Design and Analysis of Algorithms (Cse 3-2)

Course Objectives:
 To know the importance of the complexity of a given algorithm.
 To study various algorithm design techniques.
 To utilize data structures and/or algorithmic design techniques in solving new
    problems.
 To know and understand basic computability concepts and the complexity
    classes P, NP, and NP-Complete.
 To study some techniques for solving hard problems.
Course Outcomes:
 Analyze the complexity of the algorithms
 Use techniques divide and conquer, greedy, dynamic programming,
    backtracking, branch and bound to solve the problems.
 Identify and analyze criteria and specifications appropriate to new problems, and
    choose the appropriate algorithmic design technique for their solution.
 Able to prove that a certain problem is NP-Complete.

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, Stressen ̳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
Back tracking: 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 beingin P, Cook ̳s Theorem, Reduction Source Problems,Reductions: Reductions for some known problems

Study Material's for Design & Analysis Of Algorithms

Website: Tutorial's Point
2 Mark's for all Units: Download
Lecture Notes: Unit Wise are listed below

Unit-1
Introduction, Divide & Conquer: Download

Unit-2
Greedy method : Download
Dynamic Programming: Download

Unit-3:
Basic Traversal and Search Techniques: Download
Back tracking: Download

Unit-4:
Branch and Bound:  Download
Lower Bound Theory: Download

Unit-5:
NP – Hard and NP – Complete Problems: Download