JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY 
HYDERABAD 
II Year B.Tech. CSE -II Sem  L T/P/D C 
4 -/-/-  4 
DESIGN AND ANALYSIS OF ALGORITHMS 

---

Objectives:

• To analyze performance of algorithms.
• To choose the appropriate data structure and algorithm design method for a specified application.
• To understand how the choice of data structures and algorithm design methods impacts the performance of programs.
• To solve problems using algorithm design methods such as the greedy method, divide and conquer, dynamic programming, backtracking and branch and bound.
• Prerequisites (Subjects) Data structures, Mathematical foundations of computer science.

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. 

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

UNIT II:

Searching and Traversal Techniques: Efficient non - recursive binary tree traversal algorithm, Disjoint set operations, union and find algorithms, Spanning trees, Graph traversals - Breadth first search and Depth first search, AND / OR graphs, game trees, Connected Components, Bi - connected components. Disjoint Sets- disjoint set operations, union and find algorithms, spanning trees, connected components and biconnected components. 

UNIT III: 

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

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 IV: 

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

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 V: 

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. Foundations of Algorithm, 4th edition, R. Neapolitan and K. Naimipour, Jones and Bartlett Learning.
3. Design and Analysis of Algorithms, P. H. Dave, H. B. Dave, Pearson Education, 2008.

REFERENCES : 

1. Computer Algorithms, Introduction to Design and Analysis, 3rd Edition, Sara Baase, Allen, Van, Gelder, Pearson Education.
2. Algorithm Design: Foundations, Analysis and Internet examples, M. T. Goodrich and R. Tomassia, John Wiley and sons.
3. Fundamentals of Sequential and Parallel Algorithm, K. A. Berman and J. L. Paul, Cengage Learning.
4. Introducation to the Design and Analysis of Algorithms, A. Levitin, Pearson Education.
5. Introducation to Algorithms, 3rd Edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, PHI Pvt. Ltd.
6. Design and Analysis of algorithm, Aho, Ullman and Hopcroft, Pearson Education, 2004.

Outcomes:

• ​Be able to analyze algorithms and improve the efficiency of algorithms.
• Apply different designing methods for development of algorithms to realistic problems, such as divide and conquer, greedy and etc. Ability to understand and estimate the performance of algorithm.