Teaching

CMU 15-451, Algorithms

This course is about designing algorithms for computational problems, and how to think clearly about analyzing correctness and running time. The main goal of this course is to provide the intellectual tools needed for designing and analyzing your own algorithms for new problems you need to solve in the future. Algorithm design tools we will discuss include Dynamic Programming, Divide-and-Conquer, Data Structure design principles, Randomization, Network Flows, Linear Programming, and the Fast Fourier Transform. Some analytical tools we will discuss and use include Recurrences, Probabilistic Analysis, Amortized Analysis, and Potential Functions. We will also discuss a bit of Complexity Theory (which looks at the intrinsic difficulty of computational problems) as well as Cryptography and Algorithmic Game Theory.

CS 15-750 (Graduate Algorithms)

This course is about good data structures, design of fast algorithms, algorithmic analysis (counting steps), and proofs (eg of correctness of algorithms).

It is assumed that each student has already taken an undergraduate algorithms course in which he or she got a B or better. If not, she should take CS15-450 first.

Specific data structure topics to be taught include: Binomial Heaps, Fibonacci Heaps, Amortized Analysis, Splay Trees.

Depending on the instructor, there may be lectures on Union-Find and Self-Organizing Data Structures.

Randomizing algorithms are often either simpler or faster than their non-randomizing counterparts. It is assumed that the student will have seen the analysis of Quick-Sort. In this course, these ideas will be extended to

• Randomizing Binomial Search Trees.
• Plane and Planar Graphs, Planarity Testing Algorithms, Planar Separator Theorems.
• Flow algorithms, Matching. Randomizing matching (using Tutte's theorem).
• Reductions and NP Completeness, Cook's Theorem.
  Counting Problems and #P completeness, Counting bipartite matchings.
• Approximation Algorithms for a variety of NP-complete problems.
• Probability and Randomness. Chernoff Bounds. Random Walks on Graphs.
• The Probabilistic Method of Erdos, Alon and Spencer.

Other topics selected by the instructor may include, but are not limited to, number-theoretic algorithms, numerical analysis, machine learning, and complexity theory.

CS 15-453 (Formal Languages Automata and Computability aka FLAC)

This course provides an introduction to formal languages, automata, computability, and complexity. In the Fall of 2005, we will emphasize complexity theory more heavily than in previous semesters. The course consists of a traditional lecture component supported by weekly homework assignments and a course project. There are two midterms and a final examination.

Textbook: Introduction to the Theory of Computation (2nd Ed.) by Michael Sipser, 2005.