Practice Midterm 2 Solutions

Q1) C++ Fundamentals

void diagonalLine(Grid<int>& grid) {
    int row1 = 0;    // Used to store row of 1 in initial grid
    int col1 = 0;    // Used to store column of 1 in initial grid

    // Find the 1 in the initial grid and store in col1, row1
    for (int row = 0; row < grid.numRows(); row++) {
        for (int col = 0; col < grid.numCols(); col++) {
            if (grid[row][col] == 1) {
                row1 = row;
                col1 = col;
            }
        }
    }

    // Fill in diagonal down-right of original location
    int curRow = row1 + 1;
    int curCol = col1 + 1;
    while (curCol < grid.numCols() && curRow < grid.numRows()) {
        grid[curRow][curCol] = 1;
        curRow++;
        curCol++;
    }

    // Fill in diagonal up-left of original location
    curRow = row1 - 1;
    curCol = col1 - 1;
    while (curCol >= 0 && curRow >= 0) {
        grid[curRow][curCol] = 1;
        curRow--;
        curCol--;
    }
}

Q2) ADTS

Map<string, Set<string>> predecessorMap(Vector<string>& input) {
    Map<string, Set<string>> result;
    string lastWord;  // Most-recently-read string, initially empty as a sentinel.
    
    /* Loop over all lines */
    for (string line: input) {
        Vector<string> tokens = tokenize(line);
        for (string token: tokens) {
            if (token != "") {
                token = toLowerCase(token);
                if (lastWord != "") {
                    result[token].add(lastWord);
                }
                lastWord = token;
            }
        }
    }
    return result;
}

Q3) Code study: ADTs and Big-O

a)

• function1 runs in time O(n).
• function2 runs in time O(n).
• function3 runs in time O(n log n).
• function4 runs in time O(n^2).

Some explanations:

In function1, we do n pushes followed by n pops. The cost of each Stack operation is O(1), so this means we’re doing 2n operations at an effective cost of O(1) each, for a net total of O(n). The same is true about Queue operations: each one takes time O(1), which is why function2 takes time O(n) as well.

For function3, inserting an element into a Set takes time O(log n). This means that the cost of inserting n elements is O(n log n). The cost of iterating over the set is also O(n) so the net runtime is O(n log n).

For function4, adding n elements to the end of a Vector takes time O(n). However, removing from the front of a Vector with n elements also takes time O(n), since we have to shift all the other elements back one position. This means that the overall runtime is O(n^2).

b)

• function1 cannot produce the given output.
• function2 will always produce this output.
• function3 will always produce this output.
• function4 will always produce this output.

Some explanations:

In function1, since elements are stored in a Stack, the last element popped is the first element pushed, which would always be zero. Therefore, we’d expect to see a column of zeros in the table, which doesn’t match what’s actually there.

In function2, the last element removed from the Queue is the last element added to the queue, which, here, would be n – 1, matching the output.

In function3, the Set type stores its elements in sorted order. Iterating over the Set, therefore, will visit the elements in ascending order, so the last element iterated over by the loop would be n – 1, matching the output.

Finally, in function4, we remove elements from the Vector in the reverse order in which they’re added, matching the queue’s ordering and making the last element visited exactly n – 1.

c) function2

First, notice that the runtime appears to be O(n); doubling the size of the inputs roughly doubles the runtime. That leaves function1 and function2 as choices, and function1 has the wrong return value. Therefore, we must have run function2.

Q4 Tracing Recursion

a)

Call                    Printed value
----------------------------------------------------
recursionTrace(8)       0 0 0 : 2 4 8
recursionTrace(25)      1 0 0 1 : 3 6 12 25 
recursionTrace(46)      0 1 1 1 0 : 2 5 11 23 46

b)

Call                    Printed value
----------------------------------------------------
sillyFunc(10, 0)        1
sillyFunc(5, 2)         25
sillyFunc(4, 3)         64

c) This function computes a ^ b.

Q5 Recursive Function

int digitSum(int n) {
    if (n < 10) {
        return n;
    } else {
        return digitSum(n / 10) + digitSum(n % 10);
    }
}