Syllabus, Honors Basic Algorithms, Fall 98

Running time Program complexity; function asymptotics; asymptotic growth relations.

Mathematics The (simple) mathematics for algorithmic analysis. A simple recurrence relation and its solution; why most recurrence relations in CS are simple; recursive programs and their analysis.

Sorting
Sorting algorithms: insertion sort, heap sort, merge sort, quicksort, bucket and radix sort.
Lower bounds on running time for sorting.

Trees
Their traversals: preorder, inorder, postorder, by level.

Search Trees
2-3 trees: insertion, deletion and search; concatenate, merge, split.
Random search trees.

Priority queues
Floyd's heap.

Hashing
Open and closed.

Directed and Undirected Graphs -- the basics
Connected components; DFS and BFS.
Dijkstra and the power of greed; the significance of an ADT.
Floyd and Warshall's algorithms. Path recovery.
Reductions among graph problems.

More on data structures
Merge-Find a.k.a. Union-Find.
Hybrid structures -- an introduction.

More on Graphs
Topological sort: DFS or BFS. Cycle finding.
Spanning trees (and forests); Prim and Kruskal's algorithms.
Strong Components.

Algorithm design paradigms
Divide-and-Conquer: Multiplication, Tournaments, Selection and divide-and-throw-away.
Dynamic programming: Simple recursive series, Computing odds.
Greedy algorithms: Dijkstra; maximal paths.

If time permits
Undecidability; The Halting Problem. NP-completeness.

Course Home Page

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