CS 218 : Design and Analysis of Algorithms
Course Code CS 218
Course Name Design and Analysis of Algorithms
Offered to UG
Pre-requisites NIL
Lecture 3
Tutorial 0
Practical 0
Credit 6
Reference 1. T.H.Cormen, C.E.Leiserson, R.L.Rivest, C. Stein, Introduction to Algorithms, 2nd edition, Prentice-Hall India, 2001.
2. J. Kleinberg and E. Tardos, Algorithm Design, Pearson International Edition, 2005.
Description Models of computation, algorithm analysis, time and space complexity, average and worst case analysis, lower bounds. Algorithm design techniques: divide and conquer, greedy, dynamic programming, amortization, randomization. Problem classes P, NP, PSPACE; reducibility, NP-hard and NP-complete problems. Approximation algorithms for some NP-hard problems