Design and Analysis of Algorithms

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

Unit 1

Introduction

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.