代写代考 COMP3530 comp3530 Assignment 5 s2 2016 – cscodehelp代写

comp3530 Assignment 5 s2 2016
This assignment is due on Nov 12. All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Plagiarism” policies.
Problem 1. Let f and g be two subset functions over a common ground set U. Consider the following functions:
a) h1(S) = f(S)g(S) for all S ⊆ U, and b) h2(S)=􏰂f(S)forallS⊆U.
For each function hi prove or disprove that hi is submodular whenever f and g are normalized, monotone non-decreasing, and submodular.
Problem 2. Consider an instance of the knapsack problem where we have n items
with weight w1, . . . , wn and benefit b1, . . . , bn, and knapsack with capacity W. For
a set S ⊆ {1,…,n} let f(S) be the value of the knapsack problem restricted to the 􏰀􏰁
itemsinS;namely, f(S)=max ∑bi :A⊆Sand ∑wi ≤W . i∈A i∈A
Prove that f is not submodular.
Problem 3. Let T be a rooted tree having node weights w : V → R+. For a non- empty set S ⊂ V let A(S) be the set ancestors of any node is S, and let C(S) be the set of common ancestors to all nodes in S. Finally, we define A(∅) = C(∅) = ∅. Notice that these sets are always non-empty if S ̸= ∅ because the root of T is an ancestor to all nodes in V (we consider a node to be an ancestor of itself).
Let f(S) = ∑u∈A(S) w(u) and g(S) = ∑u∈C(S) w(u). Prove or disprove that these functions are submodular.
Problem 4. Let G = (V, E) be a strongly connected directed graph. We define an alternative cascading process via an iterative process. Starting from A0 = ∅ and A1 =S,whereSisourtargetset,wedefineAi+1 =Ai∪Nout(Ai)1 fori>1.
For v ∈ V let τv to be the index of the first A-set containing v; i.e., v ∈ Aτv and v ∈/ Aτv−1. Since G is strongly connected tv is well-defined for all S ̸= ∅.
We define the average cover time of V from S ̸= ∅ to be f(S)= 1 ∑τv.
|V| v∈V To complete the function, we define f (∅) = ∞.
Prove that f is monotone non-increasing and supermodular.
1Recall that Nout(X) = {u ∈ V : ∃(x,u) ∈ E and x ∈ X} is the out neighborhood of X 1