| Course Code | CS 218 |
| Course Name | Design and Analysis of Algorithms |
| Offered to | UG/PG |
| 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. |