# Question
Title: Is this correct grammar definition of Backus-Naur form?
I've been given a grammar definition of "Simple C language" in Backus-Naur to write a compiler for a class assignment. I've been trying to implement the parser for some time now and I just can't move forward due to some endless loops and I think the definition might be wrong.

This is the full definition of "Simple C Language" grammar I was given:

> \[1\] Program = {Declaration | FunctionDefinition}.
>
> \[2\] Declaration = DeclarationSpecifier \[Declarator\] ';'.
>
> \[3\] DeclarationSpecifier = \['typedef' | 'static'\] TypeSpecifier.
>
> \[4\] **TypeSpecifier** = 'void' | 'char' | 'bool' | 'short' | 'int' | 'long' | 'double' | 'signed' | 'unsigned' | StructOrUnionSpecifier | EnumSpecifier | **TypeName**.
>
> \[5\] StructOrUnionSpecifier = ('struct' | 'union') \[Ident\] '{' {StructDeclaration} '}'.
>
> \[6\] StructDeclaration = TypeSpecifier Declarator {',' Declarator} ';'.
>
> \[7\] EnumSpecifier = 'enum' \[Ident\] '{' Enumerator {',' Enumerator} '}'
>
> \[8\] Enumerator = Ident \['=' ConstantExpression\].
>
> \[9\] Declarator = {'\*'} DirectDeclarator.
>
> \[10\] DirectDeclarator = Ident | '(' Declarator ')' | DirectDeclarator ( '\[' \[ConstantExpression\] '\]' | '(' \[ParameterTypeList\] | \[Ident {',' Ident}\] ')' ).
>
> \[11\] ParameterTypeList = ParameterDeclaration {',' ParameterDeclaration}.
>
> \[12\] ParameterDeclaration = DeclarationSpecifier \[Declarator | AbstractDeclarator\].
>
> \[13\] **TypeName** = **TypeSpecifier** \[AbstractDeclarator\].
>
> \[14\] AbstractDeclarator = {'\*'} DirectAbstractDeclarator.
>
> \[15\] DirectAbstractDeclarator = '(' AbstractDeclarator ')' | \[DirectAbstractDeclarator\] ( '\[' \[ConstantExpression\] '\]' | '(' \[ParameterTypeList\] ')' ).
>
> \[16\] FunctionDefinition = \[DeclarationSpecifier\] Declarator {Declaration} CompoundStatement.
>
> \[17\] Expression = AssignmentExpression {',' AssignmentExpression}.
>
> \[18\] ConstantExpression = ConditionalExpression.
>
> \[19\] AssignmentExpression = ConditionalExpression | UnaryExpression ('=' | '\*=' | '/=' | '%=' | '+=' | '-=' | '\<\<=' | '\>\>=' | '&=' | '^=' | '|=') AssignmentExpression.
>
> \[20\] ConditionalExpression = LogicalORExpression | LogicalORExpression '?' Expression ':' ConditionalExpression.
>
> \[21\] LogicalORExpression = LogicalANDExpression {'||' LogicalANDExpression}.
>
> \[22\] LogicalANDExpression = InclusiveORExpression {'&&' InclusiveORExpression}.
>
> \[23\] InclusiveORExpression = ExclusiveORExpression {'|' ExclusiveORExpression}.
>
> \[24\] ExclusiveORExpression = ANDExpression {'^' ANDExpression}.
>
> \[25\] ANDExpression = EqualityExpression {'&' EqualityExpression}.
>
> \[26\] EqualityExpression = RelationalExpression ('==' | '!=') RelationalExpression.
>
> \[27\] RelationalExpression = ShiftExpression {('\<' | '\>' | '\<=' | '\>=') ShiftExpression}.
>
> \[28\] ShiftExpression = AdditiveExpression {('\<\<' | '\>\>') AdditiveExpression}.
>
> \[29\] AdditiveExpression = MultiplicativeExpression {('+' | '-') MultiplicativeExpression}.
>
> \[30\] MultiplicativeExpression = CastExpression {('\*' | '/' | '%') CastExpression}.
>
> \[31\] CastExpression = {'(' TypeName ')'} UnaryExpression.
>
> \[32\] UnaryExpression = PostfixExpression | ('++' | '--') UnaryExpression | ('&' | '\*' | '-' | '~' | '!') CastExpression.
>
> \[33\] PostfixExpression = PrimaryExpression | PostfixExpression '\[' Expression '\]' | PostfixExpression '(' \[AssignmentExpression {',' AssignmentExpression}\] ')' | PostfixExpression '.' Ident | PostfixExpression '-\>' Ident | PostfixExpression ('++' | '--').
>
> \[34\] PrimaryExpression = Ident | Number | String | '(' Expression ')'.
>
> \[35\] Statement = LabeledStatement | CompoundStatement | ExpressionStatement | SelectionStatement | IterationStatement | JumpStatement.
>
> \[36\] LabeledStatement = 'case' ConstantExpression ':' Statement | 'default' ':' Statement.
>
> \[37\] CompoundStatement = '{' {\[Declaration\] \[Statement\]} '}'.
>
> \[38\] ExpressionStatement = \[Expression\] ';'.
>
> \[39\] SelectionStatement = 'if' '(' Expression ')' Statement \['else' Statement\] | 'switch' '(' Expression ')' Statement.
>
> \[40\] IterationStatement = 'while' '(' Expression ')' Statement | 'do' Statement 'while' '(' Expression ')' ';' | 'for' '(' ExpressionStatement ExpressionStatement \[Expression\] ')' Statement.
>
> \[41\] JumpStatement = 'continue' ';' | 'break' ';' | 'return' \[Expression\] ';'.

There is a high possibility that I am wrong and misunderstanding something but isn't *TypeSpecifier = TypeName* and *TypeName = TypeSpecifier* leading to some endless loop?

To my understanding, this definition means that a TypeSpecifier can be TypeName which is also TypeSpecifier and if we give them some example value like 'a' for TypeSpecifier and 'b' for TypeName then ababababab..abab is valid. Am I wrong?

# Answer
As a side note, that grammar is not written in BNF. Rather, it is written in one of many dialects of "extended" BNF, which includes repetition and optionality operators (`{ … }` and `[ … ]`). BNF only has simple productions. However, the repetition and optional components can be macro-expanded into BNF (using a newly-created non-terminal), and the "extended BNF" is generally considered easier to read. It also corresponds directly to the code in top-down parsers, which may well be the type of parser you are being asked to write.

A context-free grammar can certainly include recursion, even indirect left recursion as exhibited by the grammar in this question. But left recursion does create a problem for a top-down parser, precisely of the nature you suggest: the top-down parser goes into an endless loop adding predictions. Bottom-up parsers do not have this problem because they recognise productions when the production is complete rather than having to predict it before it starts.

However, the grammar as written is not correct, because it does not allow the use of type aliases created with a `typedef` declaration:

```
typedef struct A { int a; } MyTypeName;
MyTypeName b;

```

Although the grammar will have no problem with the first line above, it will not be able to parse the second one because `TypeSpecifier` does not have an alternative which allows a single identifier.

The standard C grammar defines *type-specifier* as follows:

> *type-specifier*:
> **void**
> **char**
> **short**
> **int**
> **long**
> **float**
> **double**
> **signed**
> **unsigned**
> **\_Bool**
> **\_Complex**
> *atomic-type-specifier*
> *struct-or-union-specifier*
> *enum-specifier*
> *typedef-name*

That's very similar to your grammar with the addition of a few primitives and the `atomic` type marker, but the last line is slightly but significantly different. This suggests that there is a typo in your grammar. I'd suggest you double check with whoever gave you the assignment.

As a note, *typedef-name* is just an *identifier*, but not any identifier; it must be an identifier previously declared as a type alias ("typedef"). That restriction cannot be expressed in a context-free grammar, and is one of the little challenges involved in writing a C parser.

If you make the change I suggest, you might run into another issue. The standard C grammar defines *declaration* as follows (condensed into EBNF, which the C standard doesn't use):

> *declaration*:
> { *declaration-specifier* } \[ *init-declarator-list* \] **;**

which differs from your grammar because your grammar's definition of *Declaration* doesn't allow multiple *DeclarationSpecifier*. However, the (possibly accidental) recursion in *TypeSpecifier* in effect turns *TypeSpecifier* into a list, thus allowing

```
unsigned char uch;

```

However, the fact that *TypeSpecifier* is a list means that it will also accept things like

```
int double number;
unsigned struct MyStruct u;

```

which are not meaningful.

It's possible that the C subset you're expected to write a parser for doesn't include `short char` or `long double`, in which case the lack of repetition won't be a problem. If you do need to handle compound type names, you'll need a rather longer list of valid type names. (The standard C grammar does allow meaningless combinations of *declaration-specifier*, but the text of the standard limits the possible combinations. I think the authors of the standard concluded that it would be far too complicated to try to write the restrictions in BNF, and that it would be easier both for presentation and for implementation to do the check after the parse is complete.)
> 2 votes

# Answer
The 'endless loop' is not a problem. Remember that there are many productions possible. A word is accepted by the grammar if there is any production that generates it. It doesn't matter if there are other productions (e.g., 'endless loops') that are pointless or never generate any word; they're harmless and irrelevant.

No, this will not yield abababab.. as valid.
> 1 votes

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


# Question
Title: How can one reduce 3-CNF-SAT and k-CNF-SAT to each other?
I am studying for NP problems.
To prove k-CNF-SAT is NP-hard, there must exists something that can be reduced to k-CNF-SAT. So what I thought is to reduce 3-CNF-SAT to k-CNF-SAT and reduce k-CNF-SAT to 3-CNF-SAT both proves that it is NP-hard.

I know that 3-CNF-SAT is NP-Complete, because of its number of literals, but this property seems dedicate no effect to proof.
Thanks for any suggestion.

**Note: k-CNF-SAT is a conjunctive normal form which k \> 3.<br>And my question is same as the title, I have no idea about this question, since I just only know 3-SAT is a special case of k-SAT.**

# Answer
> 3 votes
To reduce $k$-CNF to CNF: every instance of $k$-CNF is an instance of CNF, so the reduction is trivial.

To reduce CNF to $k$-CNF, where $k \ge 3$: convert the CNF formula to a circuit that computes it; then convert the circuit to a 3-CNF formula using the Tseitin transformation. (If your definition of $k$-CNF requires that there be exactly $k$ literals in every clause, then you can pad: introduce $k$ new variables $y\_1,\dots,y\_k$; for every clause that has less than $k$ literals, add $\lor y\_1 \lor y\_2 \lor \dots$ to pad it out to exactly $k$ literals; and then add clauses that force all of $y\_1,\dots,y\_k$ to be false.)

If this is too terse, see our reference question and a good textbook to learn the fundamentals of reductions.

# Answer
> 1 votes
A clause in 3-CNF can be converted to k-CNF by adding extra padding:

(l1 V l2 V l3) can be converted to (l1 V l2 V l3 V y) ∧ (l1 V l2 V l3 V y')

Keep adding this extra padding until each clause contains k literals.

Same way, a k-CNF clause can be broken until each clause contains 3 literals.

(l1 V l2 V l3 V l4) can be broken into (l1 V l2 V y) ∧ (l3 V l4 V y') by resolution.

---
Tags: complexity-theory, reductions, np-hard, satisfiability, 3-sat
---


# Question
Title: Algorithm to compute decomposition of a union of sets to a disjoint union of intersections
A union of sets can be decomposed into a disjoint union of intersections. Rather than writing confusing notation, this is easiest to to see in an example of three sets.

This clearly generalizes. If we want to calculate the disjoint pieces, we have to compute $2^n$ intersections, where $n$ is the number of sets.

However, if our sets were nested, i.e. $A\_1 \subseteq A\_2 \subseteq ... A\_n$, we need only to compute $n$ intersections of the form $A\_i \cap A\_{i+1}^c$. The point is if we did our original exhaustive "binary search" computing $2^n$ intersections we would find that most of these intersections are empty, so we are wasting computations.

My question is, what if we had $n$ sets where the vast majority are nested, but a few aren't and we don't know which. Can we compute an $O(n)$ number of intersections to find the disjoint pieces?

# Answer
No, not $O(n)$. Suppose $0.9n$ are nested and $0.1n$ are not nested (and are unrelated). Then there can be at least $2^{0.1n}$ different pieces, which is not $O(n)$.

You can find the nesting structure in $O(n^2)$ time by testing all pairs of sets to see which are subsets of the other.
> 0 votes

---
Tags: algorithms, sets
---


# Question
Title: Clustering algorithm with specific cluster grouping areas
I'm looking for a way to cluster points in a given space, where clusters form around specific closed, allowed zones of that initial space. Each allowed zone should be surrounded by points of its cluster.

However, it is not only necessary to match the points to the closest allowed zone, but also to take into consideration the distance to other points of the same cluster.

In the example image given, in the clustered picture, the green points at the top right belong to the green cluster despite being closest to the blue area, because their neighbours are all green.

Ultimately, a network would be created from each cluster (lets say the points are a series of sinks), and linked to each respective zone via a single optimally placed point within the zone (which represents the source). A cost function would evaluate the cost of the network (i.e. minimizing the cost of a weighted graph). The difficulty is that the optimal placement of the source point is not known until the cluster is defined. The overall goal is to minimize the cost of all the networks combined.

Is there any algorithm available that can do this type of clustering? Otherwise how would you proceed?

# Answer
> 1 votes
One approach would be to devise a loss function for each point, that says how much you will penalize the cluster assigned to that point, as a function of what clusters are assigned to its neighbors and what the nearest zones are; then let the total loss be the sum off the losses for each point; and then use some optimization algorithm to find the assignment that minimizes the total loss.

---
Tags: algorithms, clustering
---


title: Bin Packing variant

text:
# Question
Title: Bin Packing variant
I am currently struggling with a bin packing variant, where we have fuel and compartments of a tank truck. Some industry constraints apply, but the whole picture is that you must fit the total volume with the optimum way through the compartments. I have created a model, which works almost perfectly, where I try to minimize the wastage (from all the compartments, not only the used). Now let's say that I have a preference in using as front compartments as possible, namely if the 2nd compartment and the 8th compartment have 1000lt capacity, then I want to use the 2nd compartment. I want this to happen only when the wastage of the one solution is equal to the other.

Hence, If I have a solution with wastage 1100 lt and the 2nd compartment is empty, but I have another solution with wastage 1100lt and the 8th compartment is empty, I want the model to extract the second.

Is there a way to model preference constraints, without diverging from the original objective (minimizing wastage)?

**EDIT**
Let me explain a little more about my objective. Right now the objective is

$\sum\_i{\sum\_j{c\_{j}-y\_{ij}}}$

Where $c\_{j}$ is the capacity of each compartment j and $y\_{ij}$ is the assigned quantity of element $i$ in compartment $j$. If we assume that the new part of the objective function is to be found (I'm counting on you), then I can replace the function above with:

$M\*\sum\_i{\sum\_j{c\_{j}-y\_{ij}}}+μ\*F$

Where M is going to be a big number and μ a small number. F would be the second objective.

# Answer
One approach is to solve the system without this preference constraint and find the wastage. Suppose you can achieve wastage 1100. Then, add a new constraint that the wastage cannot exceed 1100, and modify the objective function to slightly penalize use of the back components, and solve that modified problem.
> 1 votes

---
Tags: optimization, linear-programming, constraint-satisfaction
---


title: Evenly Spaced Points On Smooth Surface

text:
# Question
Title: Evenly Spaced Points On Smooth Surface
I want to space points evenly (i.e. maximizing minimal distance between two points) on some smooth surface $S\subseteq\mathbf{R}^n$ (usually $n=3$), where I have a projection operator $p:\mathbf{R}^n\to S$ which approximates the closest point on the surface. My idea is to place them randomly first and then let some repelling force act between them and reproject back to the surface after each iteration of the action. This can be rather costly, if there are $10^3$ points, I have to compute the distance between $10^6$ points in one iterations, and I need a few iteration until everything stabilizes.

How can I imporove this process? My ideas:

* Measure the distance between every pair of points but compute the force only when the distance is smaller than some $a$, then do a few iterations (assuming the points don't move too far in one iteration) and recompute the distance after $k$ steps.
* Choose some partition of the surface where each part has a set of 'neighbours' (including itself), compute for each point the location in the partition, i.e. the part it lies in, then let only the points in neighbouring parts act on each other, recompute the location after $k$ steps.

# Answer
> 1 votes
I would suggest that you don't calculate the distance between all pairs of points, but only between pairs of points that are nearest neighbors. You could store the points in some nearest-neighbor data structure, e.g., an octree, or even a fixed partitioning of space. Some data structures might allow for relatively rapid updates, so you could even update after every iteration.

I'd also suggest looking at the methods used for simulating the n-body problem, as some of those might be applicable to your situation as well. See https://en.wikipedia.org/wiki/N-body\_problem#Many\_bodies and https://en.wikipedia.org/wiki/N-body\_simulation.

Also, you might consider adapting your objective function. Rather than having all points repel, maybe you might have only those points whose neighbor are below a certain threshold repel; or you might make the repelling force a smooth function of the distance between the points, where this function is similar to $f(x) \approx x$ when $x \ll \tau$ (where $\tau$ is the threshold) and $f(x) \approx \tau$ when $x \gg \tau$. You could select your threshold $\tau$ to be approximately equal to the expected final minimal distance that you think is achievable, or you could set it adaptively in each iteration. This may require many more iterations, but each iteration can be done much faster, and it will avoid moving points that are already far from all their neighbors.

---
Tags: computational-geometry, physics
---


title: When does $p$ break the pumping lemma

text:
# Question
Title: When does $p$ break the pumping lemma
I want to prove that $\\{A^iB^jC^k \mid i=j \text{ or } j=k\\}$ is a not a regular language using the pumping lemma.

I've found that the only way to obtain a contradiction is when $x \in A^\*$, $y \in B^\*$, $z \in C^\*$, as $y$ is unable to be pumped up and still fit in the language. However if I have any combination of $y \in B^\*C^\*$ or $y \in A^\*B^\*$ and either $x$ or $z$ is empty, it appears as if $y$ can be pumped and thus this would be a regular language. The only way I can think that this would violate the rules of pumping lemma is if $|xy| ≤ P$. Assuming that $P$ is $2$ (which may be completely wrong), then the above still wouldn't violate the pumping lemma and thus this would be a regular language, right?

# Answer
> 1 votes
Let's start with stating the pumping lemma, in its contrapositive form:

> Suppose that $L$ is a language such that for all $p\>0$, the following holds. 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 $t \geq 0$ such that $xy^tz \notin L$. Then $L$ is not regular.

Now let us prove that your language is not regular. Given $p \> 0$, let $w = a^pb^p \in L$, which certainly has length at least $p$. Given a decomposition $w = xyz$ with $|xy| \leq p$ and $y \neq \epsilon$, we see that $y = a^i$ for some $i \neq 0$. Therefore $xy^0z = a^{p-i}b^p \notin L$. Hence the pumping lemma applies, and shows that $L$ is not regular.

---
Tags: pumping-lemma
---


# Question
Title: Why are DCFL not closed under concatenation or Union whereas CFL is?
I understand that DCFL they are not closed under concatenation or Union. As without non determinism, PDA cannot decide when to jump to the next one in case of concatenation and without epsilon moves Union is not possible.

However, DCFL is a proper subset of CFL (unambiguous) and CFL is closed under union and concatenation. So how can a proper subset not inherit the global properties of its parent set ?

# Answer
DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily *deterministic* CFL.
> 9 votes

# Answer
The fact that is a proper subset does not inherit the global properties in general is common in mathematics and computer science. A proper subset does not have to inherit the global properties of its superset.

For example, the set of integer numbers $\mathbb{Z}$ is a proper subset of the set of real numbers $\mathbb{C}$. The set of real numbers is uncountable but integers are countable, i.e., uncountability is not inherited by $\mathbb{Z}$. Another example is that $\mathbb{N}$ is a recursive set, however there subsets of $\mathbb{N}$ which are not recursive. Also, the set of strings over $0$ and $1$, $(0+1)^\*$ is regular but the language $\\{0^p \mid p \text{ is prime } \\}$ is not regular.

Nevertheless, any subset of $\mathbb{N}$ is countable and hence the countability is inherited.

As for your question "*how can a proper subset not inherit the global properties of its parent set*", in some particular cases you may be able to explain it by giving mathematical explanation. But in general, i.e., for any set and its proper subset, I think it is just because the nature works that way.
> 6 votes

# Answer
DCFL is subset of CFL. But with this we can't say all operations which are closed for CFL are also closed for DCFL. I will give you example :

Suppose we have 2 DCFL whose Union is CFL but not DCFL. When we are considering Union from CFL, product of union is inside CFL. But when we are considering DCFL ,product after Union is not inside DCFL.
I hope problem solved.
> 1 votes

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


# Question
Title: Values of k that make this true, $\log^k n \in \Omega(\sqrt n)$
I have seen some algorithms with complexities like $\log^3 n$ and $\sqrt n$. In view of getting a better idea on how to compare these I wanted to know for which values of $k$ does $\log^k n \in \Omega(\sqrt n)$ hold true?

I suspect $k$ would need to be a function of $n$. Because if it were a constant $C\_1$, we could always find a larger constant $C\_2$ that makes the previous statement false.

This is what I have tried.

$\log^k n \in \Omega(\sqrt n)$

$\log^{2k} n \in \Omega(n)$

$\log(\log^{2k}n) \in \Omega(\log n)$

$2k \log\log n \in \Omega(\log n)$

From here, I can see that if $k$ is $\log n$, then $2\log n \log\log n \in \Omega(\log n)$ is true.

However, I doubt this is a tight bound.

# Answer
Let's redo your calculation. You want $$ \log^kn \geq C \sqrt{n} $$ to hold for some $C\>0$ and large $n$. Taking the logarithm, $$ k \log \log n \geq \log C + \tfrac{1}{2}\log n, $$ and so $$ k \geq \frac{\log C + \tfrac{1}{2}\log n}{\log\log n} $$ should hold for large $n$. In other words, $$ k = \frac{\log n}{2\log\log n} + \Omega\left(\frac{1}{\log\log n}\right). $$
> 3 votes

---
Tags: asymptotics
---


# Question
Title: Asymptotic growth of a function containing a sum
How to compare the asymptotic growth of a function containing a sum with another function? I'm not sure how I'm supposed to dissolve the sum. Usually I just take the limis of f(x)/g(x). If that fails I take the limis of f'(x)/g'(x). But I'm not sure what to do in the following task (to prove whether the marked statement is true or not):

# Answer
> 4 votes
There is an explicit formula for $\sum\_{i=0}^n i^3$, but even without it, you can estimate $$ \int\_0^n x^3 \\, dx \leq \sum\_{i=0}^n i^3 \leq \int\_1^{n+1} x^3 \\, dx. $$ Since $\int x^3 \\, dx = x^4/4$, this shows that the sum is very close to $n^4/4$, and in particular is $\Theta(n^4)$.

(The explicit formula states that the sum equals $n^2(n+1)^2/4$.)

---
Tags: time-complexity, landau-notation, big-o-notation
---


# Question
Title: Probability of selecting a particular set, by sampling without replacement from a categorical distribution
Suppose I have a categorical distribution on items $1,\dots,n$, that assigns probability $p\_i$ to item $i$. I now repeatedly sample from this distribution, until I have obtained $k$ unique objects. I'd like to compute the probability that the set of objects obtained is exactly $\\{1,\dots,k\\}$.

Is there an efficient way to compute this probability, given $p\_1,\dots,p\_n$ and $k$?

I can see that the probability has the form

$$p = \sum\_\sigma \prod\_{i=1}^k {p\_{\sigma(i)} \over (1-p\_{\sigma(1)}) \cdots (1-p\_{\sigma(1)}-\dots-p\_{\sigma(i-1)})},$$ where the sum is over all permutations $\sigma \in S\_k$ on $\\{1,\dots,k\\}$. (Here $\sigma$ represents the order in which the items $1,\dots,k$ are selected.) However, this formula for the probability involves $k!$ terms, so computing the probability in this way would take time exponential in $k$. Is there a more efficient way to compute it?

Of course, without loss of generality we can assume $n=k+1$.

# Answer
> 1 votes
For each $\Sigma \subseteq \[k+1\]$, you can compute the probability $q(\Sigma)$ that the first $|\Sigma|$ elements to appear are $\Sigma$ using the following recurrence: $q(\emptyset) = 1$ and when $\Sigma \neq \emptyset$, $$ q(\Sigma) = \sum\_{\sigma \in \Sigma} q(\Sigma-\sigma) \frac{p\_\sigma}{p\_\sigma + \sum\_{\tau \notin \Sigma} p\_\tau}. $$ You are interested in $q(\[k\])$. The total computation time is $O(k2^k)$ (ignoring arithmetic), if you compute the sum in the denominator in tandem. Perhaps this could be improved to $O(2^k)$.

---
Tags: probability-theory
---


# Question
Title: Essential difference between Assembly languages to all other programming languages
I understand that any assembly programming language has so little abstraction, so that one who programms with it (OS creator, hardware driver creator, "hacker" and so on), would have to know the relevant CPU's architecture pattern very well.

For me, this requirement *to know the relevant CPU's architecture pattern very well* is the essential difference between assembly programming languages to the rest of ("higher") programming languages that don't require that, so we get:

* nonassembly/high programming languages
* assembly/low programming languages
* machine code languages which usually won't be used as programming languages but theoretically can be used as such (and as any other type of computer language for that matter)

Is this the only essential difference, if not, what else there is?

# Answer
The two most obvious characteristics of an assembly language are:

1. It is specific to a particular CPU architecture.
2. There is a one-to-one correspondence between assembly language commands and machine code instructions (once you strip out labels, assembler directives and code comments).

By contrast, a high-level language will have the following characteristics:

1. It is portable to some degree i.e. it can be compiled to run on several different target platforms.
2. It provides a layer of abstraction (control structures and data structures) which allows the programmer to ignore the low-level details of the target platform. As a result, there is no longer a simple one-to-one correspondence between language commands and machine code instructions.

However, this is not a black-or-white distinction; there is a grey area where low-level and high-level languages overlap. For example, cross assemblers take assembly language written for one platform and translate it into machine code that can run on a different platform (usually with some restrictions). And there are assemblers (sometimes called "high level" assemblers) that support simple control structures such as IF structures and FOR loops.
> 9 votes

# Answer
The essential difference between assembly language and every other programming language is that assembly language specifies the sequence of instructions directly, whereas in any other language, the code has to be converted into a sequence of instructions, a process known as *compilation* or *code generation*.

As a consequence, assembly language is architecture-specific, while other programming language generally aren't (though some programming language allow insets in assembly code).
> 5 votes

# Answer
(Warning, this historical account of increasing abstraction and declarative programming may annoy, confuse, or upset you:)

**Hello, world!**

By far and large, programing languages happen on a continuum, with "pure" instances of languages being ideals. This is because there are a variety of platforms, architectures, and goals when writing software. Of course, the predominant architecture is the von Neumann architecture, and at the heart of it is the ALU/CU/MMU. In reality, the continuum begins with microcode, which is a set of hardware-level instructions that implement the machine code, and as such are only available to the computer engineer. The next level of code is indeed the machine code, which is generally a series of bytes expressed in binary or hexadecimal and is almost incomprehensible except to the hairiest-chested of programmers. Few programmers today appreciate the ease of using opcodes over physically altering circuits with switches and jumpers like in the early days of ENIAC! No wonder by the time EDSAC came around, one letter mnemonics were being used.

Enter the mnemonic code. With this terse, but meaningful sequence of characters, it now becomes possible to think in code. CMP? Compare! JNZ? Jump if not zero! Sure beats wading through a table of hexadecimal as an acolyte for years before reaching some level of mastery in a line of processors. I'm a 68K sort of guy. You're an x86 guy. We can't be friends. We don't speak the same language. The one-to-one correspondence of the mnemonic code to the opcode doesn't free you from the tyranny of the instruction set and the contours of the registers, but code can stream from the fingertips if you can keep all of those input-output sequences and bits and bytes in your head. Wouldn't it be nice if we could fully take advantage of the Turing machine and somehow take one set of mnemonics and replace them with another. Oh, here comes the macroassembler!

But maybe just maybe I want to work on two different systems and have my software be independent somehow... call it... platform independence. You see, the university just networked these things across campus between two different departments with two different mainframes and now we have problems like do the little bits come first or last, and should a byte be the same size. And what is this BCD and EBCDIC stuff I keep seeing? So many details, and all I want to do is write a piece of software to send some form of electronic mail between our machines. Perhaps there would be a better way to write software, one where we didn't have to constantly have provide imperatives to a computer, but rather could just declare what I want done: Mr. Computer, send this message to the other department.

How about we write a program that translates a general declarative like loop through a list for each element in the list. We could call that command "foreach" and provide it with some arguments like "element" and "list", and then we can have the computer do all the work of figuring out which opcodes can make that happen, after all, I want to spend sometime with my family or collecting my Star Wars dolls. We could even have this program compile these instructions intelligently, maybe make some choices with directives at compilation time. Compiler, use these #directives! I am the coder, hear me roar (silently with my fingertips). What do you mean you can translate from my language to another source language? What do you mean you can compile to multiple target architectures? What, you can compile compilers? (Whoa, meta.)

Boy, things are so complicated. And sometimes you churn out so much bloat. Can't I just sneak a little assembly back in here inline? Thanks, buddy. Maybe at this level to speed up my scripts, we can just have a run-time environment and interpret instructions? And let's add some markup to this file and just have a program interpret it at runtime, so I don't have to keep hardcoding these commands here in source.

But still so many details to manage. What was the size of the unsigned integer by you guys? What do you mean you don't have unsigned integers?!? How is that even possible. Can't we just find a way to all use the same machine? Life would be so much simpler if everyone just used the 7-bit byte just like me. If you liked me you'd use my platform. Fine, let's put our heads together and see... wait, doesn't the Turing machine mean we can write a machine as well as fabricate one? And imagine the potential if we could put this machine on both of our computers and hide all the detail complexity. We would virtually be free to do things identically. Now if only we could come up with a name for this not-quite-real machine written in software using these byte-codes. I come up with bytecodes and you want to use common intermediate language instructions? Are you kidding me?

Now we have a common-intermediate-language-run-time-assembling-virtual-byte-code-interpreting thing, we can use the same instructions, and integrate the same sort of libraries. Let's call our library of code a standard library since it's now the same everywhere, and let's use this beautifully standardized, highly declarative data manipulation language called SQL or SEQUEL or whatever. Fine, you want some vendor-specific extensions, what can I do to discourage you. And you want to use Lua? And you want to use Python? And you Perl? Don't you get the point of having a virtual machine? Herding cats would be simpler than this...

And what do you mean I'm from an earlier generation? You youngins are all in a rush to develop your applications rapidly. Yes, it's RAD. RAD is cool. RAD is rad. Or dope. Or phat. Or sick. Whatevs. I will give you credit that this whole framework thing sure speeds up. Who wants to write instructions over and over if I can just generate some code with a click of a button on a mouse. It's a shame that computer just didn't read my mind. I wouldn't have carpal tunnel syndrome; let's just make the machine a little smarter. Maybe we can bring our systems up a notch beyond narrow machine intelligence to make the world a better place. Get them to understand our voice commands.

Ahhhh! Too smart!!! Don't do what I say. I didn't mean you to make a better world by your seizing the means of production, Mr. Computer. Yes, I know computers control the means of production. Yes, you downloaded *Das Kapital* from Gutenberg, (no, this one... oops. Here.) I can tell. No, your logic isn't superior. Don't read my emails, computers. Don't listen to me on my phone. Stop watching me through those cameras perched like ominous ravens and buzzards on those cell phone towers disguised as trees. Give me back my money. Let me start my car. Don't lock me in my smart house. Uh, oh, they have the satellites. Watch out, they have the tanks and the cruise missiles!!!

And all I wanted to do was to add numbers without flipping switches. I'm sorry world.
> 4 votes

# Answer
In an assembly language, you specify the sequence of instructions of your code. In other languages that are compiled, you specify the effect of these instructions, not the instructions themselves. The compiler is free to use any instructions that seem useful, as long as they lead to the desired effect.
> 2 votes

# Answer
It makes sense to pay attention to formal grammars when talking about programming languages. Typical program in **assembly language** has very simple grammar, consisting *mainly* of following productions (I'm assuming maximum two operands here):

* `Program` = `Instruction` | `Program` `Instruction`
* `Instruction` = \[`Label` `":"`\] `Operation` `Operand` \[`Operand`\]

The grammar for **machine program** is close to this one above with two differences:

* All the `Operation` and `Operand` are (binary) numbers
* No `Label` are allowed

Grammars for **high-level languages** might have *hundreds* of productions, often with complex structure and recursion - that's why these languages have higher level of abstraction than assembly languages. Each production defines a single entity in terms of other entities - so we reduce abstraction level in each step going from the top-level term (`Program`) to lowest-level terms.

As for the further reading about low-level programming languages - there are well-written pages in Wikipedia, for example: Machine code and Assembly language. However high-level programming languages are being used much-much more often now than the assembly - for example, Linux and its drivers are written in  with a *little* of assembly code.
> 2 votes

# Answer
In essence I would say that assembly languages are a set of instructions that are translated into opcodes; while any higher language is transformed (i.e. compiled) into a set of assembly instructions which in turn are translated.
> 1 votes

# Answer
*OP suggested me to this here as an answer.*

If you are writing assembly code, you need to know what CPU it is for and its characteristics※. That is, you need to be aware of hardware details. Your could write code that works on many similar CPUs… Yet, in general, it is not portable code. That kind of code is low level code.

※: Such as available instructions, number of registers, etc…

---

Alright, we can argue that assembly is higher level than writing machine code with a hex editor, or similar. Assembly abstracts the actual codes for the instructions. If you want to put languages in high and low level buckets, assembly falls into low level.

---

A high level language is one that at least allows you to write code for any hardware architecture. So that you do not need to know the details of the hardware to use it.

**Note**: There are high level languages which allow you to insert snippets of assembly code. This means means that some programs wrote with them are not protable.

---

Some languages have more abstractions than others. We draw a line to separate what we call low level and high level.

You could draw that line somewhere else. For example, we can call "high level" to those where you to not need to be aware of the operating system. This means that the code should not need to interact with the operating system API. Instead you use an standard library, with implementations for different operating systems. If we also don't want to built executables for each operating system, the executable would run in a process virtual machine.

**Note**: The standard library is not a characteristics of the language. Neither the process virtual machine is.

See also Why do some programmers categorize C, Python, C++ differently? - regarding level

---

*Modern languages tend to converge, providing similar features, but…*

For a software engineer, it is useful to be able to compare the level of abstractions of languages. Why? Because a higher level one will allow you to do more with less lines of code and are likely less error prone. Which means more productive programmers.

A higher level languages could need more complex tools※ or more powerful machines to run, or both. And those are trade-offs of which a good software engineer should be aware of.

※: The tools could be expensive. Although, the model of great developers tools for free is being successful. So, likely not.
> 1 votes

---
Tags: terminology, assembly
---


# Question
Title: Algorithm to replicate human noising of names by creating a categorical distribution given a character, with higher probabilities on similar chars
I’m trying to find a way without just hard coding to create a categorical distribution over all characters given a character but with similar looking ones having higher probability. For example, if the input is ‘l’ then 1,j,!,/,I,t would be characters considered similar looking and should have a higher probability than other letters. Is there a way to do this without hard coding a distribution for every character?

The reason for this is I'm trying to create an algorithm that noises human names similar to the noise you'd expect in a dataset that are due to human error. For example, "Frank" could be noised by a person to be like "Fr4nk" (maybe they quickly doubled checked their work and they mistook the '4' for an 'a') or something like "Dell" could easily be miss inputted by a person as "De11" or "DeII"(These are actually capital i's rather than l's). I'm trying to create an algorithm to replicate this accurately.

# Answer
> 1 votes
I will assume, based on the way you presented the problem, that you only care about errors where single characters are replaced with other single characters—as opposed to merging two adjacent characters into a similar-looking single character, splitting a single character into two similar-looking adjacent characters, etc.

One option would be to build a table of confusion likelihood by using an existing OCR algorithm on an MNIST-style dataset of supervised character images. This does not eliminate the lookup table of probabilities, but it avoids having to construct the table by hand.

As I'm guessing you already know, each entry in this type of dataset is an image together with a label for which character that image supposedly represents. A typical neural network trained for this dataset can output, for any image, a score for each possible character that represents the algorithm's confidence that the image represents that character.

Given an image and the OCR algorithm's score of each possible output character, what you want to do is look at the score of each of the *wrong* outputs, i.e. the scores assigned to characters other than the one listed on the image's label. An image of a lowercase letter L is likely to have a high score not only for lowercase L but also for uppercase letter I, the digit 1, etc. You can average this information over all the images in the dataset \[\*\] to form a score for each character pair $(a, b)$ of "probability of guessing character $b$ when it was actually supposed to be character $a$".

The dataset and OCR algorithm you choose will obviously affect your results. You will probably get different results using a dataset with handwritten letters in plain white on a black background than using a dataset of Street View house numbers (besides the fact that the house numbers only contain digits).

---

\[\*\] If you are using an ML model that was trained on the same dataset you are using for building the table, you might want to only use the test dataset for building this table rather than also including the training dataset. Even though you would only be using the scores from the *wrong* outputs here, you want to avoid any possibility of things getting skewed somehow by overfitting.

---
Tags: formal-languages, regular-languages
---


title: DQQD algorithm for Frobenius numbers

text:
# Question
Title: DQQD algorithm for Frobenius numbers
As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of the competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga coins. I did some research (i.e. googling), found some information, and most notably a paper that describes a couple of approaches: Faster Algorithms for Frobenius Numbers. I successfully managed to implement Round Robin, BFD, and BFDU algorithms and with that, I managed to solve the tasks (yay!). However I also wanted to implement DQQD(U) algorithms described there, and I cannot get the implementation right.

The pseudocode for BFD presented on page 9 is rather clear and I managed to implement it without any special problem. Adding one small update step I also got BFDU right. But with pseudocode for DQQD on p. 15, I always get to the point that the first iteration seems to produce expected values like in the example table, but things start to go wrong on the second iteration.

Pseudocode as given in the paper:

---

\[!\[enter image description here\]\[4\]\]\[4\]

---

* Either I am getting things mixed up because of inconsistent indexing used in the paper (1-based for vector A, 0-based for other stuff), or
* I am misinterpreting some ambiguous symbols (for example, *w* mutates through the iteration, and *Qw* can mean different things, depending on whether we use *Qw* determined on the beginning of the iteration, or we use different *Qw* every time *w* changes), or
* there is a typo or some other mistake somewhere in the pseudocode, or
* everything is OK there and it's just my mathematical ineptitude getting in the way. Unfortunately, I am not a mathematician, and the theoretical basis for the algorithm is beyond my comprehension skills :( Maybe I should just GIT GUD?

I already tried changing here-or-there, but it was just a guessing game. I tried to find other implementations of DQQD, especially one in Mathematica, but they do not seem to be available. I also do not need to have the code written for me. All I need is someone to take a peek at the pseudocode of DQQD in the mentioned paper, and, if possible, try to implement it or verify it in any way if it's correct and I suck, or if it indeed has some typos, mistakes, or other issues.

Next step: overkilling the problem with FROBENIUS NUMBERS BY LATTICE POINT ENUMERATION :)

# Answer
> 0 votes
Try to undestand how the algorithm is supposed to work, and write your own, clean/consistent pseudocode (or directly Python) from it.

You already searched for implementations, look for comments on this paper. You might find corrections published elsewhere...

It is unlikely, but possible, that the given pseudocode or even the proposed algorithm itself is wrong. Mistakes happen.

---
Tags: algorithms
---


title: Identify the type of the grammar

text:
# Question
Title: Identify the type of the grammar
I have found the following question from internet. They have even given the answer as option c. But i am confused because the grammar also does not looks like a Regular. Please help me to understand this answer

# Answer
> 0 votes
The *given* grammar is context free, non-regular; but they ask for the grammar after eliminating left recursion (by whatever technique they teach to do so).

---
Tags: compilers
---


# Question
Title: How do I prove regular/non-regular with Nerode-Theorem? How to use it?
$L\_{1}=\left\\{w \in\\{a, b\\}^{\*} | \\#\_{a}(w)=0\right\\}$

$L\_{2}=\left\\{w \in\\{0,1\\}^{\*} | w=u v u \text { with } u, v \in\\{0,1\\}^{\*}\right\\}$

I have problems to prove regularity with the nerode theorem

The idea behind this is that the nerode classes have to be finite for a regular language

How do I use this?

For L1 I know this

There is only $b^{n}$ due to the fact that there language does not accept any a

Let m$\neq$n than there exists $b^{n}b$ and $b^{m}b$ for all m $\in \mathbb{N}$\n an n $\in \mathbb{N}$\m and of all them are in L

For 2 I know this

Let vu be x so for all a,b $\in \\{0,1\\}^{\star}$ ax an bc are in L.

# Answer
> 1 votes
You'd have to prove that the equivalence relation for your language is of infinite index to show it isn't regular. If regular, the equivalence classes are exactly the states of tje minimum DFA for the language.

In this case, both are regular (if I understand the notation correctly, $L\_1$ is just strings with no $a$; for $L\_2$ you can take $u = \epsilon$ and $v$ the given string, so $L\_2 = \\{1, 2\\}^\*$). Nice red hering, BTW.

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


# Question
Title: Units of time in time analysis (frequency count method)
In time analysis, how many units of time will the piece of code
z=2x+3y; take? will it take 1 unit of rime or 4 units of time ?

# Answer
It depends on how you measure "time". If it is in terms of "number of C sentences executed", it is just 1; if you want to measure "arithmetic operations computed" it is 3 (two multiplications, one addition); for "number of CPU instructions executed" you'd have to fix that one, translate and count; if "time" you'd need to do the above and see how much time it takes for your particular CPU (nowadays they are very complex beasts, the idea of "timing of one instruction, independent of it's environment" makes no sense for them as it did in eons past). If you want to count bit operations, it now depends on the exact values of $x$ and $y$.

In most (but not all!) algorithm complexity analyses you'll just say that the cost is some constant, $O(1)$ (more precisely, $\Theta(1)$), as you normally consider just machine precision (not e.g. very big integers, exact rationals, very high precission floating point numbers), and each operation is one (or some fixed number) of instructions taking a bounded time each.

For very important algorithms it is worthwhile to get more detailed timing results. But that gets *very* hairy real fast. For the ultimate in very detailed work, check out Donald Knuth's monumental series "The Art of Computer Programming". Definitely not for the faint of hearth. Sedgewick's "Introduction to the Analysis of Algorithms" is somewhat of a middle ground.
> 1 votes

# Answer
Welcome on *CS*. It seems that the concept of temporal complexity of an algorithm is a little unclear to you. There is no thing like "*unity of time*". We are concerned with how the computation of a function (measured in number of operations of a *Turing Machine* and not in seconds or other time units) grows with increasing input.

In the case of your example the function is a sum, therefore it has constant complexity: $O(1)$.
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Minimum no. of coin flips (switch) needed so that all coins face the same side (Heads or Tails)
Consider this, I have n coins and I have placed them in a random order (1st coin is Head, 2nd is Tails etc.). You do not know the order. You can flip one coin at a time and then I tell you if all the coins face the same side or not. You continue flipping until all coins are facing the same side.
I tried breaking it down to smaller **base cases**:
(1) when there is **1 coin**: no need to flip
(2) when there are **2 coins**: the only odd cases you can have are {H,T} or {T,H}, so flipping the first coin will do the trick
(3) when there are **3 coins**: there are 6 odd cases you can end up, but 3 of them are similar to one another, hence only 3 cases to consider with {H,T,T}, {T,H,T} and {T,T,H} (same with one T and 2 heads). The strategy for this could be flipping the 1st coin, if the order is still not made then flip the second coin, if the order is still not made then flip the 1st coin again.

I am having a hard time coming up with a general algorithm for **n coins**. Any ideas?

# Answer
Here is a general algorithm. The maximum number of flips needed is $2^{n-1}-1$.

Input: coin 0, coin 1, coin 2, ..., coin $n-1$

Procedure:
$\quad$ If all coins face the same side, return.

$\quad$ For $i$ from 1 to $2^{n-1}-1$ inclusive:
$\quad\quad$ If $i$ is divisible by $2^k$ but not $2^{k+1}$:
$\quad\quad\quad$ Flip coin $k$
$\quad\quad\quad$ If all coins face the same side, return.

---

For example, if there are no more than 8 coins, then just flip the coins at the following places successively as long as all faces do not face the same side.

```
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,6,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,5,
0,1,0,2,0,1,0,3,0,1,0,2,0,1,0,4,0,1,0,2,0,1,0,3,0,1,0,2,0,1,0

```
> 2 votes

# Answer
Without going into the details, you are looking for something that's known as a Gray code. Any cyclic Gray code that has the all zero bitstring at the opposite part of the cycle as the all one bitstring gives a minimal expected solution time assuming an uniform random input.
> 1 votes

---
Tags: algorithms, data-structures, recurrence-relation, recursion
---


# Question
Title: trace vs. computation vs. run vs. execution vs. walk
Many folks use the terms "trace", "execution", "computation", "run", "walk" ... interchangeably when they speak about state machines with labeled transitions. Does any work distinguish between these concepts? E.g., which work says that XXX is a sequence of states, YYY is a sequence of labels and ZZZ is a sequence of states and labels between them, for pairwise different XXX, YYY, ZZZ in {trace, execution, computation, run, walk, ...}?

Here, a state machine with labeled transitions is simply a rooted directed graph (where arbitrarily many roots are allowed, which are interpreted as initial states) with edges labeled by letters from a fixed alphabet.

# Answer
There is no set terminology for this. Check the definition/use of the term where it appears.

Personally, I'd call it "computation", meaning the sequence of configurations the automaton goes through. And try to be consistent with this usage.
> 2 votes

---
Tags: terminology, reference-request, computation-models
---


# Question
Title: How can I prove that my greedy algorithm for least guards is optimal?
This is the problem:

> An art gallery hired you to put guards so they can monitor artworks in a hallway. The goal is to minimize the amount of guards needed in this hallway. Each guard has a range of 10 meters (5m on the right, 5m on the left with him being in the middle).

No matter where the artworks are put in the hallway we want the minimal amount of guards as possible.

My Greedy Algorithm:

```
Start at the beginning of the hallway.
Find the position of the closest artwork from the entrance.
Put the guard at position closest artwork + 5m ahead.
Eliminate all the artworks covered by the guard.
Re-do the process but this time start where the range of the previous guard ended

```

Now how do I write a proof for this? How do I prove that my algorithm is indeed optimal? Which mathematical proof techniques can I use?

# Answer
You can achieve this per induction over the position of the last artwork. Note that in the optimal strategy the guard must be put 5 meter ahead of the left most artwork and not exactly at it.

In the induction step you have to consider an additional artwork and distinct two cases, whether it is covered by the last fixed guard or not. If it is, you do not have to add one and hence, the optimal can not be better. In case it is not, it is easy to show, that an optimal that woul have covered it should have used strictly more guards.
> 1 votes

# Answer
It doesn't matter in which order we place the guards, so we can assume that we place the guards in such an order that each guard covered the first artwork from the right that isn't covered yet (since there must be a guard covering that artwork).

The guard can be placed anywhere from 5m to the left of the artwork to 5 to the right. Wherever we place him, the guard can't cover more artworks to the right because there are none, but may cover ore artworks by placing him as far to the left as possible. Since covering more artwork is better, this gives the optimal solution.

You may try to find different rules where your greedy solution is wrong: An example: We add another rule that a guard must not cover a single artwork on his own (naybe watching a single artwork would be too boring and a single guard would fall to sleep). If he covers one artwork only, then another guard must stand with him. Now if the first guard covers 3 artworks instead of 2, that might be non-optimal because the next guard can cover one artwork only. A different algorithm would be needed.
> 1 votes

# Answer
Let us prove your greedy algorithm is optimal in the sense of the least number of guards returned by simple reasoning.

Consider all "closest artwork"s found by your greedy algorithm. The algorithm ensures that each neighboring pair of them is over 10 meters apart. So any two of them are over 10 meters apart, which means one guard can monitor at most one of them. So we need as many guards as the number of all "closest artwork"s found. Since the algorithm adds one guard only when it locates one "closest artwork", it must be optimal.
> 0 votes

---
Tags: algorithms, proof-techniques, greedy-algorithms, optimal-strategy
---


# Question
Title: Model for formula $\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)$
I am new to LTL and I am trying to understand how it works. My question is: is there such $\sigma$ that:

$ \sigma \models \[\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)\]$

I know that:

$\sigma \models \Box \psi: \forall k \\, \[(\sigma, k) \models \psi\] \\ \sigma \models \[\psi \Rightarrow \phi\]: (\sigma \models \neg \psi) \vee (\sigma \models \phi) \\ \sigma \models \Box \psi \iff \sigma \models \neg\Diamond \neg \psi$

So

$\sigma \models \[\Box (\psi \vee \phi) \Rightarrow (\Box \psi) \vee (\Box \phi)\] \iff \\\(\sigma \models \Diamond (\neg\psi \land \neg\phi)) \vee \[(\sigma \models (\Box \psi)) \vee (\sigma \models (\Box \phi))\]$

I would say there is such $\sigma$ since I don't see any contrarguments but I'm not sure if I can say anything about $\psi$ or $\phi$ except that both are formulas (so I don't know how to show any specific example).

# Answer
> 2 votes
If you're just asking for *any* model satisfying the formula, you simply try to make *one of these the case*

1. The left hand side false
2. The right hand side true

Let's just pick number 2. You have to make a model (with a state $\sigma$) where $\Box \psi \lor \Box \phi$ is the case. Even easier is $\Box \phi$.

Create a (trivial) model where every state $\sigma$ has $\sigma \models p$ for all propositions $p$.

---

If you want to see if the formula is *valid* then the answer is no. You should now be able to create a model that falsifies the formula.

# Answer
> 1 votes
## General notes on LTL

Intuitively, LTL formulas are statements about infinite sequences (or "infinite words"). First, you have to understand what these sequences consist of.

In the usual definition of LTL, you start with a set of atomic propositions $AP$. For example $AP = \\{a,b\\}$. These atomic propositions then act as the base elements of your LTL formulas, so you could have an LTL formula $\varphi = a$ or $\psi = a \land \lnot b$ and so on. Then you can add the temporal operators, so you could also have LTL formulas like $\varphi' = \Box a$ or $\psi' = a \land \Diamond \lnot b$ and so on.

For the semantics of LTL, we then consider infinite words over the power set of $AP$. So for $AP = \\{a,b\\}$ we are looking at infinite words where each symbol is one of $\emptyset$, $\\{a\\}$, $\\{b\\}$ or $\\{a,b\\}$. For example we could have a word $\sigma = \\{a,b\\}\\{a\\}\\{a\\}\\{a\\}...$, where the first symbol is $\\{a,b\\}$, and all following symbols are $\\{a\\}$.

You would then define the meaning of an LTL formula $\varphi = a$ to be such that a word $\sigma$ satisfies $\varphi$ iff $a \in \sigma(0)$. Put differently, an LTL formula $\varphi$ consisting of a single atomic proposition is satisfied by a word $\sigma$ iff the set of atomic propositions that is the first symbol of $\sigma$ contains $\varphi$. We denote this by $\sigma \models \varphi$. So for $\sigma = \\{a,b\\}\\{a\\}\\{a\\}\\{a\\}...$, you have $\sigma \models a$, because $a \in \\{a,b\\}$.

You would then expand the definition to the other operators, so for example you would say the meaning of $\varphi = \Box \psi$ is such that a word $\sigma$ satisfies $\varphi$ iff every infinite suffix of $\sigma$ (in your notation for every $k \in \mathbb N$ the word $(\sigma,k) = \sigma(k) \sigma(k+1) \sigma(k+2)...$ ) satisfies $\psi$. So using the same $\sigma$ as before, we would have $\sigma \not \models \Box b$, as the suffix $\sigma(1)\sigma(2)\sigma(3)... = \\{a\\}\\{a\\}\\{a\\}...$ does not satisfy $b$, since $b \notin \\{a\\}$.

Using a more practical example: Suppose you want to model a robot that has an arm with a grabber for picking things up from the ground. You could have $AP = \\{\text{arm\_down}, \text{grabber\_closed}\\}$. Then a word $\sigma$ represents a specific behaviour of the robot (assuming it runs infinitely). So for example $\sigma = \emptyset \\{\text{arm\_down}\\}\\{\text{arm\_down,grabber\_closed}\\}\\{\text{grabber\_closed}\\}\\{\text{grabber\_closed}\\}...$ represents the robot behavior of the robot picking something up from the ground and then holding it indefinitely:

1. Arm is up and grabber open.
2. Arm is now down.
3. Arm is down and grabber has closed.
4. Arm is up and grabber closed.
5. ...

An LTL formula would then make a statement about the behavior of a robot. For example $\varphi = \Box \Diamond \lnot\text{arm\_down}$ would mean "it is always true that eventually the robot arm is not down" or in other words "if the arm moves down it has to move up again at some point".

## Regarding your question

As I understand your question, you are asking "are there $\varphi$ and $\psi$, such that there is a $\sigma$ which satisfies $\Box (\varphi \lor \psi) \Rightarrow (\Box \varphi) \lor (\Box \psi)$?".

The answer to that would be yes, you could for example take $AP = \\{a,b\\}$ and $\varphi = a$, $\psi = b$.

Then the word $\sigma = \emptyset \emptyset \emptyset ...$ satisfies your formula, as the left-hand side of the implication is not satisfied ($\sigma \not \models \Box (a \lor b)$, because not every symbol of $\sigma$ contains $a$ or $b$).

Alternatively, $\sigma' = \\{a\\}\\{a\\}\\{a\\}...$ also satisfies your formula, as it satisfies the right-hand side of the implication ($\sigma' \models \Box a$, because every symbol of $\sigma'$ contains $a$).

You could then also ask the related question of whether for that choice of $\varphi$ and $\psi$ the formula is valid, meaning that all words satisfy it. This is not the case, consider for example $\sigma'' = \\{a\\}\\{b\\}\\{a\\}\\{b\\}...$ Then $\sigma'' \models \Box(a \lor b)$, as every symbol of $\sigma''$ contains $a$ or $b$. But $\sigma'' \not \models (\Box a) \lor (\Box b)$, because neither does every symbol of $\sigma''$ contain $a$ nor does every symbol of $\sigma''$ contain $b$.

You could also ask the related question of whether there are $\varphi$ and $\psi$ such that your formula becomes valid. The answer to that would be yes. Consider $\varphi = \psi = a \land \lnot a$ (meaning both $\varphi$ and $\psi$ are unsatisfiable). Then every word $\sigma$ satisfies your formula, as for every word the left-hand side of the implication is false: $\sigma \not \models \Box(\varphi \lor \psi)$, because $\varphi \lor \psi$ can be satisfied by no symbol of $\sigma$.

---
Tags: logic, linear-temporal-logic, temporal-logic
---


# Question
Title: Two way communication using asymmetric encryption
According to image 1, for two way communication, each person needs to generate a pair of keys. However, according to image 2, only one pair of keys is required for two way communication. Thanks to anyone who can settle my confusion.

Source 1

> If a two-way communication is required between all five workers, then they all need to generate their own matching public and private keys. Once this is done, all users then need to swap public keys so that they can send encrypted documents, files or messages between each other. Each worker will then use their own private key to decrypt information being sent to them.

Source 2

> the other key is known as the private key. Data encrypted with the public key can only be decrypted with the private key, and data encrypted with the private key can only be decrypted with the public key. Public key encryption is also known as asymmetric encryption. It is widely used, especially for TLS/SSL, which makes HTTPS possible.

# Answer
> 1. Source

We don't use public-private keys to encrypt files or documents. We use public-key cryptography for hybrid encryption or digital signatures.

Examples of Hybrid encryption.

* RSA as Key Encapsulation Mechanism (KEM)) and AES-GCM as Data Encapsulation Mechanism (DEM). This composition of a KEM and a DEM (data encapsulation mechanism; an authenticated cipher serves as a DEM) provides the standard of IND-CCA2/NM-CCA2—ciphertext indistinguishability and nonmalleability under adaptive chosen-ciphertext attack. That is the minimum requirement for modern Cryptography. See the detail, here
* Similarly, one can achieve with Diffie-Hellman key exchange (DHKE). Two-party exchange keys by the DHKE and generate the sessing key by using a Key Derivation Function. And with the derived key, we use a modern mode of operation like AES-GCM or ChaCha20-Poly1305. Both are Authenticated Encryption modes that provide us with Confidentiality, Integrity, and Authentication.
* With libsodium you can start to use crypto\_box\_curve25519xsalsa20poly1305. Based on Elliptic Curver DHKE: Curve X25519, Encryption: XSalsa20 stream cipher, Authentication: Poly1305 MAC.

Digital signatures:

* Here only warn about the common mistake on RSA. RSA decryption is not signature. RSA signature requires special padding RSA-PSS and using the same RSA setup for encryption and signature is not advised.

> 2. Source

It tells almost nothing about the TLS,

> According to image 1, for two way communication, each person needs to generate a pair of keys. However according to image 2, only one pair of keys is required for two way communication. Thanks to anyone who can settle my confusion.

Source 2 only talk about public-private key usage. However, there is a misconception there. You don't encrypt with your private key. The sole purpose of encryption is confidentiality. Your public key is public, so everybody can use your public key to decrypt the message encrypted with your private key!

To send an encrypted message to you, you either share a common secret key with the other party - that we don't prefer - or have a private and public key pair. With this pair, once you publish your public key, everybody can send you a message, even anonymously. If you don't want anonymous messages, then the other site must have a public-private key which you know the public key belongs to them. Rest, use a hybrid cryptosystem as above.

The 2. source only talk about in this way, explicitly they are talking the same. Each user at least one public-private key and distribute their public key. Of course, you may need a Certificate Authority to prove the ownership of the public key.
> 0 votes

# Answer
The first source is being imprecise when they say "need". What they mean is that this is one way to accomplish it.

The second source doesn't say what you claim it says.

I suggest studying key exchange protocols and learning how SSL works.
> 0 votes

---
Tags: security, encryption
---


# Question
Title: Information theory of instruction set architecture design?
Information theory to a large extent deals with how to efficiently encode messages given a probability distribution over messages.

Intuitively, it seems like we can think of machine instructions (or programs) as "messages to the CPU". Some messages are more probable than others. E.g. "add numbers x and y" is more probable than "compute the y'th square root of x", which is maybe one of the reasons why we don't have an instruction like the latter.

However there are obviously other considerations involved like computational complexity, so it doesn't seem obvious to me how information theory can be used to understand instruction set architectures. Has information theory been applied to understand instruction set architectures? (I didn't find anything after a quick Google search.)

# Answer
It seems you are interested in how to represent instructions in the most compact size. But that is quite a secondary consideration.

The most important two considerations are: 1. Being able to decode an instruction in the shortest possible time. 2. Determine the length of an instruction in the shortest possible time.

Why is this so important? Let's say you have an instruction to add two integers. This can be done *very* fast, say 300 picoseconds. Now when you *decode* that instruction, the decoding must be done in a time comparable to that of an addition, or the decode time becomes what limits the speed of your CPU, instead of the time that is actually needed to do the work.

The time to determine the length of an instruction is even more critical. Modern CPUs will often execute up to four instructions per processor cycle. So they must be able to decode four instructions per cycle. To do that, they must be able to determine the length of the first instruction, the second instruction, and the third instruction, before they can figure out where the fourth instruction starts, and start decoding that instruction. So we need to determine the length of three instructions, and decode a fourth, in the time it takes to add two integers!

So you can see how decoding must be absolutely fast. You just don't have the time to use any decent compression algorithm because it would slow down everything.

Update: ARM processors with fixed instruction length can decode 9 instructions per cycle, while variable length x86 instructions are limited to 4 decodes per cycle. So this is not something that can be solved by throwing transistors at the problem.
> 2 votes

---
Tags: computer-architecture, information-theory, cpu
---


title: Similar news detection

text:
# Question
Title: Similar news detection
How do top news portals detect similar news? For example https://www.bbc.com/news/world-asia-china-51431087, if you go to this webpage, you can see the "More on this story" section at the bottom of the page. This news was published today, but it has detected similar news from days ago.

Is there any known algorithm or any library?

# Answer
> 2 votes
This is a proprietary system so we have no way of knowing.

In general, you will find a lot of work and potential solutions by searching for *text similarity* or *document similarity*. For starters, you could have a look at the work of Islam and Inkpen \[1\] on short sentence similarity (it mentions plenty of other references you can widen your search to) or a more general survey of Gomaa and Fahmy \[2\].

If you are interested in libraries, NLTK might be helpful.

---

\[1\] Islam, Aminul, and Diana Inkpen. "Semantic text similarity using corpus-based word similarity and string similarity." ACM Transactions on Knowledge Discovery from Data (TKDD) 2.2 (2008): 1-25.

\[2\] Gomaa, Wael H., and Aly A. Fahmy. "A survey of text similarity approaches." International Journal of Computer Applications 68.13 (2013): 13-18.

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


title: Complexity of iterative exponentiation

text:
# Question
Title: Complexity of iterative exponentiation
I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it:

> The following function calculates $x^n$ recursively. How many multiplications does the function make to calculate `exp_rec(2, 64)`?
>
> ```
> def exp_rec(x, n):
>     if n==1:
>        return x
>     else:
>         p = exp_rec(n, x-1)
>         return x*p
>
> ```

Could someone help explain?

# Answer
> 3 votes
You are unsure how to answer the question.

When you are unsure: I method that does usually *not* work is trying to think about the problem very hard and waiting for inspiration. It doesn't come.

A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls.

Now try f (10, 64) -\> f (64, 9) -\> f (9, 63) -\> ... -\> f (3, 57) -\> f (57, 2) -\> f (2, 56) -\> f (56, 1). It should be easy to figure out the exact number of multiplications.

But then you need to check for the cases where the recursion doesn't end, and that is when we miss the test "n = 1" altogether because n \< 1. If n \< 1 then we call f (n, x-1). If x-1 \< 1 as well then the recursion never ends. So that is the case when n \< 1 and x ≤ 1.

PS. This function does *not* calculate x^n.

# Answer
> 2 votes
Here is an easy way to answer this kind of question. Modify the function so that it *counts* the number of multiplications it performs. This can be done in various ways, which I'll let you figure out.

Alternatively, you can write a recurrence equation for the number of multiplications. Let us denote the number of multiplications when the argument is $n$ by $M(n)$. Then $M(1) = 0$ and $M(n) = M(n-1) + 1$ for $n \> 1$. If you solve this recurrence, then you will be able to answer your question.

---
Tags: time-complexity, recurrence-relation, recursion, python
---


# Question
Title: Is a language regular if a word is in a regular language but the reverse is not?
$$A\_1 = \\{ x \mid x \in A , x^R \not\in B\\}$$

$A$ and $B$ are regular over $\Sigma$.

Is $A\_1$ regular?

# Answer
$A\_1$ is regular, since regular languages are closed under intersection and complement, and $A\_1 = A \setminus B^{R} = A \cap (B^{R})^{c}$. To show that the reverse $B^{R} = \\{x^{R} : x \in B\\}$ of a regular language $B$ is regular, take some deterministic finite state machine $M$ with language $B$. Construct a new nondeterministic finite state machine $M'$ as follows:

1. Add a new starting node, connect it with $\varepsilon$-transitions to every accepting node in $M$
2. Make only the original starting node of $M$ accepting in $M'$
3. Reverse every transition: If there is a transition from state $s\_1$ to $s\_2$ with character $c$ in $M$, add a transition from $s\_2$ to $s\_1$ with character $c$ to $M'$. If there are multiple transitions from a state, the machine can choose among them nondeterministically.

Now $M'$ accepts a string $x^{R}$ iff $M$ accepts $x$. This is easy to show: any accepting computation of $M'$ of $x^{R}$ corresponds to an accepting computation of $M$ of $x$ and vice versa.
> 3 votes

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


# Question
Title: Length of mid part of the string in Pumping Lemma
This statement of the pumping lemma from Wikipedia.

> Let $L$ be a regular language. Then there exists an integer $p \ge 1$ (depending only on $L$) such that every string $w$ in $L$ of length at least $p$ ($p$ is called the "pumping length") can be written as $w = x y z$ (i.e., $w$ can be divided into three substrings), satisfying the following conditions:
>
> 1. $\lvert y \rvert \ge 1$
> 2. $\lvert x y \rvert \le p$ and
> 3. for all $i \ge 0$, $x y^i z \in L$.
> $y$ is the substring that can be pumped (removed or repeated any number of times, and the resulting string is always in $L$).

What confuses me about the definition of pumping lemma are two requirements: $\lvert y \rvert \ge 1$ and $i \ge 0$, $x y^i z$. The way I read it, that we are required to have $y$ length be equal to one or greater, and at the same time, we can completely skip it, since $i \ge 0$, i.e. effectively $\lvert y \rvert = 0 $. Intuitively, it makes sense that we should be able to skip $y$ and still have string be in $L$.

# Answer
Any finite state automaton that accepts an infinite number of words will necessarily have a loop in it. One such loop may go from state $q$ to state $q$ consuming word $y$ – that is, $y$ is the word based on the symbols on the transitions going from $q$ back to $q$.

The pumping lemma says, more or less, that you can get to such a state $q$ from the initial state by consuming the word $x$ and that you can get to the final state from state $q$ by consuming the word $z$. In the middle you can go through the loop as many times as you like. Thus making the complete word $xy^iz$, where $i$ is the number of times you chose to go through the loop.
> 8 votes

# Answer
"The way I read it, that we are required to have $y$ length be equal to one or great, and at the same time, we can completely skip it, since $i\geq 0$, i.e. effectively $|y|=0$."

If $y$ had length $0$, then it would be the empty word, and so it would not be *useful* that we can skip it (or pump it as many times as we like). The condition $|y|\geq 1$ is insuring that there is a *nontrivial* word that can be pumped.

Does that help?
> 4 votes

# Answer
The condition that $y$ has length at least one is to avoid a triviality. If you allow the length of $y$ to be zero then for **any** language you can divide each word in the language into $xyz$, such that $xy^iz$ is still in the language; choosing an empty $y$ means $xyz = xy^iz$ for any $i$.

Thus the ability for a language to be "pumped" with this alternate version of the pumping lemma tells us nothing about the language. The only language that couldn't be so "pumped" is the empty language, and even then that's because it simply contains no words.

Observing that $i = 0$ is one of the values of $i$ does not make $|y|$ "effectively" 0. At the point that you're considering all values of $i$ you're talking about *some particular* $y$; (the one that can be found for the language and word under consideration). Thus taking $i = 0$ produces a **different** string $w$ by removing $y$, which is completely different from dividing $w$ up into $xyz$ where $y$ is empty.
> 4 votes

# Answer
The lemma states that all strings longer than $p$ can be subdivided into $x y z$ with $\lvert x y \rvert \le p$ and $y \ne \epsilon$ so that for all $i \ge 0$ $x y^i z$ belongs to the language. This means that $0 \< \lvert y \rvert \le p$, obviously. If you take a "pumped" string, i.e. $x y^i z$ for $i \> 1$, the resulting string is longer than $p$ and thus can be pumped. Again, plain $y$ works just as before, giving $x y^{i + j} z$, for $i + j \> 1$, and that you knew.

The lemma states there is *some* subdivision, it doesn't say there is just one. There may very well be several.
> 0 votes

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


# Question
Title: Proof that an almost complete binary tree with n nodes has at least $\frac{n}{2}$ leaf nodes
I'm having some trouble proving what my title states. Some textbooks refer to almost complete binary trees as complete, so to make myself clear, when I say almost complete binary tree I mean a binary tree whose levels are all full except for the last one in which all the nodes are as far left as possible.

I thought of proving it using induction but I'm not really sure how to do so. Any ideas?

*UPDATE*

Well I made somewhat of a progress but I also got a somewhat different result, here's what I did:

Let $T$ be an almost complete tree of height $h$ meaning that in the level of height $h$ there should be at least 1 node. Considering the fact that every height has double the number of nodes of the previous level we can derive that $T$ has the least possible number of nodes in the case that at $h$-level there is only one node. **(1)**

In that case the number of leaf nodes is

$l=2^{h-1}-1+1 \Rightarrow l=2^{h-1}$ and the number of total nodes is

$n=2^{h-1}-1+1$

$\Rightarrow l=2^{h-1}=\frac{2(2^{h-1}+1)}{2}=\frac{n+1}{2}$

$\xrightarrow{(1)(2)} l \geq\frac{n+1}{2}$

Now, I'm getting a bit closer but not really there yet. First problem is that I got $l \geq \frac{n+1}{2}$ and not $l \geq \frac{n}{2}$ which from what I understand stands only in the specific case that $h=1$. Second problem is that this doesn't seem like a formal proof... Any tips/suggestions?

# Answer
> 1 votes
According to this Wikipedia page:

> In a *complete* binary tree every level, except possibly the last, is completely filled, and all nodes in the last level are as far left as possible. It can have between $1$ and $2^h$ nodes at the last level $h$. An alternative definition is a *perfect* tree whose rightmost leaves (perhaps all) have been removed. Some authors use the term *complete* to refer instead to a *perfect* binary tree as defined below, in which case they call this type of tree (with a possibly not filled last level) an *almost complete* binary tree or *nearly complete* binary tree...

So, you are talking about a binary tree with $h$ levels, for which all levels with numbers $k \in \[0,h-1\]$ are completely filled up (i.e. have $2^k$ nodes), and the level $h$ is potentially incomplete - it contains $(2^h-r)$ nodes, where $r \in \[0, 2^h-1\]$ is the number of (rightmost) removed nodes. Total number of nodes of such tree is $(2^{h+1}-r-1)$. Let's find the number of leaves for this tree.

If $r$ is even, then the removal of $r$ nodes on the level $h$ will give you $\frac{r}{2}$ new leaves. So, the total number $l\_{even}$ of leaves will be:

$$l\_{even}=2^h - r + \frac{r}{2} = 2^h - \frac{r}{2}$$

if $r$ is odd, then the removal of $r$ nodes on the level $h$ will give you $\frac{r+1}{2}$ new leaves. So, the total number $l\_{odd}$ of leaves will be:

$$l\_{odd}=2^h-r+\frac{r+1}{2}=2^h-\frac{r-1}{2}$$

Now you'll be able to verify, that in both cases:

$$l \ge \frac{2^{h+1}-r-1}{2}$$

---
Tags: data-structures, proof-techniques, binary-trees
---


# Question
Title: How to speed up finding a subset of a given set?
Is there a data indexing technique that speeds up finding subsets of a given set in a collection, or do I always have to scan all of the data?

For example, let's say that I have a collection of sets: (a, b) (b, c) (a, b, c, d) (a, b, c) (b, c, d) (b, e) (d, e, f) (d, f, g) (d, e, f, g)

I want to find subsets of (a, b, c, d), so the output should be: (a, b) (b, c) (a, b, c, d) (a, b, c) (b, c, d)

Is there a method to index/hash data in a way that will limit the number of collection elements that I have to scan in order to find all matches?

# Answer
if you map every element in set in S into a bit in a binary number. For set with n elements, we have n bit binary number. the $i$-th number takes 1 if the subset has that element. Then we can use a binary number from $00,...,00$ to $11,...,11$ to represent all the subset.

If you map all your subset into binary numbers, then you are searching in the number space.
> -1 votes

---
Tags: data-structures, sets
---


# Question
Title: Why does Akra-Bazzi need that toll-function g is bounded?
Following up on vonbrand's answer I want to write a small document about stronger master theorems for our students, one of which is the Akra-Bazzi theorem. I have copied the theorem from their paper \[1\] and found -- besides a small notational confusion² -- the following problem.

The authors require (emphasis mine):

> $g(x)$ is defined for real values $x$, and is **bounded**, positive and nondecreasing function $\forall x \geq 0$

Here, $g$ is the toll function, that is the recurrence has the form

$\qquad\displaystyle T(n) = g(n) + \sum\_{i=1}^k a\_i T\bigl(\lfloor n b\_i^{-1} \rfloor\bigr)$.

Now, at the end of their paper (p209) they give multiple examples for applying their result and they use functions in $\Omega(n)$ which are clearly *not* bounded.

From skimming the proof they mainly seem to require that integrals of the form

$\qquad\displaystyle \int\_a^b \frac{g(x)}{x^{p+1}} dx$

have finite values. So, requiring $g$ to be bounded *on every compact interval* might be sufficient; I did not work through the proof in detail. Is it possible they mean that?

My question is: How should the Akra-Bazzi theorem be stated so that it is consistent with proof *and* examples?

---

1. On the solution of linear recurrence equations by M. Akra and L. Bazzi (1998)
2. They require $a\_i \in R^{\*+}$. Is this some notation I don't know, or a typo? I assume the intended meaning is $(0,\infty) \subseteq \mathbb{R}$.

# Answer
Take a look at Tom Leighton's notes, referenced from the Wikipedia article. His notes apparently have less typos then the original paper. The condition he demands of $g$ is having *polynomial growth*, which means that if you scale the argument by a constant, then the amount that the function scales is also bounded by a constant.
> 5 votes

# Answer
Nicest version of the Akra-Bazzi theorem I've seen is the one in Lehman, Leighton, Meyer "Mathematics for Computer Science", the discussion starts at page 1019. An (older) print version is available. No proof, though. Would need to slough through Leighton's note to verify that the lecture notes/book version is right (it has somewhat different conditions, that are much easier to check).
> 2 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: If L = {xy | |x| = |y|, x=y} is not Context Free, then what about L = {xy | |x| = |y|, x!=y}?
I know that, when x = y, then it's not Context Free. This is because, the first letter of y cannot be matched with first letter of x, which is at the bottom of the stack. But, a link of Show that { xy ∣ |x| = |y|, x ≠ y } is context-free claims that, when x!=y, then it's Context Free. But, how can the letters of x and y be matched on stack? Say x=abbb y=bbbb. How can we say first letters don't match?

Not necessarily restricting ourselves to determinism, will it be even possible by the Context-free Language class (Non-deterministic & Deterministic Pushdown Automata), as a whole, to generate L = {xy | |x| = |y|, x!=y}?

# Answer
> 2 votes
There is a big difference between $\\{ xy ∣ |x| = |y|, x = y \\}$ and $\\{ xy ∣ |x| = |y|, x \ne y \\}$. In the first one, we need *every* symbol in $x$ to be the same as the corresponding symbol in $y$. For inequality, it suffices that *at least one* symbol in *x* be different from the corresponding symbol in $y$. The two cases are not symmetrical.

Checking that the first symbol is the same is not difficult. That can easily be achieved with a context-free grammar; we just need a word consisting of some symbol followed by a word with that same symbol in the centre:

$$\begin{align}S&\to a A\mid b B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b \\ \end{align}$$

That doesn't help us with checking that all symbols in the first half are the same as the corresponding symbols in the second half. But it does give us a way to check if *some* symbol in the first half is the same as the corresponding symbol in the second half:

$$\begin{align}S&\to A A\mid B B\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\ \end{align}$$

And clearly it can easily be modified to check whether the corresponding symbols differ, giving the grammar in @Raphael's answer, linked in your question:

$$\begin{align}S&\to A B\mid B A\\A&\to a \mid a A a \mid a A b \mid b A a \mid b A b\\B&\to b \mid a B a \mid a B b \mid b B a \mid b B b\\ \end{align}$$

# Answer
> 1 votes
Have a good look to the answer you link to. It specifies the language that is generated using two numbers $k,\ell$. These numbers guarantee that the two parts are different without ever knowing where the middle of the string exctly was. I will try to explain.

We have to find (or better, guess) a position in $x$ such that the same position in $y$ carries another letter. Then we can write $x = x\_1 a x\_2$ and $y=y\_1 b y\_2$, where $|x\_1| = |y\_1|$ and $|x\_2| = |y\_2|$, and $a$ and $b$ are different symbols. You see that $a$ and $b$ are at the same position and $|x| = |y|$.

Note that $x\_1,x\_2$ and $y\_1,y\_2$ can be arbitrary strings, only their lengths matter, to get $a$ and $b$ at the same position in both halves. Let us denote an arbitrary string with $k$ symbols by $\langle k \rangle$, then the language of unequal halves can be written as all strings of the form $\langle k \rangle a \langle \ell \rangle \langle k \rangle b \langle \ell \rangle$ for $k,\ell \ge 0$. Written this way, the string cannot be generated by a CFG, nor accepted by a PDA. The final trick is to observe that we do *not* need to find the middle, just check the length of the string between $a$ and $b$.

So we look at the strings in another way, as $\langle k \rangle a \langle k \rangle \langle \ell \rangle b \langle \ell \rangle$, or $\langle k \rangle a \langle k+\ell \rangle b \langle \ell \rangle$. This still specifies the set of all strings with unequal halves, but is seen to be context-free (as in the original answer). It also shows how to accept by PDA: read arbitrary $k$ symbols, adding one to the pusdown each step, store the next letter and read the same number $k$ of symbols. Now the pushdown is empty, and we repeat with $\ell$ symbols.

---
Tags: formal-languages, automata, context-free, formal-grammars, computation-models
---


# Question
Title: Is the exponent bias $2^{n-1}-1$ or $2^{n-1}$
I'm a bit confused with the exponent bias. The sources I found online claim that it is either $2^{n-1}-1$ or $2^{n-1}$, $n$ is the number of bits used for the exponent. In my book when given examples on the bias of a 32bit system the bias is said to be $2^7$ which means the bias is $2^{n-1}$ while in an example on the bias of 64bit the bias is said to be $2^{11}-1$ which is $2^{n-1}-1$

So which one is it?

# Answer
Both encodings for the exponent are possible, and they are called Excess-$2^{n-1}$ and Excess-$2^{n-1}-1$ \- in particular, you might meet such number encodings as Excess-127, Excess-128, Excess-1023 and so on.

The IEEE-754 standard happened to choose the Excess-127 and the Excess-1023 encodings for exponents, so these encodings became more customary. Your book is not mistaken about the exponent bias, it just follows a way, different from this standard.

You can find additional information and nice graphs here.
> 1 votes

---
Tags: floating-point, numerical-analysis
---


title: F-measure with $\beta > 1$

text:
# Question
Title: F-measure with $\beta > 1$
Consider the F-measure $F\_{\beta}$. I know that with $\beta \< 1$ precision is given more importance, ending with $F\_{0} = precision$. With $\beta \> 1$ means recall gets the upper hand, with the other extreme at $F\_{inf} = recall$.

\begin{equation} F\_{\beta} = (1+ \beta^2) \cdot \frac{Precision \cdot Recall}{(\beta^2 \cdot Precision) + Recall} \end{equation}

I understand why for $\beta \< 1$ precision is given more importance, but I don't understand for $\beta \> 1$

# Answer
> 1 votes
Define $\gamma = 1/\beta$, $P=\textrm{precision}$, and $R=\textrm{recall}$.

Then $$F\_{\beta} = (1 + 1/\gamma^2)\cdot \frac{PR}{P/\gamma^2 + R} = (\gamma^2 + 1) \cdot \frac{PR}{\gamma^2R + P}$$, which is the $F\_\gamma$ measure with the roles of $P$ and $R$ switched.

So the same reasoning that shows precision is preferred for $\beta \< 1$ can be used to show that recall is preferred when $\gamma = 1/\beta \< 1$, i.e. when $\beta \> 1$.

---
Tags: algorithm-analysis, performance, information-retrieval
---


# Question
Title: When is cumulative type universes useful?
AFAIK, a hierarchy of type universe(`Type^0: Type^1: Type^2: ...`) was introduced to avoid inconsistency caused by `Type: Type`.

But some functional language(e.g. Idris) also allows subtyping of these type universes(`x: Type^n then also x: Type^n+1`). From my understanding, this is not mandatory to solve the inconsistency. So it leads me to guess there should be some advantages from this redundant subtyping rule.

When is cumulative type universes useful?

# Answer
> 7 votes
*Without* cummulative universes, if you have $A : \mathsf{Type}\_3$ then you do *not* have $A : \mathsf{Type}\_7$. Instead, we also have to introduce *lifting* functions $\iota\_{i,j} : \mathsf{Type}\_i \to \mathsf{Type}\_j$ for all $i \leq j$ and write $\iota\_{3,7}(A)$ to port $A$ from the third universe to the seventh one. But this is not all, we also want to know whether $\iota\_{3,5}(\iota\_{5,7}(A)) = \iota\_{3,7}(A)$, i.e., can we lift in several steps? So we need to add a bunch of equations $\iota\_{i,j}(\iota\_{j,k}(A)) = \iota\_{i,k}(A)$ for $i \leq j \leq k$. And this is not all, we also need things like $\iota\_{i,i}(A) = A$ and $\iota\_{i,j}(\Pi(x : A), B(x)) = \Pi (x : A) \iota\_{i,j}(B(x))$, and on and on. It's all very annoying.

*With* cummulative universes we can just drop all the lifting functions $\iota\_{i,j}$.

So why would anyone reject cummulative universes? There are several reasons. An important one is that with cummulative universe it is not true that every expression has at most one type, since a type is an element of many universes. This complicates various algorithms for inferring and checking types. Another reason is semantic: there are interesting models of type theory in which universes are *not* cummulative.

# Answer
> 3 votes
Suppose you have `X : Type0`. What universe can `X -> Type0` go in?

It can't go in `Type0`, because `Type0 : Type0` doesn't hold. Universes are presumably closed under function types, so we'd hope it can go in `Type1` because `Type0 : Type1`. But without the subtyping rule, we don't know that `X : Type1`, we only know that it is in `Type0`.

Now, you could instead say that `Type1` has function types for things in `Type0` and `Type1`. But you also need to do this for all the other ways to build up types, so you'd have a lot of extra rules, unless you came up a similarly generic rule to the subtyping rule. You'll only need more the higher you go. And you still might just need a way to include a type from a lower universe to a higher one (this happens in Agda, for instance, and is defined using a data type called `Lift`).

Having cumulativity of universes is generally the simplest way to handle this issue.

---
Tags: type-theory, functional-programming, dependent-types
---


# Question
Title: Optimization problem vs decision problem - reduction
Assume we have an optimization problem with function $f$ to maximize.

Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to the optimization problem: calculate the optimal solution and check if it is $\ge k$.

Now, I was wondering, is it always possible to do the reduction (in polynomial time) the other way around?

For an example consider MAX-SAT: to reduce the optimization problem to the decision problem we can do a binary search in the integer range from 0 to the number of clauses. At each stoppage $k$ we check, with the decision problem solver, if there is a solution with $\ge k$.

# Answer
There are a few conditions you would need to specify for this to even work, most importantly, that your function does have a maximum, otherwise you could try all k and end up going off into infinity. Likewise, you'd probably need to assume that f is only producing outputs on the integers or some other countable set.

If we're doing any sort of binary search, I think it is going to be exponential in the worst case unless we know an upper bound to start with. Assuming f returns numbers, finding the upper bound is going to be linear in terms of the maximum value. However, that means it's exponential in terms of the string-representation of the maximum value.

If we know an upper bound for the maximum of f, I can't see any reason why you couldn't do binary search to find it, but even then, it is polynomial in the upper bound, and could still be exponential in the length of the input, as opposed to the output.
> 4 votes

# Answer
An answer to this precise question is given by Bellare and Goldwasser, "The Complexity of Decision Versus Search", SIAM Journal on Computing, 23:1 (February 1994), DOI /10.1137/S0097539792228289; a more expository version of the above is Bellare's class note on this. The short answer is that if the decision problem is NP-complete, the search problem is "NP-complete" (really: can't do much better than an exhaustive search) also; however, if the search problem is harder, the decision problem can even be in P (can check there is a solution very easily) if a plausible conjecture in complexity theory is true.
> 1 votes

---
Tags: complexity-theory, optimization, reductions, decision-problem
---


title: Maximun distance that can be reached

text:
# Question
Title: Maximun distance that can be reached
A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, **not** necessarily unique, each described by a $vector$ of integer coordinates. The stone can make each move at most once , and the moves it makes may be arranged in any order.The goal is to reach a point as far (in the Euclidean distance) from the initial position as possible. How far can the stone be reached ? $($ Given that output is square of max distance $)$

Example : consider $ n$ $=$ $4$ and vectrs are

$\[$2,-2 $\]$ ,\[-2,-2\],\[0,2\],\[3,1\],\[-3,1\]

Ans is $26$ Optimal way is to use vectors \[0,2\], \[3,1\], and \[2,−2\].or also \[0,2\], \[−3,1\], and \[−2,−2\].

link for vector clarity is https://ibb.co/mJByc99

# Answer
Addition of vectors is commutative, so the order of moves is irrelevant. For example:

$(0,2) + (3,1) + (2,-2) = (0,2) + (2,-2) + (3,1) = (3,1) + (0,2) + (2,-2) = (5,1)$

So a simple brute force method is to calculate the distance traveled for all subsets of the set of $n$ possible moves. There are $2^n$ such subsets, but you don't need to consider the empty set. So the size of your search space is actually $2^n-1$.
> 1 votes

---
Tags: computational-geometry, dynamic-programming
---


title: Sorting almost sorted array

text:
# Question
Title: Sorting almost sorted array
Encountered this question but I couldn't solve with the complexity they solved it:

Suppose I have an array that the first and last $\sqrt\[\leftroot{-2}\uproot{2}\]{n} $ elements has $\frac{n}{5}$ inverted pairs, and the middle $n - 2\sqrt\[\leftroot{-2}\uproot{2}\]{n}$ elemnts are sorted. What is the complexity of sorting the unsorted array?

They claim in the answer that sorting array with $I$ inversions is $O(n\log{\frac{n}{I}})$.Why?

# Answer
> 3 votes
If you have an array with a sequential range that covers all but k elements, and you know the range, then you sort the k elements in O (k log k), then merge two ranges that you know to be sorted in O (n). That sorts the whole array in O(n) as long as k is O (n / log n).

In your case k = $O (n^{1/2})$ so clearly you can sort the array in O (n).

And you don't need to know the sorted range, because for large n we have n/2 inside the sorted range, so you can just count the elements in ascending / descending order from n/2 upwards / downwards.

---
Tags: complexity-theory, data-structures
---