Übungen

#timestamp 2025-02-20

#timestamp 2025-02-25

graph LR;
    Z(( ))
    
    Z -->|Key-Value Pairs?| B(Duplicates?)
    B -->|yes| C(Ordered?)
    C -->|yes| D[multimap]
    C -->|no| E[unordered_multimap]
    B -->|no| F(Ordered?)
    F -->|yes| G[map]
    F -->|no| H[unordered_map]

    Z -->|Values?| J(Duplicates?)
    J -->|yes| K(Ordered?)
    K -->|sorted| L[multiset]
    K -->|insertion order| M[vector, array, deque, list, forward_list]
    K -->|no| N[unordered_multiset]
    J -->|no| O(Ordered?)
    O -->|yes| P[set]
    O -->|no| Q[unordered_set]

induction proofs

• base clause
• induction hypothesis
• induction step

#timestamp 2025-03-11

the copy-swap idiom is useful if you want securely to write new data to a vector, without implementing it yourself

• https://stackoverflow.com/a/3279550/16490381

#timestamp 2025-03-18

Binary Search TREE

traversal possibilities:

pre:
8 3 5 4 13 10 9 19
post:
4 5 3 9 10 19 13 8
inorder:
3 4 5 8 9 10 13 19
-> inorder traversing is sorted for a BST

rebuilding tree from a trasversal:
1 3 2 5 6 8 7 4
recursively:
-> 4 root, 1 3 2 left, 5 6 8 7 right
-> left: 2 root, 1 left, 3 right
-> right: 7 root, 5 6 left, 8 right

-> for pre- and post-order, the tree is unique, but not for inorder

Heap

extract min/max:

1. delete root (largest/smallest element)
2. make last element new root
3. sift down from root

-> extraction in $\mathcal{O}(\log n)$

quiz: number of MaxHeaps of $n$ keys
-> root node and structure is fixed, but the rest of the heap is just all possible combinations

e.g.

3: 2 possibilities
6: $(\genfrac{}{}{0ex}{}{5}{3})\ast N(3)=20$ possibilities
-> root fixed: 5 elements left, 3 elements in left subtree, 2 in right
-> we know: N(3) options for left subtree, only a single option for right subtree

Hashing

Modulo

#timestamp 2025-04-08

how to find an intersection?

least complex ($\mathcal{O}(n)$) approach for only two lines

There is a line $a$ with two points $a_1,a_2$ and a second line $b$ with $b_1,b_2$. If the cross product between $a\times a_1{b}_1$ is positive and $a\times a_1{b}_2$ is negative, the two vertices of $b$ are on different sides of $a$ $⟹$ $b$ is either intersecting with $a$ or behind $a$.
By the cross product also from $b$ ($b\times b_1{a}_1,b\times b_1{a}_2$) and they are also not on the same side of $b$ (have different signs), we can be sure that $a$ and $b$ are intersecting.

int sgn(int num) {
	if (num > 0) return 1;
	if (num < 0) return -1;
	return 0; // (?) is this correct
}

bool is_intersecting(line a, line b) {
	// check if a and b possibly intersects
	line ab1 = line(a.p1, b.p1);
	line ab2 = line(a.p1, b.p2);
	if(sgn(cross_product(a, ab1)) != sgn(cross_product(a, ab2))) {
		// check if a and b intersect, from b
		line ba1 = line(b.p1, a.p1);
		line ba2 = line(b.p1, a.p2);
		if(sgn(cross_product(b, ba1)) != sgn(cross_product(b, ba2)))
			return true;
	}
	return false;
}

finding all intersections ->

#timestamp 2025-05-06

max flow

consider this flow network:

graph LR
    a -- 4/5 --> b
    a -- 2/3 --> c
    b -- 5/5 --> d
    c -- 1/3 --> b
    c -- 1/3 --> d

found the maximum flow if:

• the residual network does not have any more augmenting paths
• alternative: Identify a cut with $|c(S,T)|=|f|$
  • NOTE: cuts can have more than $|f|$, but $|f|$ can only be as large as the smallest cut

finding max flow with augmenting paths

• there is still a path $a\to b\to c\to d$ with capacity 1
• there is still a path $a\to c\to d$ with capacity 1
• there are no more augmenting paths -> max flow reached with $8$

finding max flow with cuts

• cut $\{a\},\{b.c.d\}$: capacity 8
• cut $\{a,b\},\{c,d\}$: capacity 11
• cut $\{a,c\},\{b,d\}$: capacity 11
• cut $\{a,b,c\},\{d\}$: capacity 8

and $|f|=b\to d+c\to d=7$
=> since min cut is $8$, but $|f|=7$, the max flow of $8$ is not reached

#timestamp 2025-06-03

#timestamp 2025-06-25

recursion proof - example