CS6033 Homework Assignment 12
No late assignments accepted
1. Run Dijkstra’s algorithm on the directed graph below., Use vertex s as the source. Show the v.d and v.π values and the vertices in set S after each iteration of the while loop.
2. CLRS 22.3-4. Modify the DIJKSTRA procedure so that the priority queue Q is more like the queue in the BFS procedure in that it contains only vertices that have been reached from source s so far: Q ⊆ V − S and v ∈ Q implies v.d ̸= ∞.
3. CLRS 22.3-2. Give a simple example of a directed graph with negative-weight edges for which Dijkstra’s algorithm produces an incorrect answer. Why doesn’t the proof of Theorem 22.6 go through when negative-weight edges are allowed?
4. What is an optimal Huffman code for the following set of frequencies? a:3,b:6,c:8,d:2,e:5,f :9,g:13,h:12
5. Run the Floyd-Warshall algorithm on the graph below to compute D(3). (Of course, it would be more interesting to compute D(6), but that might be a bit too tedious to do by hand!)
6. Show how to use the output of the Floyd-Warshall algorithm to detect the presence of a negative-weight cycle.
7. Fourth edition CLRS 23.2-3. (Equivalent to third edition CLRS 25.2-3)
8. Fourth edition CLRS 23.2-4. (Equivalent to third edition CLRS 25.2-4)
9. (Do not turn in) In the activity selection problem, suppose that instead of always selecting the first activity to finish, you instead select the last activity to start that is compatible with all previously selected activities. Describe how this approach is a greedy algorithm, and prove that it yields an optimal solution.
10. (Do not turn in) After a horrifying road trip with your friend to California. You now need to return home. You vow to study hard in class (and thus get a job), so next time you visit California, you will be driving your own car (you were unaware your friend refused to drink coffee). After the horrifying experience on the trip down (you nearly crashed 42 times), you have revised your return plan. On your trip home, you refuse to travel more than 300 miles per day. You have the list of hotels from last time at mile markers m1,m2,...,mn. You wish to get home in as few days as possible.
Design an algorithm and provide the running time of your algorithm using big-Oh notation.
11. Turn in this question. (Question more appropriate for lecture 11) You and a friend are taking a class from professor E.Z. Ya. He has been assigned a long group homework assignment. It comprises a list of n problems (where n is an even number). Each problem qi has an ”easiness” factor associated with it. To make sure you don’t miss a problem, you decide to start solving the problems from either end (i.e., you start by solving q1 or qn. If you choose first to solve q1, then the next time, you could select q2 or qn. If you first chose qn then the next time you could select q1 or qn−1. Etc.) To finish quicker, you and your friend will simultaneously solve a problem. You get to choose the first problem (you) will solve. Your friend then decides which problem to solve. How do you ensure that you have done the minimum amount of work when you are done?
Determine a recursive solution to this problem. Design an efficient algorithm to solve this problem where you assume your friend will also be choosing to minimize his/her workload.
Show how your algorithm works on a small example.
