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 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.

#### Similar Solved Questions

##### 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....
##### 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...
##### 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 ...
6/13-4/13?...
##### 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 ...
##### 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...
##### 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...
##### 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...
##### 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....
##### 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 ...
##### How does moment of inertia affect angular velocity?
How does moment of inertia affect angular velocity?...
##### 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...
##### 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...
##### 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?...