102
CHAPTER 3. FINDING SIMILAR ITEMS
(b) diﬀ(x, y) = |x −y| (the absolute magnitude of the diﬀerence between x
and y).
(c) sum(x, y) = x + y.
Exercise 3.5.2: Find the L1 and L2 distances between the points (5, 6, 7) and
(8, 2, 4).
!! Exercise 3.5.3: Prove that if i and j are any positive integers, and i < j,
then the Li norm between any two points is greater than the Lj norm between
those same two points.
Exercise 3.5.4: Find the Jaccard distances between the following pairs of
sets:
(a) {1, 2, 3, 4} and {2, 3, 4, 5}.
(b) {1, 2, 3} and {4, 5, 6}.
Exercise 3.5.5: Compute the cosines of the angles between each of the fol-
lowing pairs of vectors.6
(a) (3, −1, 2) and (−2, 3, 1).
(b) (1, 2, 3) and (2, 4, 6).
(c) (5, 0, −4) and (−1, −6, 2).
(d) (0, 1, 1, 0, 1, 1) and (0, 0, 1, 0, 0, 0).
! Exercise 3.5.6: Prove that the cosine distance between any two vectors of 0’s
and 1’s, of the same length, is at most 90 degrees.
Exercise 3.5.7: Find the edit distances (using only insertions and deletions)
between the following pairs of strings.
(a) abcdef and bdaefc.
(b) abccdabc and acbdcab.
(c) abcdef and baedfc.
! Exercise 3.5.8: There are a number of other notions of edit distance available.
For instance, we can allow, in addition to insertions and deletions, the following
operations:
6Note that what we are asking for is not precisely the cosine distance, but from the cosine
of an angle, you can compute the angle itself, perhaps with the aid of a table or library
function.
