Problem 3
(a) Explain how k-fold cross-validation is
implemented.
- K-fold cross-validation works by randomly dividing the full data set
into k roughly equal-sized folds. The model is then fit k times, each
time using k-1 folds as the training data and the remaining fold as the
validation set. The test error is estimated by averaging the k
validation errors together.
(b) What are the advantages and disadvantages of k-fold
cross-validation relative to:
i. The validation set approach?
- K-fold CV has two big advantages over the validation set approach:
it makes use of more data for training (since most observations are used
for fitting in each fold), and it produces a less variable test error
estimate because the result is averaged over k splits rather than a
single one. The downside is that it takes longer to compute since the
model must be fir k times instead of once.
ii. LOOCV?
- Compared to LOOCV, k-fold CV is much faster to compute because it
fits the model one k times instead of once for every observation. It may
have slightly more bias than LOOKV, but it often produces a more stable
estimate of the test error.
Problem 5
(a) Fit a logistic regression model that uses income and
balance to predict default.
library(ISLR2)
set.seed(42)
glm_default <- glm(default ~ income + balance, data = Default, family = binomial)
summary(glm_default)
Call:
glm(formula = default ~ income + balance, family = binomial,
data = Default)
Coefficients:
Estimate Std. Error z value Pr(>|z|)
(Intercept) -1.154e+01 4.348e-01 -26.545 < 2e-16 ***
income 2.081e-05 4.985e-06 4.174 2.99e-05 ***
balance 5.647e-03 2.274e-04 24.836 < 2e-16 ***
---
Signif. codes: 0 ‘***’ 0.001 ‘**’ 0.01 ‘*’ 0.05 ‘.’ 0.1 ‘ ’ 1
(Dispersion parameter for binomial family taken to be 1)
Null deviance: 2920.6 on 9999 degrees of freedom
Residual deviance: 1579.0 on 9997 degrees of freedom
AIC: 1585
Number of Fisher Scoring iterations: 8
(b) Using the validation set approach, estimate the test
error of this model.
set.seed(42)
# i. Split into training and validation sets
n <- nrow(Default)
train_idx <- sample(n, n / 2)
default_train <- Default[train_idx, ]
default_val <- Default[-train_idx, ]
# ii. Fit logistic regression on training set only
glm_train <- glm(default ~ income + balance, data = default_train, family = binomial)
# iii. Predict default status on validation set
val_probs <- predict(glm_train, default_val, type = "response")
val_pred <- ifelse(val_probs > 0.5, "Yes", "No")
# iv. Compute validation set error
mean(val_pred != default_val$default)
[1] 0.026
- The validation set error is approximately 2.6%, meaning the logistic
regression model incorrectly classifies about 2.6% of the observations
in the validation set.
(c) Repeat the process in (b) three times, using three
different splits of the observations into a training set and a
validation set. Comment on the results obtained.
set.seed(1)
n <- nrow(Default)
train_idx <- sample(n, n / 2)
default_train <- Default[train_idx, ]
default_val <- Default[-train_idx, ]
# ii. Fit logistic regression on training set only
glm_train <- glm(default ~ income + balance, data = default_train, family = binomial)
# iii. Predict default status on validation set
val_probs <- predict(glm_train, default_val, type = "response")
val_pred <- ifelse(val_probs > 0.5, "Yes", "No")
mean(val_pred != default_val$default)
[1] 0.0254
set.seed(2)
n <- nrow(Default)
train_idx <- sample(n, n / 2)
default_train <- Default[train_idx, ]
default_val <- Default[-train_idx, ]
# ii. Fit logistic regression on training set only
glm_train <- glm(default ~ income + balance, data = default_train, family = binomial)
# iii. Predict default status on validation set
val_probs <- predict(glm_train, default_val, type = "response")
val_pred <- ifelse(val_probs > 0.5, "Yes", "No")
# iv. Compute validation set error
mean(val_pred != default_val$default)
[1] 0.0238
set.seed(3)
n <- nrow(Default)
train_idx <- sample(n, n / 2)
default_train <- Default[train_idx, ]
default_val <- Default[-train_idx, ]
# ii. Fit logistic regression on training set only
glm_train <- glm(default ~ income + balance, data = default_train, family = binomial)
# iii. Predict default status on validation set
val_probs <- predict(glm_train, default_val, type = "response")
val_pred <- ifelse(val_probs > 0.5, "Yes", "No")
# iv. Compute validation set error
mean(val_pred != default_val$default)
[1] 0.0264
- The validation error ranged from about 2.3% to 2.8% across the three
splits. This shows that the validation set approach can produce slightly
different test error estimates depending on how the data are split.
(d) Now consider a logistic regression model that predicts
the probability of default using income, balance, and a dummy variable
for student. Estimate the test error for this model using the validation
set approach. Comment on whether or not including a dummy variable for
student leads to a reduction in the test error rate.
set.seed(42)
train_idx_d <- sample(n, n / 2)
glm_student <- glm(default ~ income + balance + student,
data = Default[train_idx_d, ], family = binomial)
probs_student <- predict(glm_student, Default[-train_idx_d, ], type = "response")
pred_student <- ifelse(probs_student > 0.5, "Yes", "No")
mean(pred_student != Default[-train_idx_d, ]$default)
[1] 0.0258
- Adding the student dummy variable does not reduce the test error by
much, it remains around 2.6%, essentially the same as the model without
student. This suggests that student status does not add significant
predictive power for default.
Problem 6
(a) Using the summary() and glm() functions, determine the
estimated standard errors for the coefficients associated with income
and balance in a multiple logistic regression model that uses both
predictors.
set.seed(42)
glm_se <- glm(default ~ income + balance, data = Default, family = binomial)
summary(glm_se)$coefficients
Estimate Std. Error z value Pr(>|z|)
(Intercept) -1.154047e+01 4.347564e-01 -26.544680 2.958355e-155
income 2.080898e-05 4.985167e-06 4.174178 2.990638e-05
balance 5.647103e-03 2.273731e-04 24.836280 3.638120e-136
(b) Write a function, boot.fn(), that takes as input the
Default data set as well as an index of the observations, and that
outputs the coefficient estimates for income and balance in the multiple
logistic regression model.
boot.fn <- function(data, index) {
fit <- glm(default ~ income + balance, data = data, family = binomial, subset = index)
coef(fit)[c("income", "balance")]
}
# Test on full data
boot.fn(Default, 1:nrow(Default))
income balance
2.080898e-05 5.647103e-03
(c) Use the boot() function together with your boot.fn()
function to estimate the standard errors of the logistic regression
coefficients for income and balance.
library(boot)
set.seed(42)
boot(Default, boot.fn, R = 1000)
ORDINARY NONPARAMETRIC BOOTSTRAP
Call:
boot(data = Default, statistic = boot.fn, R = 1000)
Bootstrap Statistics :
original bias std. error
t1* 2.080898e-05 2.737444e-08 5.073444e-06
t2* 5.647103e-03 1.176249e-05 2.299133e-04
(d) Comment on the estimated standard errors obtained using
the glm() function and using your bootstrap function.
- The standard errors from the bootstrap method are very similar to
those from glm(). This suggests that the estimates are consistent, and
either method provides similar results for this data set.
Problem 9
(a) Based on this data set, provide an estimate for the
population mean of medv. Call this estimate µ̂.
library(ISLR2)
mu_hat <- mean(Boston$medv)
print(mu_hat)
[1] 22.53281
- The estimated population mean of
medv is approximately
22.53, meaning the average median home value across Boston is about
$22,530.
(b) Provide an estimate of the standard error of µ̂. Interpret
this result.
se_hat <- sd(Boston$medv) / sqrt(nrow(Boston))
print(se_hat)
[1] 0.4088611
- The estimated standard error of µ̂ is approximately 0.409. This means
that the sample mean of
medv would typically vary by
about.409 from the true population mean if we repeatedly took random
samples from the population.
(c) Now estimate the standard error of µ̂ using the bootstrap.
How does this compare to your answer from (b)?
library(boot)
mean.fn <- function(data, index) {
mean(data$medv[index])
}
set.seed(42)
boot_result <- boot(Boston, mean.fn, R = 1000)
boot_result
ORDINARY NONPARAMETRIC BOOTSTRAP
Call:
boot(data = Boston, statistic = mean.fn, R = 1000)
Bootstrap Statistics :
original bias std. error
t1* 22.53281 0.02671186 0.4009216
- The bootstrap standard error is very close to the estimate from part
(b), with both values being about 0.41. This suggests that both methods
give similar estimates of the standard error.
(d) Based on your bootstrap estimate from (c), provide a 95%
confidence interval for the mean of medv. Compare it to the results
obtained using t.test(Boston$medv).
ci_lower <- mu_hat - 2 * sd(boot_result$t)
ci_upper <- mu_hat + 2 * sd(boot_result$t)
# t.test CI
t.test(Boston$medv)
One Sample t-test
data: Boston$medv
t = 55.111, df = 505, p-value < 2.2e-16
alternative hypothesis: true mean is not equal to 0
95 percent confidence interval:
21.72953 23.33608
sample estimates:
mean of x
22.53281
- The bootstrap 95% confidence interval for the mean of
medv is approximately [21.73, 23.34], which is very similar
to the interval produced by t.test(). This suggests that
both methods give similar estimates for the true population mean.
(e) Based on this data set, provide an estimate,
µ̂_med, for the median value of medv in the
population.
mu_med <- median(Boston$medv)
print(mu_med)
[1] 21.2
- The estimated population median of
medv is 21.2,
meaning half of Boston has a median home value below $21,200.
(f) We now would like to estimate the standard error of
µ̂_med. Estimate the standard error of the median using the
bootstrap. Comment on your findings.
median.fn <- function(data, index) {
median(data$medv[index])
}
set.seed(42)
boot_median <- boot(Boston, median.fn, R = 1000)
boot_median
ORDINARY NONPARAMETRIC BOOTSTRAP
Call:
boot(data = Boston, statistic = median.fn, R = 1000)
Bootstrap Statistics :
original bias std. error
t1* 21.2 0.0106 0.3661785
- The bootstrap standard error of the median is approximately 0.38,
which is similar to the standard error of the mean. This suggests that
both the sample mean and sample median are fairly stable estimates for
this data set.
(g) Based on this data set, provide an estimate for the tenth
percentile of medv in Boston census tracts. Call this quantity
µ̂_0.1.
mu_10 <- quantile(Boston$medv, 0.10)
print(mu_10)
10%
12.75
- The estimated tenth percentile of
medv is 12.75,
meaning that approx 10% of census tracts have a median home value at or
below $12,750.
(h) Use the bootstrap to estimate the standard error of
µ̂_0.1. Comment on your findings.
percentile10.fn <- function(data, index) {
quantile(data$medv[index], 0.10)
}
set.seed(1)
boot_p10 <- boot(Boston, percentile10.fn, R = 1000)
boot_p10
ORDINARY NONPARAMETRIC BOOTSTRAP
Call:
boot(data = Boston, statistic = percentile10.fn, R = 1000)
Bootstrap Statistics :
original bias std. error
t1* 12.75 0.0339 0.4767526
- The bootstrap estimated the standard error of th e10th percentile to
be approx .50. This is slightly larger than the standard errors for the
mean and median, suggesting that the 10th percentile is more variable
from sample to sample.
LS0tDQp0aXRsZTogIkFzc2lnbm1lbnQ0Ig0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIyMjIFByb2JsZW0gMw0KDQoNCl9fKGEpIEV4cGxhaW4gaG93IGstZm9sZCBjcm9zcy12YWxpZGF0aW9uIGlzIGltcGxlbWVudGVkLl9fDQoNCiAgLSBLLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiB3b3JrcyBieSByYW5kb21seSBkaXZpZGluZyB0aGUgZnVsbCBkYXRhIHNldCBpbnRvIGsgcm91Z2hseSBlcXVhbC1zaXplZCBmb2xkcy4gVGhlIG1vZGVsIGlzIHRoZW4gZml0IGsgdGltZXMsIGVhY2ggdGltZSB1c2luZyBrLTEgZm9sZHMgYXMgdGhlIHRyYWluaW5nIGRhdGEgYW5kIHRoZSByZW1haW5pbmcgZm9sZCBhcyB0aGUgdmFsaWRhdGlvbiBzZXQuIFRoZSB0ZXN0IGVycm9yIGlzIGVzdGltYXRlZCBieSBhdmVyYWdpbmcgdGhlIGsgdmFsaWRhdGlvbiBlcnJvcnMgdG9nZXRoZXIuIA0KICANCl9fKGIpIFdoYXQgYXJlIHRoZSBhZHZhbnRhZ2VzIGFuZCBkaXNhZHZhbnRhZ2VzIG9mIGstZm9sZCBjcm9zcy12YWxpZGF0aW9uIHJlbGF0aXZlIHRvOl9fDQoNCiAgX19pLiBUaGUgdmFsaWRhdGlvbiBzZXQgYXBwcm9hY2g/X18NCg0KICAtIEstZm9sZCBDViBoYXMgdHdvIGJpZyBhZHZhbnRhZ2VzIG92ZXIgdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoOiBpdCBtYWtlcyB1c2Ugb2YgbW9yZSBkYXRhIGZvciB0cmFpbmluZyAoc2luY2UgbW9zdCBvYnNlcnZhdGlvbnMgYXJlIHVzZWQgZm9yIGZpdHRpbmcgaW4gZWFjaCBmb2xkKSwgYW5kIGl0IHByb2R1Y2VzIGEgbGVzcyB2YXJpYWJsZSB0ZXN0IGVycm9yIGVzdGltYXRlIGJlY2F1c2UgdGhlIHJlc3VsdCBpcyBhdmVyYWdlZCBvdmVyIGsgc3BsaXRzIHJhdGhlciB0aGFuIGEgc2luZ2xlIG9uZS4gVGhlIGRvd25zaWRlIGlzIHRoYXQgaXQgdGFrZXMgbG9uZ2VyIHRvIGNvbXB1dGUgc2luY2UgdGhlIG1vZGVsIG11c3QgYmUgZmlyIGsgdGltZXMgaW5zdGVhZCBvZiBvbmNlLg0KDQogIF9faWkuIExPT0NWP19fDQoNCiAgLSBDb21wYXJlZCB0byBMT09DViwgay1mb2xkIENWIGlzIG11Y2ggZmFzdGVyIHRvIGNvbXB1dGUgYmVjYXVzZSBpdCBmaXRzIHRoZSBtb2RlbCBvbmUgayB0aW1lcyBpbnN0ZWFkIG9mIG9uY2UgZm9yIGV2ZXJ5IG9ic2VydmF0aW9uLiBJdCBtYXkgaGF2ZSBzbGlnaHRseSBtb3JlIGJpYXMgdGhhbiBMT09LViwgYnV0IGl0IG9mdGVuIHByb2R1Y2VzIGEgbW9yZSBzdGFibGUgZXN0aW1hdGUgb2YgdGhlIHRlc3QgZXJyb3IuDQoNCi0tLQ0KDQojIyMgUHJvYmxlbSA1DQoNCl9fKGEpIEZpdCBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgdGhhdCB1c2VzIGluY29tZSBhbmQgYmFsYW5jZSB0byBwcmVkaWN0IGRlZmF1bHQuX18NCmBgYHtyfQ0KbGlicmFyeShJU0xSMikNCnNldC5zZWVkKDQyKQ0KDQpnbG1fZGVmYXVsdCA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBEZWZhdWx0LCBmYW1pbHkgPSBiaW5vbWlhbCkNCnN1bW1hcnkoZ2xtX2RlZmF1bHQpDQpgYGANCg0KX18oYikgVXNpbmcgdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoLCBlc3RpbWF0ZSB0aGUgdGVzdCBlcnJvciBvZiB0aGlzIG1vZGVsLl9fDQpgYGB7cn0NCnNldC5zZWVkKDQyKQ0KDQojIGkuIFNwbGl0IGludG8gdHJhaW5pbmcgYW5kIHZhbGlkYXRpb24gc2V0cw0KbiA8LSBucm93KERlZmF1bHQpDQp0cmFpbl9pZHggPC0gc2FtcGxlKG4sIG4gLyAyKQ0KZGVmYXVsdF90cmFpbiA8LSBEZWZhdWx0W3RyYWluX2lkeCwgXQ0KZGVmYXVsdF92YWwgICA8LSBEZWZhdWx0Wy10cmFpbl9pZHgsIF0NCg0KIyBpaS4gRml0IGxvZ2lzdGljIHJlZ3Jlc3Npb24gb24gdHJhaW5pbmcgc2V0IG9ubHkNCmdsbV90cmFpbiA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBkZWZhdWx0X3RyYWluLCBmYW1pbHkgPSBiaW5vbWlhbCkNCg0KIyBpaWkuIFByZWRpY3QgZGVmYXVsdCBzdGF0dXMgb24gdmFsaWRhdGlvbiBzZXQNCnZhbF9wcm9icyA8LSBwcmVkaWN0KGdsbV90cmFpbiwgZGVmYXVsdF92YWwsIHR5cGUgPSAicmVzcG9uc2UiKQ0KdmFsX3ByZWQgIDwtIGlmZWxzZSh2YWxfcHJvYnMgPiAwLjUsICJZZXMiLCAiTm8iKQ0KDQojIGl2LiBDb21wdXRlIHZhbGlkYXRpb24gc2V0IGVycm9yDQptZWFuKHZhbF9wcmVkICE9IGRlZmF1bHRfdmFsJGRlZmF1bHQpDQoNCmBgYA0KDQogIC0gVGhlIHZhbGlkYXRpb24gc2V0IGVycm9yIGlzIGFwcHJveGltYXRlbHkgMi42JSwgbWVhbmluZyB0aGUgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCBpbmNvcnJlY3RseSBjbGFzc2lmaWVzIGFib3V0IDIuNiUgb2YgdGhlIG9ic2VydmF0aW9ucyBpbiB0aGUgdmFsaWRhdGlvbiBzZXQuDQoNCl9fKGMpIFJlcGVhdCB0aGUgcHJvY2VzcyBpbiAoYikgdGhyZWUgdGltZXMsIHVzaW5nIHRocmVlIGRpZmZlcmVudCBzcGxpdHMgb2YgdGhlIG9ic2VydmF0aW9ucyBpbnRvIGEgdHJhaW5pbmcgc2V0IGFuZCBhIHZhbGlkYXRpb24gc2V0LiBDb21tZW50IG9uIHRoZSByZXN1bHRzIG9idGFpbmVkLl9fDQpgYGB7cn0NCnNldC5zZWVkKDEpDQpuIDwtIG5yb3coRGVmYXVsdCkNCnRyYWluX2lkeCA8LSBzYW1wbGUobiwgbiAvIDIpDQpkZWZhdWx0X3RyYWluIDwtIERlZmF1bHRbdHJhaW5faWR4LCBdDQpkZWZhdWx0X3ZhbCAgIDwtIERlZmF1bHRbLXRyYWluX2lkeCwgXQ0KDQojIGlpLiBGaXQgbG9naXN0aWMgcmVncmVzc2lvbiBvbiB0cmFpbmluZyBzZXQgb25seQ0KZ2xtX3RyYWluIDwtIGdsbShkZWZhdWx0IH4gaW5jb21lICsgYmFsYW5jZSwgZGF0YSA9IGRlZmF1bHRfdHJhaW4sIGZhbWlseSA9IGJpbm9taWFsKQ0KDQojIGlpaS4gUHJlZGljdCBkZWZhdWx0IHN0YXR1cyBvbiB2YWxpZGF0aW9uIHNldA0KdmFsX3Byb2JzIDwtIHByZWRpY3QoZ2xtX3RyYWluLCBkZWZhdWx0X3ZhbCwgdHlwZSA9ICJyZXNwb25zZSIpDQp2YWxfcHJlZCAgPC0gaWZlbHNlKHZhbF9wcm9icyA+IDAuNSwgIlllcyIsICJObyIpDQoNCm1lYW4odmFsX3ByZWQgIT0gZGVmYXVsdF92YWwkZGVmYXVsdCkNCg0KDQpzZXQuc2VlZCgyKQ0KbiA8LSBucm93KERlZmF1bHQpDQp0cmFpbl9pZHggPC0gc2FtcGxlKG4sIG4gLyAyKQ0KZGVmYXVsdF90cmFpbiA8LSBEZWZhdWx0W3RyYWluX2lkeCwgXQ0KZGVmYXVsdF92YWwgICA8LSBEZWZhdWx0Wy10cmFpbl9pZHgsIF0NCg0KIyBpaS4gRml0IGxvZ2lzdGljIHJlZ3Jlc3Npb24gb24gdHJhaW5pbmcgc2V0IG9ubHkNCmdsbV90cmFpbiA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBkZWZhdWx0X3RyYWluLCBmYW1pbHkgPSBiaW5vbWlhbCkNCg0KIyBpaWkuIFByZWRpY3QgZGVmYXVsdCBzdGF0dXMgb24gdmFsaWRhdGlvbiBzZXQNCnZhbF9wcm9icyA8LSBwcmVkaWN0KGdsbV90cmFpbiwgZGVmYXVsdF92YWwsIHR5cGUgPSAicmVzcG9uc2UiKQ0KdmFsX3ByZWQgIDwtIGlmZWxzZSh2YWxfcHJvYnMgPiAwLjUsICJZZXMiLCAiTm8iKQ0KDQojIGl2LiBDb21wdXRlIHZhbGlkYXRpb24gc2V0IGVycm9yDQptZWFuKHZhbF9wcmVkICE9IGRlZmF1bHRfdmFsJGRlZmF1bHQpDQoNCg0KDQpzZXQuc2VlZCgzKQ0KbiA8LSBucm93KERlZmF1bHQpDQp0cmFpbl9pZHggPC0gc2FtcGxlKG4sIG4gLyAyKQ0KZGVmYXVsdF90cmFpbiA8LSBEZWZhdWx0W3RyYWluX2lkeCwgXQ0KZGVmYXVsdF92YWwgICA8LSBEZWZhdWx0Wy10cmFpbl9pZHgsIF0NCg0KIyBpaS4gRml0IGxvZ2lzdGljIHJlZ3Jlc3Npb24gb24gdHJhaW5pbmcgc2V0IG9ubHkNCmdsbV90cmFpbiA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBkZWZhdWx0X3RyYWluLCBmYW1pbHkgPSBiaW5vbWlhbCkNCg0KIyBpaWkuIFByZWRpY3QgZGVmYXVsdCBzdGF0dXMgb24gdmFsaWRhdGlvbiBzZXQNCnZhbF9wcm9icyA8LSBwcmVkaWN0KGdsbV90cmFpbiwgZGVmYXVsdF92YWwsIHR5cGUgPSAicmVzcG9uc2UiKQ0KdmFsX3ByZWQgIDwtIGlmZWxzZSh2YWxfcHJvYnMgPiAwLjUsICJZZXMiLCAiTm8iKQ0KDQojIGl2LiBDb21wdXRlIHZhbGlkYXRpb24gc2V0IGVycm9yDQptZWFuKHZhbF9wcmVkICE9IGRlZmF1bHRfdmFsJGRlZmF1bHQpDQogDQpgYGANCg0KICAtIFRoZSB2YWxpZGF0aW9uIGVycm9yIHJhbmdlZCBmcm9tIGFib3V0IDIuMyUgdG8gMi44JSBhY3Jvc3MgdGhlIHRocmVlIHNwbGl0cy4gVGhpcyBzaG93cyB0aGF0IHRoZSB2YWxpZGF0aW9uIHNldCBhcHByb2FjaCBjYW4gcHJvZHVjZSBzbGlnaHRseSBkaWZmZXJlbnQgdGVzdCBlcnJvciBlc3RpbWF0ZXMgZGVwZW5kaW5nIG9uIGhvdyB0aGUgZGF0YSBhcmUgc3BsaXQuDQoNCl9fKGQpIE5vdyBjb25zaWRlciBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgdGhhdCBwcmVkaWN0cyB0aGUgcHJvYmFiaWxpdHkgb2YgZGVmYXVsdCB1c2luZyBpbmNvbWUsIGJhbGFuY2UsIGFuZCBhIGR1bW15IHZhcmlhYmxlIGZvciBzdHVkZW50LiBFc3RpbWF0ZSB0aGUgdGVzdCBlcnJvciBmb3IgdGhpcyBtb2RlbCB1c2luZyB0aGUgdmFsaWRhdGlvbiBzZXQgYXBwcm9hY2guIENvbW1lbnQgb24gd2hldGhlciBvciBub3QgaW5jbHVkaW5nIGEgZHVtbXkgdmFyaWFibGUgZm9yIHN0dWRlbnQgbGVhZHMgdG8gYSByZWR1Y3Rpb24gaW4gdGhlIHRlc3QgZXJyb3IgcmF0ZS5fXw0KYGBge3J9DQpzZXQuc2VlZCg0MikNCnRyYWluX2lkeF9kIDwtIHNhbXBsZShuLCBuIC8gMikNCmdsbV9zdHVkZW50IDwtIGdsbShkZWZhdWx0IH4gaW5jb21lICsgYmFsYW5jZSArIHN0dWRlbnQsDQogICAgICAgICAgICAgICAgICAgZGF0YSA9IERlZmF1bHRbdHJhaW5faWR4X2QsIF0sIGZhbWlseSA9IGJpbm9taWFsKQ0KcHJvYnNfc3R1ZGVudCA8LSBwcmVkaWN0KGdsbV9zdHVkZW50LCBEZWZhdWx0Wy10cmFpbl9pZHhfZCwgXSwgdHlwZSA9ICJyZXNwb25zZSIpDQpwcmVkX3N0dWRlbnQgIDwtIGlmZWxzZShwcm9ic19zdHVkZW50ID4gMC41LCAiWWVzIiwgIk5vIikNCm1lYW4ocHJlZF9zdHVkZW50ICE9IERlZmF1bHRbLXRyYWluX2lkeF9kLCBdJGRlZmF1bHQpDQoNCmBgYA0KDQogIC0gQWRkaW5nIHRoZSBzdHVkZW50IGR1bW15IHZhcmlhYmxlIGRvZXMgbm90IHJlZHVjZSB0aGUgdGVzdCBlcnJvciBieSBtdWNoLCBpdCByZW1haW5zIGFyb3VuZCAyLjYlLCBlc3NlbnRpYWxseSB0aGUgc2FtZSBhcyB0aGUgbW9kZWwgd2l0aG91dCBzdHVkZW50LiBUaGlzIHN1Z2dlc3RzIHRoYXQgc3R1ZGVudCBzdGF0dXMgZG9lcyBub3QgYWRkIHNpZ25pZmljYW50IHByZWRpY3RpdmUgcG93ZXIgZm9yIGRlZmF1bHQuDQoNCi0tLQ0KDQojIyMgUHJvYmxlbSA2DQoNCl9fKGEpIFVzaW5nIHRoZSBzdW1tYXJ5KCkgYW5kIGdsbSgpIGZ1bmN0aW9ucywgZGV0ZXJtaW5lIHRoZSBlc3RpbWF0ZWQgc3RhbmRhcmQgZXJyb3JzIGZvciB0aGUgY29lZmZpY2llbnRzIGFzc29jaWF0ZWQgd2l0aCBpbmNvbWUgYW5kIGJhbGFuY2UgaW4gYSBtdWx0aXBsZSBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsIHRoYXQgdXNlcyBib3RoIHByZWRpY3RvcnMuX18NCmBgYHtyfQ0Kc2V0LnNlZWQoNDIpDQpnbG1fc2UgPC0gZ2xtKGRlZmF1bHQgfiBpbmNvbWUgKyBiYWxhbmNlLCBkYXRhID0gRGVmYXVsdCwgZmFtaWx5ID0gYmlub21pYWwpDQpzdW1tYXJ5KGdsbV9zZSkkY29lZmZpY2llbnRzDQpgYGANCg0KX18oYikgV3JpdGUgYSBmdW5jdGlvbiwgYm9vdC5mbigpLCB0aGF0IHRha2VzIGFzIGlucHV0IHRoZSBEZWZhdWx0IGRhdGEgc2V0IGFzIHdlbGwgYXMgYW4gaW5kZXggb2YgdGhlIG9ic2VydmF0aW9ucywgYW5kIHRoYXQgb3V0cHV0cyB0aGUgY29lZmZpY2llbnQgZXN0aW1hdGVzIGZvciBpbmNvbWUgYW5kIGJhbGFuY2UgaW4gdGhlIG11bHRpcGxlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwuX18NCmBgYHtyfQ0KYm9vdC5mbiA8LSBmdW5jdGlvbihkYXRhLCBpbmRleCkgew0KICBmaXQgPC0gZ2xtKGRlZmF1bHQgfiBpbmNvbWUgKyBiYWxhbmNlLCBkYXRhID0gZGF0YSwgZmFtaWx5ID0gYmlub21pYWwsIHN1YnNldCA9IGluZGV4KQ0KICBjb2VmKGZpdClbYygiaW5jb21lIiwgImJhbGFuY2UiKV0NCn0NCg0KIyBUZXN0IG9uIGZ1bGwgZGF0YQ0KYm9vdC5mbihEZWZhdWx0LCAxOm5yb3coRGVmYXVsdCkpDQpgYGANCg0KX18oYykgVXNlIHRoZSBib290KCkgZnVuY3Rpb24gdG9nZXRoZXIgd2l0aCB5b3VyIGJvb3QuZm4oKSBmdW5jdGlvbiB0byBlc3RpbWF0ZSB0aGUgc3RhbmRhcmQgZXJyb3JzIG9mIHRoZSBsb2dpc3RpYyByZWdyZXNzaW9uIGNvZWZmaWNpZW50cyBmb3IgaW5jb21lIGFuZCBiYWxhbmNlLl9fDQpgYGB7cn0NCmxpYnJhcnkoYm9vdCkNCnNldC5zZWVkKDQyKQ0KYm9vdChEZWZhdWx0LCBib290LmZuLCBSID0gMTAwMCkNCmBgYA0KDQpfXyhkKSBDb21tZW50IG9uIHRoZSBlc3RpbWF0ZWQgc3RhbmRhcmQgZXJyb3JzIG9idGFpbmVkIHVzaW5nIHRoZSBnbG0oKSBmdW5jdGlvbiBhbmQgdXNpbmcgeW91ciBib290c3RyYXAgZnVuY3Rpb24uX18NCg0KICAtIFRoZSBzdGFuZGFyZCBlcnJvcnMgZnJvbSB0aGUgYm9vdHN0cmFwIG1ldGhvZCBhcmUgdmVyeSBzaW1pbGFyIHRvIHRob3NlIGZyb20gZ2xtKCkuIFRoaXMgc3VnZ2VzdHMgdGhhdCB0aGUgZXN0aW1hdGVzIGFyZSBjb25zaXN0ZW50LCBhbmQgZWl0aGVyIG1ldGhvZCBwcm92aWRlcyBzaW1pbGFyIHJlc3VsdHMgZm9yIHRoaXMgZGF0YSBzZXQuDQoNCi0tLQ0KDQojIyMgUHJvYmxlbSA5DQoNCg0KX18oYSkgQmFzZWQgb24gdGhpcyBkYXRhIHNldCwgcHJvdmlkZSBhbiBlc3RpbWF0ZSBmb3IgdGhlIHBvcHVsYXRpb24gbWVhbiBvZiBtZWR2LiBDYWxsIHRoaXMgZXN0aW1hdGUgwrXMgi5fXw0KYGBge3J9DQpsaWJyYXJ5KElTTFIyKQ0KbXVfaGF0IDwtIG1lYW4oQm9zdG9uJG1lZHYpDQpwcmludChtdV9oYXQpDQpgYGANCg0KICAtIFRoZSBlc3RpbWF0ZWQgcG9wdWxhdGlvbiBtZWFuIG9mIGBtZWR2YCBpcyBhcHByb3hpbWF0ZWx5IDIyLjUzLCBtZWFuaW5nIHRoZSBhdmVyYWdlIG1lZGlhbiBob21lIHZhbHVlIGFjcm9zcyBCb3N0b24gaXMgYWJvdXQgJDIyLDUzMC4NCg0KX18oYikgUHJvdmlkZSBhbiBlc3RpbWF0ZSBvZiB0aGUgc3RhbmRhcmQgZXJyb3Igb2YgwrXMgi4gSW50ZXJwcmV0IHRoaXMgcmVzdWx0Ll9fDQpgYGB7cn0NCnNlX2hhdCA8LSBzZChCb3N0b24kbWVkdikgLyBzcXJ0KG5yb3coQm9zdG9uKSkNCnByaW50KHNlX2hhdCkNCmBgYA0KDQogIC0gVGhlIGVzdGltYXRlZCBzdGFuZGFyZCBlcnJvciBvZiDCtcyCIGlzIGFwcHJveGltYXRlbHkgMC40MDkuIFRoaXMgbWVhbnMgdGhhdCB0aGUgc2FtcGxlIG1lYW4gb2YgYG1lZHZgIHdvdWxkIHR5cGljYWxseSB2YXJ5IGJ5IGFib3V0LjQwOSBmcm9tIHRoZSB0cnVlIHBvcHVsYXRpb24gbWVhbiBpZiB3ZSByZXBlYXRlZGx5IHRvb2sgcmFuZG9tIHNhbXBsZXMgZnJvbSB0aGUgcG9wdWxhdGlvbi4NCiAgDQpfXyhjKSBOb3cgZXN0aW1hdGUgdGhlIHN0YW5kYXJkIGVycm9yIG9mIMK1zIIgdXNpbmcgdGhlIGJvb3RzdHJhcC4gSG93IGRvZXMgdGhpcyBjb21wYXJlIHRvIHlvdXIgYW5zd2VyIGZyb20gKGIpP19fDQpgYGB7cn0NCmxpYnJhcnkoYm9vdCkNCg0KbWVhbi5mbiA8LSBmdW5jdGlvbihkYXRhLCBpbmRleCkgew0KICBtZWFuKGRhdGEkbWVkdltpbmRleF0pDQp9DQoNCnNldC5zZWVkKDQyKQ0KYm9vdF9yZXN1bHQgPC0gYm9vdChCb3N0b24sIG1lYW4uZm4sIFIgPSAxMDAwKQ0KYm9vdF9yZXN1bHQNCmBgYA0KDQogIC0gVGhlIGJvb3RzdHJhcCBzdGFuZGFyZCBlcnJvciBpcyB2ZXJ5IGNsb3NlIHRvIHRoZSBlc3RpbWF0ZSBmcm9tIHBhcnQgKGIpLCB3aXRoIGJvdGggdmFsdWVzIGJlaW5nIGFib3V0IDAuNDEuIFRoaXMgc3VnZ2VzdHMgdGhhdCBib3RoIG1ldGhvZHMgZ2l2ZSBzaW1pbGFyIGVzdGltYXRlcyBvZiB0aGUgc3RhbmRhcmQgZXJyb3IuDQoNCl9fKGQpIEJhc2VkIG9uIHlvdXIgYm9vdHN0cmFwIGVzdGltYXRlIGZyb20gKGMpLCBwcm92aWRlIGEgOTUlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgZm9yIHRoZSBtZWFuIG9mIG1lZHYuIENvbXBhcmUgaXQgdG8gdGhlIHJlc3VsdHMgb2J0YWluZWQgdXNpbmcgdC50ZXN0KEJvc3RvbiRtZWR2KS5fXw0KYGBge3J9DQpjaV9sb3dlciA8LSBtdV9oYXQgLSAyICogc2QoYm9vdF9yZXN1bHQkdCkNCmNpX3VwcGVyIDwtIG11X2hhdCArIDIgKiBzZChib290X3Jlc3VsdCR0KQ0KDQojIHQudGVzdCBDSQ0KdC50ZXN0KEJvc3RvbiRtZWR2KQ0KYGBgDQoNCiAgLSBUaGUgYm9vdHN0cmFwIDk1JSBjb25maWRlbmNlIGludGVydmFsIGZvciB0aGUgbWVhbiBvZiBgbWVkdmAgaXMgYXBwcm94aW1hdGVseSBbMjEuNzMsIDIzLjM0XSwgd2hpY2ggaXMgdmVyeSBzaW1pbGFyIHRvIHRoZSBpbnRlcnZhbCBwcm9kdWNlZCBieSBgdC50ZXN0KClgLiBUaGlzIHN1Z2dlc3RzIHRoYXQgYm90aCBtZXRob2RzIGdpdmUgc2ltaWxhciBlc3RpbWF0ZXMgZm9yIHRoZSB0cnVlIHBvcHVsYXRpb24gbWVhbi4NCg0KDQpfXyhlKSBCYXNlZCBvbiB0aGlzIGRhdGEgc2V0LCBwcm92aWRlIGFuIGVzdGltYXRlLCBgwrXMgl9tZWRgLCBmb3IgdGhlIG1lZGlhbiB2YWx1ZSBvZiBtZWR2IGluIHRoZSBwb3B1bGF0aW9uLl9fDQpgYGB7cn0NCm11X21lZCA8LSBtZWRpYW4oQm9zdG9uJG1lZHYpDQpwcmludChtdV9tZWQpDQpgYGANCg0KICAtIFRoZSBlc3RpbWF0ZWQgcG9wdWxhdGlvbiBtZWRpYW4gb2YgYG1lZHZgIGlzIDIxLjIsIG1lYW5pbmcgaGFsZiBvZiBCb3N0b24gaGFzIGEgbWVkaWFuIGhvbWUgdmFsdWUgYmVsb3cgJDIxLDIwMC4NCg0KX18oZikgV2Ugbm93IHdvdWxkIGxpa2UgdG8gZXN0aW1hdGUgdGhlIHN0YW5kYXJkIGVycm9yIG9mIGDCtcyCX21lZGAuIEVzdGltYXRlIHRoZSBzdGFuZGFyZCBlcnJvciBvZiB0aGUgbWVkaWFuIHVzaW5nIHRoZSBib290c3RyYXAuIENvbW1lbnQgb24geW91ciBmaW5kaW5ncy5fXw0KYGBge3J9DQptZWRpYW4uZm4gPC0gZnVuY3Rpb24oZGF0YSwgaW5kZXgpIHsNCiAgbWVkaWFuKGRhdGEkbWVkdltpbmRleF0pDQp9DQoNCnNldC5zZWVkKDQyKQ0KYm9vdF9tZWRpYW4gPC0gYm9vdChCb3N0b24sIG1lZGlhbi5mbiwgUiA9IDEwMDApDQpib290X21lZGlhbg0KYGBgDQoNCiAgLSBUaGUgYm9vdHN0cmFwIHN0YW5kYXJkIGVycm9yIG9mIHRoZSBtZWRpYW4gaXMgYXBwcm94aW1hdGVseSAwLjM4LCB3aGljaCBpcyBzaW1pbGFyIHRvIHRoZSBzdGFuZGFyZCBlcnJvciBvZiB0aGUgbWVhbi4gVGhpcyBzdWdnZXN0cyB0aGF0IGJvdGggdGhlIHNhbXBsZSBtZWFuIGFuZCBzYW1wbGUgbWVkaWFuIGFyZSBmYWlybHkgc3RhYmxlIGVzdGltYXRlcyBmb3IgdGhpcyBkYXRhIHNldC4NCg0KX18oZykgQmFzZWQgb24gdGhpcyBkYXRhIHNldCwgcHJvdmlkZSBhbiBlc3RpbWF0ZSBmb3IgdGhlIHRlbnRoIHBlcmNlbnRpbGUgb2YgbWVkdiBpbiBCb3N0b24gY2Vuc3VzIHRyYWN0cy4gQ2FsbCB0aGlzIHF1YW50aXR5IGAgwrXMgl8wLjFgLl9fDQpgYGB7cn0NCm11XzEwIDwtIHF1YW50aWxlKEJvc3RvbiRtZWR2LCAwLjEwKQ0KcHJpbnQobXVfMTApDQpgYGANCg0KICAtIFRoZSBlc3RpbWF0ZWQgdGVudGggcGVyY2VudGlsZSBvZiBgbWVkdmAgaXMgMTIuNzUsIG1lYW5pbmcgdGhhdCBhcHByb3ggMTAlIG9mIGNlbnN1cyB0cmFjdHMgaGF2ZSBhIG1lZGlhbiBob21lIHZhbHVlIGF0IG9yIGJlbG93ICQxMiw3NTAuDQoNCl9fKGgpIFVzZSB0aGUgYm9vdHN0cmFwIHRvIGVzdGltYXRlIHRoZSBzdGFuZGFyZCBlcnJvciBvZiBgIMK1zIJfMC4xYC4gQ29tbWVudCBvbiB5b3VyIGZpbmRpbmdzLl9fDQpgYGB7cn0NCnBlcmNlbnRpbGUxMC5mbiA8LSBmdW5jdGlvbihkYXRhLCBpbmRleCkgew0KICBxdWFudGlsZShkYXRhJG1lZHZbaW5kZXhdLCAwLjEwKQ0KfQ0KDQpzZXQuc2VlZCgxKQ0KYm9vdF9wMTAgPC0gYm9vdChCb3N0b24sIHBlcmNlbnRpbGUxMC5mbiwgUiA9IDEwMDApDQpib290X3AxMA0KYGBgDQoNCiAgLSBUaGUgYm9vdHN0cmFwIGVzdGltYXRlZCB0aGUgc3RhbmRhcmQgZXJyb3Igb2YgdGggZTEwdGggcGVyY2VudGlsZSB0byBiZSBhcHByb3ggLjUwLiBUaGlzIGlzIHNsaWdodGx5IGxhcmdlciB0aGFuIHRoZSBzdGFuZGFyZCBlcnJvcnMgZm9yIHRoZSBtZWFuIGFuZCBtZWRpYW4sIHN1Z2dlc3RpbmcgdGhhdCB0aGUgMTB0aCBwZXJjZW50aWxlIGlzIG1vcmUgdmFyaWFibGUgZnJvbSBzYW1wbGUgdG8gc2FtcGxlLg0KICANCg==