Algorithms
An algorithm is...
...a set of instructions that, when followed precisely, will solve a given problem.
Algorithmic Thinking - where experts solve problems and write the solution down as a series of instructions for the benefit of all.
Want a perfect Victoria Sandwich? Thank Delia for that!
We live in algorithmic times. We don't have to re-invent the wheel!
Describing a solution
We live in algorithmic times. Solutions to past problems have been described as algorithms for us to use today. It is important when describing a solution to ensure that it is clear and unambiguous for OTHERS to understand.
Algorithms are written down in one of three ways:
Structured English
Pseudocode - great for detail
Flowcharts - quickly read and understood but not good for details
#learning #DESIGN Describing an algorithm using Structured English
All students will be able to attempt to write a solution to a problem
Most students will write the solution in a way that another person can follow
Some students will write an efficient solution to the problem that someone else can follow
#learning #DESIGN Describing a secure password algorithm using Structured English
All students will be able to attempt to write an algorithm in Structure English
Most students will write an algorithm that someone else can understand to produce a strong password
Some students will write an easy to follow algorithm that creates a very strong password
An algorithm that EVERYONE MUST KNOW is how to create a strong password for every website we visit (written in Structured English):
Take the last character of URL of website you want to sign up to (eg. Facebook) and make CAPS = K
Think of x2 words that mean something to you (eg. walking and apples) = Kwalking.apples
Append the first character of the URL of the website you want to sign up to = Kwalking.applesf
Append some special characters "!?" at the end = Kwalking.applesf!?
Common algorithms that are important for Computer Scientists:
Searching
Linear search
Binary search
Sorting
Bubble sort
Merge sort
Insertion sort (GeekForGeek, Khan Academy)
Linear search (linear)
This algorithm does not assume a sorted list.
Searches each list item in turn until the required item is found.
Worst case performance: O(n)
Best case performance: O(1)
Average performance: O(n)
This algorithm assumes a sorted list.
Divides the search space into x2 equal sets then compares the required item with each set. It discards the set that cannot contain the required item and repeats the process with the resultant set.
Worst complexity: O(log n)
Best complexity: O(1)
Average complexity: O(log n)
Starts at one end of the list, compares the current item with its neighbour. If it is larger then they swap. The current item moves onto the next list item and the process repeats until the last item. Then the process is repeated from the end of the list again.
Deterministic version: This algorithm will blindly repeat n^2 times.
Non-deterministic version: This algorithm will stop iterating when there have been no swaps.
Worst complexity: O(n^2)
Best complexity: O(n)
Average complexity: O(n^2)
Split the list into x2 lists: sorted and unsorted. The sorted list contains just one number, the unsorted list contains all others. Take each number in the unsorted list in turn, then track back through each number in the sorted list until the number can be inserted in its sorted position. Repeat this process until the unsorted list is empty.
Worst complexity: O(n^2)
Best complexity: O(n)
Average complexity: O(n^2)
Continually divide the list until you get to individual items. Then 'merge' neighbouring items back together, sorting them as you merge. Once items are merged, repeat the process between neighbouring pairs. Then neighbouring sets and so forth until the list is reconstructed sorted.
Worst complexity: O(n*log(n))
Best complexity: O(n*log(n))
Average complexity: O(n*log(n))
EXTENTION: SimpleHASH
Why so many algorithms that do the same thing?
You may wonder why there are x3 different ways to sort numbers. There are in fact lots more than x3 but why?
We live in Algorithmic times. People sit down and solve problems, eg. how to sort some numbers. Then they write the solution down as an algorithm. Then release it to the world - to live forever. Then another person sits down to solve the same problem, eg. sorting numbers, and writes their algorithm and releases it to the world. We now have x2 algorithms that sort numbers. They do the same job but in a different way.
Evaluating an algorithm
There is more than one way to sort a list of numbers of search a list of numbers, so which do you use? Pick at random? Eeny meeny miney moe?
Different algorithms do the job (sort or search for things) in different times, under different conditions. An algorithm is evaluated in terms of:
its speed (called time complexity) and
how much memory it takes (space complexity)
in doing its job. The test results are written down as "Big O notation".
You choose the algorithm based on the conditions it will operate under and how much time and space you have to use.
NCCE
Learning Outcomes
Recognise that computing is about a way of thinking that involves several core concepts - Computational Thinking & The Big 3 (sequence, selection and iteration)
Appreciate that algorithms cannot be separated from the data structures they manipulate.
Have identified the key elements used to construct both algorithms and data structures.
Be able to express the movement of data within a list, with reference to index positions.
Have some ideas for activities to introducing these core concepts to your classes.
Learning Outcomes
Be able to articulate the process of iterating over a list/array
Appreciate that simple algorithms can be expressed as flow charts
Become familiar with the Flowgorithm tools
Be able to analyse a classic computational problems
Have some ideas for activities to introducing these core concepts to your classes.
Learning Outcomes
Be able to develop a subroutine as a named procedure accepting two parameters
Have extended your repertoire of standard data processing operations
Become more confident manipulating index pointers
Appreciate the value of kinaesthetic activities for working through more complex operations
Be familiar with some activities to make curriculum links and introducing these idea to your classes
Learning Outcomes
Identify barriers to understanding sorting
Recognise the steps involved in the Insertion Sort
Be able to refine the Bubble Sort
Appreciate that some algorithms work better than others
Be aware of activities that can be used in class
Learning Outcomes
Be aware of the capabilities for visualising code execution
Be familiar with the key steps involved in a binary search
Appreciate how effective the method is for large data sets
Become more confident writing and tracing pseudocode
Recognise divide and conquer as one problem solving strategy
Get some ideas for activities to introduce divide and conquer concepts to you classes
Learning Outcomes
Recognise some cognitive hurdles to understanding code
Have practical experience coding basic algorithms
Become familiar with the Merge Sort
Recognise that similar strategies can be used to solve different problems
Gather ideas to develop code comprehension with your classes