Problem
1. Prove that edit distance on text strings defines a metric.
2. Show that the expected distance between two points chosen uniformly and independently from a line of length 1 is 1/3. Establish convincing upper and lower bounds on this expected distance for partial credit.
3. What is the maximum number of nearest neighbors that a given point p can have in two dimensions, assuming the possibility of ties?