c) Suppose we have 2 lists, X and Y, where X is sorted in increasing order...

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?