Problem 1
Mark the following statements as true or false. a. \(\quad\) A sequential search of a list assumes that the list is in ascending order. b. \(\quad\) A binary search of a list assumes that the list is sorted. c. \(A\) binary search is faster on ordered lists and slower on unordered lists. d. \(A\) binary search is faster on large lists, but a sequential search is faster on small lists.
Problem 2
Consider the following list: 35,82,45,12,56,67,92,77 Using the sequential search as described in this chapter, how many comparisons are required to find whether the following items are in the list? (Recall that by comparisons we mean item comparisons, not index comparisons.) a. 12 b. 92 c. 65 d. 35
Problem 3
a. Write a version of the sequential search algorithm that can be used to search a sorted list. b. Consider the following list: 8,12,15,27,35,48,65,77,86,94,120 Using a sequential search on ordered lists, which you designed in (a), how many comparisons are required to determine whether the following items are in the list? (Recall that comparisons mean item comparisons, not index comparisons. i. 65 ii. 8 iii. 80 iv. 125
Problem 4
Consider the following list: 5,12,25,32,38,46,58,62,85,90,97,105,110 Using the binary search as described in this chapter, how many comparisons are required to find whether the following items are in the list? Show the values of first, last, and middle and the number of comparisons after each iteration of the loop. a. 32 b. 20 c. 105 d. 60
Problem 5
Suppose that \(L\) is a sorted list of 4096 elements. What is the maximum number of comparisons made by the binary search algorithm, given in this chapter, to determine if an item is in \(L ?\)
Problem 6
Sort the following list using the bubble sort algorithm as discussed in this chapter. Show the list after each iteration of the outer for loop. \\[ 38,60,43,5,70,58,15,10 \\]
Problem 7
a. The number of comparisons in the best case of a bubble sort algorithm, as given in this chapter, is \(O\left(n^{2}\right) .\) Show that the following version of the bubble sort algorithm reduces the number of comparisons in the best case of the bubble sort algorithm to \(O(n)\) //list – list to be sorted //elemType – type of the list elements //length – length of the list bool isSorted = false; for (int iteration = 1; (iteration < length) && !isSorted; iteration++) { isSorted = true; //assume that the sublist is sorted for (int index = 0; index < length - iteration; index++) { if (list[index] > list[index + 1]) { elemType temp = list[index]; list[index] = list[index + 1]; list[index + 1] = temp; isSorted = false; } } } b. Using the algorithm given in part (a), find the number of iterations that are needed to sort the following list: 65,14,52,43,75,25,80,90,95
Problem 8
Sort the following list using the bubble sort algorithm as discussed in this chapter. Show the list after each iteration of the outer for loop. \\[ 46,58,16,25,83,98,8,70,5,62 \\]
Problem 9
Assume the following list of keys: 8,28,31,20,55,46 The first three keys are in order. To move 20 to its proper position using the insertion sort algorithm as described in this chapter, exactly how many key comparisons are executed?
Problem 10
Assume the following list of keys: 12,38,45,50,55,5,30 The first five keys are in order. To move 5 to its proper position using the insertion sort algorithm as described in this chapter, exactly how many key comparisons are executed?
