This file contains the exercises, hints, and solutions for Chapter 1 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 1.1
1. Do some research on al-Khorezmi (also al-Khwarizmi), the man from
whose name the word “algorithm” is derived. In particular, you should
learn what the origins of the words “algorithm” and “algebra” have in
common.
5. Design an algorithm to find all the common elements in two sorted lists
of numbers. For example, for the lists 2, 5, 5, 5 and 2, 2, 3, 5, 5, 7, the
output should be 2, 5, 5. What is the maximum number of comparisons
your algorithm makes if the lengths of the two given lists are and
respectively?
8. What does Euclid’s algorithm do for a pair of integers in which the first
is smaller than the second? What is the maximum number of times this
can happen during the algorithm’s execution on such an input?
b. What is the maximum number of divisions made by Euclid’s algorithm
among all inputs 1≤ ≤10?
10. a. Euclid’s algorithm, as presented in Euclid’s treatise, uses subtractions
rather than integer divisions. Write pseudocode for this version of Euclid’s
algorithm.
11. The extended Euclid’s algorithm determines not only the greatest
common divisor of two positive integers and but also integers (not
necessarily positive) and ,suchthat + =
12. BLocker doors There are lockers in a hallway, numbered sequentially
from 1 to . Initially, all the locker doors are closed. You make passes
Hints to Exercises 1.1
2. One can find arguments supporting either view. There is a well established
principle pertinent to the matter, though: scientific facts or mathematical
expressions of them are not patentable. (Why do you think it is the case?)
But should this preclude granting patents for all algorithms?
3. You may assume that you are writing your algorithms for a human rather
5. Try to design an algorithm that always makes less than comparisons.
6. a. Just follow Euclid’s algorithm as described in the text.
b. Compare the number of divisions made by the two algorithms.
7. Prove that if divides both and (i.e., = and = for some
b. The key is to figure out the total number of distinct integers that can be
written on the board, starting with an initial pair where ≥1
You should exploit a connection of this question to the question of part
(a). Considering small examples, especially those with =1and =2
should help, too.
3
Solutions to Exercises 1.1
1. Al-Khwarizmi (9th century C.E.) was a great Arabic scholar, most famous
for his algebra textbook. In fact, the word “algebra” is derived from the
2. This legal issue has yet to be settled. The current legal state of affairs
3. n/a
4. A straightforward algorithm that does not rely on the availability of an
approximate value of √can check the squares of consecutive positive
5. Initialize the list of common elements to empty. Starting with the first ele-
ments of the lists given, repeat the following until one of the lists becomes
empty. Compare the current elements of the two lists: if they are equal,
6. a. gcd(3141514142) = gcd(141423131) = gcd(31311618) =
gcd(16181513) = gcd(1513105) = gcd(1513105) = gcd(10543) =
gcd(4319) = gcd(195) = gcd(54) = gcd(41) = gcd(10) = 1
7. Let us first prove that if divides two integers and it also divides
both +and −.Bydefinition of division, there exist integers and
such that = and = Therefore
±= ± =(±)
8. For any input pair such that 0≤Euclid’s algorithm simply
swaps the numbers on the first iteration:
9. a. For any input pair ≥≥1in which is a multiple of Euclid’s
algorithm makes exactly one division; it is the smallest number possible
for two positive numbers.
10. a. Here is a nonrecursive version:
Algorithm Euclid2 ( )
//Computes gcd( )by Euclid’s algorithm based on subtractions
//Input: Two nonnegative integers and not both equal to 0
11. n/a
12. Since all the doors are initially closed, a door will be open after the last
pass if and only if it is toggled an odd number of times. Door (1 ≤≤)
is toggled on pass (1 ≤≤)if and only if divides Hence, the total
number of times door is toggled is equal to the number of its divisors.
Exercises 1.2
1. Old World puzzle Apeasantfinds himself on a riverbank with a wolf,
a goat, and a head of cabbage. He needs to transport all three to the
other side of the river in his boat. However, the boat has room for only
2. New World puzzle Therearefourpeoplewhowanttocrossarickety
bridge; they all begin on the same side. You have 17 minutes to get them
all across to the other side. It is night, and they have one flashlight. A
3. Which of the following formulas can be considered an algorithm for com-
puting the area of a triangle whose side lengths are given positive numbers
,,and?
5. Describe the standard algorithm for finding the binary representation of
a positive decimal integer
6. Describe the algorithm used by your favorite ATM machine in dispensing
cash. (You may give your description in either English or pseudocode,
whichever you find more convenient.)
7
7. a. Can the problem of computing the number be solved exactly?
8. Give an example of a problem other than computing the greatest common
divisor for which you know more than one algorithm. Which of them is
simpler? Which is more efficient?
9. Consider the following algorithm for finding the distance between the two
closest elements in an array of numbers.
10. One of the most influential books on problem solving, titled How To Solve
It [Pol57], was written by the Hungarian-American mathematician George
Pólya (1887—1985). Pólya summarized his ideas in a four-point summary.
Hints to Exercises 1.2
1. The peasant would have to make several trips across the river, starting
with the only one possible.
5. You almost certainly learned this algorithm in one of your introductory
programming courses. If this assumption is not true, you have a choice
between designing such an algorithm on your own or looking it up.
6. You may need to make a field trip to refresh your memory.
10. n/a
Solutions to Exercises 1.2
1. Let P,w,g,andcstand for the peasant, wolf, goat, and cabbage head,
respectively. The following is one of the two principal sequences that
solve the problem:
2. Let 1, 2, 5, 10 be labels representing the men of the problem, represent
the flashlight’s location, and the number in the parenthesis be the total
amount of time elapsed. The following sequence of moves solves the
problem:
3. a. The formula can be considered an algorithm if we assume that we know
how to compute the square root of an arbitrary positive number.
b. The difficulty here lies in computing sin Since the formula says
nothing about how it has to be computed, it should not be considered an
4. Algorithm Quadratic( )
//The algorithm finds real roots of equation 2+ +=0
//Input: Real coefficients
10
5. a. Divide the given number by 2: the remainder (0 or 1) will be
the next (from right to left) digit of the binary representation in question.
Replace by the quotient of the last division and repeat this operation
until becomes 0.
6. n/a
7. a. , as an irrational number, can be computed only approximately.
8. n/a
11
10. Pólya’s general four-point approach is:
1. Understand the problem
12
Exercises 1.3
1. Consider the algorithm for the sorting problem that sorts an array by
counting, for each of its elements, the number of smaller elements and
then uses this information to put the element in its appropriate position
in the sorted array:
Algorithm ComparisonCountingSort([0 −1],[0 −1])
a. Apply this algorithm to sorting the list 60, 35, 81, 98, 14, 47.
b. Is this algorithm stable?
c. Is it in place?
2. Name the algorithms for the searching problem that you already know.
13
a. State the problem as a graph problem.
b. Does this problem have a solution? If you believe it does, draw such
5. Icosian Game A century after Euler’s discovery (see Problem 4), an-
other famous puzzle–this one invented by the renown Irish mathemati-
6. Consider the following problem: Design an algorithm to determine the
best route for a subway passenger to take from one designated station to
another in a well-developed subway system similar to those in such cities
7. a. Rephrase the traveling salesman problem in combinatorial object terms.