Material covered by schedule subject to change, although the date of the final exam is fixed. This schedule is very tentative!
Schedule is numbered by week.
- (1/3): Introduction, overview of Algorithm design; analysis of non-recursive algorithms.
Read 1.1-1.4, 2.1, 2.3, 2.4, Appendix A.
-
(1/8): Analysis of recursive algorithms. Loop Invariants, Big-Oh notation review. Review data structures.
Read 2.2, 4.1-4.3
(1/10) Divide and conquer algorithms (including at least Merge sort), recurrence equations, and analysis of them.
Assignment #1 due.
-
(1/15): MLK day, no class.
Read 4.6.
(1/17): Master Theorem, Closest Pair, Convex Hull.
Assignment #2 due.
-
(1/22): Midterm Review and More practice
(1/24): Midterm 1 on Wednesday, Jan. 24.
-
(1/29): Review trees, start dynamic programming.
Read 4.4, 8.1, 8.2, 8.4
(1/31): More dynamic programming.
-
(2/5): Start Decrease-and-Conquer. More Dynamic Programming.
Assignment #3 due.
Read 8.2, 5.1-5.4.
(2/7): Decrease-and-Conquer
-
(2/12): Assignment #4 due. Decrease-and-Conquer. Greedy algorithms.
Read chapter 9.1-9.3
(2/14): More Greedy Algorithms
-
(2/19): President's Day no class
(2/21): Midterm 2 on Wednesday, Feb. 21.
-
(2/26): More Greedy Algorithms.
Assignment #5 due.
(2/28): Transform-and-Conquer.
-
(3/5): Assignment #6 due. Transform-and-conquer continued.
Read chapter 6.1, 6.4-6.6. Read chapter 7.1,7.3.
(3/7): Space and Time Tradeoffs.
- Final Exam date: Monday, Mar.. 12th