Link to Course: Link.

ROUGH NOTES (!)
Updated: 5/4/25

Week 0. Scratch.

What is Computer Science?

Computer Science is the study of information. How we represent it, and how we process it.

What is Problem Solving?

\[{ \text{Input} \to \blacksquare \to \text{Output}. }\]

Can we represent the inputs and outputs?

Eg: Consider counting, representing the number of people attending a class.

In unary notation (base ${ 1 }$),

\[{ (\overline{d _n \ldots d _0}) _1 := d _n \times 1 ^n + \ldots + d _0 \times 1 ^0 \quad (\text{each } d _i \in \lbrace 0, 1 \rbrace). }\]

Hence in unary notation, we count as

\[{ (0) _1, (1) _1, (11) _1 , (111) _1, \ldots }\]

How high can we count, using a single hand, in unary notation?

We can count from ${ (0) _1 }$ to ${ (11111) _1 . }$ That is, we can count from ${ 0 }$ to ${ 5 . }$

How high can we count, using a single hand?

We can count from ${ (0) _2 }$ to ${ (11111) _2 . }$ That is, we can count from ${ 0 }$ to ${ 31 . }$

In binary notation (base ${ 2 }$),

\[{ (\overline{d _n \ldots d _0}) _2 := d _n \times 2 ^n + \ldots + d _0 \times 2 ^0 \quad (\text{each } d _i \in \lbrace 0, 1 \rbrace). }\]

Hence in binary notation, we count as

\[{ (0) _2, (1) _2, (10) _2, (11) _2, (100) _2, \ldots }\]

Computers only understand or speak what alphabet, so to speak?

Computers only understand ${ 0 }$s and ${ 1 }$s.

What is a bit?

A bit is a binary digit, ${ b \in \lbrace 0 , 1 \rbrace . }$

Eg: We can think of a bit ${ 0 }$ as a light bulb / switch which is off.
We can think of a bit ${ 1 }$ as a light bulb / switch which is on.

How are bits represented in modern computers (PC, Phone, etc.)?

Inside PCs, Phones, etc. we have millions of tiny switches called transistors, that can be turned on or off.

We can use those transistors to store information.

Eg: How high can we count with ${ 3 }$ light bulbs / bits?

We can count from ${ (000) _2 }$ to ${ (111) _2 . }$

\[{ (000) _2. (001) _2, (010) _2, (011) _2, (100) _2, (101) _2, (110) _2, (111) _2 . }\]

Hence we can count from ${ 0 }$ to ${ 7 . }$

We are most comfortable with decimal notation (base ${ 10 }$). For eg, what is ${ 123 }$?

\[{ 123 = 100 + 20 + 3 = 1 \times 10 ^2 + 2 \times 10 ^1 + 3 \times 10 ^0 . }\]

What is a byte?

A byte is ${ 8 }$ bits.

How high can we count with ${ 1 }$ byte, that is ${ 8 }$ bits / light bulbs / switches?

We can count from ${ (00000000) _2 }$ to ${ (11111111) _2 . }$ That is, we can count from ${ 0 }$ to ${ 255 . }$

Note that Computers only contain or only use ${ 0 }$s and ${ 1 }$s.
Can we represent “A” inside of a computer?

We can use the ASCII representation.

${ A }$ is represented by the byte ${ (01000001) _2 . }$

That is, ${ A }$ is represented by the decimal number ${ 65 . }$

${ B }$ is represented by the decimal number ${ 66 , }$ and so on.

${ a }$ is represented by the decimal number ${ 97 . }$

${ b }$ is represented by the decimal number ${ 98 , }$ and so on.

Link to ASCII table: Link.

Eg: What do the three bytes

\[{ 01001000 \quad 01001001 \quad 00100001 }\]

represent in ASCII?

Each byte above represents a single character in ASCII. The three bytes represent

\[{ H \quad I \quad ! }\]

Can we represent other characters?

We can use ${ 8 }$ bits (${ 1 }$ byte) to represent English letters. We can use ASCII.

We can use ${ 32 }$ bits (${ 4 }$ bytes) to represent other characters. We can use Unicode.

Eg: The four bytes

\[{ 11110000100111111001100010000010 }\]

represents the emoji

\[{ 😂 }\]

Can we represent colours?

We can use the RGB system. We can use ${ 3 }$ bytes to represent the color of a pixel.

Eg: The three bytes

\[{ 72 \quad 73 \quad 33 }\]

intuitively represents the mixture

\[{ {\color{red}{\blacksquare}} - 72 \, (\text{of } 255) , \quad {\color{green}{\blacksquare}} - 73 \, (\text{of } 255), \quad {\color{blue}{\blacksquare}} - 33 \, (\text{of } 255) }\]

It represents the shade of yellow here.

Can we represent images?

An image is a collection of pixels of various colours.

Can we represent videos?

Note that a rapid sequence of images can be percieved as motion. For eg, flipbooks. For eg, ${ 24 }$ frames / images per second videos.

Can we represent sound?

We can represent the pitch, volume, and duration of sound by bytes.

What is an algorithm?

An algorithm is a precise description of how to do something.

Eg: Consider a Phonebook. Can we efficiently look up “John Harvard”?

We can search for “John Harvard” page by page.

We can go ahead by ${ 2 }$ pages each step, and go ahead by ${ 1 }$ page each step once we reach the ${ J }$ section.

We can use Binary Search.

Go to the middle of the phonebook. Ask: Is “John Harvard” to the left or the right? If it is to the left, throw away the right half, and vice versa. Repeat the process on the reduced phonebook.

For eg, say the phonebook has ${ 1000 }$ pages. In Binary Search, the problem size reduces as

\[{ 1000 \text{ pages} \rightsquigarrow 500 \text{ pages} \rightsquigarrow 250 \text{ pages} \rightsquigarrow \ldots }\]

Hence the algorithm takes roughly ${ \log _2 (n) }$ steps, where ${ n }$ is the number of pages.

The time to solve vs size of the problem graph for these algorithms: Link.

Pseudocode for Binary Search:

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 

Focus on the action words / verbs “${ \texttt{Pick up} }$”, “${ \texttt{Open to} }$”, “${ \texttt{Look at} }$”, “${ \texttt{Call} }$”.

These are functions. A function is an action / verb.

Focus on the words “${ \texttt{If} }$”, “${ \texttt{Else If} }$”, “${ \texttt{Else} }$”.

These are conditionals. They are proverbial forks in the road, where you choose which way to go based on a question.

Focus on the words

”${ \texttt{person is on page} }$”, “${ \texttt{person is earlier in book} }$”, “${ \texttt{person is later in book} }$”.

These are questions fed to conditionals. They have a Yes / No answer to them. They are called Boolean expressions.

Focus on the words “${ \texttt{Go back to} }$”.

They are loops. They are used to create cycles in a program.

Can we build intelligent programs? Can we build a chatbot which answers questions and has a conversation with the user?

Eg: A naive example psuedocode for a chatbot:

If student says hello
    Say hello 
Else if student says goodbye 
    Say goodbye 
Else if student asks how you are 
    Say well 
....

We can’t rely on having a long list of conditionals. There is an infinite number of things the user can ask the chatbot.

Can we implement a chatbot?

We can train it based on lots of data (Eg Wikipedia, Internet forums, etc.). We can let it figure out what it should say, the most statistically likely answer to question asked, in response to a certain question.

We can use large language models (LLMs).

LLMs are implemented using neural networks, inspired by biology.

CS50 LLM (for rubber duck debugging): Link.

We can program in Scratch.

Coordinate System in Scratch: Link.

Hello World in Scratch: Link.

Hello Name in Scratch: Link, Link, Link.

Meow in Scratch: Link, Link (scaleable code), Link (modular code, defining meow function), Link.

Meow on touching in Scratch: Link, Link.

Oscartime versions: Link.

Ivy’s hardest game versions: Link.