| Date | Topic | First Edition | Second Edition | |||
| August 26 | Course overview | --- | --- | |||
| August 28 | Introduction | Chapter 1 | Chapter 2 | |||
| September 2 | Introduction | |||||
| September 4
. |
Math review
Asymptotic notation |
Sections 2.2 and 3.1
Section 2.1 |
Section 3.2 and Appendix A.1
Section 3.1 |
|||
| September 9 | Asymptotic notation | |||||
| September 11
. |
Asymptotic notation
Recurrences |
Sections 4.1-4.3 |
Sections 4.1-4.3 |
|||
| September 18 | Recurrences | |||||
| September 23
. |
Recurrences
Heap-Sort |
Chapter 7 |
Chapter 6 |
|||
| September 25
. |
Heap-Sort
Quick-Sort |
Sections 8.1-8.3 |
Sections 7.1-7.3 |
|||
| September 30
. |
Quick-Sort
Lower bounds for sorting |
Section 9.1 |
Section 8.1 |
|||
| October 2
. |
Lower bounds for sorting
Counting sort |
Section 9.2 |
Section 8.2 |
|||
| October 7
. |
Radix sort
Bucket sort |
Section 9.3
Section 9.4 |
Section 8.3
Section 8.4 |
|||
| October 9
. |
Stacks and queues
Binary search trees |
Section 11.1
Sections 13.1-13.3 |
Section 10.1
Sections 12.1-12.3 |
|||
| October 14
. |
Binary search trees
Red-black trees |
Chapter 14 |
Chapter 13 |
|||
| October 16 | MIDTERM | --- | --- | |||
| October 21 | Red-black trees | |||||
| October 23 | Red-black trees | |||||
| October 28
. |
Red-black trees
Representing graphs |
Section 23.1 |
Section 22.1 |
|||
| October 30
. |
Representing graphs
Breadth-first search Depth-first search |
Section 23.2 Section 23.3 |
Section 22.2 Section 22.3 |
|||
| November 4
. |
Depth-first search
Topological sort |
Section 23.4 |
Section 22.4 |
|||
| November 6
. |
Shortest paths in DAG
Dijkstra's shortest paths |
Section 25.4
Section 25.2 |
Section 24.2
Section 24.3 |
|||
| November 18
. |
Dijkstra's shortest paths
NP-completeness |
Chapter 36 |
Chapter 34 |
|||
| November 20 | NP-completeness | |||||
| November 25 | FINAL EXAM | --- | --- | |||
| December 2 | NP-completeness | |||||
| December 4 | NP-completeness |