CSCI 104 - Spring 2018 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 01.

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-spring2018/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 here and here

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 assignment you should:

  1. Email your professor immediately.
  2. Assign the issue to your grader on GitHub.
  3. Go see a regrade 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):

What should you do to ensure you are submitting your code correctly?

  1. Nothing: submit your code, then sit back and enjoy.
  2. Clone your github directory, checkout the SHA you plan to submit, and rerun your tests.
  3. Use the long SHA in your submission (20+ digits/letters).
  4. Check the output from the submission system when you submit your code: this may alert you to missing files or compilation errors.
  5. Resubmit your code if you find additional problems before the deadline.

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.

$ valgrind --tool=memcheck --leak-check=yes ./program input.txt output.txt

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([1,2,3,4,5], 5)? 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. For what input values would funcB fail to terminate? Why will funcB always terminate for other input values?
  3. What gets output when you call funcB(a, min, max) and why?
void funcA (int *a, int size) {
    funcB(a, 0, size-1);
}

void funcB(int *a, int min, int max) {
    if (min == max)
        cout << a[min] << endl;
    else {
        int mid = (min+max)/2;
        funcB(a, min, mid);
        funcB(a, mid+1, max);
    }
}

Problem 5 (Recursion, 10%)

Barry Bruin is learning about recursion, and attempted to write a program that recursively determines whether a provided integer's digits are in non-decreasing order (that is, they are in increasing order, but not necessarily strictly increasing order). We have provided this file to you in the homework-resources/hw1 folder/repo, as barry.cpp. Copy the file to your hw-usc_username/hw1 folder. The program currently always outputs Not increasing order. 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.

Input:

11344

Intended output:

Increasing order.

Input:

312

Intended output:

Not increasing order.

Problem 6 (Streams, 10%)

Write a program that reads in a text file consisting of several strings, and outputs the strings of that file in reverse order. Your program must use recursion, and cannot use dynamic memory allocation. Your submitted program should be named hw1q6.cpp, and it 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 strings in the file; let's call it n. This will be followed by n strings, possibly spread over multiple lines. You do not need to handle any error-checking here: we promise the input file will be in the correct format.

The following is a sample input and output of the program.

5
Yoda does this, like speak

> g++ -g -Wall hw1q6.cpp -o hw1q6

> ./hw1q6 hw1q6.txt
speak like this, does Yoda
9
The quick brown 
fox jumps over 
the lazy dog.
dog. lazy the over jumps fox brown quick The

Problem 7 (Game Of Pointers 50%)

Ladies and Gentlemen, are you ready for battle? Seg faults are coming! In this part of the assignment, you will battle with your understanding of memory and pointers all under the guise of battling warriors.

Your warriors are structs with a weapon and power level:

struct Warrior {
    std::string weapon;
    int power;
};

There are only two types of weapons, “sword” and “axe”. An axe is more powerful than a sword in this game (although that may be debatable). The power is the strength of the warrior and you may assume this is a non-negative integer.

You will receive two command line parameters: an input file to read from, and an output file to write to.

The input file will consist of at least 4 lines, where each line has exactly one non-negative integer. The first integer indicates n, the number of rows of protectors and also the number of columns of invaders. The second integer indicates m, the number of columns of protectors and also the number of rows of invaders. The third integer indicates how many protectors there are in reserve. The fourth integer indicates x, the number of skirmishes. There will be exactly x more lines (after the first 4) in the input file, indicating who fights in each duel (more details below).

Example input file (the actual input file won't contain comments):

34 /* number of rows of protectors, and columns of invaders*/
56 /* number of columns of protectors, and rows of invaders*/
5 /* number of reserve forces for protectors*/
2 /* number of skirmishes */
0 /* row of invaders and column of protectors that fights in skirmish 1*/
49 /* row of invaders and column of protectors that fights in skirmish 2*/

In the file game_of_pointers.cpp, you will have one epic battle that must do the following:

  1. First you must create the Stark warriors who will be protecting their home. This will be an n by m array of Warriors called protectors. If a warrior is in an even battalion row (0-based), then they have an axe. Otherwise they have a sword. The power of each warrior of the protectors is i*10+(j+1)*10, where i is the row index and j is the column index.
  2. Create the invading Lannister warriors. This will be an m by n array, called invaders. If the warrior is in an odd-index battalion row, they have an axe. Otherwise they have a sword. The power of each invader is i*10+(j+1)*10, where i is the row index and j is the column index.

Here are the rules for a single skirmish:

  1. Row i of the invaders duels column i (again, 0-based) of the protectors, where i is indicated from the input file.
  2. If i is out of bounds (there is no row i of invaders nor column i of protectors), then nothing happens, and you move on to the next skirmish.
  3. Warriors duel each other in order, meaning that the first invader (the one in column 0) in row i duels the first protector (the one in row 0) in column i, and then the second invader (the one in column 1) in row i duels the second protector (the one in row 1) in column i, and so forth.
  4. In any given duel, if exactly one of the two warriors has an axe, that warrior wins. Otherwise, whichever warrior has the greater power wins. If they have the same power, there is a draw (so nothing happens), in which case you should output Duel ends in draw and a newline character to the output file.
  5. In any given duel, if there is no invader at that location, then nothing happens. Output No assault and a newline character to the output file.
  6. In any given duel, if there is an invader, but no protector at that location, then the walls are breached, and the invading army is immediately declared the winner (do not conduct any more duels or skirmishes).

If an invader loses their duel, they are killed. Output Invader killed and a newline character to the output file. The position is left empty.

If a protector loses their duel, then:

After all of the skirmishes, if the invaders have not breached the walls, then the protectors are declared the winner.

Important Notes:

Here are some sample input and output that you can use to check your understanding of the game. You can also find these in homework-resources under hw1/p7_tests. You are encouraged to write more test input yourself.

Sample Input 1:

2
3
1
2
0
1

Expected Output 1:

Invader killed
Duel ends in draw
Duel ends in draw
Protector defected
Winner: protectors

Sample Input 2:

2
5
1
3
1
3
3

Expected Output 2:

Duel ends in draw
Protector killed
Duel ends in draw
Protector killed
Duel ends in draw
Winner: invaders

Sample Input 3:

2
3
1
2
1
1

Expected Output 3:

Duel ends in draw
Protector killed
Duel ends in draw
Invader killed
Winner: protectors

Commit then Re-clone your Repository

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