辅导COMPSCI编程、讲解Java，c++语言程序、讲解Python设计编程
解析R语言编程|辅导R语言程序
COMPSCI 1JC3 C01
Introduction to Computational Thinking
Fall 2020
Assignment 5
The purpose of Assignment 5 is implement a practical higher-order function.
The requirements for Assignment 5 and for Assignment 5 Extra Credit
are given below. You are required to do Assignment 5, but Assignment 5 Extra
Credit is optional. Please submit Assignment 5 as two files, Assign 5.hs
and Assign 5 Test.hs, to the Assignment 5 folder on Avenue under Assessments/Assignments.
If you choose to do Assignment 5 Extra Credit for extra
marks, please submit it also as two files, Assign 5 ExtraCredit.hs and
Assign 5 Test ExtraCredit.hs, to the Assignment 5 Extra Credit folder
on Avenue in the same place. Both Assignment 5 and Assignment 5 Extra
Credit is due December 13, 2020 before midnight. Assignment 5 is
worth 4% of your final grade, while Assignment 5 Extra Credit is worth 2
extra percentage points.
Late submissions will not be accepted! So it is suggested that you
submit preliminary Assign 5.hs and Assign 5 Test.hs files well before the
deadline so that your mark is not zero if, e.g., your computer fails at 11:50
PM on December 13.
Although you are allowed to receive help from the instructional
staff and other students, your submitted program must be your
own work. Copying will be treated as academic dishonesty!
1 Background
Using the trapezoidal rule,
is the area of a trapezoid that approximates the area under the graph of f
from xi−1 to xi
. The approximation becomes more accurate as the parameter
n increases in value.
2 Assignment 5
The purpose of this assignment is to create a Haskell module for approximating
the definite integral of a function f : R → R.
2.1 Requirements
1. Download from Avenue Assign5 Project Template.zip which contains
the Stack project files for this assignment. Modify the
Assign 5.hs file in the src folder so that the following requirements
are satisfied. Also put your testing code for this assignment in the
Assign 5 Test.hs file in the test folder.
2. Your name, the date, and “Assignment 5” are in comments at the top
of your file. macid is defined to be your MacID.
3. The file includes a function definiteIntegral of type
Double -> Double -> (Double -> Double) -> Integer -> Double
4. The file includes a function arcsin1 of type Integer -> Double such
using the definiteIntegral function with n partitions.
2
5. The file includes a function piApprox of type Double -> Double that
uses arcsin1 to approximate π where piApprox tol returns a value
pi’ such that
|pi’ − pi| ≤ tol
for the built-in Haskell approximation pi (this should be manageable
for tol ≥ 10−5
).
6. The file includes a function logApprox of type
Double -> Double -> Double such that logApprox x tol approximates
the value of log x by exploiting its definition as a definite
integral, i.e.,
Use the definiteIntegral function, and return the approximation
that uses the smallest number of partitions n such that
|(definiteIntegral 1 x g n)−(definiteIntegral 1 x g (n-1))| ≤ tol.
7. Your file can be imported into GHCi and all of your functions perform
correctly.
2.2 Testing
Include in your file a test plan for all four functions mentioned above. The
test plan must include at least three test cases for each function. Each test
case should have following form:
Function: Name of the function being tested.
Test Case Number: The number of the test case.
Input: Inputs for function.
Expected Output: Expected output for the function.
Actual Output: Actual output for the function.
In addition, your test plan must include at least one QuickCheck case
for each of the four functions. Each QuickCheck case should have following
form:
Function: Name of the function being tested.
Property: Code defining the property to be tested by QuickCheck.
Actual Test Result: Pass or Fail.
The test plan should be at the bottom of your file in a comment region
beginning with a {- line and ending with a -} line. Put your testing code
for this assignment in the Assign 5 Test.hs file in the test folder.
3
3 Background Extra Credit
Monte-Carlo Integration is a technique for computing approximations of
definite integrals relying on random number generation. Recall, a definite
integral
Z b
a
f(x) dx
is the area between the curve of f(x) and the x-axis over the domain a ≤
x ≤ b. Monte-Carlo Integration relies on approximating this area as a ratio
of the area of the smallest rectangle that can encapsulate the curve over
the given domain. Approximating the ratio of this rectangle is done by
generating random sampling points within the rectangle, and counting the
number of points inside the curve (hits) vs the number of points outside of
the curve (misses).
More formally, given a hit function H(x, y), a number of samples N
and a set of randomly generated samples {(xi
, yi) · i ← {1..N}},
Figure 1: Example Sampling of a Quarter Unit Circle
As an example, consider computing the area of the unit circle (circle of
radius 1). To simplify the problem, we’ll compute only the positive/upperright
quadrant. Given the circle has radius 1, the area of the encapsulating
rectangle is 1 × 1 = 1.
Figure 1 shows an example sampling of the unit circle, where hits/misses
are denoted by red/black dots respectively. After simplifying the area of the
4
rectangle to 1,
Generally, a uniform distribution is the simplest distribution to sample
from. However sometimes a different distribution such as the normal
distribution is more appropriate. The Box-Muller transform can be used
to take two uniform distribution samples U1 and U2 on the unit interval
(0, 1) and return a point (Z1, Z2) from a standard normal distribution,
where
Z0 = Rcos(θ) = p
−2lnU1cos(2πU2)
Z1 = Rsin(θ) = p
−2lnU1sin(2πU2)
4 Assignment 5 Extra Credit
The purpose of this assignment is to create a Haskell module for approximating
the definite integral of a function f : R → R in
4.1 Requirements
1. Download from Avenue Assign5 Project Template.zip which contains
the Stack project files for this assignment. Modify the
Assign 5.hs file in the src folder so that the following requirements
are satisfied. Also put your testing code for this assignment in the
Assign 5 Test.hs file in the test folder.
2. Your name, the date, and “Assignment 5” are in comments at the top
of your file. macid is defined to be your MacID.
3. The file includes a function uniformSample2D of type
(Random a,Floating a) => IO (a,a)
that returns a random uniformly distributed point in the IO monad
over the unit interval (0, 1). Hint: the function randomRIO from the
System.Random library returns a single uniformly distributed random
sample. See documentation for System.Random here http://
hackage.haskell.org/package/random-1.1/docs/System-Random.
html)
4. The file includes a function uniformToNorm of type
Floating a => a -> a -> (a,a)
that takes two uniformly distributed samples and transforms them to
a normally distributed sample point using the Box Muller transform
5
5. The file includes a function normalSample2D of type
(Random a, Floating a) => IO (a,a)
that returns a random normally distributed point in the IO monad
voer the unit interval (0, 1)
6. The file includes a function genSamples of type
(Random a, Floating a) => IO (a,a) -> Int -> IO [(a,a)]
that takes a sampling function (i.e uniformSample2D or normalSample2D),
an Integer N and generates a list of N randomly generated samples in
the IO monad
7. The file includes a function monteCarlo2D of type
Floating a => a -> a -> [(a,a)] -> ((a,a) -> Bool) -> a
that (assuming your working in the upper-right positive quadrant of
a coordinate plane) takes xM ax such that the domain of the definite
integral is (0, xM ax), a value yM ax that’s assumed to be the maximum
value of the function over the domain it’s being integrated, a list
of samples and a boolean hit function and returns the Monte-Carlo
Integration approximation.
8. The file includes a function unitCircleHit of type
(Floating a,Ord a) => (a,a) -> Bool
that is the hit function for the unit circle (Hint: H(x, y) as defined in
Section Background)
9. The file includes a function estimatePi of type
IO (Double,Double) -> Int -> IO Double
that uses Monte-Carlo Integration to estimate the value of pi. It takes
a sampling function (i.e uniformSample2D or normalSample2D) and
an Integer N of number of samples to take.Note: the value of pie is the
area of the unit circle (or 4 times the area of the first quadrant of the
unit circle). A uniform distribution should yield a good guess of π at a
sufficiently high N. Interestingly, a normal distribution will generally
half the number hits in the first quadrant, giving a good guess for π
2
10. Your file can be imported into GHCi and all of your functions perform
correctly.
6
4.2 Testing
Include in your file a test plan for uniformSample2D, uniformToNorm,
normalSample2D, genSamples, unitCircleHit. The test plan must should
thoroughly cover critical all critical cases per function. Functions returning
random values need not have specific output listed (i.e can specify range,
property like normally distributed in Expected Output). Each test case
should have following form:
Function: Name of the function being tested.
Test Case Number: The number of the test case.
Input: Inputs for function.
Expected Output: Expected output for the function.
Actual Output: Actual output for the function.
In addition, your test plan must include at least one QuickCheck case
for uniformToNorm and unitCircleHit. Each QuickCheck case should have
following form:
Function: Name of the function being tested.
Property: Code defining the property to be tested by QuickCheck.
Actual Test Result: Pass or Fail.
The test plan should be at the bottom of your file in a comment region
beginning with a {- line and ending with a -} line. Put your testing code
for this assignment in the Assign 5 Test.hs file in the test folder.
7