ADA MTech

Advance Data Structure and Algorithms

Instructor Details

Name: AJAYA KUMAR DASH
Email:
@Office:
- CG-19, Faculty chamber, IIIT Bhubaneswar
- AR Lab, 1st Floor, C Block, IIIT Bhubaneswar ( Occasionally present here )

Class schedule ( ≈ 4 hrs per Week)

Day → Branch ↓	Monday	Tuesday	Wednesday	Thursday	Friday	Saturday	Sunday
MTech-CS (A 106)	03:00 pm - 05:00 pm	-	11:00 am - 01:00 pm	-	-	-	-

Prerequisites

UG level courses on Data Structures, Design and Analysis on Algorithms.

Syllabus

You can find the syllabus of ADSA in the linked document [here].

Books

Text Book

T1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. (CLRS, 4th Ed.)

Reference Books

R1. Handbook of Data Structures and Applications by Dinesh P Mehta, Sartaj Sahni, Chapman and Hall/CRC.
R2. Algorithms by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani, McGraw Hill Education (India) Pvt. Ltd.
R3. The Design and Analysis of Computer Algorithms by Aho, Hopcroft, Ullman, Addison-Wesley.
R4. Algorithm Design: Foundations, Analysis, and Internet Examples by M. T. Goodrich, R. Tamassia, John Wiley & Sons.
R5. Algorithm Design by Jon Kleinberg, Éva Tardos, Pearson.
R6. The algorithm design manual, Second Edition, by Steven S. Skiena, Springer-Verlag London Limited.
R7. Computational Geometry: Algorithms and Applications By Mark Berg et al., Springer Berlin, Heidelberg.

Evaluation

Classroom Assignments

Submission Due: December 30, 2025
- Instruction to upload a single pdf file and the link will be updated before the due date.

Course Progress and Resources

Serial No			Reading List	Topics Discussed
1	-	3hrs	[T1] Chapter 2 & 3 [ClassNote]	Overview of the course, motivation and introduction, model of computation, concepts of worst case, best case and average case time, asymptotic notations revisited, a glimpse of an undergraduate level algorithm: Heap sort and lower bound for sorting.
2	-	2hrs	[T1] Chapter 4.2	[Matrix Computations-I]: Divide and conquer paradigm revisited, Strassen’s matrix multiplication (Definition, problem statement, algorithm development, complexity analysis).
3	-	2hrs	Lect5 Note	[Matrix Computations-II]: Introduction to LUP decompostion, problem statement, forward and backward substitution, LUP solve, complexity of LUP solve, Example.
4	-	2hrs	Lect5 Note	[Matrix Computations-III]: Gaussian elimination for LU decomposition, building mathematical foundation for the algorithm, Schur complement, LU decompostion algorithm, Complexity, Example.
5	-	2hrs	[ClassNote]	[Matrix Computations-IV]: Necessity of LUP decomposition over LU decomposition, Building mathematical foundations, LUP decompostion algorithm, Complexity, Example; Inverting a matrix using LUP decomposition, complexity, example.
6	-	2hrs	[T1] Chapter 24.1 & 24.2	[Flow Networks-I]: Problem statement, basic terminologies, flows, cuts, maxflow-mincut theorem, building mathematical foundations, Residual network, augmenting path, example.
7	-	2hrs	[ClassNote]	[Flow Networks-II]: Ford-Fulkersion Algorithm to find maximum flow, Example and complexity; Finding minimum cut, example; Idea of Edmond-Karp algorithm for maximum flow.
8	-	4hrs	[ClassNote] [T1] Chapter 24.3 and 25.1	[Graph Matching]: Problem statement discussion, definition of maximal and maximum matching, perfect matching, altering and augmenting path, Building mathematical foundation, Berge’s Theorem and proof; The naive algoritm to find maximum matching, Maximum bipartite matching, Edmond’s Blossom Algorithm
9	-	2hrs	[ClassNote]	[Complexity Theory]: Introduction to complexity classes, concept behind polynomial time reduction; Overview of P, NP, co-NP, NP-Complete class of problems.
10	-	3hrs	[ClassNote] [T1] Chapter 34	[Complexity Theory]: I. Necessary tools and techniques for recognizing NP-Hard problems.
11	-	2hrs	[ClassNote] [T1] Chapter 34	[Complexity Theory]: II. Necessary tools and techniques for recognizing NP-Hard problems.
12	-	2hrs	[T1] Chapter 35.1	[Approx. Algorithms]: Handling NP-Hard problems: The approximation algorithms; 2-approximation algorithm for vertex cover problem.
13	-	2hrs	[T1] Chapter 35.2	[Approx. Algorithms]: The TSP problem, Euclidean TSP, 2-approximation algorithm for Euclidean TSP.
14	-	2hrs	[T1] Chapter 32.1, 32.2, 32.4 & Presentations	[Text Processing]: String matching: Naive algorithm, complexity analysis; Rabin_Karp algorithm, complexity analysis, The Knuth-Morris-Pratt (KMP) algorithm with complexity analysis.
15	-	1hr	Presentation	Splay Trees: definition, reprsentations, basic operations, complexity analysis.
16	-	1hr	Presentation	Huffman coding alogithm, entropy, complexity analysis, application to image compression.
16	-	1hr	Presentation	Fibonacci heap: definition, reprsentations, basic operations, complexity analysis.
17	-	1hr	Presentation	Line segmenent intersection, algorithm, complexity analysis, application of line segment intersection in Computer graphics.