DAA (Design and Analysis of Algorithms)

DCRUST SYLLABUS

CSE 206C Design and Analysis of Algorithms

CATEGORY : ENGINEERING SCIENCE COURSE

Course Objectives:

1. To analyze worst-case running times of algorithms based on asymptotic analysis and justify the correctness of algorithms.
2. To apply the algorithms and design techniques to solve problems.
3. To explain the major graph algorithms and their analyses and to employ graphs to model engineering problems.
4. To understand the concepts of tractable and intractable problems and the classes P, NP and NP-complete problems.

Unit I

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.

Click on any topic to read about the topic.

Unit II

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,  Knap  Sack  TSP.  Heuristics-characteristics and their application domains.

Click on any topic to read about the topic.

Unit III

Graph  and  Tree  Algorithms:  Traversal  algorithms: Depth First Search (DFS) and Breadth First Search (BFS); Shortest path  algorithms,  Transitive  closure,  Minimum  Spanning  Tree, Topological sorting, Network Flow Algorithm.

Click on any topic to read about the topic.

Unit IV

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.

Advanced Topics: Approximation algorithms, Randomized algorithms, Class of problems beyond NP – P SPACE

Click on any topic to read about the topic.

TEXT BOOKS:

1. Introduction to  Algorithms,  4TH  Edition,  Thomas H  Cormen, MIT Press/McGraw-Hill.Fundamentals of Algorithms – E. Horowitz et al.

REFERENCE BOOKS:

1. Algorithm  Design,   1ST   Edition,   Jon   Kleinberg   and ÉvaTardos, Pearson.
2. Algorithm  Design:  Foundations,  Analysis,  and  Internet Examples, Second Edition, Michael T Goodrich and Roberto Tamassia, Wiley.
3. Algorithms   — A   Creative Approach, 3^RD Edition, UdiManber, Addison-Wesley, Reading, MA.

Course  Outcomes: After successful completion of the course students will be able to:

1. Analyze worst-case running times of algorithms based on asymptotic analysis and justify the correctness of algorithms.
2. Apply the algorithms and design techniques to solve problems;
3. Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, 
4. Understand the concepts of tractable and intractable problems and the classes P, NP and NP-complete problems.