Component 02 - Algorithms

Component 02 - Algorithms

1. Computational Thinking

   • Decomposition
     • Breaking a complex problem down into smaller probelms and solving eacjh one individually
   • Abstraction
     • Picking the improtant bits of information from the problem, ignoring the specific details that dont matter
   • Algorithmic Thinking
     • A logical way of getting from the problem to the solution. If the steps you take to solve a problem follow an algorithm then they can be reused and adapted to solve similar problems in the future

2. Flow Diagrams

   • Start/stop
   • Inputs/Outputs
   • Processes
   • Decision
   • Sub-Routine
   • Algorithms
     • Sequence
       • Only one way from the start to the end
     • Selections
       • There are multiple ways to get from the start to stop
     • Iteration
       • Contains a loop that allows you to repeat a task

3. Pseudocode

   • Pseudocode is not an actaul programming language but it should follow a similar structure and read like one (roughly). The idea is that pseudocode clearly shows an algorithm's steps without worrying about the finer details (syntax) of any particular programming language
   • It is quick to write and can be easily converted into any programming language
   • There are diffent ways to write pseudocode - they are all equally correct as long as the person reading the code can follow it and understand what you mean

4. Search Algorithms

   • Binary Search Algorithm
     • 1. Find the middle item in the ordered list.
       • 2. If this is the item you're looking for, then stop the search - you've found it.
         • 3. If not, compare the item you're looking for to the middle item. If it comes before the middle item, get rid of the second half of the list. If it comes after the middle item, get rid of the first half of the list.
           • 4. You'll be left with a list half the size of the original list. Repeat steps 1 - 3 on this smaller list to get an even smaller one. Keep going until you find the item you're looking for.
   • Linear Search Algorithm
     • 1. Look at the first item in the unordered list.
       • 2. If this is the item you're looking for the stop the search - you've found it.
         • 3. If not, then look at the next item in the list.
           • 4. Repeat steps 2 - 3 until you find the item that you're looking for or you've checked every item

5. Sorting Algorithms

   • Bubble Sort Algorithm
     • 1. Look at the first two items in the list
       • 2. If they're in the right order, you don't have to do anything. If they're in the wrong order, swap them.
         • 3. Move on to the next pair of items (the 2nd and 3rd entries) and repeat step 2
           • 4. Repeat step 3 until you get to the end of the list - this is called one pass. The last item will now be in the correct place, so don't include it in the next pass
             • 5. Repeat steps 1 - 4 until there are no swaps in a pass
   • Insertion Sort Algorithm
     • 1. Look at the second item in a list
       • 2. Compare it to all items before it (in this case just the first item) and insert the number into the right place
         • 3. Repeat step 2 for third, fourth, fifth, etc. items until the last number in the list has bee inserted into the correct place
   • Merge Sort Algorithm
     • 1. Split the list in half the (smaller lists are called sub-lists) - the second sub-list should start at the middle item
       • 2. Keep repeating step 1 on each sub-list until all the lists only contain one item
         • 3. Merge pairs of sub-lists so that each sub-list has twice as many items. Each time you merge sub-lists, sort the items into the right order.
           • 4. Repeat step 3 until you've merged all the sub-lists together

Images and files in the map