CS 466/666, Spring 2009

Advanced Algorithms

Instructor:

Meeting Time/Place:

TAs:

Course Work:

[Solutions to A1, A2, A3, A4, A5, and the midterm can be found on reserve in the DC library (UWD 1902)]

Announcements:

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

I'll continue to have office hours on 7/30 Thu (3:30-4:30), 8/4 Tue (2:30-3:30) and 8/6 Thu (3:30-4:30). Taylor will have an office hour on 8/6 Thu at 1:00-2:00 (instead of 8/3 Mon).

A5s have been marked and may be picked up, e.g., on Wednesday afternoon (between 2:30 and 5:30) or Thursday afternoon (between 2:00 and 5:30) outside my office.

7/29: A couple of clarifications on the A5 solutions:

• In Q1b, "(n+1)^{k^3}" can be reduced to "(n/3+1)^{k^3}".
• In Q1c, "part (a)" should be "part (b)" (twice). To justify the inequality OPT(S^+) <= OPT(S) + 3 eps M, note that the previous sentence implies that for any solution X for S, there is a corresponding solution X^+ for S^+ with cost(X^+) <= cost(X) + 3 eps M. Taking min over all X on both sides implies OPT(S^+) <= OPT(S) + 3 eps M.
• In Q2a, the definitions of V_L and V_H refer to the initial degrees. In the definition of t, "degree" refers to the degree at the current iteration.

7/16: Typo in the solutions to A4Q2: the parts are mislabelled because of an extra blank item ((c) -> (b), (d) -> (c), etc.) And in the A5 assignment sheet, "4" should of course be "5" in the heading! (Please note that the due date is a Tuesday.)

7/3: Typo in A4Q1: "S intersects both A_i and its complement" should be changed to "A_i intersects both S and its complement". (Also, in A4Q2(c,d,e): you can actually ignore all the |B_3^*| terms (why?).)

6/4: For A2Q2, you will still get full marks if the amortized time for initialize() is O(n log^c n) or the amortized time for x-partition() and y-partition() is O(log^c n) for any constant c.

6/4: Here's a sample past midterm exam.

5/31: In the solutions to A1Q2b, "leftmost point" should be "topmost point".

5/19: On the bonus question in A1Q3, for full marks, I still want top-k to take O(k) worst-case time (and insert to take O(1) worst-case time) and space to be O(k).

Newsgroup:

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]

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 5: 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 7, 12: 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) (for a different method, see my note)

Problem of May 21, 26, 28: "Incremental" graph connectivity---or, in disguise, the union-find problem

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

Problem of 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 4: 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, 11: Median (by Prof. Biedl)

• Algorithms: quickselect, Blum-Floyd-Pratt-Rivest-Tarjan's algorithm (O(n) worst case), Floyd and Rivest (1.5n Monte Carlo/Las Vegas)
• Illustrates: Blum et al.'s lower bound by adversary argument (1.5n deterministic), 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 16: 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 18: 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 23, 25: Minimum spanning trees

• Algorithms: Kruskal and Prim revisited, Boruvka (O(m log n)), hybrid (O(m log log n)), Karger, and Karger-Klein-Tarjan (O(m) Las Vegas)
• Illustrates: random sampling, backwards analysis (again), reducing input size by a fraction, ...
• Ref: [MR, Ch10.3], Chazelle's paper (readers' discretion is advised :-)), a proof of the sampling lemma

Problem of June 30, July 2: 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"), local search
• Ref: [MR, Ch6.1] or Papadimitriou, Computational complexity, 1994, p245, p184; Schoening's 1999 paper (just 4 pages!)

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

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

• Algorithms: OPT (not on-line), LFU (not competitive), LRU (ratio k)
• Illustrates: on-line algorithms and competitive analysis, deterministic lower bound (ratio >= k) by adversary arguments
• Ref: see the book by [BE] (and also [MR, Ch13])