1 byte = 1111 1111 = 0x12 1 int32 = 0x00 0x00 0x00 0x00 = 4 byte = 0x12345678 1 char = 0x01 = 1 byte 1 short = 0x01 0x02 = 2 byte 1 long = 0x01 0x02 0x03 0x04 0x05 0x06 0x07 0x08 = 8 byte
int* p;
- pointer p is not initialized (different from NULL)
int* p = NULL;
- pointer p is NULL
int** p = alloc(int*);
- pointer *p is NULL since default value of a pointer is NULL
Arrays
int[] A;
A is uninitialized
A[0];
A[0] is uninitialized
Allocating a struct
field array: initialized to uninitialized
int: 0
string: ""
any pointer: NULL
Exam Tips:
think pointers as physical address
alloc() will give a new address with its component initialized to default value
Exam Tips:
always repeat contracts of loops to show condition with negation after the loop finishes
you can point to inside loop, but you can't reason over multiple
when checking init: you have to make sure you don't use the equality in the for loop because it isn't checked when the loop initializes.
The integer quantity ____ strictly decrease because during an arbitary iteration of the loop, ____ gets strictly larger/smaller. Since the loop terminates if the quantity reaches 0 or less, and this quantity is strictly decreasing, the loop must terminate.
Contracts:
requires
ensures
data structure invariant: (used only in implementation)
Exam Tips:
don't assume _t
to be pointer
check NULL before doing anything else
TODO: contracts for basic operations
Exam Tips:
copy stack and queue use tmp
recursion
Best case complexity
Linear search O(1)
Binary search O(1)
Selection Sorting | Merge Sort | Quick Sort | |
---|---|---|---|
Worst Case | n^2 | n log(n) | n^2 |
Average Case | n^2 | n log(n) | n log(n) |
Best Case | n^2 | n log(n) | n log(n) |
In-Place | Y | N | Y (can be) |
Stable | N | Y | Y |
stable: whether sort among 2 dimension produce the same outcome
Exam Tips:
no search algorithm can be better than O(log(n))
no sort algorithm can be better than O(nlog(n))
best/worst case example: sorted backward, everything the same value, sorted forward, value does not exist
O(1)<O(log(log(n)))<O(log(n))<O(log(n)^2)<O(n)<O(n*log(n))<O(n^2)<O(2^n)<O(n!)
change of log base does not matter
(A outrun B, A outpace B, means A is slower)
because max(x,y) <= x+y <= 2max(x,y), then O(max(x,y)) <= O(x+y) <= O(max(x,y)). So we just write O(x+y)
Exam Tip: write O(x) in terms of the actual variable
leftshift: << k = *2^k*
rightshift: >> k = /2^k
(exception shifting don't round down to zero, we round down to negative infinity.)
Exam Tips:
computers are 32 bits. 0xF = 1111 but there are 0s before. Therefore 0xF << 2 will not produce 1100, it will be 111100
-x = ~x+1
overflow: check int_max(), int_min()
division: dividing / mod by 0, int_min()/-1
shifting: 32bits, copying
division: rounding
int_min = -2^(k-1) = 1 and all zeros
int_max = 2^(k-1)-1 = 0 and all ones
-1 will be all ones
-int_min = int_min
-int_max() = as expected = int_min + 1
(x/y)*y+(x%y)=x to hold, round down to 0
Solving represent positive and negative
// de-referencing *p //@requires p!=NULL; (you can only use NULL for pointers, not other data type)
alloc(p) //@ensures \result != NULL;
ptr->field //@requires ptr!=NULL; (checked by compiler)
In question 1 (Counting sort), just before the code for the function running_sums, the explanation line in the segment B[0,j). should have been in the segment B[0,j+1).
Don't Do:
alloc(void)
de-reference void*
casting void to void
\hastag(a, b) b must be void. a tag can never be void.
\hastag(a, b) a must not be void*, otherwise compiler error.
Do:
Casting to void gives the tag. If the value if NULL, it has all the tags. Therefore, you can do int* i = NULL; void* q = (void*) i; string s = (string*) q;
, but you cannot do string* s = (string*) i;
You cannot cast one type to the other without going though void. Casting between two different types must go through void*.
typedef int hash_fn(string s); hashing_fn* F = &key_hash;
ALWAYS PUT () around when accessing function pointer You have to establish the function pointer first using correct type then convert
Interface:
dummy node: start note + end_dummy (used in chain array)
NULL node: last point to node (used in dictionary)
doubly linked
Insert: O(1), add in front Remove: O(1), remove from end Access: O(n)
TODO cost, amortize,
capacity: m (bucket) size: n (elements) load factor: n/m (average length) Hash Function: minimize collision
Insert: check for duplicates
if allow for duplicate O(1)
if not: worst O(n), average O(n/m)=O(1), average-insert-amortized-resize O(1)
open addressing: using auto-resize array, always mod array length.
quadratic probing: try index +1, +4, and +9... from the hash (produce cycle)
Interface:
entry_key() give entry, convert to key
key_hash() key to hash
key_equiv() compare 2 key, true false
Invariant:
Invariant:
(all data) in left child < parent < all data in right child (no dupe, same as BST) - but no local check
child height differ at most 1
Insert:
insert follow BST O(log(n))
rotate O(1)
each type of rotation only cost O(1)
at most 1 (double) rotation for each insertion
you should fix the bottom violation first
Deletion: same as insertion
Interface:
has_higher_priority_fr() give e1 >(strictly) e2
next: point to next unfilled element
limit: size + 1 (IMPORTANT)
Invariant:
fill top down, left right
parents have higher or equal priority (heap allows duplicates, therefore not BST)
Access:
left child: 2i
right child: 2i+1
parent i/2
pq_add: swap up (sift up) pq_rem: replace with the last element, swap with higher priority child (sift down)
Make sure castings are aligned: otherwise out-of-bound or undefined behavior two pointer with different type can be equal since pointers only store address, without element size.
int E[8]
allocates on the stack. You still need to initialize it!
int F[] = {2, 4, 6, 8, 10}
They still have type int*
struct point p;
p.x = 9;
p.y = 7;
&
operation can get address of
functions
local variables
fields of structs
array elements
You cannot do:
&(int+2): since i+2=7 is not legal
&(A+3): since A+3 = xcalloc() is not legal
&&i: &i = xmalloc() is not legal
char* s1 = "hello";
it is an char pointer (or char array if you like)
\0
whose value is 0)strlen: counts up to NUL, not included
strcpy(dst, src): copy up to NUL included
char *s1 = "hello"
as TEXT segment
read-only: otherwise undefined
no need to free: undefined
if they have the same contents, then the pointers will be the same (maybe for some compilers)
initialized on string literals
char *s2 = xcalloc(sizeof(char), strlen(char) + 1)
as HEAP
remember to allocate NUL termination
need to free it
char s3[] = "world"; char s4[] = {'s', '\0'}; char s5[5]
as STACK
in stack
no need to free
when inside a struct char s4[2]
, it is in heap(the same place as struct as you free it), assignments to {'s', '\0'} is not allowed unless assign each index individually.
initialized either in string literals or other (https://www.diderot.one/courses/42/post-office/30196) String in C: https://www.youtube.com/watch?v=90gFFdzuZMw&ab_channel=EngineerMan
Other undefined: (can be used to do security hacks)
shifting by 0 <= k && k<32
division / modulus by 0, INT_MIN by -1
freeing partial array? TODO
overflow of signed types only!
accessing array out-of-bound
de-referencing NULL
reading uninitialized memory (even if allocated)
using freed memory
double free
freeing memory not returned by malloc
writing to read-only
https://www.diderot.one/courses/42/post-office/30141 Freeing a casted non-void pointer is often undefined if they misaligned
due to misalignment of bytes
but free() on non-void-pointer have same representation regardless of type, so it is allowed.
Small unsigned -> larger unsigned: zero padding, value preserve Small signed -> larger signed: sign extend, value preserve Signed -> Unsigned -> Signed: preserve bit, value change when half used
Float: 32 bits Double: 64 bits Calculation rounding error depend on compiler
enum season {WINTER, SPRING, SUMMER, FALL};
emun season today = FALL;
if (today == WINTER) printf("snow!\n");
switch (today) {
case WINTER:
printf("snow!\n");
break;
default:
printf("other\n");
}
Union Type allow using the same space in different ways:
Edge: lines (e=[0, v(v-1)/2]) No Self-Edge: no (V, V) Neighbors: [0, min(v, e)]
Implicit graph: We don't need a graph data structure
it will be too big to graph all possibilities
we explore graph, we never build graph
Explicit graph: data structure in memory Cost: e \in O(v^2), but might be lower if we use e too.
Linked list of edges | Hash set of edges | Matrix | List | ||
---|---|---|---|---|---|
graph_hasedge | O(e) | O(1) avg+amt | O(1) | O(min(v,e)) | |
graph_addedge | O(1) | O(1) | O(1) | O(1) | |
graph_get_neighbors | O(e) | O(e) | O(v) | O(1) cuz grab | |
space | O(v^2) | O(v+e)\O(max(v,e)) |
Adj | Mat | |
---|---|---|
new | v+e | v^2 |
free | 1 | 1 |
size | v+e | v^2 |
hasedge | 1 | 1 |
addedge | min(v,e) | 1 |
get_neighbors | 1 | v |
hasmore_neighbors | 1 | 1 |
next_neighbor | 1 | 1 |
free_neighbors | 1 | min(v,e) |
DFS/BFS | v+e | min(v^2, ev) |
DFS/BFS Tree | v | ? |
Note: max(v, e) \leq v+e \leq 2\times max(v, e)
iterate neighbors: O(1)*O(min(v,e)) dense graph: e \in O(v^2) sparse graph: e \in O(v) \lor e \in O(vlog(v)) (we typically work with sparse graphs)
traversing
Cycle: a path from a vertex to itself
0-1-4-0
0-1-0
0
Simple Cycle: with at least one edge and without repeated edges
Start with a spanning forest of singleton trees and add edges from the graph as long as they don't form a cycles (def.B)
Initialize T with isolated vertices of G (O(1)=graph_new)
For each edge (u, v) in G: (O(e))
if connected(u, v): (O(v) where v=v_in_tree_so_far by DFS/BFS)
discard the edge
else:
add it to T (O(1))
stop once T has v-1 edges
costs O(ev)
- O(v^2) for sparse graphs
(it can create spanning forests) (Edge-Centric algorithm is greedy, DFS/BFS is not since they have worklist)
Start with a single vertex in the tree and add edges to vertices not in the tree (def.C)
(Complexity: O(e) as DFS/BFS)Minimum spanning tree: one with the least total weight of its edges.
total is O(ev)
sort is O(e log(e))
check if two point to the same representative (O(v))
merge representative, always have 2 choice (don't merge node) O(1)
stop once T has v-1 edges
store length in root as negative
merge shorter trees into taller trees
initialize array into "-1"s
A tree T of height h has at least 2^{h-1} vertices
A tree T with v vertices has height at most log(v)+1 (balanced tree = O(log v), for loop O(e), total O(eloge + elog v), assume sparse O(eloge))
adding/removing edges is O(log e) in priority queue
complexity O(e log e)
Math
2^(k-1) adds to get to worst case (flipping all bits)
i'th bit flips 2^(k-i-1) times, summing up 0<=i<=k, 2^k - 1 times total
cost: \frac{2^k-1}{2^k} = 2-2^{1-k}, as k goes to infinity, cost=O(2)
Token
TODO: casting print automatic TODO: https://www.rapidtables.com/convert/number/decimal-to-hex.html TODO: drawing pad
Tips:
when wonder, test it later!
read + annotate
try int_min, -1, 0, 1, int_max and some normal values
for coding section, if you see pointers, they are testing you casting stuff!
careful with shifting and byte
Table of Content