Question 1

What is the minimum time required to complete eight independent tasks on two processors when the sum of all the times of the eight tasks is 72 minutes?

Accepted Answer

A)   4 minutes
B)   9 minutes
C)   16 minutes
D)   36 minutes D

Question 2

Choose the packing that results from the use of the worst-fit decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs. $$4 \mathrm { lbs } , 5 \mathrm { lbs } , 3 \mathrm { lbs } , 2 \mathrm { lbs } , 7 \mathrm { lbs } , 6 \mathrm { lbs } , 4 \mathrm { lbs } , 2 \mathrm { lbs }$$

Accepted Answer

A)   
B)   
C)   
D)   Another packing  B

Question 3

Use the decreasing-time-list algorithm to schedule these tasks on two machines: How much time does the resulting schedule require? $$9 \text { minutes, } 2 \text { minutes, } 8 \text { minutes, } 5 \text { minutes, } 4 \text { minutes, } 8 \text { minutes }$$

Accepted Answer

A)   17 minutes
B)   18 minutes
C)   19 minutes
D)   22 minutes  B

Question 4

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs:
2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs
-Find the number of bins required using the first-fit (FF) algorithm.

Accepted Answer

A)   4
B)   5
C)   6
D)   8

Question 5

Choose the packing that results from the use of the worst-fit decreasing (WFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs. $$61 \mathrm { bs } , 2 \mathrm { lbs } , 4 \mathrm { lbs } , 3 \mathrm { lbs } , 5 \mathrm { lbs } , 3 \mathrm { lbs } , 2 \mathrm { lbs } , 4 \mathrm { lbs }$$

Accepted Answer

A)   
B)   
C)   
D)

Question 6

What is the minimum time required to complete 12 independent tasks on two processors when the sum of all the times of the 12 tasks is 84 minutes?

Accepted Answer

A)   6 minutes
B)   14 minutes
C)   24 minutes
D)   42 minutes

Question 7

Find the chromatic number of the graph below.

Accepted Answer

A)   2
B)   3
C)   4
D)   5

Question 8

Given the order-requirement digraph below (with time given in minutes) and the priority list T1, T2, T 3, T4, T5, T6, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

Accepted Answer

A)   14 minutes
B)   15 minutes
C)   16 minutes
D)   18 minutes

Question 9

For an order-requirement digraph of 10 tasks, how many priority lists are possible?

Accepted Answer

The answer of For an order-requirement digraph of 10 tasks,...

Question 10

Compare the first-fit (FF) and first-fit decreasing (FFD) bin-packing algorithms in packing the following weights into bins that can hold no more than 10 lbs. 
3 lb, 8 lbs, 5 lbs, 7 lbs, 5 lbs, 5 lbs, 8 lbs, 4 lbs, 10 lbs, 6 lbs

Accepted Answer

The answer of Compare the first-fit (FF) and first-fit decreasing...

Question 11

Use the decreasing-time-list algorithm to schedule these tasks on two machines:
4, 2, 1, 6, 4, 5, 4 (time in minutes).
How much time does the resulting schedule require?

Accepted Answer

The answer of Use the decreasing-time-list algorithm to schedule these...

Question 12

Given the order-requirement digraph below (with time given in minutes) and the priority list T1, T4, T 5, T2, T3, T6, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

Accepted Answer

A)   21 minutes
B)   22 minutes
C)   23 minutes
D)   24 minutes

Question 13

Which of the following is a correct vertex coloring of the given graph? (Capital letters indicate which color the vertex is colored.)

Accepted Answer

A)   I only
B)   II only
C)   Both I and II
D)   Neither I nor II

Question 14

The worst-fit (WF) algorithm never uses more boxes than the first-fit (FF) algorithm.

Accepted Answer

A) True 
 B)False

Question 15

Choose the packing that results from the use of the worst-fit (WF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs. $$61 \mathrm { bs } , 2 \mathrm { lbs } , 4 \mathrm { lbs } , 3 \mathrm { lbs } , 5 \mathrm { lbs } , 3 \mathrm { lbs } , 2 \mathrm { lbs } , 4 \mathrm { lbs }$$

Accepted Answer

A)   
B)   
C)   
D)   .

Question 16

When scheduling tasks using an order-requirement digraph, why does the critical-path scheduling algorithm generally produce good schedules? Does it always produce an optimal schedule?

Accepted Answer

The answer of When scheduling tasks using an order-requirement digraph,...

Question 17

What is the minimum number of processors required to perform the following tasks in 12 minutes? $$3 \text { minutes, } 5 \text { minutes, } 8 \text { minutes, } 4 \text { minutes, } 6 \text { minutes, } 2 \text { minutes }$$

Accepted Answer

A)   2
B)   3
C)   4
D)   5

Question 18

Choose the packing that results from the use of the first-fit decreasing (FFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs. $$4 \mathrm { lbs } , 5 \mathrm { lbs } , 3 \mathrm { lbs } , 2 \mathrm { lbs } , 7 \mathrm { lbs } , 6 \mathrm { lbs } , 4 \mathrm { lbs } , 2 \mathrm { lbs }$$

Accepted Answer

A)   
B)   
C)    
D)   Another packing

Question 19

Find the chromatic number of the graph below:

Accepted Answer

The answer of Find the chromatic number of the graph...

Question 20

Find the chromatic number of the graph below.

Accepted Answer

A)   6
B)   4
C)   3
D)   2

Exam 3: Planning and Scheduling

What is the minimum time required to complete eight independent tasks on two processors when the sum of all the times of the eight tasks is 72 minutes?

Use the decreasing-time-list algorithm to schedule these tasks on two machines: How much time does the resulting schedule require? $9 \text { minutes, } 2 \text { minutes, } 8 \text { minutes, } 5 \text { minutes, } 4 \text { minutes, } 8 \text { minutes }$

Questions refer to this bin-packing task. Pack the following weights into bins holding no more than 5 lbs: 2 lbs, 1 lb, 4 lbs, 3 lbs, 4 lbs, 1 lb, 2 lbs, 3 lbs -Find the number of bins required using the first-fit (FF) algorithm.

What is the minimum time required to complete 12 independent tasks on two processors when the sum of all the times of the 12 tasks is 84 minutes?

Find the chromatic number of the graph below.

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₂, T ₃, T₄, T₅, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

For an order-requirement digraph of 10 tasks, how many priority lists are possible?

Compare the first-fit (FF) and first-fit decreasing (FFD) bin-packing algorithms in packing the following weights into bins that can hold no more than 10 lbs. 3 lb, 8 lbs, 5 lbs, 7 lbs, 5 lbs, 5 lbs, 8 lbs, 4 lbs, 10 lbs, 6 lbs

Use the decreasing-time-list algorithm to schedule these tasks on two machines: 4, 2, 1, 6, 4, 5, 4 (time in minutes). How much time does the resulting schedule require?

Given the order-requirement digraph below (with time given in minutes) and the priority list T₁, T₄, T ₅, T₂, T₃, T₆, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require?

Which of the following is a correct vertex coloring of the given graph? (Capital letters indicate which color the vertex is colored.)

The worst-fit (WF) algorithm never uses more boxes than the first-fit (FF) algorithm.

When scheduling tasks using an order-requirement digraph, why does the critical-path scheduling algorithm generally produce good schedules? Does it always produce an optimal schedule?

What is the minimum number of processors required to perform the following tasks in 12 minutes? $3 \text { minutes, } 5 \text { minutes, } 8 \text { minutes, } 4 \text { minutes, } 6 \text { minutes, } 2 \text { minutes }$

Find the chromatic number of the graph below:

Find the chromatic number of the graph below.