ICS 46 Spring 2022, Exercise Set 3

Getting started

First of all, be sure that you've read the Reinforcement Exercises page, which explains everything you'll need to know, generally, about how the reinforcement exercises will work this quarter. Make sure you read that page before you continue with this one.

Before you begin work on these reinforcement exercises, there's a chore that you'll need to complete on your ICS 46 VM to get it set up to proceed.

Refreshing your ICS 46 VM environment

Even if you previously downloaded your ICS 46 VM, you will probably need to refresh its environment before proceeding with these exercises. Log into your VM and issue the command ics46 version to see what version of the ICS 46 environment you currently have stored on your VM. Note, in particular, the timestamp; if you see a version with a timestamp older than the one listed below, you'll need to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with these exercises.

2022-04-19 10:22:31
Exercise Set 3 template added

If you're unable to get outgoing network access to work on the ICS 46 VM — something that afflicts a handful of students each quarter — then the ics46 refresh command won't work, but an alternative approach is to download the latest environment from the link below, then to upload the file on to your ICS 46 VM using SCP. (See the Project #0 write-up for more details on using SCP.) Once the file is on your VM, you can run the command ics46 refresh_local NAME_OF_ENVIRONMENT_FILE, replacing NAME_OF_ENVIRONMENT_FILE with the name of the file you uploaded; note that you'd need to be in the same directory where the file is when you run the command.

ics46-2022spring-environment.tar.gz

Creating your project directory on your ICS 46 VM

A project template has been created specifically for this set of exercises, containing a similar structure to the basic template you saw in Project #0. Among other things, it contains a version of the gather script that's different from the ones in the projects, so you'll absolutely need to use the set3 template for these exercises, as opposed to the basic one.

Decide on a name for your project directory, then issue the command ics46 start YOUR_CHOSEN_PROJECT_NAME set3 to create your new project directory using the set3 template. (For example, if you wanted to call your project directory set3, you would issue the command ics46 start set3 set3.)

Problem 1 (3 points)

Suppose that you have the following recursive function written in C++. I've intentionally written the function so that it doesn't use descriptive names for anything, though that's obviously not a good design practice, but I aim not to bias your understanding of the techniques you'll be using by assuming anything about what the function's goal is; to stay "on task" here, you should resist the temptation to try to figure that out first.

void kaboom(
    const std::vector<int>& v, std::vector<int>& w,
    unsigned int i)
{
    if (i < w.size())
    {
        int q = 0;

        for (int j : v)
        {
            q += j;
        }

        w.at(i) = q;
        kaboom(v, w, i + 1);
    }
}

Using the techniques from our discussion of the Asymptotic Analysis of Recursion, write a recurrence that describes the time required to run the following call to kaboom for two vector v and w whose sizes are the same. Use the variable s in your recurrence to denote that size.
```
kaboom(v, w, 0)
```
Using the repeated substitution technique, reduce the recurrence to a closed form, then give an asymptotic notation that best describes it.

What to submit

Add one PDF file to your core directory with this name: problem1.pdf, which contains your answers to these two questions.

Problem 2 (3 points)

Consider the following general tree, which you saw in the Tree Traversals notes.

General Tree

Now suppose that, when given a choice between two or more subtrees or a given tree, you always consider them in right-to-left order, relative to what's in that diagram. (In practice, the order is not especially relevant, but, for the purposes of this question, we'll assume right-to-left ordering is required.)

In a complete postorder traversal of the tree, in what order would the nodes be visited? What is the maximum number of nodes that would ever be stored on the run-time stack while it runs on this tree, assuming the traversal was implemented recursively?
In a complete preorder traversal of the tree, in what order would the nodes be visited? What is the maximum number of nodes that would ever be stored on the run-time stack while it runs on this tree, assuming the traversal was implemented recursively?
In a complete breadth-first traversal of the tree, in what order would the nodes be visited? What is the maximum number of nodes that would ever be stored in the queue at any given time while it runs on this tree?

What to submit

Add one PDF file to your core directory with this name: problem2.pdf, which contains your answers to these three questions.

Problem 3 (2 points)

We saw the mechanics of Tree Traversals and discussed how they're different from one another, but if we want to write practical software, we also need to know when we should be using the techniques we're learning about. In each of the scenarios described below in which a tree traversal is required, what would be the appropriate kind of tree traversal to use? For each one, briefly explain (in no more than a sentence or two) why.

You're writing an analysis tool for a hierarchical organization, in which there is one person fundamentally in charge, to whom some number of people report, to each of whom some number of people report, and so on. There is a ranking in the organization, so the person in charge has rank 1, the people who report to that person have the rank 2, the people who report to the rank-2 people have the rank 3, and so on. Your input is this kind of organizational hierarchy. Your desired output is to be able to find the highest-ranking person (i.e., the person with the minimum rank number) who meets some characteristic (such as the highest-ranking person under 30 years old).
Your input is a binary tree that is an expression tree, in which each non-leaf node contains a binary mathematical operator (such as +, −, ×, or ÷) and each leaf node contains a numeric value (such as 2 or 9.5). Your desired output is the value of the expression represented by the tree — so, for example, if the tree had a root node + and its two children were the numeric values 3 and 6, the result would be 9.
You're implementing a copy constructor for a class that implements a general tree using the "list of children" technique, with the objective being the usual one when implementing a copy constructor: The newly-constructed tree is wholly separate from the original, so that any modification to one does not affect the other.

What to submit

Add one PDF file to your core directory with this name: problem3.pdf, which contains your choice (and explanation) about which traversals would best address each scenario.

Problem 4 (2 points)

Suppose that you implemented the following C++ class template.

template <unsigned int N, typename T>
class NAryTree
{
    // ...
};

The template's parameters are:

N, which specifies the number of children that each node will have.
T, which specifies the type of value stored in each node.

Now suppose that you were going to implement NAryTree using the "list of children" technique described in the General Trees notes, with each node storing pointers to its children. Would you expect to be able to statically allocate the collection of "child pointers" in each node, or would you expect that you would have to dynamically allocate it? Why?

What to submit

Add one PDF file to your core directory with this name: problem4.pdf, which contains your answer to this question.

Deliverables

In Canvas, you'll find a separate submission area for each problem. Submit your solution to each problem into the appropriate submission area. Be sure that you're submitting the correct file into the correct area (i.e., submitting your Problem 1 solution to the area for Problem 1, and so on). Under no circumstances will we offer credit for files submited in the incorrect area.

Submit each file as-is, without putting it into a .tar.gz file or arranging it in any other way. (There is a gather script in the set3 template, but there's no need to use it.) If we asked for a PDF, for example, all we want is a PDF; no more, no less. If you submit something other than what we asked for, we will not be offering you any credit on the submission. There are no exceptions to this rule.

Of course, you should also be aware that you're responsible for submitting precisely the version of your work that you want graded. We won't regrade an exercise simply because you submitted the wrong version accidentally, and we won't be able to offer any credit on exercises that you forgot to submit.

Can I submit after the deadline?

Unlike some of the projects in this course, the reinforcement exercises cannot be submitted after the deadline; there is no late policy for these. Each is worth only 3% of your grade, so it's not a disaster if you miss one of them along the way.

Can I work on this outside of the VM?

Yes, but be aware that you must submit the files in the appropriate format, and that any C++ code you submit must compile and run on the ICS 46 VM.