22PCSCC11:
DESIGN AND ANALYSIS OF ALGORITHMS
UNIT
I
Introduction: Algorithm Definition–Algorithm
Specification–Performance Analysis-Asymptotic Notations. Elementary Data Structures:
Stacks and Queues– Trees–Dictionaries – Priority Queues–Sets and Disjoint Set
-Union–Graphs
UNIT
II
Divide and Conquer: The General Method – Defective Chessboard
–Binary Search – Finding the Maximum and Minimum – Merge Sort –Quick Sort –
Selection-Stassen’s Matrix Multiplication.
UNIT
III
The Greedy Method: General Method-Container Loading-Knapsack
Problem-Tree Vertex Splitting–Job Sequencing With Deadlines-Minimum Cost
Spanning Trees- Optimal Storage On Tapes–Optimal Merge Patterns-Single Source
Shortest Paths.
UNIT
IV
Dynamic Programming: The General Method – Multistage Graphs
–All-Pairs Shortest Paths–Single-Source Shortest Paths-Optimal Binary Search
Trees-String Editing-0/1Knapsack- Reliability Design - The Traveling
Salesperson Problem - Flow Shop Scheduling. Basic Traversal and Search
Techniques: Techniques for Binary Trees –Techniques for Graphs–Connected
Components and Spanning Trees–Bi connected Components and DFS.
UNIT
V
Backtracking: The General Method – The 8-Queens Problem – Sum of
Subsets–Graph Coloring–Hamiltonian Cycles–Knapsack Problem Branch and Bound:
Least Cost searchhod-0/1Knapsack Problem.
Text Books
1. Ellis Horowitz, Satraj
Sahni and Sanguthevar Rajasekaran, Fundamentals of Computer Algorithms,
Universities Press, Second Edition, Reprint 2009.
CLICK TO DOWNLOAD THE SYLLABUS IN PDF
.jpg)
No comments:
Post a Comment