Contents

• 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