Description
1. Express β (3π
3 β 6π + 2)
π
π=0
as a polynomial p(n). Then prove that the sum = p(n) by
induction.
2. Aerosort is a sorting algorithm.
Aerosort(A, i, j) // A is array to sort; i and j are start and end
indices.
n = j β i + 1
If (n < 10) {
sort A[iβ¦j] by insertion-sort
return
}
m1 = i + 3 * n / 4
m2 = i + n / 4
Aerosort(A, i, m1)
Aerosort(A, m2, j)
Aerosort(A, i, m1)
a. What is the asymptotic worst-case running time of Aerosort? Show your work.
b. Prove that Aerosort(A, 1, n) correctly sorts an array A of n elements.
3. Devise a comparison-based algorithm (no bucket or radix sort, for instance) to
simultaneously find the minimum and the maximum element in a list of n numbers
using at most 3n/2 comparisons. Give pseudocode.
4. Give an efficient algorithm to convert a given ο’-bit (binary) integer to a decimal
representation. Argue that if multiplication or division of integers whose length is at
most ο’ takes time M(ο’), then binary-to-decimal conversion can be performed in time
Ξ(M(ο’) log ο’). (Hint: use a divide-and-conquer approach, obtaining the top and bottom
halves of the result with separate recursions.)
