DESIGN AND ANALYSIS OF ALGORITHM
DESIGN AND ANALYSIS OF ALGORITHM UNIT-1 Introduction: Algorithm definition, Specifications, Performance Analysis- Time Complexity, Space Complexity. Asymptotic Notations-Big-Oh, Omega, Theta. Divide and Conquer: General Method, Binary Search, Finding Maximum and Minimum, Merge Sort, Quick sort, closest pair of points. UNIT – II The Greedy Method – General Method, Knapsack Problem, Job sequencing with deadlines, Minimum-cost spanning trees, Optimal storage on tapes, Single source shortest paths, Huffman coding. UNIT – III Dynamic Programming - General method, Multistage graph, All pairs shortest path, Single Source Shortest path, Optimal Binary search trees, 0/1 Knapsack, Reliability design, the travelling salesman problem. UNIT - IV Back tracking - The General Method, The 8-Queens Problem, Sum of subsets, Graph Coloring, Hamiltonian cycles. UNIT-V Branch and Bound – General method, Job sequencing with deadlines –LC Branch and Bound, FIFO Branch and Bound and LIFO Branch an