6  Basic Data Structures

“A computer would deserve to be called intelligent if it could deceive a human into believing that it was human.”
– Alan Turning

Most algorithms take their input as a collection of objects. Such a collection, also called data, is usually organized as a data-structure. In this chapter, we discuss some of commonly used data-structures: arrays, stacks, and queues.

Recall that in our running time analyses so far, we tacitly assumed that accessing an element A[i] at index i into a collection A took constant time. This is, in fact, the case if A is an array. However, if the algorithm was handed a different data-structure like a linked-list L, accessing L[i] would take \Omega(\text{n}) in the worst-case for an n-element list. The choice of the data-structure used in an algorithm is thus crucial.

6.1 Arrays

Array (or something equivalent) is a primitive data-structure in almost all programming languages. Most compilers store an array in the memory as a contiguous sequence of (a fixed number of) bytes. In each block of bytes, a data element is stored. In order to keep the size (or number of bytes) of each block fixed, compilers do not store data objects of different types in them.

In Python, arrays are implemented by the class list. Although Python tricks us into believing that a list can contain objects of different types, only the references (or addresses) to those objects are kept in each element of the list.

Access

Given a list A and an index i into the list, the object at index i is accessed by A[i].

Complexity:

• Time: O(1)

• Extra Space: O(1)

Array indexing takes constant time because of two reasons. First, we can calculate the memory address of the i-th element using a + i\times s. Here a is the address of the first element in the array, and s is the space each element takes (this is why the elements in an array must have the same type, so that will be the same for every element).

Second, we can retrieve the element from the address in the equation above. Both calculating the address and retrieving the element take constant time. This is the key reason why array is one of the most important data structures in algorithm design.

In practice, the two steps are combined in one. Moreover, we do not have to know the a and s in the equation above as the complier keeps track of them. All we need to know is the index of the element we want to access.

Find Max (Min)

Let us now develop and compare strategies to find the maximum element of a given array.

Here is an incremental scheme taking O(n) in the worst-case:

\begin{algorithm} \caption{MAX-ARRAY} \begin{algorithmic} \Procedure{MAX-ARRAY}{$A[0:n-1]$} \State $max=A[0]$ \For{$i = 1$ \To $n-1$} \If{$A[i] \geq max$} \State $max=A[i]$ \EndIf \EndFor \Return $max$ \EndProcedure \end{algorithmic} \end{algorithm}

Exercise 6.1 Explain why the for-loop in #3 iterates from i=1, instead of i=0.

Solution

This is alright, because the running max is initialized with A[0].

So, it suffices to now visit the other elements A[1:n-1] of the array to check for a bigger element.

Exercise 6.2 What would happen if the inequality in line #4 was replaced with strict inequality?

Solution

Although the replacement update max less frequently, it would not change the outcome of the algorithm. With a >, we update the current max only when a genuinely larger element is encountered.

In that sense, the replacement would be a better coding practice.

Exercise 6.3 Identify at least three corner cases for Algorithm 1. Discuss how you would address them.

Solution

1. The input is not a list or iterable.
   • raise an Exception.
2. The input list is empty, i.e., len(A)=0.
   • The mathematical convention is that the maximum of the empty set (\emptyset) is -\infty. So, I would return -math.inf in this case.
3. The input is a non-empty array with non-numerical values.
   • raise an Exception.

Exercise 6.4 Implement Algorithm 1 in Python handling the above mentioned corner cases.

Exercise 6.5 Develop an algorithm for finding the maximum using divide-and-conquer. Make sure that the size of each subproblem is nearly half the original size.

Solution

Let A[p, r] is the array under consideration.

Divide: Split into two subarrays A[p:q] and A[q+1:r], where q is the midpoint of p and r.

Conquer: Recursively find max of A[p:q] and A[q+1:r]. The recursion reaches the base case—when p\geq r.

Combine: We use the recursive formula: \max(A[p,q])=\max\{\max(A[p,q]), \max(A[q+1,r])\}.

Exercise 6.6 Analyze the time-complexity and (extra) space-complexity of the above recursive scheme.

Solution

Here are the costs:

Divide + Combine: constant, say c_1.

Conquer: Two subproblems, each with half the size.

Therefore, the running time T(n)=c_1 + 2T(n/2). The Master theorem gives us: T(n)=O(n).

Extra space: O(1).

Exercise 6.7 Find a good lower bound on the time-complexity in big-\Omega notation.

Solution

Note that to find the maximum of a list, we must visit each element of the list at least one. Hence, a lower bound is \Omega(n).

Insert

A new element x is inserted into a list A by the list method A.append(x).

Exercise 6.8 Discuss the time-complexity of .append().

Solution

Note that insertion is usually O(1) if array is implemented to have a fixed length. Examples include C, C++, Java, etc.

In Python, lists are of variable length—similar to ArrayList in Java. Such flexibility comes at a cost. When the list gets full, the .append(x) doubles are size of the array incurring a cost of O(n). So, inserting a new element technically takes O(n).

Doubling of the array does not happen with each call of .append(x), but only when the array is full. For this reason, the amortized running time is O(1). Read to know more about amortized analysis.

Search

Finding membership of an element x in a list A is done by using the command x in A. As we have already discussed, the operation takes O(n) in the worst-case.

Dictionary

Although we would discuss the dictionary data-structure in this course, they facilitate O(1)-time searching of a key x.

If D is a Python dictionary and key is a query item, then key in D takes O(1).

Delete

Exercise 6.9 Discuss the time-complexity of deleting from an array the element at an index i.

6.2 Stacks (LIFO)

Simply put, a stack is a data-structure that follows LIFO (last-in, first-out) policy. A stack is often visualized as a stack of plates, where a plate is added (and removed) always from the top. The data-structure implements two operations: push and pop.

In Python, a list can be used as a stack. It implements insertion to a stack via append(x) and removal of the last element via pop().

Complexity:

• pop: O(1)

• push: O(n), but O(1) amortized

Call Stacks

Execution of recursive algorithms make use of stacks. Internally, a compiler (or interpreter) uses a call stack to store information about the active subroutines of a computer program.

In order to run a computer program, the compiler repeatedly evaluates the top of the corresponding call stack. If the main program depends on a subroutine, then the subroutine is pushed to the top of the call stack to be evaluated first.

Demo: recFact

viewof n1 = Inputs.range([0, 10], {
  value: 3,
  step: 1,
  label: tex`n`
});
mutable done1 = false;
mutable pending1 = false;

html`<br>`;

viewof execute1 = Inputs.button(`evaluate`, {
  value: null,
  disabled: done1 || S1.length == 0,
  reduce: () => {
    let d = S1[S1.length - 1];
    d.pending = true;

    if(d.x <= 1) {
      d.val = 1;
      d.pending = false;
      mutable done1 = true;
    }
    else if(d.val == -1) {
      S1.push({x: d.x - 1, val: -1, pending: false});
      mutable done1 = false;
    }
  }
});
viewof pop1 = Inputs.button(`pop`, {
  value: null,
  disabled: !done1 ||  S1.length == 0,
  reduce: () => {
    let d = S1.pop();      
    let d1 = S1[S1.length - 1];
    if(d1) {
        d1.val = d.val * d1.x;
        d1.pending = false;
        mutable done1 = true;
    } else {
        S1.append(d);
    }
  }
});

S1 = [{x: n1, val: -1, pending: false}];
{
  execute1;pop1;n1;
  const container = d3
    .create("div")
    .attr("width", width)
    .style("min-height", '100px')
    .style("margin-top", '30px')
  
  container
    .selectAll(".element")
    .data(S1.toReversed())
    .join("div")
    .attr("class", "element")
    .style("border", "3px solid lightgray")
    .style('border-color', (d, id) => done1 && id == 0 ? 'lightgreen' : 'pink')
    .style("width", "200px")
    .style("height", "50px")
    .style("padding", "1px")
    .style("text-align", "center")
    .style("font-size", "20px")
    .style("line-height", "40px")
    .text((d, id ) => d.pending ? `${d.x}! = ${d.x-1}! * ${d.x}` :  
          d.val == -1 ? `${d.x}!` : `${d.x}! = ${d.val}`)
  return container.node();
}

Demo: recFib

viewof n = Inputs.range([0, 10], {
  value: 3,
  step: 1,
  label: tex`n`
});
html`<br>`;

viewof execute = Inputs.button(`evaluate`, {
  value: null,
  disabled: done || S.length == 0,
  reduce: () => {
    let d = S[S.length - 1];
    d.pending = true;

    if(d.x <= 1) {
      d.val = d.x;
      d.a, d.b = d.x, d.x;
      d.pending = false;
      mutable done = true;
    }
    else if(d.a == -1) {
      S.push({x: d.x - 1, a: -1, b: -1, val: -1, pending: false});
      mutable done = false;
    }else if(d.b == -1) {
      S.push({x: d.x - 2, a: -1, b: -1, val: -1, pending: false});
      mutable done = false;
    }
    }
});
viewof pop = Inputs.button(`pop`, {
  value: null,
  disabled: !done ||  S.length == 0,
  reduce: () => {
    let d = S.pop();      
    let d1 = S[S.length - 1];
    if(d1) {
      if(d1.a == -1) {
        mutable done = false;
        d1.a = d.val;
      }
      else if(d1.b == -1) {
        d1.b = d.val;
        d1.val = d1.a + d1.b;
        d1.pending = false;
        mutable done = true;
      }
    } else 
        S.append(d);
  }
});

S = [{x: n, a: -1, b: -1, pending: false, val: -1}];
mutable done = false;
mutable pending = false;

{
  execute;pop;
  const container = d3
    .create("div")
    .attr("width", width)
    .style("min-height", '100px')
    .style("margin-top", '30px')
  
  container
    .selectAll(".element")
    .data(S.toReversed())
    .join("div")
    .attr("class", "element")
    .style("border", "3px solid lightgray")
    .style('border-color', (d, id) => done && id == 0?'lightgreen' : 'pink')
    .style("width", "200px")
    .style("height", "50px")
    .style("padding", "1px")
    .style("text-align", "center")
    .style("font-size", "20px")
    .style("line-height", "40px")
    .text((d, id ) => d.pending ? `F(${d.x}) = ` + (d.a == -1 ? `F(${d.x-1})` : d.a) + ` + F(${d.x - 2})` : d.val == -1 ? `F(${d.x})` : `F(${d.x}) = ${d.val}`)
  return container.node();
}

Exercise 6.10 A sequence of parentheses in a string is valid if they occur in the correct open-close order. Assume that the input string can contain only ( and ).

For example: (()) is valid, but (() is not. Design an algorithm to check if an input string has valid parentheses.

Exercise 6.11 Implement in Python what you have designed.

Exercise 6.12 A sequence of parentheses in a string is valid if they occur in the correct open-close order. Assume that the input string can contain
{, (, [, ], ), and }.

For example: ([]) is valid, but (][) is not. Design an algorithm to check if an input string has valid parentheses.

Solution

To be added.

Exercise 6.13 Implement in Python what you have designed.

6.3 Queue (FIFO)

In this section we will introduce another data structure, named queue, which works in a somehow opposite way compared to stack. In simple words, queue is a structure where data are stored in a FIFO (first in first out) fashion. This is the key difference between queue and stack (which works in a LIFO way). You can think of the queue data-structure as the queue in real life. Most of the time, we wait in a queue (or a line) so that the customer who enters first will be served first (a.k.a., first come first serve). It would be chaotic if we waited in a stack instead!

There is another difference between stack and queue, on the programming level. As mentioned, we use the class list to implement stack. However, we do not do so for queue. This is because all the operations for stack (pushing and popping) are conducted from the end of the list.

A queue must implement two methods: enQueue(x) (to the end) and deQueue() (from the front). Ideally, both must take O(1) time. There is a data-structure particularly designed for queue in Python, named deque. Here are some simple examples showing how it works.

6.4 Priority Queue

In this section we will introduce another data structure, named priority queue, which generalizes both the stack and queue data structures.

In simple words, each object x in a priority queue has a priority, stored in an attribute named key. Then, objects are added and removed based on their priorities: x.key. There are two types: max-priority queue and min-priority queue. Here we only discuss the former: the object with the most priority is the one to be popped first. To abuse notation, we simply call it priority queue.

We can now think of queue as a priority queue, where x.key is the given by their waiting time in the queue. The longer an object waits, the more priority it earns for being popped; this is exactly the FIFO policy.

Similarly, we can now think of stack as a priority queue, where x.key is the given by the negative of their waiting time in the queue. The longer an object waits, the less priority it earns for being popped; this is exactly the LIFO policy.

A priority queue must implement two methods: enQueue(x), deQueue(), increaseKey(x).

Exercise 6.14 Design an implementation of priority queue, and analyze the time and space complexities of our scheme.

6.5 Resources

Read more about the complexities of data-structures implemented in Python.

Stack of papers. Image courtesy iStockPhotos.