What is an computer program ?

- Computer program = a series of instructions/commands that is executed by the computer Note:
  A computer is a machine and cannot think !!!
- Some computer programs are used to solve complex problems
  These computer programs are called "algorithms"
Algorithm = a step-by-step procedure for solving a problem or accomplishing some task A computer algorithm must be spelled out in simple steps that a (non-thinking) machine (like a computer) can understand

What is not a computer algorithm

- Consider the following steps to change a light bulb:
        Remove the light bulb
        Insert a new light bulb
- A computer cannot execute these steps because:
  A computer does not understand how to remove a light bulb A computer does not understand how to insert a light bulb
- Remember that:
  A computer algorithm must be spelled out in simple steps that a (non-thinking) machine (like a computer) can understand

What does a computer algorithm look like ?

- A computer algorithm to change a light bulb would look like this:
         repeat until the light bulb comes out of socket
         {
            turn light bulb in counter-clockwise direction
         }

         pick a new light bulb

         repeat until the light bulb is secure in socket
         {
            turn light bulb in clockwise direction
         }
You can see that computer algorithms uses very simple operations

A famous algorithm to find the Greatest Common Divisor of 2 numbers

- Euclid's Algorithm to find the Greatest Common Divisor of numbers `A` and `B`:
         Repeat until (A == 0 or B == 0):
         {
            if ( A > B )
                replace A with the value (A - B)
            otherwise
                replace B with the value (B - A)
         }

         if ( A is not equal to 0 )
            The Greatest Common Divisor = A
         otherwise
            The Greatest Common Divisor = B
Recall that a computer can perform arithmetic operations, this includes comparing 2 numbers !

A famous algorithm to find the Greatest Common Divisor of 2 numbers

See how the Euclid's Algorithm works with an example:

      Find the Greatest Common Divisor of A=28 and B=36

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Let's execute the Euclid's Algorithm ourselves (you are pretending to be a computer !)

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

We will execute this step:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)    <------
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

We will execute this step:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)     <------
          otherwise
              replace B with the value (B - A)
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

We will execute this step:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)     <------
          otherwise
              replace B with the value (B - A)
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

We will execute this step:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)     <------
          otherwise
              replace B with the value (B - A)
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

We will execute this step:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)      <------
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

We will execute this step:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)      <------
       }

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 1 of Euclid's Algorithm:

       As long as neither number is equal to zero (0) do
       {
          if ( A > B )
              replace A with the value (A - B)
          otherwise
              replace B with the value (B - A)
       }

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Step 1 ends and we continue to step 2:

     Step 2 of Euclid's Algorithm:

       if ( A > 0 )
          The Greatest Common Divisor is A
       otherwise
          The Greatest Common Divisor is B

Question: what will the algorithm do next ?

A famous algorithm to find the Greatest Common Divisor of 2 numbers

Result:

     Step 2 of Euclid's Algorithm:

       if ( A > 0 )
          The Greatest Common Divisor is A       <----
       otherwise
          The Greatest Common Divisor is B

Result: the greatest common divisor of 28 and 36 is 4

❮ ❯