Chrysolites Tech Academy

Introduction to Computer Science: Harvard CS50 · Course book

Chapter 1: Bits, Algorithms and Blocks

Pairs with Lesson 1: Computational Thinking and Scratch

Computer science is less about computers than about solving problems. A problem has inputs, the information you start with, and outputs, the answer you want, and the work in between is a step-by-step method called an algorithm. This chapter covers the two foundations that every later chapter builds on: how a computer represents information using nothing but on and off, and how to think about algorithms clearly enough to judge which one is better. It ends with a first look at programming in Scratch, a visual language that lets you build programs from blocks.

Counting with only two digits

People count in decimal, using ten digits, 0 to 9, probably because we have ten fingers. Each position in a decimal number is worth ten times the one to its right: in 123, the 1 means one hundred, the 2 means twenty and the 3 means three.

Computers are built from billions of tiny switches, called transistors, each of which is either on or off. That makes a two-digit system natural: 1 for on and 0 for off. This is binary, and each binary digit is a bit. Binary works exactly like decimal, except that each position is worth two times the one to its right.

Position value1286432168421Decimal total
Bits for 5000001014 + 1 = 5
Bits for 500011001032 + 16 + 2 = 50
Bits for 720100100064 + 8 = 72
Bits for 25511111111128 + 64 + … + 1 = 255

A group of 8 bits is called a byte. It can hold 2 multiplied by itself 8 times, which is 256, different patterns, so it can represent the numbers 0 to 255. Every extra bit doubles the range, which is why sizes in computing are so often powers of two: 16 bits give 65,536 patterns, and 32 bits give about 4.3 billion.

From numbers to letters, colours and more

If a computer can store only numbers, how does it store a letter? By agreement. A standard called ASCII assigns a number to each English letter, digit and punctuation mark. Capital A is 65, B is 66, and so on; capital H is 72 and capital I is 73. When a computer receives the bytes 72 and 73 in a context where text is expected, it displays "HI". The same bits could mean the numbers 72 and 73 elsewhere; context decides.

ASCII uses 7 bits, enough for 128 characters, which covers English but not the thousands of characters used in other writing systems. Unicode extends the idea, using more bits per character to give a number to the characters of virtually every language, and to emoji. An emoji is simply a character with a large number, drawn as a picture by your device.

Colours follow the same principle. A common scheme, RGB, describes each colour by how much red, green and blue light it contains, each as a number from 0 to 255, one byte apiece. The values 72, 73 and 33 mean a little red, a little green and less blue, a dark yellowish colour. A picture is a grid of such dots, called pixels, so a small 1,000 by 1,000 image already needs 1,000,000 pixels × 3 bytes = 3,000,000 bytes. Video is a sequence of pictures shown quickly, and sound is a sequence of numbers describing a wave.

Abstraction. Each layer hides the one beneath it. You think about a photograph, not about pixels; about pixels, not about bytes; about bytes, not about transistors. This idea, called abstraction, is one of the most important in computer science.

Algorithms: the phone book problem

Imagine an old printed phone book of 1,000 pages, sorted alphabetically, and the task of finding one person's name. There are several algorithms.

  1. One page at a time. Start at page 1 and turn pages until you find the name. It is correct, but in the worst case you turn all 1,000 pages.
  2. Two pages at a time. Twice as fast, at most about 500 steps, but you could skip the name. You must be ready to step back one page when you overshoot, which costs at most one extra step.
  3. Divide and conquer. Open the book in the middle. If the name you want comes earlier in the alphabet, tear the book in half and keep only the first half; otherwise keep the second. Repeat with what remains.

The third algorithm is dramatically better. Each step halves the problem, so 1,000 pages become 500, 250, 125 and so on, down to 1 page after about 10 steps, because 2 multiplied by itself 10 times is 1,024. If the phone book doubled to 2,000 pages, the first algorithm would need 1,000 more steps, while the third would need just one more.

n: one page at a timen / 2: two at a timelog₂ n: divide and conquer 05001,000 02505007501,000size of the problem (pages) steps needed in the worst case
Figure 1.1 — Three ways to search a sorted phone book. The two straight lines grow in step with the book; divide and conquer barely rises at all.

Two properties matter when judging any algorithm. The first is correctness: does it always give the right answer? The two-pages-at-a-time method is only correct if you remember to step back when you overshoot. The second is efficiency: how much time, or memory, does it need? Divide and conquer is both correct and efficient, but it relies on the book being sorted; on an unsorted list it would fail. Choosing an algorithm always means checking what it assumes about its input.

The shapes in Figure 1.1 have names. The first two grow linearly, in proportion to n, the size of the problem. The third grows logarithmically, as log₂ n, the number of times n can be halved before reaching 1. Comparing how running time grows is the core of judging algorithms, a theme that returns in Chapter 3.

Writing algorithms down: pseudocode

Before writing real code, programmers often describe an algorithm in pseudocode: plain, precise English with numbered steps. The divide-and-conquer search might read:

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

This short listing contains the building blocks found in almost every programming language. Verbs such as "pick up", "open" and "call" are functions, actions to perform. "If", "else if" and "else" are conditions, choices between paths. Questions such as "is the person on the page?" are Boolean expressions, whose answer is true or false. "Go back to line 3" creates a loop, repetition. The final "else", which handles the case where the person is not in the book at all, matters more than it seems: programs that forget to handle an unexpected case are a common cause of crashes and freezes.

Programming with blocks: Scratch

Scratch, developed at MIT, is a programming language in which you drag puzzle-piece blocks together instead of typing. It is used here because it lets you focus on ideas without worrying about punctuation. Every concept from the pseudocode appears as a block.

when green flag clicked set counter to 0 repeat 3 say "hello" for 1 second change counter by 1 event: starts the programvariable: stores a valueloop: repeats the blocks insidefunction: an actionupdates the variable After it runs, the sprite has said "hello" three times and counter holds 3.
Figure 1.2 — A small block program. Each block corresponds to a concept from pseudocode, and the shapes only fit together in ways that make sense.

Scratch programs control characters called sprites on a stage. Blocks fall into families: events start scripts ("when green flag clicked", "when this sprite is clicked"); variables remember values, such as a score; loops repeat ("repeat 10", "forever"); conditions choose ("if touching the edge, then turn around"). Several scripts can run at the same time, which is called concurrency, and sprites can send each other broadcast messages to coordinate.

Good programs are built gradually. Rather than writing a whole game at once, you make one small piece work, test it, and add the next. And when the same group of blocks appears in several places, you can define your own block, giving it a name and using it like any other. That is the same idea as a function in pseudocode, and it keeps programs short, readable and easy to change.

Check your understanding

  • Write 13 in binary. (Answer: 8 + 4 + 1, so 1101.)
  • What decimal number is the binary 101010? (Answer: 32 + 8 + 2 = 42.)
  • How many different values can 10 bits represent? (Answer: 2 multiplied by itself 10 times, 1,024.)
  • Using ASCII, which word do the numbers 72, 73 and 33 spell, if 33 is the exclamation mark? (Answer: HI!)
  • About how many steps does divide and conquer need for a 4,000-page phone book? (Answer: about 12, since 2 to the power 12 is 4,096.)
  • Name the four building blocks found in the pseudocode, and give an example of each.
  • Why should every program handle the "else" case?

Install Chrysolites Tech Academy

Android / Chrome / Edge: open the browser menu and choose Install app or Add to Home screen.

iPhone / iPad (Safari): tap the Share button, then Add to Home Screen.