Description

Warnings
– Please read the “Project 1” handout carefully
– Download your template project1.scm from DriveF@VOL/COURSES/UGRADS/COMP200/SHARE/[username]/project1/.
– Please do the necessary editing on your project1.scm and make sure your file loads without errors by using RUN (DrRacket) command. Only the files that are errorfree will be graded.
– Name of the submission file have to be project1.scm. If you need to make resubmission the format should be the following: project1 X.scm where X is the submission number. For example, if you want to resubmit your homework for a second time, the name of file should be project1 2.scm . Files that are named other than that will not be graded.
– Please upload your homework to the folder DriveF@VOL/COURSES/UGRADS/COMP200/HOMEWORK/[username]/project1/.
– In DrRacket please select the R5RS option from the language toolbar.

Reading Chapter 1 and Section 2.1 in Structure and Interpretation of Computer Programs

Help Please email comp200@ku.edu.tr if you have any questions.
Purpose
The purpose of this project is for you to gain experience with writing and testing relatively simple procedures. You should read the project submission instructions in the Assignments section of the course website to find out how to retrieve the project file and submit your solutions. For each problem below, include your code (with identification of the problem number being solved), as well as comments and explanations of your code, and demonstrate your code’s functionality against a set of test cases. On occasion, we may provide some example test cases, but you should always create and include your own additional, meaningful test cases to ensure that your code works not only on typical inputs, but also on more difficult cases. Get in the habit of writing and running these test cases after every procedure you write — no matter how trivial the procedure may seem to you.
Scenario
Alyssa I. Hackerkesen has just arrived in Cambridge, England, about to embark on a semester in the Cambridge exchange program. Suffering from severe culture shock, she is delighted to find that her favorite
1
candy, M&M’s, comes in a British variant, Smarties. Even better, she finds that Smarties come in a variety of colors (colours?), and that her favorite color, orange, is well represented. Thrilled by this unexpected turn of events, she decides that she needs to develop software in an effort to optimize the number of orange smarties she can consume over the next three months.
The key to this project will be to model the way that packets of Smarties are produced. Throughout the project, we’ll assume that each Smarties packet is produced by the manufacturer, in the following random process. Each Smarties packet will contain some number, n, of smarties (e.g., n = 100). The value for n will be chosen by Alyssa or the manufacturer. The colors of these n Smarties are then chosen at random. More specifically, the probability that a randomly chosen Smartie is orange is p, where p is some value between 0 and 1. If p is high, there’s a good chance that there will be a large number of orange Smarties in the packet. If p is low, there will a good chance that there will be very few Smarties that are orange, and Alyssa will be disappointed.
Problem 1: Some Simple Probability Theory
The first thing that Alyssa would like to do is model the probability of seeing exactly b orange Smarties in a Smarties packet. This probability will vary depending on the number of smarties in a packet, n, and the probability of any one Smartie being orange, p. In general, the probability of seeing exactly b smarties is
given by the following formula: 
b^{!} 
p^{b}(1 − p)^{n−b} 
bin(n, b, p) = 

n 
where ^{n}_{b} is defined as the binomial coefficient
!
n n!

^{=} (n − b)!b!
(This result comes from the binomial distribution, if you’re interested in reading more about this you can see http://mathworld.wolfram.com/BinomialDistribution.html.)
We want you to write a procedure that takes parameters n and b as input, and returns the binomial coefficient ^{n}_{b} in two different ways.
For the first method, you should be able to directly encode the formula above (i.e., write a procedure to compute factorial, and then use it to implement the formula):
(define factorial
(lambda (n)
YOURCODEHERE))
(define binomial
(lambda (n b)
YOURCODEHERE))
Test your code for at least the following cases:
(binomial 5 2) ; > 10
(binomial 10 5) ; > 252
As a second method, you can take advantage of properties of factorial. In particular,

b^{!}
=
(n
^{n!}_{b)!b!} =
b (b
^{−}1)
· · ·
(n
−
1
n
n (n
1)
b + 1)
−
−
Write a second version of binomial that uses this idea as its basis and does not use factorial:
(define binomial2
(lambda (n b)
YOURCODEHERE))
Test your code to show that binomial2 in fact gives the same answers as binomial.
Building on this code, write a procedure that takes parameters n, b, and p as input, and returns the probability that a packet of n smarties has exactly b orange smarties, given that p is the probability of any single Smartie being orange:
(define exactlybsmarties
(lambda (n b p)
YOURCODEHERE))
Test your code for at least the following cases (you should be able to calculate the later cases directly using a calculator, to verify that your code is producing the correct answer):
(exactlybsmarties 1 
1 0.5) 
; > 
0.5 

(exactlybsmarties 2 
1 0.5) 
; > 
0.5 

(exactlybsmarties 2 
2 0.5) 
; > 
0.25 

(exactlybsmarties 
2 
1 0.3) 
; 
> 

(exactlybsmarties 
10 2 0.3) 
; 
> 
Note that you might think about what checks you want to put into your code to ensure that it handles the right set of parameters. For example, what if b is greater than n?
Problem 2: More Probability Theory
Alyssa would now like to calculate the probability that there will be at least b orange smarties in a bag, given that it is generated with underlying parameters n and p. Note that the probability of seeing at least b orange smarties in a bag can be calculated as the probability of seeing exactly b orange smarties, plus the
probability of seeing exactly b + 1 orange smarties, and so on, up to seeing exactly n smarties. This can be captured mathematically as:
!
^{X}^{n} ^{n }_{p}r_{(1} _{−} _{p)}n−r
^{r}
which uses the summation notation
X^{n}
r=b
f (r) = f (b) + f (b + 1) + f (b + 2) + . . . + f (n)
which applies to any function f (r).
In other words, we’ve made use of the identity
P robability(at least b smarties) = P robability(exactly b smarties) +
P robability(exactly b + 1 smarties) +
P robability(exactly b + 2 smarties) +
. . .
P robability(exactly n smarties)
Making use of your code for exactlybsmarties, write code which takes as input parameters n, b, and p, and returns the probability that at least b orange Smarties are found in a bag:
(define atleastbsmarties
(lambda (n b p)
YOURCODEHERE))
Write your code in two different ways. In the first method, use a recursive process (i.e., rely on the fact that getting at least b smarties is the same as either getting exactly b smarties or getting at least b+1 smarties). In the second method, use an iterative process, while relying on your code to get exactly b smarties.
Test your code for at least the following cases:
(atleastbsmarties 9 5 0.5) 
; > 0.5 

(atleastbsmarties 19 
10 0.5) 
; > 0.5 

(atleastbsmarties 
10 
5 
0.6) 
; 
> 
(atleastbsmarties 
15 
5 
0.3) 
; 
> 
Problem 3: Choosing a Bag
Alyssa is now almost ready to go shopping for Smarties. To her delight, she finds that each Smarties bag has the parameters n and p printed on it; the values for n and p may vary bag by bag. A bag costs one pound (about 2 dollars), and she decides that a bag will be worth buying as long as there’s at least a 50% chance that it will have 8 or more orange Smarties.
Write a function goodbag which takes parameters n and p as input, and returns #t if the bag is worth buying, #f if it is not worth buying. Be careful of a special case, that if n < 8 there is no chance that the bag will have 8 or more Smarties.
(define goodbag
(lambda (n p)
YOURCODEHERE))
Test your code for at least the following cases:
(goodbag 7 
1) 
; > #f 
(goodbag 8 
1) 
; > #t 
(goodbag 8 
0.5) 
; > #f 
(goodbag 8 
0.99) 
; > #t 
(goodbag 16 0.5) 
; > 

(goodbag 16 0.7) 
; > 

(goodbag 16 0.4) 
; > 
Problem 4: Choosing a Value for p
After a couple of months in England, Alyssa has purchased so many bags of Smarties that she has the power to directly negotiate with the manufacturer. Whenever she wants a bag of Smarties, she can call up the company, which will produce a customized bag for her. They will tell her the number of Smarties, n, that will appear in the bag. You can assume that n will be at least 8. Alyssa then gets to choose a minimum value for the probability p. In particular, she wants to choose the minimum value of p such that the bag is a “good bag”, as defined in the previous problem.
Write a function minimump which takes a parameter n as input, and returns p, the minimum probability under which the bag will be acceptable to Alyssa. minimump should be a recursive procedure that tries different values for p ranging from 0 to 1, sampled at some specific increment size inc (i.e., tries p = 0, then p =inc, then p = 2 inc, and so on), and which makes use of goodbag. The value for the increment should be an additional parameter of the function, called inc:
(define minimump
(lambda (n inc)
YOURCODEHERE))
Test your code for the following case:
(minimump 12 0.01)
You should get a value of 0.63. To check that this is correct, what do you get for the following applications of goodbag?:
12 
0.63) 
; 
> 

(goodbag 
12 
( 0.63 0.01)) 
; 
> 
Now try
(minimump 12 0.1)
(minimump 12 0.01)
(minimump 12 0.001)
(minimump 12 0.0001)
(minimump 12 0.00001)
Create 3 other test cases that are similar to the case above.
Problem 5: Choosing p More Efficiently
Alyssa discovers that her code for calculating minimump (in Problem 4) is too slow; her telephone bill for calls to the company is becoming so big that she’s running out of money for Smarties. She decides to try to make a more efficient version of the function.
First, though, you should implement a new version of minimump which displays (or prints out) the number of times that goodbag is called by the recursive search procedure. Call this procedure minimumpnew. For example, it should show the following behavior:
(minimumpnew 12 0.01)
Number of calls to goodbag: 63
0.63000000000003
(The procedure returns the value 0.63 (roughly), and also displays or prints out 63, i.e., the number of times goodbag was called, which is ironically very similar in this case.) You may find the procedures newline (with no arguments), and display (with one argument) convenient – the former outputs a blank line, and the latter will print out the value of its argument on the screen.
Try the following test cases:
(minimumpnew 15 0.1)
(minimumpnew 15 0.01)
(minimumpnew 15 0.001)
(minimumpnew 15 0.0001)
(minimumpnew 15 0.00001)
Alyssa realises that there’s a more efficient way of calculating minimump. It is based on an idea called binary search. First, note that we know that the value for minimump is between 0 and 1. Suppose we try a value of 0.5 (halfway between). There are then two possible outcomes:

If a value of p = 0.5 gives a good bag, we know that the minimum value for p is between 0 and 0.5. We can then search this range of values, by recursing, and testing a value of p = 0.25.

If p = 0.5 does not give a good bag, we know the minimum value for p is between 0.5 and 1. We can then search this range of values, by recursing, and testing a value of p = 0.75.
To implement this procedure, fill in the following code:
(define minimumpbinary
(lambda (n inc)
(minimumpbinaryhelper n inc 0 1 0)))
(define minimumpbinaryhelper
(lambda (n inc a b count)
YOURCODEHERE))
The procedure (minimumpbinaryhelper n inc a b count) should implement binary search for the best value of p between a and b, up to a level of precision defined by inc. If (b − a) < inc, then it should just return b as its final answer. Otherwise, it should test whether a value for p = (a + b)/2 leads to a good or bad bag, and make a recursive call to minimumpbinaryhelper with new values of a and/or b which depend on this answer. It should also keep track (using count) of how many times goodbag is called.
Test your code on the following cases:
(minimumpbinary 12 0.1)
(minimumpbinary 12 0.01)
(minimumpbinary 12 0.001)
(minimumpbinary 12 0.0001)
(minimumpbinary 12 0.00001)
Your code should again print the number of times that goodbag is called when minimumpbinary is used. You should find that it calls goodbag far fewer times than the number of times used by minimumpnew, particularly when inc becomes small.
Problem 6: MonteCarlo Simulations
Unfortunately, the company has a change in management, and while still willing to customize bags for Alyssa, they are slightly less flexible. The company will only produce bags in batches of some size m (e.g., m = 8) that they choose. Furthermore, they will specify the parameters n and p which are used to generate all of the bags in a given batch. Alyssa now wants to build a function (estimategoodprobability

n p) which returns the probability that at least one bag out of the m bags she receives will be a “good bag”, where a “good bag” is as defined before.
This is a more difficult problem, and Alyssa decides to abandon her existing code (you should too: don’t use the code developed in the previous problems!). Instead, she decides to develop an approach based
on MonteCarlo methods. (See http://en.wikipedia.org/wiki/Monte Carlo method for an overview of the history of MonteCarlo methods. MonteCarlo methods have had widespread use since their invention, one notable case being in the development of the hydrogen bomb. But Alyssa is delighted that they finally have a serious application, i.e., in orangesmartieconsumptionoptimization.)
In the MonteCarlo method we develop, the central idea will be to build a simulator that randomly generates batches of bags of Smarties. We can then see how often a randomly generated batch contains at least one good bag; we can use this to estimate the probability of there being at least one good bag under parameters
m, n, b.
At the center of our approach is a function, random. Each time a call to (random 1.0) is made, it returns a value chosen uniformly at random from the interval between 0 and 1. Roughly speaking, this means that any real number between 0 and 1 will be returned with the same, equal probability. (Note that if you call random with an integer argument, it returns an integer selected uniformly at random from the integers between 0 and one less than the argument.)
Try calling (random 1.0) a few times in the readevalprint loop: you should find a random value between 0 and 1 returned each time.
The first function you should write is (cointoss p). This takes a parameter p which is between 0 and 1. With probability p it returns #t, with probability (1 − p) it returns #f:
(define cointoss
(lambda (p)
YOURCODEHERE))
Thus this is the simplest form of simulator: (cointoss p) simulates a coin being tossed that has probability p of turning up heads, and probability (1 −p) of turning up tails. It returns #t or #f for heads/tails respectively. (Hint: use (random 1.0) to generate a number between 0 and 1, and then test whether this number is ≥ p.)
Next, write a function randombag which takes parameters n and p as input. The function should generate a bag of Smarties of size n where each Smartie has probability p of being orange. It returns a single value, which is the number of Smarties in the bag which were orange.
(define randombag
(lambda (n p)
YOURCODEHERE))
Your code should make use of n calls to cointoss.
Next, write a function getmbags which takes parameters m, n and p as input. It should generate m bags at random using the parameters n and p, and return #t if at least one of these bags is good, i.e. has 8 or more orange smarties.
(define getmbags
(lambda (m n p)
YOURCODEHERE))
Finally, write code estimategoodprobability which takes parameters m, n, p and t as input. As before, m is the number of bags in a batch; n is the number of Smarties in a bag; and p is the probability of any individual Smartie being orange. The function should make t calls to getmbags, and return ^{g}_{t} as its estimate, where g is the number of times getmbags returns true.
(define estimategoodprobability
(lambda (m n p t)
YOURCODEHERE))
Give values that your code returns for the following cases:
(estimategoodprobability 24 12 0.5 1000)
(estimategoodprobability 24 16 0.5 1000)
(estimategoodprobability 24 16 0.3 1000)
(estimategoodprobability 24 16 0.2 1000)
Note: you should report numbers for 3 runs of each case. Note that because the procedure makes use of random sampling, you’ll almost certainly get slightly different answers in different runs with the same parameter values!
Problem 7: MonteCarlo Again
Now write a new MonteCarlo simulator for the following scenario. The company will again produce bags in batches of some size m that they choose; each bag will again have n Smarties. With probability p, each individual Smartie will be orange; with probability q, it will be blue; with probability 1 − p − q it will be some other color. Alyssa dislikes blue Smarties with a vengeance, and now defines a good bag to be any bag which has more than half of the smarties of orange color and less than onefifth of the smarties of blue color. Alyssa now wants to build a function (estimategoodprobability2 m n p q

which returns the probability that at least one bag out of the m bags she receives will be a “good bag”, where a “good bag” now has the new definition. As before, t is a parameter specifying the number of batches which are generated at random during the MonteCarlo simulation.
Hint: use the same logic to build up your solution as you did in problem 6. Note however that your solution may require new functions, or may require substantially new versions of the functions in problem 6.