Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 231, Spring 2024
ASSIGNMENT 4
Due date:July 24,202416:00(Waterloo time)
Coverage: Through Module 10
This assignment consists of a written component and a programming component.Please read the instructions on the reference page for assignments carefully to ensure that you submit each component correctly.
Please check the pinned FAQ in the discussion forum for corrections and clarifications.
Note:In assignment questions that specify the use df aparticular 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 expegted to provide a brief justifcation of any answer you provide.
W1.[6 marks]In Assignment 2,we considered a greedy algorithm for finding as maximum size cluster in a graph.Here we will consider the algorithm as an approximation algorithm.
(a)[1 mark]What is the approximation ratio when the instance is a complete graph on at least two vertices?Briefly justify your answer.
(b)[1 mark]What is the approximation ratio when the instance is a tree on at least two vertices?Briefly justify your answer.
(c)[4 marks]Give a family of graphs for which the approximation ratio cannot be bounded above by a constant.That is,provide a function f(n),where f(n)is not a constant function,such that the ratio between the approximate and the optimal solution is at least f(n).You do not need to provide a graph for each value of n, but you should show how to form an infinite family ofgraphs of increasing size.As in W2 of Assignment 2,the statement should hold for any ordering of the vertices,no matter how ties are broken.
W2.[6 marks]In this question,we will consider two possible backtracking algorithms for CLUS- TER PARAMETERIZED BY CLUSTER SIZE,defined as follows:
Input: A graph G and a positive integer k
Output: Yes or no,answering“Is there a cluster in G of size k? Parameter: k
For each of the algorithms described below,answer the following two questions:
● Is the worst-case running time of the algorithm in f(k)·n⁰(1)?
● Is the proposed algorithm guaranteed to produce the correct answer?
(a)[3 marks]Form a search tree in which the root corresponds to the empty set.At each node,form a child for each node not already in the set that is a neighbour of all nodes in the set (vacuously true for the empty set).Stop after k+1 levels,producing true if a node is formed and false otherwise.
(b)[3 marks]Order the vertices.Form a search tree in which the root corresponds to the empty set.At each node,for the next vertex in order,create one set that contains the vertex (if it and the current contents of the set form a cluster)and one that does not contain the vertex.Stop after k+1 levels,producng true if a node is formed and false otherwise.
W3.[9 marks]In this question,you will use hilkclimblng for the problem of REPRESENTATIVE SETS,as defined in Assignment 2.
(a)[3 marks]Describe a hill-climbing apprdach,including the initial solution and how it is updated at each step.For full marks,be sure to explain why your approach can be classified as hill-clambing
(b)[3 marks]Provide an input on which your approach is guaranteed to produce the optimal solution.Yout input mast contain at least 4 sets,and each set must contain at least 2 values.Briefly justify your answer by explaining how your approach performs on the provided input ahd why the solution is optimal.
(c)[3 marks]Provide an input on which your approach is not guaranteed to provide the optimal solution.Your input must contain at least 4 sets,and each set must contain at least 2 values.Briefly justify your answer by discussing both the output of the approach and the optimal solution.
W4.[3 marks]An algorithm for REPRESENTATIVE SETs forms a solution B as follows:consid- ering each set in A one by one,randomly choose whether or not to put the set in B.The probability of adding a particular set is 1/2,so the probability of omitting it is also 1/2. For the purpose of this question,we'll define“high probability”(of producing the correct answer)to be any probability that is greater than 3/4.
(a)[1 mark]Does the algorithm fit the definition of a Las Vegas algorithm?
(b)[1 mark]Does the algorithm fit the definition of a Monte Carlo algorithm?
(c)[1 mark]Is there ever a reason that one might choose to use a randomized algorithm for a problem in P?Briefly justify your answer.
Programming component
Please read the information on assignments and Python 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 fol- lowing files:check.py,graphs.py,and equiv.py,as well as built-in modules such as math and copy.
Be sure to read the instructions on the Python requirements page to ensure that you have imported the files as required.
P1.[14 marks]Write a function cluster_backtrack that consumes a graph and produces a list of IDs of vertices that forms a cluster of maximum size.Your function should use backtracking.
Submit your work in a fle with the name clusterbacktrock.py.