Subscribe to Macosxnerd101's Blog        RSS Feed
-----

Applications of Algorithms on the AP Computer Science Exam

Icon 2 Comments
With the AP Comp Sci exam coming up in 2 days, I'd like to cover two algorithms that show up enough in the multiple choice to warrant some attention. These two algorithms are Binary Search and Bubblesort. Usually, these algorithms don't show up verbatim. Instead, you will see modifications to or applications modeled after these algorithms. For example, here is a Binary Search multiple choice question from the College Board course description for this year (2009-2010). Some elements of Binary Search that we can easily pick out are mid = (low+high)/2;, the modification of the range based on comparison of the elem at mid in comparison to the target, and our base case of low > high. In the truest sense of the AP, this question is a recursion question using the method name mystery(). The answer to this question is A, by the way.

Quote

10. Consider the following instance variable and method.
private int[] arr;

/** Precondition: arr contains no duplicates;
* the elements in arr are in sorted order.
* @param low 0 ≤ low ≤ arr.length
* @param high low - 1 ≤ high < arr.length
* @param num
*/
public int mystery(int low, int high, int num)
{
     int mid = (low + high) / 2;
     if (low > high)
     {
        return low;
     }
     else if (arr[mid] < num)
     {
          return mystery(mid + 1, high, num);
     }
     else if (arr[mid] > num)
     {
          return mystery(low, mid - 1, num);
     }
     else // arr[mid] == num
     {
          return mid;
     }
}


What is returned by the call
mystery(0, arr.length - 1, num) ?
(A) The number of elements in arr that are less than num
(B) The number of elements in arr that are less than or equal to num
© The number of elements in arr that are equal to num
(D) The number of elements in arr that are greater than num
(E) The index of the middle element in arr


I'd also like to look at how the AP sets up Bubblesort questions. To start, let's examine a traditional Bubblesort algorithm.
public static void bubbleSort(int[] x){
           boolean swapped = false;
           do{
              swapped = false;
              for(int i = 0; i < x.length-1; i++){
                   if(x[i] > x[i+1]){
                          swap(x, i, i+1);
                          swapped = true;
                   }
               }
           }while(swapped);
           
}



From the multiple choice questions I've seen, they take one of two approaches- they either take parts of Bubblesort or they modify the Bubblesort procedure so that it starts at different points for one of the two index variables (if a nested for loops approach is taken). For the first approach, the AP loves to use the inner for loop. It is usually set up as seen in the above implementation with the if statement inside; however, the code inside the if statement is varied for some other purpose. One example of the second approach, the modification of the sorting routine, shown below is an example (or something close to, as I'm recalling from memory) that was actually on the 2009 AP Computer Science Exam, that I saw as practice at my last AP Computer Science session. If you run it, then yes- it will sort an array of ints. However, is it a traditional Bubblesort we are used to seeing? No- or at least not for me. In both cases, the question provides an input and asks for the result.
public static void mystery(int[] x){
	for(int i = x.length-1; i > 0; i--){
		for(int j = 0; j < i; j++){
			if(x[j] > x[i]) swap(x, i, j);
		}
	}



A last warning- be very careful when you see an algorithm you recognize on the AP exam. The AP loves to throw those application questions at you, so make sure to work through the problem to get the correct answer. There is no reason that if you know what you are doing and you recognize the algorithm that you should lose points for assuming. It could make the difference between the score you get and the score you want.

2 Comments On This Entry

Page 1 of 1

Dogstopper Icon

02 May 2010 - 07:31 AM
To be honest...I had to run the Binary Search one to see. OMG I felt stupid. I answered B last year. *facepalm*
0

macosxnerd101 Icon

02 May 2010 - 08:35 AM
If it makes you feel any better, the College Board Multiple Choice from the Course Description was my Midterm in AP CS. I got lazy and answered incorrectly as well. Oh well. At least my teacher grades on the AP Scale, so anything north of a 78.5% (+1 correct, -.25 wrong, 0 skip) is in 5 range, so I got an A anyways.
0
Page 1 of 1

August 2014

S M T W T F S
     12
3456789
10111213141516
17181920212223
24252627 28 2930
31      

Recent Entries

Search My Blog

0 user(s) viewing

0 Guests
0 member(s)
0 anonymous member(s)