R-7.1 Suppose we have a social network with members A, B, C, D, E, F,andG,and
the set of friendship ties,
{(A,B),(B,C),(C,A),(D,E),(F,G)}.
What are the connected components?
R-7.2 Suppose a social network, N,containsn people, m edges, and c connected com-
ponents. What is the exact number of times that each of the methods, makeSet,
union,andfind,arecalledincomputingtheconnectedcomponentsforN using
Algorithm 7.2?
R-7.3 How many walls were erased to construct the maze in Figure 7.3, not counting
the start and finish walls?
R-7.4 For the sake of analysis, if we have a sequence of union, find,andmakeSet op-
erations, why can we can assume without loss of generality that all the makeSet
operations come first?
R-7.5 One additional feature of the list-based implementation of a union-find structure
is that it allows for the contents of any set in a partition to be listed in time
proportional to the size of the set. Describe how this can be done.
R-7.6 Suppose we have 20 singleton sets, numbered 0 through 19,andwecallthe
operation union(find(i),find(i +5)), for i =0,1,2,...,14.Drawapictureofa
list-based representation of the sets that result.
R-7.7 Suppose we have 20 singleton sets, numbered 0 through 19,andwecallthe
operation union(find(i),find(i +5)), for i =0,1,2,...,14. Draw a picture of
atree-basedrepresentationofthesetsthatresult,assumingwedon’timplement
the union-by-size and path compression heuristics.
R-7.8 Answer the previous exercise assuming that we implement both the union-by-
size and path compression heuristics.
Creativity
C-7.1 Describe how to implement a union-find structure using extendable arrays, which
each contains the elements in a single set, instead of linked lists. Show how this
solution can be used to process a sequence of m union-find operations on an
initial collection of n singleton sets in O(nlogn+m) time.
C-7.2 Consider a method, remove(e),whichremovese from whichever list it belongs
to, in a list-based implementation of a union-find structure. Describe how to
modify the list-based implementation so that this method runs in timeO(1).
222 Chapter 7. Union-Find Structures
AConnectedComponentsAlgorithm
We give a pseudocode description of an algorithm for solving the connected compo-
nents problem using a union-find structure in Algorithm 7.2. The output from this
algorithm is an identification, for each person x in S, of the connected component
to which x belongs. For instance, for the social network shown in Figure 7.1, the
output would identify Lafayette, Rochambeau, George Washington, John Adams,
and Abigail Adams as belonging to the “Washington” connected component, and
Charles Cornwallis and Benedict Arnold as belonging to the “Cornwallis” con-
nected component.
Algorithm UFConnectedComponents(S,E):
Input: A set, S, of n people and a set, E,ofm pairs of people from S defining
pairwise relationships
Output: An identification, for each x in S, of the connected component con-
taining x
for each x in S do
makeSet(x)
for each (x,y) in E do
if find(x) ̸= find(y) then
union(find(x), find(y))
for each x in S do
Output “Person x belongs to connected component” find(x)
Algorithm 7.2: Aconnectedcomponentsalgorithmusingunion and find.
This algorithm’s efficiency depends on how we implement the union-find struc-
ture, of course. If performing a sequence of m union and find operations, starting
with n singleton sets created with the makeSet method, takes O(t(n,m)) time,
then the running time of the UFConnectedComponents algorithm can be char-
acterized as being O(t(n,n + m)),sincewedotwofind operations for each edge
in E and then one find operation for each of the n members of S. Using the imple-
mentations described in this chapter, we can achieve a running time that is either
O((n+m)logn), using a list-based implementation, or “almost” O(n+m), using
a tree-based implementation.
As we explore in Chapter 13, if we are given the set E in sorted order (say, ac-
cording to a lexicographic ordering), then we can actually design a connected com-
ponentsalgorithmthatrunsinO(n+m)time. ButtheUFConnectedComponents
algorithm is the fastest way we know of for solving the connected components
problem if we cannot make any assumptions about the ordering of E and we only
get to scan through it once.
Hint: Note that the exact number, not the order, is required. This umber should be expressed in
terms of n;m and c. Do not omit the nd calls within union( nd(x); nd(y)). (This duplication of
work could have been avoided but, nevertheless, you need to analyze the algorithm as given.)
2. (10pt) Given an array A of n integers, give anO(n) in-place algorithm to arrange the numbers such
that all the even ones come before all the odd ones.
3. (10pt) Problem C-9.3 from textbook. Pseudocode not required. Explain only the idea.
9.4. Exercises 279
9.4 Exercises
Reinforcement
R-9.1 Which, if any, of the algorithms bubble-sort, heap-sort, merge-sort, and quick-
sort are stable?
R-9.2 Describearadix-sortmethodforlexicographicallysortingasequenceS oftriplets
(k,l,m),wherek, l,andm are integers in the range [0,N−1],forsomeN ≥ 2.
How could this scheme be extended to sequences of d-tuples (k
1
,k
2
,...,k
d
),
where each k
i
is an integer in the range [0,N−1]?
R-9.3 Is the bucket-sort algorithm in-place? Why or why not?
R-9.4 Give a pseudocode description of an in-place quick-select algorithm.
R-9.5 Show that the worst-case running time of quick-select on an n-element sequence
is Ω(n
2
).
R-9.6 Explainwheretheinductionproofforshowingthatdeterministicselectionrunsin
O(n) time would fail if we formed groups of size 3 instead of groups of size 5.
R-9.7 Whatdoestheweightedmedianalgorithmreturniftheweightsofalltheelements
are equal?
Creativity
C-9.1 Show that any comparison-based sorting algorithm can be made to be stable,
without affecting the asymptotic running time of this algorithm.
Hint: Change the way elements are compared with each other.
C-9.2 Suppose we are given two sequences A and B of n integers, possibly contain-
ing duplicates, in the range from 1 to 2n.Describealinear-timealgorithmfor
determining if A and B contain the same set of elements (possibly in different
orders).
C-9.3 Suppose we are given a sequence S of n elements, each of which is an integer in
the range [0,n
2
−1]. Describe a simple method for sorting S in O(n) time.
Hint: Think of alternate ways of viewing the elements.
C-9.4 Let S
1
,S
2
,...,S
k
be k different sequences whose elements have integer keys in
the range [0,N−1],forsomeparameterN ≥ 2.Describeanalgorithmrunning
in O(n+N) time for sorting all the sequences (not as a union), where n denotes
the total size of all the sequences.
C-9.5 Suppose we are given a sequence, S,ofn integers in the range from 1 to n
3
.
Give an O(n)-time method for determining whether there are two equal numbers
in S.
C-9.6 Let A and B be two sequences of n integers each, in the range [1,n
4
].Givenan
integer x,describeanO(n)-time algorithm for determining if there is an integer
a in A and an integer b in B such that x = a + b.
4. (10pt) Problems C-10.8-9 from textbook.
1
10.4. Exercises 299
C-10.3 Given a character string X of length n,describeanO(n)-time algorithm to con-
struct the set, C,ofdistinctcharactersthatappearinC,alongwithacount,f(c),
for each c in C,ofhowmanytimesthecharacterc appears in X.Youmayas-
sume that the characters in X are encoded using a standard character indexing
scheme, like the ASCII system.
C-10.4 AnativeAustraliannamedAnatjariwishestocrossadesertcarryingonlyasin-
gle water bottle. He has a map that marks all the watering holes along the way.
Assuming he can walk k miles on one bottle of water, design an efficient algo-
rithm for determining where Anatjari should refill his bottle in order to make as
few stops as possible. Argue why your algorithm is correct.
C-10.5 Describe an efficient greedy algorithm for making change for a specified value
using a minimum number of coins, assuming there are four denominations of
coins (called quarters, dimes, nickels, and pennies), with values 25, 10, 5,and1,
respectively. Argue why your algorithm is correct.
C-10.6 Give an example set of denominations of coins so that a greedy change making
algorithm will not use the minimum number of coins.
C-10.7 Suppose T is a Huffman tree for a set of characters having frequencies equal
to the first n nonzero Fibonacci numbers, {1,1,2,3,5,8,13,21,34,...},where
f
0
=1, f
1
=1,andf
i
= f
i−1
+ f
i−2
.ProvethateveryinternalnodeinT has
an external-node child.
C-10.8 Suppose you’ve been sent back in time and have arrived at the scene of an ancient
Roman battle. Moreover, suppose you have just learned that it is your job to
assign n spears to n Roman soldiers, so that each man has a spear. You observe
that the men and spears are of various heights, and you have been told (in Latin)
that the army is at its best if you can minimize the total difference in heights
between each man and his spear. That is, if the ith man has height m
i
and his
spear has height s
i
,thenyouwanttominimizethesum,
n
summationdisplay
i=1
|m
i
−s
i
|.
Consider a greedy strategy of repeatedly matching the man and spear that min-
imizes the difference in heights between these two. Prove or disprove that this
greedy strategy results in the optimal assignment of spears to men.
C-10.9 Consideragainthetime-travelproblemofthepreviousexercise, butnowconsider
agreedyalgorithmthatsortsthemenbyincreasingheightsandsortsthespears
by increasing heights, and then assigns the ith spear in the ordered list of spears
to the ith man in the ordered list of Roman soldiers. Prove or disprove that this
greedy strategy results in the optimal assignment of spears to men.
C-10.10 Suppose you are organizing a party for a large group of your friends. Your friends
are pretty opinionated, though, and you don’t want to invite two friends if they
don’t like each other. So you have asked each of your friends to give you an
“enemies” list, which identifies all the other people among your friends that they
dislike and for whom they know the feeling is mutual. Your goal is to invite
the largest set of friends possible such that no pair of invited friends dislike each
Hint: C-10.8: Try. C-10.9: Solve rst the case of two soldiers and then see how you can use it as
an exchange argument for the general case of n soldiers, as we did in the proof of correctness of the
greedy solution for the fractional knapsack problem (Theorem 10.1 in textbook).
5. (10pt) Use Master Theorem to determine the asymptotic behaviour of the complexity function of
the StoogeSort algorithm below:
320 Chapter 11. Divide-and-Conquer
C-11.3 There is a sorting algorithm, “Stooge-sort,” which is named after the comedy
team, “The Three Stooges.” if the input size, n,is1or2,thenthealgorithmsorts
the input immediately. Otherwise, it recursively sorts the first 2n/3 elements,
then the last 2n/3 elements, and then the first 2n/3 elements again. The details
are shown in Algorithm 11.5. Show that Stooge-sort is correct and characterize
the running time, T(n),forStooge-sort,usingarecurrenceequation,andusethe
master theorem to determine an asymptotic bound for T(n).
Algorithm StoogeSort(A,i,j):
Input: An array, A, and two indices, i and j, such that 1 ≤ i ≤ j ≤ n
Output: Subarray, A[i..j], sorted in nondecreasing order
n ← j −i +1 // The size of the subarray we are sorting
if n =2then
if A[i] >A[j] then
Swap A[i] and A[j]
else if n>2 then
m ←⌊n/3⌋
StoogeSort(A, i, j −m) // Sort the first part
StoogeSort(A, i + m, j) // Sort the last part
StoogeSort(A, i, j −m) // Sort the first part again
return A
Algorithm 11.5: Stooge-sort.
C-11.4 Consider the Stooge-sort algorithm, shown in Algorithm 11.5, and suppose we
change the assignment statement for m (on line 6) to the following:
m ← max{1,⌊n/4⌋}
Characterize the running time, T(n),inthiscase,usingarecurrenceequation,
and use the master theorem to determine an asymptotic bound for T(n).
C-11.5 Consider a version of the divide-and-conquer recurrence equation based on use
of the ceiling function, as follows:
T(n)=aT(⌈n/b⌉)+f(n),
where a ≥ 1 and b>1 are constants, and f(n) is Θ(n
log
b
a
log
k
n),forsome
integer constant, k ≥ 0.Showthat,byusingtheinequality,
T(n) ≤ aT(n/b +1)+f(n),
for sufficiently large n, T(n) is O(n
log
b
a
log
k+1
n).
Applications
A-11.1 Averycommonproblemincomputergraphicsistoapproximateacomplexshape
with a bounding box.Foraset,S,ofn points in 2-dimensional space, the idea
is to find the smallest rectangle, R,withsidesparalleltothecoordinateaxesthat
6. (10pt) Problem A-1.7 from textbook.
1.5. Exercises 49
very deadly; just one drop diluted even a billion to one will still kill someone.
Even so, the poison works slowly; it takes a full month for the person to die.
Design a scheme that allows the evil king to determine exactly which one of
his wine bottles was poisoned in just one month’s time while expending at most
O(logn) of his taste testers.
Note: All the remaining problems are inspired by questions reported to have been
asked in job interviews for major software and Internet companies.
A-1.5 Suppose you are given a set of small boxes, numbered 1 to n,identicalinevery
respect except that each of the first i contain a pearl whereas the remaining n−i
are empty. You also have two magic wands that can each test whether a box
is empty or not in a single touch, except that a wand disappears if you test it
on an empty box. Show that, without knowing the value of i, you can use the
two wands to determine all the boxes containing pearls using at most o(n) wand
touches. Express, as a function of n, the asymptotic number of wand touches
needed.
A-1.6 Repeat the previous problem assuming that you now have k magic wands, with
k>2and k
You need to import sys and open the rst le with something like f1 = open(sys.argv[1],
"r"). The program will print on the screen the edit distance between the given strings and a
corresponding alignment. For example, if one le contains \once upon a time" and the other
contains \one pony is mine," then the output should look like this:
optimal alignment:
once upon- -a time
|| || ||| | | | |
on-e -pony is mine
edit distance = 7
For longer input strings, the alignment itself has to be broken in lines of 60 characters; here is an
example:
3
optimal alignment:
ACATACGATACAGACGATCGGCTAGAATCCACCAGCTACAGCTAG-T-C---GATACA-G
||||||||||| | || |||||||||||||||||||||||||| | | ||| | |
ACATACGATAC--A-GA--GGCTAGAATCCACCAGCTACAGCTAGTTACAAGGATCGATG
CACGAATCGCTAAACAG-CTCGATCGATCGCTAGCTGATCGATACTTACCACAGCTGATC
|||||| |||||||| || | | ||||||||||||||||||||||||||||| |
CACGAA---CTAAACAGACTAG-TTTCTCGCTAGCTGATCGATACTTACCACAGCTAAAA
GATGCTATT-TAGCTAGCT-CGTAGTA
||||||||| | | |||| | ||
GATGCTATTATTG-GAGCTAATTTTTA
edit distance = 34
To simplify the production of the output alignment, if the input les have multiple lines, then the
newline characters will be replaced by spaces: stringName.replace("nn", " ").
The strings for the two tests above are given in the les test1.txt, test2.txt, dna1.txt, dna2.txt.
Here is also an immediate application of your program to linguistics. The le americanPieEnglish.txt
contains one fragment of Don McLean’s American Pie, perhaps one of the best songs ever (can’t
use dynamic programming to measure that). The other three les contain Italian, Spanish and
Portuguese translations. You need to compute all edit distances to ll in the table below. The edit
distance is symmetric, so you have to ll in only half of the table.
Edit distance English Italian Spanish Portuguese
English 0
Italian 0
Spanish 0
Portuguese 0
The expectation is that English, as a Germanic language, is more di erent from the three Latin
languages than they are from each other. Also, among the three Latin ones, Spanish and Portuguese
are closest to each other. Of course, the sample is quite small but the di erences are still visible.
If you reach a di erent conclusion, then you have to perform. American Pie live during the rst
CS3340 class after the assignment’s deadline!
Note: { Submit your solutions, as one pdf le, and programs as py les to owl.uwo.ca. If any output is
required from the programs, include it in the pdf le.
{ The assignments must be typed, preferably in LATEX.1 Do not submit the LATEX le.
{ The programs must be written in Python.
{ The algorithms are given in pseudocode unless speci ed otherwise.2
{ Understanding the assignment is part of solving it. Read everything carefully and try your
best to understand it before asking questions.
{ The solution can use anything as long as it arguably solves the problem as given.
1It is free and by far the best for scienti c writing. Here is a quick start: https://tobi.oetiker.ch/lshort/lshort.pdf
2There are many LATEXpackages for writing pseudocode; for the assignments I am using the algorithmicx package:{ When explaining solutions, provide the essential information. Do not omit necessary details
but also do not waste time writing obvious facts. As a guideline, explain only what is not obvious
to you. Explaining things clearly but succinctly is a very important skill.
{ There is no penalty for submitting multiple times (no limit). Only the last submission is graded.