Extra Credit: An Exercise In Intimidation

File under "phrases I would not want to find on my homework." A tipster who is currently enrolled in COS 423: Analysis of Algorithms showed us this choice excerpt from their first problem set:

6. (Extra credit) We proved in class that if we use a regular or strictly regular redundant binary representation, adding 1 changes at most 3 digits, which means that counting from 0 to n takes at most 3n digit changes, whereas counting to from 0 to n using the standard binary representation takes at most 2n digit changes.  But is the 3n tight?  Use an amortized analysis to obtain the best upper bound you can (best constant factor) on the total number of digit changes to count from 0 to n using (a) the regular representation (regular addition) and (b) the strictly regular representation (strictly regular addition). This problem is extra credit because I don’t (yet) know the answer.

Yes, Robert Tarjan -- star professor in the Computer Science department and recipient of the Turing Award, the field's highest distinction -- assigned an exercise that even he didn't quite know the answer to. Something of an intimidating assignment.Because this problem could bear some translating, COS 423 student Ajay Roopakalu '13 helped put it in layman's terms. He explained that some aspects of algorithms analysis are a "science" while other aspects are an "art." In an amortized analysis, there is room for creativity; you can tinker with the variables of the potential function to produce slightly different bounds on time. The professor was basically seeing if they could design a function with "better time bounds than the one classically used." Tarjan should be commended for this novel, if ambitious, idea: assign open problems to your students and see if something brilliant pops out!