Suppose you are writing an algorithm to merge k sorted arrays of size n into a single sorted array of size kn. You write an algorithm to do so that (1) makes a recursive call to merge the first k/2 arrays, (2) makes another recursive call to merge the remaining k/2 arrays, then (3) merges the results from the calls in (1) and (2). Suppose the cost of merging two sorted arrays of sizes a and b is a+b. Suppose you are sitting at the root of the recursion tree, where the last two arrays of size kn/2 will be merged. What will be the total cost of the algorithm at this level of the tree? Give your answer as an expression in terms of n and k (in simplest form). nk'log(nk) Question 7 Given the recursive algorithm above for merging k sorted arrays, what will be the total cost of the algorithm at the bottom of the recursion tree (the sum of the work performed at the leaves)? You can assume that k is a power of 2. Give your answer as a simplified expression in terms of n and k.

Suppose you are writing an algorithm to merge k sorted arrays of size n into a single sorted array of size kn. You write an algorithm to do so that (1) makes a recursive call to merge the first k/2 arrays, (2) makes another recursive call to merge the remaining k/2 arrays, then (3) merges the results from the calls in (1) and (2). Suppose the cost of merging two sorted arrays of sizes a and b is a+b. Suppose you are sitting at the root of the recursion tree, where the last two arrays of size kn/2 will be merged. What will be the total cost of the algorithm at this level of the tree? Give your answer as an expression in terms of n and k (in simplest form). nk'log(nk) Question 7 Given the recursive algorithm above for merging k sorted arrays, what will be the total cost of the algorithm at the bottom of the recursion tree (the sum of the work performed at the leaves)? You can assume that k is a power of 2. Give your answer as a simplified expression in terms of n and k.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

You want to design an algorithm, called minMax(A,p,r), that takes an array of integers and indexes of the first and last elements, and returns the minimum and maximum values in that range. Now write the pseudo code of a divide and conquer (and therefore, recursive) algorithm with the same time complexity (Θ(n)). You can assume that p ≤ r. Also, in your code, you can return two numbers by returning a pair, e.g. “return (a, b)”, and can save the output in a similar way, e.g. “(a, b) = minMax(parameters)”. (Short answer please)
Practice using recursive definitions 14. For an n digit positive integer with digits did2d3...dn-1dn, give an informal recursive algorithm to find the sum of the digits. As an example, 247 would have d₁ = 2, d2 = 4, d3 = 7 Rubric: Correct recursion Correct calculation to get digit Correct sum calculation
Answer the given question with a proper explanation and step-by-step solution. Part 1: Implement the quickselect median algorithm Implement the median algorithm from test 1, which is called the "quickselect" algorithm (due to it's relationship to quicksort). Note, it can be used to find the i-th smallest element for any value of i, but we'll just use it to find the median (i = length/2) The algorithm uses the partition helper method (provided) to find the median. The partition method moves small elements, to the left side, and big elements to the right side. Finding the median requires moving all elements smaller than the median to the left half, and all elements greater to the right half. We can call repeatedly partition in a binary-search-like manner to quickly put the median in the right place. Implement the driver method public static int median(int[] arr) which returns the median value, and modifies the input array so all small elements are in the left half, and all big elements…
Question Which of the following statements about mergesort are true? Unless otherwise specified, assume that mergesort refers to the pure recursive (top-down) version of mergesort (with no optimizations), using the merging subroutine described in lecture. Answer Mark all that apply. OThe number of compares to bottom-up mergesort an array depends only on the length of the array n (and not on the keys or order of the keys in the array). O Mergesort is a stable sorting algorithm. Suppose that n is a power of 2. For any array of n distinct keys, top-down mergesort and bottom-up mergesort compare exactly the same pairs of keys (but possibly in a different order). OMergesort uses only a logarithmic amount of space (other than the input array). OIt is possible to design a compare-based algorithm to merge any two sorted arrays, each of length n, with no more than 3/2 n compares.
Java: Consider the following algorithm for searching in an unsorted array. If the size of the array is 1, then check if it contains the element to be searched. Otherwise, divide the array into two halves, and recursively search both halves. Which of (a)–(c) is false? The running time of this algorithm is O(N) The actual running time of this algorithm is likely to be better than sequential search. This is an example of a divide‐and‐conquer algorithm all of the above are true none of the above is true
Jad has n students in his class. He wants to calculate the average grade in exaam 1. a) (Java language) Write the code using a recursive method named double average(int[] A, int startIndex, int n). where A is the array of grades. b) (Java language) Write the code using the iterative way. c) Find the time complexity of the codes in parts (a) and (b).
Write a function lis_rec(arr) that outputs the length of the longest increasing sequence and the actual longest increasing sequence. This function should use divide and conquer strategy to the solve the problem, by using an auxiliary function that is recursive. For example, one possibility is to define a recursive function, lis_rec(arr, i, prev), that takes the array arr, an index i, and the previous element index prev of LIS (which is part of the array arr before index i), and returns the length of the LIS that can be obtained by considering the subarray arr[i:]. Write a dynamic programming version ofthe function, lis_dp(arr), that outputs the length of the longest increasing sequence and the actual longest increasing sequence by using a table to store the results of subproblems in a bottom-up manner. Test the performance of the two functions on arrays of length n = 100, 500, 1000, 5000, 10000. Compare the running times and memory usage of the two functions.
b. The reason that the recursive algorithm is so slow is because the algorithm used to simulate recursion. To compute FN, there is one call to FN-1 and FN-2. However, since FN-1 recursively makes a call to FN-2and FN-3, there are actually two separate calls to compute FN-2. If one traces out the entire algorithm, then we can see that FN-3 is computed three times, FN-4 is computed five times, FN-5 is computed eight times, and so on. As shown Figure Q2b, the growth of redundant calculations is expensive. F6. „F5 F4 F3 F3 'F2 F3 F2 FI FI FO FI FO `F2 F2 FI FI FI FO FI FO FI FO Figure Q2b Write a pseudo code that will reduce the time complexity from o (2n ) to O (n) class of efficiency.