MNIT Jaipur Syllabus computer science Design and Analysis of Algorithms

 

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.

Text/References:

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,

Pearson Education.

Leave a Comment