Teacher answer key

Algorithms with State

Gather four kinds of evidence: prediction of relevant state; behavior across varied cases including boundaries; explanation using trace/state evidence; and a reasoned correction of one mismatch. Mark each as emerging, with support or independent using paper or your school’s existing approved process. A challenge pass is machine-behavior evidence, not proof of authorship or complete mastery. Accept equivalent correct programs; the public key is a model, not the only possible answer.

Public teaching material. Solutions are examples; equivalent correct programs may also pass the actual checks.

16. Factorial and Loop Invariants

Use a multiplicative accumulator and explain why 0! is 1.

Open this lesson →

1. Predict and trace

Before running the Try program, predict its output and trace the first three executed instructions. Track the relevant registers, flags or memory as needed. Then step the program to compare.

LOAD 4 R1
LOAD 1 R2
LOOP 4
LOAD R2
MUL R1
COPY R0 R2
LOAD R1
SUB 1
COPY R0 R1
RETURN
LOAD R2
PRINT
HALT

Queue input: None

Initialize memory: All bytes initially zero

Try prediction key

Output: 24

Instruction	PC before	PC after	Relevant state	Output
LOAD	0	1	`{"registers":[0,4,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	None
LOAD	1	2	`{"registers":[0,4,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	None
LOOP	2	3	`{"registers":[0,4,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[{"start":2,"end":9,"remaining":4,"callDepth":0}],"memoryReads":[],"memoryWrites":[]}`	None

2. Build and check

Read N from 0 through 6 and print N!. Use a loop and a multiplication accumulator.

Required instruction types: INPUT, LOOP, MUL

Example challenge solution

INPUT
COPY R0 R1
COPY R0 R3
LOAD 1 R2
LOOP R3
LOAD R2
MUL R1
COPY R0 R2
LOAD R1
SUB 1
COPY R0 R1
RETURN
LOAD R2
PRINT
HALT

Actual checker fixtures

Case 1

Input: 0
Initial memory: All bytes initially zero
Expected output: 1

Case 2

Input: 4
Initial memory: All bytes initially zero
Expected output: 24

Case 3

Input: 6
Initial memory: All bytes initially zero
Expected output: 720

3. Explain the machine

Why does the product accumulator start at1?

Reasoning and teaching note

1 is multiplication's identity; zero iterations yield 0!=1. Starting0 would make every product0.

17. The Fibonacci Sequence

Keep two previous values and update them in a safe order.

Open this lesson →

1. Predict and trace

Before running the Try program, predict its output and trace the first three executed instructions. Track the relevant registers, flags or memory as needed. Then step the program to compare.

LOAD 1 R1
LOAD 1 R2
LOOP 8
LOAD R1
PRINT
ADD R2
COPY R2 R1
COPY R0 R2
RETURN
HALT

Queue input: None

Initialize memory: All bytes initially zero

Try prediction key

Output: 1, 1, 2, 3, 5, 8, 13, 21

Instruction	PC before	PC after	Relevant state	Output
LOAD	0	1	`{"registers":[0,1,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	None
LOAD	1	2	`{"registers":[0,1,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[]}`	None
LOOP	2	3	`{"registers":[0,1,1,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[{"start":2,"end":8,"remaining":8,"callDepth":0}],"memoryReads":[],"memoryWrites":[]}`	None

2. Build and check

Read N from 0 through 8. Print the first N Fibonacci values, starting 1, 1. Print nothing for N = 0.

Required instruction types: INPUT, LOOP, ADD, COPY

Example challenge solution

INPUT
COPY R0 R4
LOAD 1 R1
LOAD 1 R2
LOOP R4
LOAD R1
PRINT
ADD R2
COPY R2 R1
COPY R0 R2
RETURN
HALT

Actual checker fixtures

Case 1

Input: 0
Initial memory: All bytes initially zero
Expected output: None

Case 2

Input: 1
Initial memory: All bytes initially zero
Expected output: 1

Case 3

Input: 6
Initial memory: All bytes initially zero
Expected output: 1, 1, 2, 3, 5, 8

Case 4

Input: 8
Initial memory: All bytes initially zero
Expected output: 1, 1, 2, 3, 5, 8, 13, 21

3. Explain the machine

Why can replacing the first prior value too early break Fibonacci?

Reasoning and teaching note

It loses a still-needed operand; use a temporary/live result before shifting the pair. Correct start is 1,1.

18. Reverse a Memory Buffer

Copy a buffer backward using source and destination pointers.

Open this lesson →

1. Predict and trace

Before running the Try program, predict its output and trace the first three executed instructions. Track the relevant registers, flags or memory as needed. Then step the program to compare.

STORE 1 0
STORE 2 1
STORE 3 2
STORE 4 3
LOAD 3 R1
LOAD 16 R2
LOOP 4
LOAD [R1]
STORE R2
LOAD R1
SUB 1
COPY R0 R1
LOAD R2
ADD 1
COPY R0 R2
RETURN
HALT

Queue input: None

Initialize memory: 0: 1, 1: 2, 2: 3, 3: 4

Try prediction key

Output: None

Instruction	PC before	PC after	Relevant state	Output
STORE	0	1	`{"registers":[0,0,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[0]}`	None
STORE	1	2	`{"registers":[0,0,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[1]}`	None
STORE	2	3	`{"registers":[0,0,0,0,0,0,0,0],"flags":{"zero":false,"negative":false,"overflow":false},"sp":255,"stack":[],"callStack":[],"loopStack":[],"memoryReads":[],"memoryWrites":[2]}`	None

2. Build and check

Four bytes are seeded at addresses 0–3. Copy them in reverse order into addresses 16–19, leaving the originals unchanged. Use a loop and register addresses; no output is required.

Required instruction types: LOOP, LOAD, STORE

Example challenge solution

LOAD 3 R1
LOAD 16 R2
LOOP 4
LOAD [R1]
STORE R2
LOAD R1
SUB 1
COPY R0 R1
LOAD R2
ADD 1
COPY R0 R2
RETURN
HALT

Actual checker fixtures

Case 1

Input: None
Initial memory: 0: 1, 1: 2, 2: 3, 3: 4
Expected output: None
Expected final memory: 0: 1, 1: 2, 2: 3, 3: 4, 16: 4, 17: 3, 18: 2, 19: 1
Required memory reads: 0, 1, 2, 3

Case 2

Input: None
Initial memory: 0: 8, 1: 0, 2: 255, 3: 2
Expected output: None
Expected final memory: 0: 8, 1: 0, 2: 255, 3: 2, 16: 2, 17: 255, 18: 0, 19: 8
Required memory reads: 0, 1, 2, 3

Case 3

Input: None
Initial memory: 0: 7, 1: 7, 2: 9, 3: 9
Expected output: None
Expected final memory: 0: 7, 1: 7, 2: 9, 3: 9, 16: 9, 17: 9, 18: 7, 19: 7
Required memory reads: 0, 1, 2, 3

3. Explain the machine

Is this an in-place reversal? What must remain unchanged?

Reasoning and teaching note

No; it reverse-copies source0..3 to destination16..19. Source stays1,2,3,4; destination4,3,2,1.