# Question
Title: Searching for an algorithm with $\Theta(n2^n)$ time complexity
I am searching for an algorithm with a time complexity of $\Theta(n2^n)$ time complexity. I am aware, that e.g. the Fibonacci sequence has a time complexity of $\Theta(2^n)$.

My plan was to add a loop in the implementation, so that before you go into recursion, you are going to count from 1 to $n$. My question is, whether my plan is successful or if I made any mistakes.

# Answer
> 0 votes
If you just want any algorithm with running time $\Theta(n 2^n)$ you can trivially compute $\ell = n 2^n$ from the input size $n$ and then have a loop of no-ops (or any constant number of "useless" elementary operations) iterate $\ell$ times.

If you are looking for a "reasonable" algorithm for a "well-known" problem with that time complexity, you can look for example at the brute-force solution for the subset-sum problem. Given an input collection of $n$ non-negative integers $X=\\{x\_1, x\_2, \dots, x\_n\\}$ and $T \in \mathbb{N}$ the problem asks to decide whether there exists a subset $S$ of $X$ for which $\sum\_{x\_i \in S} x\_i = T$.

A trivial brute-force algorithm for this problem looks at $2^n$ possible binary vectors $v\_1, v\_2, \dots \in \\{0,1\\}^n$ of length $n$, where each vector $v\_i$ represents a subset of $X$. For each $v\_i$ we explicitly check, in $\Theta(n)$ time, whether $(x\_1, \dots, x\_n) \cdot v\_i = T$. After all vectors have been examined, return "yes" if one such vector was found and "no" otherwise.

# Answer
> 0 votes
Here is an algorithm with running time $O(n \cdot 2^n)$:

```
def n2n(n):
    for i in range(n * 2**n):
        pass

```

You can test it with

```
from timeit import timeit
for i in range(20):
    print(i,'\t', round(timeit(lambda : n2n(i), number=1000), 2))

```

which give running times (approximately)

```
0    0.0
1    0.0
2    0.0
3    0.0
4    0.0
5    0.0
6    0.01
7    0.02
8    0.04
9    0.09
10   0.23
11   0.48
12   0.97
13   1.91
14   4.03
15   8.58
16   18.17
17   49.32
18   83.48
19   171.05

```

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


# Question
Title: Big-O when iterations do not correlate with input
Sorry for the perhaps basic question, but my time at university is *long* ago and I need to brush up on Big-O stuff for interviews.

My question is, what would the time complexity be when an algorithm *does* depend on the input but not on the size of the input? For example, assume I have this function:

```
func doSomething(numbers []int) int {
    // find maximum number
    maxNumber := max(numbers)
    for i := 0; i < maxNumber; i++ {
      // magic happens here
    }
}

func maxNumber(numbers []int) (max int) {
     for _,num := range numbers {
           if num > max {
              max = num
            }
     }
     return max
}

```

How would you define the Time-Complexity of `doSomething`? The amount of iterations happens to be the maximum number in the input, so if the input is `[1000000]` we get `1000000` iterations with input size `1`. Yet if the input would be `[1,1,1,1,1,....]` the iteration would still only be `1` even though our input size would be much greater.

Of course the `maxNumber` would be `O(n)` but my understanding is that you would ignore this in the calculation of `doSomething`.

I could say `O(1)` because it's not dependent of the input size, but that seems wrong to me because different input *could* have different iterations.

# Answer
> 1 votes
The time complexity of `doSomething` is $O(\max(n,m))$, where $n$ is the length of the input, and $m$ is the maximum number in the input. The letter $m$ is not standard – you can use a different one if you prefer.

---
Tags: time-complexity
---


title: Minimum cost flow and Ford-Fulkerson

text:
# Question
Title: Minimum cost flow and Ford-Fulkerson
I have a question concerning the use of the Ford-Fulkerson algorithm. Since a minimum cost flow problem is a linear programming problem, it has a dual problem. That dual would be to maximize a certain function. Considering this, is it possible to apply the Ford-Fulkerson algorithm to that dual in order to solve the minimum cost flow problem?

# Answer
> 0 votes
No. Ford-Fulkerson cannot be used to solve arbitrary linear programming instances. It can only solve instances that are in the form of "max flow in this flow graph". The dual doesn't have that form.

The dual is to find the minimum cut. A standard way to find the minimum cut is by finding the max flow, and then using the max-flow min-cut theorem.

---
Tags: network-flow, ford-fulkerson
---


title: speed of preorder traversal

text:
# Question
Title: speed of preorder traversal
I want to know the speed of preorder traversal of an tree. I do not mean its order of magntude which we know is O(n). I want something like 27n operations where an operation is precisely defined. Thanks

# Answer
It's not answerable in the abstract, without a lot more specifics. It depends on intimate specifics of the computer architecture, what counts as "one" operation, how the tree is represented, and many other details that are usually considered a distraction for purposes of analysis of algorithms. And it wouldn't really be useful in practice anyway; these days, the time it takes for an algorithm to complete depends on a lot more than the number of operations. Not all operations take the same amount of time, and more importantly, the memory hierarchy plays a huge role in influencing the running time, and you can't measure its impact by counting operations.
> 1 votes

---
Tags: time-complexity, graph-traversal
---


# Question
Title: Is there any algorithm for 3SAT problem that is fast and relatively easy to implement?
Here is the description for 3SAT satisfiability problem. I already know about the DPLL algorithm, but it's implementation is pretty complex. I would like some algorithm that is relatively simpler but improves the performance by some extent. I would prefer something that is not Tree/Graph based instead bit-mask or multi-bit assignment based approach.

# Answer
If you're determined not to use the standard deterministic algorithm, the usual alternative is what's known as *local search* or *stochastic search*. The basic idea is that you start with a random bit pattern as a variable assignment, observe what's wrong with it in terms of unsatisfied clauses and try to improve it by flipping one or more variable assignments. Observe how this new assignment fails, try to improve it, and repeat.

Local search typically outperforms deterministic search for *satisfiable* random SAT instances, but performs poorly on more structured instances. It also offers no way to prove unsatisfiability unless some proof system is layered atop it.

There are various local search algorithms on offer, from Uwe Schöning's scheme to PPSZ and its variants. None of them outperform DPLL-based solvers on all instances.
> 2 votes

# Answer
I've implemented my own CDCL solver (which is the main modern variant of DPLL), and I found that the hardest part by far was understanding and implementing the 1-UIP heuristic, which in my opinion is well-motivated but not very well-explained in the literature.

If you want to see how fast and simple SAT solvers can be, check out Tinisat. It's only around 500 lines of C++, 20% of which is parsing DIMACS files.
> 2 votes

---
Tags: complexity-theory, dynamic-programming, satisfiability, 3-sat, sat-solvers
---


# Question
Title: "The Annotated Turing" on listing all binary numbers between 0 and 1
In his book "The Annotated Turing" in the first sentence on page 32 Charles Petzold wrote:

> These are binary numbers between 0 and 1, and (judging from the way we created these numbers) all the binary numbers between 0 and 1, and hence all the real numbers between 0 and 1.

And then at the bottom of the page there is a note:

> It may also seem as if we've stumbled on a method to enumerate all the real numbers between 0 and 1...

Followed by a brief explanation of why we really have not.

These two sentences contradict each other. The first one says we've made a list of all real numbers and the bottom note says we have not. So I have to questions regarding this:

1. Is it a mistake or am I getting something wrong?
2. If we have not listed all the real numbers between 0 and 1, then what have we listed?

# Answer
You haven't shown the full proof, but it most likely has the form "Assume that the set is countable. Consider any enumeration. Then (blah-blah-blah) shows that there is a number not in the enumeration. That's a contradiction, so our assumption must have been wrong."

If that's the structure of the proof, then pointing out that the proof appears to say two contradictory things is not a surprise; that's entirely the point of the line of reasoning, to show that if you start with a particular assumption, you reach absurd results.

What's actually true? The truth: that list doesn't actually contain all the real numbers. Assuming that it does is a faulty assumption.

It's possible that the text could have been written a little more carefully to caveat that the statement about it containing all numbers; but oh well, no one's perfect. Books written for a popular audience, in particular, aren't always the best source if you want a precise and careful proof of a mathematical theorem.
> 1 votes

---
Tags: sets, mathematical-foundations, books
---


# Question
Title: Are there things an analog computer can do that digital computing cannot do?
The crux of the difference between analog and digital computing is the number of bits of precision available, right? Now, I know that in the Turing machine, numbers can be stored with any degree of precision since the storage medium is an infinite tape.

But in the real world, physical quantities such as energy or position are not incremented in discrete chunks, as they are in their binary. Instead, their exact values can vary continuously as they do in analog circuits.

On that basis then, are there things which, fundamentally, an analog computer can do that digital computing cannot do?

# Answer
Digital computers are also analog if you get down all the abstraction levels until you reach electrical circuits. The only difference is that we choose to "cut" as with some sort of grid in what levels of detectable analog shifts in signal we create another new abstraction level that we call a bit or a byte.

Anything an analog computer computes, like for example the output signal of an analog filter or the amount of millimeters that a mass in a spring and damper system moves, will also eventually reach a maximum resolution. This is because of for example noise in detectors, error in measuring equipment, and maybe quantum phenomena though I'm not so sure as how that would work. If you define a bit as that very small quantum of information you'll get a digital abstraction for the output of your analog computer.

In other words, if you use a formal abstraction of a digital computer where you can achieve enough resolution for your computations, you'll be able to compute the same than an equivalent real-world analog computer for that problem will compute.

The same problem occurs when digitizing time. For example if you look into analog and digital filter equivalencies, there is always an error that is introduced when digitizing an analog filter. That error tends to 0 as the time step used for the discretizing of the continuous system gets smaller.
> 5 votes

# Answer
In one sense the answer is yes, there are things that analog computers can do that digital computers can't. Hava Siegelmann, for instance, has investigated several classes of abstract analogue machines (in much the same way as TMs are abstract digital machines), known as recurrent neural networks (RNNs) and has shown that certain of those machines can, for example, decide *any* language of bitstrings. This, of course, cannot be said about Turing Machines, so these RNNs are strictly more powerful than TMs. For more information, follow the link and look at her publications.
> 3 votes

# Answer
I know that a turing computer cannot compute everything simply because it uses a countably infinite number of bits. Analog values have an uncountable (or higher infinity-ness) infinity of precision. I would check out both VSauce and ViHart out on YouTube, as they have excellent videos on the subject of infinities.
> 0 votes

---
Tags: computability, computation-models
---


title: Definition of BPP

text:
# Question
Title: Definition of BPP
We know that BPP is described as $\\{L\mid \exists \text{ TM }M, \text{ s.t. }\Pr\[M(x)=L(x)\]\geq2/3\\}$. I saw a proof which uses Chernoff bound to prove that any probability larger than $1/2$ can be turned to any probability in $(1/2,1)$. My question is what about probabilities below $1/2$. Do they fall on a different class?

# Answer
Let $\mathsf{BPP}\_p$ be the class of languages $L$ such that some polytime Turing machine satisfies $\Pr\[M(x) = L(x)\] \geq p$ for all $x$. For any fixed $p \in (1/2,1)$, we have $\mathsf{BPP}\_p = \mathsf{BPP}$. On the other hand:

* $\mathsf{BPP}\_1 = \mathsf{P}$.
* If $p \leq 1/2$ then $\mathsf{BPP}\_p$ consists of all languages. This is because the machine $M$ which flips an unbiased coin satisfies $\Pr\[M(x) = L(x)\] = 1/2 \geq p$ for all $x$.
> 0 votes

---
Tags: complexity-theory, randomized-algorithms
---


# Question
Title: Solve the recurrence $\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $
$$\ T(n) = \sqrt{n} \cdot T(\sqrt{n}) + 1 $$

I've found so many similar questions but I couldn't understand any of the answers explanations. When I try to draw a recurrence tree, I see that each 'level' has as many operations as nodes (because of only $\ 1 $ operation in each node) so in the first level it has $\ 1 $ node then $\ \sqrt{n} $ nodes then $\ \sqrt{\sqrt{n}} $ nodes and so forth to $\ n^{\frac{1}{2^k}} $ on the lowest level on the tree.

I get the same answer when unrolling it:

$\ T(n) = n^\frac{1}{2} T(n^{\frac{1}{2}}) + 1 = n^{\frac{1}{2}}(n^{\frac{1}{4}} T(n^{\frac{1}{4}}) + 1) + 1= n^{\frac{1}{2}} ( n^{\frac{1}{4}}(n^{\frac{1}{8}} T(n^{\frac{1}{8}}) + 1 ) + 1) + 1 = ... $

But it is really inconvenient working with this form.

Also tried using substitution as mentioned here and then applying master theorem but with I can't understand how to make the transition back. Also a similar question here but no further explanations in the answers. I would rather use tree recurrence to solve it but substitution and master theorem also good.

# Answer
Let us assume that $n$ is of the form $2^{2^k}$, and furthermore, a base case of $T(2) = 1$. Applying the substitution method, \begin{align} T(2^{2^k}) &= 1 + 2^{2^{k-1}} T(2^{2^{k-1}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} T(2^{2^{k-2}}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} T(2^{2^{k-3}}) \\ &= \cdots \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} + \cdots + 2^{2^{k-1} + \cdots + 2^0} T(2^{2^0}) \\ &= 1 + 2^{2^{k-1}} + 2^{2^{k-1}+2^{k-2}} + 2^{2^{k-1}+2^{k-2}+2^{k-3}} + \cdots + 2^{2^{k-1} + \cdots + 2^0} \\ &= 2^{2^{k}} \left\[ 2^{-2^k} + 2^{-2^{k-1}} + 2^{-2^{k-2}} + 2^{-2^{k-3}} + \cdots + 2^{-2^0} \right\] \\ &\approx 2^{2^k} \sum\_{\ell=0}^\infty \frac{1}{2^{2^\ell}}. \end{align} The infinite series converges, and we conclude that $T(2^{2^k}) = \Theta(2^{2^{k}})$.
> 2 votes

---
Tags: algorithm-analysis, recurrence-relation
---


title: Argmax in $k$-NN algorithm

text:
# Question
Title: Argmax in $k$-NN algorithm
> Given a query instance $x\_q$ to be classified
>
> * Let $x\_1,\ldots,x\_k$ be $k$ instances which are nearest to $x\_q$ $$ \hat{f}(x\_q) \gets \operatorname\*{argmax}\_{v \in V} \sum\_{i=1}^k \delta(v,f(x\_i)), $$ where $\delta(a,b)=1$ if $a=b$, else $\delta(a,b)=0$ (Kronecker function).

If $f$ is an objective function to be optimized, why is argmax there? Can someone explain how this function gets updated. This is for $k$-nearest neighbor function.

# Answer
> 1 votes
Given a new point $x\_q$, we find the $k$ closest points $x\_1,\ldots,x\_k$. Each one of them is associated with a cluster $f(x\_1),\ldots,f(x\_k)$. We assign $x\_q$ to the most common cluster among $f(x\_1),\ldots,f(x\_k)$. The argmax equation is just a fancy way of expressing this idea: for any cluster $v$, the quantity $\sum\_{i=1}^k \delta(v,f(x\_i))$ is just the number of $x\_i$'s which are assigned to cluster $v$, and the argmax picks up the cluster $v$ maximizing this parameter.

---
Tags: machine-learning
---


# Question
Title: Is (λx.FV(A)) and (λx.FV(B)) β-equivalent?
Does free variables have some meaning in lambda calculus? If I follow this β-reduction

```
(λx.λz.y x) y
    -> (λz.y x){x/y}        (variable FV(y) captured)
    -> ((λz.y x){a/y}){x/y} (rename FV(y) -> FV(a)){
    -> (λz.a x){x/y}
    -> (λz.a y)

```

Here we have FV(y) captured during the β-reduction, so I rename it to FV(a) and continue the reduction. Is this result even valid?

I would rename the y argument instead

```
(λx.λz.y x) y
    -> (λz.y x){x/y}        (variable FV(y) captured)
    -> (λz.y x)({x/y}{y/a}) (rename argument FV(y) -> FV(a)
    -> (λz.y x){x/a}
    -> (λz.y a)

```

If I use De Bruijin index notation for both outputs I would get:

```
(λz.a y) -> (λ.1 2)
(λz.y a) -> (λ.1 2)

```

so they seem β-equivalent for me.

This means that FV has no meaning at all, `FV(a) β= FV(b) β= FV(c) ...`  is my understanding right?

I'm asking because when applying lambda calculus I would like to have some global variables that are not bound by the expression but are bound by the context, things like `*`, `+`, `sqrt`, etc, in this case I cant just replace free variables because they may have a meaning, what would I do so?

---

Thanks @lemontree for your answer, I'm implementing a lambda calcualtor so I need to take care of every single step. I write things in the math notation `(λx.x) y` and then translate to the expected code `Appl(Lamb('x', 'x'), 'y')`, `M[x/y]` `m.replace('x', 'y')`, so having a notation for every step help me a lot :).

I search but can't find any special notation for ɑ-conversion so I came up with `M[BV(x)/y]` to denote that x is not free in `M` and to make it distinct from `M[x/y]`. And a special function `NX` that returns the next available variables. Here is how I reduced your example (thank you!)

```
    (λx.λy.y x) y
        -> (λy.y x)[y/x]
        -> (λy.y[y/x] x[y/x])               CAPTURE ERROR on y (backtrack)
        -> (λy.y x)[BV(y)/NX(x, y)][y/x]    NX(FV ∪ BV) returns the next available variable
        -> (λy.y x)[BV(y)/z][y/x]
        -> (λz.z x)[y/x]
        -> (λz.z[y/x] x[y/x])
        -> (λz.z y)

```

The bits that I missed

* A definition of available variables `not (FV ∪ BV)`. I need this to implement ɑ-conversion
* A formal notation for ɑ-conversion

Is there anything like this in the literature? Thanks in advance :)

# Answer
Free variables have a "meaning" in the sense that two free variables (as opposed to two bound variables) are not $\alpha$-equivalent -- and that's precisely why your first reduction is *not* correct: We are not allowed to do "free renaming", only bound renaming!

Capture avoiding substitution is defined as

> If $x \neq y$ and $y \in FV(N)$ and $x \in FV(P)$, then, where $z \not \in FV(N) \cup FV(P)$: $(\lambda y.P)\[N/x\] = \lambda z.(P\[z/y\]\[N/x\])$

Capture avoiding substitution happens only when a variable occurring free in $N$ is bound by lambda abstraction in the term to substitute ($y \in FV(N)$) and there are actual occurrences of $x$ in $P$ to substitute ($x \neq y$ and $x \in FV(P)$). In that case, we rename the *bound* variable in *the term that undergoes* substitution (the function body), i.e. $(\lambda y.P) \rightsquigarrow \lambda z. (P\[z/y\])$, then perform the actual substitution of $N$ for $x$ in $P'$. **We do not rename free variables, and we do not perform renaming in the argument**.

In your example, beta-reducing $(λx.λz.y x) y$ means to replace every free occurrence of $x$ in $\lambda z. yx$ by $y$ provided that $y$ is free to substitute. **y will not be captured by anything**: As you observe, $y$ is free in $\lambda z.yx$, and that's precisely why there is no capturing and thus no capture avoiding to perform, and the substitution can be done directly. Thus the correct reduction is

> $\newcommand{\bred}{\triangleright\_\beta} \phantom{\triangleright\_\beta} (\lambda x. \lambda z. yx)y\\ \bred (\lambda z.yx)\[y/x\]\\ = \lambda z. (yx\[y/x\])\\ = \lambda z. (y\[y/x\])(x\[y/x\])\\ = \lambda z. yy$

De Bruijn indexing on this term is vacuous, because there are no pairs of binding and bound variables ($\lambda z$ does not bind any occurrences of $z$, and the two occurrences of $y$ are not bound by any abstraction $\lambda y$).

---

A case where capture avoiding substitution would be needed is if the argument $y$ were bound in the function body, e.g. if instead of the vacuous abstraction $\lambda z$ there were $\lambda y$:

> $(\lambda x. \lambda y. yx)y\\ \bred (\lambda y.yx)\[y/x\]\\ = \lambda z. (yx\[z/y\]\[y/x\]) \quad \text{(avoiding catpure of $y$)}\\ = \lambda z. (zx\[y/x\])\\ = \lambda z. zy$

---

Re. notation and implementation:

It depends a bit on how you define it, but the way I used it above (which is the approach chosen in e.g. Hindley & Seldin (see below):
When bound renaming has to happen to avoid variable capture, then this is part of the definition of substitution, i.e. the result of $(\lambda y.P)\[N/x\]$ with $y$ free in $N$ syntactically identical ("$=$", rather than just $\alpha$-equivalent) to $\lambda z.P\[z/y\]\[N/x\]$.
To express $\alpha$-equivalence in the sense that a pair of terms only differs in their bound variable names, you can write $\equiv\_\alpha$.
Alternatively, one could define beta reduction such that substitution can only be performed if no variable conflict occurs, and if it does, one has to prepend a step of $\alpha$-renaming before $\beta$-reducing.

"not $FV(A) \cup FV(B)$" is just the set-theoretic complement relative to the set of all variables, $VAR - (FV(A) \cup FV(B))$. To implement a choice of "the first variable not in $FV(A) \cup FV(B)$" you need to presuppose an ordering of variables such as $x \< y \< z \< x\_1 \< ... x\_n$ and then do something like $min\\{x: x \in VAR \land x \not \in FV(A) \land x \not \in FV(B)\\}$. The set of free and bound variables is defined by straightforward recursion on the structure of the lambda term.

Furthermore, for a precise notation in the implementation one may want to distinguish between an atomic beta reduction/variable renaming step vs. reducibility/equivalence through a chain of reductions/renamings, as well as $\beta$-reducibility monotonously downwards from $A$ to $B$ as opposed to $\beta$-equivalence by finding a common term both reduce to.

For variables you should use $x, y, z, u, v, w, x\_1, x\_2, \ldots$; wheras $a, b, c, \ldots$ are more typically understood as constants.
Constants is also what objects and functions interpreted "by context" such as $\*, +, sqrt$ would naturally be treated as; their meaning is "fixed from the outside" and you can combine lambda reduction with custom inference steps like $(\lambda x.+xx)(2) \bred +22 =\_\mathbb{N} 4$.

You can find the notation I used and all the definitions necessary for rigorously implementing substitution etc. in (amongst others)

J. R. Hindley & J.P. Seldin (2008), *Lambda calculus and combinators: an introduction*.

Another classic is

H. Barendregt (1992), *Lambda calculi with types*.
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: What is complexity class for #XOR-2-SAT?
I know that given problem is in $\mathsf{FP}$: if given formula is satisfiable, then it is only needed to find out how many connected components equality (undirected) graph has. In fact problem is to count the amount of connected components.

However, is it possible to solve it using only log space? Is then the given problem is $\mathsf{FL}$-complete? Or, maybe, this problem is complete somewhere in $\mathsf{AC}$?

# Answer
The given problem is in $\mathsf {FL}$:

1. Solve if it is satisfiable. Let the result be number $s$. Can be done in logarithmic space.
2. Set $t=0$.
3. Count the number of clauses of form $(a\oplus \overline a)$ where $a$ does not appear in any other clause except clauses identical to that one. For each such clause increase $t$ by $1$.

Step 3 can be performed in log space as follows:

```
for every i in V:
    flagIndependent = true
    flagAppears = false
    for every j in C:
        if C_j isIdentical(`(x_i xor not(x_i))`):
            flagAppears = true
        elseif C_j contains(`x_i`):
            flagIndependent = false
    t += flagAppears * flagIndependent

```

Two variables `i` and `j` take space $\log(|V|)$ and $\log(|C|)$ respectively. Variables `flagIndependent` and `flagAppears` take $1$ bit each. Functions checking clauses also require $O(\log(n))$ space at most. Therefore the total space used is logarithmic.

The answer is $s2^t$.
> 1 votes

---
Tags: complexity-theory, graphs, satisfiability
---


title: Runtime Analysis: What grows faster?

text:
# Question
Title: Runtime Analysis: What grows faster?
I was wondering which runtime is a tight upper bound for $f(n,m)= n^2 + 1/2^k$ with $k = n - m$

Intuitively I thought that $f(n,m)$ is in $O(n^2)$ but the longer I am thinking about this the more I tend to say that $f(n,m)$ is in $O(2^k)$.

Can anyone help me?

# Answer
> 0 votes
Since $k=n-m \ge 0$ you have that $n^2 \< f(n,m) \le n^2 + (1/2)^0 = n^2+1$, showing that $f(n,m) \in \Theta(n^2)$.

---
Tags: time-complexity
---


# Question
Title: How to check if a language is not regular?
I have the given regular language and i am suppose to check if it is **regular** and if it is, to provide a regular expression

However, if the language is not regular i have to prove using the "**Pumping Lemma**" that it is not regular

* it is regular if, it can be represented by a finite state automata (FSA)
* or, if it can be represented by a regular expression

```
L = { a^2 b^n c^m , where n,m >= 0 }  Alphabet is {a,b,c}

```

My thoughts:

At first glance, i thought this language is regular because it can be represented by a regular expression. The regular expression that i would propose would be `a^2 b^* c^*`, is this correct?

# Answer
> 0 votes
Yes your answer is correct.

Language L generates strings that begin with 2as followed by any number of bs then followed by any number of cs

Your regular expression represents L correctly

It is also worth reminding how the pumping lemma works , if a string in a language L cannot be pumped , then L is non-regular , however some languages can still fool the pumping lemma

Consider the language F = {a^i b^j c^k| i,j,k ≥ 0 and if i = 1 then j = k}. Which appears as a regular language in pumping lemma but is actually non-regular

This is why there are other methods to prove that a language is non-regular

For example to prove F is non-regular you should remember that regular languages are closed under complement (if F is regular then F' is regular too ) , then by the pumping lemma you can show that F' is non-regular and thus F is non-regular , sometimes closure under intersection is useful too

Finally you should try to get an intuition on the language , clearly L needs only finite memory to check the number of as , there can be any number of bs and cs and the FA does not need to remember the number of bs and cs , an intuition is a good first step .

---
Tags: regular-languages, regular-expressions, pumping-lemma
---


# Question
Title: If is true f(n) = Θ(g(n)) and if f(n) = o(h(n)) then g(n) = o(h(n))?
In asymptotic notation the transivity holds, however what happens when we have small o such as if f(n)= o(h(n)) does that means that also g(n)=o(h(n)) holds?

i take as granted that both of f(n)=o(h(n)) is true and f(n)= O(g(n)) (from THETA) then i need to show g(n) \< c h(n) given that i have f(n) \<= d g(n) and f(n) \< c h(n) how one would proceed from there?

# Answer
> 0 votes
From $f(n) = \Theta(g(n))$ you know that, for some positive constants $c \in \mathbb{R}^+$ and $\eta \in \mathbb{N}$, and for all $n \ge \eta$, it holds that $f(n) \ge c g(n)$, i.e., $g(n) \le \frac{1}{c} f(n)$.$^1$

Moreover, from $f(n) = o(h(n))$, you know that for *any* constant $c' \> 0$ there is some $\eta'\_{c'}$ such that $f(n) \le c' h(n)$ for any $n \ge \eta'\_{c'}$.

Pick any constant $c'' \> 0$ and let $\eta'' = \max\\{\eta, \eta'\_{c'}\\}$ where $c' = c \cdot c'' \> 0$. From the previous inequalities we have that, for any $n \ge \eta''$: $$ g(n) \le \frac{1}{c} f(n) \le \frac{1}{c} \cdot c' h(n) = c'' h(n), $$ thus proving that $g(n) = o(h(n))$.

---

$^1$: In fact, the weaker condition $f(n) = \Omega(g(n))$ suffices.

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


# Question
Title: how to prove that a language is regular?
I know that this language is not regular L = {w | na(w) = nb(w)} where na(w) is the number of a's in w. But what if now the language changes to that the number of a's has to be greater than b's? I think not, because we do not have finite number of prefix equivalence class. And in that case, how can I prove it? Or if it was regular, how would it be?

# Answer
Both mentioned languages are irregular

This can be easily shown for both languages using the pumping lemma

First consider L = {w | w has more as than bs} Let p be the pumping length then clearly b^p a^(p+1) is in L and it cannot be pumped

We know that |xy| ≤ p ,and thus x and y will have only bs , then pumping the string for i \> 1 , xy^i z will give you a string with bs equal to (for i=2) or more than ( for i \>2) as, since this string cannot be pumped L is irregular

In a similar manner the language with the number of as equal to bs can be shown to be non-regular , consider a^p b^p clearly it has equal number of as and bs , using the same argument as above x and y will have only as and thus pumping the string gives more as than bs and thus this language is also non-regular

Intuitively we know both are irregular since we need to keep count of the number of as and bs to compare them something , and the number of as and bs is not a finite specified number .
> 0 votes

---
Tags: regular-languages, regular-expressions
---


# Question
Title: Need help understanding what co-recursively enumerable means
Lets say I have a set: $ L = \\{\langle G \rangle | L(G) = \Sigma^{\star}\\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not halt on inputs in L.

So in this case would something "not in L" be nothing?

# Answer
> 0 votes
If you by co-CE mean co-Computably Enumerable, then they are the same.

The field called Recursion Theory is also known as Computation Theory.

You find the same analogy in the classes. *Recursive* is a different way of calling *Computable*. A *recursively enumerable* set is a different way of calling *computably enumerable* set.

# Answer
> 0 votes
> So in this case would something "not in L" be nothing?

No. A string $\langle G\rangle$ is not in $L$ means $L(G)\ne \Sigma^\*$. Such strings exist of course. For example, if $G$ is a machine that rejects anything, then $L(G)=\emptyset$, thus $\langle G\rangle\notin L$.

# Answer
> 0 votes
A language is said to be co-Turing-Recognisable or co-Recursively Enumerable if it is the complement of a Turing recognisable Language.

We can show that if a language L is Turing recognisable and it is co-Turing-Recognisable meaning that it's complement is also Turing recognisable then this language is decidable (this may be useful to use as a contradiction ).

So the question is asking you, is the complement of language $L$, say $L'$, Turing recognisable or not?

$L' = \\{\langle G\rangle \mid L(G) \neq \Sigma^\*\\}$ is turing recognisable. How do we know that?

We can construct a TM M to recognise L' ,

M on input \< G\>:

Construct PDA P from \< G\>

Generate all strings x in Σ\* in lexicographical order

Run x on P

If P rejects any string x accept

If some string x is not accepted by P , then it cannot be generated by G , thus G ≠ Σ\* and hence we accept

So , if G ≠ Σ\* then we eventually reach a string x not generated by G and eventually accept G , if G = Σ\* then we loop

Clearly M recognises L' and hence L' is Turing recognisable , since the complement of L is Turing recognisable , then L is co-turing-recognisable

We can extend this further by proving that L is not Turing recognisable , we know that L' is Turing recognisable , we also know that L is undecidable , if we assume that L is Turing recognisable , then both L and L' are Turing recognisable and hence L is decidable , which is a contradiction , thus L is non-turing recognisable

Note: the terms "Turing recognisable" and "recursively Enumerable" are interchangable.

---
Tags: formal-languages, context-free, semi-decidability
---


# Question
Title: If there is no Hamiltonian path in a DAG then there are at least two different Topological sorts
I understand the concept that if there is no Hamiltonian path so there will be 2 smaller paths and with them I can build more then one topological sort but I am not sure how make it formal.

Can you help me to structure the proof?

# Answer
Let's call two vertices $u$ and $v$ comparable if there is an oriented path from $u$ to $v$ or from $v$ to $u$, and call them incomparable otherwise. Now let's prove that if there is no Hamiltonian path in DAG then there exist two incomparable vertices. Let's use a proof by contradiction and prove instead that if all vertices in a given DAG are pairwise comparable then there exists a Hamiltonian path. Let's prove it by induction by a number of vertices. Obviously, this statement is true for $1$ and $2$ vertex DAGs. Not let's consider an arbitrary DAG where all vertices are pairwise comparable. There is exactly one vertex with zero in-degree in such graph. Let's call this zero in-degree vertex $a$. What is more, if you remove vertex $a$ from your DAG, the remaining subgraph will also be a DAG where every two vertices are comparable. By induction assumption you can build a Hamiltonian path $P$ in this subgraph. Let's call the first vertex of this Hamiltonian path $v$. Then there is an edge $(a, v)$ in the original DAG. Indeed, let's assume that such edge does not exist. But we know that there is a path from $a$ to $v$ (because they are comparable and there is no in-edges to $a$). Let $b$ be the second vertex of the path from $a$ to $v$. Then there is a path from $b$ to $v$, but there is also a path from $v$ to $b$ (by construction of $v$). Hence, there is a cycle in a considered graph. Contradiction. So there is an edge $(a, v)$ and $v$ is a start vertex of some Hamiltonian path $P$ in the subgraph without $a$. Thus $\\{a\\} \cup P$ is a Hamiltionian path in the original graph.

So in every DAG without a Hamiltonian path there is at least 2 incomparable vertices. Thus you can get two different topological sortings just by swapping the numerations on dfs subtrees of these two vertices.
> 2 votes

---
Tags: sorting, dag, hamiltonian-path
---


# Question
Title: Is the language of words having same number of a's and b's context-free?
I'm trying to use the pumping lemma, to show that the language $$L = \\{w \in \\{a, b\\}^+: na(w) = nb(w)\\}$$ is not context free, where $na(w)$ is the number of $a$'s in $w$ and $nb(w)$ is the number of $b$'s in $w$.

I have this: By contradiction, if $L$ is context free, we use the pumping lemma, then let $N$, and $w = a^{floor(N/2)}\*b^{floor(N / 2)}$, with $|w| = N$. Then if we divide $w = uvxyz$, with $v \not = \epsilon$ and $x = \epsilon$, we see that when repeating v there appear more a's than b's, then $uv ^ kxy ^ kz$ $\notin$ L. Contradiction.

Is this right or am I missing something?

# Answer
This language L = { w | w has equal number of as and bs and w≠ ε (since you put a +) } is a CFL

A PDA would work as follows :

On reading a :

If the stack is empty or the top of the stack is a push a

If the top of stack is b pop b push nothing

On reading b :

If the stack is empty or the top of the stack is b push b

If the top of stack is a pop a push nothing

At the end of input if stack is empty accept else reject
> 2 votes

---
Tags: regular-languages, context-free, pumping-lemma
---


# Question
Title: Undecidability of closure under reverse of language accepted by TM
> Prove that the following problem is undecidable using a reduction: Given a Turing machine $S$, does $S$ accept a word $w$ iff it accepts its reverse $w^R$?

There is a solution here, which I don't understand. We reduce from the halting problem. Given a Turing machine $M$ and a word $w$, we construct a Turing machine $M\_1$:

```
M1(x) =
   simulate M on w
   if M accepts w
      if x = 01
         accept

```

The machine $M\_1$ accepts only 01 and all other strings will be rejected. Then

```
MA(<M>, w) =
   Construct M1 as above
   if ML accepts <M1>
      reject
   else if ML rejects <M1>
      accept

```

so the Turing machine $S$ will accept *all* strings except $w=01$.

Why is the string 01 the only string which is accepted by $M\_1$? Why it cannot be 10 instead of 01, for example? It doesn't make sense to me.

If $w$ were 01 and $L$ would also contain 10 and 01, then it should also be accepted, no?

Would anyone please explain me the whole process and especially the Turing machine $M\_1$? Why does this work?

# Answer
> 0 votes
Ok , first consider this clearer proof which takes a similar approach :

Assume S is decidable , we show a reduction ATM ≤m S , obtaining a contradiction

We map \<M,w\> to \<M'\> such that :

M' = " on input x :

If x = 01 accept ,

If x = 10 reject ,

If x = 10 simulate M on w , if M accepts w accept , if M halts and rejects w then reject

Now , if M accepts w , meaning \<M,w\> ∈ ATM , then the L(M') would be = {01 (which is always accepted) , 10 (which is only accepted if M accepts w) } and thus \<M'\> ∈ S

If M rejects w or loops on w , meaning \<M,w\> does not belong to ATM , then L(M') = {01} and thus \<M'\> does not belong to S , completing our reduction , and thus if S is decidable ATM is decidable which is a contradiction , thus S is undecidable

The point is to construct M' such that it accepts a string and it's reverse if M accepts w so that also S accepts M' or accept a single string if M rejects w so S rejects M' since M' doesn't also accept the reverse of the string

You could have used any 2 different strings as long as one is the reverse of the other , instead of 01,10 feel free to use 110,011 hopefully you get the point

Following the link the reduction is from ATM , the only difference is that if M accepts w , then L(M') is ∅ so S accepts M' and if M rejects w or loops on w L(M) = {01 (which could have been chosen to be any string) } and thus M' does not belong to S

Finally it's worth reminding that ATM is the language where M accepts w , while Halting is the language where M halts on w , you may find it a good exercise to try showing a reduction from Halting to S , the proof would be very similar

---
Tags: turing-machines, reductions, undecidability
---


# Question
Title: Calculating the pipeline speed up in case we have an infinite amount of stages
I have the following question:

> We begin with a computer implemented in single-cycle implementation. When the stages are split by functionality, the stages do not require exactly the same amount of time. The original machine had a clock cycle time of 7 ns. After the stages were split, the measured times were IF, 1 ns; ID, 1.5 ns; EX, 1 ns; MEM, 2 ns; and WB, 1.5 ns. The pipeline register delay is 0.1 ns.
>
> If the pipelined machine had an infinite number of stages, what would its speedup be over the single-cycle machine?

I have no idea how to approach this question, any help or hints would be appreciated.

I thought that I might be able to use (time per instruction without pipeline)/(number of stages) since the stages will all have 2.1 ns reserved but it obviously seems 0 which seemed odd to me.

# Answer
The cycle time/clock period is equal to the time doing actual work plus the overhead (represented, simplistically, as "pipeline register delay" in this problem). The time doing actual work can be approximated as the total time doing actual work divided by the number of stages, so the limit of time doing actual work as the number of stages approaches infinity would be zero. (Pipeline stage imbalance does not matter with infinitesimally short work times.) The clock period can, therefore, be reduced to the pipeline register delay (0.1 ns).

Of course, a *slightly* more realistic perspective would recognize that work time is quantized (e.g., the time for one level of transistor switching).

This pipeline speed up also only applies to the clock period/frequency not performance. (Also, an infinite pipeline would never complete the first instruction — unless perhaps one had a higher order infinity of time, as pipeline depth would presumably be countably infinite like the integers.☺)

Presumably the problem is only trying to make the student realize that pipeline overhead is a fundamental limit to clock period.
> 2 votes

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: linear time nash equilibirum aproximations for two player zero sum games
I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. Given that I have 10s of thousands of entries I can't apply even an $O(n^2)$ algorithm or the result will take too long so I need a linear time algorithm. I've found this note which details an exceedingly simple $\frac{1}{2}$-approximation algorithm that works for any game, not just a zero sum game. It also does so by only looking at $O(\sqrt{N})$ entries in the table which is *even* faster than what I need.

Zero sum games can have their exact equilibrium computed in polynomial time via linear programming but this is too slow.

What I'm looking for is something in between; Something that uses more computational resources than the simple 1/2-aproximation algorithm but gives a better approximation; Something that uses fewer computational resources than linear programming but only gives an approximate answer. Does a linear time approximation algorithm exist for 2-player zero-sum games that is better than $\frac{1}{2}$-approximation?

# Answer
> 1 votes
By choosing a different framework of thought that does not attempt to ensure a specific bound we can do well in practice using an algorithm called regret matching.. The paper introducing this is called "A Simple Adaptive Procedure Leading to Correlated Equilibrium" by Sergui Hart and Mas-Colell .

Regret matching is ensured to almost certainly converge to a nash equilibrium for a zero sum gum. There does not seem to be a ton of literature on the convergence rate but in practice it seems that for small matrices it converges close to the equilibrium in a matter of thousands of iterations. Additionally there are many strategies for speeding up convergence that sacrifice guaranteed convergence such as shareholding, or incorporating negative regret along with some normalization procedure. Regret matching has the extreme benefit of being exceedingly simple as well.

Regret matching is the basis for counter-factual regret minimization which is the technique behind state of the art poker AIs.

---
Tags: reference-request, approximation, linear-programming, game-theory
---


# Question
Title: The difference between $\beta$-reduction and $let$
These are the reduction rules associated with $\beta$ reduction and $let$:

$$(\lambda x. e\_2) e\_1 \to\_{\beta} e\_2 \[e\_1 / x\]$$ $$let \\,x = e\_1 \textit{ in }e\_2 \to e\_2 \[e\_1/x\]$$

These reduction rules are very similar.

What is the point of having $let$ as well as $\beta$-reduction?

I can't see why it is of any use.

# Answer
> 3 votes
In the untyped lambda calculus, $\mathsf{let}$ is indeed useless, and most presentations leave it out. But in many typed lambda calculi, $\mathsf{let}$ is useful because it has a more general typing rule.

The best known example is the Hindley-Milner type system, which derives its power from let-polymorphism. In $(\lambda x.e\_1) \\: e\_2$, the expression $e\_1$ has one particular type, which is also the type of $x$ when typing $e\_1$. But in $\mathsf{let} \\: x = e\_1 \\: \mathsf{in} \\: e\_2$, $e\_1$ can be polymorphic, and the instances of $x$ in $e\_1$ can have different specializations of this polymorphic type.

---
Tags: lambda-calculus
---


# Question
Title: How is the optimal number of hashes is derived in bloom filter?
As mentioned in several resources such as Wikipedia the optimal number of hash functions for a bloom filter is known to be $$k=\frac{m}{n} \ln 2$$ but how is this number derived? It seems that it's the number that minimizes the false positive rate which is equal to $$(1-(1-\frac{1}{m})^{kn})^k$$ Can anybody explain the steps to find the argmin of the FP rate?

# Answer
We want to find the value of $k$ that minimizes the function $$ f(k) = \left(1 - \left(1 - \frac{1}{m}\right)^{kn}\right)^k. $$ When $m$ is large, $1 - 1/m \approx e^{-m}$, and so $$ f(k) \approx \left(1 - e^{-kn/m}\right)^k. $$ The logarithm of this is $$ \log f(k) \approx k \log(1-e^{-kn/m}). $$ The derivative of this approximation is $$ \log(1 - e^{-kn/m}) + k \frac{\frac{n}{m}e^{-kn/m}}{1-e^{-kn/m}} = \log(1 - e^{-kn/m}) + \frac{kn}{m} \frac{e^{-kn/m}}{1-e^{-kn/m}}. $$ Let $x = e^{-kn/m} \in (0,1)$. The derivative is thus $$ \log (1-x) - \log x \frac{x}{1-x} = \frac{(1-x)\log(1-x)-x\log x}{1-x}. $$ It is not hard to check that the numerator is positive for $x\<1/2$, zero at $x=1/2$, and negative for $x\>1/2$. This means that when $k \< \frac{m}{n}\log 2$, the approximation to $f(k)$ is decreasing, and when $k \> \frac{m}{n}\log 2$, it is increasing. It thus reaches a minimum when $k = \frac{m}{n} \log 2$.
> 2 votes

---
Tags: bloom-filters
---


# Question
Title: Conversion of nfa with self-loop to one without self-loop
For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent NFA that does not have any self-loop. How can we prove this statement in a general basis without the use of examples?

# Answer
Since you are looking for a solution without $\epsilon$-transitions you can simply do this: create a NFA in which every original state $q$ two copies $(q, 0)$ and $(q, 1)$.

If a state was final then both its copies are final. If $q\_0$ was the initial state, then $(q\_0, 0)$ is the new initial state. Create the transition function as follows: if there was a transition $q \to^a q'$, then add the two new transitions $(q, 0) \to^a (q', 1)$ and $(q, 1) \to^a (q', 0)$.

It is easy to see that his NFA is equivalent to the initial one. You have essentially created a DFA which is a bipartite graph, and each transition changes the side of the bipartition the current state is in.
> 1 votes

# Answer
Add a new state and make the self loop point to the new state and add a empty transition from the new state back to the original state.

It is straightforward to prove that this NFA is equivalent to the original.
> 0 votes

# Answer
Say that a state $q$ has a self loop on symbol $\alpha$, create a new state $q'$ and remove the self loop from $q$.

Then

1. let $q$ and $q'$ have the same transitions,
2. if in $q$ on reading $\alpha$ go to $q'$, if in $q'$ on reading $\alpha$ go to $q$,
3. if $q$ is an accept state let $q'$ be also an accept state.

If we are in $q$ and we read $\alpha$ we go to $q'$, if we are in $q'$ and we read $\alpha$ we go to $q$ so point 2 replaces the self loop. If we are in $q$ or $q'$ and we read any symbol we go to the same state since both have the same transitions that is what point 1 does, and if $q$ is accepting then so is $q'$.

Formally :

For a state $q$ with a self loop on symbol $\alpha$:

Create a new state $q'$.

Remove $\delta(q,\alpha) = q$

Then for each transition $\delta(q,\upsilon) = s$, where $s \in Q$, and $\upsilon\in\Sigma$, add transition $\delta(q'\upsilon) = s$.

Add transitions $\delta(q,\alpha) = q'$ and $\delta(q',\alpha) = q$.

If $q \in F$, where $F$ is the set of accept states, then let $q' \in F$.
> 0 votes

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


# Question
Title: What does it mean for a grammar to be LR(0)?
I am unsure what it means for a grammar to be $X$. More specifically, what it means for a grammar to be LR(0).

For part of an assignment I had to form the DFA for a grammar, which I had no issues with. And then I have been asked whether the grammar is LR(0). My guess is yes, but not because I understand *exactly* what it means. I would assume it isn't if, when creating the DFA I came across some strange behaviors that prevented the DFA making any sense (if you know what I mean/if *I'm* making any sense).

# Answer
A bottom-up parsing technique, used for parsing most context-free grammars is `LR(k)`: `L` indicates that the input is parsed from left to right, `R` indicates that in the parsing process a rightmost derivation is produced; the number `k` indicates how many lookahead symbols are used.

An LR parsing scheme consists of: input, output, stack, a parsing program and a parsing table divided into two parts (actions (shift, reduce) and goto).

The idea is that the parsing program reads characters from an input buffer one at a time and uses the stack to store strings of the form s0X1s1X2s2...smXm where s0 is the initial state, the only one present at the beginning of the computation on the stack, while sm is the state at the top of the stack. Each Xi is a grammatical symbol while each si is a symbol that identifies a state. Each state describes the information contained in the stack before it; the combination of the state at the top of the stack and the current input symbol is used to index the parsing table and to determine the parser's shift-reduce decisions.

Given a grammar, to prove that this is `LR(0)` builds the DFA of viable prefixes. The first prefix is always `S' -> .S` because we consider the grammar increased. Then follow the rules to build the LR(0) parsing table.

A grammar is LR(0) if each position in the parsing table LR(0) contains at most one element.

Furthermore, the LR(0) languages all enjoy the `prefix property`. So if a language does not have this property, we can immediately say that it is not LR(0).

If the grammar is ambiguous then it cannot be LR(k) for any k.
> 10 votes

---
Tags: formal-languages, finite-automata, formal-grammars, compilers
---


# Question
Title: Existence of boolean function with exponential average case hardness
Show that for every large enough $n$, there is a boolean function $f\colon \\{0,1\\}^n\longrightarrow\\{0,1\\}$, whose average case hardness is exponential. The question is taken from Arora Barak Computational Complexity textbook, Chapter-16, Ex-3.

Average case hardness of a boolean function $f$ is defined as, the largest $S(n)$ s.t. for all circuit $C\_n\in \operatorname{Size}(S(n))$, $\Pr\_{x\in U\_n}\[C\_n(x)=f(x)\]\<1/2+1/S(n)$. Here $U\_n$ is uniform distribution over $\\{0,1\\}^n$. I want to show there are boolean functions having $S(n)$ exponential in $n$. My approach is to pick a random $f$ and show via Chernoff bound, the probability of having such function is $\>0$.

Formally, I am following this approach, I need to show, $\Pr\_{x\in U\_n}\[C\_n(x)=f(x)\]-1/2\<1/2^n$, $S(n)=2^n$ . Take $Y$ another random variable, $Y=1$ iff, $C\_n\[x\]=f\[x\]$ else $0$. I express $\Pr\_{x\in U\_n}\[C\_n(x)=f(x)\]=\frac{1}{2^n}\sum Y\_i$, Now, by Chernoff bound if I can bound the probability $\Pr\[\frac{1}{2^n}\sum Y\_i-1/2\]\>1/2^n$ over $C$, I can take the union bound over all $C$ to show that probability is less than $1$. But, I am not sure if I can replace $\mu$ of Chernoff bound with any constant like $1/2$.

Is my approach correct? Can anyone help with my query? $U\_n$ is uniform distribution.

# Answer
> 1 votes
Let $C$ be a fixed function, and let $f$ be a random function. For $z \in \\{0,1\\}^n$, let $X\_z = 1$ if $C(z) = f(z)$, and $X\_z = -1$ otherwise. Thus $$ 2^{-n} \sum\_z X\_z = \Pr\[C(z) = f(z)\] - \Pr\[C(z) \neq f(z)\] = 2\Pr\[C(z) = f(z)\] - 1. $$ Therefore $\Pr\[C(z) = f(z)\] \geq 1/2+\delta$ iff $2^{-n} \sum\_z X\_z \geq 2\delta$. According to Bernstein's inequality, $$ \Pr\left\[2^{-n} \sum\_z X\_z \geq 2\delta\right\] \leq \exp \left(-\frac{42^n\delta^2}{2(1+2\delta/3)}\right) \leq e^{-2^n\delta^2}. $$ (The true exponent is more like $-2^{n+1}\delta^2$.)

The number of (de Morgan) circuits of size $s$ is at most roughly $e^{2s\log s}$ (according to notes of Trevisan; the bound is not tight). According to the union bound, the probability (over $f$) that *some* circuit $C$ of size $s$ satisfies $\Pr\[C(z) = f(z)\] \geq 1/2+\delta$ is at most $e^{2s\log s} \cdot e^{-2^n\delta^2}$. If $2s\log s \< 2^n\delta^2$ then this probability is less than $1$, and so there exists some function $f$ such that $\Pr\[C(z) = f(z)\] \< 1/2+\delta$ for *all* circuits of size $s$.

You're interested in the setting $\delta = 1/s$. The argument works as long as $2s^3\log s \< 2^n$, and in particular, when $s\approx2^{n/3}$.

---
Tags: circuits, lower-bounds
---


# Question
Title: Generating all the increasing subsequences
Given an array of integers, how can we generate all the increasing subsequnces of length of 4 ?

Example: given this list

```
l = [1, 2, 4, 5, 3, 6]

```

The answer should be :

```
[1, 2, 3, 6]
[1, 2, 4, 5]
[1, 2, 4, 6]
[1, 2, 5, 6]
[1, 4, 5, 6]
[2, 4, 5, 6]

```

I generated this algorithm using python :

```
def verif(x,temp):
    work=[]
    for k in temp:
        if len(k)<4 :
            if k[-1] < x :
                work.append(k+[x])
    return work+[[x]]

temp=[[1]]
for i in range(1,len(l)):
    print(i)
    zeta=verif(l[i],temp)
    for i in zeta:
        if len(i)==4 :
            print(i)
    temp+=zeta
    zeta=[]

```

I want to improve my approach , which is very slow for bigger lists unfortunately , is there another algortihm which works faster ?

# Answer
Here is an algorithm to generate all increasing sequences of length $4$ of the numbers $1,\ldots,n$:

```
for d in {4,...,n}:
  for c in {3,...,d-1}:
    for b in {2,...,c-1}:
      for a in {1,...,b-1}:
        output a,b,c,d

```
> 1 votes

---
Tags: algorithms, dynamic-programming
---


# Question
Title: Lower bound for matrix determinant algorithm
I have the an algorithm for computing a matrix determinant:

$$\ det(A) = \sum\_{i=1}^n (-1)^{i-1} \cdot A\_{i1} \cdot det(A\_{-i,-1})$$

Where $\ A\_{-i,-1} $ is the matrix $\ A $ without the row $\ 1 $ and column $\ i $

Drawing the recurrence tree, I see each level $\ k $ has $\ \frac{(n-1)!}{(n-k)!} $ nodes. So I think the upper bound for this algorithm to be $\ O(n!) $ because the height of the tree is $\ n $ and the row sum of each level is the same as number of nodes. How can I set lower bound using recurrence tree? I've found this answer where the lower bound of such arithmetic operation in a matrix is set to be $\ \Omega(n^3) $ though , can not understand why?

# Answer
> 1 votes
The complexity of your algorithm on $n \times n$ matrices satisfies the recurrence $$ T(n)=nT(n-1) + O(n^3), $$ with a base case of $T(1) = O(1)$. In particular, $T(n) \geq n! T(1)$.

In the other direction, let $S(n) = T(n)/n!$. Then $$ S(n) = S(n-1) + O(n^3/n!), $$ with a base case of $S(1) = O(1)$. Since $\sum\_{n=0}^\infty n^3/n!$ converges, we get $S(n) = O(1)$, and so $T(n) = O(n!)$. (The same argument also proves the lower bound.)

---
Tags: time-complexity, algorithm-analysis
---


# Question
Title: How can I show that this language is context sensitive?
I have this language $L=\\{a^nb^nc^n,n\geq0\\}$, I know this language is not context free, but I don't know how to show that it is context sensitive, do I have to use a PDA?

# Answer
> 4 votes
In the same way that DFAs are the counterparts for regular expressions and PDAs are the counterparts for context free languages , the counterpart for context sensitive languages are LBAs (linear bounded Automaton)

That is to say that a language is context sensitive iff some LBA recognises it

But what are LBAs ?

Hopefully you have an idea about what Turing Machines are , an LBA is basically a Turing machine with limited memory , unlike Turing Machines which can access the entire infinite tape , the LBAs computation is restricted to the part of the tape which contains the input , thus the head can only operate in the part of the tape containing the input (hence bounded) , an Alternative less stricter definition is that only a finite contiguous portion of the tape, whose length is a linear function of the length of the initial input, can be accessed by the read/write head (hence linear) , in this way you can imagine the LBA as having a tape of length kn , where n is size of input and k is a constant associated with the machine

Now can we use an LBA to recognise L ?

Let M be an LBA : M on input w :

1. Read the first symbol make sure it is an a , else reject ( since n≥1 we can't accept the empty string)
2. Read the entire string and make sure it follows the right order as , then bs then cs then ds else reject
3. move the head to the left end of the tape then start crossing an a then a b then a c then a d
4. Repeat 3 till all as are crossed , when crossing symbols if M finds that w fell short of some symbol (ex: all bs are crossed but we need to cross a b) reject
5. after all as are crossed read the entire input if there remain any uncrossed symbols reject
6. else Accept

Clearly M is an LBA that recognises L , thus L is a context sensitive language

Notice how M uses only finite memory , in this example using only the portion of the tape where the input is written is enough to recognise L

---
Tags: formal-languages, regular-languages, formal-grammars, context-sensitive
---


# Question
Title: Classify an algorithm to maximize number of tips used by liquid handlers concurrently
I'm looking for suggestions on algorithms, data structures or at least *problems* (so that I look for solutions in that domain) to consider. I realize that exact solution probably doesn't exist. But the more similar problems/solutions I can find the more ideas they may inspire.

We need to transfer reactants from source vials to target vials where they'll be mixed with other reactants and be a part of chemical reactions.

Settings: a liquid handling robot has up to 8 tips which can aspirate (suck in) & dispense (spit out) liquid from/to multiple vials. They can do this either simultaneously or one-by-one.

Input: list of source vials, list of target vials, mapping between source and target vials as well as volume to be transferred.

Goal: minimize time to transfer. This usually means maximize the amount of time tips work simultaneously. To simplify the problem - lets optimize (meaning group them) only *dispense* operations.

## Example

E.g. we aspirate from **Source** vials and dispense to **Target** vials. In this example we'll use 4 tips:

1. Aspirate all 4 Source vials, then dispense to A1, B1, C1, D1
2. Dispense E1 with 1st tip, then use 1st & 3d tips to dispense to F1, H1, then dispense to G1
3. Use 2nd & 3d tip to dispense to A2, B2 then to C2, D2
4. The rest will be filled by 1 tip at a time.

Here color represents which Target Vial should receive liquid from which Source Vial:

## Additional conditions

* Simultaneous aspiration/dispense is possible only when vials are located in the same column.
* Tips can change the spacing between them. E.g. 1st & 3d tip can either dispense to E1 & H1 or F1 & H1 simultaneously.
* Tips have max volume (1mL). If you need to dispense more - you'll have to return back and aspirate more.
* Volume to be dispensed is different in different locations.
* We could've aspirated with 2 tips from the same vial and then transfer the same substance with these 2+ tips. But for simplicity let's not consider this option.

# Answer
If we focus solely on the dispensing operation, we can formulate this as a Set Cover Problem. Namely, we are given a set of tips that have already aspirated some source liquids and we are asked to minimze the number of dispense operations to fill up a given column of target vials. In this simplified set up, we aren't allowed to go back and aspirate new source liquids and we assume that the target volumes are less than the tip capacities.

To set this up as a Set Cover Problem, we treat each target vial as its own element in the universe. We associate with each configuration of the tips (e.g.: position and tip spacing) a set corresponding to the target vials that may be covered by this configuration, taking into account the aspirated fluids in each tip (i.e.: a target vial is "covered" by a tip configuration, if there is a tip that has aspirated the appropriate fluid and positioned over that vial).
> 1 votes

# Answer
One approach would be to view this as an operations research problem, where you have a scheduling problem with a bunch of constraints. A plausible approach would be to formulate this as an integer linear programming problem (or an instance of SAT), then solve using an off-the-shelf solver.

This reminds a bit of job shop scheduling, where you are minimizing makespan. However, your problem has many additional constraints that I suspect will be difficult to model within that framework, so I doubt it will be a useful framework for approaching your problem.
> 0 votes

---
Tags: optimization, robotics
---


# Question
Title: Equivalene of big O definitions (Limit Definition $\Longleftrightarrow$ Quantifier Definition)
I need to proof, that both definitions of the Big 0 notation are equiavlent, but I am not sure if my proof works both ways of the equivalence.

**Definitions:**
Let f,g be functions.

1. $f(n)\in \mathcal{O}(g)\Longleftrightarrow \exists c\>0\exists n\_0 \forall n\geq n\_0 :f(n)\leq cg(n)$
2. $f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits\_{n\to\infty}\frac{f(n)}{g(n)}\<\infty$

**My proof:**
$f(n)\in \mathcal{O}(g)\Longleftrightarrow \limsup\limits\_{n\to\infty}\frac{f(n)}{g(n)}\<\infty$
$\Longleftrightarrow \exists c\>0 : \limsup\limits\_{n\to\infty}\frac{f(n)}{g(n)}\leq c$
$\Longleftrightarrow \exists c\>0\exists n\_0 \forall n\geq n\_0 : \frac{f(n)}{g(n)}\leq c$
$\Longleftrightarrow \exists c\>0 \exists n\_0 \forall n\geq n\_0 : \frac{f(n)}{cg(n)}\leq 1$
$\Longleftrightarrow \exists c\>0 \exists n\_0 \forall n\geq n\_0 :f(n)\leq cg(n)$
$\Longleftrightarrow f(n)\in \mathcal{O}(g)$

I would like to know, if the conversion is correct or if I made any mistakes. Thanks in advance!

# Answer
This 2 definitions, of course, are not equivalent, when $g$ have $0$ subseuquence i.e. when $\exists n\_k \in \mathbb{N}, n\_{k+1}\>n\_k , k\in \mathbb{N}$ such that $g(n\_k)=0$. In this case, assuming, that $\frac{0}{0}$ have no sense as well as $\frac{a}{0}, a \ne 0$, then $\frac{f(n\_k)}{g(n\_k)}$ is not defined, while definition with quantifiers have no problem.

This is why, imho, first should be taken as base definition and second considered only in appropriate situations and why I count your question important.

If such subsequence does not exist, then your proof is correct.
> 0 votes

---
Tags: landau-notation, big-o-notation, definitions
---


# Question
Title: XOR operation to swap to value without additional variable
I'm breaking my mind to find a good explanation to split two variables with the XOR operation.

The operation is the following:

```
x ^= y # =>                      (x ^ y, y)
y ^= x # => (x ^ y, y ^ x ^ y) = (x ^ y, x)
x ^= y # => (x ^ y ^ x, x)     = (y, x)

```

and my doubt is about the second line, in particular `(x ^ y, y ^ x ^ y) = (x ^ y, x)` how I can have the result `X` from the operation `y ^ x ^ y`?

I know that y^y = 0, but in the previous case I can not say that y^x^y is equal to x.

What I'm losing here?

Source

# Answer
First, xor is commutative and associative, therefore (a xor b) xor c = a xor (b xor c) = a xor (c xor b) = (a xor c) xor b, and in your case that means (x xor y) xor x = (x xor x) xor y = 0 xor y = y.

But this is just a rather pointless programming trick. It only works for integers, it can't be used for floating point numbers, strings, booleans, pointers etc., so it is pointless. It wouldn't pass any code review, so you can't ever use it in real life.
> 2 votes

---
Tags: bit-manipulation
---


# Question
Title: Prove that $ln(n)^r \in o(n^p)$ for $p>0$ and $r\in \mathbb{R}$
I am trying to proof $f\in o(g)$

Let be $r,p\in \mathbb{R}$ with $p\>0$
We have $f(n)=ln^r (n)$ and $g(n)=n^p$

I have already proofed that $ln(n)\in o(n)$ via l'Hospital $\lim\limits\_{n\to \infty}\frac{\frac{1}{x}}{1}=0\Longrightarrow \lim\limits\_{n\to \infty}\frac{ln(n)}{n}=0\Longleftrightarrow ln(n)\in o(n)$

I tried substituting n with ln(n) to recieve $\forall c\>0 \exists n\_0 \forall n\geq n\_0 : ln(ln(n))\leq cln(n)$
Then i tried splitting $c=\frac{a}{b}$ to get $\forall \frac{a}{b}\>0\exists n\_0 \forall n\geq n\_0 : ln(ln(n)) \leq \frac{a}{b}ln(n)$
With this information i said, that $\frac{a}{b}\*\frac{b}{a}\*b\*ln(ln(n))=b\*ln(ln(n))\leq \frac{a}{b}\*\frac{b}{a}\*\frac{a}{b}\*b\*ln(n)=\frac{a}{b}\*b\*ln(n)=a\*ln(n)$
to conclude $ln(n)^b=e^{\frac{a}{b}\*\frac{b}{a}\*b\*ln(ln(n))}\leq e^{\frac{b}{a}\*b\*ln(n)}=e^{b\*ln(n)}=n^a$

At this point i realized a huge problem. I assumed $\frac{a}{b}$ to be positive. But i need it to work for r and p, where only p is known to be postive, which in the other hand means, that r can be negative, what would make $\frac{p}{r}$ negative.

It means that my approach is propably not working a

# Answer
You just need to show that $$ \lim\_{n \to \infty} \frac{\log^r n}{n^p} = 0. $$

This is trivial if $r \le 0$ since $\frac{\log^r n}{n^p} = \frac{1}{n^p \log^{-r} n}$ and $\lim\_{n \to \infty} n^p \log^{-r} n = +\infty$.

For $r\>0$, you can use l'Hôpital's rule $\lceil r \rceil$ times to obtain: $$ \lim\_{n \to \infty} \frac{\log^r n}{n^p} = \lim\_{n \to \infty} \frac{r \log^{r-1} n}{pn^{p}} = \dots = \lim\_{n \to \infty} \frac{\prod\_{i=0}^{\lceil r \rceil-1} (r-i) \cdot \log^{r-\lceil r \rceil} n}{p^{\lceil r \rceil} n^{p}} \\ = \frac{\prod\_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}\cdot \lim\_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}} =0, $$

where $\frac{\prod\_{i=0}^{\lceil r \rceil-1} (r-i)}{p^{\lceil r \rceil}}$ is a positive constant and $ \lim\_{n \to \infty} \frac{ \log^{r-\lceil r \rceil} n}{ n^{p}} $ is equal to $0$ since it falls into the previous case.
> 2 votes

# Answer
Let's consider only $r\>0$. For $\ln(n)^r \in o(n^p),p\>0$ is enough to show $\ln(n) \in o(n^\alpha)$, for $\frac{p}{r}=\alpha\>0$, because $\frac{\ln(n)^r}{n^p} =\left(\frac{\ln(n)}{\sqrt\[r\]{n^p}}\right)^r$ and $r$ power is continuous function. So we come to limit

$$\lim\limits\_{n \to \infty}\frac{\ln(n)}{n^\alpha}=\lim\limits\_{n \to \infty}\frac{\frac{1}{n}}{\alpha n^{\alpha-1}}=\lim\limits\_{n \to \infty}\frac{1}{\alpha n^\alpha}=0$$
> 1 votes

---
Tags: asymptotics, complexity-classes, landau-notation
---


# Question
Title: Proving equivalence of two Turing machines
I have the following Turing machine: A 2R-3L-TM is similar to a standard TM with the change in which the head can only move either 3 cells to the left or 2 cells to the right (those are the only possible moves). and I want to prove equivalence between 2R-3L-TM and standard TMs (one tape and the head can move single cell right or left only). I only want to prove one side, meaning that for every standard TM M\_1, there is a $2R-3L-TM, M\_2, s.t L\left(M\_1\right)=L(M\_2)$. I started the proof on the right side but not sure how to prove the triple left side, my proof so far:

Let M2, a TM with 2R-3L, a set of states Q and transition function \delta. Let us define an equal standard machine, M2. We would do so by describing how TM M1 works in the implementation level:

1. If M1 moves to the right, do the same for M2 however mark the position with ‘ * ‘ transition to a new state at which the machine always moves to the right and then transitions to the original target of the RR transition
2. If M1 moves to the left...

How can I continue my proof and is my proof for the right side correct?

# Answer
> 1 votes
The main idea behind your proof is correct.

Note that (assuming the tape is infinitely sized on the right only) in the operator algebra of tape movements on the right-infinite tape we have identy $xR^kyL^kz = xyz$.

Using that we can prove: $$R = R^4L^3 = (R^2)^2L^3$$ $$L = R^2L^3 $$

And since the right hand side consists only of unit moves in your model, you can do the effective moves on the left hand side. And you already know how, you replace every transition $T(x, S\_i) = (y, S\_o, m)$ where $m \in \\{L,R\\}$ with series

\begin{align} &&T(x, S\_i) &= (y, s\_1(m), m'\_1(m))\\ &\forall z\in \Sigma :\quad &T(z, s\_1(m)) &= (z, s\_2(m), m'\_2(m))\\ &&&\cdots\\ &\forall z\in \Sigma :\quad &T(z, s\_{k-1}(m)) &= (z, S\_o, m'\_k(m)) \end{align}

where $s\_i$ are new temporary states and $m'\_i$ are the appropriate series of moves from $\\{R^2, L^3\\}$.

---
Tags: turing-machines, equality
---


# Question
Title: Depth of any node x in Weighted Quick-Union Algorithm
I know from Sedgewick's book on algorithms that the max depth of any node x from a set of N nodes is at most log2(N) applying the algorithm(which says to put the shorter tree beneath to avoid tall trees) and he gives an understandable proof by induction. The thing is that I have trouble visualising that result apart form the mathematical manipulations, I mean besides proving that that assumption is correct my question is how do you get to that assumption. This are some remarks he makes before the proof:

1)The depth of the node x increases by one when merged to another tree

2)When the depth increases the size of the tree at least doubles.

But here is the thing, he says : "The size of the tree containing x can double at most log2N times" And I don't understand why.

Here is the link to a presentation he gave on the topic. http://algs4.cs.princeton.edu/lectures/15UnionFind-2x2.pdf the proof's sketch is on slide 33.

Thanks :)

# Answer
> 2 votes
If the size of a tree starts at 1 and doubles $i$ times, it will be $2^i$ (at least -- there might be other size increases as well). If $i\>\log\_2N$ this would give a size $\>N$ -- more than the total number of nodes.

# Answer
> 5 votes
Here is my approach to understand, mix of both visualization and mathematics.

In the weighted quick union, when we need to do union for two nodes, we join the roots of those two nodes ( basically the smaller tree joins the bigger tree ).

Lets say these are the two trees :-

```
                            1                    6
                           / \          and     / \
                          4   3                 5  2
                                                    \
                                                     7

```

Now lets say we need to perform union ( 3, 5) the resulting tree will look like this

```
                           6
                          /| \
                         1 5  2
                        / \    \
                       4   3    7

```

Depth of node 3 increased by 1 during this operation but the depth of node 5 remained the same.

This means the depth of a node will only increase if the tree in which it is present joins a bigger tree.

Now whenever a small tree of size x ( no. of nodes in the tree) joins a bigger ( or equal sized ) tree, the size of result tree is at least 2 times x.

Now lets say this doubling of size happens i times, the size of resulting tree will be 2^i. Remember that whenever the size doubled the depth of some of the nodes increased by 1.

What is the maximum size the tree can obtain ?

```
   2^i   <=  n ( no. of nodes in the tree )
   i <= log n ( base 2 log operation )

```

Thus the depth of any node can be increased upto log n, not anymore than that.

Remember all the above logic only applies when a smaller tree joins a larger tree as its branch. Otherwise the **doubling logic** will not apply.

# Answer
> 1 votes
Though it is late to answer this question, just wanted to answer. Here Let the total no. of elements be N. When you union two elements - a and b, you merge the two connected components: one component that contains a, and the other being that contains b. Here at the max you can double the resulting component(when both the components those contains a and b have same size). and Continuing like this - total number of components should be less than the number of time they are merged say i times. Now the maximum number of elements in terms of can be 2^i i.e. N \< (2^i) =\> i \> ln(N) ==\> the maximum depth can be ln(N).

# Answer
> 1 votes
Maybe explaining bottom-up might help to someone, as it did to me:

* Maximum height of a tree only increases when 2 trees with same height are merged.
* You can make maximum logN merges of such trees. (as you will have to keep dividing N with 2 to form i amount of such trees. At the example with N=8 below, you create equally sized trees to merge max 3 times.
* Therefore, depth of any node x is at most LogN. (due to max height)
* As you can see below, that happens first at the merge of (0,1), (0,2) and lastly (0,4).

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


# Question
Title: Permuting integer vectors $x$ and $y$ which add to integer vector $z$
I posted this on mathoverflow but haven't recieved any comments. I wonder if there might be some insight from this community. Thanks!

**The problem**

Suppose you have nonnegative integer vectors of length d, $x$, $y$, $z \in \mathbb{Z^+}^d$. We know that $\sum\_{i=1}^d x\_i + y\_i = \sum\_{i=1}^d z\_i$. I wish to find permutation matrices $\Pi\_1$ and $\Pi\_2$ such that \begin{align} \Pi\_1 x + \Pi\_2 y = z \end{align}

without enumerating all possible permutations. If there is a solution, I'd like to know in as few steps as possible. If the solution is not unique, I'd like to know all permutation pairs which satisfy the above (or have an efficient means of enumerating them)

**More context:**

$x$ and $y$ actually represent integer partitions, and I actually have many $x$'s and many $y$'s for any given $z$, and will have to check all possible $x, y$ pairs for the given $z$.

**Things I've tried:**

1. We can immediately rule out some $x, y$ pairs using majorization. Let $\tilde{x}$ and $\tilde{y}$ be the sorted versions of $x$ and $y$. I can show that $\tilde{x} + \tilde{y}$ majorizes all other permuted sums of $x$ and $y$. If $z$ majorizes $\tilde{x} + \tilde{y}$ (and is not equal to it, modulo permutation), then it majorizes all permuted sums of $x$ and $y$, so there is no solution. Similarly, $\tilde{x} + \text{reverse}(\tilde{y})$ is majorized by all other permuted sums. If $z$ is majorized by $\tilde{x} + \text{reverse}(\tilde{y})$, then it is majorized by all permuted sums and there is no solution. By partially ordering all the $x$'s using majorization and doing the same for $y$, this method potentially knocks out many pairs without having to check them all.
2. We can avoid checking all pairs of permutations by using sorting. Let $\tilde{x}$ be the sorted version of $x$ and let $\widetilde{\Pi}\_x$ be a permutation which sorts $x$, i.e. $\widetilde{\Pi}\_x x = \tilde{x}$. Enumerate all unique permutations of $y$, and subtract them from $z$. Sort each difference vector, and compare it against $\tilde{x}$. Given a match, $\Pi\_1$ and $\Pi\_2$ can be determined by the permutation of $y$ and the permutation which \`\`unsorts'' $\tilde{s}$. Formally, suppose for some permutation $\Pi^\*$, $s = z - \Pi^\* y$ with $\tilde{s} = \tilde{x}$. Then $\Pi\_1 = {\widetilde{\Pi}\_s}^{-1} \widetilde{\Pi}\_x$ and $\Pi\_2 = \Pi^\*$.
3. I've found a reduction of the problem to filling in count matrices with specified row, column, and diagonal margins, but haven't found efficient ways of solving that problem. Please chime in if you have thoughts on this. I can say more about this if relevant.

I realize this question is somewhat algorithmic in nature, but I'm hoping there is some relevant area of mathematics that could help. I've tried to think about this from the perspective of symmetric groups, the elementary basis for symmetric functions, general equivalence classes, but I'm not getting very far. Any help or suggested directions would be appreciated!

# Answer
Your problem is equivalent to numerical 3-dimensional matching and is NP-complete.

It is listed under code SP16 in *Computers and Intractability; A Guide to the Theory of NP-Completeness* by Garey and Johnson.
> 3 votes

---
Tags: algorithms, enumeration
---


# Question
Title: Why do OS locks require hardware support?
I just read the chapter on locks in the book Operating Systems: Three Easy Pieces, and it discusses an implementation of locks (see in Figure 28.9) that involves a test-and-set hardware instruction.

The textbook emphasizes that both hardware support and OS support are necessary to build an efficient locking mechanism. Wikipedia echoes this sentiment:

> Locks typically require hardware support for efficient implementation. This support usually takes the form of one or more atomic instructions such as "test-and-set", "fetch-and-add" or "compare-and-swap". These instructions allow a single process to test if the lock is free, and if free, acquire the lock in a single atomic operation.

I think I've come up with an alternative lock implementation that doesn't require hardware support. It seems to have relatively similar performance overhead, while guaranteeing mutual exclusion, so making this post to find out if I'm missing something.

### Textbook Lock Implementation

I'll first summarize the textbook implementation. For setup, we need to:

1. Maintain a single flag (set to 0 or 1) and a queue (of thread IDs).
2. Maintain a separate flag for a "guard" lock, which will be a simple spin lock. Because the guard lock is meant to protect a relatively small critical section, the performance overhead of a spin lock won't be as pronounced.

When a thread wants to acquire a lock, it will do the following:

1. First, spin with the test-and-set instruction until you acquire the guard lock.
2. Once acquired, check if the flag (of the main lock) is set to 0. If it is, simply set it to 1, and the lock has been acquired! If the flag is set to 1, proceed to step 3.
3. Push the current thread ID onto the queue.
4. "Park" the current thread. This is an instruction in Solaris that basically puts a thread to sleep.

On the other hand, when a thread wants to release a lock, it will do the following:

1. Spin until you acquire the guard lock.
2. If the queue is empty, set the flag to 0, and you're done. If the queue is nonempty, proceed to step 3.
3. Pop a thread ID from the queue, and "unpark" the corresponding thread (wake it up).

### My Implementation (without hardware support)

First, some setup:

1. Every lock must be initialized with some unique lock ID.
2. Inside the OS, maintain a "lock table." For each lock ID, the lock table will maintain a flag (0 or 1) and a queue (of thread IDs).

Then, when you want to acquire the lock:

1. Make a system call (which might be called something like `lock`) and pass in the lock ID as an argument.
2. Enter the OS. Since the OS manages scheduling, we guarantee mutual exclusion for the following steps.
3. Search the lock table for the specified lock ID. If the flag is 0, set it to 1. Then return; the lock has been acquired! If the flag is 1, proceed to step 4.
4. Push the calling thread to a queue.
5. Block the calling thread, so for now, it cannot be scheduled.

To release a lock:

1. Again, make a system call with the lock ID as an argument.
2. Entering the OS (again guaranteeing mutual exclusion), search the lock table for the specified lock ID. If the queue is empty, set the flag to 0, you're done. If not, proceed to step 3.
3. Pop a thread from the queue, and unblock it. It should be scheduled soon.

Note that when we are acquiring a lock, a context switch is not necessary if the lock is available, so the performance overhead should be minimal.

It's likely that I'm missing a small detail that will make me look stupid, but that's why I'm asking this question in the first place.

# Answer
> Since the OS manages scheduling, we guarantee mutual exclusion for the following steps.

But how do you guarantee mutual exclusion inside the OS?

On a single-processor machine¹, you know that only the kernel code that serves the `lock` system call is executing. All other threads are in a known state. However the kernel code can be interrupted at any time by a hardware interrupt. This could be the timer interrupt that tells the kernel that it's supposed to schedule a different thread. You can implement locks just by manipulating the bits in the lock table, but only if interrupt code won't manipulate the lock table. So it's possible to implement a lock this way, but it imposes some design constraints in the kernel.

On a multi-processor machine, all you know is that *this* processor is serving the `lock` system call. The other processors could be manipulating the lock table at the same time. At step 3, you read an entry from the lock table and then possibly write to that entry. Another processor could have read or written the entry between your read and your write². Avoiding this race condition is precisely why processors have instructions such as compare-and-swap that combine a read and a write.

Even on a single-processor machine, making a system call is a heavyweight operation compared to a single instruction such as compare-and-swap. It's no good for high-speed concurrency.

¹ <sub> By single-processor, I mean a machine that executes a single thread at a time. In this context, a machine with a single piece of silicon that contains multiple logical cores is a multi-processor machine. </sub>
² <sub> And in the real world, it can get worse, because processors don't always have a consistent view of memory, so two processors could for example take the same lock independently even if their read/write sequences don't overlap. But even with consistent memory, interlacing read/write sequences spells doom for a naive lock implementation. </sub>
> 5 votes

# Answer
OS locks require hardware support because **every instruction** in the ISA takes **multiple clock cycles** to complete. It has to go through a **instruction execution cycle** having fetch,decode,execute,write... stages (there are processor with \>20 stages). Also most of the processor nowadays are pipe-lined processors. I.e, since hardware for each stage of the instruction execute cycle is different, multiple instruction are put in flight (at different stages) at the same time. This scenario is further complicated by the fact that memory operand for a instruction can be at any place in the memory hierarchy, L1, L2, L3 ... cache or main memory. So the time taken for reading a operand can be large (hundreds of cycles for main memory read).

**Lock is a memory variable**. So modifying it can take multiple cycles (number of stages in instruction execution cycle and where the lock memory variable is). If there is a hardware support (atomic instructions) then, processor will ensure that no other instruction is able to access the **lock memory location** till previous instruction that **requested an access** is completed (goes through all its instruction cycle stages). A atomic instruction ensure that there is **total order** among all the **lock variable modifying instructions**.

Even spin lock function **use atomic instruction** for exclusive access to spin-locks.
> 2 votes

---
Tags: operating-systems, threads
---


# Question
Title: Irregularity of $\{0^x1^y : y \nmid x\}$
The language $L=\\{W\in\\{0,1\\}^{\*} \mid W=0^{x}1^{y} \text{ where } x\geq0, y\>0 \text{ are integers and } y\nmid x\\}$ is not regular.

How would one prove this using Pumping Lemma?

I thought about it for quite a while but couldn't quite figure it out. Lots of number theory is necessary I'd imagine.

# Answer
> 2 votes
Assume that $L$ is regular. Suppose that the pumping constant is $q$, and let $p$ be a prime larger than $q$. Consider the word $w = 0^{p+1}1^p \in L$. According to the pumping lemma, we can write $w = xyz$, where $|xy| \leq q$, $y \neq \epsilon$, and $xy^tz \in L$ for all $t \geq 0$. Let $y = 0^i$, where $1 \leq i \leq q \< p$. Then $$ xy^{t+1}z = 0^{p+1+ti} 1^p. $$ Since $i \in \\{1,\ldots,p-1\\}$ and $p$ is prime, we know that $i$ has an inverse modulo $p$, that is, a number $j \in \\{1,\ldots,p-1\\}$ such that $ij - 1$ is a multiple of $p$, say $ij = ap + 1$ (we prove this below). If we take $t = (p-1)j$ then $$ p+1+ti = p+1+(p-1)ij = p+1+(p-1)(ap+1) = p(a(p-1)+2) $$ is a multiple of $p$, and so $xy^{t+1}z \notin L$, contradicting the pumping lemma.

The existence of $j$ can be proven in many ways. Here is one. Consider the integers $i,2i,3i,\ldots,(p-1)i$. Suppose that you divide them by $p$, obtaining remainders $r\_1,r\_2,\ldots,r\_{p-1}$. Since $p$ is prime and $i \in \\{1,\ldots,p-1\\}$, all these remainders are non-zero. Furthermore, they must be different: if $r\_u = r\_v$ for $1 \leq u \< v \< p-1$ then $vi-ui = (v-u)i$ would be a multiple of $p$, contradicting the primeness of $p$. Therefore one of the remainders $r\_j$ must equal $1$.

# Answer
> 2 votes
Suppose that $L$ is regular. Then so is the language $L' = \\{0^x 1^y : x,y \ge 0 \wedge y \mid x\\}$ obtained as the intersection between the complement of $L$ and $0^\*1^\*$.

Let $n$ be the pumping length of $L'$ and consider the word $w = 0^{n+1} 1^{n+1} \in L'$.

By the pumping lemma, there is some constant $c$ such that $1 \le c \le n$ and, for every non-negative integer $k$, $0^{n-c+1} 0^{kc} 1^{n+1} \in L'$. Pick $k = 0$ to obtain $0^{n-c+1} 1^n \in L'$, which is a contradiction since $(n+1) \not\mid (n-c+1)$.

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: Approximation algorithms for an instance of the Monotone circuit satisfiability
I have the following problem. Given a below boolean formula (of the type explained below) containing $n$ literals and two parameter $k$ and $l$, come up with a satisfying assignment of literals such that no more than $k$ of them are set to true. ($l$ will be explained below.)

An example boolean formula with 4 literals is as follows: $ (x\_1 \lor (x\_2 \land x\_4)) \land (x\_2 \lor (x\_3 \land x\_1)) \land (x\_3 \lor (x\_4 \land x\_1)) \land (x\_4 \lor (x\_3 \land x\_2)) $. Some properties of the kind of formulae I am dealing with:

1. The number of outermost clauses (connected via AND) is same as the number of literals.
2. There is a restriction on size of the innermost AND clauses, they can have at most $l$ literals. For example $l=2$ in the example above.

I did some literature search to realize that this is called as the "Monotone circuit satisfiability" problem in the complexity parameterization literature. My interest in the problem is largely practical, so I am looking for the best approximation algorithm known for the above problem. Any help / suggestions are much appreciated.

# Answer
If this is a practical problem, rather than an approximation algorithm, I suggest using an off-the-shelf SAT solver. There are standard ways to encode the constraint that at most $k$ variables are set to true, using an at-most-$k$-out-of-$n$ constraint. For instance, Z3 has good support for this kind of constraint.

My impression is that approximation algorithms for SAT-like problems tend to perform very poorly.
> 1 votes

---
Tags: complexity-theory, approximation
---


# Question
Title: Help with problem 4.1-1 from CLRS 2nd edition
The exercise says "Show that the solution of $T(n) = T(\lceil{n/2}\rceil) + 1$ is $O(\lg(n))$." I came up with a solution for this exercise using the substitution method but I don't know if it is correct. My solution goes like this: I claim $T(n) \leq c\lg{n}$ and assume it holds for $\lceil{n/2}\rceil$, then $$ \begin{aligned} T(n) &\le c\lg(\lceil{n/2}\rceil) + 1 && \text{Inductive Hypothesis}\\ &= c\lg(n/2) + 1 && \text{Omitting ceiling}\\ &= c\lg{n} - c + 1 && \text{Algebra}\\ &\le c\lg{n} && \text{for $c\ge1$} \end{aligned} $$

I omit the ceiling function according to the text.

I, however, found another solution on the internet that is slightly more complicated which makes me think my solution is probably wrong. It states that $T(n) \leq c\lg(n - b)$ and assumes it holds for $\lceil{n/2}\rceil$, consequently:

$$ \begin{aligned} T(n) &\le c\lg({\lceil{n/2-b}\rceil}) + 1 \\ &\lt c\lg(n/2-b + 1) + 1\\ &= c\lg\big(\frac{n-2b+2}{2}\big) + 1\\ &= c\lg(n-2b+2) - c\lg2 + 1\\ &\le c\lg(n - b) \end{aligned} $$ Where the last inequality requires that $b \ge 2$ and $c \ge 1$.

My question is if my solution is correct, then why subtract $b$ from $n$ in the second solution? If my solution is not correct, is subtracting $b$ from $n$ absolutely necessary and why is my solution not correct?

# Answer
> 1 votes
As pointed out in the comments, your proof is wrong since it is not true in general that $\log \lceil n/2 \rceil \leq \log n/2$. For example, if $n = 1$ then the left-hand side is zero while the right-hand side is negative.

---

In the comment you mention that the text states that they omit floors and ceilings. *This is always wrong.* You cannot "omit" stuff. It invalidates your entire reasoning. (Sometimes, however, you can use true inequalities to get rid of floors or ceilings: for example, $\lfloor x \rfloor \leq x$.)

Consider for example a divide-and-conquer algorithm which splits its input into two halves and performs some $O(n)$ processing. You often see its running time expressed as the recurrence $$ T(n) = 2T(n/2) + O(n). $$ This is clearly wrong – what if $n$ is odd? What does $T(13.5)$ even mean? The argument has to be a positive integer! The real recurrence is probably more like $$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n). $$

When the text states that they omit floors and ceilings, they are being sloppy. They allow themselves to do that since you can solve the true recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$ via the fake one $T(n) = 2T(n/2) + O(n)$, which should be interpreted as defining a function $T(n)$ for *all* positive values of $n$.

You can see this sentiment expressed formally in the Akra–Bazzi theorem, where floors and ceilings don't change the answer. Another way to see it is to consider only values of $n$ of the form $n = 2^m$. For these values, the recurrence $T(n) = 2T(n/2) + O(n)$ does hold. You can prove by induction that the solution to the recurrence $T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n)$, and so it suffices (in this case) to determine the asymptotic rate of growth for $n$ of the form $n = 2^m$.

---

How do you solve your recurrence, $T(n) = T(\lceil n/2 \rceil) + 1$? First of all, you have to supply some base case, say $T(1) = C$. Given $n$, we now construct the following sequence: $n\_0 = n$, $n\_{i+1} = \lceil n\_i/2 \rceil$. You can check that $T(n)$ equals $C$ plus the minimal index $i$ such that $n\_i = 1$.

Since $\lceil m/2 \rceil \leq (m+1)/2$, we know that $n\_1 \leq (n+1)/2$, and so $n\_2 \leq (n+3)/4$, and $n\_3 \leq (n+7)/8$, and so on. More generally, $n\_i \leq (n+2^i-1)/2^i \< n/2^i + 1$. Hence if $i = \lceil \log\_2 n \rceil$ then $n\_i \< n/n + 1 = 2$, implying that $n\_i \leq 1$.

In the other direction, clearly $n\_i \geq n/2^i$, and so if $i = \lceil \log\_2 n \rceil - 1 \< \log\_2 n$ then $n\_i \> 1$, implying that $T(n) \> \lceil \log\_2 n \rceil - 1 + C$.

We conclude that the minimal $i$ such that $n\_i = 1$ is exactly $\lceil \log\_2 n \rceil$. Hence $T(n) = C + \lceil \log\_2 n \rceil$.

---
Tags: algorithms
---


# Question
Title: How do i prove this language is regular?
I have this language {0+1+0+} and i need to prove it is regular,i had the idea to use the closure properties but i can find any regular languages to unify perhaps.Any ideas?

# Answer
Build a finite state machine. Or look up the definition, your definition will either say "there's a finite state machine", or "it's defined by a regular expression".
> 0 votes

---
Tags: regular-languages, finite-automata, closure-properties
---


title: Notation within gaussian function

text:
# Question
Title: Notation within gaussian function
On our lecture slides we have two different notations of the gaussian function.

First it gets introduced as follows: $$p(x\_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\\{-\frac{(x\_n-\mu)^2}{2\sigma^2}\\} \text{ with } \theta=(\mu,\sigma)$$

But later it is used like this: $$\frac{1}{\sqrt{2\pi}\sigma}exp\\{-\frac{||x\_n-\mu||^2}{2\sigma^2}\\}$$

What is the difference between $$(x\_n-\mu)^2$$ and $$||x\_n-\mu||^2$$ or are they equal?

# Answer
> 1 votes
The notation $\\|x\_n - \mu\\|^2$ stands for the squared $L\_2$ norm of the vector $x\_n - \mu$.

The squared $L\_2$ norm of the $d$-dimensional vector $v = \begin{pmatrix} v\_1 & \cdots & v\_d \end{pmatrix}$ is $$\\|v\\|^2 = v\_1^2 + \cdots + v\_d^2. $$ In particular, when $d = 1$, we have $\\|v\\|^2 = v\_1^2$.

The formula you state works for the Gaussian multivariate distribution, when the various variables are independent and have the same variance $\sigma^2$. The formula in the general case is a bit more complicated.

---
Tags: probability-theory, notation
---


# Question
Title: How does random number probabilities work in distributed systems?
Let's say I have a code which does coin toss at 25% win probability.

1. If I run this code n number of times in the same system it will yield ~25% win.
2. If I run this code on n devices (once each) will the result be ~25%.

n = very large number.

Are my assertions right?

Edit:My key doubt was, since computers use pseudo random numbers (which are based on a seed), will this affect this assertion (especially #2)

# Answer
> 1 votes
Yes - this is a consequence of the Law of Large Numbers. https://en.wikipedia.org/wiki/Law\_of\_large\_numbers

Yes - it still holds for pseudorandom number generators if they are any good.

Seed each PRNG independently.

---
Tags: distributed-systems, randomness, pseudo-random-generators
---


# Question
Title: Number of spanning arborescences with a specific root in a directed graph
I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:

where there are 5 spanning arborescences. Note that there is an edge from `b2` to `b3` and one from `b3` to `b2`.

Angela Pretorius mentioned a method in Number of Spanning Arborescences, Mathematics, but there is no euclidean circuit in this example. It seems that he/she is referring to BEST theorem.

# Answer
It seems that Kirchhoff's theorem can be used:

> Kirchhoff's theorem can be modified to count the number of oriented spanning trees in directed multigraphs. The matrix Q is constructed as follows:
>
> The entry i, j for distinct i and j equals −m, where m is the number of edges from i to j;
> The entry i, i equals the indegree of i minus the number of loops at i.
>
> The number of oriented spanning trees rooted at a vertex i is the determinant of the matrix gotten by removing the i-th row and column of Q.
> 1 votes

---
Tags: graphs, spanning-trees, directed-graphs
---


# Question
Title: Which language is used to construct a type system?
Typically, OCaml and Scala seem to be used for designing any programming languages tool. But what features offer them an edge over other languages.

A related question, is a type system for a language always written in the native language itself?

# Answer
> 4 votes
OCaml and Scala are popular choices for types systems, but they are by no means the only languages you can write a compiler, interpreter, typechecker, or type system in.

Type-checking involves traversing syntax trees representing terms and types. Languages with some form of algebraic data type make this easy, since these traversals can be defined using pattern-matching . In an object oriented language, these traversals have to be done using a Vistor pattern, which ends up using much more boilerplate. Languages like Haskell can use techniques like monads or datatype-generic programming to abstract away even more of the boilerplate of these traversals.

Also, functional programming languages tend to be closer to the lambda calculus and the other formalizations of programming languages. Since programming language researchers are often the ones developing both these formalizations and the implementations, so it makes sense that they'll be more comfortable in languages like these.

It's worth mentioning that a some work has been put into developing other ways to declaratively specify type systems for languages. For example:

* Turnstile is a Racket DSL that lets you develop type systems in a form that looks a lot like formal inference rules.
* Spoofax is a toolkit for writing programming languages, that can generate a typechecker with IDE integration from a specification.

> A related question, is a type system for a language always written in the native language itself?

Certainly not! It's popular for writers to implement a language in the language itself, (often called "self hosting"). If you're writing a programming language, then there's a good chance that it's been designed to solve problems that whoever was writing the language had. So whoever is designing the language probably finds it a pleasant language to use.

But for performance reasons, often languages are implemented lower-level languages like C or Rust. This is particularly important for interpreted languages: if you write your interpreted language in another interpreted language, then interpreting code involves running your interpreter in yet another interpreter, which is a lot of indirection that hurts performance.

---
Tags: type-theory, type-checking, dependent-types, type-inference, data-flow-analysis
---