We have seen how dynamic arrays enable arrays to grow while still achieving constant-time amortized performance. This problem concerns extending dynamic arrays to let them both grow and shrink on demand.
a) Consider an underflow strategy that cuts the array size in half whenever the array falls below half full.
Describe a sequence of insertions and deletions where this strategy gives a bad amortized cost.
b) Give a better underflow strategy than suggested above, one that always achieves constant amortized cost per deletion.