गुरुर्ब्रह्मा गुरुर्विष्णु गुरुर्देवो महेश्वरा गुरुर्साक्षात परब्रह्म तस्मै श्री गुरवे नमः !

WEEK-11

Week 11: Assignment 11

1) Which of the following are true?

500n^2 < 1500n
5000n^2 > n^3
300n > 3n^2
999n^2 < 9n^3

Correct Answer : 999n^2 < 9n^3

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

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

Correct Answer :T(n)=T(n−1)+T(n−2) such that T(1)=2 and T(2)=3

3) Let an be a sequence that satisfies the recurrence relation a_n=20a_n−1−25a_n−2 where a₀=4 and a₁=14. What are a₃ and a₄ respectively?

180, 3250
3250, 60500
250, 4625
7950, 168500

Correct Answer : 3250, 60500

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

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

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

III) Complexity of tower of Hanoi is n2.

II and III
I II and III
I and II
I and III

Correct Answer : I and II

5) Which of the following sequence is correct?

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

Correct Answer : O(log(n)) < O(log(n2)) < O(n) < O(nlog(n))<O(n2)

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

17711
46368
75025
28657

Correct Answer : 28657

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?

log(500)
log(10000)
log(1000)
log(1000000)

Correct Answer :log(1000)

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.