04 and 05 Big-Omega, Big-Theta, little-o, little-omega, recursion (skyline problem), recurrence relations (guess and verify)

06 and 07 Recurrence relations (recursion trees)

08 and 09 and 10 Recurrence relations (Master Method), lower bounds (reduce sorting to skyline), decision trees, bucket and radix sort

11 and 12 k-select (randomized algorithm), k-select (deterministic linear-time algorithm)

13 and 14 and 15 and reference material on adversary strategy Problem complexity (lower and upper bounds), complexity of median-finding (adversary arguments),

16 and 17 and 18 and 19 Graph representation, minimum spanning trees (greedy algorithms), disjoint sets structure, shortest paths (Dijkstra's algorithm),

20 and 21 Shortest paths (Dijkstra's algorithm), greedy job scheduling (max number of jobs)

22 and 23 and 24 Dynamic programming: job scheduling (max total jobs' lengths), longest increasing subsequence

25 and 26 and 27 and 28 Dynamic programming: matrix chain multiplication, longest common subsequence, shortest path (Bellman-Ford)

29 and 30 NP-completeness: P, NP, NP-hard

31 NP-completeness: reductions (SAT to CLIQUE, CLIQUE to VC)

32 and 33 and 34 Approximation algorithms: VC and triangle-TSP

2 due 2 October at the start of class. Solutions

3 due 16 October at the start of class. Solutions

4 due 23 October 26 October at the start of class. Solutions

5 due 30 October at the start of class. Solutions

6 due 13 November at the start of class. Solutions

7 due 20 November at the start of class. Solutions

8 due 27 November at the start of class. Solutions

2

3

4

5 (no new material)

6

7 and tutorial slides

8 (no new material), tutorial slides - a few practice mid-term 2 solutions

9 - tutorial slides

10 and tutorial slides

11

12 and tutorial slides

Some versions of browsers automatically convert *.rtf files to *.doc files when downloading. For optimal viewing, save *.doc tutorial slide files as *.rtf, and open with WordPad, instead of Word.

Also note: some tutorial slides have "invisible" (white) text within [ ... ] ...

Practice Midterm 2

Practice Final Exam with solutions from the summer offering of CS320. This is not exactly how our final will be, but there are some good questions here.