AP Computer Science Study Guide

Introduction

Java is a good language for programming. It has a wealth of features and large libraries of code for almost anything you could want to do with a program. Had I had a year with a class I would have endeavored to teach them as much of Java as I could. Luckily for AP Computer Science students I am not in charge of the test. Instead you have a much smaller scope of knowledge to deal with. I have said before you should download the AP course description from the College Board website. It details exactly what subject matter you should be familiar with.

Test Taking Strategy

There are no point reductions for wrong answers so you should strive to answer all the multiple choice questions. With 5 minutes left to go you should stick in any answer in the blank problems then go back and see how many you can answer. Every question should have an answer! Don't take so much time that you have blanks on your computer answer sheet.

You have 2 minutes per problem (less really). You can't get stuck for 5 minutes on any one problem. You should quickly go through the test and find all questions you can answer quickly and easily. The worst thing you can do is get stuck on a problem and leave 5 easy questions unanswered at the end of the test.

When you take practice tests you should compile a list of which type of problems take you the longest and which type are you more inclined to get wrong. Then save these for last. Once you realize a question falls into that category guess an answer (put down D or E or something) don't even do an educated guess. Mark the problem to come back to and continue. Once you get through the test the first time now go back and answer the questions you had to guess on. Now you can take a little bit more time on each problem. You will be confident that you have found all the easy "get-able" questions and now you are just working to improve your score.

DANGER: Don't missalign problems in your bubble sheet because you skipped them. You should certainly practice this method on a couple of practice tests before you do it on the real exam. By practice I mean get a bubble sheet and take the test on the bubble sheet then check your answers to make sure you did not misalign anything.

The AP Computer Science Java Subset

Base types

• int, double, boolean

Arithmetic operators

Operator	Name
+	addition
-	subtraction
*	muliplication
/	division
%	modulo

Comparison Operators

Operator	Name	Function
==	equals	test if equal to
!=	not equals	test if not equal to
<	less than	test if left value 'less than' right value
<=	less than or equal to	test if left 'less than or equal to' right
>	greater than	test if left 'greater than' right
>=	greater than or equal to	test if left 'greater than or equal to' right

Logical Comparisons

Operator	Name	Function
&&	and	returns true if both left and right values are true otherwise it returns false
||	or	returns false if both left and right values are false otherwise it returns true
!	not	returns the opposite of the right hand value true becomes false and vise versa

NOTE: The && and || 'short circuit' because of the fact that any false value in && makes the whole statement false further processing does not have to occur the compiler can immediately choose the else clause. The same but opposite happens for || except as soon as the compiler finds a true value it can go into the next statement in the if portion of an if-then-else statement

Assignment Operators

Operator	Function
=	assign value of right hand side (RHS) to variable on left hand side (LHS)
+=	LHS = LHS + RHS
-=	LHS = LHS - RHS
*=	LHS = LHS * RHS
/=	LHS = LHS / RHS
%=	LHS = LHS % RHS
(int)	truncates double giving the int portion: int myvar = (int) 32.25 //myvar = 32
(double)	makes a double value out of an int value so +-*/ operations return double values

The Study Guide in Code

To help you study for the AP exam I have gone through the subset and placed comments for each of the subset items. Then for a portion of it I have implemented examples of the subset. To save some typing I have implemented 'log' methods to simplify the output. Between the code and the output you should have a pretty good idea of what the subset entails and what you are responsible to know. Hopefully I will have time to provide you a completed sheet that way you may have some extra examples of code going into the AP test.

Don't forget to check out the updated version in the blog post at the following link:
Study Guide take 2

/*
 * This Class definition is to give an example of using everything in 
 * the Java subset used on the AP exam. Use this as a learning tool and 
 * add in code from test questions where you weren't sure how the compiler
 * would handle the code. It will become your study guide for the AP exam.
 * This is not a substitute for reading the course pdf file on the College
 * Board site. 
 */
package apcompsci;

/**
 *
 * @author nasty old dog
 */
public class APSubset {

    public static void log(String str)
    {
        System.out.print("APSubset: ");
        System.out.println(str);
    }

    public static void log_array(String str, int[] arr)
    {
        System.out.print("APSubset: ");
        System.out.print(str);
        for (int i : arr){
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public static void main (String[] args)
    {
        // Basic types: int, double, boolean
        int a = 0;
        double b = 0.0;
        boolean c = false;
        log("BASIC TYPES");
        log("int a = " + a);
        log("double b = " + b);
        log("boolean c = " + c);

        // Basic operators: +, -, *, /, %
        log("\n");
        log("BASIC OPERATORS");
        a = 1 + 2;
        log("int a = 1 + 2 = " + a);
        b = 2.0 + 3.5;
        log("double b = 2.0 + 3.5 = " + b);
        a = 2 - 3;
        log("int a = 2 - 3 = " + a);
        b = 2.0 - 3.5;
        log("double b = 2.0 - 3.5 = " + b);
        a = 2 * 3;
        log("int a = 2 * 3 = " + a);
        b = 2.0 * 3.5;
        log("double b = 2.0 * 3.5 = " + b);
        a = 3 / 2;
        log("int a = 3 / 2 = " + a);
        b = 3.5 / 2.0;
        log("double b = 3.5 / 2.0 = " + b);
        a = 17 % 5;
        log("int a = 17 % 5 = " + a);
        b = 17.0 % 6.0;
        log("double b = 17.0 % 6.0 = " + b);

        // To show modulo(remainder) lets show the division first

        // preincrement/postincrement predecrement/postdecrement
        // These are used for their side effects and never inside an expression
        // mainly for loop increment/decrement
        log("\n");
        log("Pre/Post-increment and Pre/Post-decrement");
        log("int a = " + a);
        log("a++ = " + a++);
        log("int a = " + a);
        log("++a = " + ++a);
        log("int a = " + a);
        log("a-- = " + a--);
        log("int a = " + a);
        log("--a = " + --a);
        log("int a = " + a);

        log("double b = " + b);
        log("b++ = " + b++);
        log("double b = " + b);
        log("++b = " + ++b);
        log("double b = " + b);
        log("b-- = " + b--);
        log("double b = " + b);
        log("--b = " + --b);
        log("double b = " + b);

        // Assignment operators: +=, -=, *=, /=, %=
        log("\n");
        log("Assignment operators +=, -=, *=, /=, %=");
        a = 13;
        log ("int a = " + a);
        b = 13.0;
        log ("double b = " + b);
        a += 7;
        log ("int a += 7 = " + a);
        b += 7.5;
        log ("double b += 7.5 = " + b);
        a -= 3;
        log ("int a -= 3 = " + a);
        b -= 3.5;
        log ("double b -= 3.5 = " + b);
        a *= 2;
        log ("int a *= 2 = " + a);
        b *= 2.0;
        log ("double b *= 2.0 = " + b);
        a /= 2;
        log ("int a /= 2 = " + a);
        b /= 2.0;
        log("double b /= 2.0 = " + b);
        a %= 5;
        log("int a %= 5 = " + a);
        b %= 6.0;
        log("double b %= 6.0 = " + b);

        // Relational operators: == != < <= > >=
        c = 1 == 1;
        log("boolean c = 1 == 1 = " + c);
        c = 2 != 3;
        log("boolean c = 2 != 3 = " + c);
        c = 2 < 1;
        log("boolean c = 2 < 1 = " + c);
        c = 2 < 3;
        log("boolean c = 2 < 3 = " + c);
        c = 2 <= 4;
        log("boolean c = 2 <= 4 = " + c);
        c = 2 <= 2;
        log("boolean c = 2 <= 2 = " + c);
        c = 4 > 1;
        log("boolean c = 4 > 1 = " + c);
        c = 4 >= 5;
        log("boolean c = 4 >= 5 = " + c);
        c = 5 >= 5;
        log("boolean c = 5 >= 5 = " + c);
        // Logic operators || && ! short circuit evaluation
        log("\n");
        log("Logical Operators ||, &&, !");
        c = true || true;
        log("boolean c = true || true = " + c);
        c = true || false;
        log("boolean c = true || false = " + c);
        c = false || false;
        log("boolean c = false || false = " + c);
        c = true && true;
        log("boolean c = true && true = " + c);
        c = true && false;
        log("boolean c = true && false = " + c);
        c = false && false;
        log("boolean c = false && false = " + c);
        int d[] = null;
        if (d != null && d[1]==2) {
            // The d[1] is an illegal operation ArrayOutofBounds error
            // But because d == null it never gets executed due to the 
            // short circuit
        }
        else {
            log("int[] d = null: in else clause due to short circuit");
        }
        d = new int[] {1,2,3,4,5};
        if (d != null && d[1]==2) {
            // The d[1] is an illegal operation ArrayOutofBounds error
            // But because d == null it never gets executed due to the 
            // short circuit
            log_array("int[] d = ",d);
        }
        // numeric casts (int) and (double))
        b = 5.0 / 2;
        log("double b = 5.0/2 = " + b);
        b = (int) b;
        log ("double b = (int) b = " + b);
        a = (int) 5.0/2;
        log ("int a = (int) 5.0/2 = " + a);
        b = 5.0 / (int) 2;
        log("double b = 5.0/(int) 2 = " + b);
        b = (int) 5.0 / (int) 2;
        log("double b = (int) 5.0/(int) 2 = " + b);
        b = ((int) 5.0) / (double) 2;
        log("double b = ((int) 5.0)/(double) 2 = " + b);
        b = ((int) 5.0) / 2;
        log("double b = ((int) 5.0)/ 2 = " + b);

        // String concatenation
        // String escape sequences: \\, \n, \"
        // One Dimensional Arrays
        // Two Dimensional Arrays
        // if stm
        // if-else stm
        // while
        // for
        // for each
        // method over loading
        // new operator
        // public and private
        // java comments /* // and /** @param and @return
        // final for variables and final class scope
        // static methods static variables
        // null
        // this forget what I told you they don't care about it.
        // Super
        // Initialize all variables in constructors implicit initialization is not in subset
        // extend classes and implement interfaces method overriding and polymorphism
        // interface and abstract classes
        // difference between = and ==
        // Conversion from Subclass to Superclass and Class casts from Object to another class
        // import specific classes
        // Generic Class (need to know how it works won't be required to implement)
        // String.compareTo()
        // Exceptions
        // Standard Classes: String, Math, List, ArrayList
        // Wrapper classes: Integer, Double
        // Class java.lang.Object: equals(Object other) toString()
        // Class java.lang.Integer
        // Class java.lang.Double
        // Class java.lang.String
        // Class java.lang.Math
        // Interface java.util.List<E>
        // Interface java.util.ArrayList<E>
    }
}

Output

run:
APSubset: BASIC TYPES
APSubset: int a = 0
APSubset: double b = 0.0
APSubset: boolean c = false
APSubset: 

APSubset: BASIC OPERATORS
APSubset: int a = 1 + 2 = 3
APSubset: double b = 2.0 + 3.5 = 5.5
APSubset: int a = 2 - 3 = -1
APSubset: double b = 2.0 - 3.5 = -1.5
APSubset: int a = 2 * 3 = 6
APSubset: double b = 2.0 * 3.5 = 7.0
APSubset: int a = 3 / 2 = 1
APSubset: double b = 3.5 / 2.0 = 1.75
APSubset: int a = 17 % 5 = 2
APSubset: double b = 17.0 % 6.0 = 5.0
APSubset: 

APSubset: Pre/Post-increment and Pre/Post-decrement
APSubset: int a = 2
APSubset: a++ = 2
APSubset: int a = 3
APSubset: ++a = 4
APSubset: int a = 4
APSubset: a-- = 4
APSubset: int a = 3
APSubset: --a = 2
APSubset: int a = 2
APSubset: double b = 5.0
APSubset: b++ = 5.0
APSubset: double b = 6.0
APSubset: ++b = 7.0
APSubset: double b = 7.0
APSubset: b-- = 7.0
APSubset: double b = 6.0
APSubset: --b = 5.0
APSubset: double b = 5.0
APSubset: 

APSubset: Assignment operators +=, -=, *=, /=, %=
APSubset: int a = 13
APSubset: double b = 13.0
APSubset: int a += 7 = 20
APSubset: double b += 7.5 = 20.5
APSubset: int a -= 3 = 17
APSubset: double b -= 3.5 = 17.0
APSubset: int a *= 2 = 34
APSubset: double b *= 2.0 = 34.0
APSubset: int a /= 2 = 17
APSubset: double b /= 2.0 = 17.0
APSubset: int a %= 5 = 2
APSubset: double b %= 6.0 = 5.0
APSubset: boolean c = 1 == 1 = true
APSubset: boolean c = 2 != 3 = true
APSubset: boolean c = 2 < 1 = false
APSubset: boolean c = 2 < 3 = true
APSubset: boolean c = 2 <= 4 = true
APSubset: boolean c = 2 <= 2 = true
APSubset: boolean c = 4 > 1 = true
APSubset: boolean c = 4 >= 5 = false
APSubset: boolean c = 5 >= 5 = true
APSubset: 

APSubset: Logical Operators ||, &&, !
APSubset: boolean c = true || true = true
APSubset: boolean c = true || false = true
APSubset: boolean c = false || false = false
APSubset: boolean c = true && true = true
APSubset: boolean c = true && false = false
APSubset: boolean c = false && false = false
APSubset: int[] d = null: in else clause due to short circuit
APSubset: int[] d = 1  2  3  4  5  
APSubset: double b = 5.0/2 = 2.5
APSubset: double b = (int) b = 2.0
APSubset: int a = (int) 5.0/2 = 2
APSubset: double b = 5.0/(int) 2 = 2.5
APSubset: double b = (int) 5.0/(int) 2 = 2.0
APSubset: double b = ((int) 5.0)/(double) 2 = 2.5
APSubset: double b = ((int) 5.0)/ 2 = 2.0
BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

You shouldn't wait for me to finish this. Go ahead and take on the task yourself. By implementing each part of the Java AP subset you will further enhance your knowledge. In previous articles I have deviated from the subset to help you understand some basic programming concepts and constructs. But you should start to tailor your studying specifically for the AP (at this time the AP is about a month away for 2013).

If you haven't started doing practice test you should start. Anycode you had problems with you should add to this study guide. By the time you get through 3 or 4 tests you should be an expert on the AP subset and know exactly what to expect in May. Remember in the free response questions to limit yourself to the AP subset. If your course was taught properly you should have learned more Java than you need for the test. Now however it's time to focus on the subset.

You should develop your test taking strategy as you take practice exams. Make sure you time yourself to the amount of time the AP exam allows for each section (at least on a couple of practice tests). Your strategy is working if you 1) answer all questions and 2) did not have to guess on otherwise easy problems.

References

1. https://apstudent.collegeboard.org/apcourse/ap-computer-science-a/course-details "Course Details." AP Computer Science A. N.p., n.d. Web. 29 Mar. 2013.

Author: Nasty Old Dog

Merge Sort

Introduction

Merge sort works based on the fact that it is relatively easy to take 2 sorted lists and merge them into a larger sorted list. Once we have a merge operation the rest of the sorting routine is relatively simple. Merge sort is also a faster sorting algorithm than either selection sort or insertion sort (on moderate sized lists or arrays anyway). It has to do with the divide and conquer structure of the recursive solution. Merge sort's one draw back is that it is memory intensive. At each level of recursion a new list has to be created to hold the merged smaller lists until the program get's back to the top level call where a new list of sorted elements is provided. In the other 2 sorts the sorting is done inline and only a 'tmp' variable is needed to swap the values when necessary. Memory used to be a big thing now adays not so much. Memory for computers is relatively cheap and many gigabytes may be had for a few hundred dollars.

Merge operation

I will develop the merge sort in the same SortLab class as the other sort routines. First step in the merge sort is let's develop the merge operation.

Specifications

• Take two int[] parameters that are assumed to be sorted
• return a new int[] whose length is the size of list1.length + list2.length
• The returned int[] should have its elements sorted in ascending order

Even though the lists are sorted this operation needs to track a few things:

• One array may run out of elements early at which point just add in the last elements from the other array
• Even if they alternate they may not alternate evenly so we must track where we are in each contributing array
• In the first round of testing merge will be a static routine. Once we go to a full merge sort we will instantiate an object as we did for the other routines

merge code

public static int[] merge(int[] a, int[] b)
{
    int[] m = new int[a.length + b.length];
    int i=0;
    int j=0;

    for (int k = 0; k < m.length; k++)
    {
        if (i < a.length && j < b.length) {
        if (a[i]<=b[j]) {
            m[k] = a[i];
            i++;
        }
        else {
            m[k] = b[j];
            j++;
        }
        }
        else if (i < a.length) {  // b exhausted use up a
            m[k] = a[i];
            i++;
        }
        else { // b still has some left use up those
            m[k] = b[j];
            j++;
        }
    }
    return m;
}

public static void main(String[] args) {
    SortLab select = new SortLab();
    SortLab selectA = new SortLab();
    SortLab insert = new SortLab();
    SortLab insertA = new SortLab();

    System.out.println("Selection Sort");
    System.out.print("unsorted: ");
    select.display();
    select.selection();
    System.out.print("sorted:   ");
    select.display();
    System.out.println("SelectionA Sort");
    System.out.print("unsorted: ");
    selectA.display();
    selectA.selectionA();
    System.out.print("sorted:   ");
    selectA.display();
    System.out.println();
    System.out.println();
    System.out.println("Insertion Sort");
    System.out.print("unsorted: ");
    insert.display();
    insert.insertion();
    System.out.print("sorted:   ");
    insert.display();
    System.out.println("Insertion Sort with Explicit Shift");
    System.out.print("unsorted: ");
    insertA.display();
    insertA.insertion();
    System.out.print("sorted:   ");
    insertA.display();

    System.out.println("Merge Testing");
    int[] l1 = {0, 2, 3, 4, 6, 7, 9};
    int[] l2 = {1, 3, 5, 8, 10};
    int[] l3 = merge(l1,l2);
    for (int i : l3)
    {
        System.out.print(i + " ");
    }
    System.out.println();
}    

Output 1

run:
Selection Sort
unsorted: 9  6  2  1  3  7  8  4  0  5  
interim:  0  6  2  1  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  6  3  7  8  4  9  5  
interim:  0  1  2  3  6  7  8  4  9  5  
interim:  0  1  2  3  4  7  8  6  9  5  
interim:  0  1  2  3  4  5  8  6  9  7  
interim:  0  1  2  3  4  5  6  8  9  7  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 9  0  5  7  2  8  4  3  1  6  
interim:  0  9  5  7  2  8  4  3  1  6  
interim:  0  1  5  7  2  8  4  3  9  6  
interim:  0  1  2  7  5  8  4  3  9  6  
interim:  0  1  2  3  5  8  4  7  9  6  
interim:  0  1  2  3  4  8  5  7  9  6  
interim:  0  1  2  3  4  5  8  7  9  6  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 3  0  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  3  5  2  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  5  6  4  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  2  3  4  5  6  7  9  1  8  
interim:  0  1  2  3  4  5  6  7  9  8  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 1  9  3  8  5  7  6  4  0  2  
interim:  1  9  3  8  5  7  6  4  0  2  
interim:  1  3  9  8  5  7  6  4  0  2  
interim:  1  3  8  9  5  7  6  4  0  2  
interim:  1  3  5  8  9  7  6  4  0  2  
interim:  1  3  5  7  8  9  6  4  0  2  
interim:  1  3  5  6  7  8  9  4  0  2  
interim:  1  3  4  5  6  7  8  9  0  2  
interim:  0  1  3  4  5  6  7  8  9  2  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Merge Testing
0 1 2 3 3 4 5 6 7 8 9 10 

Splitting the list

Splitting is the next thing to tackle, the straight forward way would be to just add the beginning index and the ending index together and divide by 2. This cuts the list in half. If we start with a list with 10 things in it, the starting index = 0 and the ending index = 9. (0+9)/2 = 4 we split the list after four (4). This gives us 2 lists from 0 - 4 and 5 - 9. We then want to split the list again and again until ideally all we are left with is 10 single element list. If you work this out on various size arrays you end up needing to help a little when you get to a pair of indexes. So my implementation will treat single indexes and pair indexes as the test case for recursion.

Given the above for background lets look at some pseudo code. I will assume that the original list is the labArray field and mergesort will track indexes into that array.

public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
    return newArray;
  }
  int split = (begin + end)/2;
  return merge(mergesort(begin, split), mergesort(split+1,end));
}

This works rather nicely. I have made some changes to the actual code over the above pseudo code to display interim results during the merge sort. The full code includes all the sorting routines we have done so far and the work on merge. Finally the code for the mergesort routine itself. It's implemented as a recursive routine as shown in the pseudocode.

The new routines I've added a new display(int[] array) method to display the new arrays that get built during the mergesort. I have also changed all 'for' statements to the for-each version where possible so you can compare it's use to a standard for loop in the previous implementation. I also use the 'display' methods where I can.

Final Code

/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package apcompsci;

/**
 *
 * @author Nasty Old Dog
 */
public class SortLab {

    int[] labArray = null;
    int len = 10;

    public SortLab(int n) {
        this.len = n;
        labArray = new int[this.len];
        for (int i = 0; i < this.len; i++) {
            labArray[i] = i;
        }
        this.shuffle();
    }

    public SortLab() {
        this(10);
    }

    // This shuffle routine adapted from the work done previously
    private void shuffle() {
        int rindex;
        int swap;

        for (int i = 0; i < this.len; i++) {
            rindex = (int) ((Math.random() * ((double) (this.len - i))) + i);
            swap = this.labArray[i];
            this.labArray[i] = this.labArray[rindex];
            this.labArray[rindex] = swap;
        }
    }

    void swap(int k, int l) {
        int tmp;

        tmp = this.labArray[k];
        this.labArray[k] = this.labArray[l];
        this.labArray[l] = tmp;
    }

    public void display() {
        for (int i : this.labArray) {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void display(int[] array) {
        for( int i : array)
        {
            System.out.print(i + "  ");
        }
        System.out.println();
    }

    public void selection() {
        int tmp, tmp_idx;

        for (int i = 0; i < this.len - 1; i++) {
            //select the ith element save value and index
            tmp = this.labArray[i];
            tmp_idx = i;
            // Check if selected is the lowest of the remaining array
            // if not switch them
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    // found something less save it and it's index
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            // if tmp_idx != i then swap the values (move the lowest val in)
            if (tmp_idx != i) {
                this.labArray[tmp_idx] = this.labArray[i];
                this.labArray[i] = tmp;
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    // Alternate implementation of selection sort using swap function 
    public void selectionA() {
        int tmp, tmp_idx;
        for (int i = 0; i < this.len - 1; i++) {
            tmp = this.labArray[i];
            tmp_idx = i;
            for (int j = i + 1; j < this.len; j++) {
                if (this.labArray[j] < tmp) {
                    tmp = this.labArray[j];
                    tmp_idx = j;
                }
            }
            swap(i, tmp_idx);
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertion() {
        int j;

        for (int i = 1; i < this.len; i++) {
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                this.swap(j, j - 1);
            }
            System.out.print("interim:  ");
            this.display();
        }
    }

    public void insertionShift()
    {
        int j;
        int tmp;

        for (int i = 1; i < this.len; i++) {
            // take ith element find where it should be inserted
            tmp = this.labArray[i];
            for (j = i; j > 0 && this.labArray[j] < this.labArray[j - 1]; j--) {
                // no need to do anything
                // when the loop ends j will be the insertion position
            }
            // Shift elements from j to i-1 over 1
            for (int k = i - 1; k >= j; k--)
            {
                this.labArray[k + 1] = this.labArray[k];
            }
            this.labArray[j] = tmp;
            System.out.print("interim:  ");
            this.display();
        }
    }

    public int[] merge(int[] a, int[] b)
    {
        int[] m = new int[a.length + b.length];
        int i=0;
        int j=0;

        for (int k = 0; k < m.length; k++)
        {
            if (i < a.length && j < b.length) {
            if (a[i]<=b[j]) {
                m[k] = a[i];
                i++;
            }
            else {
                m[k] = b[j];
                j++;
            }
            }
            else if (i < a.length) {  // b exhausted use up a
                m[k] = a[i];
                i++;
            }
            else { // b still has some left use up those
                m[k] = b[j];
                j++;
            }
        }
        return m;
    }

    public int[] mergesort(int begin, int end)
{
  int[] newArray = null;
  if (begin == end) { 
    // This is the end of the road create a new list of 1 element
    newArray = new int[1];
    newArray[0] = this.labArray[begin];
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  if (1 == end-begin) {
    // down to 2 elements 
    newArray = new int[2];
    if ( this.labArray[begin] < this.labArray[end]) {
      newArray[0] = this.labArray[begin];
      newArray[1] = this.labArray[end];
    } else {
      newArray[0] = this.labArray[end];
      newArray[1] = this.labArray[begin];
    }
  System.out.print("interim:  ");
  this.display(newArray);
    return newArray;
  }
  int split = (begin + end)/2;
  newArray = this.merge(this.mergesort(begin, split), this.mergesort(split+1,end));
  System.out.print("interim:  ");
  this.display(newArray);
  return newArray;
}


    public static void main(String[] args) {
        SortLab select = new SortLab();
        SortLab selectA = new SortLab();
        SortLab insert = new SortLab();
        SortLab insertA = new SortLab();
        SortLab msort = new SortLab();

        System.out.println("Selection Sort");
        System.out.print("unsorted: ");
        select.display();
        select.selection();
        System.out.print("sorted:   ");
        select.display();
        System.out.println("SelectionA Sort");
        System.out.print("unsorted: ");
        selectA.display();
        selectA.selectionA();
        System.out.print("sorted:   ");
        selectA.display();
        System.out.println();
        System.out.println();
        System.out.println("Insertion Sort");
        System.out.print("unsorted: ");
        insert.display();
        insert.insertion();
        System.out.print("sorted:   ");
        insert.display();
        System.out.println("Insertion Sort with Explicit Shift");
        System.out.print("unsorted: ");
        insertA.display();
        insertA.insertion();
        System.out.print("sorted:   ");
        insertA.display();
        System.out.println("\n");
        System.out.println("Merge Testing");
        int[] l1 = {0, 2, 3, 4, 6, 7, 9};
        int[] l2 = {1, 3, 5, 8, 10};
        int[] l3 = msort.merge(l1,l2);
        System.out.print("l1 = ");
        msort.display(l1);
        System.out.print("l2 = ");
        msort.display(l2);
        System.out.print("l3 = merge(l1,l2) = ");
        msort.display(l3);
        System.out.println("\n");

        System.out.println("merge sort");
        System.out.print("unsorted: ");
        msort.display();
        int[] sorted  = msort.mergesort(0,msort.len-1);
        System.out.print("sorted:   ");
        msort.display(sorted);
    }
}

Output 2

run:
Selection Sort
unsorted: 6  2  5  0  3  8  7  1  4  9  
interim:  0  2  5  6  3  8  7  1  4  9  
interim:  0  1  5  6  3  8  7  2  4  9  
interim:  0  1  2  6  3  8  7  5  4  9  
interim:  0  1  2  3  6  8  7  5  4  9  
interim:  0  1  2  3  4  8  7  5  6  9  
interim:  0  1  2  3  4  5  7  8  6  9  
interim:  0  1  2  3  4  5  6  8  7  9  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
SelectionA Sort
unsorted: 0  3  1  6  9  5  8  4  2  7  
interim:  0  3  1  6  9  5  8  4  2  7  
interim:  0  1  3  6  9  5  8  4  2  7  
interim:  0  1  2  6  9  5  8  4  3  7  
interim:  0  1  2  3  9  5  8  4  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  8  9  6  7  
interim:  0  1  2  3  4  5  6  9  8  7  
interim:  0  1  2  3  4  5  6  7  8  9  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Insertion Sort
unsorted: 1  3  2  7  6  0  9  8  5  4  
interim:  1  3  2  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  7  6  0  9  8  5  4  
interim:  1  2  3  6  7  0  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  9  8  5  4  
interim:  0  1  2  3  6  7  8  9  5  4  
interim:  0  1  2  3  5  6  7  8  9  4  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
Insertion Sort with Explicit Shift
unsorted: 7  1  2  5  4  3  6  9  8  0  
interim:  1  7  2  5  4  3  6  9  8  0  
interim:  1  2  7  5  4  3  6  9  8  0  
interim:  1  2  5  7  4  3  6  9  8  0  
interim:  1  2  4  5  7  3  6  9  8  0  
interim:  1  2  3  4  5  7  6  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  9  8  0  
interim:  1  2  3  4  5  6  7  8  9  0  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  


Merge Testing
l1 = 0  2  3  4  6  7  9  
l2 = 1  3  5  8  10  
l3 = merge(l1,l2) = 0  1  2  3  3  4  5  6  7  8  9  10  


merge sort
unsorted: 6  9  0  8  7  2  3  1  4  5  
interim:  6  9  
interim:  0  
interim:  0  6  9  
interim:  7  8  
interim:  0  6  7  8  9  
interim:  2  3  
interim:  1  
interim:  1  2  3  
interim:  4  5  
interim:  1  2  3  4  5  
interim:  0  1  2  3  4  5  6  7  8  9  
sorted:   0  1  2  3  4  5  6  7  8  9  
BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

If you haven't done so already you should at the very least download the AP Computer Science A Course Description. It's a PDF file and basically goes over everything you should have been taught in AP Computer Science (See References). My read of the latest 2010 document indicates that you only need to know about the 3 sorts I have covered. However in years past looking at the teaching site Bubble sort and Quick sort have been taught in the past. If you have time go over those your teacher's may have introduced them to you. If not then take the College Board at their word and make sure you know the 3 I have presented. For Future knowledge Donald Knuth in his Art of Computer Programming series goes over the following sorts (based on a quick scan of the text I may have missed one or two):

• Insertion sort
• Shell Sort
• Exchange Sort
• Bubble Sort
• Baucher Sort
• Quick Sort
• Heap Sort
• Merge Sort

If you go online to Google Scholar you will find many more. Sorting is certainly a basic problem for any Computer Scientist. They all have their drawbacks and the best one changes from time to time as people discover scenarios where the algorithms don't work well. In my day of learning this material I was told that Quicksort was best in actual practice even though theoretically Heap sort should have the better outcome. I don't have a reference for you but if you continue your pursuit of computers you will probably come across Journal articles that will espouse one algorithm over another.

References

1. Knuth, Donald Ervin. The Art of Computer Programming Sorting and Searching. 2nd ed. Vol. 3. Reading, Mass. Addison-Wesley, 1998.
2. https://apstudent.collegeboard.org/apcourse/ap-computer-science-a/course-details "Course Details." AP Computer Science A. N.p., n.d. Web. 29 Mar. 2013.

Author: Nasty Old Dog

More Recursion

Double Recursion

Introduction

Recursion is a wonderful thing once you've mastered it. There are often problems in Computer Science that have simple, concise solutions once recursion is applied to the problem. One of the biggest problem for beginners occurs when they try to follow the recursive calls of a routine that makes two or more calls to itself. The problem becomes evident in what I term a double recursion. Once you understand how to trace the calls in this type of routine you will be able to apply the analysis to any number of calls.

What exactly is a double recursion? It's a method that calls itself twice. This is different from a method that chooses one type of recursive call over another. In this case every call to the method will spawn 2 more calls to the method. This then recurses down spawning 2 more calls until the test case is met and the method calls start to return back up the chain. The problem for the beginning student is that this type of arrangement maps out a 'tree' of calls and the student must perform a manual 'depth' first search of the call tree.

Trees

Trees are a data structure object that crop up in computer science and while it is not necessary to program one for the AP Computer Science exam a brief description of terminology for trees is useful to the discussion here. Students when trying to figure out a double recursion forget about what the computer is doing and bounce back and forth between a 'depth' first search of the method calls and what is know as a 'breadth' first search.

A diagram will explain this much better than words.

Depth First Search

In a depth search first you must follow the branches all the way down then go back up and follow any other branches etc. The numbering of the boxes shows how we visit the nodes. This is the same for recursion when 2 or more recursive calls are made. You must follow the first recursive trail and then back up and follow the next call in a similar fashion to this tree.

Breadth First Search

The mistake is to try to account for both calls at the same time when you enter the first call sequence. The computer doesn't do it this way it blindly follows the trail of the first call then when it comes back it handles the second. So breadth first search is a mistake of reading the program as you would a story. You complete the paragraph then go off to see what the next sequence is. The following diagram is the WRONG way to follow a recursion tree:

I almost don't want to show you this for fear you will worry about it. But rememeber you must follow the first call sequence down until the test case is reached. Then you pop back up at each stage to handle the second call. Forget about breadth first and stick to the order of the first diagram. Recursion is naturally a depth first search.

Make the computer do it

While you must learn to draw out the call structure by hand. There is no reason not to experiment with having the computer do it for you. With the appropriate use of output statements and a little bookkeeping in a program example we can make the computer account for how the recursion is happening. First let's create a single recursive method that logs it's calls then we can add a double recursion to the example. In the end you will have a program that maps out it's call tree in a textual representation. From there you only need to be able to draw a sketch on the test and you should be ready for any recursive problem thrown at you.

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            System.out.print(vals[m] + "  ");
            singleRecursion(vals, m - 1);
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output

run:
0  1  2  3  4  5  
BUILD SUCCESSFUL (total time: 0 seconds)

So the code goes to the end of the array and prints each value. This reverses the order of the array. This is because the print happens before the recursive call back into singleRecursion. If the print statement is moved to after the method call the recursion goes all the way to m = -1 which ends the recursion then as the computer starts to come back up from it's decent into the recursion values will be printed in normal order indexed from 0 - 5 to print the values as they appear in the intialization of myArray.

Here is the class with the print statement moved after the recursive call:

class DoubleRecurse {

    public static void singleRecursion(int[] vals, int m) {
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public static void main(String[] args) {
        int[] myArray = {5, 4, 3, 2, 1, 0};

        singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 1

run:
5  4  3  2  1  0  
BUILD SUCCESSFUL (total time: 1 second)

Exposing Recursion

Let's add some print statements to expose the recursion more explicitly in the output. One way to display the recursion is to present the output from each call on a separate line. By using field variables we can also track the number of calls and the depth (or level) of the recursion. The depth field can be used to prepend spaces so that deeper levels of recursion are indented in the output.

The changes will include making this object oriented by taking away the static method and making it a plain method call to singleRecursion. This will mean that a DoubleRecurse object needs to be instantiated in the main method so the method can be used. But it means that the new fields will be available for any new recursive methods added to the class. The new code with the tracking fields and the new output statements follows:

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {
        calls++;
        depth++;

        // track calls depth and m
        indent(depth);
        System.out.println("calls = " + calls 
                + "  depth = " + depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursion(vals, m - 1);
            indent(depth);
            System.out.println(vals[m]);
        }
        else {
            indent(depth);
            System.out.println("test case met no more recursion start backing out");
        }

        depth --;
    }

    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 2

run:
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

BUILD SUCCESSFUL (total time: 0 seconds)

Double Recursion

Now that there are tools to display the recursive calls, the program can be modified to track a doubly recursive call. Rather than change the singleRecursion method a new method called doubleRecursion can be added.

In the new code there are 4 method calls. The original singleRecursion method that does no tracking. A new method called singleRecursionTrack that has the tracking fields and output statements. Then the single recursion modified to do double recursion and it's tracking counterpart named doubleRecursion and doubleRecursionTrack respectively

class DoubleRecurse {
    // Track number of calls
    int calls = 0;
    // Track level
    int depth = 0;

    void indent(int spaces)
    {
        for (int i = 0; i < spaces; i++) {
            System.out.print("  ");
        }
    }

    public void singleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            singleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
        }
    }

    public void singleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            singleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth--;
    }

    public void doubleRecursion(int[] vals, int m) {        
        if (m >= 0) {
            this.doubleRecursion(vals, m - 1);
            System.out.print(vals[m] + "  ");
            this.doubleRecursion(vals, m - 3);
        }
    }

    public void doubleRecursionTrack(int[] vals, int m) {
        this.calls++;
        this.depth++;

        // track calls depth and m
        indent(this.depth);
        System.out.println("calls = " + this.calls 
                + "  depth = " + this.depth 
                + "  m = " + m);

        if (m >= 0) {
            this.doubleRecursionTrack(vals, m - 1);
            indent(this.depth);
            System.out.println(vals[m]);
            this.doubleRecursionTrack(vals, m - 3);
        }
        else {
            indent(this.depth);
            System.out.println("test case met no more recursion start backing out");
        }

        this.depth --;
    }


    public static void main(String[] args) {
        DoubleRecurse recursion = new DoubleRecurse();
        int[] myArray = {5, 4, 3, 2, 1, 0};

        recursion.singleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.singleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
        recursion.calls = 0;  // start new recursion reset calls to track
        recursion.doubleRecursion(myArray, myArray.length-1);
        System.out.println();
        recursion.doubleRecursionTrack(myArray, myArray.length-1);
        System.out.println();
    }
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
        calls = 11  depth = 4  m = 0
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
      calls = 14  depth = 3  m = 1
        calls = 15  depth = 4  m = 0
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
    calls = 19  depth = 2  m = 2
      calls = 20  depth = 3  m = 1
        calls = 21  depth = 4  m = 0
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 0 seconds)

This gives a good trail of when calls take place and at what level but it is still not completely obvious when the first recursive call is taking place and when the second is. By adding a field to the doubleRecursion the call number can be saved separately from the total calls. Adding 2 printlns before the calls (indenting for the current depth of course) now highlights exactly where the processing is being done.

public void doubleRecursionTrack(int[] vals, int m) {
    int current_call = 0;

    this.calls++;
    current_call = this.calls;
    this.depth++;

    // track calls depth and m
    indent(this.depth);
    System.out.println("calls = " + this.calls 
            + "  depth = " + this.depth 
            + "  m = " + m);

    if (m >= 0) {
        indent(this.depth);
        System.out.println("call = " + current_call + " enter first recursion");
        this.doubleRecursionTrack(vals, m - 1);
        indent(this.depth);
        System.out.println(vals[m]);
        indent(this.depth);
        System.out.println("call = " + current_call + " enter second recursion");
        this.doubleRecursionTrack(vals, m - 3);
    }
    else {
        indent(this.depth);
        System.out.println("test case met no more recursion start backing out");
    }

    this.depth --;
}

Output 3

run:
5  4  3  2  1  0  
  calls = 1  depth = 1  m = 5
    calls = 2  depth = 2  m = 4
      calls = 3  depth = 3  m = 3
        calls = 4  depth = 4  m = 2
          calls = 5  depth = 5  m = 1
            calls = 6  depth = 6  m = 0
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
          4
        3
      2
    1
  0

5  4  3  2  5  1  5  4  0  5  4  3  
  calls = 1  depth = 1  m = 5
  call = 1 enter first recursion
    calls = 2  depth = 2  m = 4
    call = 2 enter first recursion
      calls = 3  depth = 3  m = 3
      call = 3 enter first recursion
        calls = 4  depth = 4  m = 2
        call = 4 enter first recursion
          calls = 5  depth = 5  m = 1
          call = 5 enter first recursion
            calls = 6  depth = 6  m = 0
            call = 6 enter first recursion
              calls = 7  depth = 7  m = -1
              test case met no more recursion start backing out
            5
            call = 6 enter second recursion
              calls = 8  depth = 7  m = -3
              test case met no more recursion start backing out
          4
          call = 5 enter second recursion
            calls = 9  depth = 6  m = -2
            test case met no more recursion start backing out
        3
        call = 4 enter second recursion
          calls = 10  depth = 5  m = -1
          test case met no more recursion start backing out
      2
      call = 3 enter second recursion
        calls = 11  depth = 4  m = 0
        call = 11 enter first recursion
          calls = 12  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 11 enter second recursion
          calls = 13  depth = 5  m = -3
          test case met no more recursion start backing out
    1
    call = 2 enter second recursion
      calls = 14  depth = 3  m = 1
      call = 14 enter first recursion
        calls = 15  depth = 4  m = 0
        call = 15 enter first recursion
          calls = 16  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 15 enter second recursion
          calls = 17  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 14 enter second recursion
        calls = 18  depth = 4  m = -2
        test case met no more recursion start backing out
  0
  call = 1 enter second recursion
    calls = 19  depth = 2  m = 2
    call = 19 enter first recursion
      calls = 20  depth = 3  m = 1
      call = 20 enter first recursion
        calls = 21  depth = 4  m = 0
        call = 21 enter first recursion
          calls = 22  depth = 5  m = -1
          test case met no more recursion start backing out
        5
        call = 21 enter second recursion
          calls = 23  depth = 5  m = -3
          test case met no more recursion start backing out
      4
      call = 20 enter second recursion
        calls = 24  depth = 4  m = -2
        test case met no more recursion start backing out
    3
    call = 19 enter second recursion
      calls = 25  depth = 3  m = -1
      test case met no more recursion start backing out

BUILD SUCCESSFUL (total time: 2 seconds)

Conclusion

This should help when trying to follow recursion. Certainly in an exam situation they don't allow an IDE to code with, but with some paper, pencil and a little fortitude even the average student should be able to build a recursion tree by hand. The AP question makers understand there is limited time so the example provided here is much more complex in terms of the number of calls a student will have to track.

A study recommendation
If you find yourself getting the recursion problems wrong in your practice tests, code them up with indentation and tracking information. Most likely you are making a simple mistake drawing out the call tree. The output from your code should enlighten you on the proper call pattern.

Date: 2013-03-26T16:55-0400

Author: Nasty Old Dog