CSCI 104 - Fall 2019 Data Structures and Design

Homework 1

A Few Notes on Repositories

  1. Never clone a repository into another. If you have the course material in a folder and you clone your personal repo hw_username inside it, the outside repository will start tracking the new files and it will be a mess. Whenever you want to clone another repository, you need to do it in the folder above, adjacent to your original repository.
  2. If your homework repositories are not available, make sure you've followed the instructions for creating your account. That set of instructions is available at the end of lab zero.

Skeleton Code

On many occasions we will want to distribute skeleton code, tests, and other pertinent files. To do this, we have made a separate repository, homework_resources, under our class GitHub site. You should clone this repository to your laptop and do a git pull regularly to check for updates (yes, even we sometimes make mistakes; when we do, we will fix them as quickly as possible, but you'll only get the fixes when you pull).

git clone git@github.com:usc-csci104-fall2019/homework_resources.git

Here is a clickable link: https://github.com/usc-csci104-fall2019/homework_resources. Again, be sure you don't clone this repository into your hw-username repo, but at some higher-up point like in a csci104 folder on your computer.

1. Course Policies (10%)

Carefully study the information on the course site and answer the following questions about course policies. Anywhere from no to all answers may be correct. Place your answers to this question in a file named ANSWERS.md in your homework repository.

Part (a)

Which of the following are acceptable behaviors in solving homework problems and doing projects?

  1. Looking up information relevant to the course online.
  2. Looking up or asking for sample solutions online.
  3. Copying code from my classmates, and then editing it significantly.
  4. Asking the course staff for help.
  5. Sitting next to my classmate and coding together as a team or with significant conversation about our approach.
  6. Sharing my code with a classmate, if he/she promises not to copy it, but to just read over it and learn from it.

Part (b)

To dispute a grade on an assigment you should:

  1. Email your professor immediately.
  2. Fill out the homework regrade form.
  3. Post on Piazza if you do not receive any response to your regrade request.
  4. Raise an issue within 1 week of receiving the grade.

Part (c)

Which of the following are recommended ways of writing code?

  1. gedit
  2. emacs
  3. Eclipse
  4. sublime
  5. Microsoft Visual Studio
  6. notepad

Part (d)

What is the late submission policy?

  1. Each assignment can be submitted late for 50% credit.
  2. Each student has 4 late days of which only two can be used per HW.
  3. Students need to get approval before submitting an assignment late.
  4. One hour late submission is acceptable for each assignment.
  5. There is no late policy.

Part (e)

After making a late submission by pushing your code to Github you should:

  1. Do nothing. Sit back and enjoy.
  2. Complete the online submission form as you would for an on-time submission.
  3. Start the next assignment sooner.

2. Git Quiz (10%)

Put your answers to this question in the file named ANSWERS.md.

Part (a)

Which of the following git user interfaces are accepted and supported in this course?

  1. Git Bash (Windows)
  2. GitHub Desktop Client
  3. Terminal (Mac or Linux)
  4. Eclipse eGit
  5. Tower Git Client

Part (b)

When cloning a Git repo, which of the following should you avoid?

  1. Cloning into a folder that itself is a git repo.
  2. Cloning into a sync'ed folder like Dropbox or Google Drive.
  3. Cloning into the Desktop folder of your VM.

Part (c)

Provide the appropriate git command to perform the following operations:

  1. Stage an untracked file to be committed. The (hypothetical) file is called 'hw1q2b.cpp'.
  2. Display the details of the last three commits in the repository.

Part (d)

Let's say you staged three files to be committed. Then, you ran git commit. What will git do?

Part (e)

What is the full command to re-clone your private CSCI104 repo to your VM? Assume you are in an appropriate folder.

3. More Git Questions (10%)

In this problem, we will be working with a fictional sample repository, which we pretend is located at https://github.com/usc-csci104-fall2019/SampleRepo. There is no actual repo there, so don't be surprised if you cannot actually clone it or otherwise interact with it. This exercise is designed to measure your understanding of the file status lifecycle in git. Please frame your answers in the context of the following lifecycle based on your interaction with the repository as specified below:

Git File Status Lifecycle

Figure courtesy of the Pro Git book by Scott Chacon

Parts (a) through (f) should be done in sequence. In other words, when you get to part (f), you should assume that you already executed the earlier commands (a) through (e). You must use the terminology specified in the lifecycle shown above, for example the output of git status is not accepted as a valid answer. For the purposes of this question, you can assume you have full access (i.e., read/write) to the repository. Put your answers to this question in the file named ANSWERS.md.

Part (a)

What is the status of README.md after performing the following operations:

# Change directory to the home directory
cd

# Clone the SampleRepo repository
git clone git@github.com:usc-csci104-fall2019/SampleRepo.git

# Change directory into the local copy of SampleRepo
cd SampleRepo

Part (b)

What is the status of README.md and fun_problem.txt after performing the following operations:

# Create a new empty file named fun_problem.txt
touch fun_problem.txt

# List files
ls

# Append a line to the end of README.md
echo "Markdown is easy" >> README.md

Part (c)

What is the status of README.md and fun_problem.txt after performing the following operation:

git add README.md fun_problem.txt

Part (d)

What is the status of README.md and fun_problem.txt after performing the following operations:

git commit -m "My opinion on markdown"
echo "Markdown is too easy" >> README.md
echo "So far, so good" >> fun_problem.txt

Part (e)

What is the status of README.md and fun_problem.txt after performing the following operations:

git add README.md
git checkout -- fun_problem.txt

Also, what are the contents of fun_problem.txt? Why?

Part (f)

What is the status of README.md after performing the following operation:

echo "Fancy git move" >> README.md

Explain why this status was reached.

Valgrind

You will lose points if you have memory leaks, so be sure to run valgrind once you think your code is working.

You can run valgrind as follows:

$ valgrind --tool=memcheck --leak-check=yes ./sum 4098

If you have no errors, your leak summary will look like this, though note that the number of bytes and blocks in use at exit might differ:

==3184== HEAP SUMMARY:
==3184==     in use at exit: 72,704 bytes in 1 blocks
==3184==   total heap usage: 1 allocs, 0 frees, 72,704 bytes allocated
==3184== 
==3184== LEAK SUMMARY:
==3184==    definitely lost: 0 bytes in 0 blocks
==3184==    indirectly lost: 0 bytes in 0 blocks
==3184==      possibly lost: 0 bytes in 0 blocks
==3184==    still reachable: 0 bytes in 0 blocks
==3184==         suppressed: 72,704 bytes in 1 blocks

These 72,704 bytes come from a known error in the g++ and valgrind compatibility, and you should not worry about them.

Command Line Arguments

Hint: In order to read parameters as command line arguments in C++, you need to use a slightly different syntax for your main function: int main (int argc, char* argv[]). When your program is called at the command line, argc will then contain the total number of arguments that the program was given, and argv will be an array of strings, the parameters the program was passed. The char* at argv[0] is always the name of your program, then argv[1] is first argument. The operating system will assign the values of argc and argv, and you can just access them inside your program.

4. File Reverser (15%)

Write a program that reads in a text file and outputs the characters of that file in reverse order to the terminal. To achieve this, you will need to use dynamic memory allocation. The program should receive the filename as a command line parameter. An empty file_reverse.cpp file is provided in the file_reverse directory of the skeleton code for you to work in.

For the text file, the first line will consist only of an integer representing the number of characters in the file; let's call it n. This will be followed by n characters on the second line. The following is a sample input and output of the program.

Input text file example.txt:

44
The quick brown fox jumps over the lazy dog.

Compiling the program on the command line:

g++ -g file_reverse.cpp -o file_reverse

Running the program and the output:

$ ./file_reverse example.txt
.god yzal eht revo spmuj xof nworb kciuq ehT

Another input text file example:

27
Able was I, ere I saw Elba.

The output:

.ablE was I ere ,I saw elbA

5. The Rani (55%)

Please put all solution code in the file named the_rani.cpp. In the future you will be able to separate your code into separate files, since you will be required to submit a makefile.

The Rani is planning to run her latest round of experiments to build genetically modified mutant creatures. In order to do so, she will start with a population of experimental subjects taken from Miasimia Goria, and subject different sets of them to different experiments. She needs to keep track of which subjects are in which experiment, and which experiments they have been subjected to in the past, so that when she finally finds a suitable mutant, she can remember what experiments she performed to get it.

You will write a program that helps her with keeping track of her experiments - while she is a world-class mad scientist, her coding skills were not enough to get her into USC Computer Science. You will maintain a 2-d array of strings subject_history[][], where subject_history[i] stores all of the subjects currently involved in experiment i, and subject_history[i][j] contains a string listing all of the experiments that this particular subject has been a part of.

You will be given her experimental logbook, which contains a sequence of the following operations, one per line. Errors and how to handle them are discussed below.

Your program will take two strings as input: the first specifies an input file, and the second specifies an output file. The input file could contain many different slates of experiments. Any time you encounter the line START n for some parameter n, the previous experiment is completely discarded, and a new slate of experiments is started from scratch. Once the last line in the input file has been processed, the program should correctly deallocate all memory and terminate.

We are providing you with some skeleton code to get you started in the homework_resources repo (see the top of this assignment for information on that repo). In your solution, you cannot use vector, deque, or list data types from the STL. Instead you will be dynamically allocating and deallocating all of your memory via arrays of strings. In addition, you should be using good programming style by breaking your code up into smaller class functions (consider carefully what functions should be private and public). Outside of these requirements, you are free to make any changes you like to the skeleton code; it is merely given to you as a suggestion. The most important part of this problem is to make sure that your solution does not leak memory. You will lose significant points (more than half) for serious memory leaks.

Your program should be robust to many types of errors, but there are some that would be very cumbersome for you to handle. For that reason, we provide you here with a list that hopefully covers all/most of the errors that could come up. If you have questions about errors not covered here, post (publicly) on Piazza. If multiple errors from the list below apply, only output the first message. For instance, if a command has a wrong number of parameters, and is given a string instead of an integer, just output that it has the wrong number.

Handling Runtime Errors

Whenever you diagnose an error in a line, you should write Error on line <number>: <message> to the output file where <number> is the line number of the incorrect command you found followed by the error-specific <message> on the next line. Once an errors is caught and the corresponding message is written to output, the program should continue. Below, we will list which types of errors in lines you need to catch, and which ones we promise will not happen.

When a command contains multiple errors (i.e. QUERY -1 5), you only need to write out the first error. The order that errors should be check is the order they are listed above. Error messages should be printed without the quote around them: when we say message "no subjects yet", your output file should contain Error on line <number>: no subjects yet).

Errors You Don't Need to Handle

Hints on Handling Parameters of Incorrect Types

C++ provides several useful functions for turning strings into numbers (integers or doubles). Check out C++ documentation to learn about them and save yourself a lot of work. One method would put the string into a stringstream and extract numbers from it. Another would just use conversion functions explicitly. Conveniently, these methods also let you know when they failed, which indicates that the input was not a number. Unfortunately, even functions that are supposed to extract an integer will not fail when the string is actually a double. When you try to extract an integer from the string "3.14159", you will simply get 3.

To deal with this, we offer three potential approaches (there may be more). The first is to extract a double, then check if the double has zero for its fractional value (there is a function to get the fractional part of a double). If so, convert it to an integer; otherwise, treat it as an error. Another is to think about which symbols are not supposed to occur in an integer number. Then check out functions like find_first_not_of() and some of its relatives to see how you might easily detect such incorrect symbols. A final option might be to peek into the stringstream you're working with to check whether the next character is allowed after reading an integer.

A Note on Exceptions

You are encouraged (but not required) to familiarize yourself with exceptions, and use them in your error-checking process. There is a catch clause supplied in TheRani::main which can be modified to output correctly formatted errors. If you use exceptions, other exception classes you might use from <stdexcept> include invalid_argument and runtime_error. While it's good practice to use a semantically appropriate error type to differentiate in the catch block, for the purpose of this exercise any exception may be thrown as long as the message is correct. This is because the existing try block has a blanket catch(exception& e), which will catch any of these exceptions and print just the message.

For some very basic testing of your code (obviously, our real test cases will be much more difficult), we are providing you with an easy input and the corresponding output. The files are linked below, and are also in the homework resources repo. We provide you with two versions of the input: one that will work for your program, and another that has some comments added so that you can see what the input means:

Submitting Your Solution

You can submit your homework here. Please make sure you have read and understood the submission instructions.

WAIT! You aren't done yet! Complete the last section below to ensure you've committed all your code.

Commit and Re-clone Your Repository

Be sure to add, commit, and push your code in your hw1 directory to your hw-username repository. Now double-check what you've committed, by following the directions below (failure to do so may result in point deductions):

  1. Please make sure you have read and understood the submission instructions.
  2. Go to your home directory: $ cd ~
  3. Create a verify directory: $ mkdir verify
  4. Go into that directory: $ cd verify
  5. Clone your hw-username repo: $ git clone git@github.com:usc-csci104-fall2019/hw-username.git
  6. Go into your hw1 folder: $ cd hw-username/hw1
  7. Recompile and rerun your programs and tests to ensure that what you submitted works.
  8. Go to the Assignments page and click on the submission link.
  9. Find your full commit SHA (not just the 7 digit summary) and paste the full commit SHA into the textbox on the submission page.
  10. Click Submit via Github
  11. Click Check My Submission to ensure what you are submitting compiles and passes any basic tests we have provided.