1. In your programming language of choice, simulate the monty hall problem 1000 times. Test it in the case you switch the door, and test in the case you do not switch the door. Include your code and the results.

2. Suppose there are two full bowls of cookies. Bowl 1 has 10 chocolate chip and 30 plain cookies, while Bowl 2 has 20 of each. Our friend Fred picks a bowl at random, and then picks a cookie at random. The cookie turns out to be a plain one. How probable is it that Fred picked it out of Bowl 1?

3. The blue M&M was introduced in 1995. Before then, the color mix in a bag of plain M&Ms was (30% Brown, 20% Yellow, 20% Red, 10% Green, 10% Orange, 10% Tan). Afterward it was (24% Blue , 20% Green, 16% Orange, 14% Yellow, 13% Red, 13% Brown). A friend of mine has two bags of M&Ms, and he tells me that one is from 1994 and one from 1996. He wonâ€™t tell me which is which, but he gives me one M&M from each bag. One is yellow and one is green. What is the probability that the yellow M&M came from the 1994 bag?

4. A test for a particular cancer has an error rate of 1% (false positive and false negative rate). Only 0.1% of the population has this type of cancer. You went to get tested, and your test result was positive. What is the probability that you have that particular type of cancer?

5. Speeds of functions of 'n'

a) T(n) below is the time it takes to perform an algorithm's operations on a data set in microseconds. Report the time in the shortest unit of time that is greater than 1. That is, instead of 1,000,000 seconds, you would report 1.65 weeks. Units can be microseconds, milliseconds, seconds, minutes, hours, days, weeks, months, or years. Assume log base 10.

Do this for T(n) = log n, n, n log n, n2, n3, 2n, n!

for 'n' is one item, one thousand items, one million items, and one billion items. Anything more than a century, feel free to just write something equivalent to 'more than a lifetime'

6. The following function below is recursive

public int recFunc (int n) {
if (n > 1) {
return (n + recFunc(n-2));
} else {
return (n);
}
}

a) What does this function compute?

b) Each call to the recFunc function requires O(1) space to hold the previous function call in memory. How much space (in Big O notation) does the whole program require when it runs. Explain. (hint: the answer is not O(1))?

7. Below are some functions for the number of seconds an algorithm takes to complete depending on the size of the data structure. What is the big-O for each?

• 7 log n + 4 n log (3 n) + 2 n
• 500 n^2 + 0.01 n log n
• 600 * log (5 n) + 0.00001 n2
• the time this loop takes: for (i = 0; i <= n; i += 1000)
• the time this loop takes: for (i = 1; i <= n; i *= 2)

8. What is the big-O for the following operations in an array of 'n' values?

• Finding an element in an array, when you know the index
• Finding an element in an unsorted array, without knowing the index
• Performing a binary search for a value in a sorted array.