In this lab, you will implement some recursive routines that will operate on arrays. Then you will implement code that manipulates a sorted linked list.
After completing this lab, you should:
You may work with a partner for this lab. If you choose a partner, both members must contribute to the same work. That is, you cannot simply divide the lab in half, as everyone is responsible for all the content. Instead, you should use a pair programming style. In pair programming, one person acts as a driver, who takes control of the keyboard. The other person acts as a navigator, who reviews what the driver writes and offers advice. Oftentimes, the driver is occupied with details of the problem (e.g., variables, control flow, etc.), whereas the navigator is concerned with bigger-picture problems (e.g., functions, design, interactions). This works well for problems which are simply too large to fit into one person's head. If you're unfamiliar with the concept of pair programming, you may wish to watch this video on the topic.
With pair programming, oftentimes it works best if both participants are of approximately the same skill level. Generally, if the disparity in skill is large, the end result is frustrating for both parties - it really only works when both parties operate at approximately the same speed. With this in mind, you should select someone of approximately the same skill level.
You may wish to peruse Dale chapter 7.
-bash-4.2$ cd -bash-4.2$ pwd /cs/student/yourusername -bash-4.2$ cd cs24 -bash-4.2$ pwd /cs/student/yourusername/cs24 -bash-4.2$ mkdir lab6 -bash-4.2$ cd lab6 -bash-4.2$ pwd /cs/student/yourusername/cs24/lab6
Now copy over the files for this week.
They are kept in the directory: /cs/student/kyledewey/cs24/labs/6
-bash-4.2$ cp /cs/student/kyledewey/cs24/labs/6/* .
Note that there is a '.' at the end of that line. cp means copy.
/cs/student/kyledewey/cs24/labs/6/* means all of the files contained
in the directory /cs/student/kyledewey/cs24/labs/6. The '.' means to
copy from that location to the current location.
Now check to make sure the copy worked correctly:
-bash-4.2$ ls
You should see a set of files listed that will be used for this warm-up.
From here, you need to copy over files from your week 3 and week 5 labs, like so:
-bash-4.2$ cp ../lab3/* ../lab5/* .
The file reading_questions.txt contains a series of questions
you must answer. Note that this time
around, the questions are closely connected to the lab, and your answers
can be used directly in solving the rest of the lab. As such, you may want
to answer all the questions first and proceed through the rest of the
lab second. A setup for those problems, along with additional
instructions and explanations, follows.
Breaking down a problem so that you can implement it recursively is a way of thinking, not just an implementation technique. You've had some practice this quarter taking large problems and breaking them into smaller parts. Now we're doing something pretty different - we are breaking a problem down into a smaller part that is identical to the original problem (but smaller).
The way to think about this is, if you had a helper to whom you could give a subproblem (that is the exact same problem but on a smaller problem), then how would you use that result to make your job easier?
For example, if I have to calculate x^y,
that's really x*x*x*...*x. Well,
if I had the answer to x^(y-1), that would make my job really easy - just
multiply by x!
The problem is broken up into a few parts:
For the above example of exponent, that is, x^y, the
answers to the above questions are:
x^0 = 1 or x^1 = xx^(y-1)x * x^(y-1)You can either express them as mathematical functions or as a description. For example, let's break down the problem of sorting 100 words:
1 word is, by definition, sortednth word into the sorted list of n-1 words
As another example, let's look at the factorial function, AKA n!.
An equation depicting this function (provided by Wikipedia) is shown below:
As shown by the above equation, it is defined that 0! = 1.
This acts as a base case.
From there, factorial is recursively defined in terms of (n - 1)!.
We can put the factorial function into the same format as the two examples above, as shown below:
0! = 1(n - 1)!(n - 1)! * n
In functions.cpp, two functions have
been written iteratively. You will
be writing recursive versions of them.
The first sums the numbers from 5 to n.
The second counts the number
of numbers larger than 7 in an array of integers. Your job is to
create two new functions that are recursive.
For full credit in this part, you may not:
The above restrictions are in place to force you to write code that fully embraces recursion. Solutions that violate any of the above constraints will recieve only minimal credit, if any at all.
sum5ToNRecursively
First, make sure your input is valid (n<5). If not, return 0.
Now look for the base case. You need to detect when it is the base
case and return the right value when it is.
Then write the code that calls the recursive case. Finally, when you
have the answer from the recursive call, modify it to be the right
return value for this problem.
If you go to the recursive function sum5ToNRecursively, these steps
have been placed in comments to help you fill in the code.
Fill in the appropriate code, compile, and run the program:
-bash-4.2$ clang++ main_functions.cpp functions.cpp
countMoreThanSevensRecursivelyIf you are working in partners, switch partners now.
Now fill in the code for countMoreThanSevensRecursively. I have given you the
function prototype, but you need to fill in all of the code. I have
not commented this one for you.
-bash-4.2$ clang++ main_functions.cpp functions.cpp
LinkedList Holds
Right now, your IntLinkedList and
IntNode classes hold ints, not anything else.
We are going to copy that code and make it hold Cards instead,
so it can be used to hold a hand of cards. The new
CardLinkedList.h has been provided for you. Your job is to
take your IntLinkedList.cpp code and modify that to work with
the CardLinkedList.
Take a good look at CardLinkedList.h and
CardNode.h. Notice that the name of
the class has changed, the type of one instance variable has
changed, and the types of some input parameters and return types
of the methods have changed.
As a first step, rename your IntNode.cpp to CardNode.cpp:
-bash-4.2$ mv IntNode.cpp CardNode.cpp
Now go through and change the class name to CardNode and the
int types to Card. Also remove all references
to the variable count and the getCount method.
(If you're curious, that was a good use of a
static variable defined in a class, or a class variable.
We won't be going into details of this feature in this class, though you may wish
to read about it if it interests you.)
The printCardNode method does nothing more than call the
print method in Card.
Now do the same thing with IntLinkedList.cpp.
Your print method printList has the following key features, some
of which may need adjustment:
tmp->printIntNode(); in its loop
printf(", "); in its loop
After the loop, printf("\n");
Once you are finished with your changes, try compiling and running the code:
-bash-4.2$ clang++ CardNode.cpp CardLinkedList.cpp Card.cpp main_cards.cpp
You should not proceed forward until your code compiles and runs, since subsequent steps build on top of this code.
CardLinkedList::addSortedCurrently, the cards are in some sort of order related to the order in which they were added by the player. Instead, we need to be sorted.
The easiest way to do this is not to sort the cards already in the hand. Instead, we should make sure the cards in the hand are always sorted (starting from an empty hand). As long as we insert each new card into the right location in the list, the list will always remain sorted.
We begin with an empty list. Then, the first item is inserted, and the list is a sorted list of one item. Then, the second item is inserted into the list. If that second item is less than the item in the list, then it is placed at the head. Otherwise, it is placed after the existing item. When a third item is inserted, it is placed either at the head, between the two items, or at the tail. As long as you make sure that each item is inserted into the correct location, the list will always remain sorted.
For more information on insertion sort, here is a demo by Romanian folk dancers. Although it is actually showing the insertion sort as a way to sort an unsorted list of numbers, we can relate it to what we are doing, as well. The dancers with their backs to the video have not be inserted yet. When two look at each other, they are making their comparison. The new item is finding its place in the list. They show an array, but it works similarly to a linked list with one major exception. In an array, the new one is placed at the end of the array and then bubbles back down into its proper location. In a linked list, while the search for its location occurs, it is not in the list. We find where to insert it and then insert it at that spot. We do not insert it in the wrong location and then gradually move it down the list. You can find other animations by typing "insertion sort animation" into Google. Most of those are in-place sorts on an array, just like the folk dancers' rendition. Just view those unsorted ones as items that have not yet been inserted, and you'll be fine.
You need to write the method CardLinkedList::addSorted(Card *c).
This calls the compare method on the Card objects
to figure out where this new Card should be placed in the linked list.
If you aren't sure how to code this, here are a few tips:
Remember that you are not supposed to access any
fields of the Cards from outside of the Cards methods -
just call the compare method. And don't forget that
the linked list actually holds Node objects - you need to access a method
of the Node object in order to access the Card it is holding.
An iterative solution for this part will receive full credit. That said, a recursive solution will allow you to get up to a 20% bonus for this lab. If you wish to write a recursive solution, we recommend you first implement and test an iterative solution, and get that up to speed. From there, implement the recursive solution. Be sure to leave your iterative solution commented-out in your code if you opt to do both solutions. A fully-working iterative solution will get more points than a very broken recursive solution.
CardLinkedList::addSorted
Make sure you make good test cases. In this case, you need to think about
all of the positions a Card could be inserted into an existing list.
Create different scenarios that insert cards at the beginning, end,
and within the middle of the list.
The modify the main_cards.cpp to use the
addSorted method to place items into
the linked list rather than the addHead method. Compile, test, test again,
test yet again.
First, fill out the required fields in the provided README.txt file.
Once you have filled this in, you may submit everything with the following command:
-bash-4.2$ turnin lab6@cs24 README.txt CardLinkedList.h CardLinkedList.cpp CardNode.h CardNode.cpp functions.h functions.cpp main_cards.cpp main_functions.cpp reading_questions.txt
All content was graciously provided by Professor Diana Franklin, with slight formatting-related adaptation.