The University of Texas at Austin CS331

Department of Computer Science

Professor Vijaya Ramachandran

TEST 2 Sample

This test has problems worth a total of 22 points.

Scores will be capped at value v that is at most 20. In other words, any score above v will
be reset to v, and this will be the maximum score possible for the test. All scores below v
will remain unchanged.

• Write your answers in the spaces provided. You may use the facing page or the back
of the sheet if you need extra space.

• Answer as many problems as you can, and on an initial scan, skip over the ones you
find difficult. You can come back to the difficult problems after you have completed
the other problems.

• Please be clear and rigorous in your answers.

In your solutions, you can use results seen in class and in your homework
without reproducing their derivation, unless stated otherwise.
However, please be sure to state clearly any such result you use.
(Simply stating ‘as seen in class’ will not suffice.)

• You are allowed to use one two-sided sheet of your personal notes, but no other ma-
terial.

• Please put away all electronic devices, including cell-phones. Silence your devices.

Please display your UT id card next to you on the desk.

GOOD LUCK

−oooooo−

I declare that I have not taken or received help during this test.

SIGNATURE

NAME

UTEID

1
1. [7 POINTS] A bricklayer has a sequence of n bricks B1 , B2 , · · · , Bn , where the i-th
brick, Bi , has length li . He needs to choose bricks from this sequence of bricks to place
along a wall of length L.
The bricklayer will place the chosen bricks next to each other in the same order as they
occur in the original sequence, without gaps and without exceeding the length of the wall.
The bricks cannot be broken.
The optimization problem here is to find a sequence of bricks from the input sequence whose
lengths sum up to the maximum value that does not exceed L.

(a) (3 pts) State and prove an optimal substructure property for this problem.
Your answer must be self-contained, and should not refer to results from class or the PS.

2
(b) (2 pts) Give a recursive formulation (including base case) for the value of an optimal
solution to the bricklayer input, using your answer to part (a). No correctness proof needed.

(c) (2 pts) Give a dynamic programming algorithm to compute the value of an optimal
solution. Be sure to include initialization. Make your algorithm as efficient as you can. No
proof of correctness is needed.

3
2. [3 POINTS] Consider the following algorithm based on the Bellman-Ford algorithm.

BF+n(G = (V, E), w, s)

Input. Graph G = (V, E), weights w(e) on edges e ∈ E, source s ∈ V . All vertices are
reachable from source s
Output. δ(s, v) for all v ∈ V in the d array.
1. Initialize. d[s] ← 0; for each v ∈ V − {s} do d[v] ← ∞
2. for n − 1 iterations do
for each (u, v) ∈ E do d[v] ← min{d[v], d[u] + w(u, v)} ( Relax(u, v) )
3. for v ∈ V do d1 (v) ← d[v]
4. for n iterations do
for each (u, v) ∈ E do d[v] ← min{d[v], d[u] + w(u, v)} ( Relax(u, v) )
5. for v ∈ V do d2 (v) ← d[v]

The algorithm BF+n runs the Bellman-Ford algorithm in Steps 1-2 and copies the d-values
into d1 [1..n] in Step 3. In Step 4 it runs the computation in Step 2 for n additional iterations,
and then copies the d-values at the end of Step 4 into d2 [1..n] in Step 5.

(a) (2 pts) Give a method to determine whether or not G has a negative weight cycle by
examining the entries in d1 and d2 .

(b) (1 pt) Argue correctness of your method. You can use results seen in class and the PS
without reproving them.

4
3. [4 POINTS] Consider the Union-Find data structure that we saw in class using Union
by size. In this problem we will use the Union operation instead of the Link operation.
We proved in class that if there are n elements in the data structure then any Find-set or
Union operation will run in O(log n) time, and a Make-set runs in constant time.
In this problem you will show that this bound on Find-set is tight as follows.
Let n = 2k , for some positive integer k. You need to construct a sequence of 2n Union-Find
operations as follows:
The first n operations are Make-set(xi ), 1 ≤ i ≤ n, where the xi are all distinct elements.

(a) (3 pts) Give a sequence of n − 1 Union operations, followed by one Find-set operation
such that the final Find-set operation takes Ω(log n) time to execute.
This sequence will execute after the first n Make-set operations listed above.

(b) (1 pt) Briefly argue why the final Find-set operation takes Ω(log n) time.

5
4. [5 POINTS] Recall the algorithm we saw in class for maximum bipartite matching
which solved the problem by phrasing it as a maximum integer flow problem.
You need to run this algorithm on the bipartite graph G given below along with its associated
flow network N :

In the following 3 parts, you need to give (a) a maximum matching in G, (b) a maximum
flow in N , and (c) the residual graph of the maximum flow given in part (b).

(a) (1 pt) List the edges in a maximum matching in G.

(b) (1 pt) Draw N with a flow f in it corresponding to the maximum matching in G that
you listed in part (a).

6
(c) (2 pts) Draw the residual graph Nf of N with respect to the flow f you gave in part
(b).

(d) (1 pt) List the edges in the minimum cut in N you obtain from Nf .

7
5. [3 POINTS] Give a linear programming (LP) formulation of the maximum flow problem
whose input is a flow network G = (V, E, s, t, c) with |V | = n, |E| = m. You can assume
that the vertices are numbered from 1 to n (with s = 1 and t = n), so V = {1, 2, · · · n}, and
that, if (i, j) ∈ E then cij is the capacity of edge (i, j).

Recall that the general form an LP is as follows:

Pn
maximize (or minimize) j=1 cj · xj subject to:

• p ≥ 0 inequality constraints:
Pn
j=1 aij · xj ≤ bi , 1 ≤ i ≤ p

• q ≥ 0 equality constraints:
Pn 0
j=1 aij · xj = b0i , 1 ≤ i ≤ q

• non-negativity constraints: xj ≥ 0, for some indices j ∈ {1, 2, · · · , n}.

The only variables are the xj , 1 ≤ j ≤ n. All cj , aij , a0ij , bi and b0i are constants values
provided in the input.

8
9