Quiz 3

Published

June 9, 2026

CS F364: Design & Analysis of Algorithms

Quiz 3 — June 9, 2026

Coverage: Lectures 1–12

Note

Instructions:

  • Time: 15 minutes.
  • Write your answers clearly on paper, scan, and upload to Google Classroom.
  • Show all steps for full credit.

Question: Median of Medians

The Deterministic Select algorithm (Median of Medians) finds the \(i^{\text{th}}\) smallest element in \(O(n)\) time by:

  1. Dividing the \(n\) elements into groups of 5.
  2. Finding the median of each group (by brute force, \(O(1)\) per group).
  3. Recursively finding the median \(x\) of these \(\lceil n/5 \rceil\) medians.
  4. Partitioning around \(x\) and recursing on the appropriate side.

The recurrence for groups of size 5 is:

\[ T(n) \le T\left(\frac{n}{5}\right) + T\left(\frac{7n}{10}\right) + O(n) \]

(a) [2 marks] Give the recurrence \(T_3(n)\) for the Deterministic Select algorithm when groups of size 3 are used instead of 5. What fraction of elements is guaranteed to be \(\le\) the median-of-medians, and what fraction is guaranteed to be \(\ge\) it?

(b) [2 marks] Give the recurrence \(T_7(n)\) when groups of size 7 are used. What are the corresponding fractions?

(c) [1 mark] Solve \(T_3(n)\) using the substitution method (guess \(T_3(n) \le cn\) and show it fails, then state the actual asymptotic growth).