This repository contains solutions to the programming projects accompanied with Tim Roughgarden's Algorithm Illuminated series. This is a great series that you definitely don't want to miss, for more details check here Algorithm Illuminated
These solutions are just for reviewing the algorithms mentioned in the corresponding video lectures. To make the implementation simple, the solutions here are more or less the naive implementation of algorithms described in the slides, so not surprisingly, some of them might not scale to large problem sizes.
To sanity check these solutions, first you need to download the testcases from here and put them under ./algorithmsilluminated/tests/. After that try the following command:
cd ./algorithmsilluminated
python -m unittest -v
you can also run the solution file itself, sanity check is added in each of the main functions e.g.
cd ./algorithmsilluminated
./algorithm/bellbellman_ford.py
For more test cases, check here: stanford-algs. (Note the alg method defined in each solution file is used for testing the cases there)
- Sorting
- Selection
- Scheduling
- Huffman Encoding
- Knapsack Problem
- Sequence Alignment
- Weighted Independent Set
- Optimal Binary Search Tree
- Single Source Shortest Path (SSSP)
- All Pair Shortest Path (APSP)
- Strongly Connected Components
- Minimum Cut
- Minimum Spanning Tree
- TSP (Traveling Sales Man) Problem
- 2-SAT Problem
- Vertex Cover Problem
- Misc
- Data Structures
Problem definition:
Input: array of n numbers, unsorted
Output: Same numbers, sorted in increasing order
Average Running time O(nlog(n))
Pesudo code
QuickSort(array A, length n)
- if n = 1 return
- p = ChoosePivot(A, n)
- Partition A around p
- Recursively sort 1st part
- Recursively sort 2nd part
Pesudo code for Partition
Partition(A, l, r) [input corresponds to A[l...r]]
- p := A[l]
- i := l + 1
- for j = l + 1 to r
- if A[j] < p [if A[j] > p, do nothing]
- swap A[j] and A[i]
- i := i+1
- swap A[l] and A[i-1]
Code: quick_sort.py
Running time O(nlog(n))
Pseudo code
- recursively sort 1st half of the input array
- recursively sort 2nd half of the input array
- merge two sorted sub array into one
[ignores base cases]
Pseudo code for the merge step
C = output[length=n]
A = 1st sorted array [n/2]
B = 2nd sorted array [n/2]
i = 1
j = 1
for k = 1 to n
if A[i] < B[j]
C[k] = A[i]
i++
else B[j] < A[i]
C[k] = B[j]
j++
[ignore end cases]
Code merge_sort.py
Problem definition:
Input: array A with n distinct (for simplicity) numbers and a number
Output: ith order statistic (i.e.ith smallest element of input array)
Average running time O(n)
Pseudo code
Rselect(array A, length n, order statistic i)
- if n = 1 return A[1]
- Choose pivot p from A uniformly
- Partition A around p
let j = new index of p
- if j = i, return p
- if j > i, return Rselect(1st part of A, j-1, i)
- if j < i, return Rselect(2nd part of A, n-j, i-j)
Code: randomized_selection.py
Running time O(mlog(n)) (with Heap data structure)
Code: dijkstra_shortest_path.py
Running time O(mn)
Code: bellman_ford.py