Link to Course: Link.
ROUGH NOTES (!)
Updated: 1/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?
A rapid sequence of images is percieved as motion. 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