Any regular language upholds the pumping lemma. Hence, if a language doesn't uphold the pumping lemma, it is not a regular language. This is in fact the standard way of proving a language is not regular.

Let us choose $p$ to be the pumping length. Let's now take $0^n=1^n \oplus 1^n$, which is in $A$. This string can be decomposed into three concatenated substrings $xyz$. Since $|xy| \leq p$, we see that $v=0^k$ for some $k$ greater than 0. If we choose to pump it $i$ times, we will then obviously obtain an $x$ which is longer ($i > 1$) or shorter ($i = 0$) than the other two operands and cannot then be the result of their XOR, hence proving that the language is not regular.

However, it may be that you forgot to add some clauses to the problem statement, since this seems quite trivial. Edit: my intention was not to point out that this is easy in general, the principle itself of the proof being rather non-trivial. However, some additional clauses, such as the strings having the same length would render this sensibly harder, and it may be what the problem had in mind.


Pascal FOR loop with context free gramar

The answer depends on how you represent variables.

If there are an infinite number of variable names, the answer is no.
If there are a finite number of variable names, the answer is "yes but you never would in practice".

Here's some informal arguments for that:

For the first case, there must be some set of non-terminals which represent valid loop bodies. And for each variable, there must be a non-terminal where you can refer to that variable, and one where you can't. Because of loop nesting, this must be true for any combination of any number of variables i.e. we need a distinct non-terminal for each of an infinite combinations of allowed and not allowed variables.

But, then we have an infinite number of non-terminals, which is not allowed in a context-free grammar.

This is basically because of the "context free" part of CFG. Knowing which variables are allowed and aren't is context, which our grammars are free of.

In the case of a finite number of allowed variables, you basically model it like I said above, with a different non-terminal for each combination of variables. So in terms of computability/expressibility, you you can do it with a context free grammar, in the same way you can model your computer and its 8GB of RAM with a finite automaton. Doing so will explode quickly, and it's not the way you want to do things.


The usual trick to avoid this underflow is to compute with logarithms, using the identity $$ \log \prod_{i=1}^n p_i = \sum_{i=1}^n \log p_i. $$
That is, instead of using probabilities, you use their logarithms. Instead of multiplying them, you add them.

Another approach, which is not so common, is to normalize the product manually. Instead of keeping just one floating point number $p$, you keep a floating point number $p_0 \in [1,2)$ (say) and a negative exponent $x$ such that $p = p_0 2^x$. After each operation you normalize the resulting number.


Data types for storing arbitrarily much information

Yes, you can create bigger and bigger variables to store big integer. There are many libraries that provide that functionality. For example BigInteger in Java. The problem with using big integer is that it makes program slower as more instructions are required to perform operations such as addition. Moreover, using a bigger representation will consumes more memory.


Difference between bit times and milli seconds

The propagation delay is time it takes to transfer one bit from sender to receiver.
200 ms would be such time, for Bit Times it is the duration of given bits in the medium, the first bit of a header reaches the receiver before the last bit was transmitted by the source (here also given 200).


Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$

Hint 1: What happens when $k=2$?

Hint 2: Use a reduction from $\text{ALL}_{\text{TM}}$.


In predicate logic, is the "environment" only needed when free variables are present?

It is not so that the model alone allows you to make inferences and that you don't need an environment at all; it is rather that, if no free variables occur, then you may as well start with an empty environment. Quantifiers modify the current environment, so you do need one. However, if there are no free variables around, then any of the assignments in the initial environment will not be used, and all variable values will come from the quantifiers anyway. Therefore, by trimming unnecessary assignments in the initial environment, you get an empty one.


It is simpler than what you think. You don't even need a Turing machine that writes to the tape.

Here is a Turing machine whose final state would be $YES$ if the string (in tape) contains an even number of 1's, and in $NO$ if the string contains an odd number of 1's, assuming the string marks its end with a #, and it starts from left to right.

Let $ M = (Q, Γ, Σ, δ, s, B, F)$ be a Turing Machine with the definition

$$Q = \{read_0,read_1,YES,NO\}$$

$$Γ = \{1,0,\#\}$$

$$Σ = \{\}$$

$$F = \{YES,NO\}$$

$$s = read_0$$

$$B=\#$$

$δ$ is given by $δ_{q\ t} = ( move \,\ next\ stage)$ where $t$ is the tape symbol that it reads, and $q$ represents each state:

$$δ_{read_0\ 0} = (R,read_0)$$
$$δ_{read_0\ 1} = (R,read_1)$$
$$δ_{read_0\ \#} = (0,YES)$$
$$δ_{read_1\ 0} = (R,read_1)$$
$$δ_{read_1\ 1} = (R,read_0)$$
$$δ_{read_1\ \#} = (0,NO)$$

Basically what it does is that if it see $1$ it alters between $read_0$ and $read_1$ states. And if it is in $read_0$ state and sees $\#$, which means the string ended, it would go to the final state, $YES$. If it is in $read_1$ and sees $\#$ it would go to $NO$.

So if the string contains three $1$s, the states change in this way $$read_0 \rightarrow read_1 \rightarrow read_0 \rightarrow read_1 \rightarrow NO$$ implying that it doesn't contain an even number of 1s.


My code works, But how do I make this code run in a deterministic time?

Your code is determinstic: it uses no randomness. But I assume you want the running time to be essentially independent of the input.

Assuming I've understood the problem correctly, you're dropping a ball from height h and, when dropped from height x, it bounces to height x*Bouncefactor. You want to know how many times it passes through the height you're calling window.  Your approach is, essentially, to simulate the bouncing ball and count.

Instead of doing that, you should just calculate how many times the ball bounces before it's at height less than window.  This is the least k such that h * Bouncefactor^k < window, so you just need to solve this equation and then convert the number of bounces into the number of times that the ball is seen.


NFA string acceptance with loop of epsilon transitions

An algorithm for testing whether an NFA accepts a string has the following specification:

Input: NFA $A$ and word $w$
Output: Yes if $A$ accepts $w$, No if $A$ doesn't accept $w$

In particular, the algorithm must always terminate. What algorithm you use is up to you.

One way to overcome the problem of $\epsilon$-loops is to compute, for each prefix of $w$, the set of states that the NFA can reach. To this end, for every state $q$ we define $N_\epsilon(q)$ as the set of states reachable from $q$ via (possibly zero) $\epsilon$-transitions. You can compute $N_\epsilon(q)$ using a graph traversal algorithm such as BFS/DFS.

Given a word $w = \sigma_1\ldots \sigma_n$, we define the set of states $R_i$ reachable after reading the first $i$ letters as follows:

$R_0 = N_\epsilon(q_0)$.
For $i = 1,\ldots,n$, $R_i$ is the union of $N_\epsilon(q')$ for all $q' \in \delta(q,\sigma_i)$ and all $q \in R_{i-1}$.

The NFA accepts $w$ iff $R_n \cap F \neq \emptyset$, that is, if $R_n$ contains an accepting state.

In your example, $N_\epsilon(1) = N_\epsilon(2) = \{1,2\}$. The fact that the graph induced by the $\epsilon$-transitions contains directed cycles is not problematic at all for this approach, since we only care about which states are reachable from which.


There is just one loop in for, so the number of steps here will be proportional to n not n^2. The outer loop is running in a n proportional number of steps too. So The complexity of your algorithm is n^2.
N.B. : When speaking complexity, you don't have to state (n^2 + n) / 2,just say n^2 because they are the same for big ns.


How to teach random number generator algorithms?

So much depends on the language or library you are using. If the tool you are using allows feeding a specific seed I would start by demonstrating how using the same seed gives the same set of random numbers each time. If not and the tool uses the system time as the seed, as many do, then create several random data sets if a very tight look and show how they are the same.

This cre3ating several random sets in a tight loop is something students often do by accident BTW. It gives them no end of trouble as they see identical numbers for all of them.

Then demonstrate how the same code gives different (from the first example) random numbers when used with a different seed.

With your example, using a random number from the same seed would return the same word every time. Using a time based seed should normally return a different word each time.

BTW random.org is a useful/interesting site on the topic. They go into some detail on random and pseudo-random numbers at https://www.random.org/randomness/


How should I describe the relationships between type expressions?

The set-theoretic intuitions can make sense in the semantics, especially in the context of realizability semantics (where types are interpreted as sets of terms). In this case, the polymorphic type $\forall \alpha. \mathrm{Maybe}(\alpha)$, written Maybe a in Haskell, intuitively corresponds to the intersection over every type $T$ of the
elements of $\mathrm{Maybe}(T)$. Or in other words, $⟦\forall \alpha. \mathrm{Maybe}(\alpha)⟧ = \bigcap_T ⟦\mathrm{Maybe}(T)⟧$, where $T$ ranges over the semantic domain (and elements of the semantics are injected into the syntax).

On the other hand, set-theoretic intuition does not really make sense on the side of the type system, because standard set operations are not allowed. For instance, it is not possible to refer to the intersection of two types in the syntax (at least when you are not working with intersection type systems, and I don't think this is the case in Haskell). However, one operation on types that is primitive in all type systems with polymorphism is instantiation. This corresponds to the elimination rule for the universal quantifier (or polymorphism), and it states that if you have a term $t$ of type $\forall \alpha, \mathrm{Maybe}(\alpha)$ then the term $t$ can be seen as an element of type $\mathrm{Maybe}(T)$ for any type $T$, for example $\mathrm{Integer}$.


The language $L$ is not regular, but $L_2$ is. In fact $L_2 = \{a,b\}^*$.
Indeed if $w \in L_2$, then by definition, $w$ is suffix of a word of $\{a,b\}^*$ and thus $w \in \{a,b\}^*$. Thus $L_2 \subseteq \{a,b\}^*$. To prove the opposite inclusion, consider a word $w \in \{a,b\}^*$. Let $p$ be a prime such that $p \geqslant |w|$ and let $u = a^{p-|w|}w$. By construction, $|u| = p$,
$u \in \{a,b\}^*$ and $w$ is a suffix of $u$, and thus $w \in L_2$.


Programming a genetic algorithm with a non-fixed size

There are plenty of possibilities:

Add/remove a symbol at the end with probability $c$.
Add/remove $k$ symbols at the end with probability $c \cdot 2^{-k}$.
For every symbol, remove it with probability $c_1$;
for every gap, insert a symbol with probability $c_2$.
For every symbol $a$, convert it to $a^k$ with probability $c \cdot 2^{-k-1}$.

And so on and so on. Basically, whatever works for you is good. Without any knowledge about the function you are trying to optimise, it is impossible to guess which strategies make more sense than others.


Why isn't the search space size of TSP $(n-1)!$ instead of $n!$?

The search space has size $(n-1)!$. You can see this in many ways, for example:

Each tour corresponds to $n$ different permutations, depending on the starting point.
If we start describing the tour at some point $P$ fixed ahead of time, then the tour is given (injectively) by an arbtirary permutation of the remaining $n-1$ points.

The reason that sometimes $n!$ is used is that $n!$ is shorter, and the difference between $n!$ and $(n-1)!$ is not always important.


Does $O(1) * o(1)$ equal a $o(1)$ function?

The formal proof would proceed along these lines:
Let $C$ be a constant such that $f(n)\le C$ for all $n$ (such a constant exists since $f(n)\in O(1)$).
Then
$$\lim_{n\to \infty}f(n)\cdot g(n)\le C\cdot \lim_{n\to \infty}g(n)=0$$
So $f(n)g(n)\in o(1)$.


Decision problem - vertex with path to all other vertcies

Suppose we are given a directed graph $G$ and two vertices $s,t$. Add a new vertex $a$ and an edge from $a$ to $s$. Also, add an edge from $t$ to all vertices in the graph apart from $a$.

Since $a$ has no incoming edges, if there is any vertex from which all other vertices are reachable, it must be $a$. For this to happen, in particular $t$ must be reachable from $a$. Since the only outgoing edge from $a$ points at $s$, this can only happen if $t$ is reachable from $s$. In that case, all other vertices are also reachable from $a$, via $t$, since we added outgoing edges from $t$ to all vertices apart from $a$.


Optimal prefix-free binary code with several codewords already assigned

"Ordinary" Huffman is suboptimal

Let's call a symbol "free" if it has not yet been assigned any codeword.  Here's an easy counterexample to the optimality of running the ordinary Huffman algorithm on the set of free symbols:

Suppose we have three symbols $a, b, c$, with frequencies $0.5, 0.25, 0.25$, of which $b$ and $c$ are free; $a$ has already been assigned the codeword $00$.  Then the unique minimum-size tree in which $b$ and $c$ -- the lowest-frequency free symbols -- are siblings is

  /\
 / /\
a b  c

with expected codeword length $0.5*2 + 0.25*2 + 0.25*2 = 2$, which is strictly greater than that of either of the two trees in which they are not siblings:

  /\        /\
 /\ c      /\ b
a  b      a  c

which each have expected codeword length $0.5*2 + 0.25*2 + 0.25*1 = 1.75$.


Finding a set of maximally different solutions using linear programming or other optimization technique

A heuristic, using linear programming

One approach might be to pick a random objective function, and maximize it.  Then repeat, with a different set of objective functions each time.

In other words, suppose the unknowns are $x_1,x_2,\dots,x_n$, and you have some constraints $\mathcal{C}$.  In each iteration you pick $c_1,c_2,\dots,c_n \in \mathbb{R}$ randomly, then search for a solution that maximizes $c_1 x_1 + \dots + c_n x_n$ subject to the constraints $\mathcal{C}$.

I would expect this heuristic might often find a somewhat scattered set of solutions -- not necessarily maximally scattered (maximally far from each other), but probably not too close to each other, either.

Maximizing the average pairwise L2 distance, using quadratic programming

Alternatively, use quadratic programming.  For simplicity, let's look at the problem of finding two solutions.  Suppose you want two solutions $x,y$ that are as far apart from each other as possible, under the $L_2$ norm (Euclidean distance).  Then this can be formulated as a quadratic programming problem.

Basically, you want to maximize the squared distance $d(x,y)^2 = (x_1-y_1)^2+\cdots+(x_n-y_n)^2$ between $x$ and $y$, subject to the requirement that both $x$ and $y$ must satisfy the constraints.  This is the problem of maximizing a quadratic objective function, with linear constraints -- i.e., quadratic programming.

If you want $k$ points that are maximally scattered, this is also possible.  Say the points are $x^1,\dots,x^k \in \mathbb{R}^n$.  Then you could maximize the objective function

$$\sum_{i<j} d(x^i,x^j)^2,$$

i.e., the function

$$\sum_{i<j} \sum_\ell (x^i_\ell - x^j_\ell)^2.$$

This is a quadratic function, and you have linear constraints $\mathcal{C}$ on each of the points $x^i$, so this is a quadratic programming instance.  It finds you points that are maximally scattered in the sense that the average pairwise distance is maximized.

You can also formulate a greedy variant of this algorithm, where you already have $k$ solutions, and you want to find a $k+1$th solution that satisfies all the linear inequalities and also maximizes the average L2 distance from it to the other $k$ solutions.  That too can be formulated as a quadratic programming problem.

Quadratic programming is harder than linear programming, but there are off-the-self solvers that will solve quadratic programming problems for you.

Maximizing the minimal pairwise L2 distance, using QCQP

Finally, let's say you want your $k$ points to be scattered in the sense that you want to maximize the minimum pairwise distance.  In other words, let's say you want to find the largest possible threshold $t$ such that it is possible to find $k$ points $x^1,\dots,x^k \in \mathbb{R}^n$ that each satisfy the linear constraints, and such that each pair of points is at distance $t$ away from each other: $d(x^i,x^j) \ge t$ for all $i<j$.  Then this can be formulated as a quadratic optimization program with quadratic constraints, i.e., QCQP.  QCQP is even harder, but there are off-the-shelf solvers for QCQP you could try out, too.


After an $\exists$ the period can be read as "such that".
For example,
$\exists x\in \mathbb{N}. x>4$ can be read as "there exists a natural $x$ such that $x$ is greater than 4."

After a $\forall$ it can be read as "it is the case that". For example,
$\forall x\in\mathbf{N}. x +  1> x$ can be read as "for all natural numbers $x$, it is the case that $x+1$ is greater than $x$.

Generally one can omit "it is the case that" and the sentence still works.


Prove that $r$-ary entropy $H_r(s) = H(s) / \log_2 r$

There's nothing to prove here, this follows by Definition. Assume a discrete r.v. $X$, then

$$H(X) \triangleq \mathbb{E}[-\log \Pr(X)]$$

and,

$$H_r (X) \triangleq \mathbb{E}[-\log_r \Pr(X)].$$

Therefore, the claim follows (using $E(aX)=aE(X)$ for a constant $a$). Note that in your question you use $H(X)$ as the binary entropy $H(X) \triangleq H_2(X) = \mathbb{E}[-\log_2 \Pr(X)]$, hence the multiplicative factor is $\log_2 r$.


Minimal Deterministic Buchi Automata Product

This is only a partial answer (as I believe that the state of the art is insufficient to answer your questions completely - I am happy to be proven wrong here), but I hope that it helps you anyway.

First of all, note that when taking the conjunction of two automata with $n$ and $m$ states, the result having $nm - o(n) - o(m)$ states cannot be avoided. This follows pretty much from the fact that for deterministic automata over finite words, such a blow-up can also not be avoided. At the same time, we have an upper bound on $2nm$ many states for the product. For automata theory researchers, this is actually pretty tight.
The constructions given in the Vardi paper and the one given in the slide set you referred to are slightly different. Both have counters for keeping track of for which automaton an accepting state has to be visited next. In the slide set construction, after both automata have seen accepting states, goes to the counter value of 3, where in the product an accepting state is visited and then switches back to 1. Vardi (who attributes the construction to earlier work by another researcher) does it differently. In a nutshell, the idea is to recycle the accepting states from the factor automata, and to switch the counter only after an accepting state has just been seen. In this way, the "3" counter value is not neccessary, and the construction still works anyway.
As far as I know, there is no research that answers your questions completely. But you may be interested in Schewe's paper that shows that minimizing deterministic Buchi automata is NP-hard (The ArXiV version of the paper can be found here). I would not be surprised if you could base a proof that your problem 3 is NP-hard on his proof ideas. For the case that the factor automata are not already minimal, this proof would be trivial, but I assume that you want to start with minimally-sized automata.


sPaz, your answer in the comment is on the right track.

I'll give you some more hints.

Since $L$ is RE, as you said, we have a TM that accepts it. Let's call it $R$.
Now, we can run $M_i$ on $x$ for any $M_i$ that is being accepted by $R$.
The question is, what happens if $M_i$ is not accepted by $R$ (and in fact, $R$ goes into a loop)? Also, what happens if $M_1$ is accepted by $R$, but $M_1$ goes on an infinite loop on input $x$?

The standard technique of "running in parallel" (dovetailing) should help you to complete your proof. In more details:

   We have a counter $i$. We run $i$ steps of $R$ on any machine $M_j$ such that $\langle M_j \rangle < i$. We keep a list of all the machines that were accepted by $R$. For each such machine, we run $i$ steps of that machine on $x$. If any of them accepts, we accept. Otherwise, we set $i\leftarrow i+1$ and continue.


How do you have a type typed "Type" when implementing a programming language?

I think what you might have found in your previous researches might be a pure type system.
In a pure type system, to avoid having "Type" being a "Type" at the same level that "Int" is a "Type", you would define another layer of "Types" where you would define "Type" as the entire first layer (and you would define this layer in the next one, and so on)
In practice, you could define your base types as "types", and the next layer would be kinds. The type "type" would be a kind. You might also want to consider functions of types to types as another kind.


Combining these two results into one asymptotic notation

Not that I encourage you to do so, but here's one way:
$$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) $$

For $\epsilon = \omega(N^{-1})$, the $\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor$ expression is $0$, and the left expression is $$\frac{1}{\epsilon+N^{-1}}+\log N = \Theta(\epsilon^{-1} + \log N)$$

For $\epsilon = \Theta(N^{-1})$, the whole expression translates into $\Theta(N)$.

For $\epsilon = o(N^{-1})$ you get:
$$\Theta \left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+ \frac{1}{\epsilon+N^{-1}}+\log N\right) = \Theta\left(N\log\left\lfloor\frac{1}{N\epsilon}+1\right\rfloor+\Theta(N)\right)=\Theta\left(N\log\frac{2}{N\epsilon}\right)$$


How do I describe formally complexity of 2-sum problem algorithm?

Consider this slightly modified algorithm where I've added an "operation counter" t. This will be incremented every time we do a comparison or assignment.

1. ZeroSumPair(A[1..n]) // A[1..n] <-- sorted
2.   l <- 1, r <- n
3.   t <- 3             // 2 for first two assignments and 1 for initial while check
4.   while(l < r)
5.     t++              // 1 for initial while check
6.     while(l < r or A[l] + A[r] > 0)
7.       t++            // 1 for decrementing r
8.       r--
9.       t++            // 1 for following while check
10.    t++              // 1 for if comparison
11.    if(A[l] + A[r] = 0)
12.      return true
13.    t++              // 1 for incrementing l
14.    l++
15.    t++              // 1 for following while check
16.  return false

This is a bit verbose, but it will work. Now we must simply prove that, at termination we have $t = O(n)$. We can do this inductively with a loop invariant.

Let's use the following loop invariant for the loop on line 4.

$$t = 3 + 4(l-1) + 2(n-r)$$

Base Case

Initially $t = 3$, $l = 1$, and $r = n$. Thus we have:

$$3 = 3 + 4(1 - 1) + 2(n - n) = 3$$

Inductive Case

Let $t'$, $l'$, and $r'$ be the values of $t$, $l$, and $r$ at the end of our previous iteration. At the end of our current iteration we have $l = l' + 1$, $r = r' - k$ for some $k$, and $t = t' + 4 + 2k$. Thus we have:

$$\begin{align*}
t & = t' + 4 + 2k\\
  & = 3 + 4(l' - 1) + 2(n - r') + 4 + 2k\\
  & = 3 + 4(l - 2) + 2(n - (r + k)) + 4 + 2k\\
  & = 3 + 4(l - 1) - 4 + 2(n - r) - 2k + 4 + 2k\\
  & = 3 + 4(l - 1) + 2(n - r) & \square
\end{align*}$$

Thus, we can conclude the loop invariant holds. At the end of the loop (in the worst case) we have $l = r \leq n$. We then have:
$$\begin{align*}
t & = 3 + 4(l - 1) + 2(n - r)\\
  & = 3 + 4l - 4 + 2n - 2l\\
  & = 2(n + l) - 1\\
  & \leq 2(n + n) - 1\\
  & = 4n - 1\\
  & = O(n) & \square
\end{align*}$$

Thus it is linear. There might be an easier way to do this, but this way makes sense to me pretty clearly.


Why do OS and DBMS have their own synchronisation mechanisms, when OS can alone do it and it sits at the bottom of DB?

Program synchronization is a very different beast compared to transaction synchronization. The objective of your Operating System is to have multiple applications working in sync to maximize the utilization of your CPU. A couple of reasons I can think of as to why OS' are not equipped to handle transaction synchronization are as follows.

Your DBMS is a self contained application. Allowing a 3rd party software (i.e. your OS which may be open source or owned by some corporation) direct access to the data is a no-go for business.
There maybe multiple DBMS' with different architectures (relational, non-relational, written in different languages, using different standards) installed on a single Operating System. OS designers usually ignore deadlock recovery because it becomes too complicated for them to handle efficiently. Accounting for applications across the board will mean worse performance issues for the OS, ultimately defeating the purpose of having one in the first place.


Express XOR with multiple inputs in zero-one integer linear programming (ILP)

Here is another way you could try.  To express $y=x_1 \oplus x_2 \oplus \dots \oplus x_n$ (the exclusive-or of $x_1,\dots,x_n$), try the following constraints:

$$y = x_1 + x_2 + \dots + x_n - 2t$$
$$0 \le y \le 1$$

where $y$ and $t$ are constrained to be integers.

There are no guarantees this will work better than a sequence of 2-input xors or a tree of 2-input xors.  Generally, the only way to discover what will work best with an ILP solver is to try each of the operations and see how fast the ILP solver runs.

Caution: If your problem has a lot of XORs, integer linear programming might not be the best tool for the job.  A SAT solver might be more effective.  See also CryptoMiniSat, which is a SAT solver optimized to deal well with XORs.


What is the significance of the imaginary parts in the output of an Inverse Fourier Transform? Can I avoid them?

The Fourier Transform is the change of basis, the discrete signal from image, which is finite, gets transformed into sines. The transformation itself is prone to rounding, because in frequency domain there is no such thing as finite impulse or rectangular for that matter (see Gibbs effect), there will be some approximation.

The complex numbers represent the transformed signal, where amplitude is the length (magnitude) of the number while phase is the angle. Cutting off the imaginary part destroys the phase and changes the amplitude so image looks like a noise. There is no way to avoid Imaginary part (unless the image itself is fully even-symmetric then Im is zero).

The small components in Imaginary part cannot be avoided, extending precision will help a lot, but please keep in mind that some inputs cannot be preserved and some loss will occur. Using only magnitude and discarding the phase is equivalent to saving pixel intensities and discarding the location.

If you want to store FFT result as the valid image, the best idea is to produce two images, for Real and Imaginary part or another pair using Phase and Magnitude. Another idea is to save separate channels, which works for grayscale image but is not sn option for grayscale. This operation is very lossy, some fixed unsigned integer (for example 8bit) is converted into complex pair, both floating point, so using any standard storage option will lose crucial data. Probably to make it work the log transform would be need.


This grammar (which isn't ambiguous) isn't LR(k) due to the right-recursion, thus it isn't LR(1).


What guarantees Paxos to converge (terminate)? (i.e. not run forever without a consensus)

There is no guarantee that Paxos will converge. In fact, more strongly, it can be shown that it is impossible to guarantee convergence of a distributed consensus algorithm in an asynchronous network. See for example Fischer, Lynch and Patterson's short paper ‘Impossibility of Distributed Consensus with One Faulty Process’.

In practical implementations it is usual to rely on the fact that, as long as enough nodes are working and communicating with each other, if exactly one node sends out a PREPARE (phase 1a) message for a sufficiently large ballot, and there are no other messages in flight, then the system will converge in a small number of round-trips. These conditions can be arranged, eventually-almost-certainly, by using randomised timeouts and maybe some kind of backoff.


Undecidability of closure under reverse of language accepted by TM

Ok , first consider this clearer proof which takes a similar approach :
Assume S is decidable , we show a reduction ATM ≤m S , obtaining a contradiction
We map <M,w> to <M'> such that :
M' = " on input x :
If x = 01 accept ,
If x = 10 reject ,
If x = 10 simulate M on w , if M accepts w accept , if M halts and rejects w then reject
Now , if M accepts w , meaning <M,w>   ∈ ATM  , then the L(M') would be =  {01 (which is always accepted) , 10 (which is only accepted if M accepts w) } and thus <M'> ∈ S
If M rejects w or loops on w , meaning <M,w> does not belong to ATM , then L(M') = {01} and thus <M'> does not belong to S , completing our reduction , and thus if S is decidable ATM is decidable which is a contradiction , thus S is undecidable
The point is to construct M' such that it accepts a string and it's reverse if M accepts w so that also S accepts M' or accept a single string if M rejects w so S rejects M' since M' doesn't also accept the reverse of the string
You could have used any 2 different strings as long as one is the reverse of the other , instead of 01,10 feel free to use 110,011 hopefully you get the point
Following the link the reduction is from ATM , the only difference is that if M accepts w , then L(M') is ∅ so S accepts M' and if M rejects w or loops on w L(M) = {01 (which could have been chosen to be any string) } and thus M' does not belong to S
Finally it's worth reminding that ATM is the language where M accepts w , while Halting is the language where M halts on w , you may find it a good exercise to try showing a reduction from Halting to S , the proof would be very similar


largest samples of set of random variables

Yes, you are right; the PDF of $Z=\max(X,Y)$ can be computed from the PDFs for $X,Y$ in $O(n+m)$ time, using the approach you described.

In particular, it takes $O(n)$ time to compute $P(X<x)$ for each $x$ ($n$ sums), $O(m)$ time to compute $P(Y<y)$ for each $y$ ($m$ sums), and $O(n+m)$ time to then compute $P(Z=z)$ for each $z$ (3 products and 2 sums for each of the possible values of $z$).

Perhaps that paper was using a sub-optimal algorithm, or maybe it was just a mistake, or maybe the author didn't care about the difference between $O(n+m)$ vs $O(nm)$ and used an overly loose bound.


Complexity of deciding if a formula has exactly 1 satisfying assignment

Your problem is known as the $\text{UNIQUE-SAT}$ problem which is $\mathsf{US}$-complete. The problem is in $\mathsf{D^p}$ but not known to be $\mathsf{D^p}$-hard under deterministic polynomial time reductions, where the class $\mathsf{D^p} = \{ L_1 \cap \overline{L_2} \mid L_1,L_2 \in \mathsf{NP} \}$.

It was shown by Papadimitriou and Yannakis [1] that the set of uniquely satisfiable formulas is contained in $\mathsf{D^p}$. This follows by the definition of $\mathsf{D^p}$: let $L_1$ be SAT, and let $L_2$ be the set of formulas with $2$ or more satisfying assignments. Regarding $\mathsf{D^p}$-hardness of $\text{UNIQUE-SAT}$, Blass and Gurevich [2] gave a partial answer. For one, they showed a non-relativizing proof technique would be needed to settle the question. However, Valiant and Vazirani [3] gave a randomized polynomial time reduction from $\text{SAT}$ showing $\mathsf{D^p}$-hardness of $\text{UNIQUE-SAT}$ under randomized polynomial time reductions .

When it is known that the problem has at most one assignment or no assignments, the promise problem is called $\text{UNAMBIGUOUS-SAT}$. The Valiant–Vazirani theorem states that if there is a polynomial time algorithm for $\text{UNAMBIGUOUS-SAT}$, then $\mathsf{NP}=\mathsf{RP}$. To prove their theorem they showed that the promise problem $\text{UNAMBIGUOUS-SAT}$ is $\mathsf{NP}$-hard under randomized polynomial time reductions. A corollary that follows from the Valiant–Vazirani theorem is that $\text{UNIQUE-SAT}$ is complete for $\mathsf{D^p}$ under randomized polynomial time reductions.

[1] Papadimitriou, Christos H., and Mihalis Yannakakis. "The complexity of facets (and some facets of complexity)." Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 1982.

[2] Blass, Andreas, and Yuri Gurevich. "On the unique satisfiability problem." Information and Control 55.1 (1982): 80-88.

[3] Valiant, Leslie G., and Vijay V. Vazirani. "NP is as easy as detecting unique solutions." Theoretical Computer Science 47 (1986): 85-93.


Estimate distribution of a composite variable

Use a convolution.

For instance, write the generating function for each set, then multiply the generating functions; this gives you the generating function for the distribution of the sum.

This gives you the exact distribution (which is even better than an approximation!).


A trace is a (finite or infinite) sequence of program steps. (Some works only consider finite traces, or only infinite ones.)

A property is a set of traces. E.g. all those traces where variable $x$ is never negative.

A hyperproperty is a set of sets of traces. E.g. the sets of traces $T$ where each trace in $T$ is finite.

Some complex security goals can not be described as a property. Non-interference, for instance, can not be checked on a single trace, but only on the set of all the possible traces a given system can generate during execution.


Is there a formal language of Combinatory Logic's expressions?

The set of valid expressions in combinatory logic forms a computable formal language, and so can be described by a grammar. It is likely that this language is context-free, and so can be described by a context-free grammar.
More generally, we know the power of grammars exactly: a formal language can be described by a grammar if and only if it is recursively enumerable. So if there is an algorithm which enumerates all valid expressions in combinatory logic, then the language of all valid expressions in combinatory logic can be described by a grammar.
Even more generally, by definition, a formal language over an alphabet $\Sigma$ is just a collection of words over $\Sigma$. This means that any encoding of combinatory logic expressions which uses some fixed alphabet is automatically a formal language.


Categorisation of type systems (strong/weak, dynamic/static)

Historically, the term "strongly typed programming language" came into use in the 70's in reaction to the existing widely used programming languages, most of which had type holes.  Some examples:

In Fortran, there were things called "COMMON" storage areas, which could be shared across modules, but there were no checks to see if each module was declaring the contents of the COMMON storage with the same types.  So, one module could declare that a particular COMMON storage block had an integer and another a floating point number, and the data would get corrupted as a result.  Fortran also had "EQUIVALENCE" statements, whereby the same storage could be declared to contain two different objects of different types.
In Algol 60, the type of procedure parameters was declared as just "procedure", without specifying the types of the parameters of the procedure.  So, one could assume that a procedure parameter was an integer-accepting procedure, but pass in a real-accepting procedure as the argument.  This would result in the same kind of corruption as the COMMON and EQUIVALENCE statements.  (However, Algol 60 did eliminate the older problems.)
In Pascal, "variant records" were added which were almost exactly like the old EQUIVALENCE statements.
In C, "type casts" were added whereby any type of data could be reinterpreted as data of a different type.  This was a rather deliberate type hole meant for programmers who supposedly know what they are doing.

The strongly typed languages designed in the 70's were meant to eliminate all such type holes.  If you drill down into what this means, it means essentially that data representations are protected.  It is not possible to view data object of one type as an object of another type which happens to have the same bit pattern as its internal representation.  Theoreticians began to use the term "representation independence" to characterize this property instead of the vague idea of "strong typing".

Note that dynamically typed languages like Lisp which perform complete run-time type checking are "strongly typed" in the sense of protecting representations.  At the same time, statically typed languages would lose representation independence unless they did array bounds checking.  So, they are not "strongly typed" in the strict sense of the term.  Due to these anomalous consequences, the term "strongly typed" fell into disuse after the 70's.
When the US Department of Defence developed rigorous requirements for the design of Ada, they included the requirement that the language should be "strongly typed".  (It seems to have been believed at that time that the idea of "strongly typed" was self-evident.  No definition was offered.)  All the language proposals submitted in response claimed to be "strongly typed".  When Dijkstra analysed all the language proposals, he found that none of them were strongly typed and, in fact, it wasn't even clear what the term meant.  See the report EWD663.  However, I see that the term is coming back into use now, through a younger generation of researchers who don't know the checkered history of the term.

The term "statically typed" means that all type-checking is done statically and no type errors will arise at run-time.  If the language is also strongly typed, that means that there are really no type errors during execution.  If, on the other hand, there are type holes in the type system, the absence of run-time type errors means nothing.  The results could be completely corrupt.

The new debate about "strong vs weak typing" seems to be about whether certain type conversions should be allowed.  Allowing a string where an integer is required is "weak typing" according to these folks.  There is some sense to that because attempting to convert a string to an integer may fail, if the string doesn't happen to represent an integer.  However, converting an integer to a string doesn't have that problem.  Would that be an instance of "weak typing" according to these folks?  I have no idea.  I notice that the Wikipedia discussions on "weak typing" don't cite any refereed publications.  I don't believe that it is a coherent idea.

Note added: The basic point is that the term "strong typing" did not come into use as a technical term with a rigorous definition.  It was more like some language designers felt: "our type system is strong; it catches all type errors; it doesn't have type holes" and, so, when they published their language design, they claimed that it was "strongly typed".  It was a buzz word that sounded good and people started using it.  The Cardelli-Wegner paper was the first one that I have seen where some analysis was provided into what it means.  My post here should be thought of as an elaboration of their position.


Building vertex-edge visibility graph among polygonal obstacles on 2d plane

I'm not sure if this is what you're after, but here's an $O(n + k)$ approach from J. O'Rourke and I. Streinu, Computational Geometry 10 (1998), pp. 105-120:

  $G_{VE}$ may be constructed in $O(n + k)$ time for a polygon with $n$ vertices and $k$ visibility edges, by a slight modification of Hershberger's algorithm that constructs $G_v$ in this time bound [8] from a polygon triangulation. Supplementing with Chazelle's linear-time triangulation algorithm achieves the claimed bound.


You can use the pumping lemma to show that $L$ is not regular and by definition you can't generate NFA. Maybe the question is wrong and they want you to generate a pushdown automaton (PDA).


Concave Polygon Intersection - Algorithm

First, order the $Blue \cup Yellow$ points according to a clockwise visit of A, and similarly, order the $Red \cup Yellow$ points according to a clockwise visit of B.

Now start at a blue point (if there is one) and follow A clockwise until you are at a yellow point. Then follow B clockwise until you are at a yellow point again; then follow A clockwise, and so on, switching from following one polygon to the other every time you encounter a yellow point. Continue until you are back at the starting point. See Weiler-Atherton clipping algorithm and the references there.

If there are no blue points, start instead from a red point and follow B initially. If there are only yellow points (with no blue nor red), start from any yellow point and follow the polygon that makes you stay inside the other polygon.

Note that in general the intersection of non-convex polygons may consist of multiple disconnected regions. The procedure above will only give you one of these regions.


Probabilistic test of matrix multiplication with one-sided error

If $AB=C$, then $A(Bx)=Cx$ for all vectors $x$. Generate vectors randomly and check. This known as Freivalds' algorithm. Wikipedia has details.


Implementing regular expression matching using Brzozowski derivatives

Yes.  This approach has been used before.  I've seen it used in a research project, where the goal was to build a regexp matcher that could be formally verified to be correct (with as little effort as possible).  This algorithm was implemented in Coq and then proven correct.  The nice thing is that it is relatively easy to prove correct.  In contrast, a table-driven lexer would be harder to prove correct, because one would have to prove that the table was constructed correctly.

I think that table-driven lexers are often faster in practice.  Your scheme essentially computes the transition table on the fly.  Table-driven lexers involve pre-computing the transition table, and now you only need to do a few instructions per character read from the input (read one character, do a table lookup based on the current state and just-read character, update the current state).  Therefore, their constant factor can be lower.

To be clear, by table-driven lexer, I mean something that converts the regexp to a DFA and then precomputes a table that represents the transition table.  This is useful in cases where the regexp is fixed and known at compile time.  For many regexps seen in practice, the size of the DFA is not too large and so this leads to a fairly efficient matcher algorithm.


Regular Expressions to accept strings where every two successive 0s are followed by a 1

Take either 1, or 01, or 001 and repeat any number of times. Plus there can be a single 0 at the end.


Proving $L = \{a^iba^j|i\ge2j\ge0\}$ isn't regular

As noted, you need to be careful making assertions about $xy$. Recall that the pumping lemma says that if $L$ is a regular language, then there is a positive integer $p$ such that any string $s\in L$ can be written as $s=xyz$ where

$|xy| \le p$,
$|y| > 0$,
$xy^iz\in L$ for all $i=0,1,\dotsc$.

so in your example all you know is that $|xy|\le p$. You certainly can't assert that $|xy|=2p+2$.

All is not lost, though. If you assume that $L$ is regular and let $s=a^{2p}ba^p$ (notice that I chose a different string to pump), then since $|xy|\le p$, you know that $xy$ "lives" among the first group of $a$'s, and so $xy=a^k$, for some $k\le p$. Hence $y=a^t$ for some $0<t\le p$ and so the PL assures us that $xy^iz\in L$ and we have $xy^iz=a^{2p+(i-1)t}ba^p$. [Do you see why?] Now all you have to do is pick some $i$ so that $xy^iz\notin L$ to establish a contradiction and thus show that $L$ isn't regular.

I'll leave the rest for you: what $i$ can you use to show that $xy^iz\notin L$?


Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one)

Consider the dynamic programming formulation of Bellman-Ford:

$\qquad \displaystyle \mathrm{bf}(i,j) = \begin{cases}
                             0         &, i = 0 \land j = s \\
                             \infty    &, i = 0 \land j \neq s \\
                             \min\limits_{k \in V}\, \big(\, \mathrm{bf}(i-1,k) + c(k,j)\,\big) &, \text{else}
                          \end{cases}$

What meaning does $\mathrm{bf}(i,j)$ have, that is what does DP-matrix entry $\mathrm{bf}[i,j]$ contain?

   If you unfold the definition (i.e. proof by induction) you see that $\mathrm{bf}(i,j)$ is the weight of the shortest path from starting node $s$ to $j$ with at most $i$ edges -- exactly what you are looking for.


Enumerate all paths of length 3 in a given tree T

Let $T$ be a tree on $n$ vertices. Root $T$ in an arbitrary vertex $r$ and let $p(v)$ denote the parent of vertex $v \neq r$ in $T$. For $v \in V$, let $C(v)$ denote the children of $v$ in $T$.

A path $\langle v_1, v_2, v_3, v_4 \rangle$ of length $3$ in $T$ is of exactly one of the following two forms (when the path's traversal direction is ignored):

Type A: $p(v_1) = v_2$, $p(v_2) = v_3$, $p(v_3) = v_4$, or
Type B: $p(v_1)=p(v_3)=v_2$ and $p(v_4)=p(v_3)$.

To enumerate all paths of type $A$ it suffices to perform a DFS visit of $T$. When a vertex $v$ at depth at least $3$ is encountered, return the path $\langle v, p(v), p(p(v)), p(p(p(v))) \rangle$.
This takes $O(n)$ time overall.

To enumerate all paths of type $B$, perform a DFS visit of $T$ and when a vertex $v$ at depth at least $2$ is encountered, return all the paths of the form $\langle v, p(v), p(p(v)), u \rangle$ where $u \in C(p(p(v))) \setminus \{ p(v) \}$.
This requires time $O(n + P)$, where $P$ is the number of paths of type $B$ in $T$.

Overall you can enumerate all the paths of length $3$ in $T$ in time $O(n + P)$.

Notice that $\Omega(n)$ is a lower bound on the time needed by any algorithm since you need to read the input tree. A bad case in which $P=0$ but you still spend $\Theta(n)$ time is a star.


I suppose you want to delete as little EmptyEvents as possible.

In that case, you can achieve what you want in O(nlog(n)) time, where n is the number of events.

Proceed as follows:

First, get rid of the EmptyEvents which overlap with a NormalEvent. To do so, put all your starting and ending times in a vector and sort them in increasing order, breaking ties by putting end-times before start-times. Set a counter = 0 and an empty unordered set S. Now go through your vector of times in order.

Each time you come across the start-time of an EmptyEvent, if counter > 0, then flag that event for deletion. If counter == 0, put that event (or rather its id) in S.
Each time you come across the end-time of an EmptyEvent, if counter > 0, then flag that event for deletion. Delete the corresponding event from S (if it is still in there).
Each time you come across the start-time of a NormalEvent, increase the counter by 1.
Each time you come across the end-time of a NormalEvent, decrease the counter by 1, flag all EmptyEvents in S for deletion and clear S.

(then delete all the flagged events)
Then, choose the largest subset of EmptyEvents, no two intersecting. To do so, sort all EmptyEvents according to end-time. Then just go through these events and greedily select one each time it doesn't intersect with the last selected one.
Then, set all the NormalEvent booleans. Set a counter = 0 and prevStart to track the most recent start-time. Sort all NormalEvents start and end-times. Iterate through them in order.

Each time you come across start-time of NormalEvent e, set e.overlapsStart to counter > 0. Then increase counter by 1. Also set prevStart = e.startTime.
Each time you come across end-time of a NormalEvent e, decrease the counter by 1 and set e.overlapsEnd to e.startTime < prevStart.

I'll let you convince yourself of the validity of each step. But here is a good starting point if you are unable to do so :
Interval scheduling on Wikipedia


No, $\sqrt{n}$ increases far faster than $O(1)$, and $n^{\sqrt{n}}$ grows far faster than $n^{O(1)}$.  No, it certainly does not have the same runtime.  See Sorting functions by asymptotic growth.

There may be no predefined complexity class; the complexity class is the class of all algorithms who run in time $n^{O(\sqrt{n} \log n)}$, and there's probably not much more to say.


Find the bitwise AND of a subarray closest to given number

Let f (i, j) = AND ($A_i, A_{i+1}, ..., A_{j-1})$ for $0 ≤ i < j ≤ n$. $f (i, j)$ has the property that whenever $i ≤ i' < j' ≤ j$, $f (i, j) ≤ f (i', j')$.

We also have $f (i, j)$ = AND($(f (i, k), f (k, j)$) for any $0 ≤ i < k < j ≤ n$.

Because of these properties, we get an algorithm slightly better than brute force as follows:

Keep track of the optimal solution so far, initialising with f (0, 1). For 0 ≤ i < n: If $a_i ≤ P$ then check if f (i, i+1) is a better solution. Otherwise, find the largest j such that f (i, j) ≥ P; it may be that j = n. Check if f (i, j) is a better solution. If j < n then check if f (i, j+1) < P is a better solution.

How to find the largest j in O (log n), making the total time O (n log n):

We start by building some tables, calculating all f (i, i+2) for even i, f (i, i+4) for i multiple of 4, f (i, i+8) for i multiple of 8. This is done in O (n) since there are about n values which can each be calculated with a single AND operation.

To find the largest j, we start with j = i+1, f (i, j) = a [i]. If j < n is odd then we can calculate f (i, j+1); if the result is ≥ P then we replace j with j+1, which makes j even. Then if j < n is an odd multiple of 2 we can calculate f (i, j+2); if the result is ≥ P then we replace j with j+1, which makes j a multiple of 4, and so on. This ends with j being a multiple of $2^k$ for some k. Now we try to increase j by $2^{k-1}$, $2^{k-2}$, ..., 4, 2, 1 if the increased j is ≤ n, and f (i, j) ≥ P. The total cost is O (log n) operations.


Page frame management is conceptually very simple; all you really need is a linked list. However, there are two main factors which complicate things:

DMA. DMA is one of the few things that might need a physical buffer larger than a page in size. In addition, there are legacy devices to contend with; on x86, for example, 32-bit devices can only do DMA from physical addresses below the 4G limit. For ISA it's even worse.
Cache colouring, which is an extremely important optimisation.

Most operating systems use surprisingly simple techniques.

Windows, for example, just uses a bunch of linked lists (or at least it did, last time anyone said anything about it). It's hard to say since we can't see the source code, but there are probably N*M linked lists where N is the number of possible states a page can be in (e.g. in-use, free, waiting to be paged out) and M is the number of colours.

Linux famously uses a buddy allocator to manage physical pages, which is only slightly more complicated than a bunch of linked lists when you think about it.

Probably the most sophisticated management scheme that has been documented extensively is that of Solaris. See Bonwick & Adams, Magazines and Vmem: Extending the Slab Allocator to Many CPUs and Arbitrary Resources, USENIX 2001. There is also an extended discussion in the book Solaris Internals. The Solaris slab allocator goes to a lot of trouble to avoid lock contention, cache thrashing, and the like, and also can tune its implementation for different data types as needed.

What's interesting is that Solaris uses the same memory allocator to handle page frames that it uses to handle kernel objects, by nesting slab allocators inside slab allocators. The paper is definitely worth a read.


The impact of caching on the system performance or on the user experience

I think that a good starting point to understand how the memory (including caching) works is What Every Programmer Should Know About Memory from U. Drepper. In fact, this is one of the best papers I have ever read about computers.

More recently, I found How misaligning data can increase performance quite entertaining. It is a direct application of the things you can learn from the first one.


Show that if the discrete log problem is $(T,1-\epsilon)$-hard, then it's $(O(\frac{T}{\frac{1}{\epsilon}log\frac{1}{\epsilon}}-nlogm),\epsilon)$-hard

Suppose that there exists an algorithm $A$ which runs in time $T_A\le \frac{T}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}-n\log m$, and $\Pr\limits_{a\sim U(G)}\left[A(a)=\log_g a\right]\ge \epsilon$. We want to enhance the success probability of $A$. The trick is to evaluate $A$ on different elements $b_1,...,b_k$ (who of course depend on the input $a$) whose logarithm will allow us to recover $\log_g a$. Define $A'$ as follows, given input $a$ pick independently $i_1,...,i_k\in [m]$ uniformly at random, and evaluate $A$ on the inputs $ag^{i_1},...,ag^{i_k}$. For each $1\le j\le k$ check whether $A(ag^{i_j})=\log_g ag^{i_j}$ (the verification requires $n\log m$ time), and if there exists $j$ for which the equality holds return $A(ag^{i_j})-i_j \pmod m$. The running time of $A'$ is bounded by $k(T_A+n\log m)\le \frac{k}{\frac{1}{\epsilon}\log\frac{1}{\epsilon}}T$. I leave it to you to show that $ag^{i_1},...,ag^{i_k}$ are independent and therefore we can write $\Pr\limits_{a\sim U(G)}\left[A'(a)=\log_g(a)\right]\ge 1-(1-\epsilon)^k\ge 1-e^{-\epsilon k}\ge 1-\epsilon$, for $k=\frac{1}{\epsilon}\log\frac{1}{\epsilon}$.


Function whose domain is strictly included in its range

Without getting to the technicality of codomain/range/image and surjective functions, the property you ask for can surely happen. For instance,

$$f(x) = 2x$$

defined over the domain interval $[0,1]$, has the image $[0,2]$. This should not happen over finite domains.


There is no universal answer. It depends on how you choose to model the universe of discourse you've been assigned to model.
We'd normally expect there to be multiple cars that appear as distinct individuals in the model, and we expect the predicate has to be the relationship that expresses which individual owns which individual object, i.e. between individual persons and individual cars.  In that case, if car is a constant, it must denote a particular car, so you'd need other constants, for instance, car2, car3, etcetera, to denote other cars. It's awkward, but it can be done.
So it is valid, but very impractical. In practice, we usually see a predicate is_car(x), as Yuval Filmus suggests, and a couple of individuals for which that predicate holds that stand for the individual cars that exist in the universe of discourse being modelled.
Tom can be a constant representing a particular person, and we can use other constants such as Dick and Harry to represent other persons. Courses in logic tend to do this because they are proper names and they use sentences such as Tom has a car which imply that there is, indeed, exactly one Tom in the universe of discourse, so you can do this.
Once again: this is valid, and probably what your professor wants you to do, but it is highly impractical.
In practical applications of logic, e.g. when designing a relational database, we can't usually assume that names such as Tom uniquely identify a person, so we model names not as constants, but as predicates.
For instance, we may use a predicate has_first_name(x,y), and the statement Tom has a car can then be expressed as
$\exists! x: \mbox{has_first_name}(x,\mbox{"Tom"}) \\ \wedge \\ \exists x: \mbox{has_first_name}(x,\mbox{"Tom"}) \wedge \exists y: \mbox{is_car}(y) \wedge \mbox{has}(x,y)$
PS: Mars points out a more serious issue with using constants for cars: they always refer to a particular car, and Tom has a car doesn't - you could only express it by a statement that lists every individual car, like this: $\mbox{has}(\mbox{Tom},\mbox{car}) \vee \mbox{has}(\mbox{Tom},\mbox{car2}) \vee \ldots$.


Why is the Marking Algorithm takes O(number of marks) ?

After mailing the author, I've found the answer:

The marking algorithm can be done in $O(B)$ by making sure that every unit of time we spend produces one mark. Consider the following piece of code:

for i in 1..|T|
  for j in A s.t. T[i]==P[j]
    m[i-j+1]++

The second loop need not take $O(|A|)$, it can be implemented more efficiently by precomputing the matching positions for every character in the alphabet. For example, if $T[i]$ happens to be '$c$' then we precompute all the offsets $j$ in $A$ for which P[j]=='c'. Then every iteration of the second loop produces a mark, like this:

for i in 1..|T|
  for j in offsets[T[i]]
   m[i-j+1]++

The total number of marks is $\sum_{a\in A} F_a=B$ because every position $a\in A$ has $F_a$ marks. So the run time is $O(B)$.


Why can we ignore the constant factor in Weis's proof of the Master Theorem

Suppose that your function is always in the range $cN^k$ to $CN^k$. Consider the three recurrences
$$
s(N) = as(N/b) + cN^k, S(N) = aS(N/b) + CN^k, R(N) = aR(N/b) + N^k.
$$
For appropriate initial conditions, $s(N) \leq T(N) \leq S(N)$ will hold, as a straightforward proof by induction would show. On the other hand, for appropriate initial conditions, $s(N) = cR(N)$ and $S(N) = CR(N)$, as another straightforward induction shows. This explains Weis's remark.

What it happening here? As you unroll the recursion, you add various terms which are $\Theta(N^k)$, for various values of $N$. The contribution of the big Theta to the final sum is at most a constant factor. Instead of $a^m \sum_{i=0}^m (\frac{b^k}{a})^i$, you get $\Theta\bigl(a^m \sum_{i=0}^m (\frac{b^k}{a})^i\bigr)$. Crucially, the additional constant factor is global and doesn't accumulate throughout the recursion.

As an example, consider the generic recurrence $s(N) = 2s(N-1) + f(N)$, with base case $s(0) = 0$. The solution is $$ s(N) = f(N) + 2f(N-1) + 4f(N-2) + \cdots + 2^{N-1} f(1). $$ If we multiply $f(N)$ by a constant factor, the solution of this recurrence will be multiplied by the same constant factor, while the constant $2$ stays the same.


Selecting connected subgraph that exceeds value c, with least possible weight

This problem is NP-hard.
Let $S = \{x_1, \dots, x_n\}$ be an instance of partition.
Create a clique $G$ on $n$ nodes $v_1, \dots, v_n$.
Set both the cost and the weight of $v_i$ to $x_i$.
Set $t = \frac{1}{2}\sum_{x_i \in S} x_i$.
If there is a subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$, then the set of vertices $\{v_i \mid x_i \in C\}$ is connected, has total value $t$ and total weight $t$.
If there is no subset $C$ of $S$ such that $2 \sum_{x_i \in C} x_i = \sum_{x_i \in S} x_i$ then every subset of vertices of $G$ either has total value smaller than $t$ (and hence is not a feasible solution), or has a total value larger than $t$, and hence also weight larger than $t$.
Then you have that the answer to the instance of partition is yes if and only if the optimal solution to your problem has measure (total weight) $t$.


Here are some of the examples of context free languages

$\{ w \in \{0,1\}^*\mid \ w$ contains at least three ones }
$\{ w \in \{0,1\}^*\mid \ w = w^{R}$ and $\mid w \mid $ is even  }
$\{ w \in \{0,1\}^*\mid \ $ the length of $w$ is odd and the middle symbol is $0$ }
$\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0 $ and $ i + j = k $ }
$\{ a^{i} b^{j} c^{k} \mid \ i,j,k \ge 0, $ and $ i = k  $ or $i = k$ }
$\phi$

Reference : https://web.njit.edu/~marvin/cs341/hw/hwsoln05.pdf


Calculator for time complexity of recursive functions

Wolfram Alpha is giving you a more accurate estimate, $T(n) \sim 2n$. However, it can also give you the weaker estimate $T(n) = O(n)$ you are after:

Just click on Show weaker bound.


Partition the indices of 2d array to minimize sum of sub-matrices

First we note that with $\mathcal{O}(n^2)$ precomputation, where we store the 'prefix sums', we can find the sum of all the elements in a given square subgrid in $\mathcal{O}(1)$ time.

Now, let $DP[i]$ be the optimal answer, if the input matrix had only the first $i$ rows and first $i$ columns. The final answer that we are looking for is $DP[n]$.

The base case would be $DP[0] = 0$.

To compute $DP[i]$, we iterate over all $j$ such that $1 \le j \leq i$, and we consider the last interval in the partition to be $[j, i]$. For a fixed $j$, the minimum sum would be $DP[j-1] + Sum(M[j \ldots i][j \ldots i])$. So that leads to the equation

$$DP[i] = \min_{1\leq j \leq i} (DP[j-1] + Sum(M[j \ldots i][j \ldots i]))$$

So, $DP[i]$ can be computed in $\mathcal{O}(n)$ time, and the whole problem takes $\mathcal{O}(n^2)$ time and space.


Choosing Constant for Last Step in Substitution METHOD $T(n)= 5T(n/4) + n^2$

Your constant $c$ needs to satisfy
$$ \frac{5}{16} c n^2 + n^2 \leq c n^2, $$
that is,
$$ \frac{5}{16} c + 1 \leq c. $$
Hopefully you can determine the set of constants $c$ for which this inequality is satisfied.


The question doesnt make too much sense because the $\pi$-calculus was proven Turing complete, or in other words equivalent to a Turing machine ever since its inception by Milner in 1992. There is a reference on Wikipedia.


Why do modern processors need a runtime stack?

I would say that "required" is a bit of strong word. Processors provide hardware support for stacks to help implement the call stack abstraction. Having special instructions to do so can improve performance. Note however that some processors like ARM (except in Thumb mode) do not really have special instruction to do so, the ldm/stm instructions with pre/post inc/dec are flexible enough to do so.


"Mathematical Physics"'s equivalent for Computer Science

When you use mathematics or mathematical models to understand physical nature around us and its dynamics, the mathematics in its association with physical laws become Physics. Similarly, when you leverage mathematics or its models like trees, graph, first-order logic etc to understand computational problems it becomes computer science.


How can i solve the recurrence $T(n)=2T(n-2)+n\log n$

Hint:

Let $n=2m$.

$$T(2m)=2T(2m-2)+2m\log(2m)$$

or

$$T'(m)=2T'(m-1)+2m\log(2m)$$

which has the classical form.


Can constraint satisfaction problems be solved with Prolog?

To solve a problem with Prolog, as with any programming language, be it declarative or imperative, you have to think about the representation of the solution and the input.

Since this is a programming question, it would've been popular on StackOverflow.com where programmers solve programming problems. Here I would attempt to be more scientific.

To solve the problem in the OP one has to reverse the relation defined by the dependencies stated in the input. Clauses of the form $Attend(X) \to Attend(Y) \wedge Attend(Z)$ are easy to reverse. The clauses $Attend(AD)\wedge Attend(BM)\to Attend(DD)$ like

  Daisy Dodderidge said she would come if Albus Dumbledore and Burdock
  Muldoon both came

are more difficult to treat.

With Prolog the first simple approach is to avoid a full reversal of the  relationship and be goal directed instead.

Assume an ordering on the list of guests and use a rule

$\qquad \left\{\begin{align}
 A(X)\wedge A(Y) &\to A(Z), \\
 A(W)&\to A(X), \\
 A(W)&\to A(Y), \\
 X&<Z, \\
 Y&<Z\end{align}\right\}\quad \vdash \quad A(W) \to A(Z)$

(We use $A(X)$ instead of $Attend(X)$ to keep it short)

This rule is easy to implement.

A rather naive approach

For readability let follows be the relation given as an input, and brings be its reverse.

Then the input is given by

follows(bm,[ad]).
follows(cp,[ad]).
follows(ad,[cp]).
follows(dd,[cp]).
follows(ad,[ec]).
follows(bm,[ec]).
follows(cp,[ec]).
follows(cp,[fa]).
follows(dd,[fa]).
follows(bm,[cp,dd]).
follows(ec,[cp,dd]).
follows(fa,[cp,dd]).
follows(dd,[ad,bm]).

And brings can be defined as follows:

brings(X,S):-brings(X,S,[]).

brings(_X,[],_S).
brings(X,[X|L],S):-brings(X,L,[X|S]).
brings(X,[Y|L],S):-follows(Y,[X]),brings(X,L,[Y|S]).
brings(X,[Y|L],S):-follows(Y,[A,B]),
          member(A,S),member(B,S),brings(X,L,[Y|S]).

Here the third argument in brings/3(X,L,S) is the list of guests that were already proven to attend if $X$ attends.

If we define

 partymaker(X):-Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests).

We get the following unique solutions:

 [ad,ec]

This is not the complete list, since under the alphabetical ordering the clause

 follows(bm,[cp,dd]).

is not working.

A rather involved solution to the original puzzle

To solve the problem completely you have to actually let the system try to prove attendance for later guests without introducing infinite loops to the search tree. There are multiple ways to accomplish this goal. Each has its advantages and disadvantages.

One way is to redefine brings/2 as follows:

brings(X,S):-brings(X,S,[],[]).

% brings(X,RemainsToBring,AlreadyTaken,AlreadyTried).
%
% Problem solved
brings(_X,[],_S,_N).
% Self
brings(X,[X|L],S,N):-brings(X,L,[X|S],N).
% Follower
brings(X,[Y|L],S,N):-follows(Y,[X]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 2
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),
                   follows(Y,[A,B]),
                   try_bring(X,A,L,S,[Y|N]),
                   try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 1
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),\+follows(Y,[_A,_B]),
                   follows(Y,[C]),
                   try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).

try_bring(_X,A,_L,S,_N):-member(A,S).
try_bring(X,A,L,S,N):- \+member(A,S),sort([A|L],Y),brings(X,Y,S,N).

The last argument in brings/4 is necessary to avoid an infinite loop in try_bring.

This gives the following answers: Albus, Carlotta, Elfrida and Falco. However this solution is not the most efficient one since backtracking is introduced where it sometimes can be avoided.

A general solution

After the link to the Third International NoCOUG SQL & NoSQL Challenge was added to the original question, it became clear that what we are after is a general reachability checker on the set of subsets of the set of guests, where
the transition relation is defined by rules given such that
an application of the rule $r(X,S): V \to V'$ is a guarded command:

  if $S \subseteq V$ then $V' = V \cup \{X\}$.

We are interested in the minimal subsets $V$ such that the whole set $U$ of guests is reachable from $V$ after a finite sequence of rule applications.

add_element(X,V,U):- ( var(V) -> % set difference that works in both modes
                           member(X,U),subtract(U,[X],V);
                      \+member(X,V),sort([X|V],U) ).

support(V,U):- guests(G), % rule application
               member(X,G),
               add_element(X,V,U),
               follows(X,S),
               subset(S,V).

set_support(U,V):- support(V1,U), % sort of a minimal set
               ( support(_V2,V1) ->
                      set_support(V1,V) ;
                 V = V1).

is_duplicate(X,[Y|L]):- ( subset(Y,X) ; is_duplicate(X,L) ).

% purging solutions that are not truly minimal
minimal_support(U,L):-minimal_support(U,[],L).
minimal_support([],L,L).
minimal_support([X|L],L1,L2):-( append(L,L1,U),is_duplicate(X,U) ->
                                    minimal_support(L,L1,L2);
                                minimal_support(L,[X|L1],L2) ).

solution(L):- guests(G),setof(X,set_support(G,X),S),
              minimal_support(S,L).

Now if for instance dataset #2 is given as

follows(fa,[dd,ec]).
follows(cp,[ad,bm]).
guests([ad,bm,cp,dd,ec,fa]).

We get the answer L = [[ad, bm, dd, ec]]. Which means that all guests but Carlotte and Falco must be invited.

The answers this solution gave me matched the solutions given in the Wicked Witch article with the exception of dataset #6, where more solutions were produced. This seems to be the correct solution.

Finally, I must mention the CLP(FD) library of Prolog that is particularly suitable for this sort of problems.


How do you read the regular expression (0^∗10^+)^+?

This regular expression describes the language of all words over $\{0,1\}$ which do not consist entirely of $0$-s, and in which every $1$ is followed by $0$.


Consider the following reduction from the NP-complete problem $Clique = \{ \langle G, k\rangle \ : \text{G is undirected Graph that has a clique of size at least k}\}$ to $L$. The reduction operates as follows.
Given input $\langle G = (V, E), k \rangle\in Clique$:

If $k < \frac{9\cdot|V|}{10}$, output $G' = G \cup K_{t}$, where $t= 9\cdot |V| -10k$, and $K_t$ is the complete graph over $t$ vertices. In addition, add edges that connect every vertex in $K_{t}$ with every vertex in $G$.

Othwerwise, if $k \geq \frac{9\cdot|V|}{10}$, output $G'$ that is defined as follows. $G'$ is obtained by replacing each vertex of $v \in V$ by a clique of size 9, denoted $c_9(v)$, and then for every edge $\{ u, v\}\in E$, the two cliques $c_9(v), c_9(u)$ in $G'$ are connected, that is, every vertex of $c_9(v)$ is connected by an edge with every vertex of $c_9(u)$. Also, add to $G'$ new $t$ isolated vertices, where $t= 10k - 9|V|$.

Correctness:

If $k < \frac{9\cdot|V|}{10}$, then note that $t = 9\cdot |V| - 10k >
    0$, and so the output of the reduction $G'$ is well-defined. Now if $G$
has a clique $C$ of size at least $k$, then $G'$ has a clique of
size at least $k+t$ (verify that $C\cup \{ v: \text{$v$ is a vertex
in $K_t$}\}$ is a clique of $G'$). Conversely, if $G'$ has a clique
of $C'$ of size at least $k + t$, then the set $C = C' \setminus \{
v: v \text{ is a vertex of $K_t$} \}$ is a clique of $G$. Indeed,
the reduction does not add new edges between the vertices of $G$.
Also note that $C$ is of size $|C| \geq |C'| - | \{ v: v \text{ is a
vertex of $K_t$} \}| = |C'| - t \geq k+t - t = k$ in $G$. All in
all, we have that $G$ has a clique of size at least $k$ iff $G'$ has
a clique of size at least $k+t$. Finally, note that
$\frac{k+t}{|G'|} = \frac{k+t}{|V|+t} = \frac{k + 9|V| - 10k}{|V| +
9|V| - 10k} = \frac{9|V| - 9k}{10|V|-10k} = \frac{9}{10}$. So, $G$
has a clique of size at least $k$ iff $G'$ has a clique of size at
least $k+t = \frac{9}{10} |G'|$.
If $k \geq\frac{9\cdot|V|}{10}$, then note that  $10k - 9|V| \geq 0$, and so the output of the reduction $G'$ is well-defined. For the first direction, if $G$ has a clique $C$ of size at least $k$, then $G'$ has a clique $C'$ of size at least $9k$. Indeed, we can take $C' = \bigcup_{v\in C} c_9(v)$, that is, $C'$ consists of the 9-cliques corresponding to the vertices in $C$ (verify that $C'$ is indeed a clique of size at least $9k$ in $G'$). The following holds $\frac{|C'|}{|G'|} \geq \frac{9k}{|G'|} =
\frac{9k}{9|V|+t} = \frac{9k}{9|V| +10k-9|V| }
 =
\frac{9}{10}$. So $G'$ has a clique of size at least $\frac{9|G'|}{10}$. Conversely, assume that $G'$ has a clique $C'$ of size at least $\frac{9|G'|}{10} = \frac{9\cdot (9|V| + t)}{10} = \frac{9\cdot(9|V| + 10k - 9|V|)}{10} = \frac{9\cdot 10k}{10} = 9k$. Clearly, none of the added isolated vertices are in $C'$, and thus $C'$ consists of vertices $p$ such that $p\in c_9(v)$ for some $v\in V$. In words, $C'$ consists of vertices $p$ such that $p$ belongs to one of the 9-cliques of $G'$. Note that there could be two vertices $p_1, p_2\in C'$ such that both $p_1$ and $p_2$ are in $c_9(v)$ for some $v\in V$ (that is, $C'$ can have vertices that correspond to the same 9-clique). Now consider the following set $C =\{ v\in V: \text{ there is $p\in C'$ such that $p\in c_9(v)$} \}$. We claim that $C$ is a clique of size at least $k$ in $G$, and thus we're done. To begin with, $|C|\geq k$ because for every $v\in C$ there are at most 9 $p$'s such that $p\in c_9(v)$ and $p\in C'$, and those 9 $p$'s correspond only to the vertex $v$ in $C$. So in the worst case, $C'$ consists of whole 9-cliques and we replace every 9-clique $c_9(v)$ with $v$ to get the set $C$. So, as $|C'|\geq 9k$, then $|C|\geq k$. Now to show that $C$ is a clique in $G$, let $v_1, v_2$ be two vertices in $C$. We need to show that $\{u, v \}\in E$. By definition of $C$, there are $p_1, p_2 \in C'$ such that $p_1\in c_9(v_1)$ and $p_2\in c_9(v_2)$. Since $C'$ is a clique of $G'$, we know that $\{p_1, p_2 \}$ is an edge of $G'$, and by definition of $G'$ this can happen only when $\{v_1, v_2 \} \in E$ (indeed, vertices of different 9-cliques are connected in $G'$ when the vertices defining the 9-cliques are connected in G).


Subspace clustering with random transformation

It is possible that choosing $R$ according to a uniform distribution with zero mean constitutes a Johnson–Lindenstrauss random projection (i.e., it approximately preserves distances). See for example a paper by Achlioptas which suggests three distributions that definitely work: a zero-mean Gaussian, a random $\pm 1$, and a specific distribution on $\{0,\pm 1\}$. It is probable that using the methods in the paper, the case of the uniform distribution can also be analyzed.


Why does this NFA having an empty symbol

Yes, in this example, your solution is fine.

Perhaps the example just wanted to show the use of epsilon transitions. Also, your approach would be more complicated in the case where one of the original initial states would have a loop. We cannot transfer that loop to the common initial state.


What are the drawbacks of Normalized Mutual Information clustering evaluation method?

It is a matter of preference.

If you come with an information theory background, you'll like NMI better. If you come from a classification background, Rand index is pretty much the "accuracy" that you are used to, but on pairs.


Closest point in embedded simplicial complex

If you have only a single k-complex and you want to get the closest point regardless of whether it is a neighbor, then you can simply use any spatial index that supports nearest neighbor queries.
For low dimensionality, such as 3 or 6, kd-trees, r-trees or some quadtrees (such as the PH-Tree) will work fine. In my experience, especially the R-Tree and PH-Tree work fine with millions of points.
C++ implementations are available from libSpatialIndex, Boost R-Tree, PH-Tree C++, and many others.
For Java implementations, have a look at my TinSpin Index Library or any other one.
Disclaimer: I am the developer of TinSpin and PH-Tree.
EDIT
I assumed by point you mean vertex, my mistake. I think you can adapt the approach if you are looking for nearest points on any simplex: Instead of storing vertices in the index, you can store the 2D/3D/$k$D bounding boxes of all geometries (vertices/lines/triangles/..) in the tree. Then there are two options:

Use a nearest neighbor search to go through all bounding boxes and their elements to calculate the actual distance. You will have to check and compare these distances until the distance of the bounding boxes becomes larger than the current closest simplex you could find.
Implement a custom distance function that returns nearest neighbors sorted by their closest point. This may require in depth knowledge of the index you are using.

This should still result in a $O(log(numberOfSimplexes))$ unless there are a lot of elongated geometries with overlapping bounding boxes. For example, a bad case would be a spherical data space with all geometries being lines that represent the diameter.
By intuition, I think R-Trees or the PH-tree are best suited for this kind of search.
I have little experience with this, but for larger dimensionality $k$, the bounding box approach may work less well because boxes in $k$-dim space tend to become very large, so they may be a lot of overlap (or maybe not, because the whole dataspace is also growing exponentially?).
In any case, it can make sense to break up 'flat' objects (such as line segments in 3D) in to multiple segments in order to represent them with a chain of smaller bounding boxes instead of one large bounding box. Having several small bounding boxes if more efficient than one large one.


Expressing a logical constraint in integer programming

Let $x \in [-10,10] \cap \mathbb Z$ and $y \in \{0,1\}$. Suppose that

$$y = \begin{cases} 1 & \text{if } x \geq 3\\ 0 & \text{if } x \leq 2\end{cases}$$

To ensure that $y \neq 0$ when $x \geq 3$, use

$$y \geq \frac{x-2}{8}$$

To ensure that $y \neq 1$ when $x \leq 2$, use

$$y \leq \frac{x+10}{13}$$

Pictorially,

The trivial inequality constraints are $-10 \leq x \leq 10$ and $0 \leq y \leq 1$. Lastly, the integrality constraints $x, y \in \mathbb Z$ should not be forgotten.


Misconception in taking Pumping Length of language {a} to be $2$

Informally, the pumping lemma for regular languages state that any sufficient large string may be pumped.

Your language is finite, meaning if you pick a pumping length that is larger than any string in your language, the lemma is trivially true. In your example the pumping length is $2$ but there are no strings in your language of length at least two. So you can pump all strings of length $2$ or longer (there are none!).

If you try and pick a smaller pumping length (the only possibility is $1$) then you will find that you can not pump. $w = a$ is your only string and the only possible decompsition $w=xyz$ is $x=\epsilon$, $y=a$, $z=\epsilon$. You can't however pump that because e.g. $\epsilon$ and $aa$ is not in your language.

Therefore; $2$ is the minimal pumping length of the language $\{a\}$


An intuitive explanation for LR grammars?

A language is $LR(k)$ if looking at the right side of a production, and looking $k$ symbols ahead, one can determine the left hand side of the production. This is quite incomplete, but intuitively easy (hah!) to grasp. In particular, it explains why $LR$ grammars are a much richer set than the $LL$ ones.

In practice, it is probably much more relevant to be able to understand the format in which your preferred LR parser generator spits out item sets when tickled the right way, and in particular how to track down the origin of conflicts and alternative ways to solve them (and their consecuences). I like the bison manual a lot in this regard.


Is there a 'string stack' data structure that supports these string operations?

I thought for quite some time, but didn't find the problem with doing all of your operations in the most stupid possible way in a trie-like DAG structure:
Add-Prefix-Set
Create a trie of strings from $T$. Connect each leaf node to the root of the old trie.
Complexity: $O(|T|)$
Merge
Unite roots of two structures: make all children nodes of the second root children of the first node. You may now have multiple edges marked with the same character going from the same node.
Complexity: $O(1)$
Lazy update of the root

For each character unite all children of the root accessible by the edges marked with this character. ($O(|\Sigma|)$ + Amortized $O(1)$ for each edge ever added)
Delete all edges going into the root from the top. (Can happen after Remove-prefixes, amortized $O(1)$ for each edge ever added)

Get-prefixes
Lazy update the root. Now find all children of the root and report set of letters on edges going to them.
Complexity: $O(|\Sigma|)$
Remove-prefixes
Lazy update the root. Unite all children of the root and set the root pointer to the result of this unite. Lazy update the new root.
Complexity: $O(|\Sigma|)$ + Lazy update
Persistence
All information about this data structure can be saved in arrays, with $O(1)$ information per node plus $O(|\Sigma|)$ information for each child of the node. Each operation can be held out as set of assignments in these arrays. Use persistent range tree or any other data structure that can be viewed as a persistent array. Additional multiplier for memory and space complexity $O(log N)$, where $N$ is the total number of characters in all queries.


Variant of TSP: allow each vertex to be visited at most twice

Let $T = (V,d,k)$ be an instance of Metric-TSP, where $V$ is a vertex set, $d: V\times V \rightarrow \mathbb{R}_{\geq 0}$ is a distance with triangle inequality, and $k\in \mathbb{R}_{\geq 0}$.

Suppose that $T$ is a positive instance of Metric-TSP (i.e. there exists a tour with total length $\leq k$. Then $T$ is also a positive instance for your variant (just take the same tour).

Suppose $T$ is a positive instance of your variant, and let $t = (v_1, v_2,\ldots,v_r)$ denote a "tour" with total length $\leq k$. Whenever there is a vertex $v$ which appears twice in $t$ one can safely delete one of the two appearances as every vertex will still be visited and by the triangle inequality the total length of $t$ can only decrease. Once you have deleted all the duplicates, you are thus left with a tour of length $\leq k$, which shows that $T$ is also a positive instance of Metric-TSP.

Thus, there is a trivial reduction (namely the identity) from Metric-TSP to your variant. As Metric-TSP is NP-complete and your variant is in NP, your variant is also NP-Complete.


Algorithm to determine if an interval is covered by a list of intervals?

I don't know if it's the most efficient algorithm, but here's my suggestion:

Your problem is somewhat similar to balancing parenthesis: you can put all $s_i$ and $e_i$ values on a list and sort it (Lets call this list $V$), but keep the type of each element ($s$ or $e$ element) attached to the value. Then use this list to integrate all the intervals with the following algorithm (uniting overlapping intervals to one interval):

create a list of intervals L, Create a stack St
for every element n in the sorted list V (from the smallest to the largest)
{
    if n is an s element and St is empty
    {
         create a new interval I (a pair of numbers)
         assign I.s = n
         push some value to St
    }

    else if n is an s element and St isn't empty
    {
         push some value to St
    }

    else if n is an e element (stack can't be empty here)
    {
         pop a value from St
         if St is empty
         {
               assign I.e = n
               add interval I to the interval list L
         }
   }
}

return L

Now you have a list of integrated intervals, and checking if $[a,b]$ si covered by one of them is easy: for every interval $I$ in $L$, check if $a \geq I.s$ and $b \leq I.e$ (there are no overlapping intervals in $L$ now, they were integrated in the previous step).

Integrating the intervals to create $L$ takes $O(n)$ computation time and so is checking if $[a,b]$ is covered by one of the intervals in $L$, which makes the sorting $V$ the most expensive task here, $O(n\log{n})$.

Hope this helps, though there might be a linear time algorithm for performing this task...


No, you can't say that, because $O$ doesn't mean "For small inputs, [something] happens" and $\Theta$ doesn't mean "For some inputs, one of the functions is bigger and, for other inputs, the other one is." In mathematics, it is essential to use the actual definition of the concepts that you're working with, and to prove that the definition applies in your situation.


Try to think in terms of binary search:
Start by checking half the cake. Then, if you didn't smell vanilla, you can be sure the first half does not contain vanilla, hence we don't need to check them anymore - hence we save time. This was only intuiton to why it might be possible to do better than $O(n)$, not the actual solution for it.
But something important to note is that any algorithm better than $O(n)$ must depend on $k$. Its not hard to show a lower bound of $\Omega(k)$


What can distributed computing do besides parallel computing?

Distributed computing can be seen as a special case of parallel computing with some additional features and restrictions, some of which I'll outline here.

Multiply IO throughput

In some settings, e.g. databases, IO is the main limiting factor of performance, e.g. hard drive accesses. By serving requests on many machines, you can parallelise hard drive accesses (not possible in typical many-core machines).
Avoid slow IO

Real machines have technical limits regarding quick memory. These limits change constantly, but at any given point in time every machine can only hold so much data in RAM. A distributed system can be scaled so that all data resides in RAM, thus eliminating the need to resort to slower mediums.
Focus on throughput over response time

When faced with many small requests already dominated by, say, IO, you can not speed up individual requests anymore. Having multiple nodes serve requests can increase throughput.
Redundancy

Many nodes should be able to serve any given request so you can perform load balancing.
Consistency

When a requests not only retrieves but also changes data, many nodes may need to be informed of these changes. This is probably the factor with the most impact on performance.
Failure tolerance

The system as a whole should be robust against failure of individual nodes, i.e. continue to work (if with reduced throughput). This is not trivial since you can typically not hold all data on all nodes.
Communication cost

In a distributed system, nodes typically communicate over some kind of network. Delays in the order of milliseconds (typical response times in Ethernet) are prohibitive for systems/algorithms that require frequent communication. In specialised network implementations, wire length actually becomes a significant factor in delay times even inside a single server farm.
Security

If you don't control all aspects of the network connecting your nodes, the inner workings of your system are open to outside attack.

Note that all of these are interconnected.


It can be done. Here's a presentation explaining the language and how the compiler works (so far).

You can play with an asm.js version at http://hackerfoo.com/eval.html


O(1) distinct elements in an array implies?

Essentially, it means no matter what the size of the array is (namely, no matter what $n$ is), it will have no more than a fixed constant number of distinct elements. This assumes that you know what the term $O(1)$ means. If not, ask for clarification.


Turn biased random number generator into uniform

For general $p$ you can't generate a random bit using a finite number of samples. Indeed, suppose you could do it using $n$ samples. Let $c_k$ be the number of inputs of Hamming weight $k$ which will cause you to return $1$. For your generator to be unbiased, you need
$$ \frac{1}{2} = \sum_{k=0}^n c_k p^k (1-p)^{n-k} = \sum_{\ell=0}^n \left(\sum_{k=\ell}^n c_k (-1)^{\ell-k} \binom{n-k}{\ell-k} \right) p^\ell. $$
If $p$ is transcendental or of the form $a/b$ for odd $b$ then the equation $\frac{1}{2} = \sum_{\ell=0}^n d_\ell p^\ell$ has no integer solutions $d_0,\ldots,d_n$. In particular, even if you know $p$, then in these cases no finite number of samples can be used to extract even one uniformly random bit.

The standard solution, attributed (IIRC) to von Neumann, is to use the following algorithm:

Repeatedly sample two biased samples $r_1,r_2$ until $r_1 \neq r_2$.
Return $r_1$.

Conditioned on $r_1 \neq r_2$, the two outcomes $(r_1,r_2)=(0,1)$ and $(r_1,r_2)=(1,0)$ have the same probability, and so the result is an unbiased bit.

How efficient is this generator? The probability that $r_1 \neq r_2$ is $2p(1-p)$, and so on average you will need $1/(2p(1-p))$ samples per bit. Compare that to the optimal extractor given by Shannon's source coding theorem: extracting $n$ bits should take $n/H(p) + o(n)$ samples with high probability (when $p$ is known).

The plot shows that the von Neumann algorithm is reasonably good but not optimal.


Following your idea, you can do this:

Iterate through the (sorted) list.
For every item, flip a coin until you get a $0$. The item's level is the number of $1$s you got; create the tower of pointers and link already created towers accordingly.

For every item, the expected level is $\frac{1}{p}$ with $p$ the probability of a $1$ (geometric distribution); therefore, every item causes constant runtime in expectation, resulting in a total expected runtime in $O(n)$ for creating the list. As the maximum level is $\log_{1/p} n$ in expectation and you only need to remember the last (dangling) pointer for every level, the algorithm requires only $O(\log_{1/p} n)$ additional memory in expectation.

Note that the resulting list is not stricly "ideal" but in expectation; the interesting operations have logarithmic expected runtime due to the resulting distribution. See William Pugh's Skip Lists: A Probabilistic Alternative to Balanced Trees (1990) and the work referenced there for details.

It is clear that there can be no algorithm that works in expected time $o(n)$; in expectation, there have to be $\frac{n}{2}$ items on level two so at least that many have to be investigated (in expectation).


There is no such test.  All automated tests for examining the randomness of a PRNG have limitations.  If you read some papers in the literature that propose PRNGs, you might notice that they do more than just run an automated test against their scheme.

Of course you can always write up anything at any time.  For the research community to find it interesting, or for practitioners to find it useful, it will probably take more than just passing an automated test.   Getting a paper to be accepted at a quality peer-reviewed conference will probably require the reviewers to find it novel and interesting.  For your PRNG to be adopted in practice, your PRNG will probably need to be better than existing ones in some relevant respect (perhaps it is faster and the quality of the pseudorandomness is "as good" in some sense as existing schemes; or better in some other way that implementors care about).


Concatenation property of regular languages

$L \Sigma^* = \emptyset \Sigma^* = \emptyset = L$

$\Sigma^*L = \Sigma^* \emptyset = \emptyset = L$

$L \Sigma^* = (S \Sigma^*)\Sigma^* = S \Sigma^* = L$ for all languages $S$

$\Sigma^* L = \Sigma^* (\Sigma^* S) = \Sigma^* S = L$ for all languages S

$L \Sigma^* = (\Sigma^* S \Sigma^*) \Sigma^* = \Sigma^* S \Sigma^* = L$ for all languages $S$

$\Sigma^* L = \Sigma^* (\Sigma^* S \Sigma^*) = \Sigma^* S \Sigma^* = L$ for all languages S.

In short: there are infinitely many distinct languages where appending the language to $\Sigma^*$ (front or back) will yield the same language. An infinite family of such languages is given by $\Sigma^* S \Sigma^*$ where $S$ can be any language whatsoever.


Detecting errors changing an odd number of bits using CRC

Recall that we are working modulo $2$. Thus $E(x)$ is a polynomial whose coefficients are $0,1$, and $E(1) \in \{0,1\}$.
By definition, $G(x)$ is a factor of $E(x)$ if there exists a polynomial $H(x)$ such that $E(x) = G(x) H(x)$.
In this case, we assume that $E(1) = 1$. Since $E(1) = G(1) H(1)$, this forces $G(1) = 1$.


What are the exponential alternatives that are skipped in dynamic programming for longest increasing subsequence?

Go over all $2^n$ subsequences. For each one, check whether it is increasing.
There are two meanings of subsequence: contiguous subsequence and arbitrary subsequence. For example, $1,3$ is a non-contiguous subsequence of $1,2,3$.
Formally, a subsequence of $a_1,\ldots,a_n$ is a sequence $a_{i_1},\ldots,a_{i_m}$ for some $1 \leq m \leq n$, where $1 \leq i_1 < \cdots < i_m \leq n$. A subsequence is contiguous if it is of the form $a_i,a_{i+1},\ldots,a_j$, that is, if it contains all elements from $a_i$ to $a_j$.
A sequence of length $n$ has $2^n-1$ subsequences, only $\binom{n+1}{2}$ of which are contiguous.
For example, here are all subsequences of $a,b,c$:
$$
a \\ b \\ c \\ a,b \\ a,c \\ b,c \\ a,b,c
$$
Of these, only $a,c$ is not contiguous.


BFS Algorithm for Finding Minimum Steps for Knight Eliminating a Moving Pawn

It's very simple.

A pawn has a choice to move one or two positions forward in its first move, in all following moves it moves one position. A knight moves two squares in one direction, and one step orthogonal.

As a result, the colour of a pawn's square changes on every move, except on the first move, where it has a choice to change the square's colour or not. The knight always changes the colour of its square. So in its first move, the pawn moves to the same colour as the knight, and from then on, the knight can never take the pawn.

(You need to specify what should happen if the knight is in the pawn's way so it cannot move though. If the rule is that the pawn just doesn't move, then the knight can block the pawn's path, and two moves later takes the pawn).


Your examples do not look correct according to my understanding of the definition of CNF.  The first formula is CNF; it has two clauses, each with a single literal.  I would say that the second isn't, but the equivalent formula p is.  See https://en.wikipedia.org/wiki/Conjunctive_normal_form.


I'm not aware of any implementations of planar subgraph isomorphism algorithms, sorry. Note that "SubGemini", which is a (1993) circuit/netlist-oriented subgraph isomorphism solver, doesn't use a planar algorithm, seemingly because they did not want to make planarity assumptions.

For subgraph isomorphism in general (i.e. not planar), the practical state of the art seems to be:

Lee, J. et al. (2012) "An In-depth Comparison of Subgraph Isomorphism
Algorithms in Graph Databases". The paper says they've released source code for their [re]implementations, but I'm having trouble find it... so you may want to email the corresponding author.
Solnon, C. (2010): "AllDifferent-based Filtering for Subgraph Isomorphism." Its implementation is found in LAD.
Cordella, L.P et al. (2004) "A (sub)graph isomorphism algorithm for matching large graphs"; this is basically describing the implementation in vflib and in NetworkX.

All of these papers have experimental results, so you can get an idea what problem sizes they can handle (which might not be a bad idea to specify in your question).

The paper by Dorn (2009) suggested by Luke Mathieson above seems your best bet if you want to implement planar subgraph isomorphism, but that paper has no experimental results, so... you'll probably be the first to experiment with it.

Alternatively, since we're talking subcircuit extraction (SCE) here, you could look at  Jiang and Bunke's Marked Subgraph Isomorphism approach for SCE. The assumption there is different than planarity:

  In this case we know a priori that the degree of some vertices is preserved under the subgraph isomorphism mapping. This information is explicitly utilized to develop a polynomial-time algorithm.

I'm a bit skeptical about the applicability of that paper to real-life SCE because the paper was published at somewhat obscure workshop that is not even circuit-focused... But they claim to have soundly beaten SubGemini. The subgraphs searched there are pretty small, a 6 node cell (presumably 6T SRAM cell) is searched and found (in many copies) in a RAM array of several thousand copies. If your application looks like this... it might be what you want.

The 2003 IEEE Potentials article about SCE even though co-authored by Frank Harary alas ignores this paper of Jiang and Bunke entirely, which not really a surprise to me given where it was published. You may want to read that brief for pointers to other approaches to SCE, including genetic algorithms, neural networks etc. A couple of SCE papers indicated in that brief as claiming good practical results are:

Chang et al.'s DECIDE "A novel subcircuit extraction algorithm by recursive identification scheme"
Zhang and Wunsch "A fuzzy attributed graph approach to subcircuit extraction problem".

Not covered in that review because it's slightly newer is FROSTY; it works by matching smaller directed (sub)graphs by doing a first pass identifying gates. In its paper, results are only compared to SubGemini though, which isn't that hard to beat.

Somewhat similar (in the sense that it relies on higher-level graphs that are in a certain sense directed) but broader in scope (in the sense that it handles both exact and approximate matching) is "Pattern Search in Hierarchical High-Level Designs" by Terem et al. from Intel + Moshe Vardi. The way they handle both exact and approximate matching is setting up both problems a constraint satisfaction problems.

Also probably worth looking at is a series papers by N. Rubanov 2006; 2002; his methods are probabilistic, but they all beat SubGemini by orders of magnitude. Rubanov worked in the EDA industry (Circuit Semantics, Magma Design Automation, Cadence).

There also three fairly recent Oracle (prbably Sun labs) patents by Douglas C. Meserve in this area: US7958468,
US7861193,
US8788990. I couldn't find any academic publication related to these patents.

The most recent comprehensive SCE work I found (insofar) is a 2009 Ph.D. thesis "Hierarchical Pattern Matching in VLSI" by M. Miloševic.

As an interesting addendum, SubGemini is based on the Conneil and Gotlieb partitioning, which has its issues, in these sense that its correctness is based on a conjecture that was eventually proved false by counterexample.


Hint: The obvious thing to do would be to have two vertices $v^+,v_-$ per variable and one triangle per constraint. You might have to tweak this construction a little to avoid the possibility that both truth values are selected for some variable. You can do this using a "gadget", one per variable, that forces the selection of at least one truth value per variable.


How to best maintain a sorted list from a stream of integers?

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access.  Augment the data structure to store, in each node, the number of values stored in the subtree under that node.  Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.