Problem 1(a)(b)(c)(d)(e)Problem 2(a)(b)Problem 3(a)(b)(c)(d)Problem 4(a)(b)Problem 5(a)(b)Problem 6Problem 7(a)(b)(c)(d)Problem 8Problem 9Problem 106.042/18.062J Mathematics for Computer Science December 17, 2008 Tom Leighton and Marten van Dijk Final Exam Name: • This final is closed book, but you may have three 8.5” × 11” sheets with notes in your own handwriting on both sides. • You may not use a calculator or a Python interpreter, and while exercising skill with a PostScript interpreter would highly impress at least one member of the course staff, you are not allowed to use that either. You may work with any of the follow-ing: a slide rule, an abacus, a Curta, Napier’s bones, any original version of the Antikythera mechanism, an Enigma machine, and/or the difference engine. You are also permitted to use a perpetual motion machine as a source of energy, and an antigravity device to elevate yourself above the rest of the class. • You may assume all of the results presented in class. • Please show your work. Partial credit cannot be given for a wrong answer if your work isn’t shown. • Write your solutions in the space provided. If you need more space, write on the back of the sheet containing the problem. Please keep your entire answer to a prob-lem on that problem’s page. • Be neat and write legibly. You will be graded not only on the correctness of your answers, but also on the clarity with which you express them. • If you get stuck on a problem, move on to others. The problems are not arranged in order of difficulty. • Please resist the urge to roll on the floor laughing out loud. • You have three hours to complete the exam. Problem 1 2 3 4 5 6 7 8 9 10 Total Points 25 25 25 15 15 15 25 15 20 20 200 Score Grader2 Final Exam Problem 1. [25 points] The Final Breakdown Suppose the 6.042 final consists of: • 36 true/false questions worth 1 point each. • 1 induction problem worth 15 points. • 1 giant problem that combines everything from the semester, worth 49 points. Grading goes as follows: • The TAs choose to grade the easy true/false questions. For each individual point, they flip a fair coin. If it comes up heads, the student gets the point. • Marten and Brooke split the task of grading the induction problem. – With 1/3 probability, Marten grades the problem. His grading policy is as follows: Either he gets exasperated by the improper use of math symbols and gives 0 points (which happens with 2/5 probability), or he finds the answer satisfactory and gives 15 points (which happens with 3/5 probability). – With 2/3 probability, Brooke grades the problem. Her grading policy is as follows: She selects a random integer point value from the range from 0 to 15, inclusive, with uniform probability. • Finally, Tom grades the giant problem. He rolls two fair seven-sided dice (which have values from 1 to 7, inclusive), takes their product, and subtracts it from 49 to determine the score. (Example: Tom rolls a 3 and a 4. The score is then 49 − 3 4 = · 37.) Assume all random choices during the grading process are mutually independent. The problem parts start on the next page. Show your work to receive partial credit.3 Final Exam (a) [7 pts] What is the expected score on the exam? (b) [5 pts] What is the variance on the 36 true/false questions?4 Final Exam (c) [5 pts] What is the variance on the induction score, given that Marten graded the problem? (d) [3 pts] Argue why the Markov bound can be used to determine an upper bound on the probability that the score on the exam is ≥ 80. You do not need to compute the actual bound. (e) [5 pts] Use the Chebyshev bound to determine an upper bound on the probability that the score on the true/false questions is ≥ 24.5 Final Exam Problem 2. [25 points] Woodchucks Chucking Wood All woodchucks can chuck wood, but only some can do it well. • 1/3 of all woodchucks like to chuck wood. • 2/3 of all woodchucks can chuck wood well. • 1/2 of those that like chucking wood can do it well. • The expected amount of wood chucked by a woodchuck (randomly chosen with uniform probability) is 7 kg/day. • The expected amount of wood chucked by a woodchuck that likes chucking wood but can’t do it well is 1 kg/day. • A woodchuck that does not like chucking wood does not chuck any wood at all, regardless of its wood-chucking skillz or lack thereof. (a) [10 pts] What is the probability that a woodchuck (randomly chosen with uniform probability) likes chucking wood, given that it can do it well?6 Final Exam (b) [15 pts] On average, how much wood would a woodchuck chuck if the woodchuck could chuck wood well?7 Final Exam Problem 3. [25 points] Cardsharing�Revolution Three 6.042 students—Kirari, Noelle, and Cobeni—are playing a game of Tan Tan Taan!. During each round of Tan Tan Taan!, each player is dealt 4 cards of their own, and one additional card is shared among all players, so that each player has 5 cards that they can use (the 4 cards of their own along with the single shared card). Cards are uniformly distributed from a 52-card deck. If you get four of a kind (for example, four aces or four 2’s), you can continue playing in the next round. If you don’t get four of a kind, you must quit and return to doing your 6.042 homework. Cards from round to round are mutually independent. This game is so fun that even if two of the three players must quit and return to their 6.042 homework, the third player will continue playing alone as long as they are able to. (a) [5 pts] What is the probability that Kirari has four aces in the first round? (b) [5 pts] What is the probability that Kirari doesn’t get four of a kind in the first round (and must quit playing)?8 Final Exam (c) [5 pts] What is the expected number of rounds that Kirari will play? (d) [10 pts] What is the probability that all three can play a second round?9 Final Exam Problem 4. [15 points] Packet Racket! Consider the complete ternary-tree network with 9 inputs and 9 outputs shown below where packets are routed randomly. The route each packet takes is the shortest path between input and output. Let I0, I1, and I2 be indicator random variables for the events that a packet originating at in0, in1, and in2, respectively, crosses the dashed edge in the figure. Let T = I0 + I1 + I2 be a random
View Full Document
Unlocking...