DESIGN AND ANALYSIS OF ALGORITHMS

Topic: DESIGN AND ANALYSIS OF ALGORITHMS

Sem: 4

Syllabus:
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).
3rd edition: Click here to download 1

2nd edition: Click to download 2

Solution manual : Download

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)
----------------------------------------------------------------------------------------