Page 257 - Discrete Mathematics and Its Applications

236 3 / Algorithms

9. Given an ordered list of n integers and an integer x in the 10. Given a list of integers, determine the number of compar-
list, find the number of comparisons used to determine isons used by the bubble sort and by the insertion sort to
the position of x in the list using a linear search and using sort this list.
a binary search.

Computations and Explorations

Use a computational program or programs you have written to do these exercises.

n
b
1. We know that n is O(d ) when b and d are positive and determine whether the smallest number of coins was
numbers with d ≥ 2. Give values of the constants C and used. Can you find conditions so that the greedy algorithm
n
b
k such that n ≤ Cd whenever x> k for each of these is guaranteed to use the fewest coins possible?
sets of values: b = 10, d = 2; b = 20, d = 3; b = 1000, 3. Using a generator of random orderings of the integers
d = 7. 1, 2,...,n, find the number of comparisons used by
2. Compute the change for different values of n with coins the bubble sort, insertion sort, binary insertion sort, and
of different denominations using the greedy algorithm selection sort to sort these integers.
Writing Projects

Respond to these with essays using outside sources.

1. Examine the history of the word algorithm and describe 7. Explain what the TuringAward is and describe the criteria
the use of this word in early writings. used to select winners. List six past winners of the award
2. Look up Bachmann’s original introduction of big-O no- and why they received the award.
tation. Explain how he and others have used this notation. 8. Describe what is meant by a parallel algorithm. Explain
3. Explain how sorting algorithms can be classified into a how the pseudocode used in this book can be extended to
taxonomy based on the underlying principle on which handle parallel algorithms.
they are based.
9. Explain how the complexity of parallel algorithms can be
4. Describe the radix sort algorithm.
measured. Give some examples to illustrate this concept,
5. Describe the historic trends in how quickly processors can showing how a parallel algorithm can work more quickly
perform operations and use these trends to estimate how than one that does not operate in parallel.
quickly processors will be able to perform operations in
the next twenty years. 10. Describe six different NP-complete problems.
6. Develop a detailed list of algorithmic paradigms and pro- 11. Demonstrate how one of the many different NP-complete
vide examples using each of these paradigms. problems can be reduced to the satisfiability problem.