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

Backtracking 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

Suggested Reading:

1. Horowitz E, SahniS, Fundamentals of Computer Algorithms, 2nd Edition, Universities Press, 2007

2. AhoA.V.HopcroftJ.E,UllmanJ.D, TheDesignandAnalysisofComputerAlgorithms, Addison Wesley, 1974

3. Michael T. Goodrich, Roberto Tamassia, Algorithm Design: Foundations, Analysis and Internet Examples, John Wiley & Sons,2002