Computer Science & Engineering for K-12

2011-10-14T17:41:00.000-07:00

Google Code-In is an open source development contest for 13-17 year old students. Similar to Google's Summer of Code, but targeted at younger programmers.

If you know any High School students who are interested in programming or curious to get involved in open-source projects, you might want to point them to the announcement on Google's Open Source blog.

The participating projects haven't been announced yet, but some of the tasks will include: coding, documenting, researching, training, translating and user interface design.

Timeline:
November 9: Announce participating open-source projects
November 21: Google Code-In begins
January 16: All tasks must be complete

[Repost from: Google+]

How to explain programming to young children

2011-09-13T17:43:00.000-07:00

A recent article on Slashdot had an interesting comment titled Here's my way of explaining "programming" authored by "Sun" (or Shachar) [minor typos corrected]:

Caveat - I have never actually tried it, and I developed it for adults. I still think it might work with 2nd graders (probably too complex).

Ask for a volunteer. Write a bunch of numbers on the board, and tell the volunteer to sort them.

Explain that this is not programming.

Now, cover the volunteer's eyes, write some more numbers on the board, and tell him to tell you to sort them. Allow asking "what is the first number" and such.

Explain that this is, also, not programming.

Now, tell the volunteer to tell you how to sort the numbers before they are written on the board. Explain that once the numbers are written on the board, you will not hear any comment from him. Write the instructions down on the board. When they are done, write down numbers and carry the instructions out. Try to pick numbers that won't work with their instructions. Allow the class to fix the instructions, but any time they do, restart the whole thing.

This is programming.

Shachar

While I agree that it seems a bit involved for a 2nd grade classroom (where making a PB&J sandwich might be more appropriate), this seems like a good approach for middle school and up.

Technically, this is demonstrating how to create an algorithm, but creating an algorithm to solve a task is a big part of programming. Once the algorithm is done, the programmer must then implement it efficiently in a programming language.

A variant of this would be to pair up the students and give each group a set of cards to sort - cards should be a bit easier for the blindfolded student to work with. After each group has created their sorting algorithm, the algorithms can be shared with the class and you can run through examples to improve them collaboratively.

K-8 curriculum overview for computer skills

2011-09-11T11:47:00.000-07:00

From the If-I-Ran-The-World Dept...

So here is a rough outline of my ideal computer skills curriculum for K-8, with a focus on preparing students for programming in middle school. I'm assuming roughly 1.5-2 hours per week and ~32 weeks in a school year. For K-5, the items are more "computer literacy" than "computer science", but that changes in middle school (grades 6-8) where the focus switches to teaching how computers work and how to program.

Note that, when assigning a lesson to a grade/age, I tried to select a grade where the vast majority of students would be ready and able to understand the concepts. Thus, the grade-level specified is meant to be appropriate for a classroom setting.

When homeschooling or teaching an individual, you may find that the student is ready for this material at an earlier age (often 2-3 years earlier). The best learning environments are those that can adapt to the students' interests, so feel free to move things earlier as needed. But note that this request to move the lesson earlier needs to come from the student.

For classrooms, if you prefer to think in terms of Introduce/Reinforce/Master, then the grades listed here are a cross between Introduce and Reinforce.

I'm using US school grades so add 6 to get an approximate age (1st grade is roughly 7 yrs old).

Elementary School

The key lessons here are to learn how to use computers effectively and to be exposed to the underlying math/logic principles that will be used in middle school.

At the end of 5th grade, the students should have the following skills:

Know how to interact with a computer using mouse and keyboard
Be able to save/load files from an app, and to organize their files in directories
Understand non-decimal number systems, specifically binary numbers.
Understand basic boolean logic, specifically AND, OR, XOR and NOT
Have a general understanding of how things are stored on a computer
Be able to use a web browser and perform effective internet research

K - 2nd grade

During these years, the student should develop basic computer interaction skills.

Mouse: moving, pointing, clicking, selecting, double-clicking, dragging, ...
Keyboard: basic typing skills,
Parts: name the various parts of a computer

3rd grade

Focus on using computers as tools.

Productivity apps: word processor, spreadsheet
Keyboard shortcuts for common operations: (cut/copy/paste/undo, find/search)
Understand file types: txt, doc, gif, png, mp3, avi, ...
Understand where files are stored: locally, on file server, in cloud
Maintaining an account: passwords, logging in/out, simple security
Web browser - using and navigating

4th grade

More work with using computers as tools, but start building the foundation for
computer lessons in later years.

Email - etiquette, subject lines, spam & chain-mail, attachments, privacy, To/Cc/Bcc
How to perform internet research. How to evaluate a website's reputable.
Ethics: copyright, fair use and giving appropriate credit
Web browser - uploading/downloading/sharing files
Security: viruses, worms, trojan horses
Security: passwords, privacy
Number systems: roman numerals, tally marks, zero
Number systems: positional number systems (decimal, octal, binary, hexadecimal)
Curriculum-Link (Math): number systems
Curriculum-Link (Math): plotting x-y values

5th grade

Less focus on how to use computers, and more focus on what's going on behind the
scenes.

How data is encoded on computers (text/char-sets/unicode, colors/rgb/hsl, digitizing analog/digital, audio, video, ...)
Compression/decompression of computer files (zip)
Security: encryption
Difference between text editors and word processors.
Privacy: browser history, cookies, caches
Privacy: what happens when personal info (or password) is comprimised
HTML/CSS: create a set of linked webpages (on local machine) using a text editor.
Learn how to structure a project with many (HTML/CSS) files.
Boolean logic: AND, OR, XOR, NOT
Curriculum-Link (Science): colors and light, additive/subtractive color models
Curriculum-Link (Math): prime numbers (encryption)

Middle School

During middle school, the students should be introduced to programming and learn how computers work. Optionally, they should learn about electronics and robotics (although these lessons tend to require extra equipment, so it's not always possible to include them).

At the end of 8th grade, students should:

Understand why computers use binary
Have been exposed to the "big ideas" that de-mystify how computers work:

How computers perform computation
How computers remember things
How computers perform actions in sequence

Know how to write simple programs in at least 2 different programming languages
Be able to construct a small electronic project on a breadboard

6th grade

In 6th grade, the students should be introduced to all the basic programming concepts: variables, flow control, functions, arrays, and so on.

Visual programming: Scratch or variant - variables, flow control
Choose two languages from: [Python, Javascript, Processing] - functions, arrays
Interact with the computer using the shell/cmd-prompt
Wildcards and simple regular expressions
Internet: How the internet works (to route traffic, overview of DNS)
Privacy: where your internet 'footsteps' are logged (routers, ISPs)
Security: botnets and why you should apply security patches
Algorithms: searching, sorting
Curriculum-Link (Science): Write spreadsheet functions for data analysis

7th grade

Continue building programming skills by expanding into more languages. Introduce basic electronics and explain how computers work.

Choose remaining language from: [Python, Javascript, Processing]
Electricity: very simplified - focus on Voltage - just enough to understand transistors
Transistors: what they are and how they work (CMOS)
Logic gates: built from transistors (NOT, NAND, NOR)
How computers calculate (addition using logic gates)
How computers remember (memory latches using logic gates)
Negative numbers in binary (2's complement)
Basic digital electronics with Arduino (breadboards, LEDs, servos, ...)
Optional: Robotics (if you have the resources)
Curriculum-Link (Science): Electricity (done properly with V=IR, ...)

8th grade

More advanced programming and managing larger projects.

Java (using Greenfoot or BlueJ)
Do at least one "large" programming project
Project management: divide large task in to smaller subtasks
How memory is allocated (stacks, heaps, fragmentation)
How functions are called (call stack, recursion)
Data encapsulation, classes and inheritance
Regular expressions: grouping and matching, greedy vs. non-greedy
Floating-point numbers: representation and implication for scientific calculations
More data structures and algorithms: stacks, linked lists, hash-tables, trees, graphs, ...
Curriculum-Link (Math): Trigonometry
Curriculum-Link (Science): Using regexps to process data files
Curriculum-Link (Science): Gravity, acceleration (for jumping in a game)

A Computer Scientist's Lament

2011-06-05T09:56:00.000-07:00

Here are a couple of recent articles on learning CS that I found interesting because, rather than focusing on the classroom setting or enrollment numbers, they talked about the challenges facing a motivated self-study student.

In Andrew Binstock's "Lax Language Tutorials", he discusses the current state of programming language tutorials. In summary, most books being published appear to be confused between an introductory tutorial and a treatise on every feature of the language. This leads to absurdly large volumes that may be a bargain in terms of dollars-per-page, but are overwhelming for anyone who just wants to get started and learn the basics.

To paraphrase Messrs. Twain and Pascal:

"I didn't have time to write a concise programming language tutorial, so I wrote this bloated monstrosity instead."

James Somers' article in The Atlantic, "How I Failed, Failed, and Finally Succeeded at Learning How to Code", describes the issues he had with these language tutorials:

For a while I thought I didn't have the right kind of brain for programming. Maybe I needed to be better at math. Maybe I needed to be smarter.

But it turns out that the people trying to teach me were just doing a bad job. Those books that dragged me through a series of structured principles were just bad books. I should have ignored them. I should have just played.

And then continues with an indictment of the AP's CS curriculum:

Nobody misses that fact more egregiously than the American College Board, the folks responsible for setting the AP Computer Science high school curriculum. The AP curriculum ought to be a model for how to teach people to program. Instead it's an example of how something intrinsically amusing can be made into a lifeless slog.

He also makes reference to Paul Lockhart's A Mathematician's Lament (which comments on how uninspiring most math instruction has become) and draws comparisons between math and CS instruction.

Somers persevered with his attempts at programming and found inspiration in the programming website Project Euler, but it's easy to imagine that many of these motivated students simply give up, thinking that programming is too hard for them.

Minibloq ≈ Visual Programming + Arduino

2011-05-22T07:40:00.000-07:00

Minibloq is a Kickstarter project to create a freely-available visual programming environment for the Arduino - something like Scratch for Arduino programming.

The good news is that they've already reached their funding goal so they can go ahead with this project. I'm looking forward to playing with this later this year.

Arduinos in Museums

2011-04-13T13:30:00.000-07:00

New York Times: An Interactive Exhibit for About $30

Over the past few years, museums have switched from expensive general-purpose computers to cheap (~$30) Arduino microcontrollers to run the exhibits:

“Hackers and geeks have been doing this for years, building all sorts of cool robots and interactive experiences, but now it’s become so simple and inexpensive that artists and designers have adopted it, too.”

...and students.

“The two most important introductions for art in the past 20 years have been the Arduino and Processing,” explained Paola Antonelli, senior curator in the Department of Architecture and Design at the Museum of Modern Art.

Sounds like an endorsement of Processing for Intro to CS classes.

How to publish your teaching materials

2011-04-03T16:19:00.000-07:00

During this past SIGCSE, I was involved in a couple of discussions about how one finds CS teaching materials on the web. At one point, the conversation turned to how one goes about publishing these materials.

The background for this discussion was base-sixteen.org - a website that I'm working on to catalog (and organize, somewhat) the CS teaching resources that are available on the internet. The question was whether or not this should be a "catalog" (with links to resources that were hosted elsewhere) or a "repository" (which hosts the material on the same site).

There are pros and cons to each approach:

Because a repository keeps a local copy, the resource will still be available even if the original site goes away. However, this local copy will be out-of-date if the original site is updated (unless the repository is updated as well).
A catalog has the opposite problem. It will always point to the most recent version, but if the site goes away then the resource will no longer be available (unless it was cached elsewhere).

There are other issues as well, such as whether or not a repository has the legal right to host some material, but the main concern in this discussion was for dealing with materials that are here-today, gone-tomorrow.

This is a particular problem for things like syllabuses and lesson plans because these materials are often hosted on a university (or college, or high school) website which is managed by someone other than the instructor creating the materials. When the new school year rolls along, the webmaster might decide to clean out all the old "outdated" files. Even if the teacher is in control of their part of the website, when they move on or switch schools the materials will go away with the person (hopefully to reappear somewhere else, but the link is still dead).

There are a number of different approaches for dealing with this, but I was interested primarily in the "webmaster deleted my files" problem because this is something that can usually be avoided by simply publishing the documents on the web yourself.

Of course, creating a website to host a few documents is way too much money and work, but there are far easier (and free!) ways to be in control of your published documents. Companies like DropBox and SpiderOak allow you to host and share documents in the cloud, or you could publish directly from web-document editors like Google Docs.

I created a small document that summarizes some of the ways you can publish your documents on the web:

https://docs.google.com/document/pub?id=1QRBBrU9ac8A0SSkhx0HKTtvj21Ja-ynMetY2rj_0hcQ
(Isn't that a great URL? Well, that's one of the downsides of having someone else host your material ^_^)

It's published as a Google Doc (rather than in this blog post) so that I can edit and update it as I discover new services. If you have a preferred way of publishing that I don't mention, please let me know so that I can update the document.

"Thankfully, for most people, that's a pretty low bar."

2011-04-01T22:11:00.000-07:00

In my opinion, one of the best April Fool's Day pranks this year was Think Geek's PLAYMOBIL™ Apple Store Playset. I don't what it says about me that I would probably buy one if it was actually an item for sale.

But the reason why I'm posting this here is because they also made a fake Apple announcement video for this product. It's 2min 22sec long, but the money quote in this video comes around 1:29:

"Frankly, if something exceeds your ability to understand how it works, it sort of becomes magical. Thankfully, for most people, that's a pretty low bar."

Matthew Chwat — Graphic Design Specialist

Now, this is funny in the video because they're being over-the-top elitist, but the quote also has a "It's funny because it's true" quality to it.

In particular, it reminded me of Arthur C. Clarke's 3rd law, something that I often quote when discussing how woefully inadequate our education system is at teaching students about the basics of how technology works:

"Any sufficiently advanced technology is indistinguishable from magic."

Beyond simply teaching students how to program, we also need to be showing them how computers work at a basic level. I do this in my class by showing them how transistors work, how logic gates can be combined to add numbers, and I also have the students program and build simple electronics projects, often with a microcontroller like an Arduino.

I don't expect these students to become computer engineers, but I do want them to have a general understanding of what's going on inside the "magical" boxes that surround them. This is no different that what we do for other disciplines like Chemistry — we teach the Bohr model of the atom and the periodic table of the elements even though only a very small percentage of students will actually become chemists and need to know this information. We do this because we feel it's good for students to have a basic understanding of the world around us, even if they don't go on and pursue the subject in more depth.

Well, the same reasoning applies to computer technology as well. Especially as we're seeing more and more of it in our lives.

Using CCG cards to teach computer science

2011-03-18T20:09:00.000-07:00

I published a new activity for teaching computer science searching/sorting concepts. It's designed for middle school students, although there's no reason why it wouldn't work for upper elementary or high school students.

Using CCG cards to teach searching/sorting

It introduces algorithms for searching and sorting by using Collectible Card Game (CCG) cards – like Magic the Gathering or Pokemon cards – as objects for the students to search/sort.

An advantage of using these cards is that they are easy to hold and don't take a lot of room, so each student can easily manage 10 cards on a standard school desk. And the activity scales to more or less cards, or students can work in groups if needed. The cards are also cheap (or free) if you're willing to look around, but you can always just go to the store and buy some (convenient if you're traveling and left your teaching props at home).

I've run this activity in a number of classes in different schools and it's a great way to demonstrate how these algorithms work.

Google engineers visit local schools to promote CS

2011-03-18T12:28:00.000-07:00

Official Google Blog: National Engineers Week 2011: Classroom visits inspire students to pursue CS

National Engineers Week outreach - Having engineers visit local schools

2011-03-18T12:26:00.000-07:00

Recent K-12 outreach where Google engineers go out and visit local schools and talk about computer science:

http://googleblog.blogspot.com/2011/03/national-engineers-week-2011-classroom.html

Yes, that's my byline on the blog post. It was a lot of fun doing these visits (although it required a lot of prep-work in advance to get things set up).

CS education is important for scientists

2011-02-17T11:51:00.000-08:00

Philip Wadler's recent blog post "Scientific programming does not compute" draws attention to a Nature article from last October : "...Error ...why scientific programming does not compute" (Nature 467, pp.775-777 - 14 October 2010)

This article has some wonderful examples of why CS education is important to students interested in pursuing a career in the sciences.

Researchers are spending more and more time writing computer software to model biological structures, simulate the early evolution of the Universe and analyze past climate data, among other topics.

and

As a general rule, researchers do not test or document their programs rigorously, and they rarely release their codes, making it almost impossible to reproduce and verify published results generated by scientific software, say computer scientists.

Although I imagine that computer scientists probably said that they rarely release their "code". Why is it so difficult for writers (and Hollywood) to understand that computer programming "code" is a mass noun (like "water"), and not a count noun (like "pumpkin"). I can only guess that people are confused by things like "secret codes" and think computer code is the same. Anyway, I digress...

So continuing with choice quotes from the article, a Toronto-based computer scientists named Greg Wilson conducted an online survey about the programming habits of scientists back in 2008. He received nearly 2000 responses and reported the following results:

45% said scientists spend more time today developing software than five years ago.

38% of scientists spend at least one fifth of their time developing software.

Only 47% of scientists have a good understanding of software testing.

Only 34% of scientists think that formal training in developing software is important..

Wilson also added:

"There are terrifying statistics showing that almost all of what scientists know about coding is self-taught," says Wilson. "They just don't know how bad they are."

Why does this matter? Well,. this lack of proper programming skills can lead to data being misinterpreted and incorrect results being published:

As a result, codes [grrr...] may be riddled with tiny errors that do not cause the program to break down, but may drastically change the scientific results that it spits out.

The article then provides a number of interesting real-world examples:

A structural biology group at a research center needed to retract 5 previously published papers when they found a bug in the program that analyzed their data.
A computational biologist wrote some code based on assumptions that were valid for his work, but another group re-used his code in a different scenario where these assumptions did not hold true.
The code used to analyze data from the Large Hadron Collider is so complex and convoluted that it is difficult for new researchers to come in and test or modify the code

What does the article suggest we do about this problem?

In the long tern, though, [software developer Nick] Barnes says that there needs to be a change in the way that science students are trained.

and

Science administrators also need to value programming skills more highly, says David Gavaghan, a computational biologist at the University of Oxford, UK.

In some sense, the article is calling for better software engineering skills (including documenting and testing) rather than raw programming skills. But the programming fundamentals need to come first for everyone.

The crisis in K-12 computer science education is really a crisis for all the sciences.

Comments for K-12 STEM education

2011-01-31T13:25:00.000-08:00

Today is the deadline for submitting comments to the NITRD request for information on strategies for meeting the goals set out in the recent PCAST report: "Designing a Digital Future: Federally Funded Research and Development in Networking and Information Technology" (Dec 2010).

The first 2 comment sections relate to particular industries (health case, energy, transportation, ...) or R&D, but the third section asks specifically about strategies for incorporating computer science into K-12 STEM education.

The rest of this post contains the comments that I submitted:

3. The PCAST report calls for fundamental changes in K-12 STEM education in the United States, including the incorporation of computer science (CS) as an essential component.

a. What CS concepts are important to effective elementary, secondary, and post-secondary curricula? Among these concepts, which are commonly found in curricula today? Which are missing?

Elementary: (3rd-5th)

Currently, elementary schools are likely to cover "logic grid" puzzles and syllogisms, but not much more. Ideally, they should include at least the following:

Number systems (specifically binary, octal and hexadecimal since these are the ones that matter for computer science)
Boolean logic (and, or, xor, not): boolean variables and expressions
Introduce the concept of simple variables (integer) here and relate to boolean values (x = 3 is either true or false)

Including a variety of different logic puzzles (Sudoku and similar) would also be beneficial.

In addition, elementary school should also cover the skills necessary to use a computer effectively and perform common tasks (word processing, web search, ...). This is necessary so that they are comfortable using computers when we introduce programming in later grades.

Middle School: (6th-8th)

In these grades, students should focus on understanding how computers work and learning how to write a basic program.

As part of "understanding how computers work", we need to demystify the operation of the computer. This is important because learning how to program doesn't give a complete picture of how computers operate. This section should include the following:

Basic file formats (show how text, graphics, music and video are stored on a computer; explain difference between bitmap and vector graphics, and text vs. rich-text formats)
How color is encoded (RGB encoding, compare with primary colors they were taught in elementary school)
How computers work (basic description of how computers perform logic and math operations)
Basic boolean algebra (DeMorgan's law, re-writing expressions)
Simple electronics (hardwire or programmatically control an LED)
Internet: What happens when a website is visited? How does the internet route traffic?

For "how to write a basic program":

Programming constructs: variables, control flow, functions, objects, ... (exact set varies depending on languages chosen)
Write simple programs (see below)
Explore and contrast various general-purpose vs. special-purpose languages
Using wildcards and regular expressions (in a programming language and in a shell/cmd prompt)

When having the student write simple programs, it is important that the core assignments are interesting and engaging. The best way to accomplish this is by having the project require significant creative input from the student. For example, creative writing for a text adventure or drawings for a 2D game. This approach gets the student to invest in the success of the project (since it's their story or artwork), so they are more motivated to learn how to make their characters work they way they want.

Note that rather than arguing about which programming language to teach, we should focus on introducing students to a number of different languages (at least 2 or 3). This is useful because each language has different strengths and weaknesses, and we don't want students to graduate thinking there is only one way to program. Frankly, I would expect the languages chosen to vary somewhat between school systems and the change over time.

In addition, in these grades it is also important to start teaching students about electronic privacy, security and information sharing. It makes sense to teach these subjects in the context of computer science and to give the students programming assignments that (directly or indirectly) explore these topics.

The goal should be for all 8th graders to graduate knowing that they (1) are capable of writing (simple) computer programs, and (2) have a basic understanding of how computers work.

High School: (9th-12th)

High school should introduce advanced programming topics (algorithms and data structures) just like high schools offer advanced chemistry and physics classes. Beyond 9th or 10th grade, these classes don't have to be required for all students, but they should be required for students interested in a science and technology track.

Overall

Overall, we should try to link CS projects to other subjects whenever it makes sense: We can motivate learning about trigonometry by showing how it is used in games to calculate distance and to detect (bounding sphere) collisions. We can talk about the math/physics behind gravity and acceleration when we want to have a character jump realistically on the screen. We can demonstrate the additive color properties of light and discuss prisms and rainbows when we introduce RGB color.

Once we have CS as a core subject, these links will be easier to make and will lead to a much richer learning environment for the students.

b. What do teachers need (including preparation and training, tools, and resources) to be able to deliver CS education effectively?

Training and ready-to-use classroom materials are key for all grade levels. Any materials that are created need to be supplemented with instructions showing how to use it properly in the classroom. Two types of instructors should be targetted here: teachers who know how to manage a class but are not very familiar with programming, and teachers who know how to program but are not familiar with teaching strategies and classroom management. These two groups are likely to make up the bulk of teachers during the first years when we introduce CS to the classroom.

There will also need to be programs offered for teachers to learn how to teach this material. Fortunately, most (if not all) school systems require regular teacher training for "clock hours". This is the perfect venue for reaching the teachers and bringing them up to speed with the material.

c. What factors are important in promoting student interest in CS?

I discussed some factors in the earlier sections, but the most important factor is simply that computer science needs to be included as part of the core K-12 curriculum.

An example which underscores the importance of this happened recently to a friend of mine. His daughter (age 12) had already taken a programming class or two and she was interested in participating in an after-school robotics class. However, even though she was interested, she decided not to sign up because none of her friends were planning to take the class and she didn't want to be "alone". Whenever I think about this, I wonder how many other students are missing out because of (even minimal) social pressures, and how many of her friends would have discovered that this was a subject that was interesting to them, if only they had been forced to try.

And remember, this was for someone lucky enough to have encouraging parents and teachers willing to organize this after-school class. Most students don't have those advantages.

I'm tempted to say that adding CS to the core is the only important factor and that it (almost) doesn't matter what we teach or how we teach it. Once we make CS a core requirement, everything else will (by necessity) follow. Of course, it's clearly better to teach it properly, but as long as we're willing to iterate and improve, even a less-than-perfect rollout will be of great benefit to the students.

Materials for teaching transistors and logic gates

2010-12-05T14:35:00.000-08:00

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

2010-11-27T11:33:00.000-08:00

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

2010-11-26T23:06:00.000-08:00

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

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

2010-11-13T23:27:00.000-08:00

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"

2010-11-10T15:00:00.000-08:00

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

2010-11-07T00:17:00.000-07:00

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

2010-11-02T13:53:00.000-07:00

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

2010-11-01T09:34:00.000-07:00

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
10³	10²	10¹	10⁰

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
8³	8²	8¹	8⁰

[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
10³	10²	10¹	10⁰

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
2⁵	2⁴	2³	2²	2¹	2⁰

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

2010-10-28T00:07:00.000-07:00

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:

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

2010-10-23T07:26:00.000-07:00

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.

Getting "Computing in the Core"

2010-10-17T09:28:00.000-07:00

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

2010-10-10T10:10:00.000-07:00

[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

2010-09-27T21:33:00.000-07:00

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

2010-09-08T14:40:00.000-07:00

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

2010-08-08T16:13:00.000-07:00

[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 (routing tables 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:

Packet-based communication. On the internet, data is bundled into self-contained "packets" that are routed through the internet.
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 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 "TO" is the IP address of Google.
The "FROM" is your IP address.
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 and it 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)
To: 74.125.19.104 (www.google.com)
From: 65.32.200.101 (you)
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.

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 and have the runner take it back to the user.

Packet: (1-2)
To: 65.32.200.101 (you)
From: 74.125.19.104 (www.google.com)
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)
To: 74.125.19.104 (www.google.com)
From: 65.32.200.101 (you)
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)
To: 65.32.200.101 (you)
From: 74.125.19.104 (www.google.com)
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

2010-05-16T10:38:00.000-07:00

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

How the Internet Works - Part II - The Phone System

2009-12-27T10:11:00.000-08:00

[This is the second in a 4-part post that describes an activity to demonstrate how the internet works. This part contains an introduction and a description of how the (landline) phone system works.]

Some notes on presentation:

This document presents the activity as a rough script. For 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 part of the activity (routing tables and labels) can be downloaded from www.cse4k12.org/internet/how-internet-works.html.

Introduction

What is the internet? Basically, the internet is just an interconnected collection (a "network") of computers throughout the world. The interesting part of the internet is how the computers are connected with each other. It's easy to connect a small number of computers to each other, but the internet consists of millions of computers.

In order to understand how the internet works (i.e., how these millions of computers interact with each other), it's useful to start with a networking system that you're already (somewhat) familiar with and then compare that system to the internet.

So, let start with a discussion of the phone system.

(Note, we're talking about traditional landline phones here. Cellular phones are different beasts and we don't cover them.)

Phone system

Let's say you want to call someone on the telephone. What do you do?

You somehow get their phone number and dial it. Then the phone system finds the target phone and makes it ring.

This raises 2 questions:

How do you know which number is associated with the person you want to call?
How does the phone system use the number to find the target phone for that person?

(#1) So, how do you know the phone number?

Well, you ask someone. Either the person you want to call (if they're around), or a mutual friend (if there are any). You can also try the phone book, but people might be unlisted or listed under a different name (like their parent's name).

In addition, when using a phone book that covers an entire city, multiple people might have the same name - what do you do then? You may only know one person named “John Smith”, but there may be a dozen people with the same name in a single city. The phone system uses phone numbers instead of names to avoid this problem.

So, once you get the phone number, you probably write it in your personal address book so that you don't forget it. This address book provides a mapping from “name” to “phone number” for you. Once you write a number in your address book, you don't have to ask around or search for that number again.

ACTION (optional) : Show a small personal address book.

The point of showing this object is to emphasize that each person typically keeps track of a relatively small number of people/phone numbers. Larger phone books will be shown later for comparison.

But what happens if the person moves and gets a new phone number? Well, if they remember, they tell you the new number. But if they don't contact you, then you will still have this old, obsolete number that no longer connects you to that person.

(This is a great way to discover if someone is still your friend ^_^)

(#2) How does the phone system connect calls?

Like most automated systems, the phone system works with numbers.

In this case, you give the telephone system the telephone number it needs to identify the target phone. It then uses this number to set a bunch of switches to make the complete connection.

The exact details of this routing are complex and have evolved considerably over time. In the early days of the phone system, there was a person who manually connected the calls using a plugboard. Nowadays, there are computerized systems that handle the connection automatically.

What we'll do here is present a greatly simplified system that is intended to give a general overview of how this switching works:

ACTION: Assign students and add labels to the nodes in the network graph:

1, 2, 3 : These are switches. No need for labels, but they should be referred to as switches during this part of the activity.
4 : Area code "206" – The next 3 are also switches, but it's convenient to refer to them as "area codes" or "local switches".
5 : Area code "212"
6 : Area code "425" – Only a label is needed here. No need to assign a student to this node since there is nothing for them to do.
7 : "you : (206) 555-1000"
8 : “neighbor : (206) 555-2000”
9 : "friend : (212) 555-3000”

You will need 9 students total: 8 students for the nodes (1-5 & 7-9) plus an additional student to act as a "runner" to help you make the phone connection.

Depending on how everyone is arranged, you may want to have the students sitting down at each node so that everyone can see what's going on. Have them stand up only when they are an active part of the demonstration.

Feel free to change the area codes and numbers, but make sure that you keep the labels consistent with the switching tables.

Each of these nodes has a "switching table" that tells it how to connect phone calls. Simply look up the phone number in the table and it will tell you which link to connect the call to. There's a primary and a secondary column - we're only going to use the primary column for now.

ACTION: Hand out the printed switching tables to the students in nodes 1-5. Node 6 also has a switching table, but it is not used in this exercise so it can be placed on the ground by node 6. This table can be used to extend the exercise if desired.

So, let's pretend that "you" are located in area code "206" and your phone number is "555-1000". If you want to call your neighbor at "555-2000" in the same area code, you simply dial your neighbor's phone number and your request is sent to the local phone company.

ACTION: Using a rope, have the "runner" student start from the "you" node and travel along the "Aa" link to the “206” switch. The rope should trail behind the runner so that it maintains a connection back to the "you" node. The student at the "you" node should pay out the rope as the runner walks away.

When the phone company gets the request, it uses the phone number and the switching table to connect the call.

ACTION: The runner student should approach the "206" node and ask to be connected to "555-2000". The student at the "206" node should look up this number in the switching table and direct the runner down the "Bb" link.

The runner should give a part of the rope for the 206 node to hold and then continue down the "Bb" link. When the runner reaches the destination, the rope should form a connection from the start (“you”) to the end (“neighbor”) nodes through the “206” switch.

Even if you want to call your friend who lives far away in a different area code (212-555-3000), the process is the same: you simply dial the number. The "206" node recognizes that it needs to send this to a different area code when it looks at the switching table.

ACTION: Reset the rope from the previous part and have the runner go back to the "you" node.

Have the runner start again, this time asking to be connected to "(212) 555-3000". As before, have the rope trail out behind the runner and have each visited node hold onto the rope and let it slide through their hand.

The "206" node directs the call down the "Dd" link to switch "1".

ACTION: For each of these connections, have the runner walk from the one node to the next along the path indicated by the switching table. As the runner gets to each node, they need to ask the node where to go next.

Switch "1" directs the call down the "Ii" link to area code "212".

And the "212" node sends the call down the "Pp" link to the friend's phone.

ACTION: At this point the rope should run from "you" (node 7) to "friend" (node 9) going through area code "206" to switch "1" and area code "212".

But what happens if one of the links or if an entire switch goes away?

ACTION: Disable the "Dd" link by "cutting" it. You can actually cut the rope to be dramatic, but it suffices to simply pretend.

What happens? You get "cut off" and the connection is dropped.

If you want, you can call back. And you might get the same connection path if the problem has been fixed. But if the problem has not yet been fixed, you'd like the call to be directed around the problem. For this reason, the switches typically have a primary/secondary path. If there's a problem with the primary path, it uses the secondary.

Let's assume that the problem has not been fixed. Now if you call back, you get a new path around the problem and your call will go through.

ACTION: Reset and start the call over again. Stand in the middle of the "Dd" link as a reminder that it is currently not working.

Now when the "206" node tries to connect the call through the "Dd" link, it fails and it needs to rely on the secondary path "Ee" which leads to switch "2".

Switch "2" sends the call down "Gg" to switch "1".

Where it continues, as before, down the "Ii" link to area code "212" and then down the "Pp" link to the friend's phone.

Notice how the connection is directed around the damaged part of the network. What happens if there is more damage to the network, for example, if the "Gg" link is also disabled? What happens if the entire switch "1" is broken?

ACTION: Remove other links/switches and see how the phone connection is directed around the damage. Have the students experiment with damaging the network. Which nodes are critical to making the connection? How much damage can this network sustain and still be able to connect the phone call?

So that is a (greatly) simplified view of how the phone system connects phone calls. But you may recall that the point of this activity is to demonstrate how the internet works, so we'll get to that in the next part.

[to be continued in Part III]

School presentation for CS Education Week

2009-12-18T05:47:00.000-08:00

Since last week was Computer Science Education Week, I spent some time at my daughter's new school to give a short presentation about computer science and engineering.

It was an eclectic mix of topics/activities:

They had to find all the computers in the classroom. That is, find all the items that had computers/microprocessors inside them, so it included the printers, microwave ovens, CD players, cell phones and TVs in addition to the obvious desktop computers.
I took apart an old GBA and identified the various components. Also, I put it back together afterwards to verify that it still worked!
We discussed the logic needed to control a character in a simple platforming video game - how to move the character when the player presses the buttons on the control pad.
Demonstrated some small electronics projects that show how a single bit of memory is stored.
Passed around an 8" wafer from Intel. These are really neat to look at - and one of the students had a parent working at Intel but had never seen a wafer.

And finally, I had them get into groups of 3 and do the How Computers Work activity. And that's where things got a bit interesting.

Competition

There were 6 students - 3 boys and 3 girls - and they naturally divided themselves into a group of boys and a group of girls.

While handing out the papers for the activity, one of the boys suggested that it should be a competition to see who would finish first. I watched to see the reaction of the students - the girls (and perhaps the other boys as well) didn't seem to be interested, and the one who suggested it moved on and didn't push for it.

I realized how easy it would have been for me to encourage this competition - I would be reacting to a student's request and that's usually an appropriate thing to do as an instructor. But it also would have partially alienated some of the students who did not want to be part of a competition. At the very least, it would have made it more stressful for them to participate. It made me wonder how many times in the past I had inadvertently done something similar and made things more difficult for some of the students.

Knowing what I know now about learning differences between girls/boys (and students in general), I would have stopped the competition anyway by pointing out that the two teams had different (albeit comparable) "programs" so a timed competition wouldn't really be fair. But I was relieved that the topic went away on its own.

Starting early

The other aspect that was interesting was that as the boys were forming their group, they discussed all the computer/technology stuff they had done before: The computer camps they went to, the programs they had written, the robot they helped build, and so on.

This sort of conversation did not happen with the girls team.

One comment from a boy struck me. I can't remember the exact quote and when I replay my best recollection it seems harsher now than it did at the time (so I'm sure I have the quote wrong somewhat). But the comment was something like: "the girls aren't interested in computers" or "they don't know much about programming, except for GirlX". GirlX being my daughter, the only one that apparently had been exposed to computer programming beforehand.

So, by 7th grade, the majority of boys (in this admittedly very small sample) had already gone to a computer camp of some sort whereas none of the girls had. Some of them had already formed their view of what was interesting to boys vs. girls.

So now I wonder,

Is 7th grade too late to start introducing computer programming in the classroom?
Is this related to boys tendency to brag and overstate accomplishments vs. girls tendency to understate?
What are the parents' roles in this? Did they offer computer/math camp to their daughters? Should they have? My assumption is that most parents follow the natural interests of their children, so they will look for camps that their children have already expressed an interest in.

I have been working on the assumption that 6th through 8th grade was the critical period to introduce programming, with pre-programming skills (binary, logic, ...) taught in 3rd through 5th grade. But I also assumed that starting anytime in 6-8th grade would be OK, even if it could have been started earlier.

After this, I'm wondering if the first introductory programming class really needs to be before middle school starts.

How the Internet Works (activity for elementary/middle school)

2009-12-08T15:03:00.000-08:00

The post is the first installment of a "How the Internet Works" activity which is suitable for upper-elementary and middle school students.

I've been running this activity for the past year or so and have been promising to write it up for a while. With Computer Science Education Week happening this week, it seems like the perfect opportunity to get my act together.

I'll be posting this activity in 4 separate parts:

(1) Overview and setting up
(2) The phone system (switching network)
(3) The internet (routing network)
(4) DNS (Domain Name Server)

Overview

This activity is an interactive demonstration of what happens when you type a URL into a browser.

In this activity the students will be guided to act out the various parts of the internet: websites, routers, name servers, ISPs and home computers. In this activity, students will:

Learn the difference between a switching (phone system) and routing (internet) network
See how packets are routed through the internet
See how the internet routes around damage
See how domain name servers are used to lookup an IP address

It is designed for 8-13 students, but fewer or more can be accommodated if needed.

Required time

Preparation:

30 minutes printing and creating signs
1 hour room prep (creating network on the floor using tape)
plus whatever time you need to familiarize yourself with the material

Activity: 45 minutes

Note: Because of the room preparation required for this activity, you may want to present it multiple times back-to-back to different groups of students.

Materials

You will need the following materials:

Masking tape/chalk to mark network on floor
Masking tape is useful indoors, chalk works well on hard surfaces outdoors
You'll want at least a couple of rolls of masking tape for this
Alternately, if outdoors, you can use hula hoops and rope to mark the network
Note that you'll need to attach labels to each rope
Rope (50' is more than enough)
This is used to show the phone switched connection
Manilla folders
Used to label the network nodes
You can skip this if you have another way of labelling nodes
Markers
To write labels on the masking tape and manilla folders.
Print out the following:
Routing tables
Packets
Website results
Scissors (to cut out holes for the “images” from the web page printout)
Props (optional):
Small, personal address book
City phone book (as thick as possible, perhaps have a few from different cities)

Preparations

(1) Draw the network map on the floor

Draw the following network map on the floor using masking tape:

You'll want an open space roughly 20'x20' (6m x 6m) in size for this.

If you're outdoors, you can use chalk or you can use anything else convenient: hula hoops connected by rope would also work. The important thing is that you're able to label each node and link in the diagram.

Make each node (circles/boxes) large enough for a student to stand/sit within. Circles are hard to do with masking tape, so squares are fine (the shape of each node does not matter). Each square should be about 3' (1m) on each side. Nodes 10-13 can be a different shape (like a triangle) if desired.

Make sure there's enough space between each node so that the links between them are easy to see. Ideally it should take from 2-3 steps (~5' or ~1.5m) to go from one node to another.

The graph is easier to make if you start with the 3 central nodes (1, 2, and 3) and label them for identification. Add the other nodes to this core network, but don't label them yet (since they will change function during the activity) – you will make signs for these nodes. See the next section (about creating signs) for information about labeling each of the nodes.

Each of the links between the nodes should be labeled so that they are easy to identify. If using masking tape, write the label directly on the tape.

Write the label more than once along the tape. At least mark the points closest to each node, but it is preferable to mark all along the tape (separated by ~1' (~30cm)).
Note that the students will be walking around and viewing the labels from all angles, so make sure that they are easy to read.
We use both upper-case and lower-case letters to label each link (e.g., "Aa"). This is because the labels will be viewed from all angles as the students walk around and using just upper or lower case letters leads to cases where the labels are ambiguous ("p" vs. "d" or "H" vs. capital "I" with serifs) .

The graph can be stretched and distorted to conform to your environment, but do not change the topology (i.e., don't change the connections between the nodes).

(2) Create signs to place on the internet nodes

Only 3 of the nodes that you just created can be labeled permanently (i.e.: for the duration of the activity): “1”, “2” and “3”. You can label these using tape or chalk or whatever is convenient.

Don't give permanent labels to the other 10 nodes because we need to give them more descriptive names during the presentation (and these names will change during the course of the activity). You should create name tags for these nodes - I just use manilla folders and wrote the node names on them, but you can label them however you see fit.

You will need to create the following 10 signs:

For Part II (phone system):

“206”
“425”
“212”

(or you can choose whichever 3 area codes you like. Just remember to adjust the switching tables to be consistent.)

For Part III (internet):

“google.com”
“wikipedia.org”
“ISP”

(or you can replace these with whichever search engine / web resource you prefer. Just remember to adjust the routing table and all the packets to be consistent.)

For Part IV (DNS):

“root name server” (rns)
“.com name server” (.com ns)
“.org name server” (.org ns)
“ISP name server” (ISP ns)

(3) Print out the switching/routing tables and internet packets

Print out all of the switching/routing tables and internet packets in the PDF files. They should all be printed single sided.

[Links to these files will be in the following posts.]

(4) Cut out holes for the “images” from webpage in last set of packets

The last set of printouts requires that you cut out the squares where the images should be displayed in the web page.

[to be continued...]

Octal counting worksheets

2009-12-07T21:14:00.000-08:00

I've added a couple of worksheets for practicing with writing numbers in octal to the cse4k12.org website.

These worksheets can be used by students to practice counting/converting numbers in octal. They each show a set of circles that the student must count in both octal and decimal. The circles are arranged in groups of eight to make the octal calculation straightforward.

cse4k12 ~ resources

2009-12-06T18:05:00.000-08:00

Over Thanksgiving I started playing around with App Engine and threw together an a fairly simple app for keeping track of Computer Science (& Engineering) teaching resources.

I probably would have waited a bit before making it available, but with Computer Science Education Week going on right now, I figured that this was as good a time as any.

It's running at http://cse4k12.appspot.com/ and you can use it to search for resources by topic, add comments/reviews or you can add links to your own material.

It's still fairly early and I'm still going through and adding all the material that I'm aware of - I'll be adding it piece-by-piece as I get around to it. If you know of anything that is not listed, then please feel free to add it.

Authentication... sigh...

The thing that bugs me the most about it is that, while no login is required to access any content on the site, you do need to login in order to add resources or comments. This is to help prevent people from spamming the site with useless comments/advertisements.

I didn't want to force people to create yet another account/password just for this site, so you can use your Google account (gmail account) for authentication. And no, this doesn't mean that you give your password to us - what happens is that we send you to Google where you login and then they send back a token that says "the current user has successfully logged in as xxx@gmail.com". That's all we get: your email (well, and a "nickname"). Which is great because we don't really want or need anything else.

Of course, this doesn't help you if you don't already have a Google account. While it's easy to create one, you'd probably rather use your Passport or OpenID account or whatever it is you use on a day-to-day basis. I plan on adding support for these different authentication providers, but haven't had a chance to do it yet. Please let me know if you would find this useful so that I can prioritize adding support for this.

Updated bitmap (binary/hex) worksheets

2009-11-15T15:14:00.000-08:00

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.

Slides for AMS 2009 workshop

2009-10-17T04:27:00.000-07:00

These are the slides for the "Computer Science Education in the Montessori Classroom" workshop that I presented yesterday at the AMS Fall 2009 conference.

I added an extra slide to include a diagram of a ripple carry adder.

Slides are available in the following formats:

Note that the PDF and PowerPoint versions were converted from the original OpenDocument format file. Because of the conversion, a few of the slides look a bit funky in the PowerPoint version. If this is a concern, please use the OpenDocument (using OpenOffice) or PDF (using Adobe Reader) version.

How Computers Work (high level)

2009-10-17T04:11:00.000-07:00

This is an activity for 3 students to work together as a group. Each student takes on the role of a different part of the computer:

CPU
ALU (& memory)
Graphics display

They work through the project with the CPU running the "program", the ALU performing the math and keeping track of the variables, and the display plotting the values as needed.

The purpose of the activity is to give the students a sense of how computers work at a reasonably high level.

I created this a while ago, but neglected to actually post the information here. Full information about this activity can be found at http://cse4k12.org/how_computers_work/index.html.

Computer Science Education in the Montessori Classroom

2009-10-17T02:04:00.000-07:00

I gave a "Computer Science Education in the Montessori Classroom" workshop at the American Montessori Society (AMS) Fall conference yesterday.

The workshop description that we submitted (oh so many months ago) was:

How can we better prepare our children for life in a high-technology society? How early should we teach them computer and pre-programming skills? How can we integrate computer science education into Montessori classrooms? This presentation of Montessori-friendly and age-appropriate activities will include stand-alone activities and extensions to existing classroom curricula as well as a take-home list of some useful online resources for teachers.

Looking back at this, it sounds sufficiently vague that I probably could have talked about anything as long as I mentioned computers every so often.

The following would perhaps have been a better overview:

Why aren't we teaching pre-programming skills (binary, boolean logic, transistors) to our children during elementary school? Why don't we teach students how computers actually work instead of simply how to use them? In this workshop, we will show (1) how computers work and (2) how you can teach these concepts to your elementary/middle school classroom.

A part of me wants to say something more confrontational like "how we're failing our students by not providing a solid understanding of computer technology", but I'll resist the urge and hold off on that rant (until another time perhaps ^_^).

I'll be posting the slides here once I get a chance to upload them.

cse4k12.org vs. cse4k12.com

2009-10-17T01:56:00.000-07:00

Grrrr....

cse4k12.org is supposed to be the main URL for the website and cse4k12.com is supposed to simply redirect to .org.

Unfortunately, it looks like things are set up screwy and .org no longer redirects to the right place. I'll have to fix that but in the meantime all of the cse4k12.org links in the blog were not working.

Temp fix: change all the links to .com. I'll change them back once I fix the issue with .org, but for now if you have problems with any .org address, just change the "org" to "com" and it should work.

[Update: This has been fixed. All .org links are working again.]

New Spritely tutorials: Creating NDS ROMs

2009-04-04T14:43:00.001-07:00

Two new tutorials for Spritely:

* Creating an NDS ROM File
* Info about GBA and NDS cartridges

Crossbin puzzle #2

2009-03-28T06:56:00.000-07:00

Binary magic trick

2009-03-28T06:49:00.001-07:00

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

2009-03-22T10:27:00.000-07:00

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

New Spritely tutorial: Adding a Projectile

2009-03-16T14:30:00.001-07:00

I've added a new tutorial for Spritely that shows how to add a single projectile to a game project.

http://spritely.googlecode.com/svn/trunk/tutorials/projectiles.html

Spritely in action

2009-03-13T08:49:00.000-07:00

John is using Spritely to introduce his son to programming and made a video:

http://botchagalupe.tumblr.com/post/84674186/teaching-kids-how-to-code

It looks like I have to get my act together and make more tutorials available (e.g., projectiles).

SIGCSE 2009 slides

2009-03-08T08:43:00.000-07:00

Here are the slides from my SIGCSE 2009 presentation:

"Introducing Computer Programming via Gameboy Advance Homebrew"

Slides (PDF)
Paper (PDF)
Note: Requires ACM Web Account.