# Question
Title: How can you find all unbalanced parens in a string in linear time with constant memory?
I was given the following problem during an interview:

> Gives a string which contains some mixture of parens (not brackets or braces-- only parens) with other alphanumeric characters, identify all parens that have no matching paren.
>
> For example, in the string ")(ab))", indices 0 and 5 contain parens that have no matching paren.

I put forward a working O(n) solution using O(n) memory, using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren.

Afterwards, the interviewer noted that the problem could be solved in linear time with constant memory (as in, no additional memory usage besides what's taken up by the input.)

I asked how and she said something about going through the string once from the left identifying all open parens, and then a second time from the right identifying all close parens....or maybe it was the other way around. I didn't really understand and didn't want to ask her to hand-hold me through it.

Can anyone clarify the solution she suggested?

# Answer
> 17 votes
Since this comes from a programming background and not a theoretical computer science exercise, I assume that it takes $O(1)$ memory to store an index into the string. In theoretical computer science, this would mean using the RAM model; with Turing machines you couldn't do this and you'd need $\Theta(\log(n))$ memory to store an index into a string of length $n$.

You can keep the basic principle of the algorithm that you used. You missed an opportunity for a memory optimization.

> using a stack and going through the string once adding parens to the stack and removing them from the stack whenever I encountered a closing paren and the top of the stack contained an opening paren

So what does this stack contain? It's never going to contain `()` (an opening parenthesis followed by a closing parenthesis), since whenever the `)` appear you pop the `(` instead of pushing the `)`. So the stack is always of the form `)…)(…(` — a bunch of closing parentheses followed by a bunch of opening parentheses.

You don't need a stack to represent this. Just remember the number of closing parentheses and the number of opening parentheses.

If you process the string from left to right, using these two counters, what you have at the end is the number of mismatched closing parentheses and the number of mismatched opening parentheses.

If you want to report the positions of the mismatched parentheses at the end, you'll need to remember the position of each parenthesis. That would require $\Theta(n)$ memory in the worst case. But you don't need to wait until the end to produce output. As soon as you find a mismatched closing parenthesis, you know that it's mismatched, so output it now. And then you aren't going to use the number of mismatched closing parentheses for anything, so just keep a counter of unmatched opening parentheses.

In summary: process the string from left to right. Maintain a counter of unmatched opening parentheses. If you see an opening parenthesis, increment the counter. If you see a closing parenthesis and the counter is nonzero, decrement the counter. If you see a closing parenthesis and the counter is zero, output the current index as a mismatched closing parenthesis.

The final value of the counter is the number of mismatched opening parentheses, but this doesn't give you their position. Notice that the problem is symmetric. To list the positions of mismatched opening parentheses, just run the algorithm in the opposite direction.

Exercise 1: write this down in a formal notation (math, pseudocode or your favorite programming language).

Exercise 2: convince yourself that this is the same algorithm as Apass.Jack, just explained differently.

# Answer
> 8 votes
Since we can just ignore all alphanumeric characters, we will assume the string contains only parentheses from now on. As in the question, there is only one kind of parenthesis, "()".

If we keep removing balanced parentheses until no more balanced parentheses can be removed, all remaining parentheses must look like like "))…)((…(", which are all unbalanced parentheses. This observation suggests that we should find first that turning point, before which we have unbalanced closing parentheses only and after which we have unbalanced opening parentheses only.

Here is the algorithm. In a nutshell, it computes the turning point first. Then it outputs extra closing parenthesis, scanning the string from the start to the right until the turning point. Symmetrically, it outputs extra opening parenthesis, scanning from the end to the left until the turning point.

---

Let `str` be the string as an array of characters, whose size is $n$.

Initialize `turning_point=0, maximum_count=0, count=0`. For each `i` from `0` to `n-1` do the following.

1. If `str[i] = ')'`, add 1 to `count`; otherwise, subtract 1.
2. If `count > maximum_count`, set `turning_point=i` and `maximum_count=count`.

Now `turning_point` is the index of the turning point.

Reset `maximum_count=0, count=0`. For each `i` from `0` to `turning_point` do the following.

1. If `str[i] = ')'`, add 1 to `count`; otherwise, subtract 1.
2. If `count > maximum_count`, set `maximum_count = count`. Output `i` as the index of an unbalanced closing parenthesis.

Reset `maximum_count=0, count=0`. For each `i` from `n-1` to `turning_point+1` downwards do the following.

1. If `str[j] = '('`, add 1 to `count`; otherwise, subtract 1.
2. If `count > maximum_count`, set `maximum_count = count`. Output `i` as the index of an unbalanced opening parenthesis.

---

It is clear that the algorithm runs in $O(n)$ time and $O(1)$ auxiliary memory and $O(u)$ output memory, where $u$ is the number of unbalanced parentheses.

---

**If we analyzed the algorithm above, we will see that, in fact, we do not need to find and use the turning point at all.** The nice observation that all unbalanced closing parentheses happens before all unbalanced opening parentheses can be ignored although interesting.

## Here is code in Python.

Just hit "run" to see several test results.

---

**Exercise 1.** Show that the above algorithm will output a set of parentheses with the least cardinality such that the remaining parentheses are balanced.

**Problem 1.** Can we generalize the algorithm to the case when the string contains two kinds of parentheses such as "()\[\]"? We have to determine how to recognize and treat the new situation, the interleaving case, "(\[)\]".

---
Tags: algorithms
---


# Question
Title: Dijkstra's Algorithm with different color nodes
You are given a directed graph G = (V, E) and nodes s, t. Nodes are colored red, white, and blue. A path from s to t is called colorful if it contains both a red node and a blue node. The task is to determine if a colorful path exists, and if so, find one that contains a minimum number of white nodes.

Im not sure how to get started on this. Any help is greatly appreciated!

# Answer
> 1 votes
Expanding on hengxin's idea, in order to find whether such a path exists, go over all choices of two nodes $x,y$, one red and the other blue, and see if there are paths $s \leadsto x \leadsto y \leadsto t$. In order to find the one containing the minimum number of white nodes, assign weight 1 to edges entering white nodes, and weight 0 to all other edges. The weight of a path is now the number of white nodes. Go over all possible choices of $x,y$, and calculate the minimum-weight path $s\leadsto x\leadsto y\leadsto t$; choose $x,y$ that minimize that weight.

# Answer
> 1 votes
An alternative solution that I believe maintains the same complexity as Dijkstra:

Make a copy $G\_{start}$ of $G$ and connect it to two other copies: $G\_{red\to blue}$ and $G\_{blue\to red}$ such that:

* All red nodes of $G\_{start}$ have a zero cost edge to their equivalent in $G\_{red\to blue}$.
* All blue nodes of $G\_{start}$ have a zero cost edge to their equivalent in $G\_{blue\to red}$.

Then in turn, connect $G\_{red\to blue}$ and $G\_{blue\to red}$ to another copy, $G\_{end}$, such that:

* All blue nodes of $G\_{red\to blue}$ have a zero cost edge to their equivalent in $G\_{end}$.
* All red nodes of $G\_{blue\to red}$ have a zero cost edge to their equivalent in $G\_{end}$.

Now put your start node in $G\_{start}$ and your end node in $G\_{end}$ and apply Dijkstra to the resulting graph. The resulting path will be the shortest path that goes through a red node then a blue node (by going through $G\_{start} \to G\_{red\to blue} \to G\_{end}$), or a blue node then a red node (by going through $G\_{start} \to G\_{blue\to red} \to G\_{end}$).

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


# Question
Title: Is there any implementation of AO* algorithm?
I'm trying to solve And-Or Graph, and I find AO\* algorithm can handle it. Someone said it's already used in AI, but I can't find it in detail.

Have it implemented? Or it's just a pseudocode that can't realized? If it exists, where can I find it? Or any suggestions to help me to implement it? I'm really appreciate your help.

# Answer
I cannot point you towards an existing implementation, but I am pretty confident that it is not too hard to implement yourself. I suggest you to have a look at this paper by Nau, Kumar and Kanal, which has detailed pseudocode for AO\* and other related algorithms such as A\* and branch and bound. In particular, have a look into Section 7 of that paper and the procedures they call P8 and P9.
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to prove $\{ a^ma^lcb^{m+l}\mid m,l \in N \}$ is not regular using the Pumping Lemma?
I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.

Task:
Prove that $M = \left\\{ a^ma^lcb^{m+l}\mid m,l \in N \right\\} $ with $\sum =\left\\{ a,b,c \right\\}$ is not a regular language using the Pumping Lemma.

Here is my try:
First of all I would like to write $M= \left\\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\\} $ as $ M = \left\\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\\} $. Is this possible?

Proof: Let $n\in N$ be fixed. Choose the word $w = { a }^{ 2n }c{ b }^{ 2n }\in M$ with $|w|\ge n$. Let $w=xyz$ be a decomposition with $y\neq \lambda $ and $|xy|\le n$. Then we have $x={ a }^{ 2i }$, $y={ a }^{ 2j }$ and $z={ a }^{ 2n-2i-2j }c{ b }^{ 2n }$ for $j\neq 0$ and $2(i+j)\le 2n$.

We choose $k=0$. Then we have $x{ y }^{ 0 }z = { a }^{ 2n-2i }c{ b }^{ 2n }$. $\Longrightarrow x{ y }^{ 0 }z\notin M$ because $2n-2i\neq 2n$ for $j\neq 0$. $\Longrightarrow$ M is not a regular language.

# Answer
> First of all I would like to write $M= \left\\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\\} $ as $ M = \left\\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\\} $. Is this possible?

We have $a^ma^\ell cb^{m+\ell}=a^{m+\ell}cb^{m+\ell}$ so you can certainly write that as $a^ncb^n$ for some $n\geq 2$. But you can't write it as $a^{2n}cb^{2n}$ because $m+\ell$ isn't necessarily even.

The question originally contained a typo, as follows. I've kept my answer to that version of the question because it illustrates a common mistake, so will probably be useful to somebody.

> First of all I would like to write $M= \left\\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+1 }\mid m,l \in N \right\\} $ as $ M = \left\\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in N \right\\} $. Is this possible?

No, you can't do that. Let $M=\\{a^ma^\ell cb^{m+1}\mid m,\ell\in\mathbb{N}\\}$ and $M'= \\{a^{2n}cb^{2n}\mid n\in\mathbb{N}\\}$. Any $a^{2n}cb^{2n}\in M'$ can be rewritten as $a^{(2n-1)}a^1cb^{(2n-1)+1}\in M$ (i.e., we can set $m=2n-1$ $\ell=1$), so $M'\subseteq M$. However, take $m=2$, $\ell=1$ and we get $a^3cb^3\in M$, but this string is not in $M'$, which means that $M'\neq M$.

You've tried to prove that $M'$ is non-regular but that doesn't prove that $M$ is non-regular. For example, pick your favourite non-regular language $L$ over your favourite alphabet $\Sigma$. $L\subsetneq\Sigma^\*$ but the fact that $L$ is non-regular certainly doesn't mean that $\Sigma^\*$ is non-regular!

> Proof.

Your proof that $M'$ is non-regular is basically correct except for two small mistakes. First, you can't assume that $x$ and $y$ have even length: they need to have length $i$ and $j$, rather than $2i$ and $2j$. Remember that you need to show that *every* partition of the string as $xyz$ fails the pumping property, not just the ones where $x$ and $y$ have some particular property. Second, in your sentences about $xy^0z$, some of the $i$s should be $j$s.
> 1 votes

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


# Question
Title: Using LP to prove the max matching - min cover theorem
Konig's theorem says that, in a bipartite graph, the size of the maximum matching equals the size of the minimum vertex cover. This theorem has several proofs; I would like to know if the following proof, based on primal-dual linear program, is valid. This is mainly an exercise in understanding this primal-dual concept.

**Step 1**: define an LP for the maximum matching. For every edge $(u,v)\in E$, define a variable $z\_{uv}$ whose value is 1 if the edge is in the matching. The LP is:

\begin{align} \text{maximize} && \sum\_{(u,v)\in E} z\_{uv} && \\ \text{subject to} && \sum\_{v\in Y} z\_{uv} \leq 1 && \forall u\in X \\ && \sum\_{u\in X} z\_{uv} \leq 1 && \forall v\in Y \\ && z\_{uv}\geq 0 && \forall (u,v)\in E \end{align}

**Step 2**. Create the dual LP using the recipe:

* Each primal constraint becomes a dual variable - so there is a variable $x\_u$ for each $u\in X$ and a variable $y\_v$ for each $v\in Y$.
* The sign of each dual variable is opposite to the sign of its primal constraint - so $x\_u\geq 0, y\_v\geq 0$.
* The dual objective is minimization, where the coefficient of each dual variable is the number on the right-hand side of its primal constraint - in this case it is always 1. So the objective is "minimize $\sum x\_u + \sum y\_v$".
* Each primal variable becomes a dual constraint. The coefficient of a dual variable in the dual constraint is the coefficient of its primal variable in its primal constraint. In this case, the coefficient of the dual variable of a node $i$, in the dual constraint of the edge $(j,k)$, should be 1 iff $i=j$ or $i=k$.
* The sign of each dual constraint is the sign of its primal variable.
* All in all, the dual LP is:

\begin{align} \text{minimize} && \sum\_{u\in X} x\_u + \sum\_{v\in Y}y\_v && \\ \text{subject to} && x\_u + y\_v \geq 1 && \forall (u,v)\in E \\ && x\_{u}\geq 0, y\_v \geq 0 && \forall u\in X, v\in Y \end{align}

The dual LP finds a minimum vertex cover - it minimizes the number of vertices under the constraint that for each edge, at least one of its endpoints is in the cover.

My question is: is this proof valid?

The main thing I am not sure at is that the LP allows fractional variables, while the original problems are integral. What argument should be added to handle this issue?

# Answer
> 2 votes
Your proof is missing a crucial ingredient, namely that for bipartite graphs, your LPs have the same objective value as the corresponding IPs. This is not true in general (otherwise vertex cover would be in P). You can see a proof for maximum matching in lecture notes of Meena Mahajan, and a proof for both in lecture notes of A. A. Ahmadi.

---
Tags: linear-programming, bipartite-matching, duality
---


# Question
Title: Induction to prove equivalence of a recursive and iterative algorithm for Towers of Hanoi
Using induction how do you prove that two algorithm implementations, one recursive and the other iterative, of the Towers of Hanoi perform identical move operations? The implementations are as follows.

```
Hanoi(n, src, dst, tmp):
  if n > 0
    hanoi(n-1, src, dst, tmp)
    move disk n from src to dst
    hanoi(n-1, tmp, dst, src)

```

And iteratively,

> If n is even, swap pegs 1 and 2. At the ith step, make the only legal move that avoids peg i mod 3. If there is no legal move, then all disks are on peg i mod 3, and the puzzle is solved.

```
 hanoi(n, s, t, d)
  pegs[s = [1,2,..,n], t, d]
  if n is even
    swap pegs[1], pegs[2]
  i <- 1
  while(pegs[d].length < n.length)
    avoid <- i mod 3
    if the top of pegs[(avoid + 1) mod 3] > the top of pegs[(avoid + 2) mod 3]
      move the top of pegs[(avoid + 1) mod 3] to pegs[(avoid + 2) mod 3]
    else
      move the top of pegs[(avoid + 2) mod 3] to pegs[(avoid + 1) mod 3]
    i++

```

I'm having a hard time figuring out how to put this into mathematical expressions or a recurrence-relation which I can then perform induction on to show their equivalence.

My searching has only brought me problems that deal with the complexity or correctness of algorithms, I'm interested in showing that every $i$th move the performed are identical.

# Answer
> 4 votes
Let's start with reformulating the two solutions, following Wikipedia. We use A for the source peg, B for the auxiliary peg, and C for the destination peg.

**Recursive algorithm**

1. If $n \> 1$, recursively move $n-1$ discs from A to B.
2. Move the $n$th disk from A to C.
3. If $n \> 1$, recursively move $n-1$ discs from B to C.

**Iterative algorithm**

If $n$ is even, execute repeatedly until done:

1. Make a legal move between A and B.
2. Make a legal move between A and C.
3. Make a legal move between B and C.

If $n$ is odd, execute repeatedly until done:

1. Make a legal move between A and C.
2. Make a legal move between A and B.
3. Make a legal move between B and C.

(We terminate the algorithms whenever there is no legal move.)

---

We will prove that both algorithms coincide, using the fact that the recursive algorithm makes exactly $2^n-1$ moves, which can easily be proved by induction. The base case is $n = 1$. In this case, the recursive algorithm moves the disk from A to C, and this is also what the iterative algorithm does.

Suppose now that we have proved the claim for $n$. We will prove it for $n+1$. There are two cases to consider, according to the parity of $n$. Suppose first that $n$ is odd.

The first step in the recursive algorithm is to move $n$ discs from A to B. We know that this is the same as running $2^n-1$ steps of the iterative algorithm for odd many disks, with B and C switched. We observe that upon switching B and C, we exactly obtain the iterative algorithm for even many disks. Therefore the first $2^n-1$ moves made by the iterative algorithm coincide with what the recursive algorithm does (this is because at any step there is a move involving one of the first $n$ disks).

Since $2^n-1 \equiv (-1)^n-1 \equiv 1 \pmod{3}$, after executing $2^n-1$ steps, the next step in the iterative algorithm is to make a legal move between A and C, which is exactly what the recursive algorithm does. We can now rephrase the remaining operation of the iterative algorithm as repeatedly executing the following moves:

1. Make a legal move between B and C.
2. Make a legal move between A and B.
3. Make a legal move between A and C.

This is exactly what the iterative algorithm for odd many disks looks like after switching A and B. Therefore just as before, the following $2^n-1$ steps of both algorithms coincide. The same calculation as before shows that the next move to be considered in the iterative algorithm is the one involving A and B, but there are no disks on either of these pegs, so the iterative algorithm stops. This completes the proof for odd $n$.

The proof for even $n$ is very similar. The first $2^n-1$ moves coincide since switching B and C switches the two versions of the iterative algorithm. This time $2^n-1 \equiv 0 \pmod{3}$, so the next move to be considered by the iterative algorithm involves A and C, matching the recursive algorithm. We can rephrase the operation of the iterative algorithm henceforward as repeatedly executing

1. Make a legal move between A and B.
2. Make a legal move between B and C.
3. Make a legal move between A and C.

This is the same as the iterative algorithm for even number of disks with A and B switched, so the following $2^n-1$ moves coincide. The next move to be considered again involves A and B, which is impossible. This completes the proof.

---
Tags: algorithm-analysis, recurrence-relation, recursion, induction, towers-of-hanoi
---


# Question
Title: Proving NP hardness about graph creation problem with triangle number
I have graph creation problem.

Given a set of nodes of graph, and node constraints such as given every node's number of neighbors (degree). I am also provided with the total number of triangles in the graph. Given the above constraints ($n+1$), I have to generate a graph that satisfies all the constraints.

I know that given nodes' degrees, it is possible to construct using Havel–Hakimi algorithm a graph satisfying node degrees. But I am not sure how to fulfill the total triangle count constraint and if it makes the problem NP-hard.

# Answer
This is just a begining of reflexion. I hope it will help. This is not a solution for the very general case but some points that can reduce the problem.

If you consider triangles as unique 3-cliques, you know how many triangles are provided by a k-clique:

* 3-clique : 1 triangle
* 4-clique : 4 triangles
* 5-clique : 10 triangles
* k-clique : C(k, 3) triangles

Thus the number of triangles you have to provide is a combination of these numbers: N = 1\*a + 4\*b + 10\*c ...

You also know that building a clique requires nodes with sufficient neighboors. A k-clique requires k nodes having k-1 edges. And any node with only one edge cannot create any triangle.

On a short example : 10 nodes with (5, 5, 4, 4, 3, 3, 2, 2, 1, 1) edges. A 5-clique is not possible. I think this can do up to 12 triangles with 3 different 4 cliques (5, 5, 4a, 4b), (5, 5, 4a, 3a), (5, 5, 4b, 3b). The remaining (2, 2, 1, 1) cannot provide any triangle.
> 1 votes

---
Tags: graphs, np-complete, np-hard, np, constraint-satisfaction
---


# Question
Title: Which word could I use for the pumping lemma?
I have a problem to start my proof because I do not find a word $w$ where I can use the pumping lemma.

Task:

Be $\sum { =\left\\{ a,b,c \right\\} } $ and $S=\left\\{ bx{ c }^{ m }|x\in { \left\\{ a,b \right\\} }^{ * }\wedge m\in N\wedge { |bx| }\_{ a }-{ |bx| }\_{ b }\>m \right\\} $

Proof with the the pumping lemma, that S is no regular language.

What I know is, that the word has to start we one $b$ following from n times $a$ or $b$ but $w$ needs to have one more $a$ than $b$ in it and $w$ also needs to have one more $b$ than $c$ in it to fulfill the condition. So it has to be something like this $W=b{a}^{2m+2}b^mc^m$? This language is very difficult for me, hope you see more than I.

P.S. Please no complete solutions of the full task.

# Answer
> 1 votes
> So it has to be something like this $w=b{a}^{2m+2}b^mc^m$.

$b{a}^{2m+2}b^mc^m$ is not the general form for $w=bxc^m\in S$. If $x$ must be in the form of $a^\*b^\*$, $w$ will be something like $b{a}^{m+n+k+2}b^nc^m$ for some $n,k\ge0$. Just for completeness, $w$ could be like $baba^{m+1}c^m$ or $baba^{m+1}a^kb^kc^m$ or many other forms. Of course, it is totally fine if you just meant to choose one word so as to apply the pumping lemma.

---

Can you check word $ba^{p+2}c^{p}$, assuming the pumping length is $p$? This word is about as simple as you could get.

---

**Exercise 1.** Assuming the pumping length is $p$, can we pump $ba^{p+3}bc^p\in S$?

**Exercise 2.** Assuming the pumping length is $p$, can we pump $ba^{2p+2}b^pc^p\in S$?

---
Tags: regular-languages, pumping-lemma, proof-assistants
---


# Question
Title: Can you connect an output from a logic gate to 2 or more logic gates or inputs?
I have been given this diagram of a circuit: https://www.google.com/search?q=full+adder+logic+gate&rlz=1C1CHBF\_enCA831CA831&source=lnms&tbm=isch&sa=X&ved=0ahUKEwjCjZzc\_PbfAhXCj4MKHahtCvcQ\_AUIDigB&biw=1536&bih=792#imgrc=GFIqfN5OgCdtRM:

The second XOR gate looks like its output is being connected as inputs of 2 different gates at the same time. Am I interpreting this incorrectly or is it possible to send the a single output to 2 gates simultaneously?

# Answer
> 1 votes
In circuit complexity, the *fan-out* of a gate is the number of gates its output is connected to (similarly, the fan-in is the number of inputs to the gate). A circuit in which all gates have fan-out 1 is known as a *formula*. It is known that some $n$-bit functions can be computed by circuits of size $O(2^n/n)$ but require formulas of size $\Omega(2^n/\log n)$. It is conjectured that polynomial size circuits can compute more functions than polynomial size formulas, but this conjecture, known as the $\mathsf{NC^1} \stackrel?= \mathsf{P}$ question, remains unproved.

---
Tags: logic
---


# Question
Title: Terminology for worst-case N-complexity on $O(1)$ insert after amortisation
Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews nowadays).

For example, when an insertion of an element requires reallocation and copying of the array, increasing the size in two, it is still said that insertion is $O(1)$, not $O(n)$; the worst-case performance is rarely mentioned. Compare this with sorting algorithms, where the worst case could be $O(n^2)$, whereas the average case could be $O(n\log{}n)$, and this is always specified and discussed.

* What is the terminology to express this N-level complexity for the $O(1)$ insertion that requires reallocation with copy of $O(N)$ elements?
* What is the alternative terminology for expressing an optimisation approach, with delayed copy, where the worst-case complexity remains constant-time, provided the operation to allocate new chunk of memory itself is constant. In other words, where you keep both arrays, and do a lazy-copy approach.

Specifically, both of the above could be described as amortisation. But I'm having trouble finding out the absolutely correct terminology for this nuanced problem, as how do you distinguish between these two different scenarios in describing amortisation?!

# Answer
The case, when the operation performs the worst, is commonly called the **worst case**.

The common name for the optimization you mentioned is **de-amortization**.

To denote the fact that operations take $O(1)$ on average, you may say that the time complexity of a single operation is **amortized** $O(1)$.

As far as I know, amortized complexity analysis was first introduced by Robert Tarjan in his “Amortized Computational Complexity”, where you can look up more usages of the term.
> 1 votes

# Answer
Per Dmitri's hint on it being called **de-amortisation**, here's some applicable references on the subject:

* Rao Kosaraju S., Pop M. (1998) **De-amortization of Algorithms**. In: Hsu WL., Kao MY. (eds) Computing and Combinatorics. COCOON 1998. Lecture Notes in Computer Science, vol 1449. Springer, Berlin, Heidelberg

Abstract: De-amortization aims to convert algorithms with excellent overall speed, $f(n)$ for performing n operations, into algorithms that take no more than $O(f(n)/n)$ steps for each operation. The paper reviews several existing techniques for de-amortization of algorithms.

https://rd.springer.com/chapter/10.1007%2F3-540-68535-9\_4

https://doi.org/10.1007/3-540-68535-9\_4
> 1 votes

---
Tags: terminology, asymptotics, notation
---


title: Is ∅ ∈ {{∅}} true?

text:
# Question
Title: Is ∅ ∈ {{∅}} true?
I learned that the empty set is not an element of every set unless the empty set is explicitly included in the set like {∅}, so I believe it is false because it is not ∅ ∈ {∅}.

# Answer
> 2 votes
This is, in fact, false.

Remember, a set contains *only the things directly inside it*. A set of sets does not contain its elements' elements.

So the set $S = \\{\\{\varnothing\\}\\}$ has only one element: $\\{\varnothing\\}$. Since that one element is not $\varnothing$, $\varnothing$ is not in $S$.

Another way to think of it is to rename $\\{\varnothing\\}$ as $\xi$. Now you're wondering if $\varnothing \in \\{\xi\\}$. It should be clear now that the answer is "no".

---
Tags: discrete-mathematics
---


# Question
Title: Why doesn't infinite run time violate Turing completeness? Shouldn't "completeness" include halting?
Why doesn't infinite run time violate Turing completeness? Shouldn't "completeness" include halting?

---

The halting problem:

> The halting problem is a decision problem about properties of computer programs on a fixed **Turing-complete** model of computation
>
> ...
>
> The problem is to determine, given a program and an input to the program, whether the program will eventually halt when run with that input.

---

Now, if one has a language that's Turing-complete, but expresses a program of infinite computation, e.g.

```
while(True): 1;

```

then why is it meaningful to still treat it as being a "Turing-complete" program?

---

Contrast this to the notion of completeness in Banach spaces:

> a real normed vector space $V$ is called **complete if** every Cauchy sequence in **converges** in $V$.

---

However, Wikipedia certainly says that:

> No physical system can have infinite memory, but **if the limitation of finite memory is ignored, most programming languages are otherwise Turing-complete.**

https://en.wikipedia.org/wiki/Turing\_completeness

**However, why is this ignoring reasonable?** Because even when the ignorance might fit Turing's theses, it's not practical, since infinite programs are useless.

# Answer
> 8 votes
You do not yet understand what Turing completeness means.

Turing completeness is the ability to perform arbitrary *finite* computations.

To simplify matters, we say an arbitrary finite computation is an effective procedure that, given some (finite) input, produces some (finite) output, after some (finite number of) steps. To simplify matters further, we assume the output for a given input is the same every time.

That is to say: the effect of a computation is a function from strings (finite sequences of symbols) to strings.

(Not all computations in practice are of this type, but as far as computability is concerned, they can be shown to correspond to a computation of this type.)

So the inputs, the outputs, and the numbers of steps are all finite. However, the set of possible inputs and the set of possible outputs can be infinite.

Such a function is called *computable* if and only if some Turing machine computes it. That is to say, the Turing machine, when started on a tape containing an input to the function, will always terminate with a tape containing the output defined by the function for that input.

It turns out that not all functions from strings to strings are computable.

In particular, not all functions from strings to {"Y", "N"} are computable. These functions effectively say whether a string is a member of a certain set (the function says "Y" if it is, and "N" if it is not).

A set is decidable if some Turing machine computes its "Y"/"N" function. Not all sets are decidable.

A programming language is Turing complete if it can compute all functions that a Turing machine can compute. Amongst other things, this means it can decide any decidable set. Undecidable sets are the ones that no Turing machine can decide. No programming language can decide those sets (says the Church-Turing thesis; I could substantiate this, but this answer is too long already), not even when it is Turing complete.

In short: Turing completeness means a programming language can do everything a Turing machine can do. It doesn't mean it can do things a Turing machine cannot do, such as deciding undecidable sets. No violation is going on here.

# Answer
> 2 votes
Turing completeness is a property of computational machinery/model (e.g. a programming language).

Undecidability is a property of a decision problem (e.g. set membership).

You may not, for some reason, like the usage of word “complete”, but both of the terms we are talking about have clear definitions that don’t rely on each other.
You could think of it as “undecidability” residing in the world above “Turing completeness”, it is a property on input sets to computational models.

Look up the proof for undecidability of the Halting problem and it should be clear that undecidability is inevitable, so there is no such thing as “avoiding Halting problem” with Turing complete models and stronger model has not been invented, probably never will.

# Answer
> 1 votes
"Turing complete" is defined as "able to do everything a Turing machine can do, if you give it enough resources". All modern programming languages are either Turing complete or "effectively" (\*) Turing complete, simply because it's hard to be a useful programming language without that.

In particular, if you have…

* Some basic means of doing arithmetic, like an "increment" instruction
* Some basic means of storing variables
* Some way of checking the value of a variable, and branching based on it
* Some way to make a loop (i.e. branch/jump backward)

…then your language is most likely Turing-complete. It's been shown that the language SUBLEQ, in which the only instruction is "subtract $a$ from $b$, then branch to $c$ if $d \leq 0$", is Turing-complete. Same with the language Brainfuck, which is about as simple as you can possibly go.

For some other examples, it's been shown that *Magic: the Gathering* is Turing-complete. Same with Pokémon Yellow, the Sendmail configuration file, Internet routers, and PowerPoint presentations.

And Turing proved that *for anything Turing-complete*, there are certain problems that can never be solved. The Halting Problem is one of these. That means that, for example, it's possible to get into a situation in a *Magic: the Gathering* game where *whether or not the game ever ends is undecidable*, or to create a Sendmail configuration that can't be proven to ever finish starting up.

In other words, it's really hard to make something that's useful for computation but not Turing complete.

So, what's so special about Turing completeness? It sounds like a pretty weak property, if things like Sendmail config files have it.

The key is…nobody's ever found something *stronger* than Turing completeness. That is, nobody's ever been able to make an algorithm that X fancy new machine can run, but a Turing machine can't. In theory, anything your computer can do, a game of *Magic: the Gathering* can do. Or a PowerPoint presentation, or Conway's Game of Life. Some people claim that human consciousness can do things a Turing machine can't, but even that is questionable: look into the Church-Turing Thesis.

TL;DR: Turing completeness is useful because weaker models aren't very interesting (\**), and stronger models have never been proven to exist.

(\*) C, for example, isn't *technically* Turing complete, because of some lawyerly details in the specification; what it comes down to is, adding more addressable memory makes it a different "implementation", which doesn't count as "the same" language. If you don't care about the fine print, and are happy to call "C with 32-bit pointers" and "C with 64-bit pointers" the same language, then it's Turing-complete.

(\**) Well, this isn't quite true. Finite state automata, pushdown automata, and the like are all very interesting and useful for certain tasks. But they're also very limited, since it's been proven that they can never possibly do certain things that we want to do. For example, a finite state or pushdown automaton can never answer the question "are there the same number of As, Bs, and Cs in this string?"

---
Tags: turing-machines, undecidability, semi-decidability, turing-completeness
---


title: T&PL: Language grammar with terms

text:
# Question
Title: T&PL: Language grammar with terms
I'm autodidacting Pierce's *Types and Programming Languages*. On page 27 he states a definition for "terms, concretely" in constructing a language of terms, thus:

For each natural number $i$, define a set $S\_i$ as follows:

> \begin{align} S\_0 & = \emptyset \\ S\_{i+1} & = \\;\\;\\;\\{true, false, \> 0\\} \\ & \\;\\;\\;\cup \\; \\{succ \\: t\_1, pred \\: t\_1, iszero \\: t\_1\ |\\: \> t\_1 \in S\_i\\} \\ & \\;\\;\\;\cup \\; \\{if\\: t\_1 \\:then \\: t\_2 \\:else \\: \> t\_3\\: |\\; t\_1, t\_2, t\_3 \in S\_i\\} \\ \end{align}
>
> where $succ\\: t$ is the successor of $t$, $pred \\:t$ is the predecessor of $t$ and $iszero \\:t$ tests if $t = 0$. Finally, let
>
> $$S = \bigcup\_i{S\_i}$$
>
> where $S\_0$ is empty; $S\_1$ contains just the constants (I assume $true, false, 0$ is meant); $S\_2$ contains the constants plus the phrases that can be built with constants and just one $succ, pred, \> iszero$ or $if$; $S\_3$ contains these and all phrases that can be built using $succ, pred, iszero$ and $if$ in $S\_2$; and so on. $S$ collects together all the phrases that can be built in this way, i.e., all the phrases built by some finite number of arithmetic and conditional operators, beginning with just constants.

Then as an exercise: *How many elements does $S\_3$ have?* And the answer is (from back of book): $|S\_{i+1}| = {|S\_i|}^3 + |S\_i| \\,\times\\,3+3$, and $|S\_0| = 0$. So $|S\_3| = 59439.$

I really get lost when he says what $S\_1$ and $S\_2$ are. Anyone who could get me started on what is going on here, or could point me to another treatment of these ideas would be appreciated.

# Answer
$S\_0$ is the empty set.

Let $i=0$. $$\begin{align} S\_1= S\_{0+1} & = \\;\\;\\;\\{true, false, 0\\} \\ & \\;\\;\\;\cup \\; \\{succ \\: t\_1, pred \\: t\_1, iszero \\: t\_1\ |\\: t\_1 \in S\_0\\} \\ & \\;\\;\\;\cup \\; \\{if\\: t\_1 \\:then \\: t\_2 \\:else \\: t\_3\\: |\\; t\_1, t\_2, t\_3 \in S\_0\\} \\ & = \\;\\;\\;\\{true, false, 0\\} \\ & \\;\\;\\;\cup \\; \emptyset \\ & \\;\\;\\;\cup \\; \emptyset \\ & = \\;\\;\\;\\{true, false, 0\\} \\ \end{align}$$

So $S\_1$ contains 3 elements.

Let $i=1$. $$\begin{align} S\_2= S\_{1+1} & = \\;\\;\\;\\{true, false, 0\\} \\ & \\;\\;\\;\cup \\; \\{succ \\: t\_1, pred \\: t\_1, iszero \\: t\_1\ |\\: t\_1 \in S\_1\\} \\ & \\;\\;\\;\cup \\; \\{if\\: t\_1 \\:then \\: t\_2 \\:else \\: t\_3\\: |\\; t\_1, t\_2, t\_3 \in S\_1\\} \\ & = \\;\\;\\;\\{true, false, 0\\} \\ & \\;\\;\\;\cup \\; \\{succ \\: true, pred \\: true, iszero \\: true, \\ &\quad\quad\\;\\;succ \\: false, pred \\: false, iszero \\: false, \\ &\quad\quad\\;\\;succ \\: 0, pred \\: 0, iszero \\: 0\\} \\ & \\;\\;\\;\cup \\; \\{if\\: true \\:then \\: true \\:else \\: true,\\ &\quad\quad\\;\\;if\\: true \\:then \\: true \\:else \\: false,\\ &\quad\quad\\;\\;if\\: true \\:then \\: true \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: true \\:then \\: false \\:else \\: true,\\ &\quad\quad\\;\\;if\\: true \\:then \\: false \\:else \\: false,\\ &\quad\quad\\;\\;if\\: true \\:then \\: false \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: true \\:then \\: 0 \\:else \\: true,\\ &\quad\quad\\;\\;if\\: true \\:then \\: 0 \\:else \\: false,\\ &\quad\quad\\;\\;if\\: true \\:then \\: 0 \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: false \\:then \\: true \\:else \\: true,\\ &\quad\quad\\;\\;if\\: false \\:then \\: true \\:else \\: false,\\ &\quad\quad\\;\\;if\\: false \\:then \\: true \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: false \\:then \\: false \\:else \\: true,\\ &\quad\quad\\;\\;if\\: false \\:then \\: false \\:else \\: false,\\ &\quad\quad\\;\\;if\\: false \\:then \\: false \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: false \\:then \\: 0 \\:else \\: true,\\ &\quad\quad\\;\\;if\\: false \\:then \\: 0 \\:else \\: false,\\ &\quad\quad\\;\\;if\\: false \\:then \\: 0 \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: true \\:else \\: true,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: true \\:else \\: false,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: true \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: false \\:else \\: true,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: false \\:else \\: false,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: false \\:else \\: 0,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: 0 \\:else \\: true,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: 0 \\:else \\: false,\\ &\quad\quad\\;\\;if\\: 0 \\:then \\: 0 \\:else \\: 0\\} \end{align}$$

So $S\_2$ contains 3+9+27= 39 elements.

Let $i= 2$, we will get $S\_3=S\_{2+1}=\cdots$, which contains 3+39\*3+39^3=59439 elements.

---

You are supposed to get lost in case you want to find the **meaning** or the **semantics** of the elements in $S\_1$ and $S\_2$, because there is no meaning attached to those elements yet at this stage of the book. In other words, although you, I suspect, **have understood** all that are supposed to be understood, you do not feel or know that you have. Be relaxed, this introductory book is not supposed to be difficult here.

At this stage of the book, $S\_0, S\_1, S\_2, \cdots$ are just sets of words over the alphabet $\Sigma=\\{ true, false, 0, succ, pred, iszero, if, then, else \\}$. In fact, *3.2.1 Definition \[Terms, inductively\]* defines the language $\mathcal T$ by the following context-free grammar.

$S\to true \mid false \mid 0$
$S\to succ\ S \mid pred\ S \mid iszero\ S$
$S\to if\ S\ then\ S\ else\ S $

Once again, let me emphasize that there is no meaning to each symbol in the alphabet $\Sigma$. For example, $true$ is just one symbol, which happens to look like "true". It should have worked equally well had we used $asdf$ or $easypeasy$ or $humptydumpty$ instead. It is expected that we will assign meaning or semantics to all symbols in $\Sigma$ and many words in $\mathcal T$; however, that has not been done yet at this stage of the book.

---

To compute $|S\_3|$, we need to prove the formula, $|S\_{i+1}| = {|S\_i|}^3 + |S\_i| \times3+3$, which comes from the following equality, where $\sqcup$ means disjoint union.

\begin{align} S\_{i+1} & = \\;\\;\\;\\{true,\\, false,\\, 0\\} \\ & \\;\\;\\; \sqcup \\, \\{succ \\: t\_1\mid t\_1 \in S\_i\\} \\,\sqcup\\, \\{pred \\: t\_1\mid t\_1 \in S\_i\\} \\; \sqcup \\; \\{iszero \\: t\_1\mid t\_1 \in S\_i\\} \\ & \\;\\;\\;\sqcup \\, \\{if\\: t\_1 \\:then \\: t\_2 \\:else \\: t\_3\\: |\\; t\_1, t\_2, t\_3 \in S\_i\\} \\ \end{align}

Note that it might not be trivial to show the cardinality of the last set $\\{if\\: t\_1 \\:then \\: t\_2 \\:else \\: t\_3\\: |\\; t\_1, t\_2, t\_3 \in S\_i\\}$ is $|S\_i|^3$ for $i\ge2$ in general since we need to show more or less that the grammar above is deterministic. However, the cases of $i=0,1,2$ that are needed for the moment can be easily enumerated.
> 5 votes

---
Tags: type-theory, types-and-programming-languages
---


title: Is it possible that $L=NP$?

text:
# Question
Title: Is it possible that $L=NP$?
According to Wikipedia and other sources, the question whether $L=P$ is an open problem, and of course everyone is familiar with the problem of whether $P=NP$. However, I found absolutely no information online regarding a possible equality between $L$ and $NP$.

Such an equality doesn't directly violate the space-hierarchy theorem or the time-hierarchy theorem, and so I don't have any idea how to disprove it.

# Answer
> 4 votes
The question whether $L = NP$ is an open problem \[1\], so yes, it is possible. However, it is considered unlikely, or in other words, most *believe* that $L \subsetneq P \subsetneq NP \subsetneq PSPACE$, but we only *know* that $L \subsetneq PSPACE$ \[2, 3\].

References:

---
Tags: complexity-theory
---


# Question
Title: What Are the Ideas Behind Variations of the Coin Change Problem?
> Problem: given a set of `n` coins of unique face values, and a value `change`, find number of ways of making change for `change`.

Assuming we can use a denomination more than once, here's the pseudocode I came up with

```
1. NUM-WAYS(denom[], n, change)
2.   dp = [change + 1][n + 1]
3.   for i = 0 to n
4      dp[i][0] = 1
5.   xs = denom.sorted

6.   for i = 1 to change
7.     for j = 1 to n
8.       if xs[j - 1] > i
9.         dp[i][j] = dp[i][j - 1]
10.      else
11.        dp[i][j] = dp[i - xs[j - 1]][j] + dp[i][j - 1]

12.  return dp[change][n]

```

The above algorithm is clear to me. However, if we are only allowed to use a denomination once, then line 11 changes to `dp[i - xs[j - 1]][j - 1] + dp[i][j - 1]`, as if we are not allowed to use the current denomination at all. I'm failing to wrap my head around this. Can you explain this?

Here're some test runs:

```
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
01222
01233

// use once
Change: 3, denominations: [8, 3, 1, 2]
11111
01111
00111
00122

Change: 4, denominations: [3, 1, 2]
1111
0111
0122
0123
0134

// use once
Change: 4, denominations: [3, 1, 2]
1111
0111
0011
0012
0001

```

# Answer
OP here, answering my own question for the greater good of mankind.

Let `dp[i][j]` denote the solution to the `[i,j]`-th subproblem; that is, `dp[i][j]` is the number of ways to make change for the amount `i`, using coins `j` through `n`.

### Coin Change Problem with Repetition

```
dp[i - xs[j - 1]][j] + // 1
    dp[i][j - 1]       // 2

```
1. Use coin `j`, and since there is no constraint on the denominations, solve the smaller subproblem using the same denomination.
2. Don't use coin `j`.

### Coin Change Problem without Repetition

```
dp[i - xs[j - 1]][j - 1] + // 1
    dp[i][j - 1]           // 2

```
1. Use coin `j`, and since we used coin `j` for this subproblem, we can't use it for any other.
2. Don't use coin `j`.
> 1 votes

---
Tags: algorithms, dynamic-programming, coin-change
---


# Question
Title: Expectation for the number of leaf nodes in a randomized tree construction
Consider this procedure for building a tree from $v\_1, v\_2, ..., v\_n$:

* insert $v\_1$
* insert $v\_2$ and connect it to $v\_1$ via a directional edge from $v\_2$ to $v\_1$
* insert $v\_3$ and with a uniform probabiliy connect it to $v\_1$ or $v\_2$
* ...
* insert $v\_n$ and with a uniform porability connect it to $v\_1$ or $v\_2$,... $v\_{n-1}$

The question is what is the expectation for the number of leaf nodes?

# Answer
> 1 votes
I tried to define a random variable $x\_i$ for a node $i$, which is $1$ if it is a leaf node and $0$ otherwise.

Then, I must find $$E(X) = \sum\_i E(x\_i)$$.

If $A\_{ij}$ shows the event that the node $j$ is connected to the node $i$, then I must have $\bar A\_{ij}$, and then $Pr\[x\_i = 1\] = Pr\[\bar A\_{ii+1}\].Pr\[\bar A\_{ii+2} | \bar A\_{ii+1}\]....$

$j$ must be bigger than $i$, pointing to the nodes that arrive after the node $i$. Let $j$ be $i+1$.

$$Pr\[A\_{ij}\] = \frac{1}{j-1}$$ so $$Pr\[\bar A\_{ij}\] = 1- \frac{1}{j-1} = \frac{j-2}{j-1}$$

The reason is that when the node $j$ arrives there are $j-1$ nodes to be attached to. Similarly:

$$Pr\[\bar A\_{ij+1} | \bar A\_{ij}\] = 1 - \frac{1}{j} = \frac{j-1}{j}$$

so

$$Pr\[\bar A\_{in} | \bar A\_{ij} \cap \bar A\_{ij+1} ... \cap \bar A\_{in-1} \] = 1- \frac{1}{n-1} = \frac{n-2}{n-1}$$

So, let's multiply them to each other:

$$ Pr\[x\_i = 1\] = \frac{j-2}{j-1} . \frac{j-1}{j} .. \frac{n-2}{n-1} $$

Since the product is telescopic, we have:

$$ Pr\[x\_i = 1\] = \frac{j-2}{n-1} $$

By replacing $j$ with $i+1$:

$$ E(x\_i) = Pr\[x\_i = 1\] = \frac{i-1}{n-1}$$

So $$ E(X) = \sum\_{i=1}^{n}E(x\_i) = \sum\_{i=1}^{n}\frac{i-1}{n-1} = \frac{1}{n-1}\frac{n(n-1)}{2} = \frac{n}{2}$$

---
Tags: algorithms, probability-theory, randomized-algorithms
---


# Question
Title: Why Church-encoded types aren't sufficient to express inductive proofs?
I've heard some claims that the calculus of constructions without inductive types isn't powerful enough to express proofs by induction. Is that correct? If so, why isn't the Church-encoding sufficient for that?

# Answer
How would you *prove* inside the pure CoC that the induction principle holds of the Church numerals? See Thomas Streicher's, Independence of the induction principle and the axiom of choice in the pure calculus of constructions.
> 5 votes

# Answer
There is a result recently published within Annals of Pure and Applied Logic in which church encoded data are realizers of their own induction principle. In this system, the induction principle for natural numbers, trees, lists... are derivable. The core calculus doesn't have any datatype constructors packaged in. It starts at an extrinsic (curry style) System F adding 3 typing constructs: implicit product, heterogeneous equality, and dependent intersection.

Geuvers result does not apply to this calculus and is mentioned in the paper.

paper: "From Realizability to Induction via Dependent Intersection", by Aaron Stump
> 1 votes

---
Tags: proof-techniques, functional-programming, automated-theorem-proving, curry-howard
---


# Question
Title: How to generate a grammer from this language?
I'm trying to generate a grammar from this language:

```
L={a^i b^j c^k d^l :  i+j=k+l}

```

to be clear its a in the power of i and b in the power of j... and so on, so that i+j will equal k+l, I would love an explanation how to get to the solution as well, thank you!

# Answer
Start with $i+j=k+\ell$. If $i\ge \ell$, say $=\ell+m$, then also $k=j+m$ and we can write strings in the form $a^\ell a^m b^j c^j c^m d^\ell$. Those can be generated by a grammar, you can use the basic toolbox.

Similarly when $i\le \ell$.
> 0 votes

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


# Question
Title: Superposition calculus: Elimination of redundant atoms
Bachmair and Ganzinger (1991), 'Rewrite-Based Equational Theorem Proving With Selection and Simplification', section 5.2, 'Simplification and Deletion Techniques', page 17, 'Elimination of redundant atoms', discusses the question of when, having used one clause to derive another, you can throw away the first clause instead of ending up with both. As discussed in Redundancy elimination in the superposition calculus you cannot do this in the general case, but you can do it in some particular cases, such as when discarding tautologies or subsumed clauses.

"Let C = Γ, u ≈ v → ∆ be a clause in N. If N |= Γ → u ≈ v, ∆, then N |= Γ → ∆, so that C can be simplified to Γ → ∆. A particular case is the elimination of multiple occurrences of atoms in the antecedent. For example, if C = Γ, u ≈ v, u ≈ v → ∆, then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology and hence trivially implied by N. Redundant atoms in the succedent can be eliminated in a similar way."

Hang on. "elimination of multiple occurrences of atoms in the antecedent", "Redundant atoms in the succedent can be eliminated" - it would certainly be nice if you could do this, but as I understand it, as discussed in https://stackoverflow.com/questions/29164610/why-are-clauses-multisets you have to treat clauses as multisets, not sets, you cannot just throw away multiple occurrences of the same atom. What am I missing?

And "then the clause Γ, u ≈ v → u ≈ v, ∆ is a tautology" - as I understand it, this is true, a clause which contains both an item and its negation is indeed a tautology and you really can promptly discard tautologies, but what does that have to do with multiple occurrences of the same atom with the same polarity? How is that sentence connected to the rest of the paragraph?

# Answer
This one seems to be a case of a not very careful choice of notation in this paper.

So we have a clause $C = \Gamma, u\approx v, u\approx v \to \Delta$ in $\mathcal{N}$.

We could use the simplification rule as follows. Let $\Gamma\_1 = \Gamma, u\approx v$. Then the following two conditions hold:

1. $C = \Gamma\_1, u\approx v \to \Delta$ in $\mathcal{N}$
2. $\Gamma\_1 \to u\approx v, \Delta$ is a tautology therefore it can be added to $\mathcal{N}$ without loss of soundness.

Now applying the simplification rule we can replace $C$ with $\Gamma\_1\to \Delta$. From the definition of $\Gamma\_1$ we have replaced $C$ with the clause $\Gamma, u\approx v\to\Delta$. Effectively the second occurrence of the atom $u\approx v$ has been removed.

They also claim that the same procedure works for removing of multiple occurrences in the succedent.

Also note that this is not specific to equational theorem proving and applies to any atoms.
> 2 votes

---
Tags: logic, first-order-logic, automated-theorem-proving
---


# Question
Title: Effective Procedures and P vs NP Problem
If, suppose, P doesn't equal NP. Implication of this statement is that there is no effective procedure to solve a hard problem; however there exists an acceptable solution S. I have following two explicit queries:

1. If an effective procedure cannot be given which yields a solution, in what sense is the S actually a *solution*? Does this defy the formal definition of solution? I am assuming that an effective procedure is equivalent to a proof.
2. If there is no effective procedure to arrive at an accepted solution, this implies that solution is not a syntactic consequence of problem. According to formal definition, syntactic consequence is equivalent to an effective procedure. If solution to a hard problem is not a syntactic consequence of problem, what is it?

# Answer
> 1 votes
No. $\mathrm{P}\neq\mathrm{NP}$ means that there is no *efficient* (i.e., deterministic polynomial time) solution to $\mathrm{NP}$-hard problems, not that there is no effective (i.e., computable) solution. The fact that the solution is hard to find doesn't mean that it's impossible to find. Indeed, essentially the whole reason that $\mathrm{NP}$ is an interesting class of problems is that we know how to check proposed solutions to $\mathrm{NP}$ efficiently. Regardless of how hard it is to find satisfying assignments to Boolean formulas, if I give you an assignment and tell you that it satisfies the formula, you can easily check that I'm telling the truth.

---
Tags: p-vs-np, formal-methods, mathematical-foundations
---


# Question
Title: NP-hardness does not imply lower bound, strictly speaking?
```
A problem is NP-hard iff every NP problem can be polynomially-time reduced to it.

```

Hardness is often intuitively explained as a lower bound. But it isn't, *strictly speaking*. For the sake of the argument, assume P=NP. Now the definition becomes:

```
A problem is P-hard iff every P problem can be polynomially-time reduced to it.

```

Because the above definition uses the polynomial-time reduction, the overall running time is polynomial (reduction + solving the resulting problem), no matter how easy is the resulting problem. Hence we could get an absurd result: a problem, which runs in constant time (hence lower bound is constant), is P-hard.

The definition makes total sense if we assume that NP\>P. **Do people assume NP\>P?**

The same question arises for the definition of PSPACE-hardness, where book authors use polynomial-time reduction, rather than something strictly easier than PSPACE.

I guess the answer to this question is simply "yes", sorry for the rant.

# Answer
> Hardness is often intuitively explained as a lower bound.

In general, "hardness results" obtained by reductions yield a *conditional* lower bound that relies on assuming a sort of lower bound on a single problem. In the case of NP-hardness, the following statement is true:

> assuming P$\neq$NP, NP-hard problems cannot be solved in polynomial time

P$\neq$NP is equivalent to 3SAT (or any other NP-complete problem) not being solvable in polynomial time, so we can equivalently say

> assuming 3SAT cannot be solved in polynomial time, NP-hard problems cannot be solved in polynomial time

The theory of NP-hardness and the 'belief' P$\neq$NP that has become "common" enough that the required assumption is often not made explicit. Unfortunately, no-one has been able to actually prove the assumption (and almost no-one expects that to happen any time soon)

---

Note that this means that if we can actually prove a lower bound for a single problem, reductions can give an unconditional result. For example, we know that EXPTIME-complete problems cannot be solved in polynomial time. This means that if a problem is EXPTIME-hard, it cannot be solved in polynomial time (without needing any further assumptions!).
> 1 votes

# Answer
Yes, if P = NP then any decision problem is NP hard as long as there is one problem instance where the answer is "YES" and one where the answer is "NO".

Just check the definition of NP-hard (and check why problems where *every* instance has the answer YES or *every* instance has the answer NO are not NP-hard by that definition).
> 1 votes

---
Tags: complexity-theory, reductions, np-hard, complexity-classes
---


# Question
Title: Characterize an OS as multiprogrammed OS
Which of the following features will characterize an OS as multiprogrammed OS?

1. More than one program may be loaded into main memory at the same time.
2. If a program waits for certain event another program is immediately scheduled.
3. If the execution of a program terminates, another program is immediately scheduled.

---

My attempt:

Only, statement (1) is correct, but statement (2) and (3) may not be true when there were no process at ready state. So, they should be false.

But, somewhere it explained as both statement (1) and (2) are true, and (3) is false.

And also, official key is given all statements are correct.

> Can you explain it, please?

# Answer
Sorry That is not a complete answer but i hope it can help you .

"One of the most important aspects of operating systems is the ability to multiprogram. A single program cannot, in general, keep either the CPU or the I/O devices busy at all times. Single users frequently have multiple programs running. Multiprogramming increases CPU utilization by organizing jobs (code and data) so that the CPU always has one to execute. The idea is as follows: The operating system keeps several jobs in memory simultaneously (Figure 1.9). Since, in general, main memory is too small to accommodate all jobs, the jobs are kept initially on the disk in the job pool. This pool consists of all processes residing on disk awaiting allocation of main memory. The set of jobs in memory can be a subset of the jobs kept in the job pool. The operating system picks and begins to execute one of the jobs in memory.**Eventually, the job may have to wait for some task, such as an I/O** **operation, to complete. In a non-multiprogrammed system, the CPU would sit** **idle. In a multiprogrammed system, the operating system simply switches to,** **and executes, another job. When that job needs to wait, the CPU switches to** **another job, and so on. Eventually, the first job finishes waiting and gets the** **CPU back. As long as at least one job needs to execute, the CPU is never idle.** This idea is common in other life situations. A lawyer does not work for only one client at a time, for example. While one case is waiting to go to trial or have papers typed, the lawyer can work on another case. If he has enough clients, the lawyer will never be idle for lack of work. (Idle lawyers tend to become politicians, so there is a certain social value in keeping lawyers busy.) Multiprogrammed systems provide an environment in which the various system resources (for example, CPU, memory, and peripheral devices) are utilized effectively, but they do not provide for user interaction with the computer system. Time sharing (or multitasking) is a logical extension of multiprogramming. In time-sharing systems, the CPU executes multiple jobs by switching among them, but the switches occur so frequently that the users can interact with each program while it is running."

"Time sharing and multiprogramming require that several jobs be kept simultaneously in memory. If several jobs are ready to be brought into memory, and if there is not enough room for all of them, then the system must choose among them. Making this decision involves job scheduling."

'Having several programs in memory at the same time requires some form of memory management'

Operating System Concepts Essentials -Abraham Silberschatz -second edition \[2013\] section \[1.4\]
> 3 votes

# Answer
Your textbook is correct. The definition of a *multiprogramming* system is one in which more than one program can be loaded into main memory simultaneously, and the operating system can improve cpu utilization by switching between programs when the program that has been using the cpu waits for an event such as I/O.

The reason you need both halves of the definition is that the objective of multiprogramming is to maximize utilization of the cpu, which was the most expensive component back in the 1960s when the term first came into use.

The program you are switching to needs to be in main memory, because you are trying to cover up I/O delay. If the program you were switching to were not in main memory, then you'd need to initiate another (slow) I/O request to get the instructions to the cpu.

On the other hand, if you were *not* switching quickly between programs at the point of an I/O then there would be little point in keeping the second program in (expensive) main memory.

I agree with you that your book is using the term *immediately* rather vaguely. The operation of the scheduler just needs to be much faster than the time to do the I/O operation, not "immediate" or "instantaneous".

I was surprised that I couldn't turn up a particularly good online definition to reference. The wikipedia discussion seems to mainly give motivation, as does @vonbrand's otherwise excellent answer here.
> 1 votes

---
Tags: computer-architecture, operating-systems, memory-management, process-scheduling
---


# Question
Title: Complexity of multiplying two integers of size $n$ and $m$
The multiplication of two integers of size $n$ can be done in time $O(n \cdot \log n \cdot \log\log n)$ using FFT method.

If the two integers have different sizes $n$ and $m$, does a smaller upper bound using $n$ and $m$ exists ?

# Answer
> 1 votes
The multiplication of two integers of size $n$ and size $m$ in base-2 with $n\le m$ can be done in time $$O(m\cdot\log n\cdot\log\log n)$$ where the product will be given in base-2 as well.

Here is a sketch of the simple idea to prove the above claim.

---

Let positive integer $a$ has $n$ digits and positive integer $b$ have $m$ digits in base 2. For simplicity, let $m=kn$ for some integer $k$. $$b=\sum\_{i=0}^{k-1}\sum\_{j=0}^{n-1}b\_{i,j}2^{in+j}=\sum\_{i=0}^{k-1}2^{in}b\_i$$ where $0\le b\_{i,j}\le1$, $b\_i=\sum\_{j=0}^{n-1}b\_{i,j}2^j$. In other words, $b\_{k-1}\cdots b\_1b\_0$ is $b$ in base-$2^n$. So $$ab= \sum\_{i=0}^{k-1}2^{in}(ab\_i).$$

Since both $a\_i$ and $b\_i$ have $n$ digits, the product $ab\_i$ can be computed in $O(n\cdot\log n\cdot\log\log n)$ (using FFT method). Multiplying by factor $k=\dfrac mn$, we see that all summands in the above equality and hence $ab$ can be computed in $O(m\cdot\log n\cdot\log\log n)$. Note that the computation cost of various bookkeeping and additions is not substantial enough to invalidate that bound.

---

This idea of splitting the bits of the bigger number by the length of the bits of the smaller number is articulated here first in Yuval's comment. That idea is, apparently, folklore among users experienced in algorithms.

If we have a smaller bound for the multiplication of the integers of the same size, we will get a smaller bound for the multiplication of integers of different sizes accordingly. For example, an algorithm by Harvey and van der Hoeven gives bound $O(n\log n\cdot 2^{2\log ^{\*}n})$. So we will have bound $O(m\log n\cdot 2^{2\log ^{\*}n})$ accordingly.

# Answer
> 0 votes
There is a trivial upper bound O (n * m). If m = o (log n log log n) then this is better than O (n log n log log n).

I think it will be very hard to beat O (max (n\*m, n log n log log n)) for m ≤ n.

PS. Wrong, wrong, wrong: Look at apass.jack's answer. Of course if you have say n = 1,000,000 and m = 100,000 then there isn't much savings.

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


# Question
Title: Is there any relationship between grammar being ambiguous and the language itself?
According to my understanding, a grammar is ambiguous if it generate strings which can be interpreted in more than one ways ( that is , more than one parse tree), but when it comes to the language itself , is there any kind of relationship between the language itself and the ambiguous nature of a particular grammar that could generate it. Also , I am having another doubt , Is it possible that there should exist,infinite number of grammars that could generate the strings of a particular language ?

# Answer
There exist context-free languages which have no unambiguous grammar. Such languages are called "inherently ambiguous".

On the other hand, there is no such thing as a language which does not have an ambiguous grammar; any grammar can be made ambiguous by duplicating some or all of the non-terminals.

The fact that inherently ambiguous languages exist is interesting, but they rarely if ever show up in real-life parsing problems.
> 2 votes

---
Tags: formal-grammars, ambiguity
---


# Question
Title: Shortest common supersequence with Genetic Algorithm
I'm trying to solve the shortest common supersequence with Genetic Algorithm. I found it a little bit hard to reduce the size of the chromosomes in each generation.

I know that the maximum size of the chromosome is the total length of the strings. Even if we create a "naive" genetic algorithm: Totally random strings (with different length) as initial population, mutation that replace a character, fitness that return how much strings that chromosome contains etc. How the crossover can reduce the size of the chromosome length? If we choose n-points crossover, the length of the children cannot be smaller than the shorter parent.

So how genetic algorithm can solve such problems that need the shortest chromosome length? How crossover can reduce the chromosome length?

# Answer
> 1 votes
As is usual, you will really have to think for yourself what makes sense for the crossover function. But here is the naive approach (without really knowing your problem).

Let $s\_1$ and $s\_2$ be the strings you want to find the shortest common supersequence for. Let $\text{superseq}(x, s\_1)$ be the number of characters in $x$ that form a supersequence.

For individuals $x$, $x'$, define

1. **fitness**: $f(x) = \text{length}(x) - \text{superseq}(x, s\_1) - \text{superseq}(x, s\_2)$ (we want to minimize $f$)
2. **mutation**: $m(x) = \hat x$, where we obtain $\hat x$ from $x$ by randomly changing, deleting, or adding a character
3. **crossover**: $c(x, x') = x\[i, j\] + x'\[i', j'\]$ for randomly drawn $i \leq j$, $i' \leq j'$.

In other words, the crossover simply picks a random (consecutive) substring of each of the individuals and concatenates it to make a new. There are many more options, you can pick a string smarter (keeping only certain missing characters), you can interleave the strings, e.g. shuffle the string $\chi = 0^{\text{length(x)}}1^{\text{lenth(x')}}$ and let the result of the crossover be

$$ \left\[ x\[i\] \text{ if } \chi\_i = 0 \text{ else } x'\[i\] \text{ for } i \in \text{range}(\text{length}(\chi) \right\]. $$

---
Tags: genetic-algorithms
---


# Question
Title: Determine Intersection given only a hyperrectangle and a point-contained-in-shape-Predicate
Given only an n-dimensional hyperrectangle by its corner-point-values and an n-dimensional Predicate that corresponds to an arbitrary shape and tests whether a point is contained in said shape,

is it possible to calculate whether the box intersects the shape?

# Answer
If all you have is a black-box function to test containment in your shape $S$, then the answer is no in general. For example, take $n=2$, let your rectangle $R$ have corners $(\pm1,\pm1)$ and let $S$ be a disk. Note that $S$ can have exactly 1 point of intersection with our rectangle and this can be *any* point on the boundary of the rectangle. So, since we work over $\mathbb{R}^2$, we have to test an infinite number of points and hence it is impossible. (obviously, if we have a discretized space, the rectangle has a finite number of points and we can simple test all of those.)

---

So, if you can have an intersection with only 1 point at an infinite number of places, it is impossible. This can happen for a large class of shapes. The first counter-example I can think of is when $S$ is an axis-parallel rectangle with a minimum side-length $w\>0$. $S$ can intersect at one point only in the 4 corners. If $S$ does intersect $R$, but not intersect in a corner $S$ must intersect a segment of length $w$ on the boundary of $R$, so we can test $\approx \frac{4}{w}$ values on the boundary of $R$ to find the intersection.

Note that even in this case, you need $O(\frac{1}{w})$ tests to determine intersections. I think this means that unless you make some strong assumptions about $S$ or relax your condition of intersection, this problem is not solvable.
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Minimal shift operations to sort an array
I have been stuck on this sorting problem for a while now:

Given an array of length N find the minimum number of shift operations in order to sort the array. A shift operation is defined as shifting a value in an array to another position. For this problem however, **you can only perform this shift operation on the first element** in the array.

For example, let's say N = 4 and our array was \[1,2,4,3\].To sort this array we could perform the following shift operations:

\[1,2,4,3\] -\> \[2,4,1,3\] -\> \[4,1,2,3\] -\> \[1,2,3,4\]

Thus, we would have to perform a minimum of 3 shift operations.

Any clues on how to approach this problem?

# Answer
The problem is actually quite simple. When shifting the element at the front, find the last element that is greater than it, and put it after that element.

The number of shifts this takes is $n -k$ where $k$ is the length of the longest increasing suffix of the input.
> 1 votes

---
Tags: sorting
---


# Question
Title: Why theta(n^2) if m=floor(n/2) for Naive String-matching
I’m reading CLRS(Introduction to Algorithm, 3rd edition). In the chapter 32.1 about the naive string-matching algorithm, the book says the worst case running time is $\Theta(n^2)$ if $m = \lfloor \frac n2\rfloor$. I get that when $m$ equals $\frac n2$, but I don’t see it when $m$ is less than $\frac n2$. Any hint or suggestion is very appreciated! m is the length of the pattern string, n is the length of the text to be searched for the pattern. The book uses (n-m+1)m to calculate the running time.

# Answer
Here is the relevant excerpt from *Introduction to Algorithm* by CLRS, 3rd edition.

> Procedure NAIVE-STRING-MATCHER takes time $O(n - m +1)m$, and this bound is tight in the worst case. For example, consider the text string $a^n$ (a string of $n$ a’s) and the pattern $a^m$. For each of the $n-m+1$ possible values of the shift $s$, the implicit loop on line 4 to compare corresponding characters must execute $m$ times to validate the shift. **The worst-case running time is thus $\Theta((n-m+1)m)$, which is $\Theta(n^2)$ if $m=\lfloor n/2\rfloor$.**

Proposition: Let $f(n,m)=\Theta((n-m+1)m)$ be the worst-case running time where $1\le m\le n$. If $m=\lfloor\frac n2\rfloor$, then $f(n,m)=\Theta(n^2)$.

Proof. There are constants $c\_1, c\_2\gt0$ such that for all $1\le m\le n$, $$c\_1((n-m+1)m)\le f(n,m)\le c\_2((n-m+1)m).$$

Now let $m=\lfloor \frac n2\rfloor$. Since $1\le n+1-2\lfloor\frac n2\rfloor\le2$, for $n\ge2$, $$ \begin{align} \frac{n^2}4&\lt\left(\frac{n+1}2\right)^2-1\\ &\le \left(\frac{n+1}2\right)^2-\left(\frac{n+1-2m}2\right)^2=(n-m+1)m\\ &\le\left(\frac{n+1}2\right)^2-\frac14\lt n^2 \end{align}$$ So $$\frac{c\_1}4n^2\lt f(n,m)\lt c\_2 n^2, $$ which says $f(n,m)\in \Theta(n^2)$.
> 2 votes

---
Tags: algorithms, algorithm-analysis
---


title: Maximum flow with constraints

text:
# Question
Title: Maximum flow with constraints
In a flow network, suppose we add constraints of the following type:

> The flow entering a vertex $v$ must be at most the flow exiting a vertex $u$.

Is maximum-flow with such constraints still solvable in polynomial time?

Is it possible to reduce it to a standard maximum-flow problem?

NOTE: I found a recent paper that studies network flow with constraints, however, the constraints studied there are different:

> "A *negative disjunctive constraint* states that a certain pair of arcs cannot be simultaneously used for sending flow"
>
> "A *positive disjunctive constraint* forces that for certain pairs of arcs at least one arc has to carry flow".

# Answer
First a quick note, the flow entering a vertex is equal to the flow leaving. I'll just refer to it as the amount of flow through a vertex.

Second, note that we can say $a \leq b \wedge b \leq a$, thus we can add the constraint $a = b$ for two vertices.

Then we can re-use the NP-hard result from the paper that you quoted:

> "A negative disjunctive constraint states that a certain pair of arcs cannot be simultaneously used for sending flow"

The reduction is done by putting two proxy vertices in the middle of the respective arcs, let's call them $a$ and $b$.

We then also add two vertices $a'$ and $b'$, directly connecting to the source, and add the constraints $a = a'$ and $b = b'$. Finally we add vertex $c$, and connect it to $a'$, $b'$ and the sink. Note that the flow through $c = a' + b' = a + b$.

We finish the reduction by adding constraints $c \leq a$ and $c \leq b$. Now $a+b \leq a$ and $a+b \leq b$ implies that either $a=0$ or $b=0$ (or both).
> 2 votes

---
Tags: optimization, network-flow
---


title: Is it possible to convert LBA into DFA?

text:
# Question
Title: Is it possible to convert LBA into DFA?
Today I learned about an abstract class of machines called linear bounded automata.

It is intended to model real-world computers that have a limited amount of memory. I have always thought that real computers are DFAs due to the finite memory (but the DFA is a terribly poor abstraction).

Is it possible to convert LBA into an equivalent DFA by making every possible tape configuration into a state of the DFA?

# Answer
> 6 votes
No, you can't do this. A single LBA can process inputs of any possible finite length. For any individual input, there are only finitely many possible tape configurations but, over all possible inputs or all possible lengths, there are there are infinitely many possible tape configurations. A finite automaton can't have one state for each of these configurations.

In particular, LBAs can accept non-regular languages, such as $\\{a^nb^n\mid n\geq 0\\}$ so there are LBAs that can't be converted to a single DFA.

What you could do is produce an infinite family of DFAs, one for each possible input length. Each of these would have a finite number of states. However, such an infinite family could recognize any language – even undecidable ones! – because every language contains only finitely many strings of each length and every finite language is regular.

# Answer
> 2 votes
Yes, you just modelled the LBA by a finite state device. You have to decide what are the actions of that model, probably the instructions of the LBA ("in state $q$ on reading $a$ on the tape do ...").

But there is a catch. You have modelled the LBA *together with its input*. That means you will get a different finite state automaton for each input of the LBA. Which is drastically different from DFA: they can accept strings of arbitrary length.

I will not start the discussion whether real computers are finite state automata. Oh boy. That question has been asked: "Are real computers finite state machines?" (and was closed as "unclear what you're asking"), and several times before: "Does our PC work as Turing Machine?". Check the responses there.

---
Tags: finite-automata, linear-bounded-automata
---


# Question
Title: Why a TM with infinite states can decide the halting problem?
Assuming we have a model of TM with an infinite number of states. The domain and range of the transition function are also infinite. Given a description of a TM $M$ and a string $w$ how can we use the new model to tell if $M$ ever stops when running on $w$?

# Answer
> 3 votes
If you are allowed infinite states and transition functions, then even a DFA could solve the halting problem (and in fact, any language). In this case, the DFA/TM can basically have a state for each possible pair of TM + word. If a certain state represents a pair where the TM halts on the word it would be an accepting state.

Notice that I don't give a constructive algorithm of how to build this TM/DFA, but it could easily be seen that such a TM theoretically exists and therefore decides the halting problem.

**EDIT - more detail regarding the last point:** by definition, a language is regular if there exists some DFA accepting it, even if we don't know how to build that DFA. If we allow infinite states, than all languages will be regular. The infinite-state-DFA I described above may seem confusing because we have no idea how to construct it, and in particular, how to choose which states are accepting and which aren't. However, it definitely still exists!

Another way to think about it is that the states of the DFA can be computed/built in "compile-time" and therefore we don't need to figure out whether a TM stops on a word in "run time". We determine what is accepting and what isn't before we even get any input, and when we do get an input, we will definitely halt on it because of the nature of DFAs. We don't need to simulate a TM on an input during the DFAs run!

Lastly, I want to emphasize that the confusion regarding DFAs which we have no algorithm to construct is valid even using the standard, finite-state model of DFAs. If we denote the halting problem by $H\_{TM}$, then for all $n$, the language $H\_n:=H\_{TM}\cap \\{0,1\\}^n$ is a finite language and therefore regular! However, it can be proved that there is no general algorithm that takes $n$ as an input constructs a DFA for $H\_n$, since otherwise we could decide the halting problem.

---
Tags: computability, computation-models, halting-problem
---


# Question
Title: Give a grammar for words whose number of $a$'s modulo 2 is larger than whose number of $b$'s modulo 2
Given is an alphabet $\Sigma = \\{ a, b, c \\}$, and a language $A4 =\\{ w \mid w \in \Sigma^\* \wedge |w|\_a \operatorname{mod} 2 \ge |w|\_b \operatorname{mod} 2 \\}$

whereas $|w|\_a$ is the number $a$'s in the word $w$ and $|w|\_b$ is the number of $b$'s in $w$.

We should give a grammar (of any type) for $A4$.

I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

I can't seem to be able to give a comprehensive grammar for this without breaking that rule. Any tip would be greatly appreciated.

# Answer
> 3 votes
> I know that the only words that do not belong in $A4$ are the words where the number of $b$'s is odd and the number of $a$'s is even.

This characterization of words not in $A4$ is nice. However, what we want is to produce words in $A$. Let us classify the words in $A4$ as the disjoint union of the following 3 pieces.

1. the words where the number of $a$'s is even and the number of $b$'s is even.
2. the words where the number of $a$'s is odd and the number of $b$'s is even.
3. the words where the number of $a$'s is odd and the number of $b$'s is odd.

Now use a distinct nonterminal to represent each piece.

The above hint should be enough to set you moving.

Once you have got your own solution, or you run into another bottleneck, you could mouseover the following to reveal the spoiler.

> To facilitate writing the grammar, we will add a non-terminal to represent the 4-th piece.
> $\quad$4. the words where the number of $a$'s is even and the number of $b$'s is odd.
> Here is the grammar, where non-terminal $S\_{i,j}$ represents the words whose number of $a$'s is $i$ modulo 2 and whose number of $b$'s is $j$ modulo 2.
> $S\to S\_{0,0}\mid S\_{1,0}\mid S\_{1,1}$
> $S\_{0,0}\to cS\_{0,0}\mid aS\_{1,0}\mid bS\_{0,1}\mid\epsilon $
> $S\_{0,1}\to cS\_{0,1}\mid aS\_{1,1}\mid bS\_{0,0}$
> $S\_{1,0}\to cS\_{1,0}\mid aS\_{0,0}\mid bS\_{1,1}$
> $S\_{1,1}\to cS\_{1,1}\mid aS\_{0,1}\mid bS\_{1,0}$

# Answer
> 0 votes
Your language is regular. It contains all words over $\\{a,b,c\\}$ with either an even number of $b$’s or an odd number of $a$’s (or both).

# Answer
> 0 votes
Let S be the start symbol. S represents anything that doesn't have an even number of a's and odd number of b's. Further three symbols: A is not (odd a's and odd b's), B is not (even a's and even b's), C is not (odd a's and even b's).

An empty string is in the language derived from S, A or C, but not B. Therefore we have rules

```
S->eps
A->eps
C->eps

```

c doesn't change anything, so we have rules

```
S->cS
A->cA
B->cB
C->cC

```

a and b change what should come next. Check the following careful, easy to get wrong.

```
S->aA, S->bB
A->aS, A->bC
B->aC, B->bS
C->aB, C->bA

```

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


# Question
Title: Prove that there always exists a line bisecting each of two point sets
A line $\ell$ for a set $S$ of points is *bisecting* if the open halfspaces on either side of $\ell$ contain at most $\frac{|S|}{2}$ points.

Now given point sets $A$ and $B$ in the plane, prove that we can always find a line $\ell$ such that $\ell$ bisects both $A$ and $B$ simultaneously. We can assume that no three points in $A \cup B$ lie on a line and no two points share an x-coordinate.

Note that I am not asking for an algorithm separating $A$ and $B$.

---

So far I have proven the following claim:

> Let $S$ be a point set in the plane containing an even number of points. Prove that, for any point $s \in S$, a bisecting line $\ell$ for $S \setminus \\{s\\}$ also bisects $S$.

From this claim we can also infer that all separting lines for a point set $P$ with an odd number of points must pass through at least one point $p \in P$. However I am stuck on how to continue. Intuition suggests that one of the lines between points $a \in A$ and $b \in B$ must be simultaneously bisecting (if either of $A$ or $B$ contain an even number of points we can just remove one at random by the above claim). However I cannot seem to prove this is always the case.

Can you give me a hint for the next step?

# Answer
> 2 votes
We can prove this using the geometric dual of $P$ and $Q$.

Take the line arrangement of $P^\*$ and $Q^\*$ in the plane and let us look at the median levels $\Lambda\_p$ and $\Lambda\_q$. Their intersection is definitely a possible solution because $\Lambda\_p$ is the point set describing the dual of all bisecting lines for $P$, and vice-versa for $Q$.

Note the following: Since $|P|$ and $|Q|$ are odd, both median line arrangements have the same slope (and since all slopes are unique by assumption, they must correspond to the same lines) in the beginning and the end of the arrangement. Let us denote $p^\*$ and $q^\*$ as the respective lines. Then at the beginning (i.e. the largest x-value where no intersections occured yet), one must be above the other and at the end (i.e. the smallest x-value such that no intersections happen from now on forward), they must have switched places.

Since the levels $\Lambda\_p$ and $\Lambda\_q$ are piecewise continuous (actually even continuously extensible), by the intermediate value theorem they must intersect in at least one point $c^\*$, which is the dual of a possible simultaneously bisecting line $c$.

---
Tags: computational-geometry
---


# Question
Title: What should we return when pattern matching on a Path constructor?
Context: Cubical Type Theory

Consider a simple HIT, say, an `HitInt`:

```
data HitInt : Set where
  pos : (n : ℕ) → HitInt
  neg : (n : ℕ) → HitInt
  posneg : pos 0 ≡ neg 0

```

Or, if you don't speak Agda we can use cubicaltt:

```
data int = pos (n : nat)
         | neg (n : nat)
         | zeroP <i> [ (i = 0) -> pos zero
                     , (i = 1) -> neg zero ]

```

We want to define, for instance, a `succ` operation for it. As a functional programmer, we want to pattern matching on this HIT. In Agda, it's:

```
sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (neg zero) = pos 1
sucHitInt (neg (suc n)) = neg n
sucHitInt (posneg x) = pos 1

```

Or in cubicaltt:

```
sucInt : int -> int = split
  pos n -> pos (suc n)
  neg n -> sucNat n
    where sucNat : nat -> int = split
            zero -> pos one
            suc n -> neg n
  zeroP @ i -> pos one

```

What I'm interested in is the last case-split of these two pattern matchings. The function is supposed to return the successor of the input integer, but we need to implement something that "finds the successor of the input *Path*".

My question is, how are we supposed to implement this case-split? In the cubicaltt version (taken from the cubicaltt's GitHub repository, examples/integer.ctt), it matches the Path `pos 0 == neg 0` and returns `pos 1` -- say, matches a `Path`, but returns a normal integer. Is this really what we want to do? Why it's not returning a `Path` like `<i> pos 1` (even this is not a member of the higher inductive family)?

What's interesting is that, in Agda it'll fill `pos 1` in the case body when I use Agda's proof-search.

# Answer
> 9 votes
> it matches the `Path pos 0 == neg 0` and returns `pos 1` -- say, matches a Path, but returns a normal integer

My understanding is that it matches *points of path* rather than path itself. This is why the matching is on `posneg x` (where `x : I`) rather than `posneg` itself.

Since paths can be seen as (special) maps from `I`, we can think of HIT constructors as just a special of regular constructors, i.e.

```
  posneg : I ↝ HitInt [i0 ↦ pos 0 ; i1 ↦ neg 0]

```

where if you ignore "special" properties of `Interval`, it looks like a regular constructor (in cubicaltt notation it already looks similar except that `I` is always treated specially).

> What's interesting is that, in Agda it'll fill pos 1 in the case body when I use Agda's proof-search.

It's the only way to satisfy constraints imposed by previous definitions (this works for both zero cases). In fact, Agda can correctly solve even two holes (in right order):

```
sucHitInt : HitInt → HitInt
sucHitInt (pos n) = pos (suc n)
sucHitInt (posneg i) = {!!}
sucHitInt (neg zero) = {!!}
sucHitInt (neg (suc n)) = neg n

```

> Why it's not returning a Path like pos 1 (even this is not a member of the higher inductive family)?

Again, since we're matching on points rather than paths; for symmetry it's possible to imagine that case as equal to:

```
sucHitInt (posneg i) = (λ _ → pos 1) i

```

reading somewhat like "for all projections from `I` at `i` to path `posneg` we have projections from `I` at I to constant path `(λ _ → pos 1)`". This doesn't quite work in Agda (because typecheking lambda application directly isn't very well supported), however the following (with the same meaning) does:

```
sucHitInt (posneg i) = refl {x = pos 1} i

```

Finally, abusing notation, we could rewrite that as

```
(ap sucHitInt posneg) i = (refl {x = pos 1}) i

```

(where `ap` (from the HoTT book) corresponds to `cong` in typical Agda) and, getting rid of `i` from the both sides, recover path to path mapping.

PS: i'm new to cubical myself, so hopefully someone can correct or extend my answer

---
Tags: homotopy-type-theory, cubical-type-theory, higher-inductive-types
---


# Question
Title: Complexity of brute force primality test in the number of digits
I'm wondering how to express the complexity of a brute force primality testing algorithm in the number of digits the number under test has. The brute force algorithm just checks whether $n$ is prime by checking if there is a number $k$ from $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ that cleanly divides $n$. How would I go about expressing the complexity of this algorithm in the number of digits $n$ has?

My initial thought would be that in the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$. Is my thought process correct?

# Answer
> 2 votes
> In the worst case we would have to check every number $k$ $2 \leq k \leq \lfloor\sqrt{n}\rfloor$ and $n$ is very close to $10^p$ where $p$ is the amount of digits in $n$. So this would give us at least an upper bound of $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$

You are on the right track. The upper bound $\mathcal{O}(\lfloor\sqrt{10^p}\rfloor)$ is pretty good.

We can simplify the formula a little bit and strength the result a little bit.

**Proposition.** The number of integers between $2$ and $\sqrt n$ (inclusively) is $\Theta(10^{\frac p2})$, where $p$ is the number of digits of $n$ in base 10.

Proof. Since $p$ is the number of digits of $n$ in base 10, we know $10^{p-1}\le n\<10^p$. The number of integers between 2 and $\sqrt n$ is $\lfloor\sqrt n\rfloor-1$. I will leave the rest of the proof to you.

---
Tags: algorithm-analysis, runtime-analysis, primes
---


title: Induction on strings (words)

text:
# Question
Title: Induction on strings (words)
Given is an alphabet $\Sigma = \\{ 0, 1, 2 \\}$ and a function **quer** to calculate the cross sum of a word.

$quer : \Sigma^\*\to \Bbb N$ with:

$$quer(w)=\begin{cases} 0, &\text{when } w=\epsilon\\ quer(v)+x, &\text{when } w=vx, x\in\Sigma \end{cases}$$

Where $\epsilon$ is the empty string.

Prove by Induction on words that $\forall w\in\Sigma^\*$, $quer(w)\le 2\*|w|$.

I can prove that the statement holds for $\epsilon$.

*Base case*: $quer(\epsilon) = 0 \le 2 * |\epsilon| = 0 $

How can I show that the statement holds in the inductive step?

# Answer
> 2 votes
I suppose you are already familiar with the idea behind mathematical induction, but just to recap the general idea, the goal is to use the inductive hypothesis to help us get the desired statement. It is helpful to construct the words in a way that will simplify how you can relate back to the original word.

Suppose it works for all words $v \in \Sigma^\*$ such as $\lvert v \rvert = n$ (we can do this because you proved the base case for words of length 0). Now, take $w = vx$ for any $x \in \Sigma$. Note that the length of $w$ is $\lvert v \rvert + 1$ by construction ($\lvert w \rvert = n + 1$).

$$ quer(w) = quer(vx) = quer(v) + x \leq quer(v) + 2 \\ \leq 2\cdot \lvert v \rvert + 2\\ = 2 \cdot (\lvert w \lvert -1) + 2\\ = 2\lvert w \rvert - 2 + 2 \\ = 2 \lvert w \rvert $$

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


title: Round-Robin fashion exercise

text:
# Question
Title: Round-Robin fashion exercise
In my Operating Systems class I have an exercise to sketch out how a round-robin algorithm would apply to a specific scenario, which is the following:

---

---

Now the correction that I was provided with by the lecturer is the following:

---

---

But I do not understand how this is correct. After referring to the lecture that was given on this specific topic, I understood that Round-Robin maintains a queue with threads and each thread has a time quantum of tens of milliseconds of CPU time. When a thread has exhausted its time quantum CPU time it goes straight to the end of the queue. I also know that, threads that do not full use their time quantum CPU time, will be put in a separated queue, resulting in multilevel queue. After my understanding, this last part is ignored here. Here is the resolution of the exercise that I came up with:

---

---

The "-" stand for executing time, the "v^v^v" stands for blocking time, pretty much like in the correction picture. Note that my version, and the version of the correction match up until the 1st pink dashed line.

Finally, **the question is**: *How come that after the 1st pink dashed line, A is assigned to the CPU? (in the correction version), instead of B, which is, after my understanding, the next process in the queue to be executed(See "Ready queue") in my version of the exercise.*

Please note that there are priorities, but according to the definition of round-robin fashion, priorities are not considered for it(I know that in most OSs the plain vanilla round-robin is not applied, but please ignore that); priorities are there for other parts of the exercise which have nothing to do with this issue.

# Answer
> 1 votes
A round robin scheduler has a fifo queue of processes in state *runnable*. At each time step the scheduler runs the process at the head of the queue for one quantum.

At the end of each time quantum the running process is interrupted and placed at the tail of the queue. If the process blocks (requests i/o) during the time quantum it is typically completely removed from the queue.

The difference between your solution and your instructor's solution is the assumption you are making about what happens when a process's i/o request finishes, and the process again becomes runnable. Your instructor assumes that the process is placed on the tail of the queue. You seem to be assuming that the process is placed at the head of the queue.

Either choice (placing the newly unblocked process at the tail or at the head) is reasonable, but they have different consequences as described by @Gille's answer to a broader question.

If you place the newly unblocked process at the tail of the queue then you maintain the guarantee that no process will ever be *starved*. In practice however, i/o-bound jobs are sometimes given higher priority, both to reduce the latency of those jobs, and to maximize throughput of i/o devices. You could implement this increase in priority by putting newly unblocked processes at the head of the queue instead of the tail, but you would lose your starvation-freeness guarantees.

---
Tags: operating-systems, scheduling, process-scheduling
---


# Question
Title: Intersection of two shortest paths in connected weighted graph
Let $G=(V,E)$ be a connected directed weighted graph with non-negative weights on edges. Let $u,v,s,t$ be vertices in the graph $G$. I need to find an algorithm which in $O(|E|\log |V|)$ time checks if there is a vertex $w$ which lies in the shorthest path from $u$ to $v$ and $s$ to $t$.

My idea is to find a shortest path from $u$ to $v$ using Dijsktra for example, and then for every vertex $w\_i$ in that path check if there is a shortest path from $s$ to $w\_i$ and $w\_i$ to $t$. This can be done in the seeked time using Dijkstra if I am correct. Is my reasoning correct?

# Answer
> My idea is to find a shortest path from $u$ to $v$ ...

As noted by Pål GD, it is not enough to find just one shortest path from $u$ to $v$ as a different shortest path might contain the wanted intersection vertex. We have to take into consideration all shortest paths from $u$ to $v$. Since we are only interested in the vertices, it is enough to find all vertices that are on some shortest path from $u$ to $v$. Denote that set of vertices as $S(u,v)$, where $S$ is the shorthand for both "shortest" and "set".

**Characterization of $S(u,v)$:** Let $d(x,y)$ be the distance between vertex $x$ and $y$. $$x\in S(u,v) \Longleftrightarrow d(u,x)+d(x,v)=d(u,v).$$

It is immediate to prove both "if" and "only if" part.

Here is an wanted algorithm.

Run Dijkstra's algorithm with $u$ as source and with a priority queue such as described at this wikipedia entry to obtain function $d\_u$ such that $d\_u(x)=d(u,x)$ for all $x\in V$ in the form of a look-up table. Similarly, obtain function $d\_v(x)$ such that $d\_v(x)=d(x,v)$ for all $x\in V$ by running Dijkstra's algorithm on $G$ with all edges reversed and $v$ as source. Similarly, obtain $d\_s(x)$ and $d\_t(x)$. For each vertex $x$ in $V$, check whether $d\_u(x)+d\_v(x)=d\_u(v)$ and $d\_s(x)+d\_t(x)=d\_s(t)$. If we find one such vertex, the answer is yes; otherwise, the answer is no.

---

Here are several related exercises.

**Exercise 1.** Prove the correctness of the characterization of $S(u,v)$ as well as the correctness of the algorithm.

**Exercise 2.** Show that the above algorithm runs in $O(|E|\log |V|)$ time when the priority queue of Dijkstra's algorithm is implemented as a self-balancing binary search tree, binary heap, pairing heap, or Fibonacci heap.

**Exercise 3.** For each vertex $u$, let the shortest-path-index $d(u)$ be the number of ordered vertex pairs $(v\_1,v\_2)$ such that $u$ belongs to one of the shortest paths from $v\_1$ to $v\_2$. Let a path-center of $G$ be any vertex whose shortest-path-index is the maximum. Find an efficient algorithm that returns all path-centers.
> 1 votes

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


# Question
Title: Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached
Let G be a graph directed without circles. Suggest a method to find a minimum set of vertices So that all the vertices in the graph can be reached.

I thought to run an SCC algorithm to find binding components and then return them. This is true? Or is there a better algorithm?

# Answer
> 0 votes
Considering the strongly connected component is a good start if graph $G$ may have cycles. However, as implied by Pål GD, every vertex is a strongly connected component of a graph without cycles. We need to do more work to find the minimum set of vertices from which all vertices can be reached.

Here is the outline of an algorithm that does the job.

1. Find one root $r$ of $G$ by repeatedly going to the ancestor of a node. Mark $r$ as an wanted vertex.
2. Remove all vertices reachable from $r$.
3. Go to step 1 unless there is no more vertex.
4. return all vertices that are marked as wanted.

---

**Exercise**. Given a directed graph (that may have cycles), describe an algorithm that finds a minimum set of vertices from which all vertices can be reached. (Hint, strongly connected components are useful now. Try reducing the problem to the current question.)

---
Tags: algorithms, graphs, optimization, dag
---


# Question
Title: Why $\Theta(n^2)$ multiplication of coefficient required for canonical form of polynomial?
I was working through a textbook (*Probability & Computing by Michael Mitzenmacher & Eli Upfal*) and am not able to understand the following:

> Let $F(x)$ be given as a product $F(x) = \prod\_{i=0}^{n} (x - a\_i)$. Transforming $F(x)$ to its canonical form by consecutively multiplying the $i$th monomial with the product of the first $i-1$ monomials requires **$\Theta(n^2)$** multiplications of coefficients.

A canonical form of a polynomial is $\sum\_{i=0}^{n} c\_i x\_i$.

Why does this take $\Theta(n^2)$ time?

# Answer
> 3 votes
Multiplying a degree $d$ polynomial by a degree $1$ monic polynomial requires $d$ multiplications (and some additions). This can be seen from the following formula: $$ (x-c) \sum\_{i=0}^d b\_i x^i = (-cb\_0) x^0 + \sum\_{i=1}^d (b\_{i-1}-cb\_i)x^i + b\_dx^d. $$ If you compute $(x-a\_1)\cdots(x-a\_n)$ by successively multiplying the terms, i.e. by computing $P\_1 = x-a\_1$ and $P\_{d+1} = P\_d(x-a\_{d+1})$ for $1 \leq d \leq n-1$, then you need this many multiplications: $$ 1+2+\cdots+(n-1) = \frac{n(n-1)}{2} = \Theta(n^2). $$

---
Tags: algorithms, runtime-analysis, normal-forms, polynomials
---