JNTUH B.Tech Design and Analysis of Algorithms R09 Syllabus

 August 11, 2013     VIKRAM     1930
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY 
HYDERABAD 
III Year B.Tech. CSE -I Sem T P C 
4+1* 0 4 
DESIGN AND ANALYSIS OF ALGORITHMS 

UNIT I : 
Introduction: Algorithm,Psuedo code for expressing algorithms,Performance Analysis-Space complexity, 
Time complexity, Asymptotic Notation- Big oh notation, Omega notation, Theta notation and Little oh 
notation,Probabilistic analysis, Amortized analysis. 

UNIT II : 
Disjoint Sets- disjoint set operations, union and find algorithms, spanning trees, connected components 
and biconnected components. 

UNIT III : 
Divide and conquer: General method , applications-Binary search, Quick sort, Merge sort, Strassen’s 
matrix multiplication. 

UNIT IV : 
Greedy method: General method, applications-Job sequencing with dead lines, 0/1 knapsack problem, 
Minimum cost spanning trees, Single source shortest path problem. 

UNIT V : 
Dynamic Programming: General method, applications-Matrix chain multiplication, Optimal binary search 
trees, 0/1 knapsack problem, All pairs shortest path problem,Travelling sales person problem, Reliability 
design. 

UNIT VI : 
Backtracking: General method, applications-n-queen problem, sum of subsets problem, graph coloring, 
Hamiltonian cycles. 

UNIT VII : 
Branch and Bound: General method, applications - Travelling sales person problem,0/1 knapsack 
problem- LC Branch and Bound solution, FIFO Branch and Bound solution. 

UNIT VIII : 
NP-Hard and NP-Complete problems: Basic concepts, non deterministic algorithms, NP - Hard and 
NPComplete classes, Cook’s theorem. 

TEXT BOOKS : 
1. Fundamentals of Computer Algorithms, Ellis Horowitz,Satraj Sahni and 
 Rajasekharam,Galgotia publications pvt. Ltd. 
2. Algorithm Design: Foundations, Analysis and Internet examples, 
 M.T.Goodrich and R.Tomassia,John wiley and sons. 

REFERENCES : 
1. Introduction to Algorithms, secondedition,T.H.Cormen,C.E.Leiserson, 
 R.L.Rivest,and C.Stein,PHI Pvt. Ltd./ Pearson Education
2. Introduction to Design and Analysis of Algorithms A strategic approach, 
 R.C.T.Lee, S.S.Tseng, R.C.Chang and T.Tsai, Mc Graw Hill. 
3. Data structures and Algorithm Analysis in C++, Allen Weiss, Second 
 edition, Pearson education. 
4. Design and Analysis of algorithms, Aho, Ullman and Hopcroft,Pearson 
 education. 
5. Algorithms – Richard Johnson baugh and Marcus Schaefer, Pearson 
 Education