CS 666, Spring 2006
Project Guidelines
Due date: before August 15, Tuesday noon; send your report to me (tmchan)
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 small cliques in graphs: generalization of the
triangle-finding problem, e.g., see
Kloks, Kratsch, Muller (2000)
- Maximum matching:
Mucha and Sankowski (2004) very recently made
a surprising breakthrough and gave
a Monte Carlo O(n^{2.376}) algorithm using matrix multiplication,
improving the longstanding O(n^{2.5}) algorithm.
- More heaps:
Brodal's data structure (1996)
supports all Fibonacci heap operations (including
decrease-key as well as merge) in worst-case rather than amortized time;
it gets complicated, though...
- Data structures for level ancestors:
Bender and Farach-Colton (2002) gave a simpler method for
a basic query problem for trees.
- Dynamic all-pairs shortest path: several
recent papers, including
Demetrescu and Italiano (2001) and
Thorup (2005).
- 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.
- A randomized algorithm for linear programming:
Matousek, Sharir, and Welzl (1996) analyzed a simple Las Vegas
algorithm
(similar to the smallest enclosing circle algorithm from class) with
"subexponential" dependence on the dimension.
- Another randomized exponential SAT algorithm:
Paturi, Pudlak, and Zane (1997) gave a 3-SAT algorithm
that came before Schoning's and was also quite simple.
- Faster exponential algorithms for maximum independent set:
A number of papers (Tarjan and Trojanowski (1977), Robson (1986),
Beigel (1999))
gave algorithms of the form O(c^n) for smaller and smaller constants
c<2.
- Faster exponential algorithms for your other favorite NP-complete
problem (e.g., coloring, TSP, ...)
- Approximation algorithms for set cover:
Duh and Furer (1997)
gave a factor-4/3 algorithm for 3-set-cover based on a simple
local-improvement approach.
- Approximation algorithms for TSP variants: e.g.,
Aggarwal
et al. (SODA 1997) looked at an angular-metric version.
- Approximation algorithms for your other favorite NP-complete
problem: see the
compendium of NP-hard optimization problems for inspiration.
- An on-line searching problem:
Demaine et al.
studied a variant of the "lost cow" problem.
- An on-line scheduling problem:
for example,
Chrobak et al. (2004) described a number of randomized
and deterministic algorithms (and lower bounds) with interesting
competitive ratios for one version of scheduling
- Your other favorite on-line problem (secretary problems,
robot navigation, etc.).