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