Section 4. Backtracking, Big-O, and Sorting

This week’s section exercises explore the ins and outs of content from weeks 4 and 5, focusing on delving more deeply into recursive backtracking and its applications, plus a bit of Big-O!

Each week, we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter code

Recursive Backtracking

Problem One: Tug-of-War

You are trying to organize a tug-of-war event for a group of people. For each person, you have an int representing the amount of force they can pull with. You'd like to break the group into two teams with exactly equal pulling strength.

Write a function

bool canSplitEvently(const Vector<int>& strengths);

that takes as input a Vector<int> holding all the pulling strengths of the people in the group, then returns whether there is some way to split the group into two teams of exactly equal pulling strength.

/* Given the existing strengths of the two teams, can the people from index
 * nextIndex and onward be split across the two teams to balance out the
 * strengths?
 */
bool canSplitRec(const Vector<int>& strengths,
                 int teamAStrength, int teamBStrength,
                 int nextIndex) {
    /* Base Case: If everyone is assigned, see if the teams have the same
     * strength.
     */
    if (nextIndex == strengths.size()) {
        return teamAStrength == teamBStrength;
    }
    /* Recursive Case: See what happens if we assign the next person to Team
     * A and to Team B. If either option works, there's a split. If neither
     * option works, we need to back up and try something else.
     */
    else {
        return canSplitRec(strengths,
                           teamAStrength + strengths[nextIndex],
                           teamBStrength,
                           nextIndex + 1) ||
               canSplitRec(strengths,
                           teamAStrength,
                           teamBStrength + strengths[nextIndex],
                           nextIndex + 1);
    }
}

bool canSplitEvenly(const Vector<int>& strengths) {
    /* Nice little optimization here: because the roles of the two teams are
     * interchangeable, we can place the first person onto Team A. Otherwise,
     * we'd consider each split twice, once with the teams labeled Team A
     * and Team B, and once with the teams labeled Team B and Team A.
     */
    if (strengths.isEmpty()) {
        return true;
    }

    return canSplitRec(strengths, strengths[0], 0, 1);
}

Problem Two: All Squared Away

Here’s a little number puzzle: can you arrange the numbers 1, 2, 3, …, and 15 in a sequence such that the sum of any two adjacent numbers is a perfect square? (A perfect square is a number that’s the square of an integer. So, for example, 16 = 4² is a perfect square, and 1 = 1² is a perfect square, but 19 isn’t a perfect square). There is indeed a way to do this, which is shown here:

 8,  1,  15,  10,  6,  3,  13,  12,  4,  5,  11,  14,  2,  7,  9

However, you can’t do this with the numbers 1, 2, 3, …, 18, and you can’t do this with the numbers 1, 2, 3, …, 19, but you can do this with the numbers 1, 2, 3, …, 23.

Implement a function

Optional<Vector<int>> findSquareSequence(int n);

that takes as input a number n, then returns an arrangement of the numbers 1, 2, 3, …, n such that each number appears exactly once and the sum of any two adjacent numbers is a perfect square. If there isn't a way to do this, this function returns Nothing. (If $n$ is negative, your function should call error to report an error.)

For convenience, we have provided you with a function

bool isPerfectSquare(int value);

that takes as input an integer and returns whether that integer is a perfect square.

/* Can we use the remaining numbers to build up a sequence, given what the last
 * number used in the sequence was?
 */
Optional<Vector<int>> findSequenceRec(const Set<int>& unused,
                                      Optional<int> last) {
    /* Base Case: If all numbers are used, we have our sequence! */
    if (unused.isEmpty()) {
        return { }; // Empty sequence works
    }

    /* Recursive Case: Some number comes next. Try each of them and see which
     * one we should pick.
     */
    for (int next: unused) {
        /* We can use this if either
         *
         * 1. there is no previous number (we're the first), or
         * 2. we add with the previous number to a perfect square.
         *
         * We rely on short-circuit evaluation below. If last is Nothing,
         * we don't evaluate the isPerfectSquare bit.
         */
        if (last == Nothing || isPerfectSquare(next + last.value())) {
            /* See what happens if we extend with this number. */
            auto result = findSequenceRec(unused - next, next);
            if (result != Nothing) {
                /* result currently holds a square sequence using all the
                 * remaining numbers. We need to put our number at the front
                 * of the sequence.
                 */
                result.value().insert(0, next);
                return result;
            }
        }
    }

    /* Tried all options and none of them worked. Oh well! */
    return Nothing;
}

Optional<Vector<int>> findSquareSequence(int n) {
    /* Validate input. */
    if (n < 0) {
        error("Don't be so negative!");
    }

    /* Build a set of the numbers 1, 2, 3, ..., n. */
    Set<int> options;
    for (int i = 1; i <= n; i++) {
        options += i;
    }
    return findSequenceRec(options, Nothing);
}

Optional<Vector<int>> findSequenceRec(const Set<int>& unused,
                                      const Vector<int>& soFar);

Optional<Vector<int>> findSquareSequence(int n) {
    /* Validate input. */
    if (n < 0) {
        error("Don't be so negative!");
    }

    /* Build a set of the numbers 1, 2, 3, ..., n. */
    Set<int> options;
    for (int i = 1; i <= n; i++) {
        options += i;
    }
    return findSequenceRec(options, { });
}

Optional<Vector<int>> findSequenceRec(const Set<int>& unused,
                                      const Vector<int>& soFar) {
    /* Base Case: If all numbers are used, we have our sequence! */
    if (unused.isEmpty()) {
        return soFar;
    }

    /* Recursive Case: Some number comes next. Try each of them and see which
     * one we should pick.
     */
    for (int next: unused) {
        /* We can use this if either
         *
         * 1. the sequence is empty, so we're first in line, or
         * 2. the sequence is not empty, but we sum to a perfect square
         *    with the previous term.
         */
        if (soFar.isEmpty() ||
            isPerfectSquare(next + soFar[soFar.size() - 1])) {
            /* See what happens if we extend with this number. */
            auto result = findSequenceRec(unused - next, soFar + next);
            if (result != Nothing) {
                return result;
            }
        }
    }

    /* Tried all options and none of them worked. Oh well! */
    return Nothing;
}

Problem Three: Mmmmm… Pancakes!

Bill Gates is famous for a number of things – for his work at Microsoft, for his wide-scale philanthropy through the Bill and Melinda Gates Foundation, and, oddly enough, for a paper he co-authored about flip-ping pancakes.

Imagine you have a stack of pancakes of different diameters. In an ideal pancake stack, the kind of pancake stack you’d see someone photograph and put on Instagram, the pancakes would be stacked in decreasing order of size from bottom to top. That way, all the delicious syrup and melted butter you put on top of the pancakes can drip down onto the rest of the stack. Otherwise, you’ll have a bigger pancake on top of a smaller one, serving as an edible umbrella that shields the lower pancakes from all the deliciousness you’re trying to spread onto them.

The problem with trying to get a stack of pancakes in sorted order is that it’s really, really hard to pull a single pancake out of a stack and move it somewhere else in the stack. On the other hand, it’s actually not that difficult to slip a spatula under one of the pancakes, pick up that pancake and all the pancakes above it, then flip that part of the stack over. For example, in the illustration below, we can flip the top three pancakes in the stack over, then flip the top five pancakes of the resulting stack over:

Your task is to write a function

Optional<Vector<int>> sortStack(Stack<double> pancakes, int numFlips);

that accepts as input a Stack<double> representing the stack of pancakes (with each pancake represented by its width in cm) and a number of flips, then returns a sequence of at most numFlips flips needed to sort the stack. Each flip is specified as how many pancakes off the top of the stack you flipped. For example, the above illustration would correspond to the flip sequence {3, 5}, since we first flipped the top three pancakes, then the top five pancakes. If there is no way to sort the stack with numFlips or fewer flips, you should return Nothing.

Here are some notes on this problem:

• Treat this as a backtracking problem – try all possible series of flips you can make and see whether you can find one that gets everything into sorted order. As a result, don’t worry about efficiency.

• Your solution must be recursive.

• You can assume the pancakes all have different widths and that those widths are positive.

• The Stack here is ordered the way the pancakes are – the topmost pancake is at the top of the stack, and the bottommost pancake is at the bottom.

/* Given a stack of pancakes, returns whether it's sorted. */
bool isSorted(Stack<double> pancakes) {
    double last = -1; // No pancakes have negative size;

    while (!pancakes.isEmpty()) {
        /* Check the next pancake. */
        double next = pancakes.pop();
        if (next < last) {
            return false;
        }

        last = next;
    }

    /* Pancakes are in increasing order! */
    return true;
}

/* Given a stack of pancakes and a flip size, flips that many pancakes
 * on the top of the stack.
 */
Stack<double> flip(Stack<double> pancakes, int numToFlip) {
    /* Take the top pancakes off the stack and run them into a queue.
     * This preserves the order in which they were removed.
     */
    Queue<double> buffer;
    for (int i = 0; i < numToFlip; i++) {
        buffer.enqueue(pancakes.pop());
    }

    /* Move the pancakes back. */
    while (!buffer.isEmpty()) {
        pancakes.push(buffer.dequeue());
    }

    return pancakes;
}

Optional<Vector<int>> sortStack(Stack<double> pancakes, int numFlips) {
    /* Base Case: If the stack is sorted, great! We're done, and no flips
     * were needed.
     */
    if (isSorted(pancakes)) {
        return { }; // No flips
    }
    /* Base Case: If the stack isn't sorted and we're out of flips, then
     * there is no way to sort things.
     */
    else if (numFlips == 0) {
        return Nothing;
    }
    /* Recursive Case: The stack isn't sorted and we still have flips left.
     * The next flip could flip 1, 2, 3, ..., or all N of the pancakes.
     * Try each option and see whether any of them work.
     */
    for (int numToFlip = 1; numToFlip <= pancakes.size(); numToFlip++) {
        /* Make the flip and see if it works. */
        auto result = sortStack(flip(pancakes, numToFlip), numFlips - 1);
        if (result != Nothing) {
            /* The result holds all the remaining flips but doesn't know about
             * the flip we just did. Insert that flip at the beginning.
             */
            result.value().insert(0, numToFlip);
            return result;
        }
    }

    /* If we're here, then no matter which flip we make first, we cannot
     * get the pancakes sorted. Give up.
     */
    return Nothing;
}

Big-O Notation

Problem Four: Runtime Analyses

What are the big-O runtimes of each of the following functions as a function of $n$, where $n$ is either the explicit parameter to the function or the size of the input container?

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

   Solution

   Each iteration of the loop does a constant amount of work, and the number of iterations is $n$. Therefore, we do $O(n)$ total work.

   ---

2. void algiricus(int n) {
       for (int i = 0; i < 137 * n + 42; i++) {
           cout << '*' << endl;
       }
   }
   

   Solution

   This loop runs for $137n + 42$ iterations, which is a linear function of the number of loop iterations. Therefore, the loop runs $O(n)$ times. Since the work done per loop iteration is $O(1)$, the total work done is $O(n)$.

   ---

3. void angustus(int n) {
       for (int i = 0; i < 271828; i++) {
           cout << '*' << endl;
       }
   }
   

   Solution

   This loop always runs $271,828$ times, regardless of what the value of $n$ is. That means that the loop runs $O(1)$ total times, with $O(1)$ meaning "something that does not scale as a function of $n$." Each iteration does $O(1)$ work, so the total work done here is $O(1)$.

   ---

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

   Solution

   This is a great place to apply the maxim "when in doubt, work inside out!" The inner loop does $O(n)$ total work. Since the outer loop runs $O(n)$ times, the total work done is

   \[O(n) \text{ iterations} \times \frac{O(n) \text{ work}}{\text{iteration}} = O(n^2) \text{work.}\]

   ---

5. void bargibanti(int n) {
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               if (j % 2 == 0) { // j is even
                   cout << '*' << endl;
               } else {
                   cout << '?' << endl;
               }
           }
       }
   }
   

   Solution

   This is basically the same code as before, except that the innermost for loop now has an if statement inside it. However, that doesn't matter for our purposes, because the for loop does $O(1)$ work regardless of which branch we take. The code therefore still runs in time $O(n^2)$.

   ---

6. void breviceps(int n) {
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               if (j % 2 == 0) { // j is even
                   cout << '*' << endl;
               } else {
                   for (int k = 0; k < n; k++) {
                       cout << '?' << endl;
                   }
               }
           }
       }
   }
   

   Solution

   Now things get a bit more interesting. Notice that the loop on $k$ does $O(n)$ total work, so we can rewrite the code like this:

   void breviceps(int n) {
       for (int i = 0; i < n; i++) {
           for (int j = 0; j < n; j++) {
               if (j % 2 == 0) { // j is even
                   cout << '*' << endl;
               } else {
                   // do O(n) work
               }
           }
       }
   }
   

   Now, notice that half the time, the loop on $j$ does $O(1)$ work (when $j$ is even), and the other half the time it does $O(n)$ work (when $j$ is odd). Based on that, how much work does the loop on $j$ do? The $j$ loop runs a total of $O(n)$ times. Half of those times it'll be even, and half the times it'll be odd (roughly). Since half of $O(n)$ is still $O(n)$, this means that there are $O(n)$ iterations where the loop does $O(1)$ work, and there are $O(n)$ iterations where it does $O(n)$ work. Collectively, this means that we do $O(n) \times O(1) + O(n) \times O(n) = O(n^2)$ total work in the $j$ loop, so we can rewrite our code like this:

   void breviceps(int n) {
       for (int i = 0; i < n; i++) {
           // do O(n^2) work
       }
   }
   

   Across all $n$ iterations of the outer loop, we therefore do a total of $O(n^3)$ work.

   ---

7. void camelopardalis(const Vector<int>& v) {
       Vector<int> q;
       for (int i = v.size() - 1; i >= 0; i--) {
           q += v[i];
       }
       cout << v.size() << endl;
   }
   

   Solution

   Here, $n$ refers to the total length of the input string v, measured in number of integers.

   Our loop runs for a total of $O(n)$ iterations. The question is how much work each iteration does. If you consult the documentation for the Vector type, you'll find that appending a value to a Vector takes time $O(1)$ and accessing an element of a Vector takes time $O(1)$. Therefore, each loop iteration does $O(1)$ work, so the total work done is $O(n)$.

   ---

8. void capensis(const Vector<int>& v) {
       Set<int> q;
       for (int i = v.size() - 1; i >= 0; i--) {
           q += v[i];
       }
       cout << v.size() << endl;
   }
   

   Solution

   As before, the loop runs for $O(n)$ times. How much work does each iteration do? The answer is not $O(1)$. If you check the documentation for the Set type, you'll find that adding to a set takes time $O(\log n)$. Therefore, we do $n$ iterations of the loop, and each iteration does $O(\log n)$ work, so the total work done is $O(n \log n)$.

   ---

9. void casscsio(Vector<int>& v) {
       while (v.size() >= 5) {
           v = v.subList(5);
       }
   }
   

   Solution

   With a little though, we can see that this loop runs about $\frac{n}{5}$ total times, since each iteration makes the list five elements shorter. The question, then, is how much work each loop iteration does.

   Importantly, the cost of Vector::subList is directly proportional to the length of the sublist being requested. That is, the work done is $O(L)$, where $L$ is the length of the list. If we work out the lengths of those lists, they'll come back as $n - 5$, $n - 10$, $n - 15$, $n - 20$, etc. until we get down to a list of length (roughly) $10$, then (roughly) $5$, then (roughly) $0$. So the question then becomes: what is $0 + 5 + 10 + 15 + 20 + … + (n - 10) + (n - 5)$?

   Intuitively, this quantity counts the number of stars in this approximate triangle shape:

   *****
   **********
   ***************
   ********************
   *************************
   ******************************
   ***********************************
                    ...
   

   This triangle has a base whose size is roughly $n - 5$. Its height is roughly $\frac{n}{5}$. Therefore, the area is something kinda sorta ish like $\frac{n(n - 5)}{10}$, which is $O(n^2)$. But we can see that this is $O(n^2)$ in another way: we're counting up the number of stars that make up a 2D figure, which is asking about its area. Area grows quadratically, so the work done here is $O(n^2)$.

   Another way to see this is to divide everything by five:

   \[0 + 5 + 10 + 15 + \dots + (n - 10) + (n - 5) = 5(0 + 1 + 2 + 3 + \dots + (\frac{n}{5} - 2) + (\frac{n}{5} - 1))\]

   That last sum is the one we saw in class: it works out to $O(n^2)$. Therefore, the total work done is $5 \cdot O(n^2) = O(n^2)$.

   \end{aligned}$$

   ---

Problem Five: Changing Passwords

Looking to change your password? Rather than picking a password that’s a common word or phrase with a bunch of random numbers thrown in, consider using a multi-word password formed by choosing some sequence of totally random words out of the dictionary. Choosing four totally random words, it turns out, tends to be a pretty good way to make a password. Here’s a couple passwords you might make that way:

  RantingCollegersDenoteClinching
  VivificationPandectYawnedCarmine
  DetachednessHowlinglySportscastsVapored
  UnlearnedMockeriesTuskedChuckles
  SharpshootingPreyParaffinsLibeler

We generated these particular passwords using the following piece of code:

string makeRandomPassword(const Vector<string>& wordList) { 
   string result;                                           
   for (int i = 0; i < 4; i++) {                            
      int wordIndex = randomInteger(0, wordList.size() - 1);
      result += wordList[wordIndex];                        
   }                                                        
   return result;                                           
}

When we ran this code, we used a word list containing about 120,000 words. There are other word lists available that we could have picked. The Basic English dictionary, for example, only has about 5,000 words. A more elaborate dictionary called ENABLE has about 180,000 words. It’s therefore not all that unreasonable for us to analyze the efficiency of the above code in terms of the number of words n in our word list.

1. Let $n$ denote the number of words in wordList. What is the big-O time complexity of the above code as a function of $n$? You can assume that the words are short enough that the cost of concatenating four strings together is O(1) and that a random number can be generated in time O(1). Explain how you arrived at your answer. Your answer should be no more than 50 words long.

   Solution

   The cost of looking at the size of the Vector is O(1) and the cost of reading any element it is O(1). We do four reads and call size four times. Each operation takes time O(1). Therefore, this code runs in time O(1).

   ---

2. Let’s suppose that the above code takes 1ms to generate a password when given a word list of length 50,000. Based on your analysis from part (i), how long do you think the above code will take to generate a password when given a word list of length 100,000? Explain how you arrived at your answer. Your answer should be no more than 50 words long.

   Solution

   Since the runtime is O(1), it’s independent of the size of the Vector. Therefore, we’d expect that this code would take 1ms to complete in this case.

   ---

Now, let’s think about how someone might try to break your password. If they know that you chose four totally random English words, they could try logging in using every possible combination of four English words. Here’s some code that tries to do that:

string breakPassword(const Vector<string>& wordList) {
    for (string w1: wordList) {
        for (string w2: wordList) {
            for (string w3: wordList) {
                for (string w4: wordList) {
                    string guess = w1 + w2 + w3 + w4;
                    if (passwordIsCorrect(guess)) {
                        return guess;
                    }
                }
            }
        }
    }
    error("Couldn't break password.");
}

As before, let’s assume that the words in our word list are short enough that the cost of concatenating four of them together is O(1). Let’s also assume that calling the passwordIsCorrect function with a given password takes time O(1).

3. What is the worst-case big-O time complexity of the above piece of code as a function of $n$, the number of words in the word list? Explain how you arrived at your answer. Your answer should be no more than 50 words long.

   Solution

   Working from the inside out: the code inside the loop on w4 does O(1) work. Each of the loops on w4, w3, w2, and w1 run $n$ times. Multiplying this together gives a runtime of O($n^4$).

   ---

4. Imagine that in the worst case it takes 1,000 years to break a four-word password when given a word list of length 50,000. Based on your analysis from part (iii), how long will it take, in the worst case, to break a password when given a word list of length 100,000? Explain how you arrived at your answer. Your answer should be no more than 50 words long.

   Solution

   Since the runtime is O($n^4$), doubling the size of the input will increase the runtime by a factor of $2^4 = 16$. Therefore, we’d expect this would take 16,000 years to complete in the worst-case.

   ---

Searching and Sorting

Problem Six: Binary Search Tracing

Trace the execution of the binary search algorithm looking for the value 137 in the following array of 15 items.

{ 29, 34, 77, 78, 100, 210, 240, 278, 281, 315, 444, 549, 864, 875, 930 }

How many elements does binary search end up looking at in the course of the search?

Problem Seven: Counting Sort

The sorting algorithms we've used thus far are examples of comparison sorts, where we determine the relative ordering of elements by comparing them against one another. This allow us to use our sorting algorithms (selection sort, insertion sort, mergesort, etc.) to sort any types of objects that are comparable this way. We could sort integers, strings (compare them alphabetically), Vector<int>s, etc. However, the downside is that no comparison-based sorting algorithm can run faster than $O(n \log n)$ on average.

Let's suppose that we're specifically sorting int values. Furthermore, suppose we're sorting integers that range from 0 (inclusive) to some maximum value $U$ (exclusive). Counting sort works as follows. First, we build a histogram that shows how many of each of the $U$ possible numbers we have in our array. For example, here's a sample input array whose values are all between 0 and 9, inclusive, and its histogram:

Array:      1 3 2 4 7 1 7 9 5 7 2 4 4 7 4 6 0 2 5 9 6

           +---+---+---+---+---+---+---+---+---+---+
Histogram: | 1 | 2 | 3 | 1 | 4 | 2 | 2 | 4 | 0 | 2 |
           +---+---+---+---+---+---+---+---+---+---+
             0   1   2   3   4   5   6   7   8   9

Once we have the histogram, we can sort the input array by writing out one copy of 0, two copies of 1, three copies of 2, one copy of 3, …, and two copies of 9.

The runtime of counting sort is $O(n + U)$. If $U$ is small - say, we're sorting single-digit numbers - then this runtime may work out to $O(n)$, faster than any comparison-based sorting algorithm! However, if $U$ is large, then it may run much slower than, say, mergesort.

Write a function

void countingSort(Vector<int>& values);

that uses counting sort to sort the vector values. You can assume the values in the array are nonnegative.

/* Given a Vector<int>, returns the largest number in that Vector. */
int maxOf(const Vector<int>& values) {
    /* Bounds-check inputs. */
    if (values.isEmpty()) {
        error("Can't find the maximum of no values.");
    }
    
    int result = values[0];
    for (int i = 1; i < values.size(); i++) {
        result = max(result, values[i]);
    }
    return result;
}

/* Given a list of numbers, creates a histogram from those numbers. */
Vector<int> histogramFor(const Vector<int>& values) {
    /* Create a histogram with the right number of slots. Initially, all values
     * in the histogram will be zero.
     */
    Vector<int> histogram(maxOf(values) + 1);
    
    /* Scan across the input vector, incrementing the histogram values. */
    for (int value: values) {
        histogram[value]++;
    }
    
    return histogram;
}

void countingSort(Vector<int>& values) {
    /* Edge Case: If the array is empty, then it's already sorted. This is
     * needed because we can't take the maximum value of an empty vector.
     */
    if (values.isEmpty()) {
        return;
    }
    
    /* Form the histogram. */
    auto histogram = histogramFor(values);
    
    /* Scan across the histogram writing out the appropriate number of copies
     * of each value. We track the index of the next free spot to write to,
     * as it varies based on how many items we've written out so far.
     */
    int next = 0;
    for (int value = 0; value < histogram.size(); value++) {
        /* Write out the right number of copies. */
        for (int copy = 0; copy < histogram[value]; copy++) {
            values[next] = value;
            next++;    
        }
    }
}