CS5800 Advanced Data Structures & Algorithms

Jul - Nov 2024

about

Coordinates

• Where: CS15
• When: D slot - Mon (11 am), Tue (10 am), Wed (9 am), Thu (12 pm)

Instructor

• Yadu Vasudev
• SSB 207
• yadu@cse.iitm.ac.in

TAs

• Aditya (cs22s005@smail)
• Arun (cs23m017@smail)
• Nagashri (cs21d004@smail)
• Narayana (cs22s004@smail)
• Sampriti (cs18d200@smail)
• Subramanian (cs23m067@smail)
• Vasu (cs23m072@smail)

Important links

• Moodle
• Ed Discussions (for discussions, Q/A, announcements)
  Join using your smail/iitm ids via this link
• Anonymous course feedback

Course calendar

contents

About this course

This is a basic graduate-level course that introduces some advanced data structures, algorithm design techniques. There will be a lot of emphasis on reasoning about the data structures and algorithms that you design, and formally proving the correctness of constructions.

Prerequisites - A basic course in design and analysis of algorithms is necessary. The course will require you to design data structures and algorithms, and then mathematically prove their correctness. There will not be any programming component for this course, though you may be required to implement a few of the data structures and algorithms in CS6150 (Advanced Programming Lab).

Course contents

The following is a brief overview of the topics that will be covered in this course. The order of the topics covered may vary.

• Basic principles from algorithm design - asymptotic analysis, amortized analysis, randomization
• Data structures
  • Dictionary ADT - hash tables, skip lists, binary search trees
  • Priority Queue ADT - binary heaps, min-max heaps, mergeable heaps
  • Disjoint set ADT and applications
• Algorithm design
  • Greedy algorithms - scheduling, Huffman coding, MST
  • Dynamic programming - DP on strings, trees, DAGs, and graphs
  • Network flows and applications
• Intractability
  • Notion of poly-time reductions
  • NP-completeness and its consequences
  • Coping with intractability

---

Course resources

There are many textbooks and resources (both offline and online) that cover most of the material presented in the list above. We will not be following one textbook. Our main sources of reference will be the following textbooks.

• [E] - Algorithms by Erickson
• [CLRS] - Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, 3rd Edition
• [M] - Open Data Structures by Morin
• [DPV] - Algorithms by Dasgupta, Papadimitriou, and Vazirani

All these books contain a number of exercise problems for practice.

administrivia

Weekly schedule

There will be four lectures every week, some of which will be converted to tutorial/problem-solving sessions. I will be releasing problem sets regularly which will be discussed in the tutorial sessions. You can also use the course discussion forum to discuss these with your peers and the course staff.

---

Grading policy (tentative)

The course will be graded based on a number of tests. The following is a tentative grading policy. There will be no make-up for the tutorial tests.

• Open-book tutorial tests: Best 2 out of 3 - 2 * 15 = 30%
• Quizzes - 2 * 15 = 30%

• End-semester exam - 40%

Important dates (tentative)

We will stick to this schedule as much as possible, unless there are some unforeseen situations.

• Problem solving sessions: Aug 14, Sep 19, Oct 24
• Open-book tutorial tests: Aug 22, Sep 26, Nov 7
• Quizzes: Sep 2, Oct 10
• End-semester exam: Nov 20

---

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.

lectures