MathJax


[MO412] Question 2

Assume you only know two graph traversal algorithms: Depth-First Search (DFS) and Breadth-First Search (BFS). Given the following directed graphs, choose the alternative that correctly states, in order, which algorithm reaches NODE H first (least amount of movements). Every traversal must start from NODE A. Also, the list of nodes is ordered alphabetically.

a. BFS, BFS, DFS
b. BFS, BFS, DFS
c. DFS, DFS, BFS
d. DFS, DFS, DFS
e. None of the above.

Original idea by: Vitor Antônio Pimenta Silva

Comentários

  1. Joao Meidanis27 de agosto de 2024 às 07:16

    Nice question, but I'm afraid readers will have some doubts. For instance, what is a movement in a search? You ask for the least amount of movements. Perhaps a movement is a visit to a new node? Or revisiting an old nodes also counts? What happens when both BFS and DFS use the same amount of movements to reach H from A? I decided to discard it because of that.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

[MO412] Question 1

Imagem
Identify all backward edges forming cycles within the following directed graph: Assign the alternative that contains all backward edges: A. (a→d, e→c) B. (a→b, c→e) C. (d→a, e→c) D. (d→b, e→c) E. None of the above. Original idea by: Vitor Antônio Pimenta Silva
Leia mais

[MO412] Question 4

 Consider a particle moving in a one dimensional space. It's acceleration is proportional to the square of its velocity. Also, at t=0, it has a velocity v(t=0) = 2 [m/s] and at t=1, v(t=1) = 1 [m/s]. Consider that the particle starts at x=0. A first-order separable ordinary differential equation can be generalized as: dx dt = g ( t ) ⁢ h ( x ) . With that in mind, choose the alternative that correctly describes the particle's position in relation to time. In other words, x ( t ) ,   t ≥ 0 . A. x ( t ) = ln ( 1 + t ) 2 B. x ( t ) = 1 + ln ( 2 +
Leia mais