Writing and following algorithms

• Algorithm


  A set of clear and precisely stated steps that produce the correct output for a given input
• Properties of a good algorithm

  • Has clear and precisely stated steps that produce the correct output for a given input
  • Allows for invalid inputs
  • Always terminates at some point
  • Executes efficiently, in as few steps as possible
  • Designed in such a way that other people will be able to understand it and modify it if necessary
• Types of problems solved by algorithms

  • Internet-related algorithms (managing and manipulating data on the Internet)
  • Route-finding algorithms (determining shortest or best route between two locations)
  • Compression algorithms (compressing data files)
  • Encryption algorithms (encrypting data for secure transmission)
• Simple computational algorithm to find square root of an integer

  1. Initialise n

  2. Square n

  3. Is n^2 the number?

  4. If yes, output square root. If not, add 1 to n and repeat from step 2
• When programming, it's tempting to get straight to the computer and type in some code to solve a given problem. However, it will generally save time to figure out the steps needed using paper and pencil to write down a pseudocode algorithm before you start coding.
• Pseudocode


  A way of expressing the solution in a way that can easily be translated into a programming language
• Pseudocode algorithm to find square root of an integer

  1. Set low to 1, high to number

  2. Guess = (low + high)/2

  3. If guess^2 > number, set high = guess to eliminate top half of range

  4. If guess^2 < number, set low = guess to eliminate bottom half of range

  5. Repeat until guess^2 = number
• The algorithm described will do the job, but a better solution is based on the well-known binary search algorithm
• Binary search algorithm


  • Uses the "Divide and Conquer" strategy to halve the search area every time a guess is made
• We can draw a hierarchy chart to represent the steps of the binary search algorithm
• you


  low high, mie
• BLOCK


  • Compers guess
  • with target
• BLOCK


  • Calculate guess
  • Compare gues
• BLOCK


  Oviput
• BLOCK


  Pesetrange
• The chart represents the blocks of program code that we will use to solve the probem.
• The solutions are short, so it's not necessary to put each block in a separate subroutine
• number 19321
• high number
• nequared guess**2
• queas intillow hight/2)
• BLOCK 1 SEQUENCE


  1. while nequared

  2. number

  3. If nsquared > number

  4. high guess

  5. else

  6. endif

  7. low-guess

  8. guess -int ((low+high)/2)

  9. naquared

  10. quess**2
• BLOCK 2 ITERATION


  endwhile
• BLOCK 3-SEQUENCE


  print ("square root is ",guess)
• Add statements to calculate and print the number of guesses it took to find the answer
• Try writing and running the program for different values of number.
• Is there a formula for calculating how many guesses it should take to find the square root?
• A useful skill is to be able to look at someone else's algorithm and decide what it does and how it works
• Of course, if the programmer has put in lots of useful comments, used meaningful variable names and spit a complicated algorithm into separate modules, that should not be too difficult
• Tips for interpreting algorithms

  • Read the comments in the program
  • Look at the variable names to see if they give any clues
  • Follow the shaps in the program
  • Try a "dry run" with some test data
• Trace table


  A useful tool for performing a dry run through a program. As you follow through the log of the program in the same sequence as the computer does, you note down in the trace table when variable changes and what its value is.
• Dry run the algorithm

  1. Assume that x has a value of 7

  2. The NOD operator calculates the remainder resulting from an integer division

  3. answer True

  4. for count 2 to 1x-1)

  5. remainder x MOD count

  6. if remainder 0 then

  7. answer False

  8. endif

  9. next count

  10. answer
• The purpose of this algorithm is to