CPS 130: Course Synopsis

1. Introduction (1.0 lecture) Models of computation, complexity of algorithms, asymptotic analysis, worst-case and average-case analysis.

2. Recurrence relations (1.5 lectures) Mathematical induction, substitution method, iterative method, master method, divide-and-conquer algorithms.

3. Sorting and selection (2 lectures) Lower bound, heap sort, merge sort, quick sort, selection in linear time.

4. Dynamic programming(1.5 lectures) Matrix-chain multiplication, longest common subsequence, optimal polygon triangulation.

5. Greedy algorithms (1.0 lectures) Activity-selection algorithm, Huffman codes, task-scheduling method.

6. Amortized analysis (1.0 lectures) Aggregate method, accounting method, potential method.

7. Data structures (2.0 lectures) Binary search trees, red-black trees, B-trees, data structures for disjoint sets

8. Basic graph algorithms (2 lectures) Breadth first search, depth first search, bi-connected components, strongly connected components.

9. Advanced graph algorithms (4 lectures) Minimum spanning tree, single-source shortest path, all-pair shortest path algorithms, transitive closure, flow networks, bipartite matching.

10. Randomized algorithms (2.5 lectures) Randomized model of computation, Monte Carlo algorithms, Las Vegas algorithms, randomized selection, hashing.

11. Numerical algorithms (3.5 lectures) integer multiplication, matrix multiplication, solving systems of linear equations, GCD, modular arithmetic, RSA public-key cryptosystem, primality testing.

12. Computational geometry (2 lectures) Convex hull, segment trees, closest pair.

13. Intractable problems (2 lectures) Polynomial time, NP completeness and reducibility, NP complete problems, approximate algorithms.