R-20 Syllabus for CSE, JNTUK w. e. f.
2020 21
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY KAKINADA
KAKINADA 533 003, Andhra Pradesh, India
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
L T P C
III Year I Semester
3 0 0 3
DESIGN AND ANALYSIS OF ALGORITHMS
Course Objectives:
Upon completion of this course, students will be able to do the following:
Ability to understand, analyze and denote time complexities of algorithms
To introduce the different algorithmic approaches for problem solving through numerous example
problems
Describe the dynamic-programming paradigm and explain when an algorithmic design situation
calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming
algorithms, and analyze them.
To provide some theoretical grounding in terms of finding the lower bounds of algorithms and the
NP-completeness
Course Outcomes: After the completion of the course, student will be able to
Analyze the performance of a given algorithm, denote its time complexity using the asymptotic
notation for recursive and non-recursive algorithms
List and describe various algorithmic approaches and Solve problems using divide and conquer
&greedy Method
Synthesize efficient algorithms dynamic programming approaches to solve in common
engineering design situations.
Organize important algorithmic design paradigms and methods of analysis: backtracking, branch
and bound algorithmic approaches
Demonstrate NP- Completeness theory ,lower bound theory and String Matching
UNIT I:
Introduction: Algorithm Definition, Algorithm Specification, performance Analysis, Performance
measurement, asymptotic notation, Randomized Algorithms.
UNIT II:
Divide and Conquer: General Method, Defective chessboard, Binary Search, finding the maximum and
minimum, Merge sort, Quick sort.
The Greedy Method: The general Method, knapsack problem, minimum-cost spanning Trees, Optimal
Merge Patterns, Single Source Shortest Paths.
UNIT III:
Dynamic Programming: The general method, multistage graphs, All pairs-shortest paths, optimal Binary
search trees, 0/1 knapsack, The traveling salesperson problem.
UNIT IV:
Backtracking: The General Method, The 8-Queens problem, sum of subsets, Graph coloring,
Hamiltonian cycles, knapsack problem.
UNIT V:
NP-Hard and NP-Complete problems: Basic concepts, non-deterministic algorithms, NP - Hard and
NP-Complete classes, Cooks theorem.
R-20 Syllabus for CSE, JNTUK w. e. f. 2020 21
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY KAKINADA
KAKINADA 533 003, Andhra Pradesh, India
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
Text Books:
1. Ellis Horowitz, SartajSahni, Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms,
nd
2 Edition, Universities Press.
2. Introduction to Algorithms Thomas H. Cormen, PHI Learning
3. Harsh Bhasin, Algorithms Design & Analysis, Oxford University Press.
Reference Books:
nd
1. Horowitz E. Sahani S: Fundamentals of Computer Algorithms, 2 Edition, Galgotia
Publications, 2008.
2. S. Sridhar, Design and Analysis of Algorithms, Oxford University Press.
