Analysis And Design Of Algorithms (3150703)

Unit-1:  Basics of Algorithms and Mathematics

What is an algorithm?, Mathematics for Algorithmic Sets, Functions and Relations, Vectors and Matrices, Linear Inequalities and Linear Equations.

Unit-2:  Analysis of Algorithm

The efficient algorithm, Average, Best and worst case analysis, Amortized analysis , Asymptotic Notations, Analyzing control statement, Loop invariant and the correctness of the algorithm, Sorting Algorithms and analysis: Bubble sort, Selection sort, Insertion sort, Shell sort Heap sort, Sorting in linear time : Bucket sort, Radix sort and Counting sort

Unit-3:  Divide and Conquer Algorithm

Introduction, Recurrence and different methods to solve recurrence, Multiplying large Integers Problem, Problem Solving using divide and conquer algorithm - Binary Search, Max-Min problem, Sorting (Merge Sort, Quick Sort), Matrix Multiplication, Exponential.

Unit-4:  Dynamic Programming

Introduction, The Principle of Optimality, Problem Solving using Dynamic Programming – Calculating the Binomial Coefficient, Making Change Problem, Assembly Line-Scheduling, Knapsack problem, All Points Shortest path, Matrix chain multiplication, Longest Common Subsequence.

Unit-5:  Greedy Algorithm

General Characteristics of greedy algorithms, Problem solving using Greedy Algorithm - Activity selection problem, Elements of Greedy Strategy, Minimum Spanning trees (Kruskal’s algorithm, Prim’s algorithm), Graphs: Shortest paths, The Knapsack Problem, Job Scheduling Problem, Huffman code.

Unit-6:  Exploring Graphs

An introduction using graphs and games, Undirected Graph, Directed Graph, Traversing Graphs, Depth First Search, Breath First Search, Topological sort, Connected components.

Unit-7:  Backtracking and Branch and Bound

Introduction, The Eight queens problem , Knapsack problem, Travelling Salesman problem, Minimax principle

Unit-8:  String Matching

Introduction, The naive string matching algorithm, The Rabin-Karp algorithm, String Matching with finite automata, The Knuth-Morris-Pratt algorithm.

Unit-9:  Introduction to NP-Completeness

The class P and NP, Polynomial reduction, NP- Completeness Problem, NP-Hard Problems. Travelling Salesman problem, Hamiltonian problem, Approximation algorithms

Sr.	Title	Author	Publication	Amazon Link
1	Introduction to Algorithms	Thomas H. Cormen, Charles E. Leiserson, Ronald L.	PHI
2	Fundamental of Algorithms	Gills Brassard, Paul Bratley	PHI
3	Introduction to Design and Analysis of Algorithms	Anany Levitin	Pearson
4	Foundations of Algorithms	Shailesh R Sathe	Penram
5	Design and Analysis of Algorithms	Dave and Dave	Pearson

After learning the course the students should be able to:
1. Analyze the asymptotic performance of algorithms.
2. Derive and solve recurrences describing the performance of divide-and-conquer algorithms.
3. Find optimal solution by applying various methods.
4. Apply pattern matching algorithms to find particular pattern.
5. Differentiate polynomial and nonpolynomial problems.
6. Explain the major graph algorithms and their analyses. Employ graphs to model engineering problems, when appropriate.