⚠️ This page is not current. It is an archive from Winter Quarter 2024.
The current quarter's site is at this link.

More Practice Problems

Written by Clinton Kwarteng, drawing upon materials from previous quarters.

These problems will give you more practice with concepts covered on the mid-quarter exam. Note that some of these questions might involve topics we have not yet covered in class.

1) References Available Upon Request

Topic: Reference parameters, range-based for loops

Reference parameters are an important part of C++ programming, but can take some getting used to if you’re not familiar with them. Trace through the following code. What does it print?

void printVector(Vector<int>& values) {
    for (int elem: values) {
        cout << elem << " ";
    }
    cout << endl;
}

void maui(Vector<int> values) {
    for (int i = 0; i < values.size(); i++) {
        values[i] = 1258 * values[i] * (values[2] - values[0]);
    }
}

void moana(Vector<int>& values) {
    for (int elem: values) {
        elem *= 137;
    }
}

void heihei(Vector<int>& values) {
    for (int& elem: values) {
        elem++;
    }
}

Vector<int> teFiti(Vector<int>& values) {
    Vector<int> result;
    for (int elem: values) {
        result += (elem * 137);
    }
    return result;
}

int main() {
    Vector<int> values = { 1, 3, 7 };
    maui(values);
    printVector(values);
    moana(values);
    printVector(values);
    heihei(values);
    printVector(values);
    teFiti(values);
    printVector(values);
    return 0;
}

Here’s the output from the program:

Here’s a breakdown of where this comes from:

The maui function takes its argument by value, so it’s making changes to a copy of the original vector, not the vector itself. That means that the values are unchanged back in main.
The moana function uses a range-based for loop to access the elements of the vector. This makes a copy of each element of the vector, so the changes made in the loop only change the temporary copy and not the elements of the vector. That makes that the values are unchanged back in main.
heihei, on the other hand, uses int& as its type for the range-based for loop, so in a sense it’s really iterating over the elements of the underlying vector. Therefore, its changes stick.
The teFiti function creates and returns a new vector with a bunch of updated values, but the return value isn’t captured back in main.

2) Pig-Latin (`piglatin.cpp`)

Topics: Strings, reference parameters, return types

Write two functions, pigLatinReturn and pigLatinReference, that accept a string and convert said string into its pig-Latin form. To convert a string into pig-Latin, you must follow these steps:

Split the input string into 2 strings: a string of characters BEFORE the first vowel, and a string of characters AFTER (and including) the first vowel.
Append the first string (letters before the first vowel) to the second string.
Append the string "ay" to the resulting string.

Here are a few examples…

nick -> icknay

chase -> asechay

chris -> ischray

You will need to write this routine in two ways: once as a function that returns the pig-Latin string to the caller, and once as a function that modifies the supplied parameter string and uses it to store the resulting pig-Latin string. These will be done in pigLatinReturn and pigLatinReference, respectively. You may assume that your input is always a one-word, all lowercase string with at least one vowel.

Here's a code example of how these functions differ…

string name = "julie";
string str1 = pigLatinReturn(name);
cout << str1 << endl; // prints "uliejay"

pigLatinReference(name);
cout << name << endl; // prints "uliejay"

Once you've written these functions, discuss with your section the benefits and drawbacks of these two approaches. Which do you feel is easier to write? Which do you think is more convenient for the caller? Do you think one is better style than the other?

// Use const because VOWELS won't change -- no need to declare repeatedly
// in isVowel.
const string VOWELS = "aeiouy";

// Helper function, which I'd highly recommend writing!
bool isVowel(char ch) {
    // A little kludgy, but the handout guarantees that
    // ch will ALWAYS be lower case :)
    // NOTE: For an assignment, you probably want a more robust isVowel.
    return VOWELS.find(ch) != string::npos;
}

string pigLatinReturn(string input) {
    int strOneIndex = 0;
    for (int i = 0; i < input.length(); i++) {
        if (isVowel(input[i])) {
            strOneIndex = i;
            break;
        }
    }
    string strOne = input.substr(0, strOneIndex);
    string strTwo = input.substr(strOneIndex);
    return strTwo + strOne + "ay";
}

void pigLatinReference(string &input) {
    int strOneIndex = 0;
    for (int i = 0; i < input.length(); i++) {
        if (isVowel(input[i])) {
            strOneIndex = i;
            break;
        }
    }
    string strOne = input.substr(0, strOneIndex);
    string strTwo = input.substr(strOneIndex);
    input = strTwo + strOne + "ay";
}

Notice how similar these two approaches are – the only difference is how the result is handled at the very end. To address the discussion questions, although the pigLatinReference function is marginally more efficient because it doesn't need to make a copy of the input string, pigLatinReturn is probably more intuitive for both the caller and the writer: if the function's job is to somehow output some product, returning is the most explicit way to do so. In that way, a function that returns is also better style – it's makes the purpose of the function clearer to the reader.

If you wanted to combine the efficiency of pigLatinReference with the clarity of pigLatinReturn, I would recommend writing a function that takes in the input string by const reference, basically

string pigLatin(const string &input);

Although the const isn't explicitly necessary, it's nice to have because you never need to modify input. Moreover, you still get the efficiency gains from pass-by-reference while also writing very-understandable code.

3) 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;
}

4) Check Balance (`balance.cpp`)

Topic: Stacks

Write a function named checkBalance that accepts a string of source code and uses a Stack to check whether the braces/parentheses are balanced. Every ( or { must be closed by a } or ) in the opposite order. Return the index at which an imbalance occurs, or -1 if the string is balanced. If any ( or { are never closed, return the string's length.

Here are some example calls:

//   index    0123456789012345678901234567
checkBalance("if (a(4) > 9) { foo(a(2)); }") 
// returns -1 (balanced)

//   index    01234567890123456789012345678901
checkBalance("for (i=0;i<a;(3};i++) { foo{); )")
// returns 15 because } is out of order

//   index    0123456789012345678901234
checkBalance("while (true) foo(); }{ ()")
// returns 20 because } doesn't match any {

//   index    01234567
checkBalance("if (x) {")
// returns 8 because { is never closed

int checkBalance(string code) {
    Stack<char> parens;
    for (int i = 0; i < code.length(); i++) {
        char c = code[i];
        if (c == '(' || c == '{') {
            parens.push(c);
        } else if (c == ')' || c == '}') {
            if (parens.isEmpty()) {
                return i;
            }
            char top = parens.pop();
            if ((top == '(' && c != ')') || (top == '{' && c != '}')) {
                return i;
            }
        }
    }

    if (parens.isEmpty()) {
        return -1; // balanced
    } 
    return code.length();
}

5) Collection Mystery

Topics: Stacks and 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}

6) Twice

Topic: Sets

Write a function named twice that takes a vector of integers and returns a set containing all the numbers in the vector that appear exactly twice.

Example: passing {1, 3, 1, 4, 3, 7, -2, 0, 7, -2, -2, 1} returns {3, 7}.

Bonus: do the same thing, but you are not allowed to declare any kind of data structure other than sets.

// solution
Set<int> twice(Vector<int>& v) {
    Map<int, int> counts;
    for (int i : v) {
        counts[i]++;
    }
    Set<int> twice;
    for (int i : counts) {
        if (counts[i] == 2) {
            twice += i;
        }
    }
    return twice;
}

// bonus
Set<int> twice(Vector<int>& v) {
    Set<int> once;
    Set<int> twice;
    Set<int> more;
    for (int i : v) {
        if (once.contains(i)) {
            once.remove(i);
            twice.add(i);
        } else if (twice.contains(i)) {
            twice.remove(i);
            more.add(i);
        } else if (!more.contains(i)) {
            once.add(i);
        }
    }
    return twice;
}

7) Reversing a Map

Topic: Nested data structures

Write a function

Map<int, Set<string>> reverseMap(Map<string, int>& map)

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.)

Here’s one possible implementation.

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;
}

8) 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.

9) More Big O

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;
}

The runtime of this code is O(n): We print out a single star, which takes time O(1), a total of n times.
The runtime of this code is O(n^2). The inner loop does O(n) work, and it runs O(n) times for a net total of O(n^2) work.
This one also does O(n^2) work. To see this, note that the first iteration of the inner loop runs for n – 1 iterations, the next for n – 2 iterations, then n – 3 iterations, etc. Adding all this work up across all iterations gives (n – 1) + (n – 2) + … + 3 + 2 + 1 + 0 = O(n^2).
This one runs in time O(log n). To see why this is, note that after k iterations of the inner loop, the value of i is equal to 2^k. The loop stops running when 2^k exceeds n. If we set 2^k = n, we see that the loop must stop running after k = log₂ n steps.

Another intuition for this one: the value of i doubles on each iteration, and you can only double O(log n) times before you overtake the value n.

For the final function, Let’s follow the useful maxim of "when in doubt, work inside out!"" The innermost for loop (the one counting with j) does work proportional to the size of the values list, and the values list has size equal to i on each iteration. Therefore, we can simplify this code down to something that looks like this:

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;
}

Now, how much work does it take to create the values vector? We’re copying a total of i elements from v, and so the work done will be proportional to i. That gives us this:

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;
}

Remember that doing O(i) work twice takes time O(i), since big-O ignores constant factors. We’re now left with this:

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

This is the same pattern as function2 in the previous problem, and it works out to O(n^2) total time.

10) 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);              ______________

6

4

1

11) 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);        ___________________________________

4

8, 4, 8

16, 8, 16

12, 8, 4, 8, 12

12, 9, 6, 3, 6, 9, 12

12) 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.

Our initial call to reverseOf("stop") fires off a call to reverseOf("top"). This call fires off a call to reverseOf("op"). This in turn calls reverseOf("p"). This in turn calls reverseOf(""). This triggers the base case and returns the empty string. (Notice that the reverse of the empty string "" is indeed the empty string ""). We now append p to return "p". We now append o to return "po". We append t to return "pot". And finally we append s to return "pots" back to whoever called us. Yay!

13) 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);
    }
}

14) 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);
    }
}

15) 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);
        } 
    }
}

16) Recursion and Time Complexity and Exponents, (Big-)Oh 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)?

This function runs in time O(n). It runs the loop n times, at each step doing O(1) work. There is no dependence on m in the runtime.
We know that this code runs in time O(n), so it scales roughly linearly with the size of n. Therefore, if it took 1μs to compute a value when n = 100, it will take roughly 100 times longer when we plug in n = 10000. As a result, we’d expect this code would take about 100μs to complete.
If we trace through the recursion, we’ll see that we make a total of n recursive calls, each of which is only doing O(1) work. Adding up all the work done by these recursive calls gives us a total of O(n) work, as before.
As before, this should take about 100μs.
Notice that each recursive call does O(1) work (there are no loops anywhere here), then calls itself on a problem that’s half as big as the original one. This means that only O(log n) recursive calls will happen (remember that repeatedly dividing by two is the hallmark of a logarithm), so the total work done here is O(log n).
We know that the runtime when n = 100 is roughly 1μs. Notice that 100^2 = 10,000, so we’re essentially asking for the runtime of this function when we square the size of the input. Also notice that via properties of logarithms that log n^2 = 2 log n. Therefore, since we know the runtime grows roughly logarithmically and we’ve squared the value of n, this should take about twice as long as before, roughly 2μs.

17) Longest Common Subsequence

Topic: Recursive Backtracking

Write a recursive function named longestCommonSubsequence that returns the longest common subsequence of two strings passed as arguments. Some example function calls and return values are shown below.

Recall that if a string is a subsequence of another, each of its letters occurs in the longer string in the same order, but not necessarily consecutively.

Hint: In the recursive case, compare the first character of each string. What one recursive call can you make if they are the same? What two recursive calls do you try if they are different?

longestCommonSubsequence("cs106a", "cs106b") --> "cs106" 
longestCommonSubsequence("nick", "julie") --> "i" 
longestCommonSubsequence("karel", "c++") --> "" 
longestCommonSubsequence("she sells", "seashells") --> "sesells"

string longestCommonSubsequence(string s1, string s2) {
	if (s1.length() == 0 || s2.length() == 0) {
		return "";
 	} else if (s1[0] == s2[0]) {
 		return s1[0] + longestCommonSubsequence(s1.substr(1), 
 							s2.substr(1));
 	} else {
 		string choice1 = longestCommonSubsequence(s1, s2.substr(1));
		string choice2 = longestCommonSubsequence(s1.substr(1), s2);
		if (choice1.length() >= choice2.length()) {
			return choice1;
		} else {
			return choice2;
		}
	}
}

18) Recursion (`recursion.cpp`)

Imagine you have a 2 × n grid that you’d like to cover using 2 × 1 dominoes. The dominoes need to be completely contained within the grid (so they can’t hang over the sides), can’t overlap, and have to be at 90° angles (so you can’t have diagonal or tilted tiles). There’s exactly one way to tile a 2 × 1 grid this way, exactly two ways to tile a 2 × 2 grid this way, and exactly three ways to tile a 2 × 3 grid this way (can you see what they are?) Write a recursive function

int numWaysToTile(int n)

that, given a number n, returns the number of ways you can tile a 2 × n grid with 2 × 1 dominoes.

If you draw out a couple of sample tilings, you might notice that every tiling either starts with a single vertical domino or with two horizontal dominoes. That means that the number of ways to tile a 2 × n (for n ≥ 2) is given by the number of ways to tile a 2 × (n – 1) grid (because any of them can be extended into a 2 × n grid by adding a vertical domino) plus the number of ways to tile a 2 × (n – 2) grid (because any of them can be extended into a 2 × n grid by adding two horizontal dominoes). From there the question is how to compute this. You could do this with regular recursion, like this:

int numWaysToTile(int n) {
    /* There's one way to tile a 2 x 0 grid: put down no dominoes. */
    if (n == 0) return 1;

    /* There's one way to tile a 2 x 1 grid: put down a vertical domino. */
    if (n == 1) return 1;
    
    /* Recursive case: Use the above insight. */
    return numWaysToTile(n - 1) + numWaysToTile(n - 2);
}

19) Cracking Passwords

Topic: Recursive Backtracking

Write a function crack that takes in the maximum length a site allows for a user's password and tries to find the password into an account by using recursive backtracking to attempt all possible passwords up to that length (inclusive). Assume you have access to the function bool login(string password) that returns true if a password is correct. You can also assume that the passwords are entirely alphabetic and case-sensitive. You should return the correct password you find, or the empty string if you cannot find the password. You should return the empty string if the maximum length passed is 0 and raise an error if the length is negative.

Security note: The ease with which computers can brute-force passwords is the reason why login systems usually permit only a certain number of login attempts at a time before timing out. It’s also why long passwords that contain a variety of different characters are better! Try experimenting with how long it takes to crack longer and more complex passwords. See the comic here for more information: https://xkcd.com/936/

string crackHelper(string soFar, int maxLength) {
	if (login(soFar)) {
		return soFar;
	}
	if (soFar.size() == maxLength) {
		return "";
	}
	for (char c = 'a'; c <= 'z'; c++) {
		string password = crackHelper (soFar + c, maxLength);
		if (password != "") {
			return password;
		}
 		// Also check uppercase
 		char upperC = toupper(c);
 		password = crackHelper (soFar + upperC, maxLength);
		if (password != "") {
 			return password;
 		}
 	}
	return "";
}

string crack(int maxLength) {
	if (maxLength < 0) {
 		error("max length cannot be negative!);";
	}
 	return crackHelper("", maxLength);
}

20) Some Pointers on Cats

Topics: Pointer tracing and memory diagrams

Trace through the following function and draw the program’s memory at the designated spot. Indicate which variables are on the stack and which are on the heap, and indicate orphaned memory. Indicate with a question mark (?) memory that we don’t know the values of.

struct Lion {
	int roar;
	int *meow;
	int purr[2];
};

struct Savanna {
	int giraffe;
	Lion cat;
	Lion *kitten;
};

Lion *explore(Savanna *prairie) {
	Lion *leader = &(prairie->cat);
	leader->meow = new int;
	*(leader->meow) = 2;
	prairie = new Savanna;
	prairie->cat.roar = 6;
	prairie->kitten = leader;
	prairie->kitten->roar = 8;
	prairie->kitten->meow = &(prairie->kitten->purr[1]);
	leader->purr[0] = 4;
	return leader;
}

void kittens() {
	Savanna *habitat = new Savanna[3];
	habitat[1].giraffe = 3;
	habitat[1].kitten = nullptr;
	habitat[0] = habitat[1];
	habitat[2].kitten = explore(habitat);
	habitat[2].kitten->roar = 4;
	
	// DRAW THE MEMORY AS IT LOOKS HERE
}

Orphaned memory (memory on the heap that we no longer have access to but that was not freed) is represented with dotted lines. For a full walkthrough of the solution, check out: https://tinyurl.com/CatsPointers.