CS4700 Advanced Data Structures

Jan - May 2026

Coordinates

Where: SSB 134
When: G slot - Mon (12 pm), Wed (5 pm), Thu (10 am), Fri (9 am)

Course staff

Instructor: Yadu Vasudev (yadu@cse.iitm.ac.in)
TAs:
- Aditya (cs25m007@smail, Office hours: Tue 4.45 - 5.45 PM, CS 32)
- Alan (cs24m006@smail, Office hours: Thu 2 - 3 PM, CS 36)
- Chetan (cs25s022@smail, Office hours: Fri 2 - 3 PM, SSB 324)
- Neha (cs21d408@smail, Office hours: Tue 5 - 6 PM, SSB 322)
- Shivam (cs25m048@smail Office hours: Thu 5 - 6 PM, CS 32)

Important links

Moodle
Ed Discussions
Join using your smail/iitm ids via this link
Anonymous course feedback

Course calendar

About this course

This is a second course in data structures, and builds on the material covered in CS2700 (Programming and data structures). We will look at the design of various data structures for dictionaries, priority queues, dynamic graphs, and range queries . There will be an emphasis on understanding the design principles for various data structures, and a rigorous analysis of their complexity. At the end of the course, the student is expected to know the design and analysis of a variety of advanced data structures, and be able to design new data structures for specific applications.

Prerequisites - Programming and data structures (CS2700) or an equivalent course is a prerequisite for this course. A course in algorithm design and analysis would be useful, but not necessary. Programming experience is not necessary, but is recommended.

Course contents

The following are the broad topics that will be covered in this course.

Recall of algorithm analysis - Asymptotic notation, amortized analysis, basics of probablistic analysis.
Dictionaries - Hash tables, skip lists, balanced search trees, tries
Priority queues - Recall of binary heaps, min-max heaps, mergable heaps - binomial and Fibonacci heaps
Geometric data structures - Range queries and searching, kd-trees, segment trees
Dynamic graphs - Link-cut trees, Euler-tour trees, heavy-light decomposition, dynamic connectivity
Persistent data structures - Partial and fully persistent data structures for lists, trees, heaps

Course resources

There is no single textbook for the course. The following two books contain some of the material that will be covered in the course, especially the first half.

Open Data Structures by Pat Morin
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein

Apart from this, there are a lot of resources available online. We may refer to them occasionally.

Weekly schedule

There are four lecture slots per week. We will convert some of them into tutorial sessions and short exams. The tentative schedule is given below. You are welcome to use the course discussion forum to clarify doubts with the instructor and the TAs.

Grading policy (tentative)

Assignments: 2*10 = 20%
Short exams: 2*10 = 20%
Quizzes: 2*15 = 30%
End-semester exam = 30%

Important dates (tentative)

Assignment (deadlines): Mar 9, Apr 27
Short exams: Feb 11, Apr 15
Quizzes (according to institute calendar): Feb 25, Mar 27
End-semester (according to institute calendar): May 14

Communication

Please sign up on the course discussion forum here. This will be the first point of contact for any issues related to the course. For general questions related to the course (any comments/doubts), please create a thread in the correct category and add your question/comment there. You are encouraged to reply and clear the doubts of your friends. To encourage this interaction, the forum supports anonymous posts and answers. Please be courteous to others when you are posting anonymously.

Date	Lecture	References	Misc
Lecture #1 Mon 19/01	Introduction to the course • Admin and logistic details		Sign up on Ed Discussions
Lecture #2 Wed 21/01	Dynamic arrays - Insert operations and amortized analysis	Section 17.4.1 - CLRS Section 1.1 - Course notes
Lecture #3 Thu 22/01	Dynamic arrays with insertions and deletions - amortized analysis	Section 17.4.2 - CLRS Section 1.1 - Course notes
Lecture #4 Fri 23/01	Dictionary ADT - hash tables • Random hash functions and their properties	Section 3.1.1 - Course notes
Lecture #5 Wed 28/01	Universal hashing - properties, examples	Section 3.1.2, 3.1.3 - Course notes	Problem set 1 released on Ed
Lecture #6 Thu 29/01	Universal hashing - examples • Static dictionaries - FKS hashing	Section 3.1.3, 3.1.4 - Course notes
Lecture #7 Fri 30/01	Static dictionaries - FKS hashing • Bloom filters • Open addressing with linear probing	Section 3.1.4, 3.1.5 - Course notes
Lecture #8 Mon 02/02	Open addressing with linear probing - analysis • Skip lists - searches, insertions and deletions	Section 3.1.5, 3.2 - Course notes Section 5.2, 4.1 - Morin
Lecture #9 Wed 04/02	Skip lists - implementation and analysis	Section 3.2 - Course notes Section 4.4 - Morin
Lecture #10 Thu 05/02	Binary search trees - representation, algorithms, notion of balanced trees • AVL trees	Section 3.3.1 - Course notes	Problem set 2 released on Ed
Tutorial #1 Mon 09/02	Based on Problem sets 1 and 2
Test #1 Wed 11/02	Based on Lectures 1 to 9 (Problem sets 1 and 2)
Lecture #11 Thu 12/02	AVL trees - insertion, examples, implementation details	Section 3.3.2 - Course notes
Lecture #12 Fri 13/02	AVL trees - deletions, examples • Scapegoat trees	Section 3.3.2, 3.3.3 - Course notes
Lecture #13 Mon 16/02	Scapegoat trees - properties and analysis • Optimal BSTs and introduction to splay trees	Section 3.3.3 - Course notes
Lecture #14 Wed 18/02	Splay tree operations - examples and properties	Section 3.3.5 - Course notes	Splay tree visualization, Problem set 3 released on Ed
Lecture #15 Thu 19/02	Splay trees - amortized analysis	Section 3.3.5 - Course notes
Lecture #16 Fri 20/02	Splay tree theorems and conjectures • Top-down splaying	Section 3.3.5 - Course notes
Tutorial #2 Mon 23/02	Based on Problem set 3
Quiz #1 Wed 25/02	Based on Lectures 1 to 13 (Problem sets 1, 2, and 3)
Lecture #17 Thu 26/02	Priority queues - binary heaps and their properties	Section 4.1 - Course notes
Lecture #18 Fri 27/02	Binary min-max heaps - operations, analysis, and implementation details	Section 4.2 - Course notes
Lecture #19 Mon 02/03	Binary min-max heaps (contd.) • Randomized mergeable heaps	Section 4.3.1 - Course notes
Lecture #20 Thu 05/03	Leftist heaps - properties, operations, and analysis • Skew heaps [notes]	Section 4.3.1, 4.3.2 - Course notes
Lecture #21 Fri 06/03	Skew heaps - properties, operations, and analysis • Binomial heaps	Section 4.3.2, 4.3.3 - Course notes
Lecture #22 Mon 09/03	Binomial heaps - properties, operations, and analysis	Section 4.3.3 - Course notes
Lecture #23 Wed 11/03	Lazy binomial heaps and Fibonacci heaps - cascading cuts	Section 4.3.3, 4.3.4 - Course notes
Lecture #24 Thu 12/03	Cascading cuts in Fibonacci heaps and amortized analysis	Section 4.3.4 - Course notes
Lecture #25 Fri 13/03	Range minimum queries - lookup tables, range trees, indirection	Erickson's notes
Lecture #26 Mon 16/03	Range minimum queries - Cartesian trees and reduction to LCA	Erickson's notes
Lecture #27 Wed 18/03	LCA back to RMQ - Euler tour, depth array, and the four Russians • Level ancestors in trees	Erickson's notes Bender and Farach-Colton's paper	Problem set 4 released on Ed
Lecture #28 Thu 19/03	Level ancestors in trees - jump pointers and ladder decompositions	Bender and Farach-Colton's paper
Lecture #29 Fri 20/03	Level ancestors in trees - macro trees, micro trees, and the four Russians	Bender and Farach-Colton's paper	Problem set 4a released on Ed
Tutorial #3 Mon 23/03	Based on Problem sets 4 and 4a
Lecture #30 Wed 25/03	Range trees and orthogonal range searching	Mount's notes
Lecture #31 Thu 26/03	kd trees - range searching and nearest neighbors	Mount's notes
Quiz #2 Fri 27/03	Based on Lectures 14 to 29 (Problem sets 4 and 4a)
Lecture #32 Mon 30/03	Interval trees and their applications	Section 10.1 here
Lecture #33 Wed 01/04	Segment trees and their applications	Section 10.3 here
Lecture #34 Thu 02/04	Fractional cascading and range trees	Section 5.6 here
Lecture #35 Mon 06/04	Fractional cascading (contd.) • Data structures for strings	Section 4.1 here
Lecture #36 Wed 08/04	Data structures for strings - tries and suffix trees	Section 2 of Demaine's notes
Lecture #37 Thu 09/04	Suffix trees - applications • Suffix arrays	Section 3 of Demaine's notes
Lecture #38 Fri 10/04	Suffix arrays and LCP arrays- applications • Connection between suffix arrays LCP arrays and suffix trees	Section 4 of Demain's notes Section 3 of Venkatesh Raman's notes
Tutorial #4 Mon 13/04	Based on Problem set 5 (see on Ed)
Test #2 Wed 15/04	Based on Lectures 30 to 38 (Problem set 5)
Lecture #39 Thu 16/04	Suffix arrays in linear time - DC3 algorithm	Section 3 and 4 here, source code in Appendix A Section 5 of Demaine's notes
Lecture #40 Fri 17/04	LCP arrays using DC3 algorithm • Succinct data structures	Section 3 and 4 here, source code in Appendix A
Lecture #41 Mon 20/04	Succinct data structures - binary trees and bit vectors • Succinct rank query	Sections 2 and 3 of Demaine's notes
Lecture #42 Wed 22/04	Succinct data structures - select query • Data structures for dynamic graphs	Sections 2 and 3 of Demaine's notes
Lecture #43 Fri 24/04	Link-cut trees - preferred path decomposition, examples and properties	Section 3 of Demaine's notes Parts of Section 5.2 here (the terminology is different from what we used in class, but the ideas are the same)
Lecture #44 Mon 27/04	Link-cut trees - operations and analysis	Section 3 of Demaine's notes Parts of Section 5.2 here (the terminology is different from what we used in class, but the ideas are the same)
Lecture #45 Wed 29/04	Link-cut trees • Wrap-up of the course	Section 4 of Demaine's notes Parts of Section 5.2 here (the terminology is different from what we used in class, but the ideas are the same)