Info

Übung

  • von Montag Woche bis Donnerstagabend Woche

TA:

Ü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:

  1. delete root (largest/smallest element)
  2. make last element new root
  3. 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

20250627_D&A_recursion proof example