算法代写｜CSE 417 Algorithms & Computational Complexity Assignment #5

这是一个美国的算法和计算复杂性的算法代写assignment

This assignment is part written, part programming. It all focuses on the “closest pair of points” problem from
section 5.4 and lecture.

1. The 1-dimensional closest pair of points problem is easily solved by sorting the list of points by coordinate; after
sorting, the closest pair will be adjacent in this sorted list. Near the bottom of pg 226, the book outlines why
this algorithm does not generalize to the 2-dimensional case. Make this more concrete by providing a family
of examples (parameterized by n) having n distinct points where the closest pair of points (all closest pairs, if
there are ties) are widely separated from each other in the list of all points when sorted either by x-coordinate
or by y-coordinate.

2. In the discussion of the closest points algorithm, for simplicity, my slides assume that (*) “no two points have the
same x coordinate.” One implicit use of this simplifying assumption occurs on slide 23, which contains a claim
and its proof. The claim stated there is true in general, but the given proof relies on the additional assumption
(*). Specifically: (a) The statement “No two points lie in the same δ=2 by δ=2 square” is true (as shown on slide
23) if all points have distinct x-coordinates, but may be false in the general case where the assumption (*) is
violated. Give a counterexample illustrating why it is false in general. (Your example doesn’t need more than
4–8 points. The edges of the squares sketched on slide 23 are especially important.) (b) However, the claim
stated on that slide remains true even if multiple points have the same x-coordinate. Prove this.

3. Implement two algorithms for the “2-D closest pair of points” problem (and compare their running times; see
next problem).

(a) Version 1 is the naive Θ(n2) algorithm that calculates all pairwise distances.

(b) Version 2 is the Θ(n log2 n) algorithm described in lecture (approximately slide 24) that includes a “sort
by y” step in the recursion.

Inputs: For testing/debugging, your program should read a sequence of x-y pairs from standard input, and run
each algorithm on these points, printing to standard output (aka the console) the coordinates of, and distance
between the closest pair of points, among other things. (Output detail specified below. If several pairs tie for
closest, it doesn’t matter which you select.)

The desired input file format is simply a white-space separated list containing an even number of decimal
numbers. E.g.

-1.0 0.0 2.99 0.0 0.0
1.0

specifies three points: the first on the x-axis one unit left of the origin, the second at x = 2:99; y = 0, and
the third at x = 0; y = 1. As shown, (and unlike the simplified form discussed in lecture) distinct points
may share x and/or y coordinates. “White-space” means any combination of spaces, tabs and/or newlines.

Most programming languages have input routines that will make it easy to read data in this format. “Standard
input” usually comes from whatever you type on the keyboard; end-of-file is usually control-D (unix or Mac) or
control-Z-return (Windows). Alternatively, from the command line, you can redirect standard in to read from a
file, e.g.:

python hw5.py < points-test1.txt
# or
javac hw5.java && java hw5 < points-test1.txt

I will later provide some specific test cases that will be part of our autograder tests.
Outputs: Print a single line of output for each version of the algorithm, containing

(a) The algorithm version, e.g. “Version 2,”

(b) The number of points in the input, “n,”

(c) The coordinates of the closest pair of points “x1, y1, x2, y2,” in lexicographic order (i.e., x1 ≤ x2, and if
x1==x2, then in addition y1 ≤ y2).

(d) The distance “delta” between them, to 3 decimal places, and

(e) The time taken, in milliseconds.

Format these as comma separated values, with your version 1 line before version 2. E.g.,:

Version 1, 3, -1.0, 0.0, 0.0, 1.0, 1.414, 0.010
Version 2, 3, -1.0, 0.0, 0.0, 1.0, 1.414, 0.011

We will run your code on the given test cases, and others, using Gradescope’s autograder setup, running com
mands like the examples shown above.

Again, you may use Java or Python. You may use built-in or publicly available libraries for sorting, random
numbers, or other utility functions.

For this question, just turn in your code. (Don’t turn in the test case files; we have them. Don’t turn in output
files; there shouldn’t be any—all output goes to standard out (console).)