ANLY550 Homework 2 Out: Feb. 2, 2017 Due: Feb. 16, 2017
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. 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. As always, try to make your answers as clear and concise as possible.
1. Recall that when running depth first search on a directed graph, we classified edges into 4 categories: tree edges, forward edges, back edges, and cross edges refer to Mitzenmachers lecture notes at http: people.cs.georgetown.edujthalerANLY550lec3.pdf for the definitions.
Prove that if a graph G is undirected, then any depth first search of G will never encounter a cross edge.
2. Explain how to solve the following two problems using heaps. No credit if youre not using heaps! First, give an Onlogk algorithm to merge k sorted lists with n total elements into one sorted list. Second, say that a list of numbers is kclose to sorted if each number in the list is less than k positions from its actual place in the sorted order. Hence, a list that is 1close to sorted is actually sorted. Give an Onlogk algorithm for sorting a list of n numbers that is kclose to sorted.
3. Design an efficient algorithm to find the longest path in a directed acyclic graph. Partial credit will be given for a solution where each edge has weight 1; full credit for solutions that handle general realvalued weights on the edges, including negative values.
4. GileshasaskedBuffytooptimizeherprocedurefornighttimepatrolofSunnydale.Thistakesplacesometime in Season 2. Giles points out that proper slaying technique would allow Buffy to traverse all of the streets of Sunnydale in such a way that she would walk on each side of each block, exactly once. Buffy now has slayer homework: how can it be done? If you have to assume anything about the layout of the city of Sunnydale, make it clear!
5. In the shortestpath algorithm we are concerned with the total length of the path between a source and every other node. Suppose instead that we are concerned with the length of the longest edge between the source and every node. That is, the bottleneck of a path is defined to be the length of the longest edge in the path. Design an efficient algorithm to solve the single source smallest bottleneck problem; i.e. find the paths from a source to every other node such that each path has the smallest possible bottleneck.
6. Considertheshortestpathsprobleminthespecialcasewherealledgecostsarenonnegativeintegers.Describe a modification of Dijkstras algorithm that works in time OEVM, where M is the maximum cost of any edge in the graph.
7. The riskfree currency exchange problem offers a riskfree way to make money. Suppose we have currencies c1,…,cn. For example, c1 might be dollars, c2 rubles, c3 yen, etc. For every two currencies ci and cj there is an exchange rate ri, j such that you can exchange one unit of ci for ri, j units of c j . Note that if ri, j r j,i 1, then you can make money simply by trading units of currency i into units of currency j and back again. 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 riskfree money. That is,ifthereisasequenceofcurrenciesci1,ci2,…,cik suchthatri1,i2 ri2,i3 …rik1,ik rik,i1 1,thentradingone unitofci1 intoci2 andtradingthatintoci3 andsoonwillyieldaprofit.
Design an efficient algorithm to detect if a riskfree currency exchange exists. You need not actually find it. 1