# Question
Title: How do I follow the text of this Longest Common Sequence proof?
I'm working through a proof that is a simplified version of David Maeirs **LCS** reduction from the **VERTEX**-**COVER** problem and I had a question about a specific set of instructions and how to execute them by hand.

Background Information This works out to look like the below as a graph (please excuse the grid lines)

The part I don't understand of the proof

Now I think this would imply that I need to line up S0-S7 vertically and using that rule show I can find the LCS, which was shown in my proof to be

> $$00000001000000000000000000000100000000000000100000001$$ $$0^710^{21}10^{14}10^71$$

I tried doing that but was unable after many attempts to show that I could in fact induce $Topt$ from the sequences below. Could someone explain where I'm going wrong here? Did I misinterpret the instructions?

> $S0 =00000001000000010000000100000001000000010000000100000001$
>
> $S1 =00000000000000100000000000000100000001000000010000000100000001$
>
> $S2 =00000001000000000000001000000000000001000000010000000100000001$
>
> $S3 =00000001000000000000001000000010000000000000010000000100000001$
>
> $S4 =00000001000000010000000000000010000000100000000000000100000001$
>
> $S5 =00000001000000010000000000000010000000100000001000000000000001$
>
> $S6 =00000001000000010000000100000000000000100000000000000100000001$
>
> $S7 =00000001000000010000000100000001000000000000001000000010000000$

EDIT: I tried everything I could think of to see if I could make any of them work but didn't think it was relevant enough to include, if you want to know what I did I can list them.

# Answer
The two red-underlined parts of the proof is to **standardize** an LCS solution, that is called $T\_{opt}$ therein.

The idea is to push all the $0$'s farthest possible to the right (without passing through its nearest $1$ to the right).

Consider the following two strings:

$s\_1=0001000100010001$ (i.e. $n=4$ vertices)

$s\_2=0001000\ 00010001000$ (where the space is for visualizing purpose only) (i.e. $u=2$, $v=4$)

A common subsequence (not necessarily longest) can be: $s=0001000 00010001$ (i.e. $u$ is omitted)

The standardization process in the proof is to actually align $s$ against $s\_1$, $s\_2$.

And, this MUST be standardized to be as follows:

`s1= 0001 0001 0001 0001`

`s2= 0001 000 0001 0001000`

`s = 0001 000 0001 0001`

Similarly, if we omit $v$, then $s=000100010001000$

And, this should be standardized as follows:

`s1= 0001 0001 0001 0001`

`s2= 0001 000 0001 0001 000`

`s = 0001 0001 0001 000`

Finally, we will be able to construct an $n^2+k$-long common subsequence if there exists an independent set of size $n-k$, where for each edge $\\{u,v\\}$, we omit at least one of them (the ones that are in the independent set) so that it is possible to align like we do above (note that each edge-string $e\_j$ contains only $n-1$ symbol $1$'s). And lastly, by complementing a $k$-VC, we have an $(n-k)$-IS.
> 1 votes

---
Tags: np-complete, reductions, np-hard
---


# Question
Title: Prove that $H$ reduces to $H\varepsilon$
I have to prove that $H\_\varepsilon = \\{\<M\> \mid M\ \text{halts on input }\varepsilon\\}$ reduces to $H$ (the halting problem).

I am very confused how to PROVE it, I mean it is clear that we can take a TM $M$ that decides $H$ and then build a TM $M\varepsilon$ that decides $H\varepsilon$ by taking the input $\<M1\>$ and simulating $M$ on input $(\<M1\>, \varepsilon)$, then accepting when $M$ accepts.

But how do I prove I can do that, how do I prove that this mapping from $H$ to $H\_\varepsilon$ exists?

# Answer
This can be done by hard-coding a pre-processing stage to paste down $x$ to the input tape, before actually running $M$ on $x$ as input.

So given an instance $\<M,x\>$ of HALTING, you transform $M$ to $M\_x$ that submerges the input $x$ into its initial stage. This can be done efficiently.

For example, if $x=010$, then start from the starting state $q$ of $M\_x$ at left-marker $\\$$, it moves one step to the right, and changes to state $q\_0$. Then, $M\_x$ prints out $0$, moves the head one step to the right and changes to state $q\_1$. Then, $M\_x$ prints out $1$, moves the head one step to the right and changes to state $q\_2$. Then, $M\_x$ prints out $0$, moves the head one step to the right and changes to state $q\_3$. Then, $M\_x$ moves all the way left back to the left-marker $\\$$. Then, $M\_x$ changes to the very starting state $q\_M$ of $M$ and passes the control to $M$. Now, $M$ receives $x$ as input on the tape.

The above behavior of $M\_x$ should be coded as its transition table. The description of $M\_x$ is the produced instance of $H\_\varepsilon$.

Finally, $M$ halts on $x$ iff. $M\_x$ halts on $\varepsilon$.
> 1 votes

---
Tags: turing-machines, reductions, undecidability, halting-problem
---


# Question
Title: when to use preorder, postorder and inorder binary search tree traversal strategies
What are some examples of when to use preorder/postorder practically? When does it make more sense than in-order?

# Answer
> 4 votes
"Whatever you want in your application. This is like asking when you should drink beer, orange juice or water", commented by one wise user, Gnasher729.

"You use whichever gives you the results you need. Your question is like asking 'What are some examples of when to use subtraction/multiplication practically? When does it make more sense than addition?'", commented by another wise user, David Richerby.

What do the above similes mean exactly? **If you have understood what are preorder/postorder and inorder traversals clearly, it becomes obvious for you to choose which one make more sense to use.**

So the best answer could simply be reviewing the definition of those traversals. Here is one way to understand them in the usual context of binary trees.

* A preorder traversal visits the root node first, followed by a preorder traversal of the left subtree, followed by a preorder traversal of the right subtree.
* An inorder traversal does an inorder traversal on the left subtree, followed by a visit to the root node, followed by an inorder traversal of the right subtree.
* A postorder traversal does a postorder traversal of the left subtree, followed by a postorder traversal of the right subtree, followed by a visit to the root node.

In a nutshell, each traversal traverses a binary tree recursively. The "pre/in/post" refers to when the root node, which store the value in the middle, is visited, which is first, between first and last, and last respectively. Note that left subtree is always visited before right subtree.

Understanding cannot be solid without relevant examples and exercises. You may check for example chapter 12, "Binary Search Trees" of CLRS to find some.

Here are some usual usage examples.

* Preorder traversal is used to get prefix expression on of an expression tree, Polish notation
* Postorder traversal is used to get postfix expression of an expression tree, reverse Polish notation
* In case of binary search trees, **inorder traversal will traverse nodes in non-decreasing order**. This is probably the easiest result if not the most common result. To traverse nodes in non-increasing order, inorder traversal but visiting right subtree before left subtree can be used.

---
Tags: data-structures
---


# Question
Title: Load and Store Data hazard problem in 5-stages pipeline
Hi everyone and first of all thank you for been reading. I'm a little confused about data hazard dependences when a "Store" instruction is followed by a "Load" instruction. (Assume that we're working with a 5 stages pipeline processor withouth data forwading paths)

So if I have the following code now:

```
Store R3,R8,off-1
Load R3, off-2

```

If we've had ADD and Subsract instructions instead of "store" and "load" we'll have data hazard dependences, so we would have to "wait" for the result using No-Op, but in this case; can I start "fetchig" the second instruction while the first one is on "Decode" stage?

I think I'm missing some concepts here, as to where the operand is fetched from and where it gets stored to.

Thank you.

# Answer
> 0 votes
Assuming the stages are IF, ID, EX, MEM and WB, I believe the Load instruction cannot be carried out until the value has been written back in the first instruction i.e the WB stage.

This is what happens in the ID stage (from Hennessey-Patterson, Computer Architecture - A Quantitative Approach 4 ed.):

> Decode the instruction and read the registers corresponding to register source specifiers from the register file.

Since we have to read the registers in the ID stage, this cannot be done until the WB stage of the previous instruction has been completed as otherwise, it would lead to reading an incorrect value.

EDIT: On further notice, I've realised this might be incorrect. I wrote this answer under the assumption that the Store instruction passes through all the five pipeline stages. However, here, it is mentioned that:

> The store instruction stores to memory, so the "write" is performed inside MA.

So it won't have to wait till the WB stage, it can read the value after the MEM stage of the previous instruction.

That being said, more details about the instruction set would be helpful and how exactly are Load and Store defined would be helpful.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: Why not use Right Recursion to avoid Left Recursion?
I am reading about Representative Grammars from book, where I encountered the following grammar:

$$ E \rightarrow E + T \ | \ T $$ $$ T \rightarrow T * F \ | \ F $$ $$ F \rightarrow (E) \ | \ id$$

The above grammar is left-recursive, which is bad. So in order to eliminate left recursion, they changed it to the following:

$$ E \rightarrow TE' $$ $$ E' \rightarrow +TE' \ | \ \epsilon $$ $$ T \rightarrow FT' $$ $$ T' \rightarrow \*FT' \ | \ \epsilon $$ $$ F \rightarrow (E) \ | \ id $$

But why bother so much? Why not simply use a right recursion instead, like the following:

$$ E \rightarrow T + E \ | \ T$$ $$ T \rightarrow F * T \ | \ F$$ $$ F \rightarrow (E) \ | \ id$$

* So I am confused about whether the Right Recursive Grammar I thought of is same as the original grammar or not?
* If not, what's the difference?
* If they are same, why don't we write all grammars as Right Recursion?

# Answer
The left recursive and the right recursive grammars describe the same language. But grammars do more than give the set of allowed strings in the language, they also give a structure to such strings and that structure is sometimes meaningful. Consider `a+b+c`; the structure implied by the left recursive grammar is `{a+b}+c` (I'm using braces and not parenthesis to show the structure to avoid confusion with the common mathematical meaning of parenthesis) the structure implied by the right recursive grammar is `a+{b+c}`. If mathematically both are equivalent for addition, it is not the case for all operations. Consider subtraction `a-{b-c}` is not equal to `{a-b}-c` and that is the later that we usually consider the value of `a-b-c`.

The version with left-recursion removed is also right-recursive. But its structure is different, and easier to map to the desired structure. With `a-b-c-d` we have `{{a-b}-c}-d` for the left-recursive structure, `a-{b-{c-d}}` for the right-recursive and `a{-b{-c{-d}}}` for the result of left-recursion removal; that structure allow more easily than the right recursive one to get the intended meaning.
> 8 votes

# Answer
You can use a grammar to *recognize* a language, but usually you want more: You want to know how a string was *parsed*. (That's why we want grammars that are unique, otherwise there are sentences that can be parsed in more than one way).

Your changes don't change the language that is recognised, but they change the parse tree. If the sentence is a - b + c, then a left recursive parser might parse it as an operator "+" with two operands "a-b" and "c", while a right recursive one parses it as an operator "-" with operands "a" and "b+c". That's a huge change in meaning. If you want the sentence to mean "take a, subtract b, add c" then you need a lot of extra work with the right recursive parser.
> 1 votes

# Answer
The reason is, associative of the operators will change in the grammar that you have mentioned which may yield a different result But the right recursive grammar given in the book maintains associativity thus giving the same language.
> 0 votes

---
Tags: compilers, left-recursion
---


# Question
Title: Properties of Reverse Polish Notation expressions that are algebraically invariant
The RPN expressions

```
a b + c *

```

and

```
f d e + *

```

are algebraically equivalent, though the names of the variables are different and the order of evaluation is slightly different. The expressions

```
a b * c +

a b * c *

```

though they have the same length and number of variables as the first expression, are not algebraically equivalent, i.e. in general

```
c (a + b) ≠ c + a * b
c (a + b) ≠ a * b * c

```

Without substituting values for any of the variables, is there a property that we could compute which is the same for `a b + c *` and `f d e + *` but not for `a b + c *` and `a b * c +` or `a b * c *`?

Assume the variables are real numbers, not e.g. matrices, so `+` and `*` are commutative, but `-` and `÷` are not.

This is a simple example of a broader question I am interested in: what are some properties that RPN expressions (i.e. unambiguous expression trees) have that are different for algebraically different expressions but do not change when the names or order of evaluation of the variables change?

This would be useful because it would be a kind of fingerprint for algebraic expressions that would not change merely because of choice of variable names.

I realize that this could be a big topic; references to sections of textbooks or research articles are welcome.

# Answer
> 1 votes
You ask for a computable property that can be used as a fingerprint for equivalence (algebraic equivalence in your case). There are two general approaches to this kind of question:

1. Take a canonical element of the equivalence class (a normal form) as the fingerprint.
2. Take the equivalence class itself as the fingerprint. Of course this requires classes to be finite. For computability of the equivalence class we also need a computable bound on the size of members of the class. (Plus decidability of equivalence. But that is a general requirement, because fingerprints imply this decidability.)

In this answer I only consider the case where you only have addition, subtraction, and multiplication. None of your examples has division, so I assume that this restriction already is relevant for you. In this case, an algebraic expression essentially (up to syntax) is a multivariate polynomial. For example, the expression $x\cdot(x-z-z)$ yields the polynomial $x^2-2xz$ (more precisely $\sum\\{x^2, -2\prod\\{x,z\\}\\}$, to stress that polynomials do not carry information about the order of additions or multiplications. That is, $x^2-2xz$ is *the same* polynomial as e.g. $-2zx+x^2$). This polynomial is already close to the fingerprint you want: Different polynomials are extensionally different over the real numbers. Which means that they can be shown to be different by subtituting suitable real values. Hence polynomials are normal forms for expressions.

Renaming of variables is not yet covered. (Also observe that normalizing to polynomials may have the effect of losing variables: $x+y-x$ would be normalized to $y$, in which $x$ does not occur any more.) But we can take equivalence classes of polynomials: The degree and number of monomials imply a size bound. Equivalence is decidable just by trying out variable renamings. With canonical variable names $x\_1, x\_2, x\_3, \ldots$, the above polynomial $x^2-2xz$ yields the equivalence class $\\{x\_1^2-2x\_1x\_2, x\_2^2-2x\_1x\_2\\}$.

While we have achieved computability, we do not yet have efficiency. So, can we do any better? Can we have a normal form for polynomials? If you consider the special case where all monomials are the product of two distinct variables (like $x\cdot y$), the problem of canonizing polynomials becomes graph canonization, whose complexity is unknown.

---
Tags: notation, computer-algebra, equality
---


# Question
Title: Randomly construct linear combination that is within bounds over two basis
Given rank deficient matrix $A$, I want to randomly construct vectors $\vec{x}$ such that:

1. $0 \le x\_{j} \le 1$
2. $0 \le b\_{j} \le 1$ where $\vec{b} = A\vec{x}$

Matrix $A$ is about 10 x 15. I want to generate $10^{5}$ $\vec{x}$ as an initial guess in each iteration of a solver.

Below is my attempts.

---

*Least square and rejection*

1. Generate $\vec{y}$ with entries between 0 and 1.
2. Generate $\vec{b}$ with entries between 0 and 1.
3. Minimize $(\vec{y} - \vec{x})^{2}$ subjected to constraint $A\vec{x} = \vec{b}$.
4. Reject $\vec{x}$ that are out of bounds.

Problem: the rejection rate is very high. Very impractical even for a 10 x 15 matrix $A$.

Step 2 is equivalent to solving

$\begin{bmatrix} A & 0\\ I & A^{T} \end{bmatrix} \begin{bmatrix} \vec{x}\\ \vec{\lambda}\\ \end{bmatrix} = \begin{bmatrix} \vec{b}\\ \vec{y}\\ \end{bmatrix} $

---

*Constrained Optimization*

* Generate random $\vec{y}$ within bounds.
* Objective: $(\vec{x} - \vec{y})^2$.
* Constraint: $A\vec{x} = b$
* Bounds: between 0 and 1.

Problem: Optimization is too slow and often gives result out of bounds. Impractical.

---

*Other ideas*

* Null space
* Simplex, random planes, and projection
* Hit and run sampling

# Answer
Using barycentric coordinate and keeping sum of coordinate equal to 1 do not sample a convex polytope uniformly.

```
import numpy as np
import matplotlib.pyplot as plt

N = 1000000  # Number of samples
V = 5 # Generate points within a V-gon

# generate columns that each sum to 1
s = np.exp(-np.random.uniform(0, 1, size=(V, N)))
s /= s.sum(axis=0)

# generate vertex of regular polygon
r = 2
theta = np.linspace(0, 2*np.pi, V+1)[1:]
v_x = r*np.cos(theta)
v_y = r*np.sin(theta)

# generate random points within the polygon
# by linear combination of coordinates of
# vetex where the coefficients sum to 1.
x = (v_x[:, np.newaxis] * s).sum(axis=0)
y = (v_y[:, np.newaxis] * s).sum(axis=0)

# plot density
heatmap, xedges, yedges = np.histogram2d(x, y, bins=50)
extent = [-r, r, -r, r]

plt.clf()
plt.imshow(heatmap.T, extent=extent, origin='lower')
plt.plot(v_x, v_y, color='r')
plt.show()

```
> 1 votes

---
Tags: linear-algebra, monte-carlo
---


# Question
Title: Does an abstract syntax tree have to be a tree?
Does the output of a parser have to be a tree or could it also be general graph?

Moreover, is there any existing language or a plausible one that uses general graphs representation instead of trees for their syntax?

# Answer
The output of a parser need not be a tree. Indeed, when you consider things such as references from the USE of a variable to its DEFinition overlaid on the abstract syntax tree, you immediately have a graph.

The thing is that parsing generally is designed to take place in a single pass – this mattered for historical reasons, such as lack of space and processor speed, but also because it is simpler to reason about. Then subsequent phases decorate the parse tree with additional information.

There are such things as graph grammars, though I don't know whether they are used for parsing programming languages.
> 16 votes

# Answer
The OP's question is a bit backward stated. Of course, a parsing algorithm can output whatever it wants. The question is more to understand what parsing is for and whether the parser outputs a result that meets this goal. Then one can wonder what is the appropriate representation for that, for example a tree or a graph.

Well, I guess a parser is an algorithm that will give you the syntactic structure of a sentence given as input, according to a given formal definition of the syntax of the language.

Note that people may disagree on what constitute the syntax of the language. Some may limit that to a pure formal language backbone, while other may introduce slightly more semantical considerations such as type, genre, number or other more complex ones (I am not distinguishing NLP or programming languages). Most languages have features that require graphs to be represented, but it is up to the "implementor" (for lack of a better word) to decide whether he wants to include that in the syntax.

So depending on what you define the syntax to be, you may have to output a different kind of formal structure.

In the simple case of pure Context-Free parsing, a parse tree may do, except for the problem of ambiguity addressed below, or for the fact that you may want to modify it a bit to get an AST (see below).

However, in more complex cases, you may need different structures, often represented by links in the tree, thus leading to a graph structure. This depends very much on your definition of the language syntax.

Also, what tree you should output is not obvious. If you take the case of tree-adjoining grammars (TAG), they work in such a way that the syntax tree is not the same as the derivation tree, though the former can be derived fron the latter. Which you want to output may be a relevant question.

There is also another issue regarding ambiguity. A given sentence, while belonging to your language, may do so in many different ways, may be assigned a syntactic structure in many different ways.

Then you can choose to output just one of these structures, chosen randomly or according to some well defined criterion (likeyhood for example). You may also choose to output several or all of them. If you want to output several, it is usually comvenient to pack then in a unique structure that will share what they have in common. This save on space and on computing time, and complexity may be a real issue.

When you choose to output all of them, you have no choice but to share, because there may be an infinite number of possible parses. And infinitely can be represnted finitely only by having somehow a cycle in a graph. So you have to produce a graph structure in general. But the properties of this graph structure with be related to the kind of formal syntax you have chosen.

## About Abstract Syntax Trees

Now the question was also about Abstract Syntax Trees. I skipped the "abstract" part since it would bring confusion, imho. Indeed the question is already confusing in its various restatements.

Regarding AST in historical perspective, they originate with the language Lisp and program manipulations systems in the years 1960-1970. The idea was to consider programs as large expressions, as mathematical formulae, both for manipulation purpose and to analyse properties or define semantics in a formal way, which mathematicians know how to do on formulae. As formulae, they were naturally tree structured, but could be decorated with various information that turned these trees into graphs. This was convenient both formally and pragmatically and was further used by compilers and programming systems.

So fundamentally, an AST is a tree, as implied by the name, but can carry further information. The rest is in the choices of the implementor and in the eyes of the beholder. Is it a graph or a decorated tree? However, the basic AS tree matters, because that is the scaffolding you build on both in theory and in programming.

Note that the AST was distinct from the parse tree (syntax was context-free based) as produced by parsing algorithm as studied in formal language theory. The reason was that the design of the syntax was constrained by the parsing technology of the time, itself constrained by the low computing power available. The result was that syntax trees were only tortured variants of what one would naturally consider the structure of the program, and further processing, not reallly part of the basic formal parsing process, had to be performed to get the cleaner and simpler version called AST.

However, the representation of trees on the computer, whether abstract or not, are somewhat constrained when you want to represent all structures of an ambiguous sentence. In particular, this hides complexity issues. Preservation of ambiguities in a graph structure, while translating from parse trees to AS Trees may also be an issue. However, if you are concerned with that, it is often possible to define your concrete syntax in such a way that the parse tree can serve as AST. This is permitted by the very general algorithms that handle ambiguity, and by the power of current computers.
> 4 votes

# Answer
If you parse using GLR parsing (Generalized LR), and if the parse of the input is ambiguous (there are multiple possible ways to parse the input), then the result of the parse can be thought of as a parse DAG, rather than a parse tree. The parse DAG compactly encodes many possible parses: multiple possible parse trees.

However, the bottom line remains that if you have a context-free grammar, and if your input string is unambiguously parseable (there is only a single derivation in the grammar that produces this input string), and if the job of parsing is to produce that derivation ... then under these conditions, the output of parsing will always necessarily be a parse tree, because any production of a context-free grammar inherently has a tree structure.
> 1 votes

# Answer
In NLP, abstract syntax representations are directed acyclic graphs (DAGs). The situation when two edges point to the same node is called "structure sharing".
> 0 votes

# Answer
I once wrote an interpreter for C in which the "AST" for the += operator (for example) was not a tree. Consider `a[i++] += d` where `a[i++]` is `int` and `d` is `double`. The implicit conversion and fetch operations were explicit in the tree, so the problem is where to put the fetch of `a[i++]` and the conversion to double. Our solution was to abandon trees. The resulting "ASG" looked like this

```
         +=
       / | \
      /  |  \
     /   |   \
    / convert \
    |     |    \
    |   fetch  fetch
    |   /       |
    index       d
    /  \
   a   postinc
       |
       i

```
> 0 votes

# Answer
I was puzzled by this myself, until I have just realized that it is not the tree that is abstract, neither it is about some abstract "syntax tree," but the *syntax* is abstract.

So, to answer your question, I conclude that an abstract syntax tree, as well as a concrete syntax tree or a decision tree, or any other tree, should better be a tree.

On the other hand, nothing should prevent anyone from using an abstract syntax graph, or an abstract syntax diagram, or an abstract syntax cube, or an abstract syntax specification.

I suppose an abstract syntax tree of "abstract syntax tree" would have helped me to avoid the confusion.
> 0 votes

---
Tags: compilers, parsing
---


# Question
Title: Two's complement max with a different base
Working with fixed size integer representations, use a number system with b-complement notation, base b = 9 and n = 4 digits. What is the smallest number that can be represented in this number system? State the number in decimal, and also express it in this number system. I assume that it will be 0888 for max, and 8000 for min. If I am right, then what is the max number of integers that I can represent using this notation.

# Answer
As long as different 4 digit numbers in base b represent different decimal numbers, the particular notation one uses is not relevant to see how many integers can be represented. I'm not sure how the two-complement notation generalizes to the b-complement notation, but if the above property holds, then clearly there will be 9^4 representable integers.

My guess is that the first digit does not need to be 0 or 8, it can be any digit. That is, I think one could use the following encoding:

0000 0
...
4444 MAX
4445 MIN = -MAX
4446 MIN+1
...
8888 -1
> 0 votes

---
Tags: number-theory, number-formats
---


title: longest sub-sequence in both directions

text:
# Question
Title: longest sub-sequence in both directions
Given a character array A of size n, compute the length of a longest sub-sequence S of A such that, S read backward is also a sub-sequence of A.

Example: A = cabca

the sub-sequence S = abc is the longest of such sub-sequences.

reading S forward (abc): c**abc**a

reading S reverse (cba): **c**a**b**c**a**

How to compute the length of such an S ?

# Answer
> 2 votes
One option is to reduce your problem to *Longest Common Subsequence*. I'll let you figure out how.

---
Tags: algorithms, dynamic-programming, strings, subsequences
---


# Question
Title: Proving $L = \{a^nb^m \mid n, m≥0, n \neq m\}$ is not regular by use of Pumping Lemma
I've been struggling with this problem for quite a while now and every explanation I have managed to find doesn't seem to correctly solve it.

## Question

Proving $L = \\{a^nb^m \mid n, m≥0, n \neq m\\}$ is not regular by use of Pumping Lemma. I know the correct way of prove with factorial or using closure. However today someone explain a way to me and I couldn't find what is wrong with it. I think it is wrong but if it is true, is it possible to explain why?

## Proof (Maybe correct):

we suppose that that $L$ is regular and there is a machine with $u$ state that accept it. **If it is a NFA, we can convert any NFA to DFA with for example $k$ state.**
We have a group of strings like $a^kb^{k + t}$ for every $1 \le t \le k$ which accepted with machine.
**There is only one way for read $a^k$ because our machine is DFA so we can write $a^k = a^sa^ta^p$** that $|a^sa^t| \le k$ and $|a^t| \ge 1$ and $a^t$ is cycle, so with pumping lemma we can say that $a^{k + t}b^{k + t}$ (with one more time of cycle) belongs to $L$ and it is contradiction. (**one of our strings in our first group will fail**) so our language is not regular.

---

### My Problem

Because we we get a group of strings (instead just one strings which is normal in proves) and use same $t$ when break $a^k$ to $a^sa^ta^p$, is it true anymore? If no or yes, please explain.

### My explanation

I think we can construct a NFA that accept each of $a^kb^{k + t}$ (for each $t$) with different size of cycle (cycle that is used in pumping lemma) however when convert it to a DFA, I can't understand how to prove it.

# Answer
This is a trick question. Your proof doesn't quite work, but can be turned into a proof, as follows.

Let $p$ be the constant in the pumping lemma, and consider the word $a^pb^{p+p!} \in L$. According to the pumping lemma, it can be decomposes as $xyz$, where $|xy| \leq p$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. Since $|xy| \leq p$, we must have $y = a^q$ for some $q \leq p$; since $y \neq \epsilon$, we must have $q \geq 1$. Let $i = p!/q + 1$. Then you can check that $xy^iz = a^{p+p!} b^{p+p!} \notin L$, contradicting the pumping lemma.

Here are two more proofs. The first uses closure properties. If $L$ were regular then so would the following language be: $a^\*b^\* \setminus L = \\{ a^nb^m : n = m \\}$. However, this language is known to be non-regular.

Another proof uses Myhill–Nerode theory. Let us say that two words $x,y$ are *incomparable* if there exists a word $z$ such that $xz \in L$ but $yz \notin L$, or vice versa. In any DFA for $L$, we must have $\delta(q\_0,x) \neq \delta(q\_0,y)$ (why?). Therefore, if we can find an infinite collection of pairwise incomparable words, then the language is not regular (why?). In the case of $L$, such a collection consists of the words $a^i$ for all $i \geq 0$. Indeed, if $i \neq j$ then $a^ib^j \in L$ whereas $a^jb^j \notin L$, showing that $a^i,a^j$ are incomparable.
> 2 votes

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


# Question
Title: How is the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem?
Could anyone briefly show me how the Longest Common Sub-sequence of two sequences is a special case of the Sequence Alignment problem? I cannot wrap my head around this. Thank you.

# Answer
The problem of finding a longest common subsequence can be answered by computing the alignment where match is rewarded by +1 while mismatch and insdel penalty are both 0.
> 2 votes

---
Tags: algorithms, subsequences
---


title: Grammar for ${a^n b^n c^{n+m}}$

text:
# Question
Title: Grammar for ${a^n b^n c^{n+m}}$
Can we define a grammar for the following language?

$$L = \\{a^n b^n c^{n+m} | n,m\>=0\\}\\,. $$

I can define one for this:
$$L=\\{a^nb^n|n,m\>=0\\} $$

> S --\> aSb | λ

or this one: $$L=\\{b^nc^{n+m}|n,m\>=0\\} $$

> S --\> Ac
> A --\> bSc | Sc | λ

but I can't solve the first one, any hint?

# Answer
> 0 votes
This gives the language: $L = \\{a^n b^n c^n c^m | n,m\>=0\\}\\,. $

1. S → a b c C | N | ε
2. N → a N B c C | a b c C
3. c B → W B
4. W B → W X
5. W X → B X
6. B X → B c
7. b B → b b
8. C → c C | ε

# Answer
> 3 votes
**GRAMMAR FOR THE LANGUAGE:{a^n b^n c^n/n\>=1}**

S-\>abc|A

A-\>aABc|abc

cB-\>Bc

bB-\>bb

**FOR EXAMPLE:INPUT STRING aaabbbccc when n=3**

S-\>A

-\>aABc

-\>aaABcBc (A-\>aABc)

-\>aaabcBcBc (A-\>abc)

-\>aaabBccBc (cB-\>Bc)

-\>aaabBcBcc (cB-\>Bc)

-\>aaabbcBcc (bB-\>bb)

-\>aaabbBccc (cB-\>Bc)

-\>aaabbbccc (bB-\>bb)

# Answer
> 0 votes
There is a solution which is context-sensitive.

$$G = (N,T,P,S)$$ $$N=\\{S,A,B,C\\}$$ $$T=\\{a,b,c\\}$$ $$S=\mbox{start symbol}$$ Production Rules(P):

1. $S \rightarrow aAB\ |\ A\ |\ \epsilon$
2. $A \rightarrow aAB\ |\ aB$
3. $B \rightarrow bC$
4. $Cb \rightarrow bC$
5. $C \rightarrow cC\ |\ c$

# Answer
> -1 votes
Grammar for the language $\\{a^nb^nc^n \mid n\ge1\\}$:
$S\to aSBC\mid aBC$
$CB\to BC$
$aB\to ab$
$bB\to bb$
$bC\to bc$
$cC\to cc$

---
Tags: formal-languages, formal-grammars
---


# Question
Title: What is the simplest/smallest subset an OOP language like C#/JavaScript that is Turing-complete?
This question is not meant to be too theoretical or nitpicky. I have experience programming, so **I'm trying to get a better understanding of what it takes to get Turing-completeness by using my intuition about practical programming languages**.

Basically: What minimal elements of a language like Javascript do we need to have Turing completeness, and why? (I'm pretty sure we don't need interfaces or subclasses, etc).

Extra question: Is there a simple, natural polynomial-time reduction from a language like Javascript/C++/C# to a Turing machine?

# Answer
> 2 votes
It takes very little to obtain Turing completeness. For example the While programming language and Counter Machines are Turing complete and are easily recognized as a subset (up to syntax) of all three languages.

The While language is also good for an intuition of Turing completeness. You need

1. Potentially infinite loops, because Turing complete computations may not terminate.
2. Condition-dependend behaviour, so that you can break out of loops (important: in contrast to `for` loops, the time after which the loop ends is not be known in advance).
3. A data type with an infinite domain.

In both examples I gave above, the third ingredient is the type of integers *of unbounded size*. Arguably, it is not natively supported in C++ (I do not know about JavaScript or C#. A "normal" programming that has it is Python 3.) You promised not to nitpick, but if you did one would have to either

* replace your languages by "conceptual" variants thereof where integers are unbounded, or
* implement unbounded integers in a library (like GNU MP). When you do that, you inevitably use the "true" third ingredient of your languages: They achieve infinite-domain data through dynamic allocation.

All of the above would as well hold for C. Yet your question, at least the title, is specifically about OOP languages. Basically, your three languages are extensions of C by objects. My Turing-complete subsets then discard these extensions. At the moment I cannot come up with *natural* subsets of any of these languages where some OOP feature is essential for Turing completeness.

As for simple, natural, polynomial time reductions to Turing machines: Polynomial time is possible, natural in a sense, simple I do not think (such a reduction is a full-feature compiler for the language, so it cannot be any simpler than the language is). Let there be three tapes. One for the heap, one for the stack and one for indexing. The heap and the stack would contain sequences of substrings like `[1010011]` which encode unbounded integers (83 in this case). When used as pointers, these integers are somehow mapped to positions in the heap or the stack. Indexing an element of the heap or the stack works by copying the pointer to the indexing tape and then moving to the respective part of the tape by using the indexing tape as a counter.

---
Tags: turing-completeness, intuition
---


title: Big O order of a function

text:
# Question
Title: Big O order of a function
I'm doing some practice questions on Big O notation and came across this question. What is the Big O order of function () = ^2 + log2() + log2(). Show your working.

My answer is O(n^2) because it's the term with the highest degree. However, I'm not really sure how to show it. Am I right by saying that it has to be proven like this -\> f(n) is an element of O(n^2). So far, I've only done questions like n^2 + 2n + 1 and I have to find c and k values. I'm not quite sure how to do this one. Can anyone help me out, please?

Thanks

# Answer
> 2 votes
You need to show that there is an index $n\_0\geq 0$ and some $c\>0$ such that $f(n) \leq c\cdot n^2$, for all $n\geq n\_0$. Here you can take $c=2$.

This leaves you with showing that $n \log\_2(n) + log\_2(n) \leq n^2$, for high enough values of $n$.

This holds because $\lim\_{n\to\infty}\frac{log\_2(n)}{n} = 0$.

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Deriving the average depth for a randomly generated binary search tree
If $D(n)$ is the internal path length (sum of the depths of all nodes) for some tree $T$ with $n$ nodes then we have the following recurrence relation: $$D(n)=D(i)+D(n-i-1)+N-1$$ where I simply taken an arbitrary tree with a left subtree containing $i$ nodes and the right subtree containing $n-i-1$ nodes.

Correct me if I'm misunderstanding this, but since these left and right subtrees can be anything (where $i=0,1,2,...,n-1$) then the average of $D$ is given by $$\langle D \rangle=\dfrac{1}{n}\left(2\sum\_{i=0}^{n-1}D(i)+\sum\_{i=0}^{n-1}(n-1)\right)$$ where I divided by $n$ since there are $n$ different left/right-subtree possibilities. What I don't understand is that online sources and my textbook equates this to $D$ itself. In other words, I don't quite understand why we're allowed to set $\langle D(n) \rangle = D(n)$.

Ignoring that, I continued on and I'm also running into the problem where my book is writing $$ D(n) =\dfrac{1}{n}\left(2\sum\_{i=0}^{n-1}D(i)+(n-1)\right)$$ and seems to be ignoring the sum altogether. The reason why I say this is because later the book claims that $$ nD(n) =2\sum\_{i=0}^{n-1}D(i)+n(n-1)$$ This doesn't make any sense to me since I had a $$\sum\_{i=0}^{n-1}(n-1)\in O(n^2)$$ term in my expression so multiplying by another $n$ should be give me something like $$ nD(n) =2\sum\_{i=0}^{n-1}D(i)+O(n^3)$$ instead. I feel like I'm missing something obvious but I can't quite figure it out. Any ideas?

# Answer
> 1 votes
Suppose that $T$ is a random tree on $n$ vertices, according to the distribution you consider. Let $T\_L,T\_R$ be its two subtrees, and let their size be $N\_L,N\_R$. Let $P$ be the total path length of $T$. Let $P\_L(i)$ be the total path length of $T\_L$ if $N\_L=i$, and zero otherwise, and define $P\_R(i)$ similarly. We have $$ P = \sum\_{i=0}^{n-1} (P\_L(i) + P\_R(n-1-i)) + n-1. $$ According to linearity expectation, we have $$ \mathbb{E}\[P\] = \sum\_{i=0}^{n-1} (\mathbb{E}\[P\_L(i)\] + \mathbb{E}\[P\_R(n-1-i)\]) + n-1. $$ By definition, $\mathbb{E}\[P\] = D(n)$, where $D(n)$ is the *expected* internal path length of a random tree on $n$ vertices.

According to your probability distribution, the probability that $N\_L=i$ is $1/n$. When that happens, $T\_L$ is just a random tree on $i$ vertices. Therefore $$ \mathbb{E}\[P\_L(i)\] = \Pr\[N\_L=i\] \mathbb{E}\[P\_L(i)|N\_L=i\] + \Pr\[N\_L\neq i\] \mathbb{E}\[P\_L(i)|N\_L\neq i\] = \\ \frac{1}{n} \cdot D(i) + \left(1-\frac{1}{n}\right) \cdot 0 = \frac{D(i)}{n}. $$ Therefore we obtain the recurrence $$ D(n) = \frac{1}{n} \sum\_{i=0}^{n-1} (D(i) + D(n-1-i)) + n-1 = \frac{2}{n} \sum\_{i=0}^{n-1} D(i) + n-1. $$ Equivalently, $$ nD(n) = 2\sum\_{i=0}^{n-1} D(i) + n(n-1). $$ The initial condition is $D(0) = 0$.

We can solve this recurrence using generating functions. Let $P(x) = \sum\_{n=0}^\infty D(n) x^n$. First, $$ P'(n) = \sum\_{n=1}^\infty nD(n) x^{n-1}. $$ Second, $$ \frac{P(n)}{1-x} = \sum\_{n=0}^\infty \[D(0) + \cdots + D(n)\] x^n. $$ Third, $$ \sum\_{n=0}^\infty n(n-1) x^{n-2} = \frac{d^2}{dx^2} \frac{1}{1-x} = \frac{2}{(1-x)^3}. $$ Putting everything together, we obtain $$ P'(x) = \sum\_{n=1}^\infty nD(n) x^{n-1} = 2\sum\_{n=1}^\infty (D(0) + \cdots + D(n-1)) x^{n-1} + \sum\_{n=1}^\infty n(n-1) x^{n-1} = \\ \frac{2P(x)}{1-x} + \frac{2x}{(1-x)^3}. $$ The solution to this ODE is $$ P(x) = \frac{-2\log (1-x)-2x}{(1-x)^2} = \frac{1}{(1-x)^2} \sum\_{n=2}^\infty \frac{2}{n} x^n, $$ which implies that $$ D(n) = 2\sum\_{m=2}^n \frac{n-m+1}{m} = 2(n+1)(H\_n-1)-2(n-1) = 2(n+1)H\_n-4n. $$ Since $H\_n = \ln n + \gamma + 1/2n + O(1/n^2)$, we deduce that $$ D(n) = 2(n+1)(\ln n + \gamma + 1/2n + O(1/n^2)) - 4n = \\ 2n\ln n + 2\ln n + (2\gamma-4) n + 2\gamma + 1 + O(1/n). $$

# Answer
> 0 votes
You don't need to multiply by $n$ in the last but one expression, because the right hand side of the D(n) expression has the factor $\frac{1}{n}$.

So you only have to explain the $\mathcal{O}(n^2)$ versus $\mathcal{O}(n)$ terms; not the $\mathcal{O}(n^3)$ versus $\mathcal{O}(n)$ terms.

Also, I have a doubt whether one can take $i$ to be really arbitrary (e.g. 0) in the first expression. When $i=0$ it means the left sub-tree is empty, so the initial is not really a binary tree.

---
Tags: algorithm-analysis, recurrence-relation, binary-trees, binary-search-trees
---


# Question
Title: How to check whether a graph is connected in polynomial time?
I have to solve the following problem:

> Consider the problem Connected:
>
> **Input:** An unweighted, undirected graph $G$.
>
> **Output:** True if and only if $G$ is connected.
>
> Show that Connected can be decided in polynomial time.

I have been at this for hours, and I can't seem to find a way to prove this. Any hints?

# Answer
Make a BFS/DFS traversal on the graph. If you visited every vertex then it is connected otherwise not. Note: You have to apply BFS/DFS only one time on the graph
> 13 votes

# Answer
Two hints:

* How would you solve the problem *at all*?
* Which graph algorithms do you know? Can you use one of them to solve the problem?
> 7 votes

# Answer
Besides the usual deterministic DFS/BFS approaches, one could also consider a randomized algorithm. I will shortly describe a randomized algorithm for deciding if two vertices $s$ and $t$ are connected. It can also be used to decide if the whole graph is connected. The main benefit is that this method requires $O(\log |V|)$ bits of space, whereas a BFS/DFS requires $\Omega(|V|)$ space.

The *cover time* of an undirected graph $G=(V,E)$ is the maximum over all vertices $v \in V(G)$ of the expected time to visit all of the nodes in the graph by a random walk starting from $v$. Using some theory of Markov chains, it is not too hard to prove the cover time of $G$ if bounded from above by $4|V|\cdot|E|$.

The algorithm for deciding if $s$ and $t$ are connected is simple:

```
Input: two vertices s,t
1. Start a random walk from s.
2. If t is reached within 4|V|^3 steps, return true. Otherwise, return false.

```

Clearly, if there is no path between $s$ and $t$ the algorithm returns the correct answer. If there is a path, the algorithm errs if it is not found within $4|V|^3$ steps. The cover time of $G$ is bounded from above by $4|V||E| \< 2|V|^3$. Using Markov's inequality, the probability that a random walk takes more than $4|V|^3$ steps to reach $t$ from $s$ is at most $1/2$. In other words, the algorithm returns the correct answer with probability $1/2$, and only errs by saying $s$ and $t$ are not connected when they in fact are.
> 4 votes

# Answer
You can find the Laplacian matrix of the graph and check the multiplicity of eigenvalue zero of the Laplacian matrix, if the multiplicity of zero is one then graph is connected, if multiplicity of eigenvalue zero of Laplacian matrix of the graph is two or more then it is disconnected.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, polynomial-time
---


# Question
Title: What is the type signature of a Turing Machine?
Maybe my question is a bad question, but if it is, I want to know eactly how it is a bad question.

Suppose we have some Turing machien $M$ that takes as input a natural number $n$ in the form of a binary string, writes $n^2$ in binary on its output tape, and then halts.

What is the type signature of this machine? **Here is why I am confused:**

* We can treat $M$ as a function: $M(\cdot)$ denotes the function that maps $n\mapsto n^2$, which suggests that it has type $\\{0,1\\}^\*\to\\{0,1 \\}^\*$
* But $M$, intuitively speaking, is not a function, but a "device". This means that we can extract more information from it. e.g. potentially we could define $M\_{235}(\cdot)$ to be the function that takes an input and outputs: "what is the string on the output tape after 235 steps, given this input?".
* In the formal definition, a turing machine is a tuple $M=\langle Q,\Gamma ,b,\Sigma ,\delta ,q\_{0},F\rangle$ (with some properties on these elements). **But I am confused about how this tuple relates to type theory.** Is this the "type signature" of $M$? If so, what kind of type theory captures this kind of type?

# Answer
Usually, Turing machines are presented using set theory rather than type theory.

There might be many ways to represent a TM in type theory, each one with its advantages and disadvantages. I would not represent it as a function $\\{0,1\\}^\* \to\\{0,1\\}^\*$ since the function implemented by a TM is a *partial* function, because the TM might fail to terminate, while in type theory functions are total.

If we wanted to follow the set theoretic definition, we might define a TM as a dependent tuple. This tuple would include:

* $\Sigma:\sf Type$ a type representing the tape "alphabet"
* $Q:\sf Type$ a type representing the states
* $b:\Sigma$ the blank symbol
* $q\_0 : Q$ the initial state
* $\delta : Q \to \Sigma \to (Q \times \Sigma \times 3)$ for the transition function (assuming a deterministic TM) where $3=1+1+1$ represents the directions
* $F : Q \to 2$ with $2=1+1$ the halting states

Technically, this would be a huge dependent sum such as

$$ \sum\_{\Sigma\sf Type} \sum\_{Q:\sf Type} \Sigma \times Q \times (Q\to \Sigma \to(Q\times \Sigma\times 3))\times(Q\to 2) $$

The above would be a possible representation of a TM. (I'm unsure it would be a very good one, especially if we work without functional extensionality, but I'll neglect that.)

In a similar way one could define the type of the configurations of a TM ${\sf Conf}\ T$ and a step function $step: {\sf Conf}\ T \to 1 + {\sf Conf}\ T$ (the $1+$ is to report "no next step" when the TM halts).

One could even define a function to run $n$ steps, or a predicate for "the TM $T$ on input $x$ halts with output $y$".

$$ \begin{array}{l} {\sf runTM} : \prod\_{T:TM} {\sf Conf}\ T \to \mathbb N \to 1+{\sf Conf}\ T \\ {\sf semanticsTM} : \prod\_{T:TM} (\pi\_{\Sigma} T)^\* \to (\pi\_{\Sigma} T)^\* \to \sf Type \end{array} $$
> 2 votes

# Answer
One could see a type as a subset of values, among all the possible values. For instance, `int` is the type of all the bitstrings on 8 bits.

However, a Turing machine does restrict the values it works with: it is untyped.

Now, when you look at the definition of a Turing machine, you can ask yourself whether the (meta)language in which this definition is written has types and if the definition statement is well-typed. Here I used say that the answers are "yes". For instance, you can give a type to, say, $\delta$ which is consistant with the types of $b$, of the elements in $Q$, $\Gamma$, etc.
> 0 votes

---
Tags: turing-machines, type-theory
---


# Question
Title: Can someone explain this conclusion for Finite State Machines?
PS It isn't a homework problem.. (But the results seems to be working for me when I checked manually a couple of values of m and n)

Let's say I have two FSM's(calling them **A** and **B**)

* A is the the machine for checking divisibility by any +ve number (calling it m)
* B is the the machine for checking divisibility by any +ve number (calling it n) (m and n aren't equal)

Now we have a third machine (**C**) for which we need to find the number of states it will have if the goal of that machine is **A machine(FSM) which will accept Divisibility of both $n$ and $m$**)

So here are the claims for the count of states for $C$,

* if $GCD (m,n)$ equivalent to $1$, then the number of states in **C** is $m\*n$
* if $GCD (m,n)$ isn't equivalent to $1$, then number of states in **C** is $LCM(m,n)$

(EDIT 1- Both are technically the same thing, check the comments and the answer)

(Edit -2 I meant this, if we have strings given to us over {0,1}, and the machines will then calculate the divisibility by the given number and with result in either of the (let's say the number we are dividing with is n) n-1 states as we can have n-1 modulo values possible)

I have checked the results for few m and m manually and they seem to be correct for them..

But why it's so?(I know that A and B will have m and n as count of states respectively for minimal DFA)

# Answer
> 4 votes
In both cases, the number of states is the LCM. This is because a number is divisible by $m$ and $n$ if, and only if, it is divisible by $\mathrm{lcm}(m,n)$ and, for any positive integer $d$, you can check that the input length is divisible by $d$ by having states $\\{0, \dots, d-1\\}$ such that the automaton is in state $i$ when the number of characters read is congruent to $i$, modulo $d$.

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


# Question
Title: Curry-howard isomorphism in object oriented programming languages
I want to get a better intuition for the curry howard isomorphism, and my intuition is mainly based on object oriented programming languages like JavaScript.

So as an example, I am going to formalize the notion of "topological space" in a hypothetical object oriented programming language with dependent type theory and see if it makes sense:

```
public class TopologicalSpace
{
    BaseSet:Type
    Topology: (BaseSet -> Boolean) -> Boolean
    public TopologicalSpace(X:Type,T:(X -> 2) -> 2,
         p_axiom1:Axiom,p_axiom2:Axiom2,p_axiom3:Axiom3 )\\constructor
    {
        BaseSet = X;
        Topology = T;
        proof_axiom1 = p_axiom1;
        proof_axiom2 = p_axiom2;
        proof_axiom3 = p_axiom3;
    }

    Axiom1: Topology (function (x:BaseSet) return True) = True
        AND Topology (function (x:BaseSet) return False) = True \\empty set & domain
              \\ are in topology
    public readonly proof_axiom1:Axiom1

    Axiom2: \\\etcetcetc
}

```

**Does this approach make sense? Is there a kind of object oriented type theory + curry howard isomorphism like this?**

# Answer
> 1 votes
If you only consider terminating functions, then your axiomatisation works :-) Indeed, terminating functions have a resonable notion of equality: If their return type has decidable equality then the functions have decidable equality.

Regarding your code, it could be rendered in an OOP-like fashion this way

```
record TopologicalSpace : Set₁ where

  field
     BaseSet  : Set
     Topology : (BaseSet → Boolean) → Boolean

  Empty    = λ (x : BaseSet) → false
  Universe = λ (x : BaseSet) → true

  field
    axiom1   :       Topology Empty    ≡ true
                AND  Topology Universe ≡ true

```

This is a *real* programming language whose functions must always terminate: It is Agda; http://learnyouanagda.liamoc.net/

The source for the code can be found here: https://github.com/alhassy/RandomProgramming/blob/master/Agda/TopologicalSpaces.agda

---
Tags: type-theory, object-oriented, curry-howard
---


# Question
Title: Can a context-senstive gramma contains production rule $cB\rightarrow Bc$?
Some textbook show that the grammar $G=(N,T,P,S)$ below belongs to context-senstive grammars:

1. S-\>aSBC
2. S-\>abc
3. cB-\>Bc
4. bG-\>bb

where N={S,B}, T={a,b,c}.

I am confused by the fact that the production rule cB-\>Bc cannot satisfy the definition of a CSG. So, why is the above grammar belongs to CSG?

# Answer
> 1 votes
Your confusion is not unexpected. That grammar is not a context-sensitive grammar in its usual strict sense.

However, that grammar can be considered as a context-sensitive grammar in some situations. The Wikipedia entry on context-sensitive grmmar reads the following.

> Some definitions of a context-sensitive grammar only require that for any production rule of the form $u \to v$, the length of $u$ shall be less than or equal to the length of $v$. This seemingly weaker requirement is in fact weakly equivalent, see Noncontracting grammar#Transforming into context-sensitive grammar.

You may want to double check the definition of CFG and exposition thereafter in the textbook you mentioned.

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


# Question
Title: Finding libraries of formalized mathematics
I want to formalize **Interval Newton Methods** in **Isabelle**. As a research, I have the curiosity of whether there is anything done in the field. For that, I need to know what mathematical contents have been formalized in different proof assistants.

For Isabelle, this is easy: just google the Archive of Formal Proofs. What about the others? Can you help me to complete this list (taken from Wikipedia's table for proof assistants) providing links to the relevant libraries of formalized mathematics:

ACL2 1, Agda, Albatross, Coq, F\*, HOL Light, HOL4, Isabelle, Lean, LEGO, Mizar, NuPRL, PVS, Twelf?

If you know of other libraries you are very welcome to add the corresponding tool.

**Additions:**

Is https://coq.inria.fr/ the primary place to look for proofs written in Coq?

# Answer
> 3 votes
**Metamath** has a HUGE chapter-organized archive of formal theorems:

http://us.metamath.org/mpeuni/mmtheorems.html

Besides that, Freek Wiedijk's **QED manifesto** is always a good starter for future formalizers. And his list of top 100 formalized theorem is an ever-encouraging source of formalized ideas:

http://www.cs.ru.nl/~freek/100/

At the end of that page, he provides another list of desired but-still-missing formalized theorems. The one that I personally desire, is $\mathrm{IP=PSPACE}$.

---
Tags: reference-request, automated-theorem-proving
---


# Question
Title: Many-One Reducibility of decision problems for complexity theory?
A many-one reduction of problem $A$ to problem $B$ is essentially a function that converts a problem instance in problem $A$ to an instance in $B$. This allows you to use a $B-$solver one time to solve this converted instance, in order to solve an $A$-instance.

To show that $A$ is in **NP-complete**, people use reducibillity arguments to reduce (in polynomial time) an arbitrary problem in **NP** to $A$, but as far as I know this is not necessarily a many-one reduction.

My question is: How many of these reductions in the context of **NP-completeness** are many-one reductions? How significantly would the complexity class change if we would require many-one reductions?

# Answer
> 2 votes
NP-hardness (and so NP-completeness) are defined using many-one reductions. When you show that a problem is NP-hard, you have to follow the definition and use many-one reductions. All proofs that you see of NP-hardness use many-one reductions.

One thing to note is that usually, one does not show how to reduce an arbitrary problem in NP to the target problem. Rather, one reduces a problem already known to be NP-hard to the target problem. The starting point of this endeavor is Cook's theorem (independently proved by Levin), which shows that SAT is NP-hard.

The other common type of reduction is oracle reduction (there are other types as well, but they are less common). Oracle reductions cannot distinguish NP from coNP: every coNP-hard problem in the many-one sense is NP-hard for oracle reductions. Most researchers believe that NP is different from coNP, and this is one of the reasons we insist on using many-one reductions.

---
Tags: complexity-theory, np-complete, reductions
---


# Question
Title: How hash-table and hash-map are different?
In the context of CS, how the *hash-table* and *hash-map* are different?

I was watching a part of "Algorithm with Swift" video in Udacity, and I discovered the terms "hash-table" and "hash-map" are somewhat confusing.

As far as I understand,

* hash table → stores keys only → Swift `Set`.
* hash map → stores key/value pairs → Swift `Dictionary`.

But, Wikipedia is talking hash-table is same thing with hash-map. Here I could not find any help.

Is this formal or widely accepted **CS term**? Am I understanding correctly? If I'm wrong, please correct me. Thanks.

---

I know industry uses their own terms that can be different, and I am asking about academia because I believe terms are more consistent in academia. If it's not, I just would abandon to learn academic terms.

# Answer
If you ask me, you're correct and Wikipedia is wrong, as the complaints on the article's talk page (some 11 years ago!) clearly explain, but it was never fixed (or it was fixed and reverted).

A hash table stores items; these items can be keys (in which case it implements a set), or key-value pairs (in which case it implements a map, i.e. a hash map), or perhaps something else, e.g. triples; the Wikipedia article describes only the key-value case, while I was only taught the key-only case in class.

Some people do use *hash table* to mean *hash map*, so Wikipedia successfully describes a particular usage of the term; it should also describe the other cases. (It does describe how a hash map can be used to implement a set and other data structures, but that's not the same thing.)

In IT, most terms mean different things to different people, and most people using the term in one sense aren't aware that other people use it in another sense; *hash table* is no exception.
> 2 votes

---
Tags: terminology, hash-tables
---


# Question
Title: Finite State Machine that only accepts strings with equal number of 0's and 1's
Question: Suppose you have a finite state machine that accepts only strings with an equal number of zeros and ones. Show that you can then construct a finite state machine that accepts only strings of the form 0^n 1^n, i.e., an arbitrary finite number of zeros followed by the same number of ones.

My attempt at a response:

A Finite State Machine that accepts strings with an equal number of 0’s and 1’s (e.g. n zeros and n one's, where n is some arbitrary finite number), must have a counter that keeps track of the total number of 0's and 1's. This is impossible, since by definition a FSM has no counter or memory. But suppose this were possible. Then it’d be possible to construct another FSM that keeps track of the count of consecutive 0's in the prefix of a given string, and ensure that number equals the count of consecutive 1's in the suffix of that string.

---

I feel like there is more to the answer than this, but I don't really know what else can be said. I know that no FSM can be constructed to accept only strings in the format 0^n 1^n where n could be any arbitrary nonnegative integer, but that it is possible to do for any fixed, specific value of n. For example, it's possible to build FSM to accept only strings that contain three 0's, followed by three 1's. But I don't know whether this detail is relevant at all. Thanks for any help.

# Answer
> 5 votes
The question is not really well-defined since there is no FSM that accepts your language $L$, so the existence of such an FSM implies anything – for example, $2+2=3$.

However, the intended solution was to notice that $$ L \cap 0^\*1^\* = \\{0^n1^n : n \geq 0\\}. $$ Since the regular languages are closed under intersection, this shows that an FSM for $L$ can be converted to one of $\\{0^n1^n : n \geq 0\\}$.

Your attempt claims that an FSM accepting $L$ must have a counter. This is not a formal statement: it has no formal content. It's just intuition. A PDA for $L$ also doesn't have a counter; it has a stack. *Counter* is not a well-defined technical notion.

# Answer
> 0 votes
Step 1: Show this finite state machine does not exist

Step 2: P∧¬P→Q

Elaboration on step 1: For any number of states in the machine N there is a number of consecutive zeros N+1 that it cannot distinguish from another number of consecutive zeros M. Therefore, the machine will will match M zeros followed by N ones which it should not.

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


# Question
Title: Proof that the Blank Tape Halting Problem is undecideable
I have seen a few proofs that the Blank Tape Halting Problem is undecideable, however I'd like to check if the following is a valid proof (and if it isn't why not)

*Proof:* Suppose that the Blank Tape Halting problem is decideable, then there exists a universal turing machine $M$ that decides it. So given any turing machine $T$, $M$ decides if $T$ halts after being started on a blank tape.

Now let any turing machine $T$ and input $w$ be given. Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Then if $M$ takes $R$ as input, $M$ decides if $R$ halts on a blank tape and thus decides if $T$ halts on $w$. Since $T$ and $w$ were chosen arbitratily $M$ decides the Halting problem, a contradiction, so the Blank Tape Halting Problem is undecideable. $\square$.

---

Is there anything wrong with my reasoning above? I assume that there must be some key detail that I'm overlooking, or that my proof isn't completely rigorous

I guess the problematic argument may be the following

> Construct a new turing machine $R$ (with start state blank) such that $R$ halts on a blank tape if and only if $T$ halts on $w$.

Since I haven't explicitly constructed such a turing machine $R$ in my proof above.

# Answer
> 1 votes
You need to explain how to construct $R$. In your case this can be done formally, by constructing a machine which works as follows:

1. Write $w$ on the input tape.
2. Move the head back to its initial position.
3. Transfer control to $T$.

It is not too hard to construct $R$ explicitly from $T$.

In order for your argument to go through, you need to show that this reduction is computable. Usually we describe such reductions informally and just claim (without proof) that it is computable, since actually proving such things formally is extremely technical and longwinded.

---
Tags: turing-machines, computability
---


# Question
Title: What's a real life usage for detecting communities in complex systems?
I am reading through the Girvan-Newman description, having come from the topic of "detecting communities in a complex system".

What exactly is a community in this context and why is it useful for a network to know about it? In simpler terms, what's a real-life usage of this algorithm?

# Answer
Suppose you have a bunch of friends, regularly meeting together. Occasionally, you also visit your sibling, and they have their own friends. Can we extract these groups of friends just from knowing who's friends with whom on a social network? This is community detection, which is a form of intelligence gathering.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Why are FPGA's less efficient than fully hard-coded ASIC's?
A Field-programmable gate array (FPGA) is generally more efficient than using a "hard-coded" processor like a CPU or GPU for highly specific applications like bitcoin mining or doing structurally identical computations many times over.

however, FPGA as far as I know are beaten in computational efficiency by Application specific integrated circuits (ASIC's) that are specifically designed to the particular problem (again take Bitcoin mining as an example).

**My question is: What are the sources of the efficiency gain of ASIC's over FPGA's, given that FPGA's already allow you to setup the circuitry for the specific problem at hand?**

# Answer
> 4 votes
Functionality of FPGAs in very coarse lines: At the core functionality of FPGAs are small memories called Look Up Tables (LUTs). An FPGA instead of actually compute in hardware the output of a function, say f(x), what it does is store in these small memories all possible outputs of f. So next time an input x is given fpga passes x as address in a small memory and "looks up" the answer. As it happens with all kind of memories the larger the memory the bigger the delay. So FPGAs are consisted of "a lot" of very small LUTs distributed all over their surface. Every LUT "solves" a tiny subproblem and passes the answer to subsequent LUTs for further processing (answers). Loading the LUTs with different answers and connecting them in a programmable way gives FPGAs the ability to solve any kind of problem.

LUTs are interconnected each other in an hierarchical manner. That is, as it happens with computer networks, or with buildings, it would be infeasible to connect via road each building with every other, buildings are interconnected in an hierachical manner where you have small streets, bigger streets, highways etc. So to route a package from A to B you don't have a direct-short/fast-link between A and B, but instead you may use a lengthier route which is consisted of various kinds of roads. According to the previous analogy LUTs are the buildings and roads are the signal interconnections between LUTs. In FPGAs LUTs which are a kind of processing units are fixed in specific places, so in order to pass a signal from one LUT to another you have to follow the specific route hierarchy of FPGA. Instead in an ASIC you can place processing units in more efficient manner, and also make direct interconnection where is critical to do so, in order to minimize the delay. Even the simplest form of processing in an FPGA (consisting only of programmable logic) has to be in the form of a LUT. For example to compute the output of a 2 input AND gate you would need a LUT. In an ASIC you would need just an AND gate. The total circuitry of the LUT certainly has greater delay that just an AND gate of the same technology. To sum it up the sources of inefficiency of an FPGA are the

* routing delay you might have due to fixed routing hierarchy and
* circuitry overhead of LUTs themselves

Have in mind also that an FPGA is actually an ASIC, in which the "specific application" is to be programmable!

---
Tags: computer-architecture
---


title: Knapsack problem: equal profits

text:
# Question
Title: Knapsack problem: equal profits
I am looking for references to efficient algorithms that solve knapsack problem where all profits are equal.

More formal definition of the problem from a Wikipedia article on KPs:

> If all the profits are 1, we will try to maximize the number of items which would not exceed the knapsack capacity:
>
> maximize $\sum\_{j=0}^n x\_j$
>
> subject to $\sum\_{j=0}^n w\_jx\_j \leq W$,
>
> $x\_j \in \\{0, 1\\}, \forall\_j \in \\{1, ..., n\\}$

I skimmed through *Knapsack Problems* book (Kellerer et al', 2004) that is referenced by that Wikipedia article but couldn't find that particular problem.

I also saw some posts about this exact problem with no good answers:

The answer to the first post mentions Capital Budgeting problem, but the provided link doesn't discuss the case where all profits (values) are equal, which I believe can be better optimized due to its special case.

The answer to the second post mentions a naive solution in which a greedy algorithm picks minimum weight items at each step until no more items fit in the knapsack. This requires knowing the order of items by weight, which results in $O(n\log{n})$ solution.

Is there an algorithm with a better upper bound (e.g. linear time)?

# Answer
Comment $\rightarrow$ answer.

Without loss of generality, we assume that all weights are strictly positive (otherwise, we can take all non-positively-weighted items ahead of time and change $W$ as appropriate).

From here, one can use an approach reminiscent of Randomized Quick-Select to solve this in expected linear time. First, define a tie breaking procedure for weights that consistently breaks ties between equal weighted items. For example, one can use the ordering of items as given in the input.

Now repeat the following procedure. Pick a random element $k$ and check if the sum of weights of all elements no heavier than $k$ (using the above tie-breaking rules) is less than $W$. If so, the optimal solution must contain all such elements, so put them all aside and recurse on the subproblem of elements heavier than k, with $W$ decreased appropriately. Otherwise, the optimal solution must be a strict subset of these elements, so discard all larger elements and recurse with the same $W$ you started with. The base case of the recursion is one where you return the empty set when $W$ is less than the cost of the cheapest item (or if no items remain).

Each round takes time linear in the input size *for that round*, but it takes a constant number of rounds (in expectation) to reduce the size of the instance by a constant factor, so the total running time intuitively should be expected linear. Indeed, the usual analysis of Randomized Quickselect works identically here, too, proving the result.

Here's a non-tail-recursive implementation in Python.

```
def uniformKnapsack(items, W):
    import random

    def subProcedure(remaining, new_W):
        # base case
        if remaining == [] or min(i[0] for i in remaining) > new_W:
            return []

        # sample random item
        random_item = random.choice(remaining)

        # split input into larger and smaller subsets based on the item
        smaller = [i for i in remaining if i < random_item]
        not_smaller = [i for i in remaining if random_item <= i]

        # compute the total cost of all smaller items
        smaller_cost = sum(i[0] for i in smaller)

        if smaller_cost <= new_W:
            # include all smaller elements and recurse on the rest with a smaller W
            return smaller + subProcedure(not_smaller, new_W - smaller_cost)
        else:
            # recurse on the smaller subset with the same W
            return subProcedure(smaller, new_W)

    # convert a list of items (a, b, c) to  a list of the form ((a, 0), (b, 1), (c, 2)) for
    # consistent tie breaking in comparison operations
    augmented_items = [(j, i) for (i, j) in enumerate(items)]

    # compute the solution over the augmented items
    solution = subProcedure(augmented_items, W)

    # return the un-augmented items from the solution
    return [i[0] for i in solution]

```
> 1 votes

# Answer
Sorting the weights takes O (n ln n), but you don't need to sort them completely.

We start with the quicksort algorithm. If necessary, modify the partitioning algorithm so that portioning always separates an array into a "smaller" portion and a "larger" portion, that is all elements are exactly in one of these portion.

If the smaller elements all fit, then we put them into the knapsack without sorting them, then we handle the larger elements recursively. If the smaller elements don't all fit, then we can completely ignore the larger elements, and partition the smaller ones again.
> 0 votes

---
Tags: time-complexity, optimization, reference-request, knapsack-problems
---


# Question
Title: A hangman variation: determining a string by guessing substrings contained in it
I came up with this Hangman variation, where you must figure out the hidden word by asking whether a string is a substring of this word. E.g. if the hidden word is "abracadabra" and I guess "cad" I will get a positive result, and if I guess "arb" I get a negative result. When I guess the word I win.

My first question is if anyone knows whether this problem is known and has been solved before?

I came up with an algorithm, which seems to operate in sub-quadratic\* number of guesses (by input length) by iteratively generating graphs of 1..n length substrings. In this graph the nodes are the positively guessed k-length substrings and the edges connect to possible continuations. New k+1-length guesses are generated by appending to these possible continuations, giving one new guess per edge. Once the graph becomes a loop you can try appending all nodes in order, until you solve the word. Here's a Java implementation.

My second question is if anyone can help me figure out the time complexity of this algorithm? As there can be at most n graphs, with n being the input length, each having up to n^2 edges, then multiplied by the n time needed for the substring function gives an upper bound of O(n^4). This is assuming a constant-sized alphabet. However, I doubt this is the tightest upper bound possible.

\*experimentally, with a constant-size alphabet

# Answer
This problem can be solved with O(n * s) queries, where n is the input length and s is the alphabet size. First, determine some single character substring by trying all possibilities. Then extend that into a length 2 substring by trying to append characters to it. Continue extending the string by appending until it's not possible anymore. If it's not possible to append anymore and the length is not n, do the same strategy but prepending. In this way you reach the length n substring in n steps that each take at most s queries.
> 1 votes

---
Tags: runtime-analysis, strings, substrings
---


# Question
Title: Interpretation of Backtracking Algorithm Problem - weighted matching
I am attempting to resolve the following problem using Backtracking:

> Suppose that you have $n$ men and $n$ women and two matrices P y Q (n x n); such that $P\_{ij}$ is the preference of the man $i$ for the woman $j$ and $Q\_{ij}$ is the preference of the woman $i$ for the man $j$.
>
> 1. Depict an algorithm that follows the Backtracking technique to find the pairs of men and women whose sum of the products of the preferences are the highest possible.
> 2. With help from the matrices $P = \begin{bmatrix} 1 & 3 & 2 & 0 \\ 2 & 4 & 3 & 1 \\ 0 & 3 & 1 & 2 \\ 3 & 4 & 2 & 1 \\ \end{bmatrix} $ and $Q = \begin{bmatrix} 0 & 1 & 2 & 3 \\ 4 & 3 & 2 & 1 \\ 4 & 2 & 3 & 1 \\ 3 & 1 & 4 & 2 \\ \end{bmatrix} $ and represent the exploration tree of the exploration of the search space of the solution. Indicate:
>
> * How will you represent the solution and based on that, what are the restrictions of the problem and how will you calculate the value of the objective function.
>     * In the process of ramification, what will represent the levels and how will you generate the children of each node.
> 3. Analyze the time complexity of the algorithm.

I have the basic ideas of how backtracking works but I am having trouble interpreting the problem. What does it mean by **... the sum of the products of the preferences ...**?

# Answer
> 1 votes
Suppose man $i$ is paired with woman $w(i)$, for $1\le i\le n$.

"The sum of the products of the preferences" is the following number.

$$ P\_{1,w(1)}Q\_{w(1), 1} + P\_{2,w(2)}Q\_{w(2), 2} + \cdots + P\_{n,w(n)}Q\_{w(n), n} $$

One can imagine that each individual product $P\_{i,w(i)}Q\_{w(i),i}$ quantifies how preferred is the pairing between man $i$ and woman $w(i)$.

---
Tags: optimization, backtracking
---


# Question
Title: If value of LP relaxation of s-t minimum cuts is P ,then wen can find a s-t cut at most P edges?
My problem is mainly from this lecture notes on convex optimization here page4

Consider a s-t Minimum problem, on unweighted undirected graph $G=(V,E)$,we can formalize in following linear integer programming problem

\begin{equation\*} \begin{aligned} & \underset{}{\text{minimine}} & & \sum\_{u,v\in E}|x\_u-x\_v| \\ & \text{subject to} & & x\_s =1 ,x\_t=0 &x\_v\in \left\\{ 0，1\right\\} \forall v \in V \end{aligned} \end{equation\*}

then we can relax to:

\begin{aligned} & \underset{}{\text{minimine}} & & \sum\_{u,v\in E}|x\_u-x\_v| \\ & \text{subject to} & & x\_s -x\_t =1 \end{aligned}

for $0 \leq l \leq 1$ we define $S\_l:= \left\\{v|x\_v \geq l\right\\} $ then we have $$\sum\_{u,v\in E}|x\_u-x\_v| \geq\int^{1}\_{0}|\delta\_l(S\_l)|dl$$ where $\delta\_l(S\_l) $ denotes the crossing edge in $S\_l$

how to see this inequality ?

# Answer
> 0 votes
It's important to first understand how $\delta(S\_l)$ changes. When $l = 0$, $S\_l$ contains all vertices, and when $l = 1$, $S\_l$ contains no vertices. In either case, there is no edge going between $S\_l$ and $\overline{S\_l}$, so $\delta(S\_l) = 0$.

For values of $l$ between $0$ and $1$, $\delta(S\_l)$ contains exactly the edges with one endpoint in $S\_l$ and one endpoint in $\overline{S\_l}$. In particular, if we define

$$f\_{ij}(l) =\left\\{ \begin{array}{ll} 1 & \mbox{if } l \mbox{ is between } x\_i \mbox{ and } x\_j \\ 0 & \mbox{otherwise.} \end{array} \right.$$

then we have $$|\delta(S\_l)| = \sum\_{(i, j) \in \delta(S\_l)} 1 = \sum\_{\substack{(i,j) \in E \\ i \in S\_l \\ j \not\in S\_l}} 1 = \sum\_{(i, j) \in E} f\_{ij}(l).$$

Now let's consider one particular edge, from $u$ to $v$. Because $f\_{uv}(\cdot)$ is just $0$ everywhere except for on one interval where it takes on the value $1$, the value of $\int\_0^1 f\_{uv}(l)\\,\mathrm{d}l$ is just the length of the interval on which $f\_{uv}(l) = 1$, that is, $|x\_u - x\_v|$. So

$$\sum\_{(u, v) \in E} |x\_u - x\_v| = \sum\_{(u, v) \in E} \int\_0^1 f\_{uv}(l)\\,\mathrm{d}l = \int\_0^1 \sum\_{(u, v) \in E} f\_{uv}(l)\\,\mathrm{d}l = \int\_0^1 |\delta(S\_l)|\\,\mathrm{d}l.$$

---
Tags: algorithms, graphs, optimization, network-flow, minimum-cuts
---


# Question
Title: Hardness of the Minimum Steiner Tree problem on grid
Is the **Minimum Steiner Tree** problem $NP$-hard even on (2D, unweighted) grid graph ? A proof (for either case) will be very appreciated.

# Answer
This problem is $NP$-complete as shown by a reduction from **Rectilinear Steiner Minimum Tree** (RSMT) problem. Consider the Hanan grid: https://en.m.wikipedia.org/wiki/Hanan\_grid. Since Planar-3-SAT is strongly NP-complete, we can subdivide every segment of this grid into unit segments to obtain a grid graph.
> 1 votes

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


title: Egg dropping puzzle

text:
# Question
Title: Egg dropping puzzle
My problem is a modification of the known problem. Suppose you have a building with n floors. (Where n can be any size). Furthermore you have an indestructible egg at your disposal. If the egg is thrown from a floor which is not the maximum one gets a message. If the floor was too high you don't get a message. How can I design an algorithm that uses minimum many tests without knowing the height of the building? What is the minimum asymptotic runtime of such an algorithm?

# Answer
Suppose that the true number of floors is $n$. Your question is unclear, but it seems that you are interested in the minimum number of queries of the form "$n \< m$?" needed to find $n$.

Let us start with a lower bound. Consider a strategy for the task that works for every $n$. We can associate with each $n$ the transcript of the strategy, which is the list of yes/no answers to the queries performed by the strategy. These transcripts constitute a prefix code (why?), and so the number of queries $a\_n$ asked when the answer is $n$ satisfies Kraft's inequality: $$ \sum\_{n=1}^\infty 2^{-a\_n} \leq 1. $$ In particular, $\limsup (a\_n - \log n) = \infty$ (since the series $1/n$ diversges), which we write as $a\_n \gg \log n$; here $\log n = \log\_2 n$. Similarly, $a\_n \gg \log n + \log \log n$ (since the series $1/n\log n$ diverges).

Let us now attempt to design strategies. One simple strategy asks whether $n \< 2^t$ for $t=1,2,\ldots$, until finding a value of $t$ such that $2^t \leq n \< 2^{t+1}$; this takes $\log n + O(1)$ queries. Binary search over $2^{t+1}$ takes $\log n + O(1)$ more queries, for a total of $2\log n + O(1)$.

A better strategy applies the above strategy recursively on the $t$'s. The first step is to ask whether $n \< 2^{2^s}$ for $s=0,1,\ldots$, until finding a value of $s$ such that $2^{2^s} \leq n \< 2^{2^{s+1}}$; this takes $\log \log n + O(1)$ queries. Binary search over $2^{2^s},2^{2^s+1},\ldots,2^{2^{s+1}}$ finds a value of $t$ such that $2^t \leq n \< 2^{t+1}$ in $\log \log n + O(1)$ more steps, and finding $n$ using another binary search takes $\log n + O(1)$ steps, for a total of $\log n + 2\log\log n + O(1)$ steps.

The two strategies are completely analogous to Elias' gamma coding and delta coding. It is likely that Elias' omega coding can likewise be implemented.
> 3 votes

---
Tags: algorithms
---


# Question
Title: Finding duplicates in a stream of numbers
This is an interview question.
Say you have a function `foo()` which returns some integer.
You need to write an algorithm that does the following:

(1). Call `foo()` in a loop, till the returned value of `foo()` is -1.
(2). Returns true if during the loop there were two calls of `foo()` which returned the same value.

This is what I thought to do, please tell me if this is efficient enough:

(1). Initialize a hash map , which maps an integer to the number of times we got it in the loop
(2). Call `foo()` in a loop till the returned value of `foo()` is -1, while updating the hash map accordingly.
(3). Check if there is a key in the hash map which is mapped to a value greater than 1.

# Answer
There might be other variations, but your answer should be pretty good.

There are two improvements to your algorithm, though.

* Instead of a hashmap that counts the number of times each integer appears, you can just use a hashset to record the appearance of each integer.
* While you are calling `foo()` in a loop, you will return immediately if you find the returned integer is in the hashset and if you are not required to finish the loop till the returned value of foo() is -1. Many built-in implementations return false when you insert an existing value into a hashset.
> 1 votes

---
Tags: algorithms, efficiency, hash
---


# Question
Title: Is there an asymptotically optimal algorithm for unbounded search?
Suppose you have files with size $1,2,3,4\dots$ (which can be arbitrarily large and which have and can have any value that you want) and a USB-stick whose memory size $s$ you don't know, where $s$ is a positive integer and can be arbitrarily large. If $s$ is not smaller than your current file you get a message that it would be possible to write the file on the USB-stick. If your current file is larger than $s$ then you get no message. In each time unit one file can be tested. My question is, is there an algorithm which finds $s$ in as few time units as possible and would this algorithm asymptotically optimal?

# Answer
> 1 votes
The basic observation is:

> **Lemma.** Suppose $a\_s$ is a nondecreasing sequence of integers. There exists a strategy which uses $a\_s$ queries when the answer is $s$ if and only if $$ \sum\_{s=1}^\infty 2^{-a\_s} \leq 1. $$

In one direction, consider any strategy. For each $s$, let $w\_s$ be the sequence of answers to queries made by the strategy. No word in the collection $\\{w\_s\\}$ is a prefix of another, and so the collection forms a prefix code. The lengths $a\_s = |w\_s|$ therefore satisfy Kraft's inequality, $\sum\_{s=1}^\infty 2^{-a\_s} \leq 1$.

In the other direction, let us suppose that $\sum\_{s=1}^\infty 2^{-a\_s} \leq 1$. Decrease the $a\_s$ if need be (while keeping them nondecreasing) so that $\sum\_{s=1}^\infty 2^{-a\_s} = 1$ (this is always possible); we can restore the original values later by asking dummy questions. Since the $a\_s$ are nondecreasing, there is an index $S$ such that $$ \sum\_{s=1}^S 2^{-a\_s} = \sum\_{s=S+1}^\infty 2^{-a\_s} = \frac{1}{2}. $$ The first question asked by the strategy is "$s \leq S$?". If the answer is affirmative, recurse on $a\_1-1,\ldots,a\_S-1$; otherwise, recurse on $a\_{S+1}-1,\ldots$. The left recursion is different from the right recursion, since $a\_1-1,\ldots,a\_S-1$ is finite; but a similar argument works, with a base case of $a\_1 = 0$, in which case no more questions need be asked. $\quad \square$

Given the lemma, we have reduced the question to the topic of the paper universal codes of the natural numbers, in which it is shown that no optimal strategy exists (in a certain reasonable sense formalized in the paper).

---
Tags: algorithms, complexity-theory
---


# Question
Title: How to write an if then logical constraint given part of the input related to a decision variable?
I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select a small number of vendors (F1) while meeting the specs of some client machines and maximizing a utility function (F2).

The first decision variable `Y[j,i,v] = 1 if machine j from vendor v is candidate for machine client i, 0 otherwise.`

The second one is related to the type of client machine defined as `Z[i,t] = 1 if machine i is of type t, 0 otherwise.`

Since the input regarding this decision variable is known I set it accordingly to the type. For instance, if machine 1 is of type 1 then Z\[1,1\] = 1 and so on and each machine has only one type so other values for machine 1 are set to be 0 (Z\[1,2\] = Z\[1,3\] =0, etc.).

The last decision variable is related to the selection of vendors `A[v]=1 if vendor v is selected, 0 otherwise.`

The input of the model is the set of machines with desired specs and types the clients want to buy, the vendors with their machines, specs and types. This is stored in different data structures.

Part of the input related to `Y[j,i,v]` contains the type of machines. Since the type of machines is known, I guess I do not need to include it in the definition of the decsion variable Y to be in the form of `Y[j,i,v,t]`. I would like to write a constraint saying that if machine client i is of type t then the machine candidate should be of the same type.

With the case of `Y[j,i,v,t]` it looks like : `Z[i,t] <= Y[j,i,v,t]`.

But with the case of `Y[j,i,v]` I am not sure how to connect it with `Z[i,t]` using a constraint knowing that t is part of Z and t is a known value in Y.

Anyone can shed some light on this matter? I am using Python and Gurobi as a solver. I attached the link to my linear program format file and the output provided by gurobi (vendors and gurobi\_output).

# Answer
> 1 votes
If you have two binary variables `X, Y` and you want to express the constraint `X implies Y` via a linear inequality you can use the logical equivalent statement `(not X) or Y`, which in linear programming translates to: $$(1-X) + Y \geq 1$$ In Gurobi-Code this would be: `model.addConstr((1-X) + Y >= 1, name="implication")`.

---
Tags: linear-programming, integer-programming, modelling
---


# Question
Title: Designing a context free grammar for a language; When to use the empty string
$L= \\{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \\{a,b\\}^\*\\}$ over the alphabet $\Sigma = \\{a,b,c\\}$

How can a grammar be created from the language without the use of the empty string. Below is my example that does use the empty string.

$S \rightarrow aaSac|B$

$B \rightarrow bBc|C$

$C \rightarrow aC|bC|\epsilon $

# Answer
> 2 votes
You can use the empty string, $\epsilon$ liberally. It could help you conceptualize the grammar easier and faster. For example, as you said, because $v\in\\{a,b\\}^∗$ that v can be one of $a,b$ or $\epsilon$, therefore using $\epsilon$ will help you to isolate non-terminal symbol $v$ as generating all words over the alphabet $\\{a,b\\}$ using just three rules.

On the other hand, language $L$ in the question, $L= \\{a^{2i}b^{j}vc^{j}(ac)^{i} | i,j \ge 0, v \in \\{a,b\\}^\*\\}$ can be generated by a context-free grammar without $\epsilon$ except one rule, $S\to\epsilon$. Here it is.

$S \rightarrow aaSac|B|aaac|\epsilon$
$B \rightarrow bBc|B|bc$
$C \rightarrow aC|bC|a|b$

You can obtain the above grammar by following the procedure to eliminate ε-rules, which can change any context-free grammar to an equivalent grammar that either does not use $\epsilon$ or just uses it once in the rule $S\to\epsilon$. Note that if the language includes the empty string, at least one usage of $\epsilon$ is inevitable; otherwise, it can only generate non-empty words. Finally, a grammar in Chomsky Normal form is designed to be such a grammar.

Just in case you might think every context-free grammar will use $\epsilon$ at least once, here is a grammar that does not use $\epsilon$.

$S\to a$.

In fact, for every grammar in Chomsky Normal form that uses $\epsilon$, you can remove that single rule, $S\to\epsilon$ to obtain a new grammar that does not use $\epsilon$. The languages generated by these two grammars are the same except the former one contains the empty string while the latter one does not.

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


title: Showing $2^x$ is a lower bound

text:
# Question
Title: Showing $2^x$ is a lower bound
How do I show that $2^x - x^2 \in \Omega(2^x)$?

Basically, I know that this means that $\exists a, x\_0 \in \mathbb{R^+}, \forall x \in \mathbb{N}, a.2^x \leq 2^x - x^2$.

I worked around a bit with this and I seemed to have gotten something that makes sense for the case of an upper bound; $$2^x -x^2 \< 2^x + x^2 \< 2^{x+1} = 2.2^n $$ Now, if I were trying to find an upper bound, I'd have chosen $a = 2$ and $x\_0 = 1$. How do I work the other way around(basically less than or equal to $2^x - x^2$ and prove this lower bound?

# Answer
> -1 votes
Here is the hint or outline of a proof.

* Show that by mathematical induction, that $2x^2\< 2^x$ for $x\>7$.
* Show that $\dfrac12\cdot2^x\< 2^x-x^2$ for $x\>7$

---
Tags: asymptotics, proof-techniques, lower-bounds
---


# Question
Title: Given a list of values, choose the greatest possible number of sorted values
Given an array of numbers, I want to select some entries, preserving their order, so that I end up with the longest possible sorted sub-array. It does not matter which entries I discard in the process. In case it matters, each value may only appear once.

How might I attack this problem?

Examples:

```
[1, 3, 2] - > [1, 2]
[4, 1, 5, 2, 6, 3, 7] - > [4, 5, 6, 7]
[4, 5, 6, 1, 2, 3] - > [1, 2, 3] or [4, 5, 6]

```

Any help would be greatly appreciated.

# Answer
My approach would be as follows.

I iterate through the input list, and at each step I consider the two possibilities:

* I either put the element in the result list if I can (that is, the current element is bigger then the last element)
* or I don't

While iterating, I maintain the set of partial solutions obtained so far.

As an optimization, I can remove from the set of partial solutions those that will not have the chance of becoming end solutions: at iteration $k$, if the longest partial solution has length $m$, I can remove all partial solutions whose length are smaller then $m-(n-k)$, where $n$ is the length of the initial list. This is because I can only grow the partial solution with $n-k$ elements in the best case.

Here is a sample run for \[1,3,2\]:

* iteration 1, partial solutions: \[\[1\],\[\]\]
* iteration 2, partial solutions: \[\[1,3\],\[3\],\[\]\]
* iteration 2, after filtering: \[\[1,3\],\[3\]\] (There is only one element left to visit, so I will not be able to extend \[\] to beat the \[1,3\] partial solution.)
* iteration 3, partial solutions: \[\[1,3\],\[3\]\]
* iteration 3, after filtering: \[\[1,3\]\]
> 0 votes

# Answer
Your problem is the well-known Longest Increasing Subsequence.

Wikipedia article contains details: https://en.wikipedia.org/wiki/Longest\_increasing\_subsequence
> 1 votes

---
Tags: algorithms
---


# Question
Title: Describing the Language of a grammar in set theoretic notation where the length of strings need to be remembered
I am not well versed in this topic so please pardon any ambiguous notation. I am trying to describe the language of this grammar in set-theoretic notation.

The Grammar is given by:

$ S \rightarrow ASA|B$

$ A \rightarrow a|b$

$ B \rightarrow BC|\epsilon$

$ C \rightarrow a|b|c$

I think I can accurately describe this language in english:

If $w=xyz$ is a string and $xyz$ are substrings of $w$ then

$|x| = |z|$, and $x$ and $z$ are made up of symbols from $\\{a,b\\}^\*$.

Furthermore, $y$ is made up of symbols from $\\{a,b,c\\}^\*$

Mores simply, the strings are made up of two ends that are the same $|length| \ge 0$ and made up of symbols $a,b$. And the middle part of the string is made up of any symbols from $a,b,c$ and also has a $|length| \ge 0$

How do I more formally and accurately describe the language of the grammar $L(G)$? Is it possible to do this in a set-theoretic notation?

# Answer
Your grammar generates $\Sigma^\*$, where $\Sigma = \\{a,b,c\\}$.
> 1 votes

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


# Question
Title: What is the algorithm for a decider to get the language accepted by a DFA?
I am trying to understand the larger problem of the decidability of the equality of two DFAs. I understand that this problem can be solved using minimizing DFAs, but my textbook states this can be done using symmetric difference.

Theorem: Let $EQ$ be a language, where $EQ$ = $\\{\<A,B\> \mid \text{A and B are both DFAs and L(A) = L(B)}\\}$. In my notation, $L(X)$ stands for the language that DFA $X$ recognizes.

Prove that $EQ$ is decidable. This relies on the symmetric difference of 2 sets.

Proof: Let $Q$ be a decider defined as:

On input $\<A,B\>$ do:

1. Construct a DFA $C$ such that $L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B)) $
2. Run $\<C\>$ on the algorithm used to determine if the language recognized by a DFA is $\emptyset$ (We proved this is decidable before, and I have no issues with that).
3. If that algorithm accepts, then $Q$ accepts
4. If that algorithm rejects, then $Q$ rejects

For $Q$ to be a decider, we must prove that $Q$ will halt. Since we have proven that the algorithm used in step 2 is decidable, it will halt. So I have no problems with steps 2-4.

But the first step, how can I prove that constructing $C$ in that way will halt? I understand that the symmetric difference will result in a regular language because of the closure properties, but how can a decider actually carry out this process and be guaranteed to halt?

So this is my primary question, what is the algorithm for determining the language that a DFA accepts? I.e. given DFA $X$, how can I determine $L(X)$ (Again, this must halt, so we can't try every string in existence or something like that).

Some follow up questions are: What if the DFA in question accepts an infinite set of strings, how can we possibly represent that on the decider's tape (or if the complement of $L(A)$ is infinite, etc.)? How can a decider determine the compliment of a set? And if $L(C)$ ends up being an infinite set of strings, how can we process that so that we can construct DFA $C$?

My book simply states

> These constructions are algorithms that can be carried out by Turing machines.

which drives me nuts! Prove it.

# Answer
> 2 votes
Suppose that $A,B$ are two DFAs on a common alphabet $\Sigma$ with states $Q\_A,Q\_B$, initial states $q\_{0A},q\_{0B}$, final states $F\_A,F\_B$, and transition functions $\delta\_A,\delta\_B$. We define a product DFA as follows:

* $Q = Q\_A \times Q\_B$.
* $q\_0 = \langle q\_{0A}, q\_{0B} \rangle$.
* $F$ consists of all pairs $(q\_A,q\_B)$ such that either $q\_A \in F\_A$ and $q\_B \notin F\_B$ or $q\_A \notin F\_A$ and $q\_B \in F\_B$.
* $\delta(\langle q\_A,q\_B \rangle, \sigma) = \langle \delta\_A(q\_A, \sigma), \delta\_B(q\_B, \sigma) \rangle$.

You can prove by induction that $\delta(q\_0, w) = \langle \delta\_A(q\_{0A}, w), \delta\_B(q\_{0B}, w) \rangle$, and so our definition of $F$ guarantees that the language of this DFA is the symmetric difference of $L(A)$ and $L(B)$.

In order to know whether $L(A) = L(B)$, we have to check whether their symmetric difference is empty. This happens exactly when no accepting state is reachable from the initial state in the product DFA, a condition which we can check using BFS/DFS.

---
Tags: turing-machines, finite-automata, decision-problem, sets
---


# Question
Title: How to find the number of Binary Search Trees with given number of nodes and leaves?
With 7 nodes of distinct values (**unique**), how many Binary search trees (BST) can be formed such that:

* Exactly $1$ leaf node(s) present?
* Exactly $2$ leaf nodes present?

I was able to solve the first one(and the actual problem was also that, but then I though what if the process can be extended)

> Here's my take on the 1st one

Here the elements are $1,2,3,4,5,6,7$ (let's assume that for simplicity) and we need only $1$ leaf

* So let us fix a root node: To fix the root node we have $2$choice either $1$ or $7$ from $1,2,3,4,5,6,7$
* (if we select any non-extreme elements then only $1$ leaf is not possible)
* Let us say we select $1$ as root node
* In each and every level we have $2$ different option that is to select i,e; either of extreme elements
* So in 2nd level we can select $2,3,4,5,6,7$
* Let us say we select $7$ in 2nd level
* We still have 2 option to select in $2,3,4,5,6$
* So this is true in all levels except last level since only $1$ element is left.
* Therefore, total possibilities are : $2 * 2 * 2 * 2 * 2$ = $2^5$

The same condition is true for $7$ as a root

Hence, $2^5\* 2$ (1 as root or 7 as root) = $2^6$.

(Which comes out as $2^{number of nodes -1}$)

But how can we now approach the second subpart or it can be generalized for let's say (2,3,4) leaf nodes?

* Exactly 2 leaf nodes present?

# Answer
You can compute the numbers with dynamic programming.

Let $c(n,l)$ be the number of BSTs with $n$ nodes and $l$ leaves, where the nodes are selected from a set of $n$ distinct nodes. Then we have the following recurrence relation in general cases,

$$c(n,l) = \sum\_{i=0}^{n-1}\sum\_{j=0}^l c(i,j)\cdot c(n-i-1, l-j)$$

* The outer summation is over $i$, the number of nodes in the left sub-BST of a BST with $n$ nodes and $l$ leaves.
* The inner summation is over $j$, the number of leaves in the the left sub-BST of $i$ nodes.
* The product $c(i,j)\cdot c(n-i-1, l-j)$ is the number of BSTs whose left sub-BST has $i$ nodes and $j$ leaves and whose right sub-BST has $n-i-1$ nodes and $l-j$ leaves. Please note that the root of such BST has only one choice, namely, the $(i+1)^{th}$ smallest node.

I will let you figure out the boundary values of $c(n,l)$ such as when $n=0$ or $n=1$ or $l=0$. There might be a few different cases. However, this should be enough to point you to the right direction.
> 2 votes

---
Tags: algorithms, data-structures, dynamic-programming, binary-search-trees
---