Material covered by schedule subject to change, although the date of the final exam is fixed. This schedule is very tentative!

1. (3/26): Introduction, overview of Algorithm design; analysis of non-recursive algorithms.
   Read 1.1-1.4, 2.1-2.4, Appendix A.
   (3/28): Analysis of recursive algorithms. Loop Invariants, Big-Oh notation review. Review data structures.
2. (4/2): Divide and conquer algorithms (including at least Merge sort), recurrence relations, and analysis of them. Assignment #1 due.
   Read 4.1-4.3, 4.6
   (4/4) Quicksort, solving recurrence relations
   
   
3. (4/9): Master Theorem, Closest Pair, Assignment #2 due.
   Read 4.5, 4.6.
   (4/11): big-integer multiplication, midterm review. [Convex Hull].
   
4. (4/16): Midterm 1 on Monday, 4/16. Read 4.4, 8.1, 8.2, 8.4
   (4/18):Review trees, start dynamic programming.
5. (4/23): More dynamic programming., including knapsack. Assignment #3 due.
   (4/25): Even more dynamic programming (including floyd's) with routing table.
   
6. (4/30): Decreases & conquer, DFS/BFS, Strongly connected components
   Read 8.2, 5.1-5.4.
   (5/2): Topological  sort, strongly connected components, quick-select.  
   
7. (5/7):  Greedy algorithms, Prim's, Kruskal's.
   Read chapter 9.1-9.3
   (5/9): Midterm review, line-breaking problem (dynamic programming).
   
8. (5/14): Midterm 2 on Monday, 5/14.
   (5/16): Greedy graph algs Dijkstra, Prim's run-time; Locators.
   
9. (5/21): Finish Dijkstra correctness; Transform and conquer.
   Read chapter 6.1, 6.4-6.6.
   (5/23): Transform-and-Conquer, lower bound stuff. 
   
10. (5/28): Holiday, no class.
    Read chapter 7.1,7.3.
    (5/30): Space and Time Tradeoffs.
    
    
11. Final Exam date: Monday, June 4, 2007