1. Introduction to Algorithm Analysis
Introduction, Analysis of Algorithms, Space Complexity, Time Complexity, Asymptotic Notations, Big Theta Notation (? ), Big oh Notation (O), Big Omega Notation (?), Little oh Notation (o), Little Omega Notation (?), Recurrences, Substitution Method, Iteration Method, Recursion Tree Method, Master Method, Sorting and Complexity, Bubble Sort, Selection Sort, Insertion Sort, Heap Sort, Counting Sort, Radix Sort, Bucket Sort, Review Questions.
2. Divide and Conquer Approach
Introduction, Binary Search, Merge Sort, Quick Sort, Strassen’s Matrix Multiplication, Properties of Matrices, Operations on Matrices, Strassen’s Matrix Multiplication, Review Questions.
3. Greedy Method
Introduction, Knapsack Problem, 0/1 Knapsack Problem, Fractional Knapsack Problem, Job Sequencing Problem, Optimal Merge Pattern, Minimal Spanning Trees, Kruskal’s Minimum Spanning Tree Algorithm, Prim’s Minimum Spanning Tree Algorithm, Review Questions.
4. Dynamic Programming
Introduction, Matrix Chain Multiplication, Longest Common Subsequence (LCS), 0/1 Knapsack Problem, Review Questions.
5. Branch and Bound
Introduction, Travelling Salesperson, Lower Bound Theory, Information Theory, Decision-tree Model, Oracles and Adversary Arguments, Problem Reduction, Review Questions.
6. Backtracking
Introduction, Queens Problem, 4-Queens Problem, 8-Queens Problem, Sum of Subsets Problem, Graph Coloring Problem, Hamiltonian Cycle Problem, Traveling Salesman Problem (TSP), Review Questions.
7. Pattern Matching
Introduction, Naive Pattern Matching Algorithm, Rabin Karp Algorithm, Knuth Morris Pratt Algorithm, Boyer Moore Algorithm, Review Questions.
8. Assignment Problem
Introduction, Formulation of Assignment Problem, Quadratic Assignment Problem (QAP), Branch and Bound-Assignment Problem, Review Questions.
9. Randomized Algorithms
Introduction, Las Vegas Algorithm, Monte Carlo Algorithm, Randomized Min Cut Algorithm, Randomized Algorithm for 2-SAT, Randomized Algorithm for N-Queens Problem, Review Questions.
10. Flow Networks
Introduction, Multi Commodity Flow, Maximum Flow Problem, The Ford-Fulkerson Method, Basic Ford-Fulkerson Algorithm, Minimum Cost Multi-Commodity Flow Problem, Flow Shop Scheduling, Permutation Flow Shop Scheduling Problem, Network Flow Assignment Problem, Review Questions.
11. NP Completeness
Introduction, Classification of Problems, NP-Hard and NP-Completeness, Cook’s Theorem, Proof of NP-Completeness, Satisfiability Problem, CLIQUE Problem, Vertex Cover Problem, Hamiltonian Cycle Problem, Traveling Salesman Problem (TSP), Approximation Algorithms, Vertex Cover Problem, Set Cover Problem, Review Questions.
S. Solutions
P. Papers