Module-1
INTRODUCTION: What is an Algorithm?, Fundamentals of Algorithmic Problem Solving.
FUNDAMENTALS OF THE ANALYSIS OF ALGORITHM EFFICIENCY: Analysis Framework, Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non recursive Algorithms, Mathematical Analysis of Recursive Algorithms.
BRUTE FORCE APPROACHES: Selection Sort and Bubble Sort, Sequential Search and Brute Force String Matching.
Chapter 1 (Sections 1.1,1.2),
Chapter 2(Sections 2.1,2.2,2.3,2.4),
Chapter 3(Section 3.1,3.2)
Module-2
BRUTE FORCE APPROACHES (contd..): Exhaustive Search (Travelling Salesman problem and Knapsack Problem).
DECREASE-AND-CONQUER: Insertion Sort, Topological Sorting.
DIVIDE AND CONQUER: Merge Sort, Quick Sort, Binary Tree Traversals, Multiplication of Large Integers and Strassen’s Matrix Multiplication.
Chapter 3(Section 3.4),
Chapter 4 (Sections 4.1,4.2),
Chapter 5 (Section 5.1,5.2,5.3, 5.4)
Module-3
TRANSFORM-AND-CONQUER: Balanced Search Trees, Heaps and Heapsort.
SPACE-TIME TRADEOFFS: Sorting by Counting: Comparison counting sort, Input Enhancement in String Matching: Horspool’s Algorithm.
Chapter 6 (Sections 6.3,6.4),
Chapter 7 (Sections 7.1,7.2)
Module-4
DYNAMIC PROGRAMMING: Three basic examples, The Knapsack Problem and Memory Functions, Warshall’s and Floyd’s Algorithms.
THE GREEDY METHOD: Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees and Codes.
Chapter 8 (Sections 8.1,8.2,8.4),
Chapter 9 (Sections 9.1,9.2,9.3,9.4)
Module-5
LIMITATIONS OF ALGORITHMIC POWER: Decision Trees, P, NP, and NP-Complete Problems.
COPING WITH LIMITATIONS OF ALGORITHMIC POWER: Backtracking (n-Queens problem, Subset-sum problem), Branch-and-Bound (Knapsack problem), Approximation algorithms for NP-Hard problems (Knapsack problem).
Chapter 11 (Section 11.2, 11.3),
Chapter 12 (Sections 12.1,12.2,12.3)
Textbooks
Introduction to the Design and Analysis of Algorithms, By Anany Levitin, 3rd Edition (Indian), 2017, Pearson.
Reference books
Computer Algorithms/C++, Ellis Horowitz, SatrajSahni and Rajasekaran, 2nd Edition, 2014, Universities Press.
Introduction to Algorithms, Thomas H. Cormen, Charles E. Leiserson, Ronal L. Rivest, Clifford Stein, 3rd Edition, PHI.
Design and Analysis of Algorithms, S. Sridhar, Oxford (Higher Education)
Course outcome (Course Skill Set)
At the end of the course, the student will be able to:
Apply asymptotic notational method to analyze the performance of the algorithms in terms of time complexity.
Demonstrate divide & conquer approaches and decrease & conquer approaches to solve computational problems.
Make use of transform & conquer and dynamic programming design approaches to solve the given real world or complex computational problems.
Apply greedy and input enhancement methods to solve graph & string based computational problems.
Analyse various classes (P,NP and NP Complete) of problems 6. Illustrate backtracking, branch & bound and approximation methods.