Eric Roberts Handout #64CS 106A March 8, 2009Practice Final Examination #2Review session: Sunday, March 14, 7:00–9:00P.M. (Hewlett 201)Scheduled finals: Monday, March 15, 12:15–3:15P.M. (Hewlett 200)Friday, March 19, 12:15–3:15P.M. (Hewlett 200)The answers to this practice final will be posted to the web site on Wednesday. Note thata couple of these problems have since made their way into the text in at least some form,although they were not in the draft at the time at which these problems appeared on a oldfinal.Problem 1—Short answer (10 points)1a) Trace through the evaluation of the following program and indicate the output itproduces.import acm.program.*;public class Mystery extends ConsoleProgram {public void run() {int[] array = new int[13];for (int i = 1; i <= 12; i++) {for (int j = i; j > 0; j--) {array[j] += j;}}}}Work through the method carefully and indicate your answer by filling in the boxesbelow to show the final contents of array, just before the run method returns:0 1 2 3 4 5 6 7 8 9 10 11yarra12– 2 –1b) Suppose that you have been assigned to take over a project from another programmerwho has just been dismissed for writing buggy code. One of the methods you havebeen asked to rewrite—which doesn’t even compile—looks like this:/** * Returns the acronym of the specified string, which is * defined to be a new word formed from the first letter in * each separate word contained in the string. A word is a * consecutive string of letters. For example, calling * * acronym("self-contained underwater breathing apparatus") * * should return the string "scuba". */private String acronym(String str) {boolean inWord = false;for (int i = 0; i < str.length(); i++) {char ch = str.charAt(i);if (ch.isLetter()) {if (!inWord) result += ch;} else {inWord = false;}}return result;}Unfortunately, the code—short as it is—contains several bugs. Circle the bugs in theimplementation and write a short sentence explaining the precise nature of eachproblem you identify.– 3 –Problem 2—Using the acm.graphics library (15 points)Back before we had a graphics library, one of the early assignments in CS 106A was towrite a program that played a simple game called Nim. In the simplest version of thegame, two players start with a pile of 11 coins on the table between them. The playersthen take turns removing 1, 2, or 3 coins from the pile. The player who is forced to takethe last coin loses. In the old days, the point of this assignment was to figure out astrategy for winning the game. With our modern attachment to fancier user interfaces,however, it is just as easy to focus on the problem of representing the game graphicallyon the screen.Your job in this problem is to complete the implementation of the program that appearson the following page, which is responsible for displaying the coins and handling the userinteraction. You should think about the task as consisting of two parts. The first part ofthis problem is to create a graphical display in which you have a line of coins arrangedhorizontally on the screen, like this:GraphicNimIn constructing your display, you should make use of the named constants—N_COINS,COIN_SIZE, and COIN_SEP—that appear at the top of the program framework. Youshould also make sure that each coin is filled in GRAY and outlined in BLACK. The line ofcoins should be centered both horizontally and vertically in the window.The second part of the problem consists of making it possible to take coins away. Addthe necessary code so that if the user clicks the mouse in one of the last three coins in therow, those coins disappear. For example, if the user clicked on the third coin from theright end, the program should respond by removing the last three coins from the display,like this:GraphicNimIf the user then clicked on the rightmost coin, only that coin should go away:GraphicNim– 4 –If the mouse click does not occur inside a coin or if the coin is not one of the last three inthe row, that click should simply be ignored.In order to solve this problem, you will need to store the GOval objects in some kind ofdata structure that allows you to keep track of their order. Given the fact that you need totake coins away, an ArrayList seems perfect for the job. When a mouse click occurs,your program needs to find the object at that mouse location (if any) and see whether it isone of the last three elements in the ArrayList. If so, your program should remove thatelement and any following elements from both the ArrayList and the window.Solution to problem 2:public class GraphicNim extends GraphicsProgram {public static final int N_COINS = 11; /* Number of coins */public static final int COIN_SIZE = 25; /* Diameter of a coin */public static final int COIN_SEP = 10; /* Space between coins */. . . You fill in the run method and any other methods you need . . .}– 5 –Problem 3—Strings (15 points)In Dan Brown’s best-selling novel The Da Vinci Code, the first clue in a long chain ofpuzzles is a cryptic message left by the dying curator of the Louvre. Two of the lines ofthat message areO, Draconian devil!Oh, lame saint!Professor Robert Langdon (the hero of the book, who is played by Tom Hanks in themovie version) soon recognizes that these lines are anagrams—pairs of strings thatcontain exactly the same letters even if those letters are rearranged—forLeonardo da VinciThe Mona LisaYour job in this problem is to write a predicate methodpublic boolean isAnagram(String s1, String s2)that takes two strings and returns true if they contain exactly the same alphabeticcharacters, even though those characters may appear in any order. Thus, your methodshould return true for each of the following calls:isAnagram("O, Draconian devil!", "Leonardo da Vinci")isAnagram("Oh, lame saint!", "The Mona Lisa")isAnagram("ALGORITHMICALLY", "logarithmically")isAnagram("Doctor Who", "Torchwood")These examples illustrate two important requirements for the isAnagram method:• The implementation should look only at letters (i.e., characters for which theCharacter.isLetter method returns true), ignoring any extraneous spaces andpunctuation marks thrown in along the way.• The implementation should ignore the case of the letters in both strings.There are many different algorithmic strategies you could use to decide whether twostrings contain the same alphabetic characters. If you’re having trouble coming up with astrategy, you should note that two