CIS 275 Discrete Math I Fall 2017

Assignment 04

Evaluation:

As described in the syllabus, the assignments are 20% of the overall grade for the

regular student and 30% for the online student.

Submission:

Submit your document at the beginning of the lecture on Monday 11/15/17. No

late submission will be accepted.

Exercise 1: Tell whether or not each relation is linear homogeneous recurrence relation

with constant coefficients. Give the order of each linear homogeneous recurrence

relations with constant coefficients.

An = -3 An-1

An = An-1 + n

An = (lg2n) An-1 [lg(n-1)] An-2

An = - An-1 + 5 An-2 3 An-3

Exercise 2: Solve the recurrence relation for the initial condition given.

An = -3 An-1; A0 = 2

An = 6 An-1 8 An-2; A0 = 1 and A1 = 0

2An = 7 An-1 3 An-2; A0 = A1 = 1

An = -8 An-1 16 An-2; A0 =2 and A1 = -20

Exercise 3:

Let consider to the sequence

S1 = C, S2= G, S3 = J, S4 = M, S5 = X

Refer to the sequence S to show how the algorithm of the binary search executes in case

key = G.

Algorithm: The binary search:

Input: A sequence Si, Si+1, , Sj, i 1, sorted in nondecreasing order, a

value key, i and j.

Output: The output is an index k fro which Sk = key, or if key is not in the

sequence, the output is the value 0.

1. Binary_search(S, i, j, key) {

2. if (i > j) // not found

3. return 0

4. k = |_(i + j)/2_|

5. if (key ==Sk) // found

6. return k

7. if (key < Sk) // search left half

8. j = k - 1

9. else // search right half

10. i = k + 1

11. return binary_search(S, i, j, key)

12. }

Exercise 4:

Professor Larry proposes the following version of binary search:

binary_search3(s, i, j, key){

while ( i j) {

k = |_(i+j)/2_|

if (key==Sk)

return k

if (key < Sk)

j = k

else

i = k

}

return 0

}

Is professors version correct (does it find key if it is present and return 0 if it is not

present? If the professors version is correct, what is the worst-case time?