Spring 1999
CS 330 or consent of instructor.
[CLR] Algorithms, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill, 1990.
CS530 is the graduate-level continuation of CS330. The course will cover some of the core-topics, already studied in CS330 (or in some equivalent course at another university), but with more details and rigor. In addition, we will present a selection of advanced topics (additional tools for analyzing algorithms, refinements of design methodology, more advanced application areas).
Chapters and sections listed below refer to: either background material or material to be covered fresh in CS530. Most of the background material is assumed known; the little of it that is not known already can be learned without the instructor's help.
What is "analysis of algorithms", basic sorting techniques (Chap 1). Growth of functions and asymptotic notation (Section 2.1). Summations (Chap 3 once over lightly).
Recurrences and their solutions (early sections of Chap 4). Discrete mathematics (Chap 5). Counting and elementary probability (early sections of Chap 6).
More advance sorting techniques. Heaps, heapsort, priority queues (Chap 7). Quicksort (early sections of Chap 8).
Elementary techniques for representing discrete structures: stacks, queues, linked lists (Chap 11). Hash tables, hash functions (Chap 12). Binary search trees (Sections 13.1, 13.2, 13.3).
Programming methods: dynamic programming (early section of Chap 16), greedy algorithms (early sections of Chap 17).
Elementary graph algorithms: breadth-first search, depth-first search, topological sort (Chap 23).
More advanced graph algorithms: single-source shortest paths (early sections of Chap 25), all-pairs shortest paths (early sections of Chap 26), maximum flow (early sections of Chap 27).
Topics listed below from chapters preceding Chapter 28 are occasionally covered in CS330 (and other undergraduate-level courses on algorithms). They are purposely included here as a warm-up transition to the more advanced topics after Chapter 28.
Handout 2. Randomized Algorithms (3 lectures).
Randomized linear search, quicksort and selection. Randomized
algorithms for order statistics. Randomized verification of polynomial
identities. Monte Carlo versus Las Vegas. There will be occasional
reference to review material from Chapters 1 to 10 in [CLR].
Chapter 16. Dynamic Programming (1 lecture).
Matrix chain multiplication, longest common subsequence, polygon
triangulation. The book points out that matrix-chain multiplication
can be viewed as a special case of polygon triangulation; specifically,
every instance of the first problem can be cast as an instance of the
second problem. Put differently, using notions introduced in
Chapter 36 of [CLR], matrix-chain multiplication can be reduced
to polygon triangulation.
Chapter 31. Matrix Operations (1+2/3 lectures).
Review on your own whatever you need in Section 31.1 for later sections.
Strassen's algorithm for matrix multiplication (Section 31.2),
adaptation of Strassen's algorithm to matrices over "quasirings" such
as boolean matrices (Section 31.3), LUP decomposition
(Section 31.4), efficient reduction of matrix multiplication to
matrix inversion and vice-versa (Section 31.5).
Handout 2. Randomized Algorithms (1/3 lecture).
Verification of matrix multiplication.
Chapter 17. Greedy Algorithms (1 lecture).
Activity-selection problem (Section 17.1), the 0-1 and fractional
knapsack problem (Section 17.2).
Chapter 25. Graph Algorithms: Single-Source
Shortest Paths (1+1/2 lectures).
Brief overview of general approach (Section 25.1),
Dijkstra's algorithm (Section 25.2), the Bellman-Ford algorithm (Section 25.3),
particular case of directed acyclic graphs (Section 25.4) on your own,
difference constraints and shortest paths (Section 25.5).
Chapter 26. Graph Algorithms: All-Pairs
Shortest Paths (1+1/2 lectures).
Shortest paths and matrix multiplication (Section 26.1), the
Floyd-Warshall algorithm (Section 26.2).
Chapter 27. Graph Algorithms: Maximum Flow
(1+1/2 lecture).
Review of basic concepts (Section 27.1), the Ford-Fulkerson method and
the "Max Flow/Min Cut" theorem (Section 27.2), maximum bipartite
matching (Section 27.3).
Handout 2. Randomized Algorithms
(1/2 lecture).
Finding a min-cut of a undirected multigraph.
Chapter 30. Algorithms for Parallel Computers
(2 lectures).
Pointer jumping (Section 30.1), CRCW versus EREW (Section 30.2), proof
of Theorem 30.1 omitted in class, Brent's theorem (Section 30.3) with
all proofs omitted. To understand statements of Theorem 30.2 and
Corollary 30.3: read Section 28.1 on "comparison networks" and
Section 29.1 on "combinational circuits". Work-efficient parallel
prefix computation (Section 30.4).
Chapter 28. Sorting Networks
(1 lecture).
All sections in this chapter (not very long). You can go easy with
the proofs: You will not be responsible for them, even though they are
relatively easy and straightforward.
Chapter 36. NP-completeness
(5 lectures).
Polynomial time (Section 36.1), polynomial-time verification (Section 36.2),
NP-completeness and reducibility (Section 36.3), NP-completeness
proofs (Section 36.4). More general notion of polynomial-time reducibility
than the notion in Section 36.3, which allows a polynomial number of
polynomial transformations f(x), rather than a single such transformation
(see Figure 36.4 on page 931). NP-completeness of several problems (Section 36.5):
HAM-CYCLE, TSP, and others not in the book (1-in-3-CNF-SAT, PARTITION by reduction
from 1-in-3-CNF-SAT, 0-1-KNAPSACK, BIN-PACKING).
Chapter 37. Approximation Algorithms
(1 lecture).
Classification of approximation algorithms (Chapter introduction),
approximation algorithm for VERTEX-COVER (Section 37.1) and the
relationship with the problem of maximal matching (not in the book),
approximation algorithm for Euclidean TSP (Section 37.2).
No Handout (sorry!). Approximation Algorithms
(1 lecture).
Christofides algorithm for Euclidean TSP, based on several preliminary
properties: Eulerian cycles in undirected multigraphs (computed in low
polynomial time), minimum-cost perfect matchings for complete undirected
graphs with an even number of vertices (computed in low polynomial time),
and the following fact: If H* is an optimal tour for an instance
of the Euclidean TSP, we can "quickly" define two disjoint matchings
M1 and M2 for the odd-degree vertices such that
c(M1) + c(M2) does not exceed c(H*).
Chapter 37. Approximation Algorithms
(1 lecture).
Approximation algorithm for SET-COVER (Section 37.3).
NP-completeness of BIN-PACKING, by reduction from PARTITION,
and various approximation algorithms for it: First-Fit,
Best-Fit, First-Fit-in-Decreasing-order (part of this
material is covered in Problem 37-1, page 983, more details
are in Section 6.1 of the [GJ] book).
No Handout (sorry!). Approximation Algorithms
(1 lecture).
Absolute-error approximation algorithms for: 3-GRAPH-COLORABILITY
and MAX-k-BIN-PACKING, both of which are NP-hard.
(There is an integer e > 0 such that
C* <= C <= C* + e, for minimization problems, or
C* - e <= C <= C* , for maximization problems.)
If P is not equal to NP, impossibility of absolute-error
approximation algorithms for VERTEX-COVER.
Fully polynomial-time approximation schemes (from Introduction of
Chapter 37). If P is not equal to NP, impossibility of fully
polynomial-time approximation schemes for BIN-PACKING.
Chapter 37. Approximation Algorithms
(1 lecture).
Fully polynomial-time approximation scheme for
SUBSET-SUM (Section 37.4).
Hand-Written Handout. Tiling Algorithms
(2 lectures).
There is no discussion of tiling in [CLR]. I present several algorithmic
issues related to tiling. Special cases of tiling that are solvable
in polynonial-time, cases of tiling that are NP-complete, and cases
that are undecidable. The material is collected from various textbooks
and papers.
Assaf Kfoury
Created: 99.01.25
Modified: 99.05.10