# Question
Title: Proof that uniform circuit families can efficiently simulate a Turing Machine
Can someone explain (or provide a reference for) how to show that uniform circuit families can efficiently simulate Turing machines? I have only seen them discussed in terms of specific complexity classes (e.g., $\mathbf{P}$ or $\mathbf{NC}$). I would like to see how uniform circuit families is a strong enough model for universal, efficient computation.

# Answer
> 1 votes
Here is the basic idea. We'll take P as an example.

Given a Turing machine running in polynomial time, we construct, for each input length, a layered circuit in which each circuit represents the current configuration of the Turing machine:

* For each cell, the contents of the cell.
* For each cell, whether the head is there.
* The current state of the machine.

The number of layers is the same as the polynomial upper bound on the running time, and the width of each layer (number of cells) is the maximum space used by the machine.

The initial layer is initialized directly from the input. Each other layer is constructed from the preceding layer (using the convention that once the machine halts, its configuration remains static). Finally, the output is extracted from the last layer. The construction is uniform, as the description hopefully makes clear.

---

This shows that you can convert Turing machines running in time $T(n)$ and space $S(n)$ to uniform circuits of size $O(T(n)S(n))$. This can likely be improved.

# Answer
> 0 votes
Let us prove the following theorem:

> A language $L$ is decidable if there is a Turing machine $T$ that on input $n$ outputs a circuit for $L \cap \\{0,1\\}^n$.

$\Longrightarrow$ Suppose that $L$ is decidable. Given $n$, we can compute $L \cap \\{0,1\\}^n$. We can then construct a circuit for the corresponding Boolean function.

$\Longleftarrow$ Suppose that there is a Turing machine $T$ than on input $n$ outputs a circuit for $L \cap \\{0,1\\}^n$. To decide $L$, given an input $x$, run $T(|x|)$ to get a circuit for $L \cap \\{0,1\\}^{|x|}$, and run it on $x$ to determine whether $x \in L$.

---
Tags: complexity-theory, computation-models, complexity-classes, circuits
---


# Question
Title: Help in understanding 'reasonable' encoding of inputs
I read that a reasonable encoding of inputs is one where the length of the encoding is no more than a polynomial of the 'natural representation' of the input. For instance, binary encodings are reasonable, but unary encodings are not.

But say that the input is a graph, and its natural representation is a vertex and edge list. Suppose that the graph has $k$ vertices. If I use unary to encode, the overall length of the input referring to the vertex list would be $O(k^2)$, i.e. $=|1^1|+|1^2|+|1^3|+...+|1^k|$. Isn't this unary encoding still a polynomial with respect to the number of vertices of the graph (which is $k$)?

What am I missing here?

# Answer
> 1 votes
Unary encoding for values 0 \<= k \<= N takes O(N) space. Unary encoding of an n-bit number takes $\Theta(2^n)$ space. See the difference?

---
Tags: graphs, turing-machines, time-complexity, encoding-scheme
---


# Question
Title: An approach to determine whether language is regular or not?
I have the following problem. I need to determine whether this language is regular or not:

$L:= \\{ w \in \Sigma^\*: \forall \alpha ∈ \Sigma, |w|\_\alpha \text{ is even or divisible by 3}\\}$

$|w|\_\alpha$ =\> $|w|$ is the length of the word $w$ and $|w|\_\alpha$ is the number of $\alpha$ characters in that word.

For example: $w$ = 100111 =\> $|w|$=6, $|w|\_0$ = 2, $|w|\_1$ = 4.

I know that I need to use deterministic/non-deterministic finite automata, regular expression/grammar to prove that it is regular or to use pumping lemma to prove that it is not.

But I'm not sure how to approach this problem to start proving something. Is this trial and error method or is there some way to know from the start?

I appreciate your help!

# Answer
> 4 votes
I'm not aware of any completely "algorithmic" method to decide whether a language is regular.

For the specific language you are interested in, you can start by observing that it can be written as combination of unions and intersections of a finite number of regular languages: $$ \bigcap\_{\alpha \in \Sigma} \left( L\_{2,\alpha} \cup L\_{3,\alpha} \right), $$ where:

* $L\_{2,\alpha}$ is the language containing all words $w$ such that $|w|\_\alpha$ is divisible by 2.
* $L\_{3,\alpha}$ is the language containing all words $w$ such that $|w|\_\alpha$ is divisible by 3.

It is easy to show that all these languages are regular (since, in each language, $\alpha$ is now fixed). A DFA for $L\_{2,\alpha}$ has two states $q\_0, q\_1$ where $q\_i$ means that the number of characters equal to $\alpha$ encountered so far is $i$ modulo 2. A DFS for $L\_{3,\alpha}$ is similar but has $3$ states.

The regularity of $L$ follows from the fact that regular languages are closed under union and intersection.

# Answer
> 4 votes
This type of question often rises when starting to learn the theoretic aspect of computer science.

The answer, which may seem unfortunate at first, is that *there is no algorithmic way of determining whether a language is regular*. Moreover, there will **never** be an algorithmic way, no matter what advances in computers the future may bring, and how many clever people try to come up with algorithms.

Now, this is a pretty strong claim, so I should back this up. Technically, the reason for this is that the problem of determining, given a Turing Machine, whether its language is regular, is undecidable. Presumably, since you're just getting into automata theory, you're not familiar with undecidability yet. But when you will be, this will all make sense. Also, it will all be very very exciting, as these results are simply mind blowing (in my opinion).

As an additional note, the question "is a given language regular?" should be carefully formulated. Specifically, *how* is the language given?

* If it's given by an automaton -- then it's regular (but that's just silly).
* If it's given by a regular expression -- then it's regular (but that requires some work to prove).
* If it's given by a Turing Machine -- it's undecidable whether it's regular.
* If it's given by a different model, the it depends. For example, for CFG's, the problem is still undecidable. But for simpler models it may be decidable.

I guess all of this is not what you were aiming at with your question, since you were probably given a certain language described in English, and you're just trying to get intuition on whether it's regular. The good news on this front, is that by the time you solve 10 such questions, you'll probably have enough intuition for all the exercises you'll be given.

A good rule of thumb is that regular languages cannot "count" arbitrarily. They can count up to a fixed number (e.g., couting modulo 6, counting up to 13, etc.) but they cannot e.g., compare the number of a's to the number of b's.

# Answer
> 2 votes
How would you prove that L is regular? You can prove it by giving a regular expression or a finite state machine. And we know that finite languages are regular, and if L1 and L2 are regular then the complement of L1, and the union or intersection of L1 and L2 are regular, and with that finite set operations between regular languages are regular.

How would you prove that L is not regular? A common approach is this: Assume that you have a finite state machine for L. If Ax is in L and Bx is not, then parsing either A or B from the initial state must end in different states. If we can use this to prove that the set of statea is not finite, then L is not regular.

Why would these approaches fail? The language L must be specified in some way. If it is given by a context free grammar (CFG) for example, and we find a regular expression for it, then we have the problem that it is undecidable whether a CFG and a regular expression specify the same language!

On the other hand, given the description of a language we might find it hard or impossible to decide if a string belongs to a language at all. Take {$a^n: $There are infinitely many primes p such that p+n is also prime}. We don’t know if aa belongs to the language (that's the twin prime conjecture), but we know aaa doesn’t. That’s just two hard things you’d be up against if you wanted to find a general method to decide regularity.

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


title: Lower bound and worst case scenario

text:
# Question
Title: Lower bound and worst case scenario
We know that the lower bound is the minimum amount of work needed to solve a problem. So for a given problem say x it has the best algorithm ( the most efficient algorithm to solve this problem ) say algorithm y, then the lower bound efficiency calculated from this algorithm y is the least time this problem x can be solved through . So why do we calculate the lower bound efficiency for this algorithm on the worst case input ? why not on the best case input ? I mean lower bound is the minimum amount of work which therefore occurs on the best case scenario . Every time I see a decision tree algorithm problem to solve the lower bound of some sorting algorithm , the usual word is always mentioned "the worst case lower bound is blah blah blah" which confuse me so much ! Someone please fix my understanding :( .

# Answer
> 3 votes
When analyzing algorithms it makes little sense to consider the best-case scenario as it is very often trivial and not very informative.

You can convince yourself that almost every algorithm can be adapted to have a best-case complexity of $O(n)$, where $n$ is the size of the input, by simply running a preliminary check that verifies if the input instance belongs to some class of instances for which the solution is trivial.

Just to give a concrete example: the best case for every sorting algorithm can be made $O(n)$ if you just check whether the input sequence of numbers is already sorted.

The focus is often on the worst-case complexity. Once you decide that you want to compare algorithms with respect to their worst-case complexity, it also makes sense to ask how quickly a problem can be solved.

It is usually impossible to give a sharp bound to the time needed to solve a problem, therefore one seeks upper and lower bound.

An upper bound of $O(f(n))$ tells you that there is some algorithm that solves the problem in $O(f(n))$ worst-case time.

A lower bound of $\Omega(g(n))$ tells you that **no conceivable algorithm** can take $o(g(n))$ time to solve the problem.

Just to be clear: a lower bound on the time needed to solve a problem is expressed as a function of the input size $n$ and is the smallest amount of work that is necessary to solve **all instances** of size $n$. Intuitively (not a formal definition) you can think of it as $\min\_{A \in \mathcal{A}} \max\_{I \in \mathcal{I}\_n} T(A,I)$ where $\mathcal{A}$ is the set of all possible algorithms that solve your problem, $\mathcal{I}\_n$ is the set of all instances of size $n$, and $T(A,I)$ is the time needed by $A \in \mathcal{A}$ to solve instance $I \in \mathcal{I}\_n$.

What you seem to have in mind instead is $\min\_{A \in \mathcal{A}} \min\_{I \in \mathcal{I}\_n} T(A,I)$.

A lower bound for a problem is useful to establish how "hard" that problem is to solve (problems that require more time to solve are harder, this would make little sense if we looked at the easiest instances instead), and to measure how far an algorithm is from being optimal. For example Merge Sort solves the sorting problem in the optimal amount of time because its running time (asymptotically) matches the $\Omega(n \log n)$ lower bound for the sorting problem (in the comparison-based model).

# Answer
> 0 votes
"lower bound" can be applied for each scenario and individually not meaningful! (lower bound of what?) As we analyzed the worst-case scenario most of the time as time complexity of an algorithm, hence, "lower bound" is applied for the worst-case scenario (not the best case). In other words, as the time complexity is explaining for the worst-case scenario, "lower bound" for the time complexity will be applied to the worst-case scenario.

---
Tags: algorithms, lower-bounds, decision-tree
---


# Question
Title: Prove that if $p_1 \times p_2$ is positive, then $p_1$ is clockwise from $p_2$?
In Introduction to Algorithms (CLRS), Exercise 33-1-1, we are asked to prove that if $p\_1 \times p\_2$ is positive then $p\_1$ is clockwise from $p\_2$ and if it's negative, then $p\_1$ is counter-clockwise from $p\_2$.

This is a picture from CLRS

I found the following proof: https://sites.math.rutgers.edu/~ajl213/CLRS/Ch33.pdf

The proof above says to consider the angles both vectors make with the x-axis. We know the angle is $\arctan y/x$. We also know the cross product $p\_1 \times p\_2 = x\_1y\_2 - y\_1x\_2$. If this product is greater than zero, then this means that $y\_2/x\_2 \> y\_1/x\_1$. Since $\arctan$ is monotone then the angle $p\_2$ makes with the x-axis is larger. **which means you need to move clockwise direction to get from $p\_2$ to $p\_1$**

BUT the question is asking to prove that $p\_1$ is clockwise relative $p\_2$. What am I missing? is the above proof wrong?

I drew the following based on the proof above:

# Answer
> 2 votes
In two-dimensional space, $p\_1 \times p\_2$ is equal to $|p\_1||p\_2|\sin\theta$, where $\theta$ is the angle from $p\_1$ to $p\_2$. Depending which textbook you're using, this is probably the definition of the two-dimensional cross product—I'm not sure what definition *Introduction to Algorithms* uses.

$|p\_1|$ and $|p\_2|$ both have to be non-negative (by the definition of vector magnitude), so if neither of them is zero, the sign of the whole expression will be the sign of $\sin\theta$.

Now, how do we define "clockwise"? The easiest definition I know is is, $p\_1$ is clockwise from $p\_2$ if the angle(\*) from $p\_1$ to $p\_2$ is less than 180 degrees. Try a few examples and you'll see how this definition works—remember that angles are traditionally measured with counter-clockwise being positive.

Now, we know that if $p\_1 \times p\_2$ is positive, then $\sin\theta$ must be positive. And if $\sin\theta$ is positive, then $\theta$ must be less than 180 degrees(\*). So by the definition of clockwise, $p\_1$ is clockwise from $p\_2$.

(\*) I'm assuming without loss of generality that all angles are positive and less than 360 degrees.

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


# Question
Title: Detecting a cycle in an undirected graph and printing the vertices if there is a cycle, printing no cycle otherwise
Problem: Find an O(E + V) time algorithm that outputs the vertices of a cycle of G, if it exists. If G has no cycles, the algorithm outputs no cycle. So if there is a cycle 1, ... 3, 1, it would print 1, ..., 3, 1.

So I was thinking of doing a BFS, and if the currently examined vertex's neighbor v has been visited prior, then there is a cycle. However, I am not sure how I might go about tracking the vertices in order to print. I believe I would have to view the BFS-Tree, but unsure.

# Answer
> 2 votes
You've basically got it!

The usual way to record the cycle is to mark the *predecessor* or *parent* of each node: that is, the node from which it was first visited. Then you can follow the trail of parents to print out the cycle.

---
Tags: algorithms, graphs
---


# Question
Title: Reducing Vertex Cover to Half Vertex Cover
I need to reduce Vertex Cover to Half Vertex Cover using a Karp reduction:

Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects all edges?

Half Vertex Cover: Given a graph $G = (V,E)$ and an integer $k$, is there a subset of $V$ of size $k$ which intersects exactly half the edges?

I will be happy if you can tell me how to do that and why the reduction works (both directions of the proof).

# Answer
> 3 votes
Let *special vertex cover* be the special case of vertex cover in which $|V| = 2k+1$. We later reduce vertex cover to special vertex cover.

Now suppose we're given an instance $G = (V,E),k$ of special vertex cover. Construct an instance $G',k$ of half vertex cover by attaching $|E|$ new edges to each vertex in $V$.

The total number of edges in the new graph is $|E|(|V| + 1)$. A vertex cover of size $k$ in the original graph covers this many edges in the new graph: $$ |E|(1+k) = |E|\left(1 + \frac{|V|-1}{2}\right) = |E| \frac{|V| + 1}{2}, $$ exactly half the edges. Conversely, consider any $k$ vertices of the new graph, which cover exactly half of the edges. If they cover $m$ of the original edges then they cover at most $m + k|E|$ edges of $G'$, where $m \leq |E|$. The calculation above shows that $m = |E|$, that is, all edges of $G$ are covered.

It remains to reduce vertex cover to its special case. If $|V| = 2k+1$ then there is nothing to do.

If $|V| \< 2k+1$, then we add $\delta := 2k+1 - |V|$ many paths of length 2 edges. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + \delta$ iff the original graph had a vertex cover of size $k$. Note that $$ |V'|-2k' = (|V| + 3\delta) - 2(k+\delta) = |V| - 2k + \delta = 1. $$

Similarly, if $|V| \> 2k+1$ then we add $\delta := |V| - (2k+1)$ many triangles. The new graph $G'=(V',E')$ has a vertex cover of size $k' = k + 2\delta$ iff the original graph had a vertex cover of size $k$. Note that $$ |V'|-2k' = (|V| + 3\delta) - 2(k+2\delta) = |V| - 2k - \delta = 1. $$

# Answer
> 2 votes
In addition to the reduction given by Yuval Filmus, you can also use the following reduction, which avoids blowing up the size of $G$ to $\Theta(|V| \cdot |E|)$.

Assume w.l.o.g. that $k\<|V|$ (otherwise the reduction is trivial) and that the instance (graph) $G = (V,E)$ of vertex-cover contains a vertex $v \in V$ of degree $1$ (otherwise you could append a path of length $2$ to any vertex and increase $k$ by $1$).

To obtain an instance $G'$ of half-cover attach to $v$ $|E|$ new edges (towards new nodes), so that $G'$ has $2|E|$ edges.

If there is a vertex cover of size $k$ in $G$, then there is also a vertex cover $C$ of size $k$ that does not include $v$. Then, $C$ intersects $|E|$ edges in both $G$ and $G'$, i.e., half the edges of $G'$.

On the converse, if there is a half-cover $C'$ of size $k$ for $G'$ then $v \not\in C$ (since the degree of $v$ is $|E|+1$), and hence $C' \subseteq V$ covers all $\frac{2|E|}{2} = |E|$ edges in $E$.

---
Tags: complexity-theory, reductions, vertex-cover, polynomial-time-reductions
---


title: Computing the partition function

text:
# Question
Title: Computing the partition function
Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the **complexity class** of this problem as a function of $n$?

Perhaps I'm missing something trivial here, but other than listing some recurrent definitions of this function and some of their asymptotics, I don't see this precise information (complexity class, and known algorithms with their runtime/space complexity) in either of these articles:

# Answer
Johansson gave a nearly linear time algorithm (in terms of the output size!) in his paper Efficient implementation of the Hardy-Ramanujan-Rademacher formula. This work is mentioned at the very end of the Wikipedia article on the partition function.
> 4 votes

---
Tags: algorithms, time-complexity, reference-request, partitions
---


title: Interval sorting that avoids covering

text:
# Question
Title: Interval sorting that avoids covering
I have a collection of intervals and I want to sort them so that the order is interpreted as a sort of "z-index". That is, a given interval may or may not be "visible" depending on whether the merge of the intervals to its left (i.e. preceding it in the given order) contains it.

I am looking for an algorithm to search the optimal ordering, that maximizes the number of visible intervals.

Context: the intervals are spans of text (that all contain a given keyword) and I want to color them *using CSS cascading behavior* so that all regions are at least partially visible.

### Example

A phrase: "The quick brown fox jumps over the lazy dog"

The intervals: \["quick brown fox", "fox", "fox jumps over", "fox jumps over the lazy dog"\].

An optimal sorting: \["fox", "quick brown fox", "fox jumps over", "fox jumps over the lazy dog"\] (all 4 intervals are "visible")

Non optimal sortings: for instance, any sorting where "fox" is not the first element (so there'd be at most 3 visible intervals).

# Answer
If no two intervals end at the same point then you can simply sort them in increasing order of their right endpoint, and all of them will be visible.

If more than two intervals can end at the same point, then sort the intervals $\[a,b\]$ in increasing order of $b$ and break ties in decreasing order of $a$.

Assume w.l.o.g., that there are no identical intervals (you can discard multiple copies of the same interval, since at most one copy will ever be visible). We will show that the above algorithm is optimal with an exchange argument. Suppose that an optimal order $S$ of the intervals places two intervals in a different order than the one computed by the algorithm. Let $\[a,b\]$ and $\[a',b'\]$ be the first two consecutive intervals in $S$ that are in the "wrong" order, that is:

* $b\>b'$; or
* $b=b'$ and $a\<a'$.

we will show that $\[a,b\]$ and $\[a',b'\]$ can be swapped without decreasing the number of visible intervals.

If $\[a,b\]$ is not visible, then swapping $\[a',b'\]$ with $\[a,b\]$ cannot decrease the number of visible intervals. Therefore we assume that $\[a,b\]$ is visible. Let $p \in \[a,b\]$ be the largest point that is not covered by any the intervals preceding $\[a,b\]$.

If $p \not \in \[a',b'\]$, then swapping $\[a',b'\]$ with $\[a,b\]$ yields a solution $S'$ in which (i) $\[a,b\]$ is visible in $S'$, and (ii) if $\[a',b'\]$ is visible in $S$ then it is visible in $S'$. Assume then that $p \in \[a',b'\]$.

If $\[a',b'\]$ is not visible then swapping $\[a',b'\]$ with $\[a,b\]$ yields a solution in which $\[a',b'\] \ni p$ is visible (therefore the number of visible intervals cannot decrease). Assume then that $\[a',b'\]$ is visible.

If $\[a,b\] \supset \[a',b'\]$ then $\[a',b'\]$ would not be visible, therefore we are in the first case ($b\>b'$). By the choice of $p$, all the points of the subinterval $(p,b\]$ of $\[a,b\]$ are not visible. Therefore $S$ must contain an interval $\[a'',b''\]$ that precedes $\[a,b\]$ and is such that $b'' \ge b$ and $a'' \> p$. This cannot happen since $\[a'', b''\]$ and $\[a, b\]$ is a pair of intervals in the wrong order which appears before the pair $\[a,b\]$ and $\[a', b'\]$ in $S$.
> 2 votes

---
Tags: sorting, intervals
---


# Question
Title: How interpret the notation $f:\{0,\dots, N-1\} \rightarrow \{0,\dots, N-1\}$, $N$ is a number of the form $2^n$?
I need help how to interpret the following notation for $f$:

> Zeroes and ones form a binary number which can be converted to decimal notation. Thus, we may think of the computer as calculating a function $$ f:\\{0,\dots, N-1\\} \rightarrow \\{0,\dots, N-1\\}, $$ where $N$ is a number of the form $2^n$, and $n$ is the number of bits in the computer memory. In this description, $f$ must be a function because the computer cannot generate two or more different outputs from the same input. We assume without loss of generality that the domain and codomain of $f$ are of the same size. In other words, we assume that both the input and the output of the computer have the same number of bits.

***Update:***

*I understand the function notation \begin{align} f&:\mathbb R \rightarrow \mathbb R\_+ \\ x& \mapsto f(x) \end{align} so if $x\in \mathbb R$ we have $f(x)\in\mathbb R\_+$. So far so good.*

*However I don't follow the meaning (mapping) of $\\{0, \dots, N-1\\}$ in this case.*

**Attempt 1:**

Say I have the decimal number $5$, so $N= 5$. I guess "of the form $2^n$" means a binary number, i.e. $5\_{10}=(0101)\_2$ and thus $n=4$. So I have the function $$ f: \\{0, 1, 2, 3, 4\\} \rightarrow \\{0, 1, 2, 3, 4\\} $$

Is this correct?

**Attempt 2:**

Is the domain and codomain of $f$ a binary number? I.e. **no commas in the sets** $$ f: \\{0101\\} \rightarrow \\{0101\\} $$

Thanks in advance!

# Answer
> 0 votes
A function $f\colon \\{0,\ldots,N-1\\} \to \\{0,\ldots,N-1\\}$ accepts an input from $\\{0,\ldots,N-1\\}$ and outputs something from $\\{0,\ldots,N-1\\}$. Just like any function $f\colon A \to B$.

In this case, we are interested in $N$ of the form $2^n$. That is, we are interested in values of $N$ such that $N = 2^n$. For example, $N = 256$. We *identify* the set $\\{0,\ldots,N-1\\}$ with the set of binary strings of length $n$, using binary notation. For example, if $N = 8$, then the interpretation works as follows:

* 0 is interpreted as 000.
* 1 is interpreted as 001.
* 2 is interpreted as 010.
* 3 is interpreted as 011.
* 4 is interpreted as 100.
* 5 is interpreted as 101.
* 6 is interpreted as 110.
* 7 is interpreted as 111.

As an example, the complementation function $f\colon \\{0,\ldots,7\\} \to \\{0,\ldots,7\\}$ is given by $f(x) = 7-x$. You can check that it corresponds to complementing the binary representation of the input.

---
Tags: algorithms, complexity-theory, automata, discrete-mathematics, boolean-algebra
---


# Question
Title: Counting pairs of intervals where one is a subset of the other
Given a list of intervals with nonnegative endpoints, e.g. $ \[3,5\]\[1,7\]\[2,60\] $, the goal is to find the number of pairs of intervals $I,J$ such that $I$ is a subset of $J$. In this particular case the total number is 2 because $\[3,5\]$ is a subset of $\[1,7\]$ and a subset of $\[2,60\]$. Furthermore we were asked to find a solution to this problem with time complexity less than $O(n^2)$.

At first I thought of sorting the given sets based on their lower bound and in this example the order would be $ \[1,7\] \to \[2,60\] \to \[3,5\] $ so the time complexity so far is $O(n\log n)$, but I can tell nothing about the total number of pairs cause of the order of the upper bounds of the sets is a mess. Then I thought of sorting them based on their middle element and then performing a Binary Search based on this sorting so my time complexity would still be $O(n\log n)$. However now I am stuck and a direction would be appreciated.

# Answer
> 1 votes
Sort all endpoints of intervals, and maintain a self-balancing order statistic tree, initially empty. Scan the endpoints from left to right. Add each left endpoint to the tree. When reaching a right endpoint, determine the order statistic of the left endpoint, and then remove the endpoint. Update the number of intersections accordingly: if the left endpoint was that $i$th smallest element (counting from $1$), then add $i-1$.

Since each operation on a self-balancing order statistic tree takes $O(\log n)$, the entire algorithm runs in $O(n\log n)$.

As an example, consider your list of intervals.

* Initially, the tree is empty, and the counter is 0.
* Read left endpoint of \[1,7\]. Tree contains 1.
* Read left endpoint of \[2,60\]. Tree contains 1,2.
* Read left endpoint of \[3,5\]. Tree contains 1,2,3.
* Read right endpoint of \[3,5\]. Since 3 is the third smallest point, increase counter by 2. Tree contains 1,2.
* Read right endpoint of \[1,7\]. Since 1 is the smallest point, increase counter by 0. Tree contains 2.
* Read right endpoint of \[2,60\]. Since 2 is the smallest point, increase counter by 0. Tree is empty.

---
Tags: algorithms
---


# Question
Title: Why is this verifier for primality wrong?
We are provided with the following verifier of primality:

```
Verifier for prime

Input: integer n ≥ 1
       integer d

if 1 < d < n and d divides exactly n then
    return ’no’
else
    return ’yes’

```

But the answer is that it is wrong:

> Note that in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’. However, in the algorithm for Primes we have that n is a negative instance if and only if there exists one d such that the verifier with input n and d returns ’no’.

But I do not understand this answer or why "in order to be a verifier it is required that for every n, n is a positive instance (that is, n is a prime) if and only if there exists one d such that the verifier with input n and d returns ’yes’"

# Answer
Here are the semantics of a verifier for primality. The verifier gets two inputs, an integer $n$ and a witness $w$. The following two properties must hold"

* Soundness: if the verifier accepts $n$ and $w$, then $n$ is prime.
* Completeness: if $n$ is prime, then there is a witness $w$ such that the verifier accepts $n$ and $w$.

We also usually ask that the verifier run in polynomial time *in $n$*.

Your verifier isn't sound (take any odd composite $n$ and $d = 2$) but is complete.

However, if you flip the return value, you do get a verifier for compositeness:

* If $d \mid n$ and $1 \< d \< n$ then $n$ is composite.
* If $n$ is composite then there exists $d$ such that $d \mid n$ and $1 \< d \< n$.

The notion of a verifier is asymmetric. Your verifier works for compositeness, but not for its complement, which is primality.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Is there a difference between the equivalent automaton of a grammar and an automaton which accepts the language produced by the grammar?
I have been assigned some homework in uni, related to push-down automatons (evaluated via final state, not empty stack) and context-free grammars. I have noticed that questions related to generating push-down automatons from context-free grammars are not always phrased in the same way, with mostly two variations:

1. For the given grammar G, define a push-down automaton M such that L(M) = L(G)
2. For the given grammar G, define a push-down automaton M equivalent to grammar G.

In *Introduction to Automata Theory Languages and Computation* by John Hopcroft, in section 6.3.1 a method to obtain the equivalent push-down automaton for a context-free grammar is defined. Since the book is widely available and very well known, I will not copy the method here.

Of course, it is also possible to figure out the language produced by the grammar and work from there to define an automaton which accepts that language (this would be similar to the first phrasing).

These two method would produce equivalent automatons (i.e. automatons which accept the same language), but I am not sure if there is something that tells them apart.

Is there a theoretical difference between "the push-down automaton equivalent to a context-free grammar" and "the push-down automaton which accepts the language defined by a context-free grammar"?

# Answer
> 5 votes
The answer is really up to the definition of *equivalent*. The common definition is that two automata/grammars are equivalent if they define the same language. If your class uses the common definition, then both statements are entirely equivalent.

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


# Question
Title: A Question related to the method of find lower bound : Trivial lower bounds
In Trivial lower bounds we just need to count the number of items in the input that needs to be processed and the number of items that need to be generated and the trivial lower bound time is then the sum of these two found numbers. My question is , we know that the time complexity = number of times the basic operation is repeated as a function of the input size * the time it is taken to preform the basic operation once. So as we can see from the formula of the time complexity that it depends on the basic operations not on the number of inputs and output items. So how does the trivial solution is used to compute the lower bound ( worst time complexity of best algorithm) then ?

# Answer
> 1 votes
The trivial bound assumes that the program has to read the entire input. This is usually, but not always, the case. Similarly, it assumes that the program has to write each output item separately. This is usually, but not always, the case.

Since the program has to read the entire input, it has to do some operation for each input item. Similarly, it has to so some operation for each output item. This gives you the trivial bound, in terms of the number of basic operations.

Since we are usually only interested in complexity up to constant factors (big O complexity), the actual time that a basic operation takes doesn't enter the picture at all.

---
Tags: algorithms, time-complexity, lower-bounds
---


# Question
Title: Why do we need to connect the computers to a LAN cable when we can use the internet
why don't we put a network card or usb adapter to connect to wifi and connect all the computer to the internet without LAN and WAN cables i may act stupid so please explain it to me my friend

# Answer
> 0 votes
Using a cable, you can get up to ten gigabit per second transfer rates. WiFi is much slower. In addition, in one area you can only use at most three WiFi channels at the same time, so in an office with 100 computers you have a problem.

You can also run Ethernet over 100 meters with good cables, try that with WiFi.

---
Tags: computer-networks
---


# Question
Title: Decision tree and information-theoretic lower bound
Consider the following problem :

```
Consider the problem of finding the median of a three-element set {a, b, c}.
a. What is the information-theoretic lower bound for comparison-based
algorithms solving this problem?
b. Draw a decision tree for an algorithm solving this problem.

```

The answer of this problem is shown below :

My problem is with number a. According to my understanding the information theoretic lower bound = ceil (log2(2!)) , so in this question it should be equal to ceil (log2(6)) =3 because here we have 6 leaves not 3 ?

# Answer
No. The outcome is the median, not the sorted list. Thus, there are only 3 possible outcomes, not 3! outcomes. The information-theoretic lower bound says that if there are N possible outcomes, then it takes at least $\lceil \lg N \rceil$ comparisons. (Proof: given $k$ comparisons, you can only produce $2^k$ different outcomes.) Here $N=3$.
> 1 votes

---
Tags: lower-bounds, decision-tree
---


title: Does an algorithm have to terminate?

text:
# Question
Title: Does an algorithm have to terminate?
I was reading about the *finiteness property of an algorithm* where it is mentioned that

> the algorithm must always terminate after a finite number of steps.

Does this mean that any pseudo-code cannot contain infinite loops or it should be equivalent to Halting Turing Machine. I don't know whether the statement about finiteness property of an algorithm is correct or not. I have not found any reliable source for it and I have not read it in CLRS.

**My question is** whether the statement and whether my interpretation about it is correct:

> An algorithm must always terminate after a finite number of steps

**References:**

# Answer
Yes, an algorithm should always stop after a finite number of steps, otherwise we would call it a procedure or process or computation specification. A *procedure* that doesn't halt for certain inputs can be considered partial algorithms. Algorithms are more useful, since they terminate for any input.

An algorithm can be viewed as a function $f: \mathbb{N} \to \mathbb{N}$. if it is defined for all input values, we say that $f$ is *"total"* ; for an algorithm, it means that it halts for any input. On the other hand, if a function $f$ is "undefined" for an input, say $4$, we say that $f$ is a partial function, and in computation theory, we write $f(4)\uparrow$ meaning it "diverges", or simply "doesn't halt".

An example for a partial function can be the *inverse* of the *integer square* function, i.e. $sq(n) = n^2$. The inverse, $sq^{-1}$ is defined only on perfect squares, that is, $$sq^{-1}(n) = \cases{\sqrt{x} \text{ if $x$ is a perfect square} \\ \text{undefined otherwise.}}$$
> 5 votes

# Answer
I find this a particularly interesting question, one that I have pondered myself a couple of times.

The set of algorithms is usually defined as consisting of a finite number of instructions, and also executing in a finite number of steps. In other words, algorithms halt. But the halting problem also says that if someone is presented with a finite set of instructions, there is no universally applicable decision procedure to figure out if it actually will finish executing, i.e. whether it is an actual algorithm.

For instance, in

http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

"unbounded algorithm" would be a *contradictio in terminis*.

I personally advocate dropping the finiteness requirement from the definition of an algorithm. An algorithm must consist of a finite number of instructions, but it does not necessarily terminate in a finite number of steps. This definition avoids getting into a mess.

```
for (i = 0; i < 1e99; i++)
        puts("This is an algorithm");

while (true)
        puts("This is not an algorithm");

```

Just doesn't add up.
> 2 votes

# Answer
Well, I could write a program that will print all the Fermat primes in ascending order, given enough time. A tiny change: Make it print the first 40, 41, 42, etc Fermat primes and it becomes an algorithm. So you can say “it’s not *exactly* an algorithm, but as good as”.

Or I write software connected to a camera that detects known wanted criminals. You’d want that software forever, so it’s not an algorithm. Change it to stop running after 100 billion years, and it becomes an algorithm.

So finite number of steps is a technical requirement for an algorithm, but in practice it’s not very relevant. (Of course if I take any problem and add “stop after 10 billion years” then the Halting Problem for this program is easy. Deciding whether it halts in less than 10 billion years is a bit harder. )

So to be called an algorithm it must always halt. To be useful, not necessarily.
> 1 votes

# Answer
There isn't a good formal definition of "algorithm" at the moment, and this is one of those corner cases.

For the purpose of determining how long an algorithm takes to run, an algorithm must terminate. But there is a large cohort of computer scientists who analyse "algorithms" which don't terminate because they are cooperating processes (e.g. operating systems, servers, stream processors), but still do useful work and actually progress, rather than unproductively looping forever.

Rather than doing induction on data, we refer to this as doing codinduction on codata, the "co-" prefix referring to the category dual. And such "algorithms" may not terminate, but they might coterminate.
> 1 votes

---
Tags: algorithms
---


# Question
Title: CFG for this language $\{a^k b^m c^n \mid 1 \leq k, m, n, n \leq 2k\}$
I'm kinda new in this topic and I don't know how to figure out the rules to make a CFG out of this language, if anyone could give me an idea or hint so I can try to solve it knowing that, I would be very thankful.

Thank you for yout time.

# Answer
Ignore $b^m$ at first. Once you have the rest figured out, adding it in will be easy.

Try to build a CFG for $a^k c^k$. This is a classic CFG problem, so you've probably seen it in class.

Then, try to modify your CFG to generate $a^k c^{2k}$. This is a relatively small change.

Now, modify this new CFG to generate $a^k c^n \mid n \leq 2k$. You should only need to add new production rules, without deleting or modifying your existing ones.

Finally, add in the $b^m$. This part should be a trivial change.

Good luck! I hope this helps!
> 0 votes

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


# Question
Title: Finding the longest path of sum $0$ in a weighted tree
How to find the longest path with the sum $0$ in a weighted tree (where each edge is labeled with an integer weight)?

In other words, I want to find a path so that the sum (sum of numbers on edges) is equal to zero, and the amount of edges along which I went is the maximum.

# Answer
> 2 votes
**If the (simple) path needs to go from the root to a descendant:**

Perform BFS or a preorder DFS visit of your tree and, for each vertex $v$, record:

* the length $\ell(v)$ of the unique path from the root of the tree to $v$; and
* the depth $d(v)$ of $v$ in $t$.

This can be done in constant time per vertex since, if $v$ is the root $\ell(v)=d(v)=0$, otherwise $\ell(v) = \ell(u) + w(u,v)$ and $d(v) = d(u) + 1$, where $u$ is the parent of $v$.

Return the vertex $v$ for which $\ell(v)=0$ and $h(v)$ is maximized. The total time spent is linear.

**If the (simple) path needs to go from an ancestor to a descendant:**

Perform a preorder DFS visit and maintain a dictionary $D$ that stores the ancestors $u$ of the current vertex $v$. The key of a vertex $u$ in $D$ is the length $\ell(u)$.

When an edge $(u,v)$ is traversed moving away from the root, add $\ell(u)$ to $D$. When an edge $(u,v)$ is traversed (moving towards the root) remove $\ell(u)$ from $D$. In case of ties in $D$ break them in favor of the lowest vertex.

When a vertex $v$ is visited, we want to search $D$ for an ancestor $u$ of $v$ with key $\ell(u) = \ell(v)$, meaning that the path from $u$ to $v$ has length $\ell(v) - \ell(u) = 0$. This can be done in $O(\log H) = O(\log n)$ time, where $H$ is the height of the tree.

The overall time complexity is then $O(n \log H) = O(n \log n)$.

**If the (simple) path can be arbitrary:**

For each vertex $v$ compute its depth $d(v)$ in any standard way.

Perform a postorder DFS visit and, for each vertex $v$, maintain a dictionary $D\_v$ that stores all descendants $z$ of $v$. The key of $z$ is the distance from $v$ to $z$. Break ties in favor of vertices $z$ with larger $d(z)$. In addition to the standard operations, you can also assume that $D$ is able to increase all its keys by a constant amount in $O(1)$ time.

When $v$ is visited and $v$ is a leaf, $D\_v$ contains only $v$ itself with key $0$. Otherwise, let $u\_1, \dots, u\_k$ be $v$'s children and assume w.l.o.g. that $u\_1$ maximizes $|D\_{u\_1}|$. Construct $D\_v$ as follows:

* Initially $D\_v = D\_{u\_1}$. Notice that $D\_{u\_1}$ will not be used anymore. This operation amounts to renaming $D\_{u\_1}$ to $D\_v$.
* Increase all the keys in $D\_v$ by $w(v, {u\_1})$.
* Add $v$ with key $0$ to $D\_v$.
* The vertex $z$ with key $0$ in $D\_v$ is such that the path from $v$ to $z$ has length $0$ and the number of edges from $v$ to $z$ is maximized (remember our tie-breaking rule). This is a *candidate path*.
* For each $u = u\_2, \dots, u\_k$:

+ For each vertex $a$ with key $\ell\_a \in D\_u$:

    - Check whether there is a vertex $b$ in $D\_v$ with key $\ell\_b = -\ell\_a - w(v,u)$. If this is the case then there is a *candidate path* from $a$ to $b$ of length $0$ and hop-length $d(a) + d(b) - 2d(v)$.
    + For each vertex $z$ with key $\ell\_z \in D\_u$:

    - *Move* vertex $z$ from $D\_u$ to $D\_v$. Its new key in $D\_v$ is $\ell\_z + w(v,u)$.

Return the best candidate path seen during the visit.

To bound the time complexity notice that, apart from a $O(n \log n)$ term needed to add the vertices $v$ into $D\_v$, it is dominated by the complexity needed to move vertices $z$. When a vertex $v$ is moved from $D\_u$ to $D\_v$, the size of $D\_v$ will be at least twice the size of $D\_u$. This means that each vertex can be moved at most $O(\log n)$ times.

The overall time complexity is therefore $O(n \log^2 n)$.

---
Tags: algorithms, graphs, data-structures, trees
---


# Question
Title: Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$
I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^\*$ and a regular grammar generating $\Sigma^\*$.. I got the examples here from Sipser. Let $ALL\_{CFG}$ refer to the language that a given CFG generates $\Sigma^\*$, and let $ALL\_{REX}$ refer to the language that a given regular expression generates $\Sigma^\*$ (and since for each regular expression there is a regular grammar, we can also say that the equivalent regular grammar generates $\Sigma^\*$).

From what I got, we have:

> * $ALL\_{CFG}$ is not decidable, it is also not Turing-recognizable. Let $\overline{A\_{TM}}$ refer to the language that a TM $M$ does not accept input word $w$. We can reduce $\overline{A\_{TM}}$ to $ALL\_{CFG}$ in polynomial time using computation histories. The reduction constructs a CFG which generates all possible words where: 1) the first characters do not match $w$, 2) the last characters do not match accepting configurations, and 3) characters do not match valid transitions of $M$'s configurations. Thus, $A\_{TM}$ does not accept $w$ iff the CFG generates $\Sigma^\*$ (i.e. there are no accepting computation histories). Since the reduction maps $\overline{A\_{TM}}$ to $ALL\_{CFG}$, and $\overline{A\_{TM}}$ is not Turing-recognizable, $ALL\_{CFG}$ is not Turing-recognizable.
> * $ALL\_{REX}$ is decidable since it is decidable if a finite automaton accepts $\Sigma^\*$. However, the acceptance problem for any regular language $R$ can be polynomially reduced to the language $ALL\_{REX} - f(R\_M)$, where $R\_M$ is a TM that decides $R$, and $f(R\_M)$ is a similar reduction of computation histories as outlined above. In more detail, $f(R\_M)$ is the regular grammar that generates all possible words where 1) the first characters do not match $w$, 2) the last characters do not match rejecting configurations, and 3) characters do not match valid transitions of $R\_M$'s configurations. The decider for $ALL\_{REX} - f(R\_M)$ checks if it is empty (which means that $f(R\_M)$ is equal to $\Sigma^\*$). If empty, then there are no rejecting computation histories and $w \in R$. (In Sipser, he used something like this to show EXPSPACE-completeness for $ALL\_{REX} - f(R\_M)$)

I would like to ask:

> From above, both regular grammars and CFG could generate computation histories of a TM, and both could generate $\Sigma^\*$. But what is it with the fundamental power of the CFG's grammar that makes it valid to reduce $\overline{A\_{TM}}$ to $ALL\_{CFG}$, but it is not possible for $\overline{A\_{TM}}$ to be reduced to $ALL\_{REX} - f(A\_{TM})$ ? I know that we cannot reduce $\overline{A\_{TM}}$ to $ALL\_{REX} - f(A\_{TM})$ since $ALL\_{REX} - f(A\_{TM})$ is decidable, while $\overline{A\_{TM}}$ is not Turing-recognizable... But I would like to understand this in terms of the difference in generating power between CFG's and regular grammars via their rules.

For instance, from what I read, CFG's permit the rules $A \rightarrow BC$, where $B$ and $C$ are strings of variables and terminals. On the other hand, regular grammars only permit rules in the form of $A \rightarrow aB$, where $a$ is a terminal. I would like to ask: why does incorporating rules of the form $A \rightarrow BC$ to a grammar, give it enough generating power such that it is already valid to reduce $\overline{A\_{TM}}$ to the grammar (i.e. to the CFG).

# Answer
Your summary of the proof of undecidability is not accurate. Your specification of $\overline{A\_{TM}}$ is not correct.

For a reasonable exposition of the proof, see https://liacs.leidenuniv.nl/~hoogeboomhj/second/codingcomputations.pdf particularly the beginning of Section 1 and Section 3.

The intuition is not easy to convey, as the proof is not entirely trivial. But here is the core fact. Let $v,w$ be two configurations of a Turing machine. Write $n(v)$ to be the next configuration of the Turing machine after a single step of computation, if you start at configuration $v$. Define the language

$$L = \\{v \\# w^R \mid n(v) \ne w\\}.$$

Then the key fact is that $L$ is context-free. This takes some proof; proving that is a key step in the proof. However, that's the answer to your question: $L$ is context-free but not regular. As a result, we can reduce the halting problem to $ALL\_{CFG}$ but not to $ALL\_{REX}$.

I have skipped many steps to give you an overview of the main idea. You will need to read the full proof to fill in the details. I suggest that you next read and understand the proof, with this perspective in mind, and then revisit what I've written here. Hopefully that will help you understand why the proof holds for context-free languages but would fail for regular languages.
> 2 votes

# Answer
The difference between the models stems, intuitively, from the ability of CFGs to *count*. More precisely, CFGs are able to generate strings of the form $a^nb^n$, where the number of $a$'s and $b$'s is the same.

This ability grants it the power to compare strings, which can then be utilized to show undecidability, because the CFG is able to compare the contents of a tape between two consecutive configurations.

This becomes a bit more evident if you recall that the halting problem for two-counter machines (Minsky machines) is undecidable. There, a configuration is given by the values of two counters. You can this of this as a TM with a sort of unary alphabet (although not exactly). In two counter machines, comparing two consecutive configurations exactly amounts to comparing the values of the counters in consecutive steps, which is right up the alley for CFGs.

In contrast, Regular languages are captured by finite state automata, which have finite memory, and are able to count only up to a fixed number. Thus, these automata can simulate a TM as long as the length of a configuration is bounded in advance. Why does this give us PSPACE hardness? Well, you can simulate *any* TM that works in bounded space, it doesn't have to be polynomial in the input. However, in order for the reduction itself to be polynomial, you need the bound to be polynomial. Thus, you get exactly PSPACE hardness.

With regards to the "type" of rules, it's not so much the $A\to BC$ rules that are a problem, it's more in rules of the form $A\to aAb$ (or more generally, the ability to have *cyclic* rules). The reason is that $A\to BC$ has a "tree" structure, and if $B$ and $C$ are not related later, then this is effectively a union operation, which regular languages can simulate.

However, a rule of the form $A\to aAb$ maintains the "context" $A$, which is something regular languages cannot do.

To summarize:

> Semantically, the power of CFGs lies in their ability to count.
>
> Syntactically, the power of CFGs lies in cyclic rules.
> 2 votes

---
Tags: formal-languages, turing-machines, context-free, formal-grammars, undecidability
---


# Question
Title: Context Sensitive Grammar for the language $\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\}$
I have been trying to find a context sensitive grammar for the language $\\{ a^{2n} b^{2n+1} c^{3n} d^{n+3} \mid n \ge 1\\}$ for some time but I cannot get it done. Any ideas ?

# Answer
In the following grammar the first block of productions ensures that the right amount of $a,b,c$, and $d$ is generated, in some order. The terminal $a$ is represented by the nonterminal $A$, $b$ by $B$, etc. They also ensure that $X$, which represents a $a$, is at the end of the sentential form.

The next block ensures that $A,B,C,D$ can be reordered.

The last block ensures that terminals are generated from right to left in the correct order (first $d$, then $c$, then $b$, and finally $a$).

$$ \begin{align\*} S &\to ABBCCCDS'X \\ S' &\to AABBCCCDS' \mid BDDD\\ \\ BA & \to AB \\ CA & \to AC \\ CB & \to BC \\ DA & \to AD \\ DB & \to BD \\ DC & \to CD \\ \\ DX &\to Xd \\ X &\to Y \\ CY &\to Yc \\ Y &\to W \\ BW &\to Wb \\ W &\to Z \\ AZ &\to Za \\ Z & \to a \end{align\*} $$
> 2 votes

---
Tags: context-sensitive
---


title: Is $\frac{n}{3}$-CLIQUE NP-complete?

text:
# Question
Title: Is $\frac{n}{3}$-CLIQUE NP-complete?
Consider the problem $\frac{n}{3}$-CLIQUE: determining whether a graph contains a clique with at least $n/3$ vertices.

I want to prove it is NP-complete using a polynomial transformation from CLIQUE.

How can I approach this problem?

# Answer
> 3 votes
Let me explain how to solve this, leaving all details to you.

Given an instance $(G,k)$ of CLIQUE, we want to construct an equivalent instance of $\frac{n}{3}$-CLIQUE, say $G'$. Let us denote by $|G|$ the number of vertices in $G$. There are several cases to consider:

* Case 1: $k = |G|/3$. In this case you can take $G' = G$.
* Case 2: $k \> |G|/3$. In this case you want to increase the number of vertices to $3k$ without changing the size of the maximum clique.
* Case 3: $k \< |G|/3$. This is the most complicated case. You want to increase the number of vertices to some $n'$ while increasing the size of the maximum clique by some $\Delta$. You are done if you can ensure that $k+\Delta = n'/3$. (In fact, it suffices to have $k+\Delta \> n'/3$, since then we can use Case 2.)

You take it from here.

# Answer
> -3 votes
I'do go for the approach of assuming that it is solvable in polynomial time, then proving that given this solution u can reach the solution of the general Clique problem in polynomial time. So it is only polynomial if P=NP -i.e., simply prove the 2nd part, think if someone gave u a black box to get n/3 CLIQUE how can u use it to get the general CLIQUE

---
Tags: complexity-theory, graphs, reductions, clique
---


# Question
Title: Why shift means push terminal symbol and state into the stack? Why not push only state?
Shift means that you need to put the status and terminal symbol on the stack. But what is the terminal symbol used for? After all, if the reduce command is executed, both the state and the terminal symbol are deleted and the terminal symbol will never be used.

Why not push into the stack only state?

(English is not my native language, so please be kind to my mistakes)

# Answer
> 0 votes
You are talking about the typical description of LR parsing. And you are completely right, the "state" (if you look closely, it is the state of the DFA that recognizes left hand sides of productions when processing the current stack's contents) encodes all information needed. Adding the symbol is redundant. As far as I can tell, it is usually added to clarify what is going on (just a list of state numbers would be completely opaque).

---
Tags: parsers, lr-k
---


title: Turing Machine - Analyze brackets

text:
# Question
Title: Turing Machine - Analyze brackets
For a practical task, we are asked to provide the transition table for a Turing machine that validates the number of open brackets is equal to the number of closing brackets. The only tape symbols allowed are ( ) E B If the number of brackets is equal (opening brackets = closing brackets) then the machine must halt in-state 'yes' and if they are not equal than it must halt in-state 'no'

Any clarification on this would be greatly appreciated! :)

# Answer
It sounds like the only thing you care about is whether *the number of open brackets equals the number of close brackets*. In which case, I'd recommend an algorithm something like this:

* Look for an open bracket.
    + If you can't find one, look for a close bracket.
        - If you find one, reject. Otherwise, accept.
    + If you can find one, erase it.
* Look for a close bracket.
    + If you can't find one, reject.
    + If you can find one, erase it.

The exact mechanics of searching for brackets are up to you, but if you need more guidance, I'd recommend using one of your spare symbols ($E$ for empty) to mark empty patches of tape (everything to either side of the input) and the other ($B$ for bracket deleted) to mark things you've erased. That way you can tell when you reach the edge of the input string.
> 1 votes

# Answer
Scan left to right, erase the first '(' (i.e., overwrite with some mark), go back to the start and erase the first ')', go back and start over. Accept if no '(' or ')' left.

This just matches '(' and ')', not proper nesting!
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Algorithm Design Patterns vs. Algorithm Strategies vs. Algorithm Design Techniques vs. Algorithm Design Paradigms
I often encounter these terms, seemingly bearing same semantics and meaning. I'm almost sure they mean same - the types of Algorithms categorized based on their implementation strategy/paradigm.

Just wondering if I'm right and I get this correct, because, again - in different books/courses these terms are encountered in the same context. I'm kind of a very critical to the exactness of the terms I read.

Could you please confirm or reject my assumption?

# Answer
> 1 votes
Yes, they all refer to a categorization in terms of design paradigms (such as greedy, divide and conquer, dynamic programming, et cetera).

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


# Question
Title: Non-Midpoint Segment Splitting in Ruppert's Delaunay Triangulation Refinement Algorithm
Roughly, in Ruppert's Delaunay Triangulation refinement algorithm, so called *encroached edges* are split until no more encroached edges remain.

The algorithm specifies splitting the edges at their midpoint (except in the case of small input angles where *concentric circular shells* as suggested. This question is unrelated to these cases.)

In certain domains, given a segment, there are points on the segment that I would prefer to split on that are not necessarily the midpoints (unrelated to the concentric shell trick). These points are chosen based on some domain specific underlying data (considerations beyond the graph structure the algorithm is aware of).

* What are the implications of splitting on non-midpoints?
* What needs to be taken into consideration when selecting among several non-midpoint candidates?
* Does splitting on non-midpoints affect any of the convergence properties of the algorithm?

Another way to ask this is: Are there split points that are *better* than the *a-priori* selected midpoints?

# Answer
> 4 votes
In Rupert's refinement algorithm, if the circumcenter of a "skinny" (poor quality) triangle were inside the domain and its location is "sufficiently" far away from other points in the triangulation, the algorithm terminates. When the circumcenter is inserted, it is at least a certain distance from all other points (equal to the circumradii), so it will eventually run of space to add more points. Luckily, the ratio of the circumradii and length of the smallest side of a triangle is a function of the smallest angle in the triangle. Therefore, if a skinny triangle is defined as a triangle whose ratio is greater than 1 (corresponds to a minimum angle of 30 degrees), the algorithm is guaranteed to terminate.

But what if the circumcenter is outside the domain? That is when the midpoint on the "nearest" boundary edge is inserted. When the midpoint is inserted, it introduces two short edges whose length is equal the half the length of the original edge. In addition, all points within the diametrical circle of the original edge are deleted so that there are no "even-shorter" edges introduced. And because these two new edges may be shorter than the previous shortest edge in the mesh, during the next step, we should introduce the circumcenter only if the ratio (cumcumradii : shortest length) is greater than some quantity that is strictly greater than 1. In the pdf you shared, it is shown that the ratio should be $\sqrt2$.

If you inserted a point not on the midpoint, but somewhere else on the edge, you will create an edge shorter then half the length of the boundary edge. This edge may be much shorter than the current shortest edge in the mesh. So the ratio that guarantees termination will be greater $\sqrt2$.

To answer your specific questions: 1. Implication: weaker termination guarantee 2. The length of new edges created should be considered. If they all happen to be large, you can happily add a non-midpoint vertex into the mesh. If the boundary edge is a light year long, and other mesh edges are orders of magnitude shorter, you can split the edge almost anywhere ... almost (see below). 3. Yes, splitting on non-midpoints affects termination guarantees.

BUT .....

Alper Ungor's paper attempts to insert off-circumcenter points instead of the circumcenter.

And this paper also allows for insertion of non-midpoint vertices into the mesh. But in the limiting case, it reverts to mid point insertion.

# Answer
> 1 votes
The first paper I am aware of in the literature that has addresses analysis of non-midpoint splitting is:

*Pav, S.E.; Walkington, N.J.*, **Delaunay refinement by corner lopping**, Proceedings of the 14th International Meshing Roundtable (2005) pdf.

The motivation of that paper was a little different: they authors were analyzing refinement of curved inputs. But the analysis applies to non-midpoint splitting of edge splitting: a split point of a curve is similar in that it is not at the center of the circle with diameter between the segment or curve's end points. The take away from the analysis is that non-midpoint split points can be used but at the expense of a reduction of the guaranteed quality that can be ensured in the algorithm output. In the paper, this is seen in the appearance of $\mu$ and $\eta$ in Corollary 3.

The paper of Foteinos, Chernikov, and Chrisochoides (here) also analyzes non-midpoint splitting although with a different dependence between the parameters: the minimum angle in the output is fixed and the algorithm reverts to midpoint splitting whenever there isn't enough space to permit a midpoint split and guarantee mesh quality.

> Are there split points that are better than the a-priori selected midpoints?

There isn't any good evidence of non-midpoint splitting benefiting a particular application. For **triangle circumcenters**, there are two common motivations for using non-circumcenters,

1. Intentionally create triangles slightly above the quality threshold. The goal is to spread points out as much as possible without triggering further refinement allowing the algorithm to terminate with as few vertices as possible. This was the original motivation in Üngör's paper and Triangle does this.
2. Deliberately create triangles with angles hopefully well above the thresholds of guaranteed termination. Acute does this and on many cases is fortunate enough to create meshes that outperform theoretical expectations.

Figure 7 in this paper shows how the type of off-center selection can be used to manipulate the distribution of triangles created in the final algorithm. The results aren't that surprising: if you go out of your way to create a during type of triangle in the algorithm, then you create lots of that type and can see them over-represented in the distribution.

Non-midpoint edge splitting hasn't been particularly effective an addressing these needs. While circumcenter splitting is done in a way that to avoid creating subsequent poor quality triangles (when filling a empty space in the domain), the midpoint is generally the best position with the local information available. If the algorithm could look ahead 2, 3, 4, ... steps and see what subsequent refinement would be made to the split segment, maybe there could be some better prediction on how the segment should be refined. This paper suggests that if you know the local feature size (i.e., how long the segments needs to be in the final mesh) up front, then you can make better decisions on where to place split points and provide better guarantees on the final output. But for standard Delaunay refinement, no one has found information available at the time of an edge split that justifies a non-midpoint split.

---
Tags: computational-geometry
---


# Question
Title: Scheduling to minimize the truncated gaps
I have a single job of unit length, a set of $n$ slots, and a budget of $B$ units. If the job is scheduled at slot $t$, then it will consume $c(t)$ units of the budget $B$. If the job is not scheduled for a period of $x$ consecutive slots, then a penalty of $\lfloor x/2\rfloor$ occurs. The objective is to schedule the job in order to minimize the sum of penalties.

For example, for $n=12$, if the job is scheduled at slot 1, at slot 3, at slot 6, and at slot $12$, then the sum of penalties is $\lfloor 1/2\rfloor + \lfloor 2/2\rfloor + \lfloor 5/2\rfloor = 0+1+2=3$.

Is this problem NP-hard?

I am trying to reduce the knapsack problem to it. Transforming the values in the knapsack problem to the penalties is somehow difficult, because once the job is scheduled at $t$, the penalty is initialized.

# Answer
> 2 votes
The problem is polynomial-time solvable. To avoid edge cases it is better to think that the job needs to be scheduled at time $0$ and that $c(0)=0$.

Let $OPT\[t,p\]$ be the minimum amount of budget that needs to be spent in order to schedule the job in the first $t$ slots with an overall penalty of at most $p$ and with the additional constraint that the job must be scheduled at time $t$.

Let $P(t', t) = \Big\lfloor \frac{t-t'-1}{2} \Big\rfloor$ be the penalty incurred if the job is scheduled at times $t'$ and $t \> t'$ and is not scheduled at any time in-between.

Then $OPT\[0,p\] = 0$ and, for $t\>0$: $$ OPT\[t,p\] = c(t) + \min\_{\substack{t'=0,\dots,t-1 \\ P(t',t) \le p}} OPT\left\[t', p - P(t',t) \right\] $$

The minimum attainable penalty up to time $t$, with the constraint that the job is scheduled at time $t$, is then: $$ \mu(t) = \min \\{p \in \\{1,\dots,\lfloor t/2 \rfloor\\} \mid OPT\[t,p\] \le B \\} $$

And the minimum attainable penalty for your problem is: $$ \min\_{t=0,\dots,n} \left\\{ \mu(t) + P(t,n+1) \right\\}. $$

Notice that there are at most $n \cdot (P(0,n)+1) = O(n^2)$ values $OPT\[p,t\]$ to compute.

---
Tags: algorithms, reductions, np-hard
---


# Question
Title: What would be a natural generalization of a byte parity check?
Suppose that we have a group of N bytes. One can add a very basic (and not particularly reliable) check of the consistency of this data by storing an additional (N+1)th byte containing exclusive XOR of all N original bytes. It will be enough to detect a single byte error during the transmission.

In the practical problem that I am trying to solve, if an error occurs during transmission, I actually will know when error occurred and which byte contains the error. Then knowledge of the (N+1)th byte is sufficient to recover the incorrect byte by simply XORing all correct bytes with the (N+1)th byte.

The errors that can occur in my application actually occur in bursts of 1 or several bytes, I will denote this number as M. There can be no more than a single burst per group of N bytes. In fact, when error occurs my transmission channel returns N-M bytes, along with the marker of the position where bytes were lost.

My question is: what would be (is there?) a natural way to generalize the simple (M=1) error correction scheme using a single XOR byte to the case where the error burst can contain up to M skipped bytes? Is it possible to do this specific kind of error correction using only M bytes?

# Answer
> 3 votes
For $i \in \\{0,\ldots,M-1\\}$, add a new byte which is the sum (or XOR) of every byte whose index equals $i$ mod $M$. For example, if $M=2$, one byte is the sum of all the bytes in the even positions, and the other one is the sum of all the bytes in the odd positions. Since bursts have length at most $M$, each of these checksums will only be missing a single byte.

---
Tags: error-correcting-codes
---


# Question
Title: Why is backpatching needed during intermediate code generation?
In compiler design, control-flow statements are translated to sequences of three-address-code (3AC) instructions a lot of which are jump statements. A 3AC instruction of the jumping type could be an unconditional jump in the form of a goto statement with a target label as its argument, such as

> goto L1

or it may be a conditional jump in the form of an if statement, as in

> if a \< b goto L1

Now when the compiler generates a 3AC jump instruction, the target label is available to it in the form of an inherited attribute ( which I assume is a pointer to an object/structure and so we could think of it as a pointer to a variable ).

Now, the labels passed to say, an if-else statement as inherited attributes would also be then attached to certain target instructions **after the if-else construct that used those labels has been translated**.

Suppose, a label L1 has been used a lot of times before in constructs that have now been translated. Now suppose that label has to be attached to say a target assignment statement (the next instruction to be emitted) whose index is in the array of instructions is 137 (because there are 137 3AC instructions already stored in the quadruples array). Then at this point of time the variable L1 would get the value 137 and so all the earlier uses of L1 would also now get the value of L1 (because the variable pointed to by them now gets a value).

And so in this way we have translated control-flow statements in one pass and there is no need for backpatching to reduce the number of passes further.

I don’t understand why what I just wrote wouldn’t work and without backpatching two passes would be required to attach labels to their correct instructions.

# Answer
Suppose you encounter a jump instruction "goto L1" before encountering the label L1 itself. The solution you propose (as far as I understand) is to reserve a location M1 in memory at which L1 will be stored, and to translate "goto L1" into an instruction of the form "jump to the address stored at address M1". Later on, upon reaching L1, you update location M1 with the address of L1.

This is a form of "runtime backpatching", in which the processor itself is doing the backpatching when running the code. Accessing memory tends to be slow, and so it is much better to hardcode addresses, shifting the effort from runtime to compile time. This is where backpatching comes in. When encountering "goto L1", the compiler will note that the address is missing, and will fill it in later, when the address of L1 is known.
> 3 votes

---
Tags: compilers
---


# Question
Title: What is the Space Complexity of Tail Recursive Quicksort?
Looking at the following tail recursive quicksort pseudocode

```
QuickSort(A[1, ..., n], lo, hi)
Input: An array A of n distinct integers, the lower index and the higher index
         // For the first call lo = 1 and hi = n
Output: The array A in sorted order

If lo = hi return
         // The array A is already sorted in this case
If lo > hi or indices out of the range 1 to n then return

Else
      Pick an index k in [lo,hi] as the pivot
              // Assume that this can be done using O(1) cells on the stack
      i = Partition(A[lo, ..., hi], k)
              // Use in-place partitioning here so assume that this can be done
              // using O(1) space on the stack

If i - lo <= hi - i
      QuickSort(A, lo, i-1) // sort the smaller half first
      QuickSort(A, i+1, hi)
Else
      QuickSort(A, i+1, hi) // sort the smaller half first
      QuickSort(A, lo, i-1)

```

Assuming that the pivot is chosen adversarially each time I analyzed that it should have a space complexity of O(logn) \[which I am not entirely sure is correct\], but how would the space complexity be affected if the pivot is then chosen uniformly at random? I am fairly new to understanding space complexity over time complexity, so any feedback is appreciated!

# Answer
In the worst case the space complexity will be $\Theta(n)$. The first recursive call to quicksort is not optimized hence the stack space of the current call is not reused. This can happen $\Theta(n)$ times if `i` is always `hi`.

If the pivot is selected uniformly at random then the space required will be $O(\log n)$ with high probability, since the recursion depth will be $O(\log n)$.
> 1 votes

# Answer
If you either use a compiler that supports tail recursion, or make the small change not to use recursion for the larger partition at all, the recursion depth depends on the sizes of the smaller intervals.

The worst case for recursion depth is the case that each partition divides your subarray exactly in half, making the depth $log\_2 (n)$. The best case for recursion depth is the case that each partition divides your subarray into n-1 and 1 items, recursion depth = 1 (obviously the absolutely worst case for execution time).

So this is a bit paradoxical: Best case space complexity = worst case time complexity. But on the other hand, worst case space complexity = log n is so little that nobody cares about the space complexity. As long obviously as people don't make the mistake of sorting the larger partition first.

Without eliminating the recursion for the larger half, the worst case for recursion depth is n, and the order of the calls doesn’t matter.

Usually you can’t make an assumption that values would be different, so the quality of your partition function is important. Some will misbehave with many identical values.
> 1 votes

---
Tags: algorithms, space-complexity, quicksort
---


# Question
Title: Clarifying Practicality and Usage of a DFA's Accepted Language
I was reading up on DFA's and their accepted languages when I stumbled across this:

Let a DFA $M$ accept the language $L⊆Σ^∗$, DFA $M'$ accepts $P(L)=$ {$w∈Σ^∗|wy∈L$ for some $y∈Σ^∗$}.

Since any $wy$ has to be an element of $L$ in order for $w$ to be an accepted string, and $L⊆Σ^∗$, then wouldn't all states be accepted by $M'$?

For example, for machine $M'$ with the alphabet $Σ=$ {$0,1$}, let $w=01$. Since all values of $y$ also have to be in the alphabet $Σ^∗$, $w$ would have to be accepted. Let $y=10$, $wy=0110$, which is in the alphabet $Σ^∗$. Similarly, let $y=110$, $wy=01110$, which is again in the alphabet $Σ^∗$.

The text mentioned some transition from $M$ to $M'$, but what would the use of $M'$ actually be? How is it any different than, say, $L=$ {$w∈Σ^∗$}? Would they share the same finite-state diagram?

# Answer
> 1 votes
Picture the DFA $M$ as a directed graph, as the usual graphical depiction. Then the final states of your $M'$ that accepts prefixes of the language accepted by $M$ will have all states *from which a final state of $M$ can be reached* as final states. It should be clear that not all states of $M$ qualify. In particular, any dead states of $M$ (non-final states that loop back on all symbols) won't be final in $M'$.

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


# Question
Title: Algorithm to identify top $\log n$ elements in $O(n)$ time
Airlines has a new policy to give a first-class upgrade coupon to their customers based on the number of miles accumulated. They decided to give it to their top $\log(n)$ frequent flyers, where n is the total number of the airlines’ frequent flyers. Their current algorithm runs in $O(n \log(n))$ time to sort the flyers scan the sorted list to pick the top logn flyers. Describe an algorithm that identifies the top $\log(n)$ flyer in $O(n)$ time.

How can I devise an algorithm for this problem? I tried to solve it with priority queue ADT and some well-known sorting, but cannot solve this problem.

# Answer
> 4 votes
For every $k$, you can find the $k$th largest element in $O(n)$, using a linear time selection algorithm. You can then find the $k$ largest elements by scanning the array.

# Answer
> 1 votes
Use the deterministic select algorithm (look it up, it is widely discussed in algorithm/data structures courses). It's core is a partition like Quicksort's (i.e., small elements on one side of the pivot, large ones after), but it selects pivots carefully so as to get a linear worst case (not just average). You just need to ask for the $\log n$-th element, and read off the smaller ones before. Linear, but horrible constant. Theoretical interest only.

If you *know* which element's key is $\log n$-th beforehand somehow, you can just use Quicksort's partition to get the actual list.

# Answer
> -1 votes
You can use bucket sort for this problem, by having mile buckets/map. And then scan the frequency bucket to pick top logn flyers. This will be O(n).

---
Tags: time-complexity, data-structures, sorting
---


# Question
Title: Can Yacc be used to generate three address code for Java 1?
I have read that yacc generates bottom up parser for LALR(1) grammars. I have a grammar for Java 1 that can be used for generating three address code and is strictly LALR(1), but the translation scheme I am employing makes it L-attributed. Now I have read that L-attributed LR grammars cannot be parsed by using bottom up parsing. So, can yacc be used here or not?

# Answer
> 0 votes
A grammar's parser serves to recognize the language generated. Tools like YACC augment the parser to (essentially) trace a parse tree (some automatically build an AST, abstract syntax tree) for the parsed string according to the grammar. You can then walk this structure to generate code. But that is a separate task, that commonly uses different tools.

# Answer
> 0 votes
I'm not sure if this is what you're asking, but you can't write a single-pass Java compiler.

In C or C++, you have to declare (possibly forward-declare) a function before you use it. In Java, you don't. Since you need to know the declaration of a function/method in order to type check the call site, it follows that you can't *type check* a Java compilation unit until you have finished parsing it.

(Of course, you may be able to type check the three-address code, depending on the specifics of your representation.)

---
Tags: java, compilers
---


# Question
Title: reordering a max heap that the values of one of her subtrees has been changed
Let $H$ be a max binary heap with $n$ elements (vertexes).

Pick a vertex $z$ in the heap with height of $k$ ($0\<k\<\lg n$)

To every element in the sub heap of $z$ we add the constant value $c \> 0$.

We need to fix $H$ to be again a max heap, withour changing the value of the elements in the heap.

We need to do it with run time of $O(2^k \cdot \lg n)$.

---

I know that $MAX-HEAPIFY$ takes $O(\lg n)$ and $2^k$ is the number of leafs in a tree with hright of $k$.

But i dont realy have an idea for an algoritm.

Any directions?

Thanks.

# Answer
> 0 votes
It seems like you can do it in $O(k\log{}n)$ time. Just compare vertex $z$ with its parent $p$. If $z$ has lesser value then we are done. Else swap $z$ with $p$ and heapify subtree rooted in $p$. The vertex $z$ will be raised no more than $k$ times and each raise takes $O(\log{}n)$

---
Tags: algorithms, efficiency, heaps
---


# Question
Title: Heaps and Heapsort - Find the 7'th biggest value in a min heap by $O(1)$
I have a min heap.

I need to find the 7'th biggest value in the heap with $O(1)$.

I need to build the algorithm.

I dont realy have an idea how to get to this efficiency.

Help?

Thanks.

# Answer
O(1) means: You need to do this with a fixed number of operations. Basically, write code without a loop. That's not difficult. It's a lot of code, but a fixed amount of code.

Look at your heap as if it was a binary tree. You want the 7th largest item in your tree. That's the sixth largest of the subtrees L and R. If the item at L is smaller than the item at R, it's the fifth largest item in the subtrees L, RL and RR, otherwise the fifth largest item in the subtrees R, LL and LR. And so on..
> 3 votes

# Answer
I am pretty sure that you cannot solve this problem in $O(1)$ time without additional assumptions. You have to scan at least $L-6$ leaves (which already gives you $\Omega(n)$ time complexity), where $L$ is a total number of leaves in a heap, to find an answer. Indeed, suppose that you have an algorithm which solves the problem and scans less than $L-6$ leaves for some input heap. Then you can pick 7 arbitrary non-scanned leaves and increase their values such that one of them will become the 7-th biggest in the heap. But the repeated run of your algorithm on the modified heap won't scan the 7 modified vertices (because it didn't scan it during the first run and all other vertices remained unchanged) and, consequently, won't find the correct answer for this heap.
> 1 votes

---
Tags: algorithms, efficiency, heap-sort
---


# Question
Title: Findind The n/lgn intermidiate values in an unsorted array with asymptotic run time of $\Theta(n)$ SELECT algorithm
Let $A\[1..n\]$ be an unsorted array, we want to find the $n/lgn$ intermidiate numbers in the array.

Namely the $(n/2)+1$ biggest number and the $(n/2) + 2$ biggest number and so on... until the $(n/2) + (n/lgn)$ biggrst number.

We are studing on the select algorithm and sortings.

I think it should go somehow with select algorithm as it has an efficiency of $\Theta(n)$

But its not that simple. As just making a loop will get us to \Theta(n^2)$

Just a remainder - the select algorithm compute nad finc the median of the medians in order to find the $i$ value in the array with run tie of $\Theta(n)$

Any suggestions?

Thank you.

# Answer
> 2 votes
You can find a $k$-th order statistic of an array using a selection algorithm in $\Theta(n)$ time. It means that you can also find the $k$ least (and the $k$ greatest) elements of an array in $\Theta(n)$ time by first finding the $k$-th ordering statistic and then comparing it with each element of an array. So in your case we can find $n / 2$ (median) and $n/2 + n / \log(n)$ order statistics and then find all suitable elements by scanning an array and comparing its elements with both statistics.

# Answer
> 1 votes
I think this question is almost the same idea Algorithm to identify top $\log n$ elements in $O(n)$ time So u can combine the idea of the solution there with what was suggested to u here to get a better performance.. i.e., -find the (n/2 + 1) element and the (n/2+ n/log n) element (ur max & min) that's O(n) -Scan the whole array to get what's in between, that's O(n) too -If it's required to output them sorted, that's O(n/logn * log(n/log n) )... still O(n) .... As I said this Q is a variation of the previous one, and so is my answer here just mapping the idea suggested there

---
Tags: algorithms, efficiency, selection-problem
---


# Question
Title: Is this a Fixed Parameter Tractable algorithm?
Suppose my algorithm runs in time $O(nL^2)$, where $n$ is the size of the input, and $L$ some other parameter, which can get arbitrarily large *w.r.t.* $n$. My algorithm does not run in polynomial time, since $L$ can get arbitrarily large *w.r.t.* $n$. So I'd like to categorize it elsewise. Fixed Parameter Tractable algorithms, with regards to some defined parameter $k$, run in time $O(f(k)\times n^{O(1)})$, where $f$ is any function.

Would it be correct to state that my algorithm is Fixed Parameter Tractable (FPT) with regards to the parameter $L$?

# Answer
> 2 votes
If you consider $L$ to be *a parameter*, then yes, you have an *FPT time* algorithm, and your parameterized problem is indeed in the complexity class FPT, but be precise when you define your problem so that it is indeed stated as a parameterized problem.

Although we often refer to things as *FPT algorithms*, it is actually the *problems* that are FPT or not. Just as we don't have "NP-complete algorithms", we don't really have algorithms that are "FPT".

However, keep in mind that your algorithm also runs in pseduo-polynomial time in $O(n \cdot L^2)$ (if I understand $L$ correctly). So, since your might not be (weakly) NP-hard, I would state it as a pseudo-polynomial time algotithm.

*(Definition)*. Your algorithm is *pseudo-polynomial* in $n$ and $L$ since it has running time $O(n \cdot L^2)$ and $L$ is an integer.

Ps: I claim that it is incorrect to say that we have an FPT algorithm, when it is the *problem* that belongs to FPT, and the algorithm runs in "FPT time". Of course, I call algorithms "FPT algorithms", too, but when it comes to the way we speak with students, I feel that it is important to make a distinction between problems and algorithms.

# Answer
> 3 votes
First and foremost, I would advise having another look at the basic definitions. An FPT instance is identified by a string $x$ and an integer $k$ such that $(x, k)$ is a yes-instance.

Put briefly, if $f(k)$ is not polynomial in terms of $n$ and still depends on $n$, then you cannot obtain an FPT algorithm. We require that $k$ is fixed, or independent of $n$, and thus $f(k)$ is always independent of $n$. However, if $f(k) = n^{O(1)}$, then our FPT algorithm is in fact a polynomial time algorithm. Hence, if $f(k) = O(2^n)$, the answer is definitely no.

# Answer
> 0 votes
Yes, it is technically correct to call such an algorithm FPT but rather pointless.

Suppose that the problem at hand is computable, say, it can be solved in time $T(n)$.

You write that $L$ is bounded from below by $\Omega(\sqrt{n})$.

Putting these two facts together, we have that the problem can be solved in time $T(c L^2)$ for some constant $c$. Taking $f(k)=T(c k^2)$, this is an FPT running time, since $T(c L^2)=f(L)\times n^0=f(L)\times n^{O(1)}$.

If a parameter $k$ is bounded in any way from below by any function of $n$ (no matter how slow growing), then the problem (assuming it is computable) is automatically fixed-parameter tractable in that parameter. We don't even need the "$n^{O(1)}$-part" of the running time, we can simply solve the problem in $f(k)$ time by computing an upper bound on $n$ from $k$ and then running a brute-force algorithm.

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


# Question
Title: Longest subarray with at most two different values - Runtime complexity for a DP solution
Consider the problem of finding, for a given input array, the **longest subarray** with at most **two different values**.

For example:

```
Input: [3,3,3,1,2,1,1,2,3,3,4]
Ans = 5, the longest subarray would be [1,2,1,1,2].

Input: [1,2,3,2,2]
Ans = 4, the longest subarray would be [2,3,2,2].

```

Below is **dynamic programming** solution to this problem (in Python, hopefully it's easy to read) using a **sliding window** that holds a "valid subarray" (the subarray of elements between indices `i` and `j` always holds two values at most).

I read on e.g. LeetCode that this solution has a runtime complexity of $O(N)$ where $N$ is the length of the input array, but that's not immediately clear to me since we have two nested loops with $i$ and $j$ and $0\leq i\leq j\leq n$.

Why is the worst-case runtime complexity of this solution $O(N)$ and not $O(N^2)$?

Here's the DP solution in question with those nested loops holding a subarray between $i$ and $j$:

```
    def longest_subarray_holding_two_diff_values (input_array):
        ans = i = 0
        count = collections.Counter()

        for j, x in enumerate(input_array):
            count[x] += 1

            while len(count) >= 3:
                count[input_array[i]] -= 1
                if count[input_array[i]] == 0:
                    del count[input_array[i]]
                i += 1
            ans = max(ans, j - i + 1)
        return ans

```

# Answer
Here is how the sliding window algorithm works (unfortunately, I don't understand your code, so can't say whether this is the same algorithm).

We keep track of two pointers $i,j$, with the following properties: the subarray $A\[j\],\ldots,A\[i\]$ contains exactly two values, and it is maximal with respect to $j$ (that is, either $j = 0$ or $A\[j-1\],\ldots,A\[i\]$ contains three values). We also keep track of the two values in question $a,b$, and of their last appearance $k\_a,k\_b$. Finally, we keep track of the longest valid subarray seen so far.

In the initialization phase, we scan the array until we see two different values; if the array is constant, then the answer is the length of the array.

At steady state, we take a peek at $A\[i+1\]$. If $A\[i+1\] \in \\{a,b\\}$, we update $k\_a$ or $k\_b$, and simply increase $i$. If $A\[i+1\] \notin \\{a,b\\}$, then we do two things. First, we update the value of the longest valid subarray seen so far (comparing it to $j-i+1$). Second, suppose that $A\[i\] = a$; then we set $j = k\_b+1$, set $b = A\[i+1\]$, set $k\_b = i+1$, and increment $i$.

Finally, when reaching $i = n$, we update the value of the longest valid subarray (comparing it to $j-i+1$), and output the result.

As you can see, this algorithm performs $O(1)$ operations per iteration, so runs in $O(n)$ time.
> 2 votes

---
Tags: time-complexity, dynamic-programming, arrays, python
---


title: Calculate the number of models of a KB

text:
# Question
Title: Calculate the number of models of a KB
> Suppose we had a domain with two individuals, $x$ and $y$. Suppose we had two predicate symbols $p$ and $q$ and three constants $a$, $b$, and $c$. Suppose we had the knowledge base KB defined by:
>
> * $p(X) \leftarrow q(X)$
> * $q(a)$
>
> How many of these interpretations are models of KB?

So we know that in total there are 128 interpretations (Models and non-models).

* Constants $a,b,c$ can have two different individuals $\\{x,y\\}$: $2^3 = 8$
* There are two possible values $\\{true,false\\}$ each for: $\pi(p(x)), \pi(p(y))$: $2^2 = 4$
* There are two possible values $\\{true,false\\}$ each for: $\pi(q(x)), \pi(q(y))$: $2^2 = 4$
* $8 \cdot 4 \cdot 4 = 128$

But now we have to subtract all the interpretations that are not acceptable (no models) from 128. Supposedly the solution should be 24, but I cannot wrap my head around it.

# Answer
> 0 votes
Here's how to count the models:

* There are two options for $a$. Denote the option not chosen by $\bar{a}$ (so if $a = x$ then $\bar{a} = y$, and if $a = y$ then $\bar{a} = x$).
* There is one option for $p(a),q(a)$: both have to hold.
* There are three options for $p(\bar{a}),q(\bar{a})$.
* There are two options each for $b,c$.

In total, we get $2 \cdot 1 \cdot 3 \cdot 2 \cdot 2 = 24$.

# Answer
> 0 votes
These are all the acceptable interpretations for a model of the KB.

---
Tags: artificial-intelligence
---


# Question
Title: Are there search algorithms that perform better on a Rope than a String?
I want to implement fast text-search over a Rope data structure. That is, a B-Tree of characters, where the characters are not sorted. (Meaning the standard way to search in a B-Tree by key does not apply.) This data structure is good for making incoherent edits to, but retrieving the character at a given index takes $O(\log n)$ time. All the text search algorithms I've examined so far seem to assume that accessing characters in $O(1)$ and therefore tend to use a lot of accesses. In particular, the search algorithm I've implemented is performing poorly on large files, (hundreds of thousands of characters.) Profiling reveals most of the time to be spent in retrieving the characters to be compared.

The particular algorithm I currently have implemented is the Two-way string-matching algorithm. I chose it for my first attempt mainly because it needs only $O(1)$ additional memory, and not having an additional data structure to implement seemed like it would speed up implementation.

So, I'm wondering are there any well-described search algorithms exist which are designed for use on a B-Tree, or which otherwise perform well in such an environment? I assume the algorithms I have been looking at are trying to minimize comparisons, which I suppose would tend to minimize character retrieval as well. Does it seems sensible to suppose that one would design an algorithm differently if it was to be used on a data structure with a larger than $O(1)$ indexing time?

# Answer
> 1 votes
Rooted trees, balanced or not, can be traversed in linear time via depth-first search. Actual implementations of balanced trees usually provide a way to iterate through it, taking amortized $O(1)$ for each step. So any algorithm will work without $O(\log n)$ overhead if it makes only a single pass through the string (or if it only requires a small bounded sliding window).

---
Tags: data-structures, optimization, search-algorithms, strings
---


title: Prove that a language is decidable

text:
# Question
Title: Prove that a language is decidable
I need some help to prove that the language is decidable.

$K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}.

It tried to make an algorithm which receives as input a DFA $N$ and which determines whether or not this automaton accepts at least one word which contains no a. But it's kinda complex so any help would be appreciated.

# Answer
> 1 votes
A DFA is essentially a directed multi-graph $G$ in which a distinguished vertex is marked as the initial state $s$, a set $T$ of vertices are marked as accepting states, and edges are labelled with the symbols of $\Sigma$.

The problem is then equivalent to that of deciding whether there is a path on $G$ that goes from $s$ to a vertex in $T$, and uses only edges that are not labelled with $a$.

It suffices to delete all the edges labelled with $a$ from $G$ and to run any graph visit algorithm from $s$. If a vertex in $T$ is discovered you can immediately accept. If the visit terminates and no vertex in $T$ is discovered, then reject.

---
Tags: turing-machines, finite-automata, semi-decidability
---