DIGITAL NOTES
ON
DESIGN AND ANALYSIS OF ALGORITHMS
B.TECH II YEAR - II SEM
(2017-18)
DEPARTMENT OF INFORMATION TECHNOLO
MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, INDIA.
DESIGN AND ANALYSIS OF ALGORITHMS Page 1
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF INFORMATION TECHNOLOGY
SYLLABUS
MALLA REDDY COLLEGE OF ENGINEERING AND
TECHNOLOGY
II Year B.Tech IT – II Sem L T /P/D C
4 -/-/- 3
(R15A0508)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 deadlines, 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.
DESIGN AND ANALYSIS OF ALGORITHMS Page 2
,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:
1. Fundamentals of Computer Algorithms, Ellis Horowitz,Satraj Sahni
and Rajasekharam,Galgotia publications pvt. Ltd.
2. Foundations of Algorithm, 4th edition, R. Neapolitan and K. Naimipour, Jones and
Bartlett Learning.
3. Design and Analysis of Algorithms, P. H. Dave, H. B. Dave, Pearson Education,
2008.
REFERENCES:
1. Computer Algorithms, Introduction to Design and Analysis, 3rd Edition, Sara Baase,
Allen, Van, Gelder, Pearson Education.
2. Algorithm Design: Foundations, Analysis and Internet examples, M. T. Goodrich and
R. Tomassia, John Wiley and sons.
3. Fundamentals of Sequential and Parallel Algorithm, K. A. Berman and J. L. Paul,
Cengage Learning.
4. Introducation to the Design and Analysis of Algorithms, A. Levitin, Pearson
Education.
5. Introducation to Algorithms, 3rd Edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest,
and C. Stein, PHI Pvt. Ltd.
6. 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.
DESIGN AND ANALYSIS OF ALGORITHMS Page 3
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF INFORMATION TECHNOLOGY
INDEX
S. No Topic Page no
Unit
1 Introduction to Algorithms 5
I
2 I Divide and Conquer 24
3 II Searching and Traversal Techniques 42
4 III Greedy Method 54
5 III Dynamic Programming 67
6 IV Back Tracking 102
7 IV Branch and Bound 114
8 V NP-Hard and NP-Complete Problems 133
9
DESIGN AND ANALYSIS OF ALGORITHMS Page 4
ON
DESIGN AND ANALYSIS OF ALGORITHMS
B.TECH II YEAR - II SEM
(2017-18)
DEPARTMENT OF INFORMATION TECHNOLO
MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
(Autonomous Institution – UGC, Govt. of India)
(Affiliated to JNTUH, Hyderabad, Approved by AICTE - Accredited by NBA & NAAC – ‘A’ Grade - ISO 9001:2015 Certified)
Maisammaguda, Dhulapally (Post Via. Hakimpet), Secunderabad – 500100, Telangana State, INDIA.
DESIGN AND ANALYSIS OF ALGORITHMS Page 1
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF INFORMATION TECHNOLOGY
SYLLABUS
MALLA REDDY COLLEGE OF ENGINEERING AND
TECHNOLOGY
II Year B.Tech IT – II Sem L T /P/D C
4 -/-/- 3
(R15A0508)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 deadlines, 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.
DESIGN AND ANALYSIS OF ALGORITHMS Page 2
,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:
1. Fundamentals of Computer Algorithms, Ellis Horowitz,Satraj Sahni
and Rajasekharam,Galgotia publications pvt. Ltd.
2. Foundations of Algorithm, 4th edition, R. Neapolitan and K. Naimipour, Jones and
Bartlett Learning.
3. Design and Analysis of Algorithms, P. H. Dave, H. B. Dave, Pearson Education,
2008.
REFERENCES:
1. Computer Algorithms, Introduction to Design and Analysis, 3rd Edition, Sara Baase,
Allen, Van, Gelder, Pearson Education.
2. Algorithm Design: Foundations, Analysis and Internet examples, M. T. Goodrich and
R. Tomassia, John Wiley and sons.
3. Fundamentals of Sequential and Parallel Algorithm, K. A. Berman and J. L. Paul,
Cengage Learning.
4. Introducation to the Design and Analysis of Algorithms, A. Levitin, Pearson
Education.
5. Introducation to Algorithms, 3rd Edition, T. H. Cormen, C. E. Leiserson, R. L. Rivest,
and C. Stein, PHI Pvt. Ltd.
6. 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.
DESIGN AND ANALYSIS OF ALGORITHMS Page 3
, MALLA REDDY COLLEGE OF ENGINEERING & TECHNOLOGY
DEPARTMENT OF INFORMATION TECHNOLOGY
INDEX
S. No Topic Page no
Unit
1 Introduction to Algorithms 5
I
2 I Divide and Conquer 24
3 II Searching and Traversal Techniques 42
4 III Greedy Method 54
5 III Dynamic Programming 67
6 IV Back Tracking 102
7 IV Branch and Bound 114
8 V NP-Hard and NP-Complete Problems 133
9
DESIGN AND ANALYSIS OF ALGORITHMS Page 4
