Warning: Outdated Content
This MP is from a previous version of CS 125. Click here to access the latest version.
MP6: Recursion
Recursion is an important and powerful programming technique. Sometimes it is the best way to solve a problem, and sometimes it is almost the only way to solve a problem. Recursion can be tricky to wrap your head around at first, but as usual the best way to get comfortable with this technique is to practice.
For MP6 you’ll complete several programming tasks that encourage you to develop recursive solutions. It is due Friday, November 17th, 2017 @ 5PM. To receive full credit, you must submit by this deadline. In addition, 10% of your grade on MP6 is for committing code that earns at least 50 points by Monday, November 13th, 2017 @ 5PM.
1. Learning Objectives
MP6 introduces the concept of recursive programming. You’ll learn how to complete simple recursive methods to accomplish common programming tasks. We’ll also introduce you to binary trees, an important computer science data structure and one very amenable to recursive approaches.
2. Assignment Structure
MP6 consists of three programming tasks:
-
ReverseList.java: here you must extend a generic parent class and provide a reversal method, either using recursion or iteratively. Consider this task a warm up. List reversal is straightforward, and the hardest part of this task is probably getting the generic subclassing right. -
Tree.java: here you must complete a binary tree class, including adding constructors and insertion methods, along with methods that search and perform computations on your tree. This tasks contains the bulk of the points for the MP, so work on it once you’ve finishedReverseList.java. -
DNA.java: for the final task you must complete a class that stores a DNA sequence and a static method that computes the longest common subsequence of two DNA instances. Longest common subsequence is the hardest algorithmic challenge on this MP, so leave this for the end.
Like MP5, MP6 provides a bit less scaffolding than previous MPs. The official specification is our MP6 online documentation. It should precisely define what each public method in each class should do. Private methods are left for you to design in any way that allows the tests to pass. If you believe that the documentation is unclear, please post on the forum and we’ll offer a clarification is needed.
2.1. Obtaining MP6
Please follow the instructions from MP1.
You’ll find MP6 in an MP6 folder in your Subversion home directory.
Unless you want to learn a lot more about Subversion, do not delete your MP6
folder on the server.
This is something that you cannot fix on your own using the Eclipse Subversive
Subversion plugin, and will need to get course staff help with.
3. Approaching MP6
Completing MP6 requires writing fewer lines of code than MP4 and MP5. But it is recursive code, so it will take you longer. Don’t expect to make as much progress writing recursive code when you are getting started. It’s tricky, and takes practice. Slow down and focus on applying the recursive design principles that we’ve taught in lecture and in lab.
3.1. Understand The Requirements
To complete MP6 you must understand the specification. Read that first. And then read it again.
3.2. Designing Recursive Functions
Recall the guidelines for designing recursive functions that we presented in Lab 10:
-
Every recursive function must have a base case. If you don’t stop recursing, you will eventually run out of memory and your program will crash. So there must be some case where you do not call yourself again.
-
The base case must be reached. As a corollary to the above, every set of recursive calls must eventually reach the base case, otherwise (again) your program will recurse infinitely, run out of memory and crash.
-
The problem should get smaller each time. Each recursive step should reduce the size of the problem somehow. This can happen in several ways. In Fibonacci, for example, we reduce the size of the problem by reduction toward known staring values. When processing trees, we reduce the size of the problem by splitting the tree into several subtrees which are considered separately. How this happens depends on the problem, but it does need to happen somehow.
It can also be helpful to consider simple cases. How do you reverse a list with only one element? Now, extend that to a list with two elements, then three. You may begin to see a pattern emerge that helps you understand how to design your recursive approach.
3.3. Binary Trees
MP6 also introduces you to binary trees, an important computer science data structure. Binary trees are also recursive data structures, in that each tree node refers to other tree nodes, including a parent (moving up the tree) and two children (down the tree).
Like other data structures, binary trees are useful because of the algorithms that we can run on them. Sorting and searching can be particularly efficient on binary trees due to the way that they structure data.
3.3.1. Insertion algorithm
There are many great online resources to help you learn about binary trees. But let’s consider one of the more basic tree operations: insertion. Storing data in my tree requires that I be able to insert values. And being able to efficiently search for values later requires that I perform insertions in a particular way.
-
Start at the root of the tree.
-
Compare the value that is being inserted with the value of the current node.
-
If it is larger, try to move to the right.
-
If it is smaller, try to move to the left.
-
If the current node has a left or right child (depending on the choice above), make that the current node and continue.
-
Otherwise set the left or right child (depending on the choice above) of the current node to a new node with the new inserted value.
-
Continue until the node is inserted.
Note that your binary trees can reject duplicate values. So if you reach a node that has the same value as the one you are trying to insert, the insertion can fail.
If you maintain the sorted structure during your insertions as described above, the other algorithms that we ask you to complete on trees will be straightforward.
3.4. Getting Help
The course staff is ready and willing to help you every step of the way! Please come to office hours, or post (in the right place) on the forum when you need help. You should also feel free to help each other, as long as you do not violate the academic integrity requirements.
4. Grading
MP6 is worth 100 points total, broken down as follows:
-
10 points:
ReverseList.java -
50 points:
Tree.java:-
10 points for constructors and insertion
-
10 points for minimum and maximum
-
10 points for search
-
10 points for depth counting
-
10 points for descendant counting
-
-
20 points:
DNA.java -
10 points for no
checkstyleviolations -
10 points for committing code that earns at least 50 points before Monday, November 13th, 2017 @ 5PM.
4.1. Test Cases
As in previous MPs, we have provided exhaustive test cases for each part of MP6. Please review the MP1 testing instructions.
4.2. Autograding
Like previous assignments, we provide you with an autograding script that you can use to estimate your current grade as often as you want. Note that, like previous MPs, the local autograder can only calculate 90 out of your 100 total points.
Unless you have modified the test cases or autograder configuration files, the autograding output should equal the score that you will earn when you submit. If you modify our test cases or the autograding configuration, all bets are off.
5. Submitting Your Work
Overall you should refer to our instructions for using Subversion. Commit early and often! You only earn credit for the version of your code that is committed to your repository, so ensure that we have your best submission before the deadline.
And remember, you must commit something that earns 50 points before Monday, November 13th, 2017 @ 5PM to earn 10 points on the assignment. This is a bit of a higher bar than in previous assignments, since fixing checkstyle errors will only get you 10 points and there are no points for just compiling. So you’ll need to complete a few bits of class logic past this bar.