| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Tuesday Jan 17 |
Which algorithm is best? Finding the closest two points. | Sections 1.1-2.3 | Lab 1 | |
| Thursday Jan 19 |
Fast algorithm for finding closest pair of points | Section 33.4 | ||
| Tuesday Jan 24 |
Asymptotic notation | Chapter 3 | Lab 1 - early | |
| Thursday Jan 26 |
Divide-and-conquer algorithms | Section 4.2 | HW 1 | |
| Tuesday Jan 31 |
Solving recurrences | Section 4.3 | Lab 1 | |
| Thursday Feb 2 |
Mapping ADT, Direct Addressing, Separate Chaining | Sections 11.1-11.3 (except analysis) | ||
| Tuesday Feb 7 |
Separate Chaining analysis (and probability review) | Section 11.2 and Appendix C.3 | HW 1 | Lab 2 |
| Thursday Feb 9 |
Open Addressing (including analysis) | Section 11.4 | ||
| Tuesday Feb 14 |
Quicksort and Randomized Quicksort | Section 7.1-7.4 | Lab 2 | HW 2 |
| Thursday Feb 16 |
Sorting lower bound | Sections 8.1-8.2 | ||
| Tuesday Feb 21 |
Sorting lower bound (cont) | HW 2 | HW 3 | |
| Thursday Feb 23 |
Counting sort and radix sort | Section 8.3 | ||
| Tuesday Feb 28 |
Skiplists | handout | ||
| Thursday Mar 2 |
Skiplists analysis | HW 3 | ||
| Tuesday Mar 7 |
Midterm Exam | |||
| Thursday Mar 9 |
B-trees | Section 18.1-18.2 | Lab 3 | |
| Tuesday Mar 14 |
Spring Break | |||
| Thursday Mar 16 |
Spring Break | |||
| Tuesday Mar 21 |
B-trees, B+-trees | Sections 18.3, handout | Lab 3 - early | |
| Thursday Mar 23 |
Red-Black Trees (and relation to B-trees) | Sections 13.1-13.2 | HW 4 | |
| Tuesday Mar 28 |
Priority Queue ADT, binary heaps | Sections 6.1-6.2 | Lab 3 | |
| Thursday Mar 30 |
Graph problems, representing graphs | Section 22.1 | ||
| Tuesday Apr 4 |
Breadth-first search (BFS), introduce Dijkstra's alg | Section 22.2 | HW 4 | Lab 4 |
| Thursday Apr 6 |
Dijkstra's shortest path algorithm | Sections 24.3-24.5 | ||
| Tuesday Apr 11 |
Kruskal's and Prim's Minimum Spanning Tree (MST) Alg | Chapter 23 | Lab 4 - early | |
| Thursday Apr 13 |
DFS and topological sort | Sections 22.3-22.4 | HW 5 | |
| Tuesday Apr 18 |
Garbage collection algorithms | Handout | Lab 4 | |
| Thursday Apr 20 |
Student Selected Topic | |||
| Tuesday Apr 25 |
Student Selected Topic | |||
| Thursday Apr 27 |
Review for Final | HW 5 | ||
| Wednesday May 10 |
Final Exam 3:30pm-5:30pm |