Design and Analysis of Algorithms

Contents

1. Basics of Algorithms

1. Algorithms

1.1 History of Algorithms

1.2 Types of Algorithms

2. Space Complexity and Time Complexity

3. Asymptotic Notations (O, Omega, Theta)

3.1 O (Big “oh”)

3.2 Big Omega

3.3 Big Theta

4. Sorting Algorithms: Insertion Sort, Heap Sort, Bubble Sort

4.1 Sorting in Non-linear Time

4.2 Sorting in Linear Time

5. Searching Algorithms: Linear, Binary

2. Divide and Conquer Strategy

1. Introduction

2. Control Abstraction

3. Binary Search

4. Merge Sort

5. Quick Sort

6. Strassen’s Matrix Multiplication

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

8. MaxMin Algorithm

9. Writing Simple Algorithms using D and C Strategy

10. Convex Hull Algorithm

3. Greedy Method

1. Introduction

2. Job Sequencing/Scheduling with Deadlines

3. Minimum Cost Spanning Trees

4. Optimal Storage on Tapes

5. Generalization of Tape Storage Problem

6. Optimal Merge Patterns

7. Huffman Coding    

8. Shortest Path: Dijjstra’s Algorithm

4. Dynamic Programming

1. Introduction

2. Principle of Optimality

3. Matrix Chain Multiplication

3.1 Method to Find Matrix Chain Multiplication

4. 0|1 Knapsack with Function Method

4.1 0|1 Knapsack (Merge and Purge Method)

4.2 Dominance Principle

5. Bellman Ford Algorithm

6. Shortest Path Algorithm – (Dijkstra’s Algorithm)

7. Floyd-Warshall’s Algorithm (Shortest Path)

8. Traveling Salesman Problems

9. Longest Common Subsequence Problem (LCS)

10. String Editing

5. Decrease and Conquer

1. Introduction

2. Definition of Graph, Representation of Graph

2.1 Graphs

2.2 Restrictions on Graph

3. By Constant – DFS and BFS

3.1 Breadth First Search and Traversal1

3.2 Breadth First Graph Traversal

4. Strongly Connected Component (SCC)

5. Topological  Sorting

6. Articulation Point and Bridge Edge

6. Backtracking

1. General Method

1.1 Brute Force Approach

1.2 Control Abstraction of Backtracking

2. Fixed Tuple vs. Variable Tuple Formulation

3. N-Queens Problem

4. Graph Colouring Problem

5. Hamiltonian Cycle

6. Sum of Subsets Problem

7. Branch and Bound Technique

1. Introduction

1.1 Branch and Bound

1.2 Types of Searching

1.3 Bounding and Ranking Function

1.4 Ranking Function

2. 0|1 Knapsack using LCBB

3. Travelling Salesman Problem with LCBB (Variable Tuple Size)

3.1 Method to Solve TSP by LCBB

8. Problem Classification

1. Introduction

2. Types of Satisfiability Problem 

3. Non-Deterministic Algorithms

4. P, NP, NP-Complete, NP-Hard Problems

5. Relationship between P, NP, NP-Hard, NP-Complete and Problems

6. Cook’s Theorem