c) Suppose we have 2 lists, X and Y, where X is sorted in increasing order...
Fantastic news! We've Found the answer you've been seeking!
Question:
Transcribed Image Text:
c) Suppose we have 2 lists, X and Y, where X is sorted in increasing order and Y is sorted in decreasing order. Binary search is used to check if there is an index (position) where X and Y have the same value. If we check X and Y at position k and find that X's value is less than Y's value, should we next search the list at an index which is less than k or the list at an index that is greater than k? Briefly explain. You should next search at an index that is greater than k. If we searched next at a position less than k, then the we would be checking a value that is even smaller in list X (because it is ascending) and even larger in list Y (because it is descending) so X's value will always be less than Y's value for smaller k. In contrast, if we search at a position larger than k, then the value for X will be larger and the value for Y will be smaller and maybe they will be the same at a particular position. d) Given the following list of numbers. Show the values after each "pass" of the selection sort algorithm that we developed in class. Note that after each pass, one more value will be placed into the sorted portion of the list. 17 17 17 17 8 3 3 36 36 20 5 5 Lio 5 5 3 3 3 3 3 8 8 position 3: value 17 position 5: value 36 position 6: value 44 Not found 8 8 8 8 17 17 17 44 5 5 20 20 20 20 20 20 36 36 36 36 36 5 4444444444 e) Suppose the list in (d) is now sorted. What elements will be compared if binary search is used to search for the value 37? c) Suppose we have 2 lists, X and Y, where X is sorted in increasing order and Y is sorted in decreasing order. Binary search is used to check if there is an index (position) where X and Y have the same value. If we check X and Y at position k and find that X's value is less than Y's value, should we next search the list at an index which is less than k or the list at an index that is greater than k? Briefly explain. You should next search at an index that is greater than k. If we searched next at a position less than k, then the we would be checking a value that is even smaller in list X (because it is ascending) and even larger in list Y (because it is descending) so X's value will always be less than Y's value for smaller k. In contrast, if we search at a position larger than k, then the value for X will be larger and the value for Y will be smaller and maybe they will be the same at a particular position. d) Given the following list of numbers. Show the values after each "pass" of the selection sort algorithm that we developed in class. Note that after each pass, one more value will be placed into the sorted portion of the list. 17 17 17 17 8 3 3 36 36 20 5 5 Lio 5 5 3 3 3 3 3 8 8 position 3: value 17 position 5: value 36 position 6: value 44 Not found 8 8 8 8 17 17 17 44 5 5 20 20 20 20 20 20 36 36 36 36 36 5 4444444444 e) Suppose the list in (d) is now sorted. What elements will be compared if binary search is used to search for the value 37?
Expert Answer:
Related Book For
Discrete Mathematics and Its Applications
ISBN: 978-0073383095
7th edition
Authors: Kenneth H. Rosen
Posted Date:
Students also viewed these programming questions
-
Let A, B be sets. Define: (a) the Cartesian product (A B) (b) the set of relations R between A and B (c) the identity relation A on the set A [3 marks] Suppose S, T are relations between A and B, and...
-
CANMNMM January of this year. (a) Each item will be held in a record. Describe all the data structures that must refer to these records to implement the required functionality. Describe all the...
-
During 2018, Susan incurred and paid the following expenses for Beth (her daughter), Ed (her father), and herself: Surgery for...
-
In your own words, describe what affects the current yield and the yield to maturity for a bond.
-
how do an easement, license, profit, covenant, and equitable servitude differ, and why do we need each of them?
-
The wire BC has a diameter of 0.125 in. and the material has the stressstrain diagram shown. Determine the vertical displacement of the handle at D if the pull at the grip is slowly increased and...
-
Francum Company has the following data: direct labor $209,000, direct materials used $180,000, total manufacturing overhead $208,000, and beginning work in process $25,000. Compute (a) Total...
-
A loan has a stated annual rate of 19.71%. If loan payments are made monthly and interest is compounded monthly, what is the effective annual rate of interest? You invest $3,679.00 at the beginning...
-
The equilibrium adsorption of methane on a given activated carbon was studied by Grant et al. (1962). They proposed a Langmuir-type adsorption isotherm with parameters \(q_{m}=48 \mathrm{~g}...
-
Evaluate the following integral. Sx sin 7x dx Use integration by parts to rewrite the integral. sin 7x dx = dx Evaluate the integral. x sin 7x dx = (Use C as an arbitrary constant.)
-
Leicht Transfer & Storage provides warehousing services and often purchases pallets from Pallet Central. The companies followed a standard practice for documenting these transactions in which Pallet...
-
Allan and Koraev both owned condominiums in the same building. Koraevs unit was directly above Allans. While Allan lived in her own unit, Koraev leased his. The leasing of Koraevs unit was managed by...
-
Robert Carr is the founder of Heartland Payment Systems, Inc. Carr was heavily involved in negotiations with Global Payments, Inc., concerning the acquisition of Heartland by Global. During this...
-
On December 14, 2011, appellant Aaron Olson contracted to receive telephone service from respondent CenturyLink and also applied for reduced-rate service that CenturyLink provides through Minnesotas...
-
The Tuckers owned an RV that they insured through American Family. On August 26, 2012, their RV was struck by lightning and damaged. The Tuckers reported the damage to American Family. In March 2013,...
-
A company is evaluating a lease to determine whether it would receive capital or operating treatment and concludes that it should be capitalized. However, company accountants realize that a similar...
-
Match the following. Answers may be used more than once: Measurement Method A. Amortized cost B. Equity method C. Acquisition method and consolidation D. Fair value method Reporting Method 1. Less...
-
Construct a truth table for each of these compound propositions. a) (p q) (p q) b) (p q) (p q) c) (p q) (p q) d) (p q) (p q) e) (p q) (p r) f) (p q) (p q)
-
Find the thickness of the graphs in Exercise 27. In Exercise 27 a) K5 b) K6 c) K7 d) K3,4 e) K4,4 f) K5,5
-
Define well-formed formulae of sets, variables representing sets, and operators from {-, , , }.
-
Birth weights in the United States are normally distributed with a mean (in grams) of 3420 g and a standard deviation of 495 g. If you graph this normal distribution, the area to the right of 4000 g...
-
Is the distribution of those digits a normal distribution? Why or why not?
-
Many states have lotteries that involve the random selection of digits 0, 1, 2, ,
Study smarter with the SolutionInn App