JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (December - 2018 - R13)
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
Write the recurrence relation for divide and conquer.
Answer
The general recurrence relation for a divide and conquer algorithm is T(n) = aT(n/b) + f(n), where 'a' is the number of subproblems, 'n/b' is the size of each subproblem, and 'f(n)' is the cost of dividing the problem and merging the results.
List out the drawbacks of merge sort algorithm.
Answer
- It requires additional space proportional to O(n) for the auxiliary array, making it less memory-efficient than algorithms like quicksort.
- It is generally slower than other sorting algorithms like quicksort for smaller datasets due to the overhead of recursive function calls.
- The process of copying elements to and from the auxiliary array adds constant time overhead.
Describe and/or graph.
Answer
Sign in to view the complete answer paper.
Explain briefly game trees.
Answer
Sign in to view the complete answer paper.
List the applications of Dynamic programming.
Answer
Sign in to view the complete answer paper.
Define feasible solution, optimal solution and objective function.
Answer
Sign in to view the complete answer paper.
Differentiate live node and dead node.
Answer
Sign in to view the complete answer paper.
Define solution state and answer state.
Answer
Sign in to view the complete answer paper.
What is decision problem?
Answer
Sign in to view the complete answer paper.
Define class NP.
Answer
Sign in to view the complete answer paper.
Part B
Define algorithm. Write about algorithm design techniques.
Answer
Sign in to view the complete answer paper.
Describe Strassen’s matrix multiplication. Perform the multiplication operation on following two matrices using Strassen’s technique.
4 6
8 3
Answer
Sign in to view the complete answer paper.
What is amortized analysis? Explain in detail about techniques used in amortized analysis with help of dynamic array example.
Answer
Sign in to view the complete answer paper.
Show how quick sort sorts the following sequences of keys 65, 70, 75, 80, 85, 60, 55, 50, 45 solve the recurrence relation of quick sort using substitution method.
Answer
Sign in to view the complete answer paper.
Write the pseudo codes for various operations used by disjoint set.
Answer
Sign in to view the complete answer paper.
Define articulation point. Write the algorithm to find articulation point.
Answer
Sign in to view the complete answer paper.
Explain the graph traversal method with help of following graph shown in figure 1.
Answer
Sign in to view the complete answer paper.
Write and explain the FIND algorithm for collapse rule with example.
Answer
Sign in to view the complete answer paper.
A thief enters a house for robbing thief can carry a maximum weight of 6kg into his bag. There are 3 items in the house with weights (w1, w2, w3) = (2, 3, 4) and profits (p1, p2, p3) = (1, 2, 5) what items should thief can take will get the maximum profit? He either takes or leaves the item.
Answer
Sign in to view the complete answer paper.
Describe in detail job sequencing with deadlines problem. Let n= 4, (P1, P2, P3, P4) = (100, 10, 15, 27) and (d1, d2, d3, d4) = (2, 1, 2, 1) find the optimal solution.
Answer
Sign in to view the complete answer paper.
Explain prim’s and krushkal’s algorithm shown in figure 2 with the following example.
Answer
Sign in to view the complete answer paper.
What is n-queen problem? Describe 4-queen problem using back tracking.
Answer
Sign in to view the complete answer paper.
Find the minimum cost of Tour (TSP) for the following adjacency matrix shown in figure 3 using Branch and Bound.
5 0 9 10
6 13 0 12
8 8 9 0
Answer
Sign in to view the complete answer paper.
Write the Non deterministic algorithm for sorting.
Answer
Sign in to view the complete answer paper.
Explain CNF-SAT Problem.
Answer
Sign in to view the complete answer paper.
Explain about cook’s theorem.
Answer
Sign in to view the complete answer paper.
Explain the P, NP-Hard and NP-complete classes? Give the relation between them.
Answer
Sign in to view the complete answer paper.