算法代寫 - 算法

時間：2020-11-26

Question 1. (9 marks)
Suppose that P is an m × n matrix, whose entries are non-negative integer. Imagine a game in which Alice
chooses an integer in [m] = {1, . . . , m} and Bob chooses an integer in [n] = {1, . . . , n}. When Alice chooses
i and Bob chooses j, then Alice pays Pi,j dollars to Bob. Alice’s goal is to minimize how many dollars she
pays to Bob, and Bob’s goal is to maximize how many dollars he receives. We will allow Alice and Bob to
choose their integers randomly.
Part a. (4 marks)
Suppose that, in the above game, Alice first chooses a probability distribution D over [m], and tells D to
Bob. Based on knowing D, Bob chooses his integer j ∈ [n], so that he maximizies the expected value of the
payment he receives, assuming Alice chooses her integer according to the distribution D. Then the expected
value of Alice’s payment to Bob is:
valueA(D) = n
max
j=1
EI～D[PI,j ], (1)
where EI～D means that the expectation is with respect to taking I to be a random integer in [m] sampled
according to the probability distribution D. For example D could give probability 12
on I = 1 and probability
12
on I = 2, and then we have
valueA(D) = n
max
j=1
P1,j
2 + P2,j
2 .
Show how to use a linear program to compute a probability distribution D for Alice that minimizes valueA(D)
as defined in (1). The linear program should have as variables the probabilities assigned by D to any integer
in [m], and should also have a variable for valueA(D). Prove that the optimal solution to your linear program
gives an optimal D and its value.
Part b. (5 marks)
Suppose next that, instead, Bob goes first and chooses a probability distribution F over [n], and tells F to
Alice. Based on knowing F, Alice chooses her integer i ∈ [n], so that she minimizes the expected value of
the payment she gives to Bob, assuming Bob chooses his integer according to the distribution F. Then the
expected value of Alice’s payment is:
valueB(F) =
m
min
i=1
EJ～F [Pi,J ], (2)
where EJ～D means that the expectation is with respect to taking J to be a random integer in [n] sampled
according to the probability distribution F. Using the strong duality theorem, prove that the maximum of
valueB(F) defined in (2) over all probability distributions F on [n] equals the minimum of valueA(D) defined
in (1) over all probability distributions D on [m].
Question 2. (15 marks)
Let G = (A ∪ B, E) be a connected undirected bipartite graph, where A and B are the two sides of the
bipartition. Consider the following system of linear constraints:
?u ∈ A ∪ B : Xv:(u,v)∈E xuv = 1 (3)
?e ∈ E : xe ≥ 0 (4)
Let x be a feasible solution to (3)–(4). Your goal in this question is to design a polynomial time algorithm
that, on input G and x, computes a random matching M in G such that, for any e ∈ E, P(e ∈ M) = xe.
Part a. (4 marks)
Let F = {e ∈ E : 0 < xe < 1} be the set of edges corresponding to the fractional coordinates of x. Prove
that, if F is not empty, the subgraph H = (V, F) of G has a cycle C. 2
Part b. (6 marks)
Assume that not all coordinates in x are integers. Use the cycle C to compute two feasible solutions x0 and
x
00 of (3)–(4), so that both x0 and x
00 have strictly fewer fractional (i.e., not equal to 0 or 1) coordinates
than x. Moreover, there should be a value p ∈ [0, 1] such that
x = px0 + (1 p)x
00
.
Hint: use the fact that C must have even length, and consider alternatingly adding and subtracting a value
to the xe variables for e ∈ C (i.e., you add a value for one edge, and subtract for the next edge in the cycle.)
Part c. (5 marks)
Use the previous subquestions and describe a polynomial time algorithm that, on input G and x, computes
a random matching M in G such that, for any e ∈ E, P(e ∈ M) = xe. Justify the correctness and running
time of your algorithm.

- 留學生代寫
- Python代寫
- Java代寫
- c/c++代寫
- 數據庫代寫
- 算法代寫
- 機器學習代寫
- 數據挖掘代寫
- 數據分析代寫
- android/ios代寫
- web/html代寫
- 計算機網絡代寫
- 操作系統代寫
- 計算機體系結構代寫
- R代寫
- 數學代寫
- Finance 金融作業代寫
- Principles of Microeconomics 微觀經濟學代寫
- Accounting 會計代寫
- Statistics統計代寫
- 生物代寫
- 物理代寫
- 機械代寫
- Assignment代寫
- sql數據庫代寫
- analysis代寫
- Haskell代寫
- Linux代寫
- Shell代寫
- SPSS, SAS, R 數據分析代寫
- Principles of Macroeconomics 宏觀經濟學代寫
- Economics 經濟代寫
- Econometrics 計量經濟代寫
- Money and Banking 貨幣銀行學代寫
- Financial statistics 金融統計代寫
- Economic statistics 經濟統計代寫
- Probability theory 概率論代寫
- Algebra 代數代寫
- Engineering工程作業代寫
- Mechanical and Automation Engineering 機械與自動化工程代寫
- Actuarial Science 精算科學代寫
- JavaScript代寫
- Matlab代寫
- Unity代寫
- BigDate大數據代寫
- 匯編代寫
- stat代寫
- scala代寫
- OpenGL代寫
- CS代寫