2022-096

Consider the following statements about this graph:

1. Starting at node A, a DFS visiting order could be: A, B, E, F, C, D, G and a BFS visiting order could be: A, B, C, D, E, F, G
2. Starting at node A, a BFS visiting order could be: A, B, E, F, C, D, G and a DFS visiting order could be: A, B, C, D, E, F, G
3. There is at least one back edge on the graph, and the back edges are always the same, no matter what the DFS starting point is

Now select the alternative that lists only the true statements:

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

Original idea by: Victória Pedrazzoli

2022-095

In the network below, a discovery procedure uses the BFS algorithm to find devices.

Which alternative represents a possible order of visiting the devices (nodes):

1. FBCDEA
2. EFBACD
3. DCEBFA
4. BEFDCA
5. None of the above

Original Idea by Iury Cleveston

2022-094

A cell has an initial amount of \( l_0 \) liters of water inside it. After one hour has passed, the amount of water is \( 3 l_0 / 4 \). If the rate of water usage for the cell’s physiological functions is inversely proportional to the amount of water in the cell, find an equation that allows you to calculate the amount \( L(t) \) of water in the cell at any point \( t \) in time.

Note: Always consider positive values. Consider time measured in hours, and volume in liters.

1. \( L(t) = l_0 \sqrt{16 - 7t} / 4 \)
2. \( L(t) = l_0 (4 - t) / 4 \)
3. \( L(t) = l_0 \sqrt{-7t^2/16 + 1} / 4 \)
4. \( L(t) = l_0 (t^2 + 16) / 16 \)
5. None of the above

Original Idea by Rómulo Condori

2022-093

Consider that the following DAG (Directed Acyclic Graph) represents tasks and requirements between tasks.

Evaluate the following statements:

1. There are a total of 12 strongly connected components;
2. There are a total of 4 valid topological sorting possibilities;
3. Starting a DFS on node 2 might result in having two cross edges;
4. The DAG indicates that to perform task 10, you must perform task 7 before tasks 8 and 9.

Select the best answer:

1. 1 - True, 2 - False, 3 - True, 4 - False
2. 1 - False, 2 - True, 3 - True, 4 - False
3. 1 - True, 2 - False, 3 - True, 4 - True
4. 1 - False, 2 - False, 3 - False, 4 - False
5. None of the above 

Original idea by André Portela

2022-092

Read the statements about clustering coefficient below:

1. Local clustering coefficient measures the connectivity of a node to the rest of the network.
2. The fact that local clustering coefficients of small nodes are higher than those of hubs indicates that hubs tend to have more sparse neighborhoods.
3. For a scenario where information must be spread, a small Average Clustering Coefficient is indicative of a problem.
4. Global Cluster Coefficient can be thought of as a metric that checks the extent to which pairs of nodes with a common neighbor are also neighbors.

Which option below presents the correct statements?

1. 1 and 4
   
2. 1, 3, and 4
   
3. 2, 3, and 4
   
4. 2 and 4
   
5. None of the above
   

Original idea by: Filipe Maciel

2022-091

Topological Sorting

Analyze the graph below.

Consider the following statements.

1. There are four possible topological orderings
   
2. One valid topological ordering is ACBDEF
   
3. Topological sorting is only possible in a directed cyclic graph

Choose the best answer.

1. I - TRUE, II - TRUE, III - TRUE
2. I - TRUE, II - TRUE, III - FALSE
3. I - TRUE, II - FALSE, III - TRUE
4. I - FALSE, II - TRUE, III - FALSE
5. 
   
6. None of the above

Original idea by: Márcia Jacobina

2022-090

What is the value of the following definite integral?

$$ \int_0^{10} e^x - 1 dx $$

1. \( x e^{x - 1} \)
2. 10
3. \( e^{10} - 11 \)
4. \( 1/e^{10} \)
5. None of the above

Original idea by: Filipe Maciel

2022-089

Select the false statement regarding derivatives:

1. The derivative at a point of the function y=f(x) represents the instantaneous rate of change of y with respect to x at that point
2. If \( f'(x) = 0 \), the point \( x \) can be a local maximum point of the function \( f \)
3. If \( f'(x) = 0 \), the point \( x \) can be a local minimum point of the function \( f \)
4. Derivatives determine the area under the function graph in the cartesian plane
5. None of the above

Original idea by: Victória Pedrazzoli

2022-088

Consider that you work at a company that produces wooden boxes. A client requests a batch of 1000 boxes. However, he has some requirements:

• All boxes must have a height of 1 meter.
• All boxes must have a volume of 10000 liters.

Using the information above choose the best base dimensions a and b of the boxes to spend the least possible amount of money on wood (round to 3 decimal places):

1. a = 3.713m, b = 3.162m
2. a = 3.713m, b = 3.713m
3. a = 3.162m, b = 3.713m
4. a = 3.162m, b = 3.162m
5. None of the above

Original idea by: Felipe Crispim da Rocha Salvagnini

2022-087

Solve the differential equation below for \( y \):

$$ y' - 4 \frac{y}{x} = x $$

Considering \( A \) a constant, choose the alternative that corresponds to a general solution of this equation, if any:

1. \( y = - x^2/3 + A x^4 \)
2. \( y = A x^4 - x^2/2 \)
3. \( y = - x^2/3 - A x^4 \)
4. \( y = A x^4 + x^2/2 \)
5. None of the above

Original Idea by: André Portela

2022-086

Pink Dolphins Extinction Calculation

The pink dolphin is the largest freshwater dolphin in the world. It is found in northern South America, in the basins of the Amazon and Orinoco rivers. Even with the efforts of environmentalists and researchers, it is at risk of extinction.

The function below gives the number of pink dolphins after \( t \) years since the species began to be monitored.

After 5 years, if nothing is done, what is the instantaneous rate of change of pink dolphins (round to nearest integer)?

1. -209 pink dolphins per year
2. 209 pink dolphins per year
3. -674 pink dolphins per year
4. 674 pink dolphins per year
5. None of the above

Original idea by: Márcia Jacobina

2022-085

Consider the following differential equation:

\( x y(x) = (1 + x^2) y'(x) \)

Which alternative represents a family of possible solutions?

1. \( y(x) = c \sqrt{ e^x + 1} \)
2. \( y(x) = c e (x^2 + 1) \)
3. \( y(x) = c \sqrt{ x^2 + 1} \)
4. \( y(x) = c e (x - 1)\)
5. None of the above

Original Idea by Iury Cleveston

2022-084

On why real networks are not well modeled by random networks, check the statements below:

1. Random networks overestimate the size and frequency of high-degree nodes.
2. Real networks remain connected when \( \langle k \rangle \lt \ln N \), which is highly unlikely in the random network model.
3. The average path length of random networks is not a good approximation for the path lengths observed in real networks.
4. The clustering coefficients of nodes in real networks deviate significantly from those of random networks, for similar \( N \) and \( L \).

Which option lists exactly the correct statements:

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

Original idea by: Filipe Maciel

2022-083

A Cayley tree is a tree in which each non-leaf vertex has a constant degree \( k \), and there is a central vertex with distance \( P \) to all leaves. Here is a visual example of this type of graph, for \( k=3 \) and \( P=6 \):

Consider the following statements about Cayley trees:

1. A Cayley Tree is a connected graph with no cycles
2. Cayley Trees with \( k \ge 3 \) form an infinite graph family of networks with the small-word property
3. In the \( G(N, 0.3) \) model, the probability of a graph being a Cayley tree is zero for infinitely many values of \( N \)
4. The clustering coefficient of any node in a Cayley Tree is zero

Now select the alternative listing exactly the true statements:

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

Original idea by: Victória Pedrazzoli

2022-082

Considering that the evolution of a random network could be classified into four topologically distinct regimes, analyze the information below about a random network with N=1000 during different stages of its life.

• Stage I: p = 0.01
• Stage II: p = 0.0063
• Stage III: p = 0.001
• Stage IV: p = 0.0007
• Stage V: p = 0.007

Please, select the option that better represents the stage's topological regimes:

1. • Stage I: Connected
   • Stage II: Critical
   • Stage III: Supercritical
   • Stage IV: Critical
   • Stage V: Connected
2. • Stage I: Connected
   • Stage II: Connected
   • Stage III: Critical
   • Stage IV: Subcritical
   • Stage V: Connected
3. • Stage I: Connected
   • Stage II: Critical
   • Stage III: Subcritical
   • Stage IV: Subcritical
   • Stage V: Supercritical
4. • Stage I: Connected
   • Stage II: Supercritical
   • Stage III: Critical
   • Stage IV: Subcritical
   • Stage V: Connected
5. • None of the above.

Original idea by: Felipe Crispim da Rocha Salvagnini

2022-081

Although real networks are not random, it is possible to recognize in them some characteristics, such as topological regime, defined specifically for random networks. Taking this into account, consider the networks below and identify which ones are more likely to be real networks. Assume that each network has N nodes, L links, and average degree <k>.

1. All of them
2. Networks 1 and 2
3. Networks 2 and 3
4. Just Network 3
5. None of the above

Original idea by: Márcia Jacobina

2022-080

About Depth-First Search (DFS) and topological sorting, consider the following statements:

1. The visited node order for the following graph and adjacency lists, starting with s, is s a c e b d
   
2. While running a DFS on a directed graph, if from vertex u we visit a finished vertex v, then the edge (u, v) is a cross-edge
3. If a topological sort exists for the vertices in a directed graph, then a DFS on the graph will produce no back edges 
4. A DFS in a directed graph always produces the same number of tree edges 
5. Suppose we perform a DFS on a directed graph G. If we remove all the back edges found, the resulting graph is acyclic 

Which alternative lists all false statements and no true statement among I-V?

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

Original Idea by: Levy Chaves

2022-079

Consider the following statements concerning the execution of a DFS in an undirected graph.

I. There are no cross edges.

II. There are only tree edges.

III. There are no forward edges.

IV. There are no backward edges.

V. It is not possible to perform a DFS in an undirected graph

Select the alternative that lists all the correct statements and no false statement:

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

Original idea by: Heitor Mattosinho

2022-078

A safe order for tasks that depend on one another is known as a topological ordering. Consider the following directed graphs, where edges indicate task dependency.

I)

II)

III)

Please, select the option that shows which graphs admit a topological ordering.

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

Original idea by: Felipe Crispim da Rocha Salvagnini

2022-077

Consider the following graph, that lists the requirements for subjects in a Computer Science course. Which of the alternatives represent an acceptable topological ordering?

1. ProgI → ProgII → SO → ArqComp → CompAlg → EstDados → IA → ProbEst
2. ProbEst → IA → ProgI → ArqComp → SO → ProgII → CompAlg → EstDados
3. ArqComp → SO → ProgI → ProgII → CompAlg → EstDados → ProbEst → IA
4. ProgI → ArqComp → ProgII → SO → CompAlg → EstDados → ProbEst → IA
5. None of the above.

Original idea by: Diogo Souza

2022-076

Your classmate is having trouble identifying hubs of a network. You as a good colleague decided to help her. Which of the following alternatives contains the larger hub on the network below?

1. Node E
2. Nodes A, B and C
3. Node F
4. Node D
5. None of the above

Original idea by: Victória Pedrazzoli

2022-075

What are the partitions of this bipartite graph?

1. P1={a, c, f, h, i, k}    P2={b, d, e, g, j, l}
2. P1={a, d, f, g, i, l}    P2={b, c, e, h, j, k}
3. P1={a, d, f, h, j, k}    P2={b, c, e, g, i, l}
4. P1={a, d, e, h, i, l}    P2={f, g, b, c, j, k}
5. None of the above

Original idea by: Márcia Jacobina

2022-074

Pedro and Sofia are brothers, and they argue pretty often. Their mother is a lovely and calm person, but today she is stressed out because of her work and has decided to ground them for arguing so often. She left them an exercise to solve to get out of detention. Their mother drew a graph (image below) and asked her children if the following statements about the graph are true or false: 

1. The edge between nodes BD is a bridge
2. The shortest path between the nodes E and C is 3
3. The graph diameter is 6 
4. The graph is disconnected
5. By removing the edges BD and EA the resulting graph has two connected components

Your task is to help the kids find the true alternative in the following list. Consider that the graph is undirected.

1. Only I, II, V are correct
2. Only I, III, and IV are correct
3. Only III, and V are correct
4. Only II, III, and V are correct
5. None of the above

Original idea by: Levy Chaves

2022-073

While performing a routine check on a power grid network, an employee noticed that the adjacency matrix could be rearranged into a block diagonal form, as shown in the figure below.

It is correct to affirm that the network:

1. Forms a complete graph.
2. Contains a bridge connecting two components.
3. Consists of two disconnected components.
4. Is a bipartite network.
5. None of the above.

Original idea by: Heitor Mattosinho