| Date: | Description: | Reading: |
| 3 September | First Day Details, The Role of Algorithms in Computing, Analyzing and Designing Algorithms |
Chapters 1-2 |
| 5 September | More on Analyzing Insertion Sort, Growth of Functions (Sun sorting demo), Standard Notation and Common Functions, Quiz 0 (in class) |
Chapters 2-3 |
| 10 September | More of Growth of Functions, Useful Sums and Mathematical Properties, Recurrences and Proofs |
Appendix A, Chapter 4 |
| 12 September |
More on Recurrences |
Chapter 4 |
| 17 September | Classes Follow Monday Schedule: No Class | |
| 19 September | Heapsort and Priority Queues, |
Chapter 6 |
| 24 September | Analysis of Heapsort, Quicksort, Quiz 1 due. Programming Assignment 1 due. |
Chapter 7 |
| 26 September | More on QuickSort, Lower Bounds on Comparison Sorts |
Chapter 8 |
| 1 October |
Sorting in Linear Time: Counting Sort, Radix Sort, Bucket Sort |
|
| 3 October | More on Bucket Sort, Selection: Medians and Order Statistics Quiz 2 due. |
Chapter 9 |
| 8 October | Dynamic Programming: Multiplying a Sequence of Matrices |
Chapter 15 |
| 10 October | More on Dynamic Programming, Greedy Algorithms, Quiz 3 due. |
Chapter 15 |
| 15 October |
More on Greedy Algorithms, Review Programming Assignment 3 due. |
Chapter 16 |
| 17 October |
Midterm Exam 1 |
Chapters 1-4, 6-8 |
| 22 October |
Binary Search Trees |
Chapter 12 |
| 24 October | More on Binary Search Trees and Red-Black Trees, Quiz 4 due. Programming Assignment 2 due. |
Chapters 12-13 |
| 29 October | Represenatations of Graphs (review), Minimum Spanning Trees, Programming Assignment 4 due. Quiz 5 due. |
Chapter 22-23 |
| 31 October | Growing MST's and Single-Source Shortest Paths, Quiz 6 due. |
Chapter 23-24 |
| 5 November |
Bellman-Ford Algorithm and Dijkstra's Algorithm |
Chapter 24 |
| 7 November | String Matching, Quiz 7 due. |
Chapter 32 |
| 12 November |
More on String Matching, Programming Assignment 5 due. |
Chapter 32 |
| 14 November |
Matrix Operations, Quiz 8 due. |
Chapter 28 |
| 19 November | Review | Chapters 1-4, 6-9, 12-13, 15-16, 22-24, 28, 32 |
| 21 November | Midterm Exam 2 |
|
| 26 November | NP-Completeness |
Chapter 34 |
| 28 November |
University Holiday: No Class |
|
| 3 December |
More on NP-Completeness |
Chapter 34 |
| 5 December | More on NP-Completeness, Quiz 9 due. |
Chapter 34 |
| 10 December |
Approximation Algorithms, Programming Assignment 6 due. |
Chapter 35 |
| 12 December | Review, Quiz 10 due. |
Chapters 1-4, 6-9, 12-13, 15-16, 22-24, 28, 32, 34-35 |
| TBA | Final Exam |