Bonus

Previous bonus - Next bonus
A “graph” analog of this data structure can be used in distributed computing for data split between different nodes. For 10 points each:
[10h] Name this probabilistic data structure that consists of multiple linked lists. The first list contains all the elements in order, while each subsequent list contains a random subset of the previous one’s elements.
ANSWER: skip list [accept skip graph; prompt on list]
[10e] Operations on a skip list have this average-case big-O time complexity. This is also the average-case time complexity of binary search on a sorted array.
ANSWER: logarithmic [or O(log n); accept logarithms of any base, such as O(ln n) or O(log2n)]
[10m] Skip lists may be used to reduce these entities’ namesake contention in concurrent systems. Unlike semaphores, these synchronization primitives are always obtained and released by the same thread.
ANSWER: locks [or mutexes; accept lock contention or spinlocks]
<Other Science>
Answerlines and category may not exactly match the version played at all sites

Back to bonuses

Conversion

TeamOpponentPart 1Part 2Part 3TotalParts
Arizona StateNorth Carolina B0101020EM
Chicago AToronto B0101020EM
Columbia AWinona State0101020EM
Cornell AMaryland0101020EM
FloridaYale0000
HarvardVanderbilt0000
Illinois AChicago B010010E
Illinois BWUSTL A010010E
Johns HopkinsVirginia Tech010010E
LSENorth Carolina A0000
MichiganBritish Columbia0000
NorthwesternUCF0000
RutgersVirginia0101020EM
StanfordGeorgia State0101020EM
Toronto ATexas10101030HEM
Toronto CNYU010010E
UC Berkeley AColumbia B0101020EM
UC Berkeley BOhio State10101030HEM
Waterloo AOttawa10101030HEM
Waterloo BGeorgia Tech10101030HEM

Summary

TournamentExact Match?HeardPPBEasy %Medium %Hard %
2025 ACF NationalsYes2015.0075%55%20%