
Syllabus
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.