Any notes provided are taken from Jeff Erickson's Algorithms Materials.
| Week | Day | Topic | Reading |
|---|---|---|---|
| January 12-16 | Monday |
Introduction, course administration
Algorithms and Pseudocode |
Syllabus
Introduction |
| Wednesday | Review of recurrences | Recurrence notes | |
| Friday | Review of induction and proofs | Your handy discrete math text book | |
| January 19-23 | Monday |
Martin Luther King day
No class |
|
| Wednesday | Recursion - Towers of Hanoi | Recursion notes | |
| Friday | Recursion: Subset sum and Mergesort | Recursion notes
Divide and Conquer Notes Chapter 5 of textbook |
|
| January 26-30 | Monday | Divide and Conquer: Counting inversions | Section 5.3 of text |
| Wednesday |
Review of Big-O Divide and Conquer: Integer Multiplication |
Divide and Conquer Notes and Section 5.5 of Textbook |
|
| Friday |
Intro to Dynamic Programming:
Fibonacci numbers Intro to weighted intervals |
Dynamic Programming Notes
Chapter 6 of text |
|
| February 2-6 | Monday |
Dynamic Programming: Weighted intervals
Weighted Knapsack |
Dynamic Programming Notes
Chapter 6 of text |
| Wednesday |
Dynamic Programming: Weighted Knapsack
Sequence Alignment |
Dynamic Programming Notes
Chapter 6 of text |
|
| Friday | Dynamic Programming: Sequence alignment in O(n) space | Chapter 6 of text | |
| February 9-13 | Monday | Dynamic Programming: Problem session day | Handout in class |
| Wednesday | Greedy Algorithms: Interval scheduling |
Ch. 4.1 of Textbook
Greedy Algorithm Notes, Section 2 |
|
| Friday | No lecture due to instructor illness | Finish reading either 4.1 of text or section 2 of Greedy Algorithm Notes | |
| February 16-20 | Monday |
Greedy Algorithms
Scheduling to minimize lateness |
Section 4.2 of text |
| Wednesday | Greedy Algorithms: Huffman codes | Section 4.8 of text
Section 4 of Greedy Algorithm Notes |
|
| Friday | Greedy algorithms: problem session day | handout in class | |
| February 23-27 | Monday | Introduction to Graphs | Section 3.1-3.2 of text |
| Wednesday |
Graph Algorithms
DFS, BFS, and Topological Sort |
Sections 3.2-3.5 in text | |
| Friday |
Graph Algorithms
Shortest paths |
Section 4.4 of text | |
| March 2-7 | Monday | Graph Algorithms: MST | Sections 4.5, 4.6 of text |
| Wednesday | Review for midterm | ||
| Friday | Midterm Exam | ||
| March 9-13 | Monday | No Class: Spring Break | |
| Wednesday | |||
| Friday | |||
| March 16-20 | Monday | Discrete Probability | |
| Wednesday | Randomized Algorithms | ||
| Friday | Randomized Algorithms | ||
| March 23-27 | Monday | Randomized Algorithms | |
| Wednesday | Randomized Algorithms | ||
| Friday | Reductions | ||
| March 30-April 3 | Monday | NP-Completeness | |
| Wednesday | NP-Completeness | ||
| Friday | Complexity Classes | ||
| April 6-10 | Monday | Approximation Algorithms | |
| Wednesday | Approximation Algorithms | ||
| Friday | No Class | Good Friday | |
| April 13-17 | Monday | No Class | Easter Monday |
| Wednesday | Approximation Algorithms | ||
| Friday | Approximation Algorithms | ||
| April 20-24 | Monday | Network Flow | |
| Wednesday | Network Flow | ||
| Friday | Network Flow | ||
| April 27-May 1 | Monday | Network Flow | |
| Wednesday | Network Flow | ||
| Friday | Review + overflow day | ||
| April 27-May 1 | Monday | Review | |
| Wednesday | Finals week | ||
| Friday | |||