Analysis and Design of Algorithms

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.