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² , 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:

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