What happens if the associativity level is greater than the cache size?

Since the associativity is equal to the number of cache blocks in a set, in a traditional cache design there is no sensible interpretation of having associativity greater than capacity; a set cannot have more cache blocks than are in the entire cache.

Having more tags than full-sized blocks in a set can make sense.

If the data in a block can be compressed (possibly in a lossy manner), then data from multiple blocks may fit in the storage provided in a single block. In this case having more tags than uncompressed cache blocks allows such compressed data to be cached and indexed normally. For example, with twice as many tags, a 64-byte cache block compressed to 24 bytes and one compressed to 40 bytes could fit into a single 64-byte storage (with some metadata overhead beyond just the extra tag).

Related to compression, extra tags can also be used to facilitate use of large cache blocks with sectors allocated to different tags. For example, each tag could include a full set of valid bits for all subblocks (sectors) in a cache block, reducing the tag overhead (a valid bit is smaller than a tag) at the cost of less effective allocation. This was proposed for off-chip DRAM caches with on-chip SRAM tags (i.e., limited tag storage budget relative to cache capacity).

Extra tags can also be used to reduce back invalidation in a cache that is tag-inclusive of another cache. Tag inclusion allows the inclusive cache to be probed and avoid accessing the included cache unless the data is present there (this is a form of snoop filtering), but a replacement in an inclusive cache that victimizes an entry shared in the included cache forces the block to be removed (back invalidation) from the included cache to maintain the inclusion property.

Extra tags can also be used to improve replacement policy by keeping a record of recent victims. For example, on a tag hit but data miss, the block might be allocated with a "sticky" bit set that would be unset when the block would normally be evicted using the standard (LRU-oriented) replacement policy (this is not the best replacement policy helped by extra tags but it is a clear example).

Similarly, extra tags might be used to improve prefetch accuracy. For example, a proposed prefetch to an address that is a tag hit is more likely to be used than one that is a tag miss.

Extra tags can also be used in decoupling indexing of tags and storage of data. For example, Moinuddin K. Qureshi et al.'s "The V-Way Cache : Demand-Based Associativity via Global Replacement" proposes using twice as many sets as a cache of the capacity and associativity would normally have. This has the benefit of reducing conflict misses under a constant number of tag comparisions because generally some blocks would be allocated to the alternate set that would map to a single set normally (the number of currently used ways in a set can vary). This excess associativity also allows global replacement with full utilization of data storage capacity; if the capacity was equal to the product of associativity and number of sets, then an victimized block (invalidated tag) would mean fewer valid tags than data storage blocks.


Compression technique exploiting common similarities

Of course it is possible.
For example, you could define the trailer of a movie as the sequence of movie sequences it shows plus the trailer-specific overhead it uses. If the movie itself is at hand when you want to watch the trailer, then everything goes well.

Yet in general...either you would have to add tons of metadata to each file (e.g. "contains sequences in which blue-eyed guy fiddles around with a knife"), thus increasing all files significantly, or you would have to run some pattern-matching algorithms over all your movie database. And your file will be very context-dependent, i.e. if one of the files you rely on changes, then all hell breaks loose. That does not sound practical to me.

Note that most lossless compression techniques also share patterns that appear across different files. So if you gzip a set of very similar mp3s, then some notable compression should happen.


The choice of programming language and the length of a program

What Li and Vitanyi mean by a reasonable programming language is one that is Turing-complete. This means that you can simulate it on a Turing machine and you can simulate a Turing machine on it, so it has the same expressive power as a Turing machine. This gives you a kind of class of languages. I can prove that C is equivalent to a Turing machine, and that Java is equivalent to C, so Java is equivalent to a TM. In over fifty years, no-one has found a reasonable mechanism that is more powerful than a Turing machine (without resorting to things like time travel). This means that the Turing complete languages are considered those that are most reasonable for expressing the principle of computation (see the Church -Turing thesis).

This means that if we agree that the information content of a string should be defined as the length of the shortest program in a Turing complete language, we can never disagree much beyond that. Say that we have a string $x$ and you recon that this string contains only fifteen bits of information. I can then simulate your Turing-complete language in my Turing-complete language and run your fifteen bit program. Since my simulation of your language does not depend on $x$, we can never disagree by more than a constant amount, and for large enough $x$, the difference will become negligable.

So up to a constant term, the information content is a property of the string itself.


Category Set language using simply typed lambda calculus

There are at least two directions in which you can proceed.
First, Church's simple type theory (see also this explanation) extends the simply typed $\lambda$-calculus with the types of natural numbers and booleans, and other constructs that make it sufficiently expressive to encode a certain kind of classical set theory. These ideas were pursued in the HOL theorem provers. For instance, HOL light for a small implementation. This approach has the flavor of doing logic, i.e., there is no general notion of computation - as opposed to the simply typed $\lambda$-calculus, which is a programming language.
Second, dependent type theory, of which there are many variants, is also an extension of the simply typed $\lambda$-calculus. It can be used as a foundation of mathematics. They are used in proof assistants, such as Coq, Agda, and Lean. Some variants, notably Martin-Löf type theory, do retain the character of a programming language. In fact, Idris is a programming language based on dependent type theory.
None of the above is "set theory", but these formalisms are quite suitable for expressing mathematics, including category theory.


Embedding a general planar graph into a grid

There is a really neat result which answer's this question: Schnyder's Theorem. Another nice result is that of de Fraysseix, Pach and Pollack.

Here is a reference for both algorithms. The "Realizer Method" corresponds to Schnyder's Theorem and "Canonical Orderings" corresponds to de Fraysseix et al.'s approach.

These algorithms can embed any planar triangulation in an $O(n)\times O(n)$ grid. You can embed a planar graph $G$ by adding edges until you obtain a maximal planar graph $T$. Then you run any of these algorithms with input $T$. The output will be a drawing of $T$ in an $O(n)\times O(n)$ grid, which is also a drawing of $G$ in that same grid.


What is the tightest asymptotic bound for this recurrence?

It will be $\Theta(n)$, to save myself from rewriting an entire answer, I will refer you to this question and you can apply the answer to your question.


How can I solve the recurrence $T(n) = 4T(n/2) + n^2\log^2n$? (without master theorem)

You want to use the Master theorem. Writing $T(n)=aT(n/b)+f(n)$, we get that $a=4$, $b=2$, and $f(n)=n^2\log^2n$. This gives $\log_b(a)=2$. This is the same exponent on $f(n)$, but you have an extra $\log^2n$. This fits case 2 on the Wikipedia page. So we get $O(n^2)$ with an extra $\log^3n$. This gives an overall result of $T(n)=O(n^2\log^3n)$.


Pi Calculus: Restriction necessary for molecular (atomic) action?

Your solution would work only if you consider $P$, $Q$ and $R$ in parallel as a "closed system", i.e. a system which is not supposed to be composed and interact with an external environment but just to perform internal reactions.

In the context of your quotation, the translation of a polyadic action into a monadic one is supposed to be compositional and to yield a bisimilar labelled semantics.
The role of the restriction is to avoid exposing the actions on $w$ to the environment: what happens if the environment performs actions on the public channel in your solution?
For instance, consider the process $S$
$$
   S = w(y).S'
$$
If put in parallel with your version of $P$, $Q$ and $R$
it can "steal" the first/second component of the couple from $Q$ or $R$.
This is because you do not need to receive $w$ on $x$ to be able to use it if $w$ is a public name, while that is the only way to acquire it when it is restricted.


Continuing the example of why it's hard to compute with univalence?

You are correct, in the sense that the elusive computational nature of Univalence is not so elusive for "ordinary" type constructors.

In fact, you might want to glance at Tabareau, Tanter and Sozeau's paper Equivalences for Free!, which outlines what you have just written, along with many more types of, well, types.

Trouble starts (as usual!) with dependent types, particularly when equivalent types start appearing in indices. Take the following type:

IndexedList (A : Type) : List A -> Type :=
   | INil : IndexedList A []
   | ICons : forall (a : A) (l : List A) (il : IndexedList A l), IndexedList A (a::l)

It's an interesting exercise to write down ap_IndexedList in this case, it's not trivial! But once this is done you then have to take into account types that depend on types that depend on $A$, etc. This is where things get pretty hairy.

Homotopy type theorists want to be able to describe this theory in full generality, since only this will capture the "ideal" of a constructive model of homotopy types.

But as Tabareau & al mention, this is not really all that useful for programing applications, where "single index nesting" is really all that is necessary (for the most part, obviously then proving things about dependent types might require more). So as far as computer scientists are concerned, we're pretty much ready for univalence!


To show that $R \in \mathsf{FP}$ you need to show that there is a deterministic poly-time algorithm $A$ that takes $x$ as input and outputs a $y$ such that $(x,y) \in R$.
A possible choice of $A$ is the algorithm that outputs $\varepsilon$ (the empty word) regardless of $x$. Indeed, $(x, \varepsilon) \in R$.


Statements that are independent are not true or false, their truth value just cannot be decided given the axioms. For example, consider natural numbers. It is true that a given number is a product of primes. It is unprovable that a given number is prime, nor that it is not prime – since it depends on the number. For each given number, it is either prime or not, but it depends.

The same goes for independent statements – the "number" is here replaced with the set-theoretic universe (or whatever universe you base your logic in). It could be that in some universes P equals NP, while in some universes the two are different. The "real world" is one of these particular universes, but as Gödel showed, it is impossible to completely describe the real world: there will always be independent statements. When faced with one, we could try to find other properties of the real world which help determine the statement. This approach hasn't fared so well on the canonical example, the continuum hypothesis.

Despite the foregoing, it is not considered likely that the P vs. NP question is one of these independent statements. That's a declaration of faith. Even though it seems hard to settle, most theoreticians believe that it is just a difficult question, similar to many other difficult questions in mathematics, some of which have been solved one way or another (for example, Fermat's last theorem), some of them haven't (for example, the Riemann hypothesis).


In order to show that $f$ is regularity preserving, it suffices to show that $f^{-1}(U)$ is eventually periodic for $U = \{ n : n \equiv b \pmod{a} \}$, where $a$ is a prime power (here we are using the Chinese remainder theorem and the fact that the eventually periodic sets are closed under intersection).
For $f(n) = 2^n$, we consider two cases:

If $a = 2^k$ then $f(n) \equiv 0 \pmod{a}$ for large enough $n$.

If $a = p^k$ for an odd prime $p$, then $(2,a) = 1$, and so we can think of $2$ as an element of the multiplicative group $\mathbb{Z}_a^\times$. In particular, $2^n \bmod a$ is periodic, the period being the order of $2$ in the group.


Why can any polynomial and exponential be represented as a recurrence?

The general form for a polynomial is $a_n = \sum_{i=0}^k c_i n^i$. Thus, for $n>0$, we have
$$a_n - a_{n-1} = \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,$$
which can be transformed into the recurrence
$$a_n = a_{n-1} + \sum_{i=0}^k c_i n^i - \sum_{i=0}^k c_i (n-1)^i,~~~ a_0 = c_0.$$

For exponentials, the general form is $a_n = c\cdot b^n$. In complete analogy to the example in the book, this is generated by the recurrence
$$a_n = b\cdot a_{n-1},~~~ a_0 = c.$$


Simplifying a logic function using Boolean algebra

I'm not sure how to simplify this equation from the point you've gotten to without backtracking (e.g., recognizing that AB implies ABC' + ABC). The way I would do it is, starting from the beginning:

D = ABC + AB’C + A’B’C + ABC’ + A’BC’ + AB’C’

If we rearrange this as follows:

D = ABC + ABC’ + AB’C + AB’C’ + A’B’C + A’BC’

Then you may notice that we have:

D = A(BC + BC' + B'C + B'C') + A’B’C + A’BC’

Simplifying for C, we get:

D = A(B + B') + A’B’C + A’BC’

Which of course is just:

D = A + A'B'C + A'BC'

Since we know that D is always true when A is true, this implies:

D = A + A'B'C + A'BC' + AB'C + ABC'

Which can be rearranged as:

D = A + (A' + A)B'C + (A' + A)BC'

Giving us the final result:

D = A + B'C + BC'

I'm sure there's a way to do this with De Morgan's law, but it's been a while since I've used any Boolean algebra and I couldn't be bothered to look it up.

Alternatively, you can draw out a truth table

D | A  B  C
------------
0 | 0  0  0
1 | 0  0  1
1 | 0  1  0
0 | 0  1  1
1 | 1  0  0
1 | 1  0  1
1 | 1  1  0
1 | 1  1  1

and recognize that D will always be true if A is true (A), and that if A is not true then D will be true when B'C or BC' (B'C + BC'), thus giving us D = A + B'C + BC'

Although the more "correct" way to do this via truth tables would be to use a Karnaugh map


Your code does not work. I would suggest that you forget about the universe levels for the time being (the $\ell$ thing) and focus on simpler things first. Here is working code:

idd : (A : Set) → A → A
idd A a = a

The type of idd is (A : Set) → A → A. It is a dependent product, i.e., it could be written as $\prod_{A : \mathsf{Set}} A \to A$ in mathematical notation. If we have a type B then the type of id B is B → B.

You say:

  The type of this function is A -> A.

No. The type if idd is exactly what it says, namely (A : Set) → A → A.

  idd is a polymorphic function, where (∀ {ℓ} {A: Set ℓ}) matches any type.

Let us forget about ℓ. In this case the question is whether idd is a polymorphic function. The answer is "yes" because A matches any type.

  Because is a polymorphic function, I can say idd is of dependent type.

No. This is the wrong way to think. The function idd does not have a dependent type. It has the fixed type (A : Set) → A → A. However, this fixed type is a dependent product.


How to prove that a polynomial of degree n is θ(x^n)

Say $T(x) = a_n x^n + \dotsm + a_0$, then by the triangle inequality for $x \ge 1$:

$\begin{align}
   \lvert T(x) \rvert
     &\le \lvert a_n \rvert x^n + \lvert a_{n - 1} \rvert x^{n - 1}
            + \dotsm + \lvert a_0 \rvert \\
     &\le \lvert a_n \rvert x^n + \lvert a_{n - 1} \rvert x^n
            + \dotsm + \lvert a_0 \rvert x^n \\
     &= (\lvert a_n \rvert + \lvert a_{n - 1} \rvert + \dotsm + \lvert a_0 \rvert)
           x^n
\end{align}$

I'm sure you can take it from here. You'll have to figure out an appropriate lower bound to match.


1-2-3 is correctly sent and acknowledged so the sender's window is now over 4-5-6.

4 is received correctly and so it is acknowledged. This makes the window (currently over 4-5-6) slide to 5-6-7. However, since 5 was lost, 5 will not be acknowledged. Therefore, despite 6 being well received, 6 will not be acknowledged as well.  Meanwhile the sender sends 7 because his window allows him to (it looks like you think it doesn't trigger the sender to send 7). It is received well but the recipient doesn't acknowledge it because it's still waiting for 5 to arrive. The sender's timer goes off and therefore it sends 5-6-7 again... (etc).

If you haven't seen it already, this animation is really helpful.


Combinations (repetition not allowed & order not important)

You seem interested in just pairs of indices. Then, if you have $n$ elements you can just generate all pairs of indices  $(i,j)$ with $0 \le i < j < n$.
For i=0,1,...,n-2:
   For j=i+1, i+2, ..., n-1:
      Output (i,j)


What does the "big O complexity" of a function mean?

First of all, when people talk about big O complexity, they refer to the complexity of an algorithm, usually its running time. A somewhat better term is big O asymptotics. Big O makes sense to functions beyond the running time of an algorithm, indeed beyond any kind of complexity measure of an algorithm. Big O notation actually first appeared in the context of number theory, where it is used to simplify many statements.

Now back to your question. There really isn't any such thing as the big O complexity of a function. Let us take as an example your function. It has many big O estimates, such as:

$9n^2 + 10n = O(9n^2 + 10n)$.
$9n^2 + 10n = O(n^2)$.
$9n^2 + 10n = O(n^3)$.

The first two estimates are better than the third one, since they are tight: not only do we have $9n^2 + 10n = O(9n^2 + 10n)$, but in fact $9n^2 + 10n = \Omega(9n^2 + 10n)$, whereas it is not true that $9n^2 + 10n = \Omega(n^3)$. Comparing the first two estimates, the second one is better since it is simpler.

What does simple mean? Although this is an informal notion, everybody will agree that functions of the form $a^n n^k \log^\ell n$ are simple. If we fix this class of simple functions, then the unique simple function $f(n)$ such that $9n^2 + 10n = O(f(n))$ and moreover this is a tight bound is $f(n) = n^2$ (i.e., $a=1$, $k=2$, $\ell=0$). This could be termed "the" big O asymptotics of $9n^2 + 10n$, but a much better term would be the big $\Theta$ asymptotics of $9n^2 + 10n$, since the statement $9n^2 + 10n = \Theta(n^2)$ encompasses the property that this a tight upper bound.

This discussion suggests that when you are given an explicit function, you shouldn't be looking for big O and big $\Omega$ estimates – instead, you should aim higher, at a simple big $\Theta$ estimate.

The true role of big O and big $\Omega$ is in other situations. One situation is when analyzing the running time of an algorithm. The exact running time could depend on the input in a complicated way. For example, when running binary search on an array of length $n$, the algorithm could terminate after one step, two steps, or more – but always within $O(\log n)$ steps. We cannot describe the running time using big $\Theta$, since the best lower bound $\Omega(1)$ and the best upper bound $O(\log n)$ do not match. The same cannot be said about your example.

Another situation in which it makes sense to use big O and big Omega is when it is hard to find the exact asymptotics of a function. Take as an example the central binomial coefficient $\binom{2n}{n}$. Since $\sum_{m=0}^{2n} \binom{2n}{m} = 4^n$ and since
$$\binom{2n}{0} < \binom{2n}{1} < \cdots < \binom{2n}{n-1} < \binom{2n}{n} > \binom{2n}{n+1} > \cdots > \binom{2n}{2n-1} > \binom{2n}{2n}, $$
we can obtain the following upper and lower bounds:
$$
\frac{4^n}{2n+1} \leq \binom{2n}{n} \leq 4^n.
$$
This shows that $\binom{2n}{n} = O(4^n)$ and $\binom{2n}{n} = \Omega(4^n/n)$, where in both cases we are using simple functions as our estimators. The true rate of growth is $\binom{2n}{n} = \Theta(4^n/\sqrt{n})$, but this is harder to establish. In more complicated cases, it could be hard to find the exact rate of growth, or perhaps we are content with only an upper bound or only a lower bound, and then it makes sense to use big O or big $\Omega$.

One could also come up with contrived examples, which rarely happen in practice, in which there is no simple big $\Theta$ estimate for a given function. For example, consider the function
$$
f(n) = \begin{cases} n & \text{ if $n$ is even}, \\ n^2 & \text{ if $n$ is odd}. \end{cases}
$$
The best simple lower bound one could give is $f(n) = \Omega(n)$, and the best simple upper bound is $f(n) = O(n^2)$, but the two don't match.

Finally, while in analyzing algorithms we usually don't care about multiplicative constants, since they depend on details which our analysis abstracts away on purpose, in other situations it makes sense to ask for information beyond big Theta. For example, we can get an asymptotic estimate of the form
$$
\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}.
$$
Or we could ask for an asymptotic series, such as
$$
\binom{2n}{n} = \frac{4^n}{\sqrt{\pi n}} - \frac{4^n}{8\sqrt{\pi} n^{3/2}} + O\left(\frac{4^n}{n^{5/2}}\right).
$$

At this point in your training, however, it's probably better to concentrate at the more elementary stuff, which is of more widespread use in computer science.


Check if current interval is overlapping some intervals, or is being overlapped

Hint: Sort $\{l_1,r_1,\ldots,l_N,r_N\}$ and replace the sorted list with $1,\ldots,2N$ to effectively reduce $K$ to $2N$.

(There might be better ways of solving the problem, but this reduction at least gets rid of the dependence on $K$.)


Is this a correct application of Rice-Shapiro theorem?

The application of the theorem is not correct. Note that $\mathcal{L}$ is a set of acceptable languages, and consider your first point. If you take an acceptable language $L$ that contains a string of length 2014, then it is not necessarily that every superset of $L$ is acceptable.
Regarding the last point, the answer is yes. Given an encoding $\langle L\rangle$ of a finite language $L \in \mathcal{L}$, it is easy to check whether $L$ contains a string of length $2014$. Indeed, we're assuming that the encoding encodes all the words of $L$ in some order, so you can simply traverse the encoding to look for a word of length 2014. Specifically, quoting from the link you attached:

If $L$ is a finite language over $\Sigma$, then you can assume that $\langle L\rangle$ is the unique string over the alphabet $\Sigma \cup \{ \{,•,\}, \epsilon\}$ that contains the strings in $L$ in lexicographic order, separated by dots • and surrounded by braces {}, with $\epsilon$ representing the empty string. For example, if $\Sigma = \{ 0, 1\}$, and $L = \{\epsilon, 0,01,0110,01101001\}$, then $\langle L\rangle =  \{ \epsilon•0•01•0110•01101001\}$.

So given such an encoding as input, you can go over it and check whether there is an infix of legnth 2014 between two consecutive dots •.
Finally, you can simply show that $L$ is acceptable directly by defining a TM that accepts it. Indeed, you can simply simulate the run of $M$ on all strings of length 2014 in parallel, and accepts iff $M$ accepts at least one of them.


Path in an edge-weighted undirected graph

As D.W., point out in his comment. This problem is not $NP$-hard unless $NP\subseteq QuasiPoly$. The idea is that any such path must not contain more than $\log(n)$ edge of weight > 1.

Enumerate every such sequences of edges (with edge-weight > 1). There are ${O(n^2)}^{\log(n)}$ sequences like that.

For each sequence, to turn it into a solution, we need to fill in the "gap" with weight-1 edges.

This one is a little bit different from his comment. A flow is not the exact idea. What we need is the $k$ vertex-disjoint paths from classical work of Robertson and Seymour.

If the above description is not satisfying enough. Just note that we may split each vertex $v$ into a $\text{max-visit}(v)$-clique, and remember to connect each pair of cliques according to the original edges.


Your problem, solving a system of linear equations, can be solved using an ancient algorithm, Gaussian elimination, which works over all fields.

Note that linear programming is more general, allowing also inequalities. It is not entirely clear, however, how the order should be defined over a finite field.


Why superscalar processors use dynamic branch prediction

What you want from a branch predictor: Low implementation cost, prediction speed (you don't want to wait for branch prediction), and high accuracy (high percentage of correctly predicted branches).

So compare static and dynamic branch prediction: Dynamic branch prediction is more expensive, after all it needs to store the history of branches. Dynamic branch history is as fast as static prediction, but its accuracy is enormously higher.

The logical consequence is that when you build a chip that is going to be expensive and high performance anyway, you are not going to scrimp on the cost of branch prediction and use the more accurate method.

And look at Pseudonym's comment: Look at what a static branch predictor does, and see why it will be often less good than dynamic prediction. (Not always. Any dynamic branch prediction can be tricked into always predicting wrong).


You simply need to place a total order on the accounts and always lock the accounts in that order.

You define a < operator on Accounts and then change the beginning like this:

mutex lock1 = getlock(from)
mutex lock2 = getlock(to)
if (from < to)
    mutex lockSwap = lock1
    lock1 = lock2
    lock2 = lockSwap

It doesn't matter what order you choose, it just has to stay the same through the whole program.  In C, and other low level languages it is particularly easy to make this kind of < operator because you can just convert the addresses of the objects to integers and do the < on the integers.


If tasks arrive faster than they can be dealt with, average waiting time is unbounded.

You can probably adapt the Pollaczek–Khinchine formula to give an analytic answer to your question:

$$L = \rho + \frac{\rho^2 + \lambda^2 \operatorname{Var}(S)}{2(1-\rho)}$$

where

$L$ is the mean queue length;
$\lambda$ is the arrival rate of the Poisson process;
$1/\mu$ is the mean of the service time distribution $S$;
$\rho={\lambda \over \mu}$ is the utilization; and
$Var(S)$ is the variance of the service time distribution $S$.


How does a Turing machine with one tape read its input?

The situation here is that we would like to a construct universal Turing machine UTM $U$ with a two-sided tape. Let $T$ be a given arbitrary Turing machine (of certain kind) that computes a partial function $f$. ($T$ is call a "program" in the question.)

The question is how we will run $U$ to simulate $T$. In particular, how will we encode the input to $T$ so that the encoded input will be put on the tape of $U$ and how $U$ will be able to read that input.

Following the receipt given in the question, as a first step, we will fill a part of the tape, called the program section, to encode the transition rules of $T$. It begins on cell $b$ and ends on cell $e$ where $b < e$. Suppose we want to encode $J$, an input to $T$ on the same tape, so we begin at cell $b-1$ and work in the negative direction to encode that input, taking up as much space as we need. The head of $U$ will be put on cell $b-1$.

The first issue we encounter is how $U$ can tell the part of the tape that encodes the transition rules of $T$. We can design $U$ to solve this easily by the following one of the simple techniques.

Put one or more special symbols around cell $b$ and cell $e$ inside the program section so that $U$ will know when $U$'s head is coming in or out of the program section.
We can require the program section be encoded in a set of symbols that is disjoint with the set of the symbols that is used to encode the input to $T$.

I hope that above make it clear how $U$ can read the input $J$ to $T$.

  Is it always possible to pick an encoding and a function, and then find a single program that computes $f$ on an arbitrary input using that encoding?

I am not sure what you are asking exactly. Given an effective injective encoding (that can be decoded effectively), we can always use that encoding as the encoding of $J$ for some particular UTM, as long as that UTM has enough states and capable transitional rules to differentiate the input and program section.

  On the tape, what does the operation of the TM look like?

I assume you meant for the UTM $U$. Its behavior is rather simple conceptually at a high level for all universal machines in the article as shown by the following excerpt.

  (i) On the first stage, the UTM searches the code $P$, corresponding to the code $A_r$, and then the UTM deletes the codes $A_r$, and $A_s$, (i.e. it deletes the mark between them).
  (ii) On the second stage, the UTM writes the code $P_r$ in $Q_R$ of the tape in the reversed order.
  (iii) On the third stage the UTM restores its own tape for a new cycle of modelling.

More generally, $U$'s head read what is the symbol that should be read by $T$. Make a marker on the tape to indicate that cell of the tap is the current cell the head of $T$ is on. Then $U$'s head goes back to the program section to find the rule the corresponds to that symbol for $T$ and $T$'s state (that can be recovered from $U$' state). The result of the transition rule of $T$ is encoded in the $U$' state. Then $U$'s head locates the cell that contains that current symbol for $T$. Then according to the transition rule of $T$ encoded in $U$'s state, modify the cell and goes to the next cell.

What happens can be somewhat more complex when $U$'s modifies the program section and restore it afterwards from time to time.

  The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

Yes, problems could happen if the transition rules for $U$ is not specified correctly. However, I cannot find any problem like that with the U(2,18) of that article.


Silly question: what counts as a "unit of work" when computing big-Oh time complexity

We assume an efficient implementation of standard arithmetic operations (since a stupid implementation could be replaced with a better one). Of course, if the numbers were of unlimited size, the amount of time wouldn't be constant. But it would still be constant per bit (at least for addition and comparison).
So if we pretend that all numbers are a constant size ("one unit of storage") and we pretend that all additions are constant time ("one unit of work"), we get the same relationship between input size and processing time as we would if we worked it out measuring space in bits and processing time in single-bit operations: time is linear in input size.
Complexity analysis is not about nanoseconds. You can't figure out how many nanoseconds an algorithm will take just by looking at the algorithm. What we can figure out is what happens to the time if you increase the problem size. Twice as long is twice as long regardless of what the measurement unit is. The measurement unit is irrelevant as long as we use the same one throughout.
Now, if we were really doing arbitrary precision arithmetic, multiplication and division would take polynomial time. But for most algorithms, taking that into account would massively complicate the analysis without adding much new information. So it's convenient to pretend multiplication and division are linear time.


Why is the quantity of sentences not finite?

Before I can tell you why there are arbitrarily long sentences in English, I would like to point out that 1 is a number,
2 is a number,
3 is a number,
4 is a number,
5 is a number,
6 is a number,
7 is a number,
8 is a number,
9 is a number,
10 is a number,
11 is a number,
12 is a number,
13 is a number,
14 is a number,
15 is a number,
16 is a number,
17 is a number,
18 is a number,
19 is a number,
20 is a number,
21 is a number,
22 is a number,
23 is a number,
24 is a number,
25 is a number,
26 is a number,
27 is a number,
28 is a number,
29 is a number,
30 is a number,
31 is a number,
32 is a number,
33 is a number,
34 is a number,
35 is a number,
36 is a number,
37 is a number,
38 is a number,
39 is a number,
40 is a number,
41 is a number, and
42 is a number. Of course, one could also think of other thing to point out, for example, that the son of the
son of the
son of the
son of the
son of the
son of the
son of the
son of the
son of my
son is my
grand
grand
grand
grand
grand
grand
grand
grand
grand
son. I hope I did not make a mistake there, or two mistakes, or three mistakes, or four mistakes, or five mistakes, or six mistakes, or seven mistakes. Let us stop there, as 7 is a nice number.

Do you still think that there is a bound on the length of grammatically correct English sentences?


I'll walk you through the first question. You can ask the second question separately (see D.W.'s answer).

When faced with a "proof or refute" question like this, we need to try both directions. First, we can try proving the claim. If we seem to get stuck, we can look for a counterexample.

Let's try proving the claim. We are given that $L_1$ and $L_2$ are right congruent. This means the following, for $u,v \in \Sigma^*$ and $a \in \Sigma$:

If $u,v \in L_1$ or $u,v \notin L_1$ then either $ua,va \in L_1$ or $ua,va \notin L_1$.
If $u,v \in L_2$ or $u,v \notin L_2$ then either $ua,va \in L_2$ or $ua,va \notin L_2$.

Let's try to prove that $L_1 \cup L_2$ also satisfies a similar condition. We have to consider two cases: $u,v \in L_1 \cup L_2$ and $u,v \notin L_1 \cup L_2$. The second case looks simpler, so let's start with it. If $u,v \notin L_1 \cup L_2$ then $u,v \notin L_1$ and $u,v \notin L_2$. The assumptions then show that:

Either $ua,va \in L_1$ or $ua,va \notin L_1$.
Either $ua,va \in L_2$ or $ua,va \notin L_2$.

We have to prove that either $ua,va \in L_1 \cup L_2$ or $ua,va \notin L_1 \cup L_2$. We reason as follows. If $ua,va \in L_1$ then $ua,va \in L_1 \cup L_2$ so we're done. Same if $ua,va \in L_2$. The remaining case is $ua,va \notin L_1$ and $ua,va \notin L_2$. In this case, $ua,va \notin L_1 \cup L_2$, so we're again done.

Now let's get back to the other case: $u,v \in L_1 \cup L_2$. This case looks harder. There are many different subcases. Let's start with a simple one: $u,v \in L_1$. In this case we can say that $ua,va \in L_1$ (and then we're done, since $ua,va \in L_1 \cup L_2$) or $ua,va \notin L_1$. What do we do in the latter case? We have to consider membership of $u,v$ in $L_2$. If $u,v \in L_2$ or $u,v \notin L_2$ then either $ua,va \in L_2$ (and then we're done, since $ua,va \in L_1 \cup L_2$) or $ua,va \notin L_2$, in which case we know that $ua,va \notin L_1 \cup L_2$. But what happens if $u \in L_2$ and $v \notin L_2$? Then we seem to be stuck.

Now we switch gears, trying to refute the claim. We got stuck when we had $u,v$ such that $u,v \in L_1$, $ua,va \notin L_1$, $u \in L_2$, $v \notin L_2$. So we try to look for two right congruent languages for which two such words exist. In order to do that, we need first to think of examples of right congruent languages. One very simple example is the language of even-length words. We can enrich the repertoire by taking the language of all words having an even number of some letter $a$.

Here are two examples of this sort: take $L_1$ to be all words with an even number of $0$s, and take $L_2$ to be all words with an even number of $1$s. We can take $u = \epsilon \in L_1 \cap L_2$ (here $\epsilon$ is the empty word) and $v = 1 \in L_1 \setminus L_2$. Since we want $ua,va \notin L_1$, we take $a = 0$. Then $u0,v0 \notin L_1$ while $u0 \in L_2, v0 \notin L_2$. So $u0 \in L_1 \cup L_2$ but $v0 \notin L_1 \cup L_2$, and we have found our counterexample!

As you can see, finding a counterexample is often more creative then proving a statement, which can be quite mechanical. You just need to try a lot of things until something works.

The next step is to reflect on what we have shown. Is there any other operation on two languages which preserves the property of being right congruent? Is there an operation on one language? Indeed, there are: if $L$ is right congruent then so is $\overline{L}$; and if $L_1,L_2$ are right congruent then their symmetric difference $L_1 \triangle L_2$ is right congruent. See if you can prove these claims.

(In fact, right congruent languages are exactly the languages accepted by a DFA with at most two states. This leads to a complete classification of these languages, which I leave to the reader.)


Generating sparse connected Erdős–Rényi random graphs

Brenday McKay suggests an algorithm on mathoverflow. He considers a fixed number of edges, but you can also sample from $G(n,p)$ according to his method. First, calculate $c_{n,m}$ for all $m$. Then sample $m$ in proportion to $p^m (1-p)^{\binom{n}{2}-m} c_{n,m}$. Then use his algorithm.
Gray, Mitchell, and Roughan, Generating connected random graphs, suggest an MCMC algorithm, and analyze it empirically.
Both of these algorithms are for sampling $G(n,p)$ random graphs conditioned on the result being connected. There are also many heuristics for sampling other distributions of random connected graphs in the sparse regime, where usually the focus is on generating some "random-looking" distribution rather than a specific one. For example, you can generate a $G(N,p)$ random graph and pick a connected component, or you can add a random spanning tree to a $G(n,p')$ random graph.


How would a CPU designed purely for functional programming be different?

Actually, it has been done: https://en.wikipedia.org/wiki/Lisp_machine

One aspect in CPU design for FP is garbage collection. GC is very important for functional languages. Common implementations require that the GC can distinguish between pointers and non-pointer data. Effectively, that means storing an extra bit along your data. This is the reason that, for example, OCaml integers are only 31 bit on 32-bit architectures and 63 bit on 64-bit architectures. Integer arithmetic then involves awkward extra shifting operations. Other languages (or other OCaml data types) may waste whole machine words for that extra bit, thus using 128 bits for 64-bit integers. A CPU that is natively designed towards GC might have a 65-bit data bus but 64-bit arithmetic.

That said, a lot of non-functional languages also have garbage collection and would thus profit from respective architectures.

Another thing that comes to mind is that memory usage of FP typically is much more scattered than that of imperative programs. Mainly because it is less natural to use arrays. In consequence, these programs profit less from caching contiguous chunks of memory. So, an FP CPU might use different caching strategies.


When we say that an algorithm runs in polynomial time, we mean polynomial in the length of the input to the algorithm, i.e., the number of bits needed to represent the input.  Suppose both $a$ and $b$ are at most $n$; then the pair $\langle a,b\rangle$ takes $\lg n$ bits to represent.  So, an algorithm whose running time is $O(n)$ takes exponential time (exponential in $\lg n$).  In particular, your algorithm is an exponential time algorithm.

The problem DIV is basically equivalent to the integer factoring problem.  It is an open question whether there exists any polynomial-time algorithm for it, but many believe that there probably is no polynomial time algorithm for it.


How to proof UNIQUE-SAT is in $\Delta^p_2$

UNIQUE-SAT is complete for the complexity class US. It is not hard to reduce coSAT to UNIQUE-SAT (by adding a trivial satisfying assignment), and so if UNIQUE-SAT is in NP, it would imply that NP=coNP, which is considered unlikely. There is a randomized reduction from SAT to UNIQUE-SAT, which implies that UNIQUE-SAT∉P unless NP=RP.

A SAT oracle can only answer one type of question: is the given formula satisfiable or not. However, you can use it to answer other questions. For example, in order to determine whether there are at least two satisfying assignments for some formula $\varphi$, you can ask whether the following formula is satisfiable: $\varphi(x) \land \varphi(y) \land x \neq y$ (you can convert this into CNF).


Scott Aaronson's Proof of $\textbf{BPP} \subset \textbf{P/poly}$

What he here means by a "random string" is not an element of the input space, but rather a string of random choices, i.e. a series of coin flips that have been taken while executing the randomized algorithm. If you enumerated every possible such series of coin flips, you would see that at most a $2^{-n^2}$ fraction of them would lead the algorithm to conclude with the wrong answer.


General question on choosing an Assembly language based on my goal

There is very, very little need for assembler. For is very rarely need for inline assembly - for example, I have some code somewhere that calculates (a * b) / c for unsigned 64 bit integers where a * b overflows.

And asking "which assembler should I learn" - if you ever need assembler, then that's the one you need to learn. Any other assembler is useless.

The only case where you really need to use assembler is at the extreme ends: When you are creating a virtual machine, you need to understand the extremely rarely used instructions to do this safely. If you create codecs, or encryption software, where you have very small amounts of code using up huge amounts of CPU time, that's where you may need assembler. But you don't need to know just assembler. You need to know and understand CPU instructions that have been created exactly for these purposes. You are in a highly specialised area there.


How to find the supremum over all the "good" (interior) polytopes for a given set of 3D points?

What I ended up doing is the following:

Given a set of points in $\mathbf{R}^3$ $S$, and a single point as origin, $\mathbf O$ do the following:

Init empty set $S'$.
$r = \max\{ ||\mathbf x - \mathbf O ||^2_2 \, , \,\,   \mathbf x \in S\}$
Create a mapping $F(x): S\to S'$ where $\mathbf x \in S \to \frac{r^2}{||\mathbf x - \mathbf O\|^2} (\mathbf x- \mathbf O)$
$CH_{S'} \leftarrow $ the points in $S'$ which form convex hull of $S'$ (the sphere inverted set $S$)
Init the interior points set, $IP$ $\leftarrow$ $F^{-1}(s'\in CH_{S'})$ to find the points in $S$ whose sphere inversion points were in $CH_{S'}$.
Use Delaunay triangulation to find the volume of the the convex hull of $IP$

Matlab code:

%% Init
N=20;

S1 = cell(1, N);
for k = 1:N, S1{k} = 30*rand(1, 3); end
S2 = cell(1, N);
for k = 1:N, S2{k} = 30*rand(1, 3); end

M1 = cat(3, S1{:});
M2 = cat(3, S2{:});
M  = permute(cat(1, M1, M2), [1, 3, 2]);

O=[0.5,0.5,0.5];

NearestIntersectionPoints = cell(1,N);
for k = 1:N
    tmp1 = M(1,k,:); tmp2 = M(2,k,:);
    v1=tmp1(1,:); v2=tmp2(1,:);
    [d, intersection] = point_to_line(O, v1, v2);
    NearestIntersectionPoints{k} = intersection;
end

MHull = cat(3,NearestIntersectionPoints{:});
X=MHull(:,1,:); Y=MHull(:,2,:); Z=MHull(:,3,:);
R=[ X(:) Y(:) Z(:)];

X=[X(:)]; Y=[Y(:)]; Z=[Z(:)];
DT = delaunayTriangulation(X,Y,Z);

rSquared = (X-O(1)).^2 + (X-O(2)).^2 + (Z-O(3)).^2;

q = rSquared/max(rSquared);
xx=X./q; yy=Y./q; zz=Z./q;

figure
plot3(X,Y,Z, '.', 'MarkerSize',15);
hold on
[k,v] = convhull(X,Y,Z);
v
trisurf(k,X,Y,Z,'Facecolor','red','FaceAlpha',0.1)

figure
[k,v] = convhull(xx,yy,zz);

trisurf(k,X,Y,Z,'Facecolor','red','FaceAlpha',0.1)
hold on
plot3(X,Y,Z, '.', 'MarkerSize',15)
uniqueK = unique(k)
DTinterior = delaunayTriangulation(X(uniqueK),Y(uniqueK),Z(uniqueK));
DTexterior = delaunayTriangulation(X,Y,Z);

[kin, vin] = DTinterior.convexHull;
[kext, vext] = DTexterior.convexHull;

function [d,intersection] = point_to_line(pt, v1, v2)
      a = v1 - v2;
      b = pt - v2;
      d = norm(cross(a,b)) / norm(a);
      theta = asin(norm(cross(a,b))/(norm(a)*norm(b)));
      intersection = v2 + a * cos(theta);
end

Demo in 2D:

close all
N=20;
R=[1, 5];
center=[0, 0];
x=zeros(length(R),N);
y=zeros(length(R),N);
theta=linspace(0,2*pi,N+1);
theta=theta(1:end-1);

for i=1:length(R)
    x(i,:)=R(i)*(randn+1)*cos(theta+rand) + center(1);
    y(i,:)=R(i)*(randn+1)*sin(theta+rand) + center(2);
end

% Concat all the arrays into one set
x=[x(1,:) x(2,:)]; y=[y(1,:) y(2,:)];
rSquared=x.^2 + y.^2;
q = rSquared/max(rSquared)^2;
xx=x./q; yy=y./q;

k = convhull(xx,yy);
plot(x(k),y(k),'r-',x,y,'b*')


A many-one reduction from $HALT_{TM}$ to $A_{TM}$ means that all instances of the $HALT_{TM}$ problem are transformed to an instance of $A_{TM}$ (can be just one instance), such that if $A_{TM}$ is turing-recognizable then $HALT_{TM}$ is also turing-recognizable.

This reduction can be done by encoding a $TM$ $N$, such that $N$ accepts input string $\langle M,w\rangle$ iff $M$ halts with input string $w$. So if $M$ halts with input $w$, it means that $\langle M,w\rangle \in HALT$, which implies that $N$ accepts $\langle M,w\rangle$, and that the instance $\langle N,\langle M,w\rangle\rangle\in A_{TM}$.


What makes lambda calculus relevant to study?

In computer science we want to analyze and understand source-code with mathematical rigour. That's the only way to prove interesting properties (such as termination) with absolute certainty. For that we need a language with a very well-defined meaning for every construct.

In theory this could be any language with a good formal semantics. But to make things less complicated and less prone to error, it's best to use a language that is as simple as possible but still able to express any program (i.e. is Turing complete). For reasoning about imperative code, there are Turing machines. But for reasoning about functional programming, there is the $\lambda$-calculus.

The basic $\lambda$-calculus is like a functional programming language, but with a lot of 'baggage' taken out. It's not important that this be a nice language to actually write programs in, nor that it be an efficient language. Just that it is simple and expressive. For example, we don't need loops, because we can simulate them with recursion. And we don't need functions with multiple parameters, since we can simulate them with Currying.

Now, at some point you may want to prove properties about constructs that are not part of the basic (untyped) $\lambda$-calculus. That's why computer scientists have extended it in different directions over the years. For example, to reason about type-systems there are a great many variations of typed $\lambda$-calculi.


How to correlate a matrix of values to get a coordinated point?

I finally managed to get what I want. I used python's scipy's

interpolate.RectBivariateSpline(x,y,z,kx,ky)

to create a 60x60 matrix out of the 3x3 matrix. And out of that, I used opencv libraries to detect blobs (mainly, findContours() and fitEllipse()), so now I got a list of ellipses matching the several touches I have.


Get the running time of forest disjoint sets

You've asked two questions:

Why is the tree height Θ(log n)?
Why is the runtime Θ(m log n)?

This answer addresses both questions.  I'll start off with a review of the ranks of the different trees to go over some basics, then discuss these time bounds.

One trick that might be useful here is to think of the minimum number of nodes that can be
in a tree of height n.  Once we have that insight, we can try to relate the maximum runtime to the maximum height of any tree in the forest.

When we initially create all of the trees, they each have height 0 and have a total of 1 node in them.  Now, suppose we want to create a tree of height 1.  The only way to do that would be to merge together two trees of height 0 to form a new tree of height 1.  This would have a total of 2 nodes in it, and that's the minimum number of nodes possible.

Next, suppose we want to create a tree of height 2.  To do that, we have to merge together two trees of height 1.  Each of those trees has a minimum of 2 nodes in them, so the minimum number of nodes possible in a tree of height 2 would be 4.

To make a tree of height 3, we need to merge two trees of height 2, each of which has at least 4 nodes.  This means that we would end up with eight nodes in the tree.

If we look so far, we see this pattern:

Height 0: At least 1 node.
Height 1: At least 2 nodes.
Height 2: At least 4 nodes.
Height 3: At least 8 nodes.

It looks like a tree of height n will have at least 2n nodes in it.  This makes intuitive sense - the only way to make a tree of height n + 1 is to merge together two trees of height n, so the minimum number of nodes in a tree of height n + 1 should be at least double the number of nodes in a tree of height n.

So now let's suppose we do a series of n different union operations to link trees together.  What is the largest possible tree we can make?

Suppose that we want to make a tree of height k.  In order to do that, we first need to make two trees of height k - 1.  Each of those trees are formed from two trees of height k - 2 each, and those trees are formed from two trees of height k - 3 each, etc.  Eventually, we bottom out at trees of height 0.

If we work out a recurrence relation, we get the following expression for the total number of union operations required to get at tree of height k:

U(0) = 0
U(k + 1) = 2U(k) + 1

If we expand out the terms in this recurrence, we get

U(0) = 0
U(1) = 1
U(2) = 3
U(3) = 7
U(4) = 15
...
U(k) = 2k - 1

In other words, if we want to get to a tree of height k, we need to do 2k - 1 link operations.  This means that if we do a total of n union operations, the maximum tree height we can possibly make has height Θ(log n).

This explains the runtime bound you were curious about.  Creating the disjoint set forest takes time O(m), where m is the number of elements.  Each union operation requires us to walk up to the root of a tree whose height is at most Θ(log n), so if we do a total of n of these, the overall runtime is at worst Θ(m + n log n).

Note that this is different from the bound you've proposed.  However, if you make the assumption that m = Θ(n) (that is, you do about the same number of union operations as there are nodes in the graph), then we get that Θ(m + n log n) = Θ(n + n log n) = Θ(n log n) = Θ(m log n), which matches the bound you've described.

Hope this helps!


You are taking these definitions too literally (as if they were mathematical definitions that could be used in a proof.)  These terms all come from the "heroic" age of computer architecture when people were designing by the "seat of their pants" and kind of just getting a feel for what works and what doesn't.  Treat them more like terms for writing poetry than mathematics.

a. SPMD might refer to either multiple threads sharing an address space or multiple processes with independent address spaces sharing only through message passing or through the file system.
b. Typically with SPMD in an environment with separate processes each process would be loaded from the same executable file.

Each thread (or process) in a SPMD machine has its own instruction pointer (indicating what instruction should be executed next).  Each thread in a SPMD program updates its instruction pointer independently.  So the threads in a SPMD program execute simultaneously, but they are executing different instructions and there is no required correlation between the instructions those threads are executing.
In a SIMD program there is only one instruction pointer.  On every time step every execution unit is executing the same instruction simultaneously.  (The term NVidia uses for SIMD execution unit is "core", the term most other people use is "vector lane.")

a. SMP is not part of Flynn's taxonomy.  Flynn's taxonomy is SISD, SIMD, MISD, MIMD.  That's it.  "SPMD" is something that someone made up after the fact but is the same thing as MIMD (as pointed out by the Hennessy and Patterson quote you include.)  "SMP" is part of a completely different poem.  It might be best to think of SMP as a particular way of implementing SPMD computers.  SMP typically stands for "Symmetric Multiprocessor" not "Symmetric Multiprocessing".
b. Multithreading by OpenMP or Pthreads on multiple processors is SPMD (because you are running multiple independent threads on the same program executable.)  You might use a SMP to execute your SPMD OpenMP or Pthreads program, or you might use some other implementation of SPMD.


Is it possible that Co-NP = P but NP != P

The answer is no, and the reason is that $\mathrm{P}$ is trivially closed under complement. Just by definition of $\mathrm{co}$, it follows that $\mathrm{coNP} = \mathrm{P}$ is equivalent to $\mathrm{NP} = \mathrm{coP}$, and then we use that $\mathrm{coP} = \mathrm{P}$ to conclude that $\mathrm{coNP} = \mathrm{P}$ iff $\mathrm{NP} = \mathrm{P}$.


What is the most power/energy efficient sorting algorithm?

As concluded by this paper, the algorithm with the better asymptotic run time seems
to also have the better energy efficiency, which corroborates the assumption that an algorithm with a higher performance also has a higher energy efficiency.


"sum up the image to get the area, then skeletonize the image and sum
  up that image to get the total length.Then divide the area by the
  length."

Input images is a binary image, thus either the pixel value will be zero(black pixel) or 255(while pixel).

Summing up the image gives the sum of all while pixels(black pixel are zero).

i.e., the area of whole white line

$Area = Sum/255$

After skeletonizing the image, the thick white lines become almost one pixel thick.

Summing it up will give the approximate length of the line.

Now, as we know the area occupied by the white line and length of the line.

Dividing them will result the thickness of the line.


When you do a remote desktop connect to another pc which pc's processing power do you have?

When you remote desktop into another computer you are actually using that computers hardware. You are not running a virtual machine of that computer, which would take your main computers resources.


How to properly calculate dependent nested loops for big-O

We can write the for loop as the sums;

$$\sum_{i=1}^{n} \sum_{j = 1}^{i} 1 = \sum_{i=1}^{n}i = \frac{n(n+1)}{2} \in\mathcal{O}(n^2) \, .$$

Note: set the starting values from $i = 1$ and $j = 1$, and increment the upper boundaries also. The calculation in the inner function is assumed as a constant operation and it will not change the calculation.


Christofides algorithm (by hand) (suboptimal solution - is it my fault?)

As mentioned by Yuval, Christofides’ algorithm is an approximation algorithm to the travelling salesman problem. It is not guaranteed to produce an optimal solution. So it is not unexpected that you could end up with a sub-optimal solution of

On the other hand, you did make a mistake while computing the minimal spanning tree. In your step 1 that calculates the minimum spanning tree, edge H$\alpha$ should be replaced by edge HG.


The answer is negative. Let $L_n = \{\epsilon, a^{3^n}\}$ for $n \geq 0$, and let $L_n = \{\epsilon\}$ for $n < 0$. The infinite concatenation of the collection $\{ L_n : n \in \mathbb{Z} \}$ is
$$
L = \{ a^m : \text{$m$ is the sum of distinct powers of $3$} \}.
$$
Since $L$ is unary, in order to show that $L$ is not regular, we need to show that the set $S = \{ m : \text{$m$ is the sum of distinct powers of $3$} \}$ is not eventually periodic. We can see this in many ways. For example, $S$ is infinite but has density $0$ in the limit.


What happens to the running time of an $O(n \ln n)$ algorithm if you double $n$?

I  suggest following property: if for functions $g,f \gt 0$ we have $f \sim kg$, for some constant $k\gt 0$  i.e. $\lim\limits_{n \to \infty}\frac{f(n)}{g(n)}=k$ and both, $g$ and $f$, have not zero as limit point, then $O(f)=O(g)$.
Proof:
Let's consider $\phi \in  O(f)$, then we have $\phi \leqslant C f \leqslant C (k+\varepsilon)g$ for appropriate $C, \varepsilon$ and $n \gt N.$ So $O(f) \subset O(g)$. Using, that we have also $\lim\limits_{n \to \infty}\frac{g(n)}{f(n)}=\frac{1}{k} \gt 0$, we obtain reverse including.
Based on brought property we can say, that running time $O(n \ln n)$ does not change if we double $n$:
$$O(n \ln n) = O(2n \ln 2n)$$


What would an exponential reduction from an NP-complete problem to P signify?

There would be no implications, and indeed I will now exhibit just such a reduction. The reduction takes an instance of vertex cover, finds the optimal value (in exponential time), and then reduces it to the language $\{0\} \in P$ (the language consisting of the single string $0$), by outputting $0$ if there is a vertex cover below the required threshold, $1$ otherwise.


If the compiler/runtime are capable of passing the types down to the CPU, then aren't they are capable of emitting equivalent checks in assembly?

It could be done, but then

we move those checks from compile time to run time, impacting performance
we detect type errors at runtime instead of compile time, losing all the benefits of a type system

  Bloating an instruction set with high-level primitives increases the complexity of the assembler

True, but this instruction set may still be different from the CPU one, so it's just another (intermediate) language, not something the CPU needs to follow.

  and slows down execution time because the assembler is busy doing the compiler's job.

No, the assembler does not run at run time. At compile time, the assembler emits machine code. Compile time may get longer, but the runtime performance should not be affected.

  It sounds like this would make a compiler writer's job easier but expands the TCB without any real gains in speed or safety.

Expanding the TCB is not always detrimental to safety. Assume a nuclear power plant with some software to check that the temperature is kept in the safe range. Removing that software would make the TCB smaller, but the plant would hardly be more safe.

Adding a type system to a TCB puts more safety checks in the system. As long as the type system is not allowed to modify the program code, but only to report "well-typed / ill-typed", it can not harm safety. If it passes ill-behaved programs, say because of some bugs in the type checker, those would be executed anyway without the type system. If it fails some well-behaved programs, that's unfortunate, but preventing the deployment of a new program is always a safe choice -- this impacts productivity but not safety.


Assuming size of long is $32$ bits, each page frame in physical memory exactly contain $1$ long number, therefore in $TLB$ at particular instance of time $31$ long integers would be present. Hence, $1$ page fault in every $32$ memory accesses. Now, I am not sure what is criteria of effectiveness here. But $1$ per $32$ memory access seems pretty good.


If A is decidable and B is decidable, then A is Turing Reducible to B

One way of defining a Turing reduction (from $A$ to $B$) is as an algorithm that can decide $A$ if we have an oracle to decide $B$. The trick to notice here is that there is nothing that says you have to actually use the oracle.

So given that $A$ is decidable, we can take the Turing machine that decides it, augment it with an oracle for $B$, but completely ignore the oracle and just run the TM as normal.


Maximum number of words in deterministic finished automata with k-states

You are correct. I will try to give an informal justification:

The key is to observe that any 5-state DFA that produces a finite number of words can only produce words up to length 4, assuming the start state is included in the 5 states.

To see why this is, observe by contradiction that if it produced a word of length 5, it would have to go through 5 transitions $s_0 \rightarrow s_1 \rightarrow s_2 \rightarrow s_3 \rightarrow s_4 \rightarrow s_5$ for some set of states $s_i$. Since the DFA only has 5 states, the 6 states $s_0, \ldots, s_5$ cannot all be distinct. Thus this path contains a loop, and we can produce an infinite number of ever-longer words by looping repeatedly.

Thus the DFA can at most produce the words of length up to 4, which as you've observed is 121 words:

$\varepsilon \ | \ (a|b|c) \ | \ (a|b|c)(a|b|c) \ | \ (a|b|c)(a|b|c)(a|b|c)\  | \ (a|b|c)(a|b|c)(a|b|c)(a|b|c)$

To show that 121 is the least upper bound of possible words (in other words, that we cannot find a lower maximum), it suffices to construct a 5-state DFA that produces all 121 words. The following will do:

$C = \{a,b,c\}$

$S = \{s_0, s_1, s_2, s_3, s_4\}$, $s_0$ is the start state

$F = \{s_0, s_1, s_2, s_3, s_4\}$ (all states are accepting states)

$T = \{(s_i,s_{i+1},a), (s_i,s_{i+1},b), (s_i,s_{i+1},c)|0\le i\le 3\}$


For the purposes of this discussion, a "program" is a piece of code which always takes an integer as an input, and either runs forever or returns an integer. We say that two programs $f$ and $g$ are extensionally equal if they compute the same function, i.e., for every number $n$ either both $f(n)$ and $g(n)$ run forever, or they both terminate and output the same number.

An extensional property of programs is a property $P$ that respects extensional equality, i.e., if $f$ and $g$ are extensionally equal then they either both have the property $P$ or both do not have it.

Here are some examples of non-extensional properties:

The program halts within $n$ steps. (We can always modify a program to an extensionally equal one that runs longer.)
The program uses fewer than $n$ memory cells within the first $m$ steps of execution. (We can always modify a program to an extensionally equal one so that it uses up some memory for no good reason.)
The program text mentions a variable named k. (We can rename variables.)
Does the program invoke command $\sigma$. This may depend a bit on what $\sigma$ is, but if it is something that can be simulated in some way, then we can evade $\sigma$ and still have a program which is extensionally equal to the original one.

I am sure you have noticed that I listed precisely your alleged counter-examples to Rice's theorem, which says:

  Theorem (Rice): A computable extensional property of programs either holds of all programs or of none.

There is another way to explain this: you have to distinguish between a program and the function it computes. Many different programs compute the same function (they are all extensionally equal). Rice's theorem is about properties of functions, not about properties of programs that compute them.


What is the expansion of the regular expression $(a^*b^*)^*$

Expand the outer starred expression first and then expand the terms. If $r$ is a regular expression, then $r^*$ denotes the language consisting of zero or more copies of $r$, concatenated together, so $r^*$ could take the form $\epsilon$ (the empty string, resulting from no copies of $r$) or $r$ or $rr$ or $rrr$, and so on.

In your example, with $r=a^*b^*$, then $r$ denotes all the strings consisting of zero or more $a$'s, followed by zero or more $b$'s, and so $(a^*b^*)^*$ will denote all possible concatenations of terms $(a^*b^*)$. For example, one possible concatenation would be $(a^*b^*)(a^*b^*)(a^*b^*)$ and then after expanding each term, we might have $(abb)(aab)(bbb)=aabaabbbb$.

By choosing to expand the inner term and then concatenating the results you will likely miss the general form. If, for example, we chose a particular string in $r$ and then concatenated them, we might replace $r=a^*b^*$ with $abb$. Then, if we concatenated just those terms three times, we'd have $(abb)(abb)(abb)$. While this is in the language $(a^*b^*)^*$, it is of a special form that doesn't capture the full generality of strings in the language.

While it's not directly related to the question you asked, it's worth noting that $(a^*b^*)^*=(a\mid b)^*$ (some authors would write $(a\mid b)$ as $(a\cup b)$ or $(a+ b)$). In other words, $(a^*b^*)^*$ denotes the language consisting of all possible strings over $a$ and $b$. Can you see why?


Is there any example of Regression Tree driven optimization (or active learning)?

An active learning approach using which combines an incrementally-learned Regression Tree with bandit-style sampling from leaf nodes to determine which instance to request a label for next is described in the “Adapting to Concept Drift in Credit Card Transaction Data Streams Using Contextual Bandits and Decision Trees” paper (disclaimer: I'm an author on the paper).

A short summary:

A regression tree is learned to predict targets $\hat{y}$ based on feature vectors $x$. This is done with an incremental tree learner, it can grow over time as labelled data becomes available (for instance due to active learning)
Every node in the regression tree also contains linear models that are trained such that we can additionally distinguish between different instances within the same leaf nodes. Training linear models in all nodes, rather than only the leaf nodes or only the root node, allows us to both generalize across the tree as well as specialize for subsets of the tree.
Predictions made by linear models be treated as "ground truth" labels for unlabelled instances and plugged into the Regression Tree Learner to allow the tree to grow more quickly than it could if we only used data with real labels (Semi-Supervised Learning).
Leaf nodes are treated as arms of a Contextual Multi-Armed Bandit (contextual because we also happen to have feature vectors for instances drawn from leaf nodes)
A Contextual Multi-Armed Bandit algorithm is used to select unlabelled instances for which we'd like to obtain labels (i.e. active learning)


Example of exponential algorithm performing better than a polynomial one?

I think the classic example of this is in Linear Programming.

The Simplex Algorithm is exponential time, but fast in practice. There is a polynomial time algorithm, but it's generally slower.

See the relevant Wikipedia entry.


Whats the difference between Processor bus and System bus

A lot of terminology is vendor-specific. Different architectures and CPU vendors use different terms to describe different ways of connecting CPUs and peripherals, and the technology is constantly changing.

In what follows, I'm going to use the word "bus", but do be aware that a bus could be realised in multiple ways depending on speed and requirements, such as a point-to-point, crossbar, or switched fabric topology. It's logically a bus, even if it isn't physically a bus.

As a general rule, modern busses are hierarchical, and the hierarchy reflects the way the computer system is constructed. For example, a modern computer may have more than one logical processor/core in a given die or package, and have more than one die or package on the motherboard. A large computer (e.g. a mainframe) may have more than one motherboard connected by a backplane.

Every time you have more than one thing which needs to communicate with each other thing, you need a bus/switch/whatever to connect them together.

Here's a simplified example:

Each package or die comprises multiple logical CPUs which are connected by some kind of internal bus. These are then connected to a common bus which connect the CPUs together, along with high-speed/high-bandwidth peripherals such as RAM (which increasingly looks like a peripheral these days), coprocessors such GPUs, and fast devices such as gigabit ethernet, Fibre Channel, InfiniBand, etc.

This bus is then connected via interfaces to lower-speed busses such as PCI, USB, SCSI, I2C, etc. Most of the things that you typically think of as "peripherals" are connected to peripheral busses such as these.

Of course this is just an illustrative example, not based on any particular computer design. Different architectures do different things. Large-scale high-availability machines (e.g. modern mainframes) typically have "local" RAM for each CPU die or motherboard, and CPUs designed for those high-availability applications commonly have a backplane bus interface built onto each CPU package plus a redundant backplane connection hanging off the high-speed I/O bus.

So given all that, the term "processor bus" probably refers a bus which connects processors together. That would mean one of two things:

The bus connecting logical processors together within a single package or die.
The bus connecting processor packages or dies together.


Sorting algorithm for ranking hundreds of Images based on pairwise comparison

If you're actually using humans (e.g., MTurk) and there is any subjectivity at all, I expect that standard sorting algorithms may perform poorly.  Standard sorting algorithms expect that there will be zero errors or mistakes in any of the comparisons.  If a single comparison returns a faulty value, the sorting algorithm might fail badly.  However, in practice, humans make mistakes; and if the rating task is subjective, humans don't always agree on all rating decisions.  Consequently, I expect standard algorithms are likely to be a poor match.
If transitivity is not guaranteed, standard sorting algorithms are definitely not suitable.
There are better approaches that can tolerate some errors and mistakes and disagreements.  For instance, you might be interested in the Bradley-Terry-Luce model; see https://cs.stackexchange.com/a/134416/755.  It helps you infer an overall ordering, based on individual pairwise comparisons.  That model does not support nontransitivity, though.
We could also consider how to choose which pairwise comparisons to make (i.e., the experiment design question, instead of the inference question).  I don't know if there is literature on that; but Peer grading design - choosing a graph, to get accurate rankings/ratings might be of interest, and it might be worth checking Stats.SE or asking there about this aspect of the problem.


How do I prove that a language is deletion closed?

You'd prove that a language $L$ is deletion-closed as follows.

Consider a word $w\in L$ and let $w = w_1\dots w_\ell$.  Now, for any $r$ and $s$ with $1\leq r\leq s\leq \ell$, consider the word $w' = w_1\dots w_{r-1}w_{s+1}\dots w_\ell$, i.e., the word that results from deleting the substring $w_r\dots w_s$ from $w$. We have $w'\in L$ because [some argument that will be specific to the language $L$ you're working with].


Provided the $N_i$ are all positive, this is pretty much exactly the problem of "how many ways can I make value $Y$ out of coins with values $N_i$ (assuming no restriction on the number of coins)?"

That problem has a very easy recursive solution that breaks into two cases at each step:

Include a "coin" of value $N_i$ and recurse.
Assume you have used $N_i$ as many times as you are willing and recurse using only values $N_j$ for $j > i$.


Figuring out the language accepted by a DFA?

The DFA is already minimal. In the table below, I give words which separate all pairs of states:
$$
\begin{array}{c|c|c|c|c}
& q_1 & q_2 & q_3 & q_4 \\\hline
q_1 & & \epsilon & \epsilon & b \\\hline
q_2 & \epsilon & & ba & \epsilon \\\hline
q_3 & \epsilon & ba & & \epsilon \\\hline
q_4 & b & \epsilon & \epsilon & \\
\end{array}
$$
As for the language accepted by this DFA, the best I got is
$$
\begin{align*}
&(a^? (a^{even} b)^+ a^{odd} b)^* a^* + \\
&(a^? (a^{even} b)^+ a^{odd} b)^* a^?(a^{even} b)^+a^{even} b,
\end{align*}
$$
where $a^? = a + \epsilon$, $a^{even} = (aa)^*$, $a^{odd}=a(aa)^*$, and $r^+ = rr^*$.

There might be a simpler description.


Count number of pairs of elements whose product is a perfect square

There are $9592$ primes below $10^5$. You can convert each number in each array to a sparse binary vector of length $9592$, signifying the parity of the power of each prime. Using radix sort, sort each of the arrays, and then merge them. Denoting by $a_x,b_x$ the number of times that $x$ appears in each of the arrays (respectively), the answer is $\sum_x a_x b_x$.

There are many optimizations possible for this general scheme, which in practice can speed it up significantly. I'll let you work them out.


Counting pairs of intervals where one is a subset of the other

Sort all endpoints of intervals, and maintain a self-balancing order statistic tree, initially empty. Scan the endpoints from left to right. Add each left endpoint to the tree. When reaching a right endpoint, determine the order statistic of the left endpoint, and then remove the endpoint. Update the number of intersections accordingly: if the left endpoint was that $i$th smallest element (counting from $1$), then add $i-1$.

Since each operation on a self-balancing order statistic tree takes $O(\log n)$, the entire algorithm runs in $O(n\log n)$.

As an example, consider your list of intervals.

Initially, the tree is empty, and the counter is 0.
Read left endpoint of [1,7]. Tree contains 1.
Read left endpoint of [2,60]. Tree contains 1,2.
Read left endpoint of [3,5]. Tree contains 1,2,3.
Read right endpoint of [3,5]. Since 3 is the third smallest point, increase counter by 2. Tree contains 1,2.
Read right endpoint of [1,7]. Since 1 is the smallest point, increase counter by 0. Tree contains 2.
Read right endpoint of [2,60]. Since 2 is the smallest point, increase counter by 0. Tree is empty.


Is Hamiltonian path NP-hard on graphs of diameter 2?

Assuming you are talking about directed graphs, the work of Füredi et al. [1] shows that such graphs of n vertices and diameter 2 have at least ~n log (n) edges, or an average degree of ~log(n).  I am aware of no subsequent result tightening this result, and the authors themselves suggest that they think this result is tight; this is quite far from the known sufficient conditions for Hamiltonian paths, which are based on a roughly linear vertex degree.

As a result, this appears to be an open and difficult problem that would require some significant research for a solution.

[1] Füredi, Zoltán, et al. "Minimal oriented graphs of diameter 2." Graphs and Combinatorics 14.4 (1998): 345-350.


Solving the recurrence formula $T(n) = 3T(n/2)+n^2$


What are thin-core and fat-core processors

Thin-core is a simple processing unit, slower with less registers, for example GPU core or small, low-energy core.
Fat-core is full-fledged CPU core. The mobile version of CPU is still fat-core

From article:

  The IBM Blue Gene/P supercomputer (1 Pflop) is an example of a contemporary large-scale system design (294,912 processors) based on a many-thin (850 MHz, 1 Gbyte) processing-core approach.


Trouble Understanding a Remark about Beta-Reduction in the Lambda Calculus

Application in the lambda calculus is not associative. $m_1 m_2 m_3$ means $(m_1 m_2) m_3$ and is not equal to $m_1 (m_2 m_3)$.  So the second equality you state doesn't hold. $$a(m_1 m_2 m_3) \neq ((a m_1) m_2) m_3$$  Further $$a N_1 N_2 = (a m_1)(m_2 m_3) \neq (a m_1) m_2 m_3 = ((a m_1) m_2) m_3$$


Longest substrings of common length with the same parity

Here is an $O(n\log^2 n)$ solution.

The first step is to reduce to an easier problem:

  Given $x_1,\ldots,x_n \in \{0,1\}$, determine, for all $0 \leq i \leq n$ and $b \in \{0,1\}$, whether there is a contiguous subarray of length $i$ whose sum is equal to $b$ modulo 2.

Applying this to both $A$ and $B$, we can solve the original problem in $O(n)$.

The basic idea is to use divide and conquer. Given an array $x_1,\ldots,x_n$, divide it into two arrays $x_1,\ldots,x_m$ and $x_{m+1},\ldots,x_n$ of roughly equal size. Every contiguous subarray of $x_1,\ldots,x_n$ of length $i$ with parity $b$ has one of the following forms:

Contiguous subarray of $x_1,\ldots,x_m$ of length $i$ with parity $b$.
Contiguous subarray of $x_{m+1},\ldots,x_n$ of length $i$ with parity $b$.
The concatenation of a subarray $x_{m-i_1+1},\ldots,x_m$ of parity $b_1$ with a subarray $x_{m+1},\ldots,x_{m+i_2}$ of parity $b_2$, where $i_1+i_2 = i$ and $b_1+b_2 \equiv b \pmod{2}$.

We can determine whether subarrays of the first two forms exist, for all $i$ and $b$, by running the procedure recursively on the two halves. The interesting part is the third form. We start by determining the parity of all arrays of the form $x_{m-i_1+1},\ldots,x_m$ and of the form $x_{m+1},\ldots,x_{m+i_2}$ for all $i_1,i_2$, which takes time $O(n)$. Let $L_{b_1}$ be the set of $i_1$ such that $x_{m-i_1+1},\ldots,x_m$ has parity $b_1$, and define $R_{b_2}$ analogously. Using FFT (exercise), for each $b_1,b_2$ we can determine in $O(n\log n)$ the set $X_{b_1b_2}$ of $i$ such that there exist $i_1 \in L_{b_1}$ and $i_2 \in R_{b_2}$ summing to $i$. Given the sets $X_{b_1b_2}$ for all $b_1,b_2$, we can determine whether subarrays of the third form exist, for all $i$ and $b$.

In total, denoting the running time of our algorithm by $T(n)$, we get the recurrence
$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + O(n\log n), $$
whose solution is $T(n) = O(n\log^2 n)$.


Is there a poly-time algorithm for expanding out polynomials

For the particular polynomial in the question, we have the multinomial theorem.
$$ (x_1+x_2+\cdots+x_n)^m = \sum_{k_i\geq 0,\, k_1+k_2+\cdots+k_n=m} \binom{m}{k_1,k_2,
\cdots,k_n} x_1^{k_1}x_2^{k_2}\cdots x_n^{k_n}$$
where the coefficients are knowns as multinomial coefficients, and can be computed by
$$ \binom{m}{k_1,k_2,\cdots,k_n} = \frac{m!}{k_1!\,k_2!\cdots k_n!}$$

For most of general products of multivariable polynomials, there is no such closed formula for their expansion.


Is FNP = FEXPTIME if and only if NP = EXPTIME?

Yes, vacuously, since it is trivial that $\operatorname{FNP} \neq \operatorname{FEXPTIME}$, because it takes an exponentially long amount of time to give an exponentially long output.


This is the problem of finding a matching in a bipartite graph.  Each person is represented as a vertex in the graph, and you draw an edge between two people if they both have included each other on their rankings.  Then any matching corresponds to a way to match people.  There are standard algorithms that can find a maximum matching in a bipartite graph efficiently, so you'll even be able to find a pairing that maximizes the number of stable pairs created.


Can a Turing machine be both decidable and undecidable relative to itself?

A Turing machine doesn't come with an oracle. The oracle comes from outside. Rather, an oracle Turing machine is a Turing machine that has a special way of accessing an oracle. When you run the Turing machine with a specific oracle $O$, whenever the machine activates the special mechanism for accessing an oracle, you forward the request to $O$. A phrase like "$M$ is an oracle TM with an oracle for $A'_{TM}$" is thus meaningless.

You are saying that you run $D$ on the input $\langle D \rangle$, but you haven't specified what oracle you are running $D$ with. If you want $F$ to have the proper semantics, then you have to run $D$ with an oracle for $A'_{TM}$. When run in this way, $D$ accepts $\langle D \rangle$ iff $F$ rejects $\langle D,D \rangle$ when run with $A'_{TM}$, and so iff $D$ rejects $\langle D \rangle$ when run with $A_{TM}$.

Notice that there is no contradiction: $D$ accepts $\langle D \rangle$ when run with the oracle $A'_{TM}$ iff it rejects $\langle D \rangle$ when run with the oracle $A_{TM}$.

The real reason this works out is that a machine cannot get as input an oracle TM together with an oracle, since the oracle is an infinite object and so it cannot be specified as input.


Unfortunately, as D.W. says, it's not possible to do Deutsch's Algorithm with only a single qubit.

The key is the line you quoted in your question: the quantum oracle for the function $f$ returns $\mid x\rangle \mid y \oplus f(x)\rangle$. This only works with two qubits.

Why can't we just make the oracle return $\mid f(x) \rangle$? Well, in quantum computing, all functions must be reversible (you can reconstruct the input from the output), and we have no guarantee that $f(x)$ is reversible. And if we force $f(x)$ to be reversible, then we know it's balanced, and the problem becomes trivial (return "balanced" every time).

The only way to make a reversible function out of a function that may not be reversible is to add "ancillary" or "garbage" qubits; this is how the Toffoli gate implements the non-reversible AND function. That's basically what the second qubit is doing here: without it, we can't even necessarily call the function.


Sifting algorithm for group generated by a set

One possible explanation is that it is indicating that you should never try to read or use any matrix element $M_{i,j}$ where $i<j$.  "Referenced" might be talking about "de-referencing" a pointer, i.e., reading a memory cell, i.e., reading an entry of the matrix.  Perhaps the text is indicating that the matrix entries $M_{i,j}$ are only defined for $i \ge j$.

I suggest you read the text with this possible perspective in mind and see if it seems consistent with the surrounding context.


Which should you use?  Neither.  Personally, I think the words "taintness" and "taintedness" both look awkward.  I would recommend rephrasing the sentence to avoid using either of those words.   Instead, you might try to use something like "whether the variable is tainted".  Or, if you desperately need a noun phrase and can't make the prior suggestion work, try something like "taint status".

For example, I might rewrite the quoted sentence as something like:

  To achieve that, we propose to perform a taint dependency analysis whose objective will be twofold: 1) to compute which variables are tainted at each program location; 2) to extract from the program source the whole dependency chains between each vulnerable statement and the corresponding inputs leading to this vulnerability.

(I added italics to highlight the part that I changed.)


Conflicting definitions of quasipolynomial time

Both definitions are equivalent, since when we say that a problem can be solved in time $t$, we usually mean that it can be solved in time at most $t$. For example, a problem can be solved in time $n$ if there is an algorithm solving it whose running time $T(n)$ satisfies $T(n) \leq n$.


PDA pushing nothing given an input and the current stack top

In a commonly used model for pushdown atomata instructions of the automaton are of the form $(p,a,A,q,\alpha)$ meaning in state $p$, read $a$ from the input, pop $A$ from the stack, change to state $q$ and push $\alpha$ to the stack. In a diagram for the pda this can be represented as an edge from $p$ to $q$ labelled by $a; A/\alpha$. Note the first symbol of $\alpha$ end at the top of the stack.

There are some complications. First $a$ can be the empty string, so that the automaton ignores the letter on its input tape. To the contrary, the automaton cannot easily ignore its stack. The topmost symbol is always popped.

So if we want to perform the instruction "read $a$ whatever is on the stack" this is implemented as a set of instructions $(p,a,A,q,A)$ for all stack symbols $A$. If we want to perform "read $a$ when $A$ is on the stack (and leave $A$ there)" we just have the instruction $(p,a,A,q,A)$ for this particular symbol $A$. This seems to be your case.

Also the instruction "read $a$ and pop $A$" is then $(p,a,A,q,\varepsilon)$, pushing nothing after popping $A$.

Finally, the fact that we always need to pop at least one symbol means that formally the automaton cannot move on the empty stack, and blocks. This means if it did not just accept its input, it cannot continue and the computation fails.
(Be aware, not all books agree on the precise details here.)


Queue FIFO search speed up through the change of visited array?

Suppose 3 rooms each of which contains number 6 have been visited before any room the product of whose coordinates is 6 has been visited.
In the first version of your code, every room of the second kind will be put into the queue 3 times.
In the second version of your code, every room of the second kind will be put into the queue only 1 time (except possibly the room at (A,B), which will be put into the queue 2 times).
The difference between 3 times and 1 time is what slows down the first version. In general, there might be $m$ rooms of the first kind for the corresponding second kind. The appropriate average of $m$ in the test cases is substantially greater than 1. Hence you see the significant speedup from the first version to second version.

A good rule of thumb across all these kinds of searching problems is to try setting visited as soon as possible to avoid unnecessary and sometimes even incorrect computations.


Describing time complexity when internally using a function of unknown complexity

In complete generality there is nothing much you can say. However, in many circumstances it will be the case that $g(n)$ is monotone, and in that case you can say that
$$
\sum_{k=1}^n g(k) \leq ng(n),
$$
a bound which is often quite good.


How can I academically say that 'one computer is slower than the other'?

Let me see if I can clear up a few potential misconceptions here.

Sometimes people think that when they write a research paper they have to use fancy language: it's not enough to just say what they mean, but rather, it has to be written in academic code with more complex-sounding language.  Or, they think that using bigger words will make them sound more authoritative.  This is not the case.  If anything, it leads to papers that are overly pompous and unnecessarily hard to read.

Instead, I suggest you figure out what you mean, and then write that.  Don't worry too much about how to say it (whether the word you are using is OK in a research paper).  Do worry about being precise: figure out exactly what you mean, and then be precise in your wording.

You have a good intuition.  Your hesitation about just saying one processor is slower than another is valid.  (But not because you can't say one thing is slower than another in a research paper.)  The issue I see with that wording is that it is not very precise.  There are many things that 'slower' could mean.

What exactly do you mean by 'slower'?  Slower in what way?  And how do you know?  What evidence do you have?  Can you quantify it?  How would you measure 'slowness' in a quantitative, defensible way?

Once you can answer those questions, then you can figure out how to write something more convincing in your paper.  For instance, "processor X is 20% slower on the SpecCPU benchmark than processor Y" is more precise than "processor X is slower than processor Y", and backs up the claim with evidence.

But first you need to figure out precisely what you mean by 'slower', and why it matters to your argument, and then you can figure out how to be more precise in what you write and what evidence you can provide to back up your statement.

You won't always need to write with this level of care and precision.  Sometimes, when you are just providing intuition or background, the specifics don't matter so much, and then you can just say that X is slower than Y.  But if that statement plays a key role in your paper -- maybe it is a key part of the motivation for your paper, or it is a key part of the reasoning that underpins the design of your system -- then you should try to  be as precise as you can, and provide evidence for the statement.


The origin and the meaning of "Abstract Syntax Tree"

You are asking three questions.  I will answer one.

I don't think "abstract syntax tree" is a misnomer.  It aims to represent the syntax of the expression.  It is not claimed to represent all of the meaning (semantics) of the expression.  The issue with bound variables that you mention relates to semantics rather than syntax.

Also, remember that names are merely that: references to some concept, to serve as an aid to communication.  Sometimes the concept is subtle or nuanced enough that no name is going to fully represent all the complexities of the concept, so we choose the best name we can (while keeping it fairly short).  And a name is just an aid to communication, so not all concepts have a fully precise, rigorous definition -- if it is used in a way that aids understanding and facilitates communication, that is often  OK.


Understanding the basic concepts in memory organisation

One can derive the page size from knowing that the page table has three levels, the virtual address space is 46 bits (assume byte addressing), and a PTE is 4 bytes. P bits (where P = log2(page_size)) of the virtual address are not involved in the translation (these provide the offset within the page), so the three levels must translate a 46-P bit address value.

Each node of the page table contains page_size/PTE_size entries, and so each node covers log2(page_size/PTE_size) bits, which is P-2 bits. The page size can then be derived since 46 = (P-2)*3 + P.

(In a simple hierarchical page table, the first level is a single page [in the given design providing 2(P-2) entries]. Each valid entry points to a page-sized table at the second level. Likewise each valid entry in the second level points to a page-sized table in the third level. Each valid entry in the third level provides a page translation. If all the first and second level entries were valid, there would be 2(P-2) * 2(P-2) third level tables each with 2(P-2) entries. Thus 2(P-2)*3 entries would be available, each covering 2P (page_size) bytes.)

With respect to page coloring, one must determine the number of bits that are not part of the page offset which are used for indexing the cache. The number of sets is equal to cache_size/block_size/associativity, so to index to a specific set requires log2(cache_size/block_size/associativity) bits. The offset within the block uses log2(block_size) bits. Using C= log2(cache_size), B= log2(block_size), and A=log2(associativity), C-B-A bits are used to index the set and C-B-A+B, i.e. C-A, bits are used to address the given byte.

Since only P bits are provided as part of the page offset, C-A-P bits use virtual address bits. In order to avoid the problem of two different virtual addresses with the same physical address mapping to different sets, the virtual addresses of any physical pages that are so shared can be colored, i.e., share the same value for the C-A-P virtual address bits. (This forces them to map to the same set. With tagging based on physical addresses, this is sufficient to avoid aliasing issues like a write to one virtual address not updating a cached entry at the same physical address but a different virtual address.)

Each index group is called a color, so to provide C-A-P virtual address bits requires 2(C-A-P) colors.

(The above assumes an "ordinary" cache. Indexing not using simple modulo 2N, e.g., skewed associativity, would have different coloring requirements; but such complexities are typically ignored for problems like this.)


How to keep track of changes done to concurrent stacks?

I would use doubly-linked lists instead of opaque stacks for this.

Node = {
    type : "INT" or "FLOAT"
    value : int or float
    prev-generic : pointer to Node
    next-generic : pointer to Node
    prev-specific : pointer to Node
    next-specific : pointer to Node
}

Now you can keep three lists: a list of ints (using the specific pointers), a list of floats (using the specific pointers), and a list of both (using the generic pointers). If you keep track of the head of each list, you can treat them as stacks (pushing and popping in $O(1)$), and a popped node can also be deleted from both stacks in $O(1)$ just like in a normal doubly-linked list.


how to maximise the no of edges selected in the graph in form of cycles of unbounded length?

A solution is to solve the assignment problem. Let's call $G(W, E)$ your initial graph and build a weighted bipartite graph $G'(U,V,E')$:

on the first side $U$, you have one vertex $u_i$ for $w_i \in W$. In the kidney exchange analogy they are the donors.
on the other side $V$, you also have one vertex $v_i$ for $w_i \in W$. In the kidney exchange analogy they are the recipients.

Now, for every $e \in E$ linking $w_1$ and $w_2$, put two edges in $E'$:

$u_1$ to $v_2$, weight $0$
$u_2$ to $v_1$, weight $0$

They represent the potential trade.

Also, for every $w_i \in W$, add an extra edge in $E'$:

$u_i$ to $v_i$, weight $1$

These edges represent the possibility to have no cycle for $w_i$ in the optimal solution.

Now solve the assignment problem using Hungarian algorithm ($O(n^3)$), trying to minimize the edges selected in the assignment. You get the optimal solution maximizing the number of vertex covered by cycles.


Which method for ODE instead of Euler's?

There are lots of methods. I have usually found a 4th order adaptive step size Runge Kutta method to work fairly well. A Leapfrog method might better preserve invariants over the long term. I'm afraid I don't know enough about reaction-diffusion systems to know how that might change my answer. You might look into our sister sites in scientific computing, computational sciences, etc. for more information. If you're not already familiar with the "numerical recipes" series, that could prove very useful, although it may not have anything exactly suited to your needs.


Pseudo-Proof of Constrained Sudoku is co-np

No, it's not a persuasive proof.

Before you can have a valid proof, you must first precisely state whatever it is you are trying to prove.  You haven't done that.

A language (a decision problem) is in co-NP if it satisfies certain requirements.  You have not defined a language; you have not defined a decision problem.  You use the phrase "Constrained Sudoku" but you have not given a precise definition of what formal language that is intended to refer to.

What you list as a "definition" of co-NP is actually an English-language summary of the definition; it's not a substitute for knowing the precise mathematical definition.

The reasoning in your "proof" is faulty.  You write:

  I use an algorithm that in essence says "no" when [...]. Therefore, Constrained Sudoku is co-np.

That doesn't follow.  Just because you have an algorithm that sometimes says no, doesn't mean that the corresponding problem is in co-NP.  There are additional requirements, which you haven't checked.

I'd like to give some general advice.  Before trying to tackle this problem, I suggest you spend a bunch of time studying the fundamentals.  Set aside Sudoku and your ideas for a few weeks, and find an online course where you can learn complexity theory.  That will give you a mathematical framework that, once you've learned it, you can come back and apply to Sudoku.  Until you've done that, it is pointless to continue trying to frame questions like this.


Draw a Turing machine that decides the language of all words over the alphabet {a, b} that have an odd number of a’s and an odd number of b’s

Yes. "Words over the alphabet $\Sigma=\{a,b\}$" means that the input can be any string containing $a$s and $b$s in any order, and "decide" means that the machine must halt (accept or reject) on every input, and not get into an infinite loop.