Unit I Introduction Proof Techniques : Contradiction, Mathematical Induction, Direct proofs, Proof by counter example, Proof by contraposition. Analysis of Algorithm : Efficiency - Analysis framework, asymptotic notations – big O, theta and omega. Analysis of Non-recursive and recursive algorithms : Solving Recurrence Equations using Masters theorem and Substitution method. Brute Force method : Introduction to Brute Force method & Exhaustive search, Brute Force solution to 8 queens’ problem. (Chapters - 1, 2) Unit II Divide and Conquer and Greedy Method Divide & Conquer : General method, Quick Sort - Worst, Best and average case. Binary search, Finding Max-Min, Large integer Multiplication (for all above algorithms analysis to be done with recurrence). Greedy Method : General method and characteristics, Kruskal’s method for MST (using nlogn complexity), Dijkstra’s Algorithm, Fractional Knapsack problem, Job Sequencing, Max flow problem and Ford-Fulkerson algorithm in transport network. (Chapters - 3, 4) Unit III Dynamic Programming General strategy, Principle of optimality, 0/1 knapsack Problem, Coin change-making problem, Bellman - Ford Algorithm , Multistage Graph problem(using Forward computation), Travelling Salesman Problem. (Chapter - 5) Unit IV Backtracking General method, Recursive backtracking algorithm, Iterative backtracking method. n-Queen problem, Sum of subsets, Graph coloring, 0/1 Knapsack Problem. (Chapter - 6) Unit V Branch and Bound The method, Control abstractions for Least Cost Search, Bounding, FIFO branch and bound, LC branch and bound, 0/1 Knapsack problem - LC branch and bound and FIFO branch and bound solution, Traveling salesperson problem - LC branch and bound. (Chapter - 7) Unit VI Computational Complexity Non Deterministic algorithms, The classes : P, NP, NP Complete, NP Hard, Satisfiability problem, Proofs for NP Complete Problems : Clique, Vertex Cover. (Chapter - 8)
