2024-245

The Kosaraju-Sharir's algorithm is designed to find all Strongly Connected Components (SCCs) in a directed graph. Which of the following alternatives correctly describes the main phases of the algorithm?

 

A - Perform a DFS on the graph to compute the finishing times of each vertex. Then, reverse the graph and perform another DFS based on decreasing finishing times.

B - Perform a BFS (Breadth-First Search) on the graph, followed by sorting the nodes based on their distances from the start vertex. Then, reverse the graph and repeat the BFS.

C - Reverse the graph, perform a DFS, and then compute a topological sort of the graph to find SCCs.

D - Use Dijkstra's algorithm to find the shortest path to each vertex, then reverse the graph and repeat the process.

E - None of the above

Original idea by: Vanessa Oliveira Alves

2024-244

The goal of Kosaraju-Sharir's algorithm is to find all strongly connected components (SCCs) of a given input graph. Please take into consideration the directed graph provided below and select the appropriate alternative about the decomposition of the graph into SCCs using this algorithm.

A. Starting from A and using alphabetical order to apply the first DFS, node G has minimum (equal to 4) finishing time. 

B. Starting from A and using alphabetical order to apply the first DFS, node A has maximum (equal to 10) finishing time.

C. Each node of the graph is a strongly connected component.

D. {A, B, C, G, F}, {D}, and{E} are strongly connected components of the graph.

E. None of the above.

Original idea by: Karla Florentino

2024-243

In the evolving network model that includes the concept of fitness, how does a node's fitness influence its ability to gain new connections?

a) Fitness gives all nodes an equal chance to receive new connections, eliminating the advantage of high-degree nodes.

b) Nodes with higher fitness are more likely to receive new connections, even if they currently have a low number of links.

c) Fitness reduces the effect of preferential attachment, favoring nodes with fewer connections.

d) Fitnes only affects the removal of existing links, not the formation of new ones.

e) None of the above.

Original Idea by Sergio Sanchez

2024-242

In the Evolving Networks chapter of Barabasi's book, Network Science, many models for network evolution are presented. For most of these models, which of the following concepts is the starting point to derive degree probability distributions and other characteristics of the networks?

A) Clustering coefficient

B) Preferential attachment

C) Network robustness

D) Shortest path length

E) None of the above


Original idea by: João Augusto Ferreira de Moura

2024-241

Consider a particle moving in a one dimensional space. Its acceleration is proportional to the square of its velocity. Also, at \( t=0 \), it has a velocity 2 m/s and at \( t=1 \), it runs at 1 m/s. Consider that the particle starts at \( x=0 \) m.

With that in mind, choose the alternative that correctly describes the particle's position, \( x(t) \), with respect to time.

1. \( x(t) = (\ln(1 + t))/2 \)
2. \( x(t) = 1 + \ln(2 + t^2) \)
3. \( x(t) = 2 + \ln(1 + t^2) \)
4. \( x(t) = 2 \ln( 1 + t ) \)
5. None of the above.

Original idea by: Vitor Antônio Pimenta Silva

2024-240

In search for fortune, a prospector named Jack had heard tales of a legendary gold mine hidden deep in the mountains. Inspired by stories of riches, he set out to explore three promising locations: Point A, Point B, and Point C. 

Using his metal detector, he discovered at point A, a signal modeled by the function \(f(t) = 3 \sin(2t) + 5t\) ; at Point B, \(g(t) = 2 \sin(3t) + 4t\) ; and at Point C, the function was \(h(t) = 4 \sin(t) + 2t\).

Jack knew that the greater the difference between the maximum value of the derivative of the signal and a threshold of 8, the more likely he was to stumble upon gold. Select the correct alternative.

a) He is more likely to find gold at Point A.

b) He is more likely to find gold at Point B.

c) He is more likely to find gold at Point C.

d) He is equally likely to find gold at Points A, B, and C.

e) None of the above.

Original idea by: João Vitor Baptista Moreira

2024-239

In a scale-free network with 1296 nodes, the maximum degree is 144, and the degree exponent is \( \gamma = 3 \). What is the minimum degree in the network?

A) 10

B) 12

C) 8

D) 3

E) None of the above.

Original idea by: Caroline Nakazato.