Analysis of Algorithms
5IT4-05 · Semester 5
0/45 topics
Objective
Scope
Outcome
Review of algorithm
Complexity order notation definitions
Calculating complexity
Divide and conquer method
Binary search
Merge sort
Quick sort
Strassen's matrix multiplication algorithm
Knapsack problem
Job sequencing
Optimal merge patterns
Minimal spanning trees
Matrix chain multiplication
Longest common subsequence
0/1 Knapsack problem
Traveling Salesman Problem
Lower bound theory
Backtracking algorithms
N-Queens problem
Naïve string matching algorithm
Rabin-Karp string matching algorithm
KMP matcher
Boyer-Moore algorithm
Formulation of assignment problem
Quadratic assignment problem
Las Vegas algorithms
Monte Carlo algorithms
Randomized algorithm for Min-Cut
Randomized algorithm for 2-SAT
Multicommodity flow problem definition
Flow shop scheduling
Network capacity assignment problems
Definition of P problems
Definition of NP-Hard problems
Definition of NP-Complete problems
Decision problems
Cook's Theorem
Proving NP-Complete problems
Satisfiability problem
Vertex Cover problem
Approximation algorithm for Vertex Cover problem
Approximation algorithm for Set Cover problem