首页 > > 详细

Assignment 1CMPT 307

 CMPT 307

Summer 2020
Assignment 1
Submit on CS Submission Server/CourSys.
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.)
联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!