JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD

Prerequisites

• 1. A course on “Computer Programming and Data Structures”
• 2. A course on “Advanced Data Structures”

Course Objectives

• 1. Introduces the notations for analysis of the performance of algorithms.
• 2. Introduces the data structure disjoint sets.
• 3. Describes major algorithmic techniques (divide-and-conquer, backtracking, dynamic programming, greedy, branch and bound methods) and mention problems for which each technique is appropriate;
• 4. Describes how to evaluate and compare different algorithms using worst-, average-, and best- case analysis.
• 5. Explains the difference between tractable and intractable problems, and introduces the problems that are P, NP and NP complete.

Course Outcomes

• 1. Ability to analyze the performance of algorithms
• 2. Ability to choose appropriate data structures and algorithm design methods for a specified application
• 3. Ability to understand how the choice of data structures and the algorithm design methods impact the performance of programs

UNIT - I

Introduction: Algorithm, Performance Analysis-Space complexity, Time complexity, Asymptotic Notations- Big oh notation, Omega notation, Theta notation and Little oh notation. Divide and conquer: General method, applications-Binary search, Quick sort, Merge sort, Strassen’s matrix multiplication.

UNIT - II

Disjoint Sets: Disjoint set operations, union and find algorithms Backtracking: General method, applications, n-queen’s problem, sum of subsets problem, graph coloring

UNIT - III

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

UNIT - IV

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

UNIT - V

Branch and Bound: General method, applications - Travelling sales person problem, 0/1 knapsack problem - LC Branch and Bound solution, FIFO Branch and Bound solution. NP-Hard and NP-Complete problems: Basic concepts, non deterministic algorithms, NP - Hard and NP-Complete classes, Cook’s theorem.

R18 B.TECH CSE III YEAR

TEXT BOOKS:

• 1. Fundamentals of Computer Algorithms, Ellis Horowitz, Satraj Sahni and Rajasekharan, University Press.

REFERENCES:

• 1. Design and Analysis of algorithms, Aho, Ullman and Hopcroft, Pearson education.
• 2. Introduction to Algorithms, second edition, T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, PHI Pvt. Ltd./ Pearson Education.
• 3. Algorithm Design: Foundations, Analysis and Internet Examples, M.T. Goodrich and R. Tamassia, John Wiley and sons. R18 B.TECH CSE III YEAR