Eric Roberts Handout #47CS 106A February 17, 2010Extra-Credit Problem SetDue date: Wednesday, February 24, 5:00P.M. (No late days on problem sets.)Name (please print) __________________________________Section Leader __________________________________The purpose of this handout is to give those of you who had troubles with the midtermexam an opportunity—along with an incentive—to get more practice with algorithmicproblems. There are five problems on this problem set. Each answer that is substantiallycorrect will add two points to your percentage score on the midterm, up to a maximum of100% on the exam. Answers that are close enough to receive at least half credit on anexam will give you one extra point. If most of you turn in this problem set and doreasonably well, the median on the midterm will rise from 70% to something in the high70s, which is what we’re shooting for. The scaling of the exam will remain exactly thesame as shown on Handout #43, so that turning in this extra-credit assignment can helpyour grade but not hurt it. Moreover, deciding not to turn in this problem set won’t hurtyour course grade at all; you’ll simply keep your original grade on the midterm exam.These problems are designed to be completed by hand, just as if they were examproblems, given that exams are, after all, where the problems seem to come up. Feel free,however, to run them on the computer if you want to check your algorithms. (If you doimplement them, you can go ahead and staple in listings of the code, since I suspect yoursection leaders would rather look at a printed copy than try to decipher handwritten code.)We will grade these problems as if they were handwritten on an exam and not be sticklishabout semicolons and other minor syntactic problems.1. Console graphicsBack in the days before computer graphics, one of the typical assignments that we wouldgive early in CS106A was to draw some figure on the console using characters. As asimple example, if you execute the nested loopfor (int i = 0; i < 8; i++) { for (int j = 0; j < 8; j++) { print("*"); } println();}draws an 8 x 8 square on the console composed of asterisks, as follows:DrawSquare****************************************************************– 2 –These exercises were not as flashy as the acm.graphics applications you write today, butthey did have the advantage of forcing students to learn how to use nested for loops andhow to think algorithmically about how to create the figure.In this problem, your mission is to write a functionprivate void drawDiamondOutline(int size)that draws the outline of a diamond whose sides are composed of the number of starsindicated by size. For example, if your run method ispublic void run() { drawDiamondOutline(8);}your program should print asterisks and spaces in just the right places to produce thefollowing sample run:DrawDiamondOutline * * * * * * * * * * * * ** * * * * * * * * * * * * * *Answer to problem 1:private void drawDiamondOutline(int size) {}– 3 –2. The consecutive heads problem (Chapter 6, exercise 2, page 214)Heads. . . .Heads. . . .Heads. . . .A weaker man might be moved to re-examine his faith, if in nothingelse at least in the law of probability.—Tom Stoppard, Rosencrantz and Guildenstern are Dead, 1967Write a program that simulates flipping a coin repeatedly and continues until threeconsecutive heads are tossed. At that point, your program should display the totalnumber of coin flips that were made. The following is one possible sample run of theprogram:ConsecutiveHeadsTailsHeadsHeadsTailsTailsHeadsTailsHeadsHeadsHeadsIt took 10 flips to get 3 consecutive heads.Answer to problem 2:import acm.program.*;import acm.util.*;public class ConsecutiveHeads extends ConsoleProgram { private RandomGenerator rgen = RandomGenerator.getInstance();}– 4 –Problem 3: A series approximation for piIn my lecture on random numbers, I showed how one might approximate π by simulatingthe process of throwing darts at a circular dart board. At the time, I noted that there areother, more reliable ways to compute the value of π. The German mathematician Leibniz(1646–1716), for example, discovered the rather remarkable fact that π can be computedusing the following mathematical relationship:π4 = 11 – 13 + 15 – 17 + 19 – 111 + . . .The formula to the right of the equal sign represents an infinite series; each fractionmaking up the series is called a term. If you start with 1, subtract one-third, add one-fifth,and so on, for each of the odd integers, you get a number that gets closer and closer to thevalue of π/4.Write a program that uses this formula to calculate the approximation to π that resultsfrom carrying out this computation until the value of a term becomes less than a thresholddefined as a named constant as follows:private static final double TERM_THRESHOLD = .000001;To make the steps in this calculation a little clearer, your program must1. Include a loop that keeps track of the total on the right-hand side of the formula ateach step in the process.2. Keep track of the current term, which involves computing the next odd number andthen taking its reciprocal (i.e., what you get if you divide 1 by that number).3. Continue to cycle through the loop until the current term is smaller than the value ofTERM_THRESHOLD.4. Keep track of whether to add or subtract the term from the running total. The firstterm is added, the second subtracted, the third added, and so on, alternating back andforth.5. Multiply the total by 4 at the end of the loop.6. Display the result in a line like this:PiSeriesPi is approximately 3.141590653589692Note: Even though this problem involves fractions, you should not be misled into usingthe Rational class introduced in Chapter 6. Doing so will not help at all but will insteadjust get you into trouble. All you need for this problem are ints and doubles.– 5 –Answer to problem 3:import acm.program.*;public class PiSeries extends ConsoleProgram {}– 6 –4. Inverting an encryption keyIn last Wednesday’s class that introduced crypography, one of the code examples was aprogram that encrypted messages using a letter-substitution cipher. What we did nothave time to write was the program to reverse that encryption, making it possible for thereceiver to read the encrypted text. Although it is
View Full Document
Unlocking...