Data Collections: Mixed Unit Review (Computer Science A Unit 4)

(a)

public static ArrayList<Integer> readScores(String fileName) throws IOException
{
    ArrayList<Integer> scores = new ArrayList<Integer>();
    Scanner in = new Scanner(new File(fileName));
    while (in.hasNext())
    {
        String[] parts = in.nextLine().split(",");
        scores.add(Integer.parseInt(parts[1]));
    }
    in.close();
    return scores;
}

(b)

public static int countAboveAverage(ArrayList<Integer> scores)
{
    if (scores.size() == 0)
    {
        return 0;
    }
    int sum = 0;
    for (int s : scores)
    {
        sum += s;
    }
    double avg = (double) sum / scores.size();
    int count = 0;
    for (int s : scores)
    {
        if (s > avg)
        {
            count++;
        }
    }
    return count;
}

(c) The list is [70, 85, 60, 90]; the mean is 305 / 4 = 76.25; the scores above it are 85 and 90, so the result is 2 (run and confirmed). Autoboxing puts each int into the list and unboxing returns it in the enhanced for loop.

Suggested Marlbridge rubric (8 points)

Topic checks: Topic 4.6, Topic 4.7, Topic 4.8 and Topic 4.10.

(a) The insertion loop passes 3, 8, 12 and 15 (each less than 18) and stops at index 4, where 21 is not less than 18. add(4, 18) gives [3, 8, 12, 15, 18, 21, 27].

(b) The list now has 7 elements (indices 0 to 6).

The result is 5 after two comparisons (run and confirmed).

(c) For 10:

The result is -1 after three comparisons. A linear search checks each element in turn for equality (or a property), so it does not rely on order; binary search relies on order to discard half of the range after each comparison.

Suggested Marlbridge rubric (7 points)

Topic checks: Topic 4.10, Topic 4.14 and Topic 4.17.

(a)

public static double[] testAverages(int[][] s)
{
    double[] avg = new double[s[0].length];
    for (int c = 0; c < s[0].length; c++)
    {
        int sum = 0;
        for (int r = 0; r < s.length; r++)
        {
            sum += s[r][c];
        }
        avg[c] = (double) sum / s.length;
    }
    return avg;
}

(b)

public static int bestStudent(int[][] s)
{
    int best = 0;
    int bestTotal = -1;
    for (int r = 0; r < s.length; r++)
    {
        int total = 0;
        for (int c = 0; c < s[r].length; c++)
        {
            total += s[r][c];
        }
        if (total > bestTotal)
        {
            bestTotal = total;
            best = r;
        }
    }
    return best;
}

(c) Column sums are 243, 247, 234 and 236, so the test averages are 81.0, 82.33333333333333, 78.0 and 78.66666666666667. Row totals are 300, 320 and 340, so bestStudent(t) is 2 (run and confirmed).

Suggested Marlbridge rubric (8 points)

Topic checks: Topic 4.11, Topic 4.12 and Topic 4.13.

(a) Pass 1 swaps the minimum 1 (index 3) with the 9: 1, 6, 7, 9, 5. Pass 2 finds the minimum of the rest, 5 (index 4), and swaps it with the 6: 1, 5, 7, 9, 6.

(b) Pass 1 inserts 6 before 9: 6, 9, 7, 1, 5. Pass 2 inserts 7 between 6 and 9: 6, 7, 9, 1, 5. (Run and confirmed.) The two sorts differ: after two passes the selection sort has the two smallest values in final places, while the insertion sort’s first three values are only sorted among themselves.

(c) countBig(x, 0) returns 3. The calls are i = 0 (9 > 5: 1 plus the rest), i = 1 (6 > 5), i = 2 (7 > 5), i = 3 (1: not counted), i = 4 (5 is not greater than 5: not counted), i = 5 (equals the length: base case, 0). The parameter i is the position being examined; it grows by one per call until it reaches the length, like a loop index.

Suggested Marlbridge rubric (7 points)

Topic checks: Topic 4.15, Topic 4.16 and Topic 4.17.

(a) Any two of: the records could be leaked or stolen, exposing names and addresses; the titles borrowed can reveal sensitive personal interests or beliefs; the data might be kept longer than needed or used for purposes borrowers did not agree to, such as marketing; combining the data with other data sets could identify individuals. A safeguard: collect only the data needed, restrict who can access it, protect it (for example by encryption), and delete it when it is no longer required.

(b) The contents of a data set relate to a specific question and may not give correct answers for a different one. This data set describes borrowers of one library, who are probably not representative of pupils in another country, and it records borrowing, not all reading. Using it to extrapolate would risk biased conclusions.

(c) Use a linear search: traverse the list from the first index, compare each member number with the target using a value comparison, and return the index as soon as one matches. If every element has been checked without a match, return -1 (after the loop). The list does not have to be sorted. (Binary search would be faster for a long sorted list.)

Suggested Marlbridge rubric (6 points)

Topic checks: Topic 4.1, Topic 4.2 and Topic 4.14.

(a)

public static ArrayList<Integer> evens(int[][] m)
{
    ArrayList<Integer> result = new ArrayList<Integer>();
    for (int[] row : m)
    {
        for (int v : row)
        {
            if (v % 2 == 0)
            {
                result.add(v);
            }
        }
    }
    return result;
}

(b)

public static int[] toArray(ArrayList<Integer> list)
{
    int[] a = new int[list.size()];
    for (int i = 0; i < list.size(); i++)
    {
        a[i] = list.get(i);
    }
    return a;
}

(c) evens(m) is [2, 4, 6, 8] and toArray gives an array of length 4 holding 2, 4, 6 and 8 (run and confirmed). In (a) the nested enhanced for loops visit the table in row-major order, with row of type int[] and v of type int. The ArrayList is the right result type because the number of even values is not known in advance; the array in (b) has a fixed size equal to list.size().

Suggested Marlbridge rubric (7 points)

Topic checks: Topic 4.5, Topic 4.8 and Topic 4.12.