B. Tech. - Analysis and Design Algorithm
Module I: Introduction: Algorithm Design paradigms - motivation, concept of algorithmic efficiency, run time analysis of algorithms, Asymptotic Notations. Recurrences- substitution method, recursion tree method, master method
Module II: Divide and Conquer: Structure of divide-and-conquer algorithms: examples; Binary search, quick sort, Merge sort, Strassen matrix multiplication; Run time analysis of divide and conquer and recurrence 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 problems, trav:eling salesman problem
Module III:Dynamic Programming: Overview, difference between dynamic programming and divide and conquer technique, Applications: Shortest path in graph, chain matrix multiplication, Traveling salesman Problem, longest Common sequence problem, knapsack problem
Module IV:Graph Searching and Traversal: Overview, Representation of graphs, strongly connected components, Traversal methods (depth first and breadth first search) and its analysis
Back tracking: Overview, 8-queen problem, and Knapsack problem Brach and bound: LC searching Bounding, FIFO branch and bound, LC branch and bound application: 0/1 Knapsack problem, Traveling Salesman Problem
Module V: Computational Complexity: Complexity measures, Polynomial Vs non-polynomial time complexity; NP-hard and NP-complete classes, examples.