title: Successor of 6 is 7 or 9?

text:
# Question
Title: Successor of 6 is 7 or 9?
What is the successor of 6 in this tree: 7 or 9?

# Answer
There are many ways to traverse a tree, and what is the 'successor' of 6 depends entirely on how you are traversing the tree. To illustrate this, here's the answer for some common traversal methods:

**Pre-order traversal**: 3.
**In-order traversal**: 9.
**Post-order traversal**: 17.
**Level-order left-to-right**: 18.
**Lever-order right-to-left**: 20.

And for completeness, you can get 7 as a successor of 6 through **reverse pre-order**.
> 3 votes

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


# Question
Title: Counterexample to this modified Dijkstra's
In class, we were given the following problem:

> We are given a directed graph G = (V, E) on which each edge (u, v) ∈ E has an associated value r(u, v) which is a real number in the range 0 ≤ r(u, v) ≤ 1 that represents the reliability of a communication channel from vertex u to vertex v. We interpret r(u, v) as the probability that the channel from u to v will not fail, and we assume that these probabilities are independent. Give an efficient algorithm to find the most reliable path between two given vertices.

My answer was to run Dijkstra's shortest path algorithm taking (1 / r(u,v) ) as the weight for each edge, which is wrong. The standard solution to this problem is to take the -log(r(u,v)) when running Dijkstra's algorithm. I understand why the standard solution is correct as it exploits the log's property where: log(a\*b) = log(a) + log(b) to convert the problem from maximizing the product to minimizing the sum of the logs. However, what is an example of a graph where taking the inverse of the reliability would not produce the optimal result? My thinking was that any function that maps smaller fractions to bigger numbers could be used.

# Answer
Your algorithm makes the wrong choice between the following two paths:

1. 5 channels with a reliability of 50% (combined reliability 3.125%), weight $5 \cdot {1 \over 0.50} = 10$.
2. A single channel with a reliability of 8%, weight ${1 \over 0.08} = 12.5$.
> 8 votes

# Answer
"Any function that maps smaller fractions to bigger numbers can be used" - This is correct but not what you are doing. What you are assuming is, for positive numbers *a, b, c* and *d*: \begin{equation} a + b \> c + d \implies \frac{a + b}{a \times b} \< \frac{c + d}{c \times d} \end{equation} Which is eqivalent to saying: \begin{equation} \frac{c \times d}{a \times b} \< \frac{c + d}{a + b} \< 1 \end{equation} Which is incorrect. To find counter-examples, you just need to find numbers *a, b, c* and *d*, such that: \begin{equation} a + b \> c + d, \quad a \times b \< c \times d \end{equation} There are many, for instance (9, 2) (5, 5).
Here, \begin{equation} \frac{1}{11} \< \frac{1}{10}, \quad but \quad \frac{1}{9} + \frac{1}{2} \> \frac{1}{5} + \frac{1}{5} \end{equation}
> 2 votes

---
Tags: graphs, greedy-algorithms
---


# Question
Title: Why does the total credit associated with a data structure must be nonnegative at all times for the accounting method?
I was reading CLRS and it said in the chapter for the accounting method (for amortized analysis):

> the total credit associated with the data the structure must be nonnegative at all times.

where total credit is defined as:

> The total credit stored in the data structure is the difference between the total amortized cost and the total cost.

It also mentions the following:

> If we denote the actual cost of the ith operation by $c\_i$ and the amortized cost of the ith operation by $\hat{c}\_i$, we require:
>
> $$ \sum^n\_{i=1} \hat{c}\_i \geq \sum^n\_{i=1} c\_i$$
>
> for all sequences of n operations.

CLRS does provide an explanation of why it requires it but I am not sure I understand it. I will paste its explanation and explain my confusion:

> If we ever were to allow the total credit to become negative (the result of undercharging early operations with the promise of repaying the account later on), then the total amortized costs incurred at that time would be below the total actual costs incurred; for the sequence of operations up to that time, the total amortized cost would not be an upper bound on the total actual cost. Thus, we must take care that the total credit in the data structure never becomes negative.

So this is what I am confused about. When it says it requires $ \sum^n\_{i=1} \hat{c}\_i \geq \sum^n\_{i=1} c\_i$ to hold for all operations, does it implicitly also mean that it requires it for all $n \in \mathbb{N}$? i.e. its for all sequences of $n$ operations for all $n$?

What would be the deal if it didn't hold for all $n$? I tried reasoning this and I think it means that there exists some sequence that overall, is undercharged if we were to stop doing stuff at the end of that sequence. Thus, we wouldn't actually have a valid run-time analysis for this specific sequence of $n$ operations. Right?

I do think that it does mean for all natural numbers $n$ too. The reason I think this is because the way I think of the accounting method is that we have credit for later operations. If it was ever negative it means that some operation on the data structure at some point doesn't have actual enough "prepaid work" for some operation. Is this right or am I missing something?

Is the goal just that at all times for any sequence of any time that we **always** have an upper bound on the cost of $n$ operations? Regardless weather its charging, accounting, potential method etc, the goal is that **always** we have an upper bound on the cost of a sequence of $n$ operations?

So in this line of thought, if we do the potential method with:

$$ \hat{c}\_i = c\_i + \Phi(D\_i) - \Phi(D\_{i-1})$$

then because of the telescoping property, do we require for all sequences of operations that:

$$ \Phi(I\_n) - \Phi(I\_0) \geq 0$$

Since:

$$ \sum^n\_{i=1} \hat{c}\_i = \sum^n\_{i=1} ( c\_i + \Phi(D\_i) + \Phi(D\_{i-1}) ) = \sum^n\_{i=1} c\_i + \Phi(D\_n) - \Phi(D\_{0})$$

since we need: $ \Phi(I\_n) - \Phi(I\_0) \geq 0$

# Answer
> 2 votes
The amortized analysis calculates complexity for a sequence of $ n \in \mathbb{N} $ operations, no matter how large $ n $ is and what is the structure of sequence (i.e. which operations are within the sequence). If you would allow $ \sum\_{i = 1}^{n}{\hat{c\_i}} \< \sum\_{i = 1}^{n}{c\_i} $ for some $ n $ and some sequence of operations, then the same inequality would hold for any multiplication of $ n $. Thus you would not have an upper bound, so no analysis would be possible. This reasoning is for both accounting and potential method.

---
Tags: algorithms, amortized-analysis
---


# Question
Title: How to find what language a PDA accepts?
Given the following PDA describe the language it accepts.

```
Q = { q0, q1, q2 }
Σ = { a, b }
Γ = { A, B }
F = { q1, q2 }
z = B
δ ( q0, a, B ) = { ( q0, AB ) }
δ ( q0, λ, B ) = { ( q1, λ ) }
δ ( q0, b, A ) = { ( q2, λ ) }
δ ( q0, a, A ) = { ( q0, AA ) }
δ ( q2, b, A ) = { ( q2, λ ) }
δ ( q2, λ, A ) = { ( q2, λ ) }
δ ( q2, λ, B ) = { ( q1, λ ) }

```

Answer: { ai bj | 0 ≤ j ≤ i }

Can somebody show me the steps to reach the answer. What general strategy/ steps are used to answer these type of questions?

# Answer
> 0 votes
In the book, *An Introduction to Formal Languages and Automata* by Peter Linz, there is an algorithm to get the grammar accepted by the given pushdown automata. Getting the language from grammar is a very tedious task, and I don't think there is any algorithm for that.

---
Tags: automata, pushdown-automata
---


title: L equivalence classes

text:
# Question
Title: L equivalence classes
Let L be the language consisting of all strings in (a+b)\* that have an even number of letters and do not have aaba as a substring.

Into how many L-equivalence classes is (a+b)\* divided?

# Answer
Construct the minimal DFA for the language L (this can be done by first constructing an NFA and then converting it to DFA because making an NFA is easier).

The number of states in the DFA is the number of equivalence classes the language L can be divided into.
> 1 votes

---
Tags: discrete-mathematics, dfa
---


# Question
Title: Why is the path compression (no rank) for disjoint sets $O(\log n)$ amortized for Find-Set?
I was trying to understand why using only path compression (no rank) would yield $m log(n) $ total run time for a sequence of $m$ operations for Find-Set.

I was told that the potential function:

$$ \Phi(x\_1, ... , x\_n ) = \sum\_i log(w\[x\_i\])$$

would work (where $w\[x\_i\]$ is the weight of the subtree rooted at $x\_i$, i.e. the number of elements in the subtree rooted at $x\_i$).

I was given the following argument but it doesn't quite make sense to me:

I can sort of see why a -1 would come in since $\frac{1}{2} = 2^{-1} \implies log(\frac{1}{2}) = -1$, but re-arranging the equation (and taking logs) gives:

$$ log(w\[c\]) - log(w\[p\]) \leq 1$$

which reverses the sign the wrong way. Plus, if you write down the details of the potential function change, things change inside the logs, which makes it tricky to analyze...

# Answer
A quick note: the runtime is not guaranteed to be $O(m \log n)$. For example, suppose that your forest consists of $\sqrt{n}$ a linked lists, each of which has $\sqrt{n}$ nodes in it. Doing a total of $\sqrt{n}$ finds on the bottom nodes in each list will take time $\Theta(n)$, which means that the bound of $O(m \log n)$ (here, $O(\sqrt{n} \log n)$) is incorrect. A more correct bound would be to claim that the runtime will be $O(m \log n + n)$, which accounts for the "startup cost" of doing some initially-expensive compresses.

Here's one way that you can see the runtime is $O(m \log n + n)$ without using the potential argument you mentioned in your question. Let's begin with an initial disjoint-set forest. We're going to color all the edges in the forest one of three colors: gold, blue, or red. The colors are given as follows:

* Any edge from a node u to a node v, where the number of nodes in u's subtree is less than half the number of nodes in v's subtree, is colored blue.
* Every other edge is red.

To understand blue and red edges, imagine that you're not going from some node up to the root, but from the root down to some node. Every time you follow a blue path, the number of nodes in the current subtree decreases by at least a factor of two. This means that if there are $n$ total nodes in the graph, any path from a node up to its root can have at most $O(\log n)$ blue edges on it, since the number of nodes in the subtree keeps dropping geometrically. That leaves red edges as everything else.

So now imagine that you start doing a find operation beginning at some node. Look at the path that you'll take up to the root. You're going to go through some number of red edges, some number of blue edges, and some number of gold edges. We don't know a priori how many red edges you'll walk through, but we can guarantee that you'll go through at most one gold edge (remember, they have to be directly pointing to the root) and at most $O(\log n)$ blue edges. This means that the cost of performing a find operation is $O(r + \log n)$, where $r$ is the total number of red edges that you pass through.

The reason that this coloring scheme is interesting is that something magic happens when you do a find. Remember, every node on the path is going to have its parent pointer changed to be the ultimate representative in the partition. Imagine that you use the potential function that you described in the question. Every time you follow a red edge (other than one that already points to the root directly), you change the node so that it points directly to the root. This means that its old parent must lose at least half the weight in its tree, which means that $\log\[w\_i\]$ decreases by at least one. No node's weight increases, since we only move edges from descendants up to the root. This means that the drop in potential is at least $r - 1$, where $r$ is the number of red edges followed. Therefore, even though the runtime of any individual find is $O(r + \log n)$, the amortized cost of a single find is $O(\log n)$.

Now, this analysis completely ignores the costs of doing a union operation, and that's important. The good news is that it's not a problem. A union does two finds - each of which cost amortized $O(\log n)$ - and then links one tree to another. This increases the size of the root of that tree by the number of nodes in the linked tree, which is at most $n$. This means that the potential increases by at most $\log n$, so the amortized cost is $O(\log n)$.
> 5 votes

---
Tags: algorithm-analysis, data-structures, amortized-analysis
---


# Question
Title: What is monograph and digraph in keyboard optimization problem?
I have been working on Bangla keyboard optimization. I've taken this paper as a reference. In this paper they have introduce two terms monograph and digraph. But it is not clear how they have calculate these two things. In this paper it is written -

> A monograph is an isolated key which is struck in the process of typing a text. A digraph is a sequence of two consecutive keys hit in the process of typing a text. This idea allows the distinction between rules that concern the absolute position of a given key and the relative position of two consecutive keys.

What I am assuming that digraph is those two consecutive character that are used often in any language word. Like in English language ph, qu etc. But I can not understand what is monograph.

Therefore I would need a clear explanation about monograph and digraph and what is the method to calculate these in respect to keyboard optimization problem.

# Answer
> 1 votes
The article uses `monograph` to refer to a single key, say "e", in a position on the keyboard. In the interest of efficiency, you'd want the frequently-used letters to be in locations where a model typist would have to expend the least motion to strike. A `digraph`, on the other hand, would be two keys which would be struck in sequence, like the "in" which I typed a few characters ago. In this case, we would be looking for a keyboard layout which minimized the effort depending not just on the absolute positions of the characters, but on the relative positions of the pairs.

# Answer
> 0 votes
A monograph is a single letter that was typed at some point.

A digraph is a pair of consecutive letters that were typed one after the other.

For instance, if I type `sock`, the monographs are `s`, `o`, `c`, and `k`; the digraphs are `so`, `oc`, and `ck`.

---
Tags: terminology, optimization
---


title: Reduction from 3SAT

text:
# Question
Title: Reduction from 3SAT
You are given a directed acyclic graph G = (V, E) in which each node has one “left” out-arc and one “right” out-arc, with a distinguished source node s and sink node t. You are also given a list of “ties” (u, v) which say that if you take the left \[right\] edge out of u, then you must also take the left \[right\] edge out of v. Is there a path from s to t subject to the ties? Show that this decision problem is NP-complete.

For this I know we can reduce a 3SAT to a problem of checking whether a path exists or not between 's' and 't'. But I am finding difficult to add the constraints of "ties" into it

# Answer
> 2 votes
Suppose you are given a CNF $C\_1\wedge\dots\wedge C\_k$, with clauses of the form $C\_i = L\_i^1\vee L\_i^2\vee L\_i^3$, each literal $L\_i^j$ being either $x\_i^j$ or $\neg x\_i^j$ for some variable $x\_i^j\in V$. Construct a graph as follows:

* Set of nodes is $N=\\{n\_i^j\ |\ 1\le i\le k, 1\le j\le 3\\}\cup\\{\top,\bot\\}$.
* For all $i,j$: let the "sat" successor be $n\_{i+1}^1$ for $i\<k$, and $\top$ otherwise; let the "unsat" successor be $n\_i^{j+1}$ for $j\<3$, and $\bot$ otherwise. If $L\_i^j=x\_i^j$, the left and right edge from $n\_i^j$ go to the sat and unsat successor, respectively; if $L\_i^j=\neg x\_i^j$, it is the other way around.
* Add ties between all pairs of nodes $(n\_i^j,n\_p^q)$ with $x\_i^j=x\_p^q$.

Then a valuation of the variables in $V$ corresponds exactly to a choice of left or right such that for all nodes belonging to the same variable, the same direction is chosen; a satisfying valuation corresponds to a choice of directions which leads from $s=n\_1^1$ to $t=\top$.

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


# Question
Title: Consensus protocols in multiplayer video games
I'm not 100% sure this appropriate for CS. Sorry.

I'm looking for prior art on an idea I had, but either my Google fu is lacking, or it genuinely hasn't happened.

In distributed systems, there are a number of consensus protocols and implementations (Raft, Paxos, Zookeeper, etc.). There's also the Bitcoin blockchain. Both of these approaches allow the cluster/network system to recover in the face of split brains and sometimes in the face of an evil node.

In the games world, there are really only two architectures in use:

* Client-server, where the server simulates the game and is the source of truth and the clients simply act as a dumb terminal. No cheating possible. (Sometimes the server runs on a client.)
* Peer-to-peer, where all clients broadcast their status to all other clients. Cheating very possible.

I am thinking of a third architecture that enhances the peer-to-peer architecture with a voting-based cheat detection. Desynchronized game state would be rejected by a majority vote. A colluding majority would be required to cheat.

The practical purpose is two-fold:

* To eliminate the necessity of the server-side implementation of game simulation (e.g., game state machine). In the client-server model, you need to either write the implementation of the sim twice or write it generically enough that it will run in both client and server environments. For practical reasons, a shared codebase is difficult to do.
* To eliminate the computational burden of running simulations. For large online games, this burden is not insubstantial.

I'm wondering if there's any research on such a system (either similar systems having been invented and used or even a paper describing it) specifically with respect to multiplayer games.

# Answer
> 4 votes
Section IX of the following paper proposes a variant of your idea:

OpenConflict: preventing real time map hacks in online games. Elie Bursztein, Mike Hamburg, Jocelyn Lagarenne, and Dan Boneh. IEEE Security & Privacy 2011.

The difference is that they propose that detection can be done by the central server, after the fact, by analyzing all of a client's status messages for consistency. Your scheme differs only by having other clients do the same analysis. (Their proposal also has some extra hashing and signatures and cryptography, which can probably be ignored for your purposes.)

Their scheme is basically a more sophisticated version of what you propose: rather than requiring everything to be broadcast, it only has to be uploaded to the server at the end of the game. This has two advantages: (a) it significantly reduces network traffic, because they upload to the server rather than broadcasting to everyone; (b) by using commitments and hashes, they don't have to broadcast the full status messages to all other players on-the-fly; instead, it's enough to batch up all of those messages and upload them at the end (all that they need to broadcast at each step is just a commitment/signed hash, which will be much smaller and thus much more efficient to broadcast). I wouldn't be surprised if they were already familiar with your proposal, but considered it too trivial and too inefficient, and so wrote only about a more sophisticated version that is less obvious and more efficient.

I recommend you take a look at the following book:

Exploiting Online Games: Cheating Massively Distributed Systems. Greg Hoglund and Gary McGraw. Addison-Wesley.

---
Tags: computer-games, consensus
---


# Question
Title: What is the average-case complexity of trial division?
The trial division algorithm for checking if a number $N$ is prime works by trying to divide $N$ by all integers in the range 2, 3, ..., $\lfloor \sqrt{n} \rfloor$. If any of them cleanly divide $N$, then we say that $N$ is composite; otherwise we say that $N$ is prime.

In the worst case, this requires $O(\sqrt{N})$ divisions to be made. However, this only happens in the case where $N$ is prime. If $N$ is a composite number, then we might stop much earlier than this.

I'm curious about the *average-case complexity* of this algorithm, assuming that the input is a natural number chosen uniformly at random. Since there's no way to choose an natural number uniformly at random, I'm curious about the asymptotic growth rate of

$$\mathbb{E}\[T(X\_n)\]$$

where $X\_n$ is a random variable that takes on a value from $\\{2, 3, 4, 5, ..., n\\}$ uniformly at random and $T(N)$ denotes the number of divisions made by the trial division algorithm when run on the number $N$. Since the number of divisions made is equal to the smallest prime factor of the number in question, and since the number is chosen uniformly at random, this expression is equivalent to

$$\frac{\sum\_{i=2}^n \xi(i)}{n-1}$$

where $\xi(i)$ denotes the smallest prime factor of $i$.

I have some thoughts about what this might look like, but I'm not sure how to formalize them. First, there's the observation that about half the integers in $\\{2, 3, 4, 5, ..., n\\}$ are divisible by two, about a third are divisible by three, etc., so for many numbers very few divisions are required. Second, there's the prime number theorem that gives a good asymptotic estimate for the density of the prime numbers. However, I'm having trouble seeing how to combine all this information together.

Does anyone know how to determine the asymptotic growth rate of this expression?

# Answer
By the prime number theorem, about a $1/\log(n)$ fraction of numbers in the range $\[n/2,n\]$ are prime. We know that the algorithm will take $\Theta(\sqrt{n})$ time for each of them (since for all $x \in \[n/2,n\]$, we have $x = \Theta(\sqrt{n})$). Therefore,

$$\mathbb{E}\[T(X\_n)\] = \Omega\left({\sqrt{n} \over \log n}\right).$$

This is enough to establish that trial division is inefficient. Also, since we have the upper bound

$$\mathbb{E}\[T(X\_n)\] = O(\sqrt{n}),$$

we get a pair of upper and lower bounds that are almost matching.

It turns out one can show that the correct running time is

$$\mathbb{E}\[T(X\_n)\] = \Theta\left({\sqrt{n} \over \log n}\right).$$

I'll show the argument below. It's a bit detailed, so brace yourself.

---

There's an error in your post. You claim that

$$\mathbb{E}\[T(X\_n)\] = {\sum\_{i=2}^n \xi(i) \over n-1},$$

but that is not correct. The running time on input $i$ is not $\xi(i)$; the running time is $\min(\xi(i),\sqrt{i})$, since trial division aborts early as soon as it has tried all divisors $\le \sqrt{i}$. Therefore, your expression for the running time is not correct.

Yuval Filmus found that your expression was analyzed on Math.SE, and apparently

$${\sum\_{i=2}^n \xi(i) \over n-1} \sim {n \over 2 \log n},$$

but unfortunately this doesn't really tell us much about the running time of your trial division, due to the error I mentioned.

---

If we correct the error, we find

$$\mathbb{E}\[T(X\_n)\] = {\sum\_{t\<n} \xi(t) \over n-1} + \Theta\left(\sqrt{n} \over \log n\right),$$

where $t$ ranges over all composites less than $n$. Now we can upper-bound the first term as follows:

$$\begin{align\*} \sum\_{t \< n} \xi(t) &\le \sum\_{p \< \sqrt{n}} \left\lfloor {n \over p} \right\rfloor \times p\\ &\le \sum\_{p \< \sqrt{n}} n\\ &= n \times \\#\\{p : p \< \sqrt{n}, p \text{ prime}\\}\\ &= n \times O\left({\sqrt{n} \over \log n}\right). \end{align\*}$$

where the sum is over all primes $p$ that are at most $\sqrt{n}$, and using the prime number theorem in the last step to note that there are $O(\sqrt{n}/\log(\sqrt{n})) = O(\sqrt{n}/\log(n))$ many such primes $p$.

It follows that

$$\mathbb{E}\[T(X\_n)\] = O\left(\sqrt{n} \over \log n\right),$$

so the simple bound given at the start of the answer was tight.
> 8 votes

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


# Question
Title: Compare the growth of $2^{n}$ to $n^{a}$ for all $a \in \mathbb{N}$?
How to find which of $2^{n}$ to $n^{a}$ is an (upper bound, tight bound asymptotically larger, etc..)? I tried to use the formula:

$$ \lim\_{n\to\infty} \frac{f(n)}{g(n)} $$

where $f(n) = n^{a}$ and $f(n) = 2^{n}$

But I cannot figure out how to use L'Hospital's rule to solve it. We are guaranteed that $a \in \mathbb{N}$.

# Answer
As a hint, $n^\alpha = 2^{\alpha \log\_2 n}$. Now, you can compute the ratio between these functions by subtracting the exponents. There's no need to use l'Hôpital's rule.
> 3 votes

# Answer
Hint: $\frac{(n+1)^\alpha}{n^\alpha} \to 1$, so for any $C\>1$ you can show that $n^\alpha = O(C^n)$. If you take $C \< 2$ then you get that $n^\alpha = o(2^n)$.
> 2 votes

# Answer
If you want to use L'Hopital's rule to prove $n^{a}=o(2^n)$ that is fairly easy.

Lets consider the lemma in this question's accepted answer. The problem reduces to calculate the limit:

$$ \lim\_{n\to\infty} \frac{n^a}{2^n} $$

This limit is of the type "infinite divided by infinite". So we can try to use L'Hopital's rule.

Let $f^i(n)$ be the ith derivative of $f(n)$ and $g^i(n)$ be the ith derivative of $g(n)$. Consider the following properties of $f(n)=n^a$ and $g(n)=2^n$:

$$f^i(n) = a(a-1)(a-2)...(a-i+2)(a-i+1)n^{a-i} $$ $$g^i(n) = 2^n\*log^i(2)$$

As you can see the following LHopital's Rule's conditions comply:

* $f$ and $g$ are differentiable in the interval $\]1,\infty\[$.
* $g$ and $g'$ are nonzero in the interval $\]1, \infty\[$.
* As $n \rightarrow \infty$:

$$\frac{f(n)}{g(n)}\rightarrow \frac{\infty}{\infty}$$

This conditions also comply for the derivatives of $f$ and $g$.

Now we use L'Hopital's rule "a" times: We have to derive $f(n)$ and $g(n)$ "a" times and the result is:

$$ \lim\_{n\to\infty} \frac{n^a}{2^n} = \lim\_{n\to\infty} \frac{a(a-1)(a-2)...(2)(1)\*n^0}{2^n\*log^a(2)} \rightarrow \frac{a(a-1)(a-2)...(2)(1)\*1}{2^\infty\*log^a(2)}= 0 $$

Finally the last condition of L'Hopital rule complies:

* The limit exist(in this case is defined).

and the limit is zero as requested so $n^{a}=o(2^n)$.
> 1 votes

---
Tags: asymptotics
---


title: Correctness of the greedy algorithm

text:
# Question
Title: Correctness of the greedy algorithm
I am trying to solve the following problem: Given a matrix which consists of only 0's and 1's. Considering the matrix as a metal sheet, we need to "cut-out" square blocks of sizes 2x2 consisting of only 0's from it. A 1 in the sheet (represented by the matrix) indicates that we cannot cut the region out from the sheet. Given such a matrix, find the maximum number of blocks which can be extracted.

For instance, if the given matrix is:
There can be 2 blocks which can be extracted out of this.

**My Solution:**
I am using a greedy algorithm to solve the problem. I traverse from all the corners of the matrix (top-left, top-right, bottom-left, bottom-right) - one by one, extracting out the blocks on a first encountered first extracted basis. Finally I return the maximum of the 4 values that I get. From each corner, I traverse an entire row first (horizontally), only then I move up or down in the matrix.

The algorithm is as follows:

```
1) Starting from the top-left corner of the matrix (0,0), I iterate along all the columns
in this row from left to right.

2) If a zero is encountered at a position (i,j), I check if this is a possible
contender to be the top-left corner of a 2x2 block consisting of all zeros -
which would be the case when values at (i, j+1), (i+1, j) and (i+1, j+1) are all zeros.

3) If it is, I fill the 2x2 block {(i,j), {i,j+1), (i+1,j), (i+1,j+1)} with 1's, and a
counter is incremented.

4) Steps 2 through 3 are repeated for all rows from the top to bottom.

5) I restore the original matrix in the problem, and start again from the top-right corner
of the matrix (0, N) - N being the number of columns in the matrix, and iterate along
all the columns in this row, from right to left.

6) If a zero is encountered at a position (i,j), I check if this is a possible contender
to be the top-right corner of a 2x2 block consisting of all zeros - which would be the
case when values at (i, j-1), (i+1, j) and (i+1, j-1) are all zeros.

7) If it is, I fill the 2x2 block {(i,j), {i,j-1), (i+1,j), (i+1,j-1)} with 1's, and a
different counter is incremented.

8) Steps 6 through 7 are repeated for all rows from the top to bottom.

9) Likewise, the matrix is traversed two more times from bottom-left and bottom-right
corners, checking for a '0', which can be a possible bottom-right or bottom-left corner
for a 2x2 block consisting of all zeros. Each of these matrix traversals are performed on
the original matrix given in the problem - i.e. changes made in top-left traversal are
discarded while traversing the matrix from top-right and so on.

10) The 4 traversals of the matrix give us 4 different counters, and the maximum of
these 4 values is returned as the result.

```

So far I have not been able to come with a test case which shows that the algorithm is incorrect. As I am not very good with proving correctness of algorithms, I need some help to figure out if this algorithm is correct.

Thanks!

# Answer
> 6 votes
If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.

But there is an 8 blocks solution (on the right).

---

The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.

Repeating the search in different directions will not fix this, as it is possible to build symmetric patterns that result to the same behavior in all directions.

# Answer
> 4 votes
The example provided by Valentin Lorentz can be slightly modified to break your solution for one order of traversal:

```
1 0 0 1
0 0 0 0
0 0 0 0

```

You can build a larger test case that contains all 4 rotations of this one, so your greedy will mess up at least one of them.

Although I don't know a proof for NP-Hardness or anything of the kind, I highly suspect this problem does not have a polynomial solution. A similar problem that asked for 3x2 or 2x3 pieces can be found here: http://web.ics.upjs.sk/ceoi/documents/tasks/bugs-tsk.pdf.

Its solution, which is fairly sophisticated, uses dynamic programming and requires exponential time in one of the matrix's dimensions: http://web.ics.upjs.sk/ceoi/documents/tasks/bugs-sol.pdf

I'm 99% sure that your problem requires a similar approach.

An interesting case - and one that actually has a polynomial solution - is asking the same problem with 2x1 or 1x2 tiles (a.k.a domino pieces). Its solution is also more complicated than a simple greedy though.

# Answer
> 3 votes
**My own solution to this problem**:

Apparently this problem could be of an exponential type, and striving to find a fast solution might be hopeless. So my design approach is to allow a brute-force search at some place, while trying to find a reasonable heuristic when easy solutions are possible.

First shrink all the $2\times2$ blocks to their top-left cell, putting a $0$ when all four cells are $0$, and $1$ otherwise; the initial array will lose its last row and column. In image processing parlance, this is an erosion operation. It recasts the geometric reasoning from blocks to cells. \[In what follows, a cell or a block are deemed to contain only zeroes, unless otherwise specified.\]

Then, remark that two blocks can only be both counted if they don't overlap, i.e. if their corresponding cells are disconnected (not touching by an edge nor by a corner).

We can restate the problem as: "find a maximal subset of disconnected cells", or equivalently "remove a minimal number of cells so that the remaining ones are disconnected".

As an immediate consequence, we see that we should process separately all connected components in the array. This can be an important saving for fragmented cases. \[Indeed, for a total of $N$ cells there are $2^N$ possible subsets. Assume they are forming connected components of sizes $N\_1,N2,\cdots$ Then the number of subsets is $2^{N\_1}2^{N\_2}\cdots$ But if we process per-component and regroup the partial solutions as a hole, the number of possible subsets drops to $2^{N\_1}+2^{N\_2}+\cdots$ We trade multiplies for adds.\]

The connected components and the cells that form them are easily enumerated by a seed-fill algorithm, such as $8$-ways recursion, seeding from a systematic scan of the array.

Now, for a single component, we will use brute force to remove a minimal subset. We do this by increasing number of removed cells, in an exhaustive way. So we use a combination generator that will output all combinations of a single cell, then of two, three... If the component is made of $K$ cells, the successive passes will include $K,\frac{K(K-1)}2,\frac{K(K-1)(K-2)}{3!}\cdots$ combinations, for a total of $2^K$. \[This is where it can get nasty.\]

For a given target combination, we proceed as follows: for every cell, initialize a counter telling how many connections it has. Then for every cell of the combination, decrement the counters of all neighbors. When a counter drops to zero, the corresponding cell is disconnected. So it suffices to check that all counters have dropped to zero.

As soon as the check of a combination "passes", an optimal solution is found for this component.

To summarize:

```
Shrink the blocks to cells
Enumerate all connected components (by seed-filling)
    For a given component, let of size K
        By increasing number of cells, let M
            Enumerate all combinations of M cells among K
                For a given combination
                    Initialize the connection counters
                    For all cells appearing in the combination
                        Decrease the connection counter of the neighboring cells
                    If all counts have dropped to zero
                        Done for this component

```

In the given example, the shrinking of the blocks leads to a single connected component.

If we try to remove a single cell, we never get a disconnected set.

But if we try in pairs, at the fifth attempt we get one. This is an optimal solution.

---

For the $7\times7$ pattern given in my other answer, the shrunk pattern is a $6\times6$ $\\#$ shape with $20$ cells, forming a single component.

It takes at most $20+\frac{20\cdot19}2+\frac{20\cdot19\cdot18}{3!}+\cdots+\binom{20}{12}=910595$ attempts before a solution is found ($8$ remaining cells), over a possible total of $2^{20}=1048576$ combinations.

For the $8\times8$ pattern of @ValentinLorentz, there are four T-shaped components, each independently solved in at most $10$ attempts, for a total of $40$ (!).

---

**Final comment**: the method works for rectangular blocks of any size, just by adapting the shrinking operation.

# Answer
> 2 votes
Try with this one:

```
 1 0 0 1 1 0 0 1
 0 0 0 0 1 0 0 0
 0 0 0 0 1 0 0 0
 1 1 1 1 1 0 0 1
 1 0 0 1 1 1 1 1
 0 0 0 1 0 0 0 0
 0 0 0 1 0 0 0 0
 1 0 0 1 1 0 0 1

```

Example for the top left corner (the other cases are obtained through rotation):

Your algorithm (when running from the top left corner) will find this:

```
  +---+
 1|0 0|1
 0|0_0|0
 0 0 0 0

```

Whereas the optimal would be two blocks.

And when the algorithm runs from another corner, it will fail on an other pattern in the matrix

# Answer
> 0 votes
The order in which you go through the cells is not well defined. For instance, with this matrix, which one of the two squares would you find first when coming from the top left corner?

```
1 0 0
0 0 0
0 0 1

```

And I think I have a counterexample, depending on how you break ties:

```
1 0 0 1
0 0 0 0
0 0 0 0
1 0 0 1

```

With an interpretation of your algorithm, it the first square that would be found from any of the corners would be the middle one, whereas an optimal solution is 2.

---
Tags: algorithms, correctness-proof, greedy-algorithms
---


# Question
Title: Algorithm for finding fixed cycles in bipartite graphs in sublinear time
Does there exist an algorithm that will compute in sublinear time whether a bipartite graph contains a cycle of fixed length? For example given a $K\_{3,3}$ graph finding if it contains a cycle $C\_4$.

I considered the answer to be no. As a DFS could be used and then compare to see if after a certain traversal we were back at a node we've already visited. That would be $O(n)$ time at best. However, as a counter argument to that, a complete graph will always contain a cycle, and if we know the cycle length then search time should be dependant on the cycle length which would be $O(1)$ or big-oh of the cycle length. If we know whether we're in partition A or B all we have to do is return to the first node since both sets connect to all nodes of the other.

# Answer
In general, you can't determine if there is a e.g., 4-cycle in an arbitrary graph in sublinear time. This is shown by a simple adversary argument: if you don't read the whole input (this is what sublinear means), how can you possibly know if a critical edge is present that creates the 4-cycle? There are similar questions asked already, but these appear in a different context (usually, these are related to sorting). For instance, see this question.

If you assume the input graph is complete, or has some other structure that guarantees the existence of a 4-cycle, an algorithm for solving the problem can immediately output YES. But if the input graph is arbitrary, again by an adversary argument you cannot determine if the graph is say complete in sublinear time.

For example, if the input is a $K\_{3,3}$, you can immediately answer YES. So suppose the input graph is an arbitrary bipartite graph, and we are looking for a $k$-cycle for a fixed $k$. If $k$ is odd, we can output NO, as bipartite graphs are characterized by having no odd cycles. Otherwise, an adversary argument shows that for even $k$, sublinear time is not achievable. Similarly, it is easy to see you cannot test for bipartiteness in sublinear time. (For both cases, consider having read $m-1$ edges, and the last $m$th edge to be read decides if you have a path or a cycle).
> 4 votes

---
Tags: algorithms, graphs, search-algorithms
---


# Question
Title: Is O(ln n) "exponentially faster" than O(n)?
I improved the complexity of an alogrithm from $O(n)$ to $O(\ln(n))$. Is it legitimate to call this an "exponential speedup" in a scientific publication? Usually I think going from NP to P when I hear the phrase "exponential speedup". I'd like to avoid overselling my work.

# Answer
## How should we measure (asymptotic) speedup?

Say we wish to compare two functions, $f(n)$ and $g(n)$, and say something on their **asymptotic** behavior, that is, how they behave for large enough $n$'s, in the limit $n \to \infty$.

Let's start with a few examples.

> **Example 1:** $f(n)=2n$ and $g(n)=n$.

Here it is obvious that $f$ is "twice as slow" as $g$; This is true for any $n$ and also in the limit. This needs not be the case. For instance

> **Example 1.1:** $f(n)=2n$ and $g(n)=n+1000$.

Well, now, for $n\<1000$, $f$ is actually *faster* than $g$. But still, if we take large $n$'s, we want to say that $f$ is twice as slow as $g$, or in other words, the speedup is 2.

Why 2? Because the **ratio** between $f$ and $g$, in the limit, is 2.

Let's take a different example to emphasize this issue.

> **Example 1:** $f(n)=n+10$ and $g(n)=n$.

Here, $f$ is slightly slower than $g$. What is the speedup between $f$ and $g$? By how much is $g$ faster? The answer is "by 10 clocks". But speedup is measured as a ratio - "twice" as fast means it would take (approx.) twice the time to run the slower function. Here the ratio is approaching 1 $$\lim\_{n\to \infty} \frac{f(n)}{g(n)} \to 1$$ That is, the 10 clocks don't make any (multiplicative) difference. Running 10000 clocks and running 10010 clocks, is practically the same (the speedup is $\<0.1\\%$).

I hope the above establishes that *the (asymptotic) speedup between $f$ and $g$* should be defined as $$\lim\_{n\to \infty} \frac{f(n)}{g(n)}.$$

When the speedup is not a constant, then the best way to describe the speedup is to set $g(n)=k$ and ask how $f(n)$ behaves as a function of $k$. If $f(n) \propto k^2$, then the speedup is "quadratic". If $f(n)\propto k^3$ the speedup is cubic. If $f(n)\propto 2^k$, the speedup is called exponential. Not that it is important to set $g$ as the base unit ($=k$). Otherwise, If we take $f$ as the base unit, then a quadratic speedup translates to $g(n)=\sqrt{k}$, which may be a bit confusing. Maybe its better to think at the other direction: instead of considering the *speedup* from $f$ to $g$, look at the *slowdown* from $g$ to $f$. (<sub>.. if $g$ is twice as fast as $f$, then $f$ is twice as slow as $g$</sub>)

If we agree on this, we can check the speedup between $f(n)=n$ to $g(n)=\log n$. $$\lim\_{n\to \infty} \frac{f(n)}{g(n)} = \lim\_{n\to \infty}\frac{n}{\log n}$$ Let's change the limit variable, to make $g$ the base unit for the comparison: set $k=\log n$, then, $$\lim\_{n\to \infty} \frac{f(n)}{g(n)} = \lim\_{k\to \infty} \frac{2^k}{k}$$ That is the ratio between them, in the limit, has an exponential gap. As mentioned, this is called exponential speedup.
> 7 votes

---
Tags: algorithm-analysis, terminology, asymptotics
---


# Question
Title: What is discrete mathematics and why am I learning about it?
I started computer science in university. And we started learning about Discrete and it's mathematics which is completely based on logic, which I understand. however, how is predicates, sets, proofs are related to computers ? I want to know the reason for learning these stuff?

# Answer
*Very* roughly speaking, Discrete Mathematics is the body of material that a computer scientist needs to know. You can look at it as that part of mathematics which doesn't involve limits, continuity, differentiation, or integration. In set notation, we have Discrete = Mathematics \ Calculus.

The usual topics in a Discrete course and their applications to CS are

* Propositional and predicate logic: used to establish the correctness of a program.
* Proofs: used throughout CS, for things like establishing the closure properties of, say, regular languages.
* Functions: obvious uses, since functions are ubiquitous in CS.
* Sets: you can't do much in the theory of databases without them
* Relations: again, fundamental for databases and also the basis for algorithms such as topological sorting
* Recurrences: lists and trees can be viewed as recursively defined. Also, you can't do much to establish the time or space complexity of algorithms without being conversant with recurrence relations
* Graphs and trees: when establishing the properties of networks
* Counting: again, fundamental for the design and analysis of algorithms
* Probability: for example, finding the average time complexity of an algorithm

Obviously, I've left out many more uses, but you get the idea. One could make the point that essentially all of CS beyond Programming I uses the concepts of Discrete in one way or another.
> 5 votes

---
Tags: mathematical-foundations
---


# Question
Title: Can computation models be categorized in terms of efficiency?
It is widely accepted that turing-complete systems are equivalent in terms of computability - i.e., whatever a turing-machine can do, can be emulated by automatas, the lambda calculus and other computing systems.

Not much is said about the **efficiency** of such systems. Intuitively speaking, it makes sense to think that some systems are less efficient than others. Is it possible to meaningfully categorizing such systems in term of efficiency?

# Answer
If your model contains a notion of "step" (which is reasonable), and consequently defines the running time as the number of computational steps, then you can define the class $P$ for your model. If you think about polynomial time as efficient (which is what we normally do, see for example the question here), then you have a definition for what is efficiently solvable in your new model. You can now ask about the differences between the classes $P\_M$ (set of languages decidable in polynomial time in the new model $M$), and the regular $P$ (which relates to Turing - machines).

Now, a reasonable definition for "the model $M$ is more efficient than $M'$" would be $P\_{M'}\subsetneq P\_M$.

Although $P$ has the advantage that it can be defined relative to any reasonable computational model, sometimes our notion of efficiency changes depending on the context.

For example, in quantum computation (for a formal definition of the model you can look up quantum circuits or quantum Turing machines) our notion of efficiency is captured by the class $BQP$ (since we involve error probabilities, it makes sense to allow our polynomial algorithm to be wrong with small probability). Same goes for the probabilistic Turing machine (Turing machines with the additional ability to toss coins). Our notion of "efficiently computable" with respect to probabilistic Turing machines is captured by the class $BPP$.

The question whether these models are "more efficient" than the classical Turing machine, translates to whether $P\subsetneq BQP$, and whether $P\subsetneq BPP$.

Since we know factoring integers is in $BQP$ (Shor's algorithm), and we suspect that it is not in $P$, we suspect that indeed $P\subsetneq BQP$, meaning that quantum computers can decide more problems efficiently (although it has the same computational power as the classical Turing-machine).
> 2 votes

---
Tags: complexity-theory, computation-models, efficiency
---


# Question
Title: How to prove that $L_1=1^*\cup \{0^i 1^{j^2}|i\ge 0,j\ge 0\} $ is irregular?
We know that $L=\\{0^i 1^{j^2}|i\> 0,j\ge 0\\} $ is irregular (by the Pumping Lemma), we have to use it to prove two things:

1. $L\_1=1^\*\cup \\{0^i 1^{j^2}|i\ge 0,j\ge 0\\} $ is irregular.
2. $L\_1$ is making all the three conditions (I don't know the exactly word at English for this...) of the Pumping Lemma.

For the first one - how do I prove it by the Pumping Lemma?

For the second - I have no idea and I'd like to get ant help!
(Because I can choose any word that I want, and I need to prove it for all the words in $L$).

Thank you!

# Answer
You don't need to use the pumping lemma to prove that $L\_1$ is irregular. You can also make use of the closure properties of the regular languages.

We know that regular languages are closed under intersection. That is, if $L\_1$ and $L\_2$ are regular languages then $L\_3 = L\_1\cap L\_2$ is also a regular language.

A nice way to prove that a language is irregular is to assume that it is regular and reach a contradiction using the closure properties of the regular languages.

For example consider the language $L\_p = \\{1^p: p\text{ is prime}\\}$ we know that this is an irregular language. Let's consider $L\_q = L\_p \cup 0^\*$. How can we prove that this language is irregular?

Let us assume for the purpose of contradiction that $L\_q$ is regular, hence $L\_q\cap 1^\*$ is also a regular language since $1^\*$ is a regular language. But wait.. The intersection is $L\_p$ (the primes) which is not a regular language. Contradiction. So $L\_q$ is irregular.

Your problem can be solved along the same lines.
> 2 votes

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


title: Definition of complexity classes?

text:
# Question
Title: Definition of complexity classes?
My book uses this definition for the Polynomial complexity class ($L$ is a language over $\\{0,1\\}$):

$$\mathrm{P} = \left\\{L\subseteq\\{0,1\\}^\*\\;\middle|\\; \begin{array}{l} \text{there exists an algorithm $A$ that decides $L$} \\ \text{in polynomial time}\end{array}\right\\}\\,.$$

But by this definition, don't all languages belong to the polynomial complexity class? Because if I define $A$ to be 1 for all languages, then $A$ would decide all $L$ in constant time (and therefore polynomial time), since it would return 1 immediately, meaning all languages would belong to polynomial complexity.

Why is my logic incorrect?

# Answer
You seem to be confusing languages and strings.

An algorithm that decides a language $L$ is an algorithm whose input is a string $w$ and whose output is true if $w\in L$ and false if $w\notin L$. As such, an algorithm can only decide one language: specifically, the language $$L\_A = \\{w\mid A(w)=\mathrm{true}\\}\\,.$$

So, when you say, "then $A$ would decide all $L$", you're making a category error. An algorithm cannot possibly decide more than one language. What you've described is an algorithm that outputs true for every input: in other worse, an algorithm that decides the language $\\{0,1\\}^\*$.

Note that $A$ decides a language by taking strings as inputs; it doesn't take *languages* as input and decide whether that langauge is in **P**.
> 3 votes

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


# Question
Title: Proving specific prefixes of regular languages are regular
There are particular problems in Kozen that I'm unable to solve, and they seem to be similar to each other. It is showing that sets:

$$ \\{x \mid \exists y: |y| = 2^{|x|} \text{ and } xy \in A \\}$$ $$ \\{x \mid \exists y: |y| = |x|^2 \text{ and } xy \in A \\} $$

are regular for a regular set $A$. The only method I'm familiar with that is similar is proving that first-halfs or first-thirds or any other linear parts of a regular language are regular (using a 2-NFA). I've tried looking online, but I only found that it's hard to construct NFAs for that. Is there some other way of proving existence? I also don't understand how we can even compute $|x|^2$ or $2^{|x|}$ for different strings in the language to use that value.

# Answer
> 0 votes
Basically, you do not compute these lengths $2^n$ or $n^2$, but only the from-to computations that the automaton would be able to make on input with this particular lengths.

For the first two problems the automaton computes (in its internal states) the relation $E\_\ell = \\{ (p,q)\in Q\times Q \mid q\in\delta^\*(p,y) \text{ for some $y$ with $|y|=\ell$} \\}$ for some value of $\ell$ (which depends on $|x|$).

Then $E\_{2\ell}=E^2\_\ell$ which helps to solve the first problem. Here $E^2$ is the composition $E\circ E$ of the binary relation $E$ with itself: $E^2 = \\{ (p,r) \mid \text{ for some } q\in Q \text{ both } (p,q)\in E \text{ and } (q,r)\in E\\}$

I add some details. This is still rather formal, without much intuition. I hope it helps you into the right direction.

Assume we are given a FSA $\mathcal A= (Q,\Sigma,\delta,q\_0,F) $ for language $A$. We will construct an automaton for your first problem.

The new states are of the form $(p,E)$ where $p\in Q$ and $E\subseteq Q\times Q$; i.e., the new state set equals $Q\times{\mathcal P}(Q\times Q)$.
Note that the number of possible relations $E$ is finite, hence adding such a relation to the states of the automaton will still lead to a finite state automaton. The second component will always contain the relation $E\_{2^n}$ where $n$ is the length of the input read.

The initial state equals $(q\_0,E\_1)$, where $E\_1$ is the one-step relation on $Q$, just like defined above.

Now from every $(p,E)$ reading letter $a$ we move to state $(\delta(p,a),E^2)$. Thus, the first component copies the original move in $\mathcal A$, the second component steps from $E\_{2^n}$ to $E\_{2^n}\circ E\_{2^n}=E\_{2^{n+1}}$ following the recipe above.

When is a state $(p,E)$ final? When there is a pair $(p,q)\in E$ such that $q\in F$ is final in $\mathcal A$.

The $n^2$ problem is along similar lines, but actually slightly more involved (I think). It uses the fact that $(n+1)^2 = n^2 + 2n +1$. The automaton stores both $E\_{n^2}$ and $E\_{n}$ to easily update the square.

---
Tags: formal-languages, regular-languages, closure-properties
---


# Question
Title: How to check if my language is context-free can't seem to solve it using pumping lemma
I have a language and I am trying to see if it's context-free or not, by trying to use a pumping-lemma but I can't figure it out, been reading a lot of other posts but still struggling to apply it to my example

this is the language (sorry for using an image, i know how to write number exponents but i don't know how to write letters as exponents):

Thanks

# Answer
One can proof that a language is CF by constructing a CFG or a PDA for it. I will give an example CFG for this language.

Let the start symbol be $S$.

In the definition we see that we can add arbitrarily many $m$'s, and for each $m$ there have to be two $t$'s. $$M \rightarrow mMtt|\epsilon$$

The same for the $e$'s, but now with one $t$ fot each $e$. $$E \rightarrow tEe|\epsilon$$

Then finally, there has to be an extra $t$. This gives following CFG:

$$S \rightarrow MtE$$ $$M \rightarrow mMtt|\epsilon$$ $$E \rightarrow tEe|\epsilon$$
> 0 votes

---
Tags: formal-languages, context-free, formal-grammars, pumping-lemma
---


# Question
Title: Help interpreting this deadlock question
I have this assignment question but I am a bit unsure how to go about answering it. The question is as follows and accompanied by the image below:

Three processes are competing for six resources labelled A to F as shown below.

Using a resource allocation graph, show the possibility of a deadlock in the implementation above.

I know how to do the graph but what I am struggling to understand is, do I take the `Release();` methods into consideration or only the `Get();` methods. And also, would `P0()` access resources A, B and C first or will each process run simultaneously meaning `P0()` access resource A, `P1()` access resource D and `P2()` access resource C, and then the second set of `Get()` methods are requested simultaneously? Lastly it does not specify how many instances (dots) are in each resource, is there any indication as to how to determine/go about working with this? As soon as I can clear up these misunderstandings I can draw the diagram

# Answer
Here is one bad scenario:

1. P0 obtains A and B.
2. P1 obtains D and E.
3. P2 obtains C and F.

At this point, we have reached deadlock, since P0 is waiting for P2 to release C, P1 is waiting for P0 to release B, and P2 is waiting P1 to release D.
> 1 votes

# Answer
## Introduction

Consider a Petri Net model of the three processes. Assume the following:

1. Every resource (A, B, C, D, E, F) has one unit only.
2. All three processes run on a single processor. The processor can execute one and only one process at a time. This means that if a process is executing its Get() or Release() function or critical region, no other process can execute.
3. After executing a statement in any process (such as Get(), a statement in the critical section or Release()), the operating system can switch to another process and execute the other process’ next statement.

## Petri Net: Model and Sub-Models

Figure 1 is a Petri Net model of Process 1. Figure 2 is a Petri model of Process 2. Figure 3 is a Petri Net model of Process 3. Figure 4 is a Petri Net model of all processes.

## Deadlock Scenario

Figure 5 is an initial state of the system where none of the resources have been allocated. Figure 6 is the state of the system reached from the state in Figure 5 following the firing sequence: G\_0^0→G\_1^0→G\_0^1→G\_1^1→G\_0^2→G\_1^2.

## Three Processes Competing for Resources

Figure 7 is a larger version of Figure 5 and (for the PDF version of this document) it is an interactive, dynamic diagram.

## Reference

Chionglo, J. F. (2015). "A Reply to 'Help interpreting this deadlock problem'". Available at http://www.aespen.ca/AEnswers/1449369180.pdf.
> 1 votes

---
Tags: deadlocks, resource-allocation
---


title: How the deletion takes place in B+ Tree

text:
# Question
Title: How the deletion takes place in B+ Tree
My professor was giving a lecture on B+ Trees deletion, and I got very confused. According to him for deleting any key from a B+ Tree:

```
1- First navigate to the leaf *L* where it belongs.
2- If the *L* is at least half full if you can simply delete it.
3- If it contains d-1 elements then you need to redistribute and merge.

```

If you see the below image, here I want to delete 19 and 20 from the B+ Tree.

After deleting 19 and 20 from the B+ Tree.

Question:

I am confused why the redistribution and merging is required here at all? If you just simply delete 19 and 20 from the leaf nodes without any distribution it should work right? Why redistribution is performed here? Could anyone explain?

> Is it because the left pointer of 24 is pointing to 20 but no 19. Thats why redistribution is required for 20 but not 19.

# Answer
Okay I understood the issue.

Properties of B+ Tree.

* All leaves should be at the same depth, and the mininum element in each leaf node should be equal to depth of the tree. See the example below:
* All the leaves are in same depth, and here d = 2.
* Each leaf node must contain d number of elements, otherwise redistribution and merging has to be performed.
* All the data pointers are contained in leaf nodes.
* All elements should be contained in leaf nodes.
* There should be between `d` to `2*d` keys at node except possibly the root.
* There should be between `d + 1` to `2*d + 1` child pointers.

In the B+ Tree given below, each node has `2` and `2*2` data entries except possible the root. Each node has a mininum of 2 keys.

Only root of the B+ Tree can only fewer than d keys, its the only exception we have.

In my question, when you remove `19`, the property of B+ Tree is not violated but when you remove `20`, the total number of elements contained in the node is less than d. Hence redistribution and merging have to be performed so that the property of B+ tree is not violated.
> 5 votes

---
Tags: data-structures, search-trees, balanced-search-trees
---


# Question
Title: What set of primitive operations are assumed to be constant time in complexity analyses?
Different set of primitive operations lead to different complexity of certain problems. For example, sorting by comparison is only `O(N*log(N))` if one assumes both integer comparison and random array indexing are O(1). While this might hold for bounded N, I believe complexity analysis is, theoretically, supposed to speculate about the asymptotic growth of a function, whereas it is obvious that you can't implement constant-time comparison or array indexing for arbitrarily large values. This makes me question the theoretical merits of such complexity analyses.

My question is: **when there is a literature result such as `X algorithm is found to be quasipolynomial`, which set of primitive operations are assumed to be constant time?**

# Answer
It depends on the "model of computation". The model of computation specifies things like what can be done in a single step and what operations are available. There are different models of computation, each of which can sometimes lead to a slightly different running time.

If the model of computation makes an important difference and the paper is being careful, it will usually mention which model of computation it is working in. Sometimes we don't care about the difference (or the difference is negligible) and then the model of computation might not be mentioned.

So, your model of computation could specify that pointers and integers (large enough to hold numbers in the range $\[0,N\]$) fit in a single word and can be accessed in $O(1)$ time. Or, it might specify that this takes $O(\log N)$ time and space. A circuit-centric model of computation might count the number of gates in a circuit needed to do the computation. There are many others.

One example of a model of computation is the RAM model.
> 2 votes

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


title: k-tape turing machine

text:
# Question
Title: k-tape turing machine
I want to create multi-tape Turing machine that recognize language {ww, $w \in {a,b}$}. With condition that max. steps is less or equal than $\frac{3}{2}\left | x \right | + 2$. Where x is word from language. I have an idea to create x-tapes to solve this problem, but can be the number of tapes not known before reading from input(read-only) tape, and for n-length there will be n-tapes, is that possible ?

# Answer
All Turing machines are fixed in advance, independent of the input. This applies to all aspects of the machine: the state set, the alphabet, the transition function, the number of tapes. The only thing that changes from input to input is the input!
> 1 votes

---
Tags: turing-machines, regular-languages
---


# Question
Title: Which calculus is based on first-order functions and is Turing complete?
**Which calculus is based on first-order functions and is Turing complete?**

I know of calculi which are Turing complete, but based on higher-order functions:

* Lambda calculus
* SKI combinator calculus

There is also a calculus based on first-order functions, but is not Turing complete:

I know that first-order functions by itself aren't Turing complete, but first-order functions with recursion and primitive types as $\mathbb{N}$ is.

# Answer
> 5 votes
There are many, but I think the most famous one µ-recursive functions. It describes functions from $\mathbb{N}^{(\mathbb{N})}$ to $\mathbb{N}$, i.e. from tuples of naturals to naturals. This can be transformed into a theory of functions from $\mathbb{N}$ to $\mathbb{N}$ by composing with an encoding of tuples; I think the reason it isn't commonly presented that way is that it doesn't look neat.

µ-recursive functions are defined as follows:

* All constant functions are µ-recursive.
* The successor function ($S(n) = n+1$) is µ-recursive.
* Projections ($\pi\_i(n\_1,\ldots,n\_k) = n\_i$) are µ-recursive.
* Composition: if the $f\_i$ and $g$ are µ-recursive then $(n\_1,\ldots,n\_{k\_1+\ldots+k\_m}) \mapsto g(f\_1(n\_1,\ldots,n\_{k\_1}), \ldots, f\_m(n\_{k\_1+\ldots+k\_{m-1}+1},\ldots,n\_{k\_1+\ldots+k\_m}))$ is µ-recursive.
* Primitive recursion: if $f$ and $g$ are µ-recursive then the function $h$ defined by $h(0,n\_1,\ldots,n\_k) = g(n\_1,\ldots,n\_k)$ and $h(n+1,n\_1,\ldots,n\_k) = f(n,n\_1,\ldots,n\_k,h(n,n\_1,\ldots,n\_k))$ is µ-recursive.
* Minimisation: if $f$ is µ-recursive then so is the function that maps $n\_1,\ldots,n\_k$ to the smallest $x$ such that $f(n\_1,\ldots,n\_k,x) = 0$.

Note that in the definition of the minimisation operator, it is possible for $x$ not to exist. In this case the resulting function is partial. This calculus thus defines partial recursive functions.

If you restrict the calculus to total functions, you get the recursive functions, with the same computing power as Turing machines.

The minimisation operator is usually written $\mu$ and gives the calculus its name. If you omit it, the resulting set of functions are exactly the primitive recursive functions (indeed that's a convenient way to define them).

# Answer
> 3 votes
As an addition to Gilles's answer:

While the statement

> If you restrict the calculus to total functions, you get the recursive functions, with the same computing power as Turing machines.

is correct, it might be worth mentioning that there cannot be a calculus $L$ with the following features.

**Disclaimer:** I abuse notation, I am being reasonably informal and I assume some effective Gödelization $\langle\cdot\rangle\colon L\to \mathbb{N}$ as well as denotational semantics $\[\cdot,k\]\colon L\to (\mathbb{N}^k\to\mathbb{N})$:

1. There is an element $t\in L$ (think of some sort of a bytecode interpreter) such that for all terms $s\in L$ and all $x\in\mathbb{N}$ the following holds: $\[t,2\](\langle s\rangle,x)=\[s,1\](x)$.
2. Given any term $s$ there is a term $s^\*$ such that $\[s^\*,1\](x)=\[s,2\](x,x)$. For every term $s$ there is a term $s'$ such that $\[s',1\](x)\neq \[s,1\](x)$ for all $x$. Note that these are pretty trivial assumption about a calculus that is meant to describe any interesting class of computable functions.
3. all functions $\[s,k\]$ are total.

Proof by contradiction that no such calculus exists:

let $t\in L$ be as 1. above and let $s=(t^\*)'$ then \begin{align\*} \[s,1\](\langle s\rangle) &= \[(t^\*)',1\](\langle s\rangle)\\ &\neq \[t^\*,1\](\langle s\rangle)\\ & = \[t,2\](\langle s\rangle,\langle s\rangle)\\ & = \[s,1\](\langle s\rangle)\\,. \end{align\*}

**Remark:** This argument shows for example that there are total recursive functions that are not primitive recursive (or for that matter, that it is not possible to write a LOOP interpreter in LOOP). Of course, if the calculus describes not only total functions, then the given argument only proves that $\[s,1\](\langle s\rangle)$ is not defined.

---
Tags: lambda-calculus, turing-completeness
---


# Question
Title: How can you check if a 2SAT problem has a bad loop
im trying to figure out why this is true

**The clauses {a,b}, {b,~c}, {c,~a} constitute a 2SAT problem with an implication graph without bad loops.**

Can someone show me how to illustrate this and indicate how i can find wether any 2SAT problem has a bad loop or not, Thank you so much :)

# Answer
> 4 votes
The implication graph is constructed using the following ingredients:

* Vertices: One vertex for each variable, and one for each negation of a variable
* Edges: For each clause {x,y}, create an edge from -x to y and one edge from -y to x

The following should be the implication graph corresponding to your set of clauses:

A bad loop (I'm guessing this is what you want, haven't encountered that wording before) is a loop in the implication graph that contains both a variable and its negation (i.e. both x and -x). Clearly there is no such loop in your case.

Why "bad loop"? It is because each edge represents an implication that necessarily must hold for your 2-SAT instance. For example, the first clause reads "a or b". If this clause is to be satisfied, then we must have one of the two variables true. So:

* If a isn't true (i.e. -a is true), then b must be true, which is the implication -a$\to$b
* If b isn't true (i.e. -b is true), then a must be true, which is the implication -b$\to$a

In a "bad cycle", you have a cycle of such implications, so that x$\to$...$\to$-x$\to$...$\to$x. Such a cycle of implications can never be satisfied, otherwise x would be both true and false at the same time. So if you have any bad cycles, the 2-SAT formula is unsatisfiable!

In fact, a 2-SAT formula is unsatisfiable when, and *only* when, there is a bad cycle in the implication graph. So your formula is, by the absence of bad loops, satisfiable. The proof of satisfiability in the case of no bad loops even yields a poly-time algorithm to find a satisfying assignment (which is great : ) )

So how to assign values to the variables and satisfy your (or any) 2-SAT formula? I'll refer to https://en.wikipedia.org/wiki/2-satisfiability#Strongly\_connected\_components for the algorithm, but be warned that you need to know of the concept of "strongly connected component" to fully understand the algorithm.

---
Tags: complexity-theory, logic, satisfiability
---


title: Why is this language not context free?

text:
# Question
Title: Why is this language not context free?
I been watching tutorials about how to check if a language is not context-free and in 1 video there was a language: L = {a^n b^n c^n | n ≥ 0} and they used a pumping lemma to prove that it's not context-free, I am only a beginner at CFG however I thought a language is Context-free if you are able to create a CFG for it, and this is the CFG i created for this language:

```
S --> aSX |
X --> bXY |
Y --> cY |

```

Or am I not understand CFG and what I wrote doesn't make sense?

# Answer
The grammar you wrote can generate the word "aaa", which is not supposed to be generated, if the grammar generates exactly $L$.

ergo, the grammar is incorrect for $L$. (which is great, since $L$ is not CFL, and no grammar can generate it!)
> 1 votes

---
Tags: formal-languages, context-free, formal-grammars, pumping-lemma
---


# Question
Title: Is there any proof that quantum computers are more efficient than classical computers?
Shor's algorithm is often used as the argument. It can solve the factorization problem faster than any known algorithm for classical computers. Yet, we have no proof classical computers can't also factor integers efficiently.

Is there any actual proof quantum computers can solve some problems faster than classical computers?

# Answer
Yes, Grover's algorithm shows you can use a quantum algorithm to find an element in an unordered database of size $N$ with high probability by querying the database only $O(\sqrt{N})$ times. Any classical solution that succeeds with high probability requires $\Omega (N)$ queries to the database.
> 18 votes

# Answer
It depends what you consider an actual proof, and what you mean by "faster". From a complexity theoretic perspective, the answer is no -- we don't have such a proof. BQP (the class of problems which can be solved efficiently by a quantum computer) is contained in PSPACE. Being able to prove a separation between BQP and PSPACE would also imply a separation between P and PSPACE, which is not known.

Note that Grover's algorithm only gives a square root speedup, so there is no contradiction.
> 4 votes

# Answer
you ask about "proof" which might be limited to a mathematical level, but the basic question goes much deeper than that. theoreticians will acknowledge its basically still an open question in general about the relative performance of quantum vs classical algorithms and there is probably no simple/ general answer, but with some expert consensus that Shors algorithm seems to be "unusually fast compared to expected best classical speed." fast factoring in a classical computer will break widely held cryptographic security assumptions such as the RSA system.

* some of this is captured formally in the open complexity class question BPP =? BQP question. these are the analogous classical and quantum classes and the separation is unknown and an active area of research.
* a closely related question is whether physically QM computers can be built that match the theoretical specifications and a few/ minority of scientists (aka "skeptics") are arguing that there may be noise or scaling laws that prevent QM scaling as envisioned in the theory. in a sense the ultimate "proof" of a QM computer speed must be a physical implementation. (this is similar to the way the Church-Turing thesis is theoretical but seems to ultimately tie into an assertion about physical implementations.) some researchers are talking about Church-Turing analogs in QM computing. see eg Church Turing thesis in a quantum world by Montanaro.
* relevant to/ impinging on this question/ debate are ongoing substantial/ "heated" (scientific) attempts to benchmark the worlds current "largest" quantum computer by DWave. this is a big topic with a lot of related material, but for a relatively recent overview try D-Wave disputes benchmark study showing sluggish quantum computer / the Register
> -1 votes

---
Tags: algorithms, efficiency, quantum-computing
---


# Question
Title: Why is factoring large integers considered difficult?
I read somewhere that the most efficient algorithm found can compute the factors in $O(\exp((64/9 \cdot b)^{1/3} \cdot (\log b)^{2/3})$ time, but the code I wrote is $O(n)$ or possibly $O(n \log n)$ depending on how fast division and modulus are. I'm pretty sure I've misunderstood something somewhere, but I'm not sure where. Here's what I wrote in pseudo code form.

```
function factor(number) -> list
    factors = new list
    if number < 0
        factors.append(-1)
        number = -number
    i = 2
    while i <= number
        while number % i == 0
            factors.append(i)
            number /= i
        i++
    return factors

```

# Answer
> 26 votes
You are confusing the number $n$ with the number of bits needed to represent $n$. Here $b = $ the number of bits needed to represent $n$ (so $b \approx \lg n$). This makes a huge difference. A $O(n)$-time algorithm is a $O(2^b)$-time algorithm -- exponential in the number of bits. In comparison, the "efficient" algorithm you found has a running time that is subexponential in $b$.

Example: Consider $n = 2,000,000$ (2 million). Then $b=21$ bits are enough to represent the number $n$. So, an algorithm that is $O(2^{b^{1/3}})$ will be much faster than an algorithm that is $O(2^b)$. An $O(n)$ algorithm falls into the latter category, i.e., very slow.

See https://en.wikipedia.org/wiki/Integer\_factorization

# Answer
> 1 votes
you have roughly two questions here, a general and a specific one about your code. the specific one is handled in the other answer. the general question in the title about the complexity of factoring is very deep. unfortunately there is not strong scientific evidence that factoring is outside of P other than (the mostly circumstantial) "lots of experts have tried and failed" and some experts conjecture it is inside P; its regarded as one of the foremost (and very hard to resolve) open problems of complexity theory. after decades of "heavy attack" the best algorithms are exponential. factoring complexity is one of the "few exceptional problems" that is known to lie "between" P and NP complete but has not been classified as either so far.

as is pointed out, the complexity was not much of an issue until it became used ("roughly") in the RSA cryptosystems in the mid 1980s where cryptographic security depends on the *assumption.* (two other "not-exactly-encouraging" related datapoints: Shors algorithm for P-time quantum factoring and primality testing was proven to be in P in the early 2000s in the famous/ celebrated AKS algorithm.) a possible positive outcome would be that its in quasipolynomial time, which is weaker than NP complete (assuming P≠NP and NP complete has an exponential time lower bound) but still technically "hard".

have not found a great survey on this key subj so far. however see also

---
Tags: complexity-theory, time-complexity, factoring, primes
---


# Question
Title: Algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A_1)$ and $y\in L(A_2)$
Let $A\_1=(Q,\Sigma,q\_0,F\_1,\delta \_1)$ and $A\_2=(P,\Sigma ,p\_0,F\_2,\delta \_2)$ a finite non determinustic automaons.

> Describe algorithm that deside if there are two words $x$ and $y$ in the same length such that $x\in L(A\_1)$ and $y\in L(A\_2)$

Hint: Intersection automaton

**My try**

To bulid the intersection automaton $L\_1\cap L\_2$ and check if $L\_1\cap L\_2 \neq \varnothing$ with $"\color{blue}{\text{emptiness problem algorithm} }"$ and if $L\_1\cap L\_2 \neq \varnothing$ so $\exists $ word $w$ such that $w \in \mathscr L(L\_1\cap L\_2)$

# Answer
Consider the NFA $A\_1=(Q,\Sigma,q\_0,F\_1,\delta\_1)$. Observe that an accepting run of $A\_1$ *induces* an accepted word. That is, we don't really care about the alphabet of the automaton if we only want to consider word length.

Thus, instead of constructing the intersection automaton directly, first change the alphabet of both automata to be $\Sigma=\\{a\\}$, by changing the letters in all the transitions to $a$. That is, for a transition $\delta\_1(q,\sigma)=q'$, change the transition to $\delta(q,a)=q'$.

Now construct the product automaton, and check emptiness.

I'm leaving the correctness proof as an exercise.
> 3 votes

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


# Question
Title: Enumerate all pairs, in order of increasing distance, efficiently
Given $n$ points in 2D, e.g., $p\_1,p\_2,....,p\_n$, there are $n^2$ possible pairs of points. I want to output the list of $n^2$ pairs, but sorted according to their distance (e.g., the pair of two points that are closest is the first pair in the output, and so on).

Is there an algorithm to do this with running time better than $O(n^2 \log n)$? If there was no metric property and the "distance" of each pair of points was unrelated to all other distances, the lower bound would be $\Omega(n^2 \log n^2)$ based on the lower bound for sorting $n^2$ values, but perhaps we can use the properties of the Euclidean distance to do better?

# Answer
> 2 votes
Consider all the point on the x-axis, then you are describing sorting $X-X$. A special case of $X+Y$ sorting(one can actually show they are equivalent in terms of running time). This is not known to be sortable in less than $O(n^2 log n)$ time. Interestingly $O(n^2)$ comparisons suffice.

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


# Question
Title: Difference in having * inside vs outside of brackets for NFA
If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^\* \cup1^\*)$ vs $(0 \cup1)^\*$ in otherwords what difference does it make for the diagram if the star is on the inside or outside of the brackets?

# Answer
Let "$\rightarrow$" stand for "denotes". Then we have

* $0\cup 1\rightarrow \\{0, 1\\}$, so
* $(0\cup 1)^\*\rightarrow \\{\epsilon, 0, 1, 00, 01, 10, 11, 000,\dotsc\\}$, i.e., all words that can be made by concatenating any number of $0$s and $1$s.
* $0^\*\rightarrow \\{\epsilon, 0, 00, 000, 0000, \dotsc\\}$, all words that can be made of just $0$s.
* $1^\*\rightarrow \\{\epsilon, 1, 11, 111, 1111, \dotsc\\}$, all words that can be made of just $1$s, so
* $(0^\*\cup 1^\*)$, the union of the two sets above $\rightarrow \\{\epsilon, 0, 1, 00, 11, 000, 111, 0000, 1111, \dotsc\\}$.

So in particular $(0^\*\cup 1^\*)$ will never contain strings with *both* $0$s and $1$s, whereas $(0\cup1)^\*$ will contain all of $(0^\*\cup1^\*)$ along with lots of other words.
> 4 votes

# Answer
Exactly the same as the difference between $x^2+y^2$ and $(x+y)^2$. You apply the ${}^\*$ to the thing the notation says you apply it to.
> 2 votes

# Answer
* = kleene star (with containing null i.e lamda its sign like ^)
* = kleene star (not containing null)

1. (Null) * (NULL)= NULL
    2. (NuLL) * a = a a * null = a

we use this formula inside or outside the DFA
> 0 votes

---
Tags: formal-languages, regular-languages, regular-expressions, notation
---


# Question
Title: If $L_1L_2$ is regular language then is $L_2L_1$ regular too?
We have two languages: $L\_1,L\_2$. We know that $L\_1L\_2$ is regular language, so my question is if $L\_2L\_1$ is regular too?

I try to find a way to prove it...

I can't assume of course that $L\_1,L\_2$ are regular...
So I look for a way to prove it.

I'd like to get any hint!

# Answer
No, $L\_2L\_1$ is not necessarily regular.

Let $L\_1 = \\{0,1\\}^\*$, which is regular, and $L\_2 = \\{1\\} \cup \\{0^n1^n\mid n\geq 1\\}$, which is not. Then $L\_1L\_2$ is the set of all strings ending with $1$, which is regular, but $L\_2L\_1$ is the set of all strings that either begin with $1$, begin with a nonzero number of $0$s followed by at least as many $1$s. This language is not regular, since its intersection with $\\{0^m1^n\mid m,n\geq 1\\}$ is $\\{0^m1^n\mid 1\leq m\leq n\\}$, which is non-regular.
> 7 votes

# Answer
I was posting only a hint, then I saw other full answers, so this is a full (hidden) succinct solution :-)

> Let $L\_1 = \\{ 1^p \mid p \text{ is prime}\\}$, $L\_2 = \\{ 1^\* 0 \\}$; we have $L\_1 L\_2 = \\{ 11^+ 0\\}$ which is regular, but $L\_2 L\_1 = \\{ 1^\* 0 1^p \mid p \text { is prime}\\}$ which is not regular.
> 13 votes

# Answer
This is not a hint, but a full answer. Don't read on if you're still trying to solve.

There is no need for $L\_2\cdot L\_1$ to be regular.

Let $A$ be a unary (non-regular) language such that $A\cdot A$ is regular. Such languages can be found in the post here. Assume $A$ is over the alphabet $\\{a\\}$.

Define $L\_1=\\{b\\}\cdot A$ and $L\_2=A\cdot \\{b\\}$. Then, you get $L\_1\cdot L\_2=\\{b\\}\cdot A^2\cdot \\{b\\}$, which is regular. However, $L\_2\cdot L\_1=A\cdot \\{bb\\}\cdot A$, which can be easily proven to be non-regular, based on $A$ being non-regular.
> 6 votes

# Answer
The following rules define the language associated with any regular expression. Rule 1 The language associated with the regular expression that is just a single letter is that one-letter word alone and the language associated with A is just {A}, a one-word language. Rule 2 If r, is a regular expression associated with the language L, and r 2 is a regular expression associated with the language L2 then,

(i) The regular expression (rl) (r2) is associated with the language L, times L 2. language (r, r2) = L1L 2 (ii) The regular expression r, + r2 is associated with the language formed by the union of the sets L1 and L2. language (rl + r2) = L, + L2 (iii) The language associated with the regular expression (rl)\* is LI\*, the Kleene closure of the set LI as a set of words. language (rl\*) = L1\*
> 1 votes

---
Tags: formal-languages, regular-languages, closure-properties
---


title: Why is $\{1^n \mid n > 1\}$ regular?

text:
# Question
Title: Why is $\{1^n \mid n > 1\}$ regular?
Given the definition of a regular language is one that can be expressed with finite memory, how is $\\{1^n \mid n \geq 1\\}$ regular? The $n$ is unbounded. I know a DFA can be drawn, which means the language is regular. But I thought another condition is that $n$ must be bounded, so it's as if the 2 tests contradict each other?

# Answer
> 3 votes
If I understand you correctly, the following comment seems to get to the heart of what you're really asking:

> A regular language is one where you can make an automata for it, or a regular expression for it. But this seems like a poor definition to me because how do you know if none exist or you just haven't been able to think it up yet?

That's a fair question. I'm afraid the answer is -- the definition is what it is. Whether you consider it poor or not, this is the standard definition of a regular language. For now, I recommend that you simply accept it and work within it. I agree that the implications are a bit.. uncomfortable. Unfortunately, that's life.

Many definitions are like this. For instance, consider the definition of what it means for a number to be prime: a number $n$ is prime if there it does not have any divisor $d$ such that $1\<d\<n$. Of course you can ask: how do you know if such a divisor exists? Maybe you just haven't been able to find one yet? The answer is that you might not know... but that's still the definition, and there are good reasons to use this definition, rather than some other.

Ultimately, there are reasons why the standard definition of regular languages is useful. Those reasons might not be obvious when you are first starting to study the material. From a computer scientist's perspective, one reason why the notion of a regular language is useful is that it corresponds to what can be accepted by an automaton with finite state, and this has many applications through computer science (parsing by compilers, model checking, and more). From a mathematician's perspective, the notion of a regular language is interesting because it has many useful properties.

But for now... accept that the definition is what it is, and there are reasons for it to be that way, and go with it.

# Answer
> 2 votes
The language $\\{1^n\mid n\>1\\}$ is regular because, although you're right that $n$ is unbounded, you don't need to know exactly what $n$ is to accept the language. You only need to be able to tell the difference between "I've seen no $1$s", "I've seen one $1$" and "I've seen more than one $1$". Indeed, these are exactly the states you need in your automaton to accept the language (plus an extra state for "I saw a $0$ somewhere").

# Answer
> -1 votes
The set of regular languages over an alphabet is defined recursively as below. Any language belonging to this set is a regular language over .

Definition of Set of Regular Languages :

Basis Clause: , {} and {a} for any symbol a are regular languages. Inductive Clause: If Lr and Ls are regular languages, then Lr Ls , LrLs and Lr\* are regular languages.

Extremal Clause: Nothing is a regular language unless it is obtained from the above two clauses.

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


# Question
Title: Show that the following construction is not a correct proof for Context Free Grammars
> Give a counterexample to show that the following constructions are not correct proofs for the star operation:
>
> Given a CFG $G = (V,Σ,R,S)$, add the new rule i) $ S → SS$ or ii) $S → SS|ε$.

For i), I basically said that this rule is an infinite loop and doesn't contain an epsilon, so can't be the star operation.

For ii) I'm stuck and can't see why it's not equivalent to the star operation

I know the real star operation is $S'→SS'|ε$ but cant seem to see find out why ii) is not the case. I can't find a counterexample.

Any help is hugely appreciated.

# Answer
$ S\to aSb \mid \varepsilon $.

Hint (due to Klaus Draeger): Consider what happens when you apply transformation (ii) to this grammar. Does the resulting grammar $G'$ satisfy $L(G')=L(G)^\*$?

Explanation: The point is that the $S\to SS$ production can be used "inside" the grammar, not just on the "top-level" where it is intended. We can derive $S\to^\* aSSb \to^\* aababb$ which is of the wrong form. (And the grammar has $S\to\varepsilon$ anyhow.)
> 2 votes

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


# Question
Title: Deamortizing a Las-Vegas randomized algorithm
Deamortization refers to the process of converting an algorithm with an amortized bound into one with a worst-case bound.

For example, assuming you need to find the median of an array once every $n$ operations of type $X$ (which does not change the array).

You could take a specific algorithm, such as the median of medians selection algorithm, which takes at most $c\cdot n$ time, and perform $c$ of its operations every time $X$ is performed. This guarantees that the worst case run time of finding the median in each $X$ call is constant.

But now assume we'd like to use a randomized Las-Vegas algorithm (always correct, runtime is computed in expectation), such as computing the median by selection with random pivot.

Now we know that the algorithm is *expected* to take $c'\cdot n$ operations, but it might take more, or less.

* **How do you determine how many of the iterations you run every time $X$ is performed?**
* **Can we say that by performing, say, $2c'$ operations every time we will finish computing the median with high probability?**
* **Can we adaptively select how many operations of the selection algorithms to perform at each of $X\_1,X\_2\ldots X\_n$ calls such that we will finish computing the median with probability $1$, but so that with high probability, the number of operations in each $X$ call is constant?**

# Answer
> 2 votes
If the expected running time of the algorithm is $c'n$, then Markov's inequality shows that for all $A$, the probability that the algorithm takes more than $Ac'n$ operations is at most $1/A$. If you run $Ac'$ operations each time then you will finish computing with probability $1-1/A$, and if you run $Ac'$ operations each time until the last step, at which you let the algorithm loose, then the number of operations will be at most $Ac'$ with probability $1-1/A$.

In some cases you know more about the distribution of the running time of the algorithm – say its variance. In that case you can get better bounds using (for example) Chebyshev's inequality.

Another trick to try is to run several instances of the algorithm in parallel with fresh coins. For example, suppose that we run $B$ independent instances of the algorithm, each for $(A/B)c'$ operations at each step. The probability that none of them finishes is at most $(B/A)^B$, compared to $1/A$ we had before. Choosing $B \approx A/e$, this improves the failure probability from $1/A$ to roughly $e^{-A/e}$.

---
Tags: randomized-algorithms, arrays, selection-problem
---


title: "Best" automaton for a regular language

text:
# Question
Title: "Best" automaton for a regular language
For a given regular language, there are multiple finite automata. How do we determine which one is best?

# Answer
> 3 votes
That's a very deep question, since you need to define what "best" means.

Let's assume, for starters, that by "best" you mean "with a minimal number of states". If you consider deterministic automata, then it is well-known that there is a unique minimal size DFA, and finding this automaton, given any DFA for the langauge, takes polynomial time.

If you consider nondeterministic automata, then there is no canonical minimal size NFA. That is, there may be two minimal size NFAs that are topologically inequivalent. The problem of determining the minimal size of an NFA for a language is PSPACE-complete (very easy reduction from NFA universality).

The above is just to get you "on track". There are many interesting algorithms regarding DFA/NFA minimization, and there are interesting complexity questions in this field.

However, there are other measures that can be used to define "best". It just so happens that I have a work on the subject, in which we define the quality of a regular language to be the expected number of "sensors" that are needed to recognize it. You can read about it here.

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


# Question
Title: non-deterministic finite automaton state transition table language question
I have the nfa problem below which I dont quite understand. I have been reading many slides on this but I'm having a really hard time understanding them enough to be able to complete the question. I can see that on the $q\_0 $ state when we have an $a$ it should stay in the $q\_0$ state and for the $q$ state when we have an $a$ it should go to the $q\_0$ state but still dont understand the other information given well enough to construct the diagram.

If anyone could help me understand the problem below it would be much appreciated.

# Answer
> 1 votes
Starting from the $M$ you gave in a comment (which you should really include in the question), we have the transition table $$\begin{array}{r|cc} \delta & 0 & 1 \\ \hline q\_0 & q\_1 & q\_2\\ q\_1 & q\_0 & q\_2\\ q\_2 & q\_2 & q\_2 \end{array}$$ with $q\_0$ the start state and $q\_1$ the final state. Now we modify this to a new NFA $M'$ by adding another final state $q'\_0$ and construct the transitions $\delta'$:

* $\delta'(q'\_0, 0) = \\{\delta(q\_0, 0), q\_0\\}=\\{q\_1,q\_0\\}$, since $\delta(q\_0,0)=q\_1\in F$
* $\delta'(q'\_0, 1) = \\{\delta(q\_0, 1)\\}=\\{q\_2\\}$, since $\delta(q\_0,1)=q\_2\notin F$
* $\delta'(q\_0, 0) = \\{\delta(q\_0, 0), q\_0\\}=\\{q\_1,q\_0\\}$, since $\delta(q\_0,0)=q\_1\in F$
* $\delta'(q\_0, 1) = \\{\delta(q\_0, 1)\\}=\\{q\_2\\}$, since $\delta(q\_0,1)=q\_2\notin F$
* $\delta'(q\_1, 0) = \\{\delta(q\_1, 0)\\}=\\{q\_0\\}$, since $\delta(q\_1,0)=q\_0\notin F$
* $\delta'(q\_1, 1) = \\{\delta(q\_1, 1)\\}=\\{q\_2\\}$, since $\delta(q\_1,0)=q\_2\notin F$
* $\delta'(q\_2, 0) = \\{\delta(q\_2, 0)\\}=\\{q\_2\\}$, since $\delta(q\_2,0)=q\_2\notin F$
* $\delta'(q\_2, 1) = \\{\delta(q\_2, 1)\\}=\\{q\_2\\}$, since $\delta(q\_2,0)=q\_2\notin F$

giving us this transition table for $M'$ $$\begin{array}{l|cc} \delta' & 0 & 1 \\ \hline \\{q'\_0\\} & \\{q\_0,q\_1\\} & \\{q\_2\\}\\ \\{q\_0\\} & \\{q\_0,q\_1\\} & \\{q\_2\\}\\ \\{q\_1\\} & \\{q\_0\\} & \\{q\_2\\}\\ \\{q\_2\\} & \\{q\_2\\} & \\{q\_2\\}\\ \\{q\_0,q\_1\\} & \\{q\_0,q\_1\\} & \\{q\_2\\} \end{array}$$ with $\\{q'\_0\\}$ the start state and $\\{q'\_0\\}, \\{q\_1\\}, \\{q\_0,q\_1\\}$ the final states. Notice that $\\{q\_0\\}$ and $\\{q\_1\\}$ are unreachable so can be eliminated from the NFA. Notice also that in both FAs, state $q\_2$ is a "trap" state: once you enter it (on input $1$), you'll never leave. This means that neither FA will accept any string containing a $1$ and from there it's not too hard to see what $L(M)$ and $L(M')$ are.

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


title: Regular Grammar and Regular Language

text:
# Question
Title: Regular Grammar and Regular Language
My doubt is based on the relation between regular grammar and regular languges

$S \to Sa\ |\ a$ produces the regular language $a^+$ but this grammar is not type-3 grammar of Chomsky classification. So am I correct in stating that this is not a regular grammar even when it produces regular language?

# Answer
Let me quote the wikipedia entry for linear grammar:

> Two special types of linear grammars are the following:
>
> 1. the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends
> 2. the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.
>
> Collectively, these two special types of linear grammars are known as the regular grammars; both can describe exactly the regular languages.

As you can see, your grammar is a left-linear grammar, and it generates a regular language. Type-3 grammars of the Chomsky hierarchy can be defined as right-linear grammars or as left-linear grammars, as you prefer.
> 6 votes

# Answer
Also notice that the grammar $G$ with the following production rules: $$S\rightarrow aSa | aS |a$$ Generates the regular language $a^+$: $$L=\mathscr{L}(a^+)=L(G)$$ But $G$ is a context-free grammar(type 2). This is perfectly fine because a regular grammar always generate a regular language but a regular language can be generated by all types of grammar in the Chomsky's Hierarchy.
> 4 votes

---
Tags: regular-languages
---


# Question
Title: Machine Learning: What program will derive the underlying algorithm in this series?
This is a machine learning question. Given this series of categorical data, what program will derive the underlying algorithm and predict what comes next in the series?

Here is the series:

B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, ...

Anyone with knowledge of computer science may quickly realize that this series is simply counting in binary with "A" substituted for "0" and "B" substituted for "1". This is true, but...

the program that predicts what comes next must do so **only by manipulating the symbols given** in the series. It must not use hard-coded knowledge of binary counting.

I realize many patter recognition algorithms are available but I haven't seen how any can solve this deceptively hard problem.

-Edit-

Based on the votes that this problem is insolvable, I've done some refactoring and posed the question another way, with more constraints, here: What program will derive the underlying algorithm in these question-answer pairs (updated)?

# Answer
Without any a priori knowledge, the problem is insoluble. There are infinitely many possible answers and you have no wat at all to say that one of them is preferable to any of the others. How can you possibly tell just by manipulating symbols that the sequence is "Counting in binary using A and B for 0 and 1" rather than "B, BA, BB, BAA, BAB, BBA, BBB, BAAA, BAAB, BABA, BABB, BBAA, widgeon, 27, expunge" followed by a list of the squares of every third prime, number written in base-14 using Hebrew letters instead of the even digits?

Wait – how would you even know that there is a next element?
> 6 votes

# Answer
Here it is not machine learning anymore but some sort of deep/hard artificial intelligence. The problem could be stated as :

« given that infinite sequence (the program can get as many terms as it wants) what is the **shortest algorithm** (or program, **given a programming langage**) capable of generating that sequence » ? (because it is an infinite sequence you are never 100% sure, but you can affect a probability of correctness once the first $10^N$ terms have been generated correctly)

You are still able to try all the possible programs (let's say in a small subset of the C language) and wait until you find one which generates correctly the 100000 first terms,

but this is not a fully satisfactory solution (is it a matter of complexity, because trying randomly all the possible programs is exponential in time with respect to the size ? could an AI do better than that ?).
> 0 votes

---
Tags: machine-learning, artificial-intelligence
---