Register

GO Classes CS Test Series | Algorithms | Subject Wise Test 3 | Question: 26

• retagged by
133 views
0 0 votes

Which of the following statements are TRUE?

  • S1: Run Bellman-Ford on a weighted graph $\mathrm{G}=(\mathrm{V}, \mathrm{E}, \mathrm{w})$ from a vertex $\mathrm{s} \in \mathrm{V}$. If there is a witness $\mathrm{v} \in \mathrm{V}$, i.e., $\delta_{|\mathrm{V}|}(\mathrm{s}, \mathrm{v})<\delta_{|\mathrm{V}|-1}(\mathrm{~s}, \mathrm{v})$, then v is on a negativeweight cycle of G .
     
  • S2: If there is an algorithm to solve $0-1$ Knapsack in polynomial time, then there is also an algorithm to solve Subset Sum in polynomial time.
  1. S1 is True and S2 is False 
     
  2. S1 is False and S2 is True
     
  3. Both S1 and S2 are True
     
  4. Both S1 and S2 are False

1 Answer

1 1 vote
$\textbf{\textcolor{green}{Answer :C}}$

$S1:-$${\textcolor{RED}{FALSE}}$

In Bellman‑Ford, an improvement in the ∣V∣-th iteration proves that a negative‑weight cycle is reachable from the source, but the vertex v whose distance improves need not lie on that cycle.

$S2:-$ ${\textcolor{gREEN}{TRUE}}$

Subset Sum is a special case of 0‑1 Knapsack: set each item’s weight and value equal to the given number, set capacity = target sum, and check if the maximum value equals the target.
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GO Classes CS Test S...Next → · GO Classes CS Test S...
← Previous in category · GO Classes CS Test S...Next in category → · GO Classes CS Test S...
Position:
Show:

Related questions

1 1 vote
1 1 answer
82
82 views
GO Classes asked Sep 5, 2025
82 views
GO Classes CS Test Series | Algorithms | Subject Wise Test 3 | Question: 11
Consider the code fragment written in C belowvoid fun(int n){ if (n == 0){ printf("0"); } if( n == 1){ printf("1"); } else{ fu...
2 2 votes
1 1 answer
189
189 views
GO Classes asked Sep 5, 2025
189 views
GO Classes CS Test Series | Algorithms | Subject Wise Test 3 | Question: 12
Let the minimum spanning tree (MST) of the graph shown below contain the edge weights x and y.What will be the possible range of x and y if all edge weights are non-negat...
2 2 votes
1 1 answer
127
127 views
GO Classes asked Sep 5, 2025
127 views
GO Classes CS Test Series | Algorithms | Subject Wise Test 3 | Question: 13
Let $\mathrm{C}(\mathrm{S}, \mathrm{i}, \mathrm{j})$ be the function that counts the number of subsequence w , string $S$ have and $i$, j are the pointers pointing to the...