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.

Add to your library

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

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
Read less