Binary place value and algorithm traces

Base two records powers of two

Each binary digit is 0 or 1. Starting at the right, integer-place weights are 1, 2, 4, 8, 16, 32 and so on. Multiply each digit by its weight and add. A base subscript identifies notation: 101 in base two has value five, not one hundred and one

Use the place-value table. What is the decimal value of the displayed binary numeral?

Zeroes preserve places

Leading zeroes do not change a value, but an internal zero holds a place. Six unsigned bits represent integers from zero to 63. The all-one value is 32 + 16 + 8 + 4 + 2 + 1. This lesson does not interpret the first bit as a sign or use two’s-complement encoding

Which statement about 1001 in base two is correct?

Convert by choosing place weights

For decimal 38, take 32 and leave 6. The 16 and 8 places are zero. Take 4 and leave 2, then take 2 and leave zero. The 1 place is zero. Writing every place from 32 to 1 gives 100110. Recompute the weighted sum to check the conversion

In the six-place binary representation of decimal 38, what is the digit with weight 8?

Binary places can extend past the point

Fractional places have weights one half, one quarter, one eighth and so on. For a terminating binary fraction, use the same weighted-sum method on both sides of the point. Generated practice here uses unsigned integers; the fractional example is a fixed teaching check

Convert 111.01 in base two to a decimal value

Quotient and remainder give the last digit

For a nonnegative integer n, write n = 2q + r with r either 0 or 1. The remainder is the least significant bit; q contains the remaining bits. Repeat with q until it is zero. Remainders are produced from right to left, so reverse their order when writing the numeral. Zero needs its own output 0.

Construct a conversion algorithm, ungraded

Write precise pseudocode converting any nonnegative integer n to a binary numeral. Handle zero, record remainders, specify their order and justify termination. Implement it in a calculator or short program and test zero, one, a power of two and the value just below that power. Independent code and justification are ungraded

Model: repeated division with a zero case

If n = 0, output the numeral 0 and stop. Otherwise initialise an empty list R. WHILE n > 0: compute r = n MOD 2; append r to R; replace n by n DIV 2; END WHILE. Output the reverse of R as consecutive digits. For 46, the (n, quotient, remainder) rows are (46,23,0), (23,11,1), (11,5,1), (5,2,1), (2,1,0), (1,0,1), giving 101110. On positive input the nonnegative quotient strictly decreases, so termination follows. The identity n = 2q + r at each step reconstructs the original weighted value. Test outputs include 0 → 0, 1 → 1, 16 → 10000 and 15 → 1111.

Assignment changes stored state

The arrow means evaluate the right side using the values currently stored, then replace the left-side value. Later statements see earlier updates. Equality tests compare values; they do not assign them. A trace table records state after each step or iteration, and must say which. All pseudocode here uses exact arithmetic

Execute x ← 4; y ← 9; x ← x + y; y ← x − y, in that order. What is the final y?

Decisions choose a branch

IF condition THEN runs its first block when the condition is true. ELSE runs its alternative when false. Exactly one branch of an IF–ELSE runs. Use indentation and END IF to make its extent clear. Combine comparisons with the Boolean operations from 3A when several requirements must hold

n = 0. An algorithm uses IF n MOD 2 = 0 THEN output n + 7 ELSE output 2n + 7 END IF. Which branch runs?

FOR loops state a finite range

FOR i FROM 1 TO N visits every integer 1 through N, including N, with step one. In this lesson N is a nonnegative integer; N = 0 means no iterations. Initialise an accumulated sum or product before the loop, and place the output after it unless every intermediate value is required

Start total = 0. FOR i FROM 1 TO 4, add 2i − 1 to total. After END FOR, what is total?

WHILE tests before the body

WHILE repeats while its condition is true, testing again before each iteration. It can run zero times. The body must make progress towards a false guard; a missing update can cause nontermination. For total initially 0, a positive step 5 and guard total < 17, totals after updates are 5, 10, 15, 20. Stop at 20 after four updates

With total initially 0, add 6 while total < 18. How many updates occur?

Trace a changed loop, ungraded

A program repeatedly adds a positive integer s to total, starting at zero, while total < L, where L > 0. Explain how changing < to ≤ affects a run when L is a multiple of s. Give a test that distinguishes the programs and justify termination of both. Independent explanation is ungraded

Model: equality changes the stopping point

Take s = 4 and L = 12. With <, the totals are 4, 8, 12 and the count is 3. With ≤, the guard is still true at 12, so the totals are 4, 8, 12, 16 and the count is 4. In general, when L = ks with positive integer k, the counts are k and k + 1. Positive s increases total without bound, so each eventually exceeds the finite threshold. If s were zero, neither loop would progress from zero

PRINT records the current value

A printout records each value when PRINT runs, in that order. It is not just the final stored value. In this algorithm, k visits 1 through 6. MOD gives the remainder. Trace all six iterations and write the complete printout before checking its three pairs. PRINT is inside FOR but after END IF

Trace the displayed algorithm. Enter the first and second printed values as an ordered pair (a, b), with the earlier value first. Keep every repeated value

Trace the displayed algorithm. Enter the third and fourth printed values as an ordered pair (a, b), with the earlier value first. Keep every repeated value

Trace the displayed algorithm. Enter the fifth and sixth printed values as an ordered pair (a, b), with the earlier value first. Keep every repeated value

Model: preserve order and repeated values

Each row records the selected update and the value printed immediately afterwards. The complete printout, in order, is 1, 3, 1, 5, 1, 7. Repeated values stay in their positions. PRINT runs once per iteration, regardless of which branch runs

Move PRINT and test the boundary, ungraded

Move only PRINT total to immediately after END FOR. Predict the new printout and explain the difference. Then replace the upper bound 6 with 0 in both versions: the loop now has no iterations. Predict both printouts and test them in a calculator or program. Your explanation and implementation are ungraded

Model: outside the loop prints once

Start total at 1. For k from 1 to 6, add k when k is even and subtract k − 1 when k is odd. Compare PRINT after each update inside FOR with PRINT once after END FOR. With PRINT after END FOR, the six updates finish at total = 7, but only 7 is printed. With upper bound 0, total stays at 1. The inside-loop version prints nothing because its body never runs; the outside-loop version prints 1 once. An empty printout is not a printed zero