Intended to study Algorithm Specialization on Coursera.

Assignment1

Implement Karatsuba's integer multiplication algorithm.

Assignment2

Implement the fast divide-and-conquer algorithm to compute the number of inversions of the given file.

Assignment3

Compute the total number of comparisons used to sort the given input file by QuickSort.

Assignment4

Run the randomized contraction algorithm to compute minimum cut of a simple undirected graph.

Assignment1

Computer strongly connected components of a directed graph using Kosaraju's algorithm.

Assignment2

Dijkstra's shortest path algorithm.

Assignment3

Implement the Median Maintenance algorithm.

Assignment4

Implement a variant of the 2-SUM algorithm with hash table.

Assignment1

(1) Run the greedy algorithm that schedules jobs in decreasing order of the difference (weight - length) and (optimally)ratio (weight/length).

(2) Run Prim's minimum spanning tree algorithm on an undirected graph.

Assignment2

(1) Implement the clustering algorithm for computing a max-spacing k-clustering.

(2) Run the clustering algorithm, but on a MUCH bigger graph.

Assignment3

(1) Implement the greedy algorithm on Huffman coding.

Assignment3

(2) Implement the dynamic programming algorithm for computing a maximum-weight independent set of a path graph.

Assignment4

(1) Implement the knapsack algorithm.

(2) Implement the knapsack algorithm on a much bigger set that the straightforward iterative implemetation uses an infeasible amount of time and space.