Discrete Mathematics | Week 11
Quiz
Link : Discrete Mathematics Week 11 (nptel.ac.in)
1. Which of the following are true?
500n2 < 1500n
5000n2 > n3
300n > 3n2
999n2 < 9n3
d. 999n2 < 9n3
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
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
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
5. Which of the following sequence is correct?
a. 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.
d. 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?
c. 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.
d. a20 = a18 + a19
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)
10. What is the solution of the recurrence relation an= 3𝑎(n-1)−10𝑎(n-2)? given that a0=1 and a1=2.
* The material and content uploaded on this website are for general information and reference purposes only and don’t copy the answers of this website to any other domain without any permission or else copyright abuse will be in action.
Please do it by your own first!
