Duration of University Examination 3 Hours
University Examination 80 Marks
Sessional 20 Marks
Introduction & Elementary data structures:
Order notation, Analysis of algorithms, review of elementary data structures-
Divide and Conquer:
The general method, binary search, finding maximum and minimum,
Greedy method: Knapsack problem, Optimal storage on tapes,
Dynamic programming and traversal techniques: Multistage graphs
Biconnected components and depth first search.
Backtracking and branch and bound: 8-Queens problem,
Graph coloring, Hamiltonian cycles, Knapsack problem, 0/1 Knapsack problem,
Traveling salesman problem, Lower bound theory.
NP-hard and NP-completeness: Basic concepts,
Cook’s theorem, NP-hard graph problems and scheduling problems,
NP-hard code generation problems. Decision problem. Node covering problem.