About This Course

Course Objectives

I. To familiarize with algorithm design strategies.
II. To learn to analyse and measure the performance of algorithms

Expected Outcome

1. Given a problem, the student will be able to design algorithms.
II. Given an algorithm, he/she will be able to analyse it and produce an estimate of its time and space requirements.

References

1. A. Levitin, “Introduction to the Design and Analysis of Algorithms”, Pearson Education, 3rd Edition (2008).
2. Ellis Horowitz, Sartaj Sahni, Sanguthevar Rajasekaran, “Fundamentals of Computer Algorithms”, Orient Longman, Universities Press, 2nd Edition (2008)
3. Harsh Bhasin, “Algorithms Design and Analysis”, Oxford University Press, 1st Edition (2015).
4. Rajesh K.Shukla, “Analysis and Design of Algorithms, A Beginner’s Approach”, Wiley (2015)
5. Richard Neapolitan , Kumarss Naimipour, “Foundations Of Algorithms “,Jones and Bartlett Publishers, Inc, 4th Edition (2011).
6. Sara Baase , Allen Van Gelder , “Computer Algorithms: Introduction to Design and Analysis”, Pearson India, 3rd Edition (2002).
7. Thomas H. Cormen, et al., “Introduction to Algorithms”, Prentice Hall, 3rd Edition (2010)

Module I: Introduction to Algorithm Analysis :
Algorithm and its properties - Apriory and Aposterior analysis of algorithms - Time and Space Complexity- Elementary Operation and Complexity Estimation of Simple Algorithms - Asymptotic notations and their properties - Common Complexity functions - Recurrence Relations - Solution of Recurrence Relations - Iteration Method - Recurrence Tree Method - Master's Theorem (Proof not required)

Module II: Divide and Conquer Method :
Control Abstraction for Divide and Conquer- 2- way Merge Sort , Quick sort, Binary Search, Finding Maximum and minimum, Divide and Conquer Matrix Multiplication.

ModuleIII: Greedy Strategy: -
Control Abstraction for Greedy Strategy - The Fractional Knapsack Problem - Prims' and Kruskal's Algorithms for Minimal Spanning Tree - Job Sequencing Problem.

Module IV: Dynamic Programming :
Control Abstraction for Dynamic Programming - The Principle of Optimal Substructure - All Pair Shortest Path Problem - Travelling Sales Person Problem, Divide and Conquer vs Dynamic Programming.

Module V: Algorithm Design by State Space Trees: State Space - Bounding Functions – Examples. Backtracking: Control Abstraction for Backtracking - The NQueen's Problem, Sum of Subset Problem. Branch and Bound: Depth First, Breadth First and Best First Branch and Bound strategies and their control abstractions - The N2-1 Puzzle Problem

Module VI: Introduction to Computational Complexity:
Tractable and Intractable Problems - Complexity Classes- P and NP Classes - SAT and 3-SAT Problems - NP-Hard and NP-Complete Classes – Study of NP complete problems - Travelling Sales Person Problem - Knapsack Problem - Clique Problem, Vertex Cover Problem.