I recently decided to brush up on my algorithms and data structures by writing them in Python. Though these are not optimized, they could be helpful for reference. Here is the Github repo: https://github.com/calebmadrigal/algorithms-in-python.

A some of the algorithms included:

• Mergesort in Python
• Quicksort in Python
• Depth-first search in Python
• Breadth-first search in Python
• Binary search tree algorithms in Python
• Dijkstra's in Python
• Hashtable implementation in Python
• Heap in Python
• Combinatoric algorithms in Python

Recursion is awesome, but has the downside of growing the stack, which can limit its usefulness. Some languages like Scheme, however, have Tail-call optimization, which lets programmers write Tail-recursive functions that don't grow the call stack. Python does not have Tail-call optimization (TCO), but with asyncio, we can have something like Tail-call optimization. Basically, this method uses the asyncio event loop like a trampoline function.

Example:

import asyncio

# Tail-recursive factorial using asyncio event loop as a trampoline to
# keep the stack from growing.
@asyncio.coroutine
def factorial(n, callback, acc=1):
    if n == 0:
        callback(acc)
    else:
        asyncio.async(factorial(n-1, callback, acc*n)) # async -> ensure_future in Python 3.4.4

def done_callback(result):
    print("Result: {}".format(result))
    loop = asyncio.get_event_loop()
    loop.stop ...

I've been taking the Udacity CS373 (Robotic Car) class, and this week the topic was Particle filters. Particle filters are basically a localization algorithm that accounts for error in measurements and sensors.

Anyway, part of the Particle Filter algorithm requires the generation of a new set of these things called "particles" based on the particles' weights. So to accomplish this task, the Resample Wheel algorithm was presented in class. It is a particularly elegant method of generating a new set of particles by randomly drawing from an old set of particles (with replacement). The particle weight determines the likelihood of it being picked.

Here is the algorithm (with print statements - I used these to help me understand how the algorithm works):

import random

def generate_new_particles(old_particles, weights ...