Contents

1. Introduction

2. Algorithm Definition and Characteristics of Algorithm

3. Performance Analysis

3.1 Requirement for a General Analysis Methodology

3.2 Pseudo - Code

4. Space Complexity

5. Time Complexity

6. Counting Primitive Operation

7. Algorithm Analysis Notations / Asymptotic Notation

7.1 The “Big-Oh” Notation

7.2 Big Omega Notation

7.3 Big Theta Notation

8. Types of Algorithm

9. Sorting Algorithm- In non linear Time (Insertion Sort, Heap Sort, Bubble Sort)

9.1 Insertion Sort

9.2 Heap Sort

9.3 Bubble Sort

10. Sorting in Linear Time

10.1 Counting Sort

10.2  Radix Sort

10.3 Bucket Sort

11. Searching Algorithms

11.1 Linear Search

2. Divide and Conquer

1. Introduction

2. Divide and Conquer - Control Abstract

3. Binary Search

4. Merge Sort

5. Quick sort

6. Comparison between Traditional Method of Matrix Multiplication vs Strassen’s Matrix Multiplication

3. Greedy Method

1. Introduction

1.1 Elements of the Greedy Strategy

1.2 Control Abstraction

2. Knapsack Problem

3. Job Sequencing with Deadlines

4. Minimum Spanning Tree

4.1 Kruskal’s Algorithm

4.2 Prim’s Algorithm

5. Optimal Storage on Tapes

6. Huffman Codes

7. Optimal Merge Patterns

4. Dynamic Programming

1. Introduction

2. Principle of Optimality

3. Matrix-Chain Multiplication

4. 0/1 Knapsack Problem (Using Function Method)

4.1  0/1 Knapsack Problem (Merge and Purge Method)

5. Concept of Shortest Path-Algorithm

6. Single Source Shortest Path

6.1 Dijkstra’s Algorithm

6.2 Bellman Ford Algorithm

7. All Pairs Shortest Paths (Floyd Warshall’s Algorithm)

8. Longest Common Subsequence (LCS)

9. String Editing

10. The Travelling Salesperson Problem

5. Decrease and Conquer

1. Definition of Graph and Representation of Graph

2. Graph Traversal

2.1 Depth First Search (DFS)

2.2 Breadth First Search (BFS)

3. Topological Sort

4. Strongly Connected Components

5. By Variable Size Decrease Euclid's Algorithm

6. Networks and Flows

6.1 Ford Fulkerson Algorithm

7. Articulation Point and Bridge Edge

6. Backtracking

1. Introduction

2. General method

3. n-queen problem

3.1 4-Queens

3.2 The 8-Queen’s Problem

4. Graph Coloring Problem

5. Sum of Subsets Problem

5.1 Rules for Generating State Space Tree

5.2 Bounding Functions for Sum of Subset

6. Hamiltonian Cycles

7. Branch and Bound

1. Introduction

2. Least Count (LC) Search

3. 0/1 Knapsack Problem

4. Bounding Function

5. Ranking Function

6. Travelling Salesperson Problem (TSP)

8. Problem Classification

1. Introduction

2. Non-Deterministic Algorithms

3. Preliminary Issues

3.1 Input Size what we mean

3.2 Advantages: Polynomial

3.3 Decision Problems and Optimization Problems

4. The Class P, NP, NP-hard, NP-Complete Problems

4.1 P-Class

4.2 NP-Class

4.3 NP-Completeness

4.4 Polynomial Time Reducibility and NP-hardness

5. Cook’s Theorem