Kosaraju-Sharir’s algorithm and SCC Question

 The Kosaraju-Sharir’s algorithm is usually used to find strongly connected components in a graph. Analyze which options below are valid tasks to use the algorithm, and mark the alternative with the correct options.

 I. Validate and sort a sequence of actions which depend on each other, to make sure that prerequisites of a task can be completed before the given task is performed.

II. Group classes of a given Object-Oriented solution to isolate packages, in a graph where each class is a node and classes with any interaction have an edge. 

III. Find the maximum number of processing steps of a given algorithm, in a graph where each algorithm step was considered as a node.

IV.  Identify deadlocks in the operating system process execution, in a graph where nodes are processes and edges are created between processes when one waits the other for resources.

V. Optimize code compilation, identifying and removing code parts that are unreachable or adding parallelization to parts which are independent of the rest of the program, in a control flow graph (a graph with all possible execution paths).

 

a) Even options (II, IV)

b) Odd options (I, III, V)

c) III and V

d) II, IV, V

e) None of the above 

 

 Original idea  by: Giorgio Rossa

Comentários

Postar um comentário

Postagens mais visitadas deste blog

Push-relabel algorithm

Imagem
The following image illustrates a partially executed flow graph and the Push-Relabel algorithm, with the respective residual graph displayed on the right. The algorithm followed a FIFO order of selecting nodes and then selected nodes by alphabetical order when they were simultaneously activated. Active nodes are the ones that have excess in the pre-flow.  Based on the process illustrated, mark the correct alternative of the next step in the algorithm: a) Relabeling of ' c ', transforming 'h' to 2, and returning the excess flow to ' b ' using Push. b) Relabeling of ' a ', transforming 'h' to 8, and returning the excess flow to ' S ' using Push. c) Relabeling of ' c ', transforming 'h' to 8, and returning the excess flow to ' S ' using Push. d) Relabeling of ' e ', transforming 'h' to 1, and pushing the excess flow to ' t '. e) None of the above     Original idea  by: Giorgio Rossa
Leia mais

Questão BFS/DFS

Imagem
  Analyze the statements below, knowing that DFS and BFS algorithms start in the node "a" and the adjacency list is sorted in alphabetical order.   I.  During a BFS execution, three nodes that are already visited are verified (thus not being visited again); II. There is one back edge in the graph; III. If we remove the edges  C D  and EF,  the resulting graph is a bipartite graph; IV. The DFS execution would restart twice in this graph, creating two different trees; The correct statements are:  a) I and III b) Only II c) II and III d) I, II and IV e) None of the above   Original idea  by: Giorgio Rossa     
Leia mais

TSP Question

Imagem
The graph below shows the weight of each link between nodes. Considering that links not shown have infinite weight, find the correct alternative.  a) Using the Closest Neighbor heuristic, starting from node 'a'  will result in the cycle a-c-d-f-e-b-a, with a total cost of 19. b) Using the Closest Neighbor heuristic, any starting node will result in a total cost of 16. c) Using the Cheapest Insertion heuristic, starting from the cycle a-b-c-a will result in a final cost of 16. d) Using the Closest Neighbor heuristic, starting from node  'a'  will result in the cycle a-b-e-c-d-f-a, with a total cost of 16. e) None of the above.    Original idea  by: Giorgio Rossa
Leia mais