Guidelines:  (read fully!!)

● Your assignment solution must be submitted as a typed PDF document. Scanned handwritten solutions, solutions in any other format,  or unreadable solutions will  not be accepted or marked.   You  are encouraged to learn the LATEX typesetting system and use it to type your solution.  See the course website for LATEX resources.

● To submit this assignment, use the MarkUs system, at URL https://markus.teach.cs.toronto. edu/2023-01/

● This is a group assignment. This means that you can work on this assignment with at most one other student. You are strongly encouraged to work with a partner. Both partners in the group should work on and arrive at the solution together. Both partners receive the same mark on this assignment.

● Work on all problems together. For each problem, one of you should write the solution, and one should proof-read and revise it. The first page of your submission must list the name, student ID, and UTOR email address  of both group members.  Your solution should also list, for each problem, which group member wrote the problem, and which group member proof-read and revised it.

● You may not consult any other resources except: your partner; your class notes; your textbook and assigned readings.  Consulting any other resource, or collaborating with students other than your group partner, is a violation of the academic integrity policy!

● You may use any data structure, algorithm, or theorem previously studied in class, or in one of the prerequisites of this course, by just referring to it, and without describing it.  This includes any data structure, algorithm, or theorem we covered in lecture, in a tutorial, or in any of the assigned readings. Be sure to give a precise reference for the data structure/algorithm/result you are using.

● Unless stated otherwise, you should justify all your answers using rigorous arguments.  Your solution will be marked based both on its completeness and correctness, and also on the clarity and precision of your explanation.

Question 1.  (7 marks)

Recall that the Euclidean distance between two points x, y e Rd  is defined by the formula:

dist(x, y) =^(x1 · y1 )2 + . . . + (xd · yd )2 .

When d = 2 or d = 3, this is just the standard notion of distance in the plane or in 3-dimensional space, respectively.

Your goal in this question is to give a locality sensitive hash function for Euclidean distance. In this question you can use the following proposition.

Proposition 1.  Suppose that σ 1 , . . . σd  are  chosen uniformly and independently at random from {· 1, +1} . For any z1 , . . . , zd  e R, we have

E ┌ │i1 σi zi │┐ < E ┌ │i1 σi zi │2 ┐ 1/2  <A2 E ┌ │i1 σi zi │┐ .

Define a random  hash function h : {0, . . . , N }d  → {0, 1}, so that, for any x, y e {0, . . . , N }d , any 0 < r < NAd, and any C > 1,

r 

dist(x, y) < r  =÷  P(h(x) = h(y)) > 1 ·

A2K ,

(1)

(2)

where K is some constant which is allowed to depend on d and N , but not on x, y , r, or C .  (Just as in class, x and y are not random, and the probability is only over the random choice of h.) The function h should be computable in time O(d) when x is given as an array of size d.  Give a precise value for K and justify your answer.

Question 2.  (11 marks)

Once again we consider the Euclidean distance in Rd :

dist(x, y) =^(x1 · y1 )2 + . . . + (xd · yd )2 .

In this problem, you are given a set P of n points in Rd , and your goal is to find an approximately closest pair of distinct points in P . Let us define

∆(P) = min{dist(x, y) : x e P, y e P, x  y}.

The goal will be to output two distinct points in P that are not much further apart than ∆(P).

For both subquestions below, assume that you are given a near neighbour search data structure that, given a parameter r > 0, maintains a set Q of at most n points in Rd  and supports two operations: ⅠN生|kT(Q, x) which inserts a new point x into Q, and N|\kN|Ⅰ注γ↓ok(Q, q) which must satisfy the following two condi- tions:

1. If there exists a point x in Q such that dist(x, q) < r, then, with probability at least 2/3, N|\kN|Ⅰ注γ↓ok(Q, q) will output some y e P for which dist(x, y) < 2r;

2. If every point x in Q satisfies dist(x, q) > 2r, then N|\kN|Ⅰ注γ↓ok(Q, q) outputs ∶\ⅠL with probability 1.