AD8351 - Design and Analysis of Algorithms Syllabus

AD8351 -DESIGN & ANALYSIS OF ALGORITHM

COURSE OBJECTIVES

 To understand and apply the algorithm analysis techniques.
 To critically analyze the efficiency of alternative algorithmic solutions for the same problem
 To understand and implement different algorithm design techniques.
 To understand the limitations of Algorithmic power

UNIT I INTRODUCTION AND ANALYSIS - 9 Hours

Introduction: Fundamentals of algorithmic Problem solving – Important problem types; Recursive algorithms, -- Fundamentals of the Analysis of Algorithm Efficiency: Analysis framework -- Asymptotic notations and basic complexity classes – recurrences – case studies

UNIT II DIVIDE-AND-CONQUER AND GREEDY STRATEGIES - 9 Hours

Divide and Conquer strategy -- Mergesort -- Quicksort -- Multiplication of large integers and Strassen's matrix multiplication – closest pairs Greedy strategy – Huffman coding – shortest paths algorithms –minimum-cost spanning tree algorithms –disjoint sets

UNIT III DYNAMIC PROGRAMMING AND STATE-SPACE APPROACH - 9 Hours

Dynamic Programming: Computing binomial coefficient – Knapsack problem and memory functions – ordering of matrix multiplications -- Warshall's and Floyd's algorithm State-space approach – exhaustive search: DFS, BFS, Iterative deepening

UNIT IV BACKTRACKING, ITERATIVE IMPROVEMENT, AND BRANCH & BOUND - 9 Hours

Backtracking and permutations – N-queens problem – Hamilton circuits – best-first search -- Iterative Improvement: Stable marriage -- Maximum matching in bipartite graphs – maximum flow -- Branch and Bound: Knapsack problem -- Traveling salesman problem

UNIT V INTRACTABILITY - 9 Hours

Introduction to intractability -- Polynomial reductions – SAT and 3-SAT – NP-complete and NPHard problems -- Approximation algorithms: Traveling salesman problem -- Knapsack problem – Introduction to randomized and parallel algorithms

THEORY PERIODS: 45

SUGGESTIVE EXERCISES

1. Implementation of iterative and recursive algorithms for the given problem
2. Empirical analysis of algorithms
3. Implementation of divide-and-conquer sorting algorithms
4. Implementation of closest-pairs algorithm
5. Implementation of Huffman coding
6. Implementation of Dijkstra’s and Prim’s algorithms
7. Implementation of disjoint sets and Kruskal’s algorithm
8. Implementation of dynamic programming algorithm for knapsack problem
9. Implementation of backtracking to solve n-Queens and Hamilton circuits problems
10. Implementation of iterative improvement strategy for stable marriage and maxflow problems
11. Implementation of Branch and Bound technique to solve knapsack and TSP problems
12. Implementation of approximation algorithms for knapsack and TSP problems

PRACTICAL PERIODS: 30

TOTAL PERIODS: 75

OUTCOMES:

At the end of the course, the students should be able to:

 Design algorithms for various computing problems.
 Analyze the time and space complexity of algorithms.
 Critically analyze the different algorithm design techniques for a given problem.
 Modify existing algorithms to improve efficiency
 Ability to implement techniques in solving real time problems

TEXT BOOKS

1. Anany Levitin, ``Introduction to the Design and Analysis of Algorithms'', 3rd Edition, Pearson Education, 2012.
2. Jon Kleinberg and Eva Tardos, ``Algorithm Design’’, Pearson Education, 2006.

REFERENCES

1. Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stein, ``Introduction to Algorithms'', 3rd Edition, PHI Learning Private Limited, 2012.
2. Steven S Skiena, ``The Algorithm Design Manual'', 2nd Edition, Springer, 2008.
3. S Dasgupta, C H Papadimitriou, U V Vazirani,``Algorithms'',1st Edition, McGraw Hill Education, 2017.
4. S. Sridhar, “Design and Analysis of Algorithms”, Oxford University Press, 2015.
5. Sara Baase and Allen Van Gelder, Computer Algorithms, Third Edition, Pearson Education,2000.
6. Dexter C. Kozen, The Design and Analysis of Algorithms, Springer-Verlag, 1992.

>>>>Click here to Download<<<<