Average Case Complexity Rivisted I got confused with the analysis of algorithms in average case. Following is the my perception regarding average case using sorting problem:

  Suppose we have a 5 elements array to be sorted using Insertion sort.
  Time complexity will depend upon the particular arrangements of
  elements in the array. Usually, when algorithm's time complexity
  depends upon the particular ordering of elements or different instances of same
  problem size n, then different cases (i.e. best, average and worst)
  occurs. In the above example there are 5!=120 possible instances of
  problem size 5. For a instance, when elements are already sorted,
  algorithms takes lowest time, and that will be best case. For another
  instance, when elements are reverse sorted, it takes longest time, and
  that will be worst case. there are still 118 instances left. For
  average case time complexity, we should take average of running
  times for all possible input instances (including 118 left and 2
  others). That means we should take average of all 120 running time for
  different 120 instances.

Why probability distribution plays a role while computing average case time complexity? Why don't we just take a simple average of running times for all possible input instances of same problem size?

If the distribution on input instances is uniform, then the two are equivalent.  Talking about a distribution has two potential advantages: (1) it allows us to analyze the algorithm using the tools of probability theory, which can sometimes be useful, (2) it allows us to meaningfully talk about average-case running time for a non-uniform distribution on inputs.


Counters in Turing machines I know how a Turing machine works, how it accepts a language but in some.

In some scenarios we would like to use counters.
For example, I want to develop a machine that accepts $\{0^{2n} : n \geq 0\}$. How can I count the number of zeroes?

If some one of you could solve the following problem for me it would help my understanding of these matters:

  Design a Turing machine for $L = \{1^{3^n} : n \geq 1\}$.

Well, you could just implement a counter.  I'll assume that the tape alphabet is $\{0,1,\#\}$.

First, scan to the end of the input, and write $\#0$ to the tape after the last character. The string of zeroes and ones after the $\#$ will be a binary counter.

Second, convince yourself that a Turing machine can add one to a number in binary.

Third, peform the following until you run out of input.  Scan back to the first $1$ on the tape, replace it with a $\#$, scan back to the counter and add one to it.

Finally, when you've run out of input, check that the value of the counter is a number of the required type. For example, it has the value $2^k$ for some $k$ precisely if it matches the regular expression $10^*$. For $3^k$, you can either convince yourself that Turing machines can divide a binary number by $3$ or – easier! – keep your counter in ternary instead of binary.


Clarifying $\sum_{h=0}^{\lfloor lg(n)\rfloor}\lceil\frac{n}{2^{h+1}}\rceil O(h)=O(n\sum_{h=0}^{\lfloor lg(n)\rfloor}\frac{h}{2^h})$ in BUILD-MAX-HEAP I was going the text Introduction to Algorithms by Cormen et. al. Where I came across a step in the analysis of the time complexity of the $BUILD-MAX-HEAP$ procedure.
The procedure is as follows:
BUILD-MAX-HEAP(A)
1   heap-size[A] <- length[A]
2   for i <- ⌊length[A]/2⌋ downto 1
3       MAX-HEAPIFY(A,i)

Now the authors claim to derive a tighter bound by observing that the time for $MAX-HEAPIFY$ to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. The tighter analysis relies on the properties that an $n$-element heap has height $\lfloor lg (n)\rfloor$ and at most $\lceil \frac{n}{2^{h+1}} \rceil$ nodes of any height $h$.
So,$$\sum_{h=0}^{\lfloor lg (n)\rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h)= O(n \sum_{h=0}^{\lfloor lg (n)\rfloor} \frac{h}{2^h})  \ldots \tag 1$$
Now it is in the above step that I am facing the problem. How are the authors getting the expression on the RHS using the LHS so simply(as if intuitively). However I do not seem to share the same intuition.
Now the maximum height of any node is the height of the root which is $\lfloor lg (n)\rfloor$. Now let us find a bound for the minimum possible value of the fraction $\frac{n}{2^{h+1}}$ ,which occurs when $h=\lfloor lg (n)\rfloor$
So, $$\frac{n}{2^{\lfloor lg (n)\rfloor+1}} = \frac{n}{2.2^{\lfloor lg (n)\rfloor}}\geqslant\frac{n}{2.2^{lg (n)}}=\frac{n}{2n}=\frac{1}{2} \ldots \tag 2$$
Now from the analysis step by the authors in (1) they are assuming
$$\lceil \frac{n}{2^{h+1}} \rceil \leqslant c.\frac{n}{2^h}, c>0 $$
Now as far as I know from mathematics,
$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1$$
And for the way the authors worked out , it must be the situation as below,
$$\lceil \frac{n}{2^{h+1}} \rceil \lt \frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$
So, $$\frac{n}{2^{h+1}}+1 \leqslant c.\frac{n}{2^{h}}$$
$$\iff 1 \leqslant c.\frac{n}{2^{h}}-\frac{n}{2^{h+1}}$$
$$\iff 1 \leqslant \frac{n}{2^{h+1}}(2c-1)$$
$$\iff \frac{n}{2^{h+1}}\geqslant \frac{1}{2c-1} \ldots \tag 3 $$
Now for (3) to comply with (2) we should have,
$$2.c-1 \geqslant 2 \iff c \geqslant \frac{3}{2}$$
Now is that single line in (1) worth this much effort or is it the situation that the step is trivial or intuitive that we can just mentally do the step. If it is the latter, please enlighten me with such intuition..
Even in this answer here that $\frac{n}{2^{h+1}}\lt\frac{n}{2^{h}}$ is intuitive but that $1\lt\frac{n}{2^{h}}$ is not quite intuitive and requires the use of (2) I feel

Since $h \leq \lfloor \lg n \rfloor$, we have $2^h \leq n$, and so $n/2^{h+1} \geq 1/2$. Therefore
$$
\left\lceil \frac{n}{2^{h+1}} \right\rceil \leq
\frac{n}{2^{h+1}} + 1 =
\frac{n}{2^{h+1}} + 2 \cdot \frac{1}{2} \leq
\frac{n}{2^{h+1}} + 2 \frac{n}{2^{h+1}} = 3 \frac{n}{2^{h+1}}.
$$
(In fact, if you are more careful then you can replace $3$ by $2$.)
More generally, if $x \geq c > 0$ then $\lceil x \rceil  = O(x)$, where the hidden constant depends on $c$.


Is true that $L_1 = \{01^*0\}$ is $m$-complete in the class of decidable languages? Question:

  Is true that $L_1 = \{01^*0\}$ is $m$-complete in the class of
  decidable languages?

  $L_1$ is defined as:

  $$L_1 = \{01^*0\} := \{01^n0: n \in \mathbb{N}\}$$

Definition of a $m$-complete language:

  A language $L^*$ is $m$-complete in the class of decidable language,
  if for any decidable language $L$ we have that $L \leq_m L^*$ (that
  is, $L$ reduces to $L^*$).

I'm really new in this realm, so I'm quite lost about how to tackle this exercise.

I'm not sure if my approach is correct but I was trying to prove that the statement is not true by using a reduction from the Busy Beaver Function to $L_1$ (then, from this reduction and from $L_1$ being decidable we would have that BB problem is decidable, which is not possible).

Let $A$ be the algorithm deciding $L_1$ and $w \in L_1$ a word with $|w| = m$ ones. Now when running $A$ on $w \in L_1$ we keep track of the number of steps $t$ it made just before halting. Since $t = m|\Gamma|^m|Q|$, where $\Gamma$ is the set of tape symbols and $Q$ is the set of states. From here we can find the number $|Q|$ of states required for printing $|w| = m$ ones...

I stopped here because I feel there is already something wrong.

First, even is we find that number $|Q|$ for which $A$ performed $t$ steps before $A(w) = \text{Accept}$, that does not necessarily mean that $|w| = m$ ones could have been achieved with a TM with lesser number of states. Second, ''knowing'' the numbers of ones I'm determining the numbers of states and not the other way around, which is as $BB$ is defined.

Another alternative I was exploring was, on input $w$, to run all TM's $T_1, ... T_n$, that return $|w| = m$ ones. Then we record the input $w$ and the description of the machine $T_i,\ (i \in [1,n])$, that had the least number of states. If we do this $\forall w \in L_1$, we end up with a UTM $T'$, such that:

$$T' = \{ \langle T^*, w\rangle: |Q|_{T^*} = \mathrm{min}(|Q|_{T_1}, ..., |Q|_{T_n}\ \text{}\}$$

Then clearly $T'$ decides $L_1$ (just have to run it on input $w \in L_1$) and at the same time allows us to compute $BB(n)$ for a fixed $n \in \mathbb{N}$ (since $n$ is encoded in the description of $T^*$).

Probably here there are some flaws in my reasoning, but in this case, do I have to wait that, on input $w$, all those TM's reach a halt or can I assume that the first machine that halted is the one with the least number of states?

I'd appreciate any help.

Your approach can't succeed. You're asked whether every decidable language reduces to $L_1$ but your approach is to try to show that some undecidable language doesn't reduce to it. That would show nothing about decidable languages.

But are you sure that your definition is correct? Every language except $\emptyset$ and $\Sigma^*$ is $m$-complete by the definition you give.


Finding all subsets of a set of MultiSets made of elements from a single MultiSet (without replacement) (originally asked on StackOverflow)

Two recent questions on StackOverflow by the same author1 are generally solved by the same technique.  This feels to me like it would be a studied and perhaps well-solved problem.
I would like to know what it might be called and where to find more information about it, assuming it is a well-known problem
This is my own phrasing of the question:
If we have a Set, $M$, of MultiSets, $M_1$ - $M_n$ made up of elements of Set $S$, and we have a MultiSet of components, $C$, also drawn from $S$, how do we find all subsets of $M$ such that the for each subset, the multiplicities of each element of $S$ in its union is no greater than the multiplicity of that element in $C$ ?2
For example, paraphrasing my own answer to the first question:

I think I understand that what you want would be for something like this:
const catalog= ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]
const components = ["a", "b", "a", "c", "d", "e"]

simultaneousItems (catalog, components)

to yield
[
  ["ad", "ace"], ["ad", "ba"], ["ad"], ["aab", "cd"], ["aab"], ["ace", "ba"],
  ["ace", "bd"], ["ace"],["cd", "ba"], ["cd"], ["ba"], ["bd"], []
]

where every array in the result is subset of catalog items that can be made together out of the components supplied.  So, for instance, none of the output arrays contains "adf" or "def", since we have no "f" in the components, and none of them contain both "ad" and "aab" since we only have two "a"s in the component list.

Note that I'm using "abc" as a shorthand for the set containing the strings "a", "b", and "c".
The original problems seemed to be looking for maximal subsets, so there is one additional step, and that is perhaps an equally interesting problem, but I'm more curious about the version above.
Please don't look at my solution as any sort of algorithmic ideal.  It was the first idea that came to mind.
Is this a well-known problem?  There's some vague relationship to the Knapsack problem, and other packing problems, but I can't quite figure out what and where to search.

1 The first one is closer to what I think is the fundamental algorithmic question.  I'm assuming the second one is closer to the real problem the OP is trying to solve.  Without any feedback yet from the OP, I don't know for certain that my answers match the real need, but I find this an interesting question regardless.
2 More explicitly (and forgive me for being too far away from formal Math classes) if $C$ = ${\{S_1^{m(z_1)}, S_2^{m(z_2)}, ... S_j^{m(z_j)}\}}$ for some integer $j$, and $S_1$, $S_2$, ... $S_j$ in $S$, and if $N$ = ${\{M_{a_1}, M_{a_2}, ... M_{a_k}\}}$ is one of the subset of $M$ in the result, and ${∪\{{M_{a_1}, M_{a_2}, ... M_{a_k}}\}}$ = ${\{S_1^{m(x_1)}, S_2^{m(x_2)}, ... S_j^{m(x_j)}\}}$, then for all $i$, $x_i$ ≤ $z_i$.

This problem (at least assuming you wish to find some sort of maximal subset) is simply the multidimensional knapsack problem, see e.g. "The Multidimensional Knapsack Problem: Structure and Algorithms" by Jakob Puchinger, Günther Raidl, Ulrich Pferschy.
To read that paper in your terminology, a quick translation.
Your 'components' are known as resources, their multiplicities as capacities. The $i$th resource $S_i$ has capacity $c_i$. Each of your multisets $M_j$ is an item, and it consumes $w_{ij}$ of the $j$th resource. Thus $w_{ij}$ is the multiplicity of $S_i$ in $M_j$.
Finally in the optimization version that's studied in the linked paper we wish to know the most profitable solution. In this context each of your multisets $M_j$ (AKA items) has an associated profit $p_j$. The paper selects $x_j \in \{0, 1\}$ to determine whether item $j$ is part of the optimal solution, and thus solves the following problem:
\begin{align}
\text{max }\;\; & z = \sum_{j=1}^n p_jx_j\\
\text{s.t. }\;\; &\sum_{j=1}^nw_{ij}x_j \leq c_i, \quad i =1,\dots,m,\\
           &x_j\in\{0, 1\},\quad j = 1,\dots,n.
\end{align}
Note that the paper uses $m$ as the number of components/resources and $n$ as the number of multisets/items.


Can a CD disk and the memory of a device have an infinite space storage? I’m asking this because, I’m thinking that it is possible to make a CD or ps vita cd to have an infinite space storage so that new updates will come.

And, it is possible for the company Sony to make the new memory of ps vita to be infinite space storage?

Can anyone tell me if it is possible for a company to do that?

Out of curiosity.

Sorry if I have asked in a wrong site and for adding this tags, you can edit this post.

This is impossible.

Storing information requires physical space and there is a limit. This might seem somewhat obscured by the fact that we can store a lot of information in a small space, by the technological process which brought us smaller and smaller storage devices and by other factors which make the relationship between information and space less clear (e.g. a 700MB CD and a 50GB Blu-Ray disk have the same volume).

The limit on how much information can be stored is given by the Bekenstein bound:

$I \le \frac{2 \pi c R m}{\hbar ln2} $

$I$ is the information quantity that can be stored in a sphere with radius $R$ and mass $m$.

In short, you need an infinite amount of space to store an infinite amount of information, but a CD has a finite volume.


Master theorem for $T(n)=T(n-1)+O(n)$ The recurrence of selection sort is $$T(n) = T(n-1)+ O(n).$$ Can we apply the master theorem to this recurrence? I am confused because the master theorem can be applied to the following recurrence

$$T(n) = aT(n/b) + f(n),$$

where $a \ge 1$ and $b > 1$. But for selection sort, $b=1$. I am trying to apply the master theorem and stuck.

The master theorem isn't the appropriate theorem for every recurrence. As an example, your recurrence isn't of the type tackled by the master theorem, though it is easy to solve directly using the well-known identity
$$ \sum_{i=1}^n i = \frac{n(n+1)}{2} = \Theta(n^2). $$
You should think of the master theorem as a tool, not a liability. It is supposed to help you – use it if you need it, but feel free to use any other approach as you see fit. The only cases you absolutely have to apply the master theorem is when answering questions on a homework or a test that say you must use it; in the real world one tends not to limit oneself.


Big O: Analyzing the time complexity of an $O(n \log n)$-algorithm For homework, the task is to verify the time complexity of quicksort. User Nick suggested on quora that one could check the number of comparisons made when doubling the input size. If the comparisons increase by a factor of around 2, we verify that quicksort has $O(n \log n)$ time complexity.

Is this a legitimate method to verify the time complexity?

Let's denote by $C(n)$ the number of comparisons performed on an input of length $n$ (later on I will comment more on this definition). The assumption that the number of comparisons roughly doubles when doubling the input size translates to $C(2n) \approx 2 C(n)$. This is not a precise statement, so let us take it to mean that
$$
\lim_{n\to\infty} \frac{C(2n)}{C(n)} = 2.
$$
There are many functions satisfying this statement. Some examples are $n (\log n)^k$, for any value of $k$. This condition cannot distinguish between algorithms with a linear number of comparisons and those with $n\log n$ or $n\log^2 n$ comparisons, and in particular cannot imply that quicksort uses $O(n\log n)$ comparisons.

Let $D(n) = \log[C(n)/n]$, so that
$$
\lim_{n\to\infty} [D(2n) - D(n)] = 0.
$$
What we can conclude is that $D(n) = o(\log n)$, which translates to $C(n) = n 2^{o(\log n)}$.

Another problem with your analysis is that the number of comparisons could depend on the input, not only on the input size. In other words, $C(n)$ is not well-defined. It is known that quicksort has worst case number of comparisons $\Omega(n^2)$, but the average number of comparisons (over a random permutation) is only $\Theta(n\log n)$. We usually take $C(n)$ to be either the worst case number of comparisons or the average number of comparisons (for a random permutation).

Yet another problem is that it's not clear how to establish $C(2n)/C(n) \to 2$. Is this the result of an experiment, a heuristic calculation, or a formal proof? You don't make it clear. Experiments might show that $C(2n) \approx 2C(n)$ for small $n$, but the asymptotic behavior might be different; $C(2n)/C(n)$ might grow slowly, but eventually tend to infinity, for example.


Would models of computation in other conceivable universes be Turing complete? I'm interested in gathering some references that discuss the topic of the relationship between computation and physics.

Specifically, I'm interested in investigating two points of view:

our current model of computation -- assuming it describes reality accurately -- impose a limit on what is physically possible. To me this is essentially the argument that Max Tegmark makes with his Mathematical Universe Hypotheses
the physics of our universe put limits on our models for computation. Are the limits of our models for computation a direct consequence of the laws of physics?

It seems to me that these two points of view are not the same, however I lack the necessary background to really tell. I know about Tegmark but I don't know any references on the second point of view.

I am aware of the physical limits of computation in the sense that there are the limits of how fast computers can run, or how small we could theoretically build them; however, our models of computation are substrate independent and their fundamental limits are not imposed by physical properties like speed, or scale. The limits more fundamental, e.g., undecidability, the halting problem.

I wonder if these type of limits of our models are a consequence of the structure of brains, i.e. their physical properties.

Perhaps this question is ill-posed but I'm only looking for reading materials so I can hopefully formulate better questions.

The study of models of computation  extremely broadly construed is called "generalized recursion theory" (or "higher recursion theory," or "generalized/higher computability theory," or etc.). We can indeed rigorously define and study (from a theoretical standpoint of course) models of computation much stronger than what is "physically implementable" in even an ideal sense (according to our current understanding of physics). Some of these include:

Metarecursion theory, which develops an analogy between "computably enumerable" and "$\Pi^1_1$" (and extends to descriptive set theory by developing an analogy between "computably enumerable" and "coanalytic," and is further generalizable e.g. by Spector classes and Q-theory).
$\alpha$-recursion theory, where we shift from computing in the context of $\mathbb{N}$ to computing in the context of more complicated infinite sets with nice properties (and $\beta$-recursion and admissible recursion theory, which generalize $\alpha$-recursion in different directions).
Infinite-time Turing machines, which ... are basically exactly what they sound like.
Ordinal register machines, which are like infinite-time Turing machines but even more so; roughly, they're the analogue of Turing machines when we replace $\mathbb{N}$ by the class of all ordinals.
Kleene recursion, where we look at computations of "higher type" objects generally allowing the use of "lower type" objects (and their "equality predicates") as parameters.
Recursion over general structures, which is too broad to have a single name; see e.g. Blum-Shub-Smale machines (which really are a special case of previously-existing notions) or this book by Moschovakis.

There are also models of computation stronger than Turing machines which are based on "idealized" versions of phenomena which, while extremely exotic, are (somewhat) consistent with our current understanding of physics -  e.g. Malament-Hogarth.

Moreover, we can prove abstract results applicable to all models of computation satisfying some very basic properties. For example, the unsolvability of the halting problem generalizes to any situation where we have a notion of "universal machine." (Of course anything we can conceive has to be "permitted" by the laws of physics to which our physical brains are subject, but my point is that these limits are quite loose: we can conceive of blatantly un-physical objects.)


Finding pairs of vertices which would disconnect a graph An assignment question asks,

  Given a connected, undirected graph $G$, describe an algorithm which can determine if the removal of any pair of vertices would cause $G$ to become disconnected.

There is an obvious brute force solution, which is to just generate all pairs of vertices, produce new graphs with those vertices removed, and then test if that graph is connected using something like a BFS, running in $O(|V|^3)$ time.

However, I feel like this is not the intent of the question. We learned about an algorithm to find the articulation points of a graph, and it seems like something like this should be possible to determine if the removal of any pair of vertices would disconnect the graph, but I am not sure how it would be applicable.

Assume that $G=(V,E)$ does contain any articulation point (otherwise the answer is easy).

One simple approach that requires $O(|V| \cdot |E|)$ time is that of computing the articulation points of $G-v$ for each $v \in V$.

If you find any articulation point $u$ then removing the two of vertices $\{u,v\}$ disconnects the graph.

In practice this amounts to running the depth first search needed to compute the articulation points of $G-v$ on $G$, while ignoring the edges to $v$.


Maximum Flow in a Network Let $N = (V, E)$ be a network in which the capacity of each edge is either $12$ or $18$.

Prove or disprove:
The value of a maximum flow for $N$ can’t be $56$.

I'm trying to figure out how to definitely prove this.
I think that this is not possible because of no combination of $12X + 18Y$ (where $X$ and $Y$ are integers) will ever $= 56$. Is there a better way of saying this?
Am I right to say that an integer solution to $12X + 18Y = 56$ is what the Fold-Fulkerson algorithm implies?

By the max flow min cut theorem, the maximum value of a flow equals the minimum capacity of a cut. The capacity of a cut is of the form 12x+18y, which can’t equal 56 because 56 is not a multiple of 6.


Should you use Genetic algorithm for an extremly large unstructured search space? My search space is discrete and in the order of $10^{1360}$, with a probably very complex fitness surface. Is it hopeless to attempt to use GA for such a problem? One fitness evaluation could take 1-3 minutes per candidate solution.

No.  Just knowing the size of the search space is not enough to tell whether GA will work or not.  It also depends on the objective function (the "shape" of it), e.g., whether it is smoothly varying or not, how many local minima it has, and so on.

There is no good theory to know whether GA will work or not.  Ultimately, all you can do is try it and see.

As a side note: Generally speaking, for most problems, other approaches tend to do better than GA.  This is not a theorem; it's just experience / a rule of thumb that seems to often hold.


$\mathbf{NC_2}$ is closed under log-space reduction I actually have to prove the following :

$\mathbf{NL} \subseteq \mathbf{NC_2}$

I have the following approach :

I will prove that $\mathbf{PATH} = \{〈D, s, t〉 | \text{D is a directed graph with a path from vertex s to t}\} \in \mathbf{NC_2}$.
I will show that $\mathbf{NC_2}$ is closed under log-space reductions i.e:

$$(1): B \in \mathbf{NC_2} \hbox{ and } A \le_l B \Longrightarrow A \in \mathbf{NC_2}$$

where $\le_l$ is the logspace reduction defined as

$$A \le_l B :\Longleftrightarrow (\exists M \hbox{ TM}, \forall x)[x \in A \Longleftrightarrow M(x) \in B]$$

($M$ is a TM which runs in logarithmic space).

Since $\mathbf{PATH}$ is an $\mathbf{NL}$-complete problem the proof will be done.

Proving The 1st part was easy, i am stuck at the second part and have no idea how to proceed.

Any help?

We want to show that if $A\le_lB$ and $B\in NC_2$ then $A\in NC_2$.

Since $A\le_l B$ we have a Turing machine $M_{f,i}(x)$ calculating the i'th bit of the reduction output $f(x)_i$, using logarithmic space.

$M_{f,i}(x)=1 \iff \left( G_{M_{f,i}(x)},c_{start},c_{acc} \right)\in PATH$

Where $G_{M_{f,i}(x)}$ is the configuration graph of the computation of the logspace machine $M_{f,i}$ on $x$,and $c_{start},c_{acc}$ are the initial and accepting configurations, correspondingly.

Now your $NC_2$ circuit for $A$ will, "in parallel", compute all the bits of the reduction $f(x)$ (this can be done since you proved $PATH\in NC_2$) and send the result as input to the $NC_2$ circuit for $B$. This results in an $NC_2$ circuit for $A$.


How to tell if a Heuristic is monotonic I've applied a Heuristic to a puzzle where I need to move all off the B's the the right of the W's. my Heuristic is the total distance of the B's from the right most W's. my initial state is (B,B,B,*,W,W,W), where * represents a blank space. A piece can move into a blank space and can jump over one or two other pieces into a blank space. I've attached a picture of the graph.

This Heuristic is Admissible because the distance to the goal is ALWAYS more than the distance from the B's to the rightmost W.

The thing I'm not sure of is if this Heuristic is monotonic. My understanding of Monotonic is that the cost of going to an adjacent node plus the estimate of the new node have to be less than the total distance to the goal. How would I determine if this Heuristic is monotonic?

If your heuristic is essentially the original problem, but with some constraints removed, it is monotonic.
Otherwise, you must prove that there is no transition which does not uphold the formula in Caesar's answer.


Existence of non-context free but decidable languages I've been reading the decidablity and undecidability chapters in Sipser's "Intro to Theory of Computation" however I could not find an explanation on the existence of a language that is both non-context free and decidable.

The only reference to this was a simple language hierarchy diagram showing where the decidable/recognisable bounds were in relation to language types.

I'm unsure as to how I should approach this but I've thought about proving this by diagonlisation:

Let $M$ be the set of all decideable Turing Machines, and $L$ the set
of all languages that are context-free. (Assume finite alphabet)
By drawing up and filling the table where each language corresponds
to a Turing Machine, I was hoping that I could find a contradiction
in some $m \in M$ where there is no corresponding language $l \in L$.

I know that this will not work as both $M$ and $L$ are countable.

Any ideas on how I should approach this?

You could simply consider the language $L = \{a^k | k \text{ is a prime number }\}$.
This is not a context free language, but surely this is decidable by a Turing Machine that checks if the length N of the input is not divisible by any number between 2 and N-1 .


Storage in registers Whenever CPU needs the data, it gives the address of that word to the RAM via bus, then the RAM generated the copy of that word and sends to the registers via bus. Why can't the RAM send the original data instead of the copied data? Are there any disadvantages of storing original data or reference in registers?

This question illustrates a lack of understanding of fundamentals. What does moving mean!?
The RAM stores data in transistors. Do you want a little robot to pick up the specific transistors you want out of the RAM chip and deliver them to the CPU? I hope it is obvious why that is not possible.
Instead, an electronic circuit (which those transistors are part of) looks at whether those transistors are on or off. This causes an electrical signal to be sent to the CPU which updates some of its own transistors according to the electrical signal.
The question is akin to: "Whenever I need my friend's phone number, I copy it from my brain into my phone. Why can't my brain send the original data instead of making a copy?"


Typesetting LTL in Unicode? Unicode has an abundance of open circles, diamonds and boxes. Using these, we can typeset linear-time temporal logic formulas such as

$$
(\mathop{⬦}ψ)\ \,\land\ \,\mathop{⬦}(θ\ \mathsf{U}\ \mathop{◻}\mathop{○}φ)\ \ .
$$

However, in my browser, the sizes of the symbols vary too much; the heights don't match, and the result looks ugly. The same happens in LaTeX (though, you could fiddle with sizes there manually in some circumstances, but it's a mess). Are there any "proper" Unicode codepoints made specifically for typesetting LTL formulas? I failed to find any, but, maybe, I have not looked everywhere. As the pre-Unicode LTL standard take a look into the papers and books by Manna/Pnueli, e.g., http://theory.stanford.edu/~zm/tvors3.html .

Crosspost: http://latex.org/forum/viewtopic.php?f=46&t=32886

I don't know if there is a correct or recommended usage of Unicode codepoints for the LTL operators, but the mapping we used in LaTeX was the following:

□ (U+25A1) => \Box
◇ (U+25C7) => \Diamond
○ (U+25CB) => \medcirc (from txfonts/pxfonts)


Where does the decimal to binary "Divide by 2" algorithm come from? I don't know if this board would be an appropriate place for this question, but I have been trying to figure out how the divide-by-2 decimal to binary conversion trick works: in which you divide the number by 2, record its remainder and in the end write out the remainders in reverse to the get the final binary string. I have been using this for a long time but have never really considered why this works. Is there any explanation that could serve as a "proof" or even a basis for how people came up with this in the first place ? Thanks!

The algorithm follows fairly directly from our usual representation of numbers. Since most of us are more familiar with decimal, let's start there. Let's pick a number--say, 937. Since this is decimal, this means 9 * 102 + 3 * 101 + 7 * 100. So, repeatedly taking the remainder after dividing by 10 gives us the digits.
If we convert to binary, that's 11'1010'1001, because 937 is 1 * 29 + 1 * 28 + 1 * 27 + 0 * 26 + [...] + 1 * 20.
Just like in decimal, taking the remainder with repeated division by the number base we care about (2 in this case) gives us the digits of the number, starting from the least significant and progressing to the most significant, because that's pretty much how we define the representation of a number in a particular base.


How do two H gates act on two entangled qubits? In this circuit, if the two qubits are initialized at state 0, then after the oracle they are entangled and in the state:
$$\frac{1}{2} (|00\rangle+|01\rangle+|10\rangle-|11\rangle)$$
My question is, how do the two $H$ gates act on them? Do they act like:
$$\frac{1}{4} [(|0\rangle+|1\rangle)\otimes(|0\rangle+|1\rangle) + (|0\rangle+|1\rangle)\otimes(|0\rangle-|1\rangle) + (|0\rangle-|1\rangle)\otimes(|0\rangle+|1\rangle) - (|0\rangle-|1\rangle)\otimes(|0\rangle-|1\rangle)]$$
which in the end nothing has changed. My intuition tells me that it's wrong.
Update: The figure above is from a circuit to implement Grover's algorithm. The whole figure is given below:

The state is indeed not changed after the two $H$ gates, so why do they add them here?

The Hadamard gate performs the following operation on a single qubit:
\begin{align}
|0\rangle &\to \frac{|0\rangle + |1\rangle}{\sqrt{2}} \\
|1\rangle &\to \frac{|0\rangle - |1\rangle}{\sqrt{2}}
\end{align}
This gives the action on pure states. The action extends linearly to mixed states:
$$
\alpha|0\rangle + \beta|1\rangle \to \alpha\frac{|0\rangle + |1\rangle}{\sqrt{2}} + \beta\frac{|0\rangle - |1\rangle}{\sqrt{2}}
$$
What happens when there are seveal qubits around? In this case, it is common to denote $|a\rangle \otimes |b\rangle$ by $|ab\rangle$, for brevity. If we apply a Hadamard gate on the first qubit, then it only affects the first qubit:
\begin{align}
|0b\rangle &\to \frac{|0b\rangle + |1b\rangle}{\sqrt{2}} \\
|1b\rangle &\to \frac{|0b\rangle - |1b\rangle}{\sqrt{2}}
\end{align}
Similarly, if we apply a Hadamard gate on the second qubit, then it only affects the second qubit:
\begin{align}
|a0\rangle &\to \frac{|a0\rangle + |a1\rangle}{\sqrt{2}} \\
|a1\rangle &\to \frac{|a0\rangle - |a1\rangle}{\sqrt{2}}
\end{align}
The two operations commute.
What happens to a general mixed state? Denoting by $\stackrel{(i)}\to$ the application of $H$ on the $i$'th bit, we get
\begin{align}
&\alpha|00\rangle + \beta|01\rangle + \gamma|10\rangle + \delta|11\rangle \\
\stackrel{(1)}\to
&\alpha\frac{|00\rangle + |10\rangle}{\sqrt{2}} + \gamma\frac{|00\rangle - |10\rangle}{\sqrt{2}} +
\beta\frac{|01\rangle + |11\rangle}{\sqrt{2}} + \delta\frac{|01\rangle - |11\rangle}{\sqrt{2}} \\ =
&\frac{\alpha+\gamma}{\sqrt{2}} |00\rangle + \frac{\beta+\delta}{\sqrt{2}} |01\rangle +
\frac{\alpha-\gamma}{\sqrt{2}} |10\rangle + \frac{\beta-\delta}{\sqrt{2}} |11\rangle \\
\stackrel{(2)} \to
&\frac{\alpha+\gamma}{\sqrt{2}} \frac{|00\rangle + |01\rangle}{\sqrt{2}} +
\frac{\beta+\delta}{\sqrt{2}} \frac{|00\rangle - |01\rangle}{\sqrt{2}} +
\frac{\alpha-\gamma}{\sqrt{2}} \frac{|10\rangle + |11\rangle}{\sqrt{2}} +
\frac{\beta-\delta}{\sqrt{2}} \frac{|10\rangle - |11\rangle}{\sqrt{2}} \\ =
&\frac{\alpha+\beta+\gamma+\delta}{2} |00\rangle +
\frac{\alpha-\beta+\gamma-\delta}{2} |01\rangle +
\frac{\alpha+\beta-\gamma-\delta}{2} |10\rangle +
\frac{\alpha-\beta-\gamma+\delta}{2} |11\rangle
\end{align}
The Hadamard gate is Hermitian, and so applying it twice in a row results in the starting point: $HH = I$. Therefore if the oracle does nothing, you do get what you started from. But usually the oracle does change the qubits somehow.


set with maximum sum consisting of mutually co-prime numbers Definitions. Let $n$ be a natural number and $S$ be a subset of distinct natural numbers all less than $n$, and mutually co-prime. Then find the maximum sum the set $S$ can have.
Example. Let $n=10$, then the maximum sum $S$ can have is $30$ corresponding to $S=\{1,5,7,8,9\}$.

What I tried. I tried to implement the following greedy algorithm.

First I divide primes $\le n$ into $3$ lists: $list_1$ containing primes $\le \lfloor \sqrt{n} \rfloor$, $\; list_2$ containing primes in range $\big( \lfloor \sqrt(n) \rfloor,\lfloor \frac{n}{2} \rfloor \big )$ and finally $list_3$ containing prime in the range $\big[\lfloor \frac{n}{2} \rfloor+1,n \big ]$.
Next I define a function $largest(a,b,n)$, which returns the largest number of the form $a*b^{r}$ less than equal to $n$.
If there exist two numbers $l_1 \in list_1$ and $l_2 \in list_2$ such that $diff = largest(l_2,l_1,n)-( largest(1,l_1,n) + l_2 ) > 0$, I chose the pair $(l_1,l_2)$ such that $diff$ is maximised. I delete $l_1$ from $list_1$, $l_2$ from $list_2$ and append $largest(l_2,l_1,n)$ in $list_2$ and repeat step $3$. If no such pair $(l_1,l_2)$ exists such that $diff>0$, I go to step $4$.
I don't change anything in $list_3$.
In the end $ \{1\} \cup \{ l_1^r \;  | \;l_1 \; \in list_1 \text{ and } largest(1,l_1,n)=r \} \cup list_2 \cup list_3$ is my desired set $S$ and I report the sum of it's elements.

Running example of my algorithm. If $n=30$,

#list_1 = {2,3,5}
#list_2 = {7,11,13}
#list_3 = {17,19,23,29}

#The first time step 3 is evaluated I get l_1 = 2 and l_2 = 7 ..
#.. as  diff = ( 28 - ( 16 + 7 ) ) = 5 > 0 and diff is maximised
# so I delete 2 from list_1 and 7 from list_2 and append 28 in list_2

#When step 3 is evaluated again no such pair (l_1,l_2) is found

#So our desired list becomes S={1,27,25,11,13,28,17,19,23,29} with sum 193.

But my algorithm only seems to give correct for few simple cases only. Plus I am not able to prove/disprove or modify any of my assumptions .Now I am hopelessly stuck at the problem and I am not making any progress. But I still believe that some greedy algorithm is at work here.

PS: The question is from project Euler max-sum co-prime set. I would really appreciate just some hint or new direction to think.

Project Euler asks you to solve the problems yourself, without help. So dont read on if you want to submit a solution for Project Euler; that would be cheating.

Since the numbers are mutually co-prime, each prime number p is a factor of at most one element of S. On the other hand, if p is small enough then a number could have a factor $p^2$, $p^3$, $p^4$ and so on. We also know that every prime number p ≤ N is used (if p is not used as a factor of any number in the set then we just add p). And don't forget to include the number 1 in the set S :-)

A number x ≤ N cannot have two prime factors greater than $N^{1/2}$. Therefore the set S contains among other numbers one number $x_p$ ≤ N which is a multiple of a prime $p > N^{1/2}$. That's a good start for finding the optimal set S. We then take the primes $q ≤ N^{1/2}$, and either multiply one of the numbers $x_p$ by a power of q, or we add a new number $x_q$ which is some power of q.

In the Project Euler project with N = 200,000, there are fewer than 90 primes $q ≤ N^{1/2}$. We can take each of these primes q in turn, and either multiply one of the existing $x_p$ by a power of q, or add a new number $x_q$. We would try to do this achieving the highest possible increase in the sum. If no two q, q' achieve the highest increase in the same way, we can pick the optimal way for each.

In the example N = 30, we would start with $x_p$ = 7, 11, 13, 17, 19, 23, 29. We can use q = 2 to change 7 -> 28. q = 3 -> 27, q = 5 -> 25. The gains are 21, 27, 25. Each gain is > N/2. So an optimal solution cannot include a number created by two or more of the q's - that number would be ≤ N, but we would give up two gains > N/2, so this wouldn't be optimal. So in the simple example, we multiply 7 by $2^2$ and add $3^3$ and $5^2$.

With N = 100, we would have $x_p$ = 11, 13, 17, 19, 23, ... and q = 2, 3, 5, 7. q = 2: 11 -> 88 gains 77. q = 3: 11 -> 99 gains 88. q = 5: 19 -> 95 gains 76. q = 7: 13 -> 91 gains 78. Unfortunately we have a conflict; q = 2 and q = 3 would both use $x_{11}$. If we use 11->88 (gain 77), then q = 3: 31->93 with a gain of 62; total gain 139. If we use 11->99 (gain 88) then q = 2: 23->92 (gain 69) has a total gain of 157. So optimal for N = 100 is

S = { 1, 99, 91, 17, 95, 92, 29, 31, 37, 41, ,,, }

So here is the algorithm: Start with $x_p$ = primes > $N^{1/2}$. Find the primes $q ≤ N^{1/2}$. For each q, find the maximum gain that can be achieved using q: Either $q^k$ by adding the number $q^k$, or $p * (q^k - 1)$ by multiplying $x_p$ by $q^k$. If each optimal gain is achieved in a different way, and each gain is ≥ N/2, then we found the optimal solution.

Otherwise, we choose one set of q's that use the same $x_p$. For each of these q's: We assume that this q uses $x_p$, find the optimal solution under the restriction that no other q uses this $x_p$, and choose which q using $x_p$ gives the best total.

If there is a case where the two smallest gains add up to less than N, ask someone for a more complex solution :-)


Similarly colored paths in a DAG Is there an algorithm that can efficiently solve the following question?

Given a directed acyclic graph G with n vertices each assigned a random color from a set of size <= n - 1 colors, a source vertex s, and two distinct vertices a and b both having the same color and reachable from s.

Determine if there exists at least one path from s to a and one path from s to b that have the same sequence of vertex colors.

Hint:

   Use the techniques in How hard is finding the shortest path in a graph matching a given regular language?.


What is a Black Box attack against Machine Learning algorithms? And is there an attack strategy that you can use to approximate the architecture of a machine learning system with the knowledge of class labels and some data points?

This is known as a "model extraction attack", and there's a line of research in the computer security literature on this problem.  For instance, you might look at the seminal paper by Papernot et al on the subject.  A little time on Google Scholar should rapidly turn up dozens of papers on the subject.


The difference between a Hoare Triple/Assertion and a Typed Function I have been trying to wrap my head around applying Hoare Logic and am running into the question of how Hoare triples are any different from (simply) a typed function.

That is, say you have a typed function $f : A \to B$. The initial state for the function is thus $A$, and the final state is $B$. Similarly, in Hoare Logic, it would be like $\{A\}\ f\ \{B\}$. It's like the Hoare Triple is a typed function application or something, but I'm sure functional programming has those typed as well.

The types could be complex types such as dependent types that have constraints on the input as well, so you can handle things like $x > y$ and the like. So I'm wondering, what the differences are between Hoare Triples and Typed Functions (in any type system) generally.

You are putting your finger on angular stone of program verification.
At a very rough and high level you can think a derivation in Hoare logic as proving a property, thing which can somehow be translated in a type derivation.

More precisely you are almost (you're slightly limiting yourself with Hoare logic) rediscovering the very deep Curry-Howard correspondence with asserts that mathematical proof and type derivation are the same thing.


Runtime of a recursive algorithm I have a simple recursive solution as below:

public int countPaths(int x, int y) {

    if(x == 0 && y == 0) {
        return 0;
    } else if(x == 0) {
        return 1;
    } else if(y == 0) {
        return 1;
    } else {
        int count = countPaths(x-1, y);
        count += countPaths(x, y-1);
        return count;
    }
}

This is to solve the following problem from the book: Cracking the coding interview

Imagine a robot sitting on the upper left corner of an X by Y grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot to go from (0,0) to (X,Y)?

I am trying to ascertain the run time complexity and I believe it is O(x+y). I arrived at this by using a recursion tree, for example if x=2 and y=2

The max depth of this tree is (x+y) and work done at each step is a constant. So max work done is (x+y) * c and hence the run time complexity is O(x+y)

Question 1: Am I correct? I believe the upper bound I have calculated is not tight enough

Question 2: Next, if I were to improve the run time using memoization and hence not repeating computing sub-problems, how would the run time complexity as described by Big-o change?

By no means, no, your solution is not linear. It is exponencial, O(2^max(x,y)). You can see in your own picture: each function call makes another 2 calls, and that stacks multiplicatively.
Now, for memoization, you would probably build a matrix and keep the records on it, in such a manner that a i,j iteration will rely only on already made calculations on x,y iterations, where x <= i and y <= j. This will probably result into something like O(xy), if no further calculations are made per iteration.

Finally, are you sure about this problem? It is rather a combinatorial problem that does not involve any algorithm. The problem can rephrased as: how many different permutations one can get from the following string:

RRRRDDD

Where R appears x times, and D y times? This is merely a permutation with repetition: http://www.regentsprep.org/regents/math/algebra/apr2/LpermRep.htm


What is the State of The Art of Writer AIs (Deep Learning)? Does anyone know if Deep Learning Bots can already, for example, train
  on many books of an author and output a similar but new book?

I've been wanting to get into ML for quite a while but was lacking a project to use as an incentive to keep learning, and this specific AI has caught my interest. It seems feasible from the little I know of ML so far (I'm a beginner who has taken the initial module of Deeplearining.ai course from Coursera), but so far from what I can scoop out of the internet it doesn't seem like AIs are quite there yet. They seem to be somewhat convincing, but sometimes a weird outlier appears in the text; strangely, music composition seems more convincing. Does anyone disagree?

Another relevant question: is this too difficult for a beginner? I've graduated from engineering 1 year ago, so I have some ease with programming, but I don't know how difficult Recurrent Neural Networks (RNN) and Natural Language Programming (NLP) can be.

  Also, on a sidenote, does a more experienced programmer have a
  suggestion of path I should take to learn the necessary skills to
  program such a bot, i.e., online courses and books?

Researchers are trying it out, but RNNs learn character-by-character (sequences of characters), so it is difficult to get something that resembles a story plot, as a whole. This link by a Stanford researcher explains the current (2015) state of the art. Here is the code and here are some data sets for you to start experimenting with.

Another experiment involving the writing of a travel blog also concluded that you cannot really create a long passage that makes sense at the moment. The recommendation was to look at the word level, rather than character, and focus on something more manageable, such as sentence autocompletion.

When it comes to words, the more unique ones there are in the source data set (for example using the Game of Thrones books), the tougher it becomes to train a good model. Suggestions are to limit input to more basic words (think children's vocabulary) and to have at least a total training sample at least 100 times larger than the desired output.

A trained neural network could perhaps output smaller texts (<10000 words) that make some sense, if they are of a rather structured nature. A whole book needs both a coherent plot from start to finish, as well as twists in-between. As a result, it is still way too difficult.

This guy tried it out and discovered that the AI would get sometimes stuck in loops. Furthermore, the draft produced did not always make sense in terms of the storyline and required heavy human editing.

Here is another example of an LSTM RNN outputting a Harry Potter chapter, where the sentences are grammatically correct, but sometimes make no sense.

If you want to learn more about RNNs, the Deep Learning book by Goodfellow, Bengio, and Courville comes highly recommended and has a relevant chapter.

For something more specific to writing, The Bestseller Code book uses text mining techniques and should be an interesting read.


regular expression of star-height 1 Is there a regular expression of star-height 1 (i.e. without two nested Kleene stars) for the following language : $a^*(bb^*aa^*ba^*)^*$ ?

The language has star-height 2. Note that the language includes
$R_0=(ba^+ba^+)^*$, but is disjoint from $R_1=(ba^+ba^+)^*ba^+$. Therefore, it suffices to show:

Claim: If $L$ has star-height 1 and $R_0\subseteq L$, then $L\cap R_1\ne\emptyset$.

Suppose $L$ has star-height 1. Then we can write $L=\bigcup_{i=1}^m F_{i,0}^* w_{i,1} F_{i,1}^* \cdots w_{i,n} F_{i,n}^*$ for words $w_{i,j}$ and finite sets $F_{i,j}$.

We have $(ba^kba^k)^k\in R_0\subseteq L$ for every $k$. For $k$ large enough,
there is some $F_{i,j}^*$ that contributes at least three $b$'s. Let us
choose $k$ so large that also $k>|w|$ for any $w\in \bigcup_{i,j} F_{i,j}$.

Let $u$ be the factor with at least three $b$'s contributed by $F_{i,j}^*$. Then $u$ decomposes into factors $u_1,\ldots,u_m$ from $F_{i,j}$. Now we can
clearly pick one or two consecutive $u_\ell$'s that together form a word $f\in a^+ba^+$. We can therefore repeat $f$ and obtain a word in $R_1$.

Update: Tried to be clearer.


Exercise about First-order logic I try to express the following statements in first order logic:

X is a subset of Y.
A set can be uniquely characterised by its elements.
The power set p(X) contains all subsets of X.
A set X is the union of all its subsets containing just one element.

Thus far I managed:

$\forall x \in X \Rightarrow x \in Y$
$X=Y \Leftrightarrow (\forall x \in X \Rightarrow x \in Y \land \forall y \in  Y \Rightarrow y \in X)$
$ x \in p(X) \Leftrightarrow (\forall y \in x \Rightarrow y \in X) $

However now I don't know to express the 4th problem via FOL.

I tried: $ X = \cup x.(\forall z \in X \exists t. z \in t \land t = x \land z \not \in \forall y. y \neq t)$

If possible I would also like to convert 3. in an expressing $p(X)$ with $=$ rather than $\Leftrightarrow$

Any form of constructive comments are welcome. Thanks in advance.

EDIT: Regarding problem 4.: My main problem is that I am not really sure, how to express or write down the solution - I am not too sure, what is allowed, what not. Thus I take any idea that seems remotely right or constructive.

$ X = \underset{|x| = 1, x \subset X} \cup  \Leftrightarrow  \forall y \in X \exists x . (y \in x \land \lnot \exists z .(z \lnot = x \land y \in z) ) $

On the LHS of $\Leftrightarrow $ I simply tried to express the property given in the problem above and on its RHS I tried to express this property in terms of FOL.

It might be useful to take a look at the ZFC axioms. The existence of one element sets is guaranteed by the Axiom of pairing.

The axiom of pairing says that given $A$,$B$ sets, one can construct a third set $C = \{A, B\}$. Formally:
$$ \forall A. \forall B. \exists C.\forall D. (D \in C \iff D = A ~\lor~ D = B) $$

A singleton set is just the pairing $\{A,A\} = \{A\}$.

The axiom of union says that for any set $A$ there is a set $U$ whose elements are exactly the elements of the elements of $A$. That is:

$$ \forall A. \exists U. \forall c. (c \in U \implies \exists D.(c \in D ~ \land ~ D \in A)) $$

  A set $X$ is the union of all its subsets containing just one element.

Let's look at some example, let $X = \{a, b\}^\star$ be a set, take $X^\prime = \{\{a\},\{b\}\} $, which is also a set by the axiom of pairing. By the axiom of union there exists a set $\cup X^\prime$ such that:

$$ \cup X^\prime = \{a,b\} = X$$

So you can look at the Union Axiom and try to modify to fit your problem, you have to make a union on a set of singleton sets, which means you have to find a way to define $X^\prime$.

$\star$: I'm assuming $a$ and $b$ are also sets.

  EDIT: Regarding problem 4.: My main problem is that I am not really
  sure, how to express or write down the solution - I am not too sure,
  what is allowed, what not. Thus I take any idea that seems remotely
  right or constructive.

Well, from your previous answers it seems you're only allowed to use basic operations like membership and equality, if more stuff is allowed you can literally just write something that looks like natural language while still being formal.


minimum cardinality maximal matching of graph How to find minimum cardinality maximal matching?
I tried that pick a edge from highest degree vertex remove other edges from same vertex and so on.

A 2-approximation can be obtained by returning a maximal matching, Call it M.
Let OPT be a minimum maximal matching then for each edge in M OPT covers at least one of its endpoints thus: |OPT|>=|M|/2
It would be better if you’ll be more explicit about what you did and what you’d like the algorithm to achieve (analysis of your idea, approximation factor, so on...)


Grammar of words with exactly $k$ prefixes in another grammar Given a context-free grammar $G$, how can one systematically construct a grammar $G_k$ such that

$$ L(G_k) = \{w \in \Sigma^* : |\text{Pref}(w) \cap L(G)| = k\} $$

where $\text{Pref}(w)$ is the set of $|w|+1$ prefixes of $w$? Assume $G$ is unambiguous, if needed.

Unfortunately there is no such construction, as the context-free languages are not closed under this operation.

Consider the language $\{ a^nb^n \mid n\ge 1\} \cup \{ a^kb^nc^n \mid k,n\ge 1 \}$.

The language that has two prefixes in this language is $\{ a^nb^nc^n \mid n\ge 1\}\cdot \{a,b,c\}^*$, which is not context-free.


call by name : how are clashing variables handled? In call by name : In general, the effect of pass-by-name is to textually substitute the argument expressions in a procedure call for the corresponding parameters in the body of the procedure.

Technically, if any of the variables in the called procedure clash with the caller's variables, they must be renamed uniquely before substitution.

ref : http://www.cs.sfu.ca/~cameron/Teaching/383/PassByName.html

Now consider the following code :

global int i = 100, j = 5;

void P(x)
{
    int i = 10;
    print(x + 10);
    i = 200;
    j = 20;
    print(x);
}

main()
{
    P(i + j);
}

Will the variable i declared in function P get renamed before execution ?
Which i ( global or local ) is accessed by x in print(x + 10) ?
Which i ( global or local ) will get updated by (i = 200) ?
What will be the output of the second print statement (220 or 120 ) ?

Programming languages do not "textually substitute" anything, that would be horribly inefficient. The "textual substitution" definition may be offered sometimes as a sort of textbook explanation, but it usually fails to capture all the details.

There are many techniques for dealing with the problem you describe. By the way, the problem is known as "variable capture" beacuse a binder "captures" a variable.

One possiblity is to eliminate all variable names and use de Bruijn indices instead. Substitution still requires a bit of work, namely shifting of indices, but at least one does not have to generate new names.

Another possibility is to create closures. These are used for evaluation of functions (I did not say "application"!), but in a call-by-name language we could use them for any expression. Briefly, when we evaluate P(i + j) in your code, we create a closure (η, i + j) where η tells us what the values of variables are at that point in the execution (so concretely, η would be something like i ↦ 100, j ↦ 50, P ↦ ..., main ↦ ....). When P actually needs the value of its argument, we evaluate i + j in the environment η (and not in the environment of P), so that i + j gets evaluated in the "old" environment.

There are still many other techniques for avoiding variable capture. Haskell compiles to a spineless tagless G-machine, or at least it used to.


Would any continuous model of the universe have/be based on hypercomputational laws? I've read that when Turing-Church thesis is applied to the universe and physics, one of the three interpretations that we can use and is defended by some important physicists is that:

  "The universe is a hypercomputer and then it is possible to build more powerful machines than Turing machines. For this it would be enough for the universe to be continuous and make use of that continuity (another question is how dense its continuity is), using the results of said supercomputer as input"

Would that mean that every continious (or "continously-enough") model of spacetime and the universe could have fundamentally hypercomputational physics (physics described and based in hypercomputation and hypercomputational processes and laws/rules, describing a hypercomputer-like universe)? Or on the contrary only certain models could do it? In that case, can you think of any in particular?

If you are interested in the effect of being able to compute with continuous real numbers, you might enjoy learning about the Blum-Shub-Smale theory of computation with the reals.  A good survey is Computing over the Reals: Where Turing Meets Newton by Lenore Blum.  Wikipedia states that the set of functions that are computable in this model are incomparable with the set of functions that are computable in the usual model, and gives a citation where you can read more.  It's not clear to me exactly how that result should be interpreted, though.


Showing that Hadamard is its own inverse Im trying to work out that a Hadamard transform H (a unitary matrix) is its own inverse by applying it twice to an arbitrary state $|x⟩$:

$$H|x⟩ = \frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n}(-1)^{x \cdot y}|y⟩\,.$$

Then
\begin{align*}
H\left(\frac{1}{\sqrt{2^n}}\sum_{y \in \{0,1\}^n}(-1)^{x \cdot y}|y⟩\right)
&= \frac{1}{2^n}\sum_{y \in \{0,1\}^n} (-1)^{x \cdot y}\sum_{z \in \{0,1\}^n}(-1)^{y \cdot z}|z⟩\\
&=\frac{1}{2^n}\sum_{y \in \{0,1\}^n}\sum_{z \in \{0,1\}^n} (-1)^{x \cdot y}(-1)^{y \cdot z}|z⟩\\
&= \frac{1}{2^n}\sum_{y \in \{0,1\}^n}\sum_{z \in \{0,1\}^n}(-1)^{y \cdot (x + z)}|z⟩\,.
\end{align*}

But I don't know how to get from here to $|x⟩$ again.

I know that $HH^* = I$, but I want to show it this way, to understand what is happening.

Rewrite your final expression as
$$
\sum_{z \in \{0,1\}^n} \left| z \right\rangle \cdot \frac{1}{2^n} \sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)}.
$$
So to complete the proof, we need to show that
$$
\sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)} = \begin{cases} 2^n & \text{if } x=z, \\ 0 & \text{otherwise}. \end{cases}
$$
If $x=z$ then $x+z = 0$ (computing modulo 2!), and so $(-1)^{y \cdot (x+z)} = 1$ for all $y$, hence the sum equals $2^n$. If $x \neq z$ then pick some $i$ such that $x_i \neq z_i$. We can partition $y$ into the $i$th coordinate $y_i$ and all the rest $y_{-i}$. Now
$$
\sum_{y \in \{0,1\}^n} (-1)^{y \cdot (x+z)} =
\sum_{y_{-i} \in \{0,1\}^{n-1}} (-1)^{y_{-i} \cdot (x+z)_{-i}} \sum_{y_i \in \{0,1\}} (-1)^{y_i \cdot (x+z)_i} = 0,
$$
since $x_i+z_i = 1$ (modulo 2) and $\sum_{y_i \in \{0,1\}} (-1)^{y_i} = 1-1=0$.


Clustered index is dense or sparse? I am confused about clustered index is dense or sparse. I searched for that, sources saying it is sparse, but can be dense also. What is it exactly?

Clustering index is applied when records are physically ordered on a nonkey field(called clustering field). As clustering field is nonkey so there can be more than one distinct record for a single clustering field value.

The strategy of clustering index is: There is one entry in the clustering index for each distinct value in the clustering field, containing the value, and a pointer to the first block in the data file that has a record with that value for its clustering field.

So clearly it is a sparse index.


Difference between time complexity and computational complexity For measuring the complexity of an algorithm, is it time complexity, or computational complexity? What is the difference between them?
I used to calculate the maximum (worst) count of basic (most costing) operation in the algorithm.

Computational complexity is the general subject of using complexity measures to compare programs or algorithms. Time complexity and space complexity are two measures that are commonly used when talking about computational complexity, but there are others.

For example, it's common to look at the number of comparisons performed in a sorting algorithm.


Given DAG G(V,E), and weight on the vertices, find the heaviest path that starts from s Given: G(V,E) DAG, vertex s, and function w: V -> R. (the weight on the vertices)

Define: We define a weighted path in G as sum of all the vertices weight.

Question: Find the heaviest path in G that starts from s. in linear time.

Well, first of all we notice it's DAG, so we can use topological sort here. and also.

My thoughts so far: for each vertex v in G, w(u,v) = w(v). Then my friend told me to multiply by minus one and check for w(p1) < w(p2) before the multiplication iff w(p1) > w(p2). But I'm not sure why it needs to be added.

Then we came up with proceeding with topological sort, relaxing all the edges that are outgoing from the nodes (according to the sort - meaning we start from the heaviest, and we continue with the heaviest edges..)

Time complexity linear.. O(E+V).

My question: If my algorithm is correct, how can I prove it? Is there another algorithm you can think of to solve this question in linear time?

Try to transform the graph as following. Assign weight 0 to each edge and then "split" each vertex into two vertices by connecting them by an edge with the weight equal to the vertex's weight.

  ====>(12)====>   turns into  =====>(v)--12-->(u)====>

The find the longest path in $O(|V| + |E|)$. Please look here.


Does the heap property in the definition of binary heaps apply recursively? The definition of binary heaps says that it should be a complete binary tree and it should follow the heap property where according to the heap property,  the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children.

In the above tree, the node with value 70 is greater than its parent 10 breaking the heap property. However, 70 is also greater than 40 and lies in the subtree of 40. Will we say that the heap property is also breaking at 40, even though 40 is greater than its two children 10 and 2?

In simple terms should every node in the subtree of a root be smaller than the root?

I would think that most people would just say that the heap property applies only to a vertex and its immediate children, because it's a sufficient definition to maintain the "recursive" heap property everywhere.  It's a cleaner way to think about it (you only need to check O(1) objects per vertex to verify that a tree is a heap, as opposed to O(n) per vertex).

I don't know if there is exactly a consensus on this, and perhaps some other people think differently.


How to cluster a large movie dataset ?? I have to cluster a movie dataset of 10000 movies. A movie has attributes like Genres, Actors, Directors, Year. Earlier I thought that we can use a simple clustering algorithm like k-medoids and the distance can be pre-computed between two movies by subtracting genres & actors.

Initialise
d(movie1, movie2) = 0

d(movie1, movie2) -= number of common genres
d(movie1, movie2) -= number of common actors
d(movie1, movie2) -= 1 (if they have a common director)
d(movie1, movie2) -= 1 (if they belong to same decade)

Is this approach correct ? Is k-medoids fast enough to cluster this dataset (I doubt it isn't) ? If it isn't fast enough any better clustering algorithm and strategy to cluster this dataset ?

Distances have to be non-negative.  Your distance metric leads to a negative distance value, which is not allowed.  A better distance metric would be "the number of genres where they don't agree, plus the number of actors where they don't agree".

As far as how well this will work, the only way to find out is to try it and see.


Can RadixSort be Ω(n log n)? I read about RadixSort and its time complexity and the worst best and average time Complexity is O(n) , so my question is can radixSort be Ω(n log n)?

The more accurate time complexity analysis for  Radixsort gives time complexity as $O(kn)$-time where $k$ is number of digits, or keys (radix is defined as the base by which digits or keys are formed, hence the name radix sort).

So, radixsort can be $\Omega(n\log n)$ if you have $\Omega(\log n)$ digits in the numbers you are sorting. For example, if you are given numbers 1 to $n$ in an unsorted list, then radix-sort will do the sorting in $O(n\log n)$ time.

See https://en.wikipedia.org/wiki/Radix_sort.


Determine if there is a subset of the given set with sum divisible by a given integer I've been given a question to solve:

Given a set of non-negative distinct integers, and a value $m$, determine if there is a subset of the given set with sum divisible by $m$.

For this question the answer is here
I don't understand the part after if DP[j]==True
what is actually the intuition behind this code. Please explain in detail.

Let f (i, k) = true if and only of there is a subset of the first k integers with a sum equal to i modulo m. As an example, if a[12] = 75, then f (i, 12) is true if and only if either f (i, 11) is true or f ((i-75) modulo m, 11) is true. And obviously f (i, 0) is true if and only if i = 0.
So if you have n integers, create a two dimensional array of size m * (n + 1), then fill array [i, 0] for all i, then fill array a [i, 1] for all i, and so on until you filled a [i, n] for all i. And there you have the solution.
Next you figure out how to do this without using an array of (n+1) * m elements, and you figure out when you can stop early because you know the answer already.
And I would be curious if there is any reason why these numbers would have to be a set.


Proving a LL(1) equivalent grammar doesn't exist Consider the following CFG

$S \rightarrow \epsilon\ |\ aSbS\ |\ bSaS$

How can we prove formally that an equivalent $LL(1)$ grammar does not exist. I feel that intuitively an equivalent $LL(1)$ grammar doesn't exist, but I'm unable to prove this formally.

The language for the grammar in the question is the set of all words with equal number of $a$'s and $b$'s.

I am afraid your intuition is incorrect. Here is an $LL(1)$ grammar for it.

$S \to aAbS \mid bBaS \mid \epsilon$
$A \to aAb \mid \epsilon$
$B \to bBa \mid\epsilon$

Here is some statistics about the above $LL(1)$ grammar.
$$\begin{array} {|c|c|c|c|}
\hline
\text{nonterminal} &\text{first set} &\text{follow set} &\text{nullable} &\text{endable}\\\hline
S &a\ b &\emptyset &\text{yes} &\text{yes}\\\hline
A  &a &b &\text{yes} &\text{no}\\\hline
B &b &a &\text{yes} &\text{no}\\\hline
\end{array}$$

Here is the parsing table.
$$\begin{array} {|c|c|c|c|}\hline
 &a & b &\$ \\\hline
S  &S\to aAbS &S\to bBaS &S\to \epsilon\\\hline
A  &A\to aAb &A\to \epsilon\quad\ & \\\hline
B &B\to \epsilon\quad\ &B\to bBa & \\\hline
\end{array}$$

Exercise. Show that both the grammar in the question and the grammar in this answer generate the language of words with equal number of $a$'s and $b$'s.


Logarithmic Randomness is Necessary for PCP Theorem I am trying to proof the following statement:

If $ {\rm SAT} \in {\rm PCP}[r(n),O(1)]$, where $ r(n)=o(\log n)$, then ${\sf P}={\sf NP}$.

Here are my ideas for the proof:
It can be easily worked from here that there exists an nondeterministic Turing machine $N$ solving any SAT instance in time $o(n^{q})$ for any $q \in R^{+}$. I believe it should lead to a contradiction somewhere  (maybe alteration theorems). I had another approach to guess the certificate, but that takes time $2^{2^{o(\log n)}}$ which is not always polynomially bounded.

Source: PCP Course By Prahladh Harsha. This was one of the excercise questions. I am self studying this, so this does not violate any ethical arguments.

You can actually show a slightly stronger result: if $SAT \in PCP(o(\log n), o(\log n))$ then P=NP. The idea is to apply the implied reduction repeatedly, reducing the size of the instance all the way down to $O(\log n)$, at which point you can solve it by trying all certificates.

For more details, Arora and Safra (page 76) suggest looking at Theorem 26 in the appendix of FGLSS (journal version). Unfortunately, this appendix doesn't seem to be available any more.


Algorithm to compute partitions of a graph in N cliques does anyone know of an efficient algorithm to compute the partition of a graph in N cliques?

Notice that N is the number of the cliques and not the size of them.

I have heard of the 2 cliques problem, but I'm interested in the more general version.

This problem is known as clique cover and it's NP-complete. In other words, no efficient algorithm is known.


Regular language is closed given transposition of rightmost character to leftmost It would appear straightforward to show that a regular language is closed given the transposition of the rightmost character to the front. However after drawing a few sample DFA for the phenomenon, I've been unable to come up with a generalized 'concept' or 'proof'  that shows it's true for all regular languages. Could anyone help me out? It's on occasions like these that I see the value of formal definitions for DFA (instead of just drawings), however it's been a while since I've studied those.

This answer assumes that the transposed language never contains the empty string.
Let $L$ be a regular language, say accepted by a DFA with states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$.
We construct a new DFA with states $Q' = q'_0 \cup (Q \times \Sigma)$. The initial state of the new DFA is $q'_0$. The transition function is defined as follows: $\delta'(q'_0,\sigma) = (q_0,\sigma)$, and $\delta'((q,\sigma),\tau) = (\delta(q,\tau),\sigma)$. Finally, the set of accepting states $F'$ contains all states $(q,\sigma)$ such that $\delta(q,\sigma) \in F$.
The new DFA reads the first symbol $\sigma$ and remembers it. It then simulates the original DFA, accepting a word if adding $\sigma$ would result in the original DFA accepting it.


Complexity of finding the shortest simple even s-t-path Consider a graph $G=(V,E)$ and two vertices $s,t$.

What is the complexity of finding the length of the shortest simple $s-t$ path that has even length?
Does the problem become harder if the graph is edge weighted?

Note that the requirement that the path is simple makes it harder than to simply to use two copies of the graph

Its in P for undirected graphs and NP hard for directed once:
http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/pdf


Mutation considered harmful, but is there a safe set Functional programming does not have mutation. Mutation is usually harmful, however mutation is sometimes beneficial. e.g. Creating a [random number] generator.

In the same way that goto is considered harmful, but now we have structured languages that give us access to a safe set of goto patterns. Is there a safe set of mutation patterns? Is there currently any research into language features that implement them?

Ask not how to get rid of the evil mutable state, but rather how to tame it by provding structured and predictable ways of using it.

Just because goto is harmful you wouldn't remove all flow control from a language, right? You'd rather think of ways of using control flow in a structured way, and then you would invent the while loops.

There is not single best solution on how to structure and control mutable state, but there are some good ones. For example, you can have the programmer describe quite explicitly which part of the program can do what and who "owns" stateful parts of memory. The compiler will then check for compliance. An example of this sort of thing is Rust.

There is a more general phenomenon which encompasses mutable state, namely computational effects. Mutable state is tricky to get right, but so is concurrency, I/O can be tricky depending on what you do, etc. These are all computational effects, and we can ask whether there are general and structured ways of dealing with them.

The most popular general way of controlling computational effects is to use monads. These are programming language constructs that allow you to express presence of certain computational effects (could be mutable state) with typing information. This way the programmer will be able to see that a certain piece of code may cause effects, and the compiler will complain if things don't fit.

Another method that has caught some interest lately is algebraic effects and handlers. It's less general than monads, but it also organizes your code in a way that is often a bit more flexible than monads (The people of the Internet want to know this too.) Briefly, handlers are a generalization of the familiar exception handlers that allow you to intercept any computational effect and do something with it. I like to explain their usefulness with the slogan
$$\frac{\mathtt{handlers}}{\mathtt{callcc}} =
\frac{\mathtt{while}}{\mathtt{goto}}.
$$
That is, just like while is the structured way to do goto, handlers are the structured way to do non-local flow control in a functional setting (callcc has been called "the goto of functional programming").


Meaning of $\mu t$ terms in dependent type theory What is the meaning of the term $\mu t$ in the type theory formalized in this paper (section 2.1, page 2)?

The term μ t is the application of a closure μ to a term t. Similar to how t t' is the application of a term t to t'.


Is a Turing Machine a Well-formed formula? Today i wrote something about the bijection between turing machines and recursive functions. And i describe a Turing Machine as a Well-formed formula because it seems like a WFF to me.
But is it correct when we say that a Turing Machine is a WFF ?

Yes and no. Turing machines aren't WFF, but can be encoded as a WFF. The definition of TMs uses sets and functions (which aren't symbols in the alphabet), but its possible to create a one-to-one encoding from TMs to WFF. Usually, given a TM $M$, we refer to its encoding as $\langle M\rangle$.


Solving recurrence relation I am trying to find a $\Theta$ bound for the following recurrence equation:

$$ T(n,p,k)=T(n,p,k/2)+T(n,p/4,k)+T(n/8,p,k)+npk $$

                   npk
    /               |                 \
   /                |                  \
T(n,p,k/2)    T(n,p/4,k)     T(n/8,p,k)

the max height of the recursion tree is $ \log_{8}n $ and the cost of each level is at most npk
so i guess the answer is $\Theta (npk \log_{8}n) $

Is my answer right?

The cost at each level isn't $npk$. Let's look at the first few levels.

The cost at the top level, $l=0$, is indeed $npk$.
At the next level ($l=1$) you have three recursive calls: $T(n,p,k/2)$, $T(n,p/4,k)$, and $T(n/8,p,k)$ with costs $npk/2, npk/4, npk/8$ for a total cost at level two of
$$
\frac{npk}{2}+\frac{npk}{4}+\frac{npk}{8}=npk\cdot\frac{7}{8}
$$
At the subsequent level you have nine recursive calls and if you do a bit of arithmetic you see that the total cost at that level ($l=2$) is
$$
npk\cdot\left(\frac{7}{8}\right)^2
$$
You can show inductively that the cost at level $l$ will be
$$
npk\cdot\left(\frac{7}{8}\right)^l
$$
so the total cost up to and including level $M$ will be
$$
T(n,p,k)=\sum_{l=0}^Mnpk\cdot\left(\frac{7}{8}\right)^l=npk\cdot\frac{1-(7/8)^{M+1}}{1-7/8}<8npk
$$
since, as $M$ increases $(7/8)^{M+1}\rightarrow 0$. In other words, $T(n,p,k)=O(npk)$

It's clear that $T(n,p,k)>npk$, since that's the contribution at level zero, so we have, finally, $T(n,p,k)=\Theta(npk)$.


What does $\alpha_r\supset\beta_r$ mean in the tolerance definition of System Z? I'm reading up on System Z introduced by Judea Pearl (in System Z: a natural ordering of defaults with tractable applications to nonmonotonic reasoning). A central definition is that of tolerance of a subset $R'$ of a rule set $R$ for a rule $r = \alpha_r\to\beta_r$ (denoted by $T(r\ \vert\ R')$). Tolerance of $R'$ for $r$ is defined to be the set of satisfiable formulas $$(\alpha_r\land\beta_r)\bigcup_{r'\in R'}(\alpha_{r'}\supset\beta_{r'})$$
(see page 2 of the article by Pearl).

I don't understand what $\alpha_{r'}\supset\beta_{r'}$ is supposed to mean. Can anyone explain?

In elementary logic, $A \supset B$ is notation for the formula $\neg A \lor B$ (for the implication "$A$ implies $B$").  In other words, $A \supset B$ is a formula; it is true if $A$ is false or if $B$ is true, and false otherwise.  https://math.stackexchange.com/q/1106001/14578

How you could have figured this out on your own: Read the entire paper.  For instance, a useful place would be to start would be reading the examples in Section 3, where from the examples one can reverse-engineer the probable meaning of the symbol.


Making mathematical expressions as balanced trees as possible I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible.

This is what I have done so far, but is there a way to make them even more balanced?

$( − 3)(^2 +  − 1)$

$4( − 1)( − 2)( − 3)$

Since these are mathematical expressions, you can bracket the second one as (4 (x-1)) ((y-2) (z-3)) to make it more balanced. In many programming languages this wouldn't be allowed, because with floating point arithmetic, the order of operations will often change the result.

Can't see any way to improve the first one.


Advantages of using prime number as interval during a shell sort? As I understand it's best practice to always use a prime number during a shell sort for its interval. Why is this the case?

It is still an open question what the best gap sequence for shell sort would be; and what the performance of shell sort would be with an optimal sequence.

The "holy grail" for comparison based sorts is O(lg(n!)) ~= n*lg(n) -n performance.
No one has ever found a gap sequence for shell sort that achieves that.

Here's what we do know-
1= the last gap must always be 1 (insertion sort)
2= there should be no more than lg(n) -1 gaps
(thus the lg(n) -1 gap is always going to be 1)
3= the gaps should at least be relatively prime to each other.
4= the gaps should be between a factor of 2 or 3 of each other
5= the gaps can not be expressed by a closed form math formula if you want worst case performance better than O(n*lg^2(n)) or O(n^(3/2))

Thus using just primes closest to (n/2)^i for the first lg(n)-2 passes can be a very good choice, but
a= we as of yet can not prove such a gap sequence would be optimal, and
b= figuring out what the gap sequence is for any given size of data set is non trivial if all of our gaps are primes.


Proving non-regular language using the pumping lemma I would like to verify that the following language is not regular.

I know that if the pumping lemma is not valid then the language is not regular. (but its not enough to prove that the language is in fact regular if the pumping lemma is valid)

So, given the following language,

$\Sigma =\{a,b\}$,
$L=\{v\cdot u\cdot u: v,u\in\Sigma^*,u\neq \varepsilon\}$

Can I show that the pumping lemma is not valid here?

Side note:

I think I can prove that this language is regular by using regular expressions like so:

denote $r= (a\cup b)^*$
now, $L=(a\cup b)^*\cdot (aa\cup bb)\cdot r\cdot r$

Is this true?

Your language is not regular. Indeed, let $n$ be the pumping lemma constant, and consider the word $ab^nab^na = a(b^na)^2 \in L$. Suppose that your language were regular. Then you could write $ab^nab^na = xyz$, where $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$. We consider two cases:

Case 1: $x = \epsilon$, and so $y = ab^t$ for some $t \geq 0$. Then $xy^0z = b^{n-t}ab^na$. Suppose this were of the form $vu^2$. Considering the second copy of $u$, we see that $u$ ends in $a$. Since there are two copies of $a$, necessarily $u = b^na$. This is only possible if $t = 0$ (which is OK) and $v \neq \epsilon$ (which is not OK).
Case 2: $x = ab^t$, and so $y = b^s$ for some $t \geq 0$ and $s \geq 1$. Then $xy^0z = ab^{n-s}ab^na$. Suppose this were of the form $vu^2$. Since $v \neq \epsilon$, the word $u^2$ is a suffix of $b^{n-s}ab^na$, and so as before, necessarily $u = b^na$ and we reach a contradiction since $s \neq 0$.

Now, why does your regular expression $(a+b)^* (aa+bb) (a+b)^* (a+b)^*$ not work? You are implicitly assuming that if you write "$r \cdot r$" then the semantics are that the same word must be chosen twice. However, this need not be the case. For example, the word $aab$ matches your regular expression, but is not in $L$.


Proving that the reversal of a language reversal is that language I am trying to prove that with language L, (L^R) ^R =L
So that the reversal of the reversal of the language is the original language L.

I have proved that before with a string not language (let's call it a string 's').

(s^R)^R = s.
Proof by induction on the length of s.

Base: |s|=0. s=ε. (s^R)^R =(ε^R)^R =(ε)^R =ε=w.
Induction hypothesis: if 0 ≤ |x| ≤ n, then (x^R)^R = x.
Induction step: Suppose |s| = n + 1. Then we can write s = xa, where a is a symbol and 0≤|x|≤n. Then
(s^R)^R
= ((xa)^R)^R since s = xa
= (ax^R)^R since (xy)^R = y^R*x^R (think of a as a string of length 1) = (x^R)^R*a^R same as previous line but using outer R
= (x^R)^R*a using the second part of the definition of reverse with u=ε.
= xa by the induction hypothesis
= s since s = xa

How can this reasoning the expanded to Languages? In essence I am proving the same operation, but I am dealing with languages instead of strings. Languages are made up of strings. Thoughts?

Well, we don't really need induction here.

We want to prove that for any language $L$ holds the statement

$$\left( L^R \right)^R = L.$$

(1) Let $s \in \left( L^R \right)^R$.
Then there exists a (unique) string $t \in L^R$, such that $s = t^R$.
The situation is analogous with $t$: there exists a (unique) string $u \in L$ such that $t = u^R$.
From that we get $s = t^R = \left( u^R \right)^R = u$, so $s \in L$.

(2) Let $s \in L$. Observe that $s^R \in L^R$ and $\left( s^R \right)^R \in \left( L^R \right)^R$, again using the fact that $s = \left( s^R \right)^R$ we get that $s \in \left( L^R \right)^R$.

From (1) and (2) follows the statement of the theorem.


Designing a context free grammar for a language; When to use the empty string $L= \{a^{2i}b^{j}vc^{j}(ac)^{i} |  i,j \ge 0, v \in \{a,b\}^*\}$ over the alphabet $\Sigma = \{a,b,c\}$

How can a grammar be created from the language without the use of the empty string. Below is my example that does use the empty string.

$S \rightarrow aaSac|B$

$B \rightarrow bBc|C$

$C \rightarrow aC|bC|\epsilon $

You can use the empty string, $\epsilon$ liberally. It could help you conceptualize the grammar easier and faster. For example, as you said, because $v\in\{a,b\}^∗$ that v can be one of $a,b$ or $\epsilon$, therefore using $\epsilon$ will help you to isolate non-terminal symbol $v$ as generating all words over the alphabet $\{a,b\}$ using just three rules.

On the other hand, language $L$ in the question, $L= \{a^{2i}b^{j}vc^{j}(ac)^{i} |  i,j \ge 0, v \in \{a,b\}^*\}$ can be generated by a context-free grammar without $\epsilon$ except one rule, $S\to\epsilon$. Here it is.

$S \rightarrow aaSac|B|aaac|\epsilon$
$B \rightarrow bBc|B|bc$
$C \rightarrow aC|bC|a|b$

You can obtain the above grammar by following the procedure to eliminate ε-rules, which can change any context-free grammar to an equivalent grammar that either does not use $\epsilon$ or just uses it once in the rule $S\to\epsilon$.  Note that if the language includes the empty string, at least one usage of $\epsilon$ is inevitable; otherwise, it can only generate non-empty words. Finally, a grammar in Chomsky Normal form is designed to be such a grammar.

Just in case you might think every context-free grammar will use $\epsilon$ at least once, here is a grammar that does not use $\epsilon$.

$S\to a$.

In fact, for every grammar in Chomsky Normal form that uses $\epsilon$, you can remove that single rule, $S\to\epsilon$ to obtain a new grammar that does not use $\epsilon$. The languages generated by these two grammars are the same except the former one contains the empty string while the latter one does not.


Find all the ways to choose $k$ objects from a list of $n$ objects (using a graph?) I was playing around with graph theory and I noticed that a directed integer graph with unique vertices $V$ and edges $E$ such that each vertex only points to vertices with a higher value can be used to enumerate all $n \choose 2$ ways to choose $2$ values from a total of $\left|V\right|$ possible values.
For example:

Here, $V = \left\{ 0, 1, 2, 3, 4, 5, 6 \right\}$ and $E = \left\{ (0,1),(0,2),\cdots,(5,6) \right\}$ and creating the initial graph is of the order $O(n^2)$. $E$ readily contains all possible pairs of numbers chosen from the list.
I was wondering if the same strategy could be used to enumerate any $n \choose k$ where $0 \leq k \leq n$, or if there are more efficient algorithms for this purpose.

To generalize your approach to $k$-subsets of an $n$-set, you would need to build a hypergraph. Ordinary graph edges are relations between pairs of vertices. Hypergraphs allow relations between arbitrary sets of vertices. They are extremely general objects, essentially representing families of sets.
This question provides two good answers for how to (reasonably) efficiently enumerate these subsets. The first uses bit magic and is a special case when $n$ is small enough. The second takes a recursive approach which saves having to compute the first $k-1$ elements of a $k$ subset multiple times, but only really helps if enumerating over several consecutive values of $k$.


Random Forest closed loop I'm using the Random Forest algorithm for classification. I have some variable to use as features in input, but I was wondering if I can use the output of the classification itself as input.

Suppose, for example, that I want to classify people in two categories : "criminal" or "honest". In order to do that, I have a vector of three features: the name of the city where the person is born, the number of people that committed crimes in the city where the person is born, and the number of people that live in that city.
When I run the algorithm, I will get the classification results $y_1,y_2,...,y_n$ for each input vector $x_1,x_2,...,x_n$.

Now, it would be wrong to add to the input vector a new feature "number of people from the same city who have been classified by the algorithm as criminal"?

My purpose is to run several instances of the algorithm on different datasets and then share the informations gathered in each subset between the different instances.
Does it can make sense?

This is a cascade classifier. Of course you can do that, but the main disadvantage (that you have to keep in mind) is that your error propagates along your cascade classifiers. So even if you have a very good classifier somewhere towards the end of your cascade, if you feed it with weak features (i.e., the output of the previous layer which was not so good) you should not expect to get a reasonable answer. There is generally another common problem with this method and that's the well-known overfitting effect. However, since you are using different subsets of data to train each classifier it shouldn't be a problem in your case I guess.


Arithmetic of asymptotic functions I faced some problem that involves arithmetic over asymptotic functions. These are as follows:

  Let f(n)= Ω(n), g(n)= O(n) and h(n)= Ѳ(n). Then [f(n). g(n)] + h(n) is:

  (a) $Ω(n)$
  (b) $O(n)$
  (c) $\Theta(n)$
  (d) None of these

Solution to this was discussed as follows:

Let

$n = 5$
$f = 6$ so that $f = Ω(n)$ and
$g = -6$ so that $g = O(n)$ and
$h = 5$ so that $h = Ѳ(n)$
$f.g + h = -36 + 5 = -31 < n → f.g + h = O(n)$

Now let,

$g = 4$ so that $g = O(n)$ and
$f.g + h = 24 + 5 = 29 > n → f.g + h = Ω(n)$

Hence option 4 is correct, None of these.

Then I came across another problem

  Let $f(n)=Θ(n),g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)= ?$

  (a) $Ω(n)$
  (b) $Ω(n^2)$
  (c) $Θ(n)$
  (d) $Θ(n^2)$

This problem was solved in completely different approach:

Using the definitions of notations:

$f(n)= θ(n)→ c_1.n<=f(n)<=c_2.n$        ... for $n>n_0$

$g(n)= θ(n)→ c_3.n<=g(n)<=c_4.n$        ... for $n>n_0$

$h(n)= Ω(n)→ h(n)>=c_5.n$        ... for $n>n_0$

Using the extended notations forms:

$c_1.c_3.n^2<=f(n)g(n)<=c_2.c_4.n^2$        ... for $n>n_0$

Taking $c_1,c_3=k_1$ and $c_2.c_4=k_3$

$k_1.n^2<=f(n)g(n)<=k_2.n^2$

Adding h(n)

$k_1.n^2+c_5.n<=h(n)+f(n).g(n)<=k_2.n^2$        ... for $n>n_0$

As $n^2>n$ for all $

$k_3.n^2<=h(n)+f(n).g(n)<=k_2.n^2$

Which simplifies to :

$f(n).g(n) + h(n) =Ω(n^2)$

Though I am able to appreciate both approaches, this leaves me a lot of confusion. I am not able to confidently apply these methods to each other, nor to other similar problems and reach the correct solution. Are these methods correct? In fact are these questions themselves correct? Is there more straightforward approach to solve such kind of problems?

One way to help understand what's going on conceptually would be to draw a linear graph of what each of these functions mean.

So for example, say we're given a problem that tells us:

$g_1(n)=\Theta(lg(n))$

$g_2(n)=O(n^2)$

$g_3(n)=\Omega(n)$

we can make a quick sketch of where they could be in relation to each other.

With this visual, we can get an idea of possible candidates for these functions.

So let's bring it back to one of the questions you had trouble understanding:

  Let $f(n)=Θ(n), g(n)=Θ(n)$ and $h(n)=Ω(n)$. Then $h(n)+f(n)g(n)=?$

We know that $f(n)$ and $g(n)$ are both tightly bounded at $n$, so if you multiply them together, you'll clearly get $\Theta(n^2)$.

Now if we also add some function $h(n)$ that we know has a lower bound of $n$, the result must be $\Theta(n^2)+\Omega(n)$ which we can reduce to $\Omega(n^2)$, since an additional $...+\Omega(n)$ factor will be at its lowest value $n$ but there is no bound on how high this function can be (it could be anywhere from $n$ to $n^{1000}$ since there's no telling what an upper bound is), so we can conclude that it's $\Theta(n^2)+n=\Omega(n^2)$


Is {|M prints more than 300 non-blanks on input w} decidable? Let

$$ L_{300}=\{\langle M,w\rangle \mid M\text{ prints more than }300\text{ non-blanks on input }w\}.$$

Is $L_{300}$ decidable?

My intuition is it is decidable because given $M$ and $w$, we need to check for a bounded number of steps which would be a function of the number of states in the finite automata of $M$, input alphabet and the length of the input $w$. Can someone give an intuition for getting the exact bound or tell if its undecidable ?

It is decidable. The decider $D$ is described as the following pseudocode by Church–Turing thesis. The syntax of the pseudocode is borrowed from Python.

configurations = [the initial confituration]
print_non_blank = []
min = 0
max = len(w) - 1
while M does not halt on w:
    simulate one step of M on w
    configuration = the current configuration
    if M prints a non-blank:
        print_non_blank.append(1)
        if sum(print_non_blank) > 300: # Check 1
            return ACCEPT

        # update the non-blank area
        p = the position where M prints the non-blank
        if p > max:
            max = p
        if p < min:
            min = p

    else:
        print_non_blank.append(0)

        # Check 2
        for i in reserved(range(len(configurations))):
            if print_non_blank[i]:
                break
            if configurations[i].head_position < min:
                if configurations[i].state == configuration.state and configuration.head_position < configurations[i].head_position:
                    return REJECT
            elif configurations[i].head_position > max:
                if configurations[i].state == configuration.state and configuration.head_position > configurations[i].head_position:
                    return REJECT
            else:
                break

    # Check 3
    for i in range(len(configurations)):
        if configurations[i] == configuration:
            if sum(print_non_blank[i:]) > 0:
                return ACCEPT
            else:
                return REJECT

return REJECT

The decider $D$ maintains an area of the tape (represented by the closed interval $[$min$, $max$]$) such that there are only blank symbols beyond the interval. We call this area non-blank area, and call the area represented by  $(-\infty,$min$)\,\cup\,($max$, +\infty)$ blank area.

In addition to count how many non-blank symbols $M$ prints (Check 1), the decider $D$ performs two additional check. Check 2 checks for the pattern where the head of $M$ wanders in the blank area without printing any non-blank symbol, then reach a position with the same state that is no closer to the non-blank area. Check 3 checks for the case where the configuration is the same as some previous one. We can assert that $M$ will loop forever in both cases and infer whether it will print more than $300$ non-blank symbols accordingly.

Now all the rest work is to show that $D$ is indeed a decider, i.e. will always halt. We prove this by contradiction. Assume $D$ does not halt for some $M$ and $w$, then $M$ does not halt on $w$ too. Also, $M$ must print finite ($\le 300$) many non-blank symbols otherwise $D$ will detect it and halt no later than the time $M$ prints the $301$th non-blank symbol. As a result, the non-blank area is always a subset of a fixed area represented by, say $[a, b]$, during the running of $D$. We call the area represented by $[a, b]$ universal non-blank area, and call the area represented by $(-\infty,a)\cup(b,+\infty)$ universal blank area. There are two cases.

There are only finite many configurations where the head of $M$ is in the universal non-blank area. This means after some step, the head of $M$ will wander in the universal blank area forever (without printing any non-blank symbol, due to the definition of universal blank area), then there must be two configurations with the same state during the wandering. Also, the head of $M$ in the later configuration must be no closer to the non-blank area, otherwise the head will finally move into the non-blank area, which contradicts to the assumption that $M$ will wander in the universal blank area forever. As a result, this case is detected by Check 2 of $D$.
There are infinite many configurations where the head of $M$ is in the universal non-blank area. In this case, there must be two same configurations, so this case is detected by Check 3 of $D$.

Hence $D$ will halt anyway.


How can Turing machines loop forever given that the input is finite? How Turing machine can loop forever when input length is always finite?
I think this is a basic doubt but unable to understand how TM go into infinite loop? I think it can make transition forever on empty string. What are the other cases? Can it make without any empty alphabet ?

It might help to think of Turing machines as a programming language. It's easy to see how a program in your favourite language might loop (its input is finite, too!) so you can translate that to a Turing machine.


Proof of equality with destructuring let...in I have some expression (f n in the example below) returning a tuple.  I would like to prove that f n is equal to let (x, y) := f n in (x, y), which seems like it should be easy.  What tactic should I use?

Definition f (n : nat) : nat * nat :=
  match n with
    | 0 => (3, 4)
    | _ => (2, 3)
  end.
Lemma foo : forall n, f n = (let (x, y) := f n in (x, y)).
  auto. (*doesn't do anything*)
  destruct n.
  auto.
  auto.
Qed.

The same task with let tup := f n in tup can be done with the tactic trivial.  The same task with both f n replaced by an explicit tuple (f n, 12) is also covered by trivial.  Here I had to destruct n (or do a pointless induction n) to make the "tupleness" of f n be manifest.

You can destruct not only on variables, but on expressions like f n as well. So, this will get you a solution:

Lemma foo : forall n, f n = (let (x, y) := f n in (x, y)).
  intro n.
  now destruct (f n).    (* or destruct (f n). reflexivity. *)
Qed.


Maximum size of Huffman codes for an alphabet containing 256 letters I made a Huffman algorithm for data compression: it takes the content of a file as an input and outputs a compressed string. More important, it generates optimal prefix codes (made of 0 and 1) for every possible character, that is to say for every number between 0 and 255.

While the size of a code cannot exceed 256, it is possible to encode every character with a code of size 8 at most.

However, it is impossible that the algorithm generates a code of size 256 because then the codes wouldn't be optimal. It will give to the most likely chars, codes of size < 8 and it will give codes of size > 8 to the others (intuitively).

My question thus is, how can we get an upper bound of the maximum size a code can have, better than 256? I don't see how to approach the problem.

PS: the upper bound I'm looking for doesn't depend on the probability distribution. It has to be an upper bound for every possible probability distribution. As I said, I doubt that there is a probability distribution for which there is a code of size 256, so there has to be an upper bound.

I think I found the solution: For an alphabet of size $n$, the longest possible code is of size $n-1$, so here the answer is 255. So I was actually wrong in my intuition. You just need to arrange the weights so that each one is at least twice as much as the precedent and you get a Huffman tree which outputs a code of maximal size.

I don't see how to approach the problem.

OK, here is how you can approach the problem.  Can you solve this problem if you replace the number 256 with the number 3?  How about 4?  5?  Try solving those special cases, then see if you spot a pattern...

This is a useful, general pattern.  When a problem is too hard, try to find a simpler version of it and think about that.  When you see a constant in the problem, try solving simpler versions where the constant is smaller (so the problem becomes easier to think about), then look for a pattern, try to generalize, form a hypothesis, and see if you can prove your hypothesis.