Question
The best-known algorithm for this task gains its efficiency from only considering seven sub-problems, rather than the eight sub-problems necessary in a naïve approach. For 10 points each:
[10m] Name this task that can be solved in sub-cubic runtime using Strassen’s algorithm. GPUs are particularly efficient at performing this mathematical task due to their parallel nature.
ANSWER: matrix multiplication [or equivalents such as multiplying two matrices; prompt on multiplication; reject answers that refer to “multiplication of numbers” or “multiplication of integers”]
[10h] Strassen also developed a probabilistic algorithm for this other problem. The poly-time AKS algorithm was introduced in a paper simply titled “[this problem] is in P.”
ANSWER: primality testing [or word forms; or descriptions of checking if a number is prime or not or descriptions of checking if a number is composite or not; accept PRIMES or “PRIMES is in P” or Solovay–Strassen primality test or AKS primality test; reject “prime factorization”]
[10e] A computational problem is in the complexity class P if it can be solved in polynomial time on a deterministic version of this British computer scientist’s namesake “machines.”
ANSWER: Alan Turing [accept Turing machines]
<Other Science>
Summary
| 2024 ACF Winter at Lehigh | 2024-11-16 | Y | 7 | 12.86 | 100% | 29% | 0% |
| 2024 ACF Winter at Northwestern | 2024-11-16 | Y | 9 | 15.56 | 100% | 56% | 0% |
| 2024 ACF Winter at Ohio State | 2024-11-16 | Y | 9 | 12.22 | 100% | 22% | 0% |
| 2024 ACF Winter at Online | 2024-11-16 | Y | 7 | 11.43 | 100% | 14% | 0% |
| 2024 ACF Winter at Central Florida | 2024-11-16 | Y | 4 | 12.50 | 75% | 50% | 0% |
| 2024 ACF Winter at Oxford | 2024-11-16 | Y | 8 | 18.75 | 100% | 50% | 38% |
Data
| Cambridge A | Bristol A | 10 | 10 | 10 | 30 |
| Cambridge B | Imperial A | 10 | 10 | 10 | 30 |
| Manchester | Cambridge C | 0 | 0 | 10 | 10 |
| Southampton A | Cambridge D | 10 | 10 | 10 | 30 |
| Durham | Birmingham | 0 | 0 | 10 | 10 |
| Imperial B | Warwick A | 10 | 0 | 10 | 20 |
| LSE A | Oxford A | 0 | 0 | 10 | 10 |
| Oxford B | Southampton B | 0 | 0 | 10 | 10 |