Unfortunately, there is no single definition of the size of instance. But if there were, it would be the size of the input in bits. Whenever we talk about Turing machines, we have to slightly change this to the size of the input in tape symbols.

Things get more complicated for models like the RAM machine, in which numbers are opaque. If the input consists of arbitrary-precision numbers, then the inputs size is the number of input numbers. This is again a variation on the earlier definition, since in this model, every memory cell contains an entire number.

Summarizing, the size of the input is always the number of cell / tape positions containing the input, but the interpretation of this quantity depends on the model.

More concretely, in your first example, the input includes the input array of length $n$ as well as the number $n$, so the input length should be at least $n+1$. The model in question here is the RAM model. If it were the Turing machine model, the size of the input would depend on the size of the integers being sorted.

In your second example, it depends on the exact encoding. In the RAM model, you can encode a graph with $n$ vertices and $m$ edge using $O(m)$ cells. In the Turing machine model, you can encode a graph using $O(n^2)$ cells or $O((m+1)\log n)$ cells, using the dense and sparse encodings, respectively. Sometimes the input encoding affects the running time, and in that case the algorithm would expect the input in some specific encoding, and you would get the input length from this encoding. Notice that I don't bother calculating the exact input length – almost always asymptotics are enough.


Making sure the Branch Target Buffer stays accurate

The BTB is not really presumed to be accurate. It cannot be accurate. Even putting SMC aside, indirect and other variable-target jumps cannot have their target predicted perfectly. That is not a correctness problem though, the control flow instructions can be executed and at that point it becomes possible to verify the actual target and do the usual front-end-redirect and pipeline flush if the target does not match.

But that does not solve the SMC problem in general. If you need to make SMC work as if the processor is strictly serial, some extra checks are necessary. The checks can be quite conservative and still perform well when SMC isn't happening, which is usually the main case. For example, you can check whether a write is to a code page, and insert an appropriate flush (after the write) if it does. Of course such a coarse test is easily fooled by just marking a data page executable, even if it is never jumped into, needlessly degrading performance. An other strategy might be to check, at retirement of any instruction, whether its page is marked dirty (this makes SMC have a "long shadow", any modification "ruins" a code page until its dirty bit is reset). More precise mechanisms are possible.


Yes, the number of nodes in the suffix tree is $O(n)$.

Here's how you could infer that.  The suffix tree can be constructed in $O(n)$ time.  There's no way to construct a tree with strictly more nodes than that, since it takes at least $\Omega(1)$ time per node you construct; so from the fact that the running time of the suffix tree algorithm is $O(n)$, you can conclude that its output must have size $O(n)$, i.e., the suffix tree must have $O(n)$ nodes.

Here's another way you could have inferred that.  There are $n$ leaves.  Also, each internal node has at least two children.  In such a tree, the number of internal nodes is at most the number of leaves, so in this case, there are at most $n$ internal nodes and $n$ leaves.  It follows that the number of nodes in the tree is at most $2n = O(n)$.

This information is actually found in the Wikipedia page on suffix trees, which explains that any suffix tree has at most $2n$ nodes.  In the future, before asking a question here, please check standard resources, such as Wikipedia and a textbook.

It follows that the tree can be traversed in $O(n)$ time.


Why Minimum circuit size problem is important?

Finding the minimum size circuit is not important in practice for large circuits. Finding small size circuits is of course important because it directly impacts the cost of building a circuit.

Finding minimum size circuits for small circuits that are used as building blocks is quite important. For example, you'd want to know how to build the smallest possible full adder if you end up having a million of them in a processor. And you really want a minimum size circuit for a bit of memory in your L3 cache when your processor has 36MB of L3 cache or 288 million of these cells.

However, minimising the delay of a circuit is also important, and sometimes more important or even far more important than minimum size.


Random Access Machines with only addition, multiplication, equality

The other day I was reading a paper on parallelized random access machines without bit operations, which sounded very much like what you are describing. For these models NC is known not to equal P. See here: https://epubs.siam.org/doi/10.1137/S0097539794282930

The paper can also be found on Professor Mulmuley’s website.


Q1: Lamport describes a round of Paxos as two phases: a prepare phase, and an accept phase. An instance of Paxos can have multiple rounds. Can a round have multiple proposers make proposals, or is it strictly one proposal per round?

I don't think Lamport uses the term "round" to organize the two phases, at least it is not the case in the "Paxos Made Simple" paper. Actually, the word "round" only occurs once in that paper and it is used to refer to the communication round.

The term "round" is used in James Aspnes' lecture notes to refer to

  the collection of all messages labeled with some particular proposal $n$.

It is important to distinguish between the definition of "round" here and the "communication round". In this sense, a round is dedicated to a single proposal (and belongs to a single proposer), because different proposals have globally unique timestamps.

Q2: I found a number of sources which indicate there are three phases in Paxos. Which is true?

As explained in James Aspnes' lecture notes,

  Note that acceptance is a purely local phenomenon; additional messages are needed to detect which if any proposals have been accepted by a majority of acceptors. Typically this involves a fourth round, where acceptors send accepted(n, v) to all learners.

In the "Paxos Made Simple" paper, Lamport mentions the "learning" phase in Section 2.3 (see Page 6). Notice that it is a fourth phase in Aspnes' lecture note.

Q3: If we do require three phases, in which a distinguished learner informs all other participants of the chosen value, does Paxos then guarantee that all nodes agree on the chosen value? What about the minority of acceptors that did not accept the value? Does the distinguished learner inform them too?

In the classic formalization of Paxos, there are three roles which are proposers, acceptors, and learners. Learners are required to learn the chosen value. So the "learning" algorithm in Section 2.3 is (there are other variants):

  We can have the acceptors respond with their acceptances to a distinguished learner, which in turn informs the other learners when a value has been chosen.

In this approach, all acceptors send every proposal they have accepted to the distinguished learner. The distinguished learner (locally) regards a value to be chosen only when it is accepted by a majority of acceptors. Then, the chosen value is propagated to other learners.


How to prove this language is not regular (via Fooling Set)

Let $s_1 < s_2 < \cdots$ be a subset of $\mathbb{N}$ with the following property:

$$ \limsup_{n\to\infty} s_{n+1}-s_n = \infty. $$

I will show that the language $L = \{ 0^{s_n} : n \geq 0 \}$ isn't regular using the fooling set method.

The first step is to find indices $i_1 < i_2 < \cdots$ such that
$$
s_{i_1+1}-s_{i_1} < s_{i_2+1}-s_{i_2} < \cdots.
$$
This can easily be done using the given property.

Our fooling set is $\{ 0^{s_{i_n}} : n \geq 0 \}$. To show that this is a fooling set, let $j < k$, and consider the words $x = 0^{s_{i_j}}$ and $y = 0^{s_{i_k}}$. Let $z = 0^{s_{i_j+1}-s_{i_j}}$. Then $xz = 0^{s_{i_j+1}} \in L$ but $yz = 0^{s_{i_k}+s_{i_j+1}-s_{i_j}} \notin L$ since by construction,
$$ s_{i_k} < s_{i_k}+s_{i_j+1}-s_{i_j} < s_{i_k+1}. $$

More generally, a unary language $\{0^s : s \in S\}$ is regular if and only if there exist $N,M$ such that $n \in S$ iff $n+M \in S$ for all $n \geq N$. There are many ways to show it, the most elementary being that a graph of unary DFA consists of a path leading to a cycle. This result implies yours.


$AMA$ is basically a 3-round interactive proof system where the verifier (Arthur) is only allowed to send randomness to the prover (Merlin).
I haven't seen such an explicit definition yet, but I think we can formulate it as follows.
The first round of AM[3] starts with Merlin sending a message $m_1$ to Arthur. In the second round, Arthur sends randomness $r$ to Merlin, which is followed by the final third round in which Merlin sends a message $m_2$. Arthur then decides to accept/reject using deterministic polynomial-time verifier $V$.
I think we can define the class as follows.
Definition: $L ∈ AMA$ if there exists a poly-time deterministic algorithm $V$ such that:

If $x \in L \;(|x| = n)$ then $\exists P. Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 \right) \ge 2/3$ where $\; m_1 = P(x),\;
m_2 = P(x, r)$
If $x \notin L \;(|x| = n)$ then $\forall P. Pr_{r \in \{0,1\}^{p(n)}} \left( V(x, m_1, r, m_2) = 1 \right) \le 1/3$ where $\; m_1 = P(x),\;
m_2 = P(x, r)$

Note the prover $P$ is a function $P: \{0,1\}^* \rightarrow \{0,1\}^{q(n)}$, where $q(n)$ is a polynomial.
See: Computational Complxity by Arora-Barak's section 8.1.


Let me quote the wikipedia entry for linear grammar:

  Two special types of linear grammars are the following:

  the left-linear or left regular grammars, in which all nonterminals in right hand sides are at the left ends
  the right-linear or right regular grammars, in which all nonterminals in right hand sides are at the right ends.

  Collectively, these two special types of linear grammars are known as
  the regular grammars; both can describe exactly the regular languages.

As you can see, your grammar is a left-linear grammar, and it generates a regular language. Type-3 grammars of the Chomsky hierarchy can be defined as right-linear grammars or as left-linear grammars, as you prefer.


Why frame must be longer than generator polynomial?

If the CRC polynomial is $m$-bit long, then in order to create $M'$ from $M$, you need to add $m$ bits (or perhaps $m-1$ bits). In particular, the final message $M'$ is at least $m$-bit long.


Time taken by a message to reach receiver : Propagation delay or time
Time taken to push message on the link by the sender : Transmission time

Transmission time is the time from the first bit until the last bit of a message has left the transmitting node. Or, in simple word it's the amount of time required for the router to push out the packet.

Packet transmission time = Packet size / Bit rate

Reference :

in2p3.fr/actions/formation/InfoTempsReel/IN2P3-Ch1-datatran-tr.pdf


The basic syntactic units in any textual programming language are tokens, which are, if you wish, the words in the programming language. The compiler parses these tokens to build sentences and so forth.

A malformed token is a string of characters that is not a valid word for the programming language.

It is not a variable that doesn't match the naming rules – not all tokens are variables. It is not an operator that is unknown – sometimes operators can be defined by the programmer. It is one of the smallest pieces of syntax that will never correspond to something sensible.


How to simulate natural number in Pi Calculus

You can encode natural numbers in π-calculus in a way that is a variant on encodings of natural numbers in untyped λ-calculus, see (1). Milner, Parrow & Walker explain how to do this in the paper (2) that introduced  π-calculus. Note that such encodings are not efficient (they are essentally unary encodings of numbers, so give rise to large terms). You only do such encodings to gauge expressive power of the untyped π-calculus. In any real implementation, you'd add numbers as a basic data-type.

Wikipedia, Church encoding.

R. Milner, J. Parrow, D. Walker, A Calculus of Mobile Processes, Part I.


It depends on the algorithm for obtaining CNF of a formula.
A simple truth table-based method will always produce syntactically the same CNFs for equivalent formulas, since it in a sense just gives you the rows of the truth table for which the formula evaluates to false.

A trivial example of equivalent formulas, which are both in CNF:

$$A \wedge B$$
$$(A \vee B) \wedge (A \vee \neg B) \wedge (\neg A \vee B).$$

Non-uniqueness of CNF means that one can build an algorithm, which returns essentially different CNFs for equivalent formulas. For example, as a first step the conversion algorithm can check if a formula already in CNF and return it immediately.


In the learning theory version of Occam's razor, why can't I just declare whatever hypothesis I want to be "shortest"?

There are several ways to formalize Occam's razor in learning theory, and they yield theorems that are powerful. However, these theorems do not obviate the need for inductive bias, nor do they create it. That would be like asking a computer program to create entropy. They do not create the ghost in the machine. What they do provide is a way to formalize inductive bias and provide useful theorems for what one may conclude about a set of hypotheses weighted with inductive bias.

If you get "lucky" and the inductive bias you encode happens to match the real world - which you believe is prone to happen if you subscribe to Occam's razor out-of-universe - then the theorems will do a very good job of teasing out the matching hypothesis and will even know how to make tradeoffs between good, short hypotheses and excellent, less-short hypotheses. They will then provide a bound on the error.

What if you are living in a Kuhnian paradigm shift and you are not sure which of two sets of inductive biases is better? Will Occam's razor help you? Yes and no - if you have twice the data you can study both just as before but "twice the data" is of course asking for more information to enter the system. So they cannot magically decide between Newton and Einstein.

One presentation of Occam's razor, from Understanding Machine Learning as Theorem 7.7 is the following. It is a weaker presentation in that it is designed for nonuniform agnostic PAC learnability, which is quite weak, in that no perfect hypothesis can ever be returned. So the conclusions will also be weak.

  Let $\mathcal H$ be a hypothesis class and let $d:\mathcal H \rightarrow \{0,1\}^*$ be a prefix-free description language for $\mathcal H$. Then, for every sample size $m$, every confidence parameter $\delta > 0$, and every probability distribution $\mathcal D$, with probability greater than $1 - \delta$ over the choice of $S \sim \mathcal D^m$, we have that $$\forall h \in \mathcal H, L_{\mathcal D}(h) \leq L_S(h) + \sqrt{\frac{|h| + \ln(2/\delta)}{2m}}$$ where $|h|$ is the length of $d(h$).

This gives rise to the Minimum Description Length learning paradigm: For $\mathcal H, \mathcal D, d$ as above and a loss function, output the hypothesis $h$ that minimizes $L_S(h) + \sqrt{\frac{|h| + \ln(2/\delta)}{2m}}$, i.e. the empirical loss plus the estimation error given by the theorem.

So by itself the theorem isn't making any claim about which hypothesis is best. It's actually making a much more boring claim that short hypotheses are easy to estimate well. It is possible to estimate a hypothesis $h$ up to an error factor of $O(|h|^{1/2})$ (where $O$ holds $m,\delta$ constant), and moreover, it is possible to do this for all hypotheses simultaneously. You can get each and every error estimate and only degrade the quality of the estimate in $O(|h|^{1/2})$.

Now I will convince you this is not trivial. Bear in mind at the other extreme, if you have a single hypothesis $h$ and you want to estimate its error, that's actually really easy to do on a small number of examples. It's the question of determining the weight of an unbiased coin by flipping it a few times, which is given by the Hoeffding/Chernoff bounds. Spoiler alert, you can achieve an estimation error of $\sqrt{\frac{\ln(2/\delta)}{2m}}$ with probability $1-\delta$. In above notation, that's $O(1)$ in $|h|$. All you were trying to do in the Theorem, for all $h$ equipped with some length function, is estimate the error and you achieved $O(|h|^{1/2})$ but here you achieved $O(1)$. What gives?

Let's try estimating for $1000$ hypotheses and try to achieve an estimation error of $10\%$ with probability $99\%$ just by using a simple Hoeffding bound. We calculate we need $265$ examples to achieve this. Not bad. So the first hypothesis we estimate within $10\%$ with probability $99\%$. The second hypothesis we estimate within $\10\%$ with probability $99\%$. But wait, that means the probability that either may fail could exceed $1\%$. By basic probability we only know the probability both estimates succeed is at least $98.01\%$.

And that's not good, because we have 1000 hypotheses. $.99^{1000}=0.004\%$. Not good. And in the context of machine learning, if one hypothesis is estimated wrong, very often the hypothesis is an overfitter. So one failure is enough to ruin the whole model.

So if you do want to estimate 1000 hypotheses simultaneously, you will need many more examples (not too bad -- $\ln(2/\delta)$ does not grow too fast in $1/\delta$) to achieve this.

And if you have infinitely many, you simply cannot do it by naive application of the Hoeffding bound.

So the Theorem lets you achieve an $O(|h|^{1/2})$ estimation error for all hypotheses simultaneously. This is powerful.

What if you try to rig the game and take a complex hypothesis and rig it so its length is just $1$? Then you will get a good estimate for this hypothesis and a worse estimate for many others. The estimation error power is conserved. If you were interested in that hypothesis, you may have also just drawn 265 (or however many) examples and run a Hoeffding bound on it. This is no different.

And if you want to try two totally different schema, you may do exactly that, but you will need a tighter $\delta$ to assure that both succeed. This is a serious mistake you can make when running a machine learning algorithm!

The MDL learner makes no guarantees about returning the best hypothesis. It guarantees to return one that solves a particular set of bounds. That particular set of bounds incorporates "out of universe" Occam's razor, your own inductive bias as the learner or programmer or source of entropy, and will formalize that inductive bias into a set of bounds that will focus more attention onto "simpler" hypotheses, and if your inductive bias is on track, they will output aggressive error bounds on the hypothesis. I reiterate this is the nonuniformly PAC learnable model, so it's too much to ask for a guarantee on the resulting hypothesis. In that sense MDL is weak, as it must be.

A finite PAC formulation of Occam's razor is:

  Fix $\mathcal H$ and fix $\epsilon, \delta$. Suppose there exists a finite $\mathcal L \subset \mathcal H$ with the following property: Take $m \geq \frac1\epsilon(\ln|\mathcal L| + \ln(\frac1\delta)$.  If for every $S \sim \mathcal D^m$ there is an $h \in \mathcal L$ so that $h$ is consistent with $S$, then $h$ is $\epsilon$-accurate and $\delta$-confident, so $\mathcal H$ is PAC learnable with this algorithm.

i.e. if a small hypothesis class can consistently represent pretty large sets of examples, then it is PAC. This is another version of Occam's Razor that, being in a PAC setting, is stronger than the nonuniform PAC discussion above: if the hypothesis class is surprisingly rich for how surprisingly small it is, then it actually describes the world accurately. But it demands a lot, as a real-world machine learner would be pressed to find a noiseless set of data that clean, and I'm not sure if this particular "Occam's razor" theorem generalizes to harsher terrain.


Problems solvable in time $f(n)$ but not in time $o(f(n))$

Consider the language of all binary words which consist only of zeroes. It can be decided on a deterministic Turing machine in time $O(n)$, but not in time $o(n)$.
For general time-constructible functions $f(n)$, the time hierarchy theorem shows that the problem of deciding whether a Turing machine halts in time $f(n)$ can be solved in time $O(f(n)\log f(n))$ but not in time $o(f(n))$. It is not known how to eliminate this logarithmic gap in general.


How to recognize a STRIPS planning problem has no solution?

Realize that STRIPS solves linear planning problems. By this I mean those planning tasks where the order in which the goals are satisfied is not relevant and these are, in practice, easier to solve than the non-linear planning problems ---be aware, however, that STRIPS is PSPACE-complete anyway and it is necessary to restrict it quite a lot to prove it to be NP-complete (though whether both classes are equal is still unknown but, ... may I say unlikely?)

Non-linearity is quite intriguing. It does not only mean that a particular planning task with, say, 3 goals $G=\{g_1, g_2, g_3\}$ can only be satisified in a particular ordering (such as: first $g_2$, then $g_1$ and finally $g_3$). It might also imply that while some goals are achieved simultaneously, others have to be satisified in a particular order. A good discussion on the subject can be found in Korf, Richard E. Planning as Search: A Quantitative Approach. Artificial Intelligence 33, pp. 65--88. 1987

From your pseudocode, realize that STRIPS commits to a particular order in line 2.1 of STRIPS-step and it never tries any other one. In fact, the ordering selected for the goals is strict after step 2.2. Thus, STRIPS explores the whole state space engendered by the definition of the planning task for a particular ordering of the subgoals If this ordering has not been properly chosen, then the problem is unsolvable for STRIPS.

In the end, all that STRIPS can say is that a problem is unsolvable for a particular ordering but not whether the planning task is solvable or not. Although it is not shown in your pseudocode, recall that STRIPS can discard a particular operator if its preconditions introduce goals that were considered before ---i.e., it avoids circular reasonings. And, in the end, it will have no available operator if the problem is unsolvable for the selected ordering.

PRODIGY was an attempt to solve this problem by explicitly enumerating all the different orderings of the subgoals which, however, might become very easily an unmanageable number. FF, Hoffmann, Joerg, Nebel, Bernhard. The FF Planning System: Fast Plan Generation Through Heuristic Search. Journal of Artificial Intelligence Research 14, pp. 253--302. 2001, however, can detect that some planning tasks are unsolvable even if they are non-linear planning tasks just by verifying that the relaxed graphplan cannot achieve them. Nevertheless, this procedure is sound but incomplete ---i.e., some unsolvable planning tasks can seem solvable fooling FF.


What is the approximation ratio of this randomized algorithm for finding matchings?

Suppose that the only feasible solution are single edges and $\{(1,1),(2,2),\ldots,(n,n)\}$. The optimal solution thus has value $n$. On the other hand, the optimal solution on a random bipartite graph is $1$ with probability $1-2^{-n}$. Thus algorithm BA would have to take $T=\Omega(2^n)$ in order to guarantee a constant approximation ratio, even though algorithm LA always outputs the optimal solution.


Proving that Max Weighted Independent Set is in NP

The issue is with the version of the problem you are using. Note that as you define it, the output is required to be the maximum weight independent set, i.e. the optimum answer. $NP$ however is a class of decision problems, so the only valid outputs are Yes and No.

So if you want to show the problem is in $NP$ you first need to convert it to a decision problem:

  $k$-Weight Independent Set
  Input: A vertex weighted graph $G=(V,E,w)$ and an integer $k$.
  Question: Is the a set $V'\subset V$ such that $V'$ is an independent set and $\sum_{v\in V'} w(v) \geq k$?

It should be easier to see that this version is in $NP$. There is an optimization class - $NPO$ - that corresponds to $NP$, but the normal definition is that a problem is in $NPO$ if its decision variant is in $NP$ - so you're still in the position where you want to deal with the decision variant.


What is the space complexity of quicksort?

Since worst case space complexity of $\Theta(n)$ could be a problem, you can make a slight modification to the Qicksort algorithm: Partition the array, then sort the smaller half recursively, and sort the larger half iteratively. Roughly:
Sort (range r)
    While r contains two or more elements
        Partition range r
        Sort (smaller sub partition)
        r = larger sub partition

This reduces the worst case space required to $\Theta(\log n))$. It does not help with the worst case execution time.


Computing the intersection of two NPDA where it is possible

I think this is possible for the subclass of CFLs that are permutation-invariant with a binary alphabet.

These correspond to type $\langle 1,1\rangle$ quantifier languages comparing the cardinalities of two sets. [1] characterizes such languages accepted by DPDA by the equivalent semilinear sets, and states at the end that quantifier languages accepted by NPDA are finite boolean combinations of such languages accepted by DPDA.

A theorem of van Benthem ([2]) says that pushdown automata accept type $\langle 1,1\rangle$ quantifiers definable in Presburger arithmetic (i.e. defined by semilinear sets). So, if you get two languages that are non-deterministic CFLs (using the first paper to know you have such examples), their intersection should also be a CFL by this theorem.

The semilinear set which is their intersection might be a bit difficult to compute... but, if you have that, [3] (pgs.11-12) give an algorithm for creating an NPDA accepting the language based on the generators of the corresponding semilinear set.

[1] Makoto Kanazawa. Monadic quantiers recognized by deterministic push-
down automata. In Proceedings of the 19th Amsterdam Colloquium, pages
139-146, 2013.

[2] Johann van Benthem. Essays in Logical Semantics. Studies in Linguistics and Philosophy Volume 29, 1986, pp 151-176.

[3] Marcin Mostowski. Computational semantics for monadic quantiers. Journal of Applied Non-Classical Logics, 8(1-2):107-121, 1998.


The following morphism and commuting morphisms explain why those two equations hold:

$h:c\rightarrow b^a$

commuting morphisms:

$eval: b_a\times a\rightarrow b$
$f:c\times a\rightarrow b$
$h\times id: c\times a\rightarrow b^a\times a$


What is the resulting set for {0,1}*\{0}*?

You are correct that the words not in $0^*$ are exactly those words which contain $1$ somewhere. You are also correct that you can represent this complement using the regular expression $(0+1)^*1(0+1)^*$. There are other regular expressions for the same language, for example $0^*1(0+1)^*$ (which is a "deterministic" regular expression).


what is the complexity of recurrence relation?

Yes, the answer is $\lg n \cdot \lg \lg n$:

Reason this out by expanding the recurrence and looking for a pattern:

\begin{align*}
T(n) &= 2T(\sqrt{n}) + \lg n \\
     &= 2( 2T( \sqrt[4]{n} ) + \log(\sqrt{n}) ) + \lg n \\
     &= 2\left( 2T(\sqrt[4]{n}) + \frac{1}{2} \lg n \right) + \lg n  \\
     &= 4T( \sqrt[4]{n} ) + 2 \lg n \\
     &= 4( 2T( \sqrt[8]{n} ) + \lg\sqrt[8]{n} ) + 2 \lg n \\
     &= 8T( \sqrt[8]{n} ) + 3 \lg n \\
\end{align*}
So as we continue expanding this and taking the square root of $n$, we will eventually bottom out where $n < 2$.  To figure out how many times we can take the square root of $n$, consider $n = 2^{\lg n}$, and on each recursive call, $n$ will have its square root taken.  Ending when $n < 2$ gives us:
\begin{align*}
2^{\frac{\lg n}{2^k}} &= 2 \\
\frac{\lg n}{2^k} &= 1 \\
\lg n &= 2^k \\
k &= \lg \lg n
\end{align*}

Giving a solution of $\lg n \lg \lg n$.

Alternatively, this can be solved via variable substitution and the Master Theorem.  Substituting $m = \lg n$:
\begin{align*}
T(2^m) &= 2T(2^{m/2}) + m \\
S(m) &= 2S(m/2) + m
\end{align*}
At this point the Master Theorem applies, with $a=2$, $b=2$, and $f(m) = m$.  Since
$m^{\log_b a} = m^{\lg 2} = m$, resulting in $f(m) = m = \Theta(m^{\log_b a})$.  Therefore case 2 of the Master Theorem applies, and the solution is $m \lg m$.  Substituting $m = \lg n$ gives us $T(n) = \lg n \lg \lg n$.

Edit: fixed a typo (needed to write this to exceed the minimum number of characters).


Automaton accepting $\{a^{2i}bc^{2k} \mid i, k \in\mathbb{N}\}$

Yes, it means exactly that. $i$ and $k$ are arbitrary natural numbers, so $2i$ and $2k$ are arbitrary even natural numbers.


Time complexity of an algorithm: Is it important to state the base of the logarithm?

It depends where the logarithm is. If it is just a factor, then it doesn't make a difference, because big-O or $\theta$ allows you to multiply by any constant.

If you take $O(2^{\log n})$ then the base is important. In base 2 you would have just $O(n)$, in base 10 it's about $O(n^{0.3010})$.


Is time complexity of the greedy set cover algorithm cubic?

Acc. to Introductions to Algorithms (3e), given a "simple implementation" of the above given greedy set cover algorithm, and assuming the overall number of elements equals the overall number of sets ($|X| = |\mathcal{F}|$), the code runs in time $\mathcal{O}(|X|^3)$. So there are cases when the algorithm behaves cubic.


Lower bound for merging $m$ sorted arrays (decision tree leaves count - permutations)

Stirling's formula shows that
$$
\binom{N}{pN} \sim \frac{2^{H(p)N}}{\sqrt{2\pi p(1-p)N}},
$$
where $H(p)$ is the binary entropy function:
$$
H(p) = p\log \frac{1}{p} + (1-p) \log \frac{1}{1-p}.
$$
In particular, this shows that for $k \geq 2$,
$$
\binom{kn}{n} = (1+o(1)) \frac{2^{H(1/k)kn}}{\sqrt{2\pi(1/k)(1-1/k)kn}} \geq (1+o(1)) \frac{2^{n\log k}}{\sqrt{2\pi n}}.
$$
Therefore
$$
\log \binom{kn}{n} \geq n\log k - O(\log n),
$$
where the big O doesn't depend on $k$. Summing this for $k=2,\ldots,m$, we deduce
$$
h \geq n \log m! - O(m\log n) \geq nm \log m - O(nm),
$$
using Stirling's formula again.


Explain better this new inventory for Word Sense Disambiguation

The paper says:

  "we also added the semantically-empty label named GENERAL to our inventory to cover the 135 categories that could not be included in any cluster."

I suggest you read that as though it had said

  we also added the label named GENERAL to our inventory to cover the 135 categories that could not be included in any cluster.  This label is not associated with one specific semantic meaning; it is a catch-all for the categories that could not be mapped to any of the other labels.


Proving NP-hardness of Hamiltonian Cycle problem variant

Your definition:

A relaxed-Hamiltonian cycle in $G$ is a closed walk $C$ that visits every vertex of G exactly once, except for at most one vertex that $C$ visits more than once (i.e. that vertex may repeated 2 or even more times).

I'll call this revisited vertex (for a given $C$) the nexus of $C$ and look at a case that shows that even if we know which node must be the nexus of any relaxed-Hamiltonian cycle, the problem is still NP-hard.
Consider two graphs $G_1,G_2$ for which finding a Hamiltonian cycle is NP-hard (which may be two copies of the same graph). Then we create $G$ by identifying a vertex in $G_1$ with a vertex in $G_2$, with the single vertex thus created called $w$. $w$ is an articulation vertex so $G$ cannot have a (standard) Hamiltonian cycle.

If a relaxed Hamiltonian cycle exists in $G$, it must have $w$ as its nexus. To visit all nodes in $G$, we have to visit $w$ and that is the only node which allows us to cross into $G_2$ and visit all nodes there. So we have the second (minimum) visit and $w$ is the nexus.
The definition of the relaxed Hamiltonian cycle means that we could in principle find disjoint cycles all including $w$ within either $G_1$ or $G_2$ and still meet the relaxed-Hamiltonian standard. We can avoid this case by ensuring that nodes in $G_1$ and $G_2$ that we pick for identification to create $w$ are maximum degree $3$, so we cannot re-enter a second cycle in the same graph part from $w$.
Then the problem of finding a relaxed Hamiltonian cycle in $G$ is as hard as finding Hamiltonian cycles in both $G_1$ and $G_2$ which we know can be NP-hard.
Further to your claim, we therefore know that if we find a relaxed Hamiltonian cycle for $G$ we have found a Hamiltonian cycle for both $G_1$ and $G_2$ (and $G_2$ is allowed to be a copy of $G_1$).


Using Context free language to simulate regular expression in finite automata

No such non-trivial bound can be obtained. Consider the language $L_n = \{ 0^{kn} : k \in \mathbb{N}\}$. Any NFA for $L_n$ needs at least $n$ states, but it can be generated by a context-free grammar with only one non-terminal: $S\to 0^nS|\epsilon$.


What are some fundamental issues computer science tries to address?

Computer science addresses the mystery of computation (but not computers): what is computable, what is not-computable, how difficult it is to solve certain problems, when are programs correct, how can programs be effectively written, what's the best way of solving problem X (for many Xs), ...


Proof By Contradiction - Hamiltonian Paths and Cycles

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

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

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


Is this the correct answer for the cardinality of this set?

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

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

So answer is $2^4 =16$


How to restore a broken minimal spanning tree?

This is just to confirm that OP has, in the course of updating his question, arrived at a well-written correct "algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$".


Let $OPT[t, x]$ be the maximum value of $\sum_{j=1}^t  b_j^{i_j}$  that can be attained by selecting one element $(a_j^{i_j}, a_j^{i_j})$ from each of the first $t$ sets with the constraint that $\sum_{j=1}^i  a_j^{i_j} \ge x$.
If the constraint cannot be satisfied, let $OPT[t, x] = -\infty$.

According to the above definition we have $OPT[0, 0] = 0$ and $OPT[0, x] = -\infty$ for $x > 0$.

For $t>0$ we have:
$$
OPT[t,x] = \max_{i=1, \dots, n} \left( b_t^i + OPT[t-1, \max\{x-a_t^i, 0\}] \right).
$$

The answer to your problem is "yes" if and only if $OPT[p, k] \ge k$.

Since there are $O(p \cdot k)$ subproblems, each of which can be solved in $O(n)$ time, the overall time complexity of this algorithm is $O(p \cdot k \cdot n)$.

To show that your problem is NP-hard, you can notice that it is a generalization of partition problem: given a set $S = \{x_1, \dots, x_m\}$ of $m$ non-negative integers, decide whether there is a subset $S'$ of $S$ such that $\sum_{x \in S'} x = \frac{1}{2} \sum_{x \in S} x$.

To see this, define $n=2$, $p=m$, $A_j = \{ (x_j, 0), (0, x_j) \}$, and $k = \frac{1}{2} \sum_{x \in S} x$.


I can't presume to speak for Perlis, but my intuition is as follows:

Recursion is descriptive

Especially at the time this was written, the specification of a recursive function seems much more descriptive than prescriptive, in the sense that a recursion describes a mathematical property we want the result to satisfy, rather than a series of computation steps. E.g. for mergesort

 sort(l) = let l1, l2 = split(l) in merge(sort(l1), sort(l2))

Recursion involves a notion of time

But obviously recursion also describes a process or series of steps. In the case of mergesort:

Split l into l1 and l2
then compute sort(l1) and sort(l2) (in either order)
then compute the merge of those two results
the result of this is the value we wished to compute

This suggests that the time taken by this computation is the time of each of these individual steps, which itself involves a recursive equation (over integers) to compute, namely the time taken to sort the sublists l1 and l2.

Trading description for time is the essence of computation

One way of characterizing computation is that we want to go from an abstract mathematical "timeless" description of an object to a concrete representation which can be manipulated symbolically.

Computation can be defined as the process which goes from the abstract to the concrete, and the time which this process takes is one of the central considerations of CS as a field.

My last advice is that sometimes it is important not to overthink epigrams or koans, but let understanding come naturally with experience.


Find a subgraph whose edge weights sum to at least the number of nodes

Your problem is very similar to the classical densest subgraph problem, in which you want to maximize the ratio $|E(S)|/|S|$. Goldberg gave a polynomial time algorithm for this problem based on network flow. Perhaps you can use his ideas to solve your specific problem as well.


What does it mean the norm symbol applied to a concept?

The only property that the functions $|\cdot|$ and $\|\cdot\|$ need to satisfy is that for every $n$ there is a finite number of $x$'s in the domain such that $|x|=n$ or $\|x\|=n$.
The difference between the two is the domain: $|\cdot|$ is defined on $\mathcal{X}$ while $\|\cdot\|$ is defined on $\mathcal{C}$.

These functions are instantiated on page 1115: for $\mathcal{X} = \Sigma^*$, $|\cdot|$ is the length of the word; and for $\mathcal{C}$ being the set of all DFAs on $\Sigma$, $\|\cdot\|$ is the number of states.


3D gift wrapping algorithm: how to find the first face in the convex hull?

For simplicity, let us assume no four points are in the same plane. Otherwise, adapt the following procedure to deal with the degenerated cases.

Define the usual lexicographic order on points. That is, for any two distinct points $P$ and $Q$, $P<Q$ if the $x$ coordinate of $P$ is smaller than that of $Q$, or, if their $x$ coordinates are equal, the $y$ coordinate of $P$ is smaller than that of $Q$, or, if both x coordinates and y coordinates are equal, the $z$ coordinate of $P$ is smaller than that of $Q$.

Iterate through all points, keeping tracking of three smallest points.
At the end of iteration, those three smallest points are the vertices of a triangle in the convex all.


Assuming round-to-nearest and that $N > 0$, then $N * R < N$ always. (Be careful not to convert an integer that's too large.)

Let $c 2^{-q} = N$, where $c \in [1, 2)$ is the significand and $q$ is the integer exponent. Let $1 - 2^{-s} = R$ and derive the bound

$$N R = c 2^{-q}(1 - 2^{-s}) \le c 2^{-q} - 2^{-q - s},$$

with equality if and only if $c = 1$. The right-hand side is less than $N$ and, since $2^{-q - s}$ is exactly $0.5$ units in the last place of $N$, either $c = 1$ and $2^{-q} - 2^{-q - s}$ is exactly representable (since $N$ is normal and not the smallest normal), or $c > 1$, and the nearest rounding is down. In both cases, $N * R$ is less than $N$.

Upward rounding can cause a problem, not that it should ever be selected in the presence of unsuspecting users. Here's some C99 that prints "0\n1\n" on my machine.

#include <fenv.h>
#include <math.h>
#include <stdio.h>

int main(void) {
    double n = 10;
    double r = nextafter(1, 0);
    printf("%d\n", n == (n * r));
    fesetround(FE_UPWARD);
    printf("%d\n", n == (n * r));
}


Type-system combining type-states and typed effects?

Edwin Brady has done some work in that area using dependent types in IDRIS. Take a look at his work, in particular Programming and Reasoning with Algebraic Effects and Dependent Types and Resource-dependent Algebraic Effects.


showing that the pair of Finite Automata are equivalent

Your approach works. You are effectively showing that the symmetric difference $L(FA_1) \Delta L(FA_2)$ is empty, hence $L(FA_1) = L(FA_2)$.

A more direct, automaton-level approach would be to build the following product automaton $A = (Q, \Sigma, \delta, q_0, F)$:

$Q = Q_1 \times Q_2$
$\delta((q_1, q_2), a) = (\delta(q_1, a), \delta(q_2, a)) \ \forall (q_1, q_2) \in Q, a \in \Sigma$
$q_0 = (q_{0,1}, q_{0,2})$
$F = \{(q_1, q_2) \in Q \mid q_1 \in F_1 \Leftrightarrow q_2 \in F_2\}$

Intuitively, you keep in mind the current state in both $FA_1$ and $FA_2$. Initially, the current states are the respective initial states $q_{0,1}$ and $q_{0,2}$. Then, for each input symbol $a$, you move to the respective successor in each automaton, and note the successor state (the combination of the two successor states as a pair). Of course you only draw the state for each combination only once. You can proceed either breadth-first (considering all input symbols for one product state before moving on to a newly introduced state) or depth-first (always continue with the newly introduced state and backtracking if all product successor already existed).

Note that this way you might not have to construct the full product set $Q_1 \times Q_2$, as you automatically prune unreachable states (you don't ever introduce them). However, the product automaton in your example will have no more than 6 states anyway, so it is rather small.


Complexity of set partition generation while equivalence relation is given

The binary equivalence relation induces an undirected graph: each item corresponds to a vertex, and draw an edge between each pair of equivalent items.  Now compute the connected components of this graph (this can be done in linear time using algorithms based on DFS).  Each connected component is a single subset in the partition.


Global Optimization of a well-defined function with gradient information

One alternative is to use Newton's method.  Newton's method uses information from the first and second derivative (i.e., the Hessian matrix), so it can converge in fewer steps than gradient descent (which uses only information from the first derivative) -- but the cost is that each single step is slower, because it requires more complex computations.

If Newton's method is too slow, there are faster variants, such as BFGS and other quasi-Newton methods or the conjugate gradient method.

Another approach is to continue using gradient descent, but make some adjustments.  One simple thing you can try is to apply it many times, each time with a different random starting point.  Also there are various tuning knobs you can tweak, such as adjusting the step size or using momentum.  A third possibility could be to try to make a "smarter" choice of starting point for gradient descent: you can approximate each cosine by a quadratic function (using the Taylor series expansion at a particular point), obtain a function $f^*$ that is a quadratic approximation to $f$, and then find the exact minimum for $f^*$ using least-squares method.  This basically amounts to applying one step of Newton's method and then continuing with gradient descent from there.

Trying several different methods shouldn't be too hard if you use the right software, as there are many software packages that let you specify the function and then make it easy to try multiple different optimization methods.


Trying to detect recurring events at certain intervals, e.g. daily, weeekly, monthly, annually

Given an event type and a sequence of times at which it has occurred, there are several ways to check whether it seems to recur periodically.

One simple approach is to look at the interarrival times (the time between each occurrence and the previous occurrence), and histogram those; if it is periodic, you'll see a sharp peak in the histogram.

Another approach is to use autocorrelation to detect periodicity.  See, e.g., https://en.wikipedia.org/wiki/Autocorrelation.  The Fourier transform can be useful here.


Dijkstra and A* Algorithms: Why is A* faster?

I absolutely don't understand the attached images and what you try to do on it. What I can say is that Dijkstra an A* algorithm are pathfinding methods:

Dijkstra algorithm is an exploration method that let you find the shortest path to any vertex of the graph. The idea is to always consider the vertices that you reach from the cheapest (closest) node of the queue.

You may run this algorithm to find the shortest path from a specific node $s$ to a specific node $t$. But you can also use it to determine global properties of the distances from $s$. Or for instance, build a tree that let you backtrack the path from $s$ to any vertex.

A* algorithm is basically a Dijkstra method that use an additional heuristic to sort the nodes of the queue. On distance problem, this heuristic is generally based on the euclidian distance from the node to the aim. It favorises the exploration of the nodes that are more likely to go in the good direction. So this specialization of Dijkstra algorithm is only used to go from a specific node $s$ to a specific node $t$. It is generally largely faster but does not guarantee to find the optimal path (in the ver).

I suggest you play with this  pathfinding simulation tool


Is an NP-hard problem which is in NP is NP-complete?

Check the definitions of NP-completeness and NP-hardness. I suspect they use Karp reductions for one and Cook reductions for the other.

Then, the quote makes sense: it is indeed unknown if Cook reductions and Karp reductions are equivalent in this sense. This is related to the question whether co-NP = NP; Cook reductions can not separate the two but Karp reductions might. See here for some details.

However, the authors use different definitions than (most of) the rest of the CS world: the widely accepted standard is to use Karp reductions. I recommend you read our reference question (and get a better book).

To be fair, the authors want to talk about optimization problems, in which case they need a notion of (NP-)hardness that is not tied to decision problems. Karp reductions won't get them there directly.

They picked a poor way out, arguably, by defining the notions differently from everybody else. There are cleaner (but more involved) ways, defining complexity classes for optimization problems rigorously, providing them with their own types of reduction, and tying them to the classic decision-problem classes using threshold languages.


What complexity class is this set of grammars?

Every unrestricted grammar can be converted to one with the following types of rules:
$$
AB \to CD \\
A \to BC \\
A \to a \\
A \to \epsilon
$$
Wikipedia calls this Kuroda normal form for unrestricted grammars.

You can convert a rule of the form $AB \to CD$ to a pair of rules $AB \to X_{ABCD}$, $X_{ABCD} \to CD$. Following the OP's suggestion, we can convert $A \to \epsilon$ to the rule $A \to E$, and add rules $BE \to B$ and $EB \to B$ for any nonterminal $B$. This allows us to obtain a grammar in your form equivalent to the original one, up to not being able to generate $\epsilon$.


Synchronization based on test-and-set requires a shared data storage location that all the involved threads can read and modify.  Your shared register is a shared data storage location.

The reason synchronizing on a register when the threads are running on different CPUs is that the register would not be shared (not be visible) to one of the threads.  You should think of registers as memory locations with some features removed to make them faster.

In fact, something similar to your scenario was possible on SPARC processors.  The SPARC had a large register file (something like 64 or 128 registers) with 8 registers that were always visible and then 24 register "windows" into the rest of the register file.  Usually these windows were used to implement fast stack frames, but there were several experimental runtime systems that used the windows to support multiple threads.


How to get an element from an existential proposition in Type theory proof assistant (Lean prover)

The existential form of the axioms of set theory is convenient for the meta-theoretic explorations of set theory, such as forcing etc., where it is important to have a minimal language to worry about (only $\in$ relation). But even just stating the axioms of set theory without any constants and operation symbols is pretty haunting, see this gist of mine.

If you want a workable set theory you will have to rephrase your axioms so that they are not existential statements but rather operations. For example, define a union : Set → Set → Set operation and an axiom which states that u ε union X Y ↔ u ε X ∨ u ε Y. Formally, set theory does not have these operations, but every single development of set theory relies on the meta-theorem which says that introducing such constants is conservative (they can be eliminated). Also for the inductive set, introduce a constant S : Set and the axiom inductiveset S.

As a general advice, when formalizing mathematics in a proof assistants, one has to be quite flexible about organization of material. Traditional organization is good for teaching and writing textbooks, and so it may not align well with the demands of formalization.

For example, it looks to me at first sight that you would benefit by formalizing not only sets, but also classes. The class comprehension notation $\{ x \mid \phi(x) \}$ is very expressive and convenient, and easily formalized in terms of propositional functions on $\mathsf{Set}$. With it, you can define many operations on classes and then state that they are sets in terms of axioms. For example, rather than axiomatizing a union operation we just define union X Y to be the class {u | u ε X ∨ u ε Y} and then state that this class is a set. I suppose you could look at Von Neumann–Bernays–Gödel set theory.


Maximum sum difference between two sorted array elements under one condition

Two sets A and B.  Using i and j only once maximize the ∑(a[i] - b[j]).  Not required to use and i and j.

I don't know if this is a hard proof but

For $A[i] > B[j]$
∑(a[i]−b[i])  =  ∑(a[i]) - ∑(b[i])

So the problem is reduced to maximize $A[i] > B[j]$
Reverse sorting maximizes the number of $A[i] > B[j]$

Or another way to say it
maximizes ∑(a[i]) and minimizes ∑(b[i])
Descending sorting maximizes ∑(a[i])
Ascending  sorting minimizes ∑(b[i])


"Immediate" method of translating arbitrary mutable program to equivalent unmutable program?

The state monad allows us to translate any stateful (you call it "mutable") program to a pure one. The changes required to the program are "local" in the sense that you only need to make superficial changes to the syntax, assuming you use Haskell-style do notation. For example, the following is the Haskell translation of your program into a pure program:

do x <- 1
   x <- f x
   x <- f x

You think you can make your transformation by renaming variables, but this will not do when recursion or loops are involved. For example, it is not clear how to use your idea here:

s = 0
i = 0
while (i < n) do
   s = s + i
   i = i + 1
done

Following your scheme we get the non-sensical:

s1 = 0
i1 = 0
while (i1 < n) do
   s2 = s2 + i1
   i2 = i2 + 1
done

You need to think more carefully about your idea (and I don't see how to make it work).


How does one deduce small step operational semantics?

Devising an operational semantics of a programming language requires ingenuity, just like engineering a new car does. Nevertheless, there are some principle and correctness criteria by which we can judge whether a given semantics is "good".

For example, a good operational semantics should make sure that "valid programs do not do bad things". In practice this translates to "if a program succesfully compiled it is not going to dump core when we run it". Some languages are unsafe in this respect (C/C++), some are designed with safety in mind (Java, Python), and some are proved to be safe (Standard ML).

One way of translating "valid programs do not do bad things" is to interpret "valid program" as "well typed program" and "bad thing" as "getting stuck during evalution, even though we have not reached a final value". For this to make sense you have to define what "well typed" and "value" means. The central theorem then is

  Safety: If a program $p$ has type $\tau$ then its evaluation diverges or terminates in a value of type $\tau$.

The theorem is typically proved by combining two lemmas:

  Type preservation: If $p$ has type $\tau$ and $p \mapsto p'$ then $p'$ has type $\tau$. Remember this as "types do not change during evaluation".

  Progress: If $p$ has type $\tau$ then it is either a value or there is a program $p'$ such that $p \mapsto p'$.

On the other hand, it does not matter what the operational semantics does with senseless programs, such as $\mathtt{pred}(\mathtt{false})$ because those do not have a type. It is the combination of typing and operational semantics that ensures safety. You cannot ensure safety just with the operational semantics, unless you are willing to make bizarre evaluation rules that will make your language awfully hard to debug.


TL;DR: You don't have to worry about seek times with SSDs like you do with hard disks.  As a first-order approximation, you can think of them as random-access devices.

SSDs let you read and write entire blocks.  There is some cost to read/write a particular block (usually under 0.1ms).  Once you're reading or writing a block, it's a lot faster to read/write the rest of the block.

As a consequence, SSDs are almost like random-access devices -- but there is some advantage to having data that will be accessed simultaneously be in the same block, so it does matter to some extent how the data is stored on the SSD.

To dive into some more specifics: A SSD is composed of a bunch of erase blocks (think 512KB or so).  Each erase block consists of multiple write pages (think 4KB or so).  A SSD supports three operations: read at some location;  erase an entire erase-block (making all of those write-pages "blank"); and write to an write-page that is currently "blank".

There's no way to to modify just part of a page.  Instead, this is implemented by reading the entire page into RAM, modifying it, writing the entire thing to a blank page, and updating some filesystem data structure to point to the new page instead of the old page.

As a consequence, it's best if writes are clustered at the granularity of the underlying pages.  Small, random-access writes are slower; long, sequential writes are faster.  Many SSDs contain some kind of cache or "write combining" to try to reduce the impact of this.

To give some example performance numbers: it might take 0.05-0.1 ms to read an entire page, 0.3-1 ms to write a page; and 1-3 ms to erase an erase-block.  These are just examples -- don't take them too seriously.  Actual performance will vary from device to device.

More reading:

https://en.wikipedia.org/wiki/Flash_file_system

Design Tradeoffs for SSD Performance.  Nitin Agrawal ∗ , Vijayan Prabhakaran, Ted Wobber, John D. Davis, Mark Manasse, Rina Panigrahy.  Usenix ATC 2008.

Understanding Intrinsic Characteristics and System Implications of Flash Memory based Solid State Drives.  Feng Chen, David A. Koufaty, Xiaodong Zhang.  SIGMETRICS/Performance 2009.

https://en.wikipedia.org/wiki/Write_amplification


Is there an algorithm for converting Turing machines into equivalent Lambda expressions?

All proofs of the equivalence of these two models of computation are constructive, that is they describe an algorithm for converting a program from one model of computation to the other. However, I caution you that these proofs are probably rather informal, and may not satisfy you. You may get luckier if you consult original work by computing pioneers (Turing, Church, Post, Kleene and their ilk).


EQ_{TM} is not Turing recognizable, but we can reduce A_{TM} to it?

Note that $EQ_{TM}$ is the language of machines that recognize the same language (they are not necessarily equivalent).
You said

But we can also reduce $A_{TM}$ to $EQ_{TM}$ itself, that means: $EQ_{TM}$ and $NEQ_{TM}$ are not disjoint since we can reduce $A_{TM}$ to the two of them?

This is far from being true, if there are reductions from a language $A$ to two languages $B$ and $C$, this does not say anything about $B\cap C$ as the reductions need not be related. To be concrete, it is shown here that every non-trivial language is $\text{R}$-hard, so clearly, you cannot claim that every two non-trivial languages intersect.
You also said

And also, $EQ_{TM}$ is not Turing recognizable but it contains some instance that is turing recognizable since we can reduce $A_{TM}$ to it?

Clearly, $EQ_{TM}$ contains some instances $\langle M_1, M_2 \rangle$, where it is easy to check whether $L(M_1) = L(M_2)$ (for example, all instances where $M_2$ is identical to $M_1$ with some new unreachable states). Also, you're right, this indeed can be thought of a consequence of the existence of a reduction from $A_{TM}$ to $EQ_{TM}$. Formally, we have the following claim (I leave it to you as a good non-trivial exercise), and thus the image of the reduction (which is a subset of $EQ_{TM}$) is in $\text{RE}$.
Claim: Let $f: \Sigma^* \to \Sigma^*$ be a computable function and let $L\subseteq \Sigma^*$ be a language in $\text{RE}$. It holds that $f(L) = \{ f(x): x\in L \}\in \text{RE}$.
BTW, complement languages, by definition, have empty intersection.
So, regarding the question in the title, you can reduce $A_{TM}$ to $EQ_{TM}$ (here is a hint: there they asked about a reduction from the halting problem, but the hint is also good for your case), and being able to define such a reduction does not contradict anything.


Defining a "repeat until"-construct in Denotational semantics

Presumably you mean $\lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack$, which you can easily define using $\text{while}$ as follows.

$$
\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack =
\mathcal{S}_{\text{ds}} \lbrack\lbrack S ; \text{while } \lnot b \text{ do } S\rbrack\rbrack
$$

Note that typically, a $\text{repeat}$ construct loops while the condition is false; your definition keeps the condition positive.

Building on the above equation and expanding the right-hand side using the table on page 86, you get:

$$
\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack =
(\text{FIX }F)\circ \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\\ \text{where }F\ g = \text{cond}(\mathcal{B}\lbrack\lbrack \lnot b\rbrack\rbrack , g\circ\mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack, id)
$$

You can transform the above to the following.

$$
\mathcal{S}_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack =
\text{FIX }F\\
\text{where }F\ g = \text{cond}(\mathcal{B}\lbrack\lbrack \lnot b\rbrack\rbrack, g, id)\circ \mathcal{S}_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack
$$

Your version is not correct in this regard, it would be equivalent to $\lbrack\lbrack \text{while } b \text{ do } S;S\rbrack\rbrack$, which evaluates the condition before rather than after the first execution of $S$.


Is it possible to sort a linked list without copying its values but linking the nodes?

Copy the list into an array, sort the array, construct a linked list from it.   Done.  It suffices to populate the array with pointers (references) to the values; you don't need to copy the values themselves. The running time will be $\Theta(n \log n)$ if you use an appropriate sorting algorithm -- much faster than quadratic time.


An algorithm that finds ord(a) in $O(\log n)$

Suppose that $\phi(n) = 2^m$; note $m \leq \log n$. The order of $a$ is thus $2^k$ for some $k \leq m$; in fact, it is the minimal $k$ such that $a^{2^k} \equiv 1 \pmod{n}$. You find find this $k$ by repeatedly squaring $a$.


Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]

I will change your function a bit, because there is too much going on with swaps and there is variable recursionNestingLevel which is not really declared or needed.

FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

Now there is a simple idea to prevent recursing over same elements - it eliminates first unnecessary swap of and all redundant calls when array[index] is equal array[nesting level]:

FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
+       IF array[index] EQUAL array[nestingLevel] CONTINUE
+       array = CLONE array
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

CLONE here prevents passing by reference of array, which would propagate changes to every recursive call

When you prevent swapping same elements and calling permute, it effectively blocks call with same parameters, so there are no duplicates.
BTW I have tested this code, for [1, 1, 2] it yields [ 1, 1, 2 ], [ 1, 2, 1 ], [ 2, 1, 1 ], with JavaScript


Show that the running time of the build_heap function is $O(n)$

The main point is to do the analysis exactly without being sloppy. Let me define the depth of a node in this way. Depth of any leaf is 0 and depth of any non-leaf node is maximum depth among its children plus 1. One can note that
depth = $\log n - $ height.

Then for a particular node how much time does heapify take? By definition of depth you can see it is order of depth of the node.

Now the total time for buildheap is $$\sum_{d=0}^{\log n} \text{(number of nodes of depth d)}\cdot O(d).$$

Now my claim is that there are at most $n/2^d$ nodes at depth $d$ (can you see why?). For example number of leaves (depth 0) is at most $n/2^0 = n$.

Then, building time is
$$ \sum_{d = 0}^{\log n}  \frac{n}{2^d} \cdot O(d) = O(n)\cdot\sum_{d = 0}^\infty  \frac{d}{2^d} = O(n) \cdot 2 = O(n). $$


Direct edges of undirected graph so that all indegrees are even

Orient all edges in an arbitrary fashion, and add a $0/1$ variable $x_{u,v}$ for each edge $(u,v)$, with the following meaning: $x_{u,v} = 0$ means that we use the orientation $u \to v$, and $x_{u,v} = 1$ means that we use the orientation $u \gets v$. The parity of the indegree of $u$ is equal to
$$
\sum_{(u,v) \in E} x_{u,v} + \sum_{(w,u) \in E} (1 + x_{w,u}) \pmod{2}.
$$
Let $p_u$ be the parity of the number of edges of the form $(w,u)$. Then we can formulate the task as follows:

  Assign $0/1$ values to the edges so that the sum of weights of edges adjacent to $u$ is $p_u$ (mod 2).

As an example, consider your sample graph, with edges
$$
(1,2), (1,3), (2,4), (3,4).
$$
We have $p_1 = 0$, $p_2 = 1$, $p_3 = 1$, $p_4 = 0$. We are looking for a solution (mod 2) of the following system:
$$
\begin{align*}
&x_{12} + x_{13} = 0 \\
&x_{12} + x_{24} = 1 \\
&x_{13} + x_{34} = 1 \\
&x_{24} + x_{34} = 0
\end{align*}
$$

One such solution is $x_{12} = x_{13} = 0$, $x_{24} = x_{34} = 1$. This is exactly the solution that you describe.

If you sum all equations, then all the edges cancel, and you get $\sum_u p_u = 0 \pmod{2}$. This gives a necessary condition for the existence of a solution. It turns out that this condition is also sufficient, assuming the graph is connected (otherwise, you need a similar condition for each connected component). A solution can be found using linear algebra modulo 2.

This is related to the so-called Tseitin contradictions in proof complexity, which correspond to assignments of the weights $p_u$ for which no solution exists.


The following answer is incorrect.

Suppose the triangle has vertices $(x_1,y_1,z_1), (x_2,y_2,z_2), (x_3,y_3,z_3)$ and the box has coordinates $[x_\min, x_\max] \times [y_\min,y_\max] \times [z_\min, z_\max]$.  Then the bounding box of their intersection is $[x'_\min, x'_\max] \times [y'_\min,y'_\max] \times [z'_\min, z'_\max]$, where
\begin{align*}
    x'_\min &= \max\{\min\{x_1,x_2,x_3\}, x_\min\}, \\
    x'_\max &= \min\{\max\{x_1,x_2,x_3\}, x_\max\}, \\[1ex]
    y'_\min &= \max\{\min\{y_1,y_2,y_3\}, y_\min\}, \\
    y'_\max &= \min\{\max\{y_1,y_2,y_3\}, y_\max\}, \\[1ex]
    z'_\min &= \max\{\min\{z_1,z_2,z_3\}, z_\min\}, \\
    z'_\max &= \min\{\max\{z_1,z_2,z_3\}, z_\max\}. \\[1ex]
\end{align*}


Using bit arrays to solve crossword puzzles

Suppose we are looking for the set of all words of length 5 with a in first position and b in second position (an example is the word about).

Our lexicon contains up to $N = 2000$ words of each length. For each length, for each position in the word, and for each possible letter, we store the set of words of given length in which the letter at the given position is the given letter.

For example, suppose that there are 100 words of length 5. We identify these words with the numbers 1,2,...,100. There is an array of length 100 in which the $i$'th value is 1 if the $i$'th word starts with a, and 0 otherwise. There is another array of length 100 in which the $i$'th value is 1 if the second letter of the $i$'th word is b, and 0 otherwise. We can take these two arrays and compute their entrywise AND:
$$
\begin{array}{l|l}
\text{First array}  & 01110010\ldots \\
\text{Second array} & 11010011\ldots \\\hline
\text{Result}       & 01010010\ldots
\end{array}
$$
The $i$'th value of the new array is 1 iff the $i$'th word starts with ab.

Bit arrays are a space-efficient way to store Boolean arrays like the two arrays considered above, which also support fast operations like bitwise AND. The idea is simple – you store every value as one bit.


Testing regular expressions algorithmically

Hint: Check whether there is a path from the starting state to some accepting state.


It is $\beta$-reduction defined in terms of substitution (rename ($\alpha$-conversion) first if necessary):

$$(\lambda z. zq) (q) \to_{\beta} [z/q](zq) = qq. $$

In Haskell, $\lambda z.zq$ defines an anonymous function which takes a single parameter (represented by $z$) and performes $zq$.


Negative edge weights in Dijkstra and Bellman Ford shortest path algorithms

Then why texts say that Dijkstra need all non negative edge weights?

Because it has to work for all cases, not only a few examples.

  I feel that it should be no -ve edge weight cycle reachable from source node.

Try proving that claim and see where it leads. If you're successful, great; if not, trying to prove the opposite will fix your intuition.

See also here for a high-level argument.

   The smallest example where Dijsktra fails has four nodes, no (directed) cycle at all, and no negative-value cycle:


Topological Sort without modifying the graph or marking edges

Instead of seting a 'mark' flag;

 node.Marked = true;

You can maintain a set of marked nodes in a hashtable or similar;

 hashTable[node] = true;

You now have to pass the hash table around, but it's O(n) for space and O(1) to check if a node is marked.


Multiple Dimensions

For a recursive counterpart for matrices, we need dependent types.

Indeed, lists are one dimensional and so (horizontal) concatenation of lists is all that is needed. However, matrices are two dimensional and so concatenation may be meaningless if the sizes do not match up. That is to say, all rows need to have the same number of columns and likewise all columns need to have the same number of rows for a matrix to be (conventionally) meaningful. I mean, for example, usually no one thinks of, say, two rows that have two different length columns as being a matrix.

A Quick Implementation

So for concatenation, we need to keep track of the lengths. We can do so by using a language that supports dependent types, such as Idris or Agda. Haskell can mimic them, but a difficult task onto itself. So here's a naive implementation in Agda.

data Matrix (A : Set) : (rows columns : ℕ) → Set where
  ∣_∣ : A → Matrix A 1 1
  _Φ_  : ∀ {r c₁ c₂} → Matrix A r c₁ → Matrix A r c₂ → Matrix A r (c₁ + c₂)
  _⊝_  : ∀ {c r₁ r₂} → Matrix A r₁ c → Matrix A r₂ c → Matrix A (r₁ + r₂) c

The first constructor embeds the type A into 1-by-1 matrices and the other two constructors are for horizontal and vertical concatenation. Notice that the natural numbers are used to keep the matrices meaningful. For example, you can stick two matrices side-by-side to produce a wider matrix precisely if the two have the same number of rows.

For example, the 2-by-2 identity matrix

id₂ : Matrix ℕ 2 2
id₂ = (∣ 1 ∣ Φ ∣ 0 ∣) ⊝
      (∣ 0 ∣ Φ ∣ 1 ∣)

Map

In one of the above comments, you remark that its troubling that we cannot pattern match and define recursive functions. Well, we can :-)

For example, the usual map of lists has a matrix counterpart.

map : ∀ {A B} (f : A → B) → ∀ {c r} → Matrix A r c → Matrix B r c
map f ∣ x ∣ = ∣ f x ∣
map f (m Φ m₁) = map f m Φ map f m₁
map f (m ⊝ m₁) = map f m ⊝ map f m₁

toString : ℕ → String
toString zero = "Zero"
toString (suc zero) = "One"
toString _ = "just no"

map-test : map toString id₂ ≡ (∣ "One"  ∣ Φ ∣ "Zero" ∣) ⊝
                              (∣ "Zero" ∣ Φ ∣ "One"  ∣)
map-test = refl

More Involved Example

As a more complicated example, let's consider matrices made by a single constant ---compare to Haskell's repeat operation that takes an element e and returns a list [e,e,...,e].

 : ∀ {A} → A → ∀{r c} → Matrix A (suc r) (suc c)
 e {0} {0} = ∣ e ∣                     -- 1x1 singleton matrix
 e {0} {c + 1} = ∣ e ∣ Φ  e             -- row-vector of length r+1
 e {r + 1} {0} = ∣ e ∣ ⊝  e             -- column vector of length r+1
 e {r + 1} {c + 1} = (∣ e ∣ Φ  e) ⊝  e -- (∣ e ∣ ⊝  e {m} {0}) Φ  e {m+1}{c}

The last one says:

                   (    e  |  e   )
 e {r+1} {c+1} =  (  ------------- )
                   (  e {r} {c+1} )

Indeed any × matrix can be construed as the vertical concatenation
of an -row vector above an (-1)× matrix ---note a recursion!
In this case, our row vector is the element e followed by an r-row vector of e's.

Example usage:

test :  5 {2} {2}
   ≡   (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣) ⊝
       (∣ 5 ∣ Φ ∣ 5 ∣ Φ ∣ 5 ∣)
test = refl

Sources

Of course, the implementation was brief and just to answer your question.
A more full account can be found in the elegant lecture notes of Richard Bird.

Hope this helps!


You could use 4 neurons to produce a 4-bit output, which then represents the digit in binary.  A digit in the range 0-9 can be expressed in binary as a 4-bit number.

However, classification accuracy might potentially be worse than the standard method of 10 output neurons with a softmax layer.


Why do these functions satisfy that f(n) is not O(g(n)) and g(n) is not O(f(n))?

Let's firstly imagine function $f$: for $k=2$ we have two intervals $(4,5)$ and $(5,6)$ and for $k=3$ we have two intervals $(6,7)$ and $(7,8)$. Accordingly for $f$ we have:
$$\quad\quad\quad   x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\
f(x)\quad  2^4\quad\quad 2^5\quad\quad\quad 3^6 \quad\quad3^7$$
for function $g$ we have:
$$\quad\quad\quad   x\quad\ \overbrace{(4,5)\quad (5,6)}^{k=2}\quad\overbrace{(6,7)\quad (7,8)}^{k=3} \cdots\\
g(x)\quad  2^2\quad\quad 2^6\quad\quad\quad 3^4 \quad\quad3^8$$
So, as you see both $f$ and $g$ are increasing, but alternately one is more then  other with more then constant factor, so they cannot be big-$O$ of each other.
To get an idea of an example you can take a look at DNA molecule chain  and imagine, that $f$ is one line and $g$ another.


a regular language so that $unary(L) \notin $Context Free Languages

Let $L = 10^*$ and observe that $$\text{unary}(L) = \{ 1, 11, 1111, 11111111, \dots\} = \{1^{2^i} \mid i \in \mathbb{N} \}.$$

Can you prove the rest yourself?


Understanding the state vector in Quantum Computing

No, it's not correct.  It's not true in general that one entry will be 1 and all others 0; that is true for the basis vectors, but there are other states (other vectors) where that isn't true.  You can have linear combinations of the basis states, e.g., the following is a possible state:

$${1 \over \sqrt{2}} |0\rangle + {1 \over \sqrt{2}} |1\rangle.$$

It corresponds to the following vector in the vector space:

$${1 \over \sqrt{2}} (0,1) + {1 \over \sqrt{2}} (1,0) = (1/\sqrt{2},1/\sqrt{2}).$$

Because of this, you can have infinitely many possible states in this vector space.

The vector space is not $N$-dimensional.  The dimension of a vector space has a formal definition, and if you apply it, you will discover that the dimension of the vector space is $2^N$.


Is $(n^5 + n^7)\in \Omega(n^7)$? Shouldn't it be in $\Omega(n^5)$?

The function $n^5 + n^7$ is big-$Ω$ of both. However, it is little-$\omega$ of $n^5$.

It happens that $n^5 + n^7 \in \Theta(n^7)$. These asymptotic-notations only describe the behavior of the function $f(n) = n^5 + n^7$ for large $n$, aka "for all $n > \textrm{some value}$". The function is a polynomial function, and the highest-degree term determines the order of growth.

From the definition of $Θ(g)$, it means that function $f$ is both big-$O$ and big-$Ω$ of $g$. The function is bounded by some constant multiple of $n^7$ for large $n$. Namely, the function is bounded above by $2n^7$ and below by $n^7$.

Nevertheless, $n^5 + n^7 \in \Omega{(n^5)}$; the function is of [strictly] greater order than a quintic. Equivalently, $n^5 \in O(n^5 + n^7)$.


One plausible approach is to use edit distance to measure the similarity of two titles.  You might want to adjust it to reduce the penalty for capitalization (e.g., changing x to X might cost 0, or some very small amount).
Then, given a human-entered title, you need a way to find the closest match in the database.  There are various data structures and techniques for this.  See, e.g., shingling, BK trees, metric trees, Efficient map data structure supporting approximate lookup, Efficient data structures for building a fast spell checker, https://cstheory.stackexchange.com/q/4165/5038, http://norvig.com/spell-correct.html.
Another heuristic might be to extract each word from the human-entered title, canonicalize it (e.g., spelling correction, lower-case it, etc.), then look it up to find the first 1000 titles in the database that contain this word.  Take the union of those titles from the database, compare each to the human-entered title using edit distance, and keep the closest match.


Number of optimal solutions for Longest Common Subsequence (Substring) problem

Consider the following two strings:
$$
s_1 = (abc)^n, s_2 = (bac)^n.
$$
You can show that the longest common substrings of $s_1,s_2$ have length $2n$. There are at least $2^n$ of these: $\sigma_1 c \sigma_2 c \ldots \sigma_n c$, where $\sigma_i \in \{a,b\}$.


An algorithm to generate all connectible pair combinations

Model the whole thing as a directed graph.

Currences are nodes.
Conversions are edges.
Conversion factors are edge weights.

So, in your example, you'd have nodes EUR and USD, and edges from EUR to USD with weight 2  resp. from USD to EUR with weight 1/2.

Now, every (directed) path from one currency to another represents a potential series of conversions, and the total conversion factor is the product of all traversed edge weights.

Note that, in general, there are super-exponentially many such paths so you probably do not want to list them all. Furthermore, finding the "longest" path may be NP-hard.


modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

I assume you want to only calculate shortest paths, starting from $s$, to vertices in its 3-hop neighborhood, i.e. vertices which are reachable from the start vertex $s$ with a path length $\leq 3$.

Use a limited breadth-first search and save the frontier vertices in a queue which is sorted according to its edge-weights. By doing that you have a priority queue and can update vertices like in the regular Dijkstra's algorithm. Note that you need to keep track of the current depth of the breadth-first search.


I have contacted Inman Harvey from the University of Sussex and here is his answer to my question:

  In your example you have given each genotype $6 \,\,\,\, 2$-bit 'genes'. Let's look at how different your example parents $P$ and $Q$ are:

  In genes $2 (01)$ and $3 (00)$, the genes are identical in $P$ and $Q$
  In genes $1, 4, 5$ and $6$ the $2$-bit genes differ

  Ie $2/3$ of the genes differ between parents.

  If you have $1$-point crossover at any of $12$ positions on the genotype (including here the non-functional case where the crossover-point is 'off-the-end', then:

  $6$ of the possible crossover points are between-genes and hence do not count as sort-of mutations.
  $2$ of the possible crossover points are within the $2$-bit genes that are identical in $P$ and $Q$ – hence do not result in any 'crossover-style-mutation' in $Q'$

  $4$ of the possible crossover points are within non-identical genes, and hence DO result in a crossover-style-mutation in $Q'$.

  So -- with your specific example, $4$ out of $12$, ie $1/3$ of the time, crossover will produce a crossover-style-mutation. Sounds a lot. Sounds like maybe you should be worried about this in terms of impacting on effective mutation rates...

  BUT WRONG!! Your example was atypical. You will find in practice, after only a few generations of evolution, your parents $P$ and $Q$ will be genetically very similar to each other. This is the basic SAGA insight, see any of my papers with SAGA in the title. If you doubt this, then run any binary-style GA for as few as $10$ generations and check on how similar any $2$ randomly chosen parents are. It won't be (as in your example above) $67\%$ of genes differing between parents, it will be more like order of $1\%$ (if your genotypes are say $100$ bits long) differ between parents. Don't believe me, run the tests yourself, it is very easy to do!

  ... and hence your concern about these crossover-style-mutations should, I suggest, diminish to near vanishing point when you take account of the reality that most parents have mostly identical genotypes.

  Anecdotally and simplistically, if human genotypes are $98\%$ similar to chimpanzee genotypes, then you should expect your average human-human parental couple to be $99.99\%$ genetically identical, and only $0.01\%$ open to the possibilities that worry you above (that $\sim 0.01\%$ is of course important and interesting for different reasons). Elephant mating with a flea, then you can expect problems -- in fact what you are discussing above relates closely to inter-species breeding problems. Your standard $GA$ does not run into such problems.

I hadn't thought of it this way. So in fact crossover operators may introduce unwanted mutations in early generations (depending on how they are implemented) but these mutations will have little, if any, effect on the actual optimal mutation rate.


Why do some filesystems have fragmentation and others don't?

I think the term inode is misplaced here.  I am unaware of any way in which Inodes have anything to do with optimizations to reduce disk fragmentation.  The term inode goes back to Unix Version 1 from 1971.  It was not until the Berkeley Fast File System in BSD 4.2 in 1983 that anything significant was done to combat disk fragmentation.  In Unix systems the term inode refers to the data structure that holds all the metadata for a file (its length,  permissions, owner, and the pointers to the data blocks for the file (arranged as a tree in most Unix file systems since 1983.)  The file name is not stored in the inode.  Rather directory entries contain the name and an inode number.

NTFS has a data structure analogous to the inode, that contains similar information, and similarly does not contain the file name.  In NTFS this structure is called a master file table entry.   Given the similarities between an inode and NTFS's master file table entries, I can't see any impact on any kind of fragmentation.  FAT also has a similar data structure, the directory entry.  Unlike NTFS and Unix inodes, the FAT directory entry contains the file name along with all the other file information.  Putting the file name with the rest of the file metadata has both positive and negative consequences, but I can't figure out how this difference would have any bearing whatsoever on disk fragmentation.

In fact FAT has a subtle (and not very important) advantage over NTFS and most Unix file systems with inodes.  In systems with inodes (or NTFS's master file table), the inodes are allocated in inode tables, and in some systems (like Linux's ext2) you had to choose the ratio of inode tables to data blocks.  This meant that if you had more small files than you expected you might run out of inode entries even though more data space was still available, and if you have larger files than expected you might run out of data space even though there is empty space allocated for unused inode tables.

Every filesystem has disk fragmentation.  Your perception of which actually suffer from real problems may not be completely accurate.  For example: NTFS has an interface specifically designed to make it easier to write user-level defragmentation utilities that can keep serving file requests while defragmentation is going on, while ext4 (the most commonly used file system on recent Linux systems) does not.  That doesn't necessarily mean that ext4 has less disk fragmentation than NTFS, it just means that if an ext4 file system gets fragmented there is nothing you can do about it.  Both ext4 and NTFS have a number of optimizations to reduce the probability of serious disk fragmentation problems.

You should think of a filesystem as a data structure with a set of algorithms for modifying the data structure.  As with any other data structure the designer needs to trade off a variety of different desirable and undesirable traits.

One of the decisions a filesystem implementation needs to make is block size.  With larger blocks larger chunks of data are guaranteed to be adjacent.  On the other hand, it is rarely the case that a filesystem allows a block to be used by more than a single file at a time (the FreeBSD UFS2 system (c. 2003) being an exception), so if you choose larger blocks but then have many small files those files are going to be spread further apart on the disk (this is so called internal fragmentation.)

Almost every modern file system (including NTFS, HFS+ (Mac), UFS2 (FreeBSD), ZFS (Solaris) and ext4 (Linux)) has a variety of heuristics included to help reduce the number of disk-head movements required during a complete file access.  These include allocating a file's data near its inode, locating the inode near the directory that contains it, and allocating adjacent blocks for data writes that are known to be longer than a block.  Journaling file systems try to combine together many small writes into larger chunks that can be written to adjacent blocks.

Some file systems implement delayed allocation, which permits them to decrement the free-space counter for the disk when the space is requested, but delay choosing which block to write the data to until the time at which the data needs to be flushed from data to memory.  This requires coordination between the file system and other parts of the operating system.  The wikipedia article does not list NTFS as performing this optimization (and FAT system almost certainly don't bother with anything that sophisticated.)

Another thing you should take into account is whether the file system is going to be used on a hard disk or on a solid-state drive (or flash drive).  Disk fragmentation does not matter for solid state drives (because there are no mechanical delays, so every block is equally fast to access).  On the other hand for solid-state/flash drives wear leveling matters a lot.


Determining asymptotic running time by profiling

If you remove the 200ms overhead, you get
$$
\begin{array}{c|ccccc}
n & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} \\
t & 100 & 300 & 900 & 2700 & 8100
\end{array}
$$
This shows that when $n = 2^{10+k}$, $t = 100 \cdot 3^k$. You take it from here. (You won't get $cn^{3/2}$, by the way! The setters made a mistake.)


How are variables stored in and retrieved from the program stack?

Storing local variables on a stack is an implementation detail – basically an optimization. You can think of it this way. When entering a function, space for all local variables is allocated somewhere. You can then access all variables, since you know their location somehow (this is part of the process of allocation). When leaving a function, the space is deallocated (freed).

The stack is one way of implementing this process – you can think of it as a kind of "fast heap" which has limited size and so is only appropriate for small variables. As an additional optimization, all local variables are stored in one block. Since each local variable has known size, you know the offset of each variable in the block, and that is how you access it. This is in contrast to variables allocated on the heap, whose addresses are themselves stored in other variables.

You can think of the stack as very similar to the classical stack data structure, with one crucial difference: you are allowed to access items below the top-of-stack. Indeed, you can access the $k$th item from the top. This is how you can access all your local variables with pushing and popping. The only pushing being done is upon entering the function, and the only popping upon leaving the function.

Finally, let me mention that in practice, some of the local variables are stored in registers. This is since access to registers is faster than access to the stack. This is another way of implementing a space for local variables. Once again, we know exactly where a variable is stored (this time not via offset, but via the name of a register), and this kind of storage is only appropriate for small data.


What does pre-, post- and in-order walk mean for a n-ary tree?

No, it's not limited to binary trees.  Yes, pre-order and post-order can be used for $n$-ary trees.  You simply replace the steps "Traverse the left subtree.... Traverse the right subtree...." in the Wikipedia article by "For each child: traverse the subtree rooted at that child by recursively calling the traversal function".  We assume that the for-loop will iterate through the children in the order they are found in the data-structure: typically, in left-to-right order, for a diagram such as you have shown.

In fact, this is already described in the Wikipedia article on tree traversals: see https://en.wikipedia.org/wiki/Tree_traversal#Generic_tree, which describes exactly how to generalize this to $n$-ary trees.  Pre-order traversal is one where the pre-order operation is "Display the current node" and the post-order operation is "Do nothing".  Post-order traversal is one where the pre-order operation is  "Do nothing"  and the post-order operation is "Display the current node".

In-order traversal is a special case.  It probably only makes sense for binary trees.  While there are several different possible ways that one could define in-order traversal for $n$-ary trees, each of those feels a bit odd and unnatural and probably not terribly useful in practice.  So, it's probably best to think of in-order traversal as being specific to binary trees; if you want to do something akin in-order traversal for a $n$-ary tree, you'll need to decide exactly what you mean by that, as there's no standard meaning for that.


The meaning of $O(n^2)$

  I was told that the complexity of bubble sort is $O(n^2)$. But when I run with a reversed list (worst case) with size 3, the counter finishes with the value 12, shouldn't it be 9?

Had $O(n^2)$ meant $n^2$, we should have written it as $n^2$ instead of that funny looking $O(n^2)$. Instead, $O(n^2)$ means no more than $n^2$ roughly. By "roughly", we mean we do not care about a constant multiplier, be it 0.01 or 2019 or a million. That is, $O(n^2)$ represents a function of $n$ that is $0.01n$ or less. Or a function that is $2019n$ or less. Or a function that is $1000000000n$ or less.

Because of that constant multiplier, even if that counter for a list of size 3 ends up with 9999, it does not contradict the bound $O(n^2)$, although it could be considered a warning sign that the right bound might be bigger such as $O(n^3)$ instead.

The counter and the time-complexity

What is the meaning of the counter in the algorithm? It counts how many times the algorithm has entered into the loop body.

For each call of the algorithm, if we exclude the subcall of the algorithm cause by an inversion, list_[i + 1] < list_[i], the counter will be increased len(list_) times, namely, $n$ times.

Assume the input list was reversely sorted, the worst case for time-complexity. There are $n(n-1)/2$ inversions, which lead to calling the algorithm $n(n-1)/2$ times. There is also the initial call of the algorithm. In total, the algorithm is called $1+n(n-1)/2$ times. So, in the end, the value of the counter is $n\cdot(1+n(n-1)/2)$. For example, if $n=3$, counter ends up with $3(1+3(3-1)/2)=12$, as mentioned in the question.

Note that $n\cdot(1+n(n-1)/2)=\Theta(n^3)$. Since the time-complexity of the algorithm is about a constant multiple of that counter, we conclude that the time-complexity of the algorithm is $O(n^3)$.

An improved version of the algorithm

Here are a few places where the algorithm can be improved.

Instead of for i in range(len(list_)), it could have been for i in range(len(list_)-1). The try ... except can be spared.
The return value of bubble_sort_recursive is never used.
When we have swapped two elements, list_[i + 1] and list_[i] as they  found to be the first unsorted pair of elements, the first $i$ elements remain sorted. So, we can avoid checking the adjacent pairs in those $i$ elements then.
Consider the $n-1$ comparisons made in one call of the algorithm but not in the possible recursive call inside that call. When an inversion is found by one of the comparisons, a recursive call, which will try to find an inversion from scratch, will be made. That means all later comparisons will not succeed and, hence, will not change the list in any way. So, we can break the loop after the recursive call.

Here is the improved version.

def bubble_sort_recursive_improved(list_, begin):
    global counter
    for i in range(begin, len(list_) - 1):
        counter += 1
        if list_[i + 1] < list_[i]:
            list_[i], list_[i + 1] = list_[i + 1], list_[i]
            bubble_sort_recursive_improved(list_, 0 if i == 0 else i - 1)
            break

# import sys
# sys.setrecursionlimit(max(1000, n * n // 2))
numbers = [5, 4, 3, 2, 1]
counter = 0
bubble_sort_recursive_improved(numbers, 0)
print(numbers, counter)

Exercise 1. Explain how the improved algorithm works correctly.

Exercise 2. Show that the improved algorithm runs in $O(n^2)$ time. In particular, counter is at most $n(n-1)$.


how to find total paths in a graph which have only one vertex common with a given path

Let say the given path crosses $K$ nodes. As $G$ is a tree, if you remove all the edges of the given path, you will get a forest of $K$ trees. Each of these tree contains exactly one of the $K$ vertices of the given path more some of the other nodes.

Let's take $T$, one of these tree containing the vertex $a$ of the given path and a total of $n$ vertices. You want to compute the number of different paths passing through $a$. There are two possibilities:

either $a$ has only one neighbour: then the possible paths are the $N$ paths ($a$, $i$) with $i \in N$
either $a$ has several neighbours: then count the number of vertices in the subtree of each of these neighbours. The number of possible paths is the sum of the cross-products more the $N$ paths having $a$ as start.

Note that $T$ may have between $n$ and $n^2$ paths through $a$.

To answer your question, just sum all the trees' number of paths.

EDIT: small examples

If the tree has 4 vertices called $a,b,c,d$, connected linearly like that $a-b-c-d$ with $a$ being the vertex of the given path. Then $a$ has only 1 neighboor and the possible paths are all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d)$]

If the tree has 5 vertices $a $(of the given path)$, b, c, d, e$ connected like that:

    b-a-c-d
      |
      e

Then $a$ has 3 neighboors leading to the 3 subtrees: $b, c-d$ and $e$. The possible paths are:

all the $(a, i)$ => [$(a,a),(a,b),(a,c), (a,d), (a,e)$]
the cross-products between $b$ and $c-d$: [$(b, c), (b, d)$]
the cross-products between $e$ and $c-d$: [$(e, c), (e, d)$]
the cross-products between $b$ and $e$: [$(b, e)$]

total 10 paths.


Question regarding the proof that quadratic probing always finds an empty slot if the table is less than half full

Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i < t/2$ while $j > t/2$. This sort of example cannot happen if $i,j < t/2$, since then $i+j < t$.


First, observe that it is enough to prove that $d\le d'$. Then, the converse inequality follows from the fact that $\overline{\overline{C}}=C$, and by applying the initial argument to $\overline{C}$.

To prove the claim, we actually prove something stronger: we prove that if $C$ shatters $S$, then $\overline{C}$ also shatters $S$.

Let $S$ be a set that is shattered by $C$, and consider $\Pi_{\overline{C}}(S)$. Let $T\subseteq S$, then there exists $c\in C$ such that $c\cap S=S\setminus T$ (since every subset of $S$ can be reached this way). Let $c'=X\setminus c\in \overline{C}$, then $c'\cup c=X$. Thus, $c'\cap S=T$. Therefore, $\Pi_{C}(S)\subseteq\Pi_{\overline{C}}(S)$.
Applying the same argument to $\overline{C}$, we get $\Pi_{\overline{C}}(S)\subseteq \Pi_{\overline{\overline{C}}}(S)=\Pi_{C}(S)$, and thus we have the equality we wanted, and we conclude the claim.


Some ideas for a special case.

If all the elements have a limited range N (all the elements in A and B are bigger than zero and smaller than N), then you can accomplish this task by O(N*log(|A| + |B|)) as following:

for i <- 0, 1, ..., N:
    binary search in A to see whether i is in A
    binary search in A to see whether i is in B
    if i is both in A and B then
        x <- i
        break

This solution will be practically efficient if the N is not so big (for example 10^7) then it will solve the problem even when |A| and |B| are as large as 10^30 (though it is not practical to store them in any place).

The calculation: $N*\log{(|A| + |B|)} = 10^7 * \log{(2*10^{30})} \approx 3*10^8$

Besides, I do not think you can find a practically efficient algorithm for general case for card(A) and card(B) as much as 10^30. The general algorithm, in my opinion, is at least O(|A|+|B|) as following:

ia <- 0
ib <- 0
while A[ia] != B[ib] do
    if A[ia] > B[ib] then
        ib <- ib + 1
    else
        ia <- ia + 1
x <- A[ia]


Is there an structure that allows for a flat representation of trees with constant access to any element?

Well, it depends a bit on the operations. You cannot do anything reasonable if you want to realize you data structure inside an $n$-elementary array. The 2d array works, since there is a bijection between the 2d array entries and the 1d array entries. There is also such a bijection for any fixed tree, but I think this is not what you are looking for.

Notice that your tree decoding [[1,2,3],4,[5,[6,7]],8] also uses more structure than a normal 1d array. So if you ask for data structures of size $O(n)$ with $O(1)$ operations than you can actually do something.

One idea is to use a array where you store the DFS-tour (sometimes called Euler tour) of your tree, and the information about the time when you discover and when you finished a vertex in the DFS search. This can be stored inside an array of size $4n$ plus another $n$ for the values at the nodes, and it allows you to navigate through the tree using $O(1)$ operations per step.

With more involved data structures you can also answer level ancestor queries (what is the $i$-th vertex about vertex $x$?) or lowest common ancestor queries in constant time with a data structure of size $O(n)$. If you want to know more about these two data structures, look up the references in wikipedia.