AVL tree such that each insert causes rotation (single or double)

Short answer: it depends.

The answer depends on what is the set of the possible elements of the AVL tree.

Natural numbers, no duplicates allowed.

Yes, there is an AVL tree requiring a rotation on the next insertion, whatever that is:

      1
     / \
    0   3
       / \
      2   4

The next insertion has to be a natural $\geq 5$ and cause a rotation.

Similarly,

      0
       \
        1

will rotate as soon as any natural (which has to be $\geq 2$) is inserted.

Integer numbers, no duplicates allowed.

Yes, there is an AVL tree requiring a rotation on the next insertion:

      0
     / \
   -1   1
   /     \
 -2       2

The next insertion has to be $\leq -3$ or $\geq 3$.

Rational numbers, real numbers, strings.

No, there is no AVL tree requiring a rotation on the next insertion. We now prove this claim.

These sets satisfy the following property, which we now assume.

Assumption. Let $V$ be the set of the possible elements of the AVL tree. Given any two $x,y \in V$, with $x < y$, there exists $z \in V$ satisfying $x < z < y$.

Proposition. For every $n$, any AVL tree having height $n$ admits at least one insertion requiring no rotations (a simple insertion).

Proof. We proceed by induction on $n$.

For $n \leq 1$, it is trivial.

By the induction hypothesis, assume every AVL tree with height $< n$ admits a simple insertion. Take $T$ to be any tree with height $n$, and name $S,U$ its immediate subtrees. W.l.o.g., assume $height(S) \leq height(U) = n - 1 < n$ (otherwise, swap $S,U$). Hence, $S$ admits a simple insertion $p$.

Modify $p$ so to ensure that, once inserted into $T$, it is inserted into the $S$ side. This is trivial if $p$ falls "inside" the elements of $S$. If instead it is the new minimum/maximum of $S$, make sure it is larger/smaller than the root of $T$, exploiting our assumption above.

Hence, performing an insertion of $p$ into $T$ can not cause any rotation inside the $S$ subtree. Further, it can not cause a rotation around the root of $T$, since this insertion can increase $height(S)$ at most by one, so the AVL invariant $|height(S) - height(T)|\leq 1$ still holds. Hence, there is a simple insertion in $T$.

QED.

Duplicates allowed.

The above proof also holds when duplicates are allowed. In that case, one can insert a duplicate of the root of $T$ in either side.


$(3)\Rightarrow (1)$ should just be a consequence of the definition of $\textsf{NP}$-completeness.
For $(1)\Rightarrow (3)$, you can use the fact that there exists a function $f$, computable in polynomial time, such that $u\in X \Leftrightarrow f(u) \in Z$. Now to decide if $u\in X$, you can compute $f(u)$, and then decide nondeterministically if $f(u)\in Z$.


Simple cycles of length two in an undirected graph

It turns out that the very popular textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, sneakily avoids this issue by giving a different definition of cycle in undirected vs directed graphs.

In Section B.4, it defines cycle and simple cycle as I do (they also require at least one edge), in directed graphs. In an undirected graph, they define cycle the same way except they require that all of the edges in the cycle be distinct; and they say the cycle is simple if in addition the vertices are distinct, other than $v_1=v_k$.


What is the right data structure for MST in a stream

By  noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens,
you can use a ST-Tree[1],  which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $a$ to $b$"
Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find).
If they are not, you add it as possible. Otherwise, if its weight is smaller than $max( a \to b)$, you replace with $(a,b)$ the max. weight edge.
[1]https://en.wikipedia.org/wiki/Link/cut_tree


How to derive the size of $k = \log n$ base from $\frac{1}{2^k} = O(\frac{1}{n})$?

Think about it if we remove the fraction. We need a $k$ large enough so that $2^k = O(n)$. We could do this simply by solving for $k$ in the expression $2^k = n$. Which is simply $k = \log_2 n$. This is because $2^{\log_2 n} = n$.

Now apply the same logic to your expression, with $k = \log_2 n$ we see that: $$\frac{1}{2^{\log_2 n}} = \frac{1}{n} = O\left(\frac{1}{n}\right)$$


Can LOOP-Programm stop when its value goes below 0?

Variables in LOOP programs are non-negative, so the problem never arises; the instruction $x_1 = x_1 - c$ assigns $x_1$ the value of $\max(x_1-c,0)$.

Note that the instruction $x_1 = x_1 - x_2$ isn't allowed: the second operand has to be a constant. However, since $x_1 = x_1 - x_2$ can be implemented in LOOP, the programming language "LOOP with instructions of the form $x_i = x_i - x_j$" has the same power as LOOP.


How to efficiently create balanced KD-Trees from a static set of points

At depth = 1, with your pre-sorted Y list, you'll still need to perform a comparison to the parent node (and compare by X value).

This ensures that items on the left branch will have X value less than parent node, and items on right branch will have X value greater than parent node.

Since at depth = 1, your list is already pre-sorted by Y value, you save time from sorting at each level.

In the case that your item is the same as the parent node, you don't insert, because that node is already the parent.


Multiple inputs in lambda calculus (Confusing example)

The problem is in (most likely wrongly) parenthesising expressions.

$\lambda$ abstraction goes as far right as it can, so your whole example is just one abstraction with body $x\ (\lambda y. 2 \cdot y)\ \texttt{square}\ 3$, meaning that there is nothing to be applied to $\lambda x$, thus no "level-0" redexes. There is just one redex in here, namely $\require{enclose} \enclose{horizontalstrike}{(\lambda y. 2\cdot y)\ \texttt{square}}$, reducing to $\require{enclose} \enclose{horizontalstrike}{(2\cdot \texttt{square})}$. There is also no redexes within the body because if we fully parenthesise the original expression (having in mind that $\lambda$ applications (within the body) are left associative) we get
$$\lambda x. \biggl(\Bigl(\bigl(x\ (\lambda y. 2 \cdot y)\bigr)\ \texttt{square}\Bigr)\ 3\biggr)$$

If we want to make it reduce to $6$, we must completely ignore $\texttt{square}$, because no natural number squared gives $6$. We can do that by making it an input to abstraction that doesn’t use it.
$$\bigl(\lambda x.(\lambda y.\ 2 \cdot y)\bigr)\ \texttt{square}\ 3$$


Can formal languages be used to study mathematical notation?

Formal language theory does not concern itself with the semantics of the language. That might seem odd, since we tend to think of language as a mechanism for communicating something, but if you think about it, there are really two levels of understanding language (at least): the surface level, in which the language is a stream of lexemes, and the underlying denotational level which is more or less divorced from the surface representation. (Chomsky posited an intermediate "transformational" level to get around some limitations with CFGs but that's not relevant here.) Consequently, it is possible to say "the same thing" in different languages; Chomsky is not a Whorfian. (See Wikipedia for a brief overview, with some references).
Nonetheless, a context-free grammar is not sufficient to distinguish correct and incorrect utterances. Chomsky offered the classic example: Colourless ideas sleep furiously (which he spelled incorrectly, being a USian). See Wikipedia, again. (Unfortunately Wikipedia doesn't have a Canadian English version.) The precise division between syntactic and semantic errors is hard, if not impossible, to demarcate and there has been considerable debate over this topic in CS fields, which I'm not going to even attempt to discuss here because I always get into trouble when I do. However, we can identify one classic grammatical rule present in many human languages: noun/verb agreement. I disagrees seems to me to be a syntactic error in the sense that I understand the intent of the utterance perfectly but also recognize it as erroneous. But this syntactic issue can only be captured by a context-free grammar if we enumerate all possible agreements. That is, we can write something vaguely like $S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, but it is easy to see how the enumeration could get out of hand in language with more complicated agreement rules (gender, for example).
The problem with context-free grammars is that they are context-free, although you shouldn't take that description too seriously because it is easy to fall into the trap of misinterpreting technical use of common words (which, I might argue, is the basis of this question in the first place). That means that a nonterminal (like $NP$ above) must derive exactly the same set of phrases regardless of the context in which it appears. So we could not write, for example, $S \to NP_X VP_X$ with the understanding that $X$ needs to be filled in the same way in both expansions. (This is one of the issues which which transformational grammar attempted to grapple.)
That is exactly the problem with tensor index contractions. A tensor index contraction places a particular requirement on the use of index variables: an index variable must be used exactly twice, in which case it cannot be on the left-hand side, or exactly once, in which it must be on the left-hand side. (Since I'm not a physicist, I'd be tempted to collapse that into saying that an index variable must appear exactly twice in all. But there is a semantic distinction between free and placeholder variables, which is important to the understanding of the expression.) Here, there is no simple finite collection of index variables and no limit to the number of placeholders used. Moreover, renaming placeholders does not affect semantics provided that the new names are not used elsewhere in the expression, and one might expect the formal language description to capture that fact.
It is in fact possible to rigorously prove the assertion that context-free grammars cannot capture contextual agreement, as in the previous examples. I think that has something to do with what the quoted claim is asserting. Depending on how omnicurious you are, you might find it interesting to learn more, but I don't think it will end up being particularly relevant to the philosophical or physical insights you seem to be seeking.
The other linked articles, about unfortunate surface forms in mathematical notation, are simply anecdotal; none of them, as far as I can see, makes any deep or even superficial point relevant to formal language theory, just as the possibly famous joke that one man's fish is another man's poisson is not even vaguely insightful about romance linguistics, but it's still funny (IMO).


I talked to be5invis and he said it's implemented using replace.

replace is something like this in Agda: $$ replace : \forall \{a \ b\} \rightarrow (a \equiv b) \rightarrow P \ a \rightarrow P \ b $$
or, using universal polymorphism: $$ replace : \forall \{n\} \{a \ b : Set \ n\} \rightarrow (a \equiv b) \rightarrow P \ a \rightarrow P \ b $$

This is obvious, in both Agda and Idris.

And we use it like this:

$$
\begin{align*}
& proof : \ (a \equiv b) \rightarrow P \ a \rightarrow P \ b \\
& proof \ theory \ pa = replace \ theory \ pa
\end{align*}
$$

While rewrite in is just a mixfix version of replace, so, the code above can be written like this:

$$
\begin{align*}
& proof : \ (a \equiv b) \rightarrow P \ a \rightarrow P \ b \\
& proof \ theory \ pa = rewrite \ theory \ in \ pa
\end{align*}
$$

In conclusion, rewrite is syntax sugar which desugars to replace, while replace is a library function that can be implemented by anyone.
So there's nothing special.

Actually, Idris desugars it to a function like this:

rewrite__impl : (P : a -> Type) -> x = y -> P y -> P x
rewrite__impl P Refl prf = prf


Decidable restrictions of the Post Correspondence Problem

Ehrenfeucht, Karhumäki and Rozenberg have shown that binary PCP (where the domain is binary) is decidable. Halava and Holub later showed that it's actually in P.


Environment requirement in training image dataset for classifier

I think you should have a fourth dataset where the images are in their natural environments because you will need information with white background when you will be testing the datasets.


Let $0 < \varepsilon \lll 1$ be the relative error bound of the floating-point system—$2^{-53}$ in IEEE 754 binary64 arithmetic.

First, the naive formula log1p(exp(x)) always gives a good approximation unless exp(x) overflows:  If exp(x) computes $(1 + \delta_1) e^x$, and if log1p(y) computes $(1 + \delta_2) \log(1 + y)$, where $|\delta_1|, |\delta_2| \leq \varepsilon$, then log1p(exp(x)) yields

\begin{equation}
  (1 + \delta_2) \log\bigl[1 + (1 + \delta_1) e^x\bigr]
  = (1 + \delta_2) (1 + \delta_1') \log(1 + e^x)
\end{equation}

where $|\delta_1'|$ is bounded by a constant multiple of $\delta_1$ since $(1 + \delta_1) e^x$ is positive and $y \mapsto \log(1 + y)$ has small condition number on the positive real axis.  Thus the relative error is bounded by $|\delta_2| + |\delta_1'| + |\delta_2 \delta_1'|$ which in turn is bounded by small polynomial function of $\varepsilon$.

  Exercise: Compute a bound on $|\delta_1'/\delta_1|$.

But you can do better, with less computation (only one transcendental evaluation, not two), in some special cases:

If $x \lll 0$, then $e^x$ is near 0 so $\log(1 + e^x) \approx e^x$.  Specifically, $0 < e^x < 1$, so:

$\log(1 + e^x) \geq e^x/2$, since $y \mapsto \log(1 + y)$ is a concave function with derivative $y \mapsto 1/(1 + y)$ bounded below by $1/2$ for $y < 1$; and
the Taylor expansion of $y \mapsto \log(1 + y)$ converges absolutely at $e^x$.

Thus the relative error of $e^x$ from $\log(1 + e^x)$ is:

\begin{align}
     \frac{|e^x - \log(1 + e^x)|}{\left|\log(1 + e^x)\right|}
     &\leq 2 e^{-x} |e^x - \log(1 + e^x)| \\
     &= 2 e^{-x} |e^x - (e^x - e^{2x}/2 + e^{3x}/3 - \cdots)| \\
     &= 2 e^{-x} |e^{2x}/2 - e^{3x}/3 + e^{4x}/4 - \cdots| \\
     &= 2 |e^x/2 - e^{2x}/3 + e^{3x}/4 - \cdots| \\
     &< 2 |e^x/2| \\
     &= e^x.
   \end{align}

For $x \leq \log \varepsilon$, this relative error is bounded by $\varepsilon$, which justifies the formula exp(x).

In IEEE 754 binary64 arithmetic, $\log \varepsilon \approx -37$.
If $x \gg 0$, we can use the identity

\begin{equation}
     \log(1 + e^x) = \log\bigl[e^x (1 + e^{-x})\bigr] = x + \log(1 + e^{-x})
   \end{equation}

to rewrite $\log(1 + e^x)$ in terms of $\log(1 + y)$ for $0 < y < 1$, with $y = e^{-x}$, as in case (1).  The value of $\log(1 + e^x)$ lies between $x + e^{-x}$ and $x + e^{-x} - e^{-2x}/2$, so the relative error of $x + e^{-x}$ from $\log(1 + e^x)$ is below the relative error of $x + e^{-x}$ from $x + e^{-x} - e^{-2x}/2$, which is

\begin{equation}
     \frac{|x + e^{-x} - (x + e^{-x} - e^{-2x}/2)|}{|x + e^{-x} - e^{-2x}/2|}
      = \frac{e^{-2x}/2}{|x + e^{-x} - e^{-2x}/2|}
      \leq e^{-2x}/2.
   \end{equation}

For $x \geq \log(1/\sqrt{2\varepsilon})$, this is bounded by $\varepsilon$, which justifies the formula x + exp(-x).

In IEEE 754 binary64 arithmetic, $\log(1/\sqrt{2\varepsilon}) \approx 18$.
If $x \ggg 0$, then $x + \log(1 + e^{-x})$ may simply be rounded to $x$.  Specifically, the relative error of $x$ from $\log(1 + e^x) = x + \log(1 + e^{-x})$ is

\begin{equation}
     \frac{\bigl|x - \bigl[x + \log(1 + e^{-x})\bigr]\bigr|}{\left|\log(1 + e^x)\right|}
     = \frac{\log(1 + e^{-x})}{\log(1 + e^x)}
     < \log(1 + e^{-x}),
   \end{equation}

as long as $e^x \geq e - 1$ so that the denominator $\log(1 + e^x)$ is at least $1$.

For $x \geq \log[1/(e^\varepsilon - 1)]$, then this error is below $\varepsilon$, which justifies the formula x.

In IEEE 754 binary64 arithmetic, $\log[1/(e^\varepsilon - 1)] \approx 37$.

  Exercise: Find a nice formula for a bound on $x$ that corresponds to the cutoff $33.3$ in the source you cited, by taking the denominator $\log(1 + e^x)$ into account.


Why do we prove X is in NP to prove it is NP-complete?

The short answer is that it's because that's the definition of being $\mathsf{NP}$-complete.

Recall that for a problem $\Pi$ to be $\mathsf{NP}$-complete we need the following:

$\Pi \in \mathsf{NP}$.
There exists an $\mathsf{NP}$-hard problem $\Phi$ such that $\Phi \leq^{P}_{m} \Pi$ (where $\leq^{P}_{m}$ is a polynomial time many-one mapping).

What happens then if we leave out condition 1?

In that case "all" we've shown is that $\Pi$ is $\mathsf{NP}$-hard.

Even if we restrict $\Phi$ to being an $\mathsf{NP}$-complete problem, we can still reduce it to problems that are much harder. For example it's trivial to map 3-SAT to QBF-SAT, but QBF-SAT is compete for $\mathsf{PSPACE}$, so definitely not $\mathsf{NP}$-complete unless there's a rather large collapse (at least $\mathsf{NP} = \mathsf{PSPACE}$).

Going further (and thanks to David Richerby for being sensible), there are versions of $\mathsf{NP}$-complete problems that are $\textsf{NEXP}$-complete, for example SUCCINCT 3-SAT is a generalisation of 3-SAT (the reduction from 3-SAT to SUCCINCT 3-SAT is less obvious, but not tricky). However we know unconditionally that $\mathsf{NP}\neq \mathsf{NEXP}$, so SUCCINCT 3-SAT is not in $\mathsf{NP}$.

As you note, it is unlikely that we can reduce, in polynomial time, an $\mathsf{NP}$-hard problem that's unlikely to be in $\mathsf{NP}$ to a problem in $\mathsf{NP}$ (again, it would imply some collapse in complexity classes). Where you went off track is identifying this as the only important case.


How do computers synchronize their clocks with the standard time

The Network Time Protocol (NTP) uses a rather simple basis, it assumes that the roundtrip time is divided equally between up and down delays after server processing is subtracted.

NTP keeps 4 timestamps per poll: client send $t_0$, server receive $t_1$, server send $t_2$ and client receive $t_3$. Server timestamps being in the server's clock and client timestamps being in the client's clock (that possibly needs adjusting).

Then the offset from one clock to the other is

$$\theta = \frac{(t_1-t_0)+(t_2-t_3)}{2}$$

The client will do statistical analysis to average out the delta and filter out outliers (filtering out excessive roundtrips for example) before adjusting the clock.

It is possible to use GPS to synchronize


Aspects other than asymptotic worst case time are also important. For example

Actual speed in practice
Memory consumption
Implementation difficulty

Algorithmic analysis almost never tells you the complete story and never should be used to justify blanket statements like "this data structure is the best if you need operations x,y,z".


How to write all $r$-tuples with a certain property in a list

There are many ways to compute all $k$-tuples of elements in a given list $L$. One way is to use recursion and the analogue of Pascal's identity $$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}. $$ We can interpret this identity as follows. Write $L=x, L'$, where $x$ is the first element and $L'$ is the rest of the list. A $k$-tuple of $L$ is either a $k$-tuple of $L'$, or $x$ along with a $k-1$-tuple of $L'$. I'll let you figure out how to turn this into a solution for your problem.

Using the same idea, you can also write a function that given $m$ outputs the $m$th $k$-tuple of $L$, in lexicographic order. You can even decode such a tuple back to its index in this order.

If you don't like recursion, you can also try an iterative approach. The idea is to start with the tuple $0,1,\ldots, k-1$, and keep incrementing the tuple. To increment the tuple, start by incrementing the last position. If it's now $n$, we backtrack and increment the previous position. If that one is now $n-1$, we backtrack once more, and so on. Eventually, unless we were at the last tuple, we well have incremented some position successfully, say to the value $m$. The following position (if any) we set to $m+1$, the one after it (if any) to $m+2$, and so on. I'll let you figure out how to implement this idea.

Both approaches can be implemented so that they produce the same, lexicographic, order. There are probably other, trickier approaches, that rely on applying an intricate sequence of transpositions on the list $0,1,\ldots, n-1$, but the ones I described are general approaches applicable in many other situations. For the more magical ones, check Knuth's new volumes-in-preparation of TAOCP.


From the definition of transitive dependency -

A functional dependency is said to be transitive if it is indirectly formed by two functional dependencies. For e.g.

X -> Z is a transitive dependency if the following three functional dependencies hold true:

X->Y
Y does not ->X
Y->Z

Given, ABCD->E and AC->ABCD, or simply AC->BD

So, ABCD -> E can be written as AC -> E, as AC->BD.

So, the transitive rule is not required to prove AC -> E

Also, if we take X= AC, Y=ABCD, then X->Y (given) but X is subset of Y

So, Y->X (failing the second rule for transitivity)


This has nothing to do with linked lists and everything to do with references (see also pointers). When you assign a mutable object to a variable, the variable holds a reference to the actual object: its memory address. If you assign the same object to two different variables, they both reference the same object; both variables internally hold the same memory address (and changing its members will change the underlying object). But when you then reassign one of those variables, that one now points to a different object again.


Gale Shapley - Everyone ends up with second choice of partner

Let us number the men $1,2,3,4$ and the women $a,b,c,d$ (the men propose to the women), with the following preferences:
$$
\begin{align*}
&1\colon b \succ c \succ d \succ a & a\colon 1 \succ 2 \succ 3 \succ 4 \\
&2\colon b \succ a \succ d \succ c & b\colon 3 \succ 4 \succ 1 \succ 2 \\
&3\colon a \succ d \succ c \succ b & c\colon 2 \succ 1 \succ 4 \succ 3 \\
&4\colon a \succ b \succ c \succ d & d\colon 4 \succ 3 \succ 2 \succ 1
\end{align*}
$$
Let us trace the Gale-Shapley algorithm:

Round 1M: $1,2$ propose to $b$; $3,4$ propose to $a$.
Round 1W: $b$ accepts $1$; $a$ accepts $3$.
Round 2M: $2$ proposes to $a$; $4$ proposes to $b$.
Round 2W: $a$ accepts $2$, throwing $3$; $b$ accepts $4$, throwing $1$.
Round 3M: $3$ proposes to $d$; $1$ proposes to $c$.
Round 3W: $d$ accepts $3$; $c$ accepts $1$.

In the end, everyone is married to their second choice.


Converted comments to answer.

FSM is an ambiguous term but is often taken to mean "finite automaton", of which deterministic finite automata (DFAs) are representative. These are strictly less powerful than Turing machines and other Turing-equivalent systems of computation. That said, actual computers running C# programs are not Turing equivalent; in fact, they're a strictly weaker model of computation that finite automata, although many interesting finite automata can be modeled exactly, and many Turing machines can be simulated accurately. PC < FSM ~ DFA < TM.

Suppose that your PC has 1 TB of memory (RAM, registers, stack, HDD, etc.) This is 8796093022208 bits. Your computer can exist in 2^8796093022208 unique states. It is therefore incapable of recognizing any regular language whose minimal DFA contains more than 2^8796093022208 unique states. One such language is the language containing the first 2^8796093022208 words over a unary alphabet (when ordered lexicographically).


How are programming paradigms classified?

Do not be too obsessed with it. It is often only buzzwords covering a
fuzzy trend (from structured to object oriented) towards better
organization of programs, with somewhat different realizations in
different languages. It can appear in any programming paradigm,
whether imperative or declarative. They are intended to improve
readability of programs, good programming practice, maintainability,
code reuse in various guises, independence of program parts,
information hiding.

What is a lot more important is to understand the specific techniques
that can be used, their costs and benefits, the constraints they
create and the freedom they provide. The more interesting techniques
are based on formal mathematical analysis.

It involves a variety of more precisely definable concepts, such as
environments, scoping and binding of variables, typing systems,
modularity and interfacing, parameterization of code and modules,
exception handling ...

I would think you will be better off concentrating on these identified
technical issues than on more popular but fuzzier concept.


Descriptively

The standard convention is that

$$f(x) = O(g(x))$$

should really be interpreted as

$$f(x) \in O(g(x)),$$

as $O(g(x))$ is most properly viewed as a set of functions.  Yes, that means the former notation is a bit sloppy.  Personally, I don't like it much, but that's the accepted short-hand.

By the same token, the standard convention is that

$$f(x) = O(g(x)) = O(h(x))$$

actually means

$$f(x) \in O(g(x)) \subseteq O(h(x)).$$

The former notation is a bit sloppy (and I don't like), but that's the accepted short-hand notation.

Or, in this case,

$$O(f(x)) = O(g(x))$$

should be interpreted as

$$O(f(x)) \subseteq O(g(x)).$$

The same holds for $\Omega$, too.

Yes, this is sloppy and imprecise.  I think it would be clearer if authors didn't use this notational short-hand.  But, it's a standard notational convenience.  Hopefully, once you're aware of this, it should be possible to work out what was intended from context.

Prescriptively

This use of notation is ugly and confusing and should be avoided, where ever possible.


Determining possible data structures given a set of required operations

If there is no restriction on execution time or $n$ stays small then a simple unsorted array is always an option. It gives $O(n)$ execution time for all operations except adding an object and removing by swap-with-back-and-pop. As a less obvious bonus iteration over an array is very cache friendly so it will likely outperform nearly everything for small $n$.
When you value lookup more than modification you can sort the array, lookups are now $O(\log n)$ and min and max are $O(1)$. But modifications are now $O(n)$ in all cases however they can be amortized a bit by using a small scratch array on the side that gets merged in periodically for additions and tombstone sentinels for removed elements.
Using a min or max heap will reduce modification time to $O(\log n)$ at the cost of all other operations becoming $O(n)$ except the query for min or max depending on which it is. You can split the data into 2 using a selected pivot element where if smaller then elements get pushed into a min heap and if larger they get pushed into a max heap. Depending on the order of operation you may need to reselect the pivot element is the sizes of the heaps become too unbalanced.

Then there are the node-based solutions:

Linked list (sorted or not) is not useful at all here, you still have $O(n)$ execution time for nearly everything like with unsorted array with additional cache miss and dependent-load costs during iteration and the only bonus you have is that insert and remove can happen in-place. I'm mentioning it here because:
You can use a look-ahead list, essentially a sorted linked list with the addition that each node has a finger table of nodes that lets you skip ahead in the list. modifications and lookups are now $O(\log n)$. However it has an element of randomness (how large each finger table is) that can potentially screw you over and regress performance to $O(n)$ for lookups.
A balanced search tree isn't random in that way and every operation becomes $O(\log n)$ and correct implementation of the balancing routing can be tricky.
you already mentioned why you don't like the hashtable though the $O(1)$ modification and lookup can outweigh the $O(n)$ cost for min/max. Though keep in mind that there are various ways of implementing one each with various benefits and drawbacks.

Those are the basic data structures I'd select between for holding a set of values. If there are other requirements and performance is a big enough issue then I'll go research more exotic options.


I would not believe there is a greedy algorithm that can do the job. Instead, sorting followed by dynamic programming as indicated by j_random_hacker's comment seems the appropriate way to find $L$.

Let $n$ be the number of given objects. Assume $k\le n$; otherwise there is no such packing.

First, sort all the weights so that we will have $w_0\le w_2\le \cdots\le w_{n-1}$. Then there is an optimal packing in which each pack consists of consecutive weights. That fact enables dynamic programming, since we can consider only that kind of packing, which has a natural last pack.

Given a packing $P$, let $L(P)$ be the maximum difference between the maximum and minimum value of each pack in $P$. Let
$dp[i]$ be the minimum of $L(P)$ for all packings of the weights $w_0, w_1,\cdots, w_i$, where $k-1\le i\le n-1$. The final answer for all $n$ weights is $dp[n-1]$.

The base case is $dp[i] = w_i-w_0$ for $k-1\le i\lt 2k-1$, as there can be only one pack that contains all the weights.

What if $i\ge 2k-1$? Note that a packing with its last pack removed is still a packing. That critical observation tells us that $dp[i]$ is the minimum of
$$\begin{align}
&\max(dp[i-k],\ w_i-w_{(i-k)+1}), \\
&\max(dp[i-k-1],\ w_i-w_{(i-k-1)+1}), \\
&\max(dp[i-k-2],\ w_i-w_{(i-k-2)+1}), \\
&\cdots,\\
&\max(dp[i-k-\ell],\ w_i-w_{(i-k-\ell)+1}), \\
&\cdots,
\end{align}$$
where the list stops right before $\ell$ becomes $k$, since we can ignore the packings where the last pack (in fact, any pack) contains at least $2k$ objects. We can always split those objects into 2 valid packs, which will not increase $L(P)$. We can also stop as soon as $w_i-w_{(i-k-\ell)+1}$ is no less than the minimum so far.

The time-complexity of algorithm is $O(n\log n + nk)$.


Most probably, it means “for each letter $\sigma$ from alphabet $\Sigma$”.

If $\Sigma = \{ 0, 1 \}$, then B → 000 | 001 | ε.


What's wrong here, or, is CNF to DNF conversion in o(exp(n))?

Can we say that time complexity will also be within $o(exp(n))$, where $n$ denotes formula length?

No, because no one has proven that distribution of terms is the only way to convert CNF to DNF.  Obviously simple distribution of terms produces an exponential blowup in the formula size, but there may be other ways to compress the formula so that the same truth table is produced.  We already known that given a truth table clever algorithms can produce smaller formulas than full disjunction over the distributed terms.

  If 1. is true, wouldn't that prove that this problem isn't part of $P$, and, given CNF -> DNF is NP-hard NP-complete, that $P \neq NP$?

No.  If CNF to DNF conversion could be accomplished in polynomial time, its output would necessarily fit into polynomial space.  Therefore you could scan this output in polynomial time and decide satisfiability.  Thus P would be equivalent to NP.  But if CNF to DNF conversion takes exponential time it says nothing about whether some other algorithm could efficiently solve SAT and bring P and NP together.


In the usual mathematical notation: $(\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A$

The two green occurrences of $\color{green}{x}$ in the subterms $f_1 \color{green}{x}$ and $f_2 \color{green}{x}$ are bound in the term $\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))$. The binding occurrence is the blue $\color{blue}{x}$.

When evaluation $(\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A$ by beta-reduction of the top redex, the result is the substitution of $A$ for the free occurrences of $x$ in the body of the lambda abstraction. If $\&$, $f_1$ and $f_2$ are variables, then the result is simply
$$ (\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A  \to_{\beta} (\& (f_1 A) (f_2 A)) $$
If $\&$, $f_1$ and $f_2$ are lambda-terms, then they may contain free occurrences of $x$, which need to be substituted.
$$ (\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) A  \to_{\beta} (\&[x\leftarrow A] (f_1[x\leftarrow A] A) (f_2[x\leftarrow A] A)) $$

Note that the notion of free or bound variable is really a free or bound occurrence of a variable, in a given term. A variable is often said to be free in a term if it has a free occurrence. For example, in the term $(\lambda \color{blue}{x}. (\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))) (g \, \color{magenta}{x})$, the green occurrences of $\color{green}{x}$ are bound, and the magenta occurrence of $\color{magenta}{x}$ is free. In the term $\& (f_1 \color{green}{x}) (f_2 \color{green}{x}))$, the two occurrences of $\color{green}{x}$ are free.


How are Neural Networks made so general?

Neural nets don't "understand", they are trained. Despite the fancy term, a neural net is simple a regression model on steroid - often high-dimensional. It's a bunch of weights (vectors) connected in a graph, with an input side and some updating rule (for example, gradient descent).

You'll need a lot of labeled data for the training set. The neural net is trained by feeding these input and telling it about the supposed output, and it readjusts its weights in the regression model.

Apart from that it's a blackbox - kinda magical. But you can't use a neural net trained to recognize selfies to do cryptography (or anything else).


Two edges are adjacent if they're incident on the same vertex:

Two edges are adjacent if they have exactly one common endvertex.
—Bollobás, Modern Graph Theory (Springer, 1998; page 2).
Two edges $e\neq f$ are adjacent if they have an end in common.
—Diestel, Graph Theory (2nd Edition, Springer, 2000; page 3).


Is it possible to design a programming task that is unsolvable?

A simplified example can be the following:

$$T( n ) = \begin{cases}
\max \{ M(n) \mid |M| \leq n \} + 1 & \text{if such max exists}\\
0 &\text{otherwise.}
\end{cases}$$

In other words the "unprogrammable" (uncomputable) task $T$ (or better uncomputable function $T$) simply picks all programs $M$ of size at most $n$ as "input" and outputs the maximum value that they output on input $n$, plus 1.

Given a program $M_i$ that satisfies your assumption ( ... which produce an answer in finite time for a (countably) infinite number of inputs ...), there will always be an $x_0$ such that $|M_i| < x_0$ and $M_i$ on $x_0$ halts, and we have:

$$M_i(x_0) \leq \max \{ M(x_0) \mid |M| \leq x_0 \} < T(x_0)\,.$$


What's the difference between user registers and kernel registers?

It's simple - when each application program runs, it has access to its own set of registers. When you switch to other application, these register contents is saved to memory, and registers, saved from other application, loaded and this application continues its execution.

Similarly, OS has its own register contents. Depending on CPU, it may even has its own, different register set. Moreover, some CPUs has two physical register sets - for apps and for OS, thus allowing fast switching from app to OS and back again (f.e. when app requests some service from OS).

Now let's look at your citation. I'm not an OS specialist, but this text means that for each application, we have specific contents of OS registers. F.e. these registers may hold app-specific data which isn't available to app itself (such as security context of the app). So, when you switch from app to OS (usually by requesting some OS service), OS registers are immediately ready to use, making the call faster. OTOH, when you switch to other app, the entire set of kernel registers need to be saved and kernel registers for other app should be loaded instead.

Since task switching is much less frequent operation, this makes the entire execution faster.


Greedy Optimum Dominating Set For A Tree

There is a simple dynamic programming algorithm. Root the tree at some arbitrary vertex. For each subtree, compute the optimal dominating set (a) with the root, (b) without the root.


Generating function of non-regular language

If we apply a substitution that maps all letters of the alphabet to the same letter, we obtain a unary language. This shows that if $L$ is regular, then the set $\{n : L \cap \Sigma^n \neq \emptyset\}$ is eventually periodic. This shows that $\sum_{n=0}^\infty x^{n^2}$ corresponds to no regular language, for example.


Why does Pascal have a high code density?

What makes Pascal dense is not the features it has, but the features it doesn't. Here is a small list of features that make other languages less dense:

higher order functions
classes and inheritance
specialised syntax for sets, lists, hashes
built in regular expression syntax
good libraries


Recurrence relations and the Master Theorem

We know that $n! \le n^n$, therefore $\log n! \le n \log n$. Then
$$
T(n) \le 99T( \frac{n}{100} ) + n \log n
$$
Let $c=\log_{100} 99 < 1$ and notice that $n \log n$ is polynomially larger than $n^c$. Indeed:
$n \log n \in \Omega(n) \subset \Omega(n^c).$ By the master theorem we have $T(n) = O(n \log n)$.
This is tight because $\Omega(n \log n)$ is also a lower bound since:
$$
T(n) \ge \log n! \ge \log ( \lfloor n/2 \rfloor^{(n/2)} )
=  (n/2) \log ( \lfloor n/2 \rfloor)  = \Omega(n \log n).
$$
To summarize, you have $T(n) = \Theta(n \log n)$.


Return copy of array, each element product of all others, constant additional space, no division

A variation of a solution left by a commenter called Vince
Given input $a = <a_1, ..., a_n>$.

Allocate result array $b = <b_1, \ldots, b_n>$. Set $product = 1$.
For $i \in [1, n]$, set $b_i = product$ and set $product = product * a_i$.
Set $product = a_n$. For $i \in [n - 1, 1]$, set $b_i = b_i * product$, and set $product = product * a_i$.
Return the array $<b_1, \ldots, b_n>$.

This solution runs in $O(n)$ time and $O(1)$ space additional to that allocated for the result.


Does overclocking a cpu speed up a poorly optimised process?

Optimization is not really something that should be guessed at. Instead you need to measure what is going on to determine the chokepoints and where changes need to be made.

A faster processor may have little or no effect especially since the CPU utilization is not maxed out. CPU speed affects only those parts of the program which are actually running on the CPU. If the program is waiting for something else such as an I/O operation, a faster CPU doesn't help. The chokepoint is not the CPU speed but rather the I/O speed.

So you may have a faster CPU but that just means that your program gets to a place where it has to wait for something else to happen a bit faster. If your program requires user input then no matter how fast the CPU, the program is still bounded by the speed of a human doing the input.

Program speed also is affected by the algorithms being used. A faster CPU may help a bad algorithm go faster, a kind of linear increase, a better algorithm may provide several orders of magnitude improvement in speed and performance.

Another possible throughput increase can come from multi-threading. This only really helps if you can divide out the overall problem into multiple, asynchronous tasks that can be run simultaneously and the results of each task combined when all are done. The more need there is for synchronizing tasks and events the more likely that multi-threading will not provide that much of an improvement.

With multi-threading there is always the question of how many separately running cores are in the CPU or how many CPUs are being used for the program.

Multi-threading with a single core on a single CPU may or may not help since the various threads are sharing the same core and CPU. It depends on whether some threads are able to progress while other threads are waiting for some resource or event to happen such as I/O to complete.

If you are able to divide out the program into multiple threads and assign the different threads to different CPU cores or multiple processes and assign the different processes to different CPUs then more things can be happening simultaneously. However if all those threads are not compute intensive and are waiting rather than running then it may not make that much difference.

Finally the actual hardware design can make a large difference in the throughput of a CPU. Overclocking a CPU means that it is running faster however it is the same hardware. The differences in throughput between various CPU generations is not due to just CPU clock speed. There are also hardware improvements so that two CPUs with the same clock speed will show very different processing throughput because the hardware design of one is superior to the other. This is where design details such as branch prediction, prefetch, size of the onboard cache, and other hardware details really make a difference.


Generalisation of pancake sorting with arbitrary flipped slices?

Yes, it has been studied quite a lot. The general problem is called sorting by reversal. It is important as it is related to finding the similarity between genomes of two species that have the same genes, but in different order.

There are two variants of the problem, one where the orientation of the pancake [= gene] also matters. This is modelled using so-called signed permutations. See also the last paragraph and references in the Wikipedia page you quote.

There is a very precise characterization of the number of reversals needed for signed permutations in terms of the structure of a certain graph. For the unsigned variant, which you use in your question, the problems seems NP-hard (see the Wiki page) and even hard to appoximate.


Find binary number with max hamming distance wrt given set of binary numbers

Here is the decision version of the problem, which we can the problem of farthest string.

  Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s_i)\ge k$ for all $i$.

There is the problem of closest string.

  Given $m$ length-$n$ binary strings $s_1, s_2, \cdots, s_m$ and a number $k$, determine whether there is a length-$n$ string $s$ such that $d(s,s_i)\le k$ for all $i$.

Farthest string is dual to closest string.

Let $c$ denote the map that changes a binary string to its 1's complement, i.e., switching 0 and 1 everywhere. For example, $c(010010111)=101101000$. Note that $c\circ c = Id$.

Given an instance of farthest string $(m, n, s_1, s_2, \cdots, s_m, k, s)$, we can construct an instance of closest string $(m, n, c(s_1), c(s_2), \cdots, c(s_m), n-k, s)$. Call this transformation of instances $r$.

For every string $s$ of length $n$, $$d(s,s_i)+d(s, c(s_i))=n.$$
Hence
$$d(s,s_i)\ge k\text{ for all }i\  \Longleftrightarrow\ d(s,c(s_i))\le n-k\text{ for all }i. $$

So $r$ converts a yes-instance of farthest string to a yes-instance of closest string. Symmetrically, $r$ converts a yes-instance of closest string to a yes-instance of furthest string. Furthermore, $r\circ r= Id$.

So $r$ is a linear duality reduction between farthest string and closest string.

All results about closest string are about farthest string.

That is because of the duality reduction. Now we can dive into the Wikipedia article on closest string to see find what we have about closest string.

In particular, we know that farthest string is NP-complete. We can check approximability, fixed-parameter tractability as well.


Why are Python 2 and 3 so incompatible with each other?

The saying goes, "In C++11, 11 is the number of legs the stapled onto the dog to make a better octopus".

As with basically everything in Computer Science, this is all about tradeoffs.

If you focus on backwards compatibility, you have potentially conflicting features interacting with each other. You're stuck with the design choices that were initially made, when you didn't have the knowledge and data that years of production use provide.

Breaking changes, conversely, have the disadvantage of breaking old code, though with Python 2, usually files could be converted mechanically.

Now, there are also questions of "what makes a language?"

From a semantics point of view, every time you add a new feature to a language, you have effectively defined a new language with different semantics. There are nice formalisms for dealing with this: for example, some extensions to languages are conservative, meaning you're only expressing features that the start language could express.

Python 2 to 3 was not an extension, let alone a conservative one. So from a theory point of view, they're different languages, that happen to share a name, most syntax, and a real-life community.

Java broke backwards compatability when they decided to be a different language from C++ or SmallTalk or Eiffel. At the end of the day, the lines between languages and dialects and versions can be blurry, and the decision will come down to what is viewed as the most pragmatic for developers.


Complexity Sorting a finite set of numbers from 0,..,N

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

Formally let consider the following procedure:

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

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

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

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


Why?  Because this design works pretty well and meets the requirements, and most alternative don't or would be more expensive or slower.  In particular, this division of responsibilities lets the system implement a suitable page replacement policy for virtual pages in a way that is relatively efficient.

When asking a "why is it done this way?", it's often helpful to try to imagine some concrete alternative way of doing it, and then analyze the advantages and disadvantages of the current method compared to that alternative.  You haven't listed a specific alternative, so it's hard to be a lot more specific.  But for instance if you tried to do it all in software (so the OS has all responsibility), without the hardware managing the accessed or dirty bits, that would be very difficult: the only methods I can think of for doing that are clunky and will cause many context switches and thus will slow down the system a lot.


What features should a critical section have to maximize performance?

As noted in the question, the performance impact of critical sections has two components: the limiting of parallelism and the overhead in providing the isolation guarantees.

The limiting of parallelism can be addressed by minimizing the context, frequency, and duration of the critical section. Using finer-grained locking or transactional memory allows independent operations to be executed in parallel by reducing the context in which isolation must be guaranteed.

Reducing coupling of operations can reduce the context and frequency of critical sections. The use of redundant data structures can provide localization of data such that critical sections can be avoided (reducing their frequency) or the potential contention reduced. For example, instead of updating a single accumulator a tree of accumulators could be used.

(While the fastest critical section is the one that does not exist, one must be careful that overheads in avoiding critical sections are not higher than the cost of using a critical section.)

The duration of a critical section can be reduced by keeping work out of the critical section. While this is relatively obvious, moving work before or after the critical section may require that more work be done (at least in some cases) or may interfere with other design considerations. Speculatively performing work before a critical section can shorten a critical section at the cost of detecting and handling incorrect speculation.

One subtle form of work is the handling of cache misses and state updates (primarily acquiring ownership of a cache block). Avoiding false sharing is a well-known technique, but somewhat less commonly mentioned (in part because of tradeoffs of complexity and runtime overheads with the performance benefit) are localization of true sharing and prefetching. Temporal localization of sharing exploits patterns of reading and updating to use warm data. In some cases, it may even be worthwhile to increase the duration of a critical section to reduce the amount of work within critical sections by taking advantage of a warmed-up cache.

Sharing can also be localized within the memory system. Not all communication between threads has equal cost. Physical proximity of communication and read-sharing can exploit sharing of a level of cache to keep warm data in cache (incidentally avoiding replication), to prefetch data (if cross-thread accesses can have temporal locality either naturally or by clever scheduling), or to reduce the bandwidth or latency of communication. NUMA-optimizations can also reduce bandwidth and latency by locating users, especially modifiers, of data near the home of the data. NUMA-optimizations can even apply to last level cache slices when a cache block has a single home partition within the last level cache which can be accessed with less overhead by one or more processing elements.

Using finer-grained locking can also reduce the isolation overhead by avoiding cache line ping-pong. The ultimate in fine-grained locking is lockless updating using atomic operations. Knowing what facilities the targeted hardware provides and the tradeoffs in their use can also be helpful in reducing isolation overhead. For example, if the targeted hardware transactional memory system supports low overhead retry under certain conditions, it may be less important to avoid contention leading to a transient transaction failure than to make sure those conditions are satisfied.

Approximation can also exploited in some cases to reduce overhead. Statistical information such as software performance counters can often tolerate losing some updates, allowing removal from the critical section and the use of less expensive non-atomic operations. Similarly, some information only needs to be conservatively maintained for correctness. For example, a reference counter could afford to lose a decrement if the information is only used for earliest release of a resource (another layer of resource management might handle such leaks).

The basic principle for critical sections is that they should be as small (context and duration) and as infrequent as possible.


Do quantum logic gates work differently than traditional logic gates?

In layman's terms, the answer is yes: quantum gates are quite different from classical gates.

One reason is that quantum gates must be reversible. This practically means that AND gates don't even exist in the quantum world (at least, not in the same sense of a classical AND gate). Instead, there is a different set of gates (e.g., CNOT, TOFFOLI, FREDKIN, etc.) that allow to do all that is possible by quantum computing, without breaking the reversibility condition.

The other issue is what you hint in your question. Qubits can be "both in 0 and 1", and the quantum gate must take care of this. But this is not a problem, it just means that the output must be a superposition of 0 and 1.
For instance, let's take a simple NOT gate. If the input is a "superposition" of 30% 0 and 70% 1, then the output becomes 70% of 0 and 30% of 1. Of course this is a very superficial explanation, and quite inaccurate, but the idea is exactly that.

Finally, no measurement is done in gates, unless the gate is a measurement gate (also, measurement is not reversible, so it cannot happen in "standard" gates)

For more information, check

https://en.wikipedia.org/wiki/Quantum_gate
https://en.wikipedia.org/wiki/Reversible_computing


Mathematics topics or fields that increase computer programming proficiency?

So, there are many fields of math that are relevant to the Science of CS, but for programming specifically:

Graph theory: this is the big one. Graphs and trees are everywhere. Networks, maps, paths in video games. Even things like solving a Rubiks cube can be modelled as a graph algorithm and solved with A*.
Discrete math: aside from graph theory, knowing this area in general is helpful. It's full of proofs by induction, which are very useful for understanding recursion, which is very useful in programming, particularly with data structures. Knowing about sets, counting, inclusion-exclusion, boolean logic, etc. can come in handy once in a while.
Type theory: unsurprisingly, knowing type theory helps with understanding programming in typed languages, and more broadly, with using types as a way of ensuring certain correctness properties. Knowing about the theory of subtyping helps you to understand covariance and contravariance in Java-like languages. Knowing about things like parametric polymorphism is obviously helpful when learning a type-heavy language like Haskell or Purescript, but langauges like Scala, TypeScript, and Rust are becoming more prevalent in industry, and types are at their cores.

If you take this one to its extreme, you get things like Coq and Agda and Idris, which can be used to prove extremely precise correctness properties about programs.
Computability and Complexity Theory: knowing when a problem is either unsolvable, or NP-hard, is useful, because you won't waste hours racking your brain for a fast way to do it. Likewise, knowing some of the theory behind approximation algorithms, fixed-parameter tractability, or low-base exponential algorithms, can help when you really need to solve an NP-hard problem.
Automata theory: many problems can be modelled with various state machines, so understanding their properties is useful.

There are also some field-specific areas:

Statistics: If you're doing machine learning or big-data, this is a must.
Linear algebra/vector calc: both of these are important for machine learning, graphics, simulations, or image/audio processing.
Lattice theory: if you're doing any work with compilers or program optimization, this one comes up all the time. Fixed points everywhere!
Category theory: not needed to code, but useful for anything deeply drenched in type theory.

Edit: can't believe I forgot:

Cryptography: if you're interested in security, hashing, digital signatures and such, then make sure to learn some number theory, Group Theory, Field theory, elliptical curve Theory, etc.


Nodes reached with exactly $k$ steps in an undirected graph?

There is an easier way than dynamic programming. You can compute the adjacency matrix to the power of $k \in \mathbb{N}$. Let $m$ be your adjacency matrix. Then $m^k$ contains also paths of the length $k$. All other entries would be zero.

The runtime would be (because of only matrix multiplication): $\mathcal{O}(n^3)$


The constant in the merge sort recurrence

Nitpick: Are they really talking about time? If they are actually counting some operation, it's well possible (if unlikely) for the same constant to show up in both places.

  How is there a constant  c that can represent both times?

It (probably) can not. This is a simplification done with the goal in mind: derive a $\Theta$-bound.

Apply the Master theorem to both candidate recurrences; you'll note that the result stays the same. CLRS know this from experience, so they simplify the recurrence a-priori.


Confusion about the definition of de Bruijn terms in the TAPL book

The $n$ isn't indexing how many references to variables there are, it's indexing how many free variables are able to be referred to.

You can think of $0,1,\dots,n-1$ as being variables $v_0,v_1,\dots,v_{n-1}$. A term in $\mathcal T_n$ is a term that is allowed to refer to variables $v_0$ through $v_{n-1}$. If you have two terms of $\mathcal T_n$, then each is allowed to use variables $v_0$ to $v_{n-1}$. If you combine them into a new compound term, i.e. $(t_1, t_2)$, then that compound term still only refers to/uses the free variables $v_0$ through $v_{n-1}$. A use of a free variable $v_{n+4}$ hasn't suddenly appeared.

In the $\lambda.t_1\in\mathcal T_{n-1}$ case, while $t_1$ can contain an instance of $n-1$, i.e. an occurrence of $v_{n-1}$, such an occurence doesn't refer to a free variable. It refers to the variable bound by the $\lambda$. (Or $v_0$ doesn't depending on the convention: de Bruijn levels vs de Bruijn indices.) You could describe this as $\mathcal T_n$ only allows occurrences of $v_m$ if $v_m$ is under at least $m-n+1$ lambdas. From this perspective, $(t_1,t_2)\in\mathcal T_n$ when $t_1,t_2\in\mathcal T_n$, is just saying that if all occurrences of $v_m$ in $t_1$ and $t_2$ occur under at least $m-n+1$ lambdas, then they still occur under at least $m-n+1$ lambdas in $(t_1,t_2)$ since we haven't added or removed any lambdas.


Is the way an OS schedule threads related to parallel computing?

There is a relationship between what Wikipedia is calling "preemptive multitasking" and running multiple threads in parallel, but it's somewhat indirect.

Suppose you have two threads of computation that are independent (the memory locations they touch are non-overlapping).  Then we say that those two threads can run concurrently.  "Preemptive multitasking" is a way of giving the illusion that the threads are running concurrently, even though we only have a single physical processor.  The single processor gets interrupted (usually by some timer hardware) every once in a while (e.g., 100 times a second), and chooses which thread to run.  Since the processor is switching back and forth so quickly it is hard to tell that you aren't running simultaneously on two (slow) processors.

If you actually run the two threads on two different processors then you are really running in parallel, and there is no switching back and forth to share a single resource.

The similarity comes up because in both true parallelism and preemptive multitasking any ordering of the instructions between the two threads is possible.  Thus if there is any sharing of resources, memory, or locks you need to reason about the correctness of that sharing by proving that nothing bad can happen in any possible interleaving.

With cooperative multithreading you break the illusion of having multiple processors.  If a thread gets scheduled it runs as long as it wants to (and knows that the other thread is not running) and only gives up the processor by calling some system call (often called something like yield().)  On the one hand, you've lost the illusion of two processors, which is problematic if one of the threads forgets to yield().  The advantage is that you know when the the threads are switching back and forth, so the number of possible interleavings you need to reason about is much smaller.


What is the result of a reduction operation called?

In the context of reducing one language to another, I have only ever seen this referred to using phrases such as "the problem being reduced to", "the target of the reduction", etc. I don't think there is a single word for it—certainly not one that would be universally understood.


Isn't this language in $\mathrm{P}^{\mathrm{NP}}$?

Yes, your argument is correct.

$\textbf{P}^\textbf{NP}$ is the class of problems which are Cook-reducible (i.e., polynomial-time Turing-reducible) to $\textbf{NP}$. A Turing reduction to $\textbf{NP}$ is simply a reduction with oracle access to a problem in $\textbf{NP}$, in this case the problem $\text{CHROMNUM}$.

In fact, using your reasoning and the fact that $\langle G, k \rangle \not\in \text{CHROMNUM} \implies \langle G, k' \rangle \not\in \text{CHROMNUM}$ for all $k' \le k$, you can prove that you only need two oracle queries (independent of $n$). That is, your reduction resumes to checking the following:
$$\langle G, n \rangle \in \text{CHROMNUM} \land \langle G, n - 1 \rangle \not\in \text{CHROMNUM}$$
This means you only need one $\textbf{NP}$ query and one $\textbf{coNP}$ query (since checking if something is not in an $\textbf{NP}$ language is in $\textbf{coNP}$). As it turns out, there is a class of problems which are characterized by having the same type of reduction, the difference polynomial time class $\textbf{D}^\textbf{P}$, and which, incidentally, coincides with the second level of the Boolean hierarchy.


Mutation and crossover operations in discrete differential evolutionary operations?

There isn't a single way in which one can approach a discrete optimization problem using Differential Evolution (DE).

Widespread techniques listed under the Discrete Differential Evolution label aren't DE-specific.

You can allow variables to take values in a continuous range and use penalty functions to enforce integer values:

$$ \bar{f}(w) = f(w) - \sum_i{k_i \cdot (w_i - \operatorname{round}(w_i))^2} $$

$w$ is the vector of parameters (chromosome values), $f: \mathbb R^n \rightarrow \mathbb R$ the basic fitness function (here assuming "greater is better"), $k$ a problem-specific scaling vector, $\bar{f}(\cdot)$ the "penalized" fitness function.

In this way the DE algorithm (DE/rand/1) stays the same:

$$\begin{align}
X_{j,r2}^G - X_{j,r3}^G & = \{2,2,3,0,4,2\} - \{1,2,3,3,0,1\} = \{1,0,0,-3,4,1\} \\
F \cdot (X_{j,r2}^G - X_{j,r3}^G) & = 0.5 \cdot \{1,0,0,-3,4,1\} = \{0.5,0,0,-1.5,2,0.5\} \\
V_{j,i}^{G+1} & = \{4,1,3,2,2,0\} + \{0.5,0,0,-1.5,2,0.5\} = \{4.5,1,3,0.5,4,0.5\}
\end{align}
$$

The trial vector $U$ is obtained via crossover between the donor vector $V_{j,i}^{G+1}$ and a target vector $X$:

$$U_{j,i}^{G+1} = \operatorname{crossover}(V_{j,i}^{G+1}, X_{j,i}^{G})
$$

The target vector is compared with the trial vector and the best one is admitted to the next generation.

This is the recommended procedure with R DEOptim Package (via the optional fnMap parameter).

You can round all the real-valued parameters before evaluating the fitness function:

$$\bar{f}(w) = f(\operatorname{round}(w))$$

(round acts as a repair operator)

This is the technique used by Mathematica's functions NMinimize / NMaximize with the options Method → "DifferentialEvolution" and  Element[w,Integers]

There are also many variations of DE named something-Discrete-DE:

Binary Discrete Differential Evolution: the solution of a problem is presented as a binary string instead of a real-valued vector
Real Value based Discrete Differential Evolution introduces forward/backward transformations to map integer into real number
and viceversa
Exchange based Discrete Differential Evolution: here the crossover operator doesn't change but mutation, being the primary operator acting on
elements of vector in continuous space, is replaced.
...

So you should specify what form of Discrete DE you're interested in for a step by step example.

Meanwhile A Comparative Study of Discrete Differential Evolution on Binary
Constraint  Satisfaction Problems by Qingyun Yang (2008 IEEE Congress on Evolutionary Computation) is a good starting point with many references.


maximum distance in between points in taxicab metrics - inserting and deleting points

Yes, I think you can get $O(\log n)$ for $find()$ too.

First, figure out how to implement $find()$ in $O(n)$ time. Here are some ideas:

You can iterate over all possible choices for the first point $(x_i, y_i)$.
Now the problem is that depending on where the other points are situated in relation to $(x_i, y_i)$ the distance formula can take $4$ different forms. Each one of them entails different signs for the coordinates. We don't know where the maximum will come from, so let's iterate over all $4$ cases. Let's say the first case is $(x_i, -y_i)$. You'll have to match this with a $(-x_j, y_j)$, and you'll want to match it with one that has the maximum sum $-x_j + y_j$. Your first concern is how to obtain this best sum in $O(1)$. Your second concern is convincing yourself this solution is correct, because nowhere have we made sure that the best $(-x_j, y_j)$ actually has $x_j <= x_i$ so that $|x_i - x_j| = x_i - x_j$. We're trying to maximize the result of each case, but we're taking all points into account for all $4$ cases, disregarding their position relative to the fixed point. Can you see why this actually works?


Compilers: How to see "the number of grammars where there exists a string that has at least two different left-most derivations"?

Although the problem of detecting whether a grammar is ambiguous is, in general, undecidable, for toy grammars like this it is usually pretty easy to find ambiguities by simply enumerating the possible (left-most) derivations until you derive the same sentence in two ways.
For example, $G_1$ has just three productions $S\to a S b \mid S b \mid c$, and none of them has more than one non-terminal on the right hand side. So there are only four derivations of three steps, and it's easy to see that two produce the same sentence.
$$\begin{align}S&\to a S b \to a a S b b \to a a c b b \; (P_1, P_1, P_3)\\
S&\to a S b \to a S b b \to a c b b\; (P_1, P_2, P_3) \\
S&\to S b \to a S b b \to a c b b\; (P_2, P_1, P_3) \\
S&\to S b \to S b b \to c b b\; (P_2, P_2, P_3)\\
\end{align}
$$
$G_3$ does have a production which produces two non-terminals, so there are a lot more short derivations. Even so, it shouldn't take you very long to find two derivations for the same sentence.
Proving that a grammar is not ambiguous is not so easy. One possibility is to create a conflict-free parsing table, using any standard algorithm. Not all unambiguous grammars are deterministic (and fewer are deterministic with a single lookahead) but if you do manage to find a conflict-free parser, then the grammar was definitely unambiguous.


Is there any polynomial time algorithm for a restricted EXP-time problem?

Your first formulation isn't very useful, as either the machine which simply writes $0$ on its tape (without putting in any effort) or the one which writes $1$, satisfy your condition. Fixing both $T,w$ means you have only one question at hand, and not a computational task we can reason about in terms of the amount of resources require to handle it. In that case, a simple yes or no consists as a valid answer, and we can output it in constant time.

In your second formulation, you're asking whether the language

$L=\{(\langle M \rangle,w)| \text{$M$ halts on $w$ within $2^{|w|} steps$}\}$

is decidable in polynomial time? The answer is no, since $L$ is hard (under polynomial time reductions) for the class $\mathsf{DTIME\left(2^n\right)}$. This means that if $L\in P$ then $\mathsf{P=DTIME\left(2^n\right)}$, contradicting the time hierarchy theorem.


Is log(n) equivalent to (log(n))^x for big-O analysis?

$f(n)$ is not $O(n^2\log n)$

If we denote $f(n) = (n\log n+1)^2+(log n+1)(n^2+1)$
then:
$$f(n) = n^2 \log^2n + 2n\log n + 1 + n^2\log n + n^2 + \log n + 1 \geq n^2log^2n$$

since all the other terms are obviously greater than 0. Therefore by definition $f(n) = \Omega (n^2log^2n)$. Which strictly means it cannot be bounded from above by anything asymptotically greater.

Note that it also holds that $f(n) \leq 10n^2log^2n$, so $f(n) = O(n^2log^2n)$ and also $\Theta$ of the same.


If the number of clauses is very small, then there's no clause/variable ratio that makes 3-SAT hard.  3-SAT with < 20 clauses is easy.  It's asymptotically easy (technically, the running time is $O(1)$) and easy in practice (using off-the-shelf SAT solvers).

One way to derive hard instances is based upon cryptography, where you convert the problem "find a value $x$ whose SHA256 hash starts with 128 zeros" to SAT, or "find a 128-bit AES key $k$ that encrypts a fixed 128-bit string to another fixed 128-bit string".  However, these are still going to have thousands of variables and tens of thousands of clauses, at minimum.


More Information about the Question Answering System called LUKE

Check this out. This might be the paper

https://www.researchgate.net/project/LUKE-Project

https://www.researchgate.net/publication/340461536_Global_Entity_Disambiguation_with_Pretrained_Contextualized_Embeddings_of_Words_and_Entities


If $P = NP$, then the only not-$NP$-hard sets are $\emptyset$ and $\Sigma^*$, and the statement trivially holds. So let us assume $P \neq NP$.

Then whenever $X$ is $NP$-hard, both $X$ and $X^C$ must contain an infinite c.e. set, namely "the image of the positive SAT-instances under the reduction" and "the image of the negative SAT-instances under the reduction". For if either of these sets were finite, we could get a P-algorithm for SAT.

By diagonalization, we can construct some set $X$ such that neither $X$ nor $X^C$ contain an infinite c.e.-set. Then $SAT \cap X$ and $SAT \cap X^C$ do not contain infinite c.e. sets, hence are both not $NP$-hard. But their union is SAT, and hence $NP$-hard.

To get a decidable counterexample, it should suffice to note that if $X$ is NP-hard, we not only have infinite c.e.~subsets of $X$ and $X^C$, but actually ones which can be computed in exponential time. Diagonalizing against those should doable in a decidable way; but I have not worked out the details.


You do not need dovetailing when $t(n)$ can be quickly computed. Also, note that $l$ is an absolute CONSTANT. The only function is $t$ but the variable is the input string length $n$, hence we write $t(n)$.

So when you are given an input string $x$ of length $|x|=n$, Levin search just does as follows:

Knowing an upperbound for the fixed length of $p$ (i.e. $l$), quickly compute the upperbound for runtime $t(n)$, for each program represented by a tring $M$ of length $|M|=\leq l$, simulate $M$ on input $x$.

Here is the part that is TOTALLY missing from your post: If some $M$ outputs a result $s$, use the verifier for the language to see if $s$ is the string being searched for.

This is only possible if the language is in $NP$.


There are many different models in which regret minimization makes sense. One particular model is Gaussian density estimation. Takimoto and Warmuth, in their paper The minimax strategy for Gaussian density estimation, give a tight analysis which includes both an upper bound achieved by a particular algorithm and an almost matching lower bound proved using the adversary method. There are probably many more such analyses out there.


Yes, this is possible.  Here are two examples of such a function.

One function is $f(x)=x$.  This has no collisions, and the function is easy to invert.

Here is another function:  define $f(x) = x$ if $x$ is 256 bits long, otherwise $f(x) = \operatorname{SHA256}(x)$.  Then it is very hard to find collisions for $f$ (since SHA256 is collision-resistant).  At the same time, given $y$, it is easy to find an $x$ such that $f(x)=y$, so we might be willing to say that $f^{-1}(y)$ is easily computable.  To put it another way, given $y=f(x)$ where we are told $y$ but not told $x$, it is easy to find $x'$ such that $f(x')=y$.  The catch is that $x'$ might be different from the original $x$.


Because the definition of $\delta$-reduction requires that

for all $1≤i≤n$, $N_i$ is normalized

and the second argument $((+1) 1)$ is not normalized.
As you observe, we can first reduce the $\delta$-redex $((+1) 1)$ to $\delta$-normal form $2$; then $((+1) 2)$ is a $\delta$-redex which can be reduced to $\delta$-normal form $3$.
$((+ 1) ((+ 1) 1)) \triangleright_\delta ((+1) 2)) \triangleright_\delta 3$ is a correct reduction, but $((+ 1) ((+ 1) 1))$ isn't a redex in the first step; $((+ 1) 1)$ is.


How does a compiler infer a value's type?

You did not provide an explicit type identifier in the left part of the variable declaration & initialization statement. However, by implicitly specifying an initialization value in the right part to have type int, which the compiler can infer from values of 42/50, these statements triggered the procedure of the compiler to handle S-Attributed Grammar.


Why isn't converting from an NFA to a DFA working?

Your methodology for creating the DFA from the NFA is fine. The problem is that you started with the wrong NFA (you'll notice that your NFA doesn't accept abbaa either). Try this one instead:


Do the following concepts belong to syntax or semantics?

It's not really a good idea to try to divide everything in PL into "syntax" and "semantics". Often we mix things. Nevertheless, as for your question, we normally divide things up like this:

terms, values and types are syntactic entities, as each of them is described by grammatical rules, so these are syntax
a typing context is syntax in simple cases, when we can describe contexts using grammatical rules
the typing relation is considered to be part of static semantics, i.e., the typing relation is determined by the structure of the terms (as opposed to their operational behavior),
the evaluation relation is part of dynamic semantics, i.e., the evaluation rules explain the operational (dynamic) behavior of terms.

You did not mention denotational semantics, which gives mathematical meaning to terms and types. It is considered to be a separate thing of its own.


You can think of it as " every CFL is Recursive".
And Recursive languages are closed under complementation.

Therefore, if a language $L$ is CFL then it is also recursive and hence, $L^C$ is also recursive.


Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle?

You are asking two questions. The first question is whether your graph is a counterexample to the claim that in a graph with minimum degree 2, every vertex lies in a simple cycle.
Unfortunately, your graph is not simple, so if by graph you mean simple undirected graph, then your graph is not a counterexample. However, if you replace the self-loop by a cycle, you should get a valid counterexample.

The second question is whether the claim is true if the graph is 2-regular (all degrees are 2). Indeed, a 2-regular graph is a disjoint union of cycles. I'll leave you to figure out a proof.


Is there an O(1) solution to find the kth-smallest element in an implicit min-heap?

This is not possible. If this is the case then we could extract a sorted list in linear time; $O(1)$ for each $k$th smallest element. We can also create a min heap in linear time thus we could sort in linear time! We know comparison sorting has an $\Omega(n \log n)$ lower bound worst case, so this is not possible.


Reinforcement learning without self-play

If you have a sane reward function and sufficient examples you can train a neural network on predicting your next state/value given a state/action and then use this neural network as a model to generate many more training examples on which to train a policy by selecting new action combinations.  This may result in unexpected behaviour if you do not have sufficient examples which is quite likely to occur unless you have a very large training set.

Reading up on Actor-Critic reinforcement learning may help you here.


Explicit algorithms and algorithms involving unknowns

Personally, I would call the first one an algorithm, and I would call the second a non-constructive proof of the existence of an algorithm.  But it probably doesn't matter all that much what you call it, exactly, as long as you are explicit and clear about what you mean.

Related: https://en.wikipedia.org/wiki/Non-constructive_algorithm_existence_proofs, https://cstheory.stackexchange.com/q/12162/5038.


Your problem is equivalent to scheduling unit-time tasks on infintely many machines with precedence constraints (which are by necessity DAGs) minimizing the maximum completion time. In scheduling literature, this is called project scheduling and also denoted as $P_{\infty} \mid \text{prec} \mid C_{\max}$.

This problem is known to be amenable to the critical path method (CPM) which creates an optimal schedule in time $O(n^2)$, $n$ the number of tasks.

Given a schedule $s : \mathbb{N}^2 \to T$ that maps pairs of time slot and  machine indices to tasks, you can derive a tree consistent with the precedence DAG of the form

$\qquad\displaystyle \mathrm{Seq}\bigl( \mathrm{Par}(s(1,1), \dots, s(1,i_{1})),\ \dots,\ \mathrm{Par}(s(t,1), \dots, s(t,i_{t}))\bigr)$;

here, $t$ is the time of the last scheduled task, and $i_j$ is the maximum index of busy machines at time $j$. (I assume that at any given time $j$, machines $1, \dots, i_j$ are busy and $i_j+1, \dots$ idle.)

If that schedule is optimal, the tree is, too. It does not hold information about the original DAG, though.


Proving correctness of an AVL-Tree colouring algorithm

You are recursing structurally, so you might want structural induction, but in AVL trees structural induction and induction on height are similar. You probably want to prove something a bit stronger than you need at the end - perhaps something like "AVL trees with height n return RB trees with black height n, and if n is even then neither child of the root is colored red."


A plane-sweep algorithm for a points in triangles inclusion problem

Generally, you can analyze each step of the algorithm. Step 2 for constructing the tree (as insert operation can take $O(\log(n))$) is $O((p+t)\log(p+t))$.
All operations in if statements take $O(\log(n))$ (finding the minimum, deleting a member, inserting a member, and so on). Also, the main while loop takes $|X|= p + 3t$.
Hence time complexity of the algorithm would be $O((p+t)\log(p+t))$ as you guess.

In sum, to analyzing time complexity of an algorihtm in a formal manner, it would be enough discussed on each step of the algorithm.

For correctness, you should show that this algorithm can find a general point inside its triangle correctly.


This is similar to the recurrence arising in the analysis of Quicksort, search for "quicksort analysis" to get lots of results.

An easy road is to write:
\begin{align}
(n + 1) T(n + 1) &= 2 \sum_{0 \le k \le n} T(k) + (n + 1) c \\
n T(n)           &= 2 \sum_{0 \le k \le n - 1} T(k) + n c
\end{align}
Subtract to get:
$$
(n + 1) T(n + 1) - (n + 2) T(n) = c
$$
This is a linear recurrence of the first order. Divide by $(n + 1) (n + 2)$ to get:
\begin{align}
\frac{T(n + 1)}{n + 2} - \frac{T(n)}{n + 1}
  &= \frac{c}{(n + 1) (n + 2)} \\
\sum_{0 \le k \le n - 1}
    \left( \frac{T(k + 1)}{k + 2} - \frac{T(k)}{k + 1} \right)
  &= c \sum_{0 \le k \le n - 1} \frac{1}{(k + 1) (k + 2)} \\
\frac{T(n)}{n + 1} - T(0)
  &= c \sum_{1 \le k \le n} \left( \frac{1}{k} - \frac{1}{k + 1} \right) \\
  &= c \left( 1 - \frac{1}{n + 1} \right) \\
  &= c \frac{n}{n + 1} \\
T(n)
  &= T(0) (n + 1) + c n
\end{align}


Can threads use resources from other processes?

Threads are used to handle tasks simultaneously. For example, you keep your computation running in a thread, while another thread is waiting for keyboard input.

Threads inherit the privileges of the process they run in.
If the parent process is authorized to access another process's resources than the thread can do this.
The operating system assigns the process privileges when starting that process.

Whether your threads can obtain resources or not depends on the implementation of threads in your operating systems. In Linux, with some languages such as C, your threads are able to share memory with other processes, and even threads can create other threads. Basically, threads' access to memory is the same as your process. So, threads can create a shared memory with another process and keep communicating with other processes via shared memory space.


Weak precedence is first an algorithm for parsing (see Parsing Techniques - A Practical Guide 1st edition p. 186). So a weak precedence grammar would be a grammar which can be parsed by this algorithm (see the reference for a description of the algorithm, you'll probably want to start at least a few pages earlier).

IIRC, the interest of weak precedence parsing dropped at lot when practical LR(1) variants (SLR(1) and LALR(1)) were discovered, but precedence algorithms are still sometimes used in hand written parser for parsing expressions while the rest of the grammar is parsed with a recursive descend variant.


What is the complexity of finding the predecessor of a node in a doubly linked list?

Both answers look wrong. Time is indeed $O(1)$ because you can look into prev (not next) pointer of the node. The answers you found on the web are probably about single-linked lists.


Give an implementation leveldescription of a TM

There is an important gap between human reasoning ("high level") and the formal definition of a Turing Machine ("low level").
If you are approaching these exercises for the first time and you are not yet familiar with TMs, what I recommend is to write down a pseudocode description of the algorithm which is nothing more than a high level description of the Turing machine itself)
and then to "break up" the algorithm into smaller entities, until the transition function of the machine is achieved.

In the case of your example you can consider $x$, $y$ and $z$ as binary encodings of integers, then you need a function that does the following:

Read the input $($$x$, $y$, $z$$)$
Compute $y \oplus z$
Compare  $($$y \oplus z$$)$ to $(x)$

If the equality in point 3 is verified, accept the language.
This TM will always accept membership in your language $L$.


Partition of a set of integer into 3 subsets of approximately equal sum

Let $x_i,\ i=1\ldots,n$, be the list of nutritional values of the $n$ fruits, which I assume are nonnegative integers.

You want to partition $\{1,\ldots,n\}$ into three sets $A,B,C$ to maximize the minimum of $x_A = \sum_{i\in A} x_i$, $x_B = \sum_{i \in B} x_i$, $x_C = \sum_{i \in C} x_i$.  This is a variant of the set-partitioning problem.  It is NP-complete.

However, there is a dynamic programming algorithm that is pseudo-polynomial (i.e. polynomial in $n$ and $S = \sum_{i=1}^n x_i$). Namely, for $1 \le m \le n$, $u, v \ge 0$ with $u+v \le \sum_{i=1}^m x_i$, let
$T(m,u,v) = 1$ if there are disjoint subsets $A(m,u,v), B(m,u,v)$ of $\{1,\ldots,m\}$
such that $\sum_{i \in A(m,u,v)} x_i = u$ and $\sum_{i \in B(m,u,v)} x_i = v$, $T(m,u,v) = 0$ otherwise.
Thus
$$T(1,0,0) = T(1,0,x_1) = 1,\ T(1,u,v) = 0 \text{ otherwise.}$$
For $m > 1$,
$$T(m,u,v) = 1 \Longleftrightarrow T(m-1,u,v) + T(m-1,u-x_m,v) + T(m-1,u,v-x_m) \ge 1.$$

After computing all $T(m,u,v)$ using this recursion, you want to find the $(u,v)$ with $u$ as large as possible subject to $T(m,u,v) = 1$ and $u \le v \le S - u - v$.


How to represent a map data structure mathematically

There are multiple ways to represent it.

The simplest way is probably as a mathematical function $f:S \to T$ where $S$ is the type of the keys and $T$ is the type of the values.  In other words, you can represent it as a function/map.  Here we have $f(\mathtt{a}) = 10$, etc. (so this is different from the idea you mentioned in the question).

Here are some more sophisticated ways to encode this in a type system:

If the keys a, b, c, are statically known and never dynamic, and that set is fixed in advance and never changes, this could be represented as simply a tuple or a record type.

If the keys are static but you want to extend them, you could represent this as an extensible row type.  See also In type systems, is there a name for SQL's way of cutting and combining record types into new types? and Is there any difference between extensible records and dependent maps and Encoding row types.

If the keys are fully dynamic (their possible values aren't known at compile time), it needs to be represented as a function (i.e., map type).


Is a Turing machine without the ability to write on blank cells less powerful than standard Turing?

The type of Turing machine you describe is a linear bounded automaton (it can only write on the parts of the tape containing the input). LBAs are the acceptors for context-sensitive languages so to find a specific example of a problem that can't be solved with this restriction but can be solved in general by a Turing machine, you just need a language that is decidable but not context-sensitive.

The example given on Wikipedia is:

  An example of recursive language that is not context-sensitive is any recursive language whose decision is an EXPSPACE-hard problem, say, the set of pairs of equivalent regular expressions with exponentiation.

For more examples, see Is there an example of a recursive language which is not context sensitive?


What likely makes it confusing is that you are doing very different things in inductive versus coinductive cases. This is somewhat alluded to by Chlipala's reference to "infinite proofs"1. (Another aspect that makes seeing what is really going on hard is the presentation that makes coinductive type declarations look similar to inductive type declarations.)

I'm going to set up some context starting with inductive types. This is motivated by the categorical understanding of inductive types via initial algebras, but I'm not going to elaborate on that too much

Since inductive types are modeled by initial algebras, this means if we define the behavior of a function on cases, which corresponds to providing an algebra, we get a unique algebra morphism from the initial algebra to our just defined algebra, and this unique algebra morphism is the recursor. The main thing to note here for our purposes is that we get an morphism into the type of our choosing. This is evident from the type of a recursor, e.g. the one for naturals is $\forall T.T\to(T\to T)\to\mathbb N\to T$ so we get to choose $T$. To get the inductive eliminator, we can essentially do the same story but instead of using a category of types and functions, we use a category of families of types and families of functions. This is a massively oversimplified summary of Fibrational Induction Rules for Initial Algebras. Again, the upshot for us is that we get to choose the family (represented by a $\mathsf{Prop}$-valued function) and the result is a function into this family. Since from a Curry-Howard perspective, to prove the predicate that the family represents, we want to produce values in the family, and this situation is ideal. Note that the predicates we're proving are not themselves inductive types (though they could be).

The categorical story for coinductive types is categorically dual. We talk about final coalgebras instead of initial algebras. The main point for us is that a final coalgebra provides a unique coalgebra morphism from a type of our choosing into our coinductive type. This leads to the duality that it's simple to create a value of an inductive type while consuming one is involved, meanwhile it is simple to consume a value of a coinductive type but producing one is involved. This is somewhat obscured by the presentation of coinductive types in Coq.2

The problem is that if we want to prove some predicate, we need to produce a value of the appropriate type, but coinduction is about how to produce values of the coinductive type.

The "solution" is to consider coinductively defined predicates, and then we can use coinduction to produce values of these predicates to prove them. And this is what's happening in the examples. We are not using coinduction on streams to show that stream_eq holds. Instead, stream_eq is itself a coinductive type. The fact that stream is also a coinductive type is irrelevant here. For example, would could define stream_eq to talk about functions $\mathbb N\to A$ instead of streams. Indeed, the evalCmd example is defining a coinductively defined predicate over inductive types.

As for why the coinduction rule takes the form it does for stream_eq, this follows from its definition fairly mechanically except the notation obscures things a bit. First, we can make the equality of the heads more apparent by, instead of using the same variable for both, using two variables and an explicit equality. Something like:

  CoInductive stream_eq : stream A -> stream A -> Prop :=
  | Stream_eq : forall h1 h2 t1 t2,
    h1 = h2
    -> stream_eq t1 t2
    -> stream_eq (Cons h1 t1) (Cons h2 t2).

A record-oriented rewriting would make things clearer still, e.g.:

coinductive StreamEq (A : Type) (xs ys : Stream A) : Prop where
     headEq : hd xs = hd ys
     tailEq : StreamEq A (tl xs) (tl ys)

The coalgebra (in a category of families) that we need to apply coinduction corresponds to producing a family of functions from $R$ to a record of the same form as StreamEq only with $R$ in the place of StreamEq. A function into a pair can be split into a pair of functions and this exactly what Cons_case_hd and Cons_case_tl correspond to.

1 I don't really like this reference to "infinite data structures" and "infinite proofs" as that's not what's happening.

2 If we used a more record-like declaration syntax it would be more obvious. Having something like:

coinductive Stream (A : Type) where
    hd : A
    tl : Stream A

with corec would be something like

corec : (S : Type) -> (S -> { hd : A, tl : S }) -> S -> Stream A

would make this a bit clearer. This record-/projection-oriented view of coinductive types helps explain the guardedness conditions. What we're really specifying in a corec is the behavior of hd and tl. If we don't manifestly present a Cons to Coq, so it can take the hd of it as the definition of hd and the tl as the definition of tl, then Coq doesn't know what those definitions should be, and, of course, they might not exist at all which means we don't have a coalgebra and can't apply corecursion.


Complexity class that properly included in DLOGTIME

Regan & Vollmer suggest in the conclusion of the linked paper that such classes are constructible (though fiddly). The paper itself is about LOGTIME, and mentions where changes have to be made to adapt the results to LOGLOGTIME, LOGLOGLOGTIME etc., but don't explicitly demonstrate the results.


Implement K-means clustering with Map-Reduce

You can run a loop over $j\in\{1..k\}$:

Create a map that maps each point $x_i$ to itself if $x_i$ is nearest to the mean $m_j$, and to the zero vector otherwise:
$$x_i \rightarrow \begin{cases}(x_i, 1)  & d(x_i, m_j) \le d(x_i, m_l),\ l\neq j \\ (0,0) & \text{otherwise} \end{cases}$$
In the reduce stage, you would find the sums and counts:
$$(x_{i1}, c_1), (x_{i2}, c_2)\rightarrow(x_{i1}+x_{i2}, c_1+c_2)$$
You then divide the resulting sum by the total count.

Thus, for each iteration in the k-means algorithm you will need $k$ maps and $k$ reduces.


You probably cannot do much better than quote the abstract of Herlihy's original paper:

  A wait-free implementation of a concurrent data object is one that guarantees that any process can complete any operation in a finite number of steps, regardless of the execution speeds of the other processes. The problem of constructing a wait-free implementation of one data object from another lies at the heart of much recent work in concurrent algorithms, concurrent data structures, and multiprocessor architectures. First, we introduce a simple and general technique, based on reduction to a consensus protocol, for proving statements of the form, “there is no wait-free implementation of X by Y.” We derive a hierarchy of objects such that no object at one level has a wait-free implementation in terms of objects at lower levels. In particular, we show that atomic read/write registers, which have been the focus of much recent attention, are at the bottom of the hierarchy: they cannot be used to construct wait-free implementations of many simple and familiar data types. Moreover, classical synchronization primitives such as test&set and fetch&add, while more powerful than read and write, are also computationally weak, as are the standard message-passing primitives. Second, nevertheless, we show that there do exist simple universal objects from which one can construct a wait-free implementation of any sequential object.


Find combination of vectors from array that sum up to s

If $k$ is part of the input, the problem is NP-complete even when $m=1$ (and when we want to know if there's even a single solution). That is, when $m=1$, we essentially have a collection of $n$ values and our task is to decide if there is a subset of those that sum up to a target $s$. This is known as subset sum.

The Wikipedia page lists algorithms that you might be able to adapt to your more general case as well. Also, if $k$ is small enough, you might be able to do something better.


Thought process for the following problem?

Using O(n) extra space, you need to record start for each run of same numbers. Scan the array linearly. Once you removed a run, you either continue previous run, or start a new one.

for i:
  if a[i] != a[i-1]:
    if run[x] - run[x-1] >= 3:
      x--
      // avoid copying the run into output array
    if a[run[x]] != a[i]:
      x++
    run[x] = i

On the second thought, you don't need the run[] array - only start the of current run. Once a run eliminated, you can check that previous run is at least 3 elements long in O(1) operations. You still need O(n) place to store the list of eliminated ranges, though.


Are there automatic transformation of grammar algorithms?

If you are willing to implement an lr(k) algorithm then yes, there are transformations that you should do in order to obtain a correct parser:
first of all, you have to build an augmented grammar adding production S'->S, making S' the new axiom. This is actually not always necessary, but it allows you have a standardized procedure for all the productions so let's pretend it is for now. After that, you should also eliminate useless symbols from the grammar with the apposite algorithm.

If you execute lr(k) parsing under these hypothesis for the grammar, you should not have conflicts.

----- EDIT ----- I hope this will be of some help :)

An lr(k) parser builds a parsing table over a given grammar G. These parsers are able to recognize words generated from grammars which are deterministic context free and in lr(k) form. If a conflict occurs, then the language generated by the given grammar cannot be parsed using that table and the grammar is not a lr(k) grammar.

However, one can show that a language L is deterministic context free iff there exists k >= 1 such that L is generated by an lr(k) grammar.

I might be wrong but what I concluded from these notions is that if the grammar is lr(k) no conflicts should occur, and one of the definitions of a lr(k) grammar is:

The definition of lr(k) grammars states that the axiom must not occurr on the right hand side of any production, and should this is not be respected one needs contruct the augmented grammar first, using S' as new axiom and adding the only production S'->S. For further definitions of lr(k) grammars or a clarification of what I wrote, I advise to read The Theory of Parsing, Translation and Compiling (around page 370), since I fear I don't have the preparation to answer all questions.


A tree which each node selected as a root results in a different topology?

Here is a hint. If the tree has size $> 1$ it will have to have a vertex with degree $\ge 3$ as otherwise it would be in a line and the two ends would be equivalent. So consider a tree with a vertex having 3 branches out of it. The branches will have to have different lengths or the end vertices of equal length branches would be equivalent.

What's the smallest number of vertices in a tree of that form? Can you see how to expand the tree maintaining the required property?

Also note that this approach proves that the sizes of trees having the mentioned property are 1 and $\ge 7$.


What is the Big O estimate of a nested for loop?

The whole thing is $O(1)$. This is because the outermost loop has an upper bound of 100 i.e. it is constant, and it bounds the middle loop, which bounds the inner loop. There's a little bit of tricky math to figure out exactly how many times the loop is run, but you can know exactly how many times it is run.

The first hint that this is $O(1)$ is that there are no "free" variables. Pretend the code was linear. What would it be linear in terms of? There are no input parameters. We create $i$,$j$ and $k$, and their values don't change based on some input parameter.


Reducing infinite paths of a transition system to its set of sets of states

Since the set you want to output can be exponential in the size of the transition system, there is clearly no polynomial algorithm to enumerate it.
Thus, let's focus on an exponential time solution. To this end, it is actually quite easy to find a naive algorithm:
For every subset $Q\subseteq S$ (that contains $s_0$), in order to check whether $Q$ should be outputted by the algorithm, look at the subgraph induced by $Q$, and check whether there is a path from $s_0$ that goes through all the vertices in the induced subgraph.
One way to do the latter, is to indeed decompose the subgraph to its strongly connected components (SCCs), then look at the tree of SCCs, and make sure it's simply a directed path from $s_0$. If it is not a path, then you cannot traverse the entire set $Q$, as you would need to select a branching in the tree from which you cannot go back.
Thus, the test of whether $Q$ should be outputted can be done in polynomial time.


Does topological sort exist for any complete directed acyclic graph?

Yes it exists and the existence of a linear ordering not only shows the existence of the topological oredering over the vertices but also that this ordering is unique. It is not hard to prove that the graph represents a linear ordering using the facts that the graph is complete and acyclic. That should be a good exercise for you (proving a relation is a linear ordering means to prove it is reflexive, asymmetric and transitive).


Dynamic list for frame pointers and static list of nested activation frames

The two links can point to different frame.  Consider this variation:

PROCEDURE P;
  VAR x: INTEGER;
  PROCEDURE S;
  BEGIN X := 42
  END S;
  PROCEDURE Q;
  VAR y: INTEGER;
    PROCEDURE R;
    VAR z: INTEGER;
    BEGIN S
    END R;
  BEGIN R
  END Q ;
BEGIN Q
END P;

when calling S in R, it will set the static link pointing to R so that S can return to R and the dynamic link pointing to P so that S can access the correct X.