Quiz MO412 - Giorgio

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

 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 paralleliz...