Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CS 3511: Algorithms Honors Homework 4
• Upload your solutions to as a single PDF on Gradescope. Please anonymize all your submissions (i.e., do not list your name in the PDF), but if you forget, it’s OK.
• You may collaborate with any classmates, textbooks, any resource on the internet (but don’t search for the problem solution), etc. Please upload a brief “collaboration statement” listing any collaborators as the last page of your solutions PDF on Gradescope.
But after the collaboration, always write your solutions individually.
• For each problem, you should aim to keep your writeup below one page. For some problems, this may be infeasible, and for some problems you may write significantly less than a page. This is not a hard constraint, but part of the assignment is figuring out how to easily convince the grader of correctness, and to do so concisely. “One page” is just a guideline: if your solution is longer because you chose to use figures (or large margins, display math, etc.) that’s fine.
• Each problem is worth ten points (even those with multiple subparts).
§1 (Dynamic Programming). Consider a language B of strings of balanced parentheses. B contains the empty string. B also contains any string of the form (x)y, where x and y are arbitrary strings in B. You’re given as input a string S = s1, s2, . . . , sn consisting of “(”, “)”, and “? ” characters. Give a dynamic programming algorithm to compute the number of ways to replace each “? ” of S with either “(” or “)”, to turn it into an element of B. The running time of your algorithm should be O(n 3 ).
§2 (Markov Decision Process). Suppose we are given probability distributions of n inde pendent random variables where for each i ∈ {1, . . . , n} the i-th random variable Xi takes value vi ∈ R≥0 with probability pi and is 0 otherwise. Our algorithm will be revealed outcomes of these independent random variables X1, . . . , Xn one-by-one and it has to immediately and irrevocably accept/reject Xi , where in total it can accept at most 1 random variable and the goal is to maximize the expected accepted value. We will design the optimal policy for this problem. (For intuition on this problem setting, imagine you are looking to hire one of n candidates at your firm. You interview them one-by-one which reveals the value of the i-th candidate Xi and have to immediately hire/reject them.)
Hint: There are two actions in each state called accept/reject. If we accept then we receive the reward Xi and transition to state t, and if we reject then we randomly move to one of the two states corresponding to Xi+1.
(b) For i ∈ {1, . . . , n}, let opti denote the expected value of the optimal policy assuming it did not accept any of the random variables Xj for j < i. Prove that optn = pn · vn and for i ∈ {1, . . . , n − 1} we have opti = 1[vi ≥ opti+1] · pi · vi + (1 − pi) · opti+1 + 1[vi < opti+1] · opti+1 .
§3 (Linear Programs) Alice is trying to get enough oranges and bananas to host a fruit party. To successfully host a party she needs at least 8 oranges and at least 20 bananas. Unfortunately, her local grocery story only sells fruit in bundles. Bundle A costs 3 dollars and contains one orange and two bananas. Bundle B costs 2 dollars and contains three oranges and a banana. Fortunately, the grocery story will allow Alice to buy fractions of bundles (i.e. she can buy 2.5 bundle As to get 2.5 oranges and 5 bananas). They will not allow Alice to buy negative bundles (i.e. she cannot buy -1 bundle As and 3 bundle Bs to get 5 oranges and a banana).
(a) Write a linear program whose solution is the optimal choice of xA, xB for Alice’s problem.
(b) Take the dual of the linear program from part (a).
§4 (LP Duality and Interpretation)
(b) Given a graph G = (V, E) with vertex weights w : V → R≥0, write down an Integer Linear Program (ILP) to find a vertex cover with minimum weight., i.e., find a subset of vertices S ⊆ V of minimum weight P v∈S w(v) such that every edge (a, b) ∈ E has at least one of a or b inside S. Relax the integer constraint to obtain a general linear program (LP). Write the dual of the obtained LP and briefly provide an interpretation of the variables, constraints, and objective value of the dual.