CS 466/666, Spring 2011

Advanced Algorithms

Instructor:

Meeting Time/Place:

TAs:

Course Work:

Announcements:

I will hold an extra office hour on Friday (August 12) from 2:00 to 3:00.

My Monday (August 8) office hour will be moved to Tuesday (August 9) from 12:30 to 1:15. And A4s have been marked and are available for pick-up during my office hour on Tuesday.

Here's a sample past final exam (ignore Q1b and Q5).

Solutions to A1, A2, A3, A4, and the midterm (call number UWD 1104) are available in the DC library reserve.

7/5: Error in midterm model solutions on Q2e: we should return "prime" iff at least one run says "prime".

6/28: Note that in A3Q1a, the directed cycle does not have to be simple.

6/24: Project guidelines for grad students are now available.

Here's a sample past midterm exam.

6/9: Minor correction to the solution of A2Q3b: technically we need to assume in the algorithm that when A and B have the same number of blocks, the tie is resolved by insisting that the size of alpha is at least the size of beta.

6/5: Correction to the solution of A1Q3c (the direction of inequality is messed up): The change in potential is -2k/3 + |l-2k/3| - |l-k| <= -2k/3 + |(l-2k/3)-(l-k)| <= -2k/3+k/3 = -k/3. Hence the decrease is at least k/3.

5/15: For A1 Q1b, it is fine if your algorithm takes O(n(l'-l)^2 + n^2) time.

Newsgroup:

References:

Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms (3rd ed.), MIT Press, 2009 (QA76.6.C662) [CLRS] (chapter numbers below refer to the 2nd ed.)
Motwani and Raghavan, Randomized Algorithms, Cambridge University Press, 1995 (QA274.M68) [MR]
Mitzenmacher and Upfal, Probability and Computing, University Press, 2005 (QA274.M574)
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]

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 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.]

Problem of May 3: Finding triangles in graphs

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

Problem of May 5, 10: Convex hulls in 2D

• 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

• 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], Tarjan's original paper or a newer paper by Seidel and Sharir (our recursive analysis from class is inspired by/simplifies theirs)

Problem of May 31, June 2: 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 7: 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 9: 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 17: 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

• Algorithm: Floyd and Rivest (1.5n Monte Carlo/Las Vegas)
• Illustrates: Blum et al.'s lower bound by adversary argument (1.5n deterministic), sketch of 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]

• 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]

• 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

• 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

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

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