Homework 1

• Due: See assignments page
• Directory name in your github repository for this homework (case sensitive): hw1
  • Once you have cloned your 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

Written Portion

A Few Notes on Repositories

1. Never clone one repo into another. If you have a folder cs104 on your laptop (wherever you created your Github keys from Lab 0) and you clone your personal repo hw-username under it (i.e. cs104/hw-username) then whenever you want to clone some other repo, you need to do it back up in the cs104 folder or other location, NOT in the hw-username folder.
2. Your repo is created when you register with our website (aka curricula system) as outlined in the Lab 0 writeup on the Labs Page. If you’ve followed those steps, accepted the invite to the Github organization that should be generated and emailed to you after you register with our website, and still cannot access your repository, you can then make a private post on the class Q&A to let your instructors know that your repository needs to be created. Be sure to include your USC username and github username for reference.

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, resources, under our class GitHub site. You should clone this repository to your laptop (but only if you have not already done this as part of lab) and do a git pull regularly to check for updates.

$ git clone git@github.com:/resources

Again, be sure you don’t clone this repo into your hw-username repo but at some higher up point like in a cs104 folder on your laptop. You can then manually copy (in your OS’s GUI or at the command line) the skeleton files from resources/hw1 to hw-username/hw1.

For example if you are in the folder containing both the resources and hw-username folders/repos, you could enter the following command at the terminal:

$ cp -rf resources/hw1 hw-username/

Again be sure to replace hw-username with your USC username (e.g. hw-ttrojan)

Problem 1 - Course Policies (6%)

Carefully study the information on the course web site, then answer the following questions about course policies:

Place your answers to this question in a file name hw1.txt in your hw-username/hw1 folder.

Part (a):

Which of the following are acceptable behaviors in solving homeworks/projects (list all that apply)?

1. Looking up relevant C++ reference information online.
2. Looking up or asking for sample solutions online from sites like Chegg, Github, etc.
3. Talking to my classmates about general approaches about the problems (but no specific coding statements or description of your own code or someone else’s code).
4. Copying code from my classmates or an online source, and then editing it significantly.
5. Asking the course staff for help.
6. Sitting next to my classmate and coding together as a team or with significant conversation about approach.
7. Sharing my code with a classmate, even if he/she just wants to read over it and learn from it

Part (b):

To dispute a grade on a HW assignment you should (list all that apply):

1. Email the professor immediately.
2. Complete the regrade request form within 1 week of receiving the grade and wait for an issue to be posted to your Github repo.
3. Visit the designated regrade TA within 1 week of your score posting.

Part(c):

What is the late submission policy (list all that apply)?

1. One hour late submission is acceptable for each assignment.
2. Each assignment can be submitted up to two days late for 50% credit.
3. Each student has 5 late days of which only 2 can be used per HW
4. Students need to get an approval before submitting an assignment late.

Part(d):

After pushing your code to Gihub you should… (list all that apply)

1. Do nothing. Once you push your code you are done.
2. Clone your repo to a temporary folder to ensure all the files you desire are pushed and that your code compiles.
3. Complete the online submission page using your FULL (30 or more digit) SHA.

Part (e):

If you have NO grace days left and it is after the submission deadline, we will accept your assignment under what circumstances (list all that apply).

1. None. We will not accept your submission.
2. There is an hour grace period after the deadline.
3. If there is a technical difficulty (such as wireless trouble, or github commit/push issues, etc.) with submission.
4. If you email us your code as attachments.

Part (f):

General submission policies (indicate True/False).

1. True/False: Before submitting your HW you should reclone your repo to a separate folder and ensure all files are present and your code compiles.
2. True/False: If you forget to submit a file via GITHUB you can still apply for a regrade after the deadline and submit the missing file.
3. True/False: You only have 7 days to submit a regrade for homeworks, unless otherwise stated, and after that you are not eligible for a regrade for ANY reason.

Problem 2 - Git (6%)

Carefully review and implement the steps discussed in Lab1. Then, answer the following questions:

Continue your answers to this question in the file name hw1.txt in your hw-username/hw1 folder.

Part (a):

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 (b):

Provide the appropriate git command to perform the following operations:

1. Stage an untracked file to be committed. The file is called ‘hw1q2b.cpp’.
2. Display the details of the last three commits in the repository.

Part (c)

What is the full command to re-clone your private CSCI104 repo to your VM? Assume you are in an appropriate folder.

Problem 3 - Runtime Analysis (24%)

In Big-Θ notation, analyze the running time of the following three pieces of code/pseudo-code. Describe it as a function of the input (here, n). Submit your answers as a PDF (using some kind of illustration software or scanned handwritten notes where you use your phone to convert to PDF) showing your work and derivations supporting your final answer. You must name the file q3_answers.pdf. As usual, answers without supporting work will receive 0 credit.

Part (a)

void f1(int n)
{
    int i=2;
    while(i < n){
        /* do something that takes O(1) time */
        i = i*i;
    }
}

Part (b)

void f2(int n)
{
    for(int i=1; i <= n; i++){
        if( (i % (int)sqrt(n)) == 0){
            for(int k=0; k < pow(i,3); k++) {
              /* do something that takes O(1) time */
            }
        }
    }
}

Part (c)

for(int i=1; i <= n; i++){
  for(int k=1; k <= n; k++){
    if( A[k] == i){
      for(int m=1; m <= n; m=m+m){
        // do something that takes O(1) time
        // Assume the contents of the A[] array are not changed
      }
    }
  }
}

Part (d)

Notice that this code is very similar to what will happen if you keep inserting into an ArrayList (e.g. vector). Notice that this is NOT an example of amortized analysis because you are only analyzing 1 call to the function f(). If you have discussed amortized analysis, realize that does NOT apply here since amortized analysis applies to multiple calls to a function. But you may use similar ideas/approaches as amortized analysis to analyze this runtime. If you have NOT discussed amortized analysis, simply ignore it’s mention.

int f (int n)
{
  int *a = new int [10];
  int size = 10;
  for (int i = 0; i < n; i ++) 
     {
        if (i == size)
          {  
             int newsize = 3*size/2;
             int *b = new int [newsize];
             for (int j = 0; j < size; j ++) b[j] = a[j];
             delete [] a;
             a = b;
             size = newsize;
          }
        a[i] = i*i;
     }
}

Problem 4 - Linked List Recursion Tracing (14%)

Consider the following C++ code.

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.

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

Node* llrec(Node* in1, Node* in2)
{
    if(in1 == nullptr) {
        return in2;
    }
    else if(in2 == nullptr) {
        return in1;
    }
    else {
        in1->next = llrec(in2, in1->next);
        return in1;
    }
}

Question a: What linked list is returned if llrec is called with the input linked lists in1 = 1,2,3,4 and in2 = 5,6?

Question b: What linked list is return if llrec is called with the input linked lists in1 = nullptr and in2 = 2?

To show work, you can draw a call tree or box diagram of the function calls using some simplified substitution of your choice rather than pointer values (e.g. “p3” for a pointer to a node with value 3). Submit your answers as a PDF (using some kind of illustration software or scanned handwritten notes where you use your phone to convert to PDF) showing your work and derivations supporting your final answer. You must name the file q4_answers.pdf.

Problem 5 - NOT GRADED (PRACTICE ONLY) - Constructors and Destructors (0%)

Place your answers to the questions below in the same file as your answers to problem 1 and 2 (i.e. hw1.txt). You do not need to test and compile the code below. You are just writing out your answers in the hw1.txt file.

Suppose you were given the following class to model an entry in your contacts list which uses a custom Str class that models a string and replaces std::string.

#ifndef ENTRY_H
#define ENTRY_H
#include "str.h"

class Entry {
 public:
  Entry(const Str& name, const Str& phone);
  ~Entry();
  const Str& name() const;
  const Str& phone() const;

 private:
  Str name_;
  Str phone_;
};
#endif

Further assume that print statements are added to all constructor and destructors that print:

• Str in the default and initializing constructor(s)
• ~Str in the destructor
• Copy Str in the copy constructor
• Nothing is printed in the assignment operator(s)

Question a: If the Entry constructor is as shown below, what will be printed when a new Entery object is constructed.

Entry::Entry(const Str& name, const Str& phone)
{
  cout << "Entry" << endl;
  name_ = name; 
  phone_ = phone;
}

Question b: If the Entry constructor is as shown below, what will be printed when a new Entry object is constructed.

Entry::Entry(const Str& name, const Str& phone)
  : name_(name), phone_(phone)
{
  cout << "Entry" << endl;
}

Now suppose a new Wrapper class is written that uses an Entry as a data member as shown below.

#ifndef WRAPPER_H
#define WRAPPER_H
#include "entry.h"
class Wrapper
{
 public:
  Wrapper(const Str& name, const Str& phone);
  void print() const;
 private:
  Entry e_;
};
#endif

Question c: Show how to complete the constructor such that the data member e_ is initalized with the arguments name and phone. Be sure to avoid any compile errors or runtime errors. You can always try your code out using a compiler. Show the entire constructor in your answer (i.e. start by copying the code below and then add to it).

// initialize e_ with name and phone
Wrapper::Wrapper(const Str& name, const Str& phone)
{

}

Programming Portion

Problem 6 - Sparse Matrix (Classes, Pointers, LinkedLists) (50%)

Be sure you copy over all the skeleton files in resources/hw1 that start with spmat to your hw-username/hw1 folder as well as the Makefile.

In this problem you will apply and deepen your linked list programming skills by creating a sparse matrix (ie. 2D array) of doubles.

Background

A sparse matrix is one where the majority of entries are 0. Due to this characteristic, we can save memory (and potentially time) by only storing non-zero entries. One approach to doing this is to use linked lists to only store the non-zero cells. Since we do not have an entry at every row/column index, each cell must store the row/column coordinates to which it corresponds along with its data value and necessary linked list pointers. So that we can scan quickly down either a row or a column we will choose to make each cell a member of two linked lists: a row linked list and a column linked list. Each list is a doubly-linked list to support faster insertions and removals. (You may wish to spend a moment considering why a singly-linked list would make insertion/removal less efficient). Thus the overall sparse matrix would resemble the diagram below for a 4x4 matrix. Notice, there is an array of head pointers for the row lists on the far left and another array of head pointers for the column lists on the top.

Provided Implementation

Much of the skeleton has been provided to you and you will need to provide the implementation of several of the key member functions. Please review it as you read this description.

We first use a simple Coord struct with a row and col member to track where entries belong in the 2D matrix. Next, we create a SparseItem struct to hold each non-zero cell’s data and, finally, a SparseMatrix class to model the entire matrix. The matrix can be of size n x n where n is provided when the SparseMatrix is constructed. Since, we have both row and column lists, we need to store the head pointers for the n rows and the n columns (for a total of 2*n head pointers) by using an array for each set of head pointers.

The header file is provided and is complete. You should not alter the public interface but may add private helper functions if you desire and potentially other data members (though this is not recommended and should likely be discussed with a course staff to see if there is a good alternative).

A few nested types have been defined to help with the implementation of the SparseMatrix:

• Coord and SparseItem are declared as nested types inside SparseMatrix meaning non-member code will need to scope the type (e.g. SparseMatrix::Coord).
• Dim is an enumerated type which simply assigns integer values to symbolic names (as if you had written const int ROW = 0 and const int COL = 1, etc.) The row list of head pointers, row coordinate, and next/prev pointers for the row list are all at index 0 and thus we can use ROW rather than writing 0. Similarly, the column list of head pointers, column coordinate, and next/prev pointers for the column list are all at index 1 and thus we can use COL rather thant writing 1. Helpful Hint: Given a dimension index, dim (0=ROW, 1=COL), you can convert to the other dimension index with the expression 1-dim.

Provided Functions

We have provided the following completed functions which you should NOT alter.

• SparseMatrix::Coord::Coord(size_t row, size_t col) constructs Coord objects

• SparseMatrix::SparseItem::SparseItem(Coord coord, double v) constructs SparseItem objects

• double SparseMatrix::get(const Coord& coord) const will return the value at the given Coordinate.

• void SparseMatrix::print(std::ostream& ostr) const will output the matrix in a 2-dimensional format to the provided ostream

• SparseMatrix::SparseItem* SparseMatrix::lowerBound(size_t list, Coord target_coord ) const can be used to find the SparseItem with the given “target” coordinates by iterating through either the ROW(0) or COL(1) list. If no SparseItem with the given coordinates exists in the specified list, either the Item that would come before the given coordinates will be returned, or nullptr if the list is empty or the target coordinate would come before the first item in the list.

Additional Learning: Exceptions

Errors happen in programming. We receive unexpected or illegal inputs or arguments or we reach a state that we cannot handle. In those cases we can take some action like returning a specific value, but in some cases, based on the function signature, that may be impossible. An alternate approach is exceptions.

You should learn about exceptions by watching the provided lecture video and reading online or in the textbook.

• In this homework, you do not need to catch any exceptions.
• However, we will ask you to throw certain exceptions in the following problem. You can just use an appropriate throw statement. Look in the skeleton code documentation for where/when to throw an exception.

Your Task

Study the class definition in the header file and the functions already implemented in the .cpp file. Use that code to understand how to interact with the head pointer lists, SparseItems, etc. and then implement the remaining functions (listed below). Note: You MUST adhere to the requirements of each function provided in the header file documentation. Failure to do so may result in no credit.

To be Implemented

For the SparseMatrix class, you will need to complete the following operations:

• size_t& SparseMatrix::Coord::operator[](size_t index) (both const and non-const versions) which are easy accessors for the Coord struct to retrieve either the r member if index is 0 (or ROW) or the c member if index is 1 (or COL).
• bool SparseMatrix::Coord::operator==(const Coord& rhs) const to compare Coord objects if necessary
• SparseMatrix(size_t n) constructor should allocate memory for the arrays of head pointers and intiailze them as well as other data members
• ~SparseMatrix() destructor should deallocate all memory correctly without leaks
• set(coord, val) should set the cell with given coord coordinates to the value, val. If the cell at the given coordinates does not exist (i.e. it is currently 0), create and insert the new cell provided the value is not zero. If the cell at the given coordinates does exist, update its value unless the value is 0 in which case the cell should be removed from the lists. Attempting to set a non-existent cell (i.e. that is already implicitly 0) with an explicit value of 0 should simply have no effect. Read and comply with the corresponding header file description of exception cases to handle. Ensure no memory is leaked. This will likely be one of the more difficult functions to implement. Consider how lower_bound() can be used to help find the location to insert a new cell, if necessary. Also, note that you should call createSparseItem to dynamically allocate a SparseItem rather than using new yourself. This aides the DebugHelper described later on to verify your implementation.
• double sumDim(const Coord& coord) const returns the sum of the values in the specified dimension. Exactly one of the row or column coordinates must be SparseMatrix::npos. For example, a Coord of {SparseMatrix::npos, 2} specifies all entries in column 2 should be summed.
• void copyDim(size_t srcCoord[], size_t destCoord[]) copies one row or column to another (may be a transpose…row to column or vice versa). Each argument should have exactly one of the row or column coordinates be SparseMatrix::npos. For example, copyDim({5,SparseMatrix::npos}, {SparseMatrix::npos,3}) would copy row 5 to column 3.

Private Helper function

• void deleteNode(SparseItem* node) should delete the specified node from both the row and column lists of which it is a member. You must leave the provided code at the end of this function that updates the DebugHelper and performs the actual memory free by calling delete.

• SparseMatrix::npos is a static constant member (meaning all instances of SparseMatrix share that one definition of npos. You must initialize it at the top of spmat.cpp. It should be initialized to the largest possible unsigned value which can easily be done by setting it to (size_t)-1; since -1 is all 1s in binary and will be the largest unsigned value when cast to an unsigned type. You should use npos as the value for the unused dimension in calls to sumDim and copyDim. This value is patterned from the constant defined in std::string (really std::basic_string) with the same name. Info about its use is here

Example

Suppose we create the following 4x4 SparseMatrix (n=4):

If we then perform a set operation on coordinate {0,0} with value 1.8, a new SparseItem should be created in that location and added to the appropriate linked lists, resulting in the following.

If we then perform a set operation on coordinate {1,2} to value 0, the SparseItem that in that location should be deleted (since we do not store values of 0). The resulting matrix is shown below.

Finally, if we perform a copyDim operation from row 3 to column 2 (i.e. SparseMatrix::copyDim({3,SparseMatrix::npos}, {SparseMatrix::npos,2}) ) then the old contents of column 2 should be removed (taking care not to delete an item that is also in the source dimension), and the elements from source row 3 should be copied into column 2. Note: the source dimension may be modifed by this operation when copying from one row/column to the opposite (as seen here).

Notes and Other Info

• We have provided a debug helper class SparseMatrixDebugHelper to help check the consistency of your linked lists. You can examine its code in spmat-debug.h/cpp. For it to work you must use SparseMatrix::createSparseItem() anytime you allocate a SparseItem and you must use SparseMatrix::deleteNode() anytime you delete a SparseItem. These functions have hooks to call the debug helper to track the pointers to currently “scoped” SparseItems. We have included calls to the consistency checker at the end of SparseMatrix::set() and SparseMatrix::copyDim() which are the most likely places you will introduce errors. It uses conditional compilation (e.g. #ifdef tags) and currently the Makefile is setup to define SPARSE_DEBUG so that the consistency checks are enabled.

• No use of any other container is allowed (i.e. no vector or any other C++ data structure other than arrays and the linked lists of SparseItems can be used). Failure to follow this guideline will result in a 0!

Testing

• We have provided a simple test driver in spmat-test.cpp that will create a few different matrices and exercise some of the member functions. It does not perform automated testing so you will need to read the code and examine the output to verify that your code is producing correct, expected output.

Many students try to rush this step. It is far easier to find bugs in your code for small test cases that you create (and understand) than with the larger test suites that we often provide. We strongly encourage you to read the test program spmat-test.cpp and sketch on paper what the matrix would look like and then run the code (adding additional print statements) to verify the operation of your implementation. If your code crashes or generates valgrind, that’s probably a GOOD thing initially because the small cases tested here will make solving your bugs easier. We ALWAYS encourage you to think of some simple, basic tests you can write for any data structure or problem you code in this class. And in doing so, think through what the expected output should be. Then if your code does not produce that, think about why (use gdb or add print statements). This is especially true when we release test suites. You MUST read over the test code and get an idea in your head of WHAT it is trying to do and WHAT the expected outputs are. Then when your code doesn’t produce the expected outputs, you’ll have an idea of where to start. PLEASE, taking testing seriously. The better you develop your debugging skills, the easier the following assignments will be.

• We have, however, provided a helper, debug class: SparseMatrixDebugHelper. It performs consistency checks regarding your linked list pointers and will output error message. For it to work, you must use createSparseItem and deleteNode to dynamically allocate and delete SparseItems. These functions have calls to the DebugHelper to track which nodes exist currently. Hooks to call the consistencyChecker are already inserted in set and copyDim. To enable those calles, you should compile by using:

 make debug

And then run ./spmat-test

To compile without the debug code enabled, you can just run:

 make

Remember, it is ALWAYS a good idea to run your tests through valgrind. You can do so by executing the following command line.

 valgrind --tool=memcheck --leak-check=yes ./spmat-test

Scroll through the output and look for invalid reads, writes, and the heap usage summary at the end. However, please note, that just as a doctor can only diagnose you based on the symptoms or the info you provide, valgrind can only check for errors based on what the test code exercises. If the test code never triggers code to test a function and there are memory leaks or invalid access in that function, valgrind will say no errors occurred. You are only as good as what your tests exercise, so it helps to write tests that will trigger each line of code in your class (this is often referred to as code coverage).

Submission Files

Ensure you add/commit/push all your source code files, Makefile, and written problem files. Do NOT commit/push any test suite folder/files that we provide from any folder other than the resources/hw1 repo.

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 hw1 directory to your hw-username repository. Now double-check what you’ve committed, by following the directions below (failure to do so may result in point deductions):

1. In your terminal, cd to the folder that has your resources and hw-username
2. Create a verify-hw1 directory: $ mkdir verify-hw1
3. Go into that directory: $ cd verify-hw1
4. Clone your hw_username repo: $ git clone git@github.com:/hw-username.git
5. Go into your hw1 folder $ cd hw-username/hw1
6. Switch over to a docker shell, navigate to the same verify-hw1/hw-username/hw1 folder.
7. Recompile and rerun your programs and tests to ensure that what you submitted works. You may need to copy over a test-suite folder from the resources repo, if one was provided.