Meena's Class Prints: MSC Design and Analysis of Algorithms

Title of the Course/ Paper	Design and Analysis of Algorithms
Core	Second Year & Third Semester	Credit: 4	Sl. No.: 16
Objective of the course	This course gives insight into the design and analysis for selected problems.
Course outline	Unit 1: Introduction - Definition of Algorithm – pseudocode conventions – recursive algorithms – time and space complexity –big-“oh” notation – practical complexities – randomized algorithms – repeated element – primality testing - Divide and Conquer: General Method - Finding maximum and minimum – merge sort.
	Unit 2: Divide and conquer contd. – Quicksort, Selection, Strassen's matrix multiplication – Greedy Method: General Method –knapsack problem - Tree vertex splitting - Job sequencing with dead lines – optimal storage on tapes.
	Unit 3: Dynamic Programming: General Method - multistage graphs – all pairs shortest paths – single source shortest paths - String Editing – 0/1 knapsack. Search techniques for graphs – DFS-BFS-connected components – biconnected components.
	Unit 4: Back Tracking: General Method – 8-queens - Sum of subsets - Graph Coloring – Hamiltonian cycles. Branch and Bound: General Method - Traveling Salesperson problem.
	Unit 5 : Lower Bound Theory: Comparison trees - Oracles and advisory arguments - Lower bounds through reduction - Basic Concepts of NP-Hard and NP-Complete problems.

1. Recommended Texts

(i) E. Horowitz, S. Sahni and S. Rajasekaran, 1999, Computer Algorithms, Galgotia, New Delhi.

2. Reference Books

(i) G. Brassard and P. Bratley, 1997, Fundamentals of Algorithms, PHI,

New Delhi.

(ii) A.V. Aho, J.E. Hopcroft, J.D. Ullmann, !974, The design and analysis of Computer Algorithms, Addison Wesley, Boston.

(iii) S.E.Goodman and S.T.Hedetniemi, 1977, Introduction to the Design and Analysis of algorithms, Tata McGraw Hill Int. Edn, New Delhi.

3. Website, E-learning resources

Meena's Class Prints