Algorithms Notes – Chapter 3

travelling_salesman_problem

xkcd/399

References used for this section: A

Elementary Data Structures

Sets form the basis of both Mathematics and Computer Science. In Mathematics, we usually deal static (or frozen) sets. In other words, sets that don’t change much after their definition. In computer science, it is also common to deal with dynamic sets. A dynamic set is a set which allows the insertion and deletion of elements.

Just like static sets have operations like union, intersection etc., dynamic sets have additional operations. The operations on a dynamic set are divided into two categories:

  1. Queries – only return information from the set.
  2. Modifying Operations – change the set.

Here are some common dynamic set operations:

S = the set. k = the key value. x = pointer to an element in the set.

Queries

Search (S, k): returns a pointer x to an element in S such that x.key = k, or NIL if S contains no such  element.

Minimum(S): Let S be a totally ordered set. This returns a pointer to the element in S with the smallest key.

Maximum(S): Let S be a totally ordered set. This returns a pointer to the element in $latex $$ with the largest key.

Successor(S, x): Let S be a totally ordered set. This returns a pointer to the element that is the next largest to the one pointed to by x, or NIL if x points to the largest element.

Predecessor(S, x): Let S be a totally ordered set. This returns a pointer to the element that is the next smallest to the one pointed to by x, or NIL if x points to the smallest element.

Dynamic Operations

Insert(S, x): Adds the element pointed to by x to the set S, assuming the element already has the attributes necessary to be a part of S.

Delete(S, x): Removes the element pointed to by x from the set S.

Two Important Dynamic Sets

Stack: A stack has a prespecified delete operation. It implements what is called the last-in first-out (or LIFO for short) policy. The first element that gets deleted is the last element that was inserted into the stack.

Queue: A queue also has a prespecified delete operation. It implements the first-in first-out (or FIFO for short) policy. The first element that gets deleted is the first element that was inserted into a queue.

Implementing a Stack

Here’s a figure I got from wikipedia that makes it easy to understand how a stack works:

lifo_stack

A stack of at most n elements can be implemented using the following:

  • An array S[1 ... n].
  • An attribute of the array, S.top which stores the index of the most recently inserted element.

Stack Operations:
To implement a stack, you need the following three operations:

A query to check if the stack is empty.

STACK-EMPTY(S)
    if S.top == 0
        return TRUE
    else return FALSE

The insert operation, which in this case is called push. A dynamic operation.

PUSH(S, x)
    S.top = S.top + 1
    S[S.top] = x

The delete operation, which in this case is called pop. A dynamic operation.

POP(S)
    if STACK-EMPTY(S)
        error "underflow"
    else
        S.top = S.top - 1
        return S[S.top + 1]

Notes:

  • When S.top = 0, the stack is empty.
  • The stack underflows when we try to pop an empty stack
  • The stack overflows if S.top exceeds the value of n.

Implementing a Queue

Here’s a figure I got from wikipedia that makes it easy to understand how a queue works:

queue

A stack of at most n - 1 elements can be implemented using the following:

  • An array Q[1 ... n].
  • An attribute of the array Q.head that indexes the head of the queue.
  • An attribute of the array Q.tail that indexes the tail of the queue.

Queue Operations:

To implement a queue, you need the following two dynamic operations.

The insert operation, called enqueue in this case.


ENQUEUE(Q, x)
    Q[Q.tail] = x
    if Q.tail == Q.length
        Q.tail = 1
    else Q.tail = Q.tail + 1

and the delete operation, called dequeue.


DEQUEUE(Q)
    x = Q[Q.head]
    if Q.head == Q.length
        Q.head = 1
    else
        Q.head = Q.head + 1
    return x

To understand this better, refer to figure 10.2 in Section 10.1 of Introduction to Algorithms 3rd Edition by Cormen et al.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s