CS 124 Homework 2: Spring 2023
Your name: Collaborators:
No. of late days used on previous psets:
No. of late days used after including this pset:
Homework is due Wednesday Feb 15th at 11:59pm ET. You are allowed up to twelve (college)/forty (extension school), but the number of late days you take on each assignment 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 your papers to turn them in.
You may not write anything that you will submit within one hour of collaborating with other students, language models, the internet, etc., or using notes from such sources. That is, whatever you submit must first have been in your head alone, or notes produced by you alone, for an hour. Subject to that, you can collaborate with other students, e.g. in brainstorming and thinking through approaches to problem-solving.
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 no credit. Again, try to make your answers clear and concise.
(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 doesn’t work, and explain why it’s a counterexample.
(b) (7 points) Same as above, but we try to sort by decreasing preorder time.
Solution for both parts: Consider the graph G = (V,E) with V = {1,2,3,4} and E = {(1, 2), (1, 3), (2, 4), (3, 4)}. In a run of DFS that breaks ties to visit vertices in increasing order, the preorder+postorder numbers are as follows: 1 [1, 8], 2 [2, 5], 3 [6, 7], 4[3, 4], where the notation u[i,j] denotes preorder(u) = i and postorder(u) = j. Ordering by preorder yields 1243 which is not a valid topological sort since 4 is listed before one of its predecessors, namely 3. The reversed list 3421 also does not produce a valid topological sort as both 2,3 are listed before their common predecessor 1.
2. In this problem we consider two versions of “Pebbling Games”, a class of “solitaire” games (played by one player). In both versions, the input to the game includes an undirected graph G with n vertices and m edges, and positive integer parameters c and k ≤ n. At the beginning of the game, the player is given k pebbles which are placed on vertices 0, 1, . . . , k − 1. At any given moment of time, the k pebbles are located at some k (not necessarily distinct) vertices of the graph. In each move, the player can move any pebble to a vertex v, provided that prior to this move, at least c vertices adjacent to v have a pebble.
(a) (20 points) In version 1 of the game, we have c = k = 1 and so the unique pebble effectively moves across an edge of the graph. In this version, the player wins if there is a strategy that traverses every edge (in both directions) in exactly 2m moves, where m is the number of edges of G. Give a winning strategy (i.e., an algorithm that outputs an order in which the edges are traversed) for the player for every connected graph G. Solution: The most common solution approach is roughly to run DFS, moving the pebble along edges as DFS explores them. Specifically, we can:
Run DFS, starting at vertex 0. Whenever DFS follows an edge (u,v) to an unvisited vertex v (that is, when DFS prevists v), move the pebble from u to v. Whenever DFS finishes exploring a vertex v and returns to the previous vertex u in its stack (that is, when DFS postvisits v), move the pebble from v to u. Whenever DFS tries an edge (u, v) to an already-explored vertex v with preoder(v) > preorder(u), move the pebble from u to v and then from v back to u.
Proof of correctness: after each step of DFS, the pebble is at the top vertex of the DFS stack, so those moves are legal. In an undirected graph, every edge is either a tree edge or a back edge. If (u, v) is a tree edge with preorder(u) < preorder(v), then the pebble traverses (u,v) when v is first explored from u and (v,u) when DFS finishes at v, and no other times. If (u, v) is a cross edge with preorder(u) < preorder(v), then the pebble traverses it in both directions exactly once, when DFS visits v (the second vertex it visits of u and v), and no other times.
Pseudocode for that solution is:
Procedure SEARCH(v) vertex v
explored(v) := 1 previsit(v)
for (v, w) ∈ E
if explored(w) = 0 then p(w) := v
Print (v, w) /* Traverse (v, w) */
SEARCH(w) /* Pebble will perform a walk starting from and returning to w */ Print (w, v) /* Pebble traverses (w, v) */
else if preorder(w) < preorder(v) and w ̸= p(v) then /* (v,w) is a back edge */
Print (v, w) /*Pebble traverses (v, w) */ Print (w, v) /* Pebble traverses (w, v) */
endfor postvisit(v)
end search
Our final algorithm is to run SEARCH(s) from any one vertex s in the graph. Runtime Analysis: The runtime is asymptotically the same as that of DFS with O(1) additional cost per step of the DFS. So overall the runtime of our algorithm is O(n + m) for a graph on n vertices and m edges.
(b) (20 points) In version 2 of the game, c and k are arbitrary and there is a special designated target vertex t such that the player wins if they can place a pebble on t in any finite number of moves. Give an algorithm to determine if a given graph G has a winning strategy. For full credit, your algorithm should run in time at most O(n2k). Algorithm:
i. Define a graph G′ with n vertices corresponding to subsets of size k of the vertices k
of G. (We list the vertices of G′ by listing all sorted k-tuples of vertices of G, e.g.
by k nested for loops, each of which starts at the previous vertex plus 1.)
ii. For each vertex v′ of G′ corresponding to vertices (v0, v1, . . . , vk−1) of G, we similarly
list all k subsets of c of those k vertices. c
iii. For each subset, count, for each vertex of G, the number of vertices of G adjacent to all c vertices of that subset. (For instance, make an array of length n corresponding to the vertices of G, and, for each vertex vi, add 1 to the entries for all its neighbors.) Record the set S(v′) of vertices of G that are adjacent to all c vertices of at least one subset.
iv. For each vertex v in S(v′) and each vertex u in v′, we define an edge in G′ from v′ to v′ \{u}∪{v}. (After we add v to and remove u from v′, we sort the list by insertion sort, since vertices of G′ are ordered k-tuples.)
v. Run one DFS search on the resulting graph, starting from the vertex s′ = (0, 1, 2, . . . , k− 1) of G′. If DFS ever explores a vertex containing t, return True; if DFS halts with- out doing so, return False.
Proof of correctness: First, if there is a winning strategy, then there is a winning strategy that only uses positions where all k pebbles are always at distinct vertices: if we can win after moving a second pebble x to a vertex v, we could instead win by the same sequence of moves, except that instead of moving x to v, if we would ever move a pebble from v, we move x instead.
Therefore, there is a winning strategy if and only if there is a sequence of legal transi- tions (via pebble moves) between configurations of all k pebbles. If we define a graph whose vertices are the configurations of all k pebbles and whose edges are the le- gal transitions (via pebble moves) between them, then there is a winning strategy if and only if a configuration containing t is in the connected component containing the starting configuration, that is, if and only if a DFS search starting at the vertex corresponding to that configuration reaches a configuration containing t.
The algorithm above implements the definition of legal pebble moves: a pebble move from u to v in a configuration C ∋ u is legal if there is a subset of c of its k pebbles which are all adjacent to v, and the algorithm checks all such subsets.
浙大学霸代写 加微信 cstutorcs
i. We take O( n) time to list the n vertices of G′.
ii. We take O( n k) time listing subsets of size c of each vertex of G′. kc
iii. For each of O( n k) subsets of size c, we take O(nc) time to count how many of the kc
vertices of G are adjacent to all c vertices of the subset, for a total of O( n knc) kc
iv. For each of O( n) vertices of G′, for each of O(k) legal vertices to move a pebble
from, for each of O(n) legal vertices to move a pebble to, we write down an edge of the graph, which requires sorting a vertex (a list of length k). Since the vertex is already sorted except for the one new added element, insertion sort does so in O(k) time, for a total of O( nnk2) time.
v. DFS on a graph with O( n) vertices and O( nnk) edges takes time O( nnk) kkk
Therefore, the total time for the algorithm is O( nnk2 + n knc). Note that n = kkck
O(nk/k2), so the first term is O(nk+1), and n = O(nk/k!) and k = O(k!/c), so the kc
second term is also O(nk+1), and the whole algorithm runs in time O(nk+1).
(c) (0 points, optional)1 Find an algorithm for version 2 of the game which runs in time
O(nk log n).
3. 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: there’s an input function c such that for each pair (i,j) of patient-donor pairs, either c(i,j) = 1 and di can donate a kidney to pj, or c(i,j) = 0 and di can’t 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 won’t get a kidney.
(a) (5 points) Give an algorithm that determines whether or not a set of donations can occur.
Solution: Denote the set of patient-donor pairs as {p1 − d1, p2 − d2, . . . , pn − dn}. Define G = (V,E) be a directed graph with V = {v1,...,vn} and E = {(ei,ej) | di can donate to pj}.
We claim that a set of donations can occur if and only if G contains a cycle. In the forward direction, assume a set of donations can occur. Choose one such set, and let S ⊆ V denote the (nonempty) subset of nodes vi such that di (and therefore pi) partic- ipates in this set of donations. Assume for the sake of contradiction G does not contain
1We won’t use this question for grades. Try it if you’re interested. 4
程序代写 CS代考 加QQ: 749389476
a cycle. Then G is a DAG, and a topological ordering exists, call it {vi1,vi2,...,vin}. Now consider the smallest index k such that vik ∈ S. By our definition of S, dik must have donated a kidney, so pik must have received a kidney, say from dik where vik ∈ S. Then k > k since we chose k to be minimal, but we also have that (eik,eik) ∈ E, so k < k by the topological ordering property, a contradiction. Hence G must contain a cycle.
Intheotherdirection,assumeGcontainsacycle,callitvi1 →vi2 →···→vik−1 →vik → vi1. Then the following set of donations can occur: di1 → pi2,di2 → pi3,...,dik−1 → pik,dik → pi1. This works because for j = 2,3,...,k, pij receives a kidney from vij−1, and pi1 receives a kidney from dik , so the donor-patient condition is fulfilled.
Therefore, we can determine whether a set of donations can occur by checking if G contains a cycle. This can be done by running DFS and checking for whether a back edge exists. The time complexity is O(|V | + |E|).
(b) (20 points) Suppose that no set of donations can occur in the previous part, but we add 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.
We claim that every valid set of donations can be written in the following form:
a → pik,dik → pik−1,dik−1 → pik−2,...,di2 → pi1,
where i1, . . . , ik are distinct. To show this claim, consider some valid set of donations. By the problem assumption, no set of donations excluding a exists, so a must donate in this set. Suppose there are m participating donors besides a, for a total of m+1 kidneys being donated. By the donor-patient condition, the m patients corresponding to the m donors must each receive kidneys. The remaining kidney therefore must be donated to another patient pi1 who is the only receiving patient whose corresponding donor does notdonate.Forpatientpij,wecanfindthedonordij+1 forthispatientandeitherstopif dij+1 = a or continue by examining the donor pij+1 . This process inevitably terminates as there are only m + 1 total donations, and we obtain the chain
a → pik,dik → pik−1,dik−1 → pik−2,...,di2 → pi1
with k ≤ m+1. If k < m+1, then there are additional donors dik+1,...,dim+1 (distinct from di1, who does not donate) and thus their corresponding patients pik+1,...,pim+1 involved in the set of donations, and since all other donors and patients involved in the set of donations are already matched, these m − k remaining donors must be matched with the m − k remaining patients. But if we take our original set of donations and remove all k donations in the above chain, we are left with m − k donations in which for
Computer Science Tutoring
each donor dij with k + 1 ≤ j ≤ m + 1, pij still receives a kidney (as we only removed pi1 , . . . , pik from the set of receiving patients), so this set of m − k donations is valid while excluding a, a contradiction. We conclude that k = m + 1, i.e. the entire set of donations can be expressed as one long chain of donations starting with a and ending with pi1 as above. Now define the graph G = (V, E) to be the same as in part (a). Since no valid donation set excluding a exists, G must be a DAG by the claim in part (a). Now we make two modifications to G: all (directed) edges (ei,ej) are now assigned weight −vij, and we add a new node a and draw an edge (a,vi) for all i such that the altruistic donor can donate to pi. Note that G remains a DAG, since there are still no cycles not involving a (as all newly added edges are incident to a), and no cycle can involve a since a has no incoming edges. Note that every possible set of donations, expressible as a single chain in the format above, corresponds to a path a → vik → vik−1 → ··· → vi1 with total value equal to the negative of the total path weight. Thus, we can find the highest-value donation sequence by finding the shortest path in the DAG G starting at a. This is exactly the “shortest paths in a DAG” problem for which a linear-time algorithm was presented in class.
4. (10 points) Design an algorithm to solve the following Logical Inference problem. The input to the algorithm is a collection of n propositions A1,…,An and a subset of known implications where an implication Ai ⇒ Aj asserts that Aj is true if Ai is true. The set of known implications is not necessarily complete and so even though Ai ⇒ Aj and Aj ⇒ Ak should imply Ai ⇒ Ak, the last implication may be missing in the input sequence. The goal of your algorithm should be to output all two-way implications (that is, pairs (i,j) such that Ai ⇒ Aj and Aj ⇒ Ai) that are implied by the input implications. Your run time should be O(n + m + l) where n is the number of propositions, m is the number of input implications and l is the number of output implications.
We can represent each proposition as a vertex and each implication Ai =⇒ Aj as a directed edge (Ai,Aj) in a graph G. Then we can use Kosaraju’s algorithm (the SCC-finding algo- rithm taught in class) to find strongly connected components and create a new SCC graph G′ of this problem. Then for each SCC we take all vertices in the SCC and output all possible pairings of vertices in the SCC with forward and backward implications. Details in Algorithm 1.
Algorithm 1 Output Implications
A is the propositions, S is the known implications G ← (A,S)
G′ ← SCC graph of G
output ← [ ]
forvinG′ do
add all possible implications to output for the vertices of G in the SCC v (so if u,w are two
verticesinvthenaddu =⇒ wandw =⇒ u) end for
return output
Correctness: Any two propositions (their associated vertices) are in the same SCC if and
only if they imply each other though some chain of known implications by our graph model, and vice versa.
Runtime: The graph transformation takes O(n + m) time. Creating the SCC graph of G takes O(n + m) time using Kosaraju’s algorithm. Adding all combinations of vertices in each SCC to the output is O(l) This results in a total runtime of O(n + m + l).
5. (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 … · rik−1,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.)
Define a directed graph G with vertices V (G) = {v1, v2, . . . , vn, s} and edges E(G) = {(vi, vj ) | ri,j exists} S{(s,vi)}, where edge (vi,vj) has weight −logri,j and edge (s,vi) has weight 0. In other words, G has a node vi representing each currency ci and a directed edge from vi to vj with weight − log ri,j for any currencies ci, cj such that ci can be exchanged to cj , and also has a source vertex that can reach every other vertex.
We claim that a risk-free currency exchange exists iff G contains a negative cycle reach- able from s. In the forward direction, assume that a risk-free currency exchange exists. Then we can choose a sequence of currencies ci1 , ci2 , …, cik satisfying ri1,i2 ·ri2,i3 · · · rik−1,ik ·rik,i1 > 1. By construction, the edges (vi1,vi2),(vi2,vi3),…,(vik−1,vik),(vik,vi1) exist and form a cycle in G. The weight of the cycle in G is then
w(cycle)=−logri1,i2 −logri2,i3 −···−logrik−1,ik −logrik,i1
= − log r
= − log r
< − log 1 =0
+ · · · + log r
+ log r ik ,i1
· r ik ,i1
Hence G contains a negative cycle, and this cycle is reachable from s.
Conversely, assume G contains a negative cycle, call it (vi1 , vi2 ), (vi2 , vi3 ), . . . , (vik−1 , vik ), (vik , vi1 ). (Since s has no in-edges, it cannot be a part of any cycle.) By our construction, the weight
of (via,vib) is −logria,ib, and so we have that
0>−logri1,i2 −logri2,i3 −···−logrik−1,ik −logrik,i1 = − log r · r · · · r · r ,
i1 ,i2 i2 ,i3 ik−1 ,ik ik ,i1
which implies that ri1 ,i2 · ri2 ,i3 · · · rik−1 ,ik · rik ,i1 > 1, i.e. a risk-free currency exchange exists, thus proving our claim.
We can run Bellman-Ford to check for negative cycles reachable from s and therefore check for whether a risk-free currency exchange exists. This runs in O(|V ||E|) = O(n · m) time. The time to construct the graph was O(n2), so the total runtime is O(nm). The correctness and runtime of Bellman-Ford follow from lecture.
6. (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 Dijkstra’s algorithm. Can you check that T is correct in linear time?
To check that T is correct in linear time, we can use a modified version of the Bellman-Ford algorithm. First, calculate the distances according to T : run DFS on T , and on previsiting a vertex v from a previous vertex u, set dist[v] = dist[u]+weight(u, v). Then run Bellman-Ford starting with those distances, but instead of checking all the edges in the graph n − 1 times, we just check all the edges once. If any of the edges are updated, then we know that T is not the shortest path tree from s.
If T is not the tree of shortest paths from s, then there exists some vertex w such that the path to w is not the shortest. If an edge (v, w) ∈ G has dist(w) > dist(v) + weight(v, w) then we update the value at w to be the smaller distance. If we have an update, that tells us that one of the neighbors of w has a shorter distance to v, which means T did not have the shortest path.
If T is the tree of shortest paths from s, then there would not be any updates on those edges using our algorithm because there are no neighbors with a shorter distance to w.
Thus, the time complexity of this algorithm is linear because we are checking all the edges in G once and running DFS, i.e. the runtime is O(|E| + |V |).