JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD
JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech II DESIGN AND ANALYSIS OF ALGORITHMS Previous Question Paper (December - 2018 - R15)
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.
Part A
Write the recurrence relation for divide and conquer.
Answer
The general recurrence relation for a divide and conquer algorithm that divides a problem of size n into a subproblems, each of size n/b, is given by:
where a ≥ 1 is the number of subproblems, n/b is the size of each subproblem, and f(n) represents the cost of dividing the problem and merging the results of the subproblems.
List out the drawbacks of merge sort algorithm.
Answer
The merge sort algorithm has the following primary drawbacks:
- Space Complexity: It requires an additional auxiliary array of size O(n) to store the merged elements, making it less space-efficient compared to in-place sorting algorithms like quicksort or heapsort.
- Performance on Small Arrays: For small datasets, the overhead of recursive calls and the repeated copying of elements between the auxiliary array and the original array makes it slower than simpler algorithms like insertion sort.
- Data Movement: The algorithm involves significant data movement, as elements are constantly copied into the auxiliary array and then back to the original array, which can be inefficient for large objects or complex data structures where copying is costly.
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.
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.
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.