What exactly is the semantic difference between set and type?

To understand the difference between sets and types, ones has to go back to pre-mathematical ideas of "collection" and "construction", and see how sets and types mathematize these.

There is a spectrum of possibilities on what mathematics is about. Two of these are:

We think of mathematics as an activity in which mathematical objects are constructed according to some rules (think of geometry as the activity of constructing points, lines and circles with a ruler and a compass).
Thus mathematical objects are organized according to how they are constructed, and there are different types of construction. A mathematical object is always constructed in some unique way, which determines its unique type.
We think of mathematics as a vast universe full of pre-existing mathematical objects (think of the geometric plane as given). We discover, analyze and think about these objects (we observe that there are points, lines and circles in the plane). We collect them into set. Usually we collect elements that have something in common (for instance, all lines passing through a given point), but in principle a set may hold together an arbitrary selection of objects. A set is specified by its elements, and only by its elements. A mathematical object may belong to many sets.

We are not saying that the above possibilities are the only two, or that any one of them completely describes what mathematics is. Nevertheless, each can view can serve as a useful starting point for a general mathematical theory that usefully describes a wide range of mathematical activities.

It is natural to take a type $T$ and imagine the collection of all things that we can construct using the rules of $T$. This is the extension of $T$, and it is not $T$ itself. For instance, here are two types that have different rules of construction, but they have the same extension:

The type of pairs $(n, p)$ where $n$ is constructed as a natural number, and $p$ is constructed as a proof demonstrating that $n$ is an even prime number larger than $3$.
The type of pairs $(m, q)$ where $m$ is constructed as a natural number, and $q$ is constructed as a proof demonstrating that $m$ is an odd prime smaller than $2$.

Yes, these are silly trivial examples, but the point stands: both types have nothing in their extension, but they have different rules of construction. In contrast, the sets
$$\{ n \in \mathbb{N} \mid \text{$n$ is an even prime larger than $3$} \}$$
and
$$\{ m \in \mathbb{N} \mid \text{$m$ is an odd prime smaller than $2$} \}$$
are equal because they have the same elements.

Note that type theory is not about syntax. It is a mathematical theory of constructions, just like set theory is a mathematical theory of collections. It just so happens that the usual presentations of type theory emphasize syntax, and consequently people end up thinking type theory is syntax. This is not the case. To confuse a mathematical object (construction) with a syntactic expression that represents it (a term former) is a basic category mistake that has puzzled logicians for a long time, but not anymore.


A Case Distinction on Dynamic Programming: Example Needed!

There are plenty of other examples of dynamic programming algorithms that don't fit your pattern at all.

The longest increasing subsequence problem requires only a one-dimensional table.
There are several natural dynamic programming algorithms whose tables require three or even more dimensions.  For example: Find the maximum-area white rectangle in a bitmap.  The natural dynamic programming algorithm uses a three-dimensional table.
But most importantly, dynamic programming isn't about tables; it's about unwinding recursion.  There are lots of natural dynamic programming algorithms where the data structure used to store intermediate results is not an array, because the recurrence being unwound isn't over a range of integers.  Two easy examples are finding the largest independent set of vertices in a tree, and finding the largest common subtree of two trees.  A more complex example is the $(1+\epsilon)$-approximation algorithm for the Euclidean traveling salesman problem by Arora and Mitchell.


Can a non-RE language be reduced to an RE language?

As you say, no non-RE language $U$ can be reduced to any RE language $L$, because, then, we could recognize $U$ using the reduction and the recognition algorithm for $L$.

The language $L_{diag}$ that you mention is indeed non-RE: it's the complement of an RE set that isn't recursive.  There is no recursive reduction from $L_{diag}$ to $L$.


Is there an existing protocol where a sender does not know who he is sending data to?

If you want strong protections for the identity/anonymity of the participants, you might be interested in systems for anonymous communication, such as Tor.

If you're just interested in systems where the destination's address isn't necessarily known under normal operating conditions (but it's not a critical security goal to ensure it can never be known), you might be interested in peer-to-peer overlay networks, such as Chord and many others.


Which process states exist a multi-processor machine?

More states aren't technically needed, depending on an operating system's implementation.

A kernel can have a task scheduler running on each processor. This allows for the use of the same process states, since each scheduler is running independent of each other. The kernel can have "load balancing" between the processors so that not too many processes are queued-up on one processor

xv6 (UNIX V6 port for x86 architecture) is a bare-bones kernel that does just this, and so, it has the same process states like in a single-processor environment.


Finding maximum-cardinality independent set with a particular oracle

If $k = 0$ then your algorithm outputs a stable set of maximum size. In the general case, try duplicating each vertex $k+1$ times, and see if it helps.


Why do we have to trade abstraction for speed?

Debunking some myths

There is no such thing as a fast langauge. A language can generally produce fast code, but different languages will excel on different benchmarks. We can rank languages on a particular set of flawed benchmarks, but cannot rank languages in a vacuum.
C code tends to be faster because people who need every inch of performance use C. A statistic that C is faster "by a factor of 10" might be inaccurate, because it might be that the people using Python just don't care as much about speed and didn't write optimal Python code. We see this in particular with languages like Haskell. If you try really hard, you can write Haskell that performs on par with C. But most people don't need that performance, so we have a bunch of flawed comparisons.
Sometimes, it is unsafety, not abstraction, that makes C fast. Its lack of array-bounds and null-pointer checks save time, and have been the cause of numerous security holes throughout the years.
Languages aren't fast, implementations are fast. Many abstract languages start slow, because speed is not their goal, but get faster as more and more optimizations are added.

The abstraction vs speed tradeoff is perhaps inaccurate. I would suggest a better comparison:

Simplicity, speed, abstraction: Choose two.

If we're running identical algorithms in different languages, the question of speed comes down to the problem of "How much stuff do we need to do at runtime to make this work?"

In a highly abstract language that is simple, such as Python or JavaScript, because we don't know about the representation of data until runtime, there end up being lots of pointer de-referencing and dynamic checks happening at runtime, which are slow.

Likewise, there are a lot of checks that need to be done to ensure that you don't wreck your computer. When you call a function in python, it needs to make sure that the object you're calling actually is a function, since otherwise you could end up executing random code that does terrible things.

Finally, most abstract languages have overhead from garbage collection.
Most programmers have agreed that having to track the lifetimes of dynamically allocated memory is a pain, and they'd rather have a garbage collector do it for them at run time. This takes time, that a C program doesn't need to spend on GC.

Abstract Doesn't mean slow

However, there are languages which are both abstract and fast. The most dominant in this era is Rust. By introducing a borrow checker and a sophisticated type system, it allows for abstract code, and uses compile-time information to reduce the amount of work that we need to do at runtime (i.e. garbage collection).

Any statically typed language saves us time by reducing the number of runtime checks, and introduces complexity by requiring us to please a typechecker at compile-time. Similarly, if we have a language that encodes whether a value can be null into its type system, we can save time with compile time null-pointer checks.


decidability about intersection of regular language and context free language

It is known that the intersection of a regular language and a context free one is context free. Besides, you can always take your regular language to be $\Sigma^*$, so any context free language can be the result.
Then the question is if a given context free language is empty, which is easy to answer.
To ask if the complement of a context free language is empty is to ask if it is $\Sigma^*$, which is undecidable.


State complexity of converting epsilon-NFAs to NFAs without epsilon transitions

Yes, we can transform an epsilon NFA into a NFA by keeping the same state set, basically adding new edges. If there is an $\varepsilon$ path from state $p$ to state $q$, and an edge from state $q$ to state $r$, then add an $a$ edge from $p$ to $r$. Also, if from state $p$ we can reach a final state then state $p$ can be made accepting. After these two steps we can remove the original $\varepsilon$ edges without changing the language.


I would say you are right. If the post order of a tree is "left-recursion, right-recursion, root" then the reverse is "root, reverse-right-recursion, reverse-left-recursion", which is exactly what you propose. Technically the proof would state "by induction on the structure of the tree".


Decidability of Turing Machines with input of fixed length

@jmite correctly points out that the statement is written in such a way that the language is obviously undecidable. Even with 0 cells of input, as long as the machine is able to use an unbounded amount of work tape, the language will be undecidable. This is a completely basic fact about the Halting set.

@Michael should check to see whether the problem states that the machine only has 100 cells of input, or of total tape to work with. Did you transcribe the problem correctly?

Given the suggested official answer (which is not very good, may I know where this problem came from?), I think the problem meant to say that the total amount of tape available is 100 cells. In which case, the answer is as follows.

The language is decidable. Let us suppose the tape alphabet consists of three symbols, $0$, $1$ and blank.

Given a Turing machine $M$ with $n$ states, there are at most
$$n \times 3^{100} \times 100$$
configurations of the machine, the head and the tape: the machine can be in any one of $n$ states, each of the 100 cell tapes may contain one of three symbols, and the head may be in 100 different positions. To determine whether $M$ halts, we simulate step by step for at most $n \times 3^{100} \times 100 + 1$ steps. If the simulation halts, then $M$ halts, otherwise $M$ will have repeated the same configuration twice and therefore loop forever. We may even detect the repeated configuration if we wish.

Let me address the other two answers:

@jmite: you missed the fact that we may halt the simulation after a finite number of steps because there are only finitely many possible configurations of the machine, the tape and the state.
@Patrick87: it is true that the number 100 can be replaced with any other number. So, for any machine $M$ and any number $n$ we can decided whether $M$ will halt on a tape of length $n$. This however does not allow us to deduce anything about $M$ halting on an infinite tape because $M$ could run forever by using up unbounded amounts of tape. There will be no $n$ such that $M$ uses only $n$ cells, so knowing what it does on $n$ cells won't be helpful.


What are some undecidable problems for recursive languages?

For recursive languages, membership is decidable by definition, so most undecidable questions with regards to them will involve quantifiers. It's decidable to check if there's a given input is accepted, but it's undecidable to check whether a recursive language accepts any string, for example.

That said, questions like this are almost never phrased in terms of recursive languages, because there's representation of languages that captures exactly the recursive languages. Generally we represent languages as Turing Machines, but these characterize the recursively enumerable languages.

When it comes to RE, there's something called Rice's theorem,which says that any non trivial property of RE languages is undecidable. This holds for anything that's a property of the language itself, not just the specific representation.


An implication is true if the antecedent is false.

If j is 1 then the antecedent is false no matter what k you choose, which means that the implication is vacuously true for every k. So the assertion is true.


The actual claim is that there is no DFA for the language $\{p^kq^k\mid k\geq 0\}$. Such an automaton would have to accept every string of the form $p^kq^k$ for any $k$, and reject every other string.

For any one fixed value of $k$, you're absolutely right that you can use $2k$ states to count off the $p$'s and the $q$'s. However, to recognize the language, the automaton would have to be able to do this for infinitely many different values of $k$, which would require infinitely many states by this method. Of course, that's not allowed in a deterministic finite automaton.

Note that this isn't a formal proof that no DFA can accept this language; rather it's just an intuition about why you should expect there to be no DFA. To formally prove the claim, you'd have to use something like the pumping lemma or Myhill–Nerode; we have a reference question about how to do that.


Finding number of numbers dividing n^m exactly p times

Start by factoring $n$ (you can use a table of all primes of size at most $1e4$). Now you can write $n^m = \prod_i p_i^{c_i}$. Now come up with a criterion for $x = \prod p_i^{a_i}$ to divide $n^m$ exactly $p$ times, and use this criterion to answer your question.


Why is this language *not* pumpable? (language = arbitrary word followed by exact same arbitrary word)(pumping lemma for context-free-languages)

Some strings in your language are pumpable, others aren't. You have to look for one that isn't pumpable. Use the fact that the relevant piece is of limited length.
In your case, say the pumping length is $N$, and take $\sigma = 0^N 1^N 0^N 1^N$. You'll find that however you position the part that gets pieces repeated, you won't be able to increase the first and second stretch of $0$ or of $1$, or get the correct repeat by pumping around one of the $0/1$ boundaries.


Weighted Average of Neural Networks with Cross Entropy Cost Function

Disclaimer: In most situations, I would expect that a single neural network will be at least as good as an ensemble, so there's typically probably not much reason to bother with an ensemble.  In particular, if we compare an ensemble of $n$ small neural networks to a single big neural network that is $n$ times as large, I would expect that typically the big neural network will perform at least well as the ensemble.  So in most situations you're probably better off skipping the ensemble and training a big neural net. That said, here's how you can train an ensemble.

Unweighted average: The simplest way to train an ensemble is to use an unweighted average of the softmax outputs of the individual networks.  Let $F_1,\dots,F_n$ denote the networks in the ensemble, $F_i(x)$ denote the vector of softmax outputs of the $i$th network on input $i$, and $F_i(x)_c$ denote the softmax output for class $c$ from $F_i(x)$.  Define $F$ by

$$F(x) = (F_1(x) + \dots + F_n(x))/n,$$

i.e.,

$$F(x)_c = (F_1(x)_c + \dots + F_n(x)_c)/n.$$

This is the unweighted average of the individual networks.  You can train $F$ in two ways: either train each network individually, or train the whole ensemble end-to-end.

To train the ensemble end-to-end, you treat $F$ as a big model whose parameters are all of the parameters of all of the networks, and you optimize cross-entropy loss applied to the output of $F$.
Alternatively, you can train each network individually.  Train $F_1$ using cross-entropy loss on the output of $F_1$; then train $F_2$; and so on.

In principle, end-to-end training should yield performance at least as good as training each network individually.  However, training each network individually is simpler and requires less memory on the GPU.

Weighted average: We can generalize these ideas to train an ensemble that is a weighted average of the outputs of the individual neural networks.  Define $F$ by

$$F(x)_c = {\alpha_{1c} F_1(x)_c + \dots + \alpha_{nc} F_n(x)_c \over \alpha_{1c} + \dots + \alpha_{nc}},$$

where the $\alpha_{ic}$ are the weights.  There are two ways to train such an ensemble:

You can train it end-to-end.  You have a big model for $F$, whose trainable parameters are the parameters of the individual networks as well as the weights $\alpha_{ic}$.  Then, apply an optimizer to minimize cross-entropy loss applied to the output of $F$.
Alternatively, you can train each network individually, then fix the networks and train the weights $\alpha_{ic}$ subsequently.  Once you've trained the individual networks, compute new feature vectors $v_{ij} = F_i(x_j)$, where $x_j$ is the $j$th element of the training set.  Now you can throw away the $x$'s and work only with the $v_{ij}$'s, as we have
$$F(x_j)_c = {\alpha_{1c} v_{1jc} + \dots + \alpha_{nc} v_{njc} \over \alpha_{1c} + \dots + \alpha_{nc}}.$$
Finally, user an optimizer to learn the parameters $\alpha$ that minimize the cross-entropy loss on $F(x_j)$'s, using the above equation to relate this to the (trainable) $\alpha$'s and the (fixed) $v$'s.  Any stochastic gradient descent based optimization method should work fine.  You might want to initialize all the $\alpha$'s to $1/n$, and renormalize the $\alpha$'s after each iteration to prevent them from growing without bound.

The same tradeoffs between end-to-end training vs training each network individually apply.

I'm not expecting an ensemble based on a weighted average to do significantly better than an unweighted average, in most cases; and I'm not expecting an ensemble to do significantly better than a single large network, in most cases.  But there could always be exceptions, and hopefully this gives you a reasonable way to train such ensembles.


Pre-requisite knowledge before diving into algorithms

To learn algorithms mathematically you will need to have a basic understanding of

Proofs(basically using induction)
summations and
asymptotic notations(like Big-O , Big-Omega)

To learn the above subjects I recommend this course from  https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-042j-mathematics-for-computer-science-spring-2015/


Turán's theorem states that if a graph on $n$ vertices doesn't contain an $(r+1)$-clique then it has at most $\lfloor \frac{r-1}{r} \frac{n^2}{2} \rfloor$ edges. You take it from here.


Deriving the regular expression for C-style /**/ comments

I can think of four ways:

Define an automaton for the language you are interested in. Convert the regular expression to an automaton (using Brzozowski's derivatives). Check that both automata accept the same language (determinize and minimize or use a bisimulation argument).
Write loads of test cases and apply your regular expression to them.
Convert the automaton defined in point 1 to a regular expression, using standard techniques.
A combination of the above.


It is impossible to do cryptanalysis on such a short message. It could be anything, encrypted with anything. Even if you somehow knew that it's a substitution cypher, it could be any 18-character message where the right characters match (there must be seven different letters; characters 1, 3, 13, 14 and 18 have to be the same; characters 1 and 2 must be different, etc.).

If you had a longer cyphertext (say a few hundred characters), you'd just compute the frequency of the characters appearing in the cyphertext and compare that to the frequency of the letters in the language you think the message was written in. The frequencies in English are: e 12.7%, t 9.1%, a 8.2%, o 7.5%, i 7.0%, n 6.9%, etc. If a decently long cyphertext comes decently close to that distribution, you'd expect a transposition cypher.  If you only have that the most common characters occur about 13%, 9%, 8%, 8%, 7%, 7%... of the time, you'd suspect a substitution cypher and you'd start guessing the letters based on their frequency. Note that the process is not automatic and you need to be flexible: for example, if the message is about the Zulus playing zithers in zoos in Zanzibar, the letter frequencies may be skewed quite some distance from the average over all English text.


Prove using pumping free lemma for context-free languages

i figured it out

$w = (ac^pb)^p $ cannot be split.

in the case that vxy consists of only a's and b's $uv^0xy^0z $ would have less a's and b's but not less c's.

in the case that vxy consists of only c's $uv^0xy^0z $ would have less c's but not less a's and b's.

in the case of a combination it might have an a or a b or both. if it has an a, the number of c's needs to increase by p, but $|vy| \le p$ and we'd need p + 1 terminals. for b the same holds, and for an a and a b it would need even more c's.

so we cannot split this word into 5 substrings  u,v,x,y,z such that $uv^ixy^iz$ is in L


Controlled NOT gate a type of measurement?

A controlled-NOT gate is meant to be a reversible operation which, for ordered pairs of bits $(a,b) \in \{0,1\}^2$, performs the operation
$$ \mathrm{CNOT} (a,b)\; = \;(a, b \oplus a)$$
where conventionally we represent the "control" by the first bit and the "target" by the second. (In a physical implementation, essentially the same physical interaction but in a different orientation would be used to implement the transformation $(a,b) \mapsto (a\oplus b, b)$ and so this is also called a "controlled-NOT", rarely with any distinction from the one described above.) This gate is obviously reversible, as one can easily verify that $\mathrm{CNOT} \circ \mathrm{CNOT} = \mathrm{id}\,$.

As is usual in quantum computation, we "lift" reversible operations such as $\mathrm{CNOT}$ to distributions over inputs by describing it as a permutation of computational basis states. In particular, because
$$\begin{align*}
(0,0) \;&\xrightarrow{\;\mathrm{CNOT}\;\;}\; (0,0) \\
(0,1) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (0,1) \\
(1,0) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (1,1) \\
(1,1) \;&\xrightarrow{\;\phantom{\mathrm{CNOT}}\;\;}\; (1,0)
\end{align*}$$
the permutation matrix which we use to represent $\mathrm{CNOT}$ is
$$ \mathrm{CNOT} \;=\; \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}\; .$$
It is easy to verify that this (and all other permutation matrices) are unitary. This is the operation which transforms the state of the first two qubits. Because the state of those two qubits just before the $\mathrm{CNOT}$ gate is given by
$$ |\psi_1\rangle \;=\; (H \otimes \mathbf 1) |0\rangle |0\rangle \;=\; \tfrac{1}{\sqrt 2} \Bigl[ |0\rangle |0\rangle  + |1\rangle |0\rangle \Bigr] \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \,,$$
the state that we obtain afterwards is given by
$$ |\psi_2\rangle \;=\; \mathrm{CNOT} |\psi_1\rangle \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 1 \\ 0 \end{bmatrix} \;=\; \tfrac{1}{\sqrt 2} \begin{bmatrix} 1 \\ 0 \\ 0 \\ 1 \end{bmatrix}  \;=\; \tfrac{1}{\sqrt 2} \Bigl[ |0\rangle |0\rangle  + |1\rangle |1\rangle \Bigr] \,.$$
In this case, it's probably easiest to see that you can apply the action of $\mathrm{CNOT}$ on the standard basis states $|0\rangle|0\rangle$ and $|1\rangle|0\rangle$ separately, which form the components of $|\psi_1\rangle$, to obtain components  $|0\rangle|0\rangle$ and $|1\rangle|1\rangle$ respectively; this is possible because the $\mathrm{CNOT}$ operation (and all other permutations and unitary operators) is linear.


Recurrence relation with a number value (not n)

The recursion tree corresponds to repeated expansion of the recurrence:
$$
\begin{align*}
T(n) &= 3 + aT(n/4) \\ &=
3 + 3a + a^2T(n/16) \\ &=
3 + 3a + 3a^2 + a^3T(n/64) \\ &= \cdots \\ &=
3 + 3a + \cdots + 3a^{k-1} + a^kT(n/4^k) \\ &=
3\frac{a^k-1}{a-1} + a^kT(n/4^k).
\end{align*}
$$
This is the result if you stop the recursion after $k$ steps. If, for example, you define $T(1) = 3$ then for $n = 4^k$ you will get $T(n) = 3+3a+\cdots+3a^k = 3\frac{a^{k+1}-1}{a-1} = \Theta(a^{\log_4 n})$.


By definition, a language is decidable if there exists a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. Therefore one way of showing that a language is decidable is by describing a Turing machine that accepts it.

There are many offline and online resources on Turing machines. For example, here are some introductory slides on Turing machines: part 1, part 2.


minimum number of points a convex hull must have

The convex hull of 10 collinear points is the line segment between the two extreme points.
No, a convex hull does not have to be convex polygon. A convex hull can be a point, a line segment, a ray, a line, a convex polygon, a circular sector, a half plane, a cubic, etc. .
A definition in math, such as the definition of convex hull, is the strictest kind of definition. It means exactly what it says. No more, no less.


Having trouble proving vertex cover greedy algorithm

I had initially missed parts 2.3 and 3.

If I'm not still missing something, then your algorithm can find a non-optimal cover for the hexagon, and necessarily finds a non-optimal cover for  $K_{3,3}$ minus one edge. (Those are both connected balanced-bipartite graphs, so each half of their bi-partitions is a three-vertex vertex cover.)

The hexagon's vertices all have degree two, so "highest edge count (total)"  won't do anything, and your algorithm will fall back on 2.2 for each loop through 2. Your algorithm's initial choice for the hexagon doesn't matter, and its next choice will be an arbitrary one of the three vertices in the hexagon's opposite half. If your algorithm chooses the middle of those three  (i.e., the opposite vertex), then its next choice won't matter and part 2 will finish by choosing an arbitrary one of the vertices in the remaining unmarked edge. If its last choice is the one that is opposite from its next-to-last choice, then S will be the four vertices vertices from two opposite edges, which is a minimal vertex cover, in which case part 3 can't remove anything.

$K_{3,3}$ minus one edge has four vertices with degree three and no vertices with higher degree.Those four vertices are each adjacent to a degree-two vertex, so will all be put into S. Due to the removed edge, putting those four in will result in there being no unmarked edges. Since only that edge was removed, S is a minimal vertex cover, so part 3 can't remove anything from it.


What are the advantages of x86 CPUs over ARM?

I'll start with the commonly known stuff, that are currently talked about the most.
x86
All x86 processors are developed from the CISC (Complex Instruction Set Computers) architecture. The x86 processors allow you to perform several activities at the same time from a single instruction. Also, they can perform numerous simultaneous tasks without any of them being affected.
This makes them very sophisticated and advanced processors, allowing many complex calculations in a short time. The disadvantage of this design is that they need a lot of power to function and more power means more heat.
Summary: x86 chips are designed to be power hungry and high clocked, multi-thread, high instructions per cycle. In the general use-case they will be a lot faster than your common ARM chip.
ARM
As for ARM processors, they are based on the RISC (Reduced Instruction Set Computer) architecture, which is much simpler than CISC. These processors can do a much smaller number of calculations since they require several commands to act.
RISC instructions are smaller and faster to process, so in part, the disadvantage of having to process several commands for a single action is minimized. Still, ARM processors are much less powerful than the x86.
Summary: ARM chips are designed for low power draw, flexibility, low cost and low heat with good performance.
source of the info above
SoC M1
M1 is not a CPU. It is a whole system of multiple chips put into one large silicon package. The CPU is just one of these chips. And that's the main reason why it's so different and fast compared to the typical ARM chip.
Basically, the M1 is one whole computer onto a chip. The M1 contains a CPU, graphical processing unit (GPU), memory, input and output controllers, and many more things making up a whole computer. This is what is call a system on a chip (SoC).
In the past computers would have multiple physically separate chips on the motherboard of the computer. However because we are able to put so many transistors on a silicon die today, companies such as Intel and AMD began putting multiple microprocessors onto one chip (CPU cores). One core is basically a full independent chip that can read instructions from memory and perform calculations. This has for a long time been the name of the game in terms of increasing performance - just add more general-purpose CPU cores.
Instead of adding ever more general-purpose CPU cores, Apple has followed another strategy - they have started adding ever more specialized chips doing a few specialized tasks. The benefit of this is that specialized chips tend to be able to perform their tasks significantly faster using much less electric current than a general-purpose CPU core.
Hope that answers your question.
You can find more details on the M1 where I got the info for the second part of the answer. There is a lot of additional and interesting info on the CPU market and the software differences inside the M1 and Intel/AMD chips: link


NP-complete reduction proof -- graph problem

We can reduce independent set ($IS$) problem to the overarching ($OVERARCHING$) problem as follows. We reduce the instance $\langle G, k \rangle$ of IS to an instance $\langle G',S,k\rangle$ of OVERARCHING by the following reduction.

Each vertex $v_i \in V(G)$ becomes an edge $v^1_iv^2_i = e_{v_i} \in E(G')$. $G'$ will be a disconnected graph containing $|V(G)|$ edges and $2|V(G)|$ vertices. For every $v_iv_j \in E(G)$ we will add pair $(v^1_iv^2_i, v^1_jv^2_j) = (e_{v_i}, e_{v_j})$ in $S.$ If we select one of the vertices which are neighbor then we select one of the edge in the corresponding pair in the set $S$. Since all edges are disjoint in $G'$ we have absolute freedom  there in selecting any edge we want.

Then $\langle G, k \rangle$ has a $k$-size independent set if and only if $\langle G',S,k\rangle$ has a $k$-size "overarching" set $M$.

Thus $IS \leq_P OVERARCHING$, and hence $OVERARCHING$ is NP-complete.


Divide and conquer algorithm for a gas station problem

You can use binary search on the range of the car. Refill only if needed.

Here is the algorithm in more detail.

Let low = 0 and high = distance from c0 to cn. During the whole algorithm, range high is always big enough for a car to reach cn from c0, while range low is always not.
Repeat the following as long as low + 1 < high

mid = (low + high) /2
If range mid is big enough, set high = mid. Otherwise, set low = mid.

Return high, which must be the minimum range of the car.

How can we check if a given range is big enough?
Simple.
We will try driving a car with that range from c0 to cn. At each city, if the remaining range of the car is not enough for the car to reach the next city, refill the car to its full range. If we have refilled s+1 times before we have reached cn, that given range is not enough. Otherwise, it is enough.

It takes $O(n)$ time to check whether a given range is big enough.
The bisecting loop will run at most $\lceil\log_2 m\rceil$ iterations, where $m$ is the distance from c0 to cn.
So, the algorithm runs in $O(n\log_2 m)$-time.


Classification of intractable/tractable satisfiability problem variants

Classic, well-known results
As mentioned by Standa Zivny on the related question of CSTheory, Which SAT problems are easy?, there's a well-known result by Schaefer from 1978 (quoting the answer of Zivny):

If SAT is parametrised by a set of relations allowed in any instance, then there are only 6 tractable cases: 2-SAT (i.e. every clause is binary), Horn-SAT, dual-Horn-SAT, affine-SAT (solutions to linear equations in GF(2)), 0-valid (relations satisfied by the all-0 assignment) and 1-valid (relations satisfied by the all-1 assignment).

Planar-3SAT meaning the planar version of 3SAT is known to be $\mathcal{NP}$-complete. See D Lichtenstein, Planar formulae and their uses, 1981. The non-planar version of 3SAT is of course the very well-known classic $\mathcal{NP}$-complete problem.
Not-All-Equal 3SAT (NAE-3SAT) is $\mathcal{NP}$-complete. However, the planar version of it is in $\mathcal{P}$ as shown by Moret, Planar NAE3SAT is in P, 1988.
More recent and/or "weird" variants
$k$-colourable Monotone NAE-3SAT
Here's a more exotic or weird variant, a decision problem called the $k$-colourable Monotone NAE-3SAT:

Given a monotone CNF expression $\phi$ with exactly three distinct variables in each clause, such that the corresponding constraint graph $G(\phi)$ is k-colourable, is the expression $\phi$ not-all-equal satisfiable?

Here the corresponding constraint graph $G(\phi)$ is a simple undirected graph associated with $\phi$ as follows: Each variable of $\phi$ is a vertex in $G$, and two vertices have an edge between them iff they appear in some clause together.
For $k=4$ the problem is in $\mathcal{P}$. For $k=5$ however, it is $\mathcal{NP}$-complete. See P Jain, On a variant of Monotone NAE-3SAT and the Triangle-Free Cut problem, 2010.
Linear CNF variants
While not perhaps being exotic or weird, some well-known variants, namely NAE-SAT (not-all-equal SAT) and XSAT (Exact SAT; exactly one literal in each clause to 1 and all other literals to 0), of the satisfiability problem have been investigated in the linear setting. Clauses of a linear formula pairwise have at most one variable in common. Interestingly, the complexity status does not follow from Schaefer's Theorem.
NAE-SAT and XSAT remain $\mathcal{NP}$-complete when restricted to linear formulas. Moreover, NAE-SAT and XSAT are still $\mathcal{NP}$-complete on formulas only containing clauses of length at least $k$, for each positive fixed integer $k \geq 3$. They are $\mathcal{NP}$-complete for monotone (no positive literals) linear formulas. However, NAE-SAT is polynomial-time decidable on exact linear formulas, where each pair of distinct clauses has exactly one variable in common.
Some further aspects regarding the complexity of NAE-SAT and XSAT under certain assumptions are probably still open. For more specifics, see for example Porschen and Schmidt, On Some SAT-Variants over Linear Formulas, 2009 and Porschen et al., Complexity Results for Linear XSAT-Problems, 2010.


Confusion about big-O notation comparison of two functions

The key thing to keep in mind here is that the equals sign in $f = O(g)$ does not behave as an equals sign usually would. The reason is that $O(g)$ is not actually a function but a set of functions. For example, you can think of $O(n^2)$ as being a set which, among many other functions, contains the functions $n$, $5 \sqrt n$, $\log^5 n$, etc. So as the appropriate way to think of $f = O(g)$ is not as equality but instead as being an element of a set: $f \in O(g)$.

So the set $O(n)$ is a subset of $O(n^2)$ since any function that is asymptotically bounded above by a multiple of $n$ is also bounded asymptotically above by a multiple of $n^2$.


Are NP-complete sets formed from two other sets only if at least one is NP-hard?

The intersection of two non-NP-hard languages can be NP-hard.  Example: The solutions of any 3SAT instance are the set intersection of the solutions of a HORN-3SAT instance and an ANTIHORN-3SAT instance.  This is because a 3CNF clause must be either a Horn or anti-Horn clause and a 3SAT instance is the conjunction of such clauses.  3SAT is of course NP-complete; HORN-3SAT and ANTIHORN-3SAT are both in P.


Does last carry bit get added onto the sum calculated by full adder?

Addition on $w$-bit registers (or memory locations) is effectively addition modulo $2^w$, that is the carry bit is thrown away. However, on x86 CPUs at least, before getting thrown away, it is copied to the carry flag or overflow flag (so the carry bit is actually not thrown away). An additional instruction, "add with carry", adds two inputs together with the carry flag. Using these instructions, you can (1) detect overflow (which happens if the carry flag is set), and (2) implement addition on multiples on $w$ bits. For example, suppose you want to add two integers $x_1x_0$ and $y_1y_0$, where $x_i,y_i$ is each a $w$-bit memory location. You first add $x_0$ and $y_0$, and then add $x_1$ and $y_1$ along with the carry.

To answer your specific problem, for 4-bit wide registers, 0111+1011=0010, and additionally the carry flag is set, if any.


I haven't looked at your code, but a few observations.

Your selection method is very strong. If you generate 500 individuals at random and choose the best 100, within just a few generations you're going to have a population dominated by descendants of that initial 100 winners. In effect, you're very quickly focusing your search on the best 20% of a random sample. You probably need something like tournament or rank-biased selection instead -- something dramatically weaker than what you have.
The elite count is maybe a tad high as well. 5 might be OK, but certainly combined with your selection method, you have an algorithm that's basically designed to converge too quickly.
Averaging in crossover may or may not be harmful. It depends on where the optimal values of your parameters lie. Take a problem like "minimize f(x)=x^2 for x in [0, 100]". The optimal value of x in that problem is at 0, and averaging two parents will in this case always result in worse offspring than one of the parents you started with. For other problems, this may be helpful instead though. If you want to try something else, Simulated Binary Crossover (SBX) is often used for real-valued optimization problems. Alternately, one approach is to reduce the crossover rate and increase the mutation rate to provide a wider search of the parameter space.


What property of cons allows elimination of tail recursion modulo cons?

While GCC likely uses ad-hoc rules, you can derive them in the following way. I'll use pow to illustrate since you're foo is so vaguely defined. Also, foo might best be understood as an instance of last-call optimization with respect to single-assignment variables as the language Oz has and as discussed in Concepts, Techniques, and Models of Computer Programming. The benefit of using single-assignment variables is it allows remaining within a declarative programming paradigm. Essentially, you can have each field of the struct foo returns represented by single-assignment variables that are then passed to foo as additional arguments. foo then becomes a tail-recursive void returning function. No particular cleverness is needed for this.

Returning to pow, first, transform into continuation passing style. pow becomes:

pow(x, n):
    return pow2(x, n, x => x)

pow2(x, n, k):
    if n == 0: return k(1)
    else if n == 1: return k(x)
    else: return pow2(x, n-1, y => k(x*y))

All calls are tail calls now. However, the control stack has been moved into the captured environments in the closures representing the continuations.

Next, defunctionalize the continuations. Since there is only one recursive call, the resulting data structure representing the defunctionalized continuations is a list. We get:

pow(x, n):
    return pow2(x, n, Nil)

pow2(x, n, k):
    if n == 0: return applyPow(k, 1)
    else if n == 1: return applyPow(k, x)
    else: return pow2(x, n-1, Cons(x, k))

applyPow(k, acc):
    match k with:
        case Nil: return acc
        case Cons(x, k):
            return applyPow(k, x*acc)

What applyPow(k, acc) does is take a list, i.e. free monoid, like k=Cons(x, Cons(x, Cons(x, Nil))) and make it into x*(x*(x*acc)). But since * is associative and generally forms a monoid with unit 1, we can reassociate this into ((x*x)*x)*acc, and, for simplicity, tack a 1 on to start, producing (((1*x)*x)*x)*acc. The key thing is that we can actually partially compute the result even before we have acc. That means instead of passing k around as a list which is essentially some incomplete "syntax" that we'll "interpret" at the end, we can "interpret" it as we go. The upshot is that we can replace Nil with the unit of the monoid, 1 in this case, and Cons with the operation of the monoid, *, and now k represents the "running product". applyPow(k, acc) then becomes just k*acc which we can inline back into pow2 and simplify producing:

pow(x, n):
    return pow2(x, n, 1)

pow2(x, n, k):
    if n == 0: return k
    else if n == 1: return k*x
    else: return pow2(x, n-1, k*x)

A tail-recursive, accumulator-passing style version of the original pow.

Of course, I'm not saying GCC does all this reasoning at compile-time. I don't know what logic GCC uses. My point is simply having done this reasoning once, it's relatively easy to recognize the pattern and immediately translate the original source code into this final form. However, the CPS transform and defunctionalization transform are completely general and mechanical. From there fusion, deforestation, or supercompilation techniques could be used to attempt to eliminate the reified continuations. The speculative transformations could be thrown away if it is not possible to eliminate all the allocation of the reified continuations. I suspect, though, that that would be too expensive to do all the time, in full generality, hence more ad-hoc approaches.

If you want to get ridiculous, you can check out the paper Recycling Continuations which also uses CPS and representations of continuations as data, but does something similar to but different to tail-recursion-modulo-cons. This describes how you might produce pointer-reversing algorithms by transformation.

This pattern of CPS transforming and defunctionalizing is a quite powerful tool for understanding, and is used to good effect in a series of papers I list here.


A variation of the graph coloring problem

If $|M| = 2$, this is the max-cut problem.


This grammar will in fact get into an infinite loop because there is no transition for A to turn into a terminal.


This is related to the Hitting-Set-Decision-Problem:

Given $U=\{1,\ldots , n\}$ and $S\subseteq 2^U $, integer $k$
Decide whether $C\subseteq S $ exists s.t. $\cup_{X \in C} X = U$ and  $|C| \leq k$

The problem is NP-COMPLETE and thus we do not know whether a polynomial algorithm exists. The optimization problem which you refer to is NP-hard.
There are approximation algorithms (see wikipedia).


The problem in your first example is that the arrows don't compose. In the first, you have $f: A \leftarrow B$ and $g: C \leftarrow B$, so $f\circ g$ is not in $C$, hence in $C^{op}$ $f : B \leftarrow A$ and $g : B \leftarrow C$, and they still don't compose.

If you had $f: A \leftarrow B$ and $g: B \leftarrow C$, then they compose to $f\circ g =h : A \leftarrow C$ in $C$. In $C^{op}$ you have $f : B \leftarrow A$ and $g : C \leftarrow B$ and get $g\circ f = h : C \leftarrow A$ (remember in $C^{op}$ you want every thing running backwards) .

Your second example is fine, you just have $f : A \leftarrow B$ and $g : B \leftarrow A$ in $C$ and hence $f\circ g : A\leftarrow A$ and $g\circ f:B\leftarrow B$ in $C$. In $C^{op}$, they switch: $f :B \leftarrow A$, $g : A \leftarrow B$ are in $C^{op}$ and so are $g \circ f : A \leftarrow A$ and $f\circ g : B\leftarrow B$.

I wonder perhaps if the phrasing used by Bird is causing a problem. The rule is better stated:

  If $h = g \circ f$ in $C$ , then $h = f \circ g$ in $C^{op}$.

There's also a kind of name overloading going on here, from a programmer's perspective, reusing the same names for the opposite versions is a bit odd, it might make more sense to think along the lines (restating one of the rules):

  If $f : X \leftarrow Y$ is in $C$, then $f^{op} : Y \leftarrow X$ is in $C^{op}$.


Non-regularity of the set of primes in unary encoding using Myhill-Nerode

We can prove that every string in $L$, $a^p$, $p$ is prime, is in its own different equivalence class. We simply cannot have two strings, $a^p$ and $a^{p'}$, both $p$ and $p'$ prime, in same equivalence class.

Assume $a^p$ and $a^q$, $q>p$, $p$ and $q$ prime, are in same equivalence class. Then since $a^{p}a^{q-p}=a^q$ is in $L$ therefore $a^qa^{q-p}=a^{2q-p}$ will be in $L$. Since $a^{p}a^{2q-2p}=a^{2q-p}$ is in $L$ therefore $a^qa^{2q-2p}=a^{3q-2p}$ will be in $L$. We will be able to show that $a^{p+i(q-p)}$ will be in $L$ for every $i \geq 0 $. But for $i=p$ there is a contradiction.

Factually speaking even $a^c$ and $a^d$ for composites $c$ and $d$ will be in different equivalence classes. If we assume $a^c$ and $a^d$, $d > c$, where $c$ and $d$ are not primes, are in same equivalence class, then we can similarly reach a contradiction. Even if we don't prove this, the number of equivalence classes is still infinite because each $a^p$ for prime $p$ is in different equivalence class.

Thus as number of equivalence classes for $L$ is infinite (because number of primes is infinite), therefore by Myhill-Nerode theorem $L$ is not a regular language.


Predicting target location given cursor speed and direction

Fitts's law gives you a guess for the length of the movement (in terms of screen distance), and so gives you a rough spot where the user is aiming. Make a list of "points of interest" where the user is likely to click (a priori), and then put together a score which takes into account both the probability that the movement ends at the point, and its prominence. Pick the point with maximal score.

Machine learning has been used to derive the parameters for Fitts's law, and I'm not sure anything more is needed here apart from some UI experiments.


Yes, we shall use dynamic programming and extend our subset-sum algorithm here.

Let $R(i, \ s, \ t)$ be true iff there exists a subset $K \in \{1, ...
   i\}$ such that $$\sum_{i \in K} a_i = s \quad and \quad\sum_{i \in K} b_i = t.$$

Which subproblem would then give us the result we need? $R(n, 0, 0)$!

Now, let's find a recursive relation for our subproblem in terms of smaller subproblems:
$$R(i, \ s, \ t) := [(a_i==s) \wedge (b_i==t)] \\\vee R(i-1,  \ s, \ t)\\\vee\ R(i-1, \ s-a_i, \ t-b_i) $$

where, $\vee$ is the OR operator and $\wedge$ is the AND operator.

This relation works on the inclusion-exclusion principle - either we include the $i$th index in our subset $K$ or not. But the caveat here is that if we include the $i$th index, we must include both $a_i$ and $b_i$.

If we do not include the $i$th index, $R(i, \ s, \ t)$ reduces simply
to $R(i-1, \ s, \ t).$
If we do include the $i$th index, either ($a_i$ should be $s$)  AND   ($b_i$ should be t). Or, we must have some common subset of the two sets summing to $s-a_i$ and $t-b_i$ respectively i.e. $R(i-1,  \ s-a_i, \ t-b_i)$ should be true.

For the sake of completeness, the base cases are $R(1, \ s, \ t) := (a_1 ==s) \wedge (b_1==t)$.

Edit:The runtime of the algorithm then is $O(n^3{B^2})$ (Why?), which is pseudo-polynomial too.


On the computable function of a problem that halts

No, it is not.

In general, to help you think about this kind of problem, I recommend you work through some examples.  Keep them as simple as possible.

Here is an example that illustrates why the answer is no.  Suppose $P$ is the following program: "if the input is 1, then halt immediately; otherwise enter an infinite loop".  Suppose $F(1)=2$.  Then $P$ halts on the input $i=1$, but it does not halt on the input $F(i)=F(1)=2$.  So, the behavior of the program $P$ on one input tells you nothing about its behavior on a different input.


How do analogue computers perform logical operations?

As you point out, electronic analog computers were designed to compute differential equations, not simple logical operations.  You can model an arbitrary linear differential equation with a circuit made of op-amps, resistors, and capacitors, where the variables in your equation are represented by voltages and currents in your circuit.

For non-linearities you can add a diode.  The Shockley diode equation gives a good approximation for the behavior of a diode:

$$I = I_s ( e^{\frac{V}{nV_T}} - 1 )$$

(where $V$ is the voltage across the diode terminals, $I$ is the current, and $I_s$ and $n V_T$ are constants that depend on the construction of the diode.)  So now we can implement exponentials and logarithms.

So now to actually answer your question: logic circuits in modern digital computers are non-linear analog circuits where some circuit voltage or current is taken to represent the boolean value.  For example, we might say that a voltage greater than 5V represents true and a voltage less than 1V represents false.  (Any voltage between 1V and 5V is assumed to be an error).

In the 1950s this was sometimes implemented using diode logic.  For example the Wikipedia page shows this diagram of an or gate:

When this is followed by an inverting amplifier we get both a logical not operation, and restoration of any voltage levels that have degraded away from 0V or 6V.  For example a common emitter amplifier has this characteristic,

The point of all this is not that you have to use diodes and transistors to implement logic, but rather that any analog physical system with non-linearities and amplification can emulate boolean logic.  Hydraulic pumps, for example would have done just as well as diodes and transistors.


Construct a DFA from the regular expression (a)*+(aab)*

The approach of combining two smaller DFAs is right. However, it is not correct to superimpose one DFA on another simply. For example, your combined DFA accepts $aaab$, which is not included in $a^*+(aab)^*$.

The correct way to combine two DFAs so as to produce the union of their languages is to construct the product automaton of them, defining the new final states appropriately. Please check this question and answer for details.

For the current case, we can use more states in the DFA so that it remembers more about the input string and it is deterministic enough to stipulate each transition.

$$\begin{aligned}
q_0&: \text{for the empty string}.\\
q_{a}&: \text{for string }a.\\
q_{aa}&: \text{for string }aa.\\
q_{aaaa^*}&: \text{for strings } aaa, aaaa, \cdots.\\
q_{aab(aab)^*}&: \text{for strings } aab, aabaab, \cdots.\\
q_{aab(aab)^*a}&: \text{for strings } aaba, aabaaba, \cdots.\\
q_{aab(aab)^*aa}&: \text{for strings } aabaa, aabaabaa, \cdots.\\
q_{\text{reject}}&: \text{for all other strings.}\\
\end{aligned}$$

$q_0$ is the initial state. $q_0, q_{a}, q_{aa}, q_{aaaa^*}$ and $q_{aab(aab)^*}$ are accept states. $q_{reject}$ is a dead state.


The question is a little vague, but it seems like what you want to argue is along the line of this: Let $R$ be the concept to learn, and take any $R^*\subset R$ be any rectangle covering a $(1-\epsilon)$-fraction of $R$.  Then with some probability $R'$ will contain $R^*$.

The problem with this is that the particular probability depends on the specific choice of $R^*$.  I think what you're confused about is that want $R'$ to perform well on unseen examples.  By construction $R'$ will correctly classify all the training data.  The bad event is actually that all of the training data is concentrated in too small a rectangle; this happens with probability at most that of the event that one of the strips is missed by all the training examples.


Since you get
 $$g(n) = \sum_{i=1}^n (n/i)^2\geq n^2\sum_{i=1}^1 (1/i)^2=n^2\cdot H_n^{(2)}$$

Where $H_n^{(2)}$ is the second generalized harmonic number.

Since
$$\forall n\geq 1:\ \  1 < H_n^{(2)} < \frac{\pi^2}{6}$$

You get that
$$n^2 < g(n) < n^2 \cdot \frac{\pi^2}{6}$$

and $$f(n)=\frac{n(n+1)}{2}\leq \frac{(n+1)^2}{2}\leq \frac{(2n)^2}{2}\leq 2n^2$$
$$f(n)=\frac{n(n+1)}{2} \geq \frac{n^2}{2}$$

Then $$\forall n\geq 1: \frac{3}{\pi^2} g(n) \leq f(n)\leq 2\cdot g(n)$$

And thus $f(n)=\Theta(g(n))$.

As for the second part of the question:

Since $$\forall x,y,z>0:x^{\log_z y}=(z^{\log_z x})^{\log_z y}=z^{\log_z x\cdot {\log_z y}}=(z^{\log_z y})^{\log_z x}=y^{\log_z x}$$ you get that:

$$g(x)=3^{\log_2 n}=n^{\log_2 3}=n^{\log_4 9}$$

And thus $$f(n)=\Theta(g(n))$$


In Data Mining, what does it mean to be greedy?

I'm not a Data Mining expert, but from what I understand, it means the same thing as it does outside of data mining: to improving the solution in a locally optimal way, rather than one that is guaranteed globally optimal. (And, as Raphael comments, to not backtrack on that decision).

For example, if you are training a graphical model, the process of repeatedly adding the edge that improves your model's fit the most, until no changes improve the model, is a greedy process. at each stage, you've taken the action which has the most incremental improvement over your current model, but the result may not be globally optimal.

Likewise, in the clustering example, to say that the clusters are merged greedily means that they are merged in the way that provides the best incremental improvement over other merges, but may not lead to the optimal clustering at the end.


Virtual Memory vs Cache for block identification

I think it's because when using virtual memory, you have access to disk and thus have vasts amounts of memory to store extra data structures than can help you identify each page. In cache, you don't have that much memory, so the way to do things is to add identification (tag and set) bits to each cache line so that you don't need another data structure to identify each cache block because it would be expensive memory-wise. You just iterate over each set, identify the set you're looking for, then iterate over each cache line in that set and identify the cache line you're looking for and then extract the desired bytes. Also, iterating over all cache lines is not that expensive because there aren't a lot of them, but applying this technique to pages, which can be thousands, is really inefficient.


Karp hardness of an equidistant vertex set

Your problem is NP-hard, by reduction from E3SAT, an NP-hard variant of 3SAT in which every clause involves 3 different variables.

Let $C_1 \lor \cdots \lor C_m$ be an instance of 3SAT; we can assume that $m$ is larger than some constant, since otherwise we can brute force the answer in constant time.
We construct the following graph:

Vertices: There is a vertex $(C_i,\ell)$ for each clause $C_i$ and for each literal $\ell$ appearing in the clause.
Edges: We connect $(C_i,\ell)$ and $(C_j,\ell')$ if $i \neq j$ and $\ell \neq \lnot \ell'$.

Here are a few claims:

The formula is satisfiable iff the graph contains an $m$-clique. Indeed, if the formula is satisfiable, we choose one satisfied literal from each clause, and these are the vertices of the clique. In the other direction, an $m$-clique must identify a literal from each clause. These literals are non-contradictory, and so correspond to a (possibly partial) satisfying truth assignment.
The diameter of the graph is 2. Indeed, given two vertices $(C_i,\ell),(C_j,\ell')$ (where possibly $i=j$), assuming $m \geq 3$ we can find a vertex $(C_k,\ell'')$ such that $k \neq i,j$ and $\ell''$ involves a different variable from $\ell,\ell'$.
If $(C_i,\ell)$ and $(C_j,\ell')$ are at distance exactly 2 then either $i = j$ or $\ell = \lnot \ell'$.
Suppose that $K$ is a "2-clique", that is, a set of vertices in which any two vertices are at distance exactly 2. Pick some $(C_i,\ell) \in K$. If all vertices in $K$ are of the form $(C_i,\cdot)$ then $|K| \leq 3$. Otherwise, let $(C_j, \lnot \ell) \in K$, where $j \neq i$. Every other vertex $(C_k, \ell') \in K$ must satisfy $k \neq i$ or $k \neq j$; suppose, without loss of generality, that $k \neq i$. Then $\ell' = \lnot \ell$. Since $(C_k, \lnot \ell)$ and $(C_j, \lnot \ell)$ are at distance 2, necessarily $j = k$. That is, in this case $|K| \leq 2$.
Therefore if $m \geq 4$, there is an equidistant vertex set of size $m$ iff the formula is satisfiable.


Joining tables with minimum number of joins

I believe that your problem is NP-complete.

Showing that it's in NP is easy. To show that it's NP-hard, take any instance of the set cover problem. Add a new unique element to the universe, and add it to each set. Interpreting each set as a table, a solution to the minimum join problem is a solution to the original set cover problem.


I assume you want to start your proof with "suppose there is a pairing where a good man $m_1$ is matched with a bad woman $w_1$".

This indeed means that there exists a good woman $w_2$ matched with a bad man $m_2$ (by the pigeonhole principle). However, the contradiction here does not follow from the fact that $w_2$ prefers $m_1$ but is actually matched to $m_2$ (it is possible for a woman to not be matched with her top ranked man).

The contradiction follows from the fact that a matching which contains $(m_1,w_1),(m_2,w_2)$ is not stable, since $m_1$ prefers $w_2$ and $w_2$ prefers $m_1$.


what is the difference between transition function (delta) and extended transition function (delta cap ) in finite automata

I read some references in order to answer your question ,

Transition function : takes as arguments a state and an input symbol and returns a state, denoted by δ .
Extended transition function : Describes what happens when we start in any state and follow any sequence of inputs ,means is a function that takes a state q and a string w and returns a state p (the state that the automaton reaches when starting in state q and processing the sequence of inputs w).  denoted by ˆδ .
in simple term : transition function takes two parameters: a state and a symbol , while extended transition function takes a state and a string.

Example of transition function :

Example of extended transition function :


Would creating a complete computer simulation of the human brain prove the Church-Turing thesis?

How would you prove that the machine is faithfully simulating a brain? How would you prove that it doesn't matter if you simulate my brain or your brain or somebody else's brain?

Church–Turing isn't something that can be proven. It's essentially just the statement that Turing machines correspond to the intuitive notion of algorithm and that just isn't a statement of mathematics. The Turing machine is the definition of computability; Church–Turing is essentially the claim that we picked the right definition, in the sense that choosing any of the reasonable alternative definitions would give exactly the same notion of computability.


Find a path from s to t using as few red nodes as possible

To solve this, you need to use $BFS$. But first, manipulate $G$ so that the path will always favor blue vertices.

The solution has 2 parts:

Use $DFS$ on blue vertices only, to find all all-blue connected components. Let's denote each such component by $v'$. Now, each blue $v \in v'$ will be "compressed" to a single vertex $u$, and an edge $(u,x)$ will be added for every $x \in N(v')$.
Note any such $x$ is necessarily red.
This step costs $O(V+E) = O(E)$, since $DFS$ is $O(V+E)$, and you have at most $V$ blue vertices, which make no more than $E$ new edges to add.

Step 1 means all paths that are blue-only will be free. On the new graph, the $BFS$ will only consider the edges which pass through a red vertex.

Use $BFS$ from $s$. That length of the path to $t$ will essentially be the shortest path under the constraint of least red vertices in the path.


In practice, to prove an algorithm you should search a good invariant property for each loop. For example, if you compute in a given order the sum of $n$ integers with a for loop (indexed by $i$), the invariant could be : "At the end of an iteration, the $sum$ variable contains the sum of the $i$ first values". It's  invariant over iterations number and always true, it's easy to prove this by recurrence on the iterations number. Afterwards you can easily conclude that, at the end of the loop, $i=n$ and thus that $sum$ is the expected sum.

Then, there is several levels of strictness, but for simple algorithms we can generally conclude promptly since the correction of the algorithm becomes almost always trivial with all the loops invariants. A very classical approach is to prove before that the algorithm finishes and after that the algorithm is correct when it ends. For complete examples you can look here. For more subtil algorithms, you can also need some mathematical theorems which provide some links beetween objects.

Your example is very close to Misra-Gries algorithm. You can look for the proof of the Misra-Gries algorithm and try to adapt it or you can try to bound the number of times the count of the most frequent number is decreased.

In general, there isn't a systematic way to find if an algorithm produces the expected output or not. Indeed, this systematic way would be an algorithm and such an algorithm can't exist (Rice's theorem).


What is the term for two file formats that describe the same amount of information?

I think that many programmers would look at it in terms of the conversions between the two formats, and say that each format can be converted to the other losslessly, and that it's possible to make a round-trip without losing any data. It's not a standard usage, but if you said that the two formats were round-trippable wrt each other, you would probably be understood. That said, you should still explain what that means!


Doubt regarding Cantor's diagonalization argument

There are several issues with your question but perhaps I can clarify some issues.

First off you assume $f(1) = 1.999...$ and also that no $x \in \mathbb{N}$ exists such that $f(x) = 2$ but that's a contradiction in terms because $1.999... = 2$ and thus $f(1) = 2$.

Why does $1.999... = 2$? Well there's an easy answer but not fulfilling answer and a more complicated answer that I find satisfactory. The easy answer is that $1 = \sum_{i=1}^{\infty}9*10^{-i}$ (the general form $(N - 1)*N^{-i}$ holds for all $N$) and $0.99...$ is definitionally $\sum_{i=1}^{\infty}9*10^{-i}$

A more satisfactory answer comes from understanding the representation of real numbers as you would in an analysis class and understanding when we define two real numbers to be equal. There are many different representations and I'll get details wrong here if I try and give you a precise example but the basic idea of most representations is to represent a real number as a sequence (sometimes its not a sequence but generally) of finite (generally rational) approximations. So $[1/1, 1/1, ...]$ is a real number representing 1.0 and $A = [9/10, 99/100, 999/1000, ...]$ is another that as we shale see is equivlent. Notice that the terms in that are the finite sums of $\sum_{i=1}^{\infty}9*10^{-i}$. We define the summation to be the sequence of its finite summations. If the sum converges then this defines a valid real number. Why does $[2/1, 2/1, ...] = [19/10, 199/100, ...]$? Because for any $\epsilon > 0$ I choose you can find an $N$ such that the difference of the $N$th elements of each sequences is within $[-\epsilon, \epsilon]$ or in a nutshell, the approximations become arbitrarily close. Take this paragraph with a grain of salt though, I'm being handy wavy and imprecise.

The traditional proof of cantor's argument that there are more reals than naturals uses the decimal expansions of the real numbers. As we've seen a real number can have more than one decimal expansion. So when converting a bijection from the naturals to the reals into a list of decimal expansions we need to choose a canonical choice. The axiom of choice just lets us do this for free but it sounds like your book tried to do something different. It isn't clear to me what your book did exactly from your description. Here's a potential way but it relies on further knowledge of reals and decimal expansions.

Take for granted that only the rationals with terminating decimal expansions (e.g. not 1/7 or 1/3 but 1/2 = 0.5 and 1/8 = 0.125 etc.. are valid) have two representations. Then its clear that every real number has exactly one non-terminating representation. So for our decimal expansions if we restrict ourselves to the non-terminating expansions we have no ambiguity.


Lower bound for sorting n arrays of size k each

For the first part, as the comments suggest - observe that there are $k!^n$ possible permutations for the inputs - indeed, every array has $k!$ permutations, and there are $n$ arrays, so you have $k!$ options for the first array, $k!$ for the second, and so on.

So the height of a decision tree is
$$\log (k!^n)=n\log (k!)\in \theta(nk\log k)$$
So you need at least that many comparisons in order to determine a single leaf.

For the second part - the argument you suggest is quite close to a formal explanation.
The lower bound of $\Omega(k\log k)$ is for comparison-based algorithms that compare elements in the array. When you have several arrays, then it is not justified to assume that sorting them is equivalent to sorting each one independently.

A-priori, it may be easier to sort them by comparing elements between the arrays. But the lower bound on sorting does not utilize such a setting, so it is not directly relevant for this problem.

In my opinion, this is as formal as you can get without formally defining what a comparison-based algorithm actually is. To define the latter, you need to formally model the computational model you use (which would be a sort of pointer-machine), and this is unlikely to result in any insights other than what you already mentioned.


Relation between space and time complexity for machines with write once read many (WORM) memory

What are the keywords to google for available material related to these questions?

The Wang B-machine is a very simple Turing machine with only WORM memory. A Turing machine with only WORM memory is commonly referred to as a "non-erasing Turing machine".

  What is known about the relation between space and time complexity for machines with WORM memory?

Let's assume a Turing machine with $q$ internal states and a binary tape alphabet.
If the machine halts after $t$ steps, having written $m$ marks on the tape and "visited" $p$ positions of tape, then $t \leq (m+1) \cdot pq$. The reasoning behind this bound is simple. As long as the machine doesn't write a new mark, there are only $pq$ distinct configurations. As the machine didn't cycle, it can have taken at most $pq$ steps between two write events, and there were only $m$ such write events.

  Do we known whether the time complexity will remain the same, if a small (for example C*log(WORM memory)^n) amount of normal memory is added?

Already Wang himself showed that a non-erasing Turing machine can simulate a normal Turing machine with only a polynomial slowdown. It was shown recently that the same is also true for the Wang B-machine. Hence it's not really interesting to investigate the change of time complexity when adding a small amount of normal memory to the machine. It would be more interesting to investigate (for different algorithms) how much the normal space complexity can be reduced by allowing for a separate non-erasable space complexity. Not sure how to apply this to pure functional programming.


Linearithmic lower bound for 1-D "distinct" closest pair of points problem

Given $n$ integer points $p_1,\ldots,p_n$, not necessarily distinct, consider the set of points $2np_1+1,2np_2+2,\ldots,2np_n+n$. The new points are distinct by construction, and the minimal distance is smaller than $n$ iff the original points were not distinct. So an algorithm for your problem can be used to solve element distinctness.


for the max flow problem you should remove the self loops and solve it. self loops don't effect on final solution because when there exists a loop on a vertex, it means a flow from the vertex (with an arbitrary capacity) goes on pipe that connect to itself, it means the flow doesn't waste, it just return to the vertex. it's like you connect a water hose from a tank to itself. you don't limit the input flow to the tank or output flow from it. so you can ignore self loops and solve the problem.


If I am right, the configuration below leads to a 7 blocks greedy solution (on the left). By symmetry, all four directions.

But there is an 8 blocks solution (on the right).

The problem with a greedy approach is that "consuming" a block can destroy two other possible blocks, and have a negative impact.

Repeating the search in different directions will not fix this, as it is possible to build symmetric patterns that result to the same behavior in all directions.


Modeling the problem of finding all stable sets of an argumentation framework as SAT

Finding a stable argument set is equivalent to finding an independent set in the directed graph of argument attacks, with the added restriction that some member of the set must be adjacent to each vertex in the graph not in the independent set.  The problem is at least as hard as the indepependent set decision problem and is thus NP-hard.  The decision version of the stable argument set problem is reducible to Boolean SAT as follows:

Input: Given a set of $n$ arguments $ARG_{1}$ to $ARG_{n}$, let the SAT propositional variable $ATTACK_{i,j}$ be true if $ARG_{i}$ attacks $ARG_{j}$.

Output: Let $INDSET_{1} ... INDSET_{n}$ be a new set of propositional variables. $INDSET_{i}$ will be true in the SAT solution iff $ARG_{i}$ is part of the stable set found.

Generating the clauses:

For every pair of variables $INDSET_{i}$, $INDSET_{j}$, add clauses that require

$\overline{(INDSET_{i} \land INDSET_{j})} \lor (\overline{ATTACK_{i,j}} \land \overline{ATTACK_{j,i}})$.

These clauses prohibit any stable set argument from attacking another.
Let $NEEDATTACK_{1} ... NEEDATTACK_{n}$ be a new set of propositional variables.  For each $INDSET_{i}$ variable, add clauses that require

$INDSET_{i} \oplus NEEDATTACK_{i}$

These clauses record which arguments must be attacked by the stable set arguments.
Let $GOTATTACK_{1} ... GOTATTACK_{n}$ be a new set of propositional variables.
For each $GOTATTACK_{j}$ variable, add clauses that require

$GOTATTACK_{j} = (INDSET_{1} \land ATTACK_{1,j})$ $\lor$ ... $\lor$ $(INDSET_{n} \land ATTACK_{n,j})$

These clauses record which arguments have been attacked by the stable set arguments.
For each $GOTATTACK_{i}$ variable, add clauses that require

$NEEDATTACK_{i} \oplus \overline{GOTATTACK_{i}}$

These clauses require that every argument that needed to be attacked by some stable set argument was in fact attacked.

The Boolean expressions can be converted to circuits and from there to CNF using Tseitin transformations.

To obtain all the stable sets, when the SAT solver returns a set of $INDSET$ variables, you must construct a CNF clauses that forbids that solution and append it to the CNF formula.  Rerun the solver and it will either find a new solution or report that the formula is now unsatisfiable.  If "unsatisfiable" is reported, then you know you've found all the stable sets.  If a new solution is found, construct another CNF clause to forbid that solution, append it to the formula and run the solver again.


Nondeterminism is not about tape or space. It is just a computational model.

One way of thinking of how a nondeterministic TM works is parallel computation. Given an input $x$, a nondeterministic TM may start many parallel (branches of) computation and wait for answers. If all branches terminate then the whole computation terminates. In addition if at least one of them  terminates with YES then the TM accepts the input. In particular a nondeterministic TM may run exponentially many branches at the same time.
However a deterministic TM is not allowed to run more than one process (branch) at the same, so less powerful in terms of time. But in terms of decidability they are equivalent.

For example consider 3SAT problem with variables $x_1, \dots, x_n$. Then on nondeterministic TM we can check all $2^n$ settings of the variables at the same time, while on a deterministic TM we will have to check each settings one by one in sequence.

NOTE: unlike a deterministic TM a nondeterministic TM is a hypothetical abstract model which is not something we use in our everyday life.

Definition of space complexity for nondeterministic Turing machines:

  If $M$is a nondeterministic TM where all branches halt on all inputs then its space complexity is the maximum number of tape cells it scans on any branch of its computation.

In particular if a TM scans at most $O(log(n))$ working tape cells on every input of length $n$ then we say its space complexity is logarithmic. It also worth noting that requiring $O(log(n))$ space does not restrict running time. A TM may decide in exponential time but still use logarithmic space.

Typically, when dealing with sublinear, $log(n)$, space bounds we use Turing machines with two tapes: input read only tape, and working tape which contributes to space complexity.

Then formally $L = SPACE(log(n))$. $L$ is the class of languages that are decidable in logarithmic space on a deterministic TM. That means that a deterministic TM decides using no more than log space. If we switch from a deterministic TM to a nondeterministic TM then we have $NL = NSPACE(log(n))$, that is, the class of languages that are decidable in logarithmic space on a nondeterministic TM.

Thus, meaning, or more formally members, of $NL$ complexity class is all languages decidable:
1) on nondeterministic two tape TM
2) using at most $ O(log(n))$ space on work tape.

Example: the language of the problem deciding for a graph whether or not there is a simple path between nodes $s$ and $t$. This language is in $ NL$ class, but if it is in $L$ class is unknown.


You can't guarantee that $A$ can also be solved in time $O(n\log n)$ because the reduction from $A$ to $B$ might require more time than that (for example, $n^3$ steps).


Exponential example for simplex used in SMT solvers

Here, you can find hard examples for DPLL.
http://www.ioc.ee/~tarmo/tday-torve/itsykson-slides.pdf

For instance, it can be very slow for Tseitin formulas and for some unsatisfaisable formulas (it will try many solutions).

I hope it will give you some hints :)


Even if decision is easy, the counting problem #HORNSAT is #P-complete [1], the counting analog of NP-completeness problem. Thus it is very unlikely it has a polynomial time algorithm (for example, if $P \neq NP$ then #HORNSAT has no ptime algorithm).

See [1] for a dichotomy characterizing the clause restrictions leading to tractable instances of #SAT. More precisely, it is shown that the only restriction of clauses that gives tractable instances for #SAT are the clauses of the form $x_1 \oplus x_2 \oplus ...\oplus x_n = 0$ where $\oplus$ is the sum modulo $2$. The other restrictions (#2-SAT, #HORNSAT, ...) are all #P-complete.

[1] Nadia Creignou, Miki Hermann: Complexity of Generalized Satisfiability Counting Problems. Inf. Comput. 125(1): 1-12 (1996), http://www.sciencedirect.com/science/article/pii/S0890540196900164?via%3Dihub


Here is the original exercise.

  Suppose we have an algorithm whose running time is $\Theta(n(t + n^{1/t}
))$, where $n$ is the input length and $t$ is a positive parameter we can choose arbitrarily. How should $t$ be chosen (depending on $n$) such that the running time (as a function of $n$) has a minimum rate of growth?

As others have pointed out, you misunderstood the exercise. The phrase "rate of growth" is indeed somewhat misleading.

The rate of growth of the running time of an algorithm refers to the growing behavior of the running time when the input length goes bigger and bigger. It is almost universal trend that the running time of an algorithm becomes longer when the input length becomes bigger. In particular, it is true asymptotically for the current case if we assume $t$ is a constant.

In order for the running time to have a minimum rate of growth everywhere or in average, we need the running time be the minimum when the input length is sufficiently large, since the running time for input length $n$ is the sum of all differences between the running time for input length $i-1$ and $i$, where $i$ ranges through $n_0$, $n_0+1$, $\cdots$, $n$ for some small constant $n_0$ and the running time for input length $n_0$. So, the requirement "the running time (as a function of $n$) has a minimum rate of growth" in general is just "the running time (as a function of $n$) is the minimum", as we ignore the contribution of the usually rather short running time for the small input length $n_0$. The exercise would have been clearer had it said "... such that the running time is the minimum as a function of $n$".

"How to select $t$ such that the running time has a minimum rate of growth?" The definition of $\Theta$ tells us that the running time is proportional to $n(t+n^{\frac 1t})$ within a constant factor. This question requests you to select $t$ as a function of $n$ such that, $n(t+n^{\frac 1t})$ as a function of $n$ is as small as possible. Or, once we have pulled out the factor $n$,
such that, $(t+n^{\frac 1t})$ as a function of $n$ is as small as possible

Now that we have understood the exercise, the real task is how to answer that question.

Note that $t$ increases as $t$ increases. On the other hand, $n^{1/t}$ decreases as $t$ increases, assuming $n>1$.

If we let $t=1$, then $t+n^{\frac 1t} = 1 + n$. If $t=n$, then $t+n^{\frac 1t}=n+n^{\frac 1n}= n+o(1)$. In either case, either $t$ or $n^{\frac 1t}$ is rather substantial. If we select $t$ to be some value between $1$ and $n$, we could possibly make both $t$ and $n^{\frac 1t}$ much less substantial, thus making their sum much smaller. The relevation is that we could choose $t$ such that $t=n^{\frac 1t}$ so that none of the two is particularly large.

Suppose $t_0$ as a function of $n$ satisfies $t_0=n^{\frac1{t_0}}$. Then we have
$$t_0\le\min_{t>0}t+n^{\frac 1t}\le 2t_0$$

It is an easy exercise for the interested readers to prove the above formula.

The above formula indicates that we can use binary search to find or approximate the wanted value of $t$. Fixing $n$, we will start with interval $[1,n]$. Check the middle value $t =(1+n)/2$. If $t<n^{\frac1{t}}$, replace the left endpoint 1 with $(1+n)/2$ so that we will continue with interval $[(1+n)/2,n]$. Otherwise, replace the right endpoint n with $(1+n)/2$ so that we will continue with interval $[1, (1+n)/2]$. Repeating this binary search until the interval becomes small enough. We will use either of its endpoints as the wanted value of $t$.

The above gives a simple algorithmic way to chose $t$ to make $t+n^{\frac1n}$ reach the minimum within a factor of 2. We can do better following the steps given by D.W.

  You want to find $t$ that minimizes $f(t)=t+n^{1/t}$.  This can be done by setting the first derivative to zero.  In particular, $f'(t) = 1 - (n^{1/t} \log n)/t^2$; setting this to zero yields $n^{1/t} \log n = t^2$, i.e., $$(\log n)/t + \log \log n = 2 \log t.$$

Now the problem is how to solve the above equation for $t$. Note the left-hand side is a decreasing function in $t$ and the right-hand side is an increasing function in $t$. If $t=1$, the left-hand side is greater than the right-hand side. If $t=n$, the right-hand side is greater than the left-hand side. So there is a unique solution for $t$, which is between 1 and $n$. We can use binary search to find that solution.

A couple of related results are listed here just for fun.

The selected $t$ is equal to $\frac{\log n}{\log\log n}$ asymptotically..

The minimum running time is $\Theta(\frac{n\log n}{\log\log n}).$


A tree data structure is a natural way to store this data.  It supports all of the operations you listed.


How to calculate Kolmogorov Complexity if we have access to an Oracle for the HALT Problem

Here is the idea. Given a string $x$ whose Kolmogorov complexity you want to calculate, go over all programs in non-decreasing order of length. For each program $p$, check using the oracle whether it halts, and if so, check whether it outputs $x$. If it does, the Kolmogorov complexity is the length of $p$. Otherwise, go to the next program. Eventually you will find a program computing $x$. The program you will find is a shortest one since we go over all programs in non-decreasing order of length.


Convention of a += operator in pseudocode

The +=et al are C shortcuts, adopted by many languages. Most anyone should understand them.
Then again, this is (pseudo)code, you certainly can make up you own variant. Just make sure to define clearly what any not-so-standard constructions mean (I'd go for += and so on, but then again, I'm a C fan...). But make sure to be consistent, i.e., use = for assignment and += for your operation, don't mix it with e.g. $\leftarrow$, and state that you'll use C notation for assignments.
Whatever you do, always keep in sight that the objective is understanding by your gentle reader, not extreme rigour or algorithmic details.


How to correctly define the ratio of an approximation algorithm?

No, your definition isn't very useful. A $\gamma$-approximation algorithm is an algorithm that produces a solution which is not too bad compared to the optimal solution. In contrast, under your definition you are guaranteed to produce a solution which is somewhat worse than the optimal one.

Let's take as an example the maximum clique problem. Here is a $\gamma$-approximation algorithm for maximum clique under your definition: output an empty clique. This works for any $\gamma < 1$.

I suspect that what you intended to capture was that $\gamma$ is the "tight" approximation ratio of the algorithm. That is, you want $\gamma$ to be the supremal $\gamma$ such that the solution $S$ produced by the algorithm always satisfied $|S| \geq \gamma |OPT|$.

I just gave one definition of the tight approximation ratio, but here is another (equivalent) one. We say that $\gamma$ is the tight approximation ratio of the algorithm if the algorithm is a $\gamma$ approximation (under the usual definition), and for every $\epsilon > 0$ there is an instance on which the solution satisfies $|S| \leq (\gamma + \epsilon)|OPT|$. It's important here to include both parts of the definition.


How do non-deterministic algorithms work on current machines?

Is it right that non-deterministic algorithms do not rely on any randomness whatsoever?

Yes and no. Non-determinism just means that there in the computation there is a choice that needs to be made based on information not available to the algorithm. There are multiple solutions to this choice, one of which is randomness - for example in random pivot quicksort.

I had thought that non-determinism was more of a concept than one that could be put into practice at this given moment - so what exactly are the 'non-deterministic algorithms' on the Internet, such as on the Wiki page above?
Furthermore, D. Harel's book Algorithmics introduces non-determinism in that whenever the machine must make a choice between two or more branches to next states, it ALWAYS picks the one which will lead to an accepting state, if there are any accepting states. In this way, how can non-deterministic algorithms exist on current machines, as they don't have 'insight' as to what will happen further down the line?

There are four main approaches (to my knowledge) for dealing with non-determinism: parallelism, randomness, backtracking and superstates.

Parallelism: whenever a choice needs to be made split the program and investigate all choices in parallel.

Randomness: use randomness to choose a single choice out of all.

Backtracking: deterministically choose a choice (e.g. the first one) and continue computation with that choice. When that choice wasn't correct go back and choose the second options, etc.

Superstates: track all possible states the program can be in, and whenever input is received apply that input to all possible states, merging states and rejecting states eagerly.

Note that not all approaches are always valid and/or feasible. Parallelism is rarely feasible as it requires a lot of physical resources and not much non-determinism, randomness is only correct if each choice is correct, and it's just a matter of performance.
To directly implement a NFA either 3 or 4 is used. Another example of 4 are full CFG parsers that can handle ambiguity such as an Earley parser.

Finally, does converting from a non-deterministic FSM to a deterministic FSM take an exponential amount of time?

By necessity, because the resulting output can have an exponential number of states.


Is there an example of a recursive language which is not context sensitive?

Here's a more formal proof, by the standard trick of diagonalization
(it must be folklore, but I saw it recently here)

Let $G_1, G_2, ...$ be some enumeration of context sensitive grammars (convince yourself that there are only countable many of them; Why can they be enumerated?),

Let $x_1, x_2, \ldots,$ be enumeration of $\Sigma^*$ (i.e., $x_1=\epsilon$, $x_2=0$, $x_3=1$, $x_4=00$, etc. in the case of binary alphabet).

Consider the language:

$$L = \{ x_i \mid x_i \notin L(G_i)\}.$$

Claim 1 $L$ is not context sensitive: if it was, there was a specific $G_j$ generating it, but $x_j\in L$ while $x_j \notin G_j$.

Claim 2 $L$ is decidable: given $x_i$ we just check if $G_i$ generates it (this problem is known to be PSPACE complete, thus decidable).


What functions can combinator calculus expressions compute?

To get the ball rolling, and in hopes of other people giving deeper and more detailed answers on the structure of the $\lambda$-definable functions $L'\to L'$, let me cite Corollary 20.3.3 from Barendregts' The Lambda Calculus, Its Syntax and Semantics (aka "the bible").

  Corollary 20.3.3: The function $\delta:L'^2\to L'$, defined by
  $$ \delta(M, N) = \cases{\mathrm{True}\mbox{ if }M=_{\beta\eta}N\\ \mathrm{False}\mbox{ otherwise}}$$
  is not definable in the untyped $\lambda$-calculus, i.e. there is no term $D$ such that
  $$D\ M\ N =_{\beta\eta} \delta(M,N)$$
  for all $M,N\in L'$.

The proof involves considerations on Böhm trees which give a rather strong characterization of the possible "actions" of arbitrary lambda terms on normal forms. In particular, for any non-constant closed term $F$, on can find $n\in\mathbb{N}$ and $P_1,\ldots,P_n$ such that
$$ F\ x\ P_1\ldots P_n =_{\beta\eta} x\ Q_1\ldots Q_k$$

For some $k$, $Q_1,\ldots,Q_k$. This drastically constrains the possible forms of a hypothetical $D$ that implements $\delta$, showing with a little work that such a $D$ cannot exist.


We usually only care about the worst-case complexity of algorithms. An $O(n)$ algorithm is usually asymptotically optimal (assuming $n$ is the input size), since most functions require you to read the entire input in some cases.

Another example in which you can prove asymptotic optimality is comparison-based sorting algorithms. A comparison-based sorting algorithm is a sorting algorithm whose only access to the data is a comparison oracle, which compares to data items. Any such algorithm must make $\Omega(n\log n)$ oracle queries in the worst case. Therefore a comparison-based sorting algorithm running in time $O(n\log n)$ is asymptotically optimal.

In most cases, however, we cannot prove that a given algorithm running in superlinear time is optimal, since we don't know how to prove running time lower bounds on general computation models. However, in some cases we can prove such lower bounds conditionally, that is, assuming some widely believed hypothesis. This is known as fine-grained complexity theory, and it indicates (conditionally) that the best algorithms for many problems are indeed asymptotically optimal.


What's the difference between Process Context and Process Control Block?

I think you are confusing the concepts of threads and processes.

Threads (aka tasks)
Processes do not get pre-empted, only threads get pre-empted.
A process can contain one or more threads which may run concurrently and/or time-sliced.
As long as there are current threads in the process (some or all of which made be paused) it is said to be running. When the last thread ends the process terminates. When a process is terminated forcibly by the operating system all its threads are terminated as well.

Process control block
The Process Control Block is the collection of information needed to define a process. In modern OS'es processes are (more or less) isolated and run in their own memory space.
The term process control block is not actually in use by any operating system and the various info needed to control a process is not actually stored in a single structure, as such the term is not all that helpful.

Threads are confined to a process
All threads inherit their properties from the process and have little room to alter these. It is the programmer's responsibility to make sure threads do not step on each others toes. Unlike processes there is no isolation between threads inside a process other than a dedicated stack and thread local storage.

Thread context
A thread context is not part of the PCB.
A thread context is simply a dumb of the current machine state (mostly CPU registers) before the thread was interrupted, in additon every thread gets its own dedicated stack and thread local storage.
The context a thread runs under can only be understood in terms of the process state (as defined in the PCB).
E.g. memory addresses inside process X do not make sense outside that process.

Process isolation
I've never heard of process boundary. I'm assuming you mean process isolation.
Every process runs in its own virtual address space and gets access to virtual resources (such as the screen) in such a way that one process cannot access the resources of another process.
In most operating systems this isolation is imperfect and resources in use by other applications can be easily accessed especially when processes have been started with equivalent attributes (e.g. same user id).

  how is the PCB affected during a context switch (if at all)?

The PCB is not affected by a thread context switch.


Ambiguous grammar to equivalent unambiguous grammar

As you have observed, the only problem in the original CFG is that the string $ab$ can be generated by both $A$ and $B$.

Here is a hint. Instead of generating $ab, a^2b^2, a^3b^3,\cdots$, can you let $A$ generate $a^2b^2, a^3b^3,\cdots$ without generating $ab$?


Determine if a vertex is a part of a cycle in O(m+n) complexity

Simply apply Strongly connected components algorithm , Kosaraju's algorithm has complexity $O(m+n)$. Now, read through the SCC components and check if $v$ is part of a component with size $\geq$ 2. The second step is $O(n)$. Actually, the second step can be interleaved with the first step to get your required complexity result.

A simpler algorithm may be just to to use DFS on the graph. Have a look at Cormen's Introduction to algorithms, chapter 22. Your exact problem is solved there using DFS.


I finally finished the project. Given really short signals and a really small training set, SNNs (I used Echo State Machines and a neural form of SVM) vastly out-performed Deep Learning recurrent neural networks. However, this may be mostly because I'm really bad at training Deep Learning networks.

Specifically, SNNs performed better at classification of various signals I created. Given the following signals:

The various approaches had the following accuracy, where RC = Echo State Machine, FC-SVM = Frequency Component SVM and vRNN = Vanilla Deep Learning Recurrent Neural Network:

SNNs were also more robust to noise:

For more information, including how I desperately tried to improve the Deep Learning classification approach performance, check out my repository and the report I wrote which is where all the figures came from.

Update:
After spending some time away from this project, I think one of the reasons that RNNs do horribly at this project is that they're bad at dealing with really long signals. Had I chunked the signals together with some sort of smoothing as preprocessing, they probably would have performed better.


Quotient of languages, regular quotient and their closedness

All sources agree on the definition of right quotient: $L_1/L_2$ is the set of words which can be extended by a word in $L_2$ to become a word in $L_1$. In other words, $w \in L_1/L_2$ if there exists $x \in L_2$ such that $wx \in L_1$.

If $L_1$ is regular and $L_2$ is any language then $L_1/L_2$ is regular.

For many classes of languages, if $L_1$ belongs to the class and $L_2$ is regular then $L_1/L_2$ also belongs to the class. Examples of such classes include context-free languages and r.e. languages, but not context-sensitive languages. This is definitely the case for languages closed under homomorphism, inverse homomorphism, and intersection with a regular languages. Context-sensitive languages are only closed under $\epsilon$-free homomorphism, which is not enough here.

The left quotient is defined similarly, but we extend the word on the left instead of on the right. The notation is $L_1\backslash L_2$, but authors vary on which part is played by which language. One possible convention (used by Wikipedia) is that we are interested in words which can be extended on the left by a word in $L_1$ to become a word in $L_2$. Another convention (used by your link) reverses the roles of $L_1,L_2$. The alternate notations $L_1 L_2^{-1}$ and $L_2^{-1} L_1$ mentioned in your link are unambiguous. Note how the Wikipedia notation makes a bit more sense here: $L_2^{-1} L_1 = L_2 \backslash L_1$ per the Wikipedia notation, but not per the notation in the link.


Reduction from an assignment problem to an independent set problem: NP-hard

If you want to show that your problem is NP hard, your reduction should go in the other direction. You have to show:
$\exists L \in NPH: L \le_M yourProblem$
where $NPH$ is the Set of NP-hard languages.

Your try looks like you wan't to reduce from your problem to Independent Set.


The capacity of a deletion channel with deletion probability $p$ is still not fully understood, however it is known to be somewhere between $1-h(p)$ and $(1-p)/9$.

See a survey by Michael Mitzenmacher on deletion channels: A survey of results for deletion channels and related synchronization channels.


how does rotation works in AVL trees and what is a good way to understand it?

One needs three subtrees to describe rotation, as the operation reconnects the three subtrees of a pair of nodes, one the child of the other.

The operation can be seen as a associative property: $T_1\;p\; (T_2\; q\; T_3) = (T_1\; p\; T_2)\; q\; T_3$ of the inorder traversal of the nodes in a binary tree.

Both the left and right diagram have the inorder $\mathrm{in}(T_1)\; p\; \mathrm{in}(T_2) \; q\; \mathrm{in}(T_3)$, where $\mathrm{in}(T)$ is the inorder of subtree $T$.

It is pretty well explained at wikipedia Tree rotation, even with animated pictures.


"A good driver drives in three cars. His own car, the car behind him, and the car in front of him". (Bertold Brecht).
"Lookahead" is what you do when you drive a car. You look ahead and make decisions not just based on things around you, but also based on things ahead of you.
A parser with a lookahead of 1 makes decisions based on the current symbol and the symbol ahead of it. That often keeps it from making the wrong parsing decisions.