Fall 2003-04

## Approximate Class Schedule

week 1 (one lecture): course intro.; dynamic programming intro.

reading: white book, Ch. 16; OR green book, Ch. 15

Try the whole chapter. It's helpful to see lots of examples.

week 2: more dynamic programming: grid walks, ruler folding

week 3: longest common subsequence (LCS) problem; greedy algorithms - greedy scheduling (just because it's greedy doesn't mean it finds the optimum);

reading: white book, Ch. 17, 17.1-2; OR green book, Ch. 16, 16.1-2

week 4: review of DFS/BFS properties and some basic applications: finding cycles

reading: white book, Ch. 23, 23.1-4; OR: green book, Ch. 22, 22.1-4

week 5: articulation points; properties of DFS in directed graphs; directed acyclic graphs, topological sorting

reading on articulations points: white book, exercise 23-2, p. 495-6, which outlines the algorithm for finding articulation points. Part b of this exercise is missing some text. It should read: ... v is an articulation point of G if and only if v _has a child u for which_ there is no back edge (u,w) such that ... etc.

OR green book, exercise 22-2, pages 558-9. The statement of part b is correct.

reading for DFS on directed graphs, directed acyclic graphs, topological sort: 23.3 and 23.4 of the white book; 22.3 and 22.4 of the green book

week 6: midterm I (covers material through Tues., Sept. 30, i.e., BFS/DFS of undirected graphs and the algorithm for finding articulation points); lectures of week 6 are on strongly connected components, and single source shortest paths algorithms

reading: Ch. 23.5 and Ch. 25 of the white book; OR Ch. 22.5 and Ch 25 of the green book

week 7: the all pairs shortest paths problem and its connection with dynamic programming

reading: Ch. 26 and 26.2 of the white book; OR Ch. 25 and 25.2 of the green book;

intro. to network flows (reading: Chapter 27, 27.1, 27.2 of the white book, Chapter 26, 26.1, 26.2 of the green book)

week 8: the Ford-Fulkerson method for maximizing network flow; the max-flow min cut theorem and certificates of optimality; application of network flows to bipartite matching

week 9: linear programming; examples; integer linear programming, more examples; connections with network flows; linear programming duality and certificates of optimality

week 10: midterm II on material covered in class through last Tuesday, Oct. 28; this week's lectures cover: intro. to NP-completeness: problem transformation as a problem solving strategy (e.g., transformation to network flows or linear programming); problem transformation as a method for comparing computational difficulty; examples of problem transformation

week 11: intro to the theory of NP-completeness: class NP defined in terms of polynomial time verification; the "P vs. NP" conjecture; the statement of the Cook/Levin Theorem

week 12: dealing with hard problems: examples of approximation algorithms (e.g., for vertex cover, tsp, set cover); fixed parameter tractability; randomization techniques

week 13: completion of the above; review