Recent questions tagged algorithms

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

Consider,f1(N): x = 0 for i = 0 to N - 1: x++ return xand,f2(N, R): x = 0 for i = 0 to N - 1: for j = 1; j <= R; j = j + j: x = x + f1(j) return xWhat is the order of gro...

Let $G$ be a directed graph with nonnegative edge weights.Run Dijkstra's algorithm from source $s$. After the algorithm terminates, use the $\text{prev}$ pointers to cons...

Consider the following statements.Let $M$ be an MST of a connected undirected graph with positive edge weights. If $7$ is added to every edge weight, $M$ is guaranteed to...

Consider the following directed weighted graph with source vertex $0$:Bellman-Ford performs one complete pass, relaxing edges in this exact order:$$0\rightarrow1,\quad 0\...

The following running times are observed for a program:$$\begin{array}{|c|c|}\hlineN & \text{Running time} \\\hline1000 & 0.1\text{ seconds} \\2000 & 0.3\text{ seconds} \...

A linear-probing hash table of length $10$ uses:$h(k) = k \bmod 10$After inserting eight keys into an initially empty table, the table is:$$\begin{array}{|c|c|c|c|c|c|c|c...

Let $G=(V,E)$ be a connected weighted undirected graph in which all edge weights are distinct.Let, $e=(u,v)$ be an edge of weight $w(e)$.Construct a graph $G'$ containing...

Let $P$ be the problem of sorting $n\geq1$ elements using only comparisons.Consider the class of all comparison-based algorithms that correctly solve $P$.What is the asym...

When hashing is used for table addressing, a collision-resolution method is generally required.Why?Collision handling is required only when the table is completely full. ...

Let $T_A(n)$ and $T_B(n)$ denote the worst-case running times of two algorithms $A$ and $B$ that solve the same problem.We say that $A$ is asymptotically more efficient t...

Suppose every edge weight of a graph is either:a positive integer, or exactly $-1$.Consider the statement:Dijkstra's algorithm will always compute the correct shortest-pa...

Consider the following code executed while processing vertex $v$:for each edge e in G.adj(v): w = e.to() if dist[w] dist[v] + e.weight(): dist[w] = dist[v] + e.weight() ...

Consider the statement:The minimum spanning tree of a connected weighted graph $G$ is unique if and only if all edge weights in $G$ are distinct.True False

Consider three recursive algorithms.Algorithm $\mathbf{1}$Divides a problem of size $N$ into two subproblems of size $N/2$ and performs constant additional work.$T_1(N)=2...

Let, $L=\langle r_1,r_2,\ldots,r_n\rangle$ be an arbitrary list of integers, not necessarily distinct.Which of the following statements is incorrect?There exists an optim...

Consider the following recursive function $\texttt{Pot}$, which computes $x^n$, where $x$ is real and $n$ is an integer.Pot(x, n): if x == 0: return 0 if n == 0: return 1...

True or False:In every dynamic-programming solution, the asymptotic space requirement must be at least as large as the total number of distinct subproblems.True False