Section 4 - Algorithms

Section 4 - Algorithms

1. Computational Thinking

   • Decomposition - breaking down a complex problem into smaller problems and solving each individually
   • 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
   • Abstraction - picking out the important bits of information from the problem, ignoring the specific details that don't matter

2. 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 as it's found
         • 3. If not, compare the item you're looking for to the middle item. If it comes before then get rid of the second half of the list (and visa versa)
           • 4. You'll be left with a list half the size of the original. Repeat 1-3 till you reach the number
   • Linear Search Algorithm
     • 1. Look at the first item in the unordered list
       • 2. If this is what you're looking for, stop
         • 3. If not, then look at the next item in the list
           • Repeat steps 2-3 until you find the item or if you've checked every item

3. Sorting Algorithms

   • Bubble Sort
     • 1. Look at the first two items in the list
       • 2. If they're in the right order, don't do anything, if they're in the wrong order, swap them
         • 3. Move onto the next per of items and repeat step 2
           • 4. Repeat step 3 until you reach 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
             • Repeat steps 1-4 until there are no swaps in a pass
   • Merge Sort
     • 1. Split the list in half. The smaller lists are then 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, sort the sub-lists into the right order
           • Repeat step 3 until you've merged all the sub-lists together
   • Insertion Sort
     • 1. Look at the second item in a list
       • 2. Compare it to all the items before it and insert the number into the right place
         • 3. Repeat step 2 for the third, fourth, fifth, etc. items until the last number has been inserted correctly