DAA(2021)

UNIT-I: Algorithms Introduction

Introduction

1. Introduction

2. Priority Queues

3. Disjoint Set Union and Find

Lecture Notes

Divide and conquer

1. Binary Search

2. Finding Maximum and Minimum

3. Merge Sort

4. Quick Sort

5. Selection Problem

6. Strassen's Matrix Multiplication

7. Convex Hull Problem

Lecture Notes

UNIT-II: Greedy Method

1. General Method

2. Knapsack Problem

3. Tree Vertex Splitting

4. Job Sequencing With Dead Lines

5. Minimum Spanning Trees

a. Prim's Algorithm

b. Kruskal's Algorithm

6. Optimal Storage On Tapes

7. Optimal Merge Patterns

8. Huffman Coding

9. Single Source Shortest path.

Lecture Notes

UNIT-III: Dynamic Programming.

1. Multi Stage Graphs

2. All Pairs Shortest Path

3. Single Source Shortest Path With General Weights

4. Optimal Binary Search Trees.

5. String Editing Problem

6. 0/1 Knapsack Problem

7. Reliability Design

8. Travelling Salesman Problem.

Lecture Notes

UNIT-IV: Back Tracking

1. 8-Queens Problem

2. Sum Of Subsets

3. Graph Coloring

4. Hamiltonian Cycles

5. Knapsack Problem

Branch And Bound

1. 15 Puzzle Problem

2. 0/1 Knapsack Problem

Lecture Notes

UNIT-V: Algebraic Problems

1. algebraic Simplification and Transformation

2. Modular Arithmetic

3. Lower Bound Theory

4. Comparison Trees

5. NP Hard and NP Completeness

Lecture Notes