Info
Ü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
amortized analysis: Introduction_to_Algorithms_----_(IV_Advanced_Design_and_Analysis_Techniques).pdf
the copy-swap idiom is useful if you want securely to write new data to a vector, without implementing it yourself
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:
- delete root (largest/smallest element)
- make last element new root
- sift down from root
-> extraction in
quiz: number of MaxHeaps of keys -> root node and structure is fixed, but the rest of the heap is just all possible combinations
e.g.
3: 2 possibilities 6: 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 () approach for only two lines
There is a line with two points and a second line with . If the cross product between is positive and is negative, the two vertices of are on different sides of is either intersecting with or behind . By the cross product also from () and they are also not on the same side of (have different signs), we can be sure that and 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
- NOTE: cuts can have more than , but can only be as large as the smallest cut
finding max flow with augmenting paths
- there is still a path with capacity 1
- there is still a path with capacity 1
- there are no more augmenting paths -> max flow reached with
finding max flow with cuts
- cut : capacity 8
- cut : capacity 11
- cut : capacity 11
- cut : capacity 8
and => since min cut is , but , the max flow of is not reached
timestamp 2025-06-03
timestamp 2025-06-25
