CSC 477/677 Assignment 5
Fall 2004
Due April 22, 2004
-
Use dynamic programming to solve the single source minimum path problem
for this weighted acyclic directed graph,
where the source is the vertex labeled V0.
(If anyone now has trouble viewing this graph, please send email
immediately.)
Try this version if you can't view the other.
-
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.)
-
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
251 = 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.
-
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.
![](../../bluhorsa.gif)
Back to
Course Page