Advanced Algorithms Midterm (2025 Spring) Solution
Detailed Answers to Advanced Algorithms Midterm (2025 Spring)
Question 1
1. True.
log(nlog n ) = (log n)(log n) = (log n)2
Thus, clearly, log(nlog n ) = Θ((log n)2 ).
2. False.
Compare the exponential growth rates:
f (n) 4n (4/3)n
= n 10 =
g(n) 3 n n10
As n → ∞, (4/3)n grows exponentially, making the fraction diverge to infinity. Thus, 4n is not O(3n n10 ).
Question 2
1. Using substitution method, assume T (k) ≤ ck 3 for all k < n:
T (n) = T (n − 1) + n2 ≤ c(n − 1)3 + n2 = cn3 − 3cn2 + 3cn − c + n2
For sufficiently large n, choosing c appropriately ensures T (n) ≤ cn3 . Thus, T (n) = O(n3 ).
2. Assume T (n) ≤ cn log n:
cn
T (n) = 2T (n/2) + cn ≤ 2 · log(n/2) + cn = cn log(n/2) + cn = cn(log n − 1) + cn = cn log n
2
Thus, T (n) = O(n log n).
Question 3
1. Using Master theorem, we have a = 3, b = 4, f (n) = nc . Compare f (n) with nlogb a = nlog4 3 ≈ n0.792 :
Since c ≥ 1 > 0.792, by Case 3, we have T (n) = O(nc ).
2. Expand recurrence:
T (n) = log n + log(n − 1) + · · · + log 2 + T (1) = log(n!) = O(n log n)
3. Expand recurrence:
1 1
T (n) = 2
+ + · · · + 1 = O(1)
n (n − 1)2
(this converges to a constant).
4. Master theorem: a = 9, b = 3. Thus, nlogb a = n2 . f (n) = n2 log n is slightly larger. By case 2, we get:
T (n) = O(n2 (log n)2 )
1
Question 4
Loop invariant proof:
Invariant: At the start of each iteration of the outer loop, the sub-array A[0..i − 1] is sorted.
1. Initialization: When i = 1, A[0] is trivially sorted.
2. Maintenance: Assuming the invariant is true for i = k, inserting A[k] at the correct place keeps A[0..k]
sorted.
3. Termination: At termination, A[0..n − 1] is sorted, proving correctness.
Question 5
1 Algorithm (Linear-time):
FindMaximum(A):
max = A[0]
for i = 1 to [Link] - 1:
if A[i] > max:
max = A[i]
return max
Time complexity: O(n).
2 Any algorithm finding the maximum must compare each element at least once (except possibly the first),
hence requiring at least n − 1 comparisons to ensure correctness.
3 Fill in blank: a1 (only one element, return it).
4 Recurrence relation:
T (n) = 2T (n/2) + O(1) → T (n) = O(n)
The running time is O(n), identical in complexity to the iterative solution above.
Question 6
Algorithm (Divide-and-Conquer):
Split ballots into two halves. Recursively find majority ballots in each half. Use sameCandidate to merge
the result, determining the majority ballot.
Pseudocode:
findMajority(Ballots):
if len(Ballots) == 1:
return Ballots[0]
leftMajority = findMajority(left half)
rightMajority = findMajority(right half)
if sameCandidate(leftMajority, rightMajority):
return leftMajority
leftCount = count occurrences of leftMajority
rightCount = count occurrences of rightMajority
if leftCount > len(Ballots)/2:
return leftMajority
else:
return rightMajority
Complexity: O(n log n)
2
Question 7
We are given the array:
A = {12, 4, 18, 2, 8, 11, 5, 14, 9, 3, 15, 6}
Step 1: Initialization
• Pivot element: x = A[r] = 6.
• Initial boundary index: i = −1.
• Iterate j from 0 to 10.
Step 2: Iterations and Swaps
1. j = 0, A[j] = 12, no swap.
2. j = 1, A[j] = 4, swap with A[0]:
A = {4, 12, 18, 2, 8, 11, 5, 14, 9, 3, 15, 6}
3. j = 2, A[j] = 18, no swap.
4. j = 3, A[j] = 2, swap with A[1]:
A = {4, 2, 18, 12, 8, 11, 5, 14, 9, 3, 15, 6}
5. j = 4, A[j] = 8, no swap.
6. j = 5, A[j] = 11, no swap.
7. j = 6, A[j] = 5, swap with A[2]:
A = {4, 2, 5, 12, 8, 11, 18, 14, 9, 3, 15, 6}
8. j = 7, A[j] = 14, no swap.
9. j = 8, A[j] = 9, no swap.
10. j = 9, A[j] = 3, swap with A[3]:
A = {4, 2, 5, 3, 8, 11, 18, 14, 9, 12, 15, 6}
Step 3: Final Swap (Placing Pivot in Position)
Swapping pivot 6 with A[i + 1]:
A = {4, 2, 5, 3, 6, 11, 18, 14, 9, 12, 15, 8}
The pivot is now at its correct position (index 4), and the final partitioned array is:
{4, 2, 5, 3, 6, 11, 18, 14, 9, 12, 15, 8}
3
Question 8
1. Time Complexity:
• Best case: O(n log n). This occurs when the pivot divides the array into two equal (or nearly equal)
halves at each recursive step, resulting in a balanced recursion tree.
• Worst case: O(n2 ). This happens when the pivot consistently partitions the array into highly
unbalanced segments, such as when the smallest or largest element is chosen as the pivot, resulting
in one partition of size 1 and the other of size n − 1 at each step.
• Average case: O(n log n). Over many random arrangements of the input, the divisions tend to be
reasonably balanced, leading to a recursion depth of log n and a cost of n comparisons per level.
2. Pivot Selection:
The choice of pivot significantly influences the balance of partitions during the sorting process. If the pivot
is well-chosen—dividing the array into nearly equal parts—QuickSort achieves its optimal performance of
O(n log n), as the recursion depth remains low. Conversely, poor pivot choices (such as always selecting
the smallest or largest element in a sorted array) can lead to highly unbalanced partitions, causing a
worst-case time complexity of O(n2 ). Common strategies like picking a random pivot or using a median-
of-three approach help maintain balance, thus reducing the probability of hitting the worst-case scenario
and improving overall efficiency.
3. Comparison Bound Proof:
For a list of n distinct elements, consider that
each pair of elements is compared at most once during
partitioning. The number of such pairs is n2 = n(n−1)
2 . Since no pair is compared more than once, the
n(n−1)
total number of comparisons is at most 2 .