COSC 1285/2123
COSC 1285/2123 Algorithms and Analysis
Tutorial 5
Decrease and Conquer Algorithmic Paradigm
Tutorial Exercises
Objective
Students who complete this tutorial should:
� Be familiar with the three major variations of decrease-and-conquer.
� Be able to apply decrease-and-conquer strategies to different problem types.
4.1.7 Apply insertion sort to sort the list E, X, A, M, P, L, E in alphabetical order.
Answer:
E X A M P L E
E | X
E X | A
A E X | M
A E M X | P
A E M P X | L
A E L M P X | E
A E E L M P X
4.5.12 Flipping pancakes There are n pancakes all of different sizes that are stacked on top of each
other. You are allowed to slip a flipper under one of the pancakes and flip over the whole stack
above the flipper. The purpose is to arrange pancakes according to their size with the biggest at the
bottom. Design an algorithm for solving this puzzle.
Answer: This puzzle can be solved using a decrease-by-one algorithm.
First flip the largest pancake to the top, then flip the whole stack so the largest pancake is at
the correct position. Continue with the same procedure using the n− 1 top-most pancakes.
The algorithm is not optimal but always leads to a solution.
Side note: One of the only papers published while at university was related to this
problem.
©2021 RMIT University 1
COSC 1285/2123
4.2.5a Apply the source-removal algorithm to solve the topological sorting problem for the following
digraph:
Answer: d, a, b, c, g, e, f
4.4.10
a Write a pseudocode for the divide-into-three algorithm for the fake-coin problem. (Make sure
that your algorithm handles properly all values of n, not only those that are multiples of 3.)
b Set up a recurrence relation for the number of weighings in the divide-into-three algorithm for
the fake-coin problem and solve it for n = 3k .
c For large values of n, about how many times faster is this algorithm than the one based on
dividing coins into two piles? (Your answer should not depend on n.)
Answer:
Note: This is an important question which has been used as a google interview question.
a. Pseudocode:
Input: Pile of n coins with the fake coin being lighter than the others. Output: The fake
coin.
if n == 1 then
return The single coin remaining is false.
else
Divide the coins into three piles of dn/3e , dn/3e,and n− 2bn/3c coins.
Weigh the first two piles.
if they are the same then
Discard the first two piles and continue the the coins of the third pile.
else
Continue with the lighter of the first two piles.
end if
end if
Explanation for division of the piles:
If n is a multiple of 3 (i.e., n mod 3 = 0), we can divide the coins into three piles of n /3 coins
each and weigh two of the piles. If n = 3k + 1 (i.e., n mod 3 = 1), we can divide the coins into
the piles of sizes k, k, and k + 1 or k + 1, k + 1, and k − 1 (We will use the second option). Fi-
nally, if n = 3k+2 (i.e., n mod 3 = 2), we will divide the coins into the piles of sizes k+1, k+1, and k.
©2021 RMIT University 2
COSC 1285/2123
[original] [Removed ’d’] [Re-
moved ’a’]
[Removed ’b’] [Removed ’c’]
[Removed ’g’]
[Removed ’e’]
Note that if n = 3k + 1 or n = 3k + 2, then dn/3e = k + 1. If n = 3k, then dn/3e = k.
b. The recurrence relation for the number of weightings W (n) needed in the worst case is as follows:
W (n) = W (dn/3e) + 1 for n > 1,W (1) = 0.
For n = 3k, the recurrence becomes W (3k) = W (3k−1) + 1. Solving it by backward substitutions
yields W (3k) = k = log3(n).
c. The ratio of the numbers of weighings in the worst case can be approximated for large values of
n by
log2 n
log3 n
=
log2 n
log3 2 log2 n
= log2 3 ≈ 1.6
4.1.1 Ferrying soldiers A detachment of n soldiers must cross a wide and deep river with no bridge
©2021 RMIT University 3
COSC 1285/2123
in sight. They notice two 12-year-old boys playing in a rowboat by the shore. The boat is so tiny,
however, that it can only hold two boys or one soldier.
a How can the soldiers get across the river and leave the two boys in joint possession of the boat?
Outline the algorithm in plain English.
b How many times need the boat pass from shore to shore? Give a recurrence relation and solve
it.
c Explain the use of “decrease-and-conquer” in your solution.
Answer: Another real world decrease and conquer example. First, consider how to solve it for the
1 soldier case, then how to apply this solution n− 1 times.
1. Transport both boys to the other side. One of the boys return to the side with the soldiers.
One soldier uses to boat to cross. The boy on the other side takes the boat back. Repeat n−1
more times.
2. C(n) = C(n− 1) + 4, C(0) = 0.
3. You are decreasing the problem size with every soldier by a constant.
©2021 RMIT University 4