Exam

You should know all theory presented at the lecture: definitions of data structures and operations on them, all theorems and proofs thereof. The exam is oral with written preparation. You will get one major and one minor question from the following list.

Major questions

• Define the Splay tree. Describe operations Splay, Find, Insert, and Delete. Compare Splay trees with other data structures, in particular balanced search trees. State and prove the theorem on amortized complexity of the Splay operation.
  • splay tree = self-adjusting binary search tree
  • static optimal trees minimize the total search time for a known sequence of operations find
    • we don't know the sequence → we move every searched element to the root
  • operation splay(x) … pull node $x$ to the root
    • preferably using double rotation (zigzig, zigzag)
      • z has child y
      • y has child x
      • zigzig(x)/zigzag(x) moves x above both y and z
      • zigzig is used if $x \lt y\lt z$ or $z\lt y\lt x$
      • zigzag is used if $y\lt x\lt z$
    • possibly with one single rotation (zig) – as the last step
      • y has child x
      • zig(x) makes y child of x
    • splay performs a sequence of the operations until x becomes the root
  • operations
    1. find(x) or insert(x) or delete(x)
    2. splay(lowest visited node)
  • lemma: for $a,b,c\in\mathbb R^+$ satisfying $a+b\leq c$, it holds that $\log(a)+\log(b)\leq 2\log(c)-2$
    • $4ab=\underbrace{(a+b)^2}_{\leq c^2}-\underbrace{(a-b)^2}_{\geq 0}\leq c^2$
    • $\log 4+\log a+\log b\leq\log c^2$
    • note that we consider $\log_2$
  • notation, our choice of potential
    • $s(x)$ … size = number of nodes in the subtree rooted at $x$ (including $x$)
    • potential of a node $x$ … $\Phi(x)=\log s(x)$
      • sometimes denoted as rank $r(v)$
    • total potential … $\Phi:=\sum_v \Phi(v)$
    • $s_i,\Phi_i$ … values after $i$-th step
    • $p$ … parent of $x$
    • $g$ … parent of $p$
  • theorem: the amortized cost of splay(x) is at most $3(\log s_i(x)-\log s_{i-1}(x)) + 1$
  • zig step
    • $\Phi_i(x)=\Phi_{i-1}(p)$
    • $\Phi_i(p)\lt\Phi_i(x)$
    • the potential of the remaining nodes stays the same
    • $\Phi_i-\Phi_{i-1}=\sum_u(\Phi_i(u)-\Phi_{i-1}(u))=\Phi_i(x)-\Phi_{i-1}(x)+\Phi_i(p)-\Phi_{i-1}(p)$
    • $=-\Phi_{i-1}(x)+\Phi_i(p)\lt\Phi_i(x)-\Phi_{i-1}(x)$
  • zig-zag
    • $\Phi_i(x)=\Phi_{i-1}(g)$
    • $-\Phi_{i-1}(p)\lt-\Phi_{i-1}(x)$
      • because $\Phi_{i-1}(x)\lt\Phi_{i-1}(p)$
    • $\Phi_i(p)+\Phi_i(g)\leq 2\Phi_i(x)-2$
      • clearly $s_i(p)+s_i(g)\leq s_i(x)$ so we just apply the lemma
    • $\Phi_i-\Phi_{i-1}=\Phi_i(g)-\Phi_{i-1}(g)+\Phi_i(p)-\Phi_{i-1}(p)+\Phi_i(x)-\Phi_{i-1}(x)$
    • $=\Phi_i(g)+\Phi_i(p)-\Phi_{i-1}(p)-\Phi_{i-1}(x)\leq 2(\Phi_i(x)-\Phi_{i-1}(x))-2$
    • $\leq 3\Delta\Phi(x)-2$
  • zig-zig
    • similar
    • but we need to apply the lemma to this inequality: $s_{i-1}(x)+s_i(g)\leq s_i(x)$
      • → $\Phi_i(g)\leq 2\Phi_i(x)-\Phi_{i-1}(x)-2$
    • $\Phi_i-\Phi_{i-1}=\Phi_i(g)+\Phi_i(p)-\Phi_{i-1}(p)-\Phi_{i-1}(x)\leq 3(\Phi_{i}(x)-\Phi_{i-1}(x))-2$
    • $\leq 3\Delta\Phi(x)-2$
  • an operation has amortized cost $A$ if every execution of the operation satisfies $T_i+\Phi_i-\Phi_{i-1}\leq A$
    • zig-zig or zig-zag step ($T_i=2$)
      • $T_i+\Delta\Phi\leq 2+3\Delta\Phi(x)-2=3\Delta\Phi(x)$
    • zig step ($T_i=1$)
      • $T_i+\Delta\Phi\leq 1+\Delta\Phi(x)\leq 1+3\Delta\Phi(x)$
    • properties of our potential
      • $1\leq s(v)\leq n$
      • $0\leq \Phi(v)\leq \log n$
      • $0\leq\Phi\leq n\log n$
    • in total
      • $\sum_i(T_i+\Delta\Phi)\leq 1+\sum_i3(\Phi_i(x)-\Phi_{i-1}(x))$
        • we can apply telescopic sum (cancellation)
      • $\leq 1+3(\Phi_\mathrm{last}(x)-\Phi_0(x))$
        • in the end, the potential of $x$ is $\log n$
        • the initial potential of $x$ is at least zero
      • $\leq 1+3\log n=O(\log n)$ amortized complexity
  • comparison with other data structures
    • a splay tree is never asymptotically slower than a static optimal tree
    • it does not support parallelism
    • AVL tree
      • every individual lookup in $O(\log n)$
      • does not prioritize nodes that are accessed often
      • more difficult to implement
    • worst-case complexity of $k$ operations splay
      • potential always satisfies $0\leq\Phi\leq n\log n$
      • the difference between the final and the initial potential is at most $n\log n$
      • $\sum_{i=1}^k T'_i\leq\sum_{i-1}^k(1+3\log n+\Phi_{i-1}-\Phi_i)=k+3k\log n+\sum_{i=1}^k(\Phi_{i-1}-\Phi_i)$
      • $=k+3k\log n+\Phi_0-\Phi_k\leq O(k+k\log n+n\log n)=O((n+k)\log n)$
      • note that a single splay takes at most $O(n)$ time (if the tree is just a path)
• Define the (a,b)-tree. Describe operations Find, Insert, and Delete. Analyze their complexity in the worst case. Compare (a,b)-trees with other data structures, in particular balanced search trees.
  • multiway search tree
    • $k$ keys stored in a non-decreasing order in one node ($x_1,\dots,x_k$)
      • this node has $k+1$ children
      • subtrees $T_0,\dots,T_k$
      • $x_i\lt$ keys in $T_i\lt x_{i+1}$
    • terminology
      • internal node
      • external node (leaf) – contains no data, has no children
  • $(a,b)$-tree for $a\geq 2,\ b\geq 2a-1$ is a multiway search tree s.t.
    • $a\leq$ # children in internal node $\leq b$
      • $a-1\leq$ # keys $\leq b-1$
      • we relax this for the root to be able to store a single key in the entire data structure: $2\leq$ # children in root $\leq b$
    • all external nodes are on the same level
  • observation: for any $(a,b)$-tree of height $h$…
    • number of external nodes is at most $b^h$
      • every node has at most $b$ children
    • number of keys is at most $b^h-1$
      • external nodes correspond to intervals – keys separate them
    • number of external nodes is at least $2a^{h-1}$
      • every node has at least $a$ children (root has at least 2)
    • number of keys is at least $2a^{h-1}-1$
    • → $\log_b(n+1)\leq h\leq \log_a(\frac{n+1}2)+1$
      • $h\in\Omega(\log_b n)$
      • $h\in O(\log_a n)=O(\frac{\log n}{\log a})$
  • operation Find
    • $O(\log b)$ per node (to find the correct subtree)
    • in total $O(\log n\cdot\frac{\log b}{\log a})=O(\log n)$ if $b$ is polynomially bounded
  • operation Insert(x)
    • we assume it is not there (Find ends in an external node)
    • we take the parent $v$ of the external node; we add $x$ there (and add an external node)
    • if $v$ not oversized → stop
    • otherwise we split the node and push one of the keys (the middle one) to the upper node
      • we propagate this up
      • if the root is oversized, we create a new root
    • does the splitting create valid nodes?
      • oversized node has $b$ keys → new nodes have $\lfloor\frac{b-1}2\rfloor$ and $\lceil\frac{b-1}2\rceil$ keys
      • we need $\lfloor\frac{b-1}2\rfloor\geq a-1$
      • we have $b\geq 2a-1$, so this holds
  • operation Delete(x)
    • Find returns $v$
    • if $v$ is not in the last internal level, we replace it by a suitable key from the nodes in the last internal level
      • suitable = successor
    • so now we are deleting a node $v'$ in the last internal level (including an external node)
    • if $v'$ not undersized → stop
    • otherwise, we borrow a key from a sibling (if it has at least $a$ keys)
      • we perform a “rotation” of the keys (sibling to the parent, parent to the undersized node)
    • if a sibling does not have enough keys, we merge the nodes (we take a key from the parent)
      • in total, we get $a-2+1+a-1=2a-2$ keys which is alright (as $b\geq 2a-1$ and there can be at most $b-1$ keys)
      • this may propagate upwards if the parent does not have enough keys (again, we first try to borrow a key from a sibling)
  • complexity
    • Insert, Delete in $O(b\frac{\log n}{\log a})$
      • we need to manipulate at most $b$ items at each level (merging/splitting the nodes)
    • Find in $O(\log b\frac{\log n}{\log a})$
    • we need $b$ small (probably $2a-1$ or $2a$)
      • $2a$ to give some breathing space
    • if we consider such $b$, we can write $O(a\frac{\log n}{\log a})$ and $O(\log a\frac{\log n}{\log a})$
      • so we want $a$ small → $(2,4)$
      • in practice, we store the trees in memory (we want one memory block to roughly correspond to one node) → $(128,256)$
  • comparison with other data structures
    • they are shallower than binary search trees → better disk/cache performance
    • unlike hash tables, they support range queries
• Define I/O model for caches and compare cache-aware and cache-oblivious algorithms. Formulate a cache-oblivious algorithm for transposition of a square matrix. Analyze its time complexity and I/O complexity.
  • external memory model (I/O model)
    • we have internal and external memory
    • operations read (external → internal) and write (internal → external)
      • they are directly controlled by the programmer
    • definition: any algorithm has I/O complexity $f(n,B,M)$ if for any input of size $n$ it performs $\leq f(n,B,M)$ read/write operations
      • $M$ … total size of memory
      • $B$ … size of one memory block
      • so the memory has $M/B$ blocks
    • we usually care only about reads (there are more reads than writes)
  • cache-aware model
    • cache line of size $B$
    • size $M$ of the cache
    • CPU knows $B,M$
    • assumptions
      • fully associative cache (any memory block can be in any cache line)
      • cache controller has an optimal strategy
        • it evicts the cache lines that won't be needed (or will be needed the latest in the future)
  • cache-oblivious model
    • same as cache-aware, but CPU does not know $B,M$
    • if our algorithm works well in this model, it may work well for any level of the cache (unlike the previous models which work well for certain values of parameters)
  • consider a matrix $N\times N$
    • usually stored by rows
    • scanning by rows … $O(N^2/B+1)$ reads
    • scanning by columns … $O(N^2+1)$ if $M\lt NB$
  • matrix transposition
    • naive way: we traverse in both ways (by columns and by rows at once)
      • $O(N^2+1)$ block transfers if the memory is small
    • idea: split the problem into smaller subproblems which fit in the cache
      • “tiling” … tiles of size $d\times d$
      • tiles on the main diagonal can be transposed directly
      • non-diagonal tiles have to be transposed and swapped with the opposite ones → we need two tiles to fit into the cache
      • number of tiles … $\lceil N/d\rceil^2\leq (N/d+1)^2=O(N^2/d^2+1)$
      • consider $d=B$
        • we need $M\geq 2B^2$
        • usually, we make tall cache assumption … $M=\Omega(B^2)$, “memory is at least as tall as it is wide”
      • we need $O(B)$ transfers per tile → I/O complexity $O(N^2/B^2+1)\cdot O(B)=O(N^2/B+1)$
        • for cache-aware model
    • another approach: divide and conquer
      • consider $N=2^k$
      • operation transpose (T)
        • T → 2T + TS
      • operation transpose and swap (TS)
        • TS → 4TS
      • each task splits into at most 4 subtasks
      • at level $i$, we will have at most $4^i$ nodes
      • number of levels … $\log N=k$
        • each time, we reduce the size by two
      • number of leaves $\leq 4^{\log N}=N^2$
      • number of internal nodes $\leq$ number of leaves $\leq N^2$
      • in leaves
        • T … do nothing
        • TS … swap elements, $O(1)$
      • internal nodes … $O(1)$ time
      • time $O(N^2)\quad\checkmark$
      • consider a level where the subtree fits in the memory
        • min $i$ such that $d=\frac N{2^i}\leq B$
        • it becomes equivalent to the cache-aware algorithm with tiles $d=\Theta(B)$
      • so we get $O(N^2/B+1)$ I/O complexity again
        • under the cache-oblivious model (with the tall cache assumption)
        • it is optimal – each nondiagonal element has to be transferred
      • note: we must show that there exists a replacement strategy that leads to this I/O complexity
        • consider a strategy where we load the entire subproblem into the cache at level $i$
        • this strategy serves as an upper bound (in terms of cache misses) for the optimal strategy
• Describe hashing with chains and analyze its complexity. Define c-universal and k-independent systems of hash functions and provide constructions of such systems. Give an example when k-independent system in needed and c-universality does not suffice.
  • hashing function $h:\mathcal U\to [m]$
    • universe $\mathcal U$
    • $m$ buckets … $[m]=\set{0,\dots,m-1}$
    • $n$ elements are already in the hash table
    • collision → we add the element to the end of the chain
    • density $\alpha=n/m$ … expected length of the chain (in some cases?)
  • using a fixed hashing function is problematic – there exists an adversarial sequence of inputs
    • solution: pick our hashing function uniformly randomly from a parametrized family of hashing functions
    • we don't have enough memory to store a totally random function → we need a parametrized family
  • theorem
    • let $\mathcal H$ be $c$-universal, $x_1,\dots,x_n,y\in\mathcal U$ are distinct
    • then $\mathbb E_{h\in\mathcal H}[\# i\mid h(x_i)=h(y)]\leq\frac{cn}m$
  • proof (from linearity of expectation)
    • indicator variable $A_i$ for each collision
      • $A_i=1$ iff $h(x_i)=h(y)$
    • $\mathbb E[A_i]=0\cdot Pr[h(x_i)\neq h(y)]+1\cdot Pr[h(x_i)=h(y)]\leq\frac cm$
    • $\mathbb E[\sum_{i=0}^n A_i]=\sum_{i=0}^n\mathbb E[A_i]\leq\frac{cn}m$
  • complexity of hashing with chaining
    • unsuccessful find … $O(n/m)$
    • successful find … $O(n'/m)$
      • $n'$ … number of elements at the point in time when this element was inserted
    • insert, delete – similar analysis
      • unsuccessful insert = successful find
    • if $n=\Omega(m)$, we get constant expected time
  • what if we don't know $n$ (how many elements we need to hash)
    • idea: stretching
    • if $\alpha=\frac nm\gt 1$, then $m'=2m$, pick new $h\in\mathcal H$, rehash
    • if $\alpha\lt 1/4$, then $m'=\frac m2$, pick new $h$, rehash
    • so we keep $\alpha$ in the interval $[\frac 14,1]$ (but we could choose a different interval)
    • we need to ensure that we have linearly many operations between reallocations
      • so after reallocation, we want to be somewhere in the middle between the two bounds
  • definition: $c$-universality
    • let $\mathcal H$ be a family of functions from $\mathcal U$ to $[m]$
    • $\mathcal H$ is $c$-universal for some $c\gt 0$ if $\forall x,y\in\mathcal U,\ x\neq y$ we have $Pr_{h\in\mathcal H}[h(x)=h(y)]\leq\frac cm$
    • $\mathcal H$ is universal if it is $c$-universal for some $c\gt 0$
  • definition: $k$-independence
    • $\mathcal H$ is $(k,c)$-independent if $\forall$ distinct $x_1,\dots,x_k\in\mathcal U$ and $\forall a_1,\dots,a_k\in[m]$ it holds that $Pr_{h\in\mathcal H}[h(x_1)=a_1\land\dots\land h(x_k)=a_k]\leq\frac c{m^k}$
      • where $k$ is integer s.t. $1\leq k\leq |\mathcal U|$ and $c\gt 0$ is real
    • it's $k$-independent if it's $(k,c)$-independent for some $c$
  • observations
    • for $k\geq 2$, $(k,c)$-independence $\implies$ $(k-1,c)$-independence
    • $(2,c)$-independence $\implies$ $c$-universality
    • $(1,c)$-independence $\mathrlap{\kern{0.8em}/}{\implies}$ $c$-universality
      • consider a family of constant hashing functions
  • $k$-independence is necessary for linear probing and cuckoo hashing
  • 2-universal example
    • $h_{a,b}(x)=(ax+b\bmod p)\bmod m$
    • $\mathcal L=\set{h_{a,b}\mid a,b\in\mathbb Z_p}$
    • theorem: $\mathcal L$ is 2-universal $\forall$ prime $p\geq m$
    • proof
      • $x\neq y$ fixed
      • $r=(ax+b)\bmod p$
      • $s=(ay+b)\bmod p$
      • claim: $(a,b)\mapsto (r,s)$ is a bijection
        • for any pair $(r,s)$ there is exactly one choice of $(a,b)$
        • because the system of equations is regular (thanks to $x\neq y$)
        • so if I'm picking $a,b$ uniformly randomly, then $r,s$ is also chosen uniformly randomly
      • $Pr[r=s\mod m]=$ # bad pairs / # all pairs $\leq\frac{p\cdot\lceil p/m\rceil}{p^2}$
        • $p/m$ … “how many times $m$ fits inside $p$”
        • $\lceil p/m\rceil\leq\frac{p+m}m\leq\frac{2p}m$
      • so $\frac{p\cdot\lceil p/m\rceil}{p^2}\leq\frac{2p}{pm}=\frac 2m$
  • $k$-independent example
    • $h_t(x)=\sum_{i=0}^{k-1} t_ix^i\mod p$
      • $h_t:\mathbb Z_p\to\mathbb Z_p,\ t\in\mathbb Z_p^k$
      • evaluation of the polynomial in $\mathbb Z_p$
    • $\mathcal P_k=\set{h_t\mid t\in\mathbb Z_p^k}$
    • theorem: $\mathcal P_k$ is $(k,1)$-independent $\forall p$ prime, $k\geq 1$
    • proof
      • we have distinct $x_1,\dots,x_k$
      • we have $a_1,\dots,a_k$
      • $Pr[\forall i:h_t(x_i)=a_i]=\frac 1{p^k}$
        • by Lagrange interpolation theorem, there is exactly one polynomial of degree $k-1$ that intersects $k$ points
    • example
      • for $k=2$, we get $h_{a,b}=ax+b\bmod p$
      • we can see that $\mathcal P_2$ is $(2,1)$-independent (and thus 2-universal even without $\bmod m$)
• Describe and analyze hashing with linear probing (under fully random hashing function). Compare this hashing with other data structures, in particular based on other hashings.
  • probing
    • saves space (each bucket contains at most one item)
    • probe sequence: $h(x,0),h(x,1),\dots$
    • Insert follows the probe sequence until it finds an empty cell
    • linear probing
      • $h(x,i)=h(x)+i\mod m$
      • we store the items with the same $h(x)$ right next to each other
    • alternative: double hashing
      • $h(x,i)=h(x)+ig(x)\mod m$
  • properties
    • it's cache-friendly – the correct bucket is likely to be loaded into the cache (this is often not the case with double hashing or quadratic probing)
    • it stores the data directly inside the hash table (unlike hashing with chains)
    • it degrades as the table becomes full (note $m\geq 3n$ in the proof) – long clusters get longer
    • operation Delete generates tombstones (we cannot remove elements in the middle of clusters → we mark the buckets as deleted and later rehash the table if there's too many tombstones)
  • theorem: if $m\geq (1+\varepsilon)n$, then the expected number of probes in Find is…
    • $O(1/\varepsilon^2)$ for a totally random hashing function
      • or tabulation hashing (even though it's only 3-independent!)
    • $O(1/\varepsilon^{13/6})$ for any 5-independent family
    • $\Omega(\log n$) for some 4-independent family
    • $\Omega(\sqrt n)$ for some 2-independent family
  • theorem
    • let $m\geq 3n$ s.t. $m$ is a power of 2
      • (we choose $\varepsilon=2$)
    • $h:\mathcal U\to[m]$ totally random
    • $x\in\mathcal U$
    • then the expected number of probes in Find($x$) is $O(1)$
  • proof
    • we use Chernoff bound (for the right tail)
      • let $X=X_1+\dots+X_k$ s.t. $X_i$ are binary and independent
      • then $Pr[X\gt c\mu]\leq (\frac{e^{c-1}}{c^c})^\mu$
        • where $\mu=\mathbb E[X]$ and $c\gt 1$
      • observation: if we fix $c$ and increase $k$, the probability drops exponentially
    • we also use the observation, that if we randomly generate a value of variable $X$, then $\mathbb E[X]\leq\sum_i(\max I_i\cdot Pr[X\in I_i])$
      • $I_i$ are intervals where the value can fall
      • so we use the maximum from each interval and the probability that the value falls in that interval
    • aim: show that the expected length of a run $R$ is constant
    • we will consider blocks of size $2^t$ that together tile the entire table of size $m$
    • definition: block $B$ of size $2^t$ is critical if more than $\frac23\cdot 2^t$ items are hashed to $B$
      • it does not matter where the items are stored! we only care about the items being hashed to that block
    • lemma L1
      • let $B$ be block of size $2^t$
      • then the probability that $B$ is critical is $\leq(\frac e4)^{\frac{2^t}3}$
    • proof
      • we consider indicators $X_i$ indicating if $h(x_i)\in B$
      • $X=\sum X_i$ … number of items hashed to $B$
      • $\mu=\sum\mathbb E[X_i]=n\cdot\frac {2^t}m$
        • as we consider a totally random function
      • $\mu\leq\frac{2^t}3$
        • as $m\geq 3n$
      • $Pr[B\text{ critical}]\leq Pr[X\gt 2\mu]\leq(\frac{e}4)^{\frac{2^t}3}$
        • from Chernoff
        • to simplify the reasoning, we can consider $m=3n$
      • we can set $q=(e/4)^{1/3}$
        • then $Pr\leq q^{2^t}$
    • lemma L2
      • let $R$ be run, $|R|\geq 2^{\ell+2},\ B_0,\dots,B_3$ first 4 blocks of size $2^\ell$ intersecting $R$
      • then at least one of $B$ is critical
    • proof
      • consider interval $L=R\cap (B_0\cup \dots\cup B_3)$
      • $1+3\cdot 2^\ell\leq$ # items stored in $L$ $\leq$ # items hashed to $L$
        • we are considering a prefix of the run so every element stored in the blocks also has to be hashed there
      • suppose that none of the blocks is critical
        • there are at most $4\cdot\frac23\cdot 2^\ell$ items hashed to $L$
        • but this is less than $1+3\cdot 2^\ell$ → contradiction
    • lemma L3
      • consider run $R$ containing $h(x),\ |R|\in[2^{\ell+2},2^{\ell+3})$
      • then at least one of 12 consecutive blocks of size $2^\ell$ is critical
        • we consider the 8 blocks before $h(x)$, the block containing $h(x)$, and the 3 blocks after $h(x)$
    • proof
      • $4|B|\leq |R|\lt 8|B|$
      • so $R$ can begin up to 8 blocks before $h(x)$
      • then we use L2
    • we can apply union bound $Pr[\bigcup_i A_i]\leq\sum_i Pr[A_i]$
      • we get $Pr[|R|\in[2^{\ell+2},2^{\ell+3})]\leq 12q^{2^\ell}$
      • we are using the fact at least one of the 12 blocks needs to be critical (to get a run this long)
    • now we use the intervals
      • $I_1=[0,3]$ and the remaining intervals
      • $\mathbb E[|R|]\leq 3\cdot 1+\sum_{\ell\geq 0}2^{\ell+3} Pr[|R|\in[2^{\ell+2},2^{\ell+3})]$
      • $\leq 3+12\cdot 8\cdot \sum_{\ell\geq 1}iq^i$
      • $q\lt 1$ so the sum converges and we get $O(1)$
• Define multi-dimensional range trees and describe the type of queries it supports. Analyze time and space complexity of their construction and complexity of range queries.
  • goal: poly-logarithmic range queries, not space optimal
    • $O(\log^k n)$ time, $O(n\log^{k-1} n)$ space
  • idea: primary 1D search tree for x-coordinates of all points (x-tree) + secondary 1D search tree in each node $v$ for y-coordinate of all points in $\mathrm{int}(v)\times\mathbb R$ (“band”)
  • observation: $y_i$ is only in secondary subtrees on the path to $x_i$
    • → $O(n\log n)$ space if x-tree balanced
  • RangeQuery$([a_1,b_1]\times[a_2,b_2])$
    • x-tree: RangeQuery$([a_1,b_2])$ → $O(\log n)$ points + bands (corresponding to subtrees)
    • points $(x_i,y_i)$: if $y_i\in[a_2,b_2]$, report
    • bands: RangeQuery$([a_2,b_2])$ to the corresponding y-tree
  • analysis
    • $O(\log n)$ time in x-tree, $O(\log n)$ time in each y-tree, $O(\log^2 n)$ time in total
    • it the points are also reported, we need $O(\log^2 n+p)$ where $p$ is the number of reported points
  • building the range tree
    • create two sorted lists of points: one sorted by the x-coordinate, the other sorted by the y-coordinate … $O(n\log n)$
    • recursion ($O(n)$ subproblems, $O(\log n)$ levels)
      • find median in x-list … $O(1)$ per subproblem
      • build y-tree … $O(n)$ per level
      • select sub-lists … $O(n)$ per level
    • total time: $O(n\log n)$
  • we assumed there are no shared coordinates
    • but we could attach a y-tree for points with the same x-coordinate
    • so we get 2 y-trees for the single x-tree node $v$
      • y-tree for band $\mathrm{int}(v)\times\mathbb R$
      • y-tree for $\mathrm{key}(v)\times\mathbb R$
  • k-D range trees (straightforward generalization)
    • primary x-tree (1D search tree) + secondary $(k{-}1)$-dimensional range tree for each band $\mathrm{int}(v)\times\mathbb R^{k-1}$
    • space: every point in $O(\log n)$ secondary range trees → $O(n\log^{k-1}n)$ in total
    • $O(\log^k n)$ time for RangeQuery ($+p$ if enumeration)
    • building: $k$ sorted arrays, $O(n\log^{k-1}n)$ time, constant is dependent on $k$
  • can be dynamized using lazily balanced trees
• Define suffix arrays and LCP arrays. Describe and analyze algorithms for their construction. Give an example of their application.
  • the suffix array for $\alpha$ is a permutation $S[0,\dots,n]$ s.t. $\forall (0\leq i\lt n):\alpha[S[i]{:}]\lt\alpha[S[i+1]{:}]$
    • example for bananas
      0. $\varepsilon$, 7
      1. ananas, 1
      2. anas, 3
      3. as, 5
      4. bananas, 0
      5. nanas, 2
      6. nas, 4
      7. s, 6
  • the rank array $R[0,\dots,n]$ is an inverse permutation to $S$
    • $R[i]$ … number of suffixes that are lex. smaller than $\alpha[i{:}]$
    • it's a mapping inverse to $S$ (position → lexicographic order)
  • the LCP-array $L[0,\dots,n-1]$
    • $L[i]$ … length of the longest common prefix of $i$-th suffix and $(i{+}1)$-th suffix (in the lex. order)
  • constructing $R$ (we can easily construct $S$ based on $R$) – using doubling
    • $R[i]$ … lex. rank of substring starting at $i$
    • $R_k[i]$ … number of positions $j$ s.t. $\alpha[j:j+k]\lt\alpha[i:i+k]$
      • number of prefixes $\alpha[j]$ that are lexicographically smaller than $\alpha[i]$ if we compare only the first $k$ characters
    • we can compute $R_{2k}[i]$ as the number of positions $j$ s.t. $R_k[j]\lt R_k[i]$ or $R_k[j]=R_k[i]\land R_k[j+k]\lt R_k[i+k]$
      • we want to sort triples $(R_k[i],R_{k}[i+k],i)$
      • we can use bucket sort in $O(n)$
    • $R_n=R$
    • we need $O(n\log n)$ for the initial step (if the alphabet is large and we cannot rely on the bucket sort)
  • observation: $\forall(0\leq i\lt j\leq n):\mathrm{LCP}(\alpha[S[i]{:}],\alpha[S[j]{:}])=\min(L[i],L[i+1],\dots,L[j-1])$
    • let's say that the right side is $k$
    • then the LCP of $i,j$ has to be at least $k$
    • the sequence of characters at $k+1$ position is non-decreasing
      • the chars are the same (if their LCP is greater than $k$) or they differ (here we use the lex. order)
    • so the LCP of $i,j$ has to be $\leq k$
  • observation
    • let's consider two suffixes that are lexicographically consecutive (adjacent): $\alpha,\beta$
    • if we remove the first character from both of them, we get $\alpha',\beta'$
    • if $\mathrm{LCP}(\alpha,\beta)$ is nonzero, then $\mathrm{LCP}(\alpha',\beta')=\mathrm{LCP}(\alpha,\beta)-1$
    • $\alpha',\beta'$ may not be lexicographically consecutive but $\mathrm{LCP}(\alpha',\beta')$ is the minimum of that interval (according to the previous observation)
    • so to compute LCP of $\alpha'$ and its successor, we can start with $\mathrm{LCP}(\alpha,\beta)-1$
  • $S,R\to L$
    • Kasai's algorithm
      • iterate from the longest to the shortest suffix
        • index of the $i$-th suffix … $R[i]$
      • in every iteration
        • take the previous computed $k$, subtract one, clamp (so that it does not go below zero) → we get a new $k$
        • take the suffixes corresponding to indices $R[i]$ and $R[i]+1$ (the lexicographic successor)
        • we need to compare their characters one by one
          • we can skip the first $k$ characters
          • for every matching pair, we increment $k$ by one
    • runs in $O(n)$
      • we can use $k$ as potential
      • it's always non-negative and at most $n$
      • it always increases or decreases by one
      • there are at most $n$ decreases → there are at most $2n$ increases
  • applications
    • histogram of all $k$-grams (might be useful for classifying a language or a species based on its DNA)
      • we can find it in linear time by going through LCP array
      • if the current LCP is below $k$, we reached a new $k$-gram
      • we need to check that $S[i]$ is not too large (so that it truly is a $k$-gram – it should not be shorter than $k$)
    • longest repeating substring (redundancy measure)
      • find a maximum in the LCP array
    • longest common substring in $\alpha,\beta$
      • we build a LCP array for $\alpha\#\beta$
• Describe locks and atomic operations CAS and LL/SC. Describe and analyze a lock-free stack including the memory management. Explain the ABA problem and its solution.
  • lock (mutex)
    • where / how many
      • one per DS
      • one per item
        • locks bring some overhead
        • only works if there is not too much “structure” in the data structure
      • one per part
        • e.g. bucket in hash table (for hashing with chaining) + one global lock (for rehashing)
    • locks are blocking – the process needs to wait if the data structure is locked
    • problems: deadlock (ordering is not always available or possible to use), fairness, inverse priorities, fault-tolerance
  • HW assumptions (to support lock-free data structures)
    • atomic registers: read, write, (exchange), (test & set bit)
    • load linked (LL) / store conditional (SC)
      • not always available, only for limited number of registers
      • a linked load is a normal atomic read, but the processor remembers the address and keeps monitoring it for access by other processors
      • a later store conditional to the same address succeeds if the address was not written to by other processors (otherwise it reports failure)
    • compare & swap (CAS)
      • CAS(address, x, y)
      • atomically performs the following
        • load value from address
        • if value equals x, store y at address
        • return value
      • often available
  • lock-free stack
    • node: atomic pointer to next
    • global: atomic pointer to head
    • Push(n): (loop)
      • h ← head
      • n.next ← h
      • if CAS(head, h, n) == h
        • return
    • Pop: (loop)
      • h ← head
      • n ← h.next
      • if CAS(head, h, n) == h
        • return h
  • it does not work :(
    • for Pop, we are checking only the head – the next item might have been removed in the meantime
      • other process could have run this sequence of operations: Pop (removes A), Pop (removes B), Push(A)
      • ABA-problem
    • possible solutions
      • use LL/SC
      • double CAS (atomic) … only theoretical solution
        • if DCAS((head, h.next), (h, n), (n, n)) == (n, n)
      • wide CAS (atomic)
        • we can use pointer versioning
        • if WCAS((head, version), (h, ver), (n, ver+1)) == (h, ver)
        • theoretical problem: overflow (does not happen in practice)
      • restrictive memory management
    • another problem: memory management
      • if someone pops and deallocates head before we read h.next (after storing h), we may crash
    • solution: freelist
      • list of memory pieces that are ready to be deallocated
      • we deallocate only if we are sure that nobody uses them
      • how to be sure
        • synchronization points: we synchronize all processes at a point where they hold no pointers of their own (we can then free up all chunks from the freelist)
        • reference counting
        • hazard pointers – signal to the garbage collector that I am using the pointer
          • we store h in the hazard pointer
          • then we check if h still equals head (otherwise we need to continue into the next loop)
      • amortize scanning the freelist
        • scan only if freelist $\geq 2pr$ items
        • $p$ … number of processes
        • $r$ … number of hazard pointers per processor
        • this releases $\geq pr$
        • so scan can be accounted to the adding

Minor questions

• Describe a flexible array with growing and shrinking. Analyze its amortized complexity.
  • let's consider a stack, it has operations append(x) and removelast
  • shrink to $C/2$ if $n\lt C/2$?
    • this is problematic, we would get linear amortized complexity
    • we should use $n\lt C/4$ instead
  • amortized analysis … average over operations in the worst-case scenario
  • operations
    • append – double the capacity if the array is full … costs $O(C)$ in this case
    • removelast – halve the capacity if the array becomes shorter than $C/4$ … costs $O(C)$
  • we consider blocks of operations
    • block boundaries = growing/shrinking operation
    • “how many elements does the array contain at the beginning and at the end of the block?”
      • always $C/2$ at the beginning (after growing/shrinking operation, the array is half full)
      • if growing: $C$ at the end
      • if shrinking: $C/4$ at the end
    • so there are at least $C/4$ operations in each block (to get from $C/2$ elements to $C/4$ or $C$ elements)
    • we can account the $O(C)$ reallocation to the $\Omega(C)$ operations
      • → amortized $O(1)$ for operation
      • “accounting method” – we account the cost to the operations
  • note that the buffer does not need to be exactly $C/4$ but has to be linearly dependent on $C$
• Define the lazily balanced trees $BB[\alpha]$. Analyze their amortized complexity. Give an example of their application.
  • notation
    • $n$ … number of items stored in the tree
    • $\ell(v),r(v)$ … left/right child of $v$
    • $s(v)$ … size = number of nodes in the subtree rooted at $v$ (including $v$)
  • definition: BST is perfectly balanced if for every node $v$ it holds that $|s(\ell(v))-s(r(v))|\leq 1$
    • the ratio is approximately 1 : 1
  • definition: BST is balanced if for every $v$ and its every child $c$ it holds that $s(c)\leq \frac23s(v)$
    • the ratio is between 1 : 2 and 2 : 1
  • lemma: any balanced BST has depth $O(\log n)$
    • imagine the longest path from the root to a leaf
    • in each step from the root to the leaf, the size drops to at most 2/3 of the preceding size
    • size of the root … $n$
    • size of the leaf … 1
    • $1\leq(\frac23)^dn$
    • $d\leq\log_{2/3}(1/n)=\log_{3/2}n=O(\log n)$
  • insert operation
    • find, add a leaf, update sizes (we keep track of the sizes $s(v)$)
    • if not balanced, rebuild in the highest unbalanced node
  • observation: for $n$ sorted items, build takes linear time
    • select the middle item as the root and split the rest in two subtrees
    • proceed recursively
  • $\Phi:=\sum_v\varphi(v)$
  • $\varphi(v):=\begin{cases}|s(\ell(v))-s(r(v))|&\text{if at least } 2\\ 0&\text{otherwise}\end{cases}$
    • the clamping ensures that perfectly balanced tree has zero potential
  • cost of insert
    • no rebuild: $A=R+\Delta\Phi=O(\log n)+O(\log n)=O(\log n)$
      • $\Delta\Phi=O(\log n)$ because $\Delta\varphi\leq 2$ for each visited node (usually $\Delta\varphi=1$ but there may be nodes with $\varphi$ hopping from 0 to 2 due to the clamping)
    • rebuild at $v$
      • the invariant was broken for $v$ and its child $c$
      • WLOG $s(\ell(v))\gt\frac23 s(v)\implies s(r(v))\lt\frac13 s(v)\implies\varphi(v)\gt\frac13 s(v)$
        • after the rebuild, this contribution and all the contributions in the subtree become zero
        • contributions elsewhere stay the same
        • → potential drops … $\Delta\Phi\leq -\frac13 s(v)$
      • amortized cost of rebuild: $A=\underbrace{O(s(v))}_R+c\cdot\Delta\Phi\leq 0$
        • for a sufficiently large cost $c$
    • → $O(\log n)$ amortized time for insert
  • applications: dynamic sets, dictionaries (maps), priority queues
    • mostly in functional programming (new versions of a tree can share some subtrees with the original tree)
• Design operations Find, Insert, and Delete on a Splay tree. Analyze their amortized complexity. (It suffices to state the complexity of Splay operation without proof.)
  • operations
    1. find(x) or insert(x) or delete(x)
       • as in an ordinary BST
       • when deleting a node with two children, we need to replace it by its successor (WLOG)
    2. splay(lowest visited node)
  • analyzing operations
    • we need $A\leq R+\Delta\Phi$
    • find does not change the potential
      • going from the root to a node at depth $d$ has cost $\Theta(d)$
      • splaying this node also costs $\Theta(d)$ and it amortizes to $O(\log n)$
      • we can account the cost of the former part on the splay → find has total amortized complexity $O(\log n)$
    • delete decreases the potential – that's fine 👍
      • $A\leq R$
    • insert increases the potential
      • only for the nodes on the path $v_1,\dots,v_t,\underbrace{v_{t+1}}_{\text{new}}$
      • we can apply telescopic cancellation again
      • $\Delta\Phi=\Phi_i(v_{t+1})+\sum_{i=1}^t(\Phi_i(v_i)-\Phi_{i-1}(v_i))$
        • $s(v_{t+1})=1\implies\Phi_i(v_{t+1})=0$
        • $s_i(v_i)=s_{i-1}(v_i)+1\leq s_{i-1}(v_{i-1})$
      • $\Delta\Phi\leq\Phi_i(v_1)-\Phi_{i-1}(v_t)$
      • so $\Delta\Phi$ is $O(\log n)$
  • so all the operations are $O(\log n)$ amortized
• State and prove the theorem on amortized complexity on Insert and Delete on (a,2a-1)-trees and (a,2a)-trees.
  • theorem: $m$ inserts on empty $(a,b)$-tree do $O(m)$ modifications
    • number of splits $\leq$ number of nodes in $(a,b)$-tree with $m$ keys $\leq m$
  • observation: $(a,2a{-}1)$-tree cannot have $O(1)$ amortized modifications for inserts/deletes
    • there exists a problematic sequence of operations which performs $\log n$ modifications for every operation (similar to the shrinking array)
    • example: tree where every node on a path from the root to the leaves contains 2 keys and every other node contains 1 key (if we consider a $(2,3)$-tree)
      • inserting a key on the path leads to $\log n$ modifications
      • if we then delete it, $\log n$ modifications need to be performed again
      • we end up with the same tree as before → we can repeat these two operations
  • theorem: any sequence of $m$ inserts/deletes on empty $(a,2a)$-tree does $O(m)$ modifications
  • proof
    • $A=R+\Delta\Phi$
    • goal: find $\Phi$ s.t. $A=O(1)$ for add/remove/move and $A\leq 0$ for split/merge
    • $\Phi=\sum_{v \text{ internal}} f(|v|)$
      • $|v|$ … number of keys in $v$
    • we need to define the contribution $f$ for every possible size of a node (including oversized and undersized nodes)
    • add/remove/move: $|f(i+1)-f(i)|\leq c$ for some constant $c$
    • split: $f(2a)\geq f(a-1)+f(a)+c+1$ (should be 3 but we write 1 → up to rescaling)
      • so $A_\mathrm{split}\leq 0$
    • merge: $f(a-1)+f(a-2)\geq f(2a-2)+c+1$
      • so $A_\mathrm{merge}\leq 0$
    • possible function
      • $c=2$
      • $f(a-2)=2$
      • $f(a-1)=1$
      • $f(a)=0$
      • …
      • $f(2a-2)=0$
      • $f(2a-1)=2$
      • $f(2a)=4$
    • to conclude
      • $\sum R_i=\sum A_i-\Delta\Phi$
      • $\sum A_i=O(m)$
      • $\Delta\Phi=\underbrace{\Phi_m}_{\geq 0}-\underbrace{\Phi_0}_{=0}$
      • so we get $\sum R_i=O(m)$
• Analyze k-way Mergesort in the cache-aware model. Which is the optimum value of k?
  • standard Mergesort
    • we merge two “runs” (sorted arrays) of sizes $n_1,n_2$ into a single run of size $n_1+n_2$
    • $O(n\log n)$ … $O(\log n)$ passes; $O(n)$ operations in each one
    • one merge = three scans of the array
      • one scan has I/O complexity $O(N/B+1)$
  • $K$-way Mergesort
    • number of passes … $O(\log_K N)=O(\frac{\log N}{\log K})$
    • we need a heap to keep minimum of $K$ elements … $O(\log K)$
    • time
      • one pass … $O(N\log K)$
      • total … $O(N\log K\cdot\frac{\log N}{\log K})=O(N\log N)$
    • I/O complexity
      • $K+1$ scans per one run
      • one pass … $O(N/B+1)$
      • total … $O(N/B\cdot\frac{\log N}{\log K}+1)$
    • how many memory blocks we need?
      • $K+1$ blocks for merge + $K-1$ for heap
        • $K-1$ is more than enough (even a logarithm of $K$ would suffice but we want to get a nice sum)
      • so we need $M\geq 2KB$
      • optimal $K=\lfloor M/2B\rfloor$
      • which leads to I/O complexity $O(N/B\cdot\frac{\log N}{\log M/B}+1)$
        • in cache-aware model
• State and prove the Sleator-Tarjan theorem on competivity of LRU.
  • optimal strategy: “evict the cache line needed the latest” (it's an offline strategy)
  • cost of strategy $S$ … $T_{S}$ = number of cache misses
    • w.r.t. sequence of requests for particular blocks $a_1,\dots,a_n$
    • we assume fully associative cache
    • no assumption on the initial contents of the cache
  • strategy is $k$-competitive for a constant $k\geq 1$ if $(\forall C)(\forall a_1,\dots,a_n):T_{STR}\leq k\cdot T_{OPT}$
    • $C$ … cache size
    • $T_{OPT}$ … cost of the optimal strategy
  • LRU (least-recently used) strategy: “evict the cache line unused the longest time”
  • theorem: $\forall C$ and $\forall\varepsilon\gt 0$ there is an access sequence s.t. $T_{LRU}\geq C\cdot(1-\varepsilon)\cdot T_{OPT}$
    • in other words, LRU is not $k$-competitive for any $k$ (if we want the $k$ to be independent of $C$)
    • consider an access sequence $1,\dots,C,C{+}1,1,\dots,C,C{+}1,\dots$ repeated
  • theorem (Sleator, Tarjan): $(\forall C_{LRU}\gt C_{OPT}\geq 1)(\forall a_1,\dots,a_n): T_{LRU}\leq\underbrace{\frac{C_{LRU}}{C_{LRU}-C_{OPT}}}_{\gt 1} T_{OPT}+C_{OPT}$
  • corollary: for $C_{LRU}=2 C_{OPT}$, LRU is $(2{+}\varepsilon)$-competitive for large-enough sequences
  • proof
    • we split the sequence into epochs (from the end to the beginning) s.t. in every epoch except for the first one, $T_{LRU}=C_{LRU}$
      • in the first one ($E_0$): $T_{LRU}\leq C_{LRU}$
    • epoch $E_i$ s.t. $i\geq 1$
      • there are two possible situations
      1. LRU misses on distinct blocks
         • this means that the access sequence for this epoch contains at least $C_{LRU}$ distinct blocks
         • so OPT must miss at least $C_{LRU}-C_{OPT}$ times (it cannot have more than $C_{OPT}$ blocks in cache)
      2. LRU misses twice on the same block $b$
         • after the first miss, $b$ was at the head of the LRU list → there had to be at least $C_{LRU}$ other blocks accessed in the meantime
         • again, OPT must miss at least $C_{LRU}-C_{OPT}$ times
      • in epoch $E_i$, we get $T_{LRU}\leq\frac{C_{LRU}}{C_{LRU}-C_{OPT}}T_{OPT}$
    • epoch $E_0$
      • both strategies start with an empty cache → LRU misses are distinct
      • OPT can prevent up to $C_{OPT}$ of those misses
      • $T_{OPT}\geq T_{LRU}-C_{OPT}$
• Describe a system of hash functions based on scalar products. Prove that it is a 1-universal system from $Z_p^k$ to $Z_p$.
  • $h_t(x)=xt=\sum_{i=1}^d x_it_i \mod p$
  • $h_t:\mathbb Z_p^d\to\mathbb Z_p$ (for hashing strings)
  • $t,x\in\mathbb Z_p^d,\ p$ prime
  • theorem: $\mathcal S=\set{h_t\mid t\in\mathbb Z_p^d}$ is 1-universal $\forall d\geq 1$, $p$ prime
  • proof
    • for $x\neq y$ (WLOG $x_d\neq y_d$) it holds that $Pr[h_t(x)=h_t(y)]=Pr[xt=yt]=Pr[(x-y)t=0)]=$
    • $=Pr\left[(x_d-y_d)t_d=-\sum_{i=1}^{d-1}(x_i-y_i)t_i\right]$
    • note that $(x_d-y_d)\neq 0$
    • every $t_i$ is chosen independently with probability $1/p$
    • after fixing the sum, there is only one element $t_d$ such that the equality holds (and we have $p$ choices for $t_d$)
  • definition: 1-universality
    • let $\mathcal H$ be a family of functions from $\mathcal U$ to $[p]$
    • $\mathcal H$ is 1-universal if $\forall x,y\in\mathcal U,\ x\neq y$ we have $Pr_{h\in\mathcal H}[h(x)=h(y)]\leq\frac 1p$
• Describe a system of linear hash functions. Prove that it is a 2-independent system from $Z_p$ to $[m]$.
  • $h_{a,b}(x)=(ax+b\bmod p)\bmod m$
  • $\mathcal L=\set{h_{a,b}\mid a,b\in\mathbb Z_p}$
  • theorem: $\mathcal L$ is $(2,4)$-independent $\forall$ prime $p\geq m$
  • proof
    • $x\neq y$ fixed, $i,j\in[m]$ fixed
    • we need $Pr[h_{a,b}(x)=i\land h_{a,b}(y)=j]\leq\frac 4{m^2}$
    • $r=(ax+b)\bmod p$
    • $s=(ay+b)\bmod p$
    • claim: $(a,b)\mapsto (r,s)$ is a bijection
      • for any pair $(r,s)$ there is exactly one choice of $(a,b)$
      • because the system of equations is regular (thanks to $x\neq y$)
      • so if I'm picking $a,b$ uniformly randomly, then $r,s$ is also chosen uniformly randomly
    • $Pr[r=i\mod m]=$ # bad values of $r$ / # all possible values of $r$ $\leq\frac{\lceil p/m\rceil}{p}$
      • # bad values of $r$ … “how many times $m$ fits inside $p$”
      • $\lceil p/m\rceil\leq\frac{p+m}m\leq\frac{2p}m$
    • so $\frac{p\cdot\lceil p/m\rceil}{p^2}\leq\frac{2p}{pm}=\frac 2m$
    • similarly, $Pr[s=j\mod m]\leq\frac 2m$
    • clearly, $Pr[h_{a,b}(x)=i\land h_{a,b}(y)=j]=Pr[r=i\mod m]\cdot Pr[s=j\mod m]\leq\frac 4{m^2}$
      • the events are independent
  • definition: $k$-independence
    • $\mathcal H$ is $(k,c)$-independent if $\forall$ distinct $x_1,\dots,x_k\in\mathcal U$ and $\forall a_1,\dots,a_k\in[m]$ it holds that $Pr_{h\in\mathcal H}[h(x_1)=a_1\land\dots\land h(x_k)=a_k]\leq\frac c{m^k}$
      • where $k$ is integer s.t. $1\leq k\leq |\mathcal U|$ and $c\gt 0$ is real
    • it's $k$-independent if it's $(k,c)$-independent for some $c$
• Construct a k-independent system of hash functions from $Z_p$ to $[m]$.
  • $h_t(x)=\sum_{i=0}^{k-1} t_ix^i\mod p$
    • $h_t:\mathbb Z_p\to\mathbb Z_p,\ t\in\mathbb Z_p^k$
    • evaluation of the polynomial in $\mathbb Z_p$
  • $\mathcal P_k=\set{h_t\mid t\in\mathbb Z_p^k}$
  • theorem: $\mathcal P_k$ is $(k,1)$-independent $\forall p$ prime, $k\geq 1$
  • proof
    • we have distinct $x_1,\dots,x_k$
    • we have $a_1,\dots,a_k$
    • $Pr[\forall i:h_t(x_i)=a_i]=\frac 1{p^k}$
      • by Lagrange interpolation theorem, there is exactly one polynomial of degree $k-1$ that intersects $k$ points
  • lemma
    • let $\mathcal H$ be $(k,c)$-independent family of $h:\mathcal U\to[r]$
    • then $\mathcal H\bmod m$ is $(k,2^kc)$-independent (for $m\leq r$)
  • proof (for $k=2$)
    • $x_1\neq x_2,\ a_1,a_2\in[m]$
    • $Pr_{h'\in\mathcal H\bmod m}\left[h'(x_1)=a_1\land h'(x_2)=a_2)\right]=\sum_{i_1,i_2} Pr_{h\in\mathcal H}\left[h(x_1)=i_1\land h(x_2)=i_2\right]$
      • for $i_1\equiv a_1\mod m$ and $i_2\equiv a_2\mod m$
    • $\leq\sum_{i_1,i_2}\frac c{r^2}\leq\frac c{r^2}\lceil \frac rm\rceil^2\leq\frac c{r^2}\cdot(\frac{2r}{m})^2\leq\frac {4c}{m^2}$
      • because there are $\lceil \frac rm\rceil$ ways to choose $i_1$ and the same number of ways to choose $i_2$ and because $\lceil \frac rm\rceil\leq\frac{r+m}m\leq\frac{2r}m$
  • proof (generalized)
    • $Pr\leq\sum_{i_1,\dots,i_k}\frac c{r^k}\leq\frac c{r^k}\lceil \frac rm\rceil^k\leq\frac c{r^k}\cdot(\frac{2r}{m})^k\leq\frac {2^k c}{m^k}$
  • so $\mathcal P_k\bmod m$ is $k$-independent ($r=p$)
  • we could add another assumption that $r\geq 2km$ to get $(k,2c)$-independence
• Construct a 2-independent system of hash functions for hashing of strings of length at most L over an alphabet $[a]$ to a set of buckets $[m]$.
  • rolling hashing
    • let's consider $h_a(x)=\sum_{i=0}^{d-1} x_ia^i\bmod p$
      • so $x\in\mathbb Z_p^d$
      • $\mathcal R=\set{h_a\mid a\in\mathbb Z_p}$
    • lemma: $\mathcal R$ is $d$-universal for $d\geq 1$, $p$ prime
    • proof
      • $x\neq y$
      • $Pr_a[h_a(x)=h_a(y)]=Pr_a[\sum_{i=0}^{d-1}(x_i-y_i)a^i=0]\leq\frac dm$
        • a polynomial of degree $d-1$ has at most $d-1$ roots (which is $\leq d$)
    • $\mathcal R\circ\mathcal L$ is $(2,\frac 52)$-independent if $p\geq 4dm$
    • to hash strings of length at most $L$, we set $d:=L$ and we pad the strings by zeros (assuming that they don't occur elsewhere) → this part of the string then gets “skipped”
  • lemma
    • let $\mathcal F$ be a $c$-universal family of $f:\mathcal U\to[r],\ r\geq m$
    • $\mathcal G$ is $(2,d)$-independent family of $g:[r]\to[m]$
    • then $\mathcal H=\mathcal F\circ\mathcal G=\set{f\circ g\mid f\in\mathcal F,\ g\in\mathcal G}$ is $(2,c')$-independent where $c'=(\frac{cm}r+1)d$
      • where $(f\circ g)(x)=g(f(x))$
  • proof
    • $x_1,x_2\in\mathcal U,\ x_1\neq x_2,\ i_1,i_2\in[m]$
    • match event $M$ … $g(f(x_1))=i_1\land g(f(x_2))=i_2$
    • collision event $C$ … $f(x_1)=f(x_2)$
    • $P(M)=\underbrace{P(M|\neg C)}_{2\text{-ind.}}\underbrace{P(\neg C)}_{\leq 1}+\underbrace{P(M|C)}_{1\text{-ind.}}\underbrace{P(C)}_{c\text{-univ.}}$
      • $P(M| C)=0$ if $i_1\neq i_2$, otherwise 1-independence
    • $\leq \frac{d}{m^2}\cdot 1+\frac dm\cdot\frac cr=\frac{dr+dcm}{m^2r}=\frac{c'}{m^2}$
• Describe the cuckoo hashing and state the theorem on its complexity (without proof).
  • we have two hash functions $f,g$ and two sets of $m$ buckets $T_f,T_g$
  • we hash the inserted element and if the bucket is already full, we take the element present there and insert it it using the other function
    • we continue until we have correctly placed all the elements
  • when we meet the timeout (we keep cycling back and forth between the tables for long enough), we rehash
    • timeout ~ $\log n$
  • invariant: $\forall x\in X$ is in $T_f(f(x))$ or $T_g(g(x))\implies$ Find, Delete in $O(1)$ (worst case)
  • theorem
    • let $m\geq (2+\varepsilon)n,\ f,g$ from $\lceil 6\log n\rceil$-independent family
    • then cuckoo hashing with timeout $\lceil 6\log n\rceil$ has expected amortized Insert time $O(1)$
• Describe hashing with linear probing and give overview of results on its complexity.
  • probing
    • saves space (each bucket contains at most one item)
    • probe sequence: $h(x,0),h(x,1),\dots$
    • Insert follows the probe sequence until it finds an empty cell
    • linear probing
      • $h(x,i)=h(x)+i\mod m$
      • we store the items with the same $h(x)$ right next to each other
    • alternative: double hashing
      • $h(x,i)=h(x)+ig(x)\mod m$
  • properties
    • it's cache-friendly – the correct bucket is likely to be loaded into the cache (this is often not the case with double hashing or quadratic probing)
    • it stores the data directly inside the hash table (unlike hashing with chains)
    • it degrades as the table becomes full (note $m\geq 3n$ in the proof) – long clusters get longer
    • operation Delete generates tombstones (we cannot remove elements in the middle of clusters → we mark the buckets as deleted and later rehash the table if there's too many tombstones)
  • theorem: if $m\geq (1+\varepsilon)n$, then the expected number of probes in Find is…
    • $O(1/\varepsilon^2)$ for a totally random hashing function
      • or tabulation hashing (even though it's only 3-independent!)
    • $O(1/\varepsilon^{13/6})$ for any 5-independent family
    • $\Omega(\log n$) for some 4-independent family
    • $\Omega(\sqrt n)$ for some 2-independent family
• Describe and analyze the Bloom filter. Give an example of its application.
  • filter for set representation with zero false negatives
    • consider a database and a query Find(x)
    • you first ask the Bloom filter – if the filter responds “no”, we don't need to ask the database
    • of course, Insert(x) has to change both the filter and the database
  • the larger memory we have available, the smaller the probability of false positives
  • simple Bloom filter
    • bit array $[m]$, $h\in\mathcal H$ is $c$-universal
    • probability of false positivity
      • consider that there are already distinct $x_1,\dots,x_n$ present in the filter
      • consider $y$ distinct
      • $Pr[y\text{ is }FP]=Pr[\exists i:h(y)=h(x_i)]\leq\sum_{i=1}^n Pr_h[h(x_i)=h(y)]\leq\frac{cn}m$
      • let's consider that $c=1$ and that we want $Pr[FP]\leq \varepsilon$
        • we set $m:=\lceil n/\varepsilon\rceil$ (number of required bits)
        • so if there are $10^6$ items and we want $\varepsilon=0.01$, we need 100 Mb to store the filter
  • $k$-way Bloom filter
    • we take a conjunction of $k$ Bloom filters
    • we need $h_1,\dots,h_k$ to be independently chosen functions from a $c$-universal family
    • $Pr[y\text{ is }FP]\leq\prod_{i=1}^k\frac{cn}m=\frac1{2^k}\leq\varepsilon$
      • if $c=1$ and $m=2n$
    • $k:=\lceil\log 1/\varepsilon\rceil$
    • $M=mk=2n\lceil\log 1/\varepsilon\rceil$
    • now for $n=10^6$ and $\varepsilon=0.01$, we need $k=7$ and $M=14$ Mb
      • for $\varepsilon=0.001$, we need $k=10$ and $M=20$ Mb
  • single-band Bloom filter
    • we set $k$ bits using $k$ hash functions that are chosen independently – in the same table
    • if the hash functions are totally random, we may get results similar to the $k$-way filter
  • how to delete elements?
    • if we set the bit to zero, we delete all the elements with this hash value
    • instead of bits, we could use counters → counting filter
      • $b$ bits → at most $t:=2^b-1$ elements can be hashed to the same position at the filter
      • Insert/Delete just increment/decrement the value in the filter
      • Find returns yes if the filter is not zero
    • problem: when we reach $t$, the counter is “stuck” (cannot be increased, cannot be decreased), so there's a new kind of false positives
      • for a fixed bucket $i$ and totally random $h$, we have $Pr[B[i]\geq t]\leq{n\choose t}(\frac1m)^t\leq(\frac{ne}{mt})^t$
        • we use ${n\choose t}\leq(\frac{ne}t)^t$
      • if we set $m=\frac{n}{\ln 2}\doteq 1.44n$ and we use $b=4$, then $(\frac{ne}{mt})^t=(\frac{e\ln 2}t)^t\leq 3.06\cdot 10^{-14}$
      • if we have $m=10^9$ counters, the probability that any is stuck is $\leq 3.06\cdot 10^{-5}$
• Show how to perform 1-dimensional range queries on binary search trees.
  • for each node $v$ we define the interval of $v$ … $\mathrm{int}(v)$
    • contains all real numbers whose search visits $v$
    • keys in the internal nodes cut the real line to parts – these intervals correspond to the external nodes
    • they are all open intervals
  • algorithm RangeQuery$(v, Q)$
    • if $v$ is external, return
    • if $\mathrm{int}(v)\subseteq Q$, report the whole subtree rooted at $v$ and return
    • if $\mathrm{key}(v)\in Q$, report $\mathrm{key}(v)$
    • $Q_\ell\leftarrow Q\cap\mathrm{int}(\ell(v)),\ Q_r\leftarrow Q\cap\mathrm{int}(r(v))$
    • if $Q_\ell\neq\emptyset$, RangeQuery$(\ell(v), Q_\ell)$
    • if $Q_r\neq\emptyset$, RangeQuery$(r(v), Q_r)$
  • RangeQuery visits $O(\log n)$ nodes and subtrees if tree is balanced (has logarithmic depth)
    • $Q=(\alpha,\beta)$
    • $a$ … node where Find($\alpha$) stops
    • $b$ … node where Find($\beta$) stops
    • $p$ … lowest common predecessor of $a,b$
    • visited nodes: on the paths to $a,b$
    • visited subtrees: right subtrees on the path $p\to a$ and left subtrees on the path $p\to b$
• Define k-d trees and show that they require $\Omega(\sqrt n)$ time per 2-d range query.
  • keys = points in $\mathbb R^k$
  • on level $i$ split by $i$-th coordinate $\bmod k$
  • to build a static $k$-d tree, we use a median value at each level as a root
    • median of $m$ items in $O(m)$ time
    • $O(n)$ per level, $O(\log n)$ levels, $O(n\log n)$ time, $O(n)$ space
  • RangeQuery same as in 1D
    • alternate coordinates
    • $\mathrm{int}(v)$ is an open region (product of open intervals)
    • recurse until all coordinates fall into target intervals
  • lemma: RangeQuery in 2D search tree has $\Omega(\sqrt n)$ worst-case time complexity
    • consider points $\set{(i,i)\mid 1\leq i\leq n}$
    • $n=2^t-1$
    • $t$ … depth
    • RangeQuery(root, $\set{0}\times\mathbb R$)
      • x-coordinate → go to the left
      • y-coordinate → go both left and right
      • we end up visiting $2^{t/2}\approx\sqrt n$ nodes (we need to recurse into both subtrees at every other level)
  • note: it's $\Theta(\sqrt n)$
  • we assumed there are no shared coordinates
    • but we could attach a $(k{-}1)$-d subtree to each node where some points share a coordinate
• Show how to use suffix array and LCP array for finding the longest common substring of two strings.
  • we build a suffix array and LCP array for the string $\alpha \# \beta$
  • $\#$ … separator that occurs neither in $\alpha$ nor in $\beta$
  • we find the maximum $L[k]$ such that $k$-th (lex.) substring comes from $\alpha$ and $k{+}1$-th (lex.) substring comes from $\beta$ or vice versa
  • we can use $S$ to find out if the substring belongs to $\alpha$ or $\beta$ (we can compare it to the position of $\#$)
• Describe parallel (a,b)-trees with the use of locks.
  • standard $(a,b)$ tree: $a-1\leq$ number of keys $\leq b-1$
  • top-down splitting and merging
    • we need $b\geq 2a$
    • we go top down and maintain the invariant that the current node can accept one key (pre-emptive splitting)
    • → we don't need to go back
    • similarly, we maintain the invariant that the current node has more keys than $a-1$
    • we get $a-1\lt$ number of keys $\lt b-1$
  • we only need to have two locks at the same time – the current node and its parent
  • for deleting, we may need to lock siblings
    • we lock nodes in left-to-right order
    • note that if we delete a key from a node, we need to lock its subtree (we use the successor as a replacement) – this problem does not occur if we use B+ trees (store data in leaves only)