Department of Computer Science and Engineering

B.Tech. III (CO) Semester - 5

L

T

P

C

CO303 : DESIGN AND ANALYSIS OF ALGORITHMS (CS-2)

3

1

0

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)

    Introduction to algorithms, analysis and design techniques. Analysis Techniques: Mathematical, Empirical and Asymptotic analysis. Review of the notations in asymptotic analysis. Recurrence Relations and Solving Recurrences - Proof Techniques – Illustrations.

    Divide and conquer approach

    (06 Hours)

    Sorting & order statistics: Divide and Conquer technique – Various Comparison based Sorts – Analysis of the Worst-case and the Best-cases – Randomized Sorting Algorithms – Lower Bound on Sorting - Noncomparison based sorts – Applications – Medians and Order Statistics.
    Greedy design techniques

    (08 Hours)

    Basic Greedy Control Abstraction – Motivation – The Thirsty Baby Problem – Formalization – Activity Selection and its variants – Huffman Coding – Horn Formulas - The Tape Storage Problem - The Container Loading Problem – The Knapsack Problem – Graph Algorithms – Minimum Spanning Trees – Single Source Shortest Paths – Maximum Bipartite Cover Problem – Applications.

    Dynamic programming

    (08 Hours)

    Motivation – The Coin Changing problem – The Longest Common Subsequence – The 0/1 Knapscak problem – Memoization – All-pairs Shortest Path Problems - The Dynamic Programming Control Abstraction.

    Backtracking

    (04 Hours)

    Backtracking - Branch & Bound - N-Queens problem - 15-puzzle problem.

    Number theoretic algorithms

    (06 Hours)

    Number Theoretic notions – the GCD – Modular Arithmetic – The Chinese Remainder Theorem – Generators – Cyclic Groups – Galois Fields – Applications in Cryptography - The Primality Testing.

    NP-COMPLETE PROBLEMS

    (06 Hours)

    Polynomial time – verification – NP-completeness – Search Problems – The reductions – Dealing with NP-completeness – Approximation Algorithms – Local Search Heuristics.

    Tutorials will be based on the coverage of the above topics separately

    (14 Hours)
    (Total Contact Time: 42 Hours + 14 Hours = 56 Hours)

    BOOKS RECOMMENDED

    1. Cormen, Leiserson, Rivest, Stein: "Introduction to Algorithms", 3/E, the MIT Press, 2009.
    2. Knuth, Donald E. : "The Art of Computer Programming", Vol I & III, 3/E, Pearson Education, 1997
    3. Sara Baase , Allen van Gelder : "Computer Algorithms: Introduction To Design & Analysis", 3/E, Pearson Education, 2000.
    4. SartajSahni: "Data Structures, Algorithms and Applications in C++", 2/E, Universities Press/Orient Longman, 2005.
    5. J. Kleinberg, E. Tardos: "Algorithm Design", 1/E, Pearson Education, Reprint 2006.