This file contains the exercises, hints, and solutions for Chapter 2 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 2.1
1. For each of the following algorithms, indicate (i) a natural size metric for
its inputs, (ii) its basic operation, and (iii) whether the basic operation
count can be different for inputs of the same size:
a. computing the sum of numbers
2. a. Consider the definition-based algorithm for adding two ×matrices.
What is its basic operation? How many times is it performed as a function
of the matrix order ? As a function of the total number of elements in
the input matrices?
3. Consider a variation of sequential search that scans a list to return the
number of occurrences of a given search key in the list. Will its efficiency
differ from the efficiency of classic sequential search?
4. a. Glove selection There are 22 gloves in a drawer: 5 pairs of red gloves,
4 pairs of yellow, and 2 pairs of green. You select the gloves in the dark
1
5. a.BProve formula (2.1) for the number of bits in the binary representation
of a positive integer.
6. Suggest how any sorting algorithm can be augmented in a way to make
the best-case count of its key comparisons equal to just −1(is a list’s
size, of course). Do you think it would be a worthwhile addition to any
sorting algorithm?
7. Gaussian elimination, the classic algorithm for solving systems of linear
equations in unknowns, requires about 1
33multiplications, which is the
algorithm’s basic operation.
old computer?
8. For each of the following functions, indicate how much the function’s value
will change if its argument is increased fourfold.
2
10. Invention of chess a. According to a well-known legend, the game of
chess was invented many centuries ago in northwestern India by a certain
sage. When he took his invention to his king, the king liked the game so
much that he offered the inventor any reward he wanted. The inventor
Hints to Exercises 2.1
1. The questions are indeed as straightforward as they appear, though some
of them may have alternative answers. Also, keep in mind the caveat
about measuring an integer’s size.
2. a. The sum of two matrices is defined as the matrix whose elements are
the sums of the corresponding elements of the matrices given.
Then, take logarithms to base 2 of the terms in this inequality.
b. The proof is similar to the proof of formula (2.1).
c. The formula will be the same, with just one small adjustment to ac-
count for the different radix.
d. How can we switch from one logarithm base to another?
6. Insert a verification of whether the problem is already solved.
7. A similar question was investigated in the section.
4
Solutions to Exercises 2.1
1. The answers are as follows.
a. (i) ;(ii) addition of two numbers; (iii) no
b. (i) the magnitude of , i.e., the number of bits in its binary repre-
sentation; (ii) multiplication of two integers; (iii) no
2. a. Addition of two numbers. It’s performed 2times (once for each of
2elements in the matrix being computed). .Since the total number of
elements in two given matrices is =22the total number of additions
3. This algorithm will always make key comparisons on every input of size
whereasthisnumbermayvarybetweenand 1 for the classic version
of sequential search.
4. a. The best-case number is, obviously, two. The worst-case number is
twelve: one more than the number of gloves of one handedness.
5
5. a. The smallest positive integer that has binary digits in its binary
expansion is 100
|{z}
−1
which is 2−1;the largest positive integer that has
binary digits in its binary expansion is 111
|{z}
which is 2−1+2−2++1 =
b. If 0has bits in its binary representation, then, as shown in
part a,
2−1≤2
Hence
2−1+1≤2
c. =blog10 c+1=dlog10(+1)e
d. =blog2c+1 ≈log2=log
210 log10 ≈(log210),where=
6
6. Before applying a sorting algorithm, compare the adjacent elements of
its input: if ≤+1 for every =0 −2stop. Generally, it
7. a. (2)
()≈
1
3(2)3
1
33=8,whereis the time of one multiplication
8. a. log24−log2=(log
24+log
2)−log2=2
b. √4
√=2
9. a. (+1)≈2has the same order of growth (quadratic) as 20002to
within a constant multiple.
b. 1002(quadratic) has a lower order of growth than 0.013(cubic).
7
10. a. The total number of grains due to the inventor is
64
X
=1
2−1=
63
X
=0
2=2
64 −1≈18·1019
(It is many times more than one can get by planting with grain the entire
8
Exercises 2.2
1. Use the most appropriate notation among Θand Ωto indicate the
time efficiency class of sequential search (see Section 2.1)
2. Use the informal definitions of Θand Ωto determine whether the fol-
lowing assertions are true or false.
3. For each of the following functions, indicate the class Θ(()) the function
belongs to. (Use the simplest ()possible in your answers.) Prove your
assertions.
a. (2+1)
10 b. √102+7+3
4. a. Table 2.1 contains values of several functions that often arise in analysis
of algorithms. These values certainly suggest that the functions
5. Order the following functions according to their order of growth (from the
lowest to the highest):
(−2)!5lg(+ 100)102200014+33+1ln2,3
√ 3
9
7. Prove (by using the definitions of the notations involved) or disprove (by
givingaspecific counterexample) the following assertions.
a. If ()∈(())then ()∈Ω(())
8. BProve the section’s theorem for
9. We mentioned in this section that one can check whether all elements of an
array are distinct by a two-part algorithm based on the array’s presorting.
a. If the presorting is done by an algorithm with the time efficiency in
10. The range of a finite nonempty set of real numbers is defined as the
difference between the largest and smallest elements of For each repre–
sentation of given below, describe in English an algorithm to compute
the range. Indicate the time efficiency classes of these algorithms using
the most appropriate notation ( Θor Ω)
11. Lighterorheavier? You have 2identical-looking coins and a two-
pan balance scale with no weights. One of the coins is a fake, but you do
10
12. BDoor in a wall You are facing a wall that stretches infinitely in both
directions. There is a door in the wall, but you know neither how far
Hints to Exercises 2.2
1. Use the corresponding counts of the algorithm’s basic operation (see Sec-
tion 2.1) and the definitions of Θand Ω
2. Establish the order of growth of (+1)2first and then use the informal
definitions of Θand Ω. (Similar examples were given in the section.)
5. First simplify some of the functions. Then, use the list of functions
in Table 2.2 to “anchor” each of the functions given. Prove their final
placement by computing appropriate limits.
6. a. You can prove this assertion either by computing an appropriate limit
or by applying mathematical induction.
9. Follow the analysis plan used in the text when the algorithm was men-
tioned for the first time.
10. You may use straightforward algorithms for all the four questions asked.
Use the notation for the time efficiency class of one of them, and the Θ
12
Solutions to Exercises 2.2
1. a. Since ()= ()∈Θ()
b. Since ()=1
(1) ∈Θ(1)
3. a. Informally, (2+1)
10 ≈(2)10 =20 ∈Θ(20)Formally,
lim
→∞
(2+1)10
20 = lim
→∞
(2+1)10
(2)10 = lim
→∞ ³2+1
2´10 == lim
→∞ ¡1+ 1
2¢10 =1
Hence (2+1)
10 ∈Θ(20)
Note: An alternative proof can be based on the binomial formula and
the assertion of Exercise 6a.
3∈Θ(2)+Θ(3)=Θ(3)
e. Informally, blog2c≈log2∈Θ(log )Formally, by using the in-
equalities −1bc≤(see Appendix A), we obtain an upper bound
blog2c≤log2
and a lower bound
13
4. a. The order of growth and the related notations Ω,andΘdeal with
the asymptotic behavior of functions as goes to infinity. Therefore no
specific values of functions within a finite range of ’s values, suggestive
as they might be, can establish their orders of growth with mathematical
certainty.
5. (−2)! ∈Θ((−2)!)5lg(+ 100)10 =50lg(+ 100) ∈Θ(log )22=
(22)∈Θ(4)00014+33+1∈Θ(4)ln2∈Θ(log2)3
√∈
Θ(1
3)3∈Θ(3)The list of these functions ordered in increasing
order of growth looks as follows:
5lg(+ 100)10ln2 3
√ 00014+33+1322(−2)!
the order of growth of ()is larger than or equal to the order of growth
of ()The formal proof is immediate, too:
()≤()for all ≥0where 0
can be rewritten as
()≤1()for all ≥0(where 1= 0),
i.e., ()∈Θ(())
c. The assertion is obviously correct (similar to the assertion that =
if and only if ≤and ≥). The formal proof should show that
Θ(()) ⊆(()) ∩Ω(()) and that (()) ∩Ω(()) ⊆Θ(())
which immediately follow from the definitions of Ω,andΘ
15
8. a. We need to prove that if 1()∈Ω(1()) and 2()∈Ω(2()),then
1()+2()∈Ω(max{1()
2()}).
Proof Since 1()∈Ω(1())there exist some positive constant 1
and some nonnegative integer 1such that
Hence 1()+2()∈Ω(max{1()
2()}), with the constants and
0required by the definition being min{1
2}and max{1
2}re-
spectively.
9. a. Since the running time of the sorting part of the algorithm will still
dominate the running time of the second, it’s the former that will deter-
minethetimeefficiency of the entire algorithm. Formally, it follows from
equality
10. a. Scan the array to find the maximum and minimum values among its
elements and then compute the difference between them. The algorithm’s
time efficiency is Θ()Note: Although one can find both the maximum
and minimum values in an -element array with about 1.5comparisons
16
(see the solutions to Problem 5 in Exercises in 2.3 and Problem 2 in Ex-
ercises 5.1), it doesn’t change the linear efficiency class, of course.
d. The smallest (largest) element in a binary search tree is in the left-
most (rightmost) node. To reach it, one needs to start with the root and
follow the chain of left-child (right-child) pointers until a node with the
null left-child (right-child) pointer is reached. Depending on the structure
of the tree, this chain of nodes can be between 1 and nodes long. Hence,
the time of reaching its last node will be in ()The running time of the
entire algorithm will also be linear: ()+()+Θ(1) = ()
11. The puzzle can be solved in two weighings as follows. Start by taking
aside one coin if is odd and two coins if is even. After that divide the
remaining even number of coins into two equal-size groups and put them
on the opposite pans of the scale. If they weigh the same, all these coins
12. The key idea here is to walk intermittently right and left going each time
exponentially farther from the initial position. A simple implementation
of this idea is to do the following until the door is reached: For =01
17
18
Exercises 2.3
1. Compute the following sums.
a. 1+3+5+7+···+ 999
2. Find the order of growth of the following sums.
3. The sample variance of measurements 1
2 can be computed as
these formulas.
4. Consider the following algorithm.
Algorithm Mystery( )
//Input: A nonnegative integer
←0
19
d. What is the efficiency class of this algorithm?
5. Consider the following algorithm.
Algorithm Secret([0 −1])
Answer questions a—e of Problem 4 about this algorithm.
6. Consider the following algorithm.
Algorithm Enigma([0 −10 −1])
//Input: A matrix [0 −10 −1] of real numbers
7. Improve the implementation of the matrix multiplication algorithm (see
Example 3) by reducing the number of additions made by the algorithm.
What effect will this change have on the algorithm’s efficiency?
8. Determine the asymptotic order of growth for the total number of times all
the doors are toggled in the locker doors puzzle (Problem 12 in Exercises
1.1).
20