1.	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?

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

2.	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?

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

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

	A)  16 minutes    B)  17 minutes    C)  18 minutes    D)  21 minutes	

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

	A)  40 minutes    B)  44 minutes    C)  45 minutes    D)  49 minutes	

5.	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?

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

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

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

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

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

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

	A)  16 minutes    B)  17 minutes    C)  18 minutes    D)  21 minutes	

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

	A)  40 minutes    B)  44 minutes    C)  45 minutes    D)  49 minutes	

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

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

11.	What is the minimum time required to complete nine independent tasks on three processors when the sum of all the times of the nine tasks is 72 minutes?	
	A)  3 minutes    B)  8 minutes    C)  24 minutes    D)  27 minutes	

12.	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?	
	A)  4 minutes    B)  9 minutes    C)  16 minutes    D)  36 minutes	

13.	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?	
	A)  6 minutes    B)  14 minutes    C)  24 minutes    D)  42 minutes	

14.	What is the minimum time required to perform six independent tasks with a total task time of 48 minutes on 3 machines?	
	A)  2 minutes    B)  8 minutes    C)  16 minutes    D)  18 minutes	

15.	What is the minimum time required to perform eight independent tasks with a total task time of 48 minutes on four machines?	
	A)  2 minutes    B)  6 minutes    C)  12 minutes    D)  24 minutes	

16.	Use the decreasing-time-list algorithm to schedule these tasks on two machines:  
	
4 minutes, 5 minutes, 8 minutes, 3 minutes, 3 minutes, 7 minutes	

How much time does the resulting schedule require?	
	A)  15 minutes    B)  16 minutes    C)  17 minutes    D)  18 minutes	

17.	Use the decreasing-time-list algorithm to schedule these tasks on two machines:  
	
3 minutes, 5 minutes, 8 minutes, 4 minutes, 6 minutes, 2 minutes	

How much time does the resulting schedule require?	
	A)  14 minutes    B)  15 minutes    C)  16 minutes    D)  18 minutes	

18.	Use the decreasing-time-list algorithm to schedule these tasks on two machines:  
	
9 minutes, 6 minutes, 3 minutes, 4 minutes, 8 minutes	

How much time does the resulting schedule require?	
	A)  14 minutes    B)  15 minutes    C)  16 minutes    D)  17 minutes	

19.	Use the decreasing-time-list algorithm to schedule these tasks on two machines:  
	
9 minutes, 2 minutes, 8 minutes, 5 minutes, 4 minutes, 8 minutes	

How much time does the resulting schedule require?	
	A)  17 minutes    B)  18 minutes    C)  19 minutes    D)  22 minutes	

20.	Use the decreasing-time-list algorithm to schedule these tasks on two machines:
	
9 minutes, 8 minutes, 7 minutes, 9 minutes, 2 minutes, 5 minutes.	

How much time does the resulting schedule require?	
	A)  19 minutes    B)  20 minutes    C)  21 minutes    D)  22 minutes	

21.	Choose the packing that results from the use of the first fit (FF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
	
6 lbs, 2 lbs, 4 lbs, 3 lbs, 5 lbs, 3 lbs, 2 lbs, 4 lbs	

 	

22.	Choose the packing that results from the use of the next fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
	
6 lbs, 2 lbs, 4 lbs, 3 lbs, 5 lbs, 3 lbs, 2 lbs, 4 lbs	

 	

23.	Choose the packing that results from the use of the worse fit (WF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
	
6 lbs, 2 lbs, 4 lbs, 3 lbs, 5 lbs, 3 lbs, 2 lbs, 4 lbs	

 	

24.	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 8 lbs.
	
6 lbs, 2 lbs, 4 lbs, 3 lbs, 5 lbs, 3 lbs, 2 lbs, 4 lbs	

 	

25.	Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
	
6 lbs, 2 lbs, 4 lbs, 3 lbs, 5 lbs, 3 lbs, 2 lbs, 4 lbs 	

 	

26.	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.
	
6 lbs, 2 lbs, 4 lbs, 3 lbs, 5 lbs, 3 lbs, 2 lbs, 4 lbs 	

 	

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

 
d. Another packing 	

28.	Choose the packing that results from the use of the next fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
4 lbs, 5 lbs, 3 lbs, 2 lbs, 7 lbs, 6 lbs, 4 lbs, 2 lbs	

 
d. Another packing 	

29.	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 9 lbs.
	
4 lbs, 5 lbs, 3 lbs, 2 lbs, 7 lbs, 6 lbs, 4 lbs, 2 lbs	

 
d. Another packing 	

30.	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 lbs, 5 lbs, 3 lbs, 2 lbs, 7 lbs, 6 lbs, 4 lbs, 2 lbs	

 
d. Another packing 	

31.	Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 9 lbs.
	
4 lbs, 5 lbs, 3 lbs, 2 lbs, 7 lbs, 6 lbs, 4 lbs, 2 lbs	

 
d. Another packing 	

32.	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 lbs, 5 lbs, 3 lbs, 2 lbs, 7 lbs, 6 lbs, 4 lbs, 2 lbs	

 
d. Another packing 	

33.	Choose the packing that results from the use of the first fit (FF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs	

 	

34.	Choose the packing that results from the use of the next fit (NF) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs	

 	

35.	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.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs	

 	

36.	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 8 lbs.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs, 3 lbs	

 
d. Another packing 	

37.	Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack the following weights into bins that can hold no more than 8 lbs.
     5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs, 3 lbs

d. Another packing 	

38.	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.
	
5 lbs, 7 lbs, 1 lb, 2 lbs, 4 lbs, 5 lbs, 1 lb, 1 lb, 3 lbs, 6 lbs, 2 lbs, 3 lbs	

 
d. Another packing 	

39.	A talent show producer needs to fit 17 acts of varying lengths into three segments.  The segments should be as short as possible and are to be separated by intermissions. 
 
This problem could be solved by using 	

40.	A talent show producer needs to fit 17 acts of varying lengths into several segments.  The segments will be no more than 45 minutes long, and are to be separated by intermissions. 
 
This problem could be solved by using	
A)	the list processing algorithm for independent tasks.	
B)	the worst-fit algorithm for bin packing.	
C)	the critical-path scheduling algorithm.	
D)	None of these techniques would work to find a solution.	

41.	Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below.  If Task T1 is shortened from 7 minutes to 4 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

	A)  It cannot be reduced.    B)  1 minute    C)  2 minutes    D)  3 minutes	

42.	Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below.  If Task T2 is shortened from 9 minutes to 6 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

	A)  It cannot be reduced.    B)  1 minute    C)  2 minutes    D)  3 minutes	

43.	Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below.  If Task T4 is shortened from 8 minutes to 5 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

	A)  It cannot be reduced.    B)  1 minute    C)  2 minutes    D)  3 minutes	

44.	Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below.  If Task T5 is shortened from 6 minutes to 3 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

	A)  It cannot be reduced.    B)  1 minute    C)  2 minutes    D)  3 minutes	

45.	Suppose that a crew can currently complete in a minimum amount of time the job whose order-requirement digraph is shown below.  If Task T6  is shortened from 7 minutes to 4 minutes, then what is the maximum amount by which the completion time of the entire job can be shortened?

	A)  It cannot be reduced.    B)  1 minute    C)  2 minutes    D)  3 minutes	

46.	The first fit (FF) algorithm never uses more boxes than the next fit (NF) algorithm.	
	A)  True    B)  False	

47.	The worst fit (WF) algorithm never uses more boxes than the first fit (FF) algorithm.	
	A)  True    B)  False	

48.	When scheduling tasks using the list-processing algorithm, increasing the number of machines always reduces the completion time.	
	A)  True    B)  False	

49.	When scheduling tasks using the list-processing algorithm, decreasing the time of each task always decreases the completion time.	
	A)  True    B)  False	

50.	The list-processing algorithm for scheduling tasks is guaranteed to always produce an optimal solution.	
	A)  True    B)  False	

51.	The worst-fit decreasing (WFD) algorithm for bin packing is guaranteed to always produce an optimal solution.	
	A)  True    B)  False	

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

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

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

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

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

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

55.	The table below shows chemical compounds that cannot be mixed without causing dangerous reactions.  Which graph would be used to facilitate scheduling of disposal containers for the compounds?

A	
B	
C	
D	
E	
F	

A	
	
X	
	
X	
X	

B	
X	
	
X	
	
X	
X	

C	
	
X	
	
X	

D	

X	

X	

E	
X	
X	

F	
	
X	
	
X	

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

56.	Find the chromatic number of the graph below:

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

57.	Find the chromatic number of the graph below:

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

58.	Find the chromatic number of the graph below:

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

59.	Assume an order-requirement digraph requires 30 minutes when scheduled on three machines. Based on this information, when the digraph is instead scheduled on two machines, how much time will be required?	
A)	Exactly 30 minutes	C)	Exactly 45 minutes	
B)	Exactly 40 minutes	D)	At least 45 minutes	

60.	Assume an order-requirement digraph has a critical path with length 40 minutes. Based on this information, when the digraph is scheduled on four machines, how much time will be required?	
A)	Exactly 10 minutes	C)	At least 40 minutes	
B)	Exactly 30 minutes	D)	Exactly 40 minutes	

61.	Assume a job consists of six independent tasks ranging in time from 3 to 12 minutes and totaling 36 minutes. Efficiently scheduled on four machines, how much time will the job require?	
A)	Exactly 3 minutes	C)	Exactly 12 minutes	
B)	Exactly 9 minutes	D)	More than 12 minutes	

62.	What is the minimum time required to complete 12 independent tasks on four processors when the sum of all the times of the 12 tasks is 120 minutes?	
	A)  10 minutes    B)  30 minutes    C)  40 minutes    D)  60 minutes	

63.	What is the minimum time required to complete eight independent tasks with a total task time of 160 minutes on four machines?	
	A)  10 minutes    B)  20 minutes    C)  40 minutes    D)  60 minutes	

64.	Choose the packing that results from the use of the first fit (FF) bin-packing algorithm to pack data files with the following sizes onto compact discs that can hold no more than 700 MB.
 
100 MB, 500 MB, 250 MB, 350 MB, 400 MB, 250 MB, 450 MB, 200 MB, 50 MB	
A)		
B)		
C)		
D)		

65.	Choose the packing that results from the use of the next fit (NF) bin-packing algorithm to pack data files with the following sizes onto compact discs that can hold no more than 700 MB.
 
100 MB, 500 MB, 250 MB, 350 MB, 400 MB, 250 MB, 450 MB, 200 MB, 50 MB	
A)		C)		
B)		D)		

66.	Choose the packing that results from the use of the first-fit decreasing (FFD) bin-packing algorithm to pack data files with the following sizes onto compact discs that can hold no more than 700 MB.
 
100 MB, 500 MB, 250 MB, 350 MB, 400 MB, 250 MB, 450 MB, 200 MB, 50 MB	
A)		C)		
B)		D)		

67.	Choose the packing that results from the use of the next-fit decreasing (NFD) bin-packing algorithm to pack data files with the following sizes onto compact discs that can hold no more than 700 MB.
 
100 MB, 500 MB, 250 MB, 350 MB, 400 MB, 250 MB, 450 MB, 200 MB, 50 MB	
A)		C)		
B)		D)		

Answer Key

1.	C	
2.	D	
3.	B	
4.	B	
5.	C	
6.	C	
7.	D	
8.	B	
9.	B	
10.	C	
11.	C	
12.	D	
13.	D	
14.	C	
15.	C	
16.	A	
17.	A	
18.	C	
19.	B	
20.	C	
21.	a	
22.	a	
23.	a	
24.	b	
25.	c	
26.	d	
27.	b	
28.	d	
29.	c	
30.	c	
31.	a	
32.	b	
33.	b	
34.	c	
35.	a	
36.	a	
37.	d	
38.	b	
39.	the list processing algorithm for independent tasks.	
40.	B	
41.	C	
42.	C	
43.	A	
44.	A	
45.	C	
46.	B	
47.	B	
48.	B	
49.	B	
50.	B	
51.	B	
52.	C	
53.	A	
54.	B	
55.	A	
56.	C	
57.	D	
58.	B	
59.	D	
60.	C	
61.	C	
62.	B	
63.	B	
64.	D	
65.	B	
66.	A	
67.	C