• İhsan Doğramacı Bilkent University

• CS 473

Makeup MWE, 3 Sessions, May 21, 2020

Bilkent University, CS 473/573, Session 2, 30pts, 40min

Q2: You are to sort n employees in a company into k equal-sized groups by income (assume that

no two employees have the same income, n is a multiple of k , and k is a power of 2 for simplicity).

Denote these groups as G1, G2, ..., Gk . The groups must have the property that ∀i < j , every

person in Gi has a lower income than every person in Gj . The ordering within any particular group is

of no significance. Give an O(n · lg k) -time algorithm to produce k such groups to deserve full credit.

An expected O(n · k) - time algorithm will deserve 12 pts.