Subject To Change
| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Tuesday Jan 15 |
Which algorithm is best? Finding the closest two points. | Appendix B.1 | Lab 1 | |
| Thursday Jan 17 |
Divide-and-conquer algorithms | Handout 1 | ||
| Tuesday Jan 22 |
Divide-and-conquer algorithms (cont.) | Handout 1 | Lab 1 - early | |
| Thursday Jan 24 |
Asymptotic notation | Appendix B.2 | ||
| Tuesday Jan 29 |
Analyzing Divide-and-Conquer Algorithms | Appendix B.6 | Lab 1 | HW 1 |
| Thursday Jan 31 |
ADT Taxonomy Part I, Positional Collection ADT | Sections 2.1-2.6.1, Chapter 9 |
||
| Tuesday Feb 5 |
Quicksort, Expected Time Complexity | Section 11.4.5 and Appendix B.4 |
HW 1 | HW 2 |
| Thursday Feb 7 |
Adversary lower bound technique | Handout 2 | ||
| Tuesday Feb 12 |
Counting sort and radix sort | Section 11.4.6 | HW 2 | HW 3 |
| Thursday Feb 14 |
Set ADT, Direct Addressing, Open Addressing | Chapters 20, 21, 22 | ||
| Tuesday Feb 19 |
Separate Chaining | Chapter 23 | HW 3 | Lab 2 |
| Thursday Feb 21 |
ADT Taxonomy Part II | Sections 2.6.2, 7.3.2 | ||
| Tuesday Feb 26 |
Ordered Collection ADT, Balanced Search Trees | Chapters 29, 33 | Lab 2 | HW 4 |
| Thursday Feb 28 |
Red-Black Trees | Chapter 34 | ||
| Tuesday March 4 |
B-trees | Chapter 36 | HW 4 | |
| Thursday March 6 |
Midterm Exam | |||
| Tuesday March 11 |
Spring Break | |||
| Thursday March 13 |
Spring Break | |||
| Tuesday March 18 |
B-trees, B+-trees | Sections 37.1-37.2 | Lab 3 | |
| Thursday March 20 |
Skiplists | Sections 38.1-38.5 | ||
| Tuesday March 25 |
Skiplist analysis, OrderedCollection data structures comparison | Section 38.6, Section 29.7 | Lab 3 - early | |
| Thursday March 27 |
Digitized Ordered Collections, Spatial Collections and k-d Trees | Chapters 39 and 46, Section 47.1 | ||
| Tuesday April 1 |
Priority Queue ADT, Binary Heaps | Chapter 24 and 25 | Lab 3 | HW 5 |
| Thursday April 3 |
Graph problems, representing graphs | Section 2.7, Chapter 52 | ||
| Tuesday April 8 |
Breadth-first search (BFS) | Section 53.4 | HW 5 | Lab 4 |
| Thursday April 10 |
Dijkstra's shortest path algorithm | Section 57.2 | ||
| Tuesday April 15 |
Prim's and Kruskal's Minimum Spanning Tree (MST) Algorithm | Sections 57.3, 57.4 | Lab 4 - early | |
| Thursday April 17 |
DFS and topological sort | Sections 53.5, 53.6 | HW 6 | |
| Tuesday April 22 |
Garbage collection algorithms | Section 53.9 | Lab 4 | |
| Thursday April 24 |
Course Review | |||
| Monday April 28 |
Last Day of Classes for Engineering School | HW 6 (by 5pm) | ||
| Tuesday May 6 |
Final Exam 1:00pm-3:00pm, Whitaker 218 |
All readings are from A Practical Guide to Data Structures and Algorithm Using Java by Goldman and Goldman