Packet 4: Bonus 15
A 2025 result from Duan et al. claims to have disproven the conjectured optimality of this algorithm. For 10 points each:
[10m] Name this algorithm that maintains and updates a set of “frontier” elements in a priority queue. This algorithm is extended by an algorithm that additionally filters elements using an admissible heuristic function.
ANSWER: Dijkstra’s algorithm (The extension is A*.)
[10e] Dijkstra’s algorithm accomplishes this task on non-negative edge-weight graphs.
ANSWER: shortest path finding [or shortest path; accept descriptions of finding the shortest path between two nodes or vertices of a graph]
[10h] This algorithm extends Dijkstra’s algorithm to negative edge weights by reweighting each edge to make them all positive, using the Bellman–Ford algorithm to find paths, undoing the reweighting, and then running Dijkstra’s algorithm.
ANSWER: Johnson’s algorithm
<SL, Other Science (Computer Science)> | NAFTA-Packet-4
| Heard | PPB | E % | M % | H % |
|---|---|---|---|---|
| 37 | 14.05 | 97% | 43% | 0% |
Conversion
| Team | Opponent | Part 1 | Part 2 | Part 3 | Total | Parts |
|---|---|---|---|---|---|---|
| Berkeley A | Team 7 | 10 | 10 | 0 | 20 | ME |
| Stanford A | Constans Constantius and Constantine Jr. | 10 | 10 | 0 | 20 | ME |
| Stanford B | Not Old! (Old) | 10 | 10 | 0 | 20 | ME |
| Team 8 | Berkeley B | 0 | 10 | 0 | 10 | E |
Summary
| Tournament | Edition | Match | Heard | PPB | E % | M % | H % |
|---|---|---|---|---|---|---|---|
| 2026 NAFTA at Stanford | 01/17/2026 | ✓ | 4 | 17.50 | 100% | 75% | 0% |
| 2026 NAFTA at UBC | 01/17/2026 | ✓ | 2 | 15.00 | 100% | 50% | 0% |
| 2026 NAFTA at Vanderbilt | 02/14/2026 | ✓ | 3 | 13.33 | 100% | 33% | 0% |
| 2025 NAFTA at Toronto | 09/13/2025 | ✓ | 4 | 15.00 | 100% | 50% | 0% |
| 2025 NAFTA at Maryland | 09/27/2025 | ✓ | 4 | 12.50 | 75% | 50% | 0% |
| 2025 NAFTA at Harvard | 10/04/2025 | ✓ | 3 | 13.33 | 100% | 33% | 0% |
| 2025 NAFTA at Oxford | 10/11/2025 | ✓ | 4 | 12.50 | 100% | 25% | 0% |
| 2025 NAFTA at Chicago | 11/08/2025 | ✓ | 6 | 11.67 | 100% | 17% | 0% |
| 2025 NAFTA at Columbia | 11/08/2025 | ✓ | 5 | 16.00 | 100% | 60% | 0% |
| 2025 NAFTA at Richmond | 12/20/2025 | ✓ | 2 | 15.00 | 100% | 50% | 0% |