The document outlines the course structure for 'Design & Analysis of Algorithms' for B.Tech 4th semester students, detailing objectives, modules, and outcomes. Key topics include algorithm performance analysis, fundamental algorithmic strategies, graph and tree traversal algorithms, and the classification of problems. The course aims to equip students with the skills to analyze, design, and implement efficient algorithms in various engineering contexts.
The document outlines the course structure for 'Design & Analysis of Algorithms' for B.Tech 4th semester students, detailing objectives, modules, and outcomes. Key topics include algorithm performance analysis, fundamental algorithmic strategies, graph and tree traversal algorithms, and the classification of problems. The course aims to equip students with the skills to analyze, design, and implement efficient algorithms in various engineering contexts.
The document outlines the course structure for 'Design & Analysis of Algorithms' for B.Tech 4th semester students, detailing objectives, modules, and outcomes. Key topics include algorithm performance analysis, fundamental algorithmic strategies, graph and tree traversal algorithms, and the classification of problems. The course aims to equip students with the skills to analyze, design, and implement efficient algorithms in various engineering contexts.
The document outlines the course structure for 'Design & Analysis of Algorithms' for B.Tech 4th semester students, detailing objectives, modules, and outcomes. Key topics include algorithm performance analysis, fundamental algorithmic strategies, graph and tree traversal algorithms, and the classification of problems. The course aims to equip students with the skills to analyze, design, and implement efficient algorithms in various engineering contexts.
L T P THEORY EXAM: 75 3 0 0 TOTAL : 100 Pre-requisites: Data Structures and Algorithms
Course Objectives: 1. Analyze the asymptotic performance of algorithms. 2. Write rigorous correctness proofs for algorithms. 3. Demonstrate a familiarity with major algorithms and data structures. 4. Apply important algorithmic design paradigms and methods of analysis. 5. Synthesize efficient algorithms in common engineering design situations.
MODULE-1: INTRODUCTION Characteristics of algorithm, Analysis of algorithm: Asymptotic analysis of complexity bounds – best, average and worst-case behavior; Performance measurements of Algorithm, Time and space trade-offs, Analysis of recursive algorithms through recurrence relations: Substitution method, Recursion tree method and Masters’ theorem. MODULE-2: FUNDAMENTAL ALGORITHMIC STRATEGIES Brute-Force, Greedy, Dynamic Programming, Branch and-Bound and backtracking methodologies for the design of algorithms; Illustrations of these techniques for Problem-Solving, Bin Packing, Knapsack, Job sequencing with deadline, Optimal Binary Search tree, N-Queen problem, Hamiltonian Cycle, TSP, Heuristics – characteristics and their application domains. MODULE-3:GRAPH AND TREE TRAVERSAL ALGORITHMS Depth First Search (DFS) and Breadth First Search (BFS); Shortest path algorithms, Transitive closure, Minimum Spanning Tree, Topological sorting, Network Flow Algorithm. MODULE-4:TRACTABLE AND INTRACTABLE PROBLEMS Computability of Algorithms, Computability classes – P, NP, NP-complete and NP-hard, Cook’s theorem, Standard NP-complete problems and Reduction techniques.
MODULE-5:ADVANCED TOPICS
45 | P a g e Approximation algorithms, Randomized algorithms, Class of problems beyond NP – P SPACE
Course Outcomes: 1. For a given algorithms analyze worst-case running times of algorithms based on asymptotic analysis and justify the correctness of algorithms. 2. Describe the greedy paradigm and explain when an algorithmic design situation calls for it. For a given problem develop the greedy algorithms. 3. Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Synthesize divide-and-conquer algorithms. Derive and solve recurrence relation. 4. Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. For a given problems of dynamic-programming and develop the dynamic programming algorithms, and analyze it to determine its computational complexity. 5. For a given model engineering problem model it using graph and write the corresponding algorithm to solve the problems. 6. Explain the ways to analyze randomized algorithms (expected running time, probability of error). 7. Explain what an approximation algorithm is. Compute the approximation factor of an approximation algorithm (PTAS and FPTAS).
REFERENCES
1. Thomas H Cormen, Charles E Lieserson, Ronald L Rivest and Clifford Stein, “Introduction to Algorithms”, MIT Press/McGraw-Hill; 3rd edition, [ISBN: 978-0262533058], 2009. 2. Ellis Horowitz, Sartaj Sahni and SanguthevarRajasekaran, “Fundamentals of Algorithms”, Universities Press; 2nd edition [ISBN:978-8173716126],2008. 3. Jon Kleinberg and ÉvaTardos, “Algorithm Design”, Pearson Publisher; 1st edition [ISBN:978-0321295354],2012. 4. Michael T Goodrich and Roberto Tamassia, “Fundamentals of Algorithms” Wiley Press; 1st edition [ISBN:978-8126509867],2006.
