[Part2 Theory] Domains, Sparse Sets and StateManager

Question 1: Time Complexity of x.fix

The domain of a variable \(x\) is assumed to be implemented with a sparse-set. The domain size of \(x\) i is \(n\). What is the time complexity of the method \(x\).fix()?

\(O(n)\)

\(O(1)\)

\(O(n^2)\)

\(O(n \log n)\)

Question 2: Sparse Set

The current internal state of a sparse set identified below as set and initially 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 your answer as a comma-separated list, for instance:

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

Question 3: min() and max() Operations on Sparse Sets

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

min()
max()

A 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 kept values are correct, it takes only \(O(1)\) time to return the minimum and maximum.

A sparse set maintains all the values sorted after every update, so it takes \(O(1)\) time to return the minimum and maximum.

Those operations are implemented by scanning every time the whole set of values. For a domain of size \(n\), it thus takes \(\Theta(n)\) time to return the minimum and maximum.

Question 4: Sparse Set Backtrack

Assume the domain of a variable \(x\) is implemented with a sparse set and contains \(n\) values.

At some point, while exploring the search tree, assume the domain of \(x\) becomes empty and we need to backtrack all the way up to the root node in order to visit the right child 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)\)

Question 5:

StateManager sm;

StateInt a = sm.makeStateInt(6);
StateInt b = sm.makeStateInt(12);

sm.saveState();

a.setValue(6);

sm.saveState();

a.setValue(6);
a.setValue(8);

sm.saveState();
sm.restoreState();
System.out.println(a.value());
a.setValue(5);
System.out.println(a.value());
sm.restoreState();
sm.restoreState();

What is printed?

5
8

6
5

8
5

8
8

Question 6:

StateManager sm = new Trailer();

StateInt a = sm.makeStateInt(6);
StateInt b = sm.makeStateInt(12);

sm.saveState();

a.setValue(6);

sm.saveState();

a.setValue(6);
a.setValue(8);

sm.saveState();
sm.restoreState();
System.out.println(a.value());
a.setValue(5);
System.out.println(a.value());
sm.restoreState();
sm.restoreState();

How many objects of type StateEntry are created overall when executing this program ?

5

6

4

3

8

2

7

Question 7:

StateManager sm = new Copier();

StateInt a = sm.makeStateInt(6);
StateInt b = sm.makeStateInt(12);

sm.saveState();

a.setValue(6);

sm.saveState();

StateInt c = sm.makeStateInt(9);

a.setValue(6);
a.setValue(8);

sm.saveState();
sm.restoreState();
System.out.println(a.value());
a.setValue(5);
System.out.println(a.value());
sm.restoreState();
sm.restoreState();