Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

Assignment 1 for CS 231

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 exmaple as a helper function and declare that the paradigm has been used. For example, using seletion sort as a helper function is not sufficient for a problem asking you to use a greedy approach.

Written component

For full marks, you are expected to rovide a brief justification of any answer you provide.

W1.[7 marks]

As an underpaid ( and irresponsible) teacher, you have found a way to supplement your income. You’ll use the “buddy system” on field trips to pair some (but not necessarily all) of the students. Paris of students who woul like to be buddied can agree on bribe that they are willing to pay in order to be buddies.

Using your knowledge from CS231, you choose to represent the information as a graph, where students are represented by vertices and bribes by positice weights on the edges.

We use the term buddy set to refer to a set of edges such that no vertex is the endpoint of more than one edge in the set. (remember that some students might be unpaired, so it is not necessary for every vertex to be the end point of an edge in a buddy set.) The profit of a buddy set is the sum of the weights of the edges in the buddy set. For example, in Sample graph 2 (illustrated on the page Reference material > Python > Module graphs.py), the buddy set {ab,cd} has profit 40, since the weight of edge ab is 10 and the weight of edge cd is 30. The set {ab} is also a buddy set, since it is not required that every vertex appear as the endpoint of an edge in the set. However, the set {ab,bc} is not a buddy set since b is the endpoints of more than one edge in the set.

A) [2 marks] What is a buddy set of maximum profit in Sample graph 4? If there is more than one correct answer, any one will do. Briefly justify your answer, explaining both why it is a buddy set and why its profit is the maximum possible.

B) [2 marks] Give the input and output specifications for a counting problem for the problem of finding buddy sets with the maximum profit. You may use the terms defined above without supplying definitions.

C) [2 marks] By adding a bound, give the input and output specifications for a related decision problem. To answering the question, you should figure out whether the bound needs to be added only to the input specification, only to the output specification, or to both the input and the output specification.

D) [1 marks] In a variant on the problem, we divide the students into the more-mature students and the less-mature students, and only allow buddies in which one is a more-mature student and the other is a less-mature student.

Give another example of a real-world situation to which the decision problem can be applied, either for the original problem or for the variant. Briefly justify why the problem applies by explaining what vertices, edges, and edge weights signify, and what information is given by the output to the problem.

Note: Your situation does not have to be useful. Even ridiculous situations are acceptable, as long as you justify why the problem applies.

W2. [5 marks] In this question, you will be writing a pseudocode function HEAVIEST_ANCESTOR that consumes a tree Instance with positive weight of any ancestor of One if One has at least one ancestor, and 0 if One does not have any ancestors. For example, in samle tree 3, HEAVIEST_ANCESTOR will produce 10 on input d and 0 on input a.

Use the methods in trees.py to write your function, but translate them into pseudocode as described on the reference page on pseudocode. Please see the reference page on trees.py for sample trees as well as the methods.

W3. [8 marks] Use the recipe for analyzing worst-case running time to determine the worst-case running time of MYSTERY as a function of n (the number of vertices in Instance) and m (the number of edges in Instance), expressed in O notation. Be sure to refer to each line in the function and justify the values you determine. For full marks, a list of line numbers and running times for each line is not sufficient. Make sure to show each step of the recipe.

Please see the reference page on the module graphs.py for the costs of graph operations, and the reference page on costs for the costs of all other operations. You may also find it helpful to consult the reference page on pseudocode.

W4. 6 marks/ Use the formal definition of O to show that n3-5n2 logn + 12 E O(n3). Remember that in computer science, log is used to denote log2. Make sure to use specific values of the constants c1, C2, and no.

W5. [4 Marks] In a team-building exercise at your office, employees are to be divided into groups to work together to solve puzzles and compete for a prize. Rather than having teams consist of people who already know each other, teams are groups of people who do not know each other.

Suppose that there are n employees and you wish to form groups of size exactly k (where n is a multiple of k). Your goal is to come up with an exhaustive search algorithm that produces all the possible ways of forming groups in this manner, or False if there is no way to form such groups.

In answering the questions below, you can assume that the information is represented as a graph, where there is a vertex for each employee, and there is an edge between any pair of employees who know each other.

a) [2 marks] What are the [possibilities used by your algorithm?

b) [1 mark] In at most a few sentences, describe how your algorithm processes each possibility. You do not need to use pseudocode, nor to refer to specifics of graphs.py.

c) [1 mark] In at most a few sentences, describe how your algorithm uses the result of processing each possibility to produce the solution to the problem. You do not need to use pseudocode, nor to refer to specifics of graphs.py.

Write a function star that consumes a grid canvas and produces either a list of length two containing the row and column numbers of the centre of a star in canvas or False if canvas does not contain any stars. If canvas contains more than one star, your function may produce the centre of any of the stars in canvas.

You might find it helpful to use the function make_grid to create sample grids for testing.

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