Course Details
Subject {L-T-P / C} : CS6102 : Algorithm and Computational Complexity { 3-0-0 / 3}
Subject Nature : Theory
Coordinator : Prof. Bibhudatta Sahoo
Syllabus
Algorithm and problem solving, Conventional algorithm design paradigms, Approximation Algorithms, Randomized Algorithms, Pattern matching algorithms, Lower bound Technique, Algebraic and number theoretic algorithms, Genetic Algorithms, Parallel Algorithms, Bioinformatics Algorithms
Easy and hard problems. Algorithms and complexity, Turing machines. Models of computation, Deterministic Complexity Classes, NP and NP-completeness. Non-deterministic Turing machines. Space complexity and hierarchy theorems. Optimization and approximation. Combinatorial optimisation problems. Polynomial and fully polynomial approximation schemes, Randomized Complexity
Course Objectives
- Analyze the asymptotic performance of algorithms
- Write rigorous correctness proofs for algorithms
- Apply important algorithmic design paradigms and methods of analysis.
- Synthesize efficient algorithms in common engineering design situations.
Course Outcomes
Analyze worst-case running times of algorithms using asymptotic analysis. <br />Describe the divide-and-conquer paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize divide-and-conquer algorithms. Derive and solve recurrences describing the performance of divide-and-conquer algorithms. <br />Describe the dynamic-programming paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize dynamic-programming algorithms, and analyze them. <br />Describe the greedy paradigm and explain when an algorithmic design situation calls for it. Recite algorithms that employ this paradigm. Synthesize greedy algorithms, and analyze them. <br />Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate. Synthesize new graph algorithms and algorithms that employ graph computations as key components, and analyze them. <br />Explain the different ways to analyze randomized algorithms (expected running time, probability of error). Recite algorithms that employ randomization. Explain the difference between a randomized algorithm and an algorithm with probabilistic inputs. <br />Analyze randomized algorithms. Employ indicator random variables and linearity of expectation to perform the analyses. Recite analyses of algorithms that employ this method of analysis. <br />Explain what amortized running time is and what it is good for. Describe the different methods of amortized analysis (aggregate analysis, accounting, potential method). Perform amortized analysis. <br />Explain what competitive analysis is and to which situations it applies. Perform competitive analysis. <br />Compare between different data structures. Pick an appropriate data structure for a design situation. <br />Explain what an approximation algorithm is, and the benefit of using approximation algorithms. Be familiar with some approximation algorithms, including algorithms that are PTAS or FPTAS. Analyze the approximation factor of an algorithm.
Essential Reading
- J Kleinberg, E Tardos, Algorithm Design, Addison-Wesley
- Ellis Horowitz, Sartaj Sahni and Sanguthevar Rajasekaran., Fundamentals of Computer Algorithms, University Press
Supplementary Reading
- T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein, Introduction to Algorithms, MIT Press
- M. T. Goodrich and R. Tommassia, Algorithm Design, Wiley