ICS 45C 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 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-21 07:20:59
Exercise Set 3 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 set3 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 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 ics45c start set3 set3.)

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)

Write a C++ function with the following signature:

void reverse(int* first, int* last)

The presumption is that first points to the first element of an array (either statically- or dynamically-allocated) and last points to the last element of the same array. The goal of the function is to reverse the order of the elements stored in the array — so, for example, if the array contains the elements 2, 4, 1, 9, 7 when the function is called, the array will contain 7, 9, 1, 4, 2 afterward.

In your solution, you'll need to adhere to two limitations:

You must not use the indexing operator [ ] at all.
You must not use the C++ Standard Library, which means that you cannot #include any standard header files.

It is safe to assume that first and last will always point into the same array — any other scenario is assumed to lead to undefined behavior — and that last will always point to a cell in that array with an index at least as large as first will.

What to submit

Add one C++ source file to your problems directory with this name: problem1.cpp, which contains the definition of your function.

Problem 2 (2 points)

An important and recurring theme in C++'s type system revolves around Constness, the idea that there can be well-defined times where certain things are not allowed to be changed, with the compiler enforcing the restriction automatically. This can be a powerful design tool, because (like many aspects of the type system in C++) it can prevent entire categories of mistakes you might make from ever occurring in a running program. Like most design tools, though, it's important to understand when and how it's best used, and what you might give up when you do.

Now consider two pairs of functions in C++, in each case leading us to be able to compare them. For each pair of functions, assume that the two functions have identical bodies (i.e., whatever is done in these functions would be legal in either of them).

void doSomethingConst(const int& i)
void doSomethingNonConst(int i)

void doSomethingConst(const std::string& s)
void doSomethingNonConst(std::string s)

For each pair of functions, answer the following two questions:

Which of the two functions in the pair would you expect to run faster? Why?
Which of the two functions would you expect to use less memory? Why?

What to submit

Add one PDF file to your problems directory with this name: problem2.pdf, which contains your answers to the two questions for each pair of functions.

Problem 3 (2 points)

When designing a struct in C++, one thing worth thinking about is the order in which the members should be listed, which isn't necessarily an arbitrary decision, but one that has a substantive effect on program design.

List and briefly describe (in a sentence or two each) two ways that the design of a struct can be improved by adjusting the order in which the members are listed in its declaration.

What to submit

Add one PDF file to your problems directory with this name: problem3.pdf, which contains your description of the two potential improvements.

Problem 4 (2 points)

When we learned about Structures, we learned that one of the jobs of a compiler, when given a declaration of a struct, is to decide how that structure should be laid out in memory (i.e., how large it should be and where within that memory each of the members should be placed). We also noted that the rules about this vary from one compiler to another, because what's performant on one architecture might be problematic on another.

Suppose that we're writing a C++ program and our compiler uses the following rules to decide how to lay out structures.

The sizes of the built-in types are as follows: a char is one byte, a short is two bytes, an int is four bytes, and a double is eight bytes.
The underlying architecture provides the ability to fetch memory in only these ways, each of which take the same amount of time:
- One byte, given any address.
- Two bytes, given any adress that is aligned on a two-byte boundary. (In other words, we can read two bytes from the address 14 or 16, but not 15; only address divisible by two are allowed if we're reading two bytes.)
- Four bytes, given any address that is aligned on a four-byte boundary
Our compiler has a setting that allows us to decide which of the following characteristics we want:
- Optimize for speed (i.e., be able to read the members of a struct as fast as possible, even if extra memory is used).
- Optimize for memory usage (i.e., store a struct in as little memory as possible, even if member access becomes slower).

In our program, we've declared the following struct.

struct Whatever
{
    short a;
    int b;
    char c;
    double d;
};

If we've configured the compiler to optimize for speed, for each member, specify its offset (i.e., where in the structure it would begin). If padding was necessary before it, briefly explain why.
- a
- b
- c
- d
Finally, list the total size of the Whatever struct in this case.
If we've configured the compiler for memory usage, for each member, specify its offset (i.e., where in the structure it would begin). If padding was necessary before it, briefly explain why.
- a
- b
- c
- d
Finally, list the total size of the Whatever struct in this case.

What to submit

Add one PDF file to your problems directory with this name: problem4.pdf, which contains you description of these two scenarios.

Problem 5 (2 points)

In the app directory, you'll find two files, example5.hpp and example5.cpp, which contain the declaration and definition, respectively, of a function called runExample5; don't modify this, as we'll be asking you questions about it below. You'll also find the usual main.cpp file, in which you should make two changes before proceeding with this problem:

Add #include "example5.hpp" before the main() function.
Add one call to the runExample5 function in the main() function, just before it returns 0.

The end result of those two changes is that compiling and running your app will cause the runExample5 function to execute once.

Now that you've made these changes, run the app program using Memcheck (i.e., by issuing the command ./run --memcheck app, as described in the Illuminating the Dark Corners notes).

For each of the errors that appear while the program runs, note what the error was, what line of code in example5.cpp it occurred on, and briefly explain the underlying cause of the error. Don't just copy and paste the entire error message and backtrace from Memcheck; your goal is to tell us what's wrong and where, not just to blindly copy and paste Memcheck's output. Use line numbers to describe where issues are.
For each of the memory leaks listed at the end of the program, note what was leaked and what line of code in example5.cpp allocated it.

There's no need to fix what's wrong with the runExample5 function; your goal is only to determine where the issues are.

What to submit

Add one PDF file to your problems directory with this name: problem5.pdf, which contains your assessment of the errors and leaks reported by Memcheck when the provided runExample5 function executes once.

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 (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.