STAT40780 Data Programming with C (online)
STAT代写 | c++作业 | C语言代写 | Algorithm代做 | assignment | 作业lab – 这是一个关于Algorithm的题目, 主要考察了关于Algorithm的内容,是一个比较经典的题目, 是比较有代表性的c++/Algorithm等代写方向, 这个项目是lab代写的代写题目
STAT40780 Data Programming with C (online)
Dr James Herterich
Assignment
Notes: There are two questions on this assignment. The second requires you to have considered lab 8 in the course material. This assignment is worth 20% of the total grade. Ensure your code is well-commented. You will be penalized for submitting code that is not well-commented. Only the following files should be submitted:
- Any .cpp files that form part of your solutions
- A single R script file named in the format YourNameassignment.R containing all of the R code required for this assignment (submit a single R script only!)
- A single pdf document containing any other required information (e.g. de- scriptions of code implementations), named in the format YourNameassignment.pdf.
Any additional files you submit will not be graded.
1 Root-finding algorithms
A root of a functiong()is a solution to the equationg() = 0. Root-finding is an im- portant computational problem that arises commonly across many disciplines. For example, in statistics, root-finding can be used in maximum likelihood estimation. Here you are required to find a maximum likelihood estimate for the Cauchy distri- bution with the help of root-finding algorithms implemented in c++ with Rcpp.
The Cauchy distribution with unknown location parameterand scale parameter set to= 1is a continuous probability distribution, with density function:
pdf(x) =
1
[1 + (x+)^2 ]
, xR. (1)
Fornindependent observationsx 1 ,x 2 ,…,xnfrom this Cauchy distribution, the log likelihood is calculated as:
l(x) =nlog
n
i=
log
[
1 + (xi)^2
]
. (2)
Consider the following numeric vector in R storing observations generated from a Cauchy distribution with location parameterand scale parameter= 1:
1 x < c ( 1 2. 2 6 2 3 0 7 , 1 0. 2 8 1 0 7 8 , 1 0. 2 8 7 0 9 0 , 1 2. 7 3 4 0 3 9 , 2 1 1. 7 3 1 8 8 1 , 8. 8 6 1 9 9 8 , 1 2. 2 4 6 5 0 9 , 1 1. 2 4 4 8 1 8 , 3 9. 6 9 6 2 7 8 , 1 1. 5 5 7 5 7 2 , 1 1. 1 1 2 5 3 1 , 1 0. 5 5 0 1 9 0 , 4 9. 0 1 8 4 3 8 , 1 0. 7 0 4 7 7 4 , 9. 5 1 5 6 1 7 , 1 0. 0 0 3 2 4 7 , 5 1 0. 2 7 8 3 5 2 , 9. 7 0 9 6 3 0 , 1 0. 9 6 3 9 0 5 , 1 7. 3 1 4 8 1 4 )
A researcher wishes to estimate the maximum likelihood estimatefor the Cauchy
distribution from which the data inxwere generated.
A maximum likelihood estimate forcan be found by differentiating the log like-
lihood, equating to zero, and solving fori.e. we can find a maximum likelihood
estimate for the above Cauchy distribution by finding a root ofl(), the first deriva-
tive of the log likelihood. Taking the first derivative and equating to zero, gives the
following equation
l() = 2
n
i=
xi
1 + (xi)^2
= 0. (3)
A maximum likelihood estimate can be obtained by solving the equationl() = 0for
i.e. by finding a root of the functionl(). There are several numerical optimization
algorithms available for finding the roots of continuous univariate functions such as
l(), including the:
- Bisection method
- Newtons method
- Secant Method For this assignment, implement each of the above three root finding algorithms in C++ with Rcpp, to find the MLE offor the datax. You will need to research the Algorithm for each method. They are widely avail- able from any online search or within the accompanying PDF (with pseudo-code). Call each functionbisectRcpp,newtonRcpp, andsecantRcpp, respectively. The function calls (from a wrapper using a cxxfunction) should take the form: bisectRcpp(x,a=,b=,n=1000,tol=0.00000001) newtonRcpp(x, b=,n=100 ,tol=0.00000001) secantRcpp(x,a=,b=*,n=1000,tol=0.00000001) whereaandbrepresent initial values for the algorithms,nis the number of itera- tions in your algorithm, andtolis the tolerance – the level of accuracy for terminat- ing beforenis reached.
- Each function should take the vectorxas input from R (along with any other required inputs), and return the maximum likelihood estimateto R.
- Ensure that all code submitted is well commented
- Briefly describe each implementation in your submitted pdf document. This must be self-contained, i.e. do not refer to your commented code.
- Evaluate and discuss the behaviour of each implemention with different start- ing values. Consider the following: bisectRcpp (a,b)= {(9,11), (0,30), (-10,50), (15,50)} newtonRcpp b= {11, 9, 13} secantRcpp (a,b)= {(10,12), (7,12), (8,13), (8,14)} where some will work and others will fail.
- Benchmark your implementations against each other by the following: 1 # Benchmark the implementations against each other 2 benchmark ( b i s e c t R c p p ( x , a =9 , b=11 , n =1000 , t o l = 0. 0 0 0 0 0 0 0 1 ) , 3 s e c a n t R c p p ( x , a = 8 , b = 1 1 , n = 1 0 0 0 , t o l = 0. 0 0 0 0 0 0 0 1 ) , 4 newtonRcpp ( x , b = 1 1 , n=100 , t o l = 0. 0 0 0 0 0 0 0 1 ) , 5 o r d e r = r e l a t i v e )
- Discuss their advantages and limitations. Comment on the suitability and ef- ficiency of each implementation.
Note: the second derivative of the log likelihood is:
l() = 2
n
i=
(xi)^2 1
(1 + (xi)^2 )^2
. (4)
2 Welfords variance algorithm with Rcpp – with miss-
ing values
Modify Welfords variance algorithm (Lab 8) such that it can handle missing values.