Verify Account

SYLLABUS

Unit-I

Introduction: What is an Algorithm, Algorithm Specification, Performance Analysis. Divide and Conquer: General Method, Binary Search, Finding the Maximum and Minimum, Merge Sort, Quick Sort, Selection Sort, Strassen’s Matrix Multiplication.

Unit-II

Greedy Method: General Method, Knapsack Problem, Job Scheduling with Deadlines, Minimum Cost Spanning Trees, Optimal Storage on Tapes, Single-source Shortest Paths. Dynamic Programming: General Method, Multistage Graphs, All-pairs Shortest Paths, Optimal Binary Search Trees, 0/1 Knapsack, The Traveling Sales Person Problem.

Unit-III

Basic Traversal and Search Techniques: Techniques for Binary Trees, Techniques for Graphs, Connected Components and Spanning Trees, Bi-connected Components and DFS. Backtracking: General Method, 8-queens Problem, Sum of Subsets Problem, Graph Coloring and Hamiltonian Cycles, Knapsack Problem.

Unit-IV

Branch and Bound: The Method, Travelling Salesperson, 0/1 Knapsack Problem, Efficiency Considerations. Lower Bound Theory: Comparison Trees, Lower Bounds Through Reductions – Multiplying Triangular Matrices, Inverting a Lower Triangular Matrix, Computing the Transitive Closure.

Unit-V

NP-Hard and NP-Complete Problems: NP Hardness, NP Completeness, Consequences of Being in P, Cook’s Theorem, Reduction Source Problems, Reductions: Reductions for some known Problems.