Page 225 - Discrete Mathematics and Its Applications

204 3 / Algorithms

51. When a list of elements is in close to the correct order, of the opposite gender. Furthermore, suppose that each person
would it be better to use an insertion sort or its variation ranks, in order of preference, with no ties, the people of the
described in Exercise 50? opposite gender. We say that a matching of people of opposite
52. Use the greedy algorithm to make change using quarters, genders to form couples is stable if we cannot find a man m
dimes, nickels, and pennies for and a woman w who are not assigned to each other such that
m prefers w over his assigned partner and w prefers m to her
a) 87 cents. b) 49 cents.
c) 99 cents. d) 33 cents. assigned partner.
53. Use the greedy algorithm to make change using quarters, 60. Suppose we have three men m 1 , m 2 , and m 3 and three
dimes, nickels, and pennies for women w 1 , w 2 , and w 3 . Furthermore, suppose that the
preference rankings of the men for the three women, from
a) 51 cents. b) 69 cents.
highest to lowest, are m 1 : w 3 , w 1 , w 2 ; m 2 : w 1 , w 2 , w 3 ; m 3 :
c) 76 cents. d) 60 cents.
w 2 , w 3 , w 1 ; and the preference rankings of the women for
54. Use the greedy algorithm to make change using quar-
the three men, from highest to lowest, are w 1 : m 1 , m 2 ,
ters, dimes, and pennies (but no nickels) for each of the
m 3 ; w 2 : m 2 , m 1 , m 3 ; w 3 : m 3 , m 2 , m 1 . For each of the
amounts given in Exercise 52. For which of these amounts
six possible matchings of men and women to form three
does the greedy algorithm use the fewest coins of these
denominations possible? couples, determine whether this matching is stable.
The deferred acceptance algorithm, also known as the Gale-
55. Use the greedy algorithm to make change using quar-
ters, dimes, and pennies (but no nickels) for each of the Shapleyalgorithm,canbeusedtoconstructastablematching
amounts given in Exercise 53. For which of these amounts of men and women. In this algorithm, members of one gender
does the greedy algorithm use the fewest coins of these are the suitors and members of the other gender the suitees.
denominations possible? The algorithm uses a sequence of rounds; in each round every
suitor whose proposal was rejected in the previous round pro-
56. Show that if there were a coin worth 12 cents, the greedy poses to his or her highest ranking suitee who has not already
algorithm using quarters, 12-cent coins, dimes, nickels, rejected a proposal from this suitor. A suitee rejects all pro-
and pennies would not always produce change using the posals except that from the suitor that this suitee ranks highest
fewest coins possible.
among all the suitors who have proposed to this suitee in this
57. Use Algorithm 7 to schedule the largest number of talks round or previous rounds. The proposal of this highest ranking
in a lecture hall from a proposed set of talks, if the starting suitor remains pending and is rejected in a later round if a more
and ending times of the talks are 9:00 a.m. and 9:45 a.m.; appealing suitor proposes in that round. The series of rounds
9:30 a.m. and 10:00 a.m.; 9:50 a.m. and 10:15 a.m.; ends when every suitor has exactly one pending proposal. All
10:00 a.m. and 10:30 a.m.; 10:10 a.m. and 10:25 a.m.; pending proposals are then accepted.
10:30 a.m. and 10:55 a.m.; 10:15 a.m. and 10:45 a.m.;
10:30 a.m. and 11:00 a.m.; 10:45 a.m. and 11:30 a.m.; 61. Write the deferred acceptance algorithm in pseudocode.
10:55 a.m. and 11:25 a.m.; 11:00 a.m. and 11:15 a.m. 62. Show that the deferred acceptance algorithm terminates.
58. Show that a greedy algorithm that schedules talks in a lec- ∗ 63. Show that the deferred acceptance always terminates with
ture hall, as described in Example 7, by selecting at each a stable assignment.
step the talk that overlaps the fewest other talks, does not
always produce an optimal schedule. 64. Show that the problem of determining whether a program
with a given input ever prints the digit 1 is unsolvable.
∗ 59. a) Devise a greedy algorithm that determines the fewest
lecture halls needed to accommodate n talks given the 65. Show that the following problem is solvable. Given two
starting and ending time for each talk. programs with their inputs and the knowledge that exactly
b) Prove that your algorithm is optimal. one of them halts, determine which halts.
Suppose we have s men m 1 ,m 2 ,...,m s and s women 66. Show that the problem of deciding whether a specific
w 1 , w 2 ,..., w s .We wish to match each person with a member program with a specific input halts is solvable.

3.2 The Growth of Functions

Introduction

In Section 3.1 we discussed the concept of an algorithm. We introduced algorithms that solve a
variety of problems, including searching for an element in a list and sorting a list. In Section 3.3
we will study the number of operations used by these algorithms. In particular, we will estimate
the number of comparisons used by the linear and binary search algorithms to find an element
in a sequence of n elements. We will also estimate the number of comparisons used by the