Page 254 - Discrete Mathematics and Its Applications

Supplementary Exercises 233

7. a) Describe the linear search and binary search algorithm b) Use the insertion sort algorithm to sort the list 2, 5, 1,
for finding an integer in a list of integers in increasing 4, 3.
order. c) Give a big-O estimate for the number of comparisons
b) Compare the worst-case time complexities of these used by the insertion sort.
two algorithms. 10. a) Explain the concept of a greedy algorithm.
c) Is one of these algorithms always faster than the other b) Provide an example of a greedy algorithm that pro-
(measured in terms of comparisons)? duces an optimal solution and explain why it produces
8. a) Describe the bubble sort algorithm. an optimal solution.
b) Use the bubble sort algorithm to sort the list 5, 2, 4, c) Provide an example of a greedy algorithm that does
1, 3. not always produce an optimal solution and explain
c) Give a big-O estimate for the number of comparisons why it fails to do so.
used by the bubble sort. 11. Define what it means for a problem to be tractable and
9. a) Describe the insertion sort algorithm. what it means for a problem to be solvable.

Supplementary Exercises

1. a) Describe an algorithm for locating the last occurrence c) How many comparisons of elements of the sequence
of the largest number in a list of integers. are carried out by this algorithm? (Do not count com-
b) Estimate the number of comparisons used. parisons used to determine whether the end of the se-
quence has been reached.) How does this compare to
2. a) Describe an algorithm for finding the first and second
the number of comparisons used by the algorithm in
largest elements in a list of integers.
Exercise 5?
b) Estimate the number of comparisons used.
∗ 7. Show that the worst-case complexity in terms of compar-
3. a) Give an algorithm to determine whether a bit string isons of an algorithm that finds the maximum and mini-
contains a pair of consecutive zeros. mum of n elements is at least 3n/2 − 2.
b) How many comparisons does the algorithm use? 8. Devise an efficient algorithm for finding the second
4. a) Suppose that a list contains integers that are in order largest element in a sequence of n elements and deter-
of largest to smallest and an integer can appear repeat- mine the worst-case complexity of your algorithm.
edly in this list. Devise an algorithm that locates all 9. Devise an algorithm that finds all equal pairs of sums of
occurrences of an integer x in the list. two terms of a sequence of n numbers, and determine the
b) Estimate the number of comparisons used. worst-case complexity of your algorithm.
10. Devise an algorithm that finds the closest pair of integers
5. a) Adapt Algorithm 1 in Section 3.1 to find the maxi-
mum and the minimum of a sequence of n elements in a sequence of n integers, and determine the worst-case
by employing a temporary maximum and a temporary complexity of your algorithm. [Hint: Sort the sequence.
minimum that is updated as each successive element Use the fact that sorting can be done with worst-case time
is examined. complexity O(n log n).]
The shaker sort (or bidirectional bubble sort) successively
b) Describe the algorithm from part (a) in pseudocode.
compares pairs of adjacent elements, exchanging them if they
c) How many comparisons of elements in the sequence
are out of order, and alternately passing through the list from
are carried out by this algorithm? (Do not count com-
the beginning to the end and then from the end to the beginning
parisons used to determine whether the end of the se-
until no exchanges are needed.
quence has been reached.)
11. Show the steps used by the shaker sort to sort the list 3,
6. a) Describe in detail (and in English) the steps of an al-
5, 1, 4, 6, 2.
gorithm that finds the maximum and minimum of a
12. Express the shaker sort in pseudocode.
sequence of n elements by examining pairs of suc- 2
cessive elements, keeping track of a temporary maxi- 13. Show that the shaker sort has O(n ) complexity measured
mum and a temporary minimum. If n is odd, both the in terms of the number of comparisons it uses.
temporary maximum and temporary minimum should 14. Explain why the shaker sort is efficient for sorting lists
initially equal the first term, and if n is even, the tem- that are already in close to the correct order.
porary minimum and temporary maximum should be 15. Show that (n log n + n ) is O(n ).
2 3
6
found by comparing the initial two elements. The tem- 16. Show that 8x + 12x + 100 log x is O(x ).
3
3
porary maximum and temporary minimum should be 2 3 x 3
updated by comparing them with the maximum and 17. Give a big-O estimate for (x + x(log x) ) · (2 + x ).
n
minimum of the pair of elements being examined. 18. Find a big-O estimate for j=1 j(j + 1).
n
b) Express the algorithm described in part (a) in pseu- ∗ 19. Show that n! is not O(2 ).
n
docode. ∗ 20. Show that n is not O(n!).