CS 204 Fall 2000 Course Outline and Calendar

this page last edited November 3 2000

outline

  1. administrivia
  2. overview: algorithms, design, analysis; motivating example
  3. analysis intro: counting, models of computation, RAM (uni/log), Big-O, examples: add'n loop, matrix mult'n
  4. analysis intro (cont'd): WC/BC/AC, search, decision trees, lower bound arguments
  5. divide & conquer; sorting (selection, insertion, heap, quick, merge)
  6. design intro: problem/algorithm, recursion/induction, recurrence relations
  7. quicksort AC
  8. d&c: Strassen's alg
  9. recurrence relations: master theorem
  10. data structure: union find
  11. graphs: lingo, data struct
  12. graphs: basic alg's (traversal: DFS,BFS)
  13. graphs: biconnected components
  14. graphs: MST, shortest path
  15. d&c: matrix mult'n
  16. easy vs. hard: P, NP, intractibility
  17. easy vs. hard: exhaustive search

calendar

notes can be viewed with a postscript viewer (e.g. ghostview; freeware at http://www.cs.wisc.edu/~ghost/)
to obtain multiple slides per page, use a utility such as psnup
lectures4 slides/pageweekevents reading
week 1 week 1 Sep 6-8Sep 6 first class 1.3(15-16,21-27) 3.2-4   
week 2 week 2 Sep 11-15 1.4-5
week 3 week 3 Sep 18-221.6   4.7
week 4 week 4 Sept 25-293.6-7   4.1-4
week 5week 5 Oct 2- 6Oct 4 Midterm I
week 6 week 6 Oct 11-13Oct 9 Thanksgiving4.5-6
week 7 week 7 Oct 16-203.6-7
week 8 week 8 Oct 23-307.1-3
week 9 week 9 Oct 30-Nov 38.1-2   8.4   6.6
week 10 week 10 Nov 6-10Nov 8 Midterm II
week 11week 11Nov 15-17 Nov 13 Remembrance7.6-7   8.3
week 12 week 12 Nov 20-24 9.4   10.3   10.6
week 13 week 13 Nov 27-Dec 1 13.1-13.5   13.7.1-2
week 14week 14Dec 4-6 Dec 6 last class