Course Code: MIT208 |
Course Title: Analysis and design of Algorithms (4 Credits) |
Course Contents
Unit-1: Introduction to Algorithms: Concept of Algorithm, The role of algorithm in computing, Fundamentals of Algorithm, Important Types of Algorithm, Fundamental Data Structures.
Unit-2: Fundamentals of the Analysis of Algorithm Efficiency: Introduction Analysis Framework, Methodologies for Analyzing Algorithms, Amortization, Case Studies in Algorithm Analysis.
Unit-3: Mathematical aspects and Analysis of Algorithms: Asymptotic Notations and Basic Efficiency Classes, Mathematical Analysis of Non recursive Algorithms.
Unit -4: Mathematical aspects and Analysis of Algorithms-2: Mathematical Analysis of Recursive Algorithms, empirical Analysis of Algorithms, Algorithm visualization.
Unit-5: Brute Force Method: Brute Force, Selection Sort and Bubble Sort, Sequential Search and Brute-Force String Matching, Exhaustive Search.
Unit 6: Divide and Conquer: Introduction, Merge sort, Quick sort, Binary Search, Binary tree traversals and related properties, Stressen’s Matrix Multiplication.
Unit 7: Decrease and Conquer: Concepts of Decrease and Conquer, Insertion Sort, Depth First Search, Breadth First Search, Topological Sorting, Algorithms for Generating Combinatorial Objects.
Unit 8: Transform and Conquer: Presorting, Gaussian Elimination, Balanced Search Trees, Heaps and Heap sort, Problem Reduction.
Unit 9: Space and Time Tradeoffs: Sorting, Input Enhancement in String Matching, Hashing, Methodology, Indexing Schemes.
Unit 10: Dynamic programming-1: Overview of Dynamic Programming, Fibonacci numbers, Binomial coefficient, Warshall’s and Floyd’s Algorithms.
Unit 11: Dynamic programming-2: Principle of Optimality, Optimal binary search trees, knapsack problem, memory functions.
Unit 12: Greedy Technique: Introduction to Greedy Technique, Prim’s Algorithm, Kruskal’s Algorithm, Dijkstra’s Algorithm, Huffman Trees.
Unit 13: Limitations of Algorithm Power: Lower-Bound Arguments, Decision Trees, P, NP and NP-Complete Problems.
Unit 14: Coping with the Limitations of Algorithm Power: Backtracking, Branch and Bound, Approximation Algorithms for NP-Hard Problems.