JNTU
JNTU B.Tech III DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (May/June - 2019 - R16)
Note: This question paper contains two parts A and B. 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
In what way a time complexity differs from space complexity.
Answer
Time complexity measures the amount of computational time an algorithm takes to run as a function of the input size, whereas space complexity measures the amount of memory (RAM) space an algorithm requires to execute based on the input size.
Give the general plan of divide and conquer algorithms.
Answer
- Divide: Break the problem into a number of smaller, independent sub-problems of the same type.
- Conquer: Solve the sub-problems recursively. If the sub-problems are small enough, solve them directly (base case).
- Combine: Merge the solutions of the sub-problems to obtain the solution for the original problem.
Write an algorithm for collapsing find.
Answer
Sign in to view the complete answer paper.
Define Backtracking? List the applications of Backtracking
Answer
Sign in to view the complete answer paper.
What is the importance of knapsack algorithm in our daily life?
Answer
Sign in to view the complete answer paper.
Write Control Abstraction of Greedy method.
Answer
Sign in to view the complete answer paper.
What you mean by dynamic programming.
Answer
Sign in to view the complete answer paper.
Define optimal binary search tree with an example.
Answer
Sign in to view the complete answer paper.
State the difference between FIFO and LC Branch and Bound algorithms.
Answer
Sign in to view the complete answer paper.
Write the Control Abstraction of Least – Cost Branch and Bound.
Answer
Sign in to view the complete answer paper.
Part B
What are the different mathematical notations used for algorithm analysis.
Answer
Sign in to view the complete answer paper.
Write Divide – And – Conquer recursive Quick sort algorithm and analyze the algorithm for average time complexity.
Answer
Sign in to view the complete answer paper.
Write Randomized algorithm of Quicksort.
Answer
Sign in to view the complete answer paper.
Write an algorithm to determine the Hamiltonian cycle in a given graph using backtracking.
Answer
Sign in to view the complete answer paper.
Explain the AND/OR graph problem with an example.
Answer
Sign in to view the complete answer paper.
Explain the Knapsack problem with an example.
Answer
Sign in to view the complete answer paper.
Write a greedy algorithm for sequencing unit time jobs with deadlines and profits.
Answer
Sign in to view the complete answer paper.
State the Job – Sequencing with deadlines problem. Find an optimal sequence to the n = 5 Jobs where profits (P1, P2, P3, P4, P5) = (20, 15, 10, 5, 1) and deadlines (d1, d2, d3, d4, d5) =(2, 2, 1, 3, 3).
Answer
Sign in to view the complete answer paper.
Draw an Optimal Binary Search Tree for n=4 identifiers (a1,a2,a3,a4) = ( do, if, read, while) P(1:4)=(3,3,1,1) and Q(0:4)=(2,3,1,1,1).
Answer
Sign in to view the complete answer paper.
Explain how Matrix – chain Multiplication problem can be solved using dynamic programming with suitable example.
Answer
Sign in to view the complete answer paper.
Solve the Travelling Salesman problem using branch and bound algorithms.
Answer
Sign in to view the complete answer paper.
Explain the FIFO BB 0/1 Knapsack problem procedure with the knapsack instance for n=4, m=15,(p1,p2,p3,p4)=(10,10,12,18), (w1,w2,w3,w4) =(2, 4, 6, 9). Draw the portion of the state space tree and find optimal solution.
Answer
Sign in to view the complete answer paper.