Assignment 4
WARNING: To receive credit for this assign- ment, you must submit the academic integrity declaration. Do so before starting work on the questions.
Coverage: All guides; all modules.
This assignment consists of a written component and a programming component. Please read the course website carefully to ensure that you submit each component correctly.
All the questions in the written component should be submitted as a single pdf file with the name a4written.pdf. Although scanned documents are acceptable, please keep in mind that only legible writing will be marked (subject to the markers’ discretion) and that MarkUs forces a limit of 5000 KB per file, which might be exceeded by high resolution scans.
Note: In assignment questions that specify the use of a particular paradigm, you are expected to come up with a new algorithm using that paradigm. It is not sufficient to implement a class example as a helper function and declare that the paradigm has been used.
Written component
For full marks, you are expected to provide a brief justification of any answer you provide.
W1. [4 marks] We can attempt to solve the Noise Elimination problem (defined in Assign- ment 2) by choosing the character in each position at random, where for each position, 0 and 1 are equally likely to be chosen. Using the instance {111, 011, 101, 110, 000} from the solutions in part (b) of W2 in Assignment 2, determine the expected maximum distance. Briefly discuss how this compares to the worst-case for Algorithm A and the optimal solution for the example.
W2. [7 marks] In this problem we will consider the greedy algorithms for Noise Elimination discussed in Assignment 2. The goal is to use the algorithms as approximation algorithms for the related problem of Noise Minimization. Here the goal is to find a string that is the minimum total distance from all input strings.
Noise Minimization
Input: A set of strings S all of the same length l where characters are in the alphabet Σ Output: A string of α of length l such that the sum of the distances between α and the
strings in S (that is, β∈S {dist(α, β}) is as small as possible
For example, for the instance {111, 011, 000}, the string 011 has total distance dist(011, 111)+ dist(011,011)+dist(011,000) = 1+0+2 = 3. It would also be an output for Noise Elim- ination, since the maximum distance is 2, and due to 111 and 000 both being in the set, a
CS 231 Spring 2020 Naomi Nishimura
smaller maximum distance is not possible. However, not every output for Noise Elimina- tion is an output for Noise Minimization. The string 010 also has maximum distance 2, but its total distance is dist(010, 111) + dist(010, 011) + dist(010, 000) = 2 + 1 + 1 = 4. You might also wish to consider whether there exists an instance such that an output for Noise Minimization for that instance is not an output for Noise Elimination for the same instance.
(a) [2 marks] Is it possible to use Algorithm A from Assignment 2 to obtain a constant ratio bound for Noise Minimization as a function of n, s, and l? Explain why or why not.
(b) [5 marks] Describe an input using n strings (where n is not specified) on which the ratio bound for Algorithm B on Noise Minimization is not guaranteed to be a constant as a function of n, s and l. You can do so by describing how Algorithm B performs on the input and contrasting it with the optimal solution.
W3. [12 marks] In the problem Transmission Towers, we are trying to place k towers that can broadcast to a set of locations. Each location can be represented as a point (x,y) and so can each tower (you can think of the towers being very thin and tall). We are also going to allow towers to be placed on locations.
The distance between a pair of points p1 = (x1,y1) and p2 = (x2,y2) can be calculated
as dist(p1, p2) = (x2 − x1)2 + (y2 − y1)2. In this question you will not need to calculate distances; you can assume that the distance between a pair of points can be calculated in constant time. The importance of the definition of dist is that it satisfies the triangle inequality: for all points p1, p2, and p3, dist(p1, p3) ≤ dist(p1, p2) + dist(p2, p3). For this question you do not need to specify the points, just the distance between them.
In this problem, we’ll be placing towers so that no point in P is too far from a tower. We’ll measure how good our solution is by considering the value close(p) for each point p ∈ P , where close(p) is defined to be the distance between p and the closest tower.
The problem is defined as follows:
Input: A set P of points and an integer k
Output: A set of k points (not necessarily in P) at which to position towers such that the largest distance from a point in P to its closest tower (that is, maxp∈P {close(p)}) is as small as posssible
For each input point, each coordinate will be of size at most a polynomial in n, the size of P. Points do not need to have integer coordinates.
In the image, the points in P are shown in black and the points in red are the positions of k = 3 towers. Here each of the black points is at distance one from the closest red point.
We consider the following algorithms for solving the problem:
Algorithm A: Place the first tower on a point q such that the maximum distance from q to any point in P (that is, maxp∈P{dist(q,p)}) is as small as possible, breaking ties arbitrarily. For the second and subsequent towers, place the tower at a point that decreases the largest distance from a point in P to its closest tower (that is, maxp∈P {close(p)}) as much as possible, breaking ties arbitrarily.
Algorithm B: Place the first tower at an arbitrary point in P. For the second and subsequent towers, place the tower at a point in P that is farthest from all of the towers placed so far, breaking ties arbitrarily.
(a) [4 marks] Describe an input on n points (where n is not specified) for which the ratio bound for Algorithm A is not guaranteed to be a constant. You can do so by describing how Algorithm A performs on the input and contrasting it with the optimal solution. The value of k should be a constant unrelated to n.
(b) [8 marks] Using the steps in the recipe for analyzing an approximation algorithm, show that Algorithm B has a ratio bound of 2. Hint: Use the triangle inequality to reason about the distances between towers in the greedy and the optimal solutions. You may wish to use the new measure or problem for Step 1 as the maximum distance D between any point and the closest tower as placed by Algorithm B, that is, D = maxp∈P {close(p)}.
W4. [7 marks] Suppose you wish to solve Noise Elimination (defined in Assignment 2) using branch-and-bound. Specify your algorithm by using the recipe for branch-and-bound.
Programming component
Please read the course website carefully to ensure that you are using the correct version of Python and the correct style. For full marks, you are required not only to have a correct solution, but also to adhere to the requirements of the assignment question and the style guide, including aspects of the design recipe.
Although submitting tests is not required, it is highly recommended that you test your code. For each assignment question, create a testing file that imports your submission and tests the code. Do not submit your testing file.
For any of the programming questions in this assignment, you may import any of the follow- ing files: check.py, graphs.py, equiv.py, and sess2q3pair as well as built-in modules such as math, itertools, copy, and random.
P1. [5 marks] Write a function rand start that consumes a nonempty list of strings of equal nonzero length and produces a string of the same length that can serve as a starting point for hill-climbing for Noise Elimination (defined in Assignment 2). Your function should construct the string position by position, choosing the character in the first position from the characters in the first positions of the input strings, the character in the second position from the characters in the second positions of the input strings, and so on.
Submit your work in a file with the name randstart.py.
P2. [10 marks] Write a function noise elimination that consumes a nonempty list of strings of equal nonzero length and produces a single string of that length that is intended to solve Noise Elimination (defined in Assignment 2). You will use the heuristic of hill-climbing, starting with a string produced by rand start.
At each step, you will find a symbol to change to another symbol. If possible, the change will decrease the maximum distance of the solution to any of the input strings. If not, then the change should decrease the number of strings at maximum distance from the solution (without increasing the maximum distance of the solution to any of the input strings), and if that is not possible, stop the search and return the current solution.
You can use your solution to Question P1 to test your work. When you submit your assignment, use instead the line from randstartmodel import * to import our model solution. In that way, you will not lose additional marks in this question should your solution to Question P1 have problems.
Your function should work no matter what string is provided by randstartmodel, even if the characters are not in the original strings. (We might use a “fake” file for testing.)
You might find it convenient to use Pairs; if so, use the line from sess2qpair import * instead of copying the code into your file.
Submit your work in a file with the name noiseelimination.py.
P3. [10 marks] Write a function vertex cover that consumes a graph and a bound k and produces a list of vertices of length at most k that forms a vertex cover of the graph, if any exists, or False otherwise. Your function should solve the problem using the fixed- parameter algorithm discussed in class.
Submit your work in a file with the name vertexcover.py.
WARNING: To receive credit for this assign- ment, you must submit the academic integrity declaration. Do so before starting work on the questions.