III B.E. (Computer Engg.)

VI SEMESTER

6CP3 -DESIGN AND ANALYSIS OF ALGORITHMS

1. BACKGROUND: Review of Algorithm Complexity and Or Notations, Sorting Methods - Heap Sort, Radix Sort, Bucket Sort Counting Sorts.

2. DIVIDE AND CONQUER METHOD: Binary Search, Merge Quick Sort and Strasen's Matrix Multiplication.

3. GREEDY METHOD: Knapsack Problem, Job Sequencing. Option Merge Patterns and Minimal Spanning Trees.

4. DYNAMIC PROGRAMMING: Matrix Chain Multiplication. Longest Common Subsequence and 0/1 Knapsack Problem.

5. BRANCH AND BOUND: Traveling Salesman Problem and Lower Bound Theory.

6. PATTERN MATCHING ALGORITHMS: KMP Matcher and Boyer Moor.: Algorithms.

7. PROBLEM CLASSES NP, NP-HARD AND NP; COMPLETE: Definitions of P.NP-Hard and NP-Complete Problems. Decision Problem Cook's Theorem. Proving NP-Complete Problems -Satisfiability Problem and Vertex Cover Problem. Approximation Algorithms for Vertex C and Set Cover Problem.

8. INTRODUCTION TO ASSIGNMENT PROBLEMS: Formulation of Assignment Problem, Quadratic Assignment and Biquadratic Assignment Problems. Branch and Bound Method for Solving Assignment Problems (not of Quadratic or Biquadratic Assignment Problem).

9. FORMULATIONS OF MULTI COMMODITY FLOW (MCF) PROBLEMS: Min-Cost Multi commodity Flow Problem, Max-Flow Multi commodity Flow Problem, Integer Multi commodity Flow Problems. Introduction to Flow Shop Scheduling and Network Capacity Assignment Problems (No algorithms).

 Recommended Book:

1. Aho A. V. J.E. Hopcroft, J.D. Ullman: Design and Analysis of Algorithms, Pearson Education.

2. Rivest and COrlilen, Introduction to Algorithms, Prentice Hall of India.

3. Haase, Computer Algorithms, pearson Education.

4. Brassard, Algorithmics, Prentice Hall.

5. Bazaraa, Linear Programming & Network Flows, John Wiley &. Sons.