NIT Srinagar Syllabus CSE 5th Sem
Design & Analysis of Algorithms
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.
Overview of the greedy paradigm, examples of exact optimization solution (minimum cost spanning tree), approximate solution (Knapsack problem), single source shortest paths.
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.
Overview, 8-queen problem and Knapsack problem.
Branch & Bound:
LC searching, bounding, FIFO branch and bound, Applications: 0/1 Knapsack problem, Travelling salesman problem.
Complexity measures, Polynomial vs non-polynomial time complexity; NP hard and NP complete classes, examples
- Introduction to algorithims ,Cormen,Leiserson,Rivest,Stein.