Reference no: EM131465973

1. State the definition of an algorithm and define specific attributes that must be possessed by an algorithm.

2. Mathematically prove or disprove: log₆x = ½log₃x

3. Prove that (n + 1)² ∈ 0(n²) by giving the smallest value of n₀ and corresponding constant c in the definition of 0-notation.

4. What, if anything, is wrong with the following statement?

Since n = O(n), 2n = O(n),..., we have _k=1∑ⁿkn = _k=1∑ⁿO(n) = O(n²)

5. Which of the following are true and which are false? If true, provide the smallest value of no and corresponding constants c₁ and c₂ satisfying the definition of Θ-notation.

a. 2/n + 4/n² ∈ Θ(1/n²)

b. n log₁₀n ∈ Θ (n log₂n)

c. log₂n^½ ∈ Θ (log₂n)

6. Give asymptotically tight big-O bounds for T(n) in each of the following recurrences. Justify your solution by naming the master method case, by iterating the recurrence or by using the substitution method.

a. T(n) = T(n - 2) + 1

b. T(n) = 2T(n/2) + n lg² n

c. T(n) = 9T(n/4) + n²

d. T(n) = 3T(n/2) + n

e. T(n) = T(n/2 + n^0.5) + n

7. Consider a set S of n ≥ 2 distinct numbers all greater than zero in unsorted order. For each of the problems below:

• Give an algorithm to determine two distinct numbers x and y in the set S that satisfy the condition(s) of the problem.
• Your algorithm must be specified using pseudocode in the style of the text.
• You must justify that your algorithm has the requested run time.

a. In O(n Ig n) time, determine x, y ∈ S such that x ≠ y and |x-y| ≤ |w-z| for all w, z ∈ S such that w ≠ z.

b. In O(n) time, determine x, y ∈ S such that |x - y| ≥ |w-z| for all w, z ∈ S for all w, z ∈ S such that w ≠ z.