Why some Huffman codes have efficiency better than others? Consider the alphabet $\mathcal{A}=\{a_0,a_1,a_2,a_3\}$ with the the following corresponding probabilities:

$\, p_{A,1}=\{0.5,0.3,0.15,0.05\}$
$\, p_{A,2}=\{0.5,0.25,0.125,0.125\}$

The entropy for the first case is $H(A,1)= 1.65$, and for the second is $H(A,2)=1.75$. The Huffman code for both can be $\{0, 10, 110, 111 \}$ or $\{1, 01, 001, 000 \}$. The average lengths are $\bar{L_{A,1}}=1.7$ and $\bar{L_{A,2}}=1.75$. The efficiencies are $97.14 \%$ and $100 \%$ for case $1$ and $2$ respectively. Why is that? The only reasonable explanation is the probabilities themselves. In the second case, it is somehow equally divided. Can anyone explain?

First off, though the codes you gave are what the Huffman coding process produces, they aren't the only possible prefix codes for those two cases of sources.

For example, imagine if you used the code $\{\texttt{00}, \texttt{01}, \texttt{10}, \texttt{11}\}$ - then the average length is $2$ and the efficiencies drop to $82.5\%$ (case 1) and $87.5\%$ (case 2).

What the Huffman coding process guarantees is the most efficient prefix code possible for a given source, not a perfectly efficient code for every source.

So your question really is "why is it possible with some sources to make 100% efficient Huffman codes, and with other sources the most efficient possible Huffman code is less than 100% efficient?"

The answer there is that if you have a perfectly efficient Huffman code, then it's impossible to tell the difference between a stream of (source -> Huffman code) and a stream of uniformly random $\texttt{0}$s and $\texttt{1}$s. In your case number 2, with the first Huffman code, you have that situation: a stream of the source encoded by the Huffman code begins with $\texttt{0}$ half the time, and with $\texttt{1}$ half the time. When it starts with $\texttt{0}$, you start a new character from the source and so the next digit naturally is also evenly distributed. When it starts with $\texttt{1}$, half the time the next digit is $\texttt{0}$, half the time $\texttt{1}$, etc. This property (that after any sequence of bits, the chance of the next bit being $\texttt{0}$ or $\texttt{1}$ is $\frac{1}{2}$) means that the resulting binary stream has an entropy of 1 bit of entropy per output bit. (The same as a random binary source)

However, in case 1, (again using the first Huffman code) after seeing a $\texttt{1}$ in the stream, you're more likely to see a $\texttt{0}$ than a $\texttt{1}$. This means that the binary stream you get by connecting your source to the Huffman code has an entropy of less than 1 bit of entropy per output bit. (and therefore, that the binary stream is carrying less information per output bit than a random binary source)

The perfect match in case 2 happens because the probabilities of the source are all (negative) powers of $2$ and the probability of each output symbol matches the probability that a uniformly random noise source would output the symbol's Huffman string. Basically, the maximum possible efficiency for a Huffman code is a measure of how well a source's output probabilities can be approximated in binary.

Note that if we took your case 1 source and considered outputs two at a time, we'd be able to better approximate the probabilities in binary, and therefore get a more efficient Huffman code:

$$
\begin{array}{|c|l|l|}
\hline
\mathrm{output}& p & \mathrm{Huffman}\,\mathrm{code} \\ \hline
a_0a_0 & 0.25 & \texttt{10} \\ \hline
a_0a_1 & 0.15 & \texttt{000} \\ \hline
a_0a_2 & 0.075 & \texttt{0100} \\ \hline
a_0a_3 & 0.025 & \texttt{01110} \\ \hline
a_1a_0 & 0.15 & \texttt{001} \\ \hline
a_1a_1 & 0.09 & \texttt{110} \\ \hline
a_1a_2 & 0.045 & \texttt{1110} \\ \hline
a_1a_3 & 0.015 & \texttt{011010} \\ \hline
a_2a_0 & 0.075 & \texttt{0101} \\ \hline
a_2a_1 & 0.045 & \texttt{1111} \\ \hline
a_2a_2 & 0.0225 & \texttt{011000} \\ \hline
a_2a_3 & 0.0075 & \texttt{0110011} \\ \hline
a_3a_0 & 0.025 & \texttt{01111} \\ \hline
a_3a_1 & 0.015 & \texttt{011011} \\ \hline
a_3a_2 & 0.0075 & \texttt{01100100} \\ \hline
a_3a_3 & 0.0025 & \texttt{01100101} \\ \hline
\end{array}
$$

This has an average code length of $3.3275$, whereas the double-output source has an entropy of $3.30$ for an efficiency of $99.04\%$.

If you continued this process to 3 symbols at a time, you'd be able to get a $99.24\%$ efficient code. To 4 symbols, $99.43\%$ efficient.


Lambda Calculus beta reduction I am trying to learn Lambda calculus from here

and while trying to solve some problems, I got stuck. I was trying to solve the following problem (page 14, excercise 2.6 part (i):

Simplify $M \equiv (\lambda xyz.zyx) aa (\lambda pq. q)$.

My evaluation using the beta rule reduces it to $(\lambda z. z)$ as follows:
First I replace occurences of $x$ in $M$ by $aa (\lambda pq. q)$, and then since there are no occurences of $y$ in the resulting $\lambda$ term, the expression simply evaluates to $(\lambda z. z)$.

Is my reasoning correct? (Since there were no solutions to these notes, I want to ensure my understanding is correct. Any corrections, will be much appreciated! Thanks in advance.

No, your reduction is wrong. The function $(\lambda x y z. z y x)$ is applied to three arguments: $a$, $a$ and $(\lambda p q. q)$. It is not, as you wrote, a the function $(\lambda x y z. z y x)$ applied to the term $a a (\lambda p q. q)$; that second term does not appear in $M$. Strictly speaking, functions in the lambda-calculus take three arguments, they are effectively curried, so if you add optional parentheses $M$ can be written
$$
(((\lambda x. (\lambda y. (\lambda z. (z y) x))) a) a) (\lambda p. (\lambda q. q))
$$
This reduces by substituting $a$ for $x$ in $(\lambda y. (\lambda z. (z y) x)))$, then $a$ for $y$ in the result of this:
$$
M \to (\lambda y z. z y a) a (\lambda p q.q) \to (\lambda z. z a a) (\lambda p q. q)
$$
then substitute $(\lambda p q. q)$ for $z$, after which a new redex appears:
$$
\ldots \to (\lambda p. (\lambda q. q)) a a \to (\lambda q. q) a \to a
$$


Finding which value I will be on after a certain number of steps I have a fixed array: [a,b,c], I wanna loop through this 3-items-sized array for 7 times in order to find what I would get at that exact step.
The "value stack" for 7 would look like a b c a b c a.
Question is, how can I find what value would be at step 10, for example?

Input: getValueForStep( [a,b,c], 7 )
Output: a

A simple observation is that, with 0-based indices:
final_index = (elements_traversed - 1) mod array_length

For example, for array_length = 3 and elements_traversed = 7, final_index = (7 - 1) mod 3 = 0 (corresponding to the first element).


Regular expression for words over $\{0,1\}$ containing at least one 1 I had an exam on Theory of Computation, and one of the questions was to write down a regular expression for the language over $\{0,1\}$ consisting of all words containing at least one 1. My answer was:

$$ 0^* 1 0^* (0^* 1 0^*)^* \, . $$

My teacher gave me one mark out of 5, yet I can't find a possible string that will give false output here! His answer, which was $(0+1)^*1(0+1)^*$, was better, but mine works as well, I believe.

  Is my answer correct?

Your answer is correct. $0^*1$ matches the portion up to the first $1$. After that, any subsequent $1$s may have any number of $0$s between them.

There are slightly simpler regular expressions for the same language. For example,

$$0^*10^*(0^*10^*)^* \ \equiv\  0^*10^*0^*(10^*)^*\ \equiv\ 0^*10^*(10^*)^*\,.$$

You could also observe that a string with at least one $1$ is formed of some number of initial $0$s, followed by the first $1$, followed by anything else, leading to $0^*1(0+1)^*\!$, which is arguably slightly simpler than the teacher's solution.

However, you should consider that you probably lost marks for reasons other than the teacher mistakenly thinking that you were wrong. I wouldn't allocate five marks just for writing down a simple regular expression. To me, that would be either a one-mark question (one mark for right, none for wrong) or a two-mark question (two marks for right, one for being close and maybe missing a corner case, none for wrong). For five marks, I'd expect an explanation of why the regular expression does what it's supposed to do.


On submultisets of given cardinality and bound that sum to $0$ Given multiset of integers $a_1,\dots,a_{m}$ where $|a_i|\leq\log^cm$  for some $c\in\Bbb R^+$. Is it $\mathsf{NP}$-complete to decide if there is a cardinality $\lceil m^\alpha\rceil$ submultiset for some $\alpha\in(0,1)$ whose sum is $0$?

How many submultisets of such cardinality can we expect to have vanishing sum?

Assuming that $c$ is fixed, this can be solved using dynamic programming in quasipolynomial time. We compute inductively all possible sums of all submultisets of size $k$ for all $k \leq \lceil m^\alpha \rceil$. Since each such sum is at most $2^{\log^c m} \lceil m^\alpha \rceil$, this algorithm runs in $O(2^{O(\log^c m)} m^{O(1)})$, which is quasipolynomial. This suggests that the problem is not NP-hard.


If pref(L) is regular, does that imply L is regular? I have this exercise for homework:

  Say we have a language L. we know that the language pref(L) (all the prefixes of L, including all the words in L itself) is a regular language. Does this imply that the language L is regular as well?

I took the NFA of pref(L) and divided it (via 2 epsilon transitions from q0) to 2 separate NFA's, as 1 defines L and the other defines pref(L)\L.

What I actually got is a NFA for L, which means it is regular.

I am not sure this is the way or if it legal. I'd be glad for another lead.

What you say doesn't make sense. How can you operate with a NFA for $L$ if you cant be sure that $L$ is regular?

Try to consider this language
$$L=\{ uu \mid u \in \Sigma^*\}$$
This language is not regular, it is not even context-free, which can be shown with the pumping lemma. I think from here you can continue by yourself. What is $\text{pref}(L)$?


Why is Savage's Vertex Cover algorithm a 2-approximation? Carla. D. Savage formulated the following approximation algorithm for the vertex cover problem.

Given graph $G$, start at arbitrary node and traverse $G$ depth-first
Obtain DFS tree $T$
return $V_C =$ internal nodes of $T$.

Now I read everywhere that this algorithm is supposed to yield a 2-approximation, but the only proof I found was here, and frankly, I don't get it and it's rather longish. Unfortunately also, the original paper is nowhere to be found. At other places where this was given as an exercise, I find the hint that one should first show that the tree $T$ admits a matching $|M| \ge \frac{1}{2} |V_C|$. But if I had proved that (which I have no clue how to do), I have no idea how to use that knowledge. I don't see how I can put bounds on the output of the algorithm without an estimate for the number of internal nodes of an arbitrary tree. And the way I see it, such a tree can have between $1$ and $n-1$ leaves (consider the graphs which are a chain, or a star, respectively).
So I am puzzled. How could one show that this is a 2-approximation?

First of all, you have to show that $V_C$ is a vertex cover. This is because any edge touching a leaf also touches an internal node.

Next, we show that the DFS tree has a matching of size at least $|V_C|/2$. Since each vertex cover must contain at least one vertex from each edge in the matching (since any one vertex covers only one edge from the matching), this shows that the minimum vertex cover has size at least $|V_C|/2$, so we get a 2-approximation algorithm.

It remains to show that any tree $T$ has a matching of size at least $I(T)/2$, where $I(T)$ is the number of internal node. The proof is by induction on $|T|$. If $T$ contains one vertex then $I(T)=0$ and so there is nothing to prove. Now suppose that the tree contains a root $r$ and subtrees $T_1,\ldots,T_n$. Let $r_1$ be the root of $T_1$, and let $S_1,\ldots,S_m$ be the subtrees of $T_1$. The matching we are going to construct consists of matchings in $S_1,\ldots,S_m,T_2,\ldots,T_n$ together with the edge $(r,r_1)$ (you can check that this is indeed a matching). This matching contains at least $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2$ many edges. We obtained the forest $S_1,\ldots,S_m,T_2,\ldots,T_n$ by removing two vertices $r,r_1$, so $I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n) = I(T)-2$. This completes the proof since $1+(I(S_1)+\cdots+I(S_m)+I(T_2)+\cdots+I(T_n))/2 = 1+(I(T)-2)/2 = I(T)/2$.


Has this generalization of Turing machines studied before? Introduction

Hello, I'm designing a generalized model of Turing machines for a formalization in MIZAR. Mizar needs some concrete objects to work with, so I spent some time figuring out how the "tape" of a Turing machine could be defined since that part is usually left out when introducing Turing machines.
After some thinking I concluded it would be best to use graphs, so I define a "Turing Space" $T$ as a function from an cardinal $C$ to graphs. A position $p$ in the Turing Space is then defined as a function from the cardinal into the vertex sets of these graphs, so that for $c\in C$, $p.c$ is a vertex of $T.c$. From this basis one can built transition functions and so forth.

Examples

Given a double ray (a path graph that is infinite in both directions) $R$ and a positive integer $k$, the function $f_k:k\ni i\mapsto R$ (defined on $\{0,\ldots,k-1\}$) would be a Turing space describing the bands of a $k$-band TM.
Given a positive integer $d$, set $E_d:=\{\{a,b\}:a,b\in\mathbb{Z}^d,\sum|a_i-b_i|=1\}$ and graph $G_d=(\mathbb{Z}^d, E_d)$, this is the grid on $\mathbb{Z}^d$. Now the function $g_d:\{0\}\ni i\mapsto G_d$ describes the hyperspace of a $d$-dimensional TM.
These two examples are of course quite different, as the first has $k$ pointers, that can move in 3 directions (left, right, stay) each, and the second has one pointer that can move in $2d+1$ directions. That they are nevertheless computational equivalent (because they are Turing-complete) is well known. Also both reduce to a simple Turing tape in case of $k=d=1$.
It is easy to see that other well-known tape variants can be described by this definition just as well.

But it doesn't end there

However, the definition above allows much more complex examples for tapes, most notably when using infinite cardinals. And when I'm about defining Turing machines, I wonder why I would restrict the alphabet and set of states to be finite. Of course, these generalizations make it much more difficult to image any kind of realization in the real world. Nevertheless, I think it is kind of interesting if these generalizations of a TM would make it possible to archive something beyond Turing completeness. Other known generalizations such as non deterministic TMs and quantum TMs do not seem to have archived greater computability. Maybe I missed something?

The Question

Has my kind of generalization (the different "Turing Spaces") been studied before? Or any kind of allowing infinite states and/or alphabets besides the kind appearing in quantum TMs?

A general notion of machines based on graphs was given by Wilfried Sieg and John Byrnes in K-Graph Machines: Generalizing Turing's Machines and Arguments. It may or may not be related to what you are doing.

Also note that it is quite easy to find a complete formalization of Turing machines. Why are you saying that "the tape of a Turing machine ... is usually left out when introducing Turing machines". That's an odd thing to say. Let's perform an experiment. For instance, what is unclear about the definition given on Wikipedia (following a standard textbook)? All you need is a formalization of finite sequences, and I'd be flabbergasted if Mizar hasn't got those.


How to Efficiently Define the Natural Numbers in Type Theory A while ago I wondered about how Proof Assistants like Coq prove $m \leq n$ and the like. It looks like they actually need to traverse the natural numbers based on the successor/predecessor formulation:

  Coq < Eval compute in le_lt_dec 100000 1000000.
  Warning: Stack overflow or segmentation fault happens when working with large numbers in nat (observed threshold may vary from 5000 to 70000 depending on your system limits and on the command executed).
  Stack overflow.

One of the answers suggested using the BinInt (Binary Integers representation) to perform this operation.

  When a mathematician looks at a claim like $1000 ≤ 1000000$ and says "obviously", they are taking advantage of the fact that we wrote the claim in decimal notation. If you want to do something similar in CoQ, you could try to prove, e.g., $10∗10∗10≤10∗10∗10∗10∗10$.

So I'm wondering if there is a standard way of representing numbers as types without defining them like Peano's axioms style, using successor/predecessor and the like. Something that allows you to prove two numbers have a relation such as $m \leq n$ or $m \neq n$ or do other common things with numbers like adding/subtracting, in such a way where the "formal definition" (i.e. succ/pred) of the numbers is combined with some more computationally optimal version so you can use it in practice. Not sure what best-practice is to do here, but I would like to define a numbers type and have it gain all the advantages of proof theory / proof assistants, while also being the actual type definition used to construct i.e. integers.

There's nothing stopping you from defining binary numbers in type theory, and this should give greater efficiency in practice.

For example:

https://coq.inria.fr/library/Coq.Numbers.BinNums.html

EDIT: Why not base 10?

Comparison on binary numbers can be done in $O(\log_2 n))$ time. If you have base 10, you can do it in $O(\log_{10} n)$ time. But if we apply the change of base formula, $O(\log_{10} n) = O(\log_{2} n / \log_{2} 10) = O(\log_2 n)$, since $O(\log_2 10)$ is constant.

There's a speed tradeoff. You get constant speedup for some operations, but you get constant slowdown for others. For example, each pattern match now has 11 options instead of 3. So, given that they have the same asymptotic behavior, we usually go with the simplest one.

Finally, the advantage with base 2 is that, if you limit yourself to 32 or 64 bits, you can represent them using machine integers, for example, if you extract your Coq code to OCaml, which means you can get very fast extracted code.


Unclear about proof for unique MST given graph G with distinct weights http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf

I have some trouble understanding the proof above.

I understand that we assuming two MSTs, T and T', and an edge e that is the cheapest edge of G that located in T. Then the weight of this edge is larger than any weight on T', given that T' contains (x,y), by definition of MST.

My question is why do we assume that T' passes through (x,y)? Wouldn't it natural to assume that T' is completely disjoint from T?

The edge $e$ is not necessarily the cheapest edge of $G$ that is in $T$. Rather, it is the cheapest edge in the symmetric difference $T \triangle T'$. It could belong to either $T$ or $T'$ (but not both!), but since both cases are the same, we assume that it belongs to $T$ without loss of generality.

We don't need to separately consider the case that $T$ is disjoint from $T'$ and the case that they share some edges. All we need to know is that they are different and so their symmetric difference is not empty.


A context free grammar proof There is a problem which I cannot solve. If you give a tip I will be very glad.

Prove that following language is not context free:

$L= \{ a^nb^m | \gcd(n,m) = 1 \}$.

It can be proven using the pumping lemma, but how?

If I start with some prime numbers $m$ and $n$ where $m>n>2$ and pump it up from $uVxYz$, there are three possible outcomes: $a^{n + k} b^m$, $a^{n +k}b^{m +k}$, $a^n b^{m +k}$. Since I do not know whether $k$ is even or odd I cannot say something. It is certain that $a^n$ and $b^m$ will be odd. However after adding $k$ to some of them, how can I say something about whether their gcd is 1 or not?

Hint...

There may be a direct application of the pumping lemma, but I suggest you take a look at closure properties. Consider the non-CFL in the first answer to the reference post, $P=\{a^p:p \text{ prime}\}$, which is clearly a cousin of $L$. Can you find a (fairly simple) operation on $L$ that preserves CFLs and more or less yields $P$?  If so, you are done, except perhaps to tidy up with some other operations to deal with special cases for $P$.

In general, when languages are relatively "dense", that is, have a high proportion of members to non-members for all given lengths, it's harder to apply pumping arguments, because it's more work to pump to get outside the "dense" set; in fact, sometimes it's impossible.  $P$ is a nice "sparse" set, so pumping works well, as shown in the reference post.  $L$ is quite a bit "denser", so transforming it to a "sparser" form is a good tactic to try.

The classical example of this principle (for non-regular languages) is the very dense set $\{a^ib^j:i \neq j\}$ and the corresponding sparse set is $\{a^ib^i\}$. The operation in this case is complement, again with a "cleanup" operation needed as well.  As part of the above hint, the operation there is not complement, which doesn't work for CFLs anyway.


Prove that the number of full nodes plus one is qual to the number of leaves in a nonempty binary tree I'm trying to write an induction statement to prove a full node in a tree but I have no idea how to do that. I've always been terrible when it comes to logic. Where do I even start with this?

I know that a full node has 2 children.

Well, an induction proof consists of a base case and an induction step. For trees that is usually structural induction, based on inductive ways trees are built.

The base case considers the smallest binary tree, which cannot be composed further. Show that one has the Property.

The induction step argues that the Property is true for any tree $T$ assuming the Property holds for its subtrees $T_{\textrm{left}}$ and $T_{\textrm{right}}$. That assumption is called the induction hypothesis.

There is another approach, induction based on the number of (full) nodes, called natural induction. Base case has a single full node. Induction step argues Property is true assuming Property holds for any tree having less full nodes.


How can languages that are E-complete have sub-exponential size circuits? The question whether there exist languages in $\mathsf{E}$ that require circuits of size $\Omega(2^{\delta n})$ for some $\delta > 0$ is open, and this would imply some derandomization results.

Suppose we have a language $L$ which is complete for $\mathsf{E}$. Then, how can $L$ have sub-exponential size circuits? If $L$ has a circuit of size $s(n)$ where $s(n) = o(2^n)$, then we can construct a machine $M$ which evaluates the circuit in time polynomial in $s(n)$ on any input $x$, which implies that $L \in DTIME(poly(s(n))$, which we know cannot happen because of the time hierarchy theorem.

Obviously, I must be missing something here, otherwise why is this such an important and open question?

What you're missing is that it might be hard to construct the circuits. In order for your algorithm to simulate the circuit, it needs to know the circuit, but since the circuit depends on $n$, you can't hard-code it — you'll need to hardcode an infinite number of circuits.

To give a simpler example, consider the following language:
$$
\{ x : \text{The $|x|$th Turing machine halts on the empty input} \}.
$$
This is an uncomputable language which has constant size circuits.

What could not be the case is that some language in $\mathsf{E}$ has uniform subexponential circuits, for a suitable notion of uniformity (given $n$, you need to be able to construct the circuit in time subexponential in $2^n$). Your argument would work then, since the algorithm would be able to construct the circuit in subexponential time.


Algorithm to generate inputs with certain properties, but not accepted by a given regular language General

Given a regular language $L \subset \Sigma^\star$, I wish to generate at least one string not in $L$. (Obviously, this requires that there exists such a string; i.e., that $L \neq \Sigma^\star$. I would be interested in ways to decide this, if any exist.)

(Harder) I wish also to generate at least one string not in $L$, but such that the property $P$ holds. (Again, this requires $\exists w \not\in L : P(w)$ and $\exists w \in \Sigma^\star : P(w)$, but of course one must know $\Sigma,L,P$ to prove any of these.)

A somewhat naïve approach, when we can reliably generate $w : P(w)$, is to do so until $w \not\in L$. For the specific case below, this is not terribly difficult once we can generate strings from a context-free grammar. Is there better?

Specific

After thinking about Balanced braces, my stack-based implementation, and my slight rant about students knowing regular expressions are not sufficient for this problem, I would love to be able to do the following:

Given a regular expression1 that supposedly solves the balanced parentheses problem2, I would like to generate a string in the (context-free) language of balanced parentheses that is rejected by the regular expression.

This would be a nice way to highlight, based on intuition, that some languages are more bigger than others. It would also prove that the given RE is not equivalent to the desired language, though of course it does not constitute a proof that no RE is equivalent.

So, to recap:

$L$ is an attempt to recognize all strings in the language of balanced parentheses (doomed to fail);
$\Sigma = \{(, )\}$;
$P$ is the property that the given string is in the language of balanced parentheses

We can stick with the "proper" definition: concatenation, alternation, and Kleene-star repetition)
Again, stick with just ( and ) for simplicity

For your specific question, you are asking to generate a string in $\bar{L} \cap P$.  Note that since $L$ is regular, so is $\bar{L}$; and note that $P$ is context-free.  It is known that the intersection of a regular and context-free language is context-free.  So, you're asking: given a context-free language, how do we generate a word in that language?  This is straightforward.

Concretely: you could represent $L$ as a DFA, then take the complement to get a DFA for $\bar{L}$.  You could represent $P$ as a context-free grammar.  Then, using a product construction, you can obtain a context-free grammar for $\bar{L} \cap P$, remove all non-productive nonterminals, and then generate a random derivation in the grammar (or, if you want to get fancier, you can search for the shortest word in the grammar using a simple algorithm).

The product construction works by replacing each nonterminal $T$ from $P$ with nonterminals of the form ${}_sT_t$, with the intended meaning that $L({}_sT_t)$ is the set of all words $w \in L(T)$ such that if you start the DFA in state $s$ and then feed in $w$, it ends in state $t$.  You can figure out how to modify all the rules of the grammar, e.g., $T \to UV$ becomes the collection of rules ${}_sT_u \to {}_sU_t {}_tV_u$ for all states $s,t,u$.

You can find the shortest word in a context-free grammar by a simple iterative algorithm.  For each grammar symbol $T$, let $\ell(T)$ denote the length of the shortest word generated by $T$, i.e., the shortest word in $L(T)$; we assume $\ell(a)=1$ for all terminals.  As a notational convenience, if $\alpha=\alpha_1\cdots \alpha_k$ is a string of terminals and non-terminals, set $\ell(\alpha)=\ell(\alpha_1)+\dots+\ell(\alpha_k)$.  Initially, set $\ell(T) := \infty$ for all nonterminals $T$ and treat all rules as unmarked.  Then, repeat the following.  Pick an unmarked rule $A \to \alpha$ where $\ell(\alpha)<\infty$, set $\ell(A) := \min(\ell(A), \ell(\alpha))$, and mark that rule.  Repeat until convergence.  After this is finished, $L(S)$ tells you the length of the shortest word output by the grammar, if $S$ is the start symbol of the grammar.  You can augment the algorithm to keep track of the word itself as well as its length, and then you'll be able to output the shortest word in the grammar.

This might be handy for your application, because it gives you the shortest counterexample: the shortest string that has balanced parentheses but isn't accepted by your regexp.


Minimum number of rotations of a binary tree to convert it into another I have the following binary tree, which I'm trying to convert into the target binary tree (second tree in the post) using minimum number of tree rotations. The theoretical minimum number of rotations for this tree is 5, however, the smallest value I can figure out is 6 rotations, I have copied the rotations as well, what am I missing?

Tree:

 1
  \
   \
   3
  / \
 /   \
 2    5
    /   \
   /     \
   4      7
        /   \
       /     \
       6     11
            / \
           /   \
           9   12
          / \
          8 10

Target Tree:

     1
      \
       \
       11
      /   \
     /     \
     9      12
    /  \
   /    \
   3     10
  /  \
 /    \
 2     5
      / \
     /   \
     4   7
        / \
        6 8

The rotations I have tried so far (all of which require 6 rotations):

Order1:

Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 3 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9

Order2:

Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9

Order3:

Rotate left with root 7 and pivot 11
Rotate left with root 5 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 3 and pivot 9

Order4:

Rotate left with root 7 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 11
Rotate left with root 3 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 9

Order5:

Rotate left with root 7 and pivot 11
Rotate left with root 7 and pivot 9
Rotate left with root 5 and pivot 11
Rotate left with root 5 and pivot 9
Rotate left with root 3 and pivot 11
Rotate left with root 3 and pivot 9

First rotate 9 right around 11 to make a linear tree.


Size of instance after reduction A decision problem $C$ is $NP$-complete if $C$ is in $NP$, and every problem in $NP$ is reducible to $C$ in polynomial time.

Reduction means transforming an instance of one problem $A$ to an instance of another problem $B$, and by using an algorithm that solves $B$ we can obtain the solution to $A$ for our original instance.

Is there any relationship between the size of instance before and after reduction? If for example the algorithm solving $A$ is $O(n^2)$ and our instance of $A$ of size $n$, what can we say about the instance size after reducing it to $B$, whose algorithm is $O(2^n)$ (the complexity of algorithms actually doesn't matter). Is it $n$ as well? Or maybe it is a polynomial of $n$?

The question is if the fact that a problem $A$ can be reduced to $B$ in polynomial time tells us anything about the size of the resulting instance (of problem $B$) with respect to the size of initial instance of $A$.

Why? It is known that

  If we had a polynomial algorithm for an $NP$-complete problem we could
  solve any other $NP$ problem in polynomial time

right? Because we just reduce $NP$ problem to $NP$-complete problem in polynomial time and solve it in polynomial time.

Let's say problem $A$ is $NP$ and problem $B$ is $NP$-complete. I've found an algorithm for $B$ that is $O(n)$ (polynomial). And let's say the size of our $A$ instance is $k$.  If I reduced it to $B$ in polynomial time and got an instance of $B$ of size $n=2^k$, then the total time of solving it wouldn't be polynomial. So certainly the polynomial time reduction can't give an instance of size $2^k$, because if it could, then the quote above wouldn't be true.

First of all, for your definition of NP-complete, we require the reduction to be polynomial time. This makes it so that if we could solve an NP-complete language, L, in polynomial time, we would have a polynomial time algorithm for all of NP by composing the polynomial time reduction with that algorithm for L.

Note that the size of the output of a reduction has to be less than the run time of the reduction. The biggest output possible given a fixed run time would be one where a Turing machine, M, prints to its output tape at every step.


linear time nash equilibirum aproximations for two player zero sum games I'm working on an AI for a game where I'd like the game where each player has hundreds of moves to select from and so the game matrix has 10s of thousands of entries. The game is however zero sum. Given that I have 10s of thousands of entries I can't apply even an $O(n^2)$ algorithm or the result will take too long so I need a linear time algorithm. I've found this note which details an exceedingly simple $\frac{1}{2}$-approximation algorithm that works for any game, not just a zero sum game. It also does so by only looking at $O(\sqrt{N})$ entries in the table which is even faster than what I need.
Zero sum games can have their exact equilibrium computed in polynomial time via linear programming but this is too slow.
What I'm looking for is something in between; Something that uses more computational resources than the simple 1/2-aproximation algorithm but gives a better approximation; Something that uses fewer computational resources than linear programming but only gives an approximate answer. Does a linear time approximation algorithm exist for 2-player zero-sum games that is better than $\frac{1}{2}$-approximation?

By choosing a different framework of thought that does not attempt to ensure a specific bound we can do well in practice using an algorithm called regret matching.. The paper introducing this is called "A Simple Adaptive Procedure Leading to Correlated Equilibrium" by Sergui Hart and Mas-Colell
.
Regret matching is ensured to almost certainly converge to a nash equilibrium for a zero sum gum. There does not seem to be a ton of literature on the convergence rate but in practice it seems that for small matrices it converges close to the equilibrium in a matter of thousands of iterations. Additionally there are many strategies for speeding up convergence that sacrifice guaranteed convergence such as shareholding, or incorporating negative regret along with some normalization procedure. Regret matching has the extreme benefit of being exceedingly simple as well.
Regret matching is the basis for counter-factual regret minimization which is the technique behind state of the art poker AIs.


Do finite state machines need transitions for all symbols? I want to know if I want to draw up a finite state machine, say for example binary strings and I want a finite state machine that accepts only one kind of binary string e.g: 0110. Do I, for each state have to account for another symbol of the binary language being read during transition. Like for the first transition, this will be caused by 0 being read, but what if a 1 is read...do I have to implement a trap state or do I just not account for the fact that a 1 could be entered 1st?

Your question isn't entirely clear but it's easy enough to just list all the possible answers that could arise, depending on exactly what you mean.

If you're asking about nondeterministic finite automata (NFAs) then you don't need to account for every symbol. The rule is that, if you're in a state and you encounter a symbol that has no transition, then that branch of the computation rejects immediately.

If you're asking about deterministic finite automata (DFAs), then it depends on exactly what definition you're using. The classical definition (e.g., in Sipser) is that every state must have exactly one transition for each possible symbol. In that interpretation, you need a trap state, since you must specify what happens for every possible symbol you could read. Other authors, though, say that each state of a DFA has at most one transition for each symbol. In that case, you don't need a trap state: as with an NFA, if you read a symbol that has no transition, you reject.


Why is memory one dimensional? Addresses in system programming languages like C are one dimensional (i.e. one number). This forces the programmer to make a decision whether matrices are stored "row major" or "column major" causing the opposite access to be slower.

This is somewhat surprising, since I think I remember that physical RAM is actually a 2 dimensional structure. And looking at the free part of this article. It seems like there exists a burst mode for accessing multiple elements from the same row.

Why does this burst mode not exist for columns, and why do programming languages not allow for true two dimensional storage of data? This would allow for "row major"/"column major" agnostic designs, which would probably speed up a lot of linear algebra libraries. Which would then trickle down to statistics and machine learning.

(Crosspost from StackOverflow)

You're asking multiple questions.

Why are instruction set architectures designed to use a one-dimensional address space for memory?  Memory isn't actually one-dimensional, but providing a one-dimensional abstraction is very convenient.  It makes programmer's lives simpler, it makes the CPU architecture easier to specify in a comprehensible way, and it provides a single flexible abstraction that isn't tied to a particular technology of the moment or a particular device or platform.

It's not the CPU's abstraction for memory that forces you to choose between row-major vs column-major storage, and cause the opposite way of accessing a matrix to be slower; it's the way DRAM works that forces this decision.

Why don't RAM chips provide both a row-burst and column-burst? Our current DRAM technology is highly optimized for cost, density, and power.  Supporting additional features like that would be more expensive and more complex.  It's likely that the potential performance gains you're hoping for are not worth the additional expense, and would be modest for most
applications, hence not worth it.


Why is ARP needed in a host - router system if the router already has list of addresses it assigned using dhcp? The hosts are assigned IP address by the router using dhcp. So, the router has a list (mac addresses) of all the hosts that are directly connected to it as well their ip addresses.
Now if a packet comes from outside, the router must be able to find the destination mac address from its logs. Then what is the need to use ARP in such a case (hosts connected to router)?

The only time I see an use of ARP is when router has to find new routers. Using ARP allows it to find new routers as well as to force a more rigid use of longest matching address method if needed. However what is the use of ARP during "router to host" packet transfer?

The fact that the router has the list does not help when computer A wants to talk to computer B, because neither of the two has the list.


“Standard” approach to syncing data? I'm wondering if there are any universally accepted "best" algorithms for syncing data sets.

I imagine there would be different solutions depending on circumstances:

Are all peers online all the time or not?
Are we more limited by bandwidth or processing power?
Are data items large or small?
Does data get modified and deleted or are we just accumulating a growing collection of data?

My question is what are the equivalents to Djikstra's and Kruskal's algorthim of my problem?

You might say the two well known algorithms mentioned solve problems which are much more specific. That's probably true, so let me narrow down my question:

What is a good way to calculate a diff between two versions of a large growing set of very small chunks of data? Assume data is never deleted or modified, synchronisation happens between a limited number of peers, somewhat regularly but there is no real server and client situation, any peer could have some new data.

I feel I just don't know where to start looking, what papers to read.

I don't know that there is any "standard" or "best" approach, as the technique that is appropriate will depend on the setting.  However, I recommend you start by looking at the algorithms used by rsync and the Remote Differential Compression scheme.  More generally, look at techniques for delta compression.


Reading CLRS analysis of hashing with chaining I'm currently reading an analysis hashing with chaining, and it goes over two examples:

  In the first, the search is unsuccessful; no element in the table has
  key k. In the second, the search successfully finds an element with
  key k.

(This is all under the assumption of simple uniform hashing). I understood the analysis for the first case, but the second confuses me. The book goes:

  The situation for a successful search is slightly different, since
  each list is not equally likely to be searched. Instead, the
  probability that a list is searched is proportional to the number of
  elements it contains.

The above sentences are what confuses me. Why is each list not equally likely to be searched if both operate under assumption of simple uniform hashing? And why in the world would the number of elements a list contains have any effect at all on the probability that the list is searched? I would think it's the opposite...the number of elements searched in a list depends on the probability that a key is hashed to a particular index (where the list is).

I assume that you are talking about the hash-table that uses an adjacency list for the elements that have the same hash key (hash table using chaining). Let's look at a very simple example.

We have a hash table such as the following:

key : like list of elements
1   : x_11 -> x_12 -> ... -> x_11000000 -> NULL  // 1000000 elements
2   : NULL                                       // 0 element
3   : x31 -> NULL                                // 1 element

If you look at keys 1 and 3, which one is more likely to be visited? The answer is 1, because it has more elements than all other lists. Therefore, we are more likely to find the mysterious element in 1's linked list.


Constructing a data structure for a computer algebra system In thinking about how to approach this problem I think several things will be required, some tivial:

An expression tree where non-leaf node is an operation (not sure if that part is redundant), but not every node has just two children.
All nodes for operations have a defined number of children that they must have (some operators are unary (like $!$) while others are binary ($*,+,-,$ etc) and still other are n-ary ($f(a,b,d)$ and versions with different amounts of variables).
All leaf nodes are some type of number

I am under the impression that the tree should not explicitly retain information regarding the order of operations, but rather that information should be used in the parsing stage to insert things into the tree correctly.

This leads to the question, how should inserting to a specific position in the tree be done? Simply passing a list of directions (from root, take node zero, then node 1, etc, then insert) will work, but it seems overly clunky.

Or should I avoid that situation entirely (not talking about editing an equation here, just building a representation of one) by using the fact that in some sense the tree must be complete (all binary operations MUST have two children, etc, and even operators that are seemingly ambiguous (the $_{^-}$ sign for example) but these ambiguities are resolved before this point. That would all me to insert "in order"

Am I taking a reasonable approach? Does it make no sense whatsoever?

Additionally, are there papers or articles that I should read about CAS systems?

Clarification: The tree will need to support three different compound operations.

Creation: (from a string, but how to actually do that is beyond the scope of this question)
Reduction: (to some type of canonical form) so that if $a+b$ and $b+a$ are both entered and reduced, they will form identical trees.
Evaluation: Be able to traverse the tree

These are all the operations that need to be supported. There are probably many other more basic operations that may need to be supported, but in this case it only matters that the three operations above are supported. My understanding is that search for example is not a property that will be required, but deletion will be (of a whole subtree).

From the comments OP wrote, I understand he wants to start small. However, we need to think more generally so that the to-be developped CAS can be of real use. Otherwise it is nothing but another calculator. Please see Definition of Computer Algebra System.

My suggestion:

Numbers, elements, sets, operations, etc. are fundermental in algebra. The data structures will have to be about them. In particular, you can start with elementary set theory. Determine what will be an element, a set, etc. The elements should be generic(they can be anything). Abstraction is the key. Then, what are the operations associated with them? Constructing a set, membership test, union, intersection, etc. Once we have them in place, plug in the number manipulation packages to the system is a matter of instantiation.


Little endian architecture, Address 0000 stores 0xde
0001 stores 0xad
0002 stores 0xbe
0003 stores 0xef
Treat the data stored as 2 16 bit integers, what are the two values stored?
I thought the answer would be 0xadde and 0xefbe but I was wrong. Why?

Let's program it and see what happens:
#include <stdio.h>

int main(int argc, char *argv[]) {
  unsigned char mem[4] = { 0xde, 0xad, 0xbe, 0xef };

  printf("%02hhx %02hhx %02hhx %02hhx\n", mem[0], mem[1], mem[2], mem[3]);
  printf("%04hx %04hx\n", *(unsigned short *)(mem), *(unsigned short *)(mem + 2));
}

Here is the output:
de ad be ef
adde efbe


Design a DFA which accepts words with sorted letters I have just started learning Theory of Computation and have come across a question which I am not able to solve.

The question is as follows:

Design a DFA that reads a word (character strings) and decides whether the letters
of the word are in sorted order.
For example: 'adept' and 'chilly' have their words in sorted order but 'baby' doesn't.

How should I design a DFA for this language?

What I have tried:

I think there must be two states.

1) While the DFA is scanning the word, the state (q1) will transit to itself
if it reads a letter greater than or equal to previous letter read.

That is if the current_letter_read >= previous_letter_read then
q1 transits to itself. Otherwise, there is no action.

2) If '\0' is encountered, then the DFA transits to the final accepting state.

But in DFA is it possible to do so? How should I draw a DFA for this?
I got stuck at this point. Am I missing some basic concept that I should know?

Your suggestion is to use two states and stay in the first one until the machine reads a character that is strictly before the last one it read. This can't be right because a DFA can't test the current character against previous ones. A DFA knows exactly two things: which state it's in now and what the next character of the input is. Its decision about which state to move to is based only on those two pieces of information and everything from the past is forgotten.

When designing automata, it's a good idea to think about what each state means. For example, consider the following automaton, with states that I'll unhelpfully call $A$ and $B$. $A$ is the start state and is accepting; $B$ is non-accepting. Whenever the automaton reads a character, it moves to the other state. What does it do?  Well, it accepts the empty string because the start state is accepting. If it reads a character, it moves to the non-accepting state $B$; if it reads another one, it moves back to $A$. So, whenever the machine has read an even number of characters, it's in $A$ and, whenever it's read an odd number of characters, it's in $B$. It would, therefore, make much more sense to call the states "even" and "odd" because that's what they represent.  Knowing that, you could easily write an automaton that accepts exactly words whose length is, say, equal to  2, mod 3.  Or exactly the words equal to 3, 5 or 11, mod 12.  Being a bit more clever, you could write an automaton that accepts exactly the strings whose length is equal to 3 mod 5 and also equal to 0 mod 4 (hint: 20 states).

That doesn't directly answer your question but I think you've figured out the answer, from your comments. Yes, it's going to need about 28 states so it'll have about 28x27=756 arcs so you'll have to describe it instead of drawing it in full.


$P \neq NP$ and determinism Suppose $P \neq NP$. Does it imply that there exists some superpolynomial time bound, such that any $NP$-complete problem, like SAT, can be used to simulate an arbitrary deterministc Turing Machine working in that time bound?

Rephrasing does $P \neq NP$ imply that there exists some class $D$ of languages solvable by a deterministic Turing Machine, such $P \subsetneq\ D \subseteq NP$ and SAT is $D$-hard?

This post shows that the answer to your initial question is yes (even if P = NP).

On the other hand, I suspect there is no known proof that
if
unambiguousGC(polylog, NC) ⊈ coNP/poly then there is a superpolynomial time-constructible function $T$ and a superlogarithmic space-constructible function $S$ such that

DTIME(T(n)) ∩ DSPACE(S(n)) ⊆ NP/poly.


Is every problem with an output's size that grows polynomialy np? I am wondering if every problem with an output's size that grows polynomialy is $\textsf{NP}$?
My thinking is every $\textsf{NP}$ problems can be solved in polynomial time by a non-deterministic Turing machine. (Wikipedia)
Moreover, consider a non-deterministic algorithm, that takes in input an integer $n$ and an integer $k$. This algorithm randomly outputs  an $n^k$  bits combination. For example $(2,2)$ could output $0101$
Intuitively, this algorithm as a polynomial complexity.
A problem with an output's size that grows polynomialy could be solved by this algorithm.
Therefore, a problem with an output's size that grows polynomialy could be solved by a non-deterministic algorithm in polynomial time.
Therefore, every problem with an output's size that grows polynomialy is $\textsf{NP}$.
I do not know, if my thinking is correct.

No. All problems in $\mathsf{NP}$ are decision problems and, as such, the size of their output is trivially polynomially bounded (the output is just one bit).
Moreover, there are decision problems that are not in $\mathsf{NP}$. Indeed, by time hierarchy theorem $\mathsf{NTIME}(n^k) \subsetneq \mathsf{NTIME}(2^n)$ for every constant $k$.


Asymptotic analysis with factorial and exponential I'm solving a complexity question where I have:

$$ n!/2^n $$

The goal is to find an upper bound for this.

My idea is using the fact that:
$$ n! = O(n^n)$$
$$ n!/2^n = O((n/2)^n) = O(n^n)$$

But is a correct upper bound, and if so is it the tightest upper bound that can be found? I know that n! is asymptotically larger than 2^n, but I'm struggling to do a tighter analysis.

Stirling's approximation states that
$$
n! \sim \sqrt{2\pi n} (n/e)^n.
$$
It follows that
$$
n!/2^n \sim \sqrt{2\pi n}(n/2e)^n = \Theta(\sqrt{n}(n/2e)^n).
$$


Where I can find example how prove red black tree? I need prove that any red-black tree with at least two elements obtained through the insertion algorithm has at least one red node.
For this, I need use Induction.

I don't understand how apply induction. (((

Here is the obvious thing to try:

Prove that if you apply the insertion algorithm twice on an empty tree, then the resulting red-black tree has a red node (this also follows from the invariants of red-black trees).
Prove that if a red-black tree has a red node and you insert an element using the insertion algorithm, then the result red-black tree has a red node.

I don't know if this scheme works, but it's the most immediate way to apply induction.


Resolving this recurrence equation I have this recurrence equation:

$T(n) = T(n/4) + T(3n/4) + \mathcal{O}(n)$

$T(1) = 1$

I know that the result is $\mathcal{O}(n \log n)$ but i don't know how to proceed.

Construct a recursion tree. The sum of the costs per level is less then $c\cdot n$, for $c$ being the constant in the $O(n)$. The tree has roughly $n\log_4 n$ full levels, and the deepest level is $n \log_{4/3} n$. So, summing up over all levels gives $T(n)=O(n\log n)$.


Big O Notation Simplification in the fraction form How should I approach this one a(n) =  $\frac{n^3}{log^{3}(n)}$. As We can tell that $n^3$ grow much faster than $log^{3}(3)$. All of sudden, not sure what to do, found this [post][1], which is also in the fraction form, Do we calculate out $\frac{n^3}{log^{3}(n)}$ or just pick $n^3$. Eventually, the accurate number is not needed, but I somehow understand what it can simplify to and compare with other Big O,  such as \begin{equation} 2^{n^{0.008}} \end{equation}
      Any hint is appreciated

Sorry for my first typo while using LaTex it is  \begin{equation} 2^{n^{0.008}} \end{equation} instead of  $(2^{n})^{0.0008}$

It is indeed confusing if you are expecting some kind of simpler form.

However, ${n^3}/{\log^{3}n}$ is already in the simplest form in term of big-$\Theta$ notation. Consequently, it is also sort of the best form in term of big-$\Omega$ notation or big-$O$ notation. It is certainly true that $n^3/\log^3n = O(n^3)$. However, that kind of big-$O$ bound are usually frowned upon since it is obviously not tight, $n^3/\log^3n = o(n^3)$. In fact, in a similar vein, many time-complexities is described by $\Theta(n\log n)$, $O(n\log n)$ or $\Omega(n\log n)$, where the factor $\log n$ cannot be or is not removed.

The point is that although you can ignore the asymptotically insignificant terms in a sum to arrive at a simpler big-$O$ (or big-$\Theta$, big-$\Omega$) bound, you cannot do away with any unbounded factors without losing significant asymptotical information. For example, it is correct that $n^3+\log^{3}n=O(n^3)$ or $n^3+\log^{3}n=\Omega(n^3)$ or $n^3+\log^{3}n=\Theta(n^3)$, but neither $n^3/\log^{3}n=\Omega(n^3)$ nor $n^3\log^{3}n=O(n^3)$ is correct.

If you want to compare $n^3/\log^3n$ with $(2^{n})^{0.008}$, you can proceed as the following.
$$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=o((2^{0.008})^n), \text{ so } n^3/\log^3n =o((2^{0.008})^n)$$
where the second equality comes from the fact $2^{0.008}>1$ and the fact that any polynomial function grows slower than any increasing exponential function, which is proven in another answer of mine. Please note that I am using the little $o$-notation, which means basically "asymptotically growing slower than".

If you want to compare $n^3/\log^3n$ with $2^{n^{0.008}}$, you can proceed as the following.
$$\text{Since } n^3/\log^3n = O(n^3) \text { and } n^3=2^{3\log_2n} = o\left(2^{(n^{0.008})}\right), \text{ so } n^3/\log^3n =o\left(2^{n^{0.008}}\right)$$
where the second equality comes from the fact $\log_2n=o(n^{0.008})$, which is also proven in that answer of mine since $\log_2n=(\log_2e)\log n$.

You can check the reference question and answers on sorting functions for good advices and more detailed and systematic treatment.


How can a fully encrypted homomorphic program resist copying? Let's say that we have an original homomorphically encrypted program with any possible code inside. What methods can it use to ensure that it is impossible to create an exact copy of it? Are there such ways?

I understand that a person without a key will not see the internal content of a homomorphically encrypted program, I'm interested in whether it is possible to limit the exact copying of this program entirely.

Homomorphic program encryption, assuming you want it fully operational, is not possible. At some point of time actual operations are executed (directly or in obfuscated form).
Encryption of any kind does not prevent copying, because with physical access to hard drive you can make verbatim copy at any moment.
There is also a huge slowdown with program obfuscation (like in Gentry's garbled scheme)/communication that drastically reduces realistic use.


Arithmetical degree of suborders of Q At the moment I am studying several questions about the arithmetical degree of some index-sets in relation to the standard-ordering on $\mathbb{Q}$. The situation is as follows: I fix some enumeration $r_0, r_1, \ldots$ of $\mathbb{Q}$ such that $<$ is decidable. Then I take
$R_e=\{r_n \mid n \in W_e\}$, where $W_e=dom(\varphi_e)$ (the domain of the $e^{th}$ partial recursive function, refering to Kleene's Normal Form Theorem). Now $R_e$ inherits the ordering from $\mathbb{Q}$.
$\textbf{Question 1}$
Define
$$
A
=
\{
e \mid (R_e,<) \cong (\mathbb{Z},<)+(\mathbb{Z},<)
\}.
$$
I try to prove that every $\Sigma_3$-set $m$-reduces to $A$ but I don't have a good idea. Does somebody see something useful I can do?
$\textbf{Question 2}$
I want to show that there exists $d$ such that the sets $\{e \mid (R_e,<) \cong (R_d,<)\}$ and $\{e \mid (R_e,<) \equiv (R_d,<)\}$ are not arithmetical at all. Does somebody has a good idea for this?

Talking about suborders of $\mathbb{Q}$ explicitly makes things a bit harder to think about than is necessary, in my opinion. Really we should be talking about general computable (or rather, c.e.) linear orders - the point is that $\mathbb{Q}$ is "big enough" that we can WLOG construe these as suborders of $\mathbb{Q}$ for concreteness. This does make some definitions snappier, but I think obscures the intuition; instead, I think it's best to think of linear orders being built by progressively "laying down points" (or refraining from doing so of course).
For example, suppose I have a Turing machine $\Psi$ and I want to tell whether $\Psi(0)$ halts. Consider the following process for building a linear order: I start building a descending sequence until I see $\Psi(0)$ halt, at which point I build an ascending sequence starting from the very first point I laid down. For example, if $\Psi(0)$ halts at step $5$, the linear order I build is $$\color{red}{a_4<a_3<a_2<a_1<a_0}\color{green}{<a_5<a_6<a_7<a_8<...,}$$ the red part corresponding to the points added before I saw the computation halt and the green part corresponding to the points added after I saw the computation halt. It should be clear that if $\Psi(0)$ halts then I wind up building something isomorphic to $\mathbb{N}$, whereas if $\Psi(0)$ doesn't halt I build something isomorphic to $\mathbb{N}^*$ (= the "reverse order" of $\mathbb{N}$); thinking along these lines, you should be able to prove that $0'\le_T \{ e: (R_e,<)\cong (\mathbb{N},<)\}$.
Now thinking towards Question $2$, we want to generalize the above idea to higher jumps: e.g. find some "analogue of $\mathbb{N}$" which gets $0''$, and another which reduces $0'''$, and so on ... until we get an idea for one which gets every (finite) iterate of the jump all at once. At this point ordinals become useful for organizing ideas; I recommend thinking about $\omega^2$ in particular, and how we can think about this ordinal as $\omega$-many copies of $\mathbb{N}$ (keeping in mind how a single copy of $\mathbb{N}$ can encode a specific question about the halting problem).

OK, what about Question $1$?
Well, let's think about how hard it is to tell whether a computable linear order $L$ looks like $\mathbb{Z}+\mathbb{Z}$. This amounts to the following:

$L$ is nonempty. This is $\Sigma_1$: "At some stage we lay down a point."

Every point in $L$ has both an immediate successor and an immediate predecessor. This is $\Pi_3$: "For every point $a$ in $L$ there are $b,c\in L$ such that $b<a<c$ and at no stage do we add a point other than $a$ to $(b,c)$."

Note that these two conditions alone ensure that $L$ is a sum of copies of $\mathbb{Z}$. We now need to do the hard bit: ensure that we have exactly two copies of $\mathbb{Z}$ in $L$. This leads to our third and fourth conditions:

There are two points which are infinitely far from each other. This is $\Sigma_3$: "There are $a<b$ such that at every stage there is some later stage at which we add a new point to $(a,b)$."

There are no three points which are each infinitely far from each other. This is $\Pi_3$: "For every $a<b<c$ we either stop adding points to $(a,b)$ at some stage or we stop adding points to $(b,c)$ at some stage."

Once appropriately formalized, this shows that $A$ is $\Pi_3\wedge\Sigma_3$; it's now natural to hope that every $\Pi_3\wedge\Sigma_3$ set $m$-reduces to $A$, and Question $1$ is a step towards this. If we want to reduce an arbitrary $\Sigma_3$ set to $A$ we probably want to focus on the "$\Sigma_3$-part" of the characterization of $A$; in the above, this was the "There are two points infinitely far apart from each other" bit.
Here's a construction which starts us off in the right direction:

Suppose I have a $\Sigma_3$ sentence $\varphi\equiv\exists x\forall y\exists z(\theta(x,y,z))$ with $\theta\in\Delta_0$; I want to "computably build" a linear order which has a pair of points infinitely far from each other iff $\varphi$ is true. To do this, I work in "blocks:"

For each $i\in\mathbb{N}$ I have a block $B_i$. Every point in $B_i$ will be above every point in each $B_j$ with $j<i$ and below every point in $B_k$ with $k>i$, and each $B_i$ starts off with a single point.

I add points to $B_i$ in such a way that $B_i$ is isomorphic to $\mathbb{N}$ iff $\forall y\exists z(\theta(i,y,z))$ and is finite otherwise. For example, add an element to the "end" of $B_i$ each time I see $\{y: \forall y'<y\exists z(\theta(i,y',z))\}$ gain an element.

If $\varphi$ is true then at least one $B_i$ is infinite, and this forces a pair of points to be infinitely far apart (consider a point in $B_i$ and a point in $B_{i+1}$). Conversely, if $\varphi$ is false then each $B_i$ is finite and we wind up building a copy of $\mathbb{N}$.

Now (even ignoring the formalization) there are two issues with this, as far as Question $1$ goes. First, there's the problem that the "blocks" look like $\mathbb{N}$ instead of $\mathbb{Z}$; this is easily fixed, though. More serious is the issue that if $\varphi$ is true we might wind up with too many infinite blocks; fixing this will require some thought (and ultimately some injury).


Is set cover still NP-complete if you have a given k? Set cover is NP-complete given an arbitrary set $U$, a set $S$ of subsets of $U$, and an integer $k$. However, what if $k$ is always a constant 3? Is that problem still NP-complete?

No.

Like many $NP$-complete problems, fixing the solution size gives a polynomial-time algorithm. In this case, we're looking for a group of at most $(k=)3$ sets $s_{1}$, $s_{2}$ and $s_{3}$  from $S$ such that $s_{1}\cup s_{2} \cup s_{3} = U$, so we can simply try every set of 3, which gives a $O(|S|^{3})$ algorithm because there's only $\binom{|S|}{3}$ groups of three sets taken from $S$, and in general, for every fixed $k$, an $O(|S|^{k})$ algorithm.

This is true for many other problems, like Dominating Set, Vertex Cover, Independent Set, $k$-Clique etc. etc. These all have $O(n^{k})$ brute force algorithms. Expressed in Parameterized Complexity terms, they're all in the class $XP$ (in fact, for all of these, they're in $W[P]$) when the parameter is the solution size1.

Note the contrast with problems like k-Coloring, which is $NP$-complete for every fixed $k \geq 3$. The best algorithms for problems like these have running times more like $O(k^{n})$ - the relationship between $k$ and $n$ is reversed to what we had before. Again in Parameterized Complexity terminology, such things are $para$-$NP$-complete, and don't have (non-uniform $XP$ algorithms unless $P = NP$.

Footnotes

$XP$ is the class of all parameterized problems that have a polynomial time algorithm for every fixed value of the parameter, also called "slicewise polynomial". $W[P]$ is the class of problems that have a nondeterministic algorithm that runs in $f(k)n^{O(1)}$ time with at most $h(k)\log n$ nondeterministic steps for some $h$, where $k$ is the parameter - we can remove the nondeterminism and get a $O(n^{O(h(k))})$ algorithm for some function $g$, through the same approach of trying all possible solution certificates.


Minimize longest continuous streak of $1$s after flipping $m$ $-1$s to $1$s Given an array a of length n of $-1$s and $1$s, and another input $m$, I was supposed to minimize the longest continuous streak of $1$s or $-1$s after flipping $m$ $-1$s to $1$s or vice versa.

I know how to maximize it but can't figure out how to minimize it. I maximize the number of $1's$ by sliding window method.
Take a window ($wleft$ , $wright$).It covers given array from index $wleft$ to $wright$.
I represent $-1$ with $0$ for ease.Suppose number of zeros in window in $wzeros$.

Algorithm :

while wright < length of array {

     wzeros <= m: increment wright

     wzeros>m: increment wleft

  // Update the max window size during this whole process.

        int temp = wright-wleft;
        if(temp > mx_length){
          mx_length = temp;
          solution_window = wleft;
        }
    }

This code maximizes the number of consecutive $1$s whereas I want to minimize the number of consecutive $1$s and $-1($or $0)$s. How do I modify the algorithm/code to achieve so ?

You can use dynamic programming. It is very likely that much faster algorithms exist.

Given a string $w$ of length $n$, for $0 \leq i,j \leq n$ and $0 \leq k \leq m$ you compute the minimal maximum 1-run in $w_1,\ldots,w_i$ given that $k$ many -1s were changed to 1s, and given that $w_1,\ldots,w_i$ ends in a 1-run of length $j$.

This gives an $O(n^2m) = O(n^3)$ algorithm.


Transport Triggered CPU Architecture MOV and Turing Completeness Reading up on TTA CPU designs and the wikipedia article states that

  Some TTA implementations support conditional execution.

The trick to make an TTA ISA Turing-complete with an unconditional MOV instruction escapes me. Can anyone explain how that would work?
(or share some resources where it is explained)

For a CPU designed to use a TTA (Transport Triggered Architecture), one way to implement conditional branch could use a couple of addresses for these purposes:

BRANCH_ADDRESS: stores the location to branch to
BRANCH_ZERO: Sets PC to BRANCH_ADDRESS when value written is 0. Otherwise does nothing.

This could be used to implement a 'branch-if-zero'. You could also add additional addresses that implement other branch modes, including those ithat hook into flags/state of other components hooked up to the TTA CPU, such as an ALU.


Non-regular language whose prefix language is regular I understand that prefix of a regular language is regular, but I am unable to get my head around this:

  Give an example of a non-regular language $A ⊆ \{0, 1\}^*$ for which $\operatorname{Prefix}(A)$ is regular.

One approach to think of examples or counterexamples is to looking for the simplest examples or starting from some known situations.

What are some typical examples of non-regular languages? A typical example is the language of palindromes. Its prefix language contains every word $w$, since $ww^R$ is a palindrome. That is, its prefix language is a regular language.

The question has been answered.

However, as pointed out by Bader Abu Radi, the above example breaks down with unary alphabet, when the language of palindromes is the set of all words.

What are some typical examples of non-regular languages over unary alphabet, say $\{a\}$?

Let us try $\{a^{n^2}\mid n\ge0\}$ or $\{a^{2^n}\mid n\ge0\}$ or just any non-regular language you can think of. Since it is non-regular, its words can be arbitrarily long. That means its prefix language contains all words, $\epsilon, a, a^2, \cdots$. That is, its prefix language is regular.

Readers may enjoy the following two exercises.

Exercise 1 (easy). Show that an example over unary alphabet can be considered as an example over any larger alphabet.

Exercise 2. A language is prefix-closed if it is own prefix language. Give an example of non-regular prefix-closed language that does not contain a regular infinite language.


delete node from linked list (lang w/GC) -should deleted item 'next' be set to null Regarding: delete a node from a linked list algorithm,in procedural languages with garbage-collection.
Should there be a step in the algorithm, of setting the removed-node-next-pointer  to null ?

(Several high-school-CS-teachers in my area teach YES, while others teach NO)

What is the right approach?

/thanks ran

If you mean the next pointer of the node that was deleted, as far as I know it is normally not necessary to set the pointer to null.  Once the node is deleted, if the code is not buggy, then the code should not access the node after it is deleted, so the value of its next pointer should be irrelevant.  Sometimes some people do set the pointer to null, as a form of defensive programming (just in case the program is buggy and accesses that node after it was deleted).

I suggest that a useful exercise would be to ask your teachers why they teach yes or no.  Hearing their reasoning might be instructive and interesting!


Recursive complexity with change of variable I face a problem with computing a complexity.
I have this equality : $P(u) = (\sqrt{u}+1)P(\sqrt{u}) + \theta(\sqrt{u})$

And I want to prove that $P(u) = O(u)$

This is how I process :

I put $m = \lg\lg u \implies P(u) = P(2^{2^{m}}) = (2^{2^{m-1}}+1)P(2^{2^{m-1}}) + \theta(2^{2^{m-1}})$

Now, I consider $S(m)$ that is : $S(m) = P(2^{2^{m}}) = mS(m-1) + \theta(m-1)$

And here I have a problem. I obtain a factorial complexity and I don't know how to integrate $\lg$ to prove the equality $P(u) = O(u)$

Some advice ?


Master theorem: what to do with constant in parenthesis? In analysis of algorithms, we sometimes use the (unsimplified) Master Theorem for recurrence relations.
What should be done in the case that there is a constant factor in the numerator following T?
$$
T(n) = 2T\left(\frac{5n}{8}\right) + 1
$$
Does b simply equal $\frac{5}{8}$? This seems a contradiction to the Theorem.

Usually the general form of the recurrences solved by the Master theorem is stated as:
$$
T(n) = aT\left(\frac{n}{b}\right) + f(n).
$$
In your recurrence you have $a=2$, $b=\frac{8}{5}$, and $f(n)=1$.


Substitution by structural recursion Following the article's notation, I write $\mathcal{F}$ for the
category of presheaves on a (suitable) category $\mathbb{F}$, $TV$ for the
presheaf of terms, $\delta$ for the context extension, and
$\bullet$ for the product of the $\mathcal{F}$-monoid.

In Abstract Syntax and Variable Binding [Fiore, Plotkin, Turi], the
authors set out to define substitution by structural recursion
(Section 3). I was expecting to see substitution expressed as an
initial algebra of some sort.

Instead, from what I understand, the authors:

 Construct the substitution $\sigma : \delta(TV) \times TV \to TV$ by some universal construction ("Definition of substitution by structural recursion")
 Show that it forms a substitution algebra (Theorem 3.2)
 Show that the categories of substitution algebras and clones are equivalent (Theorem 3.3)
 Show that the categories of clones and monoids in $\mathcal{F}$ are equivalent (Proposition 3.4)
 Show that subtitution is the multiplication of such a monoid (Proposition 3.5)
 Conclude that $\sigma$, the substitution, is defined by structural recursion (Corollary 3.6).

I'm failing to appreciate their motive in moving from substitution
algebras to clones to monoids. Is that a natural thing to do for a
mathematician?

In particular, why not stay focused on substitution algebras and, I
guess, present substitution as the initial one?

Conversely, they claim that Corollary 3.6 gives a definition of
substitution by structural recursion: how is that? It is just said
that "$\sigma$ is the unique homomorphic extension of $V \bullet TV
\cong TV$": how did they derive their example (substitution for the
lambda calculus, very end of Section 3) from this statement?

A more tutorial-paced presentation of the same/related material is available in:
Roy L. Crole: Basic Category Theory for Models of Syntax. Generic Programming 2003: 133-177. This should help.


Purpose of randomization/derandomization in basic randomized algorithm for MAX SAT In Sections 5.1 of The Design of Approximation Algorithms by Williamson and Shmoys, they describe a basic randomized algorithm for MAX SAT and how to derandomize it. The algorithm is just to assign each variable 1 (true) with probability 1/2 and 0 (false) with probability 1/2. In other words, sample uniformly at random from the space of all solutions. They show that this is a 1/2-approximation.
Then in Section 5.2, they describe how to derandomize it using the method of conditional expectations. (I won't describe the process here because it is not very complex and widely known I'm assuming.)
My question is, why bother derandomizing this way? Or even, why bother making the algorithm random in the first place?
It seems to me that an equally good algorithm would be the one-liner which deterministically sets all variables to 1. Given some MAX SAT instance as input, it seems to me that you would also expect this to (i.e., "in expectation it would") satisfy half of the clauses. To me, the analysis of the random algorithm really seems to say that any fixed guess is "good." (Rather than showing that our random algorithm is inherently good.) So why go through the process of randomizing and derandomizing in the first place?
Thanks in advance!

The difference is that the randomized algorithm guarantees an expected 1/2-approximation on any input. By contrast, it is easy for an adversary to construct an input (i.e. an instance of MAX-SAT) for which the deterministic "set all variables to true" algorithm satisifes zero clauses.
Remember that the sample space for a randomized algorithm is over a set of auxiliary random bits. There is no probability distribution assumed over the inputs. The typical goal of randomized algorithm design is for every input to be handled well in expectation. (Analyzing algorithm behavior over an assumed input distribution is called average-case analysis instead.)
What are auxiliary random bits?
Suppose we have a randomized Turing machine $M_1$ that runs on instances of length $n$ for no more than $T(n)$ time, during which it makes no more than $R(n) \le T(n)$ random decisions. We can turn this machine into a deterministic Turing machine $M_2$ that has two input tapes: the usual tape that contains the input string $x$ of length $n$, and a tape that contains a string $r$ of length $R(n)$. The string $r$ is our string of auxiliary random bits; it determines which "random" decisions the Turing machine is to make. When we say that the randomized Turing machine run $M_1(x)$ accepts with probability $p$, this is equivalent to saying that the set
$$A(x) = \left\{r\ |\ r \in \{0, 1\}^{R(|x|)}, M_2(x, r)\text{ accepts}\right\}$$
of $r$ strings that make $M_2(x, r)$ accept constitutes a fraction $p = |A(x)| / 2^{|x|}$ of the set of all $r$ strings.
You might recognize what is going on here if you've seen the analogous construction for nondeterministic Turing machines. We can think of an NP machine as a nondeterministic machine that branches into exponentially many copies of itself. But we can also think of it as a deterministic verifier machine that requires both an input and a "proof" string, with the acceptance criteria that an input string is in the language if any proof string makes the machine accept.
It is often easier to think about this down-to-Earth concept of deterministic verifier machines and which subset of proof strings makes the machine accept on a given input, rather than thinking about very abstract ideas like exponentially branching machines and possible worlds. And it makes it easier to define complexity classes such as co-NP, PP, BPP, ⊕P, etc., all of which are essentially "NP with a different acceptance rule." For example:

NP is the set of languages $L$ for which there exists a polynomial-time verifier machine $M_2$ such that $x \in L$ if and only if there exists an $r$ string such that $M_2(x, r)$ accepts (where the length of the $r$ string is bounded by a polynomial $R(|x|)$).
BPP is the set of languages $L$ for which there exists a polynomial-time verifier machine $M_2(x, r)$ such that $x \in L$ implies that $M_2(x, r)$ accepts for at least ⅔ of $r$ strings and $x \notin L$ implies that $M_2(x, r)$ accepts for at most ⅓ of $r$ strings (where the length of the $r$ strings is bounded by a polynomial $R(|x|)$).

Note: It mostly doesn't matter whether we require the $r$ strings to have length exactly $R(n)$ or at most $R(n)$, since allowing shorter strings only increases the number of possible strings by a constant factor.


Is it possible to mapping reduce either of these languages to the other? I have the following two languages, which are languages of TM descriptions:

$$INFINITE = \{ \langle M \rangle | \mbox{M is a TM and L(M) is infinite} \}$$

$$A_{ALL} = \{ \langle M \rangle | \mbox{M is a TM and } L(M) = \Sigma^* \}$$

Neither of these languages are decidable, recognizable, or co-recognizable.

However, I believe they're in $\Pi_2$, since a TM belongs to $INFINITE$ iff for every $x$, there is a string $y$ and computation history $H$ where $y$ has length greater than $x$ and $H$ is a history that shows that $M$ accepts $y$.
And a TM belongs to $A_{ALL}$ iff for every $w$, there is a computation history $H$ that shows that $M$ accepts $w$. (I'm not sure if this reasoning is correct or not, though).

I have been wondering for a while whether either of these languages are mapping reducible to one another. I don't see a quick way to prove that the languages are not reducible to one another, but I similarly can't see a simple reduction in either direction.

Are either of these languages reducible to the other? If so, how?

I'll assume that by $L(M)$ you mean the set of strings on which $M$ halts.

Hints:

INFINITE to AALL: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on some $y \geq x$. (Arrange the inputs in some arbitrary way of your choice.)
AALL to INFINITE: Given a Turing machine $M$, construct a Turing machine $M'$ that on input $x$ halts if and only if $M$ halts on all $y \leq x$.

Both directions require use of dovetailing.


How to find whether a grammar's language is finite or infinite? I have this context-free grammar and I want to find out whether its language is finite or infinite.

S -> XY|bb  Step 1
X -> XY|SS  Step 2
Y -> XY|SS  Step 3

So I would do

S -> XY            From step 1
S -> YYY           From step 2
S -> SSYY          From step 3
S -> SSSSY         From step 3
S -> SSSSSS        From step 3
S -> bbSSSSS       From step 1
S -> bbbbSSS       From step 1
S -> bbbbbbSSS     From step 1
S -> bbbbbbbbSS    From step 1
S -> bbbbbbbbbbS   From step 1
S -> bbbbbbbbbbbb  From step 1

bbbbbbbbbbbb

So I know how to generate words like this but how to find out whether the language is finite or infinite?

A language is infinite if it can generate infinitely many words. In order to prove that a language generated by a grammar is infinite, you need come up with some infinite list of words generated by the grammar. Proving that the language is finite is slightly more messy—you need to make a list of all possible derivations, and show that all of the terminate.

In your case, you have the derivation $S\to^*SSSS$, which suggests that the language is infinite. Can you come up with an infinite list of words generated by this grammar?


what is the difference between "language" and "certificate" in complexity theory? Seems like they both are set of strings for which the problem returns "yes" in decision problems.

P class is consists of problems so we can only say a problem is in P. But we sometimes say that a language L is in P. why?

A (formal) language $L$ is a set of words over some finite alphabet. It can be an infinite set. Generally we're interested in the problem of deciding whether a particular word is in the language or not. For example $L$ can be the set of all Turing machines (encoded as binary strings for example) that halt after at most 100 steps when started with an empty tape, or $L$ can be the set of English words that don't contain the letter 'e'.

A certificate on the other hand is one particular string. When solving the decision problem I talked about above, namely checking whether some word $w$ is in some language $L$, sometimes the problem becomes much simpler if you have some additional information $c_w$. This is often called a certificate for $w \in L$ respectively $w\not \in L$.

For example if $L$ is the set of all graphs that can be colored with at most 3-colors, deciding whether a particular graph $G$ is in this set is NP-complete. But if I already give you a coloring $c_G$ it is very easy to check that it's a valid coloring. The coloring is a certificate for $G\in L$. A coloring has the nice property that it's short, just a couple of bits for each node of the graph. Note that in this case it's not easy to give a (short) certificate for some $G'$ that is not colorable. A very long certificate in this case would be an enumeration of all exponentially many possible 3-colorings of $G'$. Checking that each is not valid is again easy, and since the certificate $c_w$ is so long, the running time of the algorithm with input $G', c_w$ is polynomial as a function of input size.


Turing recognizable -decidable languages- I was wondering how to prove that $C$ (which is a language) is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$.
I do not know how to prove this kind of questions, is there any help to help me solve this problem or any problem as this kind.

There are two directions here. One is trivial: if $C$ is indeed of the above form, then it is clearly recognizable: given $x$ just run $D$ on all possible $y$'s in a dovetailing manner (see, e.g., here, or search in this site).

The other direction is less obvious, but also not too difficult: Assume that $C$ is recognizable. Then, there exists a machine that halts and accepts any $x\in C$. Thus, you can write the sequence of configurations of $M$ on input $x$, and this sequence is finite! This sequence will be the $y$ that exists if $x$ is in the language. You should be able to complete the details from here.


quicksort - Why is $\log_4 n$ used as an approximation instead of $\log_2 n$? Below is an excerpt from Khan Academy's Quick Sort Analysis page.

In the average case of quicksort they assume that each time the partition function breaks the input array into the ratio 1:3 each time.

So why is it easier to assume $\log_4 n$ levels when the $n$ elements are being partitioned ? Why not assume it to be $\log_2 n$ levels ?

Wouldn't $\log_4 n$ and $\log_2 n$ mean the same thing here ?

No, $\log_4 n$ is not the same as $\log_2 n$. $\log_4$ is exactly $\frac{\log_2 n}{2}$. At the end of the complexity computation you can obviously say that $O(\log_4 n) = O(\log_2 n)$. But at this point they aren't computing the complexity (yet). They are doing "exact" math. If you have an array with $n$ elements and you always divide it by $4$, it will take exactly $\lceil\log_4 n \rceil$ iterations until you reach the size $1$, and not $\lceil \log_2 n \rceil$.

One more thing. They don't proof, that the average runtime is $\Theta(n \lg n)$. Because the array will obviously not always split with a ratio of 1:3. They only give you some intuition, why the complexity makes sence. Like they mention in the article:

  Showing that the average-case running time is also $\Theta(n \lg n)$
  takes some pretty involved mathematics, and so we won't
  go there.


Is there a name for this relation on CFGs? I'm looking for the name (or a name if there isn't one already) of this relation between $G_1=\left<\Sigma_1,\mathcal{N}_1,\mathcal{R}_1,S_1\right>$ and $G_2=\left<\Sigma_2,\mathcal{N}_2,\mathcal{R}_2,S_2\right>$:
$$\exists f_\Sigma\in\Sigma_1\times\Sigma_2,f_\mathcal{N}\in\mathcal{N_1}\times\mathcal{N}_2 \text{ surjective functions s.t. }\\ \mathcal{R}_2=\left\{f_\mathcal{N}(N)\rightarrow f(\alpha)\mid N\rightarrow\alpha\in R_1\right\}\text{ and } S_2=f_\mathcal{N}(S_1) $$
where $f$ is the extension of $f_\Sigma$ and $f_\mathcal{N}$ to words ($f\in(\Sigma_1\cup\mathcal{N}_1)^*\times(\Sigma_2\cup\mathcal{N}_2)^*$).

In other words, you can map $G_1$ to $G_2$ (but not necessarily $G_2$ to $G_1$).

If the mapping function were bijective, this would be an isomorphism, but they're not.

What about if only $f_\mathcal{N}$ is  surjective, i.e. $f_\Sigma$ is bijective, or even the identity function?

This is a kind of (surjective) homomorphism,  but the traditional definition is defined only over terminal symbols, not nonterminals.

Your definition would merge unrelated nonterminals from the first grammar with each other in the second grammar, thereby allowing (the image of) unrelated parts of the grammar to get mixed up with each other. This probably does not have nice properties, at least compared to the traditional definition of homomorphism.

That said, I can imagine that it is useful for some kinds of modelling, of AOP, of dynamic binding, of extensible grammars. I'd be interested in knowing what your application is.


Why are CFLs not closed under intersection? I'm struggling with understanding how context free languages can be closed under union but are not closed under intersection.  I was wondering if there was a simple proof or example demonstrating that CFLs are not closed under intersection.

Let us assume $2$ CFLs $L_1$ and $L_2$ and their corresponding grammars be $S_1$ and $S_2$ respectively.
It is very straightforward to see that the union of the two, represented by the new grammar as
$$S \to S_1 \mid S_2$$
is also a CFG, as the rule of being context-free is still not violated. Context-free grammar

But to prove that they are not closed under intersection, I'll provide an example.
Let $L_1$ and $L_2$ respectively be:
$$L_1 = \{ a^nb^nc^m \mid n, m \ge 0 \}$$
$$L_2 = \{ a^mb^nc^n \mid n, m \ge 0 \}.$$
It is not hard to see that $L_1 \cap L_2$ is
$$L = \{ a^nb^nc^n \mid n, m \ge 0 \},$$
which is not CFL (No PDA cannot accept that language).
Hope this explains.


how does the program change the clock speed of the processor? bios is a program that checks all devices and starts the bootloader.
but how does the CPU sync with the motherboard if the CPU clock settings are stored in the BIOS?

Does the BIOS have CPU clock frequency settings?
how does the BIOS adjust the clock speed of the processor if it's just a program?
does the BIOS synchronize the internal clock of the processor with the external clock on the motherboard?
does the processor first start on the external clock, and after synchronization - on its own internal clock frequency?
does the change in the CPU clock speed mean its own internal clock due to heating problems (throttling)?
How can the operating system change the clock speed of the processor? does it really change the cpu settings or put some limits on the task scheduler? (Are Linux and Windows the same with this?)

I am completely confused about how the processor actually syncs at startup and sets the clock speed?
please explain me.
answer as processor clock = base clock * multiplier. I do not understand

This is different for any processor. You should consider going to the Intel, ARM and AMD websites and looking for the right manuals. That’s what I would do if I had to answer the question, and that’s what I recommend you should do.


Given a binary min-heap, find the $k$-th element I'm given a binary min-heap (implemented with an array) and need to come up with a (simple) efficient (no more than $k$ comparisons) to find the $k$-th minimal element.
My attempt was as follows:

check who is the smallest among the root children
scan the corresponding sub-heap maintaining a counter counting how many nodes are smaller than the larger child of the root (but larger than the smaller child). If the counter reaches $k-1$ return the value of the current node. other-wise after the scan is finished, call this method recursively on the larger root child to find the ($k$ $-$ couter_value + 1)-th minimal element of the larger child.

I just can't put this together formally and not sure this can be implemented with no more than $k$ comparisons.
Thanks for any help.

The minimum element will the root. So in constant time you can find the minimum element. Delete the minimum element from the root. Now min-heapify (make it minheap) the resultant tree.
The second minimum element will be the root again. Repeat the procedure mentioned above.
By this procedure, you will find $k$-th minimum element in time $O(k \log n)$ where $n$ is the number of elements in the given min-heap.


Proving NP is a subset of the union of exponential DTIME I need to prove that $\mathsf{NP}$ is a subset of the union of $\mathsf{DTIME}(2^{n^c})$ for all $c > 1$.

Let $L$ be a language/decision problem in $\mathsf{NP}$. Then $L$ can be decided given a polynomial-size certificate in polynomial time with a turing machine $M$. So then we enumerate all possible certificates of polynomial size. There are $2^l$ possible certificates for a certificate of length $l$. For a certificate of length up to $n^c$, there are $\sum_{l=0}^{n^c} 2^l = 2^{n^c + 1} - 1$ many certificates. Each certificate can be decided in polynomial time, so we get that each problem in $\mathsf{NP}$ can be done in $\mathsf{DTIME}(2^{n^c}n^c)$. What am I doing wrong?

You are on the right track. To finish the proof you need to show that

$\qquad \displaystyle \mathsf{DTIME}(2^{n^k} n^k) \subseteq \mathsf{DTIME}(2^{n^c})$

for some constant $c$.


NP-Complete is not closed under kleene star Consider $\Sigma=\{0,1\}$. Suppose that $L \subset \Sigma^*$ is $NP-$Complete. How can I prove that $L' = L \cup \{0,1\}$ is $NP-$Complete?

$L$ is $\mathrm{NP}$-complete, so, for any $X\in\mathrm{NP}$, there is a many-one reduction $f_X$ from $X$ to $L$.  Just modify $f_X$ so that it's a reduction to $L'$ instead. Note that $f_X$ already does the right thing unless you have some $w$ such that $f_X(w)\in\{0,1\}$.

Note that the same technique shows that $L\cup S$ is still $\mathrm{NP}$-complete for any finite $S\subseteq \Sigma^*$.


Transition and configuration of Turing machine In my lecture I have examples about 0 -> R (which means if it's 0, move Right) or 0 -> x, R (replace 0 with x and move Right) but I don't quite understand about the 0, 0 -> R expression. What is the configuration of Turing machine btw

Notations vary, but "$0, 1 \rightarrow R$" can be short for "$0 \rightarrow R$ and $1 \rightarrow R$."

A configuration is a way of writing the current state of the TM, the symbols on the tape and the current position of the tape. Here's a common way to write a configuration: if the state is $q_0$, the tape has $101$, and the head is pointing at $0$, write $1q_001$.


Are Boolean functions Turing complete A Boolean function is a function $f:\{0,1\}^n\rightarrow\{0,1\}$.

The boolean basis $(\vee,\wedge)$ is known to be Turing complete as it allows any sequence $s\in\{0,1\}$ to be flipped or to be left unchanged. The same can be said of $\mathrm{XOR}$ gates.

In this sense we can start with an initial machine configuration $\textbf{b}=(b_1,\ldots,b_n)$ such that $b_i\in\{0,1\}$ and $\mathrm{XOR}$ it with successive values $\textbf{v}_i$:

$
\textbf{b}\oplus\textbf{v}_1\oplus\textbf{v}_2\oplus\textbf{v}_3\ldots
$

Each state $\textbf{v}_i$ would represent a permutation of some element in $\textbf{b}$. This process effectively mimics a Turing machine and assumes that there is some generator for the values $\textbf{v}_i$.

So can we say that Boolean functions Turing complete?

Informally, a (programming) language is Turing complete if every computable function has a representation. A general computable function accepts an input of arbitrary size. Boolean functions, on the other hand, accept an input of a fixed size. Hence Boolean functions don't even qualify as potentially Turing-complete.

The relevant notion of completeness here is a complete basis of connectives. A set of connectives ($k$-ary functions on Boolean values for arbitrary $k$) is complete if every Boolean function on $x_1,\ldots,x_n$ (for arbitrary $n \geq 1$) can be represented using the connectives. The following sets are complete: the de Morgan basis $\{\lnot,\lor,\land\}$ and the basis $\{\lnot,\Rightarrow\}$. In contrast, $\{\lnot,\oplus\}$ is not complete: it can only express linear functions.


Should we eliminate left recursion before using NPDA to simulate CFG? I read the book "Introduction to the Theory of. Computation, Third Edition by Michael Sipser".
It says:

If a language is context free, then some pushdown automaton recognizes it.
Let A be a CFL. From the definition we know that A has a CFG,
G, generating it. We show how to convert G into an equivalent PDA, which we
call P.

But what if G has left recursion?
Does the NPDA construction in this book can halt when it simulate a CFG which has left recursion?
What's the different between NPDA and Recursive-Descent Parsing (full backtracking) in Compilers Principles, Techniques, & Tools ?
Thanks.

As stated in the second paragraph following the one you quote, the PDA being constructed is non-deterministic, which greatly simplifies the construction.

A non-deterministic machine is allowed to have points at which more than one action is possible, without any procedure for determining which one is correct. It is only necessary to prove that one possible action leads to correct termination.

Such machines are easy to construct in formal theory but building them in the real world is trickier. A back-tracking parser must explore alternatives in some order; if it chooses an alternative which fails to terminate, then it will never get around to trying another possibility.

In contrast, the non-deterministic machine terminates acts as if it took all possible branches at the same time. If any branch terminates in an accepting state, the machine can can terminate and accept the input. This can be simulated by making copies of the machine at every branch, and simulating the progress of all currently active copies by repeatedly advancing each one by one step. (More copies might be made at each step of each copy, so it can get a little closer unwieldy.)

Consequently, it does not matter to the PDA if there is left-recursion in the grammar. To be sure, the left-recursion means that some of the possible execution paths will never terminate, but as long as there is a path which terminates, the PDA will choose it.

There is a subtle but important point which I left out of the first version of this answer, which is that the definition of the language recognised by the PDA is the set of inputs for which the PDA terminates in an accepting state. Nothing guarantees that the PDA will eventually terminate on other inputs, and it is quite possible that the PDA will never halt if it is given a input which is not in the language it recognises. (This is another reason why non-deterministic PDAs aren't much use in practical parsers.)

This should not be surprising. If the machine were guaranteed to halt, then there would exist a machine which recognised the complement of the language. But if that were the case, the complement of every context-free language would be context-free, and we know that not to be true.


Can a Non-Deterministic Pushdown Automaton recognize $ \# a^nb^{2^n} \# $ which a TM can? $ \# a^nb^{2^n} \# $

such that

• The alphabet of the machine is {, a, b, x}.

• The symbol x will never appear on the input a.

• The contents of the tape at completion may be anything.

• The head begins on the lefthand #.

• n ≥ 0.

I know that a Turing machine could recognize this language. But can a NPDA recognize this language too? I am thinking it can but I do not know how to start proving how/why?

Actually this language is not a CFL.

And here is a proof:

Let's take string $w: a^mb^{2^m}$ where $m$ is constant guaranteed by pumping lemma for CFLs.

Then $a^{m+k_1}b^{2^m+k_2} \in L$ where $1\le k_1,k_2<m$

(cases invloving either $k_1 = 0$ or $k_2=0$ are easier.)

Now, that suggests that,

$2^{m+k_1} = 2^m + k_2$ (by defination of $L$)

$\therefore 2^m2^{k_1} = 2^m + k_2$   ....................................(1)

now, $k_1 \ge 1\implies 2^m2^{k_1} \ge 2^m + 2^m > 2^m + k_2.$

(because we have $k_1 \ge 1$ this means left side of equation $1$ will always have value $\ge 2.2^m$ but right side of equation can have maximum value of $2^m + m - 1$)

Hence this language can't be CFL.