A27228 No calculator allowed in this examination

School of Computer Science
Fourth Year Undergraduate/Postgraduate
21933
Fundamentals: Introduction to Computer Science
Main Summer Examinations 2019
Time allowed: 1:30
[Answer all questions]
– 1 – Turn Over
No calculator
Note
This paper consists of THREE questions. Answer ALL questions. Each question will be
marked out of 20. The paper will be marked out of 60, which will be rescaled to a mark
out of 100.
Useful information
You might find the following information useful in answering some of the questions.
iJVM instruction set
Mnemonic Operands Description
BIPUSH constant Push constant onto stack
GOTO
label name or
line number
Unconditional jump
HALT N/A Halt the simulator
IADD N/A Pop two words from stack; push their sum
IFEQ
label name or
line number
Pop elem from stack and branch if it is zero
IFLT
label name or
line number
Pop elem from stack and branch if it is less than
zero
IFGT
label name or
line number
Pop elem from stack and branch if it is greater
than zero
IF ICMPEQ
label name or
line number
Pop two elements from stack and branch if they
are equal
IINC
variable name,
byte
Add a constant value to a local variable
ILOAD variable name Push local variable onto stack
ISTORE variable name Pop word from stack and store in local variable
ISUB N/A
Pop two words from stack; subtract the top word
from the second to top word, push the answer;
– 2 – Turn OverA27228
No calculator
LMC instruction set
NOTE: The operand ‘xx’ below can be either a variable or a label.
Mnemonic Operands Description
ADD xx
Add the value stored at xx to whatever value is
currently on the accumulator.
SUB xx
Subtract the value stored at xx from whatever
value is currently on the accumulator.
STA xx Store the contents of the accumulator to xx.
LDA xx
Load the value from xx and enter it in the
accumulator.
BRA xx
Set the program counter to the given address
(value xx). That is, value xx will be the next
instruction executed.
BRZ xx
If the accumulator contains the value 000, set the
program counter to the value xx. Otherwise, do
nothing.
BRP xx
If the accumulator is 0 or positive, set the
program counter to the value xx. Otherwise, do
nothing.
INP N/A
fetch the value from the user, and put it in the
accumulator
OUT N/A Output the value of the accumulator
HLT N/A Halt
DAT DATA
This is an assembler instruction which loads the
value into the next available memory location.
DAT can also be used in conjunction with labels
to declare variables.
– 3 – Turn OverA27228
No calculator
Question 1
(a) Convert the following decimal numbers to binary and hexadecimal. Clearly show all
working.
(i) 73
(ii) 32
[4 marks]
(b) This question requires you to use the answer from each sub-part in the next part.
(i) Represent the following numbers using a binary system wherein numbers are
represented in 6-bits. The first bit is used as the sign bit and negative numbers
are represented using 2’s complement.
i. -12
ii. + 8
[2 marks]
(ii) Add the two numbers from the previous section in binary. Clearly show all
working. [3 marks]
(iii) Show that the result obtained in the previous section is indeed correct by per-
forming the same operation in decimal and showing that the result is the same
as in binary. [3 marks]
[8 marks]
(c) Write an assembly language program for the toy LCM assembler that takes three
numbers (a, b, c) as input and prints the sum of the last two numbers (b+c) if the
first (a) is greater than 10 or prints the difference between the last two numbers
(b-c) if the first (a) is less than or equal to 10. [8 marks]
– 4 – Turn OverA27228
No calculator
Question 2
(a) Briefly describe the purpose of the Java Virtual Machine with specific emphasis on
the need for such a system and the problems it solves.
[4 marks]
(b) The Java Virtual Machine makes use of a stack to track its internal operations. This
stack is called the “Operand Stack” and is why the JVM is called a Stack Machine.
Describe the use of this stack with a relevant (but short) example. [8 marks]
(c) This question relates to the Reverse Polish Notation and consists of two parts:
(i) Convert the following infix expression to the Reverse Polish Notation. Clearly
show the contents of any data structures (i.e. Stack, Queue, . . . ) that you
make use of:
5 + 3 ∗ 6 ∗ (8 ∗ 2 + 1)
[5 marks]
(ii) Now evaluate the value of the postfix expression you generated in the previous
section and confirm that this value is the same as when the infix expression
(provided in the previous section) is evaluated. You do not have to illustrate the
contents of the stack after every step - just when an operation is performed.
[3 marks]
[8 marks]
– 5 – Turn OverA27228
No calculator
Question 3
(a) Describe any TWO kinds of errors that could occur in programs with a brief example
of each.
[4 marks]
(b) The following table provides you with a list of functions and their corresponding
complexity when they are provided with an input array of length n:
Function Name Complexity
f1 O(n)
f2 O(n2)
f3 O(log(n))
f4 O(1)
What is the complexity of the following function f5 when the length of the array
“inArray” is n? Justify your answer.
public static void f5( int [] inArray ) –
f1( inArray );
f2( inArray );
for( int i = 0; i ¡ inArray.length; i++ ) –
f3( inArray );
˝
f4( inArray );
˝
[4 marks]
(c) Write an iJVM code snippet that performs the same operations as the following Java
code snippet. Include comments to show which Java statement is being executed
by which sections of your iJVM code.
Continued Overleaf
– 6 – Turn OverA27228
Question 3 continued No calculator
NOTES:
• In addition to writing the program, ensure that you provide adequate comments
to describe the working of your program.
• You might find the iJVM statements listed at the start of this exam paper
useful for this task.
• Assume that you also have access to a single iJVM statement “PRT” that will
pop and print the top value on the iJVM stack
int current˙number = 1 ;
int end = 10 ;
int sum = 0 ;
while( current˙number ¡= end ) –
sum += current˙number ;
current˙number += 1 ;
˝
System.out.println( sum );
[12 marks]
– 7 – Turn OverA27228

Do not complete the attendance slip, fill in the
front of the answer book or turn over the
question paper until you are told to do so



Important Reminders

• Coats/outwear should be placed in the designated area.

• Unauthorised materials (e.g. notes or Tippex) must be placed in the
designated area.

• Check that you do not have any unauthorised materials with you
(e.g. in your pockets, pencil case).

• Mobile phones and smart watches must be switched off and
placed in the designated area or under your desk. They must not
be left on your person or in your pockets.

• You are not permitted to use a mobile phone as a clock. If you have
difficulty seeing a clock, please alert an Invigilator.

• You are not permitted to have writing on your hand, arm or other
body part.

• Check that you do not have writing on your hand, arm or other body
part – if you do, you must inform an Invigilator immediately

• Alert an Invigilator immediately if you find any unauthorised item
upon you during the examination.

Any students found with non-permitted items upon their person
during the examination, or who fail to comply with Examination
rules may be subject to Student Conduct procedures.

A27228 Fundamentals: Introduction to Computer Science