CMPT 307
Assignment 1
4 problems; 10 points each.
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.)
