# Greedy Algorithms MCQ

1. Fractional knapsack problem is also known as __________

a) 0/1 knapsack problem

b) Continuous knapsack problem

c) Divisible knapsack problem

d) Non-continuous knapsack problem

Answer: b

The fractional knapsack problem is also called a continuous knapsack problem. The fractional knapsack is solved using dynamic programming.

2. Fractional knapsack problem is solved most efficiently by which of the following algorithm?

a) Divide and conquer

b) Dynamic programming

c) Greedy algorithm

d) Backtracking

Answer: c

A greedy algorithm is used to solve this problem. We first sort items according to their value/weight ratio and then add items with the highest ratio until we cannot add the next item as a whole. In the end, we add the next item as much as we can.

3. What is the objective of the knapsack problem?

a) To get maximum total value in the knapsack

b) To get the minimum total value in the knapsack

c) To get maximum weight in the knapsack

d) To get minimum weight in the knapsack

Answer: a

The objective of the knapsack problem is to fill the knapsack of some given volume with different materials such that the value of selected items is maximized.

4. Which of the following statement about the 0/1 knapsack and fractional knapsack problem is correct?

a) In 0/1 knapsack problem items are divisible and in fractional knapsack items are indivisible

b) Both are the same

c) 0/1 knapsack is solved using a greedy algorithm and fractional knapsack is solved using dynamic programming

d) In 0/1 knapsack problem items are indivisible and in fractional knapsack items are divisible

Answer: d

In the fractional knapsack problem, we can partially include an item into the knapsack whereas in the 0/1 knapsack we have to either include or exclude the item wholly.

5. Time complexity of fractional knapsack problem is ____________

a) O(n log n)

b) O(n)

c) O(n2)

d) O(nW)

Answer: a

As the main time taking a step is of sorting so it defines the time complexity of our code. So the time complexity will be O(n log n) if we use quick sort for sorting.

6. Fractional knapsack problem can be solved in time O(n).

a) True

b) False

Answer: a

It is possible to solve the Fractional knapsack problem in O(n) time by adapting the algorithm for finding weighted medians.

7. Given items as {value,weight} pairs {{40,20},{30,10},{20,5}}. The capacity of the knapsack = 20. Find the maximum value output assuming items to be divisible.

a) 60

b) 80

c) 100

d) 40

Answer: a

The value/weight ratio are-{2,3,4}. So we include the second and third items wholly into the knapsack. This leaves only 5 units of volume for the first item. So we include the first item partially.

Final value = 20+30+(40/4)=60.

8. The result of the fractional knapsack is greater than or equal to 0/1 knapsack.

a) True

b) False

Answer: a

As a fractional knapsack gives extra liberty to include the object partially which is not possible with a 0/1 knapsack, thus we get better results with a fractional knapsack.

9. The main time taking step in fractional knapsack problem is ___________

a) Breaking items into a fraction

b) Adding items to the knapsack

c) Sorting

d) Looping through sorted items

Answer: c

The main time taking a step is to sort the items according to their value/weight ratio. It defines the time complexity of the code.

10. Given items as {value,weight} pairs {{60,20},{50,25},{20,5}}. The capacity of the knapsack = 40. Find the maximum value output assuming items to be divisible and nondivisible respectively.

a) 100, 80

b) 110, 70

c) 130, 110

d) 110, 80

Answer: d

Assuming items to be divisible-

The value/weight ratio are {3, 2, 4}.So we include the third and first items wholly. So, now only 15 units of volume are left for the second item. So we include it partially.

Final volume = 20+60+50x(15/25)=80+30=110

Assuming items to be indivisible- In this case, we will have to leave one item due to insufficient capacity.

Final volume = 60 + 20 = 80.

1. Which of the following algorithms is the best approach for solving Huffman codes?

a) exhaustive search

b) greedy algorithm

c) brute force algorithm

d) divide and conquer algorithm

Answer: b

A greedy algorithm is the best approach for solving the Huffman codes problem since it greedily searches for an optimal solution.

2. How many printable characters does the ASCII character set consist of?

a) 120

b) 128

c) 100

d) 98

Answer: c

Out of 128 characters in an ASCII set, roughly, only 100 characters are printable while the rest are non-printable.

3. Which bit is reserved as a parity bit in an ASCII set?

a) first

b) seventh

c) eighth

d) tenth

Answer: c

In an ASCII character set, seven bits are reserved for character representation while the eighth bit is a parity bit.

4. How many bits are needed for standard encoding if the size of the character set is X?

a) log X

b) X+1

c) 2X

d) X2

Answer: a

If the size of the character set is X, then [log X] bits are needed for representation in a standard encoding.

5. The code length depends on the frequency of occurrence of characters.

a) true

b) false

Answer: a

The code length depends on the frequency of occurrence of characters. The more frequent the character occurs, the less the length of the code.

6. In Huffman coding, does data in a tree always occur?

a) roots

b) leaves

c) left subtrees

d) right sub trees

Answer: b

In Huffman encoding, data is always stored in the leaves of a tree in order to compute the codeword effectively.

7. From the following given tree, what is the code word for the character ‘a’?

a) 011

b) 010

c) 100

d) 101

Answer: a

By recording the path of the node from root to leaf, the code word for the character ‘a’ is found to be 011.

8. From the following given tree, what is the computed codeword for ‘c’?

a) 111

b) 101

c) 110

d) 011

Answer: c

By recording the path of the node from root to leaf, assigning the left branch as 0 and the right branch as 1, the codeword for c is 110.

9. What will be the cost of the code if character ci is at depth di and occurs at frequency fi?

a) cifi

b) ∫cifi

c) ∑fidi

d) fidi

Answer: c

If character ci is at depth di and occurs at frequency fi, the cost of the codeword obtained is ∑fidi.

10. An optimal code will always be present in a full tree.

a) true

b) false

Answer: a

An optimal tree will always have the property that all nodes are either leaves or have two children. Otherwise, nodes with one child could move up a level.

11. The type of encoding where no character code is the prefix of another character code is called?

a) optimal encoding

b) prefix encoding

c) frequency encoding

d) trie encoding

Answer: b

Even if the character codes are of different lengths, the encoding where no character code is the prefix of another character code is called prefix encoding.

12. What is the running time of the Huffman encoding algorithm?

a) O(C)

b) O(log C)

c) O(C log C)

d) O( N log C)

Answer: c

If we maintain the trees in a priority queue, ordered by weight, then the running time is given by O(C log C).

13. What is the running time of the Huffman algorithm, if its implementation of the priority queue is done using linked lists?

a) O(C)

b) O(log C)

c) O(C log C)

d) O(C^{2})

Answer: d

If the implementation of the priority queue is done using linked lists, the running time of the Huffman algorithm is O(C^{2}).