# Integrating Pareto Optimization into Dynamic Programming
## 4 Experiments
### Evaluation of Strategy SORT
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Algorithm** & **Avg.Comparator Calls** & **Max. Saved Time (s)** & **Separator** \\ \hline \multicolumn{4}{c}{_Trial 1_} \\ \hline Algorithm 1 Quicksort & 26,692.7 & \multirow{3}{*}{-} & No significant gain \\ Algorithm 2 List-Join & 1,137,920.0 & & \\ Algorithm 3 Queue-Join & 21,780.1 & 29.0 & Always use Algorithm 3 \\ Algorithm 4 In-Join & 716,920.0 & - & Algorithm 4 never performs consistently better \\ Algorithm 5 Merge A & **18,043.2** & 11.3 & Use Algorithm 5 when \(\frac{1}{2}\) & \(\frac{1}{2}\) \\ Algorithm 6 Merge B & 18,700.0 & 7.8 & Use Algorithm 6 when \(\frac{1}{2}\) & \(\frac{1}{2}\) \\ Algorithm 7 Merge In-Place & **18,043.2** & 13.4 & Use Algorithm 7 when \(\frac{1}{2}\) & \(\frac{1}{2}\) \\ \hline \multicolumn{4}{c}{_Trial 2_} \\ \hline Algorithm 1 Quicksort & 22,480.0 & \multirow{3}{*}{-} & No significant gain \\ Algorithm 2 List-Join & 50,668,600.0 & & \\ Algorithm 3 Queue-Join & 181,884.0 & 33.2 & When \(\frac{1}{2}\geq 8\) \\ Algorithm 4 In-Join & 31,480,100.0 & - & Algorithm 4 never performs consistently better \\ Algorithm 5 Merge A & **157,102.0** & 44.9 & Use Algorithm 5 when \(\frac{1}{2}\) & \(\frac{1}{2}\) \\ Algorithm 6 Merge B & 161,502.0 & 28.1 & Use Algorithm 6 when \(\frac{1}{2}\) & \(\frac{1}{2}\) \\ Algorithm 7 Merge In-Place & **157,102.0** & 62.7 & Use Algorithm 7 when \(\frac{1}{2}\) & \(\frac{1}{2}\) \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Maximal runtime gain of Algorithms 2–7 compared to Algorithm 1 for randomized uniform Trial Sets 1 and 2. The number of comparator calls was averaged over all data points, ignoring separators. Separators indicate where an algorithm becomes superior to Algorithm 1. Separators for runtime gain can operate solely on the total length of the input list \(N\) and the number of know nsorted sublists \(M\). They are estimated to the nearest integer for linear separation and to two decimal places for logarithmic separation, in both cases assuming the simplest form without any offset variables. Figure 3: Runtime gain of individual data points of for **(a)** Algorithm 3 and **(b)** Algorithm 7 against Algorithm 1 in Trial 2. Points are plotted when one algorithm performed better than the other with point sizes relative to the gained time. Separators are indicated by a black line. In **(b)**, please note that the distribution of red points is less dense above the separator than it is below. correctly in the list. Algorithm 3 performs in guaranteed \(N\) moves, whereas Algorithms 5-7 take asymptotically \(O(N\log(M))\) moves for this case, amortizing the time needed to allocate new memory and destroying the old list on small data. Experiment 2: Here, we test four dynamic programming applications in biosequence analysis as described earlier in this section. Algorithms 2-4 had exhibited a very bad time behavior in the randomized trials, which is also consistent within all new tested sets, therefore posing a strong limit on testable inputs. All tests were executed in 2 steps. To achieve an accurate comparison of the sorting algorithms embedded in the application context, first, all implementations of SORT were tested excluding the runtime of the surrounding code, e.g., the iteration through the search space. After identifying the algorithm with the biggest time gain, possibly using a separator, a second test was performed comparing the full running times, including the full GAP-L programs, of all applications. Intermediate \(N\) and \(M\) or now not uniformly sampled, but arise from the properties of the input and ADP. A summary of the results is presented in Table 4.  
Looking at the sorting performance alone, a clear speed up over Algorithm 1 could be achieved for most test cases. Exceptions are Ali3D and Prob2D, both of which have a very low overall computation time, and Gotoh2D. In all cases, Algorithm 7 (Merge In-Place) was the best performing algorithm. Furthermore, in contrast to the randomized trials, no separator was needed to optimize runtimes.