MNIT Jaipur Syllabus computer science Design and Analysis of Algorithms
Design and Analysis of Algorithms
Algorithm Analysis: Asymptotic notation, solution of recurrence, model of computation, time and space
complexities, average and worst case analysis, Amortized analysis.
Algorithm Design Techniques: Greedy algorithm, dynamic programming, divide and conquer,
backtracking, branch and bound.
Graph Algorithms: Shortest path algorithms, Disjoint set operations, minimum spanning tree algorithm,
network flow, matching, coverings, applications of DFS:- bi-connectivity, Euler circuits, strongly
connected components, topological sort, and articulation point.
Dynamic Programming: Chained matrix multiplication, longest common subsequence.
Divide and Conquer: Order Statistics – finding the median, exponentiation, matrix multiplication, LCS.
Computational Geometry: Line segments, Optimal polygon triangulation.
Approximate Algorithm: Travelling Salesman Problem, vertex-cover problem.
Primality testing, Integer factorization, Randomized algorithms, Probabilistic algorithms.
String Matching algorithms: Rabin Karp, KMP, Boyer Moore.
Matrix Algorithms – Strassen Matrix multiplication, LUP decomposition.
Construction of codes: Shannon Fano and Huffman codes.
Introduction to problem classes – NP, NPC, NP-Hard.
1. Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India.
2. Horowitz and Sahani: Fundamental of Computer algorithms.
3. Aho A.V , J.D Ulman: Design and analysis of Algorithms, Addison Wesley 4. Brassard : Fundamental of Algorithmics, PHI.
5. W.W. Peterson and E. J. Weldon: Error correcting codes.
6. Sara Baase, Allen Van Gelder: Computer Algorithms: Introduction to Design and Analysis,