Corrected exercises: loops and the patterns they carry, COMP 202 at McGill

a) The twelve months are a for over range(1, 13): the count is known before the loop begins. Reading until quit is a while, since the number of lines depends on what the user does. Walking the characters of a word is a for over the word itself, for ch in word, because the collection is the count. Asking until a valid mark is a while, and specifically a loop that must run at least once, so while True with a break, or a first read before the loop.

b) Three extra lines: i = 0 before the loop, while i < 5: as the header, and i = i + 1 as the LAST line of the body. That third one is the one that goes missing, and its absence gives an infinite loop rather than an error message. This is the whole argument for the for loop: the initialisation, the test and the update sit in one header where none of them can be forgotten, whereas the while loop scatters them over three places.

c) Nothing stops you from writing a for loop, but you cannot write its range without first knowing the answer: the number of passes is $\lfloor \log_2 n \rfloor$, which is exactly the quantity the loop was computing. That is the difference in one sentence: a for loop needs the count in advance, a while loop discovers it. Whenever the number of passes is the ANSWER, the loop is a while.

d) It does not stop early, and it prints 0 through 9 unchanged. At the top of each pass, the for loop assigns the next value of range to i, throwing away whatever the body left there. Assigning to the loop variable inside the body is therefore invisible from the next pass onward, which is a common and useless attempt at breaking out of a loop; break is the statement that does that.

e) Zero times. A while loop tests BEFORE the first pass, so a condition that starts false gives a body that never runs, and the variables the body was meant to set keep whatever they held. The equivalent for loop is one over an empty range, for i in range(0): which also runs zero times. When a body must run at least once whatever the condition, that is the pattern with while True and a break at the end, since Python has no do while.

a) count = 0 before the loop, then for ch in text: if ch in 'aeiou': count = count + 1, and count is read afterwards. The starting value is 0 because it is neutral for addition: a text with no vowel must give 0, and that is exactly what the loop returns without running its body. Testing membership with in against the string 'aeiou' is shorter and more readable than five comparisons joined by or, and it is what a marker expects. To count both cases, lower the character first with ch.lower().

b) product = 1 before the loop, then for v in values: product = product * v. Starting at 0 destroys the answer because 0 is absorbing for multiplication: every product that follows is 0, whatever the list contains. On an empty list the loop body never runs and the function returns 1, the empty product, which is the mathematically correct convention and worth stating in a docstring, since a reader may expect 0.

c) all_positive = True before the loop, then for v in values: if v <= 0: all_positive = False. The claim starts true because nothing has contradicted it yet, and one counterexample is enough to bring it down for good. The opposite choice, starting at False and setting True when a positive number is met, answers a different question, namely whether AT LEAST ONE number is positive; on the list containing 3 and -1 it would end up True. A flag for every is initialised True and only ever falls; a flag for at least one is initialised False and only ever rises.

d) index = -1 before the loop, then for i in range(len(values)): if values[i] < 0: index = i, and a break to keep the FIRST one rather than the last. The value -1 is safe as a sentinel because it is not a valid index for a search result, and a caller that tests if index >= 0 handles both cases. It is dangerous in general because -1 IS a valid Python index, the last element: a caller who forgets the test and writes values[index] reads the last element and gets a plausible wrong answer instead of a crash. Returning None makes the mistake noisy, which is usually better.

e) total = 0 and count = 0 before the loop; inside, total = total + v and count = count + 1. After the loop, the division needs a guard: if count == 0 there is nothing to average and the division raises ZeroDivisionError. Return None, or print a message, but do not return 0, which claims an average of zero for an empty collection. The guard is not defensive decoration, an empty list is what a file with a header line and no data produces.

a) The else runs only when the for loop reached the end of the collection without ever meeting break. With names holding 'Ana' and 'Ben' and target 'Ben', the break fires on the second pass and the else is skipped, so only found is printed. With the same list and target 'Zoe', the loop ends normally and the else prints not in the list. The name else is admittedly badly chosen: read it as no break happened.

b) found = False before the loop, then for name in names: if name == target: found = True, break, and afterwards if found: print('found') else: print('not in the list'). It is the version to submit in COMP 202, because every reader understands it at once, while the loop else is misread by most people including experienced programmers. It is longer than it looks because the flag has to be initialised, updated and tested in three separate places, which is three chances to forget one.

c) The continue jumps back to the test WITHOUT running the lines below it, and the increment i = i + 1 is one of those lines. So i keeps its value, the condition is still true, the same pass runs again, and the program hangs with no error message. In a for loop the same continue is harmless, since the update belongs to the loop header. The repair is to increment BEFORE the continue, or better, to use a for loop over range(len(word)) so that no update can be skipped.

d) A break leaves the innermost loop that contains it, and nothing more: the outer loop simply moves to its next pass, so the search continues on the next row. To leave both, either set a flag that the outer loop tests right after the inner loop, and break again; or, far cleaner, put the double loop in a function and use return, which leaves everything at once. Python has no labelled break.

e) Making the condition false lets the CURRENT pass finish before the loop ends, break stops it immediately. In a loop that reads a value, checks it and then processes it, that difference decides whether an invalid value is processed once before the exit. So break is the right tool when the exit must be immediate, and a condition is the right tool when the loop has one clear invariant that stops holding.

a) Twelve times, the product of 3 and 4. The seventh execution is on the second row of the table, third column, so i is 1 and j is 2. The general rule for the k-th execution, counting from 1: i is $(k-1) // 4$ and j is $(k-1) \bmod 4$, and recognising that the quotient names the row and the remainder the column is worth more than the table itself, since it is exactly how a program walks a grid stored as one long list.

b) Five hundred times five hundred, that is 250 000 comparisons, or 249 500 if the comparison of a name with itself is skipped and half that again if each pair is only compared once. Doubling the list to 1000 names gives a million comparisons: four times as many for twice the data. That is what quadratic cost means, and it is the first place in a first course where a correct program becomes unusable, exactly as the naive Fibonacci does with recursion.

c) for i in range(1, 6): then inside, for j in range(i): print('*', end=''), then after the inner loop, print(). The empty print at the OUTER level ends the line, and forgetting it prints fifteen stars in a row. The one line version replaces the inner loop with string repetition: for i in range(1, 6): print('*' * i), which is the version to write in practice, since a repeated string is one operation rather than a loop.

d) The inner loop overwrites i on every one of its passes, so when control returns to the outer header, the value the outer loop believed in is gone. With a for loop the damage is contained, because the outer header reassigns i from its own range at the top of the next pass, so the loop still runs the right number of times and only the body has read wrong values. With two while loops it is fatal: the outer counter is reset or advanced by the inner loop and the program either stops too early or never stops.

e) The inner loop runs 0, then 1, then 2, then 3, then 4 times, for a total of 10 executions, that is $5 \times 4 / 2$. The shape is the triangle of question c), and the general count for an outer range(n) is $n(n-1)/2$. It is half of the full square, and it is the natural pattern whenever each pair is to be treated once rather than twice, for example when comparing every student with every other.

a) Pass 1: n is 1234, d is 4, total becomes 4, n becomes 123. Pass 2: n is 123, d is 3, total becomes 7, n becomes 12. Pass 3: n is 12, d is 2, total becomes 9, n becomes 1. Pass 4: n is 1, d is 1, total becomes 10, n becomes 0. The test then fails and the program prints 10, which is indeed $1+2+3+4$. Note that the loop runs once per DIGIT, four passes for a four digit number, which is the count to expect for anything that peels a number apart.

b) With n = n // 10 executed before total = total + d, the digit added is the one extracted BEFORE the shift, so d is unchanged, and the result is the same. The order that really breaks the program is putting d = n % 10 after the shift: pass 1 then computes n as 123 and d as 3, pass 2 gives n as 12 and d as 2, and the units digit is never added while a leading zero is, so the printed total is 6. The lesson is that a trace table finds this in thirty seconds and reasoning about it does not.

c) It prints 0, since the condition n > 0 is false at the first test and the body never runs, leaving total at its starting value. The answer happens to be right: the digit sum of zero is zero. It is worth noticing that it is right by accident, because the neutral starting value of the accumulator coincides with the correct answer for the empty case, which is exactly why a neutral starting value is chosen.

d) The condition -5 > 0 is false, so the body never runs and the program prints 0. That is a wrong answer silently returned: the digit sum of -5 should be 5, or the input should have been refused. Nothing crashes, nothing warns, and a test suite made of positive numbers never sees it. The fix is one line at the top, n = abs(n), or a validation that refuses a negative argument.

e) The run with n = -5 changes, and it becomes an infinite loop. Follow it: -5 is not 0, so d is -5 % 10 which is 5, since the remainder carries the sign of the divisor, and n becomes -5 // 10 which is -1, since floor division rounds toward minus infinity. Next pass: -1 is not 0, d is 9, n is -1 // 10 which is -1 again. The value sticks at -1 for ever and the program hangs. The lesson: a stopping condition written with an inequality tolerates values you did not think of, one written with a strict difference demands that the sequence lands exactly on the target.

a) It prints you chose a, then tests choice != 'q' again with the SAME value, prints it again, and does so for ever. Nothing in the body changes choice, so the condition can never become false. The missing line is a second read inside the loop, choice = input('Choice (a, b, q): ') as the last line of the body. A while loop whose condition mentions a variable the body never touches is an infinite loop, and that is a check worth making on sight, before running anything.

b) The new input goes at the END of the body, after the cascade, so that the choice just made is acted upon before the next one is read. The prompt is then written twice, once before the loop to get the first value and once inside to get the following ones, which is the classic read one before, read one at the end shape. Duplicating the prompt string is a small price, though it is exactly the duplication that the version of question c) removes.

c) while True: then choice = input('Choice (a, b, q): '), then if choice == 'q': break, then the cascade of options. For a menu of ten options this is the version to prefer: the prompt appears once, the exit test sits immediately after the read where a reader looks for it, and adding an eleventh option touches one place. Its cost is that the loop header no longer says when the loop ends, so the break must be easy to find, which means keeping it at the top rather than burying it in a branch.

d) Q is not q, so both versions treat it as an unknown choice and carry on: the user asked to quit and the program refused, which is the kind of bug that gets reported as the program is broken. One call fixes it, applied to the value as it is read: choice = input('Choice (a, b, q): ').strip().lower(). The strip also removes the trailing space a user leaves, and normalising input at the border, once, is worth more than testing for every variant everywhere.

e) done = 0 before the loop, and done = done + 1 inside the two branches that recognise a choice, or once after the cascade when the else has not run. It must not be reset inside the loop, because a variable set to zero at the top of the body is created afresh on every pass and can never hold anything but the count for the current pass; the print after the loop would then always show 0 or 1. The accumulator lives OUTSIDE the loop it counts, which is the same rule as the total of exercise 2 seen from the interactive side.

a) From 6 the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1. The loop counts the transitions, not the values, so it prints 8: there are nine numbers and eight arrows between them. Confusing the two is the standard off by one of any counting loop, and writing the sequence with its arrows is what settles it.

b) largest = n before the loop, then largest = max(largest, n) as the last line of the body, or an explicit if n > largest: largest = n. The starting value must be the first term itself, not 0, for the reason already met with a running maximum: seeding with a value outside the data returns something that never occurred. For n = 6 the largest value is 16; for n = 7 the sequence climbs to 52 before coming down, in 16 steps.

c) A for loop over range(120) would perform 120 passes whatever happens, so it would keep transforming 1 after the sequence reached it: 1 is odd, so it becomes 4, then 2, then 1, and the loop cycles for the remaining passes and prints a wrong count. Adding a break when n reaches 1 repairs it, but then the range is decoration: the loop is a while wearing a for header, and the bound 120 is a number the programmer guessed. It is the wrong tool because it encodes an assumption, and the day a starting value needs 200 steps the program answers 120.

d) Inside the if branch, only the halvings are counted. For n = 6 the sequence halves at 6, 10, 16, 8, 4 and 2, that is six even values out of the eight transitions, so the program prints 6 instead of 8. Inside the else branch, only the odd steps are counted, which for n = 6 means the two tripling steps at 3 and 5, so it prints 2. The line belongs to the loop, not to a branch: what is counted is a pass, and both branches are one.

e) With n = 0 the condition 0 != 1 is true, 0 is even, so n becomes 0 again, and the program hangs for ever with no message. A negative value hangs too, on a different cycle. The guard is a validation before the loop, if n < 1: refuse, because the loop's stopping condition is only meaningful for a positive integer and there is nothing sensible for the body to do with anything else. Putting the test inside the loop tests it once per pass to answer a question that was settled before the first one.

a) False. A while loop tests FIRST and runs its body zero times when the condition starts false. The counterexample is one line: i = 10, then while i < 5: print(i), which prints nothing at all. The confusion comes from the do while loop of C and Java, which does test at the end; Python has no such statement, and the shape used instead is while True with a break at the point where the test belongs. Correct version: a while loop runs zero or more times, and zero is a case to be checked.

b) False. break leaves exactly ONE loop, the innermost one containing it. The counterexample: two nested for loops over range(3) printing i and j, with a break in the inner loop when j equals 0, prints three lines, one per pass of the OUTER loop, not one line in total. Correct version: break ends the loop that immediately contains it; leaving several loops at once needs a flag, or a return from a function.

c) False. In a while loop, continue jumps back to the condition without running the rest of the body, and the update usually lives at the end of that body. The counterexample: i = 0, while i < 3: if i == 1: continue, then i = i + 1. It prints nothing and never ends, because once i is 1 the increment is skipped for ever. Correct version: continue is safe in a for loop, whose update is in the header, and needs care in a while loop, where the update must be placed before it.

d) False, and the index version is worse than the direct one. The counterexample: values holds 1, 2, 3, 4 and the loop over range(len(values)) removes the even numbers. Removing 2 at index 1 shifts 3 and 4 down, so index 2 now holds 4, which is removed, and index 3 no longer exists, so the loop raises IndexError, or silently misses an element if a length check hides it. Correct version: never shorten a list you are walking. Build a new list with a comprehension, or walk a copy with values[:], or walk the indices backwards.

e) False. The passes multiply, they do not add: the inner loop runs its 100 passes for EACH of the outer loop's 100 passes, which is 10 000 executions of the inner body. The counterexample is a counter incremented in the inner body and printed at the end, which shows 10 000. Correct version: nested loops multiply their counts, which is why doubling the size of both lists multiplies the work by four.

a) rate = 0.04 / 12, then balance = 0.0, then for month in range(48): balance = balance * (1 + rate) + 200. The monthly rate is the annual rate divided by twelve because the interest is credited monthly; applying 0.04 every month would pay 4 percent twelve times a year. The multiplication and the addition on one line say exactly what a month is: the old money grows, then the new deposit arrives, and the deposit earns nothing during the month it arrives in.

b) The difference of 791.92 dollars is the interest, and it is small because each deposit only earns for the months that follow it. The last deposit earns nothing at all, the first earns for 47 months. On average the money has been invested for about half the period, so the interest is close to 4 percent of 9600 times two rather than times four, which is around 768 dollars, and the compounding accounts for the rest. Reasoning on the AVERAGE time invested is what turns a surprising number into an expected one.

c) Only a while loop will do, because the number of passes is the answer: balance = 0.0, month = 0, then while balance < 10000: balance = balance * (1 + rate) + 200, month = month + 1. After the loop, month holds the answer and balance holds the first amount above the target. The two must be read together, since month alone does not say by how much the target was passed, 10158.06 dollars here.

d) Fifty deposits of 200 dollars make exactly 10000, so with no interest the target is reached at month 50. With interest the target arrives at month 47, three months earlier, and at that point only 9400 dollars have been deposited: the missing 600 dollars are the accumulated interest, 758.06 to be exact, minus the overshoot. On the graph, year 4 ends at 10391.92 which is already above the line, and year 3 at 7636.31 which is below, so the crossing is inside the fourth year, and month 47 is indeed in that year.

e) The balance goes UP, because the deposit of the month then earns interest during that same month. On the first month the correct order gives 200 dollars exactly, since the account was empty, while the swapped order gives $200 \times (1 + 0.04/12) = 200.67$ dollars. The difference is 67 cents on the first month and grows with the balance. Neither line is wrong as Python: the choice states WHEN the deposit is made, at the end or at the start of the month, and a financial specification has to say which.

a) is_prime = True, then for d in range(2, n): if n % d == 0: is_prime = False, and afterwards read is_prime. Adding break after the assignment changes nothing for a PRIME, since no divisor is ever found and the loop runs to the end either way; it changes everything for an even number, where the loop stops on the very first division instead of testing the 500 000 remaining candidates for a number near a million. Cutting the cost of the easy cases and leaving the hard case untouched is exactly what break does everywhere.

b) If $d$ divides $n$ then $n = d \times e$ for some integer $e$, and if $d > \sqrt{n}$ then $e = n/d < \sqrt{n}$. So every divisor above the square root is paired with one below it, and a loop that found nothing below the square root cannot find anything above. The bound is inclusive, since $n$ may be a perfect square, as with 49 whose only nontrivial divisor is exactly 7.

c) for d in range(2, isqrt(n) + 1): if n % d == 0: print('composite'), break, and else: print('prime'), attached to the for. The else version is shorter and has no flag to forget, and it is the idiomatic Python. The flag version is the one to defend in a review with people who do not all know the loop else, and it is also the one that survives being moved into a function where the answer is returned rather than printed, which is the shape to prefer anyway: return False inside the loop, return True after it, no flag and no else at all.

d) TypeError: the expression n ** 0.5 is a FLOAT, and range accepts only integers. The correct bound is int(n ** 0.5) + 1, or better math.isqrt(n) + 1, which is exact where the float square root of a large perfect square can land just below the integer and miss a divisor. The plus one is there because range excludes its upper bound and the square root itself must be tested.

e) There are 25 primes below 100. The loop is the double loop of exercise 4: for n in range(2, 100), and inside it the primality test, so the outer accumulator counts the numbers that pass. On the single number 9973, which is prime, the naive version performs 9971 divisions, from 2 to 9972, where the square root version performs 98, from 2 to 99. That is a hundredfold saving on one number, and the ratio grows as the square root of the number tested.