Syllabus

UNIT-I
Introduction: Algorithm, Pseudo code for expressing algorithms, Performance Analysis-Space Complexity, Time Complexity, Asymptotic Notation – Big (O) Notation, Omega notation, Theta notation, Recurrences.
Basic Traversal and Search Techniques: Techniques for Binary Trees, Techniques for Graphs, DISJOINT SETS – Disjoint set Operations, Union and Find Operations,Connected Components and Spanning Trees.

UNIT-II
Divide and Conquer: General Method, Applications-Binary Search, Merge sort, Quick Sort, Finding Max and Min, Strassen ̳sMatrix Multiplication.
Greedy Method: General Method, Applications-Knapsack Problem, Job Sequencingwith Deadlines, Minimum Cost Spanning Trees-Prims and Kruskals, Optimal storage on Tapes, Single-Source Shortest Paths.

UNIT-III
Dynamic Programming: General Method, Applications-Multistage Graphs, All-Pairs Shortest Paths, Optimal Binary Search Trees, 0/1 Knapsack, TheTraveling Sales Person Problem.
Backtracking: General Method,Applications-8-Queens problem, Sum of Subsets, Graph Coloring and Hamiltonian Cycles, Knapsack Problem.

UNIT-IV
Branch and Bound: The Method, Applications-Travelling Sales Person Problem,0/ 1knapsack problem- LC Branch and Bound solution, FIFO Branch and Bound solution.

UNIT-V
NP–Hard and NP–Complete Problems: NP-hard and NP-complete problems- Basic concepts, Nondeterministic Algorithms, NP-Hard and NP-Complete Classes, Cook’s Theorem, Reduction Source Problems.

Materials for DAA:

Textbook: View/Download

Unit-1 part-1: View/Download

Unit-1 part-2: View/Download

Unit-2 part-1: View/Download

Unit-2 part-2: View/Download

Unit-3 part-1: View/Download

Unit-3 part-2: View/Download

Unit-4 : View/Download

Unit-5 : View/Download