ADA (B-TECH Computer Science Engineering 6th)

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.