GATE Computer Science Design and Analysis of Algorithms Previous Year Questions

Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d_1(u,v)$ and $d_2(u,v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G$, $T$, $u$ and $v$?

Consider the following recurrence relation:

$T(n)=2T(n-1)+n{2}^n$ for $n>0$, $T(0)=1$.

Which ONE of the following options is CORRECT?

The pseudocode of a function fun() is given below:

fun(int $A[0,\ldots,n-1]$) {  
    for i = 0 to n-2  
        for j = 0 to n-i-2  
            if ($A[j] > A[j+1]$)  
                then swap A[j] and A[j+1]   
}  

Let $A[0,\dots ,29]$ be an array storing 30 distinct integers in descending order. The number of swap operations that will be performed, if the function fun() is called with $A[0,\dots ,29]$ as argument, is ________. (Answer in integer)

Let $G(V,E)$ be an undirected and unweighted graph with 100 vertices. Let $d(u,v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u,v)$, where $u,v\in V$ such that $u\ne v$, be 30. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$?

The maximum value of x such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is ________ . (answer in integer)

Consider an unordered list of $N$ distinct integers.

What is the minimum number of element comparisons required to find an integer in the list that is NOT the largest in the list?

Which of the following statements regarding Breadth First Search (BFS) and Depth First Search (DFS) on an undirected simple graph G is/are TRUE?

Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant $\alpha$ is added to the weight of every edge.

Which ONE of the following statements is TRUE about the minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?

An array A of length n with distinct elements is said to be bitonic if there is an index $1\le i\le n$ such that $A[1\dots i]$ is sorted in the non-decreasing order and $A[i+1\dots n]$ is sorted in the non-increasing order.

Which ONE of the following represents the best possible asymptotic bound for the worst-case number of comparisons by an algorithm that searches for an element in a bitonic array $A$?

Consider the following algorithm someAlgo that takes an undirected graph $G$ as input.

someAlgo(G)

1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at maximum distance from v as given by the BFS.
2. Run BFS on G again with u as the starting vertex. Let z be the vertex at maximum distance from u as given by the BFS.
3. Output the distance between u and z in G.

The output of someAlgo(T) for the tree shown in the given figure is ________. (Answer in integer)