Design and Analysis of Algorithms

Below is the syllabus for Design and Analysis of Algorithms:-


Unit 1


Review:  Elementary Data Structures, Algorithms & its complexity(Time & Space), Analysing Algorithms, Asymptotic Notations, Priority Queue, Quick Sort and merge sort.

Recurrence relation: Methods for solving recurrence(Substitution, Recursion tree, Master theorem), Strassen multiplication.

Advanced data Structures:  Binomial heaps, Fibonacci heaps, Splay Trees, Red-Black Trees.


Unit 2

Advanced Design and Analysis Techniques

Dynamic programming: Elements, Matrix-chain multiplication, longest common subsequence,

Greedy algorithms: Elements, Activity- Selection problem, Huffman codes, Task scheduling problem, Travelling Salesman Problem.

Backtracking algorithms: Graph coloring, N-Queen problem, Hamiltonian path, and circuit.


Unit 3

Graph Algorithms

Review of graph algorithms: Traversal Methods(Depth-first & Breadth-first search), Topological sort, Strongly connected components, Minimum spanning trees- Kruskal’s and Prim’s Algorithm, Single-source shortest paths, Relaxation, Dijkstra’s Algorithm, Bellman-Ford algorithm, Single-source shortest paths for directed acyclic graphs,  Floyd-Warshall algorithm.


Unit 4

Computational Complexity: Basic Concepts, Polynomial vs Non-Polynomial Complexity, NP-hard & NP-complete classes. Flow and Sorting Networks,  Flow networks, Ford- Fulkerson method, Maximum bipartite matching, Sorting Networks, Comparison network, Zero- one principle, Bitonic sorting network, merging network


Text Books:

  1. Corman, Leiserson, and Rivest: Introduction to Algorithms, 2/e, PHI
  2. Harsh Bhasin, Algorithms: Design And Analysis Oxford University Press,2015.


Reference Books:

  1. Aho, Hopcroft, and Ullman: The Design and Analyses of Computer Algorithms. Addison Wesley.
  2. B.Patel, Expert Data Structures with C, Khanna Publications, Delhi, India, 2ndEdition 2004, ISBN 81-87325-07-0, pp.1-909.
  3. B.Patel & M.M.S Rauthan, Expert Data Structures with C++, Khana Publications, Delhi, India, 2ndEdition 2004, ISBN: 87522-03-8.
  4. Horowitz, Ellis and Sahni, Sartaj: Fundamentals of Computer Algorithms, Galgotia Publications

Below is the link to download Design and Analysis of Algorithms notes.

Related Links

    • Automata Theory (PDF Notes) – Click Here
    • Computer Networks (PDF Notes) – Click Here
    • Computer Organization and Architecture (PDF Notes) – Click Here
    • Simulation and Modelling (PDF Notes) – Click Here
    • Technical Communication (PDF Notes) – Click Here