Reference no: EM131981433

Questions -

Q1. Suppose T(n) is defined recursively as follows

T(0) = 0

T(n) = 2 · T(n - 1) + n

Which of the following is a valid formula for T(n)?

T(n) = 2(n² + n + 1)

T(n) = 2ⁿ - 1

T(n) = 2ⁿ⁺¹ - n - 2

T(n) = 2ⁿ⁺¹ - 1

T(n) = n² + n + 1

T(n) = 2n² + 2n

Q2. Order the following functions in increasing asymptotic complexity.

(I) 3n log(n) + 2n²

(II) 5nlog^(loh(n))

(III) 3n/√(n+1)

(IV) √(7n³+3n+1)

(I) < (IV) < (II) < (III)

(III) < (II) < (I) < (IV)

(I) < (IV) < (III) < (II)

(II) < (III) < (IV) < (I)

(III) < (IV) < (I) < (II)

(IV) < (II) < (I) < (III)

Q3. Suppose T(n) is defined as follows:

 T(1) = 1

T(n) = 8 · T(n/2) + 2n²(n + 1)

Which of the folding provides the best upper bound for the asymptotic complexity of T(n)?

O(n³·log(n))

O(n³)

O(n^2.5)

O(n²·log(n))

O(n²)

Q4. Suppose T(n) is defined as follows

T(1) = 2

T(n) = 2 · T(n - 1) + 4 · T(n/2)

Which of the following provides the best upper bound for the asymptotic complexity of T(n)?

O(n³)

O(2ⁿ)

O(n² · log(n)

O(n²)

O(n · log(n))

Q5. How many different 7-letter words can be made by using the exact same letters as in SCIENCE (e g SCIENCE counts but CCEINSS does not since d uses only one E)?

Q6. How many numbers in the interval [1, 2000] are divisible by 4 or 14 but not both?

Q7. How many sequences of 10 coin flips have exactly 4 heads and 6 tails?

Q8. How many sequences of n + 1 coin flips, where n > 1, contain no pair of consecutive heads (no HH) and no pair of consecutive talks (no TT)?