Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 231, Spring 2024
ASSIGNMENT 2
Due date: June 19, 2024 16:00 (Waterloo time)
Coverage: Through Module 5
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 of a particnlar paradign, you are expected to come up with a new algorithm using that paradig. It is not sufficient to implement a class example as a helper function and declare that the paradigm has been used. For example, using binary search or mergesort is not sufficient for a problem asking you to use divide-and-conquer.
Written component
For full marks, you are expected to provide a brief justification of any answer you provide.
W1. [6 marks] In this problem, you will develop a counterexample for a greedy algorithm for the problem REPRESENTAT VE SETS, defined below:
REPRESENTATIVE SETS
Input: A set A of sets of numbers
Output: 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 as small as possible
For example, if A{{0,1},{2,3}, {0}, {1}, {2}, {0,3}, {0,2}, {1,2}},
B = {{0,1}, {2,3}} is a solution to the problem because U = {0, 1,2, 3} and the union of the sets in B is also {0, 1,2,3}.
Consider the following algorithm for REPRESENTATIVE SETS.
REPRESENTATIVE SETS(A)
INPUT:A set A of sets of numbers
OUTPUT: A subset of A
1 B←0
2 while there exists some x EU not contained in the union ofthe sets in B
3 Choose a set S in A that contains x and such that no larger set in A contains x
4 Add S to B
5 return B
(a) 3 marks) Give an example of an input on which the algorithm produces the optimal solution, for any order in which elements are considered in Line 2 and any way of breaking ties in Line 3. Your example should contain at least four sets in A and at least four elements in U. Explain both how the algorithm obtains the output and why the output is an optimal solution.
(b) 3 marks) Give an example of an input on which the algorithm does not produce the optimal solution, for any order in which elements are considered in Line 2 and any way of breaking ties in Line 3. Your example should contain at least four sets in A and at least four elements in U. Explain both how the algorithm obtains the output and why the output s not an optimal solution.
W2. [8 marks/ In this question, we consider a greedy algorithm for finding a cluster in a graph, as defined in Assignment 1. Here, we are Ignoring the weights of the edges and simply trying to find a cluster containing the largest nunber of vertices possible.
Our algorithm will make use of the idoa of k-friendly vertices, as defined in Assignment 1. We'll define the friendlinessof a vertex as thle maximum k for which it is k-friendly. For example, in Sample graph3, the vertex with ID "c" has friendliness 2, since it is 2-friendly but not 3-friendly.
The algorithm will proceed as follows:
Order the vertices in nonincreasing order (from large to small) by friendliness, breaking ties arbitrarily
Initialize the cluster-so-far to the empty set
For each vertex in order, add it only if it is a neighbour of all the vertices in the cluster-so-far
After all vertices have been considered, return the cluster-so-far
In the algorithm, we consider a vertex to be a neighbour of all vertices in the empty set.
(a) 2 marks) What is the worst-case running time of the algorithm? Express your answer in O notation as a function of n, the number of vertices in the graph, m, the number justify your answer.of edges in the graph, and g(n), the cost of the first step of the algorithm. Briefly
(b) 2 marks) Does the algorithm produce an optimal solution for Sample graph 4, no matter how ties are broken? Briefly justify your answer by showing how the algorithmbehaves on the graph as well as discussing what the optimal solution is.d
(c) 4 marks) Give an example of a graph on which the algorithm fails to produce the correct solution. Your graph must have an optimal solution of size at least 3, and cannot be any of the sample graphs. Explain both how the algorithm obtains the output and why the output is not an optimal solution.
W3. 5 marks) In this question, you will write a divide-and-conquer algorithm ToTAL that consumes a tree and the ID of a node in the tree and determines the sum of the weights of all nodes in the subtree rooted at the input node. For example, on Sample tree 3 and ID "c", TOTAL will produce 15, summing the weights of the nodes with IDs "c", "e", and "f". Using the tree operations provided on the reference page for trees.py, write a pseudocode function TOTAL that solves the problem.
W4. 5 marks/ In this problem, you will develop recurrence relations for a divide-and-conquer algorithm MYSTERY written in pseudocode. The function call MYsTERY(List, A, B) processes the data items in positions A up to but not including Bin the list List; the size of the instance should be calculated as B-A.
Provide recurrences using O notation, using T(n) to represent the worst-case running time of MYSTERY on an input of size n (where n B- A). Refer to line numbers as needed,and make use the reference page on costs in your analysis
Note: You are not required to solve the recurronces.
MYSTERY(List, A, B)
INPUT: A nonempty list Dist ofintegeys and positions
A and B inList such that A< B
OUTPUT: An integer
1 if A == B
2 return List/A
3 else if A > B-5
4 return List[B]
5 else
6 FrontSplit A+ (B- A) //5
7 MidSplit ← A + 2 (B - A) // 5
8 BackSplit A +4 (B - A)//5
9 if List[A] == List[B]
10 return MYSTERY (List, A, FrontSplit)
11 else
12 Second ← MYSTERY(List, FrontSplit, MidSplit)
13 Third ← MYSTERY (List, MidSplit, BackSplit)
14 Fourth ←MYSTERY (List, BackSplit, B)
15 return Second +Third +Fourth
(a) (1 mark) Use a recurrence to express the base case or cases. Briefly justify your answer by referring to specific line numbers.
(b) [4 marks] Use a recurrence to express the general case. You may express your recurrence relation using instead of=, but be as precise as possible. Briefly justify your answer by referring to specific line numbers; explain which lines correspond to the divide, conquer, and combine stages of the algorithm.
W5. (6 marks) Use the substitution method to show that T(n) is in O(n2log n) for T(n) = 3T(L)+10n2 for n 24, T(2)T(3)50. Hint: Be sure to come up with an explicit "guess” for the upper bound instead of trying to reason using order notation.
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 requrements of the assignment question and the style guide, including aspects of the design recipe.
Although submitting tests is not required, it is highly recomnended 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 followsuch as math and copy.ing files: check.py, graphs.py, pair.py, graphs.py, and equiv.py as well as built-in modules
P1. [10 marks) In this question, you well implement the greedy algorithm for finding a clusterin a graph as described in W2.
Write a function cluster greedy that consumes a graph and produces a cluster. For full marks, your function must implement the algorithm described in W2. Do not try to "fix" the algorithm: if the algorithm produces a cluster that is not the largest cluster in the graph, your function should do the same.
Submit your work in a file with the name clustergreedy.py.
P2. [15 marks] In this question, you will use divide-and-conquer to solve the problem ALIGN, as defined below:
ALIGN
Input: A sequence of distinct integers in increasing order
Output: Yes or no, answering "Is there a position p such that position p contains the value p?"
Write a function align that consumes a (possibly empty) Python list containing distinct integers in increasing order, and produces True if there exists a position p such that position p contains the value p and False otherwise. For example, align([l) will produce False, as there are no values at all, align([-2, 0, 2]) will produce True, as value 2 is in position 2, and align([-3, 4, 6]) will produce False.For the divide step, your algorithm should divide the list roughly in half. You will lose most of the marks for a less even divide step, and almost all of the marks if you do not use divide-and-conquer.
Submit your work in a file with the name align.py.