# Question
Title: Why are palindrome and not-palindrome both context-free?
Both palindrome and its complement are context-free. This is very interesting. Both are non-deterministic context-free, which in general are not closed under complement. What is it about these two NCFLs that makes complement work?

# Answer
You make the mistake of assuming that

$\qquad \lnot \forall\\, x \in X. P(x) \quad \equiv \quad \forall\\, x \in X. \lnot P(x)$

while in truth

$\qquad \lnot \forall\\, x \in X. P(x) \quad \equiv \quad \exists\\, x \in X. \lnot P(x)$.

In your concrete case, "CFL is not closed against complement" means there are counterexample. You'll recall that REG ⊆ CFL and REG is closed against complement, so there are clearly plenty of complement-pairs in CFL.

As for the concrete two languages, the palindromes are generated by the most archetypical context-free grammar,

$\qquad S \to aSa \mid bSb \mid \dots \mid a \mid b \mid \dots \varepsilon$.

The complement is a nice exercise and can be found elsewhere on the site.
> 6 votes

# Answer
when we say that context free language is not closed under complement it means that that there exist some contest free language that its complement is not context free language not for all languages. for example $L = \\{w\in\\{a,b,c\\}^+ : n\_a(w) = n\_b(w) = n\_c(w)\\}$ is not context free language while its complement is context free language. you can see other example here.

but when we say context free language is close under union it means for all $L\_1$ and $L\_2$ that are context free language, $L\_1 \cup L\_2$ is context free language.
> 0 votes

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


# Question
Title: Closure properties of the class of inherently ambiguous CFLs
is set of inherently ambiguous context free languages close under operations such that union, intersection, kleene star, concatenation, reverse, complementation and etc. how many of theme are answered?

# Answer
### Reversal

The class of inherently ambiguous context-free languages *is* closed under reversal (exercise).

### Intersection

The class of inherently ambiguous context-free languages is *not* closed under intersection. Indeed, take some inherently ambiguous context-free language $L$. Now take $L'$ to be a copy of $L$ which uses a different alphabet. Then $L \cap L' = \emptyset$.

### Complementation

The class of inherently ambiguous context-free languages is *not* closed under complementation. Indeed, consider the Goldstine language $$ G = \\{ a^{n\_1} b \cdots a^{n\_p} b : p \geq 1 \text{ and } n\_i \neq i \text{ for some } i \\}. $$ This language is context-free and inherently ambiguous (see slides of Cyril Nicaud). Also, $$ \overline{G} \cap \Sigma^\* b = \\{ aba^2\cdots a^p b : p \geq 1 \\}, $$ which isn't even context-free.

### Union

The class of inherently ambiguous context-free languages is *not* closed under union. Indeed, the following variant of the Goldstine language is probably also context-free and inherently ambiguous: $$ G' = \\{ a^{n\_1} b \cdots a^{n\_p} b : p \geq 1 \text{ and } n\_i \neq i+1 \text{ for some } i \\}. $$ However, $G \cup G' = (a^\*b)^+$.

### Iteration (Kleene star)

The class of inherently ambiguous context-free languages is *not* closed under Kleene star. Indeed, consider the following language: $$ \Omega\_3 = \\{ u \in \\{a,b,c\\}^\* : |u|\_a \neq |u|\_b \text{ or } |u|\_a \neq |u|\_c \\}. $$ Here $|u|\_a$ is the number of $a$s in $u$. This language is context-free and inherently ambiguous (see the slides of Cyril Nicaud). However, $\Omega\_3^\* = \\{a,b,c\\}^\*$.

### Concatenation

The class of inherently ambiguous context-free languages is *not* closed under concatenation. Indeed, the following variants of $\Omega\_3$ are probably also context-free and inherently ambiguous: $$ \begin{align\*} \Omega'\_3 &= \\{ u \in \\{a,b,c\\}^\* : |u|\_a \neq |u|\_b \text{ or } |u|\_a \neq |u|\_c \text{ or } u = \epsilon \\}, \\ \Omega''\_3 &= \\{ u \in \\{a,b,c\\}^\* : |u|\_a \neq |u|\_b+1 \text{ or } |u|\_a \neq |u|\_c+1 \text{ or } u = \epsilon \\}. \end{align\*} $$ However, $\Omega'\_3 \Omega''\_3 = \\{a,b,c\\}^\*$.
> 6 votes

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


# Question
Title: Meaning of , and ; in relation to defining context
I have seen use of , and somewhere use of ; when defining context :

$$\dfrac{\phi \ , \ \Gamma \ \vdash } {} $$

somewhere else i have seen :

$$\dfrac{\phi \ ; \ \Gamma \ \vdash } {} $$

What is the difference between both. I have read something like extension of context. Then what second one means.

# Answer
> 5 votes
You'd have to check whatever you're reading, but the way I've most commonly seen it used is to separate *different* contexts. The rules will then behave differently if a variable or formula is in one context versus another. mobileink mentioned substructural logics which are often formulated with a context for linear variables and a different context for non-linear variables.

However, ; could simply be being used to separate other things so you don't confuse it with context extension. Or it could just be part of a term. Or it could be some operator on contexts distinct from context extension. Or it could just be this author decided to use ; instead of , for context extension. Again, what it means is whatever it is defined to mean, which may be nothing on its own. For example, used to separate different contexts, it's just part of the syntax of a judgement, e.g. the judgement may be 3-ary relation $(-);(-)\vdash (-)$ in which case it makes no more sense to ask what ; means than it would to ask what $.$ means in $\forall x.P(x)$. See my answer to a similar question for more elaboration on this.

# Answer
> 2 votes
They can express different ideas of what "together with" means. See Substructural Logics

For example, in many logics, there is a structural rule that says you can go from $A;B\vdash C$ to $B;A\vdash C$ (often call the rule of Exchange). Another rule says you can go from $A;A\vdash B$ to $A\vdash B$ (rule of Contraction). Etc. They're called structural rather than logical rules because they set the meaning of (non-logical) punctuation marks like ";" in these examples. Real-world analogs: suppose A and B represent events in the first example, and $A;B$ means "event A, then event B", and the rule of Exchange does not hold. Note that we could add a second mark $A,B$ to express that both events occurred in either order.

In the second example, suppose A means "one dollar" and B means "cup of coffee", so $A;A\vdash B$ means that two dollars will get you a cup of coffee, and the rule of Contraction does not hold. So in this case the informal notion of a resource that can be consumed can be expressed as a purely formal Structural Rule.

By defining different punctuation marks and selecting various structural rules you get lots of different ways of interpreting "A together with B"; logics that can be used to model lots of different things.

---
Tags: type-theory, notation
---


# Question
Title: Skolem constant in existential instantiation for first order logic
For any sentence $\alpha$, variable $v$, and constant symbol $k$ that does NOT appear elsewhere in KB: $$\dfrac{\exists \nu. \alpha}{\mathsf{subst}(\\{ \nu / k \\},\alpha)}.$$ E.g., $∃x. \mathrm{Crown}(x) \wedge \mathrm{OnHead}(x, \mathrm{John})$ yields

$\mathrm{Crown}(C\_1) \wedge \mathrm{OnHead}(C\_1, \mathrm{John})$

Provided $C\_1$ is a new constant symbol (aka Skolem constant)

Can someone clarify the Skolem constant concept?

# Answer
> 3 votes
Perhaps it will help to discuss this in a broader context, so let me explain this concept with regard to the resolution principle, which is used to check if some formula is unsatisfiable. Resolution for propositional logic's formulae is rather straightforward and is based on the Conjunctive Normal Form.

We want to apply resolution to first-order formulae, i.e. sort of reduce FOL to propositional logic. One way to do that is to convert the original formula via Skolemization into a formula of the form $$\forall x\_1x\_2...x\_nM,$$ where $M$ (called 'matrix') is a formula without quantifiers and in CNF. To do this conversion we must get rid of existential quantifiers. The rule you provided does that in the special case where the current existential quantifier is not in scope of any universal quantifiers.

The intuition here is if it is known there exists some $\nu$ for which $\alpha$ holds, then why don't we "pretend" we know that $\nu = k$, where $k$ is some fresh constant. It needs to be 'fresh' in order not to introduce any dependencies between unrelated things. And the reason we are allowed to "pretend" we know $\nu$ is that there is a theorem which claims that Skolemization preserves unsatisfiability.

Note: recall that we only want to check if a formula is satisfiable/unsatisfiable, so the skolemized formula is *not* necessarily equivalent to the original one.

# Answer
> 1 votes
Another, more informal way to look at it is that by introducing a skolem constant you extend the language of your logic. You start by defining a language with a fixed store of constant symbols, each bound to a semantic value. Then you quantify existentially using variable v in an open sentence and find some (unknown, indeterminate) semantic value that satisfies the form in which v appears, turning it into a proposition. So you extend the language by adding a fresh constant and binding it to that value. Now you can write a proposition using that symbol.

---
Tags: artificial-intelligence, first-order-logic
---


# Question
Title: How to write the turing machine processing operations?
I have this Turing machine example given in my book:

For the language $0^n1^n$. I understand how it works because it's very similar to a Finite State Machine.

But what I want to know is the following:

What is the $|-$ symbol is for what are the states $q\_0$, $q\_1$ doing in middle of everything. Unfortunately my textbook doesn't explain any of it.

# Answer
> 1 votes
The state marks the position of the head (as well as the current state): for example, in $q\_00011$, the head is to the left of $0011$, and in $xq\_1011$, it is to the left of $011$.

The notation $\sigma \vdash \tau$ means that the configuration $\sigma$ leads, after one step of the Turing machine, to the configuration $\tau$.

As David Richerby mentions in his comment, all of this is explained in your textbook at some point.

---
Tags: turing-machines, finite-automata
---


# Question
Title: How to design a top-1 select algorithm to maximize a variable and minimize other variable?
I want to implement an algorithm thats select the best group, which maximize the variable A and minimize the variable B.

For instance, I have the following groups:

G1 - A = 10 B = 2

G2 - A = 10 B = 3

G3 - A = 12 B = 1

G4 - A = 10 B = 4

and so on...

One solution could be the sorting the groups by A and resolve ties by selecting the B, but this is not the case here.. it is a tradeoff. I need to select a group with a good tradeoff. How can I do this tradeoff? any suggestion?

# Answer
> 1 votes
This question is not answerable. Only you can tell us what counts as a good tradeoff, for you. You need to pick a single objective function that combines A and B into a single quantity. We can't tell you how to do that, because that will depend on what makes sense for your particular application domain.

For instance, maybe it's best to choose the item with the highest value of $A/B$. Or maybe it's best to choose the item with highest value of $A-B$. Or maybe its' best to choose the item with highest value of $100A-B$, or $A-100B$, or $A + 1/B$, or $100A + 1/B$. We can't tell you. You will need to analyze your application to determine what the right objective function is. Take a look at your specific application and understand what is a measure of benefit or cost that is meaningful in your application domain, and then figure out how that depends on $A$ and $B$ ... and use that as the objective function to maximize.

---
Tags: sorting, selection-problem
---


# Question
Title: What data structure might this game use?
This question is not about game development or about actual implementation details.

I was playing Little Alchemy yesterday. (**Warning: Productivity hazard.**) You start with the four classical Elements of earth, air, fire, and water. You can combine them to produce other "Elements" (wood, humanity, time, cities, etc.), combine *those* to produce even more, etc. All of the relationships are predefined, so the game is less about crafting and more about lateral thinking.

I got curious about how exactly the game *could* store and query the various combinations optimally. Whether the developer actually does so under the hood is a different story, and not what I'm asking about.

Consider the following game mechanics:

* There is no limit to the number of Elements, but it's decided in advance by the game's designer and thus does not change at runtime.
* All Elements are made by combining *exactly* two other Elements, possibly of the same kind (Fire \+ Water = Steam).
* Even the four base Elements can be created (Fire \+ Ice = Water).
* Some Elements can be created through more than one combination. (Fire \+ Water = Energy \+ Water = Steam)
* Some combinations produce more than one Element (Human \+ Cow = Minotaur and Milk)
* Some Elements are "final" and cannot be combined to produce any other, though they may in future updates. (Jedi \+ Swamp = Yoda)
* Order of combination does not matter (e.g. Water + Fire = Fire + Water).

The game presumably needs fast lookup and low memory usage. More specifically:

* Given exactly two elements, look up the result of their combination, if any. This should be fast.
* There is no insertion or removal except by the game's designer in advance. This can safely be slow.

**Given these, what data structure might Little Alchemy use to store the various combinations that can be used to produce elements?**

---

# Initial Thoughts

Back-of-the-envelope guess? A big ass-hash-table that maps `(Element, Element)` pairs to `Element` lists. For $n$ Elements, this results in amortized $O(1)$ lookup and $O(n^2)$ memory, because theoretically any combination can produce every other Element at once. *Can we do better?*

# Answer
A hashtable *is* asymptotically optimal. Your analysis led you astray.

The relevant parameter is the number of rules that exist (where each rule specifies a combination of two elements and what new elements that combination produces). Call this $m$.

It's easy to see that any data structure will need at least $\Omega(m)$ space. You can't do better than that, because you're going to store something about each rule.

Moreover, a hashtable does achieve $O(m)$ space, so it is asymptotically optimal. Also, a hashtable achieves $O(1)$ expected lookup time, so it is asymptotically optimal in that respect as well.

None of this means that it will be optimal in practice, because it ignores constant factors. But speaking pragmatically: I expect a hashtable will be fine. The size of the table will be small enough that it probably takes up only a tiny fraction of the overall memory usage of the program, so most likely there's little point in trying to optimize it to the max.
> 2 votes

# Answer
Sounds like you'd want a 1:1 mapping of elements to numbers, starting at 1 (using an enumerated type or something similar, depending on the implementing language), then use a sparse matrix to store the combinations. It'd be a symmetric sparse matrix, so that might allow further compression, depending on how exactly it's implemented.
> 0 votes

---
Tags: data-structures, optimization, runtime-analysis, computer-games
---


# Question
Title: Search Heuristics Where the Search Space Has No Gradient
If I'm not mistaken, search heuristics rely on problems where the best answer is very close to pretty-good answers. For example, the traveling salesman problem. If there is a route which is the optimal except for a small anomaly somewhere, where the route isn't *quite* optimal, the algorithms still says that's "pretty good" and continues searching that space until it finds the optimal. I'm going to call this "gradient" because there isn't a sharp difference between optimal and something where everything is optimal except for a small part.

What happens if there is no "gradient"? For example, let's say I wanted to develop some electronic circuitry using a search heuristic. This probably isn't done much, or at all, but bear with me. The optimal circuit would be one which, say, does addition. But, if there is one small difference, like an AND logic gate instead of an OR gate, it doesn't perform at all and produces a terrible result. Now, in traditional search heuristics, it would probably drop this and say "this isn't even close to optimal". It has no way of telling whether something is close to optimal or far away to optimal, because there is really only one circuit that produces good results, and everything else fails miserably.

So what should I do in these situations? By the way, the circuit thing isn't my problem; just a way to demonstrate my issue.

**Phrased Differently** What does a search heuristic do when it has no way of "grading" how good a given state is, and only the optimal state produces good results? Everything else, no matter how close to the optimal, produces terrible results.

**BONUS:** What other group of algorithms might perform well in these situations?

# Answer
Search heuristics will be useless on those kinds of problems. It will effectively degenerate to brute-force search: trying all possibilities in hopes that one of them works. That's very unlikely to find you the solution, except in the smallest possible problems, as its running time is exponential.

What else can you do instead? You'll need to consider other kind of approach: e.g., a SAT solver or ILP solver, an approximation algorithm or any of the other standard methods of dealing with NP-hardness.
> 2 votes

---
Tags: algorithms, search-algorithms, heuristics
---


# Question
Title: Decidability of equivalence problem with limit
I already know, that the language $$L\_0 = \\{m \mid \text{the Turing machine $m$ does not stop on an empty tape}\\}$$ is not decidable. If I want to know, if $$EQ = \\{\langle m, n \rangle \mid L(m) = L(n)\\}$$ is decidable I can reduce $L\_0$ to $EQ$. Because $(L\_1 \setminus L\_2) \cup (L\_2 \setminus L\_1) = \emptyset$ iff $L\_1 = L\_2$, $EQ$ is also not decidable.

But what happens if a limit is added? For example the language $$EQ\_{\lim} = \\{\langle m, n \rangle \mid \exists x\_0 \in \mathbb{N}\colon \forall x \> x\_0\colon m(x) = n(x)\\}.$$

Is it (semi-)decidable? I also try to reduce from the halting problem (more specifically the inverse of the halting problem to proof also semi-decidability), but without success.

# Answer
You can still reduce $L\_0$ to $EQ\_{\lim}$. Given a Turing machine $m$, construct a Turing machine $m'$ which deletes its input and then transfers control to $m$, and let $n'$ denote a (fixed) Turing machine which halts on no input. Then $m \in L\_0$ iff $\langle m',n' \rangle \in EQ\_{\lim}$.
> 1 votes

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


# Question
Title: How do you rank the strings represented by a regular expression?
This question is about the use of 'ranking' of regular languages in applications such as format preserving encryption.

I understand format preserving encryption but I don't understand how regular expressions can be used to get an integer that is the input of an encryption algorithm.

Referring to this video https://youtu.be/MT5ketZ-jLw?t=24m44s at time stamp 24:44

According to the process described - In order to encrypt a string to a ciphertext of some agreed upon format, you need to rank all the possible strings it can be - then using your FPE function encrypt the integer that represents the input plain text to an integer in the same set - unrank the output integer to a ciphertext.

I don't understand what is being ranked? Are they actually obtaining all possible string representations of the regular expression and ranking those? Or are they ranking something else? Where does the DFA come to play - because I can see a brute force way you can do this without bothering with the DFA - or even regular expressions to define the format.

EDIT:

I have already most of the paper that use ranking in regular languages for encryption such as these ones

* Mihir Bellare, Thomas Ristenpart, Phillip Rogaway, and Till Stegers Selected Areas in Cryptography, pages 295-312. Springer-Verlag, 2009 (online, see sec 5 p 10 "FPE for arbitrary RLs")
* Daniel Luchaup, Kevin P. Dyer, Somesh Jha, Thomas Ristenpart and Thomas Shrimpton To appear in the proceedings of USENIX Security 2014

Anyway I'm just looking for a 'laymans' explanation of how this works as I cannot find any working examples online. This would be useful to understand the overall procedure. All examples I have found regarding regular expressions involve creating the DFA, and most of them end there. What happens next?

The closest I could find was this post which I think is asking the same thing

https://cstheory.stackexchange.com/questions/18589/algorithm-for-ranking-members-of-a-regular-language

# Answer
> 5 votes
Suppose you want to encode an element of $\binom{\[n\]}{k}$, that is, a subset of $\\{1,\ldots,n\\}$ of size $k$. There are $\binom{n}{k}$ such subsets. FPE functions know how to handle encoding and decoding of integers in the range $\\{1,\ldots,M\\}$, for an $M$ of your choice. To use such an FPE function in your case you will have to translate an element of $\binom{\[n\]}{k}$ to an integer in $\\{1,\ldots,M\\}$ for $M = \binom{n}{k}$ (*ranking*) and back (*unranking*), *efficiently*.

How do you efficiently rank and unrank elements of a domain like $\binom{\[n\]}{k}$? For which domains is it possible? The video describes one scenario where this is possible, and one general algorithm for handling this scenario. If your scenario is different then you might still be able to rank and unrank efficiently, but you will have to use a different approach.

The scenario described by the video (which I haven't watched) is probably that of languages accepted by a DFA with a small number of states. Such a language can be ranked and unranked efficiently, and the algorithms use the DFA which accepts the language. This is how the DFA comes in – it is used by the ranking and unranking algorithms. Hopefully these algorithms are described in the video, but otherwise you can ask another question here.

---
Tags: regular-expressions, cryptography
---


title: Property of cyclic codes

text:
# Question
Title: Property of cyclic codes
Let $C$ be a $\[n,k\]$ cyclic code over $\mathbb{F}\_q$ with $(n,q)=1$.

I want to show that $(1, \dots, 1)$ is a codeword iff $X-1 \nmid g(X)$.

$g(x)$ is the generator polynomial.

We suppose that $(1, \dots, 1)$ is a codeword.

We consider the following correspondence

$$\pi: \mathbb{F}\_q^n \to \mathbb{F}\_q\[x\] / x^n-1, (a\_0, a\_1, \dots, a\_{n-1}) \mapsto a\_0+ a\_1 x+ \dots+ a\_{n-1} x^{n-1}$$

Then $(1, \dots, 1) \mapsto 1+ x+ \dots+ x^{n-1}$.

We want to show that $X-1 \nmid g(X)$.

Then $g(X)=b(X)(X-1)$ for some polynomial $b(X)$. How can we get a contradiction?

How can we show that if $X-1 \nmid g(X)$ then $(1, \dots, 1)$ is a codeword?

# Answer
> 2 votes
The word $(1,\ldots,1)$ is in your code iff there exists a polynomial $p(x)$ such that $$ \frac{x^n-1}{x-1} = p(x) g(x). $$ Since the code is cyclic, $g(x)$ divides $x^n-1$, and so $(1,\ldots,1)$ is in your code iff there exists a polynomial $p(x)$ such that $$ \frac{x^n-1}{g(x)} = p(x)(x-1). $$ In other words, $(1,\ldots,1)$ is in your code iff $$ x-1 \mid \frac{x^n-1}{g(x)}. $$ I'll let you complete the proof, using the fact that $x-1$ divides $x^n-1$ but not $\frac{x^n-1}{x-1}$.

---
Tags: coding-theory
---


title: Does MiniSAT need exponential time?

text:
# Question
Title: Does MiniSAT need exponential time?
I'm asking for a sequence of instances for SAT, one instance for each length, such that the sequence takes exponential time with MiniSAT.

# Answer
When pure CDCL solvers (such as MiniSAT, I believe) are run on unsatisfiable instances, their transcript can be converted to a Resolution refutation of the instance. In particular, the running time of the solver is lower bounded by the length of the smallest Resolution refutation of the instance. There are instances which are known to take exponential length to refute in Resolution, for example the Pigeonhole Principle on $n+1$ pigeons and $n$ holes. Such instances will take exponential time to refute on any pure CDCL solver.
> 2 votes

---
Tags: satisfiability, sat-solvers
---


# Question
Title: How to generate a degree sequence of a degree distribution
How to generate a degree sequence of a degree distribution that follows the power-law in which I know $N=10^2$ and $\gamma=2.5$?

The degree distribution of power-law is $p\_k \sim k^{-\gamma}$.

I want to generate a power-law network using the **configuration model**, but to do that I need to know the degree sequence $seq={k\_1, k\_2, ..., k\_N}$.

Thanks

# Answer
> 1 votes
As you mention, the degree distribution follows a power law if the number of nodes of degree $k$ is roughly $N \times C^{-1} k^{-\gamma}$, where $C = \sum\_{k = 1}^\infty k^{-\gamma} = \zeta(\gamma)$ (in your case, $C \approx 1.34$). Plugging in your numbers, we want roughly

1. 75 vertices of degree 1.
2. 13 vertices of degree 2.
3. 5 vertices of degree 3.
4. 2 vertices of degree 4.
5. 1 vertices of degree 5.
6. 1 vertices of degree 6.
7. 1 vertex of degree 7.

This gives a total of 98 vertices. You can make it exactly 100 vertices in many ways — I'll let you think of one. Don't forget that the sum of degrees should be even.

The (potential) problem is that *not every sequence is the degree sequence of a graph*. Sequences which are realized by some graphs are known as graphic sequences, and are determined by the Erdős–Gallai criterion. If the resulting sequence doesn't satisfy this criterion, we're in trouble. However, I don't expect it to happen in your case. Indeed, my suggestion above (with 98 vertices) is graphical.

---
Tags: graphs
---


title: Is the given grammar LALR

text:
# Question
Title: Is the given grammar LALR
We are given the following grammar.

*S--\>AS/b*

*A--\>SA/a*

We have to tell if its LALR or not.

As we all know that LALR is only minimization of CLR, So first I constructed the CLR parsing table using canonical collection of LR(1) items.

In the table there was no conflict.But There is no minimization possible.Does that mean that the given grammar is LALR as there are no conflicts.

# Answer
> 1 votes
The grammar is always LALR, if no merging is possible and in this case LALR = CLR, but when merging is possible, we have to see that if conflicts come up and if they do come up, grammar is not LALR and if they don't,the grammar is LALR.

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


title: Correcting two-bit error using a CRC

text:
# Question
Title: Correcting two-bit error using a CRC
What algorithm can be used to correct a two-bit error in a message protected by a 32-bit CRC, assuming the CRC polynomial allows that? I'm seeking something for 480-bit payload, able to detect uncorrectable errors, fast in the worst case, and compact.

Because I have hardware support for that, I'm most interested in the CRC-32 IEEE 802.3 primitive polynomial (allowing two-bit error correction for payloads up to 2974 bits), $$x^{32}+x^{26}+x^{23}+x^{22}+x^{16}+x^{12}+x^{11}+x^{10}+x^8+x^7+x^5+x^4+x^2+x+1$$ but the question is of theoretical interest for others, such as the CRC-32K polynomial proposed by Koopman (allowing two-bit error correction for payloads up to 16360 bits) $$(x+1)(x^3+x^2+1)(x^{28}+x^{22}+x^{20}+x^{19}+x^{16}+x^{14}+x^{12}+x^9+x^8+x^6+1)$$

---

Assume payload data of $b$ bits (assimilated to the coefficients of a binary polynomial $B(x)$ of degree less than $b$), to which is appended a CRC computed with binary polynomial $P(x)$ of degree $c=32$, as $C(x)=(B(x)\\;x^c)\bmod P(x)$. It is then stored in memory $b+c$ bits of $B(x)\\;x^c+C(x)$. On reading is it computed the syndrome $S(x)=(B'(x)\\;x^c+C'(x))\bmod P(x)$. Assuming there has been at most two bits in error, and $b$ is small enough:

* If $S(x)=0$, then there has been no error.
* Otherwise, if there exists $i$ with $0\le i\<b+c$ such that $S(x)=x^i\bmod P(x)$, then there has been a single error, and $i$ tells where, allowing correction.
* Otherwise, there has been two errors and there exists $i$ and $j$ with $0\le i\<j\<b+c$ such that $S(x)=(x^j+x^i)\bmod P(x)$; again finding $(i,j)$ allows correction.

The case of a single bit in error is relatively easy; that's a discrete logarithm problem, with an easy size versus speed compromise: we can have a precomputed table allowing solving in a single lookup for $i$ multiple of $k$, and use that $k$ times. But I'm stuck with the case of two bits where I have nothing much better than trying all $j$ and doing as for a single bit in error.

# Answer
One approach: Use a meet-in-the-middle algorithm. Build a precomputed table that stores $T\_i = x^i \bmod P(x)$ for all $i$ up to the maximum message length. Now, given $S$, you are looking for $i,j$ such that $S = T\_i + T\_j$. This can be found by enumerating all $i$, and for each $i$, computing $S-T\_i$ and checking whether it is present in the precomputed table.

The running time is proportional to the maximum length of the message. I'd imagine that in a real deployment, two-bit errors will be rare enough that this running time is affordable. (If two-bit errors are common, then three-bit errors will have non-negligible probability, which is a problem of its own.)

If you want to reduce space complexity, instead of storing the entire precomputed table and looking up $S-T\_i$ in the table, compute the discrete log of $S-T\_i$ for each $i$ using whatever method you prefer (such as the one you listed in your question).

I don't know if there are smarter methods that exploit the structure of $\mathbb{F}\_2^{32}$ in a more intelligent manner.
> 4 votes

---
Tags: error-correcting-codes, crc
---


# Question
Title: How does equality works for qubit-vectors?
A bitvector of length `N` has `2^N` different values. How many different values has a quantum bit vector of length `N`? Is it possible to test two quantum bit vectors for equality?

# Answer
The state of an $n$-qubit system is defined by $2^n$ complex numbers. Basically the numbers are weightings for each of the classical $n$-bit states, similar to a probability... but square-rooted.

Technically, two quantum states are equal only if all of those weights are equal. But, when it comes to the practical aspects of quantum computing, it's better to focus on continuous concepts like *distance* rather than discrete concepts like *equality* because we only get very indirect access to the weights.

For example, quantum mechanics places pretty strict limits on how well you can compare two states. If the vectors defined by the amplitudes of state $a$ and state $b$ are an angle $\theta$ apart, then the chance of *any* QM process correctly distinguishing between them is upper-bounded by $\frac{1}{2} + \frac{1}{2}|\sin \theta|$ or equivalently $\frac{1}{2} + \frac{1}{2}\sqrt{1 - |\langle a | b\rangle|^2}$ (look up 'Trace Distance'). Distinguishing is strictly easier than equating, and we're already failing probabilistically at distinguishing! That's why people focus more on the distances.
> 2 votes

---
Tags: quantum-computing
---


# Question
Title: How can an extended linearizable history G be equivalent to sequential history S?
I am undertaking a module in Concurrent Programming where some of the new content this year covers linearizability, the Java Memory Model, and sequential consistency. Our class slides are companion slides to **The Art Of Multiprocessor Programming.**

I have been doing OK with linearizability but have become confused at this point below:

I understand that removing pending invocations gives a complete subhistory, however I cannot understand from this example how a subset G can be equivalent to set S which is larger than it - how is G obtained from S here?

As far as I am aware there is not enough information to determine if there are pending invocations from the diagram on the right and I am not sure why a --\> b is removed in the subset that is G - at first I thought it's because they are overlapping but A and B both have linearization points for viewing them 'as sequential objects'.

I may be over looking something simple and have just misunderstood the slides.

# Answer
> 3 votes
The idea of linearizability is that the parallel events behave as if each of them happened at a single point in time, during the duration of the actual execution of the event. Given a sequence of events, if the end point of event $A$ precedes the starting point of event $B$ then in *any* linearization, the time point of $A$ must precede the time point of $B$. These are the constraints $\rightarrow\_G$, which we can think of as a partial order. The events are linearizable if the constraints are extendable to a *linear* order $\rightarrow\_S$ such that the *semantics* match — the outcome of the events is the same as if they were applied in the order underlying $\rightarrow\_S$. Perhaps this is what was meant by *equivalence*, though as you mention, it is clearly applied to the wrong objects. What is equivalent here is the actual turn of events and the turn of events given the order $\rightarrow\_S$.

# Answer
> 1 votes
I'm a bit late with this question, but this would be my thoughts on the slides -

There are a lot of words within the first slide which have a different meaning in this context in comparison to other scenarios.

For instance the definitions of words are :

* **Legal** \- A history $H$ is legal, if for each object $x$ the projection $H|x$ meets the sequential specification
* **Sequential History** \- A sequential history $H$ follows the format of an initial request, such as $A\ q:end(3)$, followed by zero or more responses and invocations - a trailing innovation is valid in this scenario.

Note, invocations and responses of different threads may not be interleaved for a sequential history - for instance the below history is *not* valid, as the Thread's invocations and responses are interleaved.

$ A\ q.enq(3) \\ B\ q.enq(4) \\ A\ q:void \\ B\ q:void $
* **Equivalent** \- Two histories $H$ and $G$ are equivalent if their per thread projections are equal.

With this in mind

```
A history $H$ is linerizable if, it can be extended to $G$ by
    - Appending zero or more responses to pending invocations
    - Discarding other pending invocations

```

And with our definitions in mind, we can say - loosely speaking

```
There must exist a legal, perhaps arbitrary, sequential history S,
which follows the defined ordering within our complete history G

```

For instance in your slide, the following orderings (or precedences) are defined

$ \rightarrow\_{G} = \\{a \rightarrow c, b\rightarrow c \\} $

Note that, as the ordering between $a$ and $b$ is undefined, we must check both interleavings.

Therefore given these orderings, it means to prove a history to be linearizable, we simply need to find **any** legal, sequential history S, which is equivalent to G and contains our defined ordering relations.

One such legal sequential to test against may be the following, ie $a \rightarrow b$

$ \rightarrow\_{S} = \\{a \rightarrow b, a\rightarrow c, b \rightarrow c \\} $

And another possible legal sequential history may be the following, ie $b \rightarrow a$

$ \rightarrow\_{S} = \\{b \rightarrow a, b\rightarrow c, a \rightarrow c \\} $

So, in general it should be 'easy' to prove that a History linearizable if their method innovations do not overlap. However in this scenario both $a$ and $b$ do, so we must test out both possibilities. If either yield to be true, then our history is linearizable.

# Answer
> 0 votes
I think the confusion comes from mixing up relations and histories.

G and S are histories. G equivalent to S means that the events happen on each process in the same order in G as in S. (Note though the ordering of events on different processes may differ between equivalent histories.)

--\>G is the relation of events in G, and similarly --\>S is the relation in S. --\>G is a partial ordering, whereas --\>S is a total ordering, since S is sequential. --\>S is an extension of --\>G by adding ordering between parallel events in G.

Hope it helps.

---
Tags: concurrency
---


# Question
Title: Trying to understand this Dynamic Programming solution
The problem is as follows.

Minimize the sum of absolute differences between a matching of $n$ values from two sets, $A=\\{a\_1,a\_2,\cdots, a\_n\\}$ and the set $B=\\{b\_1, b\_2,\cdots, b\_m \\}$, with $n\leq m$.

So, we can use two list of indexes $\ I$, $J$, such that $I\subseteq \[n\]$, $J\subset \[m\]$, and $|I|=|J|=n$. The notation is $\[m\] = \\{1,2,3,\cdots, m\\}$.

Therefore, our goal reduces to:

$$ \min\_{k=1,2,\cdots, n} \\{|a\_{i\_k} - b\_{j\_k}|\ : i\_k\in \[n\],\ j\_k\in J\\}.$$

I found the problem above in this question (in other words) and trying to understand how the answer provided there, it attempts to solve the problem with dynamic programming.

This is what I understand:

* I believe we are building two indexes and are pairing them.
* We first sort boys by height
* Somehow we then construct a match, but it's not greedy, is it? it utilizes calculating the sum of the absolute difference in height. How was the pairing constructed?

This paragraph is key and I would love to understand it but I don't get it:

```
you can use dynamic programming to find the optimal matching by building up
optimal matchings that have the first j boys in sorted height order all
paired up somehow among the first k girls in sorted height order (where
j≤k), and using the optimal matchings for the values (j,k−1) and (j−1,k−1)to
decide the optimal matching for the values (j,k), based on whether you pair
up boy j with girl k or not.

```

So, the question is how the dynamic programing method is working here based on the answer given and pseudo code of the solution it would be helpful.

# Answer
We are going to build up the matching with a top-bottom approach. Before proceed your intuition is correct. We need two indexes for our solution, that it would be a recursive function $f$ based on a index $i\in \[n\]$ and index $j\in\[m\]$.

This is the definition for $f$. $$f(i,j):= \text{The optimal\* matching between the elements from }\\{a\_1, a\_2, \cdots, a\_i \\}\text{ with $i$ elements from } \\{b\_1, b\_2, \cdots, b\_j\\}.$$

The first thing as with other recursive methods, is establish the well-defined bases cases of the recursion. These are the following. $$ \begin{align} f(i,1) &= |a\_i - b\_1|\ \ \ \forall i\in \[n\]\\ f(1,j) &= \min\ \\{\ f(1, j-1),\ |a\_1 - b\_j|\ \\} \ \ \ \forall j\in \[m\]\\ \end{align} $$ These are when we have just one element from $B$ and just one element from $A$, respectively.

Thinking like $f$ is working yet as we expected, we can define it as follows with $i\in \[n\]$ and $j\in \[m\]$.

$$ f(i,j) = \min \ \begin{cases} f(i-1, j-1) + |a\_i - b\_j| & \text{we match $a\_i$ with $b\_j$}\\ f(i, j-1)&\text{we won't pair $a\_i$ with $b\_j$} \end{cases}. $$

Be aware in the recursion for the corner cases, these are when $f$ is not defined. They are when $i$ or $j$, or even both are less than or equal to zero, for these cases, we are gonna say, $f(i,j) = \infty$.

So, what is the answer (?). Because, we are using top-bottom approach and based on the definition of $f$, after compute $f(n, m)$, it should give us the answer. Notice, that this way is one of many methods using dynamic programming, and sincerely, it is almost the same as the solution your provided in the link, but here it is just more explicit.

Maybe like a pseudocode, we can do this in `Python` with the following implementation.

```
@memo
def f(n, m):
    global a, b
    if m <= 0 or n <= 0:
        return float('inf')
    if n == 1:
        return min(f(1, m - 1), abs(a[0] - b[m - 1]))
    if m == 1:
        return abs(a[n-1] - b[0])
    x = f(n - 1, m - 1) + abs(a[n - 1] - b[m - 1])  # take b_m
    y = f(n, m - 1)  # dont take b_m
    return min(x, y)

print f(len(a), len(b))

```

My `@memo` decorator is the following, and is the key of a technique that involved dynamic programing, caching o memoization. from functools import wraps def memo(func): # memoization cache = {}

```
    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

```
> 0 votes

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


title: How a file is determined

text:
# Question
Title: How a file is determined
If I have the integer ""1234" stored in a file, the size of the file when I use the command "ls -l" or "wc -c" is 5. If I have "12345" the size of the file is 6. Basically the number of bytes in a file = (number of individual digits) + 1. Now, I am assuming the "+1" comes from the space it takes to create the name of the file. But why is the rest of the byte count equal to the number of individual characters? Does the file system read the file character by character even we "write an integer" to the file? Elaboration on this would be very helpful.

# Answer
> 1 votes
The +1 is for the newline character.

The byte count equals the number of characters, in this case, because each character takes exactly one byte. That need not be true in general (see, e.g., UTF-8), but it is for the example you listed.

You didn't write an integer to the file. You wrote a string -- a sequence of characters, namely the character 1, then the character 2, then 3, then 4, then a newline. Files don't store integers or other types. They store a sequence of bytes. Each character is converted to one or more bytes using an encoding, and then the sequence of bytes is written.

---
Tags: filesystems
---


title: Is this a kind of "sketching"?

text:
# Question
Title: Is this a kind of "sketching"?
Say one is given a matrix (assume real and symmetric if necessary) and its $n-$dimensional columns be say $v\_1,v\_2,..,v\_n$. Now is it possible to find a set of $d\<n$ lower dimensional vectors ($w\_1,..,w\_d$) such that they form a $d \times d$ matrix $B$ (assume real and symmetric) with either of these properties,

* That the $d$ eigenvalues of $B$ are "close" to the top$-d$ eigenvalues of $A$? (and hence the correspomding eigenvectors are also "close" in some sense?)
* That the spectral norm of $B$ is "close" to the spectral norm of $A$.

---

Will this be called "sketching"? Does Johnson-Lindenenstrauss lemma help in doing these?

# Answer
> 1 votes
Yes, you can match the eigenvalues. It is easy to construct a matrix with any desired eigenvalues: for instance, create a diagonal matrix and put the desired values on the diagonal. Thus, you can get an exact match, not just an approximate match. Nothing fancy is needed.

No, matching the eigenvalues doesn't imply that the eigenvectors of $B$ are somehow related in any way to the eigenvectors of $A$.

Given a value $n$ you can easily construct a matrix $B$ whose spectral norm is $n$, so that too can be exactly matched.

You don't need the Johnson–Lindenstrauss lemma for these results.

---
Tags: complexity-theory, approximation, randomized-algorithms, randomness, sketching
---


# Question
Title: Is it possible to build a heap from the root to the leaves?
Most books on data-structures will briefly introduce heaps (aka priority queues) and then move to describe the "trick" allowing heaps to be implemented as arrays.

I've been looking for a way to implement a heap as an actual tree (call it pointers to structs, cons cells etc.) This would also imply building the heap from the root to the leaves (since it won't be practical to hold references to all the leaves).

With some effort I'm able to make the resulting heap to arrange the nodes s.t. the parent is greater than the children, but I cannot think of a way to also balance it.

---

If you are interested, the motivation for this exercise is: Prolog and its dialects don't really have arrays (they kind of do, but they are almost immutable). Besides, in languages where persistent data structures are a big deal, the usual construction of heap would be problematic.

---

# Idea #1

I have a feeling that rotating (switching left and right nodes places) may take care of balancing (still need to try this).

# Answer
> 3 votes
```
{-

```

Yes, you can implement a priority queue using a complete binary tree in a purely functional way. You don't need parent pointers or pointers to the left or right most elements to get the same asymptotic complexity as the usual binary heaps.

This post is Haskell, with the prose enclosed in comments. You can copy and paste it and it should work in GHC 7.6.3, modulo a number of indentation mistakes caused by StackOverflow's buggy markdown implementation.

It requires LazySmallCheck, but if you don't want to install that, you can comment out that import line and the single test that uses `==>`.

```
-}

module BinaryHeap
       (BinaryHeap, -- The type of heaps
        size,       -- O(1): the number of elements in a heap
        emptyHeap,  -- The heap of size 0
        insert,     -- O(log n): add a value to a heap
        deleteMin,  -- O(log n): remove a value from a heap
        toHeap,     -- O(n): create a heap from a list faster than foldr insert
        toList)     -- O(n): create a list from a heap faster than foldr deleteMin
       where

import Control.Monad(guard)
import Data.Maybe(isJust, fromJust)
import Test.LazySmallCheck((==>))

data Tree a = Tip | Top a (Tree a) (Tree a) deriving (Show, Read)

{-

```

A full binary tree of depth n is either the empty tree if n is 0 or a tree in which both child subtrees of the root are full binary trees of depth n-1.

```
-}

full Tip = Just 0
full (Top _ x y) =
  do n <- full x
     m <- full y
     guard (n == m)
     return (1+n)

{-

```

A complete binary tree of depth n+1 is a full binary tree of depth n along with a partially filled last level, as long as the last level is filled from left to right, contiguously.

The function "complete" is a recursive vesion of that. It is used for testing. The idea is that there are four ways that a tree can be complete:

1. Both child subtrees of the root are full trees of the same height
2. Both child subtrees of the root are full trees, but the left subtree is one level deeper than the right one.
3. The left subtree is full, the right subtree is complete, and they have the same height.
4. The right subtree is full, the left subtree is complete, and the left subtree has depth one more than the right subtree.

Thus:

```
-}

data Completetion = Full | Part deriving (Read, Show)

complete Tip = Just (Full, 0)
complete (Top _ x y) =
  do (a,b) <- complete x
     (p,q) <- complete y
     case (a,p,b-q) of
       (Full, Full, 0) -> Just (Full, b+1)
       (Full, Full, 1) -> Just (Part, b+1)
       (Full, Part, 0) -> Just (Part, b+1)
       (Part, Full, 1) -> Just (Part, b+1)
       _ -> Nothing

{-

```

Unlike more loosely-constrained balanced trees like AVL trees or tries, the shape of a complete tree is determined entirely by its size. Additionally, a complete tree of size n differs in only one location from a complete tree of size n+1. For instance, a tree of size 6 can be turned into a tree of size 7 by adding a right-most grandchild of the root.

Like many data structures, especially purely-functional ones, structure and location can be dealt with more simply by considering representations of the numbers of the sizes of the structure.

Consider, for instance, the paths from the root of the nodes that are added to a tree of size 7 to turn it into a tree of size 8, then 9, then 10, all the way up to 15. A tree of size 7 is full, so the next node is added as the leftmost child of the root. The path to that node is

Left, Left, Left

The next node is at the path

Left, Left, Right.

I'll continue writing these, but I'll denote Left by 0 and Right by 1, and I'll omit the commas. Starting at the 8th node, we have

```
000
001
010
011
100
101
110
111

```

These are the representations of the numbers 0 through 7 in binary, written bigendianly. If you add a 1 at the front of each, then the path to the nth node added to a complete tree is just the binary representation of n.

So, to make a complete tree of size n:

1. Put n into a big-endian binary format, then drop the first 1.
2. (a) If the next bit is 0, the nth node goes in the left subtree, so the right subtree is full and has height one less than the left subtree.

(b) If the next bit is 1, the nth node goes in the right subtree, so the left subtree is full and has the same height as the left subtree.
3. Drop the most significant bit from the representation and recurse, using #2.

To turn this into a method for turning a list into a complete tree, first find the length of the list, then make a complete tree of that size, then put the values from the lists at the locations in the tree.

```
-}

makeFull [] = Tip
makeFull (_:xs) = let c = makeFull xs in Top () c c

makeComplete [] = Tip
makeComplete (False:xs) = Top () (makeComplete xs) (makeFull xs)
makeComplete x@(True:xs) = Top () (makeFull x) (makeComplete xs)

littleEndian 1 = []
littleEndian x = (odd x):(littleEndian (x `div` 2))

bigEndian x = reverse $ littleEndian x

preOrder [] _ = (Tip, [])
preOrder xs Tip = (Tip, xs)
preOrder (x:xs) (Top _ p q) =
  let (p',ys) = preOrder xs p
      (q',zs) = preOrder ys q
  in (Top x p' q', zs)

toComplete xs =
  let t = makeComplete $ bigEndian $ 1 + length xs
  in fst $ preOrder xs t

-- Tests for makeComplete

completeTest x = isJust $ complete $ makeComplete x

treeSize Tip = 0
treeSize (Top _ x y) = 1 + treeSize x + treeSize y

completeSizedTest n =
  (n >= 0) ==> (let t = makeComplete $ bigEndian (1+n)
                in n == treeSize t)

{-

```

Now that we have put the list into a complete tree, we can use the textbook linear-time heapify to turn that tree into a heap.

```
-}

pushDown x@Tip = x
pushDown x@(Top _ Tip Tip) = x
pushDown (Top x Tip y) = pushDown (Top x y Tip)
pushDown x@(Top p (Top q rt st) Tip) =
  if p <= q
  then x
  else Top q (pushDown $ Top p rt st) Tip
    pushDown x@(Top p y@(Top q rt st) z@(Top u vt wt))
      | p <= q && p <= u = x
      | q <= p && q <= u = Top q (pushDown $ Top p rt st) z
  | u <= p && u <= q = Top u y (pushDown $ Top p vt wt)

heapify Tip = Tip
heapify (Top x y z) =
  let y' = heapify y
      z' = heapify z
  in pushDown $ Top x y' z'

makeHeap xs = heapify $ toComplete xs

isHeap Tip = True
isHeap (Top x Tip Tip) = True
isHeap (Top x ys@(Top y _ _) Tip) = x <= y && isHeap ys
isHeap (Top x ys@(Top y _ _) zs@(Top z _ _)) =
  x <= y && x <= y && isHeap ys && isHeap zs

heapTest xs = let h = makeHeap xs in isHeap h && (isJust $ complete h)

{-

```

To add or delete a node, we need to know where the "last" node in a binary heap is, but this is completely determined by the size by just turning its binary representation (bigendian) into a path in the tree.

After we have the location, we can follow the textbook insert and delete operations on a binary heap.

Note that we do not need multiple pointers or anything fancy in the structure itself, which remains just an int (the size) and a bog-standard binary tree.

```
-}

data BinaryHeap a =
  BinaryHeap {size :: Int, values :: Tree a}
  deriving (Show, Read)

emptyHeap = BinaryHeap 0 Tip

toListHelp [] [] = []
toListHelp [] r = toListHelp (reverse r) []
toListHelp (Tip:xs) r = toListHelp xs r
toListHelp ((Top a b c):xs) r = a:(toListHelp xs (c:b:r))

toList (BinaryHeap _ x) = toListHelp [x] []

toHeap xs = let n = length xs in BinaryHeap n (makeHeap xs)

popHelp [] (Top x Tip Tip) = (x, Tip)
popHelp (False:xs) (Top p qt rt) =
  let (ans, qt') = popHelp xs qt
  in (ans, Top p qt' rt)
popHelp (True:xs) (Top p qt rt) =
  let (ans, rt') = popHelp xs rt
  in (ans, Top p qt rt')

popBottom n t = popHelp (bigEndian n) t

deleteMin (BinaryHeap 1 (Top x Tip Tip)) = (x, BinaryHeap 0 Tip)
deleteMin (BinaryHeap n t@(Top x yt zt)) =
  let (bottom, smallTree) = popBottom n t
  in (x, BinaryHeap (n-1) (pushDown $ Top bottom yt zt))

insertHelp [] x Tip = Top x Tip Tip
insertHelp (False:xs) v (Top p qt rt) =
  if v < p
  then Top v (insertHelp xs p qt) rt
  else Top p (insertHelp xs v qt) rt
insertHelp (True:xs) v (Top p qt rt) =
  if v < p
  then Top v qt (insertHelp xs p rt)
  else Top p qt (insertHelp xs v rt)

insert x (BinaryHeap n t) =
  let m = bigEndian (1+n)
  in BinaryHeap (1+n) (insertHelp m x t)

```

# Answer
> 4 votes
Binary heaps are one possible implementations for priority queues. Although their operations are best understood as binary trees, their implementation as arrays is essential. They are stored efficiently, due to the perfect balance you mention, and do not need explicit pointers to children or parent (as these are found by calculating their index in the array).

There is a very cute data structure (on the implementation level) for priority queues that is based on binary trees, has the same heap ordering of keys, but is not perfectly balanced. They are called leftist trees. Arbitrary leftist trees can be merged efficiently. This efficiency is obtained by forcing a height balance between the two subtrees of a node. The shortest distance to a leaf is the measure for this balance.

Perhaps these leftist trees are a better binary tree implementation for priority queues than heaps (which are arrays disguised as trees)?

---
Tags: data-structures, heaps, persistent-data-structure
---


# Question
Title: How to find left-hand side of tape on a Turing Machine?
I am pretty new to Turing Machines and am trying to figure something out. So let's say I have a tape with input

```
0 0 1 0 0 1

```

The language is twice as many 0's than 1's. So first time through, I will mark an X on the first 1 I find. Then when I am heading back to the start of the tape, how do I know when to stop? Can you "run" off the left hand side of the tape?

# Answer
for above example before you start your tape is like this ($e$ means empty and right side of $\>$ is block of tape that you are reading it)

```
e>001001e

```

as you said you should first mark $X$ on the first $1$ and it become like this

```
e00>X001e

```

now you should clear two zeros because the number of zeros is twice of the number of ones. you can clear the first two zero of the tape. go to the beginning of the tape like this (when you read $e$ it means you are at the beginning of tape and go one step to the right so that marker be over the first symbol of tape)

```
e>00X001e

```

now you can mark two zeros with $X$ or $Y$ it does't matter but for readability it's better to mark it with another symbol

```
eY>YX001e

```

now go back to the beginning of tape

```
e>YYX001e

```

now it's like a for loop you should do this until there is no $1$ on the tape. when you got end of the tape while searching for $1$ it means that you ran out of ones. you should check two cases

1. is number of ones less than twice of zeros
2. is number of ones greater than twice of zeros

if the first case happens while you are searching for zeros you cant find two of them and you got to the end of tape like below

```
e>00010111e

```

become

```
eYYYXYXY1>e

```

so in this case you should reject the string.

and checking the second case is in the last step when you ran out of ones you should check that is there any zeros one the tape right now. if you found any zero you should reject.

remember never write empty over $0$ or $1$ because when you reach empty it means you are at the end or the beginning of the tape.

based on definition of Turing Machine you can run off the left hand side or not. there are Turing Machines that their tapes are infinite at the right side and finite at the left side so you can run off at the left side. but standard Turing Machine is infinite at both site so you can run off at the left hand side.
> 5 votes

---
Tags: turing-machines
---


title: Uses of the type Unit

text:
# Question
Title: Uses of the type Unit
The `Unit` type is a singleton type containing the constant `unit`. In functional languages with side effects, `unit` is used in functions that perform side effects. For example `print` is a function from `string` to `Unit`.

`Unit` also corresponds to truth. If you view the type of the expression as a proposition and the program as a proof, `Unit` corresponds to truth since you can always prove `Unit` by using the constant `unit`.

My question is aside from these two uses, is there any other uses of `Unit`?

# Answer
Some other usages of the type `Unit` (I'm sure the list is not exhaustive):

(1) The value of type `Unit` is used to simulate functions of arity 0 in strict languages that don't have zero-argument functions, like in OCaml: `f ()`. Essentially this is just for deferring computations.

(2) It also can be used to instantiate some parametrically polymorphic type when the actual "payload" is not some data, but the shape of a data structure, like when it's only the length of a list is of interest to us.

(3) `Unit` is used in dependently typed languages, for instance as a type-level analogue of the empty list or a dummy value. A simple example in Coq:

```
Fixpoint nat_to_tuple (n : nat) : Set :=
match n with
  | O => unit                 (* ! *)
  | S n' => nat * nat_to_tuple n'
end % type.

Eval compute in (nat_to_tuple 3).

(* Evaluates to (nat * (nat * (nat * unit)))
   Note: unit in Coq corresponds to Unit in the question;
         nat is the type of natural numbers;
         Set is the type of types of programs.
 *)

```

You might want to take a look at a more educational (but longer) example on implementing the head function(`hd`) for length-indexed lists in the Certified Programming with Dependent Types book by A. Chlipala.
> 5 votes

# Answer
I can think of a couple:

1. If a language makes a distinction between functions that return a value, and those that don't, it becomes difficult to stitch functions together. You have one set of functions that do return a value, and one set that doesn't. You end up having to write somewhat duplicated higher order functions. One set of higher order functions that work on a function that returns a value, and one set that doesn't. Or you say "just wrap your function that returns a value in one that doesn't", incurring an extra function call overhead.
2. Sometimes you have a function that is interesting only if it succeeds. If you have a type like Haskell's Either (returns either A or B, but never both), you can pair it with a unit. You can get a function that returns unit on success, and some sort of error class/enum/monad/what have you on failure. That means that when there's an error, you have something you can poke to get more information from (instead of, say, a status code). Granted, you don't necessarily need a unit, but having unit makes it absolutely clear that the value is uninteresting.
> 2 votes

---
Tags: lambda-calculus, curry-howard
---


title: Shuffled Strings Dynamic Programming

text:
# Question
Title: Shuffled Strings Dynamic Programming
So I have this question:

> A shuffle of two strings X and Y is formed by interspersing the characters into a new string, keeping the characters of X and Y in the same order. Example would be
>
> ```
> X = AND
> Y = THE
> Z = ATHNED -> A  N D
>                TH E
>
> ```

So this would return true. I've seen solution to this using Dyanimc Programming, but I came up with just a purely iterative algorithm that runs in O(|Z|), but I'm guessing there must be something wrong with it since all the solutions I've seen all use either memoization or DP.

Basic psuedocode for my solution (I omit some obvious base cases):

```
solution(X,Y,Z):
   i = j = 0
   for(k=0 to |Z|):
      if(either i or j out of bounds):
         return false
      if(Z[k] == A[i]):
         i++
      elif(Z[k] == B[j]):
         j++
      else:
         return false
   return true

```

Basically this just runs down string Z and marks off whichever string it came from, and when a character doesnt match either, it cant be an interleaved string.

Can someone pick this apart and tell me what's wrong and why I have to use DP?

# Answer
> 2 votes
Consider the following counter example

Let $A = aa$

Let $B = aab$

Let $Z = aabaa$

Your code will return false while the answer is true.

This is because you are giving preference to matching $A$ before matching $B$. There is no property of the problem that says that it is optimal to match all characters to $A$ before $B$ in case the character can be in both $A$ and $B$.

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


# Question
Title: Is it possible to solve the coin denomination problem using a 1-D array?
In an algorithm book it said that to solve the coin denomination problem via Dynamic Programming approach a 2-D array is needed:

Exercises 8.4 #9

Is it not possible to do this using a 1-D array.

I was thinking that maybe you could set the $C$ values in a 1-D array as: $C\[0\]=0$, $C\[n\]=1$ if $n$ is one of the denomination values and $C\[n\]= \infty$ if $n$ is less that the least denomination.

Otherwise set $C\[n\] = \min\_{1 \<= i \<= \frac{n}{2}}{(C\[i\]+C\[n-i\])}$

What is wrong with my solution other than I won't be able to generate the actual solution because my goal is only to find the optimal number of coins for that $n$ value?

# Answer
It is perfectly possible to solve the problem using a 1D array. Actually, you can even reconstruct the solution using just that 1D array. There are often multiple ways to solve a given problem, and in this case there's a neat time-memory tradeoff: in the 1D example you need $O(m)$ time to compute the value of one array slot, in the 2D example you only need $O(1)$ time but there are $O(nm)$ slots rather than just $O(n)$.
> 2 votes

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


# Question
Title: Can we derandomize subexponential algorithms given P=BPP?
Under $BPP=P$ conjecture randomization does not have much power for poly time algorithms.

Can we say the same about randomized subexp algorithms like number field sieve?

# Answer
Derandomization results transfer "upwards" using the technique of padding. Assume $\mathsf{P}=\mathsf{BPP}$. Suppose that some problem $A$ can be solved in randomized superpolynomial time $t(n)$ (which is time-constructible). Let $A'$ be the same problem, but with inputs padded to length $t(n)$. Then $A' \in \mathsf{BPP} = \mathsf{P}$. The following algorithm then solves $A$ in deterministic time $t(n)$: pad the input to length $t(n)$, then apply the polynomial time algorithm for $A'$.

Conversely, it is possible (given the current state of knowledge) that subexponential time algorithms can be randomized, but polynomial time algorithms can't (and it might be possible to construct a relativized world in which this happens unconditionally). That is, results don't transfer "downwards".
> 3 votes

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


# Question
Title: Regular expression for a finite automaton appears to be wrong
For the following finite state machine:

The language recognized by it is given to be: $0+(10+11)(0+1)^\*$ in my samples book, which I think is clearly wrong, since there's no return path to the final state.

I think the language recognized should be just an epsilon or nothing. I wanted to confirm if I am right or wrong with the answer.

# Answer
> 1 votes
Yes, you are right.

As given FA is DFA. It is accepting string only $\\{\epsilon \\}$.

And, complement of given DFA accepting : $\implies (1+0+1(0+1))(0+1)^\*= (1+0+(10+11))(0+1)^\*$

$\implies 1(0+1)^\*+0(0+1)^\*+(10+11)(0+1)^\* = (0+1)^+ =$ { accepting everything other than $\\{\epsilon \\}$ string over alphabet $\\{0,1\\}$}.

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


title: EXP-complete example

text:
# Question
Title: EXP-complete example
Is there an explicit example of a language which is EXP-complete? Or a weaker question, i.e., is there an explicit example of a language which is proven to be in EXP but not in P? By diagonalization theorem, we know the existence of such a language but is there a construction or explicit example known till date?

# Answer
Every EXP-complete problem is not in P, by the time hierarchy theorem. Many games are EXP-complete, you can look up some starting from here.

As a concrete example (albeit not a very simple one), you can consider the problem of emptiness of the intersection of deterministic tree automata. Formally, the input consists of $n$ DFTs $A\_1,...,A\_n$ (deterministic automata over trees), and the problem is to decide whether $L(A\_1)\cap...\cap L(A\_n)\neq \emptyset$.
> 6 votes

# Answer
Wikipedia lists several EXPTIME-complete problems:

* Deciding whether a Turing machine halts within a given number of steps
* Generalized versions of chess, checkers and go
* Succinct versions of P-complete problems
> 6 votes

---
Tags: complexity-theory
---


# Question
Title: Which is more fundamental: key-value or subject-predicate-object?
There seems to be two approaches to store data in NoSQL databases:

**Key-Value** \- The `Key` is usually stored in a hash-table referencing a `Value`, or `Object`, which can be either a key (with specific semantic) or any arbitrary data. Examples are Riak, Redis, Dynamo, CouchDB...

**Subject-Predicate-Object** \- `Subject` and `Predicate` are interpreted as keys and `Object` can be either a key or an arbitrary data. This will cover not only all RDF stores, but also graph databases. Examples are Neo4j, Virtuoso, AllegroGraph...

Now I am not that interested in exact definition and which database falls into which category. We know that there are plenty of RDF triple stores implemented on top of SQL databases, as well as that any SQL database can be represented using only RDF triples. And there are other database types too, like column and document databases.

I am interested in finding out which representation is more fundamental in the sense that for example for a given processor **assembler** is more fundamental than **C** (because C is written in assembler) and **C** is more fundamental than **Erlang** (because Erlang is written in C), and so on. Or also that binary representation is more fundamental than any other (octet, decimal, hexadecimal) because it uses the smallest amount of different numbers (`0` and `1`). Unfortunately I don't have a strict definition of what more fundamental means exactly.

In other words, if we assume the following:

* A `Key` is an `IRI` resource (globally unique identifier, like used in RDF)
* A `Blob` is some arbitrary binary data we can't interpret

Then we can define the following two database types:

1. `Key-Value`: Where `Key` is an `IRI` and `Value` is either an `IRI` or a `Blob`
2. `Subject-Predicate-Object`: Where `Subject`, `Predicate` are `IRI`s, and `Object` is either an `IRI` or a `Blob`

In particular, those would be the fundamental data types stored in those two databases:

Ad 1: `Key-Key`, `Key-Blob`

Ad 2: `Key-Key-Key`, `Key-Key-Blob`

I have no doubt that any data stored in any database type (graph, column, table, key-value, triple, etc) can be represented in either of those databases. I have also no doubt that data stored in one of those databases can be represented in the other, for example let's assume to represent a `Key-Value` pair as `{Key, Value}` and `Subject-Predicate-Object` as `{Subject, Predicate, Object}`. Then:

**Example 1:**

`{1, "abc"}` can be represented as two triples `{2, 3, 1}`, `{4, 3, "abc"}` where `2` means `Key`, `3` means `Stores` or `Holds`, `4` means `Value`.

**Example 2:**

`{1, 2, "abc"}` can be represented as three tuples `{1, 1}`, `{1, 2}`, `{1, "abc"}` where `Key = 1` means triple number `1`, `Value = 1` means `Subject` position, `Value = 2` means `Predicate position`, `Value = 3` means `Object` position.

The `means` is a conceptual shortcut for having a proper IRI representing that meaning.

Is there any scientific evidence that one representation is more fundamental than the other? Or, because there is no strict definition of "more fundamental", if we could put it as which representation can more easily and/or efficiently represent data stored in any other database type? And I am asking that because I hope that there isn't just an answer like "it depends" :)

# Answer
> 1 votes
Following your simplicity argument (binary is more fundamental than octal), I'd say that `key-value` stores are more fundamental. I think that `Subject-Predicate` is essentially a 'compound' or 'aggregate' key, so a `subject-predicate-object` store is a `key-value` store with additional requirements on the key (namely that it can be split into two).

# Answer
> 1 votes
The choice here is really about what semantics are exposed to the fetch/store process, and are not really about the object representation. By giving syntactic structure to the identifier (key / address / this goes by many names) of the object, the fetch and store may have some useful characteristics. This includes:

* Fetch with partial identity information (bulk/pattern fetch)
* Optimised fetch/store possible with locality

Outside semantics useful to the fetch/store process, though, semantic structure in the data from the application is typically far more complex than either of these identity patterns. These are just syntactic flattenings of that more intricate structure for systems that don't need to take dependencies on that structure (and so have more reuse).

---
Tags: graphs, data-structures, database-theory
---


# Question
Title: Why is the counting variant of a hard decision problem not automatically hard?
It is well-known that 2-SAT is in P. However, it seems quite interesting that counting the number of solutions to a given 2-SAT formula, i.e., #2-SAT is #P-hard. That is, we have an example of a problem for which decision is easy, but counting is hard.

But consider an arbitrary NP-complete problem (say 3-COL). Can we immediately say something about the hardness of its counting variant?

Really what I'm asking is: why do we need another proof to show a counting variant of a hard decision problem is also #P-hard? (Sometimes you see parsimonious reductions that preserve the number of solutions, and so on). I mean really, if the counting problem *was* easy, you could automatically solve the decision problem as well! So how could it not be hard? (OK, maybe it is hard, but I'm not sure for what definition of hard).

# Answer
> 16 votes
The reason it's not an automatic theorem that "decision is hard implies that counting is hard" is that these two statements use different definitions of "hard".

* A decision problem is hard if it's **NP**-complete under polynomial-time many-one reductions (a.k.a. Karp reductions, a.k.a. polynomial-time mapping reductions).
* A counting problem is hard if it's **#P**-complete under polynomial-time Turing reductions (a.k.a. Cook reductions).

As such, if a decision problem is **NP**-complete, we know that the corresponding counting problem is **NP**-hard but that's not the definition of what a hard counting problem is. Being **#P**-complete seems to be a much stronger statement than just being **NP**-hard – Toda has shown that **#P**-complete problems are hard for the entire polynomial hierarchy under randomized reductions so, as a complexity class, **#P** feels much closer to **PSPACE** than to **NP**.

Going in the opposite direction, it's clearly true that, if the counting problem is easy in the sense of being in **FP**, then the decision problem is in **P**. After all, if you can efficiently count, you can certainly tell if the answer is nonzero. However, just because the counting version is "not hard" (i.e., not **#P**-complete) doesn't imply that it's "easy" (i.e., in **FP**). Ladner's theorem extends to **#P** so, if **FP**$\\,\neq\\,$\**#P\** then there's an infinite hierarchy of distinct complexity classes between them so our "not-hard" counting problem could be complete for any one of those classes and, therefore, not be "easy" (in **FP**).

Having said that, I don't think we have any counterexamples to the conjecture that a decision problem being **NP**-complete means that the counting version is **#P**-complete. So, it's not a theorem but it is empirically true.

---
Tags: complexity-theory, counting
---


# Question
Title: What is the name of the word problem for free groups under straight line program encoding?
I believe that the word problem is the problem to decide whether two different expressions denote the same element of a suitably defined algebraic structure. For simplicity, let us focus on free groups here. (Because I'm only interested in free algebras, and for groups one might indeed call this a word problem.) The expressions $(b^{-1}c)^{-1}b^{-1}(ab^{-1})^{-1}$, $(ab^{-1}c)^{-1}$, and $a^{-1}bc^{-1}$ are examples of such expressions. The first and second expression denote the same element of the free group, while the third expression denotes a different element.

The straight line program encoding is basically the same concept as arithmetic circuits, without implicit commutativity. It is one of the natural encodings of elements for a free algebra. One way to define the straight line program encoding is like in definition 1.1 from one of the google results for straight line program: The straight line program encoding of $f$ is an evaluation circuit $\gamma$ for $f$, where the only operations allowed belong to $\\{()^{-1},\cdot\\}$. More precisely: $\gamma=(\gamma\_{1-n},\dots,\gamma\_0,\gamma\_1,\dots,\gamma\_L)$ where $f=\gamma\_L$, $\gamma\_{1-n}:=x\_1,\dots,\gamma\_0:=x\_n$ and for $k\>0$, $\gamma\_k$ is one of the following forms: $\gamma\_k=(\gamma\_j)^{-1}$ or $\gamma\_k=\gamma\_i\cdot\gamma\_j$ where $i,j\<k$.

The application of the operation $()^{-1}$ can easily be restricted to $\gamma\_k=(\gamma\_j)^{-1}$ for $j\leq 0$ without increasing $L$ to more than $2L+n$. This means that we are basically talking about words over the alphabet $\\{x\_1,\dots,x\_n,(x\_1)^{-1},\dots,(x\_n)^{-1}\\}$, hence the name "word problem" makes sense. But it seems a bad name for the general problem to decide whether two elements of a free algebra given by straight line programs are identical. It might be called *identity testing*.

> Does the problem (to decide whether two elements of a free algebra given by straight line programs are identical) already has an established name, or is there a good name for this problem?

Maybe a better idea would be to give a name to the complementary problem, i.e. the problem to distinguish two different elements of a free algebra. So calling it *slp distinction problem* for free groups (commutative rings, commutative inverse rings, Boolean rings, ...) could work, because straight line program (slp) is a long name (but good and descriptive nevertheless). The advantage of naming the complementary problem is that we get problems in RP and NP, instead of problems in co-RP and co-NP.

---

The computational complexity of this problem is not worse than that of identity testing of constant polynomials over $\mathbb Z$ in straight line program encoding (no variables, i.e. $n=0$, but the straight line programs allow to compactly encode huge numbers): Using the same approach as in the dlog-space algorithm for the normal word problem, the problem can be reduced to deciding whether the product of integer 2x2 matrices equals the identity matrix. (The word problem over $n$ letters easily embeds into the word problem over $2$ letters, for example you can replace $a$, $b$, $c$, $d$ by $aa$, $ab$, $ba$, and $bb$.) So the problem is in randomized polynomial time (RP) (or rather co-RP). However, I didn't manage to show that it is actually equivalent (in complexity) to identity testing of (constant) polynomials over $\mathbb Z$, as I initially hoped. (This is unrelated to the answer by D.W., which rather shows that the significance of straight line encoding is currently not widely appreciated.)

# Answer
The blog post you link to already gives a *deterministic* polynomial-time (in fact, linear-time) algorithm for the word problem over a free group with 2 letters.

In contrast, no deterministic polynomial-time algorithm for identity testing for polynomials is currently known (this is a famous open problem).

Therefore, it's not likely to be easy to prove that the word problem over the free group is equivalent in complexity to identity testing of polynomials.

---

The "straight-line encoding" doesn't seem to change the complexity of the word problem in any interesting way. It seems equivalent to simply specifying the input as an expression (i.e., a sequence of symbols, where each symbol is either $x\_i$ or $x\_i^{-1}$).
> 2 votes

---
Tags: terminology, decision-problem, group-theory
---


title: Need help with ER diagram

text:
# Question
Title: Need help with ER diagram
I am making database on Disaster Management. There are four tables.

1. `DisasterEvent (eventid, name, glideID, status, description, date_occurred, date_ended, disaster_type)`
2. `People(eventid, num_deaths, num_injuries, num_affected)`
3. `Homes (eventid, num_homes_destroyed, num_homes_damaged, total_insured_loss, total_uninsured_loss)`
4. `Place (place_id, city, state, country, postal_code)`

In my design, I have *one to one relationship* between **`People`** and **`DisasterEvent`** , and *one to one relationship* between **`Home`** and **`DisasterEvent`** because for a particular disaster there is only one **`People`** table that we are concerned and same for **`Home`** table. Now, **`Place`** has *many to many relationship* with **`DisasterEvent`** because at particular place there can be many disasters over time and same disaster could occur many place at once.

What am I trying to achieve is able to map number of affected people by the particular disaster event at certain place. For this I think there needs to be three way relationship among **`DisasterEvent`**, **`Place`** and **`People`**. How do I achieve this?

# Answer
Since you have a 1-1 relationship between **DisasterEvent** and **People** now, you can **not** distinguish any relation between **People** and **Place**. If several **Places** are related to a single **DisasterEvent**, all those places are related to the same instance of **People**.

If you want to map the **People** affected by the **Event** at a **Place**, you should relate **People** to **Place** instead of to **DisasterEvent**.

As long as an event always occurs at at least one place, you can always relate your **People** to your **DisasterEvent** via the **Place** where it occurred.

On a sidenote, I would use *Location* instead of *Place*, and maybe the more precise *Victims* for *People*, as well as maybe *Damage* for *Home*.
> 4 votes

---
Tags: databases
---


title: I'm having trouble with Parse Trees

text:
# Question
Title: I'm having trouble with Parse Trees
I am doing homework and I have the following problem:

Consider the grammar:

```
statement → assign
statement → sub_call
assignment → id = expression
sub_call → id ( arguments )
expression → head tail
tail → operation expression
tail → ε
head → id
head → sub_call
head → ( expression )
operation → + | - | * | /
arguments → expression arg_tail
arg_tail → , arguments
arg_tail → ε

```

Construct a parse tree for the input string:

```
 foo(a , b)

```

Add the production rules necessary to extend this grammar to include the definition of a subroutine. For example:

```
subroutine foo (x, y) {
z = x + y
bar(z) }

```

**What I've Considered**

I am somewhat familiar with trees that use expressions,literal, and variables but this is so much more and I can't think of where to even begin. Not to mention create a tree for a subroutine. Could someone please help me with this? How do I even start?

# Answer
> 0 votes
It's not actually that much more, it just feels daunting because the syntax is different.

## Creating a parse tree

In general, a parse tree is built out of the production rules in your grammar.

A simple string like `x + y` will have a derivation1 like:

```
expression => head tail
           => head operation expression
           => head operation head tail
           => head operation head ε
           => head operation id ε
           => id operation id ε

```

You can use this derivation to build a parse tree, the root of which will be he non-terminal `expression`, the leaves of which will be the terminals `id`, `operation`, `id`, and `ε`, and the interior nodes of which will be assorted non-terminals; I'll leave it as an exercise to figure out the specifics.

To build a parse tree for `foo(a , b)`, you would do exactly the same thing: find a derivation, and then convert it into a parse tree.

## Adding production rules

This is a slightly harder problem, in my opinion, but still not too bad. I would suggest starting by sketching out what you think a derivation *should* look like, and then add the production rules you need.

---

1 This is a right-derivation, but you could also do a left-derivation by expanding the non-terminals from left-to-right rather than from right-to-left. I'm not sure how you've been taught, so do what you've been told

# Answer
> 0 votes
Below is Prolog DCG for your requirement (using SWI Prolog):

```
:- use_module(library(dcg/basics)).

id_first --> [X], { code_type(X, csymf) }.
id_rest  --> [X], id_rest, { code_type(X, csym) } | [].
id       --> id_first, id_rest.
space    --> [X], space, { code_type(X, space) } | [].
end      --> [10].
op       --> `+` | `-` | `*` | `/`.

expression  --> subcall | arith_exp | id.
args        --> space, expression, space
              | expression, space, `,`, space, args
              | space.
ids         --> space, id, space
              | space, id, space, `,`, space, ids
              | space.
line        --> space, assignment, space, end
              | space, expression, space, end.
expressions --> line | line, expressions | space.
assignment  --> id, space, `=`, space, expression.
subcall     --> id, `(`, args, `)`.
arith_exp   --> space, id, space
              | space, subcall, space
              | space, id, space, op , space, arith_exp.
signature   -->  id, space, `(`, ids, `)`.
subroutine  --> `subroutine`, space, signature, space, `{`,
                  space, end, expressions, `}`.

```

I think, that it is easier to start with something that gives you feedback as you try to improve on it. You can test this grammar by typing something like:

```
?- phrase(subroutine, `subroutine x (y, q) {
x = y
y = func(x + z)
 } some junk`, X), string_codes(Y, X).
|    X = [32, 115, 111, 109, 101, 32, 106, 117, 110|...],
Y = " some junk" .

```

Into Prolog interactive shell after you've loaded the predicates. `phrase/3` predicate has this meaning: `phrase(A, B, C)` \- `A` is the grammar to use to parse `B` string, while the part of `B` which failed to parse will be stored in `C`.

As to your specific question, you can think about it like so: you need a rule that only matches something that starts with the exact string `subroutine` followed by `Id` variable, followed by exact string `(`, followed by the list of arguments `Arguments`, followed by exact string `)`, followed by exact string `{`, followed by `Block` (of code), ending in exact string `}`.

Note that `Block` uses the same principle as `Arguments`, so it's either nothing, a single expression or a single expression followed by a `Block` of code.

---
Tags: parsers, syntax-trees
---


# Question
Title: Lower Bounds for Size of Independent Set in a Graph?
I recently learnt that for any instance of a k-SAT problem with $m$ clauses and $n$ literals , we have an assignment of literals such that at least $m(1 - 2^{-k})$ clauses are satisfied.

I was wondering if we can we show a (non trivial) lower bound of the kind that any graph $G = (V,E)$ has an independent set of size $S$ where $S$ is some function in the number of vertices and edges or the like?

Since in the optimisation version we try to find a maximum independent subset, the tighter the lower bound, the better. Hence I was wondering if there is such a lower bound exists, how tight can we make it?

# Answer
The relevant result is known as Turán's theorem. It states that if a graph has less than (roughly) $n(n-1)/(2r)$ edges then it has an independent set of size $r+1$, and this is tight.
> 9 votes

# Answer
There is also an algorithmic kind of result. Given an $n$-vertex planar graph $G=(V,E),$ one can compute in linear time an independent set of vertices of degree less than $12$ whose size is at least $\left\lceil\frac{n}{24}\right\rceil.$ See e.g. Das, Goodrich, On the complexity of optimization problems for 3-dimensional convex polyhedra and decision trees
> 4 votes

---
Tags: graphs, satisfiability, lower-bounds
---


# Question
Title: Why did RSA encryption become popular for key exchange?
This is a soft question. I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g., the description of iMessage here). Isn't this exactly the thing that Diffie-Hellman key exchange, which is older (and to me seems simpler) is for? Looking at Wikipedia, they were also both patented, so this wouldn't have been responsible for the choice.

To be clear, I'm not asking whether it's theoretically important that public key cryptography is possible. I'm asking why it became a standard method in practice for doing key exchange. (To a non-cryptographer, DH looks easier to implement, and also isn't tied to the details of the group used.)

# Answer
There is no strong technical reason. We could have used Diffie-Hellman (with appropriate signatures) just as well as RSA.

So why RSA? As far as I can tell, non-technical historical reasons dominated. RSA was patented and there was a company behind it, marketing and advocating for RSA. Also, there were good libraries, and RSA was easy to understand and familiar to developers. For these reasons, RSA was chosen, and once it was the popular choice, it stayed that way due to inertia.

These days, the main driver that has caused an increase of usage of Diffie-Hellman is the desire for perfect forward secrecy, something that is easy to achieve by using Diffie-Hellman but is slower with RSA.

Incidentally: It's Diffie-Hellman key exchange, not Diffie-Hellman secret sharing. Secret sharing is something else entirely.
> 14 votes

# Answer
Diffie–Hellman lacks a crucial feature: authentication. You know you are sharing a secret with someone, but you can't know if it's the recipient or a man in the middle. With RSA, you may have a few trusted parties who store public keys. If you want to connect to your bank, you can ask the trusted party (let's say Verisign) for the bank's public key, as you already have the public key of the trusted party on your computer. You know therefore that you are sharing a secret with your bank.

With Diffie–Hellman, when you create a secret with your bank, you may in fact create a secret with a man in the middle (MITM), who also create one with your bank, and he just has to translate from one encryption key to the other to remain invisible (while being able to read the whole communication).
> 10 votes

# Answer
The RSA Algorithm as previously mentioned is not that much better than Diffie–Hellman, the latter just lacks authentication also both the algorithms depend on the difficulty in finding discrete logarithms so security wise they are both pretty similar.
> -2 votes

# Answer
There is a dark side to this which cannot be overlooked.
The fact that the RSA was co-opted by the NSA.
The NSA planted a backdoor in the Eliptic Curve cyhper which it supplied to the RSA.
http://www.intelligence-world.org/nsa-infiltrated-rsa-security-more-deeply-than-thought-study/
> -3 votes

---
Tags: cryptography, history
---


# Question
Title: Exhaustive list of ways to distribute n objects to k sets
I am working on a research paper and we are developing a brute force algorithm to examine another clustering technique.

In this brute force algorithm we test every possible clustering example and see what natural clusters occur.

The problem comes from the assignment of every possible clustering. If give each value a cluster sequentially the complexity is much higher than necessary and results in many overlaps.

Sequential Example: 5 objects into 3 clusters 11111, 11112, 11113, 11114, 11115, 11121, etc. . .

But 11112 and 11113 are effectively the same. The complexity above is O(k^n) where k is the number of clusters and n is the number of objects. This makes for a terrible time afterwards because duplicates will not be fun to work with and parse. Looking at natural clusters becomes easier with more points as well, and in a simple example, assigning 20 to 5 results in 3,200,000 mostly duplicate clusterings.

If we look at this using combinatorics then we can assign n objects to k groups in (n + k - 1) C (k - 1) ways. This results in 20 objects to 5 clusters having only 10626 different combinations.

Is there any way already made to exhaustively produce these arrangements in this way to eliminate the duplicates?

# Answer
> 2 votes
The objects you are interested in enumerating are counted by Stirling numbers of the second kind. In particular, $\genfrac{\\{}{\\}}{0pt}{}{n}{k}$ is the number of ways to partition a set of size $n$ into $k$ non-empty parts. The Stirling numbers satisfy the recurrence $$ \genfrac{\\{}{\\}}{0pt}{}{n+1}{k} = k\genfrac{\\{}{\\}}{0pt}{}{n}{k} + \genfrac{\\{}{\\}}{0pt}{}{n}{k-1}. $$ Indeed, either element $n+1$ is in a partition of its own, or it joins one of the other $k$ parts. The initial conditions are $\genfrac{\\{}{\\}}{0pt}{}{0}{0} = 1$ and $\genfrac{\\{}{\\}}{0pt}{}{0}{n} = \genfrac{\\{}{\\}}{0pt}{}{n}{0} = 0$ for $n \> 0$. In other words, if $n = k = 0$ then there is a unique solution (the trivial solution), and if $n = 0$ or $k = 0$ otherwise then there are no solutions.

You can use this recurrence to recursively generate all partitions you are after.

---
Tags: combinatorics, data-mining
---


# Question
Title: How to handle missing continuous attribute values in ID3 (Iterative Dichotomiser 3)?
I'm implementing the ID3 algorithm (Iterative Dichotomiser 3). I have an attribute which happens to be continuous like 12.21, 3.01, etc. AND have missing values which are marked as "NA".

How I'm discretizing the data: I'm finding the optimal split which results in the max information gain. How I'm dealing with missing values: I will use the most probable attribute value to replace the "?".

Of course I can do either process in both ways, and this is where my confusion arises. Is there a correct way in handling this?

# Answer
I would like to propose paper about ID3 and it's successors, generally about Decision Tree Algorithms.

Using Mean, Median, Mode etc. is very tempting and it works to some degree, but of course the outcome depends on values inserted to missing (NA) data.

Mean has nice property in many statistics that it just acts like missing value, but increases weight of other ones (since it changes nothing, other values are counted with +1/N weight).
But in decision trees the effect is bigger, changing the classifier, so there is one big idea - apply all possible missing values :-/.

There are also three easier techniques:

* apply mean and do not care
* reconstruct data to fit classifier better (very often trial and error, but due to discretization of continous data, only values that differ by multiplicity of $\epsilon$ are to be checked)
* try to reconstruct data

The last one should yield the best results, but it is not always possible, and still these are not exact values.

If you can predict the most probable value and replace missing ones - this is the best way to do it.
> 0 votes

# Answer
Take a look at the C4.5 algorithm. C4.5 is a successor to ID3. It is more complex. However, Wikipedia lists as one of its advantages over ID3 that C4.5 can handle data with missing attribute values. So, you might take a look at how C4.5 handles missing attribute values -- or even simply use C4.5 rather than ID3.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Is emulation and/or virtualization faster when the host and guest systems are more similar?
Is emulation and/ or virtualization performance faster when the guest and host OS are similar? If yes, how big, relatively speaking, is the difference? And whether the answer is yes or no, *why is it so*?

For example:

**Same architecture**

Will a x86 Windows host emulate and/or virtualize an x86 Android guest faster than it will an ARM Android guest?

**Similar OS**

*In the following two examples, please ignore the fact that Debian is arguably more resource efficient than Windows, and simply focus on **relative** emulation/virtualization performance.*

Will a Windows 10 host emulate/virtualize a Windows 7 guest faster than it will a Debian guest? (All are x86.)

**Remotely similar OS**

Will an OS X host emulate/virtualize a Debian guest faster than it will a Windows guest? (All are x86.) (Since OS X and Debian are both UNIX or UNIX-like.)

I would appreciate if any answers used many layman terms and analogies to explain in a way that people who are not computer scientists could understand it.

# Answer
Yes, virtualization on the same architecture will be a lot faster, if the architecture has built-in support for virtualization (as modern x86 processors do). With hardware support for virtualization, most code will run at full speed.

If you want to "virtualize" onto a different architecture, then under the hood the VM will probably end up doing emulation. Emulation is much slower.

To understand why, I suggest you do some more background reading about how virtualization and emulation work. You could start with Wikipedia: https://en.wikipedia.org/wiki/Virtual\_machine and https://en.wikipedia.org/wiki/Hardware-assisted\_virtualization and https://en.wikipedia.org/wiki/Hardware\_virtualization and https://en.wikipedia.org/wiki/Emulator. If you'd like more details, you could check out an appropriate textbook (e.g., a good operating systems textbook).

---

The operating system most likely won't matter -- at least, there's no fundamental reason why it needs to make a difference. (It might make a difference for engineering reasons rather than scientific reasons, e.g., due to a 32-bit vs 64-bit OS, or due to lack of support for features used by the VM software.) The only way to know for sure is to do some experiments: measure performance on workloads you care about.
> 2 votes

---
Tags: computer-architecture, operating-systems
---


# Question
Title: Presentation of context rules for the lambda-calculus
Reading Chris Hankin's book, *"An Introduction to Lambda Calculus for Computer Scientists"*, I learnt that the rules for reductions in the pure $\lambda$-Calculus are the $\beta$-reduction rule, $$(\lambda x.M)N = M\[x:= N\]$$ and also these: $$\frac{M=N}{N=M}$$ $$\frac{M=N}{MZ=NZ}$$ $$\frac{M=N}{ZM=ZN}$$ $$\frac{M=N}{\lambda x.M = \lambda x.N}$$ The author calls this "The Theory $\lambda$"; and although he formally defines contexts, he does not use them there.

Now, some other works -- for example, Didier Rémy's *"Type Systems for Programming languages"* -- seem to imply that there are only the $\beta$-reduction rule, and a context-rule: $$(\lambda x.a)v \to a\[x:= v\]$$ $$\frac{a\to a'}{e\[a\]\to e\[a'\]}$$ Here $e\[\]$ is an evaluation context, "$a$" is an arbitrary term, and "$v$" is a value (which the author defines to be an abstraction -- variables, he says, are not values).

I am a bit confused. I *think* (but I'd need confirmation) that they are saying the same thing, but Rémy's approach actually allows for the specification of evaluation strategy (because I can then decide if the context hole will be to the left or to the right, etc), while the presentation by Hankin does not.

Is this correct, or did I completely miss the point?

# Answer
The two formulations are saying almost the same thing. Hankin's presentation has a symmetry rule ($\frac{M=N}{N=M}$), which is strange: it ends up defining the relation “$M$ reduces to $N$ or $N$ reduces to $M$”. That's unusual; usually, when a relation is written $=$, it's either explicitly defined to be an equivalence relation (with explicit or deducible rules for reflexivity symmetry and transitivity) or implicitly defined as the equivalence induced by the explicitly-given rules.

Giving separate rules for different context forms is equivalent to stating a single context rule and, separately, describing contexts. For example, for the pure lambda calculus, you can have a separate deduction rule for each way to decompose a term syntactically: $$ \frac{M \to N}{M\\,Z \to N\\,Z} \qquad \frac{M \to N}{Z\\,M \to Z\\,N} \qquad \frac{M \to N}{\lambda x.M \to \lambda x.N} $$ or you can have a single deduction rule plus a grammatical presentation of contexts: $$ \frac{M \to N}{C\[M\] \to C\[N\]} \qquad C ::= \[\] \mid C Z \mid Z C \mid \lambda x. C $$ (In both cases, that's in addition to the beta rule.)

Other notions of reduction with more restrictive contexts can be expressed in two ways as well. For example, weak head reduction (which forbids reduction under lambda) can be given as the beta rule plus either $$ \frac{M \to\_H N}{M\\,Z \to\_H N\\,Z} \qquad \frac{M \to\_H N}{Z\\,M \to\_H Z\\,N} $$ or $$ \frac{M \to\_H N}{C\_H\[M\] \to\_H C\_H\[N\]} \qquad C\_H ::= \[\] \mid C\_H Z \mid Z C\_H $$

If you're going to manipulate several different notions of reduction, the presentation in terms of contexts is more compact: there's a single context rule, and its formulation is usually obvious so it can be omitted, all that needs to be stated is the permitted contexts if some syntactically valid contexts disallow reduction.

If you're only ever going to use a single notion of reduction, introducing contexts requires some extra syntactic baggage. But this extra baggage has the advantage of making it clearer what's going on: it makes it easier to see where a reduction is happening in a context and where actual computation is happening. So it's a pedagogical trade-off.
> 6 votes

---
Tags: lambda-calculus, term-rewriting
---