Unit 7: Recursion and Sorting Algorithms

Recursion

  • Recursion: A programming technique where a method calls itself to solve a problem.
  • Base Case: A condition that terminates the recursion.
    int factorial(int n) {
        if (n == 0) {
            return 1; // Base case
        } else {
            return n * factorial(n - 1); // Recursive call
        }
    
  • Recursive Call: A call to the same method within itself to make progress toward the base case.
    int sum(int[] arr, int index) {
        if (index == arr.length) {
            return 0; // Base case
        } else {
            return arr[index] + sum(arr, index + 1); // Recursive call
        }
    

Sorting Algorithms

  • Selection Sort: A simple sorting algorithm that repeatedly selects the minimum element from the unsorted portion and moves it to the beginning.
    void selectionSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    
  • Quick Sort: A fast, divide-and-conquer sorting algorithm that partitions the array into smaller segments.
    void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(arr, low, high);
            quickSort(arr, low, pivotIndex - 1);
            quickSort(arr, pivotIndex + 1, high);
        }
    }
      
    int partition(int[] arr, int low, int high) {
        // Choose a pivot and rearrange the elements around it
        // Return the final position of the pivot
    }
    

Unit 8: Object-Oriented Programming and Design

Abstraction

  • Abstraction: Focusing on essential features while hiding unnecessary details.
  • Abstract Classes: Classes marked as abstract that cannot be instantiated, used for creating a common base for other classes.
    abstract class Shape {
        abstract double area();
    }
    
  • Abstract Methods: Methods declared in abstract classes that have no implementation and must be overridden in subclasses.
    class Circle extends Shape {
        double radius;
          
        @Override
        double area() {
            return Math.PI * radius * radius;
        }
    

Static Members

  • Static Variables: Variables shared among all instances of a class. Accessed with the class name.
    class MathUtils {
        static final double PI = 3.14159265359;
    
  • Static Methods: Methods that belong to the class, not the instance. Accessed with the class name.
    static int add(int a, int b) {
        return a + b;
    }