Home
Syllabus
Classwork
printable version
Section A8:
[1]
[2]
[3]
[4]
Section A10:
[1]
[2]
Section A13:
[1]
Section A15:
[1]
[2]
Section A17:
[1]
[2]
Section A20:
[1]
[2]
[3]
Section A27:
[1]
[2]
For the below linear program, draw each constraint and shade in the polytope of feasible points. Circle the optimum point, labeling it with the point's coordinates.
| maximize | y | ||
| where | x | ≥ | 1 |
| y | ≥ | 2 | |
| x + y | ≤ | 6 | |
| y − x | ≤ | 3 |
The x ≥ 1 constraint is drawn in red, y ≥ 2 in blue, x + y ≤ 6 in yellow, y − x ≤ 3 in green.
Show how we can formulate a linear program to compute the maximum difference between any two numbers in an array of numbers <x0, x1, … xn − 1>. For example, given <5,7,11,3,2>, your linear program should find the solution 9, since the largest and smallest numbers in the array are 11 and 2, and their difference is 9.
We'll define two variables a and b. The variable a is intended to become the minimum within the array, while b is intended to become the maximum.
| minimize | b − a | |||
| where | a | ≤ | xi | for each index i between 0 and n − 1 |
| b | ≥ | xi | for each index i between 0 and n − 1 | |
Jared has decided that he will eat all his food at Subway. He can only stand to eat five items on their menu, however, and salad is just barely tolerable. So he wants to find a way of satisfying his dietary needs while eating as little salad as possible. To help with this, he visited their Web site and got the following dietary information.
| Cal | Fat | Sat | Pro | Na | Ca | VitA | |
| Cookie | 220 | 11.0 | 5.0 | 2 | 140 | 0 | 0 |
| Minestrone | 90 | 1.0 | 0.0 | 4 | 910 | 4 | 25 |
| Salad | 50 | 1.0 | 0.0 | 3 | 65 | 6 | 25 |
| Veggie Delite | 230 | 2.5 | 0.5 | 9 | 550 | 6 | 8 |
| Western Omelet | 460 | 19.0 | 7.0 | 27 | 1450 | 25 | 10 |
He wishes to eat at least 2,000 calories a day, of which no more than 20% should come from fat, nor 10% from saturated fat. Protein should account for at least 10% of calories. In the above able, fat, saturated fat, and protein are counted in grams; there are 9 calories per gram of fat, and 4 per gram of protein.
The diet should include at most 2,400 mg of sodium (the Na column in the table), at least 100 points of calcium (Ca), and at least 100 points of vitamin A.
Write a linear program that finds a diet for Jared using as little salad as possible.
| minimize | s | ||
| where | 220 c + 90 m + 50 s + 230 v + 460 w | = | cals |
| cals | ≥ | 2000 | |
| 11 c + 1 m + 1 s + 2.5 v + 19 w | ≤ | (0.2 / 9) cals | |
| 5 c + 0.5 v + 7 w | ≤ | (0.1 / 9) cals | |
| 2 c + 4 m + 3 s + 9 v + 27 w | ≥ | (0.1 / 4) cals | |
| 140 c + 910 m + 65 s + 550 v + 1450 w | ≤ | 2400 | |
| 4 m + 6 s + 6 v + 25 w | ≥ | 100 | |
| 5 m + 25 s + 8 v + 10 w | ≥ | 100 | |
| c | ≥ | 0 | |
| m | ≥ | 0 | |
| s | ≥ | 0 | |
| v | ≥ | 0 | |
| w | ≥ | 0 |
We operate a company specializing in cranberry sauce, made from cranberries purchased from three different suppliers.
Supplier 1 provides 200 tons at $11 / ton Supplier 2 provides 310 tons at $10 / ton Supplier 3 provides 420 tons at $9 / ton
We have two cranberry sauce factories. Factory A can use up to 460 tons of cranberries, and labor at the factory costs $26 per ton. Factory B can use up to 560 tons, and the labor cost is $21 per ton. The cost to ship cranberries from each supplier to a factory is as follows.
(in $ / ton) Factory A Factory B From Supplier 1 3 3.5 From Supplier 2 2 2.5 From Supplier 3 6 4
To provide a reasonably similar taste from each factory, we require that each supplier supply at least 20% of the cranberries to each factory.
We make $50 per ton of cranberries processed.
Write a linear program that finds the best way to distribute cranberries to our factories.
We define xi, j to be the amount of cranberries that are sent from supplier i to factory j. Also, we define a to represent the amount processed at Factory A and b the amount at Factory B.
| maximize | 50 (a + b) − 14 x1, A − 14.5 x1, B − 12 x2, A − 12.5 x2, B − 15 x3, A − 13 x3, B − 26 a − 21 b | |||||||||||||||||||||||||||||||||||||||||||||
| where |
| |||||||||||||||||||||||||||||||||||||||||||||
Suppose we're given an undirected graph represented by a set of vertices V and a set of edges E. Show how to write an integer program to solve the three-coloring problem for this graph — that is, to find a way to assign one of three colors to each vertex so that for every edge (u, v) in E, u and v have different colors assigned to them. For the sake of having an optimization function, try to find the coloring that assigns as few red vertices as possible.
We imagine rv to be a variable that is 1 if v is colored red, gv that is 1 if v is colored green, and bv that is 1 if v is colored blue.
| minimize | ∑v in V rv | |||
| where | ru + rv | ≤ | 1 | for each (u, v) in E |
| gu + gv | ≤ | 1 | for each (u, v) in E | |
| bu + bv | ≤ | 1 | for each (u, v) in E | |
| rv + gv + bv | = | 1 | for each v in V | |
| rv | in | {0, 1} | for each v in V | |
| gv | in | {0, 1} | for each v in V | |
| bv | in | {0, 1} | for each v in V |
Recall the VERTEX COVER problem, in which we want to select a set of vertices so that every edge has at least one endpoint contained in the set. We can write an integer program to solve this problem, using a variable pv for each vertex v, for which a value of 1 indicates that v is selected.
minimize ∑v in V pv where pu + pv ≥ 1 for each (u, v) in E pv in {0, 1} for each v in V
Suppose we were to relax this program by replacing the pv in {0, 1} integer constraint with two linear constraints pv ≥ 0 and pv ≤ 1. Explain how to use this fractional solution to arrive at a 2-approximation to the optimal integer solution, and justify why your approach works.
We will simply round each pv, rounding up whenever pv ≥ 0.5 and down when pv < 0.5. Doing this, each of the pu + pv ≥ 1 constraints will still be satisfied, since before the rounding a least one of pu or pv would have to be at least 0.5 for the sum to be at least 1. Thus, we still have a feasible solution to the problem.
This solution's value will be at most twice the optimal solution to the vertex-cover problem. After all, when we relax the integer program, we are expanding the polytope of valid solutions, and so the objective function ∑v in V pv will only decrease. Thus, the value of the objective function is a lower bound on the optimal value for the original problem. Rounding each pv from our linear program will do no more than double each value, so ∑v in V pv will be twice as much as it was before. Thus, we end up with something that is no more than twice the optimal solution to the vertex cover problem.
Suppose that in the graph at right, all edges are directed toward their eastward (rightmost) endpoint. The capacities of the edges are: 7 for each edge emanating from c, 8 for each edge emanating from b, and 9 for all other edges.
Apply the Ford-Fulkerson algorithm to compute the maximum flow from s to t. With each step, you should choose the maximum-capacity path from s to t, using shortest paths to break ties. Show which path is selected with each step and the capacity for that step, and give the final flow for the graph.
The first three steps are forced by the selection criterion listed above; on the fourth, there is a choice, which results in a different solution.
Assuming we are following what is labeled as the primary solution above, our final flow have 9 units flowing out of each edge from s. From a, 9 units flow into d. From b, 7 units flow into e and 2 into f. From c, 7 units flow into f and 2 into e. From d, e, and f, 9 units flow into t.
Professor F is teaching a class with group projects, where each he breaks the class into N groups for each project, each group having 5 students. Professor F assigned groups for the first project, and now he wishes to assign groups for the second project. Professor F wants to make sure that nobody works with the same person on both projects. (We know N is at least 5, since otherwise this task would be impossible.) How can he find such an assignment using maximum-flow?
There will be a vertex s, a first group of N vertices, a second group of N vertices, and another vertex t. An edge will be drawn from s to each vertex in the first group, each with capacity 5. And an edge will be drawn from each vertex in the second group to t, again with capacity 5. Finally, a capacity-1 edge will be drawn from each vertex in the first group to each vertex of the second group. For each edge that is saturated by the maximum flow, this indicates that somebody in the source-vertex group should be assigned to work in the destination-vertex group. in the destination-vertex group.
Suppose you are given the flow assignments on each edge that provides a maximum flow from s to t. How can you compute the s-t minimum cut — i.e., the least-weight set of edges so that their removal separates s from t? Your algorithm should take O(m) time.
Starting from s, perform a depth-first search, traversing only those edges whose flow is less than the edge capacity. This computes the set A of all vertices that are reachable from s using non-saturated edges, and it takes takes O(m) time to compute. Then go through all edges adjacent to a vertex in A, including in our output any such edge whose other endpoint is not in A. This again takes O(m) and outputs all edges in the minimum cut.
Distinguish between a parallel system and a distributed system.
Both involve multiple processors. However, in a parallel system we assume that communication between processors is very cheap, and is usually accomplished through shared access to the same memory; whereas in distributed systems, we assume the processors are somewhat separated, without any shared memory, and communication occurs through passing messages across a local network — quite a bit more expensive than accessing shared memory.
Describe how a parallel-processor system with p processors can compute the minimum element of an n-element array in O(n / p + log p) time. You may assume that each processor has an ID between 0 and p − 1.
Each processor uses its ID to compute its segment of the array, and it scans through that segment to find its minimum value. This takes O(n / p) time.
Now each processor whose ID is odd sends its minimum to the one before it, which sees which is the smaller of its segment's minimum and the other processor's minimum. That represents the minimum of both processors' segments. Since there is just one message being sent or received here by each processor, this takes O(1) time.
And then each processor whose ID is even but not a multiple of 4 sends its minimum to the multiple of 4 before it, and that processor sees which is the smaller of that number what what it thought was the minimum before. As a result, each processor with an ID that is a multiple of 4 will now know the smallest value in four processors' segments. Again, this step takes O(1) time.
We repeat the process, each time halving the number of
active
processors (that is, ones that received a message
in the last step and will continue working in the next step).
When there is just one active processor, we stop. There will be
⌈log2 p⌉
such rounds, each taking O(1) time,
so the combination of the segments' minima takes a total of
O(log p) time.
Suppose we're given an array of pairs (ai, bi), where a0 is 0, specifying a sequence of linear equations as follows:
| x0 | = | b0 |
| x1 | = | a1 x0 + b1 |
| x2 | = | a2 x1 + b2 |
| : | (and so forth) |
We want to compute xn − 1. We could do this easily enough on a single-processor system.
double x = 0.0; for(int i = 0; i < n; i++) x = a[i] * x + b[i];
But we have a many-processor parallel system and wish to compute the final answer more quickly. A natural approach is to try to adapt our parallel scan operation using an operator ⊗ as follows.
Applying this ⊗ operator left-to-right through the array, we see that we end up with the appropriate values for each x (recalling that a0 is defined to be 0).
| (0, b0) ⊗ (a1, b1) | = | (0, a1 b0 + b1) | = | (0, x1) |
| (0, x1) ⊗ (a2, b2) | = | (0, a2 x1 + b2) | = | (0, x2) |
| (0, x2) ⊗ (a3, b3) | = | (0, a3 x2 + b3) | = | (0, x3) | : |
Unfortunately, we can't apply the scan operator to this operator because it isn't associative.
Show a new definition of ⊗ — a slight modification of the above-shown one — which is associative and yields the correct value of xn − 1 when applied to our array.
Define ⊗ as
This operator is associative:
And it still computes the correct answer.
| (0, b0) ⊗ (a1, b1) | = | (a1 0, a1 b0 + b1) | = | (0, x1) |
| (0, x1) ⊗ (a2, b2) | = | (a2 0, a2 x1 + b2) | = | (0, x2) |
| (0, x2) ⊗ (a3, b3) | = | (a3 0, a3 x2 + b3) | = | (0, x3) | : |
Given an array <a0, a1, a2, … an − 1> and some associative operator ⊗, describe what the parallel prefix scan algorithm computes.
It computes the array:
| < | a0, | |
| a0 ⊗ a1, | ||
| a0 ⊗ a1 ⊗ a2, | ||
| …, | ||
| a0 ⊗ a1 ⊗ a2 ⊗ … ⊗ an − 1 | > |
Suppose we have an array of characters, and we want to know
whether the parentheses match — that is, we consider
(()())()
to match, but )(())()(
and (()))(()
.
Using
the parallel scan and parallel prefix scan operations,
show how to determine this in
O(n / p + log p)
on a p-processor system. (You will not need to define
a new ⊗ operator.)
Create a new array where we have 1 for each open-parenthesis and −1 for each close-parenthesis. We perform a parallel prefix scan on this array using addition as our operator. We confirm that the final entry in this parallel prefix scan (the sum of all entries) is 0; if it is not, then we reject the original string, since it doesn't have same number of open-parentheses as close-parentheses. But if the sum of all entries 0, we then compute the minimum of this parallel prefix scan using the parallel scan algorithm. If the minimum of all entries is 0, then we accept the string, since scanning through the string left-to-right we never encounter more close-parentheses than open-parentheses; but if the minimum is below 0, we reject the string.
We saw in class that we can merge two length-n arrays on p processors in O((n / p) log p) time. Using this algorithm, how long does it take to perform mergesort on a p-processor system? Justify your answer.
At the top level of the recursion tree, after applying mergesort to each half, we'll spend c((n / p) log p) time merging the two halves together, for some constant c.
At the second level of the recursion tree, each half of the array will include n / 2 entries, but only p / 2 processors will be available to sort each half (since both halves would be sorted simultaneously). After each half's halves are sorted, the amount of time taken to merge them will be c(((n / 2) / (p / 2)) log (p / 2)) = c((n / p) log (p / 2)) ≤ c((n / p) log p)
Similarly, at the second level of the recursion tree, each quarter of the array will include n / 4 entries, but only p / 4 processors will be available to sort each half (since both halves would be sorted simultaneously). After each quarter's halves are sorted, the amount of time taken to merge them will be c(((n / 4) / (p / 4)) log (p / 4)) = c((n / p) log (p / 4)) ≤ c((n / p) log p)
This proceeds down for log2 p levels. Summing the time taken on each level, we arrive at O((n / p) log² p) to merge all the processors' segments together.
Once we go down log2 p levels, we have p segments, each with n / p elements. Applying mergesort to each segment on a single-processor system will take O((n / p) log (n / p)) time.
Adding these together, we arrive at O((n / p) log (n / p) + (n / p) log² p) = O((n / p) (log (n / p) + log² p)) = O((n / p) (log n + log² p)).
What does it mean for a problem to be in the NC complexity class? Give an example of a problem that is P-complete and so is probably not amenable to radical improvements in running time using multiple processors.
(Here, we're talking about P-completeness with respect to NC: That is, if Problem A is in NC, then all other problems in P are also in NC. This is a minor distinction in this course, but people sometimes talk about P-completeness with respect to other complexity classes.)
A problem is in NC if an algorithm exists for the problem that, given a number of processors polynomial in n (the size of the problem input), can compute the answer in time polylogarithmic in n (i.e., O((log n)d) for some constant d).
Examples of P-complete problems cited in class include:
Given a circuit of AND and OR gates and the inputs into the circuit, compute the output of the circuit.
Compute the preorder number for a depth-first search of a dag.
Computing the maximum flow of a weighted graph.