Practice for Exam 1

 1 Person A: I don't think children should run into the busy streets. Person B: I think that it would be foolish to lock up children all day with no fresh air. Person B uses flawed argument. What type of fallacy is it? Give a reason.

2.
What is the valence of vertex A in the graph below?

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

3.
Which of the graphs below have Euler circuits?

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

 4 Every graph with an even number of vertices has an Euler circuit. Choose: True or False

5.
Consider the path represented by the numbered sequence of edges of the graph below. Which statement is true?

 A. The path is not a circuit.
 B. The path is an Euler circuit.
 C. The path is a circuit, but not an Euler circuit.
 D. None of the above

6.
For which of the two situations below is it desirable to find an Euler circuit or an efficient Eulerization of a graph?
I) A pizza delivery person takes pizza to ten houses in the neighborhood and then returns to pick up the next set to be delivered.
II) The city government plows the roads after a snowfall.
 A. I only
 B. II only
 C. Both I and II
 D. Neither I nor II

 7 Which of the graphs shown below gives the best eulerization of the given graph. (In the graphs below, added edges are denoted with zig-zag lines.)

8.
Which of the following describes a Hamiltonian circuit for the graph below?

 A. ABCDEFJIHG
 B. ABCDEAFJDIHBGFEJICHGA
 C. ABCDEAGHIJFA
 D. AEDCBGHIJFA

9.
For the graph below, what is the cost of the Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A?

 A. 60
 B. 54
 C. 62
 D. 66

10.
For the graph below, what is the cost of the Hamiltonian circuit obtained by using the sorted-edges algorithm?

 A. 40
 B. 58
 C. 60
 D. 66

11.
Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. The cost of the tree found is:

 A. 23
 B. 20
 C. 16
 D. 5

12.
If the order-requirement digraph for a collection of tasks is shown below, then what is the minimum completion time for the collection of tasks?

 A. 64 minutes
 B. 43 minutes
 C. 36 minutes
 D. 28 minutes

13.
In which of the diagrams below do the wiggled edges represent spanning trees?

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

14.
You want to create a mileage grid showing the distances between every pair of the 10 Canadian provincial/territorial capitals. How many numbers will you have to compute?
 A. 100
 B. 90
 C. 45
 D. 20

15.
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

16.
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

17.
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

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

19.
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

20.
Find the chromatic number of the graph below:

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

21.
Write the constraint inequalities for this situation: Kim and Lynn produce pottery vases and bowls. A vase requires 35 oz. of clay and 5 oz. of glaze. A bowl requires 20 oz. of clay and 10 oz. of glaze. There are 500 oz. of clay available and 200 oz. of glaze available. The profit on one vase is \$5 and the profit on one bowl is \$4.
 A. 35x + 5y ≤ 5, 20 x + 10y ≤ 4, x ≥ 0, y ≥ 0
 B. 35x + 5y ≤ 500, 20 x + 10y ≤ 200, x ≥ 0, y ≥ 0
 C. 35x + 20y ≤ 500, 5 x + 10y ≤ 200, x ≥ 0, y ≥ 0
 D. 35x + 20y ≤ \$5, 5 x + 10y ≤ \$4, x ≥ 0, y ≥ 0

22.
Graph the constraint inequalities for a linear programming problem shown below. Which feasible region shown is correct?
 2 x + 3y ≤ 12 x ≥ 0, y ≥ 0

23.
The graph of the feasible region for a mixture problem is shown below. Find the point that maximizes the profit function P = 2x + y.

 A. (0, 2)
 B. (2, 4)
 C. (4, 1)
 D. (3, 0)

24.
Find an initial solution using the Northwest Corner Rule and compute its total transportation cost.
 Shop1 Shop 2 Shop 3 Bakery 1 3 1 2 5 Bakery 2 1 5 4 6 3 5 3 rim conditions

25.
Transport as many units of bread as possible through (Bakery1,Store3) and compute the improvement in total transportation cost. Adjust the numbers in the fields as necessary.
 Shop1 Shop 2 Shop 3 Bakery 1 33 52 20 5 Bakery 2 10 13 43 6 3 5 3 rim conditions

1.
Staw Man: why does kids not running on the street im ply they have to be kept indoors?
Limited Choice: kids can be out, just not on the street.
2. C
3. B
4. False
5. A
6. B
7.
c
8. D
9. D
10. D
11. C
12. B
13. B
14. C
15. C
16. C
17.
a
18.
b
19. C
20. D
21. C
22.
A
23. C
24.
 Shop1 Shop 2 Shop 3 Bakery 1 33 12 20 5 Bakery 2 10 53 43 6 3 5 3 rim conditions

Transportation Cost: 3*3+2*1+3*5+3*4 = 38
25.
 Shop1 Shop 2 Shop 3 Bakery 1 33 50 22 5 Bakery 2 10 15 41 6 3 5 3 rim conditions

Change in Transportation cost:      2*(2 - 5 + 1 - 4) = -12 , that's an improvement.