Design and Analysis of Algorithm

Contents

1. Introduction  

1. Introduction  

2. Asymptotic Notations (O,W,q)    

3. Tower of Hanoi

2. Elementary Data Structures

1. Introduction  

2. Heaps and Heap Sort 

3. Sets and Disjoint Set     

4. Union and Find Operations 

5. Sorting in Linear Time    

3. Divide and Conquer  

1. Divide and Conquer  

2. General Strategy    

4. Greedy Method 

1. General Strategy    

2. Job Sequencing with Deadlines   

3. Optimal Merge Patterns    

4. Minimal Spanning Trees    

5. Dynamic Programming 

1. Introduction  

2. General Strategy    

3. Multistage Graph    

4. Optimal Binary Search Tree (OBST)     

5. 0/1 Knapsack  

6. Travelling Salesperson Problem  

7. Flow Shop Scheduling

6. Backtracking  

1. Introduction  

2. Backtracking General Strategy   

3. N-Queen’s Problem   

4. Graph Coloring

5. Hamiltonian Cycle   

6. 0/1 knapsack Problem

7. Branch and Bound    

1. Introduction

2. General Strategy    

3. 0/1 Knapsack Problem

4. Travelling Salesperson Problem (TSP)  

8. NP-Hard and NP-Complete Problems

1. Introduction  

2. Basic Concepts

3. P Vs NP Problems    

4. Non-deterministic Algorithms    

5. Decision Problem Vs Optimization Problem    

6. The Classes NP-Hard and NP-Complete