| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Thursday Aug 30 |
Which algorithm is best? Finding the closest two points. | Appendix B.1 | ||
| Tuesday Sep 4 |
Divide-and-conquer algorithms | Handout 1 | Lab 1 | |
| Thursday Sep 6 |
Divide-and-conquer algorithms (cont.) | |||
| Tuesday Sep 11 |
Asymptotic notation | Appendix B.2 | Lab 1 - early | |
| Thursday Sep 13 |
Solving recurrence equations with the master method | Appendix B.6 | ||
| 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 | Section 11.4.5 and Appendix B.5 |
||
| Tuesday Sep 25 |
Adversary lower bound technique | Handout 2 | HW 1 | HW 2 |
| Thursday Sep 27 |
Counting sort and radix sort | Section 11.4.6 | ||
| Tuesday Oct 2 |
ADT Taxonomy Part II, Set ADT | Sections 2.6.2, 7.3.2, and Chapter 20 |
HW 2 | HW 3 |
| Thursday Oct 4 |
Direct Addressing, Open Addressing | Chapters 21, 22 | ||
| Tuesday Oct 9 |
Separate Chaining | Chapter 23 | HW 3 | Lab 2 |
| Thursday Oct 11 |
Priority Queue ADT, Binary Heaps | Chapter 24 and 25 | ||
| Tuesday Oct 16 |
Ordered Collection ADT, Balanced Search Trees | Chapters 29, 33 | Lab 2 | |
| Thursday Oct 18 |
Midterm Exam | |||
| Tuesday Oct 23 |
Red-Black Trees | Chapter 34 | HW 4 | |
| Thursday Oct 25 |
B-trees | Chapter 36 | ||
| Tuesday Oct 30 |
B-trees, B+-trees | Sections 37.1-37.2 | HW 4 | Lab 3 |
| Thursday Nov 1 |
Skiplists | Sections 38.1-38.5 | ||
| Tuesday Nov 6 |
Skiplist analysis, OrderedCollection data structures comparison | Section 38.6, Section 29.7 | Lab 3 - early | |
| Thursday Nov 8 |
Digitized Ordered Collections, Spatial Collections and k-d Trees | Chapters 39 and 46, Section 47.1 | ||
| Tuesday Nov 13 |
Graph problems, representing graphs | Section 2.7, Chapter 52 | Lab 3 | HW 5 |
| Thursday Nov 15 |
Breadth-first search (BFS) | Section 53.4 | Lab 4 | |
| Tuesday Nov 20 |
Dijkstra's shortest path algorithm | Section 57.2 | HW 5 | |
| Thursday Nov 22 |
Thanksgiving Break | |||
| Tuesday Nov 27 |
Prim's and Kruskal's Minimum Spanning Tree (MST) Algorithm | Sections 57.3, 57.4 | Lab 4 - early | |
| Thursday Nov 29 |
DFS and topological sort | Sections 53.5, 53.6 | ||
| Tuesday Dec 4 |
Garbage collection algorithms | Section 53.9 | Lab 4 | HW 6 |
| Thursday Dec 6 |
Course Review | |||
| Tuesday Dec 11 |
Review Session for Final | HW 6 | ||
| Tuesday December 18 |
Final Exam 2:30pm-4:30pm |
All readings are from A Practical Guide to Data Structures and Algorithm Using Java by Goldman and Goldman