Take-Home Exam 2

Instructions

• This is a take-home exam. It has three tasks, all of which require writing Java programs. The problems are independent of one another, and you can do them in any order you find convenient.
• Code that does not compile or load properly will receive a substantial deduction. At this point in the semester, you should be able to get your code to compile. If you have gotten a partial solution to work and run out of time, then comment out any code that doesn't compile and submit the last version that did compile. You may receive some credit for a strategy described in comments and commented out code.
• This exam is open book, in the sense that you can consult any books, handouts, or notes to solve the problems. However, you may not consult solutions for exams or problem sets used in previous semesters of CS111. Mark and Stella are the only people with whom you can talk about (or send email to concerning) the exam. You may not communicate in any form with any other person about this exam. On the exam cover sheet, you are required to sign a statement verifying that you have followed this policy. Any violations of this policy will be brought before the General Judiciary. We really wish we didn't have to say all this, but almost every semester we have a take-home exam, we catch CS111 students who cheat on it. The punishment for all such students was failing the course. Some of those students requested that we include this explicit warning on future exams so you would not suffer their fate.
• You are welcome to privately (in person or via phone or email) ask Mark or Stella any questions you have about the exam. We can clarify the problems if you have trouble understanding them, but because this is an exam, we cannot help you solve the problems. We may choose not to answer a question; but if we do answer a question, we will share that answer with the whole class by posting an announcement on the CS111-S08 Announcements FirstClass conference. Be sure to check this conference regularly for late-breaking announcements about the exam.
• All code for this exam can be found in the exam2_programs directory in the CS111 download folder on the CS111 server.

Submitting Your Exam

In each task, you will be writing Java code. In Task 3, part D, you are also asked to draw an iteration table.

• You must submit a soft copy of all your Java code code in your exam2 drop folder by the deadline on the syllabus. Do not submit anything after this time! Your softcopy submission should consist of your final versions of your StarWorld, BagelMapperWorld, and Primality, folders. Please upload these as separate folders in your exam2 drop folder.
• You must submit a hardcopy of your exam under Mark's door (SCI-E120) by the posted deadline. Your hardcopy packet should consist of:
  1. Your signed cover sheet for the exam.
  2. A printout of your final version of StarWorld.java from Task 1.
  3. A printout of your final version of BagelMapperWorld.java from Task 2.
     
  4. A printout of your final version of Primality.java from Task 3.
     
  5. The iteration table from from Task 3, part D.
• The hardcopy and the softcopy code solutions must match.
• Please scan your hardcopy submission to make sure that no lines of code you have written fall off the end of the page. If lines of your code are truncated because they are too long, please reformat your code and reprint your hardcopy.
• As always, you are responsible for maintaining backup copies of all your work on this exam, including your iteration table..

Advice

• If you can't solve a problem completely, turn in whatever work you have done for partial credit. You can receive partial credit by:
  • clearly explaining what works and what doesn't;
  • explaining why the non-working aspects don't work;
  • explaining in English any solution strategies that you were not able to successfully express in your diagrams or in working code.
• Rather than doing all your work on a single copy of a program, always keep a copy of your best program(s) so far, i.e., implement and debug a piece, then save a copy of the file before working on the next part. When you have debugged another part, save that version as the last best version before moving on. That way, if some of your changes don't work out, you have a "stable" copy to return to. Of course, you should submit your best version. Experimental/non-working code should be commented out with explanation or placed in another file (mentioned in comments of your stable file). Submitting only code that doesn't compile will receive substantial deductions.

---

Task 1: StarWorld [20 points]

In this problem you will explore recursion in PictureWorld. In the exam2_programs directory, you will find a file StarWorld.java (in the StarWorld directory), which you are to edit. Specifically, add a method to StarWorld.java whose prototype is:

public Picture  makeStarPyramid(Color c1, Color c2, int levels);

Define this recursive method to create the patterns shown below. Notice that in the file there is one primitive defined for you, which draws a star as shown below:

Pyramids built from the star pattern are shown below:

When the level is 0 (zero), the picture should be empty. Note that in the file StarWorld.java, the method invocations to create these pyramids have already been included for you. All you need to do is fill in the body of the method makeStarPyramid() such that it generates the pictures above. You may use methods from the PictureWorld contract. You do not need to define any other auxiliary methods in your solution.

---

Task 2: BagelMapper [45 points]

Background

Magellan Buggle is an explorer who wanders about the grid searching for new bagels to consume. As he goes, he creates a map of the grid to record the locations of all the bagels. Since map-making requires lots of energy, Magellan eats every bagel in the grid in the process of making the map. He leaves behind a colored square in every cell where there used to be a bagel.

Assume that Magellan always explores the grid by starting in its southwest corner facing east. For instance, here is a snapshot of Magellan before he maps a rich bagel field on the island of Bago Bago:

Magellan poised to map a field of tasty bagels.

Below is a picture of the same field after Magellan has mapped it. He has eaten every bagel and left behind a patch of his color (which happens to be red) in every cell where there used to be a bagel. (If Magellan were instead blue, he would leave a blue patch.)

The state of the bagel field after Magellan has mapped it.

The map that Magellan creates is printed on the console as a sequence of IntLists. For the above example, Magellan's printed map is shown below. Notice that the first line ([5, 1, 0, 1, 1, 1, 1]) in the map below shows the mapping of the base row of the grid, i.e., the row where the buggle starts out:

[5, 1, 0, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 0, 0]
[1, 0, 0, 0, 0, 1, 0]
[3, 0, 0, 0, 1, 1, 1]
[3, 1, 1, 0, 0, 0, 1]
[6, 1, 1, 1, 1, 1, 1]
map whole grid:  18

The integers in the map can be understood with the help of the color-coding shown below:

5	1	0	1	1	1	1
0	0	0	0	0	0	0
1	0	0	0	0	1	0
3	0	0	0	1	1	1
3	1	1	0	0	0	1
6	1	1	1	1	1	1

• The yellow cells, which contain either 0 or 1, indicate the original locations of bagels in the field. A 0 indicates a cell with no bagel and a 1 indicates a cell with a bagel. The first (top) row of numbers corresponds to the bottom row of the field (the first row mapped), the second row of numbers corresponds to the second row of the field from the bottom, and so on.
• The magenta cells on the far left indicate the total number of bagels in each row. Thus, the first row has 5 bagels, the second row has 0 bagels, etc.

After the maps of each row print out, the total number of bagels in the entire grid is printed.

As a second concrete example, consider another 6×6 field with 20 bagels:

A second tempting field of bagels before mapping.

The second field after mapping.

The map of the second field. [3, 0, 0, 1, 0, 1, 1] [5, 1, 1, 1, 1, 0, 1] [5, 1, 1, 0, 1, 1, 1] [1, 0, 0, 0, 1, 0, 0] [1, 0, 0, 1, 0, 0, 0] [5, 1, 1, 1, 0, 1, 1] map whole grid: 20

Some General Notes:

• Before attempting the tasks of this problem, you should first experiment with the code in the Test subdirectory of the BuggleMapper directory. Executing the applet by loading BuggleMapperWorld.html into a browser or by running BuggleMapperWorld.class creates a BuggleWorld window and a parameter window that allows you to specify the number of rows and columns and the number of bagels in the BuggleWorld window. Pressing the Reset button in the BuggleWorld window will modify the the BuggleWorld grid to be consistent with the parameters. Pressing Run will create a red buggle (Magellan) pointing east with its brush up in the lower left corner of the grid and then cause Magellan to map the grid. Magellan's map will be printed out in the Java console window.
• In the following tasks, you will write methods that implement Magellan's bagel mapping process. You will create a BagelMapper class in the file BagelMapperWorld.java in the BagelMapper directory.
• Since the methods manipulate IntLists, you will have to write IntList. (or IntListOps.) before the various list methods you use. If you would like to abbreviate this to IL, you may include the declaration:

   private static IntListOps IL; // Used to access IntList class methods

  That will give you access to all the IntList and IntListOps methods listed below:

  IntList Methods (IL)
  IL.empty() IL.prepend() IL.head() IL.tail() IL.isEmpty() IL.toString() IL.fromString() IL.length() IL.append() IL.postpend() IL.reverse()

Task 2a: mapRow()

Define the following instance method in the BagelMapper class:

public IntList mapRow()
If (1) the buggle is c cells away from the wall that is in the direction it is headed (counting the cell the buggle occupies) and (2) these c cells contain b bagels, then invoking mapRow() engenders the following behavior:

• The buggle eats all b bagels under and in front of it, and paints each cell formerly containing a bagel with the buggle's color.
• After mapRow() returns, the state of the buggle should be exactly the same as it was before mapRow() was invoked.
• The method returns (but does not print) an integer list with c + 1 elements, where the first element is b and the other c elements are a "map" of 0s and 1s indicating the former positions of the b bagels as described above.

Notes:

• You may define mapRow() as a (non-tail) recursion or as an iteration, whichever you find easier.
• mapRow() does not print out anything. It just computes and returns a list that maps the row.
• Feel free to define any auxiliary methods you find helpful.
• Don't forget to prefix each list method with IL. or IntList..
• To test your mapRow() method, you can add the following line to the run() method of the BagelMapperWorld class. (Be sure to remove or comment out this line before you test the next method, mapGrid()).

  System.out.println("Map of first row: " + magellan.mapRow());

• If you cannot satisfy all of the specifications of mapRow(), do what you can for partial credit. For instance, you can receive partial credit for just eating the bagels and leaving behind the colored patches without returning a non-trivial map. You can also receive partial credit if you return the part of the map that contains 0s and 1s but not the sum.

Task 2b: Recursive mapGrid()

Define the following instance method in your BagelMapper class:

public int mapGrid()
If

1. the buggle is in cell (1, 1) of the buggle grid facing east;
2. the eastern wall is c cells away from the buggle (including the cell the buggle is in);
3. there are b bagels in the c × r subgrid defined by the position of the buggle and the eastern and northern walls.

Then invoking mapGrid() engenders the following behavior:

• The buggle eats all b bagels in the c x r subgrid. and paints each cell formerly containing a bagel with the buggle's color.
• For each row (starting at the bottom), mapGrid() prints out the list generated by mapRow() for that row.
• The method returns (but does not print out) an integer corresponding to the total number of bagels in the grid.
• After mapGrid() returns, the buggle should be at its starting position, i.e., the start of the bottom row of the grid.

Notes:

• You must define mapGrid() as a recursive method for this part.
• Feel free to define any auxiliary methods you find helpful.
• Use mapRow() in your definition of mapGrid().
• Don't forget to prefix each list method with IL..
• Add the following line to the BagelMapperWorld's run() method:

  System.out.println("map whole grid: " + magellan.mapGrid());

  (Be sure to first remove or comment out any lines that test mapRow() before testing mapGrid().)
• If you cannot satisfy all of the specifications of mapGrid(), do what you can for partial credit. For instance, you can receive partial credit for just eating the bagels and leaving behind the colored patches without returning a non-trivial map. You can also receive partial credit if you return the part of the map that contains 0s and 1s but not the column sums.

---

Task 3: An Application: Prime Numbers [35 points]

Write an application that takes an integer command line argument, tests it, and outputs a message saying whether the argument is a prime number or not. As a reminder, an integer is a prime number if it has only two distinct divisors: 1 and itself. For example, 7 is a prime number, since it only has two distinct divisors: the number 1 and itself. On the other hand, the number 12 is not a prime number, since it has more divisors than the trivial ones (1 and 12); namely, the numbers 2, 3, 4, and 6 are all non-trivial divisors of 12. Non-prime numbers are called composite numbers.

Create a class, named Primality, in a file named Primality.java. Then complete the following 4 subtasks (you draw the iteration table first if this helps you write the code):

1. A class (static) method that takes an integer to be tested for primality. This method should count and return the number of its factors. The definition of this method must employ a while loop.
2. A class (static) method with identical behavior that uses a for loop instead.
3. A class (static) main() method that reads the input from the command-line, invokes the methods above, and prints an informative message about the primality of the input number. Make sure to invoke both of the methods above to test them thoroughly. You may comment out testing code, but do not delete testing code: we want to see it.
4. Draw an iteration table that describes the loops you wrote for computing the number of factors of a number.

The figure below illustrates an execution of a working application from the "Interactions" tab at the bottom of the Dr. Java window.