[SOLVED] CS 124 Homework 2: Spring 2022

CS 124 Homework 2: Spring 2022
Your name: Collaborators:
No. of late days used on previous psets:
No. of late days used after including this pset:

Copyright By Assignmentchef assignmentchef

Homework is due Wednesday at midnight ET. You are allowed up to twelve (college)/forty (exten- sion school) late days through the semester, but the number of late days you take on each assignme nt must be a nonnegative integer at most two (college)/four (extension school).
Try to make your answers as clear and concise as possible; style may count in your grades. Assign- ments must be submitted in pdf format on Gradescope. If you do assignments by hand, you will need to scan in your results to turn them in.
You can collaborate with other students that are currently enrolled in this course in brainstorming and thinking through approaches to solutions but you should write the solutions on your own: you must wait one hour after any collaboration or use of notes from collaboration before any writing in your own solutions that you will submit.
For all homework problems where you are asked to give an algorithm, you must prove the correctness of your algorithm and establish the best upper bound that you can give for the running time. Generally better running times will get better credit; generally exponential time algorithms (unless specifically asked for) will receive no or little credit. You should always write a clear informal description of your algorithm in English. You may also write pseudocode if you feel your informal explanation requires more precision and detail, but keep in mind pseudocode does NOT substitute for an explanation. Answers that consist solely of pseudocode will receive little or not credit. Again, try to make your answers clear and concise.
(a) (7 points) We saw in lecture that we can find a topological sort of a directed acyclic graph by running DFS and ordering according to the postorder time (that is, we add a vertex to the sorted list after we visit its out-neighbors). Suppose we try to build a topological sort by ordering in increasing order according to the preorder, and not the postorder, time. Give a counterexample to show this doesnt work, and explain why its a counterexample.
(b) (7 points) Same as above, but we try to sort by decreasing preorder time.
(20 points) News from Cambridge: every night, snow falls and covers all the sidewalks. Every morning, the citys lone snow shoveler, Pat, is tasked with clearing all the sidewalks of snow. Proper snow-shoveling technique requires that sidewalks on opposite sides of the same street be shoveled in opposite directions. (Every street has sidewalks on both sides.) Give an algorithm to find a snow-shoveling path for Pat that doesnt require any more walking than necessaryat most once per sidewalk. (If you have to assume anything about the layout of the city of Cambridge, make it clear!) (Your algorithm should work for any city, not just the Cambridge in which Harvard is.)

3. (0 points, optional)1 This exercise is based on the 2SAT problem. The input to 2SAT is a logical expression of a specific form: it is the conjunction (AND) of a set of clauses, where each clause is the disjunction (OR) of two literals. (A literal is either a Boolean variable or the negation of a Boolean variable.) For example, the following expression is an instance of 2SAT:
(x1 x2)(x1 x3)(x1 x2)(x4 x3)(x4 x1).
A solution to an instance of a 2SAT formula is an assignment of the variables to the values T (true) and F (false) so that all the clauses are satisfied that is, there is at least one true literal in each clause. For example, the assingment x1 = T, x2 = F, x3 = F, x4 = T satisfies the 2SAT formula above.
Derive an algorithm that either finds a solution to a 2SAT formula, or returns that no solution exists. Carefully give a complete description of the entire algorithm and the running time.
(Hint: Reduce to an appropriate problem. It may help to consider the following directed graph, given a formula I in 2SAT: the nodes of the graph are all the variables appearing in I, and their negations. For each clause ( ) in I, we add a directed edge from to and a second directed edge from to . How can this be interpreted?)
4. (15 points) The risk-free currency exchange problem offers a risk-free way to make money. Suppose we have currencies c1, . . . , cn. (For example, c1 might be dollars, c2 rubles, c3 yen, etc.) For various pairs of distinct currencies ci and cj (but not necessarily every pair!) there is an exchange rate ri,j such that you can exchange one unit of ci for ri,j units of cj. (Note that even if there is an exchange rate ri,j, so it is possible to turn currency i into currency j by an exchange, the reverse might not be true that is, there might not be an exchange rate rj,i.) Now if, because of exchange rate strangeness, ri,j rj,i > 1, then you can make money simply by trading units of currency i into units of currency j and back again. (At least, if there are no exchange costs.) This almost never happens, but occasionally (because the updates for exchange rates do not happen quickly enough) for very short periods of time exchange traders can find a sequence of trades that can make risk-free money. That is, if there is a sequence of currencies ci1,ci2,,cik such that ri1,i2 ri2,i3 rik1,ik rik,i1 > 1, then trading one unit of ci1 into ci2 and trading that into ci3 and so on back to ci1 will yield a profit.
Design an efficient algorithm to detect if a risk-free currency exchange exists. (You need not actually find it.)
5. (20 points) Suppose that you are given a directed graph G = (V, E) along with weights on the edges (you can assume that they are all positive). You are also given a vertex s and a tree T connecting the graph G that is claimed to be the tree of shortest paths from s that you would get using Dijkstras algorithm. Can you check that T is correct in linear time?
6. Patients who require a kidney transplant but do not have a compatible donor can enter a kidney exchange. In this exchange, patient-donor pairs pi di may be able to donate to each other: theres an input function c such that for each pair (i,j) of patient-donor pairs, either
1We wont use this question for grades. Try it if youre interested. It may be used for recommendations/TF hiring.

c(i,j) = 1 and di can donate a kidney to pj, or c(i,j) = 0 and di cant donate a kidney to pj. As an example, suppose that we have patient-donor pairs:
p1 d1,p2 d2,p3 d3,p4 d4,p5 d5,
that c(3,2) = c(3,1) = c(2,1) = c(1,3) = 1, and that for all other inputs c is 0. That is, in this example, d3 can donate to p2 or p1, d2 can donate to p1, and d1 can then donate to p3 in the original p3 d3 pair. Then a set of these donations can simultaneously occur: all those donations except d3 p1 could happen simultaneously, with p4 d4 and p5 d5 not participating. For every donor that donates a kidney, their respective patient must also receive a kidney, so if instead c(1, 3) = 0, no donations could occur: d3 will refuse to donate a kidney to p2 because p3 wont get a kidney.
(a) (5 points) Give an algorithm that determines whether or not there exists any nonempty set of donations that can occur.
(b) (20 points) Suppose that no set of donations can occur in the previous part, but we add of an altruistic donor, d0. This altruistic donor is not bound to a patient, and is unconditionally willing to donate a kidney. Additionally, for each donation from di to pj , consider that there is some value vij associated with that donation. Give an algorithm that returns the highest value donation sequence. For partial credit, you can consider the cases where 1) every donation has the same value or 2) donations have possibly-distinct but only positive values.
7. has been thinking about how he can be more effective as Iron-Man and hes finally figured it out: two Iron-Men! He has two Iron-Man suits and he can control each remotely. Unfortunately, hes been having trouble getting the technology exactly right, so every time he makes a move in one suit, the other suit follows with a different move. Precisely, if Iron-Man 1 moves right, Iron-Man 2 moves up; if IM1 moves left, IM2 moves down; if IM1 moves up, IM2 moves left; and if IM1 moves down, then IM2 moves right. To slow him down, Thanos dropped one suit in Los Angeles and the other in Dallas. Tony needs your help getting both his suits back to in.
Because of COVID-related travel restrictions, the Iron-Men cannot leave the United States. For the sake of this problem, assume that the United States can be modelled as an n by n grid, as below (climate change has shaved off the East and West coasts).

If an Iron-Man tries to move off the grid or into an obstacle, it merely stays in place. Ad- ditionally, each step has a cost that depends on the robots location. For example, moving left from (0, 1) might cost 1 fuel but moving left from (10, 15) might require jumping over someones backyard pool and thus might cost 3 fuels. Once a robot reaches, it powers down and costs 0 fuels even as its counterpart continues to move. You are given the positions of Los Angeles (xl, yl), Dallas (xd, yd), and (xny, yny), the positions of all obstacles (xoi , yoi ), and the cost of every possible move from every possible location.
(a) (10 points) Give and explain an asymptotic upper bound on how many possible posi- tions there are for the pair of Iron-Men, and explain why no better asymptotic upper bound is possible.
(b) (20 points) Give an algorithm to find the cheapest sequence of {L, R, U, D} moves (that is, the one that requires you to buy the smallest amount of robot fuel) that will bring both Iron-Men home to.
Hint: Try to represent the position of the two Iron-Men as a single vertex in some graph. For full credit, it suffices to find an O(n8) algorithm, but an O(n4 log n) algorithm may be eligible for an exceptional score.

CS: assignmentchef QQ: 1823890830 Email: [email protected]