This file contains the exercises, hints, and solutions for Chapter 6 of the
book ”Introduction to the Design and Analysis of Algorithms,” 3rd edition, by
Exercises 6.1
1. Consider the problem of finding the distance between the two closest num-
bers in an array of numbers. (The distance between two numbers and
2. Let ={1…
}and ={1 }be two sets of numbers. Consider
3. Consider the problem of finding the smallest and largest elements in an
array of numbers.
4. Estimate how many searches will be needed to justify time spent on pre-
sorting an array of 103elements if sorting is done by mergesort and search-
ing is done by binary search. (You may assume that all searches are for
elements known to be in the array.) What about an array of 106elements?
5. To sort or not to sort? Design a reasonably efficient algorithm for solving
6. BGiven a set of ≥3points in the Cartesian plane, connect them in a
simple polygon, i.e., a closed path through all the points so that its line
segments (the polygon’s edges) do not intersect (except for neighboring
edges at their common vertex). For example,
P
3
P
6
P
1
P
3
P
6
P
1
7. BYou have an array of numbers and a number .Findoutwhether
the array contains two elements whose sum is (For example, for the
8. BYou have a list of open intervals (1
1)(2
2)…, (
)on the
realline. (Anopeninterval( )comprises all the points strictly between
9. Number placement Given a list of distinct integers and a sequence of
boxes with pre-set inequality signs inserted between them, design an algo-
rithm that places the numbers into the boxes to satisfy those inequalities.
2
10. BMaxima searching
a. A point (
)in the Cartesian plane is said to be dominated by point
(
)if ≤and ≤with at least one of the two inequalities being
strict. Given a set of points, one of them is said to be a maximum of
the set if it is not dominated by any other point in the set. For example,
in the figure below, all the maximum points of the set of ten points are
circled.
y
b. Give a few real-world applications of this algorithm.
11. BAnagram detection
a. Design an efficient algorithm for finding all sets of anagrams in a large
Hints to Exercises 6.1
1. This problem is similar to one of the examples in this section.
2. a. Compare every element in one set with all the elements in the other.
3. a. How do we find the smallest and largest elements in a sorted list?
4. Use the known results about the average-case comparison numbers of the
algorithms in this question.
5. a. The problem is similar to one of the preceding problems in these exer-
cises.
6. a. Many problems of this kind have exceptions for one particular config-
uration of points. As to the question about a solution’s uniqueness, you
7. It helps to think about real numbers as ordered points on the real line.
Considering the special case of =0with a given array containing both
negative and positive numbers, might be helpful, too.
8. After sorting the ’s and ’s, the problem can be solved in linear time.
Solutions to Exercises 6.1
1. a. Sort the array first and then scan it to find the smallest difference
between two successive elements []and [+1](0≤≤−2).
b. The time efficiency of the brute-force algorithm is in Θ(2)because
2. a. Initialize a list to contain elements of =∩to empty. Compare
every element in with successive elements of :if=,addthis
value to the list and proceed to the next element in (In fact, if
=
need not be compared with the remaining elements in and
Note that the efficiency formula implies that it is more efficient to sort the
smaller one of the two input sets.
Second solution: Sort the lists representing sets and , respectively.
Scan the lists in the mergesort-like manner but output only the values
5
3. a. Sort the list and return its first and last elements as the values of
the smallest and largest elements, respectively. Assuming the efficiency
4. Let be the smallest number of searches needed for the sort—binary search
algorithm to make fewer comparisons than searches by sequential search
(for average successful searches). Assuming that a sorting algorithm
makes about log comparisons on the average and using the formulas
for the average number of key comparisons for binary search (about log2)
5. a. The following algorithm will beat the brute-force comparisons of the
telephone numbers on the bills and the checks: Using an efficient sorting
algorithm, sort the bills and sort the checks. (In both cases, sorting has
6
to be done with respect to their telephone numbers, say, in increasing or-
6. a. The problem has a solution if and only if all the points don’t lie on the
same line. And, if a solution exists, it may not be unique.
b. Find the lowest point ∗i.e., the one with the smallest coordi-
nate. in the set. (If there is a tie, take, say, the leftmost among them,
i.e., the one with the smallest coordinate.) For each of the other −1
7. Assume first that =0Then []+[]=0if and only if []=−[]
i.e., these two elements have the same absolute value but opposite signs.
Wecancheckforpresenceofsuchelementsinagivenarrayinseveraldif–
ferent ways. If all the elements are known to be distinct, we can simply
The case of an arbitrary value of isreducedtothecaseof=0by the fol–
lowing substitution: []+[]=if and only if ([]−2)+([]−2) =
0In other words, we can start the algorithm by subtracting 2from
each element and then proceed as described above.
8. Sort all the ’s and ’s by a (log )algorithm in a single nondecreas-
ing list, treating as if it were smaller than in case of the tie =
Scan the list left to right computing the running difference between
the number of ’s and ’s seen so far. In other words, initialize to 0
9. Start by sorting the list in increasing order. Then repeat the following
−1times: If the first inequality sign is ““, place the first (smallest)
10. a. Sort the points in nondecreasing order of their -coordinates resolving
ties by listing first a point with a smaller -coordinate. Then scan the
sorted list right to left outputting the points with the strictly largest –
coordinate seen so far during this scan. All the outputted points and only
them are the maximum points of the set.
y
11. First, attach to every word in the file–as another field of the word’s record,
for example–its signature defined as the string of the word’s letters in al-
phabetical order. Obviously, words belong to the same anagram set if and
9
only if they have the same signature. Sort the records in alphabetical or-
der of their signatures. Scan the list to identify contiguous subsequences,
of length greater than one, of records with the same signature.
10
Exercises 6.2
1. Solve the following system by Gaussian elimination.
2. a. Solve the system of the previous question by the decomposition
method.
4. Would it be correct to get the efficiency class of the elimination stage of
Gaussian elimination as follows?
5. Write pseudocode for the back-substitution stage of Gaussian elimination
and show that its running time is in Θ(2)
6. Assuming that division of two real numbers takes three times longer than
7. a. Give an example of a system of two linear equations in two unknowns
that has a unique solution and solve it by Gaussian elimination.
8. The Gauss-Jordan elimination method differs from Gaussian elimina-
tion in that the elements above the main diagonal of the coefficient matrix
are made zero at the same time and by the same use of a pivot row as the
elements below the main diagonal.
9. A system =of linear equations in unknowns has a unique solution
if and only if det 6=0Is it a good idea to check this condition before
applying Gaussian elimination to the system?
10. a. Apply Cramer’s rule to solve the system of Problem 1 of these exercises.
b. Estimate how many times longer it will take to solve a system of
11. ILights out This one-person game is played on an ×board composed
of 1×1light panels. Each panel has a switch that can be turned on
and off, thereby toggling the on/offstate of this and four vertically and
horizontally adjacent panels. (Of course, toggling a corner square affects
Hints to Exercises 6.2
1. Trace the algorithm as we did in solving another system in the section.
2. a. Use the Gaussian elimination results as explained in the text.
4. Though the final answer is correct, its derivation contains an error you
have to find.
5. Pseudocode of this algorithm is quite straightforward. If you are in doubt,
6. Estimate the ratio of the algorithm running times by using the approxi-
7. a. This is a “normal” case: one of the two equations should not be pro-
portional to the other.
8. a. Manipulate the matrix rows above a pivot row the same way the rows
below the pivot row are changed.
b. Are the Gauss-Jordan method and Gaussian elimination based on the
same algorithm design technique or on different ones?
9. How long will it take to compute the determinant compared to the time
needed to apply Gaussian elimination to the system?
10. a. Apply Cramer’s rule to the system given.
b. How many distinct determinants are there in the Cramer’s rule for-
mulas?
11. a. If is the number of times the panel in the th row and th column
needs to be toggled in a solution, what can be said about ?Afteryou
Solutions to Exercises 6.2
1. a. Solve the following system by Gaussian elimination
1+2+3=2
21+2+3=3
1−2+33=8
⎡
111 2
⎤
2. a. Repeating the elimination stage (or using its results obtained in Prob-
lem 1), we get the following matrices and :
=⎡
⎣
100
210
121
⎤
⎦=⎡
⎣
111
0−1−1
004
⎤
⎦
3. Solving simultaneously the system with the three right-hand side vectors:
⎡
⎣
111100
211010
⎤
⎦row 2 – 2
1row 1
Solving the system with the first right-hand side column
⎡
⎣
1
−2
3
⎤
⎦
yields the following values of the first column of the inverse matrix:
⎡
⎣
−1
5
4
3
4
⎤
⎦
Solving the system with the second right-hand side column
16
yields the following values of the third column of the inverse matrix:
⎡
⎣
0
−1
4
1
4
⎤
⎦
Thus, the inverse of the coefficient matrix is
4. In general, the fact that 1()∈Θ(3)
2()∈Θ(3)and 3()∈Θ(3)
5. Algorithm GaussBackSub([1 1 +1])
//Implements the backward substitution stage of Gaussian elimination
//by solving a given system with an upper-triangular coefficient matrix
The basic operation is multiplication of two numbers. The number of
times it will be executed is given by the sum
17
6. Let ()()and ()()be the numbers of divisions and multiplications
made by GaussElimination, respectively. Using the count formula derived
in Section 6.2, we obtain the following approximate counts:
Let and be the times of one division and of one multiplication,
respectively. We can estimate the ratio of the running times of the two
algorithms as follows:
7. a. The elimination stage should yield a 2-by-2 upper-triangular matrix
with nonzero coefficients on its main diagonal.
8. a. Solve the following system by the Gauss-Jordan method
1+2+3=2
21+2+3=3
1−2+33=8
⎡
⎤
⎡
⎤
0048
4row 3
0048
18
We obtain the solution by dividing the right hand side values by the cor-
responding elements of the diagonal matrix:
1=11=1
2=1−1=−1
3=84=2
b. The Gauss-Jordan method is also an example of an algorithm based
c. Here is a basic pseudocode for the Gauss-Jordan elimination:
Algorithm GaussJordan([1 1][1])
//Applies Gaussian-Jordan elimination to matrix of a system’s
The number of multiplications made by the above algorithm can be com-
puted as follows:
which is about 1.5 smaller than in the Gauss-Jordan method.
19
9. Since the time needed for computing the determinant of the system’s coef-
ficient matrix is about the same as the time needed for solving the system
10. a. Solve the following system by Cramer’s rule:
1+2+3=2
21+2+3=3
1−2+33=8
Hence,
1=|1|
||=−4
−4=1
2=|2|
||=4
−4=−1
3=|3|
||=−8
−4=2
b. Cramer’s rule requires computing +1distinct determinants. If each
20