CS 666, Fall 2009
Project Guidelines
Due date: before December 9, Wednesday, 5pm.
Send your report to me (biedl -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 least 5 and at most 10 pages;
content is more important than word count.)
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:
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).
Topics may be done in groups, but a group of k students is expected
to cover k times as much material (and hence have significantly more
pages, though probably less than k*10.)
If you are interested in a problem that is already taken,
you could still consider a variation of the problem, or team up with
the student that took it. Talk to me about it.
You do not have to choose the latest paper with the best result on a
problem; find one which is "relatively" recent (usually that means it's
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 library has many journals in electronic versions that you
can accss with any browser from a UWaterloo computer. (To access them
from home, insert `.proxy.uwaterloo.ca' after the first part of the URL,
and then enter your library card number and name.)
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.
Possible topics:
Below is just a "random" list of suggested problems/papers. You are
encouraged to look for other problems on your own, but
double-check with the instructor whether your topic is appropriate.
Projects will be marked if they have been "taken".
- Priority queues in O(log log U) time with van Emde Boas trees.
This topic is old enough to have many course notes and even a
Wikipedia
page devoted to it; search the web yourself and pick your favorite
reference.
You could also look at Fredman and Willard's fusion trees (STOC'90), and
Andersson's exponential search trees (FOCS'96).
- Edge coloring bipartite graphs: can be
done very fast with a simple algorithm and a beautiful potential function
argument.
A. Schrijver, 1999.
- Alternatives to Fibonacci heaps:
Chan, 2009
uses Quake heaps to achieve good time bounds, and lists lots of
other alternatives. One more not listed there is by
Haeupler, Sen, and Tarjan (2009). Pick one or more of these,
explain and compare.
- 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...
- Heaphull?
We've seen convex hull algorithms based on insertion, selection, and
divide and conquer, i.e., they mirror sorting algorithms. Is there
a convex hull algorithm that mirrors heapsort? (Mantler and
Snoeyink, 2001)
- Convex hulls in 3D:
Many textbooks cover parts of this; give an overview of some existing
algorithms. The second half of
[Chan, 1996]
is a good starting point for references and gives an adaptive algorithm.
- Orthogonally convex hulls:
Something like convex hulls can also be defined for rectilinear polygons,
but the definition isn't as clear-cut, and the computation different.
(Ottmann, Soisalon-Soininen, Wood, 1984)
- Convex hulls of intersection points:
Even though n line segments may define Theta(n^2) intersection points,
the convex hull of these intersection points can be computed in O(n log n)
time. (Arkin,
Mitchell, Snoeyink, 2008).
- Dynamic convex hulls in 2D: can we maintain the
UH in a data structure that supports insertions and
deletions of points with good amortized bounds?
See Brodal and Jacob, FOCS 2002 and the references therein.
- Dynamic convex hulls in 3D: same as above, but one
dimension up and using different techniques.
Chan, SODA 2006.
This project has been taken.
- Lower bound for selection: Explain the lower bound
for randomized algorithms for selection by
Cunto
and Munro, 1989. A bit of background as to what lower bounds
for randomized algorithms mean would also be appropriate.
- Minimum enclosing disk with obstacles: What if we
want the minimum enclosing disk, except that we can't use all those
whose center falls into a set of (given) obstacles? Halperin et al. (2002) give a randomized algorithm
for this.
- Dynamic connectivity:
the first general polylog result (amortized and randomized!)
was achieved by a simple beautiful method of
Henzinger
and King (1999)
- Fully-dynamic graph maintenance: Keep connected
components under insertions and deletions. Or maybe even keep
maintain minimum spanning trees and other structures?
Holm et al.
give data structures for many problems here.
- Dynamic connectivity (reachability) for directed graphs:
lots of recent papers here; for example,
Roditty and Zwick's (FOCS'02) has a number of
algorithms, some of which are not too complicated (some are randomized)
- Mergeable Trees This is a data structure that
maintains dynamic rooted trees, similarly to the union-find
structures that we saw Georgiadis et al. (SODA 06).
- Variations on union-find:
e.g.,
Kaplan, Shafrir, and Tarjan. Also,
another
paper studied a problem that combines union-find
and heaps.
- Labeling schemes for ancestor queries:
studied by
Abiteboul, Kaplan, and Milo (SODA'01) and
Alstrup and Rauhe (SODA'02); supposedly this problem
has applications to XML search engines
- Approximation algorithms for planar graphs:
Many problems, e.g. independent set, can be approximated much
better on planar graphs.
Baker gave such approximation schemes, based on an intricate
dynamic program.
- Fixed-parameter tractable algorithm for MaxCut:
The title says it all.
(Raman, Saurabgh, 2007)
- Bin packing and variants:
Han, Iwama, et al.
(SODA 2007) studied "strip packing", Jansen and Solis-Oba (IPCO 08) gave a PTAS
for square packing, Jansen and Solis-Oba (SODA 06) study 3D strip packing...
- 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.
- Lost-cow problem:
Demaine, Fekete, Gal 2006 and
Dorrigiv and Lopez-Ortiz, 2008 studied the cow-path problem with other cost-functions.
- Algorithms for power savings:
Another very useful online problem: when should your computer go into
sleep state?
Irani, Shukla and Gupta, 2007.
The following are three `broad' problems-areas where you can pick
a specific paper yourself by searching the literature. Obviously,
nothing that has been covered in class can be used.
- Randomized algorithms for your favorite problem,
where using randomization yields faster/simpler/better-in-practice
algorithms than deterministic ones.
- Faster exponential algorithms for your favorite NP-complete
problem (e.g., independent set, TSP, ...)
- Approximation algorithms for your favorite NP-complete
problem: see the
compendium of NP-hard optimization problems for inspiration.
- Your favorite on-line problem. Almost any problem has
associated on-line versions.