Spring 1999

*Prerequisites:*-
CS 330 or consent of instructor.

*Required Textbook:*-
[CLR]

*Algorithms*, by T. Cormen, C. Leiserson, and R. Rivest, McGraw-Hill, 1990. *Other Textbooks (not required).*-
*Overview:*-
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.

*Background Material*(all references to [CLR]):-
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).

*Covered Fresh*(all from [CLR], unless otherwise noted):-
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). *Mid-term exam on material covered up to this point.*-
**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. *End-of-term exam on all the material covered during the semester,*

with emphasis on topics after the mid-term.-

Assaf Kfoury

Created: 99.01.25

Modified: 99.05.10