View all subjects

## Analysis of Algorithms

Students studying Computer Science will find this subject very useful. Hundreds of important topics on Analysis of Algorithms are organized neatly into lessons below.

### Overview

#### Topics Covered

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 ...

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
• 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