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
| Bard A | Rowan A | 0 | 0 | 10 | 10 |
| Columbia B | Johns Hopkins A | 0 | 0 | 10 | 10 |
| Haverford A | Princeton A | 0 | 0 | 10 | 10 |
| Rutgers A | Johns Hopkins B | 0 | 0 | 10 | 10 |
| Penn B | Penn A | 0 | 0 | 10 | 10 |
| Penn State A | Columbia A | 10 | 0 | 10 | 20 |
| Penn State B | Rutgers C | 10 | 0 | 10 | 20 |
| Indiana A | Purdue A | 10 | 0 | 10 | 20 |
| UIUC D | Miami | 0 | 0 | 10 | 10 |
| Northwestern A | Notre Dame | 10 | 0 | 10 | 20 |
| Purdue B | SIUE A | 10 | 0 | 10 | 20 |
| WashU C | Purdue C | 0 | 0 | 10 | 10 |
| UChicago D | Indiana B | 0 | 0 | 10 | 10 |
| UIUC A | UChicago C | 10 | 0 | 10 | 20 |
| WashU B | UIUC B | 10 | 0 | 10 | 20 |
| UIUC C | UChicago B | 0 | 0 | 10 | 10 |
| CWRU A (UG) | Ohio State C (DII) | 0 | 0 | 10 | 10 |
| Kenyon A (UG) | CWRU C (UG) | 10 | 0 | 10 | 20 |
| CWRU D (DII) | Kenyon B (DII) | 0 | 0 | 10 | 10 |
| Michigan C (UG) | CWRU B (UG) | 0 | 0 | 10 | 10 |
| Michigan State C (UG) | Michigan D (DII) | 0 | 0 | 10 | 10 |
| Michigan State A | Pitt A | 0 | 0 | 10 | 10 |
| Pitt B (UG) | Michigan State B (UG) | 0 | 0 | 10 | 10 |
| Michigan A | Ohio State A (UG) | 10 | 0 | 10 | 20 |
| Ohio State B (DII) | Michigan B | 0 | 0 | 10 | 10 |
| Missouri | Iowa | 0 | 0 | 10 | 10 |
| Central Oklahoma | Mississippi State | 0 | 0 | 10 | 10 |
| Oregon State | McGill E | 0 | 0 | 10 | 10 |
| Texas C | Colorado College | 0 | 0 | 10 | 10 |
| Texas A | Vassar A | 0 | 0 | 10 | 10 |
| Vassar B | Texas D | 0 | 0 | 10 | 10 |
| NYU B | WUSTL A | 10 | 0 | 10 | 20 |
| Florida Tech A | UF D | 10 | 0 | 10 | 20 |
| UCF A | Florida State University A | 10 | 0 | 10 | 20 |
| UF B | UCF B | 0 | 0 | 10 | 10 |
| UF F | UF E | 0 | 0 | 0 | 0 |
| 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 |