[Module2 Theory] Domains, Sparse Sets and State Manager

Question 1: Time Complexity of x.fix

The domain of a variable \(x\) is assumed to be implemented with a sparse set. Let the domain size of \(x\) be \(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 the 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 are very useful operations, especially for implementing bound-consistent propagators. What is the strategy followed in the default implementation of StateSparseSet.java for efficiently implementing the following operations:

min()
max()

A sparse set maintains two StateInt objects that store the current minimum and maximum values of the sparse set. The values of the StateInt objects are lazily updated whenever the minimum or maximum value changes during an update operation. Thus, assuming the values of the StateInt objects are correct, the running time of each of the two operations is \(O(1)\).

A sparse set maintains all the values sorted after every update. Thus, the running time of each of the two operations is \(O(1)\).

Each operation is implemented by linearly searching the whole set for the minimum or maximum value. Thus, for a domain of size \(n\), the running time of each of the two operations is \(\Theta(n)\).

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 B 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 A in order to visit the right child node C 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:

Consider the following Java program:

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 when executing the program?

5
8

6
5

8
5

8
8

Question 6:

Consider the following Java program:

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 in total when executing the program?

5

6

4

3

8

2

7

Question 7:

Consider the following Java program:

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();

How many objects of type StateEntry are created in total when executing the program?

9

7

4

5

6

3

8

Author(s)	pschaus
Deadline	No deadline
Submission limit	No limitation

Information

Sign in

Question 1: Time Complexity of x.fix

Question 2: Sparse Set

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

Question 4: Sparse Set Backtrack

Question 5:

Question 6:

Question 7:

Information

Sign in