Tentative Course Syllabus

The topics and order listed below are tentative and subject to change.

Review of algorithm design and analysis

(Chapts 1-4) time and space complexity; average and worst-case analysis; asymptotic notation; summations; recurrence relations.

Divide and Conquer

(Chapt 7, 9) Maximum contiguous subarray, polynomial multiplication, randomized quicksort, randomized selection

Graph algorithms

(Chapts 22-25) Graph representations, depth-first and breadth-first search, applications of DFS (articulation points and biconnected components), minimum spanning trees (Kruskal's and Prim's) and Dijkstra's shortest paths.

Dynamic Programming

(Chapt 15) 0-1 Knapsack, chain-matrix multiplication, all-pairs shortest paths; longest common subsequence.

Greedy Algorithms

(Chapt 16) Fractional Knapsack, Huffman codes