Lab 4: Recursion with multiple calls; sorting and big-O; debugging practice

Task 1: Tracing a method that makes multiple recursive calls

Your work for the first two tasks should go on the piece of paper that we give you. Please show your paper to a staff member before you leave the lab.

A number of the algorithms that we consider in CS 112 involve recursive methods in which a given invocation of the method may make two or more recursive calls. To understand how this type of algorithm works, it helps to use a diagram known as a call tree.

Let’s work together to develop a call tree for the execution of the following recursive method. (The method allows us to recursively generate the nth integer in the Fibonacci sequence, although you don’t need to be familiar with that sequence to understand this problem.)

public static int fib(int n) {
    if (n == 0 || n == 1) {
        return 1;
    } else {
        int prev1 = fib(n - 2);
        int prev2 = fib(n - 1);
        return prev1 + prev2;
    }
}

Assume that we begin with the following initial call to this method:

fib(4)

1. Let’s draw a call tree for the sequence of calls that are involved in computing the result of fib(4). As we do so, we’ll number each call of the method in the order in which they are made.

2. The order in which the calls are made is not the same as the order in which the calls return. A given invocation of the method can’t return until both of the calls that it makes (fib(n - 2) and fib(n - 1)) return.

   Underneath your call tree, list the order in which the calls return, as well as their return values. When you refer to a given call in this part of the problem, use its number from the call tree.

   For example, the initial call always returns last, so the last line in this part of the problem should look like this:

   call 1 (fib(4)) returns ...
   

   where you replace the ... with its return value.

Task 2: Learn and analyze bubble sort

In lecture, you have begun to learn about some of the many algorithms that are available for sorting arrays of values.

Today we’re going to learn about another such algorithm: bubble sort. Bubble sort performs a sequence of passes through the array. On each pass, it proceeds from left to right, swapping adjacent elements if they are out of order. As a result, larger elements “bubble up” to the end of the array.

For example, consider the following array:

First pass
Bubble sort compares elements 0 and 1 (the 28 and 24), and because they are out of order, it swaps them:

It then compares elements 1 and 2 (the 28 in its new position and 27), and because they are out of order, it swaps them:

Finally, it compares elements 2 and 3 (the 28 in its new position and 18), and because they are out of order, it swaps them:

Note that the largest element (the 28) has bubbled up to its final position, so we don’t need to consider it on the next pass.

Second pass
Bubble sort compares the elements 0 and 1 (the 24 and 27), and because they are in order, it leaves them alone:

It then compares elements 1 and 2 (the 27 and 18), and because they are out of order, it swaps them:

And the second pass ends there.

Note that the second largest element (the 27) has bubbled up to its final position, so we don’t need to consider it on the next pass.

Third pass
Bubble sort compares elements 0 and 1 (the 24 and 18), and because they are out of order, it swaps them:

And the third pass ends there.

Note that the third largest element (the 27) has bubbled up to its final position, so we don’t need to consider it on the next pass.

And because there is only one remaining element that hasn’t been bubbled up, the algorithm ends, and the array is sorted.

1. Trace bubble sort on the following array:

   7

   39

   20

   11

   16

   5

   Show what the array looks like after each swap that occurs.

2. Here is the implementation of bubble sort from our Sort class:

   public static void bubbleSort(int[] arr) {
       for (int i = arr.length - 1; i > 0; i--) {
           for (int j = 0; j < i; j++) {
               if (arr[j] > arr[j+1]) {   // how many comparisons?
                   swap(arr, j, j+1);
               }
           }
       }
   }
   

   Note that:

   • The inner loop performs a single pass.

   • The outer loop governs the number of passes, and the ending point of each pass.

   Let’s determine a formula for the number of comparisons of array elements that bubble sort performs when operating on an array of length n.

   To do so, it can help to begin by filling in a table like this one:

   pass #       # of comparisons
   ------       ----------------
      1              n - 1
   

   1. Fill in the next few rows of this table, and see if you notice a pattern.

   2. How can we take the pattern revealed by the table and use it to derive an exact formula for the number of comparisons?

   3. Given that formula, what is the big-O expression for the number of comparisons performed by bubble sort?

   4. The number of moves performed by bubble sort depends on the contents of the array. How many are performed as a function of n:

      • in the best case?
      • in the worst case?
      • in the average case?

   5. What is the big-O expression for the overall running time of bubble sort?

Task 3: Debugging practice

This task will give you practice in debugging a program. Begin by downloading the following file: DateSubtracter.java and opening it in DrJava.

DateSubtracter is a simple, non-object-oriented program that determines the number of days between two pairs of dates. In addition to the main method, there are two static methods:

• int daysBetween(int month1, int day1, int month2, int day2):
  This method should compute and return the number of days between the two dates specified by the parameters. For example, to find the number of days between October 31 (10/31) and November 7 (11/7), we would call daysBetween(10,31,11,7), which should return 7.

• int daysBefore(int month): This method should return the number of days that occur each year before the month specified by the parameter. For example, to find the number of days before March (month 3), we would call daysBefore(3), which should return 59 (because there are 31 days in January and 28 days in February).

This program has two bugs, and you should address them in the following order:

1. a runtime exception: Compile the program and run it. You should get the following error message:

   java.lang.ArrayIndexOutOfBoundsException: 12
         at DateSubtracter.daysBefore(DateSubtracter.java:39)
         at DateSubtracter.daysBetween(DateSubtracter.java:52)
         at DateSubtracter.main(DateSubtracter.java:17)
   

   followed by some additional lines.

   The first line of the error message reports that an ArrayIndexOutOfBoundsException occurred, and it gives the offending array index (12). The remaining lines of the error message give a backtrace of the method calls that produced the exception:

   • The first line in the backtrace tells us that the actual exception occurred at line 39 of DateSubtracter.java, inside the daysBefore() method.

   • The second line tells us that the call to daysBefore() occurred on line 52, inside the daysBetween() method.

   • The third line tells us that the call to daysBetween() occurred on line 17, inside the main() method.

   Take whatever steps are needed to prevent the exception from occurring. (You don’t need to get the program to produce correct output at this point. It just needs to run to completion without crashing.)

   You may find it helpful to add temporary print statements, or to employ another of our recommended debugging tips.

2. a logic error: Once you have fixed the first bug, you can move on to handle the second one. This bug doesn’t cause an exception, but it causes the program to compute one or more wrong values, along with a corresponding message that indicates the problem. Take whatever steps are needed to fix the logic error and produce the correct output. You should only need to modify a single line of code.

Extra Practice!

If you get through the exercises above, congratulations!
For extra practice, try the Practice Problems for Midterm 1.

Task 4: Submit your work

You should show the paper with your work on Tasks 1 and 2 to the teaching assistant.

You should use Apollo to submit the following file:

• your modified DateSubtracter.java file containing the changes you made in Task 3

Don’t worry if you didn’t finish all of the tasks. You should just submit whatever work you were able to complete during lab.

Here are the steps:

1. Login to Apollo, using the link in the left-hand navigation bar. You will need to use your Kerberos user name and password.
2. Check to see that your BU username is at the top of the Apollo page. If it isn’t, click the Log out button and login again.
3. Find the appropriate lab section on the main page and click Upload files.
4. For each file that you want to submit, find the matching upload section for the file. Make sure that you use the right section for each file. You may upload any number of files at a time.
5. Click the Upload button at the bottom of the page.
6. Review the upload results. If Apollo reports any issues, return to the upload page by clicking the link at the top of the results page, and try the upload again, per Apollo’s advice.
7. Once all of your files have been successfully uploaded, return to the upload page by clicking the link at the top of the results page. The upload page will show you when you uploaded each file, and it will give you a way to view or download the uploaded file. Click on the link for each file so that you can ensure that you submitted the correct file.