Www.csc.villanova.edu



VILLANOVA UNIVERSITYDepartment of Computing SciencesThursday, April 7, 2016Exam 3 of 3Show your work carefully. Just writing an answer will not do. Show any assumptions; show the steps you took, and show how you came to your answer.No calculators or any reference except your one note card is permitted. If an answer involves a computation that would be very time consuming, you may leave it in a form that just needs final calculation.Chapter 7Consider the alphabet A, B, C, D, E, F and make words without repetition of letters allowed. Remember the note at the beginning. You must show how you came to your answer. Just the answer alone will not be sufficient.How many 6-letter words are there?Six slots. Six choices for first, 5 for second, etc. 6 5 4 3 2 1 = 6!How many words begin with A or E or C?Still six slots. Now only 3 choices for the first slot, still 5 for second, etc. 3 5 4 3 2 1 = 3 * 5!How many words end with D or B?Still six slots. Constraint on the last one allows only two options there. The others are filled from the five letters not used in the last slot. 5 4 3 2 1 2 = 2 * 5!How many words have first letter that is not A or B or C and last letter that is not F?Two cases here. 1 - First letter is D or E, so two choices. Last letter any of the five remaining, except F, so 4 choices. Other slots take what is left. 2 4 3 2 1 4 2 – First letter is F. Other five slots get any of the rest. 1 5 4 3 2 1Add these: 2 * 4 * 4! + 5!You decide to treat the class to donuts one day. The class is not quite as large as ours – there are 24 students, so you will get two dozen donuts. The shop has 5 kinds of filled donuts (chocolate cream, vanilla cream, strawberry cream, vanilla custard, and cherry custard), 4 kinds of glazed donuts (maple, chocolate, coconut, praline), and 3 kinds of nut-crusted donuts (peanut, almond, walnut). In addition there are plain chocolate donuts and powdered sugar donuts. How many ways are there to choose your two dozen donuts? (This is one order of 2 dozen donuts, not two separate one-dozen orders.)This is the same type of problem as the fudge problem in the book. There are 14 options for the kinds of donut. (5 kinds of filled, 4 kinds of glazed, 3 kinds of nut-crusted, 1 plain chocolate, 1 powdered sugar). The 14 kinds of donut are like the flavors of fudge in the book problem. The 24 donuts are like the boxes in that problem.24+1313= 2713 There are 10 perfect daffodils available to place into 15 different small vases (each vase holds just one flower). The vases are distinct, being of different shapes and colors. How many ways are there to arrange the flowers in the vases?15 possible, choose 10 to get daffodils. 1510Chapter 8Recognition and basicsFor each of these, identify the technique appropriate for finding a closed form solution. The possibilities are Finite Difference (Arithmetic Sequence) or Characteristic Equation (Geometric Sequence) or Neither of those. Be sure to explain your answer.an = 2an-1+3an-2Linear, homogeneous equation with constant coefficientsan = an-1 + 3n2 – 2n + 5Arithmetic Sequencean = 2an-1+3an-2 + 5Not homogeneousan = 2an-1an-2Product of two a termsFind a0 for this recurrence:an = an-1+3an-2 a1 = 3 a2 = 6a2 = a1 + 3 a06 = 3 + 3 a03 = 3 a01 = a0Fibonacci numbers: Show that Fn+4 = 3 Fn+1 + 2 FnDoes Fk+1+4 = 3 Fk+1+1 + 2 Fk+1 ???Fk+5 = 3Fk+2 + 2 Fk+1Fk+5 = Fk+4 + Fk+3 --- Definition of Fibonacci numberFk+5 = Fk+3 + Fk+2 + Fk+2 + Fk+1 = Fk+2 + Fk+1+ Fk+2 + Fk+2 + Fk+1 = 3 (Fk+2) + 2(Fk+1 ) Find the closed form for this recurrence relation. Show all the steps clearlya1 = -2 a2 = 4 an = – an-1 + 6 an-2xn = -1xn-1 + 6xn-2x2 = -1x + 6x2 + x – 6 = 0(x+3)(x-2) = 0r1 = -3r2 =2an=q1(-3)n + q2(2)nneed to find q1, q2a1 = -2 = q1 (-3)1 +q2 (2)1a2 = 4 = q1(-3)2 + q2(2)2 -2 = -3 q1 +2 q24 = 9q1 + 4q2 3 q1 = 2 + 2q24 = 9(2 + 2q23) + 4 q2 q1 = 2 + 2q234 = 6 + 6q2 +4 q2-2/10 = q2q1 = 2+2q23=2+2(-210)3=16/103an = 16103 (-3)n - 210(2)nChapter 10 Minimum Spanning TreeHow many edges will the spanning trees of this graph contain? How do you know that? 5 = |V| -1Use the graph shown ON THE NEXT PAGE. In each of the following, show your individual steps. That means that you keep redrawing what you have done before to show how the spanning tree evolvesFind a minimum spanning tree using Kruskal’s algorithmFind a minimum spanning tree using Prim’s algorithm00Make a binary search tree for this list of words. Place the first item shown at the root. Insert the other items in the order in which they appear.One, Defines, An, Object, As, Process, Computer, Science, Study, Technique, Routine MatchingsFind a perfect matching for the graph used for question 7. (Draw it here)Three edges: A----F D-----E B-----CFor each of the graphs above, find a perfect matching or explain why none exists.Graph 1 – none. Odd number of verticesGraph 2 – none Two leaves attached to the same nodeGraph 3 – yes, several possible ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download