Analysis and Design of Algorithms

Back

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.  

Back