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. (10[1])Pollard’s (10[1])algorithm (10[1])for (10[1])integer factorization (10[1])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 (10[1])algorithm that creates a leading and trailing pointer called a “hare” (10[1])and “tortoise” (10[2])and is named (10[1])for Floyd. Detecting (10[1])these structures by checking (-5[1])already-visited nodes (-5[1])ensures that (-5[1])DFS (10[1]-5[1])halts. (10[2])The [emphasize] absence (10[1])of these structures defines the “A” in a DAG. (10[3])For 10 points, (10[3])name these (10[2])paths in a graph (10[2])that eventually (10[1]-5[1])lead back to their start. (10[1])■END■ (10[11]0[4])

Back to tossups

Buzzes

Summary