Warning
This chapter is still in development
Warning
This chapter will be written during 2013, but in the meantime there is a lesson plan that covers the material available from the NZACDITT site. The content of this chapter will relate to this lesson plan.
Note
For teachers
This chapter supports the programming languages part of the NZ achievement standard AS91074 (1.44).
Points to cover -What an algorithm is -Examples in everyday life, how algorithms can be used by humans as well. -Example of good vs bad algorithm, make this an interactive similar to the algorithms race
Key concepts that are likely to be encountered are: Algorithms: Techniques: Applications: Possible activities:
[some introductory activities/ideas to open up the topic] [ACM curriculum has some info on reason for studying algorithms]
[an area that is worth knowing about, including activities/exercises to explore it, and guidance for teachers (possibly to be separated) on how to help students use this topic for A/M/E
Note
For teachers The present searching game in this section is split into two parts, the first (levels 1 and 2) corresponds to the Linear Search algorithm (also known as Sequential Search) and the second (levels 3,4 and 5) corresponds to Binary Search. We recommend you play through the levels yourself while, or after reading this description. It is based on the CS Unplugged Battleships game, http://csunplugged.com/searching-algorithms, which can be used as a classroom activity to enforce the lessons in this chapter (the hashing activity is not used for the present searching game). The present searching game can be done individually by students as they read through the chapter or in groups.
The Linear search algorithm is, in plain english, check if the first item in a list is the item you are searching for, and if it isn’t then move on to the next item. This continues until the correct item is found, at which point the algorithm ends. In the first part of the game the numbers are in a random order and so there is no method to finding the pet, the student simply chooses a box, checks if it’s correct and if it isn’t they move on to another box. The average number of checks Linear search has to do to find an item in a list is half the total number of items in the list, but it should be noted that sometimes it will only take one check (when the item being searched for is the first one in the list) and sometimes every single item in the list will have to be checked (if the item being searched for is the last item in the list). In practice Linear Search can be applied to a sorted list as well, the list does not have to be in a random order.
The Binary Search algorithm can only be used if the list being searched has been sorted into some sort of order. The binary search algorithm is as follows. Check the item in the centre of the list, if it is the item you are looking for then you are finished, if it is smaller than the item you are looking for then ignore all items in the list before the centre, or if it is bigger than the item you are looking for then ignore all items in the list after the centre. You then repeat this process for the section of the list that you are left with. This means you are halving the number of items left to search each time you check an item. If there are n items in the list then Binary search will take on average log₂(n) checks. An easier way to explain the amount of checks Binary Search takes is to say divide the number of items in the list by 2 (if the result is a decimal then round up to the nearest whole number) and keep doing this until you get to 1, the number of times you divided by 2 is the maximum number of checks that Binary search would ever have to make to find an item in that list.
The game would also work well as a classroom activity. Get all the students to play each section of the game at the same time and then when they have all finished have a discussion about the results. After students have finished the first part (levels 1 and 2) ask them questions like “Did anyone find the pet on the first go?”, “Did anyone only find it after checking every other present?”, or find the average number of presents students had to open to find the pet (this should be around 5 for the first level and around 10 for the second). While they are playing the second part (levels 3,4,5) some may have trouble finding the correct algorithm to find the pet. If they are finding these levels confusing you can give them a hint like “Why don’t you start by opening the present in the centre” and when they do ask them “What does the number you found tell you about all the numbers before it?” if the number is smaller than the one they are looking for, or “all the numbers after it?” if the number is bigger than the one they are looking for. When students have finished ask them questions like “Where you able to find the pet even though you had less lives? What strategy did you use to find the pet?”, we have found that many students will have ended up doing a binary search (or similar) without even knowing what a binary search is! Explaining these algorithms to students is likely to be easier now that they have seen them in action.
[an area that is worth knowing about, including activities/exercises to explore it, and guidance for teachers (possibly to be separated) on how to help students use this topic for A/M/E
[an area that is worth knowing about, including activities/exercises to explore it, and guidance for teachers (possibly to be separated) on how to help students use this topic for A/M/E
[an area that is worth knowing about, including activities/exercises to explore it, and guidance for teachers (possibly to be separated) on how to help students use this topic for A/M/E
[explain where the material above has oversimplified things, and if there are any well-known concepts or techniques that have been deliberately left out because they are too complex for this age group. This may include things that require advanced maths, advanced programming, or things where students have seen the problem but not a thorough solution]