Discussion 4
1. Hardy decides to start running to work in San Francisco city to get in shape. He prefers a route that goes entirely uphill and then entirely downhill so that he could work up a sweat uphill and get a nice, cool breeze at the end of his run as he runs faster downhill. He starts running from his home and ends at his workplace. To guide his run, he prints out a detailed map of the roads between home and work with k intersections and m road segments (any existing road between two intersections). The length of each road segment and the elevations at every intersection are given. Assuming that every road segment is either fully uphill or fully downhill, give an efficient algorithm to find the shortest path (route) that meets Hardy’s specifications. If no such path meets Hardy’s specifications, your algorithm should determine this. Justify your answer.
2. You are given a graph representing the several career paths available in industry. Each node represents a position and there is an edge from node v to node u if and only if v is a prerequisite for u. Top positions are the ones which are not prerequisites for any positions. The cost of an edge (v, u) is the effort required to go from one position v to position u. Ivan wants to start a career and achieve a top position with minimum effort. Using the given graph can you provide an algorithm with the same run time complexity as Dijkstra¡¯s? You may assume the graph is a DAG.
3. You have a stack data type, and you need to implement a FIFO queue. The stack has the usual POP and PUSH operations, and the cost of each operation is 1. The FIFO has two operations: ENQUEUE and DEQUEUE. We can implement a FIFO queue using two stacks. What is the amortized cost of ENQUEUE and DEQUEUE operations.
4. Given a sequence of numbers: 3, 5, 2, 8, 1, 5, 2, 7
a. Draw a binomial heap by inserting the above numbers reading them from left to right
b. Show a heap that would be the result after the call to deleteMin() on this heap
5. (a): Suppose we are given an instance of the Minimum Spanning Tree problem on a graph G. Assume that all edges costs are distinct. Let T be a minimum spanning tree for this instance. Now suppose that we replace each edge cost ce by its square, ce2 thereby creating a new instance of the problem with the same graph but different costs. Prove or disprove: T is still a MST for this new instance.
(b): Consider an undirected graph G = (V, E) with distinct nonnegative edge weights we¡Ý0. Suppose that you have computed a minimum spanning tree of G. Now suppose each edge weight is increased by 1: the new weights are c¡¯e = ce + 1. Does the minimum spanning tree change? Give an example where it changes or prove it cannot change.