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 Sanket Shingote ★ 270
Please log in to add an answer.