Discussion 04

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.

   Answer:

   To determine which paths are valid, perform a breadth-first search beginning from his home, expanding outward on every road with an incline. Next, perform a breadth-first search beginning from his workplace, expanding outward on every road with a decline. Take the union of the sets of intersections that are in both searches. If the union is empty, then no path meets the specifications. Otherwise, the path is valid. Next, to find the shortest path, perform Dijkstra's algorithm on the set of intersections in the union, both from home and from work. The shortest path is the one with the lowest combined distance.

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.

   Answer:

   The runtime complexity of Dijkstra's algorithm is $O(|E|+|V|\log{|V|})$ when using a Fibonacci heap.

   Starting from each top position, perform Dijkstra's algorithm on the graph, and exit when we reach a node that is an entry-level position. Once we have finished running Dijkstra's algorithm on the last top position, return the shortest path encountered thus far.

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.

   Answer:

   The amortized cost of ENQUEUE is $O(1)$ and the amortized cost of DEQUEUE is $O(1)$.

4. Given the sequence of numbers:

   $3, 5, 2, 8, 1, 5, 2, 7$

   1. Draw a binomial heap by inserting the above numbers reading them from left to right

   2. Show a heap that would be the result after the call to deleteMin() on this heap

   Answer:

1.

1. 1. 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 $c_e$ by its square, $c_{e^2}$ 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.

   2. Consider an undirected graph $G = (V, E)$ with distinct nonnegative edge weights $w_e \geq 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 = c_e + 1$. Does the minimum spanning tree change? Give an example where it changes or prove it cannot change.

   Answer:

1. The minimum spaanning tree may change, such as in the case of the example below.

```
(A) -1- (B) -1- (C) -1- (D) -1- (E) -1- (F) -1- (G)
 |                       |                       |
 \ - - - - - - - 2- - - -+- - - - - - - -2- - - /
```

Docs just now