JNTUH Design and Analysis of Algorithms syllabus CS 3-2 Sem R18 CS603PC

Unit-1 Introduction

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-2 Disjoint Sets

Disjoint Sets:

Disjoint set operations, union and find algorithms

 

Backtracking:

General method, applications, n-queen’s problem, sum of subsets problem, graph coloring

Unit-3 Dynamic Programming

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-4 Greedy method

Greedy method:

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

Unit-5 Branch and Bound

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.

 

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.

 

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