# Question
Title: Temporal logic - mixing AF and AG in CTL formula
Let's look at example `AF(φ1 -> AG(φ2))`.

Does it mean that:

1. In all paths it eventually happens that if φ1 was satisfied, φ2 is satisfied **all along the path (so it basically means φ2 is satisfied in all states in all paths)**

or

2. In all paths it eventually happens that if φ1 was satisfied, φ2 is satisfied **starting when the φ1 satisfaction started**

or

3. Something else?

If 1, then isn't it equivalent to `AF(φ1) -> AG(φ2)`?

If 2, will the G start at the current or at the next iteration?

For example if φ1=p , φ2=q, are both A and B in the language, or just A?

A. q-p-q-**pq**-q-q-q-q-q...

B. q-p-q-**p**-q-q-q-q-q...

# Answer
> 3 votes
> Does it mean that: 1. or 2. or 3.?

Your second interpretation is correct: $\varphi\_1 \rightarrow AG(\varphi\_2)$ is a CTL state formula, and to check whether it is satisfied by a state $s$, the path formula $G(\varphi\_2)$ is evaluated relatively to the paths starting in s.

Therefore, a state $s$ satisfies your formula $AF(\varphi\_1 \rightarrow AG(\varphi\_2))$ iff all paths starting at $s$ eventually reach a state $s'$, such that if $\varphi\_1$ holds in $s'$, then all paths starting at $s'$ satisfy that all states on this path satisfy $\varphi\_2$.

> If 2, will the G start at the current or at the next iteration?

G starts at the current state/iteration. A path satisfies $G\varphi$ iff all states on this path satisfy $\varphi$, including the current state.

> For example if φ1=p , φ2=q, are both A and B in the language, or just A?

I am not sure what you mean by the "language" of a CTL formula. For LTL it makes sense to define the language of a formula, containing the words / label sequences that satisfy the formula. CTL does not reason about linear sequences, but about branching time, so usually for a CTL formula we are interested in the labeled transition systems whose initial states satisfy the formula (alternatively, you can unroll the transition systems and use CTL formulas to reason about languages of infinite, finitely-branching, labeled trees). I assume you meant "language" in this sense, i.e. A and B are meant as sketches of transitions systems or their unrolling, with the left-most state as the initial state.

Then A and B both satisfy the formula: Both have an initial state that is not labeled with $\varphi\_1 = p$. Hence both initial states satisfy the CTL state formula $\varphi\_1 \rightarrow AG(\varphi\_2)$. Therefore, it is true that all paths starting from their initial states eventually (in this case immediately) reach a state that satisfies $\varphi\_1 \rightarrow AG(\varphi\_2)$. Thus, the initial states satisfy $AF(\varphi\_1 \rightarrow AG(\varphi\_2))$.

References: Baier, Christel, and Joost-Pieter Katoen. Principles of model checking. MIT press, 2008.

---
Tags: temporal-logic
---


# Question
Title: Avoiding "side effects" in recursive functions
I am writing a function to find the intersection between two sets.

The non-functional requirements of the assignment include avoiding **"side effects"**.

```
function intersection(a, b) {
  return helper(a, b, []);
}

function helper(a, b, c) {
  if (a.length == 0) {
    return c;
  }

  if (b.contains(a[0])) {
    return helper(a.slice(1, a.length), b, c.concat([a[0]]));
  }

  return helper(a.slice(1, a.length), b, c);
}

```

Would mutating the argument `c` in the above code be considered a side effect?

The specific assignment is written in OCaml, so, though the above example is in an imperative language, I want to stay true to the spirit of functional programming.

Please don't provide any alternate solutions to the problem.

# Answer
> 3 votes
If the `helper` function mutated the object `c` (which `concat` **doesn't** do in JS), then `helper` would have that side effect. But overall your `intersection` function wouldn't have any side effect that I can see, as the c array doesn't exist outside of it.

PS: `concat` returns a new array every time. The original c array is unchanged.

---
Tags: recursion, functional-programming
---


title: Difference between RAM and buffer

text:
# Question
Title: Difference between RAM and buffer
I have searched but didn't get any exact difference between RAM and a buffer. If both are used for temporary storage, then why they are named differently while both having same property?

# Answer
> 3 votes
**Buffer** is a concept. It's a structure used to hold data to keep it "closer" while you're processing it. Like buffering a YouTube video. Many types of memories are used as buffers. RAM is certainly great for holding buffers, but for large data you can also buffer data on a hard drive, or an SSD.

Buffers are mainly used to hold data that is costly to read and write (costly in terms of time, or bandwidth, etc), so you'd rather only read a chunk of it once, work on it, then write it back when you're done. And RAM is a good place to do that, unless your data is huge. As you know, current RAM goes from the hundreds of MiB (smartphones) to dozens of GiB (high end PC).

**RAM** is the specific type of memory. Lots of software uses it to hold buffers, but also to hold its own code, etc.

# Answer
> 2 votes
A buffer is usually used only as temporary storage while something is being transmitted or read. For instance, you might be reading data from a slow-response external storage medium (e.g., a CD) and processing it continuously. In this setting, the first process reads chunks of data from the medium and writes it to the buffer on demand, while the latter reads from the buffer as if it were reading from storage directly. This avoids deadlocks in that the latter process does not need exclusive access to the medium.

In contrast, RAM is simply what is used as main memory for the processes in a general-purpose computer. There might be several buffers not only in RAM but also in other memory units. Saying that RAM is used for "temporary storage" can be rather misleading since "temporary" here actually means "until the process using it is inactive or extinct" (and not "until the data is not needed anymore").

In summary, a buffer is an abstracted concept (and only really exists at the software level); RAM is a concrete type of storage technology.

# Answer
> 2 votes
SSD drives are often used as buffers. You wouldn’t call an SSD drive RAM, would you?

RAM is Random Access Memory. A buffer is a data structure used to optimise the flow of data.

You make a category mistake. You compare things that cannot be compared. It’s like asking why your nose isn’t called Usain Bolt when they are both running.

---
Tags: terminology, computer-architecture, memory-hardware
---


# Question
Title: Brzozowki's algorithm doesn't work for this corner case
I'm a newbee learning DFA minimization. And I found that(strangely) Brzozowki's algorithm cannot give me a minimized DFA on this example:  In this DFA, $S\_0$ and $S\_1$ are nondistinguishable and should be merged after minimization, but they are not. The process of minimization is like this:  I tried to find out why by reading @Hendrik Jan's proof here, Proof of Brzozowski's algorithm for DFA minimization?

However, I find that this case bypasses the proof, because that in the reversed DFA, the initial state $q\_0$ cannot be reached by $q\_0$ using any words (but initial state is always considered reachable and cannot be removed). So did I miss anything, or does Brzozowki's algorithm has any specification for this corner case?

(It bypasses the proof like this: in the second series of reversal-determinization, $S\_0 = \\{q\_1\\}$ and $S\_1 = \\{q\_0, q\_1\\}$, for any $w$, $\delta(q\_0, w)$ in $S\_0$ iff $\delta(q\_0, w)$ in $S1$, so we say $S\_0 = S\_1$, assuming all states can be reached by $\delta(q\_0, w)$, but $\delta(q\_0,w)$ will never be $q\_0$)

the initial DFA I was working on:

# Answer
I have looked into some other corner cases and have a tentative answer: when we are doing the determinization after reversal, there is a corner case where in the DFA before reversal, some states cannot be reached by applying any word to the initial state (two possibilities: the initial state cannot go back to itself or we are adding a state as the new initial state, because when we are doing reversal, there are 2 or more final states). In these cases, two sets are considered the same set if the only differences between them are the "unreachable" states before reversal.

---

**Correction**:

Rici made things clearer as he commented "$S\_0$ is not a final state and $S\_1$ is. So they cannot be merged", since "the merged DFA accepts $\epsilon$. The original one does not. So they are not equivalent".

I finally find out my issue. Actually the example I gave above is my "DIY" version trying to make it simpler. And the initial one that I didn't get right is updated in the question. I found out that I used the approach mentioned in Udacity course to do the minimization using Brzozowki's algorithm, which is creating a new state as initial state in the reversed NFA, when there are 2 or more final states. And if two sets are different only on the "created" initial states, I treated them as two different ones, which is not true. I shouldn't add a new state at the beginning.

I think we can prove that by reversing the proof process in the link cited in the question.
> 2 votes

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


# Question
Title: DCEL operations on quad-edges, Twin, Next, and Prev
Suppose I have a quad-edge data-structure, and I want to be able to perform the operations of DCEL (`twin`, `next`, `prev`) on the quad-edge data structure. Let the current edge I am operating on be `e`. I know that `e.twin` would simply be `e.rot.rot`. I am just unsure about `next` and `prev`.

(Quad-Edge visualization given below.)

`next` should be equivalent to `Lnext` in the picture. Thus I tried to derive it and got `e.rot.rot.rot.Onext.rot`. `prev` should be equivalent to `Lprev`, which is the twin of `Onext`, i.e. `e.Onext.rot.rot`.

Is this correct? I am using quad-edges to prove properties on half-edges, so I want to make sure I got the basics correct before I proceed.

# Answer
It looks like you took these diagrams from this CMU publication. This publication also refers to the C++ header `cell/edge.hh`, describing basic and derived operations on edges.

So, according to this header, operations `Rot`, `InvRot`, `Sym` and `Onext` are considered basic ones, and all the other operations - derived ones. The DCEL operations `next` and `prev` are equivalent to quad-edge operations `Lnext` and `Lprev`, which are defined in this header as inline functions (I'm dropping the C++ syntax and keeping the meaning):

```
e.Lnext = e.InvRot.Onext.Rot
e.Lprev = e.Onext.Sym

```

So, your formulas look correct, with slightly overused operation `Rot`.
> 0 votes

---
Tags: computational-geometry, doubly-connected-edge-list
---


# Question
Title: All-to-All Broadcast on a Balanced Binary tree
Can somebody please suggest some procedure for All-to-All broadcast on a balanced binary tree?

Assume that only the leaves of the tree contain nodes, and that an exchange of two m-word messages between any two nodes connected by bidirectional channels takes time ts + twmk if the communication channel (or a part of it) is shared by k simultaneous messages.

Should I use Scatter technique on it, i.e, All-to-Personalized Communication?

# Answer
There are 8 processors: P0..P7, each contains one of the messages M0..M7 so

P0: M0, P1:M1, P2:M2, P3:M3, P4:M4, P5:M5, P6:M6, P7:M7

P0, P1, P2, & P3 are on the left subtree and P4, P5, P6, P7 are on the right subtree.

Step1:

All the processes make a copy of the message and left subtree processors exchange the copy with the corresponding processors on the right subtree. Result is that each processor now has two messages as shown below:

P0 & P7: M0, M7

P1 & P6: M1, M6

P2 & P5:M2, M5

P3 & P4:M3, M4

Step2:

Now P3 & P0 would make a copy of their messages and exchange the copy. Pairs of P1, P2 and P4,P7 and P5, P6 would repeat this action. The result is shown below:

P0, P3, P4 & P7: M0, M3, M4, M7

P1, P2, P5 & P6: M1, M2, M5, M6

Step3:

Now P0 & P1, would make a copy of their messages and exchange the copy. Pairs of P2, P3 and P4, P5 and P6, P7 would repeat this action. The result is the final broadcast:

P0, P1, P2, P3, P4, P5, P6, P7 would all contain the messages:

M0, M1, M2, M3, M4, M5, M6, M7

Zulfi
> 0 votes

---
Tags: parallel-computing
---


# Question
Title: How do we prove the time complexity of this simple problem in probabilistic inference on a Bayesian network?
Suppose we have a simple Bayesian network with two rows of nodes: $x\_1, x\_2, \ldots, x\_n$ and $y\_1, y\_2, \ldots, y\_n$. Each node $x\_k$ takes a state of either 0 or 1 with equal probability. Each node $y\_k$ takes state 1 with probability $p\_{k,0}$ if $x\_k$ is state 0 and probability $p\_{k,1}$ if $x\_k$ is state 1.

Is exponential time required to compute the probability that all $y\_k$ are 1? Please provide a proof either way.

# Answer
Exponential time is not required for finding the requested probability. In fact, only linear time is needed, as we will see below.

First let's define some additional notation. Let $X = (x\_1, x\_2, \ldots, x\_n)$ and $Y = (y\_1, y\_2, \ldots, y\_n)$ -- that is, two $n$-tuples of our variables. Let $\mathbf{1}$ denote an $n$-tuple of 1s, $ (1, 1, \ldots, 1)$. And let $S\_n$ denote the set of all possible $n$-tuples of $0$ and $1$. In CS literature, the elements of $S\_n$ are sometimes called "strings". If $\sigma$ is one such element, we write $\sigma(k)$ for its $k$th component.

In this new notation, the task is to compute $\Pr(Y = \mathbf{1})$. We can marginalize out the configuration of 0s and 1s on $X$ as follows: $$\Pr(Y = \mathbf{1}) = \sum\_{\sigma \in S\_n} \Pr(Y = \mathbf{1} | X = \sigma) \Pr (X = \sigma).$$

From the prompt we know that each $x\_k$ is 0 or 1 with equal probability, so $\Pr (X = \sigma) = 2^{-n}$ for every $\sigma \in S\_n$. Additionally, for any given $\sigma \in S\_n$, we know that $\Pr(Y = \mathbf{1} | X = \sigma) = \prod\_{k=1}^n p\_{k,\sigma(k)}$, since the probabilities $p\_{k,\sigma(k)}$ are independent. Combining these observations, we obtain $$\Pr(Y = \mathbf{1}) = 2^{-n} \sum\_{\sigma \in S\_n} \prod\_{k=1}^n p\_{k,\sigma(k)}.$$

Our next step is to show that we can factor the left-hand side of this equation as follows: $$\sum\_{\sigma \in S\_n} \prod\_{k=1}^n p\_{k,\sigma(k)} = \prod\_{k=1}^n (p\_{k,0}+p\_{k,1}).$$ We prove this inductively. When $n = 1$, both sides are $p\_{1,0}+p\_{1,1}$, so the base case holds. For the inductive case, we assume the $(n-1)$th case and write the $n$th case as $$(p\_{n,0}+p\_{n,1}) \sum\_{\sigma \in S\_{n-1}} \prod\_{k=1}^{n-1} p\_{k,\sigma(k)} = (p\_{n,0}+p\_{n,1}) \prod\_{k=1}^{n-1} (p\_{k,0}+p\_{k,1}).$$ Both sides simplify to those of the above identity, respectively, so the identity is proved.

This leaves us with the result that $\Pr(Y = \mathbf{1}) = 2^{-n} \prod\_{k=1}^n (p\_{k,0}+p\_{k,1}).$ For a hash table representation, look-up times are $O(1)$ for each $p\_{k,0}$ and $p\_{k,1}$, so we can compute this product with a simple for-loop in a runtime of $O(n)$.
> 5 votes

---
Tags: time-complexity, proof-techniques, probability-theory, bayesian-network
---


title: Singleton in a simple SBM

text:
# Question
Title: Singleton in a simple SBM
I can't work out the solution to the following exercise:

We have $2n$ vertices grouped in $2$ clusters of equal size. The probability of having an edge between $i$ and $j$ is $p$ if $i$ and $j$ are in the same cluster and $q$ otherwise. This is a simple SBM with $2$ clusters. The problem ask to show that if $(p+q) \<\< \log(n)/n $, the probability of having a singleton in the realization of this SBM goes to $1$ has n goes to infinity.

Here $(p+q) \<\< \log(n)/n $ means that $f(n) = p(n) + q(n)$ has a function of $n$ satisfy $\underset{n \rightarrow \infty}\lim \frac{f(n)}{\log(n)/n} = 0$.

I've been trying the following approach. Let $S$ the event we are interested in and for any vertex $i$ let $X\_i$ be the indicator random variable of the event $i$ is singleton. Define $X = \sum\_{i} X\_i$, then $\mathbb{P}(S) = 1 - \mathbb{P} (X = 0)$. Since $X$ is non negative, then $\mathbb{P} (X = 0) \le \frac{\text{Var}\[X\]}{(\mathbb{E}\[X\])^2}$.

In addition, I observe that since $X\_i$ is binary valued, then $\text{Var}\[X\_i\] \le \mathbb{E}\[X\_i^2\] = \mathbb{E}\[X\_i\]$. So

$$\text{Var}\[X\] \le \mathbb{E}\[X\] + \sum\_{i}\sum\_{j \ne i}\text{Cov}\[X\_i, X\_j\]$$

Computing all the terms I get:

$$\mathbb{E}\[X\] = 2n(1-p)^{n-1}(1-q)^{n}$$ $$\sum\_{i}\sum\_{j \ne i}\text{Cov}\[X\_i, X\_j\] = n^2q(1-p)^{2n-2}(1-q)^{2n-1} + n(n-1)p(1-p)^{2n-3}(1-q)^{2n} \le n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)$$

For the convariances, I've split the cases when $i$ and $j$ are in the same cluster and when $i$ and $j$ are in different clusters.

All in all, I get: $$\frac{\text{Var}\[X\]}{(\mathbb{E}\[X\])^2} \le \frac{2n(1-p)^{n-1}(1-q)^{n} + n^2(1-p)^{2n-3}(1-q)^{2n-1}(p + q)}{4n^2(1-p)^{2n-2}(1-q)^{2n}}$$

This term doesn't look quite right for what I'm supposed to prove, does it?

# Answer
This answer shows an approach to the problem in the question.

(**Threshold of isolated vertices**) Let $G(n,p)$ be a random graph with $n$ vertices and each edge is present with probability $p$ independently. Suppose that $p\le c{\log n}/n$ for some constant $c$. Then the possibility of the appearance of at least one isolated vertex in $G(n, p)$ goes to 1 when $n$ goes to infinity.

Assume the above proposition on the threshold of isolated vertices holds. Applying it to the case of $G(2n, p+q)$ where $p+q\le c \log (2n)/2n$, we know the appearance of at least one isolated vertex goes to 1 when $2n$ goes to infinity.

Since the random graph in the question has less edges than the random graph above, the appearance of at least one isolated vertex in the random graph in the question also goes to 1 when $n$ goes to infinity. (This loose argument can be made rigorous.)

If you prefer not to use that proposition, you can transplant its proof to fit the current problem. It should not be hard to find a proof for that proposition since it is a classic result in the introductory theory of random graphs.
> 0 votes

---
Tags: probabilistic-algorithms, random-graphs
---


title: How Symbolic Execution Works

text:
# Question
Title: How Symbolic Execution Works
From reading (1) below, it seems they have implemented an abstraction layer on top of the code that does what the code already does to some degree. They built an `Expression` class for symbolic integer manipulation, and they replace any native integer calls with these in their symbolic execution.

Wondering what it takes to do symbolic execution, at a high level. Not sure if you need to create your own entire abstraction on top of every type of object in the language, or what needs to happen. I'm not quite following the paper, but then in (2) it seems they do some more abstraction. There's not much else in terms of description there. Another paper in (3) says to create symbolic expressions as well. But at some point it seems like you are going to end up recreating the whole program, like a Virtual Machine sort of thing, which at that point it seems like you might as well run the original source code. Not sure what I'm missing in this interpretation.

In (4) they describe some more. They mention a symbolic path constraint PC, a first order quantifier free formula over symbolic expressions. Wondering how exactly this accumulates constraints. This seems like the core of it. Not much more is said there though.

The questions are:

1. How does symbolic execution work (at a high level)? If you need to really create a full model of the system (types, datatypes, operations, etc.) to "pretend" execute. How it keeps track of, and assigns, the symbolic execution constraints to the path constraint.
2. It seems that by using these symbolic objects you would inevitably have to use the heap/memory of the program (e.g. the `Expression` object is messing with the heap, etc.). It seems like this theoretically interferes with the proof / model checking.
3. Where is the boundary is between creating a clone of the program and creating a symbolic representation of it? I feel like I'm missing something here.
4. How does it decides which *values* to use when calling a method or doing some assignment of some sort? I keep imagining they would end up doing essentially Unit Tests (generating random variations of input), but not sure. Basically, at a high level, how does the input selection/generation works?

---

> (1) **6.1 Instrumentation**
>
> Conceptually, the instrumentation proceeds in two steps. First, the integer fields and operations are instrumented. The declared type of integer fields of input objects is changed to `Expression`, which is a library class we provide to support manipulation of symbolic integer expressions. A type analysis is used to determine which integer variables have their declared types changed to `Expression`. Operations involving these variables are replaced with method calls that implement “equivalent” operations that manipulate objects of type `Expression`.
>
> (2) Second, the field accesses are instrumented. Field reads are replaced by `get` methods that return a value based on whether the field is initialized or not (get methods implement the lazy initialization, as described in Section 4). Field updates are replaced by `set` methods which update the field’s value. The `get` and `set` methods for a field also set a flag to indicate that the field is initialized.
>
> (3) The key idea behind symbolic execution \[35\] is to use as input values symbolic values instead of actual data, and to represent values of program variables as symbolic expressions.
>
> (4) Symbolic execution maintains a symbolic state, which maps variables to symbolic expressions, and a symbolic path constraint PC, a first order quantifier free formula over symbolic expressions. PC accumulates constraints on the inputs that trigger the execution to follow the associated path. At every conditional statement `if (e) S1 else S2`, PC is updated with conditions on the inputs to choose between alternative paths. A fresh path condition PC' is created and initialized to PC ∧ ¬σ(e) (“else” branch) and PC is updated to PC ∧ σ(e) (“then” branch), where σ(e) denotes the symbolic predicate obtained by evaluating e in symbolic state σ. Note that unlike in concrete execution, both branches can be taken, resulting in two execution paths. If any of PC or PC0 becomes un-satisfiable, symbolic execution terminates along the corresponding path. Satisfiability is checked with a constraint solver.

See: Generalized Symbolic Execution for Model Checking and Testing

# Answer
> 4 votes
When you say "But at some point it seems like you are going to end up recreating the whole program, like a Virtual Machine sort of thing" --\> you are right. Symbolic execution does indeed try to recreate all the paths of the program (as much as the resources allow). However, this: " ... it seems like you might as well run the original source code." is not correct. When you run an actual program, only one control flow path is executed and it can very well give you an idea of the things happening or any bugs occurring in that control flow path of the program, but you do not know anything about the rest of the program. What if some rare input drives the program along with a path which is buggy? Your testing process will never be able to find it out if all you have is regular, non-rare input driven tests. What symbolic execution does is that it tracks all the paths of the code that are feasible (executable). A SE tool will fork two states of the program whenever it comes across a conditional construct, one with a 'true' branch and another with a 'false' branch. So, visualize it as a tree where every node is a conditional juncture from where a concrete execution will choose a single path from the multiple paths that may emanate from that node. The symbolic execution tool, however, will keep track of all the options by forming different path conditions along the respective paths. To check the feasibility of a path, the tool presents the path constraints collected so far to a constraint solver.

To answer your questions:

1. If you read this whole answer, you may get an idea of how symbolic execution works. It assumes a set of symbolic values for some user-specified variables instead of the concrete ones and whenever an expression is encountered on a path which is concerned with that symbolic variable, a symbolic expression is created in the state of the program and that must be used further along the path. For instance, an instruction x = x+y is modeled as sym\_x = sym\_x+sym\_y in the state of the program which changes after the "pretend" execution of an instruction. A state captures the state of the symbolic variables and the path condition seen so far.
2. Yes, symbolic execution uses the system's memory especially in cases where the tool has to model the environment in which the program executes. See this.
3. I am not sure if I understand what you mean by 'clone' of the program. Symbolic execution does no cloning business. It is a systematic software testing process which lets you find those rare inputs under which the program may crash. It is true that instead of executing the program with concrete inputs, it "executes" it with symbolic ones and keeps track of all the paths by maintaining the set of constraints along each path.
4. The inputs which you want to make as symbolic, you specify in the tool using their syntax. For example, SPF lets you specify which functions are to be executed as symbolic and which parameters are to made symbolic using this syntax: symbolic.method=Example.run(sym#sym) in the case where 'run' is a method in class Example which takes two parameters which you want to treat as symbolic. A symbolic execution tool creates a place-holder for each symbolic variable and uses it in the assignments and expressions instead of concrete value. At the end of each path of the program, you have a set of constraints which you can feed to a constraint solver to get any two of the following results: 1. UNSAT which shows that the constraints can not be satisfied and thus, the path is not feasible. 2. SAT, in which case a concrete value is assigned to each symbolic one such that the constraints are satisfied. This is the input which drives the program through that particular path. So, you see: you did not have to find the inputs manually so as to drive the program towards any particular path. The tool automatically found those rare inputs for you. Also, this process of input generation is not at all random. It is systematic and exercises every path.

---
Tags: algorithms
---


title: When are two CFG's different?

text:
# Question
Title: When are two CFG's different?
If two CFG's differ only in what names they use for their non-terminals, are they different?

For example, are these CFG's different:
$$\begin{align\*} S &\to A \\ A &\to a \end{align\*}$$ and $$\begin{align\*} S &\to B \\ B &\to a \end{align\*}$$

# Answer
> 3 votes
Two grammars $G\_1 = \langle \Sigma, V\_1, S\_1, P\_1 \rangle$ and $G\_2 = \langle \Sigma, V\_2, S\_2, P\_2 \rangle$ are

* *weakly equivalent* if $L(G\_1) = L\_(G\_2)$
* *strongly equivalent* if $L(G\_1) = L\_(G\_2)$ and for every string $w$ in the language, the minimal left-most derivations of $w$ in $G\_1$ and the minimal left-most derivations of $w$ in $G\_2$ are exactly the same in number, and can be put in one-to-one corresponce (note that the number of derivation trees must be the same in number if the grammars are ambiguous, i.e. they must be ambiguous "in the same way")

Example:

$G\_1 = S \to A; A \to 1B; A\to 1; B\to 0A$; we have $L(G\_1) = \\{ (10)^\*1 \\}$

$G\_2 = S \to B; B \to A1; B\to 1; A\to B0$; we have $L(G\_2) = \\{ 1(01)^\* \\}$

* *isomorphic* if there is a bijection $\phi : V\_1 \to V\_2$ such that $\phi(S\_1) = S\_2$ and $\phi(P\_1) = P\_2$ (after extending $\phi$ to productions and set of productions in the natural way).

Note that weakly equivalence is undecidable, while strongly equivalence (and ismorphism) are decidable.

As a final remark I think that - in most formal language contexts - it would be fine to say that the grammars in your question *are the same grammar* :-)

# Answer
> 1 votes
**Different, but equivalent** (in a certain sense).

Usually a CFG is defined as a tuple $(N, T, S, P)$ where $N$ and $T$ are the sets of non-terminals, $S \in N$, and $P$ is the set of productions. Using this definition, the two grammars would be necessarily different since you have different sets of non-terminals (and different productions).

Nevertheless, you could also say the two CFGs are *equivalent* in the sense that the two are equal up to renaming the non-terminals. This is a stronger equivalence than, for instance, simply generating the same language.

As an aside, note an equivalence based on renaming the terminal symbols (or even both terminals and non-terminals) is also conceivable.

# Answer
> 1 votes
Formally, the two grammars are different. On the other hand, they obviously generate the same language and thus they are *equivalent*.

But beyond equivalence they are also structurally equal. This *equality up to renaming symbols* is probably best captured by the concept of *isomorphism*.

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


# Question
Title: Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM
Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. But can we ensure that $N$ has the following form?

* $N$ consists of (i) a read-only input tape, (ii) a work tape that is log-space with respect to $|\langle A, B\rangle|$, and (iii) a one-way, write-only, polynomial-time output tape.

This really comes down to showing that this kind of TM can construct DFAs for $L(A) \cup L(B)$ and $L(A) \cap L(B)$. But it's not clear to me how this would work.

Any help is appreciated.

# Answer
Don't construct machines for $L(A)\cap L(B)$ and $L(A)\cup L(B)$. Use a variant of the product construction for those two automata to directly construct an automaton for symmetric difference. Because of the way the product construction works, you don't need to store much intermediate data at all: essentially the algorithm is just a couple of `for` loops and, with at most $n$ states to loop through, you only need $\log n$ bits to hold the value of the loop counter.
> 1 votes

---
Tags: complexity-theory, regular-languages, space-complexity
---


# Question
Title: Clarification on NP-hardness and hardness of approximation results for set cover?
I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.

I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover.

Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m \< n$ or $m \> n$?

# Answer
> 2 votes
When you have a result like "It is NP-hard to approximate X within ..." or say "X is NP-complete", it means that there is an infinite family of instances of X that are hard. This is what worst case intractability means.

In your example, the hardness of approximation result holds for the set cover problem, meaning that there is an infinite family of instances of set cover that are hard to approximate.

At this point, you might put further constraints on a problem in the form of "suppose every set satisfies this property" or whatever, but this is then a different problem, i.e., you are narrowing down on the instances that you care about. If you have a statement that says "set cover with your favorite property is NP-hard to approximate", it means that there is (still!) an infinite family of instances of this problem that remain hard.

---
Tags: np-hard, approximation, set-cover
---


# Question
Title: Explanation for the proof "Every 2-thread consensus protocol has a bivalent initial state"
From the book 'the art of multiprocessor programming':

> A protocol state is bivalent if the decision value is not yet fixed: there is some execution starting from that state in which the threads decide 0, and one in which they decide 1.
>
> Lemma 5.1.1. Every 2-thread consensus protocol has a bivalent initial state. Proof: Consider the initial state where A has input 0 and B has input 1. If A finishes the protocol before B takes a step, then A must decide 0, because it must decide some thread’s input, and 0 is the only input it has seen (it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0).
>
> Symmetrically, if B finishes the protocol before A takes a step, then B must decide 1, because it must decide some thread’s input, and 1 is the only input it has seen. It follows that the initial state where A has input 0 and B has input 1 is bivalent.

I don't understand why it can only output the input it has seen already. And for A why "it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0)".

# Answer
> 1 votes
> I don't understand why it can only output the input it has seen already.

The reason is simple. Just too simple. Because it cannot output any input that it has not seen deterministically, where the input could take one of two (or more) values randomly.

Let me use an example. Suppose you and I are two travellers (threads) travelling together. Each of us will be given one of two kind of maps to be used for travel, map 0 and map 1 separately. We two might be given the same kind of map. Or each of us might be given a different kind of map. Initially, each of us do not know what kind of map is given to the other one, since we are two separate travellers that have not communicated yet. Now suppose you have to decide which map should be used before you can make a move to know which map is given to me. What can you do deterministically? Since you do not know which map is given to me, the only deterministic decision you can make is to use whichever map given to you.

Had you have a chance to know which map was given to me, you could make a different decision deterministically. However, that is not the current situation.

> for A why "it cannot decide 1 because it has no way of distinguishing this state from the one in which B has input 0)".

That is because A does not know whether 1 or 0 is given to B. Even though the collective state of A and B might be observable/known to a third party, it is not known to A since, at the initial state, by definition, A has not made a move to access any shared object, i.e., A does not know the input to B since it might be 0 and it might be 1.

---

You will realize, sooner or later, wow, this is just too easy and too simple to understand. It might be fair to say that the lemma 5.1.1 is just too obvious or intuitive to use more than one sentence to explain.

On the other hand, there are lot of pitfalls and counterintuitive phenomenons in multiprocessor programming. Be careful and vigilant.

---
Tags: algorithms, protocols
---


# Question
Title: Djikstra's algorithm to compute shortest paths using at least k edges
I have a graph `G = (V, E)` where each edge is bidirectional with positive weight. I want to find the shortest path from vertex `s` to vertex `t` using *at least* `k` edges but less than 20. No vertex may be repeated in a path.

I am aware of this problem: Dijkstra's algorithm to compute shortest paths using k edges?

That problem wants to find the shortest paths using *at most* `k` edges.

My current idea is to create the product graph via `V' = V x {0, 1, 2, ..., 20}` and then ignore any shortest paths from `(s, 0)` to `(t, n)` where `n < k`. However, because the product construction essentially duplicates nodes, I am not aware of a way to ignore duplicate vertices in the path-finding algorithm.

P.S. If `k` were very large, say, `k = |V|`, wouldn't this be the Hamiltonian path problem and therefore NP-complete?

# Answer
Unfortunately, your problem is NP Complete, since you require that no vertex will be visited twice.

Consider we had a polynomial time solution for some $k$. For clarification; given an undirected graph $G=(V,E)$ and two vertices $s,t$, we can find a shortest path from $s$ to $t$ of length $\geq k$ in polynomial time. Then, by extension we can solve in polynomial time for $k=n-1$ and thus find a path that visits eeach vertex in $V$ exactly once. In other words, we can "solve" Hamiltonian Path.

If you know in advance that $k \leq 20$ then you can exhaustive search all paths of length at most 20, and therefore solve for small $k$.

An exhaustive search, at worst, is to search every vertex order starting from $s$ that ends in $t$ (corresponding to existing edges), so in total you will search: $$(n-1)(n-2)(n-3)...(n-20) = O(n^{20})$$
> 2 votes

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


# Question
Title: How to divide a line of numbers into N groups such that the sums of each group are closest to their mean using dynamic programming?
I have M numbers arranged into a line. I need to divide the line into N groups without changing numbers order such that the sums of the numbers of each group are closest to the mean of these sums by absolute differences.

Example:

Numbers: 1 2 3 4 5 6 7 8 9 10, need to divide into 3 groups.
Let's say we want to minimize sum of absolute differences (SAD).
Groups: (1) 1 2 3 4 5 6 (sum = 21); (2) 7 8 (sum = 15); (3) 9 10 (sum = 19)
Mean = (21+15+19)/3 = 18.33, SAD = 21-18.33 + 18.33-15 + 19-18.33 = 6.67 \<- That's what we want to minimize.

The question is how to solve it using dynamic programming?

---

The original question - https://stackoverflow.com/questions/9275280

# Answer
Fortunately you can calculate the group average that you are aiming for (sum of numbers, divided by the number of groups). In your case, you want the groups close to 18 1/3.

So using dynamic programming, you solve "How do I split the first m numbers into n groups, minimizing abs (sum of numbers in group - 18 1/3)", for 0 ≤ m ≤ M, and for 1 ≤ n ≤ N. You solve this by putting 0 ≤ k ≤ m items in the last group, calculating the penalty for the last group and adding the solution for n-1 groups made from the first m-k items, picking the best choice.

It feels a bit weird, because the solutions you find on the way are awfully bad. Splitting the first 0 numbers for example into 3 groups creates 3 empty groups, with a total sum of 3 * (18 1/3) = 55, but it works. What you find for N groups from M numbers is optimal.

This works easily on O (M^2 N). You can do this faster by first finding a reasonably good solution, and then excluding everything that isn't as good as the best solution.

Example: First, make each group as large as possible without the first n groups exceeding n * 18 1/3, that is (1 2 3 4 5) (6 7 8) (9 10) with penalties 3 1/3, 2 2/3, 2/3, total 6 2/3. Now we only care for 1 group with a penalty ≤ 6 2/3, then for 2 groups with a penalty ≤ 6 2/3 etc.

But also, if the remaining M-m items that need to go into N-n groups have a sum of S, they must have a penalty of at least abs (S - 18 2/3 * (N - n)), so the penalty for the first n groups plus this extra penalty must be ≤ 6 2/3. This will help if you have thousands of items.
> 0 votes

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


title: Modified Knapsack Problem

text:
# Question
Title: Modified Knapsack Problem
I have a problem with the following optimisation problem:

In total there are $n=100$ items. A quality level $L\_i \in \\{0,1,2,3,4,5\\} $ must be selected for each of these items. The greater $L\_i$ is, the greater weight $w\_i$ and its value $v\_i$, starting with $w\_i=0$ and $v\_i=0$ for $L\_i=0$. Furthermore, $w\_i$ depends on both item $n$ and its quality level $L\_i$ and is calculated using function $w\_i = w(n,L\_i)$. $v\_i$ depends on the total set of items and their selected quality levels $L\_0 \dots L\_n$ and is calculated using the relatively cost-intensive function $V$.

The question now is, what are the optimal quality levels improvements for each item, given random initital quality levels for the items and a capacity $W$? An important restriction is that a quality level can only be increased by one level in total. Each item must be selected exactly once (quality level $L=0$ is effectively the same as if the corresponding item had not been selected).

I see a difficulty in the fact that an items's value v depends on all other items. Can the problem still be solved optimally with an acceptable time complexity, or would it be necessary to use other algorithms, if so which ones? Maybe greedy algorithms?

Thank you very much for your help!

# Answer
You can't. If the function $V$ (for computing the $v\_i$'s) is arbitrary, in the worst case you will need to try all possible combinations of quality levels -- there is no algorithm faster in the worst case. That takes exponential time.

To do better, we need to know something about the function $V$: e.g., about its structure or proeprties.
> 1 votes

---
Tags: time-complexity, optimization, greedy-algorithms, knapsack-problems, integer-programming
---


# Question
Title: Implementing a symbol table with a hash table and a stack
I was in class today, in a Language Translations course, thinking about the best way to write a symbol table for a compiler. My professor showed us a hash-table with linked-lists connecting different levels of "blocks", which are usually { } curly brackets in languages such as C.

My thought was, what's wrong with using stacks instead?

For example, here's some code:

```
int x = 5;
float y = 3;
{
    // stuff
    int x = 100;
}

```

Would I not be able to start off, hashing x, pushing it onto a stack struct as

```
struct symbol_def{
    char * type;
    val_type value;
}

```

I don't know how to do a dynamic type for the value (if the value is even needed in there).

When the second x comes in:

```
int x = 100;

```

Then we just again hash x, push onto the stack.

At any given moment, the top of the stacks are the current scope's visibility.

The issue might come with popping however. How do we pop off the right things? That one I'm not entirely sure about, and could be a fatal flaw of this design.

In theory, this would be a lot of O(1) jobs (hash table lookup, pushing, popping, peeking).

Let me know your thoughts. Maybe I'm missing something here, or maybe this is how it's really done already.

# Answer
A stack of hashtables would be a perfectly fine representation.

A hashtable of stacks wouldn't be a good choice, but a stack of hashtables would work.

When you leave a scope (e.g., the `}` symbol), you need to pop off all of the symbol names defined in that scope. That's easy with a stack of hashtables, but a bit more annoying with a hashtable of stacks.

A natural way to represent a stack is as a linked list, so this might turn out to be equivalent to the solution you've already been presented.
> 1 votes

---
Tags: compilers, hash-tables, stacks
---


# Question
Title: Anonymous Visibility Check in P2P networks
I'm working on a problem for a P2P network for games. The problem is the following: Consider two opponents on a grid, each stores it's own position. Player 1 wants to know if it sees player 2. In other words, if player 2 should send it's positional data to player 1 without revealing it’s position in the process.

The problem is sort of obvious, in order to know if player 2 should send it's data it needs the position of player 1, thus player 1 has to reveal it's position. I'm wondering if anyone knows about a system which does this visibility check anonymously, without revealing the position of players.

Right now I have an algorithm/policy which only reveals if player 1 is above, below, to the left or to the right of player 2 but does not reveal the exact coordinates of player 1 to player 2. It's based on the homomorphic properties of certain cyphers, but this is still a big limitations in certain games, especially first person shooters where knowing the approximate direction of your enemy can be very helpful? Note, I am NOT looking for fully homomorphic cryptography here, only something which can solve this specific problem of checking whether a point is inside of a "visibility field" or not without revealing positional (or visibility field) information.

This question might be a stretch since there probably isn't such an algorithm out there, but I thought I'd ask anyway :)

# Answer
Ok, so after realizing my previous solution didn't work I've put this problem on ice for a while, but now I have one in which I am fairly confident. If you find any obvious flaws, please let me know. This is the first time I'm answering a question, and I'm trying to be as transparent as possible where all my ideas came from so that anyone can find errors easier. Thus my answer will be quite long.

To start with, I've limited it to determining if the distance between two players (two points) is bellow a certain therhold. It can however be extended to a vision field.

My current solution relies on a homographic encryption which can do addition (such as Paillier). To start with I note the expression which I ultimately want to evaluate, which is the distance between two points being within a certain distance: \begin{equation} (x\_a -x\_b)^2 + (y\_a - y\_b)^2 - d \< 0 \end{equation} However, since the distance you want to check will in many cases be very similar for both players, your opponent can make good guesses as to what $d$ is, which means your opponent has access to a boundary on your position (one equation, two unknowns in a 2D environment). Thus we need to add a slight modification to avoid this, and ultimately evaluate the following equation: \begin{equation} r(x\_a -x\_b)^2 + r(y\_a - y\_b)^2 - rd \< 0 \end{equation} The multiplication of $r$ here does not change the truth value of the expression, but it does add one unknown, thus the only constraint we can get is that the unknown point is on a plane, which does not add any new information.

In order to use the additive homographic property of our encryption we need to fully expand this equation: \begin{equation} rx\_a^2 +rx\_b^2 -2rx\_a x\_b + ry\_a^2 + ry\_b^2 -2ry\_a y\_b - rd \< 0 \end{equation} Let us assume that we are player b. We have access to $x\_b$ and $y\_b$ and we are going to be choosing $r$ and $d$. From the equation above it's then obvious that player b needs information about $x\_a$, $y\_a$, $x\_a^2$ and $y\_a^2$, thus player a will now encrypt those values and send them to player b, together with the public key to for the encryption.

Here comes my breakthrough, player b is only able to do addition with the encrypted values we received from player a, thus the terms $rx\_a^2$,$ry\_a^2$,$-2rx\_a x\_b$,$-2rx\_a x\_b$ are impossible for player b to compute. However, if we restrict r to be integers player b can compute $rx\_a^2$ and $ry\_a^2$ by simply adding $x\_a^2$ and $y\_a^2$ to themselves $r$ times. In practice this would be multiplying the encrypted values $r$ times (assuming we use Paillier encryption).

This only leaves $-2rx\_a x\_b$ and $-2rx\_a x\_b$, which we can solve by letting player a do the actual multiplication. If player b sends: \begin{equation} -2rx\_b \end{equation} \begin{equation} -2ry\_b \end{equation} Player a can preform the multiplication. However, we run into the same problem in the beginning, now player a can put a constraint on the position, since we are sending two equations and three unknowns, thus we need to modify what we send to keep our information hidden. Thus player b instead sends: \begin{equation} -2rx\_b + C\_1 \end{equation} \begin{equation} -2ry\_b + C\_2 \end{equation} Where $C\_1$ and $C\_2$ are integers. Since they are integers, and we know they are going to be multiplied by $x\_a$ and $y\_a$ we can do the same trick as before and account for this in our addition of the encrypted values.

Thus the last thing to work out is what to encrypt and send back, which is rather easy. We simply have to account for the added $C\_1$ and $C\_2$ and subtract them. Thus player b sends: \begin{equation} \mathcal{E} (rx\_a^2 +rx\_b^2 + ry\_a^2 + ry\_b^2 - rd - x\_a C\_1 -y\_a C\_2) \end{equation} Where $\mathcal{E}$ stands for "encrypted". There's a note to be made here about speeding up the computation of $\mathcal{E} (rx\_a^2)$ which using a naive approach would require us to do $2r + C\_1 + C\_2$ encryption computations, however this can be sped up considerably by simply adding the newly encrypted sum to itself, thus making the process exponential and reducing the computations down to somewhere above $ log\_2 (r) + log\_2(max(C\_1,C\_2))$, but this is only important for the implementation. Later I will represent this type of multiplication with $\times$.

Let's now look at all the transactions which take place:

* Player b sends a request to Player a (this step can be skipped if the transactions are continuous)
* Player a sends $\mathcal{E}(x\_a)$, $\mathcal{E}(y\_a)$, $\mathcal{E}(x\_a^2)$, $\mathcal{E}(y\_a^2)$ and $\mathcal{E}$.
* Player b sends:

+ $r \times (\mathcal{E}(x\_a^2) \mathcal{E}(y\_a^2))\mathcal{E}(rx\_b^2) \mathcal{E}(ry\_b^2)\mathcal{E}(-rd) C\_1 \times \mathcal{E}(-x\_a) C\_2 \times \mathcal{E}(-y\_a)$
    + $-2rx\_b + C\_1$
    + $-2ry\_b + C\_2$
* Player a then:

+ Decrypts the encrypted part to get $\[rx\_a^2 +x\_b^2 + ry\_a^2 + ry\_b^2 - rd - x\_a C\_1 -y\_a C\_2\]$
    + Multiplies $-2rx\_b + C\_1$ and $-2ry\_b + C\_2$ with $x\_a$ and $y\_a$ respectively.
    + Adds this all together to get: \begin{equation} \[rx\_a^2 +rx\_b^2 + ry\_a^2 + ry\_b^2 - rd - x\_a C\_1 -y\_a C\_2\] + x\_a\[-2r x\_b + C\_1\] + y\_a\[-2r y\_b + C\_2\] \end{equation} which Equates to: \begin{equation} rx\_a^2 +rx\_b^2 -2rx\_a x\_b + ry\_a^2 + ry\_b^2 -2ry\_a y\_b - rd \end{equation}
    + Player a checks if this value is smaller than 0, if so player a sends it's position to player b, if not it sends a "false" message.

I hope this answer was clear, or at least understandable. When I used the \[ \] brackets it was only to notate what came as one number, so from the perspective of player a, everything inside of a bracket is just one number.

A thing to note here is that it's player a can still cheat by just refusing to send the position ( and Player b could for example send vision checks where he shouldn't), but this sort of cheating can be caught by keeping a log of all player positions (and vision checks) throughout the game (or a subset of them to save memory) which when the game is over, or enough time has passed, can be used to verify that neither player was cheating. If a player disconnects suddenly they can just be asked to send their log when they go online again, thus sudden disconnects is not a problem either.
> 3 votes

---
Tags: algorithms, computer-networks, cryptography
---


# Question
Title: Why is finding minimum number of comparisons to sort $n$ elements so difficult?
In *The Art of Computer Programming* 2nd Ed, Vol 3, Section 5.3.1 then discuss a function $S(n)$ which is define as:

> $S(n)$ : The minimum number of comparisons that suffice to sort $n$ elements.

Further, the book regards $\lceil \lg n! \rceil$ as the *information theoretic lower bound* for $S(n)$.

Using *merge insertion* they also upper bound the number of comparisons by $F(n)$ where

$$F(n) = \sum\_{k = 1}^{n} \lceil \lg \tfrac{3}{4} k \rceil$$

So you can get the bound $\lceil \lg n! \rceil \leq S(n) \leq F(n)$, and for any values $n$ where $\lceil \lg n! \rceil = F(n)$ you can find the exact value of $S(n)$.

My questions are:

1. Why does $S(n)$ not always match the *information theoretic lower bound* $\lceil \lg n! \rceil$? It seems like if this is all the bits of information we should need, that this is all the comparisons we would need. Why do they differ?
2. Why is $S(n)$ so difficult to compute? It's discussed in the book some but the reasons are still unclear to me. Do you have to brute force and create every possible decision tree for a given $n$ and determine the longest path? Is there not a more efficient way? It seems that $S(n)$ has only been exactly computed for $n \leq 22$ (See A036604 here).

# Answer
Let's say the size of the array is such that there are $2^{k-1} \< x ≤ 2^k$ possible permutations, so the theoretical lower bound to sort this array is k comparisons.

Any comparison divides the set of possible permutations in two subsets, consistent with each outcome of the comparison. You'd first need a comparison that splits the set of all possible permutations into two subsets, each of size at most $2^{k-1}$. And each subset you need to split into two subsets of size at most $2^{k-2}$ etc. If these subsets don't have the same size, then after j comparisons the size of the largest subset could exceed $2^{k-j}$, and you lost.
> 3 votes

---
Tags: sorting, lower-bounds, comparison
---


# Question
Title: Finding combinations of variables that can take value of -1/0/1 that produce sum of 0 with added constraint
I have 64 variables that can either take a value of -1, 0, or 1 and I am interested in finding all possible combinations of variables such that I have n variables in each the positive and negative state.

Does anyone know what the best way would be to calculate the full set of combination values that fits this constraint?

Right now I just implemented a simple counting algorithm, but that will take forever since I have to test if there are n positive and negative variables at 3^64 levels, and that is before I even start to evaluate the weighting term I am actually interested in.

# Answer
There will be ${64 \choose n} \cdot {64-n \choose n}$ such combinations, since there are ${64 \choose n}$ ways to choose a subset of $n$ of the 64 variables to be -1, and then ${64-n \choose n}$ ways to choose a subset of $n$ of the $64-n$ remaining variables to be 1. Equivalently, this is ${64! \over n!^2 (64-2n)!}$.

You probably won't want to explicitly generate all of those combinations, as it would take exponentially long to do so (as there are exponentially many such combinations).

But if you really wanted to explicitly enumerate all combinations, this formula also highlights the way to do that. First, enumerate all possible ways to choose $n$ of the 64 variables; there are standard algorithms for how to do that (e.g., https://stackoverflow.com/q/127704/781723, https://en.wikipedia.org/wiki/Combination#Enumerating\_k-combinations). Then, for each such, enumerate all possible ways to choose $n$ of the remaining $64-n$ variables (again, using the same algorithm). That will give you all ways to choose a combination of the sort you desire.

Still, any time you are enumerating exponentially many possibilities and then doing something to each, you should check whether maybe there's a better way to achieve your ultimate goal without enumerating all of them. If you want to find the combination that minimizes some cost function, there might be a better way to do that, depending on the cost function.
> 1 votes

---
Tags: algorithms, combinatorics, sets, counting
---


# Question
Title: Construct a decidable set $B$ such that $B \neq A_w$ for any $w \in \Sigma^\star$
I've been stuck on this problem for a while. Any hints would be appreciated!

Let $A \subseteq \Sigma^\star$ be decidable. Given $w \in \Sigma^\star$, define $$A\_w = \\{x \in \Sigma^\star\\:|\\: \langle x, w \rangle \in A\\}.$$ Construct a decidable set $B$ such that $B \neq A\_w$ for any $w \in \Sigma^\star$.

# Answer
Here is a hint. Let $w\in B$ if $w\not\in A\_w$ and let $w\not\in B$ if $w\in A\_w$.
> 0 votes

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


# Question
Title: Algorithm for identifying correct subset
My raw data is composite, but for simplicity sake let's say they consist of three elements. One might consider a sample set thusly.

```
[A,a,1]
[A,b,1]
[B,b,1]
[B,b,2]
[C,b,3]
[A,c,3]

```

I need to create a subset that satisfy two key criteria.

* All combinations of the two last columns is represented (lower case and numeric)
* All upper case (first column) is represented at least once.

... in as few rows as possible. The data is not evenly distributed, meaning that e.g 80 percent of the rows in the input data may have b,1. If that was the case, it would be wasteful to include A,b,1 row, because I would have to include A,a,1 as well in order to make sure that a,1 combination is represented.

Though large data, the data is in memory. Accessing and iterating is relatively cheap. The data is static and may be processed over multiple passes .

Language is C#.

I'm not too happy about the title of this question, so if there is any key term that better describes this problem, feel free to comment/edit.

# Answer
You can solve this by looking for a maximum cardinality matching in a bipartite graph, then covering remaining vertices arbitrarily.

Make a bipartite graph:

* In the left part of the graph, make a vertex for every capital letter.
* In the right part of the graph, make a vertex for every combination of lowercase letter and number.
* For each record, make an edge (which necessarily goes from a vertex on the left to one on the right) corresponding to the two vertices covered by the record.

Now run an algorithm for finding a maximum cardinality matching in a bipartite graph, such as the Hopcroft-Karp maximum flow algorithm. This picks a subset of edges (records) that together cover the most possible *distinct* combinations of capital letter and (lowercase letter + number). That is, each chosen record hits both a capital letter, and a (lowercase letter + number) pair that are not hit by any other chosen record.

If the matching saturates (touches) every vertex, you have a "perfect" solution! Otherwise, for each remaining vertex, you need to pick a record incident on that vertex -- it doesn't matter which record you pick, because it definitely won't be incident on any untouched vertices on the other side (if it was, then it would have been included in the matching already).
> 2 votes

---
Tags: algorithms
---


# Question
Title: Is the empty problem (or its complement) Karp reducible to any problem in NP?
I'm currently following a course on Complexity Theory, and whilst studying, I came across a rather counterintuitive statement:

If $\textbf{P}=\textbf{NP}$, the following holds:

For every $A \in \textbf{NP}$, there is a $B \in \textbf{NP}$ such that $A \leq B$ (where $\leq$ means Karp reducible).

However, I do not understand how this applies to the empty problem $\emptyset$, and it's complement $\Sigma^\*$, as these only have no-instances and yes-instances, respectively.

Are there other problems in NP such that these two are reducible to them?

# Answer
> 3 votes
**Of course there is.**

Just take any non-trivial language $L$ (i.e., $L \neq \varnothing$ and $L \neq \Sigma^\ast$). Then there are concrete words $x \in L$ and $y \not\in L$.

To reduce $\varnothing$ to $L$, simply map *everything* to $y$. Then the input is in $\varnothing$ (which is false) if and only if $y \in L$ (which is also false). Hence, the reduction is correct.

For $\Sigma^\ast$, do the same but use $x$ instead.

---

As a note: I assume you are puzzled about $A$ being reduced to $B$. Obviously, in the statement you cite $B$ should at the very least be a non-trivial set (and it seems $\textbf{P} = \textbf{NP}$ is redundant, as Tom van der Zanden notes in the comments; in fact, the statement is rather fishy, see David Richerby's answer); note you cannot reduce non-trivial sets to $\varnothing$ or $\Sigma^\ast$ (and you cannot reduce either to one another, as David Richerby points out in the comments).

# Answer
> 1 votes
The statement is basically vacuous. Every language is reducible to itself (the reduction is the identity function), so you can just take $B=A$.

---
Tags: complexity-theory, reductions
---


# Question
Title: Is model checking PSpace-hard *in formula size*?
Sistla/Clarke proved \[SC82\] that the LTL model-checking problem is PSpace-complete. Sometimes people write that this problem is "PSpace-hard **in $|\phi|$**" (e.g. \[LP85\]). What does this mean formally?

How to prove that a decision problem that has several parameters (here, $\phi$ and system) is PSpace-hard in one of the parameters? I guess we would need to poly-time reduce some PSpace-complete problem to our problem *with the unintereseting parameter being fixed*, while the interesting parameter can vary.

But the original proof of Sistla/Clarke \[Lemma 4.4, SC82\] does not do the thing above! In their proof, both parameters of the resulting LTL model-checking problem instance depend on $n$, where $n$ is the TM tape bound. Is there a proof that fixes one of the parameters?

# Answer
You are certainly right that the level of rigor found in old papers making such claims can be a bit low at times when viewed from today's perspective.

The claim is correct anyway, even if it does not follow from Sistla/Clarke's proof. The reason is that LTL satisfiability checking is also PSPACE-complete. You can see satisfiability checking as a special case of model checking.

More formally, you want to prove the following: There exists a fixed model such that given an LTL formula, checking if the formula holds on the model is PSPACE-hard. Now the satisfiability checking problem does not restrict the number of atomic propositions, so a fixed model does not do the trick. However, S. Demri and P. Schnoebelen show in the paper "The complexity of propositional linear temporal logics in simple cases" (Inf. Comput., 174(1):84–103, 2002) that the satisfiability problem is hard even if we only have a single atomic proposition.
> 5 votes

---
Tags: complexity-theory, model-checking, linear-temporal-logic, parameterized-complexity
---


# Question
Title: Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB?
I know that synchronization is important in the OS, but why do we need a separate topic synchronization and concurrency in the DBMS? The OS concentrates on program synchronization while the DBMS concentrates on data synchronization. Why can't the OS take responsibility for data synchronization?

# Answer
> 2 votes
Program synchronization is a very different beast compared to transaction synchronization. The objective of your Operating System is to have multiple applications working in sync to maximize the utilization of your CPU. A couple of reasons I can think of as to why OS' are not equipped to handle transaction synchronization are as follows.

1. Your DBMS is a self contained application. Allowing a 3rd party software (i.e. your OS which may be open source or owned by some corporation) direct access to the data is a no-go for business.
2. There maybe multiple DBMS' with different architectures (relational, non-relational, written in different languages, using different standards) installed on a single Operating System. OS designers usually ignore deadlock recovery because it becomes too complicated for them to handle efficiently. Accounting for applications across the board will mean worse performance issues for the OS, ultimately defeating the purpose of having one in the first place.

---
Tags: operating-systems, databases, synchronization, database-concurrency
---


title: Crafting a Context Free Grammar

text:
# Question
Title: Crafting a Context Free Grammar
I'm trying to figure out the intuition on creating a CFG in my head. I understand the idea of Grammar rules akin to "onions" with various layers throughout. For example, I was working on a problem earlier where I was to construct a CFG of $a^ib^jc^k$ with $i \ne j$ OR $j \ne k$. Obviously I separated the problem into two parts, $i$ not being $j$ and the other part being $j$ not being $k$. Taking the left part into account I wrote out the following:

$$\begin{align\*} S &\to aSbTc \mid aS \mid bT \\ T &\to bTc \mid bc \\ D &\to cD \end{align\*}$$ Am I correct in this for $i$ not being $j$ or is there something in my head thats wrong in thinking through this?

# Answer
The rules like "onions" with various layers that you describe in your question can be thought of as a *build order* for how you will construct a string -- eg. "first I will build this part of the string, and then I will build this other part" or "I need to build these two parts at the same time in order to ensure that they are synchronized".

> A good general strategy for constructing a context free grammar is to determine this build order and then have a production rule that represents each stage and/or each possibility of your build order.
>
> You should be able to point to each nonterminal and explain the "meaning" or type of string that nonterminal is trying to construct.

For the example of $a^ib^jc^k$ with $i \ne j$, one possible build order could be:

1. Produce $a$'s and $b$'s in equal number (this is like $a^ib^j$ where $i = j$. Try writing a grammar for this first.)
2. At some point, the number of $a$'s and $b$'s have to diverge, so pick either $a$ or $b$ and produce an unbounded number of that character (this is like $a^ib^j$ where $i \ne j$. Try taking the grammar you have from 1) and adding production rules to be able to do this.)
3. Now just produce an unbounded number of $c$'s at the end. (this is the desired $a^ib^jc^k$ with $i \ne j$.)

---

A good question to ask yourself:

Why do we have to have more than one production rule to construct $a^ib^j$ where $i \ne j$? If I want the number of $a$'s and $b$'s to be equal, it makes sense that I'd have to build them at the same time, but if I want $i \ne j$, why ***can't*** I just do something like:

$S \rightarrow aS\ |\ Sb\ |\ \varepsilon$

which says "produce some number of $a$'s and then produce some number of $b$'s"?
> 1 votes

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


# Question
Title: Stacking things of different thickness to approximate desired thickness
I have $N$ objects of different thickness. Is there an algorithm to determine which of those objects should be stacked on each other to get as near to a desired thickness as possible? (I don't want to numerically check every combination.)

# Answer
This is as hard as the subset sum problem. The subset problem asks "is there a way to get exactly the desired thickness?". Obviously, if we could solve your problem, we could also solve the subset sum problem. Unfortunately, the subset sum problem is NP-hard, so your problem will be too.

In practice you can try using an approximation algorithm for the subset sum problem, e.g., by rounding to the nearest integer (or to the nearest multiple of $1/k$ for some $k$) and then applying the dynamic programming algorithm for subset sum. See, e.g., https://en.wikipedia.org/wiki/Subset\_sum\_problem
> 2 votes

---
Tags: algorithms
---


# Question
Title: Operations making non-context-free languages regular
1. If $A$ is a non-context free language, is $A^\*$ a regular language?
2. If $A$ is a non-context free language and $B$ is a regular language, is it possible that their concatenation is a regular language?

# Answer
Let $A$ be $\\{a^p\mid p\text{ is prime}\\}$. Let $B$ be $\\{a\\}^\*$.

Both $A^\*$ and $A\circ B$ are regular. $A^\*$ is $\epsilon+aaa^\*$ and $A\circ B$ is $aaa^\*$.
> 1 votes

---
Tags: automata
---


# Question
Title: Proving that a specific grammar is ambiguous
How can I prove that the following grammar is ambiguous:

$$ A \to AA\mid B \\ B \to aBb\mid ab $$

I tried finding a string that can be derived in two different ways, but to no avail.

# Answer
> 1 votes
The word $ababab$ can be derived in two different ways.

If you don't see why, I suggest starting with the simpler grammar $A \to AA|a$.

# Answer
> 0 votes
I could suggest a 6-letter word here but that would be too easy.

The productions for $B$ do not look promising. So check what can be done with $A$. Can you produce the same sequence of 3 non-terminals via 2 different derivations?

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


# Question
Title: Determine image of hypercube under linear map
Let $A$ be an $3\times N$ matrix (where $N$ is large) with nonnegative real entries. I'd like an algorithm for determining when a vector $v\in\Bbb R^3$ can be written as $Aw$ for some vector $w\in\Bbb R^N$ with each entry of $w$ in the range $\[0,1\]$. In other words I'd like to find the image of the unit hypercube in $\Bbb R^N$ under the map represented by $A$. Does there exist an algorithm that runs in time polynomial in $N$?

Everything I've thought of so far is exponential, basically looping over the $2^N$ vertices of the hypercube. The problem is similar to that of determining the convex hull of a given set of points, except that the entries in $w$ needn't sum to $1$. Obviously taking the convex hull of all $2^N$ points would work, but it's exponential again.

My motivation is that I want to determine the range of colours that can be seen under a given light source, based on the spectral power distribution of the light source and the responsivity curves of the three cone cells in the eye.

# Answer
> 1 votes
I eventually found an answer. The image of a hypercube in $\Bbb R^3$ under a linear map is called a zonohedron. They can be calculated efficiently, for example using the algorithm in *An Efficient Algorithm for Generating Zonohedra* (PostScript file) by Paul Heckbert.

---
Tags: linear-programming, linear-algebra, convex-hull, matrix
---


# Question
Title: Understanding the Linear speedup theorem and how strong it is
Let $k \in \mathbb{N} $ and define the language $L = \\{ n,m | n^k = m \\}$

Consider a (deterministic) TM deciding $L$ then it has to compute $k$'th power which will take $f(|n|+|m|) + h(k)$ time in worse case for some polynomials $f,h$. now, by the Linear speedup theorem we can improve this to $\frac{f(|n|+|m|) + h(k)}{h(k)} = O(f(|n|+|m|))$ This means that for whatever $k$ we choose there is a (deterministic) TM deciding it in $O(f(|n|+|m|))$ even for cases $|n+m|\<\<k$. And this seemingly doesn't make sense, because it leads me to the fact that for every two choises of $k$ there are TM's deciding the corresponding languages in the same running time. What am I missing here?

# Answer
> 1 votes
The linear speedup theorem says that, for any constant $c$, you can decide the language $c$ times faster. It does not say that you can make it faster by some non-constant function.

The speedup theorem works by defining a new Turing machine that writes $c$ characters of the old Turing machine in a single tape cell, and then adjusting the transition function so that it simulates in a single step everything that the original machine did between entering and leaving each $c$-character block. If $c$ is a constant, it doesn't depend on the input, so you just compute the new machine once and use it on whatever input you want. But if you want $c$ to be some non-constant function, then you have to figure out what the new machine is every time you run it. That takes exponentially long, since there are exponentially many possible $c$-character blocks that you have to figure out the transition function for.

---
Tags: algorithms, turing-machines, time-complexity
---


# Question
Title: Interpretation of this regular expression: (1*0*)*
Do the values of the two * inside the ( ) need to remain unchanged for every repetition of ( )?

For example, 110011001100 is part of this language set, but 1100100010 isn't?

Or can the values of the two * change for every repetition of the ( )?

# Answer
> 1 votes
For any two words $w\_1$ and $w\_2$, the regular expression $\texttt{((}w\_1\texttt{)\*(}w\_2\texttt{)\*)\*}$ is equivalent to $\texttt{(}w\_1\texttt{|}w\_2\texttt{)\*}$. Hence, both your examples are elements of the language generated by $\texttt{(1\*0\*)\*}$.

In this setting, it is impossible to specify $w\_1$ and $w\_2$ occur equally often with a regular expression (except for a finite number of possibilities). Otherwise, you would be able to generate a non-regular language, in this case $\\{ 1^n 0^n \mid n \in \mathbb{N} \\}^\ast$.

# Answer
> 0 votes
There is no memory in regular expressions. If $R$ is a regular expression, then $R^\*$ means "any sequence of strings, each of which matches $R$". So, in your example of $(1^\*0^\*)^\*$, the outer star means "any sequence of strings, each of which matches $1^\*0^\*$. $110$, $1$, $000$ and $11$ all match $1^\*0^\*$, so $110\\,1\\,000\\,11$ matches $(1^\*0^\*)^\*$.

Indeed, since $1$, $0$ and $\varepsilon$ all match $1^\*0^\*$, every binary string matches $(1^\*0^\*)^\*$.

---
Tags: regular-expressions
---


# Question
Title: Determine number of values less than mean in one pass through list
The problem statement is as follows:

> Can we determine precisely the number of elements less than the mean in a list $A$ of $n$ numbers in only one pass through the array (starting at $A\_1$ and ending at $A\_n$) with only constant memory?

By "constant memory" I mean a constant number of $O(m \log\_2 n)$ bit words where $m$ is the number of bits to represent the largest value in $A$. Some other things to consider:

1. Assume $m$ is non-constant and $m \geq \log\_2 n$. If $m$ were constant, we could not even count $n$ as Yuval mentioned.
2. Assume values in $A$ are integers, but does it affect the problem if they are rational, or real valued?
3. Assume values in $A$ are uniform random. It helps if they are uniform random because we can get a tight confidence bound with a constant number of elements. How high of a confidence bound can we get?
4. Time complexity does not matter. You can spend as much time as you want on a particular $A\_i$ if that helps, but once you move to $A\_{i+1}$ you cannot go back unless you have stored $A\_i$ in one of your constant memory words.
5. What if the values in $A$ are non-uniform random with distribution is unknown? What if the distribution is known?
6. What if we are not constrained to going from $A\_1$ to $A\_n$, perhaps we could randomly sample and get a tight confidence bound even if the distribution is non-uniform?
7. What if instead of mean, we wanted values less than median? Does this help at all?

---

It's clear with 2 passes through the array we can get this value precisely with no probability involved. With one pass through the array this seems not be possible, but I am not sure. You could create an adversary that waits until the last element to give it an extreme value and throw off all previous calculations. However, with a uniform distribution this is limited. Any thoughts on these variations or an answer under the assumptions provided would be appreciated.

# Answer
> 4 votes
Consider an algorithm for arrays of length $n$ consisting of entries from $0$ to $n$, and using space $S$ bits.

Suppose that the first half of the array consists of pairs $a,n-a$ (where $a \leq n/2$). By choosing the second half appropriately, we can make the average of the entire array anything from $n/4$ to $3n/4$ (discretized to multiples of $1/n$). In particular, the state of the memory after reading the first half should store the number of pairs with $n/4 \leq a \leq n/2$. For every non-empty subset of $\\{n/4,\ldots,n/2\\}$, we can construct a first half of the array which contains exactly these values of $a$. This shows that the number of first halves that are pairwise distinguishable is at least $2^{n/4}$, hence $S = \Omega(n)$.

A very similar construction establishes an $\Omega(n)$ lower bound even when replacing the mean with the median.

---
Tags: algorithms, probabilistic-algorithms
---


title: Equivalent unambiguous grammar

text:
# Question
Title: Equivalent unambiguous grammar
Given the grammar:

$S \to AS\mid \varepsilon$
$A \to A1\mid 0A1 \mid \varepsilon$

Generate a new unambiguous grammar that generates the same language as the grammar above.

I have no idea how to make it unambiguous, I have proven already that the given language has two leftmost derivations for the string 01101.

# Answer
> 2 votes
Your grammar generates the language $L(A)^\*$, where $$ L(A) = \\{0^i 1^j : j \geq i\\}. $$ You can generate $L(A)$ unambiguously in many ways. Two options are:

1. Use $0^i 1^j = 0^i 1^i 1^{j-i}$.
2. Use $0^i 1^j = 0^i 1^{j-i} 1^i$.

Given that, the current productions for $S$ will already generate $L(A)^\*$ unambiguously.

---
Tags: context-free, ambiguity
---


title: Recursion Tree Analysis by Leaves

text:
# Question
Title: Recursion Tree Analysis by Leaves
### Assumptions

Let's say we have any recurrence relation (however this is perhaps more applicable to "unpredictable" recurrence relations):

$$T(n) = \\;?$$

For example: $$T(n) = aT\left(\frac{n}{b}\right) + h(n)$$ We could have this recurrence where the input is an array of length $n$ and $a$ and $b$ are determined by particular functions of the array values (e.g. max value, min value, median value, etc.) This is "unpredictable" in the sense that we do not know precisely how the tree will be structured for any given $n$.

Let's say that in the **worst case** the following holds: $$T(n) = \Theta(f(n))$$

Let $L(T(n))$ be the function mapping to the total work (number of basic operations) done at the leaf level (base cases) of the recurrence relation $T(n)$. Now let's say in the **worst case** of $L$ (not $T$), the following holds:

$$L(T(n)) = \Theta(g(n))$$

### Question

Does the following hold:

$$L(T(n)) = \Theta(g(n)) \implies T(n) = \Theta(f(n))$$

That is to say, if the work at the leaf level is worst case, does this imply that work of the total recurrence tree is worst case?

---

This has particular value if you don't necessarily know how the recurrence is broken up or divided throughout the tree. Perhaps you could bound the worst case work done at the leaf level and reverse engineer the tree to show the worst case overall. Alternatively, though not as useful, you may be able to prove the following:

$$T(n) = \Theta(f(n)) \implies L(T(n)) = \Theta(g(n))$$

---

Here is an example recurrence:

$$T(n, m) \leq \begin{cases} n^2 & m = 1\\ m^2 & n = 1\\ O(\min(n,m)) + \displaystyle \max\_{i \in \\{1 \ldots \min(n,m)\\}} \left\\{ T(n - i, i) + T(i, m - i)\right\\} & \mathrm{otherwise} \end{cases}$$

In this case, determining the splits is rather difficult. However, analyzing the worst case on the leaf nodes is rather simple. When we think about the recursion tree, the work at the leaves will be maximized when $n$ and $m$ are as large as possible. Namely, $T(1, m - 1) + T(n - 1, 1) = (m-1)^2 + (n-1)^2$. Now, if we know this will be the worst case overall, e.g. $$L(T(n,m)) = \Theta(n^2 + m^2) \implies T(n,m) = \Theta(f(n,m))$$ We can deduce the splits in recursion that made it this way: $$\begin{align\*} T(n,m) &= T(n-1, 1) + T(1, m-1) + O(m + n)\\ & = \Theta(n^2 + m^2) \end{align\*}$$

# Answer
The master theorem is a very thorough answer to this question.

Let us consider the three cases of the theorem, as applied to the recurrence $T(n) = aT(n/b) + f(n)$:

1. $f(n) \ll n^{\log\_b a}$: in that case most of the work is done at the leaves.
2. $f(n) \asymp n^{\log\_b a}$: in that case the work done at all levels is similar.
3. $f(n) \gg n^{\log\_b a}$: in that case most of the work is done at the root.

Other recurrence relations behave differently. As an extreme example, there is no natural Case 1 for the recurrence $T(n) = T(n-1) + f(n)$.
> 1 votes

---
Tags: computability, asymptotics, recurrence-relation
---


# Question
Title: Can the complement of a context-free language be regular?
I know that the context-free language is not closed under the complement , and the result could be context-free language or non-context free language but my question is :

is it possible of the complement of context-free language = regular language ?

# Answer
Since regular languages are all context-free and REG is closed against complement, every regular language is such an example.

As for non-regular context-free languages, the same closure property with a sprinkle of proof by contradiction easily shows that none of them can have a regular complement.
> 3 votes

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


# Question
Title: How can I develop a pseudo-polynomial time algorithm for a non-integer problem?
I have an scheduling probelm with a set of jobs $J$, with a ''non-integer'' parameter $\beta\_j$, i.e. the parameter is a real number and $\beta\_j \leqslant 0.5, \exists j \in J$.

Since the problem will be trivial if $\beta\_j \> 0.5, \forall j \in J$, I can not assume that we may transform an instance to an integer one. By the way, I am looking for the computational complexity of the problem.

So my question is: How can I develop a pseudo-polynomial time algorithm for the problem (to indicate that it is at most NP-hard in the ordinary sense), although the problem is not integer-value?

# Answer
Classifying algorithms as pseudo-polynomial time is not really a meaningful concept if there are no numbers (integers) in the instances. Of course, it is up to you to define what parts of the input should be considered "numbers".

Using real numbers in the inputs is a bad idea in the first place if you want to be able to analyze complexity or computability of the problem, as there is no way to encode all real numbers as finite strings from a finite alphabet.

For your problem, you may be able to turn it into an equivalent integer problem using some scaling, but it is impossible to say from the description given. Otherwise I would suggest you redefine the problem with rational parameters instead. This allows you to analyze it as a normal computational problem, and you could also meaningfully talk about pseudo-polynomial time if you, for example, consider numerators and denominators as separate integers.
> 2 votes

---
Tags: complexity-theory, np-hard, scheduling, real-numbers, pseudo-polynomial
---


title: Analyzing the railways network

text:
# Question
Title: Analyzing the railways network
I am studying complex networks and I have a question. Is it possible to use the tools and methods of the theory of complex network to study the properties of railways network? Are there any articles or project that have done this and that you can link to me? Thank you in advance!

# Answer
> 1 votes
Certainly it is possible. For example, in the following study the Indian railway network was analyzed.

Small-world properties of the Indian railway network. Parongama Sen, Subinay Dasgupta, Arnab Chatterjee, P. A. Sreeram, G. Mukherjee, and S. S. Manna. Phys. Rev. E 67, 036106 – 2003

In another study, the Chinese railway network was considered.

W. Li, X. Cai, Empirical analysis of a scale-free railway network in China. Physica A: Statistical Mechanics and its Applications, Volume 382, Issue 2, 2007, Pages 693-703.

The main problem is probably obtaining good data sets. However, train time tables are public, so in principle you could use data from any available time tables to reconstruct the network topology. If you also want the spatial embedding (the geographical coordinates), those might be more difficult to obtain.

---
Tags: social-networks, network-analysis, network-topology
---


title: Is this problem in NP?

text:
# Question
Title: Is this problem in NP?
I am new in complexity theory and have a doubt. If you have a language (alphabet) L (for example {"a";"b";"Y","0","1","◄"}) and a Dictionary D (for example {"abY";"Ú■";"ba";"000001◄";"FFG","342"}) Output all the words in D that can be generated by the symbols in L So, for the example above a program will output: "abY";"ba";"000001◄" Question is: is this problem in NP? Thank you in advance.

# Answer
> 3 votes
Your question makes a category error. Your problem is an enumeration problem ("List all the things with property X") but **NP** is a class of decision problems ("Does the input have property X?").

In any case, there is an obvious deterministic polynomial time algorithm for your problem. Just check each character of each string against $L$. If $L$ is fixed, this runs in linear time; if it's a part of the input, it runs in quadratic time.

---
Tags: complexity-theory, np
---


title: Lexicographic permutation list

text:
# Question
Title: Lexicographic permutation list
Does anyone have an algorithm for stepping through all permutations of n given arbitrary objects in lexicographic order?

Thanks.

# Answer
You might not be able to generate lexicographic permutations for any sequence of *arbitrary* objects. In order to do so, you will need some way of comparing two objects and determining which one is smaller.

Assuming you have this, you could use the following algorithm to generate all permutations of a sequence of $n$ objects in lexicographic order.

1. Start by sorting the input sequence, $A$, of $n$ objects
2. Find the largest index $k$ such that $A\[k\] \< A\[k+1\]$. If no such $k$ is found, terminate. The sequence $A$ contains the last lexicographic permutation.
3. Find the largest index $l$ such that $A\[k\] \< A\[l\]$
4. Swap $A\[k\]$ and $A\[l\]$
5. Reverse the sub-sequence starting from $A\[k+1\]$ to the final element, $A\[n-1\]$

Note that this algorithm generates the next lexicographic permutation of $A$ in-place. To generate all permutations, you can repeat this until no more permutations are found.
> 2 votes

# Answer
I found the following code here:

https://github.com/nzanella/universitycode/blob/master/lexpermlist.c

The code exploits the idea that the next permutation can be computed from the previous one by group theoretic multiplication by a product of four specifically indexed permutations in each step, which can be discerned from the code.

```
/* lists all permutations of the first n positive integers */
/* in lexicographic order.                                 */

#include <stdio.h>

#define N 20 /* maximum length of an n-tuple */
#define TRUE 1
#define FALSE 0

typedef int Bool;

int a[N + 1], n;

void step_in(void);
void next_permutation(const int left_index, const int right_index);
void print_permutation(void);
void get_n(void);
void initialize_a(void);

main()
{
   get_n();
   initialize_a();

   step_in();

   return 0;
}

/**********************************************************
 * step_in: this recursive function manipulates the       *
 *          values of left_index, right_index, and        *
 *          direction. These variables control the        *
 *          general flow of the algorithm, determining    *
 *          whether a permutation is to be computed or    *
 *          printed and whether the function is to be     *
 *          exited.                                       *
 **********************************************************/

void step_in(void)
{
   static enum {LEFT, RIGHT} direction = RIGHT;
   static left_index = 0;
   int right_index;   /* successive calls of step_in hide */
                      /* previous values of right_index   */

   for (;;) {
      if (direction == RIGHT) {
         ++left_index;
         right_index = n;
         if (left_index == n - 1) {
            print_permutation();
            next_permutation(left_index, right_index);
            print_permutation();
            direction = LEFT;
            break;
         }
         else if (left_index < n - 1)
            step_in();
         else {
            /* special cases where n equals 0 or 1 are treated here */
            print_permutation();
            break;
         }
      }
      else {
         --left_index;
         if (left_index < right_index) {
            next_permutation(left_index, right_index);
            --right_index;
            direction = RIGHT;
            step_in();
         }
         else
            break;
      }
   }
}

/**********************************************************
 * next_permutation: permutes the elements of the array a *
 *                   amongst themselves to obtain a new   *
 *                   permutation of these elements.       *
 **********************************************************/

void next_permutation(const int left_index, const int right_index)
{
   int i;
   int temp[N + 1];
   int top = left_index;

   temp[top] = a[right_index];
   ++top;

   for (i = n; i > right_index; top++, i--)
      temp[top] = a[i];

   temp[top] = a[left_index];
   ++top;

   for (i = right_index - 1; i > left_index; top++, i--)
      temp[top] = a[i];

   for (i = left_index; i <= n; i++)
      a[i] = temp[i];
}

/**********************************************************
 * print_permutation: prints current permutation.         *
 **********************************************************/

void print_permutation(void)
{
   int i;

   printf("\n(");
   if (n > 0) {
      printf(" %2d", a[1]);
      for (i = 2; i <= n; i++)
         printf(", %2d", a[i]);
   }
   printf(" )\n\n");
}

/**********************************************************
 * get_n: prompt user for permutation length n. Read all  *
 *        characters entered by user up to the newline    *
 *        character. Repeat if either invalid data or an  *
 *        illegal permutation length is entered.          *
 **********************************************************/

void get_n(void)
{
   Bool invalid_int_val;
   char next_char;

   for (;;) {
      invalid_int_val = FALSE;
      printf("\n");
      printf("Enter n: ");
      scanf("%d", &n);
      for(;;) {
         if ((next_char = getchar()) == '\n')
            break;
         else if (next_char != ' ' && next_char != '\t') {
            invalid_int_val = TRUE;
            for(; getchar() != '\n';)
               ;
            break;
         }
      }
      if (invalid_int_val || n < 0 || n > N) {
         printf("\n");
         printf("The number n must be an integer between %d and %d. Try again.\n", 0, N);
      }
      else
         break;
   }
}

/**********************************************************
 * initialize_a: initializes array a.                     *
 **********************************************************/

void initialize_a(void)
{
   int i;

   for (i = 1; i <= n; i++)
      a[i] = i;
}

```
> -2 votes

---
Tags: algorithms, permutations, algorithm-design, lists
---


# Question
Title: Is intersection used in regular expression?
As union is part of regular expression in form of positive closure, similarly intersection is also a part of regular expression? in which form it can be used?

# Answer
Regular expressions over an alphabet $\Sigma$, and their denotations (denoted by $L\[r\]$), are defined as follows:

1. $\emptyset$ is a regular expression, and $L\[\emptyset\] = \emptyset$ (empty language).
2. $\epsilon$ is a regular expression, and $L\[\epsilon\] = \\{\epsilon\\}$ (the empty word).
3. For each $\sigma \in \Sigma$, $\sigma$ is a regular expression, and $L\[\sigma\] = \\{\sigma\\}$ (single letter).
4. If $r\_1,r\_2$ are regular expressions over $\Sigma$ then so is $r\_1r\_2$, and $L\[r\_1r\_2\] = L\[r\_1\]L\[r\_2\]$ (concatenation).
5. If $r\_1,r\_2$ are regular expressions over $\Sigma$ then so is $r\_1+r\_2$, and $L\[r\_1+r\_2\] = L\[r\_1\] \cup L\[r\_2\]$ (union).
6. If $r$ is a regular expression over $\Sigma$ then so is $r^\*$, and $L\[r^\*\] = L\[r\]^\*$ (iteration).

The definition of concatenation of languages is $$ L\_1L\_2 = \\{w\_1w\_2 : w\_1 \in L\_1, w\_2 \in L\_2\\}. $$ The definition of iteration is $$ L^\* = \bigcup\_{n=0}^\infty L^n, \text{ where } L^0 = \\{\epsilon\\} \text{ and } L^{n+1} = L^nL. $$

As you can see, union is built into regular expressions, whereas intersection isn't. However, the set of regular languages (which is the set of languages of the form $L\[r\]$) is closed under intersection, and so given any two regular expressions $r\_1,r\_2$, we can find a regular expression $r$ such that $L\[r\] = L\[r\_1\] \cap L\[r\_2\]$.

It turns out that sometimes $r$ will be much larger than $r\_1,r\_2$, see for example Gelade and Neven, Succinctness of the Complement and Intersection of Regular Expressions, Theorem 17(2). A similar phenomenon is exhibited by complementation, see for example Theorem 12(2) in the aforementioned paper. For this reason, sometimes extended or generalized regular expressions are considered, in which operations such as intersection and complementation are allowed. While this does not increase the expressivity of regular expressions – every language expressible using an extended regular expression can also be expressed as a standard regular expression – it does increase their economy (i.e., length or size).
> 7 votes

# Answer
Intersection is not a part of standard regular expressions. However, if $R\_1$ and $R\_2$ are regular expressions, then there is always some regular expression $R\_3$ such that $L(R\_3)=L(R\_1)\cap L(R\_2)$.

This means that adding intersection to regular languages (i.e., making $R\_1\cap R\_2$ an actual regular expression) wouldn't change what you can do with regular expressions. It would make writing regular expressions easier but make proving things about them harder, because there would be more cases to prove.
> 5 votes

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


title: Merge sort in place

text:
# Question
Title: Merge sort in place
I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in industry other factors out -weight the memory tradeoff? Likewise, with quicksort the opposite is true ie, in place is preferred over not in place, which intuitively makes sense.

# Answer
Merge sort on arrays cannot be performed in-place.
> -1 votes

---
Tags: algorithms, search-algorithms, space-complexity, quicksort, mergesort
---


title: Store array of sequential intervals

text:
# Question
Title: Store array of sequential intervals
I need to store a list of sequential intervals. So for example I would to say:

* `{0-5} = a`
* `{6} = b`
* `{7-10} = c`

and so on. I need to add and remove items from this list: `.insert(d,{1,3})`

will make our array:

* `{0} = a`
* `{1-3} = d`
* `{4-5} = a`
* `{6} = b`
* `{7-10} = c`

Morehover you may need to check what items cover a range: `.itemsIn({6,8})` will return `b,c`.

I can keep an array with pointers to the same object instance for each value in a range but I suppose I can do a better job. Interval tree?

# Answer
If every interval begins immediately after the previous one ends, then you only need to store the start point of each interval (and the endpoint of the very last interval), which you can do with a self-balancing binary search tree. Inserting and deleting intervals is then $O(\log n)$-time, and identifying the intervals overlapping a query interval is $O(\log n + k)$-time, if the answer includes $k$ intervals.
> 1 votes

# Answer
Take a look at: Richard Bonichon and Pascal, Cuoq, A Mergeable Interval Map link, 2010. I've spent a bit of time trying to find the original journal where this was published, but this link is the most stable one.

I cannot say that I followed all of the proofs and logic in that paper, but I understood enough to realize that it wasn't what I was looking for, but I think it **is** meant to solve your range query.

> The solution data structure should, for instance, be able to answer queries such as finding all bindings that intersect a given interval. Being able to do this is necessary for lookups, but also at the time of adding a new binding, in order to maintain the invariant that the intervals in the map are disjoint.

The basic idea is to enforce a "covering" ordering logic on the nodes of a tree:

> In Patricia trees, there is a static hi- erarchy for deciding which node goes above the other, and this static hierarchy ensures trees are balanced or almost balanced without any re-balancing operations. In the case of our data structure, we similarly define a static ordering on intervals that tells which node must be placed above the others. Intuitively, the interval containing the multiple of the largest power of two is put at the top. Like the ordering in Patricia trees, this ordering has the bounded chain length property...

I also recommend understanding Okasaki's Fast Mergeable Integer Maps first.
> 0 votes

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