CS111 Spring 2012

Problem Set 4

Due *Friday* 24 February 2012

Due Date

Because of the President's Day holiday on Monday Feb. 20, this assignment will be due on Fri, Feb. 24 at 5pm rather than on Tuesday, Feb. 21. This week drop-in hours will be on Wednesday and Thursday nights; there will be no Sunday or Monday night drop-ins this week.

Reading

Review the slides from the Introduction to PictureWorld and Divide/Conquer/Glue in Picture World lectures and the problems from Lab 4. Additionally, study these contracts:

About this Problem Set

In this problem set, you will practice reading, writing, and understanding fruitful methods. Task 1 exercises your understanding of fruitful PictureWorld methods through invocation trees. In Tasks 2 and 3, think carefully about what patterns should be abstracted into methods and which patterns should be named as variables. In Task 4, you will write a Java application from scratch with class methods for calculating your CS111 course grade.

Task 1 (Invocation Tree) and Task 3 (QuiltWorld) are tasks on which you are *required* to work in pairs. On these two tasks (but not the others) you must work with a partner. You may choose a different partner from previous psets or choose one you have worked with before.

To get the code for this assignment, connect to the cs server via Fetch or WinSCP. Use the cs111d account and the password given in class and download the ps04_programs folder.

This problem set will be graded using this grade sheet.

How to turn in this Problem Set

You must turn in both a hardcopy and a softcopy. For general guidelines on problem set submission, including how to submit a softcopy and how to check if you softcopy submission was successful, click here. Please make sure to keep a copy of your work, either on an external storage device (like a USB drive), or in your private directory (or, to play it safe, both).

Hardcopy Submission

Your hardcopy packet should consist of:

  1. The cover page;
  2. Your Object Land and Invocation Tree drawing from Task 1 (Only one member of a team should submit this drawing. The other member should indicate on their cover sheet that their partner submitted it. The drawing itself should list the names of both team members.);
  3. Your modified KnitWorld.java file from Task 2;
  4. Your modified QuiltWorld.java file from Task 3. (Only one member of a team should submit this file. The other member should indicate on their cover sheet that their partner submitted it. The top comment on the file should list the names of both team members.)
  5. Your Grades.java file from Task 4.

Staple these together, and submit the packet by 5pm on the due date.

Softcopy Submission

Save the modified KnitWorld.java and QuiltWorld.java files in the ps04_programs folder. Also, save your Grades.java file in the ps04_programs folder. Submit the entire ps04_programs folder to your drop folder on the CS111 server. (Only the team member who submitted the hardcopy of QuiltWorld.java need submit the softcopy.)

PictureWorld Examples

To demonstrate some of the capabilities of PictureWorld, we have included the file MyPictureWorld.java in the ps04_programs folder you downloaded. You can compile the file and run the program if you are interested. This file has lots of examples of Picture manipulations. You are not required to do anything with this file for the assignment. We have included it only because it demonstrates lots of Picture examples. Most of the examples are commented out so that the menu of the applet is not cluttered, but feel free to un-comment whatever examples you are interested in experimenting with. (This file is essentially the same as the SimplePictureWorld.java file we studied in the first PictureWorld lecture.)

Task 1: PictureWorld Invocation Tree

This is a task on which you are *required* to work in pairs. On this task and Task 3 (but not other tasks) you must work with a partner. All work by a team must be a true collaboration in which members actively work together on all parts of the Task. It is not acceptable for team members to split up the tasks and work on parts independently.

As discussed in lecture, an invocation tree is a summary of all the frames created in ExecutionLand within the Java Execution Model. It contains a node for each method called during the execution of a program (even "black-box" methods like forward and left in BuggleWorld and clockwise90 and above in PictureWorld). Each node contains the receiver of the method invocation, the name of the method, the values of its arguments, and (where applicable) its result. There is an edge connecting each "parent" node to the "children" nodes for the method invocations performed directly within the body of the parent. The children nodes for a given parent are stacked vertically, arranged from top to bottom in the order of their execution.

First Example

As a first example, consider the execution of fourSame(leaves), where leaves denotes the two-green-leaves pattern presented in class and fourSame is defined as follows:

    public Picture fourSame (Picture p) {
        return fourPics(p, p, p, p);
    }

    public Picture fourPics (Picture p1, Picture p2, Picture p3, Picture p4) {
        return above(beside(p1,p2), beside(p3,p4));
    }

Below is a JEM for this example in which Object Land shows all the objects created and Execution Land shows an invocation tree of all execution frames created during the evaluation fourSame(leaves). The object label SPW stands for the SimplePictureWorld object that receives the method invocation and PIC1 denotes the leaves Picture object. Each node contains the value of the receiver, followed by the method name, followed by the argument values enclosed in parentheses. The result of invoking the method is then shown after a colon. Note that the nodes at the same level are drawn from top to bottom in the order that the methods are invoked.

Second Example

As a second example of an invocation tree, consider the execution of rotations(gw), where gw denotes the green wedge pattern presented in class and rotations is defined as follows:

    public Picture rotations (Picture p) {
        return fourPics(clockwise270(p), p, clockwise180(p), clockwise90(p));
    }

As shown below, this invocation involves a PictureWorld object (SPW) seven picture objects (PIC1 through PIC7), and eight execution frames.

The body of rotations invokes four methods (clockwise270, clockwise180, clockwise90, and fourPics), so nodes for these four invocations are stacked vertically as children of rotations. Similarly, fourPics invokes three methods (two invocations of beside and one of above), so nodes for these three invocations are stacked vertically as children of fourPics.

Your Task

In this problem, you will draw both Object Land and an invocation tree for the invocation tents(gw), where gw is the green wedge pattern from above and tents is a SimplePictureWorld method defined as follows: 

    public Picture tents (Picture p) {
        return tent(tent(p));
    }   

    public Picture tent (Picture p) {
       Picture p90 = clockwise90(p);
       return above(p, beside(flipHorizontally(p90), p90));
    }

Your Object Land should show a SimplePictureWorld object SPW, the Picture object for the green wedge, and every Picture object created in the invocation tents(gw). To represent a Picture object, you should sketch the picture represented by that object within a square and give it an object label enclosed in an oval (e.g PIC1, PIC2, etc.), as in the above examples.

As in the above examples, your invocation tree should have one boxed node for each execution frame created during the evaluation of tents(gw), including frames for "black-box" PictureWorld methods like clockwise90, flipHorizontally, beside, and above. Each boxed node should show:

  1. the object label for the receiver of the method, followed by a dot;
  2. the name of the invoked method;
  3. the object labels for all method arguments, delimited by parenthesis and separated by commas;
  4. and the object label for the result value returned by the method invocation, following a colon.

The nodes for all methods invoked directly within the body of another method should be drawn to the right of the other method and stacked vertically, from top to bottom in the order they are invoked. A line should connect a method invocation node to the nodes of each method invoked within it.

You should label the part of your drawing containing the Picture objects "Object Land" and the part that contains the invocation tree "Execution Land". You may have trouble fitting both lands on a single piece of paper, so feel free to put Object Land on one and the invocation tree on another.

Task 2: Knit Picking

Escher's Knitting Patterns

Dutch artist M. C. Escher is renowned for creating artwork based on interlocking patterns and visual playfulness. Here we will experiment with knitting patterns that Escher himself experimented with in 1943. (For more details on Escher's artwork, see M.C. Escher: Visions of Symmetry by Doris Schattschneider, W.H. Freeman and Company, 1990).

Escher's knitting patterns were based on the following two primitive patterns that he designed:


Pattern A


Pattern B

We will call these patterns A and B. We can make many variants of A an B by rotating them, flipping them, and painting their stripes different colors. These variants of A and B can be combined to form an amazing number of patterns that resemble the weave patterns of knitted yarn. For example, study the following four knitting patterns, all of whose basic squares are versions of A and B that have been rotated, flipped, and colored in various ways.

Playing with Knitting Patterns in PictureWorld

PictureWorld is a perfect tool for experimenting with Escher's knitting patterns. The file KnitWorld.java in the ps04_programs folder contains several methods that aid in this experimentation. Colored versions of the A and B patterns are created by the following two black-box methods in KnitWorld.

public Picture tileKnit (Picture p1, Picture p2, Picture p3, Picture p4) 
{
    return fourSame(fourSame(fourPics(p1, p2, p3, p4)));
}

The fourSame() and fourPics() methods are as presented in lecture and lab:

public Picture fourSame (Picture p) 
{
    return fourPics(p, p, p, p);
}

public Picture fourPics (Picture p1, Picture p2, Picture p3, Picture p4) 
{
    return above(beside(p1, p2), beside(p3, p4));
}

Using the above methods, plus the usual picture combinators of PictureWorld, it is possible to make pictures for all four knitting patterns shown above. Here is a knit1() method, parameterized over two colors, that generates the knit1 pattern shown above:

public Picture knit1(Color c1, Color c2) 
{
    Picture A1 = A(c1, c2, c1, c1, c2);
    Picture B1 = B(c2, c1, c2 ,c2, c1);

    return tileKnit(A1, B1, A1, B1);
}

The knit2() method is similiar in structure to knit1(), but uses different colorings, flips, and rotations:

public Picture knit2(Color c1, Color c2) 
{
    Picture A1 = A(c1, c2, c1, c2, c1);
    Picture B1 = B(c2, c1, c2 ,c1, c2);

    return tileKnit(flipVertically(B1),
                    flipVertically(A1),
 	            clockwise180(B1),
		    clockwise180(A1));
}

The knit3() method is parameterized over three colors rather than two:

public Picture knit3(Color c1, Color c2, Color c3) 
{
    return tileKnit(B(c1, c2, c1, c3, c1),
                    clockwise90(B(c1, c3, c2, c2, c1)),
                    flipHorizontally(B(c1, c3, c1, c2, c1)),
                    flipHorizontally(clockwise90(A(c1, c2, c3, c3, c1))));
}

The knit4 pattern has a more complex repetition pattern than can be described by tileKnit(). Two alternative knit4() methods are shown below. Both methods produce identical pictures. The first uses 12 local variables to refer to the various intermediary pictures that are generated while constructing the final picture pattern. The second uses only 2 local variables to refer to intermediary pictures, instead preferring to nest expressions by having fruitful method invocations, which return Picture objects, serve as arguments to other methods with Picture parameters. The two alternative methods for capturing the knit4 pattern represent two different problem solving approaches that achieve the same result. 

public Picture knit4(Color c1, Color c2)
{
    Picture A1 = A(c1, c2, c1, c1, c2);
    Picture B1 = B(c1, c2, c1, c2, c1);
    Picture A2 = A(c2, c1, c2, c1, c2);
    Picture B2 = B(c2, c1, c2, c2, c1);

    Picture A1_clockwise270 = clockwise270(A1);
    Picture A1_flipDiagonally = flipDiagonally(A1);
    Picture B1_flipHorizontally = flipHorizontally(B1);
    Picture B2_flipDiagonally = flipDiagonally(B2);
    Picture B2_clockwise270 = clockwise270(B2);
    Picture A2_flipHorizontally = flipHorizontally(A2);
    
    Picture tile1 = fourPics(B1, A1_clockwise270, B1_flipHorizontally, B2_flipDiagonally);
    Picture tile2 = fourPics(A2, B2_clockwise270, A2_flipHorizontally, A1_flipDiagonally);

    return fourSame(fourPics(tile1, tile2, tile1, tile2));
}
public Picture knit4_alternative(Color c1, Color c2) 
{
    Picture tile1 = fourPics(B(c1, c2, c1, c2, c1),
                             clockwise270(A(c1, c2, c1, c1, c2)),
                             flipHorizontally(B(c1, c2, c1, c2, c1)),
                             flipDiagonally(B(c2, c1, c2, c2, c1)));
    Picture tile2 = fourPics(A(c2, c1, c2, c1, c2),
                             clockwise270(B(c2, c1, c2, c2, c1)),
                             flipHorizontally(A(c2, c1, c2, c1, c2)),
                             flipDiagonally(A(c1, c2, c1, c1, c2)));

    return fourSame(fourPics(tile1, tile2, tile1, tile2));
}

Your Task

In this problem, you will define a method that draws the knit5 knitting pattern. knit5() is parameterized over four colors. The particular knit5 patterns shown below are created by the invocation that you can read in the top of the KnitWorld picture (in the yellow bar at the top of the image). For example, the top left knit5 pattern in created by this invocation: knit5(Color.red, Color.magenta, Color.blue, Color.green).

Add your definition of the following method to the file KnitWorld.java: 

public Picture knit5(Color c1, Color c2, Color c3, Color c4);

Be sure to uncomment the menu items for knit5() in the initializePictureChoices() method so you can test your code!

To begin this problem, first study the knit1() through knit4() methods above and convince yourself that they do in fact draw the four knitting patterns shown in the previous section. Your solution to knit5() will be similar to the knit1() through knit4(). Next, you should carefully study the knit5 pattern to determine which rotations, flips, and colorings of the basic patterns A and B are employed. The final step is to encode your findings in Java in the your knit5() method. You may find it helpful to define your own auxiliary methods in addition to defining knit5().

Testing your program

To make testing a little easier, we have included a folder Test which contains working examples of the patterns you need to make so that you can compare your work with the examples (but, alas, no Java code!). There are two different ways to see the examples.

  1. Use your web browser to open the file KnitWorldSoln.html in the Test folder that you downloaded with ps04_programs. You can choose knit5 and knit6 from the menu to compare these examples with your own work.
  2. In Dr. Java, open the file CS111.txt in the Test folder that you downloaded with ps04_programs, click on the Interactions tab at the bottom of the Dr. Java window and type java KnitWorldSoln in the Interactions pane.

Ungraded Challenge

Do not attempt this problem until you have finished the entire problem set.

Write a knit6() method that behaves as shown below.

Task 3: QuiltWorld

This is a task on which you are *required* to work in pairs. On this task and Task 1 (but not other tasks) you must work with a partner. All work by a team must be a true collaboration in which members actively work together on all parts of the Task. It is not acceptable for team members to split up the tasks and work on parts independently.

Blithe Buggle, co-founder of the Buggle Bagel Ruggle Company, has been looking for new ways to expand her company's product line. Although the bagel rugs marketed by the company are popular, they are difficult to manufacture because of the labor costs (each rug is hand-drawn by a Buggle) and and raw material costs (bagels cost more than you think!). Blithe thinks the company should diversify to produce other products with interesting designs, such as quilts,wallpaper, and sweaters. Blithe is currently experimenting with the picture drawing software presented in CS111 to design quilts. Here is an example of one of Blithe's quilt designs, which we will call quilt1.


quilt1()

You and several other CS111 students have been hired as interns at the Buggle Bagel Ruggle Company to help Blithe design quilts. Your project is to use PictureWorld to generate the quilt design shown above. The quilt above is just one sample of the quilt design. Your code will contain methods that take color parameters, and therefore your code will be able to generate lots of different quilts, in the same pattern as above, but with color variation. This description of the assignment will use the quilt above as an example, but keep in mind that your code must be generic and able to handle different color variations of the above pattern. There is a file called QuiltWorld.java in the ps04_programs folder. All the methods that you will define for this problem will be in the QuiltWorld class. Your goal is to flesh out the skeleton of the quilt1() method so that it returns a picture corresponding to the quilt shown above. This picture is ultimately generated by combining primitive pictures generated by the following two black-box methods:

public Picture patch (Color c)
Returns a rectangular patch of color c with a black border that fills a given picture frame.

public Picture triangles(Color c1, Color c2)
Returns a picture that consists of two triangles filling the given picture frame: a black-bordered triangle of color c1 in the lower left corner of the frame; and a black-bordered triangle of color c2 in the upper right corner of the frame.

For example, below are the pictures generated by some sample invocations of these methods:


patch(Color.red);


triangles(Color.red, Color.blue);

Divide, Conquer, and Glue

The key to solving the problem of defining quilt1() is to note that the picture can be decomposed into smaller pictures that are used more than once in the larger picture. For example, the upper right quadrant is a picture that we'll call corner:


corner(Color.red, Color.blue, Color.green, Color.darkGray, Color.cyan, Color.magenta)

The whole picture can be decomposed into four copies of corner that have different rotations. Once we figure out how to define the corner picture, we can combine four rotated copies of the picture to form the desired quilt picture. This is an excellent illustration of the divide, conquer, and glue problem solving strategy we will use throughout this course:

  1. Divide the problem into subproblems. Here there is one subproblem: defining corner().
  2. Conquer the subproblems by solving them. In this case, the solution to the subproblem is a picture named corner.
  3. Glue the solutions to the subproblems together to form the solution to the whole problem. Here, we combine four rotated versions of corner to construct our quilt.

But how do we solve the problem of defining the corner picture? By applying the divide, conquer, and glue strategy again! In this case, you should decompose the corner picture itself into four quadrants. You can define methods quadrant1(), quadrant2(), etc. Of course, the methods will take appropriate parameters.

Continue this way, decomposing each problem into smaller subproblems, until you reach problems that can be solved using our primitives (e.g., patch() and triangle()).

Auxiliary Methods

A general principle of computer science is “never write any piece of code more than once.” If you find yourself writing the same or similar code more than once in your program, you should write methods that capture the patterns of the repeated code and invoke the methods instead.

The divide, conquer, and glue process of defining quilt1() naturally exposes the need for numerous auxiliary methods. As part of working on this assignment, define and use the following methods (insert the definitions under the "Auxiliary methods" comment in QuiltWorld.java).

public Picture patch_2x2 (Color c)
Returns a picture consisting of four rectangular patches of color c with black lines between the patches. (Remember that patch(c) returns a picture with a black border.)

public Picture triangles_2x2 (Color c1, Color c2)
Returns a picture similar to triangles(c1, c2) except that each large triangle is composed out of three smaller fragments (two triangles and a rectangle).

public Picture LL (Picture p)
Returns a picture which divides the picture space into four quadrants and places the given picture in the lower left corner.

public Picture LLNest (Picture p1, Picture p2)
Returns a picture which places picture p2 over the lower left corner of picture p1.

As you implement these methods, uncomment out the corresponding items in initializePictureChoices() to test them!

Here are example invocations of the four methods above:


patch_2x2(Color.red);


triangles_2x2(Color.red, Color.blue);


LL(triangles(Color.red, Color.blue));


LLNest(patch(Color.red), triangles(Color.red, Color.blue));

Completing the Assignment

All of the methods in the PictureWorld and QuiltWorld contracts are available to you. At a minimum, you should have methods that correspond to each pattern shown above. In addition to that, you should define additional methods which capture patterns that are used over and over again. It is also helpful to define local variables within your methods to give names to pictures that you generate as part of your solution.

Given the patterns and auxiliary methods specified above, all the quadrants (quadrant1(), etc.) should be very simple.

Each of your methods should be short: no more than a few statements long (say 5 or 6). If you find yourself defining a longer method, consider how you can break it up into smaller parts (preferably in a way that permits one or more of the smaller of the methods to be used multiple times).

Testing your program

To make testing a little easier, we have included a folder Test that contains working examples of the patterns you need to make so that you can compare your work with the examples (but, alas, no Java code!). There are two different ways to see the examples.

  1. Use your web browser to open the file QuiltWorldSoln.html in the Test folder that you downloaded with ps04_programs. You can choose components of your design, such as corner, quadrant1, LL or LLNest to compare them to your work.

  2. In Dr. Java, open the file CS111.txt in the Test folder that you downloaded with ps04_programs, click on the Interactions tab at the bottom of the Dr. Java window and type java QuildWorldSoln in the Interactions pane.

Your final Task.

Oh no! Blithe has just designed this new quilt shown below, using the same pattern as above, but with different colors. She forgot how she actually created this one. She hires you to figure out which Color parameters were used in what order to create the pattern below. To solve this problem, write a new method called quilt2() that produces the quilt shown below.

quilt2()

Task 4: An Application to Calculate Your CS111 Grade

Important note: Before you begin working on the fourth task, make sure to save and close all Java files from the previous task.

In this task, you will write an application, named Grades, from scratch. The application will calculate your final grade in CS111 based on your homework and exam scores. Of course, you have not yet received all of your homework and exam scores, so you are free to make up whatever scores you like for each assignment and exam. Based on ten homework scores and three exam scores, your application should print out (i.e., using System.out.println) your final score (between 0.0 and 100.0) in the course and your final letter grade (e.g., C+ or A). (Note: We usually grade your psets on a scale 0.0 to 50.0, but the pset scores for this task should be in the range 0.0 to 100.0; so you'll need to double your actual pset scores for this application.)

Your Grades class should contain the following five class methods: 


    /**************************************************************************
     Given scores (between 0.0 and 100.0) on ten problem sets, 
     returns the average of those ten scores. 
    **************************************************************************/
    public static double psetAverage(double ps1, double ps2, double ps3,
				     double ps4, double ps5, double ps6,
				     double ps7, double ps8, double ps9,
				     double ps10)

For example, here is a test of psetAverage in the Dr. Java Interaction pane: 

> Grades.psetAverage(90.0, 94.0, 100.0, 84.0, 87.0, 92.0, 100.0, 77.5, 100.0, 81.3)
90.58



    /**************************************************************************
     Given scores (between 0.0 and 100.0) for a problem set average and three 
     exams, returns a final score in the course. 
     * The problem sets contribute 0.40 to the final score.
     * The first exam contributes 0.15 to the final score.
     * The second exam contributes 0.25 to the final score.
     * The final exam contributes 0.20 to the final score.
    **************************************************************************/
    public static double courseScore(double psetAvg, double exam1, 
				     double exam2, double examFinal)

For example, here is a test of courseScore in the Dr. Java Interaction pane: 

> Grades.courseScore(90.58, 82.0, 86.5, 91.0)
88.357


    /**************************************************************************
     Given a final score (between 0.0 and 100.0) in the course,
     the method returns a String representing the corresponding
     letter grade for the final score. A score:
       >= 93.33 results in a letter grade of "A".
       >= 90.00 results in a letter grade of "A-".
       >= 86.67 results in a letter grade of "B+".
       >= 83.33 results in a letter grade of "B".
       >= 80.00 results in a letter grade of "B-".
       >= 76.67 results in a letter grade of "C+".
       >= 73.33 results in a letter grade of "C".
       >= 70.00 results in a letter grade of "C-".
       >= 60.00 results in a letter grade of "D".
       < 60.00 results in a letter grade of "F".
     **************************************************************************/
    public static String letterGrade(double score)

For example, here is a test of letterGrade in the Dr. Java Interaction pane: 

> Grades.letterGrade(88.357)
"B+"


    /**************************************************************************
     Given scores (between 0.0 and 100.0) on ten problem sets and three exams, 
     displays (1) the ten pset scores, (2) the pset average, (3) the three exam
     scores, (4) the course score and (5) the letter grade. 
    **************************************************************************/
    public static void printGrades(double ps1, double ps2, double ps3,
			          double ps4, double ps5, double ps6,
			          double ps7, double ps8, double ps9,
			          double ps10, double exam1, double exam2,
			          double examFinal)

For example, here is a test of printGrades in the Dr. Java Interaction pane: 

> Grades.printGrades(90.0, 94.0, 100.0, 84.0, 87.0, 92.0, 100.0, 77.5, 100.0, 81.3, 82.0, 86.5, 91.0);
Your ten pset scores are:
    90.0, 94.0, 100.0, 84.0, 87.0, 92.0, 100.0, 77.5, 100.0, 81.3
Your pset average is 90.58.
Your first midterm exam score is 82.0.
Your second midterm score is 86.5.
Your final exam score is 91.0.
You earned a course score of 88.357, which results in a letter grade of B+.


    /**************************************************************************
     For a given collection of ten problem set scores and three exam scores
     (which you choose), displays (1) the ten pset scores, (2) the pset average,
     (3) the three exam scores, (4) the course score and (5) the letter grade. 
    **************************************************************************/
    public static void main (String [] args)

The main method is tested by running the application in the Dr. Java Interaction pane. Here is one example: 

> java Grades
Your ten pset scores are:
    100.0, 92.0, 89.0, 84.0, 80.0, 85.0, 91.0, 79.0, 87.0, 85.0
Your pset average is 87.2.
Your first midterm exam score is 92.0.
Your second midterm score is 80.0.
Your final exam score is 88.0.
You earned a course score of 86.28, which results in a letter grade of B.

Happy Programming!