This exercise provides a self assessment for standard introductory programming and git skills, mostly at a freshman level. It 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 relatively 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.
There are two parts to the exercise. Part one focuses on C++ skills, while part two focuses on using git. The two parts are clearly identified below and they have separate instructions for submitting.
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.
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.
A template for this part 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.
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 cmake --build . in the
build directory. The template also ships "CMake presets", which can make
managing out of source builds easier. For example, you can run
cmake --preset debug
cmake --build --preset debugfrom within se-background-template/ itself to configure and build inside
build/debug/. ctest --preset debug runs the tests in that directory, and
cmake --workflow debug is shorthand for the full configure, build, and test
process.
Finally, while I may provide you most unit tests for this part of the 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 test/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 test/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 test/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 test/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 the 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 an 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 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 to part one by changing into the directory containing your project template and running:
tar zcvf e0.tar.gz --exclude=build 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.
By this point, you should already be able to use and understand the basics of
version control. You should have specifically used git while managing a small
team project. In this part of the exercise, you will demonstrate how to use some of
the features of modern version control along with how to use integrated
tools that can assist in coordinating and enforcing tasks like code review,
scheduling, and issue tracking in a team development environment. The git skills
that you use in this part of exercise are core essentials of modern software
development practices. Not only will you be expected to use these techniques,
and the features of GitHub, while developing your semester projects,
but any work that you do outside of these workflows simply may not be taken
into account during grading.
There are many outside sources of information on using git. The git
website has an excellent book along with
introductory videos that provide an excellent and
thorough introduction. They also have numerous
tutorials. Much of the information in this
part comes from these tutorials or expects you to be able to follow these
tutorials and then demonstrate your understanding.
NOTE, within this part of the exercise and for the class term project, all work should be completed using SFU's private GitHub Enterprise server at https://github.sfu.ca. Work submitted using github.com may not be graded.
git BasicsAs you already know, a version control system (VCS) tracks the changes in files over time. Thus, if you want to know when or why a particular change was made to a file, the VCS should hold the answer. Managing these versions also means that the VCS can coordinate and track the changes made by multiple developers, ensuring that changes from multiple developers do not (textually) interfere with one another. In a modern VCS, a set of selected changes to files is applied atomically. That is, if the changes do not interfere with other changes concurrently made by another developer, then the changes are all applied simultaneously, otherwise, they are not applied.
One feature of git and other distributed version control systems is that you
locally batch together groups of changes to files into atomic commits.
You make your changes on your own computer. Then you can choose to share
these batches of changes with others by pushing them to a remote
repository on a different machine or server.
You should have past experience with:
git clonegit add, git rm, and git mvgit commitgit status, git diff, and git loggit reset HEAD ...git checkout -- ...git push and git pull.gitignoreIf you are uncomfortable with these git basics from your previous classes,
then you can learn more in the following sections of the git book:
Once you are ready, the first step will just make sure that you can demonstrate these.
Create a new private repository using SFU's GitHub server.
Give both the instructor () and the TAs ()
access to the private repository.
You can do this through the menus:
"Settings" ⟶ "Collaborators" ⟶ "Manage Access" ⟶ "Add People".
This is required for your submission for this part of the exercise to receive a grade.
You will use this repository for all remaining tasks completed in this exercise and
submit a cloneable URL of the repository at the end.
The repository must contain exactly two commits. The first commit
to the repository must have a main branch with exactly one file called
student.txt, and file must contain exactly one line with your SFU user ID
(your short email name) without the @sfu.ca suffix.
The second commit must rename/move student.txt to username.txt and add a
second file called readme.md.
The second file may contain anything you want.
These two commits must (naturally) be pushed to the remote GitHub server.
Branching in a VCS allows different versions of a project to be worked on at the same time and even combined later. Specifically, branching refers to creating a divergent history for a project. The main history of the project can continue normally on the main branch, and you can make experimental modifications to a second branch without affecting other developers' ability to use the main one. In fact, they may be entirely unaware of the changes that you make to the second branch. Once the second branch is in a desired state, you can merge the histories again, applying the desired changes from the second branch into the main one.
A primary distinguishing feature of git is that branching is easy and
lightweight enough that it often becomes one of the primary tools for tracking
and managing changes to a software project. We will explore this more in
round 3.
Again, you most likely already know about and understand:
git switch <branch>, git switch -c <new-branch>HEADgit merge ...If you feel uncertain or in order to gain a better understanding,
you can read the following portions of the git book:
You may also try one of the online tutorials.
Create a second branch called feature in your repository. Add a new file
called diary.txt to the feature branch that contains anything you want.
Commit those changes to feature.
Merge the feature branch into main.
Be careful about the direction of the merge.
After this, main should now contain diary.txt.
You should now be on the main branch. Create a file called recipes.txt and
commit it.
Create another branch called roguechef and modify recipes.txt on
that branch. Make sure to then commit it. Don't merge yet! Back on the main branch,
modify recipes.txt differently before committing it. Now merge roguechef
into main. This will cause a conflict because the changes in the two branches
interfere. Resolve the conflict and finish merging roguechef into main.
As you saw in chapter 3.4, branching can be used to manage experimentation as part of developing a single feature, maintaining legacy versions and new development versions, and more. In addition, as we shall see shortly, branching can also be used to manage and enforce peer review of all code before it is committed to the repository. From now on, you should be following this latter practice for your projects this semester.
However, there are also some risks that ought to be recognized. In particular, maintaining many different branches can become undesirably confusing for developers, and the longer a branch lives without being merged into its eventual targets, the less likely the branch is to merge with few conflicts and little rework (or at all). The benefits and trade-offs of these workflow options need to be assessed and balanced in order to design a workflow that fits best for your project. Many companies shift to a trunk based approach to manage the risks of stale branches.
For projects this semester, you will follow a simple GitHub Flow. You can find a full explanation of GitHub workflows here. Read this documentation for a full explanation of the workflow. You can also find videos online illustrating a simple use of GitHub Flow along with features like pull request management and code review. Watch this video. It contains a clear illustration of the steps to follow for every change that you make to the repository. Roughly, the usual steps are as follows:
Note, I will track the pull requests as one metric of measuring your overall contributions to your semester projects. Do not delete the source branches as you proceed, as I can use these to give you credit and resolve issues in your group.
For your semester projects, you will receive credit for solid contributions
that make their way into your main or develop branch. This provides
extra incentives to keep your branches short lived and focused.
Create a new branch topsecret and commit a single file called secrets.txt
to it.
Create a pull request for the branch. From the pull request management
page in SFU GitHub, approve the pull request to finally merge the branch into
the main branch of the repository.
Do not delete the topsecret branch.
NOTE: In a real project, you should not approve your own pull requests! In this case, you are doing so simply to learn how the system works. For your term project, your pull requests should be reviewed and approved by another team member before being merged. Branch protection rules in GitHub can enforce this rule for you automatically.
GitHub can also identify units of work as issues. An issue can be a bug fix, a documentation change, a feature addition planned for a future sprint, or any other unit of work. The issues page of the repo provides a convenient way of organizing these issues along with a platform for discussing them, assigning them to developers, and monitoring their progress. Using this system for your semester projects can help to ensure that you do not forget a task or lose track of it amongst the many requirements you must fulfill.
Issues can also be assigned to milestones, which are commonly used to identify deadlines or iteration/sprint boundaries in a project. By having both issue tracking and milestone scheduling, GitHub allows you to flexibly keep track of the tasks that need to be performed and schedule or reschedule them as necessary.
Create a new issue titled "Add more cats to the readme". Create a new milestone and assign the issue you created to it.
Now modify readme.md on a new branch by adding the word cat to it
(anywhere you like) and commit it to the repository with a commit message that
includes the words "Fixes #N" where N is the number of the issue you created.
Push the new branch in order to create a pull request. Accept the pull request.
To submit this part of the exercise, you must submit the cloneable location of your repository via CourSys. You can find this on your repository main page. Click the "Code" button and select the "SSH" option.
For instance, my submission might be
1
git@github.sfu.ca:wsumner/exercise2.git
git includes many additional features that allow you to more conveniently
change, navigate, and extract useful information from the history of a project.
Three particularly useful features are interactive staging, stashing,
and tools for debugging. In addition, recall that we spoke in class about how
analyzing git logs could help you to identify problem areas in your project.
If you make a mistake, you can "undo" a local commit while keep the changes in your working tree by using:
1
git reset --soft HEAD~1
Interactive staging allows you to look at the changes in your working directory as diffs and select exactly the combination of changes you want for a commit. This means that you can choose to commit only part of the changes to a file if you made changes to the same file that semantically belong to different commits.
You probably noticed that checking out a branch required a clean working
directory (with no uncommitted changes). Sometimes you might have changes in
your working directory that you do not yet wish to commit. In this case, you
can stash the
changes for later, change branches to do your work, change back to the original
branch, and unstash your uncommitted changes on the original branch. It may
sound complicated, but it is quite straightforward to use.
Git contains some commands that can greatly simplify
debugging your
code. In particular, you'll find you can use git blame to identify the last
commit (and developer) that touched a particular line of code. Sometimes,
though, you'll want to perform a binary search on the history of a project in
order to discover when a bug was first introduced. This can be done either
interactively or automatically using git bisect. These are powerful tools to
have in your arsenal.
There are many git visualization tools, but on the command line you can also visualize git history and branches with:
1
git log --graph --abbrev-commit --decorate
Or in a more condensed form:
1
git log --oneline --decorate --graph --parents
What do you think the history should look like if you followed instructions? Do your classmates' graphs look like yours?
Git has many ways to make mistakes. It may have equally many ways to recover
from mistakes. If you face a problem, others have too.
Oh Shit, Git!?! is a handy collection of problems
and git recipes for how to recover from them.