CSCI 104 - Spring 2018 Data Structures and Object Oriented Design

HW2

Problem 1 (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-spring2018/SampleRepo, and contains README.md. (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), (b), ..., (e). You must use the terminalogy 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.

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

Problem 2 (Review Material, 0%)

Carefully review linked lists (Chapters 4, 9.2) and Recursion (Chapters 2, 5).

Problem 3 (Abstract Data Types, 20%)

For each of the following data storage needs, describe which abstract data types you would suggest using. Natural choices would include list, set, and map.

Try to be specific, e.g., rather than just saying "a list", say "a list of integers" or "a list of structs consisting of a name (string) and a GPA (double)". Also, state any assumptions you have made, and give a brief explanation for your answers: we are grading you at least as much on your justification as on the correctness of the answer. Also, if you give a wrong answer, when you include an explanation, we'll know whether it was a minor error or a major one, and can give you appropriate partial credit. Also, there may be multiple equally good options, so your justification may get you full credit.

  1. a data type that stores all of the items at a restaurant, ordered by their number on the menu (an integer from 1 to 100).
  2. a data type that stores all of the movies in the Star Wars universe.
  3. a data type that stores all of the books on Amazon: given an ISBN (a 13-digit number), it produces the book with that number.
  4. a data type that stores all movies: given a year, it produces all movies released in that year.
  5. a data type that stores all of the episodes of Game of Thrones: given a season and episode number, it produces the requested episode.

Problem 4 (Linked Lists, Recursion, 10%)

Consider the following C++ code. What linked list is returned if funcA is called with the input linked list 1,2,3,4,5? All of the points for this problem will be assigned based on your explanation, since we have full faith in your ability to run this program and copy down the answer. We strongly recommend solving this by hand, and only using a compiler to verify your answer.

struct Node {
    int value;
    Node *next;
};

Node* funcB(Node* in) {
    if (!in) return nullptr;
    Node *p = funcB(in->next);
    if (p) {
        p->next = in;
    }
    return in;
}

Node* funcA(Node* in) {
    if (!in) return nullptr;
    Node *r = in;
    while (r->next) r = r->next;
    Node *l = funcB(in);
    l->next = nullptr;
    return r;
}

Problem 5 (Linked Lists, Recursion, 15%)

Write a recursive function to sort the elements of a singly-linked list in non-decreasing order.

The input list will be mostly sorted. A list is mostly sorted if there is some (unknown) index i which, if removed from the list, results in the remainder of the list being sorted.

Some example mostly sorted lists:

  1. [1,2,5,3,4]
  2. [2,3,1,4,5]
  3. [1,2,3,4,5]
  4. [3,1,1,1,1]

Some example lists which are not mostly sorted:

  1. [2,2,1,1]
  2. [1,4,5,2,3]
  3. [1,2,1,2,1]

The original list need not be preserved (see below). Your function must be recursive - you will get NO credit for an iterative solution. If you use helper functions - which you may - then they all must be recursive: using loops anywhere in your functions will result in no credit.

You should use the following Node type:

struct Node {
    int value;
    Node *next;
};

Here is the function you should implement:

Node* fullsort (Node* in);

Empty lists are represented by NULL pointers.

When your function terminates, in need no longer represent the head of the list (the original lists are not preserved), and the return value should point to the head of a sorted linked list. Obviously, your solution must not leak memory.

While we will only test your fullsort function, you will probably want to write some main code to actually test it: just make sure to remove this before submission. Your submission should be in a file called fullsort.cpp, and contain only your Node struct, and the fullsort definitions (and any required helper functions).

You may not use any data types or algorithms from the STL in your solution.

Problem 6 (Linked Lists, 35%)

We have provided you the header file for a circular doubly-linked list in the homework-resources/hw2 folder. You can update/pull the homework-resources folder to obtain it and then copy it to your own hw2 directory in your own hw_usc-username repo.

  1. You need to implement the functions in lliststr.cpp. Valid locations for insertion are 0 to SIZE (where SIZE is the size of the list and indicates a value should be added to the back of the list). Valid locations for remove, set, and get are 0 to SIZE-1. Any invalid location should cause the function to simply return without modifying the list.

  2. After completing the functions above, you should write a separate program to test your implementation. Please note that these tests will be graded (and hence you should not copy or share them with your classmates). You should allocate one of your LListStr items and make calls that will exercise the various cases you've coded in your functions. For example, if you have a case in insert() to handle when the list is empty and a separate case for when it has one or more items, then you should make a call to insert() when the list is empty and when it has one or more items. It is important that when you write code, you test it thoroughly, ensuring each line of code is triggered at some point. You need to think about how you can test whether it worked or failed as well. In this case, calls to get(), size(), and others can help give you visibility as to whether your code worked or failed.

We have provided a sample test program for you in the homework-resources folder, testAddToEmptyList.cpp. Use it as a template and good example for how to write tests for individual features of your class. Your submission should contain lliststr.h, lliststr.cpp, and lliststr_test.cpp.

Problem 7 (Linked Lists, 10%)

Use your Linked List from problem 6 to implement the structure for a game of Assassin.

In the game of Assassin, there are n players arranged in a circular linked list. Each player needs to "assassinate" (with a nerf gun or similar) the next player in the list. If player A assassinates player B, then B is removed from the game, and A must now assassinate B's target. The game ends when a player's target becomes him/herself, which means all other players have been eliminated.

Write your program in assassin.cpp. Your program should read a single string from the command line, which is the input file. The input file will contain one command per line. Execute each command in order. Once the file has been read, if a single player is left in the game, output Winner: [player-name] to the terminal, and then terminate. Otherwise, output Remaining Players: [X] to terminal (on a line by itself), then output the remaining players to terminal (one per line), and then terminate. The players should be output in the order they appear in the underlying linked list.

Each command will be one of the following:

  1. ADD pos str Add a player with name str at index pos in the linked list.
  2. REPLACE pos str Remove the player at index pos, and replace them with a player named str.
  3. ACT pos The player at index pos assassinates their target: remove the next player from the game, and output Assassinated: [player-name] to the terminal. If there is only one player, then do not modify the game state (and do not output to terminal).

If you identify any errors (an invalid command, an invalid pos value, etc), then proceed to the next command without modifying the game state (you should not output anything).

Example input:

ADD 0 Sandra
ADD 0 Aaron
ACT 1

Output:

Assassinated: Aaron
Winner: Sandra

Input:

ADD 0 Aaron
ADD 1 Sandra
ACT 2

Output:

Remaining Players: 2
Aaron
Sandra

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