Recent questions tagged goclasses-da-dpp

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

Suppose we run DFS on an undirected graph, and we discover a vertex $v$ with:$\mathrm{pre}(v)=1$ and $\mathrm{post}(v)=2|V|$Then the graph must be connected.True False

Suppose a directed graph has a path from vertex $\text{X}$ to vertex $\text{Y}$, but no path from vertex $\text{Y}$ to vertex $\text{X}$.The relationship between the fini...

Suppose vertices $A,B,C,D,E,F,G$ are stored in alphabetical order in the graph shown below. What is DFS order of traversing this graph starting from vertex $G$?$G,A,B,C,D...

Find a DFS traversal for the following directed graph:$10 \rightarrow 6 \rightarrow 2 \rightarrow 3 \rightarrow 7 \rightarrow 5 \rightarrow 1 \rightarrow 0 \rightarrow 4 ...

Suppose BFS is run on a cycle graph $C_n$. For which values of $n$ will no coloring conflict occur?All $n$ Odd $n$ Even $n$ Only prime $n$