Some ground rules READ THESE FIRST
This final project asks you to work on a number of separate problems. You’ll begin with a project template in the ICS 46 VM, as you would in any other project, and will need to submit files that meet certain naming and format requirements, similar to the Reinforcement Exercises; as with those exercises, you’ll submit as PDF files (which must be typed, rather than scans of written text). You must follow specifically these requirements or we will not be grading your work.
You are required to work on these tasks entirely individually. Piazza has been deactivated for question-asking for precisely this reason, though the course staff will still field questions via email, as usual, though we can only help you to understand what a question is asking; we won’t be willing or able to help you figure out how to answer it.
The late policy does not apply to this project. It is due on Monday, June 8, 11:59pm, after which (beyond the usual ten-minute grace period) no submissions will be accepted and the submission area on Checkmate will disappear.
We’ll be grading these on the basis of correctness, as well as whether you stay on topic. For problems where you’re asked to explain an answer, we reserve the right to deduct for large amounts of irrelevant information in which a relevant answer is buried; stick with what needs to be said to make your point, rather than just dumping everything you know in hopes that some of it is correct. Also, unlike the Reinforcement Exercises, there will be no points for honest attempts that are incorrect.
Getting started
Before you begin work on these problems, 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 may need to refresh its environment before proceeding with this project, so that you have a copy of the final project template that you’ll need for this project.
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 want to refresh your environment by running the command ics46 refresh to download the latest one before you proceed with this project.
Note that you can instead use the ics46 refresh_local technique described in the Project #1 write-up, if you’re unable to make your outgoing Internet connection work from within the ICS 46 VM.
Creating your project directory on your ICS 46 VM
A project template has been created specifically for this project. It includes a gather script for preparing your files for submission when you’re finished, as well as the usual array of scripts for running the program with and without the Memcheck tool, and a directory in which you can (optionally) write unit tests to assist in your testing.
Decide on a name for your project directory, then issue the command ics46 start PROJECT_NAME final to create your new project using the final template.
Do not use other project templates, like basic or project4, for this project!
Problem 1
Suppose that you’ve decided to write this function, which takes an unsigned int parameter and generates a std::string containing that number of randomly-chosen uppercase letters.1
2
3
4
5
6
7
8
9
10
11
12
13std::string generateRandomLetters(unsigned int size)
{
std::string s(size, ' ');
for (unsigned int i = 0; i [ size; ++i)
{
std::random_device device;
std::default_random_engine engine{device()};
std::uniform_int_distribution distribution{'A', 'Z'};
s[i] = distribution(engine);
}
return s;
}
- Are there any circumstances in which you wouldn’t expect this function to do what’s specified (i.e., to generate a string of random uppercase letters)? Briefly explain why or why not.
- What adjustments, if any, would you make to the design of this function to improve it? You don’t need to rewrite the function, as long as you explain briefly what you would change about it and why.
Problem 2
Suppose that you wrote a C++ class template that implemented singly-linked list with head and tail pointers, and that you used std::shared_ptrs to link the nodes (i.e., the head pointer in the list would be a std::shared_ptr to the first node, the last pointer in the list would be a std::shared_ptr to the last node, and each node would contain a std::shared_ptr to the subsequent node).
It would seem undoubtedly true that the use of smart pointers would result in you having to write less code, given that smart pointers automate some things that you might otherwise have to write yourself. Suppose, for example, that you implemented the destructor and realized that you could use the ownership characteristics of smart pointers to write this.
Assuming that all class invariants were intact before calling this destructor (i.e., the pointers are pointing to reasonable places beforehand), are there any circumstances in which you wouldn’t expect all of the nodes to be destroyed properly? If so, briefly explain each circumstance where it would fail to destroy all of the nodes. If not, briefly explain what happens after setting head to nullptr to cause all of the nodes to be destroyed.
Problem 3
Suppose you started with an empty AVL tree, then added a sequence of n ascending, consecutive keys to it, starting with 1, then 2, then 3, and so on, until you had added all n of them. (How do you know what n is? See below.)
List your n value, then list all of the rotations that occurred, one per line, in the order that they occurred. Each rotation should be written using its name and the key in the node where the rotation is rooted (just before the rotation is done) listed in parentheses. For example, if your n value was 27 and you thought that there were three rotations, an LL rotation rooted at 4, an RR rotation rooted at 1, and an LR rotation rooted at 19, you would write this.
Problem 4
Let’s imagine that you’re storing information about the current location of a large number of objects in discrete three-dimensional space, which is to say that each location is made up of three unsigned integers x, y, and z, indicating a distance east, a distance north, and a height from some origin point. You can assume that the distances are measured in small amounts, such as millimeters, so that the numbers themselves might be quite large and that they might be distributed quite sparsely. It’s not particularly important what the application is, but let’s imagine that the most common operations are to add a new location to the set and to check whether a location is already in the set.
You’ve decided that a hash table would be an appropriate way to solve this problem, because you know that a well-chosen hash function can lead to something akin to (1) lookups and amortized (1) insertions, which sounds pretty good to you. Let’s suppose that you’ve chosen this hash function: x + y + z.
Is x + y + z a good hash function? If so, briefly explain why it’s sufficient; if not, briefly explain what’s wrong with it, though you need not propose a new hash function to replace it.
Problem 5
Let’s assume that a bipartite graph is an undirected graph in which there are two distinct sets of vertices, such that all of the edges in the graph connect a vertex in one set to a vertex in the other, but no edges connect vertices in the same set. That sounds esoteric, but there are plenty of real-world problems that collapse nicely into a graph that has these characteristics.
Now let’s assume that you’d like to implement a bipartite graph, so you consider using either an adjacency matrix or adjacency lists, but wonder if they can be modified if you know ahead of time that the graph will be bipartite.
Problem 6
We say that a circle is a directed graph in which the vertices could be given a numbering from 1 through n (i.e., each vertex could be given a unique number), where vertex 1 has one outgoing edge leading to vertex 2, vertex 2 has one outgoing edge leading to vertex 3, and so on. Vertex n has one outgoing edge leading back to vertex 1.
Problem 7
In this course, we saw no fewer than nine different ways to sort a sequence of values, but computer science has much to say about this topic, so there’s plenty more to it than we’ve had a chance to discuss.
For example, we saw that we could use randomness to our advantage in a few places in this course. Skip lists decide randomly on a number of copies of each node, yet leads to logarithmic time lookups, insertions, and removals. Quicksort performs admirably when pivots are chosen randomly. So it’s certainly true that injecting randomness into an algorithm can be a benefit. But let’s take that idea to its logical conclusion. Can you solve problems completely at random?
One way we could apply that idea is to the problem of sorting. One way to sort values might be as simple as this.
Deliverables
After using the gather script in your project directory to gather up the .cpp, .hpp, and/or .pdf files from your problems directory into a single final.tar.gz file, then submit that file (and only that file!) to Checkmate. Be sure, too, that it contains properly-named files (and files in the proper format) so that they will be graded; we’re not asking for a lot, just some attention to detail.
Follow this link for a discussion of how to submit your project via Checkmate. Be aware that I’ll be holding you to all of the rules specified in that document, including the one that says that you’re responsible for submitting the version of the project that you want graded. We won’t regrade your work simply because you submitted the wrong version accidentally. (It’s not a bad idea to look at the contents of your tarball on your host operating system before submitting it.)