DAA Lab Quiz

What is the Complexity of BUILD_MAX_HEAP function?

• O(log n)

• O(n log n)

• O(n)

• None of the above

What is the length of LCS for the following strings?

a. AABACDACC

b. CABBACCBC

• 4

• 5

• 6

• 7

For Matrix Chain Multiplication what are the missing sizes of matrix in the chain?

4x3, 3x6, 6x?, 5x8, ?x2

• 5 and 8

• 6 and 8

• 5 and 2

• 6 and 2

Which of the following is a Divide and Conquer algorithm?

• Bubble Sort

• Heap Sort

• Merge Sort

• Counting Sort

Heap_Increase_key operation is used for

• Increase the depth of the heap

• to insert a new node in the heap with given key.

• to increase the value of the given index with the new key value

• to remove the max value from the heap

What is the lower bound for comparison based sorting algorithms?

• nlogn

• n²

• logn

• n

What is true about Hoffman Tree?

• Hoffman Tree has n Leaf Nodes and n-1 intermediate nodes

• No of bits required to encode a character is its depth + 1

• Hoffman Code is a lossy compression algorithm

• None of the above is true

What is the order of partition algorithm in quick sort?

• O(logn)

• O(nlogn)

• O(n)

• O(1)

In Activity Selection problem, The List is sorted

• with respect to finish time in descending order

• with respect to start time in descending order

• with respect to finish time in ascending order

• with respect to start time in ascending order

Order the complexity function in ascending order of their complexity

a. n

b. log n

c. n²

d. n logn

• a, b, c, d

• c, d, a, b

• b, a, d, c

• d, c, b, a