15-100 Sections U-V-AA / Spring 2009 / Quiz 5
30 Minutes

3 Questions – 10 minutes per question

Notes:

• On this quiz, you will use a compiler to write code.
• You may access the course web site, Sun’s online API, and the compiler of your choice.
• You may not access anything else (no notes, books, etc, no Google or other searches, and certainly no code!).
• Place your solutions in a single Java file named Quiz5<andrewId>.java
  (So for me it would be Quiz5koz.java)
• When you are done, you should email your solution both as an attachment and pasted into the body of the message. Send it to me (andrew id: koz), and be sure to cc yourself!
  
  
• In your code, you may use loops, conditionals, helper methods, methods from any Java classes in Sun’s library, etc, even arrays if you wish (though they are not required).
• Each problem asks you to write a void method that takes no parameters.
• Your code will only be graded for correctness, not style.
• For efficiency during a quiz, do not use prompts, etc. Just provide the required UI.
• Your code must compute the answers! Hardcoded answers will not receive any credit.
• Do not use web-based scanners for this quiz. Use file-based scanners.
• Thus, before starting this quiz, download this file to your desktop:
  http://kosbie.net/cmu/spring-09/15-100/resources/millionDigitsOfPi.txt
  
  
• To save some time, you should start with this code, which also includes the import statements and the getFileScanner helper method for you.
  
  // <name>, <andrewId>, <section>
  import java.util.*;
  import java.io.*;
  class Quiz5 {
  public static void main(String[] args) {
  printPiPalindrome();
  printSmallestBlock();
  printZeroFreeOdds();
  testRandomness();
  }
  
  public static void printPiPalindrome() {
  System.out.println("printPiPalindrome not yet written!");
  }
  
  public static void printSmallestBlock () {
  System.out.println("printSmallestBlock not yet written!");
  }
  
  public static void printZeroFreeOdds () {
  System.out.println("printZeroFreeOdds not yet written!");
  }
  
  public static void testRandomness () {
  System.out.println("bonus: testRandomness not yet written!");
  }
  
  // Convenient helper method for reading from a file.
  public static Scanner getFileScanner(String filename) {
  Scanner scanner = null;
  try { scanner = new Scanner(new java.io.File(filename)); }
  catch (Exception e) {
  System.out.println("File not found");
  return null;
  }
  return scanner;
  }
  }
  
  

1. Palindromic Pi Digits
Here are the first few lines from the file millionDigitsOfPi.txt (now on your desktop):
1415926535 8979323846 2643383279 5028841971 6939937510
5820974944 5923078164 0628620899 8628034825 3421170679
8214808651 3282306647 0938446095 5058223172 5359408128
As you can see, the file consists of 10-digit blocks (100,000 of them). As it turns out, two of these blocks are palindromes (same forwards as backwards). The first one is 0136776310. Write a method, printPiPalindrome, that locates and prints the second (and only the second!) palindromic block.

2. Smallest Pi Block
We can view each 10-digit block in the file millionDigitsOfPi.txt as a number between 0 and 10 billion. Write a method, printSmallestBlock, that locates and prints the smallest 10-digit block in this file. You will have to think about overflow, and you may assume that the smallest block is less than one billion in any case (this simplifies the problem!).

3. Odds of Zero-Free Blocks
Of the first 15 blocks listed above, 3 of them (curiously, the first 3) do not contain any zeroes. That’s 3/15, or 20%. To see if this is above or below the expected value, write a method, printZeroFreeOdds, that uses Monte Carlo methods to compute and print the odds that one block of 10 random digits does not contain any zeroes. As usual, use enough trials to get a reasonably accurate result. Hint: remember to create only one instance of Random!

4. Bonus/Optional: Pi is Pseudo-Random?
Are the digits of pi a good source of pseudo-random numbers? Write a method, testRandomness, that tests this theory against the first million digits of pi in the given file, and prints the result of the test (either “yes – fairly random” or “no – not so random”, perhaps with some numeric value(s) to back up the conclusion). Write a brief comment in your Java file explaining how your test works.