ICS 46 Spring 2022, Exercise Set 8

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-05-26 06:57:46
Exercise Set 8 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 set8 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 set8 to create your new project directory using the set8 template. (For example, if you wanted to call your project directory set8, you would issue the command ics46 start set8 set8.)

Problem 1 (2 points)

To set up our conversation about Linear-Time Sorting, we discussed that comparison-based sorting algorithms can be modeled as a decision tree. While this is a theoretical model, it also has at least some practical use; if you can draw a decision tree representing an algorithm that sorts a finite (and presumably small) set of numbers, you can translate if by hand into C++ code using nested if statements. Each non-leaf node would translate into an if statement, with its children becoming the if and else branches of that statement, respectively, while each leaf node would translate into a final conclusion on the sorted order of the elements (e.g., a reordering of the elements or a return statement of some kind).

Now suppose that you used a decision tree to sort exactly four elements and then hand-translated it to C++ code, using the technique described above. At minimum, how many if statements would you expect to find in your translated code? (Count every time you would use the keyword if, regardless of how or whether it's nested within another if statement.) Briefly explain why.

What to submit

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

Problem 2 (2 points)

In our discussion of Linear-Time Sorting, we talked about an algorithm called radix sort, which does successive iterations of another algorithm called counting sort, with each of those iterations focused on one digit (e.g., sorting by the last digit and ignoring all the others, sorting by the second-to-last digit and ignoring all the others, or whatever).

Suppose that you replaced counting sort, at each step, with a hypothetical algorithm that was faster than counting sort but was not stable. If you did, would you expect radix sort to still come up with a correct result? Briefly explain why or why not.
Suppose that you sorted the digits in the opposite of the order that we specified, by first sorting by the most-significant digit, then the second-most-significant digit, and so on, but otherwise used the same radix sort algorithm that we described. If you did, would you expect radix sort to still come up with a correct result? Briefly explain why or why not.

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)

Propose an algorithm for using equivalence classes and Union-Find to find the connected components in an undirected graph, by answering the following questions about it.

What are the objects whose equivalence you'll be determining?
What is the equivalence relation used to measure their equivalence? Is it reflexive, symmetric, and transitive?
At the start of your algorithm, how many equivalence classes will you have and which objects will be in which ones?
Let's assume that, fundamnetally, your algorithm is a loop. What will your algorithm do during each loop iteration?
How will your algorithm know to end?

What to submit

Add one PDF file to your core directory with this name: problem3.pdf, which contains your exploration of this algorithm.

Problem 4 (4 points)

In the file core/problem4.hpp, you will find the declaration of (the public portions of) a class template called DisjointSetForest, which implements the data structure and algorithms described in the Union-Find Algorithm notes. Additionally, in the file gtest/DisjointSetForestTests.cpp, you'll find unit tests indicating how it should work when it's finished; you'll want to review all of that code after reading the rest of this problem, as it may answer some of the questions you have about it.

Implement the member functions in the DisjointSetForest class template. You may not change any of the public declarations that were provided, but you can add anything you'd like — including public or private member functions, private member variables, and so on — and you can feel free to use any part of C++ Standard Library that you think is helpful, but you'll need to meet all of the following design requirements.

There are two constructors that allow you to initialize a DisjointSetForest: one that initializes from a std::initializer_list and another that initializes from a begin/end iterator pair. In the latter case, you can only assume that it's a forward iterator (i.e., it might be more full-featured than that, but you can't assume it will be) and behaves just like the forward iterators in the C++ Standard Library.
A DisjointSetForest stores elements and manages which equivalence classes they belong to. It's possible to access it based on indices or based on the elements. Any time the element is given instead of an index, it must take no longer than Θ(log n) time for your DisjointSetForest to determine the index for the element.
The path compression technique must be used in your findRoot member function, so that the trees' heights are improved whenever looking up a root.
The weighted union technique must be used in your unionSets member function, so that trees with fewer nodes become children of trees with more nodes, rather than the other way around.

If you have a question about how the member functions are meant to behave, there's a pretty good chance that the provided unit tests will answer them, so I'd ask you to read those tests before asking questions on Ed Discussion or via email; you'll save yourself (and us) a lot of time that way.

What to submit

Modify the problem4.hpp in your core directory with your complete implementation of the DisjointSetForest class template.

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