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 |
|---|---|---|---|---|---|---|
| Capital One in the Twenty-First Century | The Fire Neg Time | 10 | 10 | 0 | 20 | ME |
| Middlesex County Fetty Wap Fan Club | consumption smoothing by borrowing future big law income | 0 | 10 | 0 | 10 | E |
| The Saint-Straw that Broke the Camille's Back | Surrealist Subcommandante Marcos be like Esto no es una pipa | 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% |