Design and Analysis of Algorithms(DSA/ADA-"Advanced Data Structures")

UNIT-1

INTRODUCTION TO ALGORITHMS:

The algorithm, Performance Analysis (Time and Space complexity),
Asymptotic Notation 
(Big OH, Omega and Theta): best, average, and worst-case behaviors
Elementary Data Structures Basic terminology of:
Stacks
Queues
Tree
Graph
Sets and Disjoint Set Union.

DIVIDE AND CONQUER:

A general method,
Binary Search,
Sorting algorithms with divide and conquer strategy
Merge Sort,
Quick Sort,
Strassen’s Matrix Multiplication
Algorithms analysis of these problems

UNIT-2

GREEDY METHOD:

A general method
Fractional Knapsack problem
Job Sequencing with Deadlines
Minimum Cost Spanning Trees
Single-source shortest paths

DYNAMIC PROGRAMMING:

A general method
Optimal Binary Search Trees
0/1 knapsack
The Traveling Salesperson problem.

UNIT-3

BACK TRACKING:

A general method
8-Queen’s problem
Sum of subsets
Graph Colouring
Hamiltonian Cycles.

BRANCH AND BOUND:

The method
0/1 knapsack problem
Traveling Salesperson problem
Efficiency considerations

UNIT-4

NP HARD & NP COMPLETE PROBLEMS:

Basic concepts
Cook’s theorem
NP-hard graph problems
NP-hard scheduling problems
NP hard code generation problems
Some other simplified NP-hard problems.