# Question
Title: Context free grammar for $a^i b^j a^j b^i$
I recently started learning context free grammars and was working on a couple of exercise problems and couldn't really figure out how would this exactly look like.

I started with:

$$\begin{align}S&\to S\_1S\_2\\ S\_1&\to aS\_1\mid\epsilon\\ S\_2&\to bS\_2\mid\epsilon\\ \end{align}$$

But I'm not sure how to create transitions for the reverse… Can someone give me some pointers or direct me in the right direction to find the solution?

# Answer
Context free grammars are basically the combination of four things:

* ***Alternation***: Choose one of two or more alternative sub-grammars.
* ***Concatenation***: Make one sub-grammar follow another one.
* ***Repetition***: Let a sub-grammar repeat any number of times.
* ***Recursion***: Nest a sub-grammar inside itself, like parentheses or palindromes. There are actually slightly more complicated possibilities for recursion, but the above two are a good start.

Consider the language which just consists of nested parentheses: $\epsilon$, $()$, $(())$, $((()))$, etc. One way of describing this language is $(^j)^j$, which is essentially the same thing as $a^jb^j$ (which you'll see in your task). Another way of describing that is to say that a valid sentence is either empty or a valid sentence with parentheses around it. The second description is precisely what this grammar is trying to convey: $$\begin{align}S\_2&\to(S\_2)\\ S\_2&\to\epsilon\\ \end{align}$$ That's a very simple example of recursion. Two things are important here:

* Although it doesn't look like a self-reflection with symbols $a$ and $b$, writing the symbols as parentheses makes that a bit clearer. Grammars don't care what symbols look like, so it's akin to a reflection in both cases. That might not look like a palindrome either, but that's because all the symbols in the right half are the same. Recursion matches a sequence followed by the reflection of the same sequence, but in a more general sense: you don't have to spell the elements in the same way in both halves.
* You can nest another sub-grammar at the reflection point simply by using it as the non-recursive alternative. (Think about how to write a grammar for the language $x$, $(x)$, $((x))$, $(((x)))$, etc. It just requires replacing $S\_2\to\epsilon$ with $S\_2\to x$.)

The key to writing context-free grammars for simple languages is to look for compositions of the four building blocks listed above. Recursion is probably the least familiar pattern, but it's at the core of this particular exercise.

In this case, there's a clear inner sub-grammar which generates $\epsilon$, $ba$, $bbaa$, … . And there's an outer nesting which puts that grammar in the middle of the forms $\epsilon$, $a S\_2 b$, $aa S\_2 bb$, … .
> 1 votes

# Answer
You are lucky, it’s quite easy for this case.

Your language is equal to the language $b^ja^j$ withe equal numbers of a’s and b’s in both sides. So the generate the $a^i$ and $b^i$ we use the rule S -\> aSb.

At some point we switch to generating $b^ja^j$. Starting with a non-terminal T, we have a rule T -\> bTa and another rule T -\> eps to finish. And at last one rule S -\> T to switch from one part to the other.
> 0 votes

---
Tags: automata, context-free
---


title: Complexity of T(n)=2T(n-1)

text:
# Question
Title: Complexity of T(n)=2T(n-1)
I built a recursion tree like this:

```
  0
 / \
 0  0
/\ /\
... ...

```

So the tree has height n, and width $2^n$. But if the sum of all levels is $\sum\_{i=0}^{n}0$, then is the function simply $O(1)$?

# Answer
> 0 votes
A sum of $m$ constants takes time $O(m)$.

---
Tags: complexity-theory, recursion, big-o-notation
---


# Question
Title: Dictionary with sets as keys where lookup can be set intersection
Normally, when working with dictionaries, we expect around O(1) complexity when we go to retrieve a value given the key (and when we insert). I work in Python, but this might apply to any dynamic typed language. I have been working with dictionaries where the keys are frozensets, which are just sets that are hashable and thus can be used as keys for your dictionary. I have a problem which would be magically solved if I could do "lookups" which are actually not key based, but set based. That is to say, it would be great if I had a data structure like a dictionary where I can pass in a set as a key and the data structure returns all values where the keys have a non-zero intersection with the key I passed in. I am quickly coming to the conclusion that this is never going to be O(1), but who knows. So, the question is, can we create a data structure that is basically a dictionary, but the keys are sets and it has a magic lookup ability where you can pass in a set and get all values back who's keys have non-zero intersection with the key (set) I passed in?

I imagined something to do with loading the values in. Firstly, you need keys that are sets of tuples (hashable). Then, when you load in a new value, you update the key to have a pointer to one other key and then these form long chains that do the job of getting you your sets of keys that meet the intersection criteria. This means that you push the complexity of insert way up, but lookup is fast. Apart from this, I have no idea, and I think a simple argument could be made that any such data structure will have either a bad O(N) insert or bad O(N) lookup, or both, where N is the number of keys.

# Answer
Unfortunately, no, this isn't achievable (at least not if you want to handle arbitrary sets as keys).

The reason is simple: if $N$ denotes the number of elements in a key set, then it takes $O(N)$ time just to read all of those elements, and any correct algorithm will have to read all of those elements to handle a query.

There is a simple data structure that might suffice: a dictionary that maps from each element to a list of all keys that contain that element. Then, given a query set, you can iterate over all the elements in the query set, look them up in the dictionary, and check whether any of them are an element of any stored key.

While this is linear time in the size of the query set, note that the running time is only a constant factor of the time it takes to create the query set. So there is a sense in which this is a constant-factor overhead, and thus the best you could hope for (in asymptotic analysis).

Where you might be able to do better is if you knew there was some structure on how query sets were created. For instance, suppose every query set was created via the union of two prior query sets, the intersection of two prior query sets, or by inserting an element into a prior query set. Then we could improve on the above data structure. If you have some more specific situation, I suggest pondering exactly what are the operations the data structure has to be able to handle and then asking a new question about how to support those operations efficiently.
> 3 votes

# Answer
My understanding: You might have three values in the table with keys (a, b), (a, c), (b, c). When you lookup (d, e, c) you want the values for the keys (a, c) and (b, c) containing a “c”.

First you implement a hash-table like data structure where a key can occur multiple times. When a key/value set is added or removed to the original hash, all strings in its key set are added or removed in the second set.

Your lookup function in this second set would actually iterate and return all the values. And to lookup a set in the original hash, you lookup all strings in the key set in the second set.
> 2 votes

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


# Question
Title: Can a Turing machine quickly move to any position of a large string?
Note this question was originally asked on Theoretical CS Stack Exchange, but it is not a research level question so it is being closed, and I am asking here instead.

Suppose we simulated a Turing machine on a long string $s$, where $|s| = 10^{100}$ for example. Then if we wanted to learn the value of $s\_i$, the $i$th value in the string, could we do this in say time polynomial in the length of the string?

The issue I am having is differentiating between the theoretical construction of the Turing machine vs. real computers which can for example index arrays in constant time due to their structure in memory. Could a TM obtain $s\_i$, the ith value in the array, in time polynomial in $|s|$, regardless of the chosen value of $i$? Or would the head have to "slide over to $i$" with some cap on it's speed, so it could not do this task efficiently?

# Answer
It depends.

1: If there are at least $\lceil \lg |s| \rceil$ unused cells after the end of $s$ and the head starts within $s$, then the answer is yes.

Here is how. Start from the beginning of $s$. Insert the binary representation of $i$ after the first symbol of $s$ (you can do this by copying the rest of $s$ $\lceil \lg |s| \rceil$ positions to the right). Call this the "counter". Now repeatedly do the following, until the counter reaches zero: decrement the counter by one, then copy the counter one position to the right and the next element of $s$ one position to the left. At any intermediate time step, the tape contains $s\_1 s\_2 \dots s\_j$, then the binary representation of $i-j+1$, then $s\_{j+1} s\_{j+2} \cdots$, and each iteration increments $j$ by one and decrements the counter by one.

2: If the Turing machine's head starts outside of $s$, then the answer is no. The head might be arbitrarily far away from $s$ (say, a number of cells away that is exponential in $|s|$).

A Turing machine has no way to "jump" to a position. It doesn't have random access. Instead, it can only move the head one position per step. Also, it needs a way to keep track of how far to move the head.
> 3 votes

---
Tags: turing-machines, search-problem
---


# Question
Title: Determining whether the problem of given a turing machine figuring out whether the language it accepts is the set of prime length inputs is R.E
I'm trying to figure out whether the following problem is R.E.?

Given a turing machine $M$ with alphabet $\Sigma$ is it the case that:

$L(M) = \\{w \in \Sigma^\* | |w| \space is \space prime\\}$

I think I have a reduction from $HALT$ complement which is co - R.E. to the problem proving that it's not R.E. but I'm not entirely sure if it's correct (Define a new turing machine which on input y runs M on w for |y| steps and rejects if M halts on w in |y| steps, else perform sieve and accept iff |y| is prime) but I'm not sure if this is correct.

# Answer
I think your reduction is correct. Indeed, the reduction is clearly computable and furthermore if the original Turing machine $M$ halts on (the fixed) input $w$, then the set of words accepted by the new Turing machine $M'$ is a finite set of words (of prime length), while if $M$ does not halt on input $w$, then the words accepted by $M'$ are precisely those words which have prime length. Thus your problem is $coRE$-hard.

Let me also point out that it is in fact even harder than $coRE$-hard: it is $coRE^{RE}$-complete (here $coRE^{RE}$ is the complement of languages that can be enumerated by a Turing machine that has an oracle to the halting problem). The lower bound can be proved by reducing the following $coRE^{RE}$-hard problem to it: given a Turing machine $M$, determine whether it halts on every input. The reduction is very similar to the reduction that you already used. On input $w$, our Turing machine $M'$ simulates the given Turing machine $M$ on every input of length $|w|$, and if $M$ halts on every such input, then $M'$ accepts iff $|w|$ is prime.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Amortized analysis on a dynamic table that grows its size by $\sqrt{size} $
The following problem is based on the section about *dynamic table* as part of the discussion about *amortized analysis* in CLRS

**Problem:** We are given a dynamic table $T$ that supports INSERT operation, implemented as an array and allows a constant amortized time per operation. Change the data structure so that when the array is full its size is increased by $\sqrt{T.size} $, i.e., the new size is $T.size +\sqrt{T.size}$.
Show, that the amortized time per operation is $ \Theta( \sqrt{n} ) $, in other-words, show that the total complexity that is needed for a sequence of $ n $ operations in the W.C. is $ \Theta(n\sqrt{n}) $.

**Attempt:** I really have no idea, I've been stuck on this problem for a few days and I would really appreciate a fat hint. Here's what I did though,
Consider the $i$-th INSERT operation,
If we insert an element and there is no expansion of the table then
$ T.size\_{i} = T.size\_{i-1} $ , $ T.num\_i = T.num\_{i-1} + 1 $ , $ c\_i = 1 $.
If we insert an element and there is an expansion of the table then
$ T.size\_{i} = T.size\_{i-1} + \sqrt{T.size\_{i-1}} $, $ T.num\_i = T.num\_{i-1} + 1 = T.size\_{i-1} + 1 $ , $ c\_i = i+1 = T.size\_{i-1} + 1 $

Where $ c\_i $ is the cost of the $i $-th operation. $ T.size\_i $ is the size of the table at the $i $-th operation. $ T.num\_i $ is the number of elements in the table at the $i $-th operation.

Let us look at a sequence of $n$ TABLE-INSERT operations on an initially empty table.

If the current table has room for the new item (or if this is the first operation), then $c\_{i}=1$
If the current table is full, however, and an expansion occurs, then $c\_{i}=i:$ the cost is 1 for the elementary insertion plus $i-1$ for the items that we must copy from the old table to the new table.

The total cost of $n$ TABLE-INSERT operations is therefore

$\sum\_{i=1}^{n} c\_{i} \leq n+ \[ ( 1+ \sqrt{1} ) + ( ( 1+ \sqrt{1} ) + \sqrt{ 1+ \sqrt{1} } ) + ... \] $

**\[** Well, this is it, I'm stuck from here on **(** I made a few more things on a draft paper which I don't think are worth writing, one of them is trying to solve the recurrence relation when the table expands $ T.size\_{i} = T.size\_{i-1} + \sqrt{T.size\_{i-1}} $, whose solution won't be of any value **)**. the $n$ comes from $n$ elementary insertions into the table. My trouble is the expression $ \[ ( 1+ \sqrt{1} ) + ( ( 1+ \sqrt{1} ) + \sqrt{ 1+ \sqrt{1} } ) + ... \] $ which comes from the table's expansion, **I'm stuck at realizing how many times we add this sum and what it sums to**, this is my main difficulty in the problem. **\]**

I understood the section about dynamic tables in the book and its analysis as it appears in the book when the table size grows at a constant factor of 2, but due to the nature of the problem above ( the table size does not grow constantly ), I'm having trouble wrapping my head around it.

---

I have some direction for the amortized analysis using accounting method ( but nevertheless, I'm supposed to find the worst-case tight bound for the sequence of operations for which without, my amortized analysis won't have a validation ):
In the moment of the expansion of the table, if the number of cells was $ k $ then $ \sqrt{k} $ cells will be added. For every element that I'll put into the table i'll buy $ \sqrt{k} + 2 $ coins, one coin will be used for insertion and the rest I put into the bank, such that for every inserted element into the $ \sqrt{k} $ cells, I keep $ \sqrt{k} + 1 $ coins. I fill $ \sqrt{k} $ cells and thus, in the bank, I have at the end of the filling process, $ \sqrt{k}\cdot (\sqrt{k}+1 ) = k + \sqrt{k} $ coins. ( Now I'll have to talk about how to take out the coins out of the bank at the moment of the expansion to pay for the expensive operation of expansion, but this explanation is the heart of the amortized analysis explanation ).

# Answer
> 2 votes
Assume $n\ge2022$. Consider a sequence of $n$ INSERTs.

***Lower bound of time for $n$ INSERTs***
Each expansion that has been done expands the capacity by no more than $\sqrt n$. So at least $n/\sqrt n=\sqrt n$ expansions has happened.

Consider the last $\frac{\sqrt n}2$ expansions. The earliest one of them happens when the number of elements is at least $n-\frac12\sqrt n\sqrt n=\frac n2$. So the total time-cost of these expansions is at least $(\frac n2+\sqrt{\frac n2})\cdot(\frac12\sqrt n)\ge\frac n4\sqrt n$.

***Upper bound of time for $n$ INSERTs***
Consider four consecutive expansions, assuming the first starts at size $k$. The first expansion increases the capacity by $\sqrt k$. The second expansion by $\sqrt{k+\sqrt k}$. The third by $\sqrt{k+\sqrt k +\sqrt{k+\sqrt k}}$. The fourth by $\sqrt{k+\sqrt k +\sqrt{k+\sqrt k}+\sqrt{k+\sqrt k +\sqrt{k+\sqrt k}}}\ge\sqrt k + 1$. So with every third expansion, the size of capacity increase increases by at least $(\sqrt k + 1)-\sqrt k=1$.

Hence the increase of capacity at $t$-th expansion is at least $t/3$. the total increase of capacity by the first $3t$ expansions is at least $3(1+2+\cdots+(t-1))=\frac{3(t-1)t}2$. On the other hand, the capacity is no more than $n+\sqrt n$ after $n$ INSERTs. Let $e$ be the number of expansions that happens during $n$ INSERTs. Then $$\frac{3(e/3-1)e/3}2 \ge n + \sqrt n,$$ which implies $e\le 6\sqrt n$.

Each expansion takes at most $n+\sqrt n$ time. so all expansions take at most $e(n+\sqrt n)\le 6n\sqrt n$ time. Including the time to assign $n$ values, which take $n$ time, the total time is at most $7n\sqrt n$.

***So, the total time for $n$ INSERTs is $\Theta(n\sqrt n)$.***
The reasoning above are sloppy here and there. To some people including myself, it might be considered as a proof that is good enough. To some people including myself, it may not be acceptable. Anyway, this answer should be good enough to be "a fat hint".

# Answer
> 0 votes
You can't use the physicists' or accountants' method, as these are only applicable for proving an *upper* boundon the amortized cost, and you need a *lower* bound.

Consider the time it takes to double in size from $n$ to $2n$. Each expansion adds at most $\sqrt{2n}$ items. There are thus at least $(2n-n)/\sqrt{2n} = \Theta(\sqrt{n})$ expansions. Each expansion copies at least $n$ items, so the total cost to double is $\Theta(n\sqrt{n})$.

---
Tags: algorithms, algorithm-analysis, amortized-analysis, dynamic-array
---


# Question
Title: Combinational logic check if bits is prime
I wonder if there's Digital Logic Circuit (using combinatorial logic gates) that check if number is prime or not.

For example given input fixed 8-bit that will produce 1-bit output.

00000101 will produce output 1 (1 means prime)

00000110 will produce output 0 (0 means composite).

I know it's possible if using Sequential Logic, well basically when you program to check if number is prime with high level program language such as Python is one of example Sequential Logic at cost of time.

While when using Combinational Logic, it's instantanously (not sure due to delay propagation from electricity) computed at cost of many logic gates will be used.

# Answer
> 5 votes
There is no known regularity in the primes, and for small numbers (such as 8 bits naturals), the best is to implement them as a table.

If you want an instant answer, one comparator per prime can do. Otherwise, binary search can be implemented in hardware, possibly storing a binary trie. Or simply an array of bits, one per integer.

# Answer
> 2 votes
Of course, the circuit will just grow rapidly. For 8 bits there is no problem.

You check whether bit 0 is 0 or 1. If it is 0, then you check whether the input is 2.

If it is 1, then you check bit 7. If bit 7 is set then n must be one of the primes from 67 to 127, otherwise it must be one of the primes from 3 to 61. In each case, you check bit 6, and n must be an odd prime in a range of 64 integers, and so on. For example in the branch with bits 00001xx1, there are two primes 11 and 13, so the remaining two bits must be 01 or 10.

For k bit input you will need roughly $2^k$ gates, and the delay should be roughly k gates.

---
Tags: logic, boolean-algebra, primes, digital-circuits, combinatory-logic
---


# Question
Title: Difference between cost and the heuristic function in A* search
Looking at the image above, thinking in terms of A\* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd see the heuristic function here as the number of direct steps. Or the number of cities we pass through, for example. The cost then is the number of miles between each city.

Am I right in thinking that it's the number of direct paths before we reach a path where there are multiple choices?

What confused me is, that I've also seen other examples where these numbers don't add up. For instance the image below:

The numbers in the second image don't add up the number of nodes on any path. Is it a case that the heuristic function varies from problem to problem, and I shouldn't think about how those numbers were generated too much? And that heuristic functions themselves are a separate problem, that we're just taking for granted in these two images?

# Answer
Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image. But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "better" choice. Theoretical proof can be found in aima(I forget the exact page, sorry), but in practice, you need to ensure heuristic function follow the "triangle inequality"(in a graph version search.If you work on a tree, limit is not that strict, you can check the book above). And that will give you an optimal A\* search.

triangle inequality is almostly same as formula in math and direct distance satisfies it naturally. That's why it's usual to use direct distance as a heuristic(if allowed).

> if we say function $f$ satisifies triangle inequality, it means $\forall x,u,v ,f(u,v) \< f(u,x)+f(x,v)$. In A star algorithm, we take $h(x)=h(x,target)$ by default. Intuitively, it says it's always further if you take a detour than directly go ahead.

Heuritics is chosen by yourself, but cost is attribute of the problem itself. You can change Heuritics to whatever you like, as long as it satisfies triangle inequality. But you can't change cost function.

I think trying to prove the optimal property is important for beginner, which helps you understand how algorithm is working. Forgive me for saying so much.
> 4 votes

---
Tags: graphs, heuristics, search, a-star-search
---


# Question
Title: How can I prove that LTL formula is valid?
I do not know with which technique i can prove if a LTL forumula is valid.

Let's say we have for example this one: ¬q U(¬p ∧ ¬q) → ¬Gp. How can prove if this valid or not? (should be true in any state of any model).

# Answer
There are two main technique in order to prove validity (or more in general, to solve the problem of satisfiability over a definite model) for a LTL formula.

The first one is based on semantic tableau, analogous to the case of modal logic, here you can find some explanations.

The other one is based on automata, in particular it is possible to translate a formula in a Buchi automaton, and then one can check satisfiability paths on the automaton. In the case of the validity, you have to translate the **negation** of your formula and verify that the automaton you get is the empty one. This can be performed algorithmically, this is a useful tool (by the way, you formula is actually valid, try inserting this string: NOT(((NOT q)U(NOT p && NOT q))-\>NOT G(p))), at the same page you can find reference about the implementation of the translation algorithm.
> 1 votes

---
Tags: logic, model-checking, linear-temporal-logic, logical-validity
---


title: Limited tapes-version TM for pair sum

text:
# Question
Title: Limited tapes-version TM for pair sum
In the problem of pair-sum we are given a multiset $A$ and a number $\alpha$. We are asked to find whether there is a pair ($2$ numbers) of $A$ s.t. their sum is $\alpha$. Here all numbers are small/constant, $O(1)$, sum of $2$ small numbers requires $O(1)$ actions and their size is $O(1)$ bits for representation.

I'd like to analyse an efficient algorithm for this. The algorithm sorts $A$ and then iterates over the endpoints. If their sum is less than $\alpha$, we will check the second smallest element and the largest. If their sum is larger, we will check the smallest and the second largest. So on and on.

This algorithm takes $O(n\log n)$ due to sorting. However, trying to write it as a single-work tape TM, I'm having trouble. Assuming we have $2$ tapes: one read only tape for the input, and another read/write for the working process.

Sorting the array and writing it on the TM takes $O(n\log n) $ by merge sort, using a single tape. However, what about the process itself of comparison?

If we had $2$ tapes, or a single tape with $2$ access heads, we could have done trivially in $O(n)$. But having a single tape seems to be problematic, as I might run back and forth many times, and running back and forth might take $O(n)$.

My question follows: is there a way to implement this algorithm, or any other algorithm for pair-sum, such that it will need $O(n\cdot \log n)$ runtime, on a TM with $2$ tapes: the first is read only and the second is read-write?

# Answer
Summary: There is no need to sort the given numbers since whether there are two numbers in $A$ such that their sum is $\alpha$ depends on the *set* of numbers in $A$. Since the choices for the set of numbers in $A$ is $O(1)$, there is an $O(n)$-time algorithm/TM with one read-only tape.

---

Assume that multiset $A$ and a number $\alpha$ are given as $c\_{a\_i}\square c\_{a\_2}\square\cdots\square c\_{a\_m}\square' c\_{\alpha}$ as input on the tape, where

* $c\_{a\_i}$ stands for the cells that represent $a\_i$, the $i$-th number in $A$ as a binary number.
* $c\_{\alpha}$ stands for the cells that represent $\alpha$ as a binary number.
* $\square$ and $\square'$ are two field separators (neither of them appear in $c\_\*$).

Since "their size is $O(1)$ bits for representation", there is a constant $c\in \mathbb N$ such that each number in $A$ uses at most $c$ cells, i.e., $a\_i\in \[2^c\] = \\{0,...,2^c−1\\}$.

Let us specify Turing machine (TM) $M$ as follows.

Given the input as described above, TM $M$ will,
for each number $x\in\[2^c\]$:
check whether $x$ is in $A$. If yes, for each number $y\in \\{x+1, x+2, \cdots, 2^c-1\\}$:
check whether $y$ is in $A$. If yes, check whether $x+y=\alpha$. If still yes, halt and accept.
for each number $x\in\[2^c\]$:
check whether $x$ appears in $A$ at least twice. If yes, check whether $2x=\alpha$. If still yes, halt and accept.
Halt and reject.

Since $c$ is a constant, we can hardcode all "for" loops, $x$, $y$, the result of each check, $x+y$, $2x$, etc. using states and state transitions of $M$. There is no need to alter any tape cell.

Each "check" above involves moving the head of $M$ from the start of the input to the end of the input, and then back to the start of the input, which takes $O(n)$ time. The total running time of $M$ is no more than $2^c2^c2O(n) + 2\cdot2^cO(n)$, which is $O(n)$ still.

We can improve the algorithm/$M$ so that it could run faster with less states. However, that is another task.
> 3 votes

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


# Question
Title: Why 2- way DFA is equivalent to NFA (and thus DFA)?
We know that A read-only Turing machine or Two-way deterministic finite-state automaton (2DFA)is class of models of computability that behave like a standard Turing machine and can move in both directions across input, except cannot write to its input tape. The machine in its bare form is equivalent to a Deterministic finite automaton in computational power, and therefore can only parse a regular language.

This language $L = \\{ (u\\#,v\\#)| u, v \in(a,b)^\*, |u|=|2v| \\}$ is checked by 2-way DFA but not possible to check $|u|=|2v|$ by DFA ,so my question is how could we say 2-way DFA is equivalent to DFA? Because by 2-way DFA we are able to check $|u|=|2v|$ but not possible by DFA or 1-way DFA.

# Answer
> 4 votes
The language $L=\\{ (u\\#,v\\#) \mid |u|=|2v|\\}$ from your question is actually a two-dimensional language, that is a relation between two strings, each written on their own input tape. In that way the condition $|u|=|2v|$ is easy to check, even with a deterministic one-way (two-tape) automaton: when the head moves one cell on the $v$-tape, the head on the $u$-tape moves two cells.

On the other hand, the condition $|u|=|2v|$ is indeed impossible to check for a classical, single tape, finite state automaton.

In general, for a single tape, the two-way finite automaton is as powerful as the classical (one-way) finite state automaton. (Both deterministic and non-deterministic variants.) One of the possible proof I have seen uses the concept of "crossing sequences", for each cell we record the sequence of states that the 2NFA had when entering/leaving that cell from/to its left neighbour. This in a way summarizes the 2-way computation in a one-way fashion.

Perhaps the number of tapes is not what determines the difference in power. A two-tape automaton has two heads, which can independently read letters. If a one-tape automaton is equipped with two heads, we can also accept languages like $\\{ u\\#v \mid |u|=|2v|\\}$.

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


# Question
Title: Checking my Pushdown automaton for $L = \{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j > 0 \}$
Could someone please help me check if my automaton is correctly designed?

$$L = \\{ 0^i1^j2^{i+j} | i \ge 0, j \ge 0, i+j \> 0 \\}$$

This was an exercise from our workbook, but their solution is a bit different

# Answer
> 1 votes
First of all your language is DCFL so there exist at least one DPDA for your language but you made NPDA because at state $q\_0$ ,$\delta(q\_0,0,A)\neq\emptyset$ and $\delta(q\_0,\epsilon,A)\neq\emptyset$ makes your diagram NPDA by the formal definition of DPDA.

Your language has 3 cases:

$Case:1$

If $i =0$ and $j\neq 0$, then the condition $i+j\>0$ is satisfied. In this case language becomes $L\_1=\\{1^j2^j\\}.$

Algorithm to make DPDA:

Push $1$'s and pop $1$'s against $2$'s.

$Case:2$

If $j =0$ and $i\neq 0$, then the condition $i+j\>0$ is satisfied. In this case language becomes $L\_2=\\{0^i2^i\\}.$

Algorithm to make DPDA:

Push $0$'s and pop $0$'s against $2$'s.

$Case:3$

If $i\neq 0$ and $j\neq 0$, then the condition $i+j\>0$ is satisfied. In this case language becomes $L\_3=\\{0^i1^j2^{i+j}\\}.$

Algorithm to make DPDA:

Push $0$'s and $1$'s, and then pop $1$'s and $0$'s against $2$'s.

Now combining all above 3 cases your language becomes $L=\\{12,1122........,02,0022,........0122,00112222\\}.$

Final transition function for DPDA: By taking $q\_0$ is initial state, $Z\_0$ as stack bottom, $q\_f$ is final state.

$\delta(q\_0,1,Z\_0)=(q\_0,1Z\_0).$

$\delta(q\_0,1,1)=(q\_0,11).$

$\delta(q\_0,0,Z\_0)=(q\_0,0Z\_0).$

$\delta(q\_0,0,0)=(q\_0,00).$

$\delta(q\_0,1,0)=(q\_0,10).$

$\delta(q\_0,2,1)=(q\_1,\epsilon).$

$\delta(q\_0,2,0)=(q\_1,\epsilon).$

$\delta(q\_1,2,0)=(q\_1,\epsilon).$

$\delta(q\_1,2,1)=(q\_1,\epsilon).$

$\delta(q\_1,\epsilon,Z\_0)=(q\_{f},Z\_0).$

State diagram for DPDA: All languages $L\_1, L\_2$ as well as $L\_3$ is accepted by this DPDA.

N. B:- In your question $i$ and $j$ both simultaneously are not $0$ because otherwise the condition $i+j\>0$ will be failed. The above diagram is acceptance by final state, you could make the diagram acceptance by empty stack(left for you which is your homework).

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


# Question
Title: Decomposing large bit mult or exp into smaller bit operations
Imagine a machine that can only hold N-bit values (N-bit uint).

The machine can also calculate the 2N-bit result of two operations: mult, exp. The 2N-bit result is stored across 2 N-bit values (high/low bits).

How could we then code the mult (or exp) of 2 2N-bit values that would result in a 4N-bit value? The 2 2N-bit inputs would be stored across 4 N-bit values and the 4N-bit result would be stored across 4 N-bit values as well.

Is there somewhere I can read about the kind mathematical breakdown to code this? Needed for a real world assembly coding.

thx

# Answer
> 1 votes
For product, here is the idea: $$(2^NA + B)(2^NC + D) = 2^{2N}AC + 2^N(AD+BC) + BD.$$ Exponentiation isn't a primitive operation in integer arithmetic.

---
Tags: algorithms, discrete-mathematics, binary, assembly
---


# Question
Title: Is the given language regular, CFL or in P
someone sent me a question lately and I wasn't able to solve it so I'm asking for help.

***Question:*** Given the language $$L=\\{w\in\\{0,1\\}^\*:|w| \text{ is even and the first half of it has a balanced string of length } 100\\}$$

**Balanced:** A string $w\in\\{0,1\\}^\*$ is said to balanced if it has the same number of $0$'s and $1$'s in it.

My suggestion:

1. Since the number of balanced strings of length 100 is finite build a DFA for each balanced string of length 100 that accepts it.
2. Build a new NFA which has an initial state that has $\epsilon$ edge to each one of the initial states of the DFA's in section 1. Moreover, the initial state has a loop on it that accepts $0$'s and $1$'s.
3. From each accepting state of the DFA's from section 1 add $\epsilon$ edge to a new accepting state of the NFA from section 2. The new accepting state also has a loop on it that accepts $0$'s and $1$'s.
4. Remove all the accepting states of the NFA except for the accepting state of section 3. The same thing for the initial state, remove all the initial states of the NFA except for the one of section 2.

So this suggestion works perfectly as I assume but it's problem that it can accept balanced words of length 100 **beyond** the first half of $w$. What can I do in that case?

***Note:*** The language could be not regular but I assume that it's regular so I'm trying to build NFA for it, please correct me if I'm wrong.

# Answer
> 3 votes
If a word is in your language, then it is of the form $w\_1w\_2$, where $|w\_1| = |w\_2|$ and $w\_1$ contains a balanced string of length $100$, say $y$. Note that there are finitely many options for $y$. We can write $w\_1 = xyz$. Now let's break $w\_2$ into $z'y'x'$, where $|x| = |x'|$, $|y| = |y'| = 100$ and $|z| = |z'|$. If $|x| = i$ and $|y| = j$, then $w$ belongs to $$ \Sigma^i y \Sigma^{2j + 100} \Sigma^i. $$ You take it from here.

---

To show that your language isn't regular, consider words of the form $0^i 1^{50} 0^j$.

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


# Question
Title: If P=NP, are all P problems NP-complete?
In my understanding, if we could prove one of the NP-complete problems is a P problem, then all of the NP problems are P problems. Because P problems are NP problems and NP problems are P problems, P=NP.

I thought if P=NP, then all NP-complete problems are also P problems, but not all P problems are NP-complete.

But it seems that if P=NP, P=NP=NP-complete problems.

I wonder what my blind spot is.

Thanks in advance!

# Answer
> 1 votes
In order to be NP-complete, the problem has to be also NP-hard. That means, there exists a polynomial-time reduction from SAT to the given problem. The mapping has to map all satisfiable instances of SAT to YES-instances of the problem, and all unsatisfiable instances of SAT to NO-instances of the problem. This means that, any NP-hard problem has to be nontrivial: there should be at least one YES-instance and at least one NO-instance.

On the other hand, if you think about it, that is precisely the sufficient condition to be NP-hard: if your problem has both an YES-instance and a NO-instance, then you can design a simple polynomial-time reduction from SAT: given a SAT-instance $f$, decide if $f$ is satisfiable or not in polynomial-time (possible since P=NP), and if it is satisfiable, then map it to the YES-instance, and if not, map it to the NO-instance.

So, when P=NP, all P problems are NP-complete, except those trivial problems where all answers are YES, or all answers are NO.

# Answer
> 0 votes
AYun's right. I was confused by the "trivial" instances in P because there is no mapping from SAT to an all-yes problem.

Here is original Answer:

$NPC\subset NP$, that's your possible mistake. Do not use **equal**, because they are not equal at all.

---
Tags: np-complete
---


# Question
Title: Are the clusters in a cluster graph complete graphs?
I read two definitions of cluster graphs that seem in conflict to me. One is from Koller:

> We begin by defining a *cluster graph* — a data structure that provides a graphical flowchart of the factor-manipulation process. Each node in the cluster graph is a *cluster*, which is associated with a subset of variables; the graph contains undirected edges that connect clusters whose scopes have some non-empty intersection. We note that this definition is more general than the data structures we use in this chapter, but this generality will be important in the next chapter, where we significantly extend the algorithms of this chapter.
>
> Definition 10.1: A cluster graph $\mathcal{U}$ for a set of factors $\Phi$ over $\mathcal{X}$ is an undirected graph, each of whose nodes $i$ is associated with a subset $\boldsymbol{C}\_i \subseteq \mathcal{X}$ . A cluster graph must be family-preserving — each factor $\phi \in \Phi$ must be associated with a cluster $\boldsymbol{C}\_i$, denoted $\alpha(\phi)$, such that $\text{Scope}\[\phi\] \subseteq \boldsymbol{C}\_i$. Each edge between a pair of clusters $\boldsymbol{C}\_i$ and $\boldsymbol{C}\_j$ is associated with a sepset $\boldsymbol{S}\_{i,j} \subseteq \boldsymbol{C}\_i \cap \boldsymbol{C}\_j$.

Then I saw another definition on Wikipedia

Source: page 346, Koller, Daphne, and Nir Friedman. *Probabilistic graphical models: principles and techniques.* MIT press, 2009.

> In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster graphs are also called $P\_{3}$-free graphs.

Source: https://en.wikipedia.org/wiki/Cluster\_graph#:~:text=In%20graph%20theory%2C%20a%20branch,called%20P3%2Dfree%20graphs.

Unless I am reading this wrong, Koller's definition makes no requirement for completeness. According to Koller's definition, it seems to me that each $\boldsymbol{C}\_{i}$ need only be a subset of $\mathcal{X}$ with an arbitrary configuration of edges within the cluster, no specification that it need be a complete graph.

If I am correct these definitions are incompatible, can someone explain which one is correct?

If I am incorrect, I'd love to know why.

# Answer
You are reading it correctly. Those are two different uses of the word "cluster graph".

In graph theory, and usually in computer science, when you refer to a *cluster graph* it is of the latter kind.

For graph classes, the holy scripture is `graphclasses.org`, in which you can find Graphclass: cluster

> **Graphclass**: cluster
>
> Definition:
>
> A graph is a cluster graph if it is a disjoint union of cliques.
>
> **Equivalent classes**:
>
> * 2-leaf power
> * $P\_3$-free
> 2 votes

---
Tags: graphs
---


# Question
Title: How would I design a State Diagram (FSM) for a AC unit?
Ok so I'm learning Finite Automata in my Theory of Computation course and understand the basic FSM but can't wrap my head around this question: The AC should only turn on if a person is detected in the room and the temperature is hot (80 degrees or higher). It turns off when no one is detected in the room, the window is open, or the temperature is cold (32 degrees or lower).

# Answer
> 1 votes
Your question's answer could be solved by Finite Automata with output that is Moore Machine or Mealy Machine.

You have three cases:

$Case:1$ When temperature is equal or more than $80°$ then output is $1$(Turn on) which is associated with state i.e.$(q\_i, 1).$

$Case:2$ When temperature is less than $32°$ then output is $0$(Turn off) which is associated with state i.e.$(q\_i, 0).$

$Case:3$ When temperature between $32°$ and $80°$ then output is $a$(No action) which is associated with state i.e.$(q\_i, a).$

I have designed Moore Machine where output is associated with state.

State $q\_7$ falls under $case:1$ and states $q\_6, q\_{16}$ falls under $case:3$ and remaining states falls under $case:2.$

N. B. -- The binary representation of $80$ and $32$ is $1010000$ and $100000$ respectively.You have to design Mealy Machine by your own which is your homework. Simply just convert Moore Machine to Mealy from my diagram.

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


# Question
Title: Design a Pushdown automaton for $L = \{a^nb^m | n \le m \le 3n \} $
$L = \\{a^nb^m | n \le m \le 3n \\} $

This is by far the hardest pushdown automaton I had to design. I literally have no idea where to start. Here's my thought process. Firstly, I thought that for each valid pair $(n,m)$ the differences between the number of $b$s abd $a$s will be the same. That wasn't true, as the number of possible strings rose for each new value of $n$.

Next, I tried adding $a$ on top of the stack when I read $a$, and then removing them when I read $b$s. That would only cover the case when $m=n$. I can produce an automaton where $m=n$, $m=2n$ or $m=3n$, but how do I cover all the cases where $m \in \[n, n+1, n+2, ..., 3n\]$?

# Answer
> 1 votes
First of all your language is CFL means NCFL not DCFL because machine has push confusion. Therefore DPDA design is not possible. Only NPDA has power to accept your language.

You have to understand what is grammar for your language. Suppose $n=0,$ then $m=0$ and string becomes $\epsilon.$ So your language contain $\epsilon.$ Now for $n=1,$ then $m=1,2,3$ and strings are $ab, abb, abbb.$ For $n=2,$ then $m=2,3,4,5,6 $ and the strings are $aabb, aabbb$ etc. ... . .... . ... . ..

So your grammar will be $S\to aSb|aSbb|aSbbb|\epsilon.$

This time I haven't design NPDA as last time I did,I am writing only transition functions. Start state is $q\_0$ , stack bottom is $Z\_0$ and final state is $q\_f.$

$\delta(q\_0,a,Z\_0)=(q\_0,aZ\_0),(q\_0,aaZ\_0,(q\_0,aaaZ\_0).$

$\delta(q\_0,a,a)=(q\_0,aa),(q\_0,aaa),(q\_0,aaaa).$

$\delta(q\_0,\epsilon,Z\_0)=(q\_f,Z\_0). $

$\delta(q\_0,b,a)=(q\_1,\epsilon).$

$\delta(q\_1,b,a)=(q\_1,\epsilon).$

$\delta(q\_1,\epsilon,Z\_0)=(q\_f,Z\_0).$

---
Tags: formal-languages, automata, pushdown-automata, stacks
---


# Question
Title: Retreive farthest value to the right of element
I reached a subproblem where I have an array of numbers (0 to n) un-sorted and I want to retrieve, for each element, the index of the farthest value from it **to the RIGHT** of that element.

Like

```
0 1 2 3 4 5 6 7 8 (indexes)
0 3 7 5 4 2 8 1 6 (array)

```

so the answer would be

```
6 6 7 7 6 6 7 8 -1

```

Can anyone suggest some algorithm so that this information can be retreived in `O(n)`

Farthest is in the sense of absolute difference of values. Hence it means for index i, the index j would be farthest if

```
 abs(arr[k] - arr[i]) is maximum at k=j for all k>i

```

# Answer
Based on your sample, I would assume that farthest from $x$, means the value $y$ on the right of $x$ that maximizes $|x-y|$. And that's what I am using in my answer.

Observe that the farthest value is either the lowest or highest value among the elements on the right of $x$.

Let $min$ and $max$ be the inidices of the current minimum and maximum. Both are initially set to $n-1$. Let $A$ be your given array and $B$ be the array that will contain the index of the farthest value on the right. Initially $B\[n-1\] = - 1$. Let $i$ be the current index in $A$, which is initially set to $n-2$.

1. If $|A\[i\] - A\[min\]|\ge |A\[i\] - A\[max\]| $, let $B\[i\] = min$, else $B\[i\] = max$.
2. If $A\[i\] \< A\[min\]$, $min=i$.
3. If $A\[i\] \> A\[max\]$, $max=i$.
4. Decrement $i$. If $i\>0$, go to step 1., else stop.
> 3 votes

# Answer
I figured out that the maximum difference can only be found at the minimum or maximum value to the right of concerned value.

So, I start from end of the array in reverse order and keep track of max and min upto the traversed part (k to n-1)

Now, at each iteration, max(ele-min, max-ele) would be the answer for the element.

```
    int minI = idx.size()-1, maxI = idx.size()-1;
    vector<int> farthest(idx.size());

    for(int i=idx.size()-1; i!=-1; i--) {

        farthest[i] = ((idx[i]-idx[minI]) > (idx[maxI]-idx[i])) ? minI : maxI;
        minI = (idx[minI] > idx[i]) ? i : minI;
        maxI = (idx[maxI] > idx[i]) ? maxI : i;

    }

```
> 2 votes

---
Tags: algorithms, c++
---


# Question
Title: Find a simple path from S to T in a directed graph so that the product of its weights is maximum
I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the graph are larger than zero. For any pair of nodes, there might be more than 1 edge.

I thought of the following approach. First I invert all the edge weights, i.e $w\_{new} = \frac{1}{w}$. Then I run a shortest-path algorithm such as Dijkstra against the new graph. Is doing this ok? If not then which algorithm I can use for my problem?

# Answer
> 1 votes
The problem is NP-hard by a reduction from the Hamiltonian-path problem.

If all edge weights are set to some constant $c\>1$ and $P$ is a simple path from $s$ to $t$ that maximizes the product of the edge weights, you have that the number of edges in $P$ is $n-1$ (where $n$ is the number of vertices of the graph) if and only if the input graph contains a Hamiltonian path from $s$ to $t$.

Notice that the Hamiltonian path problem remains NP-Hard even if you fix the endpoints.

# Answer
> 0 votes
$$ \max \prod\_{i}p\_i\iff \max \sum\_{i}\log p\_i,\\,p\_i\>0 $$

So it's nearly equal to ask "single source longest path", which is NP-hard in most graphs. There is a Polynomial solution on DAG. algorithm

Here is origin answer, I preserve it to help others avoid similar mistakes :-( $\min$ and $\max$ are totally different!

Why not try to take logarithm of every edge's weight?

$$ \min \prod\_{i}p\_i\iff \min \sum\_{i}\log p\_i,\\,p\_i\>0 $$

But $\log p\_i$ might give a negative cycle(e.g. every edge's weight \< 1). Now it becomes another problem: simple-path, and this shows it's NP-hard.

But if $\forall p\_i \> 1$, you can solve it with dijkstra after preprocessing above. Because for graph without negative edge, dijkstra will always output a simple shortest path.

---
Tags: graphs, shortest-path, directed-graphs
---


# Question
Title: Designing a PDA without using CFG -> PDA for the language $ \{ a^nb^m | n \le m \le 2n \}$
$L= \\{ a^nb^m | n \le m \le 2n \\}$

As you may recall, I posted a question a few hours ago about designing a PDA for a language similar to the one I have now. I have seen that the easiest way to construct it is to define a CFG for the language, and then transform it to non-deterministic PDA *which accepts strings by empty stack*.

However, for this exercise, we have been forbidden to do that. We have to construct an automaton which accepts strings with a final state. Here's my proposed solution:

Here's my reasoning. If I was to construct a context-free grammar, the rules of production would be $S \to aSb | aSbb|\epsilon$. I tried to do something similar here by putting $a$ and $aa$ on the stack for the same input symbol and the same popped symbol from the stack, creating a non-deterministic PDA.

My question is: Am I correct to assume this is a correct interpretation of non-determinism?

# Answer
> 3 votes
Your language is NCFL. Your design of NPDA is perfectly right. And in state $q\_0,q\_1$ and $q\_2$ transitions makes your diagram NPDA. You accepts your strings by final state that is $q\_3.$ If you want to accept by empty stack(without final state) then no need to move and create the new state $q\_3.$ You just give the transition $(\epsilon,A/\epsilon)$ in state $q\_2$ that is $\delta(q\_2,\epsilon,A)=(q\_2,\epsilon)$ , then the stack will be empty.

---
Tags: automata, context-free, pushdown-automata, nondeterminism
---


# Question
Title: The class of problems that can be solved efficiently using physical means?
By "physical means", I mean, for example, using water pouring down tubes, or combining chemicals, etc. Basically, using some experiment in the physical world to perform some computation. I'll call this physical computation.

As the simplest example, if I want to add the numbers 3 and 5, I could just pour 3mL into a cup and 5mL into the same cup, and measure how many mL I end up with.

I know that physical computation will probably not be completely precise, but ignore that, and assume that all experiments and measurements are carried out at their theoretical perfect precision. Another way to think about it is that we have a perfect physics simulator that's efficient up to real time.

Let the class of problems that can be solved efficiently (in a polynomial number of steps) through physical computation be called Phys-P.

My question is: what is Phys-P's relation with P? Are there problems that physical compututation can solve faster than traditional computation? Does leveraging nature and physics give you an exponential speed-up? I'd like to think yes, but I can't think of a particular NP-hard problem that physical computation would solve efficiently. Maybe something like how the structure of a crystal that grows (given some initial conditions) will solve TSP, or something like that.

If possible, I'd like to keep BQP (e.g. quantum computation) out of the discussion, and focus on running physical/chemical experiments.

# Answer
> 3 votes
It's not clear what "can be solved" actually means here. Let me explain with a real example.

It is known that NP-hard problems can be solved on an analog computer in polynomial time.

Suppose that you have a SAT problem in CNF with $m$ clauses and $n$ variables.

Define $c\_{i,v}$ to equal $1$ if variable $v$ appears positively in clause $i$, $-1$ if variable $v$ appears negatively in clause $i$, and $0$ if it does not appear in clause $i$. So, for example, if this is clause $5$:

$$x\_{3} \vee \bar{x}\_{10} \vee x\_{31}$$

Then $c\_{5,3} = 1$, $c\_{5,10} = -1$, $c\_{5,31} = 1$, and for all other $j$, $c\_{5,j} = 0$.

To find the solution to the SAT problem, we use spin variables $s\_v$ where $s\_v = -1$ if $x\_v$ is false in a satisfying assignment, and $s\_v = 1$ if $x\_v$ is true in a satisfying assignment.

For each clause $j$ we define the function:

$$K\_j(\vec{s}) = 2^{-k\_j} \prod\_{v} \left( 1 - s\_v c\_{j,v}\right)$$

where $k\_j$ is the number of variables in clause $j$.

Notice that clause $j$ is satisfied exactly when $K\_j(\vec{s}) = 0$. So this is a constrained optimisation problem, which has a standard solution by introducing Lagrange multiplier variables $a\_j$. The Lagrangian is:

$$\mathcal{L}\left(\vec{a},\vec{s}\right) = \sum\_{j} a\_j K\_j(\vec{s})^2$$

And a solution is any point where:

$$\nabla\_{\vec{a},\vec{s}} \mathcal{L} = 0$$

The Lagrangian in this case is positive definite, so on an analog computer, you can solve this system using gradient descent. Make the variables $s\_v$ and $a\_j$ functions of time, and set up this system of differential equations:

$$\begin{eqnarray\*}\frac{d s\_v}{dt} & = & - \sum\_{j} 2 a\_j c\_{j,v} \frac{K\_j(\vec{s})^2}{1 - c\_{j,v}s\_{v}} \\ \frac{d a\_j}{dt} & = & a\_j K\_j(\vec{s})\end{eqnarray\*}$$

(Note that in the equations for $s\_v$, you don't actually need circuitry to perform the division, since the divisor is a factor of $K\_j$.)

This dynamical system, if implemented on an analog computer, will find the solution in polynomial time.

Oh, but there's a catch. There's always a catch. The formal solution for the Lagrange multiplier variables is

$$a\_j(t) = a\_j(0)\\,e^{\int\_{0}^{t} K\_j\\,dt'},$$

which is to say, the voltages become exponentially large over time if the problem is stiff.

So while SAT can indeed be solved in polynomial time on an analog computer, it's not clear that this computer is physically realisable in practice.

# Answer
> 2 votes
No one knows. The extended Church-Turing hypothesis is sometimes described as saying that the answer is Phys-P = BPP. This is a conjecture or hypothesis but it is not proven. The answer depends on the physics that underlies the universe. It is widely suspected (but not proven) that BPP = P. So, roughly speaking, the extended Church-Turing hypothesis amounts to saying that no physically realizable machine can give you more than a polynomial speedup.

We already know that the ECT is most likely not quite right, as we already believe that quantum physics is correct, not Newtonian physics. As a result, many expect that quantum computing is likely to disprove the ECT. But one can correct for this by conjecturing that Phys-P = BQP. As far as know, that conjecture could well be correct.

There are various exotic possibilities in which this hypothesis might be wrong. My favorite example is that, if time travel is possible, then we can compute anything in PSPACE in polynomial time. See Scott Aaronson's lecture notes or his earlier explanation. Alternatively, from a different perspective, if we live in a closed universe, then there is some constant upper bound on the maximum number of bits that can be stored in the universe ($10^{80}$ or something; the holographic bound), which implies that computation could be simulated by a finite-state machine -- not a very helpful point of view, and somewhat pedantic and nitpicky.

I suspect you might be interested in https://en.wikipedia.org/wiki/DNA\_computing, even though it doesn't change the complexity class of what we can compute, and you might be interested in Scott Aaronson's comments on analog classical computers at https://scottaaronson.blog/?p=5517.

---
Tags: complexity-theory, np-hard, computation-models, polynomial-time, physics
---


# Question
Title: approximation ratio of TSP problem where the weights are bounded by an inequality
Consider a variant of the TSP problem where the cost function $c$ is not only symmetric but also satisfies $c(u, v) ≤ 2c(u, w) + c(w, v)$ for arbitrary vertices $u, v, w ∈ V$ . Give a polynomial time algorithm that achieves a constant factor approximation ratio for this problem.

I think the algorithm itself is the same as the one with the triangle inequality where we find an MST, but I'm not sure about what the approximation ratio would be for this problem?

# Answer
> 1 votes
Summary: Start with a minimum spanning Tree (MST). Then modify it slightly to a Hamiltonian circuit.

#### Mini-step traversal of $(T,s)$

Let $T$ be a tree.

**Definitions**: For two vertices $u$ and $v$, let $d(u,v)$ be the number of edges in the unique path from $u$ to $v$.
A sequence $v\_1, v\_2, \cdots, v\_n$ is called a **mini-step traversal** of $(T, s)$ if

* it is a permutation of all vertices in $V$, and
* $v\_1=s$, and
* $d(v\_i, v\_{i+1})\le 3$ for all $i$ such that $1\le i\lt n$, and
* $d(v\_n, v\_1)= 1$ if $n\gt1$, and
* if we walk from $v\_1$ to $v\_2$, then to $v\_3$, and so on to $v\_n$, and back to $v\_1$, always along the unique path between the vertices, then we will walk over any edge of $T$ at most $2$ times.

**Claim**. Let $s\in V$. There is a mini-step traversal of $(T, s)$.
**Proof**: Use induction on $n = |V|$.
The base case, when $n=1$ is trivial.
Consider the case of $n\ge2$. As induction hypothesis, assume the claim is true for smaller $n$.
Let $u\_1, \cdots, u\_k$ be the neighborhood of $v$. If we remove $s$ from $T$, $T$ will be split into $k$ trees, which will be denoted by $T\_1, \cdots, T\_k$, where $T\_i$ is the tree that contains $u\_i$.
Thanks to induction hypothesis, let $v\_{1,i}, v\_{2,i}, \cdots, v\_{n\_i, i}$ be a mini-step traversal of $(T\_i, u\_i)$. Then we can verify that $s, v\_{1,1}, v\_{2,1}, \cdots, v\_{n\_1, 1}, v\_{1,2}, v\_{2,2}, \cdots, v\_{n\_2, 2},\cdots, v\_{1,k}, v\_{2,k}, \cdots, v\_{n\_k, k}$ is a mini-step traversal of $(T,s)$. $\quad\checkmark$

Note that the proof provides an $O(n^2)$-time algorithm to construct a mini-step traversal of $(T,s)$, given tree $T$ with $n$ vertices and vertex $s$.

#### A polynomial-time algorithm

Input: A complete graph $G$ and a symmetric cost function $c$ that satisfies $0\le c(u,v)\le2c(u,w)+c(w,v)$
Output: a Hamiltonian circuit of $G$
Procedure:

1. Obtain an MST of $G$, which is denoted by $M$.
2. Let $s$ be a vertex in $M$. Obtain a mini-step traversal of $(M,s)$.
3. Return that traversal as a Hamiltonian circuit, denoted by $\mathcal C$.

#### Approximation ratio $\frac72$

**Claim**: $c(\mathcal C)\le\frac72\\,min\\\_cost$, where $min\\\_cost$ is the minimum cost of a Hamiltonian circuit of $G$.
**Proof**: Since $c(M)\le min\\\_cost$, it is enough to prove $c(\mathcal C)\le\frac72c(M)$.
Suppose $C=(v\_1, v\_2, \cdots, v\_n, v\_{n+1}=v\_1)$. $$\begin{aligned} c(\mathcal C) &=\sum\_{1\le i\le n}c(v\_i, v\_{i+1})\\ &\le\sum\_{1\le i\le n}\left(\frac74\sum\_{e\in {\text{the unique path in }M\text{ from }v\_i\text{ to }v\_{i+1}}}c(e)\right)\\ &=\frac74\sum\_{1\le i\le n}\ \sum\_{e\in {\text{the unique path in }M\text{ from }v\_i\text{ to }v\_{i+1}}}c(e)\\ &\le\frac74\sum\_{e\in M}2c(e)\\ &=\frac72c(M) \end{aligned}$$ where the last inequality is the last property of a mini-step traversal, while the first inequality comes from the inequalities below since $d(v\_i, v\_{i+1})\le3$ with respect to $M$.

* for any vertex $u,v,w$, we have $c(u, v) \le\frac32(c(u, w) + c(w, v))$
Proof: $c(u, v) \le 2c(u, w) + c(w, v)$. Switching $u$ and $v$, we also have $c(v, u) \le 2c(v, w) + c(w, u)$. Note that $c(v, u)=c(u,v)$, $c(v, w)=c(w,v)$, $c(w,u)=c(u,w)$. Adding both inequalities, we are done.
* for any vertex $u,v,w,x$, we have $c(u, v) \le\frac74(c(u, w) + c(w, x) + c(x,v))$
Proof: $c(u, v)\le 2c(u,w) + c(w,v)\le2c(u,w) + \frac32(c(w,x)+c(x,v))$. Similarly, $c(u, v)\le\frac32(c(u,w)+c(w,x)) + 2c(x,v)$. Add both inequalities.

---
Tags: approximation, traveling-salesman
---


# Question
Title: Are all np-complete problems also np-hard?
Are all np-complete problems also np-hard?

In other words, is np-complete a subset of np-hard?

I don't think it is entirely clear from the illsutration below, so I just wanted to quickly ask to ask to be completely sure. The np-hard area also includes the np-complete section right?

Just a quick "yes" or "no" is all I am looking for :)

# Answer
> 1 votes
A problem is said to be NP-complete if it is in both NP and NP-hard, so yes all NP-complete problems are also NP-hard.

# Answer
> -1 votes
No (unless you find a proof for it that will make you world famous as a mathematician and computer scientist). NP-complete problems are in NP and can be used to solve any problem in NP. NP-hard problems can be used to solve any problem in NP but need not be in NP.

NP-complete equals NP-hard plus NP.

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


# Question
Title: Given a permutation of n integers, how fast can a corresponding Standard Young's Tableau be created?
The Schensted insertion algorithm has an $O(n^2)$ running time, for constructing such a standard Young's Tableaux.

But, since every permutation has a unique Young's tableau, there seems no reason as to why it cannot be done in $O(n \log n)$ time, which is the optimal time to identify a permutation.

Are there any known non-trivial $\textbf{lower bounds or upper bounds}$ for this?

Any assistance/guidance towards any of the questions is much appreciated. Thanks in advance

Sample input permutation

5,7,2,3,4,1,6

Output Young's Tableaux

1,3,4,6
2,7
5

# Answer
I believe that no faster algorithm is known, at least if you are interested in computing both tableaux. Dan Romik shows in his paper The Number of Steps in the Robinson-Schensted Algorithm that on almost all permutations, the computational complexity is actually only $\Theta(n^{3/2} \log n)$. Duzhin, Kuzmin and Vasilliev show in their work RSK bumping trees and a fast RSK algorithm how to speed up the algorithm in practice by a significant constant factor. This is all I could find on the topic.
> 2 votes

---
Tags: algorithms, data-structures, combinatorics, word-combinatorics
---


# Question
Title: Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book
I'm reading the DFS section of CLRS-*Introduction to Algorithms*, and confuse on the $\Leftarrow$ direction of the proof of the white-path theorem of DFS algorithm in this book.
Note that each node u in the graph has 2 **timestamps**: $u.d$ records when u is discovered and $u.f$ records when the search ﬁnishes examining u’s adjacency list .
Dependencies:

> **Theorem 22.7 (Parenthesis theorem)**
> In any depth-ﬁrst search of a (directed or undirected) graph $G = (V, E)$, for any two vertices u and v, exactly one of the following three conditions holds:
>
> * the intervals $\[u.d, u.f\]$ and $\[v.d, v.f\]$ are entirely disjoint, and neither u nor v is a descendant of the other in the depth-ﬁrst forest,
> * the interval $\[u.d, u.f\]$ is contained entirely within the interval $\[v.d, v.f\]$, and u is a descendant of v in a depth-ﬁrst tree, or
> * the interval $\[v.d, v.f\]$ is contained entirely within the interval $\[u.d, u.f\]$, and v is a descendant of u in a depth-ﬁrst tree.

> **Corollary 22.8 (Nesting of descendants’ intervals)**
> Vertex v is a proper descendant of vertex u in the depth-ﬁrst forest for a (directed or undirected) graph G if and only if $u.d \< v.d \< v.f \< u.f$.

Proof of theorem 22.9:

> **Theorem 22.9 (White-path theorem)**
> In a depth-ﬁrst forest of a (directed or undirected) graph $G = (V, E)$, vertex v is a descendant of vertex u if and only if at the time $u.d$ that the search discovers u, there is a path from u to v consisting entirely of white vertices.
>
> **Proof** $\Rightarrow$: If $v = u$, then the path from u to v contains just vertex u, which is still white when we set the value of $u.d$. Now, suppose that v is a proper descendant of u in the depth-ﬁrst forest. By Corollary 22.8, $u.d \< v.d$, and so v is white at time $u.d$. Since v can be any descendant of u, all vertices on the unique simple path from u to in the depth-ﬁrst forest are white at time $u.d$.
>
> $\Leftarrow$ Suppose that there is a path of white vertices from u to v at time $u.d$, but v does not become a descendant of u in the depth-ﬁrst tree. Without loss of generality, assume that every vertex other than v along the path becomes a descendant of u.(Otherwise, let v be the closest vertex to u along the path that doesn’t become a descendant of u.) **Let $w$ be the predecessor of v in the path, so that $w$ is a descendant of u (w and u may in fact be the same vertex)**. By Corollary 22.8, $w.f \leq u.f$ . Because v must be discovered after u is discovered, but before w is ﬁnished, we have $u.d \< v.d \< w.f \leq u.f$ . Theorem 22.7 then implies that the interval $\[v.d, v.f\]$ is contained entirely within the interval $\[u.d, u.f\]$. By Corollary 22.8, v must after all be a descendant of u.

In the proof, they **let $w$ be the predecessor of v in the path**. How do we know that such a $w$ exists? And if such $w$ exists, whether or not theorem 22.7 and corollary 22.8 are unnecessary, because i think if $w$ is predecessor of v, so that v is descendant of w, which directly implies that v is descendant of u?

# Answer
I'm not sure what the problem is, but I will still try to answer.

The predecessor of $v$ in a path from $u$ to $v$ is the last vertex seen before $v$.

Since there exists a path from $u$ to $v$ then, unless $v = u$, $v$ has necessarily a predecessor.

More formally, if $(u\_0, u\_1, …, u\_k)$ is a path of length $k$ from $u = u\_0$ to $v = u\_k$, then the predecessor of $v$ is $u\_{k-1}$. It exists unless $u = v$.
> 2 votes

---
Tags: algorithms, graphs, depth-first-search
---


# Question
Title: Turing Machine writes "a" for every input w is undecidable
I have a doubt on my solution of the following: Formalize the language of a Turing machine that takes a Turing machine "M" and a character "a" as input, the language recognizes all and only the Turing machines that write "a" on the tape for every possible input w prove that this language is undecidable.

Formalization: A={\<M, a\> | M is a Turing machine and M writes a for every input string w}

Proof of undecidability: Assume that A is decidable and H is it's decider, we can prove that there must exist a decider for ATM reaching a contraddiction.

On input \<M, w\>:

1. Build a Turing machine N as will follow
2. Run H on input \<N, a\>
3. Return the output

N=On input x:

1. Run M on w
2. If M accepts, write "a" on the tape and accept
3. If M rejects, write "a" on the tape and reject
4. If M loops, write "a" on the tape and reject

Is this correct? I am not sure if the construction of N is ok specifically in the point 4.

# Answer
> 2 votes
Your suspicion is well-founded. The point 4 is invalid.

Imagine the exact moment N "writes 'a' on the tape and reject" in the point 4. That means at that moment, it is known that M loops. However, all the algorithm has done is running M on w for some steps without acceptance nor rejection. It is possible that if we run M one step more, it will halt to accept or reject. So, it cannot be certain that M loops.

In fact, had point 4 been valid, we would have solved the halting problem by the simple Turing machine below.

On input \<M, w\>:

1. Run M on w
2. If M accepts or rejects, accept
3. If M loops, reject

---

Here is a proof of undecidability of A.

Assume that A is decidable and H is it's decider, the following will be a specification of a decider for ATM, which is known to be impossible, however.

On input \<M, w\>:

1. Build a Turing machine N as below.
2. Run H on input \<N, a\>
3. Return the output

N=On input x:

1. Run M on w
2. If M accepts, write "a" on the tape and accept
3. If M rejects, reject.

---

The section above interprets "M writes a" in the definition of A as "M writes 'a' and accept, leaving all other cells blank.". i.e., M returns "a".

Another interpretation of "M writes a" is that "M will write 'a' at least once during its execution". Then the construction of N will be more complex.

---
Tags: turing-machines, undecidability
---


# Question
Title: Sampling unique records from a large dataframe
Suppose we have a dataframe with ~10M rows with ~9M duplicate records. What is the most time efficient way of selecting the unique records from this dataframe?

Some sort of sampling algorithm?

# Answer
> 2 votes
A reasonable approach would be to build a hashtable that stores all unique records. Scan through the records one at a time, adding each to the hashtable if it is not already present; if it already is in the hashtable, do nothing, and if it is not already in the hashtable, add it to the hashtable and output it.

Another approach would be to sort the records (which will make all duplicates adjacent), then remove duplicates, then return to the original order if needed. This has the benefit that it can scale to even larger databases: if the entire dataset cannot be stored in memory, it is possible to use an external sort and still be efficient. In contrast, a hash table will work great if everything fits in memory, but will be very slow if the database does not fit in memory.

---
Tags: algorithms, time-complexity, sorting, hash
---


# Question
Title: Choosing a subset to maximize the minimum distance between points
I have a set of points $C$, and I have the distance between each point $D(P\_i,P\_j)$. These distances are euclidean but the points are actually in a feature space.

From the $C$ points I want to choose a subset of $n$ points. Call this subset $s$. I want to choose this subset so as to maximize the minimum distance between all the points in the new set $s$.

$$ \max\_{\substack{s \subset C \\ |s| = n}} \left( \min\_{\substack{i,j \in s \\ i \neq j} } D \left( P\_i, P\_j \right) \right) $$

Right now I am using hill climbing to solve this problem. I understand that simulated annealing may give a better solution.

Is there a known solution to this type of problem? Or can this problem be reformulated into another problem that is easily solved?

# Answer
> 10 votes
The decision problem version of this optimization problem is:

> Given a threshold $t$, you want to know whether it is possible to find a subset of $n$ points such that every pair of points in the subset are at least $t$ units apart.

Of course, if you can solve the decision problem, we can solve your optimization problem (by binary search on the threshold $t$).

Now this decision problem is the problem of finding an independent set in a Euclidean graph, where points $x,y$ have an edge between them if they are at distance $\le t$ apart. One approach would be to look at standard approximation algorithms for independent set.

Even better, you can look at algorithms for independent set in geometric intersection graphs. Consider a set of disks, where each disk has diameter $t$ and is centered at one of the points in your set $C$. Now we can form a geometric intersection graph, where there is one vertex for each disk and an edge between two vertices if their corresponding discs intersect. The problem of finding an independent set in this sort of graph has been studied and there are approximation algorithms for this problem that you could try using.

If you want the exact optimum rather than an approximation, you could use any of the standard "big hammers", such as a SAT solver or an ILP solver. There is a straightforward way to formulate the independent set problem as a SAT instance, and then you could apply a SAT solver to it to find whether there exists a subset of $n$ points which are all $\ge t$ units away from each other.

# Answer
> 3 votes
This problem is known as the MaxMin Diversity Problem (MMDP). It is known to be NP-hard. However, there are algorithms for giving good approximate solutions in reasonable time, such as this one.

I'm answering this question years after it was asked because I was looking for algorithms to solve the same problem, and had trouble even finding out what to call it.

---
Tags: optimization
---


# Question
Title: Complexity of the partition problem with additional constraint
The "classical" partition problem asks whether a given multiset $S$ of positive integers can be partitioned into two subsets $S\_1$ and $S\_2$ such that the sum of the numbers in $S\_1$ equals the sum of the numbers in $S\_2$. The problem is known to be NP-hard.

I want to know if a similar problem is also NP-hard (I believe so, but can't proof it).

Given a set $S$ which consist of **pairs** of positiv integers (e.g. $S=\\{\\{2,7\\},\\{3,9\\},\\{4,5\\},\\{6,8\\}\\}$). Can $S$ be partitioned into two subsets $S\_1$ and $S\_2$ such that the sum of the numbers in $S\_1$ equals $S\_2$ **and** no two numbers from $S\_1$ belong to the same pair from $S$ (which means that if one number from a pair is choosen to be in $S\_1$ the other one must be in $S\_2$).

For example a valid solution to the set $S$ from above would be $S\_1=\\{2,9,5,6\\}$ and $S\_2=\\{7,3,4,8\\}$. Here each sum is equal to $22$ and from each pair of numbers from $S$ exactly one number can be found in $S\_1$ (or equally in $S\_2$).

# Answer
As you mentioned the first problem can be reduced to the second one by replacing each positive integer $a\_i\in S$ by a paired $(a\_i,0)$. Moreover, the second problem can be reduced to the first one by replacing each paired $(a\_i,b\_i)\in S$ by a pisitive integer $c\_i=|a\_i-b\_i|$ and after partitioning (suppose that $a\_i\ge b\_i$), if $c\_i$ is in $s\_1$ then let $a\_i\in s\_1$ and $b\_i\in s\_2$.
> 2 votes

---
Tags: optimization, np-hard, partitions
---


title: find LR(1) items of the first state

text:
# Question
Title: find LR(1) items of the first state
I need to calculate the LR(1) items of the following grammar:

```
S -> E
E -> E + T
E -> T
T -> ID
T -> ( E )

```

I can not even calculate the first group {\[S -\> .E, $\]} correctly, I read and tried to run the algorithm and did not understand why the correct answer for state 0 should be the group of items:

```
{[S -> .E, $];
[E -> .E + T, $ / +];
[E -> .T, $ / +];
[T -> .ID, $ / +];
[T ->. (E), $ / +]}

```

I calculated I found that there are only 5 items in group 0:

```
{[S -> .E,$];
 [E -> .E + T,$];
 [E -> .T,$];
 [T -> .ID,$];
 [T ->. (E),$]}

```

someone can explain to me why there should be items with a "+", and where does it come from?

# Answer
$S\to.E$,\\$.........$(1)$, now compute the closure of $E$, which is $E\to.E+T,$\\$..........$(2)$ and $E\to.T,$\\$.........$(3)$ use lookahead \\$ because in $(1)$ after $E$ is \\$ and $FIRST$ of \\$ is \\$ that's why lookahead is \\$ in (2) and (3).

From $(2)$ you need to find the closure of $E$, which is $E\to.E+T,+$........$(4)$ and $E\to .T,+$.............$(5)$ use lookahead $+$ because in $(2)$ after $E$ is $+T,$\\$ and $FIRST$ of $+T,$\\$ is $+$ that's why lookahead is $+$ in $(4)$ and $(5).$

Now combining $(2)$ and $(4)$ we get $E\to.E+T,$\\$$/+$.

Similarly combining $(3)$ and $(5)$ we get
$E\to .T,$\\$$/+$.

Rest of the things left for you.
> 0 votes

---
Tags: automata, formal-grammars, compilers, syntax, lr-k
---


# Question
Title: What property of XOR makes this algorithm work?
I'm having trouble figuring out *why* using XOR for this problem works; I've done it a couple of times by-hand, and can't really seem to understand it. I know that XOR is commutative and associative, which is why it's good for finding (missing) duplicated numbers in a list. But applying that to the following problem doesn't quite click with me:

**In a non-empty array of numbers, every number appears exactly twice except two numbers that appear only once. Find the two numbers that appear only once.**

```
Input: [1, 4, 2, 1, 3, 5, 6, 2, 3, 5]
Output: [4, 6]

```

```
Input: [2, 1, 3, 2]
Output: [1, 3]

```

The algorithm to find the **two** single numbers is this in psuedocode:

```
list_xor = 0
for each num in nums:
    # XORing all the numbers in the list
    list_xor = list_xor XOR num

# find the first bit of list_xor, used for partitioning [nums]
right_most_bit_in_list_xor = find_right_most_bit(list_xor)

!!! I don't understand this part !!!
num1, num2 = (0, 0)
for each num in nums:
    # num has a bit that's set that matches right_most
    if (right_most_bit_in_list_xor & num) == 1:
        num1 = num1 XOR num
    # else, the num doesn't have this bit set
    else:
        num2 = num2 XOR num

return num1, num2

```

I can't figure out why XOR'ing the right-most bit in the result from XOR'ing the list with each number in the list will result in `num1` and `num2` being the only single numbers.

Here's a sample "by-hand" run that I did:

```
Input: [1, 1, 2, 3, 2, 4], Output: [3, 4]
list_xor =
(000^001) = 001 -> (001^001) = 000 -> (000^010) = 010
 -> (010^011) = 001 -> (001^010) = 011 -> (011^100) = 111 (7 in decimal)

Right-most bit of 7 = 001 (1 in decimal)

Numbers with 001 as a set bit: [1, 1, 3]
num1 = 000 -> (000^001) = 001 -> (001^001) = 000 -> (000^011) = 011 (3 in decimal)

Numbers with 001 NOT set as a bit: [2, 2, 4]
num2 = 000 -> (000^010) = 010 -> (010^010) = 000 -> (000^100) = 100 (4 in decimal)

```

From the run-through, you can see that they're partitioned into two lists with duplicates and a single, single number: \[1, 1, **3**\] and \[2, 2, **4**\]. But how did it partition itself just based on the right-most bit?

# Answer
> 5 votes
Let $x$ and $y$ be the numbers that appear only once and let $z\_1, \dots,z\_n$ be the other input numbers (each number appears twice). Then $x \oplus y \oplus z\_1 \oplus \dots \oplus z\_n = x \oplus y$ and, in particular, if the generic $i$-th bit in $x \oplus y$ is $1$ then exactly one between $x$ and $y$ has the $i$-th bit set to $1$.

Pick any $i$ such that the $i$-th bit of $x \oplus y$ is $1$ (in your code this is the rightmost bit, but any such bit works) and suppose without loss of generality that the $i$-th bit of $x$ is $1$ (and hence the $i$-th bit of $y$ is $0$).

Let $Z^+$ (resp. $Z^-$) the (multi-)set containing the numbers $z\_1, \dots, z\_n$ that have their $i$-th bit set to $1$ (resp. $0$). Since there are exactly two copies of each number in $Z^+$ (resp. $Z^-)$, we have: $$ x \oplus \left(\bigoplus\_{z \in Z^+} z\right) = x \oplus 0 =x, $$ where the left-hand term is exactly how your algorithm computes `num1`. Similarly, $$ y \oplus \left(\bigoplus\_{z \in Z^-} z\right) = y \oplus 0 = y, $$ which corresponds to `num2`.

---
Tags: algorithms, bit-manipulation, xor
---


# Question
Title: Efficiently find longest common substring for all substring pairs of S and T
I am trying to find the Gesalt similarity of a string $S$ and all substrings of $T$ using Gestalt Pattern Matching (Ratcliff Obershelp Algorithm)

This algorithm requires me to find the matches of S and T which is defined as follows

$$ matches(S,T) = \begin{cases} matches(S1,T1) + \[LCS(S,T)\] + matches(S1,T2)&\text{if } LCS(S,T) \neq \epsilon\\ \[\] &\text{if } LCS(S,T) = \epsilon\\ \end{cases} $$ where

$LCS(S,T)$ is the longest common substring of $S$ and $T$

$S = S1 + LCS(S,T) + S2$

and

$T = T1 + LCS(S,T) + T2$

Informally, matches are calculated by finding $LCS(S,T)$ and then by recursively finding matches on the left and right of $LCS(S,T)$

The similairty ratio is defined as $$ sim(S,T) = \begin{cases} \frac{2 * K}{length(S) + length(T)}&\text{if }length(S) + length(T) \neq 0\\ 1 &\text{otherwise} \end{cases} $$

where $K$ is the sum of the length of all matches

Example

$S$ = "Altanta" $T$ = "Atlantis"

$$ \begin{equation\*} \begin{split} matches(S,T) &= matches(\text{'Alt', 'Atl'}) + \[\text{'ant'}\] + matches(\text{'a', 'is'}) \\ &= matches(\text{'Alt', 'Atl'}) + \[\text{'ant'}\] + \[\] \\ &= matches(\text{'Alt', 'Atl'}) + \[\text{'ant'}\] \\ &= (matches(\epsilon, \epsilon) + \[\text{'A'}\] + matches(\text{'lt', 'tl'})) + \[\text{'ant'}\] \\ &= \[\] + \[\text{'A'}\] + matches(\text{'lt', 'tl'})) + \[\text{'ant'}\] \\ &= \[\text{'A'}\] + matches(\text{'lt', 'tl'})) + \[\text{'ant'}\] \\ &= \[\text{'A'}\] + (matches(\epsilon,\text{'t'}) + \[\text{'l'}\] +matches(\text{'t'},\epsilon)) + \[\text{'ant'}\] \\ &= \[\text{'A'}\] + \[\] + \[\text{'l'}\] + \[\] + \[\text{'ant'}\] \\ &= \[\text{'A'}, \text{'l'} ,\text{'ant'}\] \\ \end{split} \end{equation\*} $$

Thus $K= length(\text{'A'}) + length(\text{'l'}) + length(\text{'ant'}) = 5$

Hence,

$$ sim(S,T) = \frac{2\*K}{length(S) + length(T)} = \frac{2 * 5}{7 + 8} = 0.666... $$

Now, I want to be able to find the similarity for $S$ and all substrings of $T$

Eg. $sim(\text{'Altanta'}, \text{'Alta'})$, $sim(\text{'Altanta'}, \text{'lantis'})$, e.t.c.

But to calculate these pairs efficiently I believe that I'll need to be able to quickly find the matches of $S$ and substrings of $T$, which in turn means that I'll need to be able to find $LCS(S',T')$ for all $S'$ and $T'$ where $S$' is substring of $S$ and $T'$ is a substring of $T$.

How can I efficiently find $LCS(S',T')$ for all $S'$ and $T'$ where $S$' is a substring of $S$ and $T'$ is a substring of $T$?

I went through Dynamic and Internal Longest Common substring which looked promising at first but only explained algorithms for constrainted cases.

# Answer
> 2 votes
I'll throw a naive algorithm out there.

One way would be to create a hash set of all possible substrings from your first input. Then check if each possible substring from the second input is in that hash set.

Time complexity: $O(N\_1^2 + N\_2^2)$

Memory usage: $O(min(N\_1^2, N\_2^2))$ (use shortest input as first input)

You can all so break the problem down in common substrings of length 1, then length 2, then length 3, etc. While clearing and reusing the hash set between each length change. That will help lower the memory usage.

---
Tags: substrings, longest-common-substring
---


# Question
Title: Is the complexity of this two-sum binary search algorithm $O(\lg n)$ or $O((\lg n)^2)$?
This algorithm solves the Two-Sum problem$^1$ assuming that the input array/list is sorted.

```
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        N = len(nums)
        l, r = 0, N-1
        while l < r:
            comp = target - nums[l]
            r = bisect_left(nums, comp, lo=l+1, hi=r+1)
            # (r == 0 or nums[r-1] <  comp) and (r == N or nums[r] >= comp)
            # but actually r != 0 since lo = l+1 <= r < hi = r+1 meaning 0 <= l < r meaning  0 < r
            # so actually, we have
            # nums[r-1] <  comp and (r == N or nums[r] >= comp)
            if r < N and nums[r] == comp:
                return l+1, r+1 # +1 to convert 0-indexed indices to 1-indexed indices
            # r == N or nums[r] > comp
            # r == N or nums[r] > target - nums[l]
            # r == N or nums[l] + nums[r] > target so do r -= 1
            # nums[r-1] < comp
            # nums[r-1] < target - nums[l]
            # nums[l] + nums[r-1] < target so do l += 1
            r -= 1
            l += 1
        return None

```

Simplified algorithm and without the comments:

```
 1 class Solution:
 2     def twoSum(self, nums: List[int], target: int) -> List[int]:
 3         N = len(nums)
 4         l, r = 0, N-1
 5         while l < r:
 6             comp = target - nums[l]
 7             r = bisect_left(nums, comp, lo=l+1, hi=r)
 8             # INVARIANT: 0 <= l < r < N
 9             if nums[r] == comp:
10                 return l+1, r+1
11             l += 1
12         return None

```
* `bisect_left`, Python's binary search algo, is $O(\lg n)$, and
* I believe the `while l < r` loop runs on the order of $\lg n$ times,

so does the algorithm have an overall time-complexity of $O((\lg n)^2)$?

$^1$: Given a list of numbers and a target value, determine if there are two numbers that add up to the target value.

# Answer
> 2 votes
Unfortunately, the worst case of this algorithm is $\Theta(n\lg n)$, which is worse than $O(n)$, the time-complexity of the usual two-pointer algorithm that solves the same problem.

---

Consider the case with `nums = list(range(n))` and `target = 3*n//2`, where `n` is an even number.

At the start of each iteration of the `while` loop, `r == n - 1`, since line 7 will set `r` to `n` and line 10 will set `r` back to `n-1`.

Since `l` goes from `0` initially to `n//2` at the end, increasing by `1` in each iteration, there are `n//2` iterations. Each iteration takes $\Theta(\lg n)$ time because of `bisect_left` at line 7. The time-complexity of this case is $\Theta(n\lg n)$.

# Answer
> 3 votes
Making the same assumption as John's accepted answer, that the numbers aren't limited like on LeetCode, we can answer your question with "no" even without looking at your code. Because those complexities are impossible. You can't do better than O(n).

Consider the n even numbers 2, 4, 6, 8, ..., 2n. The sum of smallest and largest is 2n+2. As is the sum of second-smallest and second-largest, and so on. There are n/2 pairs with sum 2n+2. Now I increase one of the numbers by 1. Which creates one pair with sum 2n+3. And I make the target 2n+3. Since the increased number is the only odd number, you need it for that target. So you have to find that one number. And looking at some other number doesn't tell you any more than that that's not the one. In whatever order you look at the numbers to find the one, you might get unlucky. My number might be the last number you look at. So you can't do better than O(n).

Another way to put it:

Think of it as a game. I tell you I have n sorted numbers built as described above. Now your task is to find that odd number. You can ask me for indexes and I'll tell you their numbers. You can do whatever you want with them. Compare, add, write a song about them, ask others for help, whatever. Until you asked for n-1 numbers, you won't know where the odd one is. Why? Because I'll cheat. For whatever n-1 numbers you ask first, I'll tell you the even number. And at the end, I'll claim that the last number is the one I increased at the start of the game. Or was I really cheating? Maybe I really did increase that particular one at the start. Cheating and not cheating, those two cases are indistinguishable to you. So I don't need to have cheated for you to need to ask for n-1 numbers.

And just in case the connection from my special case of numbers to the question's arbitrary n sorted numbers isn't clear: My special case is one possible case. We could play the same game and I would act in the exact same way, but *you* would only know that my numbers are sorted. The difference in the game as discussed above is just that I grant you a head start. I give you additional information. And despite that, you *still* have to ask for n-1 numbers.

---
Tags: algorithms, time-complexity, runtime-analysis, python
---


# Question
Title: prove that context free languages are closed under the $\circ$ operation
> Prove that if $C$ and $D$ are context-free languages, then so is $C\circ D := \cup\_{n\ge 0} C^n D C^n $.

I know that $\\{0^n 1 0^n : n\ge 0\\}$ is context free, being the intersection of $L(0^\* 10^\*)$ and $L(G)$, where $G$ is the context free grammar with start symbol S given by $S\mapsto S1 S | 0S | \epsilon$. Also, I know basic properties like the fact that context free languages are closed under taking prefixes, union, and concatenation. The issue with applying this technique to the given problem is that $C^\* B C^\*$ may not be regular. How can I circumvent this issue to solve the given question?

# Answer
As you state the language $\\{0^n 1 0^n\mid n\ge 0\\}$ is context-free. (You do not need closure properties for this: $S\to 0S0\mid 1$ will do.)

Now continue as follows. Consider instead the language $\\{X^n Y X^n\mid n\ge 0\\}$, where $X,Y$ are the axioms of context-free grammars for $C$ and $D$.
> 0 votes

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


# Question
Title: The optimal complexity of intersecting a line with a convex hull of a set of points in 2d
**The problem:** in 2d, given a line and an unordered set of $N$ points with real coordinates, find the intersection between the line and the convex hull of the points.

Clearly, one can explicitly construct the convex hull and find the answer in $O(N \log N)$. Is there a faster approach? Is there a superlinear lower bound on the complexity?

# Answer
What you're asking for reduces to finding the so-called bridges of the convex hull across this line, i.e. the two edges of the convex hull which have one vertex on both sides of the line. Kirkpatrick and Seidel \[1\] show how to do this in linear time. Their method amounts to using the two dimensional linear programming algorithms independently discovered by Megiddo \[2\] and Dyer \[3\].

You can generalize this to any (constant) dimension. Let me illustrate it in 3D. We are given a set of $n$ points $S$ in euclidean $3$-space, a line $\ell$ and we want to compute the intersection of $\ell$ with the convex hull of $S$.

Without loss of generality, we can rotate everything and assume that $\ell$ is the line of equation $x=y=0$. We want to find the highest and lowest point (in terms of $z$ coordinate) of $\ell$ which is in the convex hull. To find the highest point, notice that this is the lowest point which is the intersection of $\ell$ with a plane $\pi$ which has all point of $S$ below or on it. Say the equation of $\pi$ is $z = ax +by + c$. The $z$-coordinate of the intersection of $\ell$ with $\pi$ is $c$. We thus want to minimize $c$ under the constraints that $z\_i \leq ax\_i +by\_i + c$ for all $(x\_i,y\_i,z\_i)\in S$. This can be modelled as a linear program in three variables ($a$,$b$ and $c$) and $n$ constraints. Using the linear time algorithm by Megiddo \[4\] it can be solved in $O(n)$ time if the number of variables is constant. Of course you can compute the lowest point of intersection similarly.

\[1\] David G. Kirkpatrick and Raimund Seidel. 1986. The ultimate planar convex hull algorithm? SIAM J. Comput. 15 (1986).

\[2\] Nimrod Megiddo, Linear time algorithm for linear programming in R3 and related problems, SIAM J. Comput. 12 (1983).

\[3\] Martin E. Dyer, Linear time algorithms for two- and three-variable linear programs, SIAM J. Comp. 13 (1984).

\[4\] Nimrod Megiddo, Linear programming in linear time when the dimension is fixed. J. ACM 31 (1984).
> 4 votes

# Answer
~~I think it can be done in O(N).~~

WLOG, we assume the line is $x=0$, and the intersection set is non empty. We can rotate the point set if the line is not $x=0$. The intersection check can be done in O(n) so we can make such assumption.

So we are going to find two point $(0,a)$ and $(0,b)$, such that $a$ is the maximum number and (0,a) is a point in the convex hull, and b is the minimum number.

Obviously, (0,a) must be on an edge of the convex hull.

Say the input point set is $S=\\{ (x\_1,y\_1), \cdots, (x\_n,y\_n) \\}$

We can get $S\_1$ and $S\_2$ in O(N) time.

$S\_1 = \\{ (x,y) | x\leq 0\\} \cap S$ $S\_2 = \\{ (x,y) | x \>0 \\} \cap S$

if $S\_2$ is empty then the intersection is an edge of the convex hull, we can get the intersection in O(N) time easily.

Otherwise. $(0,a)$ must be a point on the segment between a point $A\in S\_1$ and a point $B\in S\_2$

~~We can find the "highest" point in $S\_1$ and $S\_2$: the points with maximum y-coordinate. Let's say they are $P\_1=(xx\_1,yy\_1)$ and $P\_2=(xx\_2,yy\_2)$~~

~~If $yy\_1 = yy\_2$, then $(0,a)$ must be on the segment $P\_1P\_2$, i.e. $a = yy\_1=yy\_2$~~

~~Otherwise, we can assume $yy\_1\<yy\_2$. then $(0,a)$ must be on the segment between $P\_1$ and one point in $S\_2$~~

~~We can enumerate the points in $S\_2$, say $Q\_i$, and get the intersection of $x=0$ and $P\_1Q\_i$. Then $(a,0)$ must be the highest point among the intersection points.~~

~~$(b,0)$ can be get in the same way. so intersecting a line with a convex hull of a set of points in 2d can be done in O(N).~~

This approach is wrong.
> 0 votes

---
Tags: complexity-theory, time-complexity, computational-geometry, convex-hull
---


# Question
Title: If every NP-hard language is PSPACE-hard then NP=PSPACE
To prove PSAPCE = NP we will show following inclusions :

* NP $\subseteq$ PSPACE : If every NP-hard language is PSPACE-hard then SAT is also PSPACE-hard. Since every language in PSPACE can be reduced polynomially to PSPACE-hard implies SAT $\in$ PSPACE.

SAT $\in$ PSPACE.
If L $\leq\_{P}$ B and B $\in$ PSPACE $\implies$ L $\in$ PSPACE.
* PSPACE $\subseteq$ NP : If every NP-hard language is PSPACE-hard, we can then say SAT is PSPACE-hard, now since SAT $\in$ NP $\implies \forall L \in$ PSPACE $\leq\_{P}$ SAT $\implies$ PSPACE $\subseteq$ NP. $\square$\

---

I am unsure about the second item of proof. The confusion is about where I am saying SAT is in PSPACE-hard and also in NP and using that to prove the inclusion. Is the logic correct? If yes, Is there a clearer way to write it?

# Answer
> 2 votes
"SAT is PSPACE-hard. Since SAT $\in$ NP $\implies \forall L \in$ PSPACE $\leq\_{P}$ SAT $\implies$ PSPACE $\subseteq$ NP" is indeed confusing.

What is much clearer is "SAT is PSPACE-HARD $\implies (\forall L \in$ PSPACE, $L\leq\_{P}$ SAT) $\implies$ ($\forall L \in$ PSPACE, $L$ is in NP) $\implies$ (PSPACE $\subseteq$ NP)".

* The first implication is according to the definition of PSPACE-HARD.
* The second implication holds since NP is closed under polynomial-time many-one reduction and SAT is in NP.
* The third implication is a tautology.

---

"NP $\subseteq$ PSPACE" is true, even if "every NP-hard language is PSPACE-hard" is not true. It can be proved directly. Or you can use that fact directly assuming you have learned/been taught it.

Well, the way in which it is proved in the question does not make much sense, especially the implication in this statement, "SAT is also PSPACE-hard. Since every language in PSPACE can be reduced polynomially to PSPACE-hard implies SAT $\in$ PSPACE." The fact that "SAT is PSPACE-hard" should not be helpful in proving "SAT $\in$ PSPACE".

---
Tags: reductions, np-hard, np, space-complexity, polynomial-time-reductions
---


# Question
Title: Possible PDA for $ L = \{ a^{3n}b^{2n} | n \ge 0 \}$ without transforming CFG to PDA
To those of you who saw my post from an hour ago - I deleted it because I came up with an idea.

To summarize, I have to design a PDA for this language, without using the usual method of firstly defining a CFG then transforming it to a PDA.

$ L = \\{ a^{3n}b^{2n} | n \ge 0 \\}$

Here is my proposed solution:

Since I didn't know how to implement non-determinism, I **limited the number of "a"'s on the stack to the number of b's to be read**. Then I just pop the $a$s from the stack.

My question is, is this a valid PDA for this language? If not, can anyone give a few examples of strings that are either wrongfully discarded or wrongfully admitted by the PDA, and a possible solution or hint?

Thanks!

# Answer
> 2 votes
Your language is DCFL. But you made NPDA because in state $q\_5$ the transitions $(q\_5,\epsilon,a)\neq\emptyset$ and $(q\_5,\epsilon,A)\neq\emptyset$ made your diagram NPDA as I previously said. Below the image is DPDA:

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


# Question
Title: Buddy system allocator and slab allocator in Linux kernel
In the Silberschatz's book "operating systems" the author talks about the allocation of memory via **system buddy** and **slab**. My first question is: in the book, both memory allocation methods are described as allocation method that the kernel use to allocate memory *only* for kernel's process, not for user's process. Is it true?

My second question, as the title suggest, regards the allocation method that is implemented inside the Linux kernel. Looking the website kernel.org I've seen that there is a chapter dedicated to buddy system and a page dedicated to slab. So, I imagine that both are present inside the kernel, but what is one method for and what is the other for?

# Answer
> 4 votes
A modern operating system manages physical memory as page frames. A page frame can be allocated to a user process or for the kernel to use for its own purposes, such as to allocate its own data structures.

A kernel data object (e.g. a structure representing an "open file" or something) is typically less than the size of a page. So it makes sense to have a two-level allocation hierarchy: one to manage page frames, and one to allocate data structures inside allocated page frames.

Linux uses a buddy allocator to allocate page frames, and a slab allocator to allocate kernel data structures. When the slab allocator needs more memory, it obtains it from the buddy allocator.

This approach works well for Linux, since it supports different page sizes; x86-64 CPUs support 4kB, 2M, and sometimes 2GB pages, and a binary buddy allocator can support this with very little modification.

Windows NT, by comparison, uses a simple free list to implement page frame allocation. Actually, that's not quite accurate; it uses multiple free lists to implement cache colouring, but that's a story for another time. Again, it layers another allocator on top to handle kernel data structures.

It's a similar story with Mach, the microkernel underneath macOS and iOS. Kernel data structures are implemented with a zone allocator, which plays the same role as the slab allocator in Linux. It, again, operates as a layer above the physical page frame allocator.

---
Tags: virtual-memory, memory-allocation
---


# Question
Title: Prove that if C is a regular language, then the language $\{x x^R : x\in C\}$ is context-free
> Let $C$ be a regular language. Prove that the language $D = \\{x x^R : x\in C\\}$ is context-free.

It's clearly important that $C$ is regular; if the hypothesis were weakened to C being context-free, then we would have the counterexample $C = \\{0^n 1^n : n\ge 0\\}, D = \\{0^n 1^{2n} 0^n:n\ge0\\},$ which isn't context-free.

Assume $G\_C$ is a context-free grammar for $C$ in Chomsky normal form. I don't think that just replacing every rule of the form $X\mapsto YZ$ in $G\_C$ with $X\mapsto YZZY$ will produce the required language; rather it likely produces something like $\\{x y^R :x,y \in C\\} = C\cap C^R,$ which is clearly regular.

Maybe some closure properties might be useful? For instance, if $A$ is a context free language and $B$ is a regular language, then $A\cap B$ is context free. I know $CC$ is a regular language, and I know that the set of all palindromes of a regular language is a context-free language. But I don't think $D$ is the set of all palindromes of $CC$.

# Answer
Recall that every finite state automaton can be changed into a rightlinear grammar which has productions like $X\to aY $ and $X\to \varepsilon$.

Your language can be generated using the same technique, but with linear productions which have the form $X\to aYa $ or $X\to \varepsilon$.
> 3 votes

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


# Question
Title: Algorithm for searching two numbers whose absolute difference is small
Let $A$ be an array of numbers. Let $y$ be positive.

We want to find two numbers $A\[i\]$ and $A\[j\]$ such that their absolute difference is at most $y$.

# Answer
Instead of using a hash *set* (← that refers to the question text before they vandalized it, just like the names $x\_i$ instead of $A\[i\]$), use a hash *map*. Store each $x\_i$ under its hash $h\_i = \lfloor \frac{x\_i}{y} \rfloor$. But before you store it, check it against the hash entries $h\_i-1$, $h\_i$ and $h\_i+1$ and report a pair if it's close enough.

Python implementation:

```
def pair(xs, y):
    seen = {}
    for x in xs:
        h = x // y
        for H in h-1, h, h+1:
            if H in seen:
                X = seen[H]
                if abs(x - X) <= y:
                    return X, x
        seen[h] = x

print(pair([0, 2, 4, 6, 8, 3.14], 1.1))

```

Output (Try it online!):

```
(4, 3.14)

```
> 3 votes

---
Tags: algorithms
---