1.3 Algorithms and Programs

• Algorithms


  An unambiguous list of instructions to solve a problem
• Pseudocode


  A generic programming language that is not meant to be run directly or compiled, but used to represent algorithmic ideas
• Flowcharts


  Less commonly used for representing algorithms but can be used to represent the exact same as pseudocode. They are more common for smaller algorithms.
• Variable


  A named location in the computer's memory that a programmer can use to store data whilst the program is running
• Constant


  A special kind of variable that cannot be changed during the execution of the program – this prevents it from accidentally being changed
• It is good programming practice to use constants in computer programs because if you want to change the value of the constant you only have to change it once at the top and its value will be updated throughout the whole program
• Scope of variables


  When a variable declaration is made, the computer reserves space in memory for storing its value
• Scope of variables


  The scope of a variable is the section of program when a variable's value may be accessed
• When the subroutine / function is completed the memory space reserved for local variables is released for other use
• It is important that variables should be declared locally if possible. This saves memory space when programs are run
• Identifier


  The name given to a variable, constant, function, parameter or routine by the programmer. By using meaningful names they can become self-documenting identifiers.
• Identifiers are used to make programs easier to read (by potentially different programmers or the same programmer at a later date)
• Annotation


  Comments included in computer code that are ignored during execution. These help make code self documenting and serve as important reminders to programmers when they look back at code in the future.
• When writing code it is important to use appropriate indentation. This makes it much easier to see where different sections of code start and end.
• Parameter


  A variable / value that can be passed to / from the procedure
• Passing by value


  A local copy of the data is created for the procedure (which is discarded later)
• Benefits of passing by value


  • Preserves value-at-calling of the parameter

  Avoids unwanted side-effects

  Avoids problem (associated with passing by ref) of unintended side effects where the Parameter has its value changed in the main program as well as in the procedure
• Passing by reference


  The address of the required data is passed to the procedure (rather than the actual value of the data)
• Benefits of passing by reference


  • Avoids the larger amount of processing/storage (associated with passing by value) - possibly large amounts of copying

  Allows (desirable) change to be passed back to the calling program
• Passing by reference may lead to unintended side effects where the parameter has its value changed in the main program as well as in the procedure
• Recursion


  A recursive algorithm is one which calls itself. It must also have a 'base case' to allow it to terminate (terminating condition)
• RecursionExamples


  • Quicksort

  Binary search

  Traversing binary tree

  Factorial calculation
• DIV


  An algorithm function which reports the answer of a divide operation without any remainder
• MOD


  An algorithm function which reports the remainder from a divide operation
• Validation Checks


  • Character Check (Type Check)

  Length Check

  Format Check

  Presence Check (Existence)

  Check Digit
• Character Check (Type Check)


  Ensures that the input is of the correct data type (e.g. all input is numeric)
• Length Check


  Checks the amount of characters to ensure it does not go over a specific length
• Format Check


  Ensures data conforms to a set of rules (e.g. NI Number: LL NN NN NN L)
• Presence Check (Existence)


  Ensures that data exists / is not left blank
• Check Digit


  Only available for specific inputs – uses a mathematical formula to generate an extra (check) digit. This is generated and checked at every input.
• Verification Checks


  • Double Entry

  Proof reading
• Double Entry


  Enter the data twice and then compare to ensure accuracy
• Proof reading


  A human will read over the input to manually check
• Bubble Sort


  • Quick for 'nearly sorted' files, e.g. files which have been recently sorted but may have had a few more records added at the end
• Linear Search


  This kind of search is when the first item in a list is looked at. If this is not the required piece of data, the next one is looked at... and so on...
• Linear search is not a very efficient way of searching, but if the data is not sorted into order, it is the only way
• Binary Search (Chop)


  This involves looking at the 'middle' record. If the required record is before this one, then discard the second half of the file; if it is after this one, then discard the first half of the file. Repeat the process, discarding half the file each time, until the required record is found.
• Iteration


  Iteration functions are used to make sections of code repeat a number of times. There are many different types of iteration functions.
• Selection


  Selection statements allow parts of code to be executed only if certain conditions are met. E.g. the 'IF' statement
• Counts


  A variable (integer) is used to count values which satisfy a certain condition. Remember counting always starts from 0 so the value of the variable must be initialised to 0.