### JNTUH B.Tech Design and Analysis of Algorithms R13 Syllabus

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

- Fundamentals of Computer Algorithms, Ellis Horowitz,Satraj Sahni and Rajasekharam,Galgotia publications pvt. Ltd.
- Foundations of Algorithm, 4th edition, R. Neapolitan and K. Naimipour, Jones and Bartlett Learning.
- Design and Analysis of Algorithms, P. H. Dave, H. B. Dave, Pearson Education, 2008.

**REFERENCES : **

- Computer Algorithms, Introduction to Design and Analysis, 3rd Edition, Sara Baase, Allen, Van, Gelder, Pearson Education.
- Algorithm Design: Foundations, Analysis and Internet examples, M. T. Goodrich and R. Tomassia, John Wiley and sons.
- Fundamentals of Sequential and Parallel Algorithm, K. A. Berman and J. L. Paul, Cengage Learning.
- Introducation to the Design and Analysis of Algorithms, A. Levitin, Pearson Education.
- Introducation to Algorithms, 3rd Edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, PHI Pvt. Ltd.
- 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.