Practice Midterm 4 Solutions

This page contains solutions to Practice Midterm 4.

Question 1: Big-O

This question was designed to allow you to showcase your understanding of best- and worst-case Big-O runtime analysis. It also included a few bugs to get you thinking about edge cases.

a) Base-Case: O(1), Worst-Case: O(n)

See (b) and (c) below for explanations.
Recall that with best-case runtime analysis, we have to assume our input size is arbitrarily large and look for anything that allows us to escape the function faster than in the worst-case. For a refresher, See the section titled "Best- and Worst-Case Runtime" – specifically, the note labeled "Insanely important!" – in the notes from Lecture 9: More Recursion.

b) This function encounters its best-case runtime when our sorted vector has a unique value at its mid index, which is 5 (i.e., mid[5] != mid[4] and mid[5] != mid[6]). In that case, the looping conditions are false straight out of the gate, and so they don't perform any iterations; we skip straight to the return statement at the bottom. So, one possible solution here is as follows:

v: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, k: 100

Note that k has no impact on the runtime. Note also that if the function fails on an unsorted vector, we wouldn't consider that a bug, since the comment above the function asserts that it is only designed to operate on sorted vectors. (Similarly, we would not say that an implementation of binary search has a bug if it failed to locate a value in an unsorted vector.)

c) This function encounters its worst-case runtime when our vector is filled with the same value. In that case, the loops continue until they reach the beginning or end of the vector, respectively – for a total runtime of O(n). Once again, k has no impact on our runtime. So, one possible solution here is as follows:

v: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, k: 100

d) The bug here is that if the function receives an empty vector, mid will be 0, and the second line of the function will attempt to access mid[0], which causes a crash (since there is no element 0 in the vector). We were just looking for a few words here; simply saying "crashes on empty vector" or "attempts to access v[0] if vector is empty and crashes" would suffice.

e) Best-Case: O(1), Worst-Case: O(k)

It might be tempting to say that the worst-case runtime here is O(n), since we know k < n, meaning that n is the "dominant term." However, the loops terminate as soon as we count k occurences of the element at v[mid], giving as a runtime of O(k). (Since k < n and the function terminates after finding k occurrences, we cannot possibly encounter an O(n) runtime here.)
The best-case runtime occurs when both n and k are arbitrarily large, but v[mid] != v[mid-1] and v[mid] != v[mid+1]. In that case, neither of our loops perform any iterations, and we return from the function in O(1) time.

f) Best-Case: O(1), Worst-Case: O(n)

Similar to part (e), it might be tempting to say the worst-case runtime here is O(k), since n < k, making k the "dominant term." However, the worst we can ever do with this function is loop through all the elements in the vector, which would take O(n) time. Since it's impossible to exceed a combined total of n iterations across these loops, and since we know n < k, it's impossible to get an O(k) runtime here.
The best-case runtime here is the same as in part (e). A correct explanation of that runtime requires that we assume both n and k are arbitrarily large.

g) The bug here comes into play when that if k is 1 (or smaller) and v[mid] only occurs once in the sorted vector. In those cases, we would want to return true, since v[mid] occurs at least 1 time. (Similarly, it occurse at least 0 times, at least -1 times, and so on.) However, the only way for this function to return true is for it to enter into at least one of the loops. If v[mid] is unique, we don't enter into either loop; we instead skip to the bottom of the function and return (incorrectly) false. So, one possible solution is as follows:

v: {1, 2, 3, 4, 5}
k: 1
This (broken) function would return: false
A correct version of the function would return: true

Question 2: C++ and ADTs (Inverted Index)

This question was mostly about implementing a given specification and demonstrating that you know how to correctly use ADTs, including nested collection types. It presented some unusual challenges related to moving elements from one nested ADT to another and then performing the careful bookkeeping necessary to avoid accumulation of empty nested ADTs. This question also presented a light exercise in making an appropriate ADT choice to solve part of the problem efficiently.

`incrementFrequency()`

Here's one possible approach to this part of the problem. We expected solutions to embed Set objects within the Map in order to facilitate efficient look-up operations. Given that we're repeatedly searching our nested ADTs, it's important for that operation to be fast.

void incrementFrequency(Map<int, Set<string>>& map, string word) {
    for (int key : map) {
        if (map[key].contains(word)) {
            map[key + 1].add(word);
            map[key].remove(word);
            if (map[key].isEmpty()) {
                map.remove(key);
            }
            return;
        }
    }

    // If we get here, it wasn't found.
    map[1].add(word);
}

`buildInvertedMap()`

Here's one possible approach to this part of the problem. Recall that the problem required buildInvertedMap() to build out the map by calling incrementFrequency().

Map<int, Set<string>> buildInvertedMap(Vector<string>& lines) {
    Map<int, Set<string>> map;

    for (string line : lines) {
        Vector<string> words = stringSplit(line, " ");
        for (string word : words) {
            incrementFrequency(map, word);
        }
    }

    return map;
}

Question 3: Recursion (Cascade)

This was a twist on a classical recursion problem: taking a task that is somewhat straightforward to preform by iterating through a vector, and writing a function to do that recursively. The twist came in the form of multiple restrictions that made the problem a bit more of a puzzle – the main one being that if the function referred to or accessed an element v[i] in any way, another line of the function was not allowed to refer to or access a different element (such as v[i-1] or v[i+1]). This was a fairly challenging puzzle.

Solution 1

Here is one possible approach, which relies on a helper function and a sumSoFar variable that tracks the sum of all the elements we have passed over so far:

void cascade(Vector<int>& v, int sumSoFar)
{
    if (v.size() == 0)
    {
        return;
    }

    v[0] += sumSoFar;
    int thisOne = v.remove(0);

    cascade(v, thisOne);

    v.insert(0, thisOne);
}

void cascade(Vector<int>& v)
{
    cascade(v, 0);
}

Solution 2(a)

Up next is a version that uses a helper function that returns the cumulative sum of all the elements we've already accessed in our recursive calls – which is most useful if we are adding that return value to the element at the tail end of the vector.

Note that while we cannot change the function signature for the wrapper, we can change it for the helper function. In fact, we must change the function signature for the helper; if we didn't, then we'd have two functions with identical function signatures, and our program wouldn't compile.

int cascadeHelper(Vector<int>& v)
{
    if (v.size() == 0)
    {
        return 0;
    }

    int thisOne = v.remove(v.size() - 1);

    int rest = cascadeHelper(v);

    v.add(thisOne + rest);

    return thisOne + rest;
}

void cascade(Vector<int>& v)
{
    cascadeHelper(v);
}

Solution 2(b)

This is a super cheeky twist on Solution 2(a). If we want to re-use the name of our wrapper function when writing our helper function, then we must change the parameters it takes. Otherwise, we'd have two identical function signatures, and our program wouldn't compile. This solution uses a fairly useless second parameter that just forces the helper function to be called rather than the wrapper. We don't recommend doing something like this in the real world, but it's an interesting approach, and we figured we'd share this idea with you just as an interesting oddity.

int cascade(Vector<int>& v, bool isHelper)
{
    if (v.size() == 0)
    {
        return 0;
    }

    int thisOne = v.remove(v.size() - 1);

    int rest = cascade(v, isHelper);

    v.add(thisOne + rest);

    return thisOne + rest;
}

void cascade(Vector<int>& v)
{
    cascade(v, true);
}

Solution 3

This final solution uses a classic recursive idiom we've seen in class: instead of adding and removing elements from the vector, we use an independent variable, k, to keep track of what index we want to process next. Because we're only allowed to add one parameter to our helper (for a total of two parameters), we find ourselves having to work from index v.size() - 1 down to index 0. (If we try to work from index 0 to index v.size() - 1, we don't have a vehicle that allows us to pass our cumulative sum on to the next cell, given the various restrictions in the problem statement.)

int cascade(Vector<int>& v, int k)
{
    if (k < 0)
    {
        return 0;
    }

    v[k] += cascade(v, k - 1);

    return v[k];
}

void cascadeVersion3(Vector<int>& v)
{
    cascade(v, v.size() - 1);
}

Question 4: Recursive Thinking (Permutations)

This problem was designed to give everyone a chance to showcase the understanding they've been cultivating of recursive procedures and, in particular, the order in which recursive calls are made and returned from.

a) BOAST

b) TSAOB

c) all

d) ABOST

e) none

f) none

g) SOBAT and TSOBA

h) some (but not all)

The first permutation this function will print that contains SOBA as a substring is SOBAT. There are permutations printed before and after that one that contain BOA as a substring. For example, BOAST prints before SOBAT, and TBOAS prints after SOBAT.

i) all