ICS 46 Spring 2022, Exercise Set 2

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-12 07:00:16
Exercise Set 2 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 set2 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 set2 to create your new project directory using the set2 template. (For example, if you wanted to call your project directory set2, you would issue the command ics46 start set2 set2.)

Problem 1 (2 points)

In the core directory of your project directory for this week's exercises, you'll find two files: ArrayList.hpp and ArrayList.cpp. Together, these files contain an implementation of a class called ArrayList that is part of the Well-Behaved Classes notes from ICS 45C.

To help you to get your mind wrapped around Move Semantics, implement a move constructor and a move assignment operator in this class, which will require modifications to two files:

Add the declaration of a move constructor and a move assignment operator into the class declaration in core/ArrayList.hpp.
Create a new C++ source file core/problem1.cpp, in which you'll write the definition of the move constructor and move assignment operator in the ArrayList class. (Notably, this means you will not write it in core/ArrayList.cpp. This also means that core/problem1.cpp will need to say #include "ArrayList.hpp" fairly early on. Ordinarily, there's value in implementing all of a class' member functions in one source file, but we'd only like you to submit these two functions in core/problem1.cpp, so we'll need them in a separate file.)

Additionally, add comments above each of these functions in your core/problem1.cpp file that specify the asymptotic notation that best indicates how long they would take to run on an ArrayList whose size is n and whose capacity is c, along with a brief description — a sentence or two is fine — of why.

What to submit

Add one C++ source file to your core directory with this name: problem1.cpp, which contains only the definition of your move constructor and move assignment operator, along with the comments indicating their run-time performance.

Problem 2 (2 points)

Let's take a look at the mathematical definitions of O- and Ω- notation.

By the definition of O-notation, is it true that the function 3n + 9 is O(n³)? If so, prove that it is true by using the mathematical definition of O-notation. If not, explain in a couple of sentences why it isn't.
By the definition of Ω-notation, is it true that the function 3n + 9 is Ω(n³)? If so, prove that it is true by using the mathematical definition of Ω-notation. If not, explain in a couple of sentences why it isn't.

What to submit

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

Problem 3 (2 points)

We've seen that asymptotic notations — O-, Ω-, and Θ-notation — are a tool for focusing on the general shape of a function as opposed to its finer-grained details. We've seen some details that are clearly too fine-grained to be considered, such as constant factors and lower-order terms (e.g., 8n in the function n² + 8n), while others are fundamental and shouldn't be ignored.

One thing we've not yet considered, but that will show up in many places in this course, is the effect of having multiple variables in a function. While we quite often use the variable n when the variable represents the size of a problem, not all problems' sizes can be described with one variable, which leaves us with the interesting question of what happens to additional variables in asymptotic notations.

Let's consider that problem by thinking about a few subtly different scenarios.

Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Suppose, too, that we know for sure that m is always ⌊n/2⌋ (i.e., the floor of one-half of n). What is an asymptotic notation that best describes the time required to set all of the integers to zero?
Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they relate to one another. What is an asymptotic notation that best describes the time required to set all of the integers to zero?
Suppose that we create a std::vector with n elements, each of which is a std::vector with m integers. Assume that both n and m are positive integers, but there is otherwise no limitation on how they relate to one another. What is an asymptotic notation that best describes the time required to set only some of the integers — namely, all of the integers in the first sub-vector, then only the first integer in all the other sub-vectors — to zero?

In each case, make sure to briefly explain your reasoning. None of them requires more than a couple of sentences, but simply stating an asymptotic notation is not enough here; you need to tell us why.

What to submit

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

Problem 4 (2 points)

We discussed several Linked List Variations, each of which was more complex than the one preceding it, but that was able to do certain things asymptotically faster than the simpler variants could. This is one of many examples we'll see this quarter where we make a classic tradeoff in computing: using more memory (and, correspondingly, more complexity for managing what it's in it) in an effort to spend less time. While it's not always true that we can make things faster by using more memory, it's not at all uncommon to see these two things be on opposite sides of a tradeoff.

One of the linked list variants we saw was a singly-linked list with head and tail pointers. Let's consider where this variant fell short and whether there are other ways to improve it besides what we saw.

Why isn't the presence of a tail pointer enough to allow us to remove the last node in the list in Θ(1) time?
Suppose that we added a third list-level pointer (i.e., outside of the nodes) called beforeTail, which always pointed to the second-to-last node in the list. Would we now be able to remove the last node in the list in Θ(1) time?

What to submit

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

Problem 5 (2 points)

During our conversation about Stacks, Queues, and Deques, we talked about the circular array implementation of a queue.

Why didn't we need a circular array implementation of a stack? What quality, specifically, does a queue have that led to a need for the circular array implementation? (You need to be specific here, but it shouldn't require more than a sentence of two to answer this.)
You've seen that the dynamically-allocated array underlying a std::vector is resized periodically. Propose an algorithm for resizing the array used in the circular array implementation of a queue when it comes time to enqueue an element and the array is full. How much larger is your new array? How do the contents of your queue look different than before?
Assuming your algorithm was used to solve the problem of resizing the array when it's full, what is the amortized running time of the enqueue operation? (You may want to refer back to the Amortized Analysis lecture while you consider this.)

What to submit

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

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