Database Reference
In-Depth Information
!! EXERCISE 3.5.3 Prove that if i and j are any positive integers, and i < j , then the L i norm
between any two points is greater than the L j 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 following pairs of
vectors. 5
(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 in-
stance, we can allow, in addition to insertions and deletions, the following operations:
(i) Mutation , where one symbol is replaced by another symbol. Note that a mutation can
always be performed by an insertion followed by a deletion, but if we allow mutations,
then this change counts for only 1, not 2, when computing the edit distance.
(ii) Transposition , where two adjacent symbols have their positions swapped. Like a
mutation, we can simulate a transposition by one insertion followed by one deletion,
but here we count only 1 for these two steps.
Repeat Exercise 3.5.7 if edit distance is defined to be the number of insertions, deletions,
mutations, and transpositions needed to transform one string into another.
Search WWH ::




Custom Search