Question 91
What is the main property of a prefix-free code?
A prefix-free code ensures that once a codeword is read, it cannot be the beginning of a different codeword. This enables unambiguous decoding without separators.
What is the main property of a prefix-free code?
A prefix-free code ensures that once a codeword is read, it cannot be the beginning of a different codeword. This enables unambiguous decoding without separators.
Which dynamic programming problem asks for the minimum number of scalar multiplications needed to multiply a chain of matrices?
Matrix-chain multiplication chooses parenthesization to minimize scalar multiplication cost. The matrix order is unchanged, but different parenthesizations have different costs.
What is the time complexity of the standard dynamic programming solution for LCS of strings of lengths m and n?
The DP table has (m+1)(n+1) states, and each state is computed in constant time from neighboring states, yielding O(mn) time.
Which problem is optimally solved by a greedy strategy based on value-to-weight ratio when fractions of items are allowed?
Sorting by value-to-weight ratio and taking as much as possible of the highest-ratio item first is optimal when items can be divided.
Why does the usual greedy ratio strategy not always solve 0/1 Knapsack optimally?
In 0/1 knapsack each item must be taken whole or not at all. Choosing the highest ratio item can leave unusable capacity and prevent a better combination of other items.