IT300
Course Name:
Design and Analysis of Algorithms (IT300)
Programme:
Semester:
Category:
Credits (L-T-P):
Content:
Models of computation, algorithm analysis and asymptotic notation, time and space complexity, average and worst case analysis, lower bounds. Amortized analysis. Algorithm design techniques: recursion, branch-and-bound, divide and conquer, greedy, dynamic programming, randomization. Applications of the above techniques to a variety of problems: Stable matching, linear-time selection, integer, polynomial and matrix multiplications, Fast Fourier Transforms (FFT): FFT Algorithms, computing shortest paths and minimum spanning trees, etc. Reductions and the theory of NP-Completeness, Approximation algorithms.