What is divide and conquer?
A Split, solve, combine
B Guess and verify
C Sort, hash, delete
D Queue, dequeue, restart
Answer: A. Split, solve, combine. Divide and conquer divides a problem, solves subproblems, then combines results.
How does merge sort use divide and conquer?
A Pick pivots and partition
B Scan once and stop
C Use a hash table
D Sort halves then merge
Answer: D. Sort halves then merge. Merge sort recursively sorts halves and merges the results.
What is a recurrence relation used to describe?
A Input encoding only
B Recursive running time
C Memory address arithmetic
D Compiler warning count
Answer: B. Recursive running time. A recurrence expresses a problem cost in terms of smaller input sizes.
What does a recursion tree show?
A Cost across recursive calls
B Tree memory addresses only
C Sorted output values
D Hash collisions
Answer: A. Cost across recursive calls. A recursion tree visualizes subproblem sizes and work at each level.
What is the purpose of a base case?
A Choose a random pivot
B Handle smallest subproblem
C Merge final arrays
D Update a hash bucket
Answer: B. Handle smallest subproblem. A base case returns a direct answer for the simplest input.
What is tail recursion?
A Function calls itself twice
B Recursion uses a queue
C Every call returns an array
D Recursive call is final operation
Answer: D. Recursive call is final operation. In tail recursion, the recursive call occurs as the last operation.
What is memoization?
A Cache results of subproblems
B Sort results after recursion
C Discard repeated inputs
D Convert recursion to a graph
Answer: A. Cache results of subproblems. Memoization stores computed results to avoid solving the same subproblem again.
What property supports dynamic programming?
A Unsorted input only
B Overlapping subproblems
C Distinct subproblems always
D Constant output size
Answer: B. Overlapping subproblems. Dynamic programming benefits when subproblems recur and can share cached results.
What is optimal substructure?
A Optimal solution uses optimal subsolutions
B Every local choice is optimal
C Subproblems never overlap
D Output values are sorted
Answer: A. Optimal solution uses optimal subsolutions. An optimal solution can be built from optimal solutions to smaller subproblems.
What does tabulation usually mean?
A Top down recursion only
B Randomized pivoting
C Bottom up dynamic programming
D Hash table resizing
Answer: C. Bottom up dynamic programming. Tabulation fills a table from smaller cases toward the final result.
What does a greedy algorithm choose?
A Every possible answer
B Locally best available option
C A random state always
D The last input item
Answer: B. Locally best available option. Greedy algorithms make a locally attractive choice at each step.
Does a greedy local choice always yield a global optimum?
A No, only with suitable properties
B Yes for every problem
C Only for recursive inputs
D Yes when data is sorted
Answer: A. No, only with suitable properties. Greedy correctness requires properties that make local choices safe for the global solution.
For activity selection, a common greedy rule chooses?
A Earliest finishing activity
B Longest duration first
C Latest starting activity
D Largest identifier first
Answer: A. Earliest finishing activity. Selecting the earliest finishing compatible activity leaves room for more choices.
Which knapsack variant suits value weight ratio greedy choice?
A 0/1 knapsack
B Bounded graph coloring
C Fractional knapsack
D Subset sum always
Answer: C. Fractional knapsack. Fractional knapsack permits taking portions, making ratio based greedy selection optimal.
Why does ratio greedy fail in general for 0/1 knapsack?
A Items cannot be split
B Weights are always equal
C Values must be negative
D Capacity is unbounded
Answer: A. Items cannot be split. Whole item choices can make the best local ratio produce a suboptimal combination.
What does backtracking do after a choice fails?
A Keep every failed choice
B Sort the input again
C Hash the full search tree
D Undo choice and try another
Answer: D. Undo choice and try another. Backtracking reverses a partial choice when it cannot lead to a valid solution.
What is pruning in search?
A Add more candidate branches
B Sort all partial answers
C Store every input copy
D Skip branches unable to help
Answer: D. Skip branches unable to help. Pruning avoids exploring parts of the search space that cannot contain a solution.
What is exhaustive search?
A Use only a local choice
B Stop after first input
C Cache one subproblem
D Try every candidate solution
Answer: D. Try every candidate solution. Exhaustive search enumerates all candidates, often at high cost.
What is a randomized algorithm?
A Always produces random output
B Has no correctness guarantee
C Uses random choices during execution
D Runs only on random input
Answer: C. Uses random choices during execution. Randomized algorithms use random bits to guide some decisions.
What distinguishes a Las Vegas algorithm?
A Approximate result, fixed runtime
B Correct result, random runtime
C Incorrect result, fixed memory
D Sorted result, random input
Answer: B. Correct result, random runtime. A Las Vegas algorithm returns a correct result while its running time may be random.
What distinguishes a Monte Carlo algorithm?
A Always correct with random runtime
B No random choices
C Bounded runtime, error probability
D Exact result in one step
Answer: C. Bounded runtime, error probability. Monte Carlo algorithms limit runtime but may return an incorrect answer with some probability.
What does amortized analysis average across?
A Random input values
B All possible algorithms
C A sequence of operations
D Every machine instruction globally
Answer: C. A sequence of operations. Amortized cost bounds average work over a chosen sequence, not an input probability distribution.
What is a heuristic?
A Proof of optimality always
B A sorted data structure
C Rule for a good solution
D A recurrence base case
Answer: C. Rule for a good solution. A heuristic guides search when a fast exact method may be impractical.
What is the main goal of branch and bound?
A Sort graph edges
B Build a balanced tree
C Hash each candidate
D Prune suboptimal search branches
Answer: D. Prune suboptimal search branches. Branch and bound uses bounds to discard branches that cannot beat the current solution.
Why can memoization reduce runtime?
A It sorts inputs automatically
B It avoids repeated computation
C It removes every recursive call
D It lowers all memory use
Answer: B. It avoids repeated computation. Memoization stores answers so repeated subproblems can be answered from a cache.