20250317_D&A

Finding a Sub-Array (Rabin-Karp)

[[20250317_D&A_Serie5.pdf]]

Concatenating Heaps

The concatenation of $A$ and $B$ looks like this:

C = [a_{1}, a_{2}, \dots, a_{n}, b_{1}, b_{2}, \dots, b_{m}]

Since all elements of $A$ are smaller than each element of $B$ , and $A$ and $B$ are Min-Heaps, we know:

for $i \leq n$ :
- Since $C [i] = A [i]$ , and the structure is the same as $A$ , this part fulfills the min-heap properties.
for $i > n$ :
- $C [i] = B [i - n]$
- Since B is a min-heap, for every element $C [i]$ with $i > n$ , we know that this part of $C$ also fulfills the min-heap properties, because

\begin{aligned} C [2 \cdot i] & = B [2 \cdot (i - n)] \geq B [i - n] = C [i] \\ C [2 \cdot i + 1] & = B [2 \cdot (i - n) + 1] \geq B [i - n] = C [i] \end{aligned}

Thus, $C$ is also a Min-Heap.

Cuckoo hashing

1.) Inserting the keys 27, 2, and 32:

27:

	0	1	2	3	4
$T_{1}$	$-$	$-$	$27$	$-$	$-$
$T_{2}$	$-$	$-$	$-$	$-$	$-$

	0	1	2	3	4
$T_{1}$	$-$	$-$	$2$	$-$	$-$
$T_{2}$	$27$	$-$	$-$	$-$	$-$

32:

	0	1	2	3	4
$T_{1}$	$-$	$-$	$32$	$-$	$-$
$T_{2}$	$2 / 27$	$-$	$-$	$-$	$-$

	0	1	2	3	4
$T_{1}$	$-$	$-$	$2$	$-$	$-$
$T_{2}$	$27$	$32$	$-$	$-$	$-$

2.) Infinite Sequence

With the Cuckoo hashing technique we can store at most two keys with the same $h_{1}$ and $h_{2}$ value. Since $2$ and $27$ already have the same values, any third number $k$ with the same $h_{1}$ and $h_{2}$ values would lead to an infinite sequence.

$k$ needs to fulfill the following two conditions:

\begin{aligned} k & = 5 m + 2 & (h_{1}) \\ ⌊ \frac{k}{5} ⌋ & = 5 p & (h_{2}) \end{aligned}

$I$ in $I I$ :

⌊ m + \frac{2}{5} ⌋ = m \overset{!}{=} 5 p

in $I I$ :

k = 25 p + 2

With $p = 0$ we have $2$ , for $p = 1$ $27$ , and we could choose e.g. $p = 2$ and the third number $52$
-> $52$ would lead to an infinite sequence