# Question
Title: Given an CFG determine if $\varepsilon \in L(G)$
Given a context free grammar how am I able to determine if $\varepsilon \in L(G)$ ?

The only way I thought of is to systematically check if I can derive the empty word from the given grammar. (Assuming it's not in CNF)

Is my intuition right though?

# Answer
> 1 votes
Your intuition is not fully right. Consider the membership problem which is defined by $$L = \\{ \langle G, w\rangle: G \ is \ a\ CFG \ that\ generates \ the\ finite \ word \ w\\}$$ It is know that $L$ is decidable and the right way to prove this is by using CNF for CFGs. The problem with what you mentioned is the following. Let $G$ be a CFG and let $w\in \Sigma^\*$ be a finite word. If $G$ is not in CNF form, then you propose the following: "systematically check" if there is a derivation for $w$ in $G$. Well, this is not a good idea. Assume that you go over all derivations in some lexical ordering and once you find a derivation for $w$, we stop. The problem with this approach is that we may not halt. As a specific example, consider the following CFG: the rules are $S\to A$, $A\to A|a$ , where:

* S is the strat variable.
* A is a variable.
* a is a letter (or terminal).

Clearly, $L(G) = \\{ a\\}$. But the algorithm suggested does not halt as you need to try an infinite number of derivations and check whether $\epsilon$ is derived by one of them. Indeed, you can apply the rule $A\to A$ as much as you like.

The nice thing about CNF form is that if a word $w$ is in $L(G)$, then it requires exactly $2|w| - 1$ derivation rules to derive $w$. Hence, in order to check whether $w$ is in $L(G)$, you only need to consider all derivations of length $2|w| -1$. In particular, the algorithm halts.

# Answer
> 1 votes
You can transform the CFG to Greibach normal form, and then simply check whether the rule $S\rightarrow \varepsilon$ exists.

In fact, you are asking whether there is a parsing algorithm for CFG.

# Answer
> 1 votes
In a way, yes. But is is not straightforward what means "systematically check".

Probably the best way is to determine all the *nullable* symbols of the grammar. Here a symbol $X$ is nullable if there exists a derivation $X\Rightarrow^\* \varepsilon$. Then check whether axiom $S$ itself is nullable.

Now $X$ is nullable if there exists a production $X\to \varepsilon$ or (recursion) if there exists a production $X\to\alpha$ such that all symbols in $\alpha$ are nullable. I think an algorithm for this repeatedly looks for productions of the type $X\to\alpha$ with $\alpha$ nullable, and marking the found $X$ as nullable. The algorithm stops when after a cycle over all productions no new nullable symbols are found.

If your grammar is in Chomsky or Greibach normal form, then either generating $\varepsilon$ is ignored, or it can only occur at the first step with a special $S\to\varepsilon$ production. First transforming into Chomsky or Greibach normal form does not particularly help, as those transformations include determining the nullable symbols.

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


# Question
Title: How can I check if $n >m$ in $a^n b a^m$?
How can I design a Turing machine that takes string $a^n b a^m$ and check if $n\>m$ then convert the string to $a^{n-m}$, otherwise reject it?

# Answer
> 1 votes
Start with placing tape over $b$, then go to the rightmost $a$, put blank, go back to $b$ and delete the rightmost $a$.
Every time you scratch out $a$s on both sides, $n - m$ does not change until one side is blank.
Check if the left side is not empty, delete $b$ (and if it is required, go back to the beginning of the tape) and accept, otherwise reject.

---
Tags: turing-machines
---


# Question
Title: decision diagram and decision tree difference
What are the difference between decision diagram and decision tree? Is BDD a type of DD? what are the other type of DD? what are the algorithms used for it

# Answer
> 1 votes
Decision tree is a tree.

Discision diagram is not necessarily a tree.

A binary decision diagram is a directed acyclic graph.

See the diagram at https://en.wikipedia.org/wiki/Binary\_decision\_diagram

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


# Question
Title: Can I decrypt an RSA algorithm using only the message I am wanting to decrypt, an "e" value and a "n" value?
I have a ciphertext $c$ encrypted with RSA algorithm that needs to decrypt. I have the public key $(n,e)$.

Is it possible to decrypt with this amount of information?

# Answer
You have the public key. The whole point about public key cryptography is that the message is encrypted with the public key and must be decrypted with the private key, which you don't have.

The public key is not a secret: it is distributed publically so that people can encrypt messages for its owner. If you could decrypt the message knowing the cyphertext and the public key, RSA would be completely broken, because then anybody could decrypt any message. If anybody knows how to do this, they're keeping it a secret.
> 2 votes

---
Tags: cryptography
---


# Question
Title: What is the time complexity for division by repeated subtraction?
Given the following algorithm :

```
    input : a (integer), b (integer != 0)

    result = 0;
    while(a >= b)
    {
       a = a - b;
       result = result + 1;
    }

    return result;

```

How to find the number of instructions and the time complexity of this kind of algorithm since we don't know neither a nor b nor the number of iteration in advance ?

# Answer
Your algorithm makes exactly $\lfloor\frac{a}{b}\rfloor$ iterations of while loop.

If we suppose that the size of the inputs is $n=max\\{a,b\\}$ then your algorithm will make at most $n$ iterations; when $a=n$ and $b=1$.

Therefore, with this notation, your algorithm (on a high level) runs in $O(n)$ time complexity.

---

If you want to analyze it deeper, including the complexity of addition and subtraction which are $\Theta(n)$ for $n$-digit numbers, things get more complicated because $n$ we defined above was not the number of digits (decimal representation) but a value (unary representation).
As it can be shown, the base in which we represent numbers is not relevant, so the overall analyzed algorithm, having in mind also the properties of big-O and big-Theta runs in $O(n^2)$ where $n$ is the number of digits (in any base).
> 1 votes

# Answer
As your `while` is run in $\frac{a}{b}$-times, and inside your loop there just an add and subtraction, the time complexity is $\Theta(\frac{a}{b})$.
> 0 votes

---
Tags: algorithm-analysis, time-complexity
---


# Question
Title: Find a regular grammar that generates words with even number of a's
I have a language $L$ = {$vabu$ | $v$,$u\in \\{a,b\\}^\*$, $|vu|\_a = 0$ $($mod $2)$$\\}$

where $|vu|\_a$ is number of $a$ in $vu$.

I came up with these rules:

$\sigma \rightarrow aa\sigma | ab\xi$

$\xi \rightarrow aa\xi | \epsilon$

This generates words in form: $(aa)^iab(aa)^j\epsilon$, but not all words in $L$ look like this.

How do I make sure that $b$s can be put anywhere in between $a$s in $v$ and $u$.

Edit: I think I found a solution.

$\sigma \rightarrow b\sigma$ | $a\alpha$ | $ab\gamma$

$\alpha \rightarrow b\alpha$ | $a\sigma$ | $ab\eta$

$\gamma \rightarrow b\gamma$ | $a\eta$ | $\epsilon$

$\eta \rightarrow b\eta$ | $a\gamma$

# Answer
> 5 votes
"How do I make sure that $b$'s can be put anywhere in between $a$'s in v and u?" Hint, you may need another non-terminal.

Here is a hint about the higher-level approach to the question although you did not ask for it, since it looks like you are not in the reasonably correct way to move forward. I would also encourage you to go forward with your approach as far as possible, if only to experience and see why it does not work (it may work in the end).

Let us define two simpler languages, $$E=\\{w | w\in \\{a,b\\}^\*, |w|\_a = 0(\text{mod } 2)\\}$$ and $$O=\\{w | w\in \\{a,b\\}^\*, |w|\_a = 1(\text{mod } 2)\\}.$$

Can you write regular grammar for $E$ and $O$ ? Can you piece together some E's and O's to form $L$?

Once you have done the problem, you might be able to see a general strategy on how to generate regular grammars for these "simple" languages.

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


# Question
Title: A robot arm consisting of a sequence of rigid line segments L1, L2, . . . , Ln hinged together consecutively
Hi I am a Computer Science student attempting to solve this problem for extra credit. Problem is I am unsure what this algorithm is asking for as the language is a bit hard for me to follow:

> Imagine that you have a robot arm consisting of a sequence of rigid line segments $L\_{1}, L\_{2}, \dots , L\_{n}$ hinged together consecutively. The lengths of the line segments $l\_{1}, l\_{2}, \dots , \> l\_{n}$ are positive integers. You may rotate freely around the hinges and the line segments are allowed to cross over. Our goal is to pack in the line segments into one line segment as compactly as possible. More precisely, given positive integers $l\_{1}, l\_{2}, \dots , l\_{n}$ (and $l\_{0} = 0)$ and a sequence of $\pm1$’s, $s\_{0}, s\_{1}, \dots , s\_{n}$, where $s\_{i} = 1$ or $s\_{i} = −1$, $0 ≤ i ≤ n$, define
>
> $$m\_1 = \min\_j\left(\sum\_{i=0}^j s\_il\_i\right) $$ $$m\_2 = \max\_j\left(\sum\_{i=0}^j s\_il\_i\right) $$ where ($0 ≤ j ≤ n$). Find $\min\_s (m\_{2} − m\_{1})$, where the minimum is taken over all sequences $s = (s\_0, s\_2, \dots , s\_n)$.

The goal is for me to write an algorithm that solves this problem. But I am not entirely sure what the question is asking. My understanding is drawn below:

The arms shall be compacted as much as they can be such the vertical height of the extended arm is minimized. But I don't understand what the $s\_0, s\_1,\dots, s\_n$ sequence is for? And if someone could describe in layman's terms what the sequences $m\_1$ and $m\_2$ are asking for that would be great.

# Answer
The $s$'s tell you which way each segment of the arm is pointing: $s\_i=+1$ if the $i$th segment points up and $s\_i=-1$ if the $i$th segment points down.

This means that $S\_j := \sum\_{i=0}^j s\_i\ell\_i$ is the distance of the end of the $i$th segment from the pivot. So $\min\_j S\_j$ and $\max\_j S\_j$ are the height of the lowest and highest points of the arm when it's folded in the way that $s\_0, \dots, s\_n$ describe.
> 2 votes

---
Tags: algorithms
---


title: Help with Time Complexity

text:
# Question
Title: Help with Time Complexity
Suppose we have the function below:

```
def func(n):
    for i in range(n):
        for j in range(n - i):
            for k in range(n - j):
                if i + j + k == 0:
                    break
            if i + j == 0:
                break
        if i == 0:
            break
    return n + 1

```

We have three nested for-loops and the total number of elements evaluated appears to be: (n)(n-1)(n-2). However, this cannot be correct, as I know the time complexity of this function is not O(n^3). What is the proper way to evaluate the time complexity of this function?

# Answer
Your function has constant running time (or linear running time, depending on how `range` is implemented). I suggest running it step-by-step and seeing what happens.
> 1 votes

# Answer
If this is for Python 3.0 then by this knowledge;

* Your function is constant time $\mathcal{O}(1)$. Since every loop runs once end finishes.

If Python version \< 3.0;

```
def func(n):
    for i in range(n):             #generates all the numbers at once
        for j in range(n - i):     #generates all the numbers at once
            for k in range(n - j): #generates all the numbers at once
                if i + j + k == 0:
                    break
                else:
                    eval()
            if i + j == 0:
                break
        if i == 0:
            break
    return n + 1

```
* Since each loop actually runs once the result will be $\mathcal{O}(n)$ assuming that your `eval` function is in $\mathcal{O}(n)$.
> 0 votes

---
Tags: time-complexity, python
---


# Question
Title: If lower bound of a problem is exponential then is it NP?
Assuming that we have a problem $p$ and we showed that the lower bound for solving $p$ is $\mathcal{\Omega}(2^n)$.

* can lower bound $\mathcal{\Omega}(2^n)$ implies the problem in $NP$?

# Answer
> 21 votes
No. For example, the halting problem has an $\Omega(2^n)$ lower bound, but it is not in NP (since it is not computable).

The nondeterministic time hierarchy theorem shows that any NEXP-complete problem is another example (with $2^n$ potentially replaced by a smaller exponential function $c^{n^\epsilon}$).

NP is an *upper bound* on the complexity of a problem.

# Answer
> 14 votes
No. First, as Yuval points out, the problem could be much harder than the lower bound that you've proven.

Second, even if the problem takes time $\Theta(2^n)$ to solve, we don't know how this relates to $\mathbf{NP}$. It's possible that $\mathbf{P}=\mathbf{NP}$, in which case any problem in $\mathrm{TIME}\[\Omega(2^n)\]$ is certainly not in $\mathbf{NP}$ by the time hierarchy theorem. But even if $\mathbf{P}\neq\mathbf{NP}$, it's possible that the problem requires exponential space so isn't in $\mathbf{NP}$.

The best algorithms we know for $\mathbf{NP}$-complete problems take exponential time but you shouldn't assume that "in $\mathbf{NP}$" means "takes exponential time" or vice-versa.

---
Tags: time-complexity, np-complete
---


# Question
Title: How is it that programs can be identified with partial functions for programming language semantics?
I was reading about denotational semantics

> Broadly speaking, denotational semantics is concerned with finding mathematical objects called domains that represent what programs do. For example, programs (or program phrases) might be represented by partial functions.

I was wondering, how does one map programs to partial functions? What is the mapping? What is the intuition and conceptual idea? I don't understand what the relationship (formally or conceptually) is between partial functions and program (or Turing Machines).

# Answer
> 3 votes
Partial functions from *initial* program states to *final* program states are a suitable model for deterministic sequential programs that do not interact with the environment while executing. Such programs just try to compute a result depending on what they find in their starting state. If program $P$'s attempted computation fails when starting from some initial state $\sigma$, then that means that the function describing $P$'s semantics doesn't yield a final state for $\sigma$.

Using *functions* (of the common type mentioned above) makes sense when the constructs of the programming language under consideration are deterministic. That is the case e.g. for a language made up of assignment statements, sequential composition, conditionals, and while loops.

*Partial* as opposed to total functions are chosen for two reasons. 1. to allow loops to diverge and 2. to model problems such as division by 0.

# Answer
> 0 votes
The point is to express what a piece "means"/semantics. To define what it means we map syntax \**at a given state \** (that takes in a state $\sigma$) to a mathematical object. This mathematical object is maps. Basically code takes in states to states (where a \[of the program\] state just says what the variables are for example). So for example:

$$ \[\\!\[ i \]\\!\] \sigma = f\_i(\sigma) = i$$

where $\[\\!\[ i \]\\!\] = f\_i$ the partial map that when given a state returns the integer $i$. That is what the code fragment $i$ means. Basically $\[\\!\[ \cdot \]\\!\]$ maps the syntax to a CPO (complete partial order), essentially partial functions.

The reason we do this is because we are defining what the code does by saying how it maps states to states. Partial is because some code maps to undefined $\bot$. So some subset of the domain (domain are states) is undefined or simply we say

$$\[\\!\[ Syntax \]\\!\] \sigma = f\_{Syntax} ( \sigma ) = \bot $$

Programs map states to states or undefined. Thats why programs can be mapped to partial functions.

---
Tags: programming-languages, semantics, denotational-semantics
---


# Question
Title: Why does the denotational semantics for a while loop have a existence quantifier?
I was going through these notes and they have the following operator on partial functions:

$$ \mathcal F^{k}(\bot)(\sigma) = \left\\{ \begin{array}{ll} \alpha( \[\\!\[s\]\\!\]\sigma ) & \[\\!\[b\]\\!\]\sigma=true \\ \sigma & \[\\!\[b\]\\!\]\sigma=false \\ \bot & \[\\!\[b\]\\!\]\sigma=\bot \end{array} \right. $$

and supposedly it gives the following definition somehow (which ends up being the right denotation for while loops)

$$ \mathcal F^{k}(\bot)(\sigma) = \left\\{ \begin{array}{ll} \[\\!\[s\]\\!\]^i & \mbox{if $ \exists i \in \[0,k)$ s.t. $ \[\\!\[b\]\\!\] \[\\!\[s\]\\!\]^i \sigma = false,\ \[\\!\[b\]\\!\] \[\\!\[s\]\\!\]^j \sigma = true,\ j \in \[0,i) $}\\ \bot & \mbox{ o.w. } \end{array} \right. $$

the proof by induction is shouldn't be hard. However, it feels that it doesn't really answer the question for me intuitively because I could do the induction mechanically without understanding what is going on. Why isn't the definition something like:

$$ f(\sigma,i) = \[\\!\[s\]\\!\]^i\sigma$$

then the induction is easy:

$$ f(\sigma,0) = \[\\!\[s\]\\!\]^0\sigma = \sigma$$

then the inductive step:

$$ f(\sigma,k+1) = f \circ f{\circ}^k(\sigma)= f \circ\[\\!\[s\]\\!\]^{k}\sigma$$

but also notice $f = \[\\!\[s\]\\!\]^1\sigma$ by strong induction:

$$ f(\sigma,k+1) = \[\\!\[s\]\\!\]^{k+1}\sigma$$

as required. But that doesn't seem at all to be the sort of argument being used (assuming what I wrote is right). Did I miss something?

# Answer
The existential quantifier is misplaced. This is due to lack of reasonable notation for what needs to be expressed, namely: "if there is $i$ safisfying condition $C$, then use that $i$", where we make sure that at most one such $i$ exists. It would be better to write (and by the way, you might appreciate LaTeX's `cases` environment): $$ \mathcal F^{k}(\bot)(\sigma) = \begin{cases} \[\\!\[s\]\\!\]^i & \text{if $i \< k$ and $\[\\!\[b\]\\!\] \[\\!\[s\]\\!\]^i \sigma = \text{false}$ and, for all $j \< i$, $\[\\!\[b\]\\!\] \[\\!\[s\]\\!\]^j \sigma = true$}\\ \bot & \text{otherwise} \end{cases} $$ It may be helpful to look at a simpler definition. Suppose we want a function $f : \mathbb{N} \to \mathbb{N}$ which maps an odd number to zero and an even number to half of itself. The following is a reasonable definition: \begin{align\*} f(2 n) &= n\\ f(2 n + 1) &= 0 \end{align\*} as is the following (where $m$ and $n$ range over natural numbers): $$ f(m) = \begin{cases} n & \text{if $m = 2 n$,}\\ 0 & \text{otherwise.} \end{cases}$$ The point is that precisely one branch applies, and in a unique way, as there can be at most one $n$ satisfying the condition $m = 2 n$. However, the following is *not* a reasonable definition: $$ f(m) = \begin{cases} n & \text{if $\exists n \in \mathbb{N} \\,.\\, m = 2 n$,}\\ 0 & \text{otherwise.} \end{cases}$$ The problem is that the $n$ outside the $\exists$ quantifier is completely unspecified. This is so because the $n$ inside the $\exists$ quantifier is *bound* and can therefore be renamed at will: $$ f(m) = \begin{cases} n & \text{if $\exists k \in \mathbb{N} \\,.\\, m = 2 k$,}\\ 0 & \text{otherwise.} \end{cases}$$ (And we do *not* rename the outer $n$ because it is not in the scope of $\exists$.) This makes it clear that the existential quantifier has no place there. It is important to understand variable bindings. In the above definition of $f$, the variable $n$ is bound in the *entire* case, not just in the condition.

From a very formal point of view, the map $f$ is defined here as a *relation* explaining how an argument of $f$ is related to its value. A definition of the form $$f(m) = \begin{cases} e\_1(m,n) & \text{if $\phi\_1(m,n)$} \\ e\_2(m,n) & \text{if $\phi\_2(m,n)$} \end{cases} $$ is equivalent to $$f(m) = \text{the $v$ such that $\psi(m,v)$} $$ where $$\psi(m,v) \iff (\exists n \\,.\\, \phi\_1(m,n) \land v = e\_1(m,n)) \lor (\exists n \\,.\\, \phi\_2(m,n) \land v = e\_2(m,n))$$ Now the quantifiers *are* justified. By the way, we could have used $\forall$ instead: $$\psi(m,v) \iff (\forall n \\,.\\, \phi\_1(m,n) \Rightarrow v = e\_1(m,n)) \land (\forall n \\,.\\, \phi\_2(m,n) \Rightarrow v = e\_2(m,n)).$$
> 4 votes

# Answer
The intuition is that the loop terminates at the $i$th iteration if the loop condition is false at that iteration but true at all earlier ones. If the loop condition is never false, then the loop doesn't terminate and the denotation is $\bot$.

However, it's written down wrongly. What it says is (and please pardon me for throwing away all the notation and working by analogy):

* The answer is $i$ if there exists some $i$ such that the loop condition becomes false at the $i$th iteration;
* otherwise, the answer is $\bot$.

The problem is that the variable $i$ only has meaning within the scope of "there exists some $i$ such that...", and it's referred to outside that scope. So what's written is equivalent to "The answer is $i$ if there exists some $q$ such that the loop condition becomes false at the $q$th iteration", to which the obvious response is "What's $i$?"

What it *should* say is:

* If there is some $i$ such that the loop condition becomes false at the $i$th iteration, the answer is $i$;
* otherwise, the answer is $\bot$.
> 3 votes

---
Tags: programming-languages, induction, formal-methods, denotational-semantics
---


# Question
Title: Remove duplicates from dictionary in a safe and clever way
I have a dictionary that has keys and multiple values per key. Same value can be assigned to multiple keys.

For the sake of simplicity, the keys are `int`s and the values are `string`s, so that it would look like in C#:

```
Dictionary<int,string[]>

```

As an example the dictionary is filled as follows:

```
{ 1, ["A","B"] },
{ 2, ["A"] }

```

I now have to **remove duplicate values, under the condition that each key keeps at least one value** (if at all possible).

So we cannot say 1 gets A, because 2 will then have no associated value anymore.

The result for the example should be:

```
{ 1, ["B"] },
{ 2, ["A"] }

```

Another example with result:

```
{ 1, ["A", "B"] },
{ 2, ["C", "D"] }
-->
{ 1, ["A", "B"] },
{ 2, ["C", "D"] }

```

One key cannot contains multiples times the same value, so the following scenario is not considered, it cannot happen:

```
{ 1, ["B"] },
{ 2, ["A", "A"] }

```

What I tried so far, but where I am not sure if I captured all edge cases or if there are more efficient or more logic ways:

1. If a key has only one value assigned, this is fixed. The value is removed from all other keys and the key value pair is removed from the iterating list and stored elsewhere

1.1 If after that removal one key does not have any values associated, the algorithm failed, it is not possible.

1.2 Repeat 1. until no key with only a single value is left.
2. Search for values that are only assigned to one key. The key value pair is removed from the iterating list and stored elsewhere
3. Repeat 1. to 2. until 2. does not find a result
4. No we have a list with only n to n relations. All keys have at least 2 values and each value is at least assigned to 2 keys.
5. Now we randomly remove one value from a single key.
6. Repeat 1. to 5. until nothing changes anymore.

Is there a standard algorithm for this requirement? I am still not sure if I considered all edge cases.

# Answer
Your question is very well written. Let me make one requirement even clearer. "Remove duplicate values" means that one value can be assigned to at most one key in the end, as explained in the given examples.

**Your algorithm might return the wrong result.** For example, consider the following dictionary.

```
{ 1, ["A", "B"] }
{ 2, ["A", "B"] },
{ 3, ["C", "A", "B"] },
{ 4, ["D", "A", "B"] }
{ 5, ["C", "D", "E", "F"] }
{ 6, ["C", "D", "E", "F"] },

```

Your algorithm might proceed to remove value "C" from key 3 followed by removing value "D" from key 4. You can check that each keys still has at least 2 values and each value is still at least assigned to 2 keys. However, you can see that key 1, 2, 3 and 4 have two values in total, "A" and "B". So it is not possible to assign each of those four keys with a different value. However, there is an assignment that is possible in the beginning, i.e., { 1, \["A"\] }, { 2, \["B"\] }, { 3, \["C"\] }, { 4, \["D"\] }, { 5, \["E"\] } and { 6, \["F"\] }.

---

The problem you are trying to solve is fundamentally **finding the maximal matching in unweighted bipartite graphs**. You can find various algorithms given in that Wikipedia page such as Ford–Fulkerson algorithm and Hopcroft–Karp algorithm. I will let you figure out how to adjust or extend those algorithms a bit to solve your task of "removing duplicates from dictionary".
> 1 votes

---
Tags: algorithms, dictionaries
---


# Question
Title: Will such an algorithm be feasible, will it be considered a poly time algorithm?
Given a p-digit number n, where p is atleast 500, if we have an algorithm whose computational complexity is in the worst case, $O(p\mathrm{log}(p))$, will it be counted as a poly time algorithm ? Or since $(p\mathrm{log}(p))$ is basically the logarithm of an exponent so it will inefficient. And such an algorithm will be infeasible or intractable. Secondly what if we can cut down the complexity in the worst case scenario to, $O(p\mathrm{log}(p)/5)/100 )$?

Will this complexity be considered same as the worst-case complexity?

# Answer
> 1 votes
As the length of the input is $p$ and the worst case of the algorithm is $O(p\log(p))$, the algorithm is polynomial as the worst case is $O(p^2)$ and $p^2$ is polynomial.

For the second case, there is not any change in time complexity as constant values are multiplied or divided in the polynomial or logarithmic case. To scrutinize more, $p \frac{\log(p/5)}{100} = p \frac{(\log(p) - \log(5))}{100} = \frac{p\log(p) - p\log(5)}{100} = \Theta(p\log(p))$.

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


# Question
Title: Is there a "well known" example of a constraint satisfaction problem on a 3-element set which is polynomial-time solvable?
I'm basically looking for an example (in maybe graph theory) of a constraint satisfaction problem which has a 3-element set as a domain and the problem is known to be polynomial-time solvable.

# Answer
> 2 votes
If you want a graph, it needs to be bipartite. Hence the path of two edges or any subgraph thereof. (Here I am following the convention that graphs have no loops. As David Richerby points out in a comment, graphs with loops also have polynomial-time CSPs (by virtue of triviality).)

A more interesting example is linear algebra over the three-element field: The domain is the set of congruence classes $\bmod 3$ and the constraint relations are given by linear equations.

---
Tags: polynomial-time, constraint-satisfaction
---


# Question
Title: Algorithmic Design to Undo Rotation of Array
An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A\_{k}$.

That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $A\_k$.

Devise a $\Theta(\lg(n))$ algorithm to recover $k$ from $A\_k$ where $\lg(n) = \log\_2(n)$.

To clarify, the algorithm needs to determine what the shift $k$ applied to $A$ was which resulted in $A\_k$. Thus, $A\_k$ is sufficient enough for the algorithm to work with in order to determine the shift since we know that $A$ consisted of ascending integers.

Any help or insight would be greatly appreciated!

# Answer
I assume this is a homework question, so I will not solve it for you. I'll just give you some hints.

The problem is basically to find the *drop* in $A\_k$, that is the pair of consecutive elements such that the second one is smaller than the first one. Indeed, these two must be the last and first element of $A$.

Now, if you are given a subinterval of $A\_k$, how can you tell whether it contains the drop? Hint: It can be done in $\Theta(1)$.
> 2 votes

---
Tags: algorithms, search-algorithms, arrays
---


# Question
Title: Is the Complement of the Language $L=\{wxw^r|w \in (a+b)^+, x \in (a+b) \}$ Context free?
I know that the Context-free languages are not closed under compliment.

Given $L=\\{wxw^r| w \in(a+b)^+,x \in (a+b)\\}$ and this is a Context free language. I think it's compliment will contain words of the form $ww$ which comes under CSL.So, I think this $\lnot L$ must be not context-free.But I've read here

Why are palindrome and not-palindrome both context-free?

that palindromes are closed under complement.

Can someone please guide over this?

# Answer
Generally speaking, the way to figure out whether a given language is context-free is twofold:

* Try proving that it is not context-free, say using the pumping lemma.
* Try proving that it is context-free, say by constructing a grammar or a PDA.

If any of these methods succeed, you will have found whether the language is context-free.

In your particular case, we can notice that a word $y$ is not in $L$ if one of the following three cases occurs:

* $y$ has even length.
* $y$ has length one.
* $y$ has odd length, and when written as $y = z \sigma w^R$, with $|z| = |w|$, the two words are different.

In the third case, let us suppose that $z\_i = \alpha \neq \beta = (w^R)\_i$, and put $\ell = |z| = |w|$. Then $y \in \Sigma^{i-1} \alpha \Sigma^{\ell-i} \sigma \Sigma^{\ell-i} \beta \sigma^{i-1}$, and all such words are not in $L$. We conclude that $$ \overline{L} = (\Sigma\Sigma)^\* \cup \Sigma \cup \bigcup\_{\substack \sigma, \alpha \neq \beta \in \Sigma \\ j,k \geq 0} \Sigma^j \alpha \Sigma^k \sigma \Sigma^k \beta \Sigma^j. $$ It is routine to construct a context-free grammar for the expression on the right, and so $\overline{L}$ is context-free.
> 2 votes

---
Tags: context-free
---


# Question
Title: On uniform randomness of the weight of the remaining edges of a graph after deleting some of them
Suppose we have a graph $G(V,E,W)$, where $V$ and $E$ are the set of vertices and edges and $W$ is non-negative weight on the edges. Let $w(e)$ be the weight of edge $e$ and $N(e)$ be the neighboring edges of $e$. An edge $e$ is locally subdominant if its weight is smaller than all of its neighbors. With this background Let we have the following algorithm,

```
for e in E
if w(e) is locally sub-dominant
    delete e from the graph G
    double weights of all e in  N(e)

```

My question is after this loop ends what can we say about uniform randomness of the remaining edges. Are they still uniform random?

# Answer
> 1 votes
Let us consider the simplest case, that of a path of length two edges, which are drawn uniformly and independently from $\[0,1\]$. Let us suppose that the first edge is sub-dominant, which happens with probability 1/2. The probability that the weight of second edge is at most $t \in \[0,1\]$ is $$ \Pr\[x \leq y \leq t \mid x \leq y\] = \Pr\[x,y \leq t\] = t^2. $$ Here $x$ is the weight of the first edge, and $y$ is the weight of the second edge. We see that even before doubling, the distribution of $y$ is non-uniform.

Next, let us examine the case of a star with three edges, again drawn uniformly and independently from $\[0,1\]$. Again suppose that the first edge is sub-dominant, which happens with probability 1/3. The probability that the weight of the second edge is at most $t \in \[0,1\]$ while that of the third edge is at most $u \in \[0,1\]$ is $$ \Pr\[y \leq t, z \leq u \mid x \leq y,z\] = 3 \int\_0^{\min(t,u)} (t-x)(u-x) \\, dx = \\ 3tum - \frac{3}{2}(t+u)m^2 + m^3. $$ Here $x,y,z$ are the weights of the first, second, and third edges, respectively, and $m = \min(t,u)$. Substituting $u = 1$, we obtain $$ \Pr\[y \leq t \mid x \leq y,z\] = \frac{3t^2-t^3}{2}. $$ Calculation shows that for generic $t,u$, $$ \Pr\[y \leq t, z \leq u \mid x \leq y,z\] \neq \Pr\[y \leq t \mid x \leq y,z\] \Pr\[z \leq u \mid x \leq y,z\], $$ that is, the remaining weights are no longer independent.

---
Tags: algorithms, graphs, randomness
---


title: Discrete Mathematics Proofs for ∃ and ∀

text:
# Question
Title: Discrete Mathematics Proofs for ∃ and ∀
Premises or Givens:

* $∃x(A(x) → B(x))$
* $∀x (B(x) → K(x))$

To Prove:

* $∃x(A(x) → K(x))$

My Solution:

1. $A(z) → B(z)$ From premise and Existential instantiation $x$ for $z$
2. $B(z) → K(z)$ From premise and Universal instantiation $x$ for $z$
3. $A(z) → K(z)$ Transitivity of 1,2
4. $∃x(A(x) → K(x))$ From Existential generalization (Substitute $z$ for $x$)

OR

I was thinking about assuming $A(z)$ and then using Modus Ponens to get $B(z)$ and then further $K(z)$, then using the deduction theorem on $A(z)$ and $K(z)$, and then using Existential Generalization on that statement by substituting $x$ for $z$.

> Can someone suggest which way would be more effective?
>
> Is there any other effective way to solve it?

# Answer
Your solution is a good one, and that's how I'd prove it also. I don't believe a more straightforward or simpler version is possible.
> 1 votes

---
Tags: discrete-mathematics, predicate-logic
---


# Question
Title: Are space allocated to C/C++ variables in secondary storage also in Compiled file?
Are data segments,heap,stack etc also present in secondary memory with compiled code then later mapped by OS to RAM when I open it?

# Answer
> 1 votes
Under most operating systems the binary executable and object files stored on disk contain three segments:

1. the .text segment (the code)
2. the .data segment stores the initial value for any global and static variables that need to be initialized to specific values other than zero.
3. the .bss segment stores the global and static variables that don't need to be initialized, or are initialized to 0. Typically only the size of the .bss segment is stored since the loader can easily create a segment in RAM of this size and fill it with zeros without wasting the time and disk space to store a bunch of redundant information in the executable stored on disk.

The wikipedia page https://en.wikipedia.org/wiki/Data\_segment#Data gives some examples.

The stack and heap are typically not stored in the binary executable. They are set up by the loader in RAM when the program is started.

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


# Question
Title: Can we use Convolutional Neural Network for dataset containing numeric data?
I am working on a project of " Fraud detection using deep learning" . For that I have a dataset containing some numerical attributes . Now the task is to use CNN for the above purpose. Please guide me how can we do that as I have observed that it can be used only for image classification. I would appreciate if I get some research paper or blogs related to that.

# Answer
> 3 votes
Convolutional neural networks are just one of many models for classifing data. All models can be used for any data and they differ only in performance.

When you feed an image to the CNN (or any other model), the model does not “see” the image as you see it. It “sees” numbers that describe each pixel of an image and does all calculation using those numbers.
As was pointed in the comments; at the end, everything is effectively a number in the computer.

Your task asks you to use CNN because it will most likely perform best (in comparisson to other models) at this specific task. CNNs are very good at classifying objects that are not too similar, but have some shared features presented in a not too obvious way.

You can read about classification models here and I found a paper about detecting fraud with CNNs that might help you.

---
Tags: neural-networks
---


title: Fill the time slot with the best match

text:
# Question
Title: Fill the time slot with the best match
If I have the following array: `pieces = {35,15,20,25,30,10}` and the time slot is `80` minutes. How do I do the following:
1. Fill the time slot with any pieces for the perfect fit. (In our case: 30,35,15 or 15,25,30,10 etc.) 2. Fill the time slot with the best fit possible with deviation: (Let's say our time slot is 103 minutes and the deviation is +/-20 minutes. So, we are looking for the best fit anywhere in the 83-123 minute range.
3. Is there any optimizations that can be done if `pieces` array is sorted?

I'm looking for basic CS algorithms and strategies for optimizing runtime or space. I'm not looking for a specific solution to my problem. Instead, I'm interested in the CS topics I need to look into.

I'm able to solve the simplest version of this problem: Find out if 2 pieces for the time slot and return true. Solution: Loop through the array. Create hashtable and check if hashtable contains `timeslot-pieces[i]` if yes, then return true, if no, then add to hashtable.

# Answer
This is a well known problem in computer science, and can be mentioned as "Find all distinct subset sums in an array". The obvious solution is to generate all subsets which will take O(2^n) time for an array of `i` elements. Instead, if the sum that you can make is relatively small, you can can use dynamic programming technique to precompute a table which will mark the reached sums. The implementation details of these two ideas can be seen here. Notice that this answers also the second question.

Regarding the third point, whether having a sorted array will allow for further optimizations, the answer is no. If you would've had an applicable greedy solution (taking always the maximum or the minimum element according to some criteria) than it would've been very possible to optimize it somehow, but with simple tests it can be proven that greedy doesn't work in this case. (if it had it would certainly be faster than the dp).
> 1 votes

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


# Question
Title: Avoiding the trivial certificate in complexity class NP
One definition of the class NP is that there is a certificate whose size is bounded by a polynomial function of the problem instance size which can be used on a deterministic TM, along with the original input, to decide whether the input is a part of the language.

Doesn't this definition allow the trivial loophole where we let the certificate simply be 1 if the input is a part of the language and 0 otherwise? Then the deterministic just uses the certificate entirely and totally ignores the input.

# Answer
The point that you're missing is that the deterministic algorithm is given an input to the **NP** problem and string and it has to say either "That string is a valid certificate for the input" or "That string is not a valid certificate for the input." For example, for compositeness, the verifier would have to be able to accept "Six is composite because it is two times three" and reject "Five is composite because it is two times three." This can be done easily, by checking the arithmetic and checking that the claim isn't something like "$p$ is prime because it is $p$ times one."

If the certificate is just one bit, the only way the verifier could check that a string is a valid certificate would be to ignore the certificate and solve the problem. Using compositeness again, the verifier's input would be just "Six is composite because, well, I promise it is" and "Five is composite because, well, I promise it is." The verifier can't just "believe" that the string is a valid certificate.
> 2 votes

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


# Question
Title: Raft algorithm: What's the data format of `term`?
> Time is divided into terms, and each term begins with an election. After a successful election, a single leader manages the cluster until the end of the term. Some elections fail, in which case the term ends without choosing a leader. The transitions between terms may be observed at different times on different servers.

In Raft algorithm, term is a limited period of time, and widely used in leader election, log replication.

1. What's the data format of term?
2. Is it composed of Unix timestamp and length ?
3. How does every node guarantee their timestamp are synchronous? (Google Spanner use Atomic clock to guarantee true time).

# Answer
> 2 votes
Note that we are focused on Raft algorithm.

1. What's the data format of term?
A term is just a positive integer.
2. Is it composed of Unix timestamp and length?
No, it is not. A term is just a positive integer. It is that pure and simple. In practice for reasons such as reporting or auditing, it might be helpful to record the time period when each term is valid. However, that is not an essential part of the algorithm at all.
3. How does every node guarantee their timestamp are synchronous? (Google Spanner use Atomic clock to guarantee true time).
Presumably, the question is seeking to confirm that terms can be maintained properly if term is based on time. However, as said above, this term can be considered as having nothing to do with time. So the best answer to this question should be that there is no need to be concerned with that kind of guarantee.

Here is a figure that shows how term is used in the logs in Raft algorithm. The figure is taken from the award-winning paper In Search of an Understandable Consensus Algorithm by the creators of Raft algorithm. Those numbers 1,1,1,2,3,3,3,3, etc in each log entry are the terms. Note that actual time is not mentioned anywhere in that figure, although a term does correspond to a limited continuous period of time.

---
Tags: algorithms, databases
---


# Question
Title: Linear Temporal Logic (LTL) Syntax Infinitely Often
I'm a little confused about some LTL syntax.

When the Global and Future operator (GFx) or \[\]\<\>x is used, what does it mean. In the lecture slides it is given as infinitely often. But I don't understand it.

When used as FGx or \<\>\[\]x, I understand it as eventually in the future something will be true forever. E.g. eventually x will become 3 (x = 3) and x will stay as 3 forever.

Can someone explain what GFx means?

# Answer
> 5 votes
Consider just $Fx$. It means that at some point in time, say $t\_k$, from the perspective of current moment $t\_0$, $x$ will be true. After this moment, $x$ may never again be true. Specificaly, at the moment $t\_{k+1}$ the formula $Fx$ may not hold.

If we add $G$, we are saying that at every moment from current moment something most hold. $GFx$, that is $G(Fx)$, says that $Fx$ must hold in every moment, meaning that, in the above situation, even at $t\_{k+1}$ $Fx$ holds, that is — there must be some future moment where $x$ holds.

We have that for any moment $t\_i$ $Fx$ must hold. That means that for any $t\_i$ $x$ must hold at some future $t\_j$. Wherever we are in time, $x$ will hold eventually. And that is the same as saying that $x$ holds infinitely many times.

---
Tags: linear-temporal-logic, temporal-logic
---


# Question
Title: Have any natural complexity classes been proven not to be closed under complement?
Many important (non-deterministic) complexity classes like **NP** are believed not to be closed under complement. But have any of them been *proven* not to be?

I'm sure one could construct some contrived example, but is there any "natural" complexity class that has this property, by which I mean one that has been studied by theoretical computer scientist for reasons other than its lack of closure under complement?

I know that **RE** has been proven not to be closed under complement, but I don't know of any examples from complexity theory rather than computability theory - i.e. any classes defined in terms of some kind of *resource-constrained* Turing machine.

# Answer
There may be no such natural class, i.e. all natural classes are closed under complement.

Despite that $\mathrm{DTIME(n)\neq NTIME(n)}$ was proven, it is still possible that $\mathrm{NTIME(n^k)=co-NTIME(n^k)}$ for all natural number $k\geq1$.

For other kinds of model,we can similarly say that it is still possible: $$\mathrm{RTIME(n^k)=co-RTIME(n^k)=ZPTIME\_{\geq\frac12}(n)}$$ for all $k\geq1$.

Also, $\mathrm{UP=co-UP}$, etc.

And more importantly, all of these could **SIMULTANEOUSLY** hold if $\mathrm{L=CH}$ or $\mathrm{P=PP=CH}$ *without violating* **any known complexity result**.
> 1 votes

---
Tags: complexity-theory, closure-properties, complexity-classes
---


title: How can MLTT etc encode computability?

text:
# Question
Title: How can MLTT etc encode computability?
I am recently thinking about proving the undecidability of some problem. This problem has been formalized in Coq and by staring at it, people including me think "for sure" this is undecidable. "For sure" is a good source for surprises so I think I should try to prove it, probably formally.

But then I recall MLTT is compatible with LEM, and now my brain is in a loop:

To prove that theory is undecidable, I have to show that

```
forall x y ... z, ~({P x y ... z} + {~P x y ... z})

```

where `x y ... z` are the parameters. Namely, it's not true that we can decide the problem for all inputs.

On the other hand, LEM claims that for all `P x y ... z` we can obtain either witness or refutation, and its compatibility with type theory just says the falsehood is not provable. This means MLTT and others are just not able to express computability problems. Therefore, I am wondering can formal systems encode computability at all, or it's just I am mistaken? Is there anyone actually tried to formally prove undecidability in formal systems like Coq?

Even though I am using Coq, but since the compatibility is from MLTT, so I guess LEM does not have to live in Prop.

Apologies if I am being stupid for the moment but I think my brain is in a serious loop now.

# Answer
You have your quantifiers wrong. The `~` should be on the outermost level. That is:

`~(forall x y z, {P x y z} + ~{P x y z})`

i.e. to prove it's undecidable, you assert that there's no function which decides every instance. There may be functions which decide particular instances, which your type would rule out.

If you add LEM to MLTT, you can still have a perfectly good logic system, but provability in this logic no longer implies decidability.

Moreover, even the type I've listed above isn't sufficient: just because a problem isnt' expressible in MLTT or COC or any other non-Turing-complete logic, doesn't mean that it's undecidable.

A better approach would be model Turing Machines or (even better) a Turing Complete Lambda Calculus in your language, and assert that there are no functions in this model that always halt and answer your problem. This way, you're not trying to use your logic to reason about decidability within that logic, but an external model.

If you want an easier way, you could provide a function that takes as a parameter a function of type `forall x y z . {P x y z} + ~{P x y z}`, and returns a decision procedure deciding a commonly undecidable problem. (My favorite is Post's Correspondence, simulating a 2-counter machine is also an easy one). This reduces the trusted base of your proof: now the reader only needs to believe that PCP or 2CM is undecidable in order to see that your problem is.
> 3 votes

# Answer
One way to show that a predicate $P : A \to \mathsf{Type}$ is not decidable is to demonstrate, using intuitionistic reasoning, that decidability of $P$ implies decidability of a statement $S$ which is known not to be decidable. Since you are working in Coq, it helps to target a statement $S$ which is easily expressible in Coq.

For instance, we might use the principle LPO, $$\textstyle \mathsf{LPO} \equiv \prod\_{f : \mathbb{N} \to \mathsf{bool}} (\sum\_{n : \mathbb{N}} \mathsf{Id}(f n, \mathsf{true})) + \lnot (\sum\_{n : \mathbb{N}} \mathsf{Id}(f n, \mathsf{true})). $$ Ths is an instance of excluded middle, but is sometimes easier to reduce than general excluded middle. If you tell us a little bit about your problem, we might be able to suggest a good candidate $S$.
> 1 votes

---
Tags: computability, type-theory, formal-methods
---


# Question
Title: Compare each array $i$ member to all array $j$ member where $(i > j)$ , in time less than $O(n^2)$
I am new to algorithms so sorry to ask simple question

I am working on a problem which is about array of integers, my solution is right but not good enough, because I have time exceeded exception on codeforces. I think solution where solution's time \< O(n^2) would be right.

My solution:

```
int n;
cin >> n;

int currentScore = n;
int credits[n];
int grades[n];
for (int i = 0; i < n; i++) {
    cin >> credits[i];
    for (int j = 0; j < i; j++) {
        if (credits[i] <= credits[j]) {
            currentScore--;
        }
    }
    grades[i] = currentScore;
    currentScore = n;
}

for (int i = 0; i < n; i++) {
    cout << grades[i] << endl;
}

return 0;

```

# Answer
> 1 votes
Create a binary tree containing the points, either each node also containing the number of elements in each sub tree . For each candidate, determine the number of candidates arriving earlier, and having same or higher score using the tree, then add the candidates score to the tree.

Should work in O(n log n). I doubt O(n) is possible.

PS chi’s answer is a lot easier, and you probably have a library for the sorting, which is the hard part.

# Answer
> 1 votes
A basic approach would be as follows.

Given input $a\_1,a\_2,\ldots$ we build an array of pairs $A=(1,a\_1),(2,a\_2),\ldots$.

Now, in $O(n\log n)$ time, we can sort it according to the second component of each pair.

When $A$ is sorted in such way, it's easy to compute the score and modify $A$ so that it becomes of the form $A=(i,{\sf score}\_i),(j,{\sf score}\_j),\ldots$. This should cost $O(n)$.

Now, we can sort $A$ once more, according to the first component of each pair, so that we have $A=(1,{\sf score}\_1),(2,{\sf score}\_2),\ldots$. This costs $O(n\log n)$.

Finally, we print the scores.

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


# Question
Title: Karp hardness of an equidistant set in digraph
Following the success of the undirected version:

Karp hardness of an equidistant vertex set

Inspired by the success of this long ago question:

NP-hardness of problem with indices and subsets

We move on asking for the hardness of the directed version of an equidistant set.

> **Input**: A directed graph $G(V, A)$ and a natural number $k$
>
> **Output**: **YES** if $G$ has an equidistant vertex set of size $k$, otherwise **NO**

In this problem, we disallow opposite arcs like $(u,v)$ and $(v,u)$ to be both present in the arc set, i.e. either one of them or none.

$\DeclareMathOperator{\dist}{dist}$An **equidistant vertex set** is a set of vertices $V'\subseteq V$ such that for every two ordered pairs of vertices $u, v\in V'$ and $w, s\in V'$, we have $\dist(u, v) = \dist(w, s)$, where $\dist(u, v)$ is the length of a shortest path between $u$, $v$. Note that in digraph, it is possible that $dist(u,v)\neq dist(v,u)$.

# Answer
> 0 votes
This is $NP$-complete by reducing from the undirected version which was proven hard by Yuval's reduction.

For every pair of vertices $u$, $v$ in the undirected graph, if $dist(u,v)=2$ then we create two new vertices $x\_{uv}$, $x\_{vu}$ and add 4 arcs $(u,x\_{uv})$, $(x\_{uv},v)$, $(v,x\_{vu})$, $(x\_{vu},u)$. This guarantees that $dist(u,v)=dist(v,u)=2$ in our digraph.

Finally, add two vertices $src$ with outgoing arcs to all original vertices and $dst$ with incoming arcs from all original vertices. Add $x\_{src,dst}$ with two arcs similarly. Note that we do not have the opposite direction of $x\_{dst,src}$.

Now set $k=m+1$.

It is necessary to manipulate the case of having some $x\_{uv}$ vertex in an equidistant set. But, this is impossible (as long as $k=m+1\>4$ like in Yuval's reduction). To see this, suppose that $x\_{uv}$ is included in some equidistant set. Clearly, from $x\_{uv}$ going out, in one step, you must end at $v$. And, to reach $x\_{uv}$ in one step, you must go from $u$. So, there cannot be any vertex within distance 2 (in both directions) of $x\_{uv}$, except for $x\_{vu}$. So, our equidistant set can be of size only $2\<m$.That means we cannot have any $x\_{uv}$ vertex in our set. If instead we have $x\_{src,dst}$ in our set, we can easily see that there cannot be any other $x\_{uv}$ in our set. In all cases, we still have at least $m+1-1=m$-equidistant set without any $x\_{uv}$ vertices.

*Conversely*, if we have an $m$-equidistant set in the undirected graph, then we can add $x\_{src,dst}$ to this set to form an $m+1$-equidistant set.

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


# Question
Title: Is there a $O(n\frac{\log{n}}{\log{k}})$ sorting algorithm?
I am trying to figure out a sorting algorithm which can be used in $O(n\frac{\log{n}}{\log{k}})$ sorting time. I am allowed to use $k$ registers that can store key value pairs and these registers can insert a key value pair and return a key value pair in constant time. And when popping from one of these registers, it will return the smallest key.

So what I have so far is, I am thinking about having a hash function with value (highest value in array size $n$) and then put that into the registers, then will pop the registers (Which will return the smallest key value) and add those sorted values back into the array. But the main problem I have is I do not know how large $k$ will be so when I pop the values from the registers, I may have to put more values back in the registers, and was wonder how to go about this.

# Answer
> 0 votes
So the answer I ended up going with is making the value the key itself, then adding the key and the value to the registers. Once the registers are full, we will pop the smallest key, and do a binary search on where we should be inserting the value into a new sorted array which we will be returning.

---
Tags: algorithms, sorting
---


# Question
Title: Regex for at least three 1's and at most four 0's
The alphabet is {0,1}, express all finite strings containing at least three 1's and at most four 0's.

---

I've come up with a method that enumerate every possible number of 0's:

$$111^{+}+0111^{+}+1^{+}011^{+}+111^{+}01^{\*}+00111^{+}+......$$ But for three 1's and four 0's this is far too complex.

Need some help.

# Answer
Here is a solution for at least $a$ 1’s and at most $b$ 0’s: $$ \sum\_{a\_0+\cdots+a\_b=a} 1^{a\_0}1^\*\prod\_{i=1}^b (\epsilon+0)1^{a\_i}1^\*, $$ where $a\_0,\ldots,a\_b \geq 0$ are integers. For example, when $a=b=2$ we get $$ \begin{align\*} &111^\*(\epsilon+0)1^\*(\epsilon+0)1^\*+\\ &1^\*(\epsilon+0)111^\*(\epsilon+0)1^\*+\\ &1^\*(\epsilon+0)1^\*(\epsilon+0)111^\*+\\ &11^\*(\epsilon+0)11^\*(\epsilon+0)1^\*+\\ &11^\*(\epsilon+0)1^\*(\epsilon+0)11^\*+\\ &1^\*(\epsilon+0)11^\*(\epsilon+0)11^\*. \end{align\*} $$ With more effort, you can even create an unambiguous regular expression, that is, one which corresponds to a UFA rather than an NFA; in other words, whenever there is a sum, the corresponding languages are disjoint. As an example, here is an unambiguous regular expression corresponding to $a=b=1$: $$ 1^\*+11^\*01^\*+011^\*. $$ Compare this to the ambiguous one constructed above: $$ 11^\*(\epsilon+0)1^\*+1^\*(\epsilon+0)11^\*. $$ The words $1,101$ are both captured in both summands above, but in only a single summand in the unambiguous regular expression.
> 0 votes

---
Tags: regular-expressions
---


# Question
Title: Undecidable problem intersection of two DCFL languages is DCFL?
We have two deterministic pushdown automatas A and B, which languages are deterministic context-free. The problem is to decide if there exists a deterministic pushdown automata, which language is an intersection of the languages of A and B. This problem is known to be undecidable. But I can't find a proof for it.

# Answer
> 4 votes
**Problem statement**

We have two deterministic pushdown automatas (`DPDA`) $D\_1$ and $D\_2$. The problem is to decide whether there exists a `DPDA` $D$ such that $L(D) = L(D\_1) \cap L(D\_2)$.

**Post correspondence problem**

The proof is based on the fact that Post correspondence problem (`PCP`) is undecidable. Suppose we have a `PCP` problem with two input lists $\alpha = (\alpha\_1, ..., \alpha\_n)$ and $\beta = (\beta\_1, ..., \beta\_n)$

**Define languages**

Let $$L = \\{i\_1...i\_k\\#j\_m...j\_1\\$\beta\_{j\_1}...\beta\_{j\_m}\\$\alpha\_{i\_k}^R...\alpha\_{i\_1}^R | \\;1 \leq i\_l \leq n, 1 \leq j\_l \leq n \\}$$ One can constructively show that there exists a DPDA $D\_1$ that accepts $L$. From the other hand, the language with words $u\\$u^R\\#v\\$v^R$ also has DPDA $D\_2$. Let's call this language $L\_{rev}$.

Let intersection language be $L\_{\cap} = L \cap L\_{rev} $

**Emptiness of $L\_{\cap}$ is equivalent to PCP decidability**

Consider a word from $L\_{\cap}$. It is like $i\_1...i\_k\\#j\_m...j\_1\\$\beta\_{j\_1}...\beta\_{j\_m}\\$\alpha\_{i\_k}^R...\alpha\_{i\_1}^R$ and like $u\\$u^R\\#v\\$v^R$. So $\alpha\_{i\_1} = \beta\_{i\_1},..., \alpha\_{i\_k} = \beta\_{i\_k}.$

Since then, if $L\_{\cap} \neq \varnothing$ then there is a solution for PCP. Otherwise, there is no solution.

**Emptiness of $L\_{\cap}$ is equivalent to existing of $D$**

Furthermore if $L\_{\cap} = \varnothing$ then $L\_{\cap}$ has `DPDA` because it is empty. Using pumping lemma, one can show that if $L\_{\cap}$ is not empty then this language is not context-free. Since languages of `DPDAs` are subset of context-free languages then $D$ does not exist.

**Conclusion**

Assume we can decide if $D$ exists. Let's take our `PCP`, construct our languages and answer if $D$ exists. If it does exist, then the intersection language is empty and the `PCP` doesn't have a solution. Otherwise, it has. This way, we decide whether a solution for PCP exists. But this problem is known to be undecidable. We have come to a contradiction. Consequently, the assumption is wrong and the problem of deciding whether $D$ exists is undecidable.

---
Tags: context-free, proof-techniques, pushdown-automata, pumping-lemma
---


# Question
Title: Writing pseudocode to be language independent
There exist 5 rules for any pseudocode , one of these rules is : "Keep statements language independent" I don't understand what is this rule is saying. So can someone explain it and then give an example of pseudocode written to be language independent ? Moreover, the source for this rule is "Invitation to Computer Science, 8th Edition by Schneider/Gersting". Thanks in advance

# Answer
what is meant by independent is that Pseudocode is a description of a computer programming algorithm that uses structural conventions of a programming language, and is intended to be read by humans and not by machines. Pseudocodes usually do not use elements of sufficient detail that are not necessary for the needs of human understanding of an algorithm, such as variable declarations and codes. so that pseudocode is not tied to any programming language and pseudocode can be implemented in any language, whether it's C ++, Java, Python, or the latest programming language.

example

```
Start
Enter a, b
c = a + b
Print "c"
Finished

```

here is the same example, enter the values a and b so as to produce a value of c (sum of a + b)

You can use this pseudocode as a basis for making the addition program from different programming languages.

Java

```
// File name: Sum.java
// Description: The program displays the sum of 2 numbers

// use the Scanner class
import java.util.Scanner;

public class Addition
{
 // the main method before executing the java application
 public static void main (String args [])
 {
  // for the Scanner to get input from the form
  Scanner input = new Scanner (System.in);

  int number1; // first number
  int number2; // second number
  int sum; // number of numbers 1 and 2

  // cursor 1
  System.out.print ("Enter the First Number:");
  // reads input number 1 from the user
  number1 = input.nextInt ();

  // cursor 2
  System.out.print ("Entering the Second Number:");
  // read input number 2 from the user
  number2 = input.nextInt ();

  // sum of numbers
  sum = number1 + number2;

  // displays addition
  System.out.printf ("Sum is% d \ n", sum);
 } // end method
} // end class Addition

{

return(a + b);

}

```

c++

```
#include <iostream.h>
void main ()
{
int a, b;
float c;

cout << "Enter a:";
cin >> a;
cout << endl;
cout << "Enter the value b:";
cin >> b;
cout << endl;
c = a + b
cout << "The result is =";
cout << c;
}

```

that's the 2 code example programming language that uses the same pseudocode. hopefully can help you. :)
> 1 votes

# Answer
The rule means roughly that the statements and constructs should be clear and not be directly expressed in any actual programming language. For example, imagine we want to present a silly toy example for an algorithm that determines if the value 5 is present in an array. Perhaps you have never seen C++, but I still give you the following description:

```
#include <iostream>
#include <vector>
#include <algorithm>

int main()
{
   std::vector<int> v = { 1, 3, 5, 7 };
   auto iter = std::find(v.begin(), v.end(), 5);
   if(iter != v.end())
      std::cout << "found 5\n";
}

```

You might be confused and say "what include?", "what std::?", "what vector, find, auto, cout, \<\<, what is all this garbage?". And you would be absolutely right. My use of a concrete programming language is cluttering the presentation and obscuring what I really want to get across. So here's one possible pseudocode implementation of the above, in the spirit of the rule you mention:

```
A[1..4] = [1,3,5,7]
for i = 1 to 4:
   if A[i] == 5:
      print "found 5"

```

The logic behind the algorithm should be much clearer from this description to someone who has never seen C++ or some specific programming language I might have used.
> 2 votes

---
Tags: pseudocode
---


# Question
Title: Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How?
Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log\_2n)$? If so then how?

# Answer
No. $n^{2.999}\log\_2n$ is tighter, for example.
> 2 votes

# Answer
$g(n)$ is an asymptotically tight bound of $f(n)$ if $f(n) = O(g(n))$, but $f(n) ≠ o(g(n))$. In this case, $n^{2.99} \log n = o (n^3)$. For very large n, $n^{0.01}$ grows faster than $\log n$.
> 1 votes

---
Tags: asymptotics, notation
---


title: Inductive approach on Kleene star proof

text:
# Question
Title: Inductive approach on Kleene star proof
I'm having trouble proving the following: If $L\_1$ and $L\_2$ are languages then: $$(L\_1^\*L\_2^\*)^\* = (L\_1\cup L\_2)^\*$$ I could be on the wrong track here, but I figured an inductive approach is a good way?

My approach was this: If I use my notation $L^{(n)} = \lambda+L+L^2+...+L^n$ so that I have a kind of 'partial' Kleene star I start the induction:

1.) Base case $n=0$:

$(L\_1^\*L\_2^\*)^{(0)} = \lambda = (L\_1\cup L\_2)^{(0)}$ and so this works

2.) Assume true for some $n=k\geq0$ such that $(L\_1^\*L\_2^\*)^{(k)} = (L\_1\cup L\_2)^{(k)}$

3.) Now I want to see how $(L\_1^\*L\_2^\*)^{(k+1)}$ evaluates to:

$(L\_1^\*L\_2^\*)^{(k+1)} = (L\_1\cup L\_2)^{(k)}+(L\_1^\*L\_2^\*)^{k+1}$ where I used the inductive hypothesis. I know I should try to see if this RHS can give me the union with a (k+1) but I don't know how to manipulate this anymore. Am I on the wrong track or am I just not seeing the algebra properly?

# Answer
> 1 votes
It looks like you are on the wrong track.

While it is trivially true that $(L\_1^\*L\_2^\*)^{(0)} = \lambda = (L\_1\cup L\_2)^{(0)}$ where $\lambda$ is the language consisting of the empty word, it is more often than not that $(L\_1^\*L\_2^\*)^{(1)}\neq (L\_1\cup L\_2)^{(1)}$. For example, if either $L\_1$ or $L\_2$ has a non-empty words, the left side $(L\_1^\*L\_2^\*)^{(1)}=(L\_1^\*L\_2^\*)^{(1)}\supseteq (L\_1^\*\cup L\_2^\*)$ has infinitely many word. However, if furthermore we let both $L\_1$ and $L\_2$ be finite languages, the right side $(L\_1\cup L\_2)^{(1)}$ is a finite language as well. A concrete counterexample can be given by $L\_1=\\{a\\}$ and $L\_2=\lambda$.

Here is an approach to move forward. Can you prove that for any language $L$, $(L^\*)^\*=L^\*$? The use of that equality is that you can deduce that $(L\_1\cup L\_2)^{\*}=\left((L\_1\cup L\_2)^{\*}\right)^\*$.

Here is another approach that I like. Intuitively, it is easy to "see" the equality $(L\_1^\*L\_2^\*)^\* = (L\_1\cup L\_2)^\*$. Note that A word in $L\_1^\*L\_2^\*$ is some number of words in $L\_1$ followed by some number of words in $L\_2$.

* A word in $(L\_1^\*L\_2^\*)^\*$ is some number of words in $L\_1$ followed by some number of words in $L\_2$, possibly followed by some number of words in $L\_1$ followed by some number of words in $L\_2$, ..., possibly followed by some number of words in $L\_1$ followed by some number of words in $L\_2$. Here "some number of" means zero or more.
* A non-empty word in $(L\_1\cup L\_2)^\*$ is a word in $L\_1$ or $L\_2$, possibly followed by a word in $L\_1$ or $L\_2$, ..., possibly followed by a word in $L\_1$ or $L\_2$.

Can you see how a word in the former language must be a word in the latter language? Can you see how a word in the latter language must be a word in the former language? If you can, try expressing those "how" in rigorous terms. That would be a proof.

---

Here is a related exercise.

> Let $L\_1$ and $L\_2$ be languages such that $L\_1\subset L\_2^\*$ and $L\_2\subset L\_1^\*$. Prove that $L\_1^\*=L\_2^\*$.

---
Tags: formal-languages, kleene-star
---


title: Why is max{n,k}= Ө(n+k)

text:
# Question
Title: Why is max{n,k}= Ө(n+k)
I saw this relationship in my exercise. max{n,k}= Ө(n+k) Could somebody prove it?

# Answer
> 2 votes
Assuming n and k to be non-negative, $n\leq n+k$ and $k\leq n+k$. Hence,$\max(n, k) \in \mathcal{O}(n+k)$. Next, $n+k≤2\max(n,k)$. Hence, $\max(n,k)\in\mathcal{\Omega}(n+k)$.
Hence, we get that $\max(n,k)\in \mathcal{\Theta}(n+k)$.

---
Tags: asymptotics
---


title: Variant of the Knapsack Problem

text:
# Question
Title: Variant of the Knapsack Problem
I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way.

There are 120 items $i$, each with weight $w\_i$ and the value $v\_i$. Each item can be selected only once (or zero times). For each of them one has to chose a quality level ($a$, $b$, $c$, $d$ or $e$).
The higher the level, the higher is its weight and its value. Both are precalculated for all items and stored in matrix.

Now the question is, given a capacity $W$, how to get the optimal levels for each of the items. Since the item set is relatively huge, the aspects of computational complexity might be of special relevant, I guess.

Can you tell me which algorithms can be use for this variant of the knapsack problem? Thanks a lot!

# Answer
> 1 votes
Your basically want to solve a variant of the 0-1 Knapsack problem. Your variant includes the following changes to the standard problem: for each item instead of one set of $\[wi, vi\]$, you have five sets corresponding to each of the quality levels.

Normal 0-1 Knapsack can be solved using dynamic programming in $O(nW)$ time and $O(nW)$ space where $n$ is the number of items and $W$ is the size of the Knapsack.

In your case, the complexity will be $O(nqW)$ time and $O(nqW)$ space where $q$ is the number of quality levels. If $q \<\< n$, then we are back to $O(nW)$ time and $O(nW)$ space.

Refer this handout for a quick brush-up on the actual recurrence relation.

# Answer
> 0 votes
If you set both the values and the weights of each item corresponding to the lowest four levels to $0$, this problem is exactly the standard knapsack problem, so it is no easier than the standard knapsack problem, i.e. it is NP-hard.

You can use the dynamic programming algorithm for the standard knapsack problem to solve this problem, except that you should consider six cases instead of two: the item is not chosen, or its level $a,b,c,d$ or $e$ is chosen, then take the maximum value. The complexity is $O(nmW)$ where $m$ is the number of levels.

---
Tags: algorithms, complexity-theory, knapsack-problems, integer-programming
---


title: Maximizing entropy under constraint

text:
# Question
Title: Maximizing entropy under constraint
How do I prove that entropy is maximal for $P(A\_2) = \cdots = P(A\_n) = (1-a) /(n-1)$ while $P(A\_1) = a$ (a fixed number) and $A\_1,…, A\_n$ is a partition of the sample space?

# Answer
> 0 votes
Suppose that $X$ is a random variable over the set $\\{1,\ldots,n\\}$ satisfying $\Pr\[X=1\] = a$. Let $Y$ be the indicator of the event $X=1$. Then $$ \begin{align\*} H(X) &\stackrel{(1)} = H(Y) + H(X|Y) \\ &\stackrel{(2)}= h(a) + aH(X|Y=1) + (1-a)H(X|Y=0) \\ &\stackrel{(3)}\leq h(a) + (1-a) \log (n-1). \end{align\*} $$ Here (1) is the chain rule (using $H(X) = H(X,Y)$, since $Y$ is determined by $X$), (2) follows from $\Pr\[Y=1\]=a$ and the definition of $H(X|Y)$, and (3) follows from $H(X|Y=1) = 0$ (since when $Y=1$ we have $X=1$) and $H(X|Y=0) \leq \log (n-1)$ (since when $Y=0$, the r.v. $X$ only attains the values $2,\ldots,n$).

Furthermore, assuming $a \neq 1$, equality holds only if $X|Y=0$ is uniform, that is, if $\Pr\[X=i|Y=0\] = 1/(n-1)$ for $2 \leq i \leq n$, or in other words, if $\Pr\[X=i\] = (1-a)/(n-1)$ for $2 \leq i \leq n$.

---
Tags: probability-theory, discrete-mathematics, information-theory, entropy
---


# Question
Title: For each given set choosing either it or its complement such that their union exactly has a given size
Given an integer $k$ and $n$ sets $A\_1,\ldots,A\_n$, denote $U=A\_1\cup A\_2\cup\cdots\cup A\_n$, $A\_i^0=A\_i$ and $A\_i^1=U\backslash A\_i$. The problem asks whether there exists $(b\_1,\ldots, b\_n)\in\\{0,1\\}^n$ such that

$$\left|\bigcup\_{i=1}^nA\_i^{b\_i}\right|=k.$$

Is this problem NP-complete?

# Answer
This problem can be solved in polynomial time.

If $k=|U|$, this problem is exactly another wording for SAT where each clause contains all variables. More precisely, for each element $j\in U$, let $l\_{ij}=b\_i$ if $j\notin A\_i$ while $l\_{ij}=\neg b\_i$ otherwise. The problem is exactly to satisfy the clauses $l\_{1j}\vee l\_{2j}\vee\cdots \vee l\_{nj}$ for all $j$. If all possible clauses are involved in, the answer is certainly NO. Otherwise, without loss of generality, say one missing clause is $b\_1\vee\cdots\vee b\_n$, we can set $b\_1=\cdots=b\_n=0$ to satisfy all other clauses, thus the answer is YES.

If $k\<|U|$, then at least one element should not be included in the union. We can test for each element: if this element is not included in the union, we can determine for each set whether it or its complement should be chosen, then we can see whether their union exactly has size $k$.
> 1 votes

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


# Question
Title: After stereo image rectification, why does the relation between disparity and depth still apply?
The relation between disparity and depth is derived based on the assumption that the two cameras are parallel.

Image rectification does not make this assumption valid.

But I see in many university computer vision lectures, with two rectified images, the depth map is directly calculated. I cannot figure out why.

# Answer
> 1 votes
> Image rectification does not make this assumption valid.

Yes it does!

From the wiki: https://en.wikipedia.org/wiki/Image\_rectification

> Image rectification warps both images such that they appear as if they have been taken with only a horizontal displacement and as a consequence all epipolar lines are horizontal.

The term can be used in an overloaded manner though, by instead implying that projective distortions from the camera are removed. So you have to be careful.

---
Tags: algorithms, computer-vision
---


# Question
Title: Data structure for finding max, inserting and deleting in O(1) and O(n) space
This is an interview question. I need to implement a data structure that supports the following operations:

1. Insertion of an integer in $O(1)$
2. Deletion of an integer (for example, if we call delete(7), then 7 is deleted from the data structure, if the integer 7 exists in it) in $O(1)$.
3. Return maximum integer in the data structure (without deleting it) in $O(1)$.

You can also use up to $O(n)$ space.

I thought of something similar to this question, but here we have $O(\mathrm{log}\ n)$.

Do you know how can we implement these operations in $O(1)$?

**Edit**: forgot important thing - you can assume the numbers that will be inserted are integers in the range $\[0,n\]$.

# Answer
> 5 votes
Suppose we have such data structure. We can find in $O(1)$ the max, delete the max in $O(1)$ and repeat it $n$ times. Hence, we can sort $n$ numbers in $O(n)$. Therefore, constructing such data structure must take $\Omega(n\log(n))$ (like sorting, in general, can't be done better than $n\log(n)$. Hence, you might have some constraint on data). Also, as deleting is in $O(1)$, means it must be found. Hence, Searching and Finding is in $O(1)$.

Therefore, you must know the position of each value (something like counting sort, but with this constraint that $max \<= n$ to take the $O(n)$ space!). Hence, you can act like a counting sort by saving the max value in a variable besides the array, by accepting some constraint on data (not in general).

# Answer
> 0 votes
You can implement first 2 ops easily by creating an array from 0 to max and store counts of added/removed items there. Regarding the maximum....

I think the question is just little tricky. Since max is constant, you can iterate whole array and it would be also in O(1).

---
Tags: algorithms, data-structures, time-complexity, space-complexity, efficiency
---


# Question
Title: Shortest path when allowed to reverse an edge
We're given an unweighted directed graph with vertices $V$ and edges $E$. We're trying to find the shortest path from $s$ to $t$ but we're allowed to travel along up to one edge in the wrong direction.

If we insist on using all edges in the correct direction, we can solve this using BFS algorithm with $O(|V| + |E|)$ complexity. There's a brute-force solution by reversing each edge in turn and using BFS on each resulting graph, but that takes time $O(|V|\\,|E|+|E|^2)$, which is rather inefficient. Is there a faster solution? I Googled and couldn't find something similar, thanks for your attention and help.

I cannot provide any source URL, because it seems that it is a an example of "oral folk arts".

# Answer
This is one of a class of similar problems which can all be handled by deriving a graph $G' = (V', E')$ from the original graph $G = (V, E)$ and then using the standard algorithm on $G'$.

Consider that at any point in your search in $G'$ you need the path information you would have at a corresponding point in the search in $G$ plus the knowledge of whether or not you have already used the bonus ability. Therefore what should $V'$ be? And following on from that, what should $E'$ be?
> 4 votes

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


# Question
Title: Why is it that a lambda function requiring multiple input also requires multiple functions?
So I recently discovered lambda calculus and for the most part I understand it. However, one specific part of it that I cannot understand is this:

Let's say we define a very simple function

$$ I := \lambda a.a$$

This is simple to understand, nothing confusing. However, if you add another input I will scratch my head furiously:

$$A := \lambda a.\lambda b.a+b$$

This is confusing to me for at least 2 reasons:

1. Why is it that I cannot define a function with multiple parameters like so:

$$A := \lambda a,b. a+b$$
2. How does the second function returned have access to the first parameter if they can only hold one parameter? Is there a prospective for scope? If so, how does it work?

# Answer
1. You can. It is just not written with comma. Your function would then be written as $$\lambda a b. a+b$$ and this is known as uncurrying. Note that this is still $\lambda a. \lambda b. a+b$ in all sense, but just written differently.
2. The inner function does not need to know about variable $a$. Suppose we evaluate $$(\lambda a b. a+b)\ 2$$ We will get $$\lambda b. 2+b$$ which is a function that adds its argument to the number $2$ and does not need access to the variable $a$. There is no variable $a$ at this point if the function goes through any further evaluations.

---

And to directly answer your question from the title: Because by definition of $\lambda$-expressions, functions (abstractions) are always of $1$ argument. In the case of $\lambda$-calculus, uncurried form is just a writing convention (doesn’t change $\lambda$-expression’s nature). The inner workings stay the same (curried).
> 2 votes

# Answer
One view is that there are no functions of multiple parameters. A function which takes "two parameters" is a function taking a *single* ordered pair. In mathematics, a function $f : A \to B$ has *one* domain $A$ and codomain $B$. While it is possible to speak of functions with multiple domains, it is more customary to think of a multi-variate function $g$ as an ordinary function whose domain is a cartesian product, $g : A \times B \to C$.

So, if you would like to have functions taking two parameters in $\lambda$-calculus, you should not be changing how $\lambda$-abstraction works, but you should rather extend the calculus with ordered pairs (and people do that).

But we do not have to extend the calculus with ordered pairs, because every function of two arguments $A \times B \to C$ can be converted to a function of a single argument $A$ returning a function $B \to C$. This may take some getting used to, but it works perfectly. That is, there is a bijection between functions $A \times B \to C$ and functions $A \to (B \to C)$, where the latter expression is read as "functions taking an argument from $A$ and returning a function from $B$ to $C$". This is known as currying.

The expression $\lambda a . \lambda b . a + b$ should be read as a function taking an argument $a$ and returning the function $\lambda b . a + b$. It is thus an example of a multi-variate function that has been curried to take one argument at a time.
> 6 votes

---
Tags: lambda-calculus
---


# Question
Title: How to deal with character set in regular expression?
In regular expression implemented by language like perl or python, user can write a set of characters like \[123abcd\] or special notation like `\d` to represents digit or `\w` to represents word character. I wonder how they are converted to DFA, since you cannot really create expand edges in alphabet(Unicode).

Take example as: `x(2|\d)*y`. The dfa is generated as the following graph.

Apprently `2|\d` is the same as `\d`, the edge '2' is not necessary since it is contained in '\d'. But DFA cannot realize it.

Is there any way to reduce such kind of redundancy?

It also seems regular expression compression becomes very difficult. If we don't expand `\d` to `0|1|2...|9` E.g. we can hardly say is `\w+` equals `a*\w+b*` or not.

And does those regular expression implemention (e.g. re package in python) consider the redundancy?

# Answer
Theoretically, NFA or RegEx minimization is PSPACE-complete \[1\]

Practically, you can throw as many optimizing features to your online regex visualizer websites as current websites do, as long as it does not consume all your server's resources.

\[1\] Minimizing nfa’s and regular expressions, Gregor Gramlich,, Georg Schnitger
> 1 votes

# Answer
> Is there any way to reduce such kind of redundancy?

You expand any special notation to their full finite sets of characters.

> It also seems regular expression compression becomes very difficult. If we don't expand \d to 0|1|2...|9 E.g. we can hardly say is \w+ equals a\*\w+b\* or not.

Compare after expansion. Note that after expansion you can always replace groups of edges with their compressed forms after comparison/minimization again.

> And does those regular expression implemention (e.g. re package in python) consider the redundancy?

This is not a computer science question. Check their source code.
> 0 votes

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


# Question
Title: Are hash functions really quantum resistant for commitment schemes?
It is commonly stated that hash functions remain secure in a post quantum world, the justification being that a quantum computer only has the advantage of Grover's search to give it a quadratic speedup.

However, there is active research into, for example, commitments such as https://eprint.iacr.org/2015/361.pdf. These state that in a quantum setting (whatever that means), the old way of doing commitments by requiring collision resistance doesn't work.

My understanding (possibly wrong) is that one cannot implement a hash function with quantum operators and gates because the quantum operators are unitary and therefore the hash function becomes invertible. The classical hash function uses compression to lose information and is hence, non-invertible. Is there then a possibility that if we attempted a quantum implementation of SHA-2, that would end up showing us how to break it?

Consider $x \rightarrow y = H(x)$. If I have an implementation of $H$ with quantum gates, I could take any $y$, put the remaining registers into whatever state I want (corresponding to the lost information) and then invert to obtain a valid $x$. My only assumption here is that I implemented the quantum $H$ but I can't see why this is forbidden, or even difficult.

# Answer
No. I can see how that sounds like it could work, but it doesn't actually work. You're missing an important detail about how we implement classical functions on a quantum computer. The usual way to implement non-reversible functions with reversible logic is to use ancilla bits (i.e., constant inputs, and junk outputs that are discarded).

For instance, suppose you want to implement the function $f(x,y) = x \land y$ (it computes the boolean AND of its two inputs). You can make this invertible by instead implementing $g(x,y,z) = ((x \land y) \oplus z, x, y)$ (here $\oplus$ denotes XOR). Here $g$ is called a Toffoli gate. Note that $g$ is invertible, even though $f$ is not. Moreover, we can compute $f$ by noting that $g(x,y,0) = (f(x,y,0),x,y)$, so if you want to compute $f$ in a reversible way, you feed in $x$, $y$, and a constant $0$ to $g$, then discard all but the first bit of output. Just because you can invert $g$ doesn't mean you can invert $f$. First, given only $f(x,y)$, we don't know what value to place into the other output bits of $g$. Second, if we made random guesses at those outputs and then inverted $g$, that won't necessarily give us an inverse of $f$ (try it!).

The same is true for SHA2. We know how to implement SHA2 on a quantum computer. It uses ancilla bits. Those ancilla bits prevent you from inverting SHA2 by trying to reverse the quantum computation.
> 3 votes

---
Tags: hash, quantum-computing
---


# Question
Title: Existence of Hamiltonian cycle in a 3-regular $C_n$-free graph
I know that Hamiltonian cycle problem in $3$-regular triangle-free graphs is $NP$-complete. I would like to know how far we can stretch this result. Observing that a triangle is just $C\_3$ cycle, what is the longest fixed-length cycle $C\_g$ such that deciding the existence of Hamiltonian cycle in $3$-regular $C\_g$-free graphs is still $NP$-complete?

# Answer
Have a look at this paper "Not Being (Super)Thin or Solid is Hard: A Study of Grid Hamiltonicity" **Theorem 6.1** states that HCP (Hamiltonian Cycle Problem) for planar graph of maximum degree $3$ and girth $g$ (i.e. $C\_{g-1}$-free) is $NP$-complete, for arbitrary $g\>6$ (i.e. $g\geq 6$ in your notation).

So, in your notation, we are left with the undetermined cases of $g=4,5$.

So if you are willing to relax $3$-regular to $\Delta(G)=3$, then $g$ (actually $g+1$ for the girth value) can be arbitrarily large.
> 1 votes

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


# Question
Title: Prove if a property of a Turing Machine is decidable or not, how can I do it?
I cannot understand how to prove if a certain property of a Turing Machine M is decidable or not.

For example, if a have this:

(1.1) "M always halts within 100 steps"

or this

(1.2) "M recognizes all words with an ‘a’ in them"

what do I do to prove if it's decidable or not? I know I should use reduction or diagonalization, halting problem and so on, but I don't know how to apply them.

Thanks for the help.

# Answer
> 2 votes
To show that a language is decidable, you need to provide a description of a **total** Turing machine, i.e, on all input, the Turing machine should **halt** and accept or **halt** and reject.
Take the example of the first problem, we can build a total Turing machine, that on input $M$(where $M$ is a Turing machine) runs it all inputs of length at most 100. Note that if $M$ halts on all inputs within 100 steps, then it must halt on all inputs of length at most 100 within those many number of steps. If $M$ does so, our constructed Turing machine halts and accepts, else halts and rejects. Since we have to check only on a *finite* number of input strings, the constructed machine always halts and hence is *total*.
As for the second problem, the property of accepting all strings with an 'a' in them is a non-trivial one for recursively enumerable sets($L(M)$ or the language recognized by a Turing machine $M$ is an R.E set) and hence from Rice's theorem, the language of deciding recursively enumerable sets with this very property is undecidable.

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


# Question
Title: Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid
There are two questions that I am trying to draw a comparison between:

```
Q1: Maximum Absolute Difference
You are given an array of N integers, A1, A2 ,…, AN. Return maximum value of f(i, j) for all 1 ≤ i, j ≤ N.
f(i, j) is defined as |A[i] - A[j]| + |i - j|, where |x| denotes absolute value of x.

Q2: Min Steps in Infinite Grid
You are in an infinite 2D grid where you can move in any of the 8 directions :
    (x,y) to
    (x+1, y),
    (x - 1, y),
    (x, y+1),
    (x, y-1),
    (x-1, y-1),
    (x+1,y+1),
    (x-1,y+1),
    (x+1,y-1)

```

I was reading up about the Q2 and I came across this stackoverflow question. Here, the accepted answer reduces this question to `given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance)`

Reading up, I think both these questions are exactly the same except that Q1 is asking for Manhattan Distance in 1D and Q2 is asking for Manhattan Distance in 2D.

I am not very clear about this. Can someone please verify my observation?

# Answer
It is nice that you try to draw a comparison between two similar situations. However, it looks like you are driving too fast to stay on the right road. Henceforth I will be moving somewhat slowly so as to stay on the correct path.

What is generally considered as a distance? You might react, hi, I know what is a distance! Cool then. Here is the widely-agreed general definition of a distance according to Wikipedia as well as my years of practice in math and computer science.

> In mathematics, in particular geometry, a distance function on a given set $M$ is a function $d: M \times M \to R$, where $R$ denotes the set of real numbers, that satisfies the following conditions:
>
> * $d(x,y) ≥ 0$, and $d(x,y) = 0$ if and only if $x = y$. (Distance is positive between two different points, and is zero precisely from a point to itself.)
> * It is symmetric: $d(x,y) = d(y,x)$. (The distance between $x$ and $y$ is the same in either direction.)
> * It satisfies the triangle inequality: $d(x,z) ≤ d(x,y) + d(y,z)$. (The distance between two points is the shortest distance along any path). Such a distance function is known as a metric. Together with the set, it makes up a metric space.

Now let us write out explicitly our distance functions and metric spaces.

1. In Q1, $f$ defines a distance function on all integers from 1 to $N$ such that $f(i,j) = |A\[i\] - A\[j\]| + |i - j|$. All integers from 1 to $N$, together with $f$ forms a metric space, say, $M1$.
2. Let $\Bbb Z^2$ be all the grid points in 2D. Let $d2$ be the minimal steps needed for you to move from point (x,y) to point (p,q), where each step must be one of the eight kind of steps listed. Then $\Bbb Z^2$, together with $d2$ forms a metric space, say, $M2$. Note that $d2((0,0),(0,1))=1$, $d2((0,0),(1,0))=1\\,$ and $d2((0,0),(1,1))=1$.
3. Denote the Manhattan distance by $ma$, i.e., $ma((x,y),(p,q))=|x-p| + |y-q|$. $\Bbb Z^2$, together with $ma$ forms a metric space, say, $MA$. Note that $ma((0,0),(0,1))=1$, $ma((0,0),(1,0))=1\\,$ and $ma((0,0),(1,1))=2$.

Now please follow my observations below.

* $M1$ can be considered as a part of $MA$. Why? Define $e$: $i\mapsto (A(i),i)$. Then you can see that $d1(i,j)=ma(e(i), e(j))$, i.e., the distance between $i$ and $j$ in $M1$ is the same as the distance between $e(i)$ and $e(j)$ in $M2$. You can imagine that $e$ just embeds all integers $1, 2, \cdots, N$ in $M1$ to $MA$, keeping their pairwise distances. This is the simple reason why the accepted answer to Q1 can reduce it to `given a list of points in 2D space (x[i], y[i]), find two farthest points (with respect to Manhattan distance)`.
* $M1$ may or may not be considered as part of $M2$. It depends on how sequence $A$ is defined.
    1. Let $A\_k$ be 0 for all $k$. Then $M1$ is just those 1D integers with their usual Euclidean distance among them. It can be embedded easily into the $M2$, keep their pairwise distances.
    2. Let $A\_1=0$, $A\_2=1$, $A\_3=0$, $A\_4=1$. Then you will find the four integers 1,2,3,4 in $M1$ has pairwise distance 2 except that $d1(1,4)=4$. However, you cannot find that kind of 4 points in $M2$. This particular example shows that your intuition "both these questions are exactly the same" is suspicious.
* The distance in $M2$ is not a Manhattan Distance. You can have 8 points each of which is 1 distance away from any given points in $M2$. For example, $(1,0), (1,1), (0,1), (-1, 1), (-1,0), (-1,-1), (0, -1), (1, -1)$ are 1 distance away from $(0,0)$ in $M2$. However, there is only 4 points each of which is 1 distance away from any given point in $MA$. For example, $(1,0), (0,1), (-1,0), (0, -1)$ are 1 distance away from $(0,0)$ in $MA$. You can also check that $(0,0), (0,1), (1,1)$ is the vertices of an equilateral triangle in $M2$ with side length 1. However, you will not be able to find such an triangle in the Manhattan space $MA$.

---

Hopefully I have cleared all your doubts. Here are a few exercises for you to arrive at a better understanding of the concepts.

Exercise 0. Verify that $d1$, $d2$ and $ma$ are distance functions according to the definition.

Exercise 1. Suppose $A\_1, A\_2, \cdots, A\_n$ is an increasing sequence of integers. Show that $M1$ can be considered a part of $M2$. Show that $M1$ can also be considered as a part of $MA$.

Exercise 2. Find 4 points in $M2$ whose pairwise distance are the same. Show that there is no 4 points in $MA$ whose pairwise distances are the same.

Exercise 3. Given an $m$ by $n$ grid in $M2$ with its bottom left corner $A$ at $(0,0)$ and its upper right corner $B$ at $(m, n)$. $0\le m \le 20$. $0\le n \le 20$. Compute the number of paths starting at $A$ and ending at $B$, where you must always move closer to $B$ along the path.
> 1 votes

---
Tags: arrays, euclidean-distance
---


# Question
Title: Is distinguishing Hadamard matrices _really_ NP-hard?
In a few different places ( http://www.ams.org/journals/mcom/2004-73-246/S0025-5718-03-01539-4/S0025-5718-03-01539-4.pdf and https://books.google.com/books?id=qYYKBwAAQBAJ&pg=PA21&lpg=PA21&dq=np-hard+completing+hadamard+matrix&source=bl&ots=8sKv9bAtc8&sig=ITZSmtD2p2xr6Q4RDqhbQQk0NDI&hl=en&sa=X&ved=2ahUKEwiotuLdvfzdAhWBKHwKHUF9AO0Q6AEwB3oECAMQAQ#v=onepage&q=np-hard%20completing%20hadamard%20matrix&f=false, to give two ) it is claimed that determining the "equivalence" of two Hadamard matrices (in the sense of allowing sign-flips and permutations on rows and columns) is NP-hard. No source I found for this statement provided a citation, and I couldn't find any paper claiming to prove this.

On the other hand, https://core.ac.uk/download/pdf/82725146.pdf provides an $n^{O(\log n)}$ algorithm for identifying equivalent Hadamard matrices. This is somewhat to be expected, since Hadamard matrix equivalence is a lot like graph isomorphism. (It's also not hard to reformulate Hadamard matrix equivalence as a GI problem on $O(n^2)$ vertices directly, leading to a quasipolynomial solution under a variety of well-studied GI algorithms.)

If both of these claims were true, of course, this would be big news and violate the ETH. Is the claim of NP-hardness just a (false) folk theorem?

# Answer
> 6 votes
Both sources you cite are from the same author. Note the full quote:

> For identifying the equivalence of two Hadamard matrices of order $n$, a complete search compares $(2^n n!)^2$ pairs of matrices and is known to be an NP-hard problem when $n$ increases.

I don't think the author knows what NP-hard entails and confuses it with simply exponential. Further evidence of this is that he states that **a complete search** (an algorithm) is NP-hard, when that is a property of a problem, not an approach or algorithm.

This source from a different author similarly misuses the term NP-hard:

> The classification of Hadamard matrices of orders $n \geq 32$ is still remains \[sic\] an open and difficult problem since an algorithmic approach of an exhaustive search is an NP hard problem.

In fact the wording is very similar and found in a field study. It would surprise me if the source of this error wasn't the original paper(s) above being copied without thought.

Since these authors consistently seem to misunderstand the meaning of NP-hard, I think their claims (that come without proof or reference) can be safely dismissed.

---
Tags: np-complete, reference-request, graph-isomorphism
---


# Question
Title: Does Assembly Language depend on an Assembler or the family of processor?
From what I understand, the x86 family of processors understands the same instruction set and x86-32, x86-16 machine code can be executed by an x-86-64 processor because of backwards compatibility.

Now since Machine Code is usually produced from Assembly Language and we use an assembler for that purpose, does that mean that the family of processors doesn't define an Assembly Language but it is rather the Assembler that we use since it actually parses the code?

Let's say I have an Assembly Code like this which is assembled by MASM for an 80386 processor:

```
MOV AX, 5
ADD AX, 10

```

Now assume that this another Assembly Code which is assembled by another hypothetical assembler (lets say HASM) for the same 80386 processor:

```
MOV 5
ADD 10

```

Q1: So for the same processor we can have two different Assembly Code which when assembled using the right assembler can produce the same Machince Code?

Q2: So let's say I have a PC running another family of processor (ARM) and write an Assembly Code and assemble it by MASM which produces machine code compatible for the 80386 processor. Now, without executing, it I copy the machine code over to another PC with the 80386 processor, would the code run Okay?

Q3: If I have two PCs with 80386 processors, one running Windows & the other linux. If I use MASM to assemble a source code on Windows for the 80386 processor, why then, when I copy the machine code over to Linux, it won't execute? Both PCs are running the same processor and machine code is the same! How does OS come into play here? (Please assume no OS specific API function has been used)

# Answer
Q0: \> does that mean that the family of processors doesn't define an Assembly Language but it is rather the Assembler that we use since it actually parses the code?

It's not the processor/family that defines the detailed syntax of the assembly language for a particular CPU - the Assembler program is what defines the assembly language it accepts. You can have two different/incompatible assembly languages for the same processor/family.

Of course the CPU itself will determine what concepts are needed in the assembly language - e.g. 16 registers or 8, of different sizes, etc.

Q1: So for the same processor we can have two different Assembly Code which when assembled using the right assembler can produce the same Machince Code?

Yes. "right assembler"=\>"corresponding assembler"

Q2: So let's say I have a PC running another family of processor (ARM) and write an Assembly Code and assemble it by MASM which produces machine code compatible for the 80386 processor. Now, without executing, it I copy the machine code over to another PC with the 80386 processor, would the code run Okay?

No, because the machine code is processor-/family-specific and you are copying between different processor/family

Q3: If I have two PCs with 80386 processors, one running Windows & the other linux. If I use MASM to assemble a source code on Windows for the 80386 processor, why then, when I copy the machine code over to Linux, it won't execute? Both PCs are running the same processor and machine code is the same! How does OS come into play here? (Please assume no OS specific API function has been used)

At a low level the generated binary code of e.g. an instruction to move a constant into a register is obviously compatible between these two PCs because it is aimed at the same processor/family.

HOWEVER even if it isn't obvious in the assembly code you write, when turned into a binary this is inevitably tightly related to the Operating System - all useful executable programs rely on many Operating System services and these are not the same between your two PCs, so the program won't run in any meaningful way. Maybe it might be possible for the ultra pedantic to come up with a raw binary which could be run on any operating system, but if it's independent of the operating system then it couldn't do anything useful like input or output which is provided by the OS, so while it might prove a point, that point wouldn't actually be very useful.
> 3 votes

# Answer
Assembly language and assembler (assembly language compiler which produces machine code) is necessarily architecture-dependent.

What might still be architecture-independent that you may have in mind is called the CIL (common intermediate language) which is the lowest-level human-readable language.

**Q1**: It may happen to be so for some short assembly code but generally not always so for large, long, complicated assembly program. NASM and MASM have different mnemonic but are able to produce machine code for nearly the same variety of architectures. The produced codes are generally different due to various tricks and tips thrown in.

**Q2**: It is called cross-compiler. You can compile your code on a supercomputer using **top-secret NSA compiler tools** then run it on an 80386 processor.

**Q3**: Surely, you cannot. Linux and Windows have different executable file formats. You can read more about COFF, ELF, Windows .exe files. It is just that OS needs to read the executable file load some codes into RAM.
> 0 votes

---
Tags: computer-architecture
---