CS 598 TMC, Fall 2023

Presentation and Project Guidelines

Presentation

Date: Nov 29 or Dec 1 or Dec 6 (i.e., during the last 3 classes)

Present one paper (15 minutes if working alone, or 20 minutes if working in a group of 2, or 25 minutes if in a group of 3 -- every member of the group should participate). The format is similar to a conference talk. Spend sufficient time on the introduction (problem statement, background and survey of previous or related results, statement of the new results). Then describe the main ideas behind the new data structures in the paper. You may not have time to cover all results in the paper, or go into all the technical details; pick the part(s) you find most interesting or enjoyable for the audience. Point out connection (if any) with techniques we have seen from class. Close with open questions (from the paper, or ones you think of yourself).

Project

Deadline: Dec 13 Wednesday 5pm

Write a report (about 10 pages (single-column, single-spaced) if working alone, or about 15 pages if working in a group of 2, or about 20 pages if in a group of 3), comparing 2 or more papers on a common topic about data structures. One of the papers may be the paper you used for your presentation.

Begin with an introduction of the problem and a general survey. Then describe the new data structures in your selected papers. You do not need to explain all the technical details (especially if they are complicated). Present your own (hopefully easier-to-understand) interpretation, in your own words (do not copy or just paraphrase the descriptions from the papers). Point out similarities and differences between the papers, and their strengths and weaknesses. Point out connections (if any) with techniques from class. Close with open questions, as well as your thoughts on future work and any ideas you may have regarding possible further improvements.

Alternative option: do original research! (The format of the report would be more flexible, depending on what new results you get. If you do not succeed in solving an open problem, you may fall back to writing a general survey, and/or describe your failed attempts, partial results, etc. Feel free to discuss with me...)

Another alternative option: implement some data structures for a problem, and report on your experimental results/comparisons.

(Short) "Proposal"

Deadline: before Nov 13

Let me know what topic and papers you choose for the presentation and project before Nov 13 at the latest, so that I may provide suggestions and confirm that your choice is within scope for this course (and does not substantially overlap with other students'). A short email to me ("tmc"), in one or two paragraphs, should suffice. (And if you decide to change your choice after Nov 13, just let me know.)

Tips

• Browse through papers by conferences or by authors on DBLP
• Major theory/algorithms conferences: SODA, FOCS, STOC, ICALP, ESA, WADS, SOSA, ALENEX (for experimental papers), etc.
• Search for papers with Google Scholar
• UIUC library's proxy bookmarklet should give you access to conference and journal articles
• Note: some papers have multiple versions, in conferences, in journals, and/or on the arXiv; the journal version (if available) is usually the most up-to-date
• If you are the kind of person who wants to fully understand every low-level detail, don't pick papers that are complicated or rely on long chains of prior techniques. On the other hand, for papers that are technically more complicated, the expectation is in gaining a high-level conceptual understanding of the key ideas.
• Avoid picking well-studied topics that already have existing surveys, unless you are covering the most recent results (and similarly for experimental projects, avoid problems that already have extensive implementations/experimental studies).

Some Examples

Below is a random list of examples. You are encouraged to find a topic/papers on your own. Feel free to ask me for advice (during my office hours or by appointment).

• RMQ for higher-dimensional arrays: Brodal et al. (ESA'14), Yuan and Atallah (SODA'10) (TAKEN)
• Monotone list labeling and/or order maintenance (related to HW1Q3): e.g., Bender, Conway, Farach-Colton, Komlos, Kuszmaul, and Wein (FOCS'22), Bender, Cole, Demaine, Farach-Colton, and Zito (ESA'02), and many more
• In-place or "implicit" data structures (related to HW1Q4): Munro ('86), Granceschini and Grossi (WADS'03)
• Other variants of Fibonacci heaps: e.g., hollow heaps by Hansen, Kaplan, Tarjan, and Zwick (ICALP'15), slim and smooth heaps by Sinnamon and Tarjan (SODA'23), ... (TAKEN)
• Soft heaps: Chazelle ('00), simplified by Kaplan, Tarjan, and Zwick (SODA'09)
• Union-find with deletions: Kaplan, Shafrir, and Tarjan (SODA'02)
• Resizable arrays: Tarjan and Zwick (SOSA'23), Brodnik, Carlsson, Demaine, Munro, and Sedgewick (WADS'99) (TAKEN)
• Dynamic independent set of intervals: Gawrychowski and Pokorski (ICALP'22)
• Dynamic rank/select: e.g., Patrascu and Thorup (FOCS'14), and earlier, Dietz (WADS'99)
• Deterministic hashing/dictionaries: e.g., Ruzic (SODA'07)
• Tabulation hashing and variants: Patrascu and Thorup (STOC'11), other papers by Thorup, ..., Bercea, Beretta, Klausen, Tejs Houen, Thorup ('23)
• Hashing with better probabilistic guarantees: Kuszmaul (FOCS'22)
• Succinct hashing/dictionaries: e.g., Raman and Rao (ICALP'03), Bender, Farach-Colton, Kuszmaul, Kuszmaul, and Liu (STOC'22)
• Dynamic orthogonal range searching: e.g., my paper with Tsakalidis (SoCG'17)
• Dynamic planar point location: e.g., my paper with Nekrich (FOCS'15), or Nekrich (STOC'21)
• Point location in 3D: e.g., C., Nekrich, Rahul, and Tsakalidis (ICALP'18), de Berg, van Kreveld, and Snoeyink ('95), Preparata and Tamassia ('92)
• LSH without errors: Pagh (SODA'17), Ahle (FOCS'17), Wei (SODA'19)
• Dynamic graph connectivity without amortization: Kapron, King, and Mountjoy (SODA'13), or Chuzhoy, Gao, Li, Nanongkai, Peng, and Saranurak (FOCS'20, complicated!)
• Dynamic maximal matching or approximate maximum matching: e.g., Baswana, Gupta, and Sen (FOCS'11), Solomon (FOCS'16), Bhattacharya, Kiss, Saranurak, and Wajc (SODA'23), ...
• Dynamic graph coloring: Bhattacharya, Chakrabarty, Henzinger, and Nanongkai (SODA'18), ...
• Dynamic real-weighted all-pairs shortest paths: e.g., Demetrescu and Italiano (STOC'03), or more recently, Probst Gutenberg and Wulff-Nielsen (SODA'20) and Karczmarz and Sankowski (ICALP'23) (TAKEN)
• Dynamic approximate all-pairs shortest paths: e.g., van den Brand and Nanongkai (FOCS'19), ...
• Other dynamic graph algorithms... (e.g., see Dagstuhl workshop (2022) or Simons workshop (2023))
• Distance oracles for planar graphs: e.g., Mozes and Sommer (SODA'12)
• Text indexing: e.g., Navarro and Nekrich (SODA'12), Munro, Navarro, and Nekrich (CPM'20), ...
• Dynamic strings: Gawrychowski, Karczmarz, Kociumaka, Lacki, and Sankowski (SODA'18), or earlier papers by Mehlhorn, Sundar, and Uhrig (1997) and Alstrup, Brodal, and Rauhe (SODA'00) (TAKEN)
• Dynamic longest common substring: Gawrychowski, Mozes, and Weimann (ICALP'20)
• Dynamic suffix array: Kempe and Kociumaka (STOC'22, long!)
• Other string data structure problems... (e.g., see recent papers in the conference CPM)
• Many problems about external-memory data structures...