A2 Q1

[Thom Bohdanowicz]

regarding the specifications for the first constructor (the one that
creates an empty heap of size 0 in an array of size n):

does simply initializing an array of the correct size satisfy this
description? or do we need to fill it with zeros?

also is it okay to allocate space for the array on the heap (or does
this somehow violate the O(1) requirement? i can't remember how slow
memory allocation is)?

I've coded up the data structure and it works just fine but I just don't
want to get dinged for technically not meeting the "specification"

[cs240]

You are allowed to allocate memory on the heap. When we analyze the
complexity of the two algorithms, we are mostly concerned with the runtime
not the space required to store the array.

Vivian
CS240 Tutor

regarding the specifications for the first constructor (the one that creates
does simply initializing an array of the correct size satisfy this
description? or do we need to fill it with zeros?
also is it okay to allocate space for the array on the heap (or does this
somehow violate the O(1) requirement? i can't remember how slow memory
allocation is)?
I've coded up the data structure and it works just fine but I just don't want
to get dinged for technically not meeting the "specification"

[Su Zhang]

Post by Thom Bohdanowicz
also is it okay to allocate space for the array on the heap (or does
this somehow violate the O(1) requirement? i can't remember how slow
memory allocation is)?

In this case I do not see why we should not use dynamic memory
allocation, as n is a variable and cannot be determined at compile time.
With GCC extension, we can allocate variable-length arrays as a
automatic storage on the stack, but this reduces the portability of the
code as the function may not be supported by other compilers.

Modern heap implementations on modern desktop systems typically use
combinations of optimization techniques for dynamic memory allocations,
which produces a very fast heap allocator. However, since it is
dependent on specific systems and heap implementations, and since the
amount of memory requested usually has no apparent correlation with the
running time (that is, allocating a large chunk of memory can sometimes
be faster than allocating a smaller chunk of memory depending on the
overall states of the heap prior to the allocation), the complexity of
dynamic memory allocation is generally ignored in algorithm analysis.

For your interests:
http://g.oswego.edu/dl/html/malloc.html