ISRO CS 2019 : Algo Booster Quiz 4 for GATE & PSU CS Exams

Question 1

We are provided with a 2 x n array of integers. What is the time complexity to calculate the rectangular 1x2 or 2 x1 array whose sum of elements is maximum?
Example:

Here ans is 12

Question 2

Consider an array A in which upto some index I , integers are stored which is sorted and after that NULL values are stored. Let the size of array be n, then the time taken to find the value of I is :

Question 3

Consider the following statements regarding Dijkstra's shortest path algorithm :
S1 : Dijkstra's Algorithm can be implemented on both directed and undirected graphs.
S2 : Dijkstra Algorithm provides shortest distance from every node to every other node.
S3 : Dijkstra Algorithm just provide the shortest distance , it doesn’t provide the path information.
Which of the above statements are correct ?

Question 4

Which of the following statement is false?

Question 5

Consider the following recurrence relation :

If the input n is of the form 2^k, then what is the value of above recurrence relation.

Question 6

Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial time algorithm to solve A.

Question 7

You are given a directed graph and the shortest path between source s and destnation t. If in one case weight of every edges are increased by 10 units and in other case weight of every edges are multiplied by 10 units then which of the following statements are true in the two different cases,

Question 8

Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected graph. The tree T formed by the tree arcs is a data structure for computing

Question 9

Consider the hashing table with ‘m’ slots and ‘n’ keys. If the expected number of probes in unsuccessful search is 3 then find the expected number of probes in a successful search.

Question 10

A stable sort preserves the order of values that are equal with respect to the comparison function. We have a list of three dimensional points
[(7, 1, 8),(3, 5, 7),(6, 1, 4),(6, 5, 9),(0, 2, 5),(9, 0, 9)].
We sort these in ascending order by the second coordinate. Which of the following corresponds to a stable sort of this input ?