Iteration – Part 2

CS111 Computer Programming

Department of Computer Science

Wellesley College
Review: Iteration [Part 1]
o Iteration is the repeated execution of a set of statements until a
stopping condition is reached.
o while loops are an iteration construct used when it is not known in
advance how long execution should continue. for loops (an
abstraction of while loops) are used when we have a fixed set of
items in a sequence to iterate over.
o If the stopping condition is never reached, the loop will run forever.
It is known in this case as an infinite loop.
o The stopping condition might involve one or more state variables,
and we need to make sure that the body of the loop contains
statements that continuously update these state variables.
o We can use the model of iteration tables to understand the inner
workings of a loop. Its columns represent the state variables and the
rows represent their values in every iteration.

Iteration 2 2
 Concepts in this slide:
Comparing the syntax of
both loop constructs.
Review: Syntax of loops
a boolean expression
denoting whether to iterate
through the body of the
loop one more time.
while continuation_condition :
statement1
…

statementN A sequence of items: characters

in a string, items in a list, ranges,
A variable that takes its values etc.
from the items of the sequence.

for var in sequence:

statement1
…

statementN
Iteration 2 3
Flow charts for two
loop constructs True continuation False
_condition
statement1

while while

…
loop
body
statementN

True Still elements False

in sequence
statement1

for for
…

loop
body
statementN

Iteration 2 4
 Concepts in this slide:
Review: sumBetween Using the iteration table to
reason about a problem.

with while loop

step lo hi sumSoFar
In[6]: sumBetween(4,8) 0 4 8 0
Out[6]: 30 # 4 + 5 + 6 + 7 + 8 1 5 8 4
sumBetween(4,8) returns 30 2 6 8 9
sumBetween(4,4) returns 4 3 7 8 15
sumBetween(4,3) returns 0 4 8 8 22
5 9 8 30
def sumBetween(lo, hi):
'''Returns the sum of the integers from lo to hi
(inclusive). Assume lo and hi are integers.'''
sumSoFar = 0 initialize accumulator
To notice:
while lo <= hi: • Row 0 in the table shows the
sumSoFar += lo initial values of all state
lo += 1 update accumulator variables.
return sumSoFar • Row 1 shows values after the
updates in the loop body.
return accumulator Iteration 2 5
Today’s topics
o Nested for loops
o Swapping two variable values
o Simultaneous assignment in Python

Iteration 2 6
 Concepts in this slide:
Two nested loops: the
Nested loops for printing outer and inner loop.

A for loop body can contain a for loop.

for i in range(2, 6):

Outer loop for j in range(2, 6):
print(i, 'x', j, '=', i*j) Inner loop

# print the multiplication table from 2 to 5

2 x 2 = 4
To notice:
2 x 3 = 6 o Variable i in the outer loop is set initially to value 2.
2 x 4 = 8 • Variable j in the inner loop is set initially to value 2.
2 x 5 = 10 • Variable j keeps changing its value: 3, 4, 5;
3 x 2 = 6 meanwhile i doesn’t change.
3 x 3 = 9 o When the inner loop is done, i becomes 3.
3 x 4 = 12 • Now the inner loop starts again, and j takes on the values
... 2, 3, 4 ,5
o Every time j reaches 5, the inner loop ends and i increments.
o The outer loop ends when both i and j are 5.

Iteration 2 7
Nested Loop Exercises
Conditionals can appear anywhere in loops.
Predict the printed output of the following loops.
(Answers are in the notebook solutions.)

for i in range(2, 6):

for j in range(2, 6):
if i <= j:
print(i, 'x', j, '=', i*j)

for i in range(2, 6):

if i % 2 == 0:
for j in range(2, 6):
if i <= j:
print(i, 'x', j, '=', i*j)

See notebook solutions for answers Iteration 2 8

 Concepts in this slide:
Nested loops for Using nested loops for
successive accumulations.
accumulation
def isVowel(char):
return char.lower() in 'aeiou'

verse = "Two roads diverged in a yellow wood"

for word in verse.split():
counter = 0
for letter in word:
if isVowel(letter):
counter += 1
print('Vowels in "'+ word + '" =>', counter)
To notice:
Vowels in "Two" => 1
• The accumulator variable counter is set
Vowels in "roads" => 2
to 0 every time the inner loop starts.
Vowels in "diverged" => 3
• Outer loop iterates over a list of words.
Vowels in "in" => 1
• Inner loop iterates over characters in a
Vowels in "a" => 1
Vowels in "yellow" => 2 string.
Vowels in "wood" => 2 Iteration 2 9
Flow Chart for
nested for loops

A flow chart diagram

to explain the code
execution for the
example in slide 9.

Iteration4-10
2 10
Avoiding Nested Loops with Functions
Encapsulating the inner loop into a separate function eliminates
the loop nesting and can make programs easier to read.
# Our old friend countVowels from Lec 08 encapsulates
# the inner loop of the nested loop example with vowels
def countVowels(word):
counter = 0
for letter in word:
if isVowel(letter):
counter += 1
return counter

# We can now use countVowels to avoid an explicit nested loop

# (though at runtime the for loop within countVowels still
# executes within the for loop within countVowelsInVerse
def countVowelsInVerse(verse):
for word in verse.split():
print('Vowels in "' + word + '" =>', countVowels(word))

countVowelsInVerse("Two roads diverged in a yellow wood")

Iteration 2 11
Exercise: print words
What is printed below? (Answers are in the notebook solutions).
for letter in ['b','d','r','s']:
for suffix in ['ad', 'ib', 'ump']:
print(letter + suffix)

Iteration 2 12
Exercise: Nested Loops with graphics
Here's a picture involving a grid of randomly colored circles with
radius = 50.
This picture is created using two nested for loops. How would you
do that? You can find the answers in the notebook!

(-200, 200)

(-100, 100)

(0, 0)

Iteration 2 13
Exercise: Triangles of Circles
Which of the 4 triangular
patterns of circles is created
by the following function?
colors = ["LightSkyBlue", "LightPink",
"LightSeaGreen", "PaleVioletRed"]

reset()
noTrace()

for x in coords:
for y in coords:
if y <= x:
teleport(x, y)
color(random.choice(colors))
begin_fill()
drawCircle(radius)
end_fill()
showPicture()

How can you change the

function to make the other
3 patterns? Iteration 2 14
 Concepts in this slide:
To swap the values of two
Swapping Values in Python variables, a third variable
is needed.

Imagine you have a list of numbers that you want to sort by swapping two
adjacent (neighbor) items every time one is smaller than the other. This is a
famous algorithm known as the “bubble sort”, and is usually implemented via
nested for loops. If you’re curious, read this page. You’ll learn how to implement
bubble sort in CS 230.

Start of list If we want to do the first swap of 3 and 2,

nums = [3, 2, 1, 4] can we write the following?
After 1st swap
nums = [2, 3, 1, 4] nums[0] = nums[1]
After 2nd swap nums[1] = nums[0]
nums = [2, 1, 3, 4]
After 3rd swap Try it out to see what happens. The
nums = [1, 2, 3, 4] solution in this case would look like this:

tempVal = nums[0]
nums[0] = nums[1]
nums[1] = tempVal
Iteration 2 15
 Concepts in this slide:
Simultaneous assignment It is possible to assign
values to multiple

in Python* variables in one

statement.

In Python, we can assign values to many variables at once, here are some
examples, that you should try in the console:

a, b = 0, 1 The reason that these assignments work is

a, b, c = 1, 2, 3 that there is an equal number of variables
a, b = "AB" and values on each side. Even the string
a, b = [10, 20] “AB” is a sequence of two characters.
a, b = (15, 25)
a, b, c, d = [1, 2, 3, 4] Try a different number of variables or values
on both sides to see what errors you get.

Swapping through simultaneous

assignment
Do these statements
a, b = b, a work?
num[0], num[1] = num[1], num[0]

*This is also known as tuple assignment. Iteration 2 16

Variable update order matters
def sumHalvesBroken(n):
sumSoFar = 0
while n > 0:
n = n//2 # updates n too early!
sumSoFar += n
return sumSoFar

step n sumSoFar
In [3]: sumHalvesBroken(22) 0 22 0
Out[3]: 19 1 11 11
2 5 16
Important: 3 2 18
If update rules involve rules 4 1 19
where state variables are 5 0 19
dependent on one another, be
very careful with the order of
updates.
Iteration 2 17
Simultaneous update example:
Greatest Common Divisor algorithm
o The greatest common divisor (gcd) of
integers a and b is the largest integer that
divides both a and b
o Eg: gcd(84, 60) is 12
o Euclid (300 BC) wrote this algorithm to compute the GCD:
o Given a and b, repeat the following steps until b is 0.
o Let the new value of b be the remainder of dividing a by b
o Let the new value of a be the old value of b
o … this is a perfect opportunity
for a while loop. step a b
0 84 60
1 60 24
2 24 12
3 12 0
Iteration 2 18
Simultaneous update (e.g., gcd)
step a b step a b step a b
0 84 60 0 33 24 0 33 7
1 60 24 1 24 9 1 7 5
2 24 12 2 9 6 2 5 2
3 12 0 3 6 3 3 2 1
4 3 0 4 1 0

Neither of the following two gcd functions works. Why?

# Assume a >= b > 0 # Assume a >= b > 0
def gcdBroken1(a, b): def gcdBroken2(a, b):
while b != 0: while b != 0:
a = b b = a % b
b = a % b a = b
return a return a

Iteration 2 19
Fixing simultaneous update
# Assume a >= b > 0 # Assume a >= b > 0
def gcdFixed1(a, b): def gcdFixed2(a, b):
while b != 0: while b != 0:
prevA = a prevA = a
prevB = b prevB = b
a = prevB b = prevA % prevB
b = prevA % prevB a = prevB
return a return a

Python’s simultaneous assignment is an even more elegant solution!

# Assume a >= b > 0
def gcdFixed3(a, b):
while b != 0:
a, b = b, a % b # simultaneous assignment of a
# pair of values to a pair
# of variables (parens optional)
return a

To notice:
- Functions 1&2 use temporary variables to store
values before updates.
- Function 3 assigns multiple values in one step.

Iteration 2 20
Test your knowledge
1. The sumBetween solution in slide 5 has an iteration table with three
state variables. How will the iteration table look like if the solution is
written with a for loop?
2. If we want to print out the entire multiplication table for 1 to 10, how
many times will the print statement in slide 7 be executed?
3. What would be the final value of counter in slide 9, if we move the
assignment statement before the outer for loop?
4. What results will be printed in slide 9 if the counter assignment statements
moves within the inner loop?
5. For the exercise in slide 12, try to draw a flow chart diagram like the one in
slide 10, before writing code to solve the problem.
6. What is an alternative way of writing the function in slide 17, which leads
to the same gotcha?
7. If you type 0, 1, 2 in the Python console, what kind of type will Python
assign to this sequence of numbers? How does that help for simultaneous
assignments?

Iteration 2 21