Recent questions and answers in Algorithms

Let $G(V, E)$ be a simple, undirected, edge-weighted graph with unique edge weights.Which of the following statements about the minimum spanning trees (MST) of $G$ is/are...

There are $n$ unsorted arrays: $A_1, A_2, \dots, A_n$. Assume that $n$ is odd.Each of $A_1, A_2, \dots, A_n$ contains $n$ distinct elements. There are no common elements ...

The following diagram shows the set of edges (in thick black lines) selected at some intermediate step of an MST algorithm. Lighter edges are not yet in MST. Assume that ...

Given an undirected, weighted graph $\mathrm{G}$ with positive, integer edge weights, we want to find a path shortest path from $u$ to $v$ with the below condition.The co...

​​​​​An array $[82,101,90,11,111,75,33,131,44,93]$ is heapified. Which one of the following options represents the first three elements in the heapified array?$82,90,101$...

Which of the following statements is/are FALSE?If all edge weights of $\mathrm{G}=(\mathrm{V}, \mathrm{E})$ are distinct, the MST of a graph G is unique. Removing the max...

Consider a source which outputs independent random letters from the alphabet $A=$ $\{a, b, c, d, e\}$ with probabilities $p_{a}=1 / 4, p_{b}=1 / 4, p_{c}=1 / 6, p_{d}=1 /...

Find total number of scalar multiplications of a matrix-chain product of $6$ matrices whose sequence of dimensions is $5, 10, 3, 12, 5, 50$ and $6.$ That is $5\times 10$ ...

You have given an array A[] = {12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}. An inversion in an array A is a pair of array indices (i, j) such that i < j and A[i] A[j]. Assume...

Select the correct asymptotic complexity of an algorithm with runtime $T(n, n)$ where$T(x, c)=\Theta(x) \quad$ for $c \leq 2$,$T(c, y)=\Theta(y) \quad$ for $c \leq 2$, an...

Consider mutually recursive definitions of $T(a, b)$ and $S(c, d)$ :$$\begin{array}{rlr}T(x, c) & =\Theta(x) & \text { for } c \leq 2 \\T(x, y) & =\Theta(x)+S(x, y / 2), ...

Let $X=x_{1} x_{2} \cdots x_{m}$ and $Y=y_{1} y_{2} \cdots y_{n}$ be two strings over the alphabet $\displaystyle{}\Sigma= \{\mathrm{A}, \mathrm{C}, \mathrm{G}, \mathrm{T...

You are working on a dynamic programming problem defined by the recurrence:\[ A(i, j) = F\!\big( A(\lfloor i/2 \rfloor,\, j),\; A(i,\, \lfloor j/2 \rfloor) \big), \]where...

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

Let $G$ be a directed graph with nonnegative edge weights, and let $s$ and $t$ be vertices of $G$.Consider the statement:Any shortest path from $s$ to $t$ in $G$ is also ...

During sorting, one complete processing of all elements whose final positions have not yet been determined is called a pass.Which of the following sequences cannot be the...

An initially empty hash table $\text{HT}$ has length $11$.The hash function is:$H(key)=key \bmod 7$Collisions are resolved using linear probing.The following keys are ins...

The algorithm $\text{ALGSORT}$ sorts an array of distinct integers using comparisons.The function $\text{MININDEX(V,i,j)}$ returns the position of the smallest element in...

Consider the following statement:For every connected weighted graph $G$, there exists some vertex $v$ such that a shortest path tree rooted at $v$ is identical to a minim...

Consider a simple version of Bellman-Ford algorithm where we initialize $\text{distTo}[s]$ to $0$ and the rest of $\text{distTo}[v]$ to $+\infty$. Then fix an order on al...

Consider Dijkstra's algorithm on a graph having $V$ vertices and $E$ edges.Suppose an indexed priority queue is not used.Instead, the tentative distances are stored only ...

Consider a directed edge $e = v \to w$ with weight $7$. Suppose that during a shortest path algorithm:$\operatorname{distTo}[v] = 16$ and $\operatorname{distTo}[w] = 25$...

Suppose Huffman coding is implemented as follows.Initially, the $n$ symbols are stored in a min priority queue according to their frequencies.The algorithm repeatedly per...

Let, $G=(V,E)$ be a connected undirected graph. Edge weights may be negative.We want to choose, $E'\subseteq E$ such that $G'=(V,E')$ is connected and: $\sum_{e\in E'}w(e...

Let $G=(V,E)$ be a directed graph with positive edge weights.Given vertices $s,w,t$ we want the length of the shortest path from $s$ to $t$ that must pass through $w$.Con...

What is the primary reason to use Floyd's algorithm for the all-pairs shortest-path problem instead of Dijkstra's algorithm?Faster for dense graphs. Faster for sparse gra...

Which of the following cannot be a sequence of keys compared during a binary search for some target key?$500,200,450,180$ $500,450,200,180$ $180,500,200,450$ $180,200,500...