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