代写program、代做Python，CSS程序设计、Java编程代写

日期：2021-06-07 10:07

Question 1

[10 marks]

Every Xmas the Simpson family plays a game of candy, where Marge brings home a big bag

of candies of distinct weights. Lisa and Bart then take turns picking a candy from the bag until

it is empty. After Homer complained, an extra rule was introduced, so now after each pick all

candies with greater weight than the one just picked are also removed from the bag, and Homer

gets to keep those. Yum!

Unfortunately for Homer, Lisa and Bart are normally quite greedy and pick the largest candy

still in the bag each turn (thereby maximizing their total candy), so Homer still gets nothing.

However, this year Lisa and Bart have been fighting, and are angry with each other. Thus

instead of just trying to maximize the amount of candy they get, they try to maximize the

amount they get minus the amount the other one gets.

(a) To help Lisa and Bart, we want to create a python function max_diff(candies) which

takes as input a list of distinct candy weights in descending order, and returns the maximal

total difference in candy weight that can be guaranteed (i.e., regardless of the opponent’s

choices). A recursive implementation of function max_diff(candies) is given below:

def max_diff(candies):

if len(candies) == 0: return 0

max_tail = max_diff(candies[1:])

return max(max_tail, candies[0] - max_tail)

What is the time complexity of this implementation, as a function of n = number of candies?

Justify your answer. [3 marks]

Note: Copying a list takes time proportional to the length of the list.

(b) Maggie now also wants candy. Since she’s the little one, she gets to pick a candy each

time either Bart or Lisa picks one (after Homer get his share). Maggie isn’t angry with

anyone, and always picks the largest candy remaining. Function max_diff(candies) has

been adjusted to deal with this new rule.

def max_diff_maggie(candies):

if len(candies) == 0: return 0

max_head = candies[0] - max_diff_maggie(candies[2:])

max_tail = max_diff_maggie(candies[1:])

return max(max_head, max_tail)

What is the time complexity of max_diff_maggie(candies), as a function of n = number

of candies? Justify your answer. [3 marks]

(c) Describe two different ways how function max_diff_maggie(candies) could be optimized

to run much faster, and analyze the time complexity of your solutions. [4 marks]

1

Question 2

[8 marks]

The decision version of the independent set problem takes an undirected graph and an

integer n as input, and asks whether or not you can pick n nodes (vertices) such that no pair of

them is connected by an edge. The output required is yes or no.

The decision version of the clique problem takes an undirected graph and an integer n

as input, and asks whether or not you can pick n nodes (vertices) such that all of them are

connected to each other by edges. The output required is yes or no.

(a) Explain how you can use an algorithm that solves instances of the clique problem to solve

an instance of the independent set problem. [3 marks]

(b) The independent set problem is a known NP-complete problem, what does the reduction

from clique to independent set tell us about the clique problem? [2 marks]

(c) Let Problem A be some new problem that can be used to solve the clique problem.

That is, there exists an algorithm that uses solutions to instances of Problem A to solve

an instance of the clique problem. Explain how you could use an algorithm that solves

instances of Problem A problem to solve an instance of the independent set problem.

[3 marks]

2

Question 3

[8 marks]

The predicate P(x, y) can be interpreted as “x is a parent of y”

Using quantifiers, we can make logical statements such as

1. ?x ?P(x, x) “no-one is their own parent”

2. ?x ?y P(x, y) “everyone has a parent”

Using the predicate P defined here, provide statements in predicate logic to match the following:

1. “everyone has a grandparent”

2. “no-one is the parent of anyone who is their own parent”, in other words, the Parent

relation is anti-symmetric

3. “everyone has at most two parents”, which is equivalent to “no-one has three parents”

[3 marks]

Using instances of the Parent predicate P, define new predicates for the following relations:

1. Child(x, y) “x is a child of y”

2. Sibling(x, y) “x is a sibling of y”, in other words, x and y have a parent in common

3. Cousin(x, y) “x is a cousin of y”, in other words, x and y have parents who are siblings

[3 marks]

Show that your Sibling relation is symmetric, in other words Sibling(x, y) ?? Sibling(y, x)

[2 marks]

Note that you can use the expressions “for all”, “there exists, “not”, “and”, “or”, “implies”, “if

and only if” in place of the corresponding logical symbols if you find this easier to type.

3

Question 4

[8 marks]

The following function takes a list of zeros and ones as an argument and returns the longest

contiguous sequence of ones in the list. Four loop invariants are given as comments before the

start of the for loop.

def longest_block_of_ones(alist):

lb_start = 0

lb_end = 0

lb_size = 0

current_block_start = 0

current_block_size = 0

# all the values in the slice alist[current_block_start : i] are ones

# current_block_size is the size of the slice alist[current_block_start : i]

# the slice alist[lb_start : lb_end] is the longest block of ones seen so far

# lb_size is the size of the slice alist[lb_start : lb_end]

for i in range(len(alist)):

if alist[i] == 0:

current_block_start = i+1

current_block_size = 0

if alist[i] == 1:

current_block_size += 1

if current_block_size > lb_size:

lb_size = current_block_size

lb_start = current_block_start

lb_end = i+1

return alist[lb_start:lb_end], lb_size

(a) Give arguments to show that each of the invariants holds before the loop is executed for

the first time. [2 marks]

(b) Give arguments to show that, if each of the invariants holds before an arbitrary iteration

of the loop, then each of them holds before the next iteration of the loop. [4 marks]

(c) The loop ends after iterating over all elements of the list. Using a selection of the loop

invariants, give an argument to show that the function returns the longest contiguous

sequence of ones in the list and its size. [2 marks]

4

Question 5

[6 marks]

The activity selection problem is defined as follows: Given n activities and their start

and finish times, find a subset of k non-conflicting activities, with k as large as possible. Two

activities conflict if there is a point in time when both are active.

(a) Suppose I develop a greedy algorithm to solve the activity selection problem using the

following greedy rule: “At each step, choose the activity requiring shortest time that doesn’t

conflict with any previously chosen activity.”

Present a counter-example, by providing a set of activities with (start, finish) times, to show

that a greedy algorithm using this rule will not always return the largest possible subset of

non-conflicting activities. [2 marks]

(b) Give two more different greedy rules (not necessarily optimal, but sensible) that could be

used to develop a greedy algorithm to solve the activity selection problem. [2 marks]

(c) For each of your greedy rules from part (b), give the O(f(n)) running time for a greedy

algorithm that attempts to solve the activity selection problem by applying this rule

on a set of n activities. [2 marks]

5