# Question
Title: Is it really possible to prove lower bounds?
Given any computational problem, is the task of finding lower bounds for such computation really possible? I suppose it boils down to how a single computational step is defined and what model we use for the proof, but given that, do we really prove a lower bound then in general? What I means is that can we prove something like "problem $X$ cannot be solved faster than $t(X)$ time" rather than "problem $X$ can be solved in $t(X)$ time or faster"?

I have tried to find information specifically on lower bounds and proofs of them, but I can't really find any of interest, any recommendations on books/papers/websites on the subject?

# Answer
We can absolutely prove such things.

Many problems have trivial lower bounds, such as that finding the minimum of a set of $n$ numbers (that are not sorted/structured in any way) takes at least $\Omega(n)$ time. The proof for this is simple: a hypothetical algorithm that runs in $o(n)$ time can not examine all of the numbers in the input. So if we ran the algorithm on some input, we could observe that it never examined a particular element of the input. Changing that element to the minimum, we can get the algorithm to fail.

A less trivial lower bound is the $\Omega(n \log n)$ lower bound for sorting in the comparison-based model. The proof for that goes along the following lines: given an input of $n$ numbers, there are $n!$ possible outputs (the input could be any permutation of the sorted list, so the output can also be any permutation of the input). If we are limited to only doing comparisons, then our algorithm (on average) needs to perform at least $\log\_2(n!)=\Omega(n \log n)$ comparisons in order to be able to give $n!$ different outputs.

Lower bounds can be even stronger. There are several problems (notably the $EXPTIME$-hard problems) for which there is an exponential lower bound. Problems in this class include computing optimal strategies for games such as (generalized) chess, checkers and go. The proof of this is via the **Time Hierarchy Theorem**, which states (subject to some restrictions on $f$):

> Given a function $f$, there exists a computational problem that can be solved in time $O(f(n))$ but can not be solved in time $o(\frac{f(n)}{\log n})$.

So basically, if you can think of a function $f$ there exists a problem that requires that much time to solve.

Finally, another avenue of not necessarily proving a time lower bound but something even stronger is showing the undecidability of a problem (e.g. halting, post correspondence).
> 22 votes

# Answer
Yes, it's possible. The classic example is the fact that any comparison-based sorting algorithm requires $\Omega(n\log n)$ comparisons to sort a list of length $n$.

However, lower bounds seem to be much harder to prove than upper bounds. To prove that there's a sorting algorithm that requires $O(n\log n)$ comparisons, you just need to exhibit such an algorithm (merge sort – *voila*!). But for a lower bound, you somehow need to show that no algorithm in a particular class can solve your problem. The difficulty of doing that is illustrated by the fact that we only know that $$\mathrm{L}\subseteq \mathrm{NL}\subseteq \mathrm{P}\subseteq \mathrm{NP} \subseteq\mathrm{PSPACE}\\,,$$ even though we know that at least one of those inclusions is strict ($\mathrm{L}\subset \mathrm{PSPACE}$ by the space hierarchy theorem) and most people think they are *all* strict.

On the other hand, Ryan Williams has a nice paper (and talk, which I've heard a couple of times) called *Algorithms for Circuits and Circuits for Algorithms*, in which he argues that finding lower bounds and finding algorithms aren't fundamentally all that different. For example, he cites the proof of the undecidability of the halting problem as an example of an algorithm (the universal Turing machine) being used exactly to prove a lower bound (undecidability).
> 15 votes

# Answer
To take a trivial example, you cannot find the largest number from a set of $n$ numbers without checking them all which requires linear time. No big proof. But there are algorithms that do not always require reading all the data. A nice example is searching all occurences of a pattern in a string, which may not require reading the whole string (Boyer-Moore algorithm). But I should not repeat what is already answered, probably better than I would.

However, there is a point in the question that calls for some more remarks regarding lower bound (or complexity bounds in general).

Actually the choice of what is a single computational step is irrelevant, as long as computational steps can be considered as having a constant upperbound (and lower bound). The complexity result will be the same since it is defined up to a constant. Taking 3 comparisons as unit operations, or only a single one, makes no difference.

The same is true regarding the size of data which serves as reference to evaluate the cost of the computation. Taking a single integer, or two integers as unit of size makes no difference.

However, the two choices must be related.

You may consider that a number $n$ is a single unit of data if you consider that operations on integers, such as addition or comparison, are unit operations. You may also consider that it is $\log n$ units of data since it takes $O(\log n)$ digits to represent a number. Then, of course, addition and comparison are no longer unit operations, and their cost depends on the values of the operands.

Whether an operation can be considered having unit cost is tightly related to what data can be considered as having unit size. And that depends on what level of abstraction you choose for your model of computation.
> 3 votes

---
Tags: complexity-theory, time-complexity, proof-techniques, lower-bounds
---


# Question
Title: Do I understand pseudo polynomial time correctly?
The running time of knapsack is $O(n\*W)$, but we always specify that this is only pseudo-polynomial. I was wondering if somebody could tell me if I understand the notion of pseudo-polynomial time correctly.

My current understanding is that pseudo polynomial time means polynomial in the magnitude of the input, and polynomial time is polynomial in the number of bits it takes to represent the input. Thus, looking through each element of an array is $O(n)$ in the magnitude of its length (pseudo-polynomial), but it is exponential in the number of bits in the length of the array. In the same way, binary search is $O(log\_2 n)$ in the magnitude of the length of $n$, but is linear in the number of bits in $n$ making it "pseudo-logarithmic".

If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?

# Answer
The running time for binary search that you quote applies for the so-called RAM model. I think that it is usually assumed that the machine words have size $\Theta(\log n)$ bits, where $n$ is some natural parameter like the length of the input.

For binary search, the input has size $\Theta(n)$, assuming that the array's datatype fits in a constant number of machine words, and so the running time $O(\log n)$ is logarithmic in the input size. The running time of the dynamic programming algorithm for knapsack is $\Theta(nW)$, but the size of the input is $O(n\log W)$ (in fact somewhat less, since machine words have superconstant size). This is not polynomial in the size of the input. However, if the weights are encoded in unary, then the size of the input is $O(nW)$ (again, actually somewhat less), and so the algorithm is pseudo-polynomial. It's a matter of encoding - whether you encode the weights in binary or in unary.
> 4 votes

# Answer
> If I am correct, why do we never specify that binary search is linear in the number of bits, but we always specify that knapsack is exponential in the number of bits?

It depends on the perspective from which one tackle the problem. Often, when dealing with numbers, people tend to give more importance to the number of bits. Why is that ? Simply because numbers problem comes from their size (number of digits or bits).

e.g.

* **0/1 knapsach problem**: It runs in O(nW) time (see wikipedia). "n" being the number of items and "W" is the maximum weight. A large weight means a very large number, which is critical. A large number of items depends on the size of items, which reduces to W. The size of number grows exponentially when expressed in terms of bits (2x). For this reason people care more about size input data in terms of bits.
* **is prime problem**: An algorithm for finding out whether a number N is prime or not. It is quite easy to compute it for a 10 digit number, but harder as we go for large numbers. The number of bits here are important and grows exponentially.
* **binary search**: it runs in log2(n), but has a linear growth in terms of number of bits. It needs a really very big data set, which means a very big bit encoding so to make it impossible to run the algorithm in a reasonable amount of time.

In the first examples, there is a significant difference between the real data size and data representation: We can easily give as input 300 digit number (relatively small), but it's encoding in binary code is TOO BIG, which influences the binary operations.

However in the case of "binary search", the different between data representation and real data size is constant.
> 1 votes

---
Tags: algorithms, complexity-theory, terminology, pseudo-polynomial
---


title: Memory Consistency vs Cache Coherence

text:
# Question
Title: Memory Consistency vs Cache Coherence
Is it true that Sequential Consistency is a stronger property than Cache Coherence?

According to

> Sorin, Daniel J; Hill, Mark D; Wood, David A: A Primer on Memory Consistency and Cache Coherence, Morgan & Claypool, 2011

sequential consistency can be described as (not formally):

> *Sequential consistency* memory model specifies that the system must appear to execute all threads’ loads and stores to all memory locations in a total order that respects the program order of each thread. Each load gets the value of the most recent store in that total order.

In other words, system is sequentially consistent, if given memory events (loads and stores) of each thread we can order all these events such that: 1) for each thread the order of its events is preserved, and 2) the global order is serial (any load returns latest value stored).

Now they continue and describe coherence:

> A definition of *coherence* that is analogous to the definition of Sequential Consistency is that a coherent system must appear to execute all threads’ loads and stores to a single memory location in a total order that respects the program order of each thread.

In other words, system is coherent, if given memory events of each thread *for each location* we can order events for that location, such that: 1) for each thread the order of its events *to that location* is preserved, and 2) *for each location* the order is serial.

Finally, they point out the difference:

> This definition highlights an important *distinction between coherence and consistency*: coherence is specified on a per-memory location basis, whereas consistency is specified with respect to all memory locations.

So it seems the difference is that for coherent systems we need a total order on all events for each location (thus the ordering between events for particular location), while for consistent systems the total order should be defined on the all events (and thus the ordering is also between events for different locations)?

Does that mean that coherence is less strict that consistency? (which seems amusing!) Are there traces that are coherent but not consistent?

# Answer
> 15 votes
As you pointed out, *coherence* is a property of an individual memory location while *consistency* refers to the order of accesses to all memory locations. Sequential consistency is a strictly stronger property than coherence. That is: every system that is sequentially consistent is also coherent at every memory location. The opposite is not true, a memory that is coherent at every location is not necessarily sequentially consistent. In fact, there are many real cache-coherent multiprocessors where the memory model is only weakly consistent (there are cases where different processors observe accesses to different locations happen in different orders.)

Proof of sequentially consistent implies coherent:

Given any trace from a sequentially consistent system, by definition that trace must have a total order that is agreed on by every processor in the system. Now look at the accesses just to location $x$ in that trace. Because a total order is transitive, the accesses just to location $x$ also have a total order on them that is agreed on by every processor in the system. Thus all memory locations are coherent.

The reverse doesn't work out. Consider two coherent memory locations $x$ and $y$ with just a single access to each $x\_0$ and $y\_0$. All the processors agree on the order of accesses to location $x$ and all the processors agree on the total order of accesses to location $y$, but some processors may observe the order $x \rightarrow y$, while others may observe the order $y \rightarrow x$. So coherence doesn't imply sequential consistency.

This can lead to surprising results. For example

```
initially A=B=0
process 1               process 2
store A := 1            load B (gets 1)
store B := 1            load A (gets 0)

```

This trace is coherent:

* for A the order is: `proc2 loads A(gets 0)`, `proc1 stores A:=1`
* for B the order is: `proc1 stores B:=1`, `proc2 loads B(gets 1)`

But it is not consistent! Since if `proc2 load B` returns 1, then `proc1 store A := 1` already happened and `proc2 load A` should also return 1.

---
Tags: computer-architecture, cpu-cache, shared-memory
---


title: Entropy notation: What does this mean?

text:
# Question
Title: Entropy notation: What does this mean?
If you look at page 13 of the lecture slides here there is this line

$H(Y) = H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha))$

I don't really understand what the term on right hand side is. At first I thought it's joint probability of binary random variables but that does not make sense. After a while I notice that the first parameter is the probability of $Y = 0$, the second parameter is the probability $Y = e$ and the third parameter is the probability $Y = 1$. However, I still dont really understand what this notation means, and why this equates to

$H(\alpha,(1-\alpha)) + (1-\alpha)H(\pi,(1-\pi))$

Can someone please help me out here?

Thank you!

# Answer
> 4 votes
The first thing you should realize to understand it is that the $H(Y)$ notation corresponds to the calculation of the information entropy for the states in $Y$, such that $H(Y) = -\sum\limits\_{y \in Y} p(y) \log\[p(y)\]$. With that in mind, we can interpret the expression and equate the terms. You are correct that the three parts correspond to the probability of $0$, $e$, and $1$, where $e$ is the state of erased information. Expanding it we get:

$H((1-\pi)(1-\alpha), \alpha, \pi(1-\alpha)) $ $\quad= -(1-\pi)(1-\alpha)\log\[(1-\pi)(1-\alpha)\] - \alpha\log(\alpha) - \pi(1-\alpha)\log\[\pi(1-\alpha)\]$

This gives us the full expression for calculating the entropy of the system composed of those three states. Next, as we usually do when proving an equality, we cheat and look at the answer to see what form we need it in. Your last term has all the $\pi$ terms clumped onto one side, and all the $\alpha$ terms clumped onto another (except for where they are also a coefficient). Thus we will organize the log terms in this manner. First we use the log rules to expand the products:

$ \quad= -(1-\pi)(1-\alpha)\log(1-\pi) - (1-\pi)(1-\alpha)\log(1-\alpha) $ $\quad\phantom{=} - \alpha\log(\alpha) - \pi(1-\alpha)\log(\pi) - \pi(1-\alpha)\log(1-\alpha)$

Then we sort all the log terms in the order of the final expression:

$ \quad = -\alpha\log(\alpha) - (1-\pi)(1-\alpha)\log(1-\alpha) - \pi(1-\alpha)\log(1-\alpha) $ $ \quad\phantom{=} - \pi(1-\alpha)\log(\pi) -(1-\pi)(1-\alpha)\log(1-\pi)$

Then we simplify and factor:

$ \quad = -\alpha\log(\alpha) - (1-\alpha)\log(1-\alpha) + (1-\alpha) \cdot \[ -\pi\log(\pi) - (1-\pi)\log(1-\pi) \]$

And this is equivalent to:

$$H(\alpha, 1-\alpha) + (1-\alpha) H(\pi, 1-\pi)$$

This can be interpreted as the left part being the entropy from erasing (probability $\alpha$) or not erasing, and the right part being, in the event it was not erased, the entropy from it being a 1 (probability $\pi$) or a 0. It should also make some intuitive sense that this will be equal to the entropy from the distribution of final states of $0$, $e$ (erased), and $1$.

---
Tags: information-theory, entropy
---


title: What is an edge hop?

text:
# Question
Title: What is an edge hop?
I've tried googling it, but found nothing. Here is the context it's in:

From *Bayesian Reasoning and Machine Learning*:

Adjacency matrices may seem wasteful since many of the entries are zero. However, they have a useful property that more than redeems them. For an N x N adjacency matrix A, powers of the adjacency matrix $\[A^k\]\_i$$\_j$ specify how many paths there are from node i to node j in k edge hops. If we include 1's on the diagonal of A then $\[A^{N-1}\]\_i$$\_j$ is non-zero when there is a path connecting i to j in the graph. If A corresponds to a DAG the non-zero entries of the jth row of $\[A^{N-1}\]\_i$$\_j$ correspond to the descendants of node j.

# Answer
An "edge hop" is the "act" of crossing an edge. It's a figurative term. The entry $\[A^k\]\_{ij}$ counts how many paths there are from $i$ to $j$ of length $k$. A path of length $k$ entails traversing $k$ edges, hence the $k$ edge hops.
> 7 votes

---
Tags: graphs, machine-learning
---


title: Differences in Postfix Syntax

text:
# Question
Title: Differences in Postfix Syntax
A question about postfix/RPN came up in my class due to the current ACSL competition. Is it a rule or convention that **4 + (5 * 6)** in infix is written **4 5 6 * +** in postfix, as opposed to **5 6 * 4 +** in postfix? When the second postfix example is translated into infix, the order of the arguments is switched, but should that matter for operators with the commutative property?

# Answer
> 3 votes
There are no "rules", you make the rules yourself. The rule used in class has the property that the numbers appear in the same order in both expressions. The rule is also pretty natural:

$$ T(\alpha \circ \beta) = T(\alpha) T(\beta) \circ $$

Here $\alpha$ is an infix expression, $T(\alpha)$ is the translation of $\alpha$, and $\circ$ is a binary operation. The corresponding rule for unary expressions is $T(\circ \alpha) = T(\alpha) \circ$, and there is also a deparenthesizing rule, $T((\alpha)) = T(\alpha)$. If you apply these rules to the expression $4 + (5 * 6)$ you will get $4 \\; 5 \\; 6 * + $.

Keeping the order is important for operations which are not commutative, such as subtraction and division; that's assuming on the convention that $3 \\; 2 \\; - = 1$ and so on, rather than the other way around.

# Answer
> 1 votes
In my view postfix expressions code trees. This can be done regardless of semantics. One only needs the arity (number of arguments) of each operator. Thus your two postfix expressions code different trees.

Infix expressions can also be used to denote (binary) trees but then we usually need parentheses to fix the structure. We can do with less parentheses by adding operator precedence and associativity rules for the operators.

---
Tags: notation, syntax
---


# Question
Title: NPDA for $\{w : w \in \{a,b\}^*,n_a(w)\geq n_b(w)+1 \}$
I believe that the following NPDA accepts the language $$\\{w : w \in \\{a,b\\}^\*,n\_a(w)= n\_b(w)+1 \\}\\,,$$ where $n\_a(w)$ represents number of symbol $a$'s in string $w$.

Is there a two-state NPDA that accepts the same language?

# Answer
> 3 votes
"**Is there a two-state NPDA that accepts the same language?**"

Yes, every PDA can be replaced by one that has two states, one accepting and one non-accepting. In general one uses three steps to prove this formally:

* Every PDA (with *empty stack acceptance*) can be transformed into a CFG. The construction is sometimes known as the triplet construction: a single nonterminal of the CFG codes two states and a stack symbol of the PDA.
* Every CFG can be transformed into a PDA with a single state and *empty stack acceptance*. That equivalence is quite straghtforward.
* PDA with *empty stack acceptance* are equivalent to PDA with *final state acceptance*. But, where the stack-PDA may have a single state, the state-PDA usually uses one more, for acceptance.

Always, when discussing PDA, be explicit on the acceptance mode. (But that might be a silly request when your textbook considers only one of these types.)

PS. By the way, your machine seems to have the basic counting ideas implemented.

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


# Question
Title: What Programming Languages a Computer Science Engineer must learn
During my college I studied C/C++, C#.Net and ASP.Net. Now one my friend suggested me to learn Python & MATLAB also. He wasn't much specific why to learn these languages, He said it would be helpful to get a job with these languages. I've also seen lots of good resume, mostly they have Python (Scripting Language), MATLAB, plus above languages that I've studied. I've to appear for interviews in 3 months, So please guide me what should I do.

# Answer
Computer Science and software engineering/development/etc are not about the languages, but about creating solutions to meet a need (solve a problem). Different platforms and languages are tools you will learn to use as you learn and get more experience. All of the languages/platforms you've mentioned in your question are heavily used in software development these days (except maybe FoxPro). You should become knowledgable about all of them (and many others you might come across), and become very proficient in a select few.

You will find that, having mastered one or two languages, becoming productive in others will get easier.
> 4 votes

# Answer
It depends on the position/job you apply for.

Some employers may have an urgent need for a person who is productive at day#1. Then they want someone familiar with exactly the language and tools they have in this particular project.

Others may expect you to spend a significant time to learn the company and their special tools. Then it's less important what languages you know, the key is your ability to learn and adapt to their prefered tools.

In general, new languages and tools pops up all the time. Expect to learn add new languages and tools all the time during your career.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: Data Structure for Representing a Math Expression
I'm looking to improve my object-oriented design skills and I came across a problem which asked to design classes to represent a mathematical expression such as (a + b) * ( c - d / e) in memory so that it could be evaluated (by adding an evaluate method if need be in the class some time later)

The simplest solution I came up with was to store this expression in a stack (push(a), push(+), push(b)....), or may be even in an array (arr\[0\] = a, arr\[1\] = +...)

I feel like this is bad design and I read online that a binary tree (expression tree) is better to represent such an expression, but I am not sure why it is better.

Can someone help me understand this? Does the binary expression tree provide some benefits over storing in a stack?

# Answer
> 6 votes
Different representations are useful for different purposes. Think what kinds of things you might want to do with the expression, and think how each of them would be done using the stack representation and using the binary tree representation, and choose for yourself.

For fun, you may also want to consider something completely different, e.g. the english language representation: e.g. "the product of the sum of a and b, and the difference between c and d over e", or the representation as X86 machine code which would compute this expression, etc.

Things you may want to do with an expression (in any particular program you would probably need only a small subset of these):

* Evaluate it, given certain values of the variables
    + Just once
    + Evaluate the same expression repeatedly for different values, with very high performance requirements
* Perform simple algebraic manipulation, e.g. simplifications such as replacing *x - x =\> 0*, *x\*1 =\> x*, etc.
* Perform sophisticated algebraic manipulation on it, e.g. factorize the polynomials, compute derivatives or integrals.
* Understand the expression stored in a variable when you're debugging the program
* Format it as a string for displaying to the user
* Render it as a mathematical expression to MathML
* Draw it as a mathematical expression on a Javascript canvas
* Compare two expressions for equivalence
* Compare two expressions for equivalence ignoring variable names, e.g. *a * a + b* being equivalent to *p * p + q*
* Convert a user-supplied string into an expression, checking it for well-formedness
* ...

Honestly speaking, I can find only one item of these for which the stack representation can possibly make things easier than the binary tree representation, and the array representation seems just completely useless.

# Answer
> 1 votes
In general, syntax is represented via an abstract syntax tree. This tree structure captures the hierarchy, precedence, and logical structure of its input, but not its formatting. The AST will not necessarily be a binary tree, although nodes denoting binary operators will have two child nodes.

In pseudocode, AST classes could look like this:

```
interface Ast {
}

class Literal(@value: Float) implements Ast {
  def value = @value
}

class Variable(@name: String) implements Ast {
  def name = @name
}

abstract class Binop(@left: Ast, @right: Ast) implements Ast {
  def left = @left
  def right = @right
}

class Add extends Binop { }
class Subtract extends Binop { }
class Multiply extends Binop { }
class Divide extends Binop { }

interface AstVisitor[A] {
  def visit(ast: Literal): A
  def visit(ast: Variable): A
  def visit(ast: Add): A
  def visit(ast: Subtract): A
  def visit(ast: Multiply): A
  def visit(ast: Divide): A
}

```

Your expression `(a + b) * ( c - d / e)` could then be represented as

```
Multiply(Add(Variable("a"), Variable("b"),
         Subtract(Variable("c"),
                  Divide(Variable("d"), Variable("e"))))

```

Different visitors could then implement different functionality. For example, an evaluator would look like this:

```
class Evaluator(@env: Map[String, Float]) implements AstVisitor[Float] {
  def visit(ast: Literal) =
    ast.value
  def visit(ast: Variable) =
    env.get(ast.name)
  def visit(ast: Add) =
    this.visit(ast.left) + this.visit(ast.right)
  def visit(ast: Subtract) =
    this.visit(ast.left) - this.visit(ast.right)
  def visit(ast: Multiply) =
    this.visit(ast.left) * this.visit(ast.right)
  def visit(ast: Divide) =
    this.visit(ast.left) / this.visit(ast.right)
}

```

Other visitor classes could assume responsibilities such as rendering the expression in normal mathematical notation, or performing transformations such as constant folding or other optimizations.

Due to its versatility, using an AST is common in compiler construction, but in simple cases it's going to be absolute overkill. If you only want to evaluate simple arithmetic expressions, a stack is vastly simpler.

Let's assume that the tokens on our stack or list can be of type `Float`, `String` (for variables), `Lparen`, `Rparen`, `Plus`, `Minus`, `Mul`, and `Div`. Then your expression would be represented as

```
(Lparen, "a", Plus, "b", Rparen, Mul, Lparen, "c", Minus, "d", Div, "e", Rparen)

```

Evaluating this stack ends up being the same problem as parsing it into an AST. For arithmetic expressions, we can use the Shunting-yard algorithm to translate it into Reverse Polish notation, which reorders the elements as

```
(Mul, Plus, "a", "b", Minus, "c", Div, "d", "e")

```

Note that this is essentially our AST structure flattened into a list, and that all parens have been made unnecessary. Instead of reassembling the expression in Polish notation, the Shunting-yard algorithm can be trivially modified to either assemble an AST or to directly evaluate the expression. Where the SYA pops an operator from the temp stack and adds it to the result stack, a direct evaluator would pop the operator from the temp stack, the arguments from the result stack, perform the operation, and push the result onto the result stack. Assembling an AST has the difference that instead of calculating a result, we create an AST object and push it onto the result stack.

---
Tags: data-structures, binary-trees, stacks
---


# Question
Title: Is it possible to make excluded search with for loop in Java?
I am trying to calculate all pure strategy Nash equilibrium in a mxn game. It requires to check all pure strategy pairs (m.n pairs). Suppose player 1 has m strategies. Algorithm should start with the first pair (1,1) and compare (1,1) with (2,1),(3,1),...(m,1).

Same for all strategies, exp: (3,4) is compared by (1,4),(2,4),(4,4),...,(m,4).

In summary is it possible to make a search with for loop which excludes existing i:

Thank you.

# Answer
First of all, if you want to check each combination of pure strategies, you will have two nested `for` loops:

```
int a, b;
for (b = 0; b < n; b++) {
  for (a = 0; a < m; a++) {
    compare(a, b);
  }
}

```

Additionally, `compare(a,b)` will then be compared to each alternative I have to exchange `a` under the assumption that my opponent will use `b`:

```
int compare(int a, int b) {
  for (int x = 0; x < m; x ++) {
    if (x == a) continue; // This will exclude the check (a, b), (a, b)
    System.out.println("Comparing (" + a + ", " + b ") and (" + x + ", " + b + ")");
  }
  return 0;
}

```

However, my knowledge of game theory is a little bit rusted. Aren't you trying to determine the best answer in pure strategies to each pure strategy of your opponent?

In fact, this comparison would have a complexity of $\mathcal{O}(m^2\cdot n)$. In order to determine the best answers with only a complexity of $\mathcal{O}(m\cdot n)$, you can gradually search the maximum payoff while traversing each possible combination of strategies:

```
int best_answers[n];
int a, b;
int max_payoff;
for (b = 0; b < n; b++) {
  best_answers[b] = 0;
  max_payoff = 0; // If negative payoffs are possible, adjust this.
  for (a = 0; a < m; a++) {
    if (payoff[a][b] > max_payoff) {
      max_payoff = payoff[a][b];
      best_answers[b] = a;
    }
  }
}

```

Here, I assume that `int payoff[m][n]` is a 2-dimensional array that encodes the payoff matrix. After running this algorithm, `best_answers[b]` contains the best answer strategy for strategy $0 \leq b \< n$ of the opponent.
> 2 votes

---
Tags: search-algorithms, game-theory, java
---


# Question
Title: Update all nodes in a graph in a way that at any step all chosen nodes are disconnected
There are N nodes in a graph and some of them are connected with edges. All nodes are of type T1. The goal is to update all nodes to type T2. At any step you can choose any set of nodes and change their type to type T2 with the only restrictions that no nodes in the chosen set can be connected with an edge (i.e. this sub-graph should not have edges). Find the minimum number of steps required to update all nodes to type T2.

A graph can have any topology, i.e. nodes can be connected in a random fashion without any pattern

# Answer
> 1 votes
Hint: Your question is tantamount to finding a partition of the vertices of the graph into as few independent sets as possible. This is the same as finding the chromatic number of the graph, which is NP-complete.

---
Tags: algorithms, graphs
---


title: Deciding Countability of Languages

text:
# Question
Title: Deciding Countability of Languages
Suppose we have given $\Sigma=\\{a,b\\}$, Which one of the following set is not countable

> (a) Set of all languages over $\Sigma$
>
> (b) Set of all regular languages over $\Sigma$
>
> (c) Set of all languages over $\Sigma$ accepted by Turing machine

I've read some techniques to find answer to the question like whether

> Is the set of all infinite sequences of some alphabets countable or not
>
> Is the set of all finite non-empty subsets of some alphabets countable or not

But they didn't helped me to answer questions like above. I tried `Cantor Diagonalization` but it didn't help either. How can we answer such questions.

# Answer
> 0 votes
> (a) Un-Countable
>
> (b) Countable
>
> Regular Language may be finite or infinite. Either case enumeration is possible as it contains pattern. Hence, Set of all regular languages over $\sum$ are Countable.
>
> (c) Countable
>
> Since Language accepted by Turing Machine is `Recursively Enumerable languages`, As Enumeration is possible. Hence, Set of all languages over $\sum$ accepted by TM are Countable

---
Tags: formal-languages, uncountability
---


title: Stack memory questions

text:
# Question
Title: Stack memory questions
Are data and return addresses both pushed on the same stack space? If yes, couldn't this piece of code cause problems:

```
CALL r1 //the PC is now the contents of register 1, return address is pushed on the stack.
POP r2  //pop the top of the stack and put the data in register 2.
RET     //return from subroutine

```

The `POP` instruction would delete the return address of the subroutine so the `RET` instruction will return to the wrong location.

# Answer
> 1 votes
Yes, they are stored on the same stack. Yes, that sequence of code could cause problems. It is up to the compiler (or the assembly language programmer) not to do that.

A compiler will typically ensure that the start of the function pushes some number of words (say $n$ words), and that the end of the function pops off exactly as much as was pushed -- no more, and no less. As long as you do that, the return address will be left undisturbed and the RET will return back to right after the CALL. If you don't follow that kind of convention, then all sorts of strange things can happen, exactly as you say -- so make sure you follow the convention.

# Answer
> 0 votes
That's exactly what can be exploited using buffer overflows. If you overwrite the return address of a function by writing beyond the bounds of, e.g., a vulnerable array, you can control where the function returns to.

The OS kernels try to prevent parts of this by randomizing the memory locations where your code is loaded to, for instance. So you can't simply jump into arbitrary piece of your code, but then again there is Return-Oriented Programming (ROP). In ROP, you return to other parts of the exploited code, because the relative addresses of different functions within the same program are the same, and you can address other functions in the code by debugging them to get the relative addresses and then use pointer arithmetic.

---
Tags: computer-architecture, stacks
---


# Question
Title: How should I choose the neighborhood structure for simulated annealing for my problem?
There are $n$ students and $m$ courses. Each student $i$ wants to attend a subset $C\_i \subseteq \\{1,\ldots,m\\}$ of the courses. There are $k$ time slots on a weekly schedule. The goal is to select a time slot for each course such that the students can attend as many courses as possible, that is, find a mapping $f: \\{1,\ldots,m\\} \rightarrow \\{1,\ldots,k\\}$ such that the following objective function is maximized:

$$\sum\_{i = 1}^n \big| \bigcup\_{j \in C\_i} \\{f(j)\\} \big| $$

For my (artificial) instance $n = 10^5, m = 5000, k = 25$, and any student wants to attend at most 16 courses. I have tried a hill climbing algorithm which moves in the search space by changing one course at a time in the mapping $f$ if it improves the objective function, until it can improve no more. This gives a local maximum, but I'd like to do better. I've tried to implement a simulated annealing approach with the same neighbourhood structure, but I haven't been able to tune the parameters to beat the hill climbing algorithm.

I've read that the number of moves from any part of the search space to another part should be small. In my solution I need at most $5000$ moves, is this too much? If make bigger changes into the mapping, the evaluation of the cost function becomes expensive, as I have to recompute the objective function for every student affected by the change. What kind of a neighbourhood structure would suit this problem the best?

# Answer
> 1 votes
Simulated annealing can cope with neighborhood structures where you have to walk quite a bit to reach a distant point. Of course, the minimum distance between two points in the state space should at most be polynomial in the problem size, but any reasonable optimization heuristics will also require this restriction. The 5000 moves are completely reasonable for simulated annealing, especially since this is linear in $m$.

Don't implement any moves which would be very expensive to evaluate. The strength of simulated annealing is that it can work with moves which are cheap to evaluate, and hence evaluate a large number of candidate solutions. But if your state space is large, then you should also let simulated annealing evaluate a large number of candidate solutions. So your cool down schedule becomes important in this case. I could go into more detail here, but the question was about the neighborhood structure only, and the answer to this question is that your neighborhood structure is basically OK, and you should not use a neighborhood structure which would lead to expensive recomputations.

---
Tags: algorithms, optimization
---


# Question
Title: Is a k counter automata a special kind of PDA?
I understand that a 1 counter automata is a special kind of PDA where the stack alphabet consists of one symbol (ignoring the fixed bottom symbol) but what about 2 counter automata? Is it a special kind of PDA where the stack alphabet consists of two symbols? Can we generalize like so: a k-counter automata is a PDA with k many symbols in the stack alphabet where k\>0?

# Answer
A two-counter automaton has two counters, so two push-downs, each with a single stack symbol (agaun ignoring bottom). Such an automaton is not equavalent to push-down automata.

Any PDA can be shown to be equivalent with a PDA with two different stack symbols, so in itself characterize the context-free languages.

Two-counter automata are much more powerful, they can simulate Turing machines, and hance form the recursively enumarable languages. The special bottom symbol is essential here. In that way the machine is able to do a zero test (i.e., check the contents of the counter is zero). The simulation of TM's by counter automata is explained in the old textbook by Hopcroft and Ullman (Intro to Automata Theory, Languages, ...) in two steps. First using four counters and coding the contents of (half of) a working tape of a TM by a single number. The result is attributed to Minsky (1961).
> 3 votes

---
Tags: automata, pushdown-automata, computation-models
---


# Question
Title: How to interpret the execution of distributed computation from time-space diagram?
I'm following a course on Distributed Systems

http://www.ict.kth.se/courses/ID2203/index.html

and currently learning about asynchronous models. I can't seem to reconcile a given time-space diagram of an execution with the symbolic definition of the execution as a sequence of configurations and events.

In the model, an execution is defined as a sequence of configurations interleaved with events. As in:

```
<C,E,C,E,C,E...>

```

Where the C's are configurations (states of the nodes, including their buffers) and the E's are events, which in this model, are either Computation or Delivery events.

A computation event, comp(i), takes place at a single node, indexed by i, and modifies the buffers of node\_i and the internal state of node\_i and nothing else. A delivery event, del(i,j,m), removes message m from the output buffer of node\_i and adds it to the input buffer of node\_j.

A time space diagram of a particular execution is given in Slide 11 in this particular lecture: http://www.ict.kth.se/courses/ID2203/material/Lecture\_2.\_Unit\_3.\_Computation\_theorem\_and\_causality.pdf

The arcs on a single timeline are comp(i) events at a particular node. The arcs between timelines are del(i,j,m) events between nodes i and j.

I'd like to interpret this diagram into a sequence of comp and del events, but it seems ambiguous. Specifically, a delivery is initiated from node 1 to node 2 -- del(1,2,m) -- and during the delivery a computation event at node 3 -- comp(3) -- takes place and completes before the delivery event completes.

Since the events in an execution are, by definition, totally ordered, I'm not sure if the comp(3) should precede the del(1,2,m) or vice versa.

# Answer
> 3 votes
Yes, it is ambiguous, and it is ok. A single space-time diagram can be linearized (collapsed into a compatible sequence of configurations and events) in many ways, potentially an exponential number of ways. E.g. imagine that you have 1000 nodes, and each of them performs a local operation. Obviously there's 1000! different ways to linearize this, because there are no inherent causality constraints in this situation.

It is not true that events in an execution are totally ordered. They are only partially ordered, using the partial order given by causality constraints (most of which are "a message is sent BEFORE it is received"). There are many total orders compatible with this partial order.

---
Tags: distributed-systems
---


# Question
Title: How many combination of “n” bits are there in terms of n?
How many combination of "n" bits are there in terms of n? And if this is derived, Given 4 bits for representing negative and positive numbers, what is the largest positive number that can be represented?

# Answer
> 3 votes
Each bit can be either 0 or 1, so you have two choices per bit. That gives you 2^n combinations. E.g. n=1 implies 2^1=2 states, n=2 implies 2^2=4 states. You could arrive at this by 1) making a lexicographic list of all the combinations or 2) using a formula from combinatorics.

Your second question seems to address representing integers with binary numbers. You must first settle on an encoding scheme before that question can be answered. A popular encoding scheme is two's complement. The maximum positive integer represented in 4-bit two's complement is 0111, which is 7.

# Answer
> 2 votes
These are two separate questions.

1. How many possible combinations of "n" bits are there? Well, bit 1 can take any of the two values (so there's 2 possibilities for bit 1); for any of them, bit 2 can take any of the two values (so there's 2\*2 possibilities for bits 1,2); for any of the combinations of bits 1 and 2, bit 3 can take any of the two values, etc.
2. That depends on the particular way you choose to represent numbers as bits. A popular way is, as pointed out by @didierc, https://en.wikipedia.org/wiki/Two%27s\_complement .

---
Tags: computer-architecture, assignment-problem
---


# Question
Title: Bayes net: algorithm to calculate joint distribution?
I recently started studying bayesian networks and I am now implementing an exact inference algorithm: enumeration. I am aware of the complexity and inefficiency of this method but I want to fully understand it.

As far as I know there are three basic 'steps':

1. Use Bayes Rule on query / evidence variables.
2. Use summation for hidden variables.
3. Calculate joint distribution.

I've tried a recursive approach as suggested in most documentation of the topic, here's the algorithm I'm using (with python):

```
'''
bayesnet is an instance of a class that hold a bayes net
queryVars is a list of tuples (varname, boolean) to describe the state of a variable, eg. ('B', True)
evidenceVars is a list of tuples (varname, boolean)
'''
def enumerate_method(bayesnet, queryVars, evidenceVars = []):
    #Check evidence vars to apply bayes rule
    if len(evidenceVars):
        return enumerate_method(queryVars + evidenceVars) / enumerate_method(evidenceVars)
    #Check if there are hidden variables left given the query variables
    if len(bayesnet.hiddenVariables(queryVars)):
        #For every hidden variable
        for hiddenvar in bayesnet.hiddenVariables(queryVars):
            return enumerate_method(bayesnet, queryVars + [(hiddenvar, True)]) + enumerate_method(bayesnet, queryVars + [(hiddenvar, False)])

    #Calculate joint distribution of queryVars?

    return bayesnet.joint(queryVars)

```

I am still unsure of how to implement the joint distribution calculation. My BayesNet class stores, for each variable, a name, a list of parents and a list of tuples with the probability given its parents. The bayes network is fully described.

I guess I have to use the chain rule, but I have trouble with that as it brings new expressions with evidence variables that I do not have.

Am I moving on the right direction? If so, could you provide a suggestion on how to calculate the joint distribution.

# Answer
You already have the result of the chain rule - this is your networks topology basically. Now you need to compute the joint. I would start from "root nodes", i.e. nodes with no parents, and proceed forward (I'm sure you can go the other way too, just more pain):

* Each of the "root nodes" has its "own" joint already. I.e. if your network was just one root node, you're done - just output the CDF.
* Now suppose your network is two "root nodes". What's the joint? Suppose you have two boolean variables A,B with values a,~a,b,~b. The joint is:

(a,b, P = a\*b)

(a,~b, P = a\*~b)

(~a, b, P = ~a\*b)

(~a,~b, P = ~a\*~b)
* This looks like a cartesian product. I.e. you have a cartesian product in the variables, and the value is the product of terms. This is the simple version of a "factor product" - where factor is some unnormalized discrete distribution.
* In general the product of two factors will encounter variables that are common to the factors. Do the cartesian product and throw out all tuples that match on the common variables - this is the join in databases. Compute the probability as before.
* Now you have the factor product. Just use on your graph to compute the joint. Be careful with paths that separate and then join back in the graph.
> 2 votes

---
Tags: machine-learning, graphical-models
---


# Question
Title: What does does $O$ mean in this context?
I understand big O notation in computational complexity theory, but I don't see how it applies in the equation below.

From *Pattern Recognition and Machine Learning:*

> If we weren't familiar with the rules of ordinary calculus, we could evaluate a conventional derivative $dy/dx$ by making a small change to the variable $x$ and then expanding in powers of $\epsilon$, so that $y(x + \epsilon) = y(x) + \frac {dx}{dy}\epsilon + O(\epsilon^2)$
>
> and finally taking the limit $\lim\epsilon\to 0$.

# Answer
> 3 votes
It means exactly the same thing. It means there is a constant $c$ such that the term is $\le c \cdot \epsilon^2$ (where $c$ does not depend on $\epsilon$). Big-O notation is not unique to computer science; it is also widely used in mathematics. See https://en.wikipedia.org/wiki/Big\_O\_notation, which explains some ways it is used in mathematics.

---
Tags: asymptotics, machine-learning, notation
---


title: R Integer Overflow

text:
# Question
Title: R Integer Overflow
I have a quick question. I have a huge database and I am try to sum all the elements in a column of my data base but there are over 100,000 values and I consequently, get integer overflow (returns NA). How do I get around this in R?

# Answer
> 1 votes
From their documentation on `help(integer)`:

`Note that current implementations of R use 32-bit integers for integer vectors, so the range of representable integers is restricted to about +/-2*10^9: doubles can hold much larger integers exactly.`

So if you are already using `numeric` or `double`, I believe there is no way around it. It would be very helpful though if you present an example of your data or a clarification of your question.

: )

# Answer
> 1 votes
Use the gmp package. This provides arbitrary precision integers (BigInts).

---
Tags: programming-languages
---


# Question
Title: Cutting equal sticks from different sticks
You have $n$ sticks of arbitrary lengths, not necessarily integral.

By cutting some sticks (one cut cuts one stick, but we can cut as often as we want), you want to get $k\<n$ sticks such that:

* All these $k$ sticks have the same length;
* All $k$ sticks are at least as long as all other sticks.

Note that we obtain $n + C$ sticks after performing $C$ cuts.

What algorithm would you use such that the number of necessary cuts is minimal? And what is that number?

As an example, take $k=2$ and any $n\geq 2$. The following algorithm can be used:

* Order the sticks by descending order of length such that $L\_1\geq L\_2 \geq \ldots \geq L\_n$.
* If $L\_1\geq 2 L\_2$ then cut stick #1 to two equal pieces. There are now two sticks of length $L\_1 / 2$, which are at least as long as the remaining sticks $2 \ldots n$.
* Otherwise ($L\_1 \< 2 L\_2$), cut stick #1 to two unequal pieces of sizes $L\_2$ and $L\_1-L\_2$. There are now two sticks of length $L\_2$, which is longer than $L\_1-L\_2$ and the other sticks $3 \ldots n$.

In both cases, a single cut is sufficient.

I tried to generalize this to larger $k$, but there seem to be a lot of cases to consider. Can you find an elegant solution?

# Answer
> 6 votes
The first core observation to solving this problem is that the feasibility of a cutting length $l$,

$\qquad\displaystyle \operatorname{Feasible}(l) = \biggl\[\\, \sum\_{i=1}^n \Bigl\lfloor\frac{L\_i}{l} \Bigr\rfloor \geq k \\,\biggr\]$,

is piecewise-constant, left-continuous and non-increasing in $l$. Since the number of necessary cuts behaves similarly, finding the optimal length is just

$\qquad\displaystyle l^{\star} = \max \\{ l \mid \operatorname{Feasible}(l) \\}$.

Furthermore, as the other answers have proposed, all jump discontinuities have the form $L\_i/j$. This leaves us with a discrete, one-dimensional search problem amenable to binary search (after sorting a finite set of candidates).

Note furthermore that we only need to consider the $L\_i$ that are shorter than the $k$-largest one, since that one is always feasible.

Then, different bounds on $j$ lead to algorithms of different efficiency.

* $1 \leq j \leq k$ results in a search space of quadratic size (in $k$),
* $1 \leq j \leq \lceil k/i \rceil$ in a linearithmic one (assuming the $L\_i$ are sorted by decreasing size), and
* slightly more involved bounds in a linear one.

Using this, we can solve the proposed problem in time $\Theta(n + k \log k)$ and space $\Theta(n + k)$.

One further observation is that the sum in $\mathrm{Feasible}$ grows in $l$ by $1$ for each candidate $L\_i/j$ "passed", counting duplicates. Using this, we can use rank selection instead of binar search and obtain an algorithm that runs in time and space $\Theta(n)$, which is optimal.

Find the details in our article Efficient Algorithms for Envy-Free Stick Division With Fewest Cuts (by Reitzig and Wild, 2015).

# Answer
> 4 votes
As @randomA suggested, we will proceed in two phases: We first find the set of sticks that will be cut and then minimize the number of cuts.

As in the special case in the question, we sort/name the sticks so that $L\_1 \ge L\_2 \ge \dots \ge L\_n$. This takes $O(n\log n)$ time.

As @user1990169 pointed out, we never have to cut a piece $i\ge k$.

In the first phase we employ a binary search to find the number $s$, $1\le s \le k$, so that the sticks $1, \dotsc, s$ can be cut into at least $k$ pieces of size $L\_s$ (plus some smaller pieces), but the sticks $1, \dotsc, s-1$ can't be cut into $k$ pieces of size $L\_{s-1}$. This will take $O(k\log k)$ time.

If $L\_{s-1} = L\_s$, this value is the optimal size and we can skip phase two.

Otherwise we know that the optimal size $o$ satisfies $L\_{s-1} \> o \ge L\_s$ and if $o \> L\_s$ then $o$ results from cutting at least one of the sticks into equal sized pieces. Phase two will determine $o$:

For each stick $i$, $1\le i \le s$, determine a set of candidate sizes as follows: If cutting into pieces of size $L\_s$ turns the stick into $r\_i$ pieces (including the shorter one, if any), then the candidates for this stick are all the values $\frac{L\_i}j$, where $j\le r\_i$ and $\frac{L\_i}j\<L\_{s-1}$. (See @user1990169's answer for why these are the only candidate sizes.)

Maintain for each candidate size, how often it occured. Using a balanced search tree, this can be done in $O(k\log k)$, since the total number of candidate sizes is bound by $\sum\_i r\_i \le 2k$.

Now the candidate size that occured most often and leads to a valid cutting is the one that gives us the optimal solution. Furthermore, if any candidate size leads to a valid cutting, any smaller size will lead to a valid cutting as well.

So we can again employ binary search to find the largest candidate length that leads to a valid cutting in $O(k\log k)$. Then we iterate over the set of candidate lengths up to this threshold and find the one with the largest multitude among them in $O(k)$.

In total we get a runtime in $O(n\log n)$, or $O(k\log k)$, if we ignore (or don't have to do) the initial sort.

# Answer
> 1 votes
After you have ordered the sticks in descending order of their lengths, then a stick $L\_i$ shall be cut only if all the sticks $L\_1, L\_2, ... L\_{i-1}$ have been cut.

Now since $k \< n$, we shall not make any cut on the sticks $L\_{k}$ onwards, since we can always have $k$ sticks with length $L\_{k}$.

So now instead of $n$, we are dealing with only $k-1$ sticks (possibly adding the $k$-th stick as a whole), and the maximum number of cuts that shall be required in the worst case $= k-1$.

**Also, if the optimum number of cuts is $\< k-1$, then there shall be at least one set of sticks among those $k-1$ sticks that shall be taken as a whole from 1 original stick** (either in parts or in 1 piece), i.e., no part of that original stick shall be left 'untaken'. This is because, by *pigeon-hole* principle, there shall be at least 1 cut that shall have to produce more than 1 valid stick.

You can then conduct two nested for loops (both till $k$). Outer loop shall denote the stick number $i$ whose all parts have to be taken and inner loop shall denote the number of parts $j$ made of that stick.
For each size $\frac{L\_i}{j}$ check whether you can get feasible k sticks by cutting sticks $L\_1$ onwards sequentially, and if you can, then update the minimum cuts required so far if the current required number is less.

The total complexity of the above algorithm is $O(nlog(n) + k^3)$

# Answer
> 1 votes
The high level idea would be binary search.

The size of each of the requested k sticks will be at least the smallest stick and at most the biggest one. Because of this, we proceed by using binary search on the size of the middle stick, see what number $k'$ we can obtain, if this $k'$ is more than the given $k$ then we know we need to pick new reference candidate size. So we move to the bigger or smaller using new reference stick. We stop when $k'$ is less than $k$

Once we have found the appropriate reference stick, there is a corner case where we would need to refine the size further. We can sort all the cut sticks by the number of cuts on them and the size of the stick. Pick the one with the least number of cuts and the least size. Reduce the number of cuts on this stick by 1 and making all sub-sticks of this of equal size. This will be the new reference size, check to see if this new size can lead to acceptable $k'$. I admit, I don't know how to bound the running time in this case.

Hopefully, I can see something useful from other answers.

---
Tags: algorithms, optimization
---


# Question
Title: When is a regexp not a Regular Expression?
Since I'm studying for my formal languages college course, I stumbled upon these fascinating posts (One Two) which describe how to find a prime number using a *regexp*. As I said, a ***regexp***, not a **regular expression**. Since a regular expression can match strings computed by a Finite State Automata and finding a prime number can't be done by a FSA, the regexp shown in the blog post is not **entirely** a regular expression since it does backtracking to match the string.

Since I've never really used any regular expression, now, my question:

*How can I immediately recognize a regexp from a "true" regular expression just by looking at it?*

Definitions: By regular expression, I refer to the notion as defined in formal languages. By regexp, I mean the notion supported by modern programming languages; the regexp syntax often contains additional features, such as backreferences. Regexps as seen in programming languages are strictly more powerful than formal languages style regular expressions.

# Answer
> 17 votes
tl;dr backrefs.

As soon as there is a `\1` (or any number that isn't used to escape unicode) in the regexp it is not a regular expression.

Backrefs allows you to match `(a+)b\1` which matches n times `a` followed by b followed by n times `a` for any n\>1. This is not a regular language (it's the poster child of a non regular language).

It is necessary and nearly sufficient that the backref references a group that contains a regexp that matches an arbitrarily long string or that it contains a `*` or `+`. The only exception (that I found) of a regexp of the form `(A)B\1` where A is a finite language (could be replaced by a enumeration of all words that accepts them). You can convert it to `word1+Bword1|word2+Bword2` etc. because A is finite.

Look-around groups don't remove the regularness of the regexp. `A(?=B)C` is the cross-section of regexes `AB.*` and `AC` and the cross-section of 2 regular languages is regular. Negative lookahead is similar except using the complement of `B.*` (complements of regular languages being regular). Lookbehind is exactly the same as well `A(?<=B)C` is the cross-section of `AC` and `.*BC`.

---
Tags: regular-expressions
---


title: Erasing $\epsilon$ production from CFG

text:
# Question
Title: Erasing $\epsilon$ production from CFG
I would like to delete the $\epsilon$-production from the context free grammar with the following rules P:

$$S \rightarrow ASB , BSA, \epsilon$$ $$A \rightarrow aS$$ $$B \rightarrow bB, b$$

Now we were only given this algorithm for that task:

1. collect all variables from which the empty word is derivable.

-\> which in this case is only S

2. Add to the new rules P' every rule $A \rightarrow \alpha'$, with $\alpha \neq \epsilon$, for which P had a rule $A \rightarrow \alpha$, so that $\alpha'$ results from $\alpha$ by erasing all variables that were collected in step 1.

In this case I would erase $S \rightarrow \epsilon$ and since P included $A \rightarrow aS$ I would add $A \rightarrow a$ to P', giving me:

$$S \rightarrow ASB , BSA$$ $$A \rightarrow a$$ $$B \rightarrow bB, b$$

The grammar with these rules does not, however yield the same language as P, in fact the S never disappears. Can anybody please tell me what I'm doing wrong and how to do it correctly?

# Answer
> 5 votes
You cannot erase the $ϵ$-production from this grammar and keep the same language. The reason is that since you have the production $S\to ϵ$, the language contains $ϵ$. And the only way a CF language can contain $ϵ$ is with an $ϵ$-production.

# Answer
> 0 votes
Keep the old productions, you *add* new rules. Some occurrences of $S$ may lead to a nonempty string while other occurrences might lead to nothing, so you need both old and new in general.

Also erase $S$ from the right hand side of productions for $S$ itself.

Thus the new rules now are

$$S \rightarrow ASB , BSA, AB , BA$$ $$A \rightarrow aS, a$$ $$B \rightarrow bB, b$$

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


title: Bloom filter and perfect hashing

text:
# Question
Title: Bloom filter and perfect hashing
A Bloom filter uses a hash function to test membership in a given set $S$, by checking if an item is present of not at the specified position.

To mitigate the effect of hash collision, multiple functions are used, yielding probabilistic bound if using universal hash.

We can use 10 bits per elements to have 'reasonable' error rate.

If we could directly build a perfect hash function for the set $S + \infty$, where the last element is one not present in $S$, then we could use only 1 bit per element and have perfect recovery.

What are the fundamental reasons why this reasoning is wrong ?

# Answer
I think your reasoning is in principle correct. Perfect hashing is an alternative to Bloom filters. However, classical *dynamic* perfect hashing is rather a theoretical result than a practical solution. Cuckoo hashing is probably the more "reasonable" alternative.

Note that both dynamic perfect hashing and standard cuckoo hashing performance is only expected amortized (you might need to rebuild the data structure completely from time to time). Also Bloom filter are easier to implement. This might be arguments for using a Bloom filter, especially if you can live with false positives.
> 7 votes

# Answer
I think the Bloom filter gives you something the perfect hash function does not - it can test membership.

The PHFs I know return some answer for any key you apply them to. If the key you supplied is not in your hash set, some value is still supplied. This is fine if you are storing all of the keys that are in your set somewhere and the PHF just gives a pointer, or if you're only using the PHF to look up satellite data of size $O(1)$ on keys you happen to know to be in your structure. However, membership testing is harder.

In particular, storing $n$ distinct elements without error requires $n \log\_2 n$ bits of storage.
> 2 votes

---
Tags: data-structures, hash, probabilistic-algorithms, bloom-filters, dictionaries
---


# Question
Title: Is this language regular or non-regular: {ww : w ∈ {a,b}* }
This is a question from a text book that's giving me some trouble. The question is:

> Determine whether or not this language is regular. Justify your answer. $$L = \\{ww : w \in \\{a,b\\}^\* \\}$$

I think this language is not regular because $w$ can be of arbitrary length and adheres to no pattern. So, therefore, it cannot be determined whether $ww$ is part of the language using a finite number of states. Am I correct in this assumption, and does my explanation make sense? Thanks for any help you can give me!

My answer, after reading the comments below:

Let $w = ww = (a^p)(b^p)(a^p)(b^p)$. Then consider the Pumping Lemma. Since $|xy| \leq p $ and $|y| \geq 1$, then the $y$ part of the string must be a's. But if we pump up, we'll have more a's in the first part than the second, and $w \neq w \in ww$. Hence, the language can't be regular.

# Answer
Your explanation is correct. To make it more rigorous, assume that L can be recognized by a finite automaton $D$ with $N$ states.

Consider feeding a string $w$ longer than $N$ characters to $D$. Since $D$ has only $N$ states, that means it will go through some state twice. Suppose $w$ can be represented as $w = pqr$, where the state of the DFA is the same before and after $q$.

Then the strings $ww = pqrpqr$ and $pqqq...rpqr$ must be both accepted by $D$, but probably only the first one is in $L$ (some more rigor may be needed to prove that there exists such a string $w$ such that the second string really cannot be in $L$, for some number of repetitions of $q$).

P.S. looks like I unknowingly used the Pumping Lemma.
> 2 votes

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


# Question
Title: What is a non-contrived example of static type-checking being too conservative?
In *Concepts in Programming Languages*, John Mitchell writes that static type checking is necessarily conservative (overly strict) because of the Halting Problem. He gives as an example:

```
if (complicated-expression-that-could-run-forever)
   then (expression-with-type-error)
   else (expression-with-type-error)

```

Can someone provide a non-contrived answer that would really be a practical concern?

I understand that Java allows dynamically-checked casts for cases like this:

```
if (foo instanceof Person) {
    Person p = (Person) foo;
    :
}

```

but I consider the necessity of that more a Java language/compiler deficiency than a cross-language issue.

# Answer
I've always viewed it more as a matter of convenience, than about whether an algorithm can or can not be expressed at all. If I really wanted to run programs like Mitchell's contrived one, I'd just write the appropriate Turing Machine simulator in my statically typed language.

The trick with a static type system is to offer the right kinds of flexibility just for the cases where the flexibility allows you to write code that is more easily maintainable.

Here's some examples of program structuring techniques that are sometimes thought to be easier to manage in dynamically than statically typed languages.

# Generics and Containers

In statically typed languages before ML (c. 1973) and CLU (c. 1974) it was not difficult to create a red-black tree of strings, a red-black tree of integers, a red-black tree of floats, or a red-black tree of elements of specific type `Foo`. It was, however, difficult (maybe impossible) to create a single implementation of a red-black tree that was both statically checked and which could handle any one of these data types. The ways around the problem were (1) to break out of the type system completely (for example: by using `void *` in C), (2) to write yourself some kind of macro preprocessor and then write macros that produce the code for each specific type you want or (3) use the Lisp/Smalltalk (and Java) approach of checking the type of the extracted object dynamically.

ML and CLU introduced the notion of, respectively, inferred and explicitly declared (static) parameterized types, which allow you to write generic, statically typed, container types.

# Subtype Polymorphism

In statically typed languages before Simula67 (c. 1967) and Hope (c. 1977) it was not possible to both do dynamic dispatch and statically check that you had covered the case for every subtype. Many languages had some form of tagged unions, but it was the responsibility of the programmer to make sure that their `case` or `switch` statements, or their jump tables, covered every possible tag.

Languages following the Simula model (C++, Java, C#, Eiffel) provide abstract classes with subclassing where the compiler can check that each subclass has implemented all the methods declared by the parent class. Languages following the Hope model (all the ML variants, from SML/NJ through Haskell) have algebraic subtypes where the compiler can check that every `typecase` statement covers all the subtypes.

# Monkey Patching and Aspect Oriented Programming

Dynamic type systems make a variety of prototyping techniques much easier. In languages where types are represented by hash maps from strings to functions (e.g., Python, Javascript, Ruby) it is quite easy to globally change the behavior of every module that relies on a particular type, simply by dynamically modifying the hash map representing that type.

While there are obvious ways in which monkey patching can be used to make programs harder to maintain, there are also ways in which it can actually be used for "good" rather than "evil". In particular with aspect oriented programming one can use monkey-patching like techniques to do things like modify the file type to point to a virtualized file system, permitting the construction of unit-testing infrastructures for "free", or modify simple exception types so they print log messages every time they are caught for better debuggability.

Unlike Generics and Subtype Polymorphism where the key static checking ideas were available in the 1970s, static checking for aspect oriented programming is (I think) an active research area. I don't know much about it except that there's a language called AspectJ since about 2001.
> 7 votes

---
Tags: programming-languages, compilers, type-checking
---


# Question
Title: (Un)Decidability of disjoint decidable and undecidable sets
I thought of this question today: given are a decidable set $A$ and undecidable set $B$ for which $A \cap B = \emptyset$. Is $A \cup B$ decidable or undecidable?

I am almost sure that it is undecidable but cannot come up with an argument/proof as to why, or even a counterexample.

# Answer
Hint: Suppose you could decide $A \cup B$. Using an algorithm for deciding $A$ and an algorithm for deciding $A \cup B$, can you decide $B = (A \cup B) \setminus A$?
> 6 votes

---
Tags: computability, undecidability
---


title: Can we separate P and E?

text:
# Question
Title: Can we separate P and E?
Let $\mathsf E$ be deterministic exponential time with linear exponent. Do we know that the inclusion $\mathsf P\subseteq\mathsf E$ is strict? If so, what's the proof?

The time hierarchy immediately separates, for instance, $\mathsf E$ and $\mathsf{TIME}(2^{n\log n})$. Diagonalizing directly on $\mathsf P$ yields essentially the same bound (because diagonalizing polynomials gives $n^n=2^{n\log n}$). But none of this yields a *linear* exponential upper bound...

# Answer
Hint: The time hierarchy theorem implies that there is a function $g$ solvable in time $f(n) = n^{\log n}$ but not in time $o(f(n)/\log f(n)) = o(n^{\log n}/\log^2 n)$. In particular, $g$ cannot be solved in polynomial time.
> 2 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Techniques to prove a language is not DCFL
I know that DCFL is closed under complementation and intersection with regular languages. By using these we can prove that a language is not DCFL.

Are there any other techniques that will help me to prove a language L is not DCFL?

# Answer
> 7 votes
There is a direct type of argument, related to the fact that on an input string a DPDA has (at most) one computation (ignoring possible sequences of lambda transitions at the end). Then if one input string is the prefix of another, the computation for the longer string must have the shorter computation as prefix. Thus, the computation accepts at (at least) two moments.

As an example, $\\{ a^n b^m \mid n\ge1, m=n \mbox{ or } m=2n \\}$ is not DCFL; which is seen as follows.

Assume it is. Consider a computation of its DPDA $\cal A$ on input $a^nb^{2n}$. As $a^nb^n$ belongs to the language, the computation must enter a final state halfway the $b$'s. Now rewire $\cal A$ such that from the first final state entered we move to a copy of $\cal A$ where all letters $b$ are changed into $c$. Only keep final states in this copy that are reached after reading at least one $c$. Then the new automaton will accept $\\{ a^nb^nc^n\mid n\ge 1\\}$, which (we know) is not context-free. Contradiction, $\cal A$ cannot exist.

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


# Question
Title: What do we call a function that outputs 0 on half and 1 on the other half of all inputs?
I have a Boolean function that outputs a one on half of its inputs and outputs a zero on half of its inputs, the inputs are assumed to be coming from the uniform distribution. Another way of saying this is the output is one half the time and zero half the time, on average. What is the scientific notation for describing this output scenario?

# Answer
If you absolutely insist on using symbolic notation, you can state that $\mathbb{E}\[f\] = 1/2$ (i.e., the expectation of $f$ is $1/2$, presumably with respect to the uniform measure over all inputs). You could also state that $\hat{f}(\emptyset) = 1/2$ (i.e., the Fourier coefficient at the empty set equals $1/2$), but $\mathbb{E}\[f\] = 1/2$ is probably better. Both of these assume that you already know that $f$ is Boolean.
> 1 votes

# Answer
A boolean function is called *balanced* if it is zero on half its inputs and one on half its inputs. So, "balanced" might be the term you are looking for.
> 3 votes

# Answer
If there's a word for it, use that one (see other answers).

Mathematically speaking, you look at functions $f : X \to \\{0,1\\}$ so that

$\qquad\displaystyle |f^{-1}(0)| = |f^{-1}(1)|$

where $f^{-1}$ denotes the inverse image of $f$.

So this is how one could define the property:

> Let $X$ and $Y$ be finite sets with $|X| \in |Y|\mathbb{N}$. A function $f : X \to Y$ is *balanced* if
>
> $\qquad\displaystyle |f^{-1}(y)| = \frac{|X|}{|Y|}$
>
> for all $y \in Y$.
> 2 votes

# Answer
You could say that that boolean function follows the bernoulli distribution where an outcome of success (outputting a 1), with probability $p = 0.5$, and an outcome of failure (outputting a 0), with probability $q=(1-p)=1-0.5=0.5$. Depending on your context you can also make an output of 0 your success condition and flip your failure condition.

In terms of notation, if $x$, represents an arbitrary input, and you have such a function $f$, you could say $f(x) \sim Bernoulli(0.5)$ and $Pr(f(x)=1) = 0.5$, meaning that the probability of outputting a one on input x is 0.5 and the former porton means that f(x) follows the Bernoulli distribution.
> 0 votes

---
Tags: terminology, mathematical-foundations
---


# Question
Title: Time-complexity of recursive defined code
How would I set up a recursive formula for time-complexity for this code:

```
int b(int n, int x) {
    int erg = x;
    if (n>1) {
        for (int i = 1; i <= n; i++) {
           erg = erg+i;
        }
        for (int k=0; k<3; k++) {
           erg = erg + b(n/3,erg/9);
        }
    }
    return erg;
}

```

Is my assumption correct, that it would be something like this? $$T(n)=n(T(\tfrac{n}{3})+n)$$

But how to deal with the if statement and the second for loop, since it is independent of $n$?

# Answer
> 0 votes
The time complexity depends only on $n$ but not on $x$. You can assume $T(n)$ denote the time complexity. For $n\leq 1$, $T(n)=O(1)$ apparently. For $n\>1$, the first for-loop takes $O(n)$ time and the second for-loop takes $3T(n/3)$ time since it calls $b(n/3,\cdot)$ three times.

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


# Question
Title: Does the proof of undecidability of the Halting Problem cheat by reversing results?
I have trouble understanding Turing's halting problem.

His proof assumes that there exists a magical machine $H$ which could determine whether a computer would halt or loop forever for a given input. Then we attach another machine that reverses the output and we have a contradiction and therefore $H$ cannot exist.

My concern is that it seems as though we are saying an answer is wrong because we reversed it. As an analogy, if there is a machine called $A$ such that outputs a correct answer on certain inputs and an incorrect answer on others. Then we attach another machine that reverses the result of $A$ so the combination the two machines have a contradiction with how $A$ is defined. The two machines now generate incorrect answers for inputs that $A$ is defined to output correct answers and outputs correct answers for inputs that $A$ is defined to output incorrect answers. Would this be called a contradiction, and therefore there does not exist a machine that outputs correct answer on some inputs and incorrect answers on others?

# Answer
**Short version:** The outputs of the machines are not correct or incorrect, they are just contradictory, which proves that the initial machine that *decides* whether the input machine halts on the given string or not can't exist.

**Long version**: First we'll sketch the proof (or at least one version of it - there are many).

1. Assume that we have a Turing Machine $\mathrm{HALT}(\langle M\rangle, x)$ that decides whether the Turing Machine $M$ halts on input $x$ or not.
2. Using $\mathrm{HALT}$ we construct a machine $\mathrm{FLIP}(\langle M\rangle, x)$ which uses $HALT$ to check whether $M$ halts on $x$ or not, then does the opposite, i.e. if $M$ halts on $x$, $\mathrm{FLIP}$ loops, if $M$ does not halt on $x$, $\mathrm{FLIP}$ halts.
3. Finally we create a TM $\mathrm{C}(\langle M \rangle)$ (I ran out of good names), which takes the description of a TM and runs $\mathrm{FLIP}$ with input $(\langle M \rangle, \langle M \rangle)$, outputting whatever $\mathrm{FLIP}$ outputs.

It is important to note that as long as the decider $\mathrm{HALT}$ exists, each of these steps is simple to implement; $\mathrm{FLIP}$ just has to use $\mathrm{HALT}$ to check what to do, and $\mathrm{C}$ just duplicates its input to pass to $\mathrm{FLIP}$.

The contradiction arises when we look at what happens when we run $\mathrm{C}(\langle\mathrm{C}\rangle)$. Either $\mathrm{C}$ halts when given itself as input or not. $\mathrm{HALT}$ will decide this:

* If $\mathrm{C}$ halts on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{Yes}$, but then $\mathrm{FLIP}$ will loop, so $\mathrm{C}$ will loop, contradicting $\mathrm{HALT}$.
* If $\mathrm{C}$ loops on input $\langle\mathrm{C}\rangle$, $\mathrm{HALT}$ will say $\mathsf{No}$, but then $\mathrm{FLIP}$ will halt, so $\mathrm{C}$ will also halt, contradicting $\mathrm{HALT}$.

As each of the steps in the construction is clearly sound, we can only conclude that $\mathrm{HALT}$ can't exist; we have constructed a case where no matter what it says, $\mathrm{HALT}$ can't possible decide what to output, i.e. the problem is undecidable. Just to really hammer on the point a bit, $\mathrm{HALT}$ can't exist - that is there can't be a TM that decides the Halting Problem - because there is at least one case we have explicitly constructed where there is no logically possible answer. Remember a decider is not allowed to output the wrong answer and has to output something, but in the case we have constructed, both possible answers are wrong.
> 21 votes

# Answer
You’re discussing two different meanings of “contradict”.

In your analogy, the machine *A* and its flipped modification contradict each other just in the sense that their outputs are always different. (For instance, they might implement two test functions on integers, “*x* ≤ 5?” and “*x* \> 5?”) That’s certainly one thing “contradict” can mean in everyday usage, but it’s not what is meant by it in logical proofs.

In logical proofs, it means something stronger: something that’s simply impossible. E.g. a function that returns “true” on all inputs more than 5, and “false” on all inputs less than 10 — that’s contradictory in this stronger sense, because for, say, 7, its output would have to be both “true” and “false”, but those are not the same. Turing’s argument shows that the halting program is contradictory in the stronger sense: assuming it leads to something that’s impossible, or already known to be false.
> 7 votes

# Answer
Here is another proof that the halting problem is undecidable. We say that a program *outputs* a string $x$ if it halts and outputs $x$. (If the program never halts, then it doesn't output any string.) Define $f(n)$ to be the length of the longest string which is output by a C program of length at most $n$.

Suppose that the halting problem were decidable. Then $f(m)$ can be calculated by a C program:

> On input $m$, run over all halting C programs of length at most $m$, and determine their output; return the length of the maximal output.

That means that for each $m$, we can write a program $P\_m$ that outputs $f(m)+1$ zeroes. What is the length of $P\_m$? There is a fixed C program template, with a placeholder, that implements $P\_m$; the placeholder should be filled with the constant $m$. Specifying $m$ takes $|m|$ characters (here $|m|$ is the length of the decimal representation of $m$), where $|m| \approx \log\_{10} m$. The template takes some fixed number $T$ of characters, and so the length of $P\_m$ is $T + \log\_{10} m$. If we choose $m$ large enough ($m=2T$ would do), we will have $T + \log\_{10} m \leq m$, and so $f(m)$ is at least the size of the string output by $P\_m$, i.e., $f(m) \geq f(m) + 1$. We have reached a contradiction.
> 2 votes

---
Tags: computability, halting-problem
---


# Question
Title: What kind of subset any class of languages may or may not have?
There are different class of languages, regular,CFL, recursive and r.e. and non-r.e. Clearly a language is set of strings. if an infinite set belongs to any of these classes then what can we say about any infinite subset of that set?

As an example the language $\\{a^n | n\in N\\}$ is a regular language and it is infinite, so is it possible to take a non-recursive or non-r.e subset of this set?

So I would like to know what kind of subsets any of these class of sets may or may not have.

# Answer
> 3 votes
I do not have a general answer as I am not sure this can be actually answered in a single proof. So your question is really too broad, involving many special cases. And I am afraid there are several readings that increase that breadth, because of the expression "may or may not".

Regarding your example, $\\{a^n | n\in\mathbb N\\}$, it is trivially computably isomorphic to $\mathbb N$, as it is $\mathbb N$ in unary notation. So I guess it does have have non-recursive or non-r.e. subsets, just like $\mathbb N$.

But let us consider one simple case to understand what you may be after.

I intend to prove that **there exists a recursive set such that no infinite regular set can be a subset of that recursive set.**

Consider the language $L=\\{a^{2^i}\mid i\in\mathbb N\\}$. It is clearly a recursive set.

Assume that $R$ is an infinite regular set which is a subset of $L$. Then, the language $R$ has a pumping constant $p$. The language $R$ being infinite, it does have a word longer than $p$. Hence you can prove that it contains a sequence of words that differ in length by some constant value $q$. But the definition of $L$ is such that it contains no such sequence.

Hence $L$ contains no infinite subset that is regular.

So there are recursive set that contain no regular subset.

The proof can be transposed to CFL too.

Is that the kind of answer you are looking for?

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


# Question
Title: Polynomial reduction from unbounded knapsack problem to general integer programming
Given an oracle that can solve in polynomial time:

$$a^Tx=b$$ $$x \geq 0$$

So it can solve the feasibility problem with one equality-constraint ($a$ is here a vector and $b$ is a constant, $x$ is required to be integer) and non negativity constraint for the solution. (This problem is also known as unbounded knapsack problem)

With this oracle how can this be solved in polynomial time: $$Ax=b$$ $$x \geq 0$$

where there are arbitrary many equality-constraints ($A$ is here a Matrix and $b$ an vector, $x$ is required to be integer) and non negativity constraint for the solution.

**My thoughts:**

Just finding a solution for every constraint is not enough. You need to somehow be able to find a solution which fulfills all constraints. But i don't see a way? But there has to be way, because both problems are NP-complete.

# Answer
Hint: What do you know about the complexity class of the unbounded knapsack problem? Is it in P? Is it NP-hard?

Now what do you know about the complexity class of LP? Is it in NP?

Think a bit about your answers to those two questions and see if that helps you see one path forward. (There's a short proof of your desired result that doesn't require much detailed mathematics.)

---

Once you've figured that out: if I told you that I was giving you an oracle for some NP-complete problem, what other problems could you use it to solve (in polynomial time)? (Possible hint: Take a look at the definition of NP-complete and think about what the implications of that are...)

---

Once you've worked out that: you should now know there is a reduction. So look at the proofs of each of the steps of reasoning I walked you through. Review these proofs. Those proofs will construct a reduction for you. So, work out what reduction is implicit in the proofs. You should be able to take it from here!
> 1 votes

---
Tags: complexity-theory, reductions, integer-programming
---


title: Is log(n) in complexity class P?

text:
# Question
Title: Is log(n) in complexity class P?
$\log(n)$ is not polynomial; is a problem solvable in $\mathcal{O}(\log n)$ time in P?

$n\times \log(n)$ is also not polynomial; is a problem solvable in $\mathcal{O}(n\times \log n)$ time in P?

If not, what complexity classes contain those problems?

The definitions I've found all refer to "polynomial time", not "at most polynomial time". This may be at odds with $\mathcal{O}$ being defined in terms of bounds, but I haven't found a source which clarifies the discrepancy.

# Answer
Wikipedia says:

> An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the input for the algorithm.

$\mathcal{O}(\log n)$ is upper bounded by $\mathcal{O}(n)$, and $\mathcal{O}(n \log n )$ is upper bounded by $\mathcal{O}(n^2)$, therefore they are both in $P$.
> 21 votes

---
Tags: reference-request, asymptotics, landau-notation
---


# Question
Title: Satisfying assignments, twice-3SAT NP complete
I wanted to solve the following problem about 3SAT . The question is 1. to show if the problem is NP-complete and 2. whether the problem has two different satisfying assignments.

**"*TWICE-3SAT Input*: A propositional formula ϕ in conjunctive normal form, such that each clause consists of exactly three literals (as in 3SAT). Question: Does ϕ have at least two different satisfying assignments?"**

I understand that we have to use reduction of a known NP-complete problem (such as an independent set) to the problem asked. But I can't go further. I would appreciate your help. I have been working on this for almost a week but I cannot go further.

# Answer
Hints:

1. Showing that the problem is NP is easy.
2. To show that it is NP-hard, show first that TWICE-SAT is NP-hard (see next step).
3. In order to show that TWICE-SAT is NP-hard, reduce from SAT. The idea is to add a "dummy" satisfying assignment, which is always going to be satisfying; any satisfying assignment of the original SAT instance will translate to a (different) satisfying assignment of the new instance.
4. Either reduce TWICE-SAT to TWICE-3SAT, or use insights from your proof in step 3 to prove that TWICE-3SAT is NP-hard.
> 0 votes

---
Tags: np-complete, satisfiability, 3-sat
---


title: Questions on Graph and Hamiltonian

text:
# Question
Title: Questions on Graph and Hamiltonian
From this book and other study in complexity theory, I have seen the following statement:

> The definition of NP is not symmetric with respect to yes-instances and no-instances. For example, it is an open question whether the following problem belongs to NP: given a graph G, is it true that G is not Hamiltonian?

However, I was wondering if this this problem was NP-Complete. Could someone let me know if the following statement true?

> Determining a that a Graph is not Hamiltonian is an NP-Complete problem.

# Answer
> 5 votes
No, determining whether a graph is not Hamiltonian is coNP-complete, and it is believed *not* to be NP-complete, indeed not in NP. Determining what a graph *is* Hamiltonian is NP-complete.

---
Tags: complexity-theory, graphs, np-complete, np-hard, decision-problem
---


# Question
Title: Implementing the Schur decomposition of a matrix
I'm trying do implement the Schur decomposition of a matrix, but I can't find any good articles for the theory. Could someone share one?

# Answer
It's italian but it's very clear... Read this:

Shur decomposition

Proposition 6.13
> -1 votes

---
Tags: algorithms, reference-request, matrices, linear-algebra, numerical-algorithms
---


title: Brackets in distributive law?

text:
# Question
Title: Brackets in distributive law?
The (second) distributive law in boolean algebra is defined as

> $A + (B C) = (A + B) (A + C)$

But wouldn't it be correct to define it that way:

> $(A + (B C)\\, ) = (A + B) (A + C)$

Because if you transform

> $(\sim D + \sim C) (\sim D + B + A) (C + \sim B + \sim A)$

to

> $\sim D + (\sim C (B + A) \\, ) (C + \sim B + \sim A)$

it would be incorrect since * has higher precedence than +, so

> $(\sim D + (\sim C (B + A)\\, )\\, ) (C + \sim B + \sim A)$

would be correct, or am I totally mistaken?

# Answer
The real problem is you're making a mistake with the precedence rules being used. The sentence: $$ (\lnot D + \lnot C)(\lnot D + B + A)(C + \lnot B + \lnot A) $$ is ambiguous until we add rules of precedence, or explicitly parenthesise it. Because logical $\mathsf{AND}$ is associative (and commutative), we normally ignore the fact that we have to decide, one way or the other, which of the two $\mathsf{AND}$s applies first.

The normal rules we use (when nothing else gets in the way, go left to right) implicitly parenthesises the sentence as: $$ \[(\lnot D + \lnot C)(\lnot D + B + A)\](C + \lnot B + \lnot A) $$

If we parenthesise in this explicit way, and apply the distributive law, then you get what you expect: $$ \[\lnot D + \lnot C(B + A)\](C + \lnot B + \lnot A) $$

If we changed our rules of precedence to right-to-left and thought about it as $$ (\lnot D + \lnot C)\[(\lnot D + B + A)(C + \lnot B + \lnot A)\] $$ then we can't apply the distributive law at all, we have to apply the associative property first, then we again get what you expect.

In general you have to remember that we often simplify mathematical notation to ease reading, so when you are manipulation expressions, you have to remember that we're leaving things out, or put them back in for clarity.
> 3 votes

---
Tags: boolean-algebra
---


# Question
Title: How to design a Turing Enumerator which either ends with 011 or is of odd length?
This question was asked by my professor in optional brain teaser section, I have tried to solve it for last 48 hours, I am not able to construct a deterministic Turing Machine, Can someone provide hint or something because this seems like impossible to me :( ..

# Answer
I'm assuming you're looking for a Turing machine that *decides* the language $L$ consisting of all words ending with 011 or of odd length.

Hint: You're lucky since $L$ is regular. Construct a DFA for $L$ and rephrase it as a Turing machine.
> 0 votes

---
Tags: turing-machines
---


title: Subgraph isomorphism in planar graphs

text:
# Question
Title: Subgraph isomorphism in planar graphs
I'm a computer engineer trying to understand this Eppstein paper for matching subgraphs in planar graphs.

I'm trying to find subgraph matches to map an application graph (the subgraph) to a network-on-chip (the large graph).

I have already implemented Ullman's subgraph isomorphism algorithm and I'm successfully listing all valid mappings. However it is quite slow for larger inputs. After some research I found that the problem becomes easier for planar graphs. The Eppstein paper provides the mathematics behind planar subgraph isomorphism and claims $\mathcal{O}(n)$ runtime instead of $\mathcal{O}(x^n)$.

Because I don't have a strong mathematics background I was wondering if someone could provide me with:

> 1. An explanation that is simpler than the attached paper of planar subgraph isomorphism. I got as far as tree decomposition but I'm finding the rest very difficult to grasp.
> 2. The pseudo-code algorithm to find subgraphs in planar graphs according to the Eppstein paper, or if there is something with similar/better runtime.

# Answer
I'm not aware of any implementations of planar subgraph isomorphism algorithms, sorry. Note that "SubGemini", which is a (1993) circuit/netlist-oriented subgraph isomorphism solver, doesn't use a planar algorithm, seemingly because they did not want to make planarity assumptions.

For subgraph isomorphism in general (i.e. not planar), the practical state of the art seems to be:

All of these papers have experimental results, so you can get an idea what problem sizes they can handle (which might not be a bad idea to specify in your question).

The paper by Dorn (2009) suggested by Luke Mathieson above seems your best bet if you want to implement planar subgraph isomorphism, but that paper has no experimental results, so... you'll probably be the first to experiment with it.

---

Alternatively, since we're talking subcircuit extraction (SCE) here, you could look at Jiang and Bunke's Marked Subgraph Isomorphism approach for SCE. The assumption there is different than planarity:

> In this case we know a priori that the degree of some vertices is preserved under the subgraph isomorphism mapping. This information is explicitly utilized to develop a polynomial-time algorithm.

I'm a bit skeptical about the applicability of that paper to real-life SCE because the paper was published at somewhat obscure workshop that is not even circuit-focused... But they claim to have soundly beaten SubGemini. The subgraphs searched there are pretty small, a 6 node cell (presumably 6T SRAM cell) is searched and found (in many copies) in a RAM array of several thousand copies. If your application looks like this... it might be what you want.

The 2003 IEEE Potentials article about SCE even though co-authored by Frank Harary alas ignores this paper of Jiang and Bunke entirely, which not really a surprise to me given where it was published. You may want to read that brief for pointers to other approaches to SCE, including genetic algorithms, neural networks etc. A couple of SCE papers indicated in that brief as claiming good practical results are:

Not covered in that review because it's slightly newer is FROSTY; it works by matching smaller directed (sub)graphs by doing a first pass identifying gates. In its paper, results are only compared to SubGemini though, which isn't that hard to beat.

Somewhat similar (in the sense that it relies on higher-level graphs that are in a certain sense directed) but broader in scope (in the sense that it handles both exact and approximate matching) is "Pattern Search in Hierarchical High-Level Designs" by Terem et al. from Intel + Moshe Vardi. The way they handle both exact and approximate matching is setting up both problems a constraint satisfaction problems.

Also probably worth looking at is a series papers by N. Rubanov 2006; 2002; his methods are probabilistic, but they all beat SubGemini by orders of magnitude. Rubanov worked in the EDA industry (Circuit Semantics, Magma Design Automation, Cadence).

There also three fairly recent Oracle (prbably Sun labs) patents by Douglas C. Meserve in this area: US7958468, US7861193, US8788990. I couldn't find any academic publication related to these patents.

The most recent comprehensive SCE work I found (insofar) is a 2009 Ph.D. thesis "Hierarchical Pattern Matching in VLSI" by M. Miloševic.

As an interesting addendum, SubGemini is based on the Conneil and Gotlieb partitioning, which has its issues, in these sense that its correctness is based on a conjecture that was eventually proved false by counterexample.
> 6 votes

---
Tags: algorithms, graphs, graph-isomorphism, planar-graphs
---


# Question
Title: Can anyone help me understand the matches to this regular expression?
My professor gave us this pattern "/\[aeiou\]+\[1234567890\]\*\[a-z\]?/" and I'm trying to find matches in "ae12abc r2d2 a1steaksauce".

The resulting matches the professor gave us are ae12a, a1s, eak, auc, and e.

I think I'm totally misunderstanding how this is supposed to work. Why are ae12abc, r2d, or a1steaksauce not possible matches? Thanks in advance, I really appreciate any help with this!

# Answer
> 4 votes
Well let's walk through it. You need one or more vowels, followed by any number of numbers (including *none*), followed by (optionally) a letter.

`ae` matches your vowels, `12` matches the numbers, then `a` counts as your optional letter. The engine starts again and looks for the next vowel. It skips `bc r2d2` since there are no vowels there.

Then it finds `a` for your vowels, `1` for your numbers, and `s` as the optional letter. Then the engine starts again and looks for the next vowel.

It finds `ea` for your vowels. There are no numbers, so it grabs `k` as the optional letter. Then it starts again looking for vowels...

# Answer
> 2 votes
Why `ae12abc` is not a match: `ae` matches the `[aeiou]+` part of the regexp, `12` matches the `[1234567890]*` part, but `abc` doesn't match `[a-z]?`, because `[a-z]?` matches the empty string or any single letter, and `abc` is not a single letter.

Why `a1steaksauce` is not a match: the same reason. `steaksauce` is not a single letter.

Why `r2d` is not a match: `r` doesn't match `[aeiou]+`.

---
Tags: regular-expressions
---