Website for the advanced data structures course at Columbia university
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
README.md
_config.yml
advancedDS_hw1.pdf
advancedDS_lec1.pdf
advancedDS_lec2.pdf

README.md

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.

Assignments

Submit to CourseWorks.

  1. First homework, due February 21st (Thursday) at 6pm.

Lecture notes

  1. Lecture 1.
  2. Lecture 2.

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).