Computer Science 210
Data Structures

Fall 2017, Siena College

Lab 5: Searching and Sorting
Due: start of your lab, Wednesday, October 25, 2017

This week, we will practice more with recursion, and experiment with searching and sorting.

You will be assigned a partner on this lab. Only one submission per group is needed.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository searchingsorting-lab-yourgitname for this Lab. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub. At least one group member should make a clone of the repository to begin work.

Please answer lab questions in the file in your group's GitHub repository.

Recursion on Arrays

Your first task is to fill in the methods in Each is worth 10 points. You may test by writing a main method or by calling the methods within BlueJ and providing appropriate parameters.

No loops!

Recursive Call Trees

Consider the recursive method below for summing the values in an array from position first to last, inclusive. Below the method is the recursive call tree showing all the recursive calls made when the method is initially invoked with the array A containing values {5, 2, 4, 1, 6} and first = 0 and last = 4. The lines show the recursive calls made, and the number next to the line shows the value returned by the call.

public static int sum(int[] A, int first, int last) {
    if (first == last) {
        return A[first];
    else {
        int mid = (first + last) / 2;
        int left = sum(A, first, mid);
        int right = sum(A, mid+1, last);
        return left + right;

Question 1: There are several parameters, values of mid, and return values (on the blue lines) missing from the diagram. Please give their values. (5 points total)

Question 2: For your implementation of count100 from earlier in the lab, draw the recursive call tree corresponding to the call count100(A, 0, 5) where A is the array {100, 100, 100, 98, 100, 82}. Draw your tree in the same style used in the previous question, with the lines labeled with the return values and the return value of the initial call on a line segment extending above the initial call. You may draw this on paper and upload a picture if you prefer. (7 points)

Question 3: Consider the following recursive method method named mystery. Determine what it does by drawing a recursive call tree corresponding to the initial call mystery("", 3). (The first argument is an empty string.) Note that this method doesn't return a value; it instead prints something each time it reaches the base case. You may draw this on paper and upload a picture if you prefer. Be sure to include both your recursive call tree and the output produced. (8 points)

public static void mystery(String s, int d) {
    if (d == 0) {
        System.out.print(s + " ");
    else {
        mystery(s + "0", d - 1);
        mystery(s + "1", d - 1);

Making Ratios Comparable

For the second part of the lab assignment, you will be seeing how we can create our own Comparable objects that could be used with generic code like the search methods in the BinSearch example. Both and are in your repository. Put the names of all group members working on this task in those files now. Yes, do it now. Now. Really. Don't make me ask you again.

  1. Have the Ratio class implement the Comparable interface. So the class header would become:
    public class Ratio implements Comparable<Ratio>

    This tells Java that this class can be treated as a "comparable" object like Integer, Double, String, and many others.

    If you try to compile now (do it), you should get an error message something like

    Ratio is not abstract and does not override abstract method
    compareTo(Ratio) in Comparable

    This means that you said Ratio objects are comparable but didn't tell Java how to do that comparison. We do it in the same way that we compare other objects: by providing a compareTo method.

  2. Write a compareTo method in the Ratio class. It will need to have a method header like this:
        public int compareTo(Ratio other)

    For now, have your method simply return 0 in all cases. You should now be able to compile again.

  3. Now, make the compareTo method work properly.

    Your only experience so far with compareTo methods is probably the one built in to the String class. Recall that for String references s1 and s2, the call


    will return 0 if s1.equals(s2); a value less than 0 if this s1 is lexicographically less than s2; and a value greater than 0 if s1 is lexicographically greater than s2.

    For Ratio objects, we want to do the same thing: if we have two Ratio objects r1 and r2, the call


    should return 0 if r1.equals(r2) (keep in mind this means that the 1/2 should be equal to 3/6); a value less than 0 if this r1 is less than r2; and a value greater than 0 if r1 is greater than r2.

    It doesn't matter what positive or negative value you return, as long as it's positive when it should be, negative when it should be, and 0 when they're equal. (10 points)

  4. Write a short main method in your modified Ratio class to test your new compareTo method. Be sure all three possible return values are tested. (5 points)
  5. Add code to the main method of BinSearch that creates an array of several Ratio objects and peforms a variety of successful and unsuccessful searches. Be sure to test all important cases. (5 points)


Read the topic notes about selection sort and insertion sort and look at the recursive implementations of those algorithms in the SortingComparisons example.

Question 4: Trace through the execution of selSort(a) when a is an array of Integer containing the values {8, 3, 0, 4}. Show the parameters passed on each recursive call and show the contents of a at the start and end of each recursive call. (10 points)

Question 5: Repeat the above for insSort(a). (10 points)


Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.


This assignment is worth 100 points, which are distributed as follows:

> FeatureValueScore
maximum method 10
count100 method 10
negatives method 10
prefixSum method 10
Q1: sum call tree 5
Q2: count100 call tree 7
Q3: mystery method trace 8
Ratio compareTo method 10
Ratio main method tests 5
BinSearch main method Ratio tests 5
selSort trace 10
insSort trace 10
Total 100