COMSE6998

Advanced Data Structures

Welcome to COMSE6998 Advanced Data Structures!

Time: Thursdays, 10:00-12:00. Location: 963 Schermerhorn Hall Extension.

The course will cover data structures in 4 main themes: Integers, Geometry, Graphs and Strings (information retrieval). We will spend time on both upper and lower bounds in various memory models.

Final projects

Here is the list of suggested final projects.

Final projects are due on Friday, May 10th.

Assignments

Submit to CourseWorks.

1. First homework, due February 21st (Thursday) at 6pm.
2. Second homework, due March 9th (Saturday) at 11:59pm.
3. Third homework, due March 28th (Thursday) at 6pm.
4. Fourth homework, due April 11th (Thursday) at 6pm.
5. Fifth homework, due May 4th (Saturday) at 6pm.

Lecture notes

1. Lecture 1.
2. Lecture 2.
3. Lecture 3.
4. Lecture 4.
5. Lecture 5.
6. Lecture 6.
7. Lecture 7.
8. Lecture 8.
9. Lecture 9.
10. Lecture 10.
11. Lecture 11.
12. Lecture 12.
13. Lecture 13.

Syllabus

1. Introduction (Motivation, DS and memory models, static/dynamic, performance guarantees).
2. Advanced binary search trees (BST model of computation, instance optimality, Splay Trees).
3. Dynamic optimality conjecture (geometric view, Arboral sets, Wilber’s LB, Tango Trees).
4. Predecessor search UBs on the RAM: van-Emde Boas Trees and Fusion Trees (stratified trees, Indirection).
5. Predecessor search LB via Round-Elimination (asymmetric communication complexity paradigm).
6. Near-Neighbor Search (locality-sensitive hashing, Dynamization via Segment Trees, LBs from lopsided set disjointness and metric embeddings, Cell-Sampling).
7. Orthogonal Range Counting (Layered Range Trees, Fractional Cascading, Dynamization via BB[a] Trees, delaying updates via Buffer Trees).
8. Tight LBs for dynamic Range Counting in 1D and 2D (Chronogram method, dynamic Cell Sampling).
9. Dictionaries and Hashing (Perfect Hashing, Cuckoo Hashing, dynamic dictionaries).
10. Succinct DS for Information Retrieval (Suffix arrays, compressed pattern matching, Rank UB/LB).
11. Dynamic undirected connectivity (Link-Cut Trees, Euler-Tour Trees, Distance Oracles).
12. Tight LB for undirected connectivity (Information-Transfer method). The “Multiphase” Conjecture.

References

• Data Structures and Network Algorithms (by R.Tarjan — covers BSTs, splay trees, link-cut trees).
• Open Data Structures (by P.Morin — covers BSTs, B-trees, hashing, and some integer data structures).
• Advanced data structures (by Peter Brass. Open access e-book available on the web).
• Advanced Data Strucutres course at MIT (by Erik Demaine)

Data Structure Simulator

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Logistics

There will be bi-weekly homeworks (~5-6 in total). Grading will be based on HW (35%), scribing 1 lecture (15%) and a final project (50%), which will entail exploring and extending a research paper of your choice (to be discussed and approved by the instructor and the TAs).

TA: Gleb Posobin (Room : 522 CSB. Office Hours: Tuesday 4−6pm)

Instructor: Omri Weinstein (523 CSB. Office Hours: By appointment).