Computational Thinking

by Nick Wong ‘20

Binary

We’re used to thinking in decimal; we have 10 fingers after all!
But computers think in binary - all 0’s and 1’s!
If you’re comfortable in decimal, you could argue binary is easier; only 2 numbers, not 10
Binary goes from smallest to biggest, right to left. i.e. 001 is read in the order 1, 0, 0, which translates to 2^0 + 0 + 0 = 1 in decimal
With only three places or columns in our binary number, the biggest number we can have is 111 = 7. How do we get bigger numbers?
More digits, or more memory/hardware, allow us to represent bigger numbers. i.e. 4 spaces could be up to 1111 = 15
With these 0’s and 1’s, and now bigger numbers represented this way, how do we represent other things?

ASCII - Other Representations

What if we made it so that 65 = ‘A’, 66 = ‘B’, and so on?
For example: 72 73 33 = ‘HI!’, at least in one representation
What if we were using these numbers for colors? then 72 73 33 could be a color, in the form of how much of the following three colors we have: Red Green Blue = 72 Red, 73 Green, and 33 Blue, which gives us some weird yellow color overall. (For more practice, take a look at an RGB color palette online, they abound and are quite cool to play with)
The biggest number in decimal we could represent with one byte = eight bits of binary numbers, is going to be 255. There are 256 combinations of 0’s and 1’s, and one of those is the decimal number 0, so the highest number representable is 255. Check for yourself! What is 11111111 manually?

Abstraction

We don’t need to see what’s going on under the hood in order for things to work - we can use our computers without being computer scientists
We think of the concept of a shape (circle, square, triangle) abstractly
Computers are not intelligent - they only do what we ask of them (seems surprising!)
So we cannot tell the computer something in the abstract and have it actually follow what is going on
However, with more precision in our instructions, we can tell our computer exactly what we want
We must implement our abstract ideas in the computer in order for it to follow what we are doing, which we can think of as programming
This could be very tedious, writing down a complete list of every step each time we wanted something to work
Luckily, we can record these steps, and have them work the same way every time - in things like libraries - so that other programmers can use what we made
In this way, we abstract out the steps involved, so that when someone tells the computer to, for example, draw a circle, it knows exactly what we mean

Algorithms

A wonderful buzzword in the world of computer science - the algorithm
For example: how do we find a name in the phone book?
We could search through page by page - that’ll work! But a phone book is incredibly long! Hmm…
We could search through every other page, but what if we miss our name by a page? Well now we need to check in case we went to far
What if we divided the phone book in half, then checked the half where our name should be by dividing it in half and checking the half where our name should be and repeated until we found the name we were looking for? Eventually, if our name is in the book, we’ll find it, and in very few steps
We call this last algorithm by the name binary search
If we search in this last way through 16 things, we only need to check around 4 times! How about 32 things? Only around 5 checks! Even 1024 things means around 10 checks! That’s amazing! Just by checking using our intuitive algorithm

Pseudocode

pick up phone book
open to middle of the book
look at names on page
if Smith is in names on page
   call Mike
else if Smith is earlier in the book
   open to the middle of the left half of the book
   go to step 2
else if Smith is later in the book
   open to the middle of the right half of the book
  go to step 2

Why might this code not work?

What if Mike Smith is not in the book?

pick up phone book
open to middle of the book
look at names on page
if Smith is in names on page
   call Mike
else if Smith is earlier in the book
   open to the middle of the left half of the book
   go to step 2
else if Smith is later in the book
   open to the middle of the right half of the book
  go to step 2
else
  quit

In the above pseudocode, we have verbs telling us what to do - these are like commands in computer science - open, look, if, etc
We also check for truth - is in names is either true or false, is earlier in book is also either true or false. Can you find other truth-checks or boolean expressions in the above?
These plain English phrases can very easily be translated into actual code in a language like Python, C, Java, etc

Algorithmic Complexity

There is some relationship between the number of inputs to our algorithm and how long that algorithm takes to compute the answer
From our first answer, checking one page at a time, given n inputs, we would take n steps
Our second answer was a bit better, where for n pages in the book, or inputs, it would take us n / 2 steps to find it (at worst)
But our other algorithm, the better one we thought through, would only take log(n) steps to compute a solution given n inputs

Data in Memory

Computers don’t have physical phone books to search through though, so how do we use algorithms in computers?
What if we wanted to store 4 billion bytes of memory? That would be 4 Gigabytes, or 4Gb
If we wanted to store a number in a computer’s memory with 4Gb of total memory for us to use, we could store each byte in order
A set list of numbers in memory is something we would call an array or a list of numbers
The power of this storage mechanism - putting things down in order in some form of “grid,” is that we are able to access an arbitrary element in that grid in constant time - we can find the 4th element in the grid in one step. Similarly, we can find the 6 millionth element in the grid in one step.
The downside is that unlike us, a computer can only see one element at a time. Where we could look at a list of 10 elements and see immediately that there are 10 elements, but a computer needs to check each element individually and count up to 10

Finding 50

If I search a random list of numbers for 50, for example, then it might take me checking every element of the list in order to locate any one individual element!
What if we were to require that our lists were always sorted in numerical order?
Now we can check the list similarly to how we checked the phone book, check the middle, and then know where in general our number is located
The downside here is that we must sort the data at some point, which is a cost we will need to pay up front if we want to be able to efficiently search the list
Is there maybe an efficient way to sort lists, such that this cost is minimized?
Let’s say we have a random list of numbers, how could we sort such a list?
We could compare each number with the one next to it, and swap them if they’re not in order
We will need to repeat this over and over until our list is sorted though - what if we’ve sorted a list, and then add a very small number to the end? Sorting this way might take an extremely long time
This sorting algorithm is known as bubble sort
What’s a better way we could do this?
If I find the smallest element, and then swap it into its proper place, it seems faster, but in the worst case, it is just as bad as bubble sort
This algorithm is known as selection sort
In the above, what is a best case scenario? How about a worst case? Can you see how long it would take you to sort the list in the best and worst cases? (Now might be a good time to “play computer” and try sorting a list this way yourself)
All data up until this point has been continuous - back to back storage of data
This data structure is often known as an array
The problem here is, how do I insert a list into an array and keep the list sorted, or even just insert the element into the list at all? I could get more memory, and make a bigger array, but this isn’t efficient in memory - we need twice the space to copy over our original array.

Linked Lists

Now we know that computer’s memory could be shown as some form of “grid”, but what if we stored values in a way where they weren’t right next to one another
We could link these elements by telling each element where its neighbor is - the way we do this isn’t too important, it’s been abstracted away
Admittedly, in this storage, we cannot immediately hop to the last element in the memory, but here we can add elements without needing to worry about not having enough room
What does this mean for our algorithms?
No more binary search, can you see why?
Also, our ways of telling each element how to get to the next will take up some memory
Linked lists don’t need to be one big line though - what if we linked each element in memory to two children? We could make a tree, with its root at the top
This structure allows us to reimplement search algorithms, but at a cost to memory
The general trade-off seems to be that if we want to spend less time, we need to spend more space, and vice versa

Hash Tables

What about if we wanted a way to represent data such that we could look things up in constant time?
Could really be thought of, in many cases, as an array
Within the array, each entry points to a linked list
We could think of this as some form of hybrid between linked list and array
For example - with a size 26 array, we could put all possible English words into this data structure - but it may not be the best implementation, why?
Maybe we have uneven representations here - potentially not many entries start with ‘a’ or ‘z’, but almost all start with ‘n’, in which case we haven’t really improved much on our data structure

Bucketizing Cards

Imagine we have a deck of 52 cards and want to sort it
Maybe it would be easier if we split it by suit, into 4 groups, now we only have to sort 4 groups of 13 instead of 1 group of 52
We could do this bucketizing to something a bit more complex-sounding, such as numbers or names, using the intuitive method involved in this example

Summary

A lot of terms in computer science may sound scary or outright terrifying, but as seen in this last example, they don’t have to be
Using our intuitive understandings of things that we do in our every day lives - sorting cards, finding names in a phone book - we can understand computer science much better
This is just a matter of thinking like a computer scientist - computationally