CSE347T代写 Exam 2: Takehome代写

CSE347T

Exam 2: Takehome

CSE347T代写 This exam is limited open book. You may use your course notes, textbook. And any materialon the course You may not talk…

• This exam is limited open book. You may use your course notes, textbook. And any materialon the course You may not talk to your friends or classmates or use any resources on the internet.
• Submit the solutions via Gradescope before 4 PM on Friday, April 16th. Late submissionswill not be accepted for any  You may typeset or handwrite your solutions. But try to make them clear, concise and readable.
• Thereare 2 problems on this  Read each question carefully. Show your work, as partial credit may be given. You will be graded not only on the correctness of your answer. But also on the clarity with which you express it; so be neat. State all assumptions clearly. Do not waste time and paper rederiving facts that we have studied. It is sufficient to cite known results.
• Provide the relevant details for the proofs while being as concise as possible. You will losepoints if you do skip steps or do not provide the appropriate arguments.
• Do not provide multiple solutions to the same problem hoping that one of them is correct.We will only grade the first solution you provide.

Problem 1. CSE347T代写

[25 points] You are given a directed weighted graph G = (V, E) with a source s and a sink t. Each edge (u, v) has weight w(u, v). Your decision problem is “Is there an s-t cut of this graph with a total weight of exactly k?” In other words, can you split the vertices of the graph into two sets S and V − S such that s ∈ S. And t ∈ V − S and the total sum of the weights of the edges that go from a vertex u ∈ S to a vertex v ∈ V − S is exactly k.

Show that this problem is NP-complete.

Problem 2. CSE347T代写

[25 points] You are running a dorm library and you have a set of n books B ={b₁, b₂, …, b_n} and m members X  =  {x₁, x₂, …, x_m}.  For each member x_i, you have R_i  ⊆ B, which is the set of books member x_i wants to read. For simplicity, we can define Y_j ⊆ X as the set of members who want to read book b_j. (Note that we can find these Y_j’s given all the R_i’s since x_i ∈ Y_j iff b_j ∈ R_i.) CSE347T代写

Each member is happy to read the books on their list in any order. Members may read different books at different speeds.  So you also have a function f (x, b) which tells you how much time it takes for member x to read book b.

A member can only borrow one book at a time and a particular book can only be lent to one member at a time. Once a member x borrows book b, they return it after exactly f (x, b) time.

Once they return the book, you can give them another unread book from their list immediately or at any time thereafter.

You want to create a schedule of lending books to members so that all members finish their books as quickly as possible. In particular, F_i is the time at which the member x_i finishes reading all the books on their list. You want to minimize F_max = max_xi∈X F_i.

Here is a candidate greedy approximation algorithm. Once a book is returned, immediately give it to any member who wants to read the book, hasn’t read it yet. And doesn’t have any other book checked out at this time. That is, a book never sits in the library if it can be legally checked out to anyone. We will prove that this algorithm provides a 2-approximation for minimizing F_max.

• [3points]  Say S_i =     bj ∈Ri  f (x_i, b_j). That is, S_i is the total amount of time it will take for member x_i to read all the books on their list if they could read them continuously one after the other. Say S_max = max_xi∈X S_i. Argue that, for any algorithm for this problem, F_max ≥ S_max. That is, S_max is a lower bound for this problem. CSE347T代写
• [3points]  Say Q_j =     xi∈Yj  f (x_i, b_j). That is, Q_j is the total amount of time book b_j will be lent out to all the members Say Q_max = max_bj ∈B Q_j.  Argue that, for any algorithm for this problem, F_max ≥ Q_max. That is, Q_max is also a lower bound for this problem.
• [14 points]Now consider the greedy schedule. Say the last member to finish all the books on their list was x_l (in the greedy schedule).  And the last book they read was book b_k. Say x_l checked out this book b_k at time t. Argue that t ≤ S_max +Q_max −2f (x_l, b_k). Hint: Think about what prevented x_l from getting this book b_k before time t. CSE347T代写
• [5 points]Argue that the greedy algorithm has an approximation ratio of at most 2. For this part, you may assume that all the previous parts are established, even if you were not able to prove them yourself.