Under which of the following conditions does the collision in a hash table happen? O a. The hash table is full and there is not more space b. When the input hashes to an empty hash table slot. c. On every insert in the hash table d. When the input hashes to an already occupied hash table slot In open addressing hashing, where do we store all the items? a. In secondary storage O b. In an in-memory database O c. In the hash table itself d. Attached to the hash table using linked lists Which of the following search performances does a hash table have, in the worst-case scenario? O a. 0(2) O b. O(n) O c. O(log n) O d. 0(1) While using linear probing, if a slot at index x is found to be occupied, which of the following slots will be checked next? a. 2x O b. (x + 1) mod table_size O c. (a + j(x+1)2) mod table_size O d. x + 1 Which of the following statements is false with regard to binary search trees? a. A node in a binary search tree has a maximum of two child nodes O b. The sum of keys on all the left child nodes will be less than the parent O c. Every node except the root in a binary tree has one parent O d. The minimum key is found by picking the left child node recursively How do we implement breadth-first search traversal of a tree? a. By using the stack data structure O b. Starting at the leaf nodes and working our way up O c. Recursively choosing the right child node O d. By using the queue data structure Which of the following search performances does an unbalanced binary tree have in the worst-case scenario? a. O(n) O b. 012") O c. O(log n) O d. 0(1) Which of the following search performances does a balanced binary tree have in the worst-case scenario? O a. O(n) O b. Odlog n) O c. 0(1) O d. 0(2") Which of the following sorting algorithms follows a greedy approach? O a. Insertion sort b. Selection sort O c. Merge sort d. None of the above Which of the following sorting algorithms follows a divide and conquer approach? O a. Insertion sort b. Selection sort c. Quicksort d. Bubble sort What is the asymptotic runtime bound of the following recurrence, using the master method? T(n) = 16T(n/4) + n! O a. O(n) Ob. O(n!) c. O(nlogn) 1 d. The master method is not applicable What is the asymptotic runtime bound of the following recurrence, using the master method? T(n) = 2*Tn/2) + n a. 012") O b. O(mm) O c.0(2") O d. The master method is not applicable Which all of the following is true for a problem to have the overlapping subproblems property? O a. A recursive algorithm for the problem solves the same subproblems again and again O O b. The problem can be solved using dynamic programming c. The problem can be broken down into problems that are reused several times O d. Subproblems can't be easily split, so we must have an extra step to combine them Assume that, in the knapsack problem, you can now break items so that you can take a fraction of the item's value and weight. Which algorithm design paradigm provides an efficient solution to this problem? a. Brute force b. Divide and conquer O O c. Dynamic programming d. Greedy Both dynamic programming and greedy algorithms produce the optimal solution for problems that exhibit the optimal substructure property O a. True O b. False