TAMILNADU COLLEGE OF ENGINEERING, COIMBATORE
DEPARTMENT OF ARTIFICIAL INTELLIGENCE AND DATA
SCIENCE
AD3351 DESIGN AND ANALYSIS OF ALGORITHM LTPC
3 0 24
COURSE OBJECTIVES:
To critically analyze the efficiency of alternative algorithmic solutions for the same problem
• To illustrate brute force and divide and conquer design techniques.
• To explain dynamic programming and greedy techniques for solving various problems.
• To apply iterative improvement technique to solve optimization problems
• To examine the limitations of algorithmic power and handling it in different problems.
UNIT I INTRODUCTION 8
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.
UNIT II BRUTE FORCE AND DIVIDE AND CONQUER 10
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.
UNIT III DYNAMIC PROGRAMMING AND GREEDY TECHNIQUE
10
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.
UNIT IV ITERATIVE IMPROVEMENT
8
The Simplex Method-The Maximum-Flow Problem – Maximum Matching in Bipartite Graphs- The
Stable marriage Problem.
UNIT V LIMITATIONS OF ALGORITHM POWER 9
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.
TOTAL: 45 PERIODS
PRACTICAL EXERCISES: 30PERIODS
1. Implement recursive and non-recursive algorithms and study the order of growth from log2n to n!.
2. Divide and Conquer - Strassen’s Matrix Multiplication
3. Decrease and Conquer - Topological Sorting
4. Transform and Conquer - Heap Sort
5. Dynamic programming - Coin change Problem, Warshall’s and Floyd‘s algorithms, Knapsack Problem
6. Greedy Technique – Dijkstra’s algorithm, Huffman Trees and codes
7. Iterative improvement - Simplex Method
8. Backtracking – N-Queen problem, Subset Sum Problem 9. Branch and Bound - Assignment problem,
Traveling Salesman Problem
TOTAL: 75 PERIODS
TEXT BOOK:
[Link] Levitin, Introduction to the Design and Analysis of Algorithms, Third Edition, Pearson
Education, 2012.
REFERENCES
[Link] Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran, Computer Algorithms/ C++, Second
Edition, Universities Press, 2019.
2. Thomas [Link], Charles [Link], Ronald L. Rivest and Clifford Stein, Introduction to
Algorithms, Third Edition, PHI Learning Private Limited, 2012.
3. S. Sridhar, Design and Analysis of Algorithms, Oxford university press, 2014.
4. Alfred V. Aho, John E. Hopcroft and Jeffrey D. Ullman, Data Structures and Algorithms, Pearson
Education, Reprint 2006.