Python implementation of a number of algorithms, some of which (but not all) are homeworks taken from the Coursera Specialization by Tim Roughgarden at Stanford.
Here's a list from the coursera class:
- Karatsuba: a faster algorithm for multiplication
- Inversion: Find the number of inversions in an array: uses mergesort as a basis
- quicksort: an implementation of quicksort
- MinCut: an algorithm that operates on a graph to calculate the minimun number of edges that can divide the graph in 2.
- SCC: Find the Strongly Connected Components in a directed graph using Breadth Depth Search
- djikstra: Djikstra's Shortest Path Algorithm
- prim: The PRIM Minimim Spanning Tree algorithm
- schedule: A Greedy algorithm for a scheduling task given weight and completion times for a series of jobs
- median-maintenance: median-maintenance algorithm using a min-heap and a max-heap
- 2-sum: 2-sum algorithm where the value is in a range
- clustering: Max-spacing clustering algorithms using kruskal's algorithm with a Union-Find data structure
- huffman: The Huffman variable encoding algorithmalgorithm
- mwis: The Maximum Weighted Independent Set Algorithm using Dynamic Programming
- knapsack: The Dynamic Programming implementation of the Knapsack problem
Other Algorithms and routines:
- Bit Manipulation: some routines for manipulating bits
- Counting: An algorithm to find two values in an array that sum up to a desired value
- itoa: algorithms for both atoi() and itoa()
- reverse: algorithm to reverse a number, considering overflow
- Container: Find the Container With Most Water given a list of values corresponding to container edges.
- fastpath: A Dynamic Programming Algorithm to find the fastest path in an array where each index value consists of allowed look-ahead steps