Practice Midterm 7 Solutions

This page contains solutions to Practice Midterm 7.

Question 1: C++, ADTs, and Big-O

This question asked you to trace through code and was designed to allow you to showcase your understanding of C++ fundamentals and a few ADTs (vectors, stacks, and queues). It also asked you to give best- and worst-case Big-O runtimes for various functions.

a) {'z', 'x', 'c', 'a', 'b', 'd', 'y'}

b) rlodw

c) zyxdcba

d) dcba

e) Stack

f) Base-Case: O(n2), Worst-Case: O(n2)

  • For all of these runtime questions, note that the best-case runtime for each function was the same as its worst-case runtime. 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.

    See the section titled "Best- and Worst-Case Runtime" – specifically, the note labeled "Insanely important!" – in the notes from Lecture 9: More Recursion.

g) Base-Case: O(n2), Worst-Case: O(n2)

h) Base-Case: O(n3), Worst-Case: O(n3)

i) Base-Case: O(n3), Worst-Case: O(n3)

j) {'y', 'd', 'b', 'a', 'c', 'x', 'z'}

k) v.size() / 2 or (v.size() - 1)/ 2

  • For this one, we accepted either (or both) of answers above. The key insight to this question is that the next element to be removed in a FIFO fashion will always end up being at the middle of the vector. In the case of even-lengthed vectors, however, the exact index where we need to remove from depends in part on the number of insertion operations that got us into our current state – hence the two possibilities for where we might need to remove.


Question 2: C++ and ADTs (Moira's Teashop)

This question was mostly about implementing a given specification and demonstrating that you know how to correctly use ADTs, including various twists on nested collection types.

createVarDescriptionsMap()

This problem gave everyone a chance to showcase what they've learned about working with maps, vectors, and our string processing libraries. There are many ways to implement this function, some of which are just subtle variations on the approaches below.

The following approach uses substr() to create separate key and value variables for each entry:

Map<string, string> createVarDescriptionsMap(Vector<string>& varStrings)
{
    Map<string, string> result;
    for (string elem : varStrings)
    {
        int hashIndex = elem.find('#');
        string key = elem.substr(0, hashIndex);
        string value = elem.substr(hashIndex + 1);

        if (result.containsKey(key))
        {
            error("Repeated variable: " + key);
        }

        result[key] = value;
    }

    return result;
}

This next approach is similar to above, but uses stringSplit() to parse out the key and value variables for each entry.

Map<string, string> createVarDescriptionsMap(Vector<string>& varStrings)
{
    Map<string, string> result;
    for (string elem : varStrings)
    {
        Vector<string> sections = stringSplit(elem, "#");
        string key = sections[0];
        string value = sections[1];

        if (result.containsKey(key))
        {
            error("Repeated variable: " + key);
        }

        result[key] = value;
    }

    return result;
}

createVarLocationsMap()

A primary goal with this problem was to demonstrate an understanding of how to work with nested ADTs; we have a map within a map that tracks indices across multiple layers of a vector of vectors of strings. Solving this one requires careful consideration of what data types we're landing on as we delve into each new layer of our ADTs.

As with the previous problem, there are many ways to implement this function.

This first approach uses varLocationsMap[token][teaDescIdx] to add elements to our submaps, thereby circumventing the need to create a new variable to refer to a submap.

Map<string, Map<int, int>> createVarLocationsMap(Vector<Vector<string>>& teaDescriptions)
{
    Map<string, Map<int, int>> varLocationsMap;

    // Loop over all tea descriptions.
    for (int teaDescIdx = 0; teaDescIdx < teaDescriptions.size(); teaDescIdx++)
    {
        Vector<string> teaDescription = teaDescriptions[teaDescIdx];

        // Loop over all tokens within the tea descriptions.
        for (int tokenIdx = 0; tokenIdx < teaDescription.size(); tokenIdx++)
        {
            string token = teaDescription[tokenIdx];
        
            // Is this token a variable?
            if (startsWith(token, "<") && endsWith(token, ">"))
            {
                // Add it to the map!
                varLocationsMap[token][teaDescIdx] = tokenIdx;        
            }
        }
    }

    return varLocationsMap;
}

The following approach is similar to the one above, but it takes a different approach to determining whether our string is a <variable>, and it uses a submap variable to refer to the nested submaps. Note the need for a reference when creating the submap variable. We let that detail slide while grading, but it's still good to be familiar with what was happening there and why the & was needed in our Map<int, int>& submap declaration.

Map<string, Map<int, int>> createVarLocationsMap(Vector<Vector<string>>& teaDescriptions)
{
    Map<string, Map<int, int>> varLocationsMap;

    // Loop over all tea descriptions.
    for (int teaDescIdx = 0; teaDescIdx < teaDescriptions.size(); teaDescIdx++)
    {
        Vector<string> teaDescription = teaDescriptions[teaDescIdx];

        // Loop over all tokens within the tea descriptions.
        for (int tokenIdx = 0; tokenIdx < teaDescription.size(); tokenIdx++)
        {
            string token = teaDescription[tokenIdx];
            
            // Is this token a variable?
            if (token[0] == '<' && token[token.length() - 1] == '>')
            {
                // Add it to the map!
                Map<int, int>& submap = varLocationsMap[token];
                submap[teaDescIdx] = tokenIdx;        
            }
        }
    }

    return varLocationsMap;
}

Here's yet a third solution, which relies on the map's get() and put() methods. Note that by using put() to place our submap back into our map, we circumvent the need to create a submap a reference variable.

Map<string, Map<int, int>> createVarLocationsMap(Vector<Vector<string>>& teaDescriptions)
{
    Map<string, Map<int, int>> varLocationsMap;

    // Loop over all tea descriptions.
    for (int teaDescIdx = 0; teaDescIdx < teaDescriptions.size(); teaDescIdx++)
    {
        Vector<string> teaDescription = teaDescriptions[teaDescIdx];

        // Loop over all tokens within the tea descriptions.
        for (int tokenIdx = 0; tokenIdx < teaDescription.size(); tokenIdx++)
        {
            string token = teaDescription[tokenIdx];
            
            // Is this token a variable?
            if (startsWith(token, "<") && endsWith(token, ">"))
            {
                // Add it to the map!
                Map<int, int> submap = varLocationsMap.get(token);
                submap.put(teaDescIdx, tokenIdx);
                varLocationsMap.put(token, submap);
            }
        }
    }

    return varLocationsMap;
}

updateVariables()

This final part of the problem asked you to put together all the pieces from parts (a) and (b) to update the tea descriptions in the teaDescriptions vector. A key challenge here involved carefully manipulating nested ADTs. Another significant part of the problem was building an understanding of how the ADTs related to one another and developing a looping strategy to solve the problem appropriately.

Here is one way to solve this problem:

void updateVariables(Vector<Vector<string>>& teaDescriptions,
              Map<string, string>& varDescriptionsMap,
              Map<string, Map<int, int>>& varLocationsMap)
{
    for (string var : varLocationsMap)
    {
        if (!varDescriptionsMap.containsKey(var))
        {
            error("Could not find variable (from varLocationsMap) in varDescriptionsMap:" + var);
        }

        string varDescription = varDescriptionsMap[var];
        Map<int, int>& varLocations = varLocationsMap[var];

        for (int teaDescriptionsIdx : varLocations)
        {
            int wordIdx = varLocations[teaDescriptionsIdx];

            if (teaDescriptions[teaDescriptionsIdx][wordIdx] != var)
            {
                error("String to overwrite does not match the variable!");
            }

            teaDescriptions[teaDescriptionsIdx][wordIdx] = varDescription; 
        }
    }
}


Question 3: Recursion (kPermute)

This problem combined ideas from the permutations and sequences problems covered in class to test an understanding of recursion.

Here is one possible approach:

int kPermute(string str, int k)
{
    if (str == "" && k > 0)
    {
        error("Invalid parameters!");
    }

    return kPermuteHelper(str, k, "");
}

int kPermuteHelper(string str, int k, string soFar)
{
    if (k == 0)
    {
        cout << soFar << endl;
        return 1;
    }

    int sum = 0;

    for(char ch : str)
    {
        sum += kPermuteHelper(str, k - 1, soFar + ch);
    }

    return sum;
}

Here's an alternative approach to the helper function. It's just a slight twist on the one above: rather than decrementing k and stopping when k == 0, this one leaves k unmodified with each recursive call and instead uses the base case to check whether soFar.length() has reached k.

int kPermuteHelper(string str, int k, string soFar)
{
    if (soFar.length() == k)
    {
        cout << soFar << endl;
        return 1;
    }

    int sum = 0;

    for(char ch : str)
    {
        sum += kPermuteHelper(str, k, soFar + ch);
    }

    return sum;
}