Can Double Hashing return the same value 2 times?

Let's demonstrate what you ask with a complete example. Let's say we have a table of size $|T| = 10$, in which we use double hashing to insert-search for an item. Initially we try to insert-search for an item using $i = 0$. This means we try at location $h_1(k)\mod 10$ let's say that is $3$. If there is collision we try at the next position that is at distance $h_2(k)$ from the current position. Or in other words we try for $i = 1$ thus at position $(h_1(k)+ h_2(k))\mod 10$ and so on. Usually $h_2(k)$ is build in such a way that gives values in the range [1, 10). So given an initial position if we move  less than the 10 positions (but at least 1) there is no way to hit the same location again. You can think table $T$ as a circular buffer. That is if we index a position out of the it's length we wraparound from the beginning of the buffer. So if initial position is 3 the next 9 positions are in sequence $4,5,6,7,8,9,0,1,2$.

So $h_2(k)$ gives the minimum length we move forward to probe for an empty position. This step is always < |T|. So from step to step there is no way to hit the same location.

You may wonder now that if  we miss to find an empty location to insert our k (or in case of search we don't hit k) after several tries (increments of i) then there is possibility to probe some location again after a lot of tries. That is true, but please correct me if I am wrong, that will happen if the load factor is high enough. In such a case you should use a bigger table size of try to fit in it smaller amount of items.

As far as I searched usually the $h_2(k)$ has the form $m - k \mod m$ where $m$ is the biggest prime smaller than |T| so $h_2(k)$ will always be $\neq 0$ and $< |T|$


clarification on multiple access in data link layer

If each communication is on a separate channel, you need to figure out what channels are free before you start communicating. How do you propose to do that? If you try to ask somebody, that requires communication, so how do you find out which channels are free for that communication? If you try to just listen to what comes past and figure out which channels are free at the moment, how do you know that a channel that's quiet at the moment is really free, and it's not just that its users have paused for a moment. What do you do if somebody else also starts transmitting on that channel at the same time as you?

Alternatively, you need to preallocate $\tfrac12n(n-1)$ channels to your $n$ hosts, so that each pair of hosts has a specific channel to talk on. But that doesn't scale.


Could an NP-Hard problem be in P in after a basis transform?

The only way they could propose to solve the problem (that I can think of) ... would seem to be exponentially hard."

That's your core fallacy, and "that I can think of" is the answer. The complexity of the problem did not change, but the transformation made finding an efficient algorithm easier (as a tool).

Yes, it's certainly possible that we have yet to find a similar tool that, once we have it, allows even our feeble minds to easily find efficient algorithms for NP-hard problems. That would be a constructive and generalisable proof for P=NP, that is something like a holy grail.


Why are combinators important in lambda calculus?

The word "combinator" has some connotations that you don't seem to be intending here and sometimes a stricter definition.  Another term for the definition you gave is a closed term.  The opposite is an open term.  The programming language equivalent of an open term would be an expression referring to a variable that's simply not in scope.  Not just not in the current scope, but not in any containing scopes either.  Most languages simply don't allow this.  We can model let expressions that locally bind a name with lambda abstraction and application. In particular, let x = E in B becomes $(\lambda x.B)E$.  The top-level, or global, scope can then be thought of conceptually as just a short-hand for wrapping your program in a bunch of let expressions.  The point being, even global names are bound.  The analogy to an open term, in this context, would be a term with one or more completely undefined variables in it.

Now clearly a closed term is self-contained which is useful. Further, for the purposes of computation, we never need to consider anything other than closed terms (assuming we start with nothing but closed terms).  More precisely, for computation we usually care about weak (head) normal form which is the normal form for call-by-value(/name) reduction.  An important aspect of these reduction strategies is they never reduce under a lambda.  As such, any instance of $\beta$-reduction using these reduction strategies will only involve closed terms and will only ever produce a closed term assuming the initial term was closed.  So, for the purposes of programming and computation closed terms are all that matters. Optimizing compilers, though, manipulate programs and often do perform reduction under a lambda and as such do need to deal with open terms.  Proof assistants also need to deal with open terms as they usually need to reduce to normal form to compare lambda terms for equality. (Actually, they can often avoid going all the way to normal form.)

The focus on "combinators" isn't driven by software engineering concerns.  It's simply a fact that for many purposes you only need to consider closed terms.  The theory and formal manipulation of open terms is quite a bit hairier than for closed terms, so it is useful to limit to closed terms when possible.


Solving $T(n) = 2T(\frac{n}{2}) + n\log(n)$ without master theorem

For direct result let's use direct summation assuming $n=2^k$:
$$T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)=2\left[ 2T\left(\frac{n}{2^2}\right) +\frac{n}{2}\log \frac{n}{2}\right]+ n\log(n) = \\
=2^2T\left(\frac{n}{2^2}\right)+n\log \frac{n}{2}+ n\log(n) =\\
=\cdots=\\
=2^kT\left(1\right)+n\log \frac{n}{2^{k-1}}+ \cdots +n\log \frac{n}{2}+n\log(n)=\\
=2^kT\left(1\right) +n\log 2 + \cdots +n\log 2^k=\\
=nT\left(1\right) +n\log 2 (1 + \cdots + k) =nT\left(1\right) + \frac{k(k+1)}{2} n\log 2 \in \Theta (n \log^2 n)$$
where, of course, $k=\log_2 n$. Hope you can obtain from here everything what you wanted.
At end let me note also, that $n \sim n\log(n)$ and other equivalences, which you are using, are not correct, if we understand standard $\lim \frac{f}{g}=1$, for symbol "$\sim$". Correct is, for example, $n = o(n\log(n))$ etc.


How to determine the maximum valued play in Rummikub?

I will describe a polynomial time algorithm that solves both problem 1 and problem 2. I learned of the algorithm from this paper.
I am going to make the following assumptions:

No jokers (adding them is a small change).
There are only four colors.
There are at most two copies of each tile.
The face values range from 1 to 13.

To find the maximum value play, complete these steps:

Recursively enumerate every valid configuration that can be built from tiles in $hand \cup board$
Ignore any configuration where not all tiles from board are used (the board constraint).
Of the visited configurations, choose one with maximal score. Where score is the sum of values of tiles played or number of tiles played (whichever you prefer to maximize).

Step 1
How do we build a configuration from a given set of tiles?
We proceed by playing tiles in order of their face value.
First play all tiles of value 1.
Then play all tiles of value 2, and so on.
We can visit every configuration by recursing for each way to play tiles of the current value.
Let's look at the different ways to form runs.
Assume we are playing tiles of value 5, that we have a red 5, and that we will use it in a run.
Our tile can be used to start a new run or it can be used to extend any existing run (or partial run) that contains a red 4.
If we extend an existing run then there is at most two choices for where to put it since there is at most two runs that contain a red 4 (there are at most two red 4's).
If we have two copies of our tile then we can extend or start two runs.
In forming runs there is an optimization that can be made.
We should not start a new run if we know in advance that there is no way we could finish the run.
This can be implemented by counting the number of tiles of greater value.
Now on to forming groups.
For a given way to play runs we should recurse for every way to play groups using the remaining tiles since we want to enumerate all possible valid configurations.
However this would be very slow and in the end we really only care about finding the best configuration.
So instead we recurse for only the best way to play groups.
Notice, for a given choice of how to form runs, how we form groups does not effect what choices we have in forming groups and runs using tiles of greater value.
So given a choice of how to form runs, we should use as many of the remaining tiles in groups as possible.
To do this enumerate all ways to pick groups and choose the one containing the most tiles.
Finally after choosing how to play all tiles, discard any tile not used in a valid set.
Step 2
How do we ensure every valid configuration we visit uses all tiles from board?
After choosing how to play all tiles and discarding invalid sets, do not accept the configuration as valid if not all tiles from board are contained in it.
This is correct but it would be inefficient.
Instead we check at each step, after choosing how to form runs and groups, whether we have used enough tiles of the current value.
For example, if the current value is 5 and we have chosen a way to play the red 5's, then we need to check if we have played at least as many red 5's as are contained in board.
If we have not, then we choose another way to play red 5's before moving to the next value.
Note if we have played $n+m$ red 5's where $n$ is the number of red 5's in board, then we have played $m$ red 5's from our hand.
If there is no way to play red 5's (including not playing red 5's) then this branch of the recursion tree does not lead to a valid configuration and we should return.
However, these checks are not sufficient to guarantee we never violate the board constraint. Why?
Because when forming runs using tiles of value 6 we can choose to not extend a run that has length one or two.
The tiles in that run would have to be discarded which could violate the board constraint due to not having enough 4's or 5's.
In this case we would not be able to catch this error because so far we only know how to check the board constraint for the current value.
The way to fix this is to keep count of how many tiles we have played of the previous two values (for each color separately).
Then when forming runs with red 6's we can check if not extending a red run (of length one or two) puts us in a state where not enough red 4's or 5's have been played.
Note that if a run has length at least three then not extending it does not force us to discard any tiles and so can not violate the board constraint (so we do not have to check in this case).
We do not have to do anything special for choosing groups. In the following proof of this fact I will use 'configuration' to mean a set of groups.
Also, I will use 'maximal configuration' to mean a configuration containing the most tiles possible among all configurations where tiles come from some set $S$.
Note that if we have $n$ tiles of color $c$ in a configuration then there are at least $n$ groups in the configuration.
Also if a subset of the available tiles can be arranged into a configuration of $n$ groups then a maximal configuration contains at least $n$ groups (there are at most three groups, if using two jokers, and at most two groups of four in any configuration).
Now assume a subset $S$ of the available tiles can be arranged into a configuration with $n$ tiles of color $c$ and that we have arranged some maximal configuration $M$.
If $M$ contains $k < n$ tiles of color $c$ then $M$ contains at least $n - k$ groups which do not contain a tile of color $c$ (groups of size three).
In this case we can add $n-k$ tiles of color $c$ from $S$ to $n-k$ groups of three in $M$ which contradicts that $M$ is a maximal configuration.
Thus $k\geq n$.
This shows that if there are $n$ tiles of color $c$ in the set of tiles of current value that remain after playing runs and if those $n$ tiles can be played in some configuration then every maximal configuration contains those $n$ tiles.
So choosing a maximal group guarantees that we satisfy the board constraint if it is possible to satisfy the board constraint by playing groups.
Step 3
A simple way to do step 3 would be to compute the score of a configuration when you accept it as valid then update some global variable with the configuration of max score ('configuration' meaning set of runs & groups).
But this solves the same subproblem many times (compute score for sets common to more than one valid configuration).
Instead make use of the fact that we know at each step how many tiles of the current value we will play.
Multiply this number of tiles by the current value to find how much these choices contribute to the score.
Sum the contribution with the return value of the recursive call and then update the max if necessary.
Instead of updating a global max variable, we will update a local (available only in scope of recursive call) max variable which will hold the score of the best way to play tiles of the current value.
The recursive function should return the value of this max variable.
After attempting to play tiles of current value in all ways, if no play leads to a valid configuration (every play violates the board constraint), then return $-\infty$.
Returning $-\infty$ is useful because even if we have a high contribution (from runs & groups), adding that contribution to $-\infty$ is still $-\infty$.
Note that we cannot know the contribution of extending a length zero or length one run. This is because, when playing tiles of the next greater value, we may choose to not extend a run of length one or two and so the tiles in those runs would be discarded.
Instead we say the contribution of extending a length zero run (starting a run) or length one run is 0.
When a run is extended from length two to length three then we say it's contribution is the sum of the values of the three tiles in the run.
When extending a run that has length at least three then the contribution is just the value of the tile played into the run.
There are other things you can do here too. For example, It may be desireable to find a configuration that is maximally similar to the previous configuration of the board.
This can be done by maximizing score and then maximizing some similarity function. This would inflate the dp table size by two.
State, Memoization, & Time Complexity
The only state we need to know is the current value and the length of the runs that we could possibly extend.
The length of runs can be recorded in a list of pairs, for example [(0,0), (0,0), (0,1), (0,3)], where the $i^{th}$ pair is the length of the two possible runs of color $i$.
The order of the numbers in the pairs does not matter so the above state is the same as [(0,0), (0,0), (1,0), (0,3)].
A particular extension (i.e. child state) of those runs could be [(1,1), (0,1), (0,0), (1,3)].
Also, we never need to know if a run is longer than three tiles (so an extension of (3,3) is (3,3)).
We will only need to distinguish between when a run is of length 0, 1, 2, or 3.
A benefit of this is the size of the state space is reduced which makes memoization much more effective.
This algorithm is exponential in the number of distinct values in $hand \cup board$.
However it can be made linear by memoization.
To memoize, store in a dictionary the key-value pair key=(currentTileValue, runLengthsList) and value=localMaxValue.
Other inputs like the board, $hand\cup board$, number of jokers available, number of tiles played per color on the last two turns, etc, are just used to bound the search and so we do not need to memoize them.
Hopefully I have been able to effectively communicate most of the ideas of this algorithm.
For more details see the paper and my implementation.
Note, the paper claims that the dynamic programming state space (number of unique inputs, max size of dp table needed, i think) is of size $n * k * f(m)$.
Where $n$ is the number of possible tiles, $k$ is the number of colors, $m$ is the max number of copies of a tile, and $f(x)$ computes 4 choose $x$ with replacement.
This might be a typo, I do not know.
In any case the state space of the algorithm I've described is $n * f(m)^k$.
Note both the paper and my implementation refer to what you call the board as the table.
By the way, before learning of this algorithm, I tried to understand the algorithm you gave here.
I could not understand how to deal with duplicates.
I can see how breaking into sublists, ordering those sublists, and then combining them into a single list again would allow your recursive formula to handle duplicates for some inputs.
But you did not describe how exactly to break the original list into sublists nor how to combine them into a single list again.
For some inputs, your recursive formula will give different answers depending on how sublists are split/recombined.
Unfortunately, I do not have enough stackoverflow reputation to comment on your answer to ask for clarification.
Thanks for giving the answer though, your recursive formula is nice.


Number of ways to fill a 2xN grid with M colors

You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is
$$ \frac{M!}{(M-N)!} \sum_{T=0}^N (-1)^T \binom{N}{T} \frac{(M-T)!}{(M-N)!}. $$
I'll let you take it from here.


Given the same set of nodes, why is it (generally) easier to find a Euler cycle than a Hamilton cycle?

Suppose you are trying to find a Hamiltonian cycle on a graph.

You can solve this efficiently in the manner you describe (i.e. converting vertices into edges and then solving for an Euler path) if and only if the graph is a line graph.

There are a number of characterisations of line graphs.

For example, a graph is a line graph if and only if it does not contain any of these 9 graphs below as a subgraph:

An alternative characterisation is that a graph is a line graph if and only if you can partition the graph into cliques such that every vertex belongs to exactly two cliques.

This characterisation is perhaps more useful as you can apply Euler's proof to these cliques.


Can the complement of an unrecognizable language be a recognizable language?

Sure: the Halting language (sometimes called $K$) is recursively enumerable whereas its complement ($\overline{K}$) is famously not.

Generally speaking, the existence of such languages follows from the implication you state -- the complement of enumerable yet undecidable languages can not be enumerable -- by the existence of precisely enumerable yet undecidable languages.

That said, there are also non-enumerable languages whose complement isn't either.


Language whose intersection with a CFL is always a CFL

Let $L = \{a^n b^n : n \geq 0\}$, and let $L_0$ be an arbitrary context-free language. Define $L_1 = L_0 \cap a^* b^*$, and note that $L_1$ is context-free and $L \cap L_0 = L \cap L_1$. Let $S = \{(i,j) : a^i b^j \in L_1\}$.

According to Parikh's theorem, the set  $S$ is semilinear. The set $D = \{(n,n) \geq 0\}$ is also semilinear (in fact, it is linear). Since the semilinear sets are closed under intersection, $S \cap D$ is also semilinear. Since $S \cap D$ is (essentially) one-dimensional, it is eventually periodic. This shows that there is a finite language $F$, a modulus $m \geq 1$ and a subset $A \subseteq \{0,\ldots,m-1\}$ such that
$$
L \cap L_1 = F \Delta \{ a^n b^n : n \bmod m \in A \},
$$
where $\Delta$ is symmetric difference. It is easy to check that $\{a^nb^n : n \bmod m \in A\}$ is context-free, and so $L \cap L_1$ is context-free.

Summarizing, we have shown that $L$ is a non-regular language which satisfies your condition.


2OPT Approximation Algorithm for Multiway Cut Problem

Minimum $k$-Multiway Cut

Given a graph $G =(V,E)$ and a set of terminals $S=\{s_1, s_2, \dotsc, s_k\} \subseteq V$ find a minimum set of edges $E' \subseteq E$ whose removal separates each pair of terminals in $S$.

Case when $k=2$

For the case when $k=2$ Minimum $k$-Multiway cut is exactly the Minimum $s$-$t$ Cut problem. To see this simply let $(s_1, s_2) = (s,t)$ and compute a min $s$-$t$ cut. This can be solved in polynomial time by various Maximum-Flow algorithms.

Case when $k \geq 3$

We can design a very simple 2OPT approximation algorithm for the $k$-Multiway Cut problem. For each $s_i$, where $1 \leq i \leq k$, collapse $S \setminus \{s_i\}$ into a single node $t_i$. Compute a min $s_i$-$t_i$ cut and call it $C_i$. Repeat this for each possible $s_i$. Output  $C = \bigcup_{i=1}^k C_i$.

Claim: $|C| \leq 2 \textrm{OPT}$

Let $A$ be the optimal multiway cut and let $A_i$ be a cut that separates $s_i$ from the rest of the graph. Since each edge in $A$ is adjacent to 2 components, each edge must be in two of the cuts $A_i$. Hence, $$\begin{align*}&\sum_i |A_i| = 2|A| &(*)\end{align*}.$$ Further, since $C_i$ is a minimal cut, $|C_i| \leq |A_i|$. This fact together with $(*)$ implies that our algorithm achieves a $2\mathrm{OPT}$ approximation ratio.

Claim: $\text{Proposed algorithm runs in polynomial time}$

The algorithm requires $k$ calls to a Minimum $s$-$t$ cut procedure. Since we only make a constant number of calls to a polynomial-time algorithm, our resulting algorithm is still polynomial.

You can further improve this to $(2 - \frac{2}{k})\mathrm{OPT}$ by dropping the heaviest cut. Beating that bound requires a slightly more advanced LP rounding schema.


Is selecting some of the sets such that their intersection is of size k NP-hard?

As you suggested, the problem is equivalent to selecting sets with union of given size $k$. It is not easier than selecting given numbers (say, $m$) of sets with union of given size $k$, since we could add different auxiliary elements $a_S^{(0)},\ldots,a_S^{(n)}$ to each set $S$ and ask for a union of size $m(n+1)+k$, where $n$ is the size of the original universe. Now it is not hard to show the later problem is NP-hard because of a reduction from X3C (exact cover by 3-sets).


Efficient computation of traces of all primitive elements in field extensions of GF(2)

It's straightforward to solve this problem in time $\phi(2^n-1)$ field operations, and there's no hope to do significantly better than this.

Computing the trace of a single element can be done in $n$ field operations (just by applying the definition).  So, we can simply compute the trace for each of the $\phi(2^n-1)/n$ elements with distinct trace.  The running time will be $n \times \phi(2^n-1)/n = \phi(2^n-1)$.

There is no hope to do significantly better than this.  There are $\phi(2^n-1)$ primitive elements in the field.  If you want an algorithm to output the trace of all of those values, the length of the output from the algorithm has to be at least $\phi(2^n-1)$.  It follows that the running time of any such algorithm has to be at least $\Theta(\phi(2^n-1))$.  So, you can't do asymptotically better than the straightforward algorithm.

Finally let me point out that $\phi(2^n-1)$ is exponentially large in $n$ (in general).  This means that any algorithm for your problem will have running time that is exponential in $n$.  This means that no algorithm can possibly be efficient for anything except very small values of $n$.


Are these languages RE? How would I determine this?

Neither of these languages are RE.

Here's an intuitive way to think about this - a language $L$ is RE iff for any string $w$, there is some finite piece of information you could provide about $w$ that could convince a computer that $w$ belongs to $L$.

In the case of language (1), what information could you give me that would convince me that a TM belonged to this language?  To show that a TM belonged to that language, you'd need to convince me that every string ever accepted by that TM has length at most 13.  It doesn't seem likely that there is any finite piece of information you could give me that could convince me that the TM has this property.  (On the other hand, if a TM didn't have this property, it's easy to convince me of this - give me a string that the TM accepts that is longer than length 13, and I could confirm it by running the TM on that string and observing it accept).

To formally prove that language (1) is not RE, you could try doing a reduction from a language that's already known to not be RE.  One good example of this would be the diagonalization language $L_D$:

$$ L_D = \{ \langle M \rangle | M \mbox{ is a TM and } \langle M \rangle \notin L(M) \}$$

This is the set of all descriptions of TMs that don't accept themselves.  You can reduce $L_D$ to your language $L$ using the following reduction: given a TM $M$, build a new TM $N$ that does the following:

  When $N$ receives an input string $w$, it first runs $M$ on $\langle M \rangle$.  If $M$ accepts its own description, then $N$ accepts $w$.  If $M$ rejects its own description, then $N$ rejects $w$.  (Implicitly, if $M$ loops on its own description, then $N$ loops on $w$)

This machine has the property that if $M$ does not accept itself, then $N$ never accepts anything at all, and so $\langle N \rangle \in L$.  On the other hand, if $M$ does accept itself, then $N$ accepts everything, so $\langle N \rangle \notin L$.  This is a mapping reduction from $L_D$ to $L$, and since $L_D \notin RE$, this shows $L \notin RE$.

I'll leave the second of these as an exercise.  Use the same intuition as before to think about why the language isn't $RE$, then try using a mapping reduction from $L_D$ to formalize it.

Hope this helps!


When the stall is actually going to happen?

As part of the instruction decode phase, the operands are fetched for the instruction. In a very naive pipeline implementation, the operands for read  will only be visible after the write instruction has written back its changes to the internal registers (so the last stage).
To prevent such long stalls, a CPU can apply tricks like forwarding the store to the load as soon as the value is determined instead of needing to wait for the write to the registers.
Check out the following for a more detailed answer:
https://youtu.be/EL8uqzSsg_Q?t=433


Is the constant pi (not Raspberry) ever used in general computer science?

The $\pi$ constant is not used in theoretical computer science due to some intrinsic value or utility of the constant itself.
However, it is (obviously) used in the simulations of physical systems or mathematical equations in which it appears. Precisely for this reason, one of the efforts that computer scientist and mathematicians have made in this regard was to identify new methods and algorithms to be able to generate as many digits of its decimal expansion as possible.

If today we know $\pi$ up to 31.4 trillion decimal places
we owe it to the computational power of electronic systems.


Can I simplify log(n+1) before showing that it is in O(log n)?

Simplifying the left-hand side is a good strategy. You aren't going to find a simpler expression that's equal to $\log(n+1)$, though. However, since you're only interested in proving that $\log(n+1)$ is “not too large”, it can be a good strategy to find an intermediate step that's larger than $\log(n+1)$ but still not too large. That is, try to find a function $f$ such that $\log(n+1) \le f(n)$ (for sufficiently large $n$), and $f(n) \in O(\log n)$.

(Easy exercise: prove that this is true — if you've found a such a function $f$ then $\log(n+1) \in O(\log n)$.)

So you can try to fill in the statement $\log(n+1) \le \ldots$ with something simpler on the right-hand side. “Simpler” meaning that in the end it'll be simpler to prove that this is in $O(\log n)$. So keep the definition of $O$ in mind: you'll need to prove that $f(n) \le C \log n$ for some $C \gt 0$.

This suggests trying to find $f$ of the form $C \log(n)$.

Hint:

   $x + 1 \le x + x$

Hint #2:

   You can say that again.

Of course this approach works for other functions and other bounds.

Exercise (open-ended): can you generalize this to $\Omega$? To $\Theta$? To $o$?


Is the runtime of binary search big omega of logarithm of n?

First, you can analyze the time complexity of binary search in whatever case you wish, say "best case" and "worst case". In the best case, you use $f(n)$ time, while in the worst case you use $g(n)$ time. These are two functions of $n$, describing two different scenarios you have defined. Now, you can make statements such as $f(n) = O(1)$ or $g(n) = \Theta(\log n)$. However, the Big Oh of a function has nothing to do with time complexity, it is merely something applied to a function that could just as well be representing the number of apples you get for $n$ euros.

In particular, thinking along the lines of "$O$ is always for best case, $\Omega$ is for the worst case" (or whatever), is wrong and dangerous.

To you specific question: if a function $g(n) = \Omega(\log n)$ and $g(n) = O(\log n)$, then $g(n) = \Theta(\log n)$. The function $g(n)$ might be representing the time complexity of binary search or the number of apples, it doesn't matter. And as always, look at the definitions and you can stop guessing.


Example of two undecidable languages that cannot be mapping reduced to each other

There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.
Below, $\Phi_e$ is the $e$th oracle machine according to some standard enumeration (in older texts this is often written "$\{e\}$," which ... yeah).

The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of finite binary strings $$\sigma_0\prec\sigma_1\prec\sigma_2\prec ...\quad\mbox{and}\quad  \tau_0\prec\tau_1\prec\tau_2\prec ...$$ such that for each $i$ there do not exist infinite binary sequences $f,g$ extending $\sigma_i,\tau_i$ respectively such that $\Phi_i^f=g$ or $\Phi_i^g=f$.

Proving that such sequences in fact exist is a good exercise.

Taking $$a=\bigcup\sigma_i,\quad b=\bigcup\tau_i$$ we then have that $a$ and $b$ are Turing-incomparable. (Thinking about this construction a bit, we can in fact ensure that $a,b$ are Turing-reducible to the halting problem.)

A better result is that there are computably enumerable sets which are Turing incomparable (the Friedberg-Muchnik theorem). This is much harder to prove, however; it was the first example of a priority argument.
Yuval Filmus commented that a pair of "random" languages should probably work. There are multiple senses in which this is true - in particular, the set of pairs of infinite binary sequences which are Turing incomparable is both comeager and of full measure in the space of all pairs of infinite binary strings (with the usual topology and measure). The former observation is basically just the mutual diagonalization argument above, slightly tweaked; the latter is a bit harder to prove. (In general, in computability theory measure is more complicated than category.)

In fact, the proofs of the observations in the previous paragraph actually yield stronger results without significant changes: namely, we get that for every noncomputable infinite binary sequence $f$ the set of infinite binary sequences Turing-incomparable with $f$ is both comeager and of full measure in the space of all infinite binary sequences.


Why is it that the transition function for DPDA's only works for 1 alphabet symbol, and 1 stack symbol?

Nondeterminism, means the machine has a choice. In both your examples, it indeed has a choice.

Let's assume the stack has an 1 on its top, and the next input symbol is 0.
The PDA can choose whether to take the transition $f(q_i,1,0)\to(q_i,0)$ or  $f(q_i,\epsilon,0)\to(q_i,0)$. Note that the effect is different: in the first it deletes the 1 in the stack and puts a 0 instead of it. In the second it adds a 0 on top of the 1 without removing it.

Therefore, there are two (different) paths the machine can go from this points, hence the nondeterminism.

Just to clarify: the definition for Deterministic-PDA is clear-cut: at any moment, and for any input/stack/state configuration there is only one possible transition. If this is not the case, the PDA is non-deterministic even if multiple transitions lead to the same configuration. It's just a matter of definition.

However, in the question above, the two transitions may actually lead to different configurations, which makes the nondeterminism even more clear.


What is the correct complexity of All paths from Source to Target DFS solution?

First recall the definition of topological sort: given a DAG (Directed Acyclic Graph) with vertices $1, \dots n$ define the vector $\operatorname{TS}[1, \dots n]$ such that $\operatorname{TS}[1, \dots n]$ is a permutation of $1\, \dots n$ and $i < j$ implies that a path from node $\operatorname{TS}[j]$ to $\operatorname{TS}[i]$ does not exist. This vector can be computed in $\mathcal{O}(n)$ time.

Consider the algorithm exposed in your link, and denote with $T(n)$ the time complexity of that problem for a DAG of size $n$, then it holds:

$$ T(n) = \sum_{i=1}^{n}T(i).$$

Proof: If you call your function on $\operatorname{TS}[i]$ its execution consists of recursively calling that function on the sub-graphs composed of vertices reachable (following a directed path) from $\operatorname{TS}[j]$ such that $(i, j) \in E$. Exploiting the topological sort property it turns out that

$$\{\text{Vertices Reachable from} \operatorname{TS}[j]\} \subseteq \{\operatorname{TS}[k] \;|\; k = j + 1, \dots n\}.$$

Moreover $(i, j) \in E \implies i < j$, then you are calling the same function on smaller instances of the same problem, satisfying the equation above.

Finally, considering that $T(0) = T(1) = 1$ the complexity is $T(n) = \mathcal{O}(2^n)$ that solves that recursion.


Fill in objects that pop out from background?

Here is one simple approach:

Step 1. Find the background color.  (This is an entire topic in its own right, so if you're not sure how to do this, ask a separate question about it.)

Step 2. Binarize the image so that all pixels whose color is close to the background color are white, and all pixels whose color is not similar to the background color are black.  This will get you a rough approximation to what you want, but there might be holes in the middle of the black shape (e.g., if the cat was wearing a white collar).

Step 3. Apply a suitable morphological operator, e.g., the closing operator.

This approach will have some limitations, e.g., if the background is not flat but rather has shading or a gradient, but it is simple to implement and try.

If the simple approach I outlined above is not sufficient, the broad problem area you are looking at is image segmentation; you should check out the techniques that have been developed in the literature.  There are many, many methods for image segmentation that you could explore.  For instance, you could look at methods based upon graph cuts.


Let $s_2,s_3$ be the states on the second and third days, and let $x_2,x_3$ be the indicators of carrying an umbrella on these days. Then
$$
\newcommand{\Sunny}{\mathit{Sunny}}
\newcommand{\Rainy}{\mathit{Rainy}}
\newcommand{\Foggy}{\mathit{Foggy}}
\newcommand{\Yes}{\mathit{Yes}}
\newcommand{\No}{\mathit{No}}
\Pr[s_3 = \Foggy \mid s_1 = \Sunny, x_2 = \Yes, x_3 = \No] =
\frac{\Pr[s_3 = \Foggy, x_2 = \Yes, x_3 = \No \mid s_1 = \Sunny]}{\Pr[x_2 = \Yes, x_3 = \No \mid s_1 = \Sunny]}
$$
It seems you might have forgotten the denominator.


How could a formal system ever be non-obviously unsound?

You jumped to a conclusion when you said that "when setting up $F$ one always makes sure that all the axioms are true under the intended interpretation". This is not the case at all. Using theories and formal systems as devices with which we reliably discover thruths is only one possible application.

Insisting that a formal system must be sound with respect to an "intended interpretation" can have the unfortunate effect of holding back development. For example, in order to discover non-Euclidean geometry someone had to contradict the dogma that Euclid's geometry was obviously true, and suggesting a theory which was non-Euclidean (which was considered obviously unsound) amounted to taking a professional career risk.

Sometimes there is no intended interpretation because we are exploring a new mathematical theory with which we have very little experience. In such a situation we will attempt to identify possible axioms and hope that their consequences will inform us about what is going on.

Sometimes we simply do not know what the intended interpretation is, and so we have to make a choice about accepting or rejecting an axiom based on other criteria than truth. Or better, we do not make a choice and study several options, without obsessing about "intended model". The most famous example of this is the axiom of choice in set theory. We know that set theory with choice is consistent if, and only if, set theory without choice is consistent. Which one is sound? On what grounds do we decide whether the axiom of choice is "true in the intended interpretation"?

So what is wrong with your view? I don't think much is wrong, except that it can hinder mathematical development. I advocate the position that the so called "intended interpretation" is in general an unknowable and uncommunicable entity whose existence is grounded in history and collective social norms. Of course, this does not imply that the "intended interpretation" is completely useless. On the contrary, it binds mathematicians together and allows them to share intuitions, and give coherence to mathematical development. But let us not confound an informal mathematical idea of "intended interpetation" with its mathematical ideal of a model.


Let's program it and see what happens:
#include <stdio.h>

int main(int argc, char *argv[]) {
  unsigned char mem[4] = { 0xde, 0xad, 0xbe, 0xef };

  printf("%02hhx %02hhx %02hhx %02hhx\n", mem[0], mem[1], mem[2], mem[3]);
  printf("%04hx %04hx\n", *(unsigned short *)(mem), *(unsigned short *)(mem + 2));
}

Here is the output:
de ad be ef
adde efbe


Prove $L = \{M \mid L(M)\text{ is infinite}\}$ is not Turing-recognizable

Recall that the input to the halting problem is a pair $(\langle M\rangle, w)$ and we must accept this input if $M(w)$ halts, and reject it otherwise.

We want to decide the halting problem by reduction to $\overline{L}$.  That is, we need to produce a computable function $f$ that takes an input $(\langle M\rangle, w)$ and produces a string in $\overline{L}$ if $M(w)$ halts and a string that is not in $\overline{L}$ if $M(w)$ does not halt.

There's a small mistake in your reasoning in the question that's worth mentioning at this point, but it doesn't make any real difference.  Strings in $L$ are descriptions of Turing machines that accept infinitely many inputs.  That means that a string is in $\overline{L}$ if either it's a description of a Turing machine that only accepts finitely many inputs, or if it's not a description of any Turing machine at all.

However, we can ignore the strings that don't describe Turing machines and design a function $f$ such that $f(\langle M\rangle,w)$ is always the description of a Turing machine and that Turing machine accepts only finitely many inputs if $M(w)$ halts, and is one that accepts infinitely many inputs if $M(w)$ doesn't halt.

Hint: $\emptyset$ is finite and $\Sigma^*$ is infinite.  Transform $(\langle M\rangle,w)$ into the string $\langle M'\rangle$ such that $M'$ will accept nothing if $M(w)$ halts and will accept everything if $M(w)$ doesn't halt.

There's another hint below, which you can see by mousing over the yellow box. But try to figure it out on your own, first.

   Hint 2: the reduction is very similar to the one used to prove that the problem "Does $M$ halt on the empty input?" is undecidable.


Formal Logic - Natural deduction: Problem with assumptions about exists-negation

It is a bit hard to say exactly which introductions you should perform since we don't have your rule set, but I think the over all strategy should be as follows:
From $\neg (S \lor (P \to Q))$ you get $\neg (P \to Q)$.  Since you have $\neg Q$, you should try to introduce $\neg P$ and thus obtain $P \to Q$.  That should be a contradiction and you can conclude $P$.


Explanation about the condition for connectivity in Erdos Reyni model

If a graph is not connected then there must be a set $S$ of vertices not connected to its complement. Furthermore, we can assume that $|S| \leq n/2$. For a given set $S$, the probability that $S$ is not connected to its complement is
$$
(1-p)^{|S|(n-|S|)} \leq e^{-p|S|(n-|S|)}.
$$
The union bound shows that the probability that some such $S$ exists is at most
$$
\epsilon := \sum_{k=1}^{n/2} \binom{n}{k} e^{-pk(n-k)} =
\underbrace{\sum_{k=1}^{n/4} \binom{n}{k} e^{-pk(n-k)}}_{\epsilon_1} +
\underbrace{\sum_{k=n/4+1}^{n/2} \binom{n}{k} e^{-pk(n-k)}}_{\epsilon_2}.
$$
When $k \leq n/4$, we have $n-k \geq (3/4)n$ and so $$e^{-p(n-k)} \leq e^{-(3/4)pn} = \frac{1}{n^{3/2}}.$$
Using the bound $\binom{n}{k} \leq n^k$, we get
$$
\epsilon_1 \leq \sum_{k=1}^{n/4} n^k \cdot n^{-(3/2)k} =
\sum_{k=1}^{n/4} \frac{1}{n^{k/2}}.
$$
We can estimate this by considering separately $k=1$, $k=2$, and $k \geq 3$:
$$
\epsilon_1 \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \sum_{k=3}^{n/4} \frac{1}{n^{3/2}} \leq \frac{1}{\sqrt{n}} + \frac{1}{n} + \frac{n}{4} \cdot \frac{1}{n^{3/2}} = O\left(\frac{1}{\sqrt{n}}\right).
$$
When $n/4 < k \leq n/2$, we have $n-k \geq n/2$ and so $e^{-p(n-k)} \leq e^{-pn/2} = 1/n$. Using the sharper upper bound $\binom{n}{k} \leq (\frac{en}{k})^k$, we get
$$
\epsilon_2 \leq \sum_{k=n/4+1}^{n/2} \left(\frac{en}{k}\right)^k \cdot \frac{1}{n^k} = \sum_{k=n/4+1}^{n/2} \left(\frac{e}{k}\right)^k.
$$
The summands $(e/k)^k$ are decreasing, and so
$$
\epsilon_2 \leq \frac{n}{4} \left(\frac{4e}{n}\right)^{n/4} \leq \left(\frac{4e}{n}\right)^{n/4-1} = O\left(\frac{1}{\sqrt{n}}\right),
$$
since when $n \geq 6$, the exponent is at least $1/2$.

Putting everything together, we get that the probability that the graph is not connected is at most
$$
\epsilon = O\left(\frac{1}{\sqrt{n}}\right).
$$

Using more refined arguments, one can show that when $p = \frac{\ln n + c}{n}$ for constant $c$, the probability that $G(n,p)$ is connected tends to $e^{-e^{-c}}$. Moreover, in a certain precise sense, the only obstacle to connectivity (whp) is isolated vertices.


You could define what "least connected" means (precisely) in a variety of ways, where the precise definition chosen may affect the output of the algorithm (and there is no unique correct definition for this). But you may wish to look into Community Detection algorithms. The general intuition of Community Detection is to find a set of sub-graphs that maximises the ratio of edges within the sub-graphs versus edges between sub-graphs. Depending on the precise definition, this may be a difficult (NP-complete) problem, and so various algorithms rather use approximate (heuristic or greedy) approaches.

Five popular Community Detection algorithms are described here and should be a good starting point for your work.


Does NP-Complete imply non-satisfiability?

You're confusing languages and instances of them. A 3SAT formula could be either satisfiable or unsatisfiable. The 3SAT problem is to decide whether a given 3SAT formula is satisfiable. The 3SAT language is the set of all encodings of satisfiable 3SAT formulas. Only the 3SAT language is NP-complete. NP-completeness is a property of languages, not of their instances. If every 3SAT formula were satisfiable (or every one were unsatisfiable) then 3SAT (the language) would be very easy.


Are there existing extensions to behavior trees that fascilitate node communication?

The most mathematical paper I have seen on Behavior Trees is How Behavior Trees Modularize Hybrid Control Systems and Generalize Sequential Behavior Compositions, the Subsumption Architecture and Decision Trees. It is the only paper I have seen that defines Behavior Trees as a tuple e.g.

  A BT is a three-tuple $T_i = \{f_i, r_i, \Delta t\}$

Since Behavior Trees are related to Finite State Machines (FSMs), they mention Petri Nets which are also related to FSMs. They're a message passing / concurrency system, but weren't mentioned really in relation to message passing on Behavior Trees. Maybe it would provide some inspiration since they are highly developed message passing formalisms.

Other than that, there may be some private work done on message passing in complex Behavior Trees such as in game companies, but there doesn't seem to be any public resources on it. Maybe it is an artifact of the way behavior trees are developed, i.e. it seems to be done through node-based graphic interfaces, so less source-code-centric:

Probably best to just come up with your own system it seems. Maybe even try asking at the gamedev.se, they might have some insight. Hope that helps.


The Cook-Levin theorem demonstrates a reduction from SUBSET-SUM to SAT.
If you wanted a reduction from SAT to SUBSET-SUM, then yes, such a reduction exists; SUBSET-SUM is NP-complete, and thus the existence of such a reduction follows from the definition of NP-completeness.  You should be able to take any standard proof of NP-completeness for SUBSET-SUM and chain the reductions together to get the desired reduction.


JIT, AOT, Interpretation: What are differences between them?

The key distinction between interpreters and compilers (AOT or JIT) is this:

Interpreter: takes a source program $P$, and runs $P$, that means affecting the world through running $P$.
Compiler: takes a source program $P$, produces a new program $P_{asm}$. When we run $P_{asm}$, it has the same (hopefully) effect on the world as $P$.

In a picture:

The advantage of compilers is that generated code is faster, because a lot of work has to be done only once (e.g. lexing, parsing, type-checking, optimisation), at compile-time, so is out of the way at runtime. And the results of this work are shared in every execution. The interpreter has to redo this work every time.

A problem of AOT compilers is that they often don't have enough information to perform aggressive optimisation. This information is only available at run-time.

A JIT compiler seeks to do better, more aggressive optimisation by executing only at run-time. However, a full compilation cycle is expensive (time-consuming), so shouldn't be carried out at run-time. How can we deal with this conundrum?

The key insight is that program execution time tends to follow the Pareto Principle: the great majority of a program’s execution time is (usually) spent running in a tiny fragment of the code. Such code is referred to as hot. Pareto’s principle tells us that (typically) a program contains some hot code. Think: innermost loops. With the information available at run-time, we can aggressively optimise such hot code, and get a massive speed-up. The rest is interpreted. Sluggishness of interpretation doesn’t matter, because it’s only a fraction of program execution time.

There is just one problem ... how do we find hot code? Remember, at compile time, the optimiser couldn’t work it out (reliably). How can we do better at run-time?
Answer: Let’s use counters!
We instrument the interpreter with counters, that increment every time a method is called, or every time we go round a loop.
Whenever these counters reach a threshold, we assume that the associated code is hot. We compile that hot code, optimise it aggressively using information available at runtime. The jump to the compiled code, and execute it to completion. When the compiled code terminates, we go back to interpretation. In a picture:

Note that the description above is a simplification, the details are more complicated.

Note also that there is no need for the first part of a JIT compiler to be interpreted. In principle, and AOT can emit code that is effectively a JIT-compiler, and the job of the interpreter (evaluation and profiling) is carried out by  ahead-of-time compiled machine code.


Correct name for a recursive descent parser that uses loops to handle left recursion?

It is just an LL(1) parser implemented with recursive descent.

Starts with:

AdditionExpression  ::=
    MultiplicationExpression
        | AdditionExpression '+' MultiplicationExpression
        | AdditionExpression '-' MultiplicationExpression

apply left-recursion removal to get an LL(1) grammar:

AdditionExpression  ::=
    MultiplicationExpression AdditionExpressionTail

AdditionExpressionTail ::=
        | '+' MultiplicationExpression AdditionExpressionTail
        | '-' MultiplicationExpression AdditionExpressionTail

write the corresponding functions:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    parse_AdditionExpressionTail()
}

function parse_AdditionExpressionTail() {
    if (has_token()) {
        get_token()
        if (current_token == PLUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else if (current_token == MINUS) {
            parse_MultiplicationExpression()
            parse_AdditionExpressionTail()
        } else {
            unget_token()
        }
    }
}

remove tail recursion:

function parse_AdditionExpressionTail() {
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

inline:

function parse_AdditionExpression() {
    parse_MultiplicationExpression()
    while (has_token()) {
        get_token()
        if (current_token == PLUS)
            parse_MultiplicationExpression()
        else if (current_token == MINUS)
            parse_MultiplicationExpression()
        else {
            unget_token()
            return
        }
    }
}

and you have just to add the semantic processing to get your function.


Your problem is a special case of the following: given a convex polyhedron defined by a set of linear inequalities, compute its volume.  I believe that problem has been studied in the literature.

For instance, for related work on computing the volume of convex polyhedra/polytopes, see the following:

Algorithm for finding the volume of a convex polytope
Computing the Volume of a Convex Polytope Using Interval Arithmetic
Polytope volume computation

There is probably lots more work out there that might be relevant, but maybe this gives you a start.  You might start by reading that work to see if there are any techniques you can adapt; and by doing a literature review with the above as an entry point into the literature.


As you have stated, there are two very clear requirements for a problem $X$ to be $\mathbf{NP}$-complete:

$X \in \mathbf{NP}$.
$X$ is $\mathbf{NP}$-hard. That is, for every $Y \in \mathbf{NP}$, $Y$ is (poly-time many-one) reducible to $X$.

  Do we also need to prove that problem $X$ can be reduced to at least one $\mathbf{NP}$ problem?

No, as this is not one of the above requirements. However, if you are able to do so, you've proved that $X \in \mathbf{NP}$ (i.e., requirement no. 1): Suppose $X$ is reducible to $Y \in \mathbf{NP}$. Then verifying $x \in X$ can be done in poly-time by reducing $x$ to an instance $y$ of $Y$ and then verifying $y \in Y$.

  As problem $X$ is $\mathbf{NP}$, are we not supposed to prove that this $\mathbf{NP}$ problem can be reduced to other $\mathbf{NP}$-complete problems?

There is no need to. If you know $Y$ is $\mathbf{NP}$-complete and you show $X \in \mathbf{NP}$, then necessarily $X$ is reducible to $Y$. There is no need for you to do "extra" work.

  Why does this reduction have to be only one way to prove a problem is $\mathbf{NP}$-complete?

I am afraid I am not quite sure which reduction you are referring to, but if you are talking about reducing $X$ to $Y$, then the answer is simply: That is what the definition of $\mathbf{NP}$-completeness requires you to do.


Uncertainty whether $\{a^i b^j c^k \mid i+j \le k\}$ is context-free or not

Hint. $k = i + j + ?$, so the language is $a^ib^jc^?c^jc^i$.


Showing semidecidability without using diagonalization

Your question is a bit hard to answer, since "diagonalization" is not a formal concept (but see below). For example, does the following argument count as diagonalization? Consider the following function: $f(n)$ is the first string not generated by the first $2^n$ Turing machines. If the halting problem is decidable, then $f(n)$ is computable, and so its Kolmogorov complexity is $O(\log n)$. However, by construction, its Kolmogorov complexity is $\Omega(n)$, and we reach contradiction for large enough $n$.
One thing which is common to this proof and the usual one is the use of proof by contradiction. What happens if we disallow proof by contradiction? Can we prove that the halting problem is undecidable in constructive mathematics? I don't know the answer, but if it is negative, then this explains why proof by contradiction is necessary.
Another relevant piece of information is relativization. The halting problem is undecidable even relative to an oracle. Therefore, there should be an undecidability proof which uses only relativizing techniques. While this does not imply that any proof uses only relativizing techniques, perhaps it means that the "best" proofs should use such techniques. The advantage of this point of view is that it gives a slightly less informal definition of diagonalization, namely, any technique that relativizes.
Finally, let me mention that Kozen formalized the concept of diagonalization in his paper Indexings of subrecursive classes, and showed that every separation of complexity classes (subclasses of computable functions) can be proved by his notion of diagonalization. In his setting (which doesn't include undecidability proofs), diagonalization is the most general type of proof, which can prove all true statements. This means that any proof at all (of such statements) can be cast as a proof by diagonalization.


Proving equivalence of two substitutions by induction

First, let us show that the two assumptions are necessary. Here is an example showing what goes wrong when $x = y$. Take $t = x$, $u = 1$, $v = 2$. We have
$$
x\{x := 1\}\{x := 2\} = 1\{x := 2\} = 1,
$$
whereas
$$
x\{x := 2\}\{x := 1\{x := 2\}\} =
2\{x := 1\} = 2.
$$
Next, here is an example showing what goes wrong when $x$ is not free in $v$. Take $t = y$, $x = 1$, $y = x$. We have
$$
y \{x := 1\}\{y := x\} = y\{y := x\} = x,
$$
whereas
$$
y \{y := x\}\{x := 1\{y := x\}\} =
x\{x := 1\} = 1.
$$
Now let's do the base case more carefully. The term $t$ is just a variable. We have to consider three possibilities: $t=x$, $t=y$, $t \neq x,y$.
If $t=x$ then $t\{x := u\} = u$, and so the left-hand side is $u\{y := v\} = u\{y := v\}$. On the other hand, $t\{y := v\} = x$ (since $x \neq y$), and so the right-hand side is $x\{x := u\{y := v\}\} = u \{y := v\}$.
If $t=y$ then $t\{x := u\} = y$ (since $y \neq x$), and so the left-hand side is $y\{y := v\} = v$. On the other hand, $t\{y := v\} = v$, and so the right-hand side is $v\{ x:= u\{y := v\} \} = v$, since $x$ doesn't appear freely in $v$.
Finally, if $t \neq x,y$ then both sides are just equal to $t$, since the substitutions have no effect.
Next, the rest of the proof. The proof for function application is essentially as you wrote it. Let us denote the left-hand side by $L(t)$ and the right-hand side by $R(t)$. If $t = t_1t_2$ then
$$
L(t) = L(t_1) L(t_2) \stackrel{(\ast)}= R(t_1) R(t_2) = R(t),
$$
where $(\ast)$ is due to the induction hypothesis.
Finally, we need to handle abstraction. Let $t = \lambda m.s$. Applying $\alpha$-conversion, we can assume without loss of generality that $m \neq x,y$. This implies that
$$
L(t) = \lambda m.L(s) = \lambda m.R(s) = R(t).
$$
To see why $\alpha$-conversion is necessary, try doing the proof when $m=x$ or $m=y$. The case $m=x$ works out fine, but you will encounter a problem when $m=y$.


A 1-in-3 clause consists of three literals. It is satisfied if exactly one of these literals is true. For example, if the three literals are $\bar{x}_1,x_2,x_3$, then the three truth assignments (for $x_1,x_2,x_3$) which satisfy the clause are $(F,F,F)$, $(T,T,F)$, $(T,F,T)$.


Best approach to resource allocation problem

Let us first show that your proposed greedy algorithm for the second restriction is not optimal.
For this, consider a scenario with $e_1 = 1, e_2 = 3$ and $e_3 = 4$ as well as $d_1 = 1, d_2 = 2$ and $d_3 = 3$.
The greedy algorithm would assign $d_1$ and $d_2$ to the first city and $d_3$ to the second one, leading to only one city being retaken.
However, if we assign $d_2$ to the first city and $d_1$ and $d_3$ to the second one we could retake both of them and hence, the greedy algorithm is not optimal.
As for algorithmic approaches, note that your problem given the second restriction (let's denote it by $L$) is $\mathsf{NP}$-complete which can be shown by reducing $\mathrm{Partition}$ to $L$:
For a $\mathrm{Partition}$ instance given by a multiset $S$ of integers define an $L$-instance where the multiset of the $d_i$s is given by $S$, i.e. for every element of $S$ we create a team of the same size.
Denote by $X$ the sum of the elements of $S$ and set $e_1 = e_2 = X/2 - 1$ as well as $e_i = X + 1$ for all $i > 2$.
Now note that we can retake at most $2$ cities (as we don't have enough forces to retake any city which is held by at least $X$ soldiers) and we can only retake both of them if we can split our forces exactly in half, sending $X/2$ soldiers to the first and second city, respectively.
It follows that $S$ is a yes-instance of $\mathrm{Partition}$ if and only if we can retake 2 cities in our constructed $L$-instance (I left out some technical details but this reduction should work out just fine).
Assuming $\mathsf{P} \neq \mathsf{NP}$ this result implies that $L$ has no (deterministic) polynomial time algorithm. For some further lower bounds, see the other answer.


Construct a digraph given its in-degree and out-degree distribution

The following remarks are taken from a paper by Berger. I assume that you don't allow parallel loops.

The idea is to frame the problem on bipartite graphs. One side of the bipartition consists of the "inside" of vertices, the other of the "outside". Each vertex $v$ has two copies $v_-,v_+$, and we want $d(v_-)$ to be the indegree of $v$, $d(v_+)$ to be the outdegree of $v$. The existence of such a bipartite graph is the the focus of the Gale–Ryser theorem, which gives an efficient algorithm.

A similar criterion for the case in which loops are forbidden also exists, see Berger's paper quoted above.


How to calculate the minimum number of groups, by grouping groups with capacity together?

The problem is NP-complete, because in the special case that all cars have the same capacity, it is just the bin-packing problem.

If car A has a higher capacity than car B, and you get an optimal solution (smallest number of cars) containing B but not A, then you can swap cars A and B, you won't need more cars, and because A has more empty capacity, you may fit the passengers from another car. So which cars you use in an optimal solution is obvious. You use cars sorted by capacity in decending order. So no matter what the numbers of passengers are, you would use the car with 7 seats, then the car with 3 seats, then the one with 2 seats. I assume you have groups of passengers you want to keep together, otherwise it is trivial.

You should be able to adapt any bin-packing algorithm to your situation. I can't see graphs being useful in any way.


Complexity of finding the shortest simple even s-t-path

Its in P for undirected graphs and NP hard for directed once:
http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/pdf


Fixed-length decision-tree-like feature selection to minimize average search performance

The solution I found (I asked the question) is to use superimposed coding, and more specifically, a variant of Zatocoding which has better support for hierarchical descriptors.

The method I used comes from 'An Efficient Design for Chemical Structure Searching. I. The Screens', Alfred Feldman and Louis Hodes, J. Chem. Inf. Comput. Sci., 1975, 15 (3), pp 147–152.

The non-hierarchical solution is to look at the information density. Each descriptor will be assigned $s_i=-log_2(f_i)$ bits where $f_i$ is the frequency in the data set ($0<$f_i<=1.0). Compute the total number of bits $D$ (the size of the decision tree) using $D=\sum(s_i f_i)/M_c$ where $M_c$ is the Mooers compression factor 0.69 (from $log_e 2$). Once you have determined the total number of bits to use, select $s_i$ bits randomly for each descriptor for bit assignment.

The hierarchical solution from Feldman and Hodes replaces $s_i=-log_2(f_i)$ for descriptors which are a subset of other descriptors. In that case, use $s_i=-log_2(f_i/g_i)$ where $g_i$ is the frequency of the least frequent parent. In addition, when doing the bit assignment do not select bits which are also used by the parent's bit assignment.

There's still a problem of how to come up with the right descriptors, but that will be domain specific.


Using Rice's theorem to prove undecidability of $E_{TM}$

You have to be careful when you talk about accepting empty strings. Using the language from the linked question, what you are suggesting would yield $L(M_x)$ = $\{\epsilon\}$ instead of $L(M_x)$ = $\emptyset$.
You can use the same construction for machine $M_x$, but just change the the non-trivial property to "whether this machine accepts on no inputs". It's clearly a non-trivial property since it's not empty (there are machines with empty language), and it's not the set of all Turing Machines (since not all Turing Machines have empty language).


How to model equality in Integer Linear Programming

Use Cast to boolean, for integer linear programming, setting $x=a-b$ and $y=v$.  This only works if you have a constant upper bound on $|a-b|$.  Otherwise, I don't know how to express it in an ILP.

See also Express boolean logic operations in zero-one integer linear programming (ILP), Boolean variable true iff equation is satisfied in ILP, Boolean variable that captures whether an inequality holds.


Derandomization of vertex cover algorithm

First, let us repeat the analysis of the algorithm.

Fix some optimal vertex cover OPT, with cost $O$.

Let $S$ be the cost of the vertex cover produced by the algorithm.

Let $A_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex belonging to OPT", and let $A = \sum_e A_e$.

Let $B_e$ be the indicator for the event "when edge $e$ was considered, the algorithm added a vertex not belonging to OPT", and let $B = \sum_e B_e$.

Thus $S = A+B$ and $A \leq O$.

The idea of the analysis is that $\Pr[B_e] \leq \Pr[A_e]$. To see this, consider what happens when vertex $e$ is considered. If $e$ is already covered by vertices already chosen, then $A_e = B_e = 0$. If both endpoints of $e$ belong to OPT, then $A_e = 1$ and $B_e = 0$. Otherwise, $\Pr[A_e] = \Pr[B_e] = 1/2$. In all cases, $\Pr[B_e] \leq \Pr[A_e]$.

Since $\Pr[B_e] \leq \Pr[A_e]$, we have $\mathbb{E}[B] \leq \mathbb{E}[A]$. Therefore
$$
\mathbb{E}[S] = \mathbb{E}[A+B] \leq 2\mathbb{E}[A] \leq 2O.
$$

How would we apply the method of conditional expectations? Here are two options:

Given the choice of which endpoint is taken, compute the expected value of $S$. If $z \in \{x,y\}$ was chosen, then we remove all edges adjacent to $z$, and then run the algorithm as usual. This reduces the problem to computing $\mathbb{E}[S]$, which is the expected number of edges which are not covered when their time comes. It's not so clear how to compute $\mathbb{E}[S]$.
The same, but instead of computed $\mathbb{E}[S]$ exactly, compute an approximation which is good enough to obtain a 2-approximation. Let $O_z$ be the optimum solution after removing all edges adjacent to $z$. Then
$$
\mathbb{E}[S \mid x] \leq 1 + 2O_x, \quad
\mathbb{E}[S \mid y] \leq 1 + 2O_y.
$$
If $x$ belongs to OPT then $O_x = O-1$, and otherwise $O_x \leq O$. Thus the average of both bounds is at most
$$
\frac{1+2(O-1)+1+2O}{2} = 2O,
$$
since at least one of $x,y$ belongs to OPT. Therefore, if we choose the vertex that minimizes $O_x,O_y$, then the resulting algorithm will produce a 2-approximation. Unfortunately, it's not clear how to compute $O_x,O_y$ (indeed, this ought to be hard).

In summary, it's not so clear how to apply the method of conditional expectations.


Different boolean degrees polynomially related-2?

You're asking several questions. Here are answers for some of them.

The OR function has degree $n$, but it can be approximated by the function $(x_1+\cdots+x_n)/n$. This shows that $d_{1,\text{OR},1-1/n} = 1$.
If you have a polynomial $P$ representing $f$ in the sense that $P(x) = 0$ whenever $f(x) = 0$ and $|P(x)-1|<1$ whenever $f(x) = 1$, then for small enough $\epsilon > 0$, the function $P-\epsilon$ sign-represents $f$.
The correct tradeoff between (say) $d_{0,f,\epsilon}$ and $d_{0,f,\delta}$ for different $\epsilon,\delta$ can be studied using approximation theory, i.e. Chebyshev polynomials and the related Markov and Bernstein theorems and their ilk. The functions converting a $\delta$-approximation to an $\epsilon$-approximation can be constructed explicitly using Chebyshev polynomials, and lower bounds on their degrees can be obtained using Markov–Bernstein theorems. This is similar to the way that the tight bound $\Theta(\sqrt{n})$ for the approximate degree of the OR function $d_{\text{OR},\epsilon}$ is proved.


Is there a data-structure for semilattices similar to a tree data-structure?

This blogpost on lattice theory has a useful reference section, which contains among others "Lattice Theory with Applications" by Vijay K. Garg.
Chapter 2 "Representing Posets" describes some data structures for representing posets, and discusses how to compute join(x,y) using such a data structure.

The first two data structures discussed are the adjacency list representation of the transitive reduction graph (=Hasse diagram/cover relation) and transitive closure graph (=poset relation). A remark about the advantages of using a topological sort to label the nodes precedes that discussion. Note that the labels of topological sort would be good enough as "a distance measure to the root", which was one part of the data-structure for a tree in the question.

The other discussed representations are "Skeletal Representation", "Matrix Representation" and "Dimension Based Representation". The "Skeletal Representation" is interesting and useful, but based on a (=any) chain decomposition of the poset. The "Matrix Representation" might seem trivial, but its probably be the best representation for most practical problems. The "Dimension Based Representation" represents the poset as the subset of the Cartesian product of linear orders, but computing the minimal representation of this kind is NP-hard.

In conclusion, the most treelike representation of these is the adjacency list representation of the transitive reduction together with a labeling of the nodes by a topological sort (instead of "a distance measure to the root"). This is actually one of the representations used by Sage (the other is the "Matrix Representation").


What is the combinatorial reasoning for the $n$ factor in $n \times n! / (b!(n - b)!)$?

Part of the state of the world is the location of the agent. Since there are $n$ cells, this variable has $n$ possible values, producing the factor of $n$.
Actually, there may be a mistake in Russell and Norvig's formula. After we have chosen the location of the agent, there are only $n - 1$ possible locations for the $b$ boxes, giving us $(n - 1)! / (b! (n - b - 1)!)$ choices for where to put all of the boxes. So, the number of states is $n \times (n - 1)!/(b!(n - b - 1)!)$, which simplifies to $n! / (b! (n - b - 1)!)$. (This is the trinomial coefficient $n \choose 1, b$.)


Let $F$ be the set of all functions $f(n)$ such that $\sum_n f(n)$ diverges. Then $F$ is bounded from below by $f(n) = 1/n^2$ (for example), but there is no infimum: for every divergent sequence, you can find a sequence which diverges more slowly. This is a classical result of Hausdorff.

Similarly, if $F$ is the set of all functions $f(n)$ such that $\sum_n 1/f(n)$ converges, then $F$ is bounded from above by $f(n) = n$, but there is no supremum since for every convergent sequence you can find a convergent sequence which grows much faster.

Edit: This paper (among others) provides a proof of these claims.


Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

The fact that the total number of candies is at maximum 12 is an important constraint.

Let the candies and start and end points (total <=14 points) be key points in the grid. Now use BFS from each of the key points to find the distances between the key points, and form a new graph with only the key points. Since the number of nodes in the new graph is so small, we can use Travelling Salesman on this new graph to solve the problem.

(Note: You will need to slightly modify Travelling Salesman to work for this specific problem.)


NFA for binary words that do not end in 10

Every DFA is also, in particular, an NFA. Therefore if you have constructed a DFA for some language, then you have a fortiori constructed an NFA for it.


Statement of the Goldwasser-Sipser Set Low Bound Protocol

To succeed in distinguishing the case of $|S|\ge K$ from $|S|\le\frac{K}{2}$, you just need a constant gap (independent of $|S|$) in the acceptance probability in both cases. If you managed to achieve such a gap, then applying Chernoff to multiple executions of the protocol would achieve high success probability.
Observe that the interesting case is $k\le m$, since otherwise $K\ge 2^{k-2}\ge2^{m-2}$, and the verifier can convince himself that $|S|\ge K$ simply by sampling strings in $\{0,1\}^m$ uniformly at random and checking whether they belong to $S$ (in this case $|S|\ge K$ implies that the probability of falling in $S$ is at least $1/4$, so Chernoff with a polynomial number of samples yields the desired result). From now on assume $m\ge k$, and thus the hash functions are $h_{a,b}:GF(2^m)\rightarrow GF(2^k)$ given by $h_{a,b}=(ax+b)_{1...k}$, where $x_{1...k}$ in the truncation of a string obtained by taking the first $k$ bits.
For uniformly distributed $a,b\in GF(2^m)$, and every $x\in GF(2^m)$, $ax+b$ is uniformly distributed. This means that $\forall x\in GF(2^m): \Pr\limits_{\substack{a,b\in GF(2^m)\\y\in GF(2^k)}}\left[(ax+b)_{1...k}=y\right]=\frac{1}{2^k}$. We conclude that $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\le \frac{|S|}{2^k}$. On the other hand, we can lower bound the same probability by:
$$
\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge\\
\sum\limits_{x\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y\right]-\sum\limits_{x\neq x'\in S}\Pr\limits_{a,b,y}\left[h_{a,b}(x)=y \land h_{a,b}(x')=y\right]=\\\frac{|S|}{2^k}-\frac{}{}\binom{|S|}{2}\frac{1}{2^{2k}}\ge \frac{|S|}{2^k}\left(1-\frac{|S|}{2^{k+1}}\right).
$$
So far there were no restrictions on the size of $S$. Now, if $|S|\le K\le 2^{k-1}$ then $\frac{|S|}{2^k}\le\frac{1}{2}$, and we obtain $\Pr\limits_{a,b,y}[\exists x\in S: h_{a,b}(x)=y]\ge \frac{3}{4}\frac{|S|}{2^k}$. We conclude that if $|S|=K$ then the probability of acceptance is at least $\frac{3}{4}\frac{K}{2^k}$ (the bound trivially holds for larger $|S|$, just by taking a subset of size $K$). If on the other hand $|S|\le K/2$ then the acceptance probability is at most $\frac{1}{2}\frac{K}{2^K}$ and we have our constant gap $\ge\frac{1}{4}\frac{K}{2^k}$, and Chernoff completes the proof.


Your problem appears to be very close to the minimum quadratic assignment problem, see for example a paper by Hassin, Levin and Sviridenko; your problem is close to the metric variant (since $D$ is a metric). When $D_{i,j} = |i-j|$ we get the NP-hard problem minimum linear assignment, whose best known approximation ratio is $\tilde{O}(\sqrt{\log n})$.


Jon Hall's coding theory notes, available online here are quite good. See Chapter 5.
In addition, see Blahut's text Algebraic Codes for Data Transmission where more focus on decoding algorithms is present.


What should be the minimum value when the two threads are executed concurrently

Here's a tricky interleaving. R1,R2 denote the independent logical registers used by the threads, while count is the shared variable in memory.

Thread 1 starts its first iteration, performing only a read. count=0, R1=0, R2=?
Thread 2 performs 99 iterations. count=99, R1=0, R2=99
Thread 1 completes its first iteration (increment and write). count=1, R1=1, R2=99
Thread 2 starts iteration #100, performing only a read. count=1, R1=1, R2=1
Thread 1 performs the other 99 iterations. count=100, R1=100, R2=1
Thread 2 completes its iteration #100 (increment and write). count=2, R1=100, R2=2
Both threads now exit, having completed their execution.

So, the sequence is something like

rX = read by thread X
iX = local increment by thread X
wX = write by thread X

r1,
r2,i2,w2,r2,i2,w2,...,r2,i2,w2,  (99 full iterations)
i1,w1,
r2,
r1,i1,w1,r1,i1,w1,...,r1,i1,w1,  (99 full iterations)
i2,w2


Can we always reduce the weights of a weighted graph to rationals and preserve equality relationships?

Identify $W$ with the set of all weights. Let $B$ be a basis of $W$ over the rationals. That is, you can write every weight in $w$ as a linear combination of elements of $B$ with rational coefficients. You can identify the weights with vectors $\vec{w}$ of length $|B|$. Each linear dependency that you want to avoid can be thus encoded as an inequality
$$
\sum_i \alpha_i b_i \neq 0,
$$
where the coefficients $\alpha_i$ are not all zero. We can moreover assume that the $\alpha_i$ are integers (by taking a common denominator).

Let $M$ be an integer larger than all $|\alpha_i|$ appearing in an inequality you are interested in. If we replace $b_i$ with $M^i$ then all the requisite inequalities will be satisfied, while all equalities will also be preserved.


Decomposing the n-cube into vertex-disjoint paths

I found the following result due to Gregor and Dvorak. They show that if the sets $S$ and $T$ are balanced (in the sense that they contain the same amount of vertices from both bi-partitions of the $n$-cube), then such paths exists whenever $2k-e < n$, where $e$ is the number of pairs $(s_i, t_i)$ that form edges in $\mathcal{Q}_n$. The paper can be found here: http://www.sciencedirect.com/science/article/pii/S0020019008002238

I can construct an example when $k = 2$, $e=0$ and $n=3$, so this result isn't completely tight, however.


How to find the largest power of two divisor of a given integer?

You just need to count the number of $0$ at the end of the binary encoding of $x$.


$B*\frac{W}{r}$ is a constant, so adding it to your objective function has no effect on the solution. The problem is NP-complete, regardless of the values of $B$ and $r$.


Can literals in functional languages be thought of as functions from the empty type?

Let's start in a total language like Agda.  Then, as gallais states, this only makes sense if by "empty type" you mean the unit type, i.e. the 0-ary tuple, which has exactly one value. The empty type can be thought of as a 0-case sum type, and has no values at all. In Agda, you can easily prove that Unit -> A is isomorphic to A. In that sense, you can consider them the same, though they still aren't literally the same. I can't, for example, do a case analysis on a Unit -> Bool nor can I apply True : Bool to anything as a function.

The story for Haskell is quite different. () -> A and A are semantically non-isomorphic types. In particular, () -> () has four values, while () has only 2. The four observationally distinct values are undefined, \_ -> undefined, \x -> x, \_ -> (). So () isn't actually a unit type, in the sense that there is exactly one function into (). (In Agda, on the other hand, we can prove that if x : Unit and y : Unit, then they are equal [definitionally so if we define Unit with the record syntax as opposed to the data syntax]. That means, Unit has only one value. Further, we can prove that Unit and A -> Unit are isomorphic for any A.)

In fact, an "empty" type like Void defined as data Void is closer to being a unit type in this sense. Void has only one value, but Void -> Void still has two. In fact, every function type A -> B, has at least two observationally distinct values, namely undefined and \_ -> undefined. Therefore, Haskell has no true unit or void type.

A lot of this is due to Haskell being a non-strict language and is exasperated by the existence of seq (and its equivalents). For example, the distinction between undefined and \_ -> undefined can only be seen with seq. If we eliminated seq and its equivalents from Haskell, then Void would serve as a unit type, though, ironically, still not as an empty type.

Usually, when people talk about such things in Haskell, they are tacitly pretending that Haskell is a better behaved language than it is. That is, they are assuming bottoms don't exist for their purposes, i.e. that you're working in a total language like Agda. For the purposes of designing your code, this is usually adequate; it's not common that we care about or expect bottoms. These distinctions can become important if we're doing something like circular programming, or if safety guarantees of our program rely on these properties, e.g. a function can never be called if it has an empty type as its domain.


Proving that a language does not belong to a language class by using more specific instances of that language

Yes. The formal way to name this trick is the use of closure properties. In your specific case the families (regular, context-free) are closed inder intersection with a regular language: if $K$ is regular (context-free) then so is $K\cap R$, where $R$ is regular.

In your examples $L_2 = L \cap 0^*1^*$ and $L_{p2} = L_p \cap 0^*$.

So, if $L_{p2}$ isn't context-free then neither is $L_p$. Also if $L_2$ isn't regular then neither is $L$.

Regarding the first part of you question this will not help: $L_2$ may be context-free while $L$ isn't. (Not is this example, where they both are context-free: use pushing and popping but in a more general way, think how to represent negative numbers.) On the other hand, when you are not able to solve the general case, it might be helpful to develop intuition on the special cases.


Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂)

Take $r = (r_1 + r_2)^*$. We have to prove
$$(r_1 + r_2)^* = r_1(r_1 + r_2)^* + r_2$$

First note that both $(r_1 + r_2)^*$ and $r_1(r_1 + r_2)^* + r_2$ contain $\epsilon$ since we are given that $\epsilon \in L(r_1)$, so we will consider a nonempty string in our proof.

Let's first show that $(r_1 + r_2)^*\subseteq r_1(r_1 + r_2)^* + r_2$. But it is trivial since we know that $\epsilon \in L(r_1)$ and so
$$r_1(r_1 + r_2)^* + r_2 = (r_1 + r_2)^* + r_1'(r_1 + r_2)^* + r_2, \text { where } r_1 = r_1' + \epsilon$$

Now we have to show that $r_1(r_1 + r_2)^* + r_2 \subseteq (r_1 + r_2)^*$. Assume a nonempty string $s \in r_1(r_1 + r_2)^* + r_2$. Then either $s \in r_2$ or $s \in r_1(r_1+r_2)^m$ for some nonnegative integer $m$. In the first case since $r_2 \subseteq (r_1+r_2)^*$, we are done, so assume $s \in r_1(r_1+r_2)^m$. But we know that $(r_1+r_2)^{m+1} \subseteq (r_1+r_2)^*$. Thus
$$(r_1+r_2)^{m+1} = (r_1+r_2)(r_1+r_2)^m = r_1(r_1+r_2)^m + r_2(r_1+r_2)^m$$
meaning $r_1(r_1+r_2)^m \subseteq (r_1+r_2)^*$.


Why does DFS only yield tree and back edges on undirected, connected graphs?

A depth first search on a directed graph can yield 4 types of edges; tree, forward, back and cross edges. As we are looking at undirected graphs, it should be obvious that forward and back edges are the same thing, so the only things left to deal with are cross edges.

A cross edge in a graph is an edge that goes from a vertex $v$ to another vertex $u$ such that $u$ is neither an ancestor nor descendant of $v$. So what you need to argue is that in an undirected graph, there's no way you can get a cross edge. It might help to think of why the can occur in directed graphs, and why you can't have this case in undirected graphs.


Looking for clarity on step in fractional knapsack problem proof

All appearances of $q_i$ on the RHS are errors -- they should be replaced with $o_i$. I imagine the author was thinking of "initialising" $Q$ to be equal to $O$, and then updating its elements in-place.
Another minor issue I have is with the line "After this procedure is done, the total value of the solution $Q$ is equal to the total value of $O$ (make sure youunderstand why!)". This is true, but as this is the key part of an introductory proof, I think it would have been better to break it into its two parts:

For any $k > j$, moving positive weight from $o_k$ to $o_j$ results in a solution with value $\ge$ the original solution.
The original solution $O$ was assumed optimal, so the $\ge$ becomes a $=$.


Why is finding the closest pair of points by brute force search O(n^2)?

It's not clear what you think $O(n^2)$ means.  $O(n^2)$ means that there is a constant $c$ so that, when $n$ is large enough, your algorithm takes no more than $cn^2$ time.

As you observed, the algorithm takes  $(n-1)+(n-2) + \ldots + 1 $ time.  This is equal to $\frac12 (n^2-n)$.  This quantity is less than $2n^2$ whenever $n$ is larger than $10$.  So it is indeed $O(n^2)$.

Another way to understand $O(n^2)$ is: if $n$ doubles, the algorithm will take about four times as long.   For $n=10$, your algorithm takes $9+8+\ldots + 1 = 45$ steps.  When $n=20$, it takes $ 19+18+\ldots + 1 = 190$ steps.  That is indeed pretty close to $4\cdot 45=180$ steps.  Similarly when $n=40$ it takes $780$ steps, which is again pretty close to $4\cdot 190 = 760$.


$|x|$ here means the length of the string $x$ over an alphabet $\Sigma$. Note that $x$ does not need to be a natural number.

So, $|2^{100}|$ is $100$ (but do remember that you MUST understand that you are encoding the natural number $2^{100}$ into string over finite alphabet) if we want to encode a natural number in binary. Therefore, $T(|2^{100}|) = T(100) = \log_2100$.

It would be type-safer to write $|\lfloor{2^{100}}\rfloor|$


Proof for time complexity of Insertion (k-proximate) Sort equals O(nk)

Yes if you sort the array in ascending order you are right it should be less than $2k$ elements in $A[0],...,A[i-1]$ are greater than $A[i]$. A simple array were the statement w is wrong  ($k = 1$):
$$[1,2,3,4]$$
However is you sort in descending order it's the other way around.
But you have a good point because this seems to imply that ascending is meant...

"indeed, if A[s] > A[t] but t − s ≥ 2k, there is no way to reverse the order of these two items"


Programming language semantics prototyping tool

Although there are frameworks created specifically for the purpose of prototyping programming languages (including their semantics, type systems, evaluation, as well as checking properties about them), the best choice depends on your particular case and specific needs.

Having that said, there are multiple (perhaps not so distinct) alternatives you might take (which includie the ones you've already mentioned):

using a specific language/framework designed for creating and prototyping new languages: as an example, Redex [1], a domain-specific language embedded in Racket for specifying and checking (operational) semantics of programming languages, which, given a definition of a language, provides easy handling of tasks such as typesetting (in Latex), inspecting traces of reduction, unit tests and random testing (e.g. for checking typing)
using general modelling languages that offer defining and performing certain analyses easily, as long as they can capture the specific language at hand to the needed extent; Alloy [2] is an example of such an approach: albeit pretty general and flexible, languages can be modelled as relations between states, while the support for model checking (e.g. evaluation within such language) comes for free after the semantics is expressed with a relation model (e.g. some ideas for modelling semantics of a language can be found in [3])
embedding the language to check its properties using a theorem prover; an example would defining the language as well as its semantics by embedding it in a proof system like Coq [4] (more details about this approach, as well as discussion and demonstration of the difference between deep and shallow embedding in Coq is given in [5])
using Ott (as already mentioned, with similar in spirit as Redex, but providing a new definition language rather than being embedded); Ott allows you to define the programming language in a convenient notation, and produce typesetting and definitions in a proof system (usually with deep embedding), where most of the checking (i.e. proof) needs to be performed manually
developing the language and its semantics, as well as appropriate checks (e.g. as tests) "from scratch" in a general-purpose programming language and translation into other systems if need be, for checking purposes (some languages, like Leon [6], include built-in verifiers, which allow automatically proving certain properties and make this approach similar to embedding in a proof system)

Note that there is the trade-off between how easy is to use the framework/tool (e.g. as easy as laying out the definition on paper or in Latex) and how powerful the mechanisms for checking the properties about the language are (e.g. embedding the language in a theorem prover can allow checking very elaborate properties).

[1] Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt, and Robert Bruce Findler. Run Your Research: On the Effectiveness of Lightweight Mechanization. POPL, 2012.

[2] Daniel Jackson. Alloy: a lightweight object modelling notation. TOSEM, 2002.

[3] Greg Dennis, Felix Chang, Daniel Jackson. Modular Verification of Code with SAT. ISSTA, 2006

[4] Coq formal proof management system

[5] Formal Reasoning About Programs. Adam Chlipala, 2016

[6] Leon automated system for verifying, repairing, and synthesizing functional Scala programs


How to model a set of categorical values in the input of a neural network

Yes, the "one boolean per set element" is the standard way of encoding such a set.  This is known as a "one-hot encoding".  Yes, there will be a lot of input neurons, but that's not necessarily a serious problem; current procedures for training neural networks are able to handle millions of nodes with no problems.

If you know that $T$ will contain at most $m$ elements, in principle there are alternative encodings (e.g., use $m \lg n$ wires, where you use $\lg n$ wires for each element of $T$ to encode which element of $S$ it is)... but in practice I do not expect them to perform well.

In that case I think a better approach is to try to build a feature vector that is shorter than $n$ dimensions.  Do you have some domain knowledge you can use to identify attributes of the elements?  For instance, you could have a feature that says "how many elements of $T$ are red wines?" and "how many elements of $T$ are white wines?" and "how many elements of $T$ are dessert wines?" and so on.  You'll have to use your domain knowledge about the task to identify what attributes might be relevant to the classification task.  In this way, the number of input wires can be made much smaller than $n$.


Can lists be defined in a special way so that they contain things of different type?

The short answer is that $\tau\ \text{list}$ is defined as a type constructor, along with rules for formation and elimination, and so we could similarly define a type constructor that allowed terms of different types to form a single "variably-typed list". However, lists cannot take different types in the definition given, simply because they are defined with respect to a single type. In either case, adding lists, or variably-typed lists, involves extending the simply-typed $\lambda$-calculus, as lists of any kind do not exist in the usual presentation.
If we have a slightly richer type system than the simply-typed $\lambda$-calculus, we can encode variably-typed lists using standard $\tau\ \text{list}$s.

If we have a form of subtyping, we can store terms of different types, as long as they share a supertype. However, when we project elements out of the list, we can no longer tell specifically what type they were to begin with (this may be familiar from object-oriented programming), so this is a little limited.
If we have dependent sum types (also called $\Sigma$-types) and a universe type $\mathcal U$ (i.e. a "type of types"), we can form the type $(\Sigma_{A : \mathcal U} A)\ \text{list}$, whose elements are pairs consisting of a type $A$ and a term of that type.

Finally, I'll just note that polymorphism doesn't help us if we want heterogeneous lists: it just allows us to manipulate homogeneous lists for different $\tau$ more effectively. Polymorphic types have to be uniform in some sense, which is why we need dependency here instead.

To answer a follow-up question: if we have two variably-sorted lists using the dependent type approach, we can concatenate and flatten lists just as with ordinary lists.

The $\mathrm{List}$ monad has an operation $\mathrm{join}$ (in the language of Haskell), so given a list of variably-typed lists, $$l = [[(A, a), (B, b)], [(C, c), (D, d)]] : (\Sigma_{X : \mathcal U} X)\ \text{list list}$$ we can perform $\mathrm{join}$ to get a new list: $$\mathrm{join}(l) = [(A, a), (B, b), (C, c), (D, d)] : (\Sigma_{X : \mathcal U} X)\ \text{list}$$
Similarly, $\tau\ \text{list}$ can be equipped with a concatenation operation $+\!+$, so given the two lists in the previous example, we can concatenate them for a similar result:
$$[(A, a), (B, b)]\ {+\!+}\ [(C, c), (D, d)] = [(A, a), (B, b), (C, c), (D, d)] : (\Sigma_{X : \mathcal U} X)\ \text{list}$$


Count numbers less than $x$ co-prime to $p$

There's a very fast method if p has few prime factors. Say p is a prime. Then the numbers co-prime with p are all numbers other than p, 2p, 3p, 4p etc. There are x-1 numbers less than x, and of those floor ((x-1) / p) are divisible by p, so exactly (x-1) - floor ((x-1) / p) are co-prime with p. For simplicity, let f(n) = floor ((x - 1) / n), then for a prime p the result is f (1) - f (p).

If p has two prime factors a, b, then we would start with f(1) - f(a) - f(b) - take all numbers, except those divisible by a, except those divisible by b. But here is a mistake: Numbers divisible by ab have been removed twice, so we add them back: f(1) - f(a) - f(b) + f(ab).

For three prime factors a, b, and c, we use the same scheme and start with f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc). Numbers divisible by abc have been removed three times, added back three times, and therefore need to be subtracted once, giving f(1) - f(a) - f(b) - f(c) + f(ab) + f(ac) + f(bc) - f(abc).

You can continue this. You'll have to figure out yourself what exactly to add or subtract. With k different prime factors, you have 2^k terms - but clearly with 10 different prime factors, and say x = 1,000,000, you have only 1024 different terms. Also, as soon as a product is greater than x, you can ignore it. For example, all prime factors ≥ x of p can be completely ignored. And all duplicate prime factors can be ignored.

Actually, the number of different prime factors grows very slowly, so this method is quite good unless x is small.

How many numbers less than a billion are co-prime with $10^{100}$? Prime factors of $10^{100}$ are 2 and 5, so the answer is 999,999,999 - 499,999,999 - 199,999,999 + 99,999,999 = 400 million.


I tried expanding my comment to a proper answer. It was easier for me to write down the automata and the whole transformation process rather than using some software to generate it, thus I hope my handwriting is legible enough ;) (elsewise let me know)

The resulting Regular Expression is $[[b^*ba^*b]^*\cup[b^*aa^*ab^*b]^*]^*$

So the language accepted by your NFA ought to be something of the form $L = \{((b^lba^hb)^*(b^iba^jab^kb)^*)^*|i,j,k,l,h\ge 0\}^*$ (I've given a quasi-final form of the language).

The opposite of this language is $\sim L = \mathtt{REG} - L$

PS: Fortunately, a kind sir named Hendrik Jan observed that my conversion omits the fact that 2 is also a starting point. The solution is still holds for starting point 1. Now that you got an idea about NFA to REG conversions, I'll leave the REG determined by starting point 2 to you. :)


What's the advantage of two pointers linked list implementation of Queue versus one pointer circular list

If you're not using a circular list, then you must have a pointer to head and tail to achieve $O(1)$ enqueue and dequeue. Furthermore, if it is not a circular list and not a doubly-linked list, then without a pointer to head, we can't enqueue!

Some picture might help a little too.

Single Linked List with only tail pointer:

There's no way to get back to the head to enqueue! We would have to remedy this with a pointer to the head.
Doubly Linked List with only tail pointer:

We can get back to the head, but at an $O(n)$ cost, we might as well just add another pointer to head for convenience.
Single Circular Linked List with only tail pointer:

We can get back to the head in $O(1)$! This is a good shortcut. In circular linked lists this node can sometimes implemented as a Sentinel Node which does not contain any information but works as a separator between the head and tail of the queue.

In terms of additional space, adding tail or head or both is almost negligible. The nodes will be taking up memory no matter what, it's just whether or not you use a variable to reference them. Using a circular linked list kind of acts like a head pointer if you think about it. tail.next would be a synonym for head, so it's not really saving space, nor is it really costing much space.


Can a semi-decidable problem be also decidable?

Yes, a recursively enumerable language may be either decidable or undecidable. To see this, you ust look at the definitions of the terms.

A language $L$ is recursive (aka decidable) if there is a Turing machine that halts for all inputs, accepting every word in $L$ and rejecting every word not in $L$. $L$ is recursively enumerable (aka semi-decidable) if there is a Turing machine that halts and accepts any input in $L$ and, for any input not in $L$, it either halts and rejects or it does not halt.

Therefore, every recursive language is recursively enumerable. The machine that decides the recursive language is a special case of the machine required for a recursively enumerable language: specifically, it is allowed to either loop forever or reject for words not in $L$; in fact, it always rejects and never uses the option of looping forever.


Can String be a subtype of Character in a programming language?

Character and String are conceptually very, very different. Google for "inheritance vs. composition" - you seem to think that Character and String should be connected via inheritance, but in reality a String is composed of 0, 1 or more Characters.

And to throw a spanner in the works: Strings are often large, and String operations must be very efficient. Therefore, even though conceptually a String is an array of Characters, it will not be implemented as a sequence of objects, but as an array of somehow simpler elements, for example UTF-16 codes.

And then you can think about how to implement Character efficiently if you use Unicode and an emoji character can easily be made up of a dozen Unicode code points - but the huge majority of Characters doesn't need that complexity, and you want an implementation that is space efficient and fast.


Reduction from Vertex Cover to Dominating Set

If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$  such that  $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each other vertex in $V$. Formally: $E' = E \cup \{ (x,v) \mid v \in V \cup \{y\}\}$.

If $G$ admits a vertex-cover $C$ of size at most $k$, then $G'$ admits a vertex-cover of size at most $k+1$, namely $C \cup \{ x \}$.

If $G'$ admits a vertex-cover $C$ of size at most $k+1$, then $G$ admits a vertex-cover of size at most $k$. This can be easily seen by noticing that $C \setminus \{ x, y\}$ must cover all the edges in $E$, and that $(x,y) \in E'$ ensures that at least one of $x$ and $y$ is in $C$, i.e., $|C \setminus \{ x, y\}| = |C| - |C \cap \{x,y\}| \le |C| - 1 \le k$.

Since $G'$ has no isolated vertex, you can now safely transform it to the graph $H$ of the dominating-set instance (using the known reduction).
In this way you show that $G$ has a vertex-cover of size at most $k$ $\iff$ $H$ has a dominating set of size at most $k+1$.


Confusion about proof of undecidability of REGULAR TM in Sipser's book

A universal Turing machine accepts a machine $M$ and an input $x$, and simulates the run of $M$ on $x$.

If $M$ halts on $x$, the universal Turing machine will also halt, and will output the state of $M$ at the end of computation.
If $M$ doesn't halt on $x$, the universal Turing machine will also not halt.

This is what the machine $M_2$ does on step 2. It simulates $M$ on $w$, and may or may not halt. What a universal Turing machine cannot accomplish is solve the halting problem, that is, given $M$ and $x$, do some computation which always terminates, and answer whether $M$ halts on $x$ or not. Instead, it simulates $M$ on $x$, and halts iff $M$ halts on $x$.

We shouldn't be able to tell whether an arbitrary machine $M$ halts on an arbitrary $w$ or not. The reduction translates this question into the question whether $L(M_2)$ is regular. Since the former question is undecidable, so is the latter one.


Relation between mathematical functions and trees?

A tree structure can be completely described by three functions:

a function that given a node $x$ returns the number of children of that node,
a function that given a node $x$ and index $i$ returns the $i$th child of that node, and
a function that given a node $x$ returns an associated value $v$ stored at that node.