# CSCI 104 - Fall 2017 Data Structures and Object Oriented Design

## HW1

• Due: Fri. Sep. 1, 2017, 11:59pm (PST)
• Directory name in your github repository for this homework (case sensitive): hw1
• Once you have cloned your https://github.com/usc-csci104-fall2017/hw-username repo, create this hw1 folder underneath it (i.e. hw-username/hw1).
• If your hw-username repo has not been created yet, please do your work in a separate folder and you can copy over relevant files before submitting.

### A Few Notes on Repositories

1. Never clone one repo into another. If you have a folder cs104 on your VM and you clone your personal repo hw_usc-username under it (i.e., cs104/hw_usc-username) then whenever you want to clone some other repo (such as the repo we use to give you skeleton code, or another personal repo you may have created), you need to do it back up in the cs104 folder or another location, NOT in the hw_usc-username folder.
2. Your repos may not be ready immediately but be sure to create your GitHub account and fill out the GitHub information form linked to at the end of Lab 00.

### 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-fall2017/homework-resources.git  Again, be sure you don't clone this repo into your hw_usc-username repo, but at some higher-up point like in a cs104 folder on your laptop. Note: If you can't access the repository, you can find the files for HW1 here (sum) and here (therani). ### Problem 1 (Course Policies, 10%) Carefully study the information on the course web site, then 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 hw1.txt #### Part (a): Which of the following are acceptable behaviors in solving homeworks/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. Assign the issue to your grader on GitHub. 3. Go see a course TA if assigning the issue to your grader did not resolve your concern. 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 3 late days of which only one 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. ### Problem 2 (Git, 10%) Carefully review and implement the steps discussed in Lab1. Then answer the following questions: Continue your answers to this question in the file named hw1.txt #### 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 the following command: 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. ### Problem 3 (Review Material and Programming Advice) Carefully review recursion and dynamic memory management from your CSCI 103 notes and textbook. You may also find Chapters 2 and 5 from the textbook, Chapters 2 and 3 from the lecture notes, and the C++ Interlude 2, helpful. You will lose points if you have memory leaks, so be sure to run valgrind once you think your code is working. In order to get valgrind working properly on your VM, please first follow instructions in section "0 - Fixing Valgrind on your VM" in Lab 2 or this Piazza Post. You only need to the setup once. You can run valgrind as follows: $ valgrind --tool=memcheck --leak-check=yes --suppressions=/home/student/gcc.supp ./sum 4098

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. argv[0] is always the name of your program, and argv[1] is the first argument. The operating system will assign the values of argc and argv, and you can just access them inside your program.

### Problem 4 (Recursion, 10%)

Continue your answers to this question in the file name hw1.txt

Consider the following C++ code, and answer the following questions.

1. What gets output when you call funcA(180)? More importantly, why does this get output? All of the points for this problem will be assigned based on your explanation (since we have no doubt that you can run this program for a fixed input and copy down the output). We strongly recommend solving this by hand/calculator, and only using a compiler to verify your answer.
2. Why does the call to funcA(n) always terminate?
3. What gets output when you call funcA(n) and why?
int funcA (int n) {
return funcB(n, 2);
}

int funcB(int n, int i) {
if (n < 2 || i == n) return n;
else if (n % i == 0) return i + funcB(n/i, 2);
else return funcB(n, i+1);
}


### Problem 5 (Recursion and Streams, 10%)

Consider the program sum.cpp, which we have provided for you in the homework_resources/hw1 folder/repo. Copy the file to your hw_usc-username/hw1 folder. The program is intended to receive an int as input, and output the sum of its digits (so 4095 will return 18). However, the program currently always outputs 0. Copy, compile, and run the program with several different inputs to verify this.

Your job is to fix the code so that it gives the correct output for all possible inputs. Only make changes where the code indicates that they should be made: you should not change the main function, nor the start of the helper function.

You may assume that the input integer is non-negative.

### Problem 6 (Streams, 15%)

Write a program that reads in a text file and outputs the characters of that file in reverse order. To achieve this, you will either want to use recursion or dynamic memory allocation (your choice). The program should receive the filename as a command line parameter.

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: hw1q5.txt
44
The quick brown fox jumps over the lazy dog.

• Compiling the program

> g++ -g hw1q5.cpp -o hw1q5

• Running the program and the output
> ./hw1q5 hw1q5.txt
.god yzal eht revo spmuj xof nworb kciuq ehT

• Input text file
27
Able was I, ere I saw Elba.

• The output
.ablE was I ere ,I saw elbA


### Problem 7 (Strings and Dynamic Memory, 45%)

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 history[][], where history[i] stores all of the subjects currently involved in experiment i, and 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.)

• START n: Starts a new set of experiments, with n subjects involved. These n subjects (numbered 0 to n-1) will be added to experiment 0. (We will call this "experiment 0", but it's really just her subject pool; see below.)
• ADD: Adds a new experiment, giving it the next higher number. (So if she has 3 experiments going, they are numbered 1-3 (remember that 0 is the subject pool), so ADD would add experiment 4 next.)
• MOVE x y n m: Moves the subjects numbered n to m (inclusive) from experiment x to experiment y. What this means is that the subjects with these numbers are removed from experiment x, and all higher-numbered subjects have their numbers shifted down, so they now start being numbered at x. (In other words, you always keep subjects' numbering consecutive.) When they are added to experiment y, they are added at the next highest numbers. (So if she adds 5 more subjects to an experiment having 7 subjects already, they are numbered 7 to 11, since the previous 7 were numbered 0 to 6.) It is perfectly fine to move subjects from an experiment to the same experiment. Notice that if you do so, the internal numbering of the subjects in the experiment will likely change. Also, the experiment shold be listed multiple times (as often as the subject was in it).
• QUERY x n: Returns the sequence of experiments that the current n-th subject in experiment x was exposed to, in order. If the subject was part of experiments 0 (subject pool), 1, 6, and is currently number 5 in experiment 2, then QUERY 2 5 would output 1 6 2. (Don't output the subject pool, even if the subject is later returned to it.)

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. Outside of this requirement, 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.)

• If the input file name given at the command line does not exist, your program should output an error.
• If the first line is not a START command, you should output "Error - no subjects yet".
• Whenever you diagnose an error in a line, you should output "Error - incorrect command: #LINE", where #LINE is the incorrect command you found followed by the error-specific information on the next line. Here, the "incorrect command" refers to the entire line. For example, if the line "QUERY 5 2" contains an error, #LINE is QUERY 5 2; if the line is "542 4 2", #LINE is 542 4 2. Your program should then ignore that erroneous line and move on to the next line. Below, we will list which types of errors in lines you need to catch, and which ones we promise will not happen.
• We might give you command names that do not exist (like OUTPUT). Such non-existent commands could have any number of parameters. In that case, output as an error message "Command does not exist".
• Commands might have too few parameters. For instance, we might give you QUERY 3 or MOVE 1 4. In all of these cases, your error message should be "Too few parameters".
• Some parameters which are supposed to be integers might be garbage (strings) or doubles. In that case, output an error message of "Parameter should be an integer". (See below for hints on how to handle this.)
• Some numbers may be out of the reasonable range. For instance, a number may be negative. Or you are asked to move subjects from an experiment that does not exist, or to an experiment that does not exist. Or the range of subjects you are supposed to move (or the subject you are queried about) is outside of the number of subjects for the experiment. For instance, you might be given MOVE 3 5 7 10, but experiment 3 only has 9 subjects (so there are no subjects 9 and 10). In that case, you output "Number out of range", and ignore the command. In particular, in the example, you wouldn't move subjects 7 and 8, either, even though those two do exist.
• For the MOVE command, if the first number n is larger than the second number m, output "Invalid range of subjects to move".
• When a command contains multiple errors (i.e. QUERY -1 5), you stop at the first error. The order that errors should be check is the order they are listed above (Command does not exist -> Too few parameters -> Parameter should be an integer -> Number out of range -> Invalid range of subjects to move).
• Error messages should be printed without the quote around them (i.e. when we say print "Error - no subjects yet", your output file should contain Error - no subjects yet).

Errors you don't need to handle:

• If commands have too many parameters, such as QUERY 3 5 2 or ADD hello-world, then ignore the extra parameters (so interpret these as QUERY 3 5 and ADD).
• We promise that any integer we do give you will always fit into the int data type. (They will not be larger than 2147483648.)
• We also promise you that the number of experimental subjects will be small enough that this number of subjects and all their history will fit comfortably into main memory on any normal computer.
• As mentioned above, moving a subject from an experiment to the same experiment is not an error.

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, there are two natural ways: (1) 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. (2) 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.

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:

Be sure to add, commit, and push your code in your directory to your hw-usc-username repository. Now double-check what you've committed, by following the directions below (failure to do so may result in point deductions):
1. Go to your home directory: $cd ~ 2. Create a verify directory: $ mkdir verify
3. Go into that directory: $cd verify 4. Clone your hw-username repo: $ git clone git@github.com:usc-csci104-fall2017/hw-username.git
5. Go into your folder \$ cd hw-username/