You are given the following divide and conquer algorithm whose output you are not required to determine. Treat k here as a parameter that is in 0(1).line 0: DC(A[a_p,...,a_r], k)line 1: n <-- length(A)line 2: if n == kline 3:return A[p..p+k-1]line 4: else // Define two arrays/sequences A1 and A2 each of length n/2line 5:for i = 1 to n/2Line 6:do A1[i] <-- A[i]Line 7:A2[i] <-- A[n/2 + 1]line 8:for i = 1 to n/2line 9:do for j = i+1 to n/2line 10:do if A1[i] == A2[j]line 11:then A2[j] <-- 0line 12:b1<- DC(A1[1,...n/2], k)line 13:b2 <-- DC(A2[1,..,n/2], k)line 14:return max(b1,b2)a. Name the line number(s) where the base case takes place.Activate Windowsb. Name the line number(s) where the divide phase is taking place.Go to Settings to activate a. Name the line number(s) where the base case takes place.b. Name the line number(s) where the divide phase is taking place.c. Name the line numer(s) where the conquer phase is taking place.d. What are the sizes of each of the sub-problems tackled in the conquer phase?e. Name the line number(s) where the combine is taking place.f. Is this algorithm in-place? If yes, justify your answer. If no, determine the amount of extra space needed per recursive call.g. Write down the recurrence associated with the run-time complexity of the given algorithm.

Answer to the above question is in step2.

Answered: a. Name the line number(s) where the…

a. Name the line number(s) where the base case takes place. b. Name the line number(s) where the divide phase is taking place. c. Name the line numer(s) where the conquer phase is taking place.

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

del(int n){ j=(n/3)-1 while (n>0) for(i=n to i=j*3){ print "i"; 5. n--; }//end for 7 j=j/3; }//endwhile }//del() what is the asymptotic run time of del? anyalse each line and what is the final run time
Given: List L of pairs of characters String S Output: TRUE if S is a valid string, FALSE otherwise. A string is considered valid if each character in the string can be paired with another character in the string, where the pair belongs to the input list L. Furthermore, two pairs cannot cross each other. In other words, a pair most completely enclose another, or be completely separate. Design and implement an efficient dynamic programming solution to this problem. Examples: Input L: (a b) (b c) (c d) (a a) Input S: aaba Output: True (pairs shown color-coded: aaba, “aa” fully encloses “ab”) Input L: (a b) (b c) (c d) (a a) Input S: abcaad Output: True (pairs shown color-coded: abcaad, “ab” is separate from the other pairs) Input L: (a b) (b c) (c d) (a a) Input S: acbd Output: False (acbd is not valid because the pairs cross each other.) Input L: (a b) (b c) (c d) (a a) Input S: aaac Output: False Could you please provide python implementation to this?
Given: List L of pairs of characters String S Output: TRUE if S is a valid string, FALSE otherwise. A string is considered valid if each character in the string can be paired with another character in the string, where the pair belongs to the input list L. Furthermore, two pairs cannot cross each other. In other words, a pair most completely enclose another, or be completely separate. Design and implement an efficient dynamic programming solution to this problem. Examples: Input L: (a b) (b c) (c d) (a a) Input S: aaba Output: True (pairs shown color-coded: aaba, “aa” fully encloses “ab”) Input L: (a b) (b c) (c d) (a a) Input S: abcaad Output: True (pairs shown color-coded: abcaad, “ab” is separate from the other pairs) Input L: (a b) (b c) (c d) (a a) Input S: acbd Output: False (acbd is not valid because the pairs cross each other.) Input L: (a b) (b c) (c d) (a a) Input S: aaac Output: False
The Fibonacci sequence begins with 0 and then 1 follows. All subsequent values are the sum of the previous two, for example: 0, 1, 1, 2, 3, 5, 8, 13. Complete the Fibonacci() function, which has an index, n, as parameter and returns the nth value in the sequence. Any negative index values should return -1. Ex: If the input is: 7 the output is: Fibonacci(7) is 13 Note: Use a for loop and DO NOT use recursion.
del(int n){ j=(n/3)-1 while (n>0) for(i=n to i=j*3){ print "i"; 5. n--; }//end for 7 j=j/3; }//endwhile }//del() what is the asymptotic run time of del? anyalse each line and what is teh final run time is teh answer O(n^2/3)?
int getMax(int arr[], int n) { intmx=arr[0]; for (inti=1; i<n; i++) if (arr[i] >mx) mx=arr[i]; returnmx; } Can u give me the code for this one as well....this is the first function and countsort is the second
The Fibonacci sequence begins with O and then 1 follows. All subsequent values are the sum of the previous two, for example: 0, 1, 1, 2, 3, 5, 8, 13. Complete the Fibonacci() function, which has an index n as a parameter and returns the nth value in the sequence. Any negative index values should return -1. Ex: If the input is: 7 the output is: Fibonacci (7) is 13 Note: Use a for loop and DO NOT use recursion. 1 #include NM in N 2 3 int Fibonacci(int n) { 4 /* Type your code here. */ 5} 6 7 int main(void) { 8 int startNum; 9 scanf("%d", &startNum); main.c 10 11 printf("Fibonacci (%d) is %d", startNum, Fibonacci (startNum)); return 0; 12 13 14
Dingyu is playing a game defined on an n X n board. Each cell (i, j) of the board (1 2, he may only go to (2, n).) The reward he earns for a move from cell C to cell D is |value of cell C – value of cell D|. The game ends when he reaches (n, n). The total reward - is the sum of the rewards for each move he makes. For example, if n = 1 2 and A = 3 the answer is 4 since he can visit (1, 1) → (1, 2) → (2, 2), and no other solution will get a higher reward. A. Write a recurrence relation to express the maximum possible reward Dingyu can achieve in traveling from cell (1, 1) to cell (n, n). Be sure to include any necessary base cases. B. State the asymptotic (big-O) running time, as a function of n, of a bottom-up dynamic programming algorithm based on your answer from the previous part. Briefly justify your answer. (You do not need to write down the algorithm itself.)
Sudoku is a popular logic puzzle that uses a 9 by 9 array of squares that are organized into 3 by 3 subarrays. The puzzle solver must fill in the squares with the digits 1 to 9 such that no digit is repeated in any row, any column, or any of the nine 3 by 3 subgroups of squares. Initially, some squares are filled in already and cannot be changed. For example, the following might be a starting configuration for a Sudoku puzzle: Create a class SudokuPuzzle.java Download SudokuPuzzle.java that has the attributes • board—a 9 by 9 array of integers that represents the current state of the puzzle, where 0 indicates a blank square • start—a 9 by 9 array of boolean values that indicates which squares in board are given values that cannot be changed and the following methods: • SudokuPuzzle—a constructor that creates an empty puzzle • toString—returns a string representation of the puzzle that can be printed • addInitial(row, col, value)—sets the given square to the given value as an…
Let A = {a, b, c} and B = {u, v}. Write a. A × B b. B × A
Need help in python. Problem: 2D random walk. A two dimensional random walk simulates the behavior of a particle moving in a grid of points. At each step, the random walker moves north, south, east, or west with probability 1/4, independently of previous moves. Compose a program that takes a command-line argument n and estimates how long it will take a random walker to hit the boundary of a 2n+1-by-2n+1 square centered at the starting point. //Given codeImport stdioImport randomImport sysn = int(sys.argv[1])//write code herestdio.write('The walker took ')stdio.write(c)stdio.writeln(' steps')
Answer it is c++ only Chef recorded a video explaining his favorite recipe. However, the size of the video is too large to upload on the internet. He wants to compress the video so that it has the minimum size possible. Chef's video has N frames initially. The value of the th frame is A₁. Chef can do the following type of operation any number of times: • Choose an index i (1 ≤ i ≤ N) such that the value of the ith frame is equal to the value of either of its neighbors and remove the ith frame. Find the minimum number of frames Chef can achieve. Input 1 1 5 output 1