Design and Analysis of Algorithms(314455)

Unit I Introduction

Analysis of Algorithm Efficiency:- Analysis framework – Asymptotic notations – Analysis of Non-recursive and recursive algorithms. Amortized Analysis, Writing characteristic Polynomial equations, Solving Recurrence Equations, Proof Techniques: by Contradiction, by Mathematical Induction, direct proofs, proof by counterexample, proof by contraposition.

Unit II Divide and Conquer and The Greedy Method

Characteristic; Analysis Methodology:- Merge sort – Quick Sort – Binary

search – Large integer Multiplication and Strassen’s Matrix multiplicationclosest

pair and convex Hull problems

The Greedy Method : General characteristics of greedy algorithms, Prim’s

and kruskal’s Algorithms, Dijkstra’s Algorithm, Huffman Trees.

Unit III Dynamic Programming

General strategy, Principle of optimality, Warshall’s and Floyd’s Algorithm – Optimal Binary Search Trees – knapsack Problem

Unit IV Backtracking

General method— Recursive backtracking algorithm, iterative backtracking method. 8-queens problem, sum of subsets and Graph coloring, Hamiltonian cycle and Knapsack Problem.

Unit V Branch-Bound

The method, Least Cost Search, FIFO branch and bound, LC branch and bound. 0/1 Kanpsack problem –LC branch and bound and FIFO branch and bound solution. Traveling sales person problem.

Unit VI NP-Hard and NP-Complete Problems

Basic concepts, Non deterministic Algorithms, The classes of NP hard and

NP complete, Cooks Theorem.

NP-Complete problems- Satisfiability problem, vertex cover problem.

NP-Hard problems-graph, scheduling, code generation problems, Simplified NP hard Problems.

Text Books:

1. Anany Levitin,’Introduction to the Design & Analysis of Algorithm Pearson ISBN 81-7758-835-4

2. Horowitz and Sahani, "Fundamentals of computer Algorithms", Galgotia. ISBN 81-7371-

612-9

Reference Books:

1. Thomas H Cormen and Charles E.L Leiserson, "Introduction to Algorithm" PHI, ISBN:81-203-2141-3

2. Gilles Brassard, Paul Bratley— Fundamentals of Algorithms , Pearson ISBN 978-81-317-1244-3