CS 231 Spring 2020

Assignment 4

WARNING: To receive credit for this assignment,

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 Assignment

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 ` where characters are in the alphabet Σ

Output: A string of α of length ` such that the sum of the distances between α and the

strings in S (that is, P

β∈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 Elimination,

since the maximum distance is 2, and due to 111 and 000 both being in the set, a

smaller maximum distance is not possible. However, not every output for Noise Elimination

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 `? 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 `. 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) = q

(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 following

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 fixedparameter

algorithm discussed in class.

Submit your work in a file with the name vertexcover.py.

WARNING: To receive credit for this assignment,

you must submit the academic integrity

declaration. Do so before starting work on the

questions.

版权所有：留学生程序辅导网 2019 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。