(a) Here A = [1,1,1,1] and x = 1. At the termination of loop, low = 0. This is because
At the start of the loop, low = 0 while high = 4
(i) Inside the first iteration, m= 2, low is kept at 0 while high is set to 2
(ii) Inside the second iteration, m is set to 1, low is kept at 0 and high is set to 1
(iii) Inside the third iteration, m is set to 0, low is kept at 0 while high is set to 0
So, the loop terminates after 3 iterations
(b) Here A = [1,1,1,1] and x = 2. At the termination of loop, low = 4. This is because
At the start of the loop, low = 0 while high = 4
(i) Inside the first iteration, m = 2 and low is set to 3 while high is kept at 4
(ii) Inside the second iteration, m = 3 and low is set to 4 while high is kept at 4
Hence, the loop terminates after 2 iterations
(c) Here A = [1,1,1,1] and x = 0. At the termination of loop, low = 0. This is because
At the start of the loop, low = 0 while high = 4
(i) Inside the first iteration, m= 2, low is kept at 0 while high is set to 2
(ii) Inside the second iteration, m is set to 1, low is kept at 0 and high is set to 1
(iii) Inside the third iteration, m is set to 0, low is kept at 0 while high is set to 0
So, the loop terminates after 3 iterations
(d) Here A = [0,1,4,9,16,25,36,49] and x = 9. At the termination of loop, low = 3. This is because
At the start of the loop, low = 0 while high = 8
(i) Inside the first iteration, m = 4. Since A[4] > 9 , high is set to 4 while low is kept at 0
(ii) Inside the second iteration, m = 2. Since A[2] < 9 , low is set to 3 while high is kept at 4
(iii) Inside the third iteration, m = 3. Since A[3] = 9, high is set to 3 while low is kept at 3.
Thus, the loop terminates after 3 iterations
(e) Here A = [0,1,4,9,16,25,36,49] and x = 10. At the termination of loop, low =4 . This is because
At the start of the loop, low = 0 while high = 8
(i) Inside the first iteration, m = 4. Since A[4] > 10 , high is set to 4 while low is kept at 0
(ii) Inside the second iteration, m = 2. Since A[2] < 10 , low is set to 3 while high is kept at 4
(iii) Inside the third iteration, m = 3. Since A[3] < 10, low is set to 4 while high is kept at 4 .
Thus, the loop terminates after 3 iterations
(f) We can choose an array A = [ 0, 1, 23, 33, 43, 53, 63,......, (N-1)3]. The variable low contains the index of the approximate cube root. A[low] would be the approximate cube root
(g) The size of the array required is N since we would need to keep every integer from 0 to N-1 as each can be a possible candidate for an approximate root.
(h) At each step, either low is set to (low+high)/2 + 1 or high is set to (low+high)/2. That is in each step, the search space reduces by half. Since, there are originally n elements in the array and each iteration reduces the search space by half, time complexity is O(n) .
(i) We change Line 5. Instead of if (A[m] < x) , we can write if( m3 < x) . Rewriting the whole code below :-
int low = 0; // Line 1
int high = N; // Line 2
while(low != high) { // Line 3
m = (low + high)/2 ; // Line 4 (This is integer division)
if ( m3 < x ) // Line 5 ( this is where we change our code )
then low = m +1; // Line 6
else high = m; // Line 7
}
Refer to the following program sample to answer the parts (a-i) below. Keep in mind that low and high are both indices of array A. /1 Assume that A is a sorted array containing N integers // Assume t...
Make a sorted integer array a[i]=i, i=0,...,n-1. Let bs(a,n,x) be a binary search program that returns the index i of array a[0..n-1] where a[i]=x. Obviously, the result is bs(a,n,x)=x, and the binary search function can be tested using the loop for(j=0; j<K; j++) for(i=0; i<n; i++) if(bs(a,n,i) != i) cout << “\nERROR”; Select the largest n your software can support and then K so that this loop with an iterative version of bs runs 3 seconds or more. Then measure...
Consider the Java program below to sort an array A in an ascending order. M, N, and K are positive integers, and A is an array of N nonnegative integers where 0 < A[i] < M for all i e {0,..., N -1}. In this program, list is a class of an integer list with the following methods. 1st.size(): returns the number of elements in the list lst 1st.get(i): returns the element at the i-th position in the list lst...
My following program has an array which holds 1000 random integers between 1-1000. Now I need help to create an array that holds 10,000 random integer between 1-1000 in my following program. The main goal of this program is time analysis by using bubble sort and binary search algorithms. Please do the following task; 1. Replace the 1000 random integers with 10,000 random integers After change please answer the following question 2. what will be happen, if an array holds...
I must execute in C using parallel Programming techniques the following serial program: void producer_consumer(int *buffer, int size, int *vec, int n) { int i, j; long long unsigned int sum = 0; for(i=0;i<n;i++) { if(i % 2 == 0) { // PRODUCER for(j=0;j<size;j++) { buffer[j] = vec[i] + j*vec[i+1]; } } else { // CONSUMER for(j=0;j<size;j++) {...
Question 1 In the following incomplete C program: #include stdlib.h> #include <stdio.h> int main () { int i, n, max; int array[100]; ... } return 0; } an array of random int values is populated with n random values. Write only the code to find the location of the maximum value in the array. Question 2 Follow these instructions in your Linux account: 1. Create a file called data.txt in the root folder in your account. 2. Create a new...
Problem Description proving program correctness Consider the following program specification: Input: An integer n > 0 and an array A[0..(n - 1)] of n integers. Output: The smallest index s such that A[s] is the largest value in A[0..(n - 1)]. For example, if n = 9 and A = [ 4, 8, 1, 3, 8, 5, 4, 7, 2 ] (so A[0] = 4, A[1] = 8, etc.), then the program would return 1, since the largest value in...
I should use the array and loop to create a java program according to the instruction, but I have no idea how to do it. Introduction This lab assignment continues to give you practice using loops, particularly loops with variable termination conditions, and it also provides you an opportunity to use one-dimensional arrays. Recall that an array is used to store a collection of data. The data can be values of Java primitive data types or else objects (for instance,...
For this lab you will write a Java program that plays the dice game High-Low. In this game a player places a bet on whether the sum of two dice will come up High (totaling 8 or higher), Low (totaling 6 or less) or Sevens (totaling exactly 7). If the player wins, they receive a payout based on the schedule given in the table below: Choice Payout ------ ------ High 1 x Wager Low 1 x Wager Sevens 4 x...
Question2 uses structured design implemented in C. Array of records (structs) with file I/O is needed. The program takes two inputs at a time. The name of a person, and, the coin value as an integer in the range 5 to 95. Input coin values should always be divisible by 5 (integer division). Names are one word strings. An example input is: Jane 30 This input line indicates that 30 cents change is to be given to Jane. Output change...
I need help making this work correctly. I'm trying to do an array but it is drawing from a safeInput class that I am supposed to use from a previous lab. The safeInput class is located at the bottom of this question I'm stuck and it is not printing the output correctly. The three parts I think I am having most trouble with are in Bold below. Thanks in advance. Here are the parameters: Create a netbeans project called ArrayStuff...