Consider the following algorithm, which may be called on an array that is not necessarily sorted. and returns the array in sorted form. GoofySort (A) : if (len (A) <= 3): SelectionSort (A) else: Let t + ſlen(A)/3] A[1:2t] + GoofySort (A[1:2t]) A[t+1:n] + GoofySort (A[t+1:n]) //sort the back 2/3rds //sort the front 2/3rds A[1:2t] GoofySort (A[1:2t]) //sort the front 2/3rds (a) Write a recurrence which captures the runtime of this algorithm. Your recurrence should be of the form T (n) =?. You can ignore any non-recursive operations (i.e. you only need to focus on operations in the last three lines). You do not need to handle base cases here. You can assumen is divisible by 3 for convenience. (b) Solve your recurrence using the substitution method. Show your work. You may assume a base case of T (1) = 1. State what the big-O runtime is for this algorithm (hint: it should be a polynomial written in the form n). %3D

Consider the following algorithm, which may be called on an array that is not necessarily sorted. and returns the array in sorted form. GoofySort (A) : if (len (A) <= 3): SelectionSort (A) else: Let t + ſlen(A)/3] A[1:2t] + GoofySort (A[1:2t]) A[t+1:n] + GoofySort (A[t+1:n]) //sort the back 2/3rds //sort the front 2/3rds A[1:2t] GoofySort (A[1:2t]) //sort the front 2/3rds (a) Write a recurrence which captures the runtime of this algorithm. Your recurrence should be of the form T (n) =?. You can ignore any non-recursive operations (i.e. you only need to focus on operations in the last three lines). You do not need to handle base cases here. You can assumen is divisible by 3 for convenience. (b) Solve your recurrence using the substitution method. Show your work. You may assume a base case of T (1) = 1. State what the big-O runtime is for this algorithm (hint: it should be a polynomial written in the form n). %3D

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

Prime numbers can also be generated by an algorithm known as the Sieve of Eratosthenes . The algorithm for this procedure is presented here. Write a program that implements this algorithm so as to find all prime numbers up to n = 150. Sieve of Eratosthenes Algorithm To Display All Prime Numbers Between 1 and n Step 1: Define an array of integers P . Set all elements P i to 0, 2 <= i <= n. Step 2: Set i to 2. Step 3: If i > n , the algorithm terminates. Step 4: If P i is 0 (value i is a prime number), then i is prime and display its value. Step 5: For all positive integer values of j , such that i * j ≤ n , set P i ∗ j to 1 (non - prime). Step 6: Add 1 to i and go to step 3
Consider sorting n numbers stored in array A[1:n] by first finding the smallestelement of A[1:n] and exchanging it with the element in A[1]. Then find thesmallest element of A[2:n], and exchange it with A[2]. Then find the smallestelement of A[3:n], and exchange it with A[3]. Continue in this manner for thefirst n-1 elements of A. Write pseudocode for this algorithm, which is knownas selection sort. What loop invariant does this algorithm maintain? Why does itneed to run for only the first n-1 elements, rather than for all n elements? Give theworst-case running time of selection sort in big theta notation. Is the best-case runningtime any better?
In searching an element in an array, linear search can be used, even though simple to implement, but not efficient, with only O(n) time complexity. Assuming the array is already in sorted order, modify the search function below, using a better algorithm, so the average time complexity for the search function is O(log n). include <iostream> using namespace std; int search(int al), int s, int v) { 1/ Modify below codes. for (int i = 0; i <s; i++) { if (a[i] = v) return i; return -1; int main() { int intArray:10] = { 5, 7, 8, 9, 10, 12, 13, 15, 20, 34); // Search for element '12' in 10-elements integer array. cout << search(intArray, 10, 12); // '5' will be printed out. // Search for element '35' in 10-elements integer array. cout << search(intArray, 10, 35); // '-1' will be printed out. // Index '-l' means that the element is not found. return 0;
Given a sorted array arr[] of distinct integers. Sort the array into a wave-like array and return it In other words, arrange the elements into a sequence such that arr[1] >= arr[2] = arr[4] <= arr[5].. Example 1: Input: n = 5 arr[] {1,2,3,4,5} Output: 2 1 4 3 5 Explanation: Array elements after sorting it in wave form are 2 1 4 3 5.
In a non-empty array of integers, the priority of a number is determined by the frequency of its occurrence. Elements are added as they come but the most frequent element is deleted first. If two elements have the same priority, then the element which came first will be deleted first. For example: nums = [1,2,3,1,3,1,3,2,3]. After the first deletion now the array will be num=[2,3,3,3,2,3]. Implement a priority queue for the aforementioned scenario. give the answer in brief and the correct one.
Write the code in Java language
PYTHON: Please provide a screenshot of your code in Python. Thank you!
Using Javascript Write a higher-order function that when given an array of numbers, return a new array that only includes the even numbers. Hint: filter() function evensOnly(arr) { // your code here}// testconsole.log(evensOnly([3, 5, 6, 8, 2, 11])); /// [6, 8, 2]
15. Consider the problem of finding the first position in which an array b occurs as a subsequence of an array a. Write two nested loops: let result undefined for (let i = 0; i < a.length - b.length; i++) { for (let j = 0; j < b.length; j++) { if (a[i+j] = b[j]) . . . } } Complete with labeled break and continue statements.
Question # 02: Let’s assume we want to find the largest number in a non-empty array A. A sample solution can be following: def max(A): answer = A[0] for j in range(1,len(A)): // in pseudo-code: for i=1,...,len(A)-1 if (A[j]>answer): answer = A[j] return answer Perform the code correction check including the loop invariance. Question # 03: illustrate the operation of merge sort on the array A = {3; 41; 52; 26; 38; 57; 9; 49}. Question # 04: Answer the following short questions: a) Is 2n+1 = O(2n)? b) Is 22n = O(2n)? c) f(n)=O(g(n)) implies g(n)=O(f(n)) d) f(n) = O((f(n))2)
cse