$\newcommand{\R}{\mathbb{R}}\DeclareMathOperator{\E}{\mathbf{E}}\DeclareMathOperator{\deg}{deg}\newcommand{\N}{\mathbb{N}}$

Instructor: Pat Morin, 5177 HP, morin@scs.carleton.ca

• New: Assignment 1 is now available. It is due on February 13, before class.

Jump to Lecture Topics

About the Course

This is the home page for the graduate course Advanced Data Structures (formerly Topics in Data Structures) taught by Pat Morin in the School of Computer Science at Carleton University.

This course is about simple and easy to understand methods of data structure design and analysis that lead to efficient data structures for a variety of problems. The examples we use are selected because of their elegance and simplicity.

The course consists of three assignments, a final project, and a contribution to public knowledge. The final project is a theory or implementation project that students should choose and discuss with the instructor early in the semester. The contribution to public knowledge is a contribution to Wikipedia that adds information abouft one of the topics discussed in class or found while researching for the project.

Students in this graduate course are expected to have a background in algorithms and data structures. Assignments will require that students solve algorithmic and data structure problems and clearly explain their solutions in written english.

Learning Modality

This is an in-person only class. For your convenience, some videos of lectures from previous years are provided below, but this will not be the case for all topics covered in the course.

Important Dates

Due dates for assignments, contribution to knowledge, and the final project will be posted here.

Assignments

Assignments will be posted here as they become available.

• New: Assignment 1 is now available. It is due on February 13, before class. Here is LaTeX source for the assignment.

Please note the following rules and requirements about assignments:

• Late assignments will not be accepted
• Each assignments should be submitted to me as a single PDF file by email
• I will not respond to emails sent shortly before or after assignment deadlines asking for exceptions to the preceding two rules.
• You can type your solutions, or write them by hand and scan them (for example, using a scan app on your phone or using a real scanner).
• Solutions written-up in LaTeX are preferred, but not strictly required. In case you want to learn LaTeX, here is a tutorial. Learning LaTeX is a useful exercise, since many programs (including Microsoft Word) now use LaTeX for typesetting formulas.

Grading Scheme

Class participation	10%
Assignment 1	15%
Assignment 2	15%
Assignment 3	15%
Contribution to public knowledge	15%
Final project	30%
Total	100%

Accommodation Statement

Carleton University is committed to providing access to the educational experience in order to promote academic accessibility for all individuals. Here is information on how to apply for academic accommodation.

Lecture topics

The following schedule is from the Fall 2021 offering of COMP5408. Dates, videos, and topics will be updated as the course progresses.

• Lectures 1 & 2 (treaps): also see these alternative notes on treaps
  • Sep 9: Records, random binary search trees, quicksort chalkboard photo
    
    
  • Sep 14: Treaps
    
• Lecture 3 (iterated search and fractional cascading)
  • Sep 16: Fractional cascading
    
• Lectures 4 (persistence)
  • Sep 21: Solving next-element search (point location) using persistence
    
• Lectures 5 & 6 (entropy)
  • Sep 23: Entropy, probability splitting, and doubly-exponential series
    
  • Sep 28: Working set structure and MTF compression
    
• Lecture 7 (queaps)
  • Sep 30: Queaps
    

• Lecture 8 (van Emde Boas trees)
  • Oct 5: van Emde Boas trees
    
• Lecture 9 (x-fast and y-fast tries)
  • Oct 7: Binary tries, X-fast tries and y-fast tries
    
• Lecture 10 (Lowest-common ancestor data structures)
  • Oct 12: Lowest common ancestor data structures
    
• Lecture 11 (Level-ancestor data structures)
  • Oct 14: Level ancestor data structures
    
• Lecture 12 (dynamic partial sums and cell-probe lower-bounds)
  • Oct 19: Dynamic partial sums
    
• Lecture 13, 14, and 15 (data structures for strings)
  • Oct 21: C-strings, P-strings, ternary tries, tries, Patricia tries
    
    
  • Nov 4: Suffix arrays and suffix trees
  • sa.py
    
  • Nov 9: LCP arrays
    
• Lecture 16 (universal hashing and dynamic perfect hashing)
  • Nov 11: universal hashing and perfect hashing
    
• Lecture 17 (cuckoo hashing and retrieval-only maps analyzed using encoding arguments)
  • Nov 16: cuckoo hashing and retrieval-only dictionaries
    
• Lecture 18 (the planar separator theorem and distance oracles)
  • Nov 18: distance labelling, planar separators, and distance oracles
    
    -Lectures 19 & 20 (splay trees)
  • Nov 23: Splay trees I
    
  • Nov 25: Splay trees II
    
• Lecture 21 (external memory)
  • Nov 30: External memory and cache-oblivious B-trees
    
• Lectures 22 & 23 tripod decomposition of planar graphs
  • Dec 7: The tripod decomposition lemma
    
  • Dec 9: Tripod decompositions in $O(n\log n)$ time