Course Archives Theoretical Statistics and Mathematics Unit

Course: Design and Analysis of Algorithms Level: Undergraduate Time: Currently not 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 Top of the page Past Exams

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

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