NAME:
PRECEPT #:
Final Exam 
May 15, 2002
Computer Science 226

This test is 15 questions, weighted as specified, for a total of 100 points.
Do all of your work on these pages (use the back for
scratch space), giving the answer in the space provided. Put your name and login
on the test (now), and write out and sign the Honor Code
pledge before turning in the test. You have three hours to complete
the test.
``I pledge my honor that I have not violated the Honor Code during
this examination.''
1. ____ 6. ____ 11. ____
2. ____ 7. ____ 12. ____
3. ____ 8. ____ 13. ____
4. ____ 9. ____ 14. ____
5. ____ 10. ____ 15. ____
SUB ____ SUB ____ SUB ____
TOTAL: ____
 (5 points)
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
 (5 points)
Draw the binary trie that represents the dictionary that is constructed by the
LZW algorithm for the string "aaabaabaaa".
 (5 points)
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)
 (4 points)
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
 (8 points)
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.

Answer the same question for BFS. Assume that duplicate nodes are not
put onto the BFS queue.
 (5 points)
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.
 (5 points)
Give the transitive closure of the graph in question 6.
TO
0 1 2 3 4


0  1

F 1  1
R 
O 2  1
M 
3  1

4  1
 (6 points)
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.
Asymptotic Time (days) Time (days)
Algorithm Running Time N = 16,000 N = 32,000

Alan O ( )
Beth O ( )
 (8 points)
Consider the undirected network below.
 Run Prim's algorithm starting at vertex 1
and list the order in which the vertices are examined.
 Give the cost of the MST.
 (8 points)
Consider the directed network below.
 Run Dijkstra's algorithm on the network above
and list the order in which the vertices are examined.
 Give the length of the shortest path from s to t and also write down
the path itself.
 (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.

List the vertices on the source side of a mincut in the network above.
Also, write the value of the mincut.

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.
 (8 points)
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.

Transform the problem to standard form,
i.e., nonnegative variables, equality constraints, and maximization.
 (5 points)
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
 (9 points)
Match up each algorithm with a data structure that is critical
for implementing it.
_____ BFS A. 2D tree
_____ DFS B. Adjacency matrix
_____ Floyd / Warshall C. Binary trie
_____ Kruskal D. Deque
_____ LZW E. Parentlink
_____ NFSA simulator F. Priority queue
_____ Network simplex G. Queue
_____ PFS H. Stack
_____ Range searching I. Unionfind
 (8 points)
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