GATE Problem Solving Techniques & Application Skills 3 — Questions and Answers
Question 1: A function f(n) = 3f(n/2) + n has a solution according to the Master Theorem of:
- O(n)
- O(n log n)
- O(n^log₂3) (Correct answer)
- O(n²)
Correct answer: O(n^log₂3)
By the Master Theorem with a=3, b=2, f(n)=n: log₂3 ≈ 1.585 > 1, so f(n) = O(n^log₂3) by Case 1.
Question 2: Two workers A and B can complete a job in 12 days and 15 days respectively. How many days will they take working together?
- 5 days
- 6 days
- 6.67 days (Correct answer)
- 7 days
Correct answer: 6.67 days
Combined rate = 1/12 + 1/15 = 9/60 = 3/20 per day, so time = 20/3 ≈ 6.67 days.
Question 3: In a logic puzzle, if P → Q is true and Q → R is true, which conclusion is always valid?
- R → P
- P → R (Correct answer)
- ¬P → ¬R
- Q ↔ R
Correct answer: P → R
By hypothetical syllogism (transitivity of implication), P → Q and Q → R together imply P → R.
Question 4: A box contains 3 red, 4 blue, and 5 green balls. One ball is drawn at random. What is the probability it is NOT green?
- 5/12
- 7/12 (Correct answer)
- 1/2
- 2/3
Correct answer: 7/12
Total balls = 12; non-green = 7; P(not green) = 7/12.
Question 5: Which technique is used when a problem can be solved by making the locally optimal choice at each step and this leads to a global optimum?
- Backtracking
- Memoization
- Greedy algorithm (Correct answer)
- Branch and bound
Correct answer: Greedy algorithm
The greedy algorithm makes locally optimal (greedy) choices at each step, which for problems with the greedy choice property leads to a globally optimal solution.
Question 6: An algorithm has a time complexity of O(2^n). If n=10 takes 1 ms, approximately how long does n=20 take?
- 2 ms
- 20 ms
- 1024 ms (Correct answer)
- 100 ms
Correct answer: 1024 ms
O(2^n): doubling n from 10 to 20 increases runtime by 2^10 = 1024 times, so 1 ms × 1024 = 1024 ms.
Question 7: A number is divisible by 8 if and only if:
- The sum of its digits is divisible by 8
- Its last digit is divisible by 8
- Its last two digits form a number divisible by 8
- Its last three digits form a number divisible by 8 (Correct answer)
Correct answer: Its last three digits form a number divisible by 8
A number is divisible by 8 if and only if its last three digits form a number divisible by 8, since 1000 = 8 × 125.
GATE Problem Solving Techniques & Application Skills 3
A function f(n) = 3f(n/2) + n has a solution according to the Master Theorem of: