My notes for Harvard's CS50

week0.md

Lecture 0 - Scratch

What is computer science - problem solving

Ten digits - Human
0 1 2 3 4 5 6 7 8 9

Two digits - Computer
0 1

bits = binary + digits

Physical input of computer is electricity

100	10	1
1	2	3

100x1	10x2	1x3
100	20	3

10^2	10^1	10^0
#	#	#	human world

2^2	2^1	2^0
#	#	#	binary system
4	2	1

binary	decimal
001	1
010	2
011	3
100	4
101	5
110	6
111	7
110010	50

Computers only compute

A	character
65	decimal
01000001	binary

ASCII
character	H	I	!
decimal	72	73	33
binary	01001000	01001001	00100001

1 bytes = 8 bits

How many symbols can you represent with 8 bits?
256 = 2x2x2x2x2x2x2x2

Unicode
An example emoji = 128514(decimal)

RGB
red	green	blue	photoshoot, images
72	73	33	decimal

algorithms - step by step computer gets what you want
bug - mistake in problem or algorithm

third algorithm - faster, more efficient

Pseudocode

    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* 

• functions
• conditions
• Boolean expressions
• loops
• variables
• threads
• events
• ...

Actual code

#include<stdio.h>
int main(void)
{
  printf("hello, world\n");
}

week1.md

Lecture 1 - C

Good software/code has

• correctness
• design(well-designed)
• style(readable)

ide.cs50.io

source code --> complier --> machine code

hello.c - file

recompile code
make hello - comment
./hello - comment

arguments --> functions --> return value

side effects
return values, variables

library - code written by someone else

header files

types	size
bool	1 byte
char	1 byte
double	8 bytes
float	4 bytes
int	4 bytes
long	8 bytes
string	? byte
...

operators

• addition(+)
• substraction(-)
• multiplication(x)
• division(/)
• modulus(%)

variables
conditions
abstraction

finite bits
infinite precision

help50
style50
check50

week2.md

Lecture 2 - Arrays

Source code to machine code, these steps work:

• preprocessing
• compiling
• assembling
• linking

printf
debug50

some C libraries:

• <stdio.h>
• <cs50.h>
• <string.h>
• <ctype.h>

char c1 = 'H';  
char c2 = 'I';  
char c3 = '!';  

string s = "HI!";  

string is array of chars

\0 is the stop sign, end of string

string s = get_string("Input: ");  

for(int i = 0; s[i] != '\0'; i++)  
{  
}  

for(int i = 0; i < strlen(s); i++)  
...
// Avoid to call strlen() again and again, it calls one time  

for(int i = 0, n = strlen(s); i < n; i++)  
{  
}  

string words[2];  
words[0] = "HI!";  
words[1] = "BYE!";  

Writing ASCII code in programming code is not friendly for human-reading

manual.cs50.io

key + plaintext --> cipher --> ciphertext

Characters	I	L	O	V	E	Y	O	U
Decimal	73	76	79	86	69	89	79	85
Characters	J	M	P	W	F	Z	P	V
Decimal	74	77	80	87	70	90	80	86

week3.md

Lecture 3 - Algorithms

In computer science, an algorithm is set of instructions for solving some problem, step by step

Big-O-Notation

Linear Search

Looking phone book, page by page(Week 0 issue)

For i from 0 to n-1  
    If number behind i'th door  
        Return true  
Return false  

Binary Search

For binary search, the data need to be sorted

If no doors  
  Return false  
If number behind middle door  
  Return true  
Else if number < middle door  
  Search left half  
Else if number > middle door  
  Search right half  

// Compare two strings  
strcmp((string,string)=0)  

Sorting Algorithms

• Insertion Sort
• Selection Sort
• Bubble Sort
• Quick Sort
• Merge Sort
• Shell Sort

Selection Sort

Select one and compare it with others, and do this again and again
n + (n - 1) + (n - 2) + (n - 3) + ...

For i from 0 to n - 1  
  Find smallest item between i'th item and last item  
  Swap smallest item with i'th item  

Bubble Sort

Select a pair in array, compare them and if they are in order, swap them. Else do nothing. And do this again and again
(n - 1) x (n - 1)

Repeat (n - 1) times  
  For i from  to n - 2  
    If i'th and i + 1'th elements out of order  
      Swap them  
    If no swaps  
      Quit  

Recursion
Better design, better efficiency

Merge Sort

If only one number  
  Quit  
Else  
  Sort left half of numbers  
  Sort right half of numbers  
  Merge sorted halves  

Code in else statement is the recursive case

Brian did n things in log(n) times

Almost always, when you do something better in code or solve the problem more intelligently, you have to pay price. Maybe you spend more time is the human writing code because of harder in took more specification, that is the cost. Maybe actually more space is needed.
Selecting sort algorithm depends what you care about, what you optimize for. Sometimes money (by using slower code, you don't need twices much server), your time, computer time, other.

Upper bound
O(n^2)	selection sort, bubble sort
O(nlog(n))	merge sort
O(n)	linear search
O(log(n))	binary search
O(1)

Lower bound
Ω(n^2)	selection sort
Ω(nlog(n))	merge sort
Ω(n)	bubble sort
Ω(log(n))
Ω(1)	linear search, binary search

Compare both bound
θ(n^2)	selection sort
θ(nlog(n))	merge sort
θ(n)
θ(log(n))
θ(1)

week4.md

Lecture 4 - Memory

Hexadecimal digits
0123456789ABCDEF

16^1	16^0
#	#

One hexadecimal digit happens to be equivalent to four binary digits

Binary	Hexadecimal
11111111	FF
128+64+32+16+8+4+2+1 = 255	16x15+1x15 = 255

#000000	black
#FFFFFF	white
#FF0000	red
#00FF00	green
#0000FF	blue

pointers - 8 bits

int n = 50; 
int *p = &n; 

string s = "HI!"; 

s is address of first character
s is in higher level as string, in lower level as address of string

In any functions, your computer will automatically store any of local variables or promoters from those functions down here(stack)

heap overflow
stack overflow - calling a function so many times that it overflows the heap. There is no fundamental solution other than don't do that, don't use too much memory. Design your algorithms, choose your inputs in a such way that there just isn't that risk. Just because you can design something a little more elegantly doesn't necessarily mean that it's always going to work for you
buffer overflow - it is when you allocate on array and go too far past the end of it

file I/O
With very high probability, you can determine if any file is a jpeg by looking only at its first three bytes. A lot of file formats have what are called magic numbers at the beginning of their files. And these are industry standard numbers, 1 or 2 or 3 or more of them, that is just commonly expected to be at the beginning of a file

week5.md

Lecture 5 - Data Structures

Array
It is just a contiguous sequence of memory in which you can store a whole bunch of integers back to back to back, or maybe a whole bunch of chars back to back to back to back

Running time of inserting into an array - O(n)
Lower bound of inserting into an array - Ω(1)

Linked lists
It is a data structure that's more dynamic, whereby you can grow and shrink the data structure without having to touch all of the original data and move it from old location to new

Linked list as a collection of nodes that are connected via pointers

Storing all of these addresses cause a kind of a waste of memory.That is the price, trade off

Running time of searching a linked list - O(n)
Running time of inserting into a linked list - O(1)

Trees
Binary search trees

Running time of inserting into a binary search tree - O(log(n))

Hash tables
It is another data structure that's essentially an array of linked list

Running time of searching a hash table - O(n)

Tries
Trie is actually a tree made up of arrays. A trie is a tree, each of whose nodes is an array

Running time of searching a trie - O(1)

Price - spent a huge number bits, or bytes

Abstract Data Structures
It is kind of a mental structure that you can imagine, implemently some real world problem, typically that's implemented with some other data structure

Queues
It is a data structure that has certain properties. First in first out, FIFO
enqueue - add, insert
dequeue - remove, delete

Stacks
Last in first out, LIFO
push - add, insert
pop - remove, delete

Dictionaries
It is an abstract data type, which means you can implement it with arrays or linked lists, or hash tables, or tries, or whatever else, an abstract data type that allows you associate keys with values

week6.md

Lecture 6 - Phyton

No semicolumn at the end of line
No assigning data type
Indent your code by four spaces, or one tab correctly is necessary
More human-friendly to write

week7.md

Lecture 7 - SQL

Flat-file database
databases are really big files containing lots of data or special programs that are storing our data for us. Seperate data with commas, keep it simple.
are wonderfully useful when you just want to do quickly or when you want to download data from same third party like Google, in a standard, portable way.
aren't necessarily the best structure to use ultimately for longer data sets, because they don't really lend themselves to more efficient queries.

csv
Running time - O(n)

Relational database
are instead programs in which you store data. Those programs use a lot of RAM, memory. They keep it long term by storing your data also in files.
search, update, delete, insert

SQLite
It is a database that stays all of the data still in rows and columns. It does so using what we're going to call tables.

SQL, Structured Query Language, a new programmig language
SQLite is like a light version of SQL. It's a more user-friendly version. It's more portable.
The way SQLite works is that it stores all of your data in a binary file.
To interact with that binary file where in all of your data is stored, we need some kind of user-facing program. The standard are that comes with SQLite is called sqlite3, essentially version 3 of the tool.

Four basic operations support any relational database:
CREATE, INSERT
READ, SELECT
UPDATE
DELETE

PRIMARY KEY is the column in a table that uniqually identifies every row.

Two primary problems
SQl injection attacks, which you are vulnerable to in any application where race conditions, when you write code in a multiserver more fancily known as a multithreaded environment. Lines of code chronologically can get commingled on different servers at any given time. When you have to write code for like this, to use what are called transactions. Transactions essentially allow you to lock a table or, really, a row in the table. One action results in same code executing that's in the process of checking database, other action will not get handled by the server until first one is done executing.

week8-5.md

Lecture 8.5 - Security

Brute force attacks - means that if they don't know your password, they're not just going to try random numbers necessarily. They're just going to try all possible passwords.

4-digit passcode - 10000 possible passcodes (10 x 10 x 10 x 10)
4-letter passcode - 7311616 possible passcodes (52 x 52 x 52 x 52)(more time, more effort)
4-character passcode - 78074896 possible passcodes (94 x 94 x 94 x 94)
8-character passcode - 6095689385410816 possible passcodes (94 x 94 x 94 x 94 x 94 x 94 x 94 x 94)

two-factor authentication - password + eye, hand, face or etc.
end-to-end-encryption - in third-party service you're not just encryptily your traffic between you and third-party. You are encryptry your data between you and the person you're talking to.

week8.md

Lecture 8 - HTML, CSS, JavaScript

IP - simply standardizes how computers address each other
DNS - domain name system, this is a technology that's deployed throughout the internet that just translates what you would typically call fully qualified domain names, from those English-like or human readable characters to the corrasponding IP addresses
TCP - port number is an unique number of request for chat, e-mail, or web
HTTP - a standardized word, command (GET, POST)

.com, .net - top level of domain name , type of domain

HTML - tells the browser what you displayed and how
CSS - stylize the page
JS - write code, save on the server, but run it on user's computer

week9.md

Lecture 9 - Flask

It is a library for doing somethings in a web application
Cookie are essentially pieces of data or even files that are planted on your computer or your phone by a server that help them remember that you've been there before