lab_quacks

Assignment Description

In this lab, you will learn to think recursively and apply it to the stack and queue data structures. You might also practice templates.

Lab Insight

Stacks and queues are incredible data structures used in a wide range of applications throughout the world. You have already seen a great example of a queue in CS 225. We use the queue data structure to help us manage our office hours. Queues can do so many incredible things like helping schedule tasks for a computer or managing user priority based on a FIFO (first in, first out) principle. You will find both useful in traversing a graph later in the semester. These data structures are very versatile and useful throughout the software world. A visualization of them can be found here.

Recursion

What is recursion? Recursion is a way of thinking about problems that allows the computer to do more of the heavy lifting for us. It is analogous to the mathematical definition of recursive functions, where you can define a function call in terms of calls to itself and basic arithmetic operations, but not in terms of loops.

Why recursion? While being able to think recursively is one of the harder parts of computer science, it is also one of the most powerful. In fact, there are whole languages that entirely use recursion instead of loops, which, even though it may seem inefficient, leads to some very useful optimizations a compiler can make when dealing with such code. There are probably more problems in computer science that are simpler recursively than they are iteratively (using loops). Also, once you have a recursive algorithm, it is always possible to transform it into an iterative algorithm using a stack and a while loop. In this way, computer scientists can think about problems recursively, then use that recursive solution to make a fast iterative algorithm (and in the grand scheme of big-O notation, using recursion has little overhead compared to the rest of the running time). Here we’ll only ask you to do the first part.

How do I write recursively? Recursion just means calling a function within itself. This may sound crazy, but in fact it is not. Let’s take an iterative function to calculate the factorial of a number \(n\), \(n!\):

int factorial(int n)
{
    int result = 1;
    for (int i = 1; i <= n; i++)
        result = result * i;
    return result;
}

Okay, so four lines of code. Pretty short and understandable. Now let’s look at a recursive version:

int factorial(int n)
{
    if (n == 0) return 1;
    return (factorial(n-1) * n);
}

Only two lines of code! (Depending on whether you like putting your return statement on the same line.) Even on such a small problem, recursion helps us express ourselves more concisely. This definition also fits better with the mathematical definition:

A typical recursive function call consists of three parts. Let’s examine the function more closely to see them. Here’s the same code again, with more discussion.

int factorial(int n)
{
    if (n == 0)    // Here is our base case.
        return 1;  // The base case is the smallest problem we can think of,
                   // one we know the answer to. This is the "n = 0" case in
                   // the mathematical definition.

    // optional 'else' here

    return (factorial(n-1) // This is our recursive step. Here we are solving a
                           //   smaller version of the same problem. We have to
                           //   make a leap of faith here - trust that our
                           //   solution to the (n-1) case is correct.  This is
                           //   the same as the mathematical definition, where
                           //   to figure out n!, we need to first figure out
                           //   (n-1)!
               * n         // Here is our incremental step. We are transforming
                           //   our solution to the smaller problem into the
                           //   solution to our larger problem. This is the
                           //   same * n from the mathematical definition.
           );
}

Checking Out the Code

You can find the code for all our released assignments at the following public git repo.

release-f22

You can either clone this or pull a zip file of the repo to your local computer. All the files for this MP are in the lab_quacks directory. You should copy that directory into the directory you setup for your docker container.

Preparing Your Code

This semester for MPs we are using CMake rather than just make. This allows for us to use libraries such as Catch2 that can be installed in your system rather than providing them with each assignment. This change does mean that for each assignment you need to use CMake to build your own custom makefiles. To do this you need to run the following in the base directory of the assignment. Which in this assignment is the lab_quacks directory.

mkdir build
cd build

This first makes a new directory in your assignment directory called build. This is where you will actually build the assignment and then moves to that directory. This is not included in the provided code since we are following industry standard practices and you would normally exclude the build directory from any source control system.

Now you need to actually run CMake as follows.

cmake ..

This runs CMake to initialize the current directory which is the build directory you just made as the location to build the assignment. The one argument to CMake here is .. which referes to the parent of the current directory which in this case is top of the assignment. This directory has the files CMake needs to setup your assignment to be build.

At this point you can in the build directory run make as described to build the various programs for the MP.

As usual, to see all the required functions, check out the Doxygen.

Recursive Exercises

Sum of Digits

Given a non-negative int n, return the sum of its digits recursively (no loops). Note that modulo (%) by 10 yields the rightmost digit (126 % 10 == 6), while divide (/) by 10 removes the rightmost digit (126 / 10 == 12).

int sumDigits(int n);

sumDigits(126) -> 1 + 2 + 6 -> 9
sumDigits(49)  -> 4 + 9     -> 13
sumDigits(12)  -> 1 + 2     -> 3

Triangle

We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on:

       *        1 block
     *   *      2 blocks
   *   *   *    3 blocks
 *   *   *   *  4 blocks
............... n blocks

Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.

int triangle(int rows);

triangle(0) -> 0
triangle(1) -> 1
triangle(2) -> 3

The sum Function

Write a function called sum that takes one stack by reference, and returns the sum of all the elements in the stack, leaving the original stack in the same state (unchanged). You may modify the stack, as long as you restore it to its original values. You may use only two local variables of type T in your function. Note that this function is templatized on the stack’s type, so stacks of objects overloading the addition operator (operator+) can be summed. Hint: think recursively!

template <typename T>
T QuackFun::sum(stack<T> & s);

Non Recursive Exercises

Balancing Brackets: the isBalanced Function

For this exercise, you must write a function called isBalanced that takes one argument, an std::queue, and returns whether the string represented by the queue has balanced brackets. The queue may contain any characters, although you should only consider square bracket characters, ‘[’ and ‘]’, when considering whether a string is balanced. To be balanced, a string must not have any unmatched, extra, or hanging brackets. For example, the string [hello][] is balanced, [[][[]a]] is balanced, []] is unbalanced, ][ is unbalanced, and ))))[cs225] is balanced. It’s possible to solve this problem without using a stack, but in the spirit of this lab, you should use one in your solution!

bool isBalanced(queue<char> input);

The scramble Function

Your task is to write a function called scramble that takes one argument: a reference to a std::queue.

template <typename T>
void QuackFun::scramble(queue<T> & q);

You may use whatever local variables you need. The function should reverse the order of SOME of the elements in the queue, and maintain the order of others, according to the following pattern:

• The first element stays on the front of the queue.
• Then the next two elements are reversed.
• Then the next three elements are placed on the queue in their original order.
• Then the next four elements are reversed.
• Then the next five elements are place on the queue in their original order.
• etc.

Hint: You’ll want to make a local stack variable.

For example, given the following queue,

front                                         back
0   1 2   3 4 5   6 7 8 9   10 11 12 13 14   15 16

we get the following result:

front                                         back
0   2 1   3 4 5   9 8 7 6   10 11 12 13 14   16 15

Any “leftover” numbers should be handled as if their block was complete. (See the way 15 and 16 were treated in our example above.)

Testing Your Code

Run the Catch tests as follows:

make test
./test

Grading Information

The following files are used in grading:

• exercises.cpp
• exercises.h
• quackfun.hpp
• quackfun.h

All other files including any testing files you have added will not be used for grading.

All other files, including main.cpp and any testing files you have added will not be used for grading. Remember that submissions must be done through Prairielearn!