Instructor: Partha Sarathi Mandal [TEL: 03612582624, E-mail ID: psm
Department of Mathematics, Indian Institute of Technology Guwahati
Course title: Design and Analysis of Algorithms [MA252] [3-0-0-6]
Level: B.Tech.(M&C)
Prerequisites: MA 221 or MA251 or equivalent.
Semester: Jan'26 - May'26
MA252:Lecture Time: Tuesday: 8-8:55, Wednesday:9-9:55, Thursday: 10-10:55
Class Room: 5104
TA: Eshwar Srinivasan (E-mail ID: s.eshwar)
Contents: Click Here
Exams & Marking: POP Quizzes (30%) + Mid semester (30%) + End Semester (40%)
Texts:
  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, Prentice-Hall of India, 2009.
References:
  1. A. V. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis of Computer Algorithms, Pearson Education, 2006.
  2. J. Kleinberg and E. Tardos, Algorithm Design, Pearson Education, 2006.
  3. E. Horowitz and S. Sahni, Fundamentals of Computer Algorithms, Galgotia Publishers, 1984.
  4. M. T. Goodrich and R. Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley, 2001.
  5. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice Hall of India, 1992.
Announcement:
  1. First lecture is on 6th January
Lecture Notes: ___________________________________________________________________________
Jan 06 Lecture 1 [Tests and marks distribution, Reference Books, Introduction]
Jan 07 Lecture 2 [Recap sorting algorithms, Decision Tree, Lower bound for comparison sorting]
Jan 08 Lecture 3 [Recap sorting in linear time, Bucket Sort, Radix sort]
Jan 13 Lecture 4 [Median and Order Statistics, Randomized Selection]
Jan 15 Lecture 5 [Order Statistics in linear-time and Disjoint Set data structure]
Jan 20 Lecture 6 [Disjoint Set data structures Contd., Greedy Algorithm Paradigm: MST]
Jan 21 Lecture 7 [Greedy Algorithm Paradigm: Kruskal's Algorithm for finding MST]
Jan 22 Lecture 8 [Knapsack Problem]
Jan 27 Lecture 9 [Prim's Algorithm]
Jan 28 Lecture 10 [SSSP: Dijkstra's Algorithm]
Feb 03 Quiz I
Feb 04 Lecture 11 [Bellman Ford Algorithm, Interval Scheduling Problems]
Feb 10-11 Lecture 12-13 [Dynamic Programming (DP) Paradigm: DP Solution for Fibonacci Numbers, Longest common subsequence (LCM)]
Feb 12 Lecture 14-15 [0-1 Knapsack problem & Matrix Chain Ordering Problem]
Feb 17 Lecture 16 [All-Pairs Shortest Paths]
Feb 18-19 Lectures 17-18 [Amortized Analysis]
Feb 25 Lecture 19 [Graph algorithms: Properties of BFS and DFS, connected components, Topological sort, Strongly Connected Components, Biconnected Components]
Feb 26 Lecture 20 [Divide and Conquer: Closest Pair of Points]