1

ㅡ Faculty of Computer Science

43
 Introduction

The study of algorithms is at the very heart of computer science.

Therefore, to analyze the performance of an algorithm some model of computation is necessary.

There are several computer models which are simple enough to establish analytical results.

These models include the random access machine (RAM), the random access stored program

machine (RASP) , Turing machine and some specialized of these.

2
ㅡ Faculty of Computer Science
43
3
ㅡ Faculty of Computer Science
43
 Lesson Goals

1 To discuss about the RAM model and RAM instructions

To discuss the basic concepts of Pidgin ALGOL and explain how the Pidgin ALGOL
2
programs translate into the RAM programs

To analyze the time and space complexities of a RAM program by uniform cost and
3
logarithmic cost

4
ㅡ Faculty of Computer Science
43
 Random Access Machine (RAM) Model

RAM model is a theoretical computational model used in computer science for the purpose of
analyzing algorithms.
One-accumulator computer in which instructions are not permitted to modify themselves.
RAM consists of

Read-only input tape

Write-only output tape
Program
Memory

5
ㅡ Faculty of Computer Science
43
 Random Access Machine (RAM) Model(Cont’d)

x1 x2 ... xn Read only input tape

r0 Accumulator
r1
Location r2
Program
counter
r3
..
.
Memory

y1 y2 ... Write only output tape

6
ㅡ Faculty of Computer Science
43
 Random Access Machine (RAM) Model(Cont’d)

Read-Only Input Tape

The input tape is a sequence of squares each of which holds an integer.

Whenever a symbol is read from the input tape, the tape head moves one square to the right.

Write-Only Output Tape

The output is a write-only tape ruled into squares which are initially all blank.
When a write instruction is executed, an integer is printed in the square of the output tape that is
currently under the output tape head and the tape head is moved one square to the right.
Once an output symbol has been written , it cannot be changed.

7
ㅡ Faculty of Computer Science
43
 Random Access Machine (RAM) Model(Cont’d)

Memory

The memory consists of a sequence of registers, r0, r1, …, ri, …, each of which is capable of

holding an integer of arbitrary size.

We place no upper bound on the number of registers that can be used.

This abstraction is valid in case where:

The size of the problem is small enough to fit in the main memory of a computer.
The integers used in the computation are small enough to fit in one computer word.

8
ㅡ Faculty of Computer Science
43
 Random Access Machine (RAM) Model(Cont’d)

Program

The program for a RAM is not stored in the memory. So, the program does not modify itself.
The program is merely a sequence of (optionally) labeled instructions.
Program instructions are:
Arithmetic instructions
Input-output instructions
Indirect addressing
Branching instructions.

All computation takes place in the first register r0, called accumulator, which like every other
memory register can hold an arbitrary integer.

9
ㅡ Faculty of Computer Science
43
 RAM Instructions

Each instruction consists of two part: an operation code and an address.

No Operation Code Address
1 LOAD operand
2 STORE operand
3 ADD operand
4 SUB operand
5 MULT operand
6 DIV operand
7 READ operand
8 WRITE operand
9 JUMP label
10 JGTZ label
11 JZERO label
10 12 HALT
ㅡ Faculty of Computer Science
43
 RAM Instructions (Cont’d)

An operand can be one of the following:

=i , indicating the integer i itself.
A nonnegative integer i, indicating the contents of register i.
*i, indicating indirect addressing.

To specify the meaning of an instruction we define v(a), the value of operand a, as follows:

v(=i) = i,
v(i) = c(i),
v(*i) = c(c(i)).

11
ㅡ Faculty of Computer Science
43
 RAM Instructions (Cont’d)

Initially, c(i) = 0 for i ≥ 0, the location counter is set to the first instruction in program P, and

the output tape is blank.

After execution of the kth instruction in a program P, the location counter is automatically set

to k+1 (i.e., the next instruction), unless the kth instruction is JUMP, HALT, JGTZ, or JZERO.

12
ㅡ Faculty of Computer Science
43
 Meaning of RAM Instructions

The operand a is either =i, i, or *i.

No Instruction Meaning
1 LOAD a c(0) v(a)
2 STORE i c(i) c(0)
STORE *i c(c(i)) c(0)
3 ADD a c(0) c(0)+v(a)
4 SUB a c(0) c(0)-v(a)
5 MULT a c(0) c(0)*v(a)
6 DIV a c(0) c(0)/v(a)
7 READ i c(i)current input symbol
READ *i c((c(i))current input symbol. The input tape head moves one
square right in either case.
13
ㅡ Faculty of Computer Science
43
 Meaning of RAM Instructions(Cont’d)

No Instruction Meaning
8 WRITE a v(a) is printed on the square of the output tape currently under the
output tape head. Then the tape head is moved one square right.

9 JUMP b The location counter is set to the instruction labeled b.

10 JGTZ b The location counter is set to the instruction labeled b if c(0)> 0; other
wise, the location counter is set to the next instruction.

11 JZERO b The location counter is set to the instruction labeled b if c(0)=0; other
wise, the location counter is set to the next instruction.

12 HALT Execution ceases.

14
ㅡ Faculty of Computer Science
43
 Pidgin ALGOL

In order to describe algorithms more clearly, we shall use a high-level language called Pidgin
ALGOL. Random Access Stored Program machine
A Pidgin ALGOL program can be translated into a RAM or RASP program in a straightforward
manner.
Pidgin ALGOL is unlike any conventional programming language in that it allows the use of any
type mathematical statement as long as its meaning is clear and the translation into RAM or
RASP code is evident.
Similarly, the language does not have a fixed set of data types.
Variables can represent integers, strings, and arrays. Additional data types such as sets, graphs,
lists, and queues can be introduced is needed.

15
ㅡ Faculty of Computer Science
43
 Some Statement Types of Pidgin ALGOL Program

Assignment statement: variable ← expression

if statement: if condition then statement else statement

while statement: while condition do statement

repeat statement: repeat statement until condition

for statement: for variable ← initial-value step step-size until final-value do statement

comment statement: comment comment

16
ㅡ Faculty of Computer Science
43
 Some Statement Types of Pidgin ALGOL Program(Cont’d)

read statement: read variable

write statement: write expression

label statement: label: statement

goto statement: goto label

block statement: begin

statement; statement;
...
statement; statement
end

17
ㅡ Faculty of Computer Science
43
 Examples for Pidgin ALGOL and RAM Programs

Example 1
begin
Consider the function f(n) given by read r1;
if r1 ≤ 0 then write 0
nn for all integers n>=1, else
f(n) = begin
0 otherwise r2  r1;
Write a pidgin ALGOL program and RAM program. r3  r1-1;
while r3 > 0 do
begin
r2  r2*r1;
r3  r3-1
Pidgin ALGOL Program for nn
end;
write r2
end
end
18
ㅡ Faculty of Computer Science
43
 Examples for Pidgin ALGOL and RAM Programs (Cont’d)

RAM Program for nn

begin Corresponding Pidgin
RAM program
read r1; ALGOL statement
if r1 ≤ 0 then write 0 READ 1 read r1
else
LOAD 1
begin
r2  r1; JGTZ pos if r1 ≤ 0 then write 0
r3  r1-1; WRITE =0
while r3 > 0 do JUMP endif
begin
pos: LOAD 1
r2  r2*r1; r2  r1
r3  r3-1 STORE 2
end;
LOAD 1
write r2
end SUB =1 r3  r1-1
end STORE 3
19
ㅡ Faculty of Computer Science
43
 Examples for Pidgin ALGOL and RAM Programs (Cont’d)
RAM Program for nn
Corresponding Pidgin
begin RAM program
ALGOL statement
read r1;
while: LOAD 3
if r1 ≤ 0 then write 0
JGTZ continue while r3 > 0 do
else
begin JUMP endwhile
r2  r1; continue: LOAD 2
r3  r1-1; MULT 1 r2  r2*r1
while r3 > 0 do
STORE 2
begin
r2  r2*r1; LOAD 3
r3  r3-1 SUB =1 r3  r3-1
end; STORE 3
write r2 JUMP while
end
endwhile: WRITE 2 write r2
end
20 endif: HALT
ㅡ Faculty of Computer Science
43
 Examples for Pidgin ALGOL and RAM Programs (Cont’d)

Example 2 Pidgin ALGOL program for Recognizing Strings

with Equal Numbers of 1’s and 2’s
Consider a program that accepts the language over the
begin
input alphabet {1,2} consisting of all strings with the
d 0;
same number of 1’s and 2’s. The program reads each
read x;
input symbol into register 1 and in register 2 keeps
while x ≠ 0 do
track of the difference d between the number of 1’s
begin
and 2’s. When the end marker 0 is encountered, the
if x ≠ 1 then d d-1
program checks that the difference is zero, and if so
else dd+1;
prints 1 and halts. We assume that 0,1 and 2 are the
read x
only possible input symbols.
end;
Write a Pidgin ALGOL program and a RAM program.
if d=0 then write 1
21 end
ㅡ Faculty of Computer Science
43
 Examples for Pidgin ALGOL and RAM Programs (Cont’d)

RAM Program for Recognizing Strings with Equal Numbers of 1’s and 2’s
begin
Corresponding Pidgin
d 0; RAM program
ALGOL statement
read x; LOAD =0
STORE 2 d 0
while x ≠ 0 do
begin READ 1 read x
while: LOAD 1
if x ≠ 1 then d d-1
JZERO endwhile while x ≠ 0 do
else dd+1;
LOAD 1
read x if x ≠ 1
SUB =1
end; JZERO one
if d=0 then write 1 LOAD 2
end SUB =1 then d d-1

STORE 2
22
ㅡ Faculty of Computer Science
43
 Examples for Pidgin ALGOL and RAM Programs (Cont’d)

RAM Program for Recognizing Strings with Equal Numbers of 1’s and 2’s
begin
Corresponding Pidgin
d 0; RAM program
ALGOL statement
read x; JUMP endif
while x ≠ 0 do one: LOAD 2
ADD =1 else dd+1
begin
if x ≠ 1 then d d-1 STORE 2
endif: READ 1 read x
else dd+1;
JUMP while
read x
endwhile: LOAD 2
end; JZERO output
if d=0 then write 1
if d=0 then write 1 HALT
end output: WRITE =1
HALT
23
ㅡ Faculty of Computer Science
43
 Computational Complexity of RAM Programs

Worst-case complexity
The worst-case time complexity of a RAM program is the function f(n) which is the
maximum, over all inputs of size n , of the sum of the time taken by each instruction
executed.

Expected complexity

If the complexity is taken as the “average” complexity over all inputs of given size, then the
complexity is called the expected complexity.

24
ㅡ Faculty of Computer Science
43
 Computational Complexity of RAM Programs(Cont’d)

To specify the time and space complexity exactly, we must specify the time required to

execute each RAM instruction and the space used by each register.

Two cost criteria for RAM programs

Uniform cost criterion

Logarithmic cost criterion

25
ㅡ Faculty of Computer Science
43
 Uniform Cost Criterion

Uniform Cost Time Complexity

each RAM instruction requires one unit of time

Uniform Cost Space Complexity

each RAM register requires one unit of space

26
ㅡ Faculty of Computer Science
43
 Logarithmic Cost Criterion

Let L(i) be the following logarithmic function on the integers:

Logarithmic cost of an operand Operand a Cost t(a)

=i l(i)

i l(i) + l(c(i))

*i l(i) + l(c(i)) + l(c(c(i)))

27
ㅡ Faculty of Computer Science
43
 Logarithmic Cost of RAM Instructions

No Instruction Cost No Instruction Cost

1 LOAD a t(a) READ i l(input) + l(i)

7
READ *i l(input) + l(i) + l(c(i))
STORE i l(c(0)) + l(i)
2
STORE *i l(c(0)) + l(i) + l(c(i)) 8 WRITE a t(a)

3 ADD a l(c(0)) + t(a) 9 JUMP b 1

4 SUB a l(c(0)) + t(a) 10 JGTZ b l(c(0))

5 MULT a l(c(0)) + t(a) 11 JZERO b l(c(0))

6 DIV a l(c(0)) + t(a) 12 HALT 1

t(a) is the cost of operand a, and b denotes a label.

28
ㅡ Faculty of Computer Science
43
 Logarithmic Cost of RAM Instructions(Cont’d)

Example Consider the cost of instruction ADD *i.

First we must determine the cost of decoding the operand represented by the address.

To examine the integer i requires time l(i).

Then to read c(i), the contents of register i, requires time l(c(i)).

Finally, reading the contents of register c(i) costs l(c(c(i))).

Since the instruction ADD *i adds the integer c(c(i)) to c(0), a reasonable cost is l(c(0)) + l(i) +

l(c(i)) + l(c(c(i))).

29
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Uniform Cost

Time Complexity Maximum number of instructions in main loop

Space Complexity Number of registers used

Logarithmic Cost

Time Complexity Sum of the cost in each iteration of main instruction

Space Complexity Largest integer stored in memory register

30
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Pidgin ALGOL Program for nn

Uniform Cost Space Complexity
begin
read r1;
The number of registers used = 4 registers
if r1 ≤ 0 then write 0
else Space complexity S(n) = O(1)
begin
r2  r1;
r3  r1-1;
while r3 > 0 do Uniform Cost Time Complexity
begin
r2  r2*r1;
1 MULT instruction = 1 unit of time
r3  r3-1
end; n-1 MULT instruction = n-1 unit of time
write r2
Time complexity T(n) = O(n)
end
end
31
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Pidgin ALGOL Program for nn

begin
read r1;
if r1 ≤ 0 then write 0 Logarithmic Cost Space Complexity
else
begin
r2  r1; Largest integer stored in memory register = nn
r3  r1-1;
while r3 > 0 do Space complexity = log nn = n log n = O(n log n)
begin
r2  r2*r1;
r3  r3-1
end;
write r2
end
end
32
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Pidgin ALGOL Program for nn Logarithmic Cost Time Complexity

begin 1st MULT instruction = n * n = n2

read r1; 2nd MULT instruction = n2 * n = n3
if r1 ≤ 0 then write 0 3rd MULT instruction = n3 * n = n4
else ...
begin
ith MULT instruction = ni * n = ni+1
r2  r1;
r3  r1-1; Time complexity of ith instruction = log ni+1 = (i+1) log n
while r3 > 0 do 𝑛−1
begin Total time complexity = ෍ (i+1) log n
r2  r2*r1;
𝑖=1
r3  r3-1
= 2 log n + 3 log n + … + n log n
end;
write r2 = ( 2 + 3 + … + n) log n
𝑛 −1 (𝑛+2)
end =( ) log n
2
end = ½ n2 log n + ½ n log n - log n = O(n2 log n)
33
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Pidgin ALGOL Program for Recognizing Assume n is the length of the input string.
Strings with Equal Numbers of 1’s and 2’s
Uniform Cost Space Complexity
begin
d 0 The number of registers used = 3 registers
read x; Space complexity S(n) = O(1)
while x ≠ 0 do
begin
if x ≠ 1 then d d-1 Uniform Cost Time Complexity
else dd+1;
read x
1 ADD/SUB instruction = 1 unit of time
end;
n ADD/SUB instruction = n unit of time
if d=0 then write 1
end Time complexity T(n) = O(n)
34
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Pidgin ALGOL Program for Recognizing

Strings with Equal Numbers of 1’s and 2’s
Assume n is the length of the input string.

begin
d 0 Logarithmic Cost Space Complexity
read x;
while x ≠ 0 do Largest integer stored in memory register = n
begin
if x ≠ 1 then d d-1 Space complexity = log n = O(log n)
else dd+1;
read x
end;
if d=0 then write 1
end
35
ㅡ Faculty of Computer Science
43
 Uniform Cost and Logarithmic Cost of a RAM Program

Logarithmic Cost Time Complexity

Pidgin ALGOL Program for Recognizing
Strings with Equal Numbers of 1’s and 2’s 1st ADD instruction = 0+1=1
2nd ADD instruction = 1+1=2
begin 3rd ADD instruction = 2+1=3
d 0 ...
read x; ith ADD instruction = (i-1) + 1 = i
while x ≠ 0 do Time complexity of ith instruction= log i
begin 𝑛

if x ≠ 1 then d d-1 Total time complexity = ෍ log i

else dd+1; 𝑖=1

read x = log 1 + log 2 + log 3 + … + log n

end; = log ( 1 * 2 * 3 * … * n)
if d=0 then write 1
= log (n!) ≈ n log n = O(n log n)
end
36
ㅡ Faculty of Computer Science
43
 Exercises for RAM

Give Pidgin ALGOL programs and RAM programs and analyze the time and space complexities
of your answers under (a) the uniform cost and (b) the logarithmic cost.

Compute n! given input n.

Accept all inputs of the form 1n2n2 0
Prime
nn by addition

37
ㅡ Faculty of Computer Science
43
 Exercises for RAM

1. Compute n! given input n.

begin
read n;
f  1;
while n>0 do
begin
f  f*n;
n  n-1
end;
write f
end

38
ㅡ Faculty of Computer Science
43
 Exercises for RAM
2
[Link] all inputs of the form 1n2n 0.
begin
d1  0; d2  0; read r1;
if r1  1 then write 0
else
begin
while r1=1 do
begin
d1  d1+1; read r1
end;
if r1  2 then write 0
else
begin
while (r1 =2) do
begin
d2  d2+1; read r1
end;
if r1=0 and d2=d1*d1 then write 1
else write 0
end
end
39 end
ㅡ Faculty of Computer Science
43
 Exercises for RAM

3. Prime
begin
d  2;
read n;
if n>1 then
begin
while n % d  0 do
begin
d  d+1
end;
if n=d then write 1
else write 0
end
else write 0
end

40
ㅡ Faculty of Computer Science
43
 Exercises for RAM

4. nn by addition
begin
read n; result  n; i  n-1;
while i>0 do
begin
temp  result;
j  n-1;
while j>0 do
begin
result result + temp;
j j-1
end;
i i-1
end;
write result
end

41
ㅡ Faculty of Computer Science
43
 The RAM model and RAM instructions
The basic concepts of Pidgin ALGOL
how to write the Pidgin ALGOL programs
how the Pidgin ALGOL programs translate into the RAM programs
How to measure the performance of the RAM programs
Uniform cost complexity
Logarithmic cost complexity

42
ㅡ Faculty of Computer Science
43
 Approximate Form Using Stirling’s Formula

43
ㅡ Faculty of Computer Science
43