This assignment is divided in two parts. First part deals with analysis of algorithms. Second part is a programming assignment.

Part I

Analyse the following fragments of code. Formulate exact expressions for the running time of each code fragment.

1. (a)

   Sum = 0;
for(int i = 0; i < N; i++)
    Sum++;

   (b)

   Sum = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
        Sum++;

2. (a)

   Sum = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < N*N; j++)
        Sum++;

   (b)

   Sum = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < i; j++)
        Sum++;

3. (a)

   Sum = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < i*i; j++)
        for(int k = 0; k < j; k++)
            Sum++;

   (b)

   Sum = 0;
for(int i = 1; i <= N; i++)
    for(int j = 1; j <= i*i; j++)
        if(j % i == 0)
            for(int k = 0; k < j; k++)
                Sum++;

4. Formulate expressions for the running time of code fragments in (1), (2), and (3) assuming that a constant time (one unit time) is required to perform each operation.

Part II

This is a fairly long description. But it is not a difficult one. The length of the description is attributed to the rigorous specification of the problem statement which will eventually simplify the task of coding.

Your task is to implement a RAM (Random Access Machine) simulator.

Specification of the Random Access Machine

The RAM consists of an input tape, an output tape, a program store, a program counter and memory. Input tape is read-only, while output tape is write-only. The following figure is a schematic diagram of the RAM.

The input tape contains a sequence of signed integers. Once an integer is read, the input tape pointer advances to next integer. The output tape is initially blank. Once an integer is written on the output tape, the output pointer advances to next consecutive empty slot. Once an integer is written to the output tape, it cannot be erased.

Memory is arranged as sequence of registers. Each register can hold an integer. The register '0' is special register. It is known as Accumulator. Accumulator is an implicit operand for many instructions of the RAM. The size of the memory is essentially infinite. That means it can hold as much data as a program normally requires.

The program for RAM is stored in a separate storage. It is not writable. That means a program cannot change itself. A "Program Counter" keeps track of the current instruction. It is incremented after the execution of each instruction (except for the jump instructions which may modify it in some other way).

The instruction set of the RAM is as follows.

The action taken by the RAM for executing each instruction is given in the table below.

Note:
c(i) means contents of register i. Hence c(0) is the Accumulator.
v(i) means value of operand i, which is defined as follows.
 v(=i) = i (i is an immediate operand)
 v(i)  = c(i) (i is a register operand)
 v(*i) = c(c(i)) (i is an indirect operand)

Coding Specifications

As in the previous assignment, you have to implement an interface. This time the interface contains a single method that will essentially emulate the RAM. You may download the interface file by clicking here,

The signature of the method is as follows.
  public void execute(int program[][], int inputTape[], int outputTape[]);

The method, when invoked, will execute the instructions in program[ ][ ], read inputTape[ ] if needed, and write on outputTape[ ] if needed. The method returns when the machine halts. The input tape pointer and output tape pointer are set to zero when the machine starts execution.

The instruction format is as follows:
Each instruction is an array of 3 integers. The first element represents the OpCode for the instruction, the second element denotes operand type which is either 0 (for register operand), 1 (for immediate operand, i.e. '='), or 2 (for indirect operand, i.e. '*'). The third element is the operand value.

For example the instruction STORE *5 will be encoded as

A program, therefore, is a N*3 array of integers.

You may assume that the memory size is 100 registers (you may assume larger values than that but dont make it smaller than 100). Program Counter is initialized to zero when the machine starts. Sometimes an instruction cannot be executed due to one or more of following reasons

1. illegal OpCode, (e.g. 20)
2. illegal operand, (as in STORE =i)
3. undefined operation (such as divide by zero)

On occurence of such conditions, the current (faulty) instruction is to be treated as a HALT instruction.

What you are NOT supposed to do

Do not modify the interface file. It is read-only for you. :)

Some clarifications regarding RAM specification.

For JUMP/JGTZ/JZERO assume that the operand (i.e. 'b') is an immediate operand. Ignore the operand type field in the instruction triple.
For example see the following program... (All numbers are in decimal)

which will be translated to

In the last instruction (JUMP) it doesnt matter what value you put in place of '0', just ignore that value. The label for JUMP is encoded as the index at which the label appears in the program array (in the case above, that index is 2; program starts at index 0)

Pick up a sample RAM program here. Detailed description of the program is given in the same file. Use this to test your RAM implementation.

For Part I, write your solutions on paper and submit them to the M.Tech(CSE)Ist yr. CS201 TAs.

Be sure to put your Name and Roll No on the paper you submit.

For guidelines about how to submit the Part II, click here.

Please name your RAM implementation class file (as well the class it contains) according to your roll number. e.g. If your roll number is Y0002, name your file as "Y0002.java".