辅导program、讲解Python，CSS程序设计、Java编程辅导 辅导Web开发|讲解数据库SQL
- 首页 >> Matlab编程 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
[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