Design and Analysis of Algorithms |
UNIT I |
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 II |
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 III |
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 IV |
Back Tracking: General Method 8-queens - Sum of subsets - Graph
Coloring Hamiltonian cycles. Branch and Bound: General Method -
Traveling Salesperson problem. |
UNIT V |
Lower Bound Theory: Comparison trees - Oracles and advisory
arguments - Lower bounds through reduction - Basic Concepts of NP-Hard and
NP-Complete problems. |
Text Books |
(i) E. Horowitz, S. Sahni and S. Rajasekaran, 1999, Computer Algorithms, Galgotia,
New Delhi. |
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. |
Website, E-learning resources |
(i) http://www.cise.ufl.edu/~raj/BOOK.html |