(a) Does the Hamming distance satisfy the three axioms of a distance
metric listed in Problem 4?
6. BOdd pie fight There are ≥3people positioned in a field (Euclidean
plane) so that each has a unique nearest neighbor. Each person has a
7. The closest-pair problem can be posed in -dimensional space in which
the Euclidean distance between two points 0(0
1 0
)and 00(00
1 00
)
is defined as
8. Find the convex hulls of the following sets and identify their extreme points
(if they have any).
9. Design a linear-time algorithm to determine two extreme points of the
convex hull of a given set of 1points in the plane.
10. What modification needs to be made in the brute-force algorithm for the
convex-hull problem to handle more than two points on the same straight
line?
21
a. Sketch, in the Cartesian plane, the problem’s feasible region de-
fined as the set of points satisfying all the problem’s constraints.
22
Hints to Exercises 3.3
1. You may want to consider two versions of the answer: without taking into
2. Sorting real numbers can be done in (log )time.
4. a. Check requirements (i)—(iii) by using basic properties of absolute values.
b. For the Manhattan distance, the points in question are defined by
5. a. Prove that the Hamming distance does satisfy the three axioms of a
distance metric.
b. Your answer should include two parameters.
10. If there are other points of a given set on the straight line through and
, which of all these points need to be preserved for further processing?
11. Your program should work for any set of distinct points, including sets
with many colinear points.
23
Solutions to Exercises 3.3
1. If we take into account only the arithmetical operations involved into
computing the Euclidean distance between two points versus computing
2. Sort the numbers in ascending order, compute the differences between ad-
jacent numbers in the sorted list, and find the smallest such difference. If
3. a. If we put the post office at location the average distance between it
and all the points 1
2 is given by the formula 1
P
=1 |−
is minimized when belongs to each of the intervals [1
]⊃[2
−1]⊃ ⊃
[2
2+1]If must be one of the points given, either 2or 2+1 solves
the problem.
Let 1be odd. Then, the sum P
=1 |−|is minimized when =
b. Assuming that the points 1
2 are given in increasing order, the
answer is the point that is the closest to =(1+)2themiddlepoint
between 1and (The middle point would be the obvious solution if the
25
Algorithm PostOffice1 ()
//Input: List of (≥2) points 1
2 in increasing order
//Output: Point that minimizes max
1≤≤|−|among all 1
2
4. a. For (1
2)=|1−2|+|1−2|we have the following:
b. For the Manhattan distance, the points in question are defined by
the equation
|−0|+|−0|=1i.e., ||+||=1
26
c. False. Consider points 1(00)
2(10)and, say, 3(1
23
4)Then
5. a. Since the first two axioms of a metric is obviously satisfied for the
Hamming distance, only the third one–the triangle inequality–needs a
proof. It can be obtained by mathematical induction on the string length
If =1the inequality (1
2)≤(1
3)+(3
2)holds
b. Since the basic operation of the algorithm is comparing two char-
acters in the strings of length , the worst-case time efficiency class will
be Θ(2)
6. We’ll prove by induction that there will always remain at least one person
not hit by a pie. The basis step is easy: If =3the two persons with
the smallest pairwise distance between them throw at each other, while
27
7. The number of squarings will be
−1
X
X
X
−1
X
X
−1
X
8. a. The convex hull of a line segment is the line segment itself; its extreme
points are the endpoints of the segment.
b. The convex hull of a square is the square itself; its extreme points
are the four vertices of the square.
9. Find the point with the smallest coordinate; if there are several such
points, find the one with the smallest coordinate among them. Similarly,
find the point with the largest coordinate; if there are several such points,
10. If there are other points of a given set on the straight line through and
(while all the other points of the set lie on the same side of the line), a
11. n/a
12. a. Here is a sketch of the feasible region in question:
y
b. The extreme points are: (00)(4,0), (3,1), and (0,2).
c.
Extreme point Value of 3+5
(0,0) 0
29
Exercises 3.4
1. a. Assuming that each tour can be generated in constant time, what will
be the efficiency class of the exhaustive-search algorithm outlined in the
text for the traveling salesman problem?
2. Outline an exhaustive-search algorithm for the Hamiltonian circuit prob-
lem.
3. Outline an algorithm to determine whether a connected graph represented
5. Give an example of the assignment problem whose optimal solution does
not include the smallest element of its cost matrix.
6. Consider the partition problem:givenpositive integers, partition
them into two disjoint subsets with the same sum of their elements. (Of
course, the problem does not always have a solution.) Design an exhaus-
tive search algorithm for this problem. Try to minimize the number of
subsets the algorithm needs to generate.
9. Eight-queens problem Consider the classic puzzle of placing eight queens
on an 8×8chessboard so that no two queens are in the same row or in
the same column or on the same diagonal. How many ways are there so
that
10. A magic square of order is an arrangement of the integers from 1 to 2
in an ×matrix, with each number occurring exactly once, so that each
row, each column, and each main diagonal has the same sum.
a. Prove that if a magic square of order exists, the sum in question
11. Famous alphametic A puzzle in which the digits in a correct mathemati-
cal expression, such as a sum, are replaced by letters is called cryptarithm;
if, in addition, the puzzle’s words make sense, it is said to be an al-
phametic. The most well-known alphametic was published by the renowned
British puzzlist Henry E. Dudeney (1857-1930):
Hints to Exercises 3.4
1. a. Identify the algorithm’s basic operation and count the number of times
it will be executed.
2. How different is the traveling salesman problem from the problem of find-
ing a Hamiltonian circuit?
3. Your algorithm should check the well-known conditions that are both nec-
essary and sufficient for the existence of a Eulerian circuit in a connected
graph.
7. Follow the definitions of a clique and of an exhaustive-search algorithm.
8. Try all possible orderings of the elements given.
9. Use common formulas of elementary combinatorics.
32
Solutions to Exercises 3.4
1. a. Θ(!)
For each tour (a sequence of +1 cities), one needs additions to compute
the tour’s length. Hence, the total number of additions ()will be
2. The problem of finding a Hamiltonian circuit is very similar to the travel-
ing salesman problem. Generate permutations of vertices that start and
3. A connected graph has a Eulerian circuit if and only if all its vertices
have even degrees. An algorithm should check this condition until either
an odd vertex is encountered (then a Eulerian circuit doesn’t exist) or
4. The following assignments were generated in the chapter’s text:
⎡
9278
⎤
1, 2, 3, 4 cost = 9+4+1+4 = 18
1, 2, 4, 3 cost = 9+4+8+9 = 30