CPSC 411: Quiz 5
September 30, 2008
"On my honor, as an Aggie, I have neither given nor received
unauthorized aid on this academic work.
In particular, I certify
that I have not received or given any assistance that is
contrary to the letter or the spirit of the collaboration
guidelines for this assignment."
- (2 pts) What is the goal of amortized analysis?
- (1 pt) True or False: In the accounting method
of amortized analysis, you are permitted to charge some of the
cost of the current operation to future operations.
- (2 pts) Recall that the potential method of amortized analysis
uses a function (called the potential function) that, given a state
of the data structure, returns a real value. How is the amortized
cost of an operation defined? Hint: The definition uses the