### **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