Tossup

Gabriel Nivasch’s “multi-stack” algorithm identifies these structures. An unsolved problem that asks whether these structures produce a double cover reduces to asking about “snarks.” These structures cause Kahn’s algorithm to output an empty list, since they prevent topological sortings. Pollard’s algorithm (10[1])for integer factorization is named for the eventual resemblance to one of these structures over time. Gosper’s algorithm (-5[1])for detecting these structures improves upon another algorithm that creates a leading and trailing pointer called a “hare” and “tortoise” (10[1])and is named for Floyd. Detecting these structures by checking (-5[1])already-visited nodes ensures that DFS halts. (10[1])The [emphasize] absence of these structures defines the “A” in a DAG. (10[1])For 10 points, (10[1])name these paths in a graph that eventually lead back to their start. (10[1])■END■ (10[3]0[2])

Back to tossups

Buzzes

Summary