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.

Computer Class - Week #3

This post summarizes the material from week 3 of my computer class and includes a rough approximation how I presented the material.

Counting in Binary

We start each class with a small exercise. This week the students need to count in binary from 0 to 15, padded out to 4 digits. As they say the number, I write it on the board.

I start with '0000' and then we go around the room with each student giving the next number: '0001', '0010', '0011', '0100', '0101', ...

The reason why we start with this counting (padded to 4 digits) is that they are actually practicing the binary-hex conversion table. They haven't learned hexadecimal yet, but we'll be covering that today.

[Note: After a week or two of this, all the students know it pretty well, so they all just say the numbers in unison.

Once another teacher overheard this exercise and was somewhat surprised to hear the students intoning "zero-zero-one-zero-one-one-...". They were all saying the numbers in a monotone and it sounded like they were chanting. I'll have to remember to dim the lights and light a few candles and incense for next time.]

Binary-Decimal Conversion

"As we discussed last week, binary is for computers, and decimal is for humans. People can have a difficult time dealing with binary numbers directly, so it's good to know how to convert back and forth between the two number systems."

"Thus, we continue with some worksheets showing how to convert between decimal and binary:"

Worksheet: Converting from Binary to Decimal

Worksheet: Converting from Decimal to Binary

"The process isn't difficult, but it does take time and is hard to do in your head for anything but the most trivial conversions."

Rembering Binary Numbers

"In addition, binary numbers can be rather long and hard to remember. For example, I'm going to write a number on the board and ask you to remember it."

"For comparison, let's start with decmial. I'm going to write a number on the board:"

I write the following decimal number on the board:

571,842

After about 5 seconds, I cover it up and then ask if anyone remembers the number. Pretty much anyone in the class is able to remember the number.

"Now let's try the same this with a binary number of roughly the same magnitude."

I write the following binary number on the board:

10100000010011110101

As before, I cover it up and then ask if anyone can remember the number. I like to be a bit mean here and ask things like "Hmmmm... does anyone remember... was it 001001000 or 101101110?", using random sequences of '0's and '1's.

Now, with the binary number still covered up, I write the number again on the board. When I uncover the original number, everyone can see that they're the same number.

"So, how did I remember that long binary number? Well, I cheated. And I'll be showing you in this class what I did."

[Note: Of course, the trick is that I didn't really remember the binary number. I just thought of a 5-digit hex number and remembered that instead. When I needed to write the number, I just converted from hex to binary as I was writing. In the above example, I remembered the "A04F5" instead of the long string of binary digits.]

Hexadecimal

"OK, so binary numbers are tedious to use directly, and there's no trivial way to convert them into decimal. What are we going to do?"

"The answer is hexadecimal, which is base 16."

"Hexadecimal is just like all the other number systems we've discussed except that we need 16 symbols. We re-use 0-9 from decimal, but we need 6 more symbols. We can choose anything, but by convention we use the first 6 letters of the alphabet:"

Hex number:	0	1	2	3	4	5	6	7	8	9	A	B	C	D	E	F
Decimal equivalent:	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

[Sidenote: Sexadecimal?
Positional number systems are typically named using the Latin prefixes, hence octal (oct- = 8), decimal (deci- = 10) and duodecimal (duodeci- = 12). Given this convention, base-16 is more correctly referred to as sexadecimal since sexa- is the Latin prefix for 6 (as in sexagesimal for base-60).

The term hexadecimal is an unnatural combination of Greek (hexa- = 6) and Latin (deci- = 10) prefixes, but has gained acceptance as the preferred name for base-16.

This is probably a good thing, considering how often I tend to abbreviate the number system as "hex".]

Worksheet: Counting in Hexadecimal

"So, how does hexadecimal help us with binary? Let's compare the different number systems."

Activity: Number cards

First lay out the binary cards from right to left:

Binary:

256

128

64

32

16

8

4

2

1

Now line up the octal cards with the binary cards:

Binary:	256	128	64	32	16	8	4	2	1
Octal:			64			8			1

Then add the hexadecimal cards:

Hex:	256				16				1
Binary:	256	128	64	32	16	8	4	2	1
Octal:			64			8			1

Now try to line up the decimal cards:

Decimal:		100			10				1
Hex:	256				16				1
Binary:	256	128	64	32	16	8	4	2	1
Octal:			64			8			1

Notice the following things:

• Octal lines up with every 3rd binary card
• Hexadecimal lines up with every 4th binary card
• Decimal doesn't line up with any binary card (except 1)

"This property makes is very easy to convert from binary to either octal or hexadecimal. Hexadecimal is effectively a shorthand notation for binary. This, by the way, is the trick that I used earlier in the class - I didn't remember the binary number. I remembered a hex number and just converted to binary as I was writing it."

Worksheet: Converting from binary to octal

Worksheet: Converting from binary to hexadecimal

"So this solves one of the problems with binary - that there were too many digits to remember. It's still a bit of work to convert to/from decimal, but we can avoid this by sticking with hexadecimal as much as possible."

"Note that we just as easily could have used octal instead of hexadecimal to solve this problem. In fact, many early computer systems made extensive use of octal and grouped bits in sets of 3 (and had byte sizes of 6 or 9 bits). While there are a few places where octal is still used in computer science, hexadecimal is by far the preferred base to convert binary. Besides, grouping 4 bits at a time seems more "power of two"-ish than grouping them by 3's."

New base-sixteen.org listings: 7-13 Nov

Recently added resource listings at base-sixteen.org. Some of the CS Unplugged resources were already listed, but I finally went through and made sure they were all present and accounted for.

Racket/Scheme/Lisp

How To Design Programs - An Introduction to Programming and Computing - A free book that provides an introduction to programming using Racket (a dialect of Scheme). This was created as part of the "Teach Scheme - Reach Java" project.

Bookstrap - A middle-school curriculum for introducing students to programming based on "How to Design Programs".

How to Design Worlds : Imaginative Programming in DrScheme - A collection of project assignments for "How to Design Programs" and "Bootstrap".

DrRacket - A freely-available, cross-platform IDE for Racket. Formerly called DrScheme.

WebScheme - A cloud-based IDE for creating programs in Racket.

National Center for Women & Information Technology

Computer Science-in-a-Box: Unplug Your Curriculum - Collection of CS Unplugged activities in single, easy-to-download PDF.

Computer Science Unplugged

1: Count the Dots - Binary Numbers
2: Colour by Numbers - Image Representation
3: You Can Say That Again! - Text Compression
4: Card Flip Magic - Error Detection & Correction
5: Twenty Guesses - Information Theory
6: Battleships - Searching Algorithms
7: Lightest and Heaviest - Sorting Algorithms
8: Beat the Clock - Sorting Networks
9: The Muddy City - Minimal Spanning Trees
10: The Orange Game - Routing and Deadlock in Networks
11: Treasure Hunt - Finite-State Automata
12: Marching Orders - Programming Languages
13: The Poor Cartographer - Graph Coloring
14: Tourist Town - Dominating Sets
15: Ice roads - Steiner Trees
16: Sharing Secrets - Information Hiding Protocols
17: The Peruvian Coin Fip - Cryptographic Protocols
18: Kid Krypto - Public-key Encryption
19: The Chocolate Factory - Human Interface Design
20: Conversations with Computers - The Turing Test

Santa's Dirty Socks - Divide and Conquer - An animated video showing how Santa used a divide-and-conquer approach to save Christmas.

Kevin Carey: "Decoding the Value of Computer Science"

The Chronicle of Higher Education has an interesting piece by entitled "Decoding the Value of Computer Science".

The author, Kevin Carey, intended to major in Computer Science back when he entered college, but switched to a humanities major to avoid early-AM classes. While he had spent a fair amount of time programming in BASIC and Pascal up to that point, he basically stopped all programming at that time.

However, he was able to make use of his programming and logical reasoning skills in his non-CS careers: at the Indiana state-budget office and later as a writer. This article is a great read that underscores why we should have CS in the core K-12 curriculum.

(via BrainLog)

New base-sixteen.org resources: 31 Oct - 6 Nov

The following resources have been added to the base-sixteen.org catalog during the past week. The base-sixteen.org website is attempting to collect links to all useful Computer Science education materials on the web (and it allows user comments and ratings).

	Octal Counting Worksheets Worksheets where the student is given a set of circles to count in octal and then convert the result into decimal. The circles are arranged in groups of eight to make the octal calculation straightforward.
	Octal Dots Worksheet Similar to the first worksheet, but in this case the students are given an octal number and they must draw the correct number of dots before converting into decimal.
	Counting in Octal Worksheet Students must count from 0 to 63 (but in octal, so they need to count from 0 to 77).
	Counting in Binary Worksheet Students must count from 0 to 63 (but in binary, so they need to count from 0 to 111111).
	Counting in Hexadecimal Worksheet Students must count from 0 to 63 (but in hexadecimal, so it's really 0 to 4F).

Perfect Card Shuffles and Binary Numbers

Yesterday (November 1) on KUOW Presents, they presented a segment from Wisconsin Public Radio's "To the Best of Our Knowledge" that talked about Math and Magic Tricks and Binary numbers.

They interviewed Persi Diaconis, a magician and mathematician who is currently a professor of Statistics and Mathematics at Stanford University. In one part of the program, they talked about how card magicians (and poker cheats) can use knowledge of binary numbers and 'perfect' card shuffling to take a card at the top of the deck and move it to any desired position in the deck while apparently shuffling the cards into a random order.

The link to Jim Fleming's complete interview with Persi Diaconis is near the bottom of the "To the Best of Our Knowledge" page for this program under the "Special Web Extras" section. The uncut interview is ~34 minutes, roughly 12 of which made it into the KUOW Presents show. The part on using binary and perfect shuffles runs from around 4:54 - 6:40, but I found the entire interview interesting.

I need to turn this into classroom material because I'm sure that the students will find it fascinating.

Computer Class - Week #2

This class continues with the number system (binary, octal) work that we started last week. Because these first few classes are review of material that I covered with these students previously, this post will fill in some gaps by including material from last spring (when I first introduced binary/octal).

Binary Quote

Before class starts, I write the following quote along the top of the whiteboard (high enough that it's out of the way for the entire class):

"There are 10 types of people in this world, those that understand binary and those that don't."

If anyone asks about it, I say that we'll cover it at the end of class.

[Note: This quote should only be used for the first class that you introduce binary, otherwise it won't be nearly as effective. I used this quote last spring with these students when I introduced binary, but did not use it in this review class.]

Powers of Two

At the start of each class, we begin with a simple exercise. For the first few classes, we cover the powers of 2. I first (jokingly) check to make sure that everyone knows how to multiply by 2 and then write:

1
2
4

and then go around the room asking the students to multiply the previous value by 2:

8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536

I usually stop at 65536 and then point out 2⁸ (256) and 2¹⁶ (65536) as values that we'll be encountering later as we learn more about computers.

Review Octal

Even though my goal is to teach binary and hexadecimal, I always start with octal since I believe that it's an easier transition from decimal: when counting in binary, new digits are added rapidly for the first few number and this can be confusing. And with hexadecimal, we're adding additional symbols into the mix, so it's easier to introduce that once they've already mastered an alternate number system.

So, what did we cover last week? Numbers, binary, octal. We're going to continue with that this week.

I briefly review place-value number systems and describe base-10 (decimal) and base-8 (octal).

Decimal is based on 10's. It has 10 digits (0-9), and the places are based on 10:

1000's	100's	10's	1's
10x10x10	10x10	10	1
103	102	101	100

Octal is based on 8's. It has 8 digits (0-7), and the places are bases on 8:

512's	64's	8's	1's
8x8x8	8x8	8	1
83	82	81	80

[Sidenote: I use this opportunity to remind the students that any number raised to the 0^th power is 1. If the students were thinking of powers as "how many times do I multiply this number by itself" then this result will seem odd (since you'll expect the answer to be 0). Hence, this is a great opportunity to reinforce the correct answer.]

Octal Worksheets

To practice a bit with octal, we start with a few worksheets:

Worksheet: Octal counting (1 & 2)

These worksheets have the students count circles that are pre-arranged into groups of eight to make it easy to determine the octal number. In addition to writing the octal number, the students must also write the corresponding decimal number.

I hand out these worksheets in class and then give the students a few minutes to complete them before going over the answers. The purpose of this worksheet is to make the numbers concrete (by using the circles) since that helps break the association that (for example) the number '10' always means ten items (it means ten items in decimal, but eight items in octal). In addition, these worksheets also allow practice with the idea that ten items can be written in multiple ways: '10' in decimal, or '12' in octal.

Worksheet: Octal dots

This is similar to the previous worksheet except that they students are now required to draw the correct number of dots and then convert to decimal.

When reviewing the answers for these worksheets, I point out that the answers can be checked by simply multiplying out the numbers by the place values. So if you have octal 35, you can break it up as:

= 3 in the eights position, 5 in the ones position
= 3 x 8 + 5 x 1
= 29

This is a direct result of how positional number systems work, and it parallels what we do in decimal, where 29 is really 2 x 10 + 9 x 1.

[Sidenote: Depending on how much you want your students to suffer, you can tell the following octal joke: "Why do computer programmers often confuse Christmas and Halloween?" Answer: Because Oct 31 = Dec 25 (Octal 31 = Decimal 25).]

Worksheet: Counting in octal

This is the last of the octal worksheets and has the students count from 0 to 63 in octal.

[Sidenote: I make sure that I hand out this worksheet out after I finish all of the octal-decimal conversions that I want to cover in class. One time I had the students do this worksheet first and some of them kept it around as a reference for the later work. This meant that they were thinking less about the number representation/conversion and doing simple table lookups to get the answer.]

Review Binary

For binary, it follows the same pattern that we saw with decimal and octal:

Here's the decimal information for comparison: Decimal is based on 10's. It has 10 digits (0-9), and the places are based on 10:

1000's	100's	10's	1's
10x10x10	10x10	10	1
103	102	101	100

Binary is based on 2's. It has 2 digits (0 and 1), and the places are bases on 2:

32's	16's	8's	4's	2's	1's
2x2x2x2x2	2x2x2x2	2x2x2	2x2	2	1
25	24	23	22	21	20

At this point we practice converting numbers between binary and decimal. I describe the process on the whiteboard and the students practice:

• Converting a decimal number into binary by repeatedly subtracting powers of 2.
• Converting a binary number into decimal by adding the power-of-2 that corresponds to each '1' digit in the binary number.

[Sidenote: I created some worksheets for this, but didn't have them ready in time for this class, so I'll provide more details in my post for next week's class.]

If there is time, I also like to introduce the Binary Magic Trick just after I cover how to convert from binary to decimal. Be prepared for the students to be really disappointed when they learn how the trick works - the younger students especially seem to prefer to live a world where you were able to magically read their mind (rather than simply convert from binary to decimal).

Binary Worksheets

Worksheet: Counting in binary

Similar to the "Counting in octal" worksheet, but this time for binary. The students must count from 0 to 63 in binary ('0' to '111111')

Wrapping up

In summary:

• Binary is for computers, decimal is for humans
• Converting between decimal and binary is not difficult, but it is tedious:
  
  • Converting binary to decimal requires lots of adding
  • Converting decimal to binary requires lots of repeated subtraction

Since it's annoying to do this conversion all the time (especially for large numbers), we'd like to have an easier way. And we'll cover that next week.

Binary Quote (part II)

At the very end of class, I go back to the binary quote written at the top of the board. I ask a student to read the quote aloud. Invariably, they will start off with "There are ten types of...", and I'll stop them at that point and write "ten" on the board?

"Does it say 'ten'? I don't see a 'ten' there - I see a '1' and a '0'."

This is usually sufficient to make the connection, but if needed, you can ask the students what '10' is in binary.

I now congratulate the students on their transition from the "those that don't" group into the "those that understand binary" one.

[Sidenote: I once asked a student what he thought the quote was about when he first read it at the beginning of class (before he knew binary). He responded that he thought it was unfinished and that I would be adding 8 more items later.]

End of class. Next week we'll continue with converting between number systems and introduce hexadecimal.