My six year old son has got the bug for trading cards. I began taking an unnaturally close interest in this craze as soon as I realised the cards were a launching point for all sorts of computational thinking. Ian loves Star Wars cards, but it doesn't matter in the least what the topic of the cards is. If you ever wanted to try out these activities with a class, you could get the kids to make their own card sets which appeal to them. That would avoid problems with inclusion, either to do with the money for buying card packets or the marketing of most trading cards towards stereo-typically boys' interests. I refuse to believe that collecting or sorting cards is inherently either "for" boys or girls.
So what do trading cards have to do with computational thinking? They are a collection of objects, each of which has a type (such as rebel, empire, mercenary), and numerical attributes (such as star rating, attack or defense). Each card also has a unique identification number. Computer scientists love collections. Their collections are usually digital objects (data) but the same computational principles apply. Your set of trading cards is information, or data, and what you do with the cards are the processes.
What do kids like to do with trading cards?
- Collect a complete set. This involves knowing how many items there are in a complete set, and what those items are and knowing how many items you have in your own collection and what those items are. This enables you to work out how many cards you are missing, and which you need to acquire.
- Trade with friends. Some kids trade to acquire the cards they are missing for their collections. Others seems to just love trading for the sake of it.
I'll focus on number 1 for today, but there is a lot of interesting learning about game theory to be done with 2.
Collecting a complete set: data structures and sorting
How do you know what's in the complete set?
The company which makes the star wars cards supplies a poster which shows a photo of each card. The photos are grouped by type and the unique identification number is printed underneath. The numbers start at the top left, and the highest card number is at the bottom right. There is a checkbox under each so you can tick when you collect it. My son and I spent a happy half hour executing this algorithm:
For each card in your own set{
Look at the picture on your card
Find the picture on the poster which matches your card picture
Tick the box on the poster once you have found a match}
But wait! There is more than one Yoda card (you get two sorts of subtly different shiny ones and a plain one). How do we decide whether we have the right one? We changed our algorithm:
For each card in your own set{
Look at the unique identification number on your card
Find the card on the poster with the same identification number
Tick the box on the poster once you have found a match}
And that, my friends, exactly captures why unique identifiers are necessary as any database designer will tell you.
Then you can count how many ticks you have, and subtract from the total number in the complete collection. You can spot doubles easily too, which means you can identify what to trade. Note that every time you make a trade you'd need to keep the poster up to date. That's because it's a copy of the data in your actual card set, so when the cards get updated, you need to update the copy too.
How do you know what's in your own set?
If you have a set of cards, you need to store them somehow. You could keep them in a stack with an elastic band round it. My son loves stationary, so he was very keen to get a folder to keep his cards in. So was I when I realised that folder consisted of transparent pages with 9 slots on each page -it suggested to me an array data structure. At first Ian loved putting the cards into the folder and then taking them out again just for the sheer physical fun of it. But as his card collection grew, it became harder to know where to find his cards when he wanted them and he grew more ambitious.
I asked him (and Daddy who is a software developer) what is the best way to get the cards from the pile into the right place in the book? Ian wasn’t sure at first but then he suggested searching the card pile for the lowest card (which would be 1) and inserting it into first free slot in the folder. Then look for the highest number in the pile (243) and put it in the last free slot in the folder and then keep doing that. As I understand it, this is Ian's algorithm:
set lowest to 1
set highest to 243
While there are still cards left in your pile{
for each card in your own set{
if (card id equals lowest){
insert card into folder in slot labelled with lowest
}
}
lowest = lowest +1
for each card in your own set{
if (card id equals highest){
insert card into folder in slot labelled with highest
}
}
lowest = lowest +1
highest = highest -1
}
Now, this isn't the most efficient way of doing it but it would work (and is pretty good for a six year, she notes bursting with motherly pride).
Then I suggested other ways of doing it. 1) Label all the slots in the book and then iterate over the pile, inserting each card into the slot with the corresponding identication number. 2) Sorting all the cards in the pile, then inserting each card from the sorted pile into the next free slot in the folder, starting from a blank folder.
Now we really get to the heart of computer science. We have a couple of possible ways of solving the problem correctly but we need to decide which to use. Which is optimal for our purpose? That really depends how you define optimal - what your priorities are. When sorting a collection of objects in computer science, you usually worry about efficiency: what is the quickest way to solve this given the size of the collection? If this is our priority, then 1) is better. * YOU MAY NOT CARE ABOUT THIS BIT ***As Daddy pointed out, 2) is less efficient because the sort is nlogn or worse, and for 1) labelling all the book slots is linear plus constant time insertions. What this means is that theoretical computer scientists do mathematical proofs about the efficiency of sorting algorithms based on the size of collection (referred to as "n"). The fastest known way of sorting will take the time it takes to process every item in the collection (n) multiplied by the logarithm of n. Because method 2) relies on sorting, we know it can't be faster than nlogn. For method 1, we need to write a number on every slot to store the collections - this takes n time. In both cases, inserting an item into an array is considered to be constant time - the time for it doesn't vary according to the size of the collection. START READING AGAIN* For computer science education, we might choose to define optimal as something different.To teach computational thinking we could think about optimising algorithms for cognitive load.We should think about the working memory load on the kid who is doing the sorting, and how hard they find every individual operation (such as comparing numbers or writing labels). In this case, 1 is also easier because it is easier on the memory and builds on writing numbers in sequence, which is common at school.
Anyway, back to Ian's Star Wars collection. We decided to label every slot with a number, starting at 1 and going to 243 (the size of the complete collection). More messy black ink and smudges than the nice clean digital equivalent:
int[] myIntArray = new int[243]*
* Yes alright, I know arrays in programming start at 0, but evidently the manufacturers of trading cards don't
Then we applied this algorithm
While there are still cards left in your pile{
Pick up the card on the top of the pile
Read the card id number
Insert the card into the slot labelled with the card id number
}
Simple! So now we can see where there are gaps in the collection, and it's easy to insert into the collection in the right place when you get a new card. The see through slots make it easy to gleefully browse your collection. Isn't computer science wonderful?
Comments