lab08 : Recursion

num ready? description assigned due
lab08 true Recursion Mon 03/02 09:00AM Thu 03/12 11:59PM

Goals of this lab

The goal of this lab is get more practice with recursion, linked-lists, and string functions. Continue to practice code tracing to reason about your code. We request that you DO NOT ask the staff to debug your code. They have been specifically instructed not to debug for you, rather to guide in the process.

You are also required to apply the style guidelines as described in this presentation: link to style guide

If you are using a style different from what is recommended and feel strongly about continuing in that style, you may include a note as a comment in the README of your project explaining the rationale behind your choices. Cite any sources as relevant.

If you are using any instructor written code or hints from a previous offering of this course, cite your source. Remember that code that is not written by you is in violation of the academic honesty for this class.

Extra credit survey (1%)

Please fill out this survey by the lab due date to receive 1% EC to your overall grade in the course: https://ucsb.co1.qualtrics.com/jfe/form/SV_0qVnEcqYnx9AJkV

Step by Step Instructions: PLEASE READ CAREFULLY!

Step 1: Getting Started

  1. Decide if you are working alone, or working in a pair. Pair programming is OPTIONAL for this lab.

  2. Choose who will be the first driver and who will start as navigator, and then remember to switch (at least once) during the lab.

  3. Go to github and create a git repo for this lab following the naming convention specified in previous labs (this step carries style points, see our feedback on previous labs to understand what we are looking for). If you are working with a partner only one of you needs to create the repo.

  4. If you are working with a partner and you are the one who created the github repo, add your partner as a collborator on the repo

  5. Decide on initial navigator and driver.

  6. Driver, log on to your CSIL account.

  7. Open a terminal window and log into the correct machine.

  8. Change into your CS 16 directory

Note: Remember to push your work to github at the end of EVERY work session. That way, both partners always have access to the latest version of the code even if the code is being developed on one partner’s CoE account.

Step 2: Obtaining the starter code

cp /cs/faculty/dimirza/cs16/labs/lab08/* ./

Typing the list (ls) command should show you the following files in your current directory

[dimirza@csil-03 lab08-startercode]$ ls
Makefile   linkedListFuncs.cpp  linkedListTest.cpp        spliceTest.cpp  strFuncs.h   sumTest.cpp   tddFuncs.h
README.md  linkedListFuncs.h    removeKFromFrontTest.cpp  strFuncs.cpp    strTest.cpp  tddFuncs.cpp
[dimirza@csil-03 lab08-startercode]$

Step 3: Reviewing the files and what your tasks are

Here is a list of your tasks for this lab:

Step 3a: Familiarize yourself with the big picture

Type “make tests” and you will see some tests pass, but some fail. Note: if you get a warning about comparing signed and unsigned integers, please ignore it.

You are finished when all the tests pass. You will need to edit two files: linkedListFuncs.cpp and strFuncs.cpp

Please note that this lab may be more difficult than the previous labs you have worked on. Don’t be afraid to ask questions on Piazza and attend open lab hours.

Step 3b: Work on the linked list and string functions

Please note that all of these functions must be written recursively. You will not get credit if you implement them iteratively. There are 4 functions you will need to write for this lab, one of which is a bonus:

In strFuncs.cpp:

In linkedListFuncs.cpp:

Each one has a set of tests which can be found under its corresponding heading when you type make tests. For example, the addIntToEndOfList tests look like this to start:

./llTests 1
--------------REMOVE_K_NODES_FROM_THE_FRONT_OF_THE_LIST--------------
   FAILED: Remove 3 from front of 1->2->3->4->5
     Expected: 4 5  Actual:

You should replace each function stub with the correct code for the function until all of the tests for each one pass. It is recommended that you work on the functions one at a time in the order that they are presented above. That is, get all the tests to pass for addIntToStartOfList then addIntToEndOfList and so on. When all the tests pass, move on to the next step.

Step 4: Checking your work before submitting

When you are finished, you should be able to type make clean and then make tests and see all of the tests pass.

At that point, you are ready to try submitting on gradescope.

Step 5: Submitting via gradescope

Submit the strFuncs.cpp and linkedListFuncs.cpp files on gradescope. Make sure to add your partner as a collaborator if you had one.

Grading Rubric

Most of the points will be awarded based on gradescope automatic grading. Other points will be assigned after visual code inspection by TAs - if a function is not implemented recursively, you will receive NOT receive any credit for that function at all.

The splice function is a bonus question - note that it is intended to be difficult. Although Gradescope will be display a score out of 110, your lab is only worth 100 points - should you successfully complete the bonus, you will receive 110/100. We will manually adjust the grades afterwards.

Gradescope automatic points

Test NameValue

isPalindrome

(10 pts)

findKthNode

(10 pts)

removeKFromFront

(10 pts)

sum

(20 pts)

splice

(10 pts - BONUS)

Code inspection human-assigned points

An important word about academic honesty and the gradescope system

We will test your code against other data files too—not just these. So while you might be able to pass the tests on gradescope now by just doing a hard-coded “cout” of the expected output, that will NOT receive credit.

To be very clear, code like this will pass on gradescope, BUT REPRESENTS A FORM OF ACADEMIC DISHONESTY since it is an attempt to just “game the system”, i.e. to get the tests to pass without really solving the problem.

I would hope this would be obvious, but I have to say it so that there is no ambiguity: hard coding your output is a form of cheating, i.e. a form of “academic dishonesty”. Submitting a program of this kind would be subject not only to a reduced grade, but to possible disciplinary penalties. If there is any doubt about this fact, please ask your TA and/or your instructor for clarification.