Everything Is Bits: Representation, Algorithms and Scratch

What this week is about

This week follows CS50 Week 0: first how computers represent information, then what an algorithm is, then the five ideas behind every programming language, built one block at a time in Scratch. The orange boxes are the Scratch programs we build together in class. Every one of them is downloadable, so you can open it yourself: in Scratch, File → Load from your computer.

Part 1 · What is computer science?

Picture a box. A problem goes in on the left, a solution comes out on the right, and the box in the middle is what this whole course is about. But before we can say anything about the box, we need to agree on how the things going in and coming out are written down. We use words, numbers and pictures. A computer has only electricity, which is either flowing or not.

Part 2 · Representation: everything is bits

Unary, decimal, binary

How high can you count on one hand? Five, if each finger is one unit. That is unary. Now treat each finger as a bit: down is 0, up is 1. Suddenly one hand counts to 31, and two hands to 1023. That is not a trick, it is place value, and it is the whole secret of the machine in front of you.

In decimal we have ten digits, and each position is worth ten times the one to its right (1, 10, 100). A transistor is a switch, on or off, so a computer has two digits, and each position is worth two times the one to its right (1, 2, 4, 8, …).

A single binary digit is a bit; eight of them are a byte; a byte holds 2⁸ = 256 values, 0 through 255. Click the bits, then type your name:

Text: ASCII and Unicode

Bits are just numbers. To store letters we need an agreement, and the 1963 agreement is ASCII: 65 is A, 66 is B, 97 is a, 48 is the character 0, 32 is a space. So what does 72 73 33 say? Look it up in the table: H, I, !.

ASCII has 128 characters, enough for English and little else. Unicode extends the same idea to about 150 000 characters, every writing system and every emoji, stored as 1 to 4 bytes per character in UTF-8: ş is two bytes, 😂 (code point 128 514) is four. Every emoji you have ever sent was a number.

Color, images, sound, video

• A pixel is three bytes, red, green, blue, each 0–255. (255, 255, 255) is white, (0, 0, 0) black, (255, 0, 0) red. Zoom into any emoji far enough and the squares appear. “Enhance!” in crime shows is impossible: there is nothing behind the bytes.
• An image is a grid of pixels plus a header; a video is many images per second; sound is a wave sampled 44 100 times a second, each sample a number.
• Programs are bits too, instructions the processor understands. We meet them in week 3.

The notebook at the bottom of this page draws a pixel-art smiley from a grid of numbers. Open it in Colab after class.

Part 3 · Algorithms

The classic example: find John Harvard in a 1 000-page phone book.

1. Page by page: correct, up to 1 000 steps. Linear search.
2. Two pages at a time: twice as fast, but you can overshoot and need a check step. Still linear.
3. Open the middle, decide which half, tear the other half away, repeat: 10 steps for 1 000 pages, 20 for a million, 30 for a billion. Binary search, and it only works because the book is sorted.

Correctness first, then efficiency; the second column is why Google feels instant. Week 5 turns this into a science (Big O).

Pseudocode

Write the algorithm in English with structure, and the vocabulary of every programming language appears by itself:

1  Pick up phone book
2  Open to middle of phone book
3  Look at page
4  If person is on page
5      Call person
6  Else if person is earlier in book
7      Open to middle of left half of book
8      Go back to line 3
9  Else if person is later in book
10     Open to middle of right half of book
11     Go back to line 3
12 Else
13     Quit

Keep this table in mind for the rest of the page: every Scratch program below is one or two rows of it.

Part 4 · Scratch: the five ideas, one block at a time

Scratch is a block language from MIT. You drag blocks instead of typing, so there are no syntax errors, and we can concentrate on the ideas. Open scratch.mit.edu → Create. Three areas: blocks on the left, scripts in the middle, the stage on the right. Colors are categories: Motion, Looks, Sound, Events, Control, Sensing, Operators, Variables, My Blocks.

What Scratch taught you, in one list

• Functions with arguments (say hello) and return values (answer, join).
• Loops: repeat n, forever, repeat until.
• Conditions on boolean expressions: if touching … then … else, and, or, not.
• Variables: set score to 0, change score by 1.
• Events: green flag, key pressed, sprite clicked, broadcast received.
• Abstraction: make a block, with or without inputs; reuse across sprites.

Part 5 · Where this goes

The same program, twice:

when green flag clicked
say [hello, world]

#include <stdio.h>

int main(void)
{
    printf("hello, world\n");
}

main is the green flag, printf is say. The semicolon ends a statement; the braces group statements into a block. Next week we type this ourselves, and every block you dragged today gets a text spelling. Not in today’s lab, though: today’s lab is all Scratch and bits.

Summary

• Computers hold only bits. Numbers, text, color, sound, images and programs are all bits under an agreement (binary, ASCII/Unicode, RGB).
• 8 bits = 1 byte = 256 values; n bits give 2ⁿ values.
• An algorithm is a precise procedure; binary search needs a sorted input and takes about log₂ n steps. Pseudocode is how we design before we code.
• Five ideas in every language: functions, conditions (on booleans), loops, variables, events; plus abstraction (custom blocks) to manage size.
• The lab starts at 15:00: Lab 1 · Hello, Scratch. You can begin before the instructor arrives.

Tags:binarybitsbytesASCIIUnicodeRGBalgorithmbinary searchpseudocodeScratchabstractionfunctionsloopsconditionalsvariablesevents