This exercise provides a self assessment for standard introductory programming skills, mostly at a freshman level. If will provide you a chance to recall basic programming skills for C++ as well as provide some guidance on whether you have the basic programming skills assumed by third year courses. If you have the expected skills, you should find the assignment simple. Note that introductory C++ skills are part of the prerequisites for this course and will be assumed going forward. I do not assume that you know modern C++, so you can apply older C++ knowledge on this task. We will discuss aspects of modern C++ in the future, and you will be expected to apply them from that point on. Learning how to design better code regardless of the specific language will be a focus of future discussions in the class.
As in all exercises that you perform for this class, there will be rules, but the rules for this exercise are simple. You may not use any external libraries except for the C++ standard library in order to complete this exercise. Your code should not contain buggy behavior or memory leaks.
A template for the project is available
here.
You should not add new files to the template or they will not be graded.
All of your solutions should modify code in the lib/solutions directory.
This helps automated checking for adhering to the rules.
CSIL is not required for performing the assignment, but you can find basic
instructions for accessing CSIL remotely
here.
All exercises in this course have minimum requirements for your development
environment, but I have provided a development virtual environment in CSIL
that you can activate with:
source /usr/shared/CMPT/faculty/wsumner/base/env373/bin/activateThe "Exercises" page for the course also has a Docker image and instructions for how to do all work for the course in a Docker container.
Initially, the template will not compile because of the unit tests that
depend upon your solutions, which you have not yet written.
You can comment out the rules for those unit tests at the bottom of
se-background-template/test/CMakeLists.txt to allow the build to proceed.
If you complete the tasks in order, then they will also succeed in order,
and you can simply run the unit tests appropriate for tasks you wish to check.
When checking your final submission, make sure to uncomment all tests!
In order to actually build the project, you should create a separate build
directory for an "out of source" build. For instance, if you have a cmpt373
directory containing the unpacked se-background.tar.gz in
cmpt373/se-background-template/, you can create cmpt373/se-background-build/
as the build directory. From within the build directory, run:
cmake ../se-background-template/This will configure the build for the project within the build directory.
You can then build the project itself by running make in the build directory.
Finally, while I may provide you most unit tests for this exercise, that will not necessarily be the case for all exercises in the future. There may be additional cases that you want to consider and add to the provided unit tests when checking your solutions. This is fine. Any modifications that you make to the unit tests will be ignored during grading.
As always, do not share your code or show your code to others.
This group of tasks is mainly centered around making sure that you understand ways of defining function signatures and passing arguments around. You do not need to make use of modern C++ and will not be graded on style for this task. You should find it straightforward.
Define a function task01 in task01.cpp that takes a single int argument.
Declare the function with a prototype in task01.h.
The function should increment the value by one and return the result.
Design the API such that the caller and callee have separate, unique copies of
the argument.
Note that creating distinct copies supports composition because the caller and
callee cannot interfere with each other except through the argument values.
For lightweight types like primitives or small objects, passing arguments in
this way is efficient and preferred.
If bin/unit01 passes then you meet the functional requirements for this task.
Note that other tasks have additional nonfunctional requirements tied to the
quality of the API you design, how it manages memory, or other such features.
Passing the unit tests may not be enough to know that other tasks are correct.
Define a function task02 in task02.cpp that takes a single int argument.
Declare the function with a prototype in task02.h.
The function should increment the value by one and return the result.
Design the API such that the caller and callee share the argument value.
Modifying the value in task02 should change the value that the caller
observes. This is an "out parameter". In general you should avoid them.
They make code harder to understand by modifying state
(variables and their values) of the caller in non-obvious ways.
As a result, reasoning about the behavior of the caller is harder and tends
to be noncompositional.
Especially in modern C++, you should aim to avoid out parameters unless absolutely required.
Similar to task 1, if bin/unit02 passes, then you meet the functional
requirements for this task. This pattern continues for the remainder of tasks.
Again, you may find it useful to comment out the specific tests for each task
and uncomment them as you solve the tasks.
The Support.h header file defines a HotPotato class.
Right now, the class keeps track of how many pats of butter have been
added to a hot potato.
This class has custom implementations of its destructor, constructors, and
assignment methods to print out when the methods are called.
This should help you to see the behaviors of the code that you write.
Recall that these are referred to as special member functions in C++.
The compiler provides them by default unless you want to customize their
behavior.
This can get complicated, but if you want to know more, references are
available online.
[0]
[1]
[2]
[3]
Define a function task03 in task03.cpp that takes a single
HotPotato argument.
Declare the function with a prototype in task03.h.
The function should extract the butter pat count of the HotPotato
and return a butter pat count that is one greater.
You do not need to use the addButter method to perform this.
At no point should any copies or assignments to the HotPotato occur.
It should not be possible to modify the original HotPotato.
You can run the generated unit test in bin/unit03 to see the behavior
when using your function and know whether extra copies are being made.
Note that passing the test suite does not mean that your solution is correct.
It simply sanity checks the functional requirements.
Any object that you do not know to be lightweight should probably be passed without copying but also without the ability to modify the original object. This promotes both efficiency and compositional reasoning about program behavior.
Define a function task04 in task04.cpp that takes a single
HotPotato argument.
Declare the function with a prototype in task04.h.
The function should increment the butter pat count of the HotPotato and return it.
This time, instead of incrementing the value yourself, you must call the
addButter method of the HotPotato.
However, at no point should any changes be made to the original HotPotato.
Note that during grading I can replace the implementation of HotPotato
to easily enforce that you are performing the correct behavior.
Try running bin/unit04 to see the difference in overall behavior compared
to the previous task.
Copying an object is useful when you want to retain or modify an independent version of the object. For instance, you want to be able to modify the object while not affecting the original (again, to promote compositional reasoning). Alternatively, you may want to store an object as a field of another object. If the lifetime of the original can be shorter than the lifetime of the field, then copy of the object is required as opposed to a reference to the original.
There are often trade-offs to be made in deciding whether to copy or not, and they are often intertwined with other aspects of higher level system design.
Define a class Task05 in task05.cpp with a constructor that takes
a single object of type HotPotato as an argument and retains it.
Declare the class in task05.h.
Note that in C++, you should usually declare constructors that take one argument
as explicit.
We will discuss this further in the next task, but for now make
your constructor explicit.
Add a butterExcessively method to your class.
Calling butterExcessively on your class should call
addButter 5 times on the original object.
Since butterExcessively should not throw or propagate exceptions,
you should mark it noexcept.
Note that in this case your Task05 class defines a lightweight type.
Making copies of your class is efficient, and it can be passed around
as a value type to other functions. Such value types
can provide convenient lightweight non-owning abstractions. std::string_view
is an instance of such a type.
We will discuss these more when we discuss modern C++.
At they same time, they must be used carefully in an API in order to avoid lifetime mismatches. Good linters and compiler tools can look for such bugs automatically. These non-owning value types are most likely at the boundaries between components or within generic APIs.
This group of questions focuses on making use of the C++ standard library.
Keep the rules of the exercise in mind.
Note also that in newer versions of C++ these are easier, as
ranges
should enable workflow more like
LINQ
in .NET or
streams
in Java.
We will discuss the impact of those designs later,
but for now you should not use ranges.
For these tasks, you may also find it helpful to consider the documentation for
std::string,
std::vector,
and some iterators.
You will often want to work with APIs that operate on strings. Note that many
of these should be operating on domain objects instead of strings
(avoid "stringly typed APIs"
[6]
[7]
[8] – we will discuss this later),
but nonetheless strings are common form of data to operate on as well.
We will discuss later how to better handle API's that involve even non-domain
object strings, but for now we will simply consider using the C++
std::string class.
Define a function task06 in task06.cpp that takes a single C++ std::string
as a argument.
Declare the function with a prototype in task06.h.
The function should sum and return the unsigned integral values of
the characters, essentially computing a checksum.
The exact return type should be uint32_t and all checksum math should be done
within that type's range (allowing rollover).
You should try to do this avoiding loops, but using a loop is allowed.
In future exercises, you will sometimes be forbidden from writing loops.
As a final reminder, where it is possible to use a domain relevant type instead of a string, you should almost certainly do so. Stringly typed code is bad and will not count toward your project. Code that operates on strings because its purpose is to operate on strings is, on the other hand, fine.
You should be well acquainted with different data structures for maintaining
maps, lists, etc. at this point. While your default for any task should be
a std::vector or a std::array, being comfortable using other data structures
should be second nature as well.
Define a function task07 in task07.cpp that takes a single C++ std::string
and a std::unordered_map from chars to std::strings as an argument.
Declare the function with a prototype in task07.h.
The function should return a new string in which each character that is a key
in the map is replaced with the string to which the key is mapped.
While std::unordered_map has performance characteristics that can make it
undesirable to use in production code, it is more than suitable for prototyping
and demonstrating functionality.
From classes like 225, you should understand why general purpose chaining hash
tables may have pathological behavior.
We may consider related issues later in the semester.
Note, you should not make any unnecessary/extra copies of data structures while completing this task. Try to minimize the memory allocations that you make.
This last section just double checks that you have basic understanding of objects, classes, and constructing them. It does not check that you have a good understanding of OOP or how to use it well. We will later address that in class.
A classic way of making sure that students have an understanding of objects and
pointers is to have them implement linked lists, so this task will have you
do that again in a goal oriented fashion.
You will implement a linked list that contains only ints.
You will be told some basic design constraints that must be satisfied,
and the way you implement the class is up to you.
You may not, however, make use of standard C++ collections for this task.
If you are comfortable with pointers and classes, it should be straightforward.
Declare a class called OrderedList in task08.h and define it in task08.cpp.
Lists can be created with the default constructor and will be empty after
construction.
In addition they should have the following methods:
add() – This method takes a single int argument and inserts it into the
ordered position in the list. That is, if a list contains [0, 1, 3], then
adding 2 will result in [0, 1, 2, 3].
The method returns a Node* corresponding to the entry for the added value.getNode() – This method takes a single int argument and returns a Node*
object corresponding to the entry in the linked list for the node containing
the given value.
If the element in the list is not present, the pointer should be a nullptr.
If the linked list is destroyed, then this pointer need no longer be valid.
You might see several issues with this is design. We will discuss techniques
that could improve it later in class.The Node class should be a nested class of OrderedList and have the following methods:
getNext() – This method will return the Node* of the next entry in
the list. Again, the pointer will be a nullptr if the next entry does not
exist.remove() – This method will remove the given entry from the list.
Any Node* referring to the entry are invalidated and may no longer be used.getValue() – This method returns the int value corresponding to this
entry in the list.You are not assessed on the computational complexity of these operations.
Remember that in addition to the desired behaviors, your design should not have
any memory leaks. You may use new and delete in this exercise, but you will
not be allowed to use them at any other point in the semester.
Create an archive of your solution by changing into the directory containing your project template and running:
tar zcvf e0.tar.gz se-background-template/The names of directories matter. Do not include your build artifacts. You can then upload this archive to CourSys.
Valid submissions should not contain your build directory and must be able to compile in CSIL.