2 MARKS QUESTIONS
1. Define the Rule of Sum with an example.
2. Define the Rule of Product with a simple example.
3. What is a permutation?
4. Write the formula for nPr.
5. Define a combination.
6. Write the relation between nPr and nCr .
7. What is the Pigeonhole Principle?
8. Give one example of the Pigeonhole Principle.
9. State the Inclusion–Exclusion principle for two sets.
10. Define a recurrence relation.
11. Give the recurrence relation for Fibonacci numbers.
12. What is a linear recurrence relation?
13. What is Divide and Conquer? Give one example.
14. State the general form of Master Theorem.
15. Define a generating function.
16. What is meant by circular permutation?
17. Define identical permutation with example.
18. Write the characteristic equation of a recurrence relation.
19. State any two applications of Divide and Conquer.
20. Expand the generating function for the sequence 1, 1, 1, 1, …
5 MARKS QUESTIONS
1. Explain the Rule of Sum and Rule of Product with examples.
2. Differentiate between permutations and combinations with examples.
3. Explain permutations of items when some objects are identical.
4. Find how many 6-digit numbers can be formed starting with “30” using distinct digits.
5. Explain the Pigeonhole Principle with two suitable examples.
6. State and explain the Inclusion–Exclusion Principle for three sets.
7. In a class of 50 students, 24 like cold drinks and 36 like hot drinks. If each likes at least
one, find how many like both.
8. Explain Recurrence Relations with examples.
9. Solve the recurrence: an=7an−1−10an−2 given a0=2,a1=3.
10. Explain the steps of Divide and Conquer technique with diagram.
11. Solve using Master theorem: T(n)=T(n/2)+1.
12. Solve using Master theorem: T(n)=2T(n/2)+n.
13. Explain generating functions with the sequence 1,2,3,4,...
14. Explain why the Handshake problem is an application of the Pigeonhole Principle.
15. Find the number of integers from 1 to 50 that are multiples of 2 or 3 but not both.
16. Explain the three cases of solving linear recurrence relations.
17. What are the advantages of Divide and Conquer?
18. Explain the applications of Inclusion–Exclusion principle.
19. Illustrate the concept of circular permutations with example.
20. Solve the recurrence Fn=5Fn−1−6Fn−2 for given initial values.
10 MARKS QUESTIONS
1. Explain permutations and combinations in detail. Give formulas, differences, and solved
examples.
2. State and prove the Inclusion–Exclusion principle. Use an example involving newspapers
A, B, and C.
3. Explain the Pigeonhole Principle in detail. Include birthday example, handshake
example, and 3-students- born-in-same-month problem.
4. Explain recurrence relations in detail. Discuss distinct roots, repeated roots, and complex
roots with examples.
5. Solve the recurrence relation using characteristic equation:
Fn=5Fn−1−6Fn−2, F0=1, F1=4
6. Explain Divide and Conquer technique with applications like Merge Sort, Quick Sort,
FFT, and Strassen’s Matrix Multiplication.
7. Explain the Master Theorem in detail and solve:
o T(n)=2T(n/2)+n
o T(n)=3T(n/2)+n2
o T(n)=T(n/2)+log n
8. Explain generating functions in detail. Show how they are used to solve recurrence
relations.
9. Using Inclusion–Exclusion, find how many integers ≤1000 are NOT divisible by 3, 5, or
7.
10. Describe advanced counting techniques: Recurrence relations, generating functions, and
Inclusion–Exclusion with examples.
11. Explain permutation with restrictions (things always together, never together, definite
positions) with examples.
12. Describe circular permutation and solve two related numerical problems.
13. Explain the advantages and disadvantages of Divide and Conquer algorithms.
14. Discuss the applications and limitations of the Master Theorem.
15. Explain Combinations with multiple-level selection problems (men–women, cows–pigs–
hens) with examples.