Analysis and Design of algorithm

PART -A

UNIT 1: Introduction to Algorithm

1.1  Algorithm analysis

1.2  Problem solving approach

1.3  Asymptotic analysis

1.4  Analysis of Non-recursive and Recursive Algorithm

1.5   Sets and disjoint sets union

UNIT 2: Divide and Conquer approach

2   

2.1  Introduction to Divide and Conquer approach

2.2  Binary search

2.3  Merge sort

2.4  Quick sort

2.5  Selection sort

2.6  Stassen’s matrix multiplication algorithms

UNIT 3: Greedy Method

3.1  Introduction to Greedy Method

3.2  Knapsack problem

3.3  Job sequencing with dead lines

3.4  Minimum Spanning Trees: Kruskal and Prim’s method

3.5  Single source shortest paths (Dijesktra’s algorithm).

PART-B

UNIT 4: Dynamic Programming

4   

4.1  General method

4.2  Optimal binary search trees

4.3   0/1 knapsack

4.4  Traveling salesperson problem

UNIT 5: Backtracking

5   

5.1  General Method

5.2  8 queen’s problem

5.3  Graph colouring

5.4  Hamiltonian cycles

5.5   Introduction to Branch and Bound approach

5.6   0/1 knapsack

5.7    Traveling salesperson problem.

UNIT 6: Problem Classes

6   

6.1  Polynomial and Non Polynomial classes

6.2  NP-hard and NP-complete

6.3  Deterministic and non-deterministic polynomial time algorithms,

6.4   Cook’s theorem

6.5   NP scheduling problems.