Students will be able to:
What are examples of tasks that get finished sooner if more people help with them? What are examples of tasks that don't get finished sooner if more people help with them?
Tasks such as tidying the classroom, picking up rubbish, or reshelving library books may come up as ones that benefit from multiple helpers. Things that don't go faster might include delivering a note to the office (10 people delivering the note won't get it there 10 times faster), or washing dishes if there is only one sink (two people are faster than one, but more people probably can't speed it up).
Use the Sorting Network template to draw a 6 person Sorting Network on a paved surface outside using chalk (other alternatives include using masking/painters tape on a carpet or wooden floor, tape on a tarpaulin, or line marking paint on grass). Note that the Sorting Network needn't use different colours or line thicknesses, but if suitable chalk or tape is available, this can help students remember which way to go. It should be large enough that two students can comfortably stand in the rectangles; the more spread out it is, the more effective the exercise is. In a very confined situation, it could be done on a desk top using game counters instead of students moving around, but this is much less engaging.
Show the students the Sorting Network drawn on the ground, and tell them "This chalk computer can do some things very fast, let’s investigate what it does."
Supports students understanding of ordering any range of numbers, from ordering single digit numbers to fractions and decimals, or numbers in their millions.
Here are examples of the kinds of numbers you could use to reinforce number ordering (two of each set of six cards are shown). It's good to start with the single digit numbers to get students used to the system, and then provide more difficult numbers appropriate to the students' ability level.
If it didn’t work it may be because a pair incorrectly went to the wrong square or a person raced ahead of everyone else. Have the group repeat the task and check each comparison. If it doesn’t work a second time, bring in student “testers” to confirm that each square has made the right decision which person is to go to the left and the right. Encouraging them to say "hello" when they meet at a square helps to avoid someone heading off before they have made a decision on the values.
If a student races to the end ahead of everyone else because they already know where their number will go once the numbers are sorted (this happens quite often!) then some students are going to be left stuck inside the network because they don’t have someone to compare numbers with. This is a good opportunity to remind students that computers need to follow the instructions they are given precisely to make sure they achieve the correct result; it also reinforces the need for teamwork!
This technique with parallel instructions can't run directly in the kind of computer system that students are likely to be learning about, as simpler systems can only compare one pair of values at a time, while this one is comparing up to three pairs of values at the same time. But although this algorithm hasn’t been written to work on a conventional system, there is still an algorithm to be observed, a parallel algorithm, and this can be implemented with specialised hardware and software. The challenge with creating parallel algorithms is to have as many things happening at the same time as possible, so that we can get things done faster. However, it's not always easy to break a problem up so that separate parts can happen at the same time, as often each comparison depends on the results of another. The diagram that we used above happens to be the shortest one we can design for sorting 6 values.
How do we know this Sorting Network is reliable and works every time?
The outcome we want to achieve is that the numbers come out in the correct order with the smallest number being in the left-most box and the second smallest number finishing next to it, right through to the largest number being in the right-most box. If we want to make sure it works for all possible inputs, then we would need to try it for every order that the values might start in - it turns out that there are 720 different orderings that 6 items can start in, so that's a lot of cases to test. For sorting more than 6 items, there are way too many different orderings to try out, so we must make a mathematical proof of why it works. Here are some elements of such a proof:
Let’s disregard the numbers for now and look at the Sorting Network from the point of view of following the paths. If the smallest number was in node 1, what path would it take and does it end up in the leftmost node at the end?
Now repeat this by asking if the smallest number was in node 2, what path would it take and does it still end up in the leftmost node at the end?
Repeat this until you’ve tested all 6 nodes. If the smallest number ends up in the leftmost node regardless of where it starts, that's part-way to being sure that the structure always works.
You can repeat this with the largest number - no matter where it starts, it will always end up in the right-most node.
Doing this for the other four values (e.g. the second to largest) isn't quite as simple, but computer scientists are able to prove that they will also always end up in their correct position.
Throughout the lessons there are links to computational thinking. Below we've noted some general links that apply to this content.
Teaching computational thinking through CSUnplugged activities supports students to learn how to describe a problem, identify what are the important details they need to solve this problem, break it down into small logical steps so that they can then create a process which solves the problem, and then evaluate this process. These skills are transferable to any other curriculum area, but are particularly relevant to developing digital systems and solving problems using the capabilities of computers.
These Computational Thinking concepts are all connected to each other and support each other, but it’s important to note that not all aspects of Computational Thinking happen in every unit or lesson. We’ve highlighted the important connections for you to observe your students in action. For more background information on what our definition of Computational Thinking is see our notes about computational thinking.
We used an algorithm in this lesson to sort the numbers into order using a parallel processor (normally this processor would be implemented in hardware, but our chalk network is still actually one! It’s powered by people instead of electricity).
Do students understand how each node functions (taking in two values and swapping them if they are in the wrong order)? Are they able to explain to other students how to use the network correctly?
Do the students see that no matter what numbers or data we put into the network we will always get a solution if we follow the algorithm correctly?
The Sorting Network used in these activities is itself an abstract representation of how Sorting Networks are implemented in hardware and software. It represents the core functionality of a Sorting Network, whilst hiding all the nitty gritty details of how the hardware and circuitry works.
The whole process of sorting in this activity is decomposed into a very simple operation: comparing two values. This operation alone is very simplistic, but when it is performed many many times it can be used to build up a solution to a much larger task.
In this lesson students only worked with one type of information, numbers, so there wasn’t much use of generalisation. It is more prominent in the next lesson.
For this Sorting Network there can be up to three comparisons happening at once, and the length of the network determines how long it would take to complete all these comparisons. Although 12 comparisons need to be made when going through the network, the network can be completed in the time it takes to an individual node to make 5 comparisons.
The smallest value will always take the left path at any comparison, and from every starting point the path that always takes the left branch will lead to that node, the smallest value will therefore always end up in the left-most position at the end.
