the cedar ledge

Random Access Machine (RAM) Model

Date: January 7 2021

Summary: Modeling computational actions as single step actions

Keywords: ##zettel #random #access #machine #model #archive

Bibliography

Not Available

Table of Contents

    1. Properties of RAM
      1. Step Execution of Times
      2. Data Types
    2. Algorithmic Analysis within the RAM Model
  1. How To Cite
  2. References
  3. Discussion:

Random Access Machine (RAM) Model: instructions are executed contiguously without concurrency. [1]

Properties of RAM

Step Execution of Times

RAM concerns common real-world instructions executed at constant times:

  1. Arithmetic:

    • Add

    • Subtract

    • Multiply

    • Divide

    • Remainder

    • Floor

    • Ceiling

  2. Data Movement

    • Loading

    • Storing

    • Copying

  3. Control flow

    • Conditionals and unconditional branches

    • Subroutine calls

    • Returns

Data Types

Algorithmic Analysis within the RAM Model

Algorithm analysis: predicting the resources an algorithm requires.Computational time is what is commonly measured. Memory, hardware, or bandwidth are sometimes also analyzed. [1]

Running time: the number of basic operations executed in an algorithm. In the RAM model, each executed line takes the constant time ci.

Generally, time taken by an algorithm grows in proportion to the size of the input. [1] Definitions for input size depend on what is studied:

How To Cite

Zelko, Jacob. Random Access Machine (RAM) Model. https://jacobzelko.com/01072021072613-random-access-model. January 7 2021.

References

[1] T. H. Cormen, Ed., Introduction to algorithms, 3rd ed. Cambridge, Mass: MIT Press, 2009.

Discussion:

CC BY-SA 4.0 Jacob Zelko. Last modified: May 19, 2024. Website built with Franklin.jl and the Julia programming language.