15-112 Spring 2015 Homework 10
Due Sunday, 5-Apr, at 10pm

Read these instructions first!

Starting this week, you may use Monte Carlo techniques, in addition to OOP, exceptions, and recursion, sets and maps,2d lists, event-based animations, 1d-lists, tuples, strings, graphics, loops and conditionals.

This hw is entirely manually graded -- no portion of this hw is autograded. Even so, you may make up to 5 submissions. As usual, only your last one counts.

These problems require Monte Carlo techniques. Even if you know how to solve these problem without them (say, by using exact formulas, or by counting techniques, or any other way), you must use Monte Carlo techniques to receive any credit. Then again, you may use those other solution approaches in your test functions if you wish.

Testing Monte Carlo functions is hard, because the results vary each run, and sometimes you have little idea how to limit the range of viable results. We are not looking for extraordinarily brilliant test functions. But you do have to do something. For example, you could at least test that a probability is between 0 and 1. Hopefully, you could narrow the range down tighter than that for most problems. But don't stress over your test functions, as we know they won't be too effective this week.

TP Peer Discussions [5 pts] [manually graded]
Meet in a small group of 3-5 students (and unlike other collaborative hw's, here the collaboration is required; you may not do this part solo, since there is no such thing as a solo peer discussion). These meetings will be for at least one-half hour, and everyone must be on time, participate fully, and stay to the end. Each participant should describe their current thinking about their term project ideas, and then the group should discuss the ideas, trying to provide constructive, helpful, interesting feedback and suggestions. Even if you have no ideas, you must suggest something. Plus, if at all possible, you should share pictures or storyboards of your idea, or if you don't have that, then perhaps a short video clip of a similar idea on YouTube. In any case, present your idea quickly, so that most of the time is spent discussing the idea. The goal here is not to dream up every possible suggestion, but rather to come up with a few really, really good suggestions.

What to turn in (in the triple-quoted string at the top of hw10.py): a list of your groupmates (names and andrew id's) and your detailed notes on their feedback and suggestions for you.

Excerpts from f14-midterm2 [10 pts] [manually graded]
In the triple-quoted string at the top of hw10.py, include your solutions to these problems from f14-midterm2:
- 1. just part 1 (skip parts 2 and 3)
- 2. all
- 3. all
- 4. part D and part E
- 5. the first 4 parts (skip t1 and t2)
- 6. all
- 7. none (skip)
- 8. all
- bonus: the first one (skip the second) (this is not for bonus on the hw)
It is recommended, but not required, that you first print out the midterm and take these under exam conditions, and then go back and correct them, only then placing the corrected solutions into your hw10.py triple-quoted string.

deMeresProblem(t) [5 pts] [manually graded]
Background: The French nobleman Chevalier de Mere, a notorious gambler, once asked the great mathematician Blaise Pascal to confirm his suspicion that the probability of getting at least one "6" in four rolls of a single 6-sided die is slightly higher than the probability of getting at least one double-six in 24 rolls of two dice.

With this in mind, write the function deMeresProblem(t) that takes one parameter, a non-negative integer number of trials, and, using Monte Carlo techniques with the given number trials each, computes the odds of each event, and returns True if, based on your computations, deMere was right and False otherwise. Interestingly, deMere's inquiry is believed to have led Pascal (with help from Fermat) to invent what we think of as the field of probability theory!

randomCoprimeOdds(t) [10 pts] [manually graded]
Write the function randomCoprimeOdds(t) that takes one parameter, a non-negative integer number of trials, and by using Monte Carlo techniques with the given number of trials, determines and returns the probability (as a float between 0 and 1) that two integers chosen at random between 2 and 1 billion, each, happen to be coprime (that is, that they have no common factors besides 1).

stickyTriangleOdds(t) [15 pts] [manually graded]
Say that you take a stick and randomly break it in two, then take the longer of the two pieces and randomly break that piece in two, so now you have three pieces. Write the function stickyTriangleOdds(t) that takes one parameter, a non-negative integer number of trials, and using Monte Carlo techniques with the given number of trials, returns the probability (as a number between 0 and 1) that the three pieces can form a triangle.

oddsOfAnEvenNumberOfSixes(n, t) [15 pts] [manually graded]
Background: According to this really interesting page from Drexel University's "Ask Dr. Math" Math Forum, if a six-sided die is thrown n times, then the probability that there were an even number of sixes among those n throws is 1/2 * [1 + (2/3)**n]. Fascinating! For this problem, you will use Monte Carlo methods to empirically confirm this result.

Write the function, oddsOfAnEvenNumberOfSixes(n, t), that takes two integers -- n, the number of throws to make for each trial, and t, a non-negative integer number of trials -- and using Monte Carlo techniques with the given number of trials, returns the probability (as a number between 0 and 1) that one would get an even number of sixes among n throws. In a comment above this function, briefly reflect on whether or not this seemed to confirm the formula from "Ask Dr. Math".

yahtzeeOdds(rollsPerTurn, trials) [40 pts] [manually graded]
First, read the entire writeup on Yahtzee (problem #1) from s11-hw5. Here, you are only responsible for the yahtzeeOdds(rollsPerTurn, trials) and testYahtzeeOdds() functions from part e (though you may wish to write some of the helper functions specified earlier in the problem).

Bonus/Optional: bonusTexasHoldEmVisualizer() [up to 5 pts] [manually graded]
Write the function bonusTexasHoldEmVisualizer(), that takes no parameters, and makes the second chart on this page, which displays a visualization of the average hand strength of each possible hand in Texas Hold'em (which you'll have to do a short bit of research on first). Do not try to generate the trillions of hand combinations! Instead, to receive credit, you must use Monte Carlo techniques to estimate the percentages in each cell. Note that there are 52**2, or 2704 cells. If you use 3,700 trials per cell, that's a total of about 10 million trials, which will be slow but bearable, so we'll go with that. Also, try hovering over any individual cell in the chart on that page, and see how a popup box shows the data for that specific cell. Your program must do the same, using the class-based animation framework from this semester (though otherwise your program does not have to be object-oriented).

Bonus/Optional: bonusPolyaUrnVisualizer() [up to 5 pts] [manually graded]
Write the function bonusPolyaUrnVisualizer(), that takes no parameters and makes an interactive graphical visualization that uses Monte Carlo techniques to explore the expected outcomes in Polya's Urn (which you'll have to do a short bit of research on first) (and, yes, it's that Polya!). You must use Monte Carlo techniques and not compute the exact solutions, and you should use the class-based animation framework from this semester (though otherwise your program does not have to be object-oriented).