CS 681 Fall 2002 --- Approximate Syllabus
The course is organized around a few fundamental themes in the area of
algorithms. The exact coverage in each of these areas is subject to change. Many
of these themes appear in undergraduate algorithms courses, such as in CS 482.
The coverage here will focus on more advanced topics, and will involve very
little overlap with CS 482.
- Greedy algorithms:
- spanning trees, Steiner trees, matroids, arborescences, and multicast
- Advanced data structures:
- advanced heaps, self-organizing data-structures.
- Network Flows:
- maximum flows and minimum cuts, the preflow-push
algorithm, minimum-cost flows,
multicommodity flows, and applications to matching, scheduling, network
routing and vision.
- Dynamic programming.
- basic dynamic programming technique, dynamic
programming on trees, tree decomposition, and algorithms
for graphs with bounded tree width.
- This topic is discussed extensively in the
undergraduate course, CS 482. The coverage here will be briefer.
- Algorithms for hard problems
- Approximation Algorithms: greedy algorithms, local
search, on-line algorithms, primal-dual algorithms, the use of linear
- Randomized Algorithms:
- basic techniques from discrete probability, and applications to
optimization, distributed computation, and packet routing.