JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Course 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.
• To understand the differences between tractable and intractable problems.
• To introduce P and NP classes.

Course Outcomes:

• Ability to analyze the performance of algorithms.
• Ability to choose appropriate algorithm design techniques for solving problems.
• Ability to understand how the choice of data structures and the algorithm design methods impact the performance of programs.

UNIT - I

Introduction-Algorithm definition, Algorithm Specification, Performance Analysis-Space complexity, Time complexity, Randomized Algorithms. Divide and conquer- General method, applications - Binary search, Merge sort, Quick sort, Strassen’s Matrix Multiplication.

UNIT - II

Disjoint set operations, union and find algorithms, AND/OR graphs, Connected Components and Spanning trees, Bi-connected components Backtracking-General method, applications- The 8-queen problem, sum of subsets problem, graph coloring, Hamiltonian cycles.

UNIT - III

Greedy method- General method, applications- Knapsack problem, Job sequencing with deadlines, Minimum cost spanning trees, Single source shortest path problem.

UNIT - IV

Dynamic Programming- General Method, applications- Chained matrix multiplication, All pairs shortest path problem, Optimal binary search trees, 0/1 knapsack problem, Reliability design, Traveling sales person problem.

R16 B.TECH CSE.

UNIT - V

Branch and Bound- General Method, applications-0/1 Knapsack problem, LC Branch and Bound solution, FIFO Branch and Bound solution, Traveling sales person problem. NP-Hard and NP-Complete problems- Basic concepts, Non-deterministic algorithms, NP - Hard and NP- Complete classes, Cook’s theorem.

TEXT BOOKS:

• 1. Fundamentals of Computer Algorithms, 2nd Edition, Ellis Horowitz, Sartaj Sahni and S. Rajasekharan, Universities Press.
• 2. Design and Analysis of Algorithms, P. H. Dave, H.B.Dave,2nd edition, Pearson Education.

REFERENCE BOOKS

• 1. Algorithm Design: Foundations, Analysis and Internet examples, M. T. Goodrich and R. Tomassia, John Wiley and sons.
• 2. Design and Analysis of Algorithms, S. Sridhar, Oxford Univ. Press
• 3. Design and Analysis of algorithms, Aho, Ullman and Hopcroft, Pearson Education.
• 4. Foundations of Algorithms,, R. Neapolitan and K. Naimipour, 4th edition, Jones and Bartlett Student edition.
• 5. Introduction to Algorithms,3 rd Edition, T. H. Cormen, C. E.Leiserson, R. L. Rivest, and C. Stein, PHI R16 B.TECH CSE.