Page: Syllabus of Book of Analysis of Algorithms
0

As per Choice Based Grading System


Module 01: 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

Module 02: 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

Module 03 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

Module 04: Backtracking and Branch-and-bound:

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

Module 05: String Matching Algorithms:

  • The naïve string matching Algorithms
  • The Rabin Karp algorithm
  • String matching with finite automata
  • The knuth-Morris-Pratt algorithm

Module 06: Non-deterministic polynomial algorithms:

  • Polynomial time,
  • Polynomial time verification
  • NP Completeness and reducibility
  • NP Completeness proofs
  • Vertex Cover Problems
  • Clique Problems
page • 51 views
ADD COMMENTlink
written 6 months ago by gravatar for Sanket Shingote Sanket Shingote270
Please log in to add an answer.