CSE 131 Module 6: Recursion

• Module Home
• Exercises
• Studio
• Lab
• Extensions

Extensions

Extension 1: Divine Lines (5 points):

Authors

• Ron K. Cytron
• Ken Goldman

A video demonstrating a solution can be found here.

Do not change the parameters or return type of the drawLine method! You are welcome to define other methods in the Lines class if you wish, but the drawLine method's signature (the number and types of its parameters and its return type) must be preserved as you do your work.

Your task is to devise an algorithm for drawing a line from (x1,y1) to (x2,y2) using recursion. It may take you some time to think about how to do that, but once you see the recursive nature of drawing a line, you will probably need only a few lines of code to accomplish this task.

Please take note of the following guidelines, as you will not receive credit unless your solution follows the rules of this assignment:

• The code given to you will perform a test of your drawLine when you run it as a Java Application.
• If you want to draw lines interactively using your solution, then run the InteractiveLines class as a Java Application.
• Do not use StdDraw.line to do any of your work!
• The only methods you are allowed to use from StdDraw are point, setPenRadius, and setPenColor.

  This means you must draw your line one point at a time.

• Some students approach this problem by computing the slope of the line and then incrementally trying to draw pieces of it using recursion. That approach comes to grief for vertical lines, which have infinite slope. There is a much easier and satisfying way to solve this problem, but you have to think about it.

  Do not compute or use the slope of the line in your approach. We will not count the extension if you do that. Instead, think recursively about how a line is constructed.

When you done with this extension, you must be cleared by the TA to receive credit.

• Commit all your work to your repository
• Fill in the form below with the relevant information
• Have a TA check your work
• The TA should check your work and then fill in his or her name
• Click OK while the TA watches
• If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 6.1

	Last name	WUSTL Key	Propagate?
		(or your numeric ID)		Do not propagate
e.g.	Smith	j.smith
1				Copy from 1 to all others
2				Copy from 2 to all others

---

TA: Password:

End of extension 1

Extension 2: Persian Recursian (10 points):

Authors

• Ron K. Cytron
• The idea for this assignment comes from the article "Persian Recursion" by Anne M. Burns that appeared on pages 196-199 of Mathematics Magazine, volume 7, in 1997

• A video demonstrating my solution can be found here.
• That video instructs you how to speed up the drawing substantially.
• Don't speed things up until you see the rug is drawing properly.

• The square is described by its lower-left corner (in this case, (0,0)), and its size (in this case, 1).
• Each step of the recursion considers the colors of the provided square's sides (in this case, blue), and computes a color for the two lines to be drawn inside the square (in this case, red).

  Computing the color of these two lines is what makes the rug look as it does. More detail is given below concerning how to pick a color.

• Further recursion would act on the sub-squares you see in the above picture. For example, the upper-left subsquare has its lower-left corner at (0, 0.5), has size 0.5, and has colors blue, red, red, blue, starting from north and proceeding clockwise.

The parameters for persianRug are documented in the source code provided to you for this extension.

Notes:

• Colors in this lab are represented as an index into a Color array called palette. This array is provided for you in the source code and it is passed into your persianRug method.
• Indexes into palette are passed into persianRug to describe the colors of the square's bordering edges. For example, blue is represented by index 0 into the palette array, and cyan appears at index 1.
• Picking a color for the two lines drawn inside a given square is the creative aspect of this assignment. The following should be read carefully and understood before you jump into coding.
  • Although you will eventually pick more diverse colors, we recommend that unti your lab is working, you should always use color index 0 for the color of the two drawn lines.
  • Once that is working, you must pick a color that is a function of the square's bordering colors (which are conveniently represented as indexes into palette. That function must have the following properties to perform correctly:
    • The function must return a value that is an appropriate index into the palette array.

      As you know, 0 is the smallest index, and the largest index is palette.length-1.

    • The function must return the same value for any permutation of a given square's bordering colors. For example, if the colors are specified in order red, blue, blue, red, then any square with two blue and two red sides must compute the same color for the two drawn lines.

      Recall that these colors are represented as integers, each being an index into the palette array. What kinds of functions on integers return the same result no matter the order of those integers?

  • Different functions will produce different rugs. The rug below is computed using the same code as the rug shown at the top of this assignment, but the function was tweaked slightly: Perhaps you can see that in the above rug, once a square has red on each of its borders, the two drawn lines inside that square are also red. That effect just happens to be a property of the function I used to produce the above image.

  • Rugs contributed Fall 2013:

    Ben Greene	Dylan Jew and Ari Spilo	Alan Waldman
    Sam Chase	Meagan Provencher	Ben Zod
    Diana Fasanello	Anna Kolasa and Kunyao Liu	Jeremy Scharf

  • When things go wrong, it is almost always because you do not have a consistent view of the square as presented to persianRug. Ask for help as needed!

  When you done with this extension, you must be cleared by the TA to receive credit.

  • Commit all your work to your repository
  • Fill in the form below with the relevant information
  • Have a TA check your work
  • The TA should check your work and then fill in his or her name
  • Click OK while the TA watches
  • If you request propagation, it does not happen immediately, but should be posted in the next day or so

  This demo box is for extension 6.2

  	Last name	WUSTL Key	Propagate?
  		(or your numeric ID)		Do not propagate
  e.g.	Smith	j.smith
  1				Copy from 1 to all others
  2				Copy from 2 to all others

  ---

  TA: Password:
  

  End of extension 2

  ---

  Extension 3: Flower Power (4 points):

  Authors

  • Ron K. Cytron
  • Ken Goldman

  A video demonstrating my solution can be found here.

  In the extensions folder open the recursivepatterns package. The following classes found there, and described in greater detail below, must be completed for this extension:
  • TransparentColor
  • Flower
  The ultimate goal is to complete the flower method of the Flower class so that it draws an image similar to the one shown below: The colors shown in the above image are somewhat transparent, so that the color of an ellipse is allowed to bleed through the ellipse above it.

  You can proceed by working on either class first. However, if you postpone TransparentColor, you will see solid colors in your flower until you have completed that class.

  Details

  TransparentColor

  As is the case with most color models, Java's Color objects are allowed to have a degree of transparency.

  The transparentColor method, as provided to you, ignores the alpha parameter and returns the color provided as input.

  You must change this behavior so that the color returned as the same red, green, and blue components as the provided color, but with the specified transparency.

  Java makes this easy, because there is a constructor for Color that does the job. This task is given to you primarily to acquaint you with the process of looking through JavaDoc documentation to find a class or method you need.

  Follow the instructions provided in the TransparentColor source code.

  Before moving on, test your code by running TransparentColor as a Java Application. You should see the colors solid at the upper right of the drawing window, and blended (more transparent) at the lower left.

  You must demo this to a TA when you seek credit for this extension.

  Flower

  Your task here is to complete the flower method, whose parameters are described in the JavaDoc for the method. Some useful guildines follow:

  • The StdDraw class offers a filledEllipse method, but you must set the color before calling it.
  • You should choose a random color for each ellipse you draw, and you are provided a palette of Color objects as input to your flower method.

    If necessary, review the material in the text and slides that discusses how to pick a random integer. You would use that integer to index the palette array.

  • You must find the substructure in the flower pattern. To help with this, the following diagram shows the locations of each ellipse within a given level of recursion:
  • Analyze the above diagrams to infer the area taken up by each sub-ellipse that you must draw.
  • Remember that the StdDraw coordinate system has (0,0) at the lower-left, and (1,1) at the upper right.
  • Remember that StdDraw shapes take a center as their primary coordinate, and use half-widths and half-lengths for dimensions.

  As usual, ask for help as needed.

  When you done with this extension, you must be cleared by the TA to receive credit.

  • Commit all your work to your repository
  • Fill in the form below with the relevant information
  • Have a TA check your work
  • The TA should check your work and then fill in his or her name
  • Click OK while the TA watches
  • If you request propagation, it does not happen immediately, but should be posted in the next day or so

  This demo box is for extension 6.3

  	Last name	WUSTL Key	Propagate?
  		(or your numeric ID)		Do not propagate
  e.g.	Smith	j.smith
  1				Copy from 1 to all others
  2				Copy from 2 to all others

  ---

  TA: Password:
  

  End of extension 3

  ---

  Extension 4: Fibonacci Recursively and Iteratively (5 points):

  Authors

  • Ron K. Cytron

  Introduction

  You have written the recursive function for the Fibonacci Sequence in studio. In this extension, you will compare the running time of that recursive formulation with an iterative formulation of the same function.

  Procedure

  • Find the fibonacci package in the extensions source folder.
  • Complete the recursive method so that it returns the n^th fibonacci number using the recursive proram from studio.
  • Complete the iterative method so that it computes the same function, but iteratively.

    As a hint, you will need two variables that represent the (n-1)^th and (n-2)^th values of the sequence. Adding those together produces the n^th term. The variables' values are then shifted prior to the next iteration.

  • Run the CorrectnessTest to make sure your functions are computing the correct values.
  • We will now compare the timing of the two methods. First run TimedTest, and give it a little time to finish. Right click the outputs folder and click refresh. You should now see two excel file outputs in the folder. Open them up and plot the points, observing the difference in time between the iterative and recursive methods.

  When you done with this extension, you must be cleared by the TA to receive credit.

  • Commit all your work to your repository
  • Fill in the form below with the relevant information
  • Have a TA check your work
  • The TA should check your work and then fill in his or her name
  • Click OK while the TA watches
  • If you request propagation, it does not happen immediately, but should be posted in the next day or so

  This demo box is for extension 6.4

  	Last name	WUSTL Key	Propagate?
  		(or your numeric ID)		Do not propagate
  e.g.	Smith	j.smith
  1				Copy from 1 to all others
  2				Copy from 2 to all others

  ---

  TA: Password:
  

  End of extension 4

  ---

  Extension 5: Tic-Tac-Toe: A Perfect Player (8 points):

  Authors

  • Tim Huber
  • Ron K. Cytron

  Issues: Not yet ready

  Warning: You must have a complete and working tictactoe extension before you take on this work. So make sure you already have credit for that extension and that all method work properly.

  Procedure

  Your task in this extension is to design a robot player that plays tic-tac-toe perfectly. Once this player is implemented correctly, it should never lose, regardless of whether it makes the first move or not. Note that a tic-tac-toe game between two perfect players will always end in a tie.

  Inside the extensions folder is a tictactoexpert package, which contains the following:

  NaivePlayer

  This player picks a random move from those currently available on the board.

  PerfectPlayer

  Here is where you do your work. The perfectMove method should play so as to always at least force a tie, if not a win, for myPlayer. As given to you, the code simply picks the next available move in a top-to-bottom, left-to-right scan of the board.

  Game

  You can use this class to test your PerfectPlayer. The play alternates between you and the PerfectPlayer. You should test your code here by allowing it to win or draw, with you playing (as human) a good but not perfect game.

  PPTest

  This tests your PerfectPlayer, ensuring that it always draws against itself, and never loses against the NaivePlayer.

  Open it up and you should see a PerfectPlayer class. This is where you will be doing the work for this extension. It contains a public static int[] makeMove(String[][] board, String playerSymbol) that takes in a double String array representation of the board and the String symbol of the player ("x" or "o"), and returns an int array in which the first entry is the row of the robot's move and the second entry is the column. In the String[][] parameter, the row and column of each String correspond to that row and column on the tic-tac-tow board. A "" (not null) indicates a free space and an "o" or "x" indicate either the robot player or its opponent's mark. The playerSymbol parameter tells you which mark corresponds to the robot's moves.

  There is a simple, complete robot player implemented in the DumbPlayer class that you can look at for reference.

  You can find outline of tic-tac-toe strategy here, which can be turned into a simple algorithm for the robot player. This algorithm doesn't strictly need recursion, but you will find that creating and blocking forks is much more easily accomplished by calling the makeMove method recursively. This will allow you to predict the state of the board several moves ahead and decide if a move actually produces a fork.

  In a tic-tac-toe game, the first and second moves are extremely important. You may want to handle these moves individually before moving on to a more general algorithm.

  You can test your perfect robot player with the TestPerfectPlayer JUnit test. Be aware that this test is not exhaustive (even after passing, the robot player could be making some mistakes) but it is sufficient to get credit for this extension.

  When you done with this extension, you must be cleared by the TA to receive credit.

  • Commit all your work to your repository
  • Fill in the form below with the relevant information
  • Have a TA check your work
  • The TA should check your work and then fill in his or her name
  • Click OK while the TA watches
  • If you request propagation, it does not happen immediately, but should be posted in the next day or so

  This demo box is for extension 6.5

  	Last name	WUSTL Key	Propagate?
  		(or your numeric ID)		Do not propagate
  e.g.	Smith	j.smith
  1				Copy from 1 to all others
  2				Copy from 2 to all others

  ---

  TA: Password:
  

  End of extension 5

  ---