for num_training in train_data_sizes:

    try:
        del X_train
    except:
        pass

    try:
        del y_train
    except:
        pass

    try:
        del X_test
    except:
        pass

    try:
        del y_test
    except:
        pass

    mask = np.arange(num_training,dtype=int)
    X_train = X_train_orig[mask]
    y_train = y_train_orig[mask]

    num_test = num_training / 10
    mask = np.arange(num_test,dtype=int)
    X_test = X_test_orig[mask]
    y_test = y_test_orig[mask]

    # Reshape the image data into rows
    X_train = np.reshape(X_train, (X_train.shape[0], -1))
    X_test = np.reshape(X_test, (X_test.shape[0], -1))

    classifier = KNearestNeighbor()
    classifier.train(X_train, y_train)


    num_folds = 5
    k_choices = [1, 3, 5, 8, 10, 12, 15, 20, 50, 100]

    X_train_folds = []
    y_train_folds = []

    X_train_folds = np.array_split(X_train, num_folds)
    y_train_folds = np.array_split(y_train, num_folds)

    k_to_accuracies = {}

    for k in k_choices:
        k_to_accuracies[k] = []
        for i in range(num_folds):
            # prepare training data for the current fold
            X_train_fold = np.concatenate([ fold for j, fold in enumerate(X_train_folds) if i != j ])
            y_train_fold = np.concatenate([ fold for j, fold in enumerate(y_train_folds) if i != j ])

            # use of k-nearest-neighbor algorithm
            classifier.train(X_train_fold, y_train_fold)
            y_pred_fold = classifier.predict(X_train_folds[i], k=k, num_loops=0)

            # Compute the fraction of correctly predicted examples
            num_correct = np.sum(y_pred_fold == y_train_folds[i])
            accuracy = float(num_correct) / X_train_folds[i].shape[0]
            k_to_accuracies[k].append(accuracy)

    accuracies_mean = np.array([np.mean(v) for k,v in sorted(k_to_accuracies.items())])
    accuracies_std = np.array([np.std(v) for k,v in sorted(k_to_accuracies.items())])

    best_k = k_choices[accuracies_mean.argmax()]

    classifier = KNearestNeighbor()
    classifier.train(X_train, y_train)
    y_test_pred = classifier.predict(X_test, k=best_k)

    # Compute and display the accuracy
    num_correct = np.sum(y_test_pred == y_test)
    accuracy = float(num_correct) / num_test
    num_train_to_accuracy[num_training] = accuracy