Syllabus Design and Analysis of Algorithms - (AD3351) UNIT I INTRODUCTION Notion of an Algorithm - Fundamentals of Algorithmic Problem Solving - Important Problem Types - Fundamentals of the Analysis of Algorithm Efficiency - Analysis Framework - Asymptotic Notations and their properties - Empirical analysis - Mathematical analysis of Recursive and Non-recursive algorithms - Visualization. (Chapter - 1) UNIT II BRUTE FORCE AND DIVIDE AND CONQUER Brute Force - String Matching - Exhaustive Search - Traveling Salesman Problem - Knapsack Problem - Assignment problem. Divide and Conquer Methodology - Multiplication of Large Integers and Strassen’s Matrix Multiplication - Closest-Pair and Convex - Hull Problems. Decrease and Conquer : - Topological Sorting - Transform and Conquer : Presorting - Heaps and Heap Sort. (Chapter - 2) UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE Dynamic programming - Principle of optimality - Coin changing problem - Warshall’s and Floyd‘s algorithms - Optimal Binary Search Trees - Multi stage graph - Knapsack Problem and Memory functions. Greedy Technique - Dijkstra’s algorithm - Huffman Trees and codes - 0/1 Knapsack problem. (Chapter - 3) UNIT IV ITERATIVE IMPROVEMENT The Simplex Method - The Maximum-Flow Problem - Maximum Matching in Bipartite Graphs - The Stable marriage Problem. (Chapter - 4) UNIT V LIMITATIONS OF ALGORITHM POWER Lower - Bound Arguments - P, NP, NP- Complete and NP Hard Problems. Backtracking - N-Queen problem - Hamiltonian Circuit Problem - Subset Sum Problem. Branch and Bound - LIFO Search and FIFO search - Assignment problem - Knapsack Problem - Traveling Salesman Problem - Approximation Algorithms for NP-Hard Problems - Traveling Salesman problem - Knapsack problem. (Chapter - 5)
