COMPSCI 110 Cheatsheet · Introduction to Computer Systems

01 · Exam map course.json · brief

“An A4-cheat sheet (typed or handwritten) can be brought into the exam hall.” (COMPSCI 110 exam revision slides, Semester Two 2026)

Scope Final weighting: OS 8 marks; Compilers 7; Security 6; Turing 6; Networks 5; AI 5; Binary 4; Logic, Organisation and Assembly 3 each. Spend time in that order, but bank every mechanical mark.

02 · Binary toolkit M1 · CH 1

Signed representations

03 · Logic → circuit M2 · CH 2

NOT flips 0↔1. NAND and NOR are functionally complete; tie their inputs together to make NOT. An n-input table has 2ⁿ rows.

Hardware rules

Exam move From a supplied truth table: circle every output-1 row; write all variables in each AND term; bar only the 0 inputs; OR every term. Simplify only if asked.

04 · Stored-program machine M3 · CH 3

Von Neumann: one memory holds instructions and data; subsystems are Memory, I/O, ALU and Control Unit; CPU = ALU + CU. Shared sequential traffic causes the bottleneck. Fetch preserves; store overwrites.

05 · Assembly / machine code M4 · CH 4

Use supplied Figure 6.5: lookup → 12-bit address → concatenate → hex nibbles. Arithmetic uses one register R and 16-bit two's complement.

Desk-check / assemble

1. After every line record R, changed memory and GT/EQ/LT.
2. .BEGIN/.END/.DATA are directives; LABEL: .DATA 0 binds an address.
3. Pass 1 builds label→address; pass 2 inserts opcodes/addresses and emits words. This resolves forward labels.

Trap Do not “remember” an opcode when Figure 6.5 is supplied. Read it; then keep opcode in the top nibble and pad the operand to exactly 12 bits.

06 · Network calculations M6 · CH 6

07 · Compiler decision chain M7 · CH 7 · 7 marks

Tokenise under pressure

1. Scan left→right. Take the longest valid token.
2. Classify: keyword; identifier/symbol; operator; bracket; number; literal; terminator/symbol.
3. Discard spaces and comments. == is one operator token and differs from assignment =.
4. Count the list. An illegal arrangement still tokenises; the parser rejects its grammar later. A misplaced else remains a keyword.

BNF: productions expand non-terminals into terminals/non-terminals. A parse tree is valid only if its leaves match the token stream and its root reaches the grammar's goal symbol. Syntax asks whether the form is legal; semantics asks whether that legal form makes sense.

Mark check If the prompt says “scanner”, do not repair syntax. If it says “parser”, use the supplied grammar. If it says “semantic”, discuss meaning/type/name records, not punctuation.

09 · OS scheduling M8 · CH 8 · 8 marks

A context switch saves PC, registers and resource handles, then loads the next process. Useful work pauses. If arrival times are not all zero, do not use the shortened waiting formula without accounting for arrival.

OS managers: process, memory, device, file and network managers plus the command interpreter. The ready queue holds runnable processes; the waiting queue holds processes blocked on an event or I/O.

Deadlock decision

Trap A process merely waiting for I/O is not deadlocked. Deadlock is permanent circular waiting: each holds something the next needs and none can proceed.

10 · Cryptography chooser M9 · CH 9 · 6 marks

Caesar: 25 shifts + preserved frequencies ⇒ brute force/frequency attack. Matrix blocks add diffusion.

11 · Turing trace M10 · CH 10 · 6 marks

1. Record state + symbol; choose the unique matching rule.
2. Write field 3; go to state 4; move field 5.
3. No match ⇒ HALT; repeating a configuration indicates a loop.

Valid: no duplicate (state,symbol) left sides. Church–Turing: any effectively computable function is Turing-computable; thesis, not theorem.

12 · AI concept distinctions M11 · CH 11 · 5 marks

Trap Turing tests behaviour, not inner mechanism; Winograd tests meaning, not grammar alone.

13 · Worked: −9 in 5-bit two's complement M1 · worked example

Question: represent −9, verify with +9, and state the signed range.

1. +9: 01001₂.
2. Invert: 10110₂.
3. Add 1: 10111₂, so this encodes −9.
4. Verify: 01001 + 10111 = 1 00000; discard carry → 0. Range = −2⁴…2⁴−1 = −16…+15.

Trap 10110 is one's complement, off by one. The range is asymmetric: −16 exists but +16 does not.

14 · Worked: SOP from a table M2 · worked example

1. Select rows 00, 01, 11 because Y=1.
2. Write one AND term per row, barring each 0 input.
3. OR all terms: (¬A·¬B) + (¬A·B) + (A·B).
4. Optional check: first two terms = ¬A; result simplifies to ¬A + B and reproduces 1,1,0,1.

Trap Do not bar the 1s; bar the 0s. Do not omit an output-1 row. A combinational circuit depends only on current inputs; an SR latch stores state.

15 · Binary micro-checks M1 · body text

16 · Worked: assembly → machine M4 · worked example

Given: Y at address 13; THREE at 14; X at 12. Translate LOAD Y · ADD THREE · STORE X · HALT.

1. Lookup opcodes: LOAD 0000; ADD 0011; STORE 0001; HALT 1111.
2. Write 13, 14, 12 as 12-bit addresses; no-operand HALT uses zeros.
3. Join 4+12 bits. Group into nibbles only after the 16-bit word is complete.

Trap Addresses are values 13, 14, 12, not the values stored in Y, THREE and X.

17 · Worked: field sizing M3 · worked example

Machine: 16-bit IR, 16 instructions, 16 registers. Can OPCODE REG1 REG2 REG3 fit?

1. 16 operations: 2⁴=16 → opcode = 4 bits.
2. 16-bit word − 4 = 12 operand bits.
3. 16 registers: 2⁴=16 → each register field = 4 bits.
4. 4-bit opcode + three 4-bit registers = 16 bits: fits exactly.

18 · Fetch trace scaffold M3 · body text

19 · Worked: link delay + bottleneck M6 · worked example

Given: L=3 Mbit; R=1.5 Mbps; distance=3000 km; s=2×10⁸ m/s; later link=1 Mbps.

1. d_trans = L/R = 3×10⁶ bits ÷ 1.5×10⁶ bits/s = 2 s.
2. 3000 km = 3×10⁶ m. d_prop = d/s = 3×10⁶ ÷ 2×10⁸ = 0.015 s = 15 ms.
3. Nodal delay also includes processing and queueing.
4. Path throughput = minimum link rate = 1 Mbps.

Queueing varies with congestion; processing checks the packet and selects its output link.

Trap Throughput is never the sum of link rates. Improving a non-bottleneck link changes nothing.

20 · Worked: lexical analysis M7 · worked example

if (a == b) answer = 42;

1. Ignore whitespace/comments.
2. Scan left-to-right, longest token first.
3. Classify each token; count = 10.
4. Do not claim lexical analysis proves valid syntax; only parsing does.

Compiler trap table

21 · Worked: Round-Robin M8 · worked example

Given: all arrive at 0; A=200 ms, B=100 ms, C=300 ms; quantum=100 ms; queue A,B,C; ignore switching.

1. Take at most one quantum from queue head.
2. If unfinished, append to queue tail; if finished, remove.
3. Read completion times only after the timeline is correct.
4. For simultaneous arrival, subtract burst from completion.

Trap B finishes after its first slice; do not return it to the queue. C takes consecutive final slices only because nobody else remains.

22 · Scheduling + deadlock checks M8 · topic map

Resource-arrow grammar

State order: CREATE → READY → RUN → FINISH, with RUN↔WAIT when I/O blocks/unblocks. Ready processes can run; waiting processes cannot until their event completes.

23 · Worked: matrix cipher GO → UU M9 · worked example

Given: A=0…Z=25; V=[6 14] for GO; M=[[3,5],[2,3]]; arithmetic mod 26.

1. G=6 and O=14, so V=[6 14].
2. V·M = [6·3+14·2, 6·5+14·3] = [46,72].
3. 46 mod 26=20; 72 mod 26=20 → [20,20].
4. 20=U, so ciphertext=UU. Decrypt with M′: [20 20]·M′ mod 26=[6 14]=GO.

Trap Keep row-vector orientation V·M. Both outputs use both input letters: that diffusion is the point.

24 · Worked: Turing complement M10 · worked example

Rules: (1,0,1,1,R) and (1,1,0,1,R). Start state 1 on leftmost symbol of …b 1 0 1 b….

Trap Tuple field 3 is the symbol written; field 4 is next state. The head move occurs after the write/state change.

25 · Security fast recall M9 · topic map

26 · Worked: Winograd reasoning M11 · worked example

“The trophy doesn't fit in the suitcase because it is too big.”

1. Grammar permits trophy or suitcase.
2. Commonsense says the too-big object fails to fit: “it” = trophy.
3. Change “big” to “small” and the referent flips to suitcase: meaning, not syntax, resolves it.

Turing test: a text judge cannot reliably distinguish machine from person; this tests behaviour, not mechanism. Neural net: weighted, layered units; forward pass predicts; back-propagation sends error backward to adjust weights. No numeric calculation here.

27 · Method chooser all final modules

28 · Final error scan faq + study strategies

Last pass Mechanical questions reward visible method. Preserve the fixed width, operand order, units, queue order, matrix orientation and head position so a small slip cannot propagate unseen.