Time Left - 15:00 mins

Algorithms Rapid Quiz - 1 (App update required to attempt this test)

Attempt now to get your rank among 698 students!

Question 1

Conisder a sorted array with 100 elements. To find a specific element in array , the worst case number of probes required _______.

Question 2

Consider the following functions:

Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

Question 3

Consider the following problems related to graph.

• Verifying given graph connected or not

• Finding number of connected components in a graph

• Checking given graph strongly connected or not.

• Checking given graph contain cycle or not

• Verifying a specific vertex in graph articulation point or not

• Single Source Shortest Path in given unweighted graph

• Verifying given graph bipartite or not.

Let 'X' denote the number of problems that can be solved using Breadth First traversal and let 'Y' denote the number of problems that can be solved using Depth First traversal. Then find the values of (X²-Y²) _____________.

Question 4

Consider the following keys that are hashed into the hash table in the order given using the hash function

mod 11.
12, 44, 13, 88, 23, 94, 11, 39, 20, 16, 5.
Assume hash table has locations from 0 to 10. If hash table uses chaining to handle the collisions, how many locations are left without hashing any element into it?

Question 5

Given a set of n numbers, we wish to find the 'I' largest in sorted order using a comparison‐based algorithm. So we build a max‐priority queue from the numbers, and call EXTRACT‐MAX i times. What will be the time complexity of this algorithm ?

Question 6

Molecular biology DNA sequences (genes) can be represented as sequences of four letters ACGT, corresponding to the four sub-molecules forming DNA. When biologists find a new sequences, they typically want to know what other sequences it is most similar to. One way of computing how similar two sequences are is to find the length of their longest common subsequence. If the value of LCS > n/2 then they are most probable to similar , if LCS < n/2 then it is not similar and if LCS = n/2 then it may or may not be similar where n is the length of DNA sample. So consider the following two samples of DNA and comment upon their similarity .
Sample 1 : TACCAGGT
Sample 2 : CATTGATT

698 attempts
1 upvote
3 comments

Tags :

GATE & PSU CS Algorithms

Jun 25GATE & PSU CS