Algorithms: Design and Analysis, Part 1

Week 1: Introduction.  Asymptotic analysis including big-oh notation.  Divide-and-conquer algorithms for sorting, counting inversions, matrix multiplication, and closest pair.

Week 2: Running time analysis of divide-and-conquer algorithms.  The master method.  Introduction to randomized algorithms, with a probability review.  QuickSort. 

Week 3: More on randomized algorithms and probability.  Computing the median in linear time.  A randomized algorithm for the minimum graph cut problem.

Week 4: Graph primitives.  Depth- and breadth-first search.  Connected components in undirected graphs.  Topological sort in directed acyclic graphs.  Strongly connected components in directed graphs.

Week 5: Dijkstra's shortest-path algorithm.  Introduction to data structures.  Heaps and applications.

Week 6: Further data structures.  Hash tables and applications.  Balanced binary search trees.