| Date | Lecture Topic | Reading | Due | Assigned |
|---|---|---|---|---|
| Thursday Sept 1 |
Which algorithm is best? Finding the closest two points. | Sections 1.1-2.3 (1st ed: 1.1-1.4) |
||
| Tuesday Sept 6 |
Fast algorithm for finding closest pair of points | Section 33.4 (1st ed: 35.4) |
Lab 1 | |
| Thursday Sept 8 |
Asymptotic notation | Chapter 3 (1st ed: Ch. 2) |
||
| Tuesday Sept 13 |
Divide-and-conquer algorithms | Section 4.2 (1st ed: same) |
Lab 1 - early | |
| Thursday Sept 15 |
Solving recurrences | Section 4.3 (1st ed: same) |
||
| Tuesday Sept 20 |
Dictionary/Mapping ADT, hashing | Sections 10.2, 11.1-11.2 (1st ed: 11.2,12.1-12.2) |
Lab 1 | Homework 1 |
| Thursday Sept 22 |
Hashing analysis (and probability review) | Section 11.3.1 and Appendix C.3 (1st ed: 12.3.1 & 6.3 to middle of pg 113) |
||
| Tuesday Sept 27 |
Quicksort worst-case analysis, randomized quicksort | Section 7.1-7.2 (1st ed: 8.1-8.2) |
Homework 1 | Lab 2 |
| Thursday Sept 29 |
Analysis of randomized quicksort | Sections 7.3-7.4 (1st ed: 8.3-8.4) | ||
| Tuesday Oct 4 |
Sorting lower bound | Sections 8.1-8.2 (1st ed: 9.1-9.2) |
Lab 2 | Homework 2 |
| Thursday Oct 6 |
Sorting lower bound (cont) | |||
| Tuesday Oct 11 |
Counting sort and radix sort | Section 8.3 (1st ed: 9.3) |
Homework 2 | Homework 3 |
| Thursday Oct 13 |
Review of binary search trees | Sections 12.1-12.3 (1st ed: 13.1-13.3) |
||
| Tuesday Oct 18 |
Skip lists | handout | Homework 3 | |
| Thursday Oct 20 |
Midterm Exam | |||
| Tuesday Oct 25 |
Skip list analysis | Lab 3 | ||
| Thursday Oct 27 |
B-trees | Sections 18.1-18.3 (1st ed: 19.1-19.3) |
||
| Tuesday Nov 1 |
B-trees (cont) | Lab 3 - early | ||
| Thursday Nov 3 |
Priority Queue ADT, binary heaps | Sections 6.1-6.2 (1st ed: 7.1-7.2) |
||
| Tuesday Nov 8 |
Graph problems, representing graphs | Section 22.1 (1st ed: 23.1) |
Lab 3 | Homework 4 |
| Thursday Nov 10 |
Breadth-first search (BFS), introduce Dijkstra's alg | Section 22.2 (1st ed: 23.2) |
||
| Tuesday Nov 15 |
Dijkstra's shortest path algorithm | Sections 24.3-24.5 (1st ed: 25.1-25.2) |
Homework 4 | Lab 4 |
| Thursday Nov 17 |
Prim's Minimum Spanning Tree (MST) Alg | Sections 23.1-23.2 (1st ed: 24.1-24.2) |
||
| Tuesday Nov 22 |
Analysis of Prim's and Dijkstra's algorithms | Sections 22.3-22.4 (1st ed: 23.3-23.4) |
Lab 4 - early | |
| Thursday Nov 24 |
Thanksgiving Break | |||
| Tuesday Nov 29 |
DFS and topological sort | Sections 22.3-22.4 (1st ed: 23.3-23.4) |
||
| Thursday Dec 1 |
Garbage collection algorithms | Handout | ||
| Tuesday Dec 6 |
Student Selected Topic | Lab 4 | Homework 5 | |
| Thursday Dec 8 |
Student Selected Topic | |||
| Tuesday Dec 13 |
Review for Final | Homework 5 | ||
| Wednesday Dec 21 |
Final Exam 1:00pm-3:00pm |