Recent questions tagged goclasses-da-dpp

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

True or False:The root of an optimal binary search tree must always contain the key having the highest search probability.True False

An instance of Subset Sum contains:$n$ positive integersa positive target value $m$What is the running time of the standard dynamic-programming solution?$\Theta(m+n)$ $\T...

There is an unlimited supply of three item types:$$\begin{array}{|c|cc|}\hline\text{Item} & \text{Size} & \text{Value} \\\hlineA & 1 & 2 \\B & 2 & 6 \\C & 3 & 9 \\\hline\...

The following function $\texttt{CalcEditDistance}$ computes the edit distance between two strings.For this problem:Inserting one character has cost $1$.Deleting one chara...

For an array, $a ,a ,\ldots,a[n]$ consider the proposed DP state:$LIS[i]=$ length of the longest increasing subsequence contained anywhere within $a[1\ldots i]$.Using onl...

A $15$ kg knapsack is given with the following items:$$\begin{array}{|c|cc|}\hline\text{Item} & \text{Weight} & \text{Value} \\\hlineA & 2 & 7 \\B & 3 & 10 \\C & 5 & 18 \...

Consider the sequences:$X=\{A,C,B,C,D,C\}$$Y=\{C,D,B,D,C,A\}$What is the length of their longest common subsequence?

Consider four matrices whose dimension array is:$p=[5,2,2,4,6]$Thus:$A_1:5\times2$$A_2:2\times2$$A_3:2\times4$$A_4:4\times6$Using optimal matrix-chain multiplication, wha...

Consider the following statements.Dynamic programming generally solves smaller subproblems, stores their solutions, and combines those stored results to solve progressive...

Let $G$ be an undirected graph and let $G^*$ be obtained by removing an edge $(u,v)$ from $G$.Suppose both $G$ and $G^*$ are connected.Let $T$ be a BFS tree of $G$ rooted...

Let $T$ be any tree which contains all the vertices of a connected undirected graph $G$.There is a way to break ties in DFS such that DFS outputs $T$.True False

Let $G$ be an undirected graph with $n$ vertices and $m$ edges.$\text{S1}:$ All its DFS forests, for traversals starting at different vertices, have the same number of tr...

Which of the following is NOT a possible depth-first search sequence of the given directed graph?$V_1,V_5,V_4,V_3,V_2$ $V_1,V_3,V_2,V_5,V_4$ $V_1,V_2,V_5,V_4,V_3$ $V_1,V_...

Let $G$ be a connected graph with $n$ vertices. Two searches are performed starting from vertex $v$:$l(x)$ denotes the order in which vertex $x$ is reached by BFS. $p(x)$...

Can the above graph be topologically sorted?Yes No

Suppose DFS is called on a DAG $G$, and the resulting DFS forest has a single tree. Then $G$ has exactly one source vertex.True False

Is the reverse postorder the only valid topological order for this graph?No Yes

Let $G=(V,E)$ be a dag, where each edge is annotated with some positive length. Let $s$ be a source vertex in $G$.Suppose we run Dijkstra's algorithm to compute the dista...

Which of the following is a valid topological ordering of the vertices in the given graph?$0 \rightarrow 6 \rightarrow 1 \rightarrow 7 \rightarrow 3 \rightarrow 5 \righta...

Suppose that during an execution of depth-first search in a digraph $G$, $\texttt{dfs(v)}$ is called as a recursive subcall after $\texttt{dfs(w)}$ is called, but before ...

Run DFS on a directed graph $G$ computing visit times $pre(v)$ and $post(v)$ for each vertex $v$.An edge $(u,v)$ is a back edge if and only if $pre(v)<pre(u)<post(u)<post...

If the DFS tree has no back edges, then there are no cycles in the graph.True False

Let $T$ be a depth-first search tree of a undirected graph. Let $(x,y)$ be an edge of $G$ that is not an edge of $T$, then one of $x$ or $y$ is an ancestor of the other.T...

In DFS, if $(u,v)$ is an edge which connects two node such that they do not have any ancestor and a descendant relationship between them, than the edge is calledTree edge...

Is the following statement true?A DFS of a directed graph always produces the same number of tree edges, i.e. independent of the order in which the vertices are considere...