DESIGN AND ANALYSIS OF ALGORITHMS

(Common to CSE & ISE)

Subject Code: 10CS43 I.A. Marks : 25

Hours/Week : 04 Exam Hours: 03

Total Hours : 52 Exam Marks: 100

PART – A

UNIT – 1                                                                                                                                    7 Hours

INTRODUCTION: Notion of Algorithm, Review of Asymptotic Notations,Mathematical Analysis of Non-Recursive and Recursive Algorithms Brute Force Approaches: Introduction, Selection Sort and Bubble Sort,Sequential Search and Brute Force String Matching.
UNIT - 2                                                                                                                                     6 Hours
DIVIDE AND CONQUER: Divide and Conquer: General Method,Defective Chess Board, Binary Search, Merge Sort, Quick Sort and its performance.
UNIT - 3                                                                                                                                     7 Hours
THE GREEDY METHOD: The General Method, Knapsack Problem, Job Sequencing with deadlines, Minimum-Cost Spanning Trees: Prim’s Algorithm, Kruskal’s Algorithm; Single Source Shortest Paths.
UNIT - 4                                                                                                                                      6 Hours
DYNAMIC PROGRAMMING: The General Method, Warshall’s Algorithm, Floyd’s Algorithm for the All-Pairs Shortest Paths Problem, Single-Source Shortest Paths: General Weights, 0/1 Knapsack, The Traveling Salesperson problem.

PART – B

UNIT - 5                                                                                                                                      7 Hours
DECREASE-AND-CONQUER APPROACHES, SPACE-TIME TRADEOFFS: Decrease-and-Conquer Approaches: Introduction, Insertion Sort, Depth First Search and Breadth First Search, Topological Sorting Space-Time Tradeoffs: Introduction, Sorting by Counting, Input
Enhancement in String Matching.
UNIT – 6                                                                                                                                     7 Hours
LIMITATIONS OF ALGORITHMIC POWER AND COPING WITH THEM: Lower-Bound Arguments, Decision Trees, P, NP, and NP-Complete Problems, Challenges of Numerical Algorithms.
UNIT - 7                                                                                                                                     6 Hours
COPING WITH LIMITATIONS OF ALGORITHMIC POWER:Backtracking: n - Queens problem, Hamiltonian Circuit Problem, Subset –Sum Problem. Branch-and-Bound: Assignment Problem, Knapsack Problem, Traveling Salesperson Problem.Approximation Algorithms for NP-Hard Problems – Traveling Salesperson Problem, Knapsack Problem
UNIT – 8                                                                                                                                      6 Hours
PRAM ALGORITHMS: Introduction, Computational Model, Parallel Algorithms for Prefix Computation, List Ranking, and Graph Problems.

Text Books:
1. Anany Levitin: Introduction to The Design & Analysis of Algorithms, 2nd Edition, Pearson Education, 2007. (Listed topics only from the Chapters 1, 2, 3, 5, 7, 8, 10, 11).
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran: Fundamentals of Computer Algorithms, 2nd Edition, Universities Press, 2007. (Listed topics only from the Chapters 3, 4, 5, 13)
Reference Books:
1. Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein: Introduction to Algorithms, 3rd Edition, PHI, 2010.
2. R.C.T. Lee, S.S. Tseng, R.C. Chang & Y.T.Tsai: Introduction to the Design and Analysis of Algorithms A Strategic Approach, Tata McGraw Hill, 2005.