IT300

Course Name: 

Design and Analysis of Algorithms (IT300)

Programme: 

B.Tech (IT)

Semester: 

Fourth

Category: 

Programme Core (PC)

Credits (L-T-P): 

(3-0-2) 4

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.

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
 

Contact us

Biju R Mohan

Head of the Department,
Department of Information Technology, NITK, Surathkal,
P. O. Srinivasnagar, Mangalore - 575 025
Karnataka, India.
Ph.:    +91-824-2474056
Email:  infotech[AT]nitk[DOT]ac[DOT]in
            infotech[AT]nitk[DOT]edu[DOT]in

Sowmya Kamath S (Web Admin)

Connect with us

We're on Social Networks. Follow us & stay in touch.