Approximate Lecture Outline and Reading, Fundamental Algorithms, Fall 99

Week 1. Introduction (Chapter 1, excluding sections 1.4, 1.6); running time (section 2.3.1); exponentials (section 2.0 to page 24).

Week 2. Logarithms (section 2.0 to page 25); additional reading (review notation in section 2.0; asymptotics (section 2.2); tree algorithms (section 3.4.1).

Week 3. Tree algorithms (section 4.2 up to page 98, 4th paragraph); insertion, merge, heap sort (sections 5.1, 5.2.1, 5.2.2 and pages 74-80).

Week 4. Recurrence equations (sections 2.3.1-2.4.2 through the middle of page 57).

Week 5. Quiz 1; recurrence equations continued.

Week 6. Quicksort (page 122 and section 5.2.5); lower bound for sorting (section 5.3); radix and lexicographic sort (sections 5.4.2-5.4.5 through paragraph 2, page 157).

Week 7. Random search trees (section 6.4); 2-3 trees (handout and section 6.5 excluding 6.5.3); divide and conquer: probabilistic selection (page 164), deterministic selection (pages 166-8).

Week 8. Divide and conquer: multiplication (section 11.2.1); hashing (section 6.8 through paragraph 3, page 199); graphs (chapter 7); DFS.

Week 9. Quiz 2; DFS continued.

Week 10. Shortest path problems (section 8.1).

Week 11. Shortest path problems continued (section 8.3 through page 259).

Week 12. Minimum spanning tree (sections 8.4, 9.5).

Week 13. Dynamic programming (section 11.3 through page 360); backtracking (section 11.6 through page 372); biconnectivity (section 10.1).

Week 14. Strong connectivity (section 10.2 excluding 10.2.1); NP-completeness, halting problem (chapter 13).

There will be more or less weekly homeworks.

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Aug 27, 1999