Are runtime bounds decidable for anything nontrivial? Problem  Given a Turing machine $M$ which has known runtime ${O}(g(n))$ with respect to input length $n$, is the runtime of $M \in {O}(f(n))$?

Is the above problem decidable for some nontrivial pairs of $g$ and $f$?A solution is trivial if $g(n) \in O(f(n))$.

This is related to the problem Are runtime bounds in P decidable? (answer: no). One can derive from Viola's answer that if $f(n)\not \in o(n)$ and $f(n)\not \in O(g(n))$ then the problem is undecidable.

The requirement that $f(n)\not \in o(n)$ is because the $M'$ in Viola's proof need $O(n)$ time to find its input size. Thus Viola's proof could not work when $f(n)=1$.

It would be interesting if we can decide on the run time of sublinear time algorithms. A special case is when we have arbitrary $g(n)$ and $f(n)=1$.

Here are a few remarks which could be relevant:

Kobayashi proved that a TM running in time $o(n\log n)$ accepts a regular language (and so runs in time $O(n)$); recently this has been extended to non-deterministic TMs (Tadaki, Yamakami and Lin).
Machines running in time $o(n)$ actually run in constant time (consider any $n$ for which the running time is less than $n$; adding characters to the end doesn't affect the TM).


Buying ingredients for a cake from many different stores and need to minimise the number of stores - algorithm name? So let's say I'm baking a cake and it has a few ingredients (including multiples):

ingredients = {sugar, sugar, baking powder, chocolate, flour, egg, egg}

I can go to a bunch of different stores to buy the ingredients. Each store has a different collection of ingredients to offer:

store_1 = {sugar, vanilla extract, olive oil, chocolate}
store_2 = {chocolate, chocolate, flour, egg}
store_3 = {flour, baking powder, sugar, sugar, sugar, egg}

Problem: I want to buy all the ingredients for the cake from the minimum number of stores

I'm sure this is a common problem with existing algorithms, but I can't seem to find anything besides the bin packing problem. It is a similar problem but not quite the same.

Any ideas would be appreciated.

If it was not for multiples the problem would be Set Cover.
With multiples, a natural name would be Multiset Cover though I cannot say I have encountered this name before.

Obviously, Multiset Cover has Set Cover as a special case.
Hence (the decision variant of) it is NP-hard and you will not find a truly efficient algorithm.
On the other hand, Multiset Cover can be seen as a special case of integer linear programming in the same way that cover problems generally can.


Algorithm to compute power function on interval [0, 1] I am looking for an efficient algorithm to compute $$f(x) = x^a, x\in[0, 1] \land a\,\text{constant}$$

If it helps, $a$ is either $2.2$, or $1/2.2$. Knowing valid values for $x$ and $a$ could make it possible to take some shortcuts a general pow function cannot make.

General tailor series expansion has some serious convergence problems when $x \to 0^+$, at least when $a < 1$.

The algorithm must be faster than pow
The maximum error on the specified interval must be less than or equal to $10^{-4}$.

The Weierstrass Approximation Theorem states that any continuous function can be approximated on a bounded interval $[a, b]$ as closely as desired by a polynomial. In practice, instead of using Taylor series expansions, one uses polynomial minimax approximations $p(x)$ which approximate the function on the chosen interval with the minimal maximum error (thus the name).
When one looks at the graph of the error function $f(x) - p(x)$ one observes that it oscillates such that all extrema are of equal magnitude and neighboring extrema have opposite sign (equi-oscillation property), and that there are a total of $n+2$ extrema for a polynomial of degree $n$. This behavior of the error function can be used to construct the minimax polynomial, as also noted in gnasher729's answer.
The standard algorithm used to do this is called the Remez algorithm, named after the Russian mathematician who published it in 1927. This functionality can be found in ready-to-use form in widely used tools such as Maple and Mathematica, as well as the software tool Sollya, which provides an fpminimax command to generate minimax polynomial approximations. One can also create one's own implementation of the Remez algorithm, and I have used such code for this answer.
While the minimax polynomial is well defined mathematically, when the coefficients need to be stored in a finite-precision floating-point format and the polynomial evaluated is evaluated in finite-precision floating-point arithmetic, the error
function $(f(x) - p(x)$ becomes deformed and no longer satisfies the equi-oscillation criterion. That means we wind up with a polynomial that is merely close to the true minimax polynomial. Many tools do not adjust for this effect at all, delivering coefficients based on high-precision internal computations. Sollya takes the finite-precision storage of the coefficients into consideration, and thus can often deliver superior results.
A minimax polynomial of degree five suffices to approximate $x^{2.2}$ to within the accuracy desired by OP. $f(x)=p(x)+\epsilon, \:\: |\epsilon| < 7.4\cdot10^{-5}$. We can observe the equi-oscillation property of the error function $f(x) - p(x)$ and its seven extrema by plotting it, e.g. with Wolfram Alpha. Exemplary C code looks as follows:
/* Approximate x**(2.2) on [0,1] with minimax polynomial. Max. err < 7.4e-5 */
float pow_2p2_minimax (float x)
{
    const float c0 =  1.06425546e-1f; //  0x1.b3eb46p-4
    const float c1 = -3.56089801e-1f; // -0x1.6ca2cep-2
    const float c2 =  5.86735249e-1f; //  0x1.2c6890p-1
    const float c3 =  6.73461437e-1f; //  0x1.58cff0p-1
    const float c4 = -1.05324369e-2f; // -0x1.59207cp-7
    const float c5 =  7.38649687e-5f; //  0x1.35cfe8p-14
    return ((((c0 * x + c1) * x + c2) * x + c3) * x + c4) * x + c5;
}

Note that the minimax polynomial does not return zero at the origin. If we desire this property, we can add this additional constraint by using $f(x) = x^{2}p(x) +\epsilon$. An example, with $|\epsilon| < 1.33 \cdot 10^{-4}$, is shown in this exemplary C implementation (plot of error function):
/* Approximate x**(2.2) on [0,1] with constrained minimax. Max. err < 1.33e-4 */
float pow_2p2_constraint (float x)
{
    const float c0 = -3.66555989e-1f; // -0x1.775a74p-2
    const float c1 =  1.19028902e+0f; //  0x1.30b6c8p+0
    const float c2 = -1.55231142e+0f; // -0x1.8d6448p+0
    const float c3 =  1.19035530e+0f; //  0x1.30bb20p+0
    const float c4 =  5.38091123e-1f; //  0x1.1380aep-1
    return x * x * ((((c0 * x + c1) * x + c2) * x + c3) * x + c4);
}

The computation of $x^{1/2.2}$ is a bit trickier. The easiest approach that does not suffer from premature underflow seems to be the following: Compute $y = \sqrt{\sqrt{x}} = x^{\frac{1}{4}}$, then compute $y^{\frac{20}{11}} = p(y) + \epsilon$ = $x^{\frac{5}{11}} = x^{1/2.2}$. The square root function is very fast on many modern processors, but slow on others, so this may not be a universal win, depending on how pow() is implemented. To achieve the error bound desired by OP, a minimax polynomial of degree six is needed, resulting in $|\epsilon| < 7.5 \cdot 10^{-5}$. Exemplary C code looks like so:
/* Approximate x**(1/2.2) on [0,1] with minimax polynomial. Max. err < 7.5e-5 */
float pow_0p4545_minimax (float x)
{
    const float c0 =  3.07896197e-1f; //  0x1.3b4924p-2
    const float c1 = -1.06079876e+0f; // -0x1.0f9082p+0
    const float c2 =  1.48817670e+0f; //  0x1.7cf926p+0
    const float c3 = -1.18180847e+0f; // -0x1.2e8b00p+0
    const float c4 =  1.42678642e+0f; //  0x1.6d41e0p+0
    const float c5 =  1.98969673e-2f; //  0x1.45fdeep-6
    const float c6 = -7.45610159e-5f; // -0x1.38bb48p-14

    /* compute x**0.25 */
    x = sqrtf (sqrtf (x));
    /* compute (x**0.25)**(20/11) = x**(1/2.2) */
    return (((((c0 * x + c1) * x + c2) * x + c3) * x + c4) * x + c5) * x + c6;
}


How can I combine my interests for pure mathematics and computer science in college? I’m a high school senior who's gone through quite the self-introspection the past few months while applying for college, and I have a bit of a dilemma. All my life, I've loved & excelled at mathematics, and wants to study & explore it very much in depth in college. I get very excited when I read up on fields such as number theory, analysis, topology, and algebraic geometry. On top of that, I've also realized that although I have no experience programming, there are wonderful merits to applying math to computer science and would love to apply my math skills to a fast-growing industry.

I feel, however, that studying comp sci will "limit" the scope and depth of the math I study, because joint programs of math and comp sci will only make you take math classes relevant to the study of computer science. Out of the Common App colleges I'm applying to, Emory, NYU, and BU have joint majors in math and computer science, while UMiami only has a BS in mathematics, and Georgia Tech has BSs in discrete and applied mathematics. For Emory, for instance, I'll be "missing out" on multivariable calculus, complex variables, real analysis, and abstract algebra.

If there is a way to combine these two interests without limiting the mathematics I learn, that'd be amazing, but if not, so be it. If you feel I have certain misconceptions, please feel free to point them out. Lastly, I know this is not the best place to ask this question, as it is directed towards students and researchers of computer science, but I would love your input and appreciate it ahead of time!

Thank you!

Math is heavily used in both computer security, machine learning and AI.

Computer Security, such as encryption and related fields is all about finding math that makes it impossible to retrieve information without being the intended recipient.  With quantum computing possibility being a reality within the next 10 - 20 years there is a lot of work needed to come up with new ways of securing data.  Number theory is very relevant here.
Machine learning is heavily based on statistics.  new algo's with better capability of prediction is always relevant, and a very hot topic.
AI, while strictly an area of machine learning, are typically resolving to other areas of of learning than typical stats.  Any advancements in this areas will be done by people with strong math background.


How to Solve the following Recurrence Equation? I wanted to Solve the following Recurrence Equation using Master Theorem and Back substitution but Im stuck at certain point . can u pls help me how to proceed further

$T(n)=T(\sqrt{n})+n+c$

Using Master Theorem,

put n = $2^{m}$

$ T(n)=T(2^{m})= S(m)$ ie $T(\sqrt{n}) = S(\frac{m}{2})$

Hence the Recurrence Relation will be
$S(m)=S(\frac{m}{2})+ 2^{m}$

Here a =1 , b=2 $f(m)=2^{m}$

case 1 :  $2^{m} \notin O(m^{\log_b a - \epsilon })$

case 2 : $2^{m} \notin \Theta (m^{\log_b a } \log^{k} n)$

case 3 : $2^{m} \in \Omega (m^{\log_b a +\epsilon } )$

put $\epsilon = 1$  We get

$2^{m} \in \Omega (m^{\log_2 1 +1 } ) \Rightarrow \Omega (m^{0+1})\Rightarrow \Omega (m)$ Which is True

Now checking Regularity

$af(\frac{m}{b})\leq \delta f(m) \Rightarrow f(\frac{m}{2})\leq \delta f(m)$

ie .$2^{\frac{m}{2}} \leq \delta \ 2^{m}$ taking log on both sides
$\frac{m}{2}\leq \log_2 \delta +m$

taking $\delta =\frac{1}{2}$

$\frac{m}{2}\leq -1 +m \Rightarrow 1 \leq  \frac{m}{2} $

How to check this last condition is satisfied or not ? How to proceed from here... ?

Using back Substitution
$T(n)=T(\sqrt{n})+n+c$

$T(n)= T(n^{\frac{1}{2}})+n+b \\ = T(n^{\frac{1}{4}})+n^{\frac{1}{2}}+n+2b \\ =T(n^{\frac{1}{8}})+n^{\frac{1}{4}}+n^{\frac{1}{2}}+n+3b \\ ... \\ .. \\ = T(n^{\frac{1}{2^{k}}})+\sum_{i=1}^{k} n^{\frac{1}{2^{i}}} + kb$

How to Evaluate the summation ? How to proceed further... ?

please explain both the method.

Regarding the master method, I don't quite understand why you got stuck. You had to show that the function $f(n) = 2^n$ satisfies $f(n/2) \leq (1-\epsilon) f(n)$ for some $\epsilon > 0$ and large enough $n$. You showed this using some complicated calculation. So the condition is satisfied, and the method applies, giving the answer $T(2^m) = \Theta(f(m)) = \Theta(2^m)$. A more elementary way to check the condition is to notice that when $n \geq 2$,
$$
2^{n/2} \leq 2^{n-1} = \frac{1}{2} \cdot 2^n.
$$

Regarding substitution, clearly $f(n) \geq n + c$. In the other direction, when $n \geq M$ we have $\sqrt{n} \leq n/\sqrt{n} \leq n/\sqrt{M}$, $\sqrt[4]{n} \leq \sqrt{n}/\sqrt{M} \leq n/M$, and so on. Therefore when $n^{1/2^{k+1}} \geq M$,
$$
\begin{align*}
f(n) &= n + c + \sqrt{n} + c + \cdots + n^{1/2^k} + c + f(n^{1/2^{k+1}}) \\ &\leq n + \frac{n}{\sqrt{M}} + \cdots + \frac{n}{\sqrt{M}^k} + (k+1) c + f(n^{1/2^{k+1}}) \\ &\leq
n \sum_{t=0}^\infty \frac{1}{\sqrt{M}^t} + (k+1)c + f(n^{1/2^{k+1}}) \\ &=
\frac{1}{1-1/\sqrt{M}} n + (k+1)c + f(n^{1/2^{k+1}}).
\end{align*}
$$
Choosing $k$ so that $n^{1/2^{k+1}} \approx M$, we deduce that
$$
f(n) \leq \frac{1}{1-1/\sqrt{M}} n + O(c\log\log n),
$$
where the hidden constant depends on $M$. Choosing an arbitrary $M$, we get $f(n) = O(n)$. This implies that
$$
f(n) = n + c + f(\sqrt{n}) = n + O(\sqrt{n}).
$$
Combining this with the lower bound, we have
$$
n + c \leq f(n) \leq n + O(\sqrt{n}).
$$
This is a much better estimate than the one we got using the master theorem.


Difference between regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ Can anyone tell me what is the difference between the following regular expressions: $(0^*1^*)^*$ and $(0+1)^*$ ? To me they look like generating the same string.

The language of both regular expressions is the same, $L((0+1)^*)=L((0^*1^*)^*)$. This follows from the following three claims:

Claim 1:

  if $L_1 \subseteq L_2$, then $L_1^* \subseteq L_2^*$.

Claim 2:

  $L(0+1) \subseteq L(0^*1^*)$

Claim 3:

  $ (0^*1^*)^* \subseteq (0+1)^* \equiv \Sigma^*$

The 2nd and 3rd claims are trivial. Prove the first claim and you're done.

Note however, that the two regular expressions are not the same (ie., they are different!). They are equivalent in the sense of the language they generate. They are different in the way they generate it.


What is semantic closure? In the context of database theory, what does semantic closure mean (linguistically speaking, i.e. not the mathematical definition)

If X is the set of attributes of $F$, then the semantic closure $F^+$ of $F$ is defined as follows:
$F^+=\{$ Y $\rightarrow$ Z $\ |\ $ Y $\cup$ Z $\subseteq$ X $\wedge\ F \models$ Y $\rightarrow$ Z $\}$
$F \models $ Y $\rightarrow$ Z means that any database instance that satisfies every functional dependency of $F$ also satisfies Y $\rightarrow$ Z

In this context, $F^+ = \{ X \rightarrow Y \mid F \models X \rightarrow Y \}$ is the set of all the dependencies that semantically (logically) follow from $F$ as you wrote.
You also have a syntactic closure, defined as $F^\star = \{ X \rightarrow Y \mid F \vdash X \rightarrow Y \}$ where $F \vdash X \rightarrow Y$ means that $X \rightarrow Y$ can be deduced from $F$ according to an inference system, in this case, Armstrong's axioms.

Armstrong's system is both sound and complete so $F^+ = F^\star$, but the concepts are different. To illustrate the difference, let $\Sigma = \{A \rightarrow B, BC \rightarrow D\}$ and prove the following:

$AC \rightarrow D \in \Sigma^+$ (semantic proof). Let $r$ an instance such that $r \models A \rightarrow B$ and $r \models BC \rightarrow D$. Assume $t_1, t_2 \in r$ with $t_1[AC] = t_2[AC]$ this implies $t_1[A] = t_2[A]$ which implies $t_1[B] = t_2[B]$ because $r \models A \rightarrow B$. Thus we have $t_1[BC] = t_2[BC]$ and we can conclude $t_1[D] = t_2[D]$ because  $r \models BC \rightarrow D$. Thus $t_1[AC] = t_2[AC]$ implies $t_1[D] = t_2[D]$ for arbitrary tuples $t_1$ and $t_2$ so $r \models AC \rightarrow D$. We have shown an arbitrary instance model of $\Sigma$   is a model of  $AC \rightarrow D$ too, so $\Sigma \models AC \rightarrow D$.
$AC \rightarrow D \in \Sigma^\star$ (axiomatic proof). From  $A \rightarrow B$ we obtain  $AC \rightarrow BC$ by augmentation. Now using $BC \rightarrow D$ we obtain $AC \rightarrow D$ by transitivity.


Regular language where syntactic right congruence and syntactic congruence differ Find an example of a regular language where the syntactic right congruence and the syntactic congruence are not identical.

I have gone through the relevant definitions and understand them, but could not figure out an example for this case.

Definition: An equivalence relation $\sim$ on $\Sigma^*$ is a right (left) congruence if $x\sim y$ implies $xv\sim yv$ (respectively $vx\sim vy$) for every $x, y, v \in\Sigma^*$.
Definition: Given a language $L$ over an alphabet $\Sigma$, the canonical right congruence $\sim_L$ is defined by $x\sim_L y$ if and only if for all $z\in\Sigma^*$ we have $xz\in L\iff yz\in L$. Similarly, for the canonical left congruence $x{}_{L}\sim y$ if for all $z\in\Sigma^*$ we have that $zx\in L\iff zy\in L$.
Example: Consider the (regular) language $L=\{ab,abb\}$ over $\Sigma^*$. For this language, the relations $\sim_L$ and ${}_L\sim$ are not the same.
In fact, according to ${}_L\sim$ the words $x=ab$ and $y=abb$ are in the same class. This is because if we prepend any $z\in\Sigma^*$ to $x$ and $y$, both word $zx$ and $zy$ are in $L$ or not simultaneously. In fact, for $z=\epsilon$ both $zx=\epsilon ab=ab$ and $zy=\epsilon abb=abb$ are in $L$. However, when $z\neq \epsilon$, then both $zx$ and $zy$ are not in $L$. Therefore $ab{}_L\sim abb$.
Now, when we consider the relation $\sim_L$, we have that $ab\not\sim_L abb$. In fact, if we take $z=b$ we get that $xz=abb\in L$ but $yz=abbb\not\in L$.
So, the regular language $L$ is an example for which its left and right canonical congruences are not the same relation.


Grammar of a non-regular language Given the alphabet $Λ = \{a, b\}$ and this non-regular language:

$$L=\{aba^nb^ma^n|n,m>0\}$$

what's the best way to generate the grammar?  Every string has to start with $ab$, then we have $aba$ and this part has to have the same number of $a$. In words that is clear, but I'm stuck; should I first consider the fixed part $ab$, or is better to produce the $a^nb^ma^n$ part and then add the $ab$? I need a method basically.

You should think of this language as all words of the form
$$
xa^nya^n,
$$
where $x=ab$ and $y \in b^*$. You can now modify a grammar for $a^nb^n$ to generate your language.


Precise runtime of the algorithm to find number of digits in an integer Consider an integer ( of arbitrary length ). To find the number of digits it has, here is a known simple algorithm

count = 1;
while ( (value = value/10) )    count++;

Now, what is the time cost of this algorithm? If we assume that k is the number of bits ( not digits) required to represent the number, then it is O(k). But this algorithm doesn't have a clean linear behavior. That is, if I double the the number of bits in the integer, the number of iterations of while loop doesn't necessarily double every time. An increase of 3-4 bits in the input increases the iteration count by 1.

I know that the number of digits in a number N is floor(log10(N)) + 1 but then we wouldn't be expressing the runtime in terms of number of bits, which is what I need.

In such cases how to calculate the runtime precisely?

There are two answers here:

$\log_{10} n = \log_{10} 2 \log_2 n$, and $\log_2 n$ is (almost) the length of $n$ in bits.
We don't care about the exact complexity. The point of big O notation is to hide multiplicative constants. A function is $O(\log_2 n)$ iff it is $O(\log_{10} n)$. Moreover, the exact time complexity depends on the exact computation model used (i.e. compiler, CPU, operating system and environment – presumably this code snippet runs on actual hardware and its execution time is measured in seconds), which you haven't specified anyway. Again, the point of big O notation is that these details don't matter since they only affect the complexity by a multiplicative constant.

Another point which you should consider is that in practice, either value has a fixed length, or it is variable length (bignum). If it has fixed length (say it's a 32 bit integer), then the correct parameter here is not the length (which is constant) but the value itself. If it has variable length, then the division instruction cannot be reasonably assumed to take constant time.


Is Binary Search Related to Binary Search Tree? I was reading binary search and suddenly realized that it would be very difficult for a binary search tree to find the middle value and then split in two. Are these related at all?

A balanced binary search tree describes the working of the binary search algorithm on a sorted list. The root should contain the middle element, the left subtree the left half, the right subtree the right half, and so on recursively. The tree also has to be balanced, that is, to reflect the fact that we chose the middle element as the root. In this sense, a binary search tree is a generalization of binary search on a sorted list.


What exactly is the difference between supervised and unsupervised learning? I am trying to understand clustering methods.

What I I think I understood:

In supervised learning, the categories/labels data is assigned to are known before computation. So, the labels, classes or categories are being used in order to "learn" the parameters that are really significant for those clusters.
In unsupervised learning, datasets are assigned to segments, without the clusters being known.

Does that mean that, if I don't even know which parameters are crucial for a segmentation, I should prefer supervised learning?

The difference is that in supervised learning the "categories", "classes" or "labels" are known. In unsupervised learning, they are not, and the learning process attempts to find appropriate "categories". In both kinds of learning all parameters are considered to determine which are most appropriate to perform the classification.

Whether you chose supervised or unsupervised should be based on whether or not you know what the "categories" of your data are. If you know, use supervised learning. If you do not know, then use unsupervised.

As you have a large number of parameters and you do not know which ones are relevant, you could use something like principle component analysis to help determine the relevant ones.


Complexity analysis of an unsolvable algorithmic problem? In my automata theory class, for our term project we are required to present a complexity analysis for our algorithmic problem. I have chosen an unsolvable problem, and he has off-the-cuff mentioned that any unsolvable problem would have a complexity of infinite.

However, this strikes me as strange. It feels intuitive to me to say that an unsolvable problem would have no complexity, as any attempt to solve it would be impossible. The quantity of infinity says to me that "if you had unlimited time, you could solve it", but what if it's a question that the answer simply cannot be computed for?

Is this O(infinity) concept common in algorithmic complexity analyses?

Basically, this is a degenerate case.  We can adopt the convention that the running time of any algorithm is $\infty$ (so its complexity is $\infty$), or we can adopt the convention that it doesn't have a complexity.  For informal conversation, probably it doesn't matter much what convention you adopt, as long as it's clear which you're using and what you mean.

See also how to calculate time complexity of non terminating loops for discussion of the running time of an algorithm that never terminates, and What is the difference between an algorithm, a language and a problem? for background on the difference between the complexity of an algorithm vs the complexity of a problem.


Sequencing or continuation-passing in pure lambda-calculus I am trying to solve the following exercise given here.
Consider the following number representation. How to define the addition?
|0| = λx.x
|1| = λx.λx.x
 ...
|n + 1| = λx.|n|

The successor and predecessor operators are easy to define:
Succ n = λx.n
Pred n = n (λx.x)

An "obvious" solution for defining the addition is to use the successor operation plus the test for zero together with the fixed point combinator, something like (Y F) for F given below (the operator if and booleans are defined as usual):
F = λf.(λm n. if (Is0 m) n (Succ (f (Pred m) n))

But defining Is0 seems non-trivial. The problem is that a numeral |N| consumes N+1 arguments, and N arguments are simply erased by it. Hence, if I apply such a function, it seems reasonable to stop its application when it becomes clear that the numeral, e.g. is not an identity. I guess it is some sort of continuation, but I cannot imagine how to model it in the pure lambda-calculus. Maybe someone knows any tips that may help?
A sequencing operator can also help to define the addition. If an application of a numeral |m| is delayed until a numeral |n| is applied to all its arguments, the result will be exactly a numeral |n+m|. Maybe there exists a variant of such a sequencing combinator in the pure lambda-calculus?
The answer which is provided by the author of the exercise uses a non-pure operation (namely, IsProcedure which checks whether its argument is a function).
UPD: It is not hard to do a CPS in lambda-calculus (details for CBV can be found here). Seems that is not enough for solving the problem.
UPD: If we have some version of quote-eval functions for the pure lambda-calculus, then there must be a function $eq$, which recognizes whether the quoted lambda-expressions are syntactically equal, and we can construct Is0 using $eq$. But I doubt that $eq$ is definable. The reason is "genericity lemma" (Barendregt book, lemma 14.3.24). If we were able to test equality on the quoted lambda-terms then ($eq$ (Quote $\Omega$) (Quote $\lambda x.x$)) would return $False$, and the genericity implies that ($eq$ (Quote $\lambda x.x$) (Quote $\lambda x.x$)) would also return $False$. Does that contradict a possibility of constructing Quote in the pure lambda-calculus?

I do not think you will find what you are looking for in the pure lambda calculus. The key is this statement you made:

A sequencing operator can also help to define the addition. If an application of a numeral |m| is delayed until a numeral |n| is applied to all its arguments, ...

Well, models of the lambda calculus are supposed to be like:
$$U \cong U^U$$
And the point of this is that every semantic value $u \in U$ may be applied to something. So it makes no sense to talk about something being "applied to all its arguments." There is no value that cannot be applied to more arguments in the pure lambda calculus.
I don't know off hand of a model/argument that this representation of naturals makes it impossible to implement IsZero, although some thinking about it makes it seem unlikely. However, if it is to be possible in the pure lambda calculus, it will have to make sense semantically, and not be based on notions that are only syntactic.
Edit: here is a sketch of an argument. A definition of $\mathsf{IsZero}$ must eventually reduce like:
$$\mathsf{IsZero}\ n \rightsquigarrow^* n \overrightarrow v$$
The reason is that applying to some number of values is the only mechanism in the lambda calculus to actually distinguish between numerals. It needs to be the case that: $$0 \overrightarrow v = \mathsf{true} \\ \mathsf{s}n \overrightarrow v = \mathsf{false}$$ However, for every $\overrightarrow v$ it is the case that: $$||\overrightarrow v| + k|\overrightarrow v = |k|$$ (where $|\overrightarrow v|$ is the length of $\overrightarrow v$). But only $|1| = \mathsf{false}$ (if that is the convention chosen). In English, there is no bound on the number of terms required to get a boolean by applying a numeral. So there cannot be a $\overrightarrow v$ that satisfies the equations for all numerals, and thus $\mathsf{IsZero}$ cannot be defined.


Which is better, Flood Fill or Scanline Fill algorithm ? Which is better, Flood Fill or Scanline Fill algorithm in computer graphics? My thoughts says that both of them has the same efficiency in term of time and space complexity. Maybe you guys have another thinking? Thanks

They have different purposes.

Flood fill implies that you have a graph with neighbours and a starting node. You need a data structure to hold the frontier of nodes you still have to fill (and possible one for all the nodes you have visited). But each node is visited exactly once.

Whereas the scanline implies that you have points in a coordinate system. Each point you visit may add new points of interest further along. You need a data structure to hold the sorted points.


Finding Connected Components Dependent on Order? It seems to me that the outcome of a connected components algo is dependent on the start vertex. Is this correct?

Say we had the graph

If we started our connected component search from the vertex on the upper right then we would end up with different set of connected components than if we started our search with the vertex in the upper left?

Is this correct?

There's a few things we need to clear up.

First, the graph you show is directed. Are we talking strongly-connected, weakly connected, bilaterally-connected, etc. What you mean by connected here matters.

Secondly, in such an algorithm, usually you keep searching until each vertex in the graph has been assigned a component.

So, if you use the algorithm(s) properly, and keep searching until all vertices have been classified, the output will not depend on what vertex you start at. Each vertex belongs to exactly one connected component (whichever variety you choose), and a correct algorithm will assign it as such, regardless of the start vertex.

However, if you start at a vertex, you might not find all vertices just in the search starting from that vertex, which is why you need to repeat your search until you have seen all vertices.


Is there a proof that shows why DFAs can't be used to show the concatenation of two regular languages? Sipser goes on to show that regular languages are closed under concatenation using NFAs. His proofs typically use NFAs to prove closure under the operations.

Is there an alternative proof that goes on to show that regular languages are also closed under concatenation using DFAs?

Using NFAs does prove the result for regular languages, since NFAs accept exactly the regular languages. In principle, one could give a proof using DFAs but it's likely to be very fiddly and probably not enlightening. It's much easier to give the proof using NFAs and separately show that anything accepted by an NFA is also accepted by a DFA.

Indeed, it's even easier to give the proof using regular expressions! This is part of the point behind giving the three equivalent characterizations of the regular languages: it means that, when you want to prove something about regular languages, you can use whatever system makes the proof easiest.


Is the empty string and some words of even length are elements of this set? $L = \{w \in \{a,b\}^*| \text{the first, the middle, and the last characters of $w$ are identical}\}$.

I have my answers, but I need confirmation:

Is the empty string $\epsilon \in L$? Yes. Reason: there is no first, middle, or last character to break the rule.

Words of even length, assuming the first and last characters of them are identical, again, must be in $L$, as there is no middle character to break the rule in such words.

This is in the context of theory of computation by the way.

Yes, since "the first, the middle, and the last characters of $w$ are identical" is not really well defined here (so there might be ambiguities like is $\epsilon\in L$?)

Probably it wont really matter for the question if you assume $\epsilon\in L$ or $\epsilon \notin L$ (other than some small change in the PDA or CFG) But if you really want to make sure everything is ok, then write (in the answer for the question) that there are ambiguities and this is how you interpeted them.


(M)ILP overlap of two intervals I got an ILP Model where $c_i$ represents the starting time for a visit$_i$.
$c_i$ is already constraint by a number of constraints, one is $c_i > 0$.

I have now outside of my model 0 or multiple desired intervals for the visit$_i$, lets call them $dStart_{ik}$ and $dEnd_{ik}$ where k represents the k-th desired interval. i started by adding two variables per k: $desiredStart_{ik}$ and $desiredEnd_{ik}$.

I added the constraints

$desiredStart_{ik} >= dStart_{ik}$

$desiredStart_{ik} >= c_{i}$

$desiredEnd_{ik} <= dEnd_{ik}$

$desiredEnd_{ik} <= c_{i+1}$

$desiredDuration_{ik} <= desiredEnd_{ik} - desiredStart_{ik}$

with the last constraint, i get the problem if the intervals do not overlap, the $desiredDuration_{ik}$ gets negative. So I added a "helper" Variable $desiredHelper_{ik}$ to it so it looks like this:

$desiredDuration_{ik} <= desiredEnd_{ik} - desiredStart_{ik} + desiredHelper_{ik}$

The general problem of my model is a minimsationProblem, so I added these two terms to the target function:

$+100000 \sum_{i=0}^N \sum_{k=0}^N desiredHelper_{ik} -\sum_{i=0}^N \sum_{k=0}^N desiredDuration_{ik} $

With this formulation I see a problem, it favours solutions where the desired interval is closer by the actual solution.
Is there a better formulation? how could I avoid the $desiredHelper_{ik}$ variable?

In case someone else needs this in the future

I ended up using indicator constraints

$desiredOverlap_{ik} = 1 \rightarrow desiredEnd_{ik} - desiredStart_{ik} \geq 0$
$desiredOverlap_{ik} = 1 \rightarrow desiredDuration_{ik} = desiredEnd_{ik} - desiredStart_{ik}$
$desiredOverlap_{ik} = 0 \rightarrow desiredEnd_{ik} - desiredStart_{ik} \leq 0$
$desiredOverlap_{ik} = 0 \rightarrow desiredDuration_{ik} = 0$


How to devise an algorithm that suggests feasible cooking recipes? I once had a veteran in my course that created an algorithm that would suggest cooking recipes. At first, all sort of crazy recipes would come out. Then, she would train the cooking algorithm with real recipes and eventually it would suggest very good ones.

I believe she used something related to Bayes Theorem or Clustering, but she is long gone and so is the algorithm. I have searched the internet but looking for cooking recipes will yield any sort of results but not the one I am looking for. So, my question is:

  What techniques can be used to devise an algorithm that (randomly) suggests feasible recipes (without using a database of fixed recipes)?

Why would I bother looking for a cooking algorithm? Well, it was a very good example of a real world application of the underlying concepts, and such algorithm could be useful in different settings that are closer to the real world.

Hmm, using Bayes Theorem to make new recipes out of old recipes. I imagine you first would want the algorithm to pull apart the ingredients into a form it understands (not sure if we are using NLP for that, or if you manually enter the data in yourself, that's neither here nor there.) From there...

I envision something like this.

Test Data analyzed. Now we have a list of recipes and the probabilities that each ingredient will take place alongside another ingredient, and in what quantities. After we have this data then you would have the program randomly make the new recipes. First it cycles through a list of all the known ingredients, then randomly selects a main ingredient, from there it uses the probabilities of an ingredient given another ingredient to start throwing in more random ingredients, all the while matching appropriate trained data for quantities and compatible ingredients.

Might I suggest that when creating a new recipe the program be given information like, I want something sweet, or something sour, or for instance something mostly made up of wheat.

Hopefully this helps a bit.


Is Turing machine a scientific theory in CS? The English Wikipedia article about Turing machine opens with:

  A Turing machine is a mathematical model of computation that defines
  an abstract machine,[1]

As a Hebrew speaker, I read a similar explanation in Hebrew Wikipedia:

  מכונת טיורינג היא מודל חישובי מתמטי אשר
  באמצעותו ניתן לתאר באופן מופשט את פעולתו של מחשב (כולל מחשב מודרני).

My problem

I understand this term as reflecting a scientific theory in CS or Math, but interestingly, none of the two opening sentences presented this concept as a scientific theory in either CS or Math.

By scientific theory I meant:

  An idea or set of ideas that can be falsified by principle
  (falsifiability as a condition for it to be real) and that one or more
  reinforcements can make it somewhat more plausible in reality.

But;

If it's a theory in Math, maybe my approach is wrong, because, as far as I understand, in Math the paradigm is different so something is either true or false (i.e, not true).

My question

Is Turing machine a scientific theory in CS?

Update

In comment section, Yuval Filmus said (minor paraphrase):

  Turing machines are a mathematical abstraction.
  They're neither a scientific theory nor a practical engineering idea;
  Actual computers are much better modeled using a different abstraction → RAM machines;
  The relevant scientific theory is the Church-Turing thesis.

This made me wonder "what is the difference between a mathematical model and a mathematical abstraction and does the former or the latter or both, can be based in a "scientific theory"?

This isn't the main question, but you are welcome to explain this in an answer as I think it's relevant.

No, as Yuval Filmus explained, a Turing machine is not a scientific theory.

Furthermore, something can be both a mathematical model and a mathematical abstraction; for example, if the model is an abstraction.

Types of scientific theories

In the physical sciences, a scientific theory is a set of rules or models that makes testable predictions that could potentially be falsified. A Turing machine just isn't any of those.

In mathematics, the word "theory" may be used to describe a framework for reasoning where we have axioms, definitions, and inference rules for making deductions that follow from those axioms and definitions.  A Turing machine isn't that, either.

Personal opinion

I don't think it's a good use of time to devote a lot of energy to these kinds of questions. Instead, I would suggest that you learn the basic material in textbooks on Turing machines and computability and decidability, and don't worry too much about how to categorize or classify it or what words can be applied to it.  From a computer science perspective, it's more useful to focus on the mathematics without trying to put it into a philosophical framework or trying to come up with definitions of these broad, vague concepts (abstraction, theory, model).


Would creating a complete computer simulation of the human brain prove the Church-Turing thesis? According to Wikipedia, the Church-Turing thesis "states that a function on the natural numbers is computable by a human being ignoring resource limitations if and only if it is computable by a Turing machine."

If we made a complete simulation of the human brain, that would imply that a Turing machine can do everything that a human brain can do. Wouldn't that prove the thesis?

How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain?

Church–Turing isn't something that can be proven. It's essentially just the statement that Turing machines correspond to the intuitive notion of algorithm and that just isn't a statement of mathematics. The Turing machine is the definition of computability; Church–Turing is essentially the claim that we picked the right definition, in the sense that choosing any of the reasonable alternative definitions would give exactly the same notion of computability.


Rice's theorem application on a language that resembles ETM I'm working on an exercise that involves checking if the Rice's theorem can be applied on a two languages.

The first language is $E_{TM} = \{ \langle M \rangle \text{ | M is a Turing Machine and } L(M) = \emptyset \} $.

I already know it's undecidable, thus Rice's theorem should apply without any problem and in fact it checks the three theorem's requisite just fine.

The second language is $X = \{\langle M \rangle \text{ | M is a Turing Machine that does not halts on any input string \}}$.

To me, the fact that the TM does not halts on any string means that the language is empty, which means that X is similar if not equal to $E_{TM}$.

But the property stated in X is not on the language of the TM, but rather describes what it does on all possible strings.

Is this reasoning correct?

Thanks for your help.

First of all, note that there are undecidable languages where Rice's theorem cannot be applied. In your third paragraph one may suggest that it would work that way. But in fact, for $E_{TM}$ you can apply the theorem.

$X$ is not the same language as $E_{TM}$ but it is a proper subset of $E_{TM}$. E.g. the TM $M_0$ that prints $0$ (reject) immediately after the start for any input and halts after that is in $E_{TM}$ but not in $X$. However, Rice's theorem is applicable for $X$. You have to find a proper, non-empty subset of all computable functions $\mathcal{R}$ that contains precisely the function computed by the TM in $X$. Let $$\mathcal{S} = \{f_M \mid f_M(x) = \bot \text{ for all } x \in \{0, 1\}^\ast\},$$ where $\bot$ means "never halt". Then

$\mathcal{S} \neq \varnothing$ as the function of the Turing machine that immediately goes in an infinite loop is in $\mathcal{S}$,
$\mathcal{S} \neq \mathcal{R}$ as $M_0$'s function (see above) is not in $\mathcal{S}$.

Obviously, the set of all Turing machines that compute a function from $\mathcal{S}$ coincide with $X$. Thus, $X$ is undecidable following Rice's theorem.

Note that Rice's theorem can be stated in different ways but it should look like this when speaking about TMs.


Process Synchronization: Dekker's algorithm This Screenshot is taken from William Stalling's Operating Systems book.
My doubt is that Bounded wait is not satisfied by this solution.

For example: P0 and P1 both want to enter critical section and set their flags to true.

flag[0] = true

flag[ 1] = true

Both p0 and p1 enter while loop, p0 wins the race process P1 sets its flag to false

now flag[ 1]= false

Process P0 goes into Critical Section, comes out, sets turn = 1 and flag[0]=false.

Now actual problem starts from here:

Process P1 comes out of infinite while loop and before i could set flag[ 1] to True from False, it gets preempted.

Now Process P0 can go any number of times in Critical section because Flag[ 1] is False.

Conclusion: Process P1 tried to get access to critical section but because of bad solution it did set its flag to False to give path to Po and now stuck for infinite time.

hence B.W is not satisfied!

When P1 runs again, it set its flag to True. Your scenario assumes P0 is executed continuously, while P1 never gets a chance to execute its code. This also happens in the simple case where there is only one process running, but obviously this does not contradict bounded waiting.

An implicit assumption when talking about protocols for mutual exclusion is that all of the processes involved will eventually run and execute their current command (otherwise it is meaningless to talk about properties such as bounded waiting or starvation freedom).


Dynamic connectivity in forests with constant query time I'm interested in the dynamic connectivity problem for forests. In this problem a forest is subject to updates (edge insertion that do not create cycles and edge deletion)  and queries if two nodes are connected.

Link cut trees and Euler tour trees supports these three operations in $O(\log n)$ (Erik Demaine's notes). The results of Eppstein at. all (Sparsification—a technique for speeding up dynamic graph algorithms, JACM, 1997) for general graphs are $O(\sqrt n)$ for updates and $O(1)$ for queries.

In my use case queries are more common than updates, so I'm looking for an alternative structure (the Eppstein structure is too general and too complicated to implement) that supports updates in sublinear time and queries in constant time. Is there such structure?

An Euler tour tree is a linear representation of a tree. When the tour is stored in a balanced binary search tree keyed (implicitly) by the index in tour, the update and query operations can be done in $O(\log n)$. This is described in the referenced Erik's notes.

The tour can be stored in a two level array (similar to the structure described in section 2.2 of Data Structures for Traveling Salesmen). Each tree tour is stored in $O(\sqrt n)$ arrays with $O(\sqrt n)$ elements in each. Each tour element keeps a reference to its array, and each array keeps an reference to its parent array.

The update operations involves a constant number of arrays so it can be done in $O(\sqrt n)$. The query operation can be done in $O(1)$: The root of the tree containing each element is found and then compared. Each root is found in the position 0 of the first array of the tree tour. To find the tree tour containing a element just follows the element reference to its array and then follows the link to the parent array (that is, the tree tour).


All superlinear runtime algorithms are asymptotically equivalent to convex function? Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?

All the examples that I could think of satisfy the above mentioned requirement. For example, all polynomials are convex on $\mathbb N_+$. Additionally, $n\log(n)$ is convex from $n=2$ and on, so it's asymptotically equivalent to convex function.

Is it true that every algorithm with runtime complexity of $T(n)=\Omega(n)$ satisfies that $T(n)=\Theta(f(n))$ for some convex function $f$?

No. A simple example is
$$T(n)=\begin{cases}n & \text{ when } n \text{ is odd,}\\
n^2 & \text{ when } n \text{ is even.}
\end{cases}$$

What if we also require $T(n)$ be strictly increasing?

The answer is still no. A simple example is

$$T(n)=\begin{cases}2^{(n+1)^2} & \text{ when } n \text{ is odd,}\\
 2^{n^2}+1 & \text{ when } n\text{ is even.}
\end{cases}$$

Since $\displaystyle\lim_{k\to\infty}\frac{T(2k)}{T(2k-1)}=1$ and $\displaystyle\lim_{k\to\infty}\frac{T(2k+1)}{T(2k)}=\infty,$
there is no convex function $f$ such that $T(n)=\Theta(f(n))$.

Exercise 1. What if we also require both $T(n)$ be strictly increasing and $T(n+1)/T(n)$ be bounded?

Exercise 2. Let $T_1$ and $T_2$ be two increasing functions such that $T_2(n)\not=O(T_1(n))$. Show that there is a function $T(n)$ that is bounded between $f_1$ and $f_2$ such that there is no convex function $f(n)$ such that $T(n)=\Theta(f(n))$.


detecting a cycle in an undirected graph problem is in $RL$ complexity class I need come up with an algorithm for detecting a cycle in an undirected graph where the algorithm is in $RL$. That is, the algorithm detects a cycle with a probability greater-equal to $\frac{1}{2}$ but it doesn't return true for a graph with no cycle (no false-positive).

In class, we've learned that $USTCONN$ (the problem of telling if there's a path from $s$ to $t$ in an unidrected graph) is in $RL$.

I thought about utilizing it for the current problem:

We choose $s,t$ in random s.t $t$ has at least $2$ edges and check if there's a path between them.
Then, in the same fashion, we check if there's a path between $s$ and $t$'s neighbors (If there are too many we may limit it to some constant, randomly, since we must use only logarithmic space)
If we found two different paths from $s$ to $u_1,u_2$ where the latter are $t$'s neighbors then there must be two different paths from $s$ to $t$ - Which is a cycle.
We repeat the above sufficiently many times (TBD)

I would like to know if that is the algorithm expected from me to come up with before I put efforts in proving that this algorithm is indeed in $RL$.

Thanks!

In fact USTCONN is in L (as shown by Reingold), and you can reduce your problem to USTCONN using non-backtracking walks. These are walks which are not allowed to backtrack, that is, after going from $x$ to $y$ we can't go immediately back to $x$ (but we could go back to $x$ via a different route). The graph contains a cycle iff there is a non-backtracking walk from some vertex to itself. You can formulate this problem as aan undirected connectivity problem, and solve it using the logspace algorithm for USTCONN. As a result, you can detect whether the graph contains a cycle in logspace.


How are hash table's values stored physically in memory? Question:
How are hash table's values stored in memory such that space if efficiently used and values don't have to be relocated often?
My current understanding (could be wrong):
Let's say I have 3 objects stored in a hash table. Their hash functions generate these values:

0
10
20

I would presume that the pointers of these objects would not be stored at the following memory addresses because there would be huge gaps between them:

startOfHashTable + 0
startOfHashTable + 10
startOfHashTable + 20

The Wikipedia article on hash tables says that the "index" is computed as such:
hash = hashfunc(key)
index = hash % array_size

So in my example, the indices would be:

0 % 3 = 0
10 % 3 = 1
20 % 3 = 2

This gets rid of the huge gaps that I mentioned before. Even with this modulo scheme, there's problems when you add more objects to the hash table. If I add a fourth object to the hash table, I would need to apply % 4 to get the index. Wouldn't that invalidate all the % 3's that I did in the past? Would all those previous % 3's need to be relocated to the % 4 locations?

The entries of a hash table are stored in an array. However, you have misunderstood the application of the modulo operator to the hash values. If the hash table is stored in an array of size $n$, then the hash function is computed modulo $n$, regardless of how many items are currently stored in the table.  So, in your example, if you were storing the items in an array of size 6, the three items with hash values 0, 10 and 20 would be stored at locations 0, 4 and 2, respectively.  If you added a fourth element with hash value, say, 31, that would be stored at location 1, without needing to move any of the first three items.  If your hash table was becoming full and you wanted to move it into a bigger array, then you would need to recalculate the locations of all the items in the table and move them appropriately.


A DFA for recognizing comments The following DFA is a lexical analyzer which is supposed to recognize comments. The lexical analyzer will ignore the comment and goes back to the state one. I'm told that there's something wrong with it but I can't figure it out. What's the problem?

FWIW, those tiny signs are stars which are necessary for C-style comment: "/* comment */"
  The loop in the state three is "except *"

There is no initial state, so there's no automaton. I suppose $1$ is the initial state.
From state 4 you can still read several times the symbol $*$ and accept the comment. For example, the coment /*hello*/ is being accepted, but the comment /*hello**/ is not. So you need $\delta(4,*)=4$.
Also, you need more transitions for the automaton to be a DFA. Remember that a DFA has a defined transition for all symbols from all states.

For example, you need transitions from $4$ with other symbols ($\delta(4,x)=3$ for $x\in\Sigma\smallsetminus\{*,/\}$).
The same goes for $1$ and $2$, but I leave that as an exercise ;-)


Are too many function calls bad(as in slows speed performance) for programs written using interpretor-based scripting language(JavaScript, Perl)? The interpreters used for running scripting language (i.e., JavaScript, Perl, PHP, etc. ) programs go line-by-line.  Isn't it better to Avoid too many function invocations for programs written in said scripting languages?  However, Avoiding writing functions would be really a pain because you would have huge blocks of code that go continuously (basically No modularity)

@d-w Sorry, I should have mentioned that since interpreters for scripting languages go line-by-line, I thought it would be slower with more function calls. In compiler-based languages, it would be faster because the compiler's optimizing features could substitute the actual code within the function where the function is actually invoked. Basically, I thought compilers are more sophisticated, while interpreters just go line-by-line.  Is the aforementioned belief correct?

Practically speaking, function calls have a cost.  They have a cost if your language is interpreted.  They have a cost of your language is compiled.  Some compilers can substitute the code for some functions (it's called inlining), but in the vast majority of cases, one does not do that.

However, the cost of a function call is low.  If you have a 50 line function with a reasonable amount of work done on each line, you'll find function calls account for less than 1% of your total runtime.  Their value in organization typically far exceeds their cost.

You don't want to be excessive with function calls unless you can inline them.  Some styles of code depend on inlining, such as some C++ code which may have 10+ function calls nested and do perhaps 3 lines worth of work.  That kind of a situation demands inlining.  However, for the vast majority of the cases, don't worry about it.

You will eventually learn how to profile your code, which is a way to find hotspots where you spend a lot of your time.  Always profile before you optimize.  You will find that most of your function calls don't have a significant effect on runtime at all, and if you're unlucky, 3-4 functions might have too much overhead.  Then you remove those functions, inlining the code manually, and you leave all of the other functions.

If you're interested in numbers, it is estimated that a function call in Python (an interpreted language) costs between 150ns and 350ns.  In C++, the cost is on the order of 15-30 instructions, which is on par with a L1 cache miss (if that term doesn't mean anything to you, it's a good indicator of just how fast these function calls are).  On a 4GHz processor, that's 4-8ns.


Solving a discrete optimization problem Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative functions of $x_i$. Values of both functions are given for all values of $x_i$. Now consider the optimization problem
\begin{align}\max_{x_1,\dots,x_n}&\sum_jf_j(x_j) \\\text{s.t.}&\sum_jg_j(x_j)\leq B&\end{align}where $B$ is a given positive constant. The straightforward solution is to do a brute-force search. However, this will be exponentially complex. Is this problem studied in literature? What are the known approaches to this? If you are familiar with solution approaches or relevant references, please point them out.

Complexity

Your problem is NP-hard.  Therefore, you should not expect any efficient algorithm that will always find the optimal solution.

In particular, your problem is a generalization of the knapsack problem.  Suppose we insist that $f_i(5)=f_i(6)=\cdots=f_i(4999)=0$ for all $i$ (but $f_i(5000)$ can be any positive integer), and the same for the $g_i$.  Then the problem becomes exactly the knapsack problem.  In particular, the knapsack problem is a special case of your problem, which means your problem is at least as hard as the knapsack problem, as any algorithm for your problem could also be used to solve the knapsack problem.  Moreover, the knapsack problem is NP-hard, so your problem is too.

Therefore, you're going to have to make some compromises.  You could look for heuristics that produce the optimal solution and sometimes run fast, but in the worst case might take exponential time.  Or, you could look for heuristics that produce an approximate solution (not optimal, but hopefully close to it).  I'll outline several approaches.

Exact solutions

Suppose you want the exact optimum solution.  Then I know of two reasonable approaches, depending on how large $B$ is.

If $B$ is small, you can adapt the standard dynamic programming algorithm for the knapsack problem to this situation.  The running time will be roughly proportional to $B$, so if $B$ is not too large, this is reasonable, but if $B$ is a 100-bit integer, this is completely infeasible.

Alternatively, you can use integer linear programming.  Introduce zero-or-one variables $v_{i,k}$, with the intended meaning that $v_{i,k}=1$ means that you've set $x_i$ to $k$.  Add constraints to ensure that $x_i$ is set to  a single value ($v_{i,5} + \dots + v_{i,5000}=1$) and that $g_1(x_1)+\dots+g_n(x_n)\le B$ (namely, $\sum_{i,k} v_{i,k} g_i(k) \le B$), and then maximize the objective function $\sum_{i,k} v_{i,k} f_i(k)$.  Feed this to an off-the-shelf ILP solver, and it might find a solution for you, if you are lucky and the size of the problem is not too large.

Approximate solutions

If you're willing to accept an approximate solution that isn't necessarily optimal but should be close to optimal, there are several possible approaches.

One approach is to create the ILP problem above, run the ILP solver for a limited amount of time, then stop the solver and ask it to give you the best solution it has found so far.  Many ILP solvers have the ability to do that.

Another approach is to round to a limited precision.  Pick a constant $c>1$, and replace each $g_i(x)$ with $\lfloor g_i(x)/c \rfloor$ and replace $B$ with $\lfloor B/c \rfloor$.  In other words, divide all the $g$'s and $B$ by $c$, and then round to an integer.  Now solve the resulting problem.  This is an instance of your problem, but with smaller numbers and a smaller $B$, so you can now try to find an exact solution to this smaller problem -- for instance, using dynamic programming.  The optimal solution to this smaller problem will correspond to a close-to-optimal solution to the original problem.  You can tune the value of $c$: the larger $c$ is, the more efficient this will be, but the worse the quality of the solution.

There may be other methods.  You could study the literature on the knapsack problem to see what techniques have been considered there and see  how to adapt them to your situation.  But the above is probably a pretty good starting point.


Does this context-free grammar generate a regular language? Does the following set of production rules produce a regular language or not?

$S \to AB \mid b $
$A \to SB$
$B \to AS \mid a$

I have generated following words with above grammar

$b , baa , baaaa , baaaaaa, .....$
$bbaba , babab , bababaa , bbbabba ,.....$

But I am not able to create a language using it.
Is this grammar just context free or is this regular also ?
If yes, how to prove that ?

The grammar can be transformed to

$\quad$ $S \to SBB \mid b $
$\quad$ $B \to SBS \mid a$

Let $L_S$ be the language generated by the rules above (with $S$ as the start symbol). $L_S$ is context-free by definition.

We will prove it is not regular. The idea comes from the rule, $B\to SBS$.

Let $L_B$ be the language generated by the two rules above with $B$ as the start symbol.

Claim: We have the following inclusions of languages.
$\quad\{b\}\cup\{b^{i+1}ab^ia\mid i\ge0\}\subseteq L_S$
$\quad\{b^iab^i\mid i\ge0\}\subseteq L_B$

Proof: Use mathematical induction on $n$, the upper bound for $i$.

The base case when $n=0$. $S\Rightarrow SBB \Rightarrow^*  baa$ and $B\Rightarrow a$.
Suppose it is true for $n$. Then $B\Rightarrow SBS\Rightarrow^* b(b^nab^n)b=b^{n+1}ab^{n+1}$. $S\Rightarrow SBB\Rightarrow^* b(b^{n+1}ab^{n+1})a=b^{(n+1)+1}ab^{n+1}a$. So it is true for $n+1$ as well.

Claim: We have following inclusions of languages.
$\quad L_S\subseteq E_S :=\{ba^{2i}\mid i\ge0\}\cup\{b^{i+1}ab^ia\mid i>0\}\cup\{\text{words that have at least three } a\text{'s}\}$
$\quad L_B\subseteq E_B:=\{a\}\cup\{\text{words that have at least two } a\text{'s}\}$

Proof: It is easy to check that $E_SE_BE_B\subseteq E_S$, $a\in E_S$, $E_BE_SE_B\subseteq E_B$ and $b\in E_B$.

The above two claims implies that $L_S\cap L(b^*ab^*a) = \{b^{i+1}ab^ia\mid i\ge0\}$, which is not a regular language. Since $L(b^*ab^*a)$ is regular, $L_S$ cannot be regular.

Exercise 1. Show that the following grammar generates a regular language.
$\quad$ $S \to SAS \mid b $
$\quad$ $A \to ASA \mid a$

Exercise 2. Show that the following grammar generates a non-regular language.
$\quad$ $S \to AB \mid b $
$\quad$ $B \to SA $
$\quad$ $A \to BS \mid a$


Model disjunction in a $\{0,1\}$ integer linear program How can I model logical OR as an integer linear program?

$$(y_3 + y_4 + y_5 + y_6 = 2) \lor (y_2  = 1)$$

where $y_i \in \{0, 1\}$, $1$ = True and $0$ = False.

Let's assume that all variables are Boolean (constrained to $\{0,1\}$). Here is how to encode the constraint "$x+y=1$ or $z=1$". Presumably you can extend this.

$$
\begin{align*}
&x+y+u-v = 1 \\
&z+w = 1 \\
&w+u+v \leq 1
\end{align*}
$$

If $x+y = 1$ then we take $u=v=0$ and $w=1-z$.

If $z = 1$ and $x+y = 0$ then we take $u=1$, $v=0$ and $w=0$.

If $z = 1$ and $x+y = 2$ then we take $u=0$, $v=1$ and $w=0$.

This shows that these equations are solvable when $x+y=1$ and when $z=1$.

Conversely, suppose that these equations are solvable, and so at most one of $w,u,v$ is non-zero. If $w = 0$ then $z = 1$. Otherwise, $u=v=0$ and so $x+y = 1$.


Prove Partition is NP-Complete using that SubsetSum so is it The SubsetSum problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ and $k \in \mathbb{N}_0$ contains a subset of $S$ such that its summation is $k$ or not. This problem is NP-Complete.

The Partition problem decides whether a set $S = \{s_1, s_2,..., s_n\}$ can be partitionated in two subsets such that the difference between the sums of the both sets are lesser or equal to $K$.

Prove that the partition problem is NP-Complete using that SubsetSum so is it.

Any ideas?

Define your $\rm P{\small ARTITION}(S, K)$ problem as:

"Are there partitions $S_1, S_2$ of $S$ such that $|\text{sum}(S_1) - \text{sum}(S_2)| \leq K$, where $\text{sum}(S_i)$ is the sum of all elements of $S_i$?".

Then $\rm P {\small ARTITION}(S, 0)$ would mean $|\text{sum}(S_1) - \text{sum}(S_2)| \leq 0$ which is true only if $\text{sum}(S_1) = \text{sum}(S_2)$. Thus, given $S$ we could reduce the $\rm S{\small UBSET}(S,k)$ problem to the problem asking for existence of two partitions of $S$ with equal sums of elements---$\rm P{\small ARTITION}(S, 0)$.

The reduction to the latter can be done as following:
Let $s=\text{sum(S)}$ and define a new set $S_{new} = S \cup \{2k − s\}$. We choose $2k-s$ since the sum of $S_{new}$ is $2k-s+s = 2k = k+k$, and we want two partitions with equal sizes equal to $k$.

Now call (reduction!) $\rm P{\small ARTITION}(S_{new},0)$. If it returns YES/TRUE then $S_{new}$ can be partitioned into two sets $S_1$ and $S_2$ with sums equal to $k$. Also notice that either $S_1$ or $S_2$ can contain the new element $2k − s$ (since they are partitions) meaning that either $S_1$ or $S_2$ is a subset of $S$. Thus we have a subset (without the element $2k − s$) of $S$ with the sum $k$, and we return YES/TRUE. Otherwise, if we get NO/FALSE then return NO/FALSE.


Calculation of Inorder Traversal Complexity I want to analyze complexity of traversing a BST. I directly thought that its complexity as $O(2^n)$ because there are two recursive cases. I mean $T(n) = constants + 2T(n-1)$. However, AFAI research it is $O(n)$. Can you show it how come and my wrong?

void printInorder(Node node)
    {
        if (node == null)     // I think it is T(0) = 1
            return;           // constant c

        /* first recur on left child */
        printInorder(node.left);     // T(n-1)

        /* then print the data of node */
        System.out.print(node.key + " "); //constant(c)

        /* now recur on right child */
        printInorder(node.right); //T(n-1)
    }

In order to analyse the time complexity of a tree traversal you have to think in the terms of number of nodes visited. If a tree has $n$ nodes, then each node is visited only once in inorder traversal and hence the complexity is $O(n)$.

Here, the input is in terms of number of nodes in the tree and the hence the complexity.

The notion that each recursive call is $T(n-1)$ is wrong. Let say we have a tree that has three children to the left of root and three children to the right of root. So n = 7. Now when you visit root then you have two paths. One to left which has 3 children and one to right which also has 3 children. But $7-1 \neq 3$. Hence this notion of 2 recursive calls of $T(n-1)$ is wrong.

It totally depends on the structure of the tree. In worst case a tree may degenerate to linked list  (a skew tree having children on only one side either left or right) and we know well that traversal of linked list is $O(n)$, for a list of n elements. Hence, also the worst case is $O(n)$.


Why do we use multiple data structures? I'm studying elementary data structures like Linked List, Doubly Linked List and Binary Trees like Binary Search Trees.

Both runs in worst case O(n) in the same operations,  so why don't we use only one data structure?

Aspects other than asymptotic worst case time are also important. For example

Actual speed in practice
Memory consumption
Implementation difficulty

Algorithmic analysis almost never tells you the complete story and never should be used to justify blanket statements like "this data structure is the best if you need operations x,y,z".


Evolutionary algorithm - how to select the parents I try to solve Physical Travelling Salesman Problem using evolutionary algorithm and I have diffucult to detemine how to choose the parent , on which we do the crossover.

Assume I have popultion of 100.
The parent should be selected randomally? or according to their fitness?
If I choose them randomally I don't think the result be enough good but in the other hand, if I will choose the 2 with the best fitness, I will always choose the same! (Maybe child  of them , but most of my population will never be choosed!).

What I miss?

I also need some advise on how to calculate fitness. The parameters are the amount of waypoints each van collect and the total time.

My problem here is becuase there are unit that don't manage to collect any points and thus thier fitness is 0 and step by step my array full with 0....(I am working with the code here : http://www.ptsp-game.net/ ant there is problem of time exceed..)

As a simple method, you can use the roulette wheel selection. The idea is that every individual has a chance to be selected as a parent, but the more fit an individual is, the more likely it is to be selected. Let $f_i$ be the fitness of the individual $i$. The probability $p_i$ of choosing $i$ as a parent for the next round is $p_i = f_i / \sum_{j=1}^{N}$, where N is the size of your population.

Here's an example in the context of TSP. For simplicity, let's say your population is only 4 individuals. Assume every individual is a tour of some length. The shorter the tour, the higher the fitness. Let the fitness values of the tours be $F = \{ 25,15,10,5 \}$. The sum of elements is 55. We divide every element $f_i$ with 55, and obtain $\{ 0.45, 0.27, 0.18, 0.09\}$. To implement the roulette wheel, you can use a weighted random generator if the language provides one (if not, just roll your own).

If you want to experiment with other genetic selection operators, look up other more complicated selection methods. To get you started on those, have a look at selection operators.


Post Correspondence problem provable instance Let the Post Correspondence problem with input

$$K = ((x_1, y_1), . . . ,(x_n, y_n)), x_i, y_i ∈ \Sigma^*$$

for $$ i = 1, . . . , n $$

Find a concrete solution for the input

$$K = ((001,0), (01, 011),(01, 101),(10, 001))$$

The Post Correspondence problem is undecidable so it's really hard to find a concrete solution. I've tried brute forcing it but it gets frustrating after a few tries.

Is there a logical way to deduce that K is a solution, rather than finding a pattern that works?

The smallest solution is

  0110011010010010110011001101001101001001101001001011000100101101010010010100100100101100110001010011010010011000100101100010010100100101001010011000100101

generated by the string

  bdcddbabdcdcddcddbaddbacdaacdddbabaaacdcdabaddbadaacdaacaacabadaac

where $a = (001,0)$, $b=(01,011)$, $c=(01,101)$, $d=(10,001)$.

This solution can be found by a simple pruning procedure:

Start with the list $L$ which contains a pair of empty strings.
At each iteration, attempt to add each of the four "pieces" to each of the pairs in $L$, and remove any pair for which no string is a prefix of the other.

Eventually $L$ will contain a pair of equal strings, in this case after 66 iterations.

As an example, here is the contents of $L$ in the first few iterations:

Iteration 1: (001,0), (01,011)
Iteration 2: (001001,00), (0110,011001)
Iteration 3: (011001,011001011), (011001,011001101)
Iteration 4: (01100101,011001011011), (01100101,011001011101), (01100110,011001101001)

The number of pairs of strings at every iteration fluctuates but generally increases, and after 66 iterations reaches 12081, one of which is the solution given above.


Proving non-regularity via syntactic congruence classes? Let $L$ be a language. The Myhill-Nerode theorem is based on the following equivalence relation:
$$x \equiv_M y \Leftrightarrow \forall v \in \Sigma^*. (xv \in L \leftrightarrow yv \in L).$$
One corollary of the Myhill-Nerode theorem is that if $\equiv_M$ has infinitely many equivalence classes, then $L$ is not a regular language.
There's a different equivalence relation called syntactic congruence which is also due to Myhill:
$$x \equiv_S y \Leftrightarrow \forall u \in \Sigma^*. \forall v \in \Sigma^*. (uxv \in L \leftrightarrow uyv \in L).$$
My question is the following: is it also the case that if $\equiv_S$ has infinitely many equivalence classes, then $L$ is not a regular language? I've tried a smattering of regular languages and each one I've tried has a finite number of these equivalence classes, but I don't see a way to get a general proof to that effect (and I'm not even sure one exists!)

You want to prove that if $\equiv_S$ has infinite index, then $L$ is not a regular language, or, equivalently that if $L$ is regular, then $\equiv_S$ has finite index. This is an immediate consequence of the following result.
Theorem. Let ${\cal A} = (Q, \Sigma, \cdot, i, F)$ be the minimal complete deterministic automaton of $L$. Then $u \equiv_S v$ if and only if, for every state $q \in Q$, $q \cdot u = q \cdot v$.
Proof. Suppose that $u \equiv_S v$ and let $q \in Q$. Since $\cal A$ is minimal, it is accessible, and there exists a word $x$ such that $i \cdot x = q$. Now, for every word $y$,
$$
xuy \in L \iff xvy \in L,
$$
or, equivalently,
$$
1 \cdot xuy \in F \iff 1 \cdot xvy \in F
$$
that is,
$$
(q \cdot u) \cdot y \in F \iff (q \cdot v) \cdot y \in F
$$
It follows that the states $q \cdot u$ and $q \cdot v$ are equivalent, and hence equal, since $\cal A$ is minimal.
Suppose now that for every state $q \in Q$, $q \cdot u = q \cdot v$. Let $x$ and $y$ be words. Then the following equivalences hold:
\begin{align}
xuy \in L &\iff 1 \cdot xuy \in F \iff ((1 \cdot x) \cdot u) \cdot y \in F \\
&\iff ((1 \cdot x) \cdot v) \cdot y \in F \iff 1 \cdot xvy \in F \\
&\iff xvy \in L
\end{align}
and thus $u \equiv_S v$.


Why $((+ 1) ((+ 1) 1))$ is not a $\delta-$redex? I was reading http://barrywatson.se/lsi/lsi_delta_reduction.html, where

((+ 1) 2) →δ 3 is a δ-reduction.
((+ 1) ((+ 1) 1)) is a not a δ-redex.

Wouldn't $((+ 1) ((+ 1) 1)) \rightarrow ((+1) 2)) \rightarrow 3$?

Because the definition of $\delta$-reduction requires that

for all $1≤i≤n$, $N_i$ is normalized

and the second argument $((+1) 1)$ is not normalized.
As you observe, we can first reduce the $\delta$-redex $((+1) 1)$ to $\delta$-normal form $2$; then $((+1) 2)$ is a $\delta$-redex which can be reduced to $\delta$-normal form $3$.
$((+ 1) ((+ 1) 1)) \triangleright_\delta ((+1) 2)) \triangleright_\delta 3$ is a correct reduction, but $((+ 1) ((+ 1) 1))$ isn't a redex in the first step; $((+ 1) 1)$ is.


Constrain traveling salesman: visit a given city within a given distance from start I would like to add an additional constraint to the traveling salesman problem: that a given city is visited within a given distance (say 100) from start. Is there a way to do this? My question is related to this unanswered CS question.

I have a mixed integer program using the R package CVXR that find the shortest route without subroutes (see below). The city order is represent in the vector node_order. The strategy I've pursued so far is:

Re-organize node_order so that the index is the order and the value is the city id
Look up the associated distances in distances
Compute a vector with the cumulative sum of these distances.
Add the constraint that city i must occur before the first index in (3) exceeding the distance constraint for that city.

The issues I've encountered with this approach is that I have not found a way to include finding-index-by-value into the optimization in CVXR. This is needed in both step (1) and (4) above. Maybe this is possible after all, or there is another approach? I am willing to use other packages than CVXR and other software than R.

Current program

library(CVXR)

# Make distances
N = 10
distances = matrix(1:(N*N), ncol = N)

# Flag 1 iff we travel that path. 0 otherwise
do_transition = Variable(N, N, boolean = TRUE)

# Minimize the total duration of the traveled paths.
objective = Minimize(sum(do_transition * distances))

# Only go one tour. Order is 1:(N-1)
node_order = Variable(N-1, integer = TRUE)
ii = t(node_order %*% matrix(1, ncol = N - 1))  # repeat as N rows
jj = node_order %*% matrix(1, ncol = N - 1)  # repeat as N cols

# Constraints
constraints = list(
  do_transition * diag(N) == 0,  # Disallow transitions to self (diagonal elements)
  sum_entries(do_transition, 1) == rep(1, N),  # Exactly one entrance to each node
  sum_entries(do_transition, 2) == rep(1, N),  # Exactly one exit from each node
  (jj - ii) + N * do_transition[2:N, 2:N] <= N - 1,  # One tour constraint (no subtours)
  node_order >= 1,   # This interval represents order as ranks (1 to N-1)
  node_order <= N-1
)

# Find optimum
solution = solve(Problem(objective, constraints))

Unsuccessful attempt

A bit of code pertaining to my current (unsuccessful) attempts:

# Get tour order
#tour = order(c(NA, result$getValue(node_order)))  # R solution
tour = rep(NA, N-1)
tour[result$getValue(node_order)] = 2:N

# Get tour distances
distances_optim = diag(distances[tour, tour[2:N]])

# Tour cumulative distances
distances_cumul = cumsum_axis(distances_optim)

You can easily impose the constraint that a given city should be visited before a given location in the sequence. I.e., that city 5 should be one of the three first visited:

node_order[5 - 1] <= 3

Or that city 7 should be visited as the third, fourth, or fifth:

node_order[7 - 1] <= 5,
node_order[7 - 1] >= 3

This does not exactly impose the constraint on cumulative distance, though.


difference between "addressable" and "address" in memory? I'm struggle on this practice question from this site....

Calculate the number of bits required in the address for memory having
size of 16 GB. Assume the memory is 4-byte addressable.

MY QUESTION IS: what is the difference between an "address" and "the memory is 4 byte addressable"?
I understand an address would be its location in memory that is represented by bits, such as 2^n, where n is the number of bits in the address. But I'm confused about addressable in this question and how that's different than address
2^n * 4 bytes = 2^34
The solution is 32 bits

Address is a label that identifies a memory location. The memory is $4$ byte addressable means that you have labels that refer to memory locations of size $4$ bytes. You don't have names for smaller sizes. For example, if we have a memory of $12$ bytes and the memory is $4$ byte addressable, then we can have $3$ blocks of memory to which we can assign an address. Their addresses could be Memory block 1, The glorious block 2 and Ceres. Instead of fancy long names what is common is for the addresses to be binary numbers. Since there are $3$ addresses, then we need at least $2$ bits.
In your problem, instead of $12$ bytes, you have $16$ GB ${}=2^{34}$ bytes. The memory is $4$ byte addressable. So, we can have $2^{34}/4=2^{32}$ different addresses. So, we need $32$ bits to encode all addresses.


Proof of Minsky Papert Symmetrization technique I frequently hear about the Minsky-Papert Symmetrization technique in many papers with a reference to the book of Minsky. I could not locate the book online. Could someone supply me a proof of the symmetrization technique?

For instance, it is used in Lemma $5$ in this paper http://www.csee.usf.edu/~tripathi/Publication/polynomial-degree-conference.pdf

Over $0/1$ inputs we have
$$
\begin{align*}
(y_1+\cdots+y_N)^0 &= 1 \\
(y_1+\cdots+y_N)^1 &= \sum_i y_i \\
(y_1+\cdots+y_N)^2 &= \sum_i y_i+2\sum_{i<j} y_iy_j \\
(y_1+\cdots+y_N)^3 &= \sum_i y_i+6\sum_{i<j} y_iy_j + 6\sum_{i<j<k} y_iy_jy_k
\end{align*}
$$
And so on. It follows that for $0/1$ inputs, $p_{sym}$ can be written as a linear combination of $(y_1+\cdots+y_n)^0,\ldots,(y_1+\cdots+y_n)^d$, where $d$ is its degree. This linear combination can also be viewed as a polynomial $\tilde{p}$ in $y_1+\cdots+y_n$, which is equal to $p_{sym}$ for $0/1$ inputs.


Longest palindrome substring in logarithmic runtime complexity In a palindrome of size N, the amount of candidates for the longest palindrome is N^2. Therefore, the information theoretic lower bound (IBT) should be lg(N^2), which is equivalent to a runtime complexity of lg(N).

By IBT I mean that if we use a comparison based algorithm and you think about a decision tree to apply it, the leafs of that tree will be all of the possibilities (N^2 leafs), therefore the height of that tree is lg(N^2). However, I was not able to find any algorithm that is able to solve this question in this runtime complexity; the best I have found is Manacher's algorithm that solves the question in linear time.

If a you are given a palindrome $p$ of size $N$ (as you say in the beginning of the question), then the longest palindrome is $p$ itself and you don't need to do any computation.

If your input is not a palindrome but an arbitrary string, then you need to at least read the input and therefore $\Omega(N)$ is a trivial lower bound.


How these two Turing machine problems are different in terms of their decidability? I was referring to slide 4 of this, which states following:

  It is decidable whether a given CFG accepts a non-empty language?

Then I was reading Intro to Automata theory book by Ullman et al. It states following:

  Let $L_{ne}$ be the language of all codes for Turing machines that accept atleast one input string.
  $$L_{ne}=\{M | L(M)\neq \phi\}$$
  $L_{ne}$ is not recursive.

Knowing that "not recursive" is same as "undecidable" and the functionality of Turing machine is expressed as a CFG, I feel that the problems in above two statements sound same and the statements contradicts each other in terms of their decidability claims. Thus, one of them must be wrong. However I also feel that I still miss something basic and both of them are non contradictory and equally true. But then what I miss?

The thing you missed is that Turing Machines are strictly more expressive than Context-Free Grammars. CFGs are as expressive as push-down automata (PDA, i.e. automata with one stack).

E.g. the language $L = \{a^nb^nc^n | n > 0\}$ cannot be expressed by CFG (or decided by a PDA), but can be decided by a Turing Machine.

So, for CFG, the emptiness problem is decidable, but somewhere on the way to Turing completeness, this property is lost.


Efficiently checking if two star graphs are disjoint I have given an undirected graph $G$ with vertex $\{1, ... n\}$ and two star subgraphs $S_1$ and $S_2$, always consisting of ALL neighbors of a given vertex,  and the goal is to check wether the two star graphs have a vertex in common. This will be will be executed $M$ times for $M$ a large integer.

My approach would be to store the graph in adjacency list format and for each vertex store its adjacency list in sorted order.

We can then check in $O(M n \log n)$ time in total if two star graphs of the sequence of $M$ star graph pairs have a vertex in common.

But maybe this can be done more efficiently?

I assume the graph $G$ is fixed, and you are doing $M$ queries on $G$.

Your algorithm takes $O(Mn\log n+t)$ time, where $t$ is the amount of time to build the adjacency list. We can use the same time, but remove the log factor by merging the neighbor of $S_1$ and $S_2$ list in $O(n)$ time.

If $M \in \Omega(n)$, you can just compute the result for all queries in $O(n^2)$ time. Store the result in a new matrix $N$, initially all $0$s. Set $N_{i,j}=1$ for all $\{i,j\}\in \{i|M_{k,i}=1\}$. Thus $N_{i,j}=1$ iff $i$ and $j$ share a neighbor.

If you query for star $S_i,S_j$, it returns $\max(N_{i,j},M_{i,j})$, if it's $0$, then there is no common vertex for the stars.

It takes $O(M+n^2)$ time and $O(n^2)$ memory.


$\beta$ reduction equational equality In Categories, Types and Structures, authors talk about exponential objects in section 2.3.1.

  Let $C$ be a Cartesian category, and $a,b \in Ob_C$. The exponent of $a$ and $b$ is an object $b^a$ together with a morphism $eval_{alb}: b^a \times a\rightarrow b$ (evaluation map), and for every object $c$ an operation $\Lambda_c : C[c\times a,b]\rightarrow C[c, b^a]$ such that for all morphisms $f: c\times a\rightarrow b$, $h:c\rightarrow b^a$, the following equation holds:
  $\beta. eval_{a,b} \circ (\Lambda (f)\times id_a )=f$
  $\eta. \Lambda_c(eval_{a,b}\circ(h\times id_a))=h$

Can you please show me the steps to derive the last two equations?

The following morphism and commuting morphisms explain why those two equations hold:

$h:c\rightarrow b^a$

commuting morphisms:

$eval: b_a\times a\rightarrow b$
$f:c\times a\rightarrow b$
$h\times id: c\times a\rightarrow b^a\times a$


Is $L = \{\langle M, w \rangle: \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$ decidable? I'm trying to find whether

$$L = \{\langle M, w \rangle: \exists q.\ \text{on input}\ w\ M\ \text{doesn't pass through a state}\ q\}$$

is decidable or not.

I don't know how to proceed here. I mean, I have the feeling that I have to know which state $q$ the machine $M$ 'skipped' in order to go ahead. For instance if $q = \text{Accept}$, it means that $M(w) = \text{Reject}$ and I guess that, in this case, $L$ can be shown to be a reduction from $L_{empty}$ (written also $E_{TM}$). So if we assumed that $L$ was decidable $\implies E_{TM}$ is decidable which is not true.

But what about the case where $q \neq \text{Accept}$ state?

You can prove that $L$ is undecidable using a diagonal argument: Assume $M$ decides $L$. Then, define $\tilde{M}$ as follows: On input $x$, run $M$ on input $\langle x, x \rangle$. If it accepts, go through all states and then halt; otherwise halt without going to some dedicated state $q_0$.

If you now run $\tilde{M}$ on input $\tilde{M}$, it runs $M$ on input $\langle \tilde{M}, \tilde{M} \rangle$. Since $M$ decides $L$, it accepts if and only if $\tilde{M}$ on input $\tilde{M}$ does not go through some state. This contradicts the construction of $\tilde{M}$. Hence, $L$ is not decidable.


Is there a way to calculate exactly how many binary trees are possible if only one of the preorder, inorder and postorder traversals is given? I am studying tree traversals and I've got to know that we can uniquely determine the binary tree if their:

Case 1. Preorder & inorder traversals are given or

Case 2. postorder & inorder traversals are given

We can not determine the tree if only one of the traversals are given because there will be finitely many trees possible.

My question is that, is there a way to calculate the number of trees possible?

Your question probably assumes that the nodes of the tree all contain different values. If we have a tree with $n$ nodes all of whose have the same label $x$, then we can't tell what tree we're looking at by observing the traversals, as we always get just a series of $x$'s, independent of what the tree shape is or what traversal we use. So I assume the labels are all different.

Use the traversal to generate a list of all the elements of the tree $[x_1, \ldots, x_n]$. Now, which trees are possible with this particular traversal? Pick any tree with $n$ elements and place the labels $x_i$ into the nodes so that for that tree you'll get them back in the order $[x_1, \ldots, x_n]$. This shows that, if we only have one of the traversals available, any tree shape is possible, as long as it has the correct number of nodes $n$. So the answer is that there are $C_n$ such trees, where
$$C_n = \frac{1}{n+ 1}{2 n \choose n}$$
is the $n$-th Catalan number.


Creating an K-nary tree that is balanced in both width and depth for N nodes. N known a priori Given N items you want to put into a tree, think very generally here like a phone tree, and your goal is to keep the tree from getting "too wide" and "too deep". How many children (K) do you put at each node?

I seem to recall hearing of some proof, many years ago, K was best when set to Euler's number. Therefore in real applications if you must choose a single number you pick 3 children and the tree should end up closely balanced between depth and width. In other words, binary trees tend to be too deep, and 5-trees are "too wide".

Some searching of the 'net and reading some tree designs on Wikipedia has not proved fruitful but perhaps I am dreaming up a false memory?

This sounds as follows.

The answer is that the optimal number of children in a tree is $e$. What was "optimal" in the question?

One such question is as follows.

Let us construct a tree of $N$ nodes.
Imagine we arrange them into a perfect $K$-ary tree with $L$ levels of internal vertices.
When we search over such tree, assume that the worst case is that we visit $K$ vertices in each of the $L$ internal levels, making the search $O (K \cdot L)$.
What is the optimal $K$ as $N$ tends to infinity?

Here, we select $K$, and then $L$ is computed as $log_K N$.

When we think about it a bit, here is an arithmetic rephrase.

We have a number $N$.
We want to express some integer $M \ge N$ as a product of integers $S_1 \cdot S_2 \cdots S_L$ so that the sum $S_1 + S_2 + \ldots + S_L$ is minimal possible.
When $N$ tends to infinity, what will be the sequence $\{S\}$?

The values $S_1, S_2, \ldots, S_L$ are the number of children at levels $1, 2, \ldots, L$, respectively.
If we had a perfect $K$-ary tree, all our $S_i$ would be equal to $K$, but we lifted the restriction that they are all equal: the essence of the solution remains the same.

When we don't insist that $N$ and $S_i$ are integers, after performing some basic calculus, we can see that the optimal answer is to pick all $S_i$ close to $e$.
Note that the closest integer to $e$ is $3$.
So for the integer version, the optimal answers turn out to be of the following forms:
$$(3 \cdot 3 \cdots 3)$$
$$(3 \cdot 3 \cdots 3) \cdot 2$$
$$(3 \cdot 3 \cdots 3) \cdot 2 \cdot 2$$


NP-hard in what parameter? I often read statements such as "the run-time of algorithm X is polynomial in m and n". Indeed, when a problem has two parameters, it is possible that the run-time of an algorithm is polynomial in one parameter but not the other one, so if this is not the case, it is important to emphasize that it is polynomial in both parameters.

However, I have never read a statement such as "the problem is NP-hard in m and n". A problem is always claimed to be NP-hard, period. My first question is: why? Apparently the same rationale is true here too: a problem may be NP-hard in one parameter, but at the same time, it may have an algorithm with run-time polynomial in the other parameter.

My second question: what is an accurate description of a problem with two parameters: $m$ and $n$, that (1) for a fixed $m$, can be solved in time polynomial in $n$, (2) for a fixed $n$, it is NP-hard (with respect to $m$)?

A problem is always claimed to be NP-hard, period.

Indeed, a problem's definition already contains a specification of its parameters. (See the entries in Richard Karp's seminal collection of NP-complete problems for several examples.) Usually, there is no need to make explicit reference to the parameters per se, as they are "automatically scaled" by the input length; for your two parameters $m$ and $n$, for instance, the input could simply be encoded as $0^m1^n$. Hence, for abstract problem instances, it usually suffices to refer strictly to the input length, which is indeed how time complexity is defined (i.e., as the number of computation steps as a function of the input length).

Studying how different requirements on the parameters impact the problem's complexity is the object of study of parameterized complexity theory. For example, the set of SAT formulas with $k$ many variables, $k$ being a fixed parameter (i.e., constant), is decidable in polynomial time (in the formula's length); in parameterized complexity terms, this means SAT is fixed-parameter tractable. It is only as the number of variables is also allowed to scale (in the input length) that SAT becomes NP-hard.


Proof that the language $ww^R$ is not regular without using the pumping lemma I am breaking my head over this. Let the alphabet $A$ be given by
$A = \{a,b,c\}$ and let

$$L = \{ww^R \mid w \in A^* \}.$$

Prove that the language $L$ is not regular without using the pumping lemma, but using:

The fact that $\{a^nb^n \in A^* \mid n \geq 0 \}$ is not regular.
The fact that $\{w \in A^* \mid w \text{ is a palindrome} \}$ is not regular.
Closure properties of the class of regular languages (such as if $L_1$ and $L_2$ are regular, then $L_1 \cup L_2$ is also regular, etc.).

Let

$$ L_1 = \{\ \omega\omega^r \ | \ \omega \in \Sigma^* \} $$
$$ L_2 = \{\ a^nb^n \ | \ n \in \mathbb{N}\ \}$$

Because $\Sigma = \{a, b, c\}$ is finite, $\Sigma^*$ must be countable.

This means we can define a function $f : \Sigma^* \rightarrow \mathbb{N}$ which returns the position of a word $\omega \in \Sigma^*$ in an arbitrary ordering defined by $f$. $f$ is invertible, we define $f^{-1} : \mathbb{N} \rightarrow \Sigma^*$, which returns the word $\omega$ at position $n$ in the enumeration of $\Sigma^*$ as defined by $f$.

Now, since every word $\omega$ is uniquely defined by a natural number $n$, and every word $\omega$ has exactly one unique reverse $\omega^r$, we can define an isomorphism between $L_1$ and $L_2$:

$$ g \colon\  L_1 \rightarrow L_2; \quad \omega\omega^r \mapsto a^{f(\omega)}b^{f(\omega)} $$

$$ g^{-1} \colon \ L_2 \rightarrow L_1; \quad a^nb^n \mapsto f^{-1}(n) f^{-1}(n)^r $$

Since $L_2$ is not regular and we have a bijection between $L_1$ and $L_2$, $L_1$ must not be regular.

This proof works for any finite alphabet $\Sigma$ because the transitive closure of a finite alphabet is always countable.


Information on Tavori and Dreizin ranged hash function? While doing some digging around in the GNU implementation of the C++ standard library I came across a section in bits/hashtabe.h that refers to a hash function "in the terminology of Tavori and Dreizin" (see below). I have tried without success to find information on these people, in the hopes of learning about their hash function -- everything points to online versions of the file that the following extract is from. Can anyone give me some information on this?

*  @tparam _H1  The hash function. A unary function object with
*  argument type _Key and result type size_t. Return values should
*  be distributed over the entire range [0, numeric_limits<size_t>:::max()].
*
*  @tparam _H2  The range-hashing function (in the terminology of
*  Tavori and Dreizin).  A binary function object whose argument
*  types and result type are all size_t.  Given arguments r and N,
*  the return value is in the range [0, N).
*
*  @tparam _Hash  The ranged hash function (Tavori and Dreizin). A
*  binary function whose argument types are _Key and size_t and
*  whose result type is size_t.  Given arguments k and N, the
*  return value is in the range [0, N).  Default: hash(k, N) =
*  h2(h1(k), N).  If _Hash is anything other than the default, _H1
*  and _H2 are ignored.

Ami Tavory, Vladimir Dreizin (IBM), and Benjamin Kosnik (Red Hat) authored the "Policy-Based Data Structures" library. Ideas developed there were later used in the GNU implementation of the C++ standard library.
Link-only answers are typically discouraged, but let me post the link here anyway because it is not discoverable with Google in a simple way:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/
In particular, range hashing approach is described here:
https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/hash_based_containers.html


How to partition a tree on a fixed budget of edge cuts? Suppose I have a tree $T=(V,E,w)$ with vertex weights $w(v)\ge 0$ for all $v\in V$.  I want to partition this tree into $k+1$ trees by cutting $k$ edges such that the deviation from the mean of the sum of vertex weights in each partition is minimized.

Is there an algorithm to get a good approximation in polynomial time?

Literature research has yielded this method finding a partitioning with bounded partition size, but it doesn't seem to adapt readily to the desired fixed number of cuts.  Likewise, there is a lot of research on tree partitionings where multiple subtrees can be placed into one partition, an NP-hard problem.  This doesn't seem relevant either as each partition must be a single subtree in my case, significantly changing the problem. This question seems to ask the same question I ask but doesn't specify what kind of partitioning is optimal.  The dynamic program given in this answer would work for the unweighted case, but my graph is weighted, so it doesn't apply.

There is a straightforward dynamic programming algorithm to find the exact answer whose running time is something like $O(nk^2t^2)$, where each partition's total weight is about $t$.  This is far too slow for your parameter settings.

To get an approximation, one trick is to pick a parameter $r$ and divide every weight by $r$ and then round to the nearest integer.  Then, you have a new instance where the weights are much smaller, and you can find an exact solution to this using dynamic programming.  That will then be an approximate solution to the original problem -- not necessarily the optimal answer, due to rounding, but it might get close.

When rounding, you might get some improvement by using randomized rounding.  For example, if the division gives you a number like $2.7$, you flip a biased coin; with probability $0.7$, you round this to the integer $3$, and with probability $0.3$, you round it to the integer $2$.

There may be better solutions, but this is one simple thing you could try.


Variable derives itself In Sipser's Introduction to the theory of computation (3rd edition), I found the following claim.

Consider the grammar:

$$
\begin{align*}
&R \to XRX \mid S \\
&S \to aTb \mid bTa \\
&T \to XTX \mid X \mid \epsilon \\
&X \to a \mid b
\end{align*}
$$

In this grammar, it holds that $T \Rightarrow^* T$.

Can anyone explain how this is true?

We say that $\alpha \Rightarrow^* \beta$ if $\beta$ can be derived from $\alpha$ in zero or more steps. (More fancily, $\Rightarrow^*$ is the reflexive-transitive closure of $\Rightarrow$.) In particular, it is always that case that $\alpha \Rightarrow^* \alpha$, for every $\alpha$, due to a derivation of zero steps.

In contrast, in your case it doesn't hold that $T \Rightarrow^+ T$. (This is derivation in one or more steps, or the transitive closure of $\Rightarrow$.)


Rice's theorem vs Turing completeness I would like to clarify this because I see some kind of contradiction between Rice's theorem and Turing completeness.

This is the problem:

In building an Universal Turing Machine to emulate another Turing Machine, how can we be sure that we are indeed simulating it? ('sure' in the sense of being computationally verified by an algorithm). So I get confused, the problem I found is that Rice's theorem apparently tell us that we can not verify this computationally.. Is not "to emulate" an extensive property?.This lead me to think we could not prove the Universal Turing Machine is doing what it's supposed to do..

EDIT

To expand the topic

I want to expand this point, what I understood from given answers, is you can state that a specific Machine is Universal but not that an arbitrary machine is (nor a family of machines are universal), ok, but I don't ask for arbitrary!, nor a family, but to test algorithmically a single fixed machine. Test, like measuring, is against something, It's hard to think a computer concept without having something to compare with, and according to answers, completeness of a machine seems as something that can't be compared.

How universality is proven? let's say by showing 'look mom I am simulating a TM', so, as she believes TM are universal, then your machine is also universal, but, she can't verify it!, she must believe you because she can't test that single machine you made, not by an algorithm, so that's why I see Rice's theorem rubs against completeness, there is no algorithm to test two fixed machines are doing the same computation.

So what can "universal" mean?, it's seems like saying, your software is doing what you mind, because is written in a Turing Complete language!. 'This is emulating a machine because it can'. I think that's not enough.

Your misunderstanding is:

  'sure' in the sense of being computationally verified by an algorithm

We are not, and we can not be . The question,

  Is this given Turing machine $M$ a universal one?

can not be generally and algorithmically decided for the reasons you state.

However, we can prove for a fixed Turing machine that it is universal -- and that is quite enough.