Materials for teaching transistors and logic gates

As part of my computer class that I teach to upper-elementary/middle-school students, I have a section on transistors and logic gates. The goal is to introduce the "atoms" (transistors) and "molecules" (logic gates) that are used in digital computation, and the topic ends with the students learning how computers perform addition.

Since I want to focus on digital computation, I try to keep the electricity part as simple as possible while still teaching the basics needed to understand how digital logic gates are implemented. For this reason, I discuss CMOS transistors. What's nice about CMOS is that there is no need to introduce any other electrical component (like resistors or capacitors) to understand how to build logic gates in CMOS.

In this simplified presentation, voltage is all that matters and we can basically ignore the details of electric current. All you need to know is that electrons at Ground potential (0V) represent '0's and electrons at Power potential (usually +5V) represent '1's.

Cards & Yarn
When I was first teaching this topic (a few years ago), I started by using laminated paper images of transistors that I connected with yarn (for the wires) using paper clips. The cards & yarn are used to layout a simple CMOS circuit and then the students have '0' and '1' markers flow through the circuit.

These were very low cost and worked acceptably well for the lesson.

Transistor cards connected with yarn

But there were a few problems:

• More difficult/time-consuming to build. In most cases, I ended up building the circuit and showing the students how it worked because it was a bit messy to get everything connected properly.
• Difficult to 'reset'. Once you were finished with one set of inputs, you need to remove all the markers to reset things for the next set of inputs. And you can't just sweep the markers away because that will mess up the connections. This made the activity less suitable for students to work on independently.
• Gets confusing when the yarn overlaps. With the NAND and NOR circuits, the yarn 'wires' overlap which can make it confusing to follow. This can be mitigated by using different colored yarn, but it's still a problem that needs to be dealt with.
• Weak against wind attacks. The materials are light, so a slight breeze from an open window can be enough to mess up your carefully constructed circuit. They can also be messed up easily by a student accidentally brushing their sleeve across the work area.

Laser-cut tiles
To address these problems with the paper & yarn approach, I started experimenting with using laser-cut wooden tiles. I drew a set of prototype tiles using Inkscape and had them fabricated either locally at Metrix Create:Space or online using Ponoko.

Each tile is roughly 1.5" on a side, and there are tabs on all sides so they can interlock like puzzle pieces. They need to be cut from opaque material, so I chose 1/8" inch wood stock.

Here are the basic tiles I created:

Power			Ground
Input/Output
nMOS Transistor			pMOS Transistor
Straight wire			Bent wire
"T" connection			Wire crossover

The tiles ended up looking very nice and the students find them much more satisfying to work with. I can now give each student (or pair of students) a set of tiles and a circuit to create and they will work independently.

Here are some pictures from the most recent batch of tiles (these ones arrived from Ponoko):

9x9 tiles in package

Removing the upper wax protective sheet

Close-up of nMOS & pMOS transistor tiles

Removing tiles from the sticky wax backing paper

After removing the tiles, I group them into student packets that contain the tiles needed to construct the logic gates I cover in class.

Starting to build...

Here are a few pictures of the students working with the tiles in class.

Building an inverter

Constructing a NAND gate

Another student's NAND gate

Sadly, the one downside to these materials is their cost. The paper & yarn version costs practically nothing, while having the tiles custom laser-cut can be rather expensive. This is especially true if you want to have enough materials for an entire class.

What about using real transistors?
Another option that I considered was to use actual transistors in class. However, I opted against it because:

• Students can't see what's going on. The transistor itself is a black lump of plastic with 3 wires coming out and the electrons are not visible in the wires. While this might not be a serious problem for older students, I wanted the materials to be appropriate for younger students as well.
• Adding LEDs requires more knowledge of electronics. If we want to add LEDs to make the input/output values visible, then we need to pay more attention to electrical current and also add resistors. This would not only complicate the lesson, but it would also introduce material that would be a distraction from the primary goal of understanding digital logic.
• I'll be covering electronics later anyway. Later in the school year, we'll be working with Arduinos and lighting up LEDs. No need to rush this material now.

Making available
I'll be releasing these materials in the near future: image files for laser-cutting (so you can cut your own tiles if you want) and worksheets for using the tiles in class. I'll also have the original transistor cards released as well since that's the low-cost way to try out these lessons.

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.

Google Code-in and Exploring Computational Thinking

I run across a large number of education links that talk about how to use a particular computer program or website to create lesson plans or other classroom materials. For example, there are pages like:

• Using Google Docs: Docs for teachers
• Creating a lesson plan with Word

I suppose that I run across these a lot because they (on the surface) seem to apply to the topic of 'teaching' and 'computers'. As someone who teaches how to program computers, it can be frustrating that these 'how to teach using computers' pages seem to drown out the content that is of real interest to me.

I can accept the fact that there are more educators out there trying to use computers than there are trying to teach computers and so, Yes I can see how these pages are serving a useful purpose. But No, I still don't find them particularly interesting.

The reason I bring this up is because I've recently come across not one, but two interesting links to Google projects that I think are interesting for people teaching computer science in 6th through 12th grade. Since I work for Google, I was hesitant because I tend to be suspicious of other people who push their employer's projects on their blogs, so I was starting to get suspicious of myself. I don't want this blog to start linking to every 'How to use Google product X in your classroom' document on the web.

But having thought about it a bit, I really think that these projects are both interesting and relevant to K-12 Computer Science educators.

Google Code-in 2010

The first one is Google Code-in 2010, announced back on 7 October 2010. As I read the description, it sounds like Google's Summer of Code (SoC) but for pre-university students.

If you're unfamiliar with SoC, it is basically a summer job for college students where they are paid by Google to work (from home) on a selected set of open source projects. The open source projects act as 'mentor organizations' for the students as they work on their assigned summer task.

For the Code-in, each open source project will propose a set of tasks and students will claim tasks to work on. When the task is done, the mentor organization will evaluate the work and accept the task as done (assuming the work was done properly). For every three tasks, the student gets $100, up to a max of $500.

As is stated in the Code-in FAQ:

It is Google's not so secret hope that the student contestants of today will be long-term contributors to these and other open source projects in the future.

In other words, they hope that students participating in this contest will become computer scientists and programmers.

This is open to students between the ages of 13 and 18 (as of 22 November 2010) and runs from 22 November 2010 until 10 January 2011. The list of mentor organizations hasn't been announced yet, but the list will be posted on the Code-in site on 5 November 2010.

If you're interested, be sure to check out main Code-in site. There are many more details than I can give here, and any updates or changes will be posted there.

Exploring Computational Thinking

The second link of interest is to Exploring Computational Thinking. This site contains a set of lessons created by teachers that can be used to demonstrate computational thinking in a variety of math and science topics, such as:

• Calculating percent change
• Determining the distance between 2 points
• Finding the roots of an equation
• Understanding Filters (in Cellular Biology)

The site was announced earlier this week so it's still fairly new, but it already contains over 60 different lessons for grades ranging from 6th through 12th.

It will be interesting to see how people make use of these materials since it seems (to me) that they might be most useful for non-CS teachers interested in including some CS material. Although CS teachers should also find the material useful since the lessons make a nice summary of how CS ('computational thinking') can be relevant to math and science education.

Using PlainCards to create classroom materials

For a while I've had my eyes open to pick up some printable cardstock that was pre-perforated to make 'playing card'-sized classroom material.

I've tried printing the cards out on regular paper, but that doesn't feel right when you have a stack of them. Laminating helps make the cards sturdier, but they still don't slide off each other the way regular playing cards do (and the cards tend to stick together a bit).

The standard place to go for cardstock products like this is Avery, and they have a number of products that are almost (but not quite) like this: they list Business Cards, Greeting Cards, Note Cards, Index Cards, Postcards, Tent Cards, Rotary Cards, and ID Cards.

But not Playing Cards.

This is unfortunate because the cardstock products that they have don't work well for cards that you want to stack and hold in your hand. Either the size is wrong (business cards are too small; greeting and note cards are too big) or the cards don't slide against each other well.

PlainCards

However, a company called PlainCards makes exactly what I was looking for: micro-perforated cardstock that you can run through your printer to make custom cards.

My immediate need was to create "number system" cards to teach binary, octal and hexadecimal, so I picked up a set of the Blank Playing Cards with Pattern Backs.

These are blank on one side and have a standard 'playing card' pattern on the back so that you only need to print on one side. They also offer cards that are blank on both sides so you can print your own card backs, but this seems unnecessary for classroom material.

Software

To layout the card designs, PlainCards offers their own QuickCards3 software. This is free to download, but you need to buy it for ~$17 if you want to be able to print. I can't comment on the quality of the software since I haven't used it, but I didn't feel it was worth purchasing. One annoying thing about how they market this software is that they divide it into three separate versions: one for Playing Cards, another for Game & Trading Cards and yet another for Tarot Cards. Of course, you have to buy each one separately (or get the special bundle pricing).

Rather than use their software, I created some blank templates in Inkscape, which is a freely available, open-source vector drawing package (download here for Mac, Windows, et al.). Note that these template are SVG files, so they should work fine in any vector drawing application like Illustrator or Freehand.

Download: PlainCards Blank Template

The templates are quite simple: they contain boxes marking the micro-perforation outlines on the PlainCards cardstock. To use the templates, simply:

• Add your design/artwork
• Use the bounding box outlines to center the design for each card
• Delete (or hide) the bounding box outlines
• Print

Note that the perforations are centered and symmetric on the cardstock, so you don't need to worry about paper orientation when printing.

Overall

Overall, the PlainCards did exactly what I wanted them to do and I'll certainly be using more of them to create class materials. After I finish the current batch of number system cards, I plan on going back and re-doing the Binary Magic Trick cards so they can be printed directly onto PlainCards.

Other Reviews

Here are a couple other reviews for PlainCards, written by people using them to make custom cards for their games. They provide some useful tips on how to carefully remove the cards from the cardstock after printing.

• PlainCards FTW!
• Making Mordheim Campaign Cards with PlainCards

Getting "Computing in the Core"

I've typically avoided spending much time on trying to convince school board (or whomever) that they should do more to include Computer Science & Engineering & Programming in the K-12 curriculum. This is not because I feel this is unimportant (double-negative = yes, I think it's important), but rather that I'd rather not get mired in the politics at this point. In any case there are lots of competent people already working on this (uphill) battle.

I've also felt that I can do my part by creating and publishing various assignments, projects and presentations so that other instructors can make use of them. (I've been doing OK on the 'creating' part, but I have a large backlog of material I need to get around to 'publishing').

Getting back to the 'lots of competent people already working on this' topic, I just saw the announcement for Computing in the Core (CinC) which touts itself as a:

...non-partisan advocacy coalition of [blah, blah, blahs] that strive to elevate computer science education to a core academic subject in K-12 education...

And it made me go 'yea!'

Even if they focus only on 9th-12th grade (which I hope they don't), their success would still makes a great start since eventually the requirements will trickle down to the lower grades. I strongly believe that we should be starting earlier with CS education and that many of the problems we encounter are due to the late start, but that's another topic for another day.

I was reminded of the importance of getting CS into the core curriculum when I was talking with a friend the other day:

This friend has a daughter who attends a middle-school with an after-school robotics program. She was interested in this class (and had done some robotics in the past) but none of here friends were going to be taking it. In the end, she chose not to sign up for the program.

If this had been a "6th period robotics" class that everyone had to take, this would not have happened. It's difficult to be the only one of your peers interested in something like this. Who knows, maybe her friends would have enjoyed it as well.

But to finish up on a positive note. Yea for CinC! I hope that they are wildly successful.

Computer Class - Week #1

[So, this past week my Computer Class finally started. We purposefully delayed the start until the school year was well underway so that the students didn't have everything starting at the same time. This class is sortof a continuation of what I taught last spring, and sortof a new class since we'll be taking things a different direction.

Last spring, I covered basic pre-programming skills: number systems + logic and data representation. Later we went into electronics since that meshed well with what was being taught in the students' regular class.

This year I'll be doing (roughly) the following:

• (Review) Pre-programming skills: number systems and logic
• How computers work and computer architecture
• Computer programming (embedded systems like GBA and Arduino, then HTML+JavaScript)

The rest of this post is a rough outline of what I covered in the first class.]

(1) Welcome - Introductions and getting settled.

This was a simple intro and an overview of what the goals are for the class. These goals are:

• Get everyone to understand how computers work
• Get everyone to understand how to write a basic program

I also emphasized that the class will be working together to learn these things. We're not going to zip along and leave people behind, so it's in everyone's best interest to collaborate and help each other out.

My goal is to make all of this seem easy. Your goal is to work together and let me know if anything doesn't make sense.

(2) Roadmap - What we'll be covering in this class.

As a roadmap for the class, I drew (something like) the following on the whiteboard:

	Java App	C# App	HTML/JavaScript
C/C++ App	JVM	CLR	Browser
Operating System (Windows, Mac, Linux)
Kernel, device drivers
~~~~~~~~~~~~~~~~~~~~
CPU, Memory, I/O Devices...
Functional units
Logic gates
Transistors
Electricity

Everything above the squiggly-line is software and everything below it is hardware.

Most desktop applications (like Microsoft Office or Adobe Photoshop) that you buy today fall into the "C/C++ App" bucket in the above diagram (although there are many other languages that can be used as well). You can also find a lot of applications written in Java or C# as well, and many websites make use of JavaScript in addition to basic HTML.

Computer classes will typically spend all their time in one of the upper "programming language" boxes: C, C++, Java, C#, JavaScript or whichever language the class is built around. There's nothing particularly wrong with that - it's perfectly valid to choose a language and focus on the parts of programming that are "above" this diagram (like data structures and algorithms).

But notice how many layers there are between the programs you write and the underlying hardware. You have at least the OS and you might also have one or more virtual machines (like the Java Virtual Machine - JVM) or an application (like your web browser).  Rarely do programming classes attempt to describe what it going on in these lower layers, and rarer still are those that attempt to describe what's going on in the hardware layers.

But this class is different. In this class we will:

• Start from the bottom and work our way up (for the most part)
• Explore embedded systems (like the GBA, Nintendo DS and Arduino) so that we have fewer layers between the software we write and the hardware we use.

This will help us to actually answer the question: "How do computers work?"

We'll still do some work at these upper layers as well. Once we'll built the foundation, we'll start covering higher level languages and discuss more advanced programming concepts.

(3) So, How do computers work?

I asked the class, does anyone know? How would you describe it to a friend who was curious to know how they worked?

The answers to this question typically fall into one of three categories:

• Magic gnomes
• CPU + Memory + "other stuff"
• '0's and '1's

What's interesting about these answers is that none of them really tell you anything useful about how a computer works.

Compare this to common answers for "how does a car work?" and you can see the difference. Yes, some people will simply say "I don't know" or have stop at an "engine + wheels" description, but a large number of people will be able to talk about "gasoline + pistons + tiny explosions + crankshaft to make rotary motion + wheels". It's not perfect, but there's enough information there to understand why you need put gasoline in a car and change your oil regularly.

Going back to the computer descriptions above, and you'll see that they are (at best) the "engine + wheels" variety. The last 2 (technically correct) descriptions are really not much better than the "magic gnomes" description - none of them make you feel like you understand what's going on.

This is why we'll be focusing (at least at the beginning) on "how computers work" rather than "how to use computers" or "how to program computers".

(4) Binary (review)

[This was a review from material covered at the end of last year, so we went pretty quickly over this.]

I took out a bunch of counters - I use glass counter beads because I like the feel - and dumped a bunch on the table in the front of the class.  How many glass beads do I have?

I forget the exact number, but it was something like 25. So I write '25' on the board.

What are some other ways of recoding this number?

• Tally marks: using vertical lines or 正 (in China, Japan and Korea)
• Roman numerals: XXV
• Chinese/Japanese characters: 二五 or 二十五
• Arabic (middle-eastern) numerals: ٢٥
• Scientific notation: 2.5e1 or 2.5 x 10¹.

What are the advantages/disadvantages of each?

• Tally marks: Good for counting, keeping score in a game (easy to add 1). Bad for numbers greater than ~50. No way to represent 0.
• Roman numerals: Better than tally marks for numbers greater than 20. Still not good for numbers larger than ~10,000.
• Scientific notation: Useful for very large and very small numbers.
• Chinese/Japanese/Arabic: Note that the actual symbols don't matter, they're all valid for representing numbers.

The number system we commonly use is a "positional number system" called decimal or base-10. Key features of our number system:

• Uses 10 distinct symbols, including a symbol to represent zero.
• Positional: Symbols are arranged in positions based on powers of 10: ones, tens, hundreds, ...
• Each symbol changes meaning based on its position. '3' in the ones position means 3, but in the tens position is means 30.

Why ten? We could have used any other number. In fact, some cultures have used 12 instead of 10 because 12 is 'more interesting' (evenly divisible by 2,3,4,6, whereas 10 is evenly divisible by only 2,5). We still have remnants of 12 in our culture (hours on a clock, dozen eggs, ...).

What about base-8 (for octal). That would have 8 symbols: 0,1,2,3,4,5,6,7.  Each position would be based on 8: ones, eights, sixty-fours (8x8), ...

How would we represent this number of counters (remember we had 25) in octal? 3 groups of 8 + 1 left over = 3 in the 'eights' position and 1 in the 'ones' position = 31.

What about base-2 (for binary). That would have 2 symbols: 0,1. Each position would be based on 2: ones, twos, fours (2x2), eights (2x2x2), sixteens (2x2x2x2), ...

We were running out of time, so we didn't have a lot of time to practice, but I gave each student a handful of counters and they each practiced counting in decimal and octal and binary. This was review from last year and most remembered how the process worked.

Key takeaways:

• The positional number system was a key cultural advance. Requires a symbol for zero to work.
• The choice of 10 was arbitrary - any number base could have been used.
• Binary uses only 2 symbols 0,1, but it can represent any number that you can in decimal. It just requires more digits.
• Computers do, in fact, use binary for everything. How this works will be covered later.

Ah, well. Out of time.... This is where we'll pick up next week as we do a bit more review of number systems...

Hiring 10,000 new STEM teachers

So, the White House announced today their goal of recruiting 10,000 new STEM (Science, Technology, Engineering & Math) teachers over the next two years, as a first step in recruiting 100,000 new STEM teachers over the next decade:

President Obama Announces Goal of Recruiting 10,000 STEM Teachers Over the Next Two Years

This follows the announcement last week of the Change the Equation (CTEq) program, which describes itself as a "CEO-led initiative to solve America’s innovation problem" and is focused on getting corporations to help fill the gaping holes in our K-12 STEM education. CTEq sounds rather interesting, with projects like Intel Math and FIRST Robotics, but it's also kinda disappointing that we have to rely so heavily on these external programs to fix our broken education system.

These announcements are all good news, but I don't see this helping out Computer Science education all that much.

I noted that, while "launch[ing] robotics competitions" sounded cool enough to get a mention in the White House blog's announcement for CTEq, not once did any of these White House announcements mention anything about computers or programming. It's always "math" and "science", where these terms retain their traditional meaning without expanding them to include the new sciences.

"Math & Science. Hey! We already have math and science programs in our schools. We just need more of it, right? Let's hire more teachers. We just need to keep doing what we have always been doing, only more so!"

These initiatives are a nice start, but it would be great if they did something like explicitly include computer science in what they mean by "science". The White House could do this and people would actually listen. As it is now, schools are tied to traditional definitions for math and science and will continue teaching to whatever graduation metric they have in place.

So how many K-8 STEM teachers do you think will be hired?  Something tells me that most (if not all) of this hiring will be at the high school level where, in my opinion, you've already missed the opportunity to get young students really excited about math, science and programming.

Starting the new school year...

The new school year has begun and I will soon be starting my computer class at a local (Seattle-area) Montessori school.  Since my class is extra-curricular, I delay the start a bit so that the students can settle into their normal routine before the new class begins. The planned start date is the first week of October.

The class is primarily 6th-8th graders. I focus on this age group (upper elementary/middle school) because I'm trying to catch the students before they learn (from where?! grrr...) things like "computers are difficult to understand" and "programming is hard".

I'll be posting each week about the topics covered and I'll be including the materials that I create/use.

The first 6 or so weeks will mostly be a review of what we covered during the 16 weeks of classes last year:

• Number systems (binary, hexadecimal)
• Boolean Logic (and, or, xor, not)
• Data encoding (ASCII, hex editors)
• Electronics (electricity, LEDs, resistors + using solderless breadboards)
• + some other stuff I can't recall at the moment...

And throughout this school year, I'll be covering:

• Electronics (more LEDs with Arduino microcontrollers)
• Transistors (and how to build basic logic gates from them)
• Web pages (HTML5 + CSS + canvas)
• Programming (Arduino, GameBoy/Nintendo DS)

and whatever else comes to mind that matches the students' interests. I'll probably also spend a day talking about ActionReplay codes and hacking DS games, but we'll see how much time there is for that.

The goal of this class is to teach the fundamentals of computers and programming so that the students actually understand what is going on under-the-covers.  I could skip all the details and just focus on the programming bits, but that's not nearly as interesting (for me nor the students).

How the Internet Works - Part III - Routing Traffic

[This is the third in a 4-part post that describes an activity to demonstrate how the internet works. This part describes how the internet routes traffic using IP addresses.]

Some notes on presentation:

This document presents the activity as a rough script with "ACTION" breakouts when you need to perform some task. In this activity, you will be presenting information and directing the students as they act out the various parts of the internet.

You shouldn't just read from this script verbatim (since that will be rather dull), but you will probably want to have this printed out with you while you're presenting. Use a highlighter and mark key points so that you can find them easily while presenting.

Feel free to include additional information if you feel like it and accept questions and ad lib to follow the class interest. Throughout the script, there are a number of questions for the students that can be used to make the presentation more interactive.

The files for this activity (internet packets and labels) can be downloaded from www.cse4k12.org/internet/how-internet-works.html.

Internet

The phone system (even in the very simplified form as described in the previous post), works reasonably well. But the internet differs from a phone network in a few key ways:

1. Packet-based communication. On the internet, data is bundled into self-contained "packets" that are routed through the internet.
2. Automatic address lookup. Every internet-connected device has an IP address, which is similar to a telephone number in that it uniquely identifies a computer on the internet. However, you don't need to know this IP address for the website you're visiting. To visit a website, you can simply type the domain name (like "http://www.google.com") and the correct IP address will be automatically looked up.

We'll look at these two differences in turn — starting with a discussion of packets. Address lookup will be covered in Part IV.

But first, a note on IP Addresses

Currently, an IP ("Internet Protocol") address consists of four 8-bit numbers (ranging from 0 to 255) written in decimal and separated by dots, for example: 74.125.19.104. This 32-bit (4 x 8-bit) number is known as an IPv4 address and it can provide unique IDs for up to 2³² (about 4 billion) computers.

Because the number of devices connected to the internet will soon exceed the number of available addresses in IPv4, a new standard called IPv6 is being introduced. An IPv6 address is 128-bits long and is written as a set of eight 16-bit hexadecimal numbers separated by colons (e.g., 2001:A3D2:32C9:1F37:0000:0000:0000:0000). These new IPv6 addresses can support up to 3.4 x 10³⁸ unique devices.

In this activity, we'll be using IPv4 addresses exclusively because they are easier to work with, but the same concepts presented here also apply to IPv6 addresses.

Packet-based communication

Unlike the traditional landline phone system, the internet is packet based. This means that computers on the internet communicate with each other by sending packets of information back and forth. Think of it as sending tiny electronic letters to each other with the internet acting as the postal service. Large "letters" are not allowed — they must be broken into smaller pieces, sent separately and then reassembled on the receiving end.

As an example, imagine writing a long letter (email) to grandma. You'd have to cut it into (say) 3 pieces, put each piece in a separate envelope (packet), number them (1,2,3), and mail them separately. When your grandmother receives the letter she would wait for all 3 pieces (packets), tape them together and then read the letter. Note that the pieces (packets) might not be received in the correct 1,2,3 order, so she may need to sort them before taping them together.

The advantage of the packet-based system is that doesn't require a dedicated connection (remember the rope in the phone system example). This allows computers to support a very large number of simultaneous connections — receive a packet, respond to it, go to the next packet. Imagine how inefficient it would be if you needed to have a dedicated connection to access every website you wanted to visit. And popular websites like Google or Wikipedia would only be able to support a relatively small number of simultaneous users. In addition, most of the connection capacity would be wasted while the computers waited for the next command/communication. And once people got a connection, they would probably try to hold on to it for as long as possible.

So, how does this work? Basically the same was as the phone network except that we use "routers" instead of "switches". A "switch" (like we saw in the phone network), takes an incoming connection and connects it to its destination. It also needs to maintain this connection for the duration of the call. A "router" accepts a packet of information and then sends it on its way — completely forgetting about it after sending it off. This allows the router to support a much larger number of users than it could otherwise handle.

ACTION: Collect the switching tables from nodes 1-6 and replace them with routing tables. The switching tables can be set aside since they are no longer needed.

Skipping over the issue (for the time being) of how we lookup an IP address from a domain name like "www.google.com", let's follow an internet connection like we did with a phone connection.

We'll start with a very small "internet". In this network, we have the basic elements that we find on the internet:

• Two websites: in this case, google.com and wikipedia.org. In this network, Google is represented by 2 nodes (#5 and #9). In general, large websites on the internet will be distributed across multiple machines.
• Two homes: you and your neighbor
• An ISP: this is your "Internet Service Provider". That's the company that you pay to keep you connected to the internet.
• Three routers: "1", "2" and "3"

ACTION: Relabel the nodes on the graph as you mention them:

4 : ISP — IP address = 65.32.236.122
5 : google.com — IP address = 74.125.45.100
6 : wikipedia.org — IP address = 208.80.152.2
7 : you — IP address = 65.32.200.101
8 : neighbor — IP address = 65.32.200.102
9 : www.google.com — IP address = 74.125.19.104

Note that nodes 1, 2 and 3 don't have labels. These are the “routers”. No need for a label, but they should be referred to as routers during this part of the activity.

ACTION: Assign new students to the graph nodes, or re-assign the students to play different roles. Nodes 6 (wikipedia.org) and 8 (neighbor) aren't used for this part of the activity, so you will only need 7 students for the nodes on the graph + 1 additional student to act as a "runner". This runner will propagate the packets through the network.

As mentioned earlier, we'll start by pretending that we already know the IP address of the website we want to visit. So we already know (somehow) that "www.google.com" has an IP address of "74.125.19.104".

Once we have the IP address of a website, we can send a request to it. These requests are similar to letters in that they have a "TO" and a "FROM" and some content that is being sent.

Here is a sample packet that we're going to send to Google:

• The "FROM" is your IP address.
• The "TO" is the IP address of Google.
• The default content is a generic "Hey, show me your website" request. This is what we commonly refer to as "visiting" a website.

When you want to visit a website, you send your request out so that it gets delivered to the correct website. Since your ISP is your connection to the internet, you sent your request first to your ISP which sends it along to its destination.

ACTION: Have the student at node 7 ("you") give the packet 1-1 to the "runner". The runner should then carry the packet, starting at “you”, to the ISP.

Packet: (1-1)
From: 65.32.200.101 (you)
To: 74.125.19.104 (www.google.com)
Message: Please show me website

The routers operate in much the same way at the phone switches do - except that they use IP addresses instead of telephone numbers to decide what to do.

ACTION: Follow this packet through the various routers, up to node #9: www.google.com.

When Google gets this request (packet), it sends back a response. This response is also a packet, but this time FROM google TO you. Since you didn't ask for anything specific, the contents of the packet are the main search page (the default for this website).

ACTION: Have the runner give the 1-1 packet to the "www.google.com" student at node #9. The website will now process the request and create a new packet to send back. Introduce packet 1-2 at node #9 and have the runner route it back to the user.

Packet: (1-2)
From: 74.125.19.104 (www.google.com)
To: 65.32.200.101 (you)
Message: Website contents (main search page with empty search box)

When you get the response packet, your web browser displays it on your computer screen. You can now interact with the webpage and enter a search term, like "donut", and send another request to Google.

ACTION: Have "you" give packet 1-3 to the runner and send it off.

Packet: (1-3)
From: 65.32.200.101 (you)
To: 74.125.19.104 (www.google.com)
Message: Search for "donut"

But this time, let's see what happens when the network is damaged. Let's pretend that link "Ii" is no longer working.

ACTION: Walk over to the "Ii" link and stand there as a reminder that this link is no longer functioning. Alternately, you can have a student stand there to block network traffic.

As with the phone example, the network routes around the damaged parts. Note that with the packet network, we didn't lose the connection and need to re-start it. The packet was already on its way and simply continued around the damage to reach the destination.

When "www.google.com" finally gets the request, it runs the requested search and creates a new packet with the results to send back.

ACTION: Have "www.google.com" give packet 1-4 to the runner to send back.

Packet: (1-4)
From: 74.125.19.104 (www.google.com)
To: 65.32.200.101 (you)
Message: Search results

If we have more damage to the network...

ACTION: Walk over to link "Dd" to take it out of commission. Make sure the keep "Ii" blocked as well.

...the network will route the packet around the new damage as well.

And eventually the search results come back to you.

So, a question: How long does all this take to run end-to-end? Well, how long do you wait for a webpage to return results before you start to get annoyed that the "internet is slow"? In general, anything that takes longer than 1 second is irritatingly slow.

Setup for part IV

So now we have our search results for "donut". Let's say there's a wikipedia link (http://en.wikipedia.org/wiki/Doughnuts) in the results. What happens when we click on that? And how do we find the wikipedia.org website if we don't know its IP address?

[to be continued in Part IV]

Boy Toys & Girl Toys

Saturday Morning Breakfast Cereal's take on "Why are there so few girl engineers?"