Algorithms

There is no good formal definition of algorithm. Very unformally:

• a step by step process to accomplish a task
• a recipe
• a guideline

Examples

Guideline how to use an extinguisher

Maze route Lee algorithm

      

Source: https://www.geeksforgeeks.org/minimum-steps-reach-target-knight/.

Find the minimal number of steps by which a Knight from a given start position can reach a given target position.

1. SET n to 0 and mark the start position of a Knight by 0.
2. WHILE the target position is not marked yet, do:
1. SET n to n+1.
2. Do FOR ALL positions that are marked by the number n-1:
   • Try all 8 possible positions where a Knight can reach from the position:
     IF reachable position is not already visited (and is inside the board),
     mark it by the number n.
3. The result is n.

The important fact used here is that from any given position, every other position is reachable in a finite number of steps.

---

Input, output data

Variables: means for remembering data (values)

Basic statements:

• assignement: SET some variable to some value
  
  
• control flow of the steps:
• conditional statement: IF some condition - causes branching of the flow
  
• loop control:
  • WHILE some condition - causes repetition;
    number of repetitions is not known in advance
  • FOR ALL elements in some list - causes repetition;
    number of repetitions is known in advance

What is algorithm - more precisely

An algorithm is a sequence of a FINITE number of ELEMENTARY steps,
that leads to solution of any problem belonging to a certain CLASS

Typical properties:

• Finitness: the process must always end, for any set of data from the given class.
• Repeatability: the proces can be repeated by any person (or machine) mechanically, even without understanding the method or purpose. Each steps in algorithm should be clear and unambiguous.
• General solution method: not just one particular problem; input data, output data.

How to write down an algorithm

• pictograph (like on extinguishers)
• text instructions
• flowchart
• programming language
• ...

Illustration of a Flowchart (while loop):

      

Source: http://www.trytoprogram.com/c-programming/c-programming-while-and-do-while-loop/

Program

Program is an algorithm written in a programming language.

THE advantage: it can be executed by a computer.

Illustration of programming languages

Problem:

John has a deposit of 8000 Kč with interest rate of 3%.
What would be the gross interest after 7 years?
(Assume the interest is assigned once a year.)

Analysis:

• the geometric sequence: a_n = a₀ * qⁿ
• a₀ ... the deposit = 8000
• q ... 1 + 1/100 times the interest rate = 1.03
• a_n ... the deposit after n years
• the gross interest: a_n - a₀

Algorithm:

Input: Deposit, Rate and N_years (numbers)
Output: Gross_interest

1. Read Deposit, Rate, N_years.
2. Set q to 1 + Rate/100.
3. Set Gross_interest to Deposit * q ^N_years - Deposit.
4. Print Gross_interest.

Algorithm executed for the given example:

1. Deposit = 8000, Rate = 3, N_years = 7
2. q = 1 + 3/100 = 1.03
3. Gross_interest = 8000 * 1.03 ⁷ - 8000 = 9839 - 8000 = 1839
4. Print 1839

Matlab:

% Computing of the gross interest:

Deposit = input('Give the deposit:');
Rate = input('Give the interest rate:');
N_years = input('Give the number of years:');

q = 1 + Rate/100;
Gross_interest = Deposit * q^ N_years - Deposit;

disp('The gross interest is');
disp(Gross_interest);

C:

#include <stdio.h>
main()
{
% Computing of the gross interest:

  int Deposit, Rate, N_years;
  float q, Gross_interest;

  printf("Give the deposit:");
  scanf("%d",&Deposit);
  printf("Give the interest rate:");
  scanf("%d",&Rate);
  printf("Give the number of years:");
  scanf("%d",&N_years);

  q = 1 + Rate/100.0;
  Gross_interest = Deposit * pow(q, N_years) - Deposit;

  printf("The gross interest is %f", Gross_interest);
}

---

Motivation (Excerpt from an interview with D. Knuth - the legendary IT scientist)

"As we express our design, we are explaining something to the computer. And to do that, we need to really understand what we are explaining. If I explain something to you, you will nod your head and I know you got it. When explaining things to a computer, you won’t get such feedback. The computer doesn’t nod its head. You have to explain things absolutely perfectly."

"Everybody who is designing computer programs needs to understand in great detail how things work."

---

Q:"If someone never coded, if someone doesn’t know any programming language, what are they missing about the world?"

A:"They are missing what it means to say something carefully and unambiguously. There was a TV show in the 60s where the secretary was a robot. It was amazing to some people that a computer would do exactly as told. Because people don’t work that way. This character – a very good-looking young lady – was a robot and people had to learn that they need to tell her everything exactly, not approximately."

Donald Knuth

Source: Donald Knuth: Programming is like nothing else. Become friends with geeks.