Section-A
Brief Review of Graphs, Sets and disjoint sets, union, sorting and searching algorithms and their analysis in terms of space and time
complexity.
Divide and Conquer: General method, binary search, merge sort, qick sort, selection sort, Strassen‟s matrix multiplication
algorithms and analysis of algorithms for these problems.
Section-B
Greedy Method: General method, knapsack problem, job sequencing with dead lines, minimum spanning trees, single souce paths
and analysis of these problems.
Dynamic Programming: General method, optimal binary search trees, O/I knapsack, the traveling salesperson problem.
Section-C
Unit-5: Back Tracking: General method, 8 queen‟s problem, graph colouring, Hamiltonian cycles, analysis of these problems.
Unit-6: Branch and Bound: Method, O/I knapsack and traveling salesperson problem, efficiency considerations. Techniques for
algebraic problems, some lower bounds on parallel computations.
Section-D
Unit-7: NP Hard and NP Complete Problems: Basic concepts, Cook‟s theorem, NP hard graph and NP scheduling problems some
simplified NP hard problems.