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
A. Levitin. The problems that might be challenging for at least some students
are marked by B; those that might be difficult for a majority of students are
marked by I
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.
2. Given that the official purpose of the U.S. patent system is the promo-
tion of the “useful arts,” do you think algorithms are patentable in this
country? Should they be?
3. a. Write down driving directions for going from your school to your home
with the precision required from an algorithm’s description.
b. Write down a recipe for cooking your favorite dish with the precision
required by an algorithm.
√
4. Design an algorithm for computing b c for any positive integer . Be-
sides assignment and comparison, your algorithm may only use the four
basic arithmetical operations.
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?
6. a. Find gcd(31415, 14142) by applying Euclid’s algorithm.
b. Estimate how many times faster it will be to find gcd(31415, 14142)
by Euclid’s algorithm compared with the algorithm based on checking
consecutive integers from min{ } down to gcd( )
7. B Prove the equality gcd( ) = gcd( mod ) for every pair of positive
integers and .
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?
9. a. What is the minimum number of divisions made by Euclid’s algorithm
among all inputs 1 ≤ ≤ 10?
1
, 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.
b. I Euclid’s game (see [Bog]) starts with two unequal positive in-
tegers on the board. Two players move in turn. On each move, a player
has to write on the board a positive number equal to the difference of two
numbers already on the board; this number must be new, i.e., different
from all the numbers already on the board. The player who cannot move
loses the game. Should you choose to move first or second in this game?
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 , such that + =
a. Look up a description of the extended Euclid’s algorithm (see, e.g.,
[KnuI, p. 13]) and implement it in the language of your choice.
b. Modify your program to find integer solutions to the Diophantine
equation + = with any set of integer coefficients , , and .
12. B Locker doors There are lockers in a hallway, numbered sequentially
from 1 to . Initially, all the locker doors are closed. You make passes
by the lockers, each time starting with locker #1. On the th pass, =
1 2 , you toggle the door of every th locker: if the door is closed, you
open it; if it is open, you close it. After the last pass, which locker doors
are open and which are closed? How many of them are open?
2
, Hints to Exercises 1.1
1. It is probably faster to do this by searching the Web, but your library
should be able to help, too.
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
than a machine. Still, make sure that your descriptions do not contain
obvious ambiguities. Knuth provides an interesting comparison between
cooking recipes and algorithms [KnuI, p.6].
4. There is a quite
√ straightforward algorithm for this problem based on the
definition of b c.
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
positive integers and ), then it also divides both and = mod
and vice versa Use the formula = + (0 ≤ ) and the fact that
if divides two integers and it also divides + and − (Why?)
8. Perform one iteration of the algorithm for two arbitrarily chosen integers
9. The answer to part (a) can be given immediately; the answer to part
(b) can be given by checking the algorithm’s performance on all pairs
1 ≤ 10
10. a. Use the equality
gcd( ) = gcd( − ) for ≥ 0
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 = 1 and = 2
should help, too.
11. Of course, for some coefficients, the equation will have no solutions.
12. Tracing the algorithm by hand for, say, = 10 and studying its outcome
should help answering both questions.
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
Arabic title of this book while the word “algorithm” is derived from a
translation of Al-Khwarizmi’s last name (see, e.g., [KnuI, pp. 1-2], [Knu96,
pp. 88-92, 114]).
2. This legal issue has yet to be settled. The current legal state of affairs
distinguishes mathematical algorithms, which are not patentable, from
other algorithms, which may be patentable if implemented as computer
programs (e.g., [Cha00]).
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
integers until the first square exceeding is encountered. The answer will
be the number’s immediate predecessor. Note: A much faster algorithm
for solving this problem can be obtained by using Newton’s method (see
Sections 11.4 and 12.4).
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,
add this element to the list of common elements and move to the next
elements of both lists (if any); otherwise, move to the element following
the smaller of the two involved in the comparison.
The maximum number of comparisons, which is made by this algorithm
on some lists with no common elements such as the first positive odd
numbers and the first positive even numbers, is equal to + − 1
6. a. gcd(31415 14142) = gcd(14142 3131) = gcd(3131 1618) =
gcd(1618 1513) = gcd(1513 105) = gcd(1513 105) = gcd(105 43) =
gcd(43 19) = gcd(19 5) = gcd(5 4) = gcd(4 1) = gcd(1 0) = 1
b. To answer the question, we need to compare the number of divisions
the algorithms make on the input given. The number of divisions made
by Euclid’s algorithm is 11 (see part a). The number of divisions made
by the consecutive integer checking algorithm on each of its 14142 itera-
tions is either 1 and 2; hence the total number of multiplications is be-
tween 1·14142 and 2·14142. Therefore, Euclid’s algorithm will be between
1·1414211 ≈ 1300 and 2·1414211 ≈ 2600 times faster.
4
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
A. Levitin. The problems that might be challenging for at least some students
are marked by B; those that might be difficult for a majority of students are
marked by I
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.
2. Given that the official purpose of the U.S. patent system is the promo-
tion of the “useful arts,” do you think algorithms are patentable in this
country? Should they be?
3. a. Write down driving directions for going from your school to your home
with the precision required from an algorithm’s description.
b. Write down a recipe for cooking your favorite dish with the precision
required by an algorithm.
√
4. Design an algorithm for computing b c for any positive integer . Be-
sides assignment and comparison, your algorithm may only use the four
basic arithmetical operations.
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?
6. a. Find gcd(31415, 14142) by applying Euclid’s algorithm.
b. Estimate how many times faster it will be to find gcd(31415, 14142)
by Euclid’s algorithm compared with the algorithm based on checking
consecutive integers from min{ } down to gcd( )
7. B Prove the equality gcd( ) = gcd( mod ) for every pair of positive
integers and .
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?
9. a. What is the minimum number of divisions made by Euclid’s algorithm
among all inputs 1 ≤ ≤ 10?
1
, 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.
b. I Euclid’s game (see [Bog]) starts with two unequal positive in-
tegers on the board. Two players move in turn. On each move, a player
has to write on the board a positive number equal to the difference of two
numbers already on the board; this number must be new, i.e., different
from all the numbers already on the board. The player who cannot move
loses the game. Should you choose to move first or second in this game?
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 , such that + =
a. Look up a description of the extended Euclid’s algorithm (see, e.g.,
[KnuI, p. 13]) and implement it in the language of your choice.
b. Modify your program to find integer solutions to the Diophantine
equation + = with any set of integer coefficients , , and .
12. B Locker doors There are lockers in a hallway, numbered sequentially
from 1 to . Initially, all the locker doors are closed. You make passes
by the lockers, each time starting with locker #1. On the th pass, =
1 2 , you toggle the door of every th locker: if the door is closed, you
open it; if it is open, you close it. After the last pass, which locker doors
are open and which are closed? How many of them are open?
2
, Hints to Exercises 1.1
1. It is probably faster to do this by searching the Web, but your library
should be able to help, too.
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
than a machine. Still, make sure that your descriptions do not contain
obvious ambiguities. Knuth provides an interesting comparison between
cooking recipes and algorithms [KnuI, p.6].
4. There is a quite
√ straightforward algorithm for this problem based on the
definition of b c.
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
positive integers and ), then it also divides both and = mod
and vice versa Use the formula = + (0 ≤ ) and the fact that
if divides two integers and it also divides + and − (Why?)
8. Perform one iteration of the algorithm for two arbitrarily chosen integers
9. The answer to part (a) can be given immediately; the answer to part
(b) can be given by checking the algorithm’s performance on all pairs
1 ≤ 10
10. a. Use the equality
gcd( ) = gcd( − ) for ≥ 0
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 = 1 and = 2
should help, too.
11. Of course, for some coefficients, the equation will have no solutions.
12. Tracing the algorithm by hand for, say, = 10 and studying its outcome
should help answering both questions.
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
Arabic title of this book while the word “algorithm” is derived from a
translation of Al-Khwarizmi’s last name (see, e.g., [KnuI, pp. 1-2], [Knu96,
pp. 88-92, 114]).
2. This legal issue has yet to be settled. The current legal state of affairs
distinguishes mathematical algorithms, which are not patentable, from
other algorithms, which may be patentable if implemented as computer
programs (e.g., [Cha00]).
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
integers until the first square exceeding is encountered. The answer will
be the number’s immediate predecessor. Note: A much faster algorithm
for solving this problem can be obtained by using Newton’s method (see
Sections 11.4 and 12.4).
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,
add this element to the list of common elements and move to the next
elements of both lists (if any); otherwise, move to the element following
the smaller of the two involved in the comparison.
The maximum number of comparisons, which is made by this algorithm
on some lists with no common elements such as the first positive odd
numbers and the first positive even numbers, is equal to + − 1
6. a. gcd(31415 14142) = gcd(14142 3131) = gcd(3131 1618) =
gcd(1618 1513) = gcd(1513 105) = gcd(1513 105) = gcd(105 43) =
gcd(43 19) = gcd(19 5) = gcd(5 4) = gcd(4 1) = gcd(1 0) = 1
b. To answer the question, we need to compare the number of divisions
the algorithms make on the input given. The number of divisions made
by Euclid’s algorithm is 11 (see part a). The number of divisions made
by the consecutive integer checking algorithm on each of its 14142 itera-
tions is either 1 and 2; hence the total number of multiplications is be-
tween 1·14142 and 2·14142. Therefore, Euclid’s algorithm will be between
1·1414211 ≈ 1300 and 2·1414211 ≈ 2600 times faster.
4
