Assigned 7 Apr, due 3 May
Note: will not be accepted late!
Problems from the Levitin textbook
Do problem 5.2.3 in the textbook (note that the
graph is undirected).
Do problem 5.2.6 in the textbook (note that the
graph is directed).
Do problem 5.6.10 in the textbook (sorting a
stack of pancakes by flipping substacks).
Do problem 6.1.6 in the textbook (you'll need
the formula on p. 126 for the number of comparisons in a merge sort).
Do problem 6.4.2 in the textbook (checking
whether a given array, when viewed as a binary tree, is a heap).
Do problem 6.5.10 in the textbook. By
"discuss which is more convenient," I mean
- for each of the two representations, give a pseudocode algorithm
to solve the problem;
- for each of the two representations, analyze your pseudocode
- tell which representation makes the problem easier.
Do problems 7.2.1, 7.2.2, and 7.2.3 in the textbook
(Horspool string matching).
Read problem 8.1.9 in the textbook, then do the
- Set up a recurrence relation
for P[i,j] that can be used to solve the problem.
- Write a working program that solves the
problem, recursively and top-down, using the recurrence
relation. The input to the program is the probability
p of Team A winning any given game,
and the number of games in the
series (you may assume this number is odd); the output is the
probability of Team A winning the series (i.e. winning a majority of
the games). Test and time
your program on a variety of series sizes and probabilities.
- Modify this program to use
"memo-ization" to avoid re-computing answers to common
sub-problems. Test and time the modified program on
the same test cases.
- Write pseudocode for a bottom-up,
dynamic-programming algorithm to solve the same problem.
- Implement this bottom-up algorithm in real code.
Test and time it as before.
- Compare the running times of the three versions
of the program.
A problem out of my head
You're a network administrator concerned about terrorist
attacks, either on computers in the network or on cables between
computers. You want to know whether
For each of these three questions,
- the network is currently connected, i.e. a message can get from
any computer to any other; and if so, whether
- there is a single computer which, if destroyed, would leave the
network no longer connected; or
- there is a single cable which, if cut, would leave the network
no longer connected.
- re-phrase it in graph terminology
- give a pseudocode algorithm for solving it
- analyze the running time of your algorithm
Wed Apr 6 11:38:26 EDT 2005
Stephen Bloch / email@example.com