Time Left - 15:00 mins

GATE CS 2021 : Algorithm Rapid Quiz-1 (App update required to attempt this test)

Attempt now to get your rank among 513 students!

Question 1

Consider the following message:

Message = pppqqqqqrpqppqqrrrrssssspq

The number of bits required for huffman encoding of the above message are __________?

Question 2

Consider the data in the following table:

Capacity of knapsack, m = 10 and no. of objects, n = 3. Consider the situation that we can only take a object in the bag wholly or we can leave it , but we can't take it partially. Find the difference in maximum profit obtained from dynamic pogramming approach and greedy approach.

Question 3

Let the number of comparisons done in Quick Sort be x1 and number of swaps done are yCompute the value of x1-2y1 for the following set of data.

56, 89, 23, 67, 12, 45, 6, 8, 92

Note: In Quick Sort, the pivot element chosen will be the last element of the set.

Question 4

Which of the following statements about Huffman Coding is true:
X. In Huffman Coding the length of the code for the largest and the second largest occurring character can never be the same.
Y. The most occurring character will always be the child of root node.
Z. The second smallest element will be farthest leaf from the root node.

Question 5

Consider the following matrices with given dimension:
A0 (4 × 6), A1 (6 × 8), A2 (8 × 4), A3 (4 × 5)
Which of the following multiplication order gives optimal solution of the above matrices.

Question 6

The worst case time complexity required for an efficient algorithm to compute the number of inversions in any permutation of n elements, stored in an array are:
  • 513 attempts
  • 3 upvotes
  • 2 comments
Dec 9GATE & PSU CS