CSCI 104 - Fall 2017 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-fall2017/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), (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-fall2017/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 (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* funcA(Node* in) {
    Node *out = in;
    while (out->next != nullptr) {
    out = out->next;
    }
    funcB(in)->next = NULL;
    return out;
}

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

Problem 4 (Linked Lists, Recursion, 20%)

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

The input list will be mostly sorted (sometimes referred to as "circularly sorted"): there is some (unknown) index i which is the smallest element in the list, the elements from indices i to n-1 are sorted (in non-decreasing order), and the elements from 0 to i-1 are also sorted (in non-decreasing order). If i is not 0, then the element in index 0 is at least as large as the element in index n-1.

Some example mostly sorted lists:

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

Some example lists which are not mostly sorted:

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

The original list should 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 (and include it in your solution code):

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

Here is the function you should implement:

Node* fullsort (Node* in);

Empty lists are represented by nullptr pointers.

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

Hint: the easiest way to make this work is to not delete or new nodes, but just to change the pointers.

While we will only test your fullsort function, you will probably want to write some main code to actually test it. Your submission should be in a file called fullsort.cpp, and it should only contain the Node struct and your implementation of the function fullsort, but no main function.

Problem 5 (Recursion, 25%)

Write a function that takes in a string, and outputs all possible permutations of the input, one per line. A permutation is a shuffling of the characters.

If the input is USC, then the output would be (in any order):

USC
UCS
SUC
SCU
CUS
CSU

If the input string is length n, then there should be exactly n! output strings. If the input string has no repeat letters, then there should be no repeat output strings.

If the input is CSC, then there will be repeat output (CCS shows up twice, once when one C is the first character, the other when the other C is the first character):

CSC
CCS
SCC
SCC
CSC
CCS

Here is the function you should implement:

void permutations(std::string in)

While we will only test your permutations function, you will probably want to write some main code to actually test it. Your submission should be in a file called permutations.cpp, and it should only contain your implementation of the function.

You may use loops and/or recursion in your implementation (Hint: you probably want to combine the two). However, you may not use C++ libraries that trivialize the problem. If you do, your score will be 0 on the problem.

Problem 6 (Startup Companies, 35%)

Startups these days are merging so fast, it's hard to keep track of who is in what company. Company A merges with Company B, and Company C merges with Company D, and then the two merged companies merge, and suddenly, employees from companies A and C find themselves being colleagues. This is getting sufficiently difficult to follow that we will have you write a Startup Tracker.

Here is how this will work. You have n students. Initially, each starts a startup company by himself/herself. Then, companies may merge. When you have a merge command, you will be given the numbers of two representative students, one from each company. Then, for each of those two students, you find the "biggest" company they are in, i.e., companies that are not subcompanies of any bigger company; let's call them A and B. Those two companies A and B are then merged into a new company; let's call it C. C will become the parent company of A and B.

Sometimes, companies also split up again. When we call split, we will again give you a representative student. Then, you find the biggest company that the student is in - let's call it A. As a result of the split, A should be completely removed, and the two companies that were at some point in the past merged to become A will now be individual companies without a parent again. (If the student is only in their own 1-person company, split does nothing.)

You will build a data structure that allows you to process a sequence of merges and splits, and answer queries about whether two students are in the same company.

To illustrate this, consider the following example with 5 students. After each command, we are showing you the structure of the nested companies with braces. The notation { {1}, { {2}, {3} } } means that we have a company with two subcompanies: the first subcompany is just student 1, while the second subcompany again has two subcompanies, one consisting of just student 2, the other consisting of just student 3.

merge (0,1)   => { {0}, {1} }, {2}, {3}, {4}
merge (2,3)   => { {0}, {1} }, { {2}, {3} }, {4}
merge (0,3)   => { { {0}, {1} }, { {2}, {3} } }, {4}
split (2)     => { {0}, {1} }, { {2},{3} }, {4}
split (2)     => { {0}, {1} }, {2}, {3}, {4}
merge (2,4)   => { {0}, {1} }, { {2}, {4} }, {3}
split (0)     => {0}, {1}, { {2}, {4} }, {3}

A company is captured by the following

struct Company {
  Company *parent;   // the parent company, or nullptr if it has no parent
  Company *merge1, *merge2;
  /* the subcompanies that were merged to obtain this company, or
     nullptr if this is a 1-student company */

  Company ()
  { parent = NULL; merge1 = NULL; merge2 = NULL; }
  Company (Company *m1, Company *m2)
  { parent = NULL; merge1 = m1; merge2 = m2; }
};

Your task is to implement the following data structure:

class CompanyTracker {
public:
  CompanyTracker (int n);
  // initializes the tracker with n students and their 1-person companies

  ~CompanyTracker (); // deallocates all dynamically allocated memory

  void merge (int i, int j);
  /* Merges the largest companies containing students i and j,
     according to the rules described above.
     That is, it generates a new Company object which will
     become the parent company of the largest companies currently
     containing students i and j.
     If i and j already belong to the same company (or are the same),
     merge doesn't do anything.
     If either i or j are out of range, merge doesn't do anything. */

  void split (int i);
  /* Splits the largest company that student i belongs to,
     according to the rules described above.
     That is, it deletes that Company object, and makes sure that
     the two subcompanies have no parent afterwards.
     If i's largest company is a 1-person company, split doesn't do anything.
     If i is out of range, split doesn't do anything. */

  bool inSameCompany (int i, int j);
  /* Returns whether students i and j are currently in the same company.
     Returns true if i==j.
     Returns false if i or j (or both) is out of range. */

private:
  int numCompanies;  // the number of companies you are tracking

  Company** companies; 
  /* an array (allocated once in the constructor)
     to keep pointers to all the 1-person companies.
     Will not contain the merged companies. */

  /* Feel free to add private helper functions as you see fit.
     In particular, you may want a function to find the largest company
     that a student i is part of. */
};

The signature above is given to you as a file company.h in the homework-resources repo. There, we also give you a bit of skeleton code that you are welcome to use to simplify your life a little bit. You may add private helper functions to CopmanyTracker, but you cannot change the signatures of any of the functions we gave you - otherwise, we cannot test your solution, and that would be bad for your score.

In order to test your CompanyTracker implementation, you will almost certainly want to write another file that includes it, and has a main function. You can then either read from a file, or hard-wire test-cases. Your test cases and main will not be graded, though; you should submit only your company.cpp file and company.h file (even if you didn't change it from our provided file).

Chocolate Problem (1 Chocolate Bar)

We will from time to time assign "Chocolate Problems" on homeworks. These are entirely optional: solving them will not in any way affect your grade in this class. The reward is literally chocolate: if your solution is correct (or close enough), you will get the number of chocolate bars listed with the problem. If you have preferences/allergies, feel free to specify those with your submission. You can solve chocolate problems in teams, and will then share the chocolate as a team. The number of chocolate bars is a rough estimate of how difficult or time-consuming we think the problem is, but keep in mind that even a "1 chocolate bar" problem is more challenging than most standard homework problems. If you solved a chocolate problem, do not submit it via github - instead, just send all necessary files as an attachment to David Kempe. Similarly, if you want to discuss ideas or get hints on chocolate problems, don't ask the course producers and TAs (they have enough to do helping your classmates with regular homework); instead, ask David directly in person or on Piazza. Homework deadlines do not explicitly apply to chocolate problems, but please do not submit more than a few days after the actual HW deadline.

Use recursion to write a program playing perfect Tic Tac Toe. Feel free to design any reasonable user interface (input and output). Your program should never lose, and win whenever given a chance.

(Note: Contrary to the famous silly clip from the movie War Games, even if you let your program play itself, it will not learn that sometimes in life, one has to lose.)

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