Words that have the same right- and left-associative product I have started to study non deterministic automata using the book of Hopcroft and Ullman. I'm stuck in a problem that I found very interesting:

  Give a non deterministic finite automaton accepting all the strings that
  have the same value when evaluated left to right as right to left by
  multiplying according to the following table:

  $\qquad \displaystyle\begin{array}{c|ccc}
    \times & a & b & c \\
    \hline
    a & a & a & c \\
    b & c & a & b \\
    c & b & c &a
   \end{array}$

So if we have the string $abc$,
the product from left to right is $(a \times b) \times c=a \times c=c$ and
the product from right to left is $a \times (b \times c)=a \times b=a$

So $abc$ should not be acceptable for the automata. To me its obvious that any string $aa^*$ or $bb^*$ or $cc^*$ is an aceptable string (their right and left evaluation work on the same partial strings). It is easy to give an NFA that describes the left to right evaluation but the problem is that if the machine try to compute the right to left evaluation I think it needs to know the length of the string (so infinite memory is necessary).

So how can a non deterministic automata evaluate from right to left in order to compare with the left to right evaluation?

$(\ast)$ If $L$ is a regular language, then $L^R$, the language consisting of the reverse of all words in $L$, is also regular. Take this as an exercise.

How does this help us solve the problem? Let $L_a,L_b,L_c$ be the languages consisting of all strings that evaluate to $a,b,c$ when evaluating from left to right. The language you're interested in is
$$ (L_a \cap L_a^R) \cup (L_b \cap L_b^R) \cup (L_c \cap L_c^R). $$
This shows that if you know how to prove $(\ast)$, then you can construct an NFA for the language in question.

In fact, if you use the idea of the proof of $(\ast)$, then you can probably just go ahead and construct the automaton. So let's consider this. In particular, let's try to construct an NFA for $L_a^R$, the language of all strings that evaluate to $a$ when evaluated from right to left.

The idea is this. Suppose that the first letter you see is $b$. Then the rest of the string must evaluate to $b$ (since $bx = a$ implies $x = b$). Similar reasoning applies when the first letter is $c$. When the first letter is $a$, however, the rest can evaluate to either $a$ or $b$, or be null. With an NFA, we can guess (and later verify our guess).

This hint should give you enough to think about, and hopefully solve the problem.


Representing "but not" in formal grammar I just came across the following grammar definition:

  CommentChar ::

        SourceCharacter but not LineTerminator

But for discussion, I'll present this similar construct:

  Digit ::

         '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

  Zero ::

         '0'

  NonZeroDigit ::

         Digit but not Zero

Is this "but not" construct common in formal grammar specifications?  If there a name for it?

I realize that NonZeroDigit could be defined by "manually" expanding the nonterminals and finding the  difference -- here that process is as straightforward as it gets.  But for more complicated "but not" constructs, I imagine that would be painful and error-prone.

Or, in grammars that support it, is this just considered just a sequence of (a) a negative lookahead (for Zero) combined with (b) the nonterminal for Digit.

For context-free grammars (I guess your question concerns this type of formal grammars), it would be not only painful, but also impossible in general.

Suppose we have an algorithm that provides such "expansion" and yields a new grammar without $\text{but not }$occurrences. Then we can take two arbitrary context-free languages $L, L'$ with start nonterminals $A, A'$ respectively, write down a rule $B \longrightarrow A \text{ but not } A'$, run the algorithm on it, and get a context-free grammar for $L\backslash L'$. It contradicts a well-known fact that difference of two context-free languages can be not context-free.


What is the difference between halting, accepting, and deciding in the context of Turing machines? Does accepting mean that the TM will read and recognize a char from the cell it's currently reading from? And is it the case that a TM halts iff the input is decidable?

Accepting and rejecting the state a Turing machine may eventually enter, is based on the string read from the tape, not just the symbol from one cell. Of course, the decision about entering an accepting or rejecting tape is ultimately made on the basis of one symbol.

A Turing machine can either eventually enter an accepting state, enter a rejecting state, or loop forever. If it enters either an accepting or rejecting state, then it halts.

A Turing machine is said to be total if it halts on all inputs.

The language accepted by a Turing machine is the set of all words that that, when provided as input to the Turing machine, cause the Turing machine to enter an accepting state.

A language is said to be decidable if and only if there exists a total Turing machine that will accept the language.


How does an Operating System without kernel mode work? Andrew S. Tanenbaum, in his book Modern Operating Systems (3rd Edition), states that the distinction between operating system software and normal (user mode) software can sometimes be blurred in embedded systems (which may not have a kernel mode).

  Can someone please describe more what an OS without a kernel mode looks
  like and how it works?

Thank you.

It's more like an operating system without a user mode.  In many embedded systems there is only one (or a small number) of "applications" and so the application is just built right into the lowest-level of the system.

Desktop/server operating systems provide many services, some of them unnecessary for embedded systems.

At the lowest level you typically need some wrapper routines for accessing various physical devices (serial buses, sensors, actuators) and interrupt service routines for devices that need asynchronous attention.  In a desktop/server OS the device registers or memory mapped locations for accessing the device registers would be protected/hidden from the applications, but in an embedded system you can trust the application writer.

As you go up the stack some services may be necessary for a particular embedded system, but those can be provided by library routines.  For example, you might need a file system, but you just implement this as a library that provides open, read, write, close, make_directory and such routines to the rest of the system.

Your embedded system may (or may not) need to be able to load and execute programs not built into the kernel.  Again, you can provide the ability to load the executable part of a file off the disk into memory and then jump to some start location.

Your embedded system may (or may not) need dynamic memory allocation.  This just means that all the memory not otherwise in use is managed by a library routine (usually called malloc and free or something similar).

Your embedded system may (or may not) need multiple threads.  Many embedded systems manage the threads cooperatively.  That means that there are library routines to allocate and initialize memory for a new thread, and then the library selects one thread to run for awhile and when the thread calls some function (often called yield) this jumps back to the thread management library, which then selects a different thread to run and performs any necessary book-keeping.  This can be taken a step further by making the thread library preemptive (an interrupt handling routine calls the library's yield routine on a timer interrupt if the current thread doesn't call it itself.)

Since you know the apps that are running (and trust their authors) you generally don't bother with the hardware expense of different protected address spaces.  Similarly you generally don't bother with virtualizing the memory (using the disk or SSD to make the memory look larger than it really is.)


Complexity classes that are closed under subtraction Are NP or P closed under subtraction? Im having a hard time deciding whether they are or aren't.
Question was edited

Original question:
Im having some hard time figuring out what languages are closed under subtraction.
Say you have 2 languages A, B ∈ NP. Is A\B ∈ NP? what about P?

Commenters:
My original question was extremely not accurate so i rephrased :)

Thanks!

$A \setminus B$ is defined as $\{x | x \in A ~ and ~ not ~ x \in B \}$. If you know the complexity of checking $x \in A$ and $x \in B$, what does that tell you about the complexitty of $x \in A \setminus B$? Can you see the algorithm for checking it?


Sorting numbers in $O(1)$ Here is an experiment I came up with (I don't have sufficient material to make it):

Say that, you have a list of $n$ numbers $L = \{l_1, l_2, ..., l_n\}$.
And you have bars representing those numbers like so:

Say that, width of every bar is $w$.
Imagine a line, thatis made up of $n$ line segments, each of them are $w$ long, and they are enough to cover all the bars.
When any of the lines touches a bar, it sends a signal, declaring its ID.
ID of each bar correspods to its position.

If we are able to build a system as described above, we can release the whole line and store the signals respectively in an array, therefore have the real poisitons of each number we want to sort.

Therotically, when does it take more time and energy to sort $n$ numbers with this method than sorting $n$ numbers using a supercomputer?

This is similar to what is known as counting sort. Whether your method is more efficient than other methods depends on the model of computation, which you haven't specified. For example, what if the dynamic range of the numbers is really large, say they are integers from $0$ to $2^{100}$? You could use some adaptive approach ("scanning" from top to bottom, stopping each time a number is reached), but it really depends on what your computer is allowed to do, and in practice you probably won't be able to pull it off. Counting sort is a conventional algorithm which uses a very similar idea in situations in which the dynamic range is small, in which case the algorithm is highly effective.


Counting number of sums from contiguous subarrays of an array We are given an array $a[1 \ldots n]$ with all $a[i]>0$.

Now we need to find how many distinct sums can be formed from its subarrays (where a subarray is a contiguous range of the array, i.e., $a[j\ldots k]$ for some $j,k$, the sum is the sum of all of the elements of the subarray). For example, if $a=[1,2,1]$, then the answer is 4: we can form $ 1,2,3,4$.

I know how to count the number of distinct sums in $O(n^2)$ time.

Furthermore, I have come to realise this is similar to the classical problem where we need to find the number of distinct substrings of a string. I was thinking of the possibility of constructing a suffix array and solving it in a similar fashion (in $O(n)$ time). But I have not been able to figure out how to modify that to work here. For example, if we use suffix array for $a=[1,2,1]$ we will get 5 cases instead of the four acceptable ones. Is this possible to do this using suffix arrays or am I thinking in the wrong direction?

Also there is one more direction I have been thinking in. Divide and conquer. Like if I divide the array into two parts every time until it is reduced to a single element. A single element can have one sum. Now if we combine two single elements, It can be done in two ways: if both single ranges have same element then we get 2 different sums, or if both have different elements we get 3 different sums. But I am not being able to generalize this for merging arrays of length greater than 1. Is it possible to merge two m size arrays and get the answer in $O(m)$?

You almost surely can't get better than $O(n^2)$ in the worst case since the number of different sums can be in $\Theta(n^2)$.

Consider e.g. the array $[1,2,4,8,\dotsc, 2^n]$. Here each of the $\frac{n(n+1)}2$ contiguous subarrays has a different sum.

The "almost surely" is due to the fact that the problem does not require the values of the sums as output. However, I don't think duplicates can be avoided without determining at least most of the values.


Why theorem proving is hard? Every time I ask why most people think that P ≠ NP, I get a response like "because theorem proving is harder than proof checking".

From this, I understand that proving theorems is hard. But why is this? In fact, it is known that a theorem, in mathematics, is a statement that has been proved on the basis of previously established statements. So a not proven theorem would not be called a theorem, would it? I mean, a theorem is easy to prove because it is defined to be so and people call it theorem because they know how to prove it, no? If we were talking about conjectures, I would have not asked this question.

When I was looking, I found this paper: Cook, Stephen (1971). "The complexity of theorem proving procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158. But this seems to confuse me furthermore.

I am sure I am missing something (maybe some obvious one). Would you please clarify this?

So a not proven theorem would not be called a theorem

No, it's usually called a proposition, or a conjecture.

  I mean, a theorem is easy to prove because it is defined to be so and people call it theorem because they know how to prove it, no?

Just because you know a proof exists doesn't mean that you can efficiently find that proof.

  From this, I understand that proving theorems is hard

The thing is, there is no mathematical evidence that it's hard, other than the repeated failures of people to prove that it's easy. But of course, the failures of people to prove that it's hard acts as evidence that it's easy.

When people say that proving theorems is harder than checking them, they are speaking from intuition. From a complexity theory standpoint, there is no evidence that proving theorems is harder than verifying them. If there were, we would be able to resolve $P$ vs $NP$. Any guesses one way to the other are just that, guesses.

There is, however, an analogy, from computability theory.

When people are talking about proving versus checking for $P$ vs $NP$, they usually mean things like SAT or Constructive Propositional Logic, or other such systems with no quantifiers, or restricted quantifiers. But if we extend proofs to include predicate logic, with $\forall$ and $\exists$, then we have a firm result: checking proofs of these is decidable, and generating such proofs is undecidable. This is a basic consequence of the undecidability of the halting problem.


What are the differences between NP-Complete and NP-Hard? What are the differences between NP, NP-Complete and NP-Hard?

I am aware of many resources all over the web. I'd like to read your explanations, and the reason is they might be different from what's out there, or there is something that I'm not aware of.

A problem $\Pi$ is $\textrm{NP}$-hard if every problem in $\Pi' \in \textrm{NP}$ can be reduced to $\Pi$ via a Karp reduction $\le_p$, i.e., if $\Pi' \le_p \Pi$.

A problem $\Pi$ is $\textrm{NP}$-complete if it is $\textrm{NP}$-hard and belongs to $NP$.

Intuitively, a $\textrm{NP}$-complete problem is as hard as the hardest problem in $\textrm{NP}$ while a $\textrm{NP}$-hard problem might be even harder.

Finding a polynomial-time algorithm $A$ for any $\textrm{NP}$-hard problem $\Pi$ (therefore also for any $\textrm{NP}$-complete problem) would immediately yield a polynomial-time algorithm for all problems in $\textrm{NP}$: reduce (in polynomial-time) an instance $x$ your problem $\Pi' \in \textrm{NP}$ of choice to an instance $y$ of $\Pi$ and then solve $y$ it using $A$.


Can a computer game can run on a boot mode without the aid of os? I meant that that the game programmer can just add its own code to the game to manipulate its own low level function as the operating system does provide in a common executables,and load it into the boot mode using its own bootstrap

Yes, it is possible to boot computer to the specially designed program, which will be some game. But this will be harder, because there will be no drivers for advanced hardware, only elementary BIOS functions, basic video memory access. For example, if author want to add sound to the game, he can used PC speaker, or write own driver for ... for which card? Sound blaster, or RTL? What if user has another card? Same problem for video: game may know about some Radeon and will not work on older or newer AMD card or on Nvidia or Intel.

So, writing a bootable computer game is the same as writing both the game and the Operating System with drivers (or stealing its codes like in PS4's Orbis OS with FreeBSD sources or SteamOS with linux sources).


Recognizing Regular Languages in Layman terms I understand that regular languages are languages which can be computed by Finite Automata however i am having some trouble understanding how one can identify a regular from non-regular.

I know that 0*1* is regular because the machine just needs to make sure the 0s and 1s are in order

I know that 0^n 1^nis non regular because the machine needs to keep count to make sure there is an equal number of 0s and 1s

But why is (01)^n considered regular? Doesn't the machine have to keep track to make sure that there are n amount of 01?

How about {0^m 1^n | n>m}?

What is the general rule for quickly figuring out if something is regular or not in layman terms?

the way to test if something is non regular is to use the pumping lemma for regular languages. It can prove that a language is non regular, but it will not necessarily prove that a language is regular. To prove that some language is regular, you can create a finite automata for that language.


Post Correspondence Problem - algorithm that solves the problem for a word with maximum K length The question is as follows:

Let's observe the following Post correspondence problem.
Input: Two finite lists of words $A$ and $B$ and a natural number $k$.
Question: Is there any words correspondence with a length of $k$ at the maximum?
Describe an algorithm to solve the problem and analyze its runtime.

I really don't understand how to solve this problem. From my understanding, the Post correspondence problem is undecidable so how come we can describe an algorithm to solve this question?

PCP is undecidable essentially because, if there is a match, it could be arbitrarily long. But, here, the question specifically excludes any string longer than $k$ characters. There are only about $2^{k+1}$ possible strings of length at most $k$ over alphabet $\{a,b\}$. Does that help you find an algorithm?


Hardness of a problem related to set cover Suppose $C_1, \ldots, C_m$ are subsets of $\{1, \ldots, n\}$. The goal is to find the smallest subcollection of $C_1, ..., C_m$ such that each element of $\{1, \ldots, n\}$ appears at least $k$ times in this subcollection.

If $k=1$, this is set cover. I would be interested to learn how to prove NP-hardness for $k=2$ and $k=3$.

Hine: Given an instance of set cover, add $k-1$ copies of the set $\{1,\ldots,n\}$.


Longest repeated substring I am trying to solve a problem- Longest repeated substring in a string. Firstly, I built a suffix tree that takes O(n) time and then I traversed the suffix tree to find the deepest internal node. I am not sure whether traversing in a suffix tree would be O(n) or not?

These are the properties of a suffix tree-

A suffix tree will contain n leaves which are numbered from 1 to n.
Each internal node (except root) should have at least 2 children.

If each internal node can have more than 2 children,How can I say that number of nodes in a suffix tree is O(n)? So, How will the complexity be O(n)?

Here is the code that I have written for traversal. I am aware that this platform is language independent so I have added the relevant comments along with my code.

struct StNode
{
    string str;
    StNode* child[256];
};
void lrs(StNode* t,string s,string &res)
{
    if(leafNode(t)){    //leafNode means no child
        string str=t->str;
        s.erase(s.length()-str.length());   //erasing the leafNode's string
        int k=s.length();
        if(k>res.length())   res=s;
        return;
    }
    for(int i=0;i<256;i++){     //traversing through all childs
        if(t->child[i]!=NULL){
            string str=t->child[i]->str;
            lrs(t->child[i],s+str,res);
        }
    }
}

Yes, the number of nodes in the suffix tree is $O(n)$.

Here's how you could infer that.  The suffix tree can be constructed in $O(n)$ time.  There's no way to construct a tree with strictly more nodes than that, since it takes at least $\Omega(1)$ time per node you construct; so from the fact that the running time of the suffix tree algorithm is $O(n)$, you can conclude that its output must have size $O(n)$, i.e., the suffix tree must have $O(n)$ nodes.

Here's another way you could have inferred that.  There are $n$ leaves.  Also, each internal node has at least two children.  In such a tree, the number of internal nodes is at most the number of leaves, so in this case, there are at most $n$ internal nodes and $n$ leaves.  It follows that the number of nodes in the tree is at most $2n = O(n)$.

This information is actually found in the Wikipedia page on suffix trees, which explains that any suffix tree has at most $2n$ nodes.  In the future, before asking a question here, please check standard resources, such as Wikipedia and a textbook.

It follows that the tree can be traversed in $O(n)$ time.


Searching for points near given point in a multidimensional space I want to search many times, not identical elements but similar, for something a similar image or fingerprint without having to search the whole space.
When I have a 1D case I sort it first.
For 2D I can make boxes big enough to be not wasted on boxes containing no elements, these boxes have subboxes and these have elements.

There is a problem: because when the width is 100, then if I'm looking for a 401 I can find a 490 and I can't find a close element 399.
You would have to look in the boxes around, in 9 instead of in one. It's still possible, but for 3D it will be 27, generally 3^n, what if we have 512D?

If you don't want the exact nearest neighbour but would be satisfied with finding points that are not too far off, then you should take a look at Approximate nearest neighbour search.

Wikipedia suggests the following approaches:

Locality-sensitive hashing
Best bin first
Balanced box-decomposition tree

Depending on the distribution of your data, not all dimensions may be equally relevant (maybe all points are bunched together along some line or hyperplane) and you could also use dimensionality reduction techniques, the main one being PCA (or maybe autoencoders nowadays).

Of course you can combine both, and that is also what I would recommend you to do in most cases.

If you want the exact nearest neighbour, unfortunately research suggests that this is very hard in high dimensions (see curse of dimensionality), and with a 512 dimensional space "clever" methods can very well end up being worse in practice than simply searching through all points.


Proving $ \{ \langle D_1, ... ,D_K \rangle : \text{ where } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $ is NP-Hard The question (Prove L is NP-hard) was about proving that the following language is NP-hard:
$$ L = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N}\text{, the } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) = \emptyset \} $$

That got me thinking about the related problem:

$$ L' = \{ \langle D_1, D_2, ... ,D_K \rangle : k \in {N}\text{, the } D_i \text{ are DFAs and } {\bigcap}_{i=1}^k L(D_i) \neq \emptyset \} $$

I would imagine that $L'$ is also NP-hard, but I couldn't think of any reductions.. am I missing something obvious?

The language $L$ is in fact PSPACE-complete, so in particular it's both NP-hard and coNP-hard. Here is a quick sketch of the proof.

$L$ is in PSPACE. This part is easy. The intersection of the DFAs can be realized as a DFA with $n^n$ many states, hence if the intersection is non-empty, there must be a word of length $n^n$ accepted by all DFAs. Counting up to $n^n$ requires $O(n\log n)$ space, so there is an NPSPACE machine for $L$: the machine guesses a word of length at most $n^n$ and verifies (in parallel) that the word is accepted by all DFAs. Savitch's theorem shows that NPSPACE=PSPACE, so we're done.

$L$ is PSPACE-hard. The reduction is from TQBF, which is the problem, given a formula $\varphi(x_1,\ldots,x_n)$, to decide the truth value of $\psi = \exists x_1 \forall x_2 \exists x_3 \cdots \varphi(x_1,\ldots,x_n)$. Consider some iterative algorithm for evaluating $\psi$: it goes over all possible assignments of $x_1,\ldots,x_n$, and computes intermediate values of $Q x_i \bar{Q} x_{i+1} \cdots \varphi(y_1,\ldots,y_{i-1},x_i,\ldots,x_n)$ (where $Q \in \{\forall,\exists\}$). We can write this computation as one long string $w$. The computation can be verified locally: for example, if all we wanted is to verify that $w$ is a $\#$-separated list of all numbers from $0$ to $2^n-1$ in binary (i.e. for $n=2$, $\#00\#01\#10\#11$), then we can write several regular expressions which verify this:

$w$ is a $\#$-separated list: $(\#(0+1)^n)^*$
$w$ starts with $0^n$: $\#0^n\Sigma^*$
$w$ ends with $1^n$: $\Sigma^*\#1^n$
The LSBs in $w$ behaves correctly: $(\#(0+1)^{n-1}0\#(0+1)^{n-1}1)^*$
The MSBs in $w$ behaves correctly: $(\sum_{i=0}^{n-2} \#0(0+1)^i0(0+1)^{n-2-i})^*\#01^{n-1}\#10^{n-1}(\#1(0+1)^{n-1})^*$
Similar (but more complicated) regular expression ensure that the other bits behave correctly.

All these expressions (and the corresponding DFAs!) are of length polynomial in $n$, and there is a polynomial number of them, so using DFA intersection you can express the fact that $w$ is of the given form.

The actual $w$ is more complicated, but the idea is the same. At the very end of $w$ will appear the actual value of $\psi$, and we can add a regular expression which verifies that $\psi$ is true. This reduces TQBF to DFA intersection.

The classical reference is Kozen's Lower bounds for natural proof systems, or you can check my account (Section 4) which proves a different result but contains everything that you need to prove that $L$ is PSPACE-hard.


Finding top k which are the most different from each other Assume I have a set of items $A$ and each item $a \in A$ has a score $s(a)$.
Also, each two items $a_1,a_2 \in A$ have variety score $var(a_1,a_2)$ which tells how different they are.

I want to optimize over these two values (say with equal weights) to find $k$ items that have both high scores and large variety (to avoid almost-repetitive items). That is, to solve the following optimization problem:

$$\arg\max_{a_1,...,a_k\in A}{(\sum_{i=1}^{k} s(a_i) + \sum_{1 \le i<j\le k} var(a_i, a_j)})$$

Is this problem NP-hard?
If not, can you provide a polynomial time algorithm that solves it?
If yes, can you provide a polynomial time approximation algorithm that approximately solves it?

Your problem is NP-hard, when $k$ is part of the input.  Let $G=(V,E)$ be an undirected graph.  If we set all the scores to zero and $\text{var}(u,v)$ to 1 if $(u,v) \in E$ and 0 otherwise, your problem is equivalent to asking whether $G$ contains a clique of size $k$.  This is a NP-hard problem.

If we set all the scores to zero and allow the variety values to be arbitrary, your problem is equivalent to the maximum edge-weighted clique problem (MEWCP), which has been studied in the literature.  For instance, you can use quadratic programming or ILP to look for solutions; these can take exponential time in the worst case, but might be useful in practice if the number of items is not too large.

Obviously, when we take into account that scores can be non-zero, the problem only gets harder.  You might be able to adapt methods for MEWCP to your problem, or express your problem directly as an ILP or QP.


Differentiating between BubbleSort and InsertionSort This is a homework I'm doing, but I couldn't find an answer, hopefully you guys can shine some light on this.

The problem is this:
You have two unknown sorting algorithms, one is Bubble Sort, the other Insertion Sort.
Identify which is which given that you can only differentiate them via differences in asymptotic time for different data sets. (Meaning no run time cross comparison between the two sorts, as our professor may add constant time costs making Insertion Sort slower).

Edit: To clarify, we can specify any array of length n, with a particular sequence if you wish, to see the time it took to sort.
However, you may not compare times between the two sorts. E.g. This sort is faster, therefore this is Insertion Sort.

My findings:

            Insertion Sort | Bubble Sort
Best case:            O(n) | O(n)
Worst case:         O(n^2) | O(n^2)
Average case:       O(n^2) | O(n^2)
Stable:                Yes | Yes
In-place:              Yes | Yes
Nearly Sorted:        O(n) | O(n)
Reversed:           O(n^2) | O(n^2)
Few Unique: closer to O(n) | closer to O(n^2) // not sure

Given how similar the two sorts are, it's really hard to distinct them...

Unfortunately, your problem statement is contradictory, so the problem cannot be solved in its current form.  Your question states that we can obtain the running time for finite values of $n$.  However, it also states that we only learn the asymptotic running time.  This is self-contradictory, because it is not possible to infer the asymptotic running time based on any finite number of measurements.

If I had to speculate, I'd guess that maybe what the instructor actually wants you to do is find an infinite sequence of inputs $a_1,a_2,a_3,\dots$ such that: (1) $a_i$ is an array of length $i$; (2) the asymptotic running time of Insertion Sort on these inputs differs by more than a constant factor from the asymptotic running time of Bubble Sort on these inputs.  If that's correct, your next step should be to investigate various ways you might construct such a sequence.  I emphasize that this is only speculation, and not something that can be definitively derived from the problem statement as provided.


Why proving that two languages used to merge into a regular language are not necessarily regular isn't possible with closure properties? Let $L$ be a regular language over alphabet $\Sigma$. $L$ is the result of merging $2$ languages letter by letter that is for $a_1a_2...a_n\in L_1, b_1b_2...b_n\in L_2, L=a_1b_1a_2b_2...a_nb_n$. $\epsilon \in L \iff\epsilon \in L_1,L_2$. Does this mean that $L_1$ is necessarily regular?

At first I tried to prove that this is true using closure properties of regular languages before finding out that the claim is not true (e.g. $L_1=\{a^ib^i|i\ge 0\}, L_2=\{ab\}$).

I'd like to understand though what's wrong with my proof:

1) Define homomorphism $h:\Sigma\to \Sigma^*\cup \Sigma'^*$ as follows: $h(\sigma)=h(\sigma')=\sigma$ for $\sigma,\sigma'\in \Sigma.$

2) Let $X=h^{-1}(L)\cap(\Sigma\Sigma^*)$

3) Define another homomorphism: $f_1:\Sigma^*\cup \Sigma'^*\to \Sigma$ like this:
$$
f_1(\sigma)=\sigma\\f_1(\sigma')=\epsilon
$$
4) Define another homomorphism: $f_2:\Sigma^*\cup \Sigma'^*\to \Sigma$ like this:
$$
f_2(\sigma')=\sigma'\\f_2(\sigma)=\epsilon
$$
Then $L_1=f_1(X), L_2=f_2(X)$. Now if either $L_1$ or $L_2$ is not regular than it's contradiction because by closure properties they should've been regular. Where is my mistake?

EDIT: following one of the comments, the problem with the attempt to use closure properties is that apply the homomorphisms $f_1,f_2$ on $X$ we may get a different language from the original one.

Your construction outputs the language
$$ \{ w \in L_1 : \exists z \in L_2 \text{ s.t. } |z|=|w| \}. $$
In words, it outputs those words in $L_1$ whose length matches the length of some word in $L_2$. In general, this could be much smaller than $L_1$.

In particular, if $L_2$ is a finite language, then the result of merging $L_1$ and $L_2$ is finite, and so regular, for every language $L_1$.


What this subnetting restriction means I was reading Data Communication book by Forouzan in which there is a one restriction put on CIDR subnetting by Internet authorities:

  First IP address in the block should be evenly divisible by the number of addresses. For example, below, the first address, when converted to a decimal number, is 3440387360, which when divided by 16 (block size) results in 215024210.

Since this did not clear the practical significance behind this restriction I went on exploring and came across the video where it is explained as follows:

  Whenever we divide any number by $k^{th}$ power of 2 (another restriction being that the block size should be $2^k$), the reminder is least significant k bits. So evenly divisible by $2^k$ means that least significant $k$ bits should all be 0. This way the first address of the allocated address block can be used as a block ID since it has all 0s in the host ID part.

Now that seems more logical despite the fact that I dont understand how

evenly divisible by the number of addresses $2^k$

translates to

least significant $k$ bits should all be 0

Can't it be just that the decimal equivalent of least significant $k$ bits should be divisible by 2. I mean if least significant 4 bits (for a block of $2^4$ addresses) is $(1010)_2$, then it translates to $(10)_{10}$ which is divisible by 2.

So in short why is evenly divisible translates to all 0 LSBs?

Since each place in a binary number is a power of two, the binary expansion of $2^k$ for any $k$ will be a 1 followed by $k$ zeroes.  Examples:

$$1 = 2^0 = 1$$
$$16 = 2^4 = 1\underbrace{0000}_{4\ zeroes}$$
$$512 = 2^9 = 1\underbrace{000000000}_{9\ zeroes}$$

Multiplying a number that ends in zeroes by another number (integer) produces at least that many trailing zeroes.  So any number divisible by a number ending in $k$ zeroes has to end in at least $k$ zeroes.


Meaning of type inference rule for abstraction in lambda-calculus Below is a snippet about simply typed lambda-calculus from CS152: Programming Languages Lecture 9 | Simply Typed Lambda Calculus, on printed‑page 15, indexed 23.

$$
\frac {\Gamma, x: \tau_1 \vdash e: \tau_2}{\Gamma \vdash \lambda x. e: \tau_1 \rightarrow \tau_2}
$$

I read it as: if from a context $\Gamma$ containing $x$ of type $\tau_1$, follows that an expression $e$ is of type $\tau_2$, then from context $\Gamma$, follows that $\lambda x. e$ is of type $\tau_1 \rightarrow \tau_2$.

How does that differs from this:

$$
\frac {\Gamma \vdash x: \tau_1 \land \Gamma \vdash e: \tau_2}{\Gamma \vdash \lambda x. e : \tau_1 \rightarrow \tau_2}
$$

I understand $x$ is expected to typically appears in $e$ (but need not to), however still not see why the second expression (looking more intuitive to me) is not used instead, and so I suspect I may be not really understanding the notation in the first expression.

Is this the same or is this different? If it is not the same, what's the precise meaning of the former and what's the (different) meaning (if it has one) of the latter? Is the former just a way to underline $x$ may be contained in $e$ (i.e., more matter of style than formal meaning)?

The problem is that whatever the context $\Gamma$ may imply about the
variable $x$ is irrelevant. This rule is intended to type a
$\lambda$-abstraction, and the variable $x$ may be changed to another
variable by $\alpha$-conversion, without changing the semantics of the
$\lambda$-abstraction,  and thus without changing its type.

By writing $\Gamma, x: \tau_1$, we are considering a context $\Gamma$
where the variable $x$ has type $\tau_1$, ignoring what the type of
$x$ may have been in context $\Gamma$ alone. If $x$ could be assigned
a type in the context $\Gamma$ alone, it would refer to some homonymous variable that is irrelevant to the abstraction, since its scope is shadowed in the abstraction by the local variable $x$. Indeed, an $\alpha$-conversion would make $x$ disappear from $e$ altogether.

In other words: $\Gamma \vdash x: \tau_1$ may or may not be true, but
it is simply irrelevant to typing the abstraction.

Then, it is possible that $\Gamma \vdash e: \tau_2$. But that is only
possible if the type of $x$ is irrelevant, for example when $x$ does
not actually occurs in $e$, as for the abstarction $\lambda x.42$,
Then $e=42$ which is indeed typable. But in general, you cannot type $e$ without having a type for $x$ (for the variable $x$ of the abstraction).

In other words, you expect the type of $e$ to be in general related to the type of $x$, and it is their relation that the rule is intended to express.

What the rule says is that, if by adding to the context $\Gamma$ that the new
variable $x$ has type $\tau_1$, you can infer then that $e$ has type
$\tau_2$ in this new environment, then the abstraction $\lambda x. e$
has type $\tau_1 \rightarrow \tau_2$ in the original environment
$\Gamma$.

It says that the type of $e$ is dependent on the type $x$ may have.

Then, wherever the abstraction is applied to another expression $e'$, the type of the application is whathever the type of $e$ should be when the type of $x$ is that of $e'$.  But that is another typing rule.


Why does little endian apply to numbers and not to text strings? The Portable Executable file format is the format that Windows EXE files use.

It is a binary format.

Numbers are in little endian form. Thus, the following hex represents the decimal number 256, not 1.

00 01

Some fields in the file format represent text strings. For example, the "Name" field contains a null-terminated string that has up to 8 characters. Here are the hex bytes for a name and in parentheses the corresponding string:

2E 64 61 74 61 00 00 00 (.data)

My question is this: The file's byte order is little endian and therefore the bytes in a number are interpreted from right-to-left. Why aren't the bytes in a string interpreted right-to-left? Why aren't the bytes for the above string this:

00 00 00 63 74 61 64 2E

Notice that I reversed the order of the bytes. That's not how it is in EXE files, but why not? Why does "little endian" apply only to numbers and not to text strings?

The premise is wrong. Unicode encodings include UTF-16BE, UTF-16LE, UTF-32BE and UTF32-LE. Only UTF-8 has no Litte-Endian or Big-Endian variants.

Fundamentally, Endian-ness is about the byte order of multi-byte words, and you're thinking of text encodings which use a single byte per character (i.e. ASCII). There's no order to a single byte.


Computation tree logic and Kripke structures Specifications in Kripke structures are verified by Computation tree logic (CTL). However, refering to this Wikipedia article the CTL-operators are relative to a current state. So, when we want to verify if EF q is satisfied in a Kripke structure

Do we only need to check if EF q holds starting from the starting state oder do we need to check if EF q holds starting from every state?

CTL formulas are always evaluated from the starting state of the Kripke structure. Indeed, CTL stands for computation Tree logic, and the tree in question is the unwinding of the Kripke structure, starting from the initial state.

If you want to specify that $EF q$ should hold from every (reachable) state, that can be specified as $AGEFq$, which is still a CTL formula.


Matching Upper Bound for Online Problems I have an online problem and I want to prove that no deterministic online algorithm is competitive.

Let $\texttt{ON}$ be an online algorithm and $\texttt{OPT}$ an optimal offline algorithm (an adversary). Given a sequence of $n$ inputs $\sigma=\sigma_1\sigma_2\cdots\sigma_n$ revealed in an online fashion, let $v(\texttt{ON}_\sigma)$ and $v(\texttt{OPT}_\sigma)$ be the values achieved respectively by $\texttt{ON}$ and $\texttt{OPT}$.

What I proved is this: let $\sigma=\sigma_1\sigma_2$ be an 2-input sequence. If $\texttt{ON}$ acts on $\sigma_1$ with action $a$, then I could find an input $\sigma_2$ such that $$\frac{v(\texttt{OPT}_\sigma)}{v(\texttt{ON}_\sigma)},$$ is unbounded.

The problem is that, if the action $a$ changes, then the above ratio could be equal to $1$.

Is it sufficient to prove that the ratio is unbounded for some action $a$? Or must it be true for any $a$?

Since we are dealing with deterministic algorithms, the adversary can pick the hardest input possible for the online algorithm.

Since the online algorithm we are discussing is deterministic, given some input, its output can always be determined. The adversary is 'smart' in the sense that they are able to look ahead and pick input such that it gives the worst possible result for the online algorithm.

What you have proved seems to be sufficient.


How can I convert the Turing machine the recognizes language $L$ into an unrestricted grammar? According to this Wikipedia article, unrestricted grammars are equivalent to Turing machines. The article notes that I can convert any Turing machine into an unrestricted grammar, but it only shows how to convert a grammar to a Turing machine.

How do I indeed do that and convert the Turing machine the recognizes language $L$ into an unrestricted grammar? I have tried replacing transition rules with grammar rules, but a Turing machine can have many different configurations of states as well...

We encode the Turing machine's tape content in sentential forms; a special set of non-terminals encodes the current state. There can only be one of them in the sentential form at any point in time, placed to the right of the symbol the TM is currently pointing at.

The second crucial idea is that we have to reverse the process: TMs take the word as input and convert it to $1$ or $0$, or they don't terminate. The grammar, however, has to generate the word. Luckily, grammars are inherently non-deterministic, so we can just let it "guess" where the accepting $1$ came from; all words that cause the TM to accept can be generated then.

Let $\cal{Q} = \{Q_0,\dots,Q_k\}$ the set of state-nonterminals; w.l.o.g. let $Q_0$ be the starting-state-nonterminal and $\cal{Q}_F \subseteq \cal{Q}$ the set of accepting-states-nonterminals. First, we need starting rules that generate all possible accepting configurations:

$\qquad \displaystyle S \to \#1Q_f\# \qquad$ for all $Q_f \in \cal{Q}_F$.

Similarly, we terminate when we "reach" the starting state in the correct position, namely on the first symbol:

$\qquad \#aQ_0 \to \#a \qquad$ for all $a \in \Sigma$.

Translating the actual state transitions is straight-forward:

$\qquad \begin{align}
  aQ &\to cQ' \qquad\ \,\text{ for } a,c \in \Sigma \land (a,Q,N) \in \delta(c,Q') \\
  aQb &\to acQ' \qquad \text{ for } a,b,c \in \Sigma \land (b,Q,L) \in \delta(c,Q') \\
  abQ &\to cQ'b \qquad\, \text{ for } a,b,c \in \Sigma \land (a,Q,R) \in \delta(c,Q')
\end{align}$

There are some technical kinks to iron out; for instance, you have to get rid of the boundary markers $\#$ at the end. That can be done by spawning two special nonterminals instead of terminating, swapping those to the ends and then removing the $\#$ along with them. Furthermore, more $\#$ have to be created on demand; that requires some hacking of the rules with $d=\#$.

Also, the construction becomes a bit more complicated if the TM uses non-input symbols. In that case, the termination rules may be wrong: if there are non-input symbols somewhere on the tape, we have not generated a proper word. This can be fixed similarly to removing $\#$: spawn a special non-terminal from $Q_0$ that is swapped to the right and only removed if all symbols are from $\Sigma$.


What's the usage of $S$ in Dijkstra shortest path algorithm in the book Introduction to Algorithms? I don't understand how the $S$ is needed in dijkstra shortest path algorithm. For each node $v$ in $G.V$, the $v.\pi = previous\_node$ is used to denote it previous node in the shortest path to the current node, and $\rm{}INITIALIZE\rm{-}SINGLE\rm{-}SOURCE(G,s)$ also initialize all $v.\pi=NIL,$ so if it's impossible to reach some node, a simple check $$\textrm{if }v.\pi==NIL$$ is enough. So why the $S$ is needed? If all node can be reached then $S=G.V$ and it will be useless...

Edit: I add the book statement, but I wonder since that the priority queue has been used, the description becomes inconsistent with the pseudocode follows, no need to refer to $V-S$, which will slow down the algorithm?

Edit2: I suspect that priority queue is not a requirement of dijkstra SP algorithm, it's just a technique to speed up it, so the pseudocode in my another question on Dijkstra's SP algorithm is correct?

Edit3: Now I got stuck on my own comment, I suspect it's not correct:

I tried to make use of $S$, so I tried $G.Adj[u]\color{blue}{-S}$ and thought it will speed up the updating, but what if the following happen that the edge $(\color{red}{v,u})$ will not be selected since $\color{blue}S$ is already subtracted?

Book: Introduction to Algorithm 3ed. page 658, (forget about the679 is just pdf reader page #.)

Yes, the set $S$ is not needed in the Dijkstra’s algorithm, which is at the beginning of section 24.3, Dijkstra’s algorithm of the book introduction to algorithms by CLRS, third edition. That is, line 2 and line 6 in procedure DIJKSTRA($G,w,s$) can be removed without affecting the algorithm.

One immediate purpose of $S$ is to facilitate the proof of theorem 24.6 (Correctness of Dijkstra’s algorithm) of the book. Also, other implementations of Dijktra's might use that set more visibly such as the set of visited nodes in Wikipedia's entry. It is indeed a cornerstone concept to understand Dijktra's algorithm.

By the way, your observation that the line 7 of line 7 could be improved to "for each vertex $v \in G.Adj[u]\setminus S$" is very nice. In fact, that is done in the Wikipedia' entry mentioned above. Should that be done, $S$ could not be removed  any more as you have emphasized.


Transforming an array into one with descending order Problem Description

Given an array $A$ of $n$ integers, find the minimum number of operations to turn it into a new array $\widehat{A}$ with a (weakly) descending order: we require that $\hat{a}_i \geq \hat{a}_j$ for all $1\leq i<j\leq n$. Here an operation means either increasing or decreasing an element by $1$.

For example, it requires at least $4$ operations to turn the array $[1,2,3,4]$ into descending order. One solution is increasing the first element by $2$, increasing the second element by $1$, and decreasing the last element by $1$ (then the new array is $[3,3,3,3]$, which is in decending order).

My questions:

Is the problem NP-hard?
If not, what algorithm solves this problem with the best time complexity?

My efforts

We can write this problem as an integer linear programming. Say the elements in the array are $a_1,a_2,\ldots,a_n$, and those in the new array are $\hat{a}_1,\ldots,\hat{a}_n$ then the problem is essentially an interger programming:

$$
\begin{align*}
\text{minimize}\quad &\left|\hat{a}_1-a_1\right|+\cdots+\left|\hat{a}_n-a_n\right| \\
\text{subject to}\quad &\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

or equivalentlly

$$
\begin{align*}
\text{minimize}\quad &t_1+\cdots+t_n \\
\text{subject to}\quad &\hat{a}_i-a_i\le t_i, &i=1,\ldots,n\\
&-\left(\hat{a}_i-a_i\right)\le t_i, &i=1,\ldots,n\\
&\hat{a}_1\ge\cdots\ge\hat{a}_n
\end{align*}
$$

But it seems not to help because the coefficient matrix is not totally unimodular, thus we cannot relax it to linear programming.

I also find a property of optimum solutions:

  If some consecutive elements are originally in non-descending order, then they must be the same in an optimum solution.

I don't know whether this property helps.

There is an efficient dynamic programming solution if the input domain is small.

Let $C_i(v)$ be the cost of increasing/reducing elements such that $\hat a_i = v \wedge (\forall j >i)[\hat a_{j} \leq v]$.

It should be obvious that $C_n(v)$ is simply $|a_n - v|$, and thus computing $C_n$ completely is easy.

Then $C_{i}(v)$ is $|a_i - v| + \min(C_{i+1}(0), C_{i+1}(1),\dots,C_{i+1}(v))$. Using this we can compute $C$ as a table, using $C_{i+1}$ to fill $C_i$, working backwards all the way to $C_1$. Then choosing the minimal element of $C_1$ and working forwards again you have found the solution.


Reference for counting the number of paths in a DAG Given a connected DAG I know how to compute the number of paths between two nodes. See e.g. Counting number of paths between two vertices in a DAG .
Is there a reference or name for the algorithm?   If not, are there well known applications?

This idea is sufficiently well-known that I'm pretty sure I've seen papers just say things like "we can count the number of paths by dynamic programming" and stop there, with the expectation that the reader can fill in the details.
It is also the semiring problem for $\mathbb{N}$ with the usual $+$ and $\times$, and can be extended to cyclic graphs by extending the value set to $\mathbb{N} \cup \infty$ and adding a suitable $a^*$ operator.


What is required for universal analogue computation? What operations need to be performed in order to do any arbitrary analogue computation? Would addition, subtraction, multiplication and division be sufficient?

Also, does anyone know exactly what problems are tractable using analogue computation, but not with digital?

I don't think the question can be answered unless we have a definition of what kind of computations we are talking about.

Universality of a machine model w.r.t. a class of computationw means that any computation in that class can be computed by a machine. Unless you define the class of "arbitrary analogue computations", we cannot answer what is universality w.r.t. to them.

Now, the functions you have listed will only give you polynomials and their quotient which is a rather small class of real functions, you cannot even compute simple functions like $2^x$, $\lfloor x \rfloor$, $\sqrt x$, ... using them.

If your question is if there are physical systems that starting from an initial state will reach another state in some time and if that is always computable, then the answer depends on what kind of physics we are talking about, and what it means to set up an initial configuration and observing the result, etc.

If we are just talking mathematically about classical physics (we can set any initial configuration to infinite precision and without any considerations about things like energy needed to set up the configuration and observing the result is similarly from mathematical point of view) then it has been know for long time that there are differential equations about computable functions s.t. their solution is not computable, see Marian B. Pour-El, and J. Ian Richards, "Computability in Analysis and Physics", 1989.

An interesting case is if the n-body problem is computable (and if I remember correctly the answer is no, at least for $n>4$).

Generally, if we can just check equality of two real numbers that gives a function which is not continuous w.r.t. typical typologies of information about real numbers and therefore cannot be computed by a Turing machine since any function (including higher type functions) that a Turing machine can compute is continuous (w.r.t. the topology of information).


Can we quantify how close a partially correct programs is to being correct? I know that there is something called partial correctness, but I was wondering if there was a way to tell how close a semi-correct program is to a fully correct program.

For example, if you had a sorting program that almost completely sorts an array, could you use Hoare logic to determine how close it is to getting the correct answer? One way to do this would be to make the precondition a series of and statements and see how many of these statements the weakest precondition, resulting from the postcondition being propagated through the program, would be able to imply.

However, this method seems to be very crude. Is there any other way to do something like this?

Partial correctness does not mean that not all statements of a specification are met by an algorithm. Have a look at the Wikipedia article about correctness:

Partial correctness of an algorithm means that it returns the correct answer if it terminates.

Total correctness means that is it additionally guaranteed that the algorithm terminates.

Such a proof of termination can e.g. be done by a loop variant: To proof that a loop terminates we show that an integer expression is decreased in the loop body and that the expression stays always non-negative. Then the loop can be only iterated a finite number of times.
The B-Method uses such integer variants in its while loops.
An alternative for an integer expression would be a finite set where in each iteration an element is removed.

Example: A simple algorithm to initialise an array of size n with 0:

i := 0
while i<n do
  x[i] := 0
  i := i+1
done

Partial correctness can be proven by using a loop invariant ("all elements of x in 0..i are 0", 0<=i, i<=n). One must show that the invariant is fulfilled when entering the loop and after each iteration. After the loop we know that the invariant is fulfilled and the loop condition not (i>=n together with the loop invariant implies that i=n, that again implies "all elements of x in 0..n are 0").
Even if we forget the line i := i+1, we could prove the partial correctness of the algorithm, i.e. the array will be filled with 0 after termination. The problem would be that it does not terminate.

Termination can be shown by choosing n-i as a variant. With the invariant i<=n it can be proven that the variant is always non-negative and n-i is decreased (by increasing i) in every iteration. Thus the loop must terminate. Together with partial correctness, total correctness is shown.


Proof of NP Completeness of set-partition problem I have reduced subset sum problem to set partition problem but do not know whether it is correct and so I need your help.
MY METHOD
In subset sum problem we have to find a subset $S_1$ of set $S$ so that it sums to a number $t$ and in set partition problem we need to find a subset $X_1$ of set $X$ such that summation of numbers in set $X_1$ is half of that in $X$.
So let us take instance of subset sum problem where $t = (\text{sum of numbers in }X) / 2$. If we can solve the set partition problem than we solved the subset sum problem too. But we know that subset sum is NP Complete so subset sum problem is also NP Complete (I know how to prove it is NP).
I am having doubt whether we can make a choice of $t$ like that or not. Please help.

No, your can't arbitrarily choose $t$ so your proof is incorrect.

In fact, you have build a reduction from the following variant of subset sum problem to partition problem:

  Given a set $S$ of integers whose sum is $s$, is there a subset of $S$ whose sum is $s/2$?

This variant is different from the normal subset problem, and you cannot assert it is NP-complete (though it in fact is), so your proof is incorrect.

You can find a complete proof here.


PRAM with no bit operations and P vs NC I was reading up on something called the PRAM model without bit operations.
What exactly does it mean that this PRAM model cannot do bit operations?
I can't find a straightforward definition anywhere.
Surely the different processors will still be able to do all sorts of stuff with bits. The reason why I am asking is that the max-flow problem (which is in P cannot be solved in this model using a polynomial number of processors. So in fact it is a non-trivial implication of the conjecture
that $P \neq NC$. So it is further "evidence" of the $P \neq NC$ conjecture.

Without further information, it's hard to tell exactly. However, to the best of my knowledge, bit operations may be intended as follows. Consider the problem of finding the maximum element in an array of $n$ real numbers. This problem can be solved by an EREW algorithm in $\Omega(\lg n)$; moreover, no CREW algorithm can do any better.

However, this problem can be solved in $O(1)$ time with $n^2$ processors using a common-CRCW algorithm (in this model, when several processors write to the same location, they all write the same value). The key point here is that a CRCW PRAM is capable of performing a boolean AND of $n$ variables in $O(1)$ time with $n$ processors (which allows overcoming the $\Omega(\lg n)$ lower bound). I think that bit operations may refer to this powerful AND capability of a common-CRCW.

Additional information regarding the FAST-MAX algorithm can be found in the first edition of CLRS Introduction to Algorithms, chapter 30 (ALGORITHMS FOR PARALLEL COMPUTERS).


How private IP address is determined? Today I presented about IP address during my online class based on Computer Networks by Andrew S. Tanenbaum and during QnA session, I was asked about private IP Address range.
10.0.0.0 – 10.255.255.255
172.16.0.0 – 172.31.255.255
192.168.0.0 – 192.168.255.255

The questioner asked my why private IP address is determined in such range. I haven't really think much about the range because I accept it as something that had been decided by the people who came up with this technology but I eventually have to present again because I couldn't answer the questioner's question. Perhaps there are reason behind why the private IP address is determined in such ways?
For example why it starts with 10 and not 9? or why it starts with 172 and not 173?
I tried to read in RFC 1918 but I couldn't really find the answer about why they chose 10 or 172 or 192.
If anyone can share link that I could refer to or know the answer, I would highly appreciate it.
Thank you.

"The questioner asked my why private IP address is determined in such range"
IMO a good answer is "Because it has been established in RFC-1918; which is a "Best Current Practice" RFC :-)
The three ranges allow private networks to "resemble" the class A-B-C subdivision (and probably this is what the questioner wanted to hear from you). See older RFC791: .... To provide for flexibility in assigning address to networks and
allow for the  large number of small to intermediate sized networks
the interpretation of the address field is coded to specify a small
number of networks with a large number of host, a moderate number of
networks with a moderate number of hosts, and a large number of
networks with a small number of hosts..... Also see Wikipedia Classful network for more details / references.
The reasons for the particular numbers are not well known (and are only interesting from a historical-folklore point of view), and probably the main criteria was to use address spaces that were free/unused at the moment.

10.x.x.x comes from the old ARPANET and is easy to remember
172.x.x.x was marked by IANA as "Special purpouse" block of IP addresses
192.168.x.x was used by Sun in its workstations (?!?)


Numeral systems other than unary used in nature or in animal and human behaviours Representing numeric values using positional notation is one of the milestones in the history of arithmetic. Babylons used a base 60 system, Maya a base 20 system; base 10 system became "the standard" used by modern civilizations; digital computers use the Binary numeral system, ....

But if we look at nature, we found that life itself "heavily rely" on an alphabet of 4 symbols: the DNA has four (chemical) bases: adenine, cytosine, guanine and thymine (A, C, G, T) that are used to store the "instructions and information" to generate and drive the parts of a living organism.

But on a higher level, are there "natural algorithms" (algorithms found in natural processes, in animal behaviours or in everyday human behaviours) that take advantages of "numeral systems" other than the unary representation.

To be more precise I would like to know whether or not natural processes or living creatures make use of a finite, discrete alphabet of "symbols" and use them in a manner similar to a positional notation: the symbols are placed together and used as a whole to  represent "something" (an action, an information, an object, ...) among many other possibilites ... a sort of "index" in an exponential number of possibilites.

Another (obvious) non numeric example is the human language where (in general) a combination of finite number of sounds ("alphabet") are combined to form the words.

There is at least one example where a string of symbols from an alphabet is also used: proteins.

Proteins consist of chains of 20 different amino acids (usually, in some cases, it's 21 or 22) and the sequence of amino acids determines what given protein does.

This example is closely related to the DNA example you gave, because each amino acid in a protein is encoded by a triplet of bases in DNA.

For more information, see the article Genetic code on Wikipedia.


What Properties Matter For the Bound on Generalization Error of Hypothesis Set? As I know, there are several upper bounds on the generalization error of hypothesis set with respect to sample complexity. For hypothesis space $V$, if the learning algorithm output the set of hypotheses that are consistent with the training data, i.e., $\sum\limits_{1 \leq i \leq n}{\frac{I[h(x_i) \not= y_i]}{n}} = 0$, the VC theory gives the bound on generalization error. If we consider the "margin" or confidence of classification, PAC Bayes theory gives tighter bounds on generalization error with margin incorporated.

My question is: what other properties or structure of the set of all possible hypotheses output by the learning algorithm matter for the bound on generalization errors? Name a few.

Rademacher complexity is also a tool used to bound generalization error.


Complexity of set partition generation while equivalence relation is given Given a binary equivalence relation, R on a set A, Let P be the resulting partition. I want to generate the partition means each subset in the partition. What would be the fastest algorithm for this purpose? please help.

The binary equivalence relation induces an undirected graph: each item corresponds to a vertex, and draw an edge between each pair of equivalent items.  Now compute the connected components of this graph (this can be done in linear time using algorithms based on DFS).  Each connected component is a single subset in the partition.


Uniformly random efficient sampling of shortest s-t paths, with optimal random bits Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random,
The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of seemingly unnecessary random bits.
My question is:

Can the solution be improved to use a single random number in interval $[0,w(t))$, where $w(t)$ is the total number of shortest paths from $s\text{-}t$.
Alternatively, can the solution be improved to use $\left\lceil \log_2 w(t)\right\rceil $ random bits?

D. W. computes for each node $v \in S$ the number of paths $n(v)$ from $v$ to $t$. Using this information, it is easy to decode a number in the range $[0,n(s))$ to a unique path from $s$ to $t$ in $S$ (and so in the original graph). More generally, at each node $v$ we will come up with a procedure to map $[0,n(v))$ to a unique path from $v$ to $t$. Let the children of $v$ be $v_1,\ldots,v_k$. The idea is to write
$$ [0,n(v)) = [0,n(v_1)) \cup [n(v_1),n(v_1)+n(v_2)) \cup \cdots [n(v_1)+\cdots + n(v_{k-1}), n(v_1)+\cdots+n(v_k)), $$
and use the $i$th component to encode paths going through $v_i$. By subtracting $n(v_1) + \cdots + n(v_{i-1})$, we then reduce the problem to decoding a number in $[0,n(v_i))$ to a unique path from $v_i$ to $t$. Pseudocode left to the reader.


Complexity of Pythagorean triples We define a Pythagorean triple as a triple $\langle a,b,c\rangle$ such that $a,b,c\in \mathbb N$ and $a^2+b^2=c^2$.

In order to avoid duplicates, we say that a triple $\langle a,b,c\rangle$ is legit iff $b>a$.

Let $\mathcal P$ be the set of all legit Pythagorean triples.

We define a lexicographic order $\prec$ on $\mathcal P$, such that $$\langle a_1,b_1,c_1\rangle\prec\langle a_2,b_2,c_2\rangle\iff (a_1< a_2)\vee ((a_1=a_2)\wedge(b_1<b_2)$$

Let $$L_\mathrm{PT}=\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P\text{ w.r.t.}\prec\}$$

  What can we say about the complexity of $L_\mathrm{PT}$?

We say that a triple $\langle a,b,c\rangle$ is minimal if $gcd(a,b,c)=1$.
Let $\mathcal P_\mathrm{M}$ be the set of all legit, minimal triples.

We define $$L_\mathrm{PT}'=\{\langle \langle a,b,c\rangle,n\rangle \mid \langle a,b,c\rangle \text{ is the $n$'th triplet in } \mathcal P_\mathrm{M}\text{ w.r.t.}\prec\}$$

  What can we say about the complexity of $L'_\mathrm{PT}$?

This is not a full answer, but I think it is very useful.

Euclid's formula generates all primitive triples in a fairly linear fashion. Using all integers $m, n$ with $m > n$, $m, n$ coprime and $m-n$ is odd, all primitive triples can be generated as

$$a=m^2-n^2, b=2mn, c=m^2 + n^2$$

I don't have any knowledge on complexity, but hopefully this will help


Returning m greatest elements from k sorted array We have $k$ sorted arrays, $A_1[1...n_1],...,A_k[1..n_k]$, where $n_1+n_2+...+n_k=n$.

How can we get the $m$ greatest elements in running time $O(k + m\lg k)$?

I have tried to use MIN-HEAP size of $k$ since we have $k$ arrays. I have to navigate through the ends of the $k$ array somehow. By extracting the min of heap and getting new element from respective array was my idea but it does not work. I could not figure out getting m greatest elements.

Your idea works out. The idea is to maintain a heap of size $k$ which contains exactly one element from each array. For each array $A_i$, we maintain an index $p_i$ which keeps track of the position of the current element in the array. Initially, $p_i = n_i$, and we insert $A_i[n_i]$ into the heap.
We then repeat the following $m$ times:

Extract the maximum element from the heap.
If the extracted element belonged to $A_i$, then we decrease $p_i$ by one and insert $A_i[p_i]$ into the heap.

The initialization phase takes time $O(k)$, and the extraction phase takes time $O(m\log k)$, for a total of $O(k+m\log k)$. You can prove that the extracted elements are indeed the $m$ largest ones.


Computing parity function on n variables with O(n) gates Sipser example 9.29

He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same as parity on 2 variables, and then implement each XOR gate with two NOTs and two ANDs, and one OR. ... Let A be the language of strings that contain an odd number of 1's. Then A has circuit complexity O(n)."

I'm not seeing the steps that lead to saying that A has circuit complexity of O(n). Why can we say that if we implement a binary tree of XORs we can compute the parity with O(n) gates?

Because the parity is 1 if and only if the XOR of all the bits is 1.  In other words, computing the parity is equivalent to computing the XOR of the bits.  Sipser describes how to compute the XOR of the $n$ bits with $O(n)$ gates, which means that this same circuit computes the parity of those $n$ bits with $O(n)$ gates.


Conversion of nfa with self-loop to one without self-loop For every nondeterministic finite state automata that has self-loop(s), there exists an equivalent nfa that does not have any self-loop. How can we prove this statement in a general basis without the use of examples?

Add a new state and make the self loop point to the new state and add a empty transition from the new state back to the original state.

It is straightforward to prove that this NFA is equivalent to the original.


In describing the tokens of a programming language using RE, it is not necessary to have the $\epsilon$ or t. Why is this? In describing the tokens of a programming language using regular expressions, it is not necessary to have the $\epsilon$, (for the empty set) or t (for the empty string). Why is this?

Please tell me why is it not necessary thanks

The empty set is only needed in order to describe the empty regular language. The set of tokens of a certain type is never empty, so the empty set isn't needed.

Similarly, the empty string is only needed to describe regular languages which include the empty string. The empty string isn't a token of any type, so the empty string isn't needed.

Here are some proofs. I will use the convention in which $\emptyset$ is the emptyset and $\epsilon$ is the empty string. I will use the following inductive definition of regular expressions over an alphabet $\Sigma$:

$\emptyset$ is a regular expression.
$\epsilon$ is a regular expression.
For any $\sigma \in \Sigma$, $\sigma$ is a regular expression.
If $r$ is a regular expression then $r^*$ is a regular expression.
If $r_1,r_2$ are regular expressions then $r_1+r_2$ is a regular expression.
If $r_1,r_2$ are regular expressions then $r_1r_2$ is a regular expression.

Two regular expressions are equivalent if they generate the same language. We denote this by $\approx$. The language generated by $r$ is denoted $L[r]$.

Lemma 1. Every regular expression is either equivalent to $\emptyset$ or to a regular expression without $\emptyset$.

Corollary 1. If a regular expression doesn't generate the empty language, then it is equivalent to a regular expression without $\emptyset$.

Note that every regular expression not involving $\emptyset$ doesn't generate the empty language.

Proof. The proof is by structural induction. The base cases $\emptyset,\epsilon,\sigma$ are obvious. Consider now a regular expression $r$ constructed inductively from one or two regular expressions $r_1,r_2$, which we can assume satisfy the dichotomy in the lemma. If $r_1,r_2 \neq \emptyset$ then there is nothing to prove, so assume that at least one of them is $\emptyset$.

$r = r_1^*$: in that case $r = \emptyset^* \approx \epsilon$.
$r = r_1 + r_2$: if $r_1=r_2=\emptyset$ then $r \approx \emptyset$. If $r_1 \neq \emptyset$ and $r_2 = \emptyset$ then $r \approx r_1$.
$r = r_1r_2$: in that case $r \approx \emptyset$. $\qquad\square$

Lemma 2. Every $\emptyset$-free regular expression can be written in one of the forms $\epsilon,s,s+\epsilon$, where $s$ is $\emptyset,\epsilon$-free and $\epsilon \notin L[s]$.

Corollary 2. If $\epsilon \notin L[r]$ and $L[r] \neq \emptyset$ then $r$ is equivalent to a regular expression not involving $\emptyset,\epsilon$.

Proof. Again the proof is by structural induction. The base cases $\epsilon,\sigma$ are obvious. Let us now consider a regular expression $r$ constructed inductively from $r_1,r_2$ which are of one of the forms $s_i,s_i+\epsilon,\epsilon$, where the $s_i$ satisfy the conditions stated in the lemma.

$r = r_1^*$: If $r_1 = \epsilon$ then $r \approx \epsilon$. If $r_1 = s_1 + \epsilon$ or $r_1 = s_1$ then $r \approx s_1s_1^* + \epsilon$.
$r = r_1 + r_2$: If $r_1=r_2=\epsilon$ then $r \approx \epsilon$. If $r_1=s_1$ and $r_2 = s_2$ then $r$ is already of the required form. Otherwise $r \approx (s_1+s_2) + \epsilon$.
$r = r_1r_2$: If $r_1=r_2=\epsilon$ then $r \approx \epsilon$. If $r_1=s_1$, $r_2=s_2$ then $r$ is already of the required form. If $r_1=s_1$ and $r_2=s_2+\epsilon$ then $r \approx s_1s_2 + s_1$. Similarly, if $r_1=s_1+\epsilon$ and $r_2=s_2$ then $r \approx s_1s_2 + s_2$. Finally, if $r_1=s_1+\epsilon$ and $r_2=s_2+\epsilon$ then $r \approx (s_1s_2 + s_1 + s_2) + \epsilon$. $\qquad\square$


In counterfactual regret minimization, why are additions to regret weighted by reach probability? I'm reading the algorithm on page 12 of An Introduction to Counterfactual Regret Minimization. On lines 25 and 26, we accumulate new values into $r_i$ and $s_i$:

$25.\space \space r_I[a] ← r_I[a] + \pi_{-i} . (v_{\sigma I \rightarrow a}[a] - v_{\sigma}[a])$
$26. \space \space s_I[a] ← s_I[a] + \pi_{i} . \sigma^t(I, a)$

$r_I[a]$ is the accumulated regret for information set $I$ and action $a$. $s_I[a]$ is the accumulated strategy for information set $I$ and action $a$.
$\pi_{i}$ is the probability of reaching this game state for the learning player (for whom we're updating strategy and regret values in the current CFR iteration). $\pi_{-i}$ is the probability of reaching this game state for the other player.
Why do we multiply by $\pi_{-i}$ and $\pi_{i}$ to accumulate the strategy and regret on lines 25 and 26? Couldn't we just do this:

$25.\space \space r_I[a] ← r_I[a] + (v_{\sigma I \rightarrow a}[a] - v_{\sigma}[a])$
$26. \space \space s_I[a] ← s_I[a] + \sigma^t(I, a)$

It seems to me it doesn't matter exactly how much we adjust the strategy and regrets in this CFR iteration—so long as we do enough CFR iterations, won't we end up with good values for $r_I$ and $s_I$ in the end?

Algorithm 1, which I refer to in the question, produces a strategy that minimizes cumulative counterfactual regret.
The motivation is to get a strategy which minimizes overall regret (as defined earlier in the paper). That's because such a strategy approximates a nash equilibrium strategy.
In other words, cumulative counterfactual regret was designed to be:

computable with a reasonable runtime; and
an upper bound on overall regret, so that minimizing cumulative counterfactual regret minimizes overall regret.

In Regret Minimization in Games with Incomplete
Information it is proven that overall regret is bounded by cumulative counterfactual regret. I'm reading through the proof currently, and will update this answer with an intuitive explanation if possible.
But for future readers who come across this, reading that proof could be a promising direction for understanding the motivation behind Algorithm 1 and the underlying formulas.


Can formal languages be used to study mathematical notation? Question: Are there any introductory texts in formal language or programming language theory which discuss how to apply it to the study of optimal notation?

In particular, I am interested to learn what stack-languages, parse trees, and indices are, and how to predict when a certain type of notation will lead to exponential redundancy.

I have basically no background in either formal language/grammar or programming theory, since as a math major the only computer science I learned was algorithms and graph theory, as well as very modest smidgens of complexity theory and Boolean functions. Thus, if the only books which discuss this are not introductory, I would be grateful for answers that both list such books discussing exponential notation blow-up as well as introductory books that will prepare for the books which directly address my question.

Context: This question is inspired primarily by an answer on Physics.SE, which says that:

  It is very easy to prove (rigorously) that there is no parentheses notation which reproduces tensor index contractions, because parentheses are parsed by a stack-language (context free grammar in Chomsky's classification) while indices cannot be parsed this way, because they include general graphs. The parentheses generate parse trees, and you always have exponentially many maximal trees inside any graph, so there is exponential redundancy in the notation.

Throughout the rest of the answer, other examples of "exponential notation blow-up" are discussed, for example with Petri Nets in computational biology.

There are also other instances where mathematical notation is difficult to parse, for example as mentioned here when functions and functions applied to the argument are not distinguished clearly. This can become especially confusing when the function becomes the argument and the argument becomes the function, e.g. here.

Formal language theory does not concern itself with the semantics of the language. That might seem odd, since we tend to think of language as a mechanism for communicating something, but if you think about it, there are really two levels of understanding language (at least): the surface level, in which the language is a stream of lexemes, and the underlying denotational level which is more or less divorced from the surface representation. (Chomsky posited an intermediate "transformational" level to get around some limitations with CFGs but that's not relevant here.) Consequently, it is possible to say "the same thing" in different languages; Chomsky is not a Whorfian. (See Wikipedia for a brief overview, with some references).
Nonetheless, a context-free grammar is not sufficient to distinguish correct and incorrect utterances. Chomsky offered the classic example: Colourless ideas sleep furiously (which he spelled incorrectly, being a USian). See Wikipedia, again. (Unfortunately Wikipedia doesn't have a Canadian English version.) The precise division between syntactic and semantic errors is hard, if not impossible, to demarcate and there has been considerable debate over this topic in CS fields, which I'm not going to even attempt to discuss here because I always get into trouble when I do. However, we can identify one classic grammatical rule present in many human languages: noun/verb agreement. I disagrees seems to me to be a syntactic error in the sense that I understand the intent of the utterance perfectly but also recognize it as erroneous. But this syntactic issue can only be captured by a context-free grammar if we enumerate all possible agreements. That is, we can write something vaguely like $S \to NP_{sing} VP_{sing} | NP_{plural} VP_{plural}$, but it is easy to see how the enumeration could get out of hand in language with more complicated agreement rules (gender, for example).
The problem with context-free grammars is that they are context-free, although you shouldn't take that description too seriously because it is easy to fall into the trap of misinterpreting technical use of common words (which, I might argue, is the basis of this question in the first place). That means that a nonterminal (like $NP$ above) must derive exactly the same set of phrases regardless of the context in which it appears. So we could not write, for example, $S \to NP_X VP_X$ with the understanding that $X$ needs to be filled in the same way in both expansions. (This is one of the issues which which transformational grammar attempted to grapple.)
That is exactly the problem with tensor index contractions. A tensor index contraction places a particular requirement on the use of index variables: an index variable must be used exactly twice, in which case it cannot be on the left-hand side, or exactly once, in which it must be on the left-hand side. (Since I'm not a physicist, I'd be tempted to collapse that into saying that an index variable must appear exactly twice in all. But there is a semantic distinction between free and placeholder variables, which is important to the understanding of the expression.) Here, there is no simple finite collection of index variables and no limit to the number of placeholders used. Moreover, renaming placeholders does not affect semantics provided that the new names are not used elsewhere in the expression, and one might expect the formal language description to capture that fact.
It is in fact possible to rigorously prove the assertion that context-free grammars cannot capture contextual agreement, as in the previous examples. I think that has something to do with what the quoted claim is asserting. Depending on how omnicurious you are, you might find it interesting to learn more, but I don't think it will end up being particularly relevant to the philosophical or physical insights you seem to be seeking.
The other linked articles, about unfortunate surface forms in mathematical notation, are simply anecdotal; none of them, as far as I can see, makes any deep or even superficial point relevant to formal language theory, just as the possibly famous joke that one man's fish is another man's poisson is not even vaguely insightful about romance linguistics, but it's still funny (IMO).


Prove $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$ $13) \} $ is regular or context-free or neither $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$  $13)  \} $

Exercises: If the language L is regular (build a DFA or regular expression)
else if the language L is context-free (build a grammar or PDA)
else if the language L is not context-free (Prove)

so

We know that $ww ^ {R}$ without any restrictions isn't regular, but it is context-free. but with additional above restrictions $ L = \{ww^{R} \in \{a, b\}^{*} : |w|_{a} \equiv |w|_{b} \equiv 0$ $ (mod$  $13)  \} $ I have no idea how to prove this. I think this language still isn't regular :

Let's take $n, m > p$ where $p$ is from pumping lemma and $n mod 13 = 0$ and $m mod 13 = 0$ and chose word
$s = a^{m}b^{n}b^{n}a^{m}$ and use the pumping lemma that is not regular. Well?

Any idea?

Let
$$ P = \{ww^{R} : w\in \{a, b\}^{*} \} $$
$$R_a=\{u\in \{a, b\}^{*} : |u|_{a}\equiv 0\ (\text{mod}13)  \} $$
$$R_b=\{u\in \{a, b\}^{*} : |u|_{b}\equiv 0\ (\text{mod}13)  \} $$

We know $P$ is context-free.

We know $R_a$ is regular and $R_b$ is regular. So $R_a\cap R_b$ is regular.

So, $L=P\cap (R_a\cap R_b)$ is context-free.

Exercise 1. (One minute or less) Verify that $L=P\cap (R_a\cap R_b)$.

Exercise 2. Show that $R_a$ is regular.


Chess pieces placement algorithm I've got the following problem:

I've got chessboard with fixed size N x M
I've got list of pieces, like 2 queens, 2 rooks (It can be any piece with exception of pawn).
I need to find every combination where none of the pieces is in a position to take any of the others

For example for chessboard 3 x 3 and 2 rooks and 1 king, possible solutions are:

 |R|        |R|      K| |      | |K
-+-+-      -+-+-     -+-+-    -+-+-
R| |        | |R      | |R    R| |
-+-+-      -+-+-     -+-+-    -+-+-
 | |K      K| |       |R|      |R|

What I came out with:

I create a whitelist of fields where the new piece can be placed (at the beginning it has all fields of the chessboard)
I take the first piece from the list
I place it on the first field I take from whitelist: (1,1)
I update whitelist excluding all fields that are threatened with this piece I placed
Here I branch out: I take next piece from the list and call my method recursively on every field from the whitelist (I also need to check, if placing new piece would threat already standing piece).
I repeat it until the last piece is placed
If there are pieces left, but no fields on whitelist I just finish that branch.

I noticed I can calculate results only for first quadrant (fields (1,1),(1,2)(2,1),(2,2) for my example. Rest of the solutions can be received by just mirroring results from the first quadrant.

Problem with my solution is, it's not very fast. For chessboard 7x7 and 7 pieces it takes ~15 minutes to finish. I implemented it with scala.

Do you have any tips about how can I improve it?

Suppose you're trying to place $Q$ queens, $R$ rooks, $B$ bishops, $N$ knights, and $K$ kings.  Then doing things the way you're doing them now, at least provided the language isn't clever enough to memoize the pure function calls for you, means that you're processing each solution $Q!R!B!N!K!$ times, rather than once, since in a solution containing $Q$ queens you could have placed them in any of $Q!$ different orders, and so forth.

Similar logic also applies to the partial solutions in your call stack.

If you're just trying to place one of each piece then this isn't so bad.  If, on the other hand, you're trying to place 8 queens on an 8 x 8 board, this means each solution gets generated 8! = 40,320 different times.

This is probably the single largest issue you're seeing here.  I tested this out by writing a naive python program, and it was able to do 8 queens on an 8x8 board in considerably less than fifteen minutes running on a single core of my twelve-year-old laptop with 1GB of RAM.

I'm not particularly familiar with Scala but it's possible you could just keep your existing code but tell it to memoize your function, at least provided it's written as a pure function.

Other optimizations would be to parallelize the analysis (which, again, a functional language like Scala might be able to do near-automatically for you), and to take advantage of the four- or eightfold-symmetry of the problem (depending on whether the board is square or just rectangular) by putting everything into a canonical form.

One last thing to check is that the intermediate data is stored in such a way that you're not having to recalculate anything.  When checking for a blank square, you want a stored list of blank squares you can iterate over.  When checking to see if the piece you just added is threatening something already on the board, you want a stored list of occupied positions to work with.


Continuation-passing style: what is meant by "CPS'ing"? I'm reading Dijkstra Monads for Free for a presentation I'll be doing and it's pretty meaty. One of the things that I keep running into is the term "CPS'ing". I've read a little bit on continuation-passing style (i.e., I've read through most of the Wikipedia page and it didn't feel like utter nonsense...) but I'm still not clear what the phrase "CPS'ing" means.
They give an example, which I will duplicate here, after which I will present the main pattern I see:

Rather than being given manually, we show that these predicate transformers can be automatically derived by CPS'ing purely functional definitions of monadic effects (with answer type Type). For instance, rather than defining WP_ST, one can simply compute it by CPS'ing the familiar ST monad (i.e., state -> a * state), deriving
WP_ST a = ((a * state) -> Type) -> state -> Type

(For context, this can be found on page 1, first full paragraph at the top of the second column).
So there is a pretty obvious pattern here: Given some type
a1 -> a2 -> ... -> an

we can map it via the contraviariant functor F (a -> b) = (b -> a) that just reverses the arrows, yielding
an -> ... -> a2 -> a1

and then replacing each ai with (ai -> Type).
Is this a reasonable interpretation of the term "CPS'ing"? Also, it's not clear to me why this is useful - is there any motivation for what is gained by applying such a transformation?

I had only a quick look at the paper, but I believe that they are referring to moving from
$$
    t_1 \to t_2 \cdots \to t_n
$$
to
$$
    t_1 \to t_2 \cdots \to \lnot \lnot t_n
$$
where $\lnot t = (t \to r)$ for some fixed return type $r$. In the paper, they choose $r = \sf Type$. So, we get
$$
    t_1 \to t_2 \cdots \to (t_n \to {\sf Type}) \to {\sf Type}
$$
In the case of the state monad we get
$$
    state \to ((a \times state) \to {\sf Type}) \to {\sf Type}
$$
which is isomorphic to (exchanging the order of the arguments)
$$
    ((a \times state) \to {\sf Type}) \to state \to {\sf Type}
$$

Anyway, Sect. 2.3 of the paper shows the actual transform.


Finding the similarity between large text files My first question is: is there an algorithm that already exists for this? If not any thoughts and ideas are appreciated.

Let's say I have two large text files (original file A and new file B). Each file is English prose text (including dialogue) with a typical size 256K to 500K characters.

I want to compare them to find out how similar the contents of B are to A.

Similar in this case means: all, or a significant part, of B exists in A, with the condition that there may be subtle differences, words changed here and there, or even globally.

In all cases we have to remember that this is looking for similarity, not (necessarily) identity.

Preprocessing for the text:

Remove all punctuation (and close up gaps "didn't" -> "didnt");
Lowercase everything;
Remove common words;
Reduce all whitespace to single space only, but keep paragraphs;

Other possible optimisations to reduce future workload:

Ignore any paragraph of less than a certain length. Why? Because there's a higher probability of natural duplication in shorter paragraphs (though arguably not in the same overall position).

Have an arbitrary cut-off length on the paragraphs. Why? Mostly because it reduces workload.

Finally:

For every word, turn it into a Metaphone. So instead of every paragraph being composed of normal words it becomes a list a metaphones which help in comparing slightly modified words.

We end up with paragraphs that look like this (each of these lines is a separate paragraph):

WNT TR0 ABT E0L JRTN TTKTF INSPK WLMS E0L UTRL OBNKS JRL
TM RL SRPRS LKT TRKTL KM N SX WRT
LT ASK W0R RT WRKS T ST N WLTNT RT 0M AL

But I admit, when it comes to the comparison I'm not sure how to approach it, beyond a brute force take the first encoded paragraph from B (B[0]) and check every paragraph in A looking for a high match (maybe identical, maybe very similar). Perhaps we use Levenshtein to find a match percentage on the paragraphs.

If we find a match at A[n], then check B[1] against A[n+1] and maybe a couple further A[n+2] and A[n+3] just in case something was inserted.

And proceed that way.

What should be detected:

Near-identical text
Global proper noun changes
B is a subset of A

Thanks.

My first question is: is there an algorithm that already exists for this? If not any thoughts and ideas are appreciated.

Yes, the problem you expose is widely studied in computer science/machine learning and there are dozens of algorithms to do what you are looking for. Depending on the precise specifications of what you are looking for, the complexity of the algorithm may vary.
When I happened to have to perform this computation, I personally used the TF-IDF approach.

As I said it depends a lot on what you want to achieve and even a minimum change in the initial specifications can lead to a drastic change in the algorithm. You could also take a look at this link.


Narrowing the field of a combitorial game I'm doing a challenge and it has posed a problem I am unfamiliar with.  It goes like this,  You start with two numbers, 1 and 1.  You can combine the numbers in either direction, in this case makes 2,1 and 1,2 or in the case of 3,2 it would produce 5,2 or 3,5.  Always starting from 1,1 my challenge is to try to find a pair of numbers in as few "moves" as possible.

My first pass was to build a greedy-first SSS* like algorithm.  Works well for a small space but in the end takes too long on large inputs.  So I think I have to massively narrow the search.  Or I'm sure someone has seen this before and has come up with a clever workaround.

Any help is appreciated

You have discovered the Calkin–Wilf tree, which is the game tree of your game. There is a unique way to reach any pair of coprime positive integers. Given a pair of coprime positive integers, repeatedly subtract the smaller one from the larger one, and you will eventually reach $(1,1)$. Reversing your moves, you obtain the unique way to generate the given (ordered) pair.


Finding two store typings that make the same store valid (lambda-calculus with references) Problem 13.5.2 of Pierce's TAPL's book (page 167) asks:

  Can you find a context $\Gamma$, a store $\mu$ and two different store typings $\Sigma_1,\Sigma_2$ such that both $\Gamma | \Sigma_1 \vdash \mu$ and $\Gamma | \Sigma_2 \vdash \mu$?

I'm not getting the proposed solution:

But how can this be the case? I mean should not $l$ be of a reference type $Ref(T_1)? $ How can it be of function type?

The store $\mu$ indicates the type of what is stored in the reference. If $\Sigma(\ell) = T$ then the expression $!\ell$ has the type $T$, and the expression $\ell$ has the type $\mathsf{Ref}(T)$.

If all you need is for $\lambda x:\mathsf{Unit}. (!\ell)(x)$ to be well-typed, then $\ell$ must be a reference to a function whose argument type is $\mathsf{Unit}$, with no constraint on the return type.


Sum collision from two lists of numbers Suppose you have two large lists of integers of length $N$, and you want to find two pairs $(a_1, b_1)$, $(a_2, b_2)$ from the lists such that $a_1 + b_1 = a_2 + b_2$ (modulo the integer width). Say for example, that $N = 2^{32}+1$ and the integers are 64 bits.

Is there any efficient way to do this? I know that if you are given a particular value, you can easily find the pairs that sum to that value in linear time, so the hard part is finding the colliding sum value in the first place. The obvious approach is $O(N^2)$, but I can't think of anything better.

One other idea I had was to try FFT to do a convolution on the lists, but I don't think that helps because the lists of integers are sparse, while my understanding is that the fourier transform would involve computing $2^{64}$ elements.

This answer says that there is an $O(N^{4/3})$ algorithm if the integers are randomly distributed, but doesn't provide any details.

You can find a solution with an algorithm that requires about $2^{24}$ operations and $2^{22}$ space, and requires only $N=2^{22}$ entries in each list.  (If you have more than that in each list, ignore the rest and use only the first $2^{22}$ entries.)  Here's how.

Step 1. Build a list $L$ of all of the pairs $(a,b)$ such that $a+b \equiv 0 \bmod 2^{22}$.

By the birthday paradox, we expect there will be about $N^2/2^{22} \approx 2^{22}$ such pairs $(a,b)$, since there are $N^2$ possible pairs and each pair has a $1/2^{22}$ chance of satisfying the condition.  To find them, build a sorted list of the values $a \bmod 2^{22}$, a sorted list of the values $-b \bmod 2^{22}$, and merge the sorted lists.  Or, use a hash table.

Step 2. Look for two pairs $(a_1,b_1)$ and $(a_2,b_2)$ in $L$ that have the same sum modulo $2^{64}$.

By the birthday paradox, we expect such a solution should exist with high probability, since we have about $2^{22}$ entries in $L$ (and thus about $2^{43}$ candidate solutions) and the condition holds with probability $1/2^{42}$.  (Why $1/2^{42}$?  Well, their sum is guaranteed to match in the low 22 bits, by the way we constructed $L$.  So, we just need their high 42 bits to match too.)


Does the "dictionary of stacks" ADT have an accepted name? With a stack, you can push and you can pop. There's also a generalization, let's call it a foo, in which key-value pairs are involved. The idea is that instead of just pushing a value, we push a key-value pair, as in L.push(key, value). Similarly, to pop a value, we have to supple a key. As in L.pop(key).

A straightforward implementation can be obtained as follows: choose an implementation for the dictionary data type, and then define that a foo is a dictionary in which the values are linked stacks. So L.push(key, value) is executed by querying the dictionary for the stack associated with the key key and then pushing value onto that stack. Similarly L.pop(key) is executed by querying the dictionary for the stack associated with the key key and then popping the top value.

A different implementation that can be more space-efficient under some circumstances uses a single linked list, whose nodes are key-value pairs. To perform L.pop(key), we search through the linked list until the desired key is found, and then pop that particular node. In fact there's situations where this single-list implementation is actually more time-efficient*; in particular, if you're mainly pushing and popping items in the reverse order, avoiding the cost of hashing the key can meaningfully improve the speed up of the lookup.

(*) You can't improve the big-$O$ time-complexity like this, only the practical running speed.

Anyway, since this data structure appears frequently in some of my amateur research into the foundations of mathematics, I'd be interested in getting a name for it.

Question. Does the "dictionary of stacks" ADT have an accepted name?

The implementation with a linked list is called association list, or alist for short.

I don't think there's a universal term for the interface. I'd call it a dictionary with shadowing of keys (pushing (k,v2) when the data structure already contains (k,v1) shadows the existing binding for k).


What type of HMM-GMM I need Context: I have 100 speech sentences that I asked my friend to speak. The vocabulary in the sentences are same but only the order of words are changed. My friend says that he spoke exactly what was asked for each sentence. But I don't know whether he spoke exactly that sentence or something else. What I have here is those 100 reference sentences against which I need to match his speech samples. As I want to do it by computer and not by listening manually therefore I am seeking your guidance.

Data: I have been able to segment the words in each speech sample of my friend. So I have 100 sentences each segmented into individual words with sequence of each word preserved for each sentence. I have extracted required features from each word (MFCC + Delta and Delta Delta).

What I am looking for: I need your guidance and help in informing how can I recognize these words with over 95% accuracy. As I read many papers and articles, GMM + HMM is the reasonably good way to do this. But I have a confusion, when I have already segmented every sentence, why should I try to match the entire speech sentence by transitioning state to state using HMM? I can simply match each word and see if the sequence is same with respect to the reference sentence word sequence. Is GMM + HMM the way to go for this? Can I use DTW or Neural Network or SVM to classify (matching or not matching) each word and get high accuracy?

Normally in speech-to-text we don't already have a perfect segmentation into words, which is why we often use the HMM to match the entire speech sentence.  Also, this way the HMM can take into account probabilistic information on the distribution of word bigrams (and even trigrams).  If you already have a segmentation and you are sure it is correct, then you can use the HMM to match just the word, if you like.  But getting a reliably correct segmentation is tricky, given how people speak in practice, so you might want to check how accurate your segmentation is before relying upon it.

Either GMM + HMM or DTW would be a reasonable approach.

A very simple approach would be to download an existing speech-to-text tool and use it on those sentences, instead of trying to build something yourself.