
The following table gives the KMP state transitions
for the string 1011011010, except for one
state transition, labeled X in the table. What should the value of X be?
0 1 2 3 4 5 6 7 8 9 10

0  0 2 0 2 5 0 2 8 0 10 10
1  1 1 3 4 1 6 7 1 9 X 10
X = 7.

Draw the binary trie that represents the dictionary that is constructed by the
LZW algorithm for the string "aaabaabaaa".
The dictionary consists of the strings
a, aa, aaa, aab, aaba,
b, and ba. Note that the prefix of every dictionary
entry is also in the dictionary.
In the figure below, left is a, right is b.
.
/ \
. .
/ /
.
/ \
.
/

Draw the subdivision of the plane that corresponds to inserting the
following points into an initially empty 2D tree, in the order given.
(1, 1) (2, 2) (3, 3) (4, 4) (5, 5) (6, 6) (7, 7)

Which one of the following statements is true regarding the
asymptotic running time of computing a 2D tree for a set of N points?
Circle your answer.
 guaranteed quadratic always
 guaranteed N log N always
 guaranteed linear always
 for any point set, some ordering of the points leads to linear time
 for any point set, no ordering of the points leads to better than N log N time
e
Inserting N nodes into a binary tree takes at least N lg N time, even if the tree
is balanced.

Consider the graph on five nodes, labeled 0 through 4,
with the 7 undirected edges
01 02 03 12 13 23 34

How many of the 14 edges (each listed edge and its reverse) does a
DFS examine in the worst case to find a path from 0 to 4?
The graph is represented using a standard adjacency list, but
the edges are inserted in arbitrary order rather than the order
listed above.
11
DFS can consider the edges in the following order.
03 30 31 10 13 12 20 21 23 32 34

Answer the same question for BFS. Assume that duplicate nodes are not
put onto the BFS queue.
13
BFS can consider the edges in the following order.
01 02 03 10 12 13 20 21 23 30 31 32 34

Consider the digraph on five nodes, labeled 0 through 4, with six
directed edges
01 14 40 02 23 32
List the strongly connected components of this digraph.
{0, 1, 4} {2, 3}

Give the transitive closure of the graph in question 6.
TO
0 1 2 3 4

0  1 1 1 1 1
F 1  1 1 1 1 1
R 2  1 1
O 3  1 1
M 4  1 1 1 1 1

Alan has discovered an amazing new algorithm for the mincost maxflow
problem. Alan has done some preliminary computational experiments that appear
to indicate the potential utility of the new algorithm, in particular
it appears much faster than Beth's classic algorithm.
running time (seconds)
N Alan Beth

5 0.00 0.01
10 0.00 0.05
20 0.01 0.16
40 0.05 0.63
80 0.41 2.51
160 3.27 10.20
Estimate the asymptotic running time of the algorithms
as a function of N. Predict how long (in days) that each of the two algorithms
will take to solve an instance of size N = 16,000 and N = 32,000.
Your estimates need not be calculated exact, but they should be within 10% of the
true answers. There are 86,400 seconds in a day.
Asymptotic Time (days) Time (days)
Algorithm Running Time N = 16,000 N = 32,000

Alan O(N^3) 38 303
Beth O(N^2) 1.2 4.7

Consider the undirected network below.
 Run Prim's algorithm starting at vertex 1
and list the order in which the vertices are examined.
1 2 4 7 6 8 5 3
 Give the cost of the MST.
6 + 8 + 7 + 1 + 3 + 2 + 9 = 36

Consider the directed network below.
 Run Dijkstra's algorithm on the network above
and list the order in which the vertices are examined.
s 3 4 7 6 2 5 t
 Give the length of the shortest path from s to t and also write down
the path itself.
26
s34765t
 (12 points)
Consider the boxed flow of value 24 in the maxflow network below.

Perform one iteration of the FordFulkerson augmenting path algorithm.
Write the augmenting path below and the value of the resulting flow.
either s256t or s2567t

List the vertices on the source side of a mincut in the network above.
Also, write the value of the mincut.
25
{s, 2, 4, 5}

Suppose that the capacity of the arc 47 is decreased from 6 to 5.
Without resolving the resulting maxflow problem, argue concisely (10 words
or less), but rigorously, why the maxflow value must decrease.
maxflow = mincut <= capacity cut {s, 2, 4, 5} = 24

You are the investment manager for a small company. You can purchase three
types of assets, each of which costs $100,000 per unit.
Assets can be purchased in whole or fractional units.
The assets produce income 5, 10, and 20 years from now, and that income is
needed to cover minimum cash flow requirements in those years.
Your goal is to minimize the cost of the assets purchased.
Note: cash from a previous year cannot be carried over to meet the cash
flow requirement for a subsequent year.
Year Asset 1 Asset 2 Asset 3 Cash flow required

5 200 100 50 4000
10 50 50 100 1000
20 0 150 200 3000

Formulate the problem as a linear programming problem.
min 100000 x1 + 100000 x2 + 100000 x3
s.t 200 x1 + 100 x2 + 50 x3 >= 4000
50 x1 + 50 x2 + 100 x3 >= 1000
150 x2 + 200 x3 >= 3000
x1 , x2 , x3 >= 0

Transform the problem to standard form,
i.e., nonnegative variables, equality constraints, and maximization.
max 100000 x1  100000 x2  100000 x3
s.t 200 x1 + 100 x2 + 50 x3  s1 = 4000
50 x1 + 50 x2 + 100 x3  s2 = 1000
150 x2 + 200 x3  s3 = 3000
x1 , x2 , x3 , s1 , s2 , s3 >= 0

Circle each statement about reduction
below that is not known to be true.
 Assignment reduces to Mincost Maxflow
 Longest path reduces to Shortest Path with Nonnegative Weights
 Maxflow reduces to Mincut
 Mincut reduces to Maxflow
 Maxflow reduces to Linear Programming
b, c

Match up each algorithm with a data structure that is critical
for implementing it.
G BFS A. 2D tree
H DFS B. Adjacency matrix
B Floyd / Warshall C. Binary trie
I Kruskal D. Deque
C LZW E. Parentlink
D NFSA simulator F. Priority queue
E Network simplex G. Queue
F PFS H. Stack
A Range searching I. Unionfind

This question is in regard to your parttime job working for a
software technology company. Your boss (having been told by you on
the basis on your 126 knowledge that the company had better not bet
its future on developing an application that finds an optimal tour
connecting a set of cities) is still looking for a
challenging project for you. Your boss is willing to invest in
things that might be difficult, but not things that we know to be
impossible or that we believe to be intractable. On the basis of your
226 knowledge, which of the following ideas can you tell your boss
to forget about? Circle all that apply.

An FSAbased search engine interface that allows users to
specify a richer set of patterns than does "grep"
 A lineartime maxflow algorithm
 An algorithm that compresses any given file by ten percent
 A lineartime algorithm for finding the MST of a set of
points in the plane that can only compare the distances
between two points (not know their coordinate values)
 A lineartime algorithm for finding the MST of a graph
with positive edge weights
 A lineartime algorithm for sorting a set of numbers
that can only compare two numbers (not know their values)
 An algorithm that finds the longest path connecting
two vertices in a network with positive edge weights
 An algorithm that finds the shortest path connecting
two vertices in a network with positive edge weights
a, c, d, f, g