##### Question 1: TimeComplexity of x.fix

Let \(x\) be a variable with a domain of size \(n\). What is the time complexity of the method x.fix(v) ?

\(O(n)\)

\(O(1)\)

\(O(n^2)\)

\(O(n \log(n))\)

##### Question 2: SparseSet

The internal state of a sparset-set identified as set and containing the values {0,1,2,3,4,5,6,7,8,9} is represented here:

What is the content of indexes after the following operations on the sparse-set:

set.remove(7) set.remove(0) set.removeAllBut(1)

Give the answer as a comma separeted list, for instance:

0,6,2,3,4,5,7,9,8,1

##### Question 3: min() and max() operations on SparseSet

Being able to retrieve the minimum and maximum value of a sparse-set domain is a very useful operations, especially for implementing bound-consistent propagators. What is the strategy followed in the default implementation of StateSparseSet.java for implementing efficiently

min() max()

The sparse-set maintains two StateInt to remember the current minimum and maximum. Those values are lazily updated whenever the minimum or the maximum disappears from the domain during an update operation. Assuming the values maintained are correct, it takes only \(O(1)\) to return them.

The sparse-set maintains all the values sorted after every update so it takes \(O(1)\) to retrieve the min.

Those operations are implemented by scanning everytime the whole set of values. For a domain of size n, it thus takes \(\Theta(n)\) to retrieve the min.

##### Question 4: SparseSet Backtrack

The domain of some variable \(x\) is implemented with a sparse-set and contains \(n\) values.

At some point, while exploring the search tree, the domain of x becomes empty and we need to backtrack all the way up to the root node to visit the right node of the root. In the worst case, what is the time complexity required to restore all the values in the domain of x ? Select the most accurate answer.

\(O(1)\)

\(O(n)\)

\(O(n^2)\)

\(O(1)\) expected but \(O(n)\) in the worst case

\(O(n \log(n))\)