Pleas
Please answer all questions
2. (15 points) News from Cambridge, for those of you far away: every night, snow falls and covers all the sidewalks. Every morning, the city's 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 doesn't 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. (15 points) The risk-free currency erchange problem offers a risk-free way to make money. Suppose we have currencies c),..., G. (For example, cu might be dollars, ca rubles, c3 yen, etc.) For various pairs of distinct currencies G and cj (but not necessarily every pair!) there is an exchange rate Tij such that you can exchange one unit of c; for rij units of cj. (Note that even if there is an exchange rate Tij, 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 Tj;i:) Now if, because of exchange rate strangeness, Tij Tjji > 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 Ci, Ciz..., Cie such that l'iniz l'izis ... Tik-1,RTiki > 1, then trading one unit of G into Giz and trading that into Ciz and so on back to G, will yield a profit. Design an efficient algorithm to detect if a risk-free currency exchange exists. (You need not actually find it.) 4. (20 points) Give an algorithm to find the lengths of all shortest paths from a given vertex in a directed graph G = (V, E) where all edge weights are integers between 0 and m, inclusive. Your algorithm should work in time 0(E[ + ]V|m). (Hint: Modify Dijkstra's algorithm.) 5. (15 points) Design an efficient algorithm to find the longest path in a directed acyclic graph whose edges have real-number weights. (Partial credit will be given for a solution where each edge has weight 1; full credit for solutions that handle general real-valued weights on the edges, including negative values.) 2. (15 points) News from Cambridge, for those of you far away: every night, snow falls and covers all the sidewalks. Every morning, the city's 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 doesn't 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. (15 points) The risk-free currency erchange problem offers a risk-free way to make money. Suppose we have currencies c),..., G. (For example, cu might be dollars, ca rubles, c3 yen, etc.) For various pairs of distinct currencies G and cj (but not necessarily every pair!) there is an exchange rate Tij such that you can exchange one unit of c; for rij units of cj. (Note that even if there is an exchange rate Tij, 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 Tj;i:) Now if, because of exchange rate strangeness, Tij Tjji > 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 Ci, Ciz..., Cie such that l'iniz l'izis ... Tik-1,RTiki > 1, then trading one unit of G into Giz and trading that into Ciz and so on back to G, will yield a profit. Design an efficient algorithm to detect if a risk-free currency exchange exists. (You need not actually find it.) 4. (20 points) Give an algorithm to find the lengths of all shortest paths from a given vertex in a directed graph G = (V, E) where all edge weights are integers between 0 and m, inclusive. Your algorithm should work in time 0(E[ + ]V|m). (Hint: Modify Dijkstra's algorithm.) 5. (15 points) Design an efficient algorithm to find the longest path in a directed acyclic graph whose edges have real-number weights. (Partial credit will be given for a solution where each edge has weight 1; full credit for solutions that handle general real-valued weights on the edges, including negative values.)
