# 算法代写｜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).)