Summer Diet -1- CS1S 2022 Solutions
CS1S Computer Systems: Questions and Solutions
May 2022
Duration: 1 hour
Rubric: Answer all questions
This examination is worth a total of 50 marks
1. (a) Convert 1010 0110 to a decimal number, assuming binary representation.
[2]
Calculate 128 + 32 + 4 + 2 = 166 by adding the powers of 2 corresponding to the
positions where there is a 1 bit in the word.
[Problem solving. 1 mark for correct powers of 2, 1 mark for adding them]
(b) Convert 1010 0110 to a decimal number, assuming two’s complement
representation.
[3]
Since the leftmost bit is 1, this is a negative number. Negate it to get a nonnegative
number. To negate, first invert it, giving 0101 1001. Then increment it, giving 0101
1010. Now this result is nonnegative, so its binary representation is the same as its two’s
complement value; this is 64 + 16 + 8 + 2 = 90. Since the negation of the original word
is 90, the answer is -90.
[Problem solving. 1 mark for identifying it as negative; 1 mark for inverting and 1 mark
for adding 1 and getting the correct result.]
(c) Translate the statement a := b * (c-d) into Sigma16 assembly language, assuming
that a, b, c, d are signed integer variables. You do not need to write a complete
program, and you don’t need to write data statements for the variables. Just
translate this one statement.
[3]
load R1,b[R0]
load R2,c[R0]
load R3,d[R0]
sub R4,R2,R3
mul R5,R1,R4
store R5,a[R0]
[Problem solving, requires understanding usage of registers, variables, and basic
instructions. 1 mark for loads, 1 mark for store, 1 mark for arithmetic.]
Summer Diet -2- CS1S 2022 Solutions
(d) Consider the following program:
load R1,mod[R0]
load R2,instr[R1]
add R2,R2,R1
store R2,instr[R0]
lea R4,4[R0]
lea R5,2[R0]
instr add R3,R0,R0
store R3,out[R0]
trap R0,R0,R0
mod data 0
out data 0
Hand-execute the above program and report the final value of the out variable for the
following values of mod (remember the following RRR operation codes: add 0; sub 1; mul
2; div 3):
- mod = 0
- mod = $0045
- mod = $1045
- mod = $2045
Explain what behaviour the code of this program is displaying, and in particular with the
instruction with the instr label.
Explain what kind of major problems this type of program can lead to when executed.
Explain why this type of program is not recommended in terms of software engineering.
[8]
Values of out: 0.5 mark for each correct value
- 0 (mod left instr as it is, i.e. R3=0+0)
- 6 (mod modified instr into R3=R4+R5)
- 2 (mod modified instr into R3=R4-R5)
- 8 (mod modified instr into R3=R4*R5)
The code is an example of self-modifying code: the program, once stored in memory,
can be modified itself through instructions. [2 marks]
A major potential problem is that a program may go haywire or lead to unpredictable
behaviour e.g. not reaching end states or jumping to other code sections [2 marks]
From a software engineering standpoint, self-modifying code is difficult to document,
read, maintain, and debug [2 marks]
[Bookwork, problem-solving and critical thinking]
Summer Diet -3- CS1S 2022 Solutions
(e) Consider two arrays named x and y that both contain n integers, where n is an
integer variable in memory. Write a Sigma16 assembly language program that
calculates the dot product of the two array and stores this sum in the variable
dotprod (i.e. dotprod := x0.y0 + x1.y1 + x2.y2 + …. + xn-1.yn-1). The program
must work correctly for any nonnegative n and initial array elements. Don’t
forget to appropriately document your code with comments. You may assume
that the variables have been declared but not initialised. Your program should
exit cleanly.
[9]
; Possible solution:
; R1 = constant 1
; R2 = i
; R3 = n
; R4 = dotprod
; R5, R6 used for temporary calculations
; Initialize the variables
lea R1,1[R0] ; R1 := 1
lea R2,0[R0] ; R2 := i := 0
load R3,n[R0] ; R3 := n
lea R4,0[R0] ; R4 := dotprod := 0
loop
; if not (i cmp R2,R3 ; compare i, n
jumpge done[R0] ; if not (i
; dotprod := dotprod + x[i] * y[i]
load R5,x[R2] ; R5 := x[i]
load R6,y[R2] ; R6 := y[i]
mul R5,R5,R6 ; R5 := x[i]*y[i]
add R4,R4,R5 ; dotprod := dotprod + x[i]*y[i]
; i := i + 1
add R2,R2,R1 ; i := i + 1
; goto loop
jump loop[R0] ; goto loop
done
store R4,dotprod[R0] ; store result
trap R0,R0,R0 ; terminate
[Problem solving, requires understanding of the instruction set, conditionals, indexed
addressing and loops. 2 marks for initialization, 2 marks for loop, 1 mark for arithmetic,
1 marks for conditional, 1mark for storing to dotprod, and 1 mark for termination.]
Summer Diet -4- CS1S 2022 Solutions
2. (a) Define the behaviour of a 1-bit multiplexer circuit (the mux1 circuit): detail how
many inputs are used by the circuit and how many outputs the circuit provides,
Write the truth table of the mux1 circuit. Explain how the multiplexer circuit
enables the creation of complex programs.
[3]
The mux1 circuit takes three inputs: x, y, c (control signal), and has one output (out).
A multiplexer is used to implemented conditional logic in digital circuits. If c=0, then
out=x, else out=y.
[Bookwork. 1 mark for variables, 1 mark for behaviour, 1 mark for truth table/circuit]
(b) Design a circuit that produces the following truth table for inputs x, y, z and
output o. Draw the corresponding schema for the circuit.
[2]
[Bookwork. 2 marks for the diagram]
Summer Diet -5- CS1S 2022 Solutions
(c) Consider a synchronous circuit with a gate delay of 1ms and a critical path of 20
logic gates. What is the maximum value of the clock speed? What could happen
if we use a higher clock speed?
[4]
The clock needs to wait 20ms at least: so the clock speed is at the most 50Hz.
If we used a higher clock speed, signals going through the critical path will not have had
time to stabilise and therefore the output will not correspond to the defined circuit
function.
[Bookwork. 2 marks for the right clock speed answer. 2 marks for explaining the
behaviour of the circuit with a higher clock speed.]
(d) Consider a personal banking system used to record series of expenses on
customers’ bank accounts. To store the transactions, a linked list data structure is
used for each customer. Each node in that list contains three fields: value, an
unsigned integer containing the amount being debited from the account,
account_id, an unsigned integer used to identify the other party of the
transaction (e.g. a store charging the customer for a purchase) and next, a
pointer to the next node in the list.
i) Discuss the pros and cons of using a linked list to store these transactions instead
of using an array.
[3]
An array would take less storage space: with linked lists, we need to store pointers to the
next elements. An array would allow to reach a given transaction faster (random access).
It would require prespecifying an array size, which could lead to complications if
growing too large, or unused space if too much storage is reserved.
[Bookwork. 3 marks maximum, 1 mark for each correct comment on the following
topics: storage space per element; array fixed size vs linked lists not specifying a max
size; random access]
ii) Write a high-level program that traverses the linked list and calculates the total
amount of money spent at one store, given a pointer p pointing to the linked list
containing transactions of the individual, and a binary number store representing
the identification number of that store and corresponding to one of the numbers
present in the account_id field of transactions.
[3]
Summer Diet -6- CS1S 2022 Solutions
sum := 0
while p /= nil do {
if store == (*p).account_id then {
sum := sum + (*p).amount
}
p := (*p).next
}
[Problem-solving. 1 point for correct while loop, 1 point for conditional, 1 point for
correct usage of pointers.]
iii) Translate this high-level language program to a low-level language. (The low
level language contains assignment statements, goto statements, and statements of
the form if b then goto label, where b is a Boolean expression.)
[3]
sum := 0
loop:
if (*p).next == 0 then goto done
if (*p).account_id /= store then goto skip
sum := sum + (*p).amount
skip:
p := (*p).next
goto loop
done: terminate
[Problem-solving. 1 point for correct while loop termination condition, 1 point for
correct conditional skip depending on account_id, 1 point on correct usage of pointers.]
iv) Translate this low-level program to a Sigma16 program.
[7]
; R1 = p (given)
; R2 = store (given)
; R3 = sum
; R4 = temp *p.accout_id
; R5 = temp *p.value
add R3,R0,R0 ; sum := 0
loop
cmp R1,R0 ; compare p with nil
jumpeq done[R0] ; if p = nil then goto done
load R4,1[R1] ; R4 := (*p).account_id
cmp R4,R2 ; compare account_id with store
jumpneq skip[R0] ; if wrong id then goto skip
load R5,0[R1] ; R5 := (*p).value
add R3,R3,R5 ; sum := sum + (*p).value
Summer Diet -7- CS1S 2022 Solutions
skip
load R1,1[R1] ; p := (*p).next
jump loop[R0] ; goto loop
done
store R3,sum[R0] ; sum := R3
trap R0,R0,R0 ; terminate
[Problem solving. 1 mark for comparing p to nil, 1 mark for jump to end condition if p is
nil, 1 mark for dereferencing (*p).account_id, 1 mark for comparing (*p).account_id to
store, 1 mark for skipping if unequal, 1 mark for adding value to sum if equal, 1 mark for
store and trap upon end condition]