This week’s section exercises provide practice with Big-O and begin our exploration of recursion with some interesting problems!
Remember that every 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:
1. Big O, basics
Topics: Big-O, code analysis
What is the Big O runtime of the following functions, in terms of the variable N?
Code Snippet A
int sum = 0;
for (int i = 1; i <= N + 2; i++) {
sum++;
}
for (int j = 1; j <= N * 2; j++) {
sum++;
}
Code Snippet B
int sum = 0;
for (int i = 1; i <= N - 5; i++) {
for (int j = 1; j <= N - 5; j += 2) {
sum++;
}
}
Code Snippet C
int sum = 0;
for (int i = 1; i <= 10000000; i++) {
sum ++;
}
Code Snippet D
int sum = 0;
for (int i = 0; i < 1000000; i++) {
for (int j = 1; j <= i; j++) {
sum += N;
}
for (int j = 1; j <= i; j++) {
sum += N;
}
for (int j = 1; j <= i; j++) {
sum += N;
}
}
Code Snippet E
int sum = 0;
for (int i = 1; i <= N; i *= 2) {
sum ++;
}
Code Snippet A has a runtime complexity of O(N): The first for loop runs in O(N),
the second also runs in O(N). This makes O(N) + O(N) = O(2N) = O(N), because we
throw away constants
Code Snippet B has a runtime complexity of O(N^2): The code in the innermost for
loop is just a sum so that runs in constant time, O(1). The j for loop iterates
a total of (N - 5)/2 times which is equal to O(N) since we ignore constants and
scalars. The outermost for loop also runs in O(N). In total we get
O(1) * O(N) * O(N) = O(N^2)
Code Snippet C has a runtime complexity of O(1): This loop doesn't depend on N
at all, and loops up to a constant 10000000. Therefore runtime is O(1)
Code Snippet D has a runtime complexity of O(1): This is also constant time. The
outermost for loop loops up until 1000000, which is constant. The 3 inner loops
all loop until i, which will be always less than 1000000. Therefore total
runtime is O(1)
Code Snippet E has a runtime complexity of O(logN): This runs in logarithmic
time, O(logN). You can see this by counting the number of times it takes i to get to
n. i starts at 1, then jumps to 2, then 4, ..., n. It takes logN steps to get
to N. This is similar to logarithmic runtime analysis in class that starts from
n and drops down to 1.
2. 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!
3. Random Shuffling (shuffle.cpp)
How might the computer shuffle a deck of cards? This problem is a bit more complex than it might seem, and while it's easy to come up with algorithms that randomize the order of the cards, only a few algorithms will do so in a way that ends up generating a uniformly-random reordering of the cards.
One simple algorithm for shuffling a deck of cards is based on the following idea:
- Choose a random card from the deck and remove it.
- Shuffle the rest of the deck.
- Place the randomly-chosen card on top of the deck. Assuming that we choose the card that we put on top uniformly at random from the deck, this ends up producing a random shuffle of the deck.
Write a function
string randomShuffle(string input)
that accepts as input a string, then returns a random permutation of the characters of the string using the above algorithm. Your algorithm should be recursive and not use any loops (for, while, etc.).
The header file "random.h" includes a function
int randomInteger(int low, int high);
that takes as input a pair of integers low and high, then returns an integer greater than or equal to low and less than or equal to high. Feel free to use that here.
Interesting note: This shuffling algorithm is a variant of the Fisher-Yates Shuffle. To learn how to prove it works correctly, take CS109!
Here is one possible solution:
string randomShuffle(string input) {
/* Base case: There is only one possible permutation of a string
* with no characters in it.
*/
if (input.empty()) {
return input;
} else {
/* Choose a random index in the string. */
int i = randomInteger(0, input.length() - 1);
/* shuffle the rest of the string, add the removed character on the front
* the string.
*/
return input[i] + randomShuffle(input.substr(0, i) + input.substr(i + 1));
}
}
This function is based on the recursive observation that there is only one possible random shuffle of the empty string (namely, itself), and then using the algorithm specified in the handout for the recursive step.
4. Count Escape Routes (escape.cpp)
Topics: Recursive counting
Given an input maze and a start GridLocation, write a recursive function that counts the number of ways we can escape the maze. In this maze, we can only take one unit steps in two directions: south and east. Just like the maze in assignment 2, the only exit out of the maze is at the bottom right corner.
int countWaysToEscape(Grid<bool>& maze, GridLocation location) {
// if we are out of bounds or this location is blocked, stop searching
if (!maze.inBounds(location) || !maze[location]) {
return 0;
}
// if we are the end of the maze, we've found one way to escape
if (location == GridLocation{maze.numRows() - 1, maze.numCols() - 1}) {
return 1;
}
int waysSouth = countWaysToEscape(maze, {location.row + 1, location.col});
int waysEast = countWaysToEscape(maze, {location.row, location.col + 1});
return waysSouth + waysEast;
}
5. Big O, Recursive Functions - Fibonacci
Topics: Big-O, code analysis, recursion
What is the Big O runtime of the following function, in terms of the variable n?
int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
The time complexity for fibonacci is exponential, O(2^n). This is tricky!
We can speculate that it's exponential because 1 recursive call makes 2
others which in turn make 4 others and so on. In general this is how you
can analyze Big O of recursive functions. First, find what the runtime
is in 1 recursive call. Next, count how many recursive calls we make in
terms of N.
In a single recursive call to fibonacci, we just make other calls to Fibonacci.
So outside of the recursive calls, we do constant time amount of work. Next,
let's analyze how many calls we make in terms of n. To do that, it helps to
try a few examples. Fibonacci(3) calls Fibonacci(2) and Fibonacci(1).
Fibonacci(2) then calls Fibonacci(1) and Fibonacci(0). In total, for N = 3,
we make 4 recursive calls. Let's try another example for Fibonacci(4).
Fibonacci(4) calls Fibonacci(3) and Fibonacci(2). From the above, we know
that Fibonacci(3) results in 4 recursive calls. Fibonacci(2) then calls
Fibonacci(1) and Fibonacci(0). In total, we make 8 recursive calls.
Do you see some kind of pattern here? From our simple examples, it appears
for each n, we make approximately 2^(n - 1) recursive calls (It's approximate
because this formula doesn't fit for all n). We can write 2^(n - 1) as
2^n / 2. Therefore we can write the Big O as O(1)[for amount of work in a
single recursive call] * O(2^n / 2)[the total number of recursive calls we
make]. Remember that in Big O, we discard constant multipliers, so the Big O
for fibonacci simplifies to O(2^n).
----------------------------------------
Interesting note (beyond the scope of what we cover in this class):
Note that if fibonacci(n) called fibonacci(n-1) twice, the number of calls
would be approximately 2^(n-1). However, this formula is not super precise
for Fibonacci -- and is actually an overestimate of the runtime -- because
the function is making two different function calls: one to fibonacci(n-1)
and one to fibonacci(n-2). If we diagram out these calls with a decision
tree, rather than seeing a nice, symmetrical tree with approximately
2^(n-1) calls, we see a lopsided tree in which the right-hand side is
smaller than the left-hand side.
A more precise indication of the runtime is actually O(Φ^n) ≈ O(1.618^n).
A careful analysis of the runtime is beyond the scope of this class but
can be found if you google "Fibonacci runtime analysis," if you're curious!