GATE Problem Solving Techniques & Application Skills 3

Question 1

A function f(n) = 3f(n/2) + n has a solution according to the Master Theorem of:

Accepted Answer

O(n^log₂3)

Answer

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?

Accepted Answer

6.67 days

Answer

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?

Accepted Answer

P → R

Answer

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?

Accepted Answer

7/12

Answer

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?

Accepted Answer

Greedy algorithm

Answer

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.

(GATE) Graduate Aptitude Test in Engineering Practice Test

(GATE) Graduate Aptitude Test in Engineering Practice Test

GATE Problem Solving Techniques & Application Skills 3