CS 466/666, Spring 2006

Advanced Algorithms

Instructor:

Meeting Time/Place:

TAs:

David Pal (DC3549B, x5672, dpal "at" cs, office hrs: Wed 2:00-3:00)
Michael Spriggs (DC2305B, x5350, mjspriggs "at" cs, office hrs: Mon 1:00-2:00)

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:

Announcements:

Midterm solutions are now available on reserve (UWD 1713) in the DC library.

Small typo in A3: in Q3c, the hint should read: "part (b) is meant to help".

Note: CS666 project guidelines are now available (see the link above).

Solutions to A5 are available electronically.

Newsgroup:

Lecture Topics:

The lectures are organized around problems instead of techniques, to motivate things better. Most of the lectures will begin with a specific problem and then explore different ideas on how to come up with 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: 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 11,16: 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)

Problem of May 18, 23: Range searching in 2D

• Algorithms: k-d trees (only briefly), range trees (O(log^2n) query), dynamic range trees (O(log^3n) amortized update)
• Illustrates: more data structure problems, multidimensional divide-and-conquer, amortized analysis, be lazy again, keep tree balanced
• Ref: de Berg et al., Computational Geometry: Algorithms and Applications, 2000 (QA448.D38 C65) [Ch5]

• 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 by Tarjan, without proof), recursive method by la Poutre (O(alpha(n)) amortized, with proof)
• Illustrates: more amortized analysis, doubling arguments, (very) slow growing functions, multilevel recurrences...
• Ref: [CLRS, Ch21]

Problem of May 30: Primality testing

• 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 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 13: 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 20: Satisfiability

• Algorithm: Papadimitriou's (Monte Carlo, O(n^2) steps for 2-SAT), Schoning's (Monte Carlo, O((4/3)^n) steps for 3-SAT, but only briefly)
• 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

• 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 July 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)

Problem of July 11: MAX-SAT

• Algorithms: greedy (factor 1/2), randomized "do-nothing" (expected factor 1/2), Goemans-Williamson (expected factor 3/4)
• Illustrates: randomized approximation algorithms, the technique of linear programming relaxation and randomized rounding
• Ref: [V, Ch16 and Ch26.4], the Goemans-Williamson paper (and other papers) from Michel Goemans' home page

Problem of July 13: "Lost cow"

• 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: Paging

• Algorithms: OPT (not on-line), LFU (not competitive), LRU and FIFO (ratio k), Random-Mark (expected ratio O(log k))
• Illustrates: on-line algorithms and competitive analysis, deterministic lower bound 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])

July 25: No class