” CS 231编程 写作、 写作Python语言编程、Python编程CS 231 Spring 2020Assignment 4WARNING: To receive credit for this assignment,you must submit the academic integritydeclaration. Do so before starting work on thequestions.Coverage: All guides; all modules.This assignment consists of a written component and a programming component. Pleaseread 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 thename a4written.pdf. Although scanned documents are acceptable, please keep in mind thatonly legible writing will be marked (subject to the markers discretion) and that MarkUs forcesa 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 expectedto come up with a new algorithm using that paradigm. It is not sufficient to implement a classexample as a helper function and declare that the paradigm has been used.Written componentFor 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 Assignment2) by choosing the character in each position at random, where for each position, 0and 1 are equally likely to be chosen. Using the instance {111, 011, 101, 110, 000} from thesolutions 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 optimalsolution for the example.W2. [7 marks] In this problem we will consider the greedy algorithms for Noise Eliminationdiscussed in Assignment 2. The goal is to use the algorithms as approximation algorithmsfor the related problem of Noise Minimization. Here the goal is to find a string that isthe minimum total distance from all input strings.Noise MinimizationInput: 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 thestrings in S (that is, PCS 231作业 写作、 写作Python语言作业、Python编程设计S{dist(, }) is as small as possibleFor 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, asmaller maximum distance is not possible. However, not every output for Noise Eliminationis an output for Noise Minimization. The string 010 also has maximum distance2, 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 forNoise Minimization for that instance is not an output for Noise Elimination for thesame instance.(a) [2 marks] Is it possible to use Algorithm A from Assignment 2 to obtain a constantratio bound for Noise Minimization as a function of n, s, and `? Explain why orwhy not.(b) [5 marks] Describe an input using n strings (where n is not specified) on which theratio bound for Algorithm B on Noise Minimization is not guaranteed to be aconstant as a function of n, s and `. You can do so by describing how Algorithm Bperforms 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 thatcan 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 alsogoing to allow towers to be placed on locations.The distance between a pair of points p1 = (x1, y1) and p2 = (x2, y2) can be calculatedas dist(p1, p2) = q(x2 x1)2 + (y2 y1)2. In this question you will not need to calculatedistances; you can assume that the distance between a pair of points can be calculatedin constant time. The importance of the definition of dist is that it satisfies the triangleinequality: for all points p1, p2, and p3, dist(p1, p3) dist(p1, p2) + dist(p2, p3). For thisquestion you do not need to specify the points, just the distance between them.In this problem, well be placing towers so that no point in P is too far from a tower.Well measure how good our solution is by considering the value close(p) for each pointp 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 kOutput: A set of k points (not necessarily in P) at which to position towers such thatthe largest distance from a point in P to its closest tower (that is, maxpP {close(p)})is as small as posssibleFor each input point, each coordinate will be of size at most a polynomial in n, the sizeof 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 ofk = 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 fromq to any point in P (that is, maxpP {dist(q, p)}) is as small as possible, breaking tiesarbitrarily. For the second And subsequent towers, place the tower at a point that decreasesthe largest distance from a point in P to its closest tower (that is, maxpP {close(p)}) asmuch as possible, Breaking ties arbitrarily.Algorithm B: Place the first tower at an arbitrary point in P. For the second andsubsequent towers, place the tower at a point in P that is farthest from all of the towersplaced so far, breaking ties arbitrarily.(a) [4 marks] Describe an input on n points (where n is not specified) for which theratio bound for Algorithm A is not guaranteed to be a constant. You can do soby describing how Algorithm A performs on the input and contrasting it with theoptimal 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 toreason 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 distanceD between any point and the closest tower as placed by Algorithm B, that is, D =maxpP {close(p)}.W4. [7 marks] Suppose you wish to solve Noise Elimination (defined in Assignment 2) usingbranch-and-bound. Specify your algorithm by using the recipe for branch-and-bound.Programming componentPlease read the course website carefully to ensure that you are using the correct versionof Python and the correct style. For full marks, you are required not only to have a correctsolution, 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 thecode. Do not submit your testing file.For any of the programming questions in this assignment, you may import any of the followingfiles: check.py, graphs.py, equiv.py, and sess2q3pair as well as built-in modules suchas math, itertools, copy, and random.P1. [5 marks] Write a Function rand start that consumes a nonempty list of strings of equalnonzero length and produces a string of the same length that can serve as a startingpoint for hill-climbing for Noise Elimination (defined in Assignment 2). Your functionshould construct the string position by position, choosing the character in the first positionfrom the characters in the first positions of the input strings, the character in the secondposition 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 stringsof equal nonzero length and produces a single string of that length that is intended to solveNoise 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 changewill 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 thesolution (without increasing the maximum distance of the solution to any of the inputstrings), 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 yourassignment, use instead the line from randstartmodel import * to import our modelsolution. In that way, you will not lose additional marks in this question should yoursolution to Question P1 have problems.Your function should work no matter what string is provided by randstartmodel, even ifthe 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 andproduces a list of vertices of length at most k that forms a vertex cover of the graph, ifany exists, or False otherwise. Your function should solve the problem using the fixedparameteralgorithm 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 integritydeclaration. Do so before starting work on thequestions.如有需要，请加QQ：99515681 或邮箱：99515681@qq.com
“
添加老师微信回复‘’官网 辅导‘’获取专业老师帮助，或点击联系老师1对1在线指导。
