JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II Year DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (May - 2019 - R13)
Part A is compulsory which carries 25 marks. Answer all questions in Part A. Part B consists of 5 Units. Answer any one full question from each unit.
Part A
Write the recursive Fibonacci algorithm and it’s recurrence relation.
Answer
The recursive Fibonacci algorithm is defined as:
The recurrence relation is:
Give the general strategy of divide and conquer method.
Answer
The divide and conquer strategy follows three steps:
- Divide: Break the problem into smaller sub-problems of the same type.
- Conquer: Solve the sub-problems recursively. If the sub-problems are small enough, solve them directly.
- Combine: Merge the solutions of the sub-problems to form the solution for the original problem.
What is minimum cost spanning tree?
Answer
Sign in to view the complete answer paper.
Explain about Single source shortest path problem.
Answer
Sign in to view the complete answer paper.
Define dynamic programming.
Answer
Sign in to view the complete answer paper.
Define i) Principles of optimality ii) Feasible solution iii) Optimal solution.
Answer
Sign in to view the complete answer paper.
Write the control abstraction for LC-Search.
Answer
Sign in to view the complete answer paper.
Describe the 4-queens problem using backtracking.
Answer
Sign in to view the complete answer paper.
What is the significance of Cook’s theorem?
Answer
Sign in to view the complete answer paper.
What are deterministic algorithms?
Answer
Sign in to view the complete answer paper.
Part B
Solve the following recurrence relations and give a Ω bound for each of them:
Answer
Sign in to view the complete answer paper.
Explain the usefulness of the following functional operations on sets: i) MIN ii) DELETE iii) FIND iv) UNION v) INSERT
Answer
Sign in to view the complete answer paper.
Briefly explain the Quick Sort Algorithm with suitable example.
Answer
Sign in to view the complete answer paper.
Describe the Knapsack problem using greedy method.
Answer
Sign in to view the complete answer paper.
Write a short note on BFS.
Answer
Sign in to view the complete answer paper.
Write the algorithm for job sequencing with deadlines.
Answer
Sign in to view the complete answer paper.
Discuss the algorithm and pseudocode to find the minimum spanning tree using prim’s algorithm.
Answer
Sign in to view the complete answer paper.
Dynamic programming was best compared to greedy method. Justify the statement. Explain all pairs shortest path problem.
Answer
Sign in to view the complete answer paper.
What is matrix chain multiplication protocol? Give the solution for the problem of matrix chain multiplication and derive it’s time complexity.
Answer
Sign in to view the complete answer paper.
Discuss the dynamic programming solutions for the problems of:
a) Reliability design and b) Traveling salesperson.
Answer
Sign in to view the complete answer paper.
Briefly explain graph coloring using backtracking.
Answer
Sign in to view the complete answer paper.
Draw the state space tree for m coloring when n=3 and m=3.
Answer
Sign in to view the complete answer paper.
What do you mean by bounding? Explain how these bound are useful in branch and bound methods?
Answer
Sign in to view the complete answer paper.
Explain the method of reduction to solve TSP problem using branch and bound.
Answer
Sign in to view the complete answer paper.
Explain the satisfiability problem.
Answer
Sign in to view the complete answer paper.
Explain the classes of NP-Hard and NP-Complete.
Answer
Sign in to view the complete answer paper.
Discuss approximation algorithm for NP-hard problems.
Answer
Sign in to view the complete answer paper.