Question
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>
Summary
| 2025 ACF Nationals | 04/19/2025 | Y | 20 | 15.00 | 75% | 55% | 20% |
Data
| Arizona State | North Carolina B | 0 | 10 | 10 | 20 |
| Illinois A | Chicago B | 0 | 10 | 0 | 10 |
| Columbia A | Winona State | 0 | 10 | 10 | 20 |
| UC Berkeley A | Columbia B | 0 | 10 | 10 | 20 |
| Stanford | Georgia State | 0 | 10 | 10 | 20 |
| Harvard | Vanderbilt | 0 | 0 | 0 | 0 |
| Illinois B | WUSTL A | 0 | 10 | 0 | 10 |
| Johns Hopkins | Virginia Tech | 0 | 10 | 0 | 10 |
| LSE | North Carolina A | 0 | 0 | 0 | 0 |
| Cornell A | Maryland | 0 | 10 | 10 | 20 |
| Michigan | British Columbia | 0 | 0 | 0 | 0 |
| Toronto C | NYU | 0 | 10 | 0 | 10 |
| Toronto A | Texas | 10 | 10 | 10 | 30 |
| UC Berkeley B | Ohio State | 10 | 10 | 10 | 30 |
| Northwestern | UCF | 0 | 0 | 0 | 0 |
| Rutgers | Virginia | 0 | 10 | 10 | 20 |
| Waterloo A | Ottawa | 10 | 10 | 10 | 30 |
| Waterloo B | Georgia Tech | 10 | 10 | 10 | 30 |
| Florida | Yale | 0 | 0 | 0 | 0 |
| Chicago A | Toronto B | 0 | 10 | 10 | 20 |