Course Description

Welcome to the Advanced Data Structure and Algorithms course!

This is a core course for first-year M.Tech CSE students, aimed at building a solid foundation in designing and analyising algorithms. It focuses on teaching students how to design algorithms for computational problems and formally reason about their correctness and efficiency.

Course Information

Prerequisites

A basic knowledge of Data Structures and Algorithms.

Books

1. Introduction to Algorithms by CLRS

Evaluation Scheme

1. 10% - Ten programming problems on CSES.
2. 20% - Quizzes (MCQs, T/Fs) (best 2 out of 3 quizzes)
3. 28% - Minor
4. 42% - Major
5. 0% - Practice problems whose variants may come in exam
6. Bonus 1% - For every first catch of an error during the lectures

Office Hours

Mail me to fix an appointment

Lectures

1. Course Overview, Administrative Details, Introduction ( Slides )
2. Binary Search Trees ( Slides )
3. Binary Search Trees (contd.) ( Slides )
4. BST: Insertion & Deletion, Intro to Red-Black Trees ( Slides )
5. Red-Black Trees, Height Bound, Insertion ( Slides )
6. Red-Black Trees: Insertion, Deletion ( Slides )
7. Red-Black Trees: Deletion ( Slides )
8. Red-Black Trees: Deletion (contd.), Augmenting Trees ( Slides )
9. Augmenting Trees (contd.) ( Slides )
10. Interval Trees ( Slides )
11. Disjoint-Set Data Structure ( Slides )
12. Disjoint-Set Data Structure (contd.) ( Slides )
13. Introduction to Graphs ( Slides )
14. Dijkstra’s Algorithm ( Slides )
15. Dijkstra’s Algorithm (contd.) ( Slides )
16. Dijkstra’s Algorithm (contd.), Flow Networks ( Slides )
17. Flow Networks, Ford-Fulkerson Method ( Slides )
18. Ford-Fulkerson Method (contd.), Max-Flow Min-Cut Theorem ( Slides )
19. Max-Flow Min-Cut Theorem ( Slides )
20. Maximum Bipartite Macthing ( Slides )
21. Maximum Bipartite Macthing (contd.), Edmonds-Karp Algorithm ( Slides )
22. Edmonds-Karp Algorithm (contd.) ( Slides )
23. Introduction to Dynamic Programming ( Slides )
24. Dynamic Programming: Rod Cutting (contd.), LCS ( Slides )
25. Dynamic Programming: LCS (contd.) ( Slides )
26. Dynamic Programming: Counting Boolean Parenthesizations, Bellman-Ford ( Slides )
27. Dynamic Programming: Bellman-Ford (contd.), Activity-Selection Problem ( Slides )
28. Dynamic Programming: Activity-Selection Problem (contd.) ( Slides )
29. Greedy: Activity-Selection Problem (contd.), MST ( Slides )
30. Greedy: MST, Kruskal’s Algorithm ( Slides )
31. Greedy: Kruskal’s Algorithm (contd.), Prim’s Algorithm ( Slides )
32. P, NP ( Slides )
33. NP, P vs NP ( Slides )
34. Reductions, NP-complete ( Slides )
35. More NP-complete Problems ( Slides )
36. Reductions: IndSet, VertexCover, DirHampath ( Slides )
37. Reductions: DirHampath (contd.), Hampath, Hamcycle ( Slides )
38. Hamcycle to TSP, Approximation Algorithms, OptVertexCover ( Slides )
39. Approximability and Inapproximability of OptTSP ( Slides )

Programming Assignments

1. Problem 1
2. Problem 2
3. Problem 3
4. Problem 4
5. Problem 5
6. Problem 6
7. Problem 7
8. Problem 8
9. Problem 9
10. Problem 10

Practice Problem Sets

1. Problem Set 1
2. Problem Set 2
3. Problem Set 3
4. Problem Set 4
5. Problem Set 5