megamusz/algorithmsilluminated

Exercises for the Algorithm Illuminated series

Algorithm Illuminated Exercises

Overview

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

Intention

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.

Getting Started

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)

List of Algorithms

• Sorting
  • Quick Sort
  • Merge Sort
• Selection
  • Randomized Selection
• Scheduling
• Huffman Encoding
• Knapsack Problem
• Sequence Alignment
• Weighted Independent Set
• Optimal Binary Search Tree
• Single Source Shortest Path (SSSP)
  • Dijkstra's shortest path
  • Bellman-Ford
• All Pair Shortest Path (APSP)
  • Floyd-Warshall
  • Johnson
• Strongly Connected Components
  • Kosaraju's 2-pass Algorithm
• Minimum Cut
  • Karger's mincut algorithm
• Minimum Spanning Tree
  • Prim's Algorithm
  • Kruskal's Algorithm
• TSP (Traveling Sales Man) Problem
• 2-SAT Problem
  • Papadimitriou's algorithm
• Vertex Cover Problem
• Misc
  • Karatsuba multiplication
  • Counting inversions
  • Median maintenance
  • Two Sum
• Data Structures
  • Heap
  • Hash-table
  • Union-Find

Sorting

Problem definition:
Input: array of n numbers, unsorted
Output: Same numbers, sorted in increasing order

Quick Sort

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

Merge Sort

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

Selection

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)

Randomized Selection

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

Scheduling

Huffman Encoding

Knapsack Problem

Weighted Independent Set

Randomized Selection

Single Source Shortest Path (SSSP)

Dijkstra

Running time O(mlog(n)) (with Heap data structure)

Pseudo code

Code: dijkstra_shortest_path.py

Bellman-Ford

Running time O(mn)

Code: bellman_ford.py

All Pair Shortest Path (APSP)

Floyd-Warshall

Johnson

Strongly Connected Components

Kosaraju's 2-pass Algorithm

Sequence Alignment

TSP (Traveling Sales Man) Problem

Vertex Cover Problem