MNIT Jaipur Syllabus Information Technology Design and Analysis of Algorithms

 

 

 

MNIT Jaipur Syllabus Information Technology  Design and Analysis of Algorithms

 

 

 

 

Design and Analysis of Algorithms

 Review of Algorithms: Seaching and Sorting, Tree and Graph traversal. DFS and its applications.

Shortest path algorithms, minimum spanning tree algorithm. Algorithm Design Techniques: Greedy

algorithm, dynamic programming, divide and conquer, backtracking, branch and bound.

Algorithm Analysis: Asymptotic notation, solution of recurrence, model of computation, time and space

complexities,  average  and  worst  case  analysis,  Amortized  analysis.  Master’s  theorem.  Recurrence

solving.

Graph Algorithms: network flow, matching, coverings, applications of DFS:- bi-connectivity, Euler

circuits, strongly connected components, topological sort, and articulation point. Network Flow.

Greedy Algorithms: Knapsack problem.

Dynamic Programming: Chained matrix multiplication, longest common subsequence.

Divide and Conquer: Order Statistics – finding the median, exponentiation, matrix multiplication, LCS.

Approximate Algorithm: Travelling Salesman Problem, vertex-cover problem.

Randomized Algorithms:

Matrix Algorithms – Strassen Matrix multiplication, LUP decomposition.

Number Theoretic Algorithms: Primality Testing, Factorization.

Miscellaneous: Introduction to appoximate, randomized and probabilistic algorithms.

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