Homework Answers
a) Time for OddSum(A) = T(n)
Time for OddSum(A1) = T(n/2) as it covers half of the
input array.
Time for OddSum(A2) = T(n/2) as it covers half of the input
array.
Time for OddSum(A3) = T(n/2) as it covers half of the
input array.
Hence, T(n) = T(n/2) + T(n/2) + T(n/2) + C //C is the constant
time
Hence, T(n) = 3T(n/2) + C
b) Using Master's Theorem, a=3, b=2. f(n) =
C
Asymptotically, nlog23 is greater than f(n)
which is C.
Therefore, running time is 
Please comment for query.
Add Answer to:
2. Consider the following algorithm. Assume arrays are 0-indexed. Assume list indices are rounded to the...
What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The...
What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The input is an array A of size n. You may assume that n is a power of 2. (NOTE: It doesn’t matter what the algorithm does, just analyze its complexity). Assume that the non-recursive function call, bar(A1,A2,A3,n) has cost 3n. Show your work! Next to each statement show its cost when the algorithm is executed on an imput of size n abd give the...
What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The...
What is the worst-case asymptotic time complexity of the following divide-andconquer algorithm (give a Θ-bound). The input is an array A of size n. You may assume that n is a power of 2. (NOTE: It doesn’t matter what the algorithm does, just analyze its complexity). Assume that the non-recursive function call, bar(A1,A2,A3,n) has cost 3n. Show your work! Next to each statement show its cost when the algorithm is executed on an imput of size n abd give the...
How to design an algorithm using recursion to find number of subarray contains all 0 in...
How to design an algorithm using recursion to find number of subarray contains all 0 in an array which only contains 0 or 1? For example, we have array 00, so we return 1, if we have an array 0100, we return 2. Assume the size of array >=1. How to find the recurrence relation of the algorithm? And how to express the recurrence relation as a function of n.
Consider the following: Algorithm 1 Smallest (A,q,r) Precondition: A[ q, ... , r] is an array...
Consider the following: Algorithm 1 Smallest (A,q,r) Precondition: A[ q, ... , r] is an array of integers q ≤ r and q,r ∈ N. Postcondition: Returns the smallest element of A[q, ... , r]. 1: function Smallest (A , q , r) 2: if q = r then 3: return A[q] 4: else 5: mid <--- [q+r/2] 6: return min (Smallest(A, q, mid), Smallest (A, mid + 1, r)) 7: end if 8: end function (a) Write a recurrence...
The following algorithm (Rosen pg. 363) is a recursive version of linear search, which has access...
The following algorithm (Rosen pg. 363) is a recursive version of linear search, which has access to a global list of distinct integers a_1, a_2,..., a_n. procedure search(i, j, x : i,j, x integers, 1 < i < j < n) if a_i = x then return i else if i = j then 4. return 0 else return search(i + 1, j, x) Prove that this algorithm correctly solves the searching problem when called with parameters i = 1...
1. Write a program that reads in two arrays (a1 and a2) of numbers and creates...
1. Write a program that reads in two arrays (a1 and a2) of numbers and creates a new array (a3) of numbers such that the new array contains all the unique numbers of a1 and a2. Assume the input array elements are unique elements. In the main function, ask the user to enter the length of each array, declare and reads in the numbers for each array, and calculate and display the output array. Example input/output #1: Enter the length...
Consider an ordered array A of size n and the following ternary search algorithm for finding...
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K. Divide the array into three parts. If A[n/3] > K. the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last thud of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3]...
4 Exercise: Arrays and Functions Many of the tasks from the previous exercises can be generalized...
4 Exercise: Arrays and Functions Many of the tasks from the previous exercises can be generalized to functions, allowing easy reuse. Recall that arrays in C are essentially represented by pointers, so when an array is passed into a function, the function is given access to the original array data (not a copy). This means that arrays are effectively passed by reference in C, and therefore that functions must be careful not to modify the contents of arrays they receive...
Write a recurrence relation describing the worst case running time of each of the following algorithms,...
Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem. Simplify your answers, expressing them in a form such as O(nk) or (nklog n) whenever possible. If the algorithm takes exponential time, then just give an exponential lower bound using the 2 notation. function...
Find the space complexity of Merge Sort below as a function of n (the length of...
Find the space complexity of Merge Sort below as a function of n (the length of A). Assume: • The elements of A require (1) space. • Merge takes 2 sorted arrays as input and merges them into one sorted array containing both inputs' elements in (n) space. A (there is no index trickery allowing Al and A2 Note that Al and A2 are independent arrays from to be "in" A; A is not being sorted in place). Merge Sort...
The following algorithm (Rosen pg. 363) is a recursive version of linear search, which has access to a global list of distinct integers a_1, a_2,..., a_n. procedure search(i, j, x : i,j, x integers, 1 < i < j < n) if a_i = x then return i else if i = j then 4. return 0 else return search(i + 1, j, x) Prove that this algorithm correctly solves the searching problem when called with parameters i = 1...
Consider an ordered array A of size n and the following ternary search algorithm for finding the index i such that A[i] = K. Divide the array into three parts. If A[n/3] > K. the first third of the array is searched recursively, else if A[2n/3] > K then the middle part of the array is searched recursively, else the last thud of the array is searched recursively. Provisions are also made in the algorithm to return n/3 if A[n/3]...
Write a recurrence relation describing the worst case running time of each of the following algorithms, and determine the asymptotic complexity of the function defined by the recurrence relation. Justify your solution by using substitution or a recursion tree. You may NOT use the Master Theorem. Simplify your answers, expressing them in a form such as O(nk) or (nklog n) whenever possible. If the algorithm takes exponential time, then just give an exponential lower bound using the 2 notation. function...
Find the space complexity of Merge Sort below as a function of n (the length of A). Assume: • The elements of A require (1) space. • Merge takes 2 sorted arrays as input and merges them into one sorted array containing both inputs' elements in (n) space. A (there is no index trickery allowing Al and A2 Note that Al and A2 are independent arrays from to be "in" A; A is not being sorted in place). Merge Sort...
Most questions answered within 3 hours.
-
Pretend that you are
the audit manager on an annual financial statement audit engagement
for a...
asked 4 minutes ago -
A certain lens focuses light from an object 1.65 m away as an
image 41.8 cm...
asked 4 minutes ago -
Which metal has a resistivity that is within the range or
closest to 4.2X10^-6 to 4.7X10^-6...
asked 10 minutes ago -
5.) Suppose a researcher collected data on the mean height of
tomato plants grown in organic...
asked 22 minutes ago -
(b) A medical statistician wants to estimate the average weight
loss of people who are on...
asked 27 minutes ago -
In scala,
Can you explain what is the difference between them, and why the
first one...
asked 28 minutes ago -
True (T) or False (F) Questions
In a queuing system, if the system’s utilization is 100%,...
asked 37 minutes ago -
What is the total energy transported per hour along a narrow
cylindrical laser beam 1.60 mm...
asked 45 minutes ago -
Key Assessment PAT 6: Sayles Chapter 14 Application Exercise
2
Beginning January 1, Community Hospital had...
asked 51 minutes ago -
Let's assume the following data represents the time from when a
patient is discharged from North...
asked 58 minutes ago -
A destination marketing campaign creates an adventurous, the
only-one-of- its-kind type of theme with the destination...
asked 57 minutes ago -
There are twelve possible ways to draw a Fischer diagram that
depicts D-alanine at a pH=8....
asked 1 hour ago