8. Consider the following map:
a
b
c
d
9. Design an algorithm for the following problem: Given a set of points
in the Cartesian plane, determine whether all of them lie on the same
circumference.
10. Write a program that reads as its inputs the ( )coordinates of the
15
Hints to Exercises 1.3
1. Trace the algorithm on the input given. Use the definitions of stability
and being in-place that were introduced in the section.
5. No efficient algorithm for solving this problem for an arbitrary graph is
known. This particular graph does have Hamiltonian circuits that are
not difficult to find. (You need to find just one of them.)
6. a. Put yourself (mentally) in a passenger’s place and ask yourself what
criterion for the “best” route you would use. Then think of people that
may have different needs.
8. Create a graph whose vertices represent the map’s regions. You will have
to decide on the edges on your own.
9. Assume that the circumference in question exists and find its center first.
Also, do not forget to give a special answer for ≤2
Solutions to Exercises 1.3
1. a. Sorting 60, 35, 81, 98, 14, 47 by comparison counting will work as
follows:
Array [05] 60 35 81 98 14 47
Initially [] 0 0 0 0 0 0
After pass =0 [] 3 0 1 1 0 0
b. The algorithm is not stable. Consider, as a counterexample, the
result of its application to 10,100
2. Answers may vary but most students should be familiar with sequential
3. Align the pattern with the beginning of the text. Compare the corre-
sponding characters of the pattern and the text left-to right until either
4. a. If we represent each of the river’s banks and each of the two islands by
17
vertices and the bridges by edges, we will get the following graph:
b
a
c
d
b
a
c
d
(This is, in fact, a multigraph, not a graph, because it has more than
one edge between the same pair of vertices. But this doesn’t matter for
not return to its starting vertex, it is called an Eulerian path.
b. Euler proved that an Eulerian circuit exists in a connected (multi)graph
if and only if all its vertices have even degrees, where the degree of a ver-
tex is defined as the number of edges for which it is an endpoint. Also,
an Eulerian path exists in a connected (multi)graph if and only if it has
18
the walk −−−−−−−−
a
a
If we want a walk that returns to its starting point, all the vertices in
the corresponding multigraph must be even. Since a new bridge/edge
changes the parity of two vertices, at least two new bridges/edges will be
needed. For example, here is one such “enhancement”:
a
a
19
5. A Hamiltonian circuit is marked on the graph below:
6. a. At least three “reasonable”criteria come to mind: the fastest trip, a
trip with the smallest number of train stops, and a trip that requires the
smallest number of train changes. Note that the first criterion requires
the information about the expected traveling time between stations and
7. a. Find a permutation of given cities for which the sum of the distances
between consecutive cities in the permutation plus the distance between
its last and first city is as small as possible.
20
is the graph for the map given:
b
b
ad
Solving the graph coloring problem for this graph yields the map’s color-
ing with the smallest number of colors possible.
b. Without loss of generality, we can assign colors 1 and 2 to vertices
and , respectively. This forces the following color assignment to the
9. If =2, the answer is always “yes”; so, we may assume that ≥3
Select three points 1
2and 3from the set given. Write an equation
of the perpendicular bisector 1ofthelinesegmentwiththeendpointsat
1and 2, which is the locus of points equidistant from 1and 2.Write
21
Exercises 1.4
1. Describe how one can implement each of the following operations on an
array so that the time it takes does not depend on the array’s size .
2. If you have to solve the searching problem for a list of numbers, how
can you take advantage of the fact that the list is known to be sorted?
3. a. Show the stack after each operation of the following sequence that
starts with the empty stack:
4. a. Let be the adjacency matrix of an undirected graph. Explain what
property of the matrix indicates that
i. the graph is complete.
5. Give a detailed description of an algorithm for transforming a free tree
into a tree rooted at a given vertex of the free tree.
6. Prove the inequalities that bracket the height of a binary tree with
22
b. a sorted array.
c. a binary search tree.
8. How would you implement a dictionary of a reasonably small size if
you knew that all its elements are distinct (e.g., names of 50 states of the
United States)? Specify an implementation of each dictionary operation.
9. For each of the following applications, indicate the most appropriate data
structure:
a. answering telephone calls in the order of their known priorities.
23
Hints to Exercises 1.4
1. a. Take advantage of the fact that the array is not sorted.
b. We used this trick in implementing one of the algorithms in Section
1.1.
4. Just use the definitions of the graph properties in question and data struc-
tures involved.
5. There are two well-known algorithms that can solve this problem. The
first uses a stack, the second uses a queue. Although these algorithms
are discussed later in the book, do not miss this chance to discover them
by yourself!
6. The inequality ≤−1follows immediately from the height’s definition.
8. Because of insertions and deletions, using an array of the dictionary’s
elements (sorted or unsorted) is not the best implementation possible.
9. You need to know about the postfix notation in order to answer one of
24
Solutions to Exercises 1.4
1. a. Replace the th element with the last element and decrease the array
size by 1.
2. a. Use binary search (see Section 4.4 if you are not familiar with this
3. a.
()() ()()
4. a. For the adjacency matrix representation:
i. A graph is complete if and only if all the elements of its adjacency
matrix except those on the main diagonal are equal to 1, i.e., [ ]=1
for every 1≤ ≤ 6=
25
vertex defining the list.
5. The first algorithm works as follows. Mark a vertex to serve as the root
of the tree, make it the root of the tree to be constructed, and initialize
a stack with this vertex. Repeat the following operation until the stack
becomes empty: If there is an unmarked vertex adjacent to the vertex on
6. Since the height is defined as the length of the longest simple path from
the tree’s root to its leaf, such a pass will include no more than vertices,
which is the total number of vertices in the tree. Hence, ≤−1
Thebinarytreeofheightwith the largest number of vertices is the full
7. a. Insertion can be implemented by adding the new item after the ar-
ray’s last element. Finding the largest element requires a standard scan
26
4.4.) In the former case, the new item is inserted before []by first mov-
ing [−1] []one position to the right; in the latter case, the new
item is simply appended after the last element of the array. Finding the
largest element is done by simply returning the value of the last element
8. Use a bit vector, i.e., an array on bits in which the th bit is 1 if
9. Use: (a) a priority queue; (b) a queue; (c) a stack (and reverse Polish
10. The most straightforward solution is to search for each successive letter
of the first word in the second one. If the search is successful, delete the
first occurrence of the letter in the second word, stop otherwise.
them in a simple parallel scan.
We can also generate and compare “letter vectors” of the given words:
28