Minimum spanning tree with two minimum edge weights

Yes $G$ has a unique MST (assuming it is not a multigraph). Take a look at Kruskal's algorithm: the edges are ordered ascending by weight and then added to the MST unless there is a cycle. After adding the two minimum edges, you can't have a cycle, therefore both are in the MST.

Edit: As Paresh pointed out, this is not a complete proof, since there may be MSTs which cannot be produced by Kruskal's after permutating equally weighted edges in the sorted list. But Kruskal's is in fact able to produce any MST. Proof.


Yes, it's possible. Here's how to do it.

Obtain the source code for gdb.
Compile with the -g flag on.
Run gdb gdb.


How do we translate first order logic's universal quantifier (the $\forall$) and the existential quantifier (the $\exists$) to Prolog?

Prolog does not support arbitrary first-order logic but only a fragment of it known as Horn clauses. These are statements of the form
$$\forall x_1, \ldots, x_n \,.\, P(x_1, \ldots, x_n) \Rightarrow q(x_1, \ldots, x_n)$$
where $P$ is built from atomic predicates and conjunctions, and $q$ is an atomic predicate. Not every statement in logic can be converted to this form.

You are suggesting use of foreach. Note that this is not properly a logic quantifier in Prolog, but rather a special-purpose routine which operates on lists. Pure prolog does not have any of this. If you are willing to use lists and to limit attention to only quantification over finite lists of elements, then you can just implement everything easily enough in Prolog using lists and functions on them. But that misses the point of logic programming, does it not?


It sounds like the only thing you care about is whether the number of open brackets equals the number of close brackets. In which case, I'd recommend an algorithm something like this:

Look for an open bracket.

If you can't find one, look for a close bracket.

If you find one, reject. Otherwise, accept.

If you can find one, erase it.

Look for a close bracket.

If you can't find one, reject.
If you can find one, erase it.

The exact mechanics of searching for brackets are up to you, but if you need more guidance, I'd recommend using one of your spare symbols ($E$ for empty) to mark empty patches of tape (everything to either side of the input) and the other ($B$ for bracket deleted) to mark things you've erased. That way you can tell when you reach the edge of the input string.


Equivalence classes of regular languages

Let $L$ be a non-regular language, and suppose that there were only finitely many separating words, say $n$. Construct a graph in which vertices are equivalence classes and the edge $([x],[y])$ (where $x,y$ are the lexicographically first words in their equivalence classes, and $x<y$) is colored by the set of words separating $[x]$ from $[y]$, where for each word $w$ we additionally indicate whether $xw \in L$ ("$w<$") or $yw \in L$ ("$w>$").

Ramsey's theorem states that there exists an infinite monochromatic clique $A$ colored $\chi$. Let $[x],[y],[z] \in A$, where $x < y < z$. We consider two possibilities:

If $w< \in \chi$ then we get a contradiction since due to $(x,y)$ we should have $yw \notin L$, whereas due to $(y,z)$ we should have $yw \in L$.
If $w> \in \chi$ then we reach a similar contradiction: considering the same edges as before, we should have $yw \in L$ and $yw \notin L$.

The finitary version of Ramsey's theorem shows that for each $n$, there is $N$ such that every language with at least $N$ equivalence classes must have at least $n$ separating words.


We denote the concatenation of $x$ and $y$ by $xy$. Your relation is $x \prec y$ iff $xy < yx$ (where $<$ is the lexicographic order). You want to show that $x \prec y \prec z$ implies $x \prec z$. Suppose therefore that $xy < yx$ and $yz < zy$. Our goal is to show that $xz < zx$.

Say that two strings $s,t$ are incompatible if neither is a prefix of the other. If $s \prec t$ and $s,t$ are incompatible then there is an index on which they differ, and the first such index $i$ satisfies $s_i < t_i$. Conversely, if there exists an index on which $s,t$ differ and the first such index $i$ satisfies $s_i < t_i$ then $s,t$ are incompatible and $s \prec t$.

The proof is by induction on $|x|+|y|+|z|$. We consider several cases.

Case 1. $x,y$ are incompatible, and $y,z$ are incompatible. Let $i$ be the first index on which $x,y$ differ, and let $j$ be the first index on which $y,z$ differ. Then $k = \min(i,j)$ is the minimal index on which $x,z$ differ and $x_k < z_k$, implying $x \prec z$.

Case 2. $x = yw$. In this case $xy < yx$ implies $ywy < yyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = ywz < yzw < zyw = zx$.

Case 3. $z = yw$. In this case $yz < zy$ implies $yyw < ywy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xyw < yxw < ywx = zx$.

Case 4. $x = zw$. In this case $xy < yx$ implies $zwy < yzw < zyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = zwz < zzw = zx$.

Case 5. $z = xw$. In this case $yz < zy$ implies $xyw < yxw < xwy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xxw < xwx = zx$.

Case 6. $y = xw$ and $x,z$ are incompatible. In this case $xy < yx$ implies $xxw < xwx$, and so $x \prec w$. Moreover, $yz < zy$ implies $xwz < zxw < zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i < z_i$. It follows that $x \prec z$.

Case 7. $y = zw$ and $x,z$ are incompatible. In this case $yz < zy$ implies $zwz < zzw$, and so $w \prec z$. Moreover, $xy < yx$ implies $xwz < xzw < zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x_i < z_i$. It follows that $x \prec z$.


What is a good approach to symbol identification/recognition given a path, instead of raster data

What you are looking for is called "on-line recognition". I have written my Bachelors thesis about this:

  Thoma, Martin. "On-line Recognition of Handwritten Mathematical Symbols." arXiv preprint arXiv:1511.09030 (2015).

And I've created the online service write-math.com as a part of it.

As a short introduction, you might be interested in my presentations.

  Are there any good techniques for doing identification without first rasterizing my paths that may be well suited for my particular instance?

Yes. You can on the one hand make it a fixed-length sequence, on the other hand you can use recurrent neural networks (I didn't try that in my bachelors thesis)

  Is rasterizing to a grid particularly well suited to the problem, and should I just raster and solve this problem more classically?

This works astonishingly well. I achieved better results with the rasterized version (in my master thesis which isn't published yet due to bureaucracy problems at my university) than with fixed-length sequence techniques. But I guess the way to go is to do both.


The assumptions $A[i] \in \mathbb N$ and $A[i] + A[j] \leq n$ together imply that $0 \leq A[i] \leq n$, and so $-n \leq A[i]-i \leq n$. This suggests maintaining an array $B[-n],\ldots,B[n]$, initialized with zeroes. We go over the elements of $A$ one by one. We put $B[A[i]-i] = i$, and then check whether $B[i-A[i]]$ is non-zero, say equal to $j$. If so, then $i-A[i] = A[j] - j$, and so $A[i] - i + A[j] - j = 0$. (This allows $i = j$; if you want to disallow it, reverse the order of these two steps.)


Turing machine + time dilation = solve the halting problem?

Note that Turing's proof is one of mathematics, not of physics. Within the model of a Turing machine Turing defined, undecidability of the halting problem has been proven and is a mathematical fact. Hence, Turing's proof will not 'fail' in the spacetimes, it will simply not prove anything about the relation of the halting problem and time dilation.

However, what you'll likely want to know is whether a 'time dilation Turing machine' can solve the halting problem.

If you want to study this the influence of 'time dilation' on a Turing machine, you'll have to specify a formal model by which we can formally understand what it means for a Turing machine to make use of time dilation. Unfortunately, this format is ill-suited for providing such a formal model (unless someone else has written a paper about it) as creating the model is far too broad.

However, it isn't unlikely that some formalisation indeed is able to solve the halting problem. This paper by Scott Aaronson, Mohammad Bavarian and Giulio Gueltrini looks at computational models under the assumption that so-called Closed time-like loops exist and conclude that the halting problem is indeed computable within that model.


randomized algorithm for checking the satisfiability of s-formulas, that outputs the correct answer with probability at least $\frac{2}{3}$

Basic idea: Pick a random assignment and check it.
Then, repeat it many times. Even if one of the assignments satisfies the formula you answer "YES" (otherwise, you answer "NO")

We know that the input formula is "simple": in plain words it means that either it is not-satisfiable or it has "many" satisfying assignments. If it is not satisfiable - no matter what assignment(s) you choose, it will never satisfy the formula. Therefore, the above algorithm always answers correctly for such inputs, and from this point and on we consider only satisfiable inputs.

If the input is satisfiable, what is the probability that a random assignment satisfies it?

Let $\varphi$ be a CNF over $n$ variables with more than $2^n/n^{10}$ satisfying assignments, then
$$ \Pr_{x\sim U}[ \varphi(x)=T] \ge \frac{2^n/n^{10}}{2^n}$$

Now we repeat it $k$ times (you'll have to pick $k$ carefully. Let's do it later).
Each time we pick a random $x$. Let $E_i$ be the event that in the $i$-th instance $\varphi$ is satisfied. What is the probability that we find out at least one satisfying assignment after $k$ tries?

It is $\Pr[\bigcup_{i=1}^k E_i]$. We know that $\Pr[E_i] \ge 1/n^{10}$, and you can use standard linearity (of independent events) to work it out.

Final step - find the (minimal) $k$ that makes $\Pr[\cup_k E_i] \ge 2/3$ as required.

Bonus question: how low can you make $k$ (and make your algorithm more efficient) if you analyze the above using Chernoff's inequality?


CSP heuristics to help avoid redundancy while checking values for constraint inconsistency?

These are known as variable ordering heuristics.  One standard one is "fail first".  See the "dom" heuristic, i.e., try first the variable with the fewest number of possible values, or "dom+deg", where ties are broken by choosing the variable that participates in the smallest number of constraints.  That would handle the case you list as desired.


Finding maximum and minimum of consecutive XOR values

If $k$ is the bitsize of the integers, then you can compute the Max in $O(n k)$ time.

Basically, the problem is, given $n$, $k$-bit integers $S_i$, find $i,j$ such that $S_i \oplus S_j$ is maximum.

You treat each $S_i$ as a binary string (looking at the binary representation), and create a trie out of those strings. This takes $O(nk)$ time.

Now for each $S_j$, you trying walking the complement of $S_j$ in the trie you created (taking the best branch at each step basically), finding a $j'$ such that $S_j \oplus S_{j'}$ is maximum.

Do this for each $j$, and you find the answer in $O(n k)$ time.

Since your integers are bounded, this algorithm for max is basically linear, and so is the algorithm for min got by sorting (as sorting can be done in linear time).

Incidentally, if there were no bounds, then you can reduce element distinctness to the min version.


How do we know to what community a vertex belongs to in the Girvan-Newman algorithm?

This is hierarchical clustering method. As you remove edges, at some point the graph will become disconnected: the connected components are your top-level communities. As you keep removing edges, the top-level communities become disconnected too, and you can think of the new smaller connected components as sub-communities. So you can think of the algorithm as building a tree of finer and finer communities, where the leaves are individual vertices.


Deterministic processing on probabilistic input

How about ...

Optimal Communication of Agents under Randomized Spatial Distribution


Does the distributive property apply to regular expressions?

since someone has edited the question, the question seems much more meaningful , and yes the above equality holds , here the equations

taking LHS of the equation

= ( $q_1$a  $+$ $q_2$b ) c

=$\delta$ ( (   $q_1$a  $+$ $q_2$b ) , c )  { as you defined Sa={ δ (q,a) ∣q ∈ S} }

=$\delta$ ( (   $q_1$a )  $\bigcup$   $q_2$b ) , c )

=$\delta$ ( ( $q_1$a),c ))    $\bigcup$   $\delta$ ( (    $q_2$b ) , c )

=$q_1$ ac $+$ $q_2$bc

which is equal to RHS.


How to understand pushdown automata intuitively?

Intuitively, a pushdown automaton uses a stack and using a stack we can do a depth first traversal of a parse tree. It means that we can accept strings which are in context free languages by using stack of a pushdown automaton (left-most derivation). This is not a rigorous proof that languages of pushdown automata are context free. For proofs you must see various textbooks on the subject.


Converting Recursion into Into Iteration

Your CPU uses stacks and iteration to run any program, including programs based on recursion.

If you are unsure how this works, I suggest picking up an appropriate textbook.


You can't simply say: "This is a bin packing problem and therefore NP-hard."
Consider the problem of $N$ unit bins and $M$ unit items with the target of maximizing the usage of the bins. Clearly this is also a bin packing problem, but it is not NP-hard.

However, you can reduce to the decision variant of your problem from partition:

  Given a set of items with sizes $a_1, \dotsc, a_k$, can it be partitioned into two subsets of equal size.

Given items $a_1, \dotsc, a_k$, we construct an instance of your problem as follows:

Let $A_i = \sum_{j=1}^i a_j$ amd $A=A_k$.
We introduce $2A+2$ items and $2A+2$ bins.
$g_{i,j} = \begin{cases}
A-a_l & A_{l-1}<i=j\leq A_l\\
A-a_l & A+A_{l-1}<i=j\leq A+A_l\\
0 & A_{l-1}<i,j\leq A_l,~ i\neq j\\
0 & A+A_{l-1}<i,j\leq A+A_l,~ i\neq j\\
2 & A_{l-1}<i\leq A_l,~ A+A_{l-1}<j\leq A+A_l\\
2 & A+A_{l-1}<i\leq A+A_l,~ A_{l-1}<j\leq A_l\\
0 & j>2A,~ i\neq j\\
\frac A2 & i=j>2A\\
0 & i=2A+1,~ j\leq A\\
0 & i=2A+2,~ A<j\leq 2A\\
1 & \text{otherwise}
\end{cases}$
We ask for an assignment with $\sum_{i=1}^{A}\sum_{j=1}^{A} x_{i,j} \geq A+2$.

The construction works as follows:

Any solution will satisfy $x_{i,j}=1 \Rightarrow i=j$.
Items/bins $i$ with $A_{l-1} < i \leq A_l$ resp. $A+A_{l-1} < i \leq A+A_l$ correspond to $a_l$. In a solution, exactly one of the groups will be taken, corresponding to $a_l$ being in the first resp. second set of the partition.
The threshold can only be reached, if the last two items are placed, ensuring that the partition is into two sets of size $\frac A2$.


This are not Real numbers as $\mathbb{R}$, but at this point - CPU has double precision floating point numbers, GPU very low number of units processing them, floats on GPU are halfs.
This is due to graphics (this was the main goal before parallel processing), where results are rounded to display, so speed vs accuracy tradeof went that way.
GPU core frequencies are smaller than CPUs, number of operations is very limited on GPU (boosted by video decoder), and there is a huge difference in branch prediction - CPU has very long and complex prediction, while GPU just recently got it added.

Single core on GPU: it is Streaming Multiprocessor (there are about 4 - 16 per card), it includes cuda cores (which is about 32-64), and they work in lock-step, so it differs from CPU threads (not locked).

It is hard to compare like this, but in short - single core on GPU is still parallel unit working slower than CPU core, less memory, registers and instructions than CPU, with very short branching prediction and preferable half floats, nowadays normal floats but having about one-two processing units for double precision, some time ago integer operations were slower on GPU (not onlu by frequency) - but this changed recently.

The same operation on floats - they are slower on GPU than CPU due to frequency.

You might be interested in AMD architecture, Nvidia architecture and Intel architecture to compare instructions set and hardware differences further.


Why are DCFL not closed under concatenation or Union whereas CFL is?

DCFL does inherit the closure property of its superset CFL: the union and concatenation of two DCFL languages are CFL. What doesn't hold is that the union and concatenation are necessarily deterministic CFL.


Why assume Turing machine can compute arbitrary results in Kraft-Chaitin theorem?

Let's take the example in which $n_i = i + 1$. In this case, we can choose the $i$'th program to be $0^i1$. Here is how the prefix-free Turing machine works. It reads the input, and determines $i$. Now it runs a Turing machine which enumerates the list $\langle s_j,n_j \rangle$ until it reaches $\langle s_i, n_i \rangle$, at which point it outputs $s_i$.

More generally, we choose the programs (i.e., the potential inputs to the prefix-free Turing machine) in such a way that we can effectively convert a program $p_i$ to an index $i$. In other words, contrary to what you write, the programs are not arbitrary, only their lengths are. In general the conversion from program to index might require partial knowledge of the sequence $n_i$.

The actual programs can be constructed greedily. See for example lecture notes of Satyadev Nandakumar, proof of Theorem 3.3.5.


Sequencing or continuation-passing in pure lambda-calculus

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

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

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


Finding often repeating substrings in multiple strings

Let's say you are looking for substrings that occur at least $c$ times in each string and have length at least $k$. Furthermore, lets say we're looking for maximally repeated substrings i.e. if $R$ is our solution set of substrings, there exists no pair $r_i, r_j\in R$ such that $r_i$ is a substring of $r_j$.

Offline option

Construct a generalized suffix tree from all input strings. Any node at depth at least $k$ that has at least $c$ leaves from each input string (i.e. at least $c$ $\$_1$ leaves, at least $c$ $\$_2$ leaves and so on) is $blue$ and each $blue$ node with no $blue$ children is also $red$. The set of substrings represented by $red$ nodes is the set of maximally repeated substrings. This runs in time $O(mn)$ where you have $n$ input strings of length at most $m$.


An algorithm for fitting a rectangle inside a polygon

Let $P=(p_1,\dots,p_n)$ be the polygon and $\overline{P}$ the set of points it contains.

Let $R=(a,b,c,d)$ be the rectangle of width $w$ and length $l$ with $l\ge w$ (and we assume $d(a,b)=w$) and $\overline{R}$ the set of points it contains.

You want $\overline{R}\subset \overline{P}$.

Suppose $\overline{R} \subset \overline{P}$.

Let $q=a+\cfrac{1}{2}\vec{ab}$ and $r=c+\cfrac{1}{2}\vec{cd}$.

Since $q\in [ab]\subset \overline{R}$ and $r\in [cd]\subset \overline{R}$, $[qr]\subset \overline{P}$.

Since $q\not=r$, we can find $s$ and $t$ on the border of $P$ so that $(qr)=(st)$.

Now suppose you are given a convex $P$

Here's the algorithm:

$\forall i \in [1,n]$

$\forall j \in [i+1,n]$

If $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}\ge l$

$s = p_i + k_1 \vec{p_ip_{i+1}}$
$t = p_k + k_2 \vec{p_jp_{j+1}}$
$q = s + k_3 \vec{st}$
$r = q + \cfrac{l}{\|\vec{st}\|}\vec{st}$
$\vec{v}:=$ a vector so that $\vec{sr}\perp \vec{v}$ and $\|\vec{v}\|=\cfrac{w}{2}$
$a := s - v, b:= s + v, c := r+v,d:= r-v$
$S:=solve(\{"k_1\in [0,1]", "k_2 \in [0,1]", "k_3 \in [0,1]", "a,b,c,d\in P"\}$
If $S\not= \emptyset$, return true

return false

The way this algorithm works is it chooses an orientation and an ax for the rectangle by choosing two arbitrary points $s$ and $t$ somewhere on two arbitrary segments of $P$. Then it takes an arbitrary $q$ in $[st]$ and expresses $a,b,c,d$ in terms of the constants $k_i$ determining $s,t$ and $q$. Then for a point, you know how to determine if it is in a convex polygon so you just need to solve those linear inequalities (in $k_1,k_2,k_3$) for all $4$ points. And if you have solutions, $R$ fits in $P$. Otherwise, you just try another one. And if none worked, since we know that if $R$ fits in $P$, then at least one must work, we know $R$ doesn't fit in $P$.

NB: $\max \{d(x,y),x\in[p_ip_{i+1}],y\in[p_jp_{j+1}]\}=\max\{d(p_i,p_{i+1}),d(p_j,p_{j+1}),d(p_i,p_j),d(p_{i+1},p_{j+1})\}$

Then for the non-convex case, you loose the fact that: $a,b,c,d\in \overline{P}\Rightarrow \overline{R}\subset \overline{P}$. So I'm not sure how to do it.

If I had to try, I'd break $P$ into several convex polygons and try to apply a similar algorithm except that I'd try every recombination of $A,B,C,D$ with $a\in A,\dots,d\in D$ with $A,B,C,D$ different convex polygons forming $P$ and then check that the segments of $R$ don't cross segments of $P$...


An FPT algorithm for Hamiltonian cycle running parameterized by treewidth

If you want an FPT algorithm for the problem (parameterized by treewidth $t$), you want an algorithm working in time $f(t) \cdot n^{O(1)}$, where $f$ is any computable function (depending solely on $t$). Of course, it would be nice to make $f$ as appealing as possible.

In addition to the mentioned algorithm running in $O(t^t n)$ time, you can also get a faster (randomized) algorithm using the Cut'n'Count technique of Cygan et al. [1]. In particular, you get an algorithm running in time $4^t n^{O(1)}$. It is also possible to get a deterministic algorithm working in $c^t n^{O(1)}$ (for some small constant $c$) using a rank-based approach of [2].

[1] Cygan, M., Nederlof, J., Pilipczuk, M., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. "Solving connectivity problems parameterized by treewidth in single exponential time." IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.

[2] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. "Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth." Automata, Languages, and Programming. Springer Berlin Heidelberg, 2013. 196-207.


Total functional programming language without an static type checker

The question is, how do you eliminate terms that run forever:

In particular, things like $(\lambda x \ldotp x\ x)(\lambda x \ldotp x\ x)$ and the Y combinator must NOT be in your language, since they can be used to construct computations that do not halt.

Static typing in things like System F eliminates these: they start with a full lambda calculus, and then filter out ill-typed terms.

But, do do this in an untyped setting, you need to eliminate these terms by construction. They cannot be expressible in your language.

I can think of some silly ways to do this, like the language of imperative programs with no functions or and only loops over lists. But in general, as soon as you have higher order functions, these problematic constructs are constructible. So while I won't say that it's impossible, it's probably very difficult to do in a way that makes much sense.

It's possible for you to statically filter out these things with something that isn't a type system, with termination checkers, but these will always throw false positives, and while they aren't static typing, they are still very much a static filter on your programs.

Note that, depending on what you consider "dynamically typed," you could eliminate programs like this by keeping track of types using inference, but only throwing errors at runtime. Thus something like the Y combinator is still rejected, just later. This is dynamically typed, but probably not what you are looking for.


Natural RE undecidable problems but not Turing-complete

There indeed are sets that are undecidable but not Turing complete.  However,  I'm not sure there is such a thing as a natural undecidable not Turing complete language.

Emil Post set out on a search for exactly this (See Post's problem) and his research resulted in the Simple sets.  To quote from the Wikipedia article:

  [Its existence] was affirmed by Friedberg and Muchnik in the 1950s using a novel technique called the priority method. They give a construction for a set that is simple (and thus non-recursive), but fails to compute the halting problem.


The reduction doesn't calculate the values of all cells. Rather, it outputs a circuit which calculates (recursively) the values of all cells. You can output the circuit using only logarithmic space, while evaluating it probably requires more space (unless L=P) since CVAL is P-complete.


Resource bounded reductions for RE-Complete problems

The reduction from $M$ to $HALT$ is essentially the function $x \mapsto \langle x, M\rangle$. This function can be computed very easily in linear time.

$P^{HALT} = Exp^{HALT} = Rec^{HALT}$. The computation you want to perform inside your reduction can be delegated to $HALT$ as part of $M$ in the reduction, i.e. just include the code for wherever you want to do inside your reduction and passed it on to $HALT$ and $HALT$ will execute that for you.

Let's say your reduction from $M$ to $HALT$ is $N$. We can define a new reduction as $x \mapsto \langle x, HALT \circ N \rangle$ from $M$ to $HALT$. The new reduction only attaches a fixed string (the code of $HALT \circ N$) to its input $x$ and computable easily in linear time.

The possibility of delegating work in reduction to $HALT$ is the reason that the reduction class doesn't matter (as long as your class of reductions are computable functions and powerful enough to attach strings) and we end up with the same class of functions when attach a $HALT$ oracle whether the class of reductions is $P$ or $Exp$.


How do you solve this [1,5,9,4] pair numbers problem?

This can be done in $O(n^2 \space log \space n)$.

Insert all N array elements with the indexes into a balanced BST.
For every $i \in \{0,...N-1\}$
For every $j \in \{0,...N-1\} \space and \space j \ne i$
Search for $(A[i]+A[j]),(A[i]-A[j]),(A[i]*A[j]),(A[i]/A[j])$ in the BST and add $(A[i],A[j])$ if it is found in the BST and  its corresponding BST entry $index \ne i\space and \space j$

Steps 1 and 2 runs for $O(n)$ time.
Step 2 runs for $n-1$ times = $O(n)$.
Step 3 runs for $4*log\space n = O(log\space n)$.
Hence, time complexity is $O(n^2\space log \space n)$.


How to determine if prolog query will give an answer or not?

The order of clauses matters in Prolog: they are tried in order. So, the first clause is always tried first, and the second one would only be considered after the first clause fails. As you discovered, this never happens because the first gets stuck in a loop.

If Prolog used a breadth-first resolution algorithm, the clause order would not matter (but it would be far more consuming in terms of memory). Since instead SLD resolution is depth-first, the order does matter because of infinite paths which can lead to non-termination.


How to feel intuitively that a language is regular

The main property of DFA's/NFA's is the lack of unbounded memory. If you look at a language and the only algorithm (which should later be translated into a Finite Automaton) you can think of requires this property, that is, you feel that any algorithm that recognizes it will need to remember an arbitrary large number of things (like $n$ in your example) then that language is probably not regular.

Of course, you should always remember that mathematical intuition can be wrong, and the only way to be sure of your intuition is to prove it.

EDIT: I'll answer the last question in the comments here, because of lack of space.

  you guys are talking about unbounded memory which you mean is the reason why it is not regular. but a^nb^m can also have unbounded memory if i want, doesnot it? this is still giving me no peace.

The issue is not how big the words can get (you will usually encounter infinite regular languages, because every finite language is regular, and that's pretty boring) but how much the DFA needs to remember.
In the $a^mb^n$ example, there is no need to remember $m,n$. The algorihm just needs to make sure they are positive and that the word is correctly ordered. This is a finite list, and each of the items on the list requires a constant amount of memory.
Compare this to $a^nb^n$, for which a simple alogrithm is required to remember that the number of $a$'s is equal to the number of $b$'s. This will require unbounded memory.
When I look at a language and see that any algorithm I can think of needs unbounded memory, my intuition that the language is not regular grows stronger. If I can't find a "smart"  algorithm (one that requires a constant amount of memory) in a reasonable amount of time (how much time is reasonable is up to you) I will try proving the language is not regular.
Hope this makes it a bit clearer.


How to simulate a parallel computer (with certain number of processors) on a serial computer

The Traveling Salesman Problem (TSP) is a classic problem because it's hard to deterministically solve in a decent time frame, classified as NP-hard.  Genetic algorithms can get a good solution more quickly than NP-hard time, but there's no guarantee that you'll find an actual optimal solution.  This can be a good trade-off if you're programming, say, a driving-direction app, but it doesn't get around the NP-hard issue since it doesn't reliably solve the actual NP-hard problem.

Note that genetic algorithms are stochastic (probabilistic).  It's entirely possible that you could guess the exact best solution on the first go, or that you'd never guess it after a billion years.

  I would like to solve the traveling salesman problem (TSP) using a parallel genetic algorithm (GA). I need to write a simulator of a parallel computer (for example, a multicore workstation) that will implement the parallel version of the GA. But the simulator should run on a serial processor.

As others have said, this will cause your program to run slower than if you hadn't split it up.  Parallel solution techniques are inefficient compared to single-threaded solution techniques; the only reason that we use them is to leverage additional processors.  If you don't actually take advantage of additional processors, you pay the cost for it without enjoying the benefit.

That said, almost all modern computers have multiple cores, even cell phones and tablets.  In the paragraph above, "processor" refers to a processing unit, which single CPU's have multiple instances of.  Your computer probably has at least 2 if it's a laptop or 4 if it's a desktop.

Also, note that processors often claim to have twice as many "logical cores".  When doing numerical problems, you mostly just care about physical cores; ignore the additional logical cores.  With Intel processors, this means ignore Hyper-Threading.  With AMD processors, this often means dividing their claimed count by two, since I think that they share floating-point units (FPU) between cores.  Those extra logical cores are useful in common computer tasks where there are thread waits and such, but they're usually harmful in scientific computing.

  Since minimum communication is needed, wouldn't the speed scale with the number of processors?

Ideally, if you get 100% parallelization efficiency, total speed is equal to the speed of each of the individual processors working individually, combined.  Lots of things detract from that ideal, including communication time.

As much as possible, you want to split the problem up into large chunks that a processor can focus on, then combine those chunks at the end, or at least infrequently.

Too much communication will actually make a bunch of processors working together slower than a single one working alone.  For example, consider

return a + b + c + d;  // Single-threaded calculation

If you split this up into

half1 = worker1.Add(a, b);
half2 = worker2.Add(c, d);
return half1 + half2;

, your program will run much slower than in the first case, despite using multiple cores.  The problem is even calling other threads costs far more than simply adding the numbers together, so you've slowed the program down by a huge factor as soon as you do the first worker call.

The trick to remember is that you want to call workers only when you have a lot of work for them to do while the current thread does a lot of work itself.  If that doesn't hold, then it's more efficient to just do the work in the current thread.

  What would we learn from such a simulation that we don't already know?

Nothing, really.  This is a common homework problem in many college classes on optimization, so it's been done hundreds of thousands of times before.  I'm assuming that this is part of one of your homework problem sets.

Conclusion

If you're in college, you may have access to a good version of Visual Studio through Microsoft Imagine (previously called DreamSpark).  If not, you can download Visual Studio 2015 Community (noting that 2017's in RC right now).

If you use C# in Visual Studio, it should be pretty straightforward to create your parallel genetic algorithm optimizer for the traveling salesman problem.  Since your PC's probably already multi-core, you can take advantage of the speed up from it.  But, even if it's not multi-core, you can still do multi-threaded runs, and the OS will interleave the threads to simulate a multi-core process.


$(max,+)$ matrix product with limited number of values

The paper All pairs shortest paths using bridging sets and rectangular matrix multiplication by Uri Zwick shows that the APSP problem can be solved in subcubic time, given a bound on the edge-weights. The APSP problem uses a $(\min,+)$-matrix product. Since $\max_{A} \sum_{a\in A} a = -\min_{A} -\sum_{a\in A}a = -\min_A \sum_{a\in A}-a$, we can express a $(\max,+)$-matrix product as a $(\min,+)$-matrix product and vice versa, as the paper allows edge-weights to be either positive or negative.

So this gives a subcubic algorithm for $(\max,+)$-multiplication when the values are bounded.


How come Datagram Packets between same source-destination pair may take different routes?

Packets are routed individually: each time a router receives a packet, it decides what to do with that packet. It doesn't necessarily make the same decision each time it receives packets for a particular destination. To give a trivial example, somebody might have changed the router's configuration in the time between two packets arriving; a more common example would be a router trying to avoid congested links by sending some packets down a quieter link.


how to express the performance of a policy in policy parameters

I suggest you study reinforcement learning, and possibly Q-learning.  They are aimed at dealing with this kind of situation.

The short answer is that we almost never have a way to give a closed-form formula that measures how good a policy is, as a function of the policy parameters.  Rather, we use simulations: we conduct a bunch of simulations using that policy, measure how well it performs in simulation, and use that our estimate of the quality of the policy.  Then we apply stochastic gradient descent or other optimization methods to find parameter values that maximize the quality of the policy.


$NP$ is the class of problems that, roughly speaking, you can solve by guessing an $y$ of polynomial size (with some magic to guarantee that you guess "right") and then doing a polynomial computation involving $y$ and the original input.

$NP^{NP}$ is the class of problems solvable in this way, if you have access to an oracle for $NP$. After guessing $y$, you're not just allowed to do some polynomial computation, you're also allowed (within this calculation) to solve problems from $NP$ (through an oracle, so in constant time).

The classical $NP$-complete problem of boolean satisfiability is to compute $\exists_x R(x)$ where $R$ is some boolean formula (and $x$ is a shorthand for $x_1,\ldots,x_n$). Its $NP^{NP}$-complete analogue is to compute $\exists_x \forall_y R(x)$.

A slightly more intuitive $NP^{NP}$-complete problem is that of formula minimization: given a formula, can you find a formula of length $\leq k$ that expresses the same (boolean) function?

$NP^{NP}$ is also known as $\Sigma_2 P$, and you will be able to find more info by searching for "polynomial hierarchy" (see, e.g., Wikipedia's article).


What types of string properties are verifiable in polynomial time?

Verifying a property of strings over an alphabet $\Sigma$ is precisely the same problem as checking whether a string is part of a language, called the Entscheidungsproblem or decision problem.

Language : $\Sigma^* \mapsto \{0,1\}$

What you are interested in are 'properties of strings' or in other words 'classes of languages'.

The class you are probably looking for is 'P', which contains all languages for which the decision problem can be solved in polynomial time on a deterministic Turing machine. Interestingly this class is the same as the class of languages for which the decision problem can be solved by polynomial circuits.

All C programs which contain constantly bounded loops belong to P for example (they can easily be turned into a polynomial circuit).
From there you can extend the language to include other loops that terminate in polynomial time. You have to be careful with nested loops. There are special Hoare-type logics for this purpose.


Prove that a DFA will transition to the same state after $\gcd(i,j)$ steps where $i$ and $j$ steps can be taken to reach that state

Consider the sequence $q(n) = \delta(q,z^n)$ for $n \geq 0$. Let $b$ be the smallest index so that $q(a) = q(b)$ for some $a < b$. It is not hard to check that all further iterates cycle through the values $q(a),\ldots,q(b-1)$. Since we are given that $q(i) = q(0)$, it follows that $a = 0$, and so the function $\pi$ on $\{q(0),\ldots,q(a-1)\}$ defined by $\pi(q') = \delta(q',z)$ is a cyclic permutation.

We are given that $\pi^i(q) = \pi^j(q) = q$. Since $\pi$ is a permutation, also $\pi^{-i}(q) = \pi^{-j}(q) = q$. It follows that for any integer $\alpha,\beta$ (not necessarily non-negative) $\pi^{\alpha i + \beta j}(q) = q$. In particular, Bezout's identity shows that $\pi^{\operatorname{gcd}(i,j)}(q) = q$, and so $\delta(q,z^{\operatorname{gcd}(i,j)}) = q$.


Why is this language Turing recognizable and not not-Turing recognizable

What you are missing is that if $\langle M, w\rangle \notin \overline{A_{\mathrm{TM}}}$, i.e. if $M$ halts on input $w$, you don't know whether or $M_1 \notin L$. If $M$ does halt on $w$, but this takes longer than $20$ steps, it would also hold that $M_1 \in L$. Thus, you don't have a reduction here.
That the language $L$ cannot be co-RE is an immediate consequence of Rice's theorem.


We know that there are problems (like the halting problem) that absolutely cannot be solved by a computer because there is no algorithmic solution. But a human cannot solve those problems either.

We also know that there are problems that humans can solve, but which we do not know how to solve with a computer with our current state of knowledge and technology. Problems in image processing ("is there a teddy bear in this picture ?") or natural language processing ("do these two English sentences have equivalent meanings ?") fall into this category. The difficulty here is showing that any of these problems absolutely cannot ever be solved by a computer, given a clever enough program and enough processing power and time - it is not at all clear how you could establish that.

We do not know of any problem that can be solved by a human and absolutely cannot ever be solved by a computer, no matter how powerful.


It takes $\Omega(n)$ time to find the median of a heap in the worst case. The reason is that the lowest levels of the heap (the leaves and their close ancestors) can be very disordered, and they make up the majority of the heap. As a result, if you can find the median on a heap, you can find a median of the $\Omega(n)$ unordered elements near the leaves. Since finding the median in an unordered list takes $\Omega(n)$ time, so does finding the median in a binary heap.

For instance, if finding the median in an unordered array of size $n$ takes a given amount of time, presumably it shouldn't be any faster to find the median of that array if we prepend to it an array of size $n$ consisting of only $-\infty$ and append to it an array of size $n$ consisting of only $+\infty$. Yet, this new array of size $3n$ is a valid binary heap, and its median is also the median of the original unordered array of size $n$. Thus, if we can find the median of the heap in $O(\log 3n) = O(\log n)$ time, then we can also find the median of an unordered array in $O(\log n)$ time.

Since we know that it takes $\Omega(n)$ time to find the median of an unordered array of size $n$, it must also take $\Omega(n) = \Omega(3n)$ time to find the median of a heap of size $3n$.


Are LALR tables equal to SLR tables if the grammar is SLR modulo precedence/associativity of operators?

If a grammar is SLR(1), then: [Note 1]

The SLR(1) and LALR(1) state machines will have the same states

The set of shift transitions in the two machines will be identical (as will the goto actions).

The set of accept transitions in the two machines will be identical.

The set of reduction actions in the LALR(1) machine will be a subset of the set of reduction actions in the SLR(1) machine.

In other words, it is possible for there to be a reduce action in the SLR(1) machine which is an error (or unspecified) action in the LALR(1) machine. In the case of an input which triggers such a reduce in the SLR(1) machine, that input will still eventually trigger an error before another shift transition is taken.
The difference comes from the fact that the SLR(1) algorithm generates a reduction action for a state with a reducible item for any lookahead in the follow set of the LHS of that item. The LALR(1) algorithm only includes the lookaheads which are feasible in the context of the state.
For example, here's a simple grammar:
\begin{align*}
S &\to A \, [ \, A\, ] \\
A &\to \epsilon \, \mid \, ( \, A \, )
\end{align*}
The follow set of $A$ is $ \{ ) , [ , ] \} $.
Now consider any state in which $A$ follows the dot. For example:
\begin{align*}
A &\to ( \, \centerdot A \, ) \\
A &\to \centerdot \\
A &\to \centerdot \, ( \, A \, )
\end{align*}
This state has a shift action on $($ and a reduction action for $A \to$. It's clear that the reduction action should only be performed if the lookahead is $)$; any other lookahead is an error. But since $[$ and $]$ are in the follow set for $A$, the SLR(1) algorithm includes reduction actions for those lookaheads as well. The error will be detected after the subsequent goto action in the state $A \to ( \, A \, \centerdot \, )$. In the LALR(1) table, these two lookaheads will lead directly to an error.
However, there are other entries in the LALR(1) table for this grammar in which the LALR(1) parser will also execute reductions with a lookahead which obviously cannot be shifted. Only in an LR(1) parser are errors detected immediately. (That's not a good reason to use a canonical LR(1) parser).
Notes

I take the view that if conflicting transitions are generated, then the construction algorithm fails and no parser is produced. That's the way the algorithms are described in Aho, Sethi & Ullman, for example (the so-called "Dragon Book"). If you take the equally valid view that a parser is always produced, but is not necessarily deterministic, then the following statements would be true for all grammars.


Interval graphs are chordal graphs, so you can use a linear time algorithm for finding max clique in a chordal graph. This can be done by first finding a perfect elimination ordering, and then using the fact that every time a vertex is eliminated it forms a clique together with its neighbors that are not eliminated yet. Furthermore all maximal cliques appear in this process.

To find the perfect elimination ordering, maximum cardinality search (MCS) is the simplest algorithm and it works in linear time. (I don't know why Wikipedia mentions lexbfs first, it is much more complicated.)


Big Theta for finding combinations of arbitrarily sized subsets from n total elements

If we denote by $q(n)$ the number of permutations, the first few values are
$$\begin{array}{ccccccccc}
n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
q(n) & 1 & 1 & 3 & 6 & 14 & 25 & 56 & 97
\end{array}$$
This sequence can be found at the online encyclopedia of integer sequences, which is a really helpful site. It has a lot of information about the sequence in question, including the fact that you were right in your guess that $q(n)=\Theta(3^{n/3})$.

[Yes, I'm aware that this doesn't answer all of your question, since this only counts how many permutations there are, and doesn't enumerate them.]


Dynamic Programming Recursive Algorithm - Number of heads in a series

Method 1: DFA. Construct a DFA that accepts the language of valid coin tosses (of any length). Let $A$ be a $Q \times Q$ matrix (where $Q$ is a set of states) such that $A(j,i)$ is the number of symbols that cause the DFA to transition from state $i$ to state $j$. The number of coin tosses that you're after is $1_F A^{32} 1_{\{q_0\}}$, where $q_0$ is the initial state, $F$ is the set of final states, and $1_S$ is the characteristic vector of $S \subseteq Q$.

This method actually works with more general automaton models. For example, you can have a DFA in which some transitions are "missing": when at state $i$, upon reading a symbol $\sigma$ you might just get stuck. More generally, UFAs would work.

Method 2: Recurrence relation. This is a reformulation of the DFA approach without mentioning DFAs. Let $A(n,i)$ be the number of binary words $w$ of length $n$ such that $wH^i \notin L$ but (if $i \neq 0$) $wH^{i-1} \in L$, where $L$ consists of all strings with no three consecutive heads. You're after $B(n) = A(n,1) + A(n,2) + A(n,3)$. These sequences are given by the following recurrence:

$A(0,1) = A(0,2) = 0$, $A(0,3) = 1$.
$A(n+1,1) = A(n,2)$.
$A(n+1,2) = A(n,3)$.
$A(n+1,3) = A(n,1) + A(n,2) + A(n,3)$.

I'll let you figure out where these recurrences come from.

We can also come up with a direct recurrence for $B$:

$B(0) = 1$, $B(1) = 2$, $B(2) = 4$.
$B(n+3) = B(n+2) + B(n+1) + B(n)$.

You can prove this recurrence from the preceding ones for $A(n,i)$, and also directly.

Standard methods show that $B(n) \sim C \alpha^n$, where $\alpha \approx 1.839$ and $C \approx 1.137$. In fact, $B(n)$ can be calculated as the integer closest to $C \alpha^n$ for $n$ larger than some constant.


The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that it often takes some work to establish computability. For instance, you mention finite element methods and the problems with their convergence. This proves absolutely nothing about computability of PDEs because there are, or might be, other methods for solving PDEs.

Some references that migth interest you, in order of relevance:

H. Zenil (editor): A computable universe, Word Scientific, 2012.
The nLab has a page on computable physics.
K. Weihrauch: Computable analysis - An introduction, Springer, 2000.


Deterministic vs. Non-Deterministic PDA?

Your definition is wrong. A PDA is non-deterministic if in some state there are several possible transitions. It doesn't matter if that applies to a transition to a final state.

Your example is deterministic. Check:

From state $q_0$ with $Z_0$ on the stack, on reading $a$ there is one possibility. In the same case there is no alternative on input $\epsilon$
Similarly, from $q_0$ with stack $a$, only one option. No $\epsilon$ alternative
In $q_0$, with $a$ on the stack and inputs $a$ and $b$, again one move only. No $\epsilon$ alternative

You can complete the analysis for the other possible combinations of state, stack symbol, an possible input, making sure there is one option for a given input symbol, and if $\epsilon$ input is allowed, no "real" symbol alternative is available (e.g. in $q_1$ with $Z_0$ on the stack, only $\epsilon$ can be read).


The phrase "machine epsilon" is misleading. In reality, it doesn't depend on the machine at all, but on the floating-point data types that the programmer chooses to use.


why DFA to regex by two different methods differ

No, these methods are not guaranteed to yield the shortest regexp.  Therefore, there's no reason to expect them to necessarily yield the same regexp.

Given a regexp $R$, finding the shortest regexp $R'$ that is equivalent to $R$ is known to be PSPACE-complete, by a result of Meyer Stockmeyer.  Consequently, none of these procedures can be expected to yield the shortest regexp.  If they did, then we could just take $R$, convert it to a NFA, then convert it back to a regexp $R'$ using that method, and we'd have an efficient way to find the shortest regexp, implying that P = PSPACE -- something that is not believed to be true.

(In fact, it's even hard to approximate, i.e., to find a regexp that is close to the shortest.)

To learn more, see On Learning Regular Languages on the CSTheory.SE blog.


Cycles in hardness of ST-CON for the class NL

It turns out st-connectivity on a general digraph is log-space mapping reducible to st-connectivity on a DAG. Here is the reduction:

Given a directed graph $G$ of size $n$ and two vertices $s$ and $t$, first create a graph $G'$ by making $n$ copies of every vertex $u$ in $G$ as the new vertex $(u, i)$ in $G'$, where $i$ goes from $1$ to $n$ for the respective copies. Then, represent each edge $(u, v)$ in $G'$ by the transition $(u, i) \mapsto (v, i+1)$. Since any path from $s$ to $t$ is of length at most $n$, it then follows that a path from $s$ to $t$ exists in $G$ if and only if it exists in $G'$. Furthermore, since $i$ is always increasing in $(u, i)$, it is clear $G'$ is a DAG. Finally, the mapping can be computed in logarithmic space.

However, the approach does not work for undirected graphs, because cycles can occur in the layering technique. So although st-connectivity is easy on a tree, as described by my algorithm in the comments, undirected st-connectivity is not (directly) reducible to st-connectivity on a tree.

Therefore SL=L was not established until Reingold showed st-connectivity on an undirected graph is indeed solvable in log-space.


Minimum number of rounds to notify a hierarchy of people with DP

I do not think it is correct.Please consider this example:
Suppose $a$ has $k$ children. Two of them($b,c$) are chains of $k+1$ nodes the other are leaves.
We have:

$OPT(b) = OPT(c) = k$
All other $OPT$ are zeroes.

According to your algorithm we should have $OPT(a)=1+k$
But it is not correct:

let order of notifitions be $b,c,.....$

($c,b..$ is the same and the other are suboptimal)

Notification for the subroot of $b$ will stop at $0+(1+k)=1+k$ (time=0)
Notification for the subroot of $c$ will stop at $1 + (1+k)=2+k$ (time=1)
We don't really care about other leaves(they will all be notified by $k$)

This is different than the output to your algorithm.
The approach that FrankW proposed is the correct one!


Use a PDA.  Suppose you have a PDA for language $L$ and you want to recognize $L^*$.  Given an input $x$, it is in $L^*$ if it can be partitioned as the concatenation $x=x_1 \cdots x_n$ of words $x_i$, where each $x_i \in L$.  Construct a PDA as follows: the PDA nondeterministically guesses the end of each $x_i$ (the boundary between $x_i$ and $x_{i+1}$); if it guesses that it is at a boundary, it checks that it is in an accept state and then pops everything off the stack and then transitions to its start state and continues from there.


Need recursive version of Conflict based backjumping

When a conflict is found during a recursive constraint satisfaction search there may be assignments and inferences in the call stack that have no connection to the conflict.  Instead of backtracking through these ineffectual assignments at exponential cost it is better to jump backward over them in the call stack directly to the most recent assignment that made the conflict inevitable.  This is backjumping.

To implement backjumping in the algorithm above, you would do three things:

Make the BACKTRACK function maintain a counter storing the depth of its call stack.
Instead of simply returning failure, have BACKTRACK also return a number representing the stack depth whose BACKTRACK function should resume execution.  This number would be determined by careful examination of the assignments and inferences that led to the conflict.
Have all calls to BACKTRACK at stack depths greater than the returned number simply return the number rather than continue iterating through ORDER-DOMAIN-VALUES.

All the ORDER-DOMAIN-VALUES assignments between the current level and the backjump target level will no longer happen. This gives exponential computational savings with a cost only linear to the size of the backjump.


Question about proving that Rado's function is non-computable

Thanks for the clarification! I really misinterpreted your question.

Okay, so we have the computable function $f$, the also computable function $F$ that is based on $f$, and the Turing machine $M_F$ with the following behavior:

  when started with a tape with $y$ $1$'s, writes a block of $F(y)$ $1$'s to the right, separated by at least one blank

Note that I used $y$ instead of $x$. So when our TM starts with a tape like

$$\Delta\underbrace{1\ldots1}_{\times y}\Delta$$

the resulting tape will be

$$\Delta\underbrace{1\ldots1}_{\times y}\Delta\underbrace{1\ldots 1}_{\times F(y)}\Delta$$

and we say that $M_F$ uses $n$ states. Note that $n$ is independent of $y$. The number of states doesn't depend on the input of the TM.

Now the machine $M$ does the following:

Start with blank tape: $\Delta$
Write $x$ $1$'s on tape: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta$$
Now mimic $M_F$ with these $x$ $1$'s as a start, i.e. $y=x$: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta\underbrace{1\ldots 1}_{\times F(x)}\Delta$$
Now we mimic $M_F$ again, but this time with the $F(x)$ $1$'s as a start, i.e. $y=F(x)$: $$\Delta\underbrace{1\ldots1}_{\times x}\Delta\underbrace{1\ldots 1}_{\times F(x)}\Delta\underbrace{1\ldots 1}_{\times F(F(x))}\Delta$$

So when we mimic $M_F$ a second time, we simply ignore the $x$ $1$'s at the leftmost of the tape and pretend they are not there. I think the text is implying that executing $M_F$ doesn't moves it too much left and that is understandable, since this behavior can be simulated by using a one-side bounded TM which is equivalent to our usual TM. So by mimicking $M_F$ two times, we would need about $2n$ states for that.


Depending on the context, "all alternative parenthesizations" means either "all possible parenthesizations" or "all possible parenthesizations apart from the one we were just talking about."

The sense of the word "alternative" being used here is "one of two or more available possibilities."


Deterministic pushdown automaton for a given language

Let us start with an automaton for ${2^rc^r}$ for the alphabet $\{2, c\}$. This is quite a standard example. As long as you are reading $2$ add a letter to the stack until you read the first $c$. Then for each $c$ pop a letter from the stack. The word and the stack should finish at the same time.

Now using this automaton we should be able to build one for you language, where the string of $c$s should turn to any concatenation of a staring of $a$s and a string of $b$s and the string of $2$s turns into a concatenation of a string of ones and a string of twos. This means for each zero you read push a letter to the stack until you read the first one. Then for each one push a letter to the stack until you read the first $a$ then for each $a$ pop a letter until you find the first $b$ and then pop for each $b$. The stack should turn empty upon reading the last letter in the world. Note that the DPA should rejects the string if at any point it reads an unexpected letter (a $0$ after an $a$ for example).

Note that one of the substrings might be empty, so you should consider the case of starting with $a$s directly after zeroes for example.


Note that you got it wrong in the question. What you have is that if $Y \leq^p_m X$ and $Y$ is NP-hard, then $X$ is also NP-hard. This is true by definition, unconditional on any other lower bounds known for $X$ or $Y$ (though, as Ryan points out, such lower bounds could be very interesting).

If $X$ is in NP and has a lower bound on its computational complexity that is super-polynomial, it would mean that $P \neq NP$.


Does the write through cache copies the whole block or just the byte which is updated?

I would say that write-through cache always knows which addressable units need to be written, so there is absolutely no reason why it should write the rest of the block. Therefore it does not.

I am intentionally saying "addressable units", because (though I am not sure) it would generally be aligned units of the same width as the bus, i.e. usually 4-byte. But that has no effect here when the elements are 4-byte.

In contrast write-back cache is likely to only keep per-block modified status. However a write-back cache would be delaying the writes and since the consecutive passes through the loop end up overwriting whole blocks, it would still write just 1024 bytes.


How do you prove that polynomial reductions are not symmetric?

You have a good plan of approach.  Now you need to spend some more time pursuing this.  Try to come up with a list of languages $L$ you've seen before, and try different pairs to see if they satisfy the condition.  After some trial and error you should be able to solve your problem.


Number of "hamiltonian tours" from upper left to lower left corner of a grid graph?

I think a divide and conquer strategy is going to work here. The asymptotic runtime isn't great, but fortunately our graph is of fixed size. Pick some arbitrary node, $v$, and partition the rest of the nodes into two sets. The number of hamiltonian tours is the number of paths that start at the upper left, go through all nodes in the first side of the partition and end at $v$ multiplied by the number of paths that start at $v$, go through every node in the second half and end at the bottom left corner summed over every possible such partition. Recursively do this for each partition.


Complexity of computing the antiderivative of a given function

Kawamura, in his paper Lipschitz Continuous Ordinary Differential Equations
are Polynomial-Space Complete, mentions a classical result of Friedman (Theorem 3.4) which implies that computing the integral of an easy function could be a hard task (check the paper for the exact definitions), essentially since integration is like summing over many different values.

The result mentioned above is in the framework of computable analysis. The answer could be different in other models of computation. See Real-number Computability from the Perspective of Computer Assisted Proofs in Analysis for a recent survey of models of computation on real numbers.


what are meta variables in this static analysis book's explanation about types?

A metavariable is a variable that denotes some hypothetical chunk of a program. This distinction is important in the theory of programming languages, where we need to distinguish variables representing program fragments from the variables contained in those programs.
The terminology, I think, comes from logic: if you're defining a logic, you need to define it in some language that's distinct from the thing you're defining. This is the "meta-language", and the variables it uses are metavariables. The history of formal logic and programming languages are deeply intertwined via the Curry-Howard correspondence, so the terminology carried over.


Derek Elkins' comment solved my problem! Here's the solution I came up with:

We create a seperate renaming function rename: Term -> nat -> nat -> Term, which assumes that the name to rename with is fresh. This makes it trivially terminating.

Fixpoint rename (t:Term) (x y : nat): Term :=
  match t with
  | TVar z =>
    if beq_nat y z then TVar x
    else TVar z
  | TApp t1 t2 =>
    TApp (rename t1 x y) (rename t2 x y)
  | TAbs z t =>
    if beq_nat y z then
      TAbs z t
    else
      TAbs z (rename t x y)
  end.

we then define a (somewhat arbitrary) measure of a term:

Fixpoint size (t:Term): nat :=
  match t with
    TVar _ => 1
  | TApp t1 t2 => size t1 + size t2
  | TAbs x t => 2 + size t
  end.

and we can easily prove that renaming preserves this measure:

Lemma rename_preserves_size:
  forall t x y,
    size t = size (rename t x y).

this lemma is used in the final case of substitition in order to prove that the term rename t y' y has the same size as t and thus the call substitute (rename t y' y) t2 x happens on a strictly smaller term.

Now all I need to prove that this is correct.


Understanding the coefficient matrix of Hermite Interpolation

We are looking for a curve
$$ P(u) = a_3 u^3 + a_2 u^2 + a_1 u + a_0 $$
which satisfies the following properties:

$P(0) = P_i$.
$P(1) = P_{i+1}$.
$P'(0) = P'_i$.
$P'(1) = P'_{i+1}$.

In terms of the coefficients $a_0,a_1,a_2,a_3$, these are:

$a_0 = P_i$.
$a_3 + a_2 + a_1 + a_0 = P_{i+1}$.
$a_1 = P'_i$.
$3a_3 + 2a_2 + a_1 = P'_{i+1}$.

In matrix form, this reads:
$$
\begin{pmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{pmatrix} =
\begin{pmatrix} 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 \\ 3 & 2 & 1 & 0 \end{pmatrix}
\begin{pmatrix} a_3 \\ a_2 \\ a_1 \\ a_0 \end{pmatrix}
$$
Inverting the matrix, we get
$$
\begin{pmatrix} a_3 \\ a_2 \\ a_1 \\ a_0 \end{pmatrix} =
\begin{pmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}
\begin{pmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{pmatrix}
$$
Therefore the equation of the curve is
$$
P(u) = \begin{pmatrix} u^3 & u^2 & u & 1 \end{pmatrix}
\begin{pmatrix} a_3 \\ a_2 \\ a_1 \\ a_0 \end{pmatrix} =
\begin{pmatrix} u^3 & u^2 & u & 1 \end{pmatrix}
\begin{pmatrix} 2 & -2 & 1 & 1 \\ -3 & 3 & -2 & -1 \\ 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \end{pmatrix}
\begin{pmatrix} P_i \\ P_{i+1} \\ P'_i \\ P'_{i+1} \end{pmatrix}
$$


Halting problem - one issue that's bothering me

No, you cant prove this for every algorithm (Turing machine). This becomes a question about the nature of proofs rather than a question about computation.

Consider the following Turing machine $M(x)$: check if there exists a proof for the statement $\forall x \hspace{1mm} M(x)$ halts, of length $\le |x|$ (for explanation on the self reference, see Klenee's recursion theorem). If such proof is found, get into an infinite loop (otherwise halt).

Clearly you cant prove $M(x)$ halts for all $x$, since if you can find a proof of length $p$, it wont halt for all inputs of size $\ge p$. In addition, you cant prove $M(x)$ doesn't halt for some $x$, since this would mean there exists a proof for the halting of $M$ on all inputs (contradiction). The situation here is, that if our axiom system is consistent, then $M(x)$ halts for all $x$, but you cant prove it (meaning you can prove in your theory $T$ that if $T$ is consistent then $\forall x \hspace{1mm} M(x)$ halts, but you cant prove it halts without this assumption, unless your system is inconsistent).


Hint:
$$\sum_{i=1}^n \sum_{j=i}^n (n-j) = \sum_{i=1}^n \sum_{j=0}^{n-i} j. $$
At this point, you can either use exact formulas, or notice that for all $d \geq 0$,
$$\sum_{k=1}^m k^d = \Theta(k^{d+1}).$$
(If you don't know what a $\Theta(\cdot)$ bound is, suffice it to say that it is a "tight" $O(\cdot)$ bound.)

After you handle the inner sum, you will need to use the same trick of replacing $i$ with $n-i$ in order to handle the outer sum.


Efficient queriable data structure to represent a screen with windows on it

An easy optimization to the naive algorithm is to skip some points when you check one covered by a window. Say you scan left-to-right, top-to-bottom. If you encounter an $(x, y)$ in window $w = (l, r, w, h)$, you can jump from $x$ to $l + w + 1$ and continue. If windows are big and don't overlap, off the cuff, I'd wildly conjecture that would give you an $O(p)$ algorithm, where $p$ is the number of points in the set you return.

In fact, it could be beneficial to see whether the windows are generally wider or taller. For tall windows, it would be better to scan top-to-bottom, left-to-right; for wide windows, the method discussed above should win out. You might be able to take the idea and do scan/skip diagonally to get balanced performance across the board.

In fact, scanning left-to-right, top-to-bottom, you can remember for subsequent $h$ rows (values of $y$) that you will need to skip at the same $x$ value to the same $l + w + 1$ value, if you reach the $x$ (you might not if there's another window that overlaps). This would make top-to-bottom, left-to-right and diagonal scanning unnecessary to get equivalently good performance.

More generally, you now have two data structures: one with $O(1)$ preprocessing/construction overhead and $O(w)$ lookups, and one with $O(p)$ (possibly; maybe you can do better, or maybe my optimization doesn't really achieve this) preprocessing/construction and possibly $O(1)$ (hash/lookup table) or $O(\log p)$ (BST). So there are already two alternatives, both of which are pretty good, really...


Wagner Fischer Algorithm and the Empty String

The Wagner–Fischer is a dynamic programming algorithm. You can think of a dynamic programming algorithm like a recursion. Every recursion needs a base case (like in induction). In this case, the base case is prefixes of length zero. We could also use prefixes of length one as a base case, but the simplest implementation of the algorithms starts with prefixes of length zero.

The prefix zero case can actually happen, for example when both strings have disjoint sets of letters.


How do I show this variant of the longest path problem is NP-hard?

Hint 1. The graph doesn't have to be connected.

Hint 2. Mouse-over the following for a slightly more detailed hint.

   Arrange for there to be two components. One of them has quite a long path, which you can easily find.


Optimal solution algorithm for K-center problems

An optimal solution for the k-center problem can be found by an exhaustive search over the solution space, and by picking the best solution. The problem is NP-Hard for more than 2 dimensions, and moreover any $\delta$-approximation for $\delta < 2$ is NP-hard.


$\Omega(\sqrt[3]{n})$ lower bound on random-access memory?

If you are talking about latency, yes, that sounds right to me.  A lower bound on distance implies a lower bound on latency, due to speed-of-light considerations.  However in practice these speed-of-light considerations probably do not dominate until the amount of memory is extremely large.

By the way, the situation is different if we are talking about bandwidth (i.e., the number of random-access memory operations performed per second), rather than latency.  One can process many random-access memory operations concurrently, by using sorting networks.

One important caveat is that you seem to be assuming an architecture where we have one big CPU on the left and one big memory on the right, and they are separated somehow.  However that's not necessarily the only way to structure a computation.  One can also structure a computation, for instance, as a parallel computation, where you have a 2-D or 3-D mesh of small processors each with their own local working memory.  Now accessing your local memory can be very fast, whereas accessing far-away memory is slow.  In some sense there is still a $\sqrt{n}$ or $\sqrt[3]{n}$ bound operating, but the $n$ is much smaller for local memory than for far-away memory, so if your algorithm is designed in a way that ensures that most memory operations are to local memory, then you may be able to "beat" the lower bound you described (in some sense).

In computer architecture, one often measures the performance of a circuit by the $AT$ measure: in other words, the area of the circuit ($A$) multiplied by the time it takes for the circuit to complete a computation ($T$).  If you like, you can think of this as a price-to-performance ratio: it is the price (which is assumed to be proportional to the area of the circuit) divided by the performance (the number of computations that can be performed per second, i.e., the inverse of $T$).  A standard architecture with a single beefy CPU and one big memory is not always the optimal architecture.  Sometimes you can get large speedups (more than a constant factor) by using parallel computation or other architectures.  This is at least partly due to exactly the issue that you mentioned: it is much faster to access memory that is near you than to access memory that is far away.  Caching (e.g., L1 cache, L2 cache, etc.) is also based upon the same principle.

Below is an example of a paper in the world of cryptography that considers design of special-purpose circuits for cryptanalytic tasks, and takes these issues into account.  For instance, it has a bunch of processors, a big memory, and a sorting network in between the two to route memory accesses from the processors to memory.  This enables a high number of memory operations to be "in flight" at once, even though it does not eliminate the latency.

The Full Cost of Cryptanalytic Attacks.  Michael J. Wiener.  Journal of Cryptology, 2004.

If you want to dive further into this line of thinking, there is an interesting (but mostly theoretical) debate one can have over whether the right metric is area or volume, i.e., whether the right lower bound is $\sqrt{n}$ or $\sqrt[3]{n}$.  Yes, the world is three-dimensional, but heat dissipation is two-dimensional; a massive cube of computers would be limited by its ability to dissipate heat, which scales with its surface area, not its volume.  One can continue onward in this vein. If this sounds like a fascinating topic, see Q.9 (pp.45-46) of the following paper:

Non-uniform cracks in the concrete: the power of free precomputation.  Daniel J. Bernstein and Tanja Lange.  ASIACRYPT 2013.


Example of Soundness & Completeness of Inference

You have almost got it right, but your definition of soundness is not quite right, or perhaps too subtle.

I would say that the inference algorithm is sound if everything returned is a needle (hence some needles may be missed) and complete if all needles are returned (hence some hay may be returned too).


Why is the most probable assignment for all variables in MRFs called MAP assignment?

MLE is a point estimate $\hat{\theta}_{\text{MLE}}$ that resides at a mode of the likelihood density. That is,
$$L(\theta; X) = \Pr(X | \theta)\\
\hat{\theta}_{\text{MLE}} = \arg \max_{\theta} \Pr(X | \theta)$$

MAP stands for maximum a-posteriori. It is a point estimate $\hat{\theta}_{\text{MAP}}$ that resides at a mode of the posterior distribution (the distribution over the parameters themselves conditioned on our observed data). We can perform MAP estimation by incorporating a prior distribution for our parameters.

$$ \Pr(\theta | X) = \frac{\Pr(X | \theta) \Pr(\theta)}{\Pr(X)} \\
\Pr(\theta | X) \propto \Pr(X | \theta) \Pr(\theta) \\
\hat{\theta}_{\text{MAP}} = \arg \max_{\theta} \Pr(X |\theta)\Pr(\theta)$$

This is a simple application of Bayes' Theorem. The reason we use "proportional to" is that we don't care about the marginal likelihood constant. Since it is only a constant our point estimate for this "psuedo-MAP" still corresponds to a point-estimate for the true MAP. By definition $\hat{\theta}_{\text{MAP}}$ is the (at least locally) most-probable estimate under the posterior distribution.

The key take-away is that the Maximum Likelihood estimate is the point estimate that maximizes the probability of observing your data. The MAP estimate is the point estimate that is the (at least locally) most probable under your posterior distribution of parameters. In the end deciding whether to use the MLE or MAP estimate is up to you and your model. It really depends on what you are more interested in.

To stress the difference one last time, look at the difference between the two definitions for the distributions being maximized over. In ML estimation we are maximizing over the distribution of observing our data; in MAP estimation we are maximizing over the distribution of parameters themselves. Hence why we can say MAP estimates are the most-probable estimate whereas we cannot for the ML estimate.


Is the language $\{ 0^m 0^n : 0 \leq m \leq n\}$ regular?

Some people can be absolutely sure, and at the same time absolutely wrong. In this case, you are one of those people.

A language is a set of strings. A language is not the rules that were used to express the language. $0^*$ and $\{0^m 0^n: 0 ≤ m ≤ n\}$ are the same language, even when that language is expressed in two different ways. And $0^*$ and $\{0^m 0^n: m ≥ n ≥ 0\}$ is again the exact same language, just expressed differently.

Your attempted "pumping lemma" proof fails for the same reason: For example, $0^5 0^4$ is in the language, because it is exactly the same string as $000000000$, which is again the exact same string as $0^0 0^9$.


Show that the inequality holds for all positive integers

We are not going to prove that $a_k\geq 3a_{k-1}$ because it is not true: $$a_3=2a_2+3a_1=2\cdot 9+3\cdot 2=24<3\cdot 9=3a_2$$

We also don't have $a_k<3^k$ for all $k$, since $a_2=9=3^2$. That's probably a typo.

Let's prove, by induction, that for all natural $k$ we have $a_k\leq 3^k$.
We have that $a_1=2\leq 3=3^1$.
Assume that $a_{k-2}\leq 3^{k-2}$ and $a_{k-1}\leq 3^{k-1}$. Or you can assume that $a_t\leq 3^t$ for all $t<k$.
Then
$$\begin{align}
a_k&=2a_{k-1}+3a_{k-2}\\
&\leq 2\cdot 3^{k-1}+3\cdot 3^{k-2}\\
&=3\cdot 3^{k-1}\\
&=3^{k}
\end{align}$$
Therefore, $a_{k}\leq 3^{k}$.
By induction, for all natural $k$ we have that $a_{k}\leq 3^k$.


Oh. That's a disappointing explanation in the book.  I suggest that you don't rely on that explanation for precise details about deterministic CFGs; it looks like it is trying to give intuition, but it is not the place to look for formal definitions, rigor, or precision.  I'd suggest looking at a well-regarded automata theory textbook.  (Hopcroft, Motwani, and Ullman's book is well-regarded, though I haven't checked specifically whether it has a definition of deterministic CFG.  Sipser is also good.)

As Yuval says, the definition of a deterministic CFG is not completely standard.  I think I've seen multiple slightly different definitions.  Here are the basic concepts:

The definition of a deterministic pushdown automaton is standard.  (There are two variants, acceptance by final state and acceptance by empty stack; normally we use acceptance by final state, unless otherwise specified.)
The definition of a deterministic context-free language is standard: $L$ is a deterministic context-free language if it is accepted by any deterministic pushdown automaton.
The definition of a deterministic context-free grammar is not completely standard.  If I remember correctly, I think it can be defined in a few slightly different ways.  The one thing everyone agrees on is that, no matter what definition of deterministic CFGs you pick, the languages that can be accepted by such grammars should be exactly the deterministic context-free languages.  But there are a few different ways to place restrictions on a CFG, while achieving this property.  In particular, you can define deterministic CFGs in a way that allows it to include $A \to \lambda$ rule.  Perhaps there is another definition that doesn't allow such rules, and perhaps your textbook has that definition in mind.  Since your book doesn't state a precise definition, one can only guess.  Perhaps the author decided that the exact specifics aren't too important, for the book's purposes.

The bottom line is: your question seems perfectly reasonable.  I don't think the problem is that you lack understanding of something important.  I think the problem is that the textbook is just written in a confusing way, on this particular point.


Can the intersection two non-recursive sets be recursive? Prove it

Short answer: there are such languages.
Take some language $L\notin RE\cup co-RE$ (look at the explanation at the end for why such a language exists). Then both $L$ and $\bar L$ are not recursive, and are not even recursively enumerable. But, its obvious that $\emptyset=L\cap \bar L$ is a recursive set.
Claim: there is some $L\notin RE\cup co-RE$.
Proof:
Why would such $L$ exist? We will compare the sizes of $RE\cup co-RE$ and the set of all languages.
$RE$ contains only $\aleph_0$ languages, since each language has to be recognized by some turing machine, and turing machines we can ultimately be encoded in text. More formally, we know that for any $A\in RE$ we must have some turing machine $T$ that recognizes it, and $\langle T \rangle\in\{0,1\}^{\mathbb{N}}$. But $|\{0,1\}^\mathbb{N}|=\aleph_0$, and thus $|RE|\le\#\text{TM}\le|\{0,1\}^{\mathbb{N}}|=\aleph_0$. A similar argument can be done to show that also $|co-RE|=\aleph_0$ and combining the two, we get $|RE\cup co-RE| = \aleph_0$
Now, notice that the set of all languages, is precisely $P(\{0,1\}^{\mathbb{N}})$, and thus it has $2^{\aleph_0}$ elements in it. Since $2^{\aleph_0}>\aleph_0$, there must be some $L\in P(\{0,1\}^{\mathbb{N}})$ such that $L\notin RE\cup co-RE$, and thus we proved the claim.


Recognizing finite state machines with repetition

Finite automata in which the transitions are regular expressions might be the model you are looking at. Indeed you could have transitions of the form $p \xrightarrow{aa + bbb} q$ to indicate that in order to go from $p$ to $q$, you need either 3 $a$'s or 2 $b$'s.
This model has the same expressive power as NFAs and DFAs.


$\sqrt{n}$ belongs to the class of sublinear polynomials since $\sqrt{n}=n^{1/2}$.

From Wikipedia (beware of the difference between Little-o and Big-O notations):

  An algorithm is said to run in sublinear time if $T(n) = o(n)$

Note that constant factors do matter when they are part of the exponent; therefore, we can consider $O(n^{1/2})$ to be different from (and less than) $O(n)$.

With respect to the relationship between $log(n)$ and $\sqrt{n}$, you can find here a discussion about why $\log(n) = O(\sqrt{n})$.


Space-efficient representation of potentially very large arbitrary-precision rationals?

Representing a rational number as ${a \over b} \times c^d$ where $a,b,c,d$ are integers can represent all three classes of numbers you mentioned efficiently.  You can do standard operations on numbers represented in this way, but some of those operations will be inefficient: for instance, $10^{10000000}+1$ will be inefficient.

For any representation you have in mind, there will be some rational numbers that can be specified concisely in English but that require a huge amount of memory to represent with that representation scheme, so there is no one answer that will handle everything efficiently -- the best you can do is probably to identify the classes of numbers you want to represent efficiently and then choosing a representation that handles those particular classes.


Are physical laws uncomputable in any type of computation (according to this article)?

The reasoning given in the paper is too vague to be of much value. The question whether laws of physics are computable cannot be decided by a philosophical discussion. It already takes some hard physics and math to even properly formulate the question.

Let me give an analogy. It is impossible to travel faster than light, right? But if I shine a laser at the moon and move it fast enough, the laser dot on the moon will move faster than light. So how is this possible? We have a contradiction in physics. Or do we?

It is easy to have a discussion about computability in the real world, or computability of the laws of physics, at the level of the previous paragraph. For instance, the very nice and seriously presented result on the Undecidability of the spectral gap is easy to misinterpret, because the devil is in the details. The actual experiment cannot be set up because it requires unrealistic conditions. If we approximate the experiment, then the theorem does not hold anymore. But this does not stop people from misinterpreting the result.

For a more reasonable account of computability of the laws of physics I recommend A computable universe, in which you can find discussions of many aspects of computability. If you are interested in computability of the laws of physics then the Matthew Szudzik's contribution The Computable Universe Hypothesis.

Personally I would say that the question "is the universe computable" is ill-formed, because this is not a falsifiable statement. The question "are the laws of physics computable" makes more sense, but one really has to be careful how it is phrased.


Are these two relations on integers partial orders?

Let's look at all the different criteria (reflexivity, symmetry or antisymmetry, and transitivity) for the first relations, $aR_1b\Leftrightarrow a=2b$ :

a) Is it reflexive, or antireflexive, or neither?  For this we want to test $aR_1a$ — or in other words, whether $a=2a$.  This can hold if $a=0$, but otherwise it never holds.  So on $\Bbb{Z}$ the relation is neither reflexive nor antireflexive; but on $\Bbb{N}$ (the set of 'whole numbers', not counting 0) it would be antireflexive, since $a=2a$ can never hold there.

b) Is it symmetric, or antisymmetric, or neither?  Here we want to compare $aR_1b$ and $bR_1a$ where $a$ and $b$ are distinct values; in other words, can we have both $a=2b$ and $b=2a$?  Dividing by 2, the latter is equivalent to $a=\frac{1}{2}b$, and the only way we can have both $a=2b$ and $a=\frac{1}{2}b$ is to have $b=0$, in which case $a=0$ — but since we said that $a$ and $b$ had to be distinct, this can't hold.  In other words, if we have $aR_1b$ for $a\neq b$ we can never have $bR_1a$; the relation is antisymmetric.

c) Is it transitive?  (Note that we never ask about 'antitransitivity', even though the concept hypothetically makes sense).  For this, we want to figure out if $(aR_1b)\wedge(bR_1c)\implies(aR_1c)$ — in other words, if $a=2b$ and $b=2c$, is $a=2c$?  Well, if $a=2b$ and $b=2c$, then we have $a=2b=2(2c)=4c$, so it's definitely not the case that $a=2c$; this relation is not transitive.

Since this has the feel of homework, I'll let you do the second one yourself, but it should be relatively straightforward (as long as you know a little bit about divisibility).  For looking at reflexivity, you'll have special cases again where $a=0$ and also where $a=\pm1$ to keep an eye out for; for symmetry you should be able to use the divisibility to say something about the relative order of $a$ and $b$; and for transitivity you should try to figure out how to 'staple' the two conditions $a^2|b$ and $b^2|c$ together to see if you can figure out whether $a^2|c$.


Hash function to hash 6-digit positive integers

A hash table usually uses two different things: One, a hash function that maps an item to a hash code (with the requirement that equal items are mapped to equal hash codes), and two, a function that maps hash codes to locations in the hash table where the item would be stored.

Hashing every UID to a different 32 bit hash code is trivial - just hash every UID to itself. No collisions. The mapping function of the hash table should be implemented in a way that common hash functions don't lead to many collisions. Many hash functions either produce results that look like random, or like in this case might produce many consecutive values, so using a prime number as the hash table size and (hash code modulo hash table size) as the first location for the location in the table works quite well.

Since you have one million items, and 524309 entries, it's impossible to guarantee no collisions. In practice, that's not a problem. What counts is the time for calculating the hash code, plus the average time for finding and checking one or more locations in your hash table. As long as the average number of collisions is small, you are fine. And there is a simple way that usually keeps the number of collisions small: Use a generous size for the hash table.


Convert for loop into math sigma notation

Let me define
$$f(x) = \begin{cases} 0 & x \ne 0 \\
 1 & x = 0\end{cases}$$
Now it is
$$ \sum _{i=0}^{{N\over2}+1}\:f(N \text { mod } 2^i)$$
The code calculates how many times number is divisible by two (which by the way could be simplified to checking number of trailing zeros in binary representation, say hacky method x & -x).

You can define {N, 2} for the highest power of a prime 2 that divides N, and it is the valid notation. There are other approaches and notations of greatest power of two dividing N at MathOverflow.


Stuck in converting finite automata to its corresponding regular expression

Let's merge IV.

We have three edge transitions to consider:

IV to I, consuming a b (1)
IV to V, consuming an a (2)
III to IV, consuming a b (3)

The only way I can enter state IV is via III (3). Hence, any state that can be reached from IV can also be reached from III.

Let's now look at the path III -> IV -> I, which is the concatenation of (3) and (1). Let's forget about states for a second and simply look at paths and the consumed symbols. There exists a path ((3),(1)) that allows us to get from III to I by consuming a bb.

Due to this fact, we can just add an edge III to I consuming a bb without changing the accepted language of the automaton. It's just a shortcut for the existing path. Once we added the edge, the original path is redundant. If I'm sitting at III, instead of walking the path (3),(1), I can just take the shortcut.

Once I have made all the paths redundant that pass through a state, the state itself becomes redundant and I can remove it along with all its edges.

We can apply the same logic to III -> IV -> V. This introduces a shortcut edge III to V consuming a ba.

With those two in place, we have covered all paths that pass through IV. You can easily enumerate all paths by taking the Cartesian product of incident and outgoing edges: I have a certain number of ways of reaching the state, and for each of those I have to consider all the possible ways of exiting the state again.

Now it's just rinse and repeat. Pick a state, enumerate all paths through it, insert shortcut edges that make all paths redundant and then remove the state along with all its edges.

The only thing to watch out for are loops. The answer you linked in your question should give you a good idea how to deal with those.


What Exactly Does the Term "Key" Mean with Regards to a Hash Table?

Their difference is the role that they have in the ordering and addressing of the table. The key is used to address a specific object (it's usually calculated using some algorithm or hashing function), while the rank is used to order objects and their respective keys using a specific ranking rule.


How is the Longest Path Problem NP complete?

How does that guarantee that there is a hamiltonian path from s-t?

It doesn't, but the Longest Path problem doesn't require a path between particular vertices, it only requires that some simple path of length $K$ exist in the graph.  To reduce Hamiltonian Path to Longest Path you just require that path to have $|V| - 1$ edges, which in a simple path must involve all the vertices in the graph, making it a Hamiltonian Path.


Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP?

Yes, this is true.

To see this, notice that cliques and independent sets are complementary. That is, a set of vertices $S$ is independent precisely when $S$ forms a clique in the complement of the graph. Intuitively, this means that if you had an approximation algorithm for finding a maximum clique, you could use it to find a maximum independent set by executing it on the complement graph.


In O(1) get the coordinate i,j of a diagonally ordered matrix

These are triangular numbers, so:
$i = \lfloor(-0.5 + \sqrt{0.25 + 2 * n}\rfloor - 1\\
triangular = \frac{i * (i + 1)}{2}\\
j = n - triangular - 1$

Minus one comes from indexing from 1.


Undecidable problems limit physical theories

This was initially intended as a comment, as it side-steps a bit the
question. But I think it does answer in its own way.

What is known, or attempted so far, shows that connecting computation theory with physics can
be a pretty subtle endeavour, and I am afraid that the approach
suggested in the question is probably a bit too crude. I am not sure it
is much better than the classical argument that, everything being
finite, all we need is finite state automata theory, and that studying
Turing machines is a waste of time.  (Not my view of things)

Why should such issues be addressed with caution

I should probably motivate the above comparison with the finite
automata argument. My perception is that
computability is, maybe even more than complexity, an asymptotic theory: what
matters is what occurs at infinity. But we do not know whether the
universe is finite or infinite. If it is finite, then what would be
the point of considering infinite computations. The following concerns
physics, and I am not a physicist. I do my best to be accurate, but
you have been warned.

We often see the Big Bang as a "time" when the whole universe was a
very tiny something, with a very small size. But if it had a size at
some point, how did it transform into something infinite at a later time. I am not trying to say it is impossible ... I do not have the
slightest idea. But it could be that it always was infinite.

Then, let us consider the universe as infinite. Does it help us? Well,
we have some problems with the speed of light. If we consider what may
be relevant here (where we are), we have to consider that we can be concerned only by
a part of the universe that is included in a finite sphere. The radius
$r$ of that sphere is such that the relative speed of two points at
distance $r$ due to expansion is equal to the speed of
light. According to what we currently know, without a future variation
in expansion speed, nothing outside that sphere will ever be of
concern to us. So the universe is finite for us for all practical
purposes. Actually, things are even worse if you consider the contents
of this relevant universe: it is shrinking (unless there is some
creation process). The reason is that the sphere is expanding beyond
its own diameter, carrying with it some of its content that becomes
irrelevant too. Remark: that sphere is not what is called the
observable universe (which is dependent on the age of the universe), it is much larger.

Thus, not only "our" universe is finite, but its resources might be
shrinking.  It is possible that in so many billions
years, only our galaxy might be still relevant to us (assuming we
still exist), with the Andromeda galaxy which will hit the Milky Way
before then.

Well, I do not know what is considered established at this time, but
it shows at least that assuming infinity is a big assumption.

However, is it the case that physical limitations prevent us from
using computability theory.  All that can be concluded from the above
is that it may be unreasonable to draw physical conclusions from the
theoretical work on Turing Machines and the halting problem.

However the concerned techniques may also give useful results when
applied to devices or formalisms that are not Turing-complete. I would
not try to go into details, if only because algorithmic complexity is
not my area, but I would guess that, if the structure of the universe
is discrete, complexity could be in some form relevant to the behavior
of some phenomena. Of couse, this is only wild speculation on my
part. Some of the research I reference below is related to such
discreteness issues.

Some examples of work relating physics and computation theory

There is a significant body of work trying to tie computation and
physics, most of which I barely know of.  So, please, do not rely on anything I
might say, but simply take it as pointers to search for potentially
relevant work.

A good part of that work is concerned with thermodynamic aspects, such
as the possibility of reversible computing with no energy cost. I
thinks this ties with functional programming as it is side-effects
that cost energy (but do not trust me). You may take wikipedia as an
introduction, but Google will yield many references.

There is also work trying to tie Church-Turing thesis and physics,
involving information density among other things. See for example:

The physical Church-Turing thesis and the principles of quantum
theory
Around the Physical Church-Turing Thesis:
Cellular Automata, Formal Languages, and the
Principles of Quantum Theory,
Physics and Church-Turing Thesis.

I vaguely recall seen other
interesting takes on this, but it escapes me right-now.

Then you have Lamport's work on clocks synchronization and relativity
in distributed systems.

And, of course, you have quantum computing that apparently changes
some (achievable) time-complexities, though it does not affect
computability.

Another take is Wolfram's work on modelling physical laws with
cellular automata, though the real benefits of this work seem
disputed.

I think that trying to understand all this work could get you closer
to understanding how you can tie some computability knowledge with (as implying)
theoretical limitations of the physical world, though the trend so far
was more to tie limitations of computability to (as consequences of)
properties of the physical universe.

One possible problem in all this is the self-embedding of all our
theories (mathematics, computation, physics, ...) within the limits of
concepts that are syntactically expressible (i.e. by a language)
which might set a limit on the expressive power of our science. But I
am not sure whether the preceding sentence has meaning ... sorry about
that, it is the best I can do to express one nagging doubt.

As an account of personal disappointment, I would add that physicists
(at least on http://physics.stackexchange.com) are not very amicable to discussing what other sciences could have to say
about physical issues (though they are quite willing to discuss what
physics may have to say about other sciences).


Hamiltonian cycle, verifying and finding

Let $P$ be an arbitrary simple path in the graph. If $P$ appears in a Hamiltonian cycle of the graph, you can remove all the vertices of $p$ except the first and the last vertex, connect these two vertices with an edge and the resulting graph must be Hamiltonian.

Keeping this in mind, we can build the Hamiltonian cycle step by step starting with path of length one, since you already described how to build such a path. Then we can extend a path of length $i$ to a path of length $i+1$ using the trick above, where we try all neighbors of the last vertex in the path as a next vertex and we apply the trick above to check if a Hamiltonian cycle exists where the new path is a part of the cycle. Note that we call the black-box at most $m := |E|$ times. Once we reach a path of length $n-3$ it is easy to complete the path into a Hamiltonian cycle in linear time.