ADA MTech

Advance Data Structure and Algorithms

Instructor Details

Name: AJAYA KUMAR DASH
Email:
@Office:
- CB-51, Faculty chambers, IIIT Bhubaneswar
- AR Lab, 1st Floor, C Block, IIIT Bhubaneswar ( Most likely to be found )

Class schedule ( ≈ 4 hrs per Week)

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

Prerequisites

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

Syllabus

You can find the syllabus [here].

Books

Text Book

T1. Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. (CLRS, 3rd 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

Assignments

Submission Due: ~~November 30, 2023~~

Course Progress and Resources

Serial No			Reading List	Topics Discussed
1	-	2hrs	[T1] Chapter 2 & 3	Overview of the course, motivation and introduction, Model of computation, concepts of worst case, best case and average case time, Asymptotic notations revisited (Definitions, interpretations).
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	Lect7 Note	[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	-	2hrs	[ClassNote]	[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.
9	-	2hrs	[T1] Chapter 29	[Linear Programming-I]: Introduction and overview, Definition of Linear Programming, Modeling problems as Linear programs: network flow, shortest path, Feasible solution space, Geometric interpretation of solving a linear programming problem, Duality overview.
10	-	2hrs	[T1] Chapter 29	[Linear Programming-II]: Algorithms for linear programming: Overview of Simplex, Ellipsoid, and Karmarkar’s approach; Algorithm of Simplex method: Idea, algorithm, example, complexity. Solution of mid-semester question discussed.
11	-	2hrs	[ClassNote]	[Complexity Theory]: Introduction to complexity classes, concept behind polynomial time reduction; Overview of P, NP, co-NP, NP-Complete class of problems.
12	-	2hrs	[ClassNote]	[Complexity Theory]: I. Necessary tools and techniques for recognizing NP-Hard problems.
13	-	2hrs	[ClassNote]	[Complexity Theory]: II. Necessary tools and techniques for recognizing NP-Hard problems.
14	-	2hrs	[ClassNote]	[Approx. Algorithms]: Handling NP-Hard problems: The approximation algorithms; 2-approximation algorithm for vertex cover problem.
15	-	2hrs	[ClassNote]	[Approx. Algorithms]: The TSP problem, Euclidean TSP, 2-approximation algorithm for Euclidean TSP.
16	-	2hrs	[ClassNote]	[Text Processing]: String matching: Naive algorithm, complexity analysis; Rabin_Karp algorithm, complexity analysis.
17	-	2hrs	Presentation	[Advanced DS]: Splay Trees: definition, reprsentations, basic operations, complexity analysis; 2-3 Trees: definition, reprsentations, basic operations, complexity analysis.
18	-	2hrs	Presentation	[Advanced DS]: Red-Black Trees: definition, reprsentations, basic operations, complexity analysis; Fibonacci heap: definition, reprsentations, basic operations, complexity analysis.
19	-	1hr	Presentation	[Advanced DS]: B Trees: definition, reprsentations, basic operations, complexity analysis.