20260917 Lecture 4

CSE 030: Data Structures & Algorithms — Comprehensive Study Guide

SECTION 1: ARCHITECTURAL FOUNDATIONS & ASYMPTOTIC COMPLEXITY

1.1 First Principles of Time Complexity Analysis

Time complexity quantifies the amount of time taken by an algorithm to execute relative to the size of its input $n$. Rather than measuring physical clock time (which fluctuates based on hardware architecture, background processes, and CPU throttling), computer scientists measure the growth rate of computational operations.

The asymptotic bounds utilized across Lectures 5 and 6 are defined as:

• $O(1)$ — Constant Time: Execution time is constant, regardless of the input size. The number of basic CPU instructions executed remains fixed.

• $O(\log n)$ — Logarithmic Time: Execution time grows logarithmically with the input size. Algorithms in this class repeatedly divide the problem search space in half (e.g., binary search, recursion tree height in divide-and-conquer).

• $O(n)$ — Linear Time: Execution time is directly proportional to the size of the input. Processing requires visiting or shifting every element in an $n$-element collection once.

• $O(n\log n)$ — Linearithmic Time: Standard optimal comparison-based sorting complexity. Represents $n$ operations performed across $\log n$ recursive partitioning or merging levels.

• $O(n^2)$ — Quadratic Time: Execution time is proportional to the square of the input size. Typically arises from nested iterations over an $n$-element container.

1.2 The Underlying Container: ArrayList Architecture & Cost Model

The algorithms studied in Lectures 5 and 6 operate directly on the custom templated ArrayList<T>. Understanding how ArrayList organizes memory on the heap is essential for evaluating sorting mechanics.

Class State Representation:

• T* data: Raw pointer to a dynamically allocated contiguous memory block on the heap.
• int size: The number of active, valid elements populated by the caller.
• int capacity: The physical count of elements allocated in the current heap array.

The Central Class Invariant:

size is never equal to capacity. There is always at least one free slot at the end of the array. This architectural guarantee ensures that data[size] is always safe to write without checking capacity beforehand. Every mutating operation that appends or inserts an element must restore this invariant before returning.

Operation Cost Breakdown:

• Random Access (operator[], at(index)): $O(1)$. Contiguous memory allows direct address arithmetic: *(data + index).

• Appending (append(T value)): Amortized $O(1)$. Direct write to data[size], followed by size++. An array reallocation (inflate()) doubles capacity only when size == capacity, making resizing infrequent.

• Front and Arbitrary Insertion (prepend(T value), insert(int index, T value)): $O(n)$. Requires shifting elements to the right walking backwards (for (int i = size; i > index; i--) data[i] = data[i-1];) to avoid overwriting unshifted data.

• Front Removal (removeFirst()): $O(n)$. Requires shifting elements left walking forwards (for (int i = 0; i < size - 1; i++) data[i] = data[i+1];).

• End Removal (removeLast()): $O(1)$ amortized. Decrements size directly. If capacity > 1 && size < capacity / 4, it invokes deflate() via shrinkIfSparse().

SECTION 2: THE FOUR SORTING ALGORITHMS (MECHANICS, CODE & TRACES)

2.1 Selection Sort (Iterative In-Place Minimum Selection)

Core Concept: Selection Sort divides the array into a sorted part (initially empty, expanding from index $0$) and an unsorted part. On each iteration $i$, it scans the entire remaining unsorted range $[i,n-1]$ to locate the index of the minimum element (minIndex), then performs a single swap placing that minimum element at index $i$.

Repository Implementation:

template <class T>
 
void selectionSort(ArrayList<T>& list) {
    for (int i = 0; i < list.getSize(); i++) {
        int minIndex = i;
        
        for (int j = i; j < list.getSize(); j++) {
            if (list[j] < list[minIndex]) {
                minIndex = j;
            }
        }
        T temp = list[i];
        list[i] = list[minIndex];
        list[minIndex] = temp;
    }
}

Step-by-Step Trace:

Input: [3, 7, 5, 9, 1] ($n=5$)

• Pass $i=0$: Unsorted: [3, 7, 5, 9, 1]. Min is 1 at index 4. Swap list[0] (3) and list[4] (1) -> [1 | 7, 5, 9, 3].

• Pass $i=1$: Unsorted: [7, 5, 9, 3]. Min is 3 at index 4. Swap list[1] (7) and list[4] (3) -> [1, 3 | 5, 9, 7].

• Pass $i=2$: Unsorted: [5, 9, 7]. Min is 5 at index 2. Min is already at index 2; swap in place -> [1, 3, 5 | 9, 7].

• Pass $i=3$: Unsorted: [9, 7]. Min is 7 at index 4. Swap list[3] (9) and list[4] (7) -> [1, 3, 5, 7 | 9].

• Pass $i=4$: Single element remaining; sorted array: [1, 3, 5, 7, 9].

Complexity Analysis:

• Outer loop runs $n$ times: $O(n)$.

• Inner loop runs $(n-i)$ times, averaging $n/2$ comparisons: $O(n)$.

• Total operations: ${\sum }_{i=0}^{n-1}(n-i)=\frac{n(n+1)}{2}=O(n^2)$.

• Best vs. Worst Case: There is no best or worst case. Even if the list is already sorted, the inner loop still scans every element of the unsorted portion to confirm the minimum. Time complexity is strictly $O(n^2)$ across all input distributions.

2.2 Insertion Sort (Iterative Adaptive Shifting)

Core Concept: Insertion Sort divides the array into a sorted part (initially containing just the first element at index $0$) and an unsorted part (indices $1$ to $n-1$). It sequentially takes the first element of the unsorted part (list[i]) and shifts it leftward through the sorted part by swapping with adjacent elements as long as the element to its left is strictly greater.

Repository Implementation:

template <class T>
void insertionSort(ArrayList<T>& list) {
    for (int i = 1; i < list.getSize(); i++) {
        int j = i;
        while (j > 0 && list[j] < list[j - 1]) {
            T temp = list[j];
            list[j] = list[j - 1];
            list[j - 1] = temp;
            j--;
        }
    }
}

Step-by-Step Trace:

Input: [4, 3, 2, 1] ($n=4$)

• Pass $i=1$: Key 3. Compare 3 < 4 -> Swap -> [3, 4, 2, 1]. Loop terminates ($j=0$).

• Pass $i=2$: Key 2. Compare 2 < 4 -> Swap -> [3, 2, 4, 1]. Compare 2 < 3 -> Swap -> [2, 3, 4, 1].

• Pass $i=3$: Key 1. Compare 1 < 4 -> Swap -> [2, 3, 1, 4]. Compare 1 < 3 -> Swap -> [2, 1, 3, 4]. Compare 1 < 2 -> Swap -> [1, 2, 3, 4].

Complexity Analysis:

• Best Case: $O(n)$
  Occurs when the input array is already sorted (e.g., [1, 2, 3, 4]).
  Outer loop executes $n-1$ times. On every iteration, the condition list[j] < list[j - 1] evaluates to false immediately on the very first test. The inner loop does not perform any swaps and terminates in $O(1)$. Total work: $(n-1)\times O(1)=O(n)$.
• Worst Case: $O(n^2)$
  Occurs when the array is in reverse sorted order (e.g., [4, 3, 2, 1]). Every element must shift all the way to index $0$, executing $i$ swaps per pass: ${\sum }_{i=1}^{n-1}i=\frac{n(n-1)}{2}=O(n^2)$.
• Average Case: $O(n^2)$
  For random permutations, each element shifts halfway through the sorted section on average.

2.3 Merge Sort (Recursive Divide and Conquer)

Core Concept: Merge Sort applies divide-and-conquer

1. Divide: If the list has size $\le 1$, it is already sorted (base case). Otherwise, divide the elements into two halves: left (indices $0$ to $\lfloor n/2\rfloor -1$) and right (indices $\lfloor n/2\rfloor$ to $n-1$).
2. Conquer: Recursively sort left and right.
3. Combine: Merge the two sorted sublists into a single sorted list in $O(n)$ time using two pointers.

Repository Implementation:

template <class T> ArrayList<T> merge(ArrayList<T> &left, ArrayList<T> &right) {
    ArrayList<T> combined;
 
    int i = 0;
    int j = 0;
    while (i < left.getSize() && j < right.getSize()) {
        if (left[i] < right[j]) {
            combined.append(left[i]);
            i++;
        } else {
            combined.append(right[j]);
            j++;
        }
    }
 
    while (i < left.getSize()) {
        combined.append(left[i]);
        i++;
    }
 
    while (j < right.getSize()) {
        combined.append(right[j]);
        j++;
    }
 
    return combined;
}
 
template <class T> ArrayList<T> mergeSort(ArrayList<T> &list) {
    if (list.getSize() <= 1) {
        return list;
    } else {
        ArrayList<T> left;
        ArrayList<T> right;
 
        for (int i = 0; i < list.getSize(); i++) {
            if (i < list.getSize() / 2) {
                left.append(list[i]);
            } else {
                right.append(list[i]);
            }
        }
 
        left = mergeSort(left);
        right = mergeSort(right);
 
        ArrayList<T> result = merge(left, right);
 
        return result;
    }
}

Conceptual Recursion Tree & Work Breakdown

• Halving an array of size $n$ produces a recursion tree of height $\approx {\log }_{2}n$.

• At each level of the tree, the total number of elements merged across all subproblems is exactly $n$.

• Total work: $(\text{Tree Height})\times (\text{Work per Level})=({\log }_{2}n)\times O(n)=O(n\log n)$.

• Best, Worst, and Average Cases: Strictly $O(n\log n)$. The structural halving and linear merging are independent of initial element ordering.

• Trade-off: The implementation allocates auxiliary ArrayList instances on the heap for sublists, incurring an $O(n)$ space complexity overhead.

2.4 Quick Sort (In-Place Partitioning & Recursive Ordering)

Core Concept: A divide-and-conquer algorithm that sorts in place without allocating auxiliary list buffers:

1. Pivot Selection: Choose a pivot element (in the repository: the middle element at index $(left+right)/2$).

2. Partitioning: Initialize two indices: $i$ starting at $left$ and $j$ starting at $right$. Increment $i$ while list[i] < pivot and decrement $j$ while list[j] > pivot. When both stop and $i\le j$, swap list[i] and list[j], then increment $i$ and decrement $j$. Repeat until the pointers cross ($i>j$).

3. Divide: All elements in $[left,j]$ are $\le pivot$, and all elements in $[i,right]$ are $\ge pivot$.

4. Recursion: Recursively apply Quick Sort to the left partition $[left,j]$ and the right partition $[i,right]$ as long as boundaries remain valid.

Repository Implementation:

template <class T> void quickSort(ArrayList<T> &list, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        int pivot = list[(left + right) / 2];
 
        while (i <= j) {
            while (list[i] < pivot) {
                i++;
            }
 
            while (list[j] > pivot) {
                j--;
            }
 
            if (i <= j) {
                T temp;
                temp = list[i];
                list[i] = list[j];
                list[j] = temp;
                i++;
                j--;
            }
        }
 
        quickSort(list, left, j);
        quickSort(list, i, right);
    }
}

Step-by-Step Pointer Execution & Partition Animation:

Input: [7, 3, 5, 4, 9], left = 0, right = 4$.

• Pivot calculation: pivot = list[(0 + 4) / 2] = list[2] = 5.

• Pointer initialization: $i=0$ (value 7), $j=4$ (value 9).

• while (list[i] < 5): list[0] = 7, not < 5 -> stops at $i=0$.

• while (list[j] > 5): list[4] = 9 > 5 -> $j$ decrements to 3 (list[3] = 4). 4 not > 5 -> stops at $j=3$.

• Condition $i\le j$ ($0\le 3$) holds: Swap list[0] (7) and list[3] (4). Array becomes: [4, 3, 5, 7, 9]. Advance pointers: $i=1,j=2$.

Next loop:

• Advance $i$: list[1] = 3 < 5 -> $i$ advances to 2 (list[2] = 5). Not < 5 -> stops at $i=2$.

• Decrement $j$: list[2] = 5, not > 5 -> stops at $j=2$.

• $i\le j$ ($2\le 2$) holds: Swap list[2] with itself. Advance pointers: $i=3,j=1$.

• Pointers have crossed ($i=3>j=1$). Outer while terminates.

• Sub-calls spawned:

• Left partition: quickSort(list, 0, 1) on subarray [4, 3].

• Right partition: quickSort(list, 3, 4) on subarray [7, 9].

Complexity Analysis

• Best & Average Case: $O(n\log n)$
  Occurs when the pivot consistently divides the range into roughly equal halves. The recursion tree reaches depth $O(\log n)$, with $O(n)$ comparisons per depth level.

• Worst Case: $O(n^2)$
  Occurs when the pivot is consistently the extreme smallest or largest element in the range (e.g., already sorted array when choosing an edge element as pivot, or pathological adversarial inputs). This produces an unbalanced partition of size $1$ and size $n-1$, collapsing recursion tree depth to $n$ and yielding $O(n^2)$ total operations.

SECTION 4: 20 PRE-QUIZ COMPREHENSION & MASTERY QUESTIONS

Part A: Short-Answer Conceptual Questions (Questions 1 – 12)

Question 1 [4 Points]

State the foundational class invariant maintained by ArrayList<T>. Explain why data[size] is unconditionally safe to overwrite during an append() operation.

Question 2 [4 Points]

Analyze the time complexity of random access in ArrayList<T> (via operator[] or at(index)). Why does reading an element take $O(1)$ time regardless of whether $n=10$ or $n=1,000,000$?

Question 3 [4 Points]

Selection Sort executes a nested loop structure. Provide the exact mathematical summation representing the number of comparisons executed for an array of size $n$, and explain why there is no best-case scenario.

Question 4 [5 Points]

Insertion Sort exhibits an adaptive best-case time complexity of $O(n)$, whereas its worst-case is $O(n^2)$. Detail the exact input configuration required to achieve the best-case bound, and describe the internal loop execution that makes this possible.

Question 6 [5 Points]

In insertionSort(), explain the function of the compound while-loop condition while (j > 0 && list[j] < list[j - 1]). What happens if the order of these two operands is swapped to while (list[j] < list[j - 1] && j > 0)?

Question 7 [5 Points]

Merge Sort achieves $O(n\log n)$ time complexity across all input distributions. Explain the structural source of the $\log n$ term and the $n$ term in this bound using the divide-and-conquer recursion tree model.

Question 8 [4 Points]

Examine the helper function merge(ArrayList<T>& left, ArrayList<T>& right). What is the maximum number of element comparisons performed by the initial while loop relative to the sizes of left and right?

Question 9 [5 Points]

Quick Sort has an average-case time complexity of $O(n\log n)$ and a worst-case time complexity of $O(n^2)$. Explain what conditions cause Quick Sort to degrade to its quadratic worst case, and what that does to the recursion tree.

Question 10 [4 Points]

With the quickSort() implementation, the pivot is selected via int pivot = list[(left + right) / 2];. Why does this strategy prevent worst-case degradation on arrays that are already sorted in ascending order?

Question 11 [4 Points]

Contrast the space complexity of Merge Sort and Quick Sort as implemented in the lecture repository. Why is Quick Sort classified as an in-place sort while Merge Sort is not?

Part B: Code Implementation for ArrayList Functions (Questions 13 – 16)

Question 13 [6 Points]

Write an external templated function isSorted(const ArrayList<T>& list) that determines whether an ArrayList<T> is sorted in non-decreasing order. The function must execute with an optimal time complexity of $O(n)$ and $O(1)$ auxiliary space.

Question 14 [7 Points]

Write an external templated function descendingInsertionSort(ArrayList<T>& list) that sorts an ArrayList<T> in descending order (largest to smallest) using the insertion sort algorithm. Your solution must modify the list in place and preserve adaptive $O(n)$ best-case behavior.

Question 15 [7 Points]

Write an external templated function countOccurrences(const ArrayList<T>& list, T target) that returns the total count of occurrences of target in the list. Your function must utilize const-correct indexing and execute in $O(n)$ time without modifying the input list.

Question 16 [7 Points]

Write an external templated function partitionAroundThreshold(ArrayList<T>& list, T threshold) inspired by Quick Sort’s partitioning step. The function must rearrange the elements in place such that all elements strictly less than threshold appear before all elements greater than or equal to threshold. The function should return the integer index representing the boundary where the elements $\ge threshold$ begin.

Part C: Debugging & Method Misuse Scenarios (Questions 17 – 20)

Question 17 [5 Points]

A student implements a batch removal algorithm designed to empty an $n$-element ArrayList<T>:

while (!list.isEmpty()) {
    list.removeFirst();
}

Explain why this code exhibits catastrophic $O(n^2)$ overall performance. Identify the correct method from ArrayList that should be used to empty the list in $O(n)$ total time, and explain the mechanical difference.

Question 18 [6 Points]

A student attempts to write an in-place selection sort on an ArrayList<int>:

for (int i = 0; i < list.getCapacity(); i++) {
    int minIndex = i;
 
    for (int j = i; j < list.getCapacity(); j++) {
        if (list[j] < list[minIndex]) {
            minIndex = j;
        };
    };
 
    int temp = list.at(i);
 
    list.set(i, list.at(minIndex));
    list.set(minIndex, temp);
}

Identify the fatal logical error regarding size versus capacity. Explain what runtime exception occurs and why iterating to capacity violates data structure invariants.

Question 19 [6 Points]

A student writes a recursive Quick Sort routine but modifies the inner pointer scanning loops as follows:

while (i <= j) {
    while (list[i] <= pivot) { // Error introduced here
        i++;
    };
    
    while (list[j] >= pivot) { // Error introduced here
        j--;
    };
 
    if (i <= j) {
        T temp = list[i];
 
        list[i] = list[j];
        list[j] = temp;
 
        i++;
        j--;
    }
}

If this function is executed on an array where all elements are identical (e.g., [5, 5, 5, 5, 5]), explain the severe runtime error that occurs. Trace the pointers $i$ and $j$ to demonstrate why the strict comparisons (< and >) are mandatory.

When printed, the list is completely unsorted! Explain why list remains unchanged after calling mergeSort(list). What correction must be applied to main.cpp to properly update and benchmark the sorted output?

CSE 030: MASTER ANSWER KEY & AI EVALUATION RUBRIC

Section A: Conceptual & Complexity Analysis

Note

Question 1: ArrayList Contiguous Heap Memory & Random Access [4 Points] Prompt: Explain why random access (retrieving an element by index) in an ArrayList executes in $O(1)$ constant time, regardless of whether the list contains 5 elements or 5,000,000 elements. Reference the underlying heap pointer arithmetic in your explanation.

• Model Answer: ArrayList elements reside in a contiguous heap-allocated array referenced by pointer T* data. The memory address of any arbitrary index $i$ is calculated directly via pointer arithmetic: $\text{Address}(i)=\text{data}+(i\times \text{sizeof}(T))$ Because this calculation requires only a single multiplication and addition executed directly in CPU registers, retrieving or modifying any index requires a fixed sequence of machine cycles ($O(1)$) without traversing preceding elements.

• AI Grader Scoring Criteria:

  • +2 pts: States elements reside in contiguous memory on the heap.
  • +2 pts: References pointer arithmetic or direct base-plus-offset calculation (data + i * sizeof(T)).
  • Deduction (-2 pts): Merely claims “it takes one step” without citing contiguous memory or pointer arithmetic mechanics.

• Key Evaluation Keywords: contiguous memory, pointer arithmetic, base address, offset, constant time O(1).

Note

Question 2: Selection Sort Mechanics & Invariant Inelasticity [4 Points] Prompt: State the 4 procedural steps of Selection Sort. Why does Selection Sort have no best-case scenario (i.e., why does it remain $O(n^2)$ even if provided an array that is already sorted in ascending order)?

• Model Answer:
  1. Divide array into sorted (initially empty) and unsorted parts.
  2. In each iteration, find smallest element in the unsorted part of the array.
  3. Swap the smallest found element with the first element of the unsorted part.
  4. Repeat steps 2 and 3 until entire array becomes sorted. Selection Sort has no best case because the inner loop unconditionally scans every remaining element in the unsorted sub-array to verify the minimum index. It lacks an adaptive early-exit mechanism to detect that the array is already sorted.
• AI Grader Scoring Criteria:
  • +2 pts: Lists all 4 procedural steps accurately in order.
  • +2 pts: Explains that the inner loop unconditionally executes across all remaining unsorted elements without early termination.
  • Deduction (-1 pt): Omits or misstates any of the 4 steps.
• Key Evaluation Keywords: divide sorted/unsorted, find minimum, swap, unconditional scan, no early-exit.

Note

Question 3: Mathematical Summation for Selection Sort Comparisons [4 Points] Prompt: In Selection Sort, if an array holds $n$ elements, exactly how many comparisons does the inner loop perform over the course of the entire algorithm? Express your answer as a summation and simplify it to show how $O(n^2)$ is derived.

• Model Answer: For an array of size $n$, pass 0 compares $n-1$ elements, pass 1 compares $n-2$ elements, down to the final pass comparing 1 element: ${\sum }_{k=1}^{n-1}k=\frac{n(n-1)}{2}=\frac{n^2-n}{2}$ Dropping lower-order terms ($-n/2$) and the constant factor ($1/2$) yields the asymptotic growth rate $O(n^2)$.

• AI Grader Scoring Criteria:

  • +2 pts: Expresses the comparison count as the summation of integers from 1 to $n-1$ (or 1 to $n$).
  • +1 pt: States the closed-form formula $\frac{n(n-1)}{2}$ or $\frac{n(n+1)}{2}$.
  • +1 pt: Expands to $n^2/2$ and isolates dominant asymptotic complexity $O(n^2)$.

• Key Evaluation Keywords: summation, closed form, n(n-1)/2, dominant term, O(n^2).

Note

Question 4: Insertion Sort vs. Selection Sort on Sorted Data [5 Points] Prompt: Detail the 5 procedural steps of Insertion Sort. Contrast the mechanical operation of Insertion Sort against Selection Sort when both are executed on an array that is already completely sorted.

• Model Answer:
  • Steps: (1) Divide array into sorted (first element) and unsorted part. (2) Select first element of unsorted part. (3) Compare with elements to its left in sorted part. (4) Swap leftward until in correct position. (5) Repeat steps 2 through 4 until sorted.
  • Contrast on Sorted Data: On an already sorted array, Selection Sort still unconditionally scans the entire unsorted partition taking $O(n^2)$ comparisons. In contrast, Insertion Sort evaluates list[j] < list[j - 1], finds it false on the very first evaluation, and immediately aborts the inner while loop. It performs exactly 1 comparison and 0 swaps per outer pass, completing in $O(n)$ linear time.
• AI Grader Scoring Criteria:
  • +2 pts: Lists all 5 steps of Insertion Sort accurately.
  • +3 pts: Contrasts mechanical behavior on sorted data: Selection Sort still scans all elements ($O(n^2)$), while Insertion Sort inner loop exits immediately on the first comparison ($O(n)$).
• Key Evaluation Keywords: sorted partition, compare leftward, shift leftward, early exit, O(n) vs O(n^2).

Note

Question 5: Insertion Sort Boundary Conditions & Complexity Bounds [5 Points] Prompt: Explain the exact mathematical conditions under which Insertion Sort achieves its best-case time complexity of $O(n)$ versus its worst-case time complexity of $O(n^2)$. Cite the specific behavior of the inner while loop condition while (j > 0 && list[j] < list[j - 1]) in both scenarios.

• Model Answer:
  • Best Case ($O(n)$): Occurs when the input is pre-sorted in ascending order. For every outer index $i$, list[j] < list[j - 1] evaluates to false on the first iteration. The loop terminates in 1 comparison with 0 swaps. Work: $(n-1)\times 1=O(n)$.
  • Worst Case ($O(n^2)$): Occurs when the input is in reverse sorted order. Every candidate element is strictly smaller than all elements to its left. list[j] < list[j - 1] evaluates to true for all $j$ from $i$ down to 1. The loop executes $i$ comparisons and $i$ swaps per pass. Total work: ${\sum }_{i=1}^{n-1}i=\frac{n(n-1)}{2}=O(n^2)$.
• AI Grader Scoring Criteria:
  • +2.5 pts: Analyzes best case: pre-sorted input, condition evaluates to false immediately, 1 check per pass, $O(n)$ total.
  • +2.5 pts: Analyzes worst case: reverse sorted input, condition evaluates to true across entire sorted partition, shifts all elements, $O(n^2)$ total.
• Key Evaluation Keywords: already sorted, reverse sorted, while condition evaluates to false, maximum shifts, O(n), O(n^2).

Note

Question 6: Linear Recombination Property of Merge Sort [4 Points] Prompt: Explain the fundamental algorithmic concept behind merging two sorted lists. Why does merging two sorted lists of size $n_1$ and $n_2$ run in $O(n_1+n_2)$ linear time rather than quadratic time?

• Model Answer: Merging exploits the invariant that both sub-lists are already sorted. At each step, the algorithm only compares the current front elements (left[i] and right[j]). Whichever is smaller is appended to combined, and only that list’s index advances. Because each comparison permanently consumes one element into the merged list without ever re-evaluating or backtracking over previous elements, the total number of operations is bounded by $n_1+n_2$, executing in $O(n_1+n_2)$ linear time.

• AI Grader Scoring Criteria:

  • +2 pts: Identifies that sub-lists are pre-sorted, requiring only front elements (left[i] vs right[j]) to be compared.
  • +2 pts: Explains that each comparison advances an index and consumes an element with zero backtracking, bounding operations to $O(n_1+n_2)$.

• Key Evaluation Keywords: pre-sorted invariant, front element comparison, pointer advancement, no backtracking, linear time O(n).

Note

Question 7: Merge Sort Recursion Tree Model [5 Points] Prompt: Trace the recursion tree of Merge Sort for an input ArrayList of size $n$. Explain how the combination of recursive decomposition depth and per-level merge work yields a total time complexity of $O(n\log n)$ in all cases.

• Model Answer:
  • Decomposition: Dividing a list of size $n$ in half repeatedly until single-element base cases (size $\le 1$) are reached forms a binary recursion tree of depth $\lceil {\log }_{2}n\rceil$.
  • Recombination: At each horizontal level of the recursion tree, all $n$ elements participate in pairwise comparisons and linear merge appending passes, demanding $O(n)$ total work per level.
  • Total Asymptotic Work: $\text{Total Work}=(\text{Work per level})\times (\text{Tree depth})=O(n)\times O(\log n)=O(n\log n)$ Because binary halving and per-level recombination are structural and input-agnostic, Merge Sort executes in $O(n\log n)$ across best, average, and worst cases.
• AI Grader Scoring Criteria:
  • +2 pts: Identifies tree depth as ${\log }_{2}n$ due to recursive halving.
  • +2 pts: States that total merge work across each horizontal level is $O(n)$.
  • +1 pt: Concludes $O(n\log n)$ holds across all cases due to input-agnostic execution.
• Key Evaluation Keywords: recursion tree depth, log2(n) levels, O(n) work per level, divide-and-conquer, all cases O(n log n).

Note

Question 8: Quick Sort Pivot Mechanics & Partial Ordering [5 Points] Prompt: In Quick Sort, what is the role of the pivot? When partitioning elements around the pivot, why is it accurate to state that the left and right sub-arrays are partitioned, but not necessarily sorted?

• Model Answer: The pivot acts as a reference benchmark value to segment the dataset. Partitioning rearranges elements such that all values smaller than the pivot are placed in the left partition, and all values greater than or equal are placed in the right partition. However, within each partition, elements are swapped solely to satisfy their relationship to the pivot, not relative to each other. Thus, sub-partitions are segregated with respect to the pivot value, but remain unsorted internally until subsequent recursive sub-partitions sort them.

• AI Grader Scoring Criteria:

  • +2 pts: Explains the pivot’s role as a dividing boundary/benchmark.
  • +3 pts: Articulates why sub-partitions are unsorted internally (elements are swapped based on threshold comparison with the pivot, not pairwise intra-partition comparisons).

• Key Evaluation Keywords: reference value, boundary, segregated by pivot, unsorted internally, relative order not established.

Note

Question 9: Quick Sort Complexity Spectrum & Pathological Degradation [5 Points] Prompt: Analyze the best-case, average-case, and worst-case time complexities of Quick Sort. Describe the specific pivot selection pattern and data distribution that triggers the pathological $O(n^2)$ worst case.

• Model Answer:
  • Best Case ($O(n\log n)$): Occurs when the pivot is the median value, dividing the array into two equal halves ($n/2$), yielding ${\log }_{2}n$ recursion levels of $O(n)$ partition work.
  • Average Case ($O(n\log n)$): Occurs under typical randomized data distributions.
  • Worst Case ($O(n^2)$): Occurs when the chosen pivot is consistently an extreme value (minimum or maximum) in the current sub-range (e.g., selecting first or last elements on sorted/reverse-sorted data). This creates an unbalanced partition of size $0$ (or $1$) and $n-1$, producing a linear chain of $n$ recursion levels. Summing $n$ levels of linear work yields $O(n^2)$.
• AI Grader Scoring Criteria:
  • +1.5 pts: Identifies Best ($O(n\log n)$) and Average ($O(n\log n)$) with median/balanced split justification.
  • +2.5 pts: Details Worst Case ($O(n^2)$): extreme pivot selection creates lopsided 1 vs $n-1$ splits across $n$ recursion levels.
  • +1 pt: Demonstrates clear mathematical connection between recursion depth and total work.
• Key Evaluation Keywords: median pivot, balanced split, extreme min/max, lopsided split, n recursive levels, O(n^2).

Note

Question 10: Space Complexity Profiles: In-Place Quick Sort vs. Merge Sort [4 Points] Prompt: Compare the auxiliary memory (space complexity) profiles of the repository implementations of Merge Sort and Quick Sort. Why does this Merge Sort implementation incur an $O(n)$ heap allocation overhead while Quick Sort operates in-place?

• Model Answer: The repository implementation of Merge Sort splits lists by dynamically constructing new instances: ArrayList<T> left; ArrayList<T> right; ArrayList<T> combined;. This requires allocating new heap arrays at each recursion level, resulting in $O(n)$ auxiliary space complexity. In contrast, Quick Sort operates in-place by swapping elements directly within the original heap array via indices left and right. Its only extra memory is the function call stack frames, consuming $O(\log n)$ auxiliary stack space on average ($O(n)$ worst case).

• AI Grader Scoring Criteria:

  • +2 pts: Explains that Merge Sort dynamically allocates auxiliary ArrayList heap objects ($O(n)$ auxiliary memory).
  • +2 pts: Explains that Quick Sort operates in-place on the existing heap buffer, using only call-stack activation frames ($O(\log n)$ space).

• Key Evaluation Keywords: auxiliary heap allocation, in-place, memory buffer, call-stack frames, O(n) space vs O(log n) space.

Note

Question 11: Empirical Microbenchmarks vs. Asymptotic Predictions [5 Points] Prompt: The repository uses Timestamp startInsert; ... Timestamp endInsert; int duration = endInsert - startInsert; to benchmark algorithms. Why must empirical benchmark results across varying input sizes ($N=10,100,1000,10000$) be interpreted cautiously when testing algorithms with identical asymptotic complexities like Merge Sort and Quick Sort?

• Model Answer: Empirical benchmarking reflects total wall-clock time, which incorporates low-level hardware factors not captured by Big-O notation:
  1. Constant Factors: Quick Sort has smaller constant factors than Merge Sort because it performs in-place swaps without dynamic heap reallocations (new[] / delete[]).
  2. CPU Cache Locality: Contiguous in-place swaps in Quick Sort maximize CPU L1/L2 cache hits, whereas Merge Sort incurs cache misses and memory allocator overhead.
  3. Threshold Effects: For small $N$ ($N=10$ or $100$), startup overhead and constant factors dominate asymptotic behavior. Theoretical differences become clear only as $N\to \infty$.
• AI Grader Scoring Criteria:
  • +2 pts: Identifies constant factor differences and dynamic memory allocation overhead.
  • +2 pts: Explains hardware cache locality or memory bus performance impacts.
  • +1 pt: Observes that small $N$ benchmarks are dominated by constant overhead rather than asymptotic growth.
• Key Evaluation Keywords: constant factors, cache locality, memory allocation overhead, small N threshold, hardware effects.

---

Section B: Algorithmic Implementation Tasks

Note

Question 13: Templated Binary Search on Sorted ArrayList [6 Points] Prompt: Write a templated standalone function binarySearch that searches a pre-sorted ArrayList<T> for a given target value.

• C++ Implementation:

  template <class T>
  int binarySearch(const ArrayList<T>& list, const T& target) {
      int low = 0;
      int high = list.getSize() - 1;
      
      while (low <= high) {
          // Overflow-safe midpoint calculation
          int mid = low + (high - low) / 2;
          
          if (list[mid] == target) {
              return mid;
          } else if (list[mid] < target) {
              low = mid + 1;
          } else {
              high = mid - 1;
          }
      }
      return -1; // Target not found
  }

• AI Grader Scoring Criteria:

  • +1 pt: Correct function signature, template declaration, and passing const ArrayList<T>&.
  • +1 pt: Initializes low = 0 and high = list.getSize() - 1.
  • +1 pt: Loop condition while (low <= high).
  • +1 pt: Overflow-safe midpoint calculation low + (high - low) / 2.
  • +1 pt: Correct three-way branch comparisons and index boundary updates.
  • +1 pt: Returns -1 when target is absent.

Note

Question 14: Bubble Sort with Early-Exit Optimization [7 Points] Prompt: Write a templated function bubbleSort that sorts an ArrayList<T> in ascending order, incorporating an early-exit optimization flag.

• C++ Implementation:

  template <class T>
  void bubbleSort(ArrayList<T>& list) {
      int n = list.getSize();
      for (int i = 0; i < n - 1; i++) {
          bool swapped = false;
          for (int j = 0; j < n - i - 1; j++) {
              if (list[j + 1] < list[j]) {
                  T temp = list[j];
                  list[j] = list[j + 1];
                  list[j + 1] = temp;
                  swapped = true;
              }
          }
          // Early-exit optimization: list is already sorted
          if (!swapped) {
              break;
          }
      }
  }

• AI Grader Scoring Criteria:

  • +1 pt: Correct template declaration and pass-by-reference parameter ArrayList<T>&.
  • +1 pt: Outer loop runs up to n - 1.
  • +2 pts: Inner loop runs up to n - i - 1 with adjacent comparisons.
  • +1 pt: Correct element swapping logic using a temporary variable.
  • +2 pts: Correctly declares, flags, and evaluates bool swapped to achieve $O(n)$ best case.

Note

Question 15: Descending Selection Sort [6 Points] Prompt: Write a templated function descendingSelectionSort that sorts an ArrayList<T> in descending order (largest to smallest) using the selection sort paradigm.

• C++ Implementation:

  template <class T>
  void descendingSelectionSort(ArrayList<T>& list) {
      int n = list.getSize();
      for (int i = 0; i < n; i++) {
          int maxIndex = i;
          for (int j = i; j < n; j++) {
              if (list[j] > list[maxIndex]) { // Locate largest remaining element
                  maxIndex = j;
              }
          }
          T temp = list[i];
          list[i] = list[maxIndex];
          list[maxIndex] = temp;
      }
  }

• Complexity Justification: Remains $O(n^2)$ in all cases because the inner loop still unconditionally scans every element in the unsorted partition from $i$ to $n-1$ to verify maxIndex.

• AI Grader Scoring Criteria:

  • +1 pt: Template syntax and pass-by-reference parameter.
  • +2 pts: Initializes maxIndex = i and updates with list[j] > list[maxIndex].
  • +2 pts: Swaps list[i] with list[maxIndex].
  • +1 pt: States that time complexity remains $O(n^2)$ unconditionally.

Note

Question 16: Bounds-Safe Sorting Verification isSorted [6 Points] Prompt: Write a templated verification function isSorted that inspects an ArrayList<T> and returns true if all elements are sorted in non-decreasing (ascending) order, and false otherwise.

• C++ Implementation:

  template <class T>
  bool isSorted(const ArrayList<T>& list) {
      if (list.getSize() <= 1) {
          return true; // Trivially sorted
      }
      for (int i = 0; i < list.getSize() - 1; i++) {
          if (list[i + 1] < list[i]) {
              return false; // Inversion detected
          }
      }
      return true;
  }

• AI Grader Scoring Criteria:

  • +1 pt: Template declaration and const ArrayList<T>& list parameter.
  • +2 pts: Handles base cases (getSize() <= 1) returning true.
  • +2 pts: Single-pass loop checking adjacent inversions with immediate false return.
  • +1 pt: Guarantees strict $O(n)$ time and $O(1)$ auxiliary space.

---

Section C: Architectural Debugging & Method Misuse Scenarios

Note

Question 17: Prepend Misuse in Merge Recombination [5 Points] Scenario:

while (i < left.getSize() && j < right.getSize()) {
    if (left[i] < right[j]) {
        combined.prepend(left[i]); // Line modified
        i++;
    } else {
        combined.prepend(right[j]); // Line modified
        j++;
    }
}

• Diagnostics & Mechanical Analysis:
  1. Logical Reversal Bug: prepend() inserts each new element at index 0. Smaller elements inserted first are continuously pushed to the right, inverting the order and producing a list sorted in descending order rather than ascending order.
  2. Catastrophic Performance Degradation: In the ArrayList contiguous heap memory model, prepend() shifts every existing element one index to the right ($O(k)$ shifts). Calling prepend() $n$ times transforms merge() from $O(n)$ linear time into $O(n^2)$ quadratic time: ${\sum }_{k=1}^{n}k=O(n^2)$ Consequently, overall mergeSort() collapses from $O(n\log n)$ to $O(n^2)$.
• AI Grader Scoring Criteria:
  • +2 pts: Identifies that prepending inverts output into descending order.
  • +2 pts: Explains that ArrayList::prepend() performs an $O(n)$ memory shift on every call.
  • +1 pt: Concludes that merge() degrades to $O(n^2)$, causing mergeSort() to collapse to $O(n^2)$.
• Key Evaluation Keywords: reverse/descending order, memory shift, O(n) prepend cost, quadratic merge O(n^2).

Note

Question 18: Faulty Hoare Partitioning & Sub-Problem Stagnation [6 Points] Scenario:

template <class T>
void buggyQuickSort(ArrayList<T>& list, int left, int right) {
    if (left < right) {
        int i = left, j = right;
        int pivot = list[(left + right) / 2];
        while (i < j) { // Bug 1: changed <= to <
            while (list[i] < pivot) i++;
            while (list[j] > pivot) j--;
            if (i < j) {
                T temp = list[i];
                list[i] = list[j];
                list[j] = temp;
                i++;
                j--;
            }
        }
        buggyQuickSort(list, left, i);      // Bug 2: using i instead of j
        buggyQuickSort(list, i + 1, right);
    }
}

• Diagnostics & Mechanical Analysis:
  1. Partition Overlap Failure: Using while (i < j) instead of while (i <= j) terminates the outer loop immediately when $i==j$. Neither pointer advances past the middle element, failing to create a valid crossover boundary.
  2. Sub-Problem Stagnation & Stack Overflow: When processing duplicate values (e.g., [5, 5, 5, 5]), $i$ and $j$ halt immediately at the center index. Because pointers do not cross and $i$ does not advance past left, the recursive invocation buggyQuickSort(list, left, i) re-invokes on the exact same problem range [left, right]. The sub-problem size never shrinks, triggering infinite recursion and a call stack overflow crash (SIGSEGV).
• AI Grader Scoring Criteria:
  • +3 pts: Identifies that i < j halts when i == j without advancing/crossing pointers.
  • +3 pts: Explains that passing (left, i) fails to shrink the sub-problem size on duplicate keys, causing infinite recursion / call stack overflow.
• Key Evaluation Keywords: pointer crossover, sub-problem failure to shrink, identical duplicates, infinite recursion, call stack overflow.

Note

Question 19: Uninitialized Buffer Access via set() [5 Points] Scenario:

ArrayList<int> list;
for (int i = 0; i < 10; i++) {
    list.set(i, i * 10);
}
// Crashes with std::logic_error: Index is out of bounds

• Diagnostics & Mechanical Analysis:
  1. Exception Cause: In ArrayList.h, set(int index, T value) enforces bounds against size, not capacity:

     if (index < 0 || index >= size) throw std::logic_error("Index is out of bounds");

     On a default-constructed list, capacity == 1 but size == 0. When $i=0$, $0\ge 0$ evaluates to true, throwing an immediate out-of-bounds exception.
  2. Class Invariant & Encapsulation: set() replaces an existing element at an active logical index within $[0,\text{size}-1]$. It cannot create new elements or alter size. In contrast, append() inserts a new element into pre-allocated memory slot data[size], increments size++, and restores the class invariant (size < capacity) by invoking inflate() when required.
• AI Grader Scoring Criteria:
  • +2 pts: Explains that set() checks bounds against size (which is initially 0), throwing an exception on the first iteration.
  • +3 pts: Contrasts set() (modifies existing elements without changing size) against append() (adds elements, writes to data[size], increments size, and inflates).
• Key Evaluation Keywords: size vs capacity, guards against size, uninitialized slot, append() increments size.