使 VM
环境，完成7个C++编程问题。包括shared_ptr, linked list, AVL tree, graph, sort等问题。
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.
2020-06-02 20:03:36
Final Project template added
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.
std::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.
What to submit
Add one PDF file to your core directory with this name: problem1.pdf, which
contains your answers to these questions.
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.
template
LinkedList
{
head = nullptr;
}
—|—
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.
What to submit
Add one PDF file to your core directory with this name: problem2.pdf, which
contains your answer to this question.
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.
n = 27
LL(4)
RR(1)
LR(19)
No explanation is required, but your answer does need to be in the format
described above to be considered.
How to know what value of n to use
The value you should use for n is determined by an algorithm that has been
implemented in a program called problem3 that you’ll find in your project
directory. From your project directory, issue the command ./problem3, then
enter your UCInetID, and you’ll be given the value of n you should use.
What to submit
Add one PDF file to your core directory with this name: problem3.pdf, which
contains your answer to this question.
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.
What to submit
Add one PDF file to your core directory with this name: problem4.pdf, which
contains your answer to this question.
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.
- In an adjacency matrix implementation, what is an asymptotic notation describing how much memory you would need to use to store a bipartite graph? Is this an improvement over a graph that isn’t known ahead of time to be bipartite? If so, briefly explain why this could be an improvement; if not, briefly explain why there was no improvement to be had.
- In an adjacency lists implementation, what is an asymptotic notation describing how much time you would need to enumerate all of the edges in a bipartite graph? Is this an improvement over a graph that isn’t known ahead of time to be bipartite? If so, briefly explain why this could be an improvement; if not, briefly explain why there was no improvement to be had.
What to submit
Add one PDF file to your core directory with this name: problem5.pdf, which
contains your answer to these questions.
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.
- Propose an algorithm that takes a directed graph and determines whether it’s a circle. You don’t need to write it in C++, but some kind of an understandable form of pseudocode is necessary, so we’ll understand your algorithm.
- What is an asymptotic notation for the best-case running time of your proposed algorithm? Briefly describe the circumstance that leads to a best-case outcome.
- What is an asymptotic notation for the worst-case running time of your proposed algorithm? Briefly describe the circumstance that leads to a worst-case outcome.
What to submit
Add one PDF file to your core directory with this name: problem6.pdf, which
contains your answer to these questions.
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.
sortSequence(sequence):
loop forever:
choose any two values in the sequence at random
swap the two values
if the sequence is sorted:
return (i.e., leave this function)
—|—
- Is this algorithm correct? In other words, is it capable of taking any sequence of values and sorting it? If not, in what circumstances might it fail to sort a sequence of values?
- If we were sorting n values, how long would we expect this algorithm to run in the best case? Briefly describe the best case circumstance.
- If we were sorting n values, how long would we expect this algorithm to run in the worst case? Briefly describe the worst case circumstance.
- If we were sorting n values, how long would we expect this algorithm to run on average? Briefly explain how you arrived at your answer.
What to submit
Add one PDF file to your core directory with this name: problem7.pdf, which
contains your answer to these questions.
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.)
Can I submit after the deadline?
This project is not included in the late work policy for this course. It needs
to be completed on schedule and submitted before the due date above, so that
we have time to grade it and issue course grades in a timely way. Submissions
beyond that deadline will not be considered.
