Assignment 0: Welcome to CS111!

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 and submit 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 assignment
  • buggy.c: a provided (buggy!) program that you will use to get practice with the GDB debugger
  • moviecredits.cc: a program that you will complete to print out the cast for various movies
  • moviecredits-util.cc: a file containing the definition of the Movie 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 the make command and it will compile all the programs on the assignment for you.
  • movie.hh and movie.cc: the definition of the Movie class you will be implementing
  • movietest.cc: a test program for the Movie class; you will be modifying this to add one additional test of your own
  • custom_tests: a file where you will add a test case for the assignment
  • tools: contains symbolic links to the sanitycheck and submit programs for testing and submitting your work.
  • samples: a symbolic link to the shared directory for this assignment. It contains:
    • buggy_soln, moviecredits_soln and movietest_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!

Access the Honor Code Form

Once you have done this, also complete the following setup tasks:

  1. Join our course discussion forum by visiting the Getting Help page.
  2. 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:

Open CS107 Debugging Guide

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....

  1. 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 the strcpy function, run man strcpy. Compile all assignment programs by running make (or make 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 at samples/buggy_soln to see the intended behavior.
  2. 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 with sanitycheck, 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. Run tools/sanitycheck custom_tests to observe the buggy behavior.
  3. Use this provided custom_tests test case and use GDB (run GDB on the program itself, not sanitycheck!) and commands such as backtrace, up, down and print to fix the bug in the code and answer questions 2 and 3 in readme.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 of i in the loop in main 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 with sanitycheck to confirm the bug is resolved. Hooray!

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:

Open Vector Reference

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:

Open Map Reference

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, if movies contains 2 entries, "Movie" from 1950 with cast member "Actor", and "Movie" from 1990 with cast member "Other Actor", then movieMap 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 that map's store their contents in sorted order, which is the order the entries should be printed). Note that vectors 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-4
  • movie.hh/movie.cc: your implementation of the Movie class
  • movietest.cc: your additional test case in yourTest documented with a header comment explaining what it is testing
  • moviecredits.cc: your implementation of buildMovieMap
  • buggy.c and custom_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!