Sorting & Algorithm Design

Merge Sort (15 points)

Implement merge sort with the classic divide & conquer approach:

public class SortingAlgorithms {
    
    /**
     * Merge Sort - O(n log n) time, O(n) space, stable
     * Divides array in half, recursively sorts, then merges
     */
    public static void mergeSort(int[] arr) {
        // Implement recursive merge sort
    }
    
    private static void mergeSortHelper(int[] arr, int[] temp, int left, int right) {
        // Divide array and recursively sort
    }
    
    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        // Merge two sorted halves
    }
    
    // Also implement for generic types
    public static > void mergeSort(T[] arr) {
        // Generic merge sort
    }
}

Requirements:

• Must be stable (equal elements maintain relative order)
• Implement both iterative merge and recursive versions
• Include generic version for any Comparable type

Quick Sort (15 points)

Implement quick sort with multiple pivot strategies:

/**
 * Quick Sort - O(n log n) average, O(n²) worst, O(log n) space
 * In-place partitioning around a pivot
 */
public static void quickSort(int[] arr) {
    quickSort(arr, 0, arr.length - 1);
}

private static 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);
    }
}

// Implement multiple partition strategies
private static int partitionLomuto(int[] arr, int low, int high);   // Last element pivot
private static int partitionHoare(int[] arr, int low, int high);    // First element pivot
private static int partitionMedianOfThree(int[] arr, int low, int high); // Median pivot

// 3-way partition for arrays with many duplicates (Dutch National Flag)
private static int[] partition3Way(int[] arr, int low, int high);

Requirements:

• Implement Lomuto, Hoare, and Median-of-Three partitioning
• Implement 3-way partitioning for duplicate elements
• Use tail recursion optimization to reduce stack space

Heap Sort (15 points)

Implement heap sort using a max-heap:

/**
 * Heap Sort - O(n log n) time, O(1) space, not stable
 * Builds max-heap, repeatedly extracts maximum
 */
public static void heapSort(int[] arr) {
    int n = arr.length;
    
    // Build max-heap (heapify)
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    
    // Extract elements from heap one by one
    for (int i = n - 1; i > 0; i--) {
        swap(arr, 0, i);     // Move current root to end
        heapify(arr, i, 0);  // Heapify reduced heap
    }
}

private static void heapify(int[] arr, int n, int i) {
    // Maintain max-heap property
    // Compare with left (2*i+1) and right (2*i+2) children
}

Requirements:

• Build heap in O(n) time using bottom-up heapify
• In-place sorting with O(1) auxiliary space
• Implement both max-heap and min-heap versions

Counting Sort (10 points)

Implement counting sort for non-negative integers:

/**
 * Counting Sort - O(n + k) time, O(k) space, stable
 * k = range of input values
 */
public static void countingSort(int[] arr) {
    if (arr.length == 0) return;
    
    // Find range
    int max = Arrays.stream(arr).max().getAsInt();
    int min = Arrays.stream(arr).min().getAsInt();
    int range = max - min + 1;
    
    // Create count array and output array
    int[] count = new int[range];
    int[] output = new int[arr.length];
    
    // Count occurrences
    // Compute cumulative counts
    // Place elements in sorted order
}

// Sort objects by a key
public static  void countingSortByKey(T[] arr, Function keyExtractor, int maxKey);

Radix Sort (15 points)

Implement radix sort for integers (LSD and MSD variants):

/**
 * Radix Sort (LSD) - O(d * (n + k)) time
 * d = number of digits, k = radix (base)
 */
public static void radixSortLSD(int[] arr) {
    int max = getMax(arr);
    
    // Sort by each digit position, starting from least significant
    for (int exp = 1; max / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

/**
 * Radix Sort (MSD) - O(d * (n + k)) time
 * Recursive, most significant digit first
 */
public static void radixSortMSD(int[] arr) {
    // Find max to determine number of digits
    // Recursively sort by each digit position
}

// For strings
public static void radixSortStrings(String[] arr);

Requirements:

• Handle negative numbers correctly
• Implement both LSD (iterative) and MSD (recursive)
• Include string radix sort variant

Bucket Sort (10 points)

Implement bucket sort for uniformly distributed data:

/**
 * Bucket Sort - O(n) average time for uniform distribution
 * O(n²) worst case, O(n + k) space
 */
public static void bucketSort(float[] arr) {
    int n = arr.length;
    if (n <= 0) return;
    
    // Create n empty buckets
    List> buckets = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        buckets.add(new ArrayList<>());
    }
    
    // Put array elements in different buckets
    for (float value : arr) {
        int bucketIndex = (int) (n * value); // Assumes [0, 1)
        buckets.get(bucketIndex).add(value);
    }
    
    // Sort individual buckets (using insertion sort)
    // Concatenate all buckets into arr[]
}

// For integers with known range
public static void bucketSort(int[] arr, int numBuckets);

Merge Sort Applications (20 points)

Use merge sort technique to solve these problems:

/**
 * Count inversions in an array using modified merge sort
 * Inversion: arr[i] > arr[j] where i < j
 * Time: O(n log n)
 */
public static long countInversions(int[] arr) {
    // Use merge sort, count inversions during merge step
}

/**
 * Find the k-th smallest element using quickselect
 * Average O(n), worst O(n²)
 */
public static int quickSelect(int[] arr, int k) {
    // Partition-based selection
}

/**
 * Merge k sorted arrays into one sorted array
 * Time: O(n log k) where n = total elements
 */
public static int[] mergeKSortedArrays(int[][] arrays) {
    // Use min-heap or divide & conquer
}

Activity Selection Problem (20 points)

Implement the classic greedy activity selection:

public class Activity {
    int id;
    int start;
    int finish;
    Activity(int id, int start, int finish);
}

/**
 * Select maximum number of non-overlapping activities
 * Greedy: always select activity with earliest finish time
 */
public static List selectActivities(Activity[] activities) {
    // Sort by finish time
    // Greedily select compatible activities
}

/**
 * Weighted Activity Selection (harder variant)
 * Each activity has a value/profit - maximize total value
 * Requires DP, not pure greedy
 */
public static int maxValueActivities(Activity[] activities, int[] values) {
    // DP solution with binary search
}

Include in README: Explain why greedy works (exchange argument proof)

Interval Scheduling Problems (20 points)

Solve these interval-based optimization problems:

public class Interval {
    int start;
    int end;
    Interval(int start, int end);
}

/**
 * Merge overlapping intervals
 * Example: [[1,3],[2,6],[8,10]] -> [[1,6],[8,10]]
 */
public static List mergeIntervals(List intervals) {
    // Sort by start, merge overlapping
}

/**
 * Minimum number of meeting rooms required
 * (Interval partitioning problem)
 */
public static int minMeetingRooms(Interval[] intervals) {
    // Use min-heap or event processing
}

/**
 * Insert interval into sorted non-overlapping list
 * Merge if necessary
 */
public static List insertInterval(List intervals, Interval newInterval) {
    // Handle before, overlapping, and after cases
}

/**
 * Remove minimum intervals to make rest non-overlapping
 */
public static int eraseOverlapIntervals(Interval[] intervals) {
    // Greedy: keep interval with earliest end
}

Huffman Coding (25 points)

Implement Huffman encoding and decoding:

public class HuffmanNode implements Comparable {
    char character;
    int frequency;
    HuffmanNode left, right;
    
    // For leaf nodes
    HuffmanNode(char ch, int freq);
    // For internal nodes
    HuffmanNode(int freq, HuffmanNode left, HuffmanNode right);
    
    public int compareTo(HuffmanNode other) {
        return this.frequency - other.frequency;
    }
}

public class HuffmanCoding {
    
    /**
     * Build Huffman tree from character frequencies
     */
    public static HuffmanNode buildHuffmanTree(Map frequencies) {
        // Use min-heap to build tree
        PriorityQueue pq = new PriorityQueue<>();
        // Add all characters as leaf nodes
        // Repeatedly combine two minimum nodes
    }
    
    /**
     * Generate Huffman codes from tree
     * Returns map: character -> binary code string
     */
    public static Map generateCodes(HuffmanNode root) {
        // Traverse tree, left = 0, right = 1
    }
    
    /**
     * Encode a string using Huffman codes
     */
    public static String encode(String text, Map codes) {
        // Replace each character with its code
    }
    
    /**
     * Decode a Huffman-encoded string
     */
    public static String decode(String encoded, HuffmanNode root) {
        // Traverse tree based on 0/1 bits
    }
}

Requirements:

• Prove Huffman produces optimal prefix codes
• Calculate compression ratio for sample texts
• Handle edge cases (single character, empty string)

Divide & Conquer Problems (20 points)

Solve these classic D&C problems:

/**
 * Maximum subarray sum (Kadane's is O(n), but implement D&C version)
 * Time: O(n log n)
 */
public static int maxSubarraySumDC(int[] arr) {
    // Divide array, find max in left, right, and crossing
}

/**
 * Closest pair of points in 2D
 * Time: O(n log n)
 */
public static double closestPair(Point[] points) {
    // Sort by x, divide, combine with strip check
}

/**
 * Count smaller elements to the right of each element
 * Returns array where result[i] = count of arr[j] < arr[i] for j > i
 */
public static int[] countSmaller(int[] arr) {
    // Modified merge sort with index tracking
}

/**
 * Strassen-like matrix multiplication (simplified)
 * Divide 2x2 blocks
 */
public static int[][] matrixMultiply(int[][] A, int[][] B) {
    // Divide & conquer approach
}

Greedy Problems (15 points)

Solve additional greedy optimization problems:

/**
 * Fractional Knapsack Problem
 * Items can be broken into fractions
 * Greedy: take items with best value/weight ratio
 */
public static double fractionalKnapsack(int[] values, int[] weights, int capacity) {
    // Sort by value/weight ratio, greedily fill
}

/**
 * Job Scheduling with Deadlines
 * Each job has profit and deadline - maximize profit
 */
public static int jobScheduling(int[] deadlines, int[] profits) {
    // Greedy with Union-Find for slot allocation
}

/**
 * Minimum Platforms for Train Station
 * Given arrival and departure times, find min platforms needed
 */
public static int minPlatforms(int[] arrivals, int[] departures) {
    // Event-based processing
}

/**
 * Gas Station Circuit
 * Can you complete circular route starting from some station?
 */
public static int canCompleteCircuit(int[] gas, int[] cost) {
    // Greedy: track cumulative gas
}