Advanced Data Structures

Fall 2003

The ADT ExtendibleArray has, among other constant time operations, an operation "Claim" which claims the next available entry of the array. The array is initially allocated certain amount of memory that doubles in size whenever it overflows (ie., needs more space than is available). This allocation of the larger space incurs a non-constant cost of copying the previous array's entries -- to say nothing of initialization. Using the credit invariant argument show that this ADT has constant amortized complexity. (This idea is used in "extendible hashing", see the paper by Fagin et al.)
What are the results of executing the following loops ("nothing" is a no-op):
- while (False) do nothing;
- while (True) do nothing;
- while (this loop terminates) do nothing;
The greatest common divisor of two positive integers a and b, GCD(a,b), can be found by the Euclid's algorithm (I am sure you can figure out the convoluted then-clause, here just for fun (:-)
x=a; y=b; while (x!=y) do {if x<y then {y=x+y; x=y-x; y=y-x}; x=x-y}
- Define a loop invariant to prove that the value of x=y obtained from the execution of the loop is the GCD(a,b).
- What is the complexity of the above algorithm?
- (extra) Can you speed up the algorithm (make your own assumptions)?