Please enable JavaScript.

Coggle requires JavaScript to display documents.

CS Basics Review (CS50010 (Graphs (Graph storage, Complete Graph: m =…

- - - - GCD(a, b) { // here we assuming that a < b
        if (a == 0) return b;
        else return GCD(b mod a, a);
        }
      - By the Geometric progression: Sum_k=0->m (2^k) = 2^m - 1
  - - - {A union Complement(B)} union {B union Comp(A)}
      - {A-B} U {B-A}
    - - A U A = A
        A Intersect A = A
- - - - Using extern when you want to access function or variable from another C script.
      - Local variables are stored in the stack
      - Adding static when defining a local variable tells the compiler to preserve the value from function return to next function call (stored in data/bss)
      - Allocations
        
        Static duration
        
        Last the entire program run time, but need to know the size in the compile time.
        
        Automatic duration
        
        Only last runtime for a function call.
      - C Global variables are initialized to 0
      - Malloc
        
        Runtime memory allocation (heap)
        
        Allocation may fail if no space
        
        Returns null
      - calloc
        
        Allocate mem for an object of type
        
        calloc() calls malloc() and afterwards initializes allocated mem to 0.
      - realloc(oldblock, newsize)
        
        allocate
        
        Copy
        
        free
        
        return the pointer to the new block
      - <stdlib.h>
        
        free( ): a list of prior allocations made by malloc( ) and no longer in use.
        
        Automatic free( ) is also called the "garbage collection"
    - - Explicit and implicit memory allocation
        
        Explicit: all allocation and deallocation are done manually
        
        Implicit: automatic allocation and deallocation
      - Always check the return value from malloc( )
      - Forgot to free?
        
        Using swap space (super slow), and eventually fail.
      - Logical errors in using malloc
        
        Memory smashing
        
        Premature free
        
        Double free
        
        Wild free
      - Even if the free() error didn't crush instantly, it will cause the future free( ) or malloc ( ) crush.
      - Tools for memory allocation debugging
        
        IBM Rational Purify
        
        BoundsChecker
        
        Insure++
        
        Valgrind
        
        GDB
        
        ASan
    - - Union and Struct
        
        Union: only allow to access one variable inside (size is the largest one ceil (multiple of 8)
        
        Struct: can access multiple variables (size is the sum)
      - Head is called sentinel
        
        sl->head = NULL; is equivalent to (*sl).head = NULL;
      - typedef and #define
        
        typedef: defines any thing and give it an abbreviation
        
        typedef <something> <abbreviation>
        
        #define: define something in the pre-processor step, can be used to define almost any common values.
    - - Big-endian: naturally read from left to right, and storing the most BIG/Significant byte of the address first
      - Little-endian: processor or CPU likes this way to increase the incrementing or processing speed. A bit wired though: it reads from right to left, and stores the least/smallest byte in the address first.
    - - how to get hexdump of a structure data
      - memdump.c
  - - - *: Read the value at this address
        &: Return the address at this pointer
        To print pointer value: "0x%lx"
        To print pointer as an unsigned decimal: "%lud" or "%lu"
      - A pointer needs to be initialized by either pointing it to a variable of its type defined, or a malloc memory in heap.
        
        int a[10];
        int *p;
        p = &a[0]; // pointing to the address of a[0]
        p = p + 1 // this will add 4 bytes, because p is a ptr of integer
        // ,and thus the 1 will be multiplied by sizeof(int) = 4
        // before add into p.
      - Using pointer to increment array
        
        The following expressions are all the same
        
        a[i]
        
        *(a+i)
        
        *(&a[0] + i)
        
        *(int) ((char*)&a[0] + i * sizeof(int))
        
        Increment the address you are pointing to, and not the current address if you are using a ptr. (except when you are using an array address: *(&[0] + i))
      - The lifetime of variables local to a function is the time from function call to function return
        Do not have a function return a pointer to any of its local variables.
        
        This kind of issue/error is called dangling reference.
      - Pointer to a struct usage
        
        struct STUDENT s;
        s = &peter; // where peter is a STUDENT
        (s).name = "Jason";
        (*s).grade = 100;
        // the above two lines are the same as:
        // s->name = "Jason";
        // s->grade = 100; // which means -> can represent the pointed variables in the struct.
        
        Using typedef can save some steps of struct definition.
      - Union
        
        Union's size is the largest variable defined in the specific Union and ceiling to the nearest multiple of 4 or 32.
        
        Only on variable in Union can be defined, and all the other variables will take the same digit of bytes with different interpretation. (which is just like a converter)
  - - - Variate function
      - Thread
        
        static int i = 0
        main {
        if (something) {
        i++;
        }
        }
        
        Light weight process
        
        Allows you to run multi programs concurrently
        
        Difference between Process and Thread
        
        Instead of running one request at a time;
        Google using multi-thread to respond all in one time (parallel)
      - Local Variables are uninitialized; they will be whatever is on the stack when the function starts.
      - Static local variables are stored in data/BSS
      - realloc
        
        Runtime: O(1) [amortization]
      - calloc
        
        mallow with everything initialized to be 0
        
        Don't use it! Too slow.