1) Consider the following list of numbers (stored in an array of size 25): 2.45,

Question

1) Consider the following list of numbers (stored in an array of size 25): 2.45,6.9,12,14,17.23,30,34,36,37,41,53,59,6265,67,70,75,79.87,96,99 0.24], Show the intermediate values of the range, based on a binary search for the element "30". (Hint: The final a) Start with the initial range value of the range is 19.9) b) Repeat the steps for a binary search for the element "60" 2) Suppose that the letters A.B.E.G.IJ.O.P.UZ have been inserted into set variable setI and that the letters A.F.G.R.S,T,U,W.X have been inserted in ser2. What set of letters would be represented by the variable set3 if the following routine were performed? procedure setopl(setl set2: LetterSet; yar set3: LetterSet): j: Letters. begin for i 'A' to Z' do set3li] not set 1 [1] and set2[i] ; end; 3) Write a subroutine that deternines whether two ordered lists LI and L2 have the same elements. Use first0, nexto. EOLO and currKey0 commands

Explanation / Answer

1. Given set is 2,4,5,6,9,12,14,17,23,30,34,36,37,41,53,59,62,65,70,75,79,87,96,99 wehave to search for 30

here leftmost index is 0 and rightmost is 24 mid = l+(r-l)/2 where l is leftmost index and r is rightmost and mid is middle index

therefore mid index is (24-0)/2 = 12 therefore element at 12th index is 37 since 37 is greater than 30 we will discard the range [12,24] and consider only [0,11] , now mid value for new range = (11-0) / 2= 5 element at index 5 is 12 which is lesser than 30 so only considering range from [6,11] now mid value will be 6+ (11-6)/2 = 8 element at index 8 is 23 which is lesser than 30 therefore considering only range [9,11] now mid value will be 9+ (11-9)/2=10 element at index 10 is 34 , which is greater than 30 therefore our new range is [9,9] and we have found 30 at index 9 .

Therefore values of ranges were [0,24] ,[0,11],[6,11],[9,11],[9,9]

2.for element 60 here leftmost index is 0 and rightmost is 24 mid = l+(r-l)/2 where l is leftmost index and r is rightmost and mid is middle index

therefore mid index is (24-0)/2 = 12 therefore element at 12th index is 37 since 37 is lesser than 60 our new range becomes [13,24] and our new mid = 13+(24-13)/2 = 18 and element at index 18 is 65 which is greater than 60 , so modifying our range to [13,17] and mid = 13 + (17-13)/2 = 15 and element at index 15 is 59 which is samller than 60 therefore our new range is [16,17] and mid = 16 +(17-16)/2= 16 at index 16 62 which is greater than 60 , so we are not able to search 60 in any possible range therefore element not found.

2. set1 = { A,B,E,G,I,J,O,P,U,Z} and set 2 ={A,F,G,R,S,T,U,W,X}

intersection of set1 and set2 ie common elements are A,G,U and not of intersection means those elemends which are not common in both the set which will give us set3 = { B,E,F,I,J,O,P,R,W,X,Z}

Related Questions

Navigate

• Browse (All)
• Browse 1
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.