Time Left - 20:00 mins

GATE CSE 2020 National Champion Quiz: Algorithms (App update required to attempt this test)

Attempt now to get your rank among 2307 students!

Question 1

Let G be a graph with 10 vertices, and d(v) be the degree of a vertex v. The following conditions are holds for graph G
(i) for each vertex v in G
(ii) Not every vertex degree is even
(iii) No two odd degree vertices are of the same degree.
How many vertices are having even degree in G?

Question 2

In Prim's algorithm , we use decrease key operation. What is the time complexity of this decrease key operation in case of Prim's Algorithm :

Question 3

Considering the fractional knapsack problem, suppose we have a knapsack of capacity M=20 and three items

with profit values (

) as (25, 24, 15) respectively and weight values (

) as (18, 15, 10) respectively. What is the maximum profit achievable?

Question 4

Let

and

be four matrices of dimensions

and

respectively. The minimum number of scalar multiplications required to find the product

using the basic matrix multiplication method is ____.

Question 5

Consider the Quicksort algorithm in which while partitioning the array we always choose the first element as pivot. By choosing pivot as first element, worst case of quick sort can occur which has a time complexity of O(n²). But if we choose pivot wisely then this worst case can be avoided. So we developed an algorithm which selects the median of an array in O(n²) time and then use that median to partition the array. Find the best case time complexity of this algorithm ?

Question 6

Match the pairs in the following:

Question 7

Consider the following graph

Which of the following is NOT a depth first search traversal of the above graph?

Question 8

What is the smallest integer m such that every simple connected graph with n vertices and n edges contains at least m different spanning tree?

Question 9

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is ___________.

Question 10

Consider an initially empty symbol table implemented using a hash table of size ‘B’ with hash function h(C) = C mod B. In worst case for any possible sequence of inputs where N > B, what is the order of growth of inserting N (key, value) pairs with distinct key into table, if separate chaining is used to resolve collisions?

Question 11

Consider the already built heap (Max-Heap).
24, 20, 20, 7, 8, 9, 19, 1, 2
After root deletion operation, which of the following Max Heaps are valid.
1. 20, 8, 20, 7, 2, 9, 19, 1
2. 20, 20, 19, 7, 8, 9, 2, 1
3. 20, 20, 9, 7, 8, 2, 19, 1
4. 20, 7, 20, 2, 8, 9, 19, 1

Question 12

The median of n elements can be found in O(n)time. Which one of the following is correct about the complexity of quick sort, in which median is selected as pivot?

2307 attempts
14 upvotes
22 comments

Tags :

GATE & PSU CS Algorithms

Jun 24GATE & PSU CS