代写COMPSCI编程、代做Java，c++语言程序、代做Python设计编程

日期：2020-12-10 10:12

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