Programming Assignment 2

COSC 3320

Algorithms and Data Structures

Read the University of Houston Academic Honesty policy.

Academic Honesty Policy

All submitted work should be your own. Copying or using other people’s work (including from the

Web) will result in −MAX points, where MAX is the maximum possible number of points for that

assignment. Repeat offenses will result in a failing grade for the course and will be reported to the

Chair. If you have any questions, please reach out to the professor and the TAs. The best way to

ask is on Piazza.

By submitting this assignment, you affirm that you have followed the Academic Honesty Policy.

The writeup portion of your submission must be typed. We prefer you use LATEX to type your

solutions — LATEX is the standard way to type works in mathematical sciences, like computer science, and

is highly recommended; for more information on using LATEX, please see this post on Piazza — but any

method of typing your solutions (e.g., MS Word, Google Docs, Markdown) is acceptable. Your writeup

must be in pdf format. The assignment can be submitted up to two days late for a penalty of

10% per day. A submission more than two days late will receive a zero.

Before you begin the assignment, create an account on LeetCode if you do not already have one.

Problem 1 I k-closest points to the origin

We have a list of points on the plane. Find the k closest points to the origin, (0, 0).

(Here, the distance between two points on a plane is the Euclidean distance.)

You may return the answer in any order. The answer is guaranteed to be unique (except for the

order that it is in.)

Example 1

Input: points = [[1, 3], [−2, 2]], k = 1

Output: [[−2, 2]]

Explanation: The distance between (1, 3) and the origin is √

10.

The distance between (−2, 2) and the origin is √

8.

Since √

8 <

√

10, (−2, 2) is closer to the origin.

We only want the closest k = 1 points from the origin, so the answer is just [[−2, 2]].

Example 2

Input: points = [[3, 3], [5, −1], [−2, 4]], k = 2

Output: [[3, 3], [−2, 4]]

(The answer [[−2, 4], [3, 3]] would also be accepted.)

It is important that you solve this problem using divide and conquer. That is, you have to reduce the

original problem into one or more subproblems, recursively solve the subproblems, and then combine

the solutions to obtain the solution to the original problem. Your solution should take O(n) time in the

worst case. Note that you cannot use sorting, as this will take O(n log n) time.

Note that the LeetCode webpage may accept a solution that is not O(n) in the worst case. By contrast,

we require the solution to be O(n) in the worst case. Additionally, some solutions on LeetCode

do not use divide and conquer. These are not acceptable solutions. Some solutions posted may also be

wrong. In any case, a solution that is largely copied from another source (e.g., verbatim or made to look

different by simply changing variable names) will be in violation of the Academic Honesty Policy.

The following must be submitted.

(a) Writeup (50 Points)

• Pseudocode for your solution, with an explanation in words why your solution works. (25

points)

• Analysis, showing the correctness of your algorithm and its complexity (i.e., its runtime). (25

points).

(b) Source Code (50 Points)

• Write your solution in Python, C, C++, Java, or JavaScript.

• Your code should be well written and well commented.

• A comment with a link to your LeetCode profile (e.g., https://leetcode.com/jane-doe/)

and a statement of whether or not your code was accepted by LeetCode. We will verify whether

your code is accepted.

• We must be able to directly copy and paste your code into LeetCode at the LeetCode problem

page. If your code does not compile on LeetCode, it will will receive zero points. Under

no circumstances will we attempt to modify any submission, so be sure the code you submit

works.

Please submit these files individually. Do not submit as an archived file (zip file, tarball, etc.).

1 Pseudocode and Explanation

Algorithm 1 ClosestPoints – k closest points to the origin

1: def ClosestPoints(S, k):

Input . An array S of points in the plane and a positive integer k.

Output . The k points in S closest to the origin.

2: n ← |S|

3: if n = some number: . Base Case

4: Base Case Stuff

5: else: . Recursive Step

6: Recursive Step Stuff

2 Analysis