| Date | Topics Covered | Readings (Cormen et al 2nd edition) |
Homework |
| May 15 | Review for Final | ||
| May 10 | Finish NP, TBD | Ch 34, 35.1 For Ch 34, we will only see a small amount of the material covered, namely: definitions of P, NP, NP-hard, and NP-complete, the vertex cover, independent set, and dominating set problems, and reductions and their direction. |
Final Review Sheet |
| May 8 | Finish Floyd-Warshall, start NP |
Ch 25.2, Ch 34 For Ch 34, we will only see a small amount of the material covered, namely: definitions of P, NP, NP-hard, and NP-complete, the vertex cover, independent set, and dominating set (5/10) problems, and reductions and their direction (5/10). |
Due 5/15: CLRS 25.2-1, 25.2-6 |
| May 3 | Loop invariants and proofs, start Floyd-Warshall |
CLRS pages 17-19, Ch 25.2 | Program for 5/15 |
| May 1 | Midterm 2 returned, program proofs | CLRS pages 17-19 | HW due 5/8 |
| April 26 | *****Midterm 2***** | All material covered so far. | |
| April 24 | Midterm 2 Review | All material covered so far. | |
| April 19 | Finish Single source shortest path trees | CLRS 24-24.3 | |
| April 17 | Prim's alg, start Single source shortest path trees | CLRS 23, 24.0, 24.3 | HW due 4/24 and 4/28 |
| April 12 | Disjoint Sets, Kruskal's MST | CLRS 21-21.3, 23 | |
| April 10 | Graphs: strongly connected components. Start disjoint sets | CLRS 22.5, 21.1 | HW due 4/17 |
| April 5 | Labeling edges and topological sort (2 ways) | CLRS 22.4 | |
| April 3 | Graphs: breadth first and depth first search | CLRS 22.2, 22.3 | Programming due 4/12 |
| March 22 | Hashing analysis, Graphs, and the celebrity problem | Thms 11.1, 11.2, Chap. 22.1 |
|
| March 20 | B-tree deletions, Hashing | 18.3, 11.0-11.3.2, Skip proofs for Thms 11.1, 11.2 | |
| March 15 | B-Trees, top-down 2-3-4 trees | CLRS 18, 23-tree handout |
New Programming Assignment due 3/24 |
| March 13 | MT 1 returned, 2-3 trees | Handout coming by 3/17. | Think about how to code 2-3 trees. A new programming assignment will be posted by 3/17. |
| March 8 | *****Midterm 1***** | All material so far. | |
| March 6 | Review for Midterm 1 | Extra Tuesday Office Hours: 11-12 | Some algorithm animation sites sent by a student: http://www.cs.ubc.ca/spider/harrison/Java/index.html http://www.cs.rit.edu/~atk/Java/Sorting/sorting.html http://www.cs.hope.edu/~alganim/animator/Animator.html |
| March 1 | Countsort, radixsort, bucketsort, BSTs | CLRS 8, 12-12.3 | Sample past midterm questions |
| February 27 | Finish Heaps, Lower bounds for sorting | CLRS 8.1 | Note for Programming Assignment |
| February 22 | Heaps, heapsort | CLRS 6 | Due 3/1 and 3/6 |
| February 20 | Homework review, start Heaps | CLRS B.5.2, B.5.3, 10.5 | Hw Hint |
| February 15 | Quicksort Continued, quickselect | CLRS 7.2-7.3, 7.4 (skim), 9.2 | Due 2/22 |
| February 13 | Master Method, Quicksort | CLRS 4.3, 7-7.1 | |
| February 8 | More recurrence relations | Catch-up Reading: Chapters 1-4.1, Appendix A 1058-60, 1062-66 |
Due 2/15 |
| February 6 | Recurrence relations, substitution method, and mergesort | Chapter 2.3.1, 3.2, 4.1 | |
| February 1 | Math, basic sorting, analysis | Chapter 2.1, 2.2, 3.1, Appendix A | Due 2/8 |
| January 30 | Algorithms, NIM, binary conversion | ||
| January 25 | Administration, Introduction, Find Max | Skim Chapter 1 | Due 2/1 |