Algorithms

New Concepts

• Variables
• Algorithms as distinct from programs
  • Algorithms are programs for human computers??
  • Algorithms have specified inputs and outputs
  • Algorithms have clear and precise instructions, yet written for humans, not machines
  • Algorithms should terminate and give correct answers
• Functions???
• Executing algorithms with pencil and paper (human computers)
• Efficiency and correctness of algorithms?
• Algorithms and freedom?

Introduction

You have learned, in the Hour of Code exercises, about the basic structures (“control structures”) of programs:

1. Sequence: a list of instructions, to be executed from first to last.
2. Iteration or repetition.
3. Selection or making decisions.

Variables

In addition to these control structures, most algorithms need to keep changing state. For example, the bird is sometimes angry, sometimes not. The zombie gets hungry. How hungry is the zombie? It varies. Both the bird and the zombie move around, changing position and direction. We use variables to keep tracking of changing state. (We did not see any variables in the Hour of Code, but there were certainly some variables under the hood.)

Think about keeping track of your score as you play a game. At the start of the game, you have zero points. If you score 5 points on your first move, you have 5 points. If you score 7 points on your second move, you then have 5 + 7 = 12 points. And if you score 4 points on the third move, you have 12 + 4 = 16 points. You keep a running total on a scoreboard, a sheet of paper, or in your head. This running total is a variable. It has a value, but the value changes over time. It is also stored somewhere (on the scoreboard, for example). And we can refer to it by some kind of name (for example, “my score”) or location (for example, if we have a single sheet of paper that tracks the scores of several players, then “the third score from the left on the score sheet”).

These are the characteristics of variables, then:

1. A variable has a name.
2. A variable has a storage location.
3. The storage location contains information that usually changes over time.

A variable is a little like a cell in a spreadsheet. The spreadsheet cell has an address, which is a storage location, and it sometimes has a name, and the information stored in the cell can change. But the values in a spreadsheet cell usually do not change so often as the values of a variable.

We can also think of the variable as like a named box containing some information (write your mother’s name on a sheet of paper and put it in a box). We can put new information in the box, but there is only room for one piece of information, so the new information will replace the old.

We need some notation conventions.

1. If N is a variable name and V is a value, then N ← V means that we store the value V into the variable N. For some reason, this operation is called assignment. After it happens, the value of N is V, until there is an assignment of a new value to the variable.

For example, weight ← 25 means we store 25 into the variable weight.

2. If we encounter a variable in an expression, then we understand it to mean the current value of the variable.

For example, weight + 3 means “the current value of weight + 3”. Immediately after the assignment weight ← 25, the value of weight + 3 would be 25 + 3 = 28.

A variable can be assigned a new value that depends on its current value. For example, after the sequence of instructions

weight ← 25, weight ← weight + 1

the value of weight would be 25 + 1 = 26.

Besides “N ← V”, there are a few other common notations for the assignment operation, some of them likely to cause confusion (and that is why we do not want to use them here):

• N = V
• let N = V
• N := V

Building a House

Suppose we want to build a house, square in floor plan, with a floor area of 1000 square feet. How long should the sides be?

[Related problems: a tower with a circular floor area of …, what is the radius? a cubical building with a volume of …; a spherical storage tank with a volume of …]

Geometry tells us the area of a square is the length of its side multiplied by itself: area = side². If we know the area, we need to solve the equation for side. Of course, that means finding the square root of area, and how do we do that?

• Invite suggestions; pressing the SQRT button on a calculator is not allowed, because we are interested in the method by which such a button would work; likewise using the SQRT function in a spreadsheet.
• Perhaps students will come up with one of the following algorithms.

Perhaps we need to clarify or specify the problem a little better. Let’s generalize the problem.

Finding Square Roots

• The input is a number x ≥ 0 (x could be the area, or in general the number of which we want the square root).
• The output is the positive number y such that y² = x. That’s what it means for y to be the square root of x.
• Procedure—to be specified.

How do we find this y? We will consider a number of different procedures to find the output y.

Procedure SquareRoot1

Would this procedure work?

1. y ← 0
2. If y² = x, output y and stop
3. y ← y + 1
4. Go to step 2.

Does it work with x = 25? How about x = 27? (The procedure does not terminate—no good!)

It works only if y is a perfect square—the square of a whole number.

Before going on to improve the algorithm, let’s look at a few other ways to express the procedure.

(Show this also as a flowchart and as structured pseudocode with a while loop.)

A flowchart is a graphical depiction of the procedure, with arrows connecting the steps.

(ADD FLOWCHART)

Here is the same procedure expressed as a structured procedure; the “repeat while” block repeats statements until its condition is false (the opposite of the “repeat until” from Hour of Code, which repeats statements until the condition is true):

1. y ← 0
2. Repeat while y² ≠ x, y ← y + 1
3. Output y

Roughly speaking, “structured” means without “go to” steps. Usually, the procedure with “go to” steps is more like the instructions in computer memory; but the structured form is closer to human ways of thinking, so we’ll normally prefer the structured pseudocode form of our algorithms.

Procedure SquareRoot2

Suppose we alter the problem specification a little.

• The input is a number x > 0 (x could be the area, or in general the number of which we want the square root). [no change here]
• The output is a number y which is the nearest whole number to the square root of x. I.e., we are settling for an approximation. (And in general, we might always have to settle for an approximation, since π is the square root of π², and π has infinitely many decimal digits. We cannot write them all out. The nearest whole number is a very crude approximation, though, and later we shall look into ways of getting closer than that.)

Here is our revised procedure, with “go to” steps:

1. y ← 0
2. If y² ≥ x, goto step 5
3. y ← y + 1
4. Go to step 2
5. If ∣y² − x∣ < ∣(y − 1)² − x∣, output y and stop
6. Output y − 1 and stop

Here the idea is, in step 2, if y² ≥ x, we have reached the point where y is greater than or equal to the square root of x, and y − 1 is less than the square root. Our best approximation will therefore be either y or y − 1. In steps 5–6, we look at y² and (y − 1)² and choose either y or y − 1 depending on which is closer to x.

(Again, show also the flowchart and structured pseudocode.)

ADD FLOWCHART

Here it is in structured form:

1. y ← 0
2. Repeat while y² < x, y ← y + 1
3. If ∣y² − x∣ < ∣(y − 1)² − x∣, output y; otherwise, output y − 1

Try it, for x = 25 and x = 27.

Is it correct?

How long does it take? Is it obvious that the number of repetitions, in step 2, is proporitional to the square root of x?

Procedure SquareRoot3

Okay, so now it looks like we have a procedure that will give us the nearest integer to the square root of x. Suppose we need greater precision—for example, we want the estimated square root to be accurate to three digits after the decimal point, like 5.000 for the square root of 25.

Could we not replace the 1’s in our procedure with 0.001’s, like this:

1. y ← 0
2. Repeat while y² < x, y ← y + 0. 001
3. If ∣y² − x∣ < ∣(y − 0. 001)² − x∣, output y; otherwise, output y − 0. 001

Can we see that this is correct?

But do we dare to try this, or is it obvious that it’s going to take 1000 times as long to execute?

Procedure SquareRoot4

What about going up by 1 until we get y² ≥ x, then backing up by 1 and going up by 1/10, then backing up by 1/10 and going up by 1/100, and finally backing up by 1/100 and going up by 1/1000?

Would this get us to the desired precision, but much faster than SquareRoot3?

How do we express this procedure?

One way would be to chain together four copies of SquareRoot2. In the second copy we replace 1 by 1/10, in the third, by 1/100, and in the fourth, by 1/1000.

This seems a bit awkward, but doable, for three digits. But if we wanted 15 digits precision, it would be ridiculous.

Fortunately, there is a better way, which scales up well if we need higher precision. We use nested loops: a “repeat while” within a “repeat while.”

1. y ← 0
2. step ← 1
3. Repeat while step > 0. 001,
   1. Repeat while y² < x, y ← y + step
   2. y ← y − step
   3. step ← step / 10
4. If ∣y² − x∣ < ∣(y − step)² − x∣, output y; otherwise, output y − step

Is this correct? Probably not. We have to back up in a few places, I think. FIX THIS.

Try it out ….

Procedure SquareRoot5

This procedure uses a method called bisection search. We are looking for something, namely the square root of x. Clearly, the square root is  < x if x ≥ 1, but  > x if x < 1 (for example, think about the square roots of 4 and 1/4). Bisection search works by setting upper and lower limits and looking in the middle of the range:

• upper limit = x, if x ≥ 1; otherwise 1
• lower limit = 0
• y(upperlimit + lowerlimit) / 2

Our “search space” is the range between (lower limit) and (upper limit). Since the square root increases with x (show a plot and consider, for example, 25 > 16 and the square root of 25 is greater than the square root of 16), if y² > x, it is too high, and we can replace the upper limit with y. If y² < x, it is too low, and we can replace lower limit with y. If y² = x, of course, we are done.

We have now an extra input, the desired precision of the calculation, so we will respecify the inputs and outputs of the algorithm:

• The inputs are:
  1. A number x ≥ 0 (x could be the area, or in general the number of which we want the square root).
  2. A number, precision, (for example, 0.001), which specifies how close an estimate we want, i.e., the maximum allowable error (the absolute difference between the output and the true square root of x).
• The output is an estimate of the square root of x, which is accurate within the requested precision. That is, the output is a number y such that ∣y − z∣ ≤ precision, where z is the true square root of x.
• The procedure is:
  1. upperLimit ← (x if x ≥ 1, otherwise 1)
  2. lowerLimit ← 0
  3. y ← (upperLimit + lowerLimit) / 2
  4. Repeat while upperLimit − lowerLimit > precision
     1. if y² > x, upperLimit ← y; otherwise, if y² < x, lowerLimit ← y; otherwise, output y
     2. y ← (upperLimit + lowerLimit) / 2
  5. output y

How well does this work?

• Correctness?
• Speed (number of steps)?

Procedure SquareRoot6

This procedure uses Newton’s method. We will not attempt to explain why this works; understanding that would require calculus, which is beyond the prerequisite for this course. You will just have to take it on faith; or, if you’re inclined to be skeptical, take a course in calculus.

…