**SIXTH SEMESTER**

**Department: Computer Science and Engineering**

**Course code: CST 307**

**Course Name: Design & Analysis of Algorithm**

Prerequisite: discrete mathematics and probability, Data Structure

Contact Hours and type of course: 4 hours/week (Lecture, Tutorial)

Course Assessment Methods: Test1, Test2 Teacher Assessment, End semester exam

** **

**Course Outcomes**

S.No |
Coursee Outcome |
Unit |

1 | Ability to understand mathematical formulation, complexity analysis and methodologies to solve recurrence relations for algorithms. |
Unit 1, 2 |

2 | Ability to design algorithms using standard paradigms like: Greedy, Divide and Conquer, Dynamic Programming and Backtracking. |
Unit 3, 4, 5 |

3 | Ability to design algorithms using advance data structures and implement traversals techniques. |
Unit 2, 5 |

4 | Ability to understand NP class problems and formulate solutions using standard approaches. |
Unit 6 |

5 | Ability to apply algorithm design principles to derive solutions for real life problems and comment on complexity of solution. |
Unit 1,2,3,4,5,6 |

**Topics: **

**UNIT-I**:

Mathematical foundations, summation of arithmetic and geometric series, n, n^{2} , bounding summations using integration, recurrence relations, solutions of recurrence relations using technique of characteristic equation and generating functions, Complexity calculation of various standard functions, principles of designing algorithms

**UNIT-II**:

Asymptotic notations of analysis of algorithms, analyzing control structures, worst case and average case analysis, amortized analysis, application of amortized analysis, Sorting networks, comparison networks, bio-tonic sorting network.

**UNIT-III: ****Part-I**

**Greedy Algorithms: Contents**

Introduction to Greedy algorithm and basic principle

Examples:

Knapsack problem: Principle, numerical example, algorithm, complexity calculation, Minimum Cost Spanning Tree:

Prims Algorithm, Reverse Delete Algorithm

Single source shortest path algorithm:Dijkastra Algorithm, Optimized Dijkastra [Dial Algorithm]

Job Sequencing Problem: [Assignment on case study]

Maximum Flow Problem: Theory, numerical, example and application, Water Connection Problem: Theory, numerical, example, algorithm and application

Methodology to compute complexity of algorithm with each topic

**Part-II**

**Divide and Conquer: Contents**

Introduction to Divide and Conquer and basic principle

Examples:

Min-Max problem: Principle, example, algorithm, complexity, Quick Sort: Example, complexity equation

Matrix multiplication: Strassen’s Algorithm, Median of two sorted arrays

Closest pair algorithm: Case study and discussion on solution [Assignment on case study]

**UNIT-IV**:

Introduction to dynamic programming and basic principle

Examples:

Longest common sub-sequence and Longest increasing sub-sequence: Theory, example, algorithm, complexity

Optimal Binary Search Tree: Theory, example, application, algorithm, complexity

Minimum Edit Distance: Theory, example, application

Travelling Salesman problem: Theory, example, application

Multi-stage graph: Theory, example, algorithm, application, complexity

Coin Change problem: Theory, application, example

Maximum Sum Rectangle in 2D array: Theory, example [Assignment on case study]

**UNIT-V:**

**Part-I: Basic Traversal Techniques:**

Introduction and need of traversal techniques on trees and graphs

Articulation point in a Graph

Applications of DFS and BFS [Cloud computing preview]

Application of Inorder, preorder and postorder traversals [Big data preview]

**Part-II: Backtracking: **

Introduction, principle and need of backtracking

Example:

Sum of Subset, N-Queen, and Graph coloring: Principle, example, algorithm

Pattern matching without using regular expression

**UNIT-VI**:

NP-hard and NP-complete problems, basic concepts, non-deterministic algorithms, NP-hard and NP-complete, decision and optimization problems, graph based problems on NP Principle.

**Text Books:**

- Thomas H. Cormen et.al. “Introduction to Algorithms”, Prentice Hall of India.
- Horowitz, Sahani, Rajsekharam, “Computer Algorithms”, Galgotia Publications Pvt. Ltd.
- Brassard, Bratley, “Fundamentals of Algorithms”, Prentice Hall
- Richard Johnsonbaugh, “Algorithms”, Pearson Publication.