CS5800 Advanced Data Structures & Algorithms

Jul - Nov 2024

Coordinates

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

Instructor

TAs

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

Course calendar

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.

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.

Date Lecture References Misc
Lecture #1
Mon 29/07 		Introduction to the course • Admin and logistics • ADTs and data structures - examples
Sign up on Ed discussions
Lecture #2
Tue 30/07 		Dynamic arrays - linked lists vs arrays • Amortized analysis - aggregate method
  • Section 17.4.1 - CLRS
 PS0 released
Lecture #3
Wed 31/07 		Dynamic arrays • Amortized analysis - accounting and potential methods
  • Section 17.4.1 - CLRS
Lecture #4
Thu 01/08 		Dynamic arrays with insertions and deletions - amortized analysis using the potential method
  • Section 17.4.2 - CLRS
Lecture #5
Mon 05/08 		Basic discrete probability - sample spaces, events, independence, union bound
Lecture #6
Tue 06/08 		Random variables and their properties - examples • Quicksort
Lecture #7
Wed 07/08 		Quicksort - correctness, recurrence for running time, randomization
  • Sections 7.2, 7.3 - CLRS
Lecture #8
Thu 08/08 		Analysis of randomized quicksort
  • Section 7.4 - CLRS
 PS1 released
Lecture #9
Mon 12/08 		Dictionaries and Hash tables - trade-offs between running-time and size, random hash functions and collisions
  • Section 11.2 - CLRS
Lecture #10
Tue 13/08 		Random hash functions and collisions - the birthday problem
  • Section 5.4.1 - CLRS
Tutorial #1
Wed 14/08 		Based on Problem sets 0 and 1 PS2 released
Lecture #11
Mon 19/08 		Universal hash families I - construction and analysis
  • Section 11.3.3 - CLRS
Lecture #12
Tue 20/08 		Universal hash families II - more constructions and analysis
Lecture #13
Wed 21/08 		Perfect hashing - static dictionaries and FKS hashing
  • Section 11.5 - CLRS
Test #1
Thu 22/08 		Based on Lectures 1 - 8 (Problem sets 0, 1, 2)
Lecture #14
Mon 26/08 		Hashing using open addressing - linear probing
PS3 released
Lecture #15
Tue 27/08 		Hashing using open addressing - linear probing (contd.)
Lecture #16
Wed 28/08 		Skip lists - definition, examples, implementation details
  • Sections 4.1, 4.2 - Morin
Tutorial #2
Thu 29/08 		Based on Problem set 3
Quiz #1
Mon 02/09 		Based on Lectures 1 -13 (Problem sets 0, 1, 2, 3)
Lecture #17
Tue 03/09 		Skip lists - analysis • Binary search trees - examples
Lecture #18
Wed 04/09 		Binary search trees - search, insert and delete operations, examples, time complexity
Lecture #19
Thu 05/09 		Balanced BSTs - definitions, examples • Self-adjusting BSTs - handling searches and deletions
PS4 released
Lecture #20
Mon 09/09 		Scapegoat trees - handling searches and insertions, examples, analysis
Lecture #21
Tue 10/09 		Scapegoat trees - analysis (contd.) • Priority queues - binary minheaps, properties and examples
  • Section 6.1 - CLRS
Lecture #22
Wed 11/09 		Binary heaps - examples, properties, algorithms and complexity • Min-max heaps - examples and properties
  • Section 6.1 - 6.3 - CLRS
Lecture #23
Thu 12/09 		Min-max heaps - examples, implementation details, time complexity • Binomial heaps - properties, examples
PS5 released
Lecture #24
Mon 16/09 		Binomial heaps - implementing insert and extractmin using merges, bounds on running-time • Lazier binomial heaps - faster insertions at the cost of extractmin
Lecture #25
Wed 18/09 		Lazy binomial heaps - amortized complexity of extractmin • Fibonacci heaps - examples, decreasing keys using cascading cuts
  • Sections 19.2, 19.3 - CLRS
Tutorial #3
Thu 19/09 		Based on Problem sets 4, 5
Lecture #26
Mon 23/09 		Fibonacci heaps - cascading cuts, examples and analysis
  • Section 19.4 - CLRS
Lecture #27
Tue 24/09 		Dijkstra's shortest path algorithm - example, correctness, implementation details using priority queues
Lecture #28
Wed 25/09 		Greedy Algorithms I (Job scheduling) - examples, greedy choices, counter-examples, exchange arguments
Test #2
Thu 26/09 		Based on Lectures 14 -23 (Problem sets 4, 5)
Lecture #29
Mon 30/09 		Greedy Algorithms II (Huffman coding) - prefix-free codes and binary trees, Huffman coding algorithm, examples
Lecture #30
Tue 01/10 		Greedy Algorithm III (Huffman coding) - proof of correctness, implementation details
PS6 released
Lecture #31
Thu 03/10 		Minimum spanning trees - examples, uniqueness, greedy choice
Tutorial #4
Mon 07/10 		Based on Problem set 6
Lecture #32
Tue 08/10 		Boruvka's and Prim's algorithms - examples, analysis, implementation details
Lecture #33
Wed 09/10 		Kruskal's algorithm - examples, analysis, implementation details • Union-Find data structure
Quiz #2
Thu 10/10 		Based on Lectures 14 - 28 (Problems sets 4, 5, 6)
Lecture #34
Mon 14/10 		Union-Find data structure - union by rank, examples, analysis • Path compression - examples, brief outline of the analysis.
  • Section 5.1.4 - DPV
 PS7 released
Lecture #35
Tue 15/10 		Dynamic programming - Fibonacci recurrence, memoization, DAGs • Longest Increasing Subsequence - examples, recurrence
Lecture #36
Thu 17/10 		Dynamic programming - Longest Increasing Subsequence and Edit distance
Lecture #37
Mon 21/10 		Dynamic programming on trees and DAGs - independent sets, and single-source-shortest-path
Lecture #38
Tue 22/10 		Dynamic programming on digraphs - shortest paths and the Bellman-Ford algorithm
Lecture #39
Wed 23/10 		All-pairs shortest-paths via dynammic programming • APSP and matrix multiplication
Lecture #40
Thu 24/10 		Floyd-Warshall algorithm • APSP and matrix multiplication - Seidel's algorithm
PS8 released
Lecture #41
Mon 28/10 		Efficient algorithms vs efficient verifiability - examples • Definition of NP - examples and non-examples
Lecture #42
Tue 29/10 		Hardness and reductions - definition of NP-completeness, examples, statement of the Cook-Levin theorem
Tutorial #5
Wed 30/10 		Based on Problem sets 7 and 8
Lecture #43
Mon 04/11 		Examples of reductions - CircuitSat to 3SAT, 3SAT to Independent-Set
Lecture #44
Tue 05/11 		More examples of reductions • P vs NP and its implications
PS9 released
Test #3
Thu 07/11 		Based on Lectures 29 - 40 (Problem sets 7 and 8)
End-sem
Wed 20/11 		Based on Lectures 1 - 44 (Problem sets 0 - 9)
No matching items