CSE421-Homework 7 Solved

P1) Suppose we have received a large rectangular marble slab of size W × H and we want to cut the slab to obtain rectangular marble plates of sizes W1 × H1,W2 × H2,...,Wn × Hn. Any piece of marble (the slab or the plates cut from it) can be cut either horizontally or vertically into two rectangular plates with integral widths and heights, cutting completely through that piece. This is the only way to cut pieces and pieces cannot be joined together.

10     4
 
 
10     4
6    2
6    2
6    2
7    5
7    5
7    5
Since the marble has a pattern on it, the plates cannot be rotated: if a plate of size A × B is cut, then it cannot be used as a plate of size B × A unless A = B. We can make zero or more plates of each desired size. A marble plate is wasted if it is not of any of the desired sizes after all cuts are completed. The question is how to cut the initial slab so that as little of it as possible will be wasted.

As an example, assume that original slab is 21 × 11 and the desired plate sizes are 10 × 4,6 × 2,7 × 5, and 15 × 10. The minimum possible area wasted is 10, and the figure (below) shows one sequence of cuts with total waste area of size 10. Design an algorithm that runs in time polynomial in n,W,H that outputs the minimum possible waste area.

P2) Draw out a maximum s-t flow for the graph below, and the corresponding residual graph Gf. What is the minimum cut that corresponds to this max flow?

 

P3) Given a directed graph G such that each edge has capacity c(e). Suppose that we have assigned every node v a number r(v) if r(v) > 0 it means that v has a supply r(v) units of electricity

7-1

and if r(v) is negative it means v has a demand of −r(v) units of electricity. We want to see if it possibly to route the supply and satisfy all demand while we respect the capacity of every edge. Design an algorithm that runs in time polynomial in n and maxec(e) and outputs “yes” if we can satisfy all demands and “no” otherwise. For example, you should output yes for the left graph below and no for the right graph.

 

P4) Extra Credit: You are given an m × n array of real numbers. Suppose that the numbers in each row add up to an integer and the numbers in each column add up to an integer. You want to substitute each number A[i,j] with ⌊A[i,j]⌋ or ⌈A[i,j]⌉ such that the sum of the numbers in each row and each column remain invariant. Design a polynomial time algorithm that outputs the integer array.

For example, if the input is the left table you can output the right table. Note the sum of numbers in each row (and each column) of the left table is the same as the sum of the numbers of the same row (resp. the same column) in the right table.

0.4
0.1
1.5
⇒
1
0
1
0.6
1.9
0.5
0
2
1
7-2