Analysis & Design Of Algorithms Short BookADA Notes(Lecture Wise) 28/10/2012
Uploaded by: MYcsvtu Notes ADA Complete lecture note 25/07/2012
Shared by: praveen rathore(SSEC)
Shared by: Rohit Sharma(BIT, Durg)
Analysis & Design Of Algorithms1. Unit-1 28/10/2012
Uploaded by: MYcsvtu Notes 2. Unit-2
3. Unit-3
4. Unit-4
5. Unit-5
|
Analysis & Design Of Algorithms SyllabusUNIT-I INTRODUCTION & ANALYSIS: - Analyzing algorithms, Algorithm types, Recurrence Equations, Growth function: Asymptotic notation, Standard notation & common functions, Recurrence relation, different methods of solution of recurrence equations with examples. UNIT-II-DYNAMIC PROGRAMMING & GREEDY PARADIGM: - The basic dynamic programming paradigm, Dynamic programming solution to the optimal matrix chain multiplication and the longest common subsequence problems, Top down recursive algorithms, Greedy Paradigm: The basic greedy strategy & computing minimum spanning trees, Algorithms of Kruskal and Prim, Union to Find Algorithm & their applications, Disjoint Set, The relationship in Dijkstra’s and Prim’s algorithms, Use of greedy strategy in algorithms for the Knapsack problem and Huffman trees. UNIT-III-DIVIDE AND CONQUER & BACKTRACKING PARADIGM: - Introduction to Divide and Conquer paradigm, Quick and merge sorting techniques, Linear time selection algorithm, the basic divide and conquer algorithm for matrix multiplication, Backtracking & Recursive backtracking, Applications of backtracking paradigm. heaps and introduction to 2-3 trees, Algorithms for manipulating 2-3 trees, Representation of heaps using 2-3 trees, Red Black tree, Binary Search tree , heap sort, shell & bucket sort, Amortized Analysis. UNIT-IV-GRAPH ALGORITHMS & STRING MATCHING ALGORITHMS: - Representational issues in graphs, Depth first search & Breath first search on graphs, Computation of biconnected components and strongly connected components using DFS, Topological sorting of nodes of an acyclic graph & applications, Shortest Path Algorithms on Graphs: Bellman-Ford algorithm, Dijkstra’s algorithm & Analysis of Dijkstra’s algorithm using heaps, Floyd-Warshall’s all pairs shortest path algorithm and its refinement for computing the transitive closure of a graph. The general string problem as a finite automata, Knuth Morris and Pratt algorithms, Linear time analysis of the KMP algorithm, The Boyer-Moore algorithm. UNIT-V-NP-COMPLETE PROBLEMS:- Solvable problems, Types of problems, The notion of a non deterministic algorithm and its basic relationship to backtracking. Polynomial time non deterministic algorithms for problems like satisfiability, clique problem, Hamiltonian path problems etc., The definition of NP-hardness and NP-completeness, The statement of Cook’s theorem and a discussion of its implications, The notion of polynomial transformation and reductions, Reductions to show that the clique problem, vertex cover, subset sum and Hamiltonian cycle problems are NP-complete, Other models for computations. |