,:I f" Math 141 Exam 1 Version 2 Name: Sck-f(fm 1. "Ralph Nader was the best candidate for president, because he was totally better than all the others " Select the most suitable fallacy type. A) limited choice ® circular reasoning C) hasty generalization D) false cause 2. "I've met three race drivers today and they all were rather aggressive. Clearly, all race drivers are aggressive." Select themost suitable fallacy type. A) appeal to emotion slippery slope • JOm~ I J .1o!t! rtJCt oIh'wJ'. C hasty generalization- 8~~t 1. tr Om a ~) limited choice " 3. Which ofthe graphs below are connected? II A)® I only II only C) Both I and II D) Neither I nor II Page 1,,-p,JJ rPJ J4 r Jo nD \£.-Ju cH wU-) I lfltQu ~ III A) I only • 4. Which ofthe graphs below have Euler circuits? B) II only C) Both I and II D) Neither I nor II *A0 t r" .AJ.. ~.a, Or,v s.J;;cH-r:J, tJ;, nul 5. Every graph that has an Euler circuit is connected. CWlnLcftd. ~ False _ . B True 6. For which ofthe two situationsbelowis it desirable to find an Euler circuit oran efficient eulerization ofa graph? I. A street department employee must check the traffic signals at each intersection in a downtown area to be certain they are working. II. An employee ofa power company reads the electric meters outside each house along the streets in a residential area. A) I only ® IIonly C) Both I and II . D) Neither I nor II Page 27. Consider the path represented by the numbered sequences ofedges in the graph below. Which path represents an Euler circuit? 8 2 2 A) I only I II ~ ) D) IIonly Both I and II Neither I nor II Page 3• • • • • •••••• ••••• •••• • • ••••• •••• ••• ••••• • • • • 8. The map shown below illustrates part of a postal carrier's territory. The dots indicate mailboxes to which mail must be delivered. Which graph would be most useful for finding an efficient route for mail delivery? U L~ • ~~ fu_o:J~ ~ o. =#F G ~ d. FR3 c. Page 49. 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.) Em a. b. 0$ d. 10. A college student has six pairs ofpants, eight tee shirts, three sweatshirts and two pairs oftennis shoes. Ifan outfit consists ofpants, a tee shirt, a sweatshirt, and a pair oftennis shoes, how many different outfits can the student wear before repeating one? A) 124 B) 328 ~ 19 b ' ; , 3 ~ Z ® 288 Page 58 11. For the graph below, what is the cost ofthe Hamiltonian circuit obtained by using the nearest-neighbor algorithm, starting at A? A 10B ct+.2+/ + J+i -rJ ~ D 9,c A) 28 B) 35 ~ 25 (EJ 29 12. For the graph below, what is the cost of'the Hamiltonian circuit obtained by using the sorted-edges algorithm? A 2 B BF V I ~ &1.. + l.f t-S-+l~7 ....-&, A'; V A f-v 4 c CJ) vi AfX G F X .E A) B)© D) 33 41 29 23 11 D 16 r vi }fV' f!> J >( f-]) >( Page 613. Use Kruskal's algorithm for minimum-cost spanning trees on the graph below. What is the cost ofthe tree found? 41 5 6 5 3 9 2 7 ') 1 9 8l 6 P 2 -8 A) 39 B) 27 -S2 31 @;Mr'3.) )J,,;, fld-~~.. ~ jrO(Jtx c{ 14. The path produced by the nearest-neighbor algorithm when solving the traveling, salesman problem may be dependent on the starting city. A) False® True 15. Suppose a maintenance worker needs to empty garbage dumpsters from five locations on the grounds ofa park in the most efficient way possible. The technique most likely to be useful in solving this problem is A) applying Kruskal's algorithm for finding a minimum-cost spanning tree for a graph. B) fmding an Euler circuit on a graph. © applying the nearest-neighbor algorithm for the trl!.veling salesman problem. ,D) None ofthese techniques is likely to apply. Page 7~0 0 ;0 0, >0 ~ 16. What is the earliest possible completion time for a job whose order-requirement is shown below? 1S-11 ~T3 ~ ® T;). 13 Tr r}-<E-TQl f'6 -r::r lb T2 T3 T4 T:r IS"""TJ Tb 'I (o ;,.0 T5 Ts 11 @ 17 B) 15 C) 10 D) 40 17. The minimum-cost spanning tree produced by applying Kruskal's algorithm may contain the most expensive edge ofthe graph. ft2 False @)} True . 18. Suppose that a crew can currently complete in a minimum amount oftime the job whose order-requirement digraph is shown below. IfTask T6 is shortened from 7 minutes to 4 minutes, then what is the maximum amount by which the completion time ofthe entire job can be shortened? ' 11 T2 ><13 J:I!!-T T cK/o >0 ,>0 'I 2.. :s :Z3 c"Tl-'6 T4t:"\ T5(;"\ Ts(i;}, ,-r T /q \!!.) > \.!J >\!5 ~ J ~ A) It cannot be reduced. " ., T, B) 1 minute 4 .r b J1..' © 2minutes D) .~:3 minutes ~ Tt 1£ 20'lj. Tj T6 Ii JfJ1 vcIV) Tj Tl.-T7 &.1 k-Page 819. Given the order-requirement digraph below (with time given in minutes) and the priority list T" T2, T 3, T4, Ts, T6, apply the list-processing algorithm to construct a schedule using two processors. How much time does the resulting schedule require? 11T2 T3 o >0 >0 14f.'1 T'f.'I><0\..!.I > \.!J > 7 A) 24 minutes B) 21 minutes .-'t . 11.-Tj ~pi t '--~ 22minutes® .23 minutes 'T, I_ T4: )I Ir ~lPI. !,,! Itt /(.., .ll .2) 20. Given the order-requirement digraph below"(with time given in minutes) apply the critical-path scheduling algorithm to construct a priority list, (break ties by choosing task with lower subscript). -.~ GJ130 ,\~]f@ (j)(]) \y{T6 .@ 1-CD 11(';;\ T4(';;\ T5(;'\ ~~Ts @ 1-~ >~ )~ ~T1 IV .1} 0 .:r.. T.'I: I " \!)00~T·0 -T-Then the priority list would be: 'IL ~~ 11-r; ~~ A) T3T,T2T4T7TsT6 ® T2T,T4T7T3TsT6 C) T,T2T3T4TsT6T7 D) T7T6TsT4T3T2T, 21. 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 ~ J> bI Sf qI 3I 2 How much time does the resulting schedule require? t A) 16 minutes ® 14 minutes r EI C) 18 minutes pi J ~ 2 ® 15 minutes fL _ _ b~. 6 J It It Page 922. Choose the packing that results from the use ofthe worst fit (WF) bin-packing algorithm to pack the following weight$ into bins that can hold no more than 8 lbs. 5~7~1~2~4~5~1~1~3~6~2~ b.@12 2 23 3 2 7 7 66 5 555 4 Co ~ rTl ~ 1':"\'\1 ~ III 1 d. I~ ~ 16 12 6 15551 1 71 I~ 5 I 121 1,,\~ 23. Find the chromatic nUmber ofthe graph below: 23' J.A) 3 •If • Jt)2\94 D) 6 24. Write the resource constraints for this situation: A small stereo …