Packet 1: Tossup 11

A variant of this data structure was used by Dillencourt with “age balancing” to label ordered images. Collections of this data structure can be optimized using “refinement,” which gives the Coffman–Graham algorithm linear runtime. A variant of this data structure is used to determine if adding an edge to the output would create a cycle when greedily creating a minimum spanning (10[1])tree (-5[1])in Kruskal’s algorithm. (10[1])A defining condition of this data structure (10[1])is relaxed to form an analogous structure sometimes called a “bag.” The inverse (-5[1])Ackermann function bounds the amortized runtime of a variant of this data structure named for its (10[1])“merge” and “find” operations (-5[1])or called the “disjoint-[this (10[1])structure] (10[2])forest.” (10[3])For 10 points, name this unordered data structure (10[1])that stores unique values, (10[1]-5[1])which is typically abstractly written using curly braces. (10[2])■END■ (10[6]0[3])

Back to tossups

Buzzes

Summary