IT700
Course Name:
Advanced Algorithms (IT700)
Programme:
M.Tech (IT)
Semester:
First
Category:
Programme Core (PC)
Credits (L-T-P):
(3-0-2) 4
Content:
Review of algorithm analysis. Stable Matching Problem, Algorithm design techniques: recursion, branch-and-bound, divide and conquer, greedy, dynamic programming; integer linear programming; polynomial and matrix multiplications: Fast Fourier Transforms (FFT), FFT Algorithms, Amortized analysis, Advanced Data Structures to implement Disjoint Sets, Priority Queues and other Dynamic Sets. Randomized algorithms to solve fundamental problems like sorting, MST, min-cuts, geometric problems, caching, load balancing, etc. Reductions and theory of NP-complete problems, Approximation algorithms, Local Search heuristics and On-line algorithms.
References:
Jon Kleinberg and Eva Tardos, Algorithm Design, 1st Edition, Pearson Education India, 2013.
S Dasgupta, C Papadimitriou, U Vazirani, Algorithms, McGraw-Hill Education, 2006.
T H Cormen, C E Leiserson, R L Rivest, C Stein, Introduction to Algorithms, 3rd Edition, PHI, 2010.
Steven S Skiena, The Algorithm Design Manual, 2nd Edition, Springer-Verlag, 2nd Edition, 2013.
Michael T. Goodrich and Roberto Tamassia. Algorithm Design, Wiley, 1st Edition, 2006.
Horowitz and Sahni, Fundamentals of Computer Algorithms, Galgotia Publications, 2nd Edition, 2009.
Department:
Information Technology