Question

A breakthrough 2009 Bender et al. paper presents an algorithm for continually performing this task that explicitly avoids tracking affected regions. Purdom’s algorithm for finding transitive closures achieves quadratic time by precomputing the result of this task. A method for determining rank ordering in a round-robin tournament that minimizes upsets relies on performing this task on the feedback arc set of the tournament. The reverse of a postorder depth-first search’s iteration order is a solution to this task. (*) Kahn’s algorithm for this task repeatedly finds a source node, removes (10[1])it from the graph, and appends it to a running list; source nodes must always exist since this task is only defined for directed acyclic graphs. Resolving a dependency graph into an ordered sequence is an instance (10[1])of this problem. For 10 points, name this problem of flattening a directed acyclic graph into a list. ■END■ (0[3])

ANSWER: topological sort [or topological ordering; accept toposort; prompt on sorting or ordering]
<Alistair Gray, Other Science - Computer Science>
= Average correct buzz position

Back to tossups

Buzzes

PlayerTeamOpponentBuzz PositionValue
Aseem KeyalThe Catastrophic Implosion of Packet SubBHSU8810
Rahul KeyalThe anti-STOON-dahl cabal (the tall Keyal et al.)Team Name Think Detail12510
Shahar SchwartzSaint Peter Andre 3000Romanos IV Diogenes’ Macaroni Grill1440
Raul PassementRomanos IV Diogenes’ Macaroni GrillSaint Peter Andre 30001440
Stephen LiuCurse you, Periplus the Platypus!The Plague (anime)" was redirected to: "Oran High School Host Club1440

Summary

2023 Chicago Open08/05/2023Y450%0%0%106.50