Lecture 0 Scratch
Lecture 1 C
Lecture 2 Arrays
Lecture 3 Algorithms
- Time Complexity is an important metric used to measure the relationship between the running time of an algorithm and the size of the input. It describes how the execution time of an algorithm increases as the input size grows. Time complexity helps us assess the efficiency of an algorithm under different problem sizes, allowing us to choose the most appropriate algorithm. Time complexity is usually expressed using Big
notation. - selection sort:
- bubble sort：
- insertion sort：
- merge sort：
- selection sort:
Lecture 4 Memory
This section basically start from the pixels which formed by RGB code, for example 0xFF0000(using hexadecimal or base16 — 0x) . Why hexadecimal ? Using binary, it takes 4 bits to represent 16 possibilities. Using hexadecimal, 4 bits -> one digit, that’s easier. So one byte, two of them, is a common unit of measurement.
Then it comes to the tool or variable commonly used in C language which is pointer. A pointer is an address.
int n = 50; printf("%i\n", n); // --50 printf("%p\n", &n); // -- some address //the following sytanx are slightly differrent! int *p = &n; // also int* p = &n; they are the same, to specify a data type printf("%p\n", p);// -- same address above printf("%i\n", *p);// *p: go there --50“&a” means the address of a, “*“ is a dereference operator, which allows you to take an address, and go to it.
By convention, pointers take up more space, they account for 8 bytes. 32-bit machine differs from 64-bit machine in the width of address bus, where 64-bit machine has larger memory.
Strings, arrays of char so to speak, live at some address. They are continuous in memory from left to right, with 1 byte from each other.
string s = "CS50!"; printf("%s\n",s);//--CS50! printf("%p\n",s);//--some address printf("%p\n",&s[0]);//--address same as above printf("%p\n",&s[1]);//--address above + 0x1 //technically string is not an actual datatype string s = "CS50!"; char* s = "CS50!"; //typedef char* string; !! //char* s = "CS50!"; "&" is not needed here because CLANG puts the address of the first char in the variable when a double quote shows up.s is technically a pointer, to find the beginning of the string.
pointer arithmetic: doing math on addresses
char *s = "CS50"; printf("%c\n", s[0]); // -- C printf("%c\n", s[1]); // -- S printf("%c\n", *s); // -- C printf("%c\n", *(s+1)); // -- Smemory allocate: FREE & MALLOC
| 特性 | 栈（Stack） | 堆（Heap） |
|---|---|---|
| 管理方式 | 自动（编译器/操作系统） | 手动（程序员malloc） |
| 分配速度 | 快（直接移动指针） | 慢（需要查找可用内存） |
| 生命周期 | 函数调用结束就释放 | 显式释放（free） |
| 大小限制 | 较小（几MB） | 较大（受系统内存限制） |
| 存储内容 | 局部变量、函数调用信息 | 动态分配的对象、大型数据 |
| 碎片问题 | 无 | 可能产生内存碎片 |
//program for string operating
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <cs50.h>
int main(void)
{
char *s = get_string("s: "); // fuction from cs50.h
char *t = malloc(strlen(s) + 1);
// malloc : memory allocate
// return the first address of the memory
if(t == NULL){
return 1;
}
// "NULL" no memory available
for(int i = 0, n = strlen(s); i<=n ; i++){
t[i] = s[i];
}
strcpy(t,s);// equivalent
if (strlen(t) > 0){
t[0] = toupper(t[0]);
}
printf("%s\n", s);
printf("%s\n", t);
free(t); //free the memory mallocated，always remember to free
return 0;
}
// Upper the first Charactervalgrind: prog that check memory mistake
garbage values
matter of scope “{ }” passing by reference
void swap( int* a , int* b){ int temp = *a; *a = *b; *b = temp }
File I/O
//program for file writing --phonebook #include <cs50.h> #include <stdio.h> #include <string.h> int main(void) { FILE *file = fopen("phonebook.csv", "a"); if (file == NULL){ return 1; } char *name = get_string("Name: "); char *number = get_string("Number: "); fprintf(file, "%s,%s\n,name,number"); fclose(file); }//program for file copy #include <stdio.h> #include <stdint.h> typedef uint8_t BYTE; int main(int argc, char *argv[]) // use command line { FILE *src = fopen(argv[1], "rb"); FILE *dst = fopen(argv[2], "wb"); BYTE b; while (fread(&b, sizeof(b), 1, src) != 0){ fwrite(&b, sizeof(b), 1, dst); } fclose(dst); fclose(src); }
Lecture 5 Data Structures
abstract data types
queues: FIFO (enqueue & dequeue)
stacks: LIFO (like email systems, push & pop)
//prog for dynamic memory allocate without linked list #include <stdio.h> #include <stdlib.h> int main(void) { int *list = malloc(3 * sizeof(int)); if (list == NULL){ return 1; } // if more space is needed to be allocated dynamicly int *tmp = malloc(4 * sizeof(int)); if (tmp == NULL){ // free the original memory free(list); return 1; } for (int i = 0; i < 3; i++){ tmp[i] = list[i]; } tmp[3] = 4; // free the original memory free(list); // reorientation list = tmp; }
linked list
//template typedef struct node { int number; struct node *next; } node; //create a linked list with one node node *list = NULL; node *n = malloc(sizeof(node)); n -> number = 1; //(*n).number = 1; n -> next = NULL; list = n;// enter a linked list and print #include <stdio.h> #include <stdlib.h> typedef struct node{ int number; struct node *next; } node; int main (int argc, char *argv[]) { node *list = NULL; for (int i = 1; i < argc; i++){ int number = atoi(argv[i]); node *n = malloc(sizeof(node)); if(n == NULL){ //Free memory thus far return 1; } n->number = number; n->next = list; list = n; } //print whole list node *ptr = list; while (ptr != NULL){ printf("%i\n",ptr->number); ptr = ptr->next; } }
adding nodes：
searching nodes：
// enter a reverse linked list and print #include <stdio.h> #include <stdlib.h> typedef struct node{ int number; struct node *next; } node; int main (int argc, char *argv[]) { node *list = NULL; for (int i = 1; i < argc; i++){ int number = atoi(argv[i]); node *n = malloc(sizeof(node)); if(n == NULL){ //Free memory thus far return 1; } n->number = number; n->next = NULL; //if list is empty if (list == NULL ){ list = n; } else{ for (node *ptr = list; ptr != NULL ; ptr = ptr->next){ if(ptr->next == NULL){ ptr->next = n; break; } } } } //print whole list node *ptr = list; while (ptr != NULL){ printf("%i\n",ptr->number); ptr = ptr->next; } }adding nodes：
// enter a sequenced linked list #include <stdio.h> #include <stdlib.h> typedef struct node{ int number; struct node *next; } node; int main (int argc, char *argv[]) { node *list = NULL; for (int i = 1; i < argc; i++){ int number = atoi(argv[i]); node *n = malloc(sizeof(node)); if(n == NULL){ //Free memory thus far return 1; } n->number = number; n->next = NULL; //if list is empty if (list == NULL ){ list = n; } // if number belongs at beginning of the list else if (n->number < list->number){ n->next = list; list = n; } // if number belongs later of the list else{ for (node *ptr = list; ptr != NULL ; ptr = ptr->next){ // at end if(ptr->next == NULL){ ptr->next = n; break; } //in middle if (n->number < ptr->next->number){ n->next = ptr->next; ptr->next = n; break; } } } } //print whole list node *ptr = list; while (ptr != NULL){ printf("%i\n",ptr->number); ptr = ptr->next; } }adding nodes：
trees
binary search trees
typedef struct node{ int number; struct node *left; struct node *right; } node;
searching nodes：
dictionaries
hashing : mapping objects into finite number of outputs
hashing function
hash tables: array of linked lists
collision expectation
tries: a tree of arrays
Lecture 6 Python & Artificial Intelligence
Python manages your memory automatically. It may take more memory than C.
# python version of hash table in Problem set 5 words = set() def check(word): return word.lower() in words def load(dictionary): with open(dictionary) as file: words.update(file.read().splitlines()) return True def size(): return len(words) def unload(); return TruePython has greater ecosystem for developers, basically more libs. Example: Face detection
common IO syntax, you don’t have to specify the type of your variables
answer = input("input:") print("output, " + answer) print("output,", answer) print(f"output,{answer}") #type: bool float int str list set ...intent matters
object oriented program(OOP):
s = input("opinion: ") s = s.lower() # s = input("opinion: ").lower() if s in ["y","yes"]: print("agreed", end = "") elif s in ["n","no"]: print("not agreed") #loop for _ in range(3): print("test") #function exception def get_int(prompt): while True: try: return int(input(prompt)) except ValueError: print("not an integer") #for loop can end with an else people = [ {"name":"carter1","number":"+1-555-986-1004"} {"name":"carter2","number":"+1-555-986-1004"} {"name":"carter3","number":"+1-555-986-1004"} ] name = input("Name: ") for person in people: if person["name"] == name: number = person["number"] print(f"Found {number}") break else: print("Not found")
- the Artificial Intelligence part is more “introductory” and basic for learning
- prompt engineering
- minimax behavior
- machine learning
- reinforce learning (in robotics)
- explore vs exploit.
- deep learning
- generative artificial intelligence(large language models\transformer\attention values)
Lecture 7 SQL
SQL: a database-centric language (Structured Query Language)
flat file database example: csv
#csv example import csv with open("favorites.csv","r") as file: reader = csv.DictReader(file) counts = {} for row in reader: favorite = row["language"] if favorite in counts: counts[favorite] += 1 else: counts[favorite] = 1 for favorite in sorted(counts, key = counts.get): print(f"{favorite}: {counts[favorite]}")relational database: CRUD(create read update delete || insert drop)
this lecture uses sqlite3, for mobile database.
$ sqlite3 favorites.db sqlite> .mode csv sqlite> .import favorites.csv favorites --import csv to table sqlite> .quit sqlite> .schema --a sqlite command that shows the schema of the database sqlite> SELECT * FROM favorites; --show entire content of the table sqlite> SELECT language FROM favorites LIMIT 10; --show seletced content of the table sqlite> SELECT COUNT(*) FROM favorites; --total count sqlite> SELECT COUNT(DISTINCT(language)) FROM favorites; --type count sqlite> SELECT COUNT(*) FROM favorites WHERE language = 'C'; sqlite> SELECT COUNT(*) FROM favorites WHERE language = 'C' AND problem = 'Hello, World'; sqlite> SELECT language, COUNT(*) FROM favorites GROUP BY language; --works as python code above sqlite> INSERT INTO favotites(language, problem) VALUES('SQL', 'fiftyville'); --appending a new row to table sqlite> DELETE FROM favorites WHERE Timestamp IS NULL;--delete row sqlite> UPDATE favorites SET language = 'SQL', problem = 'fiftyville';--update and now all content has been changed which can be justified by WHERE...(condition)link different tables together one-to-one: primary key & foreign key
-- IMDb example sqlite> SELECT * FROM shows WHERE id IN ...>(SELECT show_id FROM ratings WHERE rating >= 6.0)how to join two tables that have related keys?
-- syntax 'JOIN' sqlite> SELECT * FROM shows JOIN ratings ON shows.id = ratings.show_id WHERE rating>= 6.0 LIMIT 10;
link different tables together: one-to-many ，many-to-many
just nested snytax.
- SQL injection attack just use placeholders and sanitize customer’s inputs
Lecture 8 HTML, CSS, JavaScript
routes & packets；a pair of protocols: TCP/IP
IPv4: #.#.#.# (0~255) 32 bits
TCP: use sequence numbers to help servers multiplex, port numbers (80: HTTP 443: HTTPS)
DNS (domain name system) servers
domain name -> IP address
buy a domain name: pay someone(运营商) to associate an IP address with your domain name
DHCP (dynamic host configuration protocol) 自动为设备分配地址
HTTP (hypertext transmit protocol) HTTPS (hypertext transmit protocol secure) Internet protocol that allows a web browser to request and receive information from a web server
HTML: (hypertext marker language) a really easy language that you can learn in 30 minutes. VSCode makes it even more convenient. but it can take a lot of effort to make good websites.
tags & attributes:
<!DOCTYPE html> <html lang="en"> <!--html: tag lang = "en": attributes --> <head> <title> title </title> </head> <body> body </body> </html>regular expressions: 正则表达式 https://developer.mozilla.org/en-US/docs/Web/JavaScript/Guide/Regular_expressions
you can change your local copy of html by using developer tools
CSS: (Cascading Style Sheets)
properties: example
<!DOCTYPE html> <html lang="en"> <head> <title>title</title> </head> <body style = "text-align: center"> <p style = "font-size: large"> John Harvard </p> <p style = "font-size: medium"> Welcome to my homepage </p> <p style = "font-size: small"> Copyright © John Harvard </p> </body> </html>
classes: your own style or style from third libraries
<!DOCTYPE html> <html lang="en"> <head> <style> .centered{ text-align: center; } .large{ font-size: large; } .medium{ font-size: medium; } .small{ font-size: small; } </style> <title>title</title> </head> <body class = "centered"> <head class = "large"> John Harvard </head> <main class = "medium"> Welcome to my homepage </main> <footer class = "small"> Copyright © John Harvard </footer> </body> </html>
样式可使用外链
#+… : ID
- JavaScript
Lecture 9 Flask
flask
a python third party library for web microframework linking static(html) & dynamic(python) files. We use the syntax “JINJA” to customize and formalize the outlook of the web. Following the lecture I made a simple web application to greet users, the GitHub link is https://github.com/miustannis/flask-greeting-web.git
cookies
tools that websites use to keep staying stateful. Server needs to remember something about the user, cookies will be sent back to server by browsers every time a user log in.
problems: cookies may be used for ads and tracking.
Lecture 10 Cybersecurity
passwords
brute-force attack
two-factor authentication (mostly hardware equipment)
one-time passwords
server uses hash function to compare passwords
cryptography: public key & private key (HTTPS)
passkeys: generate public key and send it to the company, and a private one for verifying your signature combining the public key.
secure deletion -> full disk encryption
*看此课程以温习basic coding和补充一些计算机思维，老师讲的很有激情，时间花的还算比较有价值
______
| see you |
======
\
\
\
\
/ \\ //\\
|\\___/| / \\// \\\\
/0 0 \\__ / // | \\ \\
/ / \\/_/ // | \\ \\
\@_^_\@'/ \\/_ // | \\ \\
//_^_/ \\/_ // | \\ \\
( //) | \\/// | \\ \\
( / /) _|_ / ) // | \\ _\\
( // /) '/,_ _ _/ ( ; -. | _ _\\.-~ .-~~~^-.
(( / / )) ,-{ _ `-.|.-~-. .~ `.
(( // / )) '/\\ / ~-. _ .-~ .-~^-. \\
(( /// )) `. { } / \\ \\
(( / )) .----~-.\\ \\-' .~ \\ `. \\^-.
///.----..> \\ _ -~ `. ^-` ^-_
///-._ _ _ _ _ _ _}^ - - - - ~ ~-- ,.-~
/.-~