2K6CS 702 DESIGN AND ANALYSIS OF ALGORITHMS

Module I (12 hours)
Role of algorithms in computing – RAM model – growth of functions – asymptotic notations (Big-Oh, Little-Oh, Big omega, Little omega, Theta)- solution to recurrences – substitution method-recursion treemastertheorem (proof not expected)-Analysis of sorting algorithms – merge sort, heap sort, quick sort- Analysis of string matching algorithms -KMP algorithm. Amortized Analysis –Aggregate –Accounting –Potential Methods
Module II (14 hours)
Different approaches to algorithm design: Divide and conquer – Strassens matrix multiplication –MedianFinding-Greedy method – Huffman code-Minimum cost spanning tree-Kruskals and Prims algorithm-Dynamic programming –Optimal binary search tree– Chain matrix multiplication Back tracking – Queens problem–Branch and bound-assignment problem-TSP
Module III (12 hours)
Complexity: complexity classes – P,NP,Co-NP, NP-hard and NPC problems – cooks theorm (proof notexpected) – NP completeness reductions for clique – vertex cover – subset sum – Hamiltonian cycle – TSPapproximationalgorithms – vertex cover – TSP – set covering and subset sum
Module IV (14 hours)
Randomized algorithms: Some complexity classes randomized algorithm for n-Queen , Quick sort-Probabilistic algorithms: pseudo random number generation methods – Monte Carlo algorithms -probabilistic counting – verifying matrix multiplication – primality testing – miller rabin test – integerfactorization – Dixon’s integer factorization algorithm -Pollard’s rho heuristic amplification of stochasticadvantage – Les Vegas algorithms.
 

Text books
1. Corman T H, Lieserson C E & Rivest R L, Introduction to Algorithms, PHI
2. Motwani R & Raghavan P, Randomized algorithms, Cambridge university press
3. Gilles Brassard, Paul Bratley, “Fundamentals of Algorithms”, PHI
Reference books
1. Basse S, Computer Algorithms : Introduction to design and analysis, Addison Wesley
2. S K Basu , Design methods and analysis of algorithms, PHI
3. Berman and Paul, “Algorithms”,Cenage Learning Indian Edition