# Question
Title: Is thread in operating system = thread function in programming languages?
I'm new to Operating System, just learnt about process and now is about to learn about threads. From what I understand,

1. a program is an executable file, program code
2. a process is a program in execution
3. a thread is part of a process
4. in a process, there might be multiple threads. e.g. MS Word
5. in a programming code, there is the main function and there're might be other functions also
6. because there is only one main function, usually the program would just run from top of the main function to down.

---

My question are:

Q1. Is thread in operating system = function in programming language?

Q2. Is function in programming language = thread function in programming language?

Q3. Is thread in operating system = thread function in programming language?

Q4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

**Q5. Where is thread written in operating system/ programming language?**

I appreciate it greatly if somebody can explain these in simple terms, and examples from analogy or simple programming languages (C/C++/java).

---

EDIT: What I mean by thread function (I'm not sure if this is a correct term) is like,

---

I guess that "thread function" = "thread".

If so, then, from David's answer,

> Q2. Is function in programming language = thread function in programming language?

* no.

And from a Q&A in Quora here, it says that

> Q: What is the difference between a thread in a programming language, like Java or Python, and a Linux thread?
>
> A: There is no difference; it is the same word with the same meaning (as opposed to one word that's overloaded to mean multiple things). The operating system will execute threads in parallel as requested by the software that creates the threads.

So, I guess that the answer for my third question,

> Q3. Is thread in operating system = thread function in programming language?

* yes.

And, from POSIX Thread

> Initially, your main() program comprises a single, default thread. All other threads must be explicitly created by the programmer

so I guess the answer for

> Q4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

* I think yes.

---

Q6. Will the program not be able to do multithreading if it doesn't include these thread functions?

* I think yes.

Although I'm not sure how it is included/written in programming code that doesn't explicitly use thread functions directly like CreateThread etc., which is my fifth question.

---

For example, in Tetris code in C, I didn't see any "thread" word inside the code. Instead, it uses `conio.h`, which is from wikipedia

> conio.h is a C header file used mostly by MS-DOS compilers to provide console input/output. It is not part of the C standard library or ISO C, nor is it defined by POSIX.

**Q7. So does this mean this particular programming code in Tetris code in C is single-threaded only?**

**Q8. Is it by including `windows.h`, a programming code can perform multithreading?**

---

Please correct me if I'm mistaken.

The remaining questions are Q5, Q7, Q8.

# Answer
> because there is only one main function, usually the program would just run from top of the main function to down.

That's a long way from being the case. Loops, conditional statements and function calls mean that the control flow of any non-trivial program is much more complex than just running from the top of `main()` to the bottom.

> 1. Is thread in operating system = function in programming language?

No. A thread is, essentially, a subprocess. A process may have several threads, and each of these threads executes semi-independently while sharing some common information. A function, on the other hand, is typically a somewhat self-contained unit of work.

An analogy might be that a process is like a company (there can be many different processes, they're kept separate from each other but they can arrange to cooperate with each other in various ways, governed by the law of the country they're in), a thread is like an employee of a company (employees share access to the company's resources and cooperate closely under rules defined by the company) and a function is a specific task that might be performed by an employee (making coffee, typing a letter, attaching a door to a car, etc.)

> 2. Is function in programming language = thread function in programming language?
> 3. Is thread in operating system = thread function in programming language?

The things you're calling "thread functions" are just programming language libraries that access the operating system's interface for creating and managing threads

> 4. Thread function allows multiple functions to be performed simultaneously, like having multiple main functions. Is this correct?

Well, threads allow multiple functions to be performed simultaneously. `main()` is just the entry point to the program as a whole: it's the place where execution starts.

> 5. Where is thread written in operating system/ programming language?

I'm not sure what you mean by this but it's going to depend on the OS and programming language in question.

> 6. Will the program not be able to do multithreading if it doesn't include these thread functions?

A program will need *some* way of telling the operating system to make a new thread. In practical terms, using a library that somebody has already written is going to be more convenient than trying to manage the interaction with the operating system yourself.
> 3 votes

---
Tags: operating-systems
---


# Question
Title: $(max,+)$ matrix product with limited number of values
I read that there is a $\Omega(n^3)$ lower bound for $(max,+)$ matrix multiplication (with $n\times n$ matrices). This is the matrix product defined as: $(A\cdot B)\_{ij}:=\max^n\_{k=1}\\{A\_{ik}+B\_{kj}\\}$, for some $n\times n$ matrices $A$ and $B$. This lower bound means that the trivial algorithm is the best one.

Is there a better algorithm if we restrict the values to be in a finite set? For example, all the matrix entries are $0$ or $1$. Note that this is different from Boolean matrix product.

Any reference is welcome.

# Answer
The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. The APSP problem uses a $(\min,+)$-matrix product. Since $\max\_{A} \sum\_{a\in A} a = -\min\_{A} -\sum\_{a\in A}a = -\min\_A \sum\_{a\in A}-a$, we can express a $(\max,+)$-matrix product as a $(\min,+)$-matrix product and vice versa, as the paper allows edge-weights to be either positive or negative.

So this gives a subcubic algorithm for $(\max,+)$-multiplication when the values are bounded.
> 4 votes

---
Tags: reference-request, matrices, multiplication
---


# Question
Title: Can Strassen's multiplication algorithm be improved if we divide matrices to 3x3 or axa in general?
Strassen's algorithm uses the divide and conquer approach to divide the matrix multiplication of two nxn matrices to multiplication of 7 2x2 matrices to get an overall complexity O(n^c) where c=log\_2(7). I also read a paper which proved that it was impossible to multiply two 2x2 matrices in less than 7 multiplication operations.

So my question is, what's so special about 2x2? Why not break the original matrix multiplication to 3x3 matrix multiplication. Surely, if we can make the multiplication in 21 multiplications or less, then we would have a better result than dividing it to 2x2. And then why stop at 3x3, when you can divide the problem to 4x4, or in general axa?

# Answer
> 3 votes
There is nothing special about 2×2 matrices. In fact you can do much better using larger matrices. The reason that you are only being explained the 2×2 algorithm is that it is simple to describe. The special thing about 2×2 matrices are that they are the smallest square matrices which are larger than 1×1.

You can read more in this recent survey by Dumas and Pan on fast matrix multiplication, which concentrate on practical algorithms.

From a pure mathematical point of view, the following theorem is known:

> Suppose that the algebraic complexity of matrix multiplication is $O(n^\alpha)$. Then for every $\epsilon \> 0$ there is a divide-and-conquer algorithm for multiplying matrices in $O(n^{\alpha+\epsilon})$.

Here a divide-and-conquer algorithm is an algorithm which recursively applies some smart algorithm for multiplying $m\times m$ matrices, for some *constant* $m$.

The fastest theoretical algorithm for matrix multiplication, due to Le Gall, is based on the classical algorithm of Coppersmith and Winograd. Unfortunately, this algorithm isn't practical.

---
Tags: algorithms, algorithm-analysis, divide-and-conquer, multiplication
---


# Question
Title: State complexity of homomorphisms of regular languages
Given a DFA $A = (Q, \Sigma, \delta, q\_0, F)$ with $n$ states and a homomorphism $h: \Sigma \to \Gamma^\*$. It is easy to see that the family of regular languages is closed under homomorphisms using regular expressions or by construction of a grammar.

My problem now is to analyze how many states are needed for a DFA $A' = (Q',\Gamma, \delta',q\_0',F')$ to accept $h(L)$. First of all I tried to think of a basic construction method to get the automaton.

Let $a \in \Sigma$:

1. If $h(a) = \varepsilon$ then all the transitions of $a$ in $A'$ can be removed.
2. If $|h(a)| = 1$ then all the transitions with $a$ can be replaced with $h(a)$.
3. If $|h(a)| \geq 2$ then the transition of $a$ in $A'$ has to be replaced with $h(a)$ and split into $|h(a)|-1$ states each with a one symbol transition

a. If the prefixes of two unique symbols of $\Sigma$ do not share the same prefix then the resulting automaton can be extended into a DFA without adding any states(?).

b. If prefixes are shared then the resulting automaton would be an NFA, therefore it has to be converted into a DFA (using power set construction) and minimizing it.

Therefore my estimation for the state complexity in case $3a$ would be: $$\begin{align\*}|Q'| &\leq |Q| + |Q|\cdot\left(\sum\_{a \in \Sigma} |h(a)| - 1\right)\\ &= |Q|\cdot(1- |\Sigma|+\sum\_{a \in \Sigma} |h(a)| )\end{align\*}$$

However, I'm not convinced about my construction as mentioned in step 3 and was not able to find an example of a language where the upper boundary is met. Therefore I'd be happy to see any advices.

# Answer
> 1 votes
Here is a simple construction that disproves your conjecture.

Let $a,b$ two relatively prime integers. It is known that the largest integer that cannot be represented as a non-negative integer combination of $a,b$ is $ab-a-b$.

Consider now the language $L = (0+1)^\*$ and the homomorphism $h$ given by $h(0) = 0^a$ and $h(1) = 0^b$. Then $L$ is accepted by a one-state DFA, while $h(L)$ requires $ab-a-b+1$ states.

---
Tags: regular-languages, finite-automata, descriptive-complexity
---


# Question
Title: Is $2^{1+\sqrt{mn}}$ an upper bound for the size of the DFA resulting from the determinisation of n DFAs of size m
*(all automata sizes are expressed in number of states in this question)*

There exist NFAs of size $n$ for which the smallest DFA recognizing the same language is of size at least $2^n$.

Let $\Sigma$ be a vocabulary, and let's consider $n$ regular languages $L\_i \subseteq \Sigma^\*$ respectively recognized by $n$ DFAs $D\_i=\\{Q\_i, q^0\_i, F\_i , \delta\_i \\}$ whose size are bounded by $m$.

We consider the epsilon-free NFA $N$ built by merging the $n$ DFAs such as $N=\\{Q=\bigcup Q\_i, q^0, F=\bigcup F\_i , \delta \\}$ where $\delta = \bigcup \delta\_i$ with the additional constraint that $\forall \sigma \in \Sigma \\, \delta(q^0, \sigma) = \\{q | \delta\_i(q\_i^0, \sigma)=q \\, \\, 0 \leq i \leq n \\}$ (note that in $N$ the $q^0\_i$ are not anymore initial states since there is a unique initial state $q^0$).

Let $D\_N$ be the DFA resulting from the powerset construction of $N$ and $D\_N^M$ be the DFA resulting from the minimisation of $D\_N$.

Is the size of $D\_N^M$ at most $2^{1+\sqrt{mn}}$ ?

An equivalent question is : let $L \subseteq \Sigma^\*$ be the language resulting from the union of the $n$ regular languages $L\_i$, is the size of the smallest DFA recognizing $L$ always below $2^{1+\sqrt{mn}}$ ?

I would appreciate if possible, some papers related to this problem or a proof/counter-example.

Many thanks, Luz

# Answer
> 4 votes
No. Asymptotically, the size can be as large as $\sim m^n$.

Let $p\_1,\dots,p\_n$ denote the $n$ largest prime numbers that are at most $m$. Let

$$L\_i = \\{x : x \not\equiv 0 \pmod{p\_i}\\},$$

where we assume the number $x$ is expressed in unary. Then $L = L\_1 \cup \dots \cup L\_n$ has the form

$$L = \\{x : x \not\equiv 0 \pmod q\\},$$

where $q = p\_1 \times \dots \times p\_n$.

Note that, with this construction, each $L\_i$ has a DFA of size at most $m$ (in particular, of size $p\_i$). However, the minimal DFA for $L$ has size $q$, which is close to $m^n$. In particular, the size of the minimal DFA for $L$ is asymptotically larger than $2^{1 + \sqrt{mn}}$ (as a function of $n$, treating $m$ as fixed).

# Answer
> 3 votes
Let $\Sigma$ be an alphabet of size $n$. For each $\sigma \in \Sigma$, let $L\_\sigma$ be the language of all words not containing $\sigma$. Each $L\_\sigma$ is accepted by a DFA with $m=2$ states. It is well known that $L = \bigcup\_{\sigma \in \Sigma} L\_\sigma$ requires $2^n = m^n$ states to be accepted by a DFA.

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


title: Basic notation in lambda calculus

text:
# Question
Title: Basic notation in lambda calculus
I have started learning lambda calculus from the book by Hindley and Seldin.

It brought up the concept with the function $x-y$, first as a function of $x$ and then as a function of $y$. In a way, it emphasized the difference between treating the expression as a function of $x$ and function of $y$, giving separate names to the functions.

$$f(x,y) = x-y \qquad\text{and}\qquad g(y,x) = x -y$$ and, in $\lambda$ notion, $$h = \lambda xy.x-y \qquad\text{and}\qquad g = \lambda yx. x-y\\,.$$

If I am not wrong then it can be inferred that $f =\lambda x .(x-y)$ means that while computing the value of the expression the expression will vary only with $x$ and similarly when $\lambda$ is placed with $x$ the other variable $y$ will be kept as a constant.

But then it said that this can be denoted as, with $h$ being the common name of the function $$h = \lambda xy.(x-y)\qquad\text{and}\qquad h = \lambda yx.(x-y)\\,.$$
Is it so that in the above expression the variable which is adjacent to $\lambda$ receives the value and the other one is constant? The above function is called a two-place function; what does that mean?

Then he introduces the following function in $\lambda$ notation calling it a one-point function: $$h^\star = \lambda x .(\lambda y . x−y)$$ and says that, for each number $a$, we have $h^\star(a)=\lambda y . a−y$. Here $a$ is being provided as an argument but $\lambda$ is placed near $y$. Why is this?

And then it deduces that $(h^\star(a))(b)=(\lambda y . a−y)(b) = a−b = h(a,b)$ and says $h^\star$ can be viewed as "representing" $h$. Is "representing" a technical term? How was $(\lambda y . a−y)(b) = a−b$ concluded?

# Answer
> 2 votes
> If I am not wrong then it can be inferred that :
>
> $f=\lambda x.(x−y)$ means that while computing the value of the expression the expression will vary only with "x" and similarly when "lambda " is placed with x the other variable y" will be kept as a constant .

Yes, intuitively that's how it works.

---

What you're looking is called Currying and it's explained fairly early in this book (in fact, I think it's the next section but I don't have a copy now to check). So when we want to work with functions with many arguments we often do it like this:

$$ f(x,y,z) = x\times y + z$$

But you can break this into simpler functions, $(x \times y)$ and $(+z)$. The multiplication can be broken into even simpler terms, first I provide $x$, then just multiply by $y$, that is, $f^{\star}(y) = x\times y$.

Defining some 1-argument functions:

$$ \begin{align\*} plus\_z &:= f^\prime(s) = s + z\\ times\_y &:= f^\star(s) = s\times y \end{align\*} $$

Combining these we can rewrite $f$ as:

$$ f(x,y,z) = f^\prime(f^\star(x)) = plus\_z (times\_y ~ x) $$

Writing this in using $\lambda$ we have:

$$ \lambda x y z. (x\times y + z) \equiv \lambda x.\bigg(\lambda y. \Big(\lambda z. (x\times y + z ) \Big) \bigg)$$

What the author has shown is that you can take a function with many arguments and transform it into many simpler functions with just one argument, the bigger function is just a composition of the simpler ones.

So just how the proof works? In your book the following functions are defined:

$$ \begin{align\*} h^\star &= \lambda x . (\lambda y . x − y)\\ h(x,y) &= x-y \end{align\*} $$

You want to show that $ h^\star = h$. To do that just take any two arguments $a$ and $b$. First evaluate $h^\star$ in $a$.

$$ h^\star(a) = (\lambda x. (\lambda y. x - y))(a) = \lambda y. a - y$$

This gives you a simpler one argument function $h^\prime = h^\star(a)$.

> How was $(λy.a−y)(b)=a−b$ concluded

The same way $(\lambda x. (\lambda y. x - y))(a) = \lambda y. a - y$ was concluded. Just evaluate the function in $b$.

$$ h^\prime(b) = (h^\star(a))(b) = (\lambda y. a - y)(b) = a - b$$

Which is the same result computed by $h(a,b) = a - b$.

---
Tags: lambda-calculus
---


# Question
Title: the sum of degree of all vertices in tree with 10 vertices
let T be tree with 10 vertices. what is the sum of degree of all vertices in tree

# Answer
> 0 votes
Fact one: graph is a tree on $n$ vertices, it has exactly $n-1$ edges https://en.m.wikipedia.org/wiki/Tree\_(graph\_theory)

Fact two: sum of all degrees is twice number of edges https://en.m.wikipedia.org/wiki/Handshaking\_lemma

Thus, for $n=10$ we get

$\sum\limits\_{v \in V} deg(v) = 2(n-1) = 18$

---
Tags: graphs
---


# Question
Title: Is selecting some of the sets such that their intersection is of size k NP-hard?
Given collection of sets S1,...,Sn and a positive number k. Is the problem of selecting some of the sets such that their intersection is of size k NP-hard?

So far, I tend to believe it is so I tried to find a reduction (unsuccessful so far), I have tried is to replace intersection by union (which is equivalent if we take the complementary sets).

I've also tried to dualize the problem and view a values as representing sets where they appear (unfortunately this transformed problem is not equivalent Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones)

I don't know if this problem is of interest for the reduction but it is the closest hard one I've found http://www.ic.unicamp.br/~eduardo/publications/ipl12.pdf

# Answer
As you suggested, the problem is equivalent to selecting sets with union of given size $k$. It is not easier than selecting **given numbers** (say, $m$) of sets with union of given size $k$, since we could add different auxiliary elements $a\_S^{(0)},\ldots,a\_S^{(n)}$ to each set $S$ and ask for a union of size $m(n+1)+k$, where $n$ is the size of the original universe. Now it is not hard to show the later problem is NP-hard because of a reduction from X3C (exact cover by 3-sets).
> 3 votes

---
Tags: np-complete, np-hard
---


# Question
Title: Recursively enumerable but non recursive subset of an infinte recursive language
How can we show that, for every infinite recursive language, it has a subset that is recursively enumerable but not recursive?

I think we need to show there's a list of natural numbers that can't be ordered but I don't know how to build such a subset.

Is there another way of arguing or another type of argument in order to prove such subset exists?

# Answer
> 1 votes
Hint. Let $S$ be any infinite recursive language. By considering, e.g., the lexicographic order, we can talk of the first, second, third, etc. strings in $S$. Use this indexing to define what you need to define.

# Answer
> 0 votes
Another hint. Let A be the infinite recursive language. Prove that you may define a computable *bijective* function f:N-\>A. Then take any r.e. not recursive subset of N (e.g. the diagonal set K). f(K) is the set you are looking for.

---
Tags: formal-languages, computability, undecidability
---


# Question
Title: Function is recursive iff its graph is recursively enumerable
So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere. But how to prove that function is recursive if and only if the language {x#f(x) |x∈(Г -{#})\*)} (graph) is recursively enumerable?

# Answer
In order to prove your claim, you need to prove two things:

1. If a function is recursive then its graph is r.e.
2. If the graph of a function is r.e. then it is recursive.

Let's see what you have to do to prove these two claims.

**Claim 1.** Suppose that $f$ is recursive, i.e. it is computable by some program. You have to come up with another program that enumerates $x\\#f(x)$. For example, assuming the inputs are natural numbers, it could output $1\\#f(1),2\\#f(2),3\\#f(3),\ldots$.

**Claim 2.** Suppose that $\\{x\\#f(x)\\}$ is r.e., that is, some program enumerates $x\\#f(x)$ for all legal inputs $x$, in some order. Given an input $y$, we need to use this enumeration to compute $f(y)$. It is natural to wait for $y\\#f(y)$ to be enumerated and extract $f(y)$.

Your task now is to flesh out these proof sketches.
> 5 votes

# Answer
Unfortunately, there is a painful terminological overloading of the term "recursive" in computability theory. So you must pay attention if you are talking about a function or a set.

In relation to functions, "recursive" is used as a synonym of "computable". This is also the intended meaning of the world in the definition of "recursively enumerable set", since the attribute "recursive" refers to the enumeration function, that must be computable, and not to the set being enumerated.

In relation to sets, "recursive" means decidable. This is due to the fact that you are implicitly referring to the "recursiveness" (that is, computability) of the *characteristic* *function* of the set, that by definition is a *total* function.

So, coming to your question, the fact that the function is *recursive* only means that it is *computable*, but does not imply that it is also total.

For *total* functions, the function is recursive if and only if its graph is recursive, that is probably what was puzzling you.
> 1 votes

---
Tags: computability, semi-decidability
---


# Question
Title: Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive?
Suppose $L\_1, L\_2, ..., L\_k$ are recursively enumerable languages forming a partition of $\Sigma^\*$.

How do I show that each $L\_i$ are recursive ?

I see that for $x \in \Sigma^\*$, $x$ belongs to exactly one $L\_i$.

My idea is to run every Turing machine simultaneosly, stopping as soon as one of them accepts $x$ (must happen at some definite time by assumption).

What theory can I use to make my idea rigorous ? I've considered an non-deterministic TM, but also a $k$-tape TM, but none seems to suit my needs ?

Can someone help ?

# Answer
If you already proved the binary case, a more formal answer is to observe that, for any i, the complement of $L\_i$ is r.e. since it is a finite union of r.e. sets. Since the set and its complement are r.e., it is recursive.
> 1 votes

---
Tags: computability, semi-decidability
---


# Question
Title: $\lambda x. \lambda x.x$ vs $\lambda y. \lambda x.x$
Several times, I saw $\lambda$-terms such as $\lambda x. \lambda x.x$, where $x$ is bound by the inner lambda, which I agree.

why not just write it as $\lambda y. \lambda x.x$, so it is clear and you don't need to comment such as "where $x$ is bound by the inner lambda".

1. what is the point of writing $\lambda x. \lambda x.x$, why not just write it as $\lambda y. \lambda x.x$? Usually, we don't write long lambda terms, so we have enough names to name bound variables distinctly.
2. why not just state that "all bound variables should be given distinct names" to avoid such vague terms and explanations?
3. is there a particular reason for having $\lambda x. \lambda x.x$?

I believe it is because of the syntax of lambda terms. I also believe banning such terms is reasonable.

# Answer
> 3 votes
You have basically discovered the Barendregt convention.

Yes, it's silly to write terms such as $\lambda x. \lambda x. x$ when $\lambda y. \lambda x. x$ is $\alpha$-equivalent and clearer.

We could forbid the former form the syntax of the lambda calculus. This however would force us to check $x$ does not occur bound in $M$ every time we craft (introduce) the term $\lambda x. M$.

The Barandregt convention goes further. It stipulates that, when building (introducing) a term $\lambda x. M$ we are always allowed to do that. However, when destructuring (eliminating) a term $\lambda x. M$ we can assume that $x$ was $\alpha$-converted so no to cope with other bound names in $M$, nor with other names that we could have around elsewhere at the moment: e.g., if we are writing a proof involving terms $N$ and $O$, the convention stipulates that $x$ does not occur in $N,O$ as well.

The convention is just a convenient shortcut, made for lazy humans which do not want to spend their time and energy to fix trivialities. Basically, we pretend that $\lambda x.\lambda x. M$ is allowed when it's convenient to do so (introduction), yet we pretend that the same is no longer allowed when convenient to do so (elimination). It feels a bit like cheating, but one could (in theory) always fix the proof to be perfectly sound.

---
Tags: lambda-calculus
---


title: -4 as floating point

text:
# Question
Title: -4 as floating point
How would one represent the number -4 as an 8-bit normalised, 2's complement, floating point, with 4 bits dedicated to the exponent?

As a normal 4-bit 2's complement number, it would be represented as 1100.

How would this be normalised, with the start of the mantissa being 1.0?

Would it be 1.000 0010, with the extra 1 on the left (after evaluation to a normal 2's compliment number) being filled in?

If so, how would you know to fill it with a 1, because it starts with a 1?

# Answer
> 1 votes
AFAIK, there is no standard with that format.

You can nevertheless try to imitate the old MIL-STD-1750A floating point format, which had two's complement mantissas and exponents.

The two's complement mantissa range is -1.0 to 0.999999....

Something like that :

```
                     Mantissa Exponent
'   0 =                  0000 0000
'0.25 =  0.5 * 2**-1 =   0100 1111
' 0.5 =   0.5 * 2**0 =   0100 0000
'  +1 =   0.5 * 2**1 =   0100 0001
'  +2 =   0.5 * 2**2 =   0100 0010
'  +4 =   0.5 * 2**3 =   0100 0011
'  -1 =  -1.0 * 2**0 =   1000 0000
'  -2 =  -1.0 * 2**1 =   1000 0001
'  -4 =  -1.0 * 2**2 =   1000 0010

```

Note the asymmetry between +1 and -1.

etc...

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


# Question
Title: $A, B$ --- enumerable sets, is $A \times B$ enumerable?
$A, B$ – enumerable sets, is $A \times B$ enumerable? I have some thoughts, that maybe it can be done using something like the proof of countability of $\mathbb{N} \times \mathbb{N}$, but I don't know how to prove this more proper.

# Answer
There are many ways you could solve this, so here's a hint. $A$ and $B$ are enumerable, which means that injections

$$ f : A \rightarrow \mathbb{N} \quad \text{and} \quad g : B \rightarrow \mathbb{N}$$

exist. Now, given a tuple $t \in A \times B$, how can you map it to a unique element in $\mathbb{N} \times \mathbb{N}$ using $f$ and $g$?

> Since $f$ and $g$ are injections, their product must also be an injection (prove this). So the function $h : A \times B \rightarrow \mathbb{N} \times \mathbb{N}$, defined as $(a, b) \mapsto (f(a), g(b))$. Is an bijection on a subset of $\mathbb{N} \times \mathbb{N}$ (because it is an injection on $\mathbb{N} \times \mathbb{N}$).

A subset of an enumerable set is always countable, so this concludes the proof.
> 5 votes

# Answer
Let $a\_0,a\_1,a\_2,\ldots$ be an enumeration of $A$, and let $b\_0,b\_1,b\_2,\ldots$ be an enumeration of $B$. Then one enumeration of $A \times B$ is $$ (a\_0,b\_0), \\ (a\_0,b\_1),(a\_1,b\_0), \\ (a\_0,b\_2),(a\_1,b\_1),(a\_2,b\_0), \\ \ldots $$ See if you can turn this idea into a full-fledged proof.
> 3 votes

---
Tags: computability, discrete-mathematics
---


# Question
Title: Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable
> Define the language
>
> $\qquad R = \\{x \in \\{0,1\\}^\ast \mid C(x) \ge |x| \\}$
>
> where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$.
>
> Prove that $R$ is co-recursively enumerable (co-r.e.).

So far, I have the following:

In order to prove the above, we need to show

$\qquad R^c$ = $\\{x \in \\{0,1\\}^\ast \mid C(x) \lt |x| \\}$

is r.e. That is there exists a program $\pi$ such that the univeral TM $U$ with argument $\pi$ equals $x$ and $|\pi| \lt |x|$ (where $U(\pi) = x$ and $|\pi| \lt |x|$).

We start by enumerating all strings in $\\{0,1\\}^\ast$.

I have no idea where to go from this point onward.

# Answer
### Fancy answer

We need to show that the set $$R = \\{x \in \\{0,1\\}^\* \mid C(x) \< |x|\\}$$ is c.e. (allow me to use the new terminology). The defining condition for $R$ is equivalent to $$\exists n, m \in \mathbb{N} \\,.\\, T(n,0,m) \land U(m) = x \land |n| \< |x| \tag{1}$$ where $T$ is Kleene's predicate and $U$ the associated output function. In words, the formula means: there exists a code $n$ such that the $n$-th machine computes $x$ (on input $0$) and the length of $n$ is less than the length of $x$. We are done because (1) is a $\Sigma^0\_1$-formula, therefore it defines a c.e. predicate.

Scholium: a $\Sigma^0\_1$ formula is a formula of the form $$\exists n \in \mathbb{N} \\,.\\, \phi(n, x)$$ where $\phi(n,x)$ is a decidable formula. Such a formula determines a c.e. predicate: to semidecide whether it holds for $x$, just run a loop $n = 0, 1, 2, \ldots$ and test for each $n$ whether $\phi(n,x)$ holds. If and when such an $n$ is found, terminate.

### Non-fancy answer

In paralell, run all machines described by codes of length less than $|x|$ (there are around $2^{|x|}$ such machines, which is a finite number). If and when one of them stops and produces output $x$, terminate.
> 7 votes

# Answer
An alternative, simple but formal answer is to observe that $\overline{R}$ can be *partially* enumerated by the following computable function:

$$g(i) = \begin{cases}|\varphi\_i(x)| & if~|i| \< |\varphi\_i(x)| \\ \uparrow & otherwise \end{cases}$$

Here, $\varphi$ is an acceptable enumeration of the partial recursive functions. I leave details to the reader.
> 0 votes

---
Tags: computability, turing-machines, semi-decidability, kolmogorov-complexity
---


# Question
Title: Is the set of programs that compute some function other than $h$ recursively enumerable?
> Let $h$ be a total computable function. Is $S = \\{x \mid f\_x \neq h\\}$ recursively enumerable?

Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated as a more general case.

By Rice's Theorem, it is not recursive. Intuitively,

* $S$ is not r.e. as if it was, it would mean that we would know that $f\_x(y)$ halts for some input $y$ in order to check if it has a different image of $h(y)$.
* $\overline{S}$ is not r.e. as if it was, we would be able to check if $f\_x(y) = h(y)$ for every input $y$ (we would check equality for infinite inputs).

How would you solve this problem?

**Note:** I tried something, but I'll post it as an answer. Some thoughts would be great and really helpful. Any approach to this problem using reduction or diagonalization methods would be useful.

# Answer
> 3 votes
The set $S$ is in fact neither c.e. nor co-c.e. You can prove this via an m-reduction to $\overline{TOT} = \\{ x | \varphi\_x \mbox{ is not total } \\}$ (which is also neither c.e. nor co-c.e.).

Define:

$ \varphi\_{f(x)}(y)=\begin{cases} h(y) & \mbox{if $\forall z\leq y~\varphi\_x(y)$ halts}\\ undefined & \mbox{ow.} \end{cases} $

Where $f$ is from the s-m-n theorem.

Then you have that $\overline{TOT} \leq\_m S$ via $f$ because, for all $x$:

$x \in TOT \iff \forall y~\varphi\_x(y) \mbox{ is defined} \iff \forall y~\forall z\leq y~\varphi\_x(z) \mbox{ is defined} \iff \forall y~\varphi\_{f(x)}(y)=h(y) \iff f(x) \notin S$

# Answer
> 0 votes
Suppose $S = \\{x | f\_x \neq h\\}$ is r.e.

Then, define g such that:

$\qquad\displaystyle g(x) = \begin{cases} h(x), &\text{ if $f\_{x\_0}(x\_0)$ halts } \\ undefined, &\text{else} \end{cases} $

Then, $g$ is computable i.e. a $TM$ can be constructed such that it computes $h(x)$ if the $x\_0-th$ machine halts on specific input $x\_0$ or loops if it does not. Then, $\forall x\_0$ $\exists i$ s.t. $f\_i = g$. Hence,

$f\_i = h \iff f\_{x\_0}(x\_0)$ halts

Let $H = \\{x | f\_x(x) \text{ halts}\\}$. Then, $i \in \overline{S} \iff x\_0 \in H$.

Hence, $H \leq\_r \overline{S}$, or equivalently, $\overline{H} \leq\_r S$.

If $S$ is r.e., $\overline{H}$ is r.e. But $H$ is also r.e. (the Halting Problem is semi-decidable). Consequently, $H$ is recursive which contradicts the fact the the halting problem is undecidable. Hence, $S$ is not r.e.

# Answer
> 0 votes
Let's look at the definition of the set $S = \\{ x : f\_x \not = h\\}$. There are two ways that a given $f\_x$ could differ from $h$:

1) For some $n$, $f\_x(n) \downarrow \not = h(n)$

2) $f\_x(n) \uparrow$ for all $n$.

In the former case, we would be able to find a "witness" $n$ by simulating the execution of $f\_x$ on all inputs. But, in the latter case, it seems as if we will never be able to tell, in a finite amount of time, that $f\_x$ will never be defined. We can use this insight to show that $S$ is not computable.

Let $A$ be some co-r.e. but not r.e. set, e.g. the complement of the halting problem. Let $h$ be any total computable function, e.g. the constant zero function.

For each $n$, define a function $F(n)$ that does the following. It ignores its input $j$. It just simulates the enumeration of $A^c$. If it finds that $n \in A^c$ then it immediately halts and returns 0 (that is, it returns $h(j)$). Thus $n \in A^c$ if and only if $F(n) = h$; if $n \in A$ then $F(n)(j)$ is undefined for all $j$. Moreover, there is a computable function $p$ that, given $n$, produces an index $p(n)$ for $F(n)$.

Now, for each $n$, $n \in A^c$ if and only if $f\_{p(n)} = h$. Thus $n \in A$ if and only if $f\_{p(n)} \not = h$, which happens if and only if $p(n) \in S$. If $S$ is an r.e. set then we can enumerate the set of number of the form $p(n)$ that are in $S$, which means we enumerate $A$: if $S$ is r.e. then so is $A$. But that is impossible by the choice of $A$.

This is an example of a sort of "parity switch" argument, which is a useful technique. The proof shows that if $S$ was r.e., we could use that to "switch the parity" of an arbitrary co-r.e. set to r.e. That isn't possible in general, so $S$ can't be r.e. You can see the roots of the parity switch in item (2): $S$ has to "do something" (enumerate $x$) if and only if $f\_x$ does *not* "do something" (halt on at least one input). That sort of situation often lays the foundations for this type of argument.

# Answer
> 0 votes
By the Rice-Shapiro Theorem, S is not c.e. because it is not compact.

---
Tags: computability, reductions, semi-decidability
---


# Question
Title: Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL
Assuming $L$ is defined as follows:

$$ L = \\{ 0^n1^{n^2} | n \ge 0 \\} $$

I'm trying to either prove/disprove whether $L$ is CFL or not.

My intuition tells me its not CFL since I cannot express the power $n^2$ by itself using CFL, but I'm having trouble proving so using the pumping lemma. Also, I failed to create any such PDA (which my intuition says its impossible).

# Answer
> 1 votes
Let $h\colon \\{0,1\\} \to \\{0\\}$ be the homomorphism given by $h(0) = \epsilon$ and $h(1) = 0$. If $L$ were context-free, so would $h(L) = \\{ 0^{n^2} : n \geq 0 \\}$ be. Since $h(L)$ is a unary language, it would be regular. However, a unary language is regular iff it is eventually periodic, which it isn't. Therefore $L$ cannot have been context-free.

More generally, if $L$ is context-free then:

1. The set of lengths of words in $L$ is eventually periodic.
2. The set of number of occurrences of a symbol in $L$ is eventually periodic.

The most general statement of this kind is Parikh's theorem.

---
Tags: automata, pumping-lemma, pushdown-automata
---


# Question
Title: What is the O time complexity for this algorithm?
is the Big-O for this O(1) or some asymptotic like 1/n?

Saying that because if it defaults, the time limits at about 1000000 ns, but if it returns while in the loop, it is about a fraction of that. The time seems to increase very slightly as the inputs increase.

```
public static int[] call(int b, int c) {
    int[] f = new int[2];
    final double n = 1.13;

    for (int x = -100; x < 100; x++) {
        for (int y = -100; y < 100; y++) {
            if (((n+x)*(n+y)) == ((n*n)+(b*n)+c)) {
                f[0] = x;
                f[1] = y;
                return f;
            }
        }
    }
    return f;

    /* // timer method
     * long startTime = System.nanoTime() ;
     * call();
     * long endTime   = System.nanoTime() ;
     * long totalTime = endTime - startTime;
     * System.out.println(totalTime);
     *
     *      f(2, 1)   : 499284
     *      f(4, 4)   : 487452
     *      f(6, 9)   : 501479
     *      f(8, 7)   : 493296
     *      f(10, 21) : 500602
     *      f(12, 36) : 505862
     *
     */

}

```

Also, please ignore that the code is wonky.

# Answer
> 1 votes
The upper bound doesn't get affected by inputs b & c so we can say it is $O(1)$.

---
Tags: time-complexity, java
---


title: Push-down Automata Construction

text:
# Question
Title: Push-down Automata Construction
Construct a push-down automata to recognize the language $ A = \\{u\\#v \in \\{0,1,\\#\\}^{\*} | u = v^{\complement} \\} $. Here, $v^{\complement}$ is the bit-complement of v.

I don't see how to perform this with a LIFO stack. I would like some hints (not a solution) if possible.

Thanks,

# Answer
There is no such PDA because $A$ is not context-free. This can be proved by pumping.
> 3 votes

---
Tags: formal-languages, context-free, pushdown-automata
---


# Question
Title: Designing DFA for accepting a string with a 1 in the tenth place from the right over an alphabet {0,1}
I'm stuck trying to implement a DFA to do this. Everything I've tried so far seems to have to be able check the next nine elements to determine if the string terminates. Any tips?

# Answer
> 1 votes
Your idea is correct.

Using the Myhill-Nerode theorem, it can be proven that the DFA for this language with the minimum number of states has $2^{10}=1024$ states.

Firstly, it is easy to see that the language is regular using an NFA of $11$ states. In the start state, have transitions for $0,1$ to itself, and a transition for $1$ to another state. From there, have a single common transition for $0,1$ from a given state to a new state each time. The last state is the final state. Thus, the string is accepted if $10$ characters earlier, the symbol was a $1$, which enabled the strings symbols to enter this "chain".

Your equivalent DFA will need to remember the each of the last $10$ symbols, which give $2^{10}$ combinations. It can be shown that every string using the given alphabet can be divided into $2^{10}$ equivalence classes over this language, one for each combination.

For any two strings over this alphabet, if they have the last $10$ symbols the same, then every string appended will result in either both being accepted by the language or both rejected by the language. They will be accepted if the first symbol is a $1$, and rejected otherwise. So, they are equivalent.

For any two strings whose last $10$ symbols are not the same, there must exist some position where they differ. By simply appending any string such that the resultant string has the symbols from this position at $10$ places from the end, one must be accepted and the other must be rejected. So, they cannot be equivalent.

If the number of symbols are less than $10$, prepend with leading zeroes, and the argument still holds.

Thus, we have $2^{10}$ equivalence classes, and by the Myhill-Nerode theorem, any DFA for this language must have at least $2^{10}$ states.

# Answer
> 0 votes
You can create an NFA easily for such languages whose $n^{th}$ symbol from rigth is specific. You can create a DFA for second and third last symbol 1 from the NFAs. Then I know there is some pattern in $\delta$ and $A$ that can be found easily and you can implement an automaton with 1024 states on a machine.

> Take $$Q = \\{q\_0,q\_1,... q\_{1023}\\}$$
> $$\delta(q\_i,a) = q\_j ,j=(i\\%512)\*2+a$$
> $$A = \\{q\_0,q\_1,...q\_{511}\\}$$
> It looks unconventional but take $q\_{1023}$ as initial state.

---
Tags: formal-languages, automata
---


# Question
Title: What makes data flow analysis higher level than control flow analysis?
I feel understanding why data flow is higher level than control flow is key to writing good code (and convincing others during code reviews). I find this repeatedly when arguing why my functional style programming with immutability is superior to their mutable state code which is more common and expected.

But I don't understand why one is higher level than the other. The closest I can come up with, informally, is that ultimately end users don't care about what movement of control occurred. But they DO care what movement of data took place.

Other examples

* applications which just do processing last only a couple of years, whereas files which store data can last decades)
* a CPU just transforms volatile data, whereas disks store data persistently

In other words, control flow is a means of achieving data flow.

Is there a more rigorous way to explain this?

<sub>(source: slideplayer.com)</sub>

# Answer
> 1 votes
Look at Wikipedia article "Control Flow". It contains typical flow chart. Arcs are the ways where control token moves from one node to another.

Now imagine you want to employ parallelism and launch several control tokens. Immediately a problem arise: how to isolate pieces of data from simultaneous modification by different control tokens. To tackle with this problem, we divide our data in parts - one parts belong to dedicated control token, and others are for exchanging information between control tokens. The result is a dataflow diagram (or chart). That is, to manage data in parallel environment, we have to split data into pieces and explicitly manipulate them. Data flow is no more than parallel control flow.

Functional programming is another story. While there exist both control flow (von Neumann) and data flow processors, there is no functional processor. Functional programs can be compiled both to data and control flow processors. But since ordinary imperative programs cannot be directly compiled to dataflow processors (they first have to be converted to dataflow programs, which is hard), and converting functional programs to dataflow representation is easy, we can consider functional programming as a variant of dataflow programming.

And finally, consider distributed computing. Since it involves multiple computers with no shared memory, it is best described as dataflow computing and not as imperative computing. What happens inside computer nodes, is it functional programming or imperative, does not matter. But the way how data are exchanged matters. And using functional data structures to exchange data between nodes is very appropriate.

---
Tags: lambda-calculus, functional-programming, programming-paradigms, data-flow-analysis
---


# Question
Title: Proving that $f(n) = o(g(n))$ implies $2^{f(n)} = o(2^{g(n)})$
I can't find a counterexample to $$f(n) = o(g(n)) \text{ implies } 2^{f(n)} = o(2^{g(n)})\\,,$$ but I do not know a formal way of proving it. Can anyone lead me in the right direction? I asked this exact question yesterday in Stack Overflow by accident (meant to post here) but no one could come up with a valid way of approaching this question.

This is "little-$o$" notation by the way. So a strict upper bound It should be for monotonically increasing functions

# Answer
Hint:

We want to prove $2^{f(n)} = o(2^{g(n)})$. This is equivalent to $\lim\_{n\to\infty} \dfrac{2^{f(n)}}{2^{g(n)}} = 0$. We can rewrite the expression inside the limit as $2^{f(n)-g(n)}$, and, exploiting the hypothesis $f(n) = o(g(n))$, we have $\lim\_{n\to\infty} f(n)-g(n) = \cdots$
> 3 votes

# Answer
Firstly, let's establish the definition for little-o:

$f(n) = o(g(n))$ if and only if $\lim\limits\_{n \to \infty} \frac{f(n)}{g(n)} = 0$

* Firstly, about counterexample. Take $f(n) = \frac{1}{n^2}$ and $g(n) = \frac{1}{n}$. The ratio is $\frac{f(n)}{g(n)} = \frac{\frac{1}{n^2}}{\frac{1}{n}} = \frac{1}{n} \to 0$, so $f(n) = o(g(n))$. However, $\frac{2^{f(n)}}{2^{g(n)}} = 2^{f(n) - g(n)} = 2^{\left(\frac{1}{n^2} - \frac{1}{n}\right)} \to 1$, because $\frac{1}{n^2} - \frac{1}{n} \to 0$ when $n \to \infty$, so the conclusion given is not correct.
* Secondly, let's see the formality so we know from where this counterexample comes and what additional conditions might support the claim.

Recall, that if $\lim\limits\_{n \to \infty} \frac{f(n)}{g(n)} = 0$ then by definition of the limit $\forall \epsilon \> 0 \exists N\forall n \geq N : \left|\frac{f(n)}{g(n)}\right| \leq \epsilon$. From this immediately we get $\left|{f(n)}\right| \leq \epsilon\left|{g(n)}\right|$. After subtracting $g(n)$ and adding for example positiveness (don't want to dig into all cases) we get something like $f(n) - g(n) \leq (\epsilon-1) g(n)$. The conclusion I have taken from here is that the claim might be true only if $g(n) \to \infty$. And that's exactly from where I took the counterexample.

*Update 1*

For those who ask what about monotonicity: Still take $g(n)$ any function with limit not infinity, for example $\arctan(x)$, $f(n) = \frac{g(n)}{n}$. By definition $f(n) = o(g(n))$. The difference $f(n) - g(n) \to 0 - \frac{\pi}{2} \neq -\infty$ so powers are not related as little-o.

*Update 2*

For both increasing $f$ and $g$ you can revert the counterexample $f(n) = -1/n^2$ and $g(n) = -1/n$.

If you put the requirement, that starting from some $n$ we have $f(n) \> 0$ and $g(n) \> 0$, the following is true. Assume $g(n) \not\to \infty$, that is $g(n) \to C \geq 0$. Then $f(n) = \alpha\_n g(n)$ where $\alpha\_n \to 0$ so $f(n) \to 0$. But $f(n) \> 0$ and thus must be decreasing at some point which violates the monotinicity requirement. By contradiction, $g(n) \to \infty$.

Take $\epsilon = \frac{1}{2}$ in the above, you have $f(n) - g(n) \leq -0.5 g(n) \to -\infty$ which proofs the claim.
> 1 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: Selecting optimal order of questions to minimize total time
Suppose there is a tutorial session at a university. We have a set of $k$ questions $Q = \\{ q\_1 \ldots q\_k \\}$ and a set of $n$ students $S = \\{ s\_1 \ldots s\_n \\}$. Each student has a doubt in a certain subset of questions, i.e. for each student $s\_j$, let $Q\_j \subseteq Q$ be the set of questions that a student has a doubt it. Assume that $\forall 1 \leq j \leq n: Q\_j \neq \phi$ and $\bigcup\_{1\leq j\leq n}Q\_j = Q$.

Now, a student leaves the tutorial session as soon as all the questions in which he has a doubt in have been discussed. Suppose that the time taken to discuss each question is equal, say 1 unit$^\*$. Let $t\_j$ be the time spent by $s\_j$ in the tutorial session. We want to find out an optimal permutation $\sigma$ in which questions are discussed $(q\_{\sigma(1)} \ldots q\_{\sigma(n)})$ such the the quantity $\Sigma\_{1\leq j \leq n}t\_j$ is minimized.

Intuitively it seems that we can greedily discuss the question that the most number of students (in the current iteration) have a doubt in. Is the greedy algorithm correct?

Sidenote: By the way, I thought of this question after an actual tutorial session, in which the TA discussed the questions in the normal order $q\_1 \ldots q\_n$ because of which many students had to wait until the end.

**Example**
Let $k=3$ and $n=2$. $Q\_1 = \\{q\_3\\}$ and $Q\_2 = \\{q\_1, q\_2, q\_3\\}$. We can see that an optimal $\sigma = \langle 3, 1, 2 \rangle$ because in that case, $s\_1$ leaves after $t\_1 = 1$ and $s\_2$ leaves after $t\_2 = 3$, so sum is 4.
However, if we discuss the questions in the order $\langle 1, 2, 3\rangle$, then $s\_1$ and $s\_2$ both have to wait till the end and $t\_1 = t\_2 = 3$, so sum is 6.

$^\*$You are free to solve the more general case where each question $q\_i$ takes $x\_i$ units to discuss!

# Answer
> 1 votes
Counterexample: Students are $x\_1\dots x\_n$ and $y\_1\dots y\_m$ and questions are $Q\_0, \dots Q\_m$. Students $x\_i$ only want $Q\_0$ to be answered while the $y\_i$ students want question $Q\_1,\dots, Q\_m$ to be answered.

Let's say you place $Q\_0$ as the $k^{th}$ question. Then the total time waited by students is:

* $L(n,m)=n(m+1)+m^2$ if $Q\_0$ is last
* $nk + m(m+1)$ if $Q\_0$ is $k^{th}$

Clearly, if you want to not put $Q\_0$ last, then you might as well put it first so that the cost is $F(n,m)=n + m(m+1)$.

Now $L(n,m)-F(n,m)=nm+n+mm-n-mm-m=nm-m=(n-1)m$ so that whenever $n\>1$ and $m\>0$, we'll have $L(n,m)\>F(n,m)$. So placing it first is better.

But your greedy algorithm would put it last if we take $m\>n$.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: Any notions of operations in basic postulates of lambda calculus
I am learning Lambda Calculus from the book by Hindley and Seldin . They start the formal postulation of lambda calculus as follow :

(a) all variables and atomic constants are λ-terms (called atoms);

(b) if M and N are any λ-terms, then (MN) is a λ-term (called an application);

(c) if M is any λ-term and x is any variable, then (λx.M) is aλ-term (called an abstraction).

In the second postulate $MN$ has been termed as a $\lambda$ term . How to define $MN$ , what does it mean ? Is it an operation? Is there any scope of defining operations in lambda calculus which are associative and/or distributive ?

# Answer
> 4 votes
You can think of application $MN$ as an algebraic operation, where the operator has been elided for convenience. Instead of $MN$ some people write $M @ N$, or even $$ apply(M, N) $$ So $apply(\cdot, \cdot)$ is a binary operation, and, as @chi points out, $apply(\cdot, \cdot)$ is is *neither* associative nor commutative. The precise nature of what $apply(\cdot, \cdot)$ does depends on exactly what $\lambda$-calculus you have in mind.

# Answer
> 3 votes
The application $MN$ is just syntax. On its own it does not mean anything.

There is, however, an intuition behind its semantics: $M$ is to be regarded as a function, and $N$ as its argument. Evaluating an application $MN$ simply corresponds to evaluating function $M$ at point $N$. This is formally defined through the $\beta$ reduction law.

Note that application is not associative or commutative. $MN$ is in general different from $NM$, and $MNO$ is an alternative notation for $(MN)O$, which is different from $M(NO)$.

This is not terribly different from any other programming language. Think about `f(x)` and `x(f)`, or `f(x)(y)` and `f(x(y))` in JavaScript, for instance.

---
Tags: lambda-calculus
---


# Question
Title: What is this type of consistency called in DataRetrieval?
I am trying to find the name of this feature that is implemented with SQL Databases:

Given a Record $R^1$ in table having two values for two different fields, e.g. Let value of field 1 $F\_1$ be $V\_1$, Let value of field 2 $F\_2$ be $V\_2$ A any query requiring records s.t. $F\_1 = V\_1$ should contain $R^1$. Also any query requiring records s.t. $F\_2 = V\_2$ should also contain $R^1$.

If a database does not have the above property then it definitely considered broken.

My question is what is the name for this kind of consistency?

# Answer
> 1 votes
I would call it expected consistency.

Unless you are just defining the $=$ operator.

When you get into transactions can have uncommitted or dirty value. By default $=$ will only match committed values but you can search on the uncommitted value. Look up ACID around data consistency.

Also careful with *any* as with an AND condition it needs to satisfy both so you may not get $R^1$ for $F\_2 = V\_2$ if another AND condition is not satisfied.

# Answer
> 0 votes
Your question's context is somewhat underspecified. Is there any form of distribution or concurrency going on?

In the absence of more context, I am assuming the most general context so I'd say this is strict consistency, the strongest form of consistency.

---
Tags: database-theory
---


# Question
Title: Number of times statement is executed in complex nested loop
I am trying to find out how many times the "statement" is executed by finding its formula based on these loops:

```
int s = 0;
for(int k = n; k > 0; k /= 2)
{
  for(int l = k; l < n; l++)
  {
    s++; // statement
  }
}

```

I have been stuck with this problem for a while since I couldn't really get the correct formula whenever I compared the result of my formula to the output s.

I started by doing this:

$$T(n) = \sum\_{k=1}^{\left\lfloor{\log\_2(n)}\right\rfloor + 1}\sum\_{l=k}^{n-1} 1$$

then eventually got this as a result:

$$T(n) = (1/2)(\left\lfloor{\log\_2(n)}\right\rfloor + 1)(2n - \left\lfloor{\log\_2(n)}\right\rfloor-2)$$

Does anyone know how to solve this kind of problem?

(This is a self-made problem btw since I kind of find analysis of algorithms fun)

# Answer
We can determine the *exact* value of $s$ as a function of $n$. For the sake of brevity, let $\lambda = \left \lfloor \lg n \right \rfloor$. We can replace the inner loop with:

> $s \leftarrow s+n-k$

At the end of the program we'll have:

$$ s= \sum\_{h=0}^{\lambda} n - \left \lfloor \frac{n}{2^h} \right \rfloor = n \left( \lambda + 1 \right) - \sum\_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor $$

Our problem is now rewriting the last term in a nicer form. . Certainly $n$ has a unique representation in base $2$, in particular it is true that

$$ n = \sum\_{u \in S} 2^u $$

for some $S \subseteq \mathbb{N}\_{\le \lambda}$.

Therefore we have:

$$ \sum\_{h=0}^{\lambda} \left \lfloor \frac{n}{2^h} \right \rfloor = \sum\_{h=0}^{\lambda} \sum\_{u \in S} \left \lfloor 2^{u-h} \right \rfloor = \sum\_{u \in S} \sum\_{h=0}^{\lambda} \left \lfloor 2^{u-h} \right \rfloor = \sum\_{u \in S} 2^{u+1} -1 $$

But then:

$$ \sum\_{u \in S} 2^{u+1} -1 = 2n - |S| $$

Piercing it all together, at the end of the program we will have:

$$ s = n \left ( \left \lfloor \lg n \right \rfloor - 1\right) + \textbf{1}(n) $$

where $\textbf{1}(n)$ is the Hamming norm of $n$, that is, the number of ones in its binary representation.
> 8 votes

# Answer
The outer loop runs about log n times.

The inner loop runs 0 times during the first iteration when k = n. All the other times, 0 ≤ k ≤ n/2, so the inner loop runs between n/2 and n times, so we have O (n log n).
> 1 votes

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


# Question
Title: Is that would be better approach to naive algorithm?
I was studying about naive pattern search algorithm and found that it requires two loops to match the pattern present in a string or not. That time an Idea stuck in my mind and I think it would be a better approach because I used only one loop to find out the pattern in string. Here is

Pseudocode

```
MY-PAT-ALGO(T[n],P[m])
[Here, T[n] is text string of length n and P[m] is pattern string of length m]
1. j <-- 0 , flag <-- 0
2. for i<-- 0 to n
   do
      if(T[i] = P[j])
         j<-- j+1
      else
         i<-- i-j
         j<-- 0
      end else-if

      if(j = m)
        flag <-- 1
        Print: "Pattern matched"
        break
      end if
  end for loop
3. if(flag = 0)
      Print: "Pattern not found"
4. Exit.

```

I want to know why it could be worst in comparison of naive approach. According to my test cases I found loop worst case is better than naive approach loop.

# Answer
> 0 votes
Let N be the length of the string you are searching
Let M be the length of the sub-string you are searching for

I bet you are using a definition of naive as searching the full M every time. The common definition is stop at the first mismatch. It is worse case $\mathcal{O}(mn)$.

A simpler and more efficient implementation compare to your code

```
int M = strlen(pat)
int N = strlen(txt)

/* A loop to slide pat[] one by one */
for (int i = 0; i <= N - M; i++)
{
    int j

    /* For current index i, check for pattern match */
    for (j = 0; j < M; j++)
        if (txt[i+j] != pat[j])
            break

    if (j == M)
         // done
}

```

# Answer
> 1 votes
It does have only one loop, but you are modifying the controlling counter ($i$). And because you reduce it by an amount proportional to the size of your pattern, I presume it is $\mathcal{O}(mn)$.

A test case could be $T\_n=a\_1a\_2a\_3...a\_{n-1}x\_n$ and $P\_m=a\_1a\_2a\_3...a\_{m-1}x\_m$ (Both are 'a's followed by an 'x'). Evidently the match will only be at the end, however it should find partial matchings at every previous positions. If you try for different $n$ and $m$ and the amount of comparisons are proportional to $mn$, then it is fundamentally the same as the naive approach.

If you want a better performance in perfect pattern matching, you could use the z-algorithm or the prefix-function (KMP is also for pattern matching, but it is space improved use of prefix-function). They work in $\mathcal{O}(m+n)$-time.

By the way, to compare algorithms (one common way but not the only one) is the Big-O Notation.

# Answer
> 1 votes
Your approach *is* the naive approach. Given a pattern of length $m$, you try to match characters $i$, $i+1$, ... $i+m-1$ of the string against characters $1$, $2$, ..., $m$ of the pattern. If they all match, you report success; otherwise, you start again at the start of the pattern and character $i+1$ of the string.

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


# Question
Title: Is the empty string ε in regular languages implicitly between any two characters in a string?
I'm wondering if this visualization makes sense with the definition of the empty string ε. I suppose it does because it doesn't seem to contradict its definition (ε is a string with no characters).

If that's the case, in finite state machines with empty transitions, is it always possible to assume ε is "before" the character *a* that should be read next, and take the empty transition instead?

If the next state also has an empty transition to another state, can I assume ε is "before" *a* again, even though the automata had just "consumed" ε in the last operation? In other words, can I assume there is an indefinite number of empty strings between any two characters in a string in a regular language?

# Answer
> 4 votes
The empty string is not there between every two characters implicitly but quite explicitly. In fact, there are *two* empty strings between any two characters, and between those two empty strings there is another, third, empty string. However, since empty strings are empty, them being there is like them not being there at all.

Let's consider this situation from a slightly more general point of view, but without using fancy words. In a sum $1 + 2$ is there a zero in between? Yes, since obviously $1 + 0 + 2 = 1 + 2$, and in fact also $0 + 0 + 1 + 0 + 0 + 0 + 2 + 0 = 1 + 2$, so that's a whole lot of zeroes. Is this sort of thinking useful? Well, in certain situations it is, for instance when we perform algebraic manipulations of numbers.

It might help to write strings as finite lists, i.e., instead of `aabab` we write $\[a, a, b, a, b\]$. With this notation the empty string is just $\[\]$, which is probably less confusing than the Greek letter $\varepsilon$. Concatenation then is actually concatenation (link together in a chain or series, according to my dictionary): $$\[a, a, b\]\[b, a\] = \[a, a, b, b, a\].$$ And now, it makes perfect sense to say that there are empty strings everywhere, like ghosts: $$\[a, a, b\]\[\]\[b, a\] = \[a, a, b, b, a\] = \[a, a, b\]\[b, a\].$$ Finite automata with silent transitions do *not* "consume $\varepsilon$". A silent transition happens when *no symbol is consumed*. You might think that "to consume no symbol" is the same as "to consume the empty string" but that is not so! An automaton (at least of the ordinary kind) *consumes one symbol* when it makes a transition, or it does not consume anything at all. An empty string is *not* a symbol, and therefore it cannot be consumed during the transition of an automaton.

More formally, the transition function $\delta$ has the type $S \times \Sigma \to \Sigma$, where $S$ is the set of states and $\Sigma$ is the alphabet. The empty string has type $\Sigma^\*$ and so it cannot be an argument to $\delta$. The types don't fit.

# Answer
> 2 votes
You may see the finite-length strings of an alphabet $\Sigma$ as the free monoid generated by $\Sigma$ with respect to composition, with $\varepsilon$ as the identity. Therefore, although it is not in general particularly useful, since by definition of identity $\varepsilon \circ A = A = A \circ \varepsilon$, you may certainly introduce any number of $\varepsilon$ in any position, without changing the original string.

However, bear in mind that the definition of a $\varepsilon-$NFA doesn't involve a "current state" but a rather a *set* of current states, I'm not sure your alternative definition would work as stated.

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


# Question
Title: How to calculate the number of tag, index and offset bits of 2 different caches?
I have two exercises:
1) A 128KB direct-mapped cache, with lines from 32bytes/lines and 36-bit address.
2) A 512KB 2-way associative cache, with lines from 64bytes/lines and 36-bit address.
For both exercises i have to find the number of bits needed for the tag,index and offset fields.
I tried to do both exercises and i found these results:
1)5 bit offset, 17 bit index, 14 bit tag
2)6 bit offset, 12 bit index, 18 bit tag
First exercise:
128KB = 217
32 bytes = 25 so 5 bit offset
17 bit index
36-5-17=14 bit tag
Second exercise:
64 bytes = 26 so i have 6 bit offset
512KB = 219
512/2 = 219/2 = 218 cache lines number
218/26= 212 so i have 12 bit index
36-(12+6)=18 bit tag

# Answer
Assuming that your machine is byte addressable`(1 word = 1 byte)`, Let us solve the problem step by step.

**1.**

`Physical address = 36 bits`. Since `32 bytes/line` and size of cache `line` = size of main memory `block`, this means `block offset = 5 bits`. Hence remaining `31 bits` is `block number( = tag + index)`.

number of cache lines = `128KB/32B`, therefore, `12 bits for index` and hence remaining `19 bits for tag`.

**2.**

`Physical address = 36 bits`. Since `64 bytes/line` and size of cache `line` = size of main memory `block`, this means `block offset = 6 bits`. `2-way` associative cache means that **two lines in one set**.

number of sets = `total cache lines/2 = (512KB/64)/2 = 2^12` , therefore `12 bits` for `set`, and hence `remaining 18 bits for the tag`.
> 1 votes

---
Tags: computer-architecture, cpu-cache
---


title: Could this be an NP-Complete problem?

text:
# Question
Title: Could this be an NP-Complete problem?
Consider the following problem statement:

> Given an initial number, you and your friend take turns to subtract a perfect square from it. The first one to get to zero wins. For example:
>
> Initial State: 37
>
> Player1 subtracts 16. State: 21
>
> Player2 subtracts 8. State: 13
>
> Player1 subtracts 4. State: 9
>
> Player2 subtracts 9. State: 0
>
> Player2 wins!
>
> Write a program that given an initial state, returns an optimal move, i.e. one that is guaranteed to lead to winning the game. If no possible move can lead you to a winning state, return -1.

This problem can be solved in pseudo-polynomial time using dynamic programming. The idea is just filling an array of length *n* (where *n* is the initial state) bottom up with the optimal moves, or -1 if no move leads to winning. This would take O(n * sqrt(n)) since for every number we need to consider subtracting each possible perfect square smaller than it (there are ~sqrt(n) of them). However, this is a pseudo-polynomial runtime complexity since the runtime actually scales exponentially with relation to the size of the input in binary (# of bits used to represent number).

Can anyone think of a polynomial algorithm for solving this problem? If not, could it be NP-Complete? Why?

# Answer
The sequence of losing positions can be found in the OEIS, A030193, as is the sequence of positions having Grundy value 1, A224839. The encyclopedia cites several relevant articles. Perhaps some of them discuss non-trivial algorithms for computing the sequence.
> 6 votes

---
Tags: complexity-theory, time-complexity, np-complete, dynamic-programming, pseudo-polynomial
---


# Question
Title: Choosing a production with $\lambda$ in Context-Free Grammars
Given the context-free grammar

\begin{align\*} & S \rightarrow AA \\ & A \rightarrow xA \\ & A \rightarrow B \\ & B \rightarrow yB \\ & B \rightarrow \lambda \end{align\*} What is the meaning of $\lambda$? $\lambda$ itself means the empty string and will match anything without consuming it, but in terms of the productions, how do you know which one to use? Do you use the last $B$ production only if $B \mapsto yB$ cannot be used? Or can both be used interchangably?

For example, parsing the string $xyy$ could give two different results:

Is there a formal way to prefer one of the two possible options? Which one is the "default"?

# Answer
I think you have understood this backwards. The CFG defines the language. All strings that can be derived by using the rules defined in the CFG are present in the language. The empty string itself is a terminal variable. You would substitute it in the string that you're deriving and is just empty.

What you are arriving at with the parse trees is called ***ambiguity*** of the grammar that you have defined. When the same string can be derived in more than one leftmost derivation, then the grammar is ambiguous. You could use two different substitutions and still arrive at the same string. So, yes, you could use either derivation, but the string itself does not change.

I would say the formal way to derive your string in exactly one particular way is to use a grammar without ambiguity.
> 2 votes

---
Tags: formal-grammars, parsers
---


# Question
Title: Minimum path - robot motion problem combined with freeze tag problem
Alright, I am not entirely sure if this is the right place to ask this, but here goes:

I have a map of coordinates of robots and obstacles. The first robot is awake from the start of the problem and it can wake up other robots on the map by walking next to them. Once a robot is woken up by another, it can also traverse the map and wake up other robots. The goal is to awaken all the robots using the minimum possible path.

Below I added an example of how a solution to a certain data set would look like.

I refrain from providing input/output files because I only want to ask for insights into and algorithm in pseudocode or even natural language, but if those would help I could add them as well!

Thank you very much in advance and should I provide any more info, do not hesitate to tell me!

EDIT #1: In the example, both robot A and robot B can traverse the path to C and D. The different colors show that in this example, robot B traversed the path to C and D. There are no cases where the robots hull interferes with the obstacles. The 'hull' can touch the obstacles. All robots have the same specifications. By minimum path I am trying to refer to the shortest time to wake up all the robots (i.e. time elapsed from when the first robot starts up until all robots are woken up).

# Answer
Define a fully connected, undirected graph $G$ so that there is a vertex for the initial position of each robot, and an edge between each two vertices whose length corresponds to the time for a robot to move from one position to the other. The edge lengths can be computed using the A\* algorithm or any other pathfinding algorithm.

Now I think you want a rooted spanning tree $T$ for the graph $G$, with the following properties:

* The root of the tree is the vertex that corresponds to the initial position of the awake robot.
* Every node of the tree has two children, except for the root, which has one child.
* The tree is a spanning tree, i.e., every vertex in $G$ appears somewhere in the three.
* The "duration" of the tree is minimal among all such trees.

Here we define the *duration* of a tree to be the maximum of the lengths of all path from the root to some leaf.

I don't know whether there is an efficient algorithm to find such a tree.
> 5 votes

# Answer
Note: This answer was written for a related problem where the goal is to minimize *total distance* travelled rather than elapsed time.

This looks a lot like a minimum spanning tree problem (as your tags indicate). If we can compute a minimum spanning binary tree, then you could do the following (note that computing such a tree might take a while).

1. Construct a complete undirected graph with a node for each "asleep" robot.
2. Compute the shortest paths between each pair of robots using your favorite collision free path planner (Dijkstra's in grid-world, RRT, FMT, etc). If both robots are asleep, put that weight on the edge between the corresponding nodes for the robots. Denote the length of the shortest path from the awake robot to robot $k$ as $w\_k$.
3. Compute the minimum spanning tree starting from each of the nodes, and denote the sum of the weights of the edges in the tree starting from the $k$th robot by $W\_k$. Return the tree with the smallest value of $W\_k + w\_k$ (which we'll call $T^\*$).
4. Send the first robot to the root of $T^\*$. As long as there are robots left to awaken: send the "just-awakened" robot down the "left" edge and the "awakener" robot down the "right" edge (define "left" and "right" however you like).

By property of your path planner, you know that you have collision free, shortest paths between each pair of robots. By property of your minimum spanning tree, you know that you have the shortest cumulative-distance paths to visit all robots.

You could define "left" and "right" to minimize the maximum distance travelled by any robot by defining an edge as "left" if its shortest path to a leaf node is longer than the "right" edge. This ensures that just-awakened robots (which have travelled less) take the longer routes.
> 1 votes

---
Tags: algorithms, graphs, minimum-spanning-tree, prims-algorithm
---


# Question
Title: Why do we use the log in gradient-based reinforcement algorithms?
I've been reading some papers on reinforcement learning.

$$\Delta w=\frac{\partial ln\ p\_w}{\partial w}r$$

I often see expressions, similar to the above one, where the weights (denoted by $w$) are updated following the partial derivative of the policy function (denoted by $p\_w$) with respect to its weights.

But why do we take the $\log$? What is its purpose?

# Answer
We often take the logarithm because:

1. Maximizing $\log \Phi(x)$ is equivalent to maximizing $\Phi(x)$, so in maximum-likelihood problems, we can maximize the log of the likelihood instead of maximizing the likelihood directly and the result will be equivalent.
2. The logarithm converts multiplication to addition, and the derivative of a sum is "nicer" than the derivative of a product. Products often arise when maximizing likelihoods, because the probability of something can often be written as the product of other probabilities (e.g., when we are calculating the probability of that multiple independent events all happen). The derivative of the product is ugly, but the derivative of the log of the product is nice and simple.
3. Gradient descent often involves maximizing a likelihood, so we'll need to take derivatives. The expressions get simpler/cleaner if we can take the derivative of the log likelihood instead.
> 7 votes

---
Tags: machine-learning, artificial-intelligence, reinforcement-learning, gradient-descent
---


# Question
Title: Distributive property with sum types and product types
In Philip Wadler's presentation, "Category Theory for the Working Hacker", something confused me. At about 30:52, he says:

> We need this additional construct which is called distributivity. Here it is, right? It just says "given a choice of an A or a C and a choice of a B or a C, we can get a choice of an A or a B **and** a C."

This is shown on the slide as:

> $$ (A + C)\times(B + C) \cong (A + B) \times C $$

Is this correct? I have the following doubts about it:

* I think that, in Boolean algebra, the distributive property would give $ (A + C)\times(B + C) = (A \times B) + C $.
* Given a choice of an A or a C and a choice of a B or a C, we might choose C both times, giving us only a C and a C. For example, in Haskell:

```
    data AorC = ACA A | ACC C       -- sum type
    data BorC = BCB B | BCC C       -- sum type
    data Prod = Prod AorC BorC      -- product type
    cAndC = Prod (ACC c1) (BCC c2)  -- choose type C both times

```

# Answer
> 4 votes
Polynomial types (those obtained through $+,\times,0,1$ and type variables) form a commutative semiring.

Basically, all the elementary arithmetic laws for $+$ and $\times$ hold as expected, up to (natural) isomorphism. These include commutativity, associativity, and distributivity of $\times$ over $+$.

More concretely, the distributive law is $$ (A\times C)+(B\times C) \simeq (A+B)\times C$$ and I think this was the law that Philip Wadler meant to show.

---
Tags: type-theory
---


# Question
Title: Minimizing transportation cost through a network, multiple source/sinks
I have the following problem:

> Inputs:
>
> * A finite collection $V$ of vertices
> * A metric cost function $c:V^2\to\Bbb R$ (interpreted as the edge cost of a complete graph on $V$)
> * An amount of resource $s:V\to\Bbb R$ on each vertex, satisfying $\sum\_{u\in V}s(u)=0$
>
> The problem is to determine a transfer function $f:V^2\to\Bbb R^{\ge0}$ such that $\sum\_{v\in V}(f(v,u)-f(u,v))=s(u)$ for all $u$, which minimizes $\sum\_{u,v}f(u,v)c(u,v)$.

The story to tell is that the points represent places with some amount of resource (if $s(u)$ is positive) or with some need of the resource (if $s(u)$ is negative), and $c(u,v)$ is the cost of sending a unit of resource from $u$ to $v$. We assume that every vertex can send resource to any other vertex, and the direct path is usually better than passing through an intermediate point. How do we minimize the cost of sending everything from where it is to where it is needed?

What is the name of this problem, and do there exist efficient algorithms to solve it? It seems similar to the minimum cost flow problem, but this only has one source and one sink, has maximum capacities for all the edges, and often needs multiple node paths for the resource, while here the direct path is always at least as good as a longer path (because the cost function is a metric).

# Answer
> 2 votes
This is an instance of the minimum-cost circulation problem. Replace each vertex $v$ by two vertices $v\_\text{in}$,$v\_\text{out}$. Each edge $(u,v)$ is replaced by $(u\_\text{out},v\_\text{in})$, with capacity (upper bound) given by $c(u,v)$ and lower bound 0. Then, add an edge $(v\_\text{in},v\_\text{out})$ with both the lower bound and upper bound set to $s(v)$.

There are polynomial-time algorithms for this problem.

---
Tags: algorithms, complexity-theory, optimization
---


# Question
Title: Minimum # toggle (3 consecutive elements) operations to convert ring A into ring B (rings made of Xs and Os: X->O and O->X)
There is a ring A and ring B made of Xs and Os. My aim is to convert A to B by using only the minimum number of `#` operations. When I do `#` on an element `i` of the ring, element `i-1`, `i` and `i+1` will be toggled. (toggled =\> X-\>O and O-\>X).

# Answer
> 1 votes
You can represent a ring as a $n$-bit string, where $n$ is the number of positions in the ring. Encode an X as 1, and encode a O as 0 (zero). That gives you a $n$-bit string, say $x$.

The # operation on index $i$ corresponds to xor-ing the string representing the current state of the ring with the string $c\_i = 0^{i-1} 111 0^{n-i-3}$. In other words, if the ring is currently $x$, then the # operation on index $i$ changes the state of the ring to $x \oplus c\_i$.

Suppose you're given two rings $x,y$ and you want to find a way to transform $x$ into $y$. Then all you need to do is find a subset of $c\_1,\dots,c\_n$ whose xor is equal to $x \oplus y$. This will be the solution to your problem. Can you see how to do that? Solution below (don't mouse over until you've thought about it for a while):

> You can find that solution using linear algebra in modulo 2 arithmetic (i.e., Gaussian elimination modulo 2).

---
Tags: algorithms, optimization
---


# Question
Title: The fastest way to check if a move is a winning move in Tic Tac Toe
I'm creating a tic tac toe game, there will be two players: `X` and `O`. `X` will be a human, and `O` is an AI which will always choose the best move to play. My board is an 11x11 board and the winning condition is 5 in a row.

How do I know if a board is at end state (where one player has won)? For the 3x3 board, you can do it easily with just a few steps. But for the larger board (11x11) and the winning condition is smaller than the dimension, it's way more complex. The best solution I have found is to check for each *n* x *n* (*n* is the winning condition) square for a winner. But that seems slow.

So here is my question: if you know the last move of a player, can you use that position to check if that player wins without checking every *n* x *n* square in the board?

# Answer
> 3 votes
Yes, you can do this more efficiently. If you have a board position and the last move made to get to that position, you can check whether the board position is an end state using the following insight:

The previous board position wasn't an end state. Thus, if the board is an end state, that can only happen because there's a 5-in-a-row that includes the square where the last move occurred.

So, if the last move was in square $s$, check whether there's a 5-in-a-row that includes square $s$. There are only 4 directions to check (horizontal, vertical, and both diagonals), and you can check each direction efficiently.

---
Tags: algorithms, complexity-theory, artificial-intelligence, search-algorithms
---


# Question
Title: Counting the nodes of a unidirectional graph
Suppose that we have the above graph. The graph is directed and is **unidirectional**; that is, we can only traverse it from *top* to *bottom*.

We want to update the count of the nodes such that the count of any given node indicates the sum of the count of the node itself and the previous nodes, avoiding any duplicate nodes.

### Example

For $ id:5 $ the count will be the sum of counts of $id:1,2,3,4$. So, the count will be calculated as $Count(id:5) = \sum Count(ancestors) + selfCount$.

So, the $Count(id:5) = 5$ in this case.

### Implementation that has been thought of

One such implementation could be traversal from top to bottom, and updating the count levelwise (*breadth-first search*).

We could then add the count of previous nodes, and subtract the count of the *LCA(Least Common Ancestor)* node.

### Example

So, if we have to find the count of node $id:5$, we would get the following count:

$ Count(id:5) = Count(id:5) + Count(id:2) + Count(id:3) + Count(id:4) - 2\*Count(id:1) = 1 + 2 + 2 +2 - 2\*1 = 5$

Here is the final graph that we are getting.

Another example:

$ Count(id:7) = Count(id:7) + Count(id:5) + Count(id:6) - Count(id:4) = 5 + 3 - 2 +1 = 7 $

### Problem

How do we remember the counts of ancestor nodes, when we are analyzing the counts of the current nodes?

It *could* be possible that the ancestor might not be immediately present, it could be far away at previous levels also.

Is there any algorithm that could solve the problem? I would really appreciate the help.

# Answer
> 2 votes
You can build a graph $G'=(V,E')$ that comprises the same set of vertices $V$ from the input graph $G=(V,E)$ and whose set of edges $E'$ includes an edge $(v,u)$ for every edge $(u,v) \in E$. That is, $G'$ is the same graph as $G$, but with the edges reversed; therefore, $G'$ is also topologically sorted (in the same way as $G$, but in the opposite direction). You are looking for the number of *successors* (+1) of every vertex in $G'$. This can be found using depth-first search, starting a new traversal from every vertex and counting the nodes that you find. The running time of this algorithm is $O(mn)$, where $n$ is the number of vertices of the graph and $m$ is the number of edges. D.W.'s answer provides some useful links with approaches with slightly better running times.

# Answer
> 1 votes
If the original value of count is 1 in every node, then this is the problem of counting the number of successors of each node in a dag. That problem is discussed in https://cstheory.stackexchange.com/q/553/5038, which cites the best algorithms known for this problem. For sparse graphs, it is hard to do much better than running DFS separately from each vertex, which has running time approximately $O(VE)$. For dense graphs, you can build an algorithm whose running time is $O(V^\omega)$, where $\omega$ is the exponent for fast matrix multiplication ($\omega \approx 2.8$ in practice).

If the original value of the counts can be different from 1, then your problem is https://cstheory.stackexchange.com/q/736/5038, which discusses the best running times known, and even mentions an approximation algorithm you could consider.

---
Tags: algorithms, graphs, data-structures
---


title: Probabilistic Substring Match

text:
# Question
Title: Probabilistic Substring Match
I'm looking for an algorithm that will help me determine substring matches at scale.

I have a pool of 100+ million "needles" (strings). I can do as much pre-processing on them as I want, and storage is cheap.

On detection side, I have both a very large pool (hundreds of TB) of strings to search for needles in, and also want to be able to stream detection as text comes in. So it's important that the detection be very fast (algorithmically). I can also pre-process this text as part of the detection, obviously.

I can store a copy of all needles, so a probabilistic algorithm would be fine (say, instead of the correct N strings, the algorithm returns some false positives -- I can always do a plain string search afterwards).

There is significant structure to the strings (they happen to be source code -- snippets on the needle side and files in the haystack).

Appreciate any thoughts on where to explore.

# Answer
> 2 votes
## Rabin-Karp

Rabin-Karp string search would be a good candidate, because it can use a rolling hash function.

You pick a segment length $\ell$. For each "needle", you hash its first $\ell$ characters, and store it in a hashtable keyed on the hash.

Then, as each character of text arrives, you compute the rolling hash of the last $\ell$ characters, look it up in the hash table, and possibly find one or more candidate needles that might match; then you test them directly.

This requires that the segment length be shorter than the shortest needle, but long enough to make hash collisions rare (i.e., so that the first $\ell$ characters of a needle mostly uniquely determines the needle). If you have a wide range of needle lengths, I suppose you could pick two segment lengths $\ell\_1,\ell\_2$, have two hash tables, and store each needle in appropriate hashtable according to its length.

## Aho-Corasick

The Aho-Corasick algorithm would also be a good candidate. It solves exactly this problem, and doesn't require any assumptions on the lengths of the needles.

You might also look at Commentz-Walter.

---
Tags: probabilistic-algorithms, substrings, longest-common-substring
---


# Question
Title: How to simplify sum of products boolean expression?
I started with this sum of products:

```
abc’d’ + abc’d + ab’cd’ + a’b’cd’ + a’bc’d + a’bcd + ab’c’d + a’b’c’d

```

I have been able to simplify to this:

```
b'c'd + abc' + a'bc + b'cd'

```

I can't seem to find a way to simplify it anymore. I have tried reading and watching a ton of tutorials but nothing is clicking.

Some things I have tried is finding the common values among the or expressions such c' or b'.

combining c'

```
c'(b'd + ab) + b'cd' + a'bc

```

combining b'

```
b'(c'd + cd') + abc' + a'bc

```

I get stuck with the simplification of combining b' or c'.

Can anyone provide any guidance as to what I am doing wrong or missing?

# Answer
From a Karnaugh map you can get a one group of 4s and three group of 2s. So you can reduce sum of 4 term in which three will have 3 literals and one with 2 literals. By doing it use K-map you will use few 1s for more than one terms so if you don't want to use a K-map just use idempotent rule($x = x + x$) and then simplify.
> 1 votes

---
Tags: logic, boolean-algebra
---


title: Bidirectional Encryption

text:
# Question
Title: Bidirectional Encryption
I would like a way to hide a piece of information from Alice and Bob. Let's say this piece of information lets Alice and Bob vote me off the island. If Alice had this information she could vote me off even if Bob did not want that. Likewise if Bob had this information he could vote me off the island even if Alice did not want that. However I'd like Alice and Bob to be able to vote me off the island if they both agree that its in their interest. So I'd like to give Alice and Bob a piece of information such that they can combine that information to vote me off the island.

One very simple method I thought of was to encrypt the information. Give the encrypted information to them. And give them each half the key that I encrypted that infomation with. I wasn't however sure how secure this was or what problems there might be with it. Additionally this is (deliberately) just like some of the naively proposed methods by which back doors might be added to encryption. I'm trying to consider what is wrong with this from a mathematical stand point. So does this method have some known theoretical issue (not issues in practice)? Is there an efficient algorithm that attacks it? If this method is a bad method then is there a good method? If not then is it possible for there to be a good method?

# Answer
That is called secret sharing.
The usual method for the 2-shares case is the method you thought of with the one-time pad.
Note that usual secret-sharing schemes provide no protection against fake shares.
> 3 votes

---
Tags: cryptography
---


# Question
Title: Proving property of a term using Induction
This is one of the example lemma that has been proved in TAPL book which I'm unable to grasp.

The objective is to prove `|Consts(t)| <= size(t)` where `t` is a term.

Now, `Consts` is a function defined like this:

```
Consts(true) = {true}
Consts(false) = {false}
... and so on

```

Similarly

```
size(true) = 1
size(false) = 1
... and so on

```

Now the proof in the book starts with something like "By induction on the depth of t" and then goes to prove the lemma. But I think I'm missing something here. Induction can be applied when we have to prove something over natural number. But there is no natural number involved in the above lemma. How come then the induction is applied ?

# Answer
A term is defined recursively. You can do induction on recursive types, using structural induction.

For instance, suppose we say that a term is something of the form

* $c$ (a constant), or
* $t\_1+t\_2$, where $t\_1,t\_2$ are terms.

Then structural induction is (loosely) similar to doing a proof by (strong) induction on the size of the tree. You prove that the property holds if the term has the form $c$ (that's the base case). Then, you prove that if the property holds for terms $t\_1$ and $t\_2$, then the property holds for the term $t\_1+t\_2$. You can probably see how to generalize this to terms whose syntax has a more complicated definition.
> 4 votes

# Answer
This type of induction is called structural induction on a term, or usual mathematical induction on the depth of a term (this is a natural number!).

More generally, well-founded induction is known. Both structural induction and mathematical induction are particular cases of well-founded induction.
> 1 votes

# Answer
> Induction can be applied when we have to prove something over natural number.

No. There are many forms of induction. In some areas of TCS, like programming languages theory, it is common to define sets/predicates/relations recursively (inductively), and then derive an associated induction principle from its definition. In some type theories, like CiC (the calculus of inductive constructions) this is also done inside the language itself!

For example, let $X$ be the smallest set satisfying the following inference rules:

1. a given constant $c$ belongs to $X$.
2. if $x,y \in X$, then $f(x,y)\in X$.
3. if $x \in X$, then $g(x)\in X$.

(The Knaster-Tarski theorem ensures there really is a smallest set satisfying $1,2,3$.)

Now, how to deduce an associated induction principle? Well, suppose $Y$ is another set satisfying $1,2,3$. Since $X$ is the smallest, we must have $X \subseteq Y$. That's the induction principle!

Let's rephrase the principle of induction over $X$. In order to prove that any $x \in X$ satisfies $x \in Y$, it suffices to prove the following:

1. $c \in Y$.
2. if $x,y \in Y$ (induction hypothesis), then $f(x,y)\in Y$.
3. if $x \in Y$ (induction hypothesis), then $g(x)\in Y$.

In other words, it suffices to prove that $x \in Y$ is a property "preserved by every rule".

As another example, if we define $\mathbb{N}$ as the smallest set such that

1. $0 \in \mathbb{N}$.
2. if $n \in \mathbb{N}$ then $n+1 \in \mathbb{N}$.

we get the usual induction principle on natural numbers.

On syntactic terms, we proceed similarly. The set of terms is the smallest set $T$ such that

1. constants/variables belong to $T$
2. if $t\_1,\ldots \in T$ then the expression $f(t\_1,\ldots)\in T$
3. etc.

(actual rules depend on the language you are defining)

Hence, to prove $p(t)$ holds for every term $t\in T$, by induction on $t$, all we have to do is to prove that $p$ holds for every constant/variable, that whenever $p(t\_1),p(t\_2),\ldots$ hold (induction hypothesis) we also have $p(f(t\_1,t\_2,\ldots))$, etc.

Inducing on the syntax of a term in this way is sometimes called structural induction.
> 1 votes

---
Tags: type-theory, induction, types-and-programming-languages
---


# Question
Title: Number of $1$'s in a Kolmogorov-random number
The problem I'm trying to tackle is to show that for a Kolmogorov-random number of length $n$, the amount of $1$'s in its binary representation is greater than $n/4$.

My only idea so far, is to use a Turing machine that takes indices of $1$'s as an argument and produces a binary sequence accordingly. Then, for instance, we could say the amount of ones is at least $\sqrt n$ as (roughly) $C\_U(n)\leq \sqrt n\log n \< n$ for $n$ large enough (each index is at most of length $\log n$). But this doesn't allow us to infer there are more than $n/4$ ones.

Is there any other way to generate some given number that would prove the statement in question?

# Answer
> 3 votes
I've found an answer which uses certain facts I was not aware of, but it's nevertheless really good.

Our machine $M$ takes the length of a number, $n$, and an index $j$ as an input (we encode the first argument in such a way so that there was no doubt where it ends, i.e. putting $0$ in between every digit and ending with $1$). $j$ denotes the $j$-th number with less than $n/4$ ones in a lexicographic order. The only problem we have now, is to evaluate how big $j$ can be.

We have $$j\_{\max}=\sum\limits\_{i\leq n/4}\binom{n}{i}$$

Often, when proving Second Shannon's Theorem, the above sum (even more general, with $\lambda n,\ \lambda\in (0,1/2\]$) is evaluated to be less than $2^{nH(\lambda)}$ with $H(\lambda)$ being the entropy of a non-fair coin throw.

Thus, we get $j\_{\max}\leq 2^{nH(1/4)}$. Since $H(\lambda)\leq 1$, a number with less than $n/4$ ones cannot be random besides finitely many cases.

More exactly, $$C\_U(x)\leq 2\log(n) + nH(1/4) + c$$ and this, for $n$ large enough, is less than $n$.

---
Tags: kolmogorov-complexity
---


# Question
Title: How to determine the carry vector of an integer addition
An integer addition can be represented as following:

$A + B = A \oplus B \oplus carry\_{vector}$

My question is how to determine the carry vector from $A$ and $B$ (not from the result)?

# Answer
The generation of the carry vector is a recursive process where the results of lower bits factor into the current carry output.

In general:

$$ Carry\_{n} = (A\_{n} \bullet B\_{n}) + ((A\_{n} \oplus B\_{n}) \bullet Carry\_{n-1}) $$ Note the $$ Carry\_{n-1} $$ term. The presence of this term means that carry data ripples through the adder chain.

This is the reason that so much effort was devoted in older computer implementation technologies to speeding up this process. This was done by brute force computing the carry for groups of bits in a process called carry look-ahead. Let's see this for two bits:

$$ Carry\_{n} = (A\_{n} \bullet B\_{n}) + ((A\_{n} \oplus B\_{n}) \bullet ((A\_{n-1} \bullet B\_{n-1}) + ((A\_{n-1} \oplus B\_{n-1}) \bullet Carry\_{n-2}))) $$

As bits get added, this gets messy in a hurry.

The classic 74181 ALU used this method for the 4 bits handled by the chip and was often paired with the 74182 Carry Look Ahead chip to speed carry propagation by performing the same between up to four chips. If more that 16 bits needed to be processed, another layer of 74182 was employed to speed up carry propagation in the lower layer. Thus an ALU with 16 74181s, 4 74182s, and one top level 74182 could process 64 bits with a delay of roughly 3 times the four bit ALU delay, instead of 16 times.

It is noteworthy though, that there is no easy solution to the problem. Each added bit of look ahead, increases the complexity of the carry generator.
> 3 votes

---
Tags: arithmetic, integers
---


# Question
Title: Combining Runtime Complexity Expressions with respect to Dijkstra
If I have an algorithm that fills out an $|V| \times |V|$ table with for loops and an $O(1)$ sub-problem **after** running Dijkstra twice (outside the loop), I think I get the following runtime complexity statement:

$$ O(\text{my algorithm}) = O(|V|\mathop{log}|V| + |E|\mathop{log}|V|) + O(|V|^2) $$

Assuming Dijkstra's is implemented with the binary heap.

---

My problem is that I realized that, worst case, $|E| = |V|^2$, and the statement rewrites as:

$$ O(|V|^2 \mathop{log}|V|) + O(|V|^2) = O(|V|^2\mathop{log}|V|) $$

But, the rest of the time, the algorithm is $O(|V|^2)$, especially if $|E| \< |V|$.

---

What is the correct runtime in this situation? And what is the reasoning behind the correct runtime statement? Because it seems like, to me, just listing out Dijkstra's runtime would be incorrect, since it is only true when the graph is dense... (can I add them together, like: $O(|V|^2 + |E|\mathop{log}|V|)$?)

# Answer
Yes, you can just add them together. If $|E|=O(|V|^2/\log|V|)$, then $O(|V|^2+|E|\log|V|)$ is the same thing as $O(|V|^2|)$, since the first term dominates. If $|E|=\Omega(|V|^2/\log|V|)$, then it's the same thing as $O(|E|\log|V|)$, since the second term dominates.

It might help your thinking to bear in mind that $f + g = O(\max\\{f,g\\})$.
> 2 votes

---
Tags: algorithms, time-complexity, shortest-path
---


# Question
Title: how does an object find the reference to its instance variables
I'm trying to understand how instance variables for a given object are stored for easy access later on.

For some background, I understand that if you have a reference to an array it is very easy for a computer to access any particular item in the array with an efficiency of $O(1)$ by just multiplying the index provided with the size of each item and adding that to the address of the array.

However it is not always meaningful to store things with just an index and so this is where things like `HashMaps` can come in handy because they allow someone to store a particular value based on a key and retrieve it in the same $O(1)$ efficiency.

So now imagine that we have some class that has many many instance variables

```
class myClass {
    int a1;
    int a2;
    int a3;
    ...
    int a500; //or some other really big number
}

```

and I write some code such as

```
myObject is new instance of myClass;
myObject.a5 = 123;
myObject.a450 = 70;
//etc

```

So my questions is:

How does the the `.a450`...etc get turned into an address? This type of access seems a lot more like the hashMap described above where a450 is a key that stores some corresponding value... however a hashMap really only attains that $O(1)$ access by careful maintenance of things such as the load factor. And to achieve the proper load factor you need to have a certain amount of empty items. There is also the issue that even though both hashMap and arrays have the same $O(1)$ access time... in practice the array will be much faster because there is no need to compute a hash function. It seems like this would not be an appropriate way to manage objects in any given language because if you have hundreds or thousands of such objects, then the overhead of having a hashmap would be very wasteful.

# Answer
Since the class is fixed in advance in C++-style languages, the offset to `a5` or `a450` is known in advance, in compile time. Each instance of the class contains a copy of each instance variable at a fixed location (relative to the address of the instance), so there is no "load factor" to talk about. So `myObject.a5` translates to something like `myObject[5]`.

Other programming languages such as python support dynamic addition of instance variables. In that case the instance variables are stored in a hash table, which as you mention has $O(1)$ amortized access time. (Perhaps some instance variables are stored in fixed locations, for the sake of optimization.)
> 2 votes

---
Tags: asymptotics, memory-access, object-oriented
---