Exercise 13 Theory: Linear Programming

Exercise 1:
a)Which of the following is NOT common to solve by linear programming?
-Linear time sorting
-Shortest path
-Maximum flow
-Multicommodity flow

b)What does it mean that a linear program is infeasible?
-There are no valid solutions
-There is no unambigous optimal solution
-There are elements in the program that aren't linear
-There exists an optimal solution

c)What does it mean that a linear program is unbounded?
-There are no valid solutions
-There is no unambigous optimal solution
-There are elements in the program that aren't linear
-There exists an optimal solution

Exercise 2:
a)Maximize:(2*x + 6*y - 3*z)
under the following restrictions:
x,y,z >= 0
y-z <= 1
x+y <= 4
-x = 0; y = 4; z = 3;
-x = 3; y = 1; z = 0;
-x = 0; y = 4; z = 0;
-x = 4; y = 4; z = 1;
-x = 4; y = 1; z = 0;
-x = 2; y = 2; z = 5;

Exercise 3:
What does the following describe?
a)Tp
-Runtime with p processors
-Total amount of work
-Critical path(span)

b)T1
-Runtime with p processors
-Total amount of work
-Critical path(span)

c)T(inf)
-Runtime with p processors
-Total amount of work
-Critical path(span)

d)Which of the following descriptions of critical path(span) is correct?
-The maximum number of processors that can work at the same time
-Longest path where the steps can't be executed in parallel
-A path that appears many times, and thus can be run byonly one processor once

e)What can you tell from T1<=Tp*P?
-The parallelity of the algorithm is optimal
-The critical path is limited by the number of processors
-The work load when using P processors is not less than when using 1