Question

Previous bonus - Next bonus
Radia Perlman’s poem “Algorhyme” describes how a protocol she designed maintains one of these structures by having network switches exchange BPDU messages. For 10 points each:
[10m] Name these structures that can be found in a graph by considering each node as a connected component, and then iteratively identifying the smallest edge weight between components.
ANSWER: spanning trees [accept minimum spanning trees or MSTs; accept Spanning Tree Protocol; prompt on trees] (BPDU is Bridge Protocol Data Unit. The process described is Borůvka’s algorithm.)
[10e] Perlman’s Spanning Tree Protocol prevents loops in these networks. In these networks, devices within a small geographic region are connected over Ethernet or Wi-Fi.
ANSWER: LANs (“lanz”) [or local area networks]
[10h] Older Ethernet LANs (“lanz”) had a bus topology that required this medium access control method to be used with collision detection. This method allows a machine to transmit only if no transmissions are detected on the bus.
ANSWER: CSMA [or carrier sense multiple access; accept CSMA/CD or carrier sense multiple access with collision detection; accept CSMA/CA or carrier sense multiple access with collision avoidance]
<Other Science>

Back to bonuses

Summary

2024 ACF Nationals2024-04-21Y2410.4263%38%4%

Data

Berkeley BCornell B0000
Chicago CMinnesota B0000
Chicago DMcGill0000
Toronto BClaremont Colleges0000
Columbia BArizona State1010020
DukeOttawa010010
FloridaYale B0000
Berkeley AGeorgia Tech1010020
HarvardVanderbilt010010
IndianaChicago A10101030
Iowa StateMaryland1010020
NorthwesternJohns Hopkins010010
Truman StateKentucky100010
IllinoisMichigan1010020
Minnesota AChicago B1010020
BrownNYU010010
North Carolina APurdue010010
North Carolina BSouth Carolina1010020
RutgersPenn0000
WUSTL AStanford0000
TexasCornell A010010
WUSTL BVirginia1010020
Columbia AWaterloo0000
Yale AToronto A010010