From: Mark Jacobson To: "John Coltrane" Cc: Jimi Hendrix Subject: Re: Questions about Green Test Review On Wed, 14 Nov 2007, Deputy Barney Fife (UNI) wrote: > Mark, > > This is John Coltrane (R=8,7). Jimi Hendrix and I were reviewing for test > tonight in the Union. We came up with a few questions. > 1. Will there be any questions on the test about hashes and/or search > performance? No, there will not be things on the exam that we have not covered in class yet. We have NOT covered binary trees or hash tables or average successful search performance for either one or for any data structures. > > 2. Are there any questions about binary search trees? No. > 3. How do I calculate a number of edges? > Example: Add the minimum number of edges (possibly 0 edges) to _each_ > of the following graphs so that the given binary relation that is > expressed by the graph is a _POSET binary relation_. (31 Oct 2003) You do NOT calculate the number of edges. You look at the graph. If you are trying to make it into a POSET, you check to see if it is reflexive, antisymmetric and transitive. If it lacks reflexiveness, you add the needed edges to each node (vertex) to make if reflexive. If it never has an edge going from one node to another node, it cannot be antisymmetric and NOT symmetric, so you would need to add an edge to make it be antisymmetric. 1 is related to 2, but there is no edge from 2 to 1. This means it is NOT SYMMETRIC, and it is ANTISYMMETRIC. When it has NO EDGES going from one vertex to another vertex, it is BOTH symmetric and antisymmetric. ---- If you ever see an edge from x to y and one from y to z and do NOT see an edge directly from x to z, you would have to ADD an edge to make it TRANSITIVE. There is no calculation involved. Just understand RST and RAT and the r, s, t, a and i properties. RST is equivalence relations. RAT is POSETs, Partially Ordered Sets POSETS go with HASSE diagrams. > 4. Are duplicate letters included in permutations or not? > Example: How many ways can the letters of the following be arranged or > permuted? a) prettier b) trinarytree > My Answers: a) P(8,8) = 8!/(8-8)! = 8!/0! = 8!/1 = 8! > b) P(11,11) = 11! > Explanation: a) The letters of prettier are individually important just > as if they were not the same letter. They can be > treated as a set like {P1,R1,E1,T1,T2,I1,E2,R2} where > P1 is the first P and P2 is the 2nd. (11 Mar 2005) WRONG! Yes, the letters in MISSISSIPPI are each individually important. However, there are only 4 different letters in the 11 letter long word. 11*10*9*8*7*6*4*3*2*1 How many ways can you arrange the 7983360 characters ABCDEFGHIJK? 11 factorial = 11! (11 * 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 * 1) / (24*24*2) 34650 How many ways can you arrange the letters in MISSISSIPPI? M IIII 4! = 24 SSSS 4! = 24 PP 2! = 2 Only 34,650 ways, not 7,983,360 ways. The textbook and the class website have many examples that explain how to count the number of permutations when you have repetitions. Study the textbook and website on this. TOO only has 3!/2! = 3 permuations TOO, OTO and OOT --- --- --- OPU has 3! = 6 permuations OPU OUP POU PUO UOP UPO JOKE has twice as many permutations as MOON or SOON JUNE has 6 times as many permuations as EPEE 4! = 24 4!/3! = 24/6 = 4 > 5. How would I solve a problem like #5 on 11 Mar 2005? > Example: Suppose it is known that you finish among the top 3 and you > get either gold, silver, or bronze medal. How many ways can the 3 > trophies be awarded if you are the winner of an unknown trophy. There > are 21 people in the race (20 + You). Show your work. There are 20 people who get medals besides yourself. Gold Silver Bronze 1 * 20 * 19 You place 1st 20 * 1 * 19 You place 2nd 20 * 19 * 1 You place 3rd -------------- 3 * (20 * 19) = 1,140 So the answer is 3 * 20 * 19 ways the medals could be awarded. ---------- 3*20 * 19 <----- bc calculator input 1140 <----- bc calculator output ---------- > My Answer: There are 6 ways the top 3 finishers can be arranged and > 190 ways to pick the other 2 on the committee of top 3 > finishers. 6 * 190 = 1140 ways to arrange the trophy > winners. 6 = P(3,3) 190 = C(20,2) > 190 = 10 * 19 and I do not see where the number 10 comes from as easily as seeing that there are 20 people for the first other medal and there are 19 people for the 2nd other medal besides the one you won. C(20, 2) is how many ways you can choose 2 runners to win medals, so your way does work. Order in NOT important in C(20, 2), which would make your answer wrong, except that you had order implied in the 3! or 6 ways 3 medals could be awarded to 3 people. Your answer would get full credit, but it is definitely not the most natural way to think about the problem. That comes with more experience. Try rewriting your CS I programs over Christmas break to warm up for and review for CS II class. You will discover that you write many of the programs in a more natural way now that you have a full semesters experience with the Ada or C++ language and with programming. That comes naturally with more experience. > How did I do on the interpretation of these sample problems? Would you like > me to come and see you Wednesday or will you plan to send out an e-mail to > the class? If I think of any others, then I will ask. You did fine except for the one about PRETTIER. P RR Each letter is important and it would be wrong EE spelling to leave out a T or an E and TT write PRETIER or PRETTIR. I However, the number of permuations you could make with those 8 letters is: 5,040 and not 40,320 8*7*6*5*4*3*2*1 40320 (8*7*6*5*4*3*2*1)/(2*2*2) 5040 PANTHERS <-- makes 8! = 40,320 permuations. PRETTIER <-- makes only 8!/(2!*2!*2!) = 5,040 permuations. http://cns2.uni.edu/~jacobson/c080.html I am at a math transitions conference today all day until 4:30 p.m. but will check my email after that to see if you are coming still. I assume the above has answered your questions. http://cns2.uni.edu/~jacobson/c080.html > Thank you for your help and time! > John Coltrane You are welcome! Good questions. Keep up the good work and studying. Mark