Due: Mon Jan 12 11:59 pm
No late submissions accepted.

No late submissions are accepted on this assignment (except for OAE accommodations or granted extensions). The deadline is firm without exception.

Assignment by Nick Troccoli, with modifications by John Ousterhout

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 is a short assignment where 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 need more explanations about. We are happy to help!

Learning Goals

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
• reviewing features of C and C++
• 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

For this and future assignments, we have review videos on Canvas that review pointers/memory and C++ classes. Check them out if you want a review under the "Panopto Course Videos" tab. The slides from those videos are available here.

Using the Myth Cluster

All of the assignments for this class will require you to login to the myth cluster using ssh. 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

We will use the same general flow for working an assignments that is used in CS 107. Once you are logged into myth, pull up the CS107 guide to working on assignments for more information - This page will walk you through how to get the starter code for an assignment and how to compile, test, and submit your work:

Open Guide to Working on Assignments

Starter Code

To get started on the assignment, login to the myth cluster and retrieve a copy of the starter code by entering the following command into a console window:

git clone /afs/ir/class/cs111/repos/assign0/$USER assign0

Be sure to type the command exactly as above, including the $USER, or copy and paste the text just to be safe. This command will create a git repository containing starter code for the assignment and place it in a new folder called assign0 in your current working directory.

If the command fails with an error that git "detected dubious ownership" and asks about "adding an exception", make sure to first run the setup.py tool from the getting started guide.

If the command fails with an error that the repository does not exist, double-check for typos in the command, and make sure you are logged into a myth machine. If these checks don't fix the problem, then you were probably not on the Axess enrollment list at the time we created the student starter repos. Please email the Head TA and include your SUNet ID so we can manually set up the starter code for you. Make sure to enroll in Axess as soon as possible (if you haven't already) 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:

• questions.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 that constructs a test database for moviecredits.cc; you do not need to modify this file.
• Makefile: 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 modify 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

Note: this assignment may take some number of seconds to compile using make, as it's compiling in a dataset used in the moviecredits.cc part of the assignment. For this reason, it's expected that running tools/sanitycheck to test your code may take slightly longer than usual.

Exercise 1: Course Logistics

Before beginning work on this project you must complete a few administrative tasks:

• First, read the CS 111 Honor Code Policy to refresh yourself on the Stanford Honor Code and the specific ways it applies to CS 111.
• Complete the CS 111 Honor Code Form below to verify your understanding of the Honor Code. You must complete this form as part of this assignment. Make sure you are logged in to Google with your Stanford email before accessing the form:

Access the Honor Code Form

• Open the file questions.txt in your favorite text editor, enter your information at the top, and fill out the "Exercise 1 portion" of the file by adding your initials in the appropriate boxes.
• Join our course discussion forum by visiting the Getting Help page.
• Remember to submit your section preferences (not first-come-first-serve) between Tue Jan 6 10:15 am PDT and Mon Jan 12 9:00 am PDT.

Exercise 2: The GDB Debugger

The gdb debugger is an valuable tool for debugging C and C++ programs. It allows you to pinpoint the source of a crash, set breakpoints to pause your program mid-execution, print variable values, step through your code, and more. Here are some resources about gdb that you might find useful:

• A short summary of the most useful gdb commands.
• The CS 107 Debugging Guide, which provides a more thorough introduction to gdb.

To provide some practice with gdb, we've created a program called buggy.c that crashes when running on certain inputs. It is a short program that was meant to test a function lastN, which checks a string to be sure its length is a multiple of N characters, then extracts the last N characters of the string. However, the program 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 (you can also access manual pages by entering commands such as "man strcpy" into your favorite Web search engine). 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. Click here to read more about sanity check / custom tests. Run tools/sanitycheck custom_tests to observe the buggy behavior.
3. Run the program again using gdb, invoking it with the same arguments from custom_tests that caused it to crash. Then answer Questions 2A and 2B in questions.txt.
4. Use gdb to determine the cause of the crash. The problem can be fixed with a one-line change (e.g., add 1 new line or change 1 line to be something else) to the program; make that change. Make sure to only change one line in the program. Also make sure to not introduce any other issues like memory leaks!
5. 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!

Exercise 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 exercise will give you practice using the STL vector and map, and you can read more on your own about others, such as set and unordered_map.

While working, it's very helpful to be able to access reference documentation for the C++ library, and there are two popular Web sites that provide C++ reference documentation online: CPlusPlus and CPPReference. We've created a page with quick links to reference documentation for some important classes you'll use in this class. Check it out for some information and example code for some data structures!

Open Data Structures Reference Page

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

You must make two changes to this file. First, fill in the implementation of the build_movie_map method, which has the following signature:

void build_movie_map(const vector<Movie>& movies, map<string, vector<string>>& movie_map);

build_movie_map takes in vector of Movie structs and copies information from the vector to a map (which is initially empty). (A C++ Struct is a way we can define our own variable types that are a collection of other variable types). You can find the definition of Movie at the top of moviecredits.cc. The map is passed by reference, so build_movie_map modifies the caller's copy. This function should go through the vector in order and populate the map with information about each movie, using the movie's title as the key and its list of actors as the corresponding value.

It's possible for multiple movies to have the same name (eg. remakes) or the same year (you do not need to worry about the case where two movies share both the same name and the same year). If, when adding an entry to the map, you see that an entry already exists with the same movie name, you should modify the name of the new entry to include the year as part of the name, to disambiguate it (hint: use the to_string function to convert a number to a string). To be more precise, if movies contains 2 entries for a movie named "Popular Movie", one from 1950 and one from 1990, you should use the title "Popular Movie" for the first instance and "Popular Movie (1990)" for the second.

In addition to filling in the body of build_movie_map, you should also add code to the main function to print out the key/value pairs in the map. The output should be sorted by title. One of the nice things about a C++ map is that it sorts its contents, so if you iterate over it in the normal way, the entries will be in alphabetical order sorted by movie name. Thus, the order of entries in the map will be potentially different from the order in the original vector (e.g. the large dataset is sorted in order of release year). Run the sample solution to see the expected output format; note that you will also need to iterate over the vector of actors for each movie in order to print them.

To test, try running tools/sanitycheck; it will run tests for both the small and large datasets and compare your output with the sample solution.

Our solution for this part is approximately 15 lines, not including comments.

Exercise 4: Movie Class

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. In particular:

• The constructor is called whenever an object of that type is created; it is responsible for initializing the state of the new object (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); it is responsible for cleaning up state, such as 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.

This exercise is intended to refresh your knowledge about basic class design. You will implement a short class Movie that represents a single movie (note: these objects are totally different from the Movie objects in Exercise 3). Each object stores information about one movie, including its title, the actors in the movie, and the role that each actor played. Take a look at the header file movie.hh: it defines the methods and documents how each method should behave, but it doesn't implement any of the methods; the method implementations are in movie.cc.

• Fill in the bodies of the methods in movie.cc so that they implement the behaviors documented in movie.hh. You will also need to add private instance variables in movie.hh to store information about each movie. You may need to add #include statements for library packages that you use in your solution, and you can create private helper methods if needed. The methods in movie.cc require only a few lines of code each (in some cases a single line will do the job).
• Make sure to test your code as you work. We have written a test program movietest.cc, which contains 5 tests to exercise the class; once you have run make, you can invoke a single test with the command ./movietest N, where N is a number from 1 to 5. This will invoke a method named testN in movietest.cc. Running tools/sanitycheck also runs these 5 provided tests and compares your ouptut with the sample solution.
• When you are debugging the assignments for this class, you should read the code of the tests, like those in movietest.cc, so that you understand exactly what's happening. As part of your testing, also open the file movietest.cc and find method test3, which implements test 3. Then answer Question 4A in questions.txt.
• Once you are done, 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.
• When you have completed your implementation of Movie, answer Question 4B in questions.txt.

Submitting

Once you are finished working and have saved all your changes, submit by running the submit tool in the tools folder: tools/submit. Make sure that you have answered all of the questions in questions.txt before submitting.

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 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, the earlier 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:

• questions.txt: confirming enrollment information and answering a few questions, including completion of the honor code survey online.
• buggy.c and custom_tests: fixing the buggy program and adding your additional test case
• moviecredits.cc: your implementation of build_movie_map
• movie.hh, movie.cc and movietest.cc: your implementation of the Movie class and your additional test case in yourTest documented with a header comment explaining what it is testing

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!