Problem 3

(a) Explain how k-fold cross-validation is implemented.

(b) What are the advantages and disadvantages of k-fold cross-validation relative to:

i. The validation set approach?

ii. LOOCV?


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

(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
 

(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

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.


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

(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

(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

(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 

(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

(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

(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 

(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
LS0tDQp0aXRsZTogIkFzc2lnbm1lbnQ0Ig0Kb3V0cHV0OiBodG1sX25vdGVib29rDQotLS0NCg0KIyMjIFByb2JsZW0gMw0KDQoNCl9fKGEpIEV4cGxhaW4gaG93IGstZm9sZCBjcm9zcy12YWxpZGF0aW9uIGlzIGltcGxlbWVudGVkLl9fDQoNCiAgLSBLLWZvbGQgY3Jvc3MtdmFsaWRhdGlvbiB3b3JrcyBieSByYW5kb21seSBkaXZpZGluZyB0aGUgZnVsbCBkYXRhIHNldCBpbnRvIGsgcm91Z2hseSBlcXVhbC1zaXplZCBmb2xkcy4gVGhlIG1vZGVsIGlzIHRoZW4gZml0IGsgdGltZXMsIGVhY2ggdGltZSB1c2luZyBrLTEgZm9sZHMgYXMgdGhlIHRyYWluaW5nIGRhdGEgYW5kIHRoZSByZW1haW5pbmcgZm9sZCBhcyB0aGUgdmFsaWRhdGlvbiBzZXQuIFRoZSB0ZXN0IGVycm9yIGlzIGVzdGltYXRlZCBieSBhdmVyYWdpbmcgdGhlIGsgdmFsaWRhdGlvbiBlcnJvcnMgdG9nZXRoZXIuIA0KICANCl9fKGIpIFdoYXQgYXJlIHRoZSBhZHZhbnRhZ2VzIGFuZCBkaXNhZHZhbnRhZ2VzIG9mIGstZm9sZCBjcm9zcy12YWxpZGF0aW9uIHJlbGF0aXZlIHRvOl9fDQoNCiAgX19pLiBUaGUgdmFsaWRhdGlvbiBzZXQgYXBwcm9hY2g/X18NCg0KICAtIEstZm9sZCBDViBoYXMgdHdvIGJpZyBhZHZhbnRhZ2VzIG92ZXIgdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoOiBpdCBtYWtlcyB1c2Ugb2YgbW9yZSBkYXRhIGZvciB0cmFpbmluZyAoc2luY2UgbW9zdCBvYnNlcnZhdGlvbnMgYXJlIHVzZWQgZm9yIGZpdHRpbmcgaW4gZWFjaCBmb2xkKSwgYW5kIGl0IHByb2R1Y2VzIGEgbGVzcyB2YXJpYWJsZSB0ZXN0IGVycm9yIGVzdGltYXRlIGJlY2F1c2UgdGhlIHJlc3VsdCBpcyBhdmVyYWdlZCBvdmVyIGsgc3BsaXRzIHJhdGhlciB0aGFuIGEgc2luZ2xlIG9uZS4gVGhlIGRvd25zaWRlIGlzIHRoYXQgaXQgdGFrZXMgbG9uZ2VyIHRvIGNvbXB1dGUgc2luY2UgdGhlIG1vZGVsIG11c3QgYmUgZmlyIGsgdGltZXMgaW5zdGVhZCBvZiBvbmNlLg0KDQogIF9faWkuIExPT0NWP19fDQoNCiAgLSBDb21wYXJlZCB0byBMT09DViwgay1mb2xkIENWIGlzIG11Y2ggZmFzdGVyIHRvIGNvbXB1dGUgYmVjYXVzZSBpdCBmaXRzIHRoZSBtb2RlbCBvbmUgayB0aW1lcyBpbnN0ZWFkIG9mIG9uY2UgZm9yIGV2ZXJ5IG9ic2VydmF0aW9uLiBJdCBtYXkgaGF2ZSBzbGlnaHRseSBtb3JlIGJpYXMgdGhhbiBMT09LViwgYnV0IGl0IG9mdGVuIHByb2R1Y2VzIGEgbW9yZSBzdGFibGUgZXN0aW1hdGUgb2YgdGhlIHRlc3QgZXJyb3IuDQoNCi0tLQ0KDQojIyMgUHJvYmxlbSA1DQoNCl9fKGEpIEZpdCBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgdGhhdCB1c2VzIGluY29tZSBhbmQgYmFsYW5jZSB0byBwcmVkaWN0IGRlZmF1bHQuX18NCmBgYHtyfQ0KbGlicmFyeShJU0xSMikNCnNldC5zZWVkKDQyKQ0KDQpnbG1fZGVmYXVsdCA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBEZWZhdWx0LCBmYW1pbHkgPSBiaW5vbWlhbCkNCnN1bW1hcnkoZ2xtX2RlZmF1bHQpDQpgYGANCg0KX18oYikgVXNpbmcgdGhlIHZhbGlkYXRpb24gc2V0IGFwcHJvYWNoLCBlc3RpbWF0ZSB0aGUgdGVzdCBlcnJvciBvZiB0aGlzIG1vZGVsLl9fDQpgYGB7cn0NCnNldC5zZWVkKDQyKQ0KDQojIGkuIFNwbGl0IGludG8gdHJhaW5pbmcgYW5kIHZhbGlkYXRpb24gc2V0cw0KbiA8LSBucm93KERlZmF1bHQpDQp0cmFpbl9pZHggPC0gc2FtcGxlKG4sIG4gLyAyKQ0KZGVmYXVsdF90cmFpbiA8LSBEZWZhdWx0W3RyYWluX2lkeCwgXQ0KZGVmYXVsdF92YWwgICA8LSBEZWZhdWx0Wy10cmFpbl9pZHgsIF0NCg0KIyBpaS4gRml0IGxvZ2lzdGljIHJlZ3Jlc3Npb24gb24gdHJhaW5pbmcgc2V0IG9ubHkNCmdsbV90cmFpbiA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBkZWZhdWx0X3RyYWluLCBmYW1pbHkgPSBiaW5vbWlhbCkNCg0KIyBpaWkuIFByZWRpY3QgZGVmYXVsdCBzdGF0dXMgb24gdmFsaWRhdGlvbiBzZXQNCnZhbF9wcm9icyA8LSBwcmVkaWN0KGdsbV90cmFpbiwgZGVmYXVsdF92YWwsIHR5cGUgPSAicmVzcG9uc2UiKQ0KdmFsX3ByZWQgIDwtIGlmZWxzZSh2YWxfcHJvYnMgPiAwLjUsICJZZXMiLCAiTm8iKQ0KDQojIGl2LiBDb21wdXRlIHZhbGlkYXRpb24gc2V0IGVycm9yDQptZWFuKHZhbF9wcmVkICE9IGRlZmF1bHRfdmFsJGRlZmF1bHQpDQoNCmBgYA0KDQogIC0gVGhlIHZhbGlkYXRpb24gc2V0IGVycm9yIGlzIGFwcHJveGltYXRlbHkgMi42JSwgbWVhbmluZyB0aGUgbG9naXN0aWMgcmVncmVzc2lvbiBtb2RlbCBpbmNvcnJlY3RseSBjbGFzc2lmaWVzIGFib3V0IDIuNiUgb2YgdGhlIG9ic2VydmF0aW9ucyBpbiB0aGUgdmFsaWRhdGlvbiBzZXQuDQoNCl9fKGMpIFJlcGVhdCB0aGUgcHJvY2VzcyBpbiAoYikgdGhyZWUgdGltZXMsIHVzaW5nIHRocmVlIGRpZmZlcmVudCBzcGxpdHMgb2YgdGhlIG9ic2VydmF0aW9ucyBpbnRvIGEgdHJhaW5pbmcgc2V0IGFuZCBhIHZhbGlkYXRpb24gc2V0LiBDb21tZW50IG9uIHRoZSByZXN1bHRzIG9idGFpbmVkLl9fDQpgYGB7cn0NCnNldC5zZWVkKDEpDQpuIDwtIG5yb3coRGVmYXVsdCkNCnRyYWluX2lkeCA8LSBzYW1wbGUobiwgbiAvIDIpDQpkZWZhdWx0X3RyYWluIDwtIERlZmF1bHRbdHJhaW5faWR4LCBdDQpkZWZhdWx0X3ZhbCAgIDwtIERlZmF1bHRbLXRyYWluX2lkeCwgXQ0KDQojIGlpLiBGaXQgbG9naXN0aWMgcmVncmVzc2lvbiBvbiB0cmFpbmluZyBzZXQgb25seQ0KZ2xtX3RyYWluIDwtIGdsbShkZWZhdWx0IH4gaW5jb21lICsgYmFsYW5jZSwgZGF0YSA9IGRlZmF1bHRfdHJhaW4sIGZhbWlseSA9IGJpbm9taWFsKQ0KDQojIGlpaS4gUHJlZGljdCBkZWZhdWx0IHN0YXR1cyBvbiB2YWxpZGF0aW9uIHNldA0KdmFsX3Byb2JzIDwtIHByZWRpY3QoZ2xtX3RyYWluLCBkZWZhdWx0X3ZhbCwgdHlwZSA9ICJyZXNwb25zZSIpDQp2YWxfcHJlZCAgPC0gaWZlbHNlKHZhbF9wcm9icyA+IDAuNSwgIlllcyIsICJObyIpDQoNCm1lYW4odmFsX3ByZWQgIT0gZGVmYXVsdF92YWwkZGVmYXVsdCkNCg0KDQpzZXQuc2VlZCgyKQ0KbiA8LSBucm93KERlZmF1bHQpDQp0cmFpbl9pZHggPC0gc2FtcGxlKG4sIG4gLyAyKQ0KZGVmYXVsdF90cmFpbiA8LSBEZWZhdWx0W3RyYWluX2lkeCwgXQ0KZGVmYXVsdF92YWwgICA8LSBEZWZhdWx0Wy10cmFpbl9pZHgsIF0NCg0KIyBpaS4gRml0IGxvZ2lzdGljIHJlZ3Jlc3Npb24gb24gdHJhaW5pbmcgc2V0IG9ubHkNCmdsbV90cmFpbiA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBkZWZhdWx0X3RyYWluLCBmYW1pbHkgPSBiaW5vbWlhbCkNCg0KIyBpaWkuIFByZWRpY3QgZGVmYXVsdCBzdGF0dXMgb24gdmFsaWRhdGlvbiBzZXQNCnZhbF9wcm9icyA8LSBwcmVkaWN0KGdsbV90cmFpbiwgZGVmYXVsdF92YWwsIHR5cGUgPSAicmVzcG9uc2UiKQ0KdmFsX3ByZWQgIDwtIGlmZWxzZSh2YWxfcHJvYnMgPiAwLjUsICJZZXMiLCAiTm8iKQ0KDQojIGl2LiBDb21wdXRlIHZhbGlkYXRpb24gc2V0IGVycm9yDQptZWFuKHZhbF9wcmVkICE9IGRlZmF1bHRfdmFsJGRlZmF1bHQpDQoNCg0KDQpzZXQuc2VlZCgzKQ0KbiA8LSBucm93KERlZmF1bHQpDQp0cmFpbl9pZHggPC0gc2FtcGxlKG4sIG4gLyAyKQ0KZGVmYXVsdF90cmFpbiA8LSBEZWZhdWx0W3RyYWluX2lkeCwgXQ0KZGVmYXVsdF92YWwgICA8LSBEZWZhdWx0Wy10cmFpbl9pZHgsIF0NCg0KIyBpaS4gRml0IGxvZ2lzdGljIHJlZ3Jlc3Npb24gb24gdHJhaW5pbmcgc2V0IG9ubHkNCmdsbV90cmFpbiA8LSBnbG0oZGVmYXVsdCB+IGluY29tZSArIGJhbGFuY2UsIGRhdGEgPSBkZWZhdWx0X3RyYWluLCBmYW1pbHkgPSBiaW5vbWlhbCkNCg0KIyBpaWkuIFByZWRpY3QgZGVmYXVsdCBzdGF0dXMgb24gdmFsaWRhdGlvbiBzZXQNCnZhbF9wcm9icyA8LSBwcmVkaWN0KGdsbV90cmFpbiwgZGVmYXVsdF92YWwsIHR5cGUgPSAicmVzcG9uc2UiKQ0KdmFsX3ByZWQgIDwtIGlmZWxzZSh2YWxfcHJvYnMgPiAwLjUsICJZZXMiLCAiTm8iKQ0KDQojIGl2LiBDb21wdXRlIHZhbGlkYXRpb24gc2V0IGVycm9yDQptZWFuKHZhbF9wcmVkICE9IGRlZmF1bHRfdmFsJGRlZmF1bHQpDQogDQpgYGANCg0KICAtIFRoZSB2YWxpZGF0aW9uIGVycm9yIHJhbmdlZCBmcm9tIGFib3V0IDIuMyUgdG8gMi44JSBhY3Jvc3MgdGhlIHRocmVlIHNwbGl0cy4gVGhpcyBzaG93cyB0aGF0IHRoZSB2YWxpZGF0aW9uIHNldCBhcHByb2FjaCBjYW4gcHJvZHVjZSBzbGlnaHRseSBkaWZmZXJlbnQgdGVzdCBlcnJvciBlc3RpbWF0ZXMgZGVwZW5kaW5nIG9uIGhvdyB0aGUgZGF0YSBhcmUgc3BsaXQuDQoNCl9fKGQpIE5vdyBjb25zaWRlciBhIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwgdGhhdCBwcmVkaWN0cyB0aGUgcHJvYmFiaWxpdHkgb2YgZGVmYXVsdCB1c2luZyBpbmNvbWUsIGJhbGFuY2UsIGFuZCBhIGR1bW15IHZhcmlhYmxlIGZvciBzdHVkZW50LiBFc3RpbWF0ZSB0aGUgdGVzdCBlcnJvciBmb3IgdGhpcyBtb2RlbCB1c2luZyB0aGUgdmFsaWRhdGlvbiBzZXQgYXBwcm9hY2guIENvbW1lbnQgb24gd2hldGhlciBvciBub3QgaW5jbHVkaW5nIGEgZHVtbXkgdmFyaWFibGUgZm9yIHN0dWRlbnQgbGVhZHMgdG8gYSByZWR1Y3Rpb24gaW4gdGhlIHRlc3QgZXJyb3IgcmF0ZS5fXw0KYGBge3J9DQpzZXQuc2VlZCg0MikNCnRyYWluX2lkeF9kIDwtIHNhbXBsZShuLCBuIC8gMikNCmdsbV9zdHVkZW50IDwtIGdsbShkZWZhdWx0IH4gaW5jb21lICsgYmFsYW5jZSArIHN0dWRlbnQsDQogICAgICAgICAgICAgICAgICAgZGF0YSA9IERlZmF1bHRbdHJhaW5faWR4X2QsIF0sIGZhbWlseSA9IGJpbm9taWFsKQ0KcHJvYnNfc3R1ZGVudCA8LSBwcmVkaWN0KGdsbV9zdHVkZW50LCBEZWZhdWx0Wy10cmFpbl9pZHhfZCwgXSwgdHlwZSA9ICJyZXNwb25zZSIpDQpwcmVkX3N0dWRlbnQgIDwtIGlmZWxzZShwcm9ic19zdHVkZW50ID4gMC41LCAiWWVzIiwgIk5vIikNCm1lYW4ocHJlZF9zdHVkZW50ICE9IERlZmF1bHRbLXRyYWluX2lkeF9kLCBdJGRlZmF1bHQpDQoNCmBgYA0KDQogIC0gQWRkaW5nIHRoZSBzdHVkZW50IGR1bW15IHZhcmlhYmxlIGRvZXMgbm90IHJlZHVjZSB0aGUgdGVzdCBlcnJvciBieSBtdWNoLCBpdCByZW1haW5zIGFyb3VuZCAyLjYlLCBlc3NlbnRpYWxseSB0aGUgc2FtZSBhcyB0aGUgbW9kZWwgd2l0aG91dCBzdHVkZW50LiBUaGlzIHN1Z2dlc3RzIHRoYXQgc3R1ZGVudCBzdGF0dXMgZG9lcyBub3QgYWRkIHNpZ25pZmljYW50IHByZWRpY3RpdmUgcG93ZXIgZm9yIGRlZmF1bHQuDQoNCi0tLQ0KDQojIyMgUHJvYmxlbSA2DQoNCl9fKGEpIFVzaW5nIHRoZSBzdW1tYXJ5KCkgYW5kIGdsbSgpIGZ1bmN0aW9ucywgZGV0ZXJtaW5lIHRoZSBlc3RpbWF0ZWQgc3RhbmRhcmQgZXJyb3JzIGZvciB0aGUgY29lZmZpY2llbnRzIGFzc29jaWF0ZWQgd2l0aCBpbmNvbWUgYW5kIGJhbGFuY2UgaW4gYSBtdWx0aXBsZSBsb2dpc3RpYyByZWdyZXNzaW9uIG1vZGVsIHRoYXQgdXNlcyBib3RoIHByZWRpY3RvcnMuX18NCmBgYHtyfQ0Kc2V0LnNlZWQoNDIpDQpnbG1fc2UgPC0gZ2xtKGRlZmF1bHQgfiBpbmNvbWUgKyBiYWxhbmNlLCBkYXRhID0gRGVmYXVsdCwgZmFtaWx5ID0gYmlub21pYWwpDQpzdW1tYXJ5KGdsbV9zZSkkY29lZmZpY2llbnRzDQpgYGANCg0KX18oYikgV3JpdGUgYSBmdW5jdGlvbiwgYm9vdC5mbigpLCB0aGF0IHRha2VzIGFzIGlucHV0IHRoZSBEZWZhdWx0IGRhdGEgc2V0IGFzIHdlbGwgYXMgYW4gaW5kZXggb2YgdGhlIG9ic2VydmF0aW9ucywgYW5kIHRoYXQgb3V0cHV0cyB0aGUgY29lZmZpY2llbnQgZXN0aW1hdGVzIGZvciBpbmNvbWUgYW5kIGJhbGFuY2UgaW4gdGhlIG11bHRpcGxlIGxvZ2lzdGljIHJlZ3Jlc3Npb24gbW9kZWwuX18NCmBgYHtyfQ0KYm9vdC5mbiA8LSBmdW5jdGlvbihkYXRhLCBpbmRleCkgew0KICBmaXQgPC0gZ2xtKGRlZmF1bHQgfiBpbmNvbWUgKyBiYWxhbmNlLCBkYXRhID0gZGF0YSwgZmFtaWx5ID0gYmlub21pYWwsIHN1YnNldCA9IGluZGV4KQ0KICBjb2VmKGZpdClbYygiaW5jb21lIiwgImJhbGFuY2UiKV0NCn0NCg0KIyBUZXN0IG9uIGZ1bGwgZGF0YQ0KYm9vdC5mbihEZWZhdWx0LCAxOm5yb3coRGVmYXVsdCkpDQpgYGANCg0KX18oYykgVXNlIHRoZSBib290KCkgZnVuY3Rpb24gdG9nZXRoZXIgd2l0aCB5b3VyIGJvb3QuZm4oKSBmdW5jdGlvbiB0byBlc3RpbWF0ZSB0aGUgc3RhbmRhcmQgZXJyb3JzIG9mIHRoZSBsb2dpc3RpYyByZWdyZXNzaW9uIGNvZWZmaWNpZW50cyBmb3IgaW5jb21lIGFuZCBiYWxhbmNlLl9fDQpgYGB7cn0NCmxpYnJhcnkoYm9vdCkNCnNldC5zZWVkKDQyKQ0KYm9vdChEZWZhdWx0LCBib290LmZuLCBSID0gMTAwMCkNCmBgYA0KDQpfXyhkKSBDb21tZW50IG9uIHRoZSBlc3RpbWF0ZWQgc3RhbmRhcmQgZXJyb3JzIG9idGFpbmVkIHVzaW5nIHRoZSBnbG0oKSBmdW5jdGlvbiBhbmQgdXNpbmcgeW91ciBib290c3RyYXAgZnVuY3Rpb24uX18NCg0KICAtIFRoZSBzdGFuZGFyZCBlcnJvcnMgZnJvbSB0aGUgYm9vdHN0cmFwIG1ldGhvZCBhcmUgdmVyeSBzaW1pbGFyIHRvIHRob3NlIGZyb20gZ2xtKCkuIFRoaXMgc3VnZ2VzdHMgdGhhdCB0aGUgZXN0aW1hdGVzIGFyZSBjb25zaXN0ZW50LCBhbmQgZWl0aGVyIG1ldGhvZCBwcm92aWRlcyBzaW1pbGFyIHJlc3VsdHMgZm9yIHRoaXMgZGF0YSBzZXQuDQoNCi0tLQ0KDQojIyMgUHJvYmxlbSA5DQoNCg0KX18oYSkgQmFzZWQgb24gdGhpcyBkYXRhIHNldCwgcHJvdmlkZSBhbiBlc3RpbWF0ZSBmb3IgdGhlIHBvcHVsYXRpb24gbWVhbiBvZiBtZWR2LiBDYWxsIHRoaXMgZXN0aW1hdGUgwrXMgi5fXw0KYGBge3J9DQpsaWJyYXJ5KElTTFIyKQ0KbXVfaGF0IDwtIG1lYW4oQm9zdG9uJG1lZHYpDQpwcmludChtdV9oYXQpDQpgYGANCg0KICAtIFRoZSBlc3RpbWF0ZWQgcG9wdWxhdGlvbiBtZWFuIG9mIGBtZWR2YCBpcyBhcHByb3hpbWF0ZWx5IDIyLjUzLCBtZWFuaW5nIHRoZSBhdmVyYWdlIG1lZGlhbiBob21lIHZhbHVlIGFjcm9zcyBCb3N0b24gaXMgYWJvdXQgJDIyLDUzMC4NCg0KX18oYikgUHJvdmlkZSBhbiBlc3RpbWF0ZSBvZiB0aGUgc3RhbmRhcmQgZXJyb3Igb2YgwrXMgi4gSW50ZXJwcmV0IHRoaXMgcmVzdWx0Ll9fDQpgYGB7cn0NCnNlX2hhdCA8LSBzZChCb3N0b24kbWVkdikgLyBzcXJ0KG5yb3coQm9zdG9uKSkNCnByaW50KHNlX2hhdCkNCmBgYA0KDQogIC0gVGhlIGVzdGltYXRlZCBzdGFuZGFyZCBlcnJvciBvZiDCtcyCIGlzIGFwcHJveGltYXRlbHkgMC40MDkuIFRoaXMgbWVhbnMgdGhhdCB0aGUgc2FtcGxlIG1lYW4gb2YgYG1lZHZgIHdvdWxkIHR5cGljYWxseSB2YXJ5IGJ5IGFib3V0LjQwOSBmcm9tIHRoZSB0cnVlIHBvcHVsYXRpb24gbWVhbiBpZiB3ZSByZXBlYXRlZGx5IHRvb2sgcmFuZG9tIHNhbXBsZXMgZnJvbSB0aGUgcG9wdWxhdGlvbi4NCiAgDQpfXyhjKSBOb3cgZXN0aW1hdGUgdGhlIHN0YW5kYXJkIGVycm9yIG9mIMK1zIIgdXNpbmcgdGhlIGJvb3RzdHJhcC4gSG93IGRvZXMgdGhpcyBjb21wYXJlIHRvIHlvdXIgYW5zd2VyIGZyb20gKGIpP19fDQpgYGB7cn0NCmxpYnJhcnkoYm9vdCkNCg0KbWVhbi5mbiA8LSBmdW5jdGlvbihkYXRhLCBpbmRleCkgew0KICBtZWFuKGRhdGEkbWVkdltpbmRleF0pDQp9DQoNCnNldC5zZWVkKDQyKQ0KYm9vdF9yZXN1bHQgPC0gYm9vdChCb3N0b24sIG1lYW4uZm4sIFIgPSAxMDAwKQ0KYm9vdF9yZXN1bHQNCmBgYA0KDQogIC0gVGhlIGJvb3RzdHJhcCBzdGFuZGFyZCBlcnJvciBpcyB2ZXJ5IGNsb3NlIHRvIHRoZSBlc3RpbWF0ZSBmcm9tIHBhcnQgKGIpLCB3aXRoIGJvdGggdmFsdWVzIGJlaW5nIGFib3V0IDAuNDEuIFRoaXMgc3VnZ2VzdHMgdGhhdCBib3RoIG1ldGhvZHMgZ2l2ZSBzaW1pbGFyIGVzdGltYXRlcyBvZiB0aGUgc3RhbmRhcmQgZXJyb3IuDQoNCl9fKGQpIEJhc2VkIG9uIHlvdXIgYm9vdHN0cmFwIGVzdGltYXRlIGZyb20gKGMpLCBwcm92aWRlIGEgOTUlIGNvbmZpZGVuY2UgaW50ZXJ2YWwgZm9yIHRoZSBtZWFuIG9mIG1lZHYuIENvbXBhcmUgaXQgdG8gdGhlIHJlc3VsdHMgb2J0YWluZWQgdXNpbmcgdC50ZXN0KEJvc3RvbiRtZWR2KS5fXw0KYGBge3J9DQpjaV9sb3dlciA8LSBtdV9oYXQgLSAyICogc2QoYm9vdF9yZXN1bHQkdCkNCmNpX3VwcGVyIDwtIG11X2hhdCArIDIgKiBzZChib290X3Jlc3VsdCR0KQ0KDQojIHQudGVzdCBDSQ0KdC50ZXN0KEJvc3RvbiRtZWR2KQ0KYGBgDQoNCiAgLSBUaGUgYm9vdHN0cmFwIDk1JSBjb25maWRlbmNlIGludGVydmFsIGZvciB0aGUgbWVhbiBvZiBgbWVkdmAgaXMgYXBwcm94aW1hdGVseSBbMjEuNzMsIDIzLjM0XSwgd2hpY2ggaXMgdmVyeSBzaW1pbGFyIHRvIHRoZSBpbnRlcnZhbCBwcm9kdWNlZCBieSBgdC50ZXN0KClgLiBUaGlzIHN1Z2dlc3RzIHRoYXQgYm90aCBtZXRob2RzIGdpdmUgc2ltaWxhciBlc3RpbWF0ZXMgZm9yIHRoZSB0cnVlIHBvcHVsYXRpb24gbWVhbi4NCg0KDQpfXyhlKSBCYXNlZCBvbiB0aGlzIGRhdGEgc2V0LCBwcm92aWRlIGFuIGVzdGltYXRlLCBgwrXMgl9tZWRgLCBmb3IgdGhlIG1lZGlhbiB2YWx1ZSBvZiBtZWR2IGluIHRoZSBwb3B1bGF0aW9uLl9fDQpgYGB7cn0NCm11X21lZCA8LSBtZWRpYW4oQm9zdG9uJG1lZHYpDQpwcmludChtdV9tZWQpDQpgYGANCg0KICAtIFRoZSBlc3RpbWF0ZWQgcG9wdWxhdGlvbiBtZWRpYW4gb2YgYG1lZHZgIGlzIDIxLjIsIG1lYW5pbmcgaGFsZiBvZiBCb3N0b24gaGFzIGEgbWVkaWFuIGhvbWUgdmFsdWUgYmVsb3cgJDIxLDIwMC4NCg0KX18oZikgV2Ugbm93IHdvdWxkIGxpa2UgdG8gZXN0aW1hdGUgdGhlIHN0YW5kYXJkIGVycm9yIG9mIGDCtcyCX21lZGAuIEVzdGltYXRlIHRoZSBzdGFuZGFyZCBlcnJvciBvZiB0aGUgbWVkaWFuIHVzaW5nIHRoZSBib290c3RyYXAuIENvbW1lbnQgb24geW91ciBmaW5kaW5ncy5fXw0KYGBge3J9DQptZWRpYW4uZm4gPC0gZnVuY3Rpb24oZGF0YSwgaW5kZXgpIHsNCiAgbWVkaWFuKGRhdGEkbWVkdltpbmRleF0pDQp9DQoNCnNldC5zZWVkKDQyKQ0KYm9vdF9tZWRpYW4gPC0gYm9vdChCb3N0b24sIG1lZGlhbi5mbiwgUiA9IDEwMDApDQpib290X21lZGlhbg0KYGBgDQoNCiAgLSBUaGUgYm9vdHN0cmFwIHN0YW5kYXJkIGVycm9yIG9mIHRoZSBtZWRpYW4gaXMgYXBwcm94aW1hdGVseSAwLjM4LCB3aGljaCBpcyBzaW1pbGFyIHRvIHRoZSBzdGFuZGFyZCBlcnJvciBvZiB0aGUgbWVhbi4gVGhpcyBzdWdnZXN0cyB0aGF0IGJvdGggdGhlIHNhbXBsZSBtZWFuIGFuZCBzYW1wbGUgbWVkaWFuIGFyZSBmYWlybHkgc3RhYmxlIGVzdGltYXRlcyBmb3IgdGhpcyBkYXRhIHNldC4NCg0KX18oZykgQmFzZWQgb24gdGhpcyBkYXRhIHNldCwgcHJvdmlkZSBhbiBlc3RpbWF0ZSBmb3IgdGhlIHRlbnRoIHBlcmNlbnRpbGUgb2YgbWVkdiBpbiBCb3N0b24gY2Vuc3VzIHRyYWN0cy4gQ2FsbCB0aGlzIHF1YW50aXR5IGAgwrXMgl8wLjFgLl9fDQpgYGB7cn0NCm11XzEwIDwtIHF1YW50aWxlKEJvc3RvbiRtZWR2LCAwLjEwKQ0KcHJpbnQobXVfMTApDQpgYGANCg0KICAtIFRoZSBlc3RpbWF0ZWQgdGVudGggcGVyY2VudGlsZSBvZiBgbWVkdmAgaXMgMTIuNzUsIG1lYW5pbmcgdGhhdCBhcHByb3ggMTAlIG9mIGNlbnN1cyB0cmFjdHMgaGF2ZSBhIG1lZGlhbiBob21lIHZhbHVlIGF0IG9yIGJlbG93ICQxMiw3NTAuDQoNCl9fKGgpIFVzZSB0aGUgYm9vdHN0cmFwIHRvIGVzdGltYXRlIHRoZSBzdGFuZGFyZCBlcnJvciBvZiBgIMK1zIJfMC4xYC4gQ29tbWVudCBvbiB5b3VyIGZpbmRpbmdzLl9fDQpgYGB7cn0NCnBlcmNlbnRpbGUxMC5mbiA8LSBmdW5jdGlvbihkYXRhLCBpbmRleCkgew0KICBxdWFudGlsZShkYXRhJG1lZHZbaW5kZXhdLCAwLjEwKQ0KfQ0KDQpzZXQuc2VlZCgxKQ0KYm9vdF9wMTAgPC0gYm9vdChCb3N0b24sIHBlcmNlbnRpbGUxMC5mbiwgUiA9IDEwMDApDQpib290X3AxMA0KYGBgDQoNCiAgLSBUaGUgYm9vdHN0cmFwIGVzdGltYXRlZCB0aGUgc3RhbmRhcmQgZXJyb3Igb2YgdGggZTEwdGggcGVyY2VudGlsZSB0byBiZSBhcHByb3ggLjUwLiBUaGlzIGlzIHNsaWdodGx5IGxhcmdlciB0aGFuIHRoZSBzdGFuZGFyZCBlcnJvcnMgZm9yIHRoZSBtZWFuIGFuZCBtZWRpYW4sIHN1Z2dlc3RpbmcgdGhhdCB0aGUgMTB0aCBwZXJjZW50aWxlIGlzIG1vcmUgdmFyaWFibGUgZnJvbSBzYW1wbGUgdG8gc2FtcGxlLg0KICANCg==