CS 466/666, Spring 2015

Advanced Algorithms

Instructor:

Meeting Time/Place:

TAs:

Course Work:

Announcements:

My office hours during exam period: July 29 Wed 12:00-1:00; July 31 Fri 11:30-12:30; Aug 5 Wed 12:00-1:00; Aug 12 Wed 12:00-1:00; Aug 14 Fri 11:30-12:30.

Here's a sample past final exam (note: the list update problem mentioned in Q5 was not covered this term).

A4Q4(b) two typos: First, S \cap A_j \neq \emptyset should be S \cap A_j = \emptyset. Second, in the exponent, \sum_{i\in A_j} y_j should be \sum_{i\in A_j} y_i.

A3Q2(c) minor typo: "(a) is meant to" -> "(b) is meant to"

I will be away for another conference on June 23 and 25; Prof. Bin Ma will give guest lectures on those days (on the topic of approximation algorithms).

Here's a sample past midterm exam. The midterm will cover material up to and including June 9's lecture.

I will be away on June 16 Tuesday; Prof. Anna Lubiw will give a guest lecture that day. I will hold an extra office hour on June 12 Friday at 11:30-12:30.

A1Q2: in line 4 of the pseudocode of the proposed greedy algorithm, "> x_i" should be "> x_{i+1}".

Piazza:

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., which is available online)
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 5: Finding triangles in graphs

• Algorithms: brute-force (O(n^3)), matrix multiplication (O(n^2.373)), 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

Problem of May 14, 19: 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) (for a different method, see my note)

Problem of May 21, 26: "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], Tarjan's original paper

Problem of May 28: 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 2: 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: 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 9: 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

• 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 (it's complicated), a proof of the sampling lemma

Problem of June 16: 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!)

• Illustrates: approximation algorithms
• Algorithms: incremental algorithm for vertex cover (factor 2), MST-based algorithm for traveling salesman (factor 2), Christofides' algorithm for traveling salesman (factor 3/2)
• Ref: [CLRS, Ch35.1, Ch35.2], [V, Ch3.2.1-3.2.2]

• 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); Rothvoss' recent paper

Problem of July 16, 21: 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)
• Ref: see [MR, Ch13] (or the book [BE])

University Policies:

The Office of Academic Integrity's website contains detailed information on UW policy for students and faculty.

This site explains why academic integrity is important and how students can avoid academic misconduct. It also identifies resources available on campus for students and faculty to help achieve academic integrity in—and out—of the classroom.

Grievance: A student who believes that a decision affecting some aspect of his/her university life has been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70 — Student Petitions and Grievances, Section 4.

Discipline: A student is expected to know what constitutes academic integrity, to avoid committing academic offenses, and to take responsibility for his/her actions. A student who is unsure whether an action constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating) or about "rules" for group work/collaboration should seek guidance from the course professor, academic advisor, or the Undergraduate Associate Dean. When misconduct has been found to have occurred, disciplinary penalties will be imposed under Policy 71 — Student Discipline. For information on categories of offenses and types of penalties, students should refer to Policy 71 — Student Discipline.

Avoiding Academic Offenses: Most students are unaware of the line between acceptable and unacceptable academic behaviour, especially when discussing assignments with classmates and using the work of other students. For information on commonly misunderstood academic offenses and how to avoid them, students should refer to the Faculty of Mathematics Cheating and Student Academic Discipline Policy.

Appeals: A student may appeal the finding and/or penalty in a decision made under Policy 70 — Student Petitions and Grievances (other than regarding a petition) or Policy 71 — Student Discipline if a ground for an appeal can be established. Read Policy 72 - Student Appeals.