Algorithm Output Trace
Consider the following algorithm written in pseudocode:
input N
S = 0
for i = 1 to N do
if i mod 2 = 0 then
S = S + i
else
S = S - i
end if
next i
output S
A student runs this algorithm with N = 6 and gets a result. Then they run it with N = 7 and get another result. They need to determine the outputs and explain the pattern.
1. Trace the algorithm for N = 6. Show the value of S after each iteration.
Read the worked answer
Start S=0. i=1: odd, S = 0 - 1 = -1 i=2: even, S = -1 + 2 = 1 i=3: odd, S = 1 - 3 = -2 i=4: even, S = -2 + 4 = 2 i=5: odd, S = 2 - 5 = -3 i=6: even, S = -3 + 6 = 3 Output S = 3.
2. Trace the algorithm for N = 7. What is the output?
Read the worked answer
Continue from N=6? Actually for N=7, we start fresh: S=0 i=1: S=-1 i=2: S=1 i=3: S=-2 i=4: S=2 i=5: S=-3 i=6: S=3 i=7: odd, S = 3 - 7 = -4 Output S = -4.
3. Describe the pattern of S for any N. Derive a formula for S in terms of N.
Read the worked answer
For even N: S = N/2. For odd N: S = -(N+1)/2. Check: N=6 even => 3; N=7 odd => -4. Derivation: The sum alternates -1+2-3+4-... For even N=2k, pairs (-1+2)=1, (-3+4)=1, ... k pairs => S=k=N/2. For odd N=2k+1, after 2k terms sum=k, then subtract (2k+1): S = k - (2k+1) = -k-1 = -(N+1)/2.