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
0 pick up phone book
1 open to middle of the book
2 look at names on page
3 if Smith is in names on page
4 call Mike
5 else if Smith is earlier in the book
6 open to the middle of the left half of the book
7 go to step 2
8 else if Smith is later in the book
9 open to the middle of the right half of the book
10 go to step 2

 Why might this code not work?

 What if Mike Smith is not in the book?
 0 pick up phone book
 1 open to middle of the book
 2 look at names on page
 3 if Smith is in names on page
 4 call Mike
 5 else if Smith is earlier in the book
 6 open to the middle of the left half of the book
 7 go to step 2
  8 else if Smith is later in the book
 9 open to the middle of the right half of the book
 10 go to step 2
 11 else
 12 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