CSCI 104 - Fall 2017 Data Structures and Object Oriented Design

HW1

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.

44
The quick brown fox jumps over the lazy dog.

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

> ./hw1q5 hw1q5.txt
.god yzal eht revo spmuj xof nworb kciuq ehT
27
Able was I, ere I saw Elba.
.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.)

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

Errors you don't need to handle:

Hints on handling parameters of incorrect types:

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 then Re-clone your Repository

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/
  6. Recompile and rerun your programs and tests to ensure that what you submitted works.