is co-NP-hard contained in EXPTIME-hard or vice-versa? is co-NP-hard contained in EXPTIME-hard or vice-versa?

It is known that co-NP $\subseteq$ PSPACE $\subseteq$ EXPTIME, so every EXPTIME-hard problem, must also be a co-NP-hard problem (as there is a polynomial time reduction from every $L\in$ EXPTIME to it, and therefore also from every $L\in$ co-NP)

Therefore EXPTIME-hard $\subseteq$ co-NP-hard.

Note that this argument does not hold for co-NP-complete and EXPTIME-complete. This is still an open problem (i believe).


Distribution of the number of bits changed during generation of all binary tuples Knuth's TAOCP chapter 7.2.1 discusses generating all the $n$-bit binary strings.
I am interested in the total number of bits that change during this process.

During generation we store an $n$-bit string and can change some of the bits of the string in each round, with the string output at the end of each round.
Call the sequence of integers represented by the output strings the generating sequence.
Every $n$-bit string must be generated precisely once in a generating sequence.
We are interested in the sum of the Hamming distances between successive elements in the sequence, with the initial value assigned to the string regarded as an $n$ bit change.

For the ascending generating sequence $0,1,\dots,2^n-1$ the number of bits changed during the enumeration is then $2^{n+1} - 2$.
The generating sequence $0,2^n-1,1,2^n-2,2,2^n-3,\dots,2^{n-1}-1,2^{n-1}$ yields a larger number of bit changes, at least $(n+1)2^{n-1} = 2^{n-1+\log n}$, and $2^{n-1+\log n} \ge 2^{n+1} > 2^{n+1} - 2$ as long as $n\ge 4$.
A Gray code (which changes one bit at each step) yields  $n+2^n-1$ bit changes.
We can normalise these by dividing by $2^n$ to obtain the mean number of bits changed per step.

  What is the distribution of the mean number of bit changes per step, for a generating sequence chosen uniformly at random?

Even the expected value would be useful, or its behaviour as $n$ grows.
The mean number of bit changes per step tends to 2 for the ascending sequence and tends to 1 for Gray codes (which achieve the minimum), as $n$ increases.
However, I'm not even sure what the maximum is, other than being no larger than $n$ bits per step.

It is somewhat more natural to normalize the number of bit changes per step by the number of steps, namely $2^n-1$. We can then rephrase your question as follows. Let $\pi$ be a random permutation of $\{0,1\}^n$. You are interested in the distribution of
$$
X = \frac{1}{2^n-1} \sum_{i=0}^{2^n-2} d(\pi(i),\pi(i+1)),
$$
where $d$ is Hamming distance. We can compute the moments of $X$ using linearity of expectation. The expected value of $X$ is
$$
\mathbb{E}[X] = \mathbb{E} d(\pi(0),\pi(1)) = \mathbb{E}_{x \neq 0} d(0^n,x) = \frac{\frac{n}{2} 2^n}{2^n-1} \approx \frac{n}{2}.
$$
The second moment of $X$ is
$$
\mathbb{E}[X^2] = \frac{1}{2^n-1} \mathbb{E} d(\pi(0),\pi(1))^2 + \frac{2(2^n-2)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(1),\pi(2)) + \frac{(2^n-2)(2^n-3)}{(2^n-1)^2} \mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx
\mathbb{E} d(\pi(0),\pi(1)) d(\pi(2),\pi(3)) \approx \left(\frac{n}{2}\right)^2.
$$
More generally, for every fixed $t$ we have
$$
\mathbb{E}[X^t] \approx \left(\frac{n}{2}\right)^t.
$$
This suggests that $X$ is tightly concentrated around $n/2$.

Going further, one is tempted to conjecture that the distribution is roughly normal, since the dependence between non-adjacent summands is very slight. This can be verified or refuted by repeating the calculation above with $d(\pi(i),\pi(i+1))$ replaced by $d'(\pi(i),\pi(i+1)) = d(\pi(i),\pi(i+1)) - n/2$. Since $d(\pi(i),\pi(i+1))$ is distributed almost like $\mathrm{Bin}(n,1/2)$, this suggests that $X$ is distributed almost like $N(n/2,n/4)$, a normal random variable with mean $n/2$ and variance $n/4$.


Heap sort best case time - $\mathcal O(n)$? It is given $\mathcal O(n\log n)$ everywhere but in best case it should be $\mathcal O(n)$, isnt it ?
The argument here is, If my input has all the same keys, then every time I delete the root, I do not need to heapify, I just need to swap with the rightmost leaf.

Why is the above argument not valid ?

Big O is for measuring the worst case time complexity, and in this case it is $O(n)$. The best case is written as $\Omega$.  Here is a paper describing the reasoning for the best case. We generally do not consider the case of having only identical elements in the list.


Count bridging edges in a family of two component forests I am given a (simple, undirected, connected) graph $G = (V, E)$ and a fixed spanning tree $T$ in this graph. Removing an edge $e\in E(T)$ from $T$ splits it into a spanning forest $F^e$ with two components $F_1^e$ and $F_2^e$. I am interested in the number $c(e)$ of edges in $G$ that connect $F^e$ i.e. with one vertex in $F_1^e$ and the other in $F_2^e$.

I would like to compute the number $c(e)$ for all $e$ in $T$ simultaneously. This can be done naively in $O(|V||E|)$. Is there a faster way to achieve this?

The graphs I am working with are small-world graphs. In particular the average distance between nodes in $G$ can be assumed to be small.

I have an idea that will efficiently get you "halfway there". Hopefully you or someone else can think of a way to extend this to get the "other half" efficiently.

For a given edge $uv$ in $T$, let me rename the two subtrees that deleting $uv$ would create as $F_u^{uv}$ (this is the subtree containing $u$) and $F_v^{uv}$ (the one containing $v$). Denote by $E_u^{uv}$ the subset of $E$ for which both vertices belong to the vertex set of $F_u^{uv}$ (i.e., the graph edges that are "completely within" the $u$-subtree of $F$), and similarly for $E_v^{uv}$.

For each edge $uv$ in $T$, if we can efficiently compute both $|E_u^{uv}|$ and $|E_v^{uv}|$ , then we can compute $c(uv)$ simply by subtracting these two counts from the total number $|E|$ of edges.

Half of the necessary counts can be computed in $O(|E|)$ time as follows:

Root $T$ arbitrarily and consider all edges to be directed "down", away from the root.
Preprocess $T$ for fast lowest common ancestor (LCA) queries.
For each graph edge $uv$:

Increment a counter $\Delta_x$, where $x$ is the LCA of $u$ and $v$ in $T$.

Compute $|E_v^{uv}|$ as $\Delta_v + \sum_{c:vc\in T}|E_c^{vc}|$ for each $T$-edge $uv$ using a single postorder DFS traversal (here $u$ is the unique parent of $v$ in $T$).

Since LCA can be computed in constant time after linear preprocessing, the above takes only $O(|E|)$ time and space to compute all $n-1$ of the $|E_v^{uv}|$ values. (I think of $|E_v^{uv}|$ as the number of edges "completely below" $uv$.) But it does not compute any of the $n-1$ $|E_u^{uv}|$ values -- the numbers of edges "completely above" $uv$ -- and I can't think of an efficient way to do so.

You can of course reroot $T$ at a different vertex and repeat the exercise: The directions of some edges will be reversed, and the $|E_v^{uv}|$ values computed for each of them can be used for the $|E_u^{uv}|$ values in the original rooting. You could repeat this until all edges have been covered in both directions -- if you were lucky enough to be given a $T$ that is a Hamiltonian path, just 2 rootings would suffice, but in general "covering" all edges this way could require as many as $n-1$ rootings (think of a star tree), which leaves us no better off than the original method.

Ideas anyone?


How is a 2-bit predictor better than a 1-bit predictor at determining loop iterations I have read various explanations why a 1-bit branch predictor is wrong twice per loop, once at the beginning when it wrongly predicts against entering the loop and once at the end when it wrongly predicts against leaving the loop.  Makes sense.

What I don't understand is why the 2-bit predictor is better.  It seems it could even be worse, since it might well predict against entering the loop in the first place, hold to that prediction for a second time before beginning to be "right," and then still wrongly predict against leaving the loop at the end.

I could live with "in practice it turns out to not happen that way all that often," but most of these explanations don't seem to be based on such.  Rather, they seem (to me) to begin with a demonstration how the 1-bit predictor fails twice, and then merely state that the 2-bit predictor does better without demonstrating that it does.

So...what am I missing?

The assumption is that destructive aliasing (or really any aliasing) is rare. That is, the branch predictor entry is unique to that static branch or at least not shared with another branch that is generally not taken.

If there is no aliasing, a later encounter of the loop will still predict taken for the 2-bit predictor but will mispredict for the 1-bit predictor. (A 1-bit predictor will also lack constructive aliasing with other loops since the previous encounter with the other loop will set the predictor entry to not-taken.)

(The common technique of BTB filtering "never" taken branches (i.e., a BTB miss for a branch that is not taken does not update the predictor and behaves as if no branch was present) can reduce destructive aliasing for taken branches.)

For loop dominated workloads a loop branch is both less likely to alias (fewer static branch instructions, one static branch accounts for multiple dynamic branches) and less likely to have destructively aliasing (constructive aliasing with other loop branches is more likely).

If aliasing were common, branch prediction would not work well because the prediction would not apply to the branch being predicted. (A 1-bit predictor can reduce aliasing by providing twice the number of entries compared to a 2-bit predictor of the same storage capacity. For certain workloads with high static branch count, the tradeoff of number of entries/aliasing and hysteresis may be justified.)


Understanding serialization I am a software engineer and after a discussion with some colleagues, I realized I do not have a good grasp of the concept serialization. As I understand, serialization is the process of converting some entity, such as an object in OOP, to a sequence of bytes, so that the said entity can be stored or transmitted for subsequent access (the process of "deserialization").

The trouble I have is: aren't all variables (be it primitives like int or composite objects) already represented by a sequence of bytes? (Of course they are, because they are stored in registers, memory, disk, etc.)

So what makes serialization such a deep topic? To serialize a variable, can't we just take these bytes in memory, and write them to a file? What intricacies have I missed?

If you have a complicated data structure, its representation in memory might ordinarily be scattered throughout memory.  (Think of a binary tree, for instance.)

In contrast, when you want to write it to disk, you probably want to have a representation as a (hopefully short) sequence of contiguous bytes.  That's what serialization does for you.


Can all programs with mutable state be refactored in programs without? Given the space A of all programs that could be possibly written in a given language and given the space B of all programs that could be possibly written in the same language but without any mutable state: can we be sure that with just B we can solve all the same problems we could solve with A ?

There is no general notion of "mutable state" for a generic language. I believe we need to restrict this question to some specific language.

For instance, consider a basic imperative language with arithmetic expressions ($*,+,-$), read input, write output, assignment, composition, conditional ($e=0$ guards), and while loop. No user-defined functions, hence no recursion. Unbounded-precision integer variables. Forbidding mutability would greatly affect the computational power. Unrestricted, it is Turing powerful, but after restriction becomes a very weak language which is able (I believe) to compute only piecewise polynomials / divergence.

If the language is instead a higher order functional language with recursion and assignment (e.g. Scheme), forbidding mutability will not affect its computational power: it was and remains Turing powerful. Mutable state can still be simulated without mutability. A way to do it is to encode state-mutating functions $f$ as pure functions $f({\sf input},{\sf old\_ state})=({\sf output},{\sf new\_state})$ (see the so-called "state monad" in functional programming).

Further, Turing & Church proved that the (pure) $\lambda$-calculus has the same power of the Turing machine. So this is a pretty established result! It is one of the very first discoveries that started computer science in the 30s.


Why can I look at a graph and immediately find the closest point to another point, but it takes me O(n) time through programming? Let me clarify:

Given a scatterplot of some given number of points n, if I want to find the closest point to any point in the plot mentally, I can immediately ignore most points in the graph, narrowing my choices down to some small, constant number of points nearby.

Yet, in programming, given a set of points n, in order to find the closest point to any one, it requires checking every other point, which is ${\cal O}(n)$ time.

I am guessing that the visual sight of a graph is likely the equivalent of some data structure I am incapable of understanding; because with programming, by converting the points to a more structured method such as a quadtree, one can find the closest points to $k$ points in $n$ in $k\cdot\log(n)$ time, or ammortized ${\cal O}(\log n)$ time.

But there is still no known ${\cal O}(1)$ ammortized algorithms (that I can find) for point-finding after data restructuring.

So why does this appear to be possible with mere visual inspection?

Your model of what you do mentally is incorrect. In fact, you operate in two steps:

Eliminate all points that are too far, in $O(1)$ time.
Measure the $m$ points that are about as close, in $\Theta(m)$ time.

If you've played games like pétanque (bowls) or curling, this should be familiar — you don't need to examine the objects that are very far from the target, but you may need to measure the closest contenders.

To illustrate this point, which green dot is closest to the red dot? (Only by a little over 1 pixel, but there is one that's closest.) To make things easier, the dots have even been color-coded by distance.

This picture contains $m=10$ points which are nearly on a circle, and $n \gg 10$ green points in total. Step 1 lets you eliminate all but about $m$ points, but step 2 requires checking each of the $m$ points. There is no a priori bound for $m$.

A physical observation lets you shrink the problem size from the whole set of $n$ points to a restricted candidate set of $m$ points. This step is not a computation step as commonly understood, because it is based on a continuous process. Continuous processes are not subject to the usual intuitions about computational complexity and in particular to asymptotic analysis.

Now, you may ask, why can't a continuous process completely solve the problem? How does it come to these $m$ points, why can't we refine the process to get $m=1$?

The answer is that I cheated a bit: I presented a set of points which is generated to consists of $m$ almost-closest points and $n-m$ points which are further. In general, determining which points lie within a precise boundary requires a precise observation which has to be performed point by point. A coarse process of elimination lets you exclude many obvious non-candidates, but merely deciding which candidates are left requires enumerating them.

You can model this system in a discrete, computational world. Assume that the points are represented in a data structure that sorts them into cells on a grid, i.e. the point $(x,y)$ is stored in a list for the cell $(\lfloor x \rfloor, \lfloor y \rfloor)$. If you're looking for the points that are closest to $(x_0, y_0)$ and the cell that contains this point contains at most one other point, then it is sufficient to check the containing cell and the 8 neighboring cells. The total number of points in these 9 cells is $m$. This model respects some key properties of the human model:

$m$ is potentially unbounded — a degenerate worse case of e.g. points lying almost on a circle is always possible.
The practical efficiency depends on having selected a scale that matches the data (e.g. you'll save nothing if your dots are on a piece of paper and your cells are 1 km wide).


Is finding a minimal set of seed variables for a complete deduction of a system of equations NP-complete? Suppose we have a set of variables $V$. We also have a set of equations $E$, which are sets of at least two variables. We don't know anything about these equations, except if we know all but one of the variables in an equation, we can deduce the missing one.

  Does there exist a set of variables $R \subseteq V$ with $|R| \leq k$ such that revealing these variables allows us to deduce all variables?

Is this problem NP-complete? What if all equations have degree $\leq d$?

I'm ultimately interested in the search version of this problem (where we actually need to find minimal $R$).

Yes, it is $NP$-complete even if $d=4$.

Note that unless $P=NP$, we cannot prove $NP$-completeness for $d=2$ because it is merely  the problem of counting the number of connected components of a given graph.

Reduce from Exact-Cover-by-$3$-sets (X3C).

Given an instance of X3C, we construct an instance of our problem as follows.

The set of elements is $E=\{e_1,e_2,\dots,e_n\}$.
The set of $3$-sets is $C=\{s_1,s_2,\dots,s_m\}$.

This will be a YES instance (of X3C) iff there exists $C'\subseteq C$ with $|C'|=\frac n3$ that cover each element exactly once.

Now, set the set of variables $V=C\cup E\cup C^{up}$ where $C^{up}=\{s_j^{up}|s_j\in C\}$, that means each element is a varialbe and each $3$-set is also a variable. And for each set $s_j$, we add a new variable $s_j^{up}$.

Note that, X3C remains $NP$-complete even when each element belongs to at most $2$ sets and each pair of $3$-sets shares at most one element.

So, here come the equations.

For each $3$-set $s_j\in C$ where $s_j=\{e_a,e_b,e_c\}$, add the following equations:

$\{s_j,e_a,e_b,e_c\}$
$\{s_j,s_j^{up}\}$
$\{s_j,s_j^{up},e_a\}, \{s_j,s_j^{up},e_b\}, \{s_j,s_j^{up},e_c\}$

Finally, set $k=\frac n3$.

We have done with our reduction. Now we have to prove its correctness.

Proof of correctness: (sketchy)

For one direction, if we have a solution $C'$ to our given X3C, it is obvious that $C'$ is also a solution to our instance.

For the other direction, note that it is w.l.o.g to assume that a (minimal) solution contains only variable in $C$. Because if it contains an element (in $E$), we can safely remove it from the solution and add one of the containing $3$-sets (that the element belongs to) to the current solution (if that set has not already been present in the current solution).

So, now a subcollection $C'\subseteq C$ is a solution to our problem. We show that it is also a solution to the original X3C instance.

For each $s_j\notin C'$, it must be the case that all $3$ contained elements of $s_j$ must be deducible. For otherwise, $s_k$ becomes unreachable.

For each element $e_i\in E$, it must be the case that one of the $2$ sets containing it must be included in $C'$.$\blacksquare$

Take @xskxzr's example: The given X3C instance is $E=\{e_1,\dots,e_9\}$, $C=\{s_1,\dots,s_5\}$ where $s_1=\{e_1,e_2,e_3\}$, $s_2=\{e_4,e_5,e_6\}$, $s_3=\{e_2,e_5,e_8\}$, $s_4=\{e_6,e_7,e_9\}$, $s_5=\{e_1,e_4,e_7\}$.

Our set of variables will be $V=C\cup C^{up}\cup E=\{s_1,\dots,s_5,s_1^{up},\cdots,s_5^{up},e_1,\dots,e_9\}$.

Our set of equations will be:

$\{s_1,s_1^{up}\},\dots,\{s_5,s_5^{up}\}$
$\{s_1,e_1,e_2,e_3\}$, $\{s_2,e_4,e_5,e_6\}$, $\{s_3,e_2,e_5,e_8\}$, $\{s_4,e_6,e_7,e_9\}$, $\{s_5,e_1,e_4,e_7\}$
$\{s_1,s_1^{up},e_1\},\{s_1,s_1^{up},e_2\},\{s_1,s_1^{up},e_3\}$
$\{s_2,s_2^{up},e_4\},\{s_2,s_2^{up},e_5\},\{s_2,s_2^{up},e_6\}$
$\{s_3,s_3^{up},e_2\},\{s_3,s_3^{up},e_5\},\{s_3,s_3^{up},e_8\}$
$\{s_4,s_4^{up},e_6\},\{s_4,s_4^{up},e_7\},\{s_4,s_4^{up},e_9\}$
$\{s_5,s_5^{up},e_1\},\{s_5,s_5^{up},e_4\},\{s_5,s_5^{up},e_7\}$

And $k=\frac n3=3$.


is the intersection of a context free language and a regular language a two way street? I wasn't sure how to word it correctly, hence the 'two way street' in the title. My question is:
The intersection of a context-free language and a regular language always results in a context free language, but does this also mean that if I have a language L1 and a regular language L2 that when L1 intersected with L2 is context free that L1 is also context free?

Your clam is false even in the special case where $L_1 \cap L_2$ is regular.
To construct a counterexample let $L_1$ be a language that is not context free (e.g.,  $L_1 = \{a^n b^n  c^n: n \ge 0\}$) and pick $L_2 =\emptyset$ (other choices for $L_2$ work too).
Both $L_2 = \emptyset$ and $L_1 \cap L_2 = \emptyset$ are regular (and hence also context-free), but $L_1$ was chosen as a non-context free language.


Karp hardness of searching for a matching erosion First, read the previous question: Karp hardness of searching for a matching cut

As mentioned in the supposed-to-be-comment answer in that question, without the requirement of cardinality $k$, the problem has been proven to be $\mathrm{NP}$-hard even when restricted to bipartite graph of bounded diameter.

Now, I wanna restrict the notion of a matching cut even further to a matching erosion. A matching erosion is a matching cut whose removal separates the original graph into two connected components $A$ and $B$, where all the vertices of $A$ belong to the matching itself. In other words, a matching erosion is just a matching cut that peels off $A$ from $G$ like cutting a thin slice of meat off a big meat block in a cafe bar.

All the literature constructions seem not to be able to yield such a nice, thin matching erosion cut.

Our problem is defined as: Given an undirected graph, determining if there exists a matching erosion.

The question is what is the complexity of our problem?

In the theory of finite undirected graph, a basic notion that is broadly studied is the notion of matching cut. A matching cut in a graph $G$ is defined to be a matching subgraph of $G$ that is also the edge set of a cut. A $\it cut$ of a graph $G = (V, E)$ is a partition of the vertex set $V$ into two sets $(A, B)$ such that $A$ and $B$ induces two disjoint induced subgraphs that were before incident to some crossing edges which are the edges in the corresponding so-called edge cut set. Specifically, the edge set of the cut $(A, B)$ is then defined to be the subset of $E$ containing all the edges with one endpoint in $A$ and the other endpoint in $B$, i.e. those edges $uv$ with $u\in A$ and $v\in B$. A matching cut is formally defined to be the edge set of such a cut, whenever its edge cut set is indeed a matching. It is worth noting that a matching subgraph which removal increases the number of connected components of a graph $G$ is not necessarily a matching cut, since it may contain edges inside the two separated induced subgraphs. It is a matching cut if it contains exactly the edges of the cut. In order to have more hard computational problems in our still very limited arsenal of proven hard problems, we want to restrict this notion further. We define a {\it matching erosion} as a matching cut $(A, B)$ such that $A$ is exactly one side of the matching. It means that each vertex $v\in A$ has exactly one edges out of $A$, and for any two different vertices $u, v\in A$ their crossing edges end in different vertices in $B$. Intuitively, such a matching split $M=(A,B)$ visually ''peels" off $A$ from $G$.

Formally, we define a matching erosion of an undirected graph as follows:

DEFINITION 1

Given an undirected graph $G=(V, E)$, a matching erosion $(A, B)$ is a partition of $V$ into two disjoint sets $V = A\cup B$ such that:

$G[A]$ and $G[B]$ are two disjoint induced subgraphs
The edge set of the cut is a matching: $M = \{uv\in E\vert u\in A \land v\in B\}$ is a matching
Every $u\in A$ is incident to an edge in $M$

Then, our problem naturally asks whether a given undirected graph $G$ has a matching erosion.

DEFINITION 2

Matching Erosion of a graph:

Input: An undirected graph $G(V, E)$

Output: Yes if $G$ has a matching erosion $(A, B)$, otherwise No

In the next section, we will show that Matching Erosion is computationally hard.

We will reduce Exact 3-Set Cover problem to our problem. Exact 3-Set Cover is another decision problem defined as follows. In Exact 3-set Cover, we are given a universe set of elements $U=\{e_1, e_2, \dots, e_{3n}\}$ and a collection $F=\{s_1, s_2, \dots, s_m\}$ of subsets of $U$. Each subset $s_j$ in $F$ contains exactly $3$ elements $e_{s_j1}, e_{s_j2}, e_{s_j3}\in U$. The decision problem asks whether there exists a subcollection $F'\subseteq F$ such that each element $e_i$ of $U$ is contained in exactly one subset $s_j$ in $F'$. Obviously, $F'$ will contain exactly $n$ subsets in the collection $F$. Such a collection $F'$ is called an exact cover of $U$.

DEFINITION 3

Exact 3-Set Cover problem:

Input: a universe $U = \{e_1, e_2, \dots, e_{3n}\}$ and a collection $F=\{s_1, s_2, \dots, s_m\}$ of subsets of $U$, where each $s_j$ contains $3$ elements $e_{s_j1}, e_{s_j2}, e_{s_j3}\in U$

Output: Yes if there exists an exact cover $F'\subseteq F$, otherwise No

Exact 3-Set Cover is shown to be hard by Garey and Johnson. After describing and proving the correctness of the reduction in the next section, we will establish the following claim.

CLAIM 4

We have that Exact 3-Set Cover $\leq_p$ Matching Erosion

Reducing EXACT 3-SET COVER to MATCHING EROSION

In this section, we prove the claim 4.

Proof:

Describing the construction: Given an instance $(U, F)$ of Exact 3-Set Cover, we will construct an undirected graph $G=(V, E)$ as the produced instance of our problem Matching Erosion. For each element $e_i$ in the universe $U$, we create a new vertex $e_i\in V$. Similarly, for each subset $s_j\in F$, we create a new $K_3$ consisting of 3 new vertices $s_{j,1}, s_{j,2}, s_{j,3}\in V$. For each such subset $s_j = \{e_{s_j1}, e_{s_j2}, e_{s_j3}\}$, we add the $3$ edges to $E$, namely $s_{j,1}e_{s_j1},\:s_{j,2}e_{s_j2},\:s_{j,3}e_{s_j3}$. Finally, we add all edges between pairs of two different vertices of the $e_i$'s vertices to turn these into a $K_{3n}$ clique.

Correctness of the construction:
Suppose that $(U, F)$ has an exact cover $F'\subseteq F$ consistig of $n$ subsets in $F$, then based on that solution to \textsc{Exact 3-Set Cover}, we will easily construct a solution to the produced instance $G(V, E)$ of our problem Matching Erosion. Namely, our matching erosion for $G$ would have $A$ to be the set of all the $K_3$'s of the subsets included in the exact cover. Clearly, each vertex $s_{j,k}$ (where $s_j$ is included in the exact cover and $1\leq k\leq 3$) in this set $A$ is connected to exactly one vertex outside of $A$, namely its corresponding element $e_{s_jk}$ in the universe $U$. Obviously, this is a matching cut that happens to be also a matching erosion.

Conversely, if $G(V, E)$ has a matching erosion $M = (A, B)$, we shall show that none of the elements $e_i$ in the universe is included in $A$. Indeed, if some $e_i$ is included in $A$ then at most one $e_l$ is not in $A$. This is because if there exist $e_i\in A$ and $e_{l1}, e_{l2}\not\in A$ then $A$ cannot form one side of a matching erosion since $e_i\in A$ is incident to two crossing edges $e_ie_{l1}$, $e_ie_{l2}$, recall that the universe $U$ is turned into a $K_{3n}$ in $G$. So, if one element in $U$ is included in $A$, at most one element $e_l$ can be in $B$, but this is also clearly not the case. Because if so, then all the other element $e_i$'s (which are included in $A$) are connected to $e_l\in B$ violating the definition of a matching erosion. So, we have shown that if some element $e_i$ is included in $A$, then all of the $K_{3n}$ corresponding to $U$ in $G$ are included in $A$. But, this also cannot be the case for a matching erosion. We need the following observation.

Observation: For each $K_3$ corresponding to a subset $s_j$, a vertex $s_{j,k}$ in this $K_3$ is included in $A$ iff. all the three vertices of this $K_3$ are included in $A$.

Proof (of the observation):
Obviously, by definition of a matching erosion.

Using this observation, we are able to show that a matching erosion cannot include all the $K_{3n}$ to $A$. Indeed, if so, the matching erosion will then partition the $K_3$'s into two disjoint sets of $K_3$'s, those in $A$ and those in $B$. The $K_3$'s in $B$ would then intuitively form an exact cover for $U$. But, unfortunately, in this case, those vertices of the $K_3$ in $A$ cannot have any crossing edge in $M$, thus violating the definition of a matching erosion.

We have therefore shown that none of the elements $e_i$ in the universe is included in $A$. This implies that $B$ contains all the $K_{3n}$. So, the matching erosion needs to partition the set of $K_3$'s into two disjoint sets of $K_3$'s, those in $A$ and those in $B$ like before. But fortunately, the situation is now reversed. the $K_3$'s in $B$ does not need any crossing incident edge (this is only required in a matching split). And, the $K_3$'s in $A$ would form an exact cover for $U$.


Hash values that are impossible to reach I was just curious as to if there are (or could by) any hash values that are impossible to compute due to the implementation of the algorithm. For example, SHA-256 produces a value that is 256-bits long. Technically, there are $2^{256}$ possible hash values that can be computed. Is it possible that a specific sequence of 256-bits cannot be generated using the SHA-256 algorithm?

This question is not specific to SHA-256 itself, but any hashing algorithm that follows a uniform distirbution pattern.

Regarding common cryptographic hash functions such as the SHA-2 family, it is highly likely that they are surjective (i.e. all potential $2^{256}$ values of SHA2-256 have a preimage). However, given $y$, finding $x$ such that $\text{SHA2-256}(x) = y$ is believed to be a computationally infeasible problem — that's preimage resistance, one of the defining properties of cryptographic hash functions. It's possible that there's a non-constructive way to provide that SHA2-256, but no such way is known, and as far as I know cryptographers tend to think the only way these functions might be proven surjective is by providing a way to compute inverses, which would mean that the functions would be broken.

To summarize, given $y$, it is probably (in the we-believe-it-but-we-could-be-wrong sense) theoretically possible to find $x$ such that $\text{SHA2-256}(x) = y$, but probably (in the chance-for-a-random-$y$ sense) practically impossible.

Hash functions for applications such as hash tables are a different matter. The point of such functions is to spread the input as wide as possible onto a finite-size output, so it is beneficial to cover as much output range as possible. It's often easy to find preimages for these hash functions, but that isn't guaranteed. A given hash function may or may not cover its whole potential $2^N$ output set.


Worst Case Scenario for Quicksort algorithm with pivot element n/2 What would the worst case array look like if I decide to always take the element on the position $\frac{n}{2}$ as the pivot element?
I know that if I choose the left or rightmost element as pivot ,the worst case occurs if:

Array is already sorted in same order
Array is already sorted in reverse order
All elements are same

and that the complexity in that cases is $\mathcal{O}({n^2})$.
However, this cases should not be a problem if I take the middle index of the partition as my pivot element.

Since you're not guaranteed anything about the order of the input, it's possible that the n/2 position has the smallest/largest element of the input. Then quicksort will proceed and put everything else on one side of the pivot.


Printing The Longest Path from Root to Leaf in Binary Tree I am stumped as to how to print the longest path from the root of a binary tree to a leaf, essentially traversing the height of the tree. I've got the following for finding the height of a binary tree:

if (root == null) {
    return -1;
}

return 1 + (Math.max(heightOfTree(root.leftNode), heightOfTree(root.rightNode)));

This easily finds the height of the tree but doesn't lend itself to actually figuring out which nodes should be printed out. I could go about finding the nodes's value that is at the leaf, and then do a find for that particular node, but that seems inefficient.

        A
      B   C
    D  E F  G
             H

For example, the height of this binary tree is 3, and I would ideally like to know the path to take, in this case it would be A, C, G, H. I know that I most likely need to keep an array for the path, but I just can't seem to find a solution that isn't terribly inefficient.

Though I don't believe this is the most efficient solution to the problem, it definitely works and I figured I would share it here and see if anyone had any feedback.

private static void printMain(BTNode node, String[] path, int arrayCounter) {
    if (node == null) {
        return;
    }

    path[arrayCounter++] = node.data;

    if (node.leftNode == null && node.rightNode == null) {
        printArray(path);
    }
    else {
        printMain(node.leftNode, path, arrayCounter);
        printMain(node.rightNode, path, arrayCounter);
    }
}

This print function adds each node's value to an array until it reaches a node that has a left and right child that is null. This means it has reached the end and the array now has a path from the root node to a leaf node. It's not necessarily the longest path though. Here in the printArray function, it checks to see if the last element of the array is null.

Since the array is initialized to only be as large as the height found in the algorithm in my original question, if the last element is null this is not the longest path. If it is we print.

private static void printArray(String[] path) {
    if (path[max] != null) {
        for (String node : path) {
            System.out.print(node + ", ");
        }
        System.out.print("\n");
    }
}

The added benefit of this approach is that it will print each and every path that is the longest. Meaning if there were 3 nodes that are of height 3, each of the 3 would be printed as opposed to just the one. I still think it could be done more efficiently but this is certainly one solution.


What is a good example to illustrate the difference between isomorphic and homomorphic representations? I am learning about "knowledge representation" in my intro to AI course and one of the key ideas has to do with isomorphic vs homomorphic representations. The examples I find when I google around are mainly on the topic of mathematical graphs, which are over my head.

Can someone give me a simple, non-mathematical example of homomorphic vs isomorphic knowledge representation to help me wrap my head around the idea?

You are probably talking about homomorphisms from logic, i.e. homomorphisms that just preserve your functions and relations: https://en.wikipedia.org/wiki/Structure_(mathematical_logic)

I'm a bit suspicious about why your instructor bothered to give you these concepts in the intro course. I also suspect you just need to understand a difference between injective and bijective functions (for this is what the difference between a homomorphism and isomorphism is in the logic world, ignoring all the stuff that deals with preserving structures).

Injective function. You have a set of shirts. You represent the shirts by their colours. Many shirts have the same colour. Some colours don't have any shirts mapped into them. If you are given just a colour, you cannot recover the knowledge of what shirt it was.
Bijective function. You have a set of books. You represent them by the ISBN number. Every book gets and ISBN number. Every ISBN number is associated with some unique book. You can go back and forth between these representations.


Bresenham's line drawing algorithm guarantees I am considering implementing my own version of Bresenham's line drawing algorithm, found here, my one question is does the algorithm guarantee that both endpoints will be covered/drawn. I am doubting this because of the error accumulation factor (decision variable), but I may be wrong.

Yes, Bresenham line drawing algorithm guarantees that endpoints are drawn.
The error accumulation is used for drawing and decreased after drawing a pixel, this is the core idea of the algorithm: incremental error is accumulated to avoid division operation, which is costly, but in this context it is something good and it doesn't mean that errors would damage continuity of line or lose endpoints.
The failure of Bresenham algorithm is technically possible only if floating point variable fails to add error, so $$deltaerr := abs(deltay / deltax)$$ is so small that $error := error + deltaerr$ would not increase $error$ at all, but if that happened, image is too big to fit on computer or some kind of clipping algorithm or bigger floating point variables are needed.
It is safe to assume that $\frac{deltay}{deltax} \le \frac{1}{2^{22}}$ is not going to happen.


What is the sequence of numbers for N = 6? The numbers in the table below are the result of executing an algorithm that has one parameter N, a non-negative integer, and produces sequences of integers as outputs. For values of N from 0 to 5, the algorithm produces the following sequences of numbers as outputs.

Here is one possible algorithm:

If $N = 0$, output the empty string.
If $N = 1$, output "0 1".
If $N = 2$, output "0 2 2 3".
If $N = 3$, output "0 2 4 3 4 5".
If $N = 4$, output "0 2 4 6 4 5 6 7".
If $N = 5$, output "0 2 4 6 8 5 6 7 8 9".
Otherwise, output the empty string.

Now, this is probably not the answer they were expecting, but it's perfectly valid.

(The answer they expected was: output the first $N$ even integers starting with zero, and then the first $N$ integers starting with $N$.)


PDA for a language where the second part is not the reverse of the first part I came across an exercise for constructing a PDA for the following language:
$$L = \{ncm \mid n,m\in\{a,b\}^* \text{ and } n \ne m^R\}.$$
Where $L \subseteq ({a,b,c})^*$
So $n$ and $m$ are both a combination of any number of $a$'s and $b$'s, but $n$ is not the reverse of $m$.
Does anyone have some tips or advice, would be much appreciated!

This answer is for the original version of the question, in which "$k$" was missing.
Your language contains all non-empty words. Indeed, if $w \neq \epsilon$ then you can write $w = nm$, where $m = \epsilon$ and $n = w \neq \epsilon = m^R$. In contrast, if $\epsilon = nm$ then $n=m=\epsilon$ and so necessarily $n=m^R$.


Don Knuth and MMIXAL vs. Chuck Moore and Forth -- Algorithms and Ideal Machines -- was there any cross-pollination / influence in their ideas / work? Question:

To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?

I'm interested in citations, interviews, articles, links, or any other sort of evidence.  It could also be evidence of the form of A and B here suggest that Moore might have borrowed or influenced C and D from Knuth here, or vice versa.  (Opinions are of course welcome, but references / links would be better!)

Context:

Until fairly recently, I have been primarily familiar with Knuth's work on algorithms and computing models, mostly through TAOCP but also through his interviews and other writings.

However, the more I have been using Forth, the more I am struck by both the power of a stack-based machine model, and the way in which the spareness of the model makes fundamental algorithmic improvements more readily apparent.

A lot of what Knuth has done in fundamental analysis of algorithms has, it seems to me, a very similar flavour, and I can easily imagine that in a parallel universe, Knuth might perhaps have chosen Forth as his computing model.

That's the software / algorithms / programming side of things.

When it comes to "ideal computing machines", Knuth in the 70s came up with the MIX computer model, and then, collaborating with designers of state-of-the-art RISC chips through the 90s, updated this with the modern MMIX model and its attendant assembly language MMIXAL.

Meanwhile, Moore, having been using and refining Forth as a language, but using it on top of whatever processor happened to be in the computer he was programming, began to imagine a world in which the efficiency and value of stack-based programming were reflected in hardware.  So he went on in the 80s to develop his own stack-based hardware chips, defining the term MISC (Minimal Instruction Set Computers) along the way, and ending up eventually with the first Forth chip, the MuP21.

Both are brilliant men with keen insight into the art of programming and algorithms, and both work at the intersection between algorithms, programs, and bare metal hardware (i.e. hardware without the clutter of operating systems).

Which leads to the question as headlined...

Question: To what extent is it known (or believed) that Chuck Moore and Don Knuth had influence on each other's thoughts on ideal machines, or their work on algorithms?

There is some evidence: This paper was presented at the ACM SIGPLAN History of Programming Languages Conference (HOPL II, April, 1993), co-authored by myself, Chuck, and Don Colburn, an erstwhile colleague now unfortunately deceased. It references, in turn, a very early work that Chuck wrote when Forth was in what might be called an "alpha" form, "Programming a Problem-oriented Language".

I worked with Chuck from 1970 until 1982, when he left FORTH, Inc. to pursue chip-level implementations of Forth. I know that he referenced Knuth's books and papers for specific algorithms from time to time, but do not believe Knuth influenced the design of Forth in any way. In the time I worked with him, the two men never met. Whether Knuth was aware of Forth or of Chuck I cannot say.


Can you convert a positively weighted DAG into a non-weighted DAG in polynomial time? Given a positively weighted DAG (directed acyclic graph) $D = (V,E)$, can you create a new non-weighted DAG $D'$ by converting each edge with weight $w(e) = x$ into x non-weighted edges and vertices? I believe this would take $O(|E|+W)$ time where $|E|$ is the number of edges and $W$ is the total weight of all edges. My concern is whether I can include this weight variable and still consider this algorithm to be in polynomial time.

(NOTE: This algorithm may apply to all positively weighted graphs, not just DAGs.)

I believe that this would qualify as pseudo-polynomial time.
See http://en.wikipedia.org/wiki/Pseudo-polynomial_time.

The idea is that, usually we represent the time complexity as a function of the length of the string (bit) representation of the input. So your algorithm runs in polynomial time, given a fixed (or at least bounded) value for $W$.

To follow your algorithm, if you perform $O(|w|) $ operations for each edge, you perform $O(2^{b})$ operations where $b$ is the length of the binary-representation of the weight. This means that overall, the algorithm runs in $O(|E|2^{b_{max}})$, where $b_{max}$ is the length of the largest edge weight.

In summary, if you fix an upper bound on the edge weights, $b_{max}$ becomes a constant and the algorithm runs in linear time, but if you allow edge weights to be unbounded, the algorithm is exponential.

This is a common pattern we see when dealing with numerical inputs. The Knapsack problem, as well as factoring the product of two primes, face the same issue.


Is this the correct answer for the cardinality of this set? This is a question from a practice quiz at my university.

Is the question asking for the cardinality of Σ1 = {a,b} to the power of four?
if that's the case, then the set would still have a cardinality of 2 since elements in a set are unique. It wouldn't be {a,b,a,b,a,b,a,b} right?

This is how you should solve it.
Let $\Sigma_1=\Sigma$
We are asked to find: $|\Sigma^ 4|$
Now
$$\Sigma^4 = \Sigma . \Sigma . \Sigma . \Sigma = \{a,b\} . \{a,b\}. \{a,b\} . \{a,b\}$$
$$\text{ Here . means the concatenation operator}$$
So this is equivalent to number of ways of forming strings of length $4$ with symbols from $\Sigma$.
We have $4$ places,

Each of the places have two choices to get filled : either $a$ or $b$.
So,
_   _  _   _
2 . 2. 2. 2

So answer is $2^4 =16$


Happened-before and Causal order I'm reading Lamport's "Time, Clocks, and the Ordering of Events in a Distributed System" and there's a detail that's bugging me.

Lamport defines the "happened before" partial order, which I understand. Then he says that "Another way of viewing the definition is to say that a -> b means that it is possible for event a to causally affect event b".

Consider now two events a and b that are message receptions at a process P1, such that a occurs before b. Further more, suppose a and b are the only two events ever occurring at P1. According to the happened-before relation definition, we have a -> b (which makes sense, since P1 observed those event in this order).

However, I don't see how it is possible for event a to causally affect event b. Those two events are totally unrelated and could have happened in a different order.

What am I missing here?

As it has been pointed out by both @kramthegram and @Wandering Logic, event $a$ "happened before" event $b$ does not imply that $a$ has physically caused $b$ (to happen).

Such causality used in Lamport's paper is often called potential causality. It captures all possibilities, often inducing a huge causality graph, and in practice it wrecks the scalability/performance of distributed systems.

To address these issues, we can consider explicit causality, or application-specified causal dependencies. One common example is social network applications: Alice has read 100 comments in a conversation thread and replied to 5 of them with a single comment. Her comment's immediate happens-before dependency could only consist of these 5 comments (instead of all these 100 comments with potential causality).

Which is the better causality? Well, it depends. For example, potential causality prevails in the research area of debugging multi-threaded programs. There are two main reasons (in my opinion): First, we have no context/semantics which tells whether two events ($\textsf{read}$ or $\textsf{write}$ operations) are effectively causally-related or not. Secondly, we want to capture all possible causality among events and reveal as many debugs as possible.

For more discussions about potential causality and explicit causality, please refer to this paper: The Potential Dangers of Causal Consistency and an Explicit Solution.


Proof By Contradiction - Hamiltonian Paths and Cycles Was hoping if anyone had any way to prove the following claim using proof by contradiction

Let $G = (V, E)$ be a simple graph with at least one vertex, and let $G'$ be the graph formed by adding a new vertex $v$ and making it adjacent to every vertex in $V$.
Claim: $G$ has a Hamiltonian Path if and only if $G'$ has a Hamiltonian cycle.

I tried manipulating the definitions of each of the two (path vs. cycle), but didn't find much luck. Any thoughts?
Thanks!

Contradiction isn't the most natural way to do this, since there's a straightforward constructive proof.

Suppose $G$ has a Hamiltonian path.  How can you extend that to a Hamiltonian cycle of $G'$?  Conversely, suppose that $G'$ has a Hamiltonian cycle. Cover up $v$ with your finger – what do you see?

It's possible to rewrite the reasoning hinted at above as a proof by contradiction, but it's not very natural. ("Suppose $G$ has a Hamiltonian path but $G'$ has no Hamiltonian cycle. Oh, look, here's a Hamiltonian cycle in $G'$ – contradiction.")


Designing a prefix code for integers? trying to figure out how to approach this problem.

  Suppose a sender in a network wanted to communicate the length n of the block it will be using in a subsequent transmission. If there were not limits on the value of n, there would be a problem to simply send the number in binary, since the receiver would find it difficult to know where the end of the number is. Hence we need to encode the integer n using some variable length prefix code, and send the code for n before the code of the length-n block. Design a prefix code for integers and show that an integer n can be encoded with a codeword of length at most log n + O(log log n) - bits.

So I know Huffman's greedy algorithm for generating prefix codes, but I don't have any frequencies to build the 2-tree. I was thinking to solve the problem, I would build a tree for 0-9, but I have a feeling I'm way off with that approach. I'm also not quite sure how to show that an integer can be encoded using log n + O(log log n) bits.

Any help to get me started would really be appreciated. Thank you for your time!

The following code is often used as a standard prefix-code for natural numbers, which bounds the length of each codeword by $\log n+O(\log\log n)$:

At first, we identify the natural numbers by binary strings:
$$(0,\epsilon),(1,0),(2,1),(3,00),(4,01),...$$

Lets call $l(x)$ the length of the binary representation of the natural number $x$. Note that for each $x\ge2$ the following holds:
$$\lfloor\log x\rfloor\le l(x)\le \lceil\log x\rceil$$

Secondly, lets define $s(x_1x_2...x_n)=\underbrace{11...1}_{n\text{ times}}0x_1x_2...x_n$ for binary sequences $x_1x_2...x_n$.

Note that the length of $s(x_1x_2...x_n)$ is $2n+1$. Lets further define $x'=s(l(x))x$, where both, $l(x)$ and $x$ are interpreted as their binary representations.

Finally, the code $D(x')=x$ is a prefix code satisfying that for each natural number $x$, the length of the encoding $x'$ is $\log x+2\log\log x+1$ (ignoring the rounding error).


Operating System: replace the process's memory space with a new program What does it mean that "replace the process's memory space with a new program"? So who's memory space will be replaced by whom?

A process memory space   is :

and when you call fork with a process, the entire address space of that process gets copied, and we allocate some part of the memory to it, and when we call exec after doing fork, it replaces that copy (the child) with a new program.
(note that we usually call exec only with the child, we do this in our code using the fact that the child will return 0 to the fork value and the parent will return the process id of that child, so we use the if command and use exec if its the child)

so to answer your question, we basically replace the address space of the child that was created, with another program.


object image segmentation I have 2 different datasets with similar objects, one where each object is 50 pixels wide and the other where they are 150 pixels. Each photo is 512x512 for both datasets. These two datasets have the same number of photos. Taken with the same camera, so same focal length, resolution etc...
So far, we agree that only the size of the objects differs.

I segment with U-net, for each dataset. It's all right, I have good predictions.
For fun, I train with 150 pixels dataset and test on 50 pixels dataset, and vice versa.
Again, everything is fine, the results are bad so we deduce that the results are better when the size of the objects is similar. Logical.

Now I train a model on a dataset composed of both the 50 and 150 pixels objects (half 50 and half 150), and in total the same number of images as before.
When I test my model on a set of the images composed exclusively of 50 pixels objects (respectively 150), I get better results than when I trained my network using only 50 pixels object to train (resp 150)
Is this due to scale-(in)variant features issues? Is there a similar case you dealt with ?
Thanks a lot

That's a tough one.  I don't know what could cause that.
It can be hard to know why we see the results we do, when working with neural nets.  Often the best we can do is form several hypotheses, and then devise experiments to try to test those hypotheses.
Some possible explanations that you could try to test:

Perhaps it is noise / random chance

Perhaps the 50-pixel images are fairly homogenous and the 150-pixel images are fairly homogenous, and taking a combination of these two yields more diversity, which helps the network learn (e.g., it doesn't overfit to either)

Perhaps the 50-pixel objects don't come from the same distribution as the 150-pixel objects (e.g., the 50-pixel images are of children and the 150-pixel images are of adults; these differ in more ways than just size; or the background is correlated to the size of the object), and you get more regularization from exposing the network to both, or something (this is vague and might not be very different from the second explanation)

Maybe you can think of other possibilities.


Why are progress bars so inaccurate? Computers and programming languages tend to be deterministic and predictable.  Yet progress bars seem the opposite, especially if the operation is complex.  Even for world class professional products, some progress bars do little to reflect the real progress of an operation.  I've seen them go from 10% to 90% in one leap after doing nothing for 4 hours.  I've even seen some take steps backwards, suggesting extra unexpected processing has been discovered.

Granted that there may be database operations, network processing and parallel operations but it seems that this could be quantified in some manner and a percentage estimated.  After all, there must be a finite amount of instructions executed to complete an operation.  Is this simply poor coding, or is there some fundamental reason representing progress is difficult?

Both. Sometimes it's just difficult to estimate how much time an operation will take, because you don't know ahead how much work needs to be done. Sometimes its simplistic and inaccurate estimates.

Example: I'm downloading four files simultaneously. Someone knows how big each file is, how much has been downloaded, and how many megabytes per second were downloaded for each file. Seem easy to predict how long it will take. However, I know that after one file is downloaded, the others will download faster. Even more after 3 files are downloaded; the last one will download four times faster. Have never seen any progress bar taking this into account.

Example: You are copying a big folder. The progress bar assumes that you copy X megabytes per second, knows how many megabytes there are, and your average speed so far. Problem is, "megabytes per second" is very inaccurate - in practice, it takes x milliseconds per file, plus y milliseconds per megabyte. So lots of small files take much longer than the progress bar anticipates.

The problem is that software developers might care, but their managers don't as long as your computer doesn't crash.


Nominal unification: How this lemma is proved? I was reading nominal unification paper. I could not understand the proof of a lemma. The paper is here  nominal unification. The lemma is following.
$\sigma$ is a substitution, $\pi$ is a permutation (swapping of atoms).

Lemma 3.3. if  $\Delta \vdash \sigma(\pi .X) \approx \sigma(t)$, then $\sigma.[X:=\pi^{-1}.t] = \sigma $.

The paper said, to prove the lemma, need to show that  $\Delta \vdash \sigma(\pi^{-1}.t) \approx \sigma(X)$.
It first showed $\Delta \vdash \sigma(t) \approx \pi.\sigma(X)$, from which,
then the paper finished the proof by saying the following.

  The case the follows from the assumptions by symmetry and commuting
   the  permutation inside the substitution.

I could not imagine  how $\sigma.[X:=\pi^{-1}.t] = \sigma $ is obtained from $\Delta \vdash \sigma(\pi^{-1}.t) \approx \sigma(X)$.
what does that "assumptions by symmetry" mean?

Could anyone point out what proof technique is used here?

Thanks.

chi's answer is mostly correct, but I've poured through the paper, and can probably fill in the gaps a bit:

The proof proceeds in 3 steps:

Show that it suffices to prove:
$$\nabla\vdash \sigma(\pi^{-1}.t) \approx \sigma(X) $$
Show that the above derivation is implied by
$$\nabla\vdash \sigma(t)\approx\pi.\sigma(X) $$
Show that in turn this is implied by the assumptions of the theorem.

The structure of the proof is a bit confusing, since it proceeds "backwards", from the conclusion of the theorem to the hypothesis.

The first step involves mostly unpacking the definition of substitutions and the notation $\sigma\ \circ\ [X:=t]$.

The second step is handled by lemmas in the paper (lemmas 2.14 and 2.12 if we're reading the same version). This step is the most complex of the proof.

The last part is performed by changing $\nabla\vdash \sigma(t)\approx\pi.\sigma(X)$ to $\nabla\vdash \pi.\sigma(X)\approx\sigma(t)$ by applying symmetry and once again applying using lemma 2.14 to move $\pi$ "inside" the permutation to get
$$\nabla\vdash \sigma(\pi.X)\approx\sigma(t) $$

which is exactly the assumption!

Again, the only real difficulty is that the proof is working backwards, starting from the conclusion and finding stronger and stronger statements until you get the hypothesis.


Is there any graph problem that, when restricted to trees, has $\Omega(n^2)$ time complexity? Trees are pretty linear in nature, since the number of edges is always one less than the number of vertices. Furthermore, the absence of cycles can sometimes drastically reduce the computational complexity of otherwise pretty hard problems. For example, the longest path problem is NP-hard for general graphs, but is easily solved in linear time for trees. Many other examples exists, where a graph problem magically becomes doable in constant- or linear-time, just because of the restriction to trees (an example for the constant case being the minimum spanning tree problem). I guess sometimes you could be forced to a linearithmic lower bound, although I'm not completely sure at the time of writing this (but my main question for now lies in the next paragraph).

However, I have struggled for a few weeks to come up with an example of a problem that has to have an $\Omega(n^2)$ bound even when restricting to trees. I suspect these problems may exist, but can't come up with any. Can anyone give me an example, or alternatively give me a proof that all decision problems on trees are decidable in less than quadratic time?

Of course, I assume we are not representing the tree using the adjacency matrix, but rather an adjacency-list or other timesaving data structure.

I also suspect that I might need to explicitly state to consider only tractable problems, since I guess you could come up with halting-type problems for trees otherwise.

Yes. By the time hierarchy theorem, there is a (tractable, solvable in $O(n^2 \log n)$ time) problem $X$ that (on an $n$-bit instance) can not be solved in less than $\Omega(N^2)$ time.

Given an $n$-bit string, I can encode it as a tree, for instance by taking a path $p_1,\ldots, p_n$ of length $n$ and adding an additional leaf vertex to vertex $p_i$ if the corresponding bit $i$ in the string is $1$ (and perhaps adding some constant-size gadget to mark the beginning of the string).

Now I will define problem $Y$ to be to recognize the trees that encode a bitstring that is a (valid) instance of $X$. Clearly this problem requires at least quadratic time (or otherwise we would have a faster algorithm for $X$).

This is of course a rather contrived and artificial example, but there are some  natural problems that are hard for trees as well. See e.g. NP-hard problems on trees.


Why do we need Gibbs sampling (and MCMC)? I just learned about Gibbs Sampling which is an MCMC method. Given a distribution $\pi$, we want to sample an item according to $\pi$.

Maybe my alternative suggestion would sound somewhat naive (even stupid) but why can't we just draw a number in random from $[0,M]$ for some sufficiently large enough $M$. Then, we divide the range to buckets with appropriate sizes according to the distribution.

This will be a true sampling of $\pi$.

One could argue that my suggestion demands a PRNG, but Gibbs Sampling uses randomness too when deciding the next state from the neighbors of the current state.

So for a reasonable distribution, wouldn't my suggestion work way better? It's essentially $O(1)$ and accurate.

It's not "essentially $O(1)$" to draw objects from a set with non-uniform probability: your bucketing scheme takes more than constant time.

Further, sampling from a Markov chain allows you to sample without having to construct the probability distribution explicitly or even the state space, explicitly. For example, how do you propose to randomly sample matchings in a graph by your method, even uniformly? You'd need to first construct the set of all matchings (of which there can be exponentially many), then select one. And note that constructing the set of matchings implies being able to count them, which is #P-hard, so very unlikely to be doable efficiently. With a Gibbs sampler, you just run a Markov chain for polynomially many steps and you have yourself a matching chosen uniformly at random.


Published or widely known failures of Page Rank algorithm I use Google a lot for searching articles and publications. Occasionally, I find Google totally misses what I am looking for and I get completely unexpected results for some search queries.

  What are the published or widely known failures of PageRank algorithm?

EDIT: Changed the post to address comments.

yes this "problem" is quite well studied and google itself is researching ways to improve it. its called the word sense disambiguation problem and is under active/ongoing research, as its becoming a competitive feature between different search engines. quite simply, the same word has different meanings depending on context.

as for your more general question about "widely known failures of page rank", it is long known that it cannot necessarily distinguish spam web pages designed to fool it, and a related technique called a link farm with many external pages pointing to one site. in this sense google search is employing somewhat similar aims/techniques to spam-detecting algorithms employed largely/widely by mail providers.

google has proprietary/closely guarded techniques to detect/filter spam and these are a large part of the continually refining versions released. then advertisers attempt to respond with new techniques. this back-and-forth evolutionary dance/ "arms race" is also known as search engine optimization from the advertisers pov, but the term also somewhat applies to googles process of improvement! (SEO is a very large field with strong overlap with marketing and probably worldwide worth in the billions of dollars.)

somewhat similar, so-called "google bombing" where people create a mass movement to use words together to affect search engine results. it is somewhat subjective whether to call this a "failure" of the search engine or actually a "feature" (as from the perspective of those exploiting it, because in a way search engines actually by design measure meme prevalence in cyberspace!).

one method of dealing with word disambiguation is actually looking at trends in users personal search engine behaviors. in this way person A typing in a query will get different results than person B depending on their search histories.[1]

a related field called Latent semantic analysis helps with this somewhat by representing documents as sets-of-words with weights associated with each word, and the same word may have different weights in different documents or depending on document similarity measured by the vector cosine similarity technique.

an example paper from this field is K&M ref below. it actually uses & builds on results of existing google searches for word disambiguation.

yet another known issue is called "topic drift" where basically, if you search on two terms $x$ and $y$, if $y$ is more common it will tend to dominate and more results will be related to $y$ and "drown out" results with both $x$ and $y$. see eg [2]

Google, Bing Battle for Better Disambiguation, AI eweek
Google & WordNet based Word Sense Disambiguation Klapaftis, Manandhar
[1] Google Now Personalizes Everyone’s Search Results searchengineland
[2] hits/pagerank & topic drift tcs.se


System f-sub, how to do type checking? I was reading that system f-sub (polymorphic lambda calculus with sub-typing) and I was quite confused with its one checking rule called "T-TAPP".

This rule as following (ctx denotes the typing context)

   ctx |- t1 : ∀X<:T11. T12    ,    ctx |- T2<:T11
   -----------------------------------------------
            ctx |- t1 [T2] : [X-->T2]T12

I could not understand how '[x-->T2]T12' will be used (I know it is substitution). This rule appears on page 10 in the following source.
I am looking for two type checking examples, in which above inference rule will be applied and at least one example is a case of type checking failure.

Could anyone provide me with concrete examples?
Description of system F-sub

I know this is old but the previous answer has a huge misconception.

The following function is in System F.

$f = \lambda X. X \rightarrow X \rightarrow X$

All we know of this function is it selects one of its arguments and can be instantieded with any type; $\ f$ [Bool] : Bool $\rightarrow$ Bool $\rightarrow$ Bool.

In System $F_{<:}$ is possible to have the following function.

$f' = \lambda X<:$Number$.\ X \rightarrow X \rightarrow X$

This function can be the addition, multiplication, division, subtraction, etc, and can be instantiated with subtypes of Number.

$f'$ [Int], $\ f'$ [Double], $\ f'$ [Real] are valid instantiations, but $\ f'$ [Bool] not, because Bool is not a subtype of Nat.

Dependent types are a different thing. It has nothing to do here and is out of the scope of the question, but it is a very interesting topic. See Lambda Cube


Why doesn't 2-opt return an optimal solution? To find a solution for the Traveling Salesman Problem (TSP), one way to go is an algorithm called 2-opt, which is explained below.

The 2-opt algorithm basically removes two edges
from the tour, and reconnects the two paths created.
This is often refered to as a 2-opt move. There is only
one way to reconnect the two paths so that we still
have a valid tour (figure 1).  We do this only if the
new tour will be shorter. Continue removing and re-
connecting the tour until no 2-opt improvements can
be found. The tour is now 2-optimal.

For me, this algorithm tries all possibilities for edge combinations, so it should return the best (optimal) solution, right? Wrong, because :

If we look at the tour as a permutation of all the
cities, a 2-opt move will result in reversing a segment
of the permutation.
Running the 2-opt heuristic will often result in a tour
with a length less than 5% above the Held-Karp bound.

My question is ; why does it not return the optimal solution? Does it not try all possible edge combinations? Can you give an example graph for which 2-opt doesn't give an optimal solution?
I'm citing from here : https://web.tuke.sk/fei-cit/butka/hop/htsp.pdf

I think I understand now after trying some examples as Yuval Filmus suggested. In the example below, we can get stuck on the local optimum using 2-opt, but as we can see the global optimum is better.


why does LSPACE(log space) complexity class exist but not logtime? I noticed that in complexity classes, logspace class is defined but there is no logtime.
I was wondering how is that possible?
Normally, I would expect the opposite, It is possible to do a search query in an ordered list in time less than the time of iterating over all items (==> Logtime?). However you can't store a list in of size n in log(n) space...
So how come Logspace exists but not logtime? there's obviously something wrong with my reasoning.
Could someone please correct me?
Thanks in advance

Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting.
What you have in mind is not Turing machines, but random-access machines, for which logarithmic time does make sense. Indeed, the corresponding complexity class exists: DLOGTIME. It is most often used in the context of DLOGTIME-uniform circuits. A related complexity class is ALOGTIME, which is the uniform version of NC¹. Buss famously proved that the formula evaluation problem is ALOGTIME-complete. For comparison, the circuit evaluation problem is P-complete.
Algorithms running in $o(n)$ time on random-access machines are known as sublinear time algorithms. Such algorithms also abound in the area of data structures.


Turing tests and humans How are the questions framed in Turing tests? I mean what factors would one consider before framing questionnaire for the Turing Test.How the questions should be framed to make the test unbiased for a machine and humans?

The basic objective of a Turing test is to come up with such an intelligent machine, which actually mimics the human way of communicating.
For that purpose, we'll carefully need to think about what normal humans would like to talk about, in a casual manner. Starting the talks with a friendly, informal manner may be a good thing. After that, you might want to know about the interests of the person you're talking to; you might start with...say, football, or cricket, economical crisis, united nations; there are literally a lot of topics.
 Look up for the common trends in the humans...these can include some recent famous political scandals (I don't want to mention Panama Leaks here). Questions can be about the current good movies (hits and flops). You may even come up with a religious, or a philosophical discussion if that helps.
 Incomplete questions, and then stating "you know the rest" after a half phrase can also be a good practice, because of the common sense the humans have to infer the essence, and background meaning of the question.
 Last, but not the least, if you're going to ask the question from a chat-bot, then it is a real good thing that you place intentional grammatical mistakes, typos, and unclear phrases, that only a real human would be able to understand, because it's a natural thing for the humans to commit a mistake. Questions about past memories are also a good thing, especially when they are slightly offensive; discussing relationships, frustration, failures, fears etc. Emotion-based questions have more tendency to crack up the game.


What is the time complexity of the original Otsu's method? I'm trying to give a general comparison of the time complexities of various thresholding algorithms. I have not taken an algorithms course yet, so please forgive any misunderstandings.
Otsu's method is performed on $N$ pixels with $L$ number of pixel intensities (e.g. an 8 bit greyscale image would have $L=256$). The algorithm will choose an intensity $k$, and calculate the variance for pixels with intensity less than $k$, and for pixels with intensities greater than $k$.
Calculating the variance involves finding the mean intensity (summing a total of  $N$ pixels), then sum the square of the difference between each pixel intensity and the mean mean intensity (again summing a total of $N$ pixels). This is performed for all intensities.
Therefore, would I be correct to say that the average time complexity of the algorithm is $O(LN)$?

The algorithm can certainly be implemented in $O(LN)$ time, as  you say.
It is not hard to optimize it to run in $O(N+L^2)$ time.  Simply form a histogram of pixel intensities (count of the number of pixels of each intensity).  Then you can compute each variance in $O(L)$ time, rather than $O(N)$ time.
You can improve it further to run in $O(N+L)$ time.  Suppose we have computed the sum of values below the threshold and sum of squared values below the threshold; and the same for those above the threshold.  That is enough to compute the standard deviations.  Then, when we bump up the threshold by one, it is possible to update those four sums in $O(1)$ time.  As a result, it takes $O(N)$ time to build the histogram, then $O(L)$ time to compute the score for the first threshold, then $O(1)$ time for each subsequent threshold, and there are $L$ candidate thresholds, for a total of $O(N+L)$ time.
In practice the difference between $O(N+L^2)$ vs $O(N+L)$ might be unimportant, as for 8-bit images, $L \le 256$.


The difference between compiler and interpreter I am reading dis, It reads:

The dis module supports the analysis of CPython bytecode by disassembling it. The CPython bytecode which this module takes as an input is defined in the file Include/opcode.h and used by the compiler and the interpreter.

In wikipedia

In computer science, an interpreter is a computer program that directly executes, i.e. performs, instructions written in a programming or scripting language, without requiring them previously to have been compiled into a machine language program.
A compiler is computer software that transforms computer code written in one programming language (the source language) into another programming language (the target language).

I really unable to figure out the difference.

In basic terms the difference between an interpreter and a compiler is the point at which a source text is actually executed.

An interpreter interprets a language by reading the text or source code and then performing computations as it processes the text to execute the text. So as the interpreter is reading the source of the program, the program runs or executes as the interpreter reads lines of code and performs those actions.

A compiler compiles a language by reading the text or source and transforms the source code into another form which is typically machine code.

To make things a bit more complicated you will see that some interpreters have a Just In Time (JIT) compiler component to them. So the process then is the interpreter reads the source code and converts it to an intermediate, more machine friendly, form which is then fed to a JIT compiler which creates a machine code which is then executed by the target hardware. Most interpreters of this form have a Virtual Machine which is hardware independent that uses a JIT compiler to target the actual hardware when the program is executing. The Virtual Machine is hardware independent but the JIT compiler must be tailored to the particular hardware. The JIT compiler compiles the Virtual Machine code or instructions into the target hardware machine code which is then executed by the hardware.

And by the way this kind of Virtual Machine is different from the virtual machine used with Docker and other types of containers which has hardware virtual machine support. The Virtual Machine used by these interpreters is an application which emulates some abstract hardware.

For examples of this kind of Virtual Machine look to the Java Virtual Machine. Or the Python Virtual Machine.  See Java “Virtual Machine” vs. Python “Interpreter” parlance?
.

And this document, Python (2.5) Virtual Machine: a guided tour has some of the gritty details about the Python Virtual Machine though an older version of Python.

A compiler will normally compile the source text to actual hardware machine language. So the output of a compiler depends on the actual target hardware. The machine code of a compiler that targets an x86 architecture is different from one that targets an ARM architecture.

Using a compiler will require additional software tools as the process for a compiler is generally something like the following:

create the source code file or files
compile the source code file or files to generate one or more object code files
link the object code files with various libraries to generate an executable
run the executable application

Using an interpreter will be a simpler procedure something like the following:

create the source code file or files
execute the interpreter program, specifying the source code file

The C programming language is normally a compiled language using a compiler. The python programming language is normally an interpreted language using an interpreter.

However there is nothing to stop someone from writing a compiler for what is normally an interpreted language nor writing an interpreter for what is normally a compiled language. And you can see examples of this all over the internet.

To make things even a bit more complicated in the naming of things, there are applications called compilers that translates one programming language into another.

A classic example is the first C++ compilers which would transform C++ source code into C source code and then compile the C source code into machine language. It's not done like that anymore and the C++ language was a subset of modern C++ (C++11/17) but it worked for a proof of concept.

I have also seen a translator that would transform C source code into JavaScript.


Proving undecidability of HALT_tm by reduction Sipser in his book introduction to the theory of computation provided a proof of undecidability of $HALT_{TM}$. He uses a contradiction, he assumed that $HALT_{TM}$ is decidable, and built a decider for $A_{TM}$, and since $A_{TM}$ is already proved by digonalization method to be undecidable, thus the contradiction occurs and $HALT_{TM}$ is undecidable. The Turing Machine is simple and straightforward and I'm not going to talk about its details.

What makes me confused is this sentence

  We prove the undecidability of $HALT_{TM}$ by a reduction from $A_{TM}$ to $HALT_{TM}$

and I would like to know in which part of the proof reduction actually occurs?

From what we know of the concept of reduction, reducing $A$ to $B$ means: we have two problems $A$ and $B$ and we know how to solve $B$ but we stuck in $A$, then if we reduce $A$ to $B$, it means solving an instance of $B$ will cause solving an instance of $A$.

let's get back to the proof, Sipser says

  We prove the undecidability of $HALT_{TM}$ by a reduction from $A_{TM}$ to $HALT_{TM}$

thus $A = A_{TM}$ and $B = HALT_{TM}$. We don't know how to solve $HALT_{TM}$ and actually this is the problem in hand, furthermore the strategy of the proof is based on contradiction, something that is completely irrelevant to the concept of reduction. Then why Sipser uses the term reduction in this proof?

Sipser reduces $A_{\mathit{TM}}$ to $\mathit{HALT}_{\mathit{TM}}$. Since $A_{\mathit{TM}}$ is uncomputable, it follows that $\mathit{HALT}_{\mathit{TM}}$ has to be uncomputable. He is using the following general statement:

  If $A$ reduces to $B$ and $B$ is uncomputable, then so is $A$.

You are right that this general statement itself is proved by contradiction. A proof which uses this general statement to prove that a particular problem is undecidable is a proof by reduction – in your case, you prove the undecidability $\mathit{HALT}_{\mathit{TM}}$ by reducing a problem you already know is undecidable to $\mathit{HALT}_{\mathit{TM}}$. In contrast, Sipser's proof that $A_{\mathit{TM}}$ uses a different technique, diagonalization.


Show that Halting problem $(\mathsf{HP\text{}})$ is $\mathsf{NP\text{-}Hard}$ Let me define first Halting problem $(\mathsf{HP\text{}})$.
Given :  $(M , x)$,  $M$ is a turing machine and $x$ is a input binary string to turing machine $M$.
Decide  : Does $M$ halt on string $x$?
I tried to reduce $\mathsf{SAT\text{}}$ instance to $\mathsf{HP\text{}}$ in polynomial time. Let $\phi$ be a instance of $\mathsf{SAT\text{}}$ and define a map $\mathsf{T\text{}} \colon \mathbb \phi \to\mathbb M$. If $\phi$ is satisfiable (means true) then turing machine $M$ will halt on string $x$ and if  $\phi$ is not satisfiable (means false) then turing machine $M$ will not halt on string $x$.
I don't know whether the map $\mathsf{T\text{}}$ right or wrong. So my question is how to define a map and to compute this map in polynomial time?

Given a SAT formula $\varphi$, construct a Turing machine which iterates over all truth assignments for $\varphi$, and so determines if $\varphi$ is satisfiable or not. If it is, it halts. If it isn't, it doesn't halt (gets into an infinite loop).

As is apparent, in the same way we can show that the halting problem is coNP-hard (by reversing the decision rule at the end). Indeed, in the very same way we can show that the halting problem is hard for many other classes – in fact, for all classes defined by time or space constraints (deterministic, non-deterministic or randomized).

NP is the "length- and time-bounded" version of the halting problem, or rather, of $\Sigma_1$. The class $\Sigma_1$ consists of all predicates $P$ such that
$$ P(x) \leftrightarrow \exists y  \, \Pi(x,y), $$
where $\Pi$ is a computable predicate. NP is defined in a very similar way, by adding two restrictions:

$y$ has to be polynomially bounded (in $x$).
$\Pi$ has to be computable in polynomial time.

If you like this sort of thing, there is an entire field dedicated to this point of view, called Bounded Arithmetic.


Terminologies of "Process calculus" and "Process algebra" In the literature, the terms of "process calculus" and "process algebra" are often interchangeable. Meanwhile, it confused me.

My questions are:

  Are there formal, standard, and widely-accepted definitions of "calculus" and "algebra"?
  What are the significant distinctions (maybe informally) between "calculus" and "algebra"?
  What are the features that make a theory kind of "calculus" or "algebra"?

To my knowledge the two terms do not have a formal established definition and are often used interchangeably.

There are different characteristics associated to each however, as @Dave already pointed out. I'll try to elaborate a bit further.

In both cases you start by introducing the syntax of a language for expressing (concurrent) systems. This introduces what the basic "combinators" (constructs) for assembling systems together are.
The real distinction comes when you start to specify their semantics.

The process calculi approach is calculational in the sense that you focus on the reduction semantics, i.e. what are the steps a system can perform when executing it. This operational view helps a lot when using these languages for simulation for example.
The chief notion in this case is the concept of "observation": what can you observe about the evolution of a system? Using this idea one can determine when two systems are equivalent. The technical word for this concept is bisimilarity. Then, in some situations, you find that processes which are bisimilar can be interchanged in any context without altering the behaviour of the system overall. This is the approach Milner and his collaborators took in defining many calculi such as CCS and π-calculus.

The algebraic view instead avoids specifying a model for the semantics directly and opts for a more axiomatic view: a series of laws (equations between expressions of the language) establish which processes have the same behaviours. The focus is in proving equivalences and enriching the calculus with different combinators. Even the "execution" of a system is expressed as an equivalence between a system and a (simpler expression used as a) specification (see the step laws for CSP for instance).
The equivalence between two systems is established by using the laws instead of referring to a particular model for their behaviour. The chief concept in this context is the one of refinement. This approach is the basis of the work of Hoare and his collaborators in defining CSP and its variants.

That said, most of the languages mentioned have being studied with a mixture of these approaches so the distinction is more about the specific method used in a specific construction rather than about a language as a whole.


The number of operations of Explicit and Implicit Euler for 1D hear equation I'm studying with "Numerical Solution of Partial Differential Equations by K.W.Morton and D.F.Mayers". On page 25, it says "2(add) + 2(multiply) operations per mesh point for the explicit algorithm (2.19)", but it seems 3(add) + 2(multiply) to me, how did I get wrong?

(2.19)  $U_j^{n+1}=U_j^{n}+\mu(U_{j+1}^{n}-2U_j^{n}+U_{j-1}^{n})$

My counting is

2(add) and 1(multiply) inside the bracket

1(multiply) for $\mu$ and the brackets

1(add) for $U_j^{n}$ and the rest


Warm starting LP solver at non-basic feasible solution I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming solvers, like GLPK.

After having solved a discrete approximation at resolution $h_0$, I can produce a reasonably good feasible solution $x_h$ for any discrete approximation of the problem at a higher resolution $h$. BUT, that reasonably good feasible solution $x_h$ is in general not a corner(i.e. basic) solution.

Given that solvers like GLPK can do a warm start only at a basic solution, how can I come up with a basic feasible solution near $x_h$ to warm start the solver with? Are there any open source, or at least free, solvers that can be warm started with feasible non-basic solutions?

LP solvers use simplex typically, so starting from nonbasic solution doesn't have too much sense. You can try finding a basic solution to $x_h$ by minimizing $||x-x_h||_p$ over your feasible region. I believe it's still an LP for $p=1$ and $p=\infty$. However, there is no guarantee warm start combined with this is faster.


Is it theoretically possible to dynamically grow array size in stack memory? I was wondering, given the usual stack memory functioning, whether it is possible for an array like primitive type allowed to grow in size to exist.
The functioning of such primitive type is as follows.

Any one function is allowed to have only one such primitive variable.
Appending to such primitive variable is allowed only within the function that it was initialized in.
If the function that such primitive variable was initialize in is not the last in the stack, such primitive variable is not allowed to grow in size.

I was wondering whether:

Such primitive type is theoretically possible.
Whether it is something that is already in use.

Yes, it is certainly possible. It really depends if you want it enough to pay the price in terms of complication.

First of all, I would strongly recommend that your array should have negative indices: a[-1], a[-2], and so on. This will be good because the stack grows downwards, and if you adopt this convention then you will not need to move all your existing array elements down to the new array position every time you enlarge the array.

After that, it is really a linguistic question. In assembler you can obviously do it, because you can do anything in assembler. Whenever you want your array to be n bytes bigger, just subtract n from the stack pointer.

In C there is often a function - disapproved of by all respectable computer scientists and therefore very useful when it is useful - called alloca or _alloca - which allocates n bytes of data on the stack and returns a pointer to the new allocation. I would be very surprised if two consecutive alloca calls did not just allocate contiguous stack space, so although there isn't a realloca function, you could effectively simulate its behaviour.

Where life gets interesting is when the compiler decides to use the stack for its own purposes: for instance, it might precompute the arguments for several function calls and push them all onto the stack before calling any of the functions. Usually such compilers notice a call to alloca and disable optimisations in the function that uses it - this is one of the reasons for disapproving of alloca.

The main difficulty you would run into would be that, if you wanted your array indices to be "the right way up" - a[0], a[1], a[2] and so on - then every reallocation would require data to be moved, which is a bore. And you can't write your own function in C to do this (that is, both the extra stack allocation and the data movement) because when you call a function, you usually push a return address onto the stack, so the stack-based array is (as you showed in your pictures) blocked by that extra piece of data and can't be enlarged. You would have to write a special realloca function in assembler which pops the return address and keeps it safe; subtracts an appropriate amount from the stack pointer; pushes the return address again; and then does the necessary memory movement. It would actually be quite fun to implement, though not at all portable because different systems will use the stack in different ways in a function call.

Is it used? Yes, I have used alloca for things I know to be small, because I love not having to rampage all over the heap and I love not having to deallocate. But your more elaborate scheme - I haven't heard of anyone who has done it.

Except in assembler - where one can do a beautiful merge sort by using the stack to store data.


Is Newton's algorithm really this much better than conjugate gradient descent? I have a function I'm minimizing. I'm using conjugate gradient descent and the Newton algorithm.

I am experiencing that the Newton algorithm is absurdly faster. Like, it finishes it 5-6 iterations, while the conjugate gradient takes 2000 iterations (and regular gradient descent takes 5000 iterations).

I know what's causing the problem too: the learning rate. In Newton's method, a learning rate of $\alpha = 1$ works. But I can't use this in the gradient descent methods, where such a choice of $\alpha$ diverges. In these methods, I am forced to use $\alpha = 0.01$.

But anyways, 5 iterations vs thousands of iterations is still an absurd difference. Is Newton's method really this good??!

The relative performance of different optimization algorithms depends a lot on the particular function you are minimizing.  We certainly can't tell you whether it is really that good for your particular function without knowing what specific objective function you are looking at, but it certainly seems possible to me.

There are some functions where Newton's method will be vastly better.  For instance, with a quadratic function, where a few iterations of Newton's method will suffice to get a very precise answer; yet gradient descent might take many iterations to get similar precision.  This can be partly explained theoretically by understanding that Newton's method often converges quadratically or faster (though for some bad cases it can converge more slowly), while gradient descent typically converges sub-linearly for convex functions or linearly for strongly convex functions (and for bad cases it can converge much more slowly), so in a theoretical sense Newton's method often requires fewer iterations than gradient descent.

Conversely, there are also some functions where (conjugate) gradient descent will be better, for instance because one iteration of gradient descent is much faster than one iteration of Newton's method.  One example would be training deep neural networks, where gradient descent works very well but Newton's method would be painfully slow due to the very high dimensionality and the time it takes to do a single iteration of Newton's method.

I would caution against drawing a conclusion about the performance of Newton's method on all functions, based on an empirical observation of its performance on one particular function (a sample size of $n=1$).


How to compare an experimental study with amortized times I have an implementation of a data structure I have to study for a group project (Fibonacci heaps if you're interested).
I'm asked to compare the theoretical results of the operations in amortized time, with the running times of my implementation.
Now my question: since amortized times are based on the fact that we look not just at a single operation, but at a series of operations, what can I do with my implementation to receive some experimental results that support (or not) my theoretical analysis?

If you want to compare theory and experiment, you have to perform both analyses under the same assumptions.

Note that this includes what you measure. Since you did not analyse time in theory, there is little sense in measuring running times in the experiments. Use combinatoric measures you can count reliably and independently of the system and its load.


What would be the consequences if P=NL I haven't found anything in the literature that suggests what would happen if that is the case.
Thank you,
Akash

$NL=P$ is not considered likely by the experts.
I found a few SE questions on this topic: [1] [2]
The corollaries include:

$P\subseteq L^2$ by Savitch's theorem
$NC=P$ by the Squeeze theorem
$EXP=PSPACE$ by $P\subseteq polyL$

I would like to include or exclude $P=L^k$, $k\in[1,2]$, but I have not collected sufficient evidence for or against that conclusion.


Complexity Sorting a finite set of numbers from 0,..,N I have a set of elements $x_1,...,x_N$, they take values $x_i \in \{0,...,N\}  $ for all $i \in \{1,...,N\}$; I need to sort them. I think I can do that with complexity $\mathcal{O}(N)$, where I can create a matrix of $N\times N+1$ where the colomns represent the sorted values of the range, i.e., $\{0,1,2,...,N\}$, and the rows are the elements.
So my questions are:

Is this correct?

Is there a better way to do that?

What if I changed the values of some of these numbers afterwards (after sorting), but all still comply with the initial rule, can I do better than linear sorting to maintain the order?

Since you have a bound on your set of elements you can
radix-sort them.

Formally let consider the following procedure:

    // Read the whole table and store the number of occurrences
    T <- Table[N] // Suppose initialized at 0
    for i = 0 to N do
        T[x[i]] <- T[x[i]]+1
    done
    // Unpack the elements
    c = 0
    for i = 0 to N do
        for j = 0 to T[i]-1 do
            x[c] <- i
            c <- c+1
        done
    done

The soundness of the algorithm is evident.
It's time complexity is in $\mathcal{O}(N)$ and its space
complexity in $\mathcal{O}(N)$, estimated in arithmetic complexity (I mean by that the reading and writing complexities for your integers is independent of their bitsize).

The (bit) time complexity is in worst case a $\mathcal{O}(N\log N)$ since
you might have to read $N+1$ bit strings of length $\Theta(log(N))$.

Notice that in any case, the algorithm is always linear in the size of its input.


Left quotient of a regular language I have this problem, and I don't really understand how am I supposed to do this. Could someone please help me with this? I know what left quotient is. I also know about regular, irregular languages. But still I don't know how to show this... Any help would be appreciated, thanks in advance! Also sorry if something is not correctly in English, not my first language.

Problem:

  Show that for any language $L ⊆ Σ^*$ and any DFA $A = \langle \Sigma, Q, q_0, \delta, F \rangle$,
  the left quotient $L \diagdown L (A)$ is a union of languages $L_q = \{v | \delta(q,v) \in F\}$ for selected states $q \in Q$, and explain what are those selected states.

Could someone please also demonstrate on a small (but non-trivial) example, in which the $L$ would be irregular?

By definition,
$$
L \diagdown L(A) = \bigcup_{x \in L} \{ w : \delta(q_0,xw) \in F \}.
$$
The idea now is to use the identity
$$
\delta(q_0,xw) = \delta(\delta(q_0,x),w).
$$
You take it from here.


If a convex optimization problem can be NP-Hard, in what sense are convex problems easier than non-convex problems? Being new to the OR and Optimization world, I've always assumed that a problem being convex meant that it can be solved in polynomial time.

Now I am learning that a convex optimization problem can be NP-Hard, but that convex problems are still somehow considered easier than non-convex problems.

Can someone explain this apparent contradiction to me:

Is it true that a convex optimization can be NP-Hard? On one hand, based on this post and the accepted answer, yes, There are examples of convex optimization problems which are NP-hard. On the other hand, This lecture from a Stanford Professor, around 28:00 states that convexity means tractability and polynomial time algorithms.
If it is indeed true that convex optimization problems can be NP-Hard, then in what sense are they "easier" than non-convex problems? As far as I know, there are no levels of NP-Hardness, anything between NP-Complete and P-Space is NP-Hard. I frequently hear Operations Research people say that we have all sorts of tools for convex problems, while non-convex problems are still very hard to deal with?

A first order approximation is that convex programs are tractable, .i.e., most problems you can think of as a layman in the field that are convex, are (probably) tractable to solve. That's why you would be told that in an introductory course on convex optimization. It is not true though.

Tractability of convex problems essentially boils down to being able to decide if a solution $x$ is feasible, in a computationally tractable way (having a so called oracle available). There are convex sets for which this isn't the case. One such example if the set of co-positive matrices. If you are trying to find a matrix $M(x)$ such that $z^TM(x)z \geq 0$ for all $z\geq 0$, you have problems, as it is very hard to decide if a candidate $M(x)$ satisfies that property. Compare to the simple case of positive-semidefinite where all $z$ should lead to non-negativity, this is simply an eigenvalue test and thus semidefinite programming is tractable. Alas, also this statement is up for debate, as it depends on what you mean with solving a problem. A semidefinite programming problem with size $n$ (what ever we mean with that) can have a solution which whose representation grows at an exponential rate $2^n$.