CSE 131 Module 5: Methods

Important!

Before beginning any work, do a Team...Pull in your repository.

Lab


Warmup


We strongly suggest that you proceed one method at a time through the work below, testing each time to be sure what you have written so far is correct.

If you show up for help with a bunch of methods that don't work because you typed them all in before testing anything, we may not be able to help you until you clean up your code and focus on one method at a time.

Provided Methods: Strings

Do NOT use == for Strings.
We have provided a class Strings which provides some utility method for comparing two String instances. Feel free to use them for your solutions.
NOTE: This class Strings should not be confused with the standard Java class String for which its utility methods work on.

Linear Search

Open the provided file LinearSearch.java. In this file you will find the method findFirstIndexIn. Your solution can be tested directly with LinearSearchTestSuite.java.
  1. Watch this video from CS50
  2. Implement findFirstIndex to meet this specification below:
  3. /**
     * Searches the specified array for the specified key.
     * 
     * For example:
     * 
     * when array: { "W", "A", "S", "H", "U" } is paired with key: "S" return 2.
     * when array: { "W", "A", "S", "H", "U" } is paired with key: "Z" return -1.
     * when array: { "A", "B", "A", "B", "A" } is paired with key: "A" return 0.
     * when array: { "A", "B", "A", "B", "A" } is paired with key: "B" return 1.
     * 
     * This method must not mutate (that is: change the contents of) the specified
     * array, nor would it have any real reason to do so.
     * 
     * @param array the array to be searched
     * @param key   the value to be searched for
     * @return the index of the first occurrence of key, if it is contained in the
     *         array; otherwise -1.
     */
    public static int findFirstIndexIn(String[] array, String key) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
    *** Common mistake to avoid: Remember to delete the throw new NotYetImplementedException line.
    *** Common mistake to avoid: Do NOT use == when comparing if two Strings have the same contents. Use Strings.equals(a,b) instead.
At this point you should have run the JUnit test and determined whether your LinearSearch works properly. Don't push ahead until you pass the LinearSearchTestSuite part of the JUnit tests.

Continue the lab in this fashion: write code, test the code, and then move forward.

Sort

Open the provided file Sort.java. In this file you will find the methods findIndexOfLexicographicallyEarliestValue, swapValuesAtIndicesInPlace, selectionSortInPlace, and isSorted. Your solution can be tested directly with SortTestSuite.java.
  1. Watch this video from CS50
  2. Implement findIndexOfLexicographicallyEarliestValue to meet this specification:
    /**
     * Searches an array from a starting fromIndex for the index of the
     * lexicographically earliest value.
     * 
     * For example, when the array: { "A", "B", "D", "C", "E" } is paired with
     * fromIndex: 2 the search would check the values "D", "C", and "E" and return
     * the index of "C" which is 3.
     * 
     * This method must not mutate (that is: change the contents of) the specified
     * array, nor would it have any real reason to do so.
     * 
     * @param array     the array to search
     * @param fromIndex the index from which to search until the each of the array
     * @return the index of the lexicographically earliest value
     */
    public static int findIndexOfLexicographicallyEarliestValue(String[] array, int fromIndex) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
    
    
  3. Implement swapValuesAtIndicesInPlace to meet this specification:
    // WARNING
    // WARNING
    // WARNING: There is an error in the Javadoc in your provided code that reads 
    // WARNING: { "A", "D", "C", "B", E" } instead of { "A", "C", "D", "B", E" } 
    // WARNING: on the post swap result.  We apologize for the error.
    // WARNING
    // WARNING
    /**
     * Swaps the values in the specified array at aIndex and bIndex. This will
     * necessarily mutate (that is: change the contents of) the specified array.
     * 
     * For example: for array: { "A", "B", "D", "C", "E" }, aIndex: 1, and bIndex: 3
     * the specified array will be changed to { "A", "C", "D", "B", E" }.
     * 
     * @param array  the array to mutate
     * @param aIndex index whose value should be swapped with the value at
     *               array[bIndex]
     * @param bIndex index whose value should be swapped with the value at
     *               array[aIndex]
     */
    public static void swapValuesAtIndicesInPlace(String[] array, int aIndex, int bIndex) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
  4. Implement selectionSortInPlace to meet this specification:
    /**
     * Sorts the specified array into ascending lexicographical order. This will
     * necessarily mutate (that is: change the contents of) the specified array.
     * 
     * @param array the array to sort in place
     */
    public static void selectionSortInPlace(String[] array) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
  5. Implement isSorted to meet this specification:
    /**
     * Determines if the specified array is sorted in ascending lexicographical
     * order.
     * 
     * This method must not mutate (that is: change the contents of) the specified
     * array, nor would it have any real reason to do so.
     * 
     * @param array the array to determine whether or not it is sorted
     * @return true if the array is sorted, otherwise false.
     */
    public static boolean isSorted(String[] array) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
At this point you should have run the JUnit test and determined whether your Sort works properly. Don't push ahead until you pass the SortTestSuite part of the JUnit tests.

Binary Search

Open the provided file BinarySearch.java. In this file you will find the methods calculateMidPoint and findIndexInSorted. Your solution can be tested directly with BinarySearchTestSuite.java.
  1. Watch this video from CS50
  2. Watch this video on how to run the SearchTimingChartApp in the lab5.chart package:
  3. Implement calculateMidPoint to meet this specification:
    /**
     * Calculates the floored midpoint of two specified integer values.
     * 
     * For example: a: 300 and b: 400 returns 350. a: 300 and b: 401 also returns
     * 350. a: 300 and b: 402 returns 351.
     * 
     * @param a a value
     * @param b another value
     * @return the midpoint of a and b
     */
    public static int calculateMidPoint(int a, int b) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
  4. Implement findIndexInSorted to meet this specification:
    /**
     * Searches the specified sorted array for the value specified by key. If the
     * array contains key, then it returns an index which holds the value, otherwise
     * it returns -1. If array contains multiple elements with the specified key
     * value, there is no guarantee which index will be returned.
     * 
     * If the array is unsorted, then the results are undefined.
     * 
     * This method must not mutate (that is: change the contents of) the specified
     * array, nor would it have any real reason to do so.
     * 
     * @param array the array to be searched
     * @param key   the value to be searched for
     * @return an index of an occurrence of key, if it is contained in the array;
     *         otherwise -1.
     */
    public static int findIndexInSorted(String[] array, String key) {
    	throw new NotYetImplementedException("delete this line of code and implement this method.");
    }
    
    *** Common mistake to avoid: Do NOT use == when comparing if two Strings have the same contents. Use Strings.equals(a,b) instead.
    *** Common mistake to avoid: Do NOT simply call your linear search method or copy its code. The fact that the array is sorted allows you to do better, and so you must do better.
    *** WARNING
    *** WARNING
    *** WARNING
    *** WARNING: It cannot be stated strongly enough: do not simply assume that because your code passes all the tests, that you will be fine. At a minimum you should also ensure that your code is also performing well with the SearchTimingChartApp. Further, your TA will be reviewing your code to assess your algorithm.
    *** WARNING
    *** WARNING
    *** WARNING
At this point you should have run the JUnit test and determined whether your BinarySearch works properly. That is: you pass the BinarySearchTestSuite part of the JUnit tests and the SearchTimingChartApp chart demonstrates the appropriate performance improvement.
Be prepared to run the all-inclusive Lab5TestSuite and the SearchTimingChartApp to demo your working solutions.

Submitting your work (read carefully)



Last modified 01:52:18 CDT 21 October 2018
When you are done with this lab, you must be cleared by the TA to receive credit.

This demo box is for lab 5
Last name WUSTL Key Propagate?
(NOT your numeric ID) Do not propagate
lower case only
e.g. Smith j.smith
1    

Acknowledgements and assertion of integrity

You must select one of the options below
The work submitted here was performed in accordance with this course's policy on collaboration.
On your honor, you have neither given nor received any unauthorized aid on this assignment.

However, the following TAs, students, or professors were supportive in completing this assignment.
Their help was also in accordance with course policies.

Thanks to (leave blank if appropriate):

In spite of seeking help as allowable by this course's policy on collaboration, you were unable to complete this assignment. No credit will be received for this assignment.

You would like to be contacted by an instructor to facilitate staying on track in this course.

Comments about this:

You have NOT abided by this course's policy on collaboration. No credit will be received for this assignment, but by checking this box, no academic integrity violation will be filed for this assignment.

You would like to be contacted by an intructor to faciliate staying on track in this course.

Comments about this:


TAs double check!
  • This demo box is for lab 5
  • The student has committed and pushed the work, and verified that it appears at bitbucket.
TA: Password: