Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP 3270

Assignment 2

Instructions:

1. This is an individual assignment. There are 10 problems.

2. Late submissions will not be accepted unless prior permission has been granted or there is a valid and verifiable excuse.

3. Think carefully; formulate your answers, and then write them out concisely using English, logic, mathematics and pseudocode (no programming language syntax).

4. Type your final answers in this Word document.

5. Don’t turn in handwritten answers with scribbling, cross-outs, erasures, etc. If an answer is unreadable, it will earn zero points.

1. (6 points) Prove that the following algorithm is correct by using the “Proof by Loop Invariants” method.

Hint: Loop Invariant S_i=x is not equal to any of the first i elements of the array

2. (5 points) Order the following list of functions by the big-Oh notation. Group together (for example by underlining) those functions that are big-Theta to each other.

3. (5 points) Describe a method for finding both the minimum and maximum of n numbers using fewer than 3n/2 comparisons. Hint: First construct a group of candidate minimums and a group of candidate maximums.

4. (18 points) 

Algorithm Mystery(A: Array [i..j] of integer) i & j are array starting and ending indexes

if i=j then return A[i]

else

k=i+floor((j-i)/2)

temp1= Mystery(A[i..k])

temp2= Mystery(A[(k+1)..j]

if temp1<temp2 then return temp1 else return temp2

(a) (1 points) What does the recursive algorithm above compute?

(b) (4 points) Develop and state the two recurrence relations exactly (i.e., determine all constants) of this algorithm by following the steps outlined in L7-Chapter4.ppt. Determine the values of constant costs of steps using directions provided in L5-Complexity.ppt. Show details of your work if you want to get partial credit.

(c) (6 points) Use the Recursion Tree Method to determine the precise mathematical expression T(n) for this algorithm. First, simplify the recurrences from part (b) by substituting the constant “c” for all constant terms. Drawing the recursion tree may help but you do not have to show the tree in your answer; instead, fill the table below. Use the examples worked out in class for guidance. Show details of your work if you want to get partial credit.

You will need the following result:  

(d) (1 points) Based on T(n) that you derived, state the order of complexity of this algorithm:

5. (10 points) T(n)=7T(n/8)+cn; T(1)=c. Determine the polynomial T(n) for the recursive algorithm characterized by these two recurrence relations, using the Recursion Tree Method. Drawing the recursion tree may help but you do not have to show the tree in your answer; instead, fill the table below.  You will need to use the following results, where and b are constants and x<1:

6. (11 points) Use the substitution method to prove the guess that is indeed correct when T(n) is defined by the following recurrence relations: T(n)=3T(n/3)+5; T(1)=5.  At the end of your proof state the value of constant c that is needed to make the proof work.

Statement of what you have to prove:

Base Case proof:

Inductive Hypotheses:

Inductive Step:

Value of c:

7. (16 points) Guess a plausible solution for the complexity of the recursive algorithm characterized by the recurrence relations T(n)=T(n/2)+T(n/4)+T(n/8)+T(n/8)+n; T(1)=c using the Substitution Method. (1) Draw the recursion tree to three levels (levels 0, 1 and 2) showing (a) all recursive executions at each level, (b) the input size to each recursive execution, (c) work done by each recursive execution other than recursive calls, and (d) the total work done at each level. (2) Pictorially show the shape of the overall tree. (3) Estimate the depth of the tree at its shallowest part. (4) Estimate the depth of the tree at its deepest part. (5) Based on these estimates, come up with a reasonable guess as to the Big-Oh complexity order of this recursive algorithm. Your answer must explicitly show every numbered part described above in order to get credit.

8. (10 points) Use the Substitution Method to prove that your guess for the previous problem is indeed correct.

Statement of what you have to prove:

Base Case proof:

Inductive Hypotheses:

Inductive Step:

9. (9 points) Use the Master Method to solve the following three recurrence relations and state the complexity orders of the corresponding recursive algorithms.

(a) T(n)=2T(99n/100)+100n

(b) T(n)=16T(n/2)+n³lgn

(c) TT(n)=16T(n/4)+n²

10. (10 points) Use Backward Substitution (10 points) and then Forward Substitution (10 points) to solve the recurrence relations T(n)=2T(n-1)+1;T(0)=1. In each case, do the following: (1) Show at least three expansions so that the emerging pattern is evident. (2) Then write out T(n) fully and simplify using equation (A.5) on Text p.1147. (3) Verify your solution by substituting it in the LHS and RHS of the recurrence relation and demonstrating that LHS=RHS. (4) Finally state the complexity order of T(n). You must show your work for parts (1)-(3) to receive credit.