**1. Introduction to analysis of algorithm**

Performance analysis , space and time complexity
Growth of function - Big - Oh ,Omega , Theta notation
Mathematical background for algorithm analysis,
Analysis of selection sort , insertion sort.

**Recurrences:**

- The substitution method
- Recursion tree method
- Master method

**Divide and Conquer Approach:**

General method
Analysis of Merge sort, Analysis of Quick sort, Analysis of Binary search,
Finding minimum and maximum algorithm and analysis, Strassens matrix
multiplication

**2. Dynamic Programming Approach:**

- General Method
- Multistage graphs
- single source shortest path
- all pair shortest path
- Assembly-line scheduling
- 0/1 knapsack
- Travelling salesman problem
- Longest common subsequence

**3. Greedy Method Approach:**

- General Method
- Single source shortest path
- Knapsack problem
- Job sequencing with deadlines
- Minimum cost spanning trees-Kruskal and prims algorithm
- Optimal storage on tapes

**4. Backtracking and Branch-and-bound:**

- General Method
- 8 queen problem( N-queen problem)
- Sum of subsets
- Graph coloring
- 15 puzzle problem,
- Travelling salesman problem.

**5. String Matching Algorithms:**

- The naive string matching Algorithms
- The Rabin Karp algorithm
- String matching with finite automata
- The knuth-Morris-Pratt algorithm

**6. Non-deterministic polynomial algorithms:**

- Polynomial time,
- Polynomial time verification
- NP Completeness and reducibility
- NP Completeness proofs
- Vertex Cover Problems
- Clique Problems