# Question
Title: Two Minimax AIs playing against each other
I am trying to have my Minimax AI chess players play against each other.

I was a bit confused about an implementation detail.

Let's call `black` my first minimax AI chess player that plays first.

`white` is the other minimax AI that goes second.

My question s about the **turn**. Should `black` maximize and `white` minimize **OR** should they just try to maximize when at their respective turns, with the evaluation function flipped?

I have thought up of two ways to go about this. I have a feeling that they are doing the same thing, but just wasn't sure whether I am right or the two solutions are in fact doing something different.

### First solution:

Instantiate a MinimaxAI object for `black` and `white` separately. Make sure that `black`'s evaluation function is the opposite of `white`. For a simple example, the object `black`'s evaluation function is
`number of black pieces on board - number of whites on board`.

The `white` object will have an opposite evaluation function `number of white pieces on board - number of blacks on board`.

Now, when each object takes turns to call the same `get_next_move` method, they will both be the `maximizing player` of the minimax algorithm.

### Second solution:

Instantiate one Minimax AI object `ai` to be used by both the `black` and the `white` as they alternate turns. `black` and `white` will have the same evaluation function
`number of white pieces on board - number of blacks on board`

Assuming `white` always goes first in chess, when `white` calls `ai.get_next_move` with an even turn number, it will be given the `maximizing player` role. On the other hand, when `black` calls `ai.get_next_move` with an odd turn number, it will be given the `minimizing player` role.

(this is what I have so far)

I think both should result in the same behavior, but it is more of a feeling than an educated opinion. Please let me know if my feeling is actually correct or not. A semi-formal reasoning process will be welcome!

# Answer
First of all, note that in chess, white players plays first and it is a quite complicated game to build a AI for. The fact it exists several "draw" situations makes the evaluation function even more complicated to build. You may consider practice on another strategy game like checkers.

**The evaluation function**:

Most of IA are indeed based on an evaluation function. Let's talk about 2 opponents strategy games without random like chess. if we neglect "draw" situation, either you have a possible winning strategy, that will make you win whatever plays the opponent, either your opponent has one. When a "draw" situation exists, one player has a possible win strategy or both have a draw strategy.

All possible combinations are nevertheless impossible to explore and finding this strategy is matter of heuristic. The evaluation fuction is an heuristic to judge if a state of the game is likely to lead to a win. It can be a value the player tries to maximize.

Generally symmetric evaluation function like yours (nb white-nb black) works well for 1vs1 games. If the two players are equivalent AI, you will indeed have

```
eval player 1 = - eval player 2

```

Your second proposition is indeed the same thing. As maximizing $A$ is like minimizing $-A$. But for a proper simulation, I would rather prefer your first proposition that treat the 2 IA independantly.

Now about the "draw" situations, a player that can hardly win (having negative eval) can decide to look for a draw instead of a win. His evaluation function may therefore not be symmetric anymore. In the same way, a player dominating the game may use an assymetric evaluation to prevent a draw.

**Depth/Minimax**:

I think you misunderstood what is the **minimax** strategy. When it is your turn to decide what to play, you will explore some possibilies. You can for instance try all your possible moves and chose the one maximizing the evaluation function. This is a **depth 1** exploration.

You may also try all your moves with all the moves the opponent may do on his next turn. This is **depth 2** exploration. But in all these combinations, you have no information on what your opponent will play. The **minimax** strategy is to assume he will play the move maximizing his evaluation function, therefore minimizing yours.

For instance, let say you have 3 possible moves $M\_i$ Each leads to several possible subsequent moves $M\_{i,j}$ for your opponent. $E\_k$ = $evaluation(M\_k)$:

* $M\_1$ : $E\_1 = 3$, $E\_{1,j} = \[4, 1\]$
* $M\_2$ : $E\_2 = 5$, $E\_{1,j} = \[7, 2, -1\]$
* $M\_3$ : $E\_3 = -1$, $E\_{1,j} = \[-3, 0\]$

in $depth 1$, you pick $argmax\_i(E\_i)$, that is to say $M\_2$

in $depth 2$, you pick $argmax\_i(min\_j(E\_{i,j}))$, that is to say $M\_1$

You can of course go even deeper, applying minimax strategy on each opponent action. The deeper you go, the better is the heuristic approximation to find the best strategy. But the number of states to explore generally grows as a power law of the depth ($O(a^{depth})$). Thus, all the difficulty is to focus computation on interesting branch. You can have a look to some methods:
> 2 votes

---
Tags: search-algorithms, artificial-intelligence, search-trees, game-theory, board-games
---


# Question
Title: What's the difference between: operational, denotational and axiomatic semantics?
Recap of the terms from the dictionary:

* **semantics**: the study of meaning in a language (words, phrases, etc) and of language constructs in programming languages (basically any syntactically valid part of a program that generates an instruction or a sequence of instructions that perform a specific task when executed by the CPU)
* **operational**: related to the activities involved in doing or producing something
* **denotational**: the main meaning of a word
* **axiomatic**: obviously true and therefore not needing to be proved

Wikipedia's main article about: semantics.

Operational semantics:

This says that the meaning of a language construct is specified by the computation it induces. It is of interest **how** the effect of a computation is produced. My understanding of this is that this basically describes the meaning of all the operations involved in a program (from the most basic to the most complex).

Examples:

**arithmetic operations**: `1 + 1, 10 ** 2, 19 // 3` etc. In this case it analyzes the meaning of the steps involved in producing a result given `n operands` and `n operators`. This can be further boiled down to what each operand means (so in my examples each number is defined in the domain of natural numbers \[1, 2, ..., n\], etc.

**assignment operations**: `x = 5, y = 5 ** 2, z = 10 ** 2 // 3 * (99 + 1024)` etc. In this case it involves an evaluation of the value of the mathematical expression on the right and assigning it to the identifier on the left.

**augmented assignment operations**: `x += y, z *= t` etc. In this case it involves an evaluation of each identifier once, and performing an arithmetic operation first, followed by an assignment operation last. etc.

Denotational semantics:

This says that meanings are modelled by mathematical objects that represent the effect of executing the constructs. It is of interest **only** the effect of a computation, not how it is produced. My understanding of this is basically that it's related to mathematical functions, which take something as an input, do some computation which you don't care about and produce a result, which you care about. Since denotational means the main meaning, I take this as: the name of your functions/methods/identifiers should constrain the possible interpretations of what they do, ideally to be exact.

Examples:

`sort(iterable)`: should pretty much do what it says, take an unordered iterable as its input and return it ordered (you don't care how it does that under the hood)

`min(iterable)`: should take an array return the smallest value (you don't care how it does it)

`max(iterable)`: should take an array return the largest value (you don't care how it does it) etc.

Axiomatic semantics:

Some properties of the effect of executing the constructs are expressed as assertions. Some aspects of the executions may be ignored. My understanding of this is that it's related to boolean algebra and logic.

Examples:

`expr1 and expr2`: if `expr1 is False` then the entire boolean expression is `False` and it short-circuits and `expr2` is not evaluated

Or even compound statements:

```
if expr1:
elif expr2:
elif expr3:
else:

```

The effect is the result of executing the above construct and you assert its value based on whichever boolean expression yield true, the rest of them being ignored.

> Question:
>
> Are my examples for each category of semantics accurate and if not can one please provide some simple (not formal as Wikipedia does it with mathematical formulas, etc) examples of each semantic category? Examples that would match what we encounter in normal, day to day computer programs.

The gist of it is that semantic ties an identifier (word, symbol, sign) to its real meaning. The way it does this can be further boiled down to:

**Operational semantics** ties any type of operation (arithmetic, assignment, etc.) to the computation involved.

**Denotational semantics** ties identifiers to their meaning (so this is basically the most common one in programming). It's when you define a function it should do what it says. So for instance if you define a function dat says `add_numbers(x, y)` it should add `x` to `y` and not multiply them.

**Axiomatic semantics** ties the outcome of constructs to assertions. Basically boolean algebra (short-circuits in logical expressions, code branching (if-elif-else, switch-cases, etc).

# Answer
> 6 votes
I think your examples show you do somehow understand the basic points of the several styles of semantics. Still, note that the whole point of having a semantics of a programming language is to have a formal, mathematically rigorous description of the program behavior. That inherently involves math and several formulae -- one can't really do without math. Math is used as the foundation of every science, and computer science is no exception to this fact.

You are correct when you say that the denotational semantics for a program is, very roughly, a function from its input to its output. E.g. "this program computes the factorial function on naturals". Things start being more complex here when we want to model that the program might not terminate, or when the result is not a simple number but rather a record (an object, if you prefer) containing *functions*, which in turn might not terminate (or return another record which ...). The mathematical models which arise there become less and less trivial as soon as you allow for more complex data types (e.g. polymorphic functions).

Operational semantics of imperative programs roughly relates the initial variables state to the final one. E.g. "if we start the program with $x=3,y=4$ we end up with $x=7,y=2$". If the semantics is in "small step" style, we further get to see all the intermediate values of variables, as if we were running a debugger and stepping through each program line, so to speak. Such "small step" semantics allows to count, say, the number of multiplications performed by the program, which can not be seen in its denotation alone (however, note that, if we consider that count to be a kind of "observable output", we could define another denotational semantics returning that count as well -- the semantics styles are rather flexible).

Axiomatic semantics instead roughly works with set of states instead of single ones. It can express statements like "if we start the program with variables having any value satisfying $x\>y\>5$ we end up with $x\<100,y=x^2$". Note that we do not know the exact value of each variable here, but only a property that variables satisfy, expressed using logic.

That being said, if you want to achieve a solid understanding, you really have to read about the technical details: all the mathematical definitions and basic theorems. This is not hard, but is also not trivial either -- typically, a single university course can cover the basics of each style.

---
Tags: semantics, operational-semantics, denotational-semantics
---


# Question
Title: Can this equation be solved in polynomial time?
I came across a more general form of this question.

Can we find the value of variables in **polynomial time** ?

Let $m = n^{2}$, there are **$m$ variables ($x,y,z\ldots$)** in the equation and these $m$ values can only take positive integer values ranging from **1 to $n$.**

We have equation generator,
$$a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$$

for variables $x,y,z\in \\{1,2\ldots, n\\}$.

$f$ can be any thing such as $x, x^{2}, \log x$ etc.

Given that the constants are rational numbers and that there exists a solution, can we solve for the variables in polynomial time?

---

**Update**: Please note that I am not giving a single instance of $a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$, instead I am giving you the entire family of all possibilities of the above equation.

Basically I am giving you a black box, if you input $f$ it gives you corresponding $k$, given that $f$ is computable in polynomial time. We can do this multiple times. The goal is to solve for variables using this black box, in a polynomial time.

**So we have:**
1. The values of $m$ and $n$
2. The constants $a,b,c ...$
3. The equation generator $a\cdot f(x)+b\cdot f(y)+c\cdot f(z)+\cdots=k$

We can go on choosing different $f$ and the generator will give us corresponding equation, with a new $k$.

**Goal:** To solve for variables in the equation when $f(x) = x$

---

**Update 2**: For people wondering the origin of the question and its purpose. If the answer for this question is yes, then I think Sudoku can be solved in polynomial time. I tried to make use of the numerical property of Sudoku, that the sum of the entries of any row or column is known. By dealing each unknown cell as a variable we could treat each row and column as an equation. For a Sudoku of $n\*n$ it would result in $2n$ equations with $n^2-k$ variables where $k$ is the number of already filled cells. This is an underdetermined system of equations. We could represent this in a matrix and it can be reduced to Echelon form. This can be repeated for sum of squares, cubes etc etc of the values. If we could solve this we could solve Sudoku.

# Answer
> 1 votes
# Summary

Your problem remains NP-hard, despite the fact that the algorithm can choose the function $f$. Consequently, no, you should not expect a polynomial-time algorithm.

The problem is at least as hard as the subset-sum problem. Fortunately, subset-sum is one of the easier NP-hard problems, so if your problem instance is small enough, you might be able to use algorithms for subset sum to solve your problem.

# Problem statement

I'm going to reformulate your problem statement, so we are all on the same page:

*Input:* integers $m,n, a\_1,\dots,a\_m$; and access to an oracle, as follows:
*Oracle:* has secret values $x\_1,\dots,x\_m \in \\{1,\dots,n\\}$; when provided a function $f:\\{1,2,\dots,n\\}\to \mathbb{N}$, the oracle outputs the value $a\_1 f(x\_1) + \dots + a\_m f(x\_m)$
*Goal:* find $x\_1,\dots,x\_m$

# An algorithm

You could use algorithms for subset-sum to help solve your problem, using the following strategy.

Let $\delta\_1$ denote the function so that $\delta\_1(1)=1$ and $\delta\_1(j)=0$ for all $j \ne 1$. Send $\delta\_1$ to the oracle, and call the result $k\_1$, i.e., $k\_1 = a\_1 \delta\_1(x\_1) + \dots + a\_m \delta\_1(x\_m)$. Notice that $k\_1$ is a sum of the a subset of the $a\_i$'s, namely, those where $x\_i=1$. In other words, $k\_1=\sum\_{i \in S\_1} a\_i$ where $S\_1=\\{j : x\_j=1\\}$. So, feed $a\_1,\dots,a\_m$ and $k\_1$ into an algorithm for the subset sum algorithm, and ask it to find a subset of the $a\_i$'s that sums to $k\_1$. If this subset sum problem has a unique solution, then the result will tell you which $x\_i$'s have the value 1.

Next, let $\delta\_2$ denote the function so that $\delta\_2(2)=1$ and $\delta\_2(j)=0$ for all $j \ne 2$. Send $\delta\_2$ to the oracle, and call the result $k\_2$. Do the same thing, using a subset-sum solver to find a subset of $a\_i$'s that sum to $k\_2$; if this solution is unique, that will be the set of $x\_i$'s that have the value 2.

Repeat, for $\delta\_1,\dots,\delta\_n$, until you have learned all the value of all of the $x\_i$'s.

If you're lucky, the subset-sum problem has a unique solution at each stage, and after solving $n$ subset-sum problems you can read off the values of the $x\_i$'s. If you're unlucky, it has multiple solutions, and now you might need to consider all combinations of solutions to find a combination where the subsets are disjoint.

(Incidentally, once you've queried the oracle on $\delta\_1,\dots,\delta\_n$, you can predict the response of the oracle on any other function, so there's not much point in querying it again. This shows that $n$ queries to the oracle suffice; we'll never need more than that.)

# The problem is NP-hard

Here is a reduction to show that the problem is as hard as subset sum. In particular, we'll show that the special case of your problem where $n=2$ is as hard as subset sum. Suppose we have a subset sum instance, namely numbers $a\_1,\dots,a\_m$ and a target $t$. We'll show how to use any algorithm for your problem to solve this subset sum instance.

We will implement a sneaky oracle, which behaves as follows: when provided a function $f:\\{1,2\\} \to \mathbb{N}$, it returns the value

$$f(1) \cdot (a\_1 + \dots + a\_m) + (f(2)-f(1)) \cdot t.$$

Notice that the sneaky oracle doesn't have a particular set of values $x\_1,\dots,x\_m$ in mind. Nonetheless, if there is a subset of the $a\_i$'s that sums to $t$, the responses from the sneaky oracle would be equivalent to what we would obtain if we had an ordinary oracle where the $x\_i$'s were 2 for all $i$ in that subset and 1 otherwise; and if there is no subset of the $a\_i$'s that sums to $t$, the responses from the sneaky oracle are not equivalent to any ordinary oracle (for any value of the $x\_i$'s).

Now, ask the purported algorithm for your problem to work with this sneaky oracle and find values for the $x\_i$'s. If the algorithm for your problem finds a solution for the $x\_i$'s, that yields a solution for the subset sum problem (simply include the $a\_i$'s where $x\_i=2$ in the subset). If the algorithm for your problem doesn't find a solution for the $x\_i$'s, there is no subset of the $a\_i$'s that sums to $t$.

(Strictly speaking, this shows the case where $n=2$ is hard. However, one can show that increasing $n$ does not make the problem any harder. Thus, the case where $n=\sqrt{m}$ is also hard.)

---
Tags: algorithms, time-complexity, linear-algebra, mathematical-programming
---


# Question
Title: Confused about pumping lemma, What i'm missing?
When I apply pumping lemma on this language: ${L=\\{010^n:n\ge0\\}}$ over the alphabet ${\Sigma =\\{0,1\\}}$ I get that it is non-regular despite the fact that it is regular.

1. let ${n=4}$, then $w=010000$
2. $w=xyz$ , $ { \mid xy\mid \leq n} $ and $ {\mid y\mid \geq 1}$
3. $x=0$ , $y=10$ , $z=000$
4. let $i =2$
5. $xy^2z = 01010000$ $\not\in L$ so L is non-regular.

so, what I'm missing?

# Answer
> 0 votes
you can't claim to know how $w$ distributes.

you know that some $w \geq n\_0$ exists, in such a way it can be denoted as

$w=xyz$

$y \neq \epsilon $

$ |xy|\leq n\_0 $

and for every $i\>0: xy^iz \in L$

your error is that you claimed you know the distribution of $w$ to $x,y,z$. Namely, you fixed $y$ to be $10$

The language of course can be pumped, since it's regular. But for any $w = xyz, y$ must be a word of only $0$, since $1's$ cannot be pumped.

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


# Question
Title: How does a computer interpret real numbers?
I understand that the modern day digital computer works on the binary number system. I can also get, that the binary representation can be converted to *rational* numbers.

But I want to know how does the present day computational model interpret *real* numbers.

**For eg**:

> On a daily basis we can see that a computer can plot graphs. But here, graphs may be continuous entities. What is the mathematical basis, that transforms a discrete (or countable, at most) like the binary system to something mathematically continuous like a say, the graph of $f(x) = x$.

# Answer
> 13 votes
They represent continuous quantities with discrete approximations. Mostly, this is done with floating point, which is analogous to scientific notation. Essentially, they work with something like $1.xyz\times 10^k$, with some appropriate number of decimal places (and in binary, rather than decimal).

It's also possible to work with some irrational numbers directly. For example, you could create yourself an object called "$\sqrt{2}$" without particularly worrying about what it is, except that it obeys the usual arithmetic rules and that $(\sqrt{2})^2=2$. So then you could compute $$(\sqrt{2}-1)(\sqrt{2}+1) = (\sqrt{2})^2 + \sqrt{2} - \sqrt{2} - 1 = 2 - 1 = 1$$ exactly, as an algebraic fact that's not susceptible to rounding errors.

Note that, if you're plotting a graph on screen, regardless of how far you zoom in, you're plotting it as discrete pixels so using an appropriate number of significant figures basically gets you everything you need.

# Answer
> 8 votes
The real numbers are uncountable. The set of real numbers that can be represented in any way is countable. Therefore, almost all real numbers cannot be represented by a computer at all.

The most common method is to store floating point numbers, which are reasonably precise approximations to real numbers that are not excessively large or small.

---
Tags: mathematical-programming, mathematical-foundations
---


title: Word Problem over Finite Groupoids

text:
# Question
Title: Word Problem over Finite Groupoids
I'm struggling with an interesting problem from a chapter about Dynamic Programming in Skienas' famous "The Algorithm Design Manual". It's listed on the following web-page under number 8-22: http://www.algorist.com/algowiki/index.php/Divide-TADM2E#8-22

The problem asks you to write a polynomial-time algorithm using DP which solves a special case of the Word Problem over finite groupoids:

Given a finite groupoid $G$, a word $s$ on $G$ and an $x \in G$, find out whether it is possible to parenthesize $s$, such that its evaluation will yield $x$. Example from the book:

\begin{array}{c|ccc} & a & b & c \\ \hline a & a & c & c \\ b & a & a & b \\ c & c & c & c \\ \end{array}

For instance, consider the above multiplication table and the string $bbbba$. Parenthesizing it $(b(bb))(ba)$ gives $a$, but $((((bb)b)b)a$ gives $c$.

So far I managed to write a naive $O(n!)$ recursive algorithm in Python:

```
def i(x):
    return ord(x) - ord('a')

def mul(x, y):
    return groupoid[i(x)][i(y)]

# rewrite('abc', 1) = 'ac'
# rewrite('abc', 0) = 'cc'
def rewrite(word, i):
    return word[:i] + mul(word[i], word[i+1]) + word[i+2:]

def search(word, x):
    exists = (word == x)
    for i in range(0, len(word) - 1):
        if exists:
            break
        exists |= search(rewrite(word, i), x)
    return exists

word = sys.argv[1]
x = sys.argv[2]
exists = search(word, x)
print('Solution exists' if exists else 'Unsolvable')

```

Although we can memoize `search`, it won't give us polynomial time, since memoization space is of a factorial order. This is where I'm stuck.

The problem here is to somehow reduce the factorial search-space of all possible reductions from $s$ on $G$ to a polynomial search-space, which will depend only on $|s|$ and $|G|$. Can you please help me with that? Any other hints?

# Answer
This word problem over groupoid is a nice example to show the essence of dynamic programming, the recognition of the subproblems. In other words, how can we define the table or the multi-dimensional array that we should fill?

In general, the subproblems should represent the computations that will be repeated many times in a brute-force algorithm. The subproblems should be refined enough so that we can solve the larger subproblems from the solutions of the smaller subproblems. Please take a moment to appreciate how the subproblems are defined below.

### Compute $dp\[i\]\[j\]$, the set of all possible values of $x\_{i}x\_{i+1}\cdots x\_j$, where $1\le i\le j\le n$.

The goal element $a$ is a possible value of $x$ if and only if $dp\[0\]\[n\]$ contains $a$.

### How to compute $dp\[i\]\[j\]$?

The base case, $dp\[i\]\[i\]$ is the set of a single element, $x\_i$.

How about the case when $j\ge i+1$? Note a parenthesization of $x\_ix\_{i+1}\cdots x\_j$ means to parenthesize it into two parts, $(x\_i\cdots x\_t)(x\_{t+1}\cdots x\_j)$ for some $i\le t\lt j$, followed by a parenthesization of the front part $x\_i\cdots x\_t$ and a parenthesization of the behind part, $x\_{t+1}\cdots x\_j$. So $dp\[i\]\[j\]$ contains all products of the form $f\cdot b$, where $f$ is a possible value of the front part and $b$ is a possible of the behind part. Note both the front part and behind part are shorter than the whole, $x\_ix\_{i+1}\cdots x\_j$.

In other word, in order to compute $dp\[i\]\[j\]$, we can iterate $f$ through all elements in $dp\[i\]\[t\]$ and $b$ through all elements in $dp\[t+1\]\[j\]$, adding the product $f\cdot b$ to $dp\[i\]\[j\]$.

There are $n(n-1)/2$ choices for $i$ and $j$. There are at most $n$ choices for $t$. There are at most $k$ choices for $f$. There are at most $k$ choices for $b$. Depending on the implementation, it takes $O(k\cdot k\cdot k)$ or much less time to compute product $f\cdot b$ and add it to a set of at most $k$ elements. Hence the time-complexity of the algorithm is polynomial in $n$ and $k$.
> 6 votes

---
Tags: algorithms, dynamic-programming, search-algorithms, word-combinatorics
---


# Question
Title: An algorithm that find the max X/Y in a polygon in O(log n)
I got a task to create two functions one finds max $X$ and the other $Y$ in a polygon in $O(\log n)$.

The polygon is represented by an array of its vertices where each vertex is represented by its coordinates $(X,Y)$. We also know that the first vertex in the array has the smallest $X$ coordinate and after that, all the other coordinates are set in the array clockwise and also that all of them are different (all the $X$'s and all the $Y$'s are different)

I have the general idea.. using binary search but I'm not sure how to fully apply it.

How should move in the array while checking coordinates and yet keeping it in $O(\log n)$ complexity?

# Answer
Assume the polygon is a convex polygon; otherwise there might not be an $O(\log n)$ algorithm to find the maximum of X-coordinates or Y-coordinates.

First, let us handle the case of X-coordinate.

Let $x\_1, x\_2, \cdots, x\_n$ be the X-coordinate of the points. Since $x\_1$ is the minimum X-coordinate, that sequence is a bitonic sequence. Here are two nice answers to how to sort a bitonic sequence.

Next, let us solve the case of Y-coordinate, which is mildly more complicated.

Let $y\_1, y\_2, \cdots, y\_n, y\_{n+1}=y\_1$ be the Y-coordinate of the points. We can drill down into the following cases by comparing $y\_1$ against $y\_2$ and against $y\_n$.

* $C\_{\lt, \lt}$ when $y\_1\lt y\_2$ and $y\_1\lt y\_n$. Here $y\_1$ is the minimum.
* $C\_{\gt, \gt}$ when $y\_1\gt y\_2$ and $y\_1\gt y\_n$. Here $y\_1$ is the maximum.
* $C\_{\lt, \gt}$ when $y\_1\lt y\_2$ and $y\_1\gt y\_n$. Here Y-coordinates goes up from $y\_1$ to the maximum, then goes down to the minimum, then goes up to $y\_1$.
* $C\_{\gt, \lt}$ when $y\_1\gt y\_2$ and $y\_1\lt y\_n$. Here Y-coordinates goes down from $y\_1$ to the minimum, then goes up to the maximum, then goes down to $y\_1$.

The first two cases are bitonic sequences, which can be treated as before.

Let us check the case of $C\_{\lt, \gt}$; the case $C\_{\gt, \lt}$ can be handled similarly.

Let $y\_M$ is the maximum and $y\_m$ is the minimum, where $M\<m$. Given an index $1\<i\<n$, we can compare $i$ to $m$ and $M$ as follows:

* If $y\[i-1\] \< y\[i\] \< y\[i+1\]$ and $y\[i\] \> y\_1$, then $i \< M$.
* If $y\[i-1\] \< y\[i\] \> y\[i+1\]$, then $i = M$.
* If $y\[i-1\] \> y\[i\] \> y\[i+1\]$, then $M \< i \< m$.
* If $y\[i-1\] \> y\[i\] \< y\[i+1\]$, then $i = m$.
* If $y\[i-1\] \< y\[i\] \< y\[i+1\]$ and $y\[i\] \< y\_1$, then $i \> m$.

The above result enables us to cut the search intervals in half each time with 2 or 3 comparisons, thus ensuring an algorithm with $O(\log n)$ time-complexity.

---

**Exercise.** What about the case when we have a sequence of $n$ distinct numbers, in which there are $t$ local maximums and $t+1$ local minimums?
> 1 votes

---
Tags: algorithms, complexity-theory, time-complexity, computational-geometry, binary-search
---


# Question
Title: Floyd–Warshall algorithm on an undirected graph contains negative weight edges
According to this answer, the Bellman-Ford algorithm doesn't work when an undirected graph contains negative weight edges since any edge with negative weight forms a negative cycle, and the distances to all vertices in a negative cycle, as well as the distances to the vertices reachable from this cycle, are not defined. So in the all-pairs shortest path problem, can we say the Floyd–Warshall algorithm also doesn't work on an undirected graph contains negative weight edges for the same reason?

# Answer
> 2 votes
Perhaps it is useful to be more precise about what is meant by "doesn't work". If the directed graph contains a cycle of negative weight, then the notion of shortest path is not well-defined. Therefore, it makes no sense to run a shortest-path algorithm on such a graph. There's no hope for any algorithm to output the shortest path in such a graph, because there *is* no shortest path.

If you have an undirected graph with negative-weight edges, and you convert it to a directed graph in the obvious way, you'll end up with a directed graph that contains negative-weight cycles. Consequently, no shortest path algorithm has any hope of success at finding shortest paths: there is no directed path (in the directed graph). It doesn't matter what algorithm you are considering using.

Basically, the conversion from undirected graph to directed graph, in shortest path problems, is only correct if all weights are non-negative. If all edge weights are non-negative, then the shortest path in the undirected graph corresponds to the shortest path in the directed graph you obtain in this way. However, if the undirected graph has negative-weight edges, then there is no longer any such correspondence, so the conversion is not useful.

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


# Question
Title: general question amortized cost and worst case
lets say a data structure has operations called insert and delete both of which take O(log(n)) worst case. Suppose the amortized cost of insert is O(log(n)) and the amortized cost of delete is O(1).

Now if a sequence that has n delete operations performed on this data structure that has n elements currently, then what is the worst case? If delete takes O(1) amortized cost does this mean the worst case (not amortized) is O(n) for n delete's ?

---

I think no because it doesn't seem right but I'm not sure how to explain it

# Answer
> 2 votes
The answer hinges on the definition of *amortized cost*. Since you haven't given such a definition, let me assume that you are using the common definition.

Consider a data structure supporting operations $O\_1,\ldots,O\_m$. These operations have amortized cost $T\_i$ (where $T\_i$ could depend on parameters) if the total cost of a sequence of operations *run immediately after initializing the data structure* consisting of $c\_i$ many operations of type $O\_i$ is at most $$ c\_1 O\_1 + \cdots + c\_m O\_m. $$ This bound only works if we consider *all* operations done on the data structure since initialization.

In your case, you are only considering one part of the operations performed on the data structure, and so amortized cost doesn't apply.

---
Tags: algorithm-analysis, data-structures, amortized-analysis
---


# Question
Title: Why $\phi$ $\cdot$ R = $\phi$, rather than $\phi$ $\cdot$ R = R in Automata?
I understand that $\phi$ is a null symbol.
why concatenation of any language L with $\phi$ is $\phi$ rather than L ?

# Answer
Let us check the definition.

For two sets of strings $S\_1$ and $S\_2$, the concatenation $S\_1\cdot S\_2$ consists of all strings of the form $vw$ where $v$ is a string from $S\_1$ and $w$ is a string from $S\_2$, or formally $S\_1\cdot S\_2 = \\{ vw : v \in S\_1, w \in S\_2 \\}$.

What about $\emptyset\cdot R$?

Since there is no string in the empty set, we cannot find any string of that form $vw$ where $v$ is a string from the empty set. For example, you cannot form a mixed double in tennis if there is no male players. So $\emptyset\cdot R=\emptyset$.
> 4 votes

# Answer
You're probably confusing $\emptyset$, the langauge that contains no strings at all, with $\\{\varepsilon\\}$, the language that contains only the empty string.
> 4 votes

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


# Question
Title: Hitting probability of random walk within given number of steps
Given m,n dimensions of a 2D matrix; (i,j) initial co-ordinates; (x,y) final co-ordinates.

What is the probability of being at (x,y) after at most k steps if we start from (i,j) initially?

We can travel to 4 neighbors.

that is ( i , j+1 ), ( i , j-1 ), ( i-1, j ), ( i+1 , j ) if they are inside the matrix.

If there are only 3 neighbors which are inside the matrix then the probability with which we will go to that neighbor is 1/3(for each of the three).

How to solve this problem? I am able to find the solution for exactly k steps.

for exactly k steps problem, I make a matrix, dp\[m\]\[n\]\[k+1\]; initial all values are zero

except dp\[x\]\[y\]\[0\]=1;

dp\[a\]\[b\]\[q\]= weighted average of probablity of neighbours.

for example dp\[0\]\[0\]\[4\] = 0.5 * dp\[1\]\[0\]\[3\] + 0.5 * dp\[0\]\[1\]\[3\];

answer will be dp\[i\]\[j\]\[k\];

# Answer
For every point $(a,b)$ and number of steps $t \leq k$, compute inductively (i.e., using dynamic programming) the probability of reaching $(a,b) \neq (x,y)$ in $t$ steps without hitting $(x,y)$. Given this information, you can easily compute the probability of hitting $(x,y)$ in at most $k$ steps.
> 1 votes

---
Tags: dynamic-programming, shortest-path, probability-theory, matrices
---


title: L1 and Ln cache: when are they written?

text:
# Question
Title: L1 and Ln cache: when are they written?
I have been following the "High Performance Computer Architecture" course from Georgia Tech (also on YouTube), and unless I've missed something, I cannot see where the following has been explained:

If I have a multilevel cache, L1/L2/L3/Ln:

1) what decides what level of this hierarchy a block fetched from memory initially gets put in?

2) If I evict a block from L1, does that mean it gets moved to L2 (replacing a block from L2 depending on the replacement policy), and so forth for L2 to L3, and L3 to Ln, until the block evicted from the last level cache gets written to memory?

**PS** And yes, I have searched for this, so don't downvote assuming I haven't :)

**Update**

After the answer given below, I went back to the video course and found this. It seems to suggest that data is **initially fetched into the L2 cache**, then "fed" to the L1 cache. This also shows how, *without the inclusion bit set*, L1 and L2 can become "out of sync".

3) Is this generally what happens in all caches? IE if I have a 7 layer cache, will the block be fetched into L7, then fed L7-\>L6, L6-\>L5 ... and finally L2-\>L1? This seems like a lot of work...

4) Except in the situation shown in the linked video (if the caches get "out of sync" then certain data will only be available in one cache even though it started out in both caches), it seems that having the same data in multiple levels of the cache all the time (i.e. when the inclusion bit is set) is a waste; we have to copy it amongst all the levels. This can't be the case though, so what am I missing?

# Answer
> 5 votes
1) Usually any accessed data are saved into L1, independent whether they were previously available in L1, L2... or memory only.

For exclusive cache, data are stored ONLY in L1, for inclusive one, in the entire hierarchy. There are also mixed strategies. Also, some CPUs have "victim cache", which is extra cache level which gets ONLY data moved out of LLC (last level cache).

2) Yes, for write-back exclusive cache.

3) You misunderstood his explanation. He said that data are fetched and placed to both caches. Inclusion, btw, isn't the "bit set", but entire cache policy. The policy is built right into the hardware.

4) Exclusive cache better use precious space, but each time you have to bring new block into L1, you have to displace some block to L2, then some one to L3... and finally some one to memory. This means a lot of work. With inclusive cache, you just drop data from L1 cache, or replace older copy in L2 with newer copy displaced from L1.

As result, exclusive strategy is more optimal when adjacent cache levels has closer sizes (f.e. \<=4x) and inclusive is better when sizes are very different.

More info at en.wikipedia.org/wiki/Cache\_inclusion\_policy

---
Tags: cpu-cache
---


# Question
Title: Term for an A*-like pathfinding strategy where only the heuristic goal distance matters
I am trying to find a proper term for the A\*-like best-first pathfinding strategy where the node to expand next is the one with the least estimated distance from the goal, regardless of its distance from the source.

In *best-first* search algorithms, the node to expand next is the most promising one according to some evaluation function (which may take into account the current global knowledge). In the normal A\* algorithm, the evaluation function is the sum of the length of the currently know shortest path from the source and the heuristic estimate of the distance to the goal. Is there a standard term for a similar strategy where the evaluation function is just the heuristic distance to the goal?

I was thinking about *greedy* and *hill-climbing*, but *greedy* in this context seems to be just a synonym of *best-first*, and in what is commonly referred to as *hill-climbing*, there seems to be either no backtracking, or just one-step backtracking, that is, old unexpanded nodes are discarded at each step.

# Answer
This is greedy best-first search.
> 1 votes

---
Tags: terminology, shortest-path, graph-traversal, heuristics, a-star-search
---


# Question
Title: How to prove "if every subset of a set is a CFL, then the set must be regular."
> "*If every subset of a set is a CFL, then the set must be regular.*"

I want to prove it, could anyone please give me some hints?

# Answer
> 3 votes
Suppose that $L$ is a language such that each subset of $L$ is context-free. I claim that $L$ must be finite, and so regular. Indeed, otherwise $L$ would have uncountably many subsets, and so not all of them could be context-free (since there are only countably many context-free languages).

# Answer
> 3 votes
Lemma 1: *any language over a finite alphabet has either a finite or countably infinite number of elements.* Option one, your language is finite. Option two, your language is infinite, but you can still sort all the strings in "lexicographic order" (i.e. alphabetical order). This means they can be enumerated, so there are only countably many.

Lemma 2: *a countably infinite set has uncountably many subsets.* This is called Cantor's Theorem, and for the sake of time I'm not going to prove it here, but the proof is very elegant and can be found online.

Lemma 3: *the set of context-free languages is countable.* You can write down the grammar of any context-free language as a string of finite length (a CFG), and these strings can be sorted lexicographically.

Lemma 4: *if a language is infinite, it must have a non-context-free subset.* If a language is infinite, it has countably many elements, which means uncountably many subsets. This means there are more distinct subsets than context-free languages. So some of these subsets must be non-context-free.

Lemma 5: *if a language is finite, it is regular.* You can make a regular expression for it by just union-ing together a whole lot of singleton strings.

Theorem: *if a language has no context-free subset, it must be regular.* The contrapositive of Lemma 4 means this language must be finite, and so Lemma 5 means it's regular.

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


# Question
Title: DFA, lower bound on number of states, language with primes and remainders
This is an exercise from old exam on formal languages that I don't know how to solve:

Let $p \ge 5$ be a prime number and $L\_p$ be a language of words over $\\{0,1\\}$ that read in binary from right (i.e. from least significant bit) give a number that gives remainder modulo $p$ from the set $\\{1,2, \ldots, \frac{p-1}{2}\\}$.

How to show that:

> Every DFA recognizing $L\_p$ has at least $2p$ states.

?

One fact that I know of and is somehow related (has DFA and primes in the statement) is:

> Any DFA recognizing language $\\{0^n : n \text{ is not divisible by } p\\}$ has at least $p$ states.

This can be seen by observing that the language is infinite, hence any DFA must have a reachable cycle, from which some accepting state is reachable. And if that cycle had less than $p$ states, then because any number smaller than $p$ is coprime with $p$, we could loop sufficiently many times in that cycle and arrive at the aforementioned accepted state with a word $0^{kp}$ for some natural $k$ - a contradiction.

Maybe it's possible to use this fact, or alter this proof somehow to make it fit for the theorem with $L\_p$?

--**EDIT**

I'm trying to solve it by Myhill-Nerode theorem, as Yuval Filmus suggested.
So, the goal is to find $2p$ words $w\_1, \ldots, w\_{2p}$ that will be pairwise distinguishable. I don't have a good intuition here but let's define $w\_i$ to be $rev(bin(i))$ for $i = 1, \ldots, 2p$ ($bin(a)$ gives a binary representation of number $a$, and $rev(w)$ reverses the word $w$). Let's take any $i \neq j$ that both belong to $L\_p$, or both don't. Now the task becomes a bit number-theoretic -- adding a common suffix $x$ to these words changes their values such that $val(w\_ix) = val(w\_i) + 2^{length(w\_i)-1}val(x)$ (and similarly for $j$), where $val(\cdot)$ gives value of binary string reading from LSB (so e.g. $val(01) = 2$).
Now the question is: can we always find an appropriate $x$ that makes one of $w\_ix, w\_jx$ belong to $L\_p$, and the other not? I don't know the answer to this question. Maybe I should use the fact, that $2$ is a multiplicative generator modulo $p$?

# Answer
> 1 votes
For a binary string $x$, let $N(x)$ be the value of the number when read LSB first. Then $N(xy) = N(x) + 2^{|x|} N(y)$.

Now consider any $P \subseteq \mathbb{Z}\_p$. For any $x$, $N(xy) \bmod p \in P$ iff $N(x) + 2^{|x|} N(y) \bmod p \in P$. This condition depends only on $N(x) \bmod p$ and $2^{|x|} \bmod p$, i.e. on $N(x) \bmod p$ and $|x| \bmod \operatorname{ord}\_p(2)$ (here $\operatorname{ord}\_p(2)$ is the smallest exponent such that $2^o \equiv 1 \pmod{p}$).

As $x$ goes over all binary strings, $(N(x) \bmod{p}, |x| \bmod\operatorname{ord}\_p(2))$ goes over all possible $p \cdot \operatorname{ord}\_p(2)$ values. One way to see this is to take zero paddings of strings representing $0,\ldots,p-1$.

Let us now consider the particular $P$ stated in the question. Since $p \geq 5$, $2^2 \not\equiv 1 \pmod{p}$, and so to prove the claim, it suffices to show that the equivalence classes $\\{(a,1),(a,2) : a \in \mathbb{Z}\_p\\}$ are all different.

Consider any two equivalence classes $(a\_1,b\_1),(a\_2,b\_2)$. If exactly one of $a\_1,a\_2$ is in $P$, then there is nothing to do. Suppose first that $a\_1,a\_2 \in \\{1,\ldots,\frac{p-1}{2}\\}$. If $b\_1 = b\_2$ then $a\_1 \neq a\_2$. Without loss of generality, $a\_1 \< a\_2$. Therefore we can find $n$ such that $a\_1 + nb\_1 = \frac{p-1}{2}$ while $a\_2 + nb\_2 \notin P$. If $b\_1 = 1$ and $b\_2 = 2$ then there is a range of $\frac{p-1}{2}$ consecutive values of $n$ such that $a\_1 + nb\_1$ goes over all of $1,\ldots,\frac{p-1}{2}$. For the same values of $n$, the expression $a\_2 + nb\_2$ goes over $\frac{p-1}{2}$ values in jumps of $2$; it is not hard to check that not all of them can belong to $P$.

We leave the case $a\_1,a\_2 \notin P$ to the reader.

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


title: Regular expressions for some languages

text:
# Question
Title: Regular expressions for some languages
1. Set of strings over $\\{0,1\\}$ having at least two occurrence of the substring 00.
2. $\\{a^n b^m : n ≥ 4, m ≥ 3\\}$.
3. Set of strings over the alphabet $\\{a,b,c\\}$ containing at least one $a$ and one $b$.

# Answer
> 0 votes
Well, think about what's necessary in each case.

In the first case, you need two instances of $00$, and you don't care what else is there. If those instances can't overlap, this would be $(\cdot^\*) 00 (\cdot^\*) 00 (\cdot^\*)$, since $(\cdot^\*)$ means "anything at all, including nothing". If the instances can overlap, you should union in $(\cdot^\*)000(\cdot^\*)$, to catch cases like $000$.

In the second case, you need at least four $n$s, then at least three $m$s. So just specify that: $nnnn(n^\*) mmm(m^\*)$.

---
Tags: automata, regular-expressions
---


# Question
Title: How to do if a potential function Does not work? Amortized analysis
Here is an example taken from CLRS.

q)Consider an ordinary binary min-heap data structure with n elements supporting the instructions INSERT and EXTRACT-MIN in O(lg n) worst-case time. Give a potential function Φ such that the amortized cost of INSERT is O(lg n) and the amortized cost of EXTRACT-MIN is O(1), and show that it works.

$\Phi(H) = 2 \cdot (size of heap = n) = 2n$

insert:

the amortized cost has the formula

$a\_n = c\_n + (\Phi\_{n+1}) - \Phi\_n$

$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$

holds ?

$a\_n = c\_n + (\Phi\_{n+1}) - \Phi\_n$

$= log(n) + 2(n+1) - 2n = log(n) + 2 = log(n)$

delete is a bit different because after operation n goes down by 1 hence

$a\_n = c\_n + (\Phi\_{n+1}) - \Phi\_n$

$= log(n) + 2(n) - 2(n+1) = log(n) - 2 = log(n)$

so delete is obviously wrong since its not O(1) but insert gave correct one. How do I properly show a potential function being incorrect? Is it enough to just show this? Note: I'm not looking to solve the above question just looking how to disprove potential functions.

# Answer
> 0 votes
When you delete, your $actual$ $cost$, or $c\_n$ by your notation, is $log(n)$.

it means you want: $\Delta \phi = \phi\_{n+1}-\phi\_n \approx -log(n)$

Its not hard to find such potential function that satisfies both:

try $\phi = nlog(n)$

for insert:

$Cost\_{insert} = log(n) + (n+1)log(n+1) - nlog(n)$

$= log(n)+log(n+1)+nlog(n+1)-nlog(n) = O(log(n))$

$Cost\_{delete} = log(n) + (n-1)log(n-1) - nlog(n) $

$= log(n)-log(n-1)+nlog(n-1)-nlog(n) $

$\leq (log(n)-log(n)) +(nlog(n)-nlog(n)) = O(1)$

All potential functions that satisfy $\phi(i) \geq 0 $, $\phi(0)=0 $ are correct, they just may not prove the amortized time you have in mind.

---
Tags: amortized-analysis
---


# Question
Title: Global indexing of shared nodes in parallel
Consider a tiling of quadrilaterals in 2D that provide complete coverage of a particular region. N quadrilaterals are distributed across many parallel threads, typically in a way to keep groups of quadrilaterals together. In each quadrilateral we distribute np nodes, with some nodes located along the boundary of the quadrilateral. This gives rise to a 2D indexing of nodes (i,j) where i=1,..,N is the quadrilateral index and j=1,..,np is the local index of the node within that quadrilateral.

We now wish to develop a map from (i,j) to a global index of nodes that accounts for coincident nodes that may exist along the boundary of the quadrilaterals (e.g., see attached image of two quadrilaterals with three shared nodes -- np=9 but global index goes from 1..15). In serial, a simple algorithm would be as follows:

```
let k = 1
let X = map from local index (i,j) to global index k
for each quadrilateral i
  for each node j in quadrilateral i
    if (i,j) is coincident with a node (i',j')->k' in X
      assign index k' to (i,j)
    else
      assign index k to (i,j) in X
      k = k + 1

```

In parallel, only elements of this map that are associated with quadrilaterals on the local thread need to be stored. We can further assume that each thread has complete knowledge of the quadrilateral indices and nodes of its own quadrilaterals and those quadrilaterals and nodes that are spatially adjacent.

So the question is: Is there a parallel algorithm that performs better than the serial algorithm above?

# Answer
Assume you have an array (random access sequence) of tuples `<q, j, x, y, first, k_tmp, k>` where `q` is the (integer) identifier of a quadrilateral, `j` is the local index (within the quadrilateral) of a node, `x`, `y` are the coordinates of a node contained in quadrilateral `q`, and `first`, and `k_tmp`, and `k` are fields to be filled in later.

1. sort the array lexicographically on `x`, then `y`, then `q` (i.e. all the array elements corresponding to the node at `x`,`y` will be adjacent in increasing order by `q`). The sort can be done in parallel. See for example Blelloch, Leiserson, Maggs, Plaxton, Smith, and Zagha, "A comparison of sorting algorithms for the connection machine CM-2", *Proc ACM Symp Parallel Alg and Arch*, SPAA-3:3-16, 1991, or Arpaci-Duesseau, Arpaci-Dusseau, Culler, Hellerstein, and Patterson, "High-Performance Sorting on Networks of Workstations", *SIGMOD Conference*, 1997:243-254.
2. foreach element `e` of the array, in parallel:
    * `array[e].first = if (array[e].x = array[e-1].x and array[e].y = array[e-1].y) then 0 else 1`
3. resort the array lexicographically on `q`, and `j`.
4. calculate `array[].k_tmp` as the parallel prefix sum (sometimes called a "scan" operation) of the `array[].first` fields. A good paper on parallel prefix sum is Chatterjee, Blelloch, and Zagha, "Scan Primitives for Vector Computers," *Proceeedings of Supercomputing*, 1990:666-675.
5. resort the array lexicographically on `x` and `y` and `q`.
6. calculate `array[].k` as the *segmented copy scan* of `array[].k_tmp` using `array[].first` as the bit vector to determine the segment boundaries (see Section 3.2 of the paper by Chatterjee, Blelloch, and Zagha). Briefly: The segmented copy scan will use `array[].k_tmp` if `array[].first` is 1, else it will use the `array[].k_tmp` from the first element to the left where `array[].first` is 1.
7. you can now resort the array lexicographically on `q` and `j` and the `k` field should be correct for each array element.

The fact that we sorted the array back and forth and back and forth seems to indicate that we should probably, in practice, use two data structures (one sorted on `q` and `j` and one sorted on `x` and `y`) with pointers back and forth between them.
> 1 votes

---
Tags: algorithms, computational-geometry, parallel-computing
---


# Question
Title: Why is Byzantine Generals Problem with traitors possible?
My question is what makes the Byzantine Generals Problem possible to solve in some cases where traitors exist, for example in the case where there are 4 generals with 1 traitor?

If the generals must either all attack or all retreat at the same time, then surely the traitorous general can simply say "yeah sure we'll attack" and then retreat as the other 3 generals plunge into their deaths.

I suspect the answer has something to do with different variations of the problem, but I was unable to find any other definition for the Byzantine Generals Problem other than "all must either attack or retreat". Almost all of the search results are blockchain related advertisement, and the Wikipedia article doesn't provide a different definition for the goal of the generals.

# Answer
Quoting from the abstract of the original paper introducing the Byzantine Generals problem (with my emphasis):

> The problem is to find an algorithm to ensure that the *loyal* generals will reach agreement.

If you read further in the paper, they reduce the problem to agreeing on a single bit: "Attack" or "Retreat". The question is can the *loyal* generals reach consensus *amongst themselves* when they don't know who the traitors are.

So for your proposed scenario, as far as the Byzantine Generals problem is concerned, the only question is whether all the loyal generals can agree on the plan, not whether the plan is workable. At any rate, "all attack" either means "all \[loyal generals\] attack" which is essentially what would be produced by a Byzantine fault-tolerance algorithm, or it means "all \[generals, loyal and traitorous alike,\] attack" which would simply be silly. In this thought experiment the generals *know* that there are potentially traitors so they would presumably not propose a plan that only works if there are no traitors. What is actually being agreed upon, e.g. the "goal", is outside the scope of the Byzantine fault-tolerance algorithm, of course. The algorithm doesn't care whether the question is "should we attack or retreat?" or "should we choose pink or chartreuse for the new standard?"
> 2 votes

# Answer
```
If the generals must either all attack or all retreat at the same time

```

That's a common mistake, but the correct is:

```
2/3 of the generals must either all attack or all retreat at the same time

```

It is not "*all or nothing*", but "***2/3*** *or nothing*" (or more).

In your example, we have 4 loyal generals and 1 traitor. This means 4 generals need to attack at the same time in order to succeed (3.33 generals, rounded to 4).
> 0 votes

---
Tags: byzantine
---


# Question
Title: Which algorithm can I use to allocate human resources?
I have to manage shifts of a variable number of people inside several rooms for a week.
Every shift must be at least 1h long and the number of hours per person for the week should be nearly the same for everyone.
Every person could ask for specific shifts and this could be accepted if a suitable solution can be found.
I could have other constraints, but let's face this very basic situation.

Now the questions:

1. Which algorithm should I study and use?
2. Is there some free library I can use for this purpose?
3. Is there something I can use for C#?

# Answer
> 7 votes
Since Vince asked me to publish my solution, I decided to write this long post.
Please bear in mind that this code is really really basic and absolutely not optimized, written as fast as possible to perform some test.
Credits for Hungarian algorithm code must be done to *vivet*.

## PURPOSE

I need to create shifts for M workers (variable number each week) on N slots (usually 50 each week, but sometimes some slot could be unavailable).
Each worker can suggest slots he wants to take and others he can't absolutely take and, if possible, these requests should be taken in account.

## GENERAL IDEA

Given that creating costs matrix for Hungarian solver can be a pain, I decided (just a quick solution) I can create text files for each worker to report his request and one file for unavailable slots.
All these files must be in the same folder.

## FILES STRUCTURE

A single text file must have as many rows as daily slots (usually 10) and as many columns as working days (usually 5).
Each *cell* must contain a preconfigured char:

* **O** means worker really needs that slot assigned
* **o** means worker would like to have the slot assigned
* **-** means no preference on that slot (it's the default naturally)
* **x** means worker would like not to have the slot assigned
* **X** means worker can't work on that particular slot

A sample could be

```
X x - - O
X x - - O
- - - - O
- - - - -
- - - - -
- - - o -
- - - o -
- - - - -
- - - - -
x x x x x

```

Unavailable slots file **must** have a well defined name (always the same) and its content will have the same structure of workers files. Naturally each *cell* having a value different than **-** means that slot is not available to workers.

## CODE

Source code can be found here.
Unfortunately .NET Fiddle uses framework 4.5, so program can't be compiled and run online due to the fact I use a newer framework (4.7.1).
Also consider my real code is organized into several files!

It works and it's fast, so I'm completely satisfied with this part.

## A STEP FURTHER

First problem solved, pretty good. But now I have to face the next one: I have several locations to assign workers shifts to and these locations share the same working hours.
A first attempt was to raise the number of columns on each file: cols 1-10 are for the 1st venue, cols 11-20 for the 2nd and so on.
Code works without any change and Hungarian algorithm processes data in a while, good; but, as expected, I end having overlapping shifts for the same workers on multiple venues (it's random, but always happens).
I could solve this problem by computing 1st venue, then changing each worker requests denying slots already given in the 1st venue before computing the 2nd one; not exactly the best way I'm sure, just an idea I had, and I'm not sure I can always find a solution.

## OTHER OPTIMIZATIONS

I could also think about adding other rules (e.g. if possible worker should have max 2 ranges in a day (avoiding for example solutions having slots 0, 2, 4, 6 and 8 and preferring slots 0-2, 6-8 instead) and limits, but this goes too far from the starting question, so it will be something I'm asking in future and I'm quite sure it could need some more complex algorithm or libraries (e.g. ORTools by Google) I'm searching/studying.

# Answer
> 6 votes
For the sake of completeness (since Vince has given you good help already, and it seems like you've got a program that works):

This is known as the *assignment problem*: given some set of workers and some set of shifts, where each worker might have preferences about which shifts they take, how can you find the optimal schedule?

The standard solution to it is called the *modified Hungarian algorithm*: it wasn't actually developed in Hungary, but it was based on the earlier work of some Hungarian mathematicians. This is the algorithm implemented in the other answer, and it runs in $O(n^3)$ time (though for any practical purposes you won't really have to worry about that aspect).

---
Tags: algorithms, optimization
---


# Question
Title: Check if a lambda constructor is well-typed
In basic type inference for -calculus with parametric polymorphism à la Hindley–Milner, when can we say that we cannot give a type to a lambda constructor? For example $$(λx.λy.y(x\ y))(λz.z)$$

# Answer
A term $M$ is well-typed if and only if there is a type derivation that leads to a judgement of the form $\Gamma \vdash M : \tau$ for some context $\Gamma$ and some type $\tau$. (I use the word “type” in its general sense which can include quantified variables; in the terminology commonly used with Hindler-Milner, that's a *type scheme*.) So, to prove that you cannot give a type to a lambda term from first principles, you prove that there is no type derivation that leads to such a judgement.

Hindley-Milner has a nice property in this respect: it's *syntax-directed*, i.e. it's presented as a set of deduction rules such that for any term, there is a single rule that can be used to end a deduction of this term. (Being syntax-directed is actually a property of a presentation of the type system, not a property of the type system. In this post, I use the classical syntax-directed presentation which builds generalization into the let rule, rather than having a separate rule for generalization.)

Another nice property (shared by almost every type system) is that unused variables can always be removed from the context. So for example, if $(\lambda x y.y (x y)) (\lambda z.z)$ is well-typed, it must have a type derivation ending with the App rule and, since the term has no free variable, an empty context: $$ \dfrac{\vdash (\lambda x y.y (x y)) : \tau\_1 \to \tau\_0 \qquad \vdash (\lambda z. z) : \tau\_1} {\vdash (\lambda x y.y (x y)) (\lambda z.z) : \tau\_0} $$

You can of course make use of any theorem that you already know. In particular, the *principal typing* theorem can be useful: if a term is well-typed then all of its types are instances of a particular one. For example, the identity function $(\lambda z.z)$'s possible types are all instances of $\forall \alpha. \alpha \to \alpha$. Similarly, it's easy to see that the function $(\lambda x y.y (x y))$ has the most general type $\forall \beta \gamma. ((\beta \to \gamma) \to \beta) \to ((\beta \to \gamma) \to \gamma)$.

In order to find a type for $(\lambda x y.y (x y)) (\lambda z.z)$, we saw above that we need to find types $\tau\_0$ and $\tau\_1$ such that $\tau\_1 \to \tau\_0$ is an instance of $\forall \beta \gamma. ((\beta \to \gamma) \to \beta) \to ((\beta \to \gamma) \to \gamma)$ and $\tau\_1$ is an instance of $\forall \alpha. \alpha \to \alpha$. This means that there must exist base types $T\_1$, $T\_2$ and $T\_3$ which satisfy the equations $$ \begin{align} \tau\_1 &= \forall \alpha \beta \gamma. (T\_2 \to T\_3) \to T\_2 \\ \tau\_0 &= \forall \alpha \beta \gamma. (T\_2 \to T\_3) \to T\_3 \\ \tau\_0 &= \forall \alpha \beta \gamma. T\_1 \to T\_1 \\ \end{align} $$ Hence $T\_3 = T\_1 = (T\_2 \to T\_3)$. But this is impossible due to the structure of types: a type can't be a strict subterm of itself. Therefore the premise of was wrong: the term $(\lambda x y.y (x y)) (\lambda z.z)$ is not well-typed.

chi's answer shows how to use another theorem about Hindley-Milner to shorten the proof: *subject reduction*, i.e. the property that if a term is well-typed and it reduces to another term then that other term also has the same type. Since $(\lambda x y.y (x y)) (\lambda z.z) \to\_\beta^\* \lambda y. y y$, if the original term has a type then so does $\lambda y. y y$. By contraposition, if $\lambda y. y y$ is not well-typed then neither is the original term. You can show that $\lambda y. y y$ is not well-typed by a shorter application of the methodology above: note that if it is well-typed, it must be an application of the lambda typing rule, which leads to a type equation of the form $T\_1 \to T\_1 = T\_1$, which has no solution for the same reason as before.

There are, of course, other type systems where the term in question is well-typed. These type systems must have some additional ways of typing terms that Hindley-Milner doesn't have. I'll give two examples:

* If you extend the syntax of types to allow them to be recursive (as with `ocaml -rectypes`), then the reasoning about the type equation having no solution because a type can't contain itself breaks down, and indeed both $\lambda y. y y$ and the original term are well-typed in this system. For example, the most general type of $\lambda y. y y$ is $\forall \alpha \beta \[\alpha = \alpha \to \beta\]. \alpha$.
* If you add a rule that allows *intersection types*: $$ \dfrac{\Gamma \vdash M : \tau\_1 \qquad \Gamma \vdash M : \tau\_2} {\Gamma \vdash M : \tau\_1 \wedge \tau\_2} $$ then the reasoning above breaks down because the presentation of the type system is not type-directed. The intersection rule can be used with any language construct. With this type system, $y : \alpha \wedge (\alpha \to \beta) \vdash\_{\wedge} y : \alpha$ and $y : \alpha \wedge (\alpha \to \beta) \vdash\_{\wedge} y : \alpha \to \beta$ and so $\lambda y. y y$ has the type $\forall \alpha \beta. (\alpha \wedge (\alpha \to \beta)) \to \beta$. The original term is also well-typed. With a rule that departs so radically from being syntax-directed, you might think that it's difficult to prove that a term is not typable, and you'd be right: the intersection rule is so strong that it causes all strongly normalizing terms to be well-typed. Conversely, intersection types with base types (but without quantifiers or a top type) only allow strong normalizing terms, so to prove that a term is not typable in that system, it's sufficient to prove that a term is not strongly normalizing. See Does there exist a Turing complete typed lambda calculus?) for more information about intersection types.
> 8 votes

# Answer
No, that term can not be typed in Hindley Milner, or any other "standard" type system. Here's a rough sketch of a proof.

Suppose by contradiction it had a type. Since type is preserved under beta reduction (by the subject reduction theorem) we would get that all these terms also have the same type

$$ \begin{array}{l} (λx.λy.y(x\ y))(λz.z) \\ (λy.y((λz.z)\ y) \\ (λy.y\ y) \\ \end{array} $$

The last term is however not typeable, since $y$ should have a function type $\tau\_1 \to \tau\_2$ because it is applied as a function, but since $y$ itself is the argument we should also have that $y$ has type $\tau\_1$. Since $\tau\_1 = \tau\_1\to\tau\_2$ is impossible, we obtain a contradiction.

Another way to see the same fact is running the type inference algorithm: doing so at a certain point would require to solve the equation $\tau\_1 = \tau\_1\to\tau\_2$, triggering the failure of type inference.

Let me add that applying a function to itself, directly or indirectly (as done above), is the archetypal way to produce a term having no type in typed lambda calculi.
> 7 votes

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


title: Longest common substring in linear time

text:
# Question
Title: Longest common substring in linear time
We know that the longest common substring of two strings can be found in $\mathcal O(N^2)$ time complexity. Can a solution be found in only linear time?

# Answer
> 16 votes
Let $m$ and $n$ be the lengths of two given strings,

### Linear time assuming the size of the alphabet is constant.

Yes, the longest common substring of two given strings can be found in $O(m+n)$ time, assuming the size of the alphabet is constant.

Here is an excerpt from Wikipedia article on longest common substring problem.

> The longest common substrings of a set of strings can be found by building a generalized suffix tree for the strings, and then finding the deepest internal nodes which have leaf nodes from all the strings in the subtree below it.

Building **a generalized suffix tree** for two given strings takes $O(m+n)$ time using the famous ingenious Ukkonen's algorithm. Finding the deepest internal nodes that come from both strings takes $O(m+n)$ time. Hence we can find the longest common substring in $O(m+n)$ time.

For a working implementation, please take a look at *Suffix Tree Application 5 – Longest Common Substring* at GeeksforGeeks

### (Improved!) Linear time

In fact, the longest common substring of two given strings can be found in $O(m+n)$ time regardless of the size of the alphabet.

Here is the abstract of *Computing Longest Common Substrings Via Suffix Arrays* by Babenko, Maxim & Starikovskaya, Tatiana. (2008).

> Given a set of $N$ strings $A = \\{\alpha\_1,\cdots,\alpha\_N\\}$ of total length $n$ over alphabet $\Sigma$ one may ask to find, for each $2 \le k\le N$, the longest substring $\beta$ that appears in at least $K$ strings in $A$. It is known that this problem can be solved in $O(n)$ time with the help of suffix trees. However, the resulting algorithm is rather complicated (in particular, it involves answering certain least common ancestor queries in $O(1)$ time). Also, its running time and memory consumption may depend on $|\Sigma|$.
>
> This paper presents an alternative, remarkably simple approach to the above problem, which relies on the notion of suffix arrays. Once the suffix array of some auxiliary $O(n)$-length string is computed, one needs a simple $O(n)$-time postprocessing to find the requested longest substring. Since a number of efficient and simple linear-time algorithms for constructing suffix arrays has been recently developed (with constant not depending on $|\Sigma|$), our approach seems to be quite practical.

Here is the general idea of the algorithm in the paper above. Let string $\alpha$ be concatenation of all $\alpha\_i$ with separating sentinels. Construct the **suffix array** for $α$ as well as its **longest-common-prefix array**. Apply a sliding window technique to these arrays to obtain the longest common substrings.

# Answer
> 4 votes
Yes. There's even a Wikipedia article about it! https://en.wikipedia.org/wiki/Longest\_common\_substring\_problem

In particular, as Wikipedia explains, there is a linear-time algorithm, using suffix trees (or suffix arrays).

Searching on "longest common substring" turns up that Wikipedia article as the first hit (for me). In the future, please research the problem before asking here. (See, e.g., https://meta.stackoverflow.com/q/261592/781723.)

---
Tags: algorithms, time-complexity, strings, longest-common-substring
---


# Question
Title: Reasons for choosing register number and address sizes in an Instruction Set
Why would it be suitable to design an instruction set with 2-bits allocated for the register number and 10-bits allocated for the memory address? Would introducing a cache change this? (If possible I'd like to know why or where to find an explanation on this.)

If it helps an example would look like this `0001 xxyy yyyy yyyy` and an instruction would be the opcode `0001` (Load) register `xx` from memory address `yy yyyy yyyy`.

# Answer
Two bits for the register and ten bits for the address makes sense when you have ~four registers and ~1024 words of memory. Any more and you can't address it all (how would you access register #5, or memory address #1025?); any less and you're wasting precious bits in every instruction (why use two bits for the register when there's only two registers to choose from?).

Generally, the purpose of a cache is to make things faster *without changing the underlying model*. In other words, if you don't care how fast your code is, you can just pretend the cache isn't there. Everything will work the same either way.

P.S. You can address more memory than this using various tricks like "bank switching", but I doubt you're concerned with those yet.
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: Proving Big Omega of a polynomial without limits
Here is the definition of $\Omega$:

> $f(n) = Ω(g(n))$ iff there exist positive constants $c$ and $n\_0$ such that $f(n) \ge cg(n)$ for all $n\ge n\_0$.

Here is one theorem:

> If $f(n) = a\_m n^m + \cdots + a\_1 n + a\_0$ and $a\_m \> 0$, then $f(n) = \Omega(n^m)$.

I want to prove this, without using limits. Despite many hours of searching across the internet, all I could find is proofs using limits. Is there any other way?

# Answer
> 2 votes
Define $M = \max(|a\_0|/a\_m, |a\_1|/a\_m, \ldots, |a\_{m-1}|/a\_m)$, and take $c = a\_m/2$ and $n\_0 = 2mM$. Then for $n \geq n\_0$, $$ \begin{align\*} f(n) &= a\_m n^m \left(1 + \frac{a\_{m-1}}{a\_m} \cdot \frac{1}{n} + \cdots + \frac{a\_1}{a\_m} \cdot \frac{1}{n^{m-1}} + \frac{a\_0}{a\_m} \cdot \frac{1}{n^m}\right) \\ &\geq a\_m n^m \left(1 - \frac{M}{n\_0} - \cdots - \frac{M}{n\_0^{m-1}} - \frac{M}{n\_0^m}\right) \\ & \geq a\_m n^m \left(1 - \frac{mM}{n\_0}\right) \\ &= c n^m. \end{align\*} $$

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


# Question
Title: (Generally) How to specify asynchronous action with side effects using logic equations
Say you have this function call sequence:

```
function all() {
  fn1()
  fn2()
  fn3()
}

```

And say that `fn2` was asynchronous and caused all kinds of side effects:

```
var globalPacketCounter = 0

function fn2() {
  var httpRequest = ...
  httpRequest.on('data', function(){
    globalPacketCounter++
  })
  drawGraphicsToDisplay()
  ...
}

```

Something complicated and with unknown implementation, though you can probe it to determine the types of behavior it has, and read docs, etc.

I'm wondering, generally speaking, what you can do to incorporate this into a model checking or symbolic evaluation system, or other verification system like Hoare logic or something. I would like to do this:

```
all() =
  /\ fn1() in state 1
  /\ fn2() in state 2
  /\ fn3() in state 3
  /\ complete = true in state 4

```

Some sort of logical statement. The question is (partially) if this is a valid approach; that is, treating the `fn2()` as a single step in a logic equation. The main part of the question though is how to generally do this. I would like to basically treat everything as logic functions but am not sure how to apply it to the "async with side effects" case.

# Answer
The way to incorporate it in a model depends on (a) what aspects of system behavior you want the model to capture, (b) what properties you want to verify of the system, and (c) what kind of expressivity the model checker framework provides.

In other words, there's no one way to model systems. One can build multiple models of the same system, each focusing on different aspects of the system, or modelling it to a different level of abstraction/precision.

For instance, in something based on pi calculus, one possible way to model asynchronous operations is as spawning a separate process to perform that stuff concurrently.
> 1 votes

# Answer
One way to model your example is through program graphs. (See chapter 2 in Principles of Model Checking.) What you can do is model `all()` as one program, which synchronizes on action 'data' with another program that runs concurrently to `all()`, let's call it `listen()`. `listen()` will have an initial state where it waits until it can synchronize with the `all()` on action 'data'.

Once you have these two models (or more for bigger examples) you can interleave them, which is a construction that contains all the possible states. Program graph interleaving also preserves shared variables (so globalPacketCounter will be updated correctly) unlike interleaving on transition systems. Though I would be careful about them, since atomicity is not implicit in the models. You can read more about critical actions in section 2.2.2. of the book.

After interleaving of PGs you construct a transition system, which you can transform to a logical equation. And there you have it.
> 2 votes

---
Tags: logic, formal-methods, software-verification, model-checking
---


title: invariant of bin packing

text:
# Question
Title: invariant of bin packing
We are given an array of integers and a number K. We need to pack these integers into bins. The condition is that we have to use exactly K number of bins and each bin should have equal capacity. We need to find the size of bin such that wastage of unused bin is minimized.

Is this problem polynomial time solvable?

# Answer
Since the number of bins is fixed, the problems boils down to a job shop scheduling with atomic jobs. See https://en.wikipedia.org/wiki/Job\_shop\_scheduling#Atomic\_jobs

A solution is given by $\max\\{ 1/m \sum\_{i=1}^n t\_i, max\_i t\_i \\}$ where $t\_i$ represents the $i$th integer and $m$ represent the set length. The wiki reference above includes a paper with the proof.

**EDIT after request on polynomial time** Since it's equivalent to the partition problem, which is NP-hard, this problem is also NP-hard and therefore not solvable in polynomial time.
> 1 votes

---
Tags: algorithms, dynamic-programming, combinatorics, approximation, subset-sum
---


# Question
Title: Boolean Algebra : Using identities, prove x(x + y) = x
Example: Prove the ABSORPTION LAW: $$ x(x + y) = x $$

$ Solution: \\ x(x + y) \\ = (x + 0)(x + y) \\;\\;\\;\\;\\; Identity \\;Law \\ = x + (0 · y) \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; Distributive \\;Law \\ = x + y · 0 \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; Commutative \\;Law \\ = x + 0 \\; \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;Domination \\;Law \\ = x \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; Identity \\;Law \\ $

I was given an example here and shown one method of solving it. I was told there was an alternative solution to it and I was curious about it.

This is one method of proving the problem.

The alternative method suggested solving the same expression in the order of:

DISTRIBUTIVE LAW, IDEMPOTENT LAW, DISTRIBUTIVE LAW, DOMINANCE LAW, and IDENTITY LAW.

When I try, I get stuck here:

$ Solution: \\ x(x + y) \\ = (x · x) + (x · y) \\;\\;\\;\\;\\; Distributive \\;Law \\ = x + (x · y) \\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\;\\; Idempotent \\;Law \\ = (x + x)(x + y) \\;\\;\\;\\;\\;\\; Distributive \\;Law \\ $

I've been stuck on where I can prove it using the dominance law, unless I can extend this with an identity law proof. My first time in a while, please excuse.

# Answer
Solution: $$ \begin{align}x(x+y) &= (x\cdot x)+(x\cdot y) \quad\text{\[Distributive Law\]} \\ &= x + (x\cdot y) \quad\text{\[Idempotent Law\]} \\ &= x \cdot (1+y) \quad\text{\[Distributive Law\]}\\ &= x \cdot 1 \quad\text{\[Property of 1\]} \\ &= x \quad\text{\[Property of 1\]} \end{align}$$
> 3 votes

---
Tags: boolean-algebra
---


title: Partition array into k subsets

text:
# Question
Title: Partition array into k subsets
We are given an array and a number K. Partition array into K subsets such that

let MaxSum be the maximum sum of among subsets.

We have to minimize summation =$$\sum\_{i=1}^{k}MaxSum-sum(i) $$

Is this problem polynimial time solvable?

# Answer
> 3 votes
I'm assuming by $sum(i)$ you mean that given an ordering of the $k$ partitioned subsets, sum over all elements of the $i$th subset.

The $k=2$ case is the optimization variant of the set partitioning problem (https://en.wikipedia.org/wiki/Partition\_problem) which is known to be as hard as subset sum. EDIT: The general case is as difficult by reduction from $k=2$.

---
Tags: algorithms, time-complexity, arrays, partitions, subset-sum
---


title: How to model references in an ontology

text:
# Question
Title: How to model references in an ontology
I am interested in creating an ontology which will model arguments (among other things). For example, a triple in the ontology might be

`Vaccination -> can lead to -> Autism`

(not that I necessarily believe this, just a good example of an argument). I would like to attach sources to any disputed statement. So ideally, the above example would be stored as

`Vaccination -> can lead to -> Autism -> according to -> Article X`

This cannot easily be represented as a triple in a standard ontology. What are the accepted ways of modeling this type of data?

I see that on WikiData, all relations can have sources attached to them (e.g. see https://www.wikidata.org/wiki/Q23 for sources on when George Washington was born). It could be that WikiData doesn't store their data as triples.

# Answer
> 3 votes
If you want to say something about an RDF triple (i.e., an `rdf:Statement`), you can use **reification**:

```
@prefix rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#> .
@prefix voc: <https://example.com/vocabulary#> .
@prefix :    <https://example.com/instances#> .

:Triple42   rdf:type        rdf:Statement .
:Triple42   rdf:subject     :Vaccination .
:Triple42   rdf:predicate   voc:canLeadTo .
:Triple42   rdf:object      :Autism .
:Triple42   voc:publishedIn <https://example.com/articles/vaccination-and-autism> .

```

But you would probably want to say something about the argument, not about the RDF statement expressing the argument. You can use **n-ary relations** for this, e.g., by introducing an instance that represents the argument:

```
@prefix voc: <https://example.com/vocabulary#> .
@prefix :    <https://example.com/instances#> .

:Argument1 a voc:Argument .
:Argument1 voc:publishedIn <https://example.com/articles/vaccination-and-autism> .
:Argument1 voc:textualRepresentation "Vaccination can lead to autism!" .

```

(and then use properties that dissect the argument to represent it in a machine-readable way)

---

Relevant vocabularies: PROV, `schema:ClaimReview`

---
Tags: graphs, database-theory, modelling, ontologies
---


# Question
Title: CFG for the language {ω ∈ {a, b}*| in every prefix of ω, the number of a’s is greater than or equal to number of b’s}
I know the answer which is:

\begin{align} S &\rightarrow aS \mid T\\ T &\rightarrow aTbT\ \mid \varepsilon \end{align}

Now, $bbaaa$ is in the language. But the given CFG cannot generate it. Is it a possible misunderstanding on my end about the prefix's? Can you explain? And if the CFG given is wrong, what is the correct CFG for the language?

Maybe this is the right grammar?

\begin{align} S &\rightarrow aS \mid T\\ T &\rightarrow aTbS \mid bTaS\ \mid \varepsilon \end{align}

# Answer
The string $bbaaa$ is not in the language, as Draconis pointed out (its prefix $b$ contains more $b$'s than $a$'s). As such, the second grammer is wrong.

However, the first suggestion is also wrong. It does not accept the string $abaaaa$, which belongs to the language.

The correct grammar is:

$$S \to \epsilon \mid aS \mid aSbS$$

To see that every word accepted by this grammar indeed belongs to the language, a straight-forward induction proof will do. So let's check that every word where each prefix has at least as many $a$'s as $b$'s is accepted by our grammar.

If the word is empty, we are done. Else it has to start with an $a$. There are two cases.

* There is one prefix of the word that has an equal number of $a$'s and $b$'s. Write the word as $awbv$ where $awb$ is the shortest such prefix. Both $w$ and $v$ must belong to the language, so we can use the rule $S\to aSbS$.
* Every prefix of the word has more $a$'s and $b$'s. Write the word as $aw$. Then $w$ must belong to the language, so we can use the rule $S \to aS$.
> 5 votes

---
Tags: formal-languages, formal-grammars
---


title: What makes a function computable?

text:
# Question
Title: What makes a function computable?
It seems to me, at the moment, that I don't understand where the line is drawn between "computability" and being incomputable. The main question is, is it the ability to be "solved" only by trying out every possible combination?

I know there are probably "even worse" things where it is not even possible to define "every possible combination", but those are obviously over the line.

I have a few fringe examples I would like to discuss.

1 - If there was a program called HaltsInUnder100Operations, one could make that decides whether any program x, given an input i, halts in under n operations (say 100 operations as it might need to be a certain goldilocks range). It seems like it could be possible to analyse the program and find the answer from there. But if you put it through the same test as the general halting problem that Turing proved was impossible, it could run into the same logical difficulty.

The problem would not directly be that it is incomputable, but instead that there are probably some programs you cannot tell will halt in under n operations, without running them. Is it that itself that makes it incomputable?

If you tried to test that program, it would possibly take more than n operations to give the result.

If you design a set of programs where it is possible to tell how many steps they will take, then the program HaltsInUnder100Operations(x,i) will not itself be in that set of programs either, so that can't work.

2 - In Numberphile where they are solving a^3 + b^3 + c^3 = 33, they say equations like these officially "could be undecideable" (incomputable?), and yet they are finding solutions left and right by trying every possible combination. Maybe they mean that there might be no "formula" for finding the solutions.

3 - Similarly, the travelling salesman problem is a famous example, but can be solved for small enough sets by trying every possible combination.

And the busy beaver problem (a prime example of "incomputable") has been solved for up to 4 states in binary, again by trying every possible program and finding which ones halt or loop - but I heard there is a point (1919 states?) where it can't be solved in this way. Maybe there are infinitely changing results for that which technically do not halt but there is no way of telling that they won't at some extremely large finite number? So, given a never-ending amount of time to get the answer, the answer would never be found.

4 - The prime numbers may seem "computable" at first glance, but then there is no known formula that can "efficiently compute" them (i.e. you plug in n and you get out the nth prime number). So what side of the line is that on?

5 - Pi (or the digits thereof) is considered to be "computable", even though it would take infinity to find all the digits.

6 - If you were to write down some numbers "at random" (without using a formula) or generate them based on random inputs, would these be "incomputable"? It could be argued that being possibly affected by stochastic processes makes them incomputable, though finite (because you are going to stop at some point). And yet if you had a computer generate all decimals of length n (where n is the length of your randomly generated decimal) then one of those would be the same decimal. So it is again a blurred line.

With these possible incomputable finite problems (if they are indeed incomputable), that makes me wonder if the basic foundation of computability is itself "incomputable" by some definition? For example, the formulae themselves which had to require some exhaustive testing, even if doing so was very easy. Computability would then be something that is based on established formulae, and then the ability to get further answers using those, without needing an exhaustive search. Maybe it just means anything that can be reached with "shortcuts" of some type?

# Answer
> 6 votes
> \[is\] the basic foundation of computability is itself "incomputable" by some definition?

Nope. There is a precise mathematical definition for the concept of "computable". We say that a function $f:\\{0,1\\}^\* \to \\{0,1\\}$ is computable if there exists a Turing machine that computes it. It only makes sense to apply this concept to functions. It doesn't make sense to ask whether an apple is computable, or whether the color green is computable, or whether the foundation of computability is computable -- none of those are functions, and the notion "computable" is only defined for functions.

I suggest finding a good textbook on computability and the theory of computing, and studying the material there to learn about computability theory. It sounds like you might be trying to guess what it might mean based on examples, informal descriptions, analogies, first principles, and maybe a little bit of speculation. I suspect that none of those are going to be a very effective way to learn a mathematical subject.

---
Tags: computability
---


# Question
Title: Is there an efficient solution to the travelling salesman problem with binary edge weights?
Is there a way to solve TSP in polynomial time if there are only two kinds of weights, 0 and 1?

# Answer
> 8 votes
No, since if every edge has weight 1, there is still the question of whether any such tour exists, which is the Hamiltonian Cycle problem, and this is still NP-hard. (The link is to a Wikipedia page for Hamiltonian Path -- both the path and cycle versions of the problem are hard.)

# Answer
> 3 votes
The accepted answer isn't quite right. An instance of TSP consists of a distance between every pair of cities: that is, it consists of a weighted complete graph. Every complete graph has a Hamiltonian cycle.

However, it is simple to reduce HAMILTON-CYCLE to $0$$1$ TSP. Given a graph $G$, create a TSP instance where the cities are the vertices and the distance is $0$ if there is an edge between the cities and $1$ if there is not. Then $G$ has a Hamiltonian cyle if, and only if, the TSP instance has a tour of weight zero. Therefore, $0$$1$ TSP is **NP**-complete.

---
Tags: traveling-salesman
---


title: Datalog Self Interpretation

text:
# Question
Title: Datalog Self Interpretation
According to https://link.springer.com/article/10.1007%2Fs001530050135 (Logics that define their own semantics, Imhof 1999) the logic FO\[LFP\] can define its own semantics, though the proof (of corollary 6.4) is somehow fuzzy. It is known from finite model theory that Datalog is equivalent to FO\[LFP\] (on ordered structures). Can someone help me see (at least partially) how to write a Datalog self-interpreter? The main difficulty is to express modus-ponens considering unification without involving existential variables in heads (i.e. variables in heads which don't appear in bodies and are understood to be existentially quantified).

Another related puzzle of mine is, if LFP's data complexity is P, and its query complexity is EXPTIME, how come it can interpret itself indeed? (I have no doubt that it can as the paper above supplied two different proofs for that. also we know that provably P!=EXPTIME)

# Answer
> 1 votes
Partial answer only.

For me, the paper is behind a paywall. So I can base this only on its abstract and your question.

I believe you have a point with your complexity doubts. I can see how to write an FO\[LFP\] self-interpreter, provided there is a way to handle large arities. In particular, the self-interpreter has a single, fixed, maximum arity and number of variables while the interpreted formulae should be unbounded with respect to arity and number of variables. I can see a few ways to go about that:

1. There is in fact not a single self-interpreter, but a family of such, indexed by maximum arity.
2. The structure that encodes the input (the formula plus the original structure) has in its domain not only (subformulae of the formula and) elements of the original structure, but also tuples of the original structure up to the required arity. Then, converting the original input into its encoding structure already imposes an exponential blowup.
3. For infinite structures, tuples can be encoded as single elements using a pairing function. On well-ordered structures, FO\[LFP\] can define (ordinal) arithmetic and hence such a pairing function. Possibly, the statement in the paper does not address finite structures at all?

For the Datalog self-interpreter, I suggest you start with a Datalog interpreter written in FO\[LFP\] and then convert that formula into a Datalog query.

---
Tags: interpreters, finite-model-theory, datalog
---


# Question
Title: Find all polygons from a set that overlap a given polygon (convex case)
Problem: Given a set of $N$ non-overlapping convex polygons $\\{S\_i | 1\leq i\leq N\\}$ defined by their vertex coordinates $(x,y)$ and a convex polygon $P$, also defined by its vertex coordinates, find all polygons $S\_i$ that overlap with $P$. Assume an algorithm to test whether a pair of polygons overlap already exists.

Constraints: We are allowed to perform operations of $O(N \log N)$ on $\\{S\_i\\}$ without knowledge of $P$ (initialization step). After that, given an arbitrary $P$ the algorithm should perform in approximately $O(\log N)$ time when $S$ consists of polygons of uniform size. Hence, an algorithm that just tests $P$ against every $S\_i$ will be rejected.

Solution idea: On initialization, insert all vertices of the polygons of $\\{S\_i\\}$ into a kd-tree $K$ and associate each vertex with its associated polygon. Store the diameter $dS$ of the largest polygon in $\\{S\_i\\}$. Then given a polygon $P$, calculate the diameter $dP$ of $P$. Find all vertices in $K$ that are no farther than $\max(dS,dP)/2$ (?) from any vertex in $P$. Test $P$ against only faces that contain the vertices in $K$.

Since lookup in $K$ is a $\log(N)$ operation, then if $N$ is large and $dP$ is approximately equal to dS then the number of tests should be $\<\< N$.

Any other solution ideas? Google is yielding nothing of value.

Similar to How to find polygons overlap reign but with additional constraints.

# Answer
Suppose all the polygons $S\_1,\dots,S\_n,P\_1,\dots,P\_n$ are given in advance. Then I can propose an algorithm that might often be efficient in practice (though it can degenerate to quadratic-time behavior if you get a sufficiently nasty configuration of polygons).

In particular, the polygon $P\_i$ overlaps with some $S\_j$ if and only if:

(1) some line segment of the perimeter of $P\_i$ crosses some line segment of the perimeter of $S\_j$; or,

(2) some vertex of $P\_i$ is inside $S\_j$, or some vertex of $S\_j$ is inside $P\_i$.

So, it suffices to check both conditions separately.

# Crossings between perimeters

You can check find all crossings between the perimeters of the polygons as follows. Decompose the perimeter of each polygon $P\_i$ into a collection of line segments. Do the same for each $S\_j$. Then, use the Bentley-Ottmann algorithm (or some other similar algorithm) to find all crossings between these line segments. This will tell you, for each $P\_i$, whether its perimeter crosses any of the $S\_j$ perimeters. If it does, then you know that $P\_i$ has an overlap with some $S\_j$.

The running time will be $O((n+k) \log n)$, where $k$ is the number of crossing between these line segments. In practice, you can hope that $k$ won't be too large (it probably often will be fairly small, unless you get really unlucky with how the polygons are arranged).

# Vertex inside a polygon

So we have a bunch of polygons, and a bunch of points. I suggest using the Bentley-Ottman sweepline algorithm on the line segments corresponding to the perimeters of the polygons. In addition to an "event" happening at each two intersection between two line segments and at each endpoint of each line segment, create another event at the location of each point. In addition to a binary search tree storing the locations of the line segments that intersect the sweepline, also use an interval tree to store an interval for each polygon that intersects the sweepline (namely, the range of $y$-coordinate values where the sweepline intersects that polygon). Now, when you hit an event corresponding to a point, you can check which intervals in the segment tree contain that point, i.e., which polygons contain that point, using a stabbing query.

By using self-balancing trees, you can arrange that each step of this algorithm can be done in $O(\log n)$ time. Thus, the total running time will again be $O((n+k)\log n)$.

# Online queries?

The above describes how to solve your problem in "batch mode", where all polygons are given in advance. What if only $S\_1,\dots,S\_n$ are given in advance and the $P\_i$'s are provided one at a time, and we have to check for overlap in an online fashion? I don't know how to handle that.

I might be able to get you started on an idea for half of it, but I don't see how to flesh it out into a full algorithm. For part of it, I think it might be possible to do something for that case as well, using partially persistent data structures.

Apply the sweepline algorithms above to the polygons $S\_1,\dots,S\_n$, and store all copies of the binary tree and interval tree at each event. Naively, this would require $\Omega(n^2)$ space (since there are $\Omega(n)$ events and each tree is $\Theta(n)$ in size), which is horrible. Fortunately, each tree differs from the previous tree by only $O(1)$ modifications. Therefore, we can use a persistent data structure to store all of the trees, using standard path copying techniques, and in that way we'll be able to store all of the trees in $O((n+k) \log n)$ space. Moreover, if we keep an array of all of the roots of these trees, then given any x-coordinate, we'll be able to look up the appropriate tree for that x-coordinate in $O(\log (n+k))$ time using binary search.

Given a polygon $P\_i$, we'll first look up each vertex of $P\_i$ in this data structure to see if it is contained in any of the $S\_j$'s. This can be done by taking each vertex, looking up the Bentley-Ottman trees for the x-coordinate of that vertex, and looking up the y-coordinate of that vertex in the interval tree to see if any of the $S\_j$s contain it.

Next, we need to go through each line segment in the perimeter of $P\_i$ and check whether it intersects any of the line segments of the $S\_j$'s. However, I don't know how to do this in a way that supports online queries for the $P\_i$'s. So, that's the part you'd need to find a way to fill in.
> 0 votes

---
Tags: algorithms, computational-geometry, search-algorithms
---


title: Prove $ 8^n = Θ(4^n)$

text:
# Question
Title: Prove $ 8^n = Θ(4^n)$
how would I prove

$ 8^n = Θ(4^n)$ is either true or false.

I so far have attempted to prove big O but cant find the value of C1

# Answer
Just compute $\lim\_{n\to\infty} \frac{8^n}{4^n} = \infty$. Hence, $8^n = \Omega(4^n)$ and also $8^n = \omega(4^n)$.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }
I don't understand what this regular language is asking for? Find a grammar for L(G) = {w || w | is odd,∑ = (0, 1) }. What does the " || " mean I know a single " | " means or.

# Answer
Yup, I can see why that would be confusing. The typesetting is probably making this harder to follow. I'm guessing what's written is $\\{w \mid |w| \text{ is odd}, \ldots\\}$. This is the set of all $w$ such that $|w|$ is odd etc. Here $|w|$ typically represents the length of the word $w$.

It might have been clearer if the author had used a colon instead of a vertical line in our set builder notation: then it would have been written $\\{w : |w| \text{ is odd}, \ldots\\}$, and maybe it would be easier to see what is going on..
> 2 votes

---
Tags: regular-languages, formal-grammars, regular-expressions, discrete-mathematics
---