Viren Bhagat

My Notes: Computational Thinking (CS50)


In order to become a developer, I've decided to go through the Introduction to Computer Science lectures (known as CS50, through Harvard Online). Here are the notes I've taken from lecture 0, I hope someone finds some use in them. All relevant links and sources will be posted below.

What is Computer Science? Per Wikipedia, "Computer science is the study of processes that interact with data and that can be represented as data in the form of programs." To me, its use is to solve problems. We have input, we need output. Computer Science takes your input and creates output through various processes and methods.

Computers..they're all 0s and 1s. A very common phrase, but true. What exactly does this mean though? There are many parts to a computer, but I think of transistors and either being on and off, at the simplest, it could be represented by 2 values (1 or 0). Binary numbers are part of the base 2 numeral system. IRL, we use denary numbers (base 10), 0-9. (I'll link some better resources to understand binary numbers and how to count).

bit: A binary digit (0 or 1)

byte: A group of 8 bits

Binary (Base 2): 0, 1

Denary (Base 10): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

Hex (Base 16): 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F

How can these 0s and 1s represent letters and other characters though? ASCII (American Standard Code for Information Interchange). ASCII is an American standard for character encoding. As different countries have different languages and characters, this is American based (hence the A). For more characters and things like emojis, there is Unicode (think a super set of ASCII). When you think of the laughing crying face emoji, you see a lot of yellow (along with the tears). The image is just a lot of yellow dots. That is represented by a RGB hexadecimal (mixes red, green, blue to make any color). When you think about photos, GIFs, or videos...they are just a lot of pixels. GIFs and videos are essentially frames of photos.

Binary -> Digits -> Text / Image

Even for music...there is notes, volume, duration. That can all be turned into digits for the computer to process.

Essentially, all media and infomration can be broken down into 0s and 1s.

Next big important topic..Algorithms! An algorithm is a step by step instruction to solve a problem.

Here is a common problem we might have experience before. Searching for a name in a phone book. What is the best way? (Best meaning most efficient, quickest). Say you're looking up John Smith.

  1. Flip page by page (phone books are pretty big so yeah, many pages to flip through).
  2. Flip 2 pages at a time (would be quicker but theres a chance you may skip over the contact you need).
  3. Start in the middle of the book. You're looking for S for Smith. If you've gone past S, go to the left, and halve it again. If not, halve the right. This would be the best way of searching.

The first method would be time n. The second method would be time n/2. The third method would be log n.

Algorithm graph

When creating algorithms, one must thing of the resources (time and memory being used up).

Psuedocode is another important concept for programmers. You will most likely work with a few different languages with different syntaxes. Some are stricter than others but psuedocode will always be there to help you. It is helpful to write out what you want your code to do in plain English first. Going back to the phonebook example..

  1. Pick up phone book
  2. Open to middle of phone book
  3. Look at page
  4. If Smith is on page

    1. Call Mike
  5. Else if Smith is earlier in book

    1. Open to middle of left half of book
    2. Go back to line 3
  6. Else if Smith is later in book

    1. Open to middle of right half of book
    2. Go back to line 3
  7. Else

    1. Quit

These are the directions on how to search most efficiently for Smith in the phone book.

To translate to code, the verbs would be functions (bolded). The conditionals are italicized (if / else). The booleans (true or false) are underlined. The loops are the "go back" instruction.

The rest of the lecture involved a languaged called Scratch, a block based visual programming language. It is important but I did not take notes on it. I would recommend watching the lecture for this.

Resources, Sources, & Useful Links

Lecture (on YouTube)

CS50 Course on edX

Bits, Bytes, Building with Binary (BaseCS) Blog

Bits, Bytes, Building with Binary (BaseCS) Podcast

computer science, cs50, notes, #LearnInPublic