Contents

1. Analysis of Algorithms

1.1 INTRODUCTION    

1.2 Performance Analysis

1.3 Asymptotic Notation   

1.4 Space Complexity

1.5 Sorting in Linear Time

1.6 Sorting Algorithms (Insertion Sort, Heap Sort)

1.7 Recursive algorithms (Permutations) 

2. Divide and Conquer

2.1 Introduction    

2.2 Divide and Conquer – Control Abstract   

2.3 Merge Sort

2.4 Quick sort

2.5 Strassen’s Matrix Multiplication  

2.6 Binary Search   

3. Greedy method

3.1 Introduction    

3.2 Knapsack Problem

3.3 Job Sequencing with Deadlines

4. Minimum Cost Spanning trees

4.1 Minimum Spanning Tree 

4.2 Optimal Storage on Tapes    

4.3 Huffman Codes   

4.4 Optimal Merge Patterns 

5. Dynamic Programming

5.1 Introduction    

5.2 Matrix–Chain Multiplication 

5.3 SINGLE SOURCE SHORTEST PATH 

5.4 All Pairs Shortest paths    

5.5 Ford Fulkerson Algorithm    

5.6 Longest Common Subsequence (LCS)  

5.7 String Editing  

5.8 The Travelling Salesperson Problem

5.9 0/1 Knapsack

6. Decrease and Conquer

6.1 Introduction    

6.2 Graph Traversal 

6.3 Topological Sort

6.4 Strongly Connected Components 

7. Backtracking

7.1 Introduction

7.2 The 8–Queen’s Problem

7.3 Sum of Subsets Problem

7.4 Graph Coloring Problem

7.5 Hamiltonian Cycles

8. Branch And Bound Techniques

8.1 Introduction

8.2 LC Search

8.3 0/1 Knapsack Problem

8.4 Travelling Salesperson Problem (TSP)

9. Transform And Conquer

9.1 Introduction    

9.2 Presorting

9.3 Gaussian Elimination  

9.4  AVL Trees

9.5  Horner’s rule and Binary Exponentiation

9.6 Problem Reduction

10. Problem Classification

10.1 Introduction

10.2 Non–Deterministic Algorithms

10.3 Preliminary Issues

10.4 Defining the Classes NP–Hard and NP–Complete

10.5 Cook’s Theorem