teaching machines

CS 352 Lecture 2 – Bases

September 9, 2016 by . Filed under cs352, fall 2016, lectures.

Dear students,

Last time we looked at how aliens might encode a message and send it to us. After class I was thinking about the suggestion that they use ASCII. But this would really be quite a leap for them, because the only alphabet that they know that we understand is Morse. All the communication that we’ve ever sent them has been in Morse, so it’s natural that they would send Morse back to us, albeit in some representation that their technology can support.

Also, I’ve had a few reports that making a persistent USB drive with Linux on it is not working out so well. Therefore, I strongly recommend that you just create a virtual machine. If you can get a USB drive working and provide on Piazza platform-independent directions that the rest of the class can follow, I’ll happily award an extra credit participation point.

Today we’re going to start with a little game called Sum This. I will send a series of green circles across the screen, with black representing 0 and bright green representing some maximum integer value. I will communicate that maximum value to you. Other intermediate shades of green will appear between black and bright green to represent intermediate values. It’s your job to sum up the values of all the circles you see.

I invite you to think about why we are playing this game, but hold on to your interpretation for a moment. Take a moment and complete this exercise with a partner:

How many digits long is value n when represented in base b? Draw a graph for various values of n. Work out a formula on paper. Start with real numbers and then generalize.

What’s appealing about large alphabets is that we can represent information in them in very few digits. The bigger the alphabet, the shorter the representation. But these days we don’t use large alphabets. We use an alphabet with two symbols, which we abstract to 0 and 1.

Early in technology’s history, there was less agreement that information should be represented in a binary form. The world after all is not binary. Voltages in a circuit span a range, as does magnetism, tides, brightness, and every other natural phenomena. To sense these analog phenomena, you needed a very accurate sensor, one that can discern the different levels of the phenomena. One could say that the size of the “alphabets” of these phenomena is high. One can say that the size of a phenomenon’s alphabet is directly proportional to the sensitivity of the instrument that measures it.

Suppose we could make instruments that were sensitive enough to discern large alphabets. We’d still have the problem that these phenomena fluctuate. The world is noisy, and we can’t rely on steady measures.

The solution is two reduce ourselves to a binary alphabet. All measures under some threshold are 0, all measures above are 1. (In reality, there’s often an invalid gray area in the middle.) When restrict ourselves like this, we lose digit “depth”. How do we regain it? By trading it for length. We extend our representation out, using multiple bits to represent larger quantities.

In a restricted alphabet, the value of each digit in a piece of information is determined by two properties: its symbol and its position. As a quick review of ideas you’ve visited in earlier classes, let’s examine a binary number: 111010. What is the value of each digit?

Now let’s play another game. Let’s write a program that takes an arbitrary int and flashes each bit using an Arduino’s LED. After we get the program working, I’ll switch up the number and you see if you can determine what it is through the flashing.

If we have time remaining, we’ll review Makefiles by writing one for the alien code we wrote last time.

Here’s your TODO list of things to complete before next class:

See you next class!

Sincerely,

P.S. It’s Haiku Friday!

What’s 1111?
Four, of course, in unary
Scratched on my cell wall

P.P.S Here’s the code we wrote together…

wigbin.ino

void setup() {
  pinMode(13, OUTPUT);
  delay(3000);
}

void loop() {
  int i = 61;

  while (i) {
    digitalWrite(13, HIGH);
    int lsbit = i & 1;
    if (lsbit == 1) {
      delay(1000);  
    } else {
      delay(250);
    }

    digitalWrite(13, LOW);
    delay(250);
    
    i = i >> 1;
  }

  delay(10000);
}