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

1. 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.

2. 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.

```
.
/ \
.   .
/   /
.
/ \
.
/

```

3. 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. 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.

2. guaranteed N log N always

3. guaranteed linear always

4. for any point set, some ordering of the points leads to linear time

5. 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.

5. Consider the graph on five nodes, labeled 0 through 4, with the 7 undirected edges
```   0-1 0-2 0-3 1-2 1-3 2-3 3-4
```

1. 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.

```
0-3 3-0 3-1 1-0 1-3 1-2 2-0 2-1 2-3 3-2 3-4
```

2. 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.

```
0-1 0-2 0-3 1-0 1-2 1-3 2-0 2-1 2-3 3-0 3-1 3-2 3-4
```

6. Consider the digraph on five nodes, labeled 0 through 4, with six directed edges
```0-1 1-4 4-0 0-2 2-3 3-2
```
List the strongly connected components of this digraph.

{0, 1, 4} {2, 3}

7. 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
```

8. 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
```

9. Consider the undirected network below.

1. 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

2. Give the cost of the MST.

6 + 8 + 7 + 1 + 3 + 2 + 9 = 36

10. Consider the directed network below.

1. 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

2. Give the length of the shortest path from s to t and also write down the path itself.

26

s-3-4-7-6-5-t

11. (12 points) Consider the boxed flow of value 24 in the maxflow network below.

1. Perform one iteration of the Ford-Fulkerson augmenting path algorithm. Write the augmenting path below and the value of the resulting flow.

either s-2-5-6-t or s-2-5-6-7-t

2. 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}

3. Suppose that the capacity of the arc 4-7 is decreased from 6 to 5. Without re-solving 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

12. 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
```

1. 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
```

2. 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
```

13. Circle each statement about reduction below that is not known to be true.

1. Assignment reduces to Mincost Maxflow

2. Longest path reduces to Shortest Path with Nonnegative Weights

3. Maxflow reduces to Mincut

4. Mincut reduces to Maxflow

5. Maxflow reduces to Linear Programming

b, c

14. Match up each algorithm with a data structure that is critical for implementing it.
```
G  BFS                    A.  2D tree

B  Floyd / Warshall       C.  Binary trie

I  Kruskal                D.  Deque

D  NFSA simulator         F.  Priority queue

E  Network simplex        G.  Queue

F  PFS                    H.  Stack

A  Range searching        I.  Union-find
```

15. This question is in regard to your part-time 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.

1. An FSA-based search engine interface that allows users to specify a richer set of patterns than does "grep"

2. A linear-time maxflow algorithm

3. An algorithm that compresses any given file by ten percent

4. A linear-time 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)

5. A linear-time algorithm for finding the MST of a graph with positive edge weights

6. A linear-time algorithm for sorting a set of numbers that can only compare two numbers (not know their values)

7. An algorithm that finds the longest path connecting two vertices in a network with positive edge weights

8. An algorithm that finds the shortest path connecting two vertices in a network with positive edge weights

a, c, d, f, g