Math 115

A B

F C

E D

November 4, 2009 Name: Key

Quiz 8

1. Find a path from vertex A to vertex F on the digraph shown:

ADCF

2. 2 processors have 5 independent tasks to accomplish: A(3 minutes),

B(2), C(6), D(5), and E(4)

Show the schedule for the 2 processors using the decreasing time algorithm

The priority list is CDEAB, and there are no precedence relations, so it is scheduled as:

C---------------------------------à A-------------à B------à

D--------------------------à E--------------------à

A(5) (13) D(5) (5) End(0)

Start(0) C(3)(8)

(14)

E(4) (4)

B(6) (14)

b. Does the decreasing time algorithm find the optimal solution in this example? Carefully justify your answer.

No, it doesn’t. If we change the priority list a little bit, we can finish the project quicker: Have one processor complete C, then E, and the other D, A and B – both will finish in 10 minutes.

3. a. The times, in minutes, for each of 5 tasks

are shown. Find the critical time for each task,

and write these times next to the vertex labels.

b. What is the shortest amount of time this project could take to complete, if you had 100 processors available?

It doesn’t matter how many processors you use – you can’t finish this in less than the critical time for the project, which is 14 minutes.