Session 23

Source Code

import java.util.*;

public class Week23 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        System.out.println("Welcome to Week 23");
        System.out.println("E1 - Example 1");
        System.out.println("Q - Quit");
        System.out.print("Choice: ");
        String choice = in.nextLine();
        switch (choice) {
            case "E1":
                System.out.println("Example 1");
                // example1();
                break;
            case "E2":
                System.out.println("Example 2");
                // example2(3);
                break;
            case "E3":
                System.out.println("Example 3");
                // System.out.println(factorial(5));
                break;
            case "E4":
                System.out.println("Example 4");
                // System.out.println(fibonacci(5));
                break;
            case "E5":
                System.out.println("Example 5");
                int target = 1;
                int[] arr1 = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
                int foundIndex = recursiveBinarySearch(arr1, target, 0, arr1.length - 1);
                System.out.println(target + " was found at index " + foundIndex);
                break;
            case "E6":
                System.out.println("Example 6");
                int[] arrMerge = {86, 3, 43, 5};
                System.out.println(Arrays.toString(arrMerge));
                mergeSort(arrMerge);
                System.out.println(Arrays.toString(arrMerge));
                break;
            case "E7":
                System.out.println("Example 7");
                // 3 discs
                // Hanoi towersofHanoi = new Hanoi(3);
                break;
            case "E8":
                System.out.println("Example 8");
                // 64 discs
                // Hanoi towersofHanoi = new Hanoi(64);
                break;
            // quit and default cases
            case "Q":
                break;
            default:
                System.out.println("Invalid Choice");
                break;
        }
    }

    // example1() method


    // example2() method


    // factorial method


    // fibonacci method
    

    // recursive binary search method
    public static int recursiveBinarySearch(int[] array, int target, int start, int end) {
        int middle = (start + end) / 2;
        // base case: check middle element
        if (target == array[middle]) {
            return middle;
        }
        // base case: check if we've run out of elements
        if (end < start) {
            return -1; // not found
        }
        // recursive call: search start to middle
        if (target < array[middle]) {
            return recursiveBinarySearch(array, target, start, middle - 1);
        }
        // recursive call: search middle to end
        if (target > array[middle]) {
            return recursiveBinarySearch(array, target, middle + 1, end);
        }
        return -1;
    }

    // merge sort
    public static void mergeSort(int[] a) {
        // Base case: if the array is of length 0 or 1, it's already sorted
        if (a.length <= 1) {
            return;
        }

        // Creating two arrays to hold the two halves of the input array
        int[] first = new int[a.length / 2];
        int[] second = new int[a.length - first.length];

        // Copying the first half of the array 'a' into 'first'
        for (int i = 0; i < first.length; i++) {
            first[i] = a[i];
        }
        // Copying the second half of the array 'a' into 'second'
        for (int i = 0; i < second.length; i++) {
            second[i] = a[first.length + i];
        }

        // Recursively sort the first half
        mergeSort(first);
        // Recursively sort the second half
        mergeSort(second);

        // Merge the sorted halves back into the original array
        merge(first, second, a);
    }

    // Private helper method to merge two sorted arrays into a single sorted array
    private static void merge(int[] first, int[] second, int[] a) {
        int iFirst = 0; // Index into the first array
        int iSecond = 0; // Index into the second array
        int j = 0; // Index into the merged array

        // While both arrays have elements yet to be merged
        while (iFirst < first.length && iSecond < second.length) {
            // Determine which element from the two halves is smaller
            // and add it to the merged array
            if (first[iFirst] < second[iSecond]) {
                a[j] = first[iFirst];
                iFirst++;
            } else {
                a[j] = second[iSecond];
                iSecond++;
            }
            j++;
        }

        // If there are remaining elements in 'first', add them to 'a'
        while (iFirst < first.length) {
            a[j] = first[iFirst];
            iFirst++;
            j++;
        }

        // If there are remaining elements in 'second', add them to 'a'
        while (iSecond < second.length) {
            a[j] = second[iSecond];
            iSecond++;
            j++;
        }
    }
}

W23Problem1.java

public class W23Problem1 {
    public static void mystery1(int n) {
        if (n <= 0) {
            System.out.println("End");
        } else {
            System.out.println(n);
            mystery1(n - 2);
        }
    }
    
    public static void main(String[] args) {
        mystery1(5);
    }
}

W23Problem2.java

public class W23Problem2 {
    public static void mystery2(String str) {
        if (str.length() == 0) {
            System.out.println("End");
        } else {
            mystery2(str.substring(1));
            System.out.println(str.charAt(0));
        }
    }

    public static void main(String[] args) {
        mystery2("CAT");
    }
}

RecursiveBinarySearchActivity.java

public class RecursiveBinarySearchActivity {

    // The recursive binary search method
    public static int recursiveBinarySearch(int[] array, int target, int start, int end) {
        if (end < start) {
            return -1; // Base case: not found
        }
        int middle = (start + end) / 2;
        if (target == array[middle]) {
            return middle; // Base case: found
        }
        if (target < array[middle]) {
            return recursiveBinarySearch(array, target, start, middle - 1);
        } else { // target > array[middle]
            return recursiveBinarySearch(array, target, middle + 1, end);
        }
    }

    // Problem 1
    public static void problem1() {
        int result1 = -1;
        System.out.println("Problem 1 Result: " + result1);
    }

    // Problem 2
    public static void problem2() {
        int result2 = -1;
        System.out.println("Problem 2 Result: " + result2);
    }

    // Problem 3
    public static void problem3() {
        int callCount = -1;
        System.out.println("Problem 3: Total recursive calls = " + callCount);
    }
    
    // Problem 4
    public static void problem4() {
        int callCount = -1;
        System.out.println("Problem 4: Total recursive calls = " + callCount);
    }

    // Helper method to count recursive calls for Problem 3
    public static int countRecursiveCalls(int[] array, int target) {
        return countCallsHelper(array, target, 0, array.length - 1, 0);
    }

    public static int countCallsHelper(int[] array, int target, int start, int end, int count) {
        count++;
        if (end < start) {
            return count;
        }
        int middle = (start + end) / 2;
        if (target == array[middle]) {
            return count;
        }
        if (target < array[middle]) {
            return countCallsHelper(array, target, start, middle - 1, count);
        } else {
            return countCallsHelper(array, target, middle + 1, end, count);
        }
    }

    // main method
    public static void main(String[] args) {
        // call each problem
        
    }
}

Hanoi.java

public class Hanoi {
   private int numDiscs;  // Number of discs

   public Hanoi(int n) {
     // Assign the number of discs.
     numDiscs = n;

     // Move the number of discs from peg 1 to peg 3
     // using peg 2 as a temporary storage location.
     moveDiscs(numDiscs, 1, 3, 2);
   }

   /**
   * The moveDiscs method accepts the number of
   * discs to move, the peg to move from, the peg
   * to move to, and the temporary peg as arguments.
   * It uses recursion to display the necessary
   * disc moves.
   */

   private void moveDiscs(int num, int fromPeg, int toPeg, int tempPeg) {
    if (num > 0) {
      moveDiscs(num - 1, fromPeg, tempPeg, toPeg);
      System.out.println("Move a disc from peg " + fromPeg + " to peg " + toPeg);
      moveDiscs(num - 1, tempPeg, toPeg, fromPeg);
    }
  }
}