Huffman Code VS Hu–Tucker Code Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background.

Huffman Code is the binary-code induced from a binary tree, constructed by Huffman's Algorithm.
Hu–Tucker Code is the binary-code induced from an alphabetical search tree.
According to Wikipedia (see the paragraph on Optimal alphabetic binary trees (Hu–Tucker coding)):

  In the standard Huffman coding problem, it is assumed that any
  codeword can correspond to any input symbol. In the alphabetic
  version, the alphabetic order of inputs and outputs must be identical.
  Thus, for example, $A = \left\{a,b,c\right\}$ could not be assigned
  code $H\left(A,C\right) = \left\{00,1,01\right\}$, but instead should
  be assigned either $H\left(A,C\right) =\left\{00,01,1\right\}$ or
  $H\left(A,C\right) = \left\{0,10,11\right\}$. This is also known as
  the Hu–Tucker problem, after T. C. Hu and Alan Tucker, the authors of
  the paper presenting the first linearithmic solution to this optimal
  binary alphabetic problem, which has some similarities to Huffman
  algorithm, but is not a variation of this algorithm. These optimal
  alphabetic binary trees are often used as binary search trees.

My question is, what are the applications of such trees? (alphabetic binary tree)
I tried to search online, but couldn't find a satisfying answer.
I also read the introduction in Hu & Tucker's paper on the subject:
Optimal Computer Search Trees and Variable-Length Alphabetical Code, but I couldn't figure out exactly the use of such tree from their example.

I can very well understand the need of a compact, optimal prefix code, induced by an optimal tree (i.e. Huffman Code); this can be used for compression, but what is the use of alphabetical binary trees?

Let me give you a real-world example, that's very similar to something I wrote once.

Let's say you're implementing a library catalogue system. A library catalogue is conceptually a collection of documents (perhaps in MARC format). A user of this system might enter a query, as in any search engine, and get a set of documents in return. The user would like to be able to sort the result set by some field (e.g. title or author), and display the result set a screenful at a time.

Sorting is a well-understood problem. However, suppose this is a big library, and a search returns 100,000 relevant documents. Clearly the user is not going to look through all of them! In fact, the user might only look at the first couple of screens of results (say, 50-100 documents) and realise that their query was too broad, and so refine it further.

Moreover, accessing the sort key for a document requires parsing the document. True, you could extract the possible sort keys into a form where you didn't require parsing MARC (or, even worse, SGML/XML), although that would duplicate data. And besides, these are strings we're talking about. They are variable length, which makes memory and disk management difficult.

So you could try a fixed-size format. You could take, say, the first K characters from every title for some predetermined K, and store it in an array on disk, indexed by document number. Then you could first sort the documents by those string prefixes (i.e. something like a bucket/radix sort), and any documents which fall in the same bucket could then be sorted by extracting the "real" sort key from the documents.

The nice thing about this is you don't need to fully sort the result set. Because the user is paging through the set, you only have to completely sort the first few screenfuls, and just retain enough bucket information to sort the others if the user decides to page through that far.

So that's an improvement, but how do you set K? A lot of titles start with the letters "The ", and that's using 32 bits of information for very little discriminatory power. In fact, you'd probably be surprised how many periodicals are called "The International Journal of X", or similar boilerplate, and some searches are likely to return a lot of documents with similar titles just like that.

One possible solution is to use an order-preserving code. Compress all titles using that code, and store first 64 bits (or some other fixed amount) of the compressed title in an on-disk array. This has quite a few practical advantages: parts of the title which have very little discriminatory power get very short code words (so you don't waste space on irrelevant detail), you can sort by it because it's order-preserving, and the keys are fixed-length (so they're easy to manage in an efficient way).


Generating Pairs of Random Numbers Please consider the following probability density function of two variables.
\begin{eqnarray*}
f(x_1,x_2) &=& \begin{cases}
    2(x_1+x_2) & \text{for} \,\, 0 \le x_1 \le x_2 \le 1\\
    0 &\text{ otherwise } \\
    \end{cases}
\end{eqnarray*}
I would like to generate two random values $X_1$ and $X_2$ such that there
distribution is consistent with the above probability density function.

If the above probability density function was of just one variable, then I would solve the above problem with the following steps.
1) I would  find the distribution function $F$ by integrating.
2) I would generate a random number $a$ on the interval $[0,1]$ using the
uniform distribution.
3) I would find a number $X$, such that $F(X) = a$. Then $X$ would be the
random number I seek.
I am wondering whether a similar method would work for a function of two
variables.

This is the problem of sampling from a multivariate distribution.

Simple method

In your case, there is a fairly simple method that will probably suffice.  First, randomly pick a value for $X_1$ according to the marginal distribution on $X_1$.  In other words, we define

$$g(x_1) = \int_{x_2=x_1}^{x_2=1} f(x_1,x_2) \; dx_2,$$

the probability density function for $x_1$, and sample $X_1$ according to $g$.  Since this is a univariate distribution, you already know how to do that (using the methods you described).  Here we have $g(x_1) = 1 + 2x_1 - 3 x_1^2$.

Second, randomly pick a value for $X_2$ according to the conditional distribution on $X_2$ given the value of $X_1$ picked earlier.  This has probability density

$$h_{x_1}(x_2)  = f(x_1,x_2)/g(x_1),$$

which is also a univariate distribution, so you already know how to sample from $X_2$ (once $X_1$ is fixed).

More general method

Alternatively, you can apply any of the general methods for sampling from a multivariate distribution.  They are probably shooting a fly with a cannon -- they're probably much more complex than what you need.  But if you want a relatively simple one, you could take a look at slice sampling.


non-binary locality-sensitive hashing with random projections I'm interested in using a random projection as a locality sensitive hash. In every example of this I've seen, it is suggested to pick a random hyperplane and produce a binary number corresponding to which side of the hyperplane a data point lies. I want to use locality sensitive hashing with a random projection, but I need to be able to produce more than just two possible indexes.

I'm wondering if I could make an LSH by binning data according to this strategy:

Initialize a d x k matrix, where d is the input data dimensionality and k is the number of hash indexes we want.
Project incoming data into k-dimensional space using this matrix.
Take the argmax of the new k-dimensional vector.  In other words, output the dimension that has the largest value.

If not, does anyone know of another technique? Thanks!

Let $h_r(x)$ be a hash function that hashes a point $x$ to a one-bit hash output.  Then you can construct a hash function that gives you a $b$-bit hash output, by concatenating $b$ independent one-bit hashes:

$$h_{r_1,\dots,r_b}(x) = (h_{r_1}(x), \dots, h_{r_b}(x)).$$

For example, you can pick $b$ random hyperplanes; then the $i$th bit of the hash will indicate where the point falls relative to the $i$th hyperplane.

This avoids the need to invent new LSH functions.


Where can I find a data set of graphs with known domination numbers? I implemented an algorithm to find the minimum dominating set of a graph. I want to check the output of the algorithm against some graphs for which the domination number has been determined.

Where can I find graphs with a known domination number?

One place to look is House of Graphs, which is a database of "interesting" graphs. For instance, there are graphs that have been used as counterexamples to various conjectures, have extremal properties with respect to some parameter, and so on. For more, see [1].

Another possibility is using Mathematica, which also has a database of graphs accessed through its GraphData-function.

[1] Brinkmann, G., Coolsaet, K., Goedgebeur, J. and Mélot, H., 2013. House of Graphs: A database of interesting graphs. Discrete Applied Mathematics, 161(1), pp.311-314. --- Free version at arXiv


Approximation scheme for Multiple Choice Knapsack The paper _Fast Approximation Algorithms for Knapsack Problems (E. Lawler, 1979) gives an FPTAS (fully polynomial time approximation scheme) for the multiple choice knapsack problem (MKP). But MKP is strongly NP-hard, so it cannot have an FPTAS unless P=NP. Is the result of this paper wrong?

The paper you cite is not available to me. However, according to this paper: "Improved Fully Polynomial time Approximation Scheme for the 0-1
Multiple-choice Knapsack Problem",

  0-1 MCKP is $\text{NP}$-hard [4] as it contains the 0-1 Knapsack problem as a special case [5, 13] but it can be solved in pseudo-polynomial time (emphasis added) through dynamic programming [7, 2].

Thus, 0-1 MCKP is not strongly $\text{NP}$-hard.

One of the citations is

[7] K. Dudzinski, S. Walukiewicz, “Exact Methods for the Knapsack Problem and its Generalizations”, European Journal of Operational Research, (28), (1987): 3–21.


Is the complement of the Turing machine equality language not recursively enumerable as well? The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

And thus this language would be recursively enumerable.

However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

The language that determines if two Turing machines are equivalent is not recursively enumerable because you can reduce it to the emptiness problem (does a Turing machine take no input).

You have the reduction the wrong way around. You're saying "Telling if two Turing machines are equivalent is impossible because, if I could solve some impossible problem, I could solve this one." Well, that's like saying, "Lifting a can of beans is impossible because lifting a truck is impossible and, if I could lift a truck, I could lift a can of beans."

Rather, you want to reduce the known-hard problem to TM equivalence: "If I could solve this problem, I'd be able to solve this impossible problem." Specifically, if you could solve the TM equivalence problem, you could solve the TM emptiness problem by asking, "Is the machine I'm interested in equivalent to this machine that immediately rejects every input?"

  Then for the complement of this language (ie. if two Turing machines are not equivalent) would you be able to reduce that to the non-emptiness problem (a Turing machine takes some input)?

Again, you mean the reduction to be the other way around. So, we need to show that the non-equivalence problem being RE would make the non-emptiness problem RE.  But the non-emptiness problem is RE: just dovetail simulations of the machine on all inputs and accept if it accepts one of them.  So there's no contradiction available, here.

  However, I thought the Turing machine equality language is an example where both a language and its complement are not recursively enumerable.

Correct.  Intuitively, you can't enumerate the language of inequivalent TMs because to do that would require you to definitively say "This machine loops on some input that this other machine accepts." And, indeed, we can turn this intuition into a formal proof.

First, observe that the Turing machine non-halting problem (given a description of a Turing machine $M$ and an input $x$, does $M(x)$ loop?) is not RE. This is the complement of the halting problem so, if it were RE, then both the halting problem and its complement would be RE. But if a language and its complement are both RE, they're both recursive, and we know that the halting problem isn't recursive.

Now, observe that, if we could solve the TM inequivalence problem, we could solve the non-halting problem. To determine if $M$ loops on input $x$, just ask if it is inequivalent to the machine "If the input is $x$, halt; otherwise, do the same as $M$."


Meaning of this python modulo operator exercise? I just got started with Python PCEP course material on netacad.com.

I've come across the following exercises:

   2 % -4 = -2
   2 % 4 = 2

As I understand it, the modulo operator returns the remainder of a division. So 2 divided by (-4) gives (-0.5). How does Python3 calculate the remainder of that as 2?

I know it's stupid but what's the reasoning behind that result?

Briefly, if $a$ is an integer and $b>0$ is a positive integers then you can find an integer $m$ and an integer $r \in \{0,\ldots,b-1\}$ such that
$$
a = mb + r.
$$
We say that $m$ is the quotient and $r$ is the remainder. For example, if $a=2$ and $b=4$ then $m=0$ and $r=2$.

When $b$ is allowed to be negative, the exact meaning is language-specific. You can work out the case of python by trying a few examples.


Why can't a compiler create universal N-bit code (e.g. 32-bit, 64-bit, etc.) It is my understanding from what I have read that you need to compile separate executables for 32 bit and 64 bit machines. So if I compile a C program for example I need to compile 2 different binaries for 32-bit and 64-bit machines.

However, it seems like intuitively a compiler should just be able to compile down to instructions that say "allocate N bits of space" and similar for other related instructions rather than "give me 32-bits of space" or "give me 64 bits of space"?

Why is this not the case (looking for some intuition at a high level)?

The instruction set for a 32-bit processor is different from the instruction set for a 64-bit processor.  The 64-bit instructions can't be executed on a 32-bit processor.  So, the program really does need to be compiled to something different: if you take a program compiled for a 64-bit processor, and try to run it on a 32-bit processor, the processor won't run it, because it doesn't understand the new 64-bit instructions.


Algorithm to find diameter of a tree using BFS/DFS. Why does it work? This link provides an algorithm for finding the diameter of an undirected tree using BFS/DFS. Summarizing:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.

Why does it work ?
Page 2 of this provides a reasoning, but it is confusing. I am quoting the initial portion of the proof:

Run BFS on any node s in the graph, remembering the node u discovered last. Run BFS from u remembering the node v discovered last. d(u,v) is the diameter of the tree.
Correctness: Let a and b be any two nodes such that d(a,b) is the diameter of the tree. There is a unique path from a to b. Let t be the first node on that path discovered by BFS. If the paths $p_1$ from s to u and $p_2$ from a to b do not share edges, then the path from t to u includes s. So
$d(t,u) \ge d(s,u)$
$d(t,u) \ge d(s,a)$
....(more inequalities follow ..)

The inequalities do not make sense to me.

All parts of proving the claim hinge on 2 crucial properties of trees with undirected edges:

1-connectedness (ie. between any 2 nodes in a tree there is exactly one path)
any node can serve as the root of the tree.

Choose an arbitrary tree node $s$. Assume $u, v \in V(G)$ are nodes with $d(u,v) = diam(G)$. Assume further that the algorithm finds a node $x$ starting at $s$ first, some node $y$ starting at $x$ next. wlog $d(s,u) \geq d(s,v)$. note that $d(s,x) \geq d(s,y)$ must hold, unless the algorithm's first stage wouldn't end up at $x$. We will see that $d(x,y) = d(u,v)$.

The most general configuration of all nodes involved can be seen in the following pseudo-graphics ( possibly $s = z_{uv}$ or $s = z_{xy}$ or both ):

(u)                                            (x)
  \                                            /
   \                                          /
    \                                        /
     ( z_uv )---------( s )----------( z_xy )
    /                                        \
   /                                          \
  /                                            \
(v)                                            (y)

we know that:

$d(z_{uv},y) \leq d(z_{uv},v)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
$d(z_{uv},x) \leq d(z_{uv},u)$. otherwise $d(u,v) < diam(G)$ contradicting the assumption.
$d(s,z_{xy}) + d(z_{xy},x) \geq d(s,z_{uv}) + d(z_{uv},u)$, otherwise stage 1 of the algorithm wouldn't have stopped at $x$.
$d(z_{xy},y) \geq d(v,z_{uv}) + d(z_{uv},z_{xy})$, otherwise stage 2 of the algorithm wouldn't have stopped at $y$.

1) and 2) imply $\, \\ d(u,v) = d(z_{uv},v) + d(z_{uv},u) \\ \qquad\geq d(z_{uv},x) + d(z_{uv},y) = d(x,y) + 2\, d(z_{uv}, z_{xy}) \\ \qquad\qquad\geq d(x,y)$.

3) and 4) imply $\, \\ d(z_{xy},y) + d(s,z_{xy}) + d(z_{xy},x) \\ \qquad\geq d(s,z_{uv}) + d(z_{uv},u) + d(v,z_{uv}) + d(z_{uv},z_{xy}) \qquad\qquad\qquad\qquad \\ \, $ equivalent to $\, \\ d(x,y) = d(z_{xy},y) + d(z_{xy},x) \\ \qquad\geq 2*\,d(s,z_{uv}) + d(v,z_{uv}) + d(u,z_{uv}) \\ \qquad\qquad\geq d(u,v)$.

therefore $d(u,v) = d(x,y)$.

analogue proofs hold for the alternative configurations

                 (u)                          (x)
                   \                          /
                    \                        /
                     \                      /
     ( s )---------( z_uv )----------( z_xy )
                     /                      \
                    /                        \
                   /                          \
                 (v)                          (y)

and

                          (x)        (u)
                          /            \
                         /              \
                        /                \
     ( s )---------( z_xy )----------( z_uv )
                        \                /
                         \              /
                          \            /
                          (y)        (v)

these are all possible configurations. in particular, $x \not\in path(s,u), x \not\in path(s,v)$ due to the result of stage 1 of the algorithm and $y \not\in path(x,u), y \not\in path(x,v)$ due to stage 2.


LU decomposition with pivoting I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero.

How to solve this problem? Iterational methods are not applied in this case.

One way is LU Decomposition method with reordering rows of $A$ to get entries in the main diagonal that are not zero, using permutation matrix. How can we quickly reorder the rows of the matrix or find the permutation matrix?

Note that the matrix dimensions are large and I have to write a program to solve SLAE in C# language, so I do not need any Matlab or Mathematica functions. Thanks!

This is a bipartite matching problem, which has several known algorithms. As a bonus, you get a combinatorial criterion for when it is even possible (namely, Hall's theorem).

Construct a bipartite graph with $n$ vertices on each side $x_i,y_j$. Connect $x_i$ to $y_j$ if $A_{ij} \neq 0$. A maximum matching in this graph, if it involves all the vertices, gives you a permutation $\pi$ such that $A_{i\pi(i)} \neq 0$ for all $i$.


Kripke automaton and observations This is a question concerning Kripke automaton. My answers seem a little short and I was wondering if I was missing something?
Transition table of a Kripke automaton:

A -> red light is on

B and D -> blue light is on

C -> both light are on

1) Is the test 001blue satisfied by any state?

Attempt: No

2) Is the test 001red satisfied by every state?

Attempt: Yes but I dont know how to show it.

3) Which test could tell difference btw A and C?

Attempt: test = 100both; C satisfies test, A doesnt

4) Can any test distinguish B and C?

Attempt: Yes, test = 10001blue; B satisfies test, C doesnt

5)Show that no test can tell the difference btw B and D.

Attempt: Their observations are different.

Your answers seem correct.
As for 2: one way is to simply check, a quicker way is to observe that all states go to A upon reading 1, so the sequence 001 ends in A, and A satisfies "red".

3 can be solved by the test "blue" (without any moves) and 4 can be solved with the test "red".

As for 5: in order to show that no test can differentiate B and D, observe that for the letter 1, both go to A, for the letter 0 both go to C, and both have the same light (blue). Thus, you can say that the "language" of both state is equal.


Can the difference of a non-regular and a regular language be regular? I have some trouble understanding some exercises related to operations on regular languages.I tried to apply their closure properties, but I am not sure how to do the following exercises:

If $L_2,L_3$ are regular and $L_1 \setminus L_2 = L_3$, is $L_1$ also regular?
If $L_2,L_3$ are regular and $L_1 \cap \overline{L_2} = L_3$, is $L_1$ also regular?

When $L_2 = \Sigma^*$, then $L_3 = \emptyset$ no matter what $L_1$ is.

Let us say that a language $L$ is subset-regular if $L \cap L'$ is regular for all languages $L'$. In other words, $L$ is subset-regular if all of its subsets (including $L$ itself) are regular.

Theorem. A language is subset-regular iff it is finite.

Proof. Clearly every finite language is subset-regular. In the other direction, an infinite language has uncountably many subsets, so not all of them can be regular. $\quad\square$

We can replace $\Sigma^*$ above with the complement of any subset-regular language, that is, with any cofinite language. Moreover, due to the theorem above, only cofinite languages work: if $L$ has a non-regular (proper) subset $L'$, then $\overline{L'} \setminus \overline{L} = \overline{L'}$ isn't regular.


Choose the best classifier to predict the label of strings of a regular language I have to tackle this problem:
I have some strings that are my training set. These strings belong to a regular language corresponding to a deterministic finite automata (hidden namely I don't now it, neither the language nor the automata). A string is labeled like positive if belong to hidden language and negative otherwise. The strings of training set are correctly labeled.
I have to build a statistical classifier from training set that predicts the label of strings not seen (generalization) in the best way (better accuracy, respect to actual labeling of hidden language/automa).
I have to choose between Support Vector Machine (SVM), Recurrent Neural Network and Convolutional Neural Network.

What could be the best choice and why?

My bet would go to a Recurrent Neural Network, as it closely models some (fuzzy, non-discrete) state machine as each character is output. A decent start to read up on RNNs for this purpose is to read the article The Unreasonable Effectiveness of Recurrent Neural Networks which describes character-level RNNs used to predict text.


How to prove that if $L, G$ are regular languages then $\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language? Prove that if $L, G$ are regular languages over $\{a,b,c\}$ then $H=\{w\in L|\exists x\in G: |x|=2\cdot |w|\}$ is a context-free language?

I think this could be a good exercise and the conditions are very simple.

Because $L,G$ are regular  they have corresponding DFA's:
$$
L=\bigg(\sum,Q_1, q_{01,\delta_1, F_1}\bigg)\\
G=\bigg(\sum,Q_2, q_{02,\delta_2, F_2}\bigg)
$$

Then we can build a pushdown automaton $M$ for $H$:

$$
M=\bigg(Q_1\times Q_2\times \{0,1,2\}\cup \{q_f\}, \sum,\{A, S\},\delta, (q_i,q_j,0),S,F_1\times F_2\times\{2\}\bigg),\quad q_i\in Q_1, q_j\in Q_2, q_f\in F_1\times F_2\times\{2\}, S \text{ is the starting symbol on the stack}
$$

$\delta$ can be defined as follows:
first we read $w\in L$ and add two stack symbols for each letter read. Also we put the special symbol $B$ which we will need later:
$$
\delta((q_i,q_j,0),\sigma, S)=((\delta_1(q_i, \sigma), q_j, 0), AABS)\\
\delta((q_i,q_j,0),\sigma, A)=((\delta_1(q_i, \sigma), q_j, 0), AAA)
$$
Then we guess the start of $x\in G$:
$$
((q_i,q_j,0),\epsilon, A)=(q_i, q_j, 1), A)
$$
Then we delete symbols off the stack one by one:
$$
\delta((q_i,q_j,1),\sigma, A)=(q_i,(\delta_2(q_j, \sigma), 1), \epsilon)
$$
If there're no more characters to read from $x\in G$ then we should see a $B$ on the stack, which means that $|x|=2\cdot |w|$ and we're in accepting state:
$$
((q_i,q_j,1),\epsilon, B)=(q_i, q_j, 2), \epsilon)
$$
Because a PDA exists for $H$ then $H$ is context-free.

Is my proof good, especially the $\delta$ function?

Let $\sigma$ be the substitution $\sigma(a) = \sigma(b) = \sigma(c) = \{a,b,c\}$, and let $h$ be the homomorphism $h(\sigma) = \sigma\sigma$.

Your language is just
$$
h^{-1}(\sigma(G)) \cap L.
$$
In other words, your language is regular.

You can also see this using a product automaton. Given automata for $L,G$, consider an NFA on $Q_L \times Q_G$, with starting state $(q_{0L},q_{0G})$, accepting states $F_L \times F_G$, and transition function
$$
\delta((q_L,q_G),\sigma) = \{ (\delta_L(q_L,\sigma),\delta_G(q_G,\sigma \tau)) : \tau \in \Sigma \}.
$$


Who are the legislators of Paxos? In the seminal distributed systems paper The Part Time Parliament (the Paxos protocol), Leslie Lamport names fictional legislators who are involved in the Paxon parliament protocol.

According to this writing, he notes that:

  I gave the Greek legislators the names of computer scientists working in the field, transliterated with Guibas's help into a bogus Greek dialect.

Does anyone have any information on the scientists that the legislators are named after? A list of the legislators in the paper and the corresponding computer scientists would be the ideal answer.

I think the first legislator mentioned in the paper, "Λινχ∂", is named after Nancy Lynch since it could be pronounced as "Linch". Also, "Λεωνίδας Γκίμπας" from the bibliography is Leo Guibas. I'm completely lost as to who the others are.

This is an educated guess of the transliterated names I could find in the Paxos paper. Most of these are people mentioned in the paper's references.

Λ˘ινχ∂: Lynch, N. - Legislator
Φισ∂ερ: Fischer, M. J. - Legislator
Tωυεγ: Toueg, S. - Legislator
Ωκι: Oki, B. M. - Legislator
∆ωλεφ: Dolev, D. - Farmer
Σκεεν: Skeen, M. D. - Merchant
Στωκµε˘ιρ: Stockmeyer, L. - Legislator
Στρωνγ: (Strong/Strang?) - Legislator
∆φωρκ: Dwork, C. - President
∆˘ικστρα: Dijkstra, E. W. - Cheese inspector
Γωυδα: (Gouda) - Cheese inspector
Φρανσεζ: Francez, N. - Wine taster
Πνυeλ˘ι: Pnueli, A. - Wine taster
Σ∂ν˘ιδερ: Schneider, F. B. - Citizen
Γρεες: (Greece) - Citizen
Λαµπσων: Lampson, B. - General
Λισκωφ: Liskov, B. H. - Merchant
Παρνας: Parnas, D. - Elder statesman
Γρα˘ι: Gray, C. G. - Priest
Λινσε˘ι: Lindsey, B. G. - Priest


Are algorithms for searching text vs searching numbers fundamentally different? I face this problem a lot while searching phone numbers and bank account numbers, when I do remember it partially.

I save a draft in gmail with the content I am mango. Then I search it, by entering just mango and it gets me to the draft.

But when I save a draft with some number such as 123987645 and try to search by entering 12398764 i.e just one character missing I fail to find it. Also I failed when I just typed  87645.

Out of curiosity I am asking are the algorithms for finding numbers and text fundamentally different? Or I am missing something?

There is no reason to assume that numbers and words are treated differently: for their servers, both are just strings. Different behaviour would be extra work and I don't see why that would be useful here.

There is one possible explanation for the behaviour you see: maybe they don't search for parts of words!

It is easy to preprocess texts so that finding whole words is fast. Well, looking for any substring is not that much slower (cf suffix trees) but it generates more data to store. Given the amount of data Google deals with, they might have a numbered dictionary and save tuples like (msg_id, position, word_id) (or similar)¹. Storing (matches for) all substrings would cause this data set to explode! (And don't even think about approximate search!)

You can try and verify this by searching not for mango but for ngo -- does it still find your message?

I'm quite sure Google does something far more clever.


Is there a flaw in this Wikipedia proof of cycle property of Minimum Spanning Tree? On wikipedia, there is a proof for the cycle property of the Minimum Spanning Tree as follows:

  Cycle Property:
  For any cycle C in the graph, if the weight of an edge e of C is
  larger than the weights of all other edges of C, then this edge cannot
  belong to an MST.

  Proof: Assume the contrary, i.e. that e belongs to an MST T1. Then
  deleting e will break T1 into two subtrees with the two ends of e in
  different subtrees. The remainder of C reconnects the subtrees, hence
  there is an edge f of C with ends in different subtrees, i.e., it
  reconnects the subtrees into a tree T2 with weight less than that of
  T1, because the weight of f is less than the weight of e.

Why does the proof assume that e belongs to MST? If e belongs to a cycle, and it belongs to MST, doesn't it immediately imply that the MST has a cycle and therefore is not a tree?

Please show me why I am not understanding this proof correctly.
i.e. How can we have an edge e already in the tree but the tree remains acyclic?

First off to answer your main question: there is no flaw in the proof.

The point where you are not following the reasoning of the proof is that:

E belongs to a cycle in the graph and to the MST.
Not every other edge of the cycle are in the MST.

If you look at your drawing, then either one of the edges towards the rest of the MST is redundant. Because not all edges of the cycle are in the graph results in that if you remove E you get two subtrees.

To answer your question about why the proof begins with assuming that e belongs to the MST: Proof by contradiction starts with assuming the opposite of what you are trying to proof. Then you reason with that assumption until you run into a contradiction.
A contradiction means that your assumption must be false. If you assumption is false, then the opposite of your assumption is true.

If you just look for images and MST examples there are enough examples with a cycle. Try to follow the reasoning of the proof and you will see why it is sound.


How do you find set of keywords present in set of words in linear time or log time? I am trying to optimize a program, where I need to know whether a given set of keywords present in the set of words. I believe using the dictionary is the only way to optimize it. Any other technique so that I can get better time complexity? The below python script is my version of the code, this works for a small sentence with a time complexity O(len(keywords)) +  O(frequency_table CONSTRUCTION TIME).
Space complexity is not a problem, but time.
def cover_test(keys, sentence):
    frequency_table = collections.Counter(sentence)
    count = 0
    for key in keys:
        if key in frequency_table:
            count += 1
    return count == len(keys)

cover_test("word1 word4".split(), "word2 word1 word3 word4".split())
# output
# True, because word1 and word4 is present in the sentense

examples of input

Set of words
['apple', 'green', 'horse', 'ink', 'ball', 'cat', 'dog', 'elephant', 'fun']
Set of keywords
['fun, 'green']

Output for the above input is True
Update: More clarifications:
The goal is to ensure that every word from the keys list is included in the sentence list, in linear or less time complexity.

I'm interpreting your question as wanting to quickly ensure that every word from the keys list is included in the sentence list.

Assuming you're using a sane version of python, the running time for the initial construction of the counter object is linear in the length of the sentence's description. At least as long as no word appears so many times that the integer stored in the counter exceeds INT_MAX.

So the overall running time, for sane inputs, is linear in the input, which is the best you can possibly expect (since Python has to read the entire input anyway, which takes linear time already).

That said, there's no compelling reason to use a counter here. You could just as easily have used a Set object and achieved the same running time without the assumption on word counts not exceeding a certain value. It might also be easier to read.

For example

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    for key in keys:
        if key not in sentence_word_set:
            return False
    return True

or even

def cover_test(keys, sentence):
    sentence_word_set = set(sentence)
    return all(i in sentence_word_set for i in keys)

Set construction is promised to be expected linear-time in the size of sentence, with expected constant-time lookups. And the for loop goes through each key once (totalling to something linear in the size of keys) so the running time is expected linear in the whole input. Which again is the best you can do.


Partition overlapping polygons On the following picture, we have overlapping polygons: we know the positions of vertices and the edges for each polygons, and the intersections are exactly known (vertices at the intersection are represented on the figure). Is it possible to 'partition' the domain spanned by the union of these polygons into 'disjoint' polygons (with contacts only at the boundary)? To be more precise, I'd like to associate to all edges the surfaces for which the edge is contained in its boundary.

Please advise if I'm not clear enough and thanks in advance for any suggestions!

First algorithm that came into my mind:

P = initial set of polygons
for every pair (p,q) of polygons in P
  if p intersects q
    remove p and q and insert the three polygons that make up p union q
repeat until P can't be grown anymore

If vertices have integer coordinates. You can use a matrix $M$ (initially $0$) and use the following algorithm:

for every polygon
  for every point p = (x,y) in the polygon
    M[y,x] += 1

A disjoint polygon is then a contiguous sub-area of the matrix. The entries in the sub-area are all equal.

One way to speed up the first algorithm is first to compute AABB's for each of the polygons and use a quadtree or some BSP data structure.


Why does quantum cost on gates formed from specific qubit gates not factor swap gates into account? I've been reading a number of quantum computation research papers that claim quantum cost's that do not add up.

For instance, in this paper - there is a claim that the MTSG gate is a quantum cost of 6. But to actually perform the computation, you need swap gates to get the stuff into the right order!

For instance, to even perform the first gate V(B, D), you'll need to do the following:

1) U = TENSOR(ID, SWAP, ID)
 2) U = TENSOR(ID, ID, VGATE)
 3) APPLY (U, R)
 4) SWAP BACK

Am I getting something wrong here?

The paper just uses the swaps to make the diagram simpler. It allows the authors to represent the relevant operation as a single box covering four wires, instead of the six underlying operations, when making larger circuits.

Here is a screen capture of the definition of the "MTSG" gate from the paper (note: the $V$ gate is just a square-root-of-NOT gate):

(They managed to make them look pretty terrible...)

And here's a place where it's used:

If you expand each MTSG box in that larger circuit into the underlying 6 operations, and align the diagram onto a fixed set of wires, you'll find you can easily slide any implied swap gates out of the circuit.

(But do keep in mind that it's possible that the first practical quantum computers will have limitations like 'only nearest neighbors in a 2d grid can interact'. That would force the use of many swap gates.)


Are there undecidable properties of non-turing-complete automata? Are there undecidable properties of linear bounded automata (avoiding the empty set language trick)? What about for a deterministic finite automaton? (put aside intractability).

I would like to get an example (if possible) of an undecidable problem that is defined without using Turing machines explicitly.

Is Turing completeness of a model necessary to support uncomputable problems?

Undecidable problems about context free grammars, and hence, pushdown acceptors as well, which are restricted TMs from Wikipedia...

Given a CFG, does it generate the language of all strings over the alphabet of terminal symbols used in its rules?
Given two CFGs, do they generate the same language?
Given two CFGs, can the first generate all strings that the second can generate?

There are many others about CFGs/PDAs as well as CSGs/LBAs and many other "simpler than TM" models.


Asymptotic bounds on number of 3SAT formulas with unique solutions A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if there is a sparse NP-complete set (under Karp reduction).

I would like to find the density of uniquely satisfiable 3SAT formulas. Is it super-polynomially dense or exponentially dense? What is known about the asymptotic lower bound on the number of 3SAT formulas with unique solutions?

It is dense, just as one would expect.

The number of uniquely satisfiable 3SAT formulas with $n$ variables and $n$ clauses is at least $2^n$, since for every possible assignment to the $n$ variables there is at least one 3SAT formula $\phi$ for which that is the satisfying assignment, and there are $2^n$ such assignments.  A 3SAT instance with $n$ variables and $n$ clauses can be represented as a string of length $\ell = 3n \lg n$.  Therefore, the number of such formulas is exponential in $\ell$.


Bits needed to send parameters of perfect hash functions Suppose that there is a server that has $n$ files. The server is used to construct a perfect hash function for those files and then the computed parameters will be sent to a user. These parameters will be used by the user to compute the hash of a certain file in order to find its position between files on the main server. The question is that how many bits are needed to be transmitted between the server and the user? Is that in order of $O(n)$?
Can anybody suggest a specific algorithm with its parameters and communication cost?

If I understand you correctly, the following is the case:

The server has $n$ files in some order $f_1, f_2, \dots, f_n$.
The user also has exactly one of those files, $f_u$, but does not know $u$.
The user and server agree on some protocol beforehand, which does not depend on any of the $f$.
The server gets to communicate some bits of information to the user once, and only in this direction.
From this information the user must be able to find integer $k$ such that $f_k = f_u$.

Based on the above I would choose some strong cryptographic hashing function $H$, and use it to hash all files on the server. Take the $k$-bit prefix of this hash such that all prefixes are unique. Send these in the correct order for $O(kn)$ total complexity.
How big does $k$ need to be in practice? The chance that the first hash is not a duplicate is $1$, the second $1- \frac{1}{2^k}$ chance, the third $1- \frac{2}{2^k}$, etc. We find that none are duplicates as $\prod_{i=0}^{n-1} (1 - i/2^k) \approx e^{-n^2/2^{k+1}}$ by the Birthday paradox. Let's say we're okay with constant chance of failure $\epsilon$, and thus we want $e^{-n^2/2^{k+1}} > 1-\epsilon$, which gives $k \in O(\log(n))$.
Thus our solution uses $O(n \log n)$ bits. You can't beat this (asymptotically) either, because a full permutation worth of information needs to be transferred, which takes $O(\log n!) = O(n \log n)$ bits.


Class C can have _______ 1s with the remaining bits 0s A subnet mask in class C can have _______ 1s with the remaining bits 0s.

MyApproach:

Class C subnet is 255.255.255.0.So, accordingly it has 9 1s on first byte,9 1s on second byte and 9 1s on third byte.etcSo total 27 1s but the Ans is 25

@Edit

For 255 it has 8 1s on first byte,8 1s on second and 8 1s  on third.=24 How 25?

  Can anyone guide What I am doing wrong?

Check again your count of how many 1's are in the binary representation of 255.  Beyond that, there's nothing wrong with your reasoning.  The answer "25" is wrong.

Some examples are available in Wikipedia: https://en.wikipedia.org/wiki/Subnetwork


The role of asymptotic notation in $e^x=1++Θ(^2)$? I'm reading CLRS and there is the following:

  When x→0, the approximation of $e^x$ by $1+x$ is
  quite good:
  $$e^x=1++Θ(^2)$$

I suppose I understand what means this equation from math perspective and, also, there is an answer in another cs question. But I don't understand some things, so have a few questions.

Why do they use $Θ$ here and why do they use $=$ sign?
Is it possible to explain how the notation here is related to the author's conclusion that $e^x$ is very close to $1 + x$ when $x \rightarrow 0 $?
Also, how is it important here that $x$ tends to $0$ rather than to
$\infty$ as we usually use asymptotic notations?

I'm sorry if there are a lot of questions and if they are stupid, I'm just trying to master this topic.

What the equation means is that there exist constant $A>0$ and $B,C$ such that
$$
|x| \leq A \Longrightarrow Bx^2 \leq e^x-1-x \leq Cx^2.
$$
In particular, for small $x$, $e^x$ is very close to $1+x$, since the error is only $O(x^2)$ (when $x$ is small, $x^2$ is much smaller than $x$).

The same estimate doesn't hold for large $x$ — indeed, $e^x$ grows faster than $x^2$, indeed faster than any fixed power of $x$. So the quoted estimate only holds for small $x$.

Here is a graphic example. Below is the plot of $\frac{e^x-1-x}{x^2}$ for $|x| \leq 0.1$. You can see that it is very close to $0.5$. This is consistent with the Taylor expansion of $e^x$, which is $1 + x + x^2/2 + O(x^3)$.

In contrast, here is the same plot for $10 \leq x \leq 20$. You can see that the ratio shoots up to infinity.

Credit: plots executed using Desmos.


An oracle to separate NP from coNP How to prove that $\mathsf{NP}^A \neq \mathsf{coNP}^A$ ? I am just looking for a such oracle TM $M$ and a recursive language $L(M) = L$ for which this holds.

I know the proof where you show that there is an oracle $A$ such that $\mathsf{P}^A \neq \mathsf{NP}^A$ and an oracle $A$ such that $\mathsf{P}^A = \mathsf{NP}^A$. I have a hint that I should find such oracle $A$ by extending the proof of $\mathsf{P}^A \neq \mathsf{NP}^A$ but wherever I search and read, it is "obvious" or "straightforward" everywhere but I just do not see how prove it at all.

As Max said the modification is not difficult, I suggest that you do not read the rest of this answer and think about the problem a little bit more, there is only one part that needs modification and remembering the definition of when a $\mathsf{coNP}$ machine accepts will help you fix that part.

I will explain the required modification below, but first let's have a brief view at the original proof.

In the original proof $A=\bigcup_n A_n$ is built in steps where at step $i$ with make sure that $i$th machine in $\mathsf{P}$, $M_i$, doesn't decide the language $\{x \mid \exists y\in A \ |x|=|y| \}$ correctly. Note that the set is in $\mathsf{NP}^A$.

We achieve this by simulating $M_i$ using the part of $A$ we have built on a $0^m$ where $m$ is large enough (the string is longer than strings considered in previous steps). $M_i$ accepts, we don't add anything, if it rejects we add a string of length $m$ that $M_i$ doesn't make a query to the set (Such a string exists since there are exponentially many strings of length $m$ but $M_i$ cannot ask about all of them in polynomial time). We will not modify this part of $A$ in future steps (i.e. strings of length $m$ or less will stay the same). This makes sure that $M_i^A$ will not decide the language correctly and completes the proof.

   Now, assume that the machines $M_i$ were in $\mathsf{coNP}$ in place of $\mathsf{P}$. We need to modify the proof to make sure that $M_i^A$ will not recognize $L$. If it is accepting we keep $A$ as before and everything works fine as in the original proof. If it rejects, we need to add a string to the set to make sure it doesn't answer correctly. We still can simulate $M_i$ with the part of $A$ we have, the problem is that $M_i$ might query all strings of length $n$. Here the way a $\mathsf{coNP}$ machine works becomes important. It accepts if and only if all computation paths accept. Since it is rejecting in this case, there is a computation path that is rejecting. As long as we keep this path intact everything will work, so we only need to keep the answers to the queries in that path the same. The number of queries in this path is polynomial (since the machine runs in polynomial time), so there are strings of length $m$ that the path doesn't query about, just add one of them to $A$ and the rest of the proof works as before.

The steps are algorithmic, so the set $A$ is recursive (the essential part of the construction is being able to simulate machines which can be done in say $\mathsf{DSpace}(n^{\omega(1)})$).


Expectation for the number of leaf nodes in a randomized tree construction Consider this procedure for building a tree from $v_1, v_2, ..., v_n$:

insert $v_1$
insert $v_2$ and connect it to $v_1$ via a directional edge from $v_2$ to $v_1$
insert $v_3$ and with a uniform probabiliy connect it to $v_1$ or $v_2$
...
insert $v_n$ and with a uniform porability connect it to $v_1$ or $v_2$,... $v_{n-1}$

The question is what is the expectation for the number of leaf nodes?

I tried to define a random variable $x_i$ for a node $i$, which is $1$ if it is a leaf node and $0$ otherwise.

Then, I must find $$E(X) = \sum_i E(x_i)$$.

If $A_{ij}$ shows the event that the node $j$ is connected to the node $i$, then I must have $\bar A_{ij}$, and then $Pr[x_i = 1] = Pr[\bar A_{ii+1}].Pr[\bar A_{ii+2} | \bar A_{ii+1}]....$

$j$ must be bigger than $i$, pointing to the nodes that arrive after the node $i$. Let $j$ be $i+1$.

$$Pr[A_{ij}] = \frac{1}{j-1}$$ so $$Pr[\bar A_{ij}] = 1- \frac{1}{j-1} = \frac{j-2}{j-1}$$

The reason is that when the node $j$ arrives there are $j-1$ nodes to be attached to. Similarly:

$$Pr[\bar A_{ij+1} | \bar A_{ij}] = 1 - \frac{1}{j} = \frac{j-1}{j}$$

so

$$Pr[\bar A_{in} | \bar A_{ij} \cap \bar A_{ij+1} ... \cap \bar A_{in-1} ] = 1- \frac{1}{n-1} = \frac{n-2}{n-1}$$

So, let's multiply them to each other:

$$ Pr[x_i = 1] = \frac{j-2}{j-1} . \frac{j-1}{j} .. \frac{n-2}{n-1} $$

Since the product is telescopic, we have:

$$ Pr[x_i = 1] = \frac{j-2}{n-1} $$

By replacing $j$ with $i+1$:

$$  E(x_i) = Pr[x_i = 1] = \frac{i-1}{n-1}$$

So
$$ E(X) = \sum_{i=1}^{n}E(x_i) = \sum_{i=1}^{n}\frac{i-1}{n-1} = \frac{1}{n-1}\frac{n(n-1)}{2} = \frac{n}{2}$$


Etymology of time and space "complexity" The word choice of "complexity" in analysis of algorithms to describe temporal and spatial resource requirements has always struct me as an odd one. These are certainly useful and meaningful concepts. This question is concerned with the language used to describe them.

Colloquially, one would probably not say that insertion sort is more "complex" than radix sort.

Is the origin and rationale of this word choice known? If so, what is it?

Complexity refers to the complexity of the computation rather than the complexity of the algorithm. For example, Ritchie's Classes of predictably computable functions from 1963 "[studies] a sequence of classes of computable
functions for which a prediction of the complexity of the calculation may be
made in a comparatively simple fashion."

Hartmanis and Stearns, in their seminal 1965 paper On the computational complexity of algorithms, also use complexity in a similar sense: "One finds, however, that some computable sequences are very easy
to compute whereas other computable sequences seem to have an inherent
complexity that makes them difficult to compute." This paper is the source of the terminology, though they cite earlier papers (like Ritchie's from 1963) which had already used complexity in this sense.


about scheduling in operation system In FIFO: when process get cpu time and then go to IO.
What happend in the time it is in IO? another process can run?
After finishing IO it continue or "loss its turn"?
Why FIFO give priority to cpu bound process?
In RR: assume slice time is s and after (s-2) for eample it get IO, what happend with the 2 other seconds? it loss them?

3.In preemptive SJF we look on the next cpu burst. What about non preemptive SJF? we lock on all the cpu in the process will need?And in genreal we look only on cpu? not on io?

Each program in the system is in one of three states: running (currently using the cpu), waiting (for i/o), or ready (not waiting for i/o, but not currently using the cpu).  When discussing scheduling disciplines jobs are not programs, rather each burst of cpu usage  between i/o requests in a program is a job.

First-in-first-out (FIFO), round-robin (RR) and shortest job first (SJF) are scheduling disciplines for choosing the next job to run from the ready queue of the operating system.  So in all three cases the jobs under discussion correspond to the set of processes that are currently in the ready state.

In FIFO as each job reaches the head of the queue it gets the cpu, when the job requests i/o then it is done.  The process (not the job) enters state waiting.  When the i/o is done the process is moved from state waiting to state ready, and the job corresponding to its next burst of cpu is put on the back of the FIFO queue.

A cpu bound process is one where the average cpu bursts (the jobs) are much longer than the average time spent waiting for each i/o.  Since FIFO is non-preemptive when a long cpu-burst gets to the head of the queue and starts running, all of the ready processes in the queue behind that job are stuck.

In round-robin we are also referring to jobs, not processes.  When a job requests i/o it is done.  When the process goes from waiting to ready the next job (cpu burst) from that process joins the round-robin queue.

Non-preemptive shortest job first is only practical if you really have future knowledge about exactly how long the jobs are.  If some jobs are taking longer than you expected and you aren't preempting them, then you're not really running the shortest one first.

In general scheduling disciplines are only looking at the jobs in the ready queue.  One of the points of SJF, though, is to make sure that the i/o system is kept as busy as possible.  Jobs usually end with an i/o request, so by scheduling the shortest job first you are getting to the next i/o request the soonest.

This insight about shortest job first is what is behind the multi-level feedback queue scheduling used in most modern operating systems: you are using past behavior to predict future job lengths, and then scheduling (expected) shortest job first (but preempting the job if it goes much beyond its expected length.)  The classic paper is Corbató, F. J., M. M. Daggett, and R. C. Daley, “An experimental time-sharing system”, AFIPS Conference Proceedings, Vol. 21, pp. 335-344, 1962.


Why can no task have a utilization rate greater than one? Let $C_i$ be the execution time for task i, $T_i$ be the task period and utilization rate $U = \frac{C_i}{T_i}$

  Then $U$ must be less or equal to $1$ for the task to be schedulable

  Proof:

  Let $\hat T$ be the lcm of task $T_1,...T_n$ i.e. $\hat T = \prod_i
> T_i$. Define $\hat L_i = \hat T/T_i$ the number of times the task is
  run. Then the total number of execution is $\sum_i C_i/\hat L_i = \sum_i \frac{C_i \hat T} {T_i}$. Suppose utilization rate $U >1$, then
  $\sum_i \frac{C_i \hat T} {T_i} > \hat T$ which is impossible. End of
  proof.

I am confused about several things in the proof.

First, what is the physical quantity representing the product or lcm of all the task periods $T_i$? It would make more sense if it was the sum of all the $T_i$ which represents the total task period.

Second, $\sum_i C_i/\hat L_i$ represents the total time spent on execution, I do not get how if this time is larger than $\hat T$, then the tasks would not be schedulable. This goes back to my misunderstanding of what $\hat T$ is.

Can anyone help?

It appears that you have a periodic scheduling system on a single processor where task $i$ must run for $C_i$ seconds out of every $T_i$.

If this is the case, then the requirement that $\tfrac{C_i}{T_i}\le1$ is just saying that $C_i\le T_i$, i.e., you're not saying something like "Task 3 must run for 15 seconds out of every 10 seconds", which is physically impossible.

It looks like there's actually a mistake in the statement of the theorem. I think it should say that the utilization of task $i$ is given by $U_i=\tfrac{C_i}{T_i}$, then define the total utilization to be $U = \sum_{i=1}^n U_i$ and then require the stronger condition that this $U$ satisfies $U\leq 1$. That is, you don't just require each task individually to use at most 100% of your resources: you require the whole ensemble to use at most 100%. You can think of it this way: if I'm supposed to spend $p_1\%$ of my time on task 1, ..., and $p_n\%$ of my time on task $n$, I'd better not be committing more than 100% of my time!

The physical significant of defining $\hat{T} = \mathrm{lcm}(T_1, \dots, T_n)$ is that it's the shortest period of time in which every task is supposed to run an integer number of times. It's not essential that you consider the shortest such period: the proof would work fine if you used any period in which every task needs to run an integer number of times. Perhaps it would be conceptually easier to set $\hat{T} = \prod_{i=1}^n T_i$ instead.


KMP - longest palindromic prefix I wanted to ask if there is a way to use KMP (Knuth-Morris-Pratt) algorithm to find the longest palindromic prefix of a word.

I've seen this algorithm used for determining if a word is rotation of the other for example. We can concatenate first word with itself and look for a pattern which would be the second word (and if found, the answer is yes). But I cannot imagine how could I use KMP for my problem. I am not sure what would the pattern be etc. Can it also be done in linear time using KMP? Thank you.

KMP algorithm is able to solve your problem. Suppose your input string can be represented as $S=AB$ where $A$ is a palindrome ($B$ can be an empty string). Now reverse $S$ we can get $S'=B'A$. consider the string $T=S*S'=AB*B'A$ where '*' is a character which doesn't appear in $S$.

As we can see, $A$ is a border of $T$. Conversely, if $X$ is a border of $T$, then $X$ is a palindrome and thus a palindromic prefix of $S$. So the answer of your problem is the longest border of $T$, which directly corresponds to the last item of "fail" array in KMP algorithm.

In fact, in order to obtain the longest palindromic prefix of a word, you can use some general methods such as Manacher's algorithm, which is the best choice in dealing palindromes.

Manacher's algorithm can find the longest palindromic substring for every palindromic center in linear time. For example, if the input string is "abbabbba", then the algorithm can give you the following results (every digit corresponds to a length of palindromic substring centered in its position):

a b b a b b b a
101410501252101

Manacher's algorithm can solve your problem easily. After getting the longest palindromic substring for every palindromic center, you can simply check for every palindromic center, whether the longest palindromic substring touches the left first character. Consequently, the whole algorithm can be done in $O(|s|)$, where $s$ is the input string.


How can you determine what set of boxes will maximize nesting? I'm trying to find a dynamic solution to the nesting boxes problem.

You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can be nested inside of each other.

So more formally,

Given set B = {b_1, b_2, . . . b_n} where each b_i contains a box with a width, height and depth.

Find the set of boxes that will allow you to nest as many as possible together.

Let $\le_B$ denote the inclusion relation between boxes, i.e. $b_i\le_B b_j$ if we can put the box $b_i$ inside $b_j$. Obviously $\le_B$ is a partial ordering of $B=\left\{b_1,...,b_n\right\}$.

Your question translates to finding the maximal linearly ordered subset of $B$ relative to $\le_B$. A linearly ordered subset is a path in the acyclic directed graph $G$ representing $\le_B$, i.e. $V_G=B$ and $(b_i,b_j)\in E_G\iff b_i\le_B b_j$. We can now reduce your problem into finding the longest path in the DAG $G$. This can be done in linear time with topological sorting. Overall, the time consuming part is constructing $G$, which requires $O(n^2)$ time.


Does quicksort for increasing order work faster if the input set is more decreasing sorted? In CLRS's Introduction to Algorithms,

  The following procedure implements quicksort:

QUICKSORT(A; p; r)
1 if p < r
2 q D PARTITION(A; p; r)
3 QUICKSORT(A; p; q-1)
4 QUICKSORT(A; q+1; r)

  To sort an entire array A, the initial call is QUICKSORT(A; 1;
  A.length).   The key to the algorithm is the PARTITION procedure,
  which rearranges the subarray A[p..r] in place.

PARTITION(A; p; r)
1 x = A[r]
2 i = p - 1
3 for j = p to r - 1
4     if A[j] <=   x
5         i = i + 1
6         exchange A[i] with A[j]
7 exchange A[i+1]  with A[r]
8 return i +1

The quicksort algorithm sorts a set in increasing order, where the pivot is chosen to be the last element in the current array.

I am trying to figure out the worse case and best case to the algorithm.

But I am more interested in whether quicksort will be faster, if the input set is originally more close to the final sorted result. In the concern, I guess the choice of pivot may not matters.

After some thought, the following questions make me think that quicksort will be slower if the input set is more close to the final sorted result.

Is it correct that

when the input set is already in decreasing order, the assignments and exchanges in the for loop in PARTITION will be skipped?
Does quicksort work faster when the input set is already more sorted in decreasing order?

Thanks.

First, this is not the Quicksort that we all know and love, but some rather strange version of it, so your results cannot be applied to what is usually called Quicksort.

If the array is already in descending order, your version (unlike the original Quicksort) will not do any exchanges in the first partitioning. So the partitioning will be fast. However, it makes practically no progress; only one element is moved to its right position, and you will have about $n^2 / 2$ comparisons in total, which is about the worst case possible.

An array in ascending order is even worse, since you will do $n^2/2$ comparisons, plus $n^2/2 exchange operations.


Is the reverse of a closed under operation maintainable? I'm looking at the following question from this handout:

  The class of decidable languages is closed under union

My question is, does this hold in reverse? Is there a phrase for this?
Basically, if $L_1 ∪ L_2$ is decidable would $L_1$ and $L_2$ be decidable as well?

I believe it does, by making one machine $M$ to emulate both on any given input string and have the following:

Save a copy of input somewhere (multitape)
Run M1
    If it accepts, accept
Reset the tape using copy
Run M2
    If it accepts, accept
Both machines have rejected, so reject

Does this work? If so, would this also apply in the case of intersection as well?

No, if $L_1\cup L_2$ is decidable $L_1$ and $L_2$ are not necessarily decidable.

Here's an example.

$$\begin{align}
L_1 &= \text{any language that is not decidable.}\\
L_2 &= \Sigma^*\setminus L_1.
\end{align}$$
$L_1\cup L_2$ is $\Sigma^*$, which is decidable. However, $L_1$ is not decidable. In fact, $L_2$ is not decidable, either.

The proof given in the preformatted block of the question is a proof for the original proposition, "if $L_1$ and $L_2$ are decidable,  then $L_1\cup L_2$ is decidable". It is not a proof for its converse proposition.

To prove its converse proposition, all you can assume is a Turing machines that decides $L_1\cup L_2$. There is no way that you can construct a Turing machine that can decide $L_1$ from that machine.

Intuitively, one condition cannot imply two other conditions. That is, "$L_1 \cup L_2$ is decidable" cannot imply both "$L_1$ is decidable" and "$L_2$ is decidable"

Here are a few related exercises.

Exercise 1. Does $L_1 \cup L_2$ is regular imply $L_1$ is regular and $L_2$ is regular?

Exercise 2. Does $L_1 \cup L_2$ is context-free imply $L_1$ is context-free and $L_2$ is context-free?

Exercise 3. Does $L_1 \cup L_2$ is recursively enumerable imply $L_1$ is recursively enumerable and $L_2$ is recursively enumerable?

Exercise 4. Raise a question similar to the above question.

Exercise 5. If you know that $L_1\cup L_2$ and $L_1$ are both decidable, does that imply $L_2$ is decidable?

The case with intersection is the same. Please check question if $L_1$ and $L_2$ are languages over the same alphabet and $L_1\cup L_2$ is context free, at least one of them must be context free, its answer and its exercises.


Is a matching $M$ maximum iff the graph doesn't have an augmenting path wrt $M$? Berge's theorem: a matching $M$ is maximum if and only if the graph doesn't have an augmenting path with respect to $M$.

I don't understand this theorem. For instance the following matching is maximum but has an augmenting path, doesn't it?

The matching $M$ is in gold here and the augmenting path is the one in dotted lines.

An augmenting path must alternate between gold and black, starting and ending with black edges. In this way, if you replace the gold edges with the black edges, you obtain a larger matching. This argument shows that a matching can only be maximum if there is no augmenting path, and Berge's theorem states the inverse direction: if a matching has no augmenting path then it is maximum.


Second order function formalization I need to work on a optimizer for a language whose operator are second order functions.

They are the well known ones filter, map, reduce, fold, foreach etc. etc.

I need to formalize as much as possible the language. I mean I would like to have at the end a description such this:

"Filter is function from this domain to that codomain, it has this and that properties, under some condition also this property holds"

Can you suggest me some publication/book where this work has been (at least partially) done?

You may not be able to completely specify formally in a tractable way
the semantics of your functions, depending on what they are. But doing
some of the work, even incompletely may help you significantly with
optimizing your programs, since it may be enough to establish whatever
properties are needed for optimization.

The first thing you want to do is to type your functions. For this,
you probably want some kind of polymorphic typing (see ML or CAML),
using type variables, as some of the base types you operate on will be
left open.

Most of these function take several arguments, and (following the
discussion in comments with @Jake) you may want to consider what would
be a convenient order, and more to the point, whether you want them
curried (or currified) or not.

For example, if we note [a] the type for a list of elements of type
a, then you can define the function map as:

a function of two arguments, the first being a function from a to
b, and the second a list in [a], and returning a list in [b], i.e.
map: (a→b)×[a] →[b]
a function of one argument which is a function from a to
b, and returns a specialized mapping function that maps lists in [a]
to lists in [b], as specified by the argument to map, i.e.
map: (a→b) →([a]→[b])

The latter is a curried version of the former. They give you the
same computing power, but the curried one may be more convenient for
optimization (just my intuition) as it decomposes structures.

Then the kind of information that you may need may depend on the kind
of optimizations you intend to implement. Many types of optimizations
("strength reduction" is a typical example) may require knowing
algebraic properties of your functions. But that may also depend on
the algebraic properties of the types or type constructors used, such
as the existence of "identity element" with respect to some
operations (such as the empty list). I doubt your specification/formalization problem can be restricted to just your second order functions.

Typically, a relation such as:

head (map (f,l))= f(head(l)) may be very useful for some
 optimizations.

or more trivially:

map(f,[]) = [] where [] denote the empty list.

I do not recall all the literature on these issues. But you may want
to look at abstract data types, formal algebras, and the algebraic
techniques used in optimization.

There are probably other properties, less algebraic, that you may be
interested in defining and using.

An important aspect is also whether your function are purely
functional, or whether they have side effects. A map function could
possibly destroy the list given as argument, the result reusing the
same memory locations.


Detecting spoken words in audio stream or file? I am a hobbyist interested in single word recognition. What is the state of research? Where I can get papers or/and software tools regarding that?

Thanks in advance for any advice!

Its a huge field.  Basics are to convert the audio into a spectragraph (a Fourier transform).  That highlights what frequencies are present in the signal and at what intensities.  From this you break up windows (wavelets in some models) and learn to identify the phonemes from these.  Phonemes are the names for the types of sounds you can make with your mouth.  There is a lot biology in this, how air leave your mouth, if your tounge is against the roof of your mouth, behind your teeth etc.  This all affects what frequencies result and subsequently you see those in the spectrograph.  With experience you can read phonemes right off from these graphs.

Phonemes are not letters in a written alphabet, they are an alphabet all their own.  But the work of linguist have decoded what phonemes emerge from pronouncing words.  It is tricky business because unlike written words, when we speak one words phonemes can blend with the start of another.  So detecting single words is actually involved.  You instead start to score the likelihood of a sequence of phonemes and work back to the most probable sequence.  This can be done with hidden Markov models, but the rise of neural nets might be changing what's the best approach here.  But certainly this is the place that becomes language specific.

A final common component is domain and grammar.  Producing text from speech works best if there is an expectation that the words come from a limited domain, such as ordering your pizza or sending text messages.  Again the linguist have to help by providing language models that map spoken language (often quite different from rules of written language) to likely sequences of words.  Pauses and intonation have to provide clues for punctuation.  So there is a lot of training and retraining to do within a domain to get it work.

Of the list of things here about the only one that springs to mind as "go do it yourself" would be to read in an audio stream and produce the spectragraph.  That much is classical signal processing and calculus.  As for phonemes, linguistic, random models, and machine learning... those seem to me to be specialist material.

Well at least this is how it was done in broad strokes years ago when I was peripherally involved.  I'm sure it has advanced but hope this gives some help.


Complexity of the Dijkstra algorithm I'm little confused by computing a time complexity for Dijkstra algorithm. It is said that the complexity is in $O(|V|^2)$ - Wikipedia - Dijkstra, which I understand. It's because for each node, we could theoretically relax edges going to each vertex so it is $n * n$ times, respectively $n(n-1)$.

On the other hand, I can't figure out why this complexity isn't $O(|E|+|V|)$. For each $v \in V$, we relax only those edges $e$, which weren't computed yet. If vertex $v$ is already computed (red on gif above), we don't need to work with it anymore.

So can I say that in one way, it is true that Dijkstra is in $O(|V|)$, but if we can put into the computation number of edges, I can say that it is in $O(|V|+|E|)$?

For each v from V, we relax only those edges e, which werent computed
  yet. If vertex v is already computed (red on gif above), we don't need
  to work with it anymore.

Your are assuming that each edge is visited only once, but this assumption is not quite right. Let's say we have two sets $S$ and $S'$, such that $V=S \cup S'$ and $S$ is the set of vertices, for which we have found the shortest path from source $s$. Each time, we need to find an edge $e=(u,v)$ ($u \in S$ and $v \in S'$) that sits on a shortest path, but how do you find this edge? You need to either

(1) use a brute-force algorithm and spend $O(|V|)$ to look at all edges $e=(u,v)$ ($u \in S$ and $v \in S'$) for finding the minimum one, which takes $O(|V|^2)$ (because each time you are looking at the same edge that are not in the shortest path).

or

(2) use a min-heap and spend $O( \log |V| ) $ for finding that edge, and achieve $O( (|V| + |E|)\cdot \log |V| )$ overall running time.

However, if the graph is unweighted, your assumption is right and you can achieve the running time $O(|V|+|E|)$.


backpropagation algorithm seems to be forcing output values to middle than extremes I have been playing around with artificial neural networks lately, specifically with the prospect of trying to replace the contrastive divergence algorithm with some type of evolutionary metaheuristic technique (i have been working with PSO) to do unsupervised pre-training, but I have come up against some issues when trying to implement the backpropagation algorithm to then fine-tune the connection weights to create a classifier.

I am using a reduced version of the MNIST dataset consisting of just the '0's and '1's to try and develop a binary classifier than is capable of distinguishing between the two different classes.

The output of my network is two visible nodes that are supposed to output [1 0] if the data is classified as a '0' and [0 1] if the data is classified as a '1'

before learning with the backpropagation algorithm i have about a 30% classification error using the quadratic error, and as i perform the supervised learning, the error gets pushed towards 12.5% but stays there as if there was an asymptote.

I thought this was showing that it was improving the classification, however when i examined the output of the network, it was just showing that with each iteration, the activations of the output nodes were moving closer to [0.5 0.5] before settling there.

before backpropagation was applied it was giving output values of [0.75 0.2] (for example) - and any attempts to train it using backpropagation just pushed those values toward [0.5 0.5] rather than amplifying the difference.

can anyone offer any insight as to why this might be happening? is this a common problem when training neural networks? or does it just sound like an implementation bug? i have implemented my backpropagation algorithm in a similar fashion to that which is found here.

I have run into a similar issue when trying to train a neural network with hidden layers for regression.
My network simply learned to always predict the mean of all target values in the training set.

In my case, the problem was missing input normalization (my input data had values in the 100,000s) in combination with sigmoid units:
The easiest way for the network to reduce the loss function (mean squared error) was to simply set the weights in the early layers to very small values and the output unit's bias to the data's mean value.

After that, the network was stuck and no amount of training seemed to change anything, since the absolute gradient values were too small.


How complete directed graph with n-vertices is connected to the n-dimensional simplex and its triangulation? Answer https://stackoverflow.com/a/26151549/1375882 suggests that Sperner's lemma can be used to prove the existence of index for the search Hamiltonian path in complete directed graph. But Sperner's lemma is about simplex, its triangulation and colouring. How such notions can be mapped to the complete graph with n-vertices?

Here is what it boils down to. There are $n$ vertices $v_1,\ldots,v_{n-1},v$. For each $i$, there is an edge either from $v$ to $v_i$ or from $v_i$ to $v$. We need to show that one of the following holds:

There is an edge from $v$ to $v_1$.
There is $i < n-1$ such that there are edges from $v_i$ to $v$ and from $v$ to $v_{i+1}$.
There is an edge from $v_{n-1}$ to $v$.

Let $x_i$ be a Boolean variable denoting that there is an edge from $v$ to $v_i$. Then we need to show that the following DNF is a tautology:
$$
x_1 \lor (\lnot x_1 \land x_2) \lor \cdots \lor (\lnot x_{n-2} \land x_{n-1}) \lor \lnot x_{n-1}.
$$
Hopefully you can manage to prove this yourself. It just states that if we have a string of 0s and 1s, then one of the following must happen:

The string starts with 1.
The string contains 01.
The string ends with 0.

The easiest way to see this is to prove the following:

  If a binary string starts with 0 and ends with 1, it must contain 01.

This is just the trivial one-dimensional case of Sperner's lemma.


Why doesn't everyone use microkernel-based operating systems? From what I have read on operating systems, the impression I have been receiving is that, for at least 30 years, "everybody has known" that microkernel-based operating systems are "better" than monolithic operating systems. And yet, I have a Linux OS at work and am typing these lines on a computer running a Windows OS at home. Moreover, looking at Wikipedia's list of microkernel-based operating systems, it seems most are old and have been discontinued, and none have really broken into the PC space (although FreeRTOS is a player in the embedded space).

Question: Why has no microkernel-based OS broken into the mainsteam? Why is the world still using monolithic OS's 28 years after Tanenbaum-Torvalds? What is the "hard problem" microkernel-based OS's have not been able to solve, and why do people keep trying?

Yes, you use microkernel operating systems. If you use a modern Intel CPU, it includes a copy of Minix which runs on a separate processor that is embedded in the processor that you think you have. Chances are also very good that at least a few of your peripherals use microkernel operating systems internally.

Moreover, you may not use any of these, but a lot of people use macOS, iOS, iPodOS, audioOS, watchOS, and tvOS. They are distinct (though in some cases related) operating systems implemented on top of the Mach microkernel. Or perhaps they use Horizon, the operating system of the Nintendo Switch.

Google seems to be going that way as well, with Zircon. ChromeOS and Android will probably be based on that at some point in the forseeable future.

Having said all that, the way the server world is going these days, especially in cloud computing, is guest operating systems running under hypervisors, which you can think of as related to the microkernel idea.


Why can we not read and write to the same address at the same time? I was reading Wikipedia about the von Neumann bottleneck.

Surely there is some simple answer to this. Why can we not read and write to the same address at the same time? We can if the addresses are different.

In other models (a distributed architecture, for example, with several processors) you can often do concurrent reads, where two or more processors are able to read a word from memory simultaneously. The problem with concurrent writes is more complicated since you have the possibility of a race condition: if one processor wants to write 31 to a memory location and at the same time another processor wants to write 0 to that location, the behavior of the system might not be predictable so running a program twice might result in two different results. Dealing with this problem can be tricky, as you might imagine. That's not to say it can't be handled, only that it's more complicated.


Why does $O(n \log n)$ seem so linear? I've implemented an algorithm, that when analyzed should be running with the time complexity of $O(n \log n)$.

However when plotting the computational time against the cardinality of the input set, it seems somewhat linear and computing $R^2$ confirms this somewhat. When then sanity checking myself by plotting $n$ on the $x$-axis and $n \log_2 n$ on the $y$-axis with python, and plotting this it also seemed linear. Computing $R^2$ (scipy.stats.linregress) further confuses me, as I get $R^2=0.9995811978450471$ when my $x$ and $y$ data is created as so:

for n in range(2, 10000000):
    x.append(n)
    y.append(n * math.log2(n))

Am I missing something fundamental? Am I using too few iterations for it to matter? When looking at the graph at http://bigocheatsheet.com/ it does not seem linear at all.

Just some general observations.

O(n log n) is only an upper bound. If it's not tight, that's your explanation right there.
A Θ(n log n) running time can have many different components, for instance

$\qquad\displaystyle a \cdot n\log n + b \cdot n \log \log n + c \cdot \sqrt n + d \cdot n + e \cdot \log n + d$

While technically the linearithmic term dominates, if $a$ is small compared to the other coefficients you will have a hard time detecting it.
Measuring wall-clock running time is noisy without end, inparticular because the coefficients mentioned above get skewed by platform details. Try investigating counts, for instance of a dominant operation or block.
Linear regresssion always works. Since the "difference" between $n \log n$ and $n$ is rather small (also considering above point), it's not susprising you'd get a high confidence. Run linearithmic regression and compare!


Formal languages: constructing * for a linear set Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem).

Right now, I'm trying to construct the equivalent of *-closure for a linear set. (Once I have this, it's easy to find for semi-linear sets).

More formally:

A linear set is a set of the form $\{ v_0 + c_1 \cdot v_1 + c_n \cdot v_n \mid c_i \in \mathbb{N}\}$. i.e. a linear combination of vectors from $\mathbb{N}^k$.
A semi-linear set is a finite union of linear sets

For a linear set $L$, I'm trying to construct $L^*$, the semi-linear (possibly linear?) set $L^* = \{ u_1 + \ldots + u_m \mid u_i \in L, m \geq 0 \}$, i.e. the infinite sum of L with itself.

I know that this set must be semi-linear, from Parikh's theorem. It basically corresponds to the case where, if $R$ is a regular languages with a linear Parikh image $L$, then $L^*$ is the Parikh image of $R^*$. (From this I know how to build up the case where R has semi-linear Parikh image).

I'm wondering if someone can either point me to a proof that Regular Expressions are semi-linear languages that doesn't rely on Parikh's theorem for context-free languages, or can point me in the right direction for constructing $L^*$ myself.

Hint. It suffices to observe that if $L = \{ v_0 + c_1v_1 + c_nv_n \mid c_1, \dotsm, c_n \in \mathbb{N}\}$, then $L^* = \{ c_0v_0 + c_1v_1 + c_n  v_n \mid c_0, \dotsm, c_n \in \mathbb{N}\}$.


Convex-hull of a star shaped polygon in O(n) I'm trying to develop an algorithm to find a convex hull of a star shaped polygon in $O(n)$ time. The specific problem, which is also described here, is as follows:

A polygon $P$ is star-shaped if there exists a point $p$ in the interior of $P$ that is in the shadow of every point on the boundary of $P$. The set of all such points $p$ is called the kernel of $P$.
Given an $n$-vertex, star-shaped polygon $P$ specified by its vertices in counterclockwise order, how to compute convex hull of this polygon in linear time.

According to these slides (slide $64$), it's really possible to find such a convex hull in linear time using Graham's Scan. This result is given as a corollary. This means that we probably need only the "scan" part of the Graham's Scan algorithm to solve this problem.

Imagine we have the following star-shaped polygon $P$:

and lets pick the point with the lowest $y$ coordinate of $P$, i.e., $p_2''$. If I'm not wrong, start from there, the steps applied would be:

Pick the next vertex, i.e., $p_3''$.

Lets consider the vertex $a$. We check if $p_2''p_3''a$ is a left or right turn, by using the cross product $(p_3'' - p2'') \times (p_3''- a)$. Since it's a left turn, we pick $a$.

We now consider $p_3''ab$. It's also a left turn, so we pick $b$.

We now consider $abc$. We also have a left turn, so we pick $c$.

Consider $bcp_1'$. It's a left turn, so we alsp pick $p_1'$.

$cp_1'p2'$ is a right turn. Thus we need to remove from the stack $p_1'$. Thus, so far we have included the following vertices in the $CH(P) = p_2'', p_3'', a, b, c, p_2'$.

We consider $cp_2'p_3' = cp_2'p_1''$ (just notation). It's a left turn, so we should include $p_3' = p_1''$. $CH(P) = p_2'', p_3'', a, b, c, p_2', p_3'$.

We now consider $p_2'p_3'p_2''$. It's a right turn, so we should remove all points which create a right turn with $p_2''$, i.e. , $p_3' = p_1''$, but also $p_2'$, because of $cp_2'p_2''$. So, now our final $$CH(P) = p_2'', p_3'', a, b, c, p_2''$$

The (literally) Graham's scan seemed to work in this instance, but I would not know for sure if it would work in general.

I tried to think about other ideas to solve this problem, since I was not sure this Graham's scan is correct, but it was mostly because I was not considering as initial point the one with the lowest $y$ coordinate.
If Graham's scan is enough to solve this problem, then the order given of the vertices, as specified in the problem above, must be related to one of the necessary orderings of the vertices required in a usual Graham's scan. I'm talking about sorting the points by polar angle in counter-clockwise around the initial chosen point $p_0$ or about sorting the points according to their $x$ value.

I would appreciate an explanation of the corollary in the slide I'm mentioning above, provided it's really a corollary.

Graham scan for a convex hull works if you have an ordering of points $a_1,a_2,...a_N$ such that you have a sequence $p_1 < p_2 <...< p_k$ where your convex hull is $a_{p_1}, a_{p_2},...,a_{p_k}$ of which it is not possible to have a winding number greater than $1$.

In general for any polygon $P$ this might not work, but for a star shaped polygon, you could observe that from the point $p$ visible to all points, in counter-clockwise order, will be have the aforementioned property.


How can I debug my pseudocode algorithm? The algorithms for the problem I am working on become more and more complex as I try to improve their performance. They already span several pages with cases and sub-cases, and will probably become even longer. I am worried that there might be mistakes that are difficult to notice.

As a programmer, I am used to writing detailed test-cases to test my programs, but the algorithm is written in pseudo-code (it is not easy to implement). What ways can you recommend for testing the algorithm?

This is an excellent question: how do we know that a complex piece of mathematics is correct? The (by now) traditional point of view is that if we succeed in proving something then it must be correct. Unfortunately, this point of view is a tad naive. Indeed, published papers often contain wrong results, and these can remain unnoticed for decades. Some high-brow examples can be found in Voevodsky's talk, and this is a notorious issue especially in cryptography and distributed computing, two fields with extremely complicated definitions and proofs.

The most stunning example, however, must be the gap in the proof of the classification of finite simple groups: the result was announced in 1983, but only in 2004 did Aschbacher and Smith publish two monographs (!) covering one of the cases. In 2008 a further gap was filled by Harada and Solomon who found, quoting Wikipedia, "a case that was accidentally omitted". Should we believe the proof now, then?

Another problem which has seen its share of wrong proofs is the four color theorem. The first two proofs, dating to 1879 (Kempe) and 1880 (Tait), were found wrong in 1890 and 1891, respectively. In 1977 Appel and Haken announced a solution, containing a very length case analysis. It was not surprising, then, that a small error was found around 1986. While the error was corrected, doubts remained. The matter was finally put to rest in in the computerized formal proof by Gonthier et al. (2005), formalizing the earlier "second generation" proof of Robertson, Sanders, Seymour and Thomas from 1996.

What is a computerized formal proof? The idea is that if you had a completely formal proof of each and every statement, then as long as we trust our proof system, then we can be sure that the result is correct. (Unfortunately, as Gödel showed there is no hope in showing that the proof system is consistent, so this is an article of faith.) As Russell and Whitehead exemplified in their Principia Mathematica, writing formal proofs is difficult. Instead, the idea is to use a proof assistant which gets hints and converts them, somehow, to a formal proof which can then be independently checked. There are several of these proof systems around, but the most popular nowadays seems to be Coq.

What if the reviewers don't believe your proof? This is the situation that Thomas Hales found himself in after proving (or so he claims) the Kepler conjecture on sphere packing. The reviewers gave up after spending a year of reviewing, saying that while they were unable to find any mistake, they are not completely certain that the proof is correct. In response, Hales decided to formalize his proof, starting up the Flyspeck project, now in its eleventh year. In a few more years the proof would probably be complete. Clearly this amount of effort is unreasonable for the everyday mathematician.

Can proof assistants be improved? Voevodsky has been developing Homotopy Type Theory, a Coq overlay for algebraic geometry, and claims that he is using it daily to verify his proofs. Last year Gonthier et al. formalized the proof of the Feit–Thompson theorem in group theory in Coq, thus laying the ground for formalized group theory results. Yet even these projects are missing a lot of background which will be needed to formalize research in theoretical computer science. Even after such a framework has been developed, it will still be rather time-consuming to turn the commonplace sloppy TCS proofs into formal attire.

So what are you to do? In your particular case, you are designing an algorithm, so you have the distinct advantage of being able to test your algorithm. (The Curry–Howard correspondence shows that every proof corresponds to an algorithm, but in your case the relation is clearer.) Perhaps there is a trivial algorithm which is very slow, and you could compare it to your algorithm. Or perhaps it is an NP-type problem, in which the solution is easy to verify but hard to find.

Do people actually verify their algorithms usually? I doubt it, unless they are in a field such as computational geometry in which their algorithms are actually being used. What people usually do is do their best to check their proofs, crossing all ts and dotting all is. That means avoiding phrases such as it is easy to see that. Having done that, they kindly ask a few other people to read through their proofs. Then they submit the paper to a journal, and if they're lucky then the referees will do another pass.

Even after all this, mistakes are occasionally found, but this is just part of life. Usually, these mistakes can be corrected easily, demonstrating that our formal sense of certainty is limited: true mathematics "works" even if not completely valid formally, as has been argued by a few philosophers, most of them coming from the ranks of practicing mathematicians. Wrong algorithms point the way to correct algorithms, as they bring new ideas. So don't worry too much, just do your best.


Unambiguous context-free grammar for strings with at least as many a's as b's I have designed this Grammar but it is ambiguous:

$$S\to aSbS \mid bSaS \mid aS \mid\epsilon$$

Would anyone help me make it unambiguous? Assume the alphabet is $\{a,b\}$.

Here is an unambiguous grammar for strings with at least as many $a$'s as $b$'s.  $\def\L#1{{\mathcal L(#1)}}$

$$\begin{align}
S&\to EM\mid E\\
M&\to aDM\mid aD\\
E&\to aBE\mid bAE\mid\epsilon\\
D&\to aBD\mid\epsilon\\
B&\to b\mid aBB\\
A&\to a\mid bAA\\
\end{align}$$

The following table should help us understand the strings generated by each non-terminal.

$$  \text{number of $a$'s minus number of $b$'s} $$

\begin{array}{|c|c|}
\hline
&\text{in the whole string} & \text{in every proper prefix}\\\hline
A&1& \lt 1\\\hline
B&-1&\gt -1\\\hline
D&0&\ge0\\\hline
E&0&\text{no restriction}\\\hline
M&\gt0&\gt0\\\hline
S&\ge0&\text{no restriciton}\\\hline
\end{array}

Some notations. For all string $w$, let $d(w)=|w|_a-|w|_b$, i.e., the number of $a$'s minus the number of $b$'s. Define $d_w:\{1,\cdots, |w|-1\}\to \mathbb N$, $w(i)=d(p_i(w))$, where $p_i(w)$ is the proper prefix of $w$ of length $i$. For example, for $w=abb$, $$\begin{align}d_w(1)&=d(a)=1 - 0=1,\\ d_w(2)&=d(ab)=1-1=0.\end{align}$$

Given a string $w$ and one of its prefixes $p$, let $w-p$ denote $w$ with $p$ removed, i.e. $w = p(w-p)$.

Continuity Lemma. $d(\cdot)$ is continuous in the sense that $d(w)$ changes at most by 1 if $w$ is extended or shrunk by one terminal. $d_w(\cdot)$ is continuous in the sense that $d_w(i)$ changes at most by 1 if $i$ becomes one less or bigger. So we have "intermediate value theorem" for $d(\cdot)$ and $d_w(\cdot)$.

Linearity Lemma. Given two strings $p$ and $w$, we have
$$\begin{align}|w-p|&=|w|-|p|,\\
d_{w-p}(i) &= d_{w}(|p| +i) - d(|p|),\color{#d0d0d0}{\text{ for } i=1,2,\cdots, |w|-1}
\end{align}$$
Proof. By definition. $\blacksquare$

Proposition AB. We have two equivalences,
$$\begin{align}
w\in \L A &\iff d(w) =1\text{ and } d_w \lt 1,\\
w\in \L B &\iff d(w) =-1\text{ and } d_w \gt -1.
\end{align}$$
Proof: By induction on $|w|$, it is straightforward to establish the "$\Rightarrow$" implications.

Let us prove the "$\Leftarrow"$ implications by induction on $|w|$ as well. The base cases when $|w|=1$ are immediate to verify. Suppose $w$ is of greater length.

$d(w) =1\text{ and } d_w \lt 1$. Since $d_w(1)\lt 1$, $w$ starts with $b$, i.e, the first value of $d_w$ is $d(b)=-1$. Since $d(w)=1$, $d(p)=0$ for some proper prefix $p$ of $w$. Let $b\mu$ be the shortest such prefix. Since $d_\mu < 1$, $d(\mu)=d(b\mu)-d(b)=1$, and $\mu$ is shorter than $w$, we have $\mu\in \L A$ by induction hypothesis.

Since $d_w\lt 1$ and $d(a\mu)=0$, $d_{w-b\mu} \lt 1$. Also note $d(w-b\mu)=1-0=1$. Since $w-b\mu$ is shorter than $w$, $w-b\mu\in\L A$ by induction hypothesis. So $w=b\mu(w-b\mu)$ can be generated from $A\to bAA$.
$d(w) = -1\text{ and } d_w \gt -1$. This case is the same as the case above, but with $-1$ and $1$ switched, $>$ and $<$ switched, $a$ and $b$ switched, $A$ and $B$ switched. We obtain that $w$ can be generated from $B\to aBB$. $\blacksquare$

Proposition DE. We have two equivalences,
$$\begin{align}
w\in \L D &\iff d(w)=0\text{ and } d_w \gt 0,\\
w\in \L E &\iff d(w)=0.
\end{align}$$

Proof: By induction on $|w|$, it is straightforward to establish the "$\Rightarrow$" implications.

Let us prove the "$\Leftarrow"$ implications by induction on $|w|$ as well. The base cases when $|w|=0$ are immediate to verify. Suppose $w$ is of greater length.

$d(w)=0$ and $d_w>0$. Since $d_w(1)>0$, $w$ starts with $a$. Let $a\mu$ be the shortest non-empty prefix with $d(a\mu)=0$. Then $d(\mu)=-1$ and $d_{\mu}\gt0$, which means $\mu\in\mathcal L(aB)$. Since $d(a\mu)=0$, have $d_{w-a\mu}\gt0$. Since $d(w-a\mu)=d(w)-d(a\mu)=0$ and $w-a\mu$ is shorter than $w$, $w-a\mu\in\L D$ by induction hypothesis. The rule $E\to aBE$ tells that $w=a\mu(w-a\mu)\in D$.
$d(w)=0$.

$w$ starts with $a$. Let $a\mu$ be the shortest prefix of $w$ such that $d(a\mu)=0$. Then $d(\mu)=-1$ and $d_\mu > -1$, which means $\mu\in \L B$. Since $d(w-a\mu)=d(w)-d(a\mu)=0$ and $w-a\mu$ is shorter than $w$, $w-a\mu\in\mathcal L(E)$ by induction hypothesis. The rule $E\to aBE$ tells that $w=a\mu(w-a\mu)\in E$.
$w$ starts with $b$. This case is the same as the case above, but with $-1$ and $1$ switched, $>$ and $<$ switched, $a$ and $b$ switched, $A$ and $B$ switched. We obtain that $w\in E$. $\blacksquare$

Proposition M. $w\in \L M \iff d_w \ge 1$.
Proof. The "$\Rightarrow$" direction is implied by the proposition above immediately since $M$ becomes multiple $aD$'s.
To prove the "$\Leftarrow$" direction, suppose $d_w\ge1$. Note that $w$ starts with $a$. Let $p$ be the longest prefix of $w$ such that $d(p)=1$, which implies $d_{w-p}\ge1$. Since we also have $d_p\ge1$, $p\in\L U$. If $p=w$, $w$ can be generated from $M\to U$. Otherwise, since $w-p$ has the same restriction as $w$, $w$ can be generated from $M\to UM$. $\blacksquare$.

Proposition S. $w\in \L S \iff d(w) \ge 0.$
Proof. The "$\Rightarrow$" direction is implied by proposition E and proposition M immediately.
 To prove the "$\Leftarrow$" direction, consider a string $w$ with $d(w)\ge0$. If $d(w)=0$, then $\mu\in\L E$. Otherwise, $d(w)>0$. Let $p$ be the longest prefix of $w$ such that $d(p)=0$. Then $p\in\mathcal L(E)$. Consider $w-p$. We must have $d_{w-p}\ge 1$; otherwise, we can extend $p$. So $w-p\in \mathcal L(M)$. $w=p(w-p)$ can be generated by $S\to EM$. $\blacksquare$

Proposition unambiguity. The grammar is unambiguous.
Proof. Given the propositions above that characterize each language involved numerically, it is relative easy to prove as the following.

Let $s\in\L S$.

$d(s)=0$. Then $s$ has to be parsed by $S\to E$.
$d(s)\gt 0$. Then $s$ has to be parsed by $S\to EM$. Suppose $s=e_1m_1=e_2m_2$, where $e_1,e_2\in\L E$ and $m_1, m_2\in\L M$. Since $d_{m_1}>0$, if $m_2$ is a proper suffix of $m_1$, i.e., $m_1-m_2$ is a proper prefix of $m_1$, we would have $d(m_1-m_2)>0$, which contradicts with $d(m_1-m_2)=d(m_1)-d(m_2)=(d(s)-d(e_1))-(d(s)-d(e_2))=0$. This contradiction means $m_1$ cannot be a proper suffix of $m_1$. By symmetry, $m_2$ cannot be a proper suffix of $m_1$, either. Hence, $m_1=m_2$ and $e_1=e_2$.

Let $m\in\L M$.

$\min d_m=1$. Then $m$ has to be parsed by $M\to aD$.
$\min d_m>1$. Then $m$ has to be parsed by $M\to aDM$. Suppose $m=ad_1m_1=ad_2m_2$, where $d_1,d_2\in\L D$ and $m_1, m_2\in\L M$. Since $d_{m_1}>0$, if $m_2$ is a proper suffix of $m_1$, i.e., $m_1-m_2$ is a proper prefix of $m_1$, we would have $d(m_1-m_2)>0$, which contradicts with $d(m_1-m_2)=d(m_1)-d(m_2)=(d(s)-d(ad_1))-(d(s)-d(ad_2))=0$. This contradiction means $m_1$ cannot be a proper suffix of $m_1$. By symmetry, $m_2$ cannot be a proper suffix of $m_1$, either. Hence, $d_1=d_2$ and $m_1=m_2$.

Let $e\in\L E$.

$|e|=0$. Then $e$ has to be parsed by $E\to \epsilon$.
$|e|>0$.

$e$ starts with $a$. Then $e$ has to be parsed by $E\to aBE$. Suppose $e=ab_1e_1=ab_2e_2$, where $b_1,b_2\in\L B$ and $e_1, e_2\in\L E$. Since $d_{b_1}>-1$ and $d(b_2)=-1$, $b_2$ cannot be a proper prefix of $b_1$. By symmetry, $b_1$ cannot be a proper prefix of $b_2$, either. Hence, $b_1=b_2$ and $e_1=e_2$.
$e$ starts with $b$. This case is symmetric to the case above.

Let $w\in\L D$.

$|w|=0$. Then $w$ has to be parsed by $D\to \epsilon$.
$|w|>0$. Then $w$ has to be parsed by $D\to aBD$. Suppose $w=ab_1q_1=ab_2q_2$, where $b_1,b_2\in\L B$ and $d_1, d_2\in\L D$. Since $d_{b_1}>-1$ and $d(b_2)=-1$, $b_2$ cannot be a proper prefix of $b_1$. By symmetry, $b_1$ cannot be a proper prefix of $b_2$, either. Hence, $b_1=b_2$ and $d_1=d_2$.

Let $w\in\L B$.

$|w|=1$. Then $w$ has to be parsed by $B\to b$.
$|w|>1$. Then $w$ has to be parsed by $B\to aBB$. Suppose $w=ab_1b_3=ab_2b_4$, where $b_1,b_2,b_3,b_4\in\L B$. Since $d_{b_1}>-1$ and $d(b_2)=-1$, $b_2$ cannot be a proper prefix of $b_1$. By symmetry, $b_1$ cannot be a proper prefix of $b_2$, either. Hence, $b_1=b_2$ and $b_3=b_4$.

Let $w\in\L A$. This case is symmetric to the case above. $\blacksquare$

Here is a simpler unambiguous grammar given by Yuval.
$$\begin{align}
S&\to SaU \mid X\\
X&\to aUbX\mid bDaX\mid\epsilon\\
D&\to bDaD\mid\epsilon\\
U&\to aUbU\mid\epsilon\\
\end{align}$$

Here is the numerical characterization for the language generated by each terminal. Check his answer for visual explanations.
$$  \text{number of $a$'s minus number of $b$'s} $$
\begin{array}{|c|c|}
\hline
&\text{in the whole string} & \text{in every proper prefix}\\\hline
S&\ge0&\text{no restriciton}\\\hline
X&0&\text{no restriciton}\\\hline
U&0&\ge0\\\hline
D&0&\le0\\\hline
\end{array}