| August 29 | Course overview | --- |
| August 31 | Introduction | Chapter 1 |
| September 5
. |
Math review
Asymptotic notation |
Section 2.2 and Chapter 3
Section 2.1 |
| September 7
. |
Asymptotic notation
Recurrences |
Chapter 4 |
| September 12 | Recurrences | |
| September 14
. |
Recurrences
Heap-Sort |
Chapter 7 |
| September 19 | Heap-Sort | |
| September 21 | Quick-Sort | Chapter 8 |
| September 26
. |
Quick-Sort
Lower bound for sorting |
Section 9.1 |
| September 28
. |
Counting sort
Radix sort |
Section 9.2
Section 9.3 |
| October 3
. . |
Bucket sort
Basic structures review Binary search trees |
Section 9.4
Sections 11.1, 11.2, and 11.4 Sections 13.1-13.3 |
| October 5 | Binary search trees | |
| October 10 | Red-black trees | Chapter 14 |
| October 12 | MIDTERM | --- |
| October 17 | Red-black trees | |
| October 19 | Red-black trees | |
| October 24
. |
Representing graphs
Breadth-first search |
Section 23.1
Section 23.2 |
| October 26
. . |
Breadth-first search
Depth-first search Topological sort |
Section 23.3 Section 23.4 |
| October 31
. |
Topological sort
Spanning trees |
Chapter 24 |
| November 2
. |
Spanning trees
Dijkstra's shortest paths |
Section 25.2 |
| November 7 | Dijkstra's shortest paths | |
| November 9
. |
Shortest paths in DAG
Naive string matching |
Section 25.4
Section 34.1 |
| November 14 | Rabin-Karp matching | Section 34.2 |
| November 16 | Finite-automata matching | Section 34.3 |
| November 21 | Finite-automata matching | |
| November 28 | NP-Completeness | Chapter 36 |
| November 30 | NP-Completeness | |
| December 5 | NP-Completeness | |
| December 7 | NP-Completeness |