ICS 45C Spring 2022, Exercise Set 4

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 45C VM to get it set up to proceed.

Refreshing your ICS 45C VM environment

Even if you previously downloaded your ICS 45C VM, you will probably need to refresh its environment before proceeding with these exercises. Log into your VM and issue the command ics45c version to see what version of the ICS 45C 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 ics45c refresh to download the latest one before you proceed with these exercises.

2022-04-28 06:52:56
Exercise Set 4 template added

If you're unable to get outgoing network access to work on the ICS 45C VM — something that afflicts a handful of students each quarter — then the ics45c 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 45C 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 ics45c 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.

ics45c-2022spring-environment.tar.gz

Creating your project directory on your ICS 45C 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 set4 template for these exercises, as opposed to the basic one.

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

A word about organizing your answers

Please do not copy and paste the problem (or portions of the problem) into the answer you submit. We are well aware of what question you're asking, so copying and pasting the problem simply slows us down when grading your work. Consequently, we will be deducting points when problems are copied and pasted into solutions.

Problem 1 (2 points)

When we discussed Classes, we made some choices that were important, but some of them might seem (to the uninitiated) to contradict one another or be unnecessary. When we make design decisions, it's a good idea for us to be able to articulate why. For that reason, in this problem, you'll explore a few of those decisions that we made in the context of the lecture example, in which we wrote a Song class, as our first foray into designing and writing classes in C++.

If our goal is to write a class' interface (how to use it) in a header file and leave its implementation (how it works internally) for a source file, then why do we declare a class' private member variables in a header file, even though they have more to do with "how it works internally" than "how to use it"? (Sure, it's because the syntax of C++ requires it, but the question is why.)
Constructors can initialize member variables either using initializers or using assignment statements in the body of the constructor. Other than just for stylistic reasons, why are initializers preferable? What do initializers allow that assignment statements in a constructor's body don't?
- Hint: Try writing a class called Person. Give the class two private member variables, a std::string called name and a Song called favoriteSong. Now try writing a constructor for the Person class without using initializers. What happens? There's no need to put this code into your PDF solution to this problem — in fact, please don't — but this would be a good way to explore this issue in depth.
In the Song example, we wrote a member function called getArtist() that returns the value of the artist member variable, as well as a setArtist() that changes it. If we've got a way to return it and a way to change it, what's the benefit of having the member variable be private, when it would require less code if we just made the member variable public and removed the getArtist() and setArtist() member functions altogether?
One of the things we saw show up in the Song example was that member functions can be marked const (i.e., we can add the word const to the end of a member function's signature). While we don't want to mark every member function this way, we do want to mark at least some of them. Suppose there's a member function for which const would be a good design choice. What is the downside if we forget to mark the member function const? Suppose there's a member function for which const would not be a good design choice. What is the downside if we mark it const anyway?

What to submit

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

Problem 2 (2 points)

In the Linked Data Structures notes, we revisited the concept of linked lists, which you've likely seen in prerequisite coursework. Linked lists solve the same basic problem that's solved by single-dimension arrays: Storing and manipulating a sequence of values. By "sequence," I mean that the order is relevant; in both a single-dimension array and a linked list, the elements in the cells of the array or the nodes of the linked list have an order to them (i.e., there's a definitive "first" element, then a definitive "second", "third", and so on).

The mechanics of linked lists are obviously quite different, though, which leads to an important question: Why are there two so wildly different solutions to the same problem? If both approaches not only exist but are widely taught and used in practice, then there must be advantages to each. Though a lot of the analysis of their differences is best deferred to ICS 46, when we'll have the mathematical tools for analyzing them in depth, your current background is enough to begin considering those differences.

To contrast them, let's suppose you had a pointer to a dynamically-allocated single-dimension array of n integers and a linked list (implemented as discussed in the Linked Data Structures notes) containing n integers (one per node). Answer the following questions about them, each requiring no more than a sentence or two.

Which would you expect to require more memory? Why?
Which would you expect to require more time to access its first integer (i.e., the integer in the first cell of the array or the integer in the first node of the list)? Why?
Which would you expect to require more time to access its ninth integer? Why?

Now assume the capacity of the array is n+1 instead of n, but that we're still storing only n elements in it (i.e., the cell at index n is allocated and available to be used, but not yet used for anything). Meanwhile, the linked list still contains n integers.

Which would you expect to require more time to insert an integer at the beginning of the sequence (i.e., before the others, so that the newly-inserted element is the first, the one that was formerly the first is now the second, and so on)? Why?
Which would you expect to require more time to insert an integer at the end of the sequence (i.e., after all the others)? Why?

What to submit

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

Problem 3 (2 points)

Suppose you had a LinkedList class similar to the one that is described in the Linked Data Structures notes, with the following private members.

class LinkedList
{
private:
    struct Node
    {
        std::string value;
        Node* next;
    };

    Node* head;
};

Write the definition of a member function in the LinkedList class called transformEach, which takes one parameter, a function that transforms a string into another string, and changes the value in every node to be the result of calling the transformation function on every string. For example, if you had a LinkedList called list containing three nodes with the values "Boo", "is", and "happy", and then you did this:

list.transformEach([](const std::string& s) { return s + "!"; });

then you would expect list's nodes to contain "Boo!", "is!", and "happy!" afterward.

You'll need to decide on the right signature for the member function — that's part of what the question is asking you to consider. You cannot assume that there are any public member functions, nor can you assume that there are any private member functions or member variables other than what you see listed above, which are sufficient for solving the problem.

What to submit

Add one C++ source file to your problems directory with this name: problem3.cpp, which contains the definition of your member function and nothing else. Since the rest of the LinkedList class has not been provided, you will not need to make changes to LinkedList's class declaration, nor will you be able to test this one, except on paper.

Problem 4 (4 points)

In the problems directory, you'll find three files called GroceryItem.hpp, GroceryPurchase.hpp, and GroceryPurchase.cpp. You'll want to read the code in these files — in that order, most likely — and understand what it does, but do not modify it.

In our conversation about Unit Testing, we talked about a tool called Google Test, which we're going to be using in this course to write unit tests for some of the code that we write. Sometimes, I'll provide tests that help you to understand the code that I've written in examples or provided in a project; sometimes, you'll be writing tests to verify the behavior of your own code. To do that, though, you'll need to be familiar with Google Test (and with unit testing, more generally, if you've never done it), and there's no better way to build familiarity with something new than to start using it.

Create a C++ source file problems/problem4.cpp and, in that file, write unit tests that completely cover the various behaviors in the provided GroceryPurchase class. There is no stated number of tests you're required to write — please don't ask, as we won't be willing or able to answer that question — because the goal here is a qualitative one, rather than a quantitative one; two tests are only better than one if they test different, interesting behaviors. So you'll want to consider what those behaviors are; it's certainly going to require more than one test for each member function, and note that not all of the member functions can be tested in isolation (e.g., you can't test a member function that returns void except with respect to how it affects the results of subsequent calls to member functions on the same object).

Note that you can compile your unit tests using the ./build gtest command from your project directory; you can run them using the ./run gtest command. (In other words, the gtest program built by your project will include all of the code in the problems directory — including the unit tests you wrote there — automatically.)

What to submit

One C++ source file named problem4.cpp, which you'll need to create in the problems directory, and which contains your unit tests for the provided GroceryPurchase class.

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 set4 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 (and the lowest score doesn't count), so it's not a disaster if you miss one of them along the way.

What do I do if Canvas slightly adjusts my filename?

Canvas will sometimes modify your filenames when you submit them (e.g., when you submit the same file twice, it will change the name of your second submission to end in -1.tar.gz instead of just .tar.gz). In general, this is fine; as long as the file you submitted has the correct name, we'll be able to obtain it with that same name, even if Canvas adjusts it.

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 45C VM.