CSE 421 Assignment #3
Spring 2016

Due: Friday, April 22, 2016.

Reading Assignment: Kleinberg and Tardos Chapter 5, Section 13.5.

Problems: (see the Grading Guidelines before answering)

  1. Kleinberg and Tardos, Chapter 4, Problem 17, page 197.

  2. Kleinberg and Tardos, Chapter 4, Problem 19, pages 198-199.

  3. Kleinberg and Tardos, Chapter 5, Problem 5, page 248.

  4. (Extra Credit) Use the same ideas as used to solve the problem for closest pair in the plane to create an O(n log2 n) algorithm for finding closest pairs in 3 dimensions and prove its running time. (This is not optimal; an O(n log n) algorithm exists that uses ideas of the above algorithm plus more flexibility in choosing how to split the points into subproblems so that the difficult strip in the middle has fewer points.)