Design and Analysis of Algorithms (DAA)

UNIT I

Introduction & Elementary Data Structures: Order notation, Analysis of algorithms, Review of elementary data structures Heaps and Heap sort, Hashing. Sets representation, UNION, FIND operations.

UNIT II

Divide-and-Conquer Method: The general method, Binary search, Finding maximum and minimum, Merge sort, Quick sort and Selection sort.

Greedy Method: Knapsack problem, Optimal storage on tapes, Job sequencing with deadlines, Optimal merge pattern, Minimum spanning trees, Single source shortest path.

UNIT III

Dynamic programming method and traversal techniques: Multi stage graphs, All pairs shortest paths, Optimal binary search tress, 0/1 Knapsack problem, Reliability design, Traveling salesman problem, Game trees, Biconnected components and Depth first search.

UNIT IV

Back tracking and branch-and-bound methods Hamiltonian cycles, Knapsack problem and problem.

Lower-bound Theory methods: N-queens problem, Graph coloring, 0/1 Knapsack problem, Traveling sales person

UNIT V

NP-hard and NP-complete problems: Basic concepts, Non-deterministic algorithms, NP-hard graph problems and scheduling problems, NP-hard code generation problem, Decision problem, Node cover problem.