#separator:tab #html:true #tags:algorithms-and-programs-quiz #columns:Front Back

Someone holds up coloured cards, and you follow four steps: look at the card, decide which colour it is, write down its symbol, wait for the next card. What makes these instructions an algorithm?

  1. That they could be transferred to a computer, since only what a machine could execute counts as an algorithm.
  2. That the steps are described so precisely that you can carry them out without understanding what they are for.
  3. That they consist of a few manageable steps that you can remember without writing them down.
  4. That they are written in a programming language, since only a fixed syntax turns instructions into an algorithm.

An algorithm is defined by the precision of its steps, not by the machine or the language.

What is the difference between an algorithm and a program?

  1. A program is the advanced stage of an algorithm, needed only once a problem becomes too large to handle by hand.
  2. An algorithm describes how to compute; a program defines how the data for it are stored and managed.
  3. A program is the same procedure, but written down so completely that a machine can carry it out.
  4. There is no essential one: both are unambiguous sequences of steps, and which word you use depends on the field.

A program is a list of instructions that a computer follows exactly and in order, so it must not rely on anyone filling in what was meant.

What do you see on the lamp when this program runs?

lamp.set_color(255, 0, 0)
time.sleep(1)
lamp.set_color(0, 0, 255)
  1. One second of red, then blue.
  2. Red and blue at once, so violet.
  3. Only blue, because the first line is skipped.
  4. Only red: the lamp keeps the first colour it receives until the program ends.

The computer carries out the lines in the order in which they stand, and each one changes the state that the next one finds.

"

Someone is puzzled: ""The lamp never turns red, but the line is right there!"" What is going on?

lamp.set_color(255, 0, 0)
lamp.set_color(0, 0, 255)
  1. The first line contains a bug that the machine silently skips; otherwise red would have to show.
  2. The second line replaces the first before that one runs: with two commands of the same kind only the last one counts.
  3. Red does show, but only for a tiny fraction of a second; without a wait that is invisible to the eye.
  4. The lamp is sluggish: with two commands this close together only the last one gets through, and the first is lost in the hardware.
"

A computer waits only where the program tells it to wait.

What role does the part (255, 0, 0) play in this line?

lamp.set_color(255, 0, 0)
  1. It says which lamp is addressed: the three numbers identify which of several lamps is meant.
  2. It says with which values the instruction runs: full red, no green, no blue.
  3. It is a note for readers that explains the intended amount of red; only the part before the brackets is carried out.
  4. It says how long the instruction runs: for 255 milliseconds, after which the lamp is off again.

An instruction names a thing, what should happen to it and with which values; change the values, and the result changes while the instruction stays the same.

What is the benefit of the first line, bright = 255?

bright = 255
lamp.set_color(bright, 0, 0)
time.sleep(1)
lamp.set_color(bright, bright, 0)
  1. The program runs faster because the machine reads the value only once instead of anew at every call.
  2. Without it the lamp would stay dark, since this line is what sets the brightness to its maximum.
  3. The brightness can be changed in exactly one place instead of at every use.
  4. Names are mandatory: an instruction like set_color accepts only named values, not bare numbers in the brackets.

A value with a name gives you one place to change instead of many.

Roughly how long does this program run, and what does the lamp show?

colors = [(255, 0, 0), (0, 255, 0),
          (0, 0, 255), (255, 255, 0)]
for r, g, b in colors:
    lamp.set_color(r, g, b)
    time.sleep(1)
  1. One second: the loop shows all four colours at once.
  2. About four seconds: four passes, each showing one colour for one second.
  3. Forever: a for loop runs until you stop it.
  4. Four seconds, but only the last colour, yellow, is ever visible.

A loop is a way of writing: the same lines run once per value, one pass after another.

Roughly how long does this program run in total?

colors = [(255, 0, 0), (255, 255, 0), (0, 0, 255)]
for r, g, b in colors:
    lamp.set_color(r, g, b)
    if (r, g, b) == (255, 255, 0):
        time.sleep(3)
    else:
        time.sleep(1)
  1. 3 seconds
  2. 9 seconds
  3. 5 seconds
  4. 4 seconds

A condition is checked anew in every pass, so the run depends on the value at hand.

Which building blocks is every program made of? Tick all that belong. (Several answers may be correct.)

  1. Instructions that run one after another.
  2. Values that get a name.
  3. Repetition.
  4. Conditions: something happens only if something holds.

All four together are the whole building material: sequence, named values, repetition and condition.

"

Your program stops with this message. What do you make of it?

Traceback (most recent call last):
  File ""blink.py"", line 7, in <module>
    lamp.set_colour(255, 0, 0)
AttributeError: 'Lamp' object has no attribute 'set_colour'. Did you mean: 'set_color'?
  1. The computer crashed; after a restart the program usually works again, since messages like this come and go.
  2. The message states file, line and cause: line 7 says set_colour, which does not exist; set_color was meant.
  3. The program overwhelms the machine; the message shows that it could not keep up when running line 7.
  4. The message is a warning you can read past: the program continues after line 7, and the lamp lights up anyway.
"

The computer carried out what was written and reports exactly where it got stuck; the last line of the message names the cause.

When does this program end?

while True:
    lamp.set_color(255, 0, 0)
    time.sleep(1)
    lamp.set_color(0, 0, 255)
    time.sleep(1)
  1. Once both colours have been shown, because then the body of the loop has been carried out completely.
  2. By itself after a while, when the machine notices that nothing new happens.
  3. Never: the condition is always true, and the body of the loop has no way out.
  4. After a fixed number of repetitions, because every loop has a built-in upper limit so that the machine does not get stuck.

A loop ends only when its end is reachable; while True without a way out runs for ever.

In the guessing game from 1 to 100, two procedures are certain to succeed: asking for every number one by one (up to 99 questions) or halving the range (at most 7 questions). What follows?

  1. Only halving deserves the name algorithm; asking one by one is mere trial without a procedure.
  2. A solution can be correct and still useless; procedures are compared by their cost.
  3. On modern computers the difference no longer matters, since both procedures finish in a fraction of a second anyway.
  4. The slow procedure is safer because it checks every number explicitly, and is therefore preferable.

What matters is how the cost grows with the size of the problem.

Six people sort themselves by height with these rules: look at your right neighbour, swap places if you are taller, start again from the left at the end of the row. How does this procedure know that it is finished?

  1. After exactly one pass through the row, because by then every person has checked their neighbour once.
  2. When the people can see that the row looks sorted.
  3. By a complete pass in which nobody swapped.
  4. Not by itself: as with any repetition that starts over, someone from outside has to stop it once the row is right.

Bubble sort ends by its own rule: a pass without a swap.

What does the lamp show when this program runs?

lamp.set_color(255, 0, 0)
lamp.set_color(0, 0, 255)
time.sleep(1)
  1. Red for one second, then blue: the time.sleep(1) obviously belongs to the red phase.
  2. Blue for one second, then red: the pause holds the colour set last, and the first line is caught up on afterwards.
  3. Red only for a split second, then blue for one second.
  4. The program is faulty and does not start, because time.sleep(1) is not allowed as the last line.

No line is missing, and still the order makes it a different program.