Determining whether $ L = \{ 0^n1^{n^2} | n \ge 0 \} $ is a CFL

Let $h\colon \{0,1\} \to \{0\}$ be the homomorphism given by $h(0) = \epsilon$ and $h(1) = 0$. If $L$ were context-free, so would $h(L) = \{ 0^{n^2} : n \geq 0 \}$ be. Since $h(L)$ is a unary language, it would be regular. However, a unary language is regular iff it is eventually periodic, which it isn't. Therefore $L$ cannot have been context-free.

More generally, if $L$ is context-free then:

The set of lengths of words in $L$ is eventually periodic.
The set of number of occurrences of a symbol in $L$ is eventually periodic.

The most general statement of this kind is Parikh's theorem.


Mathematical function vs Computer program

So, the notion of mathematical function is broader than that of a computable function i.e. one you can write in a programming language. There are some mathematical functions which can't be written as programs, such as the function from binary encodings of Turing Machines to booleans representing whether that machine halts on every input.

A Turing machine can be thought of as a function in one of two ways. In case 1, it's a function from its alphabet $\Sigma^*$ to the set ${\top, \bot}$ of boolean values, where the value for an input string is either true if the machine accepts, or false if it does not. This is also what corresponds to a decision problem in formal language theory. The second, more complex way, is where we see a Turing machine as a function from $\Sigma^*$ to $\Sigma^*$, where the value for an input string is whatever value is on the tape at the time of termination.

Note that all other types of Turing machines, such as non-deterministic, multi-tape, etc. can be converted into a deterministic one. (Unless you get something really weird that can do infinite computation in finite time). Also, you can encode most mathematical data in strings, but things get complicated for things such as real numbers or certain infinite sets.

The lambda calculus interpretation is more straight-forward. The lambda calculus is a term rewriting system, where everything is a function. A lambda calculus expression can usually be taken to a normal (irreducible) form through some sequence of $\beta$ and $\eta$ reductions. (Beta-reduction is basically just substituting values for arguments, eta is just writing $\lambda x . f x$ as $f$).

So, every lambda-calculus expression $f$ can be viewed as a function from lambda-calculus expressions to lambda-calculus normal forms, where the value of $f$ with argument $a$ (some other expression) is the normal form of $f a$. Again, most things, like integers, strings, etc, can be encoded in the lambda-calculus, but some things, such as real numbers, are more tricky.

Now's where things get fun. This is all assuming a lambda-calculus or Turing-machine model. What these are very bad at modelling is IO, or some interaction with the outside world.

The Haskell approach to this is to view these as pure functions with some "world" argument, which gets destroyed every time it's updated (a new world state is created).

Likewise, for something like interactive programs, you can stretch our definitions and model the pixels shown on the screen, the files written to disk, the audio waves played, etc. as bits which are part of the program's output.

For example, consider a Python program which prints the current date and time $n$ times for some argument $n$. At first glance, this isn't a function, since you can give it the same $n$ and get a different result. However, if you view the state of the world, namely the current date and time, as an argument to the program, then it always does give the same result for the same input, it's just that input is physically impossible to reproduce because we don't control the passage of time. (You could fudge the computer clock if you wanted, but you can apply the same principal to physical sensors and such).

So, let's look at your four specific questions.

Yes (see 2 below).
Yes, by expressing that program either as a Turing Machine or $\lambda$-calculus expression.
No, see 4.
No, assuming that you model programs with IO as taking the entire state of the world as input and outputting a new state of the world as output. Otherwise, yes.

You have to be careful, because some languages, such as Prolog, let you write something that's closer to a relation than a function. But at the end of the day, if you massage the notation enough you get something that is a function.


Generalizing the Comparison Sorting Lower Bound Proof

The decision tree method for proving lower-bounds (like the $\Omega(n \lg n)$ lower-bound for comparison based sorting you mentioned) are often called information theory methods.

Here is a short video by Faith Ellen about this method:

Lower-bounds, Part 2/4: Information Theory

The first part is here:

Lower-bounds, Part 1/4: Introduction, Decision Trees


$U = \{ \langle M, x, \#^{t} \rangle \vert M $ is a NTM that accepts $x$ within $t$ steps on some branch$\}$ is NP complete

Finding the running time of a given Turing machine is undecidable. Luckily, you don't need to find the actual degree. You only need to show the existence of a reduction from $A$ to your language, not to construct a procedure that given a description of $A\in\mathsf{NP}$ (say, as the encoding of its verifier), will output a reduction from $A$ to your language.

Think of it this way, let $\{f_n\}_{n\in\mathbb{N}}$ be a sequence of functions, where $f_i(x)=\left(M_A,x,\#^{|x|^i}\right)$. One of the functions in this sequence is the reduction you're looking for, and I don't need to point out which one (note that I can specify it in terms of the degree of the polynomial in the running time of $M_A$).


No known cryptographic hash functions are provably secure. It might seem to be hard to reconstruct an input hashing to a given hash value, but we can't prove that it is indeed very hard. We can just say that no one was able to find an algorithm accomplishing that so far, but there is no guarantee that tomorrow such an algorithm won't be found.

In cryptography there is a very exact definition of one-way functions, which implies, among else, that P$\neq$NP. While there are several specific functions which are conjectured to satisfy the definition, no one knows how to prove this. We don't even know how to prove that one-way functions exist assuming P$\neq$NP.


Estimating the time until we obtain five-in-a-row?

Just for fun, I coded this up in Mathematica. I started with a $10 \times 10$ matrix initialized to all zeros. I then considered two processes throwing darts in the cells: (1)  a cell is chosen uniformly and independently at random from the set of all cells, and (2) a cell is chosen uniformly and independently at random from the set of all empty cells. When a  dart hits a cell, the value of that cell is set to $1$. A five-in-a-row can appear on a row, column, the diagonal, or on the antidiagonal.

For both processes, I ran $N = 20000$ simulations. Rounded up to the nearest integer, for process (1) we need $65$ dart throws on average to obtain a five-in-a-row. For process (2), the same number was $47$.

This is not exactly what you were asking for, but maybe you can at least compare the numbers you get with mine.


Floating-point oblivious way to compute multiset numbers

One common way to work with binomial coefficients without overflow is to use prime factorisation.
Legendre discovered the formula for this, and it is worth proving it for yourself. The factorial of a number can be factorised as powers of primes:
$$n! = p_1^{q_1} p_2^{q_2} \cdots$$
where:
$$q_i = \sum_{k=1}^{\left\lfloor \log_{p_i} n \right\rfloor} \left\lfloor \frac{n}{p_i^k}\right\rfloor$$
Instead of multiplying and dividing, therefore, you can just add and subtract exponents of primes.


What is the intuition behind the Potential Function in Amortized Analysis of some algorithm?

Imagine filling up a huge water tank. Now when you open the faucet you have nice water pressure. The pressure will last probably until the tank is almost empty (depending on its size). At that point you need to refill it to have your constant pressure again, so you make the effort again.

The potential function is the water tank. You do some work that will "last" for a while and "store" the energy used in the potential function, e.g., allocating an new array in dynamic arrays/tables. You won't need to do any more work for a while, e.g., until the size of your array grows too much or shrinks too much. At that point you have used all the energy in your potential function (all the water is gone) and need to recharge (refill the tank).

As far as designing such a function, let's take as example the case of a dynamic array. The main point to bring home here is that the potential function Φ is linear in the input size. The coefficients and constant values matter to a certain point (in physics, what really matters is the derivative of the potential function, or the difference between values of the potential function in different points, so additive constants don't really matter in general). We know the function is linear in this case because the expensive operation that we want to amortize is a linear operation (resizing of the array) and we want to prove that this operation determines the cost of a sequence of operations. So, from a practical standpoint, we could have written Φ = a*n + c, performed our analysis and then assigned reasonable values to our two constants so that the potential is always positive. Note that these coefficients might heavily depend on the details of the algorithm/data structure being analysed. For example it's be interesting to try and change when the array gets resized and the amount by which it gets resized and see if the function still hold and also if the linearity still holds. This is discussed in CLRS.

It's also worth noting that, although possible, it might be impractical or tedious to apply amortized analysis to any algorithm. In many cases simpler approaches, e.g., the use of the master theorem, will suffice. The potential method works well for cases like the dynamic array, where you have an expensive operation that you are trying to "amortize" over a sequence of operations, thus not all the operations have the same cost, but the overall cost of performing a given sequence of operations is well defined (linear in this example).


Question for "Only if" part for the theorem "A language is Turing-recognizable iff some enumerator enumerates it."

A language is Turing-recognizable (or Recursively enumerable) iff there exists a Turing Machine which will enumerate all valid strings of the language.

What you probably miss in the above proof is the fact that $i$ can take any value ... when we say $i$ steps, we can mean $10$, $100$, $100000$, $\infty$ steps.
Basically $i$ is an index that indicates the number of words in the language; the enumerator $E$ could very well run forever (if the language has an  infinite number of strings).


The so-called Kohen–Kong theorem (described and attributed, without citation, to X.P. Kong and E.G.D. Kohen by Stewart (1994) (PDF); sometimes apparently misspelled as the "Kohen–Kung theorem") says that the path of Langton's ant can never be periodic (and, as a corollary, also cannot be bounded).

The proof is fairly simple, as the result follows directly from the following observations:

The path of the ant is (ultimately) periodic if and only if it is bounded.  (Clearly, an unbounded path cannot be periodic.  Conversely, if the ant would stay forever in a bounded region, there would be only a finite number of states in which the ant itself and the squares within that region could be, and therefore eventually the whole system would have to return to an earlier state.)
Since the ant turns 90° after every step, the direction from which it enters the next square alternates between horizontal and vertical.  To return to a particular square after once leaving it, the ant must travel an even number of steps.  Thus, if the ant once enters a given square horizontally (or vertically), it must always enter that square horizontally (or vertically).

Now, if the ant's path was periodic (and thus bounded), there would have to be a square that the ant visits repeatedly, but whose top and right neighbors the ant never visits during its periodic path.  (To find such a square, just start from any square the ant is known to visit, and move up or right to adjacent visited squares as long as you can.  Since the ant's path is, by assumption, bounded, this process will always terminate.)  Thus, the ant must always either enter this square from the left and leave downwards, or enter it from below and leave left.  But this means that the ant would have to always turn in the same direction after entering this square, which is impossible by definition.


Is there any way to get "around" the halting problem?

Say that two programs are equivalent if they have the same halting behaviour and output on every input.  The problem for your "finite exceptions" idea is that there are infinitely many programs equivalent to any program you choose.  Given a program $P$, we can always modify it in infinitely many ways without changing its output or halting behaviour: for each natural number $n$, we can write a program that essentially counts to $n$ and then runs $P$.

I suppose the good news is that this means we can decide the halting problem on an infinite class of programs. For example, let $P_n$ be the program for i = 1 to n do [nothing]; halt;: the halting problem is easily decidable on the set of all programs $P_n$.


There is an intimate connection between closure operators and complete lattices.

Given a closure operator $C$ on a set $X$, we can construct a complete lattice $L(C)$ as follows:

The points of the lattice are the fixpoints of $C$.
The meet of the lattice is $A \wedge B = A \cap B$.
The join of the lattice is $A \vee B = C(A \cup B)$.

Conversely, given a complete lattice $L$ of subsets of $X$, we can construct a closure operator $C:=C(L)$ on $X$ using the formula
$$ C(A) = \bigcap \{ B \in L : B \supseteq A \}. $$

It turns out that these two operators are inverses:
$C(L(C)) = C$ and $L(C(L)) = L$.

In particular, this shows that $C$ is determined by the set $L(C)$ of fixpoints, since
$$
C(A) = \bigcap \{B \in L(C) : B \supseteq A\}.
$$

(This information is taken from the sample chapter of M-solid varieties of algebras by Koppitz and Denecke.)


Training given pairs of similar values, not labels

I'm not convinced that a neural network is necessarily the right tool for this.  When you have a hammer, it's tempting to think that everything looks like a nail... but sometimes the answer is "No, you dummy, that's a screw, use a screwdriver, not a hammer."

So, I'll comment on several kinds of methods you could explore, for your problem.  I suggest you look into them all and see which works best in your specific application.

Clustering

It looks like your problem is basically a clustering problem.  There are many standard algorithms for clustering data.  For instance, if your space is $S=\mathbb{R}^n$, many clustering algorithms are known.  There are also many clustering algorithms known that can work on any metric space.  I recommend you take a look at https://en.wikipedia.org/wiki/Cluster_analysis to familiarize yourself with some of the standard methods, and look to see whether any of them might suit your application well.

Neural networks and autoencoders

If you are set on using a neural network (which, again, might not be the right attitude), an alternative approach might be to learn an auto-encoder for the data.  This is a standard way to use neural networks for unsupervised learning.  This basically asks the neural network to find a way to project high-dimensional data down to some lower-dimensional space, in a way that preserves as much as possible of the structure of the original data.  Empirically, it often seems to be an effective way to do unsupervised learning.

You could train a neural network in this way, and then use it to project your inputs to the lower-dimensional space and measure distances in the projected space.  There are standard training algorithms to fit an autoencoder.

See also https://en.wikipedia.org/wiki/Neural_network#Unsupervised_learning and https://en.wikipedia.org/wiki/Autoencoder.

Metric space embeddings

You might also want to look into the literature on metric space embeddings.  A metric space embedding is a map $f:S \to \mathbb{R}^n$ from a metric space $S$ to $\mathbb{R}^n$, such that $f$ approximately preserves the distance metric on $S$.  In other words, we seek to find $f$ such that

$||f(x)-f(y)||_2 \approx d_S(x,y)$$

for all or most $x,y \in S$.  This is an embedding into $\mathbb{R}^n$ with the Euclidean norm (or into $\ell_2$ if we don't care about the dimension $n$).

There's been a lot of work on this subject, including the computational aspects of learning/finding such embeddings.  See, e.g.,

https://en.wikipedia.org/wiki/Machine_learning#Similarity_and_metric_learning and https://en.wikipedia.org/wiki/Similarity_learning#Metric_learning
Embedding Finite Metric Spaces into Normed Spaces, Chapter 15 of Lectures on Discrete Geometry by Jiri Matousek.
Distributional Scaling: An Algorithm for Structure-Preserving
Embedding of Metric and Nonmetric Spaces.  Michael Quist, Golan Yona.  Journal of Machine Learning Research 5 (2004) pp.399-430.
The CMU course CS 15-859(J): Algorithmic Applications of Metric Embeddings, especially Lectures 1 and 5.
Finite Metric Spaces - Combinatorics, Geometry, and Algorithms.  Nathan Linial.  Proceedings of the International Congress of Mathematicians III, 2002.
The Geometry of Graphs and Some of Its Algorithmic Applications.  Nathan Linial, Eran London, Yuri Rabinovich.  Combinatorica 15(2), 1995.

I'm not an expert on this subject, so there's probably more relevant work out there (e.g., in the machine learning or systems community).


Runtime of the optimal greedy $2$-approximation algorithm for the $k$-clustering problem

The problem can be indeed viewed geometrically in a way that we would like to cover the $V$ points by $k$ balls, where the radius of the largest ball is minimized.

$O(nk)$ is indeed quite simple to achieve but one can do better. Feder and Greene, Optimal algorithms for approximate clustering, 1988 achieve a running time of $\Theta(n \log k)$ using more clever data structures and further show that this is optimal in the algebraic decision tree model.


Why does the Pumping Lemma Constraint |xy| ≤ p mean that y can't be 1 in the string 0p1p

Let $p$ be the pumping length of your language.
As you say, the string $s$ can be written as $s = xyz$ where $|xy| \le p$.
By the choice of $s=0^p 1^p$, you know that the first $p$ characters of $s$ are all $0$, therefore $xy$ (which contains at most $p$ character) must be a string containing only $0$s.
Since $y$ is a suffix of $xy$, $y$ must also contain only $0$s.


Counterexample for equality in Quantified Boolean Formula

The equality is correct for $n=1$, so let's take $n = 3$. Let $f(x_1,x_2,x_3) = [x_1 \neq x_2]$. Statement $B$ states that for every $x_2$ there exists $x_1 \neq x_2$, which is correct. Statement $A$ states that there exists $x_1$ which is different from all $x_2$, which is incorrect.


Lambda calculus without free variables is as strong as lambda calculus?

I'm assuming you are referring to the untyped lambda calculus.

If so, write $\newcommand{\num}[1]{\ulcorner #1 \urcorner}\num{n}$ for the Church numeral of the natural unmber $n$.

It is known that there exists a closed term (i.e., without free variables) $TM$ such that
$$
TM\ \num{i}\ \num{n}\ =_{\beta\eta}\ \num{m}
$$
if, and only if, the $i$-th Turing machine (in some standard enumeration) run with input $n\in\mathbb N$ (encoded as usual) halts returning $m$ as output.

Indeed, writing $TM$ is a standard "programming" exercise in the lambda calculus. For that, one can represent the tape as a pair-or-pairs-of-pairs-of... (AKA a cons list) of symbols. Then a "stepping" subroutine to advance the tape and the TM state can be written. Finally, the stepping subroutine is invoked until a halting state is reached. This last step can be achieved using a fixed point combinator such as $Y$.

Since we can simulate any Turing machine, we get Turing completeness.

Alternative proof, which is (in my opinion) easier to actually perform in full detail: prove that any general recursive function can be $\lambda$-defined using a closed lambda term. For that, proceed by induction on the definition of general recursive function.

Indeed, even if you do not aim for closed terms, in this programming exercise you will obtain a closed one in a natural way. After all, when programming one never needs a variable which was not declared beforehand.

Since the general recursive functions are exactly those which can be computed by a Turing machine, we get Turing completeness for the closed lambda calculus.


For $n=2$ there is a solution:

Minimize $f(y) = x_1/y_1 + x_2/(k-y_1)$, it is convex for $y_1 >0$ so you can find derivative, solve it for $=0$ and get the solution in reals, then check floor and ceil.

For general $n$ rounding needs more investigation. The only thing I'll mention that the real solution is something like $y_i = k \cdot \frac{\sqrt{x_i}}{\sum\limits_i {\sqrt{x_i}}}$, from the lagrangian. Then you do the $\max (1, \lfloor y_i \rfloor)$ and use other deeper results or greedy discussed to reach the sun to be exactly $k$.

UPD: Using greedy after this step, it will take time at most $n$ steps, resulting in $O(n)$ time. Reminder: add 1 to the $y_i$ where the difference $ \frac{x_i}{y_i} - \frac{x_i}{y_i+1}$ is maximized. Store this differences using priority queue to reuse calculations.


What graph problems are hard to solve even for a small number of verticies?

I recommend you look at a list of NP-complete problems on graphs.  For each one, research whether there exists a known approximation algorithm.  For some problems we have hardness of approximation results (which say that there is no polynomial-time algorithm that achieves approximation factor $\alpha$, unless $P=NP$).  Those are potential candidates that might be of interest.  In particular, I'd recommend you study the standard methods for dealing with intractability, then look for a candidate problem where none of those seem to work.  You might also look at graph problems that are APX-complete as candidates worthy of further exploration.

For instance, graph coloring might be a possible candidate to look at.  I haven't studied that problems so I don't know whether good heuristics exist.  I doubt it will be hard on graphs with only 10-20 vertices, but it might be hard with somewhat larger graphs.


Is an Event Counter essentially an integer version of Barrier?

An event counter can function like a barrier when a set of threads all use the same value to await. For example, 3 threads can perform an await operation on the Event-Counter EC, using the same value. Then await(EC, common_val), and then threads each will block until the EC is advanced to the common value to synchronize with one another.

However, Event Counter along with Sequencers can be used in many other ways as well, while barrier primitives have only this one type of behavior, used only to allow a set of threads to move through multiple steps. Event Counter along with a Sequencer can also make up a semaphore.


Tips.

Any (infinite) unary language has regular prefix language.
$L_1 = a \cdot K$ and similary
$L_2 = b \cdot K$  where $K$ is a well-chosen horrible language.

Question.

What is unary($L$)? If it is what I think, there is an easy example. Powers of two are not context-free: $\{ a^{2^n} \mid n\ge 1\}$.


Suppose G is simple graph with n vertices. Prove that G has twice as many edges as vertices only if $n\geq 5$

When $n \leq 4$, the possible number of edges is less than twice the number of vertices. For example, when $n = 4$, there are 4 vertices but only 6 edges. In contrast, the complete graph on 5 vertices contains 10 edges.


concatenation of context sensitive and context-free is context sensitive or not?

Suppose that $L$ is a context-sensitive language which is not context-free. Then $L\{\epsilon\}$ is not context-free (here $\epsilon$ is the empty word), while $L\emptyset$ is context-free.


Can the loops be in any order in the Floyd-Warshall algorithm?

Suppose that you change the order of loops from $k,i,j$ to $i,j,k$. Let's see what happens when $i=1$ and $j=2$:
for k from 1 to |V|
  if dist[1][2] > dist[1][k] + dist[k][2]
    dist[1][2] ← dist[1][k] + dist[k][2]
  end if
end for

It is not too hard to check that this puts in dist[1][2] the value
$$
\min_{1 \leq k \leq |V|} w(1,k) + w(k,2),
$$
where $w(1,1) = w(2,2) = 0$. This is the cost of the shortest path of length at most $2$ from $1$ to $2$.
The $(1,2)$'th iteration is the only one which modifies dist[1][2], so at the end of the procedure, dist[1][2] will still contain
$$
\min_{1 \leq k \leq |V|} w(1,k) + w(k,2),
$$
which could be arbitrarily off from the real shortest path from $1$ to $2$.


DBMS: MINIMUM NUMBER OF TABLES REQUIRED TO REALIZE THIS ER MODEL

The issue is that it cannot really be answered unless you give more constraints.

It can be implemented using only one table. Ugly but doable. Each record would be the union o fields needed plus one “type” field. There will be very little of help from the database in keeping referential integritet.


Pushdown automaton from given code for parsing a while statement

What you write is a snippet out of a recursive descent parser, one way of writing a program that parses a context free language. It is modelled on a PDA, specifically a LL(1) one. The stack is implicit in the recursive calls your parser does. Recursive descent is popular as it easy to write by hand (some tricks are needed to handle ambiguous constructs, like nested if ... then ... else and expressions, which naturally are represented by left-recursive grammars, but they are well-known) and requires no theory. More powerful parsing methods (like LALR or canonical LR) are too complex to do by hand for realistic grammars (in LL(1)/recursive descent, you can work one production at a time, other methods require considering a much larger part of the grammar). If you look at a typical (LA)LR parser generator's output (ask e.g. for --report=all for bison or -rfor byacc to get a text description, or -g for any of them to get a graphical depiction of the PDA).

Tl;dr: Undestanding PDAs and their relation to the grammar is
useful, but not essential to use the technology.


Universal Turing machine and virtualization technology

Yes and no. Essentially because of the existence of universal Turing machines, you could write a VMWare-like system that used software to simulate the CPU. In reality, though, that would be unbearably slow, so it's not how these products actually work. Instead, they run the code directly on the CPU, in a carefully controlled and hardware-supported environment.


Determining key from plaintext and ciphertext (Vigenère)

A Vigenère cypher on an alphabet of size $M$, which we identify with the integers modulo $M$, works as follows.

The key is an arbitrary word, $k_0 \ldots k_{\ell-1}$.

Given a plaintext $p_0 \ldots p_{n-1}$, the ciphertext $c_0 \ldots c_{n-1}$ is given by
$$
c_i = p_i + k_{i \bmod \ell} \bmod M.
$$
For example, suppose that we are trying to encipher decimal digits, and use as key the word 2019. If we want to encrypt the plaintext 18446744073709551616, then we form the following table:

plain  18446744073709551616
key    20192019201920192019
cipher 38538753274629643625

(In this case $n$ was divisible by $\ell$, but that need not be the case.)

In this table, the key repeats enough times, and each digit of the cipher is just the sum of the digits above it, throwing away the carry (for example, from 4 and 9 we get 3 rather than 13).

To decipher a ciphertext $c_0 \ldots c_{n-1}$, we simply reverse the process:
$$
p_i = c_i - k_{i \bmod \ell} \bmod M.
$$
In the table above, given the cipher and the key, we just need to subtract the key from the cipher, borrowing if necessary (so 3-9=4 since 13-9=4).

Similarly, given a plaintext/ciphertext pair, we can recover the key in the sense of constructing the sequence
$$
k_i = c_i - p_i \bmod M.
$$
This recovers the key up to its length $\ell$, which need not be known in advance.

In the table above, given the ciphertext and the plaintext, we subtract the latter from the former to obtain

201920192019201920192019

Out of which we can guess that the key is 2019.


VAE's have an encoder.  The encoder maps an input to a latent vector. The latent vector doesn't "stick".  Instead, in each iteration, we use the encoder to map to a latent distribution, sample from that latent distribution, then use the decoder to map to a reconstruction, and compute the loss.  Yes, each data point is mapped to its own latent vector.  Yes, you run the encoder anew and sample anew for each point and each iteration of training.

You check for convergence in the standard way for any neural network: you look for the value of the loss function to plateau.


Is it good to define a language $\mathcal{L}$ in NP as a language for
  which, given an element $x$, it is possible in polynomial-time to
  check whether $x \in \mathcal{L}$ or not?

No. If you could do that you could "check" that this language would be in P, because you can check (or more formally decide) all possible words for membership in polynomial time this way.

A correct formulation would be:

  A language $\mathcal L$ is in NP if for every word $x$ in the language there exists a witness $w$ which is of length polynomial in the length of $x$ and given the witness and the word you
  can verify language-membership in polynomial time.

Note that you only need said witness (sometimes also called certificate) need only exist for words that actually are in the language, i.e. you don't need to be able to construct them for negative instances and constructing them is allowed to take super-polynomial time.


What is the theory behind testing fixes for intermittent bugs?

You juggle with "probabilities" without defining any. There are two different questions here.

  For practical programs, can I use random testing to establish that any given execution has close to 100% success probability?

Not in the strict sense, no. Even if input spaces are finite, they are typically huge. Without further information, you'd have to test a lot of inputs (and/or contexts), which is not feasible. As in, solving most NP-complete problems is faster.

You could try to perform statistical testing, that is get some bound on the error for some statistical significance -- but that would assume that you have a model for the error distribution. Which I would be surprised to hear if you had. And even if, it's probably not one of those that mathematicians have bothered to explore. So, ballpark guess, statistical tests are impossible (or meaningless, if you went ahead and did the numbers assuming a normal model or something).

  Can I formalize programs and their execution so that I can make meaningful statements about (stochastic) bug-freeness?

Yes, sure. What you need are

formal semantics,
formal specifications, and
a distribution of inputs.

Then, you can (in principle) prove (not test!) what the expected error rate is. I've never seen it done, though -- probably because it's at least as hard as proving the program correct in the first place.

If you ask me, you are better served with reasonable heuristics and solid processes. Specification testing may be helpful in certain contexts, just because it makes it easy to test many different variants.


Difference between $O(n^2)$ and $O(m)$ for algorithms on graphs

Since $m \in \Theta(n^2)$ in the worst case, $O$-bounds don't tell you much. That is to say, just from these bounds alone, you can't say that $O(m)$ is better than $O(n^2)$ (and the reverse never holds for simple graphs).

However, if you have $\Theta$-bounds then $\Theta(m)$ is properly better than $\Theta(n^2)$ if $m \in o(n^2)$, i.e. you have sparse graphs.

Also, the usual limitations of $O$-worst-case analysis apply: you may actually be interested in typical-case behaviour, constant factors may matter to you, and you need efficiency for finite (small?) $n$.


Fine-Grain parallel algorithm for LU-decomposition

It will be clearer if you look at 1 slide before (10/42). The algorithm does not decide on how do you assign to node. It just says that the algorithm can be consisted of many parallel tasks. Each task has identification of $(i,j)$ and each executes the algorithm in slide (12/42).

More specifically, each task is assigned an entry $a_{ij}$ of the matrix ($n^2$ number of tasks), and at the end of the algorithm that entry becomes $u_{ij}$ if $i \le j$ or $l_{ij}$ if $i>j$.


Why is the A* search heuristic optimal even if it underestimates costs?

A* maintains a priority queue of options that it's considering, ordered by how good they might be. It keeps searching until it finds a route to the goal that's so good that none of the other options could possibly make it better. How good an alternative might be is based on the heuristic and on actual costs found in the search so far.

If the heuristic underestimates, the other options will look better than they really are. A* thinks those other options might improve the route, so it checks them out. If the heuristic only underestimates by a little bit, maybe some of those routes will turn out to be useful. On the other hand, if the heuristic overestimates, A* can think that the alternatives to the route already has are all terrible, so it won't bother to look at them. But the heuristic overestimates so they might be much better than they seem.

For example, suppose you're trying to drive from Chicago to New York and your heuristic is what your friends think about geography. If your first friend says, "Hey, Boston is close to New York" (underestimating), then you'll waste time looking at routes via Boston.  Before long, you'll realise that any sensible route from Chicago to Boston already gets fairly close to New York before reaching Boston and that actually going via Boston just adds more miles. So you'll stop considering routes via Boston and you'll move on to find the optimal route. Your underestimating friend cost you a bit of planning time but, in the end, you found the right route.

Suppose that another friend says, "Indiana is a million miles from New York!" Nowhere else on earth is more than 13,000 miles from New York so, if you take your friend's advice literally, you won't even consider any route through Indiana. This makes you drive for nearly twice as long and cover 50% more distance. Oops.


Does every regular language have a linear grammar?

Answer to the last question of the update.

The grammar $S \to aSb + 1$ is linear, but it generates the nonregular language $\{a^nb^n \mid n \geqslant 0\}$. Therefore, it cannot be converted into a regular linear grammar.


Description for languages that can be solved in time(n)?

We're not good at characterizing languages that can be decided in deterministic polynomial time. There are multiple characterizations of $\mathrm{NP}$ (e.g., nondeterministic Turing machines, polynomial witnesses, existential second-order logic), but $\mathrm{P}$ seems to be just "stuff you can do in polynomial time on a Turing machine."

Similarly, it's unlikely that there's any alternative characterization of linear time beyond its literal definition.

  Furthermore there are regular languages (like any modulo languages) that are not in $\mathrm{TIME}(n)$.

No there aren't. You can decide any regular language in linear time using a DFA (trivially modify its description so it's a Turing machine).


Zero knowledge proof - case of graph 3-coloring (not understanding the concept)

Your misunderstanding stems from stating a wrong protocol for ZK 3-color verification. In fact the protocol is a bit more complex:
The prover first "commits" to colors. This means that he cannot change its commitment afterwards, but at the same time, he does not reveal the colors themselves.
Then, once the verifier asks for an edge, the prover "opens" its commitment, revealing the colors of that edge alone.
Since its commitment is binding, the prover cannot change the colors after committing to them. So if the prover does not have a legal coloring, he must commit to some invalid coloring of at least one edge, and will be found with some small probability.
This is repeated, each time with a new permutation of the colors, and new commitments.


Quantum computer simulators with proper measurements

Based on QCAD's help file, their measurement gates are more like measure-later-suggestions:

  The measurement gates on QCAD only set "measurement flags". After the calculation, the measurement is performed.

I'm very surprised they would return a wrong answer instead of throwing an error. Most simlators won't do this, and if they do it should be reported as a bug.

For example, I use the same cheat in my own simulator (which you can play with in your browser), but I prevent any later operations that would cause the result to differ compared to deferring the measurement. So it lets you hit a measured qubit with a NOT gate, but a Hadamard gate or a controlled-by-unmeasured-qubit NOT gate will be forcibly disabled. Which is frustrating, but at least not misleading.

But Why?

The reason this limitation exists is efficiency. It's the difference between $\Theta(4^n)$ operations and $\Theta(2^n)$ operations needed to simulate a gate applied to an $n$-qubit system. Operations on mixed states are much more expensive to simulate than operations on pure states, and deferring measurement allows the simulation to only use pure states.

Workaround

A simple workaround for this limitation is to include an extra qubit, CNOT the value you wanted to measure onto the extra qubit, then measure the extra qubit. This is mathematically equivalent to measuring the original qubit, but will sidestep the limitation in the simulator that prevents you from then doing more things with the original qubit and still getting the correct result.

Easy Alternatives w/o By-Design Silent Mistakes

Microsoft's LiQui|>

Google's in-browser "Quantum computing playground"

Davy Wybiral's toy in-browser simulator

"Quirk", my own toy in-browser simulator


optimal placement of fixed length items on a given length

Your problem is NP-hard.  The decision problem version of your problem is to ask whether there exists a selection of equipment achieving an excess of $e$ or less (given $e$ as input, and all the lengths).  The special case of $e=0$ is exactly the subset sum problem, which is NP-complete.  Therefore, the decision version of your problem is NP-complete, so finding an optimal set of equipment is NP-hard.  In other words, you cannot hope for a fully polynomial-time algorithm to solve this problem.

If the lengths are not too large, you can adapt the standard dynamic programming algorithm for subset sum to solve your problem as well.  It applies almost directly: the dynamic programming algorithm tells you, for each integer $\ell$, whether there is a way to choose equipment whose lengths sum to exactly $\ell$.  Now you can check whether there is a solution for $\ell=100$, $\ell=99$, $\ell=101$, $\ell=98$, $\ell=102$, etc. (in that order) and take the first solution you find.  The running time will be tolerable if the desired length (e.g., 100) is not too large.


Does Reverse Polish Notation have an LL grammar?

Yes,

$
G = (\{E,S,R\}, \{n,o\}, P, E)\text{, with productions}\\
E \rightarrow n\ |\ SR \\
S \rightarrow nEo \\
R \rightarrow EoR\ |\ \epsilon \\
$

Proof:

Observation $(*)$: Each word of L represents an arithmetic expression, the result of calculating such an expression is essentially again a number. So whenever we have $w \in L$, we can treat $w$ as a number.
Theorems:

$L(G) \subset L$
$L(S) \subset L$
$w \in L(R) \implies w=\epsilon \lor (w=w_1 o, w_1 \in L)$

Inductive proof of above theorems on derivation step count $n$:

Basis $n=1$

$E \Rightarrow n\\
            \land \\
            n \in L
            $
$S\text{ can't generate any words in one step. }\\
            \land \\
            \emptyset \subset L
            $
$R \Rightarrow \epsilon, w=\epsilon$

Basis $n=2$

In all 3 cases nothing can be generated in 2 steps, and the theorems hold trivially.
Inductive step: $n=k>1,$ induction hypothesis (IH): assume theorems hold for $n<k$

$E \Rightarrow SR \Rightarrow^{k-1} w_1 w_2\, \\
           \text{where }w_1 \in L\text{ because of IH of theorem 2,} \\
           \text{and } w_2 = \epsilon\text{ or }w_2 = w_3 o, w_3 \in L\text{ because of IH of theorem 3.}$

First case: $w_2 = \epsilon$, then $w_1 w_2 = w_1 \in L$.
Second case: $w_1 w_2 = w_1 w_3 o =^{(*)} nno$, which is a valid RPN expression, thus $w_1 w_3 o \in L$

$S \Rightarrow nEo \Rightarrow^{k-1} nwo$, where $w \in L$ because of IH of theorem 1. $nwo =^{(*)} nno$, which is a valid RPN expression, and thus $n w o \in L$
$R \Rightarrow EoR \Rightarrow^{k-2} w_1 o R$, where $w_1 \in L$ because of IH of theorem 1. The last step can only be $w_1 o R \Rightarrow w_1 o \epsilon$, which satisfies theorem 3.

$\square$
Theorem: $L \subset L(G)$

Proof: induction on length of $w \in L$, show that $E \Rightarrow^* w$

(I got lazy from this point on, I might fill this in later)

$\square$
$(1) \land (2) \implies L(G) = L$
Theorem: G is LL(k) grammar, $k \in \mathbb{N}$

Proof: Pick a k large enough, then show that for each non-terminal you can decide which production rule to use by looking at the k next terminals.

$\square$

$\square$


The number of executions of the count statement; how many?

Hint: Substitute $j = 2^r$, and use the formula for summing a geometric series.

Make sure that you understand why the substitution $j = 2^r$ makes sense.


Slicing clusters of non-black pixels from an image into separate images

It seems that you're just trying to find the connected components of a graph. In this case, the vertices are the non-black pixels and there's an edge between two pixels if they're at distance at most $d$, for some appropriate choice of $d$ and some appropriate metric (Euclidean distance, Manhattan distance, whatever works best).

(Note that, in terms of implementation, you don't need to construct an explicit data structure for the graph; you can calculate whether there's an edge between any two vertices whenever you need to.)


Does this "reference" problem have a name?

This is disjoint-set data structure.

Here is the summary at Wikipedia. I put the statement about time-complexity in bold font to emphasize its efficiency.

  In computer science, a disjoint-set data structure (also called a union–find data structure or merge–find set) is a data structure that tracks a set of elements partitioned into a number of disjoint (non-overlapping) subsets. It provides near-constant-time operations (bounded by the inverse Ackermann function) to add new sets, to merge existing sets, and to determine whether elements are in the same set. In addition to many other uses (see the Applications section), disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

There are many tutorials for this data structures on the web, such as the one at TopCoder and the one at GeeksforGeeks.


Differences between basic, complex and terminological facts in a Knowledge Base using First-Order Logic

In §3.2 they distinguish between the following four grammatical categories, with some examples:

Predicates: Woman, Rich, Beautiful, Bankrupt
Relations: LivesAt, HadAnAffairWith, Loves
Functions: fatherOf, bestFriendOf, ceoOf
Individual constants: maryJones, johnQSmith, tomsHouse

In the background they have first-order logic with identity, which means they allow for quantification only over individual variables. Within this machinery, in §§ 3.3–5 they introduce the three types of facts.

  Basic facts are the atomic sentences and their negations.

The atomic sentences are those sentences which are made of:

a [predicate] + an [individual]. E.g.: Woman(maryJones)
an n-ary [relation] + n [individual]s. E.g.: Loves(maryJones, tomsHouse)
an [individual] + "=" + an [individual]. E.g.: maryJones = marySmith

Note that functions applied to individual constants also denote individuals (e.g., fatherOf(maryJones) is some individual), that's why clauses (1–3) include the word 'individual' rather than 'individual constant' so as to allow also for functional expressions denoting individuals. The negations of atomic sentences are defined as follows: a sentence ¬S is a negation of an atomic sentence iff S is an atomic sentence.

  Complex facts are the basic facts closed under boolean connectives and quantifiers.

That's just a fancy way of saying that: (i) basic facts are complex facts, and (ii) if φ and ψ are complex facts, then ¬φ, (φ ∧ ψ), (φ ∨ ψ), (φ → ψ), and ∀xφ are also complex facts. They give the following example of a complex fact on p. 34: ∀y[Rich(y) ∧ Man(y) → Loves(y, jane)] (every rich man loves Jane).

Beware that on p. 36 they list sentences like "jane ¬= john" among complex facts, suggesting that they're not basic facts. But they are. I suspect that's why you've been having hard time seeing the difference between the types. By the definition of basic facts (see above), sentences like "jane ¬= john" are considered basic, because they're the negations of atomic sentences such as "jane = john".

  Terminological facts are complex facts taken to be axiomatically or definitionally true.

A better term for them would be "definitional facts" or "meaning postulates" (as Rudolf Carnap calls them). Consider the predicate Man. If someone is a man, we know, without having to see this person, that he is not a woman; it's definitionally true! We capture that logical relationship between predicates Man and Woman with the terminological fact: ∀x[Man(x) → ¬Woman(x)]. That is only one example of a terminological fact; more can be found on pages 36–7. They're pretty straightforward to understand.

Hope this helps clarify the distinction.


Algorithm analysis in the presence of undefined functions

There are two ways to do this.  If you're lucky, the implementer of the external library will have given you a runtime analysis of their code.  If you're not, you can use an oracle model of computation. In a sense, this is treating the library routines as if they run in constant time. Of course, that would be ridiculous but an oracle-based analysis is a little smarter than that because it allows you to quantify how many times the oracle is accessed.  For example, your answer might end up being something like, "The running time is $O(n^2)$ plus the cost of $O(\log n)$ calls to makeSausage() on instances of at most linear size."


Understanding Decision Stump in Adaboost

I wonder if you what decision stump is.

Decision stump is simply a decision tree with only one node. It is usually considered as the weak classifier in boosting algorithms since due to its simplicity it will not overfit.

In your question it is not clear what is even 1 .. 3. Anyhow, the classifiers can be : decision stump1, decision stump2 and decision stump3.


Finding a minimal containing rectangle from a given set of rectangles

Check, insert, and remove can be accomplished by a data structure for dynamically maintaining 2D maxima (this 2011 paper by Brodal and Tsakalidis presents a history of the problem including their new algorithm). I have no idea how to do get.


Find the recurrence relation for the following algorithm

Your recurrence relation is almost correct. Here are some small issues with it:

The length of the array $A[n-m\ldots n-1]$ is $m$, not $n-m$.
Your recurrence only holds when $n$ is divisible by 3. The exact length of the arrays in the recursive calls is $m = \lceil 2n/3 \rceil$.
You are not handling arrays of length $1$.
You are trying to count operations, but without a precise model of computation, this is really impossible. There are two common options here: either you count specific operations, for example only comparisons and swaps, or you just give up and replace everything with $O(1)$. Both options are common.

Accordingly, here are some more accurate solutions are:

When counting only comparisons of array elements, the recurrence is $T(1) = 0$, $T(2) = 1$, and $T(n) = 3T(\lceil 2n/3 \rceil)$ for $n \geq 3$.
When counting only swaps, the recurrence is the same as in the first bullet. Note that $T$ is actually an upper bound on the worst-case cost of your procedure.
When counting both comparisons of array elements, the recurrence is the same as in the first bullet, with "$1$" replaced by "$2$".
When counting the running time on a RAM machine (the standard computation model for analyzing algorithms), the recurrence is
$$T(n) = \begin{cases} O(1) & \text{if } n \leq 2, \\ 3T(\lfloor 2n/3 \rfloor) + O(1) & \text{otherwise.} \end{cases}$$

One fine point is that except when counting comparisons, the recurrence $T$ is for an upper bound on the cost. The exact cost depends on the instance, and often we are interested in estimating the worst-case cost as a function of the input length (in this case, $n$). However, the recurrence for $T$ isn't even guaranteed to compute the worst-case cost: it could be too pessimistic. For example, it could be that no input causes all possible swaps to be performed. Nevertheless, $T(n)$ does upper-bound the cost of the procedure on any input of length $n$.


Need introductory guide to cellular automata for geographic automata systems

This here might help you as an introduction to cellular automata, written by Joel L. Schiff: INTRODUCTION

Furthermore, there is a copy of "Modelling Urban Development with Geographical Information Systems and Cellular Automata" by Yan Liu online. I do not know whether I can link it here, but you can easily search for it.


Is this statistical group summation unambiguously reversible?

The answer is no . I found it helpful to think of the information in the form of a picture: mark each pair $(a, b)$ as a point on a grid, then in each column and row write both the count of the entries in that row, and the "sum" of the entries (the sum of the 'other' coordinate). Your example may be pictured as follows:

I'm writing the count of the dots in each row/column as the number closest the the column, and the "sum" as the number further away. The original data is the set of dots, the new data are Y and Z (understood to not just be sets of points, but to be positional: for example we remember that in the $Y$ data we have $(2, 3)$ in column $1$, $(1, 3)$ in column 2, and so on).
Here are two configurations of points with equal $Y$ and $Z$ data:

Hence the operation is not reversible. Per-column ambiguity arises when there are multiple integer partitions with the prescribed number of parts: eg if a column counts to 2 and sums to 5, its possible entries are 1 + 4 or 2 + 3.


What is total work of managing the dynamic array and why is it the same as for fixed array - O(n)

All that matters is the equation you are quoting. Here is another way to see it. Suppose you have $n$ items. You push one item at a time to the end of an initially empty array. When the array reaches size $2^k$ for some $k<\log_2 n$, you reallocate the array to size $2^{k+1}$ and move all items between $0$ and $2^k-1$ to the new location. The total number of item moves is:

$$ M=1+2+2^2+\cdots+2^{\lfloor\log_2n\rfloor}=2^{\lfloor\log_2n\rfloor+1}-1\le2^{1+\log_2n}-1=2n-1 $$

If you fill the array in a random order, the total number of item moves is bounded by $2n$, too. In all, the time complexity of filling an array of size $n$ is $O(n)$, no matter whether the array is dynamic or not.

  why is the guarantee that each array access takes constant time in the worst case is lost with dynamic arrays

When you push an item to the end of an array of size $2^k$, you have to double the array and possibly copy $2^k$ existing items to a new location. This is not a constant-time operation. With dynamic array, each single operation is not always constant. However, such non-constant operations are so rare that the total number of operations to fill a dynamic array can still be $O(n)$.


What you're describing seems to be isomorphisms between strings. (Note that there happens to be a more complicated notion that is also called 'string isomorphism', but that isn't what we're talking about here.)

You can 'describe the structure' of these strings as follows: replace each character with the number of different characters excluding itself before it in the original string. If you do this for the three strings you mentioned, you get the string '00100' in all three cases.

This also gives an algorithm to test whether two strings are isomorphic: apply the above transformation on both strings and test whether the results are equal.


Yes. This is a right and possible way to go.

One can also consider the formulation of the set cover problem as an Integer Program, using the LP relaxation of such program you can obtain what is referred as $f$-approximation. Details and analysis can be found in most standard books on approximation algorithms.


Regex for divisibility by 123 in binary strings

Here is a way that succeeds, albeit with a lot of work.

First, construct a DFA for the language. That is actually quite simple: It has states $0$ through $122$ (for the remainders), start state and only accepting state is $0$, the transitions from state $n$ go to $(2n \mod 123)$ for label $0$ and to $(2n+1 \mod 123)$ for label $1$.

Now, convert that DFA to a regular expression. The result is not likely to be simple, small or nice.

If you use an extension to regular expressions that allows intersection, you can also do the above with $41$ instead of $123$ and then intersect with the expression you have for divisibility by $3$.


how to use type application rule (T-TAPP)?

Type checking and the inference rules for type theory are not an algorithm. They do not tell you how to type check. They tell you what is allowed when you perform type checking.

The rule for application should be read as:

  If you can prove $\Gamma \vdash t_1 : \forall T . T_{12}$ (and we're not telling you how to do that, you'll have to figure it out) then $\Gamma \vdash t_1[T_2] : [X \to T_2]T_{12}$ for whatever $T_2$ you choose to use (and of course we do not know what it is that you're trying to do here, the choice of $T_2$ is entirely up to you).

So, the answer to your question is: you have to figure out how to find the value of $X$ and you have to worry about the subtitution. The rules are not meant to solve that problem. They are just rules, telling you what you may do.

The correct question that you should have asked is: "How do I make an algorithm that will be able to perform type-checking automatically?" This is an important question, and people put a lot of thought into it. I can give you an initial answer: try out all possibilities until you find one that works. But that's a lousy aglorithm and it's possible to do better.


I might have found a solution to my problem by using four auxiliary binary variables $\alpha_1$, $\alpha_2$, $\alpha_3$ and  $\alpha_4$     $\epsilon\ \{0,1\} $. The constraints 1.-4. are rewritten using the big-M method.

Constraint 1

$T_{ts}\geqslant -7-M\cdot (1-\alpha_1)$
$T_{ts}\leqslant -7+M\cdot \alpha_1$

Constraint 2

$T_{it}\leqslant 15+M\cdot (1-\alpha_2)$
$T_{it}\geqslant 15-M\cdot \alpha_2$

Constraint 3

$T_{ts}-T_{it}+M\cdot (1-\alpha_3)\geqslant 5$
$T_{ts}-T_{it}-M\cdot \alpha_3\leqslant 5$

Constraint 4

$\alpha_{ts,it}=1-\alpha_{ts,gshp}$

Constraint 5

$\alpha_{ts,it}\geqslant \alpha_1+\alpha_2+\alpha_3+\alpha_4-3$
$\alpha_{ts,it}\leqslant \alpha_1$
$\alpha_{ts,it}\leqslant \alpha_2$
$\alpha_{ts,it}\leqslant \alpha_3$
$\alpha_{ts,it}\leqslant \alpha_4$

This might be a solution. Unfortunately computational time is exploding. Does someone know a less time-consuming workaround?

Best SR89


I agree with your solution of the isolated case. Your problem is to reuse your memoisation table. Suppose there are n cases.

What I imagine you could do is:

Allocate a matrix to hold all cases. It has dimensions: T, 1 <= coin value = 50. Call the maximum coin value C. The maximum number of coins is 1000. You could store each count in an unsigned 16 bit int. This max total memory so far of 100 * 50 * 16 = 80KB. We're given 65536, so this isn't too bad. Call this M1.

You now want to devise a plan to reuse your memoisation table as much as possible. As far as I can see, you can reuse a table if and only if the multi-set of coins of the next case is a superset of the previous.

You need to find a way of partitioning the rows into M1 into sequences where each successive vector represents a superset of the previous. That is, the values of coin counts should be non-decreasing over successive vectors.

What you would like to do is minimise the number of partitions. Given two plans with the same number of partitions, you would choose the one which minimises the maximum number of differing coins for a given partition, which would in turn make the solution of the isolated cases cheaper.

I'm not completely sure about the complexity of this, although I imagine that it is NP-Hard, given the number of possible partitions and its similarity to the partition problem. It seems like there might be a cheap randomised greedy algorithm to find a set of initial sequences and work from there.

To run the plan, iterate over the sequences, initialising the memoisation table each time. Run the first case as normal. Run the second case by computing change combinations only for the set of new larger combinations of each coin.


Multiple correct answers for compilation

Yup.  There are multiple sequences of assembly instructions that all do the same thing.  (For instance, one trivial way to see this is to notice that you can insert a no-op instruction anywhere.)  They might not all be equally good, but they'd all be correct.


$\Phi_1=1$ or $\Phi_1=2$ for the dynamic $\text{Table-Insert}$ , where $\Phi_i$ is the potential function after $i$ th operation, as per CLRS

You have caught an instance of the infamous off-by-one error in that popular textbook whose name we shall not mention again.
To repeat, it is correct that "the cost $c_1=1$, $\Phi_0=0$", "$num_1=size_1=1$ $\implies$ $\Phi_1 = 2\cdot1-1 =1$" and " $\hat{c_1}=$ $c_1+\Phi_1-\Phi_0$ $=2$". It is incorrect to state that $\widehat c_i=3$ for all $i$.
The first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation is indeed very special. It is not considered as an expansion, an event that is defined as "in which lines 5–9 are executed". However, it does not maintain $size_i = size_{i-1}$, either. So neither computation for $\widehat{c_i}$ in the textbook is fit for $\widehat{c_1}$.
That error is confusing given that we tend to trust fully an exemplary textbook where so much attention have been paid to detail and correctness.
On the other hand, that error is not very significant since, as you noted, it still holds that "the amortized cost is at most 3".
By the way, if you take a closer look at the figure at the end of question, it shows the potential at the end of first $\text{T}\scriptsize{\text{ABLE}}\small\text{-I}\scriptsize\text{NSERT}$ operation, $\Phi_1=1$, the correct value.


Let us assume we have find $n!$ on input $n$. Our complexity is terms of length of the input ( we assume it to be $L=O(logn)$ ). Multiplication of a $k$ bit by $l$ bit number via standard multiplication takes $O(kl)$ operations ( also after multiplication number of bits in the resultant if $O(k+l)$ ) . We multiply linearly in a loop from $1$ to $n$ to get $n!$. So number of operations carried out are upper bounded by $\# = L^2  ( 1 + 2 ...(n-1) ) = \frac{L^2n(n-1)}{2} = O(L^22^{O(L)})=o(L!)$. Thus it is space and time constructible.


nlp: phonetic edit distance between a word and the closest of a set of words

Building on the comments, there's something called the Needleman–Wunsch algorithm, for which you can find the lowest 'cost' alignment of two sequences (phonemes). You can get a good 'confusion cost matrix' by taking a normal confusion matrix and taking the log-odds of each confusion pair.

As long as your set of words is less than 33k or so, you should be able to find the lowest cost match in about a second or so. Multiply that by N if you multithread across N cores...

Full disclosure: not my ideas here, I got them from Phonemic Similarity Metrics to Compare Pronunciation Methods (Hixon, Schneider and Epstein, in Interspeech 2011).


When we say that a minimization problem A is NP-hard to approximate up to a factor $\alpha \geq 1$, we mean that there is a polynomial time reduction $f$ from instances $\varphi$ of SAT to instances $x$ of A annotated by a target value $\theta$ such that:

If $\varphi$ is satisfiable then $A(x) \leq \theta$ (where $A(x)$ is the optimal value of $x$).
If $\varphi$ is not satisfiable then $A(x) > \alpha \theta$.

Using this definition it is not hard to prove the multiplicative property.

You can also consider a more general notion of hardness: if there is a polynomial time $\alpha$-approximation algorithm for A, then P=NP. Even under this notion, a $\alpha$-hardness for A translates to a $\alpha^2$-hardness for "A2". Indeed, given an instance of A, duplicate it and pass it to the $\alpha^2$-approximation algorithm. One of the solutions is an $\alpha$-approximation. If only the objective value is given, then the smaller one is an $\alpha$-approximation.


Longest common subsequence of a set of sequences

There may be multiple different ways to upper-bound the running time of an algorithm.

Saying that the running time of an algorithm is $O(m^2 n^4)$ is analogous to saying that the running time is at most $m^2 n^4$ (ok, $c \cdot m^2 n^4$, for some constant $c$).  The keyword there is "at most".  So, think of $O(\cdot)$ as more like $\le $ than like $=$.

I haven't tried to analyze the running time of your specific algorithm, but to make up some numbers, it is possible that the running time could simultaneously be $O(m^2 n^4)$ and it could also be true that the running time is (say) $O(m^2 \ell^4)$ where $\ell$ is the length of the longest subsequence.  I'm totally making up those figures -- don't take them too seriously, as I don't claim they are actually valid running times for your algorithm -- I am just saying that both claims are consistent, i.e., they could both be true, without contradicting each other.

It's analogous to the fact that we could have both $x \le 3$ and $x \le 4$ be true.  Or, we could have both $x \le c^2$ and $x \le d^3$ be true.

Side remark: I haven't looked at your algorithm closely, but it looks suspicious to me. I would be surprised if it is a correct solution for the longest common subsequence problem.


Resolution when clauses contain more than 1 complementary literals

Clauses containing both a variable and its negation are not useful, since they're always correct. You can just ignore them.

Furthermore, you CNF is satisfiable - for example, you can set all variables to TRUE. So it's not completely clear what you are trying to accomplish.


Is every algorithm's complexity $\Omega(1)$ and $O(\infty)$?

To be clear, Big O and Big Omega are classes of functions. So if I have for example $\Omega(1)$, that's a set of a whole bunch of functions.

An algorithm's complexity is a function giving how many steps the algorithm takes on each input. This function may be in a class like $\Omega(1)$, or not.

$\Omega(1)$ is the class of functions $f(x)$ that are greater than some constant $c$ as $x$ goes to infinity. According to the technical definition, the function $f(x) = 0$ is not $\Omega(1)$, so an algorithm that never takes any steps (for instance) would not have complexity $\Omega(1)$. But virtually all algorithms would have complexity in $\Omega(1)$. (For example algorithms that always take at least one step.)

Since $\infty$ is not a number, $O(\infty)$ is not defined under any definition I've seen. It does not seem to be interesting to make this definition (
"all functions which are either finite or undefined"? but that is just all functions). So intuitively the answer to your question is yes, infinity is an upper bound on all algorithms' running times, but technically it's somewhat meaningless.

As a sidenote, we could extend little-o to include a domain of infinity by saying $f(x)$ is $o(\infty)$ if $f(x)$ is finite (i.e. well-defined) for all $x$. Under a definition like that, an algorithm that does not halt on some inputs would not have complexity $o(\infty)$. But every algorithm that does halt on all inputs would.

Edit/PS as pointed out by Yuval, we can give a slightly better answer for $O(\infty)$. Let's restrict attention to algorithms that halt on all inputs. Then we can define a function that grows like the maximum number of steps taken by any algorithm that halts. Call it $B(n)$. Then every algorithm's running time will be $O(B(n))$.

To define the function, let's take Yuval's suggestion and let $B(n) = $ the maximum number of steps taken by any halting TM of up to $n$ states on an input of up to $n$ bits. Now given any algorithm, it will be encoded as a Turing Machine, so it will have a certain number of states; say $N$ of them. Then the running time of the algorithm on inputs of size $m \geq N$ is at most $B(m)$. We can see this because $B(m)$ takes the maximum over all Turing Machines up to a certain size, including this one, so $B(m)$ will be at least as big as this TM's runtime.

See also: http://en.wikipedia.org/wiki/Busy_beaver


Approximate time for selection operation using index when equality is on nonkey

In this case full table scan will be executed.

The cost is $N$  I/O operations (where $N$ is a number of pages/blocks in your table)


Is there any problem that is hard to solve, can produce N equiprobable outputs and is easy to verify?

Requirements 1-3 describe a timelock puzzle, also known as timed-release cryptography or time capsule cryptography.  For instance, https://crypto.stackexchange.com/q/606/351.

Requirement 4 says it also has to be easy to verify a correct solution.  I don't know of any standard scheme for timelock puzzles that happens to satisfy all four requirements, but you can invent one.

For instance, here is one simple approach that works, if you trust the creator of the puzzle to not try to play games with you.  The creator picks a random AES key $k$, encrypts $k$ using the timed-release cryptography / timelock puzzle, and publishes the ciphertext as well as a SHA256 hash of $k$.  Now requirements 1-3 are satisfied (it'll take a precisely-controllable amount of time for anyone else to recover $k$), and once you've found $k$, it is easy to verify that you found it correctly by hashing it and comparing the result to the publicly known hash.

For more on timelock puzzles, see also:

https://crypto.stackexchange.com/q/5831/351
https://crypto.stackexchange.com/q/9327/351
https://security.stackexchange.com/q/89094/971

and papers in the cryptographic research literature.


How would I prove that the regular expression rejects string?

Any word accepted by this regular expression has to be either in length 3 or to end with $aba$ or $baa$.
Try to prove this fact, and use it to show that $aabaabba$ must be rejected.


Amortised analysis of a simple loop and 3 operations

We can divide the running time into several parts:

Pushes.
Pops.
The first OP performed at every round.
Subsequent OPs performed at every round.

Note that every OP costs $O(\log n)$, that there are at most $n$ pops, and that each "subsequent OP" follows a pop. We conclude that the total running time of pushes and pops is $O(n)$, the total running time of first OPs is $O(n\log n)$ (since there are $n$ rounds), and the total running time of subsequent OPs is $O(n\log n)$ (since there are at most $n$ pops). In total, the running time is $O(n\log n)$.

If you want to use the potential method, try to use a potential of the form $|S| + \log(|S|!)$.


Minimizing the area of a simple polygon by modifying/adding to a subset of its vertices

Try all possibilities for vertices $P,Q,R,S$ where $P,Q$ are adjacent and $R,S$ are adjacent (there are $O(n^2)$ possibilities).  For each such possibility, find the best way to add a point $T$ after $P$ and before $Q$, such that $T$ falls on the line segment $RS$.  This involves finding a point $T$ on the line segment $RS$ that maximizes the area of the triangle $PTQ$.  You should be able to do that in $O(1)$ time.  Repeat for each possible $P,Q,R,S$ and take the best one found.  This should yield an $O(n^2)$ time algorithm.

I don't know if it is possible to do better than $O(n^2)$ time.


It's hard for me to tell, but it sounds like you want to automatically detect the mammograms where the outline is incorrect.  I'm assuming the desired outline is the perimeter of some convex region in the image.

I'm not sure whether clustering is going to be the ideal approach here.  The first approach that comes to mind for me is something like this: we might want to build a classifier $C$ that accepts an image $I$ and a point $(x,y)$ as input and outputs either 0 or 1 according to whether $(x,y)$ is considered inside the region.  As features, you might include at least the following:

the grayscale intensity of $I(x,y)$, i.e., the darkness of the pixel at location $(x,y)$ in $I$.
the grayscale intensity of the neighborhood of $(x,y)$ in $I$.  This could be computed as the intensity of $I'(x,y)$, where $I'$ is the result of applying a Gaussian blur to $I$.
for each line $\ell$ that's part of the outline you were given for $I$, the value of $f(\ell,(x,y))$, where you define $f(\ell,(x,y))$ to be $1$ or $0$ depending on which side of $\ell$ the point $(x,y)$ is on.  For uniformity, you might choose a common orientation where one side of $\ell$ is towards the "inside" of the convex region given by the outline, and then let $f(\ell,(x,y))=1$ if $(x,y)$ is on that side of $\ell$ and let it be $0$ if $(x,y)$ is on the opposite side.
for each line $\ell'$ that's part of the edges you detected by applying an edge detector to $I$, the value of $f(\ell,(x,y))$.

Given these features, or some other suitable features of your choice, you might try to build a classifier $C$ by training on thousands of mammograms where you have ground truth (where you know what the correct outline is); for each such mammogram image $I$, you might pick a few hundred points $(x,y)$ at random, and then train on the resulting hundreds of thousands of inputs to $C$.  Since you know ground truth, you'll know what the desired/correct value for $C(I,(x,y))$ is, so you can apply supervised learning to try to infer a classifier $C$.

Once you've built a classifier $C$, you might then apply it to every new mammogram in your test set to try to infer the correct outline.

I don't know whether this will be effective in practice, nor whether it solves the problem you want to solve, but this is the first thing that springs to mind for me.


$L^R$ is the reverse of the language $L$ and for designing $L^R$ you must:

Reverse all edges in the transition diagram.
The accepting state for the LR automaton is the start state for the main automaton.
Create a new start state for the new automaton with epsilon transitions to reach of the accept states for the main automaton.
Convert this NFA back into a DFA.


A condition $P$ is weaker than $Q$ if $Q\Rightarrow P$; that is, whenever $Q$ holds, $P$ also holds or, if you prefer, $Q$ guarantees that $P$ holds. $P$ is strictly weaker than $Q$ if $Q\Rightarrow P$ but $P\not\Rightarrow Q$.  Let's look at the three conditions included in the question:

$a>2-2b$
$a>1 \;\wedge\;b>\tfrac12$
$a>0 \;\wedge\; a>2-2b$

(2) $\Rightarrow$ (3) since, if $a>1$ then certianly $a>0$ and, if $b>\tfrac12$, then $2-2b<1<a$. (3) $\Rightarrow$ (1) since if $X$ and something else are both true, then certainly $X$ is true. None of the reverse implications holds: (1) is satisfied by $a=-1$, $b=2$ but (3) is not; (3) is satisfied by $a=\tfrac12$, $b=1$ but (2) is not. Therefore, (1) is strictly weaker than (3) which, in turn, is strictly weaker than (2).

So $a>2-2b$ is the weakest of the preconditions on the table. But is it the weakest possible? Suppose $P$ is any precondition that implies that $a+2b-1>1$.  Rearranging, we see that $P\Rightarrow a>2-2b$, i.e., $P\Rightarrow$ (1). This tells us that no other precondition can be strictly weaker than (1). Therefore, (1) is the weakest precondition.

I don't understand what you mean by `It seems that he broke the rules of equivalents, by using the ">" as "="' since, surely, if (1) breaks that rule, (3) does too? I don't know that rule so maybe somebody else can address that part of the question.


Why does the category of language types have morphisms, not functors?

There are several ideas floating around here. You can look at a programming language through a categorical lens, and then types are objects, and they are indeed opaque. So Bool is not a set of True and False in this picture. It's an object that has two morphisms (injections) going into it, one corresponding to True, and one to False. In Haskell these are the two constructors of Bool. They take no arguments, but that is interpreted as being morphisms from the terminal object (the unit type). It all works out nicely.

Then there is the more traditional picture where types are just sets of values and morphisms are functions between sets. Sets and functions form a category Set. That picture works nicely as long as you don't talk about partial function (ones that loop forever).

Then there is the third idea that every individual set is a category in itself. It's a discrete category, meaning there are no morphisms (other than identity) between elements. In that case, functions between sets would indeed correspond to functors between discrete categories. But a functor between discrete categories is nothing but a function on objects (elements) which is trivial on morphisms, so it's not a very interesting point of view.


choice of data structure for domino tilings

There is an alternative, more compact kind of array representation which might be better if you are working with diamonds as defined in the paper you linked (for axis aligned rectangles you need to find the smallest covering diamond).

The idea is to checkerboard the plane and assign a 2-bit number to each "black" cell, such that the number represents the orientation of the domino relative to the cell. Consider for example:

where $0$ means "horizontal domino pointing east", $1$ means "vertical domino pointing north", etc. Tilting the numbers clockwise yields the array representation:

$$A = \begin{pmatrix} 0 & 0 & 0 & 0 \\ 2 & 3 & 3 & 0 \\ 2 & 3 & 0 & 2 \\ 2 & 1 & 0 & 1 \\ 2 & 2 & 2 & 1 \\ \end{pmatrix}$$

To find two dominos forming a square search for a $0$ adjacent to a $2$ or a $1$ adjacent  to a $3$. Now, if you deal with big tesselations and are into implemtations sped up by bit operations, you can do this:

Let $A$ be a $\{0,1,2,3\}^{m \times n}$ matrix, $b$ be the bit mask $\dots 01010101$, then we can represent the $i^{th}$ row of $A$ as a single integer by using bit-concatenation:

$$r_i = \bigvee_{j=1}^n (a_{ij} << 2(j-1))$$

where $\vee$ denotes a bitwise OR and $<<$ a leftshift. Denoting $\oplus$ as bitwise XOR we can calculate

$$s_i=(r_i \text{ mod } 2^{2n}) \oplus (r_i >> 2) \oplus b \\
t_i=r_i \oplus r_{i+1}  \oplus b, ~~i < m$$

Then domino $a_{ij}$ and domino $a_{ij+1}$ form a square iff bits $(s_i)_{2j-2}$ and $(s_i)_{2j-1}$ are both $1$. Likewise domino $a_{ij}$ and domino $a_{i+1j}$ do so iff bits $(t_i)_{2j-2}$ and $(t_i)_{2j-1}$ are both $1$.

Example calculation for rows 1,2 (little-endian!):

r_1    00 00 00 00
r_2    10 11 11 00
b      01 01 01 01
xor    -----------
       11 10 10 01

Therefore $a_{11}$ and $a_{21}$ form a square.


What is the metadata in microblogging platform?

Metadata is an infamously ill-defined term.  Roughly speaking, it's trying to get at a distinction along the following lines: data is the "content" you care about; metadata is other information that is secondary or exists primarily for technical reasons (e.g., addressing information, tags, technical data to facilitate storage or communication).

A classical analogy is postal mail.  The contents of the letter is considered "data".  The addresses on the envelope might be considered "metadata".

Of course, it's just bits, so at some level it's all data.  But when we talk about the data/metadata distinction, we're usually trying to draw a distinction between the main content that users care about, vs secondary information used to enable the system to work.

Again, the term "metadata" is vague, ambiguous, and ill-defined.  Don't expect a precise technical definition of the term.  Instead, if you plan to use this term in communication  and its precise meaning is important, then make sure to state clearly what you mean by metadata and what you do/don't consider to be metadata.

See also https://freedom-to-tinker.com/2008/10/20/what-your-mailman-knows-part-1-2/ and https://freedom-to-tinker.com/2008/10/23/abandoning-envelope-analogy-what-your-mailman-knows-part-2/ for discussion about the use of the term "metadata" in the  privacy context.


Context free grammar for $bin(n)bin(n+1)^R$

Here is one solution:
$$
\begin{align*}
&S \to 01 \mid 1A1 \mid 1B1 \\
&A \to 1A0 \mid 0 \\
&B \to 1B1 \mid 0B0 \mid 0C1 \\
&C \to 1C0 \mid \epsilon
\end{align*}
$$

Explanation:

$A$ generates $1^n 0^{n+1}$, and so $1A1$ generates $1^{n+1} 0^{n+1}1$, which handles numbers whose binary expansion is $1^{n+1}$.
$C$ generates $1^n 0^n$, and so $0C1$ generates $01^n 0^n1$.
$B$ generates $w01^n0^n1w^R$, and so $1B1$ generates $1w01^n0^n1w^R1$, which handles numbers whose binary expansion is $1w01^n$.
Finally, $01$ handles $0$.


Is there a concept of probabilistic quantum computers?

It is true that unitary gates used in quantum algorithms (and indeed any unitary evolution in quantum mechanics generally) is deterministic and measurements are the only non-deterministic elements in a quantum algorithm (and indeed in quantum mechanics generally). However, it is not true that measurement is always the final step in a quantum algorithm, see for example my answer to this question for a few prominent instances of the use of intermediate measurements. The misconception might originate in the principle of deferred measurement which says that any quantum algorithm with intermediate measurements is equivalent to one where all measurements are moved to the final step. In particular, the principle enables us to replace classical control of quantum gates based on results of intermediate measurements with quantum controlled gates.
Returning to the question of probabilistic quantum computation, note that any probabilistic quantum algorithm (understood here as one that chooses gates to apply based on random bits) can be simulated by a quantum algorithm with intermediate measurements. This follows from the fact that measurement of the state $|+\rangle = (|0\rangle + |1\rangle)/\sqrt{2}$ in the computational basis generates a random bit which can subsequently be used to make random choices about which quantum gates to apply. By the principle of deferred measurement we can turn such a probabilistic quantum algorithm into a quantum algorithm where all measurements are terminal. In conclusion, probabilistic quantum computing is subsumed by regular quantum computing. This is why no distinction is generally made between probabilistic and deterministic quantum algorithms.


Finding all edges on any shortest path between two nodes

Off the top of my head, you could do this. (Let's say you want to find all edges on a shortest path from $s$ to $t$.)

Run an All-Points Shortest Path (APSP) algorithm to store the shortest-path distances from every node to every other node
For every edge $a \rightarrow b$ in the graph:

Add up the distance from the $s$ to $a$, and the weight of the edge, and the distance from $b$ to $t$
Compare this sum to the distance from $s$ to $t$
If it's the same, this edge is part of a shortest path

This runs in $\Theta(E)$ plus the time for the APSP, which is $\Theta(V^3)$ using Floyd-Warshall. The space complexity is $\Theta(E)$ for the final results plus $\Theta(V^2)$ for the APSP.

EDIT: D.W. has pointed out an even more efficient algorithm. Instead of using APSP, use SSSP and SDSP (Single Source/Destination Shortest Path) once each, since you only need the distance from $s$ to everything, and from everything to $t$. This reduces the additional space to $\Theta(V)$, and the time to $\Theta(E+V \log V)$ using Dijkstra (assuming there are no cycles of negative weight).


UV Projection of 3D shape onto 2D images

I've accomplished this by positioning the mesh in a known position (such as the origin), placing the image in front of it so that from the camera's point of view they align as desired. Then it's simply a matter of shooting a ray from each polygon's vertices through the image towards the camera. Wherever the ray intersects the image, that's your (u, v) point for that vertex.


How may an algorithm always color optimally connected bipartite graphs?

You can prove an even stronger claim. Consider the following algorithm:

Let $v_1,\ldots,v_n$ be an ordering of the vertices such that for $i>1$, each $v_i$ is connected to at least one of $v_1,\ldots,v_{i-1}$.
Go over all vertices $v_1,\ldots,v_n$ in order, and color each one with the smallest available color.

This algorithm also uses (at most) two colors to color a connected bipartite graph. The property of the ordering that I highlight, which is satisfied by the ordering produced by the Dsatur algorithm, suffices to guarantee that the algorithm uses the minimal number of colors.
To prove that this algorithm works for a connected bipartite graph with bipartition $V_1 \cup V_2$, where $v_1 \in V_1$, prove by induction that if $v_i \in V_j$ then $v_i$ gets colored $j$.


Find all increasing/decreasing sub array

The question is not clear, you say sub-array, but in the comments you say sub-sequence, and also the comment "the array is discrete" (not sure what that means...).

It is also not clear whether you want a sub-sequence that is both increasing and decreasing. I will presume they are disjoint problems.

So, on the assumption that you want to find all increasing sub-sequences of the array: $a[i_1], a[i_2], \dots, a[i_m]$ with $i_1 \lt i_2 \lt \dots \lt i_m$ here is an algorithm.

Given the array $a[1, \dots n]$, you construct a directed acyclic graph of $n$ vertices: $v_i = (a[i], i)$ with a directed edge from $v_i$ to $v_j$ iff $a[j] \ge \alpha a[i]$ and $j \gt i$.

Now you enumerate all the paths in this directed graph. This is $O(n^2 + f(P))$ where $P$ is the number of paths in the graph, and $f$ is the complexity of the algorithm you pick to do the enumeration.

If you just wanted a count of paths rather than the actual paths themselves (which is what I suspect was your original problem, based on asking for a "hint"), then a dynamic programming algorithm which finds the number of sequences ending at a given $a[i]$ could be made to work in $O(n \log n)$ time.


Calculating worklist with live variable analysis

first of all, this will be my first post in here, so if I can't express myself clearly, I am open to all questions and suggestions.
So let's start with your first question, about the initial worklist and how should it look like? In your example, there are four blocks if we show it on control flow graph, we get :

Here we have 4 blocks or as the algorithm calls, "nodes". We create our initial worklist as a FIFO construct. So initially we have something like this :

Now, we will initialize the algorithm. In initialization part, we assign all in and out functions to empty set. So in[1], in[2].... out[3], out[4] will be empty. Also we have created our list in FIFO construct such as W = 4,3,2,1. Now we start the loop.
We start with w.pop = 4. As the algorithm suggests, out[4] = union of successor nodes' in functions. But for node 4, there is no successor so it will be again empty, {} . For in[4] = use [4] U (out[n] - def[n]) = {x,y} U ({} -{}) = {x,y}. Then we check if in[4] has changed or not. The answer is yes, it changed because it was an empty set initially but it updated and become {x,y}. So we should add our work list its predecessors where it is node 3. Now the equations have become in[1], in[2], in[3] = {} , in[4] = {x,y} and out [1], ...out[4] = {}.
Now we continue with our new worklist w = 3,3,2,1. So now we have 3 as the head. out[3] = in[4] = {x,y} and in[3] = use[3] U (out[3] - def[3]) = {}U ({x,y} -{x}) = {y}. Is our new in[3] is different? Again the answer is yes. Then, we add its predecessor 2 to our list. Our list becomes w = 2,3,2,1.
We continue to do it out[2] becomes in[3] = {y} and in[2] = {} U ({y} - {y} ) = {}. In this situation there is no update for in[2]. Because it was {} and still it is. Then we do not add its predecessor to work list, w =3,2,1.
We do the same things for 3 and 2, nothing changes. Then finally we came to the node 1. out[1] = in[2] = {} and in[1] = {}. So it does not change. And finally we finish our list, it became empty. And the algorithm terminates with the equations:
in[1] = {}
in[2] = {}
in[3] = {y}
in[4] = {x,y}
out[1] = {}
out[2] = {y}
out[3] = {x,y}
out[4] = {}
I hope it helps. If you have any questions remaining you can post here or ask me via private message (I don't know if this platform has a functionality for this). If you think that I made some mistakes, that could happen, please let me know.


As a wannabe computer "scientist" I have problems differentiating theory and practice

There is no universal objective answer to the question of how to tell what counts as theory and what counts as practice, or what counts as science vs engineering; the precise dividing line between theory and practice, or science and engineering, is subjective and a matter of opinion.  Those terms are not precisely defined -- they are fuzzy, subjective terms.  Different people use them differently.

For instance, sometimes people might use science to mean "understanding fundamental questions, identifying and testing laws of nature and hypotheses" and engineering to mean "building useful systems and solving practical problems", but even there the line is fuzzy.  Other times people use the term "science" to mean "what I do" or "the kind of work I respect" or "the really challenging stuff" and "engineering" to mean "what those other researchers do" or "the kind of work that I consider trivial/uninteresting/not deep".  You'll probably encounter many other variations on these kinds of meanings.

P.S. You are wrong that it's hard to do research with experiments in HCI.  Indeed, every human subjects study is itself an experiment, so experiments are very commonly used in HCI.  Perhaps you are thinking that it is challenging to find universal laws of nature in HCI (analogous to Newton's First Law, say, but for people), as people are complex.  That is true, but it doesn't mean no such laws exist or that such research is impossible.  Consider Fitt's Law, for instance.


Find interval sums with minimum number of operation

This problem was solved recently. The naive greedy algorithm works.

David Basin, Felix Klaedtke, Eugen Zălinescu, Greedily computing associative aggregations on sliding windows, Information Processing Letters, Volume 115, Issue 2, February 2015, Pages 186-192, ISSN 0020-0190


Mapping a free variable of type A to a cartesian closed category

It's not clear exactly what your confusion is, so I'll try to explain the example more clearly, and you reply in the comments if something's still not apparent.

In the interpretation of the simply-typed $\lambda$-calculus in a cartesian-closed category, contexts $\Gamma$ and types $A$ are interpreted as objects $⟦\Gamma⟧$ and $⟦A⟧$ (types being equivalent to one-variable contexts), while a term $\Gamma \vdash t : A$ is interpreted as a morphism $⟦t⟧ : ⟦\Gamma⟧ \to ⟦A⟧$.

Context extension is represented by taking the product in the cartesian-closed category, that is: $⟦\Gamma, x : A⟧ = ⟦\Gamma⟧ \times ⟦A⟧$. We want to form the projection of the variable $x : A$, which is represented by a morphism $⟦x⟧ : ⟦\Gamma, x : A⟧ \to ⟦A⟧$, which by definition is a morphism $⟦x⟧ : ⟦\Gamma⟧ \times ⟦A⟧ \to ⟦A⟧$. There's one obvious choice here: to project the second component of the product. Taking $⟦x⟧ = \pi_2$ gives us a term of the correct type and it satisfies the expected properties.

In general, contexts (represented by lists of variables in the type theory) are represented by products of types in the cartesian-closed category, and the term corresponding to the $i^\text{th}$ variable is given by the $i^\text{th}$ projection from the product, $\pi_i$.


Different application of Arden's theorem leads to different answers

The two regular expressions describe the same language.


Unrolling multi-variable mu (μ) expressions in type theory

I can't image they end up equivalent.

That's where you're wrong! In fact, starting with two different unfoldings of some expression you can always keep unfolding them in such a way that they "meet" again.

This property is formally called confluence.

More formally: define

$$ T \rightarrow_\tau T'$$

If $T'$ is the result of a repeated number of unfoldings of $T$. We have the following Theorem:

Suppose $$ T_1\ {}_\tau\!\leftarrow T\rightarrow_\tau T_2$$

There exists $T_3$ such that $$ T_1\rightarrow_\tau T_3\ {}_\tau\!\leftarrow T_2$$

The proof is a bit subtle. I'll just try and convince you using your own example: $$T = \mu\alpha\beta. 1 + \alpha\times\beta$$

The reductions you outlined contain a slight mistake, the correct "$\alpha$-reduction" is:

$$T\rightarrow_\tau \mu\beta.1 + T\times \beta\qquad (1)$$

and not $T\rightarrow_\tau \mu\alpha\beta.1 + (\mu\beta.1+\alpha\times\beta)\times\beta$ As you suggest.

The $\beta$-unfolding is:

$$T\rightarrow_\tau \mu\alpha.1+\alpha\times(\mu\beta.1+\alpha\times\beta)\qquad (2)$$

Let's show both of these lead to the same term. Take $U(\alpha)=\mu\beta.1+\alpha\times\beta$. We have
$$ T\rightarrow_\tau \mu\alpha.1+\alpha\times U(\alpha)$$
By the above reduction. Set $T_1=\mu\alpha.1 +\alpha\times U(\alpha)$. On the other hand
$$T\rightarrow_\tau 1+ T\times U(T)\qquad (3)$$

by composing (1) with a $\beta$-unfolding. Composing the second reduction with an $\alpha$-reduction gives
$$ 1 + T_1\times U(T_1)$$

But since $T\rightarrow_\tau T_1$, we can replace $T$ by $T_1$ in (3) to get identical terms.


Why does a DFA have multiple final states?

A DFA is a machine that reads in its input left to right, and, while reading, keeps track of its internal state. At the end, it has to decide whether to "accept" or "reject" the input based only on whatever internal state it has at the end. The final states are used to indicate which internal states should inform the machine to accept.

The reason we need to have multiple final states, then, is because we might want to accept the input in multiple different scenarios. Here is a simple example. Suppose we want to design a machine that accepts if the input is either ho, hoho, or hohoho (so we want to accept, in total, three possible input strings). Then the "state" of the machine can keep track of what letters we have seen so far: we have 7 states for [nothing], h, ho, hoh, hoho, hohoh, hohoho. If we get a letter that isn't going to be one of these strings (like if the input is haha or asdf), we need a different state to remember that the input was bad, and we can call that state [bad input]. So in total we have 8 states.

Now in this example, we want to accept three different strings: ho, hoho, and hohoho, so we need all three of those states to be final. It turns out that it would be impossible to accept these three strings if we have to have only one final state.

All states (8): [nothing], h, ho, hoh, hoho, hohoh, hohoho, [bad input]
Final states (3): ho, hoho, hohoho

In summary, multiple final states gives us the ability to accept multiple different possible patterns in the input. The above is one example of that, but there are many other examples where it is useful.


Given a matrix $A$, you can form another matrix by taking only some of the rows and columns of $A$, possibly repeated. For example, suppose that $A$ is the following matrix:
$$
\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
$$
If we take only rows 1,2 and columns 1,3, then we get the matrix
$$
\begin{bmatrix}
1 & 3 \\
4 & 6
\end{bmatrix}
$$

For your second question, $\mathcal{D}_x$ is a distribution on column indices. You don't choose a column directly – you only choose an index. This corresponds to 1,3 in the example above.


That's a very good question, and the easy answer is that checking whether a graph is Eulerian is much simpler than checking whether a graph is Hamiltonian.  You're diving head-first into the field of complexity theory and the famous question P vs NP.  (Further reading: What is the definition of P, NP, NP-complete and NP-hard.)
As you said, a graph is Eulerian if and only if the vertices have even degrees.
For checking if a graph is Hamiltonian, I could give you a "certificate" (or "witness") if it indeed was Hamiltonian.  However, there is no anti-certificate, or a certificate for showing that the graph is non-Hamiltonian;  Checking if a graph is not Hamiltonian is a co-NP-complete problem.
In fact, we believe that any certificate for non-Hamiltonian-ness needs to be exponentially large.

To answer the question:

Try every permutation of vertices, and if one of the permutations is a cycle, then the graph is Hamiltonian.  If so, you get a certificate.
If no permutation was a cycle, the graph is not Hamiltonian.  You cannot convince your friends that the graph is non-Hamiltonian without trying all permutations*.

(Ps, using algorithmic techniques (DP) you don't have to try every permutation, but still exponentially many.)


Both. Sometimes it's just difficult to estimate how much time an operation will take, because you don't know ahead how much work needs to be done. Sometimes its simplistic and inaccurate estimates.

Example: I'm downloading four files simultaneously. Someone knows how big each file is, how much has been downloaded, and how many megabytes per second were downloaded for each file. Seem easy to predict how long it will take. However, I know that after one file is downloaded, the others will download faster. Even more after 3 files are downloaded; the last one will download four times faster. Have never seen any progress bar taking this into account.

Example: You are copying a big folder. The progress bar assumes that you copy X megabytes per second, knows how many megabytes there are, and your average speed so far. Problem is, "megabytes per second" is very inaccurate - in practice, it takes x milliseconds per file, plus y milliseconds per megabyte. So lots of small files take much longer than the progress bar anticipates.

The problem is that software developers might care, but their managers don't as long as your computer doesn't crash.


Transformation of a Product Buchi Game to a Parity Game

I will assume that by "Product Buchi game", you mean the (synchronous) product of a deterministic Buchi automaton and some kind of plant or deterministic finite automaton that represents the rules of the game (so to speak) apart from the specification.

You then translated this product between the Buchi automaton and a deterministic automaton to a game by assigning atomic propositions (of which the actions of the two players are composed) or characters to the two players. You have a Buchi game then. Because in your question you state that you want to represent a Product Buchi game as a parity game, I will assume that you have this product Buchi game already.

Translating a Buchi game to a parity game is now easy: Let $\mathcal{F}$ be the set of accepting states/vertices/positions in the Buchi game. Then, you can replace $\mathcal{F}$ by the following coloring function (for every vertex $v$):

$$
c(v) = \begin{cases} 1 & \text{ if } v \in \mathcal{F} \\
0 & \text{ otherwise} \end{cases}
$$

This will give you a parity game in which the player who was formerly the Buchi player can ensure that the highest color visited infinitely often is odd if and only if it is able to win the Buchi game from which the parity game was translated.

If your definition of parity game reasons about the lowest color visited infinitely often, swap the 0 and 1 in the formula above. Likewise, add 1 to every number if the player should make sure that the highest/lowest color should be even. There are multiple definitions of parity game winning in the literature, which are however all equivalent.


Car

My favourite explanation of objects/classes is centered at cars.

Class

Class is defined as a schematic of information you can "measure from" or "store in" a car instance.
For example, every car has a color, production date, total distance passed, etc.

Object

Objects are "real" or "existant" things made upon a class (schematic). All the cars consist of properties such as color and distance traveled, but the actual values of these properties may vary.

Implementation

Object implementation may differ between languages and compilers, but I guess this might be a good way to do it:

Calculate space needed for all subobjects/properties (pointers/ints/strings/other objects) which reside in the object itself. On object creation, take up precalculated memory.
Functions inside classes (methods) are no different than "normal" functions, it is just that compiler enforces them to be called on object or inside of fashion due to object-oriented programming philosophy.

When you try to get/set certain property of an objects, compiler actually translates it into memory offset from start of objects memory, so yes, you couldsay it acts like array with different data types in it.