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."

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.

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...

Updated bitmap (binary/hex) worksheets

I've updated the bitmap (binary/hexadecimal conversion) worksheets. There is now an instruction sheet that contains 5 bitmap grids for students to create their own bitmaps plus 2 grids for them to convert from hexadecimal into a bitmap.

There are also blank worksheets (grids only - no instructions) for 8x8 and 16x16 bitmaps.

Crossbin puzzle #2

Binary magic trick

I've added documents for the binary magic trick activity that I use after introducing the students to binary numbers.

This includes the cards (to cut out) and a set of instructions on how to perform the trick.

Crossbin puzzles

I've started adding crossbin puzzles to cse4k12.org. Crossbin puzzles are similar to crossword puzzles except that the clues are hexadecimal numbers and the answers are binary numbers.

When the puzzle is complete, the grid is filled with '0's and '1's. Then all the '1's can be filled in with black (and, optionally, '0's erased to white) to create a simple black and white image.



These are useful as a simple exercise in a computer science class after the students have been introduced to binary and hexadecimal numbers (and how to convert between them).

Basic instructions and a simple example are given at cse4k12.org:

http://www.cse4k12.org/crossbin/index.html