Problem 1.
(30 Marks) Consider the following three methods of solving a particular problem (input size n):
1. You divide the problem into seven subproblems, each 17 the size of the original problem, solve each recursively, then combine the results with a cost 12n + 3 where n is the original problem size.
2. You reduce the problem size by 2, solve the subproblem recursively, then com- bine the results with a cost 120 operations.
Copyright By PowCoder代写 加微信 powcoder
3. You divide the problem into 2 subproblems, each 12 of size of the original problem, solve each recursively, then combine the results with a cost 2n2+3n+5 where n is the original problem size.
Assume the base case has size 1 for all three methods.
For each method, write a recurrence capturing its worst-case runtime. Which of the three methods yields the fastest asymptotic runtime?
In your solution, you should use the Master Theorem wherever possible. In the case where the Master Theorem doesn¡¯t apply, clearly state why not based on your recurrence, and show your work solving the recurrence using another method (no proofs required).
Problem 2.
(20 marks)
A number is called monotone if it consists of repeated decimal digits. For example, 3333 and 7777 are monotone numbers.
(i) (10 Marks) Write a divide and conquer function (in pseudocode) with time complexity ¦¨(n) named multiply_monotone that takes as input a two mono- tone numbers. We assume n is maximum length (number of digits) of the two monotone numbers, and in turn, the length of each of them (for simplicity) may be taken to be a power of 2. You may assume a number is represented as a string of digits.
(ii) (10 Marks) Using Master Theorem, argue that the time complexity of your code is ¦¨(n).
Problem 3.
(20 marks) The algorithm Occur(A, f, l, x) below returns the number of occurrences of x in array A between positions f and l. More precisely, it satisfies the following precondition/postcondition pair:
Precondition: A is an array, f and l are integers such that 1 ¡Ü f ¡Ü l ¡Ü length(A).
Postcondition: The integer returned by the algorithm is the number of elements of the following set: {j : f ¡Ü j ¡Ü l ¡Ä A[j] = x}.
Occur(A, f, l, x) t=0
while i<=l {
if A[i] == x { t=t+1
Provide a complete proof of correctness of this algorithm.
Problem 4. (20 marks)
Consider this alogrithm form the lecture:
// pre: array A.length > 42
// post: return the index of the last 42 in A
// return -1 if not found
int FindLastFortyTwo(A) {
6 return -1; }
for (i = A.length-1; i >= 0; i–) {
if (A[i] == 42) {
Compute the average runtime for this program, assuming the inputs we consider are any permutation of numbers from 1 to n for n > 42.
Problem 5. (10 marks)
Consider this function:
boolean freaky(n) {
// PRE: n is a positive integer
// POST: ???
return false x=2
while x < n {
if n mod x == 0
return false x= x+1
return true
(i) (5 marks) Find the postcondition of this function
(ii) (5 marks ) Find the best possible big-oh bound for its complexity
(iii) (Just think ... no marks for this part). What can we say about big-theta complexity for this function?
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com