CSC300 / CSC402: Homework (MyFirstHomework): Homework (MyFirstHomework)

CSC300 / CSC402: Homework (MyFirstHomework) [1/3]

Install the tools for class. Instructions.

Optional: After you've installed IntelliJ IDEA Community Edition, you can go to the Help menu and choose "Learn IDE Features" for some built-in tutorials on how to use IDEA.

See Features Trainer for more information.

Don't bother doing the "Git" tutorial, as we won't be using git in this class.
Look on D2L for quiz to complete.
Look on D2L for homework to hand in. The homework file is in the algs11 package and is called MyFirstHomework.java.
Look over IntelliJ IDEA: Getting Started. You can skim most of the content, but you might want to read through the following sections carefully.
Read chapter 1 of Core Java for the Impatient.
Skim chapter 2 of Core Java for the Impatient.
Skim Algorithms (the primary text) through the end of 1.2

There's a free online version in case you don't have the text yet. Check out the links for the textbook on the course homepage.
- Check out the booksite. Find their notes on section 1.1, which gives a summary of the textbook.
- Check out the links for the textbook on the course homepage. You will find an online version of the textbook, videos, slides and more. You can also find lecture notes, homework assignments and old exams for the class at Princeton.

file:MyFirstHomework.java [source]

package algs11;

import java.util.Arrays;

import stdlib.*;

/**
 * This is a skeleton file for your homework. Edit the sections marked TODO. You
 * may also edit the function "main" to test your code.
 * <p>
 * You must not change the declaration of any method. This will be true of every
 * skeleton file I give you.
 * <p>
 * For example, you will get zero points if you change the line
 * <pre>
 *     public static double minValue (double[] list) {
 * </pre>
 * to something like
 * <pre>
 *     public static void minValue (double[] list) {
 * </pre>
 * or
 * <pre>
 *     public static double minValue (double[] list, int i) {
 * </pre>
 * <p>
 * Each of the functions below is meant to be SELF CONTAINED. This means that
 * you should use no other functions or classes. You should not use any HashSets
 * or ArrayLists, or anything else! In addition, each of your functions should go
 * through the argument array at most once. The only exception to this
 * removeDuplicates, which is allowed to call numUnique and then go through the
 * array once after that.
 */
public class MyFirstHomework {

    /**
     * minValue returns the minimum value in an array of doubles. You can assume
     * the array is nonempty and has no duplicates. Your solution must go
     * through the array exactly once. Your solution must not call any other
     * functions. Here are some examples (using "==" informally):
     *
     * <pre>
     *   -7  == minValue (new double[] { -7 })
     *    1  == minValue (new double[] { 1, 7, 8, 11 })
     *   -7  == minValue (new double[] { 1, -4, -7, 7, 8, 11 })
     *   -13 == minValue (new double[] { -13, -4, -7, 7, 8, 11 })
     *   -13 == minValue (new double[] { 1, -4, -7, 7, 8, 11, -13 })
     * </pre>
     */
    public static double minValue(double[] list) {
        return StdRandom.uniform(); //TODO: fix this
    }

    /**
     * minPosition returns the position of the minimum value in an array of
     * doubles. The first position in an array is 0 and the last is the
     * array.length-1.
     * <p>
     * You can assume the array is nonempty and has no duplicates. Your solution
     * must go through the array exactly once. Your solution must not call any
     * other functions. Here are some examples (using "==" informally):
     *
     * <pre>
     *   0 == minPosition(new double[] { -7 })
     *   2 == minPosition(new double[] { 1, -4, -7, 7, 8, 11 })
     *   0 == minPosition(new double[] { -13, -4, -7, 7, 8, 11 })
     *   6 == minPosition(new double[] { 1, -4, -7, 7, 8, 11, -9 })
     * </pre>
     */
    public static int minPosition(double[] list) {
        return StdRandom.uniform(100); //TODO: fix this
    }

    /**
     * distanceBetweenMinAndMax returns difference between the minPosition and
     * the maxPosition in an array of doubles.
     * <p>
     * You can assume the array is nonempty and has no duplicates. Your solution
     * must go through the array exactly once. Your solution must not call any
     * other functions. Here are some examples (using "==" informally):
     *
     * <pre>
     *   0 == distanceBetweenMinAndMax(new double[] { -7 })                      // -7,-7 are the min and max
     *   3 == distanceBetweenMinAndMax(new double[] { 1, -4, -7, 7, 8, 11 }),    // -7,11
     *   5 == distanceBetweenMinAndMax(new double[] { -13, -4, -7, 7, 8, 11 })   // -13,11
     *   1 == distanceBetweenMinAndMax(new double[] { 1, -4, -7, 7, 8, 11, -9 }) // -9,11
     * </pre>
     */
    public static int distanceBetweenMinAndMax(double[] list) {
        return StdRandom.uniform(100); //TODO: fix this
    }

    /**
     * allSame returns true if all of the elements in list have the same value.
     * allSame returns false if any two elements in list have different values.
     * The array may be empty and it may contain duplicate values.
     * <p>
     * Your solution should contain at most one loop.  You may not use recursion.
     * Your solution must not call any other functions.
     * Here are some examples (using "==" informally):
     *
     * <pre>
     *     true  == allSame(new double[] { })
     *     true  == allSame(new double[] { 11 })
     *     true  == allSame(new double[] { 11, 11, 11, 11 })
     *     false == allSame(new double[] { 11, 11, 11, 22 })
     *     false == allSame(new double[] { 11, 11, 22, 11 })
     *     true  == allSame(new double[] { 22, 22, 22, 22 })
     * </pre>
     */
    public static boolean allSame(double[] list) {
        return StdRandom.bernoulli(); //TODO: fix this
    }

    /**
     * numUnique returns the number of unique values in an array of doubles.
     * The array may be empty and it may contain duplicate values.
     * Unlike the previous questions, you can assume the array is sorted.
     * <p>
     * Your solution should contain at most one loop.  You may not use recursion.
     * Your solution must not call any other functions.
     * Here are some examples (using "==" informally):
     *
     * <pre>
     *     0 == numUnique(new double[] { })
     *     1 == numUnique(new double[] { 11 })
     *     1 == numUnique(new double[] { 11, 11, 11, 11 })
     *     8 == numUnique(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 })
     *     8 == numUnique(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 })
     * </pre>
     */
    public static int numUnique(double[] list) {
        return StdRandom.uniform(100); //TODO: fix this
    }

    /**
     * removeDuplicates returns a new array containing the unique values in the
     * array. There should not be any extra space in the array --- there should
     * be exactly one space for each unique element (Hint: numUnique tells you
     * how big the array should be). You may assume that the list is sorted, as
     * you did for numUnique.
     * <p>
     * Your solution may call numUnique, but should not call any other
     * functions. After the call to numUnique, you must go through the array
     * exactly one more time. Here are some examples (using "==" informally):
     *
     * <pre>
     *   new double[] { }
     *     == removeDuplicates(new double[] { })
     *   new double[] { 11 }
     *     == removeDuplicates(new double[] { 11 })
     *     == removeDuplicates(new double[] { 11, 11, 11, 11 })
     *   new double[] { 11, 22, 33, 44, 55, 66, 77, 88 }
     *     == removeDuplicates(new double[] { 11, 11, 11, 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88, 88 })
     *     == removeDuplicates(new double[] { 11, 22, 33, 44, 44, 44, 44, 44, 55, 55, 66, 77, 88 })
     * </pre>
     */
    public static double[] removeDuplicates(double[] list) {
        return null; // TODO: fix this
    }

    /**
     * A test program, using private helper functions.  See below.
     * To make typing tests a little easier, I've written a function to convert strings to arrays.  See below.
     */
    public static void main(String[] args) {
        // for minValue: array must be nonempty with unique elements
        testMinValue(-7, "1 -4 -7 7 8 11 9 -5");
        testMinValue(-0.5, "0.2 -0.5 -0.1");
        testMinValue(9, "11 9 21 31 41");
        testMinValue(9, "11 21 9 31 41");
        testMinValue(9, "11 21 31 9 41");
        testMinValue(9, "11 21 31 41 9");
        testMinValue(9, "9 11 21 31 41");
        testMinValue(-99, "-11 -99 -21 -31 -41");
        testMinValue(-99, "-11 -21 -99 -31 -41");
        testMinValue(-99, "-11 -21 -31 -99 -41");
        testMinValue(-99, "-11 -21 -31 -41 -99");
        testMinValue(-99, "-99 -11 -21 -31 -41");
        testMinValue(11, "11");
        testMinValue(-11, "-11");

        // for minPosition: array must be nonempty with unique elements
        testMinPosition(2, "1 -4 -7 7 8 11 9 -5");
        testMinPosition(1, "0.2 -0.5 -0.1");
        testMinPosition(1, "11 9 21 31 41");
        testMinPosition(2, "11 21 9 31 41");
        testMinPosition(3, "11 21 31 9 41");
        testMinPosition(4, "11 21 31 41 9");
        testMinPosition(0, "9 11 21 31 41");
        testMinPosition(1, "-11 -99 -21 -31 -41");
        testMinPosition(2, "-11 -21 -99 -31 -41");
        testMinPosition(3, "-11 -21 -31 -99 -41");
        testMinPosition(4, "-11 -21 -31 -41 -99");
        testMinPosition(0, "-99 -11 -21 -31 -41");
        testMinPosition(0, "11");
        testMinPosition(0, "-11");

        // for distanceBetweenMinAndMax: array must be nonempty with unique elements
        testDistanceBetweenMinAndMax(3, "1 -4 -7 7 8 11 9 -5");
        testDistanceBetweenMinAndMax(3, "0.1 -0.4 -0.7 0.7 0.8 1.1 0.9 -0.5");
        testDistanceBetweenMinAndMax(4, "9 11 21 31 41");
        testDistanceBetweenMinAndMax(3, "11 9 21 31 41");
        testDistanceBetweenMinAndMax(2, "11 21 9 31 41");
        testDistanceBetweenMinAndMax(1, "11 21 31 9 41");
        testDistanceBetweenMinAndMax(1, "11 21 31 41 9");
        testDistanceBetweenMinAndMax(4, "9 -11 -21 -31 -41");
        testDistanceBetweenMinAndMax(3, "-11 9 -21 -31 -41");
        testDistanceBetweenMinAndMax(2, "-11 -21 9 -31 -41");
        testDistanceBetweenMinAndMax(1, "-11 -21 -31 9 -41");
        testDistanceBetweenMinAndMax(1, "-11 -21 -31 -41 9");
        testDistanceBetweenMinAndMax(0, "11");
        testDistanceBetweenMinAndMax(0, "-11");

        testAllSame(true, "11 11 11 11");
        testAllSame(true, "5 5 5");
        testAllSame(false, "11 5 11 11");
        testAllSame(false, "11 11 5 11");
        testAllSame(false, "11 11 11 5");
        testAllSame(false, "5 11 11 11");
        testAllSame(false, "11 5 5 11 11");
        testAllSame(false, "11 11 5 5 11");
        testAllSame(false, "11 11 5 11 5");
        testAllSame(false, "5 5 11 11 11");
        testAllSame(false, "11 11 11 5 5");
        testAllSame(true, "11");
        testAllSame(true, "2");
        testAllSame(true, "");

        // for numUnique: array must be sorted
        testNumUnique(4, "11 21 21 21 31 41 41 41 41");
        testNumUnique(1, "11 11 11 11");
        testNumUnique(4, "11 21 31 41");
        testNumUnique(4, "11 11 11 21 31 31 31 31 41");
        testNumUnique(4, "11 11 21 21 21 31 31 41 41 41 41");
        testNumUnique(8, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81");
        testNumUnique(8, "11 21 31 41 41 41 41 41 51 51 61 71 81");
        testNumUnique(7, "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71");
        testNumUnique(7, "11 21 31 41 41 41 41 41 51 51 61 71");
        testNumUnique(8, "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11");
        testNumUnique(3, "-11 -11 -11 0 0 11 11 11");
        testNumUnique(2, "0 11 11 11");
        testNumUnique(2, "-Infinity 11 11 11");
        testNumUnique(2, "11 11 11 Infinity");
        testNumUnique(1, "11 11");
        testNumUnique(1, "11");
        testNumUnique(0, "");

        // for removeDuplicates: array must be sorted
        testRemoveDuplicates("11", "11 11 11 11");
        testRemoveDuplicates("11 21", "11 11 21");
        testRemoveDuplicates("11 21 31 41", "11 21 31 41");
        testRemoveDuplicates("11 21 31 41", "11 11 11 21 31 31 31 31 41");
        testRemoveDuplicates("11 21 31 41", "11 21 21 21 31 41 41 41 41");
        testRemoveDuplicates("11 21 31 41", "11 11 21 21 21 31 31 41 41 41 41");
        testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71 81 81");
        testRemoveDuplicates("11 21 31 41 51 61 71 81", "11 21 31 41 41 41 41 41 51 51 61 71 81");
        testRemoveDuplicates("11 21 31 41 51 61 71", "11 11 11 11 21 31 41 41 41 41 41 51 51 61 71");
        testRemoveDuplicates("11 21 31 41 51 61 71", "11 21 31 41 41 41 41 41 51 51 61 71");
        testRemoveDuplicates("-81 -71 -61 -51 -41 -31 -21 -11", "-81 -81 -81 -81 -71 -61 -51 -51 -51 -51 -41 -41 -31 -21 -11 -11 -11");
        testRemoveDuplicates("-11 0 11", "-11 -11 -11 0 0 11 11 11");
        testRemoveDuplicates("0 11", "0 11 11 11");
        testRemoveDuplicates("-Infinity 11", "-Infinity 11 11 11");
        testRemoveDuplicates("11 Infinity", "11 11 11 Infinity");
        testRemoveDuplicates("11", "11 11");
        testRemoveDuplicates("11", "11");
        testRemoveDuplicates("", "");

        StdOut.println("Finished tests");
    }

    /* Test functions --- lot's of similar code! */
    private static void testMinValue(double expected, String list) {
        double[] aList = doublesFromString(list);
        double actual = minValue(aList);
        if (!Arrays.equals(aList, doublesFromString(list))) {
            StdOut.format("Failed minValue([%s]): Array modified\n", list);
        }
        if (expected != actual) {
            StdOut.format("Failed minValue([%s]): Expecting (%.1f) Actual (%.1f)\n", list, expected, actual);
        }
    }

    private static void testMinPosition(int expected, String list) {
        double[] aList = doublesFromString(list);
        int actual = minPosition(aList);
        if (!Arrays.equals(aList, doublesFromString(list))) {
            StdOut.format("Failed minPosition([%s]): Array modified\n", list);
        }
        if (expected != actual) {
            StdOut.format("Failed minPosition([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual);
        }
    }

    private static void testDistanceBetweenMinAndMax(int expected, String list) {
        double[] aList = doublesFromString(list);
        int actual = distanceBetweenMinAndMax(aList);
        if (!Arrays.equals(aList, doublesFromString(list))) {
            StdOut.format("Failed distanceBetweenMinAndMax([%s]): Array modified\n", list);
        }
        if (expected != actual) {
            StdOut.format("Failed distanceBetweenMinAndMax([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual);
        }
    }

    private static void testAllSame(boolean expected, String list) {
        double[] aList = doublesFromString(list);
        boolean actual = allSame(aList);
        if (!Arrays.equals(aList, doublesFromString(list))) {
            StdOut.format("Failed allSame([%s]): Array modified\n", list);
        }
        if (expected != actual) {
            StdOut.format("Failed allSame([%s]): Expecting (%b) Actual (%b)\n", list, expected, actual);
        }
    }

    private static void testNumUnique(int expected, String list) {
        double[] aList = doublesFromString(list);
        int actual = numUnique(aList);
        if (!Arrays.equals(aList, doublesFromString(list))) {
            StdOut.format("Failed numUnique([%s]): Array modified\n", list);
        }
        if (expected != actual) {
            StdOut.format("Failed numUnique([%s]): Expecting (%d) Actual (%d)\n", list, expected, actual);
        }
    }

    private static void testRemoveDuplicates(String expected, String list) {
        double[] aList = doublesFromString(list);
        double[] actual = removeDuplicates(aList);
        if (!Arrays.equals(aList, doublesFromString(list))) {
            StdOut.format("Failed removeDuplicates([%s]): Array modified\n", list);
        }
        double[] aExpected = doublesFromString(expected);
        // != does not do what we want on arrays
        if (!Arrays.equals(aExpected, actual)) {
            StdOut.format("Failed removeDuplicates([%s]): Expecting (%s) Actual (%s)\n", list, Arrays.toString(aExpected), Arrays.toString(actual));
        }
    }


    /* A utility function to create an array of doubles from a string. */
    // The string should include a list of numbers, separated by single spaces.
    private static double[] doublesFromString(String s) {
        if ("".equals(s)) return new double[0]; // empty array is a special case
        String[] nums = s.split(" ");
        double[] result = new double[nums.length];
        for (int i = nums.length - 1; i >= 0; i--) {
            try {
                result[i] = Double.parseDouble(nums[i]);
            } catch (NumberFormatException e) {
                throw new IllegalArgumentException(String.format("Bad argument \"%s\": could not parse \"%s\" as a double", s, nums[i]));
            }
        }
        return result;
    }
}