Author Archives: graceliana@gmail.com

Chapter 8: Recursive Search String Finder

Assignment:

Write a program, StringFinder_YI.java that implements a recursive search of a sorted list of strings. Your program should include a recursive method that determines whether or not a given String is present within a sorted array (or, if you choose, an ArrayList) by searching successively smaller segments of the list.

magnifyingglass

Include a test driver that prompts the user for strings to be searched. The user should enter one string per line, with an empty line indicating the end of the series. After the sorted list of strings has been entered, the program should prompt the user for a search string. The program should then print a message stating whether or not the search string was found in the list, the total number of strings in the list, and the number of comparisons made while looking for the search string.

Chapter 8: Recursive Sorts

February 20th, 2014

Recursive Sorts – Clwk 2/20 – Quick Sort Exercises Part 2
With a partner find 7 different integers to demonstrate
1. The worst case for the quick sort. (most number of swaps)
2. The best case for the quick sort. (least number of swaps)

Post both sets and the number of swaps here.

Recursive Sorts – Clwk 2/20 – Quick Sort Exercises Part 3
1. What is the difference between the quick sort original code and the one from the text book?

Homework:
Recursive Sorts – Hwk 2/20 – Quick Sort random pivot
Write a different quick sort program:
Selection of pivot: choose the first three numbers and randomly assign one of them to be the pivot.

Implementation for the assignments:

/********************************************************************
   ********************************************************************/
   public void quickSort (int[] data, int min, int max)
   {
      int indexofpartition;

      if (max - min  > 0)
      {
         /** Create partitions */
         indexofpartition = findPartition(data, min, max);

         quickSort(data, min, indexofpartition - 1);

         quickSort(data, indexofpartition + 1, max);
      }
   }

   /********************************************************************
   ********************************************************************/
   private int findPartition (int[] data, int min, int max)
   {
      int left, right;
      int temp, partitionelement;

      partitionelement = data[min]; 
      left = min;
      right = max;

         while (left partitionelement) 
            right--;

         if (left

Chapter 8: Merge Sort

Merge Sort
The merge sort algorithm, another recursive sort algorithm, sorts a list by recursively dividing the list in half until each sublist has one element and then recombining these sublists in order.

General Strategy:
• Begin by dividing the list in two roughly equal parts and then recursively calling itself with each of those lists.
• Continue the recursive decomposition of the list until the base case of the recursion is reached, where the list is divided into lists of length one, which are by definition sorted.
• Then, as control passes back up the recursive calling structure, the algorithm merges into one sorted list the two sorted sublists resulting from the two recursive calls.

Example:
Let’s look at the recursive decomposition portion of the algorithm.
The merge portion of the algorithm would then recombine the list.

Merge Sort Code

wiki media

Assignment
1. The merge sort: Trace the indices for the given data:
int[] grades = {3,2,5,2};
Is it a stable sort? Explain
Use the code to supports your answer.

Good resources:

These are two good video with details and mathematical analysis:

Chapter 8: Maze Solver Illustration

Down the rabbit hole

Finding the way out of the rabbit hole

Chapter 8: Recursive Binary Search

Program: Implement Binary search in java using recursive algorithm.

A binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. In each step, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

Every recursion eliminates half of the remaining possibilities. This makes binary searches very efficient – even for large collections.

Binary search requires a sorted collection. Also, binary searching can only be applied to a collection that allows random access (indexing).

Worst case performance: O(log n)

Best case performance: O(1)

Recursion is used in this algorithm because with each pass a new array is created by cutting the old one in half. The binary search procedure is then called recursively, this time on the new array. Typically the array’s size is adjusted by manipulating a beginning and ending index. The algorithm exhibits a logarithmic order of growth because it essentially divides the problem domain in half with each pass.

Chapter 8: Intro to Recursion – More Basic Exercises

Classwork and homework assignments

1. Write a program, sumRec_YI.java with a recursive method to calculate the sum of the first N numbers.
2. Write a program, binarySearchRec_YI.java, with a recursive method to find an integer in an integer array of N elements.
3. Write a program, palindromeWordTestRec_YI.java, with a recursive method to determine if a word is a palindrome. It returns a boolean.
4. Write a program, palindromeSentenceTestRec_YI.java, with a recursive method to determine if a sentence is a palindrome. It returns a boolean.

Chapter 8: Recursion – ModSum & GCD

Today

More on Recursion

Ex 4: Modify the method that calculates the sum of the integers between 1 and N shown in this chapter. Have the new version match the following recursive definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2 + 1) to N.
Hint: modNSum(1, N/2) + modNSum(N/2 +1,N)
Write a driver to test your program.

Trace your solution using an N of 5.

// This method returns the sum of 1 to num
public int sum (int num) 
{
   int result; 
   if (num == 1)
       result = 1;
   else
       result = num + sum (num-1); 
   return result;
}

Screen Shot 2015-01-29 at 1.49.53 PM

Ex 5:
Design and implement a program that implements Euclid’s algorithm for finding the greatest common divisor of two positive integers. The greatest common divisor is the largest integer that divides both values without producing a remainder. An iterative version of this method was part of the RationalNumber class presented in Chapter 7.
In a class called DivisorCalc, define a static method called gcd that accepts two integers, num1 and num2. Create a driver to test your implementation. The recursive algorithm is defined as follows:

gcd (num1, num2) is num2 if num2 <= num1 and num2 divides num1

gcd (num1, num2) is gcd (num2, num1) if num1 < num2

gcd (num1, num2) is gcd (num2, num1%num2) otherwise

Chapter 8: quicksort demo

February 4th, 2015

Recursive sorts are not easy to follow and you might want to watch the video again. Also, we will have a few more exercises for you to practice.
James found a good source to share with all of you:

Classwork:
4. Under what conditions you have the worse case?
5. What data would yield to a best case and average case?
6. What is the big O notation for this sort for each case?
Homework:
7. Can you think of a non-recursive QuickSort?
8. Find a different algorithm for QuickSort in the internet.
9. Write code for QuickSorting objects. Include compareTo() and toString() methods of the object’s class.

NOTE for Phil: You were right. My bad.

Chapter 8: mod sum

January 30th, 2015

Share your recursive solution to yesterday’s assigment

Modify the method that calculates the sum of the integers between 1 and N shown in this chapter. Have the new version match the following recursive definition: The sum of 1 to N is the sum of 1 to (N/2) plus the sum of (N/2 + 1) to N. Trace your solution using an N of 7.

// This method returns the sum of 1 to num
public int sum (int num) 
{
   int result; 
   if (num == 1)
       result = 1;
   else
       result = num + sum (num-1); 
   return result;
}

Splash

At Princeton University. Due date to apply is March 30th!

Mrs. Elia's AP Computer Science

Class Website at PHS