CS502 Fundamentals of Algorithms Assignment 1 Solution Fall 2013

Question 1:  (5 Marks)

What are the characteristics of Random Access Machine? Briefly write down any two characteristics.


Random Access Machine is a favorite model of a sequantial ‘ computer. Its main features are:

1. Computation unit with a user defined program.’

2. Read-only inputtape and write-only output tape.

3. Unbounded number of local memory cells.

4. Each memory cell is capable of holdingan integer of unbounded size.

5. Instruction set includes operations for moving data between memory cells, comparisons and conditional branches, and simple arithmetic operations.

6. Execution starts with the first instruction and ends when a HALT instruction is executed.

7. All operations take unit time regardless of the lengths of operands.

8. Time complexity = the number of instructions executed. 9. Space complexity = the number of memory cells accessed.


Question 2:                          

(5 Marks)

Using “Figure 3.2: Merge sort: combine phase: in handouts (at Page No.29) as a model, illustrate the operation of Merge sort algorithm (for ascending sort) on the following new array input.

A = { 8 , 33 , 31, 14, 2, 0, 19 , 30 }