CS 466/666, Spring 2007

Advanced Algorithms

Instructor:

Meeting Time/Place:

TAs:

References:

Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (2nd ed.), MIT Press, 2001 (QA76.6 .C662) [CLRS]
Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68) [MR]
Vazirani, Approximation Algorithms, Springer-Verlag, 2001 (QA76.9.A43 V39) [V]
Borodin and El-Yaniv, Online Computation and Competitive Analysis, Cambridge University Press, 1998 (QA76.9.A43 B67) [BE]

Course Work:

[Solutions will be made available in the DC library (UWD 1898)]

Announcements:

6/15: CS666 project guidelines are now available---see the link above.

Alex Lopez-Ortiz will be giving the lecture on 6/22 (new topic: approximation algorithms), as I'll be away (in particular, my Friday office hour on that day will be cancelled).

6/24: In A3 Q1a, the last sentence should read: "Prove that if L_1 and L_2 are not identical up to reordering, then the probability that F_x(L_1) = F_x(L_2) is at most (n-1)/p."

7/2: In A4 Q1, the definition of splitters is messed up: the subset S should instead satisfy the property that each A_i intersects both S and the complement of S. In other words, S \setminus A_i should be A_i \setminus S. Similarly, P \setminus A_i should be A_i \setminus P.

7/17: In A5 Q2c, line 3 should read "if Z >= X and Z >= Y". Similar changes for line 8 as well.

8/9: A5s have been marked. They can be picked up during my office hours (Friday 3:30-4:30 and Monday 3:30-4:30).

Newsgroup:

Lecture Topics:

The lectures are organized around problems instead of techniques, to motivate things better. We usually devote more than a lecture to each problem and then explore different ideas to devise an efficient algorithm. Along the way, we will indeed encounter new design techniques and variations on the analysis model (themes like amortization, randomization, approximation, online computation, etc., as promised in the handbook description), but the main emphasis is how to think about problems...

[You are of course responsible only for materials covered in the lectures (summarized below), but I have included below some extra references to papers and book chapters, mainly to introduce research issues to grad students (undergrad students: please ignore them, unless you have developed an intense passion for one of the problems :-). Note that these references are generally harder to read or go beyond the lecture materials.]

Problem of May 2, 4: Finding triangles in graphs

• Algorithms: brute-force (O(n^3)), matrix multiplication (O(n^2.81)), edge-based (O(mn)), high-low trick (O(m^1.5) or O(m^1.48))
• Illustrates: the "algorithm development cycle", reduction to something you know, setting "tradeoff" parameters, open problems
• Ref: Alon, Yuster, and Zwick's paper (1994)

• Algorithms: brute-force (O(n^3)), Graham's scan (O(n log n)), Jarvis' march (O(nh)), Timothy's (O(n log h))
• Illustrates: primitive operations, incremental algorithms, sweep algorithms, (anticipation of) amortized analysis, lower bounds (by reduction from something you know, by decision trees (Ben-Or's theorem), the possibility of beating them), "output-sensitive" algorithms, guessing, ...
• Ref: [CLRS, Ch33.3], my paper

Problem of May 14, 16, 18: Minimum (dynamically!)

• Algorithms: standard heaps (insert & delete-min: O(log n)), binomial heaps (insert: O(1) amortized; delete-min: O(log n)), Fibonacci heaps (decrease-key: O(1) amortized)
• Illustrates: data structure problems, lower bound (reduction from something you know, again), amortized analysis (by summing/charging/potential -- the binary-counter example), be lazy (but clean up later!), don't let tree shape deteriorate (Fredman and Tarjan's clever invariant)
• Ref: [CLRS, Ch19,20], the original paper by Fredman and Tarjan (1987)

• Algorithms: list method with label fields and weighted union heuristic (O(log n) amortized), tree method with weighted union heuristic (O(log n)) and path compression (O(alpha(n)) amortized)
• Illustrates: more amortized analysis, charging/doubling arguments, (very!) slow growing functions...
• Ref: [CLRS, Ch21]

• Algorithm: Miller-Rabin (Monte Carlo)
• Illustrates: randomized algorithms, probability and counting, abdundance of "witnesses", repeating to lower error probability
• Ref: [CLRS, Ch31.8], Chris Caldwell's The Prime Pages, and Agrawal, Kayal and Saxena's 2002 paper

Problem of June 1: String matching

• Algorithm: Karp-Rabin (O(n) Monte Carlo/Las Vegas)
• Illustrates: the fingerprinting technique (the "Alice-Bob" communication problem), from Monte Carlo to Las Vegas by verifying
• Ref: [CLRS, Ch32], [MR, Ch7]

Problem of June 4, 6: AND/OR tree evaluation

• Algorithm: Snir's (O(1.69^n) Las Vegas)
• Illustrates: lower bound by an adversary argument (and the possibility of beating it by randomizing), doing things "in random order"
• Ref: [MR, Ch2] (but it only proves an O(3^{n/2}) bound)

Problem of June 8: Median

• Algorithm: Floyd and Rivest (1.5n Monte Carlo/Las Vegas)
• Illustrates: Blum et al.'s lower bound by adversary argument (1.5n deterministic), Fussenegger and Gabow's lower bound by decision trees (2n deterministic for middle two), Hasse diagrams, beating lower bounds by randomizing (again!), the random sampling technique
• Ref: [MR, Ch3]; Baase and Van Gelder, "Computer Algorithms", 2000 [Ch5]

Problem of June 15: Smallest enclosing circle

• Algorithm: Seidel-Welzl (O(n) Las Vegas)
• Illustrates: randomized incremental algorithms, the hiring problem [CLRS, Ch5.1], "backwards" analysis
• Ref: de Berg et al., Computational Geometry: Algorithms and Applications, 2000 (QA448.D38 C65) [Ch4.7], or Emo Welzl's paper

Problem of June 18, 20: Satisfiability

• Algorithm: Papadimitriou's (Monte Carlo, O(n^2) steps for 2-SAT), Schoening's (Monte Carlo, O((4/3)^n) steps for 3-SAT)
• Illustrates: random walk ("gambler's ruin against the sheriff")
• Ref: [MR, Ch6.1] or Padpadimitriou, Computational complexity, 1994, p245, p184; Schoening's 1999 paper (just 4 pages!)

Problem of June 22: Vertex cover (by Prof. Lopez-Ortiz)

• Algorithms: incremental algorithm (factor 2), greedy algorithm (non-constant factor!)
• Illustrates: approximation algorithms (and the difference with "heuristics"), analysis of the approximation factor, the existence of lower bound (inapproximability) results
• Ref: [CLRS, Ch35.1]

Problem of June 25, 27: Traveling salesman (metric case)

• Algorithms: the MST-based method (factor 2), Christofides' (factor 3/2)
• Illustrates: inapproximability proof for non-metric case, more approximation algorithms and analysis, fun with graphs and parity (even/odd degrees, Euler cycles, matchings)
• Ref: [CLRS, Ch35.2], [V, Ch3.2.1-3.2.2], Arora's result for the geometric special case

Problem of June 29: Disjoint unit squares

• Algorithms: greedy/incremental (factor 1/4), grid (factor 1/4), Hochbaum-Maass improved grid (factor 1-epsilon)
• Illustrates: approximation techniques (greedy, grid, shifting), polytime approximation schemes (PTAS)
• Ref: Hochbaum and Maass' paper

Problem of July 4, 6: Bin packing

• Algorithms: first-fit/best-fit (asymp factor 1.7), first-fit-decreasing/best-fit-decreasing (asymp factor 11/9), de la Vega-Lueker (asymp factor 1+epsilon)
• Illustrates: more greedy, (anticipation of) on-line algorithms vs. off-line algorithms, rounding techniques, (asymptotic) PTAS again
• Ref: [V, Ch9]; for history of earlier results, see Johnson's survey [Ch2] in Hochbaum ed., Approximation Algorithms for NP-Hard Problems, 1997 (T57.7.A68)

• Algorithms: local improvement (factor 1/2), randomized "do-nothing" (expected factor 1/2), Goemans-Williamson (expected factor 0.878)
• Illustrates: randomized approximation algorithms, linear programming relaxation (factor 3/4 for MAX-1-2-SAT), randomized rounding, semi-definite programming relaxation (for MAX-CUT)
• Ref: [V, Ch16 and Ch26.4], the Goemans-Williamson paper (and other papers) from Michel Goemans' home page

• Algorithms: doubling (ratio 9), with random starting direction (ratio 7), with random starting direction+distance and a different base (ratio 4.592)
• Illustrates: (on-line) algorithms dealing with unknown/incomplete information, competitive analysis, beating deterministic algorithms by randomizing (again)... and the usefulness of calculus(!)

Problem of July 18, 20, 23: Paging

• Algorithms: OPT (not on-line), LFU (not competitive), LRU and FIFO (ratio k), RAND-MARK (expected ratio O(log k))
• Illustrates: on-line algorithms and competitive analysis, deterministic lower bound (ratio >= k) by adversary arguments (and how to beat it yet again by randomizing), the "k-server" conjecture
• Ref: see the book by [BE] (and also [MR, Ch13])

• Algorithms: Frequency-Count/Transpose (not competitive), Move-to-Front (ratio 2(1+c)), COUNTER (expected ratio <= 2.75)
• Illustrates: on-line data structure problems and more competitive analysis, the potential method revisited, deterministic lower bound (ratio >= 3) by adversary arguments, more randomized on-line algorithms
• Ref: [BE], Reingold, Sleator, and Westbrook's paper (note we are using the "paid exchange model" instead of the "standard model")