1, 2, 3, code ! - Cycle 3 activities - Step 2.5. Plugged and unplugged activities to better understand certain algorithmic concepts

Summary

Alongside their programming activity, students deepen their understanding of certain algorithmic concepts introduced during Step 4: variables, tests, loops, logical operators and even the notion of algorithm.

Key ideas
(see Conceptual scenario)

"Algorithms":

  • A loop allows the same action to be repeated multiple times..
  • A test can be used to choose which action to carry out if a condition is true or not.
  • A condition is an expression that is either true or false.
  • We can use logical connectors such as AND, OR and NOT to create logical expressions.
  • Sometimes, we settle for an algorithm that does not offer a perfect solution.

"Machines":

  • A variable is the name we give to a memory area. It is used to store a value and use it later or modify it.

"Machines"

  • For certain tasks, computers are much faster than people.

Inquiry-based methods

Unplugged activities (as well as a plugged activity)

Equipment

For Activity 1 (formative assessment of the loop concept)

  • Computer room

For Activity 2 (set of cards to consolidate the notion of variable):

  • For each group of 8 students:
  1. 4 whiteboards, 4 markers, 4 cloths
  2. 1 set of cards (cut out) from Handout 34, and Handout 35 (for greater durability, use cardstock)
  3. A 6-sided die

For Activity 3 (game to work on logical operators)

  • For each student:
  1. Handout 36
  • For each group of 4 students:
  1. Handout 37

For Activity 4 (traveling salesman game)

  • (Optional) for each group
  1. An 8 x 8 x 8-inch board (preferably) with around 20 nails driven in (as straight as possible) randomly.
  2. A 2 1/2-yard-long string, tied to one of the nails
  3. A felt-tip pen
  • For each student
  1. Handout 38

Glossary

Loop, variable, test, condition, logical expression

 

Foreword: When to do these activities

This step is different than the others in that the tasks are not required to program the video game. Rather, they are a series of activities (most are unplugged) designed to review certain algorithmic concepts used during the programming activity.

These activities are completely independent of each other and are optional: you can continue the project without doing them.

To not lose momentum on the project underway (video game programming in Scratch), we suggest doing the unplugged activities suggested here during another lesson slot than that reserved for programming. Ideally, they should be done during a Language Arts or Math class.

Activity 1 (plugged) can easily be incorporated into a programming lesson (simply spend ten minutes on it before going back to the project).

 


 Activity 1: Formative assessment on the loop concept (plugged, 10 to 20 minutes)

It is strongly recommended to do this activity after Step 4, during which students will have dealt with loops several times in Scratch. This loop concept can be consolidated through a series of short formative assessment exercises. These will also let students further explore the loops available in Scratch (because the ones we use in our program are "infinite" loops, but others do exist!).

All of this is available in Cycle 2 with Scratch Junior (see Lesson II.3, page XX), you can have students simplify the programming code by using loops. The program below (on the left) has an avatar draw a square. The program on the right gets the same result using a loop. Depending on students' levels, you can have them create the program on the right by themselves or give them all of the necessary elements unlinked and out of order and have them put everything in order so the program provides the same result as the one on the left.

 



This avatar draws a 100 pixel square.

This program does exactly the same thing using a loop.

 

We suggest the teacher to repeat this type of exercise as many times as necessary for students to gain a good grasp of what loops are and how they work.


 


 Activity 2: set of cards to consolidate the notion of variable (unplugged, 1 hour)

This activity tackles the notion of variable through a card game. It is a good idea to let students play this game several times because they begin to develop complex strategies. It can be played during lessons designed to work on mental calculations (scoring), Language Arts (work on card meanings), or tutoring work in small groups of 8 or 16 students. If the activity is done as a class, discuss what all the cards mean before starting. If done with smaller groups, explain the meanings of any specific cards that pose a problem.

The variables dealt with during the game are the players' scores. Certain cards affect these scores. When students are learning to play the game, only cards that make basic changes to scores are included. More complex cards can then be introduced, including those that change scores depending on certain conditions.

 

Introductory question: Game presentation

Nights are long at the planetary base. Once the explorers have finished their work for the day, they relax by playing indoor sports or board and card games. Their favorite game is a card game the students are going to play. The game is played with four teams (ideally pairs) named A, B, C and D. Set up workspaces with eight students. Each team must try to score as many points as possible as follows:

  • Teams A, B, C and D all start the game with 1 point, written on a whiteboard.
  • Each team is dealt four cards and the remaining cards are stacked face down (the draw pile).
  • The students look at their cards without showing them to the other teams.
  • Each team takes a turn and decides to choose one of their four cards. They read it out loud, place it face side up on the table, and follow the instructions. Some of these instructions affect the score of one or more teams. Any changes are noted on the whiteboards.
  • When all the cards have been played, the team with the most points wins.

The teacher gives an example on the board: they draw an aerial view of teams A, B, C and D around a table, with their starting scores of 1. Out loud, they read (or have a student read) a card played by team A, asking the class how the scores will change based on the card instruction. The scores are updated with the changes. The teacher then reads (or has a student read) a card played by team B and so on. They continue as long as necessary to make sure the entire class understands.

Alternative: You may decide to set up the game as a joint effort. In this case, the four teams at a workspace work together, without telling each other what cards they have in their hands, to get their final scores as high as possible.

 

Game with cards 1 to 24

The students play the game with cards 1 to 24 only from Handout 34. The cards that affect the scores explicitly give the name of the teams' scores to change (A, B, C and/or D) and the score changes do not depend on conditions.

During the group discussion, the teacher asks students if their scores stayed the same during the game or if they changed. They introduce the adjective "variable" but not as it relates to computer science. The class discusses the role of the whiteboard (to write down current scores and easily change them).

The teacher can then, if the students have already used Scratch:

  • Ask them to suggest a name for the scores of the four teams at a workspace, e.g., Score A, Score B, Score C and Score D.
  • Show them how to initialize the value of these four variables at 1.
  • Introduce the term "variable" as it relates to computer science: a variable is a memory area where you can save a value to reuse or modify later.
  • In Scratch, begin translating the most basic cards (1 to 8 to start, and more if the class is ready; see paragraph "Translating cards into Scratch language" below). The cards are now replaced in the game by their Scratch version.

 

Game with cards 1 to 36

The students play the game again, adding cards 25 to 36 from Handout 35. Some of the new cards designate scores to change based on a player's position (player's own score, score of the person to the right or across from you, etc.). Others introduce conditions (if your score... then...).

The cards are gradually translated into Scratch to replace the physical cards with their translation.

 

Game with cards 1 to 48

The students play the game again, adding cards 37 to 48 from Handout 35. Two of these new cards deal with random draws. The eight final cards should be filled in by the students.

The translation of the cards continues, without all cards needing to be translated.

 

Translating cards into Scratch language

Depending on how work in Scratch has progressed, certain cards will have been translated from English into Scratch (cards 1 to 8 to start).

For example:

  • Card 1 reads

  • Card 5 reads

  • Card 9 has two options:

    or    

 

The translation is divided among different student groups and discussed. Note that certain translations are somewhat complex (especially for cards from No.25) and others are impossible (cards that do not affect the scores or where the player's strategy depends on the context: their score, the scores of other teams, the cards remaining in their hands).

Some cards, such as No.32, require an additional variable to store a value temporarily.

 

Conclusion and group discussion

The students come together as a group to summarize what they learned from the card game:

  • During several hands, the players scores changed (they are variables). They are memorized at each step of the game. Similarly, the position of the players on the board game, the numbers of pawns they had, etc. were memorized and varied.
  • In programming language, a variable makes it possible to memorize a value that can vary while a program runs.

 

Further study

The students try and find different contexts in which computers used in daily life use variables to store data:

  • The time on a digital clock
  • The speed of a car displayed on a digital screen
  • A bank account balance

They try and find when these variables change or are used. For example, the time on a clock changes every second, and at a certain time, an alarm goes off. A bank account balance changes each time a withdrawal or deposit is made.

 


 Activity 3: A card game to work on logical operators (unplugged, 1 hour)

During the previous step, students used tests (if the rover gathers a resource, the score increases). The teacher explains to the class that the group of words "The rover gathers a resource" is an expression that can be true or false. This type of express is called a "condition".

There are two parts to this activity:

  • First, students become familiar with logical expressions by analyzing a scene (Handout 36).
  • Next, using vignettes with conditions and logical connectors, they express the condition that must be met for the space station alarm to be triggered (Handout 37).

 

Logic exercise (individual)

Each student receives Handout 36 and must indicate if the expression for each situation is true or false, or if it is impossible to know.

The answers are:

  • Expression 1: TRUE (this is rather clear)
  • Expression 2: FALSE (clear as well)
  • Expression 3: TRUE (a door is always either open or closed)
  • Expression 4: FALSE (a door cannot be both open and closed)
  • Expression 5: Impossible to know (nothing tells us the state of the door, unless we can see it at that moment)
  • Expression 6a: TRUE (both conditions are met at the same time)
  • Expression 6b: TRUE (only one of the conditions needs to be verified, which is the case here)
  • Expression 7a: FALSE (the second condition is not met)
  • Expression 7b: TRUE (only one of the conditions needs to be verified, which is the case here)

The students' compare their answers to the different expressions on the handout. The teacher makes sure the class agrees for each expression. It is likely that the expressions with an "OR" will be harder for the students to evaluate.

  • For expression "A or B" to be true, only one of the two sub-expressions A and B must be true. It is possible, but not necessary, for A and B to both be true. 
  • For expression "A and B" to be true, both A and B must be true.

If necessary, the class can invent new simple expressions to work with these logical conditions and test if the expressions are true or false using the illustrations on Handout 3 6(or for situations at school). If this is easy for students, present the expressions within a test rather than as isolated examples. For example: "The school bell rings if it's time for recess or if it's time to go back to class or if it's the end of the class."

 

Manipulating logical expressions: programming the base alarm

Once students understand this concept, the teacher gives students Handout 37 and divides them into small groups (maximum of four students per group). This handout reviews the previous notions in the context of our scenario (exploring the planet).

The teacher gives the students the following instruction: Cut out the vignettes, then arrange them into logical expressions. The aim is to describe a condition that will cause the space station alarm to go off.

For example, the alarm goes off:

  • IF "the security door is open"
  • OR if "it's night" AND "the rover is not at base"
  • OR if "oxygen levels are critical" AND "the base is occupied"
  • OR if "energy is low" AND "the base is occupied"
  • OR if "the generator is NOT working"
  • Etc.

First, the teacher makes sure all the students understand the vignettes, whether with regard to the conditions (cards with drawings) or the logical connectors (IF, THEN, AND, OR, NOT). The NOT is new and should be explained. The fact that the rover is not at base is written: "NOT (the rover is at base)." It may be necessary to have the class think of a few simple examples together, first orally, then using the vignettes for help. Once the students understand the concept, you can let them work on their own to find and write down other conditions.

The first condition is written:

 

 

The second condition is written:

 

 

Teaching notes:

  • The parentheses help make expressions easier to understand and are an integral part of the syntax. Moving parentheses can change what an expression means! Students can place their cards on a blank piece of paper and draw parentheses on the paper.
  • Depending on how comfortable students are with the material, the teacher can ask them to write each condition separately or write a single expression that includes all the conditions that will trigger the alarm (all these conditions are connected by "OR". In this case, it may be needed to print out several copies of Handout 37 so that each group can have more vignettes (especially the logical connectors)).

For each of the necessary conditions to trigger the alarm, the teacher makes sure that the students’ various suggestions are presented and discussed.

As a group, the class writes a single expression that includes all conditions. To make the expression easier to read, feel free to add parenthesis and write the expression over several lines:

 

 

The class summarizes together what they learned in this lesson:

  • In an algorithm, we can use tests that say which instruction should be done when a condition is verified or not.
  • A condition is an expression that is either true or false (but not both).
  • We can use logical connectors such as AND, OR and NOT to create logical expressions.

Students write down these conclusions in their science notebook. The teacher updates the "Defining computer science" poster by copying down what the class learned about the notion of logic during this lesson.

 

 


 Activity 4: Understanding that an algorithm is not always perfect: the traveling salesman game (unplugged, 1 hour)

Teaching notes:

  • This activity (optional) is aimed at older students (6th grade and up). It goes into greater detail about the notion of algorithm through a simple problem: finding the shortest route that goes by several locations. The aim is to show that sometimes a problem cannot be resolved, even if there is an algorithm that is supposed to work. You have to settle for an approximate solution, which may be imperfect but good enough.
  • Here, there is a simple algorithm to resolve the problem (try all routes and choose the shortest) but this algorithm cannot actually be implemented because the number of possible routes to try quickly becomes massive.

 

Inroductory question

In the previous lessons, students set up their program to be able to add another challenge: the rover must explore the map to recover all possible resources.

The teacher explains that the rover has a limited amount of fuel left and so they need to use as little fuel as possible. This is a "classic" optimization problem: "You know from the outset the number and location of the resources. You must find the shortest route that still goes by all of these resources and returns to the starting point."

The teacher asks the students if there is a method (algorithm) that can offer a solution to this problem. The group discussion shows that this question can be broken down into two more specific questions:

  • Does the problem have a solution? Of the various routes that go by all the resources, is there one that is shorter than the others (or more than one that are equally short)? The answer to this question is yes: there are several routes possible, so there will obviously be one (or more) that is shorter than the others.
  • Is there a method that will allow us to definitely find the shortest route? The class can suggest a method for finding this route: they simply need to test all the possible routes, measure them and select the shortest one.

Depending on the available materials, the teacher can do a single activity (based on the handout) or two activities (first the handout, then the experiment using the boards with nails).

 

Finding the shortest route (in groups)

The teacher hands out a copy of Handout 38 to each student (because there are so many routes to test and draw, it is best to give all students a handout). The aim is to find all the possible routes to find two (or three, or four) resources and measure the length of the routes using a ruler.

Note: It is assumed that the route only goes by the base twice: at departure and arrival.

 

Group discussion

The group discussion shows that the number of possible routes quickly increases as the number of resources to gather rises.

  • For two resources: If B is the base and 1 and 2 are resources, there are two possible routes: B12B or B21B. In fact, this is the same route followed in opposite directions.
  • For three resources, there are six possible routes, with three that are actually different:
    • B123B and B321B (the same route in both directions)
    • B132B and B231B (the same route in both directions)
    • B213B and B123B (the same route in both directions)
  • For four resources, there are 24 possible routes, with 12 that are actually different:
    • B1234B
    • B1243B
    • B1324B
    • B1342B
    • B1423B
    • B1432B
    • B2134B
    • B2143B
    • B2341B (same as B1432B above)
    • B2314B
    • B2431B (same as B1342B above)
    • B2413B
    • B3124B
    • B3142B (same as B2413B above)
    • B3214B
    • B3241B (same as B1423B above)
    • B3412B (same as B2143B above)
    • B3421B (same as B1243B above)
    • B4123B (same as B3214B above)
    • B4132B (same as B2314B above)
    • B4213B (same as B3124B above)
    • B4231B (same as B1324B above)
    • B4312B (same as B2134B above)
    • B4321B (same as B1234B above)

When all duplicates are eliminated, there are "only" 12 possibilities left, which is too many for students to find all of them and draw on a single map.

up: “only one route”
middle: “3 routes”
bottom: “many routes!”

 

(Optional) Finding the shortest route (in groups)

If there are enough boards with nails for each group, the teacher hands out the boards and asks the students to find the shortest route possible that has the string go around each nail (and return to the starting point). For each route tested, place a mark on the string to indicate the total length (which should be a short as possible). This activity is similar to the previous one except you need physical objects (nails, string) to let students easily eliminate certain "wrong" routes and intuit what might be the "right" route.

 

 

Group discussion

This group discussion highlights several things:

  • There are a large number of possible routes (no one will have been able to test them all).
  • At the start of the activity, progress is significant (students find shorter and shorter routes) but then tapers off (despite multiple tests, they cut routes by only a tiny distance).
  • Some students may believe they found THE best route. It is not possible to confirm this statement, but you can tell them that the "right" routes are those that do not cross over each other and limit backtracking.

Scientific notes:

  • The number of different routes, for n resources + 1 base (or n+1 nail, for the second experiment) is n! (which is read "factorial n"). This number is obtained by multiplying n by all lesser whole numbers down to 1. For example:
    • 1! = 1
    • 2! = 2x1 = 2
    • 3! = 3x2x1 = 6
    • 4! = 4x3x2x1 = 24
  • If you eliminate all routes that are identical but simply taken in opposite directions, for n resources, this results in n!/2 number of possible routes.
  • This function (which, for n number of resources linked to n!/2 routes) increases very quickly:
    • 5 resources:      60 routes
    • 6 resources:    360 routes
    • 7 resources: 2,520 routes
    • 10 resources: nearly 2 million routes
    • 20 resources: 1 billion billion possible routes
    • 100 resources: the number of possible routes is 157 figures long!
  • This is a "classic" algorithmic problem, known as the "traveling salesman problem." A salesman must visit several customers in an area. What is the shortest route to visit each one once?

The teacher explains to the class that the number of routes increases exponentially (they can explain that for 20 resources, there are more than a billion billion possibilities). They ask the students if they know a device that can find the best route among several options. Some students will likely say a GPS. By replacing resources with cities, the problem the GPS must solve is similar (although it differs slightly – the traveling salesman must go to all the cities, whereas a GPS must find the shortest route from one place to another, using passing through several intermediate points). What do you do when there are thousands and thousands of cities in a country and not just 20?

The class agrees that it is impossible to test all possible routes (even a supercomputer could not do this test in our lifetime!). A GPS computer proceeds in a way similar to the nail/board experiment: it determines a given route and alters it several times to reduce the route’s total distance. When it is unable to reduce the distance by a significant amount, it stops looking and suggests the best route from those it explored. To increase its chances, it may choose several routes randomly and alter each of them separately.

The GPS does not necessarily suggest the "best" route possible but a "pretty good" route. It is not surprising that two different GPS devices will suggest two different routes for a single destination because they feature different maps (one may have more details or be more updated than the other) and different algorithms.

 

Conclusion and lesson recap activity

The class summarizes together what they learned in this lesson:

  • Sometimes a problem is so long or complicated that we have to settle for an algorithm that provides an imperfect solution.
  • For certain tasks, such as finding the best route from numerous possibilities, computers are must faster than people.

Students write down these conclusions in their science notebook. The teacher updates the "Defining computer science?" poster.

 

 

Further study

  • Showing students The Imitation Game, which tells the story of Alan Turing's life, can illustrate in another context (here, breaking the Nazis' code during the Second World War) that is sometimes impossible to test all possibilities of a problem and that a method must be found to restrict the problem's size by focusing on "interesting" possibilities. Even in the movie, the possibilities well exceeded the abilities of one or several people. To resolve the problem, Turing and his team had to find not only an effective algorithm, but also create a machine to run it: this machine was the precursor of today's computers.
  • We can compare the itineraries provided by several webmapping services (Google Maps, Mappy, ViaMichelin, etc.) or several GPS providers and verify that these tools do not suggest THE best route (if they did, they would all suggest the same route), but a "pretty good" route.

 

 

 


<< Step 2.4 Sequence II Step 2.6 >>

 

Project partners

Aucun résultats