Question 9 - The crazy Network

Pedro was really interested in last algorithms class. So he started thinking and creating crazy networks. He proposed this: 

• First, he restricted the BA model, so when adding a new node with \(m\) links, each link has to go to a different node (probabilities have to be calculated at each new link, excluding the nodes already linked to the new one). 
• Now he established that \(m\) should follow the t-Fibonacci sequence. Where for a given \(t\) we have \(tFib(t) = t * Fib(t)\). (\(Fib(t)\) is the standard Fibonacci sequence)
• Finally, for each node he adds, he deletes \(2^t\) nodes. 

Of course, at this rate, soon he could not add anymore node to the network preserving the constraints he impose. 

Pedro started the network with 9876 nodes. Can you help him find the time \(t\) where he will not be able to follow the crazy network constraints?

1. \(t = 10\)
2. \(t = 11\)
3. \(t = 12\)
4. \(t = 13\)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 8 - BA Model

On the Non-linear preferential attachment, our probability becomes \(Π(k) \sim k^\alpha\). For a starting network with 1 node, approximately how many nodes we have to add on the network for it to achieve \(k_{max} = 100\), considering the cases where \(\alpha\) is \(0.5\), \(1\) and \(1.5\) respectively?

1. \(22026\) nodes; \(10000\) nodes; \(100\) nodes respectively
2. \(1024\) nodes; \(1000\) nodes; \(100\) nodes respectively
3. \(22026\) nodes; \(10000\) nodes; \(200\) nodes respectively
4. \(1024\) nodes; \(1000\) nodes; \(200\) nodes respectively
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 7 - The Science Project

During a science project, Pedro created a system that is governed by the following equation:

$$f(x) = \frac{1}{32}x^{2}a\ -\frac{1}{2}xz +3$$

In this system, \(a\) and \(z\) are constants that are adjusted manually by him, while \(x\) is the primary variable he wants to change. During his experimental tests, he found that the system can be very unstable, only for a few values of \(x\) for different \(a\) and \(z\) the system becomes stable. Can you help him find an equation that given  \(a\) and \(z\) he can easily find the value of \(x\)?

1. \(x = \frac{16z}{2a}\)
2. \(x = \frac{16za}{2}\)
3. \(x = \frac{2az}{16}\)
4. \(x = \frac{16a}{2z}\)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 6 - Scale-free Property

  With respect to the Scale-Free Property, given the following statements:

1. One of the key differences between scale-free networks and random networks is that hubs are forbidden in the random networks, but are expected in scale-free networks.
2. In the Anomalous Regime, all nodes are close and connect in the same central hub. Thus the degree of the biggest hub increases linearly with the network size (N), so the average path length depends on N.
3. Most real networks are present in the ultra-small world (Scale-free Regime) because their first and second moments are finite.
4. In the Random Regime, the probability \(P_k\) decays sufficiently fast to make the hubs smaller and less numerous, so the scale-free networks in this regime are more closer to the random networks, being hard to distinguish one from another.

  Which alternative contains all the correct statements?

1. I and IV are true.
2. II and III are true.
3. II and IV are true.
4. I and III are true.
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 5 - Cayle Trees

Cayley trees are trees that have a central node, and all the nodes in the tree have degree \(k\). Each time we expand this tree, each leaf connects to another (k-1) node.

A Cayley tree is denoted by P (distance from the leaf to the central node) and k (the degree of any node). The tree in the picture is a P(3) and k(4) Cayley Tree. How many leaf nodes this tree has? For a Cayley Tree with P(\(\delta\)) and k(\(\lambda\)), how many leaf nodes it has?

1. Leaves in the given tree: \(36\) and leaves in the P(\(\delta\)) and k(\(\lambda\)) tree: \(\lambda(\lambda - 1)^{\delta}\)
2. Leaves in the given tree: \(36\) and leaves in the P(\(\delta\)) and k(\(\lambda\)) tree: \(\lambda(\lambda - 1)^{(\delta - 1)}\)
3. Leaves in the given tree: \(42\) and leaves in the P(\(\delta\)) and k(\(\lambda\)) tree: \(\lambda(\lambda)^{(\delta - 1)}\)
4. Leaves in the given tree: \(42\) and leaves in the P(\(\delta\)) and k(\(\lambda\)) tree: \(\lambda(\lambda - 1)^{(\delta - 1)}\)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 4 - Distances?

Given the directed and unweighted graph below, and supposing that we start in node 1:

Which of the following items gives the information about the Furthest Node and one of the Shortest Paths to the furthest Node?

1. Furthest Node: \(8\) and Shortest Path: \(1 \to 2 \to 4 \to 7 \to 8\)
2. Furthest Node: \(8\) and Shortest Path: \(1 \to 2 \to 6 \to 7 \to 8\)
3. Furthest Node: \(9\) and Shortest Path: \(1 \to 2 \to 6 \to 7 \to 9\)
4. Furthest Node: \(9\) and Shortest Path: \(1 \to 2 \to 4 \to 7 \to 8 \to 9\)
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso

Question 3 - More tasks to do!

Pedro has been given several tasks to do. But instead of a list with the order of the tasks, his supervisor gave him a graph where edges that go from node A to B mean that task B depends on task A. Unfortunately, Pedro does not know how to take this information from the graph, so he doesn't know which tasks to do first. The graph his supervisor gave was:

As a specialist in graphs, you were chosen to help Pedro with ordering the tasks he needs to do. His supervisor said to him to always prioritize the task with a lesser index when he is able to select between free tasks. Knowing the constraints, which order should Pedro follow?

1. 1, 2, 3, 4, 7, 6, 9, 10, 8, 5
2. 5, 8, 10, 9, 6, 7, 4, 3, 2, 1
3. 1, 5, 2, 6, 4, 8, 9, 7, 10, 3
4. 1, 2, 6, 3, 4, 7, 9, 10, 8, 5
5. None of the above.

  Original idea by: Pedro Henrique Di Francia Rosso