2.1 Algorithms

What you should know

Self Marking Quiz

• computational thinking:

• • • abstraction

      • • picking out the important bits

        • removing unnecessary detail

    • decomposition

• • • • breaking a complex problem down into smaller problems

• • • algorithmic thinking

• • • • applying a step-by-step process to solve a problem

• standard searching algorithms:

• • • binary search

      • list must be in order

      • split list into 2 halves

      • check top of lower half (or bottom of top half) 

      • discard the half the search value can't be in

      • repeat until found or you have exhausted the list

    • linear search

      • only option if list is unsorted

      • start with the first item in list

      • check every item until found or you have exhausted the list

• standard sorting algorithms:

• • • bubble sort

      • start at the bottom, compare 1st pair, swap if necessary

      • compare 2nd pair, swap if necessary

      • continue to the end of the list

      • repeat until there are no swaps 

    • merge sort

      • split all items into individual items

      • merge into pairs (sort as you merge)

      • merge pairs (sort as you merge)

      • repeat merging until finished

    • insertion sort

      • move first item into a new sorted list

      • take each item in turn from unsorted list insert it in order in the sorted list

      • continue until finished

•   how to produce algorithms using:

• Pseudocode

• Flow charts

•  interpret, correct or complete algorithms.

•  Trace Tables