Homework 5 - DFS

Practice problems (don't turn in):
1. Problem 3.3 from [DPV] (Implementing topological sorting algorithm)
2. Problem 3.4 from [DPV] (Implementing SCC algorithm)
3. Min-Heap (or priority queue):
   Starting from an empty min-Heap, perform the following sequence of operations, and
   draw the final Min-Heap data structure.
   • Insert a;7 (i.e., insert element a with key 7).
   • Insert b;4.
   • Insert c;9.
   • Insert d;12.
   • Insert e;10.
   • Insert f;3.
   • Decrease-Key of e to 2.
   • Delete-Min

Homework problems (turn in):
1. Problem 3.8 from [DPV] Pouring water
2. Problem 3.15 from [DPV] Computopia (2 points)
3. Running (2 points):
   To get in shape, you have decided to start running to work.
   You want a route that goes entirely uphill and then entirely downhill,
   so that you can work up a sweat going uphill and then get a nice breeze
   at the end of your run as you run faster downhill.
   Your run will start at home and end at work and you are given as input
   a map detailing the roads with n intersections and m one-way road segments,
   each road segment is marked uphill or downhill. You can assume home is
   intersection 1 and work is intersection n, and the input is given by two sets:
   E_U representing the uphill edges and E_D representing the downhill edges,
   where each set is given in adjacency list representation.
   
   Give an algorithm that determines if there is a route (regardless of the length)
   which starts at home, only goes uphill, and then only goes downhill, and finishes at work.
   
   You should give a clear description of your algorithm in words, and you should explain its running time.
   Faster (in O() notation) and correct is worth more credit.
   
   Here is an example with 5 vertices, where vertex 1 is home and vertex 5 is work.
   The input are the following arrays of linked lists:
         E_U = 1→2; 3→4 ; 3→5.
         E_D = 1→3; 2→3; 2→4; 4→5.
   There is one uphill-downhill way to go from 1 to 5: 1→2→4→5.