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'24 - May'24
MA252:Lecture Time: Monday: 9-9:55, Tuwsday:10-10:55, Wednesday: 11-11:55
Class Room: 5102
TA: Adri Bhattacharya (E-mail ID: a.bhattacharya)
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. Quiz II: Wednesday 03 April 2024 (11-11:50AM) as per class time, Venue: 2201, 2202, 2203 (Core 2)
  2. Quiz I: 7th Feb, 2024 (11-11:50AM) as per class time, Venue: 2203 (Core 2)
Lecture Notes: ___________________________________________________________________________
Jan 08 Lecture 1 [Tests and marks distribution, Reference Books, Introduction]
Jan 09 Lecture 2 [Recap sorting algorithms, Decision Tree, Lower bound for comparison sorting]
Jan 10 Lecture 3 [Recap sorting in linear time, Bucket Sort, Radix sort]
Jan 16 Lecture 4 [Recap quicksort, Randomized quicksort]
Jan 17 Lecture 5 [Median and Order Statistics]
Jan 23 Lecture 6 [Greedy Algorithm Paradigm: Knapsack Problem]
Jan 24 Lecture 7 [Disjoint set data structure]
Jan 29 Lecture 8 [Disjoint set contd., MST: Kruskal's Algorithm]
Jan 30 Lecture 9 [Prim's Algorithm]
Jan 31 Lecture 10 [SSSP: Dijkstra's Algorithm]
Feb 05 Lecture 11 [SSSP: Bellman Ford Algorithm]
Feb 06 Lecture 12 [Dynamic Programming Paradigm: Longest common subsequence (LCM)]
Feb 07 Quiz I
Feb 13 Lecture 13 [0-1 Knapsack problem]
Feb 14 Lecture 14 [DP Solution for Fibonacci, Matrix Chain Order Problem]
Feb 17 Lecture 15 [All-Pairs Shortest Paths]
Feb 19 Lecture 16 [Recap DFS, Topological sort]
Feb 20 Lecture 17 [Strongly Connected Components, Articulation points, Bridges and Biconnected Components]
Feb 21 Lecture 18 [Divide and Conquer: Closest Pair of Points]
Feb 25 Midsem
Mar 04 Lecture 19 [DP: Weighted Interval Scheduling]
Mar 05-06 Lectures 20-21 [Network Flow]
Mar 11-13 Lectures 22-23 [Network Flow contd.]
Mar 18-20 Lectures 24-26 [Amortized Analysis]
Apr 01-02 Lectures 27-28 [Complexity Classes (P, NP)]
Apr 03 Quiz II
Apr 08 Lectures 29 [Complexity Classes contd. (Reduction)]
Apr 09-10 Lectures 30-31 [Complexity Classes contd. (NP-Hard and NP-Complete)]
Apr 16-17 Lectures 32-33 [Some NP-Complete problems]