6CS2 DESIGN AND ANALYSIS OF ALGORITHMS (Comp. Engg.) |
|
|---|---|
| Units | Contents of the subjects |
| BACKGROUND: Review of Algorithm Complexity, Order Notations: definitions and calculating complexity. DIVIDE AND CONQUER METHOD: Binary Search, Merge Sort, Quick sort and Strassen's matrix multiplication algorithms. GREEDY METHOD: Knapsack Problem, Job Sequencing, Optimal Merge Patterns and Minimal Spanning Trees. | |
| DYNAMIC PROGRAMMING: Matrix Chain Multiplication. Longest Common Subsequence and 0/1 Knapsack Problem. BRANCH AND BOUND: Traveling Salesman Problem and Lower Bound Theory. Backtracking Algorithms and queens problem. | |
| PATTERN MATCHING ALGORITHMS: Naïve and Rabin Karp string
matching algorithms, KMP Matcher and Boyer Moore Algorithms. ASSIGNMENT PROBLEMS: Formulation of Assignment and Quadratic Assignment Problem. |
|
| RANDOMIZED ALGORITHMS. Las Vegas algorithms, Monte Carlo
algorithms, randomized algorithm for Min-Cut, randomized algorithm for 2- SAT. Problem definition of Multicommodity flow, Flow shop scheduling and Network capacity assignment problems. |
|
| PROBLEM CLASSES NP, NP-HARD AND NP-COMPLETE: Definitions of P, NP-Hard and NP-Complete Problems. Decision Problems. Cook's Theorem. Proving NP-Complete Problems - Satisfiability problem and Vertex Cover Problem. Approximation Algorithms for Vertex Cover and Set Cover Problem. PROBLEM CLASSES NP, NP-HARD AND NP-COMPLETE: Definitions of P, NP-Hard and NP-Complete Problems. Decision Problems. Cook's Theorem. Proving NP-Complete Problems - Satisfiability problem and Vertex Cover Problem. Approximation Algorithms for Vertex Cover and Set Cover Problem. | |
Text/References:
1. Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India.
2. Horowitz and Sahani: Fundamental of Computer algorithms.
3. Aho A.V , J.D Ulman: Design and analysis of Algorithms, Addison Wesley