2023-206

 

Imagine a Cayley Tree, constructed starting from a central node, where each node has degree \(k\), except the nodes at distance P from the central node, that have degree one, as shown in the figure above. Considering that the number of nodes reachable in \( t \geq 1 \) steps from the central node is \( k(k-1)^{t-1} \), and the number of links is \( L = N-1 \), where \( N \) is the number of nodes, what is the probability of conexion between nodes for \(k=4\) and \(P=4\)?

1. 1/161
2. 2/161
3. 1/41
4. 2/41
5. None of above

Original idea by: Germán Darío Buitrago Salazar

2023-205

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 \( (i,j) \) may be created with probability \( 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 for 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.

1. \( p = \frac{1}{N} \), because it is the critical point.
2. \( p = \frac{\ln N}{N} \), because it is the boundary between the supercritical and the connected regime.
3. \( p = \frac{\ln N}{\ln \langle k \rangle} \), because it is the boundary between the supercritical and the connected regime.
4. \( p = \frac{\langle k \rangle}{N} \), because it is the critical point.
5. None of the above

Original idea by: Christian Konishi

2023-204

Considering the Gilbert model , which statements from the following list are correct?

1. The expected number of links in a network generated with this model is \( \frac{pN(N-1)}{2} \)
2. If \( p > \frac{\ln N}{N} \) this model always generates a fully connected network with 100% certainty
3. This model produces a degree distribution that follows a Poisson distribution, which can be approximated by binomial distribution when \( N \) is much larger than \( k \)
4. A complete network can be generated from this model when \( p > 0 \), even if this is not likely

1. I and III
2. II, III and IV
3. I, II and IV
4. I and IV
5. None of above

Original idea by: Anderson Nogueira Cotrim

2023-203

Given the following adjacency matrix that represents a directed graph (a '1' in row \(x\) and column \(y\) means a directed link \(x \rightarrow y\)), apply a topological sort using Depth First Search (DFS) and determine the start and finish times for each node. Start from node 'a' and always prioritize visiting nodes in alphabetical order.

	\(a\)	\(b\)	\(c\)	\(d\)	\(e\)	\(f\)	\(g\)
\(a\)	0	1	0	0	0	0	0
\(b\)	0	0	1	0	1	0	0
\(c\)	0	0	0	1	0	0	0
\(d\)	0	0	0	0	1	0	1
\(e\)	0	0	0	0	0	1	0
\(f\)	0	0	0	0	0	0	0
\(g\)	0	0	0	0	0	1	0

1. a(1,14); b(2,13); c(3,12); d(4,11); e(5,10); f(6,7); g(5,8)
2. a(1,14); b(2,13); c(3,12); d(4,11); e(5,7); f(6,9); g(8,10)
3. a(1,14); b(2,13); c(3,12); d(4,11); e(5,10); f(7,8); g(6,9)
4. a(1,14); b(2,13); c(3,12); d(4,11); e(5,8); f(6,7); g(9,10)
5. None of the above

Original idea by: Thaysa Bello