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 algorithms: insertion sort, heap sort, merge sort, quicksort, bucket and radix sort.
Lower bounds on running time for sorting.
Their traversals: preorder, inorder, postorder, by level.
2-3 trees: insertion, deletion and search; concatenate, merge, split.
Random search trees.
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.
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
email@example.com (Richard Cole)