CPSC 425 Spring 2004
HW 5: Heap Management

1. We discussed three heap-allocation systems: first fit, best fit, and worst fit. For each system, give a memory size and sequence of allocations and deallocations that will succeed for that scheme and fail for the others.

2. We discussed three garbage collection systems: reference counting, mark-and-sweep and copying. Carefully evaluate each of these with respect to
   1. correctness (will it ever collect non-garbage?)
   2. completeness (will it collect all garbage?), and
   3. time and space efficiency. Be as specific as possible on this last one: exactly how much space is required, and for what? Is it possible to use less space? If so, what is the penalty for doing so? How much time is required, and for what? Big-O estimates are fine for time, but clearly specify what the input size (N) represents.