If you have a look at this wikipedia page  then you will see that there are over tens of algorithms for calculating the square root of a number.

Let's consider the Babylonian method for calculating square roots. This is very similar to Newton's iterative method for finding roots and therefore an approximation algorithm. The pseudocode is as follows:

1. Start with an arbitrary positive start value x.
The closer this value is to the actual root, the better the convergence is.

2. Initialize y = 1.
This variable will hold the value for the previous iteration of the root.

3. Initialize e = some arbitrary small value.
This will determine the accuracy of our root.

4. Do following until (x - y) > e :
  a) Set y = (n/x)
  a) Set x = (y + x) / 2

This answer gives a good look into how the running time complexity of the above method can be obtained. The TLDR version is $O(log(log(n))$ for $\sqrt(n)$.

A small thing to note is that if n can change throughout the loop, then the square root will be calculated every time the loop is run. However if n does not change at all, it is treated as a loop invariant and the compiler takes steps to optimize the performance internally. In short, the calculation of the square root is taken outside the loop body.

Finally, since there are multiple algorithms for calculating the root of a number there is no single solution to the question:

  how many arithmetic operations does (√n) use?

As for the second question, ie:

  Is it a fixed amount or does it change with n (and if so to what extent)?

You can clearly see that its not a fixed amount, and the number of operations depend on the value of n itself, the initial root chosen and the level of accuracy preferred.

Some related additional reading for iterative algorithms: Gradient Descent.


Calculate the number of cycles of a Cactus graph?

If a graph is a cactus, then the number of cycles is $c = m-n+x$, where $x$ is the number of connected components and $c$ is the number of cycles.

The proof is by induction on the number of edges. If $m = 0$, then the graph contains no cycles, and furthermore $n = x$, and so $m-n+x = 0$.

Suppose now that $m > 0$, and remove an arbitrary edge $(u,v)$. There are two cases:

The edge was not on a cycle. In that case, removing the edge increases the number of connected components by one: otherwise, $u,v$ are connected by some simple path not involving $(u,v)$, which together with $u,v$ would form a cycle. Therefore by the induction hypothesis, the number of cycles in the new graph is $(m-1)-n+(x+1) = m - n + x$. Since the original graph has the same number of cycles by assumption, this proves the induction hypothesis in this case.
The edge was part of a unique cycle. In this case, removing the edge does not increase the number of connected components, since $u,v$ are connected by the rest of the cycle. By the induction hypothesis, the new graph has $(m-1)-n+x = m-n+x-1$ cycles. The original graph has one more cycle, for a total of $m-n+x$ cycles, proving the induction hypothesis in this case as well.


Why is $\{a^nb^n \mid n \geq 1\}$ not type 3 (regular)?

$S\Rightarrow bS\Rightarrow baS\Rightarrow bab$.

However, $bab$ is not $a^nb^n$ for any $n$.

(Exercise.) Is the following grammar a grammar for $L_1$?

$S \to Sa \mid Sb \mid a$


What Good Is Kolmogorov Complexity Since It Is Relative?

The relativity is up to an additive constant. Suppose that you express Kolmogorov complexity relative to your favourite universal Turing machine $U$, but I do it relative to my favourite UTM $V$. If the shortest program for $V$ that outputs a string $x$ is $M$, then the shortest program for your machine $U$ can't be any longer than the one that simulates $V$ running $M$, and that has length $|M|+k$, where $k$ is the size of the simulator.

So, yes, you could pick a UTM that has a very efficient coding for some finite set of strings. However, that would increase the length of the coding of at least that the same number of other strings, and we're typically interested in the asymptotic behaviour of infinite families of strings, rather than individual strings.


Why c_f (u, v) = f (v, u) if f (v, u) not in E?

There is a significant typo on that slide.

"$c_f (u, v) = f (v, u)$ if $f (v, u)$ not in $E$" should have been "$c_f (u, v) = f (v, u)$ if $(u, v)$ not in $E$" or, what is equivalent, "$c_f (u, v) = f (v, u)$ if $(v, u)$ is in $E$".

  Why do we care about edge that is not in $E$?

In fact, we care only edge $(u,v)$ if either $(u,v)$ is in $E$ or $(v,u)$ is in $E$. If $(v,u)$ is in $E$, it appears that we care about $(u,v)$, an edge that is not in $E$.

The reason can be seen by looking at the specific example in those slides written by Vincent Maccio.

The flow in the above network is not the maximum flow, 6. However, there is no path from $s$ to $t$. How about adding a flow of 2 along the edges along the edges $s\to 2\to1\to3\to t$? This flow is apparently invalid since the only capacity between 1 and 2 are from 1 to 2 instead of from 2 to 1. However, if we consider the net effect of all flows on the edge between 1 and 2, it is effectively 0 as we had a flow of 2 from 1 to 2. So the combinations of all flows, including the apparently illegal flow are in fact valid.

Now the problem is how we can find that apparently invalid but actually valid and helpful additional flow. We did it by a stroke of luck or a flash of intelligence. The systemic way is to adjust the remaining capacities on possible more edges. In the example, we can add an edge from 2 to 1 of capacity 2, which will enable the algorithmic search for additional valid flow.  That is, since directed edge (2,1) is not in $E$ (the directed edge (1,2) is in $E$), we would like to add edge (2,1) with capacity the flow through (1,2). That is " Why $c_f (u, v) = f (v, u)$ if $(u, v)$ not in $E$."

For more information, check the slides and related materials on the web.


Pumping Lemma: is it valid to "multiply the product of powers" in this case?

You're right, the superscript in this context means concatenation.

To prove a language isn't regular, you use the fact that any regular language can be "pumped". First, find out what "pumping" a word means (I can't do your homework for you), and then show that your language can not be pumped, and thus, can not be regular.  Basically you will take a sufficiently long word that belongs to your language, and show that it cannot be broken up and pumped in such a way that it satisfies the pumping lemma.

Note that the converse of the pumping lemma is not always true: that is, if a language does NOT satisfy the pumping lemma, it may still be non-regular.  For this reason, the pumping lemma is used to exclude a language from a set of languages, and not to include a language in a set of languages (such as regular).  In other words, satisfying the pumping lemma is a necessary, but not sufficient, condition for a language to be regular.


Convolutional Neural Network with constant kernels

A fully connected layer is able to classify images better than random. If you make the kernels constant and there is still information in the result, the network is essentially only a FCN operating on a preprocessed image. Of course it will learn how to classify the image. But it will certainly be worse than a similar network where the convolutional weights are learned.


From your explanation I assume that the game is not episodic, but sequential: each move outcome is dependent on the previous moves.

The Minimax algorithm modification you explained is called Expectimax and is generally a standard approach for such problems as far as I know. In order to avoid the big branching factor you can try some variation of the Monte Carlo algorithm. This way you will be able to explore deeper the game tree and still take into consideration the randomness.


If $L_2 \neq \Sigma^*$ and $L_2 \neq \emptyset$ then $L_1 \in R$ and $L_2 \in RE$ implies $L_1 \le_m L_2$.
Let $T$ be a Turing machine that decides $L_1$. Let $a,b \in \Sigma^*$ such that $a \in L_2$ and $b \not\in L_2$.
For $x \in \Sigma^*$, define $\phi(x) =
\begin{cases}
a & \text{ if $T(x)$ accepts }\\
b & \text{ if $T(x)$ rejects }
\end{cases}$.
It is easy to check that $\phi$ is a mapping reduction from $L_1$ to $L_2$.
If $L_2 = \Sigma^*$ then $L_1 \in R$ and $L_2 \in RE$ does not imply $L_1 \le_m L_2$.
This can be seen, e.g., by choosing $L_1 = \emptyset$.
If $L_2 = \emptyset$ then $L_1 \in R$ and $L_2 \in RE$ does not imply $L_1 \le_m L_2$.
This can be seen, e.g., by choosing $L_1 = \Sigma^*$.


Why is addition in GF(2^8) the same as XOR?

Finite fields are usually described as polynomials over the base field (in this case $GF(2)$) modulo some irreducible polynomial. If you represent each polynomial as a vector of coefficients, then addition of polynomials corresponds to elementwise addition of the coefficients, which in the case of $GF(2)$, translates to XOR.

For example, suppose that your field elements are $1+x^2$ and $x+x^2 + x^5$. Their binary representations are $101$ and $100110$ (LSB is the coefficient of $1$). Their sum is $1+x+2x^2+x^5 = 1+x+x^5$ (since $2=0$ over $GF(2)$), whose binary representation is $100011$. This is the XOR of $101$ and $100110$.


How does automated verification of systems with infinitely many states work?

Infinite-state system verification is indeed a rather broad topic. First of all, all computers used nowadays can only have a finite number of states, as the amount of RAM is fixed. But that's is mainly a matter of terminology -- any verification technique that needs to iterate over all possible states is doomed from the beginning due to computation time.

Also note that you used "verification" in your title, and "to validate" in your question. These are different concepts that should not be confused. I will assume that you meant "verification".

To solve a verification problem with a large number of states, one typically constructs a proof of correctness of some sort. Such proofs do not need to refer to all possible states, rather they group sets of states by constraints that they satisfy. The description of the constraints can indeed by small, so that in the end we get a small proof.

For example consider the following function:

int comp(int parameter) {
    int p=parameter;
    if (p<0) {
        return p*p;
    } else {
        return p;
    }
}

We want to verify that the function comp never returns a negative number. If "int" is an arbitrary-length integer datatype, this program can already have an infinite number of states. To verify this program, we can perform a case split on whether "parameter" is negative or not, and then apply basic mathematical rules that we assume the integer data type to follow. What we get is a small correctness proof for an infinite-state system.

When researchers say that they work on infinite-state verification, they typically mean that they work of verifying systems in some type of modelling framework that allows to express systems with an infinite number of states - this does not mean that they can verify arbitrary such systems and their techniques are typically sound, but not complete.


You're both wrong.  It should be $10^{50} \times (10+50)^{200}$.  If you have $k$ objects, and there are $n$ possible places for each, there are $n^k$ possible combinations of ways for where to put each of them.

This probably doesn't really change the main point that I suspect the AI book was making: there are a lot of possible states, far too many to iterate over one by one.


How many languages exist with input alphabet {0,1} and all strings in the language have length less than or equal to 5?

First, you seem to have missed the empty string, so there are actually 63 possible strings. In any language, each of the 63 strings could either be in or not in the language, so there will be a total of $2^{63}$ different languages. In the jargon, that's a BFN.


Minimum cost max flow network problem with an alternative flow cost

This is sometimes called the minimum edge-cost flow problem or fixed-cost flow problem. As you suspected, it is indeed NP-hard, even when the network is bipartite. It is listed as problem ND32 in the list of NP-hard problems by Garey and Johnson:

M.R. Garey, D.S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York, 1979.

An approximation algorithm is discussed here:

S.O. Krumke, H. Noltemeier, S. Schwarz, H.-C. Wirth, R. Ravi. Flow Improvement and Network Flows with Fixed Costs. In Operations Research Proceedings 1998: Selected Papers of the International Conference on Operations Research Zurich, p. 158--167, Springer, Berlin, 1998.

The idea is to solve a standard linear-cost flow problem in which edge capacities are unchanged, but the cost of one unit of flow along edge $e$ is defined to be the edge weight divided by the edge capacity. This will give a solution that may weigh up to $F$ times the weight of the optimal solution, where $F$ is the flow value; but it will not weigh more than that.

If the approximate solution is not good enough, you might want to resort to an ILP solver.


Can a deterministic language be accepted by a deterministic Push Down Automaton?

Sure, a deterministic language can trivially be accepted by a nondeterministic PDA. Simplest way to see it is that a deterministic PDA is just a special case of the non-deterministic one. If that isn't enough, for some transition

$\begin{align}
   \delta(q, a, A) = \{(p, \alpha)\}
\end{align}$

you can add the following, without changing the language accepted
(the modified PDA isn't deterministic, it is enabled to do completely pointless $\epsilon$ moves):

$\begin{align}
   \delta(q, \epsilon, A) = \{(q, A)\}
\end{align}$


How is conditional jump implemented in the CPU?

The problem: to define conditional jump we need a conditional jump? I mean in order to evaluate an IF the processor has to evaluate condition and IF it's true, then jump, otherwise not. It's an endless recursion.

Processors have some level of code that is directly executed, by hardware circuits. That might not be the same level that they expose as their ISA, processors may translate ISA-level instructions into some other form before really executing them or even treat ISA-level instructions as small subroutines that are implemented in micro-code, but there is still some level is not interpreted in terms of something else and built into the physical structure of the hardware.
Below is a diagram of a simple processor. The "if" in the logic of "if we need to branch then take PC+offset as next PC, otherwise take PC+4" is implemented by the top left multiplexer (labeled Mux). A multiplexer does not actually "do one thing or the other", it combines two signals and a control signal via the formula: (~condition & a) | (condition & b). That's just a boolean formula that can be implemented easily as a physical circuit.


This is the idea of probability amplification, in which one improves the probability of correctness of the algorithm by running it multiple times. You are talking about Monte-Carlo algorithms which have one-sided error. Lets take an example (from Wikipedia) having such a similar feature :

The Solovay–Strassen primality test is used to determine whether a
given number is a prime number. It always answers true for prime
number inputs; for composite inputs, it answers false with probability
at least 1/2 and true with probability at most 1/2. Thus, false
answers from the algorithm are certain to be correct, whereas the true
answers remain uncertain; this is said to be a (1/2)-correct
false-biased algorithm.

The probability that the above algorithm returns an incorrect answer is thus at most 1/2. Now, the key idea is to understand that successive runs of the algorithm produce answers that are independent of each other - hence, on running it twice, the probability that the algorithm returns an incorrect answer both times is at most $(\frac{1}{2})^2$. Thus, after $k$ iterations, the probability of an incorrect answer reduces to at most $(\frac{1}{2})^k$. Thus, if we adopt the scheme that the algorithm returns false if the any of the first $k$ runs give an output of false, else return true, then the probability that our scheme returns an incorrect answer is at most $1 - (\frac{1}{2})^k$, which can be driven down to $0$ for large values of $k$.


Finding lower bounds for data structures with non-standard interfaces

Data structure lower bounds is a full-fledged area in theory of computation. The main model of computation on which the lower bounds are proved is the cell probe model, which counts the number of memory accesses, but for which computation is free. For an overview of how things stood in 2008, you can take a look at Mihai Pătraşcu's thesis. Tragically, Pătraşcu died from brain cancer in 2012 at the age of 29.


Looping through random integers - will it halt with probability 1?

For deterministic algorithms, the statement "Algorithm $A$ halts on input $x$" is well defined. However, when $A$ is randomized (i.e. has access to some random source during its computation) this question becomes meaningless, as you need to know what was the outcome of the random source in order to answer it.

You can ask "does $A$ always halt on $x$", i.e. does it halt for every possible output of the random source. In your case, assuming the source produces uniformly distributed elements in the given range, the answer is no, since e.g. the infinite sequence "444..." is a possible outcome of the source, and this will cause $A$ to never halt.

However, "Algorithm $A$ halts on input $x$" is now an event, i.e. it is a subset of your sample space (we associate this event with the set of random outputs who cause $A$ to halt). Events have probabilities, so you can ask "What is the probability that $A$ halts on $x$"? If your source is uniform, then the probability that your algorithm doesn't halt is $p=\prod\limits_{i=1}^\infty\left(\frac{99}{100}\right)^i=0$. So in your case it is correct to say that the algorithm halts with probability $1$, but it is incorrect to say it always halts.

As for whether or not the randomness source matters, the answer is definitely yes. Consider the source which first chooses a number from the range uniformly at random, and then remembers it and outputs it to you in any later request (i.e. the source has memory, and different outcomes are not independent). In that case, your algorithm does not halt with probability $\frac{99}{100}$. For a source which always outputs $5$, it is true to say the the algorithm always halts (and not only with probability $1$, which is a weaker statement).


Just elaborating what @Lamine pointed out : When $k$ is part of the input, $k$ can be as large as $\frac{n}{2}$, in which case the number of potential clique sets are $\binom{n}{\frac{n}{2}}$ which is at least $\left( \frac{n}{\frac{n}{2}} \right)^{\frac{n}{2}}$. Hence your naive algorithm would take time $2^{\frac{n}{2}}$ which is clearly exponential in input length $|x|+|k|=n+\log n$. The parameterized version $G(n,k)$ where we are looking for $k$-cliques in an $n$-vertex graph captures the hardness of the problem in its most generalized form because $k$ is part of the input. Hence a poly-time algorithm for $G(n,k)$ would also imply a poly-time algorithm for any specific $k$.


Classification algorithm for high dimensional data which is uniquely definable in a very small sub-space

Since your data are extremely sparse, using GMMs or a traditional SVM will result in an over-fit model. By employing methods that exploit the sparsity of the structure, you should get much better results. Regression methods typically add some penalty function as a measure of the amount of non-zero values. This is usually referred to as "regularization". Doing this exactly (under the $L_0$ norm) is difficult, so relaxations are used (lasso: $L_1$, ridge: $L_2$).

If you are comfortable with Python, SciKit Learn has implementations for several approaches that utilize either lasso or ridge penalties. Here is an example of Lasso penalty for an SVM model. I would try that and see how well it works. It may require a parameter to adjust the regularization amount. You can do cross-validation to find what parameter works best.


Thoughts on definition for disadvantage of concurrent processing?

I'm studying for the same A Level and have found that deadlock, starvation, race conditions and the overhead affiliated with coordinating simultaneous threads are reasonable, in-depth disadvantages of concurrent processing

Deadlock occurs when each process/thread is waiting for another to finish (meaning that no process is ever able to complete). For example, this happens with cyclic dependencies (e.g. when process A needs B which needs C which needs A).

Starvation is when a process is always denied a resource that it needs, resulting in the process never completing.

Race conditions are when two processes are sharing the same storage location (i.e. variable) and the result of operations depends on the order in which they are ran.

Overhead - there is additional processing overhead to coordinate the individual threads (and combine their results). This can mean, for some problems, a single thread is more efficient than multiple.

Hope I've helped clarify things for anyone who was also confused with this topic,

Josh

Sources:

Cambridge Elevate OCR A Level Textbook

Rensselaer Polytechnic Institute Lecture Notes


I am a little bit confused about how to calculate the memory capacity

This formula assumes that memory is word-addressable rather than byte-addressable. The number of words that can be addressed is $2^n$. If you want to convert this from words to bytes, you can use the formula (in which word stands for the word size in bits). If you want to convert it to kilobytes, for example, you need to multiply by the word size in bits, and divide by $8192$. And so on. Come up with your own formulas!


The theory behind backpropogation, gradient calculation

The gradient, just like the derivative, is linear: for functions $f,g$ on the same variables and scalars $\alpha,\beta$:
$$
\nabla(\alpha f + \beta g) = \alpha \nabla f + \beta \nabla g.
$$


We will be using the following definitions:

  Let $f\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ be a function mapping positive integers to positive integers.

  The class $O(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C>0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \leq Cf(n)$.

  The class $\Omega(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $c>0$, for all $n \in \mathbb{Z}_+$ we have $g(n) \geq cf(n)$.

  The class $\Theta(f)$ consists of all functions $g\colon \mathbb{Z}_+ \to \mathbb{Z}_+$ such that for some real $C,c>0$, for all $n \in \mathbb{Z}_+$ we have $cf(n) \leq g(n) \leq Cf(n)$.

  We also write $g(n) = O(f(n))$ instead of $g(n) \in O(f(n))$, and similarly for the other two.

These are equivalent to the more standard definition in which the above only has to hold for large enough $n$. You can also carry out the proofs below using the standard definitions — this entails only small changes.

Let's start with the second statement: $f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$.

Suppose that $f(n) = \Theta(g(n))$. Then there exist $C,c>0$ such that for all $n$ we have $cf(n) \leq g(n) \leq Cf(n)$. Therefore for all $n$ we have $C^{-1} g(n) \leq f(n) \leq c^{-1} g(n)$, and so $g(n) = \Theta(f(n))$. Similarly, if $g(n) = \Theta(f(n))$ then $f(n) = \Theta(g(n))$.

Now let us go back to the first statement: $O(f(n)) = O(g(n))$ iff $\Omega(f(n)) = \Omega(g(n))$ iff $\Theta(f(n)) = \Theta(g(n))$.

Suppose that $O(f(n)) = O(g(n))$. It is easy to check that $g(n) = O(g(n))$ (take $C = 1$), and so $O(f(n)) = O(g(n))$ implies that $g(n) = O(f(n))$. That is, there exists $D>0$ such that $g(n) \leq Df(n)$ for all $n$. Similarly, $f(n) = O(g(n))$, and so there exists $E>0$ such that $f(n) \leq Eg(n)$ for all $n$. Suppose now that $h(n) = \Theta(f(n))$. Then there exist $C,c>0$ such that $cf(n) \leq h(n) \leq Cf(n)$ for all $n$. This implies that $cD^{-1} g(n) \leq h(n) \leq CEg(n)$, and so $h(n) = \Theta(g(n))$. Similarly, if $h(n) = \Theta(g(n))$ then $h(n) = \Theta(f(n))$, and so $\Theta(f(n)) = \Theta(g(n))$.

Similarly, if $\Omega(f(n)) = \Omega(g(n))$ then $\Theta(f(n)) = \Theta(g(n))$.

Conversely, if $\Theta(f(n)) = \Theta(g(n))$ then, as before, $f(n) = \Theta(g(n))$. This means that there exist $C,c>0$ such that $cg(n) \leq f(n) \leq Cg(n)$ for all $n$. Now suppose that $h(n) = O(f(n))$. Then there exists $D>0$ such that $h(n) \leq Df(n)$ for all $n$. Since $h(n) \leq Df(n) \leq DCg(n)$, we see that $h(n) = O(g(n))$. Similarly, if $h(n) = O(g(n))$ then there exists $E>0$ such that $h(n) \leq Eg(n)$. This implies that $h(n) \leq Ec^{-1} f(n)$, and so $h(n) = O(f(n))$. Thus $O(g(n)) = O(f(n))$. Similarly, $\Omega(g(n)) = \Omega(f(n))$.


Looks right to me in the following convention:
$S_n = \sum_{k=1}^{n} \Theta(1/k)$ is convenient notation for

There is an $f(x) \in \Theta(1/x)$ (as $x \to \infty$) such that
$S_n = \sum_{k=1}^{n} f(k)$.

Thus the $c_i$ (or with the notation in this answer $c_k$) you get, are not really dependent on $k$.
Under this interpretation, it is indeed true that $S_n = \Theta(H_n)$.
In fact, in Jeff's answer, he shows that $T(k+1) = f(k) + T(k)$ where $f \in \Theta(1/k)$, so it is consistent with the above interpretation.
The confusion seems to be arising from mentally "unrolling" the $\sum$ and presuming different functions for each occurrence of $\Theta$...


In typical floating point implementations, the result of a single operation is produced as if the operation was performed with infinite precision, and then rounded to the nearest floating-point number.

Compare $a+b$ and $b+a$: The result of each operation performed with infinite precision is the same, therefore these identical infinite precision results are rounded in an identical way. In other words, floating-point addition is commutative.

Take $b + b + a$: $b$ is a floating-point number. With binary floating point numbers, $2b$ is also a floating-point number (the exponent is larger by one), so $b+b$ is added without any rounding error. Then $a$ is added to the exact value $b+b$. The result is the exact value $2b + a$, rounded to the nearest floating-point number.

Take $a + b + b$: $a + b$ is added, and there will be a rounding error $r$, so we get the result $a+b+r$. Add $b$, and the result is the exact value $2b + a + r$, rounded to the nearest floating-point number.

So in one case, $2b + a$, rounded. In the other case, $2b + a + r$, rounded.

PS. Whether for two particular numbers $a$ and $b$ both calculations give the same result or not depends on the numbers, and on the rounding error in the calculation $a + b$, and is usually hard to predict. Using single or double precision makes no difference to the problem in principle, but since the rounding errors are different, there will be values of a and b where in single precision the results are equal and in double precision they are not, or vice versa. The precision will be a lot higher, but the problem that two expressions are mathematically the same but not the same in floating-point arithmetic stays the same.

PPS. In some languages, floating point arithmetic may be performed with higher precision or a higher range of numbers than given by the actual statements. In that case, it would be much much more likely (but still not guaranteed) that both sums give the same result.

PPPS. A comment asked whether we should ask if floating point numbers are equal or not at all. Absolutely if you know what you are doing. For example, if you sort an array, or implement a set, you get yourself into awful trouble if you want to use some notion of "approximately equal". In a graphical user interface, you may need to recalculate object sizes if the size of an object has changed - you compare oldSize == newSize to avoid that recalculation, knowing that in practice you almost never have almost identical sizes, and your program is correct even if there is an unnecesary recalculation.


I think what you want is impossible to do without further assumptions on F.

Consider the following, rather simple data stream for a target data length of 5:

123441233512245113451255513555 ...

Note that not a single block contains 12345 (our original data). In order to find a proper combination of data parts, you would have check all combinations, in general. What is the probability that some combination other than 12345 is accepted by F? And this is on a stream without lost or corrupt symbols and ignoring the problem of overlaps between blocks which might by accident be valid data!

Therefore, I think keeping a buffer of size $N$ and running F in every time step is the best you can do. Note that you can skip evaluation of F if there is a corrupt symbol in the buffer (provided you can identify those). You still have the problem of overlap errors and wrong valid blocks, though.

You have more potential if F has nice properties, for example if it is able to identify valid parts of data. Then you can store only maximal valid parts and piece those together. Also, formatting the data stream can help; a simple example would be markers for the beginning of a data block (that would get rid of problems with overlaps and reduce the amount of calls to F). Furthermore, usual assumptions such as "error probability is small" can make waiting for a full valid copy of the data viable; many protocols break down if virtually every other symbol is corrupt.

All these are not new problems. I suggest further reading on

error detection and correction codes,
codes in general and
communication protocols.


Why are not programs already in binary code?

The short answer to your question is "for productivity and portability".

Let me expand on this. The very first generation of computers were indeed programmed directly in binary, either by entering each binary instruction using physical switches on the computer itself or by some simple bulk loading mechanism such a reading and loading instructions from a paper tape. This was first generation programming (although at the time it was just called "programming").

Programmers soon realised that it would be simpler and quicker to write programs use mnemonics instead of binary instruction codes. So instead of having to remember or look up the binary code for "load the next byte into register A", they could use the mnemonic "LDA". Translating mnemonics into binary instructions required a program called an assembler. Once someone had invested the time and effort into writing an assembler on a particular computer, programs could be written in mnemonics or "assembly language". This was much quicker than working out all the binary codes for yourself, and it also made it much easier to debug and update programs. This was second generation programming.

As more and more programs were written on different machines, programmers realised that the underlying concepts of programming were similar, regardless of which type of computer the program was being written for. Programmers would be even more productive if they could use a language that implemented concepts like variables, loops, case statements and sub-routines. It would also be convenient to be able to write complex instructions like "print the following string of characters to the screen" or "multiply A+1 by B+2, divide the result by C and store the final result in a variable called D" in one line of code instead of multiple assembly language instructions. So programmers invented higher-level languages such as FORTRAN and BASIC (and eventually C and Java) and wrote compilers and interpreters which would translate code written in a higher level language into assembly language instructions or directly into binary instructions. Not only did this make programmers even more productive, but also by creating compilers for different types of computer, the same FORTRAN program could be translated and run on different computers. So programs became portable and programmers did not have to learn lots of different different assembly languages. This was third generation programming.

Mainstream development in programming languages and computer architectures have continued in this direction, with more and more layers of abstraction between the languages that programmers write in and the machine code instructions that a CPU executes directly. Programming languages have become more specialised, with languages specifically designed for implementing user interfaces; processing data in large databases; creating management information reports; running simulations; processing graphics; developing video games etc. Developments in computer architecture design have concentrated on running a relatively small, simple and general set of machine code instructions more rapidly. Increasing CPU speeds and falling memory costs mean that it is more cost effective to translate each line of high level language into hundreds of machine code instructions than it would be to develop more complex CPUs that could execute higher level language code more directly.


Find point with smallest average distance to a set of given points

This point is known as the geometric median, also known as the 1-median.

Apparently, there is no simple algorithm for computing the geometric median.  Instead, one must use some kind of numerical approximation.  Wikipedia mentions Weiszfeld's algorithm, which appears to be a kind of iterative descent algorithm, and cites other more sophisticated algorithms.

This is a special case of the Weber problem, a facility location problem.  Standard solvers for facilitation location problems be able to compute the geometric median for you, by framing this as an instance of the Weber problem.


Suffix array construction algorithm linear complexity constant

Constants like this are generally not calculated for the run time of algorithms, because it's not clear what they would count - would they count the number of some sort of primitive C operation executed, or the number of x86-64 operations, or the number of arm64 operations, or the microcode operations, or ...?

More frequently than calculating the constants, people measure the run time and show the $\alpha$ that fits best. They will also sometimes calculate the number of times a specific operation is executed, like comparisons or swaps in a sorting algorithm.


Asymptotic growth of a function containing a sum

There is an explicit formula for $\sum_{i=0}^n i^3$, but even without it, you can estimate
$$
\int_0^n x^3 \, dx \leq \sum_{i=0}^n i^3 \leq \int_1^{n+1} x^3 \, dx.
$$
Since $\int x^3 \, dx = x^4/4$, this shows that the sum is very close to $n^4/4$, and in particular is $\Theta(n^4)$.

(The explicit formula states that the sum equals $n^2(n+1)^2/4$.)


Are chaotic systems computable in polynomial time

Wolfram's rule 30 is a one dimensional cellular automaton.
If you want to know the state of the CA at step $t$, given the initial configuration, you just need to run the rule for $t$ steps. At every step the computation consist in no more than a bunch of if's, so the time complexity of such  CA is linear in $t$.


Clarification on Solving Recurrence Relations (Linear)

The first step is to solve the easier recurrence
$$
T(n) = T(n-4) + T(n-10).
$$
This is explained in our reference question. The solution to your recurrence will likely be larger by a factor of $\log n$, roughly speaking.

Indeed, you can consider a recursion tree in which the root is $n$, and a node $m$ has children $m-4$ and $m-10$ (you stop the recursion at some constant $m$). The solution to the recurrence $T(n) = T(n-4) + T(n-10)$ is proportional to the number of leaves, which we expect to be proportional to the number of nodes. For all $m \geq \sqrt{n}$ (say), $\log n = \Theta(\log m)$, which leads us to expect that the solution of your non-homogeneous recurrence is larger by a factor of $\log n$ than the solution of the corresponding homogeneous recurrence $T(n) = T(n-4) + T(n-10)$.

The preceding paragraph contains some intuition which will need to be proven. But whether or not the $\log n$ factor appears in the final formula makes little difference, since the growth rate of the recurrence is exponential.


How to reduce this regular expression into DFA

What can be done so that this regex can be converted to DFA easily?

Algorithmic methods are doomed, if you insist on a DFA. Your regular expression contains about sixty characters. Roughly speaking, any procedure for converting to an automaton is going to produce at least one state per character of the regular expression. That means you're going to end up with an automaton with at least sixty states, and it's probably going to be nondeterministic. Determinizing that naïvely is going to give you $2^{>60}$ states, which isn't quite as many as the number of atoms in the earth, but it's still an unmanageably huge number.

Do you really need a DFA? If, for example, you're trying to write a program that will accept strings that match this regular expression, it's straightforward to check if an NFA accepts a particular string: just scan along the string keeping track of the set of states the automaton could be in after each successive character. For a fixed automaton, this can be done in linear time.

If you do need a DFA, you're going to have to figure out what the regular expression does. Break it into chunks.  $(a(aa|b)^∗ab|b)$ matches $b$, along with all strings that have an even number of $a$s, begin with $a$ and end $ab$. It's not too difficult to see that this language is matched by the following automaton (I've omitted a trap state that's reached if any character is read from state $q_3$):

If you stare at that for a moment, you'll realise that states $q_0$ and $q_2$ are the same (both say "if $a$, go to $q_1$; else, go to $q_3$") so we can reduce the automaton to the following.

You could also use algorithmic state-minimization techniques to avoid having to notice things like this.

You can probably produce similar automata for the various "top-level" chunks of the regular expression, and chain them together to get a DFA for the whole thing.


HeapSort: A procedure which sorts an array in place.

Can be in-place or not in-place, the point is it's using a heap data structure to help sort.

Building heap is linear with a careful analysis

See more here


Assign undirected edges in a mixed graph to make graph cyclic/acyclic

As noted by R B, the acyclic variant of the problem is solvable iff the directed part of the graph is acyclic, in which case one can take a topological sort of the directed edges, and orient undirected edges consistently with the linear order obtained.

For the cyclic variant of the problem, we can use the following polynomial-time algorithm, where $G=(V,E)$ is the input graph:

for every directed edge $e=(a,b)\in E$, and for every orientation $(a,b)$ of an undirected edge $e=\{a,b\}\in E$:

if there is a path (directed where applicable) from $b$ to $a$ in $(V,E\smallsetminus\{e\})$:

find such a path $p$
make sure the path is simple by deleting subcycles
output any orientation of the undirected edges that agrees with the cycle $e,p$ and stop

if no edge worked, reject

Note that the simplicity of $p$ in particular ensures that no undirected edge appears twice in $e,p$, hence it gives a consistent orientation. Thus, if the algorithm accepts, it is correct. On the other hand, if there exists an orientation of $G$ that includes a (wlog simple) cycle $c$, and $e=(a,b)$ is any edge in $c$ (properly oriented), then $a$ is reachable from $b$ in $(V,E\smallsetminus\{e\})$ by means of the rest of the cycle. Thus the algorithm will accept sooner or later.

In terms of complexity, both problems are NL-complete as decision problems, and the search problem versions are in FNL.


Here's a general technique on linear recurrences that's useful to know. Observe that:

$$
\begin{bmatrix}
T(n) \\
T(n+1)
\end{bmatrix} =
\begin{bmatrix}
0 & 1 \\
2 & -1
\end{bmatrix}^{n}
\begin{bmatrix}
2 \\
5
\end{bmatrix}$$

If we can perform an eigendecomposition of $M$:

$$M = Q \Lambda Q^{-1}$$

where $\Lambda$ is a diagonal matrix, then:

$$M^n = Q \Lambda^n Q^{-1}$$

Raising a diagonal matrix to a power is trivial. This gives you a closed form for $M^n$.

In your case:

$$\begin{bmatrix}
0 & 1 \\ 2 & -1
\end{bmatrix} =
\begin{bmatrix}
-\frac{1}{\sqrt{5}} & \frac{1}{\sqrt{2}} \\
\frac{2}{\sqrt{5}} & \frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix}
-2 & 0 \\
0 & 1
\end{bmatrix}
\begin{bmatrix}
\frac{-\sqrt{5}}{3} & \frac{\sqrt{5}}{3} \\
\frac{2\sqrt{2}}{3} & \frac{\sqrt{2}}{3}
\end{bmatrix}$$

So:

$$
\begin{bmatrix}
T(n) \\
T(n+1)
\end{bmatrix} =
\begin{bmatrix}
-\frac{1}{\sqrt{5}} & \frac{1}{\sqrt{2}} \\
\frac{2}{\sqrt{5}} & \frac{1}{\sqrt{2}}
\end{bmatrix}
\begin{bmatrix}
-2 & 0 \\
0 & 1
\end{bmatrix}^n
\begin{bmatrix}
\frac{-\sqrt{5}}{3} & \frac{\sqrt{5}}{3} \\
\frac{2\sqrt{2}}{3} & \frac{\sqrt{2}}{3}
\end{bmatrix}
\begin{bmatrix}
2 \\
5
\end{bmatrix}$$

Multiplying the matrices together, taking the top row, and simplifying gives:

$$T(n) = 3 - (-2)^n$$

It's a lot of work (if you don't have a computer algebra system handy), but it always gives an answer if the system is linear and diagonalisable.


Grammars and Parsing: Ambiguity in Sequences

This parser state

KEYWORD DECVAL DECVAL
               ^
               |---------- Lookahead

is not a conflict because a shift action is not possible. There is no production in which A DECVAL follows another DECVAL. There is not even a production in which a VALUE follows another VALUE. Before the lookahead DECVAL can be shifted, the DECVAL at the top of the stack must be reduced to something which can be followed with DECVAL.


Relation between witness and problem statement

Consider a problem named 3SAT_NORM which is a version of 3SAT restricted to instances wherein the number of literals used is equal to the number of clauses. For 3SAT_NORM, every input of $n$ clauses requires the witness to give $n$ values for the satisfying assignment. Thus, you can't simply limit the size of the witness and relate the difficulty of the new problem -- the witness size is a function of the instance size.

But, you could conceive of a different witness than the usual one for 3SAT_NORM. You could take a convention where if the witness to 3SAT_NORM only defines some subset of the literals, then the other ones are automatically assumed by convention to be given an assignment of "true".

Now, suddenly, we can limit the size of the witness and make observations about the relationship -- in particular, restricting our witness to be smaller is the same as restricting 3SAT_NORM to include only formula where satisfying assignments are guaranteed to have a lot of "true" values.

What I'm trying to get at is the witness is a property of a solution to the problem, not a property of the problem itself. SAT and subset sum seem to have "natural" witnesses, but there still could be other witnesses and some problems may have witnesses that are less natural. Some witnesses can be restricted in size, and others can't.

With this in mind, there is still one major observation we can take in mind. If we limit witnesses to size $f(n)$ then there are only $2^{f(n)}$ possible witnesses so for small functions $f$ we can simply evaluate each possible witness to see if it works. In other words, by looking only at small enough witnesses, the problem is easy. This means if witnesses to inputs of size $n$ are guaranteed to be $log(n)$ in size, then the original problem can be solved in pseudo-polynomial time, and if the witnesses are guaranteed to be constant size then the original problem can be solved in polynomial time.


Find the average number of steps to sort an array by randomly selecting two elements

The average number is hard, an upper bound isn’t.
You have n numbers, therefore n(n-1) / 2 pairs of numbers. On average half of those pairs are in the wrong order. You need to figure out the distribution for that.
Now if you have k pairs in the wrong order, the probability of picking two random numbers in the wrong order is 2k / n / (n-1). If you pick two numbers in the wrong order and exchange them, the number of incorrectly ordered pairs goes down at least by one. So you expect n(n-1)/2k picks to go from k inversions to k-1 or fewer. (The “fewer” makes it hard to analyse).


Programming languages for genetic engineering

I choose to reply in an answer rather than a comment because I think
that is actually the proper answer to your question (and it is too
long for a comment anyway).

Style

If you intend to do research and write papers for an audience, then
you should learn to be easy to read. Any improvement costs only once
to you, and saves time and energy to each one of your readers. That
includes giving web references that  can be clicked, rather than
having to be cut and pasted in a browser window. That also include
briefly telling your readers what the reference is about, so that
they do not have to jump into unknown territory. (this is a comment on
the original version of your question, before the friendly editing of
David Richerby).

The same is actually true for programs. It is not enough to write a
program that solves the problem, you should also make sure that it is
easy to understand and to use, so as to spare aggravation to your
users.
Substance

Getting a Ph.D entails doing a fair amount of research. The very
first step is to find litterature that is relevant to your research
topic. Usually, if you choose the topic, you are supposed to have
some knowledge of it. In your case, you know of a project that is
relevant.  So that gives you names, keywords, and topics to search for on the
web. Then some reading of that should give you a better
understanding, increase your competence and allow you to search for
more ... and find research groups that do that kind of work by
looking at the authors of papers. Their affiliation is usually given,
and many have a web site.

Doing this yourself will increase you general competence at doing
research, and also increase your knowledge of the field. It is in no
way wasted work. Doing if for you is not doing you a service. You
would not think of getting someone on the net to write your
dissertation for you. Of course, it does make sense to discuss issues
and ask questions, but usually after doing what work you can, so as
to spare the time of colleagues ... they do not have so much available.

But if you cannot do it yourself, you probably do not have the
maturity to do research and you should rather consider another
academic path, or professional path.


Estimating P in Amdahl's Law theoretically and in practice

Amdahl divided a program in two parts, serial and parallel, and assumed each processor to have same compute ability. This concept has been further refined by Hill and Marty Amdahl's law in multi-core era, in other words it is not necessary that every processor should have same the compute ability and Cassidy Beyond Amdahl's Law: An Objective Function That Links Multiprocessor Performance Gains to Delay and Energy, in other words why divide in only two parts.

After a brief overview of Amdahl's law, I answer the question how to measure the serial (1-P) and parallel (P) parts of a program.

Static instrumentation: Put a function that gives the current time like gettimeofday in Linux at the start of the program, the point where you create threads and points where you join threads and if necessary (if your program does a lot of post processing) at the end of program. Take differences and you will have the P value. Use the single threaded program. If you want to have more precision in measurement use the rdtscp instruction on Intel processors Excellent blog by Dr. John McCalpin.
Dynamic instrumentation: It is possible to do the above even when you don't have the source code to do static instrumentation. You can use library preloading (LD_PRELOAD) or the Intel Pin tool Introduction to Pin using examples or similar dynamic binary instrumentation tools like Dynamorio, Valgrind and Linux perf Tutorial by Brendan gregg. All of them are established frameworks, completely free, with multiple research tools using them.


Forward edges in undirected graph using BFS

My example was a multigraph (multiple edges between a given pair of vertices is allowed). And in multigraph BFS does "produce" forward edges!


What are the rules for positive recursive types in dependent type theory?

Why are recursive types seldomly seen in dependent type theory?

The point of inductive types is precisely that you get normalization. Unrestricted recursive types simply lead to non-normalizing terms.

Given any type $A$, we may inhabit $A$ with a non-normalizing term as follows. Consider the recursive type
$$D = D \to A.$$
The term $\omega \mathrel{{:}{=}} \lambda d : D . d \; d$ has type $D \to A$ and it also has type $D$, since they are equal. Therefore $\omega \; \omega$ has type $A$, and in addition $\omega \; \omega$ reduces to itself, giving a non-normalizing term.

If instead of $D = D \to A$ we have just $D \cong D \to A$ then an easy adaptation of the above argument leads to the same conclusion. You just have to coerce $d$ to have type $D \to A$.

Is this bad? If you're using type theory to write programs then it probably isn't that bad. It's actually kind of cool. But if you're using type theory to do reasoning, i.e., you want ot use types as propositions, then it's bad because every type has an inhabitant and so every propostion has a proof. It just depends on what you want from type theory.

What are the rules for recursive types?

$\newcommand{\Type}{\mathsf{Type}}$
Let us try to formulate the rules for recursive types. A reasonable attempt goes along the same lines as what you've suggested:
$$\frac{\Gamma, X : \Type \vdash F(X) : \Type}{\Gamma\vdash \mu X . F(X) : \Type}$$
$$\frac{\Gamma \vdash e : F(\mu X . F(X))}{\Gamma \vdash S(e) : \mu X . F(X)}$$
$$\frac{\Gamma, y : \mu X . F(X) \vdash C(y) : \Type \qquad
  \Gamma, x : F(\mu X . F(X)) \vdash f(x) : C(S(x)) \quad
  \Gamma \vdash u : \mu X . F(X)
}{\Gamma \vdash \mathsf{rec}_F([x . f(x)], u) : C(u)}$$
We shouldn't forget to ask about equations that we expect to hold. The $\beta$-rule would be
$$\mathsf{rec}_F([x . f(x)], S(e)) = f(e)$$
and let us throw in an $\eta$-rule
$$S(\mathsf{rec}_F([x . x], u)) = u.$$
The $\eta$-rule says that if we take apart $u : \mu X . F(X)$ and put it back together, we will get $u$.
So far we have a map $S : F(\mu X . F(X)) \to \mu X . F(X)$, but we also want $R : \mu X . F(X) \to F(\mu X . F(X))$ together with
$$S(R(u)) = u \qquad\text{and}\qquad R(S(e)) = e \tag{1}$$
These say that $S$ and $R$ form an isomorphism between $F(\mu X . F(X))$ and $\mu X . F(X)$. We can get such an $R$, namely
$$R \mathbin{{:}{=}} \lambda y : F(\mu X . F(X)) . \mathsf{rec}_F([x . x], y).$$
Indeed, we have by the $\beta$-rule
$$R(S(e)) = \mathsf{rec}_F([x . x], S(e)) = e$$
and by the $\eta$-rule
$$S(R(u)) = S(\mathsf{rec}_F([x . x], u) = u.$$

We could have started with having $S$ and $R$ satisfying equations (1), and that would allow us to derive the eliminator as
$$\mathsf{rec}_F ([x . f(x)], u) = f(R(u)).$$
Such an eliminator satisfies the $\beta$-rule and the $\eta$-rule, quite obviously. This should give us pause. We discovered that our rules say precisely that $\mu X . F(X)$ is isomorphic to $F(\mu X . F(X))$ and nothing else. This is not good, because the rules should fix the meaning of $\mu X . F(X)$ up to equivalence of types.

To see that the rules are no good, consider the case $F(X) = X$. Every type is a fixed point of $F$, and our rules say nothing about which one $\mu X . X$ should be. Indeed, we can take an arbitrary type $A$ and set $R$ and $S$ to be the identity maps. That will satisfy all the rules for $\mu X . X$.

We should somehow state which fixed point of $F$ we have in mind when we write down $\mu X . F(X)$. a reasonable choice would be to ask for the smallest or initial one. But what does that mean? In category theory it means that there is a unique homomorphism from the algebra $S : F(\mu X . F(X)) \to \mu X . F(X)$ to any other $F$-algebra. Here we rely on the fact that $F$ is a functor so that we can reasonably talk about $F$ applied to a map. But our $F$ is not going to be a functor in general because it might break covariance (try to extend $F(X) = X \to X$ so that it takes $f : A \to B$ to some $F(f) : F(A) \to F(B)$ and you will see what the problem is). We are stuck, as we have no good criterion for picking one of possible fixed points of $F$!

The way out is to decompose $F : \Type \to \Type$ according to covariant and contravariant arguments,
$$F : \Type \times \Type^{\mathrm{op}} \to \Type.$$
For example $F(X) = X \to X$ becomes $F(X_1, X_2) = X_2 \to X_1$.  But now it's not clear what a fixed point of $F$ might be. All this leads to Freyd's notion of algebraically compact categories and a beautiful theory surrounding them. The theory can be applied to categorical models of programming languages to explain how recursive types work there. When we throw in dependent types, then as far as I know, things break and nobody knows what to do. But I would love to be proved wrong!

The sort of recursive types we spoke about here goes under the name isorecursive types. The other option are equirecursive types, see the same link.


Can truth tables be used in non-boolean algebra to derive functions?

There are two possible ways to define a non-boolean algebra.

Stick with $\mathbb{F}_2 = \{0,1\}$ but choose base operations other than $\{\land, \lor, \lnot\}$.
Change the base set entirely.

For the whole concept of simplification to word similarly to boolean algebra, we need two binary operations with associativity, commutativity and distributivity. Fields are the natural choice and, I think, the only one. Commutative rings might work but I suspect you get into trouble composing functions in a regular way if you don't have multiplicative inverse elements.

Infinite fields do not make sense here -- you can not draw an infinite table. So finite fields remain, of which there is exactly one per size (up to isomorphy).

So let us, for example, consider $\mathbb{Z}/5$ (the smallest field over $\mathbb{Z}$ with more than two elements and interesting inverses). Now try and formulate a function in a way that looks like a boolean function provided by Karnaugh maps, that is in additive (disjunctive) or multiplicative (conjunctive) normal form. We get to the core question:

  What is the complement of a given element in a non-binary algebra?

The simple logic "if it's not one it's the other" does not work here. Note that the boolean complement does not correspond to the additive nor the multiplicative inverse, so there no hope there. So let's try and define a "complement"; say $\overline{a} = a + 1$ (which contains the boolean complement as special case). We note with unease that this new complement is not symmetric. I expect symmetry to be of essence; reading off from the Karnaugh map seems to rely on it.

So there is no way to get there with an odd number of elements; let's pick one with an even number (so we can pair elements for a complement relation). Now things become messy and I'll stop. After all, Wikipedia says that (emphasis mine)

  the solution can be found by eliminating extra variables within groups using the axioms of boolean algebra

which characterise boolean algebra. Therefore -- provided that all axioms are needed for Karnaugh maps to work -- the concept does not work for non-boolean algebras.


Question about spanning trees and creating them through BFS and/or DFS algorithms

If you get to pick, each time, an ordering of the vertices, then statement is trivially true - just choose the ordering that gives that tree, but this is not interesting.

Assuming the vertices do have some fixed order (so the DFS/BFS can't arbitrarily pick which vertex it has to choose next), then statement is false. We can see this via a simple counting argument. As the ordering is fixed, the DFS/BFS produces a unique spanning tree for each starting vertex, i.e. we can produce at most $n$ spanning trees (per algorithm), where $n$ is the number of vertices in the graph.

However if our input graph is $K_{n}$ with $n > 3$ (the complete graph on $n$ vertices), the graph has $n^{n-2}$ spanning trees, clearly far more than what we can produce from the DFS/BFS.


You have asked two questions. I will answer them one by one.

Choosing the seed. The usual approach here is to choose the seeds randomly once and for all, and to hard-code them. If the hash family is reasonable, then all small sets of seeds should look "the same". I don't know the Murmur3 family, but it's probably reasonable enough.

Note that linear dependence is not the correct measure here — you want a $k$-tuple of hash values generated from $k$ different seeds to look like a random $k$-tuple of values, either statistically or computationally. Linear dependence is just one possible wrong thing that could happen.

Limiting the hash domain. If the modulus isn't a power of 2 then the resulting value wouldn't be uniform, but usually it will be "close enough" to uniform, particular with respect to the performance of a Bloom filter. Indeed, it is standard practice to generate a random number in a range $\{0,\ldots,m-1\}$ by taking a random 32-bit or 64-bit value modulo $m$.

In the specific case of Bloom filters, if you know that every value in $\{0,\ldots,m-1\}$ appears with probability in the range $[c/m,C/m]$ then you can adjust the analysis of the Bloom filter to see what you get. You can then calculate $c,C$ in your case (exercise) and choose parameters for the Bloom filter accordingly. You will probably find out that in most cases the parameters you get by assuming $c=C=1$ are very close to the ones that you get by taking into account the actual $c,C$.


In a simple computer architecture with a single active CPU connected to RAM and other passive peripherals by a bus, then there is a timing signal (typically produced by a quartz oscillator) that synchronises the internal operation of the CPU. This clock signal is the system clock.

There may also be a separate timing signal that synchronises the activities of writing to and reading from the bus. This is the bus clock. Because the speed at which data can be reliably transmitted across the bus may be lower than the internal speed at which the CPU runs, the bus clock signal is usually at a lower frequency than the system clock. The bus clock signal may be produced by passing the higher frequency system clock signal through a frequency divider.

In more complex architectures, where there are multiple active components (CPUs, FPUs, graphics cards, memory controllers, I/O controllers) running at different speeds, then the bus clock is often the fundamental synchronising signal, and each component then multiplies the frequency of the bus clock signal by a specific ratio to obtain its internal system clock signal.

For more details see https://anydifferencebetween.com/difference-between-system-clock-and-bus-clock/ and https://en.wikipedia.org/wiki/CPU_multiplier.


In [1] (authored by one of the co-creators of Simula), there is a suggestion that Simula 67 may have been the first to use this dot notation. Given that Simula is widely credited for being the first OO language, it may be tricky to find an earlier example specifically in an OO context.

EDIT:
On DiscreteLizard's suggestion in comments, I took a peek at the use of this dot notation for specifying fields in a record. As it turns out, according to this specification of the PL/I language for the IBM System/360 from July 1965, the dot notation was indeed used to identify fields within structures:

  A qualified name takes the form:

  identifier {. identifier} ...

  Examples:
  1. A program may contain the structures:

  DECLARE 1 CARDIN, 2 PARTNO, 3 DESCRIPTION, 2 PRICE;

  DECLARE 1 CARDOUT, 2 PARTNO, 2 DESCRIPTION, 2 PRICE;

  Elements are then referred to as:

  CARDIN.PARTNO

  CARDOUT.PARTNO

  CARDIN.PRICE

Dahl, Ole-Johan. "The Birth of Object Orientation: the Simula Languages." From Object-Orientation to Formal Methods. Springer, Berlin, Heidelberg, 2004. 15-25.


How often is Prolog/ASP used in non-research areas?

how widely used ASP or other declarative languages are

You can see the activity of Prolog which I think is the most common ASP programming language:

SWI-Prolog Package Downloads: 483 downloads (not sure the interval), 239 packages.
Compare to Node.js Package Downloads underscore.js has 139,326 weekly downloads. Over 350k packages.

Just based on that, Prolog's top package is (483 / 139,326) x 100 = 0.35% as popular as one of Node.js's large packages. Or 0.07% as many packages.

  is it mostly for research purposes

IMO yes, it is mostly for research purposes. But it is similar to Ocaml, which from my experience was mostly for research purposes until corporate users like Facebook published Flow (typed JavaScript programming), and others published Coq (automated theorem proving), which helped bring Ocaml to the mainstream.

  What may be the reason they are not so well known?

IMO Prolog is not used because it is (a) a different paradigm, (b) the package manager isn't up to par (this is a big deal these days), and (c) there is no evangelized web framework. If there was a good package manager like NPM for Node.js, and there was a web framework that was marketed, as well as a small group of evangelists, that would help bring it to the mainstream. Ruby had 37signals and Rails, Python had Google, etc.

  Is it because AI-development belongs to a more "advanced level" of programming?

No not really. Some AI research uses prolog for modeling stuff, but it is not a requirement for AI. AI could be divided into two parts: (1) Machine learning / probabilistic-based models where the relations are learned and not well-defined, and then (2) manually defined models. Most AI is a mixture of both, but the manually defined models are valuable and kept private for the most part. The manually defined models could be defined using Prolog, and there are a few papers out there for doing that, but it is not necessary. To summarize, all AI work can be done in regular programming languages, just that Prolog might make it slightly more compact to write in some cases.


Data structure that supports finding frequency of given element in $O(\log n)$ and most frequent elemnt in O(1) time

As for the frequency functions, I was thinking of storing each element with an int attached to it or something, indicating number of appearances so far, thus enabling me to just search for some element to know the number of times he appears in S, but that's messy too.

That's exactly the solution I would go for.

Store a mapping of $\langle x, freq_x\rangle$ in the BST. Because each $x$ will be unique in the bst you will be able to search for the frequency with just $x$.

insert becomes

if x is in BST then
    replace <x, freq> with <x, freq+1> in bst
    if freq+1 > max_freq then
        max_freq := freq+1
        max_x := x
    endif
else
    insert <x, 1> into bst
    if max_freq = 0 then
        max_freq := 1
        max_x := x
    endif
endif

You don't really need a tree, instead a hashtable would drop the complexity down to O(1) for every access and O(N) for init.


Hardness of ambiguity/non-ambiguity for context-free grammars

Ambiguous grammars can be enumerated, since each ambiguous grammar has a proof of ambiguity, namely a word with two different parses.


Non-primitive recursiveness in real world nonmathematical software?

Many useful pieces of software have "unbounded" loops that can't be trivially bounded. Any program with a user interface that waits for input, for example. You'd probably also be surprised by the number of software that contains an interpreter of some sorts: your browser, your PDF reader, the software on your printer...


Both are correct, though I'd say the first one more so.

A von Neumann architecture means the program is stored in memory along with everything else, rather than being a separate unit attached to the processor. This means that anything the computer tries to do, no matter what it might be, is bottlenecked by the connection between the processor and memory.

So "getting data from memory is slower than processing it" is a valid description, as is "you need to fetch instructions and you need to fetch data and both of those are slow". But the most important part is that fetching from memory is extremely slow compared to anything else the processor might be doing.


You are confusing Turing reductions with mapping reduction, in a sense. The problem with your argument is that if you allow an oracle $O$ to an NP-complete (or coNP-complete) problem, you immediately get that $P^O=co-P^O$. That is, if you already have an oracle for coNP, then you cannot distinguish NP from coNP (but that does not mean that they are equal!).

Here is a shorter version of your argument, to make things clear: suppose we have an oracle for Tautology. It is true that $\phi$ is satisfiable iff $\neg \phi$ is not a tautology. Thus, in order to test if $\phi$ is satisfiable, just run the oracle on $\neg \phi$, and invert the answer. But this only shows that $NP\subseteq P^{coNP}$. Your assumption that $P^{coNP}=coNP$ is incorrect (or at least, it's an open question).


Process address space separation in L1 cache of Intel hyperthreaded CPUs

In modern Intel processors, the virtual-physical mapping is done in parallel with the lookup into the L1 cache.  There is a trick that gets the effect of doing lookups on virtual addresses, without actually having to complete the virtual-physical mapping before the cache lookup (and thus avoiding the delay you are worried about).  See https://stackoverflow.com/q/19039280/781723 and https://software.intel.com/en-us/articles/how-memory-is-accessedfor details of how they make this work.

There is only one L1 cache per physical core.  The two virtual cores on the same physical core share the same L1 cache.  See, e.g., https://stackoverflow.com/q/27797424/781723 and https://stackoverflow.com/q/32979067/781723.

Different processes can be hyperthreaded on the same physical core.

In general, you can often find answers to these questions by reading the Intel reference manuals.


Selection, crossover and mutation function choice in genetic algorithms

SELECTION. Different types of selections will have different advantages and disadvantages. You will mostly find the right one through trial and error.

CROSSOVER. The optimal crossover technique is usually problem-specific. A general rule is to avoid using a single point crossover, as suggested by this paper.

MUTATION. Some mutation guidelines are provided in this paper.


Find CSG for $L = \{a^ib^jc^k \mid 0 \leq i \leq j \leq k\}$

$$
\begin{align*}
S &\to XABS' \mid XBS' \mid XS' \mid XAB \mid XB \mid X \mid \epsilon \\
S' &\to ABCS' \mid BCS' \mid CS' \mid C \\ \\
BA & \to AB \\
CA & \to AC \\
CB & \to BC \\ \\
XA &\to aX \\
X &\to Y \\
YB &\to bY\\
Y &\to Z \\
ZC &\to cZ \\
Z &\to c
\end{align*}
$$

For the intuition behind this construction see this question.


How was the ALU implemented in the first computer (i.e., Babbage's analytical engine)?

Babbage's arithmetic unit (ALU) for the Analytical Engine was originally called the mill. It wasn't constructed out of binary logic gates (AND, OR, NOT). Instead it works on the basis of counting gear teeth and escapements.

The mill is essentially an entire Difference Engine designed to be mechanically controllable/programmable (rather than needing humans to set the input gears to the correct number). The Difference Engine is much more primitive than what we would call a "calculator" today. It is bascially a mechanical abacus. Only, instead of beads it represents numbers by the rotation of gears.

I haven't tried building one so can't quite tell you the exact detail of how it works but in general it works like this:

Two rows of input gears are spun to set it to two numbers.
The gears are connected together in such a way that when you rotate them one "cycle" both will rotate another row of output gears to produce a result. Note that a "cycle" literally means what it means - there is a crank on one end of the machine that you rotate with your arms one round to get the result.
The operation can either add the sum of the input gears or it can subtract one input from another.

That's all it can do, nothing else.

Given that it can do addition and subtraction, and given that we can calculate multiplication by repeated addition and division by repeated subtraction, we can perform any calculation.

In reality Babbage optimized his mill to do more than simply add or subtract (though, the machine can indeed do that). The gears are stacked on top of each other with the output of each stage being used as input for the next stage to calculate polynomials (somehow, I don't know the details). So you can arrange the output rows to represent multipliers in a polynomial equations and you can cycle the mill x number of times to get the result for f(x). But that's more to do with the Difference Engine. The mill for the Analytical Engine could do less specialized calculations.

So Babbage didn't design his "logic" the way a digital designer would design a circuit. He designed it the way a Swiss watch maker would design a complex feature for a handcrafted watch (moon phase display for example).


Redundant States During Removal of Null-Moves (Regular Expression to DFA)

[answer by UncleDolan originally embedded in the question post]

I believe I just solved the problem on trying it again. The strategy was to remove the nulls in the right sequence, not follow a random sequence of null-deletion. Following that, I had to remove unreachable and redundant states.

First, I state the algorithm used to remove null-moves as given in my coursebook.

For two vertices A and B with a null link from A to B,

Duplicate all the edges which are going outside from B, from A.
If A is an initial state, make B an initial state.
If B is a final state, make A a final state.
Remove the null link.

Now I'll go step-wise through the solution. I generated the images using Graphviz on Ubuntu.

First, I removed the null link between q5 and q1. q0-q5 and q2-q6 are risky at this time because I would be inadvertently duplicating the null links from q5-q1 and q6-qf.

Second, I removed the null link between q6 and qf. qf now becomes unreachable.

Third, I removed the null link between q2 and q6. q6 evidently becomes redundant.

Fourth, I removed the last null link between q0 and q5. q0 becomes redundant as we now have two initial states, both having (almost) the same moves.

I remove q0, q1 and qf for being either unreachable or redundant. The end result looks very close to (e) in the question.

I find that q2 could do q6's job without making any changes to the language. q6 is redundant as well. This is the final result.


Is there a name for "density" of information?

The classical measure of information is the entropy. Entropy measures the information content of a random source. Consider the case of text files: someone has generated some text, and she wants to communicate this text to you. Since you know that the text is in English, there is no need for her to spell out all the words in full; instead, she can replace each word by its index in some dictionary. Most of the time this scheme will be very efficient, but sometimes she might use uncommon words, and then the scheme could fare less well.

More generally, the entropy of a random source is the average number of bits that need to be communicated in order to guarantee that the receiver decodes the message successfully with high probability. You can check out the formal definition in textbooks on information theory, in Wikipedia, or in Shannon's classical paper from 1948 (still the best source on the subject).

Suppose now that you have a given text file. What is its entropy? Under the definition above, its entropy is zero: if both parties know that the text being communicated is this one particular text, then there is no need to pass any information; there is no uncertainty. Randomness and uncertainty underline the concept of knowledge which entropy tries to capture.

There are at least two ways out of this paradox. The first way is to use a universal compression mechanism, like Lempel-Ziv compression. This is a compression scheme that achieves the entropy (with small error) for all long random sources which are well behaved. If you apply such a universal compression mechanism on a random text file, on average you get roughly the entropy of the random source generating the text file. Therefore one way to estimate the entropy of the mechanism generating your text files is by compressing a given text file.

Another way out of the paradox is Kolmogorov complexity. The Kolmogorov complexity of a given string is the length of the shortest program (in some fixed programming language) that generates the string. This is a notion of complexity which does make sense for a fixed string, with no randomness assumed. However, Kolmogorov complexity is uncomputable, and it cannot even be approximated. While Kolmogorov complexity has some applications in theoretical computer science, in your case the notion of entropy seems more appropriate.


Unrecognizability of $L(M_1) \cap L(M_2) = \emptyset$

Let $T$ be a Turing machine. Construct a Turing machine $T'$ that simulates $T$ on the empty input word and, when (if) the simulation ends, it accepts (regardless of the input to $T'$). Notice that $T'$ can be computed from $T$.
Pick $M_2$ as the Turing machine that immediately halts and accepts.
Then $\{T', M_2\} \in C$ iff $L(T') = \emptyset$, which happens iff $T$ does not halt on the empty input word. Therefore if $C$ were recognizable, the halting problem would be decidable (since the language of all Turing machines that halt on the empty input word is recognizable).
This shows that $C$ is not recognizable.


"Huffman coding is unsuitable for text files"?

It's not unsuitable, it is just not optimal. That's because letters in human readable text are not independent, but quite strongly correlated. That correlation can be used to get huge savings. For example, the letters q and Q are almost always followed by u. Comma and period are almost always followed by a space character, and period space is almost always followed by an uppercase character. These correlations mean text can be compressed a lot more than by using Huffman coding. But Huffman coding does work and will you get some amount of compression.


Proof by induction over rules for mutually recursive relations

Yes, it's legit; no, you'll, (usually) have to "merge" the proofs.

You are trying to prove some property of an inductively defined set. You can do so using (structural) induction along the inductive order induced by your definition.

In a nutshell, you'll assume the property for all terms up to "size" (t.b.d.) $n$ (which has to apply to all rule premises) and conclude the property for terms up to size $n+1$ (the conclusions).

In your case, coming up with a good measure of size may be the hardest part, since $a⋅x⇓e$ and $a⋅x↓v$ are of the same "size" if you count operators. What size measure will work is impossible to say without seeing the whole calculus, though. Of course, for structural induction you don't strictly need such a measure; you can just follow the inductive order (see here for examples). As long as your semantics is well-defined, that should work.


Finding the maximum substring for which a given predicate is true

Let's denote $[\exists s: F(s) \wedge |s| = x]$ as $B(x)$. First property of $F$ implies that for any $x > L$

$$B(x) \implies B(x-1)$$

Which by induction implies:

$$B(x) \implies \forall i \in [L, x] : B(i)$$

In other words, if you know that $B(x)$ is true, you don't have to examine lower values of $x$. And if $B(y)$ is false, you know that higher values of $y$ can't give you true, as it would contradict that $B(y)$ is false.

Now you can find maximal $x$ (such that $B(x)$ holds) using binary search. For each iteration of the search, $B(i)$ can be verified in $\mathcal{O}(N)$ calls to $F$: you just need to call it for every substring of fixed length $i$.

In total, this gives you $\mathcal{O}(N \log N)$ calls to $F$.


How to draw a Turing Machine for Even-Even

From what I understand, your first algorithm intends to process the $a$ and $b$ inputs separately, which doesn't seem necessary. Your difficulty seems to come from formalizing a TM, which you can do in a couple ways.

Direct Conversion (Courtesy of Raphael in the comments)

  You can view an NFA as TM that can not write and move only to the
  right. In other words, you don't have to do anything at all for the
  conversion, just add $R$ to transitions that consume a symbol and $N$
  to $ε$-transitions, and then you basically have your equivalent TM.

Multitape Approach - Suppose we know that a multitape TM is equivalent to a TM, so  we can have two tapes:

An input tape (with a string $x\in(a|b)^*$), which we'll read through exactly once.
A computation tape which will have one of four numbers $1$, $2$, $3$, or $4$, reflecting the state that the analogous finite automata (for which you have an image) might have. If we didn't want to expand the alphabet, we could instead have $\{\epsilon\epsilon,a\epsilon,\epsilon b,ab\}$ to indicate the parity of each letter.

As we proceed through the input, we update the computation tape accordingly: if we read an $a$, and we're in state $1$, we swtich to state $3$, etc. To reduce this back to one tape, we need another symbol $\#$ to separate tapes, perhaps $\hat{a},\hat{b}$ to designate the location of the heads and pre/append our computation tape (for which we only need two characters of space).

Formal Approach - we're going to define the set of states $Q$, the tape alphabet $\Gamma$, the blank symbol $\epsilon$, the input symbols $\Sigma$, the initial state $q_0$, the accepting states $F$ and the transition function $\delta$.

$$\langle Q=\{q_{\epsilon\epsilon},q_{a\epsilon},q_{\epsilon b},q_{ab}\},\Gamma=\{a,b\},b=\epsilon,\Sigma=\{a,b\},q_0=q_{\epsilon\epsilon},F=\{q_\epsilon\},\delta\rangle$$
$$\delta=
\begin{vmatrix}
    & q_{\epsilon\epsilon} & q_{a\epsilon} & q_{\epsilon b} & q_{ab} \\
  a & q_{a\epsilon} & q_{\epsilon\epsilon} & q_{ab} & q_{\epsilon b} \\
  b & q_{\epsilon b} & q_{ab} & q_{\epsilon\epsilon} & q_{a\epsilon} \\
\end{vmatrix}$$


K Nearest Neighbor using K-D Tree (What ratio makes K-D beneficial)?

There's no way to tell for sure without trying out.  That said, a crude rule of thumb is that k-d trees tend to be useful when the number of dimensions is up to about 10-20, but in higher dimensions, often they are little better than a naive linear search over all points.
See also Is there some theoretical verification or explanation of why KDTree gets slower when the dimensionality gets higher?, How can I make k nearest neighbor queries fast on unit hypersphere?, https://en.wikipedia.org/wiki/K-d_tree#Degradation_in_performance_with_high-dimensional_data


Your first goal is provable, but is somewhat non-trivial arithmetic. I believe that the issue is essentially Isabelle not knowing that
$$S(x - 2) = x -1$$
is true for arbitrary $x$, and indeed, this property is false in general, if $x<2$! This is because $x-2=0$ in Isabelle for $x=1$.

Here this doesn't occur, because $x=2\cdot 2^n$, so $x\geq 2$ for all $n\in\mathbb{N}$. But the simplifier doesn't know this. Adding a lemma along those lines, or making sure 2*nodes(explode n t) + 1 doesn't get simplified to S(2*nodes(explode n t)) should solve your issue.

Alternately, you could re-cast your whole proof in $\mathbb{Z}$, where subtraction behaves more sanely.


How can I represent state or environment in the $\lambda$-Calculus?

Such a thing is, for the most part, impossible in the pure lambda calculus: all variables represent immutable values.

However, you can fake it in a number of ways.

The simplest is parameter passing. For a function which has a "state", you give it an extra parameter, which is a data structure mapping variables to their values. Any time you alter a variables value, you just create a new store with the updated value, and use it as the new parameter.

This pattern of passing the state to each computation in sequence can be abstracted using a State monad, or something similar. A state monad provides a pattern where the machinery of creating a new store, updating its values, and correctly passing it to future functions.

Monads provide a sequencing operator, which allow for the ordered evaluation that you mention.

There exists calculi which have mutation built into them, but first off, they aren't the pure calculus as you asked for, and in such cases, you don't encode mutation, you add it as a primitive operation.


Discrepancy between process execution time and CPU speed (lost cycles)

The $2.3\textrm{GHz}$ clock cycle speed of your CPU is something entirely different from the rate at which it executes assembly instructions. Executing a single instruction may take 1, 10 or even more than 100 clock cycles or it might take less than a single cycle (since multiple instructions can sometimes be executed in a single cycle).

An interesting experiment would be to do some work in the loop body, such as an addition or a division. Even though addition and division are both single instructions, the program that does a division will probably take considerably longer than one that does addition since on most architectures division takes many clock cycles.


One can verify that the following matrix $\Gamma$ has the desired properties:
$\Gamma = [\pi]Q - Q^{\top}[\pi]$,
where $[\pi]$ is a diagonal matrix with diagonal elements being the stationary distribution. This construction relates closely to the reversibility of a Markov chain as far as I know.


This method doesn't work since you can't always pair clauses as in your example.

According to Wikipedia, 2SAT is NL-complete. In particular, this means that it is not in logspace unless L=NL, which is considered unlikely.


How to make sense of this context-sensitive production in a textbook? (a typo perhaps?)

First, they describe noncontracting grammars, and give an example: the one you are quoting.

Next, they write: equivalently, we can use a different restriction on grammars, and describe the context-sensitive grammars.

Chomsky proved the equivalence in 1963.


Recognizability of machines which halt in $n$ steps on some input

This could be proven without reduction. The proof is straightforward: given $M$ run through all strings, say over $0$ and $1$, in canonical order and for each string $x$ simulate $M(x)$ for $|x|$ steps and check if it halts. If there is such $x$, then you will eventually find this $x$ and so accept $x$.


How does processing speed affect algorithm performance?

Let's say that the execution time of an algorithm is $\Theta(f(n))$. That means the execution time is between c·f(n) and C·f(n) for all n ≥ N, for some N, c and C. Because of the constant, you can't say anything definite about the maximum problem size that can be solved in time T on a slow and a fast computer.

You can assume that the actual execution time is c·f(n) for a c that you know; that assumption is neither completely unreasonable nor completely justified. Then define for example n' as the value where c·f(n') = k · c·f(n), to get something meaningful for a machine that is k times faster.

Calculating n' depends on the nature of f(n). If f(n) is linear, then n' = k·n. If f(n) is cubic, then n' = $k^{1/3}·n$. If f(n) = c·n·ln n then n' is a bit less than k·n, the exact result is difficult. If f(n)=$2^n$, then n' = $n + \log k$. The last shows why efficient algorithms don't become less important with faster computers in practice: Because the less efficient the algorithm, the less a faster computer can improve the size of a problem that can be solved in fixed time.


Performance of microkernel vs monolithic kernel

As is always the answer (or at least the preface) to performance-related questions: know your problem domain, run comparative benchmarks, and remember what premature optimization is.

First, no comprehensive benchmarking trials have compared monolithic kernels to current-generation microkernel systems that operate in an equivalent manner. So, while there may be trials that compare specific elements of those kernels, they're not going to be representative of the "big picture" that your question is looking to paint.

With that being said, there are wildly divergent observations of kernel performance across microkernels; for example, the L4 microkernel family can be said to have IPC performance an order of magnitude higher than the Mach kernel. But every Apple device from this decade is running Mach, and they seem to work plenty fast, right?

The moral of the story is that anybody who's deciding what kernel architecture to use needs to first decide what their ultimate goal is. Microkernel systems are (when properly implemented, of course) more secure, maintainable, and modular. However, they can be tough to architect properly, and may have performance overhead over a monolithic implementation. A monolithic kernel will be faster, but security will be harder to implement and it will be less modular and less easy to customize.

Your kernel architecture should be based on what your end goal is.

(And when all else fails, try it both ways and see what happens.)


What is the relationship between tail recursion with other recursions?

We need to distinguish two things:

Tail-calls are calls to functions that are made in tail position. Tail-recursion is a recursive tail-call.
Tail-call optimization is the process by which tail-calls are turned into loops or GOTOs in compilers.

The second, as others have stated, is an implementation detail that falls in the theory of compilers, and isn't really recursion theory.

However, it is absolutely possible to study tail calls in the context of computability. In particular, there is something called Continuation Passing Style.

There exist CPS-transformations which can turn any lambda-function into one in continuation passing style. So the set of languages computed using only tail-calls is equivalent to the set of recursively-enumerable languages.

CPS has many applications in the theory of programming languages, and the concept of tail recursion is useful for more than just the tail-call optimization.


What is standardization in computer science?

A standard for a programming language is a document defining the syntax and semantics for that language. Usually, for real-world languages, this document involves a (hopefully) precise description in intuitive terms, rather than a formal semantics, written in mathematical terms.

Still, this document acts as a contract between the programmer and the language implementation (usually a compiler/interpreter, plus some "standard libraries").

The programmer knows that, if they stick to what the standard mandates, they will get back the intended result from the implementation. Vice versa, the implementor of the language can assume that the programmer used no other features than those mandated. Often, the implementor will also provide non-standard features (additional APIs, additional language constructs, OS-specific libraries, etc.).

Note that the standard does not only involve describing the APIs in the standard library. In the case of the C language, as mentioned by the OP, the standard defines among others: the syntax, the type system, the memory model, the statements, the variable declarations, etc.

For instance, what happens if we write int *x; *x=0;? The ISO standard answers that: an implementation printing mooo! on screen is perfectly conforming (as any other implementation is).

So, summing up, a standard is the authoritative document which answers questions like "is running code C guaranteed to have behavior B?".

Most standards are written by a committee made of the most prominent organizations which developed / are developing the most widespread implementations. They vote on which features should be in or out, until they reach an agreement on what should be the standard definition. Some languages are revised every few years, so to include more features.


The recurrence can be solved as:
$$
\begin{align}
C(k) &= \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}\\
2 \cdot C(k) &= 1 + C(k) + 1 + C(k-1)\\
C(k) &= 1 + 1 + C(k-1)\\
C(k) &= 2 + C(k-1)\\
\end{align}
$$
Then this can clearly be expanded to a summation:
$$
\begin{align}
C(k) &= 2 + C(k-1)\\
&= 2 + 2 + C(k - 2)\\
&= 2 + 2 + 2 + C(k - 3)\\
& \dots\\
&= 2 + 2 + \dots + C(1)\\
&= 2k\\
\end{align}
$$

I haven't done much investigation into skip lists, but the math you've shown checks out. ✓

EDIT

The reason $C(k)$ appears in the left and right side of the equation, which seems concerning, is because of the Skip List structure. Take this procedure (source) to $find(86)$:

Now let's consider the reverse of this path. Notice we always move up if we can. So for any node in the reverse path, we can either (1) move up or (2) move left:

We move up. Now we have $C(k-1)$ more levels up to go: $$1 + C(k - 1)$$
We move left. We have made no progress upwards, therefore we still have $C(k)$ more levels up to go: $$1 + C(k)$$

For a randomized skip list, either of these scenarios occurs with probability $\frac{1}{2}$. This is how we get the final recurrence:

$$C(k) = \frac{1 + C(k)}{2} + \frac{1 + C(k-1)}{2}$$


Is the language of words containing equal number of 001 and 100 regular?

An answer extracted from the question.

Yes, it is regular; below is an automaton that accepts it.

As pointed out by Hendrik Jan, there should be an additional 0 self-loop at q5.


Although this is not tight, I can offer lower and upper bounds of $1/4$ and $3/4$ on the worst case ratio between guillotine cuts and general cuts.

Let us start with the upper bound and assume we are given a square piece of glass with a side length of $2$. Furthermore, we have exactly one buyer who is interested in rectangular glass sheets of width $1-\varepsilon$ and length $1+\varepsilon$. Using general cuts, the optimal solution looks something like the following picture, with four of the desired rectangles placed around a little square of side length $\varepsilon$ in the middle.

It is easy to see that this cutting pattern can not be achieved via guillotine cuts. In fact, any cutting pattern using guillotine cuts can fit at most 3 of the desired rectangles into the original square. As a result, the worst ratio between guillotine cuts and general cuts is at least $3/4$.

Next, we have a look at the lower bound. Let $W$ and $L$ be the side lengths of the original sheet of glass. Without loss of generality, we can assume that there exists a buyer $i$ such that $w_i \leq W$ and $l_i \leq L$. Otherwise, the original sheet would be unusable, no matter if we use guillotine cuts or general cuts.  However, using guillotine cuts, we can always cut out at least one quarter of the original sheet by simply aligning the rectangles desired by buyer $i$, as shown in the following picture.

Notice that the red rectangle corresponds to one quarter of the whole sheet and is completely covered by the gray rectangles buyer $i$ desires. On the other hand, even if we use general cuts, we cannot use more than the whole sheet, which gives us a lower bound of $1/4$.

I am aware that the lower bound is quite weak and it can probably be improved with a bit more work. But it is a start.


Finding CNF of $(p \rightarrow q) \rightarrow p$ and $\lnot (q \wedge (\lnot p \rightarrow q)) $

Your formula is incorrect as CNF. Conjunctive normal form (CNF) is a normal form like

$$
  (a_1 \vee \neg a_2 \vee \dots \vee a_n) \wedge (\neg b_1 \vee \dots \vee b_m) \wedge \dots \wedge (c_1 \vee \dots \vee c_l)
$$

therefore a formula in CNF has only literals (i.e. atoms or negated atoms), $\wedge$, and $\vee$. It doesn't have $\to$.

If it's allowed to transform $p \to q$ to its equivalent formula $(\neg p) \vee q$, you can use this for the first step to convert a given formula to a CNF formula.


Three languages and how to decide if they are regular

The first two are regular, because they can be written as $aA^*aA^*+bA^*bA^*$ and $A^*aA^*a+A^*bA^*b$ (where $A=a+b$). This is because it is enough to check them for $|w|=1$, as it is implied by longer $w$.

The last language is not regular, because its intersection with the regular language $a^+b^+aba^+b^+$ is $\{a^nb^maba^nb^m| n,m\geq 1\}$ which is not regular (you can show this by pumping lemma).


How are boolean circuits used for solving P vs NP?

First, let me start by explaining what Boolean circuits are. You are probably familiar with Boolean formulas — these are formulas of the sort $(a \land b) \lor (\lnot a \land \lnot b)$. We can represent each formula as a tree. In our example, the root of the tree will be labeled $\lor$, and its two children are the trees corresponding to $a \land b$ and $\lnot a \land \lnot b$. More generally, there are four types of nodes: nodes labeled $\lor$ or $\land$ have exactly two children, nodes labeled $\lnot$ have exactly one child, and the rest of the nodes are labeled by input variables. We can think of the edges as directed towards the root.

Boolean circuits generalize Boolean formulas by allowing arbitrary directed acyclic graphs instead of directed trees. In the example above, we can, for example, identify the two nodes labeled $a$ and the two nodes labeled $b$. Alternatively, we can identify Boolean circuits with straightline programs. These are programs which use the following instructions:

$x \gets y \lor z$.
$x \gets y \land z$.
$x \gets \lnot y$.

For example, the formula above corresponds to the straightline program

$x \gets a \land b$.
$y \gets \lnot a$.
$z \gets \lnot b$.
$w \gets y \land z$.
$o \gets x \lor w$.

The value of the formula is the value of the last assignment. Notice that every variable other than the inputs is used exactly once. Straightline programs with this constraint correspond to formulas. If we remove the constraint, the we get circuits.

The $\mathsf{P} \neq \mathsf{NP}$ conjecture can be stated equivalently as follows:

  SAT has no polynomial time algorithm.

It turns out that the following conjecture (known as $\mathsf{P/poly} \neq \mathsf{NP}$) implies $\mathsf{P} \neq \mathsf{NP}$:

  SAT has no polynomial size circuits.

What does this mean? We can encode CNFs as strings of bits (for example, encode them first in ASCII, and then unfold the ASCII into bits). Let $SAT_n$ be the collection of satisfiable CNFs of length $n$ bits. A circuit for $SAT_n$ is a circuit on $n$ inputs $x_1,\ldots,x_n$ which returns True if and only if $x_1\ldots x_n \in SAT_n$, i.e., the CNF corresponding to $x_1\ldots x_n$ is satisfiable. We say that a collection of circuits $C_1,C_2,\ldots$ solves SAT if $C_n$ is a circuit for $SAT_n$. The collection has polynomial size if there exists a polynomial $P(n)$ such that the size of $C_n$ is at most $P(n)$ (the size of a circuit is the number of nodes in its graphical representation).

Why does this imply that SAT has no polynomial time algorithms? The reason is (essentially) the Cook–Levin theorem. This theorem shows that if SAT has a polynomial time algorithm then it also has polynomial size circuits. There is nothing special about SAT here — this reduction works for every problem. The theorem shows how to encode the computation of a Turing machine running in polynomial time as a polynomial size circuit.

Unfortunately, we are very far from realizing this program. We only know how to show that polynomial size circuits cannot solve certain problems in the following circumstances:

When the circuit is shallow, that is, has small depth.
When the circuit doesn’t use $\lnot$ gates at all.
For non-explicit problems: by counting the number of polynomial size circuits (for any fixed polynomial), you can show that there must be some functions that they cannot compute.

There is some further progress which throws diagonalization into the mix, but that’s about it. It seems that this approach is stuck, and different lines of attack are required to solve this important problem.


Approximating Deep Neural Networks (DNNs) with Binarized Neural Networks (BNNs)

I expect you'll run into two challenges in this line of research: (1) there are no known ways to construct a BNN that exactly matches an ordinary neural network; (2) verifying a BNN with a SAT solver won't scale to the size models needed for most interesting tasks.

Since you asked specifically about (1), no, I don't know of any way to do that.  Probably you won't find exact equivalence.  You might be able to train a BNN that has a very high agreement with the ordinary neural network on the training set; I don't know whether it will have the same adversarial examples or not.


Are qubits written in a big-endian or little-endian order when grouped?

There's no convention. Usually the endian-ness doesn't matter, or else it's clear from the context which endian-ness is being used.

(I'm also not aware of a convention for whether the wires in circuit diagrams are top-endian or bottom-endian. I just always infer from context.)