Analysis And Design Of Algorithms (3150703)

 

Examination Scheme (in Marks)
Theory ESE (E)	Theory PA (M)	Practical ESE Viva (V)	Practical PA(I)	Total
70	30	30	20	150

 

Teaching Scheme (in Hours)
Theory	Tutorial	Practical	Total
4	0	2	6

 Subject Credit : 5

Syllabus Content

Unit-1: Basic 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 queen’s 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

 

 

 

Reference Books

Index	Title	Author	Publication	Link
1	Foundation of Algorithms	SHAILESH R SATHE	PENRAM	https://amzn.to/3fJzAPZ
2	Introduction to Design and Analysis of Algorithms	Anany Levitin	PEARSON	https://amzn.to/3hPtzE7
3	Introducing to Algorithms	Thomas H. Cormen, Charles E. Leiserson, Ronald L.	PHI	https://amzn.to/2SmJDm0
4	Design and Analysis of Algorithms	DAVE AND DAVE	PEARSON	https://amzn.to/3oULyui
5	Fundamental of Algorithms	Gills Brassard, Paul Brarley	PHI	https://amzn.to/34lI0Yx