What algorithm do computers use to compute the square root of a number?

Have a look at the paper
https://www.lirmm.fr/arith18/papers/burgessn-divider.pdf
which describes the division / square root hardware implementation in some ARM processors.
Roughly the idea: For a division unit, you can look up the initial bits of divisor and dividend in a table to get two bits of result. For double precision with a 53 bit mantissa, you repeat that 26 or 27 times and you have the result. For single precision with 24 bit mantissa, you need to repeat only 12 or 13 times. All the other bits, calculating the exponent etc., can be done in parallel.
Now what does square root have to do with division? Simple: sqrt (x) = x / sqrt (x). You get the square root by dividing x by its square root. Now when you start this division, you don't know the square root yet. But as soon as you have say eight bits and you are very, very careful, you can produce two mantissa bits per cycle. And getting the first say eight bits is not hard, since unlike a division x / y, there is only one operand involved.
The paper describes this in much more detail, and importantly describes why this is superior for example to using Newton-Raphson or similar. Note: It is superior for typical floating-point numbers with 24 or 53 bit mantissa. Since that is what is used 99.9999% of the time it is important, but for different situations things are different.


Counting "actions" in this way is completely arbitrary. In order to accurately count basic actions, you need to first come up with a list of basic actions, and then to compile your statement to a list of basic actions. This is exactly what compilers do – they compile your problem to assembly language or, in some cases, to bytecode.

Since you are not specifying your assembly language, it is truly impossible to say anything. It could be that there is one instruction that is equivalent to your if, or it could be that your assembly language is very weak, and your if requires 100 instructions. Even if you did specify your assembly language, it is still not clear how to compile the statement to assembly, since in general there is no canonical way to do so.

The way out is to realize that (under certain conditions) whatever assembly language is used, the statement would compile to a constant number of instructions, whose exact number depends on the assembly language. Therefore we can say that the number of instructions is $O(1)$, where the hidden constant depends on the assembly language and the compiler. In contrast, a loop summing an array would execute $\Theta(n)$ instructions. The difference between $O(1)$ and $\Theta(n)$ exists irrespective of the assembly language and compiler used.


Hints:

For $S_1 \cup S_2$, use the same idea in the proof that the natural numbers and the integers have the same cardinality. The proof goes by listing the integers in sequence:
$$ 0,1,-1,2,-2,3,-3,\ldots $$
You can think of $S_1$ as $0,1,2,3,\ldots$ and of $S_2$ as $-1,-2,-3,\ldots$.
For $S_1 \times S_2$, use the same idea in the proof that the natural numbers and the positive rationals have the same cardinality. The proof uses the "diagonal method", and consists of listing the rationals sorted by the maximum of the numerator and the denominator:
$$ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{2}{2}, \frac{1}{3}, \frac{2}{3}, \frac{3}{1}, \frac{3}{2}, \frac{3}{3}, \ldots $$
In this case $S_1=S_2$ are both $1,2,3,\ldots$.


One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a permutation according to the Mallows distribution, given a parameter $0 < \phi \leq 1$:

Start with the permutation 1.
Insert 2 into position 1 with probability $\frac{\phi-\phi^2}{1-\phi^2}$, and into position 2 with probability $\frac{1-\phi}{1-\phi^2}$.
Insert 3 into positions 1,2,3 with probabilities
$\frac{\phi^2-\phi^3}{1-\phi^3},\frac{\phi-\phi^2}{1-\phi^3},\frac{1-\phi}{1-\phi^3}$, respectively.
Insert $4,\ldots,n$ in an analogous manner.

When inserting $x$ into position $i$, what you do is shift positions $i,\ldots,x-1$ one step forward, and insert $x$ in the resulting empty spot.

The probability to obtain a permutation $\pi$ is proportional to $\phi$ raised to the number of inversions in $\pi$ (the Kendall $\tau$ distance between $\pi$ and the identity permutation).

Another popular model is the Plackett–Luce model from 1959. There are other models, for example Tallis–Dansie.


Complex search algorithm - Points on a sphere - Best approach

Let me start by suggesting a brute-force method, then suggest some ways to speed it up:

Pick a pair of (high-weight) points $P_0,P_1$ in the sector.  For each pair of points $Q_0,Q_1$ on the sphere, guess that maybe $P_0=Q_0$ and $P_1=Q_1$: align the sector (rotate & translate it) so that $P_0$ is on top of $Q_0$ and $P_1$ is on top of $Q_1$.  There is a unique way to do this.  Then check your candidate placement of the sector, by mapping the sector onto the globe and looking at all the other points in the sector to see how well they match the points on the sphere.  If you enumerate all pairs of points $Q_0,Q_1$ on the sphere, you're guaranteed to find the correct placement of the sector for at least one of them.  So, this algorithm works, at the cost of being slow: it takes $O(n^2)$ time, where $n$ is the number of points on the sphere.

You can dramatically speed this up in several ways.

First, you can filter by the distance $d(P_0,P_1)$ between the two points.  Instead of enumerating all points $Q_0,Q_1$, only enumerate pairs $Q_0,Q_1$ such that $d(Q_0,Q_1) \approx d(P_0,P_1)$.  How do you do that?  You enumerate all possibilities for $Q_0$, and for each such $Q_0$, enumerate all points $Q_1$ that are at distance approximately $d(P_0,P_1)$ from $Q_0$.  The latter can be done using a data structure for nearest neighbor search.  If you choose two points $P_0,P_1$ that are close to each other, probably there will be only a small number of points $Q_1$ at that distance from $Q_0$.  So, heuristically, the running time might become much closer to $O(n)$.

Second, you might be able to filter using the weights.  You could pick a pair of high-weight points $P_0,P_1$ in the sector, and only consider points $Q_0,Q_1$ whose weights are above some threshold.  You'd have to experiment how to choose that threshold.  Or, you could enumerate the points $Q_0$ in sorted order of the weight, highest weight first.

You can increase robustness to small errors in the location of the points in the sector by repeating the above multiple times for multiple different choices of $P_0,P_1$.


Why are forks in the Blockchain eventually resolved?

If we simplify and assume that each miner randomly guesses a hash (as opposed to being more systematic) and we discretize time, say into minutes, then each minute each miner is hoping to "roll" the right number. Let's say there are $N > 1$ possible values only one of which is correct at each minute. Then, in a world with only two miners, each minute there is only a $\frac{1}{N^2}$ chance that both miners will roll the correct value. There's a $1-\frac{3}{N^2}$ chance that neither miner rolls the correct value. There is a $\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2}$ chance that both miners roll the correct value after exactly $k$ steps of both not rolling the correct value. The probability that they will both roll the correct value for the first time at the same time is then $$\sum_{k=0}^\infty\left(1-\frac{3}{N^2}\right)^k\frac{1}{N^2} = \left(\frac{1}{1-\left(1-\frac{3}{N^2}\right)}\right)\frac{1}{N^2} = \frac{1}{3}$$

So the odds of them rolling the correct value at the same time $m$ times in a row is $\frac{1}{3^m}$. With more miners, birthday problem aspects enter, but that won't change the exponential nature. (In fact, I don't think the birthday problem really comes into play since each miner still needs to get the correct value not just a value that matches another miner's.)

I'm pretty sure this is the idea the author had in mind. As you say, though, a malicious miner (a selfish miner) can withhold announcing blocks until they notice someone else announcing them. To account for that, you could instead consider (in the two miner world again) what the probability is that the malicious miner finds a block before the honest miner. If the miners are comparable, then that's presumably something like $\frac{1}{2}$. However, things are further complicated by the fact that when the malicious miner does find the correct value first, then that miner also gets a head start on finding the correct value for the next block. Nevertheless, for comparable miners, there is still a good chance that the honest miner will find a block first despite the malicious miner's head start. This reasoning starts to get into the selfish mining aspect I referenced in the comments.


Is there a way to check if a path in a graph is infinite?

You will not find an algorithm to do what you want. As you indirectly suggest, an algorithm can only check a finite prefix of any path.  You can't even use the process of elimination as there may be multiple infinite paths. (If there was only one, you could eventually rule out all the other finite paths.)

As you are probably aware, this is (a corollary of) König's lemma.  What you are asking for is essentially a constructive proof of it which doesn't exist.  The typical (classical) proof repeatedly uses double negation elimination in the form: if no child has an infinite (simple) path then the subtree has a finite number of vertices, this is a contradiction thus there must be some vertex that has an infinite number of descendants. There is not, in general, a computable function to pick out this vertex though.  Knowing that it must "exist" doesn't mean we have any way of calculating it.


Reducing linear programming to positive linear programming

You can add a variable $y$ and a linear equality $y=c^Tx+c_0$ for some $c_0$. Then, the original problem is equivalent to maximizing $y$ in the new system.

Except for the condition $y\geq 0$. That is where $c_0$ comes in. We need to make $c_0$ large enough that for some feasible $x$ (that is $Ax=b$ and $x\geq 0$ hold) we have $c^Tx+c_0\geq 0$. In that case it does not matter that non-negativity cuts away parts of the feasible space. The optimal value is still the same.

So how to choose $c_0$? I am not an expert in linear optimization. Is finding some feasible $x_0$ easier than finding one that maximizes the objective function? If so, we can take $c_0$ to be $-c^Tx_0$.

If the given coefficients are rationals, there is another way.
First, let us establish that the polytope of feasible $x$ has vertices (unless it is empty):
Let $p$ be a point in a minimum-dimensional boundary cell of said polytope.
For contradiction, assume that the dimension of this cell is $\geq 1$.
Then, there is a different point $q$ in the same cell. As the cell has minimum dimension, it is unbounded, so points of the form $r=p+t(q-p)$ are in the same cell and thus in the polytope. As $q-p\not=0$, some such $r$ have negative coordinates, contradicting the polytope condition $r\geq 0$.

Now, make all coefficients of $A$ and $b$ integer by multiplying with the common denominator. Let $n$ be the dimension (the length of the vector $c$) and let $M$ be the maximum absolute value of any coefficient of $A$, $b$, or $c$. Then we can bound the coordinates of any vertex of the feasible polytope by $n!\cdot M^n$. Thus, choose $c_0:=n\cdot n!\cdot M^{n+1}$.

[EDIT]

Yet another approach, in case you are willing to call the oracle multiple times: First, try the above with $c_0=0$. If you get a solution or the answer "unbounded", you are fine. If the answer is "unsolvable", you need to find out if there are solutions with negative objective function. Hence, set $z=-c^T$ and maximize $z$ instead. If you get a solution, you can use it as $x_0$. If you get "unsolvable" again, you are done as well. The last case is the answer "unbounded". Then, you need to try out ever larger $c_0$ (for few oracle calls, use a fast-growing function; the Ackermann function may do) until you get a solution.


Dijkstra algorithm step in Introduction to Algorithms

$u$ is supposed to be the first node to be insert in $V$ such that $d(s, u) \neq \delta(s, u)$. Before the insertion, $u$ is in $S-V$, it's clear. In addition, $y$ is supposed to be the first node in a choosen optimal path $s -> u$ to belong to $S - V$ when picking $u$ from $S - V$. So before we insert $u$ in $V$, $u$ and $y$ are both in $S - V$. Note that $y$ can be equal to $u$.


Is there a standard (common) notation for the following operation on binary strings?

There are pattern languages [1].

A pattern is a string over a terminal alphabet $\Sigma$ and an (infinite) variable alphabet $V = \{x_i \mid i \in \mathbb{N} \}$. Let $p = \alpha_1 x_{i_1} \alpha_2 \dots x_{i_k} \alpha_{k_1}$ be a pattern with $\alpha_i \in \Sigma^*$ for $i \in [1..k+1]$ and $x_j \in V^*$ for $j \in \{i_1, \dots, i_k\}$; its language is defined as

$\qquad\displaystyle L(p) = \{ \alpha_1 \beta_{i_1} \alpha_2 \dots \beta_{i_k} \alpha_{k+1} \mid \beta_{i_1}, \dots, \beta_{i_k} \in \Sigma^* \}$.

Note that the $i_j$ need not be pairwise distinct in general -- that is $L(x_1x_1) = \{ww \mid w \in \Sigma^*\}$ -- but one can make that restriction.

This is stronger than what you need; you want to restrict the language of possible replacements to individual symbols, and you want the variables to be independent (i.e. the $i_j$ to be pairwise distinct). It is easy to adapt the definition:

A bit-pattern is a string over a terminal alphabet $\Sigma$ and a wildcard $\star$. Let $p = \alpha_1 \star \alpha_2 \dots \star \alpha_{k_1}$ be a pattern with $\alpha_i \in \Sigma^*$ for $i \in [1..k+1]$; its language is defined as

$\qquad\displaystyle L(p) = \{ \alpha_1 x_1 \alpha_2 \dots x_k \alpha_{k+1} \mid x_1, \dots, x_k \in \Sigma \}$.

This is so straight-forward and the concept of wildcards is so wide-spread that, actually, I don't think you even need a reference; just define whatever you need. If you do find a reference it does not hurt to cite it, of course.

Polynomial time inference of extended regular pattern languages by T. Shinohara (1982)


Induction rules for reflexive, transitive closure

Here's a fully formal articulation in the language of Agda.
First, inductive rules correspond to indexed families.

data Star {A : Set}(R : A → A → Set) : A → A → Set where
    Refl : {a : A} → Star R a a
    Trans : {a b c : A} → Star R a b → R b c → Star R a c

Here the Refl data constructor corresponds to your first rule, and the Trans data constructor corresponds to your second rule. R represents $\to$, so Star R corresponds to $\to^*$. The induction rule corresponds to the eliminator for the data type, i.e. roughly the fold on that type (though things are a bit more complicated in a dependently typed language).

ind : {A : Set}{R : A → A → Set}{P : A → A → Set}
    → ({a : A} → P a a) → ({a b c : A} → P a b → R b c → P a c)
    → {a b : A} → Star R a b → P a b
ind r t Refl = r
ind r t (Trans s x) = t (ind r t s) x

This says that if you give me some binary relation $P$ and you show that $\forall a \in A. P(a,a)$ holds and $\forall a,b,c\in A. P(a,b)\land R(b,c) \Rightarrow P(a,c)$ (i.e. when $P(a,b)$ and $R(b,c)$ hold, then $P(a,c)$ holds) then I can provide you a proof of $P(a,c)$ whenever $R^*(a,c)$ holds, where $R^*$ is the reflexive, transitive closure of $R$.

Question 2 is completely trivial. The formal proof of the statement is Refl. Question 3 is not much harder.  It's asking to show that if $a \to^* b$ and $b \to^* c$ then $a \to^* c$, while the inductive rule only gives the case when $b \to c$ in a single step. Obviously, we just need to recursively apply the single-step rule. This leads to the following code:

trans : {A : Set}{R : A → A → Set}{a b c : A} → Star R a b → Star R b c → Star R a c
trans r Refl = r
trans r (Trans s x) = Trans (trans r s) x

For your purposes, you should probably define the equivalent of trans in terms of the induction rule, i.e. in terms of ind. I'll leave that as a very simple exercise.


Representing non-contiguous memory regions as a standard vector with O(1) access

A simple approach is to have a one-level lookup table that maps each block of the array to where it is stored.  In other words, for a logical array $A[0\dots n-1]$ containing $n$ bytes, we have a lookup table $T[0\dots \frac{n}{128}-1]$ containing $n/128$ pointers; the bytes $A[128k \dots 128k+127]$ are stored at the physical address $T[k]$.  To look up $A[i]$, we compute $p = T[i \gg 7]$ (where $\gg$ indicates logical right shift), then read the byte at address $p + (i \bmod 128)$.

This does require a single contiguous region large enough to store $n/128$ pointers (e.g., holding $n/32$ or $n/16$ bytes, depending on whether you're on a 32-bit or 64-bit system).  Given that, array operations become fast: you basically have one extra table lookup and indirection.

If you can't even have any contiguous region, not even a smaller one for storing the lookup table, but have to build everything out of 128-byte chunks that can be at arbitrarily-inconvenient locations with arbitrarily-bad fragmentation, then I don't think it's possible to do any better than your solution.

Rather than looking for a better data structure to handle this kind of arbitrarily-bad fragmentation, a cleaner solution is probably to design your memory management system to avoid creating worst-case memory fragmentation in the first place.  One architecture that can help deal with this is a buddy allocator.  The entire memory address space can be divided into 128-bit chunks, but we then impose a binary tree structure on it: the 128-byte chunk at address $256k$ is the sibling/buddy of the 128-byte chunk at address $256k+128$.  Those two chunks, if they're both available, can be coalesced into a (fused) 256-byte chunk.  Each 256-byte chunk has a buddy, and if they're both available, they too can be merged to obtain a 512-byte chunk.  And so on.  This allows you flexibility to deal with small 128-byte chunks when you need them, but also provides a way to build up larger chunks of contiguous memory and try to avoid arbitrarily-bad fragmentation.


Protecting data unequally using Error Correction Codes

Since error correction here is essentially discrete, it might not be easy to come up with an optimal transient encoding, however you can approximate this by applying different encoding schemes for different parts of your data. In your temperature digits example, you might consider an encoding with $d=5$ Hamming distance for integer part and $d=3$ for fractional part, which will eventually provide a two-bit correction for the integer part and one-bit correction for the fractional part. This partitioning can be varied.


Why don't we emphasize "length of input string" when considering time complexity of sorting algorithms?

First, note that the input length of a Knapsack instance is $\Theta(n \cdot \log \max \{c,w_1,\dots,w_n\})$. Assuming the instance is "pruned", namely that all weights are at most $c$, this is $\Theta(n\log c)$.

In order to answer such questions, you need to fix

the machine model,
the cost model,
the set of valid inputs and
the algorithm.

You don't give the first three.

So your question is not well defined. In order store this particular set of numbers on a Turing machine tape, six symbols are indeed sufficient (one per number), and then the algorithm would run in time $O(1)$ on its only input. In order to get a general algorithm, however, you need to "properly" encode the numbers, namely B is the correct answer. I'll assume the latter.

Insertion sort has worst-case complexity $\Theta(n^2)$ in the RAM model with uniform cost model (elementary operations on naturals cost $1$), $n$ being the number of elements. In particular, it is independent of the size of the numbers. Since $n \leq |i|$, $i$ the input, you get an $O(|i|^2)$ time algorithm.

If you apply the logarithmic cost model (elementar operations on naturals have cost depending on their encoding length, cf. elementary school), you get time $\Theta(n^2 \cdot \log E)$ with $E = \log \max\{e_1, \dots, e_n\}$ the length of the largest input number, because the $\Theta(n^2)$ comparisons on the elements dominate the runtime. With similar reasoning as above, we note that the algorithm has runtime $O(|i|^2)$.

So as you can see, the qualitative result does not change when considering the input length for this kind of algorithms, so it is often glossed over. When analysing e.g. radix sort this is no longer valid, and you have to look more closely.


What are the general applications of Computer Science in the field of Psychology?

Here are some of the areas that intuitively come into my mind where Computer Science and Psychology can go along together. As a student of Computer Science, one has to study the following core subjects at the undergrad level that are either directly or indirectly related to Psychology:

1. Data Structures and Algorithms: All the data structures do exist in the real world and the human mind perceives them to store, arrange, sort and search the required data as per their strength and limitation. Now the question arises, could there be a data structure or algorithm that is beyond the perception and capacity of human mind? Perhaps certainly or maybe.

2. Design and Analysis of Algorithms: Could there be a general algorithm for curing a mental disease, achieving happiness, finding love or the best match, finding career, overcome stress or depression, defeating a rival, rehabilitating a heroine addict or leading a "perfect life"? All of such aspects of human life can be addressed computationally. And yes the answers to these questions are indeed subjective and debatable as well.

3. Artificial Intelligence: Can we ever have machines more intelligent than humans? Oh yes, we certainly have such intelligent machines. But do such machines recognize vision and pattern as we humans do? That is an area of continuous research in Computer Science.

4. Human Computer Interaction: In the modern world, humans do interact with computers almost on a daily basis. Commercial hardware, software applications and games, all of them are designed with the "interface" keeping in view the human user's perception, expectation and limitation in consideration. Now the question arises: Can we have Computers as our personal psychiatrists? Can we treat mental or psychological patients with Computer-Aided Psychotherapy? I really want to explore!!!!

5. Professional/Ethical Issues in Computing: Can we ever be able to fully secure personal or professional data via Computers? Can we get rid of pornography from the internet? Can we develop a game that counters games leading to suicide like "Blue Whale"? Can we rid the world from religious fanaticism, terrorism, racism and hate crimes via Computer Science?  All of such questions and problem areas are pending to be addressed.


Your second $\beta$ reduction is wrong.
After the first reduction, you (should) have $(\lambda x.x (U U x)) g$, so after the second you have $g (U U g)$ as required, but you haven't substituted the second $x$ correctly, leaving both it and the $g$ that the function is applied to, giving you $g (U U x) g$, though you have substituted the first $x$ correctly.


Worst case running time to search for an element in a balanced BST with $n2^n$ elements

You state that searching an element in a BST takes time $\log n$, but this is wrong on two counts. First, this is (roughly) the worst-case number of comparisons. Second, the running time itself isn't exactly $n$ but is roughly $C\log n$ for some constant $C$ that depends on the exact machine model (assuming that comparisons take constant time). For this reason, it is better to use $\Theta$ notation (look it up!) and state that the worst-case running time of element lookup in a BST is $\Theta(\log n)$, where $n$ is the number of elements in the BST.

In our case, the number of elements is $n2^n$, and so the running time is $\Theta(\log(n2^n)) = \Theta(\log n + n) = \Theta(n)$. Asymptotically, $n + \log n = \Theta(n)$, and so there is no need to explicitly mention $\log n$.


When the indexes of the for loops depend on each other you can think like this:

When the index of the outer for loop takes its first value how many times is the inner for repeated? What about when the index of the outer for takes its second value? ... What happens when the index of the outer for takes its last value?

In your case:
When $j = n-1$, $i$ is repeated $n-1$ times.
When $j = n-2$, $i$ is repeated $n-2$ times.
...
When $j = 1$, $i$ is repeated $1$ time.

In total, the inner for loop is executed $(n-1) + (n-2) + ... + 2 + 1 = \dfrac{n}{2} * n = n^2$ times. Therefore the complexity is $O(n^2)$.

The best case is obviously when the matrix is already sorted.


The asymptotic runtime ignores access times for the digits.  On typical hardware a base 256 number can be manipulated faster than extracting base 10 digits from the same number.

If you have multiple CPUs, you can more easily exploit parallel processing by using a larger base.  The large base will spread the numbers across many buckets which can then be sorted in parallel.

Another reason to change bases is if you know your data has a bias (such as Benford's Law) that would cause the numbers to initially cluster into only a few buckets.


Data normalization when control has multiple values in CS/CE

One simple approach is to use the median.  It is less sensitive to outliers than the mean, but still serves as a good summary of typical running time.  Alternatively, you could use the mean but in that case you should inspect all the results yourself to check for the possibility of outliers.  I personally would recommend the median.

Papers often show confidence intervals as well, so that you can assess the effect of statistical noise.

Normally, benchmarks are run on an isolated system to minimize interference from other tasks.

Note that there are many challenges with benchmarking.  Even simple irrelevant changes can cause significant changes to performance, e.g., because they happened to change cache alignment to something that is randomly better or worse.  Therefore, it can be difficult to separate out whether your optimization led to a 3% performance improvement because your optimization is an improvement, or if that's just randomness (e.g., just recompiling with slightly different settings can change the running time by +/- 3%, and you happened to get unlucky once and lucky the other time).


Please help me understand this proof of the undecidability of "Do two halting Turing machines accept the same language?"

Let $\langle M, w\rangle$ be the input to the halting problem.
We will construct $M'$ that simulates $M$ as you described with $w$ as the predefined input.
As you have said, $L(M')\neq \emptyset\iff M \text{ halts}$. However, we simulated $M$ on $w$, hence $L(M')\neq \emptyset \iff M \text{ halts on } w \iff \langle M, w\rangle\in H_{TM}$ where $H_{TM}$ is the halting problem.
Define the function $f$ that given $\langle M, w\rangle$ will output $\langle M', M_{empty}\rangle$, where $M_{empty}$ is a TM that immediately rejects.
We will have: $\langle M, w\rangle \notin H_{TM} \iff L(M')= \emptyset \iff L(M')\neq L(M_{empty})\iff \langle M', M_{empty}\rangle\in EQ_{TM}$
$f$ is computable, and hence it is a reduction from $\overline H_{TM}$ to $EQ_{TM}$.
$\overline H_{TM}$ is not decidable, and thus also $EQ_{TM}$ isn't decidable


Analog computers and the Church-Turing thesis

First of all, the authors seem to be confusing two different thesis: the Church–Turing thesis and the Cook–Karp thesis. The first concerns what is computable, and the second concerns what is computable efficiently.

According to the Cook–Karp thesis, all reasonable "strong" computational models are polynomially equivalent, in the sense that they all polynomially simulate each other. Equivalently, every reasonable computational model can be polynomially simulated by a Turing machine. Quantum computers are a counterexample to this thesis, since they appear to be exponentially more efficient than classical computers. However, they are not a counterexample to the Church–Turing thesis, that is, using quantum computers you can't compute anything that you can't already compute with a Turing machine. We can also formulate an updated Cook–Karp thesis, stating that all physically realizable computational models are polynomially simulated by quantum computers.

Several physical models of computations have been proposed as challenging these theses, but under scrutiny, they all seem to not violate the Church–Turing thesis, or not to be more powerful than quantum computation. Scott Aaronson proposes to consider this situation as a "law of nature". However, as far as I know there are no theoretical arguments supporting these theses other than the inductive argument that all models which have been proposed have been shown to conform to them.


How "meaningful" is Turing test? Are there better measures?

Nowadays intelligence of computer programs could be measured by e.g. quantities of statements that they can evaluate.

So, the trick, is that the Turing Test was meant for an evaluation of strong AI: could there be a computer program that was as intelligent as a human? So evaluating statements isn't enough, since humans can do much more than that.

There are some things to keep in mind. First, while some people use the Turing Test as a metric of the quality of chatbots today, that wasn't necessarily its original intent. It was more of a thought experiment, trying to answer the question of "what does it mean for an AI to be intelligent?"

Secondly, the test wasn't mean to strictly evaluate the "question and answer" ability of an AI. It was more saying, "if there's an AI so good we can't distinguish it from a human, is there any meaningful difference?" It was a way to define sentience without bringing in complex philosophical (or possibly even religious) arguments about what is and isn't alive. The Turing Test says "if it looks sentient, we'll say it is, because there's no meaningful way to tell otherwise".

  That is, no-one can ever in practice develop a computer program that's that good. It would just be too large.

There are many possible ways around this. One is that we might not write every aspect of a program, but evolve one. We could write a program that writes a program that writes a program etc, each one being slightly more intelligent until it converges on something powerful.

Or, an AI could be developed from machine learning. With enough time and data, something close to human intelligence could grow from statistical observations, having the headstart of hand-coded AI at its core.

If a human brain is enough for human intelligence, a comparably complex program should be as well. But even if no such program is ever developed, the Turing Test still holds meaning as a thought experiment.


How to estimate the computational cost in a neural network?

It takes $O(n)$ time, where $n$ is the size of the neural network (e.g., number of nodes plus number of connections; in a graph model, number of vertices plus number of edges).


There's a small chance you might be able to get a speed-up by using properties of arithmetic modulo $n^2$, depending on how $g$ was chosen.

Suppose $g=a(1+bn)$.  Then note that, by the binomial theorem,

$$g^x = a^x (1+bn)^x = a^x \sum_i {x \choose i} (bn)^i  = a^x (1 + bx n + n^2 \times \text{stuff})$$

so we see that

$$g^x = a^x (1 + bx n) \pmod{n^2}$$

Thus if you can compute $a^x \bmod n^2$ efficiently, you can compute $g^x \bmod n^2$ with just a tiny bit more work.  Here you want to take $x=mn$.  The simplification is that now $g$ can always be expressed in the form $g=a(1+bn)$ where $0 \le a < n$.

What can we say about $a$?  Well, for one thing we know that $g^{kn}=1 \pmod{n^2}$, so it follows that $a^{kn}=1 \pmod{n^2}$.  Thus, the order of $a$ modulo $n^2$ has to be a divisor of $kn$.

If the order of $a$ is exactly $kn$, we haven't gotten anywhere.

But if the order of $a$ is a strict divisor of $kn$, we can get some speedup.  We first reduce $mn$ modulo the order of $a$, then compute $a^{mn} \bmod n^2$, and finally use the relationship above to get the value of $g^{mn} \bmod n^2$.  (For instance, if you get lucky, it is possible that the order of $a$ might be $k$, and then you'll get a non-trivial speedup.)

Whether this yields a speedup in practice will depend on the value of $g$ and how $g$ was chosen; since that wasn't specified in your question, it's not possible to evaluate whether this is likely to help in practice, but it might.


How can I compute the time complexity of this image processing algorithm?

We need to estimate how many times block operation is performed.

First lets answer in how many rows we will start block processing - easy to see that each $S$ row are taken into account, so answer to this sub-question is $O(N/S)$. If we suppose that $N$ - number fo rows and $M$ number of columns.
Then we need answer to question - how many times we will run block processing for each row, due to we perform processing of blocks that starts only in each $S$ columns - answer for this sub-question will be $O(M/S)$.

Now we have that block processing will be performe $O(N*M/S^2)$ times for whole input. And result time-complexity for whole algorithm will be $O(N*M*B^2/S^2)$.


Multiple Source Shortest Paths in a weighted graph

Yes.  Here is the trick that always works: create a new source, $s_0$, and add an edge (with length 0) from $s_0$ to each of your starting vertices.  Then, run any shortest-paths algorithm starting from $s_0$ to compute the distance from $s_0$ to each other vertex.

Your technique for BFS is equivalent to this; but this is more general and can be used with Dijkstra's algorithm, Bellman-Ford, or any other shortest paths algorithm.


This answer assumes the following interpretation of your question:

  What is the complexity of the following problem? Decide whether a given CSP is satisfiable, where at most half of the assignments satisfy each constraint.

It is likely that this problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete. In fact, if we bound the width of the constraints (how many variables appear in them), then Schaefer's dichotomy theorem implies that the problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete, giving a criterion to decide which of these possibilities holds.

In your case, it seems likely that the problem is $\mathsf{NP}$-complete already for width 3. You can verify (or refute) this using the criterion in Schaefer's theorem, which can be found in the Wikipedia article linked to above.


Why do the definitions of non-deterministic Turing machines look strange?

Basically, a NDTM on input $x$ may have more than one computation branches. If at least one of these branches accepts the input then we say the NDTM accepts the input $x$, otherwise it rejects.

You can consider a NDTM as a finite number computation branches such that branch on input$x$ may halt with accept or reject, or run forever. If at least one branch halts with accept then the NDTM accepts that input no matter other branches halts or run forever. If no branch accepts (halts with in ACCEPT state) then we say the NDTM does not accept the input. And if every branch halts and rejects then we say that NDTM rejects the input.

Do not try look for a real life model of a NDTM. It is just a conceptual computation model which allows to define a complexity class known as $\mathrm{\mathbf{NP}}$ class.

This post has more.


A modern processor will first check whether it knows the value of the condition or not. For example, if you had a C statement "if (x / y > 3) ... " then it will take quite a while until the value of the ">" condition is known. If the condition is known, then the processor knows what to do.
If the condition is not (yet) known, then things get complicated. You don't want to wait until the condition is known. The processor will therefore use branch prediction to decide whether the branch is likely to be taken or not. For example, if this branch has been performed five times before, and each time the condition was true, then the processor will guess that the condition will be true again.
However, the guess might be wrong. Therefore all the following instruction are marked as "guessed", so the processor can undo the actions of each instruction. At the same time, the processor watches the condition: In the example, once the division x/y is complete, and the comparison x/y > 3 is complete and the condition is known, the processor will know whether the guess about the condition was right or wrong. If it was wrong, then the processor undoes all the effects of instructions that were performed but shouldn't have been. If the guess was right then the processor marks all the instructions back to "not guessed". One thing that cannot be undone is storing results to memory, so while the condition was guessed, nothing has been stored to memory. All those store instructions are now started.


Left recursion and left factoring -- which one goes first?

Transformations such as left factoring or removing left recursion do not have precedence rules. Obviously, the resulting grammars may be different but they will recognize the same language.

The question's example grammar is more difficult than the typical undergrad homework problem. So showing our work will be useful.

Left Recursion

Let's define a transformation that removes left recursion.

Given

$\qquad \displaystyle A \to A\alpha_0 \mid A \alpha_1 \mid \dots \mid A \alpha_n \mid B \beta_0 \mid B \beta_1 \mid \dots \mid B\beta_n$,

we remove left recursion like this:

$\qquad \displaystyle \begin{align}
    A_h &\to B \beta_0 \mid B \beta_1 \mid \dots \mid B \beta_n \\
    A_t &\to \alpha_0 \mid \alpha_1 \mid \dots \mid \alpha_n \\
    A_{t^+} &\to A_t A_{t^+} \mid A_t \\
    A &\to A_h A_{t^+} \mid A_h
\end{align}$

The generality of above is typically not given in compiler texts, but parsing texts like Grune & Jacobs do cover this. Left factoring can be applied to the above transformed grammar but will be just introduce extra rules that will not change the answer. So we will simplify the presentation without extra left factoring being performed.

In this answer we will not cover indirect left recursion issues because we are only concerned with a single non-terminal's rules. Note that indirect left recursion can be dealt with, though. (Open a separate question if that is important.)

Left Factoring

Removing left factoring is in most introductory compiler texts done like this. Given

$\qquad \displaystyle A \to x y \mid x z$

left factoring yields:

$\qquad \displaystyle \begin{align}
 A_s &\to y \mid z \\
 A &\to x A_s
\end{align}$

Now that's perform the transformations in both ordering.

Left factoring first

Let's left factor the question's grammar

$\qquad \displaystyle \begin{align}
    F_s &\to D S \mid \varepsilon \\
    F &\to F B a \mid c F_s
\end{align}$

and then remove the left recursion:

$\qquad \displaystyle \begin{align}
    F_h &\to c F_s \\
    F_t &\to B a \\
    F_{t^+} &\to F_t F_{t^+} | F_t \\
    F_s &\to D S \mid \varepsilon \\
    F &\to F_h F_{t^+} \mid F_h
\end{align}$

Removing left-recursion first

And for the other ordering, let's remove left recursion from the question's grammar

$\qquad \displaystyle \begin{align}
    F_h &\to c D S \mid c \\
    F_t &\to B a \\
    F_{t^+} &\to F_t F_{t^+} \mid F_t \\
    F &\to F_h F_{t^+} \mid F_h
\end{align}$

and then left factor the terminal $c$:

$\qquad \displaystyle \begin{align}
    F_{hs} &\to D S \mid \varepsilon \\
    F_h &\to c F_{hs} \\
    F_t &\to B a \\
    F_{t^+} &\to F_t F_{t^+} \mid F_t \\
    F &\to F_h F_{t^+} \mid F_h
\end{align}$

Aha, the resulting grammars are the same!

In general, proving that two grammars are equivalent is undecidable. So if a series grammar transformations could influence the language that is recognized then, it would be disastrous.


Suppose you want exactly $3/4$ of the bits to be 1. If the encoded vector is of length $m$, it can be identified as a subset of $\{1,\ldots,m\}$ of size $(3/4)m$, of which there are $\binom{m}{(3/4)m}$. If $\binom{m}{(3/4)m} \geq 2^n$ then you can encode every $n$-bit string as such a subset using the technique of binomial encoding. Since $\binom{m}{(3/4)m} \approx 2^{mh(3/4)}$, this works as long as $m \gtrsim n/h(3/4) \approx 1.23n$.

Binomial encoding relies on Pascal's identity
$$ \binom{a}{b} = \binom{a-1}{b-1} + \binom{a-1}{b}. $$
To encode a number $x$ in the range $[0,\binom{a}{b})$, we act as follows:

If $x < \binom{a-1}{b-1}$ then we recursively encode $x$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b-1$, and output $S \cup \{a\}$.
If $x \geq \binom{a-1}{b-1}$ then we recursively encode $x - \binom{a-1}{b-1}$ as a subset $S$ of $\{1,\ldots,a-1\}$ of size $b$, and output $S$.

The procedure can easily be reversed (exercise).


Is my theorem about $P \neq NP$ correct?

I don't think the theorem is correct.  At least, your proof is not correct.  The problem is in the second sentences of your proof:

  Since the problem is NP-complete, any NP problem can be reduced to it in $O(N^r)$ steps, for some $r$.

This statement is not correct.  There's no guarantee there is a single $r$ that works for every NP problem.  You might have a different value of $r$ for each NP problem, with no upper bound on the set of all $r$.  (To give a silly example: Maybe for 3SAT $r=3$, for 4SAT $r=4$, for 5SAT $r=5$, and so on.  Don't take this example too seriously; it's just to give you the idea.)


Is a secondary TM sufficient to detect all loops?

This is Floyd's cycle finding algorithm, which is an efficient procedure for finding cycles. If you don't care about efficiency, you can use a big table which stores the different states the Turing machine has reached. If it reaches the same state twice, then it's in an infinite loop. What you are describing is just a more efficient way of detecting the same event, which is a particular type of infinite loop.

Turing machines can fail to halt – enter an infinite loop – in other ways. For example, a machine can keep going to the right indefinitely. The machine never halts, yet it doesn't reach the same state twice. A cycle finding algorithm won't detect this situation. Of course, there is no general way of detecting infinite loops, since the halting problem is undecidable.


Is there a way to get O(1) without extra space in the union find algorithm?

Sure, you can make Find run in $O(1)$ time if you allow Union to run in $O(n)$ time.

Suppose the elements are numbered $0,1,\dots,n-1$.  We'll maintain an array $A[0..n-1]$, where $A[i]$ is the set that contains element $i$.  Then a Find operation takes $O(1)$ time, since it consists solely of looking up in the array.  A Union operation can be done in $O(n)$ time by scanning through $A$ to find all elements of both sets and updating the array so that they're both contained in the same set.  Notice that this doesn't use any additional space.

You can replace the array with a hashtable if you prefer, and that will allow items to be identified by arbitrary identifiers (instead of integers $0..n-1$).

This probably isn't useful in practice unless Union operations are extremely rare, because the Union operation becomes so expensive.  In most situations it will probably be preferable to use a standard Union-Find data structure or extra space.


For every non-trivial language $A$ and every finite strict subset $B \subsetneq A$, it's holds that $A \le_m A \setminus B$

As mentioned in the above comment, the format of your reduction is not correct, so you have to take care of that first, and think about it again. Also, the hint I gave in the question that you linked should be enough. Anyway, here is another hint.
Hint: consider the identity reduction that maps every word $x$ to itself, and try to understand why it does not work. Then, think what is the simplest thing you can do in order to fix the identity reduction.


Examples of sets $A$ and $B$ such that $A \leq_m B$ but not $B \leq_m A$

Let $A$ be a computable set of all even nonnegative integers, and $H$ be the language of the Halting problem. Assume also that $w_1 \in H$ and $w_2 \notin H$. Then define a mapping as following:

$$f(x) = w_1 \text{ if } x \text{ is even}, w_2 \text{ if } x \text{ is odd } $$
This function is clearly computable and $x$ is even iff $f(x) = w_1 \in H$, i.e., $A \leq_m H$. However, $H \nleq_m A$, otherwise $H$ would be computable/recursive.


Define a sequence $n_0 = n$, $n_{t+1} = n_t/\log n_t$. Assuming that the underlying constant in $\Theta(n)$ is $1$, we get
$$
\begin{align*}
T(n) &= \log n_0 T(\tfrac{n_0}{\log n_0}) + n_0 \\ &=
\log n_0 \log n_1 T(\tfrac{n_1}{\log n_1}) + n_0 + n_1 \log n_0 \\ &=
\log n_0 \log n_1 \log n_2 T(\tfrac{n_2}{\log n_2}) + n_0 + n_1 \log n_0 + n_2 \log n_1 \log n_0 \\ &= \cdots
\end{align*}
$$
Now $n_{t+1} \log n_t = n_t$, and so $n_1\log n_0 = n_0$, $n_2\log n_1\log n_0 = n_1\log n_0 = n_0$, and so on.

Suppose now that the starting condition of your recurrence is $T(x) = 1$ for $x \leq 1$, and let $\ell+1$ be the minimal index such that $n_{\ell+1} \leq 1$. Then
$$ T(n) = \log n_0 \log n_1 \cdots \log n_\ell + (\ell + 1) n. $$
In fact, $\log n_0\cdots n_\ell n_{\ell+1} = n$, and clearly $n_{\ell+1} = \Omega(1)$, showing that $T(n) = (\ell + O(1))n$.

It remains to estimate $\ell$. Clearly $n_t \geq n/\log^t n$, and so $\ell \geq \log n/\log\log n$. For the other direction, notice that when $t \leq \log n/2\log\log n$, we have $n_t \geq \sqrt{n}$, and so $n_t \leq n/(\log n/2)^t$. This shows that $n_{\log n/2\log\log n} \leq \sqrt{n} 2^{\log n/2\log\log n} \leq n^{0.51}$ for $n$ larger than some constant $C$. Repeating the same argument, $n_{\log n/2\log\log n + \log n^{0.51}/2\log\log n^{0.51}} \leq n^{0.51^2}$ for $n^{0.51} \geq C$. Notice that $\log n^{0.51}/2\log\log n^{0.51} \leq 0.52\log n/2\log\log n$, for $n$ larger than some constant $C'$. Repeating this argument $k = O(\log\log n)$ times, we get that for $t = \log n/(2\log\log n) (1 + 0.52 + 0.52^2 + \dots) = O(\log n/\log\log n)$ we have $n_t = n^{0.51^k} = O(1)$. This shows that $\ell = \Theta(\log n/\log \log n)$, and so
$$ T(n) = \Theta(n\tfrac{\log n}{\log\log n}). $$


Why do register machines outperform stack machines?

I think the prime reason why register machines are better at performance because registers are within the CPU chip itself, however stack is generally the part of main memory, accessing register is on average 1-3 clock cycles, level 1 cache requires nearly 10-20 cycles on average, and depending on the design it could have level 2 shared cache which takes about 40 cycles on average, finally main memory takes 100s of cycles in comparison per initial word access then once you access it, the further block containing the required word is only incrementally cycle consuming. Hence register based architecture should always out perform stack based.

The data presented is definitely not according to today's state of the art processors take it from more of a conceptual stand point rather than practical one, and that I believe was the intent of the question.


What does "Outstanding" mean in the context of architecture?

Outstanding means, it hasn't been resolved. In the case of cache misses, that means the data request has not been serviced yet. When a cache miss happens, it has to fetch the data from the next level cache/memory, until this data arrives, you need to hold this request somewhere. You've got two options in this situation. Either block the entire cache, until data from the next level arrives. This is the easiest to implement, but quite bad in terms of performance. On the other hand, you could save the information about this data request somewhere, and carry on servicing others. This is is much better in terms of performance. Now, coming to this "place" where you are going to store information about the pending cache miss, this is a hardware structure. So you can only have finite number of "outstanding" misses. Number of entries in this buffer, is what is being provided as the number of outstanding cache misses.


Generating uniformly random bits from a stream of arbitrarily biased bits

We can simulate an unbiased coin as follows. Toss a pair of coins, and repeat until they produce different outcomes. If the outcome was H,T (heads followed by tails) output heads, and if it was T,H output tails.

Conditioning on the event that the above simulation halts (i.e. at some iteration $i$ we receive different outcomes), then both H/T have equal probability. The probability of a "bad output" in a single iteration (same result from both coins) is $p^2+(1-p)^2$, which is less than $1$ for $p\in (0,1)$. Thus, the probability of "failure" after $n$ iterations is bounded by $(1-2p(1-p))^{-n}$.


How do you check if two algorithms return the same result for any input?

In contrast to what the nay-sayers say, there are many effective techniques for doing this.

Bisimulation is one approach. See for example, Gordon's paper on Coinduction and Functional Programming.
Another approach is to use operational theories of program equivalence, such as the work of Pitts.
A third approach is to verify that both programs satisfy the same functional specification. There are thousands of papers on this approach.
A fourth approach is to show that one program can be rewritten into the other using sound program transformations.

Of course none of these methods is complete due undecidability, but volumes and volumes of work has been produced to address the problem.


Generating number of possibilites of popping two stacks to two other stacks

(answer for another problem, see the edit below)

First, generate all subsets $A_1$ of $A$. $A_1$ will go in $C$ and $A_2=A\backslash A_1$ in $D$. Likewise, generate all subsets $B_1$ of $B$. You then have to generate all possible ordered combinations of $A_1$ and $B_1$ for $C$ and the same for $A_2$ and $B_2$ in $D$.

This amounts to enumerate, given $(a_1,…,a_n)$ and $(b_1,…,b_m)$ all interleavings of length $n+m$ which can be viewed as an exploration of the intersections of a grid of size $n×m$. (There are $\frac{(n+m)!}{n!m!}$ paths)

This is a way of generating all possible $C$s and $D$s uniquely.

But maybe I misunderstood the question. Is this what you want? To help comparing with what you already have tried, here is the number of pairs of stacks it generates (where $A$ is the size of $A$):

$$N(A,B)=\sum_{n=0}^{A}\sum_{m=0}^{B}\binom{A}{n}\binom{B}{m}\frac{(n+m)!}{n!m!}\frac{(A+B-n-m)!}{(A-n)!(B-m)!}$$

Formula when $A=B$ on the OEIS.
Implementation in Haskell
Execution trace for A=["a", "b"] B=["1", "2"] with 54 pairs since $N(2,2)=54$

EDIT: I am wrong: my algorithm behaves like separating $A$ and $B$ into $(A_1,A_2)$ and $(B_1,B_2)$ before interleaving $(A_1,B_1)$ and $(A_2,B_2)$ which is presumably what you don't want (it generates too many stacks, e.g. from $A=[2,1], B=[4,3]$ it includes $C=[2,3],D=[4,1]$).

(Mitchus's answer does not have this problem.)


Is k -rainbow coloring of a hypergraph NP-complete or not?

Deciding if a hypergraph can be rainbow colored in $k$ colors is NP-complete for every $k \geq 2$. A proof is given in [1, Theorem 12].

For $k=2$, the result follows immediately by observing the problem is equivalent to set splitting (also known as hypergraph 2-coloring). For $k \geq 3$, the authors of [1] give a reduction from chromatic index on $k$-regular graphs.

[1] M. Koivisto, P. Laakkonen, and J. Lauri. "NP-completeness results for partitioning a graph into total dominating sets". In Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON), volume 10392 of Lecture Notes in Computer Science, pages 333-345. Springer, 2017.


Given a binary min-heap, find the $k$-th element

The minimum element will the root. So in constant time you can find the minimum element. Delete the minimum element from the root. Now min-heapify (make it minheap) the resultant tree.
The second minimum element will be the root again. Repeat the procedure mentioned above.
By this procedure, you will find $k$-th minimum element in time $O(k \log n)$ where $n$ is the number of elements in the given min-heap.


Show $x^y$ is a primitive recursive function

As I wrote in the comments, you haven't actually proved anything.  If you want to prove that $x^y$ is p.r., you need to write it in the scheme form, and then you need to prove that indeed $x^y = f(y,x)$ for your defined $f$ for all $x$ and $y$ (by double induction).

Consider the following definition of $f(y,x) = x^y$:

$f(0,x) = s(z(x))$ (i.e., the successor of the constant zero function).

$f(y+1, x) = u^3_1(u^3_1(x^y, x, y) \cdot x, x, y)$.

I assume now that multiplication, $x \cdot y$ and wrote it infix, and obviously $x^y = f(y,x)$.  The function $u^a_b$ is the $a$-ary projection of $b$.

(Ps. if this doesn't work for you, please post your scheme you want to use, otherwise we cannot do else then guess.)


Yes.  If you start with a Euler cycle for the graph and restrict to a biconnected component, then what you have is still a cycle on the biconnected component (basically, if the euler cycle leaves vertex v in the biconnected component, then you know it must return to the biconnected component through v, otherwise we could enlarge our biconnected component - contradicting its maximality).


Combinator terminology: What is "strong" about strong composition?

I'm not familiar with the "strong" terminology. However, the 'obvious' answer to the other question is that it both duplicates the $x$ argument and exchanges the relative positions of (one copy of) the $x$ and $g$ arguments:
$$\mathsf s\ f \ g\ x = f\ x\ (g\ x)$$
The other combinator it's usually paired with:
$$\mathsf k\ x\ y = x$$
discards an argument. Together, this is all three of the structural rules for a variable context (contraction, exchange, weakening), and it includes composition as well.


Shortest non intersecting path for a graph embedded in a euclidean plane (2D)

It is NP-complete to even decide whether any path exists.

It is clearly possible to verify any given path is a valid path in the given graph. Thus the bounded-length problem is in NP, and so is its subset, the any-path problem.

Now, to prove NP-hardness of the any-path problem (and thus of the bounded-length problem), let's reduce SAT-CNF to this problem:

The global structure is a grid of wire pieces adjoined by a column of clause pieces. Logic formula is satisfiable iff there exists a non-intersecting path through the graph.

It is impossible to cross two pieces of the path, but it is neccessary to cross two logic wires. Rather, the path flow is strictly given: a wire point is given by two nodes. The sequence of the wire points through which the path passes is forced by the reduction. Logic is represented by which node is chosen. Any path can be chosen as long as it passes through all wire points.

In this diagram, the path is represented by the red curve and the logic flow is represented by the black wires:

Now let's build each component.

Wiring uses three tiles: the crossing, the branch point, and the vertical wire. Let's start with the hardest one:

The basic idea behind the crossing is to prepare a path for each pair of wire points and bend the possible paths enough so that all pairs except those that encode the same logic (compatible paths) cross each other. Of course we can't just say two parallel edges intersect, but we can introduce extra order-2 nodes to make two paths intersect.

Supposing the paths come from north to west and from south to east, we can: collect each path from north with its compatible path from east on a line (some incompatible paths will cross each other); cross each pair with each other by reversing the order of pairs; distribute the paths to their south and west endpoints. This is best explained by a diagram. Here, each pair of nodes represents a wire point. Paths with the same color code (carrying the same logic) don't intersect, paths a different color code do:

The branch point and the vertical wire work the same, but there are fewer paths to correlate:

The clause box follows the same logic: each literal exposes one of its paths to the reading wire, then converging to the south (if it's the northernmost term or the term to the north converges to the north) or to the north (if the term to the north converges to the south). The reading wire (one node at the endpoints) branches to become one path per literal. Each reading path then crosses the literal's true-path if the literal is negated, the false-path if it is not. Note that the converged path may or may not cross a clause boundary. For consistency, here's a diagram for $\neg A \vee \neg B$:

It is possible to generalise this reduction to encode an arbitrary tree of AND and OR gates by branching the reading wire in different way. In particular, SAT-CNF and SAT-DNF are both possible to reduce to the non-intersecting path problem in the way described as above.


Using pumping lemma to prove that $L = \{ a^ib^j \mid \lvert i - j \rvert \le 2 \} $ is irregular

You can use the word $a^pb^p$, where $p$ is the constant promised by the pumping lemma.


Can Barrington's Theorem be used to speed up computation of some function ? How?

Barrington's theorem probably isn't going to be useful to speed up computation.  Rather, it's a useful way to understand the power of different computing models.  For instance, it has been used to prove facts about what can be computed with log-depth circuits.  It has also been used as a tool in building fully homomorphic cryptosystems.


How to show that every quadratic, asymptotically nonnegative function $\in \Theta(n^2)$

So I actually found the answers I was looking for. The case $c \ge 0$ is already handled in the question above. For the case $c < 0$ we have:

\begin{align}
n_{1/2}
&=   \frac{-b \pm \sqrt{b^2 - 4ac}}{2a} \\
&\le \frac{|b| + \sqrt{b^2 - 4ac}}{a}   \\
&\le \frac{|b| + \sqrt{b^2} + \sqrt{-4ac}}{a} \\
&=   \frac{2|b| + \sqrt{4a|c|}}{a}  \\
&=   \frac{2|b| + 2\sqrt{\frac{a^2|c|}{a}}}{a} \\
&=   2\frac{|b|}{a} +  2\sqrt{\frac{|c|}{a}} \\
&\le 2\max(\{|b|/a, \sqrt{|c|/a}\}) \\
&= n_0
\end{align}

This value for $n_0$ includes the case $c \ge 0$. If $f$ doesn't have any roots, we can instead choose $n_0 = 1$.

For the constants $c_1, c_2$ the authors gave us the values $c_1 = a/4$ and $c_2 = 7a/4$. To check that these are correct we do the following:

Since $n \ge 2|b|/a$ and $n \ge 2\sqrt{|c|/a}$, we know that:
\begin{alignat}{3}
&& \frac{1}{2} &\ge  &\frac{|b|}{an} \quad&\text{and}\quad &\frac{1}{4} \ge  &\frac{|c|}{an^2} \\
&&-\frac{1}{2} &\le -&\frac{|b|}{an} \quad&\text{and}\quad -&\frac{1}{4} \le -&\frac{|c|}{an^2}
\end{alignat}

This gives us

\begin{alignat}{2}
&\frac{1}{4} =   1 - \frac{1}{2} - \frac{1}{4} \le 1 - \frac{|b|}{an} - \frac{|c|}{an^2} \le 1 + \frac{b}{an} + \frac{c}{an^2} \\
\text{and therefore}\quad
&\frac{a}{4}n^2 \le an^2 + bn + c
\end{alignat}

and

\begin{alignat}{2}
&1 + \frac{b}{an} + \frac{c}{an^2} \le
 1 + \frac{|b|}{an} + \frac{|c|}{an^2} \le
 1 + \frac{1}{2} + \frac{1}{4} =
 \frac{7}{4} \\
\text{and therefore}\quad
&an^2 + bn + c \le \frac{7a}{4}n^2
\end{alignat}

which shows that the values $c_1 = a/4$ and $c_2 = 7a/4$ are indeed correct.


No. It means you should count how many slots you have checked, and if you have checked more than the available number of slots, you resize the table.

In practice, if you regularly visit more than ten slots, then either the hash function is bad (nothing you can do about it while your program is running), or your load factor is too large. Not finding an empty slot will only happen if an attacker can decide your hash values.


It's the greatest fixed point, or the final coalgebra, depending on how you set things up. In Haskell it is impossible to define the datatype of finite lists because Haskell does not have inductive types, only the coinductive ones. Many people are in denial about this particular issue.


How can $Increment([m+1/2])$ be rewritten as $Increment([m])$?

Recall that $[x]$ means the greatest integer less than or equal to $x$.

Since $m$ is integer, $m$ is the less than $m+0.5$ and $m+0.5 < m+1$. Thus the the greatest integer less than or equal to $m+0.5$ is $m$.


Every non-empty context-free language has an ambiguous grammar. Indeed, take any context-free grammar for the language, and add to it the production $S \to S$ (if it is not already there), where $S$ is the start symbol. Every word in the language has infinitely many derivations, since given a derivation, we can always come up with a longer one by adding an application of the rule $S \to S$ at the very beginning.


What is the difference between Data Hazard and Dependencies in Pipelining

I think a dependency is something you see by looking at the code and trying to figure out possible WAW, WAR, RAW hazards that could happen. Actual hazards instead are a property of the pipeline which means that a dependency you found earlier may or may not generate an hazard depending on the actual code execution in the processor.
In your example there's an output dependency between the instructions I2 - I4, but if we assume that the pipeline does not stall for any reason between the two and that the execution time for each instr. is the same, I2 wll be completed before I4 thus not generating any hazard.
To make the answer more clear, with the information you give about the excercise it's impossible to know the number of hazards because we don't know the architecture on which that code is executed nor the state of the pipeline.
I found your question searching for an answer so I'm not completely sure. Since you asked some months ago maybe you already found the correct answer. If so could you share it please ?


Is the problem that determines whenever the word member $\in$ L(M) decidable or not?

I would try it like this:
Reduction from $A_{TM}$: Given TM $A$ und word $w$.
Use that to define a new machine $A'$ that works as follows:

Run like $A$ on input $w$
If $A$ rejects $w$, go into eternal loop.
If $A$ accepts, delete the band content and write "member"


Recurrence $T(n) = 2T(\sqrt{n}) + \log n$

Since you know how to solve recurrence equations of the form $S(n) = \alpha S(n/\beta) + f(n)$, you want to transform the given recurrence into this form. You notice that $\log \sqrt{n} = \frac{1}{2}\log n$, so $m = \log n$ is a good substitution.

More generally, there are no rules on how to solve recurrence relations (or anything in mathematics). Having seen the Master theorem, you know what to do when you have a recurrence of the form $S(n) = \alpha S(n/\beta) + f(n)$. Having seen this example, you know (a) what to do when you have a recurrence $T(n) = \alpha T(n^\beta) + f(n)$, and (b) it is a good idea to try to reduce a general recurrence to one of the form $S(n) = \alpha S(n/\beta) + f(n)$ by using an appropriate substitution.

As you get deeper into the subject (if you choose to do so), you will learn more tricks that will help you solve problems. Yet sometimes a new trick will be necessary. When all else fails, you just try a lot of things with your recurrence. Hopefully, after a while a winning direction will emerge. This is called (mathematical) research.


Combinational Logic Circuits and Theory of Computation

Logic circuits are common in complexity theory, where they go by the name circuits. There is a big difference between circuits and models of computation such as the Turing machine: each circuit can only handle inputs of fixed size. In order to fix this, under the circuit computation model, for every input length $n$ there is a circuit $C_n$, and together they compute a function on strings of arbitrary length. This computation model, as stated, is too strong: it can compute uncomputable functions, indeed all functions. The problem is that an infinite sequence of circuits doesn't necessarily have a finite description. In order to fix this problem, we usually demand that the circuits be uniform, that is, that they be generated by some Turing machine, which on input $n$ generates $C_n$.

The circuit model is especially popular in complexity theory, even without the uniformity restriction. The reason is the following observation: a Turing machine running in polynomial time can be converted to a (uniform) sequence of circuits of polynomial size, using essentially the ideas of Cook's theorem (which shows that SAT is NP-complete). Hence if you want to prove that a certain problem cannot be solved in polynomial time, it is enough to show that it cannot be solved by polynomial size circuits.


Is the FSA for that language right? Comparison between two solutions

Your FSA would not accept the string AAB or ABBBA, or any string ending with a B or starting with AB... or starting with BA... etc., all of which it should.

One of your main issue is that you don't have any B paths out of state 1, but more problematically you only have three states, when you need at least four. This is because you have 4 different possible states, so you need at least 4 states to store all of them (odd A & odd B, odd A & even B, even A & odd B, even A & even B).

Your teacher's is correct because it has essentially divided up the responsibility of checking the parity of A's and B's to different halves. That is, you're in the top half of the graph whenever the number of A's is even, and the right half of the graph whenever the number of B's is odd. This works because each additional letter added is going to either make B go from odd to even (or vice versa) or A to go from odd to even (or vice versa).


is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?

We can write a computer program that will enumerate all halting computer programs. It seems that you are happy to accept accumulating the output of program into a (potentially infinite) set. Thus, you accept "all halting computer programs" as a valid set. It is, however, not a decidable set.
The standard proof of the undecidability of the Halting problem is constructive. Since we are proving a negative statement, a constructive proof is going to start with the assumption that it were decidable and going to derive a contradiction. Note that a decider by definition will answer either "yes" or "no" on any input, we can thus do the case-distinction in the usual proof of the undecidability of the Halting problem without having to involke the law of excluded middle.
Alright, so let us have a look at how exactly to prove that the Halting problem is undecidable. Bob claims the Halting problem is decidable, and we prove him wrong. Since Bob claims decidability, we can make him tell us what program he thinks does the job. Bob has to give us a program D, and the assurance that on any input w, the computation D(w) will halt and answer either "true" or "false".
Now, consider the following program:
E(input s)
   While {D([s]('s')} {do nothing}
   halt

Here, with $[s](`s')$ I mean "consider s as a program, and apply this program to the input given by s considered as a string". This may feel weird, but since we have received s, we can obviously copy it and so on.
Now, modulo knowing what D is (and that's Bob's responsibility, not mine), we have a concrete piece of code up there. Call that piece of code "e". We can again treat e both as a program (which takes an input) and as a string. In particular, it makes sense to consider $[e](`e')$ again, which is the program e run on the string e as input.
Bob has claimed that running $D([e](`e')$ will answer either true or false, and that this answer is about whether the computation $[e](`e')$ ever halts. Since Bob so kindly provided the case distinction for us, we can exploit it.
If $D([e](`e')$ answers "true", then in the computation that happens when we run E('e') we can never escape the while-loop, so it can't halt. Bob is wrong.
If $D([e](`e')$ answers "false", then E(`e') never enters the loop, but halts straight away. Bob is wrong, again. We won.


Operations without common elements can not be generated using a finite state automata

One has to differentiate between regex in computer science and regex in real world programming languages. In compsci regular expressions are defined to only recognize regular languages, which are the same languages DFAs can recognize, thereby making DFAs and regex a descriptions of the same class of languages.
In real world application the recognition of regular languages is somewhat limiting which is the reason why many regex libraries introduce operators which allow you to recognize languages that are not regular. One such operator is recursion (?R) see here for an example using python. Notice that the language in the article is the balanced parentheses language which is a well known context free language that is not regular and thus can not be recognized by a DFA.


Can a purely declarative language really exist?

Declarative programming defined the goal, as in your example transform A to B, where steps made are not present in this layer of abstraction, and simply it is not enforced.

Imperative programming defines steps to achieve the goal. With optimizations it is a bit of mixture of both - steps are defined but this is translated to goal and then changed to make it faster.

To achieve exactly imperative in this pure form all optimisations need to be suppressed, branching does not change the order. Interpreter executing one instruction at the time does that already.

As far as I know we call languages like C, Fortran, Pascal, assembler imperative languages and do not go into details of execution. One example is read from disk 1bit, 1 byte, several bytes and so on - disk reads the whole batch at once so it did not exactly what we asked for, the same with access to memory.

The side effects are not declarative, but imperative. Purely functional language is declarative already. The problem with purely functional language is e.g. I/O, which is mittigated by monads, to set states, but it does not matter to declarative one.


Algorithm for generating sorting instructions

Generally speaking, you sorting algorithm should involve the following two steps:

Sort the books and assign them a numerical order.
Generate optimal sorting instructions given the permutation.

In your example, you start with a list of four books. Sorting them, you assign them a numerical order, B C A D (the numbers here are A,B,C,D). Then you figure out instructions for sorting the permutation B C A D. One approach that will always work is to move A to 0, B to 1, C to 2, and so on. However, this is not optimal. Figuring out the optimal sequence of moves seems like the difficult part of your question.


How to actually implement universal hashing?

One example of universal hashing's application is perfect hashing. If you know all the keys beforehand, we can obtain $O(1)$ time for search, insert, delete (dynamic perfect hashing exists but is difficult to implement). More concretely we hash all of our values with an initial hash function into our table and keep track of where collisions occurred. For wherever $d>1$ collisions occurred, you build another hash table of size $d^2$. You obtain a hash function for this ($d^2$ size) table by applying universal hashing until you get no collisions.

Universal hashing guarantees that the probability of getting collisions with any two distinct keys is $\leq \frac{1}m$ where $m$ is our table size. Following your universal hash functions $h_{a,b}$ defined above (which is proved to be universal using number theory), we can try various $a,b$ in each $d^2$ size table until we get no collisions.

So to answer your question you just try a bunch of times (usually not too many as shown by probabilistic analysis and universal hashing) until you get a hash function that works for your problem setting and then save that hash function to use later for retrieval, insertion...

To be clear, the cost of utilizing this data structure is $O(1)$ because we only need to compute the first hash function and then the second hash function (we obtained via universal hashing).


Are Petri Nets actually used in the industry

Petri-nets are e.g. used for Businees Process Modeling with BPMN. Of course Petri Nets are an abstract idea that lends itself to modelling a wide variety of dynamic and/or distributed systems - but especially for business processes, the provable reachability, liveness and boundedness are useful properties.


What is an oracle separating IP and PSPACE?

The answer to the question you link contains all the information you need. The multi-authored paper The random oracle hypothesis is false proves the stronger result that IP and PSPACE are different with probability 1 with respect to a random oracle. They also comment that a concrete oracle under which IP differs from PSPACE can be constructed using standard techniques, by which they mean the form of diagonalization used to separate P from NP with respect to a concrete oracle; they do not provide any details, though. Presumably it is a not too difficult exercise.

The meta-question is addressed both in the answer you link and in the paper. I suggest you first read the paper, and then if you have more questions, you can ask them here in this site.


Tree balance is usually preferable as the depth of the tree is shortest and the tree itself is most compact. However, there are few situations in which the fact that is unbalanced is what gives it efficiency. Huffman Coding is an example of this, where shorter paths in a binary tree represent frequently used items.


Proving that any CF language over a 1 letter alphabet is regular

Let $L$ be a unary context-free language. According to the pumping lemma, there is a constant $p$ such that if $a^n \in L$ then either $n < p$ or there exists $q \in \{1,\ldots,p\}$ such that $a^{n+tq} \in L$ for all $t \geq 0$ (actually, the pumping lemma gives $t \geq -1$). Let $L_0$ be the set of words in $L$ of length smaller than $p$, and for $q \in \{1,\ldots,p\}$, let $L_{q_0}$ be the set of words in $L$ of length at least $p$ for which the pumping lemma gives $q = q_0$. I claim that
$$
L = L_0 \cup \bigcup_{q=1}^p \{ a^{n+tq} : a^n \in L_q, t \geq 0\}.
$$

Proof of $ \subseteq $: If $x \in L$ then either $|x| < p$, in which case $x \in L_0$, or $|x| \geq p$, in which case $x \in L_q$ for some $q$, and so $x$ belongs to the $q$'th summand on the right (choosing $t \geq 0$).

Proof of $ \supseteq $: This follows directly by definition of $L_0$ and $L_q$.

Since $L_0$ is finite, it is regular. Hence it suffices to prove that for each $q \in \{1,\ldots,p\}$, the following language is regular:
$$
R_q := \{ a^{n+tq} : a^n \in L_q, t \geq 0\}.
$$
Let us write, for $0 \leq r \leq q-1$,
$$
R_{q,r} := \{ a^{n+tq} : a^n \in L_q, t \geq 0, n \equiv r \pmod q \},
$$
so that $R_q = \bigcup_{r=0}^{q-1} R_{q,r}$. Thus it suffices to prove that each $R_{q,r}$ is regular.

If no $a^n \in L_q$ satisfies $n \equiv r \pmod q$, then $R_{q,r} = \emptyset$ is clearly regular. Otherwise, let $n_{q,r}$ be the minimal $n \equiv r \pmod q$ such that $a^n \in L_q$. I claim that
$$
R_{q,r} = \{a^{n_{q,r} + tq} : t \geq 0\} = a^{n_{q,r}} (a^q)^*,
$$
and so $R_{q,r}$ is regular.

Indeed, clearly $R_{q,r}$ contains the right-hand side. On the other hand, suppose that $a^m \in R_{q,r}$. Then $m = n+tq$ for some $n \equiv r \pmod q$ and $t \geq 0$ such that $a^n \in L$. But then $m = n_{q,r} + (t+(n-n_{q,r})/q)q$ (our choice of $n_{q,r}$ guarantees that $n \geq n_{q,r}$ and that $n-n_{q,r}$ is divisible by $q$), and so $a^m$ is an element of the right-hand side.


Consider the following grammar for arithmetic expressions:
$$
X \to X + X \mid X - X \mid X * X \mid X / X \mid \texttt{var} \mid \texttt{const}
$$
Consider the following expression:
$$
a - b - c
$$
What is its value? Here are two possible parse trees:

According to the one on the left, we should interpret $a-b-c$ as $(a-b)-c$, which is the usual interpretation. According to the one on the right, we should interpret it as $a-(b-c) = a-b+c$, which is probably not what was intended.

When compiling a program, we want the interpretation of the syntax to be unambiguous. The easiest way to enforce this is using an unambiguous grammar. If the grammar is ambiguous, we can provide tie-breaking rules, like operator precedence and associativity. These rules can equivalently be expressed by making the grammar unambiguous in a particular way.

Parse trees generated using syntax tree generator.


How can one measure the time dependency of an RNN?

I am not aware of any standard or widely-used metric for this. I think what metric would be appropriate would depend on what you want to use it for.
The issues with RNN is "forgetting".  If you feed a long sequence of inputs $x=(x_1,\dots,x_n)$ into a RNN, where $n$ is too large, the problem is that often the final decision is determined by the last few values ($\ldots,x_{n-1},x_n$) and the earliest values ($x_1,x_2,\ldots$) have been "forgotten" and do not affect the final decision.  This is undesirable in many settings.
Your metric would be one reasonable way to get a feeling for this.  Another reasonable way might be to to feed in an input $x=(x_1,x_2,\dots,x_n)$, then change just $x_1$ to get a new input $x'=(x'_1,x_2,\dots,x_n)$, feed in $x'$, and compare the outputs of the RNN on $x$ vs $x'$; and repeat for many training samples or test samples $x$.


Give CFG and PDA for the words that start and end with the same symbol

A DFA is simple: From start state $A$ on 0 go to $B$, from $B$ with 0 go to $C$ (final), from $B$ with 1 stay in $B$, from $C$ with 0 stay in $C$, from $C$ with 1 go to $B$. Use a mirror for 1.

The PDA is just the DFA which essentially ignores the stack (rewrite the stack start symbol with itself on each move).

A CFG is just:
$$
\begin{align*}
S &\rightarrow 0 A 0 \mid 1 A 1 \mid 0 \mid 1 \\
A &\rightarrow 0 A \mid 1 A \mid \epsilon
\end{align*}
$$
A CFG more in line with the DFA is:
$$
\begin{align*}
S &\rightarrow 0 A \mid 1 B \mid 0 \mid 1 \\
A &\rightarrow 0 A \mid 1 A \mid 0 \\
B &\rightarrow 0 B \mid 1 B \mid 1
\end{align*}
$$


How to we prove if a right linear language is ambiguous?

For simplicity, let me assume that the only allowed rules are of the form $A \to aB$ and $A \to \epsilon$. Denote the set of nonterminals by $V$, where $S \in V$ is the starting symbol.
Construct a new right linear grammar with nonterminals $V \times V \times \{0,1\}$. The new grammar will simulate two different production sequences for each word, keeping track whether the two actually differ.
The starting symbol is $(S,S,0)$, and the rules are:

For every pair of original rules $A \to aB$ and $C \to aD$ we add the rule $(A,C,1) \to a(B,D,1)$. (Possibly some of $A,B,C,D$ are equal.)

For every pair of original rules $A \to aB$ and $A \to aC$ such that $B \neq C$ we add the rule $(A,A,0) \to a(B,C,1)$. (Possibly $A=B$ or $A=C$.)

For every pair of original rules $A \to \epsilon$ and $B \to \epsilon$ we add the rule $(A,B,1) \to \epsilon$. (Possibly $A=B$.)

A word $w$ has two different derivations in the original grammar iff it can be generated by the new one.
For example, in your sample grammar the word $ba$ has two different derivations, $S \to bA \to baB \to ba$ and $S \to bA \to baD \to ba$, and this is reflected in the following derivation in the new grammar:
$$
(S,S,0) \to b(A,A,0) \to ba(B,D,1) \to ba.
$$


Is there a computationally reasonable algorithm for generating a set of polygons from a set of 2d points?

Yes, there are even algorithms which are able to satisfy additional constraints. It can occur as a subtask during mesh generation. The vanilla algorithm is the Delaunay triangulation, which is closely related to the Voronoi diagram (in case you wonder why D.W. thinks that the Voronoi diagram answers your question).


I don't really understand your reduction, but there is a very easy reduction from
$ALL_{CFG}=\{G| G \text{ is a CFG and } L(G)=\Sigma^*\}$.
Given $G$, Simply output $(G,G_{\Sigma^*})$, where $G_{\Sigma^*}$ is a (concrete) grammar that generates every word.

And the problem $ALL_{CFG}$ can be shown to be undecidable with a very nice (but elaborate) reduction from the word problem for TMs.


Given a sufficiently powerful computer and model, can dice rolls be predicted?

I believe it could be predicted assuming technological limits of sensors and computation were overcome. A die is too large for quantum effects and a simple enough system.

Related paper


Undecidable definition of pure function?

On undecidability

You attempt to prove that fibonacci is pure in a particular way, and you fail to do so. This does not prove that purity is an undecidable property. All it shows is that this particular way of determining the purity of fibonacci doesn't work.

A property is undecidable if no matter what method you use to calculate it, there is a parameter for which it fails. The possible methods are algorithms implemented on a Turing machine or any equivalent framework (recursive functions, etc.).

Purity is undecidable in general, but you need more language constructs than what you showed. For example, it is easy to reduce purity to halting, which is a well-known undecidable problem:

f;
global := 3;

This code is pure iff global := 3 is never executed, which is equivalent to saying that f doesn't terminate. So if you can decide purity, you can decide halting.

On recursive definitions

Your definition of purity is incomplete. You need to explain in more detail how to deal with recursive functions. To illustrate this, let's consider the following axioms for a property which I'll call cuteness:

If A and B are cute then A; B is cute.
If A, B and C are cute then if A then B else C is cute.
If A, B1, …, Bn are cute then A(B1,…,Bn) is cute.
+, -, == are cute.

Is fibonacci cute? If the list of axioms above is complete, then no, fibonacci is not cute, because a recursive function definition is not cute. All of the axioms above work if I replace “cute” by “terminating”, which shows that adding recursive functions to the mix can radically change the definition.

If I add the following axiom:

If A is cute then function f () { A } is cute.

Then all cute functions are, in fact, pure in the sense of not having assignments as side effects. The axioms above in fact completely capture a strong notion of purity, i.e. if a function is pure then you can prove it using these axioms. The notion of purity defined here forbids all assignments, even if they don't escape their scope.

On defining purity

If you want to allow internal side effects, you need a more complex definition, with a context. Above all axioms were of the form “if these programs have the property then that program has the property too”. More complex properties need to consider programs in context, to describe the variables, types, memory locations, etc. used in the program. The following rules capture purity in a context which defines what variables are allowed to be modified:

If A and B are pure in the context Γ then so is A; B.
If A, B and C are pure in the context Γ then so is if A then B else C is cute.
If A, B1, …, Bn are cute in the context Γ then so is A(B1,…,Bn).
+, -, == are pure in any context.
If A is pure in the context Γ then A is also pure in any superset of Γ.
If A is pure in the context Γ, x1,…,xn then function f (x1,…,xn) { A } is pure in the context A.
If A is pure in the context Γ then x := A is pure in the context Γ, x.

A better way to say “A is pure in the context Γ” might be “Γ captures all the side effects of A”. A program is pure if the empty context captures its side effects.


We want to show that the number of nodes $n$ in a height-balanced binary tree with height $h$ grows exponentially with $h$ and at least as fast as the Fibonacci sequence.

Let $N_h$ denote the minimum number of nodes in a height-balanced binary tree having height $h$.  Recall that in a height-balanced binary tree of height $h$, the subtree rooted at one of the children of the root has height $h-1$, and the subtree rooted at the other child of the root has height $h-1$ or $h-2$.  Thus, $N_h > N_{h-1} + N_{h-2}$.  Thus, $N_h$ is at least $f_h$, the $h$th term of the Fibonacci sequence, where $f_h \approx \phi^h / \sqrt{5}$ and $\phi$ is the golden ratio $\frac{1+\sqrt{5}}{2}$.

So, if $n$ is the number of nodes in an AVL tree of height $h$, we have $n \ge \phi^h / \sqrt{5}$. Taking $\log_2$ of both sides, we get $h \le \frac{\log_2 n}{\log_2 \phi} + c = 1.4404 \log_2 n + c$, for some constant $c$. Thus, an AVL tree has height $h = O(\log n)$

An easier proof, if you don't care about the constants as much, is to observe that $N_h > N_{h-1}+N_{h-2} > 2N_{h-2}$.  Hence, $N_h$ grows at least as fast as $\sqrt{2}^h$.  So the number of nodes $n$ in a height-balanced binary tree of height $h$ satisfies $n > \sqrt{2}^h$.  So $h \log_2 \sqrt{2} < \log n$, which implies $h < 2 \log n$.


Is the algorithm implemented by git bisect optimal?

Here's some intuition for what $X$ and $N$ are doing.  Focus on a particular commit $c$.  Suppose we test $c$ and classify it as either "good" or "bad".  Until we test it, we don't know whether it is good or bad, but we can predict in advance how much smaller the graph will get in each of those two cases.  In particular, $X$ is the number of commits that would be trimmed away if commit $c$ turns out to be good, and $N-X$ is the number of commits that would be trimmed away if commit $c$ turns out to be bad.

Therefore, the value $\min(X,N-X)$ is a lower bound on the number of commits we'll be able to trim away in the next step, no matter how the test turns out.  The idea of the Git algorithm is to maximize of this metric.  In other words, Git picks a threshold $t$ that is as large as possible, and a commit $c$ to test next, such that Git can be sure that it'll be able to trim away at least $t$ commits in the next step.

If we have no information about whether each commit is likely to turn out good or bad, so it's equally likely that it's good or bad, then this looks like a locally optimal choice.  Thus, the Git algorithm is a greedy algorithm.

Is the Git algorithm globally optimal?  That will depend upon the definition of "optimal", and (probably) on the distribution of DAGs one encounters in practice.  Probably there is no simple characterization of the probability distribution on DAGs one encounters in practice, so I'd expect it is probably going to be difficult to find an optimality result for this problem.


Where does the lg(lg(N)) factor come from in Schönhage–Strassen's run time?

The sticking point is the size of the integers in the recursive step, which is not quite $\sqrt{n}$, but rather twice as large, since the product of two $t$-bit integers has size $2t$. Assuming that we break the original $n$-bit integer into $\sqrt{n}$ parts of length $\sqrt{n}$, the running time recursion is
$$ T(n) = n\log n + \sqrt{n}T(2\sqrt{n}), $$
and by expanding it, we get
$$
\begin{align*}
T(n) &= n\log n + \sqrt{n}T(2\sqrt{n}) \\ &=
n\log n + 2n\log (2\sqrt{n}) + 2^{1/2} n^{3/4} T(2^{3/2}n^{1/4}) \\ &=
n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^{5/4} n^{7/8} T(2^{7/4} n^{1/8}) \\ &=
n\log n + 2n\log (2\sqrt{n}) + 4n\log (2^{3/2} n^{1/4}) + 2^3 n \log (2^{7/4} n^{1/8}) + \cdots,
\end{align*}
$$
so each level of the recursion takes time proportional to $n\log n$. Since there are $\log\log n$ levels, we get the quoted running time. For more information, check out these lecture notes.


Question regarding coin change algorithm (DP and greedy)

In terms of running time, the greedy algorithm is still going to be faster than the DP algorithm. DP will always produce the optimal solution regardless of values in V. Greedy, on the other hand, takes advantage of extra structure present in some value choices that allow it to effectively ignore possible ways of getting to the goal value. A coin system where the values are powers of p would allow the greedy algorithm to also consistently produce the optimal solution.


Algorithmic Complexity of Statistical Estimators

The bound $O(Q_n(θ) \cdot S(p))$ represents only the cost of evaluating $Q_n$ once per step in the "numerical optimization method"; you ignore all other cost that incurs.

Without looking at the whole algorithm, little more can be done.

Note: I very deliberately replaced $S$ with $S(p)$. That is because there is no reason, per se, to believe that $S$ is a constant. You need to be more careful about setting up your cost functions; our reference question may be helpful.


n*log n and n/log n against polynomial running time

$\log n$ is the inverse of $2^n$.  Just as $2^n$ grows faster than any polynomial $n^k$ regardless of how large a finite $k$ is, $\log n$ will grow slower than any polynomial functions $n^k$ regardless of how small a nonzero, positive $k$ is.

$n / \log n$ vs $n^k$, for $k < 1$ is identical to:
$n / \log n$ vs $n / n^{1-k}$

as $n^{1-k} > \log n$ for large $n$, $n / \log n > n^k$ for $k < 1$ and large $n$.


Is this variation of set-cover NP-hard to approximate?

Your first problem is a classical NP-hard problem known as maximum coverage. The greedy algorithm gives a $1-1/e$ approximation, and this is tight (assuming P≠NP).

Your second problem is a special case of set cover. Indeed, take any instance of set cover, and add to it the set $S$ itself. If the optimal solution for the set cover instance is $M$, then the optimal solution for the new instance (of your problem) is either $M$ or $M+1$. (You can also add $S \cup \{x\},\{x\}$, where $x$ is a new element, to make the optimal solution of the new instance exactly $M+2$.) Hence your problem inherits the $\ln n$-hardness of set cover. In the other direction, the greedy algorithm likely gives an $O(\log n)$ approximation for your problem.


Finding the two node-disjoint paths, minimizing the sum of their lengths

This can be solved by a small modification to Suurballe's algorithm, with $O(|E| + |V| \log |V|)$ running time.  You might also be interested in Computing the k shortest edge-disjoint paths on a weighted graph.
Suurballe's algorithm works with directed graphs.  You can convert an undirected graph to a directed graph by replacing each undirected edge $(u,v)$ with two directed edges $u \to v$, $v \to u$.


What is the time-complexity of histogram computation?

Presumably the time complexity of the function hist applied to data of length $N$ and to $B$ bins is $O(N+B)$ (the exact definition of $B$ depends on the implementation of hist; in your case, it seems to be the maximum of the input). In your case, each of the $n/s_1$ iterations of the loop is applied to data of length $s_1 m$, and so the total running time is
$$ \frac{n}{s_1} O(s_1m + B) = O(nm + \frac{n}{s_1} B). $$
The answer that your teacher expects is $O(nm)$.


What is the utility of proving P=NP if we can't find an algorithm that can solve any NP problem in polynomial time?

In short, if we prove $P=NP$, then we know a whole lot more about computation than we did before, even if we don't find the algorithm, and that was the objective behind research on $P=NP$ all along.

It's much worse, because most researchers believe that $P\ne NP$, meaning that even when the proof is discovered, it means that we won't be able to find a polynomial-time algorithm for SAT, not because we're looking in the wrong places, but because no such algorithm exists.

But that doesn't worry most complexity theorists, because the would-be algorithm for SAT that you describe is only a practical application, a spin-off, of the proof. And if you care about practical applications, then why are you working on $P=NP$? It's the most theoretical question in computer science!

Rather, the motivation behind research in this direction is* to better understand computation, very much akin to why mathematicians care about the Riemann hypothesis, and why physicists build giant particle colliders, even though we already have giant databases of prime numbers and even though the discovery of new particles mostly does not help us build faster rockets or better fusion reactors.

But what don't we understand about computation? We can build marvellous AI systems that recognize faces and Chinese characters, and predict the weather! Those are results of the form, this problem can be solved with so-and-so many resources, but on the flip side, one can ask, for this problem, what is the minimum amount of resources needed? The current state of affairs in the last regard is rather embaressing, because as far as we know:

SAT has a linear-time (!) algorithm**
SAT has an algorithm that uses $O(n^{1.802})$ time and $O(\sqrt{n})$ space
every language in $NP$ has a circuit with $5n$ gates.
The Succinct Circuit Satisfiability problem***, which is $NEXP$-Complete ($NEXP$ is the exponential-time version of $NP$), can be solved in polynomial time with a randomized algorithm with bounded error (i.e. it gives the wrong answer only with probability $\leq \frac{1}{n}$)
Everything that can be computed using a polynomial amount of memory can be solved using a polynomial amount of time. For example, the Quantified Boolean Formula problem, which is like SAT except instead of an $\exists$ quantifier, there are any number of $\exists x\colon\forall y\colon\exists z\colon\cdots$ quantifiers.

Until these ridiculous scenarios are ruled out, we cannot honestly say that we understand computation in any depth. And that is the utility that you ask for, of why anybody at all works on $P=NP$.

I encourage you to read this wonderful survey of Scott Aaronson where in section 1.2 he addresses all the usual objections, like, what if $P=NP$ but we can't find the algorithm, or what if we do, but it's exponent is hopeless, or...

*as far as I can tell, as someone who is not a professional complexity theorist, but who did write his Master's thesis on the topic.

** We do not know whether nondeterminism gives you an advantage for solving SAT, but we do know, since 1983 [1] that nondeterminism gives you an advantage for some language, because there is a language $L$ solvable by a non-deterministic machine in $O(n)$ time but not by any deterministic machine in $O(n)$ time. In 2001, that result was improved [2] to a language in $NTime(n)$ but not in $DTime(n\sqrt{\log(n)})$.

*** The Succinct Circuit Satisfiability problem is this: fix some encoding of Boolean circuits as binary strings. You are given a circuit on $n$ inputs. Interpret the truth table of this circuit as a binary string of length $2^n$. Interpret that string as representing a circuit. Is that circuit satisfiable?

[1] Paul, Wolfgang J., et al. "On determinism versus non-determinism and related problems." Foundations of Computer Science, 1983., 24th Annual Symposium on. IEEE, 1983.

[2] Santhanam, Rahul. "On separators, segregators and time versus space." Computational Complexity, 16th Annual IEEE Conference on, 2001.. IEEE, 2001.


Matrix permanent, #P-hard problems and NP

Let's take SAT, the quintessential NP-complete problem, as an example. An instance of SAT is a formula, and the answer is whether the formula is satisfiable. The corresponding #P-hard problem #SAT is instead to count the number of satisfying assignment. Clearly if you can count the number of satisfying assignments then you can tell whether one exists. In particular, if you can solve #SAT in polynomial time, you can solve SAT in polynomial time.

This shows that if some #P-hard problem can be computed in polynomial time, then all problems in NP can also be solved in polynomial time.


Why is binary subtraction referred to as the invert-add-shift-add method?

I found an excellent answer here, which I summarize below.

Given two number $A,B$ in binary notation, we calculate $A-B$ by adding to $A$ the two's complement of $B$. Since the two's complement of $B$ is formed by inverting all bits of $B$ and adding $1$, one way to implement this idea is invert $B$, add the result to $A$, shift the carry $1$ bit (which will appear if $A\geq B$), and add it (i.e. $1$) to the result.


Why is encrypting with the same one-time-pad not good?

I have no way to learn (say) $m_1$ unless I know $m_2$.

That is exactly the problem - if you re-use the same key, and someone has access to one message you encrypted in both plaintext and encrypted form, they can use that to find your key:
$$
(m_2 \oplus k) \oplus m_2 = k
$$

As an alternative scenario, if you use the same key over and over, the attackers may be able to guess just pieces of various encrypted message, and each successful guess reveals a piece of the key $k$, so that over time more and more of the key is revealed.

This general strategy for breaking a cryptosystem is known as a known plaintext attack. Many systems, like AES and RSA, are believed to be secure against these attacks. But a one-time pad becomes completely insecure against them unless a new pad is used for every encryption, which is why they are named "one-time pads".


How to determine the max offset of a value, given the range, step size and amount of steps

Suppose we start at $s$ and want to end up at $e$. We take $n$ steps, $n^+$ positive steps and $n^-$ negative steps. Then we can reach maximum $m \in[s, s + n^+\delta]$ and can end up in $[m-n^-\delta, m]$. We get equations:
\begin{align}
n &= n^+ + n^-\\
n^+ &\geq 0\\
n^- &\geq 0\\
s &\leq m \leq s+n^+\delta\\
m-n^-\delta &\leq e \leq m\\
\end{align}
Rearranging we get our upper bounds:
\begin{align}
m &\leq s+n^+\delta\\
m&\leq e+n^-\delta\\
\end{align}
Substitute and realize maximum:
\begin{align}
m &= \min(s+n^+\delta, e+n\delta - n^+\delta)\\
m &= s + \min(n^+\delta, e-s+n\delta - n^+\delta)
\end{align}
This looks complicated, but set $x = n^+\delta$ and $c = e-s+n\delta$ you only need to solve how to maximize:
$$\min(x, c - x)$$
Can you take it from here?