National
Computing Challenge
National
Computing Challenge
Embedded Files
Computing Challenge
2025 Computing Contest and Solutions - Gr 5 - 12
2025 Computing Contest and Solutions - Gr 5 - 12
Question 1: RGB Mixing
Question 1: RGB Mixing
Colors are made up of three values: Red, Green, and Blue (RGB). Combining different amounts of red, green, and blue can create many different colors.
To find the average color when mixing two or more colors, follow these steps:
For each color component (Red, Green, and Blue), find the average of the values.
Once you have the average for each component, you create a new color by putting together these averages for Red, Green, and Blue.
For Example:
Color 1: (254, 175, 75)
Color 2: (170, 35, 35)
To find the new color, first calculate:
The average of all the Red values
R3 = (R1 + R2) / 2 = (254 + 170) / 2 = 212
The average of all the Green values
G3 = (G1 + G2) / 2 = (175 + 35) / 2 = 105
The average of all the Blue values
B3 = (B1 + B2) / 2 = (75 + 35) / 2 = 55
Therefore, the new color has the values (212, 105, 55).
Question: Given the three colors below, find the resultant color, in the (R, G, B) format, when mixing them:
Color 1: (0, 102, 0)
Color 2: (0, 115, 154)
Color 3: (255, 128, 128)
Color 4: (___, ___, ___)
Solution
Solution
Correct Answer: Red: 85, Green: 115, Blue: 94
Explanation:
The average of all the Red values
R4 = (R1 + R2 + R3) / 3 = (0 + 0 + 255) / 3 = 85
The average of all the Green values
G4 = (G1 + G2 + G3) / 3 = (102 + 115 + 128) / 3 = 115
The average of all the Blue values
B4 = (B1 + B2 + B3) / 3 = (0 + 154 + 128) / 3 = 94
Question 2: Compression / RLE
Question 2: Compression / RLE
Run-Length Encoding (RLE) is a method of compressing (reducing) the size of data, including sequences of characters called strings.
Example:
Original string: "HHHHHAAAAHZZZ"
Compressed string using RLE: "5H4A1H3Z"
Question: You have the following strings that need to be compressed using Run-Length Encoding:
1. AAAAABBCDEEEEEFFFFFGGGGGHHHHHHHH
2. AAABBBCCCDDDEEEFFF
3. AAAAAAAAABBBBBBBBBAAAAAAAAACCCDDEEF
4. ABCDEFGHI
a) Which string compresses to the smallest size?
A) 1
B) 2
C) 3
D) 4
b) Which string has the best compression ratio i.e. the string where the fraction of compressed size/original size is the smallest?
A) 1
B) 2
C) 3
D) 4
Solution
Solution
Correct Answers:
2a. B) 2
2b. C) 3
Breakdown:
AAAAABBCDEEEEEFFFFFGGGGGHHHHHHHH → 5A2B1C1D5E5F5G8H
Original Length: 32, Compressed Length: 16, Compression Ratio: 50.0%
AAABBBCCCDDDEEEFFF → 3A3B3C3D3E3F
Original Length: 18, Compressed Length: 12, Compression Ratio: 66.66666666666666%
AAAAAAAAABBBBBBBBBAAAAAAAAACCCDDEEF → 9A9B9A3C2D2E1F
Original Length: 35, Compressed Length: 14, Compression Ratio: 40.0%
ABCDEFGHI → 1A1B1C1D1E1F1G1H1I
Original Length: 9, Compressed Length: 18, Compression Ratio: 200.0%
Question 3: Binary Search Tree Insertion
Question 3: Binary Search Tree Insertion
A binary search tree (BST) is a way to organise numbers using a tree structure.
When we insert a new number into a BST, we follow this process:
Start at the root node.
Compare the new number to the current node’s number.
If the new number is smaller, go to the left branch.
If it is larger, go to the right branch.
Repeat step 2 until you reach a spot where there is no node yet (an empty branch) where the new number can go.
Insert the new number there.
Example
To insert the value 13 into the following BST:
12
/ \
8 17
/ \ /
5 10 15
Start at the root node: 12. Since 13 > 12, go to the right branch.
At node 17. Compare: 13 < 17, so go to 17’s left branch.
Node 17’s left branch has 15. Compare: 13 < 15, so go to 15’s left branch.
15’s left branch is empty → that is where 13 is inserted.
The tree now looks like this:
12
/ \
8 17
/ \ /
5 10 15
/
13
Question
25
/ \
18 35
/ \ / \
12 22 30 42
\
33
In the BST above, which of the following is the correct place to insert the new number 29?
A) To the right of 22
B) To the left of 30
C) To the left of 35
D) To the right of 33
Solution
Solution
Correct Answer: B) To the left of 30
Explanation:
Start at the root: 29 > 25 → go right to 35.
Compare to 35: 29 < 35 → go left to 30.
Compare to 30: 29 < 30 → go left.
There is no node left of 30, so that’s where 29 is inserted.
Question 4: Inheritance
Question 4: Inheritance
To determine the features of a specific item, one has to consider the features from the sources that it
inherits these from. The specific item gets all the features from the source and can also have its own
unique features.
A base class is like a general category.
A subclass is a more specific type within that category.
The subclass inherits attributes (features) and methods (actions) from the class above it.
Example:
Vehicle is a base class. It is a general category.
All vehicles can move() and stop().
Car is subclass of Vehicle. It is a specific type of vehicle.
Inherits move() and stop() from Vehicle.
Adds its own actions: honk() and playRadio().
Bicycle is also a subclass of Vehicle. It is another type of vehicle.
Inherits move() and stop() from Vehicle.
Adds its own action: ringBell().
ElectricCar is a specific type of car. It is a subclass of Car.
Inherits move(), stop(), honk(), and playRadio() from Car and Vehicle.
Adds its own feature: batteryLevel.
Adds its own action: chargeBattery().
Review the following diagram...
Question: Given the diagram above, tick off all boxes corresponding to attributes and methods belonging to and inherited by the class Songbird.
age
name
wingspan
eat()
bark()
fetch()
fly()
layEggs()
sing()
sleep()
swim()
Solution
Solution
Correct Answer:
age
name
wingspan
eat()
fly()
layEggs()
sing()
sleep()
Explanation:
Songbird is a subclass of Bird which in turn is a subclass of Animal, so Songbird inherits features and actions from both classes while introducing a unique action of its own.
Inherits name, age, eat(), and sleep() from Animal.
Inherits wingspan, fly(), and layEggs() from Bird.
Adds its own action: sing().
Question 5: Postfix Notation
Question 5: Postfix Notation
In postfix notation, an operator (such as +, -, ×, etc.) comes after the two numbers as opposed to between them (infix notation). For example:
In infix notation, you write: 3 + 4
In postfix notation, you write: 3 4 +
Example:
5 3 4 + × 2 -
To solve it:
1. Consider the first operator, +, which applies to the two numbers immediately before it, which are 3 and 4. Add them:
3 + 4 = 7
7 replaces 3 4 +. The expression becomes: 5 7 × 2 -
2. The next operator is ×, and it applies to the two numbers immediately before it, which are 5 and 7, so multiply them:
5 × 7 = 35
35 replaces 5 7 ×. The expression becomes: 35 2 -
3. Finally, subtract 2 from 35:
35 - 2 = 33
The value of 5 3 4 + × 2 - is 33.
Question: What is the value of the expression below?
6 2 3 + × 4 -
A) 22
B) 26
C) 24
D) 20
Solution
Solution
Correct Answer: B) 26
Explanation:
Read left to right until you find an operator. The first operator is +, and it applies to the two numbers immediately before it: 2 and 3.
Compute: 2 + 3 = 5
Replace 2 3 + with 5, so the expression becomes:
6 5 × 4 −
The next operator is ×, which applies to the two numbers just before it: 6 and 5.
Compute: 6 × 5 = 30
Replace 6 5 × with 30, so the expression becomes:
30 4 −
Finally, the operator − applies to 30 and 4.
Compute: 30 − 4 = 26
Question 6: Markov Chain
Question 6: Markov Chain
A Markov chain is a way to predict what might happen next based on a current situation. The table below demonstrates how weather can be predicted given the current weather and on the roll of a six-sided die.
Example
If today is Cloudy and you roll a 5 on a six-sided die, according to table, you can predict that the
weather tomorrow will be sunny:
Cloudy → roll 5 → Tomorrow will be Sunny.
Continuing this chain, using the prediction that tomorrow will be Sunny, you roll the die again to predict the day after tomorrow:
Sunny → roll 3 → The day after tomorrow will be Cloudy.
Question 6 a): It is Monday morning and the weather is Sunny. Using the table above and his six-sided die, Mark wants to predict the weather for the next week (including next Monday). On Monday, he rolls the dice once for each day of the coming week.
This is the sequence of his dice rolls:
3, 6, 4, 5, 2, 6, 1
According to the table and the dice-sequence, what will Mark's prediction for next Monday’s weather be?
A) Sunny
B) Cloudy
C) Rainy
Question 6 b): In his predictions for the seven days, how many days are predicted to be Sunny?
A) 1
B) 2
C) 3
D) 4
Solution
Solution
Correct Answers:
6a. C) Rainy
6b. C) 3
Breakdown:
Question 7: Bubble Sort
Question 7: Bubble Sort
Bubble sort is a simple way to sort a list of numbers through a series of passes, which involves swaps until the list is sorted, from smallest to largest.
Here’s an example:
Start with the list:
5, 3, 8, 1, 4
Pass 1:
Start at the left of the list and work your way to the right:
Compare 5 and 3. Since 5 is greater than 3 → swap. → 3, 5, 8, 1, 4
Compare 5 and 8. Since 5 is less than 8 → no swap → 3, 5, 8, 1, 4
Compare 8 and 1. Since 8 is greater than 1 → swap → 3, 5, 1, 8, 4
Compare 8 and 4. Since 8 is greater than 4 → swap → 3, 5, 1, 4, 8
Pass 2
Go back to the start of the revised list from Pass 1 ( 3, 5, 1, 4, 8).
Repeat the swap process:
Compare 3 and 5 → no swap → 3, 5, 1, 4, 8
Compare 5 and 1 → swap → 3, 1, 5, 4, 8
Compare 5 and 4 → swap → 3, 1, 4, 5, 8
Compare 5 and 8 → no swap → 3, 1, 4, 5, 8
Pass 3:
Go back to the start of the revised list from Pass 2 (3, 1, 4, 5, 8).
Repeat the swap process:
Compare 3 and 1 → swap → 1, 3, 4, 5, 8
Compare 3 and 4 → no swap → 1, 3, 4, 5, 8
Compare 4 and 5 → no swap → 1, 3, 4, 5, 8
Compare 5 and 8 → no swap → 1, 3, 4, 5, 8
At this point, the list is fully sorted: 1, 3, 4, 5, 8 .
In this example, it took 3 passes to sort.
Question: (three parts)
Use bubble sort to organize the sequence below, from least to greatest:
7, 2, 9, 4, 6, 1
7. a) How many swaps are made in the first pass?
A) 1
B) 2
C) 3
D) 4
7. b) How many swaps are made in total?
A) 8
B) 9
C) 10
D) 11
7. c) How many passes does it take to sort this list?
A) 2
B) 3
C) 4
D) 5
Solution
Solution
Correct Answers:
7a. D) 4
7b. C) 10
7c. D) 5
Breakdown:
7, 2, 9, 4, 6, 1
Pass 1
Compare 7 and 2 → swap → 2, 7, 9, 4, 6, 1
Compare 7 and 9 → no swap → 2, 7, 9, 4, 6, 1
Compare 9 and 4 → swap → 2, 7, 4, 9, 6, 1
Compare 9 and 6 → swap → 2, 7, 4, 6, 9, 1
Compare 9 and 1 → swap → 2, 7, 4, 6, 1, 9
Pass 2
Compare 2 and 7 → no swap → 2, 7, 4, 6, 1, 9
Compare 7 and 4 → swap → 2, 4, 7, 6, 1, 9
Compare 7 and 6 → swap → 2, 4, 6, 7, 1, 9
Compare 7 and 1 → swap → 2, 4, 6, 1, 7, 9
Compare 7 and 9 → no swap → 2, 4, 6, 1, 7, 9
Pass 3
Compare 2 and 4 → no swap → 2, 4, 6, 1, 7, 9
Compare 4 and 6 → no swap → 2, 4, 6, 1, 7, 9
Compare 6 and 1 → swap → 2, 4, 1, 6, 7, 9
Compare 6 and 7 → no swap → 2, 4, 1, 6, 7, 9
Compare 7 and 9 → no swap → 2, 4, 1, 6, 7, 9
Pass 4
Compare 2 and 4 → no swap → 2, 4, 1, 6, 7, 9
Compare 4 and 1 → swap → 2, 1, 4, 6, 7, 9
Compare 4 and 6 → no swap → 2, 1, 4, 6, 7, 9
Compare 6 and 7 → no swap → 2, 1, 4, 6, 7, 9
Compare 7 and 9 → no swap → 2, 1, 4, 6, 7, 9
Pass 5
Compare 2 and 1 → swap → 1, 2, 4, 6, 7, 9
Compare 2 and 4 → no swap → 1, 2, 4, 6, 7, 9
Compare 4 and 6 → no swap → 1, 2, 4, 6, 7, 9
Compare 6 and 7 → no swap → 1, 2, 4, 6, 7, 9
Compare 7 and 9 → no swap → 1, 2, 4, 6, 7, 9
Question 8: Logic Gates
Question 8: Logic Gates
Logic gates are basic building blocks in electronics.
An AND gate produces an output of "1" only if all of its inputs are "1", otherwise its output is "0".
An OR gate produces an output of "1" if at least one of its inputs is "1", otherwise its output is "0".
Example:
How it works
On the left side you have four inputs, in two pairs:
Top pair: both inputs are 1 → connected into the first AND gate.
Bottom pair: first is 1, second is 0 → connected into the second AND gate.
The output from each of those AND gates then becomes an input to the single OR gate. So the OR gate has two inputs coming from those AND gates.
The output box of the OR gate is shown as 1.
Question:
Given the diagram above, which set of inputs will cause the final output to be 1?
A) A: 1, B: 1, C: 0, D: 1, E: 1, F: 0
B) A: 1, B: 1, C: 0, D: 0, E: 0, F: 1
C) A: 0, B: 1, C: 0, D: 0, E: 1, F: 1
D) A: 0, B: 1, C: 1, D: 1, E: 1, F: 0
Solution
Solution
Correct Answer: C) A: 0, B: 1, C: 0, D: 0, E: 1, F: 1
Diagram:
Question 9: Password Hashing / Hash Collision
Question 9: Password Hashing / Hash Collision
In computer science, a one-way password hashing algorithm changes a password into a special code, called a hash, that's hard to figure out backwards.
Here’s how this hashing algorithm works.
Example:
For the password “CAR”:
Convert each letter to its number in the alphabet:
C → 3, A → 1, R → 18.
Compute the sum of those numbers:
Sum = 3 + 1 + 18 = 22.
Write down each of those numbers in a row, next to each other, to make a long number:
Those numbers are 3, 1, and 18 → when you put them side by side, you get “3118”.
Add the sum (from step 2) to that long number (from step 3):
22 + 3118 = 3140.
Divide that total by 1000 and keep only the remainder:
When you divide 3140 by 1000, the remainder is 140.
So the final hash = 140.
However, sometimes different passwords can create the same hash. This is called a hash collision.
For example:
“GAP”, also hashes to 140 using exactly the same algorithm steps. Because they produce the same number (140) — it is considered a hash collision. Two different inputs → same output.
Question: Which two of the following passwords create a hash collision using the algorithm described above?
DATA
MOUSE
ENGINE
LEARNING
Solution
Solution
Correct Answer: DATA and LEARNING
Hash Values:
DATA - 227
MOUSE - 268
ENGINE - 199
LEARNING - 227
Question 10: STRIPS
Question 10: STRIPS
In planning problems we use a method called STRIPS to describe how one can plan a sequence of actions to go from a starting situation to a goal.
Scenario
A helper robot is locked inside a workshop. The robot must leave the workshop and carry a maintenance tool when it leaves. There are different ways it can do each part:
Initial (Problem) State:
Robot is in Workshop.
The door is locked.
Robot does not have the key.
The key is hidden somewhere in the workshop.
Robot does not have the tool.
The tool is hidden somewhere in the workshop.
Robot does not have key / tool printing material.
Goal (Required) State:
Robot is outside Workshop.
Robot has the tool.
The Goal State can be achieved through a sequence of actions, with each action bringing the robot closer to its goal. Each action takes a specific amount of time, so the robot should plan its actions so that it reaches its Goal State in the least amount of time.
The following table shows the actions, each of which is available under certain preconditions (conditions which need to be met in order to perform the action), so as to produce a result that gets the robot closer to its goal.
Available Actions (with their preconditions, results, and cost in minutes):
Example Plan:
If the robot chooses to search for the tool and then break the door, one possible plan is:
SearchForTool() → Cost = 7 min
BreakDoor() → Cost = 6 min
ExitWorkshop() → Cost = 1 min
Total cost = 14 minutes.
Question: What is the most efficient (minimum‑time) plan? Check all the actions below that are part of it.
SearchForKey()
SearchForTool()
LoadPrintingMaterial()
PrintKey()
PrintTool()
UnlockDoor()
BreakDoor()
ExitWorkshop()
Solution
Solution
Correct Answer:
LoadPrintingMaterial()
PrintTool()
BreakDoor()
ExitWorkshop()
Breakdown of Plans:
Search key, search tool, unlock door, exit
SearchForKey() = 5
SearchForTool() = 7
UnlockDoor() = 2
ExitWorkshop() = 1
→ Total = 5 + 7 + 2 + 1 = 15 min
Search key, load printing material, print tool, unlock door, exit
SearchForKey() = 5
LoadPrintingMaterial() = 2
PrintTool() = 2
UnlockDoor() = 2
ExitWorkshop() = 1
→ Total = 5 + 2 + 2 + 1 = 12 min
Load printing material, print key, search tool, unlock door, exit
LoadPrintingMaterial() = 2
PrintKey() = 5
SearchForTool() = 7
UnlockDoor() = 2
ExitWorkshop() = 1
→ Total = 2 + 5 + 7 + 2 + 1 = 17 min
Load printing material, print key, print tool, unlock door, exit
LoadPrintingMaterial() = 2
PrintKey() = 5
PrintTool() = 2
UnlockDoor() = 2
ExitWorkshop() = 1
→ Total = 2 + 5 + 2 + 2 + 1 = 12 min
Search tool, break door, exit
SearchForTool() = 7
BreakDoor() = 6
ExitWorkshop() = 1
→ Total = 7 + 6 + 1 = 14 min
Load printing material, print tool, break door, exit
LoadPrintingMaterial() = 2
PrintTool() = 2
BreakDoor() = 6
ExitWorkshop() = 1
→ Total = 2 + 2 + 6 + 1 = 11 min
Question 11: Data Alignment
Question 11: Data Alignment
A long beam is marked at equal intervals, 1 unit apart from each other: 0, 1, 2, 3, 4, 5,…
You are given the task of placing bricks of three possible lengths, 1-unit, 2-units, and 4-units, head-to-tail, in an assigned order, on this beam. After the bricks have been placed, the beam has to be cut at a marking at or beyond the final brick placed.
A 1-unit brick may begin at any marked position.
A 2-unit brick must begin at a position that is a multiple of 2 (0, 2, 4, 6,…).
A 4-unit brick must begin at a position that is a multiple of 4 (0, 4, 8, 12,…).
If at the end of one brick you are at position p, and it is not a multiple of the next brick’s size, then you must leave a gap until the next marking where the brick can be placed.
After all the bricks have been laid in order, the beam must be cut. The cut may only be made at or beyond the tail end of the last brick, and it must be at a multiple of the largest brick size used.
Example:
Refer to the diagram and steps below to understand the rules for placing bricks and cutting the beam for the given sequence of bricks:
1, 2, 4, 2, 1
The first brick, 1 unit long, is placed on the beam starting at 0 and ending at 1.
The next brick, 2 units long, needs to begin at a multiple of 2, so it can't be placed directly at marking 1. A 1-unit long gap is left so that the brick can be placed at marking 2. The 2-unit long brick is laid from markings 2 to 4.
The next brick, 4 units long, needs to begin at a multiple of 4, and 4 happens to be the next available marking on the beam. The 4-unit long brick is laid from markings 4 to 8.
The next brick, 2 units long, can be placed at marking 8 since this is a multiple of 2. It is laid from markings 8 to 10.
The final brick, 1 unit long, can be placed at marking 10. It is laid from markings 10 to 11.
Now that all the bricks have been laid, the beam must be cut. The rules state that the cut must be made at the earliest marking that is a multiple of the largest brick size used. Since the largest brick size used here is 4, the cut must be made at a multiple of 4. A 1-unit gap will be left from markings 11 to 12 so that the cut can be made at marking 12.
Placing this sequence of bricks required a beam 12 units in length.
Question: Given a sequence of bricks (in the exact order listed), which sequence gives the shortest beam length?
A) 1, 2, 1, 4, 2
B) 4, 2, 1, 1, 2, 1
C) 1, 4, 2, 4
D) 2, 1, 4, 1, 2, 1
Solution
Solution
Correct Answer: B) 4, 2, 1, 1, 2, 1
Diagram:
A)
B)
C)
D)
Question 12: Assembly (Part 1)
Question 12: Assembly (Part 1)
A computer has memory cells (like M1, M2, M3, …) that store numbers, and a special register called the accumulator (ACC) where calculations happen. At the start, ACC = 0. The computer runs a small set of instructions in assembly language—typically one at a time, from top to bottom—but sometimes the code will “jump” to another instruction instead of going in order. These instructions move numbers in and out of memory, and use ACC to do arithmetic.
Here are the example instructions you’ll use, along with what each one does:
Example
Initial memory:
M1 = 6
M2 = 5
M3 = 0
M4 = 0
Program:
[1] LOAD M1
[2] ADD 2
[3] SUB M2
[4] STORE M1
[5] IFNOTZERO M1 GOTO 2
[6] HALT
Step‐by‐step (Final answer: ACC = 0):
Question
Initial memory:
M1 = 1
M2 = 1
M3 = 0
M4 = 3
Program:
[1] LOAD M1
[2] ADD M2
[3] STORE M3
[4] LOAD M2
[5] STORE M1
[6] LOAD M3
[7] STORE M2
[8] LOAD M4
[9] SUB 1
[10] STORE M4
[11] IFNOTZERO M4 GOTO 1
[12] LOAD M2
[13] HALT
Question: When the program halts, what is the value in the accumulator (ACC)?
A) 5
B) 13
C) 3
D) 8
Solution
Solution
Correct Answer: A) 5
Breakdown:
Initial memory:
M1 = 1
M2 = 1
M3 = 0
M4 = 3
Program:
[1] LOAD M1
[2] ADD M2
[3] STORE M3
[4] LOAD M2
[5] STORE M1
[6] LOAD M3
[7] STORE M2
[8] LOAD M4
[9] SUB 1
[10] STORE M4
[11] IFNOTZERO M4 GOTO 1
[12] LOAD M2
[13] HALT
Step-by-step:
[1]: Copy the value from memory cell M1 into ACC.
M1 = 1
M2 = 1
M3 = 0
M4 = 3
ACC = 1
Next Line = 2
[2]: Add the value in memory cell M2 to ACC.
M1 = 1
M2 = 1
M3 = 0
M4 = 3
ACC = 2
Next Line = 3
[3]: Copy the value from ACC into memory cell M3.
M1 = 1
M2 = 1
M3 = 2
M4 = 3
ACC = 2
Next Line = 4
[4]: Copy the value from memory cell M2 into ACC.
M1 = 1
M2 = 1
M3 = 2
M4 = 3
ACC = 1
Next Line = 5
[5]: Copy the value from ACC into memory cell M1.
M1 = 1
M2 = 1
M3 = 2
M4 = 3
ACC = 1
Next Line = 6
[6]: Copy the value from memory cell M3 into ACC.
M1 = 1
M2 = 1
M3 = 2
M4 = 3
ACC = 2
Next Line = 7
[7]: Copy the value from ACC into memory cell M2.
M1 = 1
M2 = 2
M3 = 2
M4 = 3
ACC = 2
Next Line = 8
[8]: Copy the value from memory cell M4 into ACC.
M1 = 1
M2 = 2
M3 = 2
M4 = 3
ACC = 3
Next Line = 9
[9]: Subtract the literal value 1 from ACC.
M1 = 1
M2 = 2
M3 = 2
M4 = 3
ACC = 2
Next Line = 10
[10]: Copy the value from ACC into memory cell M4.
M1 = 1
M2 = 2
M3 = 2
M4 = 2
ACC = 2
Next Line = 11
[11]: If the value in memory cell M4 is not zero, jump to the instruction at line 1.
M1 = 1
M2 = 2
M3 = 2
M4 = 2
ACC = 2
Next Line = 1
[1]: Copy the value from memory cell M1 into ACC.
M1 = 1
M2 = 2
M3 = 2
M4 = 2
ACC = 1
Next Line = 2
[2]: Add the value in memory cell M2 to ACC.
M1 = 1
M2 = 2
M3 = 2
M4 = 2
ACC = 3
Next Line = 3
[3]: Copy the value from ACC into memory cell M3.
M1 = 1
M2 = 2
M3 = 3
M4 = 2
ACC = 3
Next Line = 4
[4]: Copy the value from memory cell M2 into ACC.
M1 = 1
M2 = 2
M3 = 3
M4 = 2
ACC = 2
Next Line = 5
[5]: Copy the value from ACC into memory cell M1.
M1 = 2
M2 = 2
M3 = 3
M4 = 2
ACC = 2
Next Line = 6
[6]: Copy the value from memory cell M3 into ACC.
M1 = 2
M2 = 2
M3 = 3
M4 = 2
ACC = 3
Next Line = 7
[7]: Copy the value from ACC into memory cell M2.
M1 = 2
M2 = 3
M3 = 3
M4 = 2
ACC = 3
Next Line = 8
[8]: Copy the value from memory cell M4 into ACC.
M1 = 2
M2 = 3
M3 = 3
M4 = 2
ACC = 2
Next Line = 9
[9]: Subtract the literal value 1 from ACC.
M1 = 2
M2 = 3
M3 = 3
M4 = 2
ACC = 1
Next Line = 10
[10]: Copy the value from ACC into memory cell M4.
M1 = 2
M2 = 3
M3 = 3
M4 = 1
ACC = 1
Next Line = 11
[11]: If the value in memory cell M4 is not zero, jump to the instruction at line 1.
M1 = 2
M2 = 3
M3 = 3
M4 = 1
ACC = 1
Next Line = 1
[1]: Copy the value from memory cell M1 into ACC.
M1 = 2
M2 = 3
M3 = 3
M4 = 1
ACC = 2
Next Line = 2
[2]: Add the value in memory cell M2 to ACC.
M1 = 2
M2 = 3
M3 = 3
M4 = 1
ACC = 5
Next Line = 3
[3]: Copy the value from ACC into memory cell M3.
M1 = 2
M2 = 3
M3 = 5
M4 = 1
ACC = 5
Next Line = 4
[4]: Copy the value from memory cell M2 into ACC.
M1 = 2
M2 = 3
M3 = 5
M4 = 1
ACC = 3
Next Line = 5
[5]: Copy the value from ACC into memory cell M1.
M1 = 3
M2 = 3
M3 = 5
M4 = 1
ACC = 3
Next Line = 6
[6]: Copy the value from memory cell M3 into ACC.
M1 = 3
M2 = 3
M3 = 5
M4 = 1
ACC = 5
Next Line = 7
[7]: Copy the value from ACC into memory cell M2.
M1 = 3
M2 = 5
M3 = 5
M4 = 1
ACC = 5
Next Line = 8
[8]: Copy the value from memory cell M4 into ACC.
M1 = 3
M2 = 5
M3 = 5
M4 = 1
ACC = 1
Next Line = 9
[9]: Subtract the literal value 1 from ACC.
M1 = 3
M2 = 5
M3 = 5
M4 = 1
ACC = 0
Next Line = 10
[10]: Copy the value from ACC into memory cell M4.
M1 = 3
M2 = 5
M3 = 5
M4 = 0
ACC = 0
Next Line = 11
[11]: If the value in memory cell M4 is not zero, jump to the instruction at line 1.
M1 = 3
M2 = 5
M3 = 5
M4 = 0
ACC = 0
Next Line = 12
[12]: Copy the value from memory cell M2 into ACC.
M1 = 3
M2 = 5
M3 = 5
M4 = 0
ACC = 5
Next Line = 13
[13]: Stop execution; the value currently in ACC is the final output.
M1 = 3
M2 = 5
M3 = 5
M4 = 0
ACC = 5
Steps taken = 35
Returned value = 5
Question 13: Assembly (Part 2)
Question 13: Assembly (Part 2)
The program below is intended to multiply M1 by M2 and return the product in the accumulator. However, two parts of the program are missing. These missing references are marked as {X} and {Y}.
Your task is to determine which memory cells should replace {X} and {Y} so that the program correctly computes the product.
Initial memory:
M1 = 4
M2 = 6
M3 = 0
M4 = 0
Program:
[1] IFZERO M2 GOTO 11
[2] STORE M3
[3] LOAD M3
[4] ADD M1
[5] STORE M3
[6] LOAD M2
[7] SUB 1
[8] STORE M2
[9] IFNOTZERO {X} GOTO 3
[10] LOAD {Y}
[11] HALT
13 a): Find {X}
A) M1
B) M2
C) M3
D) M4
13 b): Find {Y}
A) M1
B) M2
C) M3
D) M4
Solution
Solution
Correct Answers:
13a. B) M2
13b. C) M3
Explanation:
The program calculates the product of M1 and M2 by adding M1 with itself M2 times (i.e. 4 + 4 + 4 + 4 + 4 + 4). The result of this addition is stored in M3.
M2 can be thought of as a counter that "counts down" to the program stopping. Every time the program loops (jumps back to line 3), M1 (whose value is 4) gets added to M3, and the counter (M2) counts down by 1.
This counter needs to be checked at line 9 to evaluate if M1 has been added to M3 the correct number of times, so {X} must be M2.
When M2 finally reaches a value of 0, M3 contains the final sum, which happens to be the product of M1 and M2. Because ACC needs to hold this product before the program halts, M3 should be loaded at line 10, so {Y} is M3.
Breakdown of Completed Program:
Initial memory:
M1 = 4
M2 = 6
M3 = 0
M4 = 0
Program:
[1] IFZERO M2 GOTO 11
[2] STORE M3
[3] LOAD M3
[4] ADD M1
[5] STORE M3
[6] LOAD M2
[7] SUB 1
[8] STORE M2
[9] IFNOTZERO M2 GOTO 3
[10] LOAD M3
[11] HALT
Step-by-step:
[1]: If the value in memory cell M2 is zero, jump to the instruction at line 11.
M1 = 4
M2 = 6
M3 = 0
M4 = 0
ACC = 0
Next Line = 2
[2]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 6
M3 = 0
M4 = 0
ACC = 0
Next Line = 3
[3]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 6
M3 = 0
M4 = 0
ACC = 0
Next Line = 4
[4]: Add the value in memory cell M1 to ACC.
M1 = 4
M2 = 6
M3 = 0
M4 = 0
ACC = 4
Next Line = 5
[5]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 6
M3 = 4
M4 = 0
ACC = 4
Next Line = 6
[6]: Copy the value from memory cell M2 into ACC.
M1 = 4
M2 = 6
M3 = 4
M4 = 0
ACC = 6
Next Line = 7
[7]: Subtract the literal value 1 from ACC.
M1 = 4
M2 = 6
M3 = 4
M4 = 0
ACC = 5
Next Line = 8
[8]: Copy the value from ACC into memory cell M2.
M1 = 4
M2 = 5
M3 = 4
M4 = 0
ACC = 5
Next Line = 9
[9]: If the value in memory cell M2 is not zero, jump to the instruction at line 3.
M1 = 4
M2 = 5
M3 = 4
M4 = 0
ACC = 5
Next Line = 3
[3]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 5
M3 = 4
M4 = 0
ACC = 4
Next Line = 4
[4]: Add the value in memory cell M1 to ACC.
M1 = 4
M2 = 5
M3 = 4
M4 = 0
ACC = 8
Next Line = 5
[5]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 5
M3 = 8
M4 = 0
ACC = 8
Next Line = 6
[6]: Copy the value from memory cell M2 into ACC.
M1 = 4
M2 = 5
M3 = 8
M4 = 0
ACC = 5
Next Line = 7
[7]: Subtract the literal value 1 from ACC.
M1 = 4
M2 = 5
M3 = 8
M4 = 0
ACC = 4
Next Line = 8
[8]: Copy the value from ACC into memory cell M2.
M1 = 4
M2 = 4
M3 = 8
M4 = 0
ACC = 4
Next Line = 9
[9]: If the value in memory cell M2 is not zero, jump to the instruction at line 3.
M1 = 4
M2 = 4
M3 = 8
M4 = 0
ACC = 4
Next Line = 3
[3]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 4
M3 = 8
M4 = 0
ACC = 8
Next Line = 4
[4]: Add the value in memory cell M1 to ACC.
M1 = 4
M2 = 4
M3 = 8
M4 = 0
ACC = 12
Next Line = 5
[5]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 4
M3 = 12
M4 = 0
ACC = 12
Next Line = 6
[6]: Copy the value from memory cell M2 into ACC.
M1 = 4
M2 = 4
M3 = 12
M4 = 0
ACC = 4
Next Line = 7
[7]: Subtract the literal value 1 from ACC.
M1 = 4
M2 = 4
M3 = 12
M4 = 0
ACC = 3
Next Line = 8
[8]: Copy the value from ACC into memory cell M2.
M1 = 4
M2 = 3
M3 = 12
M4 = 0
ACC = 3
Next Line = 9
[9]: If the value in memory cell M2 is not zero, jump to the instruction at line 3.
M1 = 4
M2 = 3
M3 = 12
M4 = 0
ACC = 3
Next Line = 3
[3]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 3
M3 = 12
M4 = 0
ACC = 12
Next Line = 4
[4]: Add the value in memory cell M1 to ACC.
M1 = 4
M2 = 3
M3 = 12
M4 = 0
ACC = 16
Next Line = 5
[5]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 3
M3 = 16
M4 = 0
ACC = 16
Next Line = 6
[6]: Copy the value from memory cell M2 into ACC.
M1 = 4
M2 = 3
M3 = 16
M4 = 0
ACC = 3
Next Line = 7
[7]: Subtract the literal value 1 from ACC.
M1 = 4
M2 = 3
M3 = 16
M4 = 0
ACC = 2
Next Line = 8
[8]: Copy the value from ACC into memory cell M2.
M1 = 4
M2 = 2
M3 = 16
M4 = 0
ACC = 2
Next Line = 9
[9]: If the value in memory cell M2 is not zero, jump to the instruction at line 3.
M1 = 4
M2 = 2
M3 = 16
M4 = 0
ACC = 2
Next Line = 3
[3]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 2
M3 = 16
M4 = 0
ACC = 16
Next Line = 4
[4]: Add the value in memory cell M1 to ACC.
M1 = 4
M2 = 2
M3 = 16
M4 = 0
ACC = 20
Next Line = 5
[5]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 2
M3 = 20
M4 = 0
ACC = 20
Next Line = 6
[6]: Copy the value from memory cell M2 into ACC.
M1 = 4
M2 = 2
M3 = 20
M4 = 0
ACC = 2
Next Line = 7
[7]: Subtract the literal value 1 from ACC.
M1 = 4
M2 = 2
M3 = 20
M4 = 0
ACC = 1
Next Line = 8
[8]: Copy the value from ACC into memory cell M2.
M1 = 4
M2 = 1
M3 = 20
M4 = 0
ACC = 1
Next Line = 9
[9]: If the value in memory cell M2 is not zero, jump to the instruction at line 3.
M1 = 4
M2 = 1
M3 = 20
M4 = 0
ACC = 1
Next Line = 3
[3]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 1
M3 = 20
M4 = 0
ACC = 20
Next Line = 4
[4]: Add the value in memory cell M1 to ACC.
M1 = 4
M2 = 1
M3 = 20
M4 = 0
ACC = 24
Next Line = 5
[5]: Copy the value from ACC into memory cell M3.
M1 = 4
M2 = 1
M3 = 24
M4 = 0
ACC = 24
Next Line = 6
[6]: Copy the value from memory cell M2 into ACC.
M1 = 4
M2 = 1
M3 = 24
M4 = 0
ACC = 1
Next Line = 7
[7]: Subtract the literal value 1 from ACC.
M1 = 4
M2 = 1
M3 = 24
M4 = 0
ACC = 0
Next Line = 8
[8]: Copy the value from ACC into memory cell M2.
M1 = 4
M2 = 0
M3 = 24
M4 = 0
ACC = 0
Next Line = 9
[9]: If the value in memory cell M2 is not zero, jump to the instruction at line 3.
M1 = 4
M2 = 0
M3 = 24
M4 = 0
ACC = 0
Next Line = 10
[10]: Copy the value from memory cell M3 into ACC.
M1 = 4
M2 = 0
M3 = 24
M4 = 0
ACC = 24
Next Line = 11
[11]: Stop execution; the value currently in ACC is the final output.
M1 = 4
M2 = 0
M3 = 24
M4 = 0
ACC = 24
Steps taken = 46
Returned value = 24
Page updated
Google Sites
Report abuse