Page 224 - Discrete Mathematics and Its Applications

3.1 Algorithms 203

19. Describe an algorithm that produces the maximum, me- 33. Devise an algorithm that finds the first term of a sequence
dian, mean, and minimum of a set of three integers. (The of positive integers that is less than the immediately pre-
median of a set of integers is the middle element in the list ceding term of the sequence.
when these integers are listed in order of increasing size. 34. Use the bubble sort to sort 6, 2, 3, 1, 5, 4, showing the
The mean of a set of integers is the sum of the integers lists obtained at each step.
divided by the number of integers in the set.)
35. Use the bubble sort to sort 3, 1, 5, 7, 4, showing the lists
20. Describe an algorithm for finding both the largest and the obtained at each step.
smallest integers in a finite sequence of integers. 36. Use the bubble sort to sort d, f, k, m, a, b, showing the
21. Describe an algorithm that puts the first three terms of lists obtained at each step.
a sequence of integers of arbitrary length in increasing ∗ 37. Adapt the bubble sort algorithm so that it stops when
order. no interchanges are required. Express this more efficient
22. Describe an algorithm to find the longest word in an En- version of the algorithm in pseudocode.
glishsentence(whereasentenceisasequenceofsymbols, 38. Use the insertion sort to sort the list in Exercise 34, show-
either a letter or a blank, which can then be broken into ing the lists obtained at each step.
alternating words and blanks). 39. Use the insertion sort to sort the list in Exercise 35, show-
23. Describe an algorithm that determines whether a function ing the lists obtained at each step.
from a finite set of integers to another finite set of integers 40. Use the insertion sort to sort the list in Exercise 36, show-
is onto. ing the lists obtained at each step.
24. Describe an algorithm that determines whether a function The selection sort begins by finding the least element in the
from a finite set to another finite set is one-to-one. list. This element is moved to the front. Then the least element
25. Describe an algorithm that will count the number of 1s in among the remaining elements is found and put into the sec-
a bit string by examining each bit of the string to deter- ond position. This procedure is repeated until the entire list
mine whether it is a 1 bit. has been sorted.
26. Change Algorithm 3 so that the binary search procedure 41. Sort these lists using the selection sort.
compares x to a m at each stage of the algorithm, with the a) 3, 5, 4, 1, 2 b) 5, 4, 3, 2, 1
algorithm terminating if x = a m . What advantage does c) 1, 2, 3, 4, 5
this version of the algorithm have? 42. Write the selection sort algorithm in pseudocode.
27. The ternary search algorithm locates an element in a list 43. Describe an algorithm based on the linear search for de-
ofincreasingintegersbysuccessivelysplittingthelistinto termining the correct position in which to insert a new
three sublists of equal (or as close to equal as possible) element in an already sorted list.
size, and restricting the search to the appropriate piece. 44. Describe an algorithm based on the binary search for de-
Specify the steps of this algorithm. termining the correct position in which to insert a new
28. Specify the steps of an algorithm that locates an element element in an already sorted list.
in a list of increasing integers by successively splitting 45. How many comparisons does the insertion sort use to sort
the list into four sublists of equal (or as close to equal as the list 1, 2,...,n?
possible) size, and restricting the search to the appropriate
46. How many comparisons does the insertion sort use to sort
piece.
the list n, n − 1,..., 2, 1?
In a list of elements the same element may appear several
The binary insertion sort is a variation of the insertion sort
times. A mode of such a list is an element that occurs at least that uses a binary search technique (see Exercise 44) rather
as often as each of the other elements; a list has more than than a linear search technique to insert the ith element in the
one mode when more than one element appears the maximum correct place among the previously sorted elements.
number of times.
47. Show all the steps used by the binary insertion sort to sort
29. Devise an algorithm that finds a mode in a list of nonde- the list 3, 2, 4, 5, 1, 6.
creasing integers. (Recall that a list of integers is nonde- 48. Compare the number of comparisons used by the inser-
creasing if each term is at least as large as the preceding tion sort and the binary insertion sort to sort the list 7, 4,
term.)
3, 8, 1, 5, 4, 2.
30. Devise an algorithm that finds all modes. (Recall that a ∗ 49. Express the binary insertion sort in pseudocode.
list of integers is nondecreasing if each term of the list is
at least as large as the preceding term.) 50. a) Devise a variation of the insertion sort that uses a lin-
ear search technique that inserts the jth element in the
31. Devise an algorithm that finds the first term of a se- correct place by first comparing it with the (j − 1)st
quence of integers that equals some previous term in the element, then the (j − 2)th element if necessary, and
sequence. so on.
32. Devise an algorithm that finds all terms of a finite se- b) Use your algorithm to sort 3, 2, 4, 5, 1, 6.
quence of integers that are greater than the sum of all c) Answer Exercise 45 using this algorithm.
previous terms of the sequence. d) Answer Exercise 46 using this algorithm.