JNTU
JNTU B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (September - 2022 - R16)
Answer any five questions. All questions carry equal marks.
Main
What is optimal binary search tree? Give dynamic programming formulation for the same.
Answer
An Optimal Binary Search Tree (OBST) is a binary search tree constructed for a given set of keys with associated access probabilities such that the total search cost is minimized. If keys are sorted, the tree structure that minimizes the expected number of comparisons is chosen.
The dynamic programming formulation defines e[i, j] as the minimum expected cost of a search in an OBST containing keys ki through kj. Let w[i, j] be the sum of probabilities of keys ki to kj. The recurrence is:
Base cases are e[i, i-1] = di-1, representing the cost of dummy keys when the tree is empty.
How Partition is done in Quick Sort? Explain with an example.
Answer
The Partition process in Quick Sort rearranges a subarray A[p...r] around a pivot element x = A[r]. It places the pivot in its correct sorted position such that all elements to the left are less than or equal to the pivot, and all elements to the right are greater than the pivot.
- Initialize i = p - 1.
- Iterate j from p to r-1.
- If A[j] ≤ x, increment i and swap A[i] with A[j].
- Finally, swap A[i+1] with the pivot A[r].
Example: Consider [2, 8, 7, 1, 3, 5, 6, 4]. With pivot 4: 2 is smaller (swap), 8 is larger, 7 is larger, 1 is smaller (swap), 3 is smaller (swap). The array becomes [2, 1, 3, 4, 8, 5, 6, 7], where 4 is now at index 3.
Discuss in detail about randomized algorithms.
Answer
Sign in to view the complete answer paper.
Write an algorithm/pseudocode to sort elements using Heap sort technique. Illustrate the working of Heap sort algorithm on the following input: 35, 15, 0, 1, 60.
Answer
Sign in to view the complete answer paper.
How Dynamic Programming is used to solve Knapsack Problem? Explain.
Answer
Sign in to view the complete answer paper.
Define the Single Source Shortest Path Problem and explain any one algorithm.
Answer
Sign in to view the complete answer paper.
Write Huffman code algorithm and derive its complexity.
Answer
Sign in to view the complete answer paper.
Illustrate about minimum spanning trees with suitable examples.
Answer
Sign in to view the complete answer paper.
What is Strassen’s matrix multiplication? Explain with example. Why is Strassen matrix multiplication considered better than simple matrix multiplication? Discuss.
Answer
Sign in to view the complete answer paper.
Discuss in detail about Zero-one principle with example.
Answer
Sign in to view the complete answer paper.
Compute inverse of A = [[1, 1, 0, 0], [1, 2, 1, 0], [0, 1, 2, 1], [0, 0, 1, 2]].
Answer
Sign in to view the complete answer paper.
Write a detailed note on sorting networks.
Answer
Sign in to view the complete answer paper.
What is naive string matching algorithm? Write the complexity of naïve string matching.
Answer
Sign in to view the complete answer paper.
Discuss the purpose of Knuth Morris Pratt algorithm? What problem does it solve? Explain.
Answer
Sign in to view the complete answer paper.
Explain Traveling Salesman problem with suitable example.
Answer
Sign in to view the complete answer paper.
List and discuss various approximation algorithms in brief.
Answer
Sign in to view the complete answer paper.