CS 840
Project
General expectations of a project (It
is quite reasonable to
deviate from these, but check with me first):
- Read paper in an
area related to this course. You may start with a fairly recent paper
and realize that in order to fully understand that paper you have to
read a couple of others on which it builds.
- Understand the
results and approaches
- Write a brief
summary (less than 1 page) of the key notions of the paper and what you
might hope to extend. Due by March 9.
- At this stage you
will probably want to find a couple of other papers on the topic, to
see what else has been done.
- Apply, extend or
implement these results:
- Application
could be to some appropriate problem, perhaps one in your own research
area.
- An attempt to
extend the results may or may not be successful, in either case you
should explain the avenues taken and why they were successful or
unsuccessful
- In some cases
implementations may provide the best insight
- Present your
preliminary findings in class (in the last 3 weeks of term)
- A PC running
Windows and data projector is available during these presentation times. If you would like to
present using either PowerPoint or Acrobat, you may use this facility.
- The final written
report should summarize the papers read and your findings in a 5 to 10
pages (due April 19)
Most projects are expected to be the
work of one student and
not done for other academic credit. It is possible to deviate from
this, but
only if all parties involved are appropriately informed and agree. E.g.
a group
of 2 doing a project together is probably fine, just speak to me
(expectations
will be greater than for one student). It is possible that projects in
two
courses taken concurrently could be closely related, if so both
instructors
must approve (and presumably raise expectations).
Starting
points:
See references on course web page, or
try “recent”
conferences and journals or talk to me:
(Only a modest fraction of the papers
in any conference or
journal are relevant to this course. Conferences have a 2 to 3 year
lead on
journals, so try the following conferences)
- ACM-SIAM Symposium
on Discrete Algorithms (SODA)
- European Symposium
on Algorithms (ESA), Proc. in Springer LNCS series
- Workshop on
Algorithms and Data Structures (WADS), Proc. in Springer LNCS series
- Scandinavian
Workshop on Algorithms and Complexity (SWAT), Proc. in Springer LNCS
series
- International
Symposium on Algorithms and Computation (ISAAC), Proc. in Springer LNCS
series
- ACM Symposium on
Theory of Computing (STOC)
- IEEE Symposium on
Foundations of Computer Science (FOCS)
Conferences
and journals also
vary in “average quality”. SODA is very strong by both metrics. STOC
and FOCS
are very high quality but also rather broad in scope.
SODA
is probably the best source. Here are several papers from SODA 2010
Patrascu
and Viola: Cell-Probe Lower Bounds for Succinct Partial Sums
Yi and Zhang:
On the Cell Probe Complexity of Dynamic Membership
Sadakane
and Navarro: Fully-Functional Succinct Trees
Yuan and Atallah: Data Structures for Range Minimum Queries in mUltidimensional ArraysAndoni eta l: Lower bounds for Edit Distance and Product Metrics via Poincare-Type InequalitiesFraigniaud and Korman:Compact Ancestry Labeling Schemes for XML Trees
Goodrich: Randomized Shellsort: A Simple Oblivious Sorting AlgorithmSeidel: Data-Specific Analysis of String Sorting Bille and Thorup: Regular Expression Matching with Multi-Strings and Intervals Agarwal and Sharathkumar: Streaming Algorithms for Extent Problems in High DimensionsSiddhartha and Tarjan: Deletion Without Rebalancing in Balanced Binary Trees on the same issue is
Sedgewick: Left Leaning Red Black Treesand some others
Demaine et al: Dynamic Optimality, Almost associated with this is
Bose et al: Zipper TreesAnderson et al: Thresholds and Optimal Binary Comparison Search Trees