1

2. In class, we discussed the problem of searching for an item x in a sorted...

Question

2. In class, we discussed the problem of searching for an item x in a sorted...

2. In class, we discussed the problem of searching for an item x in a sorted array L with n entries. The returned value is suBelow, you are given two algorithms for searching in a sorted array. Each function is a minor modification of the binary sear

2. In class, we discussed the problem of searching for an item x in a sorted array L with n entries. The returned value is supposed to be -1 if the value x is not in the array, and the index i such that L[i] = x if x is in the array. Assume that I does not contain duplicate values. Now consider the decision trees of algorithms for solving this problem. To make the decision tree more explicit, we can augment the tree with square nodes, which mean that a value of -1 is returned, indicating that u does not appear in the array L. The decision tree for binary search with n= 13, augmented in this fashion, is shown below. 6 2 11 3 5 8 10 12
Below, you are given two algorithms for searching in a sorted array. Each function is a minor modification of the binary search algorithm discussed in class. Algorithm 1 Algorithm 2 integer function BS1 (n,L,x); integer first, last; begin {BS1} first = 0; last = n -1; while first <last do index= [(first + last)/2]; if x == L[index] then return(index); else if x <L[index] then last = index – 1 else first = index + 1; return(-1); end {BS1} integer function BS2(n,L,x); integer first, last; begin {BS2} first = 0; last = n -1; while first <last do index= [(first + last)/2]; if x == L[index] then return(index); else if x <L[index] then last = index else first = index + 1; return(-1); end {BS2} (a) Draw the decision tree for Algorithm 1 with n = 7. If the tree has more than four levels, you only need to draw the first four levels (i.e., levels 0, 1, 2, and 3, where 0 is the root level). (b) Based on your answer to (a), comment on the correctness of Algorithm 1. (c) Draw the decision tree for Algorithm 2 with n = 7. If the tree has more than four levels, you only need to draw the first four levels (i.e., levels 0, 1, 2, and 3, where 0 is the root level). (d) Based on your answer to (c), comment on the correctness of Algorithm 2.

Answers

(a) Decision Tree for Algorithm 1 is shown below:

5 (a)

(b) The Algorithm 1 is incorrect, because when the parameters first and last becomes equal, the algorithm directly returns -1 instead of comparing L[first] with x.  

(c) Decision Tree for Algorithm 2 is shown below:

  (©) 6 2 5 16 3 3

(d) The Algorithm 2 is also incorrect, because it runs into an infinite loop when the parameters first and last are equal.

// If you have any query do ask in the comments section.


Similar Solved Questions

1 answers
Two long, straight wires are separated by 0.12 m. They carry currents of 8 A in...
Two long, straight wires are separated by 0.12 m. They carry currents of 8 A in opposite directions. Find the magnetic field at A and at B. Problem 6 Two long, straight wires are separated by 0.12 m. They carry currents of 8 A in opposite directions. Find the magnetic field at A and at B 0.030 m 0....
1 answers
Required information [The following information applies to the questions displayed below.) Milea Inc. experienced the following...
Required information [The following information applies to the questions displayed below.) Milea Inc. experienced the following events in 2018, its first year of operations: 1. Received $14,000 cash from the issue of common stock. 2. Performed services on account for $45,000. 3. Paid the utility exp...
1 answers
5. Let X, Y, Z be random variables with joint density (discrete or continuous) plr, y,a)...
5. Let X, Y, Z be random variables with joint density (discrete or continuous) plr, y,a) a f(x, 2)g(y, 2)h() Show that (a) p(rly, s) x /(r, :), ie. P(rly, :) is a function of 1 and :; (b) p(y|z, z) g(y, z), İ.e. p(y|z,z) is a function of y and z; (c) X and Y are conditionally independent given ...
2 answers
6/13-4/13?
6/13-4/13?...
1 answers
How can I solve this 3) Inventory (25 Points) During June, the following changes in inventory...
how can I solve this 3) Inventory (25 Points) During June, the following changes in inventory took place: June 1 10 24 Beginning Balance Purchased Purchased 500 units @ $25 per unit 800 units @ $35 per unit 700 units a $10 per unit 400 units a $50 per unit 800 units a $50 per unit 600 units SS5 per ...
1 answers
Hi-Value Widgets can sell 50,000 units per year of a new widget at the price of...
Hi-Value Widgets can sell 50,000 units per year of a new widget at the price of $4 per unit. Variable cost is $2.5/unit. Fixed costs (including rent, administrative costs etc.) are $12,000 per year. The firm will need to invest $90,000 in equipment which is fully depreciated over the three-year life...
1 answers
Q7) You can't you are entitled to receive an annual cash flow of amount A at...
Q7) You can't you are entitled to receive an annual cash flow of amount A at end of each year, starting 1 year from now, except no cash flow at end of fear 4 and year 5. The last cash ! flow will be paid at the end of year 8. At the end of 3rd year after you receive the 3rd payment, someone offe...
1 answers
Let A={a b c d e f} B={a c e g} C = {b d f}...
Let A={a b c d e f} B={a c e g} C = {b d f} Find each: B = {a, c, e,g} C = {b,d,f} A= {a,b,c,d,e,f} Find: (2 points each) (a) AnB (b) AUB (c) Ang (d) COB (e) CUB (f) (An B)UC (g) An(BUC) (h) Ax B (i) C XB G) AB (k) C ( BA) (1) B2...
1 answers
The molecular structure of AsCl5 is: trigonal bipyramidal. octahedral. square pyramidal. distorted tetrahedral. None of these...
The molecular structure of AsCl5 is: trigonal bipyramidal. octahedral. square pyramidal. distorted tetrahedral. None of these choices are correct....
1 answers
MyCarcton E * a Subtract $268 from the bank balance O b Subtract $258 from the...
MyCarcton E * a Subtract $268 from the bank balance O b Subtract $258 from the book balance o c. Add $258 bo the bock balance o d Add $258 to the bank balance Check Question 7 Nol complete A company purchased shares costing $73539 during the year. These shares are classified as FVTOC the end of the ...
1 answers
How does moment of inertia affect angular velocity?
How does moment of inertia affect angular velocity?...
1 answers
A friend of yours asks you to help him/her draw two bacterial growth curves. He/she gives...
A friend of yours asks you to help him/her draw two bacterial growth curves. He/she gives you the following information: the TA started both cultures (one was labeled culture �X� and the other culture �Y�) at 8:30am using the same overnight culture to inoculate fresh medi...
1 answers
S5-16 (similar to) Question Help Mountain Springs produces premium bottled water. Mountain Springs purchases artesian water,...
S5-16 (similar to) Question Help Mountain Springs produces premium bottled water. Mountain Springs purchases artesian water, stores the water in large tanks, and then runs the water through two processes: filtration and bottling. At Mountain Springs, water is added at the beginning of the filtration...
1 answers
Consider the code segment below (assume userInput is a Scanner): int i; printf(“Enter a number: “);...
Consider the code segment below (assume userInput is a Scanner): int i; printf(“Enter a number: “); i = userInput.nextInt(); /* missing code */ What could /* missing code */ be replaced with such that the code segment doesn’t finish executing until the user inputs an even number?...
1 answers
Linear Gradient Please step by step. Thank you! 4.- If you make a deposit of 5,000...
Linear Gradient Please step by step. Thank you! 4.- If you make a deposit of 5,000 dollars at the end of this year and you decrease this amount by 200 dollars each year, and the interest rate is 9%. a) what is the present value of this cash flows b) what is the balance after the last deposit....
1 answers
When 2 defective items are extracted one by one in a partition consisting of 6 products and checked, Let X be the number of tests before finding the last defective item find the probability distrib...
When 2 defective items are extracted one by one in a partition consisting of 6 products and checked, Let X be the number of tests before finding the last defective item find the probability distribution of X. Draw a graph of the distribution function F (x) of X · Calculate the mean μ and ...
1 answers
Hi, can you help me provide the step-by-step working solution for part (b) of the above...
Hi, can you help me provide the step-by-step working solution for part (b) of the above question? 12 A nickel-titanium alloy is used to make components for jet turbine aircraft engines. Cracking is a potentially serious problem in the final part, as it can lead to non-recoverable failure. A test is ...
1 answers
Survey on Answering Machine Ownership in a survey, 63% of Americans said they own an answering...
Survey on Answering Machine Ownership in a survey, 63% of Americans said they own an answering machine. If 16 Americans are selected at random, find the probability that exactly 11 own an answering machine. Round the answer to at least four decimal places. P(11) - X...

-- 0.011200--