| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Thursday Aug 30 |
Which algorithm is best? Finding the closest two points. | Section 2.2 (CLRS) | ||
| Tuesday Sep 4 |
Divide-and-conquer algorithms | Sections 2.3 and 33.4 (CLRS) | Lab 1 | |
| Thursday Sep 6 |
Divide-and-conquer algorithms (cont.) | |||
| Tuesday Sep 11 |
Asymptotic notation | Section 3.1 (CLRS) | Lab 1 - early | |
| Thursday Sep 13 |
Solving recurrence equations with the master method | Section 4.3 (CLRS) | ||
| Tuesday Sep 18 |
ADT Taxonomy Part I, Positional Collection ADT | Sections 2.1-2.6.1, Chapter 9 |
Lab 1 | HW 1 |
| Thursday Sep 20 |
Quicksort, Expected Time Complexity | Chapter 7, and Appendix C.2 (CLRS) |
||
| Tuesday Sep 25 |
Adversary lower bound technique | Handout 2 | HW 1 | HW 2 |
| Thursday Sep 27 |
Counting sort and radix sort | Sections 8.2-8.3 (CLRS) | ||
| Tuesday Oct 2 |
ADT Taxonomy Part II, Set ADT | Sections 2.6.2, 7.3.2, and Chapter 20 (GG) |
HW 2 | HW 3 |
| Thursday Oct 4 |
Direct Addressing, Open Addressing | Section 11.1 and 11.4 (CLRS) | ||
| Tuesday Oct 9 |
Separate Chaining | Sections 11.2-11.3 (CLRS) | HW 3 | Lab 2 |
| Thursday Oct 11 |
Priority Queue ADT, Binary Heaps | Chapter 6 (CLRS) | ||
| Tuesday Oct 16 |
Ordered Collection ADT, Balanced Search Trees | Section 13.2 (CLRS) | Lab 2 | |
| Thursday Oct 18 |
Midterm Exam | |||
| Tuesday Oct 23 |
Red-Black Trees | Sections 13.1, 13.3-13.4 (CLRS) | HW 4 | |
| Thursday Oct 25 |
B-trees | Chapter 18 (CLRS) | ||
| Tuesday Oct 30 |
B-trees, B+-trees | Sections 37.1-37.2 (GG) | HW 4 | Lab 3 |
| Thursday Nov 1 |
Skiplists | Sections 38.1-38.5 (GG) | ||
| Tuesday Nov 6 |
Skiplist analysis, OrderedCollection data structures comparison | Section 38.6, Section 29.7 (GG) | Lab 3 - early | |
| Thursday Nov 8 |
Digitized Ordered Collections, Spatial Collections and k-d Trees | Chapters 39 and 46, Section 47.1 (GG) | ||
| Tuesday Nov 13 |
Graph problems, representing graphs | Section 22.1 (CLRS) | Lab 3 | HW 5 |
| Thursday Nov 15 |
Breadth-first search (BFS) | Section 22.2 (CLRS) | Lab 4 | |
| Tuesday Nov 20 |
Dijkstra's shortest path algorithm | Section 24.3 (CLRS) | HW 5 | |
| Thursday Nov 22 |
Thanksgiving Break | |||
| Tuesday Nov 27 |
Prim's and Kruskal's Minimum Spanning Tree (MST) Algorithm | Chapter 23 (CLRS) | Lab 4 - early | |
| Thursday Nov 29 |
DFS and topological sort | Sections 22.3-22.4 (CLRS) | ||
| Tuesday Dec 4 |
Garbage collection algorithms | Section 53.9 (GG) | Lab 4 | HW 6 |
| Thursday Dec 6 |
Course Overview | |||
| Tuesday Dec 11 |
Review Session for Final | HW 6 | ||
| Tuesday December 18 |
Final Exam 2:30pm-4:30pm |
When possible readings are provided from Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein (CLRS). The other readings are from A Practical Guide to Data Structures and Algorithm Using Java by Goldman and Goldman (GG).