Z OLD Homework 01 - james-bern/CS136 GitHub Wiki

- introduce 2 program structures (straight-shot-through-main/script and loop/game)
- introduce Cow.java

image

README (Before Lab)

Play with this simple number system converter app

Decimal (base-10)

  • Your whole life* you have been writing numbers in decimal aka base-10.
  • When I type Java code int a = 123, I am expressing the right hand side in decimal.
    • 123 means...
      • $1 * 100 + 2 * 10 + 3 * 1$
      • $1 * 10^2 + 2 * 10^1 + 3 * 10^0$
        • Note that $10$ is the base of the factors $10^2$, $10^1$, and $10^0$. Hence, base-10.
        • (Recall that a non-negative number raised to the zeroth power equals one.)

Binary (base-2)

  • Internally, computers represent integers in binary aka base-2.
  • 123 could be written as 1111011 in binary.
    • To avoid confusion with decimal, a prefix like 0b is typically added, _i.e., we might actually write 0b1111011.
    • 1111011 in binary means...
      • $1 * 64 + 1 * 32 + 1 * 16 + 1 * 8 + 0 * 4 + 1 * 2 + 1 * 1$
      • $1 * 2^6 + 1 * 2^5 + 1 * 2^4 + 1 * 2^3 + 0 * 2^2 + 1 * 2 ^ 1 + 1 * 2 ^ 0$

Hexadecimal (base-16)

  • Hexadecimal aka base-16 is often used to represent colors, e.g., #FF00FF is magenta.
    • the digits $0, ..., 9$ have the same meaning as in base-10, and $A, ..., F$ correspond to the numbers $10, ..., 15$
    • 123 could be written as 7B in binary.
      • A prefix like 0x or # is typically added, _i.e., we might actually write 0x7B.
      • 7B in hex means...
        • $7 * 16 + 11 * 1$
        • $7 * 16^1 + 11 * 16^0$

Details

  • *There may be times in your life where you used systems other than base-10. E.g., tally marks are base-1 aka unary.
  • Unless we're dealing with bitwise operators, we can actually ignore the detail that the computer internally stores integers in binary. Here are three ways of doing the exact same thing:
    • int a = 123; tells the computer "Store the number with decimal representation $123$ in integer a."
    • int a = 0b1111011; tells the computer "Store the number with binary representation $1111011$ in integer a."
      • Note: The DrJava Interactions pane doesn't support this, but our compiler does. 🙂👍
    • int a = 0x7B; tells the computer "Store the number with hexadecimal representation $7B$ in integer a."

Finding digits in base-N

  • Here is how to find the digits of some int a in base-N.
    • Algorithm
      • Imagine expressing $a = \cdots + d_2 N^2 + d_1 N^1 + d_0 N^0$.
        • Our goal is to find $\cdots, d_2, d_1, d_0$.
      • The remainder a % N returns $d_0$.
      • Dividing a / N will eliminate the last term (d_0 / N is less than $1$ and Java truncates when dividing int's), returning $\cdots + d_2 N^1 + d_1 N^0$.
      • We can repeat this process, extracting one digit at a time, until the result of a / N is zero and we are done.
    • Example
      • Let's find the digits of 123 in base-2 (you can follow along in the DrJava Interactions pane!)
        • 123 % 2 returns 1 $\to$ // ...1
        • 123 / 2 returns 61
        • 61 % 2 returns 1 $\to$ // ...11
        • 61 / 2 returns 30
        • 30 % 2 returns 0 $\to$ // ...011
        • 30 / 2 returns 15
        • 15 % 2 returns 1 $\to$ // ...1011
        • 15 / 2 returns 7
        • 7 % 2 returns 1 $\to$ // ...11011
        • 7 / 2 returns 3
        • 3 % 2 returns 1 $\to$ // ...111011
        • 3 / 2 returns 1
        • 1 % 2 returns 1 $\to$ // 1111011
        • 1 / 2 returns 0

Example Programs

static void printStringOneCharacterAtATimeForNoReason(String string) {
    for (int i = 0; i < string.length(); ++i) {
        char c = string.charAt(i);
        System.out.print(c);
    }
    System.out.println();
}
static int numDigits(int n) {
    assert n >= 0;
    
    int result = 0;
    while (n > 0) {
        ++result;
        n /= 10;
    }
    return result;
}

Specification

  • To get an A:

    • Implement all functions.
    • 🚨 Note: All problems should be solved using techniques like the ones we talked about in the class and on the homework. I.e., magical Java one-liners like Integer.toBinaryString(int decimal) will typically not score points (even if the autograder is happy). If in any doubt, ask!
    • You aren't allowed to modify grade() of the comment that it generates, but you can (and should!) write your own tests directly in main.

  • To get an S:

    • Do everything above.
    • Make a Project Euler account, and solve https://projecteuler.net/problem=14 (actually submit it on Project Euler). Once you are successful, include a the answer in a comment at the top of your code file. Note: If you have already done this problem, do any other problem instead.
      • 🚨 Hint: Use a long to store the $n$ instead of an int. An int does not have enough bits to store numbers as large as you will encounter!

Submission Instructions

  • Run grade() (you can do this whenever you want, as many times as you want), copy the comment it generates, and paste the comment at the top of your code file.
    • 🚨 You must do this in order to receive points.
  • Upload your code file to GradeScope by the due date.

Starter Code

If you hover your mouse over the code box below, a little button will appear in the upper-right corner that you can click to copy the code. Wow!

import java.util.*;

class HW01 {
    // returns the length of the hypotenuse of right triangle with legs of lengths a and b
    static double pythagoreanTheorem(double a, double b) {
        return 0.0;
    }

    // returns whether n is prime
    static boolean isPrime(int n) {
        return false;
    }

    // returns the sum of n's (base-10) digits
    // NOTE: don't use recursion
    static int digitSum(int n) {
        int result = 0;
        return result;
    }

    // returns the sum of hex's (base-16) digits
    // NOTE: Hexadecimal works like this 0, ..., 9, A, ..., F
    //       A is 10, B is 11, ..., F is 15.
    // NOTE: do NOT have separate cases for 'A', 'B', 'C', 'D', 'E', and, 'F'
    //       instead, have only three cases:
    //       - digit (character) in range ['0', '9']
    //       - digit (character) in range ['A', 'F']
    //       - any other digit (crash with an assert false;)
    // NOTE: should crash using an assert false; if hex is not a valid hex number
    // NOTE: don't use recursion
    static int hexDigitSum(String hex) {
        int result = 0;
        return result;
    }

    // returns a String representation of n in the following bigendian notation
    // 0 ->   "0"
    // 1 ->   "1"
    // 2 ->  "10"
    // 3 ->  "11"
    // 4 -> "100"
    // ...
    // NOTE: should crash using an assert if n is negative
    // NOTE: don't use recursion
    // NOTE: sample solution is ~6 lines
    static String getInBinary(int n) {
        String result = "";
        return result;
    }

    public static void main(String[] arguments) {
        grade();
        // System.out.println(pythagoreanTheorem(3.0, 4.0));
    }

    // Runs some basic tests and estimates your grade.
    static void grade() {
        GRADER_BEGIN_PROBLEM("pythagoreanTheorem");
        try { GRADER_ASSERT(_areApproximatelyEqual(pythagoreanTheorem(3.0, 4.0), 5.0)); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(_areApproximatelyEqual(pythagoreanTheorem(1.0, 1.0), Math.sqrt(2))); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }

        GRADER_BEGIN_PROBLEM("isPrime");
        try { GRADER_ASSERT(isPrime(-3) == false); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(isPrime(0) == false); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(isPrime(1) == false); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(isPrime(2) == true); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(isPrime(7) == true); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(isPrime(37) == true); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(isPrime(55) == false); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }

        GRADER_BEGIN_PROBLEM("digitSum");
        try { GRADER_ASSERT(digitSum(0) == 0); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(digitSum(22) == 4); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(digitSum(123) == 6); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(digitSum(7770) == 21); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }

        GRADER_BEGIN_PROBLEM("hexDigitSum");
        try { GRADER_ASSERT(hexDigitSum("") == 0); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(hexDigitSum("22") == 4); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(hexDigitSum("F1") == 16); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(hexDigitSum("AB23") == 26); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { try { hexDigitSum("XXX"); GRADER_ASSERT(false); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); } } catch (Error error) { _GRADER_HANDLE_ERROR(); }

        GRADER_BEGIN_PROBLEM("getInBinary");
        try { try { getInBinary(-1); GRADER_ASSERT(false); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); } } catch (Error error) { _GRADER_HANDLE_ERROR(); }
        try { GRADER_ASSERT(getInBinary(0).equals(  "0")); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(getInBinary(1).equals(  "1")); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(getInBinary(2).equals( "10")); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(getInBinary(3).equals( "11")); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(getInBinary(4).equals("100")); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }
        try { GRADER_ASSERT(getInBinary(25743).equals("110010010001111")); } catch (Exception exception) { GRADER_HANDLE_EXCEPTION(); }

        GRADER_FINISH_GRADING();
    }

    static boolean _areApproximatelyEqual(double a, double b) {
        return Math.abs(a - b) < 1.0e-5;
    }

    // Feel free to ignore everything below this comment. //////////////////////

    static private boolean graderReset = true;
    static private int graderCurrentProblemIndex;
    static private String gradeCurrentProblemName;
    static private boolean graderProblemCurrentlyPassing;
    static private int gradeNumProblemsPassed;
    static private ArrayList<String> graderPassedProblemNames;
    static private ArrayList<String> graderFailedProblemNames;

    static private void _GRADER_END_PROBLEM() {
        System.out.println();
        if (graderProblemCurrentlyPassing) {
            ++gradeNumProblemsPassed;
            graderPassedProblemNames.add(gradeCurrentProblemName);
        } else {
            graderFailedProblemNames.add(gradeCurrentProblemName);
        }
    }

    static private void GRADER_BEGIN_PROBLEM(String questionName) {
        if (graderReset) {
            graderReset = false;
            graderCurrentProblemIndex = 0;
            graderProblemCurrentlyPassing = false;
            gradeNumProblemsPassed = 0;
            gradeCurrentProblemName = null;
            graderPassedProblemNames = new ArrayList<>();
            graderFailedProblemNames = new ArrayList<>();
            System.out.println("/**");
            System.out.println(" * grade()");
            System.out.println(" * + means test passed (function produced correct result OR tripped assert)");
            System.out.println(" * - means test failed (function produced incorrect result OF failed to trip assert)");
            System.out.println(" * x means function crashed (in a way that it wasn't supposed to)");
            System.out.println(" * NOTE: grader assumes you have asserts enabled (using DrJava or passed -ea)");
            System.out.println(" *");
        } else {
            _GRADER_END_PROBLEM();
        }
        gradeCurrentProblemName = questionName;
        ++graderCurrentProblemIndex;
        graderProblemCurrentlyPassing = true;
        System.out.print(" * " + questionName + " ");
    }

    static private void GRADER_ASSERT(boolean shouldBeTrue) {
        System.out.print((shouldBeTrue == true) ? '+' : '-');
        graderProblemCurrentlyPassing &= shouldBeTrue;
    }

    static private void GRADER_HANDLE_EXCEPTION() {
        System.out.print('x');
        graderProblemCurrentlyPassing = false;
    }

    static private void _GRADER_HANDLE_ERROR() {
        System.out.print('+');
    }

    static private void GRADER_FINISH_GRADING() {
        if (graderCurrentProblemIndex != 0) { _GRADER_END_PROBLEM(); }

        int numProblems = graderCurrentProblemIndex;
        int numProblemsIncorrect = numProblems - gradeNumProblemsPassed;

        char grade = 'C'; {
            if (numProblemsIncorrect == 0) {
                grade = 'A';
            } else if (numProblemsIncorrect == 1) {
                grade = 'B';
            } 
        }

        System.out.println(" * ");
        System.out.println(" * Passed all tests " + graderPassedProblemNames);
        System.out.println(" * Failed some test " + graderFailedProblemNames);
        System.out.println(" * ");
        System.out.println(" * Grade ~ " + grade);
        System.out.println(" **/");

        graderReset = true;
    }
}

Home   Docs   Glow   HelpHours   LectureRecordings

⚠️ **GitHub.com Fallback** ⚠️