CPSC 411: Quiz 5
September 30, 2008

Printed Name:________________________________________

"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."

Signature:___________________________________________

  1. (2 pts) What is the goal of amortized analysis?







  2. (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.



  3. (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 potential function.