2.1 Algorithms

2.1 Algorithms

1. Computational Thinking

   • Abstraction
     • Abstraction is the process of making an “easier-to-understand” version of a complex system, by removing unnecessary information and focussing only on key information.
     • Different situations require different abstractions.
       • To describe a car to a friend: the make, model and colour
       • To describe a car to a mechanic: the mileage, fuel type, and problems
       • When designing as game you might use a square for a house, and a triangle for a tree.
   • Decomposition
     • Decomposition is extremely useful when programming solutions to large projects.
     • Decomposition is the process of breaking big problems down into a set of small problems that can be solved one small problem at a time.
     • Some smaller problems may need to be further subdivided until they are simple enough to be expressed as an algorithm.
   • Pattern recognition
     • This is being able to identify patterns in data and to build efficient algorithms to take advantage of these.
   • Computational thinking is the ability to solve problems in a structured logical way.

2. Standard Algorithms

   • Sorting
     • Bubble Sort
       • The Bubble Sort is a very inefficient sorting algorithm, as it has to check every pair of items in the list up to the sorted section, even if they do not need to be swapped.
       • Working from left to right, it repeatedly checks the order of pairs of items, and swaps them if they are in the wrong order.
       • It is the simplest sorting algorithm.
     • Merge Sort
       • It works by taking a list and splitting it in two until there are many lists which are each one element in size. It then sorts pairs of lists until the original list is re-formed in a sorted order.
       • It's very efficient & uses “divide and conquer”
     • Insertion Sort
       • The algorithm starts with the beginning item, and works its way to the end of the list. When it finds an item that is lower than the current highest item, it shifts all items down until there is a space where the number can be inserted.
       • The Insertion Sort is a simple sorting algorithm that sorts a list one item at a time.
   • Searching
     • Binary Search
       • Advantages:
         • Much Quicker
         • Fairly simple and easy algorithm
       • Disadvantages:
         • More complicated than linear - could be overkill.
         • Must be in alphabetical/ numerical order
       • It repeatedly divides in half the portion of the list that could contain the item, until you've narrowed down the possible locations to just one.
     • Linear Search
       • Advantages:
         • Doesn't have to be in alphabetical/ numerical order
         • Simple + easy to understand and implement;
       • Disadvantages:
         • Takes a lot longer
         • If the wanted value is not in the array, it will unsuccessfully search to the end of the array.
       • The linear search is a sequential search, which starts with the first element, and compares each element with the value being searched for, and stops when either the value is found or the end of the array is encountered.

3. Producing Algorithms

   • Pseudocode
     • Pseudocode is ...
   • Flow Charts

4. Interpretting, Correcting and Completing Algorithms

   • Interpretting
   • Correcting
   • Completing