| August 26 | Course overview | --- | ||
| August 28 | Introduction | Chapter 2 | ||
| September 4
. |
Introduction
Math review |
Section 3.2 and Appendix A.1 |
||
| September 9 | Asymptotic notation | Section 3.1 | ||
| September 11
. |
Asymptotic notation
Recurrences |
Chapter 4 |
||
| September 16 | Recurrences | |||
| September 23 | Heap-Sort | Chapter 6 | ||
| September 25
. |
Heap-Sort
Quick-Sort |
Chapter 7 |
||
| September 30
. |
Quick-Sort
Lower bound for sorting |
Section 8.1 |
||
| October 2
. |
Lower bound for sorting
Counting sort |
Section 8.2 |
||
| October 7
. . |
Radix sort
Bucket sort Stacks and queues |
Section 8.3
Section 8.4 Section 10.1 |
||
| October 9 | Binary search trees | Sections 12.1-12.3 | ||
| October 14
. |
Binary search trees
Red-black trees |
Chapter 13 |
||
| October 16 | MIDTERM | --- | ||
| October 21 | Midterm review | |||
| October 23 | Red-black trees | |||
| October 28 | Red-black trees | |||
| October 30
. |
Red-black trees
Representing graphs |
Section 22.1 |
||
| November 4
. |
Representing graphs
Breadth-first search |
Section 22.2 |
||
| November 13
. |
Depth-first search
Topological sort |
Section 22.3
Section 22.4 |
||
| November 18
. . |
Topological sort
Shortest paths in DAG Dijkstra's shortest paths |
Chapter 24.2 Section 24.3 |
||
| November 20
. |
Dijkstra's shortest paths
NP-Completeness |
Chapter 34 |
||
| November 25 | NP-Completeness | |||
| November 27 | NP-Completeness | |||
| December 2 | NP-Completeness | |||
| December 4 | FINAL EXAM |