Page 531 - Discrete Mathematics and Its Applications

510 8 / Advanced Counting Techniques

only once. If we did not do this, the algorithm would have exponential worst-case complexity.
The process of storing the values as each is computed is known as memoization and is an
important technique for making recursive algorithms efficient.

ALGORITHM 1 Dynamic Programming Algorithm for Scheduling Talks.

procedure Maximum Attendees (s 1 ,s 2 ,...,s n : start times of talks;
e 1 ,e 2 ,...,e n : end times of talks; w 1 , w 2 ,..., w n : number of attendees to talks)
sort talks by end time and relabel so that e 1 ≤ e 2 ≤ ··· ≤ e n
for j := 1 to n
if no job i with i< j is compatible with job j
p(j) = 0
else p(j) := max{i | i< j and job i is compatible with job j}
T(0) := 0
for j := 1 to n
T(j) := max(w j + T(p(j)), T(j − 1))
return T (n){T (n) is the maximum number of attendees}

In Algorithm 1 we determine the maximum number of attendees that can be achieved
by a schedule of talks, but we do not find a schedule that achieves this maximum. To find
talks we need to schedule, we use the fact that talk j belongs to an optimal solution for the
first j talks if and only if w j + T(p(j)) ≥ T(j − 1). We leave it as Exercise 53 to construct an
algorithm based on this observation that determines which talks should be scheduled to achieve
the maximum total number of attendees.
Algorithm 1 is a good example of dynamic programming as the maximum total atten-
dance is found using the optimal solutions of the overlapping subproblems, each of which de-
termines the maximum total attendance of the first j talks for some j with 1 ≤ j ≤ n − 1.
See Exercises 56 and 57 and Supplementary Exercises 14 and 17 for other examples of
dynamic programming.

Exercises

1. Use mathematical induction to verify the formula derived 5 pesos, 10 pesos, 20 pesos, 50 pesos, and 100 pesos. Find
in Example 2 for the number of moves required to com- a recurrence relation for the number of ways to pay a bill
plete the Tower of Hanoi puzzle. of n pesos if the order in which the coins and bills are
2. a) Find a recurrence relation for the number of permu- paid matters.
tations of a set with n elements. 5. How many ways are there to pay a bill of 17 pesos using
b) Use this recurrence relation to find the number of per- the currency described in Exercise 4, where the order in
mutations of a set with n elements using iteration. which coins and bills are paid matters?
3. A vending machine dispensing books of stamps accepts ∗ 6. a) Find a recurrence relation for the number of strictly
only one-dollar coins, $1 bills, and $5 bills. increasing sequences of positive integers that have 1
a) Find a recurrence relation for the number of ways as their first term and n as their last term, where n is
to deposit n dollars in the vending machine, where a positive integer. That is, sequences a 1 ,a 2 ,...,a k ,
the order in which the coins and bills are deposited where a 1 = 1, a k = n, and a j <a j+1 for j =
matters. 1, 2,...,k − 1.
b) What are the initial conditions? b) What are the initial conditions?
c) How many ways are there to deposit $10 for a book c) How many sequences of the type described in (a) are
of stamps? there when n is an integer with n ≥ 2?
4. A country uses as currency coins with values of 1 peso, 7. a) Find a recurrence relation for the number of bit strings
2 pesos, 5 pesos, and 10 pesos and bills with values of of length n that contain a pair of consecutive 0s.