Problem Solving Techniques & Application Skills Flashcards

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

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.

Two workers A and B can complete a job in 12 days and 15 days respectively. How many days will they take working together?

Answer: 6.67 days

Combined rate = 1/12 + 1/15 = 9/60 = 3/20 per day, so time = 20/3 ≈ 6.67 days.

In a logic puzzle, if P → Q is true and Q → R is true, which conclusion is always valid?

Answer: P → R

By hypothetical syllogism (transitivity of implication), P → Q and Q → R together imply P → R.

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?

Answer: 7/12

Total balls = 12; non-green = 7; P(not green) = 7/12.

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?

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.

An algorithm has a time complexity of O(2^n). If n=10 takes 1 ms, approximately how long does n=20 take?

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.

A number is divisible by 8 if and only if:

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.