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

http://www.cise.ufl.edu/~raj/BOOK.html

No comments:

Post a Comment