Question
The banker’s and physicist’s methods are the most common ways of analyzing this quantity. For 10 points each:
[10m] Name this measure of average computational complexity that is less pessimistic than worse-case complexity, since it accounts for cases where the worst case happens infrequently.
ANSWER: amortized complexity [accept amortized runtime]
[10h] Amortized analysis assumes that each operation’s output is an input to the next one, making it apt for this class of algorithms similar to streaming algorithms. These algorithms do not see the whole input at once, but instead must act each time they see a piece.
ANSWER: online algorithms
[10e] A variant of this data structure that dynamically resizes has a constant amortized runtime for insertion. This one-dimensional data structure has fixed capacity and its contents can be accessed by index.
ANSWER: array [accept array list; prompt on list]
<Other Science>
Summary
| 2024 ACF Regionals @ Berkeley | 01/27/2024 | Y | 3 | 13.33 | 67% | 0% | 67% |
| 2024 ACF Regionals @ Cornell | 01/27/2024 | Y | 3 | 13.33 | 100% | 0% | 33% |
| 2024 ACF Regionals @ JMU | 01/27/2024 | Y | 9 | 12.22 | 89% | 22% | 11% |
| 2024 ACF Regionals @ Minnesota | 01/27/2024 | Y | 2 | 15.00 | 100% | 50% | 0% |
| 2024 ACF Regionals @ Ohio State | 01/27/2024 | Y | 3 | 6.67 | 67% | 0% | 0% |
| 2024 ACF Regionals @ Rutgers | 01/27/2024 | Y | 5 | 10.00 | 60% | 20% | 20% |
| 2024 ACF Regionals @ Imperial | 01/27/2024 | Y | 8 | 12.50 | 88% | 25% | 13% |
| 2024 ACF Regionals @ Vanderbilt | 01/27/2024 | Y | 5 | 6.00 | 60% | 0% | 0% |
| 2024 ACF Regionals @ MIT | 01/27/2024 | Y | 3 | 3.33 | 33% | 0% | 0% |
Data
| Columbia A | NYU B | 0 | 10 | 10 | 20 |
| Haverford | Columbia C | 0 | 0 | 0 | 0 |
| John Jay | NYU A | 10 | 0 | 10 | 20 |
| Penn | Columbia B | 0 | 0 | 10 | 10 |
| Vassar | Rowan | 0 | 0 | 0 | 0 |