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

cole@cs.nyu.edu (Richard Cole)

Last modified: Sep 3, 1998