Course Archives Theoretical Statistics and Mathematics Unit

Course: Design and Analysis of Algorithms Instructor: R Badrinath Room: G23 Level: Undergraduate Time: Currently offered

Syllabus Past Exams Syllabus: Basics of Algortihm Analysis: Models of computation, asymptotic order of growth, algorithm analysis, time and space complexity, average and worst case analysis, lower bounds. Algorithm design techniques: Greedy algorithms, Divide and conquer, dynamic pro- gramming, amortization, randomization. Complexity classes: Problem classes P, NP, PSPACE; reducibility, NP-hard and NP complete problems. Approximation algorithms for some NP-hard problems. Reference Texts: (a) T. H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein: Introduction to Algorithms (b) J. Kleinberg and E. Tardos: Algorithm Design (c) R. Sedgewick and P. Flajolet: Introduction to the Analysis of Algorithms (d) R. Sedgewick: Algorithms (e) A. Aho, J. Hopcroft and J. Ullmann: Introduction to Algorithms and Data Structures (f) M. Sipser: Introduction to the Theory of Computation (g) S. S. Skiena: The algorithm Design Manual Evaluation: Mid-term 30 marks Assignment 20 marks Final Exam 50 marks Total 100 marks Top of the page Past Exams

Midterm 24.pdf 25.pdf Semestral 24.pdf Supplementary and Back Paper 25.pdf Top of the page

[ Semester Schedule ][ Statmath Unit ] [Indian Statistical Institute]