Jawaharlal Nehru Technological University Hyderabad
Jawaharlal Nehru Technological University Hyderabad B.Tech IV ADVANCED ALGORITHMS Previous Question Paper (September - 2020 - R16)
Answer any Five Questions. All Questions Carry Equal Marks.
Main
Illustrate the operation of MAX-HEAP-INSERT (A, 10) on the Heap A = {15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1}.
Answer
The initial heap A = {15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1} has 12 elements. Inserting 10 involves adding it as the next leaf node at index 13, then performing a bubble-up operation to maintain the max-heap property.
- Add 10 to the end of the array: {15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1, 10}. The new element is at index 13 (parent index is 6).
- Compare 10 with its parent at index 6 (value 7). Since 10 > 7, swap them: {15, 13, 9, 5, 12, 8, 10, 4, 0, 6, 2, 1, 7}.
- Compare 10 with its new parent at index 3 (value 5). Since 10 > 5, swap them: {15, 13, 9, 10, 12, 8, 5, 4, 0, 6, 2, 1, 7}.
- Compare 10 with its new parent at index 1 (value 13). Since 10 < 13, the max-heap property is satisfied.
Final heap: {15, 13, 9, 10, 12, 8, 5, 4, 0, 6, 2, 1, 7}.
Describe the following:
i) Best-case time for Quick Sort.
ii) Worst-case time for Quick Sort.
Answer
i) Best-case time for Quick Sort: This occurs when the partition process always picks the median element as the pivot, dividing the array into two nearly equal halves. The recurrence relation is T(n) = 2T(n/2) + O(n), which results in a time complexity of
ii) Worst-case time for Quick Sort: This occurs when the partition process consistently picks the smallest or largest element as the pivot, resulting in highly unbalanced partitions where one sub-array has n-1 elements and the other is empty. The recurrence relation is T(n) = T(n-1) + O(n), leading to a time complexity of
Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (5, 10, 3, 12, 5, 50, 6).
Answer
Sign in to view the complete answer paper.
Determine an LCS of (1,0,0,1,0,1,0,1) AND (0,1,0,1,1,0,1,1,0).
Answer
Sign in to view the complete answer paper.
What is an optimal Huffman code for the following set of frequencies, based on the first 8 Fibonacci numbers? a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21.
Answer
Sign in to view the complete answer paper.
Explain the implementation steps of Dijkstra’s algorithm to find shortest path of a given graph (as shown in figure 1).
Answer
Sign in to view the complete answer paper.
Run the Floyd-Warshall algorithm on the weighted, directed graph of figure 2. Show the matrix D(k) that results for each iteration of the outer loop.
Answer
Sign in to view the complete answer paper.
Explain in detail about Bitonic Sorting Network.
Answer
Sign in to view the complete answer paper.
Explain in detail the implementation of Strassen's Matrix Multiplication with an example.
Answer
Sign in to view the complete answer paper.
Explain the implementation of The Knuth-Morris-Pratt algorithm with an example.
Answer
Sign in to view the complete answer paper.
Explain in detail about the vertex-cover problem with an example.
Answer
Sign in to view the complete answer paper.