Approximate Lecture Outline, Honors Basic Algorithms, Fall 98

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.

Course Home Page

cole@cs.nyu.edu (Richard Cole)
Last modified: Sep 3, 1998