Algorithms

Algorithms

1. An algorithm is a sequence of steps that can be followed to complete a task.

2. Computational Thinking

   • Abstraction
     • Removing unnecessary details from a problem in order to solve it.
     • Climate change models, financial models, population models, queuing models...
     • Separates the "logical" from the "physical".
   • Decomposition
     • Breaking down a problem into smaller, simpler stages. This makes it much easier to solve.
     • Each part is itself a small, manageable subproblem.
   • Algorithmic Thinking
     • A working algorithm will always finish and return an answer or perform the task it was supposed to.
     • Pseudocode/Flow Diagrams
       • Outlines the programming constructs but doesn't rely on any specific language syntax.

3. Searching Algorithms

   • Linear Search
     • Starts at the beginning of a list, and looks at every single item until found.
     • You could be lucky and find the item quickly if near the beginning, and vice versa.
   • Binary Search
     • List must be sorted
     • Much more efficient.
     • Repeatedly divided in half the portion of the list that could contain the item.

4. Sorting Algorithms

   • Binary search needs to be sorted first.
   • Bubble Sort
     • Repeatedly going through the list, comparing each pair of adjacent elements.
       • If elements are in the wrong order, they are swapped.
     • Slowest
   • Insertion Sort
     • One piece of data at a time. One data is taken and placed in the correct location.
       • On each pass, the current data item is checked against those already in the sorted list. If the item is smaller, the sorted list is shifted to the right.
     • More efficient than bubble, less than merge.
   • Merge Sort
     • The list is successively divided in half, until the remaining lists are 1 element long.
       • Each pair of sublists is compared and merged, forming a new sublist. This sublist once again compares and merges...etc.
     • Fastest

5. Pseudocode

   • Iteration
     • Looping or repeating. For, While, (sometimes also Repeat) loops.
   • Selection
     • If...else statements. Selecting which path of an algorithm to execute depending on some criteria.
   • Sequence
     • Writing the steps down in the order they need to happen.

Images and files in the map