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>

Back to bonuses

Summary

Data

Brandeis ABoston University001010
Dartmouth ABrandeis B0000
Yale AHarvard B0000