Eric Roberts Handout #42CS 106A February 9, 2010Solutions to Midterm ExamAlthough I’m not quite sure of the reason, this midtern exam didn’t go as well asmidterms have in recent years. The median was 70 percent, which is substantially lowerthan what I shoot for and lower than it has been in recent years. Part of the problemseems to center on problem 3, which seemed to throw many of you for a loop, but evenso I am concerned that more of you are struggling with the algorithmic aspects of thematerial than is usually the case.The complete histogram of grades appears below. You can determine your letter grade—which I’ve curved so that the median is the middle of the B range—by looking up thepercentage score (the score written at the top of your exam) in the table at the upper leftcorner of the histogram.N = 213 84Median = 70 84Mean = 70.4 64 69 79 8464 69 79 84Range Grade N 64 69 79 83 8998–100 A+ 13 59 64 68 74 78 83 8988–97 A 25 54 59 64 68 74 78 83 8983–87 A– 27 54 59 64 68 74 78 83 8975–82 B+ 29 54 59 63 68 74 78 83 89 9466–74 B 33 53 59 63 68 73 78 83 88 93 9861–65 B– 26 53 59 63 67 73 78 83 88 93 9856–60 C+ 15 53 58 63 67 73 77 83 87 93 9850–55 C 21 53 58 63 67 73 77 83 87 93 9845–49 C– 6 53 58 62 66 73 77 83 87 93 9835–44 D 14 43 53 57 62 66 72 77 83 87 92 9800–34 NP 4 43 53 57 62 66 72 77 82 87 92 9843 53 57 61 66 72 76 82 87 92 9842 49 53 56 61 65 70 75 82 86 91 9839 41 47 52 56 61 65 70 75 82 85 90 9838 41 46 50 55 61 65 70 75 82 85 90 9838 40 46 50 55 61 65 70 75 81 85 90 9729 36 40 46 50 55 61 65 70 75 80 85 90 97 10023 26 30 35 40 45 50 55 60 65 70 75 80 85 90 97 100– 2 –Problem 1: Karel the Robot (10 points)/* * File: KarelCare * --------------- * Karel looks through the hospital ward for patients with * temperatures over 100 and paints the square under the * temperature red so that doctors can treat the patient. */import stanford.karel.*;public class KarelCare extends SuperKarel {/* * Runs the program. This code find every bed in the ward and * then calls checkTemperature. This code handles the final * column correctly, although that was not required. */ public void run() { while (frontIsClear()) { if (beepersPresent()) { checkTemperature(); } move(); } if (beepersPresent()) { checkTemperature(); } }/* * Flags any temperatures greater than 100. This code operates * by taking away 100 beepers (if possible) and seeing whether * there are any left. It then puts all the beepers back. */ private void checkTemperature() { for (int i = 0; i < 100; i++) { if (beepersPresent()) { pickBeeper(); } } if (beepersPresent()) { paintCorner(RED); } while (beepersInBag()) { putBeeper(); } }}On the evening exam, the color of the corner was YELLOW.– 3 –Problem 2: Simple Java programs (10 points)(2a)Afternoon exam:6 / 5 + 5 + 8 % 3 == 8 true('D' - 'A') + '0' '3' or 511 + 2 + "3" + 4 + 5 "3345"Evening exam:6 / 5 + 5 + 8 % 3 == 8 false('6' - '2') + 'A' 'E' or 691 * 2 + "3" + 4 * 5 "2320"(2b)"lollipop"(2c) afternoon exam evening examvalentine: str = XOXOXOXOXO, n = 0heart: str = XO, n = 5XOXOXvalentine: str = OXOXOXOXOX, n = 0heart: str = OX, n = 5OXOXO– 4 –Problem 3: Simple Java programs (15 points)/* * File: TotientTable.java * ----------------------- * This program produces a table of values of the Euler totient * function from 2 up to the maximum specified by the constant * LIMIT. The totient function plays a central role in the * mathematics behind the RSA public encryption algorithm. */import acm.program.*;public class TotientTable extends ConsoleProgram {/* Creates the table */ public void run() { for (int i = 2; i <= LIMIT; i++) { println("totient(" + i + ") = " + totient(i)); } }/* * Calculates the Euler totient function of n. The totient is * the number of integers between 1 and n that share no factors * with n (other than 1). */ private int totient(int n) { int count = 0; for (int i = 1; i < n; i++) { if (!shareACommonFactor(i, n)) count++; } return count; }/* * Returns true if n1 and n2 share a common factor (other than 1). * In mathematics, such numbers are said to be relatively prime. */ private boolean shareACommonFactor(int n1, int n2) { for (int i = 2; i <= Math.min(n1, n2); i++) { if (n1 % i == 0 && n2 % i == 0) return true; } return false; }/* Private constants */ private static final int LIMIT = 12;}An even simpler strategy would be to use the gcd function that was introduced in thediscussion of rational numbers and appears on page 202 of the text. In this case, youcould leave out the definition of shareACommonFactor and change the if in totient toif (gcd(i, n) == 1) count++;On the evening exam, the constant LIMIT was renamed to MAX.– 5 –Problem 4: Using the graphics and random number libraries (15 points)There are several approaches for solving this problem, of which two are shown here. Thefirst stores the direction of motion as one of the constants NORTH, EAST, SOUTH, or WEST./* * File: Snake.java * ---------------- * This program plays the simplified Snake game from the midterm exam. */import acm.graphics.*;import acm.program.*;import java.awt.event.*;public class Snake extends GraphicsProgram {/* Initializes the graphics state */ public void init() { x = getWidth() / 2; y = getHeight() / 2; dir = EAST; addMouseListeners(); }/* Runs the simulation */ public void run() { while (getElementAt(x, y) == null) { drawSquare(); updateSnakeHeadLocation(); pause(PAUSE_TIME); } }/* Adds a square to the window centered at (x, y) */ private void drawSquare() { GRect rect = new GRect(SQUARE_SIZE, SQUARE_SIZE); rect.setFilled(true); add(rect, x - SQUARE_SIZE / 2, y - SQUARE_SIZE /2); }/* Updates the location of the snake head */ private void updateSnakeHeadLocation() { switch (dir) { case NORTH: y -= SQUARE_SIZE; break; case EAST: x += SQUARE_SIZE; break; case SOUTH: y += SQUARE_SIZE; break; case WEST: x -= SQUARE_SIZE; break; } }– 6 –/* Reacts to a mouse-pressed event */ public void mousePressed(MouseEvent e) { if (dir == NORTH || dir == SOUTH) { dir = (e.getX() > x) ? EAST : WEST; } else { dir = (e.getY() > y) ? SOUTH : NORTH; }
View Full Document
Unlocking...