Iteration

From CDS 130

Jump to: navigation, search

Iteration

Contents

  1. Objectives
  2. Motivation
  3. Priming questions
  4. Overview Video
  5. Notes
    1. Iteration Motivation
    2. Example use
    3. Example use
    4. Motivation for short-hand
    5. Iteration short-hand
    6. For loop basic pattern
    7. For loop basic pattern
    8. Syntax rules
    9. Syntax conventions
    10. Syntax conventions continued
    11. Basic pattern example I
    12. Basic pattern example II
    13. For loop general pattern
    14. General pattern example I
    15. General pattern example II
    16. General pattern example IV
    17. Populating an Array
    18. Populating an Array
    19. An additional short-hand
  6. Questions
    1. Basic Pattern
    2. Basic pattern
    3. Syntax
    4. Syntax
    5. Syntax
    6. Syntax
    7. Syntax
    8. Syntax
    9. Long-hand to short-hand
    10. Long-hand to short-hand
    11. Long-hand to short-hand
    12. Short-hand to long-hand
    13. Short-hand to long-hand
    14. Short-hand to long-hand
    15. Short-hand to long-hand
    16. Populating an Array
    17. Populating an Array
    18. Iteration with arrays
    19. Create an array using a for loop
  7. Activities
    1. Introduction to Iteration
      1. Part 1
      2. Part II
      3. Part III
      4. Part IV
      5. Part V
      6. Part VI
    2. Computing Limits
      1. Part I
      2. Part II
      3. Part IV
  8. Tutorial
    1. Evaluating a loop
      1. Step 1
      2. Step 2
      3. Step 3
      4. Step 4
    2. Short-hand cont.
    3. Short-hand cont.
    4. Question
    5. Answer

1. Objectives

  • To introduce the concept of iteration.
  • To introduce the concept of a counter variable.
  • To show how iteration is performed using a for loop.

2. Motivation

  • Almost all computer models of science models require iteration.

3. Priming questions

  • Give an example of a calculation in which each calculation requires the answer from a previous calculation.

4. Overview Video

An older video that covers some of the same issues is available at [1].

5. Notes

5.1. Iteration Motivation

  • In computing, iteration means "repeat calculation".
  • Simulating a model of a physical system usually requires iteration.

5.2. Example use

Suppose the population of the number of rabbits on an island doubles every year and the population was initially 10 rabbits. The population in year 2 could be computed by entering

P = 10;   % Assign to a variable named P the value 10.
P = 2*P;  % Assign to a variable named P the previous value of P times 2.

5.3. Example use

To compute the population in year 5, the following could be entered

P = 10;   % Year 1
P = 2*P;  % Year 2
P = 2*P;  % Year 3
P = 2*P;  % Year 4
P = 2*P   % Year 5

Note that the I have repeated the commands P = 2*P four times. Also recall that MATLAB ignores everything after and including the percent sign.

5.4. Motivation for short-hand

  1. You want to compute the population in year 1000.
  2. You don't want to type all of the commands required to do the computation.

5.5. Iteration short-hand

  • There are several types of short-hand syntax for iteration. The most commonly used is the for loop syntax. (In programming, the word "loop" means repeat). The while loop can also be used for iteration.
  • The key task in programming with iteration is finding the parts of the program that can be re-written using short-hand syntax.

5.6. For loop basic pattern

A for loop is short-hand syntax that allows you to re-write a set of statements as something that (usually) requires fewer lines.

Long-hand pattern:

P = 2*P;
P = 2*P;
P = 2*P;
P = 2*P

Short-hand using for loop:

for i = [1,2,3,4]  % Line A.
  P = 2*P;         % Line B.
end                % Line C.

The lines in this statement are interpreted as (MATLAB ignores everything including and after the %):

  • Line A: Set a counter variable i to the first value in the array [1,2,3,4], which is 1.
  • Line B: Do the computation P = 2*P;
  • Line C: If all of the possible values of i in the list [1,2,3,4] have been used, end this loop and continue to the next line. Otherwise, repeat everything between the for and end lines again with the next value of i in the list (which is 2).

In this example, there was only one line between the for and end lines. This is not required. Later, we'll put multiple lines between them.

5.7. For loop basic pattern

Example of replacing basic pattern with a for loop. Note that the first line does not fit the pattern and cannot be shortened.

Original program:

P = 10;
P = 2*P;
P = 2*P;
P = 2*P;
P = 2*P;

Shorthand using for loop:

P = 10;
for i = [1,2,3,4]
  P = 2*P;
end

What will happen if you replace i = [1,2,3,4] with i = [7,8,9,10] or i = [1,3,5,7]?

In this case, you will get the same result. The part between the for and end is repeated as many times as there are numbers between the square braces. In all of these cases, there are four numbers between the square braces.

As we will see, if the part between the for and end includes a reference to i, the result will not always be the same.

5.8. Syntax rules

  • Every for statement must have an associated end statement.
  • The for and end statements must be lower case.

5.9. Syntax conventions

The for and end are usually aligned vertically. This is allowed:

for i = [1,2,3,4]
    P = 2*P;
    end

but this is easier (for humans) to read:

for i = [1,2,3,4]
  P = 2*P;
end

5.10. Syntax conventions continued

The repeated part is usually indented. This is allowed:

for i = [1,2,3,4]
a = 1;
end

but this is easier to read:

for i = [1,2,3,4]
  a = 1;
end

5.11. Basic pattern example I

Original program:

x = 10;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 13;

The middle four statements are repeated four times, so they can be re-written using a for loop.

x = 10;
for i = [1,2,3,4]
  x = x+1;
end
x = x + 13;

This will give the same result

x = 10;
for i = [1,5,10,20]
  x = x+1;
end
x = x + 13;

5.12. Basic pattern example II

Original program:

a = 0;
z = a+1;
a = z+1;
z = a+1;
a = z+1;

In this case, the repeated part takes up two lines and is repeated twice.

a = 0;
for i = [1,2]
   z = a+1;
   a = z+1;
end

This will give the same result

a = 0;
for i = [99,101]
   z = a+1;
   a = z+1;
end

5.13. For loop general pattern

Thus far, we have used the number of values between the square braces as an indicator of how many times the repeated part should be repeated. It turns out that what is actually happening when we enter

for i = [1,2]
  P = 2*P;
end

is that MATLAB is executing the commands

i = 1;
P = 2*P;
i = 2;
P = 2*P;

That is, prior to executing the commands between the for and end, MATLAB is assigning a value to the counter variable.

If you see a set of short-hand commands like this

for i = [19,20]
  P = 2*P;
end

internally, MATLAB does the following set of commands

i = 19;
P = 2*P;
i = 20;
P = 2*P;

5.14. General pattern example I

The set of commands on the left are equivalent to the set of commands on the right.

for i = [1,2,3,4]
  a = i*i;
end
i = 1;
a = i*i;
i = 2;
a = i*i;
i = 3;
a = i*i;
i = 4;
a = i*i;

The set of commands on the left are equivalent to the set of commands on the right.

for i = [10,11,12,14]
  a = i*i;
end
i = 10;
a = i*i;
i = 11;
a = i*i;
i = 12;
a = i*i;
i = 14;
a = i*i;

5.15. General pattern example II

In this example, the first two lines must be repeated. The rest follows the general pattern of a counter variable being assigned a value and then an statement that appears multiple times.

i = 1;
a = 13;
i = 2;
a = i*i;
i = 3;
a = i*i;
i = 4;
a = i*i;
i = 1;
a = 13;
for i = [2,3,4]
  a = i*i;
end

5.16. General pattern example IV

In this example, only the part after the first two lines fits the basic pattern and the Do something (repeated) part takes up two lines. That is, the statements

a = i*i
a = a+1;

are repeated three times.

i = 1;
a = 13;
i = 2;
a = i*i;
a = a+1;
i = 3;
a = i*i;
a = a+1;
i = 4;
a = a+1;
a = i*i;
i = 1;
a = 13;
for i = [2,3,4]
  a = i*i;
  a = a+1;
end

5.17. Populating an Array

Thus far, we have only used the counter variable on the right-hand side of the equals sign. We can also use it to help assign values to elements of an array. The following for loop gives the same result

clear;
for i = [1:3]
  A(i) = i;
end
A

as

clear
i = 1;
A(i) = i; % A(1) = 1;
i = 2;
A(i) = i; % A(2) = 2;
i = 3;
A(i) = i; % A(3) = 3;
A

Note that the same array could have been created using

clear;
A = [1,2,3];
A

5.18. Populating an Array

We can also modify the counter variable inside of the for loop:

clear;
for i = [0:2]
  B(i+1) = i*i;
end
B


which is the same as

clear;
i = 0;
B(i+1) = i*i; % B(0+1) = 0*0, which is B(1) = 0;
i = 1;
B(i+1) = i*i; % B(1+1) = 1*1, which is B(2) = 1;
i = 2;
B(i+1) = i*i; % B(2+1) = 2*2, which is B(3) = 4;

5.19. An additional short-hand

There is a short-hand notation that can be used in for loops. Instead of writing

[1,2,3,4,5,6,7,8,9,10]

we can write

[1:1:10]

which is read "Start at 1 and increment in steps of 1. Stop at 10." This notation can also be used to count down.

[10,9,8,7,6,5,4,3,2,1]

can be written as

[10:-1:1]

which is read "Start at 10 and count down in steps of 1. Stop at 1."

Note that the middle number can sometimes be omitted. If it is omitted, it is assumed to be 1.

[1:10]

is the same as

[1:1:10]

6. Questions

6.1. Basic Pattern

Can any part of the following be re-written using a for loop?

b = 1;
b = b+1;
b = b+1;
b = b+1;

6.2. Basic pattern

Can any part of the following be re-written using a for loop?

b = 1;
b = b+1;
c = 2*b;
b = b+1;
c = 2*b;
b = b+1;
c = 2*b;

6.3. Syntax

What is wrong with each of the following for loops?

for i = [1,2,
  a = i;
end
for j = [1,2,3]
  b = 1;
End
for j = [1,2,3]
  c = a;
end

6.4. Syntax

Are these two sets of commands equivalent?

i = 1;
b = 3+i;
i = 2;
b = 4+i;
for i = [1,2]
  b = 3+i;
end

6.5. Syntax

What will happen when these commands are executed?

for i = [3,4]
  b = 3+i
  i
end

6.6. Syntax

What will happen when these commands are executed?

for i = [3,4]
  i
  b = 3+i
end

6.7. Syntax

What will happen when these commands are executed?

for i = [1:2:100]
  i
end

6.8. Syntax

What will happen when these commands are executed? What will the final value of the variable named counter be?

counter = 0;
for i = [3:100]
  counter = counter + 1
end

6.9. Long-hand to short-hand

Using a for loop, write the short-hand version of

i = 1;
a = i-13;
i = 2;
a = i-13;
i = 3;
a = i-13;
i = 4;
a = i-13;

6.10. Long-hand to short-hand

Using a for loop, write the short-hand version of

q = 37;
q = 1;
q = 38;
q = q*10;
q = 39;
q = q*10;
q = 40;
q = q*10;

6.11. Long-hand to short-hand

Using a for loop, write the short-hand version of

i = 1;
a = i;
i = 2;
a = i;
i = 3;
a = i;

6.12. Short-hand to long-hand

clear;
B = 111;
for j = [1:4]
  B = B+1;
end
B = B + 12;





Write the long-hand version of the program to the left.

6.13. Short-hand to long-hand

Write the long-hand version of

a = 0;
for z = [1,2,3]
   a = a + 1;
end
a = 13;
b = a+1;

6.14. Short-hand to long-hand

Write the long-hand version of

for j = [1,2,3,4]
  b = j*j;
end

6.15. Short-hand to long-hand

Write out the long-hand version of each of the two programs. Use the long-hand version to explain why they give different values for B.

clear;
B = 111;
for q = [1:3]
  B = B+1;
end
B = B + 12













clear;
B = 111;
for q = [1:3]
  B = B+q;
end
B = B + 12

6.16. Populating an Array

What are the values of the array B after the following program is executed?

clear;
for i = [1:4]
  B(i) = i+1;
end
B

6.17. Populating an Array

What is displayed when the following program is executed?

clear;
for i = [-1:2]
  C(i+2) = i*i;
end
C

6.18. Iteration with arrays

Write down the values of A(2), A(3), A(4), and A(5) after this loop has executed.

A(1) = 3
for i = [2,3,4,5]
  A(i) = i*A(i-1)+i*i
end

6.19. Create an array using a for loop

Rewrite the following using the a for loop:

A(1) = 1;
A(2) = 2;
A(3) = 3;

7. Activities

7.1. Introduction to Iteration

In this in-class activity, you will learn a bit about MATLAB syntax.

In addition, the problem you work will prepare you for the next MATLAB task - to write a program that uses iteration.

7.1.1. Part 1

Before starting MATLAB, work the following problem by hand on paper.

The population of rabbits on an island is 10 at the start of year 1. A biologist has predicted that the population doubles every year.

If you enter on the MATLAB command line

p = 10

corresponding to the population at the start year 1, MATLAB interprets this to mean that you want to assign to the variable named p the value of 10.0.

If you then enter

p = p*2

MATLAB will interpret this statement as "Assign the value of p to the current value of P times 2" and display the new value of p, which is 20. This is the population at the start of the second year.

Question Suppose that you next entered

p = p*2

what do you expect MATLAB to display? _____________

Now suppose that you entered

clear

and then entered

p = p*2

What do you think will be the result? ____________

7.1.2. Part II

Start MATLAB and enter the statements from Part I on its command line.

Use MATLAB to compute the population of rabbits at the start of the 10th year.

Write your answer here: __________

7.1.3. Part III

Suppose the initial population of rabbits was 6 at the start of the first year. Use MATLAB to determine the population at the start of the 10th year.

Use MATLAB to compute the population of rabbits at the start of the 20th year.

Write your answer here: _________

7.1.4. Part IV

(I'll stop the class and show you how to do this. Feel free to try this before I give instructions!)

Entering commands on the command line can be tedious. An alternative way to achieve the same result is to type the commands into a file (MATLAB calls these "m" files because their name ends with ".m").

Open a file and name it rabbits. Copy and paste the following into the file

p = 10
p = p*2
p = p*2
p = p*2
p = p*2

Now select the green "play" button. The effect is the same as if you had entered in the above lines one-by-one at the command line.

Now put a semicolon (;) at the end of each of the lines you pasted into the file (except for the last one).

Why do you see less text displayed?

What do you expect to see if you put a semicolon at the end of the last line? Try it.

7.1.5. Part V

Compute the population of rabbits in year 20 by entering in commands into your "m" file. Do this for the case where the initial population was 6 and then do it for the case of an initial population of 10. (Hint - to get an answer for an initial population of 10, you only need to modify one line of the program that does the computation for an initial population of 6.)

7.1.6. Part VI

(I'll stop the class and give you instructions before you start this. If you finished the previous parts early, see if you can figure out how to change the programs that you wrote so that the number 2 only appears once in your m file.)

Create a new file named rabbitsIteration. Use a for loop to compute the population of rabbits at the start of year 20 assuming an initial population of 10. Compare your answer to that obtained previously.

7.2. Computing Limits

7.2.1. Part I

Write out the long-hand version of this program on paper. What will be the value of a after the program is executed?

a = 1/13
for i = [3,4,5]
  a = a + 1/i
end

Write out the long-hand version of this program on paper. What will be the value of a after the program is executed?

a = 1/13
for i = [5,4,3]
  a = a + 1/i
end

7.2.2. Part II

Based on you answer to the previous problem, do you expect these two programs to give the same result?

a = 1/13
for i = [1,2,3,4,5,6,7,8,9,10]
  a = a + 1/i
end
a = 1/13
for i = [10,9,8,7,6,5,4,3,2,1]
  a = a + 1/i
end


7.2.3. Part IV

Should the following two programs give the same answer? Do they?

What happens if you replace the 1000 in both programs with 100000 or 10000000? (The format long statement tells the program to display more decimal places than the default.)

a = 1/13;
for i = [1:1000]
  a = a + 1/i;
end
format long
a
a = 1/13;
for i = [1000:-1:1]
  a = a + 1/i;
end
format long
a

8. Tutorial

This tutorial covers an alternative technique for converting a for loop to a sequence of equivalent commands.

8.1. Evaluating a loop

A(1) = 1;
for i = [1,2,3,4,5,6]
  A(i+1) = A(i)+1;
end

To figure out what a loop does, break it down into two columns: Index and Body.

  • The Index is i (Index is always the variable between the for and =)
  • The Body is A(i+1) = A(i)+1

The result of each iteration can be broken down into three steps:

8.1.1. Step 1

Write down the Index and Body in a table

Index Body Comments
i=1 A(i+1) = A(i) + 1 (write down what is in the body)

8.1.2. Step 2

Replace any i in the Body part with the current value of Index

Index Body Comments
i=1 A(i+1) = A(i) + 1 (write down what is in the body)
i=1 A(1+1) = A(1) + 1 (replace i with 1 in all parts of Body)

8.1.3. Step 3

Do any math.

Index Body Comments
i=1 A(i+1) = A(i) + 1 (write down what is in the body)
i=1 A(1+1) = A(1) + 1 (replace i with 1 in all parts of Body)
i=1 A(2) = A(1) + 1 (only one math operation needed this time)

8.1.4. Step 4

Insert numbers for known array values. We know A(1) because in the first line we said A(1)=1, so replace A(1) with 1

Index Body Comments
i=1 A(i+1) = A(i) + 1 (write down what is in the body)
i=1 A(1+1) = A(1) + 1 (replace i with 1 in all parts of Body)
i=1 A(2) = A(1) + 1 = 2 (only one math operation needed this time)
i=1 A(2) = 1 + 1 = 2 (replace any known array values with a number)

8.2. Short-hand cont.

After the body is evaluated, the next line says "end". It means "if you have used all of the possible values of i, then you can continue. Otherwise, go back to the body with the next value of i in the list.

Step 1

Index Body Comments
i=2 A(i+1) = A(i) + 1 (Body is same as for i=1, only now i=2)

Step 2

Index Body Comments
i=2 A(i+1) = A(i) + 1
i=2 A(2+1) = A(2) + 1 (replace i with 2)

Step 3

Index Body Comments
i=2 A(i+1) = A(i) + 1
i=2 A(2+1) = A(2) + 1
i=2 A(3) = A(2) + 1

Step 4

Index Body Comments
i=2 A(i+1) = A(i) + 1
i=2 A(2+1) = A(2) + 1
i=2 A(3) = A(2) + 1
i=2 A(3) = 2 + 1 Because we know A(2) = 2 from previous iteration (when i was equal to 1).

8.3. Short-hand cont.

The end result

Index Body
i=1 A(2) = 2
i=2 A(3) = 3
i=3 A(4) = 4
i=4 A(5) = 5
i=5 A(6) = 6
i=6 A(7) = 7

8.4. Question

What will this do? Use the "table" method shown on the previous slides

A(1) = 1
for i = [1,2,3,4,5,6]
  A(i+1) = A(i)+i
end
Index Body
i=1 ?

8.5. Answer

What will this do? Use the "table" method shown on the previous slides

A(1) = 1
for i = [1,2,3,4,5,6]
  A(i+1) = A(i)+i
end
Index Body
i=1 A(i+1) = A(i)+i
i=1 A(1+1) = A(1)+1
i=1 A(2) = 1 +1
i=1 A(2) = 2
i=2 A(i+1) = A(i)+i
i=2 A(2+1) = A(2)+2
i=2 A(3) = 2 +1
i=2 A(3) = 3
i=3 A(i+1) = A(i)+i
i=3 A(3+1) = A(3)+3
i=3 A(4) = 4 +3
i=3 A(4) = 7
i=4 A(i+1) = A(i)+i
i=4 A(4+1) = A(4)+4
i=4 A(5) = 7 +4
i=4 A(5) = 11
Personal tools