# Question
Title: For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time?
For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

This question popped into my head yesterday. I've been thinking about it for a bit now, but can't figure it out. I don't really know how I'd google for this, so I'm asking here. Here's what I've come up with:

My first thought was that the answer is yes: For every computable function $f$ the problem "Output $f(n)$ dots" (or create a string with $f(n)$ dots or whatever) can obviously not be solved in $o(f(n))$ time. So we only need to show that it can be solved in $O(f(n))$ time. No problem, just take the following pseudo code:

```
x = f(n)
for i from 1 to x:
    output(".")

```

Clearly that algorithm solves the stated problem. And it's runtime is obviously in $\Theta(f(n))$, so problem solved. That was easy, right? Except no, it isn't because you have to consider the cost of the first line. The above algorithm's runtime is only in $\Theta(f(n))$ if the time needed to calculate $f(n)$ is in $O(f(n))$. Clearly that's not true for all functions1.

So this approach didn't get me anywhere. I'd be grateful for anyone pointing me in the right direction to figure this out properly.

---

1 Consider for example the function $p(n) = \cases{1 & \text{if $n$ is prime} \\ 2 & \text{otherwise}}$. Clearly $O(p(n)) = O(1)$, but there is no algorithm that calculates $p$ in $O(1)$ time.

# Answer
By the Gap theorem (using the formulation from here, search for 'gap'), for any computable unbounded function $g : \mathbb{N} \rightarrow \mathbb{N}$, there exists some increasing (in fact, arbitrarily large) computable function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $DTIME(f(n)) = DTIME(g(f(n))$.

This answers your question in that there exists such an $f$ (infinitely many, in fact): for every computable function $g$ such that $g = o(n)$, there exists some increasing function $f$ such that all problems solvable in $O(f(n))$ time are also solvable in $O(g(f(n)) = o(f(n))$ time. Note that $f$ is not necessarily time-constructible - for the time-constructible case, see the answer by @RanG.

In the Wikipedia formulation (which requires that $g(x) \geq x$), then $g \circ f$ becomes your example, and $f$ needs to be $\omega(n)$ (so you go the other way around - 'problems solvable in $O(g(f(n))$ are also solvable in $O(g(n))$' is the interesting part).

The Wikipedia article does not note that $f$ is increasing and can in fact be arbitrarily large ($f(n) \geq g(n)$ for instance). The article that proves the gap theorem *does* mention and prove this (see here, for example).
> 14 votes

# Answer
> For every computable function $f$ does there exist a problem that can be solved at best in $\Theta(f(n))$ time or is there a computable function $f$ such that every problem that can be solved in $O(f(n))$ can also be solved in $o(f(n))$ time?

If $f$ is a time-constructible function, then the Time Hierarchy Theorem says that there are problems that require $O(f(n))$ time, and cannot be solved with time $o\left (\frac{f(n)}{\log(f(n))}\right )$. Specifically, $$ \text{DTIME}\left ( o\left (\frac{f(n)}{\log(f(n))}\right) \right ) \subsetneq \text{DTIME} \left ( f(n) \right)$$

This consider only decision problems, and does not regard the time it takes to generate the output.
> 14 votes

# Answer
I will try to provide something of a framework in the hopes it grants deeper insight.

When you get to something this fundamental there are unexpected pitfalls everywhere. For example: what is it to "solve" a problem? Often in computer science we consider only the "decision" variant, in which we are given an input and need only to output True or False. You are focusing on the "function" problem.

If you consider O(f(n)) notation as trying to capture how much "work" is needed to solve a problem, using decision instead of function (where output is required) seems better because you cleanly separate the computation from the output formatting.

I don't think this will answer your question, but you may be interested in this: http://en.wikipedia.org/wiki/Time\_hierarchy\_theorem

Also, be careful about the speedup theorem.
> 4 votes

---
Tags: complexity-theory
---


title: Complexity of computing matrix powers

text:
# Question
Title: Complexity of computing matrix powers
I am interested in calculating the $n$'th power of a $n\times n$ matrix $A$. Suppose we have an algorithm for matrix multiplication which runs in $\mathcal{O}(M(n))$ time. Then, one can easily calculate $A^n$ in $\mathcal{O}(M(n)\log(n))$ time. Is it possible to solve this problem in lesser time complexity?

Matrix entries can, in general, be from a semiring but you can assume additional structure if it helps.

Note: I understand that in general computing $A^m$ in $o(M(n)\log(m))$ time would give a $o(\log m)$ algorithm for exponentiation. But, a number of interesting problems reduce to the special case of matrix exponentiation where m=$\mathcal O(n)$, and I was not able to prove the same about this simpler problem.

# Answer
> 12 votes
If the matrix is diagonalizable then taking the $n$th power can be done in time $$O(D(n)+ n\log n)$$ where $D(n)$ is the time to diagonalize $A$.

Just to complete the details, if $A=P^{-1}DP$ with a diagonal $D$, then $$A^n = (P^{-1}DP)^n = P^{-1}D^nP$$

and $D^n$ can be computed by just taking each element of the diagonal (each eigenvalue of $A$) to the $n$th power.

# Answer
> 5 votes
One good way out is Singular Value Decomposition SVD. Given an $n\times n$ real matrix $A$ of  *full rank* , SVD splits it apart as $A=U\Sigma U^T$ where $\Sigma$ is a diagonal matrix, in time $O(n^3)$. By the properties of SVD, $A^m = U \Sigma^m U^T$, so only the diagonal matrix need be exponentiated, and this can be done in $O(n\log m)$ time. Performing the final multiplication $U \times \Sigma^m \times U^T$ takes $O(n^{2.3727})$, so we have altogether $O(n^3 + n \log m)$ operations.

*Update after comment* The point is that once the SVD is found, any power takes only $O(n^{2.3727}+n \log m)$ time to compute by your own C-W algorithm. But this isn't your question.If there were really an $o(M(n)\log(m))$ algorithm, it would convert immediately to an $o(\log n)$ algorithm for integers. I suspect that one such doesn't exist.

---
Tags: algorithms, complexity-theory, time-complexity, computer-algebra
---


# Question
Title: How can I measure the usability of a catalogue?
This question might seems vague but heres the context:

When we are focusing on HCI we would most likely be interested on knowing first how the user usually deals with a certain object. We then try to see how our system could take away one of the tasks he would do himself and try to do it itself.

* The object of my interest here is a simple paper catalogue. How would you measure its usability (paper one).
* Then, how would you map it to a system interface? How would you measure the usability now on the system?
* How would you compare the two usabilities measures?

This question narrows down this approach which is suggested on Stones book - User Interface and Evaluation.

What the catalogue is about is not the point, that why I left it without a description: To avoid suggestions trying to measure what the catalogue is about. My focus here is on the particular mapping of this kind of object on the real world as a simple paper and when it is mapped to a system interface. Assume the catalogue to consist of rows and tables, where each matching row and table gives you a suggestion and you must first reason about each row and each column to see if it suits you (Perhaps you would suggest another template for the catalogue?).

# Answer
In the past I worked on usability of interfaces in the information retrieval area, so I give you some **practical** ideas on how to measure the usability.

You didn't give details of what a "catalogue" is, so I will assume that a *user has a problem (or need) and he is searching your catalogue (in paper or electronic format) for one or more solutions*.

Then you can build a set of problems $P = \\{p\_1,...,p\_n\\}$, and for each problem a set $S^i$ of (possibly weighted) correct solutions: $S^i = \\{ s^{i}\_1,...,s^{i}\_m\\}$.

Then you can setup a test with *real users*.

Every user must solve all the problems in $P$ (in shuffled order) using your catalogue, in one of the two format (paper or electronic).

For each problem, you measure the time spent solving it. At the end you ask the users to give some judgements of satisfaction (using weighted values) on the two catalogues (covering different aspects of satisfaction, for example: "Do you think the catalogue helped you?", "Do you think it is easy to learn how to use it", ....)

Then you can measure (and compare) the *usability* of the two catalogues in term of:

* standard precision and recall of the results found for each problem $p\_i$. *Precision*: number of correct solutions among the total number of answers; *recall*: number of correct solutions found among the total number of correct solutions in $S^i$
* time spent for solving each problem $p\_i$ (*efficiency* of the system);
* user *satisfaction*

For what concerns the mapping between a paper catalogue to a system interface, you can "record" what users do during their searches on the paper catalogue, then try to "simulate" the actions of those users that performed better using an expert system (see expert system design).
> 4 votes

---
Tags: empirical-research, modelling, hci
---


title: Loop invariant for an algorithm

text:
# Question
Title: Loop invariant for an algorithm
I have developed the following pseudocode for the sum of pairs problem:

> Given an array $A$ of integers and an integer $b$, return YES if there are positions $i,j$ in $A$ with $A\[i\] + A\[j\] = b$, NO otherwise.

Now I should state a loop invariant that shows that my algorithm is correct. Can someone give me a hint of a valid loop invariant?

```
PAIRSUM(A,b):
YES := true;
NO := false;
n := length(A);
if n<2 then
  return NO;

SORT(A);
i := 1;
j := n;
while i < j do  // Here I should state my invariant
   currentSum := A[i] + A[j];
   if currentSum = b  then
      return YES;
   else
    if currentSum < b then
      i := i + 1;
    else
      j := j – 1;
return NO;

```

# Answer
First simplification: this algorithm, by inspection, cannot say YES when it shouldn't, since saying YES is immediately after a test verifying that the sum at the current positions is $b$.

Second simplification: It always terminates, since $i$ and $j$ move in a monotone way up and down respectively, and one always moves. Thus, eventually they become equal and the loop ends.

So let's assume that that answer is YES, and $x$ and $y$ are the indices we are interested in, after sorting, with $x$ as small as possible and then $y$ as large as possible (we may have several possible pairs with the right sum). Here is the invariant:

* At the start of the loop, $i\le x$ and $j\ge y$.

If $i=x$ and $j=y$, then the algorithm will stop and say YES. The loop invariant is trivial at the start, and also trivial when $i\<x$ and $j\>y$. But if $i=x$, and $j\>y$, then, since the array is sorted $A\[i\]+A\[j\]\>b$, because of how $y$ was selected. So $j$ decreases in all future iterations until it reaches $y$. The other case, where $j$ gets to $y$ first is symmetric.

As noted above, the algorithm always terminates, which implies the algorithm will actually say YES, so we are done.

**Edit:** Since this question is about proof writing, here is another option, which I think is more confusing and more gritty. I do not know if Tony Hoare would approve or not.

Here is the invariant: A the top of the loop,

* If $s\<i$, then, for any $x\in \[n\]$, $A\[s\] + A\[x\] \neq b$
* If $t\>j$, then, for any $x\in \[n\]$, $A\[x\] + A\[t\]\neq b$

Again, this holds vacuously at the beginning. Now we check some cases:

* If $i = j$, then in any pair of indices $x$ and $y$ at least one of $x$ or $y$ is smaller than $i$ or bigger than $j$. This rules out the input being a YES. The loop ends and says NO, so we are in good shape.
* Assume the loop did not end. If $A\[i\] + A\[j\] = b$, the answer is YES, and the algorithm works.
* Assume $A\[i\] + A\[j\] \neq b$.
* Subcase: If there is a $j'$, by hypothesis $j'\<j$, such that $A\[i\] + A\[j'\] = b$, then $A\[j'\] \< A\[j\]$ because the array was sorted, so $A\[i\] + A\[j\] \> b$, which causes $j$ to decrease. This shows that the invariant is maintained for $i$. To see it for $j$, just note that if there is an $x$ such that $A\[x\] + A\[j\] = b$, then $x \< i$, which is ruled out by the inductive hypothesis.
* Subcase: If there is a $i'$, by hypothesis $i'\>i$, such that $A\[i'\] + A\[j\] = b$, then $A\[i'\] \> A\[i\]$ because the array was sorted, so $A\[i\] + A\[j\] \< b$, which causes $i$ to increase. This shows that the invariant is maintained for $j$. To see it for $i$, just note that if there is an $x$ such that $A\[i\] + A\[x\] = b$, then $x \> j$, which is ruled out by the inductive hypothesis.
* Subcase: If neither of the other two cases holds, then the invariant is maintained trivially.

Finally, we note that the gap between $i$ and $j$ always gets smaller, so they must eventually become equal, and the algorithm will stop.

*Remarks:* This is the exact same argument, but more difficult to follow. You too can write proofs like this using some expert techniques:

* Don't say what the algorithm does. Here, if the input is a YES, the algorithm ALWAYS gives you certifying indices that are as close to the ends as possible. The 2nd proof cleverly hides this in a case analysis.
* Don't give names to things. Having hidden what the algorithm does, also don't name the stopping point.
* Don't factor out easy cases. This algorithm clearly works for NO instances. By not noting that up front, we get a more complicated invariant.
> 5 votes

# Answer
Perhaps something like this?

> After `k` iterations of the loop, `A[i...j]` contains a sorted subarray of size `n - k`, with `k` of the original elements, none of which summing to `b` with any other element of `A`, having been removed.

Perhaps a clearer way of stating this is simply:

> After `k` iterations of the loop body, for `0 <= k < n`, `A[i...j]` is a sorted (contiguous) subarray of `A[1...n]` (whose elements are in the same order and have the same value as before the first iteration) of the loop body containing `k` elements (i.e., `i + j = k + 1`) such that `A[1...n]` contains a desired pair of elements if and only if `A[i...j]` does, as well.

This loop invariant is useful because, if the loop finishes (i.e., reaches the termination condition), then `A` is the sorted array with one element, and we can conclude that there is no pair of elements in `A`.

Here is a proof sketch/idea for this invariant:

* Before the loop, `A[1...n]` is a sorted array and `i = 1`, `j = n`. Therefore, the loop invariant is guaranteed to after `k = 0` iterations of the loop body.
* Assume that the loop invariant holds true for `k` up to and including `k'`.
* We now show that the loop invariant holds for `k' + 1`. There are three cases for the behavior of the loop body during the iteration corresponding to `k = k' + 1`:
    + `A[i] + A[j] = b`, in which case the loop correctly returns `YES` and there is no iteration after this iteration of the loop;
    + `A[i] + A[j] < b`, in which case we can safely discard the smallest element of `A`, `A[i]`. To see this, note that since `A[j]` is the largest element in `A`, if the sum of it and another element in `A` is smaller than `b`, then sum of that other element and any element of `A` is also guaranteed to be less than `b`.
    + `A[i] + A[j] > b`, in which case we can safely discard the largest element of `A`, `A[j]`. The reasoning is similar to that for the case `A[i] + A[j] < b`.
* After termination of the loop body, `i = j` and so `A` contains only one element. Since `A` now contains only one element, it is trivially the case that `A` does not contain two elements summing to `b`.

**Demonstrating the sufficiency of the loop invariant to show that there is no solution after termination of the loop**

This addresses a question raised in the comments by Raphael, here is some clarification on why this loop invariant should be sufficient.

For the loop to terminate, we must have `i = j`. Notice also that this loop always terminates, either by correctly emitting `YES` if a match is found, or by removing array elements until only one remains (by either incrementing `i` or decrementing `j`). This termination argument is not given in the sketch above, but should be straightforward.

Since `i = j`, `A` is a sorted subarray of size one. Because no array of size 1 satisfies the requirement that there exist $x, y$ (note that I am interpreting this to mean *unique* $x, y$, since otherwise the algorithm provided is incorrect; consider `A = [1]` and `b = 2`) where $A\[x\] + A\[y\] = b$, and since by the loop invariant we know that no element `A[k]`, where `k != i = j`, could be added to any element `A[k']`, where `k' != k`, to achieve sum `b`, this completes the proof idea.

Assumptions/facts used for termination condition:

* The question was interpreted correctly, i.e, $x$ and $y$ are distinct; you have to add elements at different positions in the original array.
* `i = j` after the (normal) termination of the loop body, and the loop always terminates;
* There are not two distinct $x$ and $y$ between `i` and `j` if `i = j`; there aren't two indices in a subarray of size 1.
* By the loop invariant, for `k != i = j`, there is no way to add `A[k]` to any `A[k']`, `k != k'`, to get `b`; we have only thrown out, by incrementing `i` and decrementing `j`, elements which couldn't possibly sum to `b` with any element of the original array.

Please feel free to help out if I continue to be missing something subtle.
> 3 votes

# Answer
There are always infinitely many valid loop invariants. The trick is to find one that suffices to prove what you want to prove about the algorithm, and that you can prove (usually by induction over the number of loop iterations).

There are three parts in proving the correctness of this algorithm:

* The algorithm never performs an incorrect step. Here, the potential incorrect steps are to access an array element outside the bounds of the array.
* When the algorithm returns `YES` or `NO`, this output is correct.
* The algorithm terminates for every input.

For correctness, you need to prove that $1 \le i \le n$ and $1 \le j \le n$. This had better be part of your invariant. Given the loop condition $i \< j$, you can condense this to $1 \le i \< j \le n$ at the entry into the loop body. This condition is not true when the loop test is reached at the end, but it may come in useful to notice that $i \le j$ (because inside the loop body, with $i \< j$, $i$ and $j$ only change by $1$, which can at worst turn this strict inequality into an equality).

When `return YES` is executed, $A\[i\] + A\[j\] = b$ is apparent. So this part doesn't need anything particular to be proved.

When the last `return NO` statement is executed, meaning that the loop terminated normally (and so $i \< j$ is false), you need to prove that $\forall i, \forall j, A\[i\] + A\[j\] \ne b$. This property is obviously not true in general: it doesn't hold if the answer is `YES`. You need to *strengthen* this property: you have a special case, which needs to be generalized. This is a typical case of a property that applies only to the part of the array that has been traversed already: the loop is constructed so that if $(x,y)$ is a previous value of $(i,j)$ (i.e. $1 \le x \le i$ and $j \le y \le n$ and $(x,y) \ne (i,j)$) then $A\[x\] + A\[y\] \ne b$. This had better be expressed in the loop invariant.

Are we done there? Not quite; all we know on the normal loop termination is that $\forall x \le i, \forall y \le j, A\[x\] + A\[y\] \ne b$. What if we had $x \> i$ and $y \le j$, or $x \le i$ and $y \> j$: could we have $A\[x\] + A\[y\] \ne b$? That's difficult to tell without more information. In fact, we'd better distinguish some cases when $A\[x\] + A\[y\] \> b$ and the cases when $A\[x\] + A\[y\] \< b$. With these properties, we can use the fact that the array is sorted to deduce facts about other positions in the array; with only $\ne b$, we have nothing to work on. We don't know which way $A\[x\] + A\[y\]$ lies for some random $x \< i$ and $y \> j$; but we do know what happens at the boundary: if $i$ is incremented, it's because $A\[i\] + A\[j\]$ is too small, and if $j$ is decremented, it's because $A\[i\] + A\[j\]$ is too large. Think what loop invariant could express this; I'll give a possibility below.

Note that this property doesn't directly give you the desired condition for the `return NO` statement; you'll still need to look at what happened in the last run of the loop, or alternatively to prove a stronger loop invariant that takes a closer look at when $A\[x\] + A\[y\] \< b$ and when $A\[x\] + A\[y\] \> b$.

Finally, for termination, you need to relate $i$ and $j$ with the number of iterations through the loop. Here, this is simple: either $i$ or $j$ moves at each turn, so $j - i$ decreases by $1$ at each loop iteration; you don't need to use a loop invariant to prove this.

We've obtained the following invariant: $$ \begin{array}{l} 1 \le i \le j \le n \wedge \\ (\forall x \< i, \forall y \< j, A\[x\] + A\[y\] \ne b) \wedge \\ (\forall x \< i, A\[x\] + A\[j\] \< b) \wedge \\ (\forall y \> j, A\[i\] + A\[y\] \> b) \end{array}$$
> 3 votes

# Answer
There is no foolproof way to derive a helpful invariant; note that the problem is not computable (otherwise we could solve the halting problem). Therefore, your are back to trial and error with heuristics trained by experience. See Gilles' answer for an exemplary thought process. In general, you need the desired *post condition* (i.e. output specification) first and find an invariant that implies it (together with the negated loop condition).

Here is what I think works:

$\qquad \begin{align} I = &\phantom{\land}\ A \text{ is sorted and has not been changed} \\ &\land\ 1 \leq i,j \leq n \\ &\land\ j \geq i \\ &\land\ \forall i' \lt i.\ \forall j' \gt j.\ A\[i'\] + A\[j'\] \neq b \\ &\land\ \forall i' \lt i.\ b \> A\[i'\] + A\[j\] \\ &\land\ \forall j' \gt j.\ b \< A\[i\] + A\[j'\] \end{align}$

That the latter three clauses are actually maintained by the loop -- assuming you do not terminate with YES which is trivially correct -- is tedious to show because they are heavily interdependent and $i,j$ can switch roles.

In the end, you get $i=j$ which allows to combine the last two clauses to the fact that the last element $A\[i\]$ does not sum up to $b$ with any other element. Combination between elements from left and right are excluded by clause three. Finally, two elements left of $i$ can not sum up to $b$ because of clause four and one, and similarly for two elements right of $i$.

If you do the proofs, make sure to follow the rules of Hoare logic closely.
> 2 votes

---
Tags: algorithms, proof-techniques, loop-invariants
---


# Question
Title: Does cooperative scheduling suspend processes when they perform an  I/O operation?
Many operating systems references say that with cooperative (as opposed to preemptive) multitasking, a process keeps the CPU until it explicitly voluntarily suspends itself. If a running process performs an I/O request that cannot be immediately satisfied (e.g., requests a key stroke that is not yet available), does the scheduler suspend it, or does it really keep the CPU until the request can be serviced?

\[Edited to replace "blocks on i/o" with "performs an I/O request that cannot be immediately satisfied."\]

# Answer
In a truly "cooperative" setting, and if there was no hardware protection, a process could certainly block on I/O and not relinquish control until the I/O was done (or never relinquish control at all). For example, Windows 3.1 was this way: if a single user process wanted to take over the entire computer, and prevent anything else from running, it could.

But on a system with multitasking you expect the system API I/O commands to relinquish control of the processor when they are called. So when a running process blocks on I/O, assuming that the process uses the normal system APIs, other processes will be allowed to run until the I/O is complete, and eventually the original process will resume once the I/O is done. In other words, calling a blocking I/O function is one way that a process on a cooperative system can voluntarily suspend itself.
> 15 votes

# Answer
> If a running process blocks on i/o

Blocking on IO is pretty much equivalent to suspending your process. In the context of the linux kernel, executing some IO system call such as `read()` will cause a `sysenter` or interrupt handler to trigger to look after that IO, calling `do_sys_read()` ultimately. Here, if the current request cannot immediately be satisfied, the function calls `sched()` which then may execute another process.

In the context of a co-operative system, I would expect that when you make a system call for some IO reason, if the request cannot be satisfied the kernel picks another task and executes that. This document provides some background - basically, if you waited on IO, you could be hung forever waiting for that IO. The idea of co-operative scheduling being that you frequently call `sched()` or the equvalent relinquish-the-cpu method, if doing CPU-intensive tasks.

Kernel-mode considerations get more interesting. On architectures where they are available such as certain embedded platforms, interrupts handlers will still be invoked in response to hardware or software interrupts. It is usually possible, implementation-wise, to disable interrupt handling, but that also has drawbacks.
> 11 votes

# Answer
In the cooperative scheduling (preferably `cooperative multitasking`) model, there is no concept of a scheduler in a sense that the operating system does not have any control of how long the process runs.

An application programmed correctly would voluntarily give up the CPU on I/O. But, badly written applications might just keep waiting on I/O, thereby blocking other processes.

PS: This approach was later given up by most of the OS in favor of preemptive-scheduling (which had an external scheduler) and now we have all sorts of different scheduling algorithms used by different OS.

**EDIT:** My answer was based on the scheduling as described in its original form (years ago :P). As Gilles commented some systems still use cooperative scheduling. And there is a scheduler. I am not sure if those systems use COS in its pure and original form.
> 4 votes

# Answer
Co-operative multitasking implies that an executing context must explicitly relinquish control to the scheduler, and if it wishes, can prevent a context switch from occurring.

Most implementations explicitly perform a context switch for any system call that does not return promptly, and often even if they do, to increase the fairness of processor allocation.

Usually it is only possible for failed processes (or intentionally denying service to the remainder of the system) to prevent frequent task-switching.

Pre-emption, as explained by Gilles, is a limitation of the architecture of the system that prevents timed interruption of the active task and forced context switches.
> 4 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Round-robin scheduling: allow listing a process multiple times?
In a round-robin scheduler, adding a process multiple times to the process list is a cheap way to give it higher priority.

I wonder how practical an approach this might be. What benefit does it have over other techniques such as giving the process a longer time slice (benefit: less switching time) or maintaining a separate list of high-priority processes. In particular, how does listing a process multiple times influence fairness and reactivity?

(From exercise 2.16 in Andrew Tanenbaum's *Operating Systems: Design and Implementation* 1st ed.)

# Answer
> 4 votes
The advantage of this approach is that round robin scheduling is very efficient, so you don't need to rely on a more complex scheduler, which would steal cycles. Introducing longer time slices for higher priority processes would decrease the responsiveness of other threads and make it harder for the OS to jump in to deal with an interrupt and so forth. Maintaining separate lists of processes would require a much more complex scheduler, which would be more expensive in terms of cycles. I don't see how there would be any problem with fairness, though. I guess the problem is that the granularity is fairly course: processes can only have integer multiples of the basic time-slice.

One negative point is that removing a process would be more costly, as each occurrence of the process would have to be removed from the queue. Perhaps this can be done lazily, though.

# Answer
> 2 votes
Adding the task to a round-robin scheduling queue multiple times opens up the problem of ensuring that the entries remain reasonably evently distributed. This is easy to ensure if the system does not permit dynamic task creation or deletion, but not possible in general.

In addition to the more complex process of removing the items from the queue, the eventual skewing of the process entries in the queue will result in unbalanced behaviour that is easier to make fair with multiple priority levels.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: A continuous optimization problem that reduces to TSP
Suppose I am given a finite set of points $p\_1,p\_2,..p\_n$ in the plane, and asked to draw a twice-differentiable curve $C(P)$ through the $p\_i$'s, such that its perimeter is as small as possible. Assuming $p\_i=(x\_i,y\_i)$ and $x\_i\<x\_{i+1}$, I can formalize this problem as:

*Problem 1 (edited in response to Suresh's comments)* Determine $C^2$ functions $x(t),y(t)$ of a parameter $t$ such that the arclength $ L = \int\_{\[t \in 0,1\]} \sqrt{x'^2+y'^2}dt$ is minimized, with $x(0) = x\_1, x(1) = x\_n$ and for all $t\_i: x(t\_i) = x\_i$, we have $y(t\_i)=y\_i)$.

> How do I prove (or perhaps refute) that Problem 1 is NP-hard?

*Why I suspect NP-hardness*  Suppose the $C^2$ assumption is relaxed. Evidently, the function of minimal arclength is the Travelling Salesman tour of the $p\_i$'s. Perhaps the $C^2$ constraint only makes the problem much harder?

*Context*  A variant of this problem was posted on MSE. It didn't receive an answer both there and on MO. Given that it's nontrivial to solve the problem, I want to establish how hard it is.

# Answer
> 12 votes
The differentiability requirement doesn't change the nature of the problem: requiring $\mathcal{C}^0$ (continuity) or $\mathcal{C}^{\infty}$ (infinite differentiability) gives the same lower bound for the length and the same order of points, and is equivalent to solving the traveling salesman problem.

If you have a solution to the TSP, you have a $\mathcal{C}^0$ curve that goes through all the points. Conversely, suppose you have a $\mathcal{C}^0$ curve of finite length that goes through all the points, and let $p\_{\sigma(1)}, \ldots, p\_{\sigma(n)}$ be the order in which it traverses the points and $t\_1,\ldots,t\_n$ the corresponding parameters (if the curve traverses a point more than once, pick any of the possible values of $t$). Then the curve built from $n$ segments $\[p\_{\sigma(1)},p\_{\sigma(2)}\], \ldots, \[p\_{\sigma(n-1)},p\_{\sigma(n)}\], \[p\_{\sigma(n)},p\_{\sigma(1)}\]$ is shorter, because for each segment a straight line is shorter than any other curve that connects the point. Thus for every ordering of the points, the best curve is a TSP solution, and the TSP solution provides the best ordering of the points.

Let's now show that requiring the curve to be $\mathcal{C}^{\infty}$ (or $\mathcal{C}^k$ for any $k$) doesn't change the best ordering of points. For any TSP solution of total length $\ell$ and any $\epsilon \> 0$, we can round every corner, i.e. build a $\mathcal{C}^{\infty}$ curve that traverses the points in the same order and has a length of at most $\ell + \epsilon$ (the explicit construction relies on algebraic functions and $e^{-1/t^2}$ to define bump functions and from those smooth connections between curve segments such as $e^{1-1/x^2} (x-e^{-1/(1-x)^2})$ which connects with $y=0$ at $x=0$ and with $y=x$ at $x=1$; it is tedious to make these explicit, but they are computable); hence, the lower bound for a $\mathcal{C}^{\infty}$ curve is the same as for a collection of segments (note that the lower bound is not reached in general).

---
Tags: complexity-theory, np-hard, optimization, computable-analysis
---


# Question
Title: How to approach Vertical Sticks challenge
This problem is taken from interviewstreet.com

We are given an array of integers $Y=\\{y\_1,...,y\_n\\}$ that represents $n$ line segments such that endpoints of segment $i$ are $(i, 0)$ and $(i, y\_i)$. Imagine that from the top of each segment a horizontal ray is shot to the left, and this ray stops when it touches another segment or it hits the y-axis. We construct an array of n integers, $v\_1, ..., v\_n$, where $v\_i$ is equal to length of ray shot from the top of segment $i$. We define $V(y\_1, ..., y\_n) = v\_1 + ... + v\_n$.

For example, if we have $Y=\[3,2,5,3,3,4,1,2\]$, then $\[v\_1, ..., v\_8\] = \[1,1,3,1,1,3,1,2\]$, as shown in the picture below:

For each permutation $p$ of $\[1,...,n\]$, we can calculate $V(y\_{p\_1}, ..., y\_{p\_n})$. If we choose a uniformly random permutation $p$ of $\[1,...,n\]$, what is the expected value of $V(y\_{p\_1}, ..., y\_{p\_n})$?

If we solve this problem using the naive approach it will not be efficient and run practically forever for $n=50$. I believe we can approach this problem by indepdently calculating the expected value of $v\_i$ for each stick but I still need to know wether there is another efficient approach for this problem. On what basis can we calculate the expected value for each stick independently?

# Answer
> 25 votes
Imagine a different problem: if you had to place $k$ sticks of equal heights in $n$ slots then the expected distance between sticks (and the expected distance between the first stick and a notional slot $0$, and the expected distance between the last stick and a notional slot $n+1$) is $\frac{n+1}{k+1}$ since there are $k+1$ gaps to fit in a length $n+1$.

Returning to this problem, a particular stick is interested in how many sticks (including itself) are as high or higher. If this number is $k$, then the expected gap to its left is also $\frac{n+1}{k+1}$.

So the algorithm is simply to find this value for each stick and add up the expectation. For example, starting with heights of $\[3,2,5,3,3,4,1,2\]$, the number of sticks with a greater or equal height is $\[5,7,1,5,5,2,8,7\]$ so the expectation is $\frac96+\frac98+\frac92+\frac96+\frac96+\frac93+\frac99+\frac98 = 15.25$.

This is easy to program: for example a single line in R

```
V <- function(Y){ (length(Y) + 1) * sum( 1 / (rowSums(outer(Y, Y, "<=")) + 1) ) }

```

gives the values in the sample output in the original problem

```
> V(c(1,2,3))
[1] 4.333333
> V(c(3,3,3))
[1] 3
> V(c(2,2,3))
[1] 4
> V(c(10,2,4,4))
[1] 6
> V(c(10,10,10,5,10))
[1] 5.8
> V(c(1,2,3,4,5,6))
[1] 11.15

```

# Answer
> 11 votes
**Henry's solution is both simpler and more general than this one!**

---

$E\[V\]$ is roughly half the expected number of comparisons performed by randomized quicksort.

**Assuming the sticks have distinct heights**, we can derive a closed-form solution for $E\[Y\]$ as follows.

For any indices $i\le j$, let $X\_{ij} = 1$ if $Y\_j = \max\\{Y\_i,...,Y\_j\\}$ and $X\_{ij}=0$ otherwise. (If the elements of $Y$ are *not* distinct, then $X\_{ij}=1$ means that $Y\_j$ is *strictly* greater than every element of $\\{Y\_i, \dots, Y\_{j-1}\\}$.)

Then for any index $j$, we have $v\_j = \sum\_{i=1}^j X\_{ij}$ (Do you see why?) and therefore $$ V = \sum\_{j=1}^n v\_j = \sum\_{j=1}^n \sum\_{i=1}^j X\_{ij}. $$

Linearity of expectation immediately implies that $$ E\[V\] = E\bigg\[\sum\_{1\le i\le j\le n} X\_{ij}\bigg\] = \sum\_{1\le i\le j\le n} E\[X\_{ij}\]. $$

Because $X\_{ij}$ is either $0$ or $1$, we have $E\[X\_{ij}\] = \Pr\[X\_{ij}=1\]$.

Finally—and this is the important bit—because the values in $Y$ are **distinct and** permuted uniformly, each element of the subset $\\{Y\_i,...,Y\_j\\}$ is equally likely to be the *largest* element in that subset. Thus, $\Pr\[X\_{ij}=1\] = \frac{1}{j-i+1}$. (If the elements of $Y$ are not distinct, we still have $\Pr\[X\_{ij}=1\] \le \frac{1}{j-i+1}$.)

And now we just have some math. $$ \begin{aligned} E\[V\] &= \sum\_{j=1}^n \sum\_{i=1}^j E\[X\_{ij}\] & \[\text{linearity}\]\\ &= \sum\_{j=1}^n \sum\_{i=1}^j \frac{1}{j-i+1} & \[\text{uniformity}\]\\ &= \sum\_{j=1}^n \sum\_{h=1}^j \frac{1}{h} & \[h = j-i+1\]\\ &= \sum\_{h=1}^n \sum\_{j=h}^n \frac{1}{h} & \[1\le h\le j\le n\]\\ &= \sum\_{h=1}^n \frac{n-h+1}{h}\\ &= \left((n+1)\sum\_{h=1}^n \frac{1}{h}\right) - \left(\sum\_{h=1}^n 1\right)\\ &= (n+1)H\_n - n \end{aligned} $$ where $H\_n$ denotes the $n$th harmonic number.

Now it should be trivial to compute $E\[V\]$ (up to floating point precision) in $O(n)$ time.

# Answer
> 5 votes
As mentioned in the comments, you can use Linearity of Expectation.

Sort the $y$: $y\_1 \le y\_2 \le \dots \le y\_n$.

For each $y\_i$ consider the expected value of $v\_i = E\[v\_i\]$.

Then $E\[\sum\_{i=1}^{n} v\_i\] = \sum\_{i=1}^{n} E\[v\_i\]$

One straight-forward and naive way to compute $E\[v\_i\]$ would be first fix a position for $y\_i$. Say $j$.

Now compute the probability that at position $j-1$ you have a value $\ge y\_i$.

Then the probability that at $j-1$ you have a value $\lt y\_i$ and at $j-2$ you have a value $\ge y\_i$

and so on which will allow you to compute $E\[v\_i\]$.

You can probably make it faster by actually doing the math and getting a formula (I haven't tried it myself, though).

Hope that helps.

# Answer
> 3 votes
Expanding on the answer of @Aryabhata:

Fix an $i$, and assume the item $y\_i$ is at position $j$. The exact value of the height is immaterial, what matters is whether the items are greater than or equal to $y\_i$ or not. Therefore consider the set of items $Z^{(i)}$, where $z\_k^{(i)}$ is 1 if $y\_k\geq y\_i$, and $z\_k^{(i)}$ is 0 otherwise.

A permutation on the set $Z^{(i)}$ induces an corresponding permutation on the set $Y$. Consider for instance the following permuation of the set $Z^{(i)}$: "01000(1)$\dots$". The item $z\_i^{(i)}$ is the one is brackets, at position $j$, and the items denoted by "$\dots$" don't matter.

The value of $v\_i$ is then 1 plus the length of the run of consective zeros just to the left of $z\_i^{(i)}$. It follows that $\mathbb{E}\left(v\_i\right)$ is actually 1 plus the expected length of consecutive zeors, until the first "1" is met, if we pick at most $j-1$ bits from the set $Z^{(i)} \setminus \\\{z\_i^{(i)} \\\} $(without replacement). This is reminiscent of the geometric distribution, except that it would be without replacement (and bounded number of draws). The expectation is to be taken on $j$ **as well**, as a uniform choice on the set of positions $\\{1,\dots,n \\}$.

Once this is computed (along these lines), we can follow the lines of @Aryabhata's answer.

# Answer
> -2 votes
I dont really understand what do you demend, from tags it seems you are looking for an algorithm.

if so, what is the expected time complexity? by saying: "If we solve this problem using the naive approach it will not be efficient and run practically forever for n=50." it seems to me that your naive approach solves it in exponential time.

i do have a O(n^2) algorithm in mind tho.

```
assume int y[n], v[n] where v[i] initialized with 1; as described in the question
for (i=1;i<n;i++)
   for ( j=i-1 ; j>=0 && y[j]<y[i] ; j--) v[i]++;

```

---
Tags: algorithms, probability-theory
---


# Question
Title: Lower bounds of calculating a function of a set
Having a set $A$ of $n$ elements, let's say I want to calculate a function $f(A)$ that is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

For example, $f$ could be the sum or the average.

Is there a result that proves that, under some conditions, the time necessary to a deterministic Turing machine to compute $f$ will be $\Omega(n)$?

# Answer
You have to be specify the model of computation and properties of $f$. In the following argument I will state the assumptions that I need. It can be generalized a little bit further but I think it should be sufficient to give you the idea.

Assume that the machine $M$ never reads the value of one of the members of $A$ (a fixed set, and $A$ is given as a list). Assume further that $A$ is an input such that changing the value of its $i$th member does not change $M$'s answer. Assume further that $f$ is sensitive to all parts of the input, i.e. depends on very member of $A$ (i.e. it is possible to change any member of $A$ to something else to obtain a new input $A'$ s.t. value of $f$ on $A$ and $A'$ are different).

We can use an adversary argument to show that the machine cannot compute the right answer by changing the value of that member of $A$ to obtain $A'$ else s.t. the value of $f$ is different. The value of $M$ on these two sets is the same, so one of them must be false and therefore $M$ cannot compute $f$ correctly.

Therefore any machine $M$ that computes $f$ will need to read all of the input which takes $\Omega(n)$ steps.

(On the other hand, assume that we have a nondeterministic random access machine, and we want to compute OR of the bits in the input. We can nondeterministicly guess a bit and check if that is 1, if it is 1, we output 1. This machine reads only a single bit of the input in $O(\lg n)$ steps and correctly answers the problem. So without assumptions on $M$ and $f$ the result does not hold.)
> 7 votes

---
Tags: complexity-theory
---


# Question
Title: Attack on hash functions that do not satisfy the one-way property
I am revising for a computer security course and I am stuck on one of the past questions. Here is it:

> Alice ($A$) wants to send a short message $M$ to Bob ($B$) using a shared secret $S\_{ab}$ to authenticate that the message has come from her. She proposes to send a single message with two pieces: $$ A \to B: \quad M, h(M \mathbin\parallel S\_{ab})$$ where $h$ is a hash function and $\parallel$ denotes concatenation.
>
> 1. Explain carefully what Bob does to check that the message has come from Alice, and why (apart from properties of $h$) he may believe this.
> 2. Suppose that $h$ does not satisfy the one-way property and it is possible to generate pre-images. Explain what an attacker can do and how.
> 3. If generating pre-images is comparatively time-consuming, suggest a simple countermeasure to improve the protocol without changing $h$.

I think I know the first one. Bob needs to take a hash of the received message along with his shared key and compare that hash with the hash received from Alice, if they match then this should prove Alice sent it.

I am not sure about the second two questions though. For the second one, would the answer be that an attacker can simply obtain the original message given a hash? I'm not sure how that would be done though.

# Answer
> For the second one, would the answer be that an attacker can simply obtain the original message given a hash?

Well, the message $M$ is already given to the adversary (it is sent to Bob over an insecure channel), so he needs not find it. To break the scheme he needs to send a new pair $M^\*, h(M^\*\\|S\_{ab})$ such that Bob will accept $M^\* \ne M$ as the message sent by Alice.

*For the second question:* If it is easy to generate pre-images of $h$, the adversary might be able to learn the secret key $S\_{ab}$ from $h(M\\| S\_{ab})$ thus breaking the scheme.
<sup>(Note this might not be trivial. The inverting process might output $M\_1, S\_1$ such that $h(M\\|S\_{ab})=h(M\_1\\|S\_1)$, but this is not useful for the adversary.. Furthermore, if the adversary try again to invert $h$, he might get the same pre-image.)</sup>

*For the third question:* Now we assume inverting $h$ takes a lot of time, so let's make the adversary's life harder by requiring him to invert it many times in order to break the scheme. For instance, use the hash $k$ times $h(h(h(....h(M\\|S\_{ab})..))$. Other solutions exist as well.
> 7 votes

---
Tags: cryptography, hash, one-way-functions
---


title: Creating a Self Ordering Binary Tree

text:
# Question
Title: Creating a Self Ordering Binary Tree
I have an assignment where I need to make use a binary search tree and alter it to self order itself such that items that are accessed the most (have a higher priority) are at the top of the tree, the root being the most accessed node.

The professor gave me the BST and node struct to work with, but trying to get my head around the algorithm to update the tree as things are being inserted is confusing me.

I know that as the insert is happening, it checks if the current node's data is less or greater than the current node, then recursively goes in the correct direction until it finds a null pointer and inserts itself there. and after it is inserted it increases the priority by 1.

```
template <class Type>
void BinarySearchTree<Type> ::  insert( const Type & x, BinaryNode<Type> * & t )
{
    if( t == NULL )
        t = new BinaryNode<Type>( x, NULL, NULL );
    else if( x < t->element )
        insert( x, t->left );
    else if( t->element < x )
        insert( x, t->right );
    else
        t->priority++;  // Duplicate; do nothing for right now
}

```

Now I need to figure out when the node is equal, how to re-order the tree so that the current node (who is equal to an already existing node) finds the existing node, increases that node's priority, then shifts it up if the root is a lower priority.

I think I have the idea down that the AVL logic would work, and when a shift would take place, it would be a single rotation right or a single rotation left.

Here's where I'm confused, don't really know where to start with creating an algorithm to solve the problem. Since the AVL algorithm works with keeping track of the balance of a tree, then rotating nodes left or right accordingly, this tree doesn't need to worry about being balanced, just that the nodes with the highest priority not have children with a higher priority.

# Answer
> 13 votes
Just two pointers:

1. If you want to actually combine the ideas of priority queues and binary search trees, think about combining heap and BST in one structure.
2. There is the concept of self-organising lists. The idea is to move recently accessed element to (or towards the) front in order to speed up future accesses to the same element, thusly "learning" the element distribution over time (with quality depending on the particular implementation). Maybe you can adapt this to trees?

---

**Spoiler:** Follow below links only if you have not been able to come up with something yourself.

> 1. This is called a treap.
> 2. Splay trees implement this idea.

# Answer
> 2 votes
Have a look at splay trees, they are really what you need. You would have to modify the splay function, not to move each accessed node all the way to the tree, but slowly upwards

---
Tags: algorithms, data-structures, binary-trees, search-trees
---


# Question
Title: Why does the splay tree rotation algorithm take into account both the parent and grandparent node?
I don't quite understand why the rotation in the splay tree data structure is taking into account not only the parent of the rating node, but also the grandparent (zig-zag and zig-zig operation). Why would the following not work:

As we insert, for instance, a new node to the tree, we check whether we insert into the left or right subtree. If we insert into the left, we rotate the result RIGHT, and vice versa for right subtree. Recursively it would be sth like this

```
Tree insert(Tree root, Key k){
    if(k < root.key){
        root.setLeft(insert(root.getLeft(), key);
        return rotateRight(root);
    }
    //vice versa for right subtree
}

```

That should avoid the whole "splay" procedure, don't you think?

# Answer
> 31 votes
The simpler balancing algorithm can require $\Omega(n)$ amortized time per rotation in the worst case. Suppose the tree is just a totally unbalanced path of right children; no node has a left child. The only leaf in this tree is the tree with the maximum key. If you rotate this step by step up to the root, you've used $n-1$ rotations, and the resulting tree is still totally unbalanced.

Now suppose we repeatedly promote every node in the tree, one at a time, in decreasing key order, using the simpler algorithm. After all the promotions are done, the tree has returned to its original state, and we have used roughly $n^2/2$ rotations. Thus, on average, each promotion in this sequence requires $\Omega(n)$ rotations; moreover, I can repeat this pattern forever. So the amortized cost for this promotion algorithm is $\Omega(n)$.

This bad example appears in Sleator and Tarjan's original splay tree paper.

The splay algorithm considers not just one node at a time, but two nodes at a time. In particular, if the node $x$ being splayed is the right child of a right child, the splay algorithm first rotates $x$'s parent, and only then rotates $x$.

The advantage of this more complex algorithm is that it not only brings the accessed node to the root, but *also moves every ancestor of the accessed node roughly halfway to the root*, but never moves any node more than a constant number of levels away from the root.

Sleator and Tarjan prove that the amortized time per splay is only $O(\log n)$. (The proof uses a tedious case analysis using a magic potential function; honestly, if you're curious, just read the original paper.) Of course a single splay can take $\Omega(n)$ time, but starting with an empty tree, you have to perform a *lot* of insertions and splays to set up such a bad example.

More briefly: Splaying moves nodes upward quickly and downward slowly.

---
Tags: algorithms, data-structures, binary-trees, search-trees
---


# Question
Title: Efficiently selecting the median and elements to its left and right
Suppose we have a set $S = \\{ a\_1,a\_2,a\_3,\ldots , a\_N \\}$ of $N$ coders.

Each Coders has rating $R\_i$ and the number of gold medals $E\_i$, they had won so far.

A Software Company wants to hire exactly three coders to develop an application.

For hiring three coders, they developed the following strategy:

1. They first arrange the coders in ascending order of ratings and descending order of gold medals.
2. From this arranged list, they select the three of the middle coders. E.g., if the arranged list is $(a\_5,a\_2,a\_3,a\_1,a\_4)$ they select $(a\_2,a\_3,a\_1)$ coders.

Now we have to help company by writing a program for this task.

**Input:**

The first line contains $N$, i.e. the number of coders.

Then the second line contains the ratings $R\_i$ of $i$th coder.

The third line contains the number of gold medals bagged by the $i$th coder.

**Output:**

Display only one line that contains the sum of gold medals earned by the three coders the company will select.

# Answer
> 16 votes
This is a problem of selecting the $k$th smallest element from the list solved by a class of algorithms called the Selection Algorithms. There exist deterministic linear time selection algorithms so your problem can be solved in linear time by selecting the $n/2,n/2-1,n/2+1$th smallest elements from the original unsorted list.

---
Tags: algorithms, algorithm-design
---


# Question
Title: Classification of intractable/tractable satisfiability problem variants
Recently I found in a paper \[1\] a special symmetric version of SAT called the **2/2/4-SAT**. But there are many $\text{NP}$-complete variants out there, for example: **MONOTONE NAE-3SAT**, **MONOTONE 1-IN-3-SAT**, ...

Some other variants are tractable: $2$-$\text{SAT}$, Planar-NAE-$\text{SAT}$, ...

Are there survey papers (or web pages) that classify all the (weird) $\text{SAT}$ variants that have been proved to be $\text{NP}$-complete (or in $\text{P}$) ?

---

1. Finding a shortest solution for the $N$x$N$ extension of the 15-Puzzle is intractable by D. Ratner and M. Warmuth (1986)

# Answer
> 18 votes
# Classic, well-known results

As mentioned by Standa Zivny on the related question of CSTheory, Which SAT problems are easy?, there's a well-known result by Schaefer from 1978 (quoting the answer of Zivny):

> If SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions to linear equations in **GF**(2)), 0-valid (relations satisfied by the all-0 assignment) and 1-valid (relations satisfied by the all-1 assignment).

**Planar-3SAT** meaning the planar version of **3SAT** is known to be $\mathcal{NP}$-complete. See D Lichtenstein, Planar formulae and their uses, 1981. The non-planar version of 3SAT is of course the very well-known classic $\mathcal{NP}$-complete problem.

Not-All-Equal 3SAT (**NAE-3SAT**) is $\mathcal{NP}$-complete. However, the planar version of it is in $\mathcal{P}$ as shown by Moret, Planar NAE3SAT is in P, 1988.

# More recent and/or "weird" variants

# $k$-colourable Monotone NAE-3SAT

Here's a more exotic or weird variant, a decision problem called the **$k$-colourable Monotone NAE-3SAT**:

> Given a monotone CNF expression $\phi$ with exactly three distinct variables in each clause, such that the corresponding constraint graph $G(\phi)$ is k-colourable, is the expression $\phi$ not-all-equal satisfiable?

Here the corresponding constraint graph $G(\phi)$ is a simple undirected graph associated with $\phi$ as follows: Each variable of $\phi$ is a vertex in $G$, and two vertices have an edge between them iff they appear in some clause together.

For $k=4$ the problem is in $\mathcal{P}$. For $k=5$ however, it is $\mathcal{NP}$-complete. See P Jain, On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem, 2010.

# Linear CNF variants

While not perhaps being exotic or weird, some well-known variants, namely **NAE-SAT** (not-all-equal SAT) and **XSAT** (Exact SAT; *exactly one* literal in each clause to 1 and all other literals to 0), of the satisfiability problem have been investigated in the *linear* setting. Clauses of a linear formula pairwise have at most one variable in common. Interestingly, the complexity status does not follow from Schaefer's Theorem.

**NAE-SAT** and **XSAT** remain $\mathcal{NP}$-complete when restricted to linear formulas. Moreover, **NAE-SAT** and **XSAT** are still $\mathcal{NP}$-complete on formulas only containing clauses of length at least $k$, for each positive fixed integer $k \geq 3$. They are $\mathcal{NP}$-complete for monotone (no positive literals) linear formulas. However, **NAE-SAT** is polynomial-time decidable on exact linear formulas, where each pair of distinct clauses has exactly one variable in common.

Some further aspects regarding the complexity of **NAE-SAT** and **XSAT** under certain assumptions are probably still open. For more specifics, see for example Porschen and Schmidt, On Some SAT-Variants over Linear Formulas, 2009 and Porschen et al., Complexity Results for Linear XSAT-Problems, 2010.

---
Tags: complexity-theory, reference-request, satisfiability
---


title: Complexity of Special Case Problems

text:
# Question
Title: Complexity of Special Case Problems
Often I see a sentence like this while reading texts on Computational Complexity:

"For this special case of $\text{TSP}$" or

"This is a special case of $\text{SAT}$" or

"$k$-$\text{PARTITION}$ is the following special case of $\text{BIN PACKING}$" or

"$\text{SUBSET SUM}$ is a special case of $\text{KNAPSACK}$" ad nauseam.

What I find missing is the criterium to claim one problem is a special case of another.
What is the necessity of classifying one problem as a special case of another? Does a special case always carry the complexity class as its 'unspecial' case?

Often this is simply stated with no proof of relation between these problems.

What requirements must be met for a problem to be a special case of another?

How can I prove a new Language for a problem is a special case of an already existing problem?

# Answer
When we say that a problem $B$ is a special case of a problem $A$, we mean that $B$ is the same problem as $A$, with the exception that not all problem instances of $A$ are problem instances for $B$. If $B$ is a special case of $A$, we say that $A$ is a generalization of $B$.

Two examples: the addition of positive whole numbers (say $5 + 3$) is a special case of addition of whole numbers (say $5 + (-3)$), and sorting of integers in the range $\\{ 1, 2, \dots, k \\}$ for fixed $k$ is a special case of sorting of arbitrary integers.

Any solution to $A$ is also a solution to $B$, and any hardness results for $B$ (for example, it is $NP$-hard or needs $\Omega(n^2)$ time to be solved) immediately transfer to $A$. However, we usually consider special cases because we can sometimes find better algorithms for them compared to the general case.

Examples: the $\Theta(n \log n)$ sorting algorithm works just as well on integers in the range $\\{ 1, 2, \dots, k \\}$, but CountingSort works on the special case (not on the general) in $O(n + k)$, which is usually faster if $k$ is small. $SAT$ is $NP$-hard, $3SAT$ is a special case of $SAT$ that is still $NP$-hard (which therefore implies that $SAT$ is $NP$-hard), but $2SAT$ is in $P$.

Note that the above definition is sometimes stretched (abused) to say that you can encode any instance of $B$ as an instance of $A$, and that this encoding is extremely simple. In that case, the above usually still holds, but is less rigorous.
> 11 votes

# Answer
"Special case" is simply the opposite of "general case".

For instance, a tree is a special case of a graph, etc. The same works for *problems*: "find the minimal element of some list" or "find the median" are merely special cases of the problem "find the $k$-th smallest element in the list".

As for the complexity, we know that the special case is at most as hard as the general case (because any algorithm that solves the general case, can also solve the special case).

However, it is possible that the special case is way more simple than the general case. Many $\text{NP}$-complete problems have special cases that are "easy" to solve. For instance, 2-$\text{SAT}$ which is the special case of $\text{SAT}$ in which the formula has only 2 variables in each clause. While $\text{SAT}$ is $\text{NP}$-complete, 2-$\text{SAT}$ can be solved with polynomial time.

Another example: although sorting takes $\Omega(n\log n)$ in general, for the special case in which the domain is bounded (i.e., the elements are only from $\\{1, \ldots, m\\}$ for a fixed $m$), a linear $O(n+m)$ solution exists using Bucket sort, etc.
> 4 votes

---
Tags: complexity-theory
---


# Question
Title: Are asymptotic lower bounds relevant to cryptography?
An asymptotic lower bound such as exponential-hardness is generally thought to imply that a problem is "inherently difficult". Encryption that is "inherently difficult" to break is thought to be secure.

However, an asymptotic lower bound does not rule out the possibility that a huge but finite class of problem instances are easy (eg. all instances with size less than $10^{1000}$).

Is there any reason to think that cryptography being based on asymptotic lower bounds would confer any particular level of security? Do security experts consider such possibilities, or are they simply ignored?

An example is the use of trap-door functions based on the decomposition of large numbers into their prime factors. This was at one point thought to be inherently difficult (I think that exponential was the conjecture) but now many believe that there may be a polynomial algorithm (as there is for primality testing). No one seems to care very much about the lack of an exponential lower bound.

I believe that other trap door functions have been proposed that are thought to be NP-hard (see related question), and some may even have a proven lower bound. My question is more fundamental: does it matter what the asymptotic lower bound is? If not, is the practical security of any cryptographic code at all related to any asymptotic complexity result?

# Answer
I'll try to give a partial answer, since I'm not fully aware of how this issue is considered by the entire crypto-community (maybe repost on crypto.SE?).

I would say there are two "kinds" of cryptographers: *Theoretical* and *Practical*. I will not try to tell them apart (every practical-cryptographer is also a bit theoretician..) but I'll say that for theoretical cryptography - this issue doesn't really matter. For any security parameter, there will be an instance size that will provide that security level, and that is usually all that we care about.

Practical cryptographers care a lot about the issue you mention. For a given security parameter (say $2^{1024}$) cryptographers try to come up with the most efficient protocols, shaving the constant as much as possible. Look for instance for NIST's AES or SHA-3 competition. The algorithms were required to be both secure and efficient. The issue here is that the notion of security is somewhat different from the "theoretical" one, and sometimes is not really asymptotic.

A concrete example I can think of is the discrete log or the DDH assumption (the security of many cryptographic schemes are based on these assumptions). We **assume** that for some group $G$ computing the log takes $O(|G|)$ time. (We can't be sure: it might be that $\text{P}=\text{NP}$ and this problem can be solved in $O(\log |G|)$). Cryptographers **DO** care about the actual time it takes to compute the log. More accurately, they care alot about special cases for which computing the log is easy. In many papers you will see the sentence "Let $G$ be a group in which DDH is hard". See this survey for families of groups for which DDH is believed to be intractable (unless P=NP).
> 2 votes

---
Tags: complexity-theory, cryptography, asymptotics
---


# Question
Title: Where can I find good study material on Role Mining?
I need to cover these topics in Role Mining. If anyone knows good site which well summarizes the topics and concepts are well explained please help out.

Basic role mining problem
• Delta-approx RMP
• Min-noise RMP
• Nature of the RMP problems
• Mapping RMP to database tiling problem
• Minimum tiling problem
• Mapping min-noise RMP to database tiling problem
• Mapping RMP to minimum biclique cover problem

# Answer
The paper The Role Mining Problem: Finding a Minimal Descriptive Set of Roles by Jaideep Vaidya, Vijayalakshmi Atluri and Qi Guo covers the basic definitions and some variants and includes a mapping to the minimum tiling problem. This is explored in more detail in the third author's PhD thesis (found by Googling "A formal approach to the role mining problem.)

An alternative formal definition of the Role Mining problem is found in the paper On the Deﬁnition of Role Mining by Mario Frank, Joachim M. Buhmann, and David Basin. This is another good starting point; it also contains references to much of the earlier work.

These tutorial slides cover many of the topics you mention. They also contain a load of references for you to follow up. The author of these slides has a small page describing the basics of role mining.

Optimal Boolean Matrix Decomposition: Application to Role Engineering by Haibing Lu, Jaideep Vaidya and Vijayalakshmi Atluri covers basic RMP along with min-noise RMP, $\delta$-approximate RMP and edge-RMP using boolean matrix decomposition as the basic formalism.
> 3 votes

---
Tags: education, reference-request, security, access-control
---


# Question
Title: How to devise an algorithm to arrange (resizable) windows on the screen to cover as much space as possible?
I would like to write a simple program that accepts a set of windows (width+height) and the screen resolution and outputs an arrangement of those windows on the screen such that the windows take the most space. Therefore it is possible to resize a window, while maintaining `output size >= initial size` and the aspect ratio. So for window $i$, I'd like the algorithm to return a tuple $(x, y, width, height)$.

I believe this is might be a variation of 2D Knapsack. I've tried going over results around the web but they mostly had a lot of background (and no implementation) that made it hard for me to follow.

I'm less interested in the fastest possible algorithm, but more in something that is practical for my specific need.

# Answer
*Although your question does not say it, I'm assuming that you do not want windows to overlap.*

One approach to this problem is to use a constraint solver such as Choco. One simply writes down the constraints encoding your problem, tunes the solver to act in a smart way, and then let it run. This means that all the thinking you need to do will be spent on finding a good way of encoding the problem, not on devising an algorithm and doing the programming and tuning. Here is a partial answer to get you started.

Assume that the screen size is by $x\_{max}\times y\_{max}$.

For each window, $W\_i$, you'll have a set of variables $x\_i, y\_i, h\_i, w\_i$ and constraints

* $x\_i,y\_i,h\_i,w\_i\ge 0$
* $x\_i + w\_i \le x\_{max}$
* $y\_i + h\_i \le y\_{max}$
* Perhaps also some constraints on the minimal size of windows, e.g., $h\_i\ge 100$ and so forth.
* Aspect constraints: If aspect ratio is 3:4, the constraint could be something like $4h\_i - \epsilon \le 3 w\_i \le 4 h\_i + \epsilon$, where $\epsilon$ is some small non-zero error term to allow for non-perfect window sizes, as otherwise you'd over constraint the problem.

Now you need to take care of window overlap. For each pair of windows, $W\_i, W\_j$, where $i\neq j$, you'll generate constraints like the following, which capture that no corner of $W\_j$ appears within $W\_i$. For $(x,y)\in\\{(x\_j,y\_j), (x\_j+w\_j,y\_j), (x\_j,y\_j+h\_j), (x\_j+w\_j,y\_j+h\_j)\\}$, generate constraint:

* $\neg(x\_i \le x\le x\_i + w\_j \wedge y\_i\le y \le y\_i+h\_j)$.

The constraints specified thus far only describe non-overlapping windows that do not spill over the sides of the screen, that satisfy some minimal size constraints, and that preserve their aspect ratio.

In order to get a good fit, you need to specify a metric that captures what it means to be a good layout. One possibility is to assume that you want to keep windows roughly equal in size and/or that you want to minimize "white space". I do not think that this can be specified using Choco, but it may be possible with another constraint solve (someone else might be able to help here).

Choco does allow one to maximize wrt to an objective function specified as a single variable. Based on this idea, you could maximize the following:

* $\sum\_i (h\_i + w\_i)$

by writing a constraint $\mathit{cost}=\sum\_i (h\_i + w\_i)$ and telling Choco to maximize $\mathit{cost}$.
> 9 votes

# Answer
I started writing a prototype for a brute force solution, that hopefully can be optimized to a point where it will be practical.

First, some definitions: Let $W$ be the set of all windows. Each window $w$ is composed of $x\_w, y\_w, w\_w, h\_w$ for the x, y coordinates and the width and height. A window is initialized with a minimum width and height.

The input of the algorithm is the screen, $S$, which has a width and height and a list of windows.

It works roughly so:

```
void fit(W, S, i, n, result)
    if i == n
        if S.score() < result.score()
            result = S
        return

    w = W[i]
    foreach x, y in S.coordinates()
        set w position to (x, y)
        while S.put(w) # check that w doesn't overlap with S's other windows and add it
            fit(W, S, i+1, n, result)
            S.windows.pop()
            w.grow()
        w.restoresize()

```

There are a few things that should be improved:

* `S.coordinates()` is very slow right now. It iterates all points in `S.width x S.height` and checks if each one is in one of S's windows.
* `S.put()` checks if its parameter overlaps with the rest of S's windows by doing the test mentioned in Dave's answer. Maybe this can be improved by using interval trees?
* `S.score()` currently returns $\sum\_{w \in S.windows} (h\_w \cdot w\_w)$ which is simply the area of all windows. It needs to take into account other variables to produce better layouts.
* The above function needs to try all permutations of $W$ to get the best possible result.

I am currently trying to figure out a suitable data structure to represent the screen and its windows, it needs to support these queries:

* return a list of coordinates where a given window can be positioned without overlapping with others
* insert window at position x, y (already verified that it doesn't overlap)
* return all windows
> 1 votes

---
Tags: algorithms, computational-geometry, packing, user-interface
---


# Question
Title: A lambda calculus evaluation involving Church numerals
I understand that a Church numeral $c\_n$ looks like $\lambda s. \lambda z. s$ (... n times ...) $s\\;z$. This means nothing more than "the function $s$ applied $n$ times to the function $z$".

A possible definition of the $\mathtt{times}$ function is the following: $\mathtt{times} = \lambda m. \lambda n. \lambda s. m \\; (n\\; s)$. Looking at the body, I understand the logic behind the function. However, when I start evaluating, I get stuck. I will illustrate it with an example:

$$\begin{align\*} (\lambda m. \lambda n. \lambda s. m \\; (n\\; s))(\lambda s.\lambda z.s\\;s\\;z)(\lambda s.\lambda z.s\\;s\\;s\\;z) \mspace{-4em} \\ \to^\*& \lambda s. (\lambda s.\lambda z.s\\;s\\;z) \\; ((\lambda s.\lambda z.s\\;s\\;s\\;z)\\; s)) \\ \to^\*& \lambda s. (\lambda s.\lambda z.s\\;s\\;z) \\; (\lambda z.s\\;s\\;s\\;z) \\ \to^\*& \lambda s. \lambda z.(\lambda z.s\\;s\\;s\\;z)\\;(\lambda z.s\\;s\\;s\\;z)\\;z \end{align\*}$$

Now in this situation, if I first apply $(\lambda z.s\\;s\\;s\\;z)\\;z$, I get to the desired result. However, if I apply $(\lambda z.s\\;s\\;s\\;z)\\;(\lambda z.s\\;s\\;s\\;z)$ first, as I should because application is associative from the left, I get a wrong result:

$\lambda s. \lambda z.(\lambda z.s\\;s\\;s\\;z)\\;(\lambda z.s\\;s\\;s\\;z)\\;z \to \lambda s. \lambda z.(s\\;s\\;s\\;(\lambda z.s\\;s\\;s\\;z))\\;\\;z$

I can no longer reduce this. What am I doing wrong? The result should be $\lambda s. \lambda z.s\\;s\\;s\\;s\\;s\\;s\\;z$

# Answer
I think your reduction is correct (I've only eyeballed it, though). At the end, you can't apply $(\lambda z. s s s z)$ to $z$, this never appears in the term. $\lambda z. f f z$ is $\lambda z. (f f) z$, not $\lambda z. f (f z)$. Functions in the lambda-calculus take a single argument; they are effectively curried: a two-argument function is implemented as a one-argument function that takes the first argument and returns a new one-argument function that takes the second argument and returns the result.

You made the same mistake when defining Church numerals. The Church numeral for $n$ is based on composing a function $n$ times. “The function $s$ applied $n$ times to the function $z$” $\lambda s. \lambda z. s (s ( … s \\: z) … ))$. What you wrote is the function $s$ applied $n-1$ times to the function $s$ and finally to $z$, which doesn't strike me as a useful term.

$2 \times 3$ is thus $(\lambda m n s. m (n s)) (\lambda s z. s (s \\: z)) (\lambda s z. s (s (s \\: z)))$. I'll let you check that it does reduce to $\lambda s z. s (s (s (s (s (s \\: z)))))$.
> 7 votes

---
Tags: lambda-calculus, church-numerals
---


# Question
Title: Supporting data structures for SAT local search
WalkSAT and GSAT are well-known and simple local search algorithms for solving the Boolean satisfiability problem. The pseudocode for the GSAT algorithm is copied from the question Implementing the GSAT algorithm - How to select which literal to flip? and presented below.

```
procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

```

Here we flip the variable that maximizes the number of satisfied clauses. How is this done efficiently? The naive method is to flip every variable, and for each step through all clauses and calculate how many of them get satisfied. Even if a clause could be queried for satisfiability in constant time, the naive method would still run in $O(VC)$ time, where $V$ is the number of variables and $C$ the number of clauses. I'm sure we can do better, hence the question:

> Many local search algorithms flip the variable's assignment that maximizes the number of satisfied clauses. In practice, with what data structures is this operation supported efficiently?

This is something I feel like textbooks often omit. One example is even the famous Russell & Norvig book.

# Answer
The needed data structure is an *occur list*, a list for each variable containing the clauses the variable occurs in. These lists are built once, when the CNF is first read. They are used in steps 3 and 5 below to avoid scanning the whole CNF formula to count satisfied clauses.

A better algorithm than flipping every variable is:

1. Make a list of only the variables that occur in the unsatisfied clauses.
2. Choose a variable $x$ from this list.
3. Count how many clauses that contain $x$ are satisfied.
4. Flip $x$.
5. Count how many clauses that contain $x$ are satisfied.
6. Unflip $x$.
7. Subtract the result of step 3 from step 5 and record it for $x$.
8. Repeat steps 2-7 for the rest of the variables found in step 1.
9. Flip the variable with the highest number recorded in step 7.

A reference for the data structure (often also known as an adjacency list) is for example Lynce and Marques-Silva, Efficient Data Structures for Backtracking SAT solvers, 2004.
> 9 votes

---
Tags: algorithms, data-structures, satisfiability
---


# Question
Title: How do I construct reductions between problems to prove a problem is NP-complete?
I am taking a complexity course and I am having trouble with coming up with reductions between NPC problems. How can I find reductions between problems? Is there a general trick that I can use? How should I approach a problem that asks me to prove a problem is NPC?

# Answer
There is no magic bullet; NP-hardness proofs are hard. However, there is a general framework for all such proofs. Many students who struggle with NP-hardness proofs are confused about *what* they're supposed to be doing, which obviously makes it impossible to figure out *how* to do it. So here is *what* to do to prove a problem NP-hard.

First, unless you're just doing homework, you have to **decide which NP-hard problem to reduce to your problem**. This is largely a question of "smell". If the number 3 appears anywhere in the problem statement, try reducing from $\mathsf{3SAT}$ or $\mathsf{3Color}$ or $\mathsf{3Partition}$. (Yes, I'm serious.) If your problem involves finding an optimal subsequence or permutation or path, try reducing from $\mathsf{HamiltonianCycle}$ or $\mathsf{HamiltonianPath}$. If your problem asks for the smallest subset with a certain property, try $\mathsf{Clique}$; if it asks for the largest subset with a certain property, try $\mathsf{IndependentSet}$. If your problem involves doing something in the plane, try $\mathsf{PlanarCircuitSAT}$ or $\mathsf{PlanarTSP}$. And so on. If your problem doesn't "smell" like anything, $\mathsf{3SAT}$ or $\mathsf{CircuitSAT}$ is probably your best bet.

Obviously, you need to already know *precisely* how all these problems are defined, and the simpler the problem you reduce from, the better. So as cool as the result might look in the end, I don't recommend reducing from $\mathsf{Minesweeper}$ or $\mathsf{Tetris}$ or $\mathsf{OneCheckersMove}$ or $\mathsf{SuperMarioBros}$.

Second, the actual reduction. To reduce problem X (the one you know is NP-hard) to problem Y (the one you're trying to prove is NP-hard, you need to describe an algorithm that transforms an *arbitrary* instance of X into a legal instance of Y. The reduction algorithm needs to do something specific with each "feature" of the X-instance; the portion of the output for each "feature" is usually called a gadget.

But what's a feature? That depends on problem X. For example:

* To transform an instance of $\mathsf{3SAT}$, you'll need a gadget for each variable and for each clause in the input formula. Each variable gadget should have two "states" that correspond to "true" and "false". Each clause gadget should also have multiple "states", each of which somehow forces at least one of the literals in that clause to be true. (The states are not part of the output of the reduction algorithm.)
* To transform an instance of $\mathsf{3Color}$, you'll need a gadget for each vertex and each edge of the input graph, and another gadget to define the three colors.
* To transform an instance of $\mathsf{PlanarCircuitSat}$, you'll need a gadget for each input, for each wire, and for each gate in the input circuit.

The actual form of the gadget depends on problem Y, the one you're reducing **to**. For example, if you're reducing to a problem about graphs, your gadgets will be small subgraphs; see the Wikipedia article. If you're reducing to a problem about scheduling, each gadget will be a set of jobs to be scheduled. If you're reducing to a problem about Mario, each gadget will be a set of blocks and bricks and Koopas.

This can get confusing if both problems involve the same kind of object. For example, if both X and Y are problems about graphs, your algorithm is going to transform one graph (an instance of X) into a different graph (an instance of Y). Choose your notation wisely, so that you don't confuse these two graphs. I also strongly recommend using multiple colors of ink.

Finally, your reduction algorithm must satisfy three properties:

* It runs in polynomial time. (This is usually easy.)
* If your reduction algorithm is given a *positive* instance of X as input, it produces a *positive* instance of Y as output.
* If your reduction algorithm produces a *positive* instance of Y as output, it must have been given a *positive* instance of X as input.

There's an important subtlety here. Your reduction algorithm only works in one direction, *from* instances of X *to* instances of Y, but proving the algorithm correct requires reasoning about the transformation in both directions. You must also remember that your reduction algorithm *cannot* tell whether a given instance of X is positive or negative—that would require solving an NP-hard problem in polynomial time!

That's the *what*. The *how* just comes with practice.
> 67 votes

# Answer
JeffE outlines the most common strategy: know lots of NP-complete problems, find one that fits very well and make the *easy* reduction.

Another valid strategy is to *always* use 3SAT (or any other problem). This might make some reductions more intricate, but the upside is that you have *lots* of experience expressing satifiability in other types of problems. So you save the time of finding a good reduction partner (including dead-ends) and hope that your experience will allow you to do the reduction quickly even if it is harder.

This approach has some meta beauty, too: (3)SAT is one of the few problems for which NP-completeness has been proven (almost) directly. Therefore, relying only on that proof keeps your "proof tree" flat, avoiding long chains of reductions.
> 16 votes

---
Tags: complexity-theory, np-complete, proof-techniques, reductions
---


# Question
Title: Efficient queriable data structure to represent a screen with windows on it
(this is related to my other question, see here)

Imagine a screen, with 3 windows on it:

I'd like to find an efficient data structure to represent this, while supporting these actions:

* return a list of coordinates where a given window can be positioned without overlapping with others
    + for the above example, if we want to insert a window of size 2x2, possible positions will be (8, 6), (8, 7), ..
* resizing a window on the screen without overlapping other windows while maintaining aspect ratio
* insert window at position x, y (assuming it doesn't overlap)

Right now my naive approach is keeping an array of windows and going over all points on the screen, checking for each one if it's in any of the windows. This is $O(n\cdot m\cdot w)$ where $n, m$ are the width, height of the screen and $w$ is the number of windows in it. Note that in general $w$ will be small (say \< 10) where each window is taking a lot of space.

# Answer
> 3 votes
An easy optimization to the naive algorithm is to skip some points when you check one covered by a window. Say you scan left-to-right, top-to-bottom. If you encounter an $(x, y)$ in window $w = (l, r, w, h)$, you can jump from $x$ to $l + w + 1$ and continue. If windows are big and don't overlap, off the cuff, I'd wildly conjecture that would give you an $O(p)$ algorithm, where $p$ is the number of points in the set you return.

In fact, it could be beneficial to see whether the windows are generally wider or taller. For tall windows, it would be better to scan top-to-bottom, left-to-right; for wide windows, the method discussed above should win out. You might be able to take the idea and do scan/skip diagonally to get balanced performance across the board.

In fact, scanning left-to-right, top-to-bottom, you can remember for subsequent $h$ rows (values of $y$) that you will need to skip at the same $x$ value to the same $l + w + 1$ value, if you reach the $x$ (you might not if there's another window that overlaps). This would make top-to-bottom, left-to-right and diagonal scanning unnecessary to get equivalently good performance.

More generally, you now have two data structures: one with $O(1)$ preprocessing/construction overhead and $O(w)$ lookups, and one with $O(p)$ (possibly; maybe you can do better, or maybe my optimization doesn't really achieve this) preprocessing/construction and possibly $O(1)$ (hash/lookup table) or $O(\log p)$ (BST). So there are already two alternatives, both of which are pretty good, really...

---
Tags: algorithms, computational-geometry, user-interface, modelling
---


# Question
Title: Find subsequence of maximal length simultaneously satisfying two ordering constraints
We are given a set $F=\\{f\_1, f\_2, f\_3, …, f\_N\\}$ of $N$ Fruits. Each Fruit has price $P\_i$ and vitamin content $V\_i$; we associated fruit $f\_i$ with the ordered pair $(P\_i, V\_i)$. Now we have to arrange these fruits in such a way that the sorted list contains prices in ascending order and vitamin contents in descending order.

**Example 1**: $N = 4$ and $F = \\{(2, 8), (5, 11), (7, 9), (10, 2)\\}$.

If we arrange the list such that all price are in ascending order and vitamin contents in descending order, then the valid lists are the following:

* $\[(2, 8)\]$
* $\[(5, 11)\]$
* $\[(7, 9)\]$
* $\[(10, 2)\]$
* $\[(2, 8), (10, 2)\]$
* $\[(5, 11), (7, 9)\]$
* $\[(5, 11), (10, 2)\]$
* $\[(7, 9), (10, 2)\]$
* $\[(5, 11), (7, 9), (10, 2)\]$

From the above lists, I want to choose the list of maximal size. If more than one list has maximal size, we should choose the list of maximal size whose sum of prices is least. The list which should be chosen in the above example is $\\{(5, 11), (7, 9), (10, 2)\\}$.

**Example 2**: $N = 10$ and $$F = \\{(99,10),(12,23),(34,4),(10,5),(87,11),(19,10), \\\(90,18), (43,90),(13,100),(78,65)\\}$$

The answer to this example instance is $\[(13,100),(43,90),(78,65),(87,11),(99,10)\]$.

Until now, this is what I have been doing:

1. Sort the original list in ascending order of price;
2. Find all subsequences of the sorted list;
3. Check whether the subsequence is valid, and compare all valid subsequences.

However, this takes exponential time; how can I solve this problem more efficiently?

# Answer
A dynamic programming solution would work here, if the vitamin contents come from a finite set (for instance, bounded integers). First, sort the fruits on price ascending and in the cases were two or more fruit have the same price, sort them on vitamin content (descending). Now, define $M\[f, v\]$ to be the maximal number of fruits in a sublist, containing only the last $f$ fruits (of the sorted list), having a vitamin content of at most $v$. $M\[0, \*\] = 0$ and $$M\[f, v\] = \begin{cases} \mathrm{max} \\{M\[f-1, v\], 1 + M\[f-1, V\_f\]\\} & \text{if \\(V\_f \<= v\\)} \\ M\[f-1, v\] & \text{otherwise} \\ \end{cases}$$ Using dynamic programming gives you a solution that runs in $O(\text{number of fruit} \times \text{possible vitamin values})$.
> 5 votes

---
Tags: algorithms, arrays, constraint-programming, subsequences
---


# Question
Title: Solve a recurrence using the master theorem
This is the recursive formula for which I'm trying to find an asymptotic closed form by the master theorem: $$T(n)=9T(n/27)+(n \cdot \lg(n))^{1/2}$$

I started with $a=9,b=27$ and $f(n)=(n\cdot \lg n)^{1/2}$ for using the master theorem by $n^{\log\_b(a)}$, and if so $n^{\log\_{27}(9)}=n^{2/3}$ but I don't understand how to play with the $(n\cdot \lg n)^{1/2}$.

I think that the $(n\cdot \lg n)^{1/2}$ is bigger than $n^{2/3}$ but I'm sure I skip here on something.

I think it fits to the third case of the master theorem.

# Answer
$f(n) = (n\cdot \lg n)^{1/2}$ and $n^{\log\_b a}=n^{2/3}$, thus $f(n) = O(n^{\log\_b a})$ and even $f(n) = O(n^{\log\_b a - \epsilon})$ for $\epsilon \< 1/6$.

Why? because $$\lim\_{n\to\infty} \frac{f(n)}{n^{\log\_b a - \epsilon}} = \lim\_{n\to\infty}\frac{n^{1/2}\lg^{1/2}n}{n^{2/3-\epsilon}} = \lim\_{n\to\infty} \frac{\lg^{1/2}n}{n^{1/6-\epsilon}} =0 \quad\text{for }\epsilon\< 1/6$$

Thus case 1 of the Master theorem should apply, and $T(n) = \Theta(n^{2/3})$.
> 5 votes

---
Tags: algorithm-analysis, asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Find minimum number 1's so the matrix consist of 1 connected region of 1's
Let $M$ be a $(0, 1)$ matrix. We say two entries are neighbors if they are adjacent horizontal or vertically, and both entries are $1$'s. One wants to find minimum number of $1$'s to add, so every $1$ can reach another one through a sequence of neighbors.

Example:

```
100
000
001

```

Here we need 3 $1$'s:

```
100
100
111

```

How can we efficiently find the minimum number of $1$'s to add, and where?

# Answer
> 5 votes
If you model your problem with graphs, Your problem is like Steiner Tree problem:

See here for simplest possible definition.

> Given a weighted graph in which a subset of vertices are identified as terminals, find a minimum-weight connected subgraph that includes all the terminals.

As you can see it's NPC in general, but in your case your graph is grid graph, may be you can find good solution for it, but for your current example (when terminals are in boundary) you can see Steiner tree in grid graphs paper.

Anyway there are excellent heuristics for Steiner Tree problem, you can apply similar approach to your problem.

P.S: You can assume neighbor 1s are connected nodes, after that you can contract their edges to make a new graph, your new created graph is planar, and if you could solve the Steiner Tree for it you can solve your problem, but may be there is a good solution for your problem which is independent from Steiner Tree.

---
Tags: algorithms, graphs, matrices
---


# Question
Title: How to score a given arrangement of windows on a screen to produce good layouts
(this is related to my other question, see here)

I would like to write a function that scores a given arrangement of windows on a screen.

The purpose of this function is to determine whether a particular layout is good and by going over other possible layouts, finding the one with the highest score.

Here are some characteristics that I think make a good layout:

1. maximizing amount of space used by windows (or in other words, the free space on the screen should be minimized)
2. windows are (more or less) evenly sized

Bonus: assigning each window a priority and giving a higher score for layouts where windows with a higher priority take more space.

Here's an example: Suppose our screen is 11x11 and we want to put two windows on it. Window A's initial size is 1x1 and window B is 2x1.

When we resize windows, we preserve their aspect ratio. So here are two possible layout:

The function should give the one on the right a higher score.

Another nice thing to have is the option to 'dock' a window to one or more sides of the screen. Then suppose we want to dock A to the bottom-left of the screen, the scoring function should prefer this layout than the above one on the right:

# Answer
I will expand on my comment on the other question and propose a target function that ensures that no very small windows occur and that windows are not unnecessarily far away from screen edges. Let $\mathcal{W} = \\{1,\dots,n\\}$ a set of windows and $T = \mathcal{W} \to \mathbb{N}^4$ a tiling; if $T(W) = (x,y,w,h)$ window $W$'s top-left corner is positioned at $(x,y)$ and $W$ has width $w$ and height $h$. Now let $c : (\mathbb{N}^4)^\mathcal{W} \to \mathbb{R}$ a cost function from the space of all tilings to the reals:

$\qquad \displaystyle c(T) = \left\[ \min\_{W \in \mathcal{W}} T(W)\_3\cdot T(W)\_4 \right\] - \sum\limits\_{W \in \mathcal{W}} \operatorname{empty}(W)$

where $\operatorname{emtpy}(W)$ the maximum number of empty tiles between one of $W$'s edges and the respective nearest screen edges. The objective is maximisation.

Note that this is a (non-equivalent) simplification of the multicriteria optimisation goal of maximising

$\qquad \displaystyle c(T) = \left( \min\_{W \in \mathcal{W}} T(W)\_3\cdot T(W)\_4 \ ,\ -\sum\limits\_{W \in \mathcal{W}} \operatorname{empty}(W)\right)$.

Of course you need appropriate restrictions in place that ensure that now window is placed outside of the screen and windows do not overlap.
> 2 votes

---
Tags: computational-geometry, user-interface, modelling
---


# Question
Title: Solving problems related to Marginal Contribution Nets
So, I encoutered this problem in examination:

> Consider the following marginal contribution net:
>
> $\\{a \wedge b\\} \to 5$
>
> $\\{b\\} \to 2$
>
> $\\{c\\} \to 4$
>
> $\\{b \wedge \neg c\\} \to −2$
>
> Let $v$ be the characteristic function defined by these rules. Give the values of the following:
>
> i) $v(\emptyset)$
>
> ii) $v(\\{a\\})$
>
> iii) $v(\\{b\\})$
>
> iv) $v(\\{a, b\\})$
>
> v) $v(\\{a, b, c\\})$

My answer is below, but I am not sure.

> i) $v(\emptyset) = -2$
>
> ii) $v(\\{a\\}) = 0 - 2$
>
> iii) $v(\\{b\\}) = 2 - 2$
>
> iv) $v(\\{a, b\\}) = 5 + 2 - 2$
>
> v) $v(\\{a, b, c\\}) = 5 + 4 + 2 - 2$

If anybody knows how to solve this kind of problem, could you confirm?

Exact same problem is shown on page 4 of following paper: Marginal Contribution Nets: A Compact Representation Scheme for Coalitional Games (by Samuel Ieong and Yoav Shoham)

# Answer
> 6 votes
I got the following answer:

1. $v(\emptyset)=0$
2. $v(\\{a\\}) = 0$
3. $v(\\{b\\}) = 2-2 = 0$
4. $v(\\{a,b\\}) = 5+2-2 = 5$
5. $v(\\{a,b,c\\}) = 5+2+4 = 11$

Here's a general approach to doing this calculation. Consider a set $A\subseteq \\{a,b,c\\}$. Define a map $I\_A:\\{a,b,c\\}\to\\{\text{True},\text{False}\\}$ as follows: $$I\_A(x) = \left\\{ \begin{array}{l@{~~}l} \text{True} & \mbox{if}~x\in A \\ \text{False} & \mbox{otherwise} \end{array}\right.$$ This is the so-called indicator function of set $A$.

Now take each element of the marginal contribution net and evaluate whether it is true or false given $I\_A$. If it is true, add the contribution. If not, add no contribution. More explicitly, given element $\psi\to c$, add $c$ only if $I\_A\models\psi$ holds.

Here the notation $I\_A\models\psi$ simply means evaluate the truth of the formula $\psi$ given the assignment of the variables $\\{a,b,c\\}$ to true or false.

Consider $v(\\{a,b\\})$. This corresponds to the map $I\_{\\{a,b\\}}=\\{a \mapsto\text{True},b\mapsto\text{True},x\mapsto\text{False}\\}$. Given this assignment of truth values, we can conclude that:

* $a\wedge b$ is true, so $5$ is contributed.
* $b$ is true, so $2$ is contributed.
* $c$ is false, so nothing is contributed.
* $b\wedge\neg c$ is true, so $-2$ is contributed.

Therefore the total contribution is $5+2-2=5$.

---
Tags: artificial-intelligence
---


title: Security Lattice Construction

text:
# Question
Title: Security Lattice Construction
I am having a problem trying to solve a question on a past paper asking to design a security lattice. Here is the question:

> The AB model (Almost Biba) is a model for expressing integrity policies rather than confidentiality. It has the same setup as Bell-LaPadula, except that $L$ is now a set of integrity levels which express the degree of confidence we have in the integrity of subjects and objects. Subjects and data at higher integrity levels are considered to be more accurate or safe. The set of subjects and objects may also be different, for example, programs are naturally considered as subjects.
>
> Often, the set $L$ is actually a lattice of levels, with two operations: least upper bound $l\_1 \vee l\_2$ and greatest lower bound $l\_1 \wedge l\_2$, where $l\_1, l\_2 \in L$.
>
> i. Design an example integrity lattice for AB, by combining two degrees of data integrity **dirty** and **clean** and two means by which a piece of input may be received, **website** (external user input from a web site form) and **dataentry** (internal user input by trusted staff).

I have been looking for an explanation on how to build lattices but can't seem to find one on the internet or in textbooks. Can anyone point me in the right direction?

# Answer
The way to view the lattice is by taking the two pieces one at a time. Firstly, you have the lattice: $$ \begin{array}{c} Clean \\ | \\ Dirty \end{array} $$ to capture that *Clean* data has higher integrity than *Dirty* data.

Similarly, $$ \begin{array}{c} DataEntry \\ | \\ Website \end{array} $$ captures that *DataEntry* data has higher integrity than *Website* data.

These can be combined (using the product of two lattices) into the following, which captures all combinations and the relationship between them: $$ \begin{array}{ccccc} && (Clean, DataEntry) \\ & / && \backslash~~~~~~~~~~~~~~~~~~~~~~~~~ \\ (Dirty, DataEntry) &&& (Clean,Website) \\ &\backslash &&/~~~~~~~~~~~~~~~~~~~~~~~~~~ \\ && (Dirty,Website) \end{array} $$ The two middle elements are incomparable.

The paper Lattice-based Access Control Models by Ravi Sandhu gives a good overview of the application of lattices in access control models, including the Biba model.

If you want to learn the general theory about lattices, then *Introduction to Lattices and Order* by B. A. Davey and H. A. Priestley is a very good starting point.
> 4 votes

---
Tags: security, lattices, integrity
---