Arrays, Recursion, and Complexity Lesson 11—Recursion, Complexity, and Searching and Sorting
Chapter 11
Solutions
Answers to Review Questions
Exercise 11.1
1. The presence of a well-defined stopping state keeps a recursive definition from being circular. The stopping state is a test of a condition and an action that does not result in a recursive step.
2. A stopping state and a recursive step.
3. Recursion in most programming languages requires a call stack to track the data for each call of a recursive method. Each time a recursive method is called, the computer allocates memory for the method's information on the stack and copies the information into this memory. Thus, there is a cost of memory and time as well.
4. The primary benefit of using recursion is that the programmer can write solutions to some problems more easily and with less effort than solutions that use a loop. Some problems lend themselves quite naturally to recursive solutions and not at all naturally to iterative ones.
5.
raise(2, 5)
raise(2, 4)
raise(2, 3)
raise(2, 2)
raise(2, 1)
raise(2, 0)
returns 1
returns 2
returns 4
returns 8
returns 16
returns 32
6. The method whatAMethod is always called recursively with the same value, n. Thus, the stopping state, when n == 0, is never reached. The computer tolerates these recursive calls until there is no more stack space and then throws an exception.
Exercise 11.2
1.a. The run time of factorial is O(n).
1.b. The run time of raise is O(n).
2.a. The memory usage of factorial is O(n).
2.b. The memory usage of fibonacci is O(n).
3. The run time of the sort method is O(n2).
Exercise 11.3
1.
int raise(int base, int expo){
if (expo == 0)
return 1;
else if (expo % 2 == 0){
int result = raise(base, expo / 2);
return result * result;
}else
return base * expo(base, expo – 1);
}
2.
raise(2, 16)
raise(2, 8)
raise(2, 4)
raise(2, 2)
raise(2, 1)
raise(2, 0)
returns 1
returns 2
returns 4
returns 16
returns 256
returns 65536
3. For large n, raise tends to divide n by 2 on each recursive call, so the method is O(logn).
Exercise 11.4
1. The strategy of quick sort is to select a pivot item and shift all of the smaller items to its left and all of the larger items to its right. This part of the process is linear. If the pivot item tends to be in the middle of the list, the number of times the shifting must occur is logarithmic, so that's why quicksort can be better than O(n2).
2. Quicksort is not O(nlogn) in all cases because the pivot item might be near the beginning or the end of the list, thus causing an uneven split of the list. If this situation occurs often enough, the run time of quicksort can degenerate to O(n2) in the worst case.
3. Three methods to select a pivot value are to pick the item at the midpoint, to pick an item at a random position, and to pick the median of the first, last, and middle items.
4. If the subarray is relatively small, running an insertion sort might be a bright idea for two reasons. First, this algorithm probably performs just as well as a quicksort on small data sets. Second, the behavior of insertion sort is close to linear when the array is partially sorted, as many subarrays would be within the context of a quicksort.
Review Questions
Vocabulary Review
Activation record: An area of computer memory that keeps track of a method call's parameters, local values, return value, and the caller's return address.
Big-O notation: A formal notation used to express the amount of work done by an algorithm or the amount of memory used by an algorithm.
Binary search algorithm: The process of examining a middle value of a sorted array to see which half contains the value in question and halving until the value is located.
Call stack: The trace of method calls that appears when Java throws an exception during program execution.
Complexity analysis: For algorithms, the process of deriving a formula that expresses the rate of growth of work or memory as a function of the size of the data or problem that it solves.
Infinite recursion: A situation that occurs when the run of a recursive algorithm reaches no stopping state.
Iterative process: A process that repeats with no growth of computer memory.
Quicksort: A sorting technique that moves elements around a pivot recursively sorts the elements to the left and the right of the pivot.
Recursive method: A method that calls itself.
Recursive step: A step in the recursive process that solves a similar problem of smaller size and eventually leads to a termination of the process.
Stack: A dynamic data structure in which access can be made from only one end. Referred to as a LIFO (last-in, first-out) structure.
Stack overflow error: A situation that occurs when the computer runs out of memory to allocate for its call stack. This situation usually arises during an infinite recursion.
Stopping state: The well-defined termination of a recursive process.
Tail-recursive: The property that a recursive algorithm has of performing no work after each recursive step.
Fill in the Blank
1. The stopping state of a recursive algorithm is the part in which a problem is solved directly, without further recursion.
2. The recursive step of a recursive algorithm is the part in which the problem is reduced in size.
3. The memory of a computer is formatted into a large call stack to support recursive method calls.
4. The memory for each recursive method call is organized in a group of cells called an activation record.
5. The type of error in a recursive algorithm that causes it to run forever is called an infinite recursion.
6. When a recursive method does not stop, a stack overflow error occurs at run time.
7. The linear, quadratic, and logarithmic orders of complexity are expressed as O(n), O(n2), and O(logn) using big-O notation.
8. The bubble sort algorithm has a run-time complexity of O(n2) in the best case and O(n) in the worst case.
9. The quicksort algorithm has a run-time complexity of O(nlogn) in the best case and O(n2) in the worst case.
Solutions to Projects
Project 11-1
// Solution to Project 11.1
// Tester program for the gcd method
import TerminalIO.KeyboardReader;
public class TestGCD{
// Precondition:
// x, y > 0
// Postcondition:
// returns the gcd of x and y
public static int gcd (int x, int y){
if (x == 0)
return y;
else if (y == 0)
return x;
else
return gcd (y, x % y);
}
public static void main (String[] args){
System.out.println ("gcd(3,6) = " + gcd(3,6));
System.out.println ("gcd(6,3) = " + gcd(6,3));
System.out.println ("gcd(24,30) = " + gcd(24,30));
KeyboardReader reader = new KeyboardReader();
while (true){
int a = reader.readInt("Enter the first number: ");
int b = reader.readInt("Enter the first number: ");
System.out.println("The GCD of " + a + " and " + b +
" is " + gcd(a, b));
}
}
}
Project 11-2
// Solution to Project 11.2
// Tester program for reversing a string
import TerminalIO.KeyboardReader;
public class TestReverse{
public static String reverse (String s){
return recursiveReverse(s, 0);
}
public static String recursiveReverse (String s, int pos){
if (pos < s.length()){
String beginningOfString = recursiveReverse(s, pos + 1);
return beginningOfString + s.charAt(pos);
}else
return "";
}
public static void main (String[] args){
KeyboardReader reader = new KeyboardReader();
while (true){
String s = reader.readLine("Enter a string: ");
System.out.println("The reverse of " + s + " is " +
reverse(s));
}
}
}
Project 11-3
// Solution to Project 11.3
// Tester program for adding commas to a number
import TerminalIO.KeyboardReader;
public class TestCommas{
public static String addCommas (int number){
if (number >= 1000){
String beforeComma = addCommas(number / 1000);
if (number % 1000 == 0)
return beforeComma + ",000";
else
return beforeComma + "," + + number % 1000;
}else
return number + "";
}
public static void main (String[] args){
KeyboardReader reader = new KeyboardReader();
while (true){
int number = reader.readInt("Enter a number: ");
System.out.println("The format of " + number + " is " +
addCommas(number));
}
}
}
Project 11-4
// Solution to Project 11.4
// Tester program for N choose K
/*
pseudocode for nChooseK:
nChooseK(n, k)
if (n == 0 || n == 1)
return 1
else
return nChooseK(n - 1, k) + nChooseK(n - 1, k - 1)
*/
import TerminalIO.KeyboardReader;
public class TestNChooseK{
public static long nChooseK (int n, int k){
if (k == 0 || n == k)
return 1;
else
return nChooseK(n - 1, k) + nChooseK(n - 1, k - 1);
}
public static void main (String[] args){
KeyboardReader reader = new KeyboardReader();
while (true){
int n = reader.readInt("Enter N: ");
int k = reader.readInt("Enter K: ");
if (k <= n & k >= 0)
System.out.println("N choose K of " + n + " and " + k + " is " +
nChooseK(n, k));
else
System.out.println("K must be <= N and >= 0; try again");
}
}
}
Project 11-5
// Solution to Project 11.5
import javax.swing.*;
import java.util.*;
import BreezySwing.*;
/*
Modify the Case Study of this lesson so that it counts comparison and exchange
operations in both sort algorithms and displays these statistics as well.
Run the program with two array sizes and make a prediction on the number of
comparisons, exchanges, and run times for a third size.
*/
public class ComparingSortAlgorithms extends GBFrame{
private JLabel arrayLengthLabel, resultsLabel;
private IntegerField arrayLengthField;
private JButton sortButton;
private JTextArea resultsTextArea;
private int comparisons1, comparisons2;
private int exchanges1, exchanges2;
public ComparingSortAlgorithms(){
setTitle ("Sort Tester");
// Instantiate window objects
arrayLengthLabel = addLabel ("Array Length",1,1,1,1);
arrayLengthField = addIntegerField (0,1,2,1,1);
sortButton = addButton("Sort",2,1,3,1);
resultsLabel = addLabel ("Milliseconds as a function of array length",3,1,3,1);
resultsTextArea = addTextArea ("Area",4,1,3,4);
//Set the text to column headers
String str = Format.justify ('L', " Bubble Sort", 30)
+ Format.justify ('L', " Quicksort", 30) + "\n"
+ Format.justify ('R', "Length", 7)
+ Format.justify ('R', "Comparisons", 12)
+ Format.justify ('R', "Exchanges", 10)
+ Format.justify ('R', "Time", 8)
+ Format.justify ('R', "Length", 8)
+ Format.justify ('R', "Comparisons", 12)
+ Format.justify ('R', "Exchanges", 10)
+ Format.justify ('R', "Time", 8) + "\n"
+ Format.justify ('L', "------",
38)
+ Format.justify ('R', "------",
38) + "\n";
resultsTextArea.setText (str);
}
public void buttonClicked (JButton buttonObj){
//Get the array length and instantiate two arrays,
//one of this length and the other a 100 times longer.
int arrayLength = arrayLengthField.getNumber();
int[] a1 = new int[arrayLength];
int[] a2 = new int[arrayLength*100];
//Initialize the first array
for (int i = 0; i < a1.length; i++)
a1[i] = (int)(Math.random() * (100000));
// Random numbers between 0 and 100,000
//Initialize the second array
for (int i = 0; i < a2.length; i++){
a2[i] = (int)(Math.random() * (100000));
}
//Declare timers
Date d1, d2;
long elapsedTime1, elapsedTime2;
//Time bubble sort
comparisons1 = 0;
exchanges1 = 0;
d1 = new Date();
bubbleSort (a1);
d2 = new Date();
elapsedTime1 = d2.getTime() - d1.getTime();
//Time quick sort
comparisons2 = 0;
exchanges2 = 0;
d1 = new Date();
quickSort (a2, 0, a2.length - 1);
d2 = new Date();
elapsedTime2 = (d2.getTime() - d1.getTime());
//Display results in text area
resultsTextArea.append
( Format.justify ('R', "" + arrayLength, 7)
+ Format.justify ('R', "" + comparisons1, 8)
+ Format.justify ('R', "" + exchanges1, 12)
+ Format.justify ('R', "" + elapsedTime1, 8)
+ Format.justify ('R', "" + arrayLength*100, 8)
+ Format.justify ('R', "" + comparisons2, 12)
+ Format.justify ('R', "" + exchanges2, 8)
+ Format.justify ('R', "" + elapsedTime2, 8) + "\n");
}
private void bubbleSort (int[] a){
//Bubble sort
for (int i = 0; i < a.length - 1; i++){
for (int j = i + 1; j < a.length; j++){
comparisons1++;
if (a[i] > a[j]){
exchanges1++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
}
}
private void quickSort (int[] a, int left, int right){
//Quick sort
if (left >= right) return;
int i = left;
int j = right;
int pivotValue = a[(left + right)/2];
while (i < j){
while (a[i] < pivotValue){
i++;
comparisons2++;
}
while (pivotValue < a[j]){
j--;
comparisons2++;
}
comparisons2++;
if (i <= j){
exchanges2++;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
i++;
j--;
}
}
quickSort (a, left, j);
quickSort (a, i, right);
return;
}
public static void main (String[] args){
ComparingSortAlgorithms theGUI = new ComparingSortAlgorithms();
theGUI.setSize (600, 300);
theGUI.setVisible(true);
}
}
Project 11-6
// Solution to Project 11.6
// Display the number of recursive calls required.
// Omit the trace of the moves made.
public class TestHanoi{
private static long count;
public static void main (String[] args){
for (int i = 1; i <= 5; i++){
count = 0;
int n = (int)Math.pow(2,i);
move(n, 1, 3, 2);
System.out.println ("" + n + ":" + count);
}
}
public static void move (int n, int i, int j, int k){
//Print the moves for n rings going from peg i to peg j
// Preconditions -- none
// Postconditions -- the moves have been printed
count++;
if (n > 0){ //Stopping state is n == 0
//Move the n-1 smaller rings from peg i to peg k
move (n - 1, i, k, j);
//Move the largest ring from peg i to peg j
//System.out.println("Move ring " + n + " from peg " + i + " to " + j);
//Move the n-1 smaller rings from peg k to peg j
move (n - 1, k, j, i);
//n rings have now been moved from peg i to peg j.
}
}
}
Project 11-7
// Solution to Project 11.7
/* TestManyQueens.java
Determine the solution to the many queens problem for a chessboard
of any size.
If there is a solution display it else indicate that there is none.