# Group Assignment 3.3-3.5

## 3.3 (A-question)
Consider a stream of numbers $a_1, . . . , a_n ∈ {1, 2, . . . , n}$. Design and analyze an algorithm that uses $O(polylog(n))$ space and outputs whether the input stream is a permutation, or whether there is some $1 ≤ i < j ≤ n$ such that $a_i = a_j$.

It is enough that your algorithm works correctly with some constant probability $p > 0$. You can assume that n is known to the algorithm from the beginning.

Hints:

One possible solution is to extend the fingerprint technique.
Note that in this problem, the length $n$ of the stream is the same as the range ${1, . . . , n}$ of the possible values.

### Solution

## 3.4 (C-Question)
A 3-cut of a graph $G = (V, E)$ is a partition of $V$ into three nonempty sets of vertices $A$, $B$ and $C$. The size of the cut is the number of edges connecting vertices from different sets.

Design and analyze an algorithm that finds a minimum 3-cut in $O(n^4 log^{O(1)}n)$ time with high probability.

Hint: One possibility is to modify Karger's miminum cut algorithm from the lecture notes.

## 3.5 (E-Question)
Recall the warm-up version of the $L_0$ sampling algorithm for the special case when we know that the number of distinct elements in the stream is exactly 2.

Initialize by picking a random hash function $h : {0, . . . , n −1}→{0, 1}$.
When reading $a_i$: store ai if $h(a_i) = 0$.
If $> 1$ distinct number gets stored: output “fail”
If no number gets stored: output “fail”
Otherwise, output the stored number.
In other words, output the number x from the input stream that is hashed to 0, if it is unique.

Consider running this algorithm when the hash function is selected uniformly at random from the family $H= \{hr\}, r∈{0,...,n}$ where $hr(x) = 〈x, r〉\mod 2$. Here〈$x, r〉$ denotes the inner product of the numbers $x$ and $r$ when written as binary vectors. E.g. if $x = 7$ and $r = 9$ then in binary $x = (0, 1, 1, 1)$ and $r = (1, 0, 0, 1)$ and $〈x, r〉 = 0·1 + 1·0 + 1·0 + 1·1 = 1$. In other words we pick a uniformly random $r ∈ {0, . . . , n}$ and use $〈x, r〉\mod 2$ as the hash function.

Suppose $n = 3$ and the input stream is $(1, 2, 1, 3, 2, 3, 2, 1, 1, 1, 2, 3, 1, 3)$. Analyze the probability that the algorithm “fails” (in either of line 3 or 4). In other words, among the four possibilities of the value of $r ∈ {0, 1, 2, 3}$, how many of them lead to failures? Please write down your answer (a number between 0 and 1) before providing your analysis.

$0 = (0,0,0,0)$
$1 = (0,0,0,1)$
$2 = (0,0,1,0)$
$3 = (0,0,1,1)$

If $r = 0$:

$〈1, 0〉\mod 2 = 0$
$〈2, 0〉\mod 2 = 0$

FAIL (1 and 2 stored)

If $r = 1$:

$〈1, 1〉\mod 2 = 0+0+0+1=1$
$〈2, 1〉\mod 2 = 0+0+0+0=0$
$〈1, 1〉\mod 2 = 0+0+0+1=1$
$〈3, 1〉\mod 2 = 0+0+0+1=1$
...

SUCCESS (only 2 stored)

If $r = 2$:

$〈1, 2〉\mod 2 = 0+0+0+0=0$
$〈2, 2〉\mod 2 = 0+0+1+0=1$
$〈1, 2〉\mod 2 = 0+0+0+0=0$
$〈3, 2〉\mod 2 = 0+0+1+0=1$
...

SUCCESS (only 1 stored)

If $r = 3$:

$〈1, 3〉\mod 2 = 0+0+0+1=1$
$〈2, 3〉\mod 2 = 0+0+1+0=1$
$〈1, 3〉\mod 2 = 0+0+0+1=1$
$〈3, 3〉\mod 2 = 0+0+1+1=0$
$〈2, 3〉\mod 2 = 0+0+1+0=1$

SUCCESS (only 3 stored)

Answer: only $0$ leads to a failure. This means the probability of picking a failing $r$ is $\frac{1}{4}$.