Project Guidelines

Due date: before Wednesday, December 15 at 5pm. Send your report to me (imunro -at- uwaterloo.ca) by e-mail (in either PDF or PostScript).

Basically: pick a problem and a paper, read the paper, and write a report about it (at most 10 pages).

You may choose a paper on your own (but see tips and suggestions below). The paper should be about algorithms, of course, and preferrably related to topics covered in class. In accordance with the "spirit" of this course, the emphasis of the paper should be on well-defined problems and algorithms with provable performance guarantees (worst-case time, expected time, approximation factor, competitive ratio, etc.). Implementations and experimental studies are not required and are not the objective.

The Report

The first part should be devoted to a clear statement of the problem and a short survey of known results. For this, you may have to read up on previous papers and do a literature search for the latest results.

The second part should be an description, in your own words, of the algorithm and/or analysis from your particular paper. You might find that papers don't necessarily give the clearest explanation. So, don't just paraphrase the paper's description. Rather, the objective is to make the paper easier to understand, for example, by finding a different way to look at the algorithm, using simpler notation, highlighting ideas as you see them to be, adding examples and intuition, etc. Be creative! With only 10 pages, don't try to explain all the details in the paper if they are too complicated and technical---an overview is more important. (If the paper contains several algorithms, focus perhaps on just one.) But do point out connections with ideas from previous papers as well as techniques we have seen from class.

The final part should be your critique of the new ideas and results from the paper, e.g., how they compare with previous (and subsequent) results and known lower bounds, how practical they are, etc. Also state open problems, including any of your own, for future work in the area. (And if through this process you are able to obtain improvements and solve an open problem, I'd love to hear about it!)

Tips

Ideally, each student should choose a different problem, so let me know what you have decided on (e.g., by e-mail or during office hrs).

You do not have to choose the latest paper with the best result on a problem; find one which is "relatively" recent (i.e., not already described in existing books or surveys) and which you think you can understand reasonably well.

To get a feel for recent research in algorithms and complexity, browse through conference proceedings such as FOCS (IEEE Sympos. on Foundations of Computer Science, QA401.S95x), STOC (ACM Sympos. on Theory of Computing, QA267.A2), and SODA (ACM-SIAM Sympos. on Discrete Algorithms, QA76.6.A278). Final versions of papers usually appear in journals.

The DBLP web site provides links to publishers' electronic copies of many papers. The CiteSeer site provides links to the authors' own electronic copies of recent papers. The latter site also tracks citations, which is handy for finding related papers. Also try Google Scholar.

Examples

Below is just a "random" list of suggested problems/papers. You are encouraged to look for other problems on your own.

• Finding cycles of length 4, 5, etc.: e.g., Yuster and Zwick (2004)
• Dynamic connectivity: the first general polylog result (amortized and randomized!) was achieved by a simple beautiful method of Henzinger and King (1999)
• Alternatives to Fibonacci heaps: Recently (2009), Haeupler, Sen, and Tarjan showed how decrease-key can be done in constant amortized time without "cascading cuts", by instead changing the "ranks" of nodes.
• Splay trees and dynamic optimality: e.g., Bose, Douieb, and Langerman and Derryberry and Sleator.
• Variations on union-find: e.g., Kaplan, Shafrir, and Tarjan. Also, another paper studied a problem that combines union-find and heaps.
• Dynamic all-pairs shortest path: several recent papers, e.g., Demetrescu and Italiano (2003), which also uses amortized analysis.
• Randomized algorithms for geometric pattern matching: Cardoze and Schulman (1998) gave randomized algorithms for pattern matching, not for strings, but for one- and higher-dimensional point sets.
• Another randomized exponential SAT algorithm: Paturi, Pudlak, and Zane (1997) gave a 3-SAT algorithm that came before Schoening's and was also quite simple. Or consider deterministic 3-SAT algorithms, the latest of which is by Scheder (2008).
• More news on SAT: it is known that in every k-CNF formula, there always exists a satisfying assignment if each clause has common variables with at most 2^{k-2} other clauses. Moser's recent award-winning paper (2009) describes a simple randomized polynomial-time algorithm (also based on local search) that almost matches this existence result.
• Faster exponential algorithms for graph coloring: two recent papers by Bjorklund and Husfeldt and Koivisto (2006), describing some surprisingly simple new algorithms.
• Faster exponential algorithms for your other favorite NP-complete problem (e.g., independent set, TSP, ...)
• Approximation algorithms for maximum metric TSP: e.g., Hassin and Rubinstein (2002) gave a short, randomized approximation algorithm for a "max" variant of the metric TSP problem.
• Approximation algorithms for maximum independent set: Berman and Furer described a simple local improvement algorithm with approximation factor about D/5 (better than the naive greedy with factor D+1) where D is the maximum degree.
• Approximation algorithms for set cover: Levin gave the latest approximation result on the k-set-cover problem using a combination of greedy and local search approaches.
• Approximation algorithms for your other favorite NP-complete problem: see the compendium of NP-hard optimization problems for inspiration.
• An on-line knapsack problem: Iwama and Taketomi investigated the competitive ratio of a variant of the on-line bin packing problem (the 1-bin case does not appear too complicated).
• An on-line coloring problem: e.g., Epstein et al. or Azar et al. studied coloring of intervals "with bandwidth" in an on-line setting.
• Rendez-vous in the plane: Two people are somewhere in the plane and want to find each other. What are good exploration strategies for this on-line problem? Anderson and Fekete, 1998 studied this problem in various settings.
• Your other favorite on-line problem (secretary problems, robot navigation, facility location or clustering, etc.).