CMPT 307 Summer 2020 Assignment 1
Submit on CS Submission Server/CourSys. 4 problems; 10 points each.
1. Express ∑𝑛𝑖=0(3𝑖3 − 6𝑖 + 2) as a polynomial p(n). induction.
Then prove that the sum = p(n) by
2. Aerosort is a sorting algorithm. Aerosort(A, i, j)
indices. n=j–i+1
// A is array to sort; i and j are start and end
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.)