Harvard CS50 Study Log（on going）

学习记录
10k 词

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.
    1. selection sort:
    2. bubble sort：
    3. insertion sort：
    4. merge 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)); // -- S

  • memory 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 Character

  • valgrind: 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 True

  • Python 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:
    printf("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: primary key & foreign key one-to-one

    -- 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

​

Lecture 8 HTML, CSS, JavaScript

Lecture 9 Flask

Lecture 10 Cybersecurity

Problem Set： https://cs50.harvard.edu/x/2024/psets/

*看此课程以温习basic coding和补充一些计算机思维，老师讲的很有激情，时间花的还算比较有价值