Time Left - 12:00 mins

BARC CS 2018 Mini Nuclear Quiz - 1

Attempt now to get your rank among 524 students!

Question 1

A student want to prove a relation between the “gradeup” and “gaterank”. If he prove that gradeup is reducible to “gaterank” and “gaterank” is decidable then which of the following is true? (Assume gradeup & gaterank are two problems)

Question 2

Four matrices A1, A2, A3 and A4 are of the dimension v * w, w * x, x * y and y * z respectively. Now, these matrices can be multiplied in different ways to get total scalar multiplication. For example: In the following case ((A1 * A2) * (A3 * A4)), total number of multiplication is vwx + xyz + vxz. If v=40, w=20, x=30, y=10 and z=30, then minimum number of scalar multiplications are:

Question 3

if T(n) = T(n - 1) + n Then T(n) is equals to

Question 4

Suppose that each row of an n× n array A consists of 1’s and 0’s such that, in any row i of A, all the1’s come before any 0’s in that row. Suppose further that the number of 1’s in row (i+1) is at least the number in row i, for i = 0, 1,. . . , n – 2. Assuming A is already in memory, what is the running time to count the number of 1’s in the array?

Question 5

If the following degree vertex, (5, 3, 2, 4, 3) can't form a simple graph then which of the following degree vertex should be added to make it form a simple graph?

Question 6

An undirected graph consists of 50 vertices and 150 edges. Weight of the MST of this graph is 300. Each weight of each edges of this graph is incremented by 5, now what is the updated weight of the MST?

Question 7

Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?

Question 8

Consider a hash table with 9 slots. The hash function is ℎ(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17 and 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

Question 9

Assume that a merge sort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?

Question 10

Consider the following bubble sort function.

bubblesort (A)
{
for i ← 1 to length [A]
do for j ← length [A] down to i + 1
do if (X) then exchange A[j]

A[j – 1]
}
What is the missing statement at X, if the bubble sort function implemented correctly to sort the
elements in the increasing order?

524 attempts
1 upvote
5 comments

Tags :

GATE & PSU CS Algorithms

Apr 6GATE & PSU CS