Classroom practice, week 1: Algorithms

The idea is as follows:

Let's print 1.
Let's print 2.
Let's print 3.
…
Let's print 10.

Observe that this solution is not precise enough. There a slight detail that has not been taken into account: each number should appear in a new line. A more precise solution is:

Let's print 1. I don't write anything into this line anymore.
Let's print 2. I don't write anything into this line anymore.
…
Let's print 10. I don't write anything into this line anymore.

Note that these are simple, repetitve steps, that are almost identical. The only difference between the instructions in the number to be written to the screen. Hence, we can put together a more general solution:

Let's consider number 1.
Print the number number to the screen. Start a new line.
Let's increment our number by one.
Print the number number to the screen. Start a new line.
Let's increment our number by one.
Print the number number to the screen. Start a new line.
Let's increment our number by one.
…

Describing this algorithm by pseudo-code leads to:

   1. Let's consider number 1.
   ↓
┌> 2. Print the number number to the screen. Start a new line.
│  ↓
│  3. Let's increment the number by one.
│  ↓
└─ 4. If the number is ≤ 10, go back to step 2
   ↓
   5. End.

   Let's consider number 1.
   ↓
┌> Repeat the following operations:
│    ↓
│    Print the number number to the screen. Start a new line.
│    ↓
│    Let's increment the number by one.
│    ↓
└─── Repeat again, if the number is ≤ 10, otherwise go on to the next line.
   ↓
   End.

   X = 1
   ↓
┌> While X ≤ 10, repeat:
│    ↓
│    Print X to the screen. Start a new line.
│    ↓
│    X = X+1
│    ↓
└─── End of repeatition.
   ↓
   End.

Testing is not required, it is enough to start the loop from 2 and increment the variable by 2 in each iteration.

In this case we have no choice, we need to go one-by-one and test all numbers whether they satisfy the criteria individually. We introduce conditional branches:

   X = 1
   ↓
┌> While X < 100, repeat:
│    ↓
│    If X is divisible by 3, and it is not divisible by 5, then:
│        ↓
│        Print X. Start a new line.
│    ↓
│    X = X+1
│    ↓
└─── End of repetition.
   ↓
   End.

We start at the least significant decimal digit. We add the two digits, and write down the last digit of the sum (between 0 and 9). If the result is greater than 10, we keep the first digit (that is 1, called carry) in mind, since we have to take it into consideration in the next step of the algorithm. These steps need to be repeated as long as we have further digits to add.

To obtain the next digit of the solution and the carry digit, we need to obtain the integer part and remainder part of the division by 10. If the sum of the digits is 13, the integer part of 13/10 is 1 (this will be the carry digit), and the remainder of the division is 3 (giving the next digit of the solution).

   1. Start with the least significant decimal digit
   ↓
┌> 2. Add up the digits below each other
│  ↓
│  3. If there is one, add up the carry digit from the previous iteration as well.
│  ↓
│  4. Divide it by 10, write down the remainder below the line.
│  ↓
│  5. If we have a carry (the integer part of the division), keep it in mind.
│  ↓
└─ 6. Move to a more significant position, If we still have digits (local values) left, jump back to step 2.

This is again an algorithm that is thaught in elementary school.

Let us review the algorithm through an example, number 120. We have to divide this number by primes, starting with 2 (that is the smallest prime number). If our number is divisible by 2 (without remainder), then we write down the prime (120|2 ), and actually perform the division on the number. If it is not divisible, then we try to divide it by the next prime number, till we find a proper prime divisor. These steps are repeated till our number, as the result of the subsequent divisions, reduces to 1.

Two small details need to be discussed before writing down the program. First of all, the next prime divisor is taken only when the division with the current one was not possible, hence, the number can potentially be divided by the same prime factor many times. Next, we don't have to restrict ourselves to prime divisors. In our example, we have to divide 120 by 2 three times (resulting 120/2/2/2=15), then by 3 once (giving 15/3=5), and then we can go on and try to divide it by 4 even if it is not a prime, since the division is going to fail anyway (as we divided by 2 as many times as we could). This observation simplifies the solution siginficantly.

   1. Ask the user for a number subject to prime factorization.
   ↓
   2. The smallest divisor to try is 2.
   ↓
┌> 3. Check if the number can be divided by the divisor without remainder.
│     ├─> If yes, then print: number | divisor; and perform the division.
│     └─> If not,  then try the next divisor.
│  ↓
└─ 4. While we do not reach 1, do again from line 3.
   ↓
   5. Print 1|.

120│2
 60│2
 30│2
 15│3
  5│5
  1│

It is possible to put together another solution as well, which is clearly visible from the example above. We first divided by 2, then again by 2, again and again till it was possible. In case of failure we can increment the divisor by one.

While this solution is essentially different from the previous one, still it provides the same output. Having very different solutions to the same problem is typical in programming.

      1. Ask the user for a number subject to prime factorization.
      ↓
      2. The smallest divisor to try is 2.
      ↓
┌> ┌> 3. If the number can be divided by the divisor,
│  │       print: number | divisor; and perform the division.
│  └──── Try again: if it was divisible, repeat line 3.
│     ↓
│     4. Increment the divisor by 1.
│     ↓
└──── 5. While we do not reach 1, do again from line 3.
      ↓
      6. Print 1|.