Algorithms

Algorithms

1. Computational thinking

   • Abstraction
     • Using symbols and variables to represent a real world problem in a computer program removing unnecessary details
       • E.g. Not having curved lines in tube maps so they are easier to read
       • Sat nav - dont need houses/ hills/ etc
   • Algorithmic thinking
     • Solving a problem using defined instructions
       • Example: psuedocode
   • Decomposition
     • Breaking down larger, complex problems into smaller sub-problems
       • Example: a bike Explain how each part works instead of all at once. E.g. Say how brakes work and then wheels

2. Search algorithms

   • Linear search
     • Goes through every item until item being searched for is found
   • Binary search
     • Goes to middle item
       • Looks at numbers on left and right and compares to item searched for
         • Gets rid of all numbers on side not needed
           • Repeats until item is found
   • Sort algorithms
     • Bubble sort
       • Compare first 2 items and swap if needed
         • Once compared repeat with next 2 items
           • When whole row is done repeat until all items sorted
       • Slow
       • Easiest to code
     • Insert sort
       • Take item
         • Item is sorted Put all other items as unsorted
           • Compare first item in list and sort Once sorted place in order in sorted side
             • Take next item and compare with all items on sorted side then put in order
               • Repeat until all numbers sorted
       • Easy to code
         • Faster than bubble sort
       • Slower than merge sort
     • Merge sort
       • Split all items into separate columns
         • Compare and combine every pair of items
           • Once combined the pair become one item
             • Compare next items in pairs
               • Repeat until all are one item in order
       • Hard to code
         • Can use others if less than 1000 items
       • Quickest