2.1 Algorithms

2.1 Algorithms

1. Computational Thinking

   • Algorithmic Thinking
     • Identifying the steps involved in solving a problem
   • Consists of four parts:
     • Abstraction
       • Getting rid of irrelevant details and focusing on the important information
     • Pattern Recognition
       • Recognising similarities between problems which could save you time and debugging
     • Decomposition
       • Breaking up a problem into smaller, more manageable problems
     • Algorithms
       • Developing a step-by-step solution to the problem

2. Methods of Searching

   • Binary Search
     • Longer and more complex to write
     • List needs to be in order
     • At most, half of the values are checked
     • Takes the middle value and compares it to the desired value
       • IF the value is correct then the algorithm stops
       • ELSE IF the value is larger than necessary then the algorithm takes the values on the left and repeats the process
       • ELSE (the value needs to be smaller) then the algorithm takes the values on the right and repeats the process
   • Linear Search
     • List doesn't need to be in order
       • At most, all of the values are checked
     • Simpler to write
     • It goes through each value one by one
       • IF the value is correct then the algorithm stops
       • ELSE the algorithm moves to the next value

3. Types of Sorts

   • Merge
     • List is split in two and combined two at a time
   • Bubble
     • Moves through a list repeatedly, swapping elements until they're in the right order
     • Can take a long time to do
     • Takes the first 2 elements, compares them then moves onto the second and third. Repeats this until the list is checked through with no changes
   • Insertion
     • You have one ordered list and a selection of other elements
     • These elements are taken one at a time, compared to the ordered list and then placed in the correct position. This process is repeated until all the values are in the correct position

4. Psuedocode

   • Simplified programming code that is used to design algorithms

5. Completing and Correcting Algorithms

   • Dry Run
     • Walking through an algorithm which samples data, running through each step manually
   • Trace Table
     • A table that follows the values of variables to check for accuracy
   • Correcting
     • Ensure you know what the algorithm should do then separate it into smaller chunks and draft the steps that should occur
     • Read through the algorithm, compare to your notes and correct the algorithm where they differ
   • Completing
     • Follow the same steps as correcting but complete at the end rather than correct
     • May be asked to fill in elements or just continue the algorithm