# Discrete Mathematics | Week 11

## Quiz

1. Which of the following are true?

500n2 < 1500n

5000n2 > n3

300n > 3n2

999n2 < 9n3

d. 999n2 < 9n3

Explanation

2. How many n-bit binary strings are possible without having consecutive ones?

c. T(n)=T(n−1)+T(n−2) such that T(1)=2 and T(2)=3

Explanation

3. Let an be a sequence that satisfies the recurrence relation an= 20an-1− 25an-2 where a0=4 and a1=14. What are a3 and a4 respectively?

b.  3250, 60500

Explanation

4. Which of the following statement(s) is/are true?

I) The solution for the tower of Hanoi is 2n – 1.

II) The recurrence relation for the tower of Hanoi is 𝑇(𝑛)=2𝑇(𝑛−1) + 1 for T1 = 1.

III) Complexity of tower of Hanoi is n2.

c. I and II

Explanation

5. Which of the following sequence is correct?

a. O(log(n)) < O(log(n2)) < O(n) < O(nlog(n))<O(n2)

Explanation

6. Given the sequence {0, 1, 1, 2, 3, 5, 8, 13……} find is the 23rd term this sequence.

d. 28657

Explanation

7. Paras is reading a novel that consists of 1000 pages. While he reads the book, his dad calls him for some work. Being in a hurry, he forgets to put the bookmark on the page he was reading, though he remembers the page number. How much minimum effort would Paras require to get back to the page that he last visited, if he uses an efficient searching technique?

c.  log(1000)

Explanation

8. Which of the following is the correct recurrence relation for climbing 20 stairs? Climbing stairs simply means walking on stairs, covering one stair in one step.

d. a20 = a18 + a19

Explanation

9. What can we say about the following function?

c. f4(n) is an order n^3 function
d.
f2(n) and f3(n) grow slower than f1(n)

Explanation

10. What is the solution of the recurrence relation an= 3𝑎(n-1)−10𝑎(n-2)? given that a0=1 and a1=2.

Explanation

KUIZZER Helping Educational website for Youngers

Welcome To Kuizzer!

KUIZZER - Helping Educational Website for YoungersYour Post is going to visible like this

Here, Your Promotional Details are going to visible for others whenever they visit the site !