CS 307 Assignment 7, Writing Recursive Algorithms

Programming Assignment 7: This is a pair assignment. You may work with one other person on this assignment using the pair programming technique. Review this paper on pair programming. You are not required to work in a pair on the assignment. If you begin working with one partner and do not wish to finish the assignment with that partner you must complete the assignment individually. If you work with a partner the intent is that work together, at the same computer, on the assignment. One person "drives" (does the typing and explains what they are doing) and the other person "navigates" (watches and asks questions when something is unclear). You should not partition the work, work on your own, and then put things together. You may not acquire, from any source (e.g., another student or student pair or an internet site), a partial or complete solution to a problem or project that has been assigned. You may not show another student or student pair your solution to an assignment. You may not have another person (current student, former student, tutor, friend, anyone) “walk you through” how to solve an assignment. Review the class policy on collaboration from the syllabus.

If you work with a partner you will turn in one version of your code. Pick which account to submit the code to.

If you are working with a partner and want to use slip days you must both have the required number of slip days and both students use slip days. If the assignment is turned in 1 day late each student in a pair must have at least 1 slip day and it costs each student in the pair 1 slip day.

• Placed online: Wednesday, October 21
• 20 points, ~2% of final grade.
• Due: no later than 11 pm, Thursday, October 29
• General Assignment Requirements

Summary: The purpose of this assignment is to practice writing recursive algorithms.

In this assignment you will write recursive methods and trace some recursive code by hand. Some of the methods will use recursion to solve problems that could just as easily, if not more easily, be solved using simple iteration (for loops or while loops), but you will use recursion for the practice. (These are labeled "Hammer Problem" in the tips section of the handout.) You will collect all of these methods in a single class, Recursive. Some of the non-Hammer methods that solve the problem recursively still need a normal loop as in the recursive backtracking examples shown in class. (Such as the determining the space taken up by files and the N Queens examples done in class. Those were both examples of recursive backtracking.) The tester code will be placed in a class named RecursiveTester. You will turn in these two files. (No jar file this time.)

The provided file RecursiveTrace.java contains a number of methods and questions. Answer the questions in this file by tracing the code by hand. Place your answers in a comment at the top of the RecursiveTester class.

The provided file Recursive.java contains eight methods that you must complete. For each method you complete clearly state the base case and  recursive step for each method.

The provided file RecursiveTester.java contains a number of tests of the methods in Recursive.java. Some of these tests may be incorrect. Find and fix any incorrect tests. Your implementation of Recursive.java must pass these tests. Add at least 3 tests for each method other than the triangle and carpet methods to RecursiveTester.java.

When finished turn in your Recursive.java and RecursiveTester.java using the turnin program.

Checklist: Did you remember to:

• review and follow the general assignment requirements?
• work on the assignment with at most, one other person?
• fill in the header in RecursiveTester.java?
• ensure your methods in Recursive.java pass the tests in RecursiveTester.java and add your own tests? Add at least 3 tests for each method other than the triangles and carpets methods.
• Place your answers to the questions regarding the methods in RecursiveTrace.java in a comment at the top of the RecursiveTester class?
• turn in your files to the proper account in the Microlab via the turnin program before 11 pm, Thursday, October 29?

Tips and Individual Problem Descriptions from Recursive.java:

1.    The McCarthy 91 function:

// pre: n > 0
public int mcCarthy91(int n){

John McCarthy, an early computer scientist who created the Lisp programming language, devised the following function. (it is called the McCarthy 91 function.)

M(n) for integers > 0:
if n > 100, M(n) = n - 10
if n <= 100, M(n) = M(M(n+11))

Note for the case (if n <= 100, M(n) = M(M(n+11)) ) there is a nested recursive call.

So for example if n = 200 then M(200) = 200 - 10 = 190.

if n = 98 then M(98) = M( M(98 + 11) ). You might call that a double recursive call.. I have to find M(109) first. M(109) = 99. So now we have M(99) which equals M(M(110)) and so forth.

This function is actually a lot easier to implement then it seems. Don't make it harder than it is.

The remarkable thing about this function is that for all n such that 1 <= n <= 101 the answer is always 91! (meaning NINETY ONE, not 91 factorial.)

2. Phone Mnemonics 

public ArrayList<String> listMnemonics(String number)

(From Thinking Recursively by Eric Roberts.) On most telephone keypads the letters of the alphabet are mapped to various digits as shown in the picture below:

In order to make their phone numbers more memorable, service providers like to find numbers that spell out some word (called a mnemonic) appropriate to their business that makes that phone number easier to remember. For example, the phone number for a recorded time-of-day message in some localities is 637-8687 (NERVOUS). Write a method listMnemonics that will generate all possible letter combinations that correspond to a given number, represented as a string of digits. This is a recursive backtracking problem, but you are trying to find all the "solutions", not just one. In fact you are trying to find all possible Strings, not just Strings that are actual "words".

For example, if you call

ArrayList<String> result = recursiveObject.listMnemonics("623") 

your method shall generate and return an ArrayList containing the following 27 possible letter combinations that correspond to that prefix:

Note, the order of the Strings in the ArrayList is unimportant.  

You will use the following helper method:

public String digitLetters(char ch)

This method returns the letters associated with a given digit.

You will find it useful to create a method that does most of the real work:

private void recursiveMnemonics(ArrayList<String> result, String mnemonicSoFar, String digitsLeft)

The ArrayList named result is used to store completed mnemonics. mnemonicSoFar is the String that has been built up so far based on various choices of letters for a digit. Initially it is the empty String. digitsLeft consists of the digits from the original number that have not been used so yet. Initially digitsLeft is the entire phone number. (Or collection of digits.)

To kick off the recursion you would call method recursiveMnemonics from listMnemonics:

ArrayList<String> result = new ArrayList<String>();
recursiveMnemonics(result, "", number); // when starting the mnemonic is the empty string
return result;

It should come as no surprise there is a website that does this kind of thing, but checks the results against a dictionary:  http://www.phonespell.org/

3.    Binary Conversion

public String getBinary(int N)

(Hammer Problem) Write a method to recursively creates a String that is the binary representation of an int N.  

Here is an example. The binary equivalent of 13 may be found by repeatedly dividing 13 by 2.  If there is a remainder a 1 gets concatenated to the resulting String otherwise a zero gets concatenated to the resulting String. (The tricky part is figuring out the right time and place to do the concatenation.)

13 / 2 = 6 r 1
6 / 2 = 3 r 0
3 / 2 = 1 r 1
1 / 2 = 0 r 1

13 in base 2 is 1101. The method would return "1101".

Yes, you have to get the order of the digits correct! They cannot be in reverse order.

4. Reversing a String

public String revString(String target)

(Hammer Problem) Write a recursive method that returns a String that is the reverse of the input String.

System.out.println( recursiveObject.revString("Calvin and Hobbes"));

would return a String equal to this:

"sebboH dna nivlaC"

5.   Creating fair teams.(This is a hard one. You may want to save it for last.)

// pre: numTeams >= 2, abilities != 0, abilities.length >= numTeams
/* post: return the minimum possible difference between the team with the maximum ability and the team with the minimum ability. Every team must have at least one member and every person (ability score) must be assigned to some team. The return value will must be greater than or equal to 0.
*/

In this question you are passed an int that represents the number of teams we want to form. You are also passed an array of ints that represents the abilities of all of the individuals we want to assign to teams. (It could be athletic ability, IQ, artistic ability, etc.) Abilities can be positive or negative and are not limited in any way.

The goal of this method is to find the minimum possible difference between the team with the maximum ability and the team with the minimum ability. The constraints are everyone (represented by a value in the array named abilities) must be placed on a team and every team must have at least one member.

You must create a helper method. You will need to keep track of multiple things such as which element in the abilities array you are currently considering, what the total ability score is for each team, as well as some way of ensuring each team has at least one member. (You could simply track the number of members per team.)

For example if we have the following abilities: [1, 2, 3, 4, 5, 6, 7] and want to form three teams the min difference possible between the team with the maximum total ability and the team with the minimum total ability is 1. Your program does not need to show what the members of each team are but in this example the minimum possible difference is created by having 2 teams with a total ability of 9 and 1 team with 10. (min 9, max 10). There are multiple ways of doing this with these values one of which is:
Team 1:  1 + 3 + 6 = 10
Team 2:  2 + 7 = 9
Team 3:  4 + 5 = 9

Note you can use methods from the Array class in your base case. (copyOf and sort are particularly useful)

Note, you are not being graded on the efficiency of this method.

6. Water flowing off a map.


/*pre: map != null, map.length > 0, map is a rectangular matrix, 0 <= row < map.length,
  0 <= col < map[0].length
  post: return true if a drop of water starting at the location specified by row, column can reach the edge of the map, false otherwise.
*/
public boolean canFlowOffMap(int[][] map, int row, int col)    

In this problem an area of land is represented as a 2D array of ints. The value at each element represents the elevation of that point on land. The higher the elevation, the higher the number, the lower the elevation the lower the number. So a flat plain at an elevation of 100 feet above sea level might look like this:

A river flowing through a 200 foot  gorge might look like this. Cells that make up the river are shaded gray.

Method canFlowOffMap has a parameter that represents a map of elevations as 2D array of ints. It also has parameters that represent the starting location of a drop of water on the map.

• The drop of water can move to one of the four adjacent cells (above, below, left, and right of the current cell) if the elevation in that cell is less than the elevation of the current cell.
• Water in any cell on the edge of the map can flow off the map.
• In other words water in a cell on the border of the map is assumed to be able to flow off the map regardless of the cells around it.

 In the first example, the plain, water in any cell not on the border of the 2d array, cannot flow to any other cell because all adjacent cells because all the elevations are the same. Water on any of the bordering cells could flow off the map. In the second example if a drop of water started at the cell at row 2, column 2 (the yellow cell with a value of 96) it could eventually flow off the map by following the river. (Each segment of the river is one foot lower than the previous.) 

Recall that water on the border can also flow off. So in the second example if we started at the cell in row 2, column 0 (the red cell with a value of 200) then we can flow off the map. The elevation in that cell is 200. The water can't flow to any of the other cells adjacent to it, but that doesn't matter because that cell is on the border and so if start there I can flow off the map. If the starting cell is row 3, column 1 (the blue cell with a value of 200), the water can flow off the map. That cell has an elevation of 200. The water can't flow west or south because those cells are also at 200. But the water can flow north or east to the cells in the rive. (the water falls off the bank into the river) and then off the map via the river. Finally the cell at row 6, column 2 (the green cell with a value of 200) can't flow off the map. It tries north and dead ends. It can't move east or west. It can try south, but eventually dead ends.

When thinking about the problem it may help to think that off the edge of border rows and columns is an infinitely deep canyon. So if you are on a border of the map, (row 0 , column 0, last row, or last column) then you can flow off the map. (Base case?)

canFlowOffMap is to return true if a drop of water starting at the location specified by row, column can reach the edge of the map, false otherwise.

Hints: Use the recursive backtracking algorithm shown on the class slides for moving through a maze.

7. Sierpinski triangles

Write a method to draw a Sierpinski triangle. Sierpinski triangles are fractals named after their creator. Here is an example

Here is another example.

To draw the Sierpinski triangle there are two methods, a starter method and the recursive method. Here is the header of the starter method:

/**
* Create a DrawingPanel and place Sierpinski triangles in it. The lower
* left corner should be 20 pixels from the left edge of the window
* and 20 pixels from the bottom of the window.
* @param windowSize > 20
* @param minSideLength > 4
* @param startingSideLength > minSideLength
*/
public void drawTriangles(int windowSize, int minSideLength, int startingSideLength)

The parameters of this method specify the size of the window that will contain the triangles, the minimum side length and the initial side length. This method is already complete. It creates a DrawingPanel object, gets the Graphics object for that DrawingPanel, and then calls the recursive helper method that actually draws the triangles. (DrawingPanel is not a standard Java class. You must download it from this web page.) Here is the header of the recursive helper method that you will complete.

public void drawTriangles(int minSideLength, double currentSideLength, double x1, double y1, Graphics g)

The parameters for this method are the minimum side length, the current length of a side, and a set of coordinates for the lower left corned of an equilateral triangle.

The algorithm for drawing a Sierpinski triangle is:

-if the currentSideLength is less than or equal to the minSideLength, then draw the triangle. Note, the length of the triangle and the coordinates are doubles. When you actually draw a triangle you will have to cast these to ints. (Base Case)
-else create (not draw) three smaller Sierpinski triangles that are half the size of the original. The lower left corners of these three triangles are located at

1. the original x1, y1.
2. the midpoint of the line segment going from x1, y1 to the top of the triangle
3. the midpoint of the horizontal line segment starting at x1, y1.

Use trigonometry to determine the value of y2. The other coordinates are easy to figure out:

• x3 = x1 + 0.5 * length of side
• y3 = y1
• x2 = x1 + 0.25 * length of side

y2 = y1 - sqrt(3) * length of side / 4.

When you reach the base case you will use the Graphics object to actually draw the lines. The method passes doubles until it reaches the base case when you will have to cast to int.

You can use the drawLine method to draw the outline of the "small" triangle. The drawLine method accepts 4 ints, which are the endpoints of the line segment to draw. Alternatively, you may use the fillPolygon method. Either approach is acceptable. The examples above just draw the outlines of the triangles. here are example of filling the polygons. Here are some examples with the triangles filled in.

minSideLength = 100

minSideLength = 15

Note, you may get some results that look a bit off. That is okay. This is because are parameters are ints and when we divide we may get some round off errors. How would you avoid those round off errors? (not necessary to answer the question in the assignment. Just something to think about and try on your own.)

8.  Sierpinksi Carpet

Create a method to draw a Sierpinski carpet. Here is an example:

The carpet is created via the following algorithm.

- if the length of the square is less than or equal to the limit value do nothing.
- else (the length of the square must be greater than the limit value) divide the square into a 3 by 3 grid which will contain 9 sub squares. Cut out the middle square and then create a Sierpenski carpet in the 8 remaining sub squares.
 

The middle square is "cut out" by drawing a rectangle colored white.

I have provided the starter method. You must supply the method to complete the carpet. The header for the method to actually draw the carpet is:

 private static void drawSquares(Graphics g, int size, int limit, double x, double y)

You will need to use the fillRect method from the Graphics class. Here is its signature.

fillRect(int x, int y, int width, int height)
    Fills the specified rectangle.

Recall point 0, 0 is at the top, left of the drawing panel and y increases as you go down (not up).

You will complete the following method.

public static void drawSquares(Graphics g, int size, int limit, double x, double y){

Again, the x and y coordinates are passed as doubles. When you call the fillRect method you will have to cast them to ints.

As in the Sierpinski triangle problem you may get some round off errors. That is okay.

Other famous problems with recursive solutions: These are not required but if you are interested in more recursive problems consider the follow.

• Knight's tour
• Koch snowflake
• Towers of Hanoi
• Knapsack problem

  Back to the CS 307 homepage.