Covered in the first lecture of the Harvard’s computer science course are the very basics of computer science. What it is, and the fundamentals of how it achieves this; bits, bytes, binary, how to represent letters, numbers and colours. It goes on to cover some absolute foundations of programming.
Malan starts off describing what computers do; they take an input, perform a function on it and spit out an output.
Input -> Function -> Output
He then talks about numbering systems. Us humans use base10; the decimal system. There are other systems too. Computers don’t function using base10, they use base2 or binary. Either on or off. There are only 2 options. In the binary system, we can represent any number using ons and offs, or 1 and 0. A binary digit is known as a ‘bit’. The intuition of understanding on and off or 1 and 0 is that they represent a state of a switch. The switch is either on or off. In a computer, a phone, a calculator or any digital device there are circuit boards with devices that house thousands and millions of switches called transistors. Transistors are tiny little switches that are either on or off (or 1 and 0 respectively). Nowadays digital memories can store millions and millions of bits. A singular bit is either 1 or 0. Now let’s see how to represent a number in binary. We start with a line of bits; 000. These switches are all off, so it’s zero. 001 represents 1. 010 represents 2, 011 represents 3, 100:4, 101:5, 110:6, 111:7. In this 3 bit system we can represent numbers upto 7, 8 including zero. The maths here is 2 to the power of 3 equals 8. 2 because it’s base2, 3 because that’s the number of bits we are playing with. Obviously in a computer we can represent numbers much higher than this. A byte is a collection of 8 bits. In an 8 bit system we can represent 256 numbers (28). I’m not going to go more into counting in binary as I learnt it in high school physics.
We can use this system to represent letters. In the early days, we used a system called ASCII (American Standard Code for Information Interchange). Some group of people in a room decided the standard for representing letters using numbers. Capital A is 65, B 66, C 67. Lower case a is 97, b 98, c 99 etc. They are contiguous. They only allocated a byte per character, this means that we can only represent 256 characters. You can use an ASCII lookup table on the internet to see what numbers represent what characters. Unfortunately this is only enough to represent English language characters (upper and lower case), numbers 0 – 9, punctuation and some extras. The limited number of characters inherent in ASCII couldn’t include characters from other languages. Nowadays we use a system called Unicode, this uses 32 bits which gives 4,294,967,296 different character possibilities, which is huge. Now we can represent every character in every language, all sorts of punctuation characters but also loads of different emojis too.
We can use binary to represent colours. For each pixel on the screen, its colour can be broken into Red Green and Blue components. Each component can be represented by an 8 bit number, 0 – 255. When you mix the relative intensity levels you get a resultant colour. When you display all of the different pixels’ colours in the correct order, you get an image. We create video by stacking a load of images called frames and flicking through them at a certain frame rate. 24fps in standard cinema, just like creating a stop motion animation or drawing cartoons out on paper and flicking through them quickly. To represent audio, we can split the audio into time-based segments called samples. In a CD we split 1 second of audio into 44100 samples. Each of these samples has an amplitude that we need to digitally record as a binary number. Again in a CD we use 16 bits per sample. So each second of audio is represented by 44100 binary numbers, sequenced in order. This is known as Pulse Code Modulation (PCM) We can represent musical notation using a system called MIDI (Musical Instrument Digital Interface). Each note played is represented by a number, how hard we hit a note (velocity) is represented as a number, the moment we release a note is represented, the pressure which we apply to the note after pressing the note with the initial velocity is represented. All of these values are sent in the correct order and are interpreted to create musical notes. We can even assign different instruments different numbers, and then we can score a whole orchestra. Looking at this globally, we can do a lot with 0s and 1s. We just need a convention of how to store and how to read the information.
The next section talks about algorithms. An algorithm is a very precise way of doing something. It has to be precise. When leafing through a phonebook to find someone called John Harvard we can turn each and every page and eventually find him, but it would take a long time. We could turn every 2 pages, it would be twice as fast, but we might miss the name is one of the skipped pages. Or we can go to exactly the middle, and check what character we are at. We discard the half of the book that the name isn’t in. Then we go to the middle of the remaining book, and discard the portion of the book not containing the name. We can keep iterating this and get to the answer without fail in the shortest amount of time. In a 500 page phonebook, this method would result in 10 steps, rather than possibly 500 steps using the first method. Both the first and last method work, but the last is much more efficient. Mathematically, the first algorithm takes n steps, where n is the number of pages, the second algorithm is n/2, the last is log2 n. If were were to double the phonebook, the first algorithm would take double the amount of time, but for the last algorithm we would only need to add one more step. The power of learning algorithms and thinking algorithmically is to be able to navigate big data in the best, most efficient and easiest way.
To implement these English language algorithms, we can still use English but write out pseudo-code. We convert the intuition we wrote out into formal steps:
Step 1; pick up the phonebook.
Step 2; turn to the middle of the book.
Step 3; Look at page.
Step 4; if person is on page,
Step 5; call person.
Step 6; Else if the person is earlier in the book then
Step 7; go to the middle of the left part of the book
Step 8; go back to step 3.
Step 9; Else if the person is later in the book
Step 10; open to the right half of the book and
Step 11 go to step 3.
Step 12; Else
Step 13; quit.
In our pseudo-code, we have actions, or verbs, or in computer science we call them functions (Pick up, call, look, go). The ‘else’ and ‘else if’ are called conditionals. Proverbial forks in the road. The questions we ask to get these answers are called boolean expressions. It has a yes or no answer; a 1 or 0 answer; a true or false answer. The indentations are important; indented blocks belong to the preceding condition; it tells us that this is the function to be performed if the boolean expression is true. There is another fundamental feature; ‘go back to’. This points to looping behaviour. Looping something until it becomes true or false.
Artificial intelligence doesn’t work like this. It can figure out the steps. It works by being trained on lots of data and letting it figure out what it should say. It boils down to statistics and probability. It works out what you are asking and formulates an answer it thinks is the most probable answer based on all of the data it has been fed. This is inspired by neural networks in our human brains. Computer scientists have been able to model neural networks using 0s and 1s, and store all of the training data in the neural networks. It used to be that if we come across a problem and we can’t figure out where we have gone wrong, we were encouraged to talk to a rubber duck, list out the logical steps and often the solution would come to us. Now we have AI to ask and get more in depth answers.
Malan next talks about Scratch; a graphical-based programming program. It is used to teach the way programming languages work, all of the intuition in Scratch is the same across most other languages. I’m not going to write out the specifics of how to use the program, but rather the intuition he’s teaching. I hope. One thing I want to note is the difference between a function and side effect. The ‘Say’ block is a function. It takes the input from the user input text field, and prints the input. The side effect is the cats saying something.
Input -> Function -> Output
“hello, world” -> The ‘say’ block -> The cat saying “hello, world”.
A return value is an output that the program returns to you. It can be stored as a variable to be used later. An argument to a function is an input. Return values can be used as the argument to another function, chaining or nesting functions. These are executed like brackets in maths. It is possible to create a program in Scratch that makes the cat meow 3 times with a 1 second pause in between. One way is to drag in the meow function block, and the pause function, and copy paste these 2 more times, thus it will meow three times with a 1 second pause in between. This is correct as it does what we want it to, but it’s not very graceful; it’s messy. Copy-pasting code is bad practise and can always be fixed by programming better. Using a loop is a better way. That way you can specify easily how many times to loop, and you can alter the code in the loop if you want different behaviour. In the copy pasta version it is not as easy to do as you’d have to change the behaviour in each of the copy pasta. We can also create our own functions, say we will use a certain routine again and again within a program, instead of writing it out every time, we can abstract it out into it’s own function, and call back to it again and again. It’s now reusable. When we create functions we can create space for arguments to be passed into the function.
When creating complex programs, it is difficult sometimes to create the whole program all at once. Sometimes it is easier to create it in versions, adding functionality in each version. Baby steps.
That is the end. Malan shows off some previous projects he and other students have created, but I don’t feel like it adds to the content of the lecture. I also didn’t have any questions or points that needed further research.