CSCI5610 Advanced Data Structures

Offered by Yufei Tao, Spring 2022. TA: Shiyuan Deng (sydeng@cse) Quick navigation links: [Lecture Notes][Exercises]

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.

Announcements

News 9 (27 Apr): Zoom link of tomorrow's exam is here. News 8 (11 Apr): The final exam will take place during 2-5pm, Apr 28. The scope covers Lectures 1-15, except Lecture 13. News 7 (7 Apr): Quiz 3 will take place in the lecture of 14 Apr. The scope covers the Fibonacci heap, the union find structure, and the Euler-tour structure. News 6 (18 Mar): Quiz 2 will take place in the lecture of 24 Mar (Thu). The scope covers cuckoo hashing and binomial heaps. The quiz will be 20 minutes long. News 5 (3 Mar): Midterm will take place in the lecture of Mar 9 (Wed). The scope covers everything in Lecture 1-8. The exam time is 40 minutes. News 4 (10 Feb): Midterm, Quiz 2, and Quiz 3 will take place in the lecture of Mar 9, 24, and Apr 7 Apr 14, respectively. News 3 (10 Feb): Quiz 1 will take place in the lecture of Feb 17. The scope covers Lects 2-3 and the kd-tree of Lect 4. The quiz will be 20 minutes long. News 2 (25 Jan): Our teaching will be Zoom-based until further notice. News 1 (8 Jan): Hello, all.

Time and Venues

Lectures Wed: 14:30pm - 15:15pm Room 405, William M W Mong Eng Bldg Zoom Thu: 10:30am - 12:15pm Room 402, Yasumoto Int'l Acad Park Zoom Click here for a campus map.

Grading Scheme

In-Class Quiz 1: 5% In-Class Quiz 2: 5% In-Class Quiz 3: 5% Midterm Exam: 35% Final Exam: 50% Style of Exams: The instructor will generate a list of exercises without solutions. In the midterm and final exams, about 35% of the marks will come from problems taken from that list. The rest 65% will be new problems. In each exam, you can bring a single-sided, A4-sized, note sheet on which you can print/write anything useful.

Lecture Notes

Lecture notes are available here: Download The notes are subject to revisions. Print wisely and avoid substantial re-printing. Lecture Schedule Lect 1 Overview and computation models Video Lect 2 BST and 2-3 tree. Video For more details of the BST, see this and that. For more details of the 2-3 tree, see this. Lect 3 [Intervals] Interval tree and segment tree Video (intv-tree) Lect 4 [Points] kd-tree, bootstrapping, priority search tree, and range tree Video (seg-tree, kd-tree) Video (bootstrapping) Video (pst, range-tree) See this for solving recurrences Lect 5 [Dynamization] Global rebuilding and charging augments Video (amortization) Video (charging argument) Lect 6 [Dynamization] Logarithmic method Video Lect 7 [Dynamization] Weight balancing Video 1 Video 2 Lect 8 [Temporal] Partial persistence Video 1 Video 2 Lect 9 [Hashing] Dynamic perfect hashing Video Read this for a short introduction to randomized algorithms. Lect 10 [Fundamentals] Binomial and Fibonacci heaps Video (binomial) Video (fobonacci 1) Video (fobonacci 2) Lect 11 [Fundamentals] Union-find structure Video 1 Video 2 Video 3 Lect 12 [Connectivity] Euler-tour structure Video Lect 13 [Tabulation] Range min queries Video 1 Video 2 Lect 14 [Integers] van Emde Boas Structure Video 1 Video 2 ======= (End of the final exam's scope) ===== Lect 15 [Word length] 2D orthogonal range counting Video Lect 16 [Strings] The suffix tree Video There will be no more lectures.

Exercises

As mentioned, some exam problems will come from the exercises below. List 1: Prob 1-4 in the exercise section of Lect 2 (see the lect notes). List 2: Prob 1-6 of Lect 3 and Prob 1-4 of Lect 4. List 3: Prob 7, 9, 10, 12 of Lect 4. List 4: Prob 1-2 of Lect 5, Prob 2 of Lect 6. List 5: Prob 1, 2, 4 of Lect 7. List 6: Prob 1-5 of Lect 8. List 7: Prob 1-4 of Lect 9. List 8: Prob 1, 2, 4-7 of Lect 10. List 9: Prob 1-4, 6, 7 of Lect 11. List 10: Prob 4-7 of Lect 12. List 11: Prob 1-2, Prob 6, 9, 10 of Lect 14. List 12: Prob 1-4 of Lect 15. There will be no more exercise lists.