Recap exercises - ferragina/AD2DA GitHub Wiki

Suppose that an integer sequence contains the values

7 (200 times) 22 (100 times) 64 (50 times) 250 (20 times)

Estimate the space usage of variable byte encoding using 8-bit blocks (7 data + 1 continuation) or 4-bit blocks (3 data + 1 continuation).

Which are the smallest and the largest integer representable with a Gamma code of 17 bits?

Decode the sequence $0110011000110000110000011000$

• Decode the sequence $(10)^{16}1$ (33 bits in total)

• Decode the sequence $01100110001100001100000110$

• Which is the first value obtained by delta-decoding the sequence $0^5 1 0^{55} 1 0^{55} \cdots$

Encode the integers 10, 20, 30, 40 with Gamma, Delta and plain Variable-byte encoding (7+1). Which is the one producing the smallest total length?

Encode the sequence of integers: $2, 3, 5, 8, 13, 21, 34$ belonging to the universe $[0,40)$

The Elias-Fano coding of a sequence of integers in $[0,101)$ is L = 00000000100001100011, H= 11100010. Which is the largest integer in the sequence?

Find a sequence of 4 increasing integers, whose Elias-Fano encoding returns an array $L$ of all 0's

How many nodes are there in the suffix tree of abcd$. Justify your answer.

Which is the LCP array of the string aaa...aa$ ($n$ a's in total)?

Show how to compute in linear time the lexicographically smaller longest common substring between S and T, using the suffix tree for the string S#T$'. Next, show how to solve the problem still in linear time using the Suffix Aray and LCP array of S#T$.

Suppose we want to build an FM-index for a sequence of length $2^{32}$ over an alphabet of size 4, so that each character can be represented with two bits.

To represent the column $L$ and support rank operations over it, we consider the following two strategies:

1. As in Ben Langmead slides, store $L$ and a sample of the rank values for each alphabet symbol, sampling one position every 512.

2. Use a wavelet tree in which in each node the rank1 operation is supported using a 25% overhead over the plain bit array.

Compare the space usage and running time of the two solutions. More in general, for which alphabet sizes the Wavelet tree approach is using less space than the sampling approach?

Let gsysnss.mm..isi$siih denote the BWT of an unknown string (note $ < . < any other char). In addition to the BWT, the index stores the positions of the suffix array entries which are multiple of 5 (counting from 0): sa[8]=5, sa[14]=10, sa[15]=0, sa[16]=15.

Using the backward search procedure, we find that the pattern miss appears twice, in rows 10 and 11 of the rotations matrix. Describe the steps required for computing the position of the two occurrences in the indexed texts, and in particular detail with rank operations over the BWT are required for the computation.

Estimate the total size usage of the sampled Suffix Array for a 4GB text over an alphabet of size 4, assuming that in order to locate a position of an occurrence we want to execute at most 32 applications of the LF-map. Which is the answer if the alphabet has size 16?

Let L denote the BWT of a string over the alphabet $ < a < b.

1. prove that it cannot be L[0] = $
2. prove that L cannot start with BAA

• Consider a balanced WT of height 4 storing a sequence of n integers in the range [0,15]. Describe a procedure for counting the number of elements in the sequence greater of equal to 5, using a single tree traversal. Generalize replacing 5 with an arbitrary integer between 0 and 15.

• Draw the shape of a Wavelet Tree for the integers 1,2,3,4,5, in which the root-to-leaf path for integer $i$, $i=1,\ldots,5$ has length at most equal to the length of the binary string $\gamma(i)$

• Using Kraft inequality, prove that there cannot be a wavelet tree with 5 leaves at depth respectively 1, 2, 3, 3, 3.

• Estimate the extra space of a wavelet tree in which the binary rank operation is supported splitting the inputs in blocks of size 512 and for each block using a block count of size 64 and 7 mini-block counts of 9 bits each. Which is the size of a mini-block?

• The popcount operation computes in constant time the number of 1's in a 64 bit integer. Which is the fastest way to compute the number of 1's among the first 20 bits of an integer?

Note: in the LOUDS representation in the slides the role of 0s and 1s is reversed with respect to Sect. 15.2.2 of the textbook. Use the one you prefer.

Consider the following binary tree (some nodes have been labeled for convenience)

Describe: 1) the binary tree representation, 2) the LOUDS representation, 3) the balanced parenthesis representation

a bc  de    f
1 11 1111 00101101 01000000 00

    a   b   c   d   e     f 
1 110 110 110 010 110 10 10 0000

ab  df    Bce    E    CA
((()((())))((()())(())))

Consider the binary tree representation and describe the sequence of rank/select operations required to move from node a to node f. Recall that each node is identified by its position in the level order traversal, so a=1, b=2, c=3, d=5, e=6, f=8.

In the LOUDS representation describe the sequence of rank/select operations require to move from node e to the root of teh tree. Recall that each node is identified by its position in the level order traversal, so a=1, b=2, c=3, d=5, e=6, f=8

Consider the following tree (some nodes have been labeled for convenience)

Describe: 1) the LOUDS representation, 2) the balanced parenthesis representation

      a        b      c    d
1 11110 000 1110 00 110 0 10 0

a      b    c  d  DCBA
(()()()(()()(()(()))))

Consider the following adjacency lists, and show ho to compress them using reference compression. Each list must be compressed referring to the previous list which has the largest intersection with it.

Id    OutDeg    Successors
1     8         10 20 30 40 50 60 70 80
2     4          9 10 40 45
3     4          8  9 10 40
4     2         40 60
5     3         40 70 81
6     5         10 40 60

For each node, except the first, specify Reference, Copy Lists and Extra nodes.

Draw the $k^2$ tree encoding the following matrix:

and compute the succinct binary representation of the tree.