Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 231, Spring 2024
ASSIGNMENT 3
Due date: July 10, 2024 16:00 (Waterloo time)
Written component
For full marks, you are expected to provide a brief justification of any answer you provide.
W1. 10 marks/ In this question we wlll dse dynamic programming for the following computation:
Given inputs x1,...,En and ,..,Un such that xi
A(i,i) = y; for 1 ≤ i ≤ n
for 1 ≤ i < j ≤ n
(a) [2 marks)Calculate A(1,3), where x = 1, x2 = 2, 3 = 3, y = 1, y2 = 4, and y3 = 9. For full marks, show your work.
(b) [2 marks] What are the base cases and their values?
(c) 2 marks] What is the smallest possible shape and size of a single table used to calculate A(1, n)?
(d) [2 marks) Draw the table needed to solve the problem for A(1,4). Label each entry with the information stored in that location as well as the order in which it is filled. For the ordering, fill in all the base cases with the number O and the rest of the entries using numbers 1, 2, and so on to show the order in which entries should be evaluated. Any nonzero number should appear at most once.
(e) (2 marks) State and briefly justify the running time of the algorithm for A(1, n) in Θ notation as a function of n. You can assume that each mathematical operation can be executed in Θ(1) time.
W2. 5 marks) In this question, we will consider lower bounds on MAXiMuM SizE CuusTER,as defined below:
MAXIMUM SIZE CLUSTER
Input: A graph G
Output: The maximum size of any cluster in G
For your bound, you will consider only algorithms in which the key operation is specifying in any other way. two vertices and asking whether they are adjacent. Algorithms may not access the graph in any other way.
The lower bound should be as big and as precise as possible; do not use order notation. You should explain an adversary strategy and how the strategy can be used to prove the lower bound.
(a) 1 mark/ Describe an/adversary strategy.
Remember that an adversary can store and compute whatever it wishes, without worrying about limits on resources, but is unable to know what the algorithm isgoing to do next.
(b) 4 marks) State and prove the adversary lower bound in terms of n.d
W3. 8 marks/ Using all the steps of the recipe shown in lecture, prove that REpRESENTATIVE SETS DECISION, defined below, is in NP.
REPRESENTATIVE SETS DECISION
Input: A set A of sets of numbers and a positive integer k
Output: Yes or no, answering "Does there exist a subset B of A such that:
the union of all the sets in B is equal to the union U of all the sets in A, and
the size of B is at most k?"
W4. 7 marks) Using the fact that CLIQUE is NP-complete, follow the steps in the recipe toshow that CLUSTER DECISION is NP-complete. You may assume that CLUSTER DECISION is in NP.
CLUSTER DECISION
Input: A graph G with positive weights on edges, a positive integer k, and a positive integer B
Output: Yes or no, answering "Is there a cluster in G of size k and with total value atinteger Bmost B?"
Since the first two steps of the recipe have been completed, start your work at the thirdstep.
Programming component
Please read the information on-assignments and Python carefully to ensure that you are using the correct version of Pyhon 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, grids.py, graphs.py, and equiv.py, as well as built-in modules such as math and copy.
P1. [18 marks] In this question, you will implement the dynamic programming algorithm for STRING EDITING, defined as follows:
Input: A source string S, a target string T, and integer costs ca for addition, ca fordeletion, and cs for substitution
Output: The lowest cost of any editing sequence that can be used to edit s into t
For example, we can edit the string cats into the string chats by a single addition (ofh), into the string cat by a single deletion (of s), and into the string cots by a single substitution (of a into o). We could also edit cats into cots by a deletion (of a) followed by an addition (of o). If c =1, ca = 2, and c = 10, using one deletion and one addition would have a total cost of ca +ca = 3, which would be cheaper than a substitution at a cost of Cs = 10.
The problem can be solved using dynamic programming, where C[i,i] is defined as the minimum cost to edit S[: i] into T[: i]. The following facts can be used:
If S[i - 1] = Ti- 1], then Cli,j] = C[i - 1,j- 1].
Otherwise, Cli,j]= min{Cli-1,j-1]+ca,Cli-1,j]+ca,C[i,j-1]+ca}
Write a function string_edit that consumes two strings source and target and integers add_cost, delete_cost, and sub_cost and produces the cheapest cost of an edit sequence from source to target. Your function must use dynamic programming.
For full marks, you must use grids. To use the module grids.py, use the line frongrids import *; do not include the code for grids.py directly in the file you submit. Submit your work in a file with the name stringedit.py
P2. [7 marks/ In this question, you will write a verification algorithm for CLusTER DECIsIoN. as defined in Question W4.
Write a function cluster verify that consumes a graph graph, two integers size and bound, and a certificate. You cannot make any assumptions about the type of certificate.
Your function should produce True if certificate is a list of strings of length size, where the strings are distinct IDs ofvertices in graph that form a cluster with total value at most bound. Otherwise, your function should produce False.
Here are a few examples, assuming that graph_four is Sample graph 4. Then, cluster verify(graph_fo produce2, 17, ["d","g"])willTrue, since the two vertices with Ds in the certificate form a cluster of total value 11, and 11 ≤ 17. However, cluster_verify(graph_four, 3, 17, ["b","f","g"]) will produce False, since the vertices with the IDs in the certificate do not form a cluster, and cluster verify(graph four, 3, 14, ["e","f","g"]) will produce False, since the total value of the cluster is 16, which is greater than 14.
Submit your work in a file with the name clusterverify.py.