CSC300: Homework (MySecondHomework)

for homework this week I want you to read chapter two in core Java for the impatient I want you to start looking at section 1.3 of the textbook that's where we'll start talking about stacks and linked structures we'll start that next week and in particular look at the subsection on linked lists which starts around page 142 it's sort of toward the back of section 1.3 of the textbook but we're going to start there talking about howling structures are built and then I've got some homework for you on d2l that I'll walk through now and let's just start looking at it so here's my second homework there's several problems that are marked in here with to do so the first problem is to translate the following sum function from an iterative solution to a recursive one so you should write a helper method don't use any fields to solve this problem you know you're not allowed to do anything like this where you declare variables outside the function we'll talk more about that next week but don't do that and you're allowed to write a helper function for each recursive function so here's the sum you should write as sum helper so I think I'll give you an example up here yeah this is something like this is a reasonable sort of helper function that you might work with and start working on how you want to figure out the sum function I've given you an a model which is to figure out the minimum value so here is the minimum value iteratively using a while loop and here's the minimum value using a forward recursion so here we're asking you just to compute the sum and you can compute it either using a forward or backward backward recursion I encourage you to try both actually see if you can write it both way the second problem is to write a recursive version of the reverse function given here so this is again something where you can write a helper function to get you through the list and figure out how to write this recursive function without a loop so you're forbidden to use loops in these recursive functions you should not have any occurrence of while or for those words should not appear if they do that you've got something wrong for the next problem you're gonna be working with Mickey Mouse I had to adjust my screen a little bit to get this to show so when you run the program it should pop up a screen that will draw Mickey Mouse for you when you close that window it will terminate your program I was having trouble because in full-screen mode on Mac OS it appears that Eclipse will not show the Mickey Mouse window so I encourage you to use Eclipse outside of full-screen mode when doing this homework so what's Mickey Mouse look like well Mickey Mouse is essentially three circles so I've given you code to draw three circles and there's some stuff in here that I've put in to help you or to give you hints toward the solution of the recursive version but what are we going to do I'm drawing a circle for Mickey's head I'm gonna draw a circle for the left ear gonna draw a circle for the right ear if you want to have different colors here that's fine you can change let's make one year green and one ear pink see if that works yeah it seems to work so I can run here and I'll get a green ear in a pink ear woohoo so you can color Mickey if you like any case what I want you to do is convert this code so that instead of drawing Mickey Mouse we get Mickey moose so what's Mickey Mouse Mickey moose is an example of a fractal so fractals are very cool examples of recursion it's essentially a recursive drawing so here's an example online where the fractal is responding to my mouse and you can see here another example of a fractal or a recursive drawing where again it's responding to my mouse there's lots of such examples this is probably the simplest one you can think of a coastline getting more and more complicated as you get closer to it you can see this is sort of recursive because getting more complex and a tree here so these are fun things to mess around with and these are all examples of recursive drawing so recursive drawing is definitely amusing let me see if I can do this I'm going to drag a square over here and I'm gonna use the shift key to change the width of the square and then use no shift key to sort of shrink in a little bit and I think I can move it yeah I can move it down here so I'll just have my little square my rectangle then I can take it and drop so what i'm doing here notice i'm taking this picture and dropping it on itself so this is saying i want to include the picture in itself what you can do then is shrink the picture that you're adding you can move it around so and i might move this a little bit that way say and you end up with something like this and now I can drag drag the picture run itself again and this is where it gets sort of amusing you can edit this where you move the picture around and like that say you get a nice little tree this is a recursive drawing so the drawing includes a sub drawing of itself and it's a rather amusing thing to play around with I'm gonna have you do a really simple version of this which is to figure out how to convert Mickey Mouse to mickey moose and the key here is to replace the drawing of Mickey's ears with a recursive call to the draw his head just smaller right so I've set this up for you so that all you have to do is adjust the positions and the radius to give you an example here you can see how I'm adjusting the positions and the radius in order to draw the ears so think about it try to get your code as simple as possible you should only need your recursive function to draw one circle see if you can make that work the next part of the homework is to run this function called Terabithia Nachi this is terrible Fibonacci loop which runs Fibonacci over and over and over again for larger and larger numbers just run it on your computer for an hour and see where you get you can see here how what's happening on my machine when I get up to fibonacci of 4243 it's pretty slow I mean the early Fibonacci's are really fast but these labor Fibonacci's are very very slow and after about an hour I think I remember what I get up to but it's not super large so let me just terminate that and that's the problem here is just for you to put a comment in here all you do is write in what's the last number you got so just write it in here replace the double dots or the triple dots with the numbers that you got after an hour of running in the final problem is to actually rewrite with terrible Fibonacci to make it more efficient so here you needs a little think a little bit and you can think about in the lecture that I presented the two ways that we looked at the Fibonacci function so one of them was the top down where we had two calls to the terrible Fibonacci but there was a way of thinking about this function in a tabular way where we started at the base case and worked up so think about trying to implement it that way once you've successfully finished the homework the output should look like this you should have a lovely fractal Mickey moose and in addition you should have notification that you've finished all the tests and you should get a printout of the first 100 or so Fibonacci numbers one thing I'll point out is that the Fibonacci numbers get so big that eventually they out run the amount of memory in the machine that's used to store the value of the Fibonacci and you can see on my machine it's right around 92 I run out of room and something weird happens at 93 they go negative this is because of wrap-around in the values so once the values exceed the maximum possible value for integer values they wrap around I actually used a long to represent the return value here so as to delay this wraparound as much as possible with an INT you only get 32 bits which is about 4 billion values half of those are used for positive half or use for negative so you get up to 2 billion and you're done at least here I'm getting up to about 8 quintillion and so but once you get around 8 quintillion it's done and it'll go negative on you good luck with a homework

Read chapter 2 of Core Java for the Impatient.

Skim section 1.3 of Algorithms

Read the subsection on Linked Lists, starting around page 142.

Do the homework assigned on d2l.

One of the problems is to convert mickey mouse:

to mickey moose:

This is an example of a Fractal also known as a Recursive drawing

file:MySecondHomework.java [source] [doc-public] [doc-private]

package algs11;

import java.util.Arrays;
import stdlib.*;

/**
 * This is a skeleton file for your homework. Edit the sections marked TODO. You
 * may add new functions. You may also edit the function "main" to test your
 * code.
 *
 * You must not add static variables. You MAY add static functions, just not
 * static variables.
 *
 * It is okay to add functions, such as
 *
 * <pre>
 *     public static double sumHelper (double[] list, int i, double sumSoFar) {
 * </pre>
 *
 * but it is NOT okay to add static variables, such as
 *
 * <pre>
 * public static int x;
 * </pre>
 *
 * As for homework 1, you must not change the declaration of any method.
 * 
 * You can edit the main function all you want. I will not run your main
 * function when grading.
 */
public class MySecondHomework {

  /**
   * As a model, here is a minValue function, both iteratively and recursively
   */
  /** iterative version */
  public static double minValueI (double[] list) {
    double result = list[0];
    int i = 1;
    while (i < list.length) {
      if (list[i] < result) result = list[i];
      i = i + 1;
    }
    return result;
  }

  /** recursive version */
  public static double minValue (double[] list) {
    return minValueHelper (list, 1, list[0]);
  }
  private static double minValueHelper (double[] list, int i, double result) {
    if (i < list.length) {
      if (list[i] < result) result = list[i];
      result = minValueHelper (list, i + 1, result);
    }
    return result;
  }

  /**
   * PROBLEM 1: Translate the following sum function from iterative to
   * recursive.
   *
   * You should write a helper method. You may not use any "fields" to solve
   * this problem (a field is a variable that is declared "outside" of the
   * function declaration --- either before or after).
   */
  public static double sumI (double[] a) {
    double result = 0.0;
    int i = 0;
    while (i < a.length) {
      result = result + a[i];
      i = i + 1;
    }
    return result;
  }
  public static double sum (double[] a) {
    // TODO
    return StdRandom.uniform ();
  }

  /**
   * PROBLEM 2: Do the same translation for this in-place reverse function
   *
   * You should write a helper method. You may not use any "fields" to solve
   * this problem (a field is a variable that is declared "outside" of the
   * function declaration --- either before or after).
   */
  public static void reverseI (double[] a) {
    int hi = a.length - 1;
    int lo = 0;
    while (lo < hi) {
      double loVal = a[lo];
      double hiVal = a[hi];
      a[hi] = loVal;
      a[lo] = hiVal;
      lo = lo + 1;
      hi = hi - 1;
    }
  }
  public static void reverse (double[] a) {
    // TODO
  }

  /**
   * PROBLEM 3: The following function draws mickey mouse, if you call it like
   * this from main:
   *
   * <pre>
   * draw (.5, .5, .25);
   * </pre>
   *
   * Change the code to draw mickey moose instead. Your solution should be
   * recursive.
   * 
   * Before picture:
   * http://fpl.cs.depaul.edu/jriely/ds1/images/MickeyMouse.png After picture:
   * http://fpl.cs.depaul.edu/jriely/ds1/images/MickeyMoose.png
   *
   * You may not use any "fields" to solve this problem (a field is a variable
   * that is declared "outside" of the function declaration --- either before
   * or after).
   */
  public static void draw (double centerX, double centerY, double radius) {
    // TODO 
    if (radius < .0005) return;

    StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
    StdDraw.filledCircle (centerX, centerY, radius);
    StdDraw.setPenColor (StdDraw.BLACK);
    StdDraw.circle (centerX, centerY, radius);

    double change = radius * 0.90;

    StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
    StdDraw.filledCircle (centerX + change, centerY + change, radius / 2);
    StdDraw.setPenColor (StdDraw.BLACK);
    StdDraw.circle (centerX + change, centerY + change, radius / 2);

    StdDraw.setPenColor (StdDraw.LIGHT_GRAY);
    StdDraw.filledCircle (centerX - change, centerY + change, radius / 2);
    StdDraw.setPenColor (StdDraw.BLACK);
    StdDraw.circle (centerX - change, centerY + change, radius / 2);
  }

  /**
   * PROBLEM 4: Run runTerribleLoop for one hour. You can stop the program
   * using the red "stop" square in eclipse. Fill in the OUTPUT line below
   * with the numbers you saw LAST --- edit the line, replacing the two ...
   * with what you saw:
   *
   * OUTPUT: terribleFibonacci(...)=... // TODO
   *
   * Comment: the code uses "long" variables, which are like "int", but
   * bigger. It's because fibonacci numbers get really big really fast.
   */
  public static void runTerribleLoop () {
    for (int N = 0; N < 100; N++)
      StdOut.format ("terribleFibonacci(%2d)=%d\n", N, terribleFibonacci (N));
  }
  public static long terribleFibonacci (int n) {
    if (n <= 1) return n;
    return terribleFibonacci (n - 1) + terribleFibonacci (n - 2);
  }

  /**
   * PROBLEM 5: The implementation of terribleFibonacci is TERRIBLE! Write a
   * more efficient version of fibonacci. Do not change runFibonacciLoop or
   * runFibonacciSomeValues.
   *
   * To make fibonacci run faster, you want it so that each call to
   * fibonacci(n) computes the fibonacci numbers between 0 and n once, not
   * over and over again.
   *
   * Comment: You will want to use a local variable of type "long" rather than
   * type "int", for the reasons discussed above.
   *
   * Comment: At some point, your fibonacci numbers might become negative.
   * This is normal and expected.
   * http://en.wikipedia.org/wiki/Integer_overflow We discuss this at length
   * in our systems classes.
   *
   * You may not use any "fields" to solve this problem (a field is a variable
   * that is declared "outside" of the function declaration --- either before
   * or after).
   * 
   * You may use a loop on this problem.
   * You do not need to use recursion.
   */
  public static void runFibonacciLoop () {
    for (int N = 0; N < 100; N++)
      StdOut.format ("fibonacci(%2d)=%d\n", N, fibonacci (N));
  }
  public static long fibonacci (int n) {
    return 0; // TODO
  }

  /**
   * A test program, using private helper functions.  See below.
   * To make typing tests a little easier, I've written a function to convert strings to arrays.  See below.
   * You can modify this -- it is not graded.
   */
  public static void main (String[] args) {
    testSum ("11 21 81 -41 51 61");
    testSum ("11 21 81 -41 51");
    testSum ("11 21 81 -41");
    testSum ("11 21 81");
    testSum ("11 21");
    testSum ("11");
    testSum ("");

    testReverse ("11 21 81 -41 51 61");
    testReverse ("11 21 81 -41 51");
    testReverse ("11 21 81 -41");
    testReverse ("11 21 81");
    testReverse ("11 21");
    testReverse ("11");
    testReverse ("");

    testFibonacci (0, 0);
    testFibonacci (1, 1);
    testFibonacci (1, 2);
    testFibonacci (2, 3);
    testFibonacci (21, 8);
    testFibonacci (233, 13);
    testFibonacci (75025, 25);
    testFibonacci (             1_836_311_903L, 46);
    testFibonacci (             2_971_215_073L, 47);
    testFibonacci (       308_061_521_170_129L, 71); 
    testFibonacci (       498_454_011_879_264L, 72);
    testFibonacci ( 7_540_113_804_746_346_429L, 92);
    testFibonacci (-6_246_583_658_587_674_878L, 93);
    testFibonacci (  -813_251_414_217_914_645L, 376);
    StdOut.println ("Finished tests");

    draw (.5, .5, .25);

    // TODO: uncomment these temporarily when you want to see the output of your Fibonacci functions
    //runTerribleLoop (); 
    //runFibonacciLoop();   
  }
  
  /*
   * A main function for debugging -- change the name to "main" to run it (and
   * rename the existing main method to something else). Change the test as
   * appropriate.
   */
  public static void main1 (String[] args) {
    Trace.drawStepsOfMethod ("minValueI");
    Trace.drawStepsOfMethod ("minValue");
    Trace.drawStepsOfMethod ("minValueHelper");
    Trace.run ();
    testMinValue ("11 21 9 31 41");
  }

  /* Test functions --- lot's of similar code! */
  private static void testSum (String list) {
    double[] aList = doublesFromString (list);
    double expected = sumI (aList);
    double actual = sum (aList);
    if (! Arrays.equals (aList, doublesFromString (list))) {
      StdOut.format ("Failed sum([%s]): Array modified\n", list);
    }
    if (expected != actual) {
      StdOut.format ("Failed sum([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
    }
  }
  private static void testMinValue (String list) {
    double[] aList = doublesFromString (list);
    double expected = minValueI (aList);
    double actual = minValue (aList);
    if (! Arrays.equals (aList, doublesFromString (list))) {
      StdOut.format ("Failed minValue([%s]): Array modified\n", list);
    }
    if (expected != actual) {
      StdOut.format ("Failed minValue([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
    }
  }
  private static void testReverse (String list) {
    double[] expected = doublesFromString (list);
    reverseI (expected);
    double[] actual = doublesFromString (list);
    reverse (actual);
    // != does not do what we want on arrays
    if (! Arrays.equals (expected, actual)) {
      StdOut.format ("Failed reverse([%s]): Expecting (%s) Actual (%s)\n", list, Arrays.toString (expected), Arrays.toString (actual));
    }
  }
  private static void testFibonacci (long expected, int n) {
    long actual = fibonacci (n);
    if (expected != actual) {
      StdOut.format ("Failed fibonacci(%d): Expecting (%d) Actual (%d)\n", n, expected, actual);
    }
  }

  /* A utility function to create an array of doubles from a string. */
  // The string should include a list of numbers, separated by single spaces.
  private static double[] doublesFromString (String s) {
    if ("".equals (s)) return new double [0]; // empty array is a special case
    String[] nums = s.split (" ");
    double[] result = new double[nums.length];
    for (int i = nums.length-1; i >= 0; i--) {
      try { 
        result[i] = Double.parseDouble (nums[i]); 
      } catch (NumberFormatException e) { 
        throw new IllegalArgumentException (String.format ("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
      }
    }
    return result;
  }
}

Revised: 2008/03/17 13:01