# Question
Title: lower bound for Renyi–Ulam Game with lies
Player $A$ thinks of number between 1 and $n$ and ask $B$ to guess the number with minimum number of decision queries (yes or no type ).

**Game** :

1. $A$ chooses an element in {1,2....,n}
2. $B$ tries to guess this number by asking Yes/No questions.

Binary search is a way to solve the problem, so with $\log n$ many queries will be sufficient to solve the problem when player $A$ does not lie. But if player $A$ lie exactly one time than we can problem with $2\log n$ many queries (by just asking the same query two times). There is an optimal way to solve this problem with $ \log n + \log \log n +c$ , where $c$ is a constant. We will first ask $\log n $ many queries to $B$ and going to get a $\log n $ bits long binary string and now apply binary search on this binary string. In **general** when A is allowed to lie say $l$ (constant) then also the number of queries need to solved the problem is $ \log n + \log\log n + c $

**Questions** : 1) How to prove that $ \log n + \log\log n + c$ is a **lower bound** ?

2) If only $\log n$ many queries are allowed in the general case Is there an approximation algorithm for this game ( original solution = $a$ * algorithm's solution, where $a$ is constant).

3) If $l$ is very large (say order of $n$) Is it possible in that case to correctly find out the guessed number ? I tried to use the Hamming distance but not able to come up with a precise answer.

**Reference** :http://ac.els-cdn.com/S0304397503005814/1-s2.0-S0304397503005814-main.pdf?\_tid=a880fa14-f82d-11e6-81df-00000aacb35e&acdnat=1487678746\_7307f01621c154d9f6e006fc8b992ad0

# Answer
> 3 votes
For the first question, suppose that you have an algorithm that supports one error, and uses $m$ questions. For each element $i \in \\{1,\ldots,n\\}$, let $x\_{i0}$ be the vector containing the answers to all questions when A doesn't lie, and let $x\_{ij}$ be the vector containing the answers to all questions when A lies in question $j$. In total, we have $n$ collections of $m+1$ vectors. All these vectors are distinct: the $m+1$ vectors in a collection are distinct by definition, and vectors belonging to different collections must be distinct since the correct answer is different. We deduce that $(m+1)n \leq 2^m$, and so $m \geq \log n + \log\log n + \Omega(1)$.

For the second question, here is something to try. Let $m$ be a number so that $\log n$ queries suffice to find an element in $\\{1,\ldots,m\\}$, even when A is allowed to lie at most once. Partition $\\{1,\ldots,n\\}$ into $m$ intervals $\[x\_1,x\_2),\[x\_2,x\_3),\ldots,\[x\_m,x\_{m+1})$, where $\[a,b) = \\{a,\ldots,b-1\\}$, $x\_1 = 1$, and $x\_{m+1} = n+1$. Then this gives an $\alpha$-approximation for $\alpha = \max \frac{x\_{i+1}-1}{x\_i}$. I leave the rest to you.

The third question is addressed in Three thresholds for a liar by Spencer and Winkler. The threshold is $n/3$ (a strategy exists if $\ell \< n/3$).

---
Tags: algorithms, algorithm-analysis, combinatorics, lower-bounds, binary-search
---


title: Formal specification; Logical formula

text:
# Question
Title: Formal specification; Logical formula
*** Initial Question ***

I'm trying to write a logical formula consists of three Boolean variable C1, C2, C3.

My program takes graph as input and checks properties about them. C1 represents presence of some **structural properties** of the input graph (graph being strongly connected). If graph have this property, variable C1 is True else its False.

Variable C2 and C3 represent another set of properties involving other program variables.

The property i'm interested is

> If graph have this desired structural property then there is an assignment to program variables that makes C2 & C3 True.

For checking one specific graph i can just say:

```
SAT (C1 && C2 && C3)

```

And if there is a satisfying assignment i'm done.

But rather than checking properties of specific graph i'm interested in checking for every graph which have this structural property (represented by C1) also have other properties too (represented by C2,C3).

So I represent graph as arbitrary two dimensional array of size N. So that i can allow my program to iterate over any graph of size N.

```
Bool Graph[N][N]

```

I want to write this.

> For\_all Graph\[N\]\[N\] s.t C1 $\implies$ There\_exists(an assignment) s.t C2 && C3

I'm not sure how to can i write this property? Any help in this regard?

**Updated Question :** To make question clear as after an answer i thought i was unable to put my point clear.

In my program i'm taking graph as input. based on this graph i'm trying to make connection that if the graph have some structural property then it has other properties also.

The structural property is: graph being ***strongly connected***. Other properties are based on the label of edges and nodes. So to generalize, other properties depend on program variable x,y,z,.. and Boolean function f.

I can build this program by using a Boolean variable B1 to inspect whether graph is strongly connected or not, if its is B1 is True, otherwise False. and use other Boolean variable B2 and B3 to represent other properties. Hence both B1 and B2, B3 depend on graph and B2, B3 also depend on other variables x,y,z,... and Boolean function f.

To check for a single graph i can ask:

```
SAT (B1 and B2 and B3). if there is an assignment i'm :)

```

Problem arise when i'm interested not in a particular graph but in every graph (certain fixed size N). Worst possible try is to generate all graphs of certain size and check each one by one and make sure that its the case.

The thing i'm trying to achieve is something like this :

```
For_all graphs G s.t B1 -> There_exist an assignment to (x,y.., f) s.t B2 and B3.

```

## Edited

I want to iterate over all graphs (which i can do making graph arbitrary)

```
unsigned int Graph[N][N];  // For some specified N

```

but with that i'm looking to check whether there exists an assignment that makes other property works. If other property were VALID(tautologous) or Contradiction i could have checked easily. But other properties(represented by C2 , C3) are not either a Valid or a contradiction. For example with SAT (C1 && C2 && C3) and SAT (C1 && !(C2 && C3)) both have a witness.

> I'm interested in iterating and checking that there exists at least one possible assignment for each graph that makes C1 && C2 && C3 true.

# Answer
> 0 votes
If I understand correctly (and I might not), it sounds like maybe the property you are trying to prove is

$$\forall G . C\_1(G) \implies (\exists x . C\_2(G,x) \land C\_3(G,x))$$

where $G$ ranges over all graphs and $x$ ranges over all possible assignments to the program variables.

If that's right, then you can't check this with SAT or with CBMC. It's a second-order formula, so you need a 2QBF solver to check it. SAT can help you check properties of the form "$\forall x . F(x)$" and properties of the form "$\exists x . F(x)$", but for properties of the form "$\forall x . \exists y . F(x,y)$" or "$\exists x . \forall y . F(x,y)$", you need 2QBF (or, more generally, QBF). There do exist 2QBF solvers, but checking 2QBF properties is much harder than checking SAT.

An additional complication is that it sounds like you want to quantify over all graphs of all sizes.

It sounds like you want to verify the following property: for all graphs, if C1 is true, then C2 and C3 are true.

The standard approach is to use assume and assert statements. You first write some assume statements that capture the assumption that the input graph satisfies C1. You then write some assert statements that capture the requirement that the C2 and C3 had better be true. The model checker checks whether there are any inputs that satisfy all the assume statements, and make at least one of the assertions false.

If you were going to use a SAT solver, you would search for a counterexample by writing a boolean formula C1 && not(C2 and C3), then asking the SAT solver to find a satisfying assignment for that formula. If it finds one, that it has found a counterexample to your property. If the formula is unsatisfiable, then your property holds. This all assumes that you are reasoning about graphs of a fixed size.

If the graph is of arbitrary size, then the problem is much harder. That falls beyond SAT and beyond even QBF, as both SAT and QBF relate to formulas with a fixed (constant) number of boolean variables -- but if you want to reason about arbitrary-sized graphs, there is no encoding of that into a fixed number of boolean variables. A standard heuristic is to check the property on graphs of size N for a few small values of N (say, for N=1,2,3,4,5,6,... until you run out of patience or the solver starts taking too long).

---
Tags: satisfiability, formal-methods, first-order-logic, automated-theorem-proving, c
---


# Question
Title: Algorithm to allocate resources to minimize the maximum of any party
I was given the following algorithms problem:

> Suppose you have $n$ cities. Each city $c\_i$ has population $p\_i$. You want to construct $m \geq n$ schools, where each school can only serve students of its city, and fulfill two objectives:
>
> 1. Every city must have at least $1$ school.
> 2. You want to allocate schools to cities such that the maximum number of people served by any one school is minimized.

I came up with the following naive algorithm to allocate schools to cities, but found that it is too slow in practice.

1. Assign one school to every city.
2. Keep a list of triples, where one triple $t\_i$ represents the following information for city $c\_i$: `(number of schools, population, population divided by number of schools)`
3. While the number of schools left to assign is not zero:
    1. Find the triple with the maximal `population divided by number of schools`.
    2. Assign one more school to that city.

My insight here was that minimizing the maximal number of students in any school is exactly the same as minimizing the average number of students per school in any city.

Regardless, the algorithm I lined out above is far too slow in practice, because finding the triple with that maximum is a linear-time operation in the number of cities. (Additionally, I assume that some clever optimizations could let us assign multiple schools to cities at once -- proceeding one-by-one is likely also slower than necessary.) The problem statement leads me to believe that maybe I could use integer programming or dynamic programming, but I'm not sure. What is an efficient algorithm to solve this problem? Are there analogous problems?

# Answer
Hint: Binary search is often a helpful strategy.

Another hint:

> Suppose you want to find out whether it's possible to find a way to allocate schools to cities, so that every school serves at most $s$ students. Could you figure out the answer to that question, if $s,m,n$ and the $p\_i$ were given as input? I bet you could. You should be able to solve that one, in $O(n)$ time. Now you should know what to do....
> 1 votes

# Answer
* allocate 1 school to each of the cities and calculate average school size
this first pass will just be city size at it has 1 school
$\mathcal{O}(n)$
* sort on average school size for each city
with highest average first
I think $\mathcal{O}(n\*log(n))$
* add 1 school to top for the sorted cities above and take new average school size
average is city size / number of schools
* using binary to re-sort that one city by average school size
$\mathcal{O}(log(n))$
* you must do the above two steps m-n times so
$\mathcal{O}((m-n)\*log(n))$

Sum and get $\mathcal{O}(m\*log(n))$

Thinking out loud best possible case is each school has the exact same number of students so could take the total number of students and divided by m. Assign enough schools to each city to get to that number and round down (every school is over the optimal number). Any city with no school gets 1 school. Hopefully you have some schools left over. Then use the algorithm above starting at step (bullet) 2. I suspect there are edge cases this does not cover. Round down from 301 to 300 is not going to have the same effect as round down from 3 to 2.

If you do not have schools left over then then I think you could take schools in order from lowest average.
> -1 votes

---
Tags: algorithms, optimization
---


# Question
Title: Looping and branching with Algorithmic Differentiation
Algorithmic (aka *Automatic*) Differentiation is a wonderful technique for numerical computation of derivatives. I understand how it relates to the fact that we know how to deal with every elementary operation in a computer program, but I am not sure to get how this applies to *every* computer program.

To quote from this wikipedia page:

> every computer program, no matter how complicated, executes a sequence of elementary arithmetic operations

.. which I totally agree with. However, it sounds then that the number $m$ of variables newly produced from any $n$ initial input is fixed and can be determined from static code analysis. But this is not straightforward to me since constructs like:

```
if x_1 > x_2:                         # branching
    perform 4 elementary operations
else:
    perform 84 elementary operations
endif

```

and:

```
while x_1 < x_2:                      # looping
    perform 2 elementary operations
endwhile

```

do exist in so-called « complicated » computer programs. This make the number (and the type) of elementary operations not straightforward to compute in advance. And I even suspect it is impossible to gess that in general, right?

Does AD support such branching and looping programs?
Are there extensions of AD adapted to programs that are not just intricate closed-form expressions?
How does AD deal with Turing-completeness?

# Answer
> 13 votes
AD supports arbitrary computer programs, including branches and loops, but with one caveat: the control flow of the program must not depend on the *contents* of variables whose derivatives are to be calculated (or variables depending on them). Here is an example:

```
if x = 3 then 9 else x * x

```

At close inspection you will recognize that the above is really just an inefficient way of implementing $x\*x$. If you evaluate this program at $x = 3$, then the result is the constant $9$. But the derivative of constants is zero, which is obviously not the right answer, which should be $6$.

The reason is that AD will typically only look at the executed branch of your program. It is perfectly ok to have branches on conditions that don't involve numbers, or conditions involving number variables not part of the computational graph for derivative calculations. It's also ok to look at fixed properties of derivative values (e.g. the dimension of a vector). But as soon as you "look" at the contents of a variable that depends on one of the inputs to determine what calculation to perform next, you will "break the chain". AD does basically just that: apply the chain rule.

Users of AD should view programs as "configuring" a fixed computational graph. If running the program with different inputs for which derivatives are requested gives you different computational graphs, AD may not always give the correct result.

# Answer
> 5 votes
If you want the derivative everywhere, automatic differentiation can't handle branches and loops. If you are satisfied with getting the derivative "almost everywhere", automatic differentiation might be fine for some programs with (some kinds of) branches. For some kinds of optimization, this is sometimes good enough.

Automatic differentiation can support at least some branches and if-statements, but with the caveat that it might fail (or the derivative might fail to exist) at the "boundary" of the conditional statements.

Consider your case where we branch `if x_1 > x_2`, and suppose we are calculating the derivative with respect to `x_1` at a particular point `(x_1, x_2)`. Then if the branch is true at that point, we calculate the derivative of the true-branch with respect to `x_1`. If the branch is false at that point, we calculate the derivative of the false-branch with respect to `x_1`. (If `x_1 == x_2`, we might have a discontinuity and the derivative might not be defined.)

Why does this work? Consider the function

$$f(x) = \begin{cases} g(x) &\text{if $x\>c$}\\ h(x) &\text{otherwise} \end{cases}$$

Then its derivative is

$$f'(x) = \begin{cases} g'(x) &\text{if $x\>c$}\\ h'(x) &\text{otherwise} \end{cases}$$

with a possible discontinuity at $x=c$.

For conditionals with an equality comparison, things might fail at the value where equality holds (at the boundary value). For conditionals with $\le$ or $\<$ or $\ge$ or $\>$, things might fail at the boundary/threshold value, but it works elsewhere, I think.

Looping is harder, I think.

Markus Mottl's answer is better than mine; see his answer for explanation of why branches and loops are problematic for automatic differentiation.

---
Tags: algorithm-analysis, approximation, turing-completeness, loops
---


# Question
Title: How can we design an efficient divide-and-conquer algorithm for constructing a round-robin tournament?
# Background and main question

I am studying algorithm analysis and design, and have been going through "Algorithm Design and Applications" by Goodrich and Tamassia.

One of the applications problems (A-11.2) poses the following:

> Given a set, P, of n teams in some sport, a round-robin tournament is a collection of games in which each team plays each other team exactly once. Such round-robin tournaments are often used as the first round for establishing the order of teams (and their seedings) for later single- or double-elimination tournaments. Design an efficient algorithm for constructing a round-robin tournament for a set, P, of n teams assuming n is a power of 2.

The chapter is on the divide-and-conquer method, so I am assuming that they intend for us to use a recursive algorithm to solve the problem.

# Approach

I assumed that every team would play in every round (i.e. there is no need for "bye weeks").

I tried to tackle this problem via two different approaches:

1) Place each team in a some sort of collection (or, assign each team an integer, and place those into a collection). Pop the head element from the collection, and make pairs with the elements remaining in the collection. Use these pairs to populate an *n* \- 1 rounds * *n* \- 2 matches grid, where *n*, as in the problem, is the number of teams. Repeat until one element is left in the collection.

This is not a "true" divide-and-conquer approach, and is *O*((*n*-1)!), I believe.

2) Use *n* \- 1, *n* * *n* binary matrices to plot the matches for each round.

This approach is not divide-and-conquer at all. I know intuitively that it will work, but I'm not sure how I would implement it programmatically.

# Conclusion

How can we solve this problem via the divide-and-conquer approach?

What kind of asymptotic behavior can we expect?

# Answer
> 1 votes
**Hint.** Divide the teams into two sections. Every game that needs to be played is either between two teams in the same section, or between teams in different sections. What is the set of games that must be played between teams in the same section?

---
Tags: algorithms, divide-and-conquer
---


title: Finding interesting anagrams

text:
# Question
Title: Finding interesting anagrams
Say that $a\_1a\_2\ldots a\_n$ and $b\_1b\_2\ldots b\_n$ are two strings of the same length. An **anagramming** of two strings is a bijective mapping $p:\[1\ldots n\]\to\[1\ldots n\]$ such that $a\_i = b\_{p(i)}$ for each $i$.

There might be more than one anagramming for the same pair of strings. For example, If $a=$\`abcab\` and $b=$`cabab` we have $p\_1\[1,2,3,4,5\]\to\[4,5,1,2,3\]$ and $p\_2\[1,2,3,4,5\] \to \[2,5,1,4,3\]$, among others.

We'll say that the **weight** $w(p)$ of an anagramming $p$ is the number of cuts one must make in the first string to get chunks that can be rearranged to obtain the second string. Formally, this the number of values of $i\in\[1\ldots n-1\]$ for which $p(i)+1\ne p(i+1)$. That is, it is the number of points at which $p$ does *not* increase by exactly 1.For example, $w(p\_1) = 1$ and $w(p\_2) = 4$, because $p\_1$ cuts `12345` once, into the chunks `123` and `45`, and $p\_2$ cuts `12345` four times, into five chunks.

Suppose there exists an anagramming for two strings $a$ and $b$. Then at least one anagramming must have least weight. Let's say this this one is **lightest**. (There might be multiple lightest anagrammings; I don't care because I am interested only in the weights.)

## Question

I want an algorithm which, given two strings for which an anagramming exists, efficiently **yields the exact weight of the lightest anagramming** of the two strings. It is all right if the algorithm also yields a lightest anagramming, but it need not.

It is a fairly simple matter to generate all anagrammings and weigh them, but there may be many, so I would prefer a method that finds light anagrammings directly.

---

## Motivation

The reason this problem is of interest is as follows. It is very easy to make the computer search the dictionary and find anagrams, pairs of words that contain exactly the same letters. But many of the anagrams produced are uninteresting. For instance, the longest examples to be found in Webster's Second International Dictionary are:

> cholecystoduodenostomy
> duodenocholecystostomy

The problem should be clear: these are uninteresting because they admit a very light anagramming that simply exchanges the `cholecysto`, `duedeno`, and `stomy` sections, for a weight of 2. On the other hand, this much shorter example is much more surprising and interesting:

> coastline
> sectional

Here the lightest anagramming has weight 8.

I have a program that uses this method to locate interesting anagrams, namely those for which all anagrammings are of high weight. But it does this by generating and weighing all possible anagrammings, which is slow.

# Answer
This problem is known as the “minimum common string partition problem.” (More precisely, the answer in the minimum common string partition problem equals the answer in your problem plus 1.) Unfortunately, it is NP-hard, even with the restriction that each letter occurs at most twice in each of the input strings, as is proved by Goldstein, Kilman, and Zheng \[GKZ05\]. This means that no polynomial-time algorithm exists unless P=NP. (Of course, if each letter occurs at most once, then the problem is trivial because there is only one anagramming.)

On the positive side, the same authors \[GKZ05\] give a polynomial-time 1.1037-approximation algorithm under the same restriction. (A “1.1037-approximation algorithm” means an algorithm which may not output the correct answer *A* but is guaranteed to output a value *B* such that *A**B* ≤ 1.1037*A*.) They also give a linear-time 4-approximation algorithm under the weaker restriction that each letter occurs at most three times in each of the input strings.

\[GKZ05\] Avraham Goldstein, Petr Kolman, and Jie Zheng. Minimum common string partition problem: Hardness and approximations. *Electronic Journal of Combinatorics*, 12, article R50, 2005. http://www.combinatorics.org/ojs/index.php/eljc/article/view/v12i1r50
> 21 votes

# Answer
This is a followup to Tsuyoshi Ito's answer above, summarizing the most relevant portion of the GKZ05 paper he cited.

The paper proves a reduction to the Maximal Independent Set (*MIS*) problem. Construct a graph $G$ whose vertices are pairs $(i, j)$ such that $a\_i = b\_j$ and $a\_{i+1} = b\_{j+1}$. Connect vertices $(i, j)$ and $(k, \ell)$ (where $i≤k$) with an edge whenever it is impossible that an anagramming could map all of $i\mapsto j$ and $i+1\mapsto j+1$ and $k\mapsto\ell$ and $k+1\mapsto\ell+1$. This is easy to detect; such a mapping is impossible exactly if one of the following holds:

1. $i=k$ and $j\ne\ell$
2. $i+1=k$ and $j+1\ne\ell$
3. $i+1\<k$ and $\\{j, j+1\\}$ is disjoint from $\\{\ell, \ell+1\\}$

Say the resulting graph $G$ has a maximal independent set of size $s$. Then the minimum anagramming weight is exactly $n-s-1$, where $n$ is the length of the strings $a$ and $b$. (The converse holds also: a low-weight anagramming translates directly into a large MIS for $G$. For details, see pp. 4–5 of the paper.)

For example, consider the two strings `yttrious` and `touristy`. The corresponding graph has two vertices, one for the shared `ou` pair and one for the shared `ri` pair. There is no edge between the vertices, because it is possible to have an anagramming that maps both `ou` to `ou` and `ri` to `ri`; or one can check that the three conditions above all fail. So the graph obviously has a MIS of size $s=2$ and the minimum anagramming weight is indeed 8-2-1=5, corresponding to the anagramming `y|t|t|ri|ou|s``t|ou|ri|s|t|y`.'

On the other hand, consider `derater` and `treader`. This time the graph has three vertices:

1. `DErater` \+ `treaDEr`
2. `dERater` \+ `treadER`
3. `deratER` \+ `treadER`

2 and 3 are incompatible, and 1 and 3 are incompatible, but 1 and 2 are compatible. So the unique MIS has size $s=2$ and contains vertices 1 and 2. The corresponding anagramming of weight 7-2-1=4 is `der|a|t|e|r``t|r|e|a|der`.
> 9 votes

# Answer
It doesn't cover the exact algorithm you had in mind (which Tsuyoshi Ito's answer does), but trying to get at the underlying problem of finding "interesting" anagrams...

My first thought was to use some variation on edit-distance, where the atomic changes are weighted according to their "interestingness" rather than the usual "difficulty" or "confusability" weightings. Of course, it seems unlikely that you can efficiently encode the really interesting transformations in this way, since they're likely to be non-local and hence run into the NP-complete issues of MIS, etc.

So, second thought would be to construct a letter-to-letter alignment between the words (à la machine translation alignments), and then to score the alignments themselves for "interestingness" (e.g., counting the alignments that take adjacent letters to non-adjacent letters, or how many alignments each alignment crosses, etc; and then combine them all via loglinear model or such).

Third idea is to completely abandon looking at the structure of the anagramming itself, and instead look at the semantics of the words. Often what makes an anagram "interesting" is the incongruity between the meanings of the words involved. So try something like computing their distance in WordNet, or similar.
> 2 votes

# Answer
The problem can be phrased in terms of permutation groups.

Now a permutation group contains all the "anagram moves", both primitive (swapping two letters) and composite of sequences of primitive moves. It seems that you are interested in only a subset of the possible permutations. I will attempt to define these.

First, recall the notation for permutations, namely, the so-called cycle notation:

* $()$ means no permutation.
* $(1)$ means 1 is swapped with 1, which is also no permutation.
* $(12)$ means 1 and 2 are swapped.
* $(123)$ means 1 replaces 2 which replaces 3 which replaces 1 (a rotation).
* and so one

These simple 'cycles' are composed to describe more complex permutations.

It seems that the moves you are interested in are (for a word of length $n$):

* swaps of pairs of single characters: these are the swaps such as $(12)$
* swaps of pairs of 2 consecutive characters: these are permutations of the form $(a\ b)(a+1\ b+1)$, where $a\>0$ and $b\<a+1$ and $b+1\le n$
* ...
* swaps of pairs of n consecutive characters: these are permutations of the form $(a\ b)(a+1\ b+1)\cdots(a+i-1\ b+i-1)$ where $a\>0$, $a+i-1\le b$, and $b+i-1\le n$.

These moves form the basis for your algorithm. What you are interested in is finding the smallest sequence of these moves to move from one word to the next.

I don't know any algorithm for computing this, apart from the brute force search, but at least now there is a clearer (I hope) description of what the primitive moves are. (And maybe some group theorist among us can point to an appropriate algorithm.)
> 0 votes

# Answer
For cholecystoduodenostomy/duodenocholecystostome, I notice that if you assigned a number to each character describing how much it was moved as a delta, you would have some thing like 7 7's, then 8 -7s, then 6 0's. That is not right because some chars may have been repeated (the second c only moved forward 2, not back 7) etc but still very "run length encodable" because you see the same deltas in a row.

Compare to coastline/sectional, where you see something like (+2)(+5)(+5)(-3)(-1)(+3)....much less "run length encodable".

Perhaps the randomness of the deltas could give you a "score" as to how interesting the anagram is?
> 0 votes

---
Tags: algorithms, strings, search-algorithms, natural-language-processing
---


title: Question involving regular expressions

text:
# Question
Title: Question involving regular expressions
I've been playing around with converting regular languages to regular expressions and was wondering if my thinking is correct for this one.

Question:

**The set of all strings that begin or end with a doubled digit, either 11 or 00.**  *(In all cases assume the alphabet is {0,1})*.

So far, I have: $((11+00) + (1 + 0)^\*) + ((1+0)^\*(11 + 00))$.

My thinking is that we want to take the union of: the set of strings that start with 11 or 00 followed by any sequence of 1's and 0's AND the set of strings that end with 11 or 00 preceded by any sequence of 1's and 0's.

Sorry for the somewhat clunky writing.....still trying to get the hang of styling my questions.

# Answer
> 0 votes
You are thinking correctly but a small error is there in writing the regular expression. The regular expression is $r = ((00+11)(0+1)^\*)+((0+1)^\*(00+11))$.

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


# Question
Title: How can I restructure matrices to have non-zero elements close to the diagonal?
I have a matrix $C \in \mathbb{N}^{n \times n}$. Semantically, it is a confusion matrix where the element $c\_{ij}$ denotes how often members of class $i$ are predicted by a given classifier as members of class $j$.

The order of elements does not matter, but $c\_{ii}$ has to be the correct predction of class $i$. So for any given matrix $C$ you can swap columns if you swap the same rows.

How can I order the classes $1, \dots, n$ so that the biggest elements are close to the diagonal?

I thought one might pose this as an optimization problem, e.g. minimize $$\sum\_{i = 1}^n \sum\_{j=1}^n C\_{ij} \cdot {|i-j|}$$

How could I minimize this?

## Code and example

I've already visualized a $369 \times 369$ matrix without any optimization. The confuscation matrix as JSON file and the code are here.

Without modification, you get a score of `303535` for:

This looks as if there could be some improvement. A quick first thought was to just randomly swap rows. Letting this run for $10^4$ steps (~5 minutes) leads to a score of `82552` and a visualization which looks a bit cleaner:

Doing this, I realized that my score might also need some improvement. I instead of moving elements to the diagonal, it would be nice if big blocks within the matrix would only contain zeros.

The total number of possibilities to arrange the items in $C$ is equal to the number of permutations of a list of length $n$ and hence it is $n!$. Hence for $369$ classes it is already $369! \approx 10^{788}$ - too much to brute force.

## See also

# Answer
The random swapping approach (simulated annealing with extremely low temperature) yields to a score of `64496` (20 minutes or so with Python and seed 0, ~60s with C++ and playing with seeds by a friend -.-). The permutation is

```
[213, 201, 367, 34, 368, 174, 249, 193, 159, 275, 225, 276, 194, 300, 191, 362, 113, 230, 158, 5, 4, 16, 352, 126, 265, 49, 224, 139, 187, 221, 228, 192, 156, 205, 204, 203, 241, 208, 214, 166, 67, 40, 52, 283, 124, 354, 133, 152, 173, 206, 235, 231, 237, 223, 217, 138, 118, 277, 361, 269, 344, 98, 258, 251, 30, 119, 122, 339, 309, 240, 245, 26, 226, 242, 232, 218, 110, 172, 86, 282, 297, 137, 21, 146, 62, 29, 293, 189, 171, 210, 84, 250, 136, 3, 304, 335, 154, 292, 78, 11, 266, 116, 164, 129, 148, 144, 195, 327, 306, 337, 9, 47, 168, 120, 128, 259, 261, 323, 254, 121, 200, 183, 256, 246, 85, 72, 305, 77, 76, 255, 336, 55, 46, 89, 73, 341, 100, 294, 145, 163, 87, 37, 185, 199, 15, 313, 88, 268, 264, 273, 69, 59, 44, 2, 106, 303, 82, 149, 326, 197, 279, 111, 38, 366, 57, 329, 68, 340, 257, 334, 93, 295, 286, 353, 365, 298, 285, 364, 91, 92, 90, 316, 252, 19, 165, 342, 125, 274, 176, 143, 239, 288, 95, 96, 324, 325, 28, 212, 253, 81, 79, 80, 318, 94, 299, 71, 291, 64, 132, 23, 278, 338, 308, 160, 7, 115, 247, 347, 147, 271, 188, 281, 272, 280, 155, 35, 349, 157, 177, 180, 202, 108, 350, 345, 97, 51, 141, 284, 355, 179, 42, 33, 70, 99, 45, 109, 178, 181, 103, 207, 220, 102, 211, 209, 196, 127, 41, 346, 351, 359, 320, 311, 13, 43, 287, 328, 357, 83, 310, 12, 161, 135, 131, 360, 39, 302, 1, 322, 123, 167, 6, 117, 31, 330, 356, 74, 75, 151, 104, 262, 289, 296, 140, 101, 236, 312, 343, 150, 348, 56, 234, 27, 14, 114, 331, 260, 314, 17, 54, 321, 105, 263, 130, 20, 186, 190, 63, 22, 162, 134, 363, 333, 301, 0, 169, 170, 175, 10, 112, 317, 61, 50, 248, 18, 315, 60, 32, 222, 244, 290, 48, 36, 307, 184, 58, 233, 238, 229, 227, 219, 153, 66, 319, 332, 358, 25, 53, 270, 182, 8, 216, 65, 24, 267, 107, 215, 142, 198, 243]

```

which corresponds to the symbol classes

```
['\blacktriangleright', '\nvDash', '\AE', '7', '\guillemotleft', '\perp',
'\bot', '\therefore', '\boxtimes', '\vdots', '\Leftarrow',
'\ddots', '\because', '\iddots',
'\multimap', '\L', '+', '\nearrow', '\boxplus', 'F', 'E', 'Q', '\checked', '\checkmark', '\rceil', 'h', '\uparrow',
'\div', '\doteq', '\longmapsto', '\mapsto', '\pitchfork', '\boxdot',
'\varsubsetneq', '\subsetneq', '\nsubseteq', '\nRightarrow', '\gtrless', '\triangleq', '\parr', '\Sigma', '\sum', 'k', '\sharp', '\#', '\sun', '\ast', '\star', '\not\equiv', '\neq', '\rightleftarrows',
'\rightleftharpoons', '\rightrightarrows', '\Longrightarrow', '\Rightarrow', '\pm',
'\dots', '\dotsc', '\aa', ']', '\ohm', '\Omega',
'\exists', '\ni', '3', '\}', '\pounds', '\mathscr{L}', '\mathcal{L}',
'\twoheadrightarrow', '\shortrightarrow', '\rightarrow', '\longrightarrow',
'\nrightarrow', '\rightharpoonup', '\hookrightarrow', '\cong', '\equiv',
'\Xi', '\diamondsuit', '\lozenge', '\diamond', 'V', '\vee', 'v', '2', '\sphericalangle', '\simeq', '\approx', '\gtrsim', '\nu', '\forall', '\triangleright',
'D', '\mathcal{D}', '\mathscr{D}',
'\barwedge', '\sqrt{}', '\iota', 'L', '\lfloor', '\{', '\coprod', '\amalg', '\sqcup', '\mp', '\between', '\mathds{E}', '\mathcal{F}', '\mathscr{F}', 'J', 'f', '\fint', '\S', '\mathsection', '\Im', '\nexists', '\mathfrak{X}', '\hbar', '\dag', '\nmid', '\vdash', '\notin', '\lightning', '\xi', '\zeta', '\mathcal{E}', '\varepsilon', '\epsilon', '\in', '\mathscr{E}', 'n', 'e', '\varrho', '\eta', '\mathscr{S}', '\int', '\square', '\sqcap', '\prod', '\Pi', '\pi', '\models', '\vDash', 'P', '\mathcal{P}', '\rho', '[', '\lceil', '\llbracket', '\Gamma', 'r', 'c', 'C', '\subset',
'\mathcal{C}', '\Lambda', '\wedge', '\mathds{C}', '\varpropto', '\infty', '\propto', '\alpha', '\ae', 'p', '\mathds{P}', '\gamma', '\mathscr{P}',
'\wp', '\mathscr{C}', '\varphi', '\triangledown', '\nabla', '\diameter',
'\o', '\varnothing', '\emptyset', '\O', '\phi', '\Phi', '\tau',
'\mathcal{T}', '\top', 'T', '\oint', '\celsius', '\%', '\rrbracket', '\frown', '\cap', '\curvearrowright', '\clubsuit', '\psi', '\Psi', '\mathbb{1}', '\mathds{1}', '1', '\trianglelefteq', '\ell', '\lambda',
'\kappa', '\varkappa', '\mathcal{X}', '\chi', '\vartriangle', '\Delta',
'\triangle', 'x', '\times', 'X', '\aleph', '\mathscr{H}', '\mathcal{H}',
'\rtimes', 'H', '\$', '\vartheta', '\astrosun', '\odot',
'\|', '\parallel', '\angle', '/', '\prime', '\circledcirc', '8', '\leftmoon',
'\ltimes', '\prec', '\preceq', '\sqsubseteq', '\subseteq', '\female',
'\venus', '\omega', 'j', '\setminus', '\backslash', '\Bowtie', '\bowtie',
'a', '6', '\delta', '\partial', 'd', '\supseteq', '\succ', '\succeq',
'\geq', '\geqslant', '\searrow', '\leq', '\leqslant', '\lesssim',
'\preccurlyeq', '\circledR', '\sigma', '\mars', '\male', '\mathbb{H}',
'\mathfrak{A}',
'\mathcal{N}', 'N', 'b', '\flat', '\mathds{N}', '\mathbb{N}', '\mu', '\mathcal{M}', 'M',
'\circledast', '\otimes',
'\oplus', '\ss', '\beta', '\mathcal{B}', 'B', '\mathfrak{S}', '\&',
'\with', 'G', '\copyright', '4', '\mathds{Q}', '\mathbb{Q}', '\theta',
'\Theta', '\ominus', '<', '\langle', '\heartsuit', '\blacksquare',
'\bullet', '\cdot', '\circlearrowright', '\mathcal{O}', '\degree',
'\circ', '\fullmoon', 'o', '\circlearrowleft', '0', 'O',
'\mathbb{R}', '\mathds{R}', '\Re', '\mathcal{R}', 'R',
'm', '\mathfrak{M}', '>', '\rangle', '\cup', 'U', '\sim', '\backsim', 'w', 'W', '\lhd', '\triangleleft', '\AA', '\mathscr{A}', '\mathcal{A}', 'A', '\varoiint', '\oiint', '\asymp', 'K', '-', '\mathcal{U}', 'u', 'i', '\varpi', 'S',
'\mathcal{S}', 's', '5', '\leftarrow', '\mapsfrom', '\neg', 'g', '9',
'\mathcal{G}', '\dashv', 'q',
'\leadsto', '\rightsquigarrow', '\leftrightarrow', '\Leftrightarrow', '\Longleftrightarrow',
'\wr', 'z', '\mathcal{Z}', '\mathds{Z}', '\mathbb{Z}', 'Z',
'l', '|', '\mid', 'I', '\downarrow',
'y', 'Y', '\rfloor', '\supset', '\Downarrow', '\uplus', '\Vdash', '\upharpoonright']

```

As expected, this method automatically finds groups of classes which are similar, such as `'D', '\mathcal{D}', '\mathscr{D}'`.

It leads to the following confusion matrix:

## Thoughs about good solutions / minima

This optimization problem will most likely get the best results if all groups of similar classes are together. For this dataset, the groups are D-shaped, O-shaped, arrow-shaped, ...

For a good classifier, it is expected that there are many errors between members of a group and few (even none) between groups. Hence the ordering of groups does not matter (much).

If the classifier can distinguish many classes really well, a lot of groups exist. If there are $k$ groups, there will be $k!$ solutions to the confusion matrix optimization problem which will have almost the same score. For the HASYv2 dataset and the CNN classifier I expect there to be at least 50 groups (hence $50! \approx 10^{64}$ similar solutions which are all close to the minima / minimum.
> 2 votes

---
Tags: optimization, matrices
---


# Question
Title: Upper bound for the union of $n$ DFAs of size at most $m$?
Let $\Sigma$ be an alphabet of size $2$, and let's consider $n$ regular languages $L\_i \subseteq \Sigma^\*$ respectively recognized by $n$ minimal DFAs $D\_i$ whose size are bounded by $m$. As the number $k$ of minimal DFAs of size at most $m$ is finite, there exists a function $f$ that returns this number $k=f(m)$.

Let $L \subseteq \Sigma^\*$ be the language resulting from the union of the $n$ regular languages $L\_i$.

Is the size of the smallest DFA $D\_L$ recognizing $L$ always below $m^{f(m)}$ ?

And if so, how can we find a precise definition/close-form of $f(m)$ ?

My intuition is as follows : the size of a DFA resulting from the union of two DFAs $A$ and $B$ is not greater than $|A|.|B|$. Thus, if there are not more than $f(m)$ minimal DFAs of size at most $m$ then the size of the minimal DFA for the union of the $D\_i$ can not exceed $m^{f(m)}$. Sounds correct ?

Considering that for $|\Sigma|=2$ the transition function of a DFA of size at most $m$ is a graph. Since the nodes degree is bounded by $2$, for each node there are $m^2$ possibilities of pairs of arcs. In this graph there are at most $m$ possible choices of initial state and at most $2^m$ possible choices of final states sets. Thus, the maximum number of DFAs of size at most $m$ is $f(m) \leq m^{2m}.m.2^m = 2^m.m^{2m+1}$.

Thus we can conclude that for $|\Sigma|=2$ the maximal number of states required for the union of $n$ DFAs of size at most $m$ is bounded by $m^{f(m)} = m^{2^m.m^{2m+1}}$.

We can then generalize to an arbitrary alphabet $\Sigma$ : the bound becomes $f(m) \le 2^m.m^{|\Sigma|m+1}$. But it looks like this bound could be tighter though...

Does someone have a better estimate ?

One motivation to find a tighter bound is that if we fix the amount $S$ (in number of states) of memory that is available on a computer then we could easily get the maximal size $m$ that the $n$ DFAs must not exceed in order to guarantee the complete computation of the minimal DFA $D\_L$ for the union of the $n$ DFAs.

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

Many thanks, Luz

# Answer
> 1 votes
Yes. There is a simple proof.

You say that $L\_i$ are recognized by DFAs of size $\le m$, and that there are at most $f(m)$ possible such DFAs. Therefore, there are at most $f(m)$ possible such languages. If $n \ge f(m)$, then $L\_1,\dots,L\_n$ must contain some repetitions (some language appears multiple times). Remove all repeated instances, so the $L\_i$ are unique. Then at that point we have $n \le f(m)$. In other words, without loss of generality we can assume $n \le f(m)$.

Now the union of $n$ such languages can be recognized by a DFA of size at most $m^n$ (by a product construction), and $n \le f(m)$, so the union of $n$ such languages can be recognized by a DFA of size at most $m^{f(m)}$.

# Answer
> 0 votes
A better upper bound for $f(m)$ is given in this post with $f(m) \leq \frac{2^m.m^{|\Sigma|m}}{(m-1)!}$.

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


title: Removing Epsilon Transitions?

text:
# Question
Title: Removing Epsilon Transitions?
I've run into a problem concerning epsilon transitions and removing them. Specifically, it is to do with the picture seen in this post. My problem is that I am unsure of what to do with q1. I've already attempted to solve it but I don't know if it's correct. Should it just sit there still with no inputs going to it essentially making it a dead state? What should its loop be that was once an epsilon loop?

Thanks, all help appreciated!

# Answer
> 1 votes
In the original automaton, there is no way to be in $q\_1$, read one symbol, and end up in $q\_1$, so in the resulting automaton, there is no loop on $q\_1$.

# Answer
> 0 votes
There won't be a loop over $q\_1$ but there will be a transition $q\_1\in\delta(q\_0,0)$, so it won't be dead state.

---
Tags: finite-automata
---


# Question
Title: Most Efficient Way to List All $n$-bit Permutations
Suppose we are tasked with expressing a randomized list of all numbers up to but excluding $2^n$ (ie. a random list of all n-bit numbers). What are some efficient ways to do such a listing using as few bits as possible?

**Attempt:** My thought is that the verbose listing of all $n$-bit numbers has a lot of redundancy, so if we start by listing all $2^n$ numbers, $2^{n-1}$ of those numbers will have a number that is identical except for one bit (that has been previously listed)––so we can drop the $n^{th}$ bit of those $2^{n-1}$ numbers. Now among that same set of $2^{n-1}$ numbers, there will be $2^{n-2}$ values that will have a number that is identical until the last *two* bits, so we can drop the $n-1^{th}$ bit of those $2^{n-2}$ numbers as well. Continuing on iteratively, we can find $2^{n-k}$ numbers that can have the final bit dropped, with $k=1,2,3,4,...n$. Finally, there is one number that can be eliminated entirely (intuitively, this makes sense because the last number in a known set can always be determined if we know all others).

Here is an example that lists all 3-bit numbers (in increasing order):

* 000
* 00
* 010
* 0
* 100
* 10
* 110
* .

It seems like we can model the number of bits this method uses as such: $$2^{n-1}n + 2^{n-2}(n-1) + ... + 2^1(2) + 2^{0}(1) = \sum\_{k=0}^{n-1} 2^k(k+1) = 2^n(n-1)+1$$

(saving $2^n -1$ bits from the verbose $2^n\*n$ version)

# Answer
> 2 votes
Since $n$ is known from the start, you know that there are exactly $2^n!$ possible lists. Calculate the index of your list in a lexical ordering of all permutations, and then write that number using $\lceil log\_2(2^n!)\rceil$ bits.

In practice, you can come arbitrarily close to this bound using arithmetic encoding, without having to manipulate very large integers.

---
Tags: efficiency, permutations, storage
---


title: From CNF to ILP?

text:
# Question
Title: From CNF to ILP?
Can we transform a CNF to ILP without introducing new variables?

My question can be seen as a follow up to Express boolean logic operations in zero-one integer linear programming (ILP) as the solution proposed in that post introduces additional variables.

Also, my current understanding is that each 0 value in the truth table is represented by one linear inequality. This means that if my boolean function is of 16 input variables and balanced, there will be 2^15 linear inequalities so is there a way to reduce the number of inequalities?

# Answer
No. Usually (for most functions / CNF formulas) you'll need additional variables. Linear inequalities form a convex space. If the set of solutions such that $f(x)=1$ is not convex, you'll need additional variables.

The exact number of additional variables and inequalities required depends on the function / on the CNF formula.
> 1 votes

---
Tags: integer-programming
---


# Question
Title: which Pipelining architecture, should i use and how to distinguish them!
Is there any specific architecture to pipelining that we must follow to perform "operand-forwarding" inorder to avoid its harzards?

My tutor seem to have, there are different architecture. And he taught us 3 different, and i am not even sure how to know which one to use.

# Answer
In computer architecture, there is absolutely nothing that you *must* do. There are always compromises, everything has advantages and disadvantages, and advantages and disadvantages change over time.

If you learned about three different architectures to achieve the same goal, you first check how each architecture fits in with the overall design, and then you invent a fourth one that works better. Your tutor can only tell you how things were done in the past; you'll have to find yourself how things will be done in the future.
> 2 votes

---
Tags: cpu-pipelines
---


title: Is 2QBF in P^NP?

text:
# Question
Title: Is 2QBF in P^NP?
2QBF is the following problem: given a CNF formula $\psi$ on $2n$ variables, determine the truth value of

$$\forall x \in \\{0,1\\}^n . \exists y \in \\{0,1\\}^n . \psi(x,y).$$

Question: Is 2QBF in $P^{NP}$ (or, expected to be in $P^{NP}$, under standard conjectures)?

Motivation: If the answer were yes, it would suggest a way to solve 2QBF, using multiple invocations of a SAT solver. Given that SAT solvers are surprisingly effective on some problems, that might be of interest in situations where we need to solve 2QBF.

(2QBF is a version of QBF restricted to two alternating quantifiers. QBF is known to be PSPACE-complete, but 2QBF seems easier than QBF.)

# Answer
> 1 votes
Determining the truth of $\exists \forall. \phi$ formulas is $\Sigma\_2^P$-complete whereas determining the truth of $\forall \exists. \phi$ formulas are $\Pi\_2^P$-complete. Therefore, unless $\Sigma\_2^P=P^{NP}$ (resp., $\Pi\_2^P=P^{NP}$) neither of these problems can be solved in $P^{NP}$.

# Answer
> 1 votes
2QBF (in the form presented in the question) is $\Pi\_2^P$-complete. Also, $P^{NP} = \Delta\_2^P = P^{coNP}$ and $\Pi\_2^P = coNP^{coNP}$.

Therefore, if 2QBF is in $P^{NP}$, then $\Pi\_2^P = \Delta\_2^P$, from which it follows that $\Pi\_2^P = \Pi\_3^P$ (since $P^{coNP} = coNP^{coNP}$ implies $\Pi\_3^P = coNP^{coNP^{coNP}} = coNP^{P^{coNP}} = coNP^{coNP} = \Pi\_2^P$), which means that the polynomial hierarchy collapses -- something that is conjectured not to happen.

Therefore, under standard conjectures (that the polynomial hierarchy doesn't collapse), 2QBF is not in $P^{NP}$. In other words, there is no general way to solve 2QBF using polynomially invocations of a SAT solver.

---
Tags: complexity-theory, logic, satisfiability, boolean-algebra
---


# Question
Title: Randomly select a uniform subsample from a nonuniform dataset
I have a dataset of events with timestamps spanning several months. The event rate is "bursty", i.e. there are periods of much higher and lower rate than the average. I would like to randomly select a subset of these events having approximately uniform time distribution. What weight should be applied to the random sampling?

One approach I've already considered is to histogram the data and weight samples by 1/binheight, but this ends up being dependent on the binning chosen and runs into problems with very sparse samples.

Can the appropriate method also be extended to another, possibly related parameter? For example, I may have a unix timestamp (1 second resolution) and another parameter measuring phase of the 60 Hz AC power line. My subsample should be uniform in both dimensions.

# Answer
One approach would be to weight each timestamp with the time since the previous timestamp. In other words, sort the timestamps in increasing order and then let the timestamps be $t\_1,t\_2,\dots$. Now, weight the timestamp $t\_i$ with weight proportional to $t\_i-t\_{i-1}$. Finally, sample from the timestamps, choosing each possible timestamp with a probability proportional to its weight. This will ensure that the selected timestamps are distributed uniformly across time.

You can also look at variants of this, where you do some kind of smoothing. For instance, given a timestamp $t\_i$, you can look at the 5 previous timestamps, compute the average duration between them, and choose a weight based on that; this amounts to choosing $t\_i$ with probability proportional to $t\_i - t\_{i-5}$. Or, you can choose a fixed duration $d$, and choose a timestamp $t\_i$ with probability that is proportional to the number of events that occur in the window $(t\_i-d,t\_i\]$ (i.e., proportional to $|\\{j : t\_i-d \< t\_j \le t\_i\\}|$). The latter is similar to your histogramming idea, so might be a bad choice -- the problem is that you have to choose a fixed duration $d$, which might be problematic. So try my other suggestions.

---

There's no way in general to choose a sample that is simultaneously uniform in both dimensions. For instance, suppose your timestamps are evenly spaced through time, where the earliest 80% have phase 0 and the latest 20% have phase 1; then there's no distribution on timestamps that is simultaneously uniformly distributed in time and uniformly distributed in phase. However, you can choose one sample that is uniform in one dimension, and uniform in another dimension.
> 0 votes

---
Tags: algorithms, randomness, sampling
---


# Question
Title: When an ISAM index is built, how is the number of leaf nodes per index node (the "fan-out") calculated?
I asked this question on DB.SE but it didn't get any traction, so I'll ask it here...

The following statement is in the Ramakrishnan text (2nd ed. page 252):

(emphasis in bold is mine)

> The non-leaf pages direct a search to the correct leaf page. **The number of disk I/Os is equal to the number of levels of the tree and is equal to $log\_FN$, where $N$ is the number of primary leaf pages and the fan-out $F$ is the number of children per index page.** This number is considerably less than the number of disk I/Os for binary search, which is $log\_2N$; in fact, it is reduced further by pinning the root page in memory. The cost of access via a one-level index is $log\_2(N/F)$. If we consider a file with $1,000,000$ records, $10$ records per leaf page, and $100$ entries per index page, the cost (in page I/Os) of a file scan is $100,000$, a binary search of the sorted data file is $17$, a binary search of a one-level index is $10$, and the ISAM file (assuming no overflow) is $3$.

**Question: How is the value of *F* calculated when the index is constructed?**

From the example given it seems the structure will be:

* root node containing 1,000 pointers to index nodes
* one level of 1,000 index nodes, each containing a pointer to 100 leaf nodes
* 100,000 leaf nodes, each containing ten records

Assuming that is the correct understanding of what he describes, what determines the value of $F$ when the index is built? Is it calculated in such a way that the index will have exactly 3 levels and so $F$ is set to ensure we can reach all leaf nodes in 3 steps? This doesn't seem to be the case since he has a diagram elsewhere in the book of an ISAM index with more than 3 levels.

So then what dictates the value of $F$? i.e. what keeps it from being 1K or 100K?

# Answer
> 2 votes
In a page-structured file, each page has a fixed size. This effectively eliminates internal fragmentation.

Each index page needs to store a bunch of keys and corresponding pointers to other disk pages. The number of keys-and-pointers that can be stored in a disk page is what determines F.

So how big is a page?

In a real-world DBMS, the lower limit is the virtual memory page size, which is determined by the hardware and the operating system. The physical block size of a disk is typically smaller than this, so that's not a concern. Setting your file page size to be some multiple of the VM page size lets the operating system buffer cache act as the database buffer cache.

The upper limit is set by efficiency considerations, since pages which are too big require more I/O and also potentially wastes space when pages are under-full.

So in practice, a small power-of-two multiple of the VM page size is appropriate.

---
Tags: trees, search-trees, database-theory
---


title: Lazy concatenative functional language

text:
# Question
Title: Lazy concatenative functional language
Can the idea of concatenative programming languages be extended to call-by-need evaluation strategy?

I see some problems that I will explain with few examples. I will use a prefix instead of a postfix notation, so evaluation takes place from left to right.

Duplicate an argument seems trivial:

```
drop A B  ->  B

```

However, we can not forget that A is unevaluated, so the previous example only work for literals or quotations, but not for unevaluated code:

```
drop 123 B      ->  B
drop "abc" B    ->  B
drop [+ 1 2] B  ->  B
drop + 1 2 B    ->  1 2 B  -- NON SENSE!

```

This can be solved in two ways. First, we can impose some structure (unflat) to the code based on the functions arity in the parsing stage:

```
drop + 1 2 B    ->  drop [+ 1 2] B  // at parse time
drop [+ 1 2] B  ->  B               // at run time

```

The problem with this approach is that we lose all the benefits of concatenative programming (for example, flatness and multiple return values). In fact, we are converting function composition to function application in prefix notation... In this case:

```
dup + dup 2 3

```

Naively translates to:

```
dup [+ [dup 2] 3]  ->  dup [+ 2 2 3]  // `+` arity mismatch. What to do with the extra value? Which one is it, 2 or 3?

```

But it result in an strict language is:

```
4 4 3

```

The second solution is to instruct the evaluator to reduce the stack just enough to get as many arguments as the current word needs:

```
drop + 1 2 B  ->  drop 3 B  ->  B

```

Looks good, but the target of lazy evaluation is to evaluate arguments only when needed. In this case we are evaluating `+ 1 2` needlessly. It is not a big problem until we found:

```
drop + bottom 2 B  ->  bottom

```

What contradicts the expected call-by-need semantics:

```
drop + bottom 2 B  ->  B

```

# Answer
It can be done. Here's a presentation explaining the language and how the compiler works (so far).

You can play with an asm.js version at http://hackerfoo.com/eval.html
> 6 votes

---
Tags: programming-languages, functional-programming, language-design
---


# Question
Title: Vertex cover algorithms for directed graphs?
I've recently been working on a problem that I believe can be expressed as a vertex cover problem over a *directed* graph.

Formally, I have a graph $G = (V,E)$ where $V$ is a vertex set and $E$ is a set of edges between vertices. The edges are directed so we can have $e\_{ij} = 1$ but $e\_{ji} = 0$ where $i,j \in V$. Here, $e\_{ji} = 0$ would mean that there is no edge from $j$ to $i$.

My problem is as follows. I would like to find the *smallest* subset of vertices $S \subseteq V$ such that there is a *path* from every vertex in S to every vertex to V. That is, for every vertex $j \in V$, there is an $i \in S$ such that either:

* $e\_{i,j} \> 0$ (edge between $i$ and $j$)
* $e\_{i,{k\_1}}e\_{{k\_1,k\_2}}$...$e\_{{k\_t,j}} \> 0$ (path from $i$ to $j$)

I will assume that $e\_{ii} = 1$ to ensure that such a subset exists, as I can set $S = V$. However, this is only optimal when the set of nodes is entirely disconnected.

I'm wondering if this a vertex cover problem? If so, are there algorithms for this problem? I'm slightly confused because most vertex cover algorithms are for problems where the graph is *undirected* (e.g., $e\_{ij} = e\_{ji}$). If not, are there algorithms to solve this problem?

# Answer
> 5 votes
Thanks for the edit! This isn't vertex cover; it's something different.

There are simple algorithms for this problem. Decompose the graph into a dag of strongly connected components. (The dag is sometimes called "the metagraph".) Each source vertex in the dag corresponds to a SCC that has no edges coming into it from outside; for each such SCC, pick one vertex and add it to $S$.

The result will be the smallest set $S$ that meets your conditions. This can be done in $O(V+E)$ time.

---

Answer to the original version of your question (now irrelevant):

Your problem, as stated, is trivial: the solution is the empty set $S=\emptyset$.

If, on the other hand, you meant that $e\_{ij} \> 0$ implies $i \in S$, the problem is also trivial: the set $S$ has to include the source vertex of every edge. So, you just loop over all the edges $(i,j)$ and add $i$ to $S$.

# Answer
> 3 votes
The problem you're describing sounds more like a Dominating Set style problem to me (vertices covering vertices, Vertex Cover is vertices covering edges), but because you allow the dominating vertex to be at any distance from the dominated vertex, the problem becomes much easier.

I believe the problem can in fact be solved in (near) linear time (in the number of vertices).

Firstly, if we take a strongly connected component, then any vertex in that component will dominate every other vertex in the component (because there's a path from any vertex to any other in that component).

We can compute an auxiliary graph $H = (C,F)$ from $G$ (using any of the algorithms listed on the strongly connected component page) in $O(n)$ time where each strongly connected component is represented by a vertex in $C$, and there is an edge from $c\_{1} \in C$ to $c\_{2} \in C$ if there is an edge from any vertex in the component represented by $c\_{1}$ to any vertex in the component represented by $c\_{2}$.

Note that $H$ must be a acyclic (i.e. it's a DAG).

Now we solve the original problem on $H$ to get a set $S\_{H}$. The key is that $S\_{H}$ must be the set of all sources in $H$ (a source being a vertex with only out-edges, or more precisely, $i \in C$ is a source if for every $j \in C$ we have $e\_{ji} \notin F$). Why is this true? There is no path to a source from any other vertex, so each source must be in $S\_{H}$, but for every non-source vertex, there is (by definition) a path to it from a source, so it must be dominated by at least that source vertex. So the set of all sources is the minimum set that satisfies the requirements.

We can get all the sources by simply looking at each $c\_{i} \in C$ and counting it's in-degree, if it's $0$, it's a source (this is the point where the linear time claim may fall down, it depends highly on your data structures).

Then for each source $c\_{i}$ in $S\_{H}$ from $H$ we can construct the full solution $S$ for $G$ by simply taking a single vertex from each source $c\_{i}$ and adding it to $S$ (also implying that $|S\_{H}| = |S|$).

---
Tags: graphs, greedy-algorithms, set-cover
---


title: Convert PEG to BNF

text:
# Question
Title: Convert PEG to BNF
Parsing expression grammars (PEGs) are unambiguous and have a superficially similar syntax to BNF, but include three important differences:

1. The ordered choice operator `e1 / e2 / e3`.
2. The and predicate `&`.
3. The not operator `!`.

I have a few questions:

1. Are the languages recognized by PEGs all context-free?
2. If the answer to (1) is no, are there any expressive grammar formalisms guaranteed to produce only unambiguous grammars? In particular, would dropping `&` and `!` yield only context-free grammars?
3. If all PEGs are context-free, can they converted into an *equivalent* BNF via an algorithm?

The context is that I'd like to compute generating functions for a PEG library using the Chomsky–Schützenberger enumeration theorem. This seems to require a specification of the grammar in a standard form similar to BNF.

# Answer
> 6 votes
> 1. Are the languages recognized by PEGs all context-free?

No, as is pointed out by Brian Ford in his 2004 paper introducing PEGs, from which is the following short quote:

> **Theorem:** The class of PELs includes non-context-free languages.
>
> **Proof:** The classic example language $a^nb^nc^n$ is not context-free, but we can recognize it with a PEG $G = (\\{A, B, D\\}, \\{a, b, c\\}, R, D)$, where R contains the following definitions: $$A \leftarrow aAb / ε$$ $$B \leftarrow bBc / ε$$ $$D \leftarrow \\&(A !b) a^∗ B !.$$

> 2. If the answer to (1) is no, are there any expressive grammar formalisms guaranteed to produce only unambiguous grammars? In particular, would dropping $\\&$ and $!$ yield only context-free grammars?

Even without $!$ (and therefore without $\\&$, since it is formally defined in terms of $!$), you would still have to deal with the implicit complement hidden in the definition of ordered choice. I don't have a concrete example of ordered choice leading to a non-CFL, but I would try to find one by starting with two CFGs $L\_1$ and $L\_2$ whose difference is not a CFL and which can be converted to PEGs $P\_1$ and $P\_2$. Now, if $\mathbb{c}$ is some symbol not in either language, then the PEG $P\_2 / P\_1\mathbb{c}$ should recognize $L\_2 \cup (L\_1- L\_2)\mathbb{c}$, which is not a CFL.

> 3. If all PEGs are context-free, can they converted into an equivalent BNF via an algorithm?

If my conjecture above is correct, then this question is not applicable, but in any case there is no algorithm I know of to convert between PEGs and CFGs, and I believe that equivalence of a PEG and a CFG is undecidable. This fact complicates the proof procedure I propose above. :)

---
Tags: context-free, formal-grammars, normal-forms
---


# Question
Title: recursive language and computable function
Question:

Let $A$ and $B$ be finite alphabets and let $\\#$ be a symbol outside both $A$ and $B$. Let $f$ be a total function from $A^{\*}$ to $B^{\*}$. We say $f$ is *computable* if there exists a Turing machine $M$ which given an input $x \in A^{\*}$, always halts with $f(x)$ on its tape. Let $L\_{f}$ denote the language $\Bigl \\{x\\# f(x) \mid x\in A^{\*} \Bigr \\}$. Which of the following statements is true:

(A) $f$ is computable if and only if $L\_{f}$ is recursive.

(B) $f$ is computable if and only if $L\_{f}$ is recursively enumerable.

(C) If $f$ is computable then $L\_{f}$ is recursive, but not conversely.

(D) If $f$ is computable then $L\_f$ is recursively enumerable, but not conversely.

My Attempt:

if $f$ is computable then given $x$ on tape of TM, it will always halt in $f(x)$ on Tape.

$L\_f$ denote the language $\Bigl \\{x\\# f(x) \mid x\in A^{\*} \Bigr \\}$, which means $L\_f$ strings of type which has image and pre image to left and right of $\\#$.

* Now consider a function $f(x)$ is computable and its corresponding language $L\_f$, will $L\_f$ be recursive ? (given that $f(x)$ is computable )

Yes, $L\_f$ wil be recursive if $f(x)$ is computable. Because if $x\\# f(x)$ is given then i will first convert $x$ in $f(x)$ (i can do it because $f(x)$ is computable ) this gives me $f(x)\\# f(x)$ on table and i just left to match left strings to the right string of $\\#$ .

* Now consider a function $L\_f$ is recursive, will $f(x)$ be computable ?
(i need exlanation of this part)

# Answer
> 5 votes
The question is about the relation between a computable function $f$ and its graph (here denoted by $L\_f$). Since the function is *total*, the function is computable if and only if its graph is recursive (in case $f$ is a partial computable function, $f$ is computable if and only if its graph is r.e.).

So, your guess is right, and the correct answer is A. To compute $f$ from the characteristic function of the graph, you need to use a *generate* *and* *test* technique, progressively trying all possible outputs y for a given input x (using the characteristic function as tester), until you find the correct pair x#y. Since such a pair must exist, your algorithm is terminating.

---
Tags: computability, turing-machines, computation-models
---


title: Implications of Rice's theorem

text:
# Question
Title: Implications of Rice's theorem
Every time I think I get what Rice's theorem means, I find a counterexample to confuse myself. Maybe someone can tell me where I'm thinking wrong.

Lets take some non-trivial property of the set of computable functions, for example let $L = \\{ f : \mathbb{N} \to \mathbb{N} \\;|\\; \text{f is a computable and total function} \\}$. Obviously, $L$ is countably infinite and there's also a countably infinite number of computable functions not in $L$.

Now lets consider a turing complete programming language over of a finite set of instructions $\Sigma$ and the set of syntactically correct programs $P \subseteq \Sigma^\*$, with $|P| = |\mathbb{N}|$. If I can choose the semantics of my language as I please, I may also number the programs as I please and so it should be possible to design a programming language where some subset of the programs computes exactly some arbitrary subset of the computable functions, as long as the cardinality matches. For example, let $P\_{pal} = \\{ w \in \Sigma^\* \\;|\\; w\text{ is a palindrome} \\}$, and each program $p \in P\_{pal}$ compute a total function. Since $|P\_{pal}| = |L|$, such a language should exist.

However, $isPalindrome(w)$ is obviously turing-computable and since $isPalindrome(w) \iff isTotal(w)$, we would thus have a program which decides the non-trivial property $L$, which is not possible according to Rice's theorem.

Where is the error in my deduction? Does this mean there is no programming language where each palindromic program (or rather of *any* computable structure) computes exactly the total functions (or rather *any* set of computable functions)? This really perplexes me.

# Answer
What you forget is that all the mappings you use have to be computable. When you state that matching cardinalities ensure the existence of a mapping, that may be true, but the mapping is unlikely to be computable, precisely because that would let you get a contradiction with Rice theorem. In computability (at least for what I know of it), everything is either finite or countably infinite. So existence of mappings is usually not an issue. The problem is whether it is a computable one.

To say it differently, there is certainly a mapping (actually uncountably many) that associates precisely palindromic words with total computable functions. But, given such a palindrom $w$, which the mapping associates with a function $f\_w$ there is no way you can actually use such a mapping to get the result of applying $f\_w$ to some argument. You mapping does not give you any way of identifying the function or computing with it. Your language has non computable semantics.
> 6 votes

# Answer
> I may also number the programs as I please and so it should be possible to design a programming language where some subset of the programs computes exactly some arbitrary subset of the computable functions, as long as the cardinality matches.

For some sets of functions, that works; not for others. But a new programming language is a *new* numbering of *some* programs, and that is not what Rice's theorem talks about.

For the purpose of Rice's theorem, we consider only *Gödel* enumerations of *all* partial recursive functions, and then it only states something about *index sets*, that is sets of *all* indices in that enumeration of functions in the given set.

That does not cover all sets of indices; and that's good, because there certainly are plenty of decidable properties of programs. See also here.
> 2 votes

# Answer
Not every enumeration of programs is "acceptable", since not every enumeration would allow you to effectively compute the function associated with the program from the index of the program. In other words, you would not have universal machines (utm property). The second property that is usually required to "accept" the enumeration is the smn property: you need to be able to *compute* the index of program instances in a uniform and effective way.

It is possible to prove (Roger's equivalence theorem) that any pair of enumerations enjoying utm and smn are recursively isomorphic, that is to say that you have an *effective* way to translate programs beteween the two enumerations. This makes your theory enumeration-independent.

This is already enough to stress the relevance of utm and smn, the two basic theorems of the "abstract" approach to computability.

Roger's theorem is presented as an exercise (sic!) in his book Theory of Recursive functions and effective computability (exercise 2-10, pag 41). But the proof is not very hard, indeed.
> 2 votes

# Answer
I found this interesting paper by Udi Boker and Nachum Dershowitz which adresses the problem I had, among other things. In the introduction, they state that (emphasis mine)

> What does one mean by saying that “$f$ is computable”? One most likely means that there is a Turing machine $M$, such that $M$ computes $f$, *using some string representation of the domain* $D$. But what are the allowed string representations? Obviously, allowing an arbitrary representation (any injection from $D$ to $\Sigma^\*$) is problematic – it will make any decision function “computable”. **For example, by permuting the domain of machine codes, the halting function can morph into the simple parity function** \[...\]

and further

> Another approach is to allow only “natural” or “effective” representations. However, in the context of defining computability, one is obliged to resort to a vague and undefined notion of “naturalness” or of “effectiveness”, thereby defeating the very purpose of characterizing computability.

which explains what babou referred to as "computable semantics". The paper also contains this quote from Michael Rescorla:

> I will suggest that purported conceptual analyses involving Church’s thesis generate a subtle yet ineliminable circularity: they characterize the intuitive notion of computability by invoking the intuitive notion of computability \[...\] We endow the syntax with a primitive semantics. I submit that \[...\] we must demand that the semantic correlation between syntactic entities and non-syntactic entities itself be computable. But then the proposed analysis does not illuminate computability non-circularly.

So according to the authors, the common formal definition of a computable function relies on the informal intuition on what computability means, which explains what puzzled me about gödel numberings.
> 1 votes

---
Tags: computability, undecidability
---


# Question
Title: Why are Chess, Mario, and Go not NP-complete?
I have a hole in my understanding of what makes a problem NP.

I understand that Mario, for example, is NP-hard - it can be reduced to the NP-complete problem of 3SAT (see https://www.youtube.com/watch?v=mr1FMrwi6Ew)

Therefore if these games were also in NP, they would be NP-complete (by definition).

My understanding is that NP problems can be solved in polynomial time by a nondeterministic turing machine that "guesses" each step correctly. Why isn't this the case for Mario, Chess, and Go? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP (and thus NP-complete)?

# Answer
It's a common misconception that chess is NP-hard. *Generalized* chess may be NP-hard. Chess has an 8x8 board, generalized chess has an nxn board with many pieces.

The question then becomes if generalized chess is NP-complete. I reason that it's not NP-complete; not because it's easier than NP-complete problems but because it's harder. So I'll reason it's outside NP:

Given a certain position on an nxn board, will white win if both players play perfectly? There may be a "yes" answer and the certificate for NP might be a list of perfect moves for both players, but it's intractable to check if those moves by black are actually perfect. Maybe black has better moves so that white doesn't win. You can't check such a certificate in polynomial time.

Also, it may even be the case that a game takes an exponential number of moves, so that such a certificate is of exponential length.
> 11 votes

# Answer
Your understanding of what makes chess NP-Hard is slightly flawed. Yes, a nondeterministic machine is able to "play perfectly". But the language of chess is,

$$Chess = \\{Pos \quad | \quad \text{White wins with perfect play on an }n\times n \\ \text{ chess board, starting from position } Pos \quad \\}$$

Does a certificate for this exist? Consider even just *two* moves, with white moving first. Then you ask whether a move for white *exists* such that white wins, *for all* moves of black. Let $W$ be a program that takes as input a board position and returns *yes* iff white has won. Then to check whether white wins with perfect play within four moves, you need to evaluate

$$\exists w\_1\colon \forall b\_1\colon \exists w\_2\colon \forall b\_2\colon W(Move(Pos, w\_1,b\_1,w\_2,b\_2)) $$

But a nondeterministic Turing Machine can only answer questions if you ask them in the form

$$\exists y\colon M(x,y) $$

Hence what makes chess, and other games, hard, is that the quantifiers alternate. From Even and Tarjan \[1\], who proved, to my knowledge, PSPACE-Completeness of a game for the first time:

*Our construction also suggests that what makes "games" harder than "puzzles" (e.g. NP-Complete problems) is the fact that the initiative ("the move") can shift back and forth between the players. Such a shift corresponds to an alternation of quantifiers in the Boolean formula (the NP-Complete problems correspond to Boolean formulas with no quantifier alternation).*

\[1\] Even, Shimon, and Robert Endre Tarjan. "A combinatorial problem which is complete in polynomial space." Journal of the ACM (JACM) 23.4 (1976): 710-719.
> 10 votes

# Answer
> My understanding is that NP problems can be solved in polynomial time by a nondeterministic turing machine that "guesses" each step correctly.

That's correct.

> Why isn't this the case for Mario, Chess, and Go? Can't such a machine just guess the right way, for example, for Mario to go at each gadget thus rendering the problem in NP (and thus NP-complete)?

You've argued that these problems can be solved by nondeterministic Turing machines but you've not argued that they can be solved in polynomial time on such a machine. How do you know that there's some $k$ such that the outcome of a chess position on an $n\times n$ board can be determined by looking $n^k$ moves into the future?
> 1 votes

---
Tags: complexity-theory, decision-problem, np
---


# Question
Title: How can context switch affect the modification of a variable?
```
float myTotalAmount=0;
void update(float amt){
    myTotalAmount+= amt;
}

```

Task A called `update(10);`

Calculated `myTotalAmount+= amt;`

Didn't store the value for `myTotalAmount;` -------X

Task B called `update(5);`

Can we say X didn't happen due to context switch? or is Task B able to call update method because context switch happened due to some reason before the X?

Overall I am trying to understand race condition.

# Answer
A context switch is simply the operating system pausing the execution of one process and starting another. As such, context switches are required for any concurrency problem since, if there are no context switches, there's only one process executing so there is no concurrency.

In your example, the race condition occurs because what the function `update` really does is:

1. Read the value of `myTotalAmount` from memory;
2. Add `amt` to this value;
3. Store the result back in the memory.

Context switches at bad times can cause a race if the processes don't protect against that. Let's say that `myTotalAmount` currently has value zero.

1. Process B reads the value of `myTotalAmount`, which is zero.
2. Process B calculates the new value 0+5=5.
3. *Context switch*.
4. Process A reads the value of `myTotalAmount`, which is still zero.
5. Process A calculates the new value 0+10=10.
6. Process A writes the value 10 to `myTotalAmount`.
7. *Context switch*.
8. Process B writes the value 5 to `myTotalAmount`.

(Note that ordering the steps 13456728 would give the same result.)
> 2 votes

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


# Question
Title: Quantification in pumping lemma for regular languages
The Wikipedia article on the pumping lemma states:

> We now pump $y$ up: $xy^2z$ has more instances of the letter $a$ than the letter $b$, since we have added some instances of $a$ without adding instances of $b$. Therefore, $xy^2z$ is not in $L$. We have reached a contradiction. Therefore, the assumption that $L$ is regular must be incorrect. Hence $L$ is not regular.

But this formal version of the lemma seems to differ: $$ \begin{align\*} &(\forall L \subseteq \Sigma^\*) \\ &\quad (\text{regular}(L) \Rightarrow \\ &\quad ((\exists p \geq 1)((\forall w \in L)((|w| \geq p) \Rightarrow \\ &\quad ((\exists x,y,z \in \Sigma^\*)(w=xyz \land (|y| \geq 1 \land |xy| \leq p \land (\forall i \geq 0)(xy^iz \in L)))))))) \end{align\*} $$ I thought there only has to "**exist** a combination of $x,y,z$" in order to be regular (as stated in this answer as well).

As far as I can see, the Wikipedia example only takes a look at one possible combination/example. Am I missing something obvious here?

# Answer
You are right that the pumping lemma requires only some $x,y,z$ to *exist*, *for every string* whose length is greater than the pumping length, that satisfy the three conditions. However, when you attempt to show that a language is not regular, you use the method of contradiction, which makes use of the negation of the consequent of the implication in the pumping lemma.

The pumping lemma states that

If a language $L$ is regular, then ***there exists*** $p\gt 0$ such that ***for all*** strings $s\in L$ such that $|s|\ge p$, ***there exists*** a way to split $s$ in the form $x,y,z$ such that ***all*** of the following conditions ***hold***:

1. $xy^iz\in L$ for all $i\ge 0$
2. $|y|\gt 0$
3. $|xy|\le p$

Let $p$ be the statement: *The language $L$ is regular.*

Let $q$ be the statement: Given a language $L$, ***there exists*** $p\gt 0$ such that ***for all*** strings $s\in L$ such that $|s|\ge p$, ***there exists*** a way to split $s$ in the form $x,y,z$ such that ***all*** of the following conditions ***hold***:

1. $xy^iz\in L$ for all $i\ge 0$
2. $|y|\gt 0$
3. $|xy|\le p$

The pumping lemma states that $p\implies q$.

---

To show that a language $L$ is not regular using the pumping lemma, you first assume that $L$ is regular, i.e., $p$ is true.

Then, you try to show that $\neg q$ is true. From the pumping lemma, as $p\implies q$, the contrapositive $\neg q\implies \neg p$ also holds. So, if you can show that $\neg q$ is true, it implies that $\neg p$ is true. From the assumption that $p$ is true, we have both $p$ and $\neg p$ to be true, which is a contradiction.

Now, let's see what is $\neg q$. We need to negate the statement $q$, which gives, $\neg q$:

Given a language $L$, ***for all*** $p\gt 0$, ***there exists*** string $s\in L$ such that $|s|\ge p$, and ***for all*** ways to split $s$ in the form $x,y,z$, ***at least one*** of the following conditions ***don't hold***:

1. $xy^iz\in L$ for all $i\ge 0$
2. $|y|\gt 0$
3. $|xy|\le p$

Now, you can see from here, that in the negation, the statement must be true irrespective of how you split $s$ into $x,y,z$. So, for any arbitrary $p$, if you can find any one string $s$ such that for every way to split it in the form $x,y,z$, at least one of the three conditions are false, it implies that the language is not regular.

The only place where "one possible example" has been used is in the choice of $s$, which is correct as you can see from the statement. No assumption has been made in how $s$ splits into $x,y,z$, and yet, it has been shown that at least one of the conditions becomes false. So, for a given $s$, *all* $x,y,z$ have been indeed considered.

It may appear that the $|y|\gt 0$ and $|xy|\le p$ make the choice of $x,y,z$ a specific choice, however, this must be true if conditions 2. and 3. are to be true - if they were not, we trivially reach a contradiction as we need only any one of the three conditions (at least) to be false.
> 4 votes

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


# Question
Title: Prove 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1
So I am trying to work on a problem and honestly... I am so lost with this one. I will try to ask it the best I can.

Exact text of the problem: "Prove the following directly from the definition of Big Theta; 100,000,000 is a member of the set of functions defined by Big Theta of g(n), where g(n) = 1"

Additionally, the definition in question is \[Click here to see definition\]

Basically, I don't understand the definition and I don't understand the question. I understand that this chapter is talking about asymptotic behavior, and how given 2 different functions these 1 number could "grow" faster than the other up to a certain point and then it would switch. Example, Using 1 and 100,000,000 as n. In the following 2 functions 1 is larger number using 1... and then the other one is larger when you 100,000,000.

1,000,000n and n^2

Perhaps someone can help put the definition and question into words I can understand a little better.

# Answer
You haven't provided a definition, but here is a standard one:

> Let $f,g$ be functions from $\mathbb{N}$ to $\mathbb{R}$. We say that $f(n) \in \Theta(g(n))$ (usually written $f(n) = \Theta(g(n))$) if there exist a natural number $N$ and positive real numbers $0 \< a \< b$ such that for all natural $n \geq N$ it holds that $$ ag(n) \leq f(n) \leq bg(n). $$

Roughly speaking, this says that the two functions $f,g$ have the same order of growth – they differ by a constant multiple. The definition is reflexive ($f(n) = \Theta(f(n))$), symmetric ($f(n) = \Theta(g(n))$ implies $g(n) = \Theta(f(n))$) and transitive ($f(n) = \Theta(g(n))$ and $g(n) = \Theta(h(n))$ imply $f(n) = \Theta(h(n))$), and so forms an equivalence relation. Each equivalence class is an "order of growth".

In your question, $f(n) = 10^8$ and $g(n) = 1$. So you have to find natural $N$ and positive reals $0 \< a \< b$ such that the following holds for all $n \geq N$: $$ ag(n) \leq f(n) \leq bg(n) \Longleftrightarrow a \leq 10^8 \leq b.$$ I'm sure you can find such $N,a,b$.
> 2 votes

---
Tags: algorithms
---


# Question
Title: In a DFA, does the restriction for a total transition function apply to accepting states?
I recently discovered the idea of a *total transition function* in Automata Theory. To my understanding this means that every state has at least one outgoing state.

My question is whether this restriction **applies to accepting states**, since my initial intuition tells me that this would be an overly strict enforcement of the state machine.

Thanks in advance for any answers.

# Answer
Unfortunately there seem to be several different definitions of DFAs in the literature. Here is the classical definition:

> A DFA is a quintuple $\langle \Sigma,Q,q\_0,F,\delta \rangle$, where $\Sigma,Q$ are non-empty finite sets, $q\_0 \in Q$, $F \subseteq Q$, and $\delta \colon Q \times \Sigma \to Q$.
>
> We extend $\delta$ to a function $\hat\delta \colon Q \times \Sigma^\* \to Q$ using the recurrence $\hat\delta(q,w\sigma) = \delta(\hat\delta(q,w),\sigma)$, with base case $\hat\delta(q,\epsilon)=q$.
>
> The language accepted by the DFA is $\\{ w \in \Sigma^\* : \hat\delta(q\_0,w) \in F \\}$.

Other definitions are possible. For example, you might allow $\delta$ to be a partial function. However, the definition I stated has a significant advantage: the Myhill–Nerode theorem holds for it.

Under my definition, from each state there is exactly one transition for each alphabet symbol. Other definitions could be different. Only you know which definition you use.

It is important to stress that this "strict" definition doesn't restrict the power of DFAs one bit. It is known that DFAs accept the very same languages as NFAs, for example, though there could be a dramatic difference in *state complexity* (the number of states needed to accept a given language).
> 4 votes

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


# Question
Title: without triangle inequality, finding good approximate tours for TSP in polynomial time is impossible unless P=NP?
In the text book, Introduction to Algorithm, 3rd Edition.

In the chapter, **Approximation Algorithms** and for the problem **Travelling Salesman Problem**, the author says:

I am wondering how triangle inequality gives rise to this assertion? It seems that this property is not that important, as I searched through the rest of this section, it does not appear.

# Answer
Here is what these lecture notes have to say. We can reduce HAMILTONIAN-PATH to MIN-TSP-TOUR in the following way: give the weight $1$ for edges in the original graph, and $B$ (for some $B \> 1$ to be chosen later) for edges not in the original graph. If the original graph had a Hamiltonian path, then the new path has a tour of length at most $n$, and otherwise any tour has length at least $n-1+B$. Thus any approximation algorithm with ratio better than $n/(n-1+B)$ would solve HAMILTONIAN-PATH. Choosing $B = 1 + (c-1)n$, we get then any algorithm with ratio better than $1/c$ would solve HAMILTONIAN-PATH. This is true for any $c \> 1$, so MIN-TSP-TOUR cannot be approximated to any constant ratio.

---

Here is where the triangle inequality comes in in Christofides' algorithm. The algorithm is at follows:

1. Construct a minimum spanning tree $T$.
2. Find a minimum matching $M$ between the set $O$ of odd-degree vertices in $T$.
3. Remove edges from $T\cup M$ to obtain a Hamiltonian cycle $H$.

The analysis goes like this. Suppose $H^\*$ is a Hamiltonian cycle of weight $w(H)$. Then $w(T) \leq w(H^\*)$ and $w(H) \leq w(T \cup M) \leq w(T) + w(M) \leq w(H^\*) + w(M)$. So far we haven't used the triangle inequality. Now take $H^\*$ and replace paths from adjacent vertices $a,b \in O$ on $H^\*$ with direct edges. *The triangle inequality implies that the resulting cycle $H^{\**}$ satisfies $w(H^{\**}) \leq w(H^\*)$.* We can partition the cycle into two matchings $M\_1,M\_2$ satisfying $w(M\_1) + w(M\_2) = w(H^{\**})$, and so $w(M) \leq \min(w(M\_1),w(M\_2)) \leq w(H^{\**}) \leq w(H^\*)$. We conclude that $w(H) \leq w(H^\*) + w(M) \leq 1.5 w(H^\*)$.
> 5 votes

# Answer
We have been puzzled by the exact same question in the past few days. At the end, it seems that the reason why metric TSP is approximable is actually not the triangle inequality itself, but the more subtle and implied assumption that one never needs to return twice to the same city (thanks to the inequality, which also implies a *all* edges do exist). In fact, if you allow several visits of the cities, then it seems that even the general variant of TSP becomes approximable (see this answer to a related question).
> 1 votes

---
Tags: algorithms, complexity-theory, traveling-salesman, approximation-algorithms
---


title: Proving that a problem is in NP

text:
# Question
Title: Proving that a problem is in NP
I have an assignment in which the problem, $D$, is simple but, once found, easy to check. Is it enough to prove that a solution $x$ can be checked in polynomial time to prove that $D \in NP$? (The problem $D$ is a decision problem)

Edit: Changed $P$ to $D$

# Answer
> 4 votes
The *two* requirements for a problem to be in **NP** are

1. it must be possible to check a given solution in polynomial time;
2. there must be some polynomial $f$ such that solutions to instances of length $n$ have size at most $f(n)$.

Properly, the "solutions" are referred to as "certificates" since they don't have to be an actual solution to the problem. Normally, the certificate to something like a satisfiability problem would be a satisfying truth assignment, but anything that "proves" the instance is in the langauge is acceptable. In particular, the proof that every language in **NP** can be thought of in these terms uses a description of the accepting computation of a Turing machine as the certificate.

This gives intuition why the certificate has to have polynomial length: the Turing machine was only allowed to run for a polynomial number of steps. Indeed, if you dropped the polynomial length requirement on the certificate, even the halting problem would "be in **NP**". The certificate would be a description of the steps taken by the Turing machine before it halts; you can easily check in polynomial time that a certificate is valid, but the certificate itself might have arbitrary length.

---
Tags: np-complete, proof-techniques, decision-problem, np
---


title: Meaning of “call by reference”

text:
# Question
Title: Meaning of “call by reference”
Can someone explain to me in a plain English what call by Reference mean ? I am having trouble to recognize a difference between "call by value" and "call by reference"

Thank you.

# Answer
When you call a function, it gets the arguments.

In math, as well as "pure" functional languages, the function can look at those arguments and compute things based on them, then return a result.

The complication comes from how, in most languages, computation can have side-effects: variables can have their values changed (mutated).

So, for example, if I pass a record/struct to a function and change one of its values, then look at the record after the function has returned, do I still see the changes?

The answer is yes for call by reference, and no for call by value.

Consider the following pseudocode:

```
function foo(bar):
  bar.x = 3
  return bar.x + bar.y

function main:
  myrecord = {x:1, y:2}
  myval = foo(myrecord)
  print myrecord.x

```

What does this program print? 1, or 3?

In call by reference, it prints 3. The function `foo` works on the same piece of memory that `main` works on, so any changes it makes, `main` sees.

In call by value, it prints 1. The "value" of `myrecord` is passed to `foo`, namely a record with 1 and 2 as its fields, but they're not operating on the same piece of memory, so `main` doesn't see any of the changes `foo` makes, because `foo` was just seeing a copy of `myrecord`.
> 3 votes

---
Tags: programming-languages, semantics, evaluation-strategies
---


# Question
Title: How to construct a NFA that the third symbol and the third from last symbol are same?
Suppose the alphabet is {a,b}. I have tried coming up with NFA1: third symbol is a, and NFA2: third from last symbol is a. Then NFA3 and NFA4 similar but with symbol of b. Then I use intersection of NFA1, NFA2, and intersection of NFA3, NFA4, and add $\epsilon$ transition. But things seem to go wrong here. When doing the intersection of, say, NFA1, and NFA2, obviously the new NFA would not accept strings such as aba, aaa.

I have been trying different methods but still stuck here for hours. Any help of hint would be much appreciated!

# Answer
*Hint*:

Here is a NFA that accepts exactly those strings whose first and last character are both $a$:

Can you modify and extend this to become a solution to your problem?
> 4 votes

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


# Question
Title: Irregularity of $\{a^iba^j : i \neq j\}$ using pumping lemma
Proving the language $L=\\{ a^i b a^j |\ i\<j,\text{ or }i\>j;\ i,j\>0 \\} $ is not regular, I am trying to use the pumping lemma for regular languages:

pumping length $:= m$

**case 1:** $i\<j; j=m$

$w\_1 = a^i b a^m = xyz$
$|xy| \< m$
$|y| \> 0$

$\Rightarrow$
$y$ can be:

* $a$s only
* $a$s + $b$
* just $b$

However, this leads to $xy^hz\ \not \in L\ \forall h,\ h\>0$.

**case 2:** $i\>j; i=m$

$w\_2 = a^m b a^j = xyz$
$|xy| \< m$
$|y| \> 0$

$\Rightarrow$
$y$ can be:

* $a$s only

Pumping with this $y$:
$xy^hz\ \in L\ \forall h$ holds true.

As this answer does not seem to even consider the second case, is the **first case** sufficient to proof the language is not regular?
However, taking a look at this answer I think I'd have to considere the **second case** as well, in order to cover all possible $xyz$ combinations.

# Answer
> 1 votes
Here is the contrapositive form of the pumping lemma, which is what we use to prove that a language is not regular:

> Let $L$ be a language. Suppose that for all $p \geq 1$ there exists a word $w \in L$ of length at least $p$ such that for every decomposition $w=xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Then $L$ is not regular.

Using the pumping lemma directly for the language $L$ in the question is a bit tricky. Given $p \geq 1$, let $w = a^p b a^{p+p!} \in L$; note that $|w| \geq p$. We have to show that for every decomposition $w = xyz$ in which $|xy| \leq p$ and $y \neq \epsilon$ there exists an integer $i \geq 0$ such that $xy^iz \notin L$. Consider any such decomposition. It is easy to check that $y = a^\ell$ for some $1 \leq \ell \leq p$, and that $xy^ij = a^{p+(i-1)\ell}ba^{p+p!}$. For $i = p!/\ell+1$ (which is an integer!), $xy^ij = a^{p+p!}ba^{p+p!} \notin L$. Thus the condition in the pumping lemma is satisfied, and we conclude that $L$ is not regular.

# Answer
> 1 votes
Let $$L\_1 = \\{a^iba^j | i\lt j\text{ and } i,j\gt 0\\}$$ $$L\_2 = \\{a^iba^j | i\gt j\text{ and } i,j\gt 0\\}$$

Here, $$L = L\_1\cup L\_2$$

From Case 1, you have shown that $L\_1$ is not regular.

You are trying to conclude that if $L\_1$ is not regular, $L$ is not regular. It is not sufficient that $L\_1$ is not regular to show that $L$ is not regular. A simple counter example will be $L\_1 = \\{a^nb^n|n\gt 0\\}$ and $L\_2=\\{a^m b^n |m\ne n\\}$. Neither $L\_1$ nor $L\_2$ are regular, yet their union is regular.

---

In the first answer you have linked, it is not true that only one case has been considered. You need to find *any one string* $s$ whose length is at least than every possible pumping length $p$ such that no matter how you partition it into $s=xyz$, the resulting string goes out of the language.

The key difference between your case 1 and the answer you linked is that you have taken a string in $L\_1\subset L$, pumped it and shown that it goes out of $L\_1$ *only*. However, what you need to show is that it cannot lie in $L$ at all, no matter how you split it and pump it, which is what the linked answer shows.

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


# Question
Title: How is pre-computation handled by complexity notation?
Suppose I have an algorithm that runs in $O(n)$ for every input of size $n$, but only after a pre-computation step of $O(n^2)$ for that given size $n.$ Is the algorithm considered $O(n)$ still, with $O(n^2)$ amortized? Or does big O only consider one "run" of the algorithm at size $n$, and so the pre-computation step is included in the notation, making the true complexity $O(n^2+n) = O(n^2)$?

# Answer
> 4 votes
I understand that you have some computational problem with input size $n$, and you use $f(n)$ time for preprocessing. Perhaps after that, you can answer some kind of queries in $g(n)$ time. Both $f$ and $g$ are functions of the input size, and you can now apply Big Oh and say, for instance, that $f(n) = O(n^2)$ and $g(n) = n$.

Now, nobody is forcing you to "consider the runtime to be $O(n)$" or anything like that. So why not just say it like it is, e.g., "after a $O(n^2)$-time preprocessing step, queries can be answered in $O(n)$ time", or "there is an $O(n^2)$-time algorithm for solving the problem", or whatever it is precisely that holds. It's up to you how you present it.

In particular, I want to clear the misconception that "big O would consider one 'run' of the algorithm". If you look at the definition of Big Oh, you'll see that it says nothing about algorithms or their "runs".

# Answer
> 0 votes
When you write about "the complexity", you must write exactly what you are measuring.

In your example, the time for solving one single problem of size n is $O (n^2)$ (actually, it could be better if there is an algorithm that doesn't do the reusable pre-computation and is faster than $O (n^2)$).

The time for solving k problems of size n is $O(n·max(k,n))$. I would say it is very similar to amortized time, but not exactly the same.

---
Tags: algorithms, time-complexity
---


# Question
Title: Prove that this language is decidable or undecidable
Is the following language decidable?

L = {(M) : M performs at least 100 steps on every accepted input.}

I tried to use reduction from the halting problem, but still no dice.

# Answer
> 2 votes
Yes, it is decidable. There is a limited amount of input that any Turing machine could look at in ≤ 100 steps, so you can test a simulation of any given machine $M$ against all of those possibilities.

---
Tags: formal-languages, turing-machines
---