Exam Review

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

Exam Review 1

Pointers

• 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

Contracts

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.

Interface

Contracts:

• requires

  • when input pointer: check not NULL
  • when input int: check within bound
  • when modify input: input modification will not raise error

• ensures

  • when return pointer: check not NULL
  • when return struct pointer:

• data structure invariant: (used only in implementation)

  • use \length when you can
  • check bound
  • check not NULL
  • check if exists contradictions values

Exam Tips:

• don't assume _t to be pointer

• check NULL before doing anything else

TODO: contracts for basic operations

Stack and Queue

Exam Tips:

• copy stack and queue use tmp

• recursion

Searching and Sorting Complexity

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

  • best case may be O(1)

• no sort algorithm can be better than O(nlog(n))

  • best case may be O(n) in bubble sort

• best/worst case example: sorted backward, everything the same value, sorted forward, value does not exist

Big-O

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

Bit-wise

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

Integer

• 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

Pointer

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

WARNINGS

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

Exam Review 2

Void* Pointers

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:

• compare two address with void* type

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

Function Pointer

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

Data Structure

Linked List

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)

Auto Resize Array

TODO cost, amortize,

Dictionary & Hash Table

capacity: m (bucket) size: n (elements) load factor: n/m (average length) Hash Function: minimize collision

• abs(int_min()) = int_min()

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

Binary Search Tree (BST) O(n) worst

Invariant:

• (all data) in left child < parent < all data in right child (no dupe) - but no local check

AVL Tree

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

Heap (Priority Queue)

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)

Exam Review 3

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.

Allocating Array on Stack

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*

Allocating Struct on Stack

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

Strings

char* s1 = "hello"; it is an char pointer (or char array if you like)

• the end of string is NUL character (\0 whose value is 0)

Libraries

strlen: counts up to NUL, not included

• assert(strlen(s1) == 5) although the length of array is 6

strcpy(dst, src): copy up to NUL included

• dst must be big enough, otherwise buffer overflow or undefined.

Different types of String

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

Summary of Undefined

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

Freeing Casted pointers

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.

Casting (added section) - implementation defined if not stated

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

Decimals

Float: 32 bits Double: 64 bits Calculation rounding error depend on compiler

Union and Enum

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:

• 

• 

• 

• 

Graphs

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)

DFS / BFS

• 

  If we use queue: breath first If we use stack or other: depth first If we use priority: A* heuristic (but insertion and removal from priority queue is not O(1))

traversing

1. if (v1 = v2) return true
2. mark v1
3. put v1 in bag
4. while(non-empty bag) take an element if (elem = v2) return true else: mark, add elem's new neighbors to bag
5. free mark array, bag, and neighbors

Spanning Tree

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

• 0-1-4-0 only

Computing a Spanning Tree

Edge-Centric algorithm (O(ev)?O(elog(v)))

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)

Vertex-Centric algorithm (O(e))

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

Minimum spanning tree: one with the least total weight of its edges.

• a graph may have several minimum spanning trees

Kruskal's Algorithm (O(ev)->O(elog(e)))

• total is O(ev)

• sort is O(e log(e))

  • O(elog(e) + ev) above
  • since log(e) \in O(v)
    • because e \in O(v^2), so log e \in O(log v)
    • and log v \in O(v)

Union Find: A way to check connectivity by grouping O(ev)

• 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

Height Tracking: Trying to build balanced tree by tracking height (O(elog(e)))

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

Path Compression (O(eAck^{-1}(v)) amortized)

Prim's Algorithm (O(e log e))

• adding/removing edges is O(log e) in priority queue

• complexity O(e log e)

Amortized Flipping bits

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

• when add 1, we charge 1 token to flip right most 0, 1 token to flip back eventually

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