Tutorial

• allowed containers: std::vector in C++, [] in Python
• if we use C++, the datasets are 100× larger (to compensate for the slowness of Python)
• we want to store a subset $S\subseteq\mathcal U$
  • $|S|=n$
  • we allocate an array of size $m=\Theta(n)$
  • $M=\set{0,\dots,m-1}$
  • idea: store value $x\in S$ at the index $h(x)$
    • $h:\mathcal U\to M$
  • collisions may occur (s.t. $h(x)=h(y)$)
    • the simplest solution: linked list
    • if we consider $m=\Theta(n)$ and a hashing function which spreads elements uniformly, the length of the lists will be constant on average
• heap
• analysis of Dijkstra using heap
  • binary heap vs. $d$-regular heap
  • how to select optimal $d$
  • $O(m\log_d n+nd\log_d n)$
    • two terms, one increases with $d$, the other decreases with $d$ increasing
    • intuition: we need the two terms to be equal to get the minimal value
  • so we use $d=\max{\set{2,\lceil m/n\rceil}}$
  • does it help?
    • for dense graphs, it helps
    • by substitution, we get complexity $\frac{m\log n}{\log(m/n)}$
    • if $m\geq n^{1+\varepsilon}$, then this equals $\frac{m\log n}{\log n^\varepsilon}=\frac1\varepsilon m=O(m)$
• binary tree
• binary search tree
• single rotation – we rotate a non-root node $u$ with its parent $p$
  • $u$ becomes a parent of $p$
• idea: whenever we access an element, we move it to the root
  • frequently accessed elements end up close to the root (not so deep)
  • but simple rotations can make the tree very unbalanced
• splay trees
  • we apply zig (single) rotation only if the node is a child of the root
  • zig-zag are just two single rotations of x
  • trick: for zig-zig, we first rotate the parent and grandparent
  • find operation
    • find and splay
    • if you don't find, splay the last found element
      • otherwise, the enemy could ask us to find an absent element too many times
  • insert = insert (if not present) & splay!
  • delete = replace by the successor, delete the successor, splay the parent of the deleted successor
    • or we could (somehow) splay the tree first and then delete