Random Access Machine

In order to judge the performance of an algorithm, there exists a mental mathematical model. This mental mathematical model helps us to ensure the stability and high performance of algorithms. Also, one could compare two algorithms using this model.

Mathematical Model: Random Access Machine.

This model consists of a processor and memory.

Designing algorithms for RAM: 

  • Variable names are allowed
  • Arrays, structures will be taken as Primitive data types
  • Trees, lists etc are allowed.
  • Instruction set:
    1. Arithmetic and Logical Operations (Single Step)
    2. Jumps and conditional jumps (Single Step)
    3. Pointer instructions (Single Step)
    4. Single dimension Array Operations (Single Step) 
Now, please note that some complex statements which do not fall in the above mentioned instruction set e.g. a = b + c * d + f will take more than one step (here 3)

Multidimensional Arrays

Lets consider a 2D array. To represent the 2D array in memory, one needs to use a linear model as the memory is linear in nature.

thus, A[i, j] = A’[i * m + j] , where m is the number of columns in one row of 2D array. 

As, A = 1, 2, 3, 4
           5, 6, 7, 8

is represented as 1, 2, 3, 4, 5, 6, 7, 8 in the linear memory.

Similarly, for a 3D array A[m][n][o]. A[i, j, k] = A’[(i * (n * o)) + (j * o) + k]
Just try and imagine a stack of 2D arrays, where i represents the number of 2D array in stack, j represents the row number and o represents the column number; and you’ll hit an epiphany.

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

%d bloggers like this: