Inline caching in not object oriented languages I've been recently studying inline caching as a technique to optimize method dispatch in object oriented languages. Basically, the idea is that one can remember what was previously dispatched and predict that things will go on in the same way.

My question is whether this technique has been used in pure functional languages (I'm a native of Scala which mixes both paradigms thus the uncertainty).

As Gilles points out, it's not immediately obvious what the analogue of this would be in a non-object-oriented language. Below is one suggestion.

Let's say you have a function h :: (A -> B) -> C (this is using Haskell syntax). h is a higher order function and particularly it takes a function of type A -> B.  The definition of h will be something like:

h f = ... (f a) ...

h doesn't know what f will be so it must emit code for a call to an unknown function. Of course, if (h g) occurs in the code where g is a known function, the compiler may choose to inline h and then further optimize the inlined body of h with f now known.  This is just normal inlining.  We could also imagine a similar variation where we make specialized versions of h for some finite collection of functions A -> B and call the appropriate specialized version rather than inlining. (For GHC Haskell, this occurs with type classes via the SPECIALIZE pragma.) Neither of these are inline caching, though you could imagine a "static" version of inline caching that adds the appropriate guards and branches to specialized code if possible and otherwise falls back to generic code. I don't believe this is a particularly common optimization whether a language is functional or not. It's similar to rearranging branches to improve branch prediction though.

On the other hand, this optimization and inline caching in OO languages will both happen automatically with a trace-based JIT compiler.  If you view a first-class function as an object with a single method as many OO languages with higher order functions do, then inline caching will do this optimization.  That said, there aren't that many functional languages with a JIT compiler (tracing or otherwise) based implementation, particularly for a JIT compiler specifically geared to the functional language.  Two trace-based systems for functional languages described in the literature are Pycket for Racket, which is not a purely function language, and Lambdachine for Haskell. I'm not aware of any JIT compiler for a functional language that explicitly and specifically targeted this particular optimization.


Labeling half of a bipartite graph Consider the following problem: let $(U \cup V, E)$ be a bipartite graph. Is it possible to label the vertices of $U$ with either $``+"$ or $``-"$ such that every vertex of $V$ is adjacent to a vertex labeled $+$ and a vertex labeled $-$?

This seems like a pretty natural problem, and I would be surprised if it hasn't been considered before. I'm not asking for someone to come up with an algorithm for this (although that would be great). Does this problem have a name?

Obvious it can be reduced to an integer linear program, which might be efficient in practice.

Your problem is known as hypergraph 2-colorability; the hypergraph has $U$ as vertices and the neighborhoods of vertices of $V$ as edges. Determining whether a hypergraph is 2-colorable is NP-complete.


k-nearest neighbors (Euclidean distance): How to process multiple attributes? Given this sample:

$$\begin{array}{|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \text{Class} \\ \hline
8 & 4 & A \\ \hline
4 & 5 & B \\ \hline
4 & 6 & B \\ \hline
7 & 7 & A \\ \hline
5 & 6 & B \\ \hline
6 & 5 & A \\ \hline
\end{array}$$
we then calculate each of Euclidean distance values to the row:

with P = (7, 4)

$$\begin{array}{|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \text{Square distance to query point  P} \\ \hline
8 & 4 & (8 - 7)^2 + (4 - 4)^2 = 1 \\ \hline
4 & 5 & (4 - 7)^2 + (5 - 4)^2 = 10 \\ \hline
4 & 6 & (4 - 7)^2 + (6 - 4)^2 = 13 \\ \hline
7 & 7 & (7 - 7)^2 + (7 - 4)^2 = 9 \\ \hline
5 & 6 & (5 - 7)^2 + (6 - 4)^2 = 8 \\ \hline
6 & 5 & (6 - 7)^2 + (5 - 4)^2 = 2 \\ \hline
\end{array}$$

But what if each class has more than one attribute , for example:
$$\begin{array}{|c|c|c|c|} \hline
X1 & X2 (Kg/m^2) & \color{red}{X3} & \text{Square distance to query point  P} \\ \hline
8 & 4 & \color{red}{2} & (8 - 7)^2 + (4 - 4)^2 = 1 \\ \hline
4 & 5 & \color{red}{5} & (4 - 7)^2 + (5 - 4)^2 = 10 \\ \hline
4 & 6 & \color{red}{1} & (4 - 7)^2 + (6 - 4)^2 = 13 \\ \hline
7 & 7 & \color{red}{4} & (7 - 7)^2 + (7 - 4)^2 = 9 \\ \hline
5 & 6 & \color{red}{6} & (5 - 7)^2 + (6 - 4)^2 = 8 \\ \hline
6 & 5 & \color{red}{2} & (6 - 7)^2 + (5 - 4)^2 = 2 \\ \hline
\end{array}$$

How to calculate the Euclidean distance in this case?


Can a solvable problem be encoded in a recursively enumerable language? Imagine I have a turing machine that can decide on a specific problem using a language. My question is that that problem (that can be decided by a TM M, with language L) can be encoded in a new language that is recursive enumerable.

If yes, this would mean that every solvable problem can encoded in recursive language; if not, a problem can be encoded in a recursive and/or recursive enumerable L and the problem could become semi-decidable for a different language.

Any clarification on this?

Almost immediately from definitions, one has:

A solvable (decidable) problem can be encoded as (not in) a recursive language.
A semi-decidable problem can be encoded as (not in) a recursively enumerable language.


What is 'real time' in a Computer Vision context? Suppose you have a program which works on a stream of images. It gets an image, makes edits and stores the image. What is the maximum latency with which one can still speak of a "real time application"? (Please give a source in your answer)

There is no one answer to this question. "Real time" can mean very different things, depending on what kind of sensor or sensors you are using, and what you are trying to do. By the way, editing and storing images may not even qualify as computer vision. Computer vision is about extracting information from images or video, and the meaning of real time depends on the kind of information you are trying to extract.

A typical video camera acquires images at 30 frames per second (fps). So that can be your definition of "real-time", i.e. being able to process images at the rate at which you acquire them.

On the other hand, if your goal is to detect and track objects in videos, then "real-time" is a function of how fast those objects move. For example, 10fps is often sufficient for tracking people walking on the street, but probably not for tracking cars going 70 miles per hour on a highway.


Constructing a NFA from a regular expression I have the following regular expression $R=ab^*(\epsilon \cup c) \cup c^*a$ and I want to construct the NFA that accepts languages defined by that regular expression.
I started by constructing the NFA that accepts $R=ab^*(\epsilon \cup c)$

Next I tried to continue the concatenation part by adding the following to the NFA as follows:

Is that correct? is there a quick approach to construct NFA from long regular expressions?

Your solution is nearly correct, however you need to remove the $c$-transition of $S_0$ and the $a$-transition from $S_0$ to $S_2$ and add a new state, say $S_3$, which is reached from $S_0$ via an $\varepsilon$-transition, has a $c$-transition to itself and an $a$-transition to $S_2$ (so that the word $cab$ is not recognized anymore, see benrg's comment below).
As for a general algorithm not that REs are built in a recursive manner by taking the symbols in your alphabet as "atoms" and then chaining them together using the basic operations $+$ (or $\cup$ as you denote it), $\ast$ and concatenation.
A NFA accepting the same language can then be built in a similar manner:

If the RE is just an atom $\alpha$, consider the NFA with one $\alpha$-transition to an accepting state
Suppose our RE is of the form $XY$ where $X$ and $Y$ are REs themselves and let $\mathcal A_X$ and $\mathcal A_Y$ denote the NFAs representing $X$ and $Y$ respectively. A NFA for $XY$ can be constructed by taking the NFAs $\mathcal A_X$ and $\mathcal A_Y$ and adding $\varepsilon$-transitions from all accepting states of $\mathcal A_X$ to the initial state of $A_Y$ and making the states of $\mathcal A_X$ not accepting.
Suppose our RE is of the form $X^\ast$ where $X$ is an RE. Take the associated NFA $\mathcal A_X$ and add $\varepsilon$-edges from its accepting states back to the initial one, which also needs to be made accepting.
Suppose our RE is of the form $X + Y$ where again $X$ and $Y$ are REs. Take $\mathcal A_X$ and $\mathcal A_Y$ and add a new initial state that has $\varepsilon$-transitions to the initial states of $A_X$ and $A_Y$.

Of course, this algorithm does not produce "optimal" NFAs, but it is a simple and general procedure to generate an NFA which accepts the same language as some given RE.


What are definite languages? How do you formally define them? I have a question in my homework that deals with the concept of a definite language. The question defines a definite language as follows -

"A language L is definite if there is some k(> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w." I'm supposed to do the following -

a) Rewrite this definition formally

b) Prove that every definite language is accepted by a finite automaton

c) Give an example of two definite languages L1 and L2 such that L1.L2 is not definite.

I'm breaking my head over the definition given in the question. In-depth google searches lead me to a few google books and this is what I came across -

Theory of Automata, Arto Salomaa :

Definite languages are completely characterized by the final subwords of a given length k of a string. The behaviour of definite automata depends exclusively on the latest k input letters for some k. Thus, the behaviour is independent of inputs which have occurred at sufficiently remote past moments.

Role of Theory in Computer Science: (edited by Konstantinidis Stavros, Moreira Nelma, Reis Rogerio)

Whether or not a word belongs to a given definite language can be determined by inspecting the last k symbols, where k is a constant only depending on the language. In particular, two words whose length exceed k having the same suffix either both belong to the language or both do not.

More precisely, a language L ⊆ Σ* is said to be definite if and only if
L = E ∪ Σ*Η, for some finite languages E,H ⊆ Σ*.

Theory of Formal Languages with Applications by Dan Simocivi, Richard L Tenney:

Τhis alternative definition was given by Perles, Rabin and Shamir.

A language L over the alphabet A is weakly k-definite if x ε L holds for a word x with |x| ≥ k if and only if the suffix of length k of x belongs to the language L.

For k ε Ν and k ≥ 1, a language L is k-definite if L is weakly k-definite, but it is not (k-1)-definite. A language is definite if it is k-definite for some k ε Ν.

Even after reading all this, I am not able to understand anything regarding the concept of a definite language. How can you precisely define a language to be definite when you don't know what the dependency on the last k symbols of ω is? Shouldn't the definition "depends on the last k symbols" be more clear? What can you quantify as a dependency on the last k symbols, to decide whether ω will belong to L? It doesn't make sense to me. Could you help me in getting a better, clearer, simpler understanding of this? Could you please give some examples, while explaining the concept?

A language L is definite if there is some k(> 0) such that for any string w, whether w ∈ L depends on the last k symbols of w.

There is of course room for interpretation here. Assuming they mean "[it] only depends on the last $k$ symbols of $w$", here's a slightly more precise rephrasing:

  A language L is definite if there is some $k$ so that all words that share the same $k$-suffix are either in or not in the language.

Try to work from here.


Is there a name for this class? The class $C_{1,\epsilon }$ of decision problems solvable by an NP machine such that

If the answer is 'yes,' at least 1/2 and at most $1-\epsilon$ of computation paths reject.
If the answer is 'no,' all computation paths reject.

Is there a name for this class that looks like $RP$?

Is this in $RP$ or $coRP$?

The class $C_{2,\epsilon }$ of decision problems solvable by an NP machine such that

If the answer is 'no,' at least 1/2 and at most $1-\epsilon$ of computation paths accept.
If the answer is 'yes,' all computation paths accept.

Is there a name for this class that looks like $coRP$?

Is this in $RP$ or $coRP$?

What is $C_{1,\epsilon }\cap C_{2,\epsilon}$?

Is it in $ZPP$?

Your class $C_{1,\epsilon}$ is the same as RP. It is clear that everything in $C_{1,\epsilon}$ is in RP. In the other direction, take an RP algorithm for a problem, and amplify its success probability to be $1-\delta$. Now modify it to toss coins and reject with probability $\epsilon$ (or some constant $c > \epsilon$) and only then run. If $\delta$ is small enough, then the overall success probability in the Yes case will be arbitrarily close to $1-\epsilon$.

The same argument shows that $C_{2,\epsilon}=coRP$, and so $C_{1\epsilon} \cap C_{2\epsilon} = ZPP$.


Big Oh notation for a function with two inputs of linear growth I'm quite new to time-complexity analysis so I might have misunderstood some basic concepts but lets say we have the following function:

    function(int x, int y)
    for (int i = 0; i < x; i++)
    {}

    for(int i = 0; i < y; i++)
    {}

From my understanding this function will for large inputs of $x$ and $y$ have two loops of linear growth. If the first loop is said to run $k$ times and the second $m$ times, will the big Oh notation be $O(k + m)$, or can the two inputs be merged into one variable of linear growth, like $n$, $O(n)$? Can $k$ and $m$, since they both have the same growth rate and (in the case of Big Oh analysis) equally large inputs be simplified into one variable or should they stay separate?

There is a common misconception that the running time always have to depend on a single parameter. This misconception is strange since in graph theory, the running time of many algorithms is stated in terms of two parameters, the number of vertices and the number of edges. As an example, DFS and BFS run in time $\Theta(V+E)$. A priori, we do not know of any relation between $V$ and $E$ other than $E \leq \binom{V}{2}$, and so $\Theta(V+E)$ cannot be simplified further. Since $E = O(V^2)$, any algorithm running in time $O(V+E)$ also runs in time $O(V^2)$. If we know that the graph is connected then $E \geq V-1$, and so $\Theta(V+E)$ is the same as $\Theta(E)$. But for general graphs, we have no reason to assume any relation between $V$ and $E$.

In your case, you seem to want to assume that $k$ and $m$ have the same order of growth. This might be the case or might not be the case, depending on the application you have in mind. Only you can tell. It is possible to state the upper bound $O(k+m)$ in terms of a single variable: it is $O(n)$, where $n = \max(k,m)$ (or $n = k+m$). Whether this is helpful or not is up to you.


Should a pure function take all of the functions it calls as arguments? After Wikipedia, if a function is pure, then:

  [it]  always evaluates the same result value given the same argument value(s).

So: if a function, let's call it f, calls another function, g, then it's behavior clearly depends on the structure of the function g. Should f take g as an argument in order to be pure?

No, f doesn't have to take g as an argument.  Wikipedia's definition is a bit informal.  Also informally, the behavior of a pure function is also allowed to depend on the code of the program.  Or, to put it another way, the code of the program is considered fixed, not something we vary, so we don't try to track dependences on it.

So, something like f(x) = 2*g(x) is fine: if g is pure, f will be too.


Prove that $L=\{x\mid K(x) \leq |x|-c\}$ is recognizable, where $x \in \{0,1\}^*$ Basically I want to prove that the set of all c-compressible binary strings is recognizable.

My goal is to construct a turing machine $N$ such that, given an input string $x$, $N$ accepts $x$ if there exist a turing machine $M$ and a string $s$ such that $M(s) = x$, and $|\langle M \rangle|+|s| \leq |x|-c$. Since both $|\langle M \rangle|$ and $|s|$ are bounded by $|x|$, there are only finitely many $M$ and $s$ to run through, and the output of each $M(s)$ is either $x$ or not $x$, hence the algorithm halts in finite time, and so $N$ is a decider for $L$.

But this is clearly not the case because $L$ is not co-recognizable. Where is the flaw?

The flaw in your argument is that Turing machines don't always halt. However, if a Turing machine does halt and prints $x$, then it gives you an upper bound on the Kolmogorov complexity.


What is the difference between broadcast and gossip/epidemics? Everything is in the title.
What is the difference between broadcast and gossip in the context of message-passing distributed systems?
According to Wikipedia, gossip and epidemic protocols/epidemics are synonym.
Thank you for your help.

While sometimes used as synonyms, to me, gossiping protocols are certain flavor of broadcast algorithms, where the message is flooded in a non-structural (commonly, random) way and spreads to the network.
In contrast, a non-gossiping broadcast algorithm may, for instance, deliver the message via a (predetermined) spanning tree, rather than let the message spread arbitrarily.
See, e.g., https://www.gsd.inesc-id.pt/~ler/reports/joaoleitaomsc.pdf


Is it possible that the halting problem is solvable for all input except the machine's code? This question occurred to me about the halting problem and I couldn't find a good answer online, wondering if someone can help.

Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself? Basically:

Halts(TM, I)
    IF TM == I:
        Undecidable, return a random result/throw an exception, whatever
    ELSE:
        Solve the problem

Halts'(X)
    IF Halts(X, X):
        Loop infinitely
    ELSE:
        Print 'done'

This seemingly resolves the contradiction. When we call the paradoxical Halts'(Halts'), we can't expect consistent behavior, but all other calls to Halts (and Halts') are legitimate and solvable.

I understand that this is highly unintuitive. If some pattern in the bits could reveal the behavior of all possible programs, why would it suddenly fall apart when the TM and input match? But can we mathematically eliminate this as a possibility?

And this reduced halting problem would not be uninteresting at all. Even if there were some meaningful program that took its own code as input it could trivially be rewritten to work on slightly different input. Of course this suggestion makes it even less understandable why a halting solution could exist with this one caveat but again, can we really mathematically eliminate this possibility?

Thanks for any help.

Recall the standard proof of the undecidability of the halting problem. Suppose that some machine $H$ decides the halting problem and let $Q$ be the machine that, on input $\langle M\rangle$ uses $H$ to determine if $M(\langle M\rangle)$ halts and, if so, $Q$ loops; otherwise, $Q$ halts. Now, $Q(\langle Q\rangle)$ halts if, and only if, it doesn't halt.

  Is it possible that the halting problem is decidable for any TM on any input so long as the input is not the TM itself?

No. If you change the definition of the halting problem in this way, the proof still works. We don't care what happens when $H$ receives $\langle H\rangle$ as input because the contradiction comes after we give input $\langle Q\rangle, \langle Q\rangle$ to $H$.

Second, if you modified $H$ to detect that input, we could get the same contradiction by using any other machine $Q'$ that is equivalent to $Q$ in the sense that, for any input $w$, $Q'(w)$ halts if, and only if, $Q(w)$ halts. There are infinitely many of these and $H$ can't detect all of them because it's undecidable whether two Turing machines are equivalent.


How to find a good asymptotic approximation of T(n) = T(n/2) + T(n/3) + 1? I can't figure out how to find a good asymptotic approximation for the following recurrence relation: $$T(n) = T(n/2) + T(n/3) + 1.$$

You can write your recurrence as
$$
T(n) = \sum_{i=1}^k a_i T(b_i x + h_i(n))  + g(n)
$$
with:

$k=2$
$a_1 = a_2 = 1$
$b_1 = \frac{1}{2}$, and $b_2 = \frac{1}{3}$
$h_1(n) = h_2(n) = 0$
$g(n) = 1$

From Akra–Bazzi theorem, the solution to your recurrence is $T(n) = \Theta\Big( n^p \big(1 + f(n)\big)\Big)$, where $p$ is such that $a_1 b_1^p + a_2 b_2^p =1$ and $f(n) = \int_1^n \frac{1}{u^{p+1}} \text{d} u$.

Substituting, we have $2^{-p} + 3^{-p} = 1$, which shows that $0.78 < p < 0.79$.

Therefore: $$
f(n) = \int_1^n \frac{1}{u^{p+1}} \text{d} u \le \int_1^\infty \frac{1}{u^{p+1}} \text{d} u = \frac{1}{p} = \Theta(1),
$$

and the solution to your recurrence is $T(n) = \Theta( n^p )$.


Sum of products of n-tuples Let's say I have an array of numbers {a,b,c,d,e} and want to calculate the sum of product of all triples abc+abd+...+cde.
I can calculate it very fast without generating all triples using this formula
F(n,k)= k*F(n-1, k-1)+ F(n-1, k) with two loops

       int[] values={a, b, c, d, e...};
       int k = 3;
       int[,] F = new int[values.Count, k];
       ...
        for(int i = 0; i < values.Count; i++)
            for(int j = 0; j < k && j <= i; j++)
                F[i, j] = values[i] * F[i - 1, j - 1] + F[i - 1, j];

Now I have this array of groups {{a1,a2,a3..an}, {b1,b2,b3 ...bn}, {c1,c2...} } and every element of a triple must be in different group.
a1*b2*c1 is a valid triple but a1*a2*b1 is not allowed because a1, a2 are in the same group. It's possible to generalize the above algorithm to find the sum of valid triples (quadruple or n-tuple)?

We have the following identity:

$$\sum_{i,j,k} a_i b_j c_k = (a_1+\dots+a_n) \times (b_1+\dots+b_n) \times (c_1 + \dots + c_n).$$

Therefore, one can compute the sum of all valid triples in $O(n)$ time by first computing the sum of the $a_i'$, the sum of the $b_i$'s, the sum of the $c_i$'s, and then multiplying these three sums.  This generalizes: you can find the sum of valid k-tuples in $O(kn)$ time.


Does NP=coNP imply P=NP? We know that P=NP implies NP=coNP. Does the reverse implication hold?
Does NP equal coNP imply that P equals NP?
If not why not?

I googled but didn't find the answer.

The case that $P \subset NP = coNP$ is possible. The reason why $P = NP$ implies $NP = coNP$ is that $P$ is closed under complement, and so if $P = NP$, $NP$ must be closed under complement as well.

A class being closed under complement doesn't necessarily imply anything about its deterministic counterpart. For example, we know that $NL$ is closed under complement, but don't know whether $L = NL$.


Can high-order unification be applied to programming by example? In 2007, it has been proven that high-order unification is decidable on the pattern matching case. If that is true, what is stopping someone to write an equation like:

(F [1,3,2], F [4,1,3,2], F[3,1]) = ([1,2,3], [1,2,3,4], [1,3])

If the unification works, wouldn't it probably find an F which implements a sorting algorithm - essentially generalizing the programming by example technique and, to an extent, replacing a programmer's job?

It's incredibly unlikely that a complete sorting algorithm that works for ANY input would be deduced from just 3 inputs.

In particular, there's a problem: sorting is a problem that matches an infinite set of inputs to an infinite set of outputs. You've only given a finite set of inputs, so there's an infinite number of problems which could be described by those input/output pairs.

For example, what if we want to sort numbers lexographically (i.e. dictionary order) instead of numerically? So 1, 11, 112, 1123, all come before 2. But, your example also describes lexographically sorting the given inputs. How does the algorithm know which one?

In short, it can't figure out that you want a sorting algorithm, because you haven't told it you want a sorting algorithm.

For that, you need a specification of some sort. The problem of "Given an arbitrary specification, find an algorithm that meets that specification" is undecidable.

So, there will never be a computer program which, 100% of the time, generates a correct algorithm solving any problem you give it.

It's possible that with machine learning, we can automatically derive some algorithms, but there will always either be a risk that those algorithms are incorrect, or there will be a risk that our procedure will say "I couldn't find a solution."

This is an unavoidable fact of mathematics.


Many-one reducibility: why $A = \{1\}$ is not a counterexample to $\forall A : A \leq_m A \cup \{0\}$? I'm looking at a textbook exercise that asks to prove or give a counterexample that $\forall A : A \leq_m A \cup \{0\}$.

$A \leq_m B$ is defined as:

$\exists f$ total, computable s.t. $\forall x \in A : x \in A \Leftrightarrow f(x) \in B$,

It then says in the answer sheet something to the effect of:

  The only counterexample is $A = \mathbb{N} \setminus \{ 0 \}$.

  Otherwise there is always an appropriate $f$:

  If $0 \in A$, $id$ is good enough
  If $0 \not\in A$, one such $f$ is

  $f'(x) = \begin{cases} x_0 & x = 0\\ x & otherwise\end{cases} $
  for some $x_0 \not\in A \cup \{0\}$.

However, before checking the answer sheet I was persuaded there were multiple such counterexamples.

In fact, I still don't understand what's wrong in my "proof" that $A = \{ 1\}$ is a counterexample.

It goes like this:

  Let $A = \{1\}$.
  Then $A \cup \{0\} = \{0,1\}$.
  Suppose such an $f$ as required by the definition exists.

  There are three cases, mutually exclusive by definition of
  function:

  $(1,0) \in f$, therefore $f(A) = \{0\} \neq A \cup \{0\} = \{0,1\}$
  $(1,1) \in f$, therefore $f(A) = \{1\} \neq A \cup \{0\} = \{0,1\}$
  $(1,c) \in f$ for some other $c$, therefore $f(A) = \{c\} \neq A \cup \{0\} = \{0,1\}$

  Therefore $f$ such that $f(A) = A \cup \{0\}$ cannot exist for $A = \{ 1 \}$. QED.

In particular, I don't see how, for the given

$f'(x) = \begin{cases} x_0 & x = 0\\ x & otherwise\end{cases} $

it holds that $f'(\{1\}) = \{1,0\}$

It seems to me that $f'(\{1\}) = \{1\} \neq \{0,1\}$.

What am I misunderstanding about either basic set theory or the definition of $\leq_m$?

The property that, for all $x$, $x\in A$ iff $f(x)\in B$ means that $f(A)\subseteq B$ and $f(\overline{A})\subseteq \overline{B}$. Your proof attempt uses the condition $f(A)=B$, which is neither necessary nor sufficient.


Why are these features missing in modern day general purpose computer languages? I often wondered why languages like c do not have simple syntactical allowances that would help readability.  For example, large numbers such as 1073741823 can be hard to read so my opinion is modern day languages should allow delimiters such as , (comma) so you can write a statement such as x = 1,073,741,823.  That is MUCH more readable.  Perhaps you can do this in some languages using #DEFINE but it seems like such a simple thing should be native to the language.

Another feature I would like to see in general purpose languages are huge ints.  That is, integers that are not limited to 16 or 32 or even 64 bits but some very large number of bits, perhaps 256.  This would help with simulation of certain games with very large state spaces.  Why burden the programmer with such tasks?  I, as a user of a programming language, would expect some complexity to be hidden from me and handled by the compiler itself.  Just like when we drive our cars, many people don't understand the inner workings of it but they don't need to.

It would also be nice if the math library had basic combinatorial functions such as choose(52,5) and the language also had direct syntax for factorial such as x = 52!/47!.  That is "syntactical sugar" compared to Factorial(52)/Factorial(47).

Also when I was in college I proposed a computer language that would optionally use indenting to limit the scope of statement like IF, CASE, LOOP, FOR....  For example:

if cardcount < 52
  ProcessNextCard()
else
  deckfinished = TRUE
next statement goes here and is not part of if statement cuz it is not indented.

Here is an even better example:

for c1 = 1 to 50
 for c2 = (c1+1) to 51
  for c3 = (c2+1) to 52
   ProcessHand()
nextstatement goes here but it is not part of any loop.

Ideally the programming environment would show indentation brackets to confirm the alignment and have a special printing program that does the same.

Of course if there are a lot of lines of code in the body of the if statement then it would be better (clearer) to insert the endif, ifend or fi "missing" part of the if statement.  The compiler should allow both options.  Forcing the programmer to indent is a good way to teach new programmers good programming practice and to penalize lazy programmers.

Also how about a language that self profiles (or at least assists) using a special directive?  For example, if someone wrote a file compressor program and wanted to know where it was eating up most of the time and in what proportion, it would be nice if the language automatically inserted some markers or at least allowed the programmer to insert them easily and then the profiler would tell the programmer what proportion of the runtime was between each set of markers (such as A-A, B-B, C-C... Z-Z).

I could go on and on with a wish list of enhanced features to make programming easier but I will just stick with these few for now.

So my main question is why are many of these features lacking in modern day languages or are they actually there?

You are asking a lot of questions, here are quick answers on some of them:

Syntactic sugar for integer literals: in a language like C, commas already have a function (they are an operator on their own), so there would be an ambiguity. Other languages allow them. In many countries in Europe, the roles of , and . are switched, and this highlights the fact that this type of issue is best handled by a preprocessor.
Large integers: operations on larger integers are slower than ones on smaller integers, so it makes sense to have different types in many circumstances. Libraries typically provide support for large integers even if the language doesn't natively support them.
Math library lacking support for your favorite functions: everybody's favorite functions are different. There is probably a library that supports yours, and otherwise you can write one. Computer algebra systems tend to support all mathematical functions you will ever want to use.
Indentation: you might like indentation, others might not. Generally speaking, the rule in most programming languages (other than Python and perhaps a few others) is that whitespace shouldn't matter. There are many reasons for that, including (historically) macro expansions (or INCLUDEs), and differing indentation styles. If you want to enforce your type of conventions, use a preprocessor.
Built-in profiling: many C compilers already have this feature, and it is part of the tool chain in most widely used programming languages. There is no need for explicit support in language syntax.

In general, one can think of many "improvements" and features for programming languages. That is one of the reasons why there are so many of them. Different compilers might actually implement some of these, perhaps optionally. To answer your general question, why your favorite feature isn't part of your favorite language, the answer is twofold. First, there are many potential features, and programming languages cannot implement all of them (see for example the recent C++ standards, adding lots of features and making the language ever harder to learn). Second, there are some performance issues that you might be ignoring.


Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem, given $T(1) = 1$
My approach with recurrence tree:
$n \sim n\log(n)$
$\frac{n}{2} \sim 2 \frac{n}{2}\log(\frac{n}{2})$
$\frac{n}{4} \sim 4 \frac{n}{4}\log(\frac{n}{4})$
Hence the summation must follow as:
$$T(n) = \sum_{i=0}^{\log(n)} n\log(\frac{n}{2^i})$$
$$= \sum_{i=0}^{\log(n)} n(\log(n) - i)$$
$$=(n\log(n) \sum_{i=0}^{\log(n)}i) - (\sum_{i=0}^{\log(n)} i)$$
I can not go further from here, any help is welcome.

For direct result let's use direct summation assuming $n=2^k$:
$$T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)=2\left[ 2T\left(\frac{n}{2^2}\right) +\frac{n}{2}\log \frac{n}{2}\right]+ n\log(n) = \\
=2^2T\left(\frac{n}{2^2}\right)+n\log \frac{n}{2}+ n\log(n) =\\
=\cdots=\\
=2^kT\left(1\right)+n\log \frac{n}{2^{k-1}}+ \cdots +n\log \frac{n}{2}+n\log(n)=\\
=2^kT\left(1\right) +n\log 2 + \cdots +n\log 2^k=\\
=nT\left(1\right) +n\log 2 (1 + \cdots + k) =nT\left(1\right) + \frac{k(k+1)}{2} n\log 2 \in \Theta (n \log^2 n)$$
where, of course, $k=\log_2 n$. Hope you can obtain from here everything what you wanted.
At end let me note also, that $n \sim n\log(n)$ and other equivalences, which you are using, are not correct, if we understand standard $\lim \frac{f}{g}=1$, for symbol "$\sim$". Correct is, for example, $n = o(n\log(n))$ etc.


Drawing a NFA for a string I have these grammar rules defined as follows,

FDL -> FDEF FDL | ε
FDEF -> #feature #: FEXP
FEXP -> #op #( FLIST #)
FLIST -> FEXP #, FEXP | #feature

I know how to derive the derivative tree for a given string from this, but how do I draw a NFA for this string {#feature #: #op #( #feature #)}*.
I have seen many examples which they draw the NFA from a regular expression, if so can I consider this string as a regular expression? If not how can I draw it?

I will leave the actual drawing up to you, but I will describe it here. You can draw a directed graph, with a start state that follows the input #feature to another node which follows an edge to #: to #op to #( to #feature to #). The node that we land on after #) is the accept state. If it any point, we read some input that does not allow us to follow that path, we immediately travel to another state (in this case, a designated reject state) with no output paths.

Our accept state will only have one out edge, which we follow on the input #feature. This takes us back to where we traveled after our start state. If we read any other input from our accept state, we move to the designated reject state.


O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible? Context: I've been working through Cracking the Code Interview and on page 70 the book asserts that there is a O(B) solution to this problem.

If

s = little string and S = len(s)
b = big string and B = len(b)

then I believe it would be something along the lines of (pseudocode):

hs = hash(s)
for every position, substring of length S in B:
    h_sub = hash(substring)
    if hs == h_sub:
         print position

Note that the for loop will run B-S+1 times, so whatever happens inside the loop must be O(1) in order for the whole thing to be O(B).

This assumes that there exists a O(1) hash function hash(s) that only returns the same hash when two words are permutations of each other, and never collide otherwise.

What is this hash function? It seems like you'd have to iterate through every letter in substring to calculate h_sub and I don't see how that can happen in less than O(S) time. This answer seemed promising but then someone found a non-valid collision.

I learned about the radix-2p hash for this problem in school and we had to prove it as a homework exercise so I am convinced of its correctness.

However in the calculation $k = \sum_{i=0}^{n-1} x_i(2^{p})^i$, the exponent on the $2^p$ always changes depending on the position of the letter $x_i$ within the substring, so I don't see how we can avoid having to iterate anew through all S letters of the substring when we calculate $k \text{ mod } (2^p-1)$.

Am I missing something or is there another approach entirely? Thanks.

I think a hash is the wrong approach. Instead you can use auxiliary variables: an array $A$ and an integer $c$. Basically $A$ tracks the error in the number of occurrences of each character and $c$ tracks the number of non-zero errors. Instead of a hash update you update the count of the character which drops out, then update $c$ if it changed from or to zero, then repeat for the character which is coming in. After that, if $c=0$ you found a permutation of $s$.


Determine if there exists a line that intersects all horizontal segments. Better than $O(n^2 \lg n)$? Suppose I have $n$ horizontal segments in the plane (i.e. their end points share the same $y$ value). I want to determine if there exists a line that intersects all such segments.

I think I can assert that (by some argument based on shifting the line), there exists such line iif there exists a line positioned on some end-point of one of the line segments that intersects all line segments (so that I can iterate through all end-points of the line segments (in total $2n$ points) and try to find the line). Then if I fix a point $p$, I can do a $O(n \lg n)$ radial sweep and see if there exists a line positioned at that point that intersects all the segments. I then just iterate through all $2n$ points and that gives me $O(n^2 \lg n)$.

Is my reasoning correct enough for me to write an algorithm for this?
Is there a better way to do this than $O(n^2 \lg n)?$

WLOG, let's rotate your problem so your segments are vertical. Let's say segment $i$ has $x$-coordinate $x_i$ and its low endpoint is $l_i$ and high endpoint $h_i$ (with $l_i < h_i$).

Then our line through it (assuming it exists) has formula $y = ax + b$. Plugging in $x_i$ gives us $y_i = ax_i + b$. And thus we have $l_i \leq ax_i + b \leq h_i$.

Convince yourself that a solution line can always intersect at least one of two points: the one with the highest $l_i$ or the one with lowest $h_i$ (the most extreme requirements).

We try to find a solution line by plugging in one of the two extreme points $p$ (trying the other if the first doesn't work) to find $b = y_p - ax_p$. Then we can substitute to change the inequalities to:

$$l_i \leq a(x_i - x_p) + y_p \leq h_i$$

Now our only variable is $a$ so we can run through the $n$ inequalities, consistently choosing the strictest bounds for $a$ until we find the range of $a$ that works or that there's no solution.

Total runtime is $O(n)$ since we only have to try the above process twice and finding the extreme points also takes only $O(n)$ time.


Show that it is undecidable if two Turing Machines accept the same language I was asked this question at an interview, and couldn't answer it, and would like to know how it is 'shown' that two Turing machines which accept the same language is undecidable. This is not a homework question!

Let's restrict ourselves to Turing machines that ignore their input. Now suppose you have two Turing machines:

Some given one T.
Another that loops forever.

If you could decide if they accept the same language, you'd be able to decide if T halts or not. This is impossible - see the halting problem.

This applies to SW/HW as well. It's undecidable if two programs perform the same computation or not.


Space(n) not closed under Karp reductions - what about NTime(n)? In the book on complexity by Arora and Barak, there is an exercise to show $Space(n)\neq NP$, the proof of which goes by showing that $NP$ is closed under Karp reductions, while $Space(n)$ isn't.

To show that $Space(n)$ isn't closed under Karp reductions, the suggested technique (both in the solutions given at my place of study as well as those given at many other universities) is to assume we have a TM that decides language $L$ in $Space(n^2)$. Now take an encoding $enc(x)$ of some $x$ in $L$ with $|enc(x)| = n$ and blow it up (in quadratic, thus polynomial time) to an encoding $enc'(x)$ of $x$ with $|enc'(x)| = n^2$ by padding the smaller encoding with $n^2-n$ padding symbols. Now we take the same TM, and it can decide $L$ in space linear in $enc'(x)$ by ignoring the padding stuff and just operating on $enc(x)$. This implies that $Space(n^2) \subseteq Space(n)$, which contradicts the space hierarchy theorem, so $Space(n)$ can't be closed under Karp reductions.

My problem here is that while I realize that we can easily show that $NP$ is closed under Karp reductions, it somewhat confuses me regarding what this says about $NTime(s(n))$. It seems to me that this approach will also work to show that $NTime(s(n))$ isn't closed under Karp reductions for any time-constructible function s(n) using the time hierarchy theorem, or am I mistaken here?

You're not mistaken. The reason NP is different is that it's defined as the union of $NTime(n^k)$ for all $k \geq 0$, so the set of upper bounds on the running time $s(n)$ is closed under substituting polynomials.


Reducing INDSET and MAXCUT to 3SAT Given a graph and an integer $k$ is there an independent set larger than $k$ is INDSET problem and is there a cut larger that $k$ is the MAXCUT problem. Is there standard way to convert to 3SAT from these problems that preserves number of solutions? I have only seen reductions other way in standard texts. Since all these are NPC there should be a way to convert back.

$\mathcal{INDSET}$ $\leq_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $x_v$.

For each edge $uv\in E$, create a clause $\lnot x_u \lor \lnot x_v$

Now, to assure that there exist exactly (or more than) $k$ variables assigned to $\mathrm{TRUE}$, we need to sum over all the assigned value ($\mathrm{FALSE}$ as $0$, $\mathrm{TRUE}$ as $1$):

We use half-adder and full-adder. Note that each circuit gate using some Boolean operation like $C = A \oplus B$ can be transformed into $\mathcal{3SAT}$ clauses easily.

To compare the obtained sum and $k$, it is straightforward from their binary representations (as two arrays of Boolean variables), just scan from left to right (in big-endianness fashion).

$\mathcal{MAX-CUT}$ $\leq_p$ $\mathcal{3SAT}$:

For each vertex $v\in V$, create a Boolean variable $s_v$. A cut is then described by a partition of the vertex set $V=S\cup (V\setminus S)$, where $v\in S$ iff. $s_v=\mathrm{TRUE}$.

For each edge $e=uv\in E$, create a Boolean variable $c_e$ and some clauses to force that $c_e=(s_u\neq s_v)$. So, $c_e=\mathrm{TRUE}$ iff. $e$ is crossing $(S, V\setminus S)$.

Then, we use half-adder and full-adder as before to count the number of crossing edges. Lastly, compare as before.


What is the maximum number of shortest paths between any pair of vertices in a chordal graph? A graph $G$ is chordal if it doesn't have induced cycles of length 4 or more. Chordal graphs are precisely the class of graphs that admit a clique tree representation. A clique tree $T$ of $G$ is a tree in which the vertices of the tree are the maximal cliques of $G$. An edge in $T$ corresponds to a minimal separator. In general, $G$ can have more than one clique tree representing it. A graph is said to be geodetic if the shortest path between any pair of vertices is unique.

Consider a chordal graph $G$ in which every minimal separator is a singleton set. I can prove such a graph is geodetic, but this property doesn't hold once minimal separators get larger. For example, consider a graph with a minimal separator $S = \{2,3\}$ of size 2 below. It already has 2 shortest paths between the vertices 1 and 4.

In fact, consider two adjacent vertices in a clique tree of a chordal graph. Let $S$ be the minimal separator corresponding to the edge between them. Now consider two distinct vertices $u$ and $v$ in these adjacent cliques such that $u,v \notin S$. The number of shortest paths from $u$ to $v$ is the size of the minimal separator between them. This is because, roughly speaking, it takes one step to move from any vertex in a clique to a separator, and likewise any vertex in a clique can be reached with one step from the separator.

Finally, consider an example like below. The graph has 3 maximal cliques, and the minimal separators are $\{ 4,5 \}$ and $\{ 2,3 \}$. Now the number of shortest paths from 1 to 6 is $2 \times 2 = 4$.

  Given a connected chordal graph $G$ (with no loops nor parallel edges), what is the maximum number of shortest paths there can exist between any pair of vertices? How can it be bounded (in terms of $n$ and $m$)?

It can be exponential in $n/2$.  The following graph has $2^{(n/2) - 1}$ shortest paths between the endpoints:

This graph has $2^{(14/2)-1} = 2^6 = 64$ different shortest path, each corresponding to a selection of "ups" and "downs".


Estimating time cost for sorting algorithm given the average time for sorting of 1000 elements Assuming that an implementation of a sorting algorithm takes 0,01 seconds to sort 1000 elements, how long would it take to sort 100 million elements?

What do I need to know about my the algorithm to estimate the time? Is its time complexity given in $\mathcal{O}$-notation sufficient to find that out?

In my example the algorithm is Bubblesort, of which I know that it is extremely inefficient for sorting long lists and I also know that the average case is $\mathcal{O(n^2)}$, however I am unsure how much depends on the concrete implementation, which is not given. I also am interested in the general approach towards the problem.

My train of though is that since Bubblesort is $\mathcal{O(n^2)}$ in the average case, the time cost is $c\cdot n^2$ for some constant time cost of an elementary operation $c$ (can I even assume that it is constant?).
So $c \cdot 1000^2=0,01 \iff c=10^{-8}$, which would instantly give me acces for time cost for any list length $n$. I am aware that $\mathcal{O(n^2)}$ does not mean that $n^2$ is the only factor in the cost equation, but it is the leading one as $n$ grows. Is this the correct approach?

It is in general impossible to interpolate the running time of algorithms even if you know their asymptotic running time. There are many reasons for this – here are two:

The running time of an algorithm is usually composed of many different terms. For example, it could be of the form $An\log n + Bn$. This running time doesn't scale like $n\log n$, since for small $n$ the $Bn$ term might be important, whereas for large $n$ it might be negligible.
Resource access times do not scale in $n$, but rather jump. When $n$ is small, everything fits into the smallest cache, so data access is very quick. When $n$ gets larger, you need to use a larger cache, so all at once data access becomes slower. When $n$ gets even larger, you need to use main memory (or even beyond), and data access becomes even slower.

In some cases these reasons do not apply. For example, you might be interested in values of $n$ for which one part of the algorithm clearly takes almost all the time, and you can easily estimate how it scales in $n$; and furthermore, memory consumption is minimal so increasing $n$ doesn't result in reduced data access behavior. In such cases it is possible to extrapolate the running time.

An extreme example is when you are estimating some quantity empirically, and $n$ is the number of samples. The running time of such a program scales linearly with $n$.


Can exactly one of NP and co-NP be equal to P? Maybe I am missing something obvious, but can it be that P = co-NP $\subsetneq$ NP or vice versa? My feeling is that there must be some theorem that rules out this possibility.

No, because $\mathsf{P}$ is closed to complement this cant be, and we even know that $\mathsf{P}=\mathsf{NP} \implies \mathsf{NP}=\mathsf{co\text{-}NP}$.

Let us assume that $\mathsf{P}=\mathsf{NP}$, and let $L \in \mathsf{co\text{-}NP}$, thus $L^c \in \mathsf{NP}$. We assumed $\mathsf{P}=\mathsf{NP}$, and therefore there exists a TM $M$ s.t. $L(M)=L^c$. If we take the "complement" of $M$, that is a machine $M'$ which is identical to $M$ except its accept and reject states are reversed, we get that $L(M')=(L^c)^c=L$, and thus $L$ is in $\mathsf{NP}$.

This shows that, under the assumption that $\mathsf{P}=\mathsf{NP}$, we get $(\mathsf{P}=)\mathsf{NP}=\mathsf{co\text{-}NP}$ and thus $\mathsf{P}=\mathsf{co\text{-}NP}$.


Automatically merging relational data Background
Semiautomated file merging is a critical part of version control systems (all the ones I've used anyway!). This is usually accomplished on textual source code without the tool understanding the underlying language – although semantic merging also exists.
I'm interested in whether merging relational data has been researched, and what the findings have been.
Specifically, I'm imagining that a single relational database is "forked" in to two (or more) independent copies. That independent changes are made to these copies, and that we then want to recombine these databases in to one again, which reflects the changes in each.
What this question isn't
I'm not asking a question about specific technologies here, although that would be interesting. I'm definitely not asking about SQL based technology sepecificaly. I'm also specifically interested in relational data, and not tree data like XML, JSON, or ASTs, etc.
I'm also not asking about integrating heterogeneous databases or information stores, which seems to be the subject of Data integration. For the purposes of this question, it can be assumed that the databases will have the same schema and this doesn't change.
Some ideas about how this might work
Relational data is, basically, sets. Sets, in principle, have (several) sensible merge semantics, even when the common base isn't known, such as for a commutative replicated datatype set.
There are obviously some basic issues, such as generating identities. If identities are simple incrementing numbers, then these become extremely hard to merge. This problem seems to be solved by using globally unique identifiers.
Incrementing identifiers seems to be a specific case of a more general problem. It is an example of inserting a new fact in to the database that has been derived from the current state of the database.
In general, I suspect that any fact added to the database that is derived from the existing facts in the database, rather than simply new information collected from the outside world, is a potential source of difficulty during a merge. I wonder if this is a huge problem, or one that can be avoided for the most part by something like normalisation?
For example: if we adjust a balance by looking up the current balance and adding or decrementing, then this is hard or impossible to merge. However, if we store individual increments and decrements, this information is trivial to merge. When we need the balance, we should compute it from the data we've got.
Problems also arise for integrity constraints. Following naive set merging, a primary key may no longer be a primary key. However, it seems like it might be possible to automatically determine where this could happen from the database schema, and then have the user choose a resolution scheme, or default to some sensible one if such a schema exists. Note: it is possible to keep an audit, show conflicts as they arise, and have a user revert a decision later, as is done with version control systems.

I'm interested in whether merging relational data has been researched, and what the findings have been.

Here are several papers mainly on the tree-to-tree editing problem. A lot of good stuff is related to XML documents.

Diffing, Patching and Merging XML Documents
The tree-to-tree editing problem
The Tree-to-Tree Correction Problem
Simple Fast Algorithms for the Editing Distance between Trees and Related Problems
Change Detection in Hierarchically Structured Information
Efficient Snapshot Differential Algorithms for Data Warehousing
Detecting Changes in XML Documents
Meaningful Change Detection in Structured Data

A record in a database can be considered a simple tree of just a single row of children (the fields) or perhaps extending to the relations the record points to. With that you can do tree diffing/merging using the techniques outlined in these papers, and adding to it any column-specific string diffing techniques.

You could then add extra database-specific heuristics to the diffing system to make it more useful. For example, you have the extra metadata of the schema of the database, which provides a lot of information.


given a weighted, directed graph. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}? This is the 24.1-5 question in CLRS. I'm having a hard time understanding the questions and also how to solve it. δ(u,v) is defined as the shortest path weight from u to v if there exist a path from u to v.

Let G=(V,E) be a weighted, directed graph with weight function w:E→R. Give an O(VE)-time algorithm to find, for each vertex v∈V, the value δ∗(v)=Min u∈V{δ(u,v)}.

What I'm confusing about this question is what is δ∗(v) suppose to be. I also found the answer online but still don't really understand why it is like that. Since this is an exercise in the Bellman-Ford algorithm of CLRS. the answer said to change the RELAX operation of the algorithm. The RELAX operation in Bellman-Ford is what help achieve the shortest path weight after you run this V time for each edge in E.

the ORIGINAL-RELAX operation supposes to be like this:

RELAX(u, v, w)
if v.d > u.d + w(u,v)
   v.d = u.d + w(u,v)
   v.pi = u.pi

With v.d and u.d being the upper bound for the shortest path from source to u and v. v.pi is supposed to be its predecessor for the current upper bound.

The answer said to change the RELAX operation to this.

MOD-RELAX(u, v, w)
if v.d > min(w(u, v), w(u, v) + u.d)
   v.d = min(w(u, v), w(u, v) + u.d)
   v.pi = u.pi

I need some explaination to what the problem is asking for and why this answered it.

What is the question?

A vertex v ∈ G.V can have shortest paths from other vertices u ∈ G.V - {v}. What is the minimum of all these paths to v? This is *(u, v). You  have to calculate this minimum value for all the vertices

Why the solution works?

To get to a vertex v you have 2 options:

Take minimum incoming edge from u to v i.e. w(u, v)
Get to u and then take the edge from u to v i.e. u.d + w(u, v)

You have to find the minimum of these 2 options. So min(w(u, v), u.d + w(u, v))

In either of the cases the v.pi will be u


How many different max-heaps exist for a list of n integers? How many different max-heaps exist for a list of $n$ integers?

Example: list [1, 2, 3, 4]

The max-heap can be either 4 3 2 1:

    4
   / \
  3   2
 /
1

or 4 2 3 1:

    4
   / \
  2   3
 /
1

I did not find a closed form, but according to this entry in the Online Encyclopedia of Integer Sequences the sequence starts with

1, 1, 1, 2, 3, 8, 20, 80, 210, 896, 3360, 19200, 79200, 506880, 2745600, 21964800, 108108000, 820019200, 5227622400, 48881664000, 319258368000, ...

You can find a not-so-nice recursion in the OEIS database. Basically the idea is as follows. The root of an $n$-ary heap is always the maximum. The two subtrees hanging off the root are again maxheaps. Their size depends on $n$, is a bit tedious to compute the sizes $n_1,n_2$ (see the OEIS entry), clearly  $n_1+n_2=n-1$. We can now pick, which elements go to the left heap and which go to the right heap. There are ${n-1 \choose  n_1}$ ways how to distribute the elements. This gives the recurrence

$$ a(n)= {n-1 \choose  n_1} a(n_1)a(n_2).$$


Exponential example for simplex used in SMT solvers The original simplex algorithm requires an exponential number of pivot operations in the worst case, e.g., if run on the Klee-Minty example [3,4].

What about the simplex algorithm used in SMT solvers [1,2]? Could you provide an example where it requires exponential time?

The algorithm I have in mind is by Bruno Dutertre and Leonardo de Moura in [1,2], and is presumably used in all modern SMT solvers. The algorithm introduces one slack variable per constraint, the slack variables have lower and upper bounds; and the problem is that of feasibility instead of optimization.

I tried to modify the Klee-Minty example [3,4], but failed so far.
Kroening & Strichman contains this question as an exercise, so you can also hint instead of answering.

Integrating Simplex with DPLL(T) by Bruno Dutertre and Leonardo de Moura:
Decision Procedures: an Algorithmic Point of View by Daniel Kroening and Ofer Strichman
Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method
Picture of the Klee-Minty cube:

Here, you can find hard examples for DPLL.
http://www.ioc.ee/~tarmo/tday-torve/itsykson-slides.pdf

For instance, it can be very slow for Tseitin formulas and for some unsatisfaisable formulas (it will try many solutions).

I hope it will give you some hints :)


Is a set of acyclic |V| - 1 light edges always a Minimum Spanning Tree? I am trying to prove the algorithm for Question 5 in this practice exam.
I am trying to prove this algorithm with the following three claims:

Suppose we have a graph G, a minimum spanning tree T, and a set of edges A that is a subset of T.  Suppose that we also have a cut C = (S, V - S) that respects A, and edge e = (u, v) is a light edge for that cut.  Then, A $\cup$ { e } is also a subset of some minimum spanning tree T'.

Suppose we have a graph G with |V| vertices that has a minimum spanning tree.  Suppose we also have a set of |V| - 1 edges = <$e_1$, $e_2$, ..., $e_n$>, such that each edge is a light edge for some cut C, and these edges do not form a cycle.  This set of edges must form a minimum spanning tree.

The algorithm given will generate a set of acyclic |V| - 1 edges each of which is light for at least one cut; thus, it will generate a minimum spanning tree.

The first and third claims are easy to prove, but I am unable to prove the second claim.  This is what I have so far:

Trivially, the set of edges must form a spanning tree - it is not possible to have |V| - 1 edges and no cycles without connecting all |V| vertices.
This spanning tree must also be a minimum spanning tree: suppose we have a new empty set of edges A.  A is trivially a subset of some minimum spanning tree for G.  A $\cup$ { $e_1$ } is also a subset of some MST by Claim 1 (because $e_1$ is a light edge for cut C which trivially respects the empty set A).
Now let us examine edge an edge $e_2 = (u, v)$ that is incident to one vertex touched by $e_1$.  We can assume without loss of generality that there is currently no edge incident to $v$.  [I can't prove that $e_2$ is safe to add].

I was wondering if this claim is even correct - and if so, how I can go about proving it.

The answer to the question in the title, "Is a set of acyclic $|V|-1$ light edges always a Minimum Spanning Tree?" is no. That is, the second claim in the question is not true. Hence, the third claim is not true, either.

Here is a simple counterexample. Let $H$ be a graph the complete graph with 4 vertices, $\{a,b, c,d\}$ and weights, $ab\rightarrow 1$, $cd\rightarrow 1$, $ac\rightarrow 2$, $ad\rightarrow 2$, $bc\rightarrow 2$, $bd\rightarrow 2$. The weight of a minimum spanning tree $\{ab, ac, cd\}$ is $1+1+2=4$. Consider the spanning tree made by the 3 edges, $\{ac, bc, bd\}$, each of which is light for the cut $\{a, b\}, \{c,d\}$. However, the weight of this spanning tree is $2 + 2 + 2 = 6$, which is greater than $4$.

One might be wondering why it might be so hard to come up with a counterexample. Part of the reason might be that if the weights of edges of $G$ are different, then $G$ has only one minimum spanning tree, which includes all light edges for every cut.


Confusion about example in Raft consensus paper In part (c) of Figure 8 in this paper http://ramcloud.stanford.edu/raft.pdf, I am confused how S1 knows that the current term is 4 when it restarts and is elected leader.

Here is the sequence as I currently understand it:

S1 is elected leader for term 2, partially replicates a request, and then dies.
S5 is then elected leader for term 3, receives but does not replicate a request and then dies.
S1 restarts, (still thinking it is term 2), is elected leader (for term 4?), and then replicates a term 2 request to a majority of nodes, but does not commit.

My confusion is in step 3. When S1 reawakens, it is elected leader for term 4, even though it hasn't been active since term 2. How does S1 know that it is now term 4?

Citation for linked paper:

O NGARO , D., AND O USTERHOUT, J. In search of an understandable consensus algorithm. In Proc ATC’14, USENIX Annual Technical Conference (2014), USENIX.

Server 1 does not immediately know the term when it starts up. Terms and other state such as commit indexes are (normally) held in memory and shared only via RPCs. Therefore, even though server 1 died when it was the leader for term 2, it won't even know about term 2 when it starts back up, let alone term 4.

The way server 1 will learn the term is via AppendEntries and RequestVote RPCs. When server 1 starts, it will initialize its term to 1. If it receives a heartbeat from node 5 before it dies, the heartbeat (an AppendEntries RPC) will contain server 5's term: 3. Given that information, when server 5 dies and server 1's election times out, it will transition to candidate, increment its term to 4, and start the election. This is the likely way in which this scenario might occur since server 2 could also win an election with or without server 1 being alive.

The reason server 1 would need to have been alive for some period of time prior to server 5 crashing is because of server 1 starts a new election immediately after it starts (without having communicated with any other node) it will lose the election since its term (1) will be less than the term of all other servers. In that scenario, server 2 would also start an election and ultimately win before server 1 can update its term and start another election.


Finding the area of a rectangle in python Q: Standard input consists of exactly four integers, first x1 and y1, the coordinates of the bottom-left corner of a rectangle, then x2 and y2, the coordinates of the top-right corner.
Write a Python script named area-of-rectangle.py which outputs the rectangle’s area.
I'm SO stuck and have no clue what I'm doing. I wrote this
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())
bottom_left = (x1 + y1)
top_right = (x2 + y2)
area = bottom_left * top_right
print(area)
IT'S ALWAYS WRONG. Please help :(

To calculate the area of a rectangle on a coordinate system, you need the length between x1 and x2, and the length between y1 and y2.
x1 = int(input())
y1 = int(input())
x2 = int(input())
y2 = int(input())

xDiff = abs(x1 - x2) # Using absolute value to ignore negatives
yDiff = abs(y1 - y2)

area = xDiff * yDiff

Edit: Forgot to mention, if x2 is always greater than x1, and y2 is always greater than y1, instead you can just use xDiff = x2 - x1 and yDiff = y2 - y1


How to find the smallest $r$ such that $o_r(n) > \log^2(n)$ in polynomial time? Defining
$$
o_r(n) = \min \left\{ \hspace{1mm} k \in \mathbb{N} \hspace{2mm} | \hspace{2mm} n^k \equiv 1 \hspace{3mm} (\text{mod } r) \hspace{1mm} \right\}
$$
How can we show that finding the smallest $r$ such that $o_r(n) > \log^2(n)$ can be done in polynomial time?

It appears you are asking because you are interested in understanding the famous "PRIMES is in P" paper and why its algorithm runs in polynomial time.  Finding such an $r$ is exactly step 2 of their algorithm.

As was explained to you previously on Math.SE, the paper explains why its algorithm runs in polynomial time.  The explanation is terse and assumes the reader will be able to make the missing connections, but the key ideas are there.  If you keep reading in the paper it presents the crucial fact: the smallest such $r$ has size at most $r \le \max\{3, \lceil \log^5 n \rceil\}$ (see Lemma 4.3, which is just a few paragraphs after the statement of the algorithm).  Consequently, there is a very simple algorithm to find such an $r$: try each $r$ in turn, i.e., try $r=1$, then $r=2$, then $r=3$, checking each candidate value of $r$ to see if it satisfies the condition.  Output the first one you find that satisfies the condition.  Thanks to the fact in the paper, you'll only need to try $O(\log^5 n)$ many such $r$, which is polynomially many.  Moreover, you can check the condition for a given $r$ in polynomial time.  Thus, the total running time is polynomial in $\log n$.

In the future, if you have a question about some aspect of the paper, please tell us in the question what paper you are reading.  More generally, tell us about the context around your question and the motivation. Also, when asking about some aspect of a paper, I encourage you to read the entire paper before asking -- sometimes the answer to your question might be found later in the paper.


Is programming an emulation of the real world? Assume that we have a car in the real world, this car would be composed of atoms, and we can do operations on this car (for example: we can move the car or change its color, etc.).
And assume that we have a car object in the computer world (in RAM), this car object obviously is not a real car but rather a representation of a real car, but we can imagine that this car object is a real car, and we can also do operations on this car object (for example: we can move the car object or change its color, etc.).
Now if we want to for example change the color of the car in the real world, we have to manipulate some of the atoms that compose the car to accomplish that.
And to change the color of the car object in the computer world (in RAM), we have to manipulate some of the bits that compose the car object to accomplish that.
However, one difference that I can think of between the real world and the computer world is that in the real world the car is visible to people, however in the computer world the car object is not visible to people (you have to paint the car object on the screen to make it visible to people).
So can we think of programming as an emulation of the real world? more specifically, can we think of the real world as "real world RAM" that can contain any object (these objects would be composed of atoms) in the same way that RAM can contain any object (these objects would be composed of bits)?

This is a third true, a third false, and a third unknown.
Why you might think its true
As you have stated, it does intuitively makes sense that any kind of "computation" or "effect" in the real world has an equivalent computation in the computer. After all - the world we know is compromised of atoms and such, and it makes sense we can store such data in bits. If im not mistaken, the Church-Turing hypothesis that was based on this intuition hypothesizes that anything that can be done in the real world can be done in a computer
Why we might think its false
Think about our world - it has a lot of people, which independently and simultaneously do things. This kind of behaviour is not really natural for a computer - a computer can only process one thing (or at most a handful of things, if it has a few cores) at once. This leads us to think it might be impossible to think of the world as a giant computer.
Why we still don't know, and will probably never know
Physics is a branch of science that always develops. There is always more to uncover about our universe and its underlying mechanisms. Therefore, there will always be a way to create a newer and mpre sophisticated computer that can do more things. For example, the recent developments for quantum computers might change things up: In a quantum computer there are things that can be computed faster than in a normal computer. In fact, a quantum computer is capable of doing something similar to parallel computing (a common misconception is that it does compute in a parallel way, but actually it does something else that creates this effect).
This means that both statements for why it could be true and why it could be correct! It might be true that normal computers can't emulate all of the stuff that can be done in the real world, but don't know whether it will still hold for a newer computer based off of a brand new idea in physics that would be developed in a few hundred years from now.
Still, this is only my own opinion. If you want more (and probably better) answers, you might want to consider asking this to philosophers.


Boolean Logic Equation How can I prove this. what is the way? im up to the second last line. and i dont actually know how can x * (1 + y) then the y just disappears into x * 1.

x + x * y = x
x + x * y = (x * 1) + (x * y)
          = x * (1 + y)
          = x * 1 [THIS LINE]
          = x

thanks

In Boolean Algebra we have:

\begin{align*}
a \cdot b &= \min{(a,b)}\\
a + b &= \max{(a,b)}
\end{align*}

So, by the first definition it's obvious that:

$$ x \cdot 1 = \min{(x,1)} = x$$

Since $x \leq 1$.

By the same reasoning:

$$1 + y = \max{(1,y)} = 1$$
since $y \leq 1$.

So you have:

\begin{align*}
x + x \cdot y &= (x \cdot 1) + (x \cdot y)\\
&= x \cdot \color{red}{(1 + y)}\\
&= x \cdot \color{red}{1}\\
&= x \cdot 1 = x
\end{align*}


Prove Queue Automaton is equivalent to Turing Machine A deterministic queue automaton (DQA) is like a PDA except the stack is replaced by a queue. A queue is a tape allowing symbols to be written (push) on the left-end and read (pull) on the right-end.

Actually I've proved that a 2-tape Turing Machine can simulate the DQA. Now I'm proving the DQA can simulate Turing Machine TM. Let the queue store all the input and the right-end symbol is the one being read. Suppose $a$ is the right-end symbol in the queue.

For the transition $\delta(q,a)=(r,b,L)$ in TM, it's easy to simulate. Just pull $a$ and push $b$. Now the right-end symbol would be the symbol on the left of $a$. It's like move the head in TM to the left.

My problem is I cannot find a way to simulate the transition $\delta(q,a)=(r,b,R)$. Since the symbol on the right of $a$ is actually the left-end symbol, how can I let this symbol move to the right-end? I spend several hours on this and I think answers on Internet are not very clear. Could anyone give me some hint?

It is obvious that you can't handle all the right moves at the same time, so the trick is to use a special symbol to mark the head position ($\#$) and place it on the left of the symbol under the head:

queue: 0100100#1  equivalent to tape: __0100100[1]___

Now you pop the symbols from the right and re-push them on the left but with one symbol of delay (you buffer one symbol using the internal states). When you read a symbol $x$ and the internal buffer contains $z$ then you re-push $z$ on the queue:

queue: 0100101#1  pop:   buf:* (initially the buffer contains the * marker, see below)
queue:  0100101#  pop:1  buf:*
queue:  *0100101  pop:#  buf:1

When you pop $\#$ then you know that the symbol $x$ in the (internal) buffer is the symbol under the head,  and you can apply the corresponding transition:

** if the transition says to write symbol $y$ and goto to $Right$ then you push $\#$ and the $y$ on the left of the queue.

 queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Right
 queue:  0#*0100101   pop:   buf:
 queue:   0#*010010   pop:1  buf:
 queue:    0#*01001   pop:0  buf:1
 queue:    10#*0100   pop:1  buf:0
 ...

Then you continue the pop-push operations until you find again the $\#$.

** if the transition says to write symbol $y$ and goto to $Left$ then you can simply push $y$ on the left of the queue and keep the $\#$ in the internal buffer, read the next symbol and apply another transition until you find a Right move again:

queue:    *0100101   pop:#  buf:1  apply transition Write 0 go Left
queue:    0*010010   pop:1  buf:#  apply transition Write 1 go Left
queue:    10*01001   pop:0  buf:#  apply transition Write 1 go Right
queue:  1#10*01001   pop:   buf:
...

The special symbol $*$ marks the begin/end of the tape and you can use it to handle the tape expansion on both directions. Now, you should be able to discover how by yourself.
And if you want to be rigorous, you should also consider the special initial case in which the queue doesn't contain the head symbol #.


creating a binary search tree (manual) I've been given the following values to add to a binary search tree (in the order given)

56, 35, 55, 58, 29, 15, 16, 5, 71, 92, 69, 95

and this is what my tree ended up like:

but apparently it's wrong?

The property that makes a binary tree a binary search tree is that for every branch labeled $x$, all of the labels in the left subtree are smaller than $x$ and all of the labels in the right subtree are greater than $x$.

If you look at your tree, that property is violated in many places. For example, $5$ is in the right subtree of the node labeled $15$, yet $15 \not < 5$.


How do I reconstruct the forest of syntax trees from the Earley vector? Using the Earley vector as a recognizer is quite straightforward: when the end of the string is reached, you just have to check for a completed axiomatic production started at position 0. If you have at least one, then the string is accepted.

Using the Earley vector to reconstruct the parsing tree(s) is less obvious. Actually, I cannot figure out how an algorithmic procedure would work, moreover the only references I found were either vague or super-technical. Could anybody shed some light on it?

I am using terminology and notations from Earley's paper. It is possible that the description you read is different.

It seems frequent that general CF parsing algorithms are first
presented in the form of a recognizer, and then the information
management needed to actually build parse trees and parse forests is
sort of added as an afterthought. One reason may be that keeping the
information needed to construct the shared forest require cubic space
$O(n^3)$ where $n$ is the length of the input string being parsed, but
the space requirement is only square $O(n^2)$ for recognition, when this information is
not preserved. The reason for this space complexity increase is quite
simple: the parse forest size can be cubic.

The worst case time complexity is $O(n^3)$, as is well known.

The best reference for Earley's algorithm is of course Earley's paper,
but it is not very explicit about building the parse forest. This can
actually be a messy business, much more so than the fast talk of
section 7 page 101 will let appear. To be true, Earley does not talk
of parse forest, or of forest, but of "a factored representation of
all possible parse trees". And there is a good reason for that: if he
tried to produce a forest according to his grammar, his space (hence
time) complexity bound would climb to $O(n^{s+1})$ where $s$ is the
size of the longest rule right-hand-side. This is why other algorithms
use grammars in binary form (not necessarily Chomsky Normal Form (CNF)).

Actually, Earley uses binary form implicitly, because that is
necessary for the cubic time complexity. This is one of the major
roles of the rule dot in states. But this implicit binary form
produces parses and forests according to the binarized grammar, not
to the original one, which, I fear, is a major source of obscurity. This is detailed further below.

One good way to understand how the forest is obtained is probably to
look at it in a simpler case, the CYK algorithm. It is also often
described as a recognizer, and the parser aspect is added at the end.
You can look at the description in wikipedia. The information needed
to build the forest is what they store in the table of "backpointers".
Backpointers are essentially pointers to substrings (an associated
symbol) that form the constituents of a string according to some
rule. They give all possible ways of parsing a substring. Recall that
CYK uses binary form, usually CNF, so that things are simpler. The CYK
parser has fundamentally the same dynamic programming structure as
Earley, but is much simpler. So understanding it well can be a
significant help.

Going back to Earley's algorithm, I do not believe you need Earley
vector to decide acceptance or to build parse trees and forests.  What
Earley calls vector in his paper appears only in page 97, in third
paragraph of implementation. It is only a device to speed up the
search of states pointing back at some given string position k, in
order to get a better complexity. But all the information is in the
state sets, implemented as lists of states. However, this information
is not sufficient to build the forest of parse trees, because the
algorithm does not keep track of the way(s) a state may be
obtain. Indeed, the vector is even used to efficiently discard a state
already found, independently of how it was found.

In section 7 of Earley's article, he explains that in order to "make
the recognizer into a parser", i.e. to be able to recover parse trees,
it is necessary to keep track of the way completions are done.

  Each time we perform the completer operation adding a state
    $E\rightarrow \alpha D.\beta \; g$ (ignoring lookahead) we construct a pointer from the instance of $D$ in
  that state to the state $D\rightarrow \gamma. \; f$ which caused us to do the
  operation. This indicates that $D$ was parsed as $\gamma$. In case
  D is ambiguous there will be a set of pointers from it,
  one for each completer operation which caused $E\rightarrow \alpha
D.\beta \; g$ to be added to the particular state set. Each symbol in
  $\gamma$ will also have pointers from it (unless it is terminal),
  and so on, thus representing the derivation tree for $D$.

Note that in this text, $f$ and $g$ are indices in the parsed string,
pointing where the recognition of the rule left-hand side started (as
the right-hand side symbol had been predicted. So $f$ is the string
index where the recognition of $D\rightarrow \gamma$ started, and it
ended at index $g$. These "completion pointers" are the Earley
equivalent of the backpointers described (not too well in
wikipedia) for the parser version of CYK.

From such a pointer (as described in the quote) we know that the $D$
in the rule instance $E\rightarrow \alpha D.\beta \; g$ can itself be
developped into a tree (or forest) that parses the input string $w$ from
index $f+1$ to index $g$, which we note $w_{f+1:g}$. The nodes immediately below $D$ are given by
the rule $D\rightarrow \gamma$. By looking for the completion that lead
to $D\rightarrow \gamma. \; f$ we can then find other such pointers
that tell how the last symbol of $D$ was obtained, and hence more
information on the possible parse trees. Also by looking at the
completion that recognized the symbol before last in an earleir state
sets, you find how it was obtained, and so on.

Assuming you kept all the needed pointers as indicated in the paper,
you can get all the shared tree representations starting from the last
symbol recognized by the parser, which is of course the initial symbol
of the grammar.

But I also skipped the messy part. Suppose you have a rule
$U\rightarrow XYZ$, which I choose with a right hand side longer than
2 symbols, and another rule $W\rightarrow UV$, for an ambiguous
grammar.

It may well happen that the parser will parse $w_{f+1:g}$ into $X$,
$w_{g+1:h}$ into $Y$ and both $w_{h+1:i}$ and $w_{h+1:j}$ into
$Z$. So, with the rule $U\rightarrow XYZ$, Both $w_{f+1:i}$ and
$w_{f+1:j}$ parse into $U$.

Then it may also be that both $w_{i+1:k}$ and $w_{j+1:k}$ both
parse into $V$. Then, with the rule $W\rightarrow UV$, the string
$w_{f+1:k}$ parse into $W$ in two different way, which correspond to
an ambiguity of the grammar.

Of course, to avoid repeating computations, Earley's algorithm will
attempt to share as much as possible of the two parsing computations.
What it will actually share is obviously the recognition (and parsing)
of $w_{f+1:g}$ and $w_{g+1:h}$ into $X$ and $Y$. But it will actually
do a bit more: it will also share the beginning of the two distinct
parses that recognize $U$ with the rule $U\rightarrow XYZ$. What I
mean is that the state $U\rightarrow XY.Z \; f$ will be found only
once (with respect to what I am describing), in state set $S_h$. It
will be a common part of the two parses. Of course, things will
temprarily diverge while parsing the $Z$ since they correspond to
distict substrings, until they converge again when everything parses
into W, when the state $W\rightarrow UV. \; f$ is produced twice in
state set $S_k$.

So the forest of syntax trees can be a very strange one, with kind of
siamese twin subtrees that may share the first two edges of some node, but
not the third edge. In other words, it may be a very awkward
structure. This may explain why Earley calls it "a factored representation of
all possible parse trees", without being more specific.

Any attenpt to surgically separate the siamese twins, without changing
the grammar will result in increased complexity. The right way to do it
is to binarize the grammar.

I hope this will help you. Let me know.  But I do insist that a good
understanding of CYK parsing can help. There are other algorithms, simpler than Earley's, that can parse all CF languages efficiently.

You may find more general info on this parse forest issue in two other answers I gave: https://cstheory.stackexchange.com/questions/7374#18006 and https://linguistics.stackexchange.com/questions/4619#6120. But they do not go into specific details of Earley's algorithm.


Language of TMs such that one state is visited most often To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some $M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where $Q$ is the finite state set, $\Sigma \subset \Gamma$ are the input and working alphabet, $q_0, q_F$ are the initial and final states, and $\delta : Q \times \Gamma \times Q \times \Gamma \times \{L,N,R\}$ is the transition function. I am talking about single-tape TMs without input or output tape, so the initial configuration of input $w$ is just $B^{-\omega} q_0 w B^\omega$, where $B$ is the blank symbol.

The language I am considering is $L$ of all Turing machines $M$ which satisfy the following: There is a state $q$ of $M$ such that on the run of $M$ on the empty word $\varepsilon$, $q$ is visited more often than any other state.

"More often" talks about the cardinality, i.e. $q$ is visited more often than $p$ if $p$ is visited $n$ times (finitely often) and ($q$ is visited infinitely often or $q$ is visited finitely often but $>n$ times).

I came up with this language as an exercise for students, when I found that neither I nor any colleague I asked could come up with precise decidability results.

It is clear that $L$ is not coRE and therefore undecidable. We can, for example, reduce the epsilon halting problem $H_\varepsilon$ to $L$ by inserting a new state and have the TM visit that state once after each step of computation.

Unsolved so far is the question whether $L$ is RE. When allowing multiple tapes, it is not, as we can reduce $\overline{H_\varepsilon}$ to $L$. However, for single-tape TMs, our last guess was that it is enumerable by using the fact that a positive input which does not halt has to stay in a single state forever and can only expand the tape into one direction from that point on. We could not come up with an exact solution so far though.

After a deleted (wrong) answer I thought  about the following to prove that $L$ is RE for single tape Turing machines.

As you said in the question, the problem is "recognizing" $M \in L$ that doesn't halt.

Note that a non-halting TM $M \in L$ not necessarily must expand the tape; for example:

q,[ -> q,[,R
q,a -> q,b,R
q,] -> q,],L
q,b -> q,a,L
causes an endless ping-pong in the same state q
...[aaaaa]....
   ^head

Also note that a non-halting TM $M \in L$ can expand the tape without changing its state; for example:

q,[ -> q,[,R
q,a -> q,b,R
q,B -> q,b,L
q,b -> q,a,L
causes an endless expanding loop:
...[aaaaaBB...

But for both expanding and non-expanding cases, we must have that the Turing machine $M$ must continue forever in the same state otherwise it doesn't belong to $L$ (cardinality constraint).

But the halting problem for one-state one-tape Turing machine, on a blank tape except for a finite number of cells, is decidable. See for example Gabor T. Herman: The uniform halting problem for generalized one-state turing machines. Information and Control; Volume 15, Issue 4, October 1969, Pages 353-367):

-----
Introduction: The uniform halting problem (UH) can be stated as follows: Give a decision procedure which for any given TM will decide whether or not it has an immortal instantaneous description (ID). An ID is called immortal if it has no terminal successor.
... we assume that in an ID the tape must be blank except for some finite number of squares ...
In this paper we show the solvability of the UH for one-state TM's ...
-----

So, to enumerate the $M_i \in L$ start a dovetailed simulation of $M_1,M_2,M_3,....$.

if $M_i$ halts at steps $n$  then just count the states visited and outputs $M_i$ if there is a most visited state;
otherwise, if $M_i$ doesn't halt at step $n$, and it is in state $q$; decide if the corresponding one-state TM halts or not. If it doesn't halt then $M$ belongs to $L$;...
... otherwise continue the dovetailed simulation (if it halts it will be detected at a later step)


why does relabel take O(VE) time total for unit capacity flow networks? It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from  $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ relabelling operations per vertex, each taking $O(V)$ time, for a total of $O(V^3)$ for all relabelling operations.
I'm interested in what happens to these bounds when we restrict edge capacities to be 1. It is clear that there are no more non-saturating pushes, so only saturating pushes, of which there are always $O(VE)$, remain.
However, I found a 1995 phd thesis by a student of Goldberg that claims (on p 13) that when edge capacities are 1 (and thus all pushes are saturating), the relabelling portion takes $O(VE)$ time instead of the usual $O(V^3)$.
How does this $O(VE)$ result follow?

The $O(VE)$ result actually holds in general, not just for unit edge capacity, hence it has nothing to do with edge capacity being 1.
This result is proven in Exercise 26.4-3 of CLRS, and thus the $O(V^3)$ quoted in the question is not tight.


Is my regular expression and finite automata diagram for this state table correct? So i have some theory of computer science homework and I'm struggling with this question currently. I am given the following automaton:

$Q = \{q_0,q_1\}$.
$\Sigma = \{a,b\}$.
$q_0 = q_0$.
$F = \{q_0\}$.
$\delta(q_0,a) = \delta(q_0,b) = q_1$, $\delta(q_1,a) = \delta(q_1,b) = q_0$.

I have to do two things: draw a state diagram, and write an equivalent regular expression. For now, these are my answers. I think my diagram is correct, but I'm not sure about the regular expression.

My regular expression for now is $(a+b)^*(a+b)$. Any help is very much appreciated.

Your automaton accepts all words of even length, whereas your regular expression accepts all words of positive length. The most common way to express the language of all words of even length as a regular expression is $(\Sigma\Sigma)^*$, where $\Sigma$ is a common shortcut for an arbitrary letter of the alphabet (in your case, $\Sigma$ stands for $a+b$).


Minimum size of largest clique in graph I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this:

  What is the minimum size of the largest clique in any graph with N nodes and M edges?

The hints suggest using Turan's theorem, but it's not clear to me how to get from that to a solution.

How can I solve this problem, either with or without Turan's theorem?

The full questions is here.

Turán's theorem states that if a graph on $n$ vertices doesn't contain an $(r+1)$-clique then it has at most $\lfloor \frac{r-1}{r} \frac{n^2}{2} \rfloor$ edges. You take it from here.


How are similar bits separated? A 1 is an "on" signal, and a 0 is an "off" signal. How does a computer know 01110 is different from 010? Does the computer wait between signals?

The system operates in a synchronized fashion using a shared clock. This removes the ambiguity.


Converting (math) problems to SAT instances What I want to do is turn a math problem I have into a boolean satisfiability problem (SAT) and then solve it using a SAT Solver.  I wonder if someone knows a manual, guide or anything that will help me convert my problem to a SAT instance.

Also, I want to solve this in a better than exponential time. I hope a SAT Solver will help me.

Chapter 2 of the SAT Handbook (by Steven Prestwich) covers how to turn discrete decision problems into CNF, in some depth.  (Unfortunately, I don't think there is a draft version online -- probably best to consult your local library.)  Several of the other references cited in Magnus Björk's quirky overview Successful SAT Encoding Techniques are also useful.

If your problems are continuous, or you are especially interested in systems of inequalities, then other kinds of solvers are more likely to be useful.  As Kyle points out, SMT solvers (such as Z3, Yices, or OpenSMT) might be useful, although traditionally SMT theories tend to be focused on verification of computer software, so SMT solvers usually have great support for things like expressions involving intervals of integers, but may perform poorly on injectivity constraints.  For problems that are naturally expressed as systems of inequalities, CPLEX is the one to beat (it used to be available for academic use for free, and it might still be).  For some combinatorial decision problems (like finding packings of rectangles into a square), constraint solvers such as Minion outperform SAT solvers and are often easier to use.


Is there a shell between the kernel and hardware First and foremost, i know what a shell, kernel is. Now the dilemma.

Today i had my systems viva in college. The examiner asked me is there a shell between the hardware and the kernel. Obviously, i said no, and the gave the usual explanation that the shell is an interpreter, it takes the user input, interprets the command and communicates with the kernel via system calls.

He then says what if i say that there is a shell between the hardware and kernel. I said it can't because there is no point. The job of the kernel itself is to interface with the hardware why will the shell be involved.

Then he started arguing that kernels are itself a set of programs, the how can they run another program. Now i got confused.

So if anyone could clear my query that whether a shell exists or not. And the biggest one, how can a kernel run a program. Is it because the kernel is in memory and its starts the init process and all other programs are run by it

Given the details you have given us, you are of course right.  There is no shell between the hardware and the kernel; that's just silly.  Asking "but what if there were?" would be like asking "but what if pigs could fly?".

It is likely that either there was some misunderstanding or that the examiner is confused.  The former is much, much more likely.

One thing I might critique is your characterization of a shell as an interpreter.  While a shell is an interpreter, not every interpreter is a shell.  I suppose it is possible that the examiner was asking a follow-up question to see if you understand that.

As far as how a kernel runs programs.... read a standard operating system textbook.  The details are adequately covered in any standard OS textbook.

The thing is... I'm not sure why you're asking us. Why not ask your professor or examiner?  We can't tell you what was in your examiner's head.


Is dependency analysis required in order to type a program? I have seen stated in various places that in order to allow an "increase in polymorphism," functional dependency analysis should be performed, and type inference should be used for every declaration group in topological order. It seems like a well-known fact... except that nobody provides any reference or example.

In fact I don't understand what is really meant by this statement. Does it mean that without doing dependency analysis I wouldn't be able to type some programs (i.e. some valid programs would fail type-checking) or only that I would type them with a type that is more specific than what really is?

I'm particularly interested in consequences in a Haskell-like language/type system. In particular during kind inference, is dependency analysis actually necessary to avoid rejecting valid programs? Can you provide an example that wouldn't be well-kinded if typed without performing dependency analysis?

Since kinds are monomorphic I struggle to understand why dependency analysis should matter in this particular case.

Any use of a type anywhere may place constraints on that type. So, in the absence of explicit type signatures (i.e. when doing type inference) it is necessary to perform inference in a way that doesn't allow specific usages of a type in a particular form to "infect" the most general type it may have. This involves a dependency analysis. Consider

id = \x -> x
foo = id 1

Now if we type foo first, we would unify the first argument of id with Int and thus conclude id had type Int -> Int. So therefore we must first type id and then generalize its signature to the polymorphic type forall a. a -> a, and then instantiate that at type Int when we apply it and attempt to unify the argument type with Int.

Hence, dependencies and topological sort!


Proof for Unusual QuickSort Partition Scheme TL:DR
I wrote code for a QuickSort variant. It seems a bit off from original QuickSort. Can anyone tell me why and how this works? Is it a quicksort?

The following is code I wrote for a middle pivot quicksort for a high school class of AP CS.

It works for some reason. I've also found a few versions that are same or similar to this. But I'm not sure if this is the same thing as the Hoare implementation scheme. I've tried to analyze it but found out it was quite different from the quicksort I knew of -> which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv. But this one acts like elements not greater than piv | elements not less than piv. Elements that are equal to the pivot can end up anywhere in between. But it works. Is this even quicksort?

public static void middlePivSort(int[] a, int start, int end) {
    if(start < end) {
        int i = start - 1;
        int j = end + 1;
        int m = start + (end - start) / 2;
        int v = a[m];

        while(true) {
            while (a[++i] < v);
            while (v < a[--j]);

            if (i >= j) break;

            swap(a, i, j);
        }

        middlePivSort(a, start, j);
        middlePivSort(a, j + 1, end);
    }
}

Welcome to the fascinating world of sorting algorithms!

Apparently, you get the terminologies the other way around.

What you have implemented is none other than the classic/standard/conventional version of quicksort by Hoare partition scheme.

The version of quicksort that you knew of, "which takes form of: elements smaller than piv | piv ~ piv | elements greater than piv", is probably a variation of quicksort using a variation of Lomuto partition scheme that is good at sorting arrays with many repeated elements.

Exercise 1. Will your code still be correct if the line int m = start + (end - start) / 2; is changed to int m = start;?

Exercise 2. Will your code still be correct if the lines int m = start + (end - start) / 2; int v = a[m]; is changed to int v = (a[start] + a[end]) / 2? .


Unification vs. SAT solver I read on Wikipedia that unification is a process of solving the satisfability problem.

At the same time, I know that such solvers are called "SAT solvers" or "SMT solvers". So, are they different names for the same thing?

If you say that they are different, please point out a flaw in my treatment.

SAT solvers solve the Boolean Satisfiability Problem. This is "the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE."

An example is find an assignment of truth values to variables $a,b,c$ such that
$(a \lor b \lor c)\land (\lnot a \lor \lnot b \lor c)\land (a \lor \lnot b \lor \lnot c)\land (\lnot a \lor b \lor \lnot c)$ is true. A SAT solver could return a solution such as $a=true$, $b=true$, $c=true$.

SMT solvers solve a more general problem, namely Satisfiability Modulo Theories. This is "a decision problem for logical formulas with respect to combinations of background theories expressed in classical first-order logic with equality".
These theories could include "the theory of real numbers, the theory of integers, and the theories of various data structures such as lists, arrays, bit vectors and so on."

An example, given typed variables $x:int$ and $y:int$ and $f:int\to int$, asks whether the following is
$f(x+2) \neq f(y-1) \land x=(y- 4)$ satisfiable.
An SMT solver would answer yes, with solution  $x=-2$, $y=2$, $f(0)=1$
and $f(1)=3$.

Unification is a specific technique that takes two terms and finds a substitution that would make the terms equal. For example, given terms $book(x,\text{"Fishing"},2010)$ and $book(\text{D.~Smith},y,2010)$, unification would produce substitution $\{x\mapsto\text{D. Smith},y\mapsto\text{"Fishing"}\}$.
Unification is likely used inside SMT solvers.