Syllabus of Analysis of Algorithms
1 Answer

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, Strassen‟s 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 prim‟s 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 naïve 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
Please log in to add an answer.

Continue reading...

The best way to discover useful content is by searching it.