Instructor: Pat Morin, 5177 HP, morin@scs.carleton.ca
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
Content for this course is delivered simultaneously in class and online via Zoom. Students who want to attend inperson can do so. Others can join via Zoom. The Zoom recordings will also be made available for offline viewing.
Notice: Today, Thursday December 2nd, there will be no online or inperson lecture.
Students joining over Zoom should use this link. This meeting has a waiting room. Before joining please make sure that you have a recognizable screen name, otherwise I may not let you in.
Important Dates
Due dates for assignments, contribution to knowledge, and the final project will be posted here.
 Assignment 2 is due on Tuesday November 9, before class. Please email me a single PDF file containing your solutions.
 Assignment 1 is due on Tuesday October 12, before class.
 Classes on Nov 23, 25, 30, and Dec 3 will be online only.
Assignments

Assignment 2 is now available.

Assignment 1 is now available. This assignment covers material from lectures 1–6. I recommend that you read the assignment as soon as possible so that you can keep the questions in mind when the relevant material is discussed in class.
More assignments will be posted here as they become available.
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 writtenup 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.
Academic Integrity (Newâ€”Please Read)
As of 2020, there are new penalties in place for academic integrity violations. These will be issued by the Associate Dean (Undergraduate Affairs) of Science to students who copy, in whole or in part, work they submit for assignments.
 First offence: F in the course
 Second offence: Oneyear suspension from program
 Third offence: Expulsion from the University
These are standard penalties. Moresevere penalties will be applied in cases of egregious offences. Failure to inform yourself of the expectations regarding academic integrity is not a valid excuse for violations of the policy. When in doubt, ASK your instructor or TA.
More information can be found at the ODS website
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 Winter 2014 offering of COMP5408. Dates, videos, and topics will be updated as the course progresses. In case I'm slow uploading or a link here is broken, you can find these videos on my YouTube channel.
 Lectures 1 & 2 (treaps): also see these alternative notes on treaps
 Sep 9: Records, random binary search trees, quicksort chalkboard photo
 Sep 14: Treaps
 Sep 9: Records, random binary search trees, quicksort chalkboard photo
 Lecture 3 (iterated search and fractional cascading)
 Sep 16: Fractional cascading
 Sep 16: Fractional cascading
 Lectures 4 (persistence)
 Sep 21: Solving nextelement search (point location) using persistence
 Sep 21: Solving nextelement search (point location) using persistence
 Lectures 5 & 6 (entropy)
 Sep 23: Entropy, probability splitting, and doublyexponential series
 Sep 28: Working set structure and MTF compression
 Sep 23: Entropy, probability splitting, and doublyexponential series
 Lecture 7 (queaps)
 Sep 30: Queaps
 Sep 30: Queaps
 Lecture 8 (van Emde Boas trees)
 Oct 5: van Emde Boas trees
 Oct 5: van Emde Boas trees
 Lecture 9 (xfast and yfast tries)
 Oct 7: Binary tries, Xfast tries and yfast tries
 Oct 7: Binary tries, Xfast tries and yfast tries
 Lecture 10 (Lowestcommon ancestor data structures)
 Oct 12: Lowest common ancestor data structures
 Oct 12: Lowest common ancestor data structures
 Lecture 11 (Levelancestor data structures)
 Oct 14: Level ancestor data structures
 Oct 14: Level ancestor data structures
 Lecture 12 (dynamic partial sums and cellprobe lowerbounds)
 Oct 19: Dynamic partial sums
 Oct 19: Dynamic partial sums
 Lecture 13, 14, and 15 (data structures for strings)
 Oct 21: Cstrings, Pstrings, ternary tries, tries, Patricia tries
 Nov 2: Assignment 1 Review
 Nov 4: Suffix arrays and suffix trees
 sa.py
 Nov 9: LCP arrays
 Oct 21: Cstrings, Pstrings, ternary tries, tries, Patricia tries
 Lecture 16 (universal hashing and dynamic perfect hashing)
 Nov 11: universal hashing and perfect hashing
 Nov 11: universal hashing and perfect hashing
 Lecture 17 (cuckoo hashing and retrievalonly maps analyzed using encoding arguments)
 Nov 16: cuckoo hashing and retrievalonly dictionaries
 Nov 16: cuckoo hashing and retrievalonly 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
 Nov 18: distance labelling, planar separators, and distance oracles
 Lecture 21 (external memory)
 Nov 30: External memory and cacheoblivious Btrees
 Nov 30: External memory and cacheoblivious Btrees
 Lectures 22 & 23 tripod decomposition of planar graphs
 Dec 7: The tripod decomposition lemma
 Dec 9: Tripod decompositions in $O(n\log n)$ time
 Dec 7: The tripod decomposition lemma