NIT Srinagar Syllabus CSE 5th Sem Design & Analysis of Algorithms

NIT Srinagar Syllabus CSE 5th Sem

Design & Analysis of Algorithms

Introduction:

Algorithm Design paradigms- motivation, concept of algorithmic efficiency, run time analysis of algorithms, Asymptomatic Notations.

Divide & Conquer:
Structure of divide and conquer algorithms: examples, Binary search, Quick sort, analysis of divide and conquer run time reference relations.

Greedy method:
Overview of the greedy paradigm, examples of exact optimization solution (minimum cost spanning tree), approximate solution (Knapsack problem), single source shortest paths.

Dynamic Programming:
Overview, difference between dynamic programming and divide and conquer, applications: shortest path in graph, matrix multiplication, travelling salesman problem, longest common sequence.

Graph searching and traversal:
Overview, traversal methods, depth first and breadth first search.

Back Tracking:
Overview, 8-queen problem and Knapsack problem.

Branch & Bound:
LC searching, bounding, FIFO branch and bound, Applications: 0/1 Knapsack problem, Travelling salesman problem.

Computational complexity:
Complexity measures, Polynomial vs non-polynomial time complexity; NP hard and NP complete classes, examples

Books Recommended:

  1. Introduction to algorithims ,Cormen,Leiserson,Rivest,Stein.

Leave a Comment