## 2 The Algorithms: MC, MCQ, MCR, MCS and BBMC
### Mc
#### 2.1.2 Observations on MC  
There are several points of interest. First, there is the search process itself. If we commented out lines 37 and changed line 41 to add to \(newP\) all vertices in \(P\) other than \(v\), method \(expand\) would produce the power set of \(P\) and at each depth \(k\) in the backtrack tree we would have \({n\choose k}\) calls to \(expand\). That is, \(expand\) produces a _binomial backtrack search tree_ of size \(O(2^{n})\) (see pages 6 and 7 of [17]). This can be compared to a bifurcating search process where on one side we take an element and make arecursive call, and on the other side reject it and make a recursive call, terminating when \(P\) is empty (_i.e._, generating a binary backtrack tree such as in [6,8,18]). This generates the power set on the leaf nodes of the backtrack tree and explores \(2^{n+1}-1\) nodes. This is also \(O(2^{n})\) but in practice is often twice as slow as the binomial search. In Figure 2 we see a binomial search produced by a simplification of MC, generating the power set of \(\{0,1,2,3\}\). Each node in the tree contains two sets: The set that will be added to the power set and the set that can be selected from at the next level. We see 16 nodes and at each depth \(k\) we have \(\binom{n}{k}\) nodes. The corresponding tree for the bifurcating search (not shown) has 31 nodes with the power set appearing on the 16 leaf nodes at depth 4. The second point of interest is the actual Java implementation. Java gives us an elegant construct for iterating over collections, the for-each loop, used in line 41 of Listing 1. This is rewritten in class MC0 (extending MC, overwriting the \(expand\) method) Listing 2 lines 15 to 18: One line of code is replaced with 4 lines. MC0 gets the \(j^{th}\) element of \(P\), calls it \(w\) (line 16 of Listing 2) and if it is adjacent to \(v\) it is added to \(newP\) (line 17 of Listing 2). In MC (line 41 of Listing 1) the for-each statement implicitly creates an iterator object and uses that for selecting elements. This typically results in a 10% reduction in runtime for MC0. Our third point is how we create our sets. In MC0 line 14 the new candidate set is created with a capacity of \(i\). Why do that when we can just create \(newP\) with no size and let Java work it out dynamically? And why size \(i\)? Figure 2: A binomial search tree producing the power set of \(\{0,1,2,3\}\). In the loop of line 10 \(i\) counts down from the size of the candidate set, less one, to zero. Therefore at line 14 \(P\) is of size \(i+1\) and we can set the maximum size of \(newP\) accordingly. If we do not set the size Java will give \(newP\) an initial size of 10 and when additions exceed this \(newP\) will be re-sized. By grabbing this space we avoid that. This results in yet another measurable reduction in run-time. Our fourth point is how we remove elements from our sets. In MC we remove the current vertex \(v\) from \(C\) and \(P\) (lines 44 and 45) whereas in MC0 we remove the _last element_ in \(C\) and \(P\) (lines 21 and 22). Clearly \(v\) will always be the last element in \(C\) and \(P\). The code in MC results in a sequential scan to find and then delete the last element, _i.e._, \(O(n)\), whereas in MC0 it is a simple \(O(1)\) task. This raises another question: \(P\) and \(C\) are really stacks so why not use a Java Stack? The Stack class is represented using an ArrayList and cannot be initialised with a size, but has a default initial size of 10. When the stack grows and exceeds its current capacity, the capacity is doubled and the contents are copied across. Experiments showed that using a Stack increased run time by a few percentage points. Typically MC0 is 50% faster than MC. In many cases a 50% improvement in run time would be considered a significant gain, usually brought about by changes in the algorithm. Here, such a gain can be achieved by moderately careful coding.