Algorithms 3027 Assignment 2 The University of Sydney 2019 Semester 1 School of Computer Science
This assignment is for COMP3027 students only.
Description
Suppose we are running a bed manufacturing company. There are several different types of bed of various dimensions (length and width) that we can produce. To decide which beds we should produce, we run a market survey asking people what dimensions they require in a bed (i.e. the minimum length and the minimum width they need). We say that a person is compatible with a bed type if its length is at least that person’s length requirement, and its width is at least that person’s width requirement. The compatibility of a bed type is the number of persons compatible with it. Our goal is to determine efficiently the compatibility of every bed type.
We now state the problem more formally. Suppose we have n bed types, and surveyed n persons. Let B = {b1, . . . , bn} be a set of n points in 2-dimensional space representing the dimensions of the bed types. We write bi = (bi(x),bi(y)) with bi(x) representing the length of bed type i and bi(y) its width. Similarly, we represent the requirements of the n persons with P = {p1,…,pn}, a set of n points in 2-dimensional space, and we also write pj = (pj(x),pj(y)) where pj(x) and pj(y) are person j’s length and width requirements, respectively.
Point bi is compatible with point pj if and only if bi(x) ≥ pj(x) and bi(y) ≥ pj(y). The compatibility of bi is the number of points of P that it is compatible with and we write comp(bi) = k if it is compatible with k points of p. See Figure 1 for an illustration.
4 1
1 0
Figure 1: The solid circles represent points in B and the hollow circles represent points in P . The numbers represent the compatibility of each points in B.
Your task is to design an algorithm that computes the compatibility of every point in B. Task 1: 1-dimensional case [20 marks]
We will start with the simpler 1-dimensional case, that is, P = {p1,…,pn} and B = {b1,…,bn} are points in 1-dimensional space (multiple points may have the same value). Your task is to design an O(n log n) time algorithm that computes the compatibility of each point in B with P .
(a) Description of how your algorithm works (“in plain English”). (b) Argue why your algorithm is correct.
(c) Prove an upper bound on the time complexity of your algorithm.
(d) Implement your algorithm (in Ed) (see the appendices for the data formats).
[5 marks] [4 marks] [3 marks] [8 marks]
1
Task 2: 2-dimensional case [80 marks]
Consider the same problem in 2D, that is, let P = {p1,…,pn} and B = {b1,…,bn} be a set of points in 2-dimensional space, where each point pi is a 2-tuple pj = (pj(x),pj(y)) and bi = (bi(x),bi(y)). The task is to solve this problem using a divide-and-conquer approach. A divide and conquer algorithm works by recursively breaking down a problem into two (or more) sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then merged to give a solution to the original problem. For full marks on this question the algorithm is required to run in O(n log n) time.
We will start with the merge step.
(a) Merge step [40 marks] Consider a vertical line L. Suppose the line splits P into two sets P1 = {p1,…,pl} and P2 = {q1,…,qn−l}, where P1 lies to the left of L and P2 lies to its right. Similarly, it also splits B into two sets B1 = {b1,…,bm} and B2 = {c1,…,cn−m}. We will also assume that the sets in P1 and P2, B1 and B2 are ordered from bottom to top (in case of a tie the points are ordered with respect to increasing x-coordinates). Assume that the problem has been solved for (P1,B1) and (P2,B2), respectively. That is, the compatibility of each points in B1 has been computed with respect to P1 and the compatibility of each point in B2 has been computed with respect to P2. Your task is to combine the two solutions into one solution for P = P1 ∪ P2 andB=B1∪B2 inO(n)time.AnexampleisshowninFig.2.
(i) Description of how your algorithm works (“in plain English”). (ii) Argue why your algorithm is correct.
(iii) Prove an upper bound on the time complexity of your algorithm.
(iv) Implement your algorithm (in Ed) (see the appendices for the data formats).
24 11
11 00
[13 marks] [12 marks] [5 marks] [10 marks]
Figure 2: The point sets P1, B1 are separated from P2, B2 by a vertical line. The merge step merges the input data into the compatibility of all the points in B = B1 ∪ B2 with respect to points P = P1 ∪ P2.
(b) [40 marks] The final task is to use the merge step algorithm from (a) to construct a divide-and- conquer algorithm for the problem.
(i) Description of how your algorithm works (“in plain English”). (ii) Argue why your algorithm is correct.
(iii) Prove an upper bound on the time complexity of your (entire) algorithm. (iv) Implement your algorithm (in Ed) (see the appendices for the data formats).
Submission details
[8 marks] [10 marks] [10 marks] [12 marks]
• Submission deadline is Wednesday 3rd April, at 23:59. Late submissions without special consideration will be subject to the penalties specified in the first lecture (5% per day; 0 marks after 10 days late).
• Submit your answers to Tasks 1a-c, 2a(i-iii), and 2b(i-iii) as a single document to Canvas. Your work must be typed (no images of text, although you can use diagrams if you think it helps.) Please try to be reasonably concise.
2
• The implementation required for Tasks 1d, 2a(iv) and 2b(iv) should be done in Ed, and submitted via Ed. Please be aware that there may be hidden tests, and additional tests may be added after the submission deadline.
• Your report will be subject to automatic and manual plagiarism detection systems. Remember, it’s acceptable to discuss high level ideas with your peers, but you should not share the detail of your work, such as parts as the precise algorithms, examples, proofs, writing, or code.
• To facilitate anonymous grading, please do not write your name on your submission. Appendices
Task 1: I/O format
Input is given as a filename. This file contains text, similar to the following example:
5
p1 5.3 p2 3.2 p3 1.0 p4 11.3 p5 12.4 b1 2.6 b2 11.4 b3 10.2 b4 1.3 b5 2.1
In this example, n = 5 (first line of the file), p1(x) = 5.3, … b4(x) = 1.3, … etc.
The output should be printed to screen. The expected output for this instance would be:
b1 1 b2 4 b3 3 b4 1 b5 1
The number following the bed name is the number of people that are compatible with that bed.
Task 2.a: I/O format
Input is given as a filename. This file contains text, similar to the following example:
5 2 3 p1 p2 b1 b2 b3 q1 q2 q3 c1 c2
1.0 2.0
3.2 3.1
2.6 2.0 1 2.1 12.5 1 1.3 24.3 1 5.3 1.0
12.4 1.0 11.3 11.0 16.4 2.0 2 15.2 23.5 3
In this example:
• n=5,l=2,m=3
• p1(x) = 1.0, p1(y) = 2.0, … etc.
3
• b1(x) = 2.6, b1(y) = 2.0, compatibility of bed b1 with the people {p1, …pl} is 1… etc.
• c2(x) = 15.2, c2(y) = 23.5, compatibility of bed c2 with the people {q1, …qn−l} is 3… etc. The output should be printed to screen. The expected output in this case would be:
b1 1 b2 1 b3 1 c1 3 c2 5
i.e. the bed name, followed by the number of people it is compatible with (from both sets of people).
Task 2.b: I/O format
Input is given as a filename. This file contains text, similar to the following example:
5 p1 p2 p3 p4 p5 b1 b2 b3 b4 b5
b1 b2 b3 b4 b5
12.4 1.0 1.0 2.0 11.3 11.0 5.3 1.0 3.2 3.1 15.2 23.5 2.1 12.5 1.3 24.3 2.6 2.0 16.4 2.0
i.e. n, followed by n two dimensional points for each of P and B.
The output should be printed to screen. The output format is the same as before. e.g.
5 1 1 1 3
4