27 November 2010

Computer Class - Week #4

This post summarizes the material from week 4 of my computer class and includes a rough approximation of how I presented the material. These notes are not completely polished, so some of the transitions may seem abrupt.

Perfect shuffles

Materials needed: 2 decks of cards for every 8 students in the class. The two decks should each have a different colored back. I picked up a set of decks from CostCo that had an assortment of red and blue decks, but it doesn't matter as long as the card backs are obviously different.

I start class by handing out a small set of cards to each student:
  • 1 Ace (e.g., Ace of Spades with red card back)
  • 9 cards 2-10 in a different colored suit and different colored back from the Ace (e.g., 2-10 of Hearts with blue card back)
The reason for having the Ace be a different colored suit and card back color is to make it very easy to see where the card is. You can skip using different colored decks, but then you'll need to scan the cards for the Ace each time.

Activity: Perfect card shuffling

This is an interesting follow-up activity after you've introduced binary numbers to the students. The general idea is to have the them perform the shuffles, record the position of the Ace and then "discover" the pattern of binary numbers in the results.

Note that the worksheets are set up so that the cards are optional for the students. They can see where the Ace goes just by following the arrows on the worksheets.

If you intend to perform this, I recommend you practice shuffling a bit before teaching this the first time. Performing perfect shuffles is actually rather easy if you go slowly and carefully (it becomes hard when you want to make it look like a real shuffle but that's not necessary for this class). The hardest part of shuffling the cards for class is getting used to shuffling only 10 cards.

Boolean Logic

A boolean value is a way of describing objects by specifying whether a particular attribute is True or False. For example, a light could have the attribute 'isOn' which is True when the light is turned on and False when the light is off.

These attributes can be anything that you can give a True/False answer to:
  • isRaining – True if it's raining outside, False otherwise
  • hasRaincoat – True if you have a raincoat, False if you don't
Note that there can be a lot of ambiguity in these terms: What if it's only raining a little bit? What if it's raining here, but not over there? Do we say isRed=True if an object is mostly yellow, but has a little bit of red?

Boolean logic is an attempt to formalize the thought process and these expressions are used in computer programs (including games) to control what happens.

Also note that there are only 2 values: True and False. This sounds a lot like binary, with 0=False and 1=True. This is not a coincidence and we'll be discussing that in more detail later.

Activity: Describe objects in the room
Have students choose objects in the room and then come up with boolean attributes to describe the objects. When the students suggest an attribute (like 'it's bigger than my head') convert it into a True/False boolean attribute ('isBiggerThanMyHead'). As new objects are brought up, discuss whether the attributes from the previous objects would be True or False for the new object.
Boolean Operations

In addition to the basic attributes, there is also a set of boolean operators that can be used to combine these properties to create new ones. For example:
getsWet = isRaining AND NOT hasRaincoat
These boolean operations are NOT, AND, OR and XOR.

NOT

The NOT operation changes True to False and vice versa. So if 'isCat' is True, then 'NOT isCat' is False.

Note that in English, we would probably say “is not a cat”. In logic, we say “not is-a-cat” or 'NOT isCat'.

AND

a AND b is True only if a and b are both True.

So if you have 2 boolean statements 'isCat' and 'hasStripes', then 'isCat AND hasStripes':
  • is True for striped cats
  • is False for spotted cats or striped dogs

OR

a OR b is True if either a or b (or both) are True.

So 'isCat OR hasStripes':
  • is True for striped cats, spotted cats, striped dogs
  • is False for spotted dogs
Note that is somewhat different from the way we think about 'or' when we talk. At a restaurant, when you are offered a choice of soup or salad, you can only choose one. In logic, both sides can be True and the result is True.

XOR

a XOR b is True if either a or b (but not both) are True .

So, 'isCat XOR hasStripes':
  • is True for spotted cats, striped dogs
  • is False for striped cats, spotted dogs

NAND, NOR, XNOR

For convenience, we also have NAND, NOR and XNOR, which are simply shorthand for NOT-AND, NOT-OR and NOT-XOR.

Note that XNOR is not a great name - it would be more accurate to call it NXOR. However, XNOR is the commonly accepted name (and in any case, 'ex-nor' is slightly easier to say than 'en-ex-or').

Object Properties

These worksheets introduce the students to describing objects with boolean variables like "isBlack" or "isCircle". For each object, they identify whether each boolean value is True or False.

Worksheet: Object properties

After determining the attribute values for each object, the students will then group related objects. Finally (on the 3rd worksheet), they will construct boolean expressions that are True for a selected set of objects (without including any extras).

Nethack

Nethack is a dungeon exploration computer game that was originally released in 1987. In this activity, we discuss the boolean properties and expressions used in Nethack to determine when the player is petrified (turned to stone) by a cockatrice (one of the monsters in the game).

Activity: Boolean logic - Nethack

Describing Objects

In this activity, I go around the room and ask each student to think of an object and then think of a property that can be used to describe it. For example, you could think of an Apple and describe it as being "red" or "green" or "tasty".

I take the most interesting of these descriptive terms, convert it into a boolean True/False attribute and write it on the board. Once you go around the entire class, you should have a fairly useful set of attributes on the board.

For this particular class, the students came up with:
  • isBouncy
  • isYummy
  • isFrozen
  • canTalk
  • isFuzzy
  • isAddictive
  • isWet
  • isSquishy
Now, given these attributes, pick two at random, connect them with an AND operator and ask a student to think of an object for which that expression is True. For example, choosing "isWet AND isSquishy" might results in the student suggesting a sponge.

I was actually quite surprised how creative the students were with their responses. Here are a number of examples from class:
  • isYummy AND isSquishy = jello
  • isFuzzy AND isFrozen - ice kitty (kitty frozen in snow)
  • isFurry AND isYummy - kiwi
  • isWet AND isSquishy - squid
  • isAddictive AND isYummy - brownies
  • isYummy AND isBouncy - grapes
  • isFurry AND isSquishy - gerbil (although you really shouldn't squish it!)
As you can see, isYummy was a student favorite.

Once the students have given a couple of objects from the AND operator, these can now be used to test their understanding of NOT, OR and XOR. For this part, I take a couple of attributes, combine them with OR and XOR (and optionally use a NOT) and then ask if the expression is True or False for each object:
  • isFurry OR isWet
    • squid (T), brownies (F), ice kitty (T), ...
  • isYummy XOR isAddictive
    • brownie (F), jello (T), gerbil (F), kiwi (T), ...

Describing Objects II

For the last activity, I bring in a set of related objects and have the students create attributes to describe them.

For this class, I brought in some Lego bricks (of different colors and sizes) and a few playing cards. The students came up with the following descriptive attributes:
  • isSquare
  • isRectangle
  • isGrayDark
  • isGrayLight
  • isPlastic
  • is2x4
  • is2x2
  • isRed
  • isPaper
  • isBlack
  • isLimeGreen
  • isAce
  • isLetter
  • isHearts
And then I selected a few of the objects and asked the class to come up with a boolean expression to select just those objects. This is similar to the 3rd page of the Object Properties activity done earlier in the class.

In retrospect, the Lego bricks were probably a bit too small and perhaps a bit too distracting, but they worked well enough. Next time, I may experiment with different (larger) objects.

No comments: