JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II 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. Each question carries 10 marks and may have a, b, c as sub questions.
Part A
Explain the Big oh notation.
Answer
Big Oh notation (O-notation) provides an asymptotic upper bound on the growth rate of a function. A function f(n) is O(g(n)) if there exist positive constants c and n0 such that f(n) ≤ c * g(n) for all n ≥ n0, representing the worst-case time complexity of an algorithm.
Explain Binary search in brief.
Answer
Binary search is an efficient divide-and-conquer algorithm used to find an element in a sorted array. It repeatedly divides the search interval in half by comparing the target value to the middle element; if they are not equal, the half in which the target cannot lie is eliminated, continuing until the element is found or the interval is empty.
What are disjoint sets?
Answer
Sign in to view the complete answer paper.
What is spanning tree?
Answer
Sign in to view the complete answer paper.
State the travelling salesman problem.
Answer
Sign in to view the complete answer paper.
Write the applications of Dynamic programming.
Answer
Sign in to view the complete answer paper.
What is Hamiltonian cycle?
Answer
Sign in to view the complete answer paper.
Explain 8-queen problem.
Answer
Sign in to view the complete answer paper.
What is NP-Complete?
Answer
Sign in to view the complete answer paper.
Explain non-deterministic algorithm.
Answer
Sign in to view the complete answer paper.
Part B
Describe the performance analysis of an algorithm in detail.
Answer
Sign in to view the complete answer paper.
Briefly explain merge sort algorithm with suitable example and derive its time complexity.
Answer
Sign in to view the complete answer paper.
Define time complexity. Describe different notations used to represent time complexities.
Answer
Sign in to view the complete answer paper.
Explain divide and conquer in detail.
Answer
Sign in to view the complete answer paper.
Write a nonrecursive algorithm for inorder traversal of a binary tree T.
Answer
Sign in to view the complete answer paper.
Explain AND/OR Graphs.
Answer
Sign in to view the complete answer paper.
Explain in detail about:
Depth First Search
Answer
Sign in to view the complete answer paper.
Breadth First Search.
Answer
Sign in to view the complete answer paper.
Explain Optimal binary search tree.
Answer
Sign in to view the complete answer paper.
Explain the Prim’s algorithm with an example.
Answer
Sign in to view the complete answer paper.
Solve the following 0/1 Knapsack problem where P=(10, 5, 15, 7, 6, 18, 3), W=(2, 3, 5, 7, 1, 4, 1), C=15, n=7.
Answer
Sign in to view the complete answer paper.
Write an algorithm of all pairs shortest path problem.
Answer
Sign in to view the complete answer paper.
Explain in detail about backtracking.
Answer
Sign in to view the complete answer paper.
Explain the graph coloring with example.
Answer
Sign in to view the complete answer paper.
Briefly explain the Hamiltonian cycle using backtracking.
Answer
Sign in to view the complete answer paper.
Explain the FIFO Branch and Bound solution.
Answer
Sign in to view the complete answer paper.
Compare and contrast between NP-Hard and NP Complete.
Answer
Sign in to view the complete answer paper.
Briefly explain Cooks theorem.
Answer
Sign in to view the complete answer paper.
Explain the classes of P and NP.
Answer
Sign in to view the complete answer paper.
Write a non-deterministic Knapsack algorithm.
Answer
Sign in to view the complete answer paper.