Writing and Following Algorithms

• Algorithm

  A set of instructions to solve a problem or complete some well-defined task in a finite number of steps
• Problems solved by algorithms

  Routing problems:

  • routing packets of data around the internet by the shortest route
  • finding the shortest route for a salesman to cover his territory

  Timetabling commercial aircraft crews so that they do not exceed their permitted flight hours

  Searching information on the internet or from a database

  Encrypting communications so that they cannot be hacked

  Sorting large amounts of data

  Writing a compiler program to translate a high level language to machine code
• Properties of a good algorithm

  • has clear and precisely stated steps that produce the correct output for any set of valid inputs
  • should allow for invalid inputs
  • must always terminate at some point
  • should perform the task efficiently, in as few steps as possible
  • should be designed in such a way that other people will be able to understand it and modify it if necessary
• Pseudocode

  Pseudocode is a halfway house between English statements and program code. To a large extent, it is independent of any particular programming language.
• Bubble Sort


  The simplest sorting algorithm. It starts with the first item in the list, each item is compared with the adjacent item and swapped if it is larger. At the end of the first pass the largest item 'bubbles' up to the end of the list.
• Linear Search


  Starts at the beginning of the list and examines every item
• Binary Search


  uses the 'divide and conquer' strategy to halve the search area each time an item is examined. It can only be used if the items are in sorted order.
• Writing good programs:

  • use comments to document your programs
  • use a standard for identifiers
  • use properly indented code
  • make sure your program does not contain statements that are not needed
  • use a modular structure, with no module longer than a page of code, performing a discrete task