Syllabus - Design And Analysis of Algorithms (CB-402)

Computer Science and Business System

Design And Analysis of Algorithms (CB-402)

IV

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.

Fundamental Algorithmic Strategies

Brute-Force, Heuristics, Greedy, Dynamic Programming, Branch and Bound and Backtracking methodologies; Illustrationsof these techniques for Problem-Solving, Bin Packing, Knapsack, Travelling Salesman Problem.

Graph and Tree Algorithms

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

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, Introduction to Quantum Algorithms.

Practicals

Reference Books

  • Fundamental of Computer Algorithms, E. Horowitz and S. Sahni.

  • The Design and Analysis of Computer Algorithms, A. Aho, J. Hopcroft and J. Ullman.

  • Introduction to Algorithms, T. H. Cormen, C. E. Leiserson and R. L. Rivest.

  • Computer Algorithms: Introduction to Design and Analysis, S. Baase.

  • The Art of Computer Programming, Vol. 1, Vol. 2 and Vol. 3, .D. E. Knuth.

  • Quantum Computation and Quantum Information, Michael A. Nielsen and Isaac L. Chuang.