# Question
Title: Initializing non-deterministic variables in QBF
I'm trying to translate the following pseudocode to QBF. The integers are encoded as simple fixed-width bitvectors, and the entire procedure runs in polynomial space ensuring QBF has enough representational power for a compact formula.

The following formula is nested to a linear depth in n, producing 2^n increments when unrolled. Using QBF allows for an exponentially more compact encoding than SAT. QBF solvers can typically handle thousands of variables, SAT solvers handle millions. For even modest values of n, such as n=30, unrolling to SAT would produce billions of variables (impractical), while a QBF encoding would be extremely practical with only tens of variables.

```
counter = 0
for loop_aux_0 in {0,1}:
  for loop_aux_1 in {0,1}:
    for loop_aux_2 in {0,1}:
      .
        .
          .
            for loop_aux_n in {0,1}:
              counter += f(loop_aux_0, loop_aux_1, .., loop_aux_n)
assert(counter > 0)

```

Here `f` is an arbitrary function that outputs 0 or 1.

This suggests a QBF implementation (although missing initialization) utilizing an adder circuit with its output fed back in as input:

∃ counter\[n\] ∀ loop\_aux\[n\] ∃ f\_output\[1\] (counter += f\_output) & (f\_output == f(loop\_aux\_0, loop\_aux\_1, .., loop\_aux\_n))

How can I add clauses or auxiliary variables to simulate sequential counter initialization?

# Answer
It looks to me like there is some confusion here about what QBF is and when it is needed. You don't need QBF for this problem; SAT is fine.

Here's how to solve this using a SAT solver. Notice that the condition `counter > 0` is true at the end if and only if there was at least one loop iteration where `f` output 1. In other words, the assertion will be true if and only if

$$\exists \mathtt{loop\\\_aux\\\_0},\dots,\mathtt{loop\\\_aux\\\_n} . \mathtt{f}(\mathtt{loop\\\_aux\\\_0},\dots,\mathtt{loop\\\_aux\\\_n})=1.$$

That can be expressed as a SAT instance. There are no nested/alternating quantifiers; the formula has the form $\exists x. \varphi(x)$, so it can be solved by SAT. Simply express the condition `f(loop_aux_0, ..., loop_aux_n)=1` in CNF form, and then use a SAT solver to check whether that condition can ever be true (for any value of the loop variables).

---

QBF is useful when you have nested quantifiers, e.g., $\exists x . \forall y . \exists z . \varphi(x,y,z)$. The result will be either true or false.

It's also worth knowing about #SAT. #SAT is useful when you want to count the number of satisfying assignments to some formula $\varphi(x)$. In other words, instead of checking whether $\exists x . \varphi(x)$ is true, suppose we want to know the number of values $x$ such that $\varphi(x)$ is true; then this is an instance of #SAT.

QBF and #SAT are not the same thing. They're different problems. And QBF isn't some kind of magic wand that lets you compress any SAT instance by some enormous factor; QBF is for a specific type of logical formula.
> 0 votes

---
Tags: satisfiability, model-checking
---


title: Size comparison of NFA and minimal DFA

text:
# Question
Title: Size comparison of NFA and minimal DFA
Except for isomorphisms, the minimal DFA of a regular language is unique. However, is it possible that an equivalent NFA has less states than the minimal DFA? If so, what is the reasoning behind this? Due to the conversion of an NFA to DFA (which produces $2^Q$ states) it seems to me that a NFA can indeed have less states than a minimal DFA, but I'm not quite sure of this. Thanks in advance.

# Answer
For every $n$ there is a language over $\\{a,b\\}$ which is accepted by an NFA having $n$ states, but its minimal DFA has $2^n$ states.

Unfortunately I don't remember the reference, but here is how to get almost this result. Let $L\_n$ be the language of all words over $\\{a\_1,\ldots,a\_n\\}$ that *don't* contain all letters. Then $L\_n$ can be accepted by an NFA with multiple initial states having $n$ states (or with a normal NFA with $n+1$ states), but its minimal DFA has $2^n$ states. Take it as an exercise to prove these statements (for the latter one, use Myhill-Nerode theory).
> 2 votes

# Answer
*Number of states in DFA is greater or equal to number of states in NFA.*

Now, minimal DFA is a kind of DFA. (Minimal DFA is a subset of DFA.) As NFA need not to show transition for all the input symbols it has lesser (or equal) number of states compare to DFA. Additionally, NFA has not dead states in transition diagram, unlike DFA.

So it may possible that minimal DFA and NFA has equal numbers of states but minimal DFA never has less number of states compare to **minimal** NFA.

That is why when we concern for minimum states in FA-Finite Automata, we go for NFA rather than DFA.

EXAMPLE:

Set of all strings start with 'a' over input symbols {a,b}.

DFA of above language has 3 states. NFA of above language has only 2 states.
> 0 votes

---
Tags: automata, finite-automata, nondeterminism
---


title: Reinforcement Learning - Q Learning

text:
# Question
Title: Reinforcement Learning - Q Learning
I am having trouble understanding the following problem and Q learning in general.

What I know so far about Q learning is that Q-learning is a model free method, i.e., it doesn’t need to learn P(s’|s,a). Thus it can compare the expected utility of the available actions without the model of the environment.It will also eventually find a policy that is the maximum achievable. However, I am not able to use this knowledge to do this problem. The answer is given in red.

If we are to look at time t = 1, then the equation becomes the following: $$ Q\_{t+1}(s,a)=(1-1/2)(1)+1/2\[R(s,a,s^{'})+(1) maxQ(s^{'},a^{'})\] $$ How do I proceed from here?

# Answer
> 0 votes
At `t=1`, you just took action `a = d` at state `s = S` and ended in `s' = S` again with 0 reward. So:

$Q(S,d) = (1 - 1/2)(1) + 1/2\[0 + (1)(1)\] = 1$ ($maxQ(s',a')$ is the maximum value you can get from state S in this case, which is 1)

So nothing changes. At `t=2`, it is exactly the same as `t=1`, so nothing changes again.

At `t=3`, we just took action `p` at `s = S` and ended on state `s' = P` with reward +1. Thus:

$Q(S,p) = (1 - 1/2)(0) + 1/2\[1 + (1)(1)\] = 1$ ($maxQ(s',a')$ here refers to $maxQ(P,a')$, the maximum value we can get from state `P`, which is 1.

So, update $Q(S,p)$ to 1.

At `t=4`, we just took action `a = p` at state `s = P`, ending in state `s' = S` with reward 0. Thus:

$Q(P,p) = (1 - 1/2)(0) + 1/2\[0 + (1)(1)\] = 1/2$

So, update $Q(P,p)$ to 1/2.

I think you can do `t=5` and `t=6` by yourself now, just note that maxQ at a terminal state is 0 (because there is no future reward to accumulate). If you can't, just tell me and I'll update the answer.

---
Tags: artificial-intelligence, reinforcement-learning
---


# Question
Title: Difference between properties of good hash function: uniformity and randomness
I did go through Korth's book of DBMS and I got these definitions:

**Uniformity:**

Each bucket is assigned the same number of search-key values from the set of all possible values.

**Randomness:**

Each bucket will have the same number of records assigned to it irrespective of the actual distribution of search-key values in the file.

These definitions seem similar to me. Can anyone please differentiate, I did search on net but can't understand.

# Answer
Uniformity is about *potential* values, while randomness is about *actual* values.

For example, suppose you make a very simple hash function that takes the first byte of a string, resulting in 256 buckets. It is uniform, because the number of possible strings starting with a particular byte doesn't depend on. But it is not random for most data sets: at least 12.5% of the values consist of nonprintable characters (control characters) that most data sets don't contain, some characters like `)]}` rarely appear at the beginning of a string, an English dictionary contains more words beginning with `a` than with `z`, etc.

Randomness is defined with respect to a specific data set. For example, if the data set consists of SHA-1 hashes of typical strings, then taking the first byte satisfies the randomness property. If the data set consists of people's surnames, it doesn't. If the data set consists of SHA-1 hashes strings that are deliberately chosen so that their SHA-1 hash starts with the byte 0, then taking the first byte doesn't satisfy randomness either.

In fact, there is no hash function that satisfies randomness for all datasets: for any hash function (with at least two buckets), a data set consisting solely of values that hash to bucket 0 violates randomness. The best you can hope is hash functions that satisfy randomness for datasets that are not deliberately crafted to violate randomness. This is possible in practice if the hash function includes a random factor which is based on a secret seed.
> 4 votes

---
Tags: hashing
---


# Question
Title: Amount of information in scaled-down images
Does an image that is scaled down lose more Information when calculating averages of pixels rather than selecting single pixels?

One way to scale down an image is to replace 2x2 pixel blocks with the average of those four pixels, the other way is to just select the top-left pixel (or any other) instead.

Averaging is done by summation and integer division. We reduce the Problem to just scaling 2x2 images down to 1x1 images. For black and white images there are 16 possible images, 15 of those will be black and one will be white thus the entropy of the scaled down image is 0.337 bits. For grayscale images with 5bits per pixel results in 4.2524 bits, with 6bits per pixel we end up at 5.251 bits.

Does averaging really lose more information than just selecting top-left pixels?

I'm aware that you lose some information due to rounding but my calculations don't seem to converge so rounding wouldn't explain everything.

# Answer
> 2 votes
Averaging-and-truncation certainly loses more information. It is not because you are not preserving any specific pixel: it is because you are taking an even probability distribution and giving it a strong bias in one direction.

If I have understood you correctly, you have taken the 16 possible 2x2 images and transformed one of them to white and 15 of them to black. This 15:1 split is about as bad as you can get! It destroys information, and it is the reason why your results are so bad compared to the "take top left corner".

The nearer you get to an "8:8" split, the less information you will lose. So try averaging and rounding: what I think you call "taking the median". This will split 11:5, which is less bad. It is still not very good, because the 6 cases of "2 black, 2 white pixels" all have to be translated either to black or to white - that is why you can only get 11:5 rather than the ideal 8:8 between black and white outcomes. \[It would be interesting to try "use the majority value if there is a majority value; if not, use the top left"\].

If you try $3\times 3$ blocks then either a clear majority of pixels will be white or a clear majority of pixels will be black: a straight 256:256 split. This is the best possible outcome, and if you simulate it then you should find it leads to the least information loss.

# Answer
> 1 votes
The averaged downscale gives you the mean of pixels (obviously), but in the most cases information is lost — you have not preserved any pixels from the original (and if you do it is unknown from only a downscaled picture). When you always take the same pixel from each kernel ($2x2$) then you have preserved these pixels perfectly.

Another possibility is to take the median, then you preserve one of the pixels, but lose the position (using a definition of median of even number of elements to take for example $\lfloor N / 2\rfloor$).

Using entropy here shows only how disordered the image is (or what is left after downsampling), so this is probably not the measure you want to use. Think about ideally random pixels, what changes after preserving $1/4$ and what after averaging them. Or what about the case when the pixels you select are ideally random and the discarded ones are not — this vastly changes the results, but in one case you still have 25% of the image preserved and in the second scheme you don't.

---
Tags: information-theory, graphics, entropy
---


# Question
Title: What is the cardinality of the set of regular grammars?
What is the cardinality of the set of regular grammars? The caveat is that I'm only interested in grammars which are 'structurally' different. Sorry I don't know how to talk about this in a formal way, but what I mean is that the actual symbols are arbitrary to me.

So for example the grammar with: {N={α}, Σ={x}, P={α→x}, S=α}

Is equivalent to the grammar: {N={β}, Σ={y}, P={β→y}, S=β}

Hopefully I am being understood! I believe this set is countable because for every N and Σ there are only a finite number of production rules which can be formulated. For example, for:

N={α} and Σ={x}

The only unique sets of production rules are:

{{α→x}}

{{α→xα}}

{{α→x}, {α→xα}}

# Answer
> 3 votes
There is at least one regular grammar per regular language, and all of them are pairwise inequivalent (for any meaningful equivalence relation). Since there is at least a countably infinite number of regular languages¹, that's a lower bound for the number of regular grammars as well.

Without loss of generality², you can write down every regular grammar as finite string over a finite alphabet. Therefore, there are at most as many regular grammars as binary strings, of which there are countably infinitely many.

Combine the bounds to get your answer.

---

1. The lower bounds follows from $\\{a\\}^n$ being regular for every $n \in \mathbb{N}$.
2. Encode all symbols using binary numbers.

---
Tags: regular-languages, formal-grammars, combinatorics
---


# Question
Title: Why is the optimal cut-off for switching from Quicksort to Insertion sort machine dependent?
I fail to understand why cut off value would be system dependent, and not a constant.

From Princeton University website

> Cutoff to insertion sort. As with mergesort, it pays to switch to insertion sort for tiny arrays. The optimum value of the cutoff is system-dependent, but any value between 5 and 15 is likely to work well in most situations.

Would it be safe to assume that optimal cut off value is equal to optimal set size for Insert sort?

# Answer
Because the actual running time (in seconds) of real code on a real computer depends on how fast that computer runs the instructions and how fast it retrieves the relevant data from memory, how well it caches it and so on. Insertion sort and quicksort use different instructions and hava different memory access patterns. So the running time of quicksort versus insertion sort for any particular dataset on any particular system will depend both on the instructions used to implement those two sorting routines and the memory access patterns of the data. Given the different mixes of instructions, it's perfectly possible that insertion sort is faster for lists of up to ten items on one system, but only for lists up to six items on some other system.
> 14 votes

# Answer
The relative costs of various operations are different on different machines, and compilers have varying degrees of ability to optimize various constructs. David Richerby goes into somewhat more detail on that, but the last half-sentence of the highlighted quote is perhaps the most important. In many cases where one algorithm is more efficient than another for small data sets, and another is more efficient for large data sets, the performance differences between the two algorithms are apt to be rather small for data sets near the "break-even" point. As a simple example, assume for numerical simplicity that the cost of insertion sort is precisely $C\_1 · N·N$ with some constant $C\_1$, and the cost of quick sort is precisely $C\_2 · N·\lg(N)$ for some other constant $C\_2$. Then consider the relative behaviors for two sets of constants.

First of all, suppose that the constants are $C\_1 =1$ and $C\_2 = 2$. Then for $N=4$ both sorts will take time 16; for $N=16$, insertion sort will take time 256 and quick sort will take time 128. For $N=8$, insertion sort will take time 64 and quick sort will take time 48.

Now suppose the constants are $C\_1 = 1$ and $C\_2 = 4$. Then for $N=4$, insertion sort will take time 16 while quick sort will take time 32; for $N=16$, both sorts will take time 256. For $N=8$, insertion sort will take time 64 and quick sort will take time 96.

In the former scenario, the break-even point was 4, and in the latter it was 16, but despite the $4:1$ difference in break-even point, the time required for insertion sort and quick sort will be within 50% of each other for $N=8$. If one knows that the real situation is somewhere between those two scenarios, determining the exact break-even point may allow some performance improvement versus simply using a value of 8, but using 8 will be at most 50% worse than using the optimal value. Note further that because a program is unlikely to spend most of its time sorting regions of size 8, the 50% difference in time to sort regions of that size will generally have only a small effect on overall sorting performance.
> 4 votes

# Answer
Hand-write an insertion sort and a merge sort for a list with 3 items, down to assembly code. Pay attention to:

* \# of comparisons performed
* \# of registers loaded
* other lower level or higher level considerations: # of assembly instructions, variance introduced by the randomness in quicksort, etc.

Now see if you can give different weights to the operations that might represent two different systems - for instance, one that's comparison-optimized and one that's register loading-optimized, and compute total . If you can get different results, then it's systems-dependent. If you always get the same result, the one algorithm is always faster.

This should give you a rigorous way to think about these problems.
> 1 votes

# Answer
Imagine an implementation where a function call is very, very expensive. Say so expensive that in the time it takes to do one function call, you can sort an array of 1000 elements with insertion sort.

Do you think that would influence the optimal switching point?
> 0 votes

# Answer
When a partition reaches the size that can fit in a machine dependent sized cache, then it will be faster . It's more interesting to look at the mathematics behind the machine independent answer of 10 being the cut off point. C\_N is the number of comparisons to sort N elements; in quick sort, each element is compared with the partitioning element until the left and right pointers cross ( so the last comparison happens once again ), so there are N + 1 comparisons for the current partitioning call. Then there are recursive calls on the left and right partitions either side of the partitioning element. In randomized quicksort, where all the elements are shuffled first, then the average number of comparisons in the two partitions is given by $ { \sum\_{j=0}^N \big( C\_{j-1} + C\_{N-j-1} \big) \over N } $.
The goal is then to simplify the solution of the quicksort average comparison count equation , and then incorporate the given average comparison cost of insertion sort $ {j(j-1) \over 4 } $ at a given cutoff $M$. The sum is simplified, because there is symmetry of C terms around half $N$. $ {2 \over N} \sum\_{j=0}^N C\_{j-1} $ Eliminate the sum by subtracting the equation for $N-1$ $$ C\_N = N + 1 + {2 \over N} \sum\_{j=0}^N C\_{j-1} $$ minus $$ C\_{N-1} = (N-1) + 1 + { 2 \over N-1} \sum\_{j=0}^{N-1} C\_{j-1} $$ Multiply by N and N-1 respectively the equations to make the subtraction easier. $$ N C\_N - (N-1) C\_{N-1} = N(N+1) - (N-1)(N) + 2 \bigg(\sum\_{j=0}^N C\_{j-1} -\sum\_{j=0}^{N-1} C\_{j-1} \bigg)$$ Collecting terms and subtracting the sums, $$ N C\_N = (N-1)C\_{N-1} + 2N + 2 \bigg( C\_{N-1} \bigg) = (N+1)C\_{N-1} + 2N $$ Dividing by N(N+1) , the suitable summation factor, which simplifies to a recurrence equation that can be telescoped. $$ {C\_N \over N+1} = {C\_{N-1} \over N} + { 2 \over N+1} $$ Telescope, whilst maintaining that $ C\_{N-1} \<\> C\_{M} $ $$ {C\_N \over N+1} = {C\_{M+1} \over M+2} + \bigg(2 \sum\_{j=M+3}^{N+1} {1 \over j} = 2 \big( \sum\_{j=1}^{N+1} {1\over j} - \sum\_{j=1}^{M+2} {1\over j} \big) \bigg) $$ $C\_{M+1}$ follows the original recurrence equation, but with the insertion cost inserted instead of recursive partitioning. $$ {C\_{M+1} \over M + 2} = (M+1) + 1 + 2 \sum\_{j=1}^{M+1} {j(j-1) \over 4} $$ Since $ \sum\_{j=1}^{P} { P \choose Q} = { P+1 \choose Q+1} $ $$ {C\_{M+1} \over M + 2 } = M + 2 + 2/2 { M+2 \choose 3} = M + 2 + (M+2)(M+1)(M) / 6 $$ $$ C\_{M+1} = 1 + { M(M+1) \over 6 } $$

Since $ \sum\_{j=1}^N {1\over j} = H\_N \approx ln N + \gamma $ , the whole equation looks like $$ C\_N = (N + 1) \bigg(1+ {M(M+1) \over 6(M+2)} + 2\big(ln (N+1) - ln (M+2) \big) \bigg) $$

So for N = 1000, C\_N is minimum when M = 10, independent of the machine.

This is a student answer (mine) to an Exercise from the AofA website, Introduction Analysis of Algorithms Sedgewick The answer is a middle school algebra expansion of some answers found on a discussion forum, mainly this thread : Flores, Yao and Spreng , and a it's a good idea to try to independently reach their answers. I got to the first one, and found it came up with 6 which was the wrong answer, and re-read the thread several times before being able to understand the abbreviated answer by Yao, having to dive into the book to get his assumptions , which are explained above in a middle school algebra way ( that's about my level, after 30+ years of not doing maths ).
> -1 votes

---
Tags: algorithms, sorting, efficiency, quicksort
---


# Question
Title: Solving the recurrence T(n) = 4T(n/4) + n log n with the iterative method
I'm trying to solve

$$ T(n) = 4T(n/4) + n \log\_{10}n.$$

I'm having trouble with Iteration Method near the end. As far as I went, I obtained the General Formula as:

$$4^kT(n/4^k)+n\log n+\sum (n/4^k)\log(n/4^k)$$

And trying to get the moment when it finishes iterating:

$$(n/4^k)=1$$ $$n=4^k$$ $$\log\_4n=k$$

And here I get stuck. I know I have to substitute $k$ with $\log\_4n$ but after that I'm lost. Can I get a bit of help with explanation of every step?

Here are some more details:

Swapped $\log\_4n$ on all $k$: $$4^{\log\_4n} T(n/4^{\log\_4n})+n\log\_2n+\sum\_{n=0}^{\log\_4n}n\log n$$

From logarithm rules of $a^{log\_an} = n$, it ends like this: $$(n)(1)+n\log\_2n+\sum\_{n=0}^{\log\_4n}n\log n$$

I'm not sure how to express the sum in $n$, but as you can see already, it is $O(n\log\_2n)$, and with the Master Theorem, you obtain the same result $O(n\log n)$.

# Answer
As a practical method, assume "log" is the base 2 logarithm (if not, that's just a constant factor), and calculate T (2^20):

$T (2^{20}) = 20 · 2^{20} + 4 T (2^{18}) $ $= 20 · 2^{20} + 18 · 2^{20} + 16 T (2^{16})$ $= 20 · 2^{20} + 18 · 2^{20} + 16 · 2^{20} + 64 T (2^{14})$ ... $= (20+18+16+...+2) · 2^{20} + 2^{20} · T (1)$

So $T (n) ≈ n ((log n)^2 / 4 + T (1))$

Now you can play around with that result to get the exact recursion.
> 2 votes

# Answer
Your "General Formula" is incorrect. The third term (with the sum) is incorrect. It should be $n$ rather than $n/4^k$.

Make the suitable correction through the rest of your answer, and use the fact that

$$\sum\_{k=0}^{\log\_4 n} n \log\_{10}(n/4^k) \le \sum\_{k=0}^{\log\_4 n} n \log\_{10} n$$

and you should be able to get an upper bound from there. (The final sum is easy to evaluate as every term is the same.)
> 2 votes

---
Tags: recurrence-relation, discrete-mathematics
---


title: Project to L1 ball of specified radius

text:
# Question
Title: Project to L1 ball of specified radius
## The task

If $x \in \mathbb{R}^d$ is a $d$-dimensional vector, recall that the $\ell\_1$ norm of $x$ is given by

$$||x||\_1 = |x\_1| + |x\_2| + \dots + |x\_d|.$$

The $\ell\_1$-ball of radius $\lambda$ is the set of points $x$ such that $||x||\_1 \le \lambda$.

Consider the following algorithmic task:

Input: $x \in \mathbb{R}^d$, $\lambda \> 0$
Desired output: $y \in \mathbb{R}^d$ such that $||y||\_1 \le \lambda$ and $||x-y||\_2$ is minimized

In other words, given $x,\lambda$, the goal is to project $x$ to the nearest point in the $\ell\_1$-ball of radius $\lambda$.

This problem comes up when we want to learn a linear SVM with L1 regularization using stochastic gradient descent.

## A proposed solution in the literature

The following paper proposes a solution:

D. Sculley, Matthew Eric Otey, Michael Pohl, Bridget Spitznagel, John Hainsworth, Yunkai Zhou. Detecting Adversarial Advertisements in the Wild. KDD 2011.

They propose an iterative algorithm $A$, with the property that iterating $A$ on $x$ eventually converges to the desired $y$: i.e., the sequence $x,A(x),A(A(x)),A(A(A(x))),\dots$ converges to the desired value $y$. Their algorithm is in Figure 2 and is as follows:

Algorithm $A$, with input $x$:
1. $c := \max(\lambda - ||x||\_1,0)$
2. $d := ||x||\_0$
3. $\tau := c/d$
4. for each non-zero element $i$ of $x$, do:
5. $\qquad s := \text{sign}(x\_i)$
6. $\qquad x\_i := s \times \max(|x\_i - \tau|,0)$
7. return $x$

However, I don't see why this algorithm works. For instance, at minimum we'd want the output of this algorithm to always satisfy $\lambda \le ||A(x)||\_1 \< ||x||\_1$, but this doesn't seem to hold. This algorithm often does nothing to the input if $||x||\_1 \> \lambda$, and it typically shrinks $x$ if $||x||\_1 \le \lambda$; this seems backwards (we want the reverse).

Also, $\max(|x\_i - \tau|,0)$ is an odd expression, as we always have $\max(|x\_i - \tau|,0) = |x\_i - \tau|$, so I don't understand why the max is there.

## My question

Does the algorithm from Sculley et al. actually work? Is there a typo or an error in this algorithm? If so, can it be fixed?

# Answer
There are two typos in their algorithm. Fixing them yields an algorithm that does work. Here's the fixed algorithm:

Algorithm $A$, with input $x$:
1. $c := \max(||x||\_1 - \lambda,0)$
2. $d := ||x||\_0$
3. $\tau := c/d$
4. for each non-zero element $i$ of $x$, do:
5. $\qquad s := \text{sign}(x\_i)$
6. $\qquad x\_i := s \times \max(x\_i - \tau,0)$
7. return $x$

The first typo was in line 1: $\lambda - ||x||\_1$ should have been $||x||\_1 - \lambda$.

The second typo was in line 6: $|x\_i - \tau|$ should have been $x\_i - \tau$ (no absolute value).

With these changes, everything makes sense and the algorithm now seems to work correctly. For instance:

* If $||x||\_1 \le \lambda$, then $A(x)=x$ (since $c=0$ in this case).
* If $||x||\_1 \> \lambda$, then $\lambda \le ||A(x)||\_1 \< ||x||\_1$ (since each $x\_i$ gets mapped to something whose absolute value is smaller).
* The sequence $x,A(x),A(A(x)),\dots$ converges to the desired $y$.
* Convergence should typically be pretty fast. In particular, if $\max\_i |x\_i|$ is not too much larger than $\lambda / ||x||\_0$, then this procedure should converge exponentially fast.

(There are definitely some bad cases where this procedure converges very slowly: e.g., if $x$ has many elements whose absolute value is tiny but non-zero, and a single element whose absolute value is enormous. In this case, the algorithm still converges, but it requires $\Theta(||x||\_0)$ iterations, which might be as bad as $\Theta(d)$. However, these bad cases are pretty rare.)
> 2 votes

---
Tags: optimization, machine-learning, numerical-algorithms
---


# Question
Title: Equivalence of data-flow analysis, abstract interpretation and type inference?
@Babou's answer to a recent question reminds me that at one time I think I read a paper about the equivalence (in terms both of the facts that can be inferred or proved and the time complexity of running the inference algorithm) of *data-flow analysis*, *abstract interpretation*, and *type inference*.

In some sub-cases (like between forward context-sensitive interprocedural data-flow analysis and abstract interpretation) the equivalence is relatively obvious to me, but the question seems more subtle for other comparisons. For example, I can't figure out how Hindley-Milner type inference could be used to prove some of the properties that can be proved with *flow-sensitive* data-flow analysis.

What are the seminal references discussing the equivalences (or differences) between data-flow analysis, abstract interpretation and type inference?

# Answer
> 7 votes
Data flow analysis and type inference are specific instances of abstract interpretation.

Data flow analysis and abstract interpretation look similar since they are both about computing a fix point. Data flow analyses typically have finite-height abstract domains which ensures termination. In general, abstract interpretation does not assume such abstract domains; to deal with infinite height domains abstract interpretation uses techniques of widening and narrowing.

It turns out that type inference is also about fix-point computation, although that is far from obvious, imo. Here is a paper that explicitly shows that types are abstract interpretations: paper. Basically, types are seen as an abstraction of program concrete semantics. In Hindley-Milner type system, for instance, abstract domain of types is of infinite height and computing a (most general) type using unification is essentially performing a (very imprecise) widening operation.

# Answer
> 6 votes
A good place to learn about these three approaches and how the relate is the book Principles of Program Analysis by Nielson, Nielson and Hankin.

I don't think it's correct to say that data-flow analysis, abstract interpretation and type inference are the same thing. While there are many similarities, and maybe more than would expect, given that the three originated in different communities, there are also many differences.

# Answer
> 5 votes
I consider them as basically the same. They just had initially different goals and were coined by different computer science factions.

Data flow analysis comes from the compiler engineering faction, trying to talk about their optimization algorithms and proofing upper bounds on their complexity etc.

Abstract interpretation comes from the formal, mathematical field of computer science. This is an even more formal version with more interest in correctness and less in building real compilers.

Type inference comes from the academic field of functional programming where it was initially a tool to do cool stuff with compilers. Then the idea came up, that a type can be a lot more than just "int" or "float" but also other stuff like in classic data flow analysis.

---
Tags: reference-request, compilers, type-inference, program-optimization
---


title: Can QBF encode #QBF?

text:
# Question
Title: Can QBF encode #QBF?
In another question Initializing non-deterministic variables in QBF, I was interested about translating assertion-based pseudocode to QBF in order to have an exponentially more compact encoding compared to unrolling deeply nested loops into SAT.

While some misunderstandings in the pseudocode for that question ultimately led to several answers adding in 'cheating' simplifications not in the spirit of the original question, D.W. clarified that a full answer depends on the relationship between PSPACE and #PSPACE.

Formally PSPACE and #PSPACE are "incompatible" for comparison in a sense of being a decision problem versus a counting problem, but this artifact can be made consistent in analogy to PH versus #P. Decision classes such as PP and ⊕P find the most-significant bit of the #P counting problem and least-significant bit respectively. Reductions filling in the rest of the bits of #P output *should* be rather straightforward given a powerful PSPACE-complete oracle, since P<sup>#P</sup> ⊂ PH ⊂ PSPACE.

Looking at the following assertion pseudocode, it's obvious that counting solutions to either SAT (#SAT) or QBF (#QBF) is trivially possible using polynomial-space. For example, the following pseudocode would naively run in exponential time, but never uses more than a linear O(n) amount of memory. This renders, via abuse of notation, #PSPACE ⊂ PSPACE.

```
counter = 0
for loop_aux_0 in {0,1}:
  for loop_aux_1 in {0,1}:
    for loop_aux_2 in {0,1}:
      .
        .
          .
            for loop_aux_n in {0,1}:
              counter += f(loop_aux_0, loop_aux_1, .., loop_aux_n)
assert(counter != UINT_MAX)

```

Here f is an arbitrary PSPACE function that outputs 0 or 1.

**If there are no objections that #PSPACE ⊂ PSPACE, how can I actually encode #QBF as part of a QBF instance?**

I suggested a QBF implementation (although missing initialization) utilizing an adder circuit for counter with its output fed back in as input alongside f\_ouput being the carry-in of the LSB:

∃ counter\[n\] ∀ loop\_aux\[n\] ∃ f\_output\[1\] (counter += f\_output) & (f\_output == f(loop\_aux\_0, loop\_aux\_1, .., loop\_aux\_n))

The problem with this encoding is that the counter is incremented non-deterministically without initialization, rendering any value of counter satisfiable. Can this encoding be saved with additional clauses or auxiliary variables to initialize the counter? Or is there a better way to encode #QBF in QBF?

# Answer
> 1 votes
Strictly speaking, this is a category confusion: it's an apples-vs-pears comparison. You can't compare SAT to #SAT; SAT is a decision problem (determine whether a formula $\varphi$ has a satisfying instance), #SAT is a counting problem (count the number of satisfying assignments to $\varphi$). They have a different API: they both take a formula $\varphi$ as input, but SAT outputs either "satisfiable" or "not satisfiable", while #SAT outputs a number. They're not the same, and you can't encode a #SAT instance as a SAT instance.

The same is true for counting the number of values of $x$ that satisfy a formula $\varphi(x)$, where $\varphi$ contains nested quantifiers (e.g., $\varphi(x) = \exists y . \forall z . \psi(x,y,z)$ or something). It's a category error: one is a decision problem, the other is a counting problem.

---

However, you might be interested in the following paper:

Richard E. Ladner. Polynomial Space Counting Problems. SIAM Journal of Computing, vol 18 no 6, pp.1087--1097, December 1989.

See, for instance, the discussion of $\natural$QBF, $\natural$PSPACE, and FPSPACE(poly).

Definitions:

* $\natural$QBF is the following problem: given a QBF instance like $\varphi(x,y,z) = \exists x \forall y \exists z \psi(x,y,z)$, count the number of values $x$ such that $\forall y \exists z \psi(x,y,z)$ is true (except that is for an arbitrary number of quantifiers, not limited to just 3).
* A function $f:\\{0,1\\}^\* \to \mathbb{N}$ is in $\natural$PSPACE if there's a polynomial-*space* nondeterministic Turing machine $x$ such that $f(x)$ counts the number of accepting computations of $M$ on input $x$, and $M$ makes only a polynomial number of nondeterministic choices.
* A function $f:\\{0,1\\}^\* \to \mathbb{N}$ is in FPSPACE(poly) if $f(x)$ is bounded by a polynomial in the length of $x$ and there's a *deterministic* polynomial-space algorithm (Turing machine) that computes $f$.

The paper proves that $\natural$PSPACE = FPSPACE(poly) and that $\natural$QBF is complete for $\natural$PSPACE and that there is a polynomial-space algorithm for computing $\natural$QBF.

We could consider the following problem:

BIT\_OF\_COUNT: Input: an index $i$ and a QBF instance $\varphi$
Desired output: the $i$th bit of the solution to this QBF instance.

This is one way to build a decision problem associated with a $\natural$QBF instance.

By the above remarks, BIT\_OF\_COUNT is in FPSPACE(poly) (since $\natural$QBF is). Since its output is in 0 or 1, that means BIT\_OF\_COUNT is actually in PSPACE. Since QBF is complete for PSPACE, that it must be possible to reduce BIT\_OF\_COUNT to QBF, i.e., to translate an instance for BIT\_OF\_COUNT into an instance for QBF, by chaining all the reductions.

It sounds like this might be what you want. So, if you study that paper and chain all the reductions together, you might get what you want. It looks a bit intimidating on first glance, but perhaps if you understand the meat of the reductions you'll be able to simplify somehow. The key trick in the paper seems to be the one used on pages 1091--1092, using ann algorithm to compute the product or sum of two $b$-bit numbers in $O(\lg b)$ space as a subroutine.

I hope someone will be able to give you a better answer.

---
Tags: complexity-theory, satisfiability, model-checking
---


# Question
Title: Why should small o notation has to satisfy the equation for all values of the constant
Big-O of a function i.e. f(n) = O(g(n)) is such that both **c** and $\textbf{n}\_0$ can be assigned values depending upon the function f(n). If such is the case for Big-O, then why for small-o, the following condition exists:

> f(n) = o(g(n)) means for all c \> 0 there exists some $\text{n}\_0$ \> 0 such that 0 ≤ f(n) \< cg(n) for all n ≥ $\text{n}\_0$. The value of $\text{n}\_0$ must not depend on n, but may depend on c.

But for the conditions,

> for all c \> 0
>
> $\text{n}\_0$ may depend on c

we can simply select the value of $\text{n}\_0$, based on the value of c, so that the equation is satisfied. So why should it satisfy for all values of c ?

# Answer
> 1 votes
Here's the intuition:

* big-O ($O(\cdot)$) is sort of like an asymptotic version of "$\le$" (less than or equal)
* little-O ($o(\cdot)$) is sort of like an asymptotic version of "$\<$" (strictly less than)

Just like it is useful to have both $\le$ and $\<$, it is useful to have asymptotic versions of those.

---

Now for the definition to *actually* behave like "an asymptotic version of $\<$", we need it to be phrased the way it is.

For $f(n) = o(g(n))$ to hold, we want $f$ to grow asymptotically strictly slower than $g$. If there was some $c$ such that $f(n) \approx c \cdot g(n)$ for all $n$, then $f$ would be growing at asymptotically the same rate as $g$, so we wouldn't want $f(n) = o(g(n))$ to be true. That's why the definition is the way it is.

---

Why does the condition say "for all $c\>0$" rather than "for all $c$"?

Well, when $c=-42$ (say), the condition $0 \le f(n) \< c g(n)$ simply cannot hold. For the functions we consider in computer science, it is assumed that $f(n),g(n)$ are never negative. Now you can't have $f(n) \< -42 \cdot g(n)$, since a positive number can't be less than a negative number.

So if we replaced "for all $c\>0$" with "for all $c$", it'd be impossible to satisfy the conditions of the definition. We want, for instance, $n^2 = o(n^3)$ to be true... but if we changed the definition to use "for all $c$" instead of "for all $c\>0$", it wouldn't be true. So we craft the conditions of the definition so they are attainable in at least some cases, to ensure the definition doesn't become degenerate and useless.

# Answer
> 2 votes
Consider this also (more?) common definition:

$\qquad\displaystyle f \in o(g) \quad\mathbin{:\\!\\!\iff}\quad \lim\_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Do you see now why we need to get below *all* factors $c$ in your definition? If not, we would have $f \in \Omega(g)$.

---
Tags: algorithms, algorithm-analysis, asymptotics
---


# Question
Title: Computer vision: Why do random filters perform similar to edge detectors?
I read here that "a randomly initialized filter acts very much like an edge detector!". I want to know if there are any papers describing and explaining this phenomenon.

# Answer
## Intuition, for a small case

Why? Let's look at the simplest possible case, where the kernel is 1x2 (i.e., two pixels wide and one pixel high).

Here's a kernel matrix for an edge detector that detects vertical edges:

$$E\_1 = \[-1 \\; +1\]$$

Here's another matrix for an edge detector that also detects vertical edges:

$$E\_2 = \[+1 \\; -1\]$$

In particular, convolution with $E\_1$ responds strongly to edges that are vertical and where the right side of the edge has higher intensity and the left side has lower intensity (whiter on the right, blacker on the left). $E\_2$ responds strongly to vertical edges with the opposite intensity variation (whiter on the left, blacker on the right).

We can see that the same is true for other examples. For instance, consider

$$E\_3 = \[+1.7 \\; -1.7\]$$

This behaves almost identically to $E\_2$, except for rescaling at its output.

For simplicity, let's focus on convolution kernels that have been normalized so their entries sum to zero. (Many convolution kernels we use in practice have this form, because they have nice properties.)

What about a random 1x2 matrix? Well, if it has been normalized, then it will necessarily have the form

$$M = \[+\alpha \\; -\alpha\]$$

for some constant $\alpha$ (where $\alpha$ is random). Regardless of what $\alpha$ is, we see that this behaves like either $E\_1$ or $E\_2$.

Conclusion: a random, normalized 1x2 convolution filter behaves like a vertical edge detector, with high probability.

## Bigger cases

This can be generalized to other sizes of kernels. For a random, normalized 2x1 kernel, we'll basically get a horizontal edge detector. A random, normalized 2x2 kernel will likely respond to edges in some direction (maybe at some angle; the specific direction will depend on the entries of the matrix).

As the matrix gets larger and larger, this effect diminishes (I think). However, typically in practice we use a relatively small convolution kernel (a fairly small receptive field), so we really care mostly about the behavior with small convolution kernels.

## Normalization

What about normalization? So far I've been talking about matrices that were generated randomly and then normalized to sum to zero. What if we skip the normalization step?

Well, this doesn't change very much. Without normalization, a $m \times n$ random matrix $M$ can be decomposed into $M=M' + c \cdot A$ where $M'$ is normalized so its entries sum to zero, $c$ is a constant, $A$ is the matrix containing $1/(mn)$ in every entry.

Convolving the input image with $M'$ has a good chance of being basically applying an edge detector filter to the input image (as discussed above). Convolving the input image with $c \cdot A$ will basically blur the image and then multiply by $c$. Thus, the output image is the (weighted) sum of these two: the (weighted) sum of an edge detector filter plus a blurred version of the image.

For a random matrix, there's a decent chance that $c$ will be relatively small (since the mean of the sum of a bunch of random variables is often fairly small), so multiplying by $c$ makes the output image be determined more by the edge detector than by the blurring. If $c$ is small, we can basically ignore the second term of the sum and approximate the output image as the result of an edge detector filter.

That's why convolution with a random matrix has a decent chance of looking like applying some kind of edge detector to the input image.

Looking at the example images on those pages, to my eyes the first one looks more or less like an edge detector, and the second one looks more or less like a blur operator. This is consistent with the analysis above.
> 6 votes

---
Tags: machine-learning, computer-vision
---


# Question
Title: Removing common background in image processing phase for classification
I'm trying to build a machine learning classifier that can detect which object is in an image. I have a labled training set of images and am currently in the image processing phase. Each of these images has one of the objects. However, almost all images have these objects embedded in a very common background color amongst all images.

These are not the images i'm training on but they give the general idea:

The background red is more or less uninformative of what object is in the picture. In order to reduce the dimensionality of my problem, I'd really like to apply an algorithm that somehow extracts the object from the common background. My idea after that was then to resize the resulting images all to some common dimension. Then i was going to try to do some deep learning. Does anyone know any algorithms in computer processing that can do this?

# Answer
> 2 votes
Try using clustering on the histogram of pixel color values. I would suggest using $K$-means using $K=2$ as a starting point, but you could use any clustering algorithm.

You might want to convert to HSV color space, build a histogram of the hues, and apply clustering on those values. You could also try other color space models, like CIELAB, but HSV is probably good enough for your purposes. Working in HSV space tends to yield techniques that are more robust to variation in lighting/illumination.

In your examples, the majority class (the cluster containing the majority of pixel values) is the background. You could use heuristics, such as that the cluster that contains the majority of pixels along the boundary of the image is more likely to be the background.

The watershed algorithm or other methods of image segmentation could be an alternative approach that might work well.

If your images are as clean as shown in the example, almost anything should work well.

---
Tags: machine-learning, image-processing, computer-vision
---


title: Operating system processes

text:
# Question
Title: Operating system processes
I'm a bit confused about this question:

> "Multiple jobs can run in parallel and finish faster than if they had run sequentially. Suppose that two jobs, each needing 10 minutes of CPU time, start simultaneously. How long will the last one take to complete if they run sequentially? How long if they run in parallel? Assume 50% I/O wait."

Answer from textbook (Modern Operating Systems 4th edition by Tanenbaum)

> "If each job has 50% I/O wait, then it will take 20 minutes to complete in the absence of competition. If run sequentially, the second one will finish 40 minutes after the first one starts. With two jobs, the approximate CPU utilization is 1 − 0.52. Thus each one gets 0.375 CPU minute per minute of real time. To accumulate 10 minutes of CPU time, a job must run for 10/0.375 minutes, or about 26.67 minutes. Thus running sequentially the jobs finish after 40 minutes, but running in parallel they finish after 26.67 minutes."

I don't understand why it will take 20 minutes for each job to complete if the IO wait time is 50%. Doesn't that just mean 5 minutes of CPU time is spent waiting for I/O?

# Answer
> 5 votes
50% I/O wait time means that a process is not in execution(i.e. CPU is sitting idle) for 50% of the **total time a process requires from CPU to complete itself(its execution)**. Thus CPU Utilization turns out to be //whereas 50% I/O time means it needs 50% of total execution time(10 minutes) to complete its I/O.

50%=50/100 = .5

thus the time needed to complete a process which requires 10 minute of CPU will be = *CPU time required by process/CPU utilization*=

10/CPU utilization= 10/0.5 = 20 minutes.

when two processes run sequentially(one after the other) then the total time required will be = 10/0.5 + 10/0.5 = 20+20=40 minutes (ANSWER)

**in case of parallel execution we again find the CPU utilization**.. since two processes are in parallel thus the formulae becomes--\>

***{1-(I/O time)^no. of processes in parallel execution}*** =1-(0.5)^2=1-.25=0.75 now the CPU utilization for 1 process will be 0.75/2=0.375 Therefore the time required will be = CPU time required by process/CPU utilization= 10/0.375=26.67 minutes.

Since the two processes are running in parallel thus the time required by 1 process will be the total time required by 2 process=26.67 minutes(ANSWER)

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


title: Type inference + overloading

text:
# Question
Title: Type inference + overloading
I'm looking for a type inference algorithm for a language I'm developing, but I couldn't find one that suits my needs because they usually are either:

* à la Haskell, with polymorphism but no ad-hoc overloading
* à la C++ (auto) in which you have ad-hoc overloading but functions are monomorphic

In particular my type system is (simplifying) (I'm using Haskellish syntax but this is language agnostic):

```
data Type = Int | Double | Matrix Type | Function Type Type

```

And I've got an operator * which has got quite some overloads:

```
Int -> Int -> Int
(Function Int Int) -> Int -> Int
Int -> (Function Int Int) -> (Function Int Int)
(Function Int Int) -> (Function Int Int) -> (Function Int Int)
Int -> Matrix Int -> Matrix Int
Matrix Int -> Matrix Int -> Matrix Int
(Function (Matrix Int) (Matrix Int)) -> Matrix Int -> Matrix Int

```

Etc...

And I want to infer possible types for

```
(2*(x => 2*x))*6
(2*(x => 2*x))*{{1,2},{3,4}}

```

The first is `Int`, the second `Matrix Int`.

Example (that doesn't work):

```
{-# LANGUAGE OverlappingInstances, MultiParamTypeClasses,
  FunctionalDependencies, FlexibleContexts,
  FlexibleInstances, UndecidableInstances #-}

import qualified Prelude
import Prelude hiding ((+), (*))
import qualified Prelude

newtype WInt = WInt { unwrap :: Int }

liftW f a b = WInt $ f (unwrap a) (unwrap b)

class Times a b c | a b -> c where
(*) :: a -> b -> c

instance Times WInt WInt WInt where
(*) = liftW (Prelude.*)

instance (Times a b c) => Times a (r -> b) (r -> c) where
x * g = \v -> x * g v

instance Times (a -> b) a b where
f * y = f y

two = WInt 2
six = WInt 6

test :: WInt
test = (two*(\x -> two*x))*six

main = undefined

```

# Answer
> 9 votes
I would suggest looking at Geoffrey Seward Smith's dissertation

As you probably already know, the way the common type inference algorithms work is that they traverse the syntax tree and for every subexpression they generate a type constraint. Then, they take this constraints, assume conjunction between them, and solve them (typically looking for a most general solution).

When you also have overloading, when analyzing an overloaded operator you generate several type constraints, instead of one, and assume disjunction between them, if the overloading is bounded. Because you are essentially saying that the operator can have \`\`either this, or this, or that type." If it is unbounded, one needs to resort to universal quantification, just as with polymorphic types, but with additional constraints that constrain the actual overloading types. The paper I reference covers these topics in more depth.

# Answer
> 7 votes
Oddly enough, Haskell itself is ~~perfectly~~ *nearly* capable of your example; Hindley-Milner is totally fine with overloading, so long as it's well-bounded:

```
{-# LANGUAGE OverlappingInstances, MultiParamTypeClasses,
             FunctionalDependencies, FlexibleContexts,
             FlexibleInstances #-}
import Prelude hiding ((*))

class Times a b c | a b -> c where
    (*) :: a -> b -> c

instance Times Int Int Int where
    (*) = (Prelude.*)

instance Times Double Double Double where
    (*) = (Prelude.*)

instance (Times a b c) => Times (r -> a) (r -> b) (r -> c) where
    f * g = \v -> f v * g v

instance (Times a b c) => Times a (r -> b) (r -> c) where
    x * g = \v -> x * g v

instance (Times a b c) => Times (r -> a) b (r -> c) where
    f * y = \v -> f v * y

type Matrix a = (Int, Int) -> a

```

You're done! Well, except that you need defaulting. If your language allows defaulting the `Times` class to `Int` (and then `Double`), then your examples will work exactly as stated. The other way to fix it, of course, is to not automatically promote `Int` to `Double`, or to only do it when immediately necessary, and to use `Int` literals as `Int` only (again, promoting only when immediately necessary); this solution will also work.

---
Tags: type-theory, type-inference
---


# Question
Title: Are there any known lower-bounds for complexity on Non-determinsitic machines
For some problems, like sorting, we know that on a deterministic RAM Machine, any comparison sort must take at least $\Omega(n\log n)$ time.

Are they any problems where we have known lower bounds for the complexity of a problem when using non-deterministic machines?

$NP$-hard or -intermediate problems are probably the most interesting, but others would be interesting (for example, an $\Omega(n)$ lower bound on non-deterministic sorting).

Obviously, there are no known exponential lower-bounds for $NP$ problems, since that would imply $P\neq NP$, but are they any known polynomial bounds?

# Answer
> 7 votes
No. There are no known polynomial bounds. The best lower bounds known are merely linear.

As described here, the situation for circuits at least is "quite depressing": there are no known lower bounds that are better than $\sim 4n$. That's the case even when you pick the problem. There is no explicitly known problem where we can prove a lower bound better than $4n$.

Of course, for many problems it is easy to get a lower bound of $n$, by noting that for some functions it is necessary to read all of the input bits. So we can do only a constant factor better than the trivial lower bound.

Moreover, it is easy to prove (by a counting argument) that there *exist* functions that require at least $2^n/\text{poly}(n)$ gates to compute. The catch is that this proof is non-constructive: we don't know an explicit example of such a function. So there is an exponential gap between the best lower bound we know how to prove, and what we know must be the actual best lower bounds (even though we don't know how to prove it for any specific problem).

I don't expect anything fundamental to change if you replace circuits with RAM machine algorithms. Moreover, this shows that we don't know how to prove useful/non-trivial lower bounds for deterministic algorithms. Proving useful/non-trivial lower bounds for non-deterministic algorithms is even harder.

---

(The situation might be slightly different with Turing machines, as they're a bit slower/less powerful than RAM machine algorithms -- but you asked about the latter, so I assume we can ignore this.)

You might enjoy perusing the lower-bounds tag on CSTheory.SE.

---
Tags: complexity-theory, np, nondeterminism, lower-bounds
---


# Question
Title: Is applying a formula a kind of reasoning?
Supposed I have a set of simple rules, e.g.

```
if A is between 10 and 20 and B is between 3 and 5, then use 3

```

and this rules are used in some kind of (more or less) mathematical formula (for example, A + B = C), would you count this as a form of reasoning or inference of a knowledge based system?

You have a knowledge base (the rules) and you get a result (a decision) by applying this rules in a specific way.

I'm curious about your opinions. Thanks!

# Answer
> 3 votes
You describe what is called *expert system* in AI. As such, they are artifacts of articial intelligence research.

As far as the Wikipedia definition goes,

> a reasoning system is a software system that generates conclusions from available knowledge using logical techniques such as deduction and induction,

which is vague enough to cover expert systems.

Is there any "intelligence" or independent reasoning in these systems? Certainly not; they are "stupid" in the sense that they just look up values in a table; no learning happens.

You will have to decide which frame of terminolgy reference you want to apply: academic AI or common sense?

---
Tags: terminology, artificial-intelligence, reasoning
---


# Question
Title: Efficient algorithm for getting from 1 to n with 3 specific operations
**The question:**

> Given those 3 valid operations over numbers and an integer $n$:
>
> * add $1$ to the number
> * multiply the number by $2$
> * multiply the number by $3$
>
> describe an efficient algorithm for the minimal number of operations of getting from $1$ to $n$ with the 3 operations mentioned above.
>
> For example for $n=28$ the answer is $4$ : $1\times 3\times 3\times 3+1=27+1=28$.

**My approach:**

I noticed that there is a recursive algorithm that will provide the answer but even when I used memoization the algorithm took a lot of time to end with $n\geq 1000$. I thought of a way to start with $n$ instead and try to reduce it to $1$ with the inverse operations of subtracting $1$ dividing by $2$ or by $3$ and trying to get it to be devisible by $3$ or by $2$ by subtracting $1$'s and checking the mod. But my second approach had some (more than some) mistakes where It stated that the smallest number of operations is more than it is. Please help or give a hint I clearly missing some kay fact about the nature of such operations.

**Edit:**

def ToN(n):

```
d=dict()
def to(x,num,di):
    if (num==x):
        return 0
    elif (num>x):
        return num
    elif num in di:
        return di[num]
    else:
        if num+1 not in di:
            di[num+1]=to(x,num+1,di)
        if num*2 not in di:
            di[num*2]=to(x,num*2,di)
        if num*3 not in di:
            di[num*3]=to(x,num*3,di)
        di[num]=min(di[num+1],di[num*2],di[num*3])+1
        return di[num]
return to(n,1,d)

```

I wrote the code above in python and it takes a lot of time to end for num=1000. Can you help me understand what is wrong w.r.t. efficiency.

# Answer
> 6 votes
Find the shortest path from $1$ to $n$ on an appropriate graph on vertices $\\{1, \dots, n\\}$. This approach will work whenever it's guaranteed that intermediate values in the calculations will lie within some bounded range.

# Answer
> 0 votes
An optimal solution will start with x = 1 and repeatedly replace x with 2x (1 step), 2x+1 (2 steps), 3x (1 step), 3x+1 (2 steps) or 3x+2 (3 steps).

I'd attack the problem from both ends: Find the shortest way from 1 to x, and how many steps it takes, for every x ≤ $n^{1/2}$ , and find the ways back from n to a number x ≤ $n^{1/2}$, then combine both. That should work in $O (n^{1/2})$.

For example n = 196 (just a random number)

1. 0 steps
2. 1 step
3. 1 step
4. 2 steps
5. 3 steps
6. 2 steps
7. 3 steps
8. 3 steps
9. 2 steps
10. 3 steps
11. 4 steps
12. 3 steps
13. 4 steps
14. 4 steps

From 196: 0 steps From 98: 1 step From 65: 2 steps From 49: 2 steps From 32: 4 steps From 24: 4 steps From 21: 5 steps From 16: 4 steps From 12: 5 steps From 10: 7 steps From 8: 5 steps From 7: 6 steps From 5: 6 steps

So there are two ways to get there in 8 steps. 1 -\> 8 -\> 98, and 1 -\> 12 -\> 98. The calculation was much quicker than O (n).

If you needed to solve this for multiple values n, I'd probably make the table of small values larger. For example, 100 values n around 1 million, I'd start with a table up to 10,000.

Edit about comments: In an optimal chain, x2 cannot be followed by +1, +1 because adding one before the multiplication would be shorter. And x3 cannot be followed by +1, +1, +1 because adding one before the multiplication would again be shorter. At the start with x = 1, we may assume that we don't add +1 once or twice because we can multiply by 2 or 3 instead. So there is always an optimal chain that consists of x2 possibly followed by +1, or x3 possibly followed by +1 or +2.

Finding *all* optimal solutions up to some k can clearly be done in a total of k steps. k = n^(1/2) means n^(1/2) steps. I assumed going backwards from to some x ≤ n^(1/2) would divide n by some k not much larger than n^(1/2) so could also be done in n^(1/2).

BUT you can actually do much better. By working your way backward, if the number of steps needed is S (n), then S (n) = min (S (floor (n/2)) + 1 + (n modulo 2), S (floor (n/3)) + 1 + (n modulo 3)). You either subtract 1 as long as the number is not divisible by 2, then divide by 2, or you subtract 1 as longas the number is not divisible by 3, then divide by 3.

One step back divides quite exactly by 2 or 3. There are only about log (n) steps going backwards. There are only about (log (n))^2 combinations of divisions by 2 or 3, because you end up at the same number no matter in which order you make steps dividing be 2 or 3. So you can easily find an optimal chain in O ((log (n))^2).

For example, if n = 1234567, then you can easily find the optimal chain 1 -\> 2 -\> 4 -\> 5 -\> 15 -\> 45 -\> 46 -\> 47 -\> 141 -\> 423 -\> 1269 -\> 1270 -\> 3810 -\> 11430 -\> 11431 -\> 22862 -\> 68586 -\> 68587 -\> 137174 -\> 411522 -\> 1234566 -\> 1234567 (21 steps).

---
Tags: algorithms, recursion, integers
---


# Question
Title: Convert between IEEE 754-2008 decimal64 and IEEE double precision floating point number
I need to know the algorithm for converting between IEEE 754-2008 decimal64 and IEEE 754-1985 double precision floating point number.

I have been working on this for the past 2 days and I match the exponents of the two different standards but my base 2 mantissas differ.

Any help is greatly appreciated.

# Answer
> 0 votes
IEEE 754-2008 specifies how to convert mantissas to binary fractions as in the case of the IEEE 754-1985 double precision floating point number.

---
Tags: algorithms, floating-point, number-formats
---


# Question
Title: What is the simplest known NP-Complete problem for testing P=NP solutions?
About a year and a half ago I asked this question regarding $\mathsf{P}=\mathsf{NP}$. The answers have helped me understand the problem tremendously and since then I've dabbled further into the topic.

With that stated, it is my understanding that $\mathsf{NP}$-complete problems are such that if a solution for $\mathsf{P}=\mathsf{NP}$ were found for that specific problem, then *all* $\mathsf{NP}$ problems could be solved using the same rules for resolving $\mathsf{NP}$.

With that stated, what is the simplest $\mathsf{P}=\mathsf{NP}$ problem outlined to date that is $\mathsf{NP}$-complete?

In other words, what is the most basic of problems that one could test a theoretical $\mathsf{P}=\mathsf{NP}$ solution against? I'm aware of many of the examples such as the Traveling Salesman or Knapsack problems but I assume there could be even simpler scenarios where all properties of the $\mathsf{P}=\mathsf{NP}$ or $\mathsf{P}\ne\mathsf{NP}$ dilemma are present.

# Answer
Since all NP-complete problems are basically equivalent, it's hard to say which one is the easiest. SAT was one of the original problems and has important practical applications, so it is really well studied. Writing fast SAT-solvers seems like a reasonably interesting hobby to me and getting started is not terribly hard. Integer Linear Programming is similarly important and well studied.

The only objective way to discern NP-complete problems that I know of is their approximability. Some problems are hard to approximate, for others you can get almost arbitrarily good solutions in polynomial time.

Subset sum is both very simple to understand and "simple" to solve. Simple to solve means that it has an easy Pseudo-polynomial algorithm and is easy to approximate. However, I don't know about any research involving the problem.
> 5 votes

# Answer
Take the SAT problem. If you find a procedure which solves the SAT problem in polynomial time, then you proved it. But you should not take 2-SAT because it is already known to be in P.
> 1 votes

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Does there exist a type system for a non-let-polymorphic lambda calculus?
I'm wondering if there is a way to extend Hinley-Milner's type system to allow polymorphic types without the need of a let construct, by adding an intersection type (as Dan pointed out) that represents the possible types of a function type.

Say I have this expression:

$\lambda x.\lambda y.(x\ (x\ y))$

While running the type inference algorithm, I'd normally, after looking at the expression $(x\ y)$, assign to $x$ some type $Y \rightarrow A$, where $Y$ is the type of $y$ and $A$ is whatever $x$ returns. Then, since $x$ also takes $(x\ y)$ which has the type $A$, I replace $Y$ with $A$, such that the type of $x$ becomes $A \rightarrow A$ and give to the whole thing the type $(A \rightarrow A) \rightarrow (A \rightarrow A)$.

But what if I, instead of replacing $Y$ with $A$ when I see $(x\ (x\ y))$, add a new type to $x$, say, $A \rightarrow B$, such that the final type is $((Y \rightarrow A) \wedge (A \rightarrow B)) \rightarrow (Y \rightarrow B)$, which is also a tautology and seems like a better representation of what the function does.

Now say I give to this abstraction the term $\lambda n.n$ like this:

$(\lambda x.\lambda y.(x\ (x\ y))\ \lambda n.n)$

Since $\lambda n.n$ has the type $N \rightarrow N$, I'd need to unify $N \rightarrow N$ with $((Y \rightarrow A) \wedge (A \rightarrow B))$. So I instantiate two copies of $N \rightarrow N$, say $N\_1 \rightarrow N\_1$ and $N\_2 \rightarrow N\_2$, and unify $N\_1 \rightarrow N\_1$ with $Y \rightarrow A$ and $N\_2 \rightarrow N\_2$ with $A \rightarrow B$. Because $A$ would be equal to $N\_1$ on one side and equal to $N\_2$ on the other side, $N\_1$, $Y$, $A$ and $B$ are all equal to $N\_2$, so the type $Y \rightarrow B$ becomes $N\_2 \rightarrow N\_2$, which is consistent with the expression you'd get after evaluating the lambda term.

With this type system I should be able to type things like this:

$(\lambda i.\lambda x.\lambda y.((i\ x)\ (i\ y))\ \lambda n.n)$

But these examples are simple, and it becomes a pain to type something like:

$(\lambda x.\lambda y.(x\ (x\ y))\ \lambda x.\lambda y.(x\ (x\ y)))$

I'm having trouble trying to figure out what the actual rules of this system would be, like what would you do if you'd have to unify two intersection types (or whether that situation is even possible).

So my question is, am I moving towards a type system that already exists? If yes, which one? If not, is this because my type system wouldn't meet the requirements of a type system (such as being decidable)?

# Answer
I am not sure what you mean by `type system being decidable`. I guess you mean type checking and type inference. (strictly speaking type inference is not a decision problem, although it can be casted as one and people usually think of it that way).

In addition to intersection types, I would also suggest looking at System F where universal quantification does not appear only at the let construct. For system F, type inference is undecidable: paper
> 3 votes

---
Tags: lambda-calculus, type-theory, type-inference
---


# Question
Title: How can I get O(1) prepend on a random-access list?
I need a data structure that has the following operation:

* $\operatorname{prepend}(\[x\_{n - 1}, ..., x\_0\], x\_n) = \[x\_n, ..., x\_0\]$

$\operatorname{prepend}$ should be in $O(1)$.

Assume that you have only randomly-accessible lists available. That is the following operations are available that are all in $O(1)$:

* $\operatorname{update}(\[x\_n, ..., x\_0\], i, y) = \[x\_n, x\_{i + 1}, y, x\_{i - 1}, x\_0\]$
* $\operatorname{at}(\[x\_n, ..., x\_1\], i) = x\_i$
* $\operatorname{append}((\[x\_n, ..., x\_1\], x\_0) = \[x\_n, ..., x\_0\]$

You could of course reverse the list in $O(n)$ each time but then $\operatorname{prepend}$ would also be in $O(n)$. So the list has to be reversed in real-time at each call of $\operatorname{prepend}$. Is there such data structure?

# Answer
A deque with growing arrays provides the operations you need in (amortized) constant time. Reversing a deque is simple, you don't move data around, you just switch the meaning of `prepend` and `append` and massage the index for `at` and `update`.

But you don't seem to want to reverse the list anyway.
> 5 votes

# Answer
The data structure: To represent an array with n elements, you have a backing array with N ≥ n elements, which contains for some k the elements a(k) to a (n-1), then a gap, then the elements a(0) to a (k-1). Inserting and removing elements both at the start and the end of the array is quick (linear in either distance to the start or the end of the array).

After inserting enough elements to remove the gap completely, the array needs to be resized in amortized constant time.

If an operation were to insert / remove at the start of the backing array (that is close to index k), then k will likely need to be changed. Inserting / removing in the middle of the array takes linear time.
> 1 votes

---
Tags: data-structures, arrays, lists
---


title: Binary rooted tree isomorphism

text:
# Question
Title: Binary rooted tree isomorphism
My trees are rooted and have at most two children at every vertex. I need references that help me solve any or all of the questions below:

* How many isomorphism classes of trees with n vertices are there?
* What are the classical algorithms to decide if two given trees are isomorphic?
* Is there a nice (computable?) isomorphism invariant?

Of course, the answers may depend on the structure used to define the trees, but I guess the correct choice of structure is part of the answer I am seeking.

# Answer
There is a classical linear time algorithm for rooted tree isomorphism due to Aho, Hopcroft and Ullman. The algorithm actually uses a simple isomorphism invariant. See for example lecture notes of Vikram Sharma. Using this, you can solve unrooted tree isomorphism in linear time, as described for example in Smal's slides. Another classic algorithm is due to Buss.
> 10 votes

---
Tags: algorithms, graphs, reference-request, combinatorics, trees
---


title: Prove or disprove that DTIME(n^2)=NL

text:
# Question
Title: Prove or disprove that DTIME(n^2)=NL
I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\log n\ 2^{\log n}=|Q|\log n \ n^2 = \omega(n^2)$ ($Q$ denotes the number of states) different configurations, which bounds the running time, therefore intuitively it looks like I'll need more then $n^2$ to run $M$.
Can someone explain to me how would you approach to these types of problems? Because I always find my self resorting to "trial and error" with diagonalization and padding arguements.
Thanks in advance.

# Answer
Let's say that a class $\cal C$ is closed under "reverse quadratic padding" if for any language $L$, if $Q(L) = \\{\langle |x|, 0^{|x|^2} \rangle : x \in L \\}$ belongs to $\cal C$ then $L$ also belongs to $\cal C$.

The class $\mathsf{NL}$ is closed under reverse quadratic padding: if $Q(L) \in \mathsf{NL}$, then we can decide $L$ itself in $\mathsf{NL}$ by simulating the decider for $Q(L)$. For that we use our ability to count up to $n^2$ (here $n$ is the input length), noticing that $O(\log(n^2)) = O(\log n)$.

In contrast, the class $\mathsf{DTIME}(n^2)$ isn't closed under reverse quadratic padding. Indeed, use the time hierarchy theorem to find a language $L \in \mathsf{DTIME}(n^3) \setminus \mathsf{DTIME}(n^2)$. Then $Q(L) \in \mathsf{DTIME}(n^2)$, whereas $L \notin \mathsf{DTIME}(n^2)$.
> 2 votes

---
Tags: complexity-theory, time-complexity, space-complexity
---


title: On the fly manipulation of operators

text:
# Question
Title: On the fly manipulation of operators
Assume that you are writing sorting algorithms, and that you want the ability to select between ascending and descending order. The only change required to do this for comparison sorts is to use the inverse of the comparison operator (for example: \> becomes \<). This begs the question, why is it not possible to change operators on the fly?

A simple bubble sort for ascending order:

```
private T[] BubbleAscending(T[] sortMe)
    {

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) > 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

```

Now we have to have a Bubble sort for descending order:

```
private T[] BubbleDescending(T[] sortMe)
    {

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) < 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

```

Now we have to have some logic to allow the user to easily select between them:

```
public T[] BubbleSort(T[] sortMe, bool descending)
    {
        if (!descending)
            return BubbleAscending(CopyArray(sortMe));

        else
            return BubbleDescending(CopyArray(sortMe));
    }

```

Wouldn't it be much simpler if we could do this?

```
public T[] BubbleSort(T[] sortMe, bool descending)
    {
        if (!descending)
            operator comparison = >;

        else if (descending)
            operator comparison = <;

        bool stopMe = true;
        int stopRecurse = sortMe.Length - 1;
        int optimizeMe = stopRecurse;

        for (int i = 0; i < stopRecurse && stopMe; i++)
        {
            stopMe = false;

            for (int j = 0; j < optimizeMe; j++)
            {
                if (sortMe[j].CompareTo(sortMe[j + 1]) comparison 0)
                {
                    Swap(sortMe, j, j + 1);
                    stopMe = true;
                }
            }

            optimizeMe--;
        }

        return sortMe;
    }

```

# Answer
Welcome to the wonderful world of functional programming and the lambda calculus!

The answer is, there is no reason that you can't do this, and most sufficiently modern programming language (and some ancient ones i.e. LISP) will let you do this.

In a language with first-class functions, functions are data. You can treat them as variables, pass them as parameters, define them as lambda expressions (i.e. a nameless function). So in most languages, you can do something like this:

```
if (descending)
  comparison = lambda x y -> x < y
else
  comparison = lambda x y -> x > y

```

The lambda is just a way of saying "comparison a function which takes two arguments and returns the value after the -\>".

Treating functions as data is an idea as old as computer science itself: lambda calculus was developed by Alan Turing's supervisor, Alonzo Church, in the 1930s.

Not being able to do this is a restriction of C and Java (although new versions are introducing lambdas), and a few other languages.

What you've shown is probably not possible because it's hard to parse (most parsers rely on the fact that `<` and `>` are special characters), but if you treat comparison as a normal function instead of an infix operator, and use a language that allows for higher-order functions, you can indeed do this, and in many cases it is preferable.
> 1 votes

---
Tags: programming-languages, sorting, api-design
---


# Question
Title: Why isn't a binary counter used for generating $k$-combinations?
I have been looking at algorithms that allow you to generate $k$-combinations of a given string.

My question is that why isn't the algorithm used to generate power sets used to generate the combinations of a given string? That is, we can just use a binary counter of length $n$ with $k$ ones set to select $k$ elements from a length $n$ string. The method is very simple.

I mean, the power set can represent all $k$-combinations of the input. So why use complex algorithms like the ones described here (e.g., Gray codes)?

# Answer
> 2 votes
For concreteness, suppose you have a string $S$ of length $n = 10$. You want to generate all $k$-combinations of $S$ for some $k$, say $k = 3$. When you use a binary counter (using $n$ bits), you go through $2^n = 2^{10} = 1024$ values, corresponding to all possible subsets. On the other hand, there are only ${10 \choose 3} = 120$ possible 3-combinations choosable from $S$. So wouldn't it be nice if you could only perform 120 steps instead of 1024? I encourage you to play around with larger numbers, and consider how quickly these numbers actually grow.

There might also be other reasons to consider e.g., Gray codes. Some algorithms have particular properties that might be crucial for certain applications. For instance, we might want that there's exactly one change between two adjacent combinations, or so on.

---
Tags: algorithms, strings, enumeration
---


title: Why is Knapsack and ILP NP-complete

text:
# Question
Title: Why is Knapsack and ILP NP-complete
I have a question concerning several NP-hard problems and why they are (or are not NP-complete).

I understand the concepts behind NP-hard and NP-complete: Problem lies in NPC if it is NP-hard and also in NP (we can verify its solution in polynomial time).

I know that **Traveling Salesman** (TSP) is NP-hard but isn't *NP-complete* (NPC), because in order to verify its solution, we would need to check that no better solution exists and hence solve it in polynomial time (so its not in *NP*).

However, problems like **Knapsack** or **ILP** (Integer Linear Programming) are said to be in *NPC*. Why is that? Isn't there the same analogy as with **TSP**? If someone gives us a solution and claims it is optimal, we would need to verify that no better solution exists and therefor solve these problems to obtain it in polynomial time.

Why is **ILP** and **Knapsack** in *NPC* and not just *NP-hard*? I hope my question is not too confusing, I will try to rephrase it if so.

# Answer
> 8 votes
As discussed in the comments, this question hinges around subtleties of the definitions. **NP** is a set of decision problems (problems with yes/no answers), so any problem such as "Find the shortest XXX" is automatically excluded. Natural problems come in a number of variants and it's sometimes important to distinguish between them.

To a complexity theorist, the travelling salesman problem (TSP) is *exactly* the following problem:

* Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities, and a target distance $d$.
* Question: Is it possible to start at one of the cities, visit every other city exactly once and return to the starting city while travelling total distance at most $d$? (Equivalently, does the shortest such route have total length at most $d$?)

Then there is the following optimization problem, MIN-TSP:

* Input: An $n\times n$ matrix giving the pairwise distances between $n$ cities.
* Question: What is the shortest distance it is possible to travel in order to start at some city, visit each of the others exactly once and return to the start city?

There are also other variants: F-TSP (function-TSP) has the same input as TSP but the output is a route of length at most $d$, if one exists, and "no", otherwise, rather than just yes or no; F-MIN-TSP is the analogous version of MIN-TSP.

These problems are all inter-related but they're not the same problem. In particular, only TSP is a decision problem: MIN-TSP is an optimization problem and the F- problems are function problems. TSP itself is **NP**-complete. If you can solve MIN-TSP, you can clearly solve TSP by computing the minimum and comparing it against $d$, so MIN-TSP is **NP**-hard (but can't be complete because it's not a decision problem so it's not in **NP**). Conversely, if you can solve TSP and you're allowed to make multiple TSP queries, then you can solve MIN-TSP by binary search.

For the function versions, being able to solve F-TSP clearly allows you to solve TSP: if F-TSP gives you a route, say "yes"; otherwise, say "no". Similarly for F-MIN-TSP. On the other hand, it's not clear that being able to solve TSP helps you solve F-TSP: being told that it's possible to visit the capitals of the 48 contiguous states and Washington, D.C., while travelling a total of less than 11,000 miles doesn't seem to give you much of a hint as to what the route would be.

Your other two examples have the same families of variants. The standard Knapsack problem has a tarvet value $v$ and asks if your knapsack can carry items of total value at least $v$; OPT-Knapsack asks what is the greatest value you can carry. ILP asks if the linear inequations have an integer solution; OPT-ILP asks for the maximum solution. In both cases, the decision version of the problem is **NP**-complete and the optimization version is **NP**-hard.

---
Tags: complexity-theory, np-complete, np-hard
---


# Question
Title: Why is quiescent consistency compositional, but sequential consistency is not
I'm having trouble in comparing these two memory consistency models.

Essentially for sequential consistency I think of real code like this:

```
int x, y;

void ThreadA()
{
   x = 20; //Write
   int a = y; //Read
}

void ThreadB()
{
    y = 20;
    int b = x;
}

```

In a sequential consistency environment it's impossible for `a` or `b` to not be 20. That is either `a = 20`, `b = 20` or `a = 20 && b = 20`.

But how does quiescent consistency fit in to this example, and why is it compositional?

# Answer
Sorry for the late reply, but I've just found the question (questions, indeed). I am studying concurrency as well and I'll try to share some ideas with you.

First, let's start with sequential consistency. A model has this property if operations appear to take effect in program order. In other words, the order in which lines of code are executed is the one specified in the source file. This prerequisite is thread-specific: operations involving different threads are unrelated by the program order. So, the property grants the following: operations issued by the same thread are executed in the same order specified by the thread source code. Operations issued by different threads can happen in any order. This prerequisite may seem obvious, but it is not always the case (compiler optimizations may change the order in which operations are issued, thus making the program order different from the source).

Your example is right, but let me give you some others. Consider this program P1 (I'll tag each line for an easy reference):

```
   int x = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A3:    int a = x;
   }

   void ThreadB()
   {
B2:    x = 20;
   }

```

Is there a sequential execution in which, at the end, a = 40? Yes: B2, A1, A3.

B2 and A1 can be executed in any order (they belong to different threads). A1 is executed before A3 (program order = source code order).

Now consider this program P2:

```
   int y = 1;

   void ThreadA()
   {
A2:    y = 40;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B3:    int b = y;
   }

```

Is there a sequential execution in which, at the end, b = 20? Yes: A2, B1, B3.

What about composition? Let's compose P1 and P2. We get P1∘P2:

```
   int x = 1;
   int y = 1;

   void ThreadA()
   {
A1:    x = x * 2;
A2:    y = 40;
A3:    int a = x;
   }

   void ThreadB()
   {
B1:    y = y / 2;
B2:    x = 20;
B3:    int b = y;
   }

```

If sequential consistency were compositional, then there should be an execution in which, at the end, a = 40 and b = 20. Is this the case? No. Let's give a formal proof oh why it can't be the case. I'll write "o1 → o2" to say that the operation o1 must be executed before operation o2.

In P1∘P2, due to sequential consistency, the following must holds: A1 -\> A2 and B1 -\> B2 (per-thread program order). In order to get a = 40 also B2 -\> A1 must hold. In order to get b = 20 also A2 -\> B1 must hold. Can you see the precedence chain? A1 -\> A2 -\> B1 -\> B2 -\> A1 -\> ...

P1 and P2 were sequentially consistent, but their composition P1∘P2 was not. Sequential consistency is not compositional. The example you provided was not tricky enough to show this fact.

Now, let's consider quiescent consistency. It's difficult for me to explain this property without using the object-oriented paradigm. In fact, quiescent consistency can be easily understood in terms of pending method calls on objects. Nevertheless, I'll try to stick with the imperative paradigm (pending method calls become functions started but not completed, objects become variables involved in functions).

A function call is composed by an invocation and a response. A function is pending if it has been invoked by a thread but it has not returned a response yet to such thread. A period of quiescence for a variable is a time interval in which there are no pending function calls (by any thread) operating on it. A model has the quiescent consistency property if function calls operating on the same variable and separated by a period of quiescence appear to take effect in their real-time order (the one specified by source code). From the converse point of view, the definition states that operations on the same variable executed by functions called concurrently by different threads (not separated by quiescence) can happen in any order.

I've tried for many hours to design a meaningful example using only read-write operations to show you the difference between quiescent and sequential consistency, but I didn't succeed. Let me use another example involving sets. I will use a bit vector to keep track of which integers (from 0 to 4) are in the set:

```
   int set[5] = {0, 0, 0, 0, 0};  // 0 if i-th item is absent, 1 otherwise

   void add(int number) {
L1:    set[number] = 1;
L2:    temp foo = set[0];
   }

   void remove(int number) {
       set[number] = 0;
   }

   int contains(int number) {
       return set[number] == 1;
   }

   void ThreadA()
   {
A1:    add(1);
   }

   void ThreadB()
   {
B1:    add(2);
B2:    remove(2);
B3:    int res = contains(2);
   }

```

Is there a sequential execution in which, at the end, res = 1? No: due to sequential consistency B1 -\> B2 and B2 -\> B3, so B1 -\> B3. So, remove(2) is always executed after add(2) and contains(2) will always returns 0.

Is there a quiescent execution in which, at the end, res = 1? Yes! Consider this execution:

Thread A invokes add(1) at A1.

Thread A executes L1 (but not L2). // since there is a pending call on the set, now Thread B is free to execute B2 before B1 because these calls involve the set as well

Thread B calls B2. // invocation + response

Thread B calls B1. // invocation + response

Thread A executes L2 and add(1) responds. // now there is quiescence on the set

Thread B executes B3. // invocation + response

Now res = 1.

Unfortunately, I still can't answer the latest question on why quiescent consistency is compositional: I found your question while I was looking for this exact answer indeed. If I come up with something I'll let you know.

For a good reading on the topic have a look at chapter 3.3 of the book "The Art of Multiprocessor Programming" by Herlihy and Shavit.

EDIT: I've just found a great page explaining why quiescent consistency is compositional. And this is another very good reading!

EDIT2: Fixed little error in the sequential consistency composability example.
> 13 votes

---
Tags: concurrency, cpu-cache, threads, shared-memory
---


# Question
Title: How do I do sum of first k elements of a row of a Pascal's Triangle efficiently?
More specifically, I want to:

$^nC\_0 + ^nC\_1 + ^nC\_2 + ..... + ^nC\_k$

I tried doing it linearly by calculating $^nC\_{j+1}$ by multiplying $^nC\_{j}$ with (n-j+1)/j.

The answer it gives is correct for small numbers. Since n and k can be large, I need have keep modding with P, a given prime number.

My method fails since I have to divide with j, which breaks the mod. Any suggestions?

# Answer
Your method is fine. You just need to know how to do modular division. Modular division is a bit different from division of two integers. You can do modular division, say $x/y \bmod p$, by computing computing the modular inverse of $y$, $y^{-1}\bmod p$, and then multiplying that by $x$. You can compute the modular inverse using the extended Euclidean algorithm.

See https://en.wikipedia.org/wiki/Modular\_multiplicative\_inverse.

A slight correction:

$${n \choose j+1} = {n \choose j} \times {(n-j) \over j+1}.$$

You had an off-by-one error in the formula. To do this modulo $p$, replace dvision by $j+1$ with multiplication by the modular inverse of $j+1$ modulo $p$.
> 2 votes

# Answer
One interesting fact about Pascal's triangle is that each rows' numbers are a power of 11. For instance, the first row is 11 to the power of 0 (1), the second is eleven to the power of 1 (1,1), the third is 11 to the power of 2 (1,2,1), etc. This identity can help your algorithm because any row at index n will have the numbers of 11^n. Then, using something like a "to\_string" conversion in C++ or the "read" function in Haskell, you can select the amount of numbers you would like to sum over in your string of numbers, convert them back to an integer, and then sum over them. Here is some pseudo-code to help illustrate my answer:

```
    int n = 7
    int k = 5
    int full_row = pow(11,n)
    string str_full_row = to_string(full_row)
    int sum=0
    int index=0
    for string i in str_full_row:
        index+=1
        sum+=(string_to_int(i))
        if index==k:
            break

```

In this case, the answer is the "sum" variable, and you don't need to use the nCr trick above. The "n" variable is the row, the "k" variable is the amount of terms within the row that you want to sum over (and it starts at 0), and the "index" simply keeps track of the the number of iterations that have happened within the for loop. I hope this helps!

EDIT: Having reviewed the answers below, I see that there is an obvious mistake for rows in which the numbers within the row are double-digit or beyond. I do not know how to correct this.
> -1 votes

---
Tags: algorithms, combinatorics
---


# Question
Title: Landau Notation: Why is O(f) (not) the set all g < c*f?
I am somewhat confused here about the Landau notations. Let's say we are dealing with function from $\mathbb{N}$ to $\mathbb{R}$. Then we can define $\mathcal{O}(f) = \left\\{ g : \mathbb{N} \to \mathbb{R} | \exists c \> 0 \text{ such that } g \leqslant cf\right\\}$. Ok, so every function $g$ that is asymptotically smaller than $f$ is in this set. So if we have an algorithm $A$ that runs at most exactly $n^2+10$ steps, then

$g1 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n^2 \in \mathcal{O}(A)$.

But also

$g2 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto n \in \mathcal{O}(A)$

or even

$g3 : \mathbb{N} \to \mathbb{R} \text{ with } n \mapsto 0 \in \mathcal{O}(A)$

satiesfy the condition to be elements of $\mathcal{O}(A)$. So, why would normally only $g1$ be the function of which one would say $g1 = \mathcal{O}(A)$ ?

I understand the $=$-sign is formally incorrect and just a convention, but if $g2$ and $g3$ also are in $\mathcal{O}(A)$ why define $\mathcal{O}$ this way, if $g1$ is the only function we care about to describe the asymptotic complexity of $A$?

# Edit

So, I see I had misunderstood the idea a little. So far I thought $\mathcal{O}$ would take an algorithm and return how long it runs asymptotically. So, what $\mathcal{O}$ actually does is the following\>: If we have an algorithm $A$ saying that

$$\forall c \> 0. \forall x \in domain(A).\lim\_{n\to\infty} T(A(x)) \leqslant cn$$ would be the same as $$T(A) \in \mathcal{O}(n)$$

Is that correct?? Something looks still wrong about that.

($T$ being the function that returns the number of steps the computation required.)

# Answer
> 7 votes
There are at least three fundamental misunderstandings, here.

1. $O(\cdot)$ only makes statements about large enough inputs to the function. It's not that there exists some $c$ such that $g\leq c\\,f$ for all $n$, but just for all large enough $n$.
2. The argument of $O(\cdot)$ is a (mathematical) function. If $A$ is an algorithm, it makes no sense to write $O(A)$: it doesn't type-check. In particular, for an algorithm $A$, we don't talk about "the order of $A$". Rather, $O(\cdot)$ is a way of comparing mathematical functions: $O(f)$ is the set of all mathematical functions $g$ such that $g(n)\leq c\\,f(n)$ for some $c$ and all large enough $n$.
3. $O(f)$ is the set of **all** mathematical functions $g$ such that $g(n)\leq c\\,f(n)$ for some $c$ and all large enough $n$. So it's simply not true that, in your example, $g\_1$ would be the only function you'd describe as being $O(n^2+10)$.

$O(\cdot)$ is defined that way because it's useful to do so: it's a way of comparing functions and it doesn't care what you use those functions for. ($O(\cdot)$ doesn't care about complexity theory, just as the meter doesn't care about Mount Everest.) So, when we say that the running time of an algorithm is, say, $O(n^2)$, we just mean that, for large enough inputs, it's no worse than some constant times $n^2$. Often, we say it that way because we don't know anything more precise. In the same vein, I'm pretty sure that you have less than a million dollars in the bank but It would be hard for me to find out how much less.

In cases where we do know something more precise, we might use $\Theta(\cdot)$, or we might use separate $O(\cdot)$ and $\Omega(\cdot)$ bounds. For example, we might say that the running time of some algorithm is $\Theta(n\log n)$, meaning that there are constants $c\_1$ and $c\_2$ such that, for all large enough $n$, the running time is between $c\_1n\log n$ and $c\_2n\log n$. For some other algorithm, we might only be able to prove that its running time is $O(n^3)$ and $\Omega(n^2)$, meaning that there are constants $c\_1$ and $c\_2$ such that, for large enough $n$, the running time is between $c\_2n^2$ and $c\_1n^3$.

# Answer
> 2 votes
As I understand it, you've failed to account for *asymtotic* behaviour, but global behavior instead.

For example, we want $n + 1$ to be in $O(n^2 - n)$ because, once your inputs get big enough, the latter will always be slower than the former. But there is no $c$ where $\forall n \ldotp c \cdot n^2 - n \geq n + 1 $. Particularly, look at $n=1$. We want $c\cdot(1-1) \geq 1+1$, and there is no such value which will satisfy this.

That's the intuition for the actual definition. We want there to be some number $m$ where we say "there exists an $m$ and a $c$ where, for all $n\>m$, we have $g(n) \geq c\cdot f(n)$" In our example, we'd set $m=2$, since once we get past that point, we can find a constant where $n^2-n$ is always bigger.

Also, be careful with your notation. What is $O(A)$? Big-O is an operation on functions, not on algorithms. You're better saying "let $f$ be the function where $f(n)$ is the maximum time $A$ takes on any input of size $n$", then saying $O(f)$.

# Answer
> 1 votes
We are not usually interested in what you call $O(A)$. This is the class of functions *lower-bounding* the time complexity of $A$, that is, they are functions $f$ such that $A$ runs in at least $Cf(n)$ steps. We're more usually interested in upper bounds on the running time, stating that $A$ runs in *at most* $Cf(n)$ steps. In your case, the running time is $O(n^2)$. It is also $O(n^3)$. Clearly the former bound is better. In general, we are interested in giving the best upper bound possible.

See also our reference question on Landau notation, if you can find it!

# Answer
> 1 votes
What you have defined there is *linear dominance*. It is indeed a reasonable definition for *an* $O$ but not *the* definition most people use.

We usually use Landau's $O$ which ignores any finite prefix of the functions at hand. That is because we have been trained to think that only behaviour for $n \to \infty$ matters. While that perspective has some advantages it is certainly not perfect.

For example, we want to assign the same "order of growth" to $10 n^2 + 5$ and $7 n^2 + 20$, that is they should be in each other's resp. $O$-class. That same class now also includes $10^{100} n^2 + 2^{100}$, though.

If you want to learn more about issues with Landau notation and different candidate definitions, I recommend the recent work by Rutanen et al. \[1\]. It's a rather mathematical read.

---

1. A General Definition of the O-Notation for Algorithm Analysis by K. Rutanen et al. (2015)

---
Tags: asymptotics, landau-notation
---


# Question
Title: Single-source shortest path algorithm for graphs representing stacked behavior
I am trying to compute a single-source shortest path in an interprocedural control flow graph (iCFG).

That is a directed, unweighted, cyclic graph with edge labels. Some of these labels represent interprocedural call and return. The impact of these is that they determine which edge must be traversed on a call return.

Is there a shortest path algorithm adapted to this kind of graph?

**Edit** Clarification: suppose that I am able to identify a pair of nodes of interest (n1, n2) in the graph using a plain boring graph traversal, I want to obtain the shortest path between n1 and n2 that respects the constraints of the graph.

# Answer
Yes. You want CFL-reachability.

You put a left-parenthesis on each call edge and a right-parenthesis on each return edge (with a different kind of parenthesis for each function). Then, you look for a path where the sequence of symbols along the edges in the path form matched parentheses.

This is basically the intersection of a context-free language (CFL) with a graph reachability problem (finite state automaton), and as you know, the intersection of a CFL and a regular language is itself a CFL. As a result, there are efficient algorithms for CFL-reachability.

There's also lots of theory and work on algorithms to make this as efficient as possible. You can even find existing tools for this sort of thing.

I'd suggest you start by looking at the following papers:

Thomas Reps. Program Analysis via Graph Reachability. Information and Software Technology, vol 40 no 11-12, Nov/Dec 1998, pp.701--726.

Thomas Reps, Susan Horwitz, Mooly Sagiv. Precise interprocedural dataflow analysis via graph reachability. POPL '95.

Thomas Reps, Stefan Schwoon, Somesh Jha, David Melski. Weighted Pushdown Systems and their Application to Interprocedural Dataflow Analysis. Science of Computing Programming, vol 58 no 1-2, Oct 2005, pp.206--263.

The first two consider only the reachability problem (is there a path from $s$ to $t$?). The third can be used for the shortest paths from (find the shortest path from $s$ to $t$).
> 2 votes

---
Tags: algorithms, graphs, reference-request, shortest-path
---