Discrete Mathematics Week 11 NPTEL

Discrete Mathematics Week 11 NPTEL Assignment Answers

Check and submit Discrete Mathematics Week 11 NPTEL assignment answers here

1. Which of the following are true?

• 500n2 < 1500n
• 5000n2 > n3
• 300n > 3n2
• 999n2 < 9n3

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𝑇(2)=1
• T(n)=T(n)+T(n−1) such that T(1)=2)
• 𝑇(𝑛)=𝑇(𝑛−1)+𝑇(𝑛−2) such that T(1)=2 and T(2)=3
• 𝑇(𝑛)=𝑇(𝑛−2)+𝑇(𝑛−3) such that T(1)=1 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?

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

These are the Discrete Mathematics Week 11 NPTEL Assignment Answers

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.

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

5. Which of the following sequence is correct?

• 𝑂(log(𝑛)) < 𝑂(log(𝑛^2)) < 𝑂(𝑛) < 𝑂(𝑛 log(𝑛)) < 𝑂(𝑛^2)
• 𝑂(log(𝑛)) < 𝑂(log(𝑛^2)) < 𝑂(𝑛) < 𝑂(𝑛^2) < 𝑂(𝑛 log(𝑛))
• 𝑂(𝑛) < 𝑂(𝑛^2) < 𝑂(log(𝑛)) < 𝑂(log(𝑛^2)) < 𝑂(𝑛 log(𝑛))
• 𝑂(𝑛) < 𝑂(𝑛^2) < 𝑂(log(𝑛)) < 𝑂(𝑛 log(𝑛)) < 𝑂(log(𝑛^2))
• 𝑂(log(𝑛^2)) < 𝑂(𝑛 log(𝑛)) < 𝑂(log(𝑛)) < 𝑂(𝑛) < 𝑂(𝑛^2)

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

• 17711
• 46368
• 75025
• 28657

These are the Discrete Mathematics Week 11 NPTEL Assignment Answers

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)

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.

• 𝑎_{20} = 𝑎_{19} − 𝑎_{18}
• 𝑎_{20} = 𝑎_{19} + 𝑎_{17}
• 𝑎_{20} = 𝑎_{20} − 𝑎_{19}
• 𝑎_{20} = 𝑎_{18} + 𝑎_{19}

9. What can we say about the following function?

f1(n)=40n^3
f2(n)=50n^2
f3(n)=23n^2+20n
f4(n)=18n^3+5n^2+9n

• 𝑓3(𝑛) is an order n function
• 𝑓2(𝑛) grows faster than f1(n)
• f4(n) is an order n^3 function
• 𝑓2(𝑛) and f3(n) grow slower than f1(n)

These are the Discrete Mathematics Week 11 NPTEL Assignment Answers

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

• an=(20/7)^n−(6/7)n−(6/7)𝑛
• an=(4/7)^n−(37)n−(3/7)𝑛
• an=(3)^n−(10)^n
• an=(5)^n−(−2)^n

---

---

These are the solution of Discrete Mathematics Week 11 NPTEL Assignment Answers

More Discrete Mathematics Weeks Solution: https://progies.in/answers/nptel/discrete-mathematics-solution

More NPTEL Solution: https://progies.in/answers/nptel

---