CSCI5610 Advanced Data Structures

Offered by Yufei TAO, Spring 2020.

TA: Pengguang Chen (

Quick navigation links:
[Lecture Notes][Exercises][Assignments/Quizzes/Exams]

Brief Description

This course introduces advanced techniques for designing data structures with strong theoretical guarantees. Topics to be covered include (i) generic methods such as logarithmic rebuilding, weight balancing, partial persistence, tabulation, doubling dimension, locality sensitive hashing, etc., and (ii) specific structures such as the interval tree, the priority search tree, cuckoo hashing, the Euler-tour tree, the van Emde Boas structure, the suffix tree, etc.


News 25 (5 May): Final exam released. Deadline May 17.
News 24 (27 Apr): Videos of Week 13 and Exercise list 13 released.
News 23 (24 Mar): Assignment 3 released. Deadline May 3.
News 22 (20 Apr): Videos of Week 12 and Exercise list 12 released.
News 21 (8 Apr): Videos of Week 11 and Exercise list 11 released.
News 20 (1 Apr): Videos of Week 10 and Exercise list 10 released.
News 19 (30 Mar): Assignment 2 released. Deadline Apr 5.
News 18 (25 Mar): Videos of Week 9 and Exercise list 9 released.
News 17 (18 Mar): Videos of Week 8 and Exercise list 8 released.
News 16 (13 Mar): Midterm released. Please scroll to the bottom to see it.
News 15 (10 Mar): Videos of Week 7 and Exercise list 7 released.
News 14 (3 Mar): Videos of Week 6 uploaded. Exercise list 6 released.
News 13 (25 Feb): Exercise list 5 released.
News 12 (25 Feb): Videos of Week 5 uploaded.
News 10 (18 Feb): Assignment 1 released. Deadline Feb 27.
News 9 (18 Feb): Exercise list 4 released.
News 8 (17 Feb): Videos of Week 4 uploaded.
News 7 (12 Feb): There will be no more classroom teaching until further notice. Videos will be uploaded each week.
News 6 (12 Feb): The grading scheme has changed due to the virus. Check it out in the section below.
News 5 (20 Jan): Exercise list 3 released.
News 4 (19 Jan): The classroom for our Tue's lectures has been changed to L3, Science Centre for the rest of the semester.
News 3 (14 Jan): Exercise list 2 released.
News 2 (7 Jan): Exercise list 1 released.
News 1 (3 Jan): Hello, all.

Time and Venues


Mon: 10:30am - 12:15pm
Room 712, William M W Mong Eng Bldg

Tue: 10:30pm - 11:15pm
Room 408, William M W Mong Eng Bldg
L3, Science Centre

Click here for a map of the campus.

Grading Scheme

In-Class Quiz 1: 5%
In-Class Quiz 2: 5%
In-Class Quiz 3: 5%
Midterm Exam: 35%
Final Exam: 50%

Update on Feb 12: Due to the coronavirus, each quiz/exam will be turned into a take-home assignment if classroom teaching has not resumed at the time of the quiz/exam.

Style of Exams:
During this course, the instructor will gradually generate a list of exercises without the solutions given. In the midterm and final exams, at least 35% of the marks will come from problems taken directly from that list. The rest 65%, however, will be from new problems.

In the midterm and the final exams, you will be allowed to bring in a single-sided, A4-sized, note sheet on which you can print/write anything you deem useful.

Lecture Notes

The instructor will write up the lecture notes and make them available here:


The above document will grow as the semester progresses. The following is the revision history:

(Apr 27): Lect 18 is complete.
(Apr 19): Lect 17 is complete.
(Apr 18): Lect 16 is complete.
(Apr 6): Lect 15 is complete.
(Apr 5): Lect 14 is complete.
(Mar 29): Lect 13 is complete.
(Mar 24): Revised Sec 11.2, 11.4.1.
(Mar 18): Revised Sec 10.3.
(Mar 17): Lect 12 is complete.
(Mar 16): Lect 11 is complete.
(Mar 10): Revised Sec 9.2.
(Mar 9): Lect 10 is complete.
(Mar 2): Lect 9 is complete.
(Feb 25): Lect 8 is complete.
(Feb 25): Lect 1 (computation models) is expanded.
(Feb 15): Lect 7 is complete.
(Feb 13): Lect 6 is complete.
(Jan 20): Lect 5 is complete.
(Jan 19): Added Sec 5.1, 5.2.
(Jan 18): Lect 4 is complete.
(Jan 11): Added Sec 4.1, 4.2.
(Jan 11): Lect 3 is complete.
(Jan 7): Lect 2 is now complete.
(Jan 6): Added Sec 2.2.1, 2.2.2.
(Jan 6): Added Sec 2.1.
(Jan 5): Added Lect 1.

Lecture Schedule

Lect 1 (week 1):
Overview and computation models

Lect 2 (week 1-2):
BST and 2-3 tree.
Remark: For a coverage of BSTs, see this and that. For a coverage of 2-3 trees, see this.

Lect 3 (week 2-3):
Interval tree and segment tree

Lect 4 (week 3):
kd-tree, bootstrapping, priority search tree, and range tree

Lect 5 (week 3-4):
Logarithmic rebuilding and global rebuilding
Video on global rebuilding

Lect 6 (week 4):
Weight balancing

Lect 7 (week 5):
Partial persistence
Video on potential
Video on persistence

Lect 8 (week 6):
Dynamic perfect hashing
Video on random graphs
Video on cuckoo hashing
(error in video: at 51:38, "4e^3/n" should be "4e^3/n^2")

Lect 9 (week 7):
Binomial and Fibonacci heaps
Video on binomial heaps
Video on Fibonacci heaps
(error in video: at 11:52, the tree is not an order-2 relaxed binomial tree -- it would be if the right child of the root had only 2 children, as opposed to 7)
(error at 13:15: same issue)

Lect 10 (week 8):
Union-find structure
Video on structure, algorithms, and O(log*(n)) bound
Video on O(α(n)) bound

Lect 11 (week 9):
Euler-tour structure
Video on the "plain" ETS
(error at 17:48 (corrected at 1:03:22): node G should be a child of node A)
(error at 14:45: in the 2-3 tree, the last two leaf nodes should contain "CHC" and "AGA", resp.)
(note about 54:54: ignore the line "CABACDCECFCHCGC")
Video on the "augmented" ETS

Lect 12 (week 9-10):
Dynamic connectivity
Video on edge leveling
Video on the algorithms

Lect 13 (week 10):
Range min queries

Lect 14 (week 11):
van Emde Boas Structure
Remark: see this for the substitution method

Lect 15 (week 11):
[Word length = Ω(log n)]
2D orthogonal range counting

Lect 16 (week 12):
[Nearest neighbor search]
Doubling dimension

Lect 17 (week 13):
[Nearest neighbor search]
Locality sensitive hashing

Lect 18 (week 13):
The suffix tree

There will be no more lectures.


As mentioned earlier, some problems in the midterm and final exams will be taken directly from the exercise lists below. No solutions to these exercises will be given. You are free to look for the solutions in any way (e.g., you may discuss them with your friends, the tutors, or even the instructor himself). Remember: during the exams, you will be allowed to consult only one piece of single-sided A4-sized paper. In other words, it is unrealisic to hope that you can write down all the solutions on that paper.

List 1: Prob 1-4 in the exercise section of Lect 2 (see the lect notes).
List 2: Prob 1-4 (in the exercises) of Lect 3, and Prob 1-4 of Lect 4.
List 3: Prob 7, 9, 10, 12 of Lect 4.
List 4: Prob 1-4 of Lect 5, and Prob 1-5 of Lect 6.
List 5: Prob 1-5 of Lect 7.
List 6: Prob 1-6 of Lect 8.
List 7: Prob 3-9 of Lect 9.
List 8: Prob 1-4, 6, 7 of Lect 10.
List 9: Prob 4-8 of Lect 11.
List 10: Prob 4-6 of Lect 12, Prob 1-6, 9, 10 of Lect 13.
List 11: Prob 1-4 of Lect 14, Prob 1-4 of Lect 15.
List 12: Prob 1-6 of Lect 16.
List 13: Prob 1-5 of Lect 17, and Prob 1-5 of Lect 18.
There will be no more exercise lists.

Assignments, Quizzes and Exams

Assignment 1 (replacing Quiz 1): Prob 4 of Lect 3, and Probs 10, 11 of Lect 4
Each student should email the instructor the solutions in a pdf typeset in Latex or Word by 11:59pm, Feb 27. No late submissions will be accepted.

Midterm exam: Prob 6 of Lect 7 (40%), Prob 1 of Lect 8 (30%), and Prob 5 of Lect 9 (30%)
  • Deadline: 11:59pm, Mar 22. No late submissions will be accepted.
  • Please typeset the solutions in Latex or Word.
  • You need to email a pdf file to the TA by the deadline (see the top of the page for the TA's email address).
  • The pdf should be named in the format of XXX.pdf, where "XXX" is your student id.
  • Please solve the problems by yourself.
Assignment 2 (replacing Quiz 2): Prob 5 of Lect 10 (40%), and Prob 7 of Lect 11 (60%)
  • Deadline: 11:59pm, Apr 5. No late submissions will be accepted.
  • Same requirements as in the last 4 bullets of Midterm.
Assignment 3 (replacing Quiz 3): Prob 3 of Lect 14 (40%), and Prob 6 of Lect 16 (60%)
  • Deadline: 11:59pm, May 3. No late submissions will be accepted.
  • Same requirements as in the last 4 bullets of Midterm.
Final exam: Download the paper here.
  • Deadline: 11:59pm, May 17. No late submissions will be accepted.
  • Same requirements as in the last 4 bullets of Midterm.