Why there is no Turing Machine that accepts the Diagonal Language?

In the following I assume that the matrix has an 1 in coordinates $(i,j)$ if $M_i$ accepts $\sigma_j$ and a $0$ otherwise (swapping all 1s and 0s does not affect the argument).
Consider the language $L = \{\sigma_i \in \Sigma^* : \sigma_i \not\in L(M_i) \}$ that contains all the words $\sigma_i$ such that the entry at coordinates $(i,i)$ of the matrix is $1$. I will first show that $L$ is not acceptable.
Suppose towards a contradiction that there is some Turing machine $M^*$ that accepts $L$.
Since the set of Turing machines is enumerable, and the rows of the matrix are associated with an enumeration of all Turing machines, there must be some integer $i \ge 1$ such that $M_i = M^*$.
Then consider the word $\sigma_i$ and suppose that the entry at coordinates $(i,i)$ is $1$.
From the way the matrix is constructed you know that $M_i$ accepts $\sigma_i$. However, by the definition of $L$, you also know that $\sigma_i \not\in L$. This implies that $M^* = M_i$ cannot accept $\sigma_i$. This is a contradiction.
If the entry at coordinates $(i,i)$ is $0$, then $M_i$ does not accept $\sigma_i$. However, $\sigma_i \in L$ implying that $M^* = M_i$ accepts $\sigma_i$. Again, this is a contradiction.
Going back to your language $L_d$: if $L_d$ were acceptable then so would be $L$.
Suppose towards a contradiction that there is a Turing Machine $M$ that accepts $L_d$.
To accept $L$ proceed as follows:

find the index $i$ such that $\sigma_i = x$. This can be done by enumerating the words in $\Sigma^*$.
Simulate $M$ with input $i$.
If $M$ with input $i$ halts and accepts, accept.

Since this is a contradiction, $L_d$ cannot be acceptable.


Defining $a^n b^{n^2}$ with one existential SO binary relation

First off, I assume you also want to have a binary relation on the domain, acting as a linear order: <. Furthermore, I assume you want to deal with existential second-order logic, which in general allows more than one existential quantifiert.

Then, you can employ Fagin's theorem: wikipedia
And what remains to show is that you can recognize the language $a^{n}b^{n^{2}}$ in polynomial time. Can you do that?

Edit:
Now, since it is clarified that you indeed want to just have an existential binary relation, consider the following:

Büchi-Elgot-Trakthenbrot tells us that regular languages (which yours is not, but that needs a prove) are exactly those that can be described by MSO. The prove gives already big insights in how many different variables you need.
Those languages definable in MSO are exactly those that are definable in existential MSO (see for this Finite Model Theory by Ebbinghaus and Flum, thm 6.2.3)
Those languages definable in existential SO are those recognizable in NP, that's Fagin's theorem.

So you have that e-MSO matchs the regular languages. If you can prove that the different existential quantifiers in BET are necessary for recognizing a language and a binary relationvariable cannot encode the unaries, you are done.

A different approach (possibly more fruitful) is to argue the following way:
The constraint $a^2 = b$ is a meta constraint. You have to emulate this inside your language to get it in the object-world. Now im general SO over the empty signature is strong enough for such, but this is a different exercise. So you have to show two things:
Is your framework strong enough to emulate $x \mapsto x^2$ relative to the discrete order? Pay attention, Beth's Definability Theorem does fail in general in the finite, as does Craig's Interpolant Theorem (both for FO). This is also in above's book, 3.5.1.
If you succeed in doing so, you still have to following problem: You need to get the "meta-size" of $U_a$ and $U_b$ into the object language. This is possible if you allow existential quantifiers of the form "exists exactly n many x:", which is possible in FO. However, you can only do this for a fixed number, additionally, you cannot get the "object-size" into the meta language. You could employ counting to test for sizes. In the MSO setting, they are of the form "$C_n(X)$ which is satisfied iff $ X mod n = 0$. These are not possible to emulate with just a binary relationvariable and FO. Can you show that even using those, you cannot get enough?

Another edit: Lets consider the solution with two binary relations, $R$ and $S$. I'll furthermore use $\bot$ as the smallest element of the order, $\top$ as the largest.

$\forall x, y: (x,y) \in R \implies U_a(x) \wedge U_b(y)$
$\forall x: ((x,\top) \in R \iff x = \bot) \wedge ((\bot,x) \in R \iff x = \top)$
$\forall x: \exists y: (x,y) \in R$
$\forall y: \exists! x: (x,y) \in R$
$\forall x_1, x_2, y_1, y_2: x_1 < x_2 \wedge U_a(x_1) \wedge U_a(x_2) \wedge (x_1, y_1) \in R \wedge (x_2, y_2) \in R \implies y_2 < y_1$

Well, $R$ does split $U_b$ into $|U_a|$ many equivalence classes, each of which is not empty and the smaller the values in $U_a$, the large the corresponding values in the factorized $U_b$. A model of this sentence can look like this (numbers being the elements in $U_a$ and letters being the elements in $U_b$ factorized by the equivalence relation induced by $R$.

  w = 1-2-3-cc-bbbbbbb-a

What is left now is to make sure that the equivalence classes have the appropriate size. For this, note that we can indeed encode $x \mapsto x^2$ inside a binary relation (somewhat). See here that if $n = 1$, we have to append 1 element to the end and if $n = m + 1$, then for this one element more in $U_a$, we have to add as many elements to $U_b$ as we did for m, and two additional ones ($(n+1)^2 - n^2 - (n^2 - (n-1)^2) = 2$, aka when considering adding +1 repeatedly to $n$, one has to add 1, 3, 5, ... to $n^2$).

So, let's encode this behaviour with $S$:

$\forall y_1, y_2: (y_1, y_2) \in S \implies U_b(y_1) \wedge U_b(y_2)$
$\forall y: \neg (y, \top) \in S$ (probably redundant)
$\forall y_1: (\exists y_2: (y_1, y_2) \in S) \implies (\exists! y_2: (y_1, y_2) \in S)$
$\forall y_1: (\exists y_2: (y_2, y_1) \in S) \implies (\exists! y_2: (y_2, y_1) \in S)$
$\forall y_1, y_2: (y_1, y_2) \in S \implies (\exists x_1, x_2: (x_1, y_1) \in R \wedge (x_2, y_2) \in R \wedge \neg \exists x_3: (x_1 < x_3 \wedge x_3 < x_2) \wedge x_1 < x_2)$
$\forall y_1: (\exists x_1, x_2: x_1 < x_2 \wedge (x_1, y_1) \in R) \implies \exists y_2: (y_1, y_2) \in S$

This asserts that $S$ acts only on $U_b$, that if it is defined, it'll be uniquely defined (an injective partial function so to say, I'll use it from now on as a function), nothing is mapped to the largest element and whenever "$y_2 = S(y_1)$", than $y_2$ is in the equivalence class induced by the direct successor of the inducer of the equivalence class of $y_1$. Furthermore, $S$ is defined for each element that is not member of the "least" equivalence class.

With the help of this auxiliary function, we can control the size of the equivalence classes produced by $R$:

$\forall x: \bot < x \wedge U_a(x) \implies (\exists x': x' < x \wedge (\neg \exists x'': x' < x'' \wedge x'' < x') \wedge (\forall y: (x', y) \in R \implies (x, S(y)) \in R \wedge \exists^2 z: U_b(z) \wedge (x, z) \in R \wedge \neg \exists q: S(q) = z \wedge \forall w: (x, w) \in R \implies (w = z \vee \exists y: (x', y) \in R \wedge w = S(y)))$

This formula expresses that for each element in $x \in U_a$, which is not the smallest one, there is a next smaller one $x'$. The elements which are paired with $x'$ in $R$ translated with $S$ are paired with $x$ in R, there are two additional elements which are not the image of any of those. Lastly, there are no elements paired with $x$) besides these two additionals and those that came from $x'$.

The following is now up to you:

Prove that all models of this sentence are words of the form $a^nb^{n^2}$
Prove that every word of the form $a^nb^{n^2}$ does satisfy this sentence
Show that you can indeed encode the two relations into one


Anonymization of dataset preserving unique identities

The point of k-anonymity is that you can't uniquely identify your patients. So I will rephrase your question:

  Given two anonymized tuples $x$ and $y$, can we tell if they are anonymizations of the same person?

Let's suppose for purposes of contradiction that we could. Then this means there is a "meta-tuple" which uniquely identifies a patient. But this violates anonymity (unless $k=1$). So it is impossible.


After stereo image rectification, why does the relation between disparity and depth still apply?

Image rectification does not make this assumption valid.

Yes it does!

From the wiki: https://en.wikipedia.org/wiki/Image_rectification

  Image rectification warps both images such that they appear as if they have been taken with only a horizontal displacement and as a consequence all epipolar lines are horizontal.

The term can be used in an overloaded manner though, by instead implying that projective distortions from the camera are removed. So you have to be careful.


How can I optimize 3 variables in order to maximize the end product?

This area is known as black-box optimization: you have a function $f(x,y,z)$ where you have the ability to evaluate $f$ on an input of your choice, and you want to find $x,y,z$ that maximizes $f(x,y,z)$.  (Here $x$ is the decision threshold, $y$ is the maximum % gain per trade, and $z$ is the stop loss, and $f(x,y,z)$ is the amount of ending money at the end of a backtest with those parameters.)

There is a broad literature on black-box optimization, with many methods you could try.  See, e.g., Google Vizier, BBComp, and derivative-free optimization; there are many other resources as well.

One last warning: your current procedure is likely to greatly overfit.  If you get a rate of return of 10% on your historical data, that doesn't mean this is expected to give you a rate of return of 10% on future data; the future return rate will probably be far lower, due to overfitting.  If you want to estimate the likely future rate of return, I suggest you split your historical data into a training set and a validation set (e.g., 4 months into the training set, 3 months into the validation set).  Use the training set for the backtesting and to select the parameters.  Then, once you have picked a value for the parameters, you can measure how well it performs on the validation set.  To avoid bias, you're only allowed to use the validation set once -- if you don't like the results you get on the validation set, you're not allowed to go back to the training set and try to choose new parameters.

Personally, I suspect that 7 months won't be nearly enough.  There are financial behaviors that only occur once every few years (e.g., due to financial cycles that occur on a multiple-year horizon), so it's likely that optimizing based solely on 7 months of historical data could lead you to parameters that might perform badly when the situation changes.


Is there a decision algorithm with time complexity of Ө(n²)?

Yes: Checking that a string is a palindrome takes $\Omega(n^2)$ on a single tape Turing machine.

In general the time hierachy theorem implies that there are such problems for most reasonable functions.

For RAM, edit distance can't be solved in $O(n^{2-\epsilon})$ for $\epsilon > 0$ unless the strong exponential time hypothesis is false.


counting arithmetic progressions $a, a+r, a+2r$ in a list

Given that the OP is rather unprecise as to the kind of numbers he is
considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to limit the
number of assumptions I can make. And while I am at it anyway, I will
generalize a bit.

This builds on the contributions of previous answer and comments, by
Rick Decker, Hendrik Jan. and HEKTO.

Generalized statement of the problem

We consider four sets of values $\mathcal{U}, \mathcal{V}, \mathcal{W}, \mathcal{Z}$, two functions $f:\mathcal{U}\times
\mathcal{V}\to \mathcal{Z}$ and $g:\mathcal{W}\to\mathcal{Z}$. Given 3
sets or
lists of values $U,V,W$, respectively from $\mathcal{U}, \mathcal{V},
\mathcal{W}$,  count the number of triples $(u,v,w)\in U\times V\times W$ such
that $f(u,v)=g(w)$. Each computation of the functions $f$ and $g$ is supposed to
be in constant time.

Let $n=max(|U|,|V|,|W|)$

General solution

This is essentially HEKTO's suggestion.

Build a hash table containing each value $w\in W$ indexed by
$g(w)$. This has a cost $O(n)$ under the Simple Uniform Hashing Assumption(SUHA). Without the SUHA, one can use a balanced tree with complexity $O(n\log n)$.

Then for each $u\in U$ and for each $v\in V$ check whether
$f(u,v)$ is in the hash table in constant time (or in the balanced tree in logarithmic time). If it is in an entry $g(w)$, then add $(u,v,w)$ to the
list of solutions (or increase the solution count by one).

Complexity is $O(n^2)$ with hash table, under SUHA, or $O(n^2\log n)$ with a balanced tree.

Case of ordered sets

This is essentially Hendrik Jan's suggestion.

We assume that one of the two sets $\mathcal{U}$ or $\mathcal{V}$ (say $\mathcal{V}$, w.l.o.g.) and the
set $\mathcal{Z}$ are totally ordered and that the function $f$ is monotonic with respect to
the argument in the ordered set (here the second argument).

Then we can have a modified algorithm that does not need a hash table.

First sort the set $V$.

Build a list $L$ of pairs $(w,g(w))$ for all $w\in W$, sorted with respect
to the second element.

Then for each $u\in U$, compare the ordered values of $f(u,v)$ with
the ordered values $g(w)$ of the pairs in $L$, by moving up the two
list $V$ and $L$ as you would do for set intersection, and add the answer
$(u,v,w)$ whenever $f(u,v)=g(w)$ for some pair $(w,g(w))$.

Complexity is $O(n^2)$.

Application to "numbers" and arithmetic progression

We consider the initial problem of detecting arithmetic progressions
in the elements of a list.

The three lists of the abstract case are the same list. The function $f$
is addition, and the function $g$ is doubling (i.e. product by 2).

The ordered set solution applies well to integers, rationals, or reals (with
some care).

Complex numbers are not an ordered field. However they can be considered as an ordered groups with respect to addition, by prioritizing coordinates, so that $a+ib> a'+ib'$ iff $a>a' \vee (a=a' \wedge b>b')$. So the ordered set construction can be used.

The hash table algorithm seems necessary in the case of
$\mathbb{Z}/p$ (i.e. integers modulo $P$) since non-trivial linearly ordered groups are
necessarily infinite, which is not the case for $\mathbb{Z}/p$.

However the ordered set construction could be adapted to
$\mathbb{Z}/p$ without loss in complexity, by allowing the list $L$
to be scanned twice, with some proper bookkeeping.


Without using pumping lemma, can we determine if $A =\{ww \mid w \in \{0,1\}^* \}$ is non regular?

Your idea (while interesting) is unlikely to work for two reasons:

How would you express $A$ as a concatenation of a language with itself?
If $L$ is non-regular, it may still be the case that $LL$ is regular. See this post:
Is $A$ regular if $A^{2}$ is regular?

You could prove it using the Myhill-Nerode theorem - show that there are infinitely many equivalence classes. Or you could simply use a pumping argument without the lemma. That is, follow the proof of the lemma for this particular language.


Rearranging strings so that the Hamming distance between them is 1

Grid graphs are finite node-induced graphs of the infinite planar grid (whose vertices are integral points, and two vertices are linked when their Euclidean distance is 1). A. Itai, C. H. Papadimitriou, and J. L. Szwarcfiter proved that the Hamiltonian path problem on grid graphs is NP-complete.

To reduce that to your problem, suppose the grid graph has $m$ rows and $n$ columns. The $i$-th row is labeled with the string $a^ib^{m-i}$, and the $j$-th column is labeled with the string $a^jb^{n-j}$. Then a vertex corresponds to the concatenation of the two labels of its row and column. Now it is easy to show the unit disk graph under Hamming distance over all these concatenated strings is exactly the same as the original grid graph.


Pumping Lemma for $\mathcal{L} = \{ \omega \omega^R a^{|\omega|} : \omega \in \{a,b\}^* \} $

The problem is not very hard if you break the proof of the pumped string not being in the language into cases. So let's work this out.
$$L = \{\omega \omega^Ra^{|\omega|}\;| \; \omega\in \{a,b\}^*\}$$
For every $n$, let us consider the string $\omega = a^nb^nb^na^na^{2n}$. You can check that this does belong to the language.
We are supposed to show that for any partition $\omega=uvwxy$, such that
$$|vwx|\leq n \;\mbox{and} \; |vx|\geq 1$$ there exists $k$ such that $uv^kwx^ky \notin L$.
Case1: $v,x$ lie inside the first $a^n$. Since, $|vx|\geq 1$, we can see that for $k=0$, the resulting string will not be in $L$.
Case2: $v,x$ lie in the starting $a^nb^n$. You should notice that if you again pump the substrings with $k=0$, then the substring cannot be broken into $\omega\omega^R a^{|\omega|}$, because the count of $a$'s at the end remains the same, and we cannot have an $\omega$ of length $2n$ in the resultant string for it to happen.
Case3: $v,x$ lie inside the first $b^n$. Here, again, you can see how $k=0$ will pump the string outside the language.
The further cases are similar to what described above. Work it out for better understanding. Please let me know if you aren't comfortable with any part of this solution.
PS: The $a^{|\omega|}$ which makes you sick was the sole reason this language is not a CFL, XD.


How does the system know how to read the correct block from a disk?

Finding the right track is relatively easy. There is a motor which can be moved a precise distance. Then the head can measure magnetism to the right and the left and use this to move to the precise centre of the track.

The sectors all have a header. The read head passes sectors at high  speed. The start of the header has a distinct pattern that cannot be found inside a sector. So the read head can wait until it finds the start of a sector. The header also contains a number identifying the sector so the read head knows when it reaches the correct sector and can start reading.

In practice, all sectors on the track will be read in case another sector is needed soon after.


Calculate minimum and maximum Ethernet (IEEE 802.3) frame size from frame format

The preamble and SFD do not count towards the frame size since they are only part of the Ethernet packet (i.e., layer 1), not of the Ethernet frame (i.e., layer 2); see here, for instance. Recall that Ethernet is not a pure layer 2 protocol but actually a mix of layers 1 and 2.


Why is using a lexer/parser on binary data so wrong?

In principle, there is nothing wrong.

In practice,

most non-textual data formats I know are not context-free and are therefore not suitable for common parser generators. The most common reason is that they have length fields giving the number of times a production has to be present.

Obviously, having a non context-free language has never prevented the use of parser generators: we parse a superset of the language and then use semantic rules to reduce it to what we want.  That approach could be used for non-textual formats if the result would be deterministic. The problem is to find something else than counts to synchronize on as most binary formats allow arbitrary data to be embedded; length fields tell you how much it is.

You can then start playing tricks like having a manually writen lexer able to handle that with feedback from the parser (lex/yacc handling of C use that kind of tricks to handle typedef, for instance).  But then we come to the second point.
most non-textual data formats are quite simple (even if they are not context-free).  When the counts mentioned above are ignored, the languages are regular, LL1 at worst, and are thus well suited for manual parsing techniques. And handling counts is easy for manual parsing techniques like recursive descent.


Unfortunately, there is no "fast" way to count them generally as this problem is #P-Complete. This means that it is basically as hard as every counting version of NP-problems, and is likely not solvable in polynomial time.

For small examples such as this one you can come up with some ad-hoc counting technique however. In this case would try listing all permutations of E,F,G and see how many choices I have for the rest if I insert them in some order. Like this:

EFG: 1+2+4+6 = 13
(1 choice for A, then 2 for B, 4 for C, 6 for D)
EGF: 1+2+4+5 = 12 (in A,B,C,D order)
FEG: 1+2+4+5 = 12 (in B,C,A,D order)
FGE: 1+2+4+6 = 13 (in B,C,D,A order)
GEF: 1+2+4+5 = 12 (in D,C,A,B order)
GFE: 1+2+4+5 = 12 (in D,C,B,A order)

So in total 4*12 + 2*13 = 74 topological orderings (with some non-negligeable probability that I miscounted somewhere).


O(B) algorithm to find positions of all permutations of smaller string in a bigger string with length B - how is this possible?

I think a hash is the wrong approach. Instead you can use auxiliary variables: an array $A$ and an integer $c$. Basically $A$ tracks the error in the number of occurrences of each character and $c$ tracks the number of non-zero errors. Instead of a hash update you update the count of the character which drops out, then update $c$ if it changed from or to zero, then repeat for the character which is coming in. After that, if $c=0$ you found a permutation of $s$.


Are tiny point-symmetric grids of two Pentominos impossible to solve?

Let's see what happens after you rotate the partition around the board's center. The region in which one part maps onto the other part is point symmetric around the board's center. Therefore, the region in which one part is mapped onto the same part is:

also point symmetric with the same center
itself partitioned into two point symmetric regions with the same center and
those two regions have the same area

The smallest non-empty such region has an area of 4. There are three possible configurations (I tetromino, S/Z tetromino, O tetromino). To connect the outer partition of the I tetromino or the S/Z tetromino into a single polyomino you need four extra tiles. For the O tetromino you need five extra, and furthemore you can't connect both regions at once.

Therefore, there is no partition of a 10-tile point symmetric board into a pair of incongruent pentominoes, and only two partitions of 12-tile point symmetric boards into a pair of incongruent hexominoes, up to symmetry:

I:   S/Z:
@@@@ @@@.
.@@. @...
.... @@..


Given $T(n) = \sum_{i = 0}^{\log n} i 2^i$, what is $O(T(n))$?

There are two ways to calculate the sum. The first way is to write it as $$\sum_{i=1}^{\log n} \sum_{k=1}^{i}2^{i}.$$

You change the order of sum and the calculation is the sum of geometric series.

Another way is to write it as $f(x)=\sum_{i=1}^{\log n} x^{i}$, and find the $xf`(x)|_{x=2}$, again a sum of geometric series.


Why in a min priority queue (heap based) it is called "decrease-key" and not just "set-key"?

Good question. One of the important applications of the data structure PriorityQueue is in Dijkstra's algorithm. Each node gets a distance from the initial node, which is updated when shorter paths are discovered. Hence updates only change the key in one direction.

The problem in the implementation of DecreaseKey is not that it is only decreasing (rather than updating the value). For a binary heap there are quite efficient methods both for increasing and decreasing. They both swap nodes with other nodes along a path in the tree (either upwards or downwards). The problem is actually knowing where to find the key. You cannot efficiently search for it, so a separate "index" has to be kept. When an update is done along a path, not only the decreased key is changed in the indax, but also the other keys along the path.

For abstract data structures we want to specify only the operations that are important in a particular context. So we have DecreaseKey only, given the Dijkstra motivation. Although for binary heaps extending the operations might be elementary, this might not be the case for other implementations of the PriorityQueue, like Leftist Heaps, Fibonacci Heaps, or Brodal Heaps.

What any particular implementation will do when the new value is in the wrong direction is up to that implementation.


dynamic programming exercise on cutting strings

The basic idea is: Try out all cut positions as first choice, solve the respective parts recursively, add the cost and choose the minimum.

In formula:

$\qquad \displaystyle \operatorname{mino}(s, C) =
  \begin{cases}
    |s| &, |C| = 1 \\
    |s| + \min_{c \in C} \left[ \begin{align}&\operatorname{mino}(s_{1,c}, \{c' \in C \mid c' < c\})\ \\ +\ &\operatorname{mino}(s_{c+1,|s|}, \{c' - c \in C \mid c' > c\}) \end{align}\right] &, \text{ else}
  \end{cases}$

Note that applying memoisation to this recursion actually saves work as switching the order of any successively applied pair of cuts results in the same three subproblems being solved.


Is Unification "an Implementation of Existential Quantification"?

It's possible you're paraphrasing me. I've certainly said things similar to that e.g. here.

A more precise statement would be that existential quantification in logic programming languages is (typically) handled by introducing a unification variable. To perform existential introduction, you need to have a term $t$. The rule looks like: $$\dfrac{\Gamma\vdash P[t/x]}{\Gamma\vdash\exists x.P}$$

One way to implement this is to just guess a term $t$ and then see if we can backchain $P(t)$. Of course, for a language like Prolog, there are an infinite number of possible terms, and you have no guidance on what term to guess. A different option is to have $t$ be a meta-variable that stands for a term and continue execution on the hope that we can constrain $t$ enough to know what to decide later. This is essentially what a unification variable is. Unification itself just constrains what possible terms that meta-variable can be. Then, instead of actually enumerating the (now constrained) terms, we usually return the (simplified) constraints themselves as a compact representation of the set of possible terms, assuming they aren't contradictory (i.e. that that set isn't empty).

The occurs-check is simply the enforcement of the fact that usual term languages don't have infinite terms. You can consider other term languages that can represent these terms leading to things like rational tree unification.

Unsurprisingly, the operation unification itself most directly implements is equality. If we did the "exhaustively enumerate terms" approach to handling existential quantification, all the places where we (implicitly) use "unification" could just be straightforward syntactic checks of ground terms. With meta-variables, they instead produce constraints. Of course, this suggests the natural and common generalization of allowing constraints other than syntactic equality, and this leads to constraint logic programming. One generic example of such a constraint is disunification which states what a term (potentially containing meta-variables) cannot be. It is the negation of unification, $t\not\equiv s$ states that for all substitutions $\sigma$, $t[\sigma]\neq s[\sigma]$.


Underlying codes for Niederreiter cryptosystems

According to Sendrier, Niederreiter systems are only known to be secure when used with Goppa codes. All other families of codes which have been tried have been broken. You are suggesting a code superficially related to the Goppa code but probably having very different properties. Hence it is likely to be insecure (or perhaps useless for other reasons, such as low rate or low distance).

More generally, cryptosystems are surprisingly brittle. I would leave them to the experts.


what does the author mean by directory structure in operating system?

Step 3 of that description is indeed a bit confusing, and your comments are right.  The short answer is that the OS keeps track, in memory, of the set of mounted file systems and where they are mounted.


Sort an array with a constant number of unsorted elements

Denote the array by $A_1,\ldots,A_n$. If $A_i > A_{i+1}$ then at least one of the two elements is out of place. We scan the array, and each time we find such a pair, we remove both elements. In $O(n)$ time, we obtain a sorted subarray $B$ together with $O(1)$ many unsorted elements, forming a set $C$. We sort $C$ in $O(1)$ and merge it with $B$ in $O(n)$.


How a computer ensures that a location in RAM is empty

In a multitasking system, every process receives its own virtual address space, i.e. the system maps the addresses from $0_h$ to $FFF\cdots F_h$ to available storage space which can reside partly in RAM memory and partly on disk (physical storage). The mapping is made for every process independently, allocating whole pages (typically 2K bytes) at a time.

The compiler is completely unaware of where the data will actually be stored and is free to use the whole address space. The system does the necessary housekeeping and ensures that there are no conflicts.

Actually, the mapping is completely dynamic and pages are moved between RAM and disk, following the needs of the processes and in a way to optimize the access speed. There is not even a relation between the size of the virtual address space and the amount of RAM and disk available.

To summarize, memory allocation is transparent to the compiler, as if the process was alone; only the system knowns which physical pages are free or allocated to a particular process.


What is the right term/theory for prediction of Binary Variables based upon their continuous value?

I would say that this approach falls under the umbrella of iterative rounding. I believe that the seminal paper regarding this kind of strategy is [1]. The heuristic outlined here differs in signifcant ways from the algorithm described in Jain's paper but I think the basic idea is in the same vein.

Jain, K. (2001). A factor 2 approximation algorithm for the generalized Steiner network problem. Combinatorica, 21(1), 39-60.


Why every point is in exactly one pair in Well Separated Pair Decomposition(WSPD)

OK, I found it. The definition says

  for any two distinct points ...

It means I must consider two points, not a one solitary. $x_1$ is well separated with $x_3$, and it is well separated with $x_2$ as well, But there is exactly one pair that separates $x_3$ from $x_1$ and also there is exactly one pair that separates $x_2$ from $x_1$


Length of an Edit Script and the Number of Deletions

This is a straightforward consequence of the fact that the edit script only contains insert and delete operations.  It follows from a little bit of basic arithmetic -- it's nothing especially deep.

Consider a script that contains $I$ insert operations and $P$ delete operations.  Then the total number of operations in the edit script is $I+P$.  If we're given that the total number of operations is $D$, we know $D=I+P$.  Also we know $M+I-P=N$ (since each insert operation increases the length of the document, and each delete decreases it).  Solving these two simultaneous equations yields the relationship you list.


How to prove the NP-completeness of MOD-PARTITION

Showing that this your problem is in NP is easy.

To show that your problem is NP-hard, reduce from PARTITION. The reduction simply chooses a large enough modulus $k$. Details left to you.


Is asymptotic ordering preserved when taking log of both functions?

If $f(n) = \Theta(g(n))$, then in particular $f(n) = O(g(n))$. This is just like saying that if $x = y$, then in particular $x \leq y$.

Suppose that $f(n) = O(g(n))$. According to the definition, there are $N,c$ such that all $n \geq N$ satisfy $f(n) \leq cg(n)$. Taking logarithms, this implies that $\log f(n) \leq \log c + \log g(n)$. Does this imply the existence of a constant $c'$ such that for large enough $n$, $\log f(n) \leq c' \log g(n)$?

Here is a simple counterexample: $f(n) = e$ and $g(n) = 1$. Clearly $f(n) = O(g(n))$, but $\log f(n) = 1$ whereas $\log g(n) = 0$. However, in this case $\log g(n)$ is not positive, so you may want to rule that case out. However, we can correct this example so that $\log g(n)$ is strictly positive, by taking $g(n) = 1 + 1/n$. In this case $\log g(n) = 1/n$ which is strictly positive, yet still $\log f(n)$ is not $O(\log g(n))$.

Here is a sufficient condition for the deduction to work. Suppose that there exists $N'$ and $C > 1$ such that for all $n \geq N'$, it holds that $g(n) > C$. Then for $n \geq \max(N,N')$, we have
$$\log f(n) \leq \log c + \log g(n) \leq \left( \frac{\log c}{\log C} + 1 \right) \log g(n),$$
and so $\log f(n) = O(\log g(n))$.


Start out by replacing in the grammar all $Z$ by $y$, since from $Z$ this is the only derivation.
Then, you can easily see what $X$ does: from it we can derive $(xy)y^*$ or $(yxy)y^*$, combined can be written as $(xy+yxy)y^*$ as a regular expression (notice that not always you can write down the derivations as regular expressions!)
Now, $Y$ derives either $xy$ or $yX$, and since $X$ derives $(xy+yxy)y^*$, then $Y$ derives $xy+y(xy+yxy)y^*$.
You can now complete the analysis by noticing that $S$ derives either $Yy$ which is $(xy+y(xy+yxy)y^*)y$, or an additional $SX$. I believe from here you already understand what the language is :)


For the answer $\forall \lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$:
I think you have got the right idea. However, this formula is not in CTL since $\lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$ is not a path formula.

By $\forall \lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$, I think you want to say $\forall \Box \left( \lnot \exists \left( \left( \lnot a \right) \bigcup b \right) \right)$, which is the answer.

(If you are observing the system from the very start (i.e., its initial state), the simpler and weaker one $\lnot \exists \left( \left( \lnot a \right) \bigcup b \right)$ would be also acceptable. Please check it and let me know whether it is right.)

As I have mentioned in the comment, there are past CTLs (PCTL) which incorporate past operators facilitating the expression of "time going backwards". Using PCTL (for example in [1]), your property can be directly rendered by $\forall \Box (b \implies \Diamond^{-1} a)$ (Note its syntax!). You can guess the meaning of $\Diamond^{-1}$ easily.

[1] Specification in CTL+Past for Verification in CTL (2000)


Can you form a group with assembly instructions under the MIPS-32 architecture?

Sure.  The integers modulo $2^{32}$ form a group.  The group operation is addition modulo $2^{32}$, which can be implemented by the ADD instruction.  You don't need the NOT instruction.

There are other groups you could form, such as the integers modulo 2, and many more.  I recommend you read the definition of a group and play around with some examples.


Prove or disprove the bound given the recurrence relation

Your recurrence relation is covered by case 3 of the master theorem:

  If

  $T(n)=aT(\frac{n}{b})+f(n)$ where $a\geq 1$ and $b>1$
  $f(n)\in\Omega(n^c)$ where $c>\log_b a$
  $af(\frac{n}{b}) \leq k f(n)$ for some constant $k<1$ and sufficiently large $n$

  then $T(n)\in \Theta(f(n))$

Note that $T(n)\in \Theta(f(n))$ means that both $T(n)\in O(f(n))$ and $f(n)\in O(T(n))$. So $T(n)\in O(f(n))$ follows from $T(n)\in \Theta(f(n))$.

In your case, you have $a=b=2$ and $f(n)\in\Omega(n^2)$ where $2 >\log_2 2 = 1$. The only problem is that you cannot guarantee $2f(\frac{n}{2})\leq kf(n)$ for some constant $k<1$ and sufficiently large $n$.

So you can disprove $T(n)=O(f(n))$ by a counterexample like $f(n)=n^2+\exp(n)\cos^2(\frac{\pi}{2}\log_2 n)$. Not really a great example for a nice exercise, but OK.


Is this a valid representation of a function in Lambda Calculus?

It's valid (because it respects $\lambda$-calculus syntax) but won't work as you expect. To see that just take your favorite language and try it out:

let f = \x -> 2*x
let g = \y -> y+1
let h = \z -> z/2

(\x -> (((fx)g)h))) 1 won't evaluate to $1.5$. Why?

Because $g$ and $h$ are functions and take one argument each, and application happens when there's an abstraction to the left. So if you change the order you will get the expected behavior.

$$ \lambda x. (h (g (f ~ x))) $$

or

$$ \lambda x. ((h  \circ g  \circ f)  ~ x) $$

In Haskell:

(\x -> (h . g . f) x)

where . ($\circ$) is for function composition.

Example:

$$ \big(\lambda x. (h (g (f ~ x)))\big) 1  \rightarrow (h (g (f ~ 1))) \rightarrow (h (g ~ 2)) \rightarrow  (h ~ 3) \rightarrow 1.5 $$


Clarification of the definition of a POMDP

The availability of action $ a $ can be understood as $P_a(u, v) > 0$ for some $ v $

If an action $ a $ is not available in $ u $ then it will have not effect, this means that $P_a(u, v) = 0 $ for every possible $v$


Optimal scheduling order for two queues of jobs

There is a simple pseudo-polynomial time algorithm that works when all tasks take the same unit time. You can transform your problem into this by rounding all completion times to some greatest common divisor, and splitting all longer tasks up into copies of unit portions. E.g. if your original completion times were $6$, $8$ and $12$ seconds you could use $2$ seconds as your unit time. Then you'd have respectively 3 copies, 4 copies and 6 copies of the unit task in a row.
Let's name the two queues $A$ and $B$. Let $T[i,j]$ be the optimal time needed to run the first $i$ tasks from $A$ and the first $j$ tasks from $B$. Let $A[i]$ be the resources required for task $i$ from $A$ and similarly for $B$. Let $m$ be the maximum number of resources available.
Of course $T[x,0] = T[0,x] = x$. Then:
$$T[i,j] = 1 + \begin{cases}T[i-1, j-1] & \text{if }A[i] + B[j] \leq m\\\min (T[i-1,j], T[i,j-1]) &\text{otherwise}\end{cases} $$
If you keep track of your choices you can reconstruct the optimal solution. The above is also amenable to bottom-up dynamic programming, in fact you only need to have two arrays $T_i[j]$ and $T_{i-1}[j]$.

I'm not claiming the above is terribly good or an optimal solution, but it's a simple algorithm that gets the job done. Perhaps someone else has a better answer.


Example of non-regular context free language L such that prefix(L) is regular

Consider the language of words with the same number of a's and b's. It is non-regular but the set of prefixes is the set of all words which clearly is regular.


How does 'deforestation' remove 'trees' from a program?

Yatima2975 seems to have covered your first two questions, I'll try to cover the third. To do this I'll treat an unrealistically simple case, but I'm sure you'll be able to imagine something more realistic.

Imagine you want to compute the depth of the full binary tree of order $n$. The type of (unlabeled) binary trees is (in Haskell syntax):

type Tree = Leaf | Node Tree Tree

Now the full tree of order $n$ is:

full : Int -> Tree
full n | n == 0 = Leaf
full n = Node (full (n-1)) (full (n-1))

And the depth of a tree is computed by

depth : Tree -> Int
depth Leaf = 0
depth (Node t1 t2) = 1 + max (depth t1) (depth t2)

Now you can see that any computation of $\mathrm{depth}\ (\mathrm{full}\ n)$ will first construct the full tree of order $n$ using $\mathrm{full}$ and then deconstruct that tree using $\mathrm{depth}$. Deforestation relies on the observation that such a pattern (construction followed by deconstruction) can often be short-circuited: we can replace any calls to $\mathrm{depth}\ (\mathrm{full}\ n)$ by a single call to $\mathrm{full\_depth}$:

full_depth : Int -> Int
full_depth n | n == 0 = 0
full_depth n = 1 + max (full_depth (n-1)) (full_depth (n-1))

This avoids memory allocation of the full tree, and the need to perform pattern matching, which greatly improves performance. In addition, if you add the optimization

max t t --> t

Then you have turned an exponential time procedure into a linear time one... It would be cool if there was an additional optimization that recognized that $\mathrm{full\_depth}$ was the identity on integers, but I am not sure that any such optimization is used in practice.

The only mainstream compiler that performs automatic deforestation is GHC, and if I recall correctly, this is performed only when composing built-in functions (for technical reasons).


What happens when there is a branch mispredict and an interrupt occurs?

All instructions in the processor are executed speculatively and every instruction that is fetched after a mispredict needs to be cancelled without allowing any of its effects to become externally visible.  This is done with register renaming and a reorder buffer that commits instruction effects in-order.  Instructions from asynchronous interrupt handlers are handled the same way, the main difference (and complexity) being how you refetch them after the mispredict causes them to get cancelled.

Example: you fetch the branch at the address $B$, mispredict its target as $M_0$, and start fetching $M_0, M_1, \cdots, M_n$.  At this point the fetch unit realizes that an asynchronous interrupt, starting at address $I_0$, needs to be handled and proceeds to set $M_{n+1}$ as the predicted EPC, and fetch $I_0, I_1, \cdots, I_m$.  (Note that we've only set the predicted EPC to $M_{n+1}$, not the "real" (externally visible) EPC.)  Now the execution unit finally realizes that the branch at $B$ was mispredicted and that the correct branch target was $T_0$.

At this point we must mark all the instructions $M_0, M_1, \cdots, M_n, I_0, I_1, \cdots, I_m$ as "cancelled."  Luckily none of them have been committed because they are all behind $B$ in the reorder buffer.  Then the execution unit sends a signal to the fetch unit that the correct instruction after $B$ should have been $T_0$, rather than $M_0$.

At this point the fetch unit must realize that there was an asynchronous interrupt handler that had been fetched but not committed.  It could do this, for example, by keeping a counter that is incremented the first time the first instruction of an asynchronous interrupt handler is fetched, and decremented when that instruction retires (is committed).  So the fetch unit sets $T_0$ as the predicted EPC, starts fetching from $I_0$ again (a new copy of the instruction at $I_0$, let's call it $I_0'$), and proceeds with $I_1', I_2', \cdots, I_m'$.  At some point the branch $B$ reaches the head of the reorder buffer and commits.  That means that it records $T_0$ as the correct (externally visible) "next instruction pc".

$B$ is followed in the reorder buffer by a bunch of cancelled instructions, $M_0, M_1, \cdots, M_n, I_0, I_1, \cdots, I_m$, these are not committed, but any resources (e.g., physcial registers) allocated to them need to be returned to the free-register queue.  Finally $I_0'$ reaches the head of the reorder buffer.  It commits.  As part of committing the externally visible "next instruction pc" is copied into the real (externally visible) EPC register.

TL;DR

Register renaming and the reorder buffer make handling mispredicted branches much easier.


Tight bound on the number of intersections between a line and a triangulation

Place $T$ triangles next to each other such that the line $l$ intersects them all. Observe how the number of intersections is $T+1$. Now substitute $T$ with the upper bound on the number of triangles for any triangulation that you mentioned, and we obtain $2n-5+1=2n-4$ as an upper bound on the number of intersections. The example provided in the question shows that the bound is tight.


Time complexity of a function with while loop


Language Recognition Devices and Language Generators

For a language $L$, a recognizer of $L$ is an algorithm that computes

$\qquad \chi_L(w) = \begin{cases} 1, & w \in L \\ 0 , &w \not\in L\end{cases}$.

Note that in computability and complexity theory, these are sometimes called deciders and algorithms that compute

$\qquad \tilde\chi_L(w) = \begin{cases} 1, & w \in L \\ \uparrow , &w \not\in L\end{cases}$

are called acceptors.

A generator or enumerator can be modelled as an algorithm computing

$\qquad e_L(i) = w_i$

where $L = \{ w_i \mid i \in \mathbb{N} \}$. As it turns out, $e_L$ and $\tilde\chi_L$ are equal in power (cf. the set of recursively enumerable languages) but $\chi_L$ is stronger (cf. the set of recursive/decidable languages).

You typically want compilers to be deciders; interpreters are arguably recognisers.

A regular expression (or, for that matter, a grammar) does not fit in this terminology per se. I'd say they give a descriptive representation of their languages while above notions are algorithms representatios. Grammars have a slighly more enumerative feel (since translating them into a top-down generator of words is intuitive) while regular expressions feel more like deciders (via their NFA), but it's also easy to build acceptors from grammars.


Simple paths with halt in between in directed graphs

As Tsuyoshi Ito notes, the first problem can be solved using network flow. This was described in detail in cstheory.


Are all turing complete languages interchangeable

Turing-completeness says one thing and one thing only: a model of computation is Turing-complete, if any computation that can be modeled by a Turing Machine can also be modeled by that model.

So, what are the computations a Turing Machine can model? Well, first and foremost, Alan Turing and all of his colleagues were only ever interested in functions on natural numbers. So, the Turing Machine (and the λ-calculus, the SK combinator calculus, μ-recursive functions, …) only talk about the computability of functions on natural numbers. If you are not talking about a function on natural numbers, then the concept of Turing-completeness doesn't even make sense, it is simply not applicable.

Note, however, that we can encode lots of interesting things as natural numbers. We can encode strings as natural numbers, we can encode graphs as natural numbers, we can encode booleans as natural numbers. We can encode Turing Machines as natural numbers, which allows us to create Turing Machines that talk about Turing Machines!

And, of course, not all functions on natural numbers are computable. A Turing Machine can only compute some functions on natural numbers, the λ-calculus can only compute some functions on natural numbers, the SK combinator calculus can only compute some functions on natural numbers, …. Surprisingly (or not), it turns out that every model of computation (that is actually realizable in our physical universe) can compute the same functions on natural numbers (at least for all the models we have found up till now). [Note: obviously, there are weaker models of computation, but we have not yet found one that is stronger, except some that are obviously incompatible with our physical universe, such as models using real numbers or time travel.]

This fact, that after a long time of searching for lots of different models, we find, every single time, that they can compute exactly the same functions, is the basis for the Church-Turing-Thesis, which says (roughly) that all models of computation are equally powerful, and that all of them capture the "ideal" notion of what it means to be "computable". (There is also a second, more philosophical aspect of the CTT, namely that a human following an algorithm can also compute exactly the same functions a TM can compute and no more.)

However, none of this says anything about

how efficient the various models are
how convenient they are to use
what else they can do besides compute functions on the natural numbers

And that is precisely where the differences between different models of computation (and programming languages) come into play.

As an example of different performance, both a Random Access Machine and a Turing Machine can copy an array. But, a RAM needs $O(size_{array})$ operations to do that, while a TM needs $O(size_{array}^2)$ operations, since it needs to skip across $size_{array}$ elements of the array for copying each element, and there are $size_{array}$ elements to copy.

As an example for different convenience, you can just compare code written in a very high-level language, code written in assembly, and the description of a TM for solving the same problem.

And your light switch is an example of the third kind of difference, things that some models can do that are not functions on natural numbers and thus have nothing to do with Turing-completeness.

To answer your specific questions:

  But can any program written in a Turing complete language be re-written in another?

No. Only if the program computes a Turing-computable function on natural numbers. And even then, it might need a complex encoding. For example, λ-calculus doesn't even have natural numbers, they need to be encoded using functions (because functions is the only thing λ-calculus has).

This encoding of the input and output can be very complex, as can expressing the algorithm. So, while it is true that any program can be rewritten, the rewritten program may be much more complex, much larger, use much more memory, and be much slower.

  What if my Assembly has a LIGHTBUTTON opcode? I physically can't emulate that language on a system (language) without a lightbulb.

A lightbulb is not a Turing-computable function on natural numbers. Really, a lightbulb is neither a function nor a computation. Switching a lightbulb on and off is an I/O side-effect. Turing Machines don't model I/O side-effects, and Turing-completess is not relevant to them.

  On arbitrary real numbers.

Turing-completeness only deals with computable functions on natural numbers, it doesn't concern itself with real numbers.

Turing-completeness is simply not very interesting when it comes to questions like yours for two reasons:

It is not a very high hurdle. All you need is IF, GOTO, WHILE, and a single integer variable (assuming the variable can hold arbitrarily large integers). Or, recursion. Lots and lots and lots of stuff is Turing-complete. The card game Magic: The Gathering is Turing-complete. CSS3 is Turing-complete. The sendmail configuration file is Turing-complete. The Intel x86 MMU is Turing-complete. The Intel x86 MOV instruction is Turing-complete. PowerPoint animations are Turing-complete. Excel (without scripting, only using formulas) is Turing-complete. The BGP routing protocol is Turing-complete. sed is Turing-complete. Apache mod_rewrite rules are Turing-complete. Google for "(accidentally OR surprisingly) turing complete" to find some other interesting examples. If almost everything is Turing-complete, being Turing-complete stops being an interesting property.
It is not actually necessary to be useful. Lots of useful stuff isn't Turing-complete. CSS before version 3 isn't Turing-complete (and the fact that CSS3 is isn't actually used by anyone). SQL before 1999 was not Turing-complete, yet, it was tremendously useful even then. The C programming language without additional libraries doesn't seem to be Turing-complete. Dependently-typed languages are, more or less by definition, not Turing-complete, yet, you can write operating systems, web servers, and games in them.

Edwin Brady, the author of Idris, uses the term "Tetris-complete" to talk about some of these aspects. Being Tetris-complete isn't rigorously defined (other than the obvious "can be used to implement Tetris"), but it encompasses stuff like being high-level enough and expressive enough that you can write a game without going insane, being able to interact with the outside world (input and output), being able to express side-effects, being able to write an event loop, being able to express reactive, asynchronous, and concurrent programming, being able to interact with the operating system, being able to interact with foreign libraries (in other words: being able to call and be called by C code) and so on. Those are much more interesting features of a general purpose programming language than Turing-completeness is.

You may find my answer to the question you linked interesting, which touches on some of the same points even though it answers a different question.


Algorithm for factoring elements of permutation groups?

It seems that your problem could be stated in terms of finding paths in Cayley Graphs, which might interest you:

Cayley Graph - Wikipedia


If the tree hasn't any single-children the hypothesis trivially holds.
Given a single-child vertex $v$, we can show that the parent of this vertex $v$ cannot be a single-child.
Let $p(v)$ be the parent of $v$.
If $p(v)$ is the root then $p(v)$ isn't a single-child per definition.
If $p(v)$ is not the root: Assume that $p(v)$ is a single-child then $p(p(v))$ has only one child. This implies that the difference in height of the subtrees of $p(p(v))$ must be at least $2$ which conflicts with the AVL-criterium and therefore implies that $p(v)$ is not a single-child.
Using this and the fact that for every single-child there is a unique parent, we can conclude that $2\cdot numOnly \leq n$.


Does SAT always have short analytic proofs?

It is known that proofs of the unsatisfiability of pigeonhole problems must be at least length $2^{n^\epsilon}$ when the resolution proof system is used.  $\epsilon$ depends on the difference between the number of pigeons and the number of holes, but $\epsilon > 0$ always.


Generalized operators for programming languages

You might be interested in the citations provided in the following post on CSTheory.StackExchange: https://cstheory.stackexchange.com/q/19091/5038  They get at something roughly similar to what you are asking for.

See also the algebraic theory of parsing, e.g., https://cstheory.stackexchange.com/q/9000/5038  It seems like it too might be in the space that you are interested in.


Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0

Augment the tree to store, for each subtree, the minimum of the prefix sums of the sequence of elements in that subtree.  Then you can check the supergood condition in $O(\log n)$ time.  It's your exercise, so I'll let you work out the details.

Hint #1: every prefix can be decomposed into a union of $O(\log n)$ subtrees.

Hint #2: the minimum of the prefix-sum of elements $[x_1,\dots,x_k]$ is the smaller of (a) the minimum of the prefix-sum of elements $[x_1,\dots,x_j]$, (b), the sum of elements $[x_1,\dots,x_j]$ plus the minimum of prefix-sum of elements $[x_{j+1},\dots,x_k]$.  Now let $[x_1,\dots,x_j]$ denote the elements in the left subtree of a node, and $[x_{j+1},\dots,x_k]$ the element in the node and the elements in the right subtree, and this gives you a way to recompute the augmented values in a node given the augmented values in its two children.

In general, the typical strategy with augmentation is that you want to choose augmented values so that (1) you can update or recompute the augmented values in a node efficiently (typically, in $O(1)$ time), given the augmented values in its two children, and (2) you can answer a query efficiently (typically, in $O(\log n)$ time), using the augmented values.  Often we handle (2) by taking advantage of the fact that every interval of consecutive values can be decomposed into a disjoint union of $O(\log n)$ subtrees.


Develop the context free grammar to match this language (puzzle)

X --> Xa | Xb | Y

Y --> aYa | bYb | #Z

Z --> Za | Zb | empty

Y is the part that handles the string reversal. X and Z handle junk to the right and left of the reversal of x.


How to prove that minimal DFA is unique?

Suppose that we are given a regular language $L$ and a DFA ${\cal A} = (Q,q_0,F,\delta)$. Denote the equivalence classes of the Myhill–Nerode relation of $L$ by $S_1,\ldots,S_m$. For each state $q \in Q$, define $L_q = \{w \in \Sigma^* : \delta(q_0,w) = q\}$. From the definition of the Myhill–Nerode relation it follows that each $L_q$ is a subset of some $S_i$.

The Myhill–Nerode theorem shows that there is a DFA with $m$ states, so suppose that ${\cal A}$ has $m$ states. From our comment above it follows that each $L_q$ equals some $S_i$. Rename the states so that $S_i = L_i$ (so now $Q = \{1,\ldots,m\}$). We now read off all the other data of ${\cal A}$:

The starting state $q_0$ is the one whose language contains the empty word $\epsilon$, that is, it is determined by the condition $\epsilon \in S_{q_0}$.
A state $i$ is accepting if $S_i \subseteq L$, and rejecting if $S_i \subseteq \overline{L}$ (it follows from the definition of the Myhill–Nerode relation that these are the only two possibilities).
Let $w_i$ be an arbitrary word in $S_i$, and let $\sigma \in \Sigma$. Then $\delta(i,\sigma) = j$ if $w_i\sigma \in S_j$. Again, the definition of the Myhill–Nerode relation shows that the choice of $w_i$ doesn't matter.

After renaming the states of ${\cal A}$ in a canonical way, we read off ${\cal A}$ from the Myhill–Nerode relation of $L$. It follows that all minimial DFAs for $L$ are equivalent.


What is the height of avl tree with n nodes

AVL trees are self-balancing binary search trees (another example is red-black trees). By definition, a self-balancing binary tree maintains the property that its height is $\Theta(\log n)$, where $n$ is the number of leaves or vertices (the two properties corresponding to the two different definitions of $n$ are equivalent).

Usually it is costly to have a data-independent height, and so the height depends on the history of the data structure (it depends on the exact order in which values were inserted and deleted), but it is always $O(\log n)$. (Note that every binary tree has height $\Omega(\log n)$.)


Do dynamic/static languages associate types or classes to values or variables?

In those bullets, Harper is addressing common misconceptions about static versus dynamic typing. Each of those bullet points starts with a misconception, and then continues with Harper's clarification.

So, the first misconception is:

  Dynamic languages associate types with values, whereas static languages associate types to variables.

Harper disagrees, and instead says that dynamic languages associate classes to values. This comes from a type-theoretic perspective, where it is useful to reserve the notion of a "type" to a particular form of static classification of expressions. In the textbook, Harper defends this perspective by demonstrating that "dynamic types" and "static types" can coexist, and in this way, the two concepts are orthogonal. In particular, there is a special static type which Harper calls dyn, and values of type dyn are given a tag at runtime which identifies their class, i.e. their "dynamic type". (By the way, it's worth mentioning that this tagging mechanism is exactly how dynamic types are implemented in modern languages.) In dynamically typed languages, it is often the case that the static types do not carry very much information, for example all expressions might actually have the static type dyn.

The interest in "values versus variables" comes from the "dynamic versus static" perspective on types. If we associate "types" with values, then we can only determine their "type" at runtime. But if we associate types with variables, then we can determine the type of the variable statically. Harper is just trying to point out that there doesn't need to be an issue of "this versus that": dynamic types and static types do not lie on the same spectrum. Simply put, from the perspective of type theory, "dynamic types" are not types.

To sum up, if we take a type-theoretic perspective and make a distinction between types and classes, then we can make this statement: all languages associate types with both variables and values. In fact, we can make an even stronger statement, which is this: all languages associate types with expressions. Variables and values are just two different forms of expressions.


Advantage of Stack-Based Allocation for Local Variables

Consider the following program:

f1();
f2();

If local variables are allocated statically, there's a space in memory that's reserved for the local variables of f1, and a separate space for the local variables of f2. If f1 needs $n_1$ bytes of memory for its local variables and f2 needs $n_2$ bytes, the program above needs $n_1 + n_2$ bytes.

If local variables are allocated on a stack, the same stack space is first used for the local variables of f1, then reused for the local variables of f2. The program only needs $\max(f_1, f_2)$ bytes of memory.

With more functions in a program, the amount of static memory grows linerarly with the number of functions and the size of their local variables. The amount of stack memory only grows as fast as the depth of the call chain.

In addition, static allocation does not permit recursion or concurrency: if f1 is already active, you can't invoke it again since the second invocation would overwrite the local variables used by the first invocation. Stack allocation does.

Stack allocation has been standard practice since the very early days of computers.


Sum of Maximum of continuous blocks of length k

For an appropriate data structure $D$, which maintains the last $k$ elements, it is natural to consider the following solution:

Initialize $D$ with $A_1,\ldots,A_k$, and initialize the sum $S$ with $\max D$.
For $i=k+1,\ldots,n$:

Remove $A_{i-k}$ from $D$.
Add $A_i$ to $D$.
Add $\max D$ to $S$.

Return $S$.

The data structure has to support three kinds of operations:

Adding an element.
Removing an element.
Calculating the maximum.

I'll let you figure out what data structure is most suitable, and what is the resulting complexity.


Why is the Turing machine rather than the finite automaton the main model for computation if computers have finite memory?

First, I want to clear a misconception:

On the other hand the input can be external and could therefore potentially be infinite.

Usually unless specified otherwise for some purpose, we do not consider TM inputs to be infinite, only unbounded in length (similar to DFA input strings, as a normal DFA cannot accept or reject a string that never ends). This distinction might be hard to grasp, but it will be useful. If you're curious, you can read up on $\omega$-automata, a class of automatons specifically modeling problems with infinite-length inputs.
It is true that an individual computer is, strictly speaking, more akin to an extremely big DFA than a TM. However, by modeling algorithms as TMs, we are trying to make a more general statement about computability, one that transcends individual computers. The theory of computation seldom concerns itself with the need to establish that a particular student laptop, ancient server or supercomputer can perform a particular computation.
Rather, by modeling a problem as a TM and comparing it to a real computer, we're establishing that the computation is possible in the sense that while a given machine might not be able to actually finish it, the only obstacles are the impractical logistics of acquiring a machine with enough RAM/paper/tape/you-name-it and possibly waiting impractically long, too. Alternatively, we're establishing that a given computer or model (eg. a programming language) can be used to simulate a Turing Machine and therefore compute anything computable under the same logistic constraints. And since the inputs are finite, the amount of memory you need to scrounge up (for a working, terminating algorithm) is finite too.
So yes, the TM does conveniently ignore that a given computer has a bounded memory, but since it doesn't need to represent a "given" computer but any computer, this slip is easy to forgive and doesn't prevent the comparison from serving its purpose. If you need to make formal proofs about a single computational device with bounded memory where the finite amount of states is likely to present an interesting issue, a DFA-equivalent model might indeed be better.


What are the reasons to learn different algorithms / data structures serving the same purpose?

There's a textbook waiting to be written at some point, with the working title Data Structures, Algorithms, and Tradeoffs. Almost every algorithm or data structure which you're likely to learn at the undergraduate level has some feature which makes it better for some applications than others.

Let's take sorting as an example, since everyone is familiar with the standard sort algorithms.

First off, complexity isn't the only concern. In practice, constant factors matter, which is why (say) quick sort tends to be used more than heap sort even though quick sort has terrible worst-case complexity.

Secondly, there's always the chance that you find yourself in a situation where you're programming under strange constraints. I once had to do quantile extraction from a modest-sized (1000 or so) collection of samples as fast as possible, but it was on a small microcontroller which had very little spare read-write memory, so that ruled out most $O(n \log n)$ sort algorithms. Shell sort was the best tradeoff, since it was sub-quadratic and didn't require additional memory.

In other cases, ideas from an algorithm or data structure might be applicable to a special-purpose problem. Bubble sort seems to be always slower than insertion sort on real hardware, but the idea of performing a bubble pass is sometimes exactly what you need.

Consider, for example, some kind of 3D visualisation or video game on a modern video card, where you'd like to draw objects in order from closest-to-the-camera to furthest-from-the-camera for performance reasons, but if you don't get the order exact, the hardware will take care of it. If you're moving around the 3D environment, the relative order of objects won't change very much between frames, so performing one bubble pass every frame might be a reasonable tradeoff. (The Source engine by Valve does this for particle effects.)

There's persistence, concurrency, cache locality, scalability onto a cluster/cloud, and a host of other possible reasons why one data structure or algorithm may be more appropriate than another even given the same computational complexity for the operations that you care about.

Having said that, that doesn't mean that you should memorise a bunch of algorithms and data structures just in case. Most of the battle is realising that there is a tradeoff to be exploited in the first place, and knowing where to look if you think there might be something appropriate.


Imagine a red-black tree. Is there always a sequence of insertions and deletions that creates it?

The insert and delete operations in a red-black tree include the balancing needed to maintain the red-black properties.

The problem with non(left- or right-) leaning red black trees is that there are multiple ways to restore the red-blackness after the basic delete or insert.
It is not the insert or the delete that transforms the tree, but the rebalancing and rotation that happens afterwards to preserve/restore the red blackness of the tree.

The basic description of the red-black tree does not prescribe which of the possible routes to take.
It may not be possible to figure out how to exactly reconstruct a given red black tree, because the rebalancing need not be deterministic.

This has been 'solved' with left-leaning red black trees.
There is only one way the balancing is done. So any given leaning red black tree can be reconstructed using inserts and deletes, because the rebalancing/rotations are done in a specific deterministic way.

This does not mean that left-leaning RB-trees are better or more efficient, what they gain on one hand by using deterministic balancing rules, they lose on the other by more complex balancing code.

As per @Anton's comment:
There is an algorithm which uses the operation insert and delete to construct a valid red-black tree consisting only of black nodes. It uses $(h+2)⋅2^{h}−1$ insertions/deletions to create a tree of height $h$. First, we can create a perfectly balanced red-black tree in breadth-first manner using $2^{h+1}−1$ insertions, then using $h∗2^{h-1}$ insertions and the same amount of deletions repaint it into a completely black tree. The trick here is to move up $h$ times the lowest red layer up the tree until it reaches the root.

I think a complete balancing algorithm like Day-Stout-Warren would be more efficient though.


Finding all pairs of points with no point in between

If you can select $p_j$ in $O(n)$ time such that it's part of the middlemost group of elements with the same color, the following algorithm works. However I haven't found such a prerequisite.
After finding $p_j$ we can do an $O(n)$ scan to find $p_k$, the minimal element $>p_j$ with the opposite color. We can do a similar scan for $p_i$, the maximal element $<p_j$ with the opposite color. Finally we can partition our array in $O(n)$ time into three subarrays, left ($\{\leq p_i\})$, middle (rest, all with same color as $p_j$), and right ($\{\geq p_k\}$).
In an analysis similar to quicksort you can prove that if we recursively apply the above partitioning to the left and right subarrays we end up with a call tree that has height $\log k$ and at each level of the tree we do a combined $O(n)$ operations, thus a total runtime of $O(n \log k)$.
Afterwards (or during) you can simply iterate over each adjacent partition and output the opposite colored pairs (because each partition is uniformly colored).


What is the theoretical minimum number of "switches" requried to implement a Turing-complete CPU?

The Rule 110 cellular automaton is apparently Turing-complete.  If you're not counting the cost of memory, I imagine a circuit that applies the Rule 110 evolution rules could be implemented with very few switches.
See also https://softwareengineering.stackexchange.com/q/230538/34181.


Problem with implementing Brzozowski's algorithm

This is an excellent question!

The reverting step in Brzozowski's Algorithm does not introduce a new virtual starting state that leads to the old accepting states via $\varepsilon$-transitions. Instead it allows multiple starting states, which is no big problem, if you construct the product-automaton anyway right after the reversion.

Conceptually, it is the easiest to consider reverting and determinization as one single step. If your DEA is $M=(Q,\Sigma,\delta,q_0,F)$, then define as the reverted DEA  $ M^R=(Q^R,\Sigma,\delta^R,q_0^R,F^R)$ as follows:

$Q^R=\mathcal{P}(Q)$,
$q_0^R=F$,
$F^R=\{ P\subseteq Q \mid q_0\in P\}$,
$\delta^R(P,a):=\{ p\in Q \mid \delta(p,a)\in P\}$.

(You might want to ignore states that are not reachable.)

Brzozowski's Theorem states that $(M^R)^R$ is a minimal DEA accepting $L(M)$.

For further reading I suggest Elements of Automata Theory by Sakarovitch pages 116-117.


How to generate graphs with a Hamiltonian path?

The simplest solution is the one suggested by Yuval Filmus. That is, take a simple path on $n$ vertices, and finish the construction after you have added some number of edges. Clearly, it is easy to enforce the maximum degree condition as well.

Alternatively, you could generate graphs whose structure guarantees the existence of a Hamiltonian path. For example, as shown by Tutte, every 4-connected planar graph has a Hamiltonian path (see e.g., Wikipedia for the statement). Then, a high-performance tool for generating planar graphs is plantri. My feeling is that this is unnecessarily complicated for your use case, but it gives you a possible another approach you might be interested in later on.


Confused about 3rd rule of CFG pumping lemma

Remember that the PL is stated for any partition $s=uvxyz$, so it is not enough to show that for one specific partition pumping $v$ and $y$ will exclude the resulting string from $L$. While it is true that $xyz$ can consist only of 0′s, it could also be the case that $xyz$ is of the form $0^i1^j$ for some $i, j < p$, for instance. You must show that pumping excludes the resulting string from $L$ in this (and all possible other) cases as well.


Using Myhill-Nerode to prove a language is non-regular

The basic idea here is that you are trying to show that there are infinitely many indistinguishable sets in $L$.

Distinguishable Strings: Let $L$ be a language over an alphabet $\sum$. We say that two strings $x$ and $y$ are distinguishable with respect to $L$ if there is a string $z$ such that $xz \in L$ and $yz \notin L$, or vice versa.  That is, if we append $z$ to $x$ and $y$, the machine that processes $xz$ will be in a different state than if it were to process $xy$.

An indistinguishable set is then a collection of strings that are indistinguishable from one another but distinguishable from every other indistinguishable set.

Consider a FA $M$ that accepts $L$ = { even 0s } with alphabet $\sum = \{0,1\}$.  The minimal FA for this machine has two states.  There exists an indistinguishable set for every state, one set containing odd number of 0s and one set containing even number of 0s.

For your language, consider that you have { 1 00 substrings, 0 11 substrings } != { 2 00 substrings, 1 11 substrings } != { 2 00 substrings, 0 11 substrings } != { 3 00 substrings, 2 11 substrings } != { 3 00 substrings, 1 11 substrings } != ... != { $k$ 00 substrings, $l$ 11 substrings | $k > l$ }. Each of these sets is distinguishable from other. In other words, your minimal FA would require infinitely many states due to its need for counting.  Since an FA cannot have infinitely many states, the language cannot be regular.


Is realization of unit disk graphs hard?

One of the complications here is that there is no natural "decision variant" of this problem, since this isn't an optimization problem. (and the problem "given an UDG, is there a realization?" is trivial)
Since reductions between decision problems tend to be better studied, one option is to make it an optimisation problem in a chosen parameter. Even though you don't care about that value, you can use binary search on the optimisation problem to solve the realisation problem. Hence, the realisation problem is not much easier than the opt. problem, so showing the opt. problem is hard suffices.
The question then of course is what parameter to choose. Perhaps the problem "Given an UDG, find a realisation with minimum/maximum sum of edge lengths" would be suitable. It seems related to the problem that Aspnes et al. [1] show to be NP-hard.

[1]: ASPNES, James, et al. A theory of network localization. IEEE Transactions on Mobile Computing, 2006, 5.12: 1663-1678.


yes the theory has advanced significantly and somewhat due to both the chess analysis literature and general parallel programming techniques. here are some newer refs on (chess) alpha beta pruning over distributed clusters/ parallelism. also some of the early distributed computing chess literature predates a lot of basic parallel design patterns and can be conceptualized within that framework.

Parallel Alpha-Beta Algorithm on the GPU / Strnad, Guid (2011)
Parallel Alpha-Beta Search on Shared Memory Multiprocessors / Manohararajah (2001) 98pp!
Parallelizing a Simple Chess Program / Greskamp, 2003
Parallel Alpha-Beta Pruning of Game Decision Trees: A Chess Implementation / Steele 1999
Is it possible to run a Minimax search with Alpha-Beta Pruning in parallel with OpenMP? (stackoverflow)
The DTS high-performance parallel tree search algorithm (Hyatt 1994)

the basic idea behind DTS is that search trees are distributed among computational nodes based on move/ layout complexity. unused processors that "finish early" can do additional work beyond an initial allocation which can be distributed as evenly as possible initially but will turn out to be uneven. hence its basically a kind of "load balancing" and "producer/ consumer" queue, or also similar to job scheduling.

  This idle processor broadcasts (using shared memory) that it is idle, and is available to "help" any other processor finish searching its tree. The busy processors collect the "state of the tree" data, and store it in shared memory for the idle processor to examine. This idle processor analyzes this data, and decides which (if any) of the busy processors seems to have a tree that is complicated enough that it would be efficient to help with the search. If such a position is found, the idle processor informs the processor which owns that node of this and they "join" forces.


Is there an algorithm to find the minimal number of dimensions, given the distances between points?

This problem of minimal dimensionality has been studied intensively.

Here is a slightly-edited excerpt from Learning metrics via discriminant kernels and multidimensional scaling: Toward expected euclidean representation by Zhihua Zhang, Proceedings of the Twentieth International Conference on Machine Learning (ICML-2003), Washington DC, 2003.

  Definition 1 (Gower & Legendre, 1986) An $m × m$ matrix $[a_{ij} ]$ is Euclidean if $m$ points $P_i$ $(i = 1, . . . , m)$ can be embedded in an Euclidean space such that the Euclidean distance between $P_i$ and $P_j$ is $a_{ij}$.

  The following theorem provides the conditions for a matrix to be Euclidean.

  Theorem 1 (Gower & Legendre, 1986) The matrix $[a_{ij}]$ is Euclidean if and only if $H^{\text{tr}}BH$ is positive semi-definite, where $B$ is the matrix with elements ${-\frac12}{a_{ij}}^2$ and $H = (I − \mathcal 1_ms)$ is a centering matrix where $I$ is the identity matrix, $\mathcal 1_m$ is the $m \times 1$ vector $(1, 1, \cdots , 1)$ and $s$ is a $1\times m$ vector satisfying $s\mathcal 1_m = 1$.

Note that in theorem 1, if the condition is true for one choice of $s$ (say $s=e_i$, the vector whose entry is 1 at $i$-th position and whose entries are 0 otherwise), it is true for every valid choice of $s$. That fact is included in Metric and Euclidean properties of dissimilarity coefficients by Gower & Legendre, 1986.

Thanks to theorem 1, we know the minimal $m$ such that there are $\{y_1,y_2,\ldots,y_k\} \in \mathbb R^m$ with $d(i,j) = \Vert{y_i -y_j}\Vert$ is one less than the minimum order of non-Eucidean sub-square-matrix of $[d(i,j)]$. A simple algorithm to compute that minimum order is to iterate through all submatrix (that allow non-consecutive rows or columns) of $[d(i,j)]$, checking whether each submatrix is Euclidean.

For more related information, we can read that article and dig further.


Is it possible to convert a graph with one negative capacity to a graph with only positive capacities?

If you indeed have an edge $e$ with a negative capacity, and, I assume, it is a directed edge having no corresponding opposite edge, then you can reverse $e$, make its capacity positive, and, then, solve a regular max-flow problem with all capacities being non-negative. (Look at the concept of the residual network to understand what a negative capacity means.) Make sure you are not confusing edge capacities with costs.


Showing NP-hardness by reducing from a search problem

Basically, you pick any convenient decision problem known to be NP-complete and reduce from that problem to 3-COL-SEARCH.  In other words, informally, you prove that if it was possible to solve 3-COL-SEARCH in polytime, then it'd also be possible to solve that other problem in polytime.

For your particular example, a very convenient choice of decision problem is 3-COLORABLE.  It's known that 3-COLORABLE is NP-complete.  Now you just need to reduce 3-COLORABLE to 3-COL-SEARCH.  The reduction will be super-easy: take the hypothetical algorithm for 3-COL-SEARCH, run it on the graph, check whether it has output a valid 3-coloring or not, and if yes, output "Yes", otherwise output "No".  This will be a valid solution to the decision problem 3-COLORABLE, if the hypothetical algorithm correctly solves 3-COL-SEARCH.

Usually you can do the same thing with other NP-hard problems: often there is a natural decision problem associated with it, so you prove that the decision problem is NP-complete and then find a reduction from the decision problem to your search problem.

The other thing that's going on in your example is that, the way you defined 3-COL-SEARCH, it's a promise problem.  A promise problem is one where we have a promise that the input will be within some set -- and the algorithm is allowed to do anything it likes on other inputs.  Promise problems can be a bit counter-intuitive, or at least harder to think about, from a complexity-theory perspective, so if you're able to frame your problem so it's not a promise problem, I think that will usually be cleaner.


Why can't we derandomize the PCP theorem by iterating over all possible $\log n$ random strings?

We can! However, the PCP theorem does not say that we can solve the problem using $\log n$ bits of randomness. It says that we can verify a solution with $\log n$ bits.

Recall that a standard definition of NP is the class of languages for which there is a deterministic, polynomial-time verifier: For each $x$ in the language, there is a certificate $y$ so that the verifier accepts $\langle x,y \rangle$, and there is no such $y$ if $x$ is outside the language.

The PCP theorem says that we could also define NP as the class of languages for which there is a randomized, polynomial-time verifier that uses $\log n$ bits of randomness and reads only a constant number of bits of the certificate $y$.

Notice that if you derandomize the $\log n$ bits of randomness by enumerating them all and running this verifier on each one, you end up with a deterministic algorithm that will read the entire certificate $y$, which matches the standard definition of NP above.


Computer scientists are almost people
I think your explanation is pretty good. There is not a single formal way to specify an algorithm, except perhaps for pseudocode but as a software developer you are likely already familiar with that. Apart from that, algorithms that don't rely on intricate math are often best explained through text, as you've done.
Perhaps it could do with a bit more formal language however. First, note that what you're describing is more accurately called a data structure than an algorithm. Indeed, you give no method for creating this structure, but rather give a description of what it looks like.
Furthermore, you could (though I argue this is not mandatory) describe the structure more mathematically if you want, defining the various objects used. For example, say we have some set of words $W$, each of which is a string made up of some set of characters $C = \{a, b, c, \dots\}$. We'll also define $W[s]$ to mean the set of words in $W$ that begin with string $s$. In our case these are English words and characters, but that does not matter for the general case. Now, we can define our data structure recursively as follows (we'll call the structure a "slick" for now, in reference to your username).
A slick $S_s$ for some set of words $W[s]$ denoted $S_s(W[s])$ is defined as a list $[S_{s+a}(W[s+a]), S_{s+b}(W[s + b]), \dots]$. A slick on an entire corpus $W$ is defined as $S_\epsilon(W[\epsilon])$ where $\epsilon$ denotes the empty string.
However, if one of the subsets $W[s+c]$ for $c \in C$ is not of at least some constant size $k$, $S_s$ is instead defined as $S_s(W[s]) = W[s]$.
Note here that we implicitly define every "subslick" $S_s$. That is, the part of the slick where every word already starts with some string $s$. We define the whole slick as a special case of the subslick, namely one where every words starts with nothing, which is true for every word. Finally, we denote the stopping condition that if not every prefix is frequent enough, we stop making slicks.
We might be able to make it shorter and more formal by introducing more notation, but this would in my opinion come at the cost of readability. For example, "if one of the subslicks is not of some constant size $k$, then define it this other way" can be turned into $(\exists_c \, [|W[s+c]| < k]) \rightarrow S_s(W[s]) = W[s]$, but I argue that this does not help most readers.
Of course, this all depends on the audience. If you're submitting a paper in computer science with as its primary purpose the establishment of an algorithm or data structure, I would expect an informal explanation as well as a formal one, with absolutely no ambiguity. I would also expect not just a description of the data structure, but an explanation of its usefulness, and mathematical arguments for its properties.
This is almost exactly a trie
As for the data structure itself, except for the stopping condition this is exactly a trie, a structure that's been around since this paper in 1959. To look for other ideas for formalization, you might want to look for other explanations of the trie on the web.
The difference between the trie (also called prefix tree for obvious reasons) and the slick is that the trie just keeps making tries until there are no more words with a certain prefix. The slick stops significantly earlier, which I'm not sure is a great idea. Indeed, if we're encoding a moderately sized set of English words, we might not find $k$ words that start with an x, and then the data structure collapses entirely. Instead, I'd recommend not collapsing $S_s$ when $W[s+c]$ is small, but rather collapsing $S_s$ only if $W[s]$ is small.


I know Binary Search is more efficient than Ternary search, but my results are opposite. Help interpreting results?

As already noted in the comments, the experiment doesn't measure the amount of comparison operations, but instead it measures the depth of the recursion needed to find the given number. Here's code that should produce a proper experiment (replacing value $\rightarrow target$, lo $\rightarrow low$, $hi \rightarrow high$, $y \rightarrow comparisons$ for readability):

int $\texttt{binarySearch}$(array $a$, int $target$, int $low$, int $high$, int $comparisons$):

$\quad$__int__ middle = $\frac{low+high}{2}$;

$\quad$ if ($a$[middle] $= target$) then

$\quad\quad$__return__ comparisons+1;

$\quad$ else if ($target$ < a[middle]) then

$\quad\quad$ return $\texttt{binarySearch}(a, target, low, middle-1, comparisons+2)$

$\quad$ else

$\quad\quad$ return $\texttt{binarySearch}(a, target, middle+1, high, comparisons+2)$;

And similarly for $\texttt{ternarySearch}$:

int $\texttt{ternarySearch}($array $a$, int $target$, int $low$, int $high$, int $comparisons$):

$\quad$__if__ $a\left[low + \frac{high-low}{3}\right] = target$ return $comparisons+1$;

$\quad$__else if__ $a\left[low+ 2\frac{high-low}{3} \right] = target$ return $comparisons+2$;

$\quad$__else if__ $target < a\left[low + \frac{high-low}{3} \right]$ return

$\quad\quad\texttt{ternarySearch}(a, target, low, low + \frac{high-low}{3}-1, comparisons+3)$

$\quad$ else if $target < a\left[low + 2\frac{high-low}{3} \right]$ return
$\texttt{ternarySearch}(a, target,$

$\quad\quad low + \frac{high-low}{3}+1, low + 2\frac{high-low}{3}-1, comparisons+4)$

$\quad$ else return $\texttt{ternarySearch}(a, target, low + 2\frac{high-low}{3}, high, comparisons+4)$

Hope this helps. You might still have to catch the $low > high$ case. Lastly, you test your cases by populating your array with $a_i = \sqrt{i}$, and then measuring with $\texttt{xSearch}(rand(max = 8\sqrt{n}))$. Is there any reason you test specifically that way? Your results will be skewed because you will (especially with larger $n$) query your array for relatively low indices. It is better methodologically, unless your target application is representative of this test case, to populate your list with numbers $1 \ldots n$, and then to shuffle the list at random, to produce a random permutation. Then query for item $rand(max=n)$.


Let $P = \sum_{n,m \geq 0} T(n,m) x^n y^m$. We have
$$
\begin{align*}
P &= \sum_{n,m \geq 1} T(n,m) x^n y^m \\ &=
\sum_{n,m \geq 1} [T(n-1,m) + T(n,m-1) + T(n-1,m-1)+1] x^n y^m \\ &=
\sum_{n \geq 0, m \geq 1} T(n,m) x^{n+1} y^m + \sum_{n \geq 1, m \geq 0} T(n,m) x^n y^{m+1} + \sum_{n,m \geq 0} T(n,m) x^{n+1} y^{m+1} + \sum_{n,m \geq 1} x^n y^m \\ &= (x+y+xy)P + \frac{xy}{(1-x)(1-y)}.
\end{align*}
$$
We deduce that $(1-x-y-xy)P = xy/(1-x)(1-y)$, and so
$$
P = \frac{xy}{(1-x)(1-y)(1-x-y-xy)}.
$$

At this point we could invoke multivariate asymptotic analysis, but instead we'll connect $P$ to the Delannoy numbers $D(n,m)$, which follow a similar recurrence $D(n,m) = D(n-1,m) + D(n,m-1) + D(n-1,m-1)$, with base case $D(0,0) = 1$. These numbers have generating series $Q = 1/(1-x-y-xy)$. Our formula above shows that
$$
P = \frac{x}{1-x} \frac{y}{1-y} Q = \sum_{n,m \geq 1} x^n y^m Q,
$$
and so we obtain the formula
$$
T(n,m) = \sum_{n'<n,m'<m} D(n',m').
$$
This formula can also be derived directly in various ways.

Pemantle and Wilson shows that when $n,m \to \infty$ and $n/m,m/n$ are bounded,
$$
D(n,m) \sim \frac{nm}{\sqrt{2\pi}(n+m-\sqrt{n^2+m^2})^2\sqrt{n^2+m^2}} \left(\frac{m}{\sqrt{n^2+m^2}-n}\right)^m \left(\frac{n}{\sqrt{n^2+m^2}-m}\right)^n
$$
This should be compared to the similar frightening formula for the binomial coefficients,
$$
\binom{n+m}{m} \sim \sqrt{\frac{n+m}{2\pi nm}} \left(\frac{n+m}{n}\right)^n \left(\frac{n+m}{m}\right)^m.
$$
The asymptotic formula for $D(n,m)$ can probably be used to come up with an asymptotic formula for $T(n,m)$, or one can do the asymptotic analysis directly using the same methods, but I doubt that it would be very useful.


Measuring the difficulty of SAT instances

In general, this is a very relevant and interesting research question. "One way is to run existing solvers..." and what would this even tell us exactly? We could see empirically that an instance seems hard for a specific solver or a specific algorithm/heuristic, but what does it really tell about the hardness of the instance?

One way that has been pursued is the identification of various structural properties of instances that lead to efficient algorithms. These properties are indeed prefered to be "easily" identifiable. An example is the topology of the underlying constraint graph, measured using various graph width parameters. For example it is known that an instance is solvable in polynomial time if the treewidth of the underlying constraint graph is bounded by a constant.

Another approach has focused on the role of hidden structure of instances. One example is the backdoor set, meaning the set of variables such that when they are instantiated, the remaining problem simplifies to a tractable class. For example, Williams et al., 2003 [1] show that even when taking into account the cost of searching for backdoor variables, one can  still obtain an overall computational advantage by focusing on a backdoor set, provided the set is sufficiently small. Furthermore, Dilkina et al., 2007 [2] note that a solver called Satz-Rand is remarkably good at finding small strong backdoors on a range of experimental domains.

More recently, Ansotegui et al., 2008 [3] propose the use of the tree-like space complexity as a measure for DPLL-based solvers. They prove that also constant-bounded space implies the existence of a polynomial time decision algorithm with space being the degree of the polynomial (Theorem 6 in the paper). Moreover, they show the space is smaller than the size of cycle-cutsets. In fact, under certain assumptions, the space is also smaller than the size of backdoors.

They also formalize what I think you are after, that is:

  Find a measure $\psi$, and an algorithm that given a formula $\Gamma$ decides satisfiability in time $O(n^{\psi ( \Gamma )})$. The smaller the measure is, the better it characterizes the hardness of a formula.

[1] Williams, Ryan, Carla P. Gomes, and Bart Selman. "Backdoors to typical case complexity." International Joint Conference on Artificial Intelligence. Vol. 18, 2003.

[2] Dilkina, Bistra, Carla Gomes, and Ashish Sabharwal. "Tradeoffs in the Complexity of Backdoor Detection." Principles and Practice of Constraint Programming (CP 2007), pp. 256-270, 2007.

[3] Ansótegui, Carlos, Maria Luisa Bonet, Jordi Levy, and Felip Manya. "Measuring the Hardness of SAT Instances." In Proceedings of the 23rd National Conference on Artificial Intelligence (AAAI’08), pp. 222-228, 2008.


Does any parser ever parse non deterministic unambiguous context free grammar?

There are a number of general parsing algorithms (Earley, GLR, GLL, etc.) which can handle arbitrary context free grammars, even ambiguous grammars. (For ambiguous grammars, an entire parse forest is produced, usually as a spaghetti-like graph structure, because grammars can produce an infinite number of parses, or an exponential number if null cycles are removed.)

What these parsers cannot do is parse any grammar in time linear to the length of the input. It could take up to cubic time, although GLR parsers can parse unambiguous grammars in quadratic time even if the grammar is non-deterministic. (In practice, GLR parsers tend to be close to linear time for typical applications, because the grammars are "mostly" deterministic and unambiguous.)


We changed value on 2nd row, now we have new weight values and bias value, do we need to check the third row which is 1  0  1 with new weight and bias value or with old one which is (w1=0, w2=0, b=1) ?

The Perceptron processes one example at a time. The weights are immediately applied and subsequently updated (if the prediction is not correct).

  if we check 2nd row 3rd row and 4th row with new values and it satisfy 2nd 3rd and 4th row with new value, does this complete our 1st epoch?

Applying the learning rule to each example in the training set is called an
epoch.

Finishing an epoch doesn't mean that the perceptron converges to zero training error (it's typical to run multiple epochs).

For example, given:

(X1)--\
       \
        \ W1
         \
(X2)--W2--+-Y---O
         /
        / B
       /
 (1)--/

with:

$$Y = W_1 \cdot X_1 + W_2 \cdot X_2 + B$$

$$
O = \begin{cases}
0 & \text{if $Y \le 0$} \\
1 & \text{if $Y > 0$}
\end{cases}
$$

$$\delta = Target - O$$

$$\Delta W = \epsilon \cdot \delta \cdot O$$

If $\epsilon = 1$ and $W_1 = W_2 = B = 0$:

X1  X2  Target   W1    W2     B     Y  O  Delta   W1'   W2'     B'
 0   0     0      0     0     0     0  0      0    0     0      0
 0   1     1      0     0     0     0  0      1    0     1      1  <-error
 1   0     1      0     1     1     1  1      0    0     1      1
 1   1     1      0     1     1     2  1      0    0     1      1
--------- END OF EPOCH 1 / NOT CONVERGED ------------------------
 0   0     0      0     1     1     1  1     -1    0     1      0  <-error
 0   1     1      0     1     0     1  1      0    0     1      0
 1   0     1      0     1     0     0  0      1    1     1      1  <-error
 1   1     1      1     1     1     3  1      0    1     1      1
--------- END OF EPOCH 2 / NOT CONVERGED ------------------------
 ...
--------- END OF EPOCH 3 / NOT CONVERGED ------------------------
 ...                                                              NO ERROR
--------- END OF EPOCH 4 / CONVERGED ----------------------------


Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming.

The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other direction – given numbers in increasing order, output them in a prescribed order).

When using a stack, there is no need to use operation PR, since it can be simulated by executing IN and then EX. It is a classical result that a sequence is stack-sortable iff it contains no instance of the pattern 231, that is, there are no three numbers $\ldots,a,\ldots,b,\ldots,c$ such that $c<a<b$.

When using a queue, if we don't use PR then the string would come out unchanged. When PR is allowed (which seems to go against Knuth's original intention), we obtain that a sequence is queue-sortable iff it contains no instance of the pattern 321.

Since then, the same problem has been studied with various other data structures (mostly, it seems, in the 1970s). The recent papers Permutations sortable by two stacks in parallel and quarter plane walks and Permutations sortable by deques and by two stacks in parallel contain many references on this interesting combinatorial pursuit.


Assuming for simplicity that the edges don't touch the image boundary (you can always guarantee that by adding a pixel-wide "frame"), you can simply run flood fill from an arbitrary point on the image boundary.


Examples for derandomization via small sample spaces

There is a survey by Luby and Wigderson: Pairwise independence and derandomization.


Suppose that the fraction of foo() that is parallelizable is $\alpha$. Then the total execution time with $n$ cores is:

the non-parallelizable execution, done by only one core: $(1- \alpha)\times 20$
the parallelizable execution: $\alpha \times 20 \times \frac{1}{n}$

Then, for the first question, we have to consider that the number of cores is $3$, and the total time is $10$. The equation becomes:
$(1-\alpha)\times 20 + \alpha\times \frac{20}{3} = 10\Leftrightarrow \alpha = 0.75$.
For the second question, we suppose known the answer to the first question: $\alpha = 0.75$, and we suppose then that $n = \infty$. The total execution time becomes:
$0.25 \times 20 + 0.75\times \frac{20}{\infty} = 0.25 \times 20 = 5$.