Due: Tue Jan 17 11:59 pm
Late submissions accepted until Thu Jan 19 11:59 pm
Assignment by Nick Troccoli
Learning Goals
The goals for this assignment are for you to get up to speed with the environment, tools, C and C++ techniques we'll be using for the quarter. This assignment will give you practice with:
- logging into the myth machines to work on and submit the assignment
- using the
sanitycheck
andsubmit
tools to test and submit your assignment - using the GDB debugger to debug a program
- becoming familiar with the C++ Standard Template Library and its provided collection classes
- using C++ library documentation as necessary to look up C++ features and methods
- writing object-oriented programs with classes, methods and instance variables
The spec below is lengthy, but the assignment parts themselves are short; each one is meant to be a refresher / guide on tools and C++ features we'll be leveraging this quarter. You will be answering a few short answer questions, reading some code, and writing a little bit of code. This assignment is a great opportunity to refresh your C and C++ memory; as you're reading through and working on the assignment, please ask questions about anything you don't understand, or anything you need more explanations about, whether it's something you see in the provided code, something about C++ features, classes, etc. We are happy to help!
Log Into Myth
To start this assignment, first you need to set up your system to log in via SSH to the Myth machines, which are the machines you will do your assignment work on this quarter. Our Getting Started guide walks you through how to do this and outlines some options for you to work on assignments - check it out!
Open the Getting Started Guide
Once you are logged into myth, pull up the CS107 guide to working on assignments, which outlines the general flow for working on assignments in both CS107 and CS111. This includes how to get the starter code for an assignment, and how to compile, test and submit your assignment. This handout will walk you through these components in more detail, but be sure to keep the following guide handy:
Open Guide to Working on Assignments
Starter Code
To get started on the assignment, log into Myth and clone the starter project using the command
git clone /afs/ir/class/cs111/repos/assign0/$USER assign0
This line creates a new folder called assign0
in your current working directory containing a copy of the starter code.
If you attempt to clone and receive an error that the repository does not exist
:
- double-check for typos in the path. The path needs to be typed exactly as specified. This includes the odd-looking
$USER
at end, which is a environment variable that expands into your username automatically. - be sure you are logged into Myth
If you confirm you are on a Myth system and your correctly-typed path is not available, this indicates that you were not on the Axess enrollment list at the time we created the student starter code projects. Please send an email to the instructor and provide your username so we can manually set up the starter code for you. Please make sure to enroll in Axess as soon as possible so that the starter code is automatically generated for you in the future.
The starter project contains the following relevant files for your work on the assignment:
readme.txt
: a text file where you will answer questions for the assignmentbuggy.c
: a provided (buggy!) program that you will use to get practice with the GDB debuggermoviecredits.cc
: a program that you will complete to print out the cast for various moviesmoviecredits-util.cc
: a file containing the definition of theMovie
struct and that constructs a test database - you do not need to modify this file.Makefile
: a provided file that contains instructions for how to compile all the assignment programs. You can run themake
command and it will compile all the programs on the assignment for you.movie.hh
andmovie.cc
: the definition of theMovie
class you will be implementingmovietest.cc
: a test program for theMovie
class; you will be modifying this to add one additional test of your owncustom_tests
: a file where you will add a test case for the assignmenttools
: contains symbolic links to thesanitycheck
andsubmit
programs for testing and submitting your work.samples
: a symbolic link to the shared directory for this assignment. It contains:buggy_soln
,moviecredits_soln
andmovietest_soln
; provided fully-implemented sample solutions
1. Enrollment Confirmation
In order to complete your enrollment in CS111, you must fill out the readme with some information about you, confirm your ability to attend the exams and accept the course Honor Code policy.
Open the readme.txt
file in your editor now and edit as appropriate.
As part of this, you must complete the Honor Code Form. When grading your assignment, we will check that you made a submission through this form, so please make sure to fill it out!
Once you have done this, also complete the following setup tasks:
- Join our course discussion forum by visiting the Getting Help page.
- Remember to submit your section preferences (not first-come-first-serve) between Wed Jan 11 5:00 pm PDT and Sat Jan 14 11:59 pm PDT.
2. The GDB Debugger
This quarter, the GDB debugger will be an invaluable tool to help debug assignments. It allows you to pinpoint the source of a crash, set breakpoints to pause your program mid-execution, step through your code and print out variable values, and more.
The CS107 website has a thorough debugging guide that has documentation and tips for using GDB to debug your code:
To provide practice with GDB, we've provided a buggy program called buggy.c
that - you guessed it - is buggy when running on certain inputs. It is a short program that was meant to test a function lastN
which extracts the last N characters of a string and ensures its length is a multiple of N. However, it doesn't quite work as expected....
- Open
buggy.c
and read through the code to get a sense of what it is doing. Use the manual pages to look up information for any functions you want to read more about - for instance, to read up on thestrcpy
function, runman strcpy
. Compile all assignment programs by runningmake
(ormake clean
to remove the compiled executables) and run the program by specifying command line arguments like this:./buggy hello
or./buggy hello cs111
. Compare with the provided (non-buggy) sample solution atsamples/buggy_soln
to see the intended behavior. - We have provided a sample test case in the
custom_tests
file that causes a segfault (crash).custom_tests
is a file where you can write test commands for your assignment programs and run them withsanitycheck
, our provided assignment testing tool (the same as in CS107). When you do,sanitycheck
will run the tests in the file on both your program and the provided sample solution version of the program and compare their behavior and output. This is a great way to test your programs to ensure correct behavior. Click here to read more about sanity check / custom tests. Runtools/sanitycheck custom_tests
to observe the buggy behavior. - Use this provided
custom_tests
test case and use GDB (run GDB on the program itself, notsanitycheck
!) and commands such asbacktrace
,up
,down
andprint
to fix the bug in the code and answer questions 2 and 3 inreadme.txt
by following these steps:- Answer Question 2 in
readme.txt
: what is the most specific line in the file that causes the crash? In 1-2 sentences, explain how you used GDB to find the answer, including which command(s) you used. Use GDB commands as much as possible, even if you are able to answer the question without using GDB. - Answer Question 3 in
readme.txt
: what is the value ofi
in the loop inmain
when the program crashes? In 1-2 sentences, explain how you used GDB to find the answer, including which command(s) you used. Use GDB commands as much as possible, even if you are able to answer the question without using GDB. - identify a one line fix for the program for it to behave as expected, and add the fix to
buggy.c
to eliminate the bug. - Add 1 additional test case of your own to
custom_tests
to test that your program is working as intended, and run the test case withsanitycheck
to confirm the bug is resolved. Hooray!
- Answer Question 2 in
3. C++ STL Collections
In C++, we have the advantage of various data structures ("collections") we can use to store data, such as maps, sets, etc. If you took CS106B, you may be familiar with the Stanford Libraries data structures, which are specific to CS106B. But C++ has its own built-in set of standard STL ("Standard Template Library") collections in the language itself, which are similar to the CS106B versions or other versions of these standard data structures you may have used in other courses / languages. This part of the assignment will give you practice using the STL vector
and map
, and you can read more on your own about others, such as set
.
Having a C++ reference handy can be extremely helpful when learning about C++ features or if you need to look up functionality for a type, such as vector
or map
. We recommend reference sites such as CPPReference or CPlusPlus. We'll be using STL data structures over the course of the quarter so keep a reference handy whenever you need to look up information about how to use them!
vector
A C++ vector
is similar to other resizable arrays / lists / vectors you may have seen; you construct one by specifying the type in <>, and you can access elements by index, add/remove elements, etc. Check out CPlusPlus for an overview:
Here is a short example program that appends entries to a vector and then prints them out. For iterating over elements in a vector, you can iterate using a regular loop counter, or you can use something called a "range-based for loop", as in this example:
vector<int> nums;
// Add elements 0-9, each time appending to the back
for (int i = 0; i < 10; i++) {
nums.push_back(i);
}
// Regular for loop - prints 0-9
for (size_t i = 0; i < nums.size(); i++) {
cout << nums[i] << endl;
}
/* Same, but range-based for loop - we access each element
* as a const reference so that we avoid making copies.
*/
for (const int& num : nums) {
cout << num << endl;
}
Check out the reference for more information on other supported functionality / methods.
map
A C++ map
is similar to other map / dictionary data structures you may have seen; you construct one by specifying both the key followed by the value in <>, and you can access elements by key, add/remove entries, check if something is in the map, etc. Check out CPlusPlus for an overview:
Here is a short example program that adds entries to a map, checks if an entry is in the map, and then prints all entries out. For iterating over key/value pairs in a map, you can use a similar "range-based for loop" - note the somewhat quirky syntax below:
// first type is key, second type is value
map<int, int> numsMap;
// Add 0->0, 1->1, 2->2, 3->3, etc.
for (int i = 0; i < 10; i++) {
numsMap[i] = i; // key and value are both the same
}
// This should print "12 is not in the map"
if (numsMap.find(12) != numsMap.end()) {
// the map contains this element
cout << "12 is in the map" << endl;
} else {
// the map doesn't contain this element
cout << "12 is not in the map" << endl;
}
/* Range-based for loop - we access each pair as a const reference
* so that we avoid making copies. (Auto means "auto-detect" the type;
* it's preferable to always specify types in C++, but here it's ok
* to use auto).
* Prints 0:0, 1:1, etc. each on their own line
*/
for (const auto& [key, value] : numsMap) {
cout << key << ": " << value << endl;
}
However, a word of caution: if a key is not in the map, using []
will insert it! This is called auto-insertion, and is sometimes useful, but can also cause problems. In other words:
map<int, string> numToStrMap;
/* 2 is not in the map, but trying to access it with []
* will auto-add an entry for it with an empty string value,
* and then return that!
*/
string nonExistentValue = numToStrMap[2];
cout << nonExistentValue << endl; // will be empty string
cout << numToStrMap.size() << endl; // will print 1!
Therefore, it's good practice to check if something is in a map first before you try to access it.
Practice: Going to the Movies
To get practice with using STL vector
and map
, we've provided the scaffolding for a program moviecredits.cc
that reads in a movie information database and prints out information about each movie and its cast. You can run it by specifying either "small" or "large" for what dataset to read from:
./moviecredits small
Try running the sample solution to see its intended behavior:
./samples/moviecredits_soln small
Your task is to fill in the implementation of buildMovieMap
, with the following signature:
void buildMovieMap(const vector<Movie>& movies, map<string, vector<string>>& movieMap);
buildMovieMap
takes in list of Movie
structs (a C++ Struct is a way we can define our own variable types that are a collection of other variable types). You can see the definition of Movie
in moviecredits-util.cc
. It also takes in an (assumed to be empty) movieMap
passed by reference, mapping movie names to lists of actor names. This function should 1) populate movieMap
with information about each movie in movies
, and 2) print out the contents of the map. Specifically:
- This function should go through the
vector
in order and populate the map with information about that movie. - It's possible for multiple movies to have the same name (eg. remakes) - if, when adding an entry to the map, you see an entry already exists with that movie name, you should include the year as part of the name just for this new entry, to disambiguate (hint: use the
to_string
function to convert a number to a string). In other words, ifmovies
contains 2 entries, "Movie" from 1950 with cast member "Actor", and "Movie" from 1990 with cast member "Other Actor", thenmovieMap
should look like the following - notice how the first entry doesn't include the year, but the second one does:
{
"Movie": ["Actor"],
"Movie (1990)": ["Other Actor"]
}
- After populating the map, the function should print out the key/value pairs in the map in sorted order, one per line (fun fact - a C++
map
sorts its contents!). Run the sample solution to see the expected output format (note thatmap
's store their contents in sorted order, which is the order the entries should be printed). Note thatvector
s can't be printed directly; so you will need to iterate through the vector to print out each element (in our solution, we print each element followed by a space; it's ok for the last actor name to be followed by a space).
To test, try running ./tools/sanitycheck
which has tests for both the small and large datasets and compares your output with the sample solution.
Our solution for this function is approximately 15 lines, not including comments.
4. C++ Classes
A class allows us to define our own variable type with methods we can call on it (like object.method()
) and with instance variables inside it. This CS106B page gives a great refresher on classes and object-oriented programming. Another great resource is this reference. In particular:
- the constructor is called whenever an object of that type is created; that is where it should initialize its state (instance variables)
- the destructor is called whenever an object of that type goes away (e.g. it's on the heap and deleted, or it's on the stack and it goes out of scope); that is where it should clean up any state (e.g. heap-allocated instance variables)
- an instance method is a function that you call on an object of that type; that method has access to all of that object's instance variables when it runs.
- an instance variable is state within the class; each object of that type has its own copy of any instance variables.
The Movie
Class
We'll be writing code with classes over the course of the quarter. To get practice with implementing them, and in the spirit of the movie problem in the earlier part (though this part is separate from the previous part), we've provided the scaffolding for a class Movie
in movie.hh
(header file) and movie.cc
(implementation file) that you should implement. Check out movietest.cc
for example usage of the Movie
type, and movie.hh
for documentation for its methods and behavior. You can run movietest
by specifying the test number, 1-5; e.g. ./movietest 1
.
Implement Movie
: You will need to add additional private instance variables as part of your implementation. You can import additional libraries if needed, and make private helper methods if you'd like. Our implementation of Movie
requires at most a few lines per method, sometimes just a single line. To test, try running ./tools/sanitycheck
which has tests for all 5 provided tests and compares your output with the sample solution.
Add one new test: Once you are done, you must also fill in the empty yourTest
function in movietest.cc
with one additional test (#6) to test usage of your Movie
class and verify its behavior. Any reasonable test case is fine, and we will not be strict about the code you write as long as it uses Movie
in a test scenario not already provided. Make sure to document your function with a header comment briefly explaining what case you are testing. This test will not be run in sanity check (since it is your own code, so it can't be run against the sample solution), but you can review its output manually to confirm your Movie
class is correct, and during grading we will review the test manually.
Readme: Lastly, answer question 4 in readme.txt
about destructors: if we implemented the destructor for Movie
to print out a message "Movie X is being destroyed" (where X is replaced with the movie name), and we ran test 1, when would this message be printed?
Submitting
Once you are finished working and have saved all your changes, submit by running the submit
tool in the tools
folder: ./tools/submit
. We recommend you do a trial submit in advance of the deadline to allow time to work through any snags. You may submit as many times as you would like; we will grade the latest submission. Submitting a stable but unpolished/unfinished is like an insurance policy. If the unexpected happens and you miss the deadline to submit your final version, this previous submit will earn points. Without a submission, we cannot grade your work. You can confirm the timestamp of your latest submission in your course gradebook.
Grading
Here is a recap of the work that will be graded on this assignment:
readme.txt
: confirming enrollment information and answering short answer questions 2-4movie.hh
/movie.cc
: your implementation of theMovie
classmovietest.cc
: your additional test case inyourTest
documented with a header comment explaining what it is testingmoviecredits.cc
: your implementation ofbuildMovieMap
buggy.c
andcustom_tests
: fixing the buggy program and adding your additional test case
We will grade your code using the provided sanity check tests and also possible additional autograder tests. We will also review your code for style grading. Check out our course style guide for tips and guidelines for writing code with good style!