Algorithm

• • • A finite sequence of precise instructions for performing a computation or for solving a problem

    • A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data.

Properties of Algorithms

• 1. Input -An algorithm has input values from a specified set.

  2. Output -From each set of input values an algorithm produces output values from a specified set. The output values are the solution to the problem.

  3. Definiteness -The steps of an algorithm must be defined precisely.

  4. Correctness -An algorithm should produce the correct output values for each set of input values.

  5. Finiteness -An algorithm should produce the desired output after a finite (but perhaps large) number of steps for any input in the set.

  6. Effectiveness -It must be possible to perform each step of an algorithm exactly and in a finite amount of time.

  7. Generality -The procedure should be applicable for all problems of the desired form, not just for a particular set of input values

Pseudocode

• • • a notation resembling a simplified programming language, used in program design

    • It uses the structural conventions of a normal programming language, but is intended for human reading rather than machine reading. 

      • It typically omits details that are essential for machine understanding of the algorithm, such as variable declarations

    • The purpose of using pseudocode is that it is easier for people to understand than conventional programming language code, and that it is an efficient and environment-independent description of the key principles of an algorithm. 

Flowchart

• • • A flowchart is the graphical representation of an algorithm that uses different symbols, shapes and arrows in order to demonstrate a process or a program. 

    • The main purpose of a flowchart is to analyze different processes. 

1. AVERAGING AN ARRAY

The array STOCK contains a list of 1000 whole numbers (integers). The following pseudocode presents an algorithm that will count how many of these numbers are non-zero, adds up all those numbers and then prints the average of all the non-zero numbers (divides by COUNT rather than dividing by 1000).

COUNT = 0

TOTAL = 0

loop N from 0 to 999

   if STOCK[N] > 0 then

      COUNT = COUNT + 1

      TOTAL = TOTAL + STOCK[N]

   end if

end loop

if NOT COUNT = 0 then

   AVERAGE = TOTAL / COUNT

   output "Average = " , AVERAGE

else

   output "There are no non-zero values"

end if

2. COPYING FROM A COLLECTION INTO AN ARRAY

The following pseudocode presents an algorithm that reads all the names from a collection, NAMES, and copies them into an array, LIST, but eliminates any duplicates. That means each name is checked against the names that are already in the array. The collection and the array are passed as parameters to the method.

COUNT = 0 // number of names currently in LIST

loop while NAMES.hasNext()

   DATA = NAMES.getNext()

   FOUND = false

      loop POS from 0 to COUNT-1

         if DATA = LIST[POS] then

            FOUND = true

         end if

      end loop

   if FOUND = false then

      LIST[COUNT] = DATA

      COUNT = COUNT + 1

   end if

end loop

3. FACTORS

The following pseudocode presents an algorithm that will print all the factors of an integer. It prints two factors at a time, stopping at the square root. It also counts and displays the total number of factors.

// recall that

// 30 div 7 = 4

// 30 mod 7 = 2

NUM = 140 // code will print all factors of this number

F = 1

FACTORS = 0

loop until F*F > NUM //code will loop until F*F is greater than NUM

   if NUM mod F = 0 then

      D = NUM div F

      output NUM , " = " , F , "*" , D

         if F = 1 then

            FACTORS = FACTORS + 0

         else if F = D then

            FACTORS = FACTORS + 1

         else

            FACTORS = FACTORS + 2

         end if

    end if

    F = F + 1

end loop

output NUM , " has " , FACTORS , " factors "

4. COPYING A COLLECTION INTO AN ARRAY IN REVERSE

The following pseudocode presents an algorithm that will read all the names from a collection, SURVEY, and then copy these names into an array, MYARRAY, in reverse order.

// MYSTACK is a stack, initially empty

COUNT = 0 // number of names

loop while SURVEY.hasNext()

   MYSTACK.push( SURVEY.getNext() )

   COUNT = COUNT + 1

end loop

// Fill the array, MYARRAY, with the names in the stack

loop POS from 0 to COUNT-1

   MYARRAY[POS] = MYSTACK.pop()

end loop

Available Resource

IB Style pseudocode and output, http://ibcomp.fis.edu/pseudocode/pcode.html