## 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