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:
    • Alan (cs24m006@smail)
    • Neha (cs21d408@smail)

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.

  1. Open Data Structures by Pat Morin
  2. 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
No matching items