Description
1. In the flow network shown below, the number beside an edge denotes its corresponding capacity. Apply
the Edmonds-Karp algorithm to find a maximum flow from s to t in the network. Show every
augmentation path (but you do NOT need to show the whole network to save time) and
explain why the flow you found is maximum.
s
a
b
c
t
e
d 3
2
6
1
3
4
2
5
4
5
6
2
3
2. Problem 26-1 (pages 760–761).
3. Problem 26-3 (pages 761–762).
4. A realtor would like to maximize the number of apartments sold. She has p apartments to sell and q
potential customers for these apartments. She has m salesmen working for her. Each salesman is assigned
a list of apartments and clients interested in these apartments. A salesman can sell an apartment to
any of his customers. Salesman i can sell at most bi apartments. Also, any apartment cannot be owned
by more than one person. For m = 2, p = 4, q = 5, b1 = 3, b2 = 1, and the following assignments of
customers and apartments to the salesmen, construct the flow network for the underlying problem. How
to find the maximum number of apartments that can be sold? (Hint: How can you constrain that
salesman i can sell at most bi apartments in this flow network?)
Salesman Customers Apartments
1 1, 2, 3, 4 1, 2, 3
2 3, 4, 5 3, 4
5. The figure below shows a segmented routing structure in a row-based field-programmable gate array
(FPGA). There are five connections, c1, c2, . . . , c5, to be routed on three segmented tracks, t1, t2, and
t3, with eight segments s11, s12, . . . , s32 in the row-based FPGA. A track can be partitioned into a set
of segments by using switches. If a switch incident on two adjacent segments is “ON”, then the two
segments are electrically connected; otherwise, the two segments can be used independently. You are
asked to route (place) the five connections on the three segmented tracks. Suppose each connection can
use at most one segment for routing, i.e., 1-segment routing. In other words, a connection ck of the
column span [lk, rk] is said to be routed on a segment sij of track ti
if ck = [lk, rk] is placed within the
column span of sij . For example, c3 = [2, 5] can be routed on segment s31 of track t3 (which consumes
only one segment) while it cannot route on track t1 or t2 (which would have consumed two segments,
thus violating the constraint of 1-segment routing). Give an efficient algorithm to solve the 1-segment
routing problem. What is the time complexity of your algorithm?
Problem 7. (10 pts total) The figure below shows a segmented routing structure in a row-based
field-programmable gate array (FPGA). There are five connections, c1, c2, . . . , c5, to be routed on
three segmented tracks, t1, t2, and t3, with eight segments s11, s12, . . . , s32 in the row-based FPGA. A
track can be partitioned into a set of segments by using switches. If a switch incident on two adjacent
segments is “ON”, then the two segments are electrically connected; otherwise, the two segments can
be used independently. You are asked to route (place) the five connections on the three segmented
tracks. Suppose each connection can use at most one segment for routing, i.e., 1-segment routing.
In other words, a connection ck of the column span [lk, rk] is said to be routed on a segment sij of
track ti if ck = [lk, rk] is placed within the column span of sij . For example, c3 = [2, 5] can be routed
on segment s31 of track t3 (which consumes only one segment) while it cannot route on track t1 or t2
(which would have consumed two segments, thus violating the constraint of 1-segment routing). Give
an efficient algorithm to solve the 1-segment routing problem. (Hint: Think about the resource
assignment between key components.)
Problem 8. (bonus) (This problem can be answered by email by 1pm January 14 after
the final exam.) Please list the corrections to the class notes and lectures you made in this semester,
if any. Please give specific information on the corrections, e.g., page numbers of the class notes, if
possible.
5
6. Concepts on polynomial-time complexity. (a) Exercise 34.1-4 (page 1060). (b) Professor Right finds a
fast algorithm for the maximum flow problem on the network G = (V, E) with the capacity c(u, v) for
the edge (u, v), which runs in O(V E(lg C)
2
) time, where C = max(u,v)∈E c(u, v). Is it a polynomial-time
algorithm? Justify your claim.
7. Exercise 34.4-7 (page 1086).
8. Problem 34-1 (pages 1101–1102).
9. Problem 34-3 (pages 1103–1104).
10. (a) Exercise 17.1-3 (page 456). (b) Exercise 17.2-2 (page 459). (c) Exercise 17.3-2 (page 462).
11. Exercise 17.4-3 (page 471).
12. Problem 17-3 (pages 473–474).
13. (DIY Problem) For this problem, you are asked to design a problem set related to Chapter(s) 17, 26,
and/or 34, and give a sample solution to your problem set. Grading on this problem will be based upon
the quality of the designed problem as well as the correctness of your sample solution.
2
