**Sept 9.**
Introduction. Running time. Sequential vs. binary search.

**Sept 14.**
Asymptotics; computing running time.

**Sept 16.**
Tree algorithms and recursion.

**Sept 21.**
Runtime of tree algorithms. Token arguments.
Counts of internal and external nodes in trees.

**Sept 23.**
Elementary sorting and invariants.

**Sept 28.**
Recurrence equations: calculating run-time of recursive algorithms.

**Sept 30, Oct 5.**
O(n log n) time sorting: merge sort, heap sort, quick sort.

**Oct 7.**
Lexicographic sort.

**Oct 12, Oct 14.**
Divide and conquer - selection, other examples.

**Oct 19, Oct 21.**
2-3 trees and extensions.

**Oct 26.**
Midterm.

**Oct 28.**
Hashing.

**Nov 2.**
Graphs and connected components.

**Nov 4, Nov 9.**
Topological sort, biconnected and strong components.

**Nov 11, Nov 16.**
Single source shortest path; all pairs shortest path.

**Nov 18, Nov 23.**
Reductions among graph problems.

**Nov 25.**
Minimum spanning trees.

**Nov 30.**
Union-find.

**Dec 2, Dec 7.**
Dynamic programming, backtracking.

**Dec 9, Dec 14.**
Halting problem, NP completeness, Public Key cryptography.

**Dec 21, 12:00-1:50pm.**
Final Exam.

There will be more or less weekly homeworks.

cole@cs.nyu.edu (Richard Cole)

Last modified: Sep 3, 1998