CS 306 Quiz 1

CS 306, Computer Algorithms II

Quiz 1, 16 September 2008

A colleague shows you an algorithm and asks you if it’s recursive. describe the algorithm features you would look for to answer your colleague’s question.
The three parts of an recursive algorithm are the base (or stopping) part, the recursive part, and the part that decides between the base and recursive part. In its simplest form, a recursive algorithm has an if statement with one branch that returns (or at least makes no further recursive calls) and another branch that calls the algorithm recursively.
Using statically allocated storage is usually not recommended when the maximum storage needed can vary widely. Describe two separate circumstances under which static allocation would still be acceptable under high variability.
The problem with wide size variations is running out of storage. Wide size variations wouldn’t cause storage exhaustion when 1) the maximum possible size variation can be covered by the maximum possible size (that is, the variations are large but the overall storage requirements are small) and 2) both the variations and maximum possible size is large, but can be covered by the allocation (that is, the maximum possible size is large, but can be covered by the allocation).
Explain why the worst-case complexity estimate O(2) is equivalent to O(1). Your explanation should be as mathematically formal as you can make it.

By the big-oh definition, there exists some function g such that Cf₂(n) ≥ g(n) for all n sufficiently large, where f₂(n) is the constant function that returns 2 for any value of n.

By arithmetic, f₂ = 2f₁, where f₁(n) is the constant function that returns 1 for any value of n. Substituting back into the previous inequality gives
C2f₁(n) ≥ g(n)
C2 is just another constant, C' say, giving
C'f₁(n) ≥ g(n)
In other words, g is also O(1).
Suppose you are using static allocation for the nodes in a binary tree ADT. Describe how you’d initialize the array holding the nodes. Give an asymptotic estimate of your initialization.

Each node in the node array is either being used or is free to be allocated. Initially all nodes are free to allocated, which means that initializing the node array involves making sure all nodes are marked as being free. How that gets done depends on how free nodes are marked.

One way to mark free nodes is to use a boolean, in which case initialization would be
```
for i = 1 to n
  nodes[i].free = true
```
where n is the number of nodes in the node array. This code touches every node, and is O(n).

Using a boolean per node requires searching the node array to allocate a node, which is also O(n). A free list provides a faster way to allocate nodes. All free nodes are linked together in a singly-linked list, and the free list points to the head of the list. Initially all nodes are on the free list, leading to the initialization code
```
for i = 1 to n - 1
  nodes[i].left = i + 1
nodes[n].left = -1
free-list = 1
```
This initialization is also linear, but allocation now requires only a constant (and small) number of pointer manipulations.

Because initialization has to touch every node, it seems the lower bound would also have to be linear. It turns out that a small trick can be used to spread out and delay initialization to make it effectively constant.

The trick is to divide the node array into two parts: one part contains initialized nodes that are being freed and allocated and the other part contains uninitialized nodes not being used. Assume the right half of the node array contains the uninitialized nodes and the variable first-uninit is the index of the first uninitialized node (that is, the leftmost end of the uninitialized part). Initialization is now
```
free-list = -1
first-uninit = 1
```
In this case the initialized nodes are being managed by a free list. Initialization is constant time. Allocation is a bit more complicated, but it’s still constant time:
```
if free-list ≠ -1
  // allocate a node.
else
  // no more nodes; get an uninitialized node.
  if first-uninit > n
    // no more nodes, die.
  else
    first-uninit++
    // allocate node
```