CS 4800 Fall 2009: Schedule

All readings are from Sanjoy Dasgupta, Christos Papadimitriou, and Umesh Vazirni (DPV), "Algorithms," McGraw Hill 2008.

Note: This is an approximate schedule; it may change at any time.
Homework links will become active by the "assigned" dates.

Lectures grouped by week

1. Wed 09-09-09
2. Thu 09-10-09
   • Introduction; admistrivia; overview of CS 4800; assessment
   • Mathematical Preliminaries, Fibonacci, Big-O
   • Reading: 0 Prologue
   • Homework 01 assigned

3. Mon 09-14-09
4. Wed 09-16-09 - Homework 01 due
5. Thu 09-17-09
   • Modular Arithmetic, Primality Testing, RSA
   • Reading: 1 Algorithms with Numbers
     Extended Euclidean algorithm, From Wikipedia, the free encyclopedia
     Read "The Table Method" in particular.
   • Homework 02 assigned

6. Mon 09-21-09
7. Wed 09-23-09 - Homework 02 due
8. Thu 09-24-09
   • RSA
   • Universal Hashing, Randomized Algorithms
   • Multiplication, Recurrence Relations, Mergesort
   • Reading: 1 Algorithms with Numbers
     2 Divide-and-Conquer Algorithms - sections 2.1 through 2.3
   • Solving Recurrences via Iteration
   • Simplified Master Method
   • Homework 03 assigned

9. Mon 09-28-09
10. Wed 09-30-09 - Homework 03 due
11. Thu 10-01-09
    • Medians, Order Statistics
    • Matrix Multiplication, Polynomial Multiplication
    • Reading: 2 Medians Divide-and-Conquer Algorithms - sections 2.4 through 2.6
    • Homework 04 assigned

12. Mon 10-05-09
13. Wed 10-07-09 - Homework 04 due
14. Thu 10-08-09
    • FFT, Fast Polynomial Multiplication
    • Reading: 2 Divide-and-Conquer Algorithms - sections 2.5 and 2.6
    • FFT-circuits.pdf
    • Homework 05 assigned

15. Mon 10-12-09, Columbus Day, no class
16. Wed 10-14-09
17. Thu 10-15-09 - Homework 05 due
    • Graphs, BFS, DFS
    • Reading: 3 Decomposition of Graphs
    • Homework 06 assigned

18. Mon 10-19-09 - Homework 05 due - No late assignments accepted.
19. Wed 10-21-09
20. Thu 10-22-09 - Homework 06 due - No late assignments accepted.
    • Strongly Connected Components
    • Reading: 3 Decomposition of Graphs

21. Mon 10-26-09 review for Midterm exam
22. Wed 10-28-09 Midterm exam (in class)
23. Thu 10-29-09
    • Breadth-First Search (BFS)
    • Reading: 4 Paths in Graphs - section 4.1
    • Graph Algorithm Applet by Harriet Fell

24. Mon 11-02-09
25. Wed 11-04-09
26. Thu 11-05-09
    • Dijkstra's Algorithm, Priority Queues
    • Shortest Path - special cases
    • Reading: 4 Paths in Graphs - sections 4.2 through 4.5
    • Negative edge weights - Bellman-Ford algorithm
    • Shortest Paths in dags
    • Reading: 4 Paths in Graphs - sections 4.6 and 4.7
    • Homework 07 assigned

27. Mon 11-09-09
28. Wed 11-11-09, Veterans Day, no class
29. Thu 11-12-09 - Homework 07 due
    • Greedy Algorithms, Huffman Encoding
    • Reading: 5 Greedy Algorithms - sections 5.1 and 5.2

30. Mon 11-16-09
31. Wed 11-18-09
32. Thu 11-19-09
    • Horn Formulas, Set Cover
    • Reading: 5 Greedy Algorithms - sections 5.3 and 5.4
    • Shortest Paths in Dags, Longest Increasing Subsequence, Edit Distance
    • Reading: 6 Dynamic Programming - sections 6.1 through 6.3

33. Mon 11-23-09
34. Wed 11-25-09,Thanksgiving Break, no class
35. Thu 11-26-09, Thanksgiving Break, no class
    • Knapsack
    • Reading: 6 Dynamic Programming - sections 6.4

36. Mon 11-30-09
37. Wed 12-02-09
38. Thu 12-03-09
    • Chain Matrix Multiplication, Shortest Paths, Independents Sets in Trees
    • Reading: 6 Dynamic Programming - sections 6.5 through 6.7

39. Mon 12-07-09
40. Wed 12-09-09
41. Thu 12-10-09
    • Flows in Networks, Bipartite Matching, Duality
    • Reading: 7 Linear Programming and Reductions - sections 7.1 through 7.4

42. Mon 12-07-09
43. Wed 12-09-09
    • Zero-Sum Games, The Simplex Algorithm
    • Review for the Final Exam
    • Reading: 7 Linear Programming and Reductions - sections 7.5 and 7.6

Switch to:

• CS 4800 Fall 2009 Home Page