Extra Practice Problems (Pre-Midterm)

These problems will give you more practice with concepts covered on the midterm exam.

⚠️ This page is actively maintained. Check back each week for additional problems.

🌱 For your convenience, new problem categories are marked with a sprout emoji each week.

📝 C++ and ADT exercises were added Wednesday, July 1.

⭕️ Big O and ↩️ Recursion exercises were added Tuesday, July 7.

Programming in C++

1. countNumbers (count.cpp)

Topics: Vectors, strings, file reading, while true, conditional statements, Stanford C+++ library

The function countNumbers reads a text file and prints the number of times a user entered number appears in that text file. A user can continually enter numbers until they hit "Enter" or "Return" on their keyboard. Here are some library functions that will be useful for this task:

• readLines, to read all lines from a file stream into a Vector
• stringSplit, to divide a string into tokens
• getLine, to read a line of text entered by the user
• stringIsInteger, to confirm a string of digits is valid integer

In particular you will be asked to write the following function

void countNumbers(string filename)

When given the following file, named numbers.txt, as input, your function should print 1 when a user enters 42. Similarly, when the user enters another number like 9, your function should print 2. Finally, the function ends when the user presses "Return".

42 is the Answer to the Ultimate Question of Life, the Universe, and Everything
This is a negative number: -9
Welcome to CS106B!
I want to own 9 cats and 9 dogs.

/*
 * Function: countNumbers
 * ----------------------
 * Write a program to read through a given file and count the
 * the number of times a user inputed number appears in that file. You  
 * can assume that numbers will be composed entirely of numerical digits, 
 * optionally preceded by a single negative sign.
 */
void countNumbers(string filepath) {
    ifstream in;
    if (!openFile(in, filepath)) {
        return;
    }

    Vector<string> lines = readLines(in);

    while (true) {
        string number = getLine("Enter a number to check (enter to quit): ");
        if (number == "") {
            break;
        }
        if (!stringIsInteger(number)) {
            cout << "Please enter a number" <<endl;
            continue;
        }
        int count = 0;
        for (string line : lines) {
            Vector<string> tokens = stringSplit(line, " ");
            for (string t : tokens) {
                if (t == number) {
                    count ++;
                }
            }
        }
        cout << "Number " << number << " appeared " << count << " times in the file." << endl;
    }
}

2. ASCII Count 'em

Topics: ASCII, strings

Write a function that takes a string as its only argument and returns a count of how many characters in that string fall between 'e' and 'm' (inclusive). In writing this function, the only comparisons you can make are to 'e' and 'm' (i.e., you cannot compare each character to 'f', 'g', 'h', 'i', and so on), and you cannot hard-code any numeric ASCII values (i.e., you cannot hard-code the integers 101 or 109 in your function – which are the ASCII values for 'e' and 'm' respectively – or any other integer values nearby).

The function signature is as follows:

int countEM(string str)

For example, countEM("sponges") should return 2; the only characters in sponges that fall between 'e' and 'm' (inclusive) are 'g' and 'e'. Similarly, countEM("grunge") should return 3; only the characters 'g' (which occurs twice) and 'e' (which occurs once) are in range.

int countEM(string str) {
    int count = 0;
    for (char ch : str) {
        if (ch >= 'e' && ch <= 'm') {
            count++;
        }
    }
    return count;
}

ADTs

1. Mirror

Topic: Grids

Write a function ​mirror​ that accepts a reference to a ​Grid​ of integers as a parameter and flips the grid along its diagonal. You may assume the grid is square; in other words, that it has the same number of rows as columns. For example, the grid below that comes first would be altered to give it the new grid state shown afterwards:

Original state: 
{ { 6, 1, 9, 4},                
  {-2, 5, 8, 12},                  
  {14, 39, -6, 18},             
  {21, 55, 73, -3} }               

Mirrored state: 
 { {6, -2, 14, 21},
   {1, 5, 39, 55},
   {9, 8, -6, 73},
   {4, 12, 18, -3} }

Bonus: How would you solve this problem if the grid were not square?

// solution
void mirror(Grid<int>& grid) {
    for (int r = 0;r < grid.numRows(); r++) {
        // start at r+1 rather than 0 to avoid double-swapping 
        for (int c = r + 1; c < grid.numCols(); c++) { 
            int temp = grid[r][c]; 
            grid[r][c] = grid[c][r]; 
            grid[c][r] = temp;
        } 
    }
}
// bonus 
void mirror(Grid<int>& grid) {
    Grid<int> result(grid.numCols(), grid.numRows());
    for (int r = 0; r < grid.numRows(); r++) {
        for (int c = 0; c < grid.numCols(); c++) {
            result[r][c] = grid[c][r];
        }
    }
    grid = result;
}

2. Collection Mystery

Topics: Stacks, queues

void collectionMystery(Stack<int>& s) 
{ 
    Queue<int> q;
    Stack<int> s2;

    while (!s.isEmpty()) {
       if (s.peek() % 2 == 0) {
            q.enqueue(s.pop()); 
        } else {
            s2.push(s.pop());
        }
    }
    while (!q.isEmpty()) {
        s.push(q.dequeue()); 
    }
    while(!s2.isEmpty()) { 
        s.push(s2.pop());
    }
    cout<< s << endl;
}

Write the output produced by the above function when passed each of the following stacks. Note that stacks and queues are written in ​front to back order, with the oldest element on the left side of the queue/stack.

Stacks:

{1, 2, 3, 4, 5, 6}                ________________________________________
{42, 3, 12, 15, 9, 71, 88}        ________________________________________
{65, 30, 10, 20, 45, 55, 6, 1}    ________________________________________

{6, 4, 2, 1, 3, 5}
{88, 12, 42, 3, 15, 9, 71}
{6, 20, 10, 30, 65, 45, 55, 1}

3. Reversing a Map

Topic: Nested data structures

Write a function

that, given a Map<string, int> that associates string values with integers, produces a Map<int, Set<string>> that’s essentially the reverse mapping, associating each integer value with the set of strings that map to it. (This is an old job interview question from 2010.)

Map<int, Set<string>> reverseMap(Map<string, int>& map) {
    Map<int, Set<string>> result;
    for (string oldKey : map) {
        // Note: we check containsKey here but this isn't 
        // necessary since Maps auto-initialize values 
        // on square bracket access if the key is not 
        // present
        if (!result.containsKey(map[oldKey])) {
            result[map[oldKey]] = {};
        }
        result[map[oldKey]].add(oldKey);
    }
    return result;
}

4. Stack vs Vector showdown

Topics: Stacks, vectors

We will analyze a simple program that emulates a text editor. The program accepts input from a user which can be of two forms:

• ADD string: This adds a one word string into the text editor

• UNDO: This removes the most recently added string from the editor.

When the user finishes providing input (by hitting ENTER), we print a string which represents the words in the text editor, in the order they were added.

Example: If we receive user input like "ADD I", "ADD Love", "ADD 106A", "UNDO", "ADD 106B", the program prints out "I love 106B".

int main() {
    Stack<string> words;

    while (true) {
        string command = getLine("Enter a command (press enter to quit): ");
        if (command == "") {
            break;
        }

        Vector<string> splitCommands = stringSplit(command, " ");
        if (splitCommands[0] == "ADD") {
            words.push(splitCommands[1]);
        } else if (splitCommands[0] == "UNDO") {
            words.pop();
        }
    }

    string result;
    while (!words.isEmpty()) {
        result = words.pop() + result;
    }
    cout << result << endl;
    return 0;
}

First, trace through this program on the example input provided above and see if you can discern how it's working. If necessary, refer to the Stanford C++ Library docs to see what functions like getLine() and stringSplit are doing.

Next, run the program, entering the provided inputs, and observe its output. Does the output match your expectation from having read the code? If not, use the debugger to step through the program and see where its behavior deviates from what you expected. After that, try different outputs and ensure the output is what you'd expect.

Finally, see if you can take at least an hour-long break from the problem and then try to code up a program that does the same thing without referring back to the code on this page and without having attempted to completely memorize the initial solution the first time around.

5. Maps

Topic: Maps

Here, we analyze a simple program that uses maps to count elements in a vector:

Map<string, int> countElements(Vector<string>& names) {
    Map<string, int> frequency;
    for (string name: names) {
        // When using the square bracket syntax([]), we don't need to initialize
        // names in the map before adding unto it. If name doesn't already exist
        // in the map, [] in the Stanford Map will initialize it for us.
        frequency[name] += 1;
    }
    return frequency;
}

What will this function return if you pass it a vector of strings (some of which are repeated)? Verify that it behaves as expected by creating a new program that calls this function and then prints out the map that it returns. Check that you're understanding how this program is working and that you understand where the resulting map's key/value pairs are coming from.

🌱 Big-O

1. Oh No, Big-O, Too Slow

Topics: Big-O, code analysis, ADTs

What is the Big O runtime of the following functions, in terms of the variable N.

Code Snippet A

Vector<int> v;
for (int i = 1; i <= N + 2; i++) {
    v.add(i);
}

for (int i = 1; i < N; i++) {
    v.insert(0, i);
}

Code Snippet B

Set<string> s;
for (int i = 1; i <= N - 5; i++) {
    s.add(i);
}

Code Snippet C

Map<int, int> m;
for (int i = 1; i <= 3*N; i++) {
    m[i] = i * 4;
}

Code Snippet D

Stack<int> s;
for (int i = 1; i <= N; i++) {
    s.push(i)
}

for (int i = 1; i <= N/2; i++) {
    s.pop(i)
}

Code Snippet A has a runtime complexity of O(N^2): The first for loop runs in 
O(N), because adding to a vector is constant time O(1), and we add N time. The
second for loop runs N times, but inside this loop we perform an O(N) 
operation, which is inserting at the front of a vector. Therefore Big O of 
second loop is O(N^2). This makes O(N) + O(N^2) = O(N^2), because we only pick 
the highest order Big O.

Code Snippet B has a runtime complexity of O(NlogN): The first for loop runs in 
N. Inside of the loop, we perform an O(logN) operation, which is adding to a set. 
This makes O(N * logN) = O(NlogN)

Code Snippet C has a runtime complexity of O(NlogN): This is very similar to B 
above. Inserting in a map also runs in O(logN). If we do that N times, we get 
O(NlogN).

Code Snippet D has a runtime complexity of O(N):  Pushing unto a stack runs in 
O(1) time, so the first for loop runs in O(N). Popping off a stack runs in O(1)
time so the second for loop runs in O(N/2) = O(N). In total, O(N) + O(N) = O(N), 
since we throw away multipliers.

2. More Big-O

Topics: Big-O, code analysis, ADTs

Below are five functions. Determine the big-O runtime of each of those pieces of code, in terms of the variable n.

void function1(int n) {
    for (int i = 0; i < n; i++) {
        cout << '*' << endl;
    }
}

void function2(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << '*' << endl;
        }
    }
}

void function3(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            cout << '*' << endl;
        }
    }
}

void function4(int n) {
    for (int i = 1; i <= n; i *= 2) {
        cout << '*' << endl;
    }
}

Finally, what is the big-O runtime of this function in terms of n, the number of elements in v?

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        Vector<int> values = v.subList(0, i);
        for (int j = 0; j < values.size(); j++) {
            result += values[j];
        }
    }
    return result;
}

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        Vector<int> values = v.subList(0, i);
        do O(i) work;
    }
    return result;
}

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        do O(i) work;
        do O(i) work;
    }
    return result;
}

int squigglebah(Vector<int>& v) {
    int result = 0;
    for (int i = 0; i < v.size(); i++) {
        do O(i) work;
    }
    return result;
}

🌱 Recursion

1. Recursion Mystery Part 1

Topics: Recursive function calls, return value tracing

Code Snippet A

int recursionMystery(int x, int y) {
    if (x < y) {
        return x;
    } else {
        return recursionMystery(x - y, y);
    }
}

For each call to the above recursive function, indicate what value is returned by the function call.

Call                                   Return value  

recursionMystery(6, 13);               ______________
recursionMystery(14, 10);              ______________
recursionMystery(37, 12);              ______________

2. Recursion Mystery Part 2

Topics: Recursive function calls, output tracing

void recursionMystery2(int x, int y) {
    if (y == 1) { 
        cout << x;
    } else {
        cout << (x * y) << ", ";
        recursionMystery2(x, y - 1);
        cout << ", " << (x * y);
    } 
}

For each call to the above recursive function, write the output that would be produced, as it would appear on the console.

Call                                   Output
        
recursionMystery2(4, 1);        ___________________________________
recursionMystery2(4, 2);        ___________________________________
recursionMystery2(8, 2);        ___________________________________
recursionMystery2(4, 3);        ___________________________________
recursionMystery2(3, 4);        ___________________________________

3. Recursion Tracing

Topics: Recursion, strings, recursion tracing

Below is a recursive function to reverse a string.

string reverseOf(string s) {
    if (s.empty()) {
        return "";
    } else {
        return reverseOf(s.substr(1)) + s[0];
    }
}

Trace through the execution of reverseOf("stop") along the lines of what we did in lecture, showing recursive call information for each call that’s made and how the final value gets computed.

4. Sum of Squares

Topics: Recursion

Write a recursive function named sumOfSquares that takes an int n and returns the sum of squares from 1 to n. For example, sumOfSquares(3)should return 1^2 + 2^2 + 3^2 = 14. If n is negative, you should report an error to that effect.

int sumOfSquares(int n) {
    if (n < 0) {
        error("Value of provided n was negative");
    } else if (n == 0) {
        return 0;
    } else {
        return n * n + sumOfSquares(n-1);
    }
}

5. Zig Zag

Topics: Recursion, printing output to console

Write a recursive function named zigzag that returns a string of n characters as follows. The middle character (or middle two characters if n is even) is an asterisk (*). All characters before the asterisks are '<'. All characters after are '>'. Report an error if n is not positive.

Call            Output
zigzag(1)       * 
zigzag(4)       <**> 
zigzag(9)       <<<<*>>>>

string zigzag(int n) {
    if (n < 1) {
        error("The value of n was negative");
    } else if (n == 1) {
        return "*";
    } else if (n == 2) {
        return "**";
    } else {
        return "<" + zigzag(n-2) + ">";
    }
}

6. Double Stack

Topics: Recursion, stacks

Write a recursive function named doubleStack that takes a reference to a stack of ints and replaces each integer with two copies of that integer. For example, if s stores {1, 2, 3}, then doubleStack(s) changes it to {1, 1, 2, 2, 3, 3}.

void doubleStack(Stack<int>& s) 
{ 
    if (!s.isEmpty()) {
        int n = s.pop();
        doubleStack(s); 
        s.push(n); 
        s.push(n);
    }
}

7. String Subsequences

Topics: Recursion, verifying properties

Write a recursive function named isSubsequence that takes two strings and returns true if the second string is a subsequence of the first string. A string is a subsequence of another if it contains the same letters in the same order, but not necessarily consecutively. You can assume both strings are already lower-cased.

Call                                    Output
isSubsequence("computer", "core")       false 
isSubsequence("computer", "cope")       true 
isSubsequence("computer", "computer")   true

bool isSubsequence(string big, string small) 
{ 
    if (small.empty()) {
        return true;
    } else if (big.empty()) {
        return false;
    } else {
        if (big[0] == small[0]) {
            return isSubsequence(big.substr(1), small.substr(1));
        } else {
            return isSubsequence(big.substr(1), small);
        } 
    }
}

8. Recursion and Time Complexity and Exponents, (Big-)O My

Topics: Recursion, time complexity, Big-O, algorithm comparison

Below is a simple function that computes the value of m^n when n is a nonnegative integer:

int raiseToPower(int m, int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        result *= m;
    }
    return result;
}

1) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1) to multiply two numbers.

2) If it takes 1 microsecond (μs) to compute raiseToPower(100, 100), approximately how long will it take to compute raiseToPower(200, 10000)?

Below is a recursive function that computes the value of m^n when n is a nonnegative integer:

int raiseToPower(int m, int n) {
    if (n == 0) return 1;
    return m * raiseToPower(m, n - 1);
}

3) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1) to multiply two numbers.

4) If it takes 1μs to compute raiseToPower(100, 100), approximately how long will it take to compute raiseToPower(200, 10000)?

Here’s an alternative recursive function for computing m^n that uses a technique called exponentiation by squaring. The idea is to modify the recursive step as follows:

• If n is an even number, then we can write n as n = 2k. Then m^n = m^(2k) = (m^k)^2.
• If n is an odd number, then we can write n as n = 2k + 1. Then m^n = m^(2k+1) = m * m^(2k) = m * (m^k)^2.

Based on this observation, we can write this recursive function:

int raiseToPower(int m, int n) {
    if (n == 0) {
        return 1;
    } else if (n % 2 == 0) {
        int halfPower = raiseToPower(m, n / 2);
        return halfPower * halfPower;
    } else {
        int halfPower = raiseToPower(m, n / 2);
        return m * halfPower * halfPower;
    }
}

5) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1) to multiply two numbers.

6) If it takes 1μs to compute raiseToPower(100, 100), approximately how long will it take to compute raiseToPower(200, 10000)?