Recent questions tagged algorithms

Let $G$ be a weighted directed acyclic graph with $m$ edges and $n$ vertices. Given $G$ and a source vertex $s$ in $G$, which one of the following options gives the worst...

Consider an array $A$ of integers of size $n$. The indices of $A$ run from $1$ to $n$. An algorithm is to be designed to check whether $A$ satisfies the condition given b...

Consider a table $T$, where the elements $T[i][j], 0 \leq i, j \leq n$, represent the cost of the optimal solutions of different subproblems of a problem that is being so...

Consider a binary search tree (BST) with $n$ leaf nodes $(n>0)$. Given any node $V$, the key present in the node is denoted as $\operatorname{Val}(V)$. All the keys prese...

Consider the following recurrence relations:For all $n>1$,\[\begin{array}{c}T_{1}(n)=4 T_{1}\left(\frac{n}{2}\right)+T_{2}(n) \\T_{2}(n)=5 T_{2}\left(\frac{n}{4}\right)+\...

Let $n$ be an odd number greater than $100$. Consider a binary minheap with $n$ elements stored in an array $P$ whose index starts from $1$.Which of the following indices...

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with $23$ no...

Let $P$ be the set of all integers from $1$ to $15$. Consider any order of insertion of the elements of $P$ into a binary search tree that creates a complete binary tree....

Let $G(V, E)$ be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path i...

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...

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph $G(V, E)$ as input, where $d[v]$ and $f[v]$ are the discovery time a...

Consider the recursive functions represented by the following code segment:int bar(int n) { if (n == 1) return 0; else return 1 + bar(n/2); } int foo(int n) { if (n == 1)...

The following sequence corresponds to the preorder traversal of a binary search tree $T$ :\[50,25,13,40,30,47,75,60,70,80,77\]The position of the element $60$ in the post...

Let $$A = [1, 2, 3, 5, 4]$$Let $N_1$ be the number of comparisons performed by Bubble Sort, and $N_2$ be the number of comparisons performed by Insertion SortWhich of th...

In Quick Sort, the first element is always chosen as the pivot.Which of the following recurrence relations correctly represent the expected running time?$T(n)=T(1)+T(n-1)...

A binary tree has the following traversals:Preorder traversal$: P, Q, S, E, R, F, G$ Inorder traversal$: S, Q, E, P, F, R, G$ Which of the following statement(s) is/are T...

Suppose the input directed graph $G(V,E)$ is a DAG. For an edge $(u,v)\in E$, which of the following will NEVER be correct in DFS discovery/finish times?$d[u] < d[v] < f[...

If there is no path from $\delta$ to a of length at most k , then $d_k(u)=\infty$Statement 1: For every $u \geq 0$ and $u \in V, d_{k+1}(u) \leq d_k(u)$.Statement 2: For ...

Consider the following:For all $n>1$$$\begin{aligned}& T_1(n)=4 T_1(n / 2)+T_2(n) \\\\& T_2(n)=5 T_2(n / 4)+\theta\left(\log _2 n\right)\end{aligned}$$Assume that for all...

Let $\mathrm{G}(\mathrm{V}, \mathrm{E})$ be a simple, undirected, edge-weighted graph with unique edge weights.Which of the following statements about MST (minimum spanni...

Let $G$ be a weighted directed acyclic graph (DAG) with $m$ vertices and $n$ edges. Given $G$ and a source vertex $S$, which of the following options gives the worst-case...