Department of Computer Science & Engineering

M.Tech. I (CO) Semester - 1

L

T

P

C

CO603: ALGORITHMS AND COMPUTATIONAL COMPLEXITY   

3

0

2

4
COURSE OBJECTIVES
  • To teach paradigms and approaches used to analyze and design algorithms and to appreciate the impact of algorithm design in practice.
  • To make students understand how the worst-case time complexity of an algorithm is defined, how asymptotic notation is used to provide a rough classification of algorithms.
  • To explain different computational models (e.g., divide-and-conquer), order notation and various complexity measures (e.g., running time, disk space) to analyze the complexity/performance of different algorithms.
  • To teach various advanced design and analysis techniques such as greedy algorithms, dynamic programming & Know the concepts of tractable and intractable problems and the classes P, NP and NP-complete problems.
    		•
    COURSE OUTCOMES
    After successful completion of this course, student will be able to
    • Analyze the asymptotic performance of algorithms.
    • Write rigorous correctness proofs for algorithms.
    • Demonstrate a familiarity with major algorithms and data structures.
    • Apply important algorithmic design paradigms and methods of analysis.
    • Synthesize efficient algorithms in common engineering design situations.
    COURSE CONTENT
    INTRODUCTION

    (04 Hours)

    Review of the Algorithmic - Terminologies - Computability Theory, Computational Complexity - Abstract Machines; Asymptotic Analysis - Basic notations - Recurrences and Mathematical Background.
    ALGORITHM DESIGN TECHNIQUES AND ANALYSIS

    (10 Hours)

    Algorithmic paradigms: Divide-and-Conquer, Dynamic Programming, Greedy, Branch -and-bound; Amortized analysis.
    GRAPH ALGORITHMS

    (06 Hours)

    Shortest paths, Minimum Spanning Trees - Flow networks - Bipartite Matching - Applications.
    COMPLEXITY THEORY

    (10 Hours)

    NP-completeness - Complexity Classes. NP and co-NP, Reductions; Results on structure of NP - complete sets, Sparse NP-hard sets, Basic Inclusions and Separations, Nondeterministic Space Classes, Logarithmic Space, A PSPACE complete problem, Polynomial Hierarchy.
    SPECIAL TOPICS

    (12 Hours)

    Advanced Numerical algorithms, Introduction to Internet algorithms, Introduction to App roximation algorithms; Randomized algorithms.

    (Total Contact Time: 42 Hours)
    PRACTICALS
    1. Empirical Analysis of the Algorithms and Problem Solutions discussed in the class and evaluating the same against the asymptotic analysis
    2. Solving and implementing the problems as given in the assignments based on the algorithms discussed in the class.
    3. Mini-projects to be carried out implementing the simulation of the algorithms discussed in the class..
    BOOKS RECOMMENDED
    1. Thomas H. Cormen, Charles E. Leiserson, Ron ald L. Rivest, and Cliff Stein," Introduction to Algorithms", 2/E, MIT Press and MGH, 2001.
    2. Jan van Leeuwen, ed. Handbook of Theoretical Computer Science, Volume A," Algorithms and Complexity", The MIT Press/Elsevier, 1990.
    3. Garey, M. R. and Johnson, D. S, "Computers and Intractability: A Guide to the Theory of NP - Completeness", W.H. Freeman, New York., 1979.
    4. Lewis, H. R. and Papadimitriou, C. H., "Elements of the Theory of Computation", 2/E,Prentice - Hall, 1997.
    5. Sipser, M, "Introduction to the Theory of Compu tation", PWS-Kent, 1997.