CS U111 · Lab 4 · Notes — the compressed map

Loops, in one page

Every loop shape, the ten patterns that cover the lab sheet, and the traps that lose marks. This is the revision layer — first time with loops? Start with the lesson, then come back here. Every problem on the sheet is worked out on the solutions page.

Start here — what the handout actually says about tomorrow

Continuous lab evaluations are open book, total 10% of the course, and are marked best k of n over the semester. One lab evaluation is therefore worth roughly 1–2% of your CS grade, and the scheme is built so a bad day drops out. Keep this page open during the session — that is allowed and it is the point of an open-book format.

Scope check: Lab 4 is Block D of the syllabus, lectures 10–14, textbook Hanly & Koffman ch. 5. It uses nothing beyond Labs 1–3 plus % and /. There are no arrays, no functions, no pointers — those are Blocks E, F and I, weeks away. Anything on the sheet that feels enormous is made of pieces you already have.

The whole thing in three questions

Every loop, in every language, is these three answers. Write them in the margin before you write code, and most loop bugs never happen:

1 · State Which variables change? What do they start at? (Counters and sums start at 0, products at 1.)

2 · Stop What keeps it going? Phrase it as "keep going while …", not "stop when …".

3 · Advance What changes inside the body so the condition eventually turns false?

If question 3 has no answer, you have written an infinite loop. If question 1 has no answer, you have written a garbage accumulator. Those are two of the three bugs in §10 of the lab sheet.

The three shapes

while — test first	do-while — test after	for — all three on one line
`int i = 0; while (i < 5) { body; i++; }`	`int i = 0; do { body; i++; } while (i < 5);`	`for (int i = 0; i < 5; i++) { body; }`
May run zero times.	Always runs at least once. Note the semicolon after `while(…)`.	May run zero times. Identical to the `while` beside it.

The for loop runs in a fixed order, and knowing it answers most trace questions: init once → test → body → update → test → body → … The update happens after the body, not before, which is why for (int i = 0; i < 5; i++) gives you i = 0 on the first pass and 4 on the last.

Choosing between them

The problem says…	Use
"for 10 terms", "rows 1 to n", "print the table up to 10" — a count you know before starting	`for`
"until the number becomes 0", "while there are digits left", "until the guess is right" — a condition, not a count	`while`
"ask the user, then check", "menu", "keep prompting until valid" — must happen at least once	`do-while`

All three are interchangeable in principle; choosing the natural one is a marked quality in lab evaluations, and it makes the code shorter.

The pattern cookbook

Ten patterns cover every problem on the Lab 4 sheet and most of what Hanly ch. 5 asks. Each one is small enough to memorise as a shape rather than as text.

1 · Counter

"how many …" · "count the …"

int count = 0;
for (…) { if (condition) count++; }

2 · Accumulator (sum / product)

"the total of …" · "the product of …"

int sum = 0;         // products start at 1, not 0
for (int i = 1; i <= n; i++) sum += i;

Starting a product at 0 makes every product 0. Starting a sum at 1 makes every sum wrong by one.

3 · Digit extraction — the workhorse

"digits of …" · "sum of digits" · "count digits" · "palindrome" · "Armstrong" · "digital root"

int temp = n;
while (temp != 0) {
    int d = temp % 10;   // last digit
    …
    temp /= 10;          // chop it off
}

Digits come out right to left. Runs zero times for n = 0 — handle that separately if 0 is a legal input.

4 · Build a number digit by digit

"reverse the number" · "is it a palindrome"

reversed = reversed * 10 + d;

×10 shifts what you have left, leaving a hole in the units place; + d fills it. A palindrome check is this, then reversed == num.

5 · Flag (boolean memory)

"is it prime" · "did any … happen" · "are all … true"

#include <stdbool.h>
bool isPrime = true;              // assume, then try to disprove
for (int i = 2; i * i <= n && isPrime; i++)
    if (n % i == 0) isPrime = false;

Set the flag to the optimistic answer, then let one counter-example knock it down. i * i <= n stops at √n — beyond that, any divisor would already have been found as its partner.

6 · Running pair

"Fibonacci" · "each term depends on the previous two"

int a = 0, b = 1;
for (int i = 0; i < n; i++) {
    printf("%d ", a);
    int next = a + b;
    a = b;  b = next;   // shift the window along
}

The temporary next is essential: overwrite a first and the old value of a is gone before b can use it.

7 · Validate input / menu

"keep asking until …" · "3 attempts" · "menu"

do {
    printf("Enter a positive number: ");
    scanf("%d", &x);
} while (x <= 0);

8 · Shrinking range (binary search)

"guess the number" · "halve the range each time"

int low = 1, high = 1000;
while (low <= high) {
    int mid = (low + high) / 2;
    if (mid == target) break;
    else if (mid < target) low = mid + 1;
    else                   high = mid - 1;
}

The + 1 and - 1 are not decoration — without them the range can stop shrinking and the loop hangs.

9 · Alternating sign

"1 − 1/3 + 1/5 − …" · any series with + and − alternating

int sign = 1;
for (int i = 0; i < N; i++) {
    sum += sign * 1.0 / (2 * i + 1);   // 1.0 — never 1
    sign = -sign;
}

Odd denominators come from 2i + 1; even ones from 2i. Both are worth remembering as generators.

10 · Nested rows × columns

"pattern" · "triangle" · "grid" · "table"

for (int i = 1; i <= n; i++) {        // rows
    for (int j = 1; j <= i; j++)      // columns — limit may depend on i
        printf("*");
    printf("\n");                     // ends the row
}

The inner loop runs completely for each single pass of the outer one. The newline goes after the inner loop, inside the outer.

Pattern 10, drawn. Shaded = printed. Change the inner condition from j <= i to j <= n and the dashed cells fill in too — that one character is the whole difference between a triangle and a square (Debugging exercise 4).

`break` and `continue`

Statement	Effect	Output for `i` = 1…5
`break`	Leaves the loop entirely, right now.	`if (i==4) break;` before the print → `1 2 3`
`continue`	Skips the rest of this pass, goes on to the update and the next test.	`if (i%2==0) continue;` before the print → `1 3 5`

Classic trap · continue inside a while

In a for loop, continue still runs the update (i++), so the loop keeps moving. In a while loop the update is a statement in the body — and continue jumps over it, straight back to the condition. Nothing changes, and the program hangs. If you continue in a while, do the update before the continue.

Two worked examples at evaluation level

Worked example 1

Predict the output — trace it, don't read it

int x = 20;
int count = 0;
while (x > 1) {
    if (x % 2 == 0) x = x / 2;
    else            x = x + 1;
    count++;
}
printf("%d %d\n", x, count);

Reading code and predicting output are different skills, and only one of them is examined. Do it in four mechanical steps.

Draw the table before you think. One column per variable that changes, one row per pass: here, x and count.
Fill in the "before the loop" row: x = 20, count = 0.
Do one pass at a time, writing every value down. Never keep two numbers in your head.

pass x at test x % 2 x becomes count

1 20 0 (even) 10 1

2 10 0 5 2

3 5 1 (odd) 6 3

4 6 0 3 4

5 3 1 4 5

6 4 0 2 6

7 2 0 1 7

test 1 — 1 > 1 is false → exit 7
Read the answer off the last row: 1 7. Match the printf format exactly — two numbers, one space, one newline.

pass	x at test	x % 2	x becomes	count
1	20	0 (even)	10	1
2	10	0	5	2
3	5	1 (odd)	6	3
4	6	0	3	4
5	3	1	4	5
6	4	0	2	6
7	2	0	1	7
test	1	—	1 > 1 is false → exit	7

Notice pass 3: x went up, from 5 to 6. A loop variable is allowed to move away from the exit as long as it eventually gets there. That is why "trace it" beats "reason about it".

Worked example 2

Write one from a spec — sum of the even numbers up to n, and how many there were

"Read a positive integer n. Print the sum of all even numbers from 1 to n inclusive, and how many there were."

Copy the required output first. Two lines, a sum and a count. That tells you two accumulators.
Answer the three questions. State: sum = 0, count = 0, loop variable i. Stop: after i passes n — a known count, so for. Advance: i++.
Write the skeleton and compile it empty — int main(void), the scanf, an empty for, the two printfs. Compile. Zero errors before there is any logic to blame.

Fill the body.

int n, sum = 0, count = 0;
printf("Enter n: ");
scanf("%d", &n);

for (int i = 1; i <= n; i++) {
    if (i % 2 == 0) { sum += i; count++; }
}

printf("Sum of evens: %d\n", sum);
printf("How many: %d\n", count);

Test the three boundaries §19 asks for. n = 1 → sum 0, count 0 (the loop runs, but the if never fires). n = 2 → sum 2, count 1. n = 10 → 2+4+6+8+10 = 30, count 5. Check the last one on paper before you believe the program.

Check yourself: how would you do it without the if?

Step by two: for (int i = 2; i <= n; i += 2) { sum += i; count++; }. The for header's update doesn't have to be i++ — it can be any change. Shorter, and it does half as much work. Both are correct; be able to write either.

Classic traps — the standard ways marks are lost

The mistake	What you see	The fix
Off by one — `i < 10` where you meant `i <= 10`	One line too few (or too many)	Count first: `i < b` from a runs b−a times; `i <= b` runs b−a+1
Missing update — nothing in the body changes the condition	Program hangs forever	`Ctrl`+`C`, then add the update. Answer question 3 before writing.
Uninitialised accumulator — `int sum;`	A huge random number, different each run	`int sum = 0;`. Compile with `-Wall` and it warns you.
Semicolon after the header — `for (…);` or `while (…);`	The body runs once, or hangs; no error message	Nothing goes between `)` and `{`. This one is invisible — look for it when output makes no sense.
Missing braces — two statements, one indented, no `{ }`	Only the first statement repeats; indentation lies	Always brace the body, even for one line.
Integer division — `1 / (2*i+1)`, `sum / n` for an average	0, or a truncated average	`1.0 / (2*i+1)`; `(double) sum / n`
`==` on floats	Two identical-looking values compare unequal	`fabs(a - b) < 1e-6`. See Debugging exercise 5.
Missing `&` in `scanf` — `scanf("%d", n)`	Crash, or garbage input	`scanf("%d", &n)`. Every `scanf` variable needs it (strings excepted, in Lab 7).
Accumulator declared outside the outer loop in a nested problem	Round 2 adds to round 1's total	Initialise immediately before the loop that fills it.
`break` missing in a `switch`	Two menu options run	One `break` per `case`.

The zero-iteration habit

§19 of the lab sheet asks you to design tests that make a loop run zero times, once, a typical number of times, and the maximum. The zero case is the one nobody tries and the one examiners choose: input 0 to a digit loop, n = 0 to a "print n rows" loop, an empty range. Write the zero case in your test list before you write the loop, and say so in a comment. Marks are given for noticing.

Minimal prerequisite kit

The complete list of school-level facts this lab leans on. Nothing else is assumed.

Fact	Why it appears
`a % b` is the remainder	`n % 10` is the last digit; `n % 2 == 0` tests even; `n % i == 0` tests divisibility
`a / b` on two `int`s truncates	`452 / 10` = 45 chops a digit off; `7 / 2` = 3, not 3.5
Place value: a digit's worth is its position's power of 10 (or 2)	`reversed * 10 + d`; the powers-of-2 walk in the binary problem
Powers of 2 up to 1024	Binary conversion; why binary search takes ~10 guesses over 1000 numbers
Divisibility and primes: a factor above √n pairs with one below	Why the prime test stops at `i * i <= n`
The leap-year rule: /4, except /100, unless /400	The calendar challenge (from Lab 3)
Odd numbers are 2i+1; even are 2i	Generating the Leibniz denominators; stepping by 2

Unpack this step — why a divisor above √n can't be the first one you meet

If n = a × b and both a and b were bigger than √n, then a × b would be bigger than n — impossible. So every factor pair has one member at or below √n, and checking up to √n finds it. That is why i * i <= n is enough, and it makes the prime test dramatically faster for large n.

What to practise

Ranked for a short evening. The lab sheet's own problems are the best practice available, because they are what the evaluation is drawn from.

Skill	Drill it on	Textbook backup Hanly ch. 5	How many
Predicting output (tracing)	Dry runs 1–4 on the solutions page	Self-check exercises, "Counting loops and the while statement" & "The for statement"	all 4 · 10 min
Spotting loop bugs	Debugging exercises 1–5	"Common programming errors" (end of chapter)	all 5 · 10 min
Digit extraction	Problem 1, then Problem 3	"Computing a sum or a product in a loop"	2 · type them
`do-while` and input validation	Problem 4	"Do-while statement and flag-controlled loops"	1 · 8 min
Nested loops / patterns	Problem 7, then invent a pyramid	"Nested loops"	2 · 10 min
Flags and prime-style tests	Sheet §12 (worked), then "is it a perfect number"	"Loop design"	1 · if time
Series and floating point	Problem 6	"Computing a sum or a product in a loop"	read only
Everything at once	The calendar challenge	"Problem solving illustrated"	weekend, not tonight

Section titles rather than numbers, because editions renumber; in the 8th edition these are the sections of chapter 5 in roughly this order. Confirm against your copy — and if the instructor names specific sections, those win.

Don't do this tonight

Don't go hunting for extra loop problems on the internet, and don't start a "100 C programs" list. The sheet has seventeen problems on it; doing four of them properly beats skimming forty. And don't let an AI write the programs — the handout examines your ability to verify generated code (lectures 40–41), the lab is invigilated, and typing them yourself is what puts the patterns in your fingers.