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

  • Sample execution of the Euclid's Algorithm: 

       A = 28      B = 36

    Steps executed by the Euclid's Algorithm: 

       Repeat until (A == 0 or B == 0):        
   {
      if ( A > B )                         # 28 > 36 --> No  
          replace A with the value (A - B)
      otherwise
          replace B with the value (B - A)    <--- do this 
   }

   if ( A is not equal to 0 )
      The Greatest Common Divisor = A
   otherwise
      The Greatest Common Divisor = B

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

  • Sample execution of the Euclid's Algorithm: 

       A = 28      B = 8

    Steps executed by the Euclid's Algorithm: 

       Repeat until (A == 0 or B == 0):        
   {
      if ( A > B )                         # 28 > 8 --> Yes  
          replace A with the value (A - B)    <--- do this 
      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

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

  • Sample execution of the Euclid's Algorithm: 

       A = 20      B = 8

    Steps executed by the Euclid's Algorithm: 

       Repeat until (A == 0 or B == 0):        
   {
      if ( A > B )                         # 20 > 8 --> Yes  
          replace A with the value (A - B)    <--- do this 
      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

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

  • Sample execution of the Euclid's Algorithm: 

       A = 12      B = 8

    Steps executed by the Euclid's Algorithm: 

       Repeat until (A == 0 or B == 0):        
   {
      if ( A > B )                         # 12 > 8 --> Yes  
          replace A with the value (A - B)    <--- do this 
      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

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

  • Sample execution of the Euclid's Algorithm: 

       A =  4      B = 8

    Steps executed by the Euclid's Algorithm: 

       Repeat until (A == 0 or B == 0):        
   {
      if ( A > B )                         #  4 > 8 --> No   
          replace A with the value (A - B)
      otherwise
          replace B with the value (B - A)    <--- do this 
   }

   if ( A is not equal to 0 )
      The Greatest Common Divisor = A
   otherwise
      The Greatest Common Divisor = B

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

  • Sample execution of the Euclid's Algorithm: 

       A =  4      B = 4

    Steps executed by the Euclid's Algorithm: 

       Repeat until (A == 0 or B == 0):        
   {
      if ( A > B )                         #  4 > 4 --> No   
          replace A with the value (A - B)
      otherwise
          replace B with the value (B - A)    <--- do this 
   }

   if ( A is not equal to 0 )
      The Greatest Common Divisor = A
   otherwise
      The Greatest Common Divisor = B

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

  • Sample execution of the Euclid's Algorithm: 

       A =  4      B = 0

    Steps executed by the Euclid's Algorithm: 

       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  <--- do this: GCD = 4 !
   otherwise
      The Greatest Common Divisor = B