CSC 477/677 Assignment 5

Fall 2004

Due April 22, 2004

1. Use dynamic programming to solve the single source minimum path problem for this weighted acyclic directed graph, where the source is the vertex labeled V₀.
   
   (If anyone now has trouble viewing this graph, please send email immediately.)
   
   Try this version if you can't view the other.


2. Use Kruskal's algorithm to find a minimal spanning tree for this weighted graph, showing steps. Then, use Prim's algorithm to do the same thing, using the same weighted graph, again showing steps. (You are to walk through the algorithms by hand, rather than writing a computer program.)
   


3. There are 50 states in the United States, each of which has a certain number of electoral votes, which means that at the next Presidential election this coming November 2, each state will select that number of Electors, who together form the Electoral College. (You can consult the web to discover how many Electors each state will choose. Nevada will choose 5.) In addition, the District of Columbia will choose 3 Electors.
   
   The Electors will meet in their state capitals on December 13, and vote for Presidential candidates. If any candidate receives a majority of the electoral votes, that candidate will become President on January 20, 2005.
   
   Assume that in each state and in the District of Columbia, all the Electors from that state vote for either the Democrat or the Republican nominee. There are thus 2⁵¹ = 2,251,799,813,685,248 possible outcomes of the election. (Actually, There is there are two states where the Electors from that state might be split, but just pretend that isn't true.)
   
   The total number of Electors will be 538. Write (in pseudocode) a dynamic programming algorithm which counts how many of these outcomes result in an Electoral College tie, i.e., where each candidate gets exactly 269 Electoral votes. (I would be interested in knowing the exact number if anyone wants to actually write the program, but although I am very interested, I will not give extra credit for this.) The input data to your algorithm will be an array of length 51, showing the list of the numbers of the Electors from each state and the District of Columbia.
4. Describe how you would use dynamic programming to design an optimal strategy for playing tic-tac-toe.
   
   You should describe the directed acyclic graph of subproblems (it might be too large to draw entirely, but at least describe it in words and show a few example vertices and edges) and explain how that graph is used to solve the problem.
   
   If you have never heard of the game tic-tac-toe, ask someone. It takes about 10 seconds to learn how to play it, so I will not accept ignorance as an excuse.