Data Structures u0026 Algorithms: Dynamic Programming and Bit Manipulation Quiz

Challenge your knowledge of advanced dynamic programming techniques and bit manipulation strategies. This quiz covers topics such as memoization, tabulation, classical DP problems, greedy algorithms, and advanced bit operations.

1. Memoization in Dynamic Programming

   Given a recursive solution for Fibonacci numbers with memoization, which data structure is most suitable for storing intermediate results: array, binary tree, queue, stack, or hash table?

   1. Binary tree
   2. Stack
   3. Queue
   4. Hash table
   5. Array

2. Knapsack Problem Application

   In the 0/1 Knapsack Problem, what does the '1' represent in its name, given a list of items with individual weights and values?

   1. Only one copy of each item is allowed
   2. Only one item can be put in the knapsack
   3. Each item has value 1
   4. Knapsack has only one compartment
   5. Knapsack can hold only one weight unit

3. Longest Increasing Subsequence Complexity

   What is the best possible time complexity for solving the Longest Increasing Subsequence (LIS) problem on an array of length n, as in [10, 9, 2, 5, 3, 7, 101, 18]?

   1. O(n^3)
   2. O(log n)
   3. O(n log n)
   4. O(n^2)
   5. O(n^2 log n)

4. LCS Space Optimization

   When computing the Longest Common Subsequence (LCS) between two strings, which is the minimal space complexity achievable using dynamic programming?

   1. O(1)
   2. O(n/m)
   3. O(mn)
   4. O(min(m, n))
   5. O(m + n)

5. Coin Change Minimum Coins

   Given denominations [1, 3, 4] and amount 6, what is the minimum number of coins needed to make the amount using dynamic programming?

   1. 1
   2. 2
   3. 4
   4. 3
   5. 5

6. Activity Selection Algorithm

   In the activity selection problem, which strategy ensures you always select the largest possible set of compatible activities?

   1. Select activities randomly
   2. Select the activity with the earliest finish time
   3. Select the shortest activity
   4. Select the activity with the latest start time
   5. Select activities with the highest profit

7. Huffman Coding Tree Property

   Which property must be true for the binary tree constructed by Huffman coding on a set of characters and frequencies?

   1. Every edge has the same length
   2. It must be a balanced tree
   3. All leaves represent distinct characters
   4. All internal nodes are labeled with characters
   5. All paths from root to leaf are of equal length

8. XOR Subset Trick

   Given an array of n positive integers, what is the result of XORing all subset XORs (i.e., computing the XOR sum of the XORs of all 2^n subsets)?

   1. Minimum element
   2. Product of all elements
   3. 0
   4. Maximum element
   5. Sum of all elements

9. Bitmask DP State Encoding

   If you have n tasks, what does a bitmask integer state of value 23 represent in a bitmask dynamic programming context?

   1. Tasks 0, 2, 3 completed
   2. Tasks 1, 3, and 4 completed
   3. Tasks 1, 2, and 4 completed
   4. Tasks 4 and 5 completed
   5. Tasks 0, 1, 2, and 4 completed

10. Power of Two Check Using Bit Manipulation

    Which of the following expressions correctly checks if a positive integer x is a power of two?

    1. (x u0026 x) == 1
    2. (x u0026 (x - 1)) == 0
    3. (x | (x - 1)) == 0
    4. (x ^ (x - 1)) == 0
    5. (x + (x - 1)) == 0