May 5th question


Consider the following directed graph:

In order to apply the Kosaraju-Sharir algorithm, a DFS was performed and the following start and end times were computed:

What will be the first strongly connected component detected in this graph?

  1. {7}.
  2. {4, 5, 6}.
  3. {2, 3, 4}.
  4. {1, 2, 3}.
  5. None of the above

Original idea by: Christian Konishi

Comentários

Postar um comentário

Postagens mais visitadas deste blog

March 31th question

Suppose that we are trying to project a distributed system with random architecture. Every time a new computer \( i \) tries to ingress, for each existing machine \( j \) in the network, a connection \( \left( i, j \right) \) may be created with a probability of \( p \). For this architecture, it is desired that any computer must be reachable from any node, however a few exceptions are tolerable. Also, \( p \) cannot be too big, because of cost reasons. Which one of these options presents a reasonable choice for the value of \( p \)? Assume that \( N \) is the number of expected computers in the network, and it is large enough to apply the law of large numbers. \( p = \frac{1}{N} \), because it is the critical point. \( p = \frac{ln\ N}{N} \), because it is the boundary between the supercritical and the connected regime. \( p = \frac{ln\ N}{ln\ \langle k \rangle} \), because it is the boundary between the supercritical and the connected regime. \( p
Leia mais

April 21st question

Assume that a certain network can be approximated by a particular continuous model, and its number of nodes increases at a rate given by the function \( f(t) = e^{\frac{-t}{1000}+10} \). Given that at \( t=0 \), the number of nodes is 0, what is the approximate maximum number of nodes that this network can have? Tip: get an expression for the number of nodes \( N(t) \) and its limit when \( t \rightarrow \infty \). \( e^{\frac{-1}{3}+10} \). \( 1000\ e^{\frac{-1}{3}+10} \). \( 1000\ e^{10} \). \( e^{10} \). None of the above Original idea by: Christian Konishi
Leia mais

June 2nd question

Imagem
Consider the following network. The fuchsia nodes are all part of a weak community. Which option presents a modification that makes this community a strong one? Remove node 8 from the community. Add node 5 to the community. Add node 9 to the community. Remove node 6 from the community. None of the above Original idea by: Christian Konishi
Leia mais