Programming and Algorithms

Programming and Algorithms

1. Searching

   • A search goes through a dataset, often an array, and looks to find a particular item.
     • Linear search
       • Starts at the beginning of the dataset, and examines each one in turn. If it is the required item the search stops; it also ends if nothing is found.
         • Quicker if the item is at the start of the data set
         • Can be used if the data is not sorted
     • Binary search
       • Starts in the middle of the dataset. If value > search_value then discard all to the left. Repeat the process in the new middle. Continue doing this until search_value is found or until the end has been reached.
         • Very fast on large data sets - 1 million items would take just 20 passes
         • Dataset must be sorted
         • Inefficient if the item is near the start of the dataset

2. Sorting

   • Sorting moves data into a specified order according to a key, such as alphabetically or numerically descending
   • Bubble sort
     • Start at the beginning of the dataset. Compare [0] to [1]. If [0] is bigger, swap them around. Compare the new [1] to [2]. If they are bigger swap them around. Continue doing this until the end of the dataset is reached. Go back to the start of the dataset and repeat the process until all the numbers are sorted.

3. Rogue value

   • A deliberately incorrect value used to indicate that the program should end.

4. Variable

   • A piece of data held in memory. Can change during execution.

5. Selection

   • Control flow - the program may have to select which choice to make during an if statement or switch

6. Testing

   • Alpha testing
     • Carried out by the developer; individual algorithms are tested and variables traced
   • User acceptance testing
     • Software is given to the end-user so that they can provide feedback on any changes they want made
   • Beta testing
     • Software is distributed to a wider audience to gain feedback and check for further bugs

7. Constant

   • A variable that doesn't often change, such as VAT

8. Variable scope

   • Global
     • Defined at start of program; accessible anywhere throughout
   • Local
     • Defined inside a function or method; only accessible within that scope

9. Problem analysis

   • Programs are complicated. They should be split up like follows:
     • Program
       • Function 1
         • Subfunction1
       • Function 2