代写 CS1S 2022、代写Java，Python编程

日期：2023-05-07 01:55

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]