Minimal requirements for Kleene's recursion theorem Kleene's recursion theorem guarantees that any Turing complete language must have quines. However, consider the following quine (in C, taken from the Quine page):

 char*f="char*f=%c%s%c;main()
 {printf(f,34,f,34,10);}%c";
 main(){printf(f,34,f,34,10);}

It makes no use of while or recursive functions, or any other of the features that make C Turing complete. It would work just fine in a subset of C that included only printf and basic string manipulations.

This makes me wonder whether Turing completeness is really necessary for the proof of Kleene's recursion theorem. Does the proof actually require it? If not, what is the most general class of languages to which the theorem applies?

Note that I'm not asking for the most general class of languages that have quines (which would be rather trivial), but the most general class of languages that have quines because of Kleene's recursion theorem. That is, I'm asking for the minimal set of language features needed to implement the recursion trick that's used in the most conservative proof of the theorem, thus guaranteeing that all languages within that class must have quines. Presumably the set of all languages that implement these features will be a subset of the set of all languages that exhibit quines, but it might be a superset of the Turing complete languages.

The Wikipedia page hints at this with the following text:

  However, a direct proof of Kleene's theorem (Kleene 1952: p. 352-353) does not make use of a universal program, which means that the theorem holds for certain subrecursive programming systems that do not have a universal program.

I don't currently have access to that reference, and I would like to know precisely which set of "subrecursive programming systems" this is referring to.

I stumbled upon a (partial) answer myself, in David Madore's essay about quines. I quote,

  A different, perhaps more satisfactory, way of stating the fixed-point theorem would be to eliminate the universality theorem from it, and to say: for every computable function $k$ there exists a $n$ such that $\phi_n(\dots) = k(n\dots)$. This corresponds more precisely to the intuitive content we have described. It is proved without the use of the universality theorem, using only the s-m-n theorem (for the actual proof, take the proof we have just given, and replace $\phi_{h(x)}(\dots)$ by $k(x\dots)$ everywhere). The advantage of formulating things like this is we see that it also works for primitive recursive functions (which satisfy s-m-n but not universality), so in effect a primitive recursive function can also make use of its own number. By applying the universality theorem (the function $\phi_{h(x)}(\dots)$ is computable, so we can call it $k(x\dots)$) we recover the fixed-point theorem as we have stated it.

So Kleene's fixed point theorem goes through at least for primitive recursive functions. It might still be that there's an even simpler class of languages that it also applies to, and I won't accept my own answer in case someone else has more to say on that topic. But for now I'm happy knowing this.


Number of seeks in an I/O efficent algroithm A seek is the task of positioning the read/write head of the disk to the required data block, and irrespective of the size of the data block, all contiguous data can be accessed using a single seek. Seek complexity of an algorithm is defined as the number of times the algorithm leaves one data locality for another, (or, in other words, chooses to read or write a block that is not physically contiguous with the last block read or written) thereby
necessitating a seek.

Now consider the simple I/O efficient Matrix Transposition algorithm. It takes $E_{P \times Q}$ as input and outputs its transpose $F_{Q \times P}$

Algorithm

Let $s=\sqrt{M/2}$

for $i = 1$ to $\lceil P/s \rceil$

$\hspace{20px}$for $i = 1$ to $\lceil Q/s \rceil$

$\hspace{40px}$ $F_{ji} = E^T_{ij}$

$\hspace{20px}$endfor

endfor

This is in fact a tiling method, that creates two tiles (matrix) of size $\sqrt{M/2} \times \sqrt{M/2}$ for input and output matrices and after its computation it writes the tile in to Disk.

When $P, Q \leq \sqrt{M/2}$ and matrix is in row-major order The two matrices fit in the main memory together (which is obvious). Simply Read $E$ in, compute $F$ and write $F$. It has been claimed:

  If a seek is needed between two rows, then $S = P + Q$ (where $S$ is number of seeks) If rows follow one another contiguously, then $S = 2$.

I can't understand the above sentence. If both matrices fit in memory, then why any seeks are needed?

Reference

This statement is in  I/O Efficient Algorithms for Matrix Computations Which is a Ph.D thesis. The definition is in Page 2 and the Algorithm in Page 12.

Thanks

You're missing the trivial point that the input is on disk, and needs P seeks to be read, while the output needs to go to disk and needs Q seeks to be written. (Or 1+1 in the cases they're contiguous on disk).

This is just setting the baseline; when you exceed the internal memory size you'll need more seeks to write out temporary data structures.


Memory Addressing - Alignment Clarification I'm reading "Computer Architecture A Quantitative Approach" (5th edition) and I'm having a hard time understing this table:

I understand how Misalignment happens, i.e., some byte, half-word, word, or double word it's not a multiple of the address where the element is being stored or accessed. The part that I don't understand is that it says in the caption: "that the byte offsets that label the columns specify the low-order 3 bits of the address"

My question is why are the low-order 3 bits of the address important or relevant in this situation? I'm assuming that the low order bits are the lowest binary values in the address. My intuition is that the 3 low order bits can tell us if the address is a multiple(2,4, or 8) of whichever data is being accessed, but I'm not sure.

Let's take a sample address, written in binary: 110100100110.

Now let's compute it modulo 2, 4, 8, 16, writing the answer in binary:

mod 2: 0
mod 4: 10
mod 8: 110
mod 16: 0110

(I recommend checking this.)

Hopefully you can connect the dots now.

As an additional hint, let's do a decimal example: 987348957943 mod 100 = 43. Why? Since the $i$th digit from the right (counting from 0) is "worth" $10^i$, so all the digits other than the two on the far right are "worth" some multiple of 100.


The nearest points in a set I have $N$ points and I have a distance between every pair of points stored in a 2D matrix. The goal is to find the nearest $K$ points among these $N$ points. "Nearest" means the sum of all distances between the $K$ points is smallest. A brute-force way is to search all combinations of $K$ points from the $N$ points. However, $K \ll N$. For example, $K$ is 5 and $N$ is 100. It is infeasible to search all ${100 \choose 5}$ combinations.

Actually, the distance between points is a metric to measure the difference between elements in the set, so it is better to describe the problem using graph rather than computational geometry.

I have read Clique problem on wiki, but I think the setting is different from my context here.

More info: The elements are probability discrete distributions. The metric here is Hellinger distance en.wikipedia.org/wiki/Hellinger_distance, which is to measure the difference between two probability distributions. I like to find the most similar probability distribution subset from a set.

This problem does generalize the clique problem.

One example of a metric is the shortest path distance in a connected, unweighted graph $G$, where the distance between vertices $u$ and $v$, $d(u,v)$, is the length of the shortest path between them. There exists a clique of size $K$ in this graph if and only if we can find $K$ points whose distances sum to ${K \choose 2}$.

For finding cliques of size $5$ you can do slightly better than brute force: see this answer. However without more structure on the metric you are interested in it is an open problem to do significantly better.


Can every context free grammar be transformed into equivalent grammar of this form? Show, that every context free grammar can be transformed into equivalent context free grammar ( with possible loss of $\lambda $ ) where  $a \in V_t$ and  $A,B,C \in V_n $ with rewriting rules of following type:

$ A \rightarrow a $

$ A \rightarrow aB $

$ A \rightarrow aBC $

My thoughts are that I need to show that every context free rule i can be written into set of context free rules that when applied generate same string as rule i.

Is that correct? If not, could you give me any hints on how to do it properly?

EDIT:

How I`m trying to do it:

Greibach normal form has rules of type:

$A \rightarrow aA_1A_2...A_n$

So I need to break long rules into shorter rules Chomsky normal form style.

Yes, you can start with ordinary Greibach NF and replace the offending productions. The trick is the same that is usually used to turn a grammar into Chomsky Normal Form. Introduce new nonterminals that represent sequences of old nonterminals, for instance $[A_1A_2\dots A_k]$ is a single symbol that represents the sequence $A_1A_2\dots A_k$ when $k\ge 2$.

Then any production $A\to aA_1A_2\dots A_n$ with $n\ge3$ is replaced by $ A\to a A_1[A_2\dots A_n]$, leaving two nonterminals at the rhs of the production.

Remaining question: what are the productions for terminals $[A_1A_2\dots A_k]$, in such a way that we get only a bounded number of those nonterminals?
Well, if $A_1 \to bB_1\dots B_m$ in the original grammar in GNF, then we add the production $[A_1A_2\dots A_k] \to b[B_1\dots B_m][A_2\dots A_k]$ in the new grammar. This can be done for all sequences of nonterminals that are suffixes of the sequences introduced by the original grammar.

Note that we have to take care of short sequences in the obvious way. If in the construction above we find an empty sequence $[\ ]$ it should be omitted, and we write $A$ for the sequence $[A]$ of length one. These special cases occur if $m\le 1$ or $k\le 2$.


Given a pair of coordinates $(x,y)$ in 2D, find the points inside the circle $C((x,y),R)$ Suppose that there are a set of $n$ points $P = \{(x_1,y_1), \dots, (x_n,y_n)\}$ in 2D.

Given two coordinates $(a,b)$ and a number $r \in \mathbb{R}$, is there an algorithm with $O(|Q| + \log n)$ running time that can find the point set $Q \subseteq P$ containing those points of $P$ that are inside the circle with center $(a,b)$ and radius $r$?

(That is, I want to find all points in $P$ with coordinates $(i,j)$ such that $(i-a)^2 + (j-b)^2 \leq r^2$.)

[I originally asked about a solution with running time $O(\log n)$, but as Pål GD correctly points out, the answer to that question was "not possible".]

Obviously not. You must inspect all the points and, on a classical, deterministic computer, you can't possibly look at $n$ points in only $O(\log n)$ time.

Note that this answer applies equally to the original question (is it possible in $\log n$ time?) and the revised one (is it possible in $|Q|+\log n$ time?). The answer could well be $Q=\emptyset$, but you can't figure that out in time $o(n)$.


Build-Max-Heap vs. HeapSort I'm not sure whether my definition for these 2 terms are correct. Hence, could you help me verify that:

HeapSort: A procedure which sorts an array in place.

Build-Max-Heap: A procedure which runs in linear time, produces a max- heap from an unordered input array.

Is worst-case input = worst-case running time?

If so, given the size n for Build-Max-Heap, would its worst case input be the same as the HeapSort which is $\mathcal{O}(n \log n)$?

HeapSort: A procedure which sorts an array in place.

Can be in-place or not in-place, the point is it's using a heap data structure to help sort.

Building heap is linear with a careful analysis

See more here


What does "effective enumeration" in Turing machines mean? what is meant by EFFECTIVE ENUMERATION i have comes across this word when I was reading about enumerators for Turing machines is it same as LEXICOGRAPHIC ORDER?
so effective enumeration is possible for recursive sets but no recursively enumerable sets?
i came across this in this question of a competitive exam

L1 is a recursively enumerable language over Σ. An algorithm A effectively enumerates its words as ω1,ω2,ω3,….
 Define another language L2 over Σ∪{#}

{wi#wj ∣ wi,wj∈L1, i < j}.

Here # is a new symbol.

Consider the following assertions.

S1:L1 is recursive implies L2 is recursive

S2:L2 is recursive implies L1 is recursive

which of the following is true ?

One way to approach EFFECTIVE ENUMERATION is as following. Let $L=\{a_1, a_2, \dots\}$ be a set/language. Then we (effectively) enumerate $A$ if we can construct a TM $M$ which prints out (enumerates) all elements of $L$ on the tape, say in the following way: $a_1$#$a_2$#$a_3$#$\dots$. The order of the elements is not important. What is important is that any element of $L$ will eventually be printed on the tape, meaning it must not be a  LEXICOGRAPHIC order.


Generating all directed acyclic graphs with constraints I am interested in listing all the unlabeled1 acyclic digraphs with n vertices which satisfy some additional constraints, such as (a) the resulting graph is connected and (b) except for R identified root vertices, all vertices have two incoming edges and zero or one outgoing edges.

There may also be additional domain-specific constraints, but they are probably easy enough to implement by simply generating and rejecting graphs that do not meet the constraints. In principle, conditions (a) and (b) above could be satisfied in this way above, but at least in the case of (b) it seems very advantageous to consider them directly in generating process since the output is likely to be quite sparse (i.e., a large majority of graphs will fail to satisfy (b) and this ration increases with increasing n).

My problem is twofold:

Even ignoring the constraints part, I have not be able to determine how to efficiently generate DAGs. I know there are a lot of them so I'll mostly be dealing with smallish n, let's say n < 15. There seem to be some promising papers, although may of them are focused on the closed-form counting of the number of graphs rather than actual generation, and any remaining ones are paywalled.
I want to apply the at least enough of the constraint part during the generation to avoid the case where nearly all generated graphs are simply rejected. That is, I hope the generation of the constrained graphs is considerably faster than the generation of the much larger number without constraints.

You can find lots of information on random generation of such graphs, but not much on exhaustive generation (which seems like the easier of the two problems).

1 That is, I want to exclude generation of isomorphic graphs.

For small $n$, the easiest solution might be to download a list of all non-isomorphic graphs and then filter them according to your condition.

You might take a look at Brendan McKay's collection, constructed using geng as part of the Nauty graph isomorphism package.

See Enumerate all non-isomorphic graphs of a certain size for more details and citations.


Find axis-aligned rectangle with maximum area in a point set in the Euclidean plane On the plane $n$ points $(x_i, y_i)$ are marked. Select 4 points so that they define a rectangle with the greatest area and sides parallel to the axes.

Time limit for python is 10 seconds, for other programming languages - 2 seconds.

Input data:

in first string integer $n$, $(4 \leq n \leq 3000)$
in next $n$ strings pairs of integer coordinates $x_i\  y_i$ $(-10\ 000  \leq x_i,\ y_i  \leq 10\ 000)$

Output data:

4 different indices (numbers from $1$ to $n$), specifying the vertices of the rectangle.

I made in python, but even with tests of $n \leq 111$ it have TL.

n = int(input())
l = []
for i in range(n):
    a, b = map(int, input().split())
    l.append((a, b))

ans = [1, 2, 3, 4]
mS = 0

for i in range(0, n - 3):
    for j in range(i, n - 2):
        for k in range(j, n - 1):
            for t in range(k, n):
                r = [l[i], l[j], l[k], l[t]]
                w = sorted(r, key=lambda element:(element[0], element[1]))
                if w[0][0] == w[1][0] and w[1][1] == w[3][1] and w[3][0] == w[2][0] and w[2][1] == w[0][1]:
                    s = (w[1][1] - w[0][1]) * (w[3][0] - w[1][0])
                    if s > mS:
                        mS = s
                        ans = [i + 1, j + 1, k + 1, t + 1]

ans = sorted(ans)
print(ans[0], ans[1], ans[2], ans[3])

Step 1. Sort all the points according to their $x$-coordinate - you will get an array of buckets, where each bucket contains a (sorted) list of points with the same $x$-coordinate. You can drop (or ignore in all subsequent steps) all the buckets, containing only single point.

Step 2. Define a mapping $M$, where the key will be a closed integer interval and the value - ordered set of integers. Scan all the buckets, created in the Step 1. For each bucket insert all the possible pairs of its $y$-coordinates into the mapping $M$ - their corresponding $x$-coordinates must be inserted into the set, corresponding to this interval:

function Insert(M, x, y0, y1)
  if mapping M contains element ([y0, y1] -> S)
    insert x into set S
  else
    insert element ([y0, y1] -> (x)) into mapping M

You can drop (or ignore in all subsequent steps) all the elements of the mapping $M$, for which their value set contains only a single number.

Step 3. The mapping M will contain elements like this:

$$([y_0, y_1] \rightarrow (x_0, x_1, ..., x_{m-1}))$$

The biggest rectangle with "vertical" side $[y_0, y_1]$ will have "horizontal" side $[x_0, x_{m-1}]$, so you can ignore all the middle elements of the ordered set. Finally, scan all the elements in the $M$ to find the element with largest rectangle area $A$:

$$A = (y_1 - y_0) \cdot (x_{m-1} - x_0) $$

Number of intervals in $M$ is $O(n^2)$, so time to insert into the mapping will be $O(n^2log(n))$.


Why is an accurate time so important for servers and computers? I just saw this short documentary about atomic clocks. The person working for the Atom clock company gets asked what would happen is all the atom clocks would be turned off and he replayed that cell phone services and the internet would stop working. I have read that an accurate time is important but do not now why.

Why is an accurate time so important for servers and computers and why would these services stop working?

It depends. If all atomic clocks would be turned off simultaneously, right now, that would be trouble. Because everyone relies on atomic clocks. And everything is organized in such a way that it doesn't matter much if a handful or two dozen stop working, but if they all stop working, then all the time servers in the world have no source for their time anymore.

If you announced that exactly three months from now all atomic clocks will be turned off, that would be a lot of work setting up some slightly less precise clocks, and to switch over to those less precise clocks, but cell phone service and internet would happily continue working. Even a quartz wall clock (like the one in your office) can be precise within 0.2 parts per billion. Taking 1,000 such wall clocks and carefully averaging their time would be quite accurate, and surely we can build a quartz clock for 100,000 that is a lot more precise than one that costs 100.

The problem is not the precision. The problem is that if you turn off all atomic clocks right now then we don't have anything to replace them right now. There are about 400 atomic clocks in the world. If we had 400 state of the art quartz clocks ready to be used as replacement automatically if the atomic clocks are stopped, then there would be no problem except for very few very special use cases.


Modulo operation in monotone complexity Given $x\in\Bbb N$, I would like to find $x\bmod N$, where $N$ is composite. For example $N=35$, $x=53$ and $x\bmod N=18$. Is this operation considered monotone in circuit/algebraic complexity language? I also want to have consider $x_1+x_2\bmod N = x_1\bmod N+x_2\bmod N$ and $x_1x_2\bmod N = (x_1\bmod N)(x_2\bmod N)$.

In circuit complexity, a monotone operation is a function $f$ which is also monotone: if $x \leq y$ then $f(x) \leq f(y)$, where $x \leq y$ is a shorthand for $x_i \leq y_i$ for all $i$. There are many ways to define modulo $N$, but most of them are probably either uninteresting or not monotone. For example, consider the function which is true if the input is divisible by $N$. Then $f(0) = 1$ while $f(1) = 0$, and $0 \leq 1$ no matter what the actual length of the input is.


Modelling a dependency of multiple transitions on data in one place We are modeling our process using a colored Petri net. One of the limitations we have is that when multiple transitions depend on one place, only one of those transitions will fire because then the token and data is consumed.

How can we model our process, or what type of Petri net property can we use, to facilitate the fact that multiple transitions can depend on one place and all have to be able to consume the same token?

I do not know if there is a variant of Petri nets that captures your intent exactly -- there probably is, there are so many -- but the feature can be expressed with regular Petri nets.

Just add a transition that creates tokens in multiple places, one per original transitions. Then, all three follow-up transitions can fire after the preceding one is done.

Introduce whatever syntax you want to express this neatly, and implement it using multiple places in the backend.


Can a KD tree be used as a decision tree through nearest neighbor queries? If I were to construct a KD tree representing a sufficiently dense space, could it be used as a decision tree by querying it for the nearest neighbor to the point to classify?

Yes, you can.  The scheme you are thinking of is called the nearest-neighbors classifier.  Read the link for more details.  In many settings it turns out to be a quite effective classification algorithm.


Why ambiguous grammars are allowed for operator precedence parser? I am aware of what is ambiguity, and why is it necessary to eliminate ambiguity in compilers in a certain context, but how can we allow ambiguity for operator precedence parser? Say I have a set of operations like a-b-c now if we operate it with two different parse trees, say one like (a-b)-c and other like a-(b-c)
there meaning changes..
So how can we allow ambiguous grammar in operator precedence parser? shouldn't it be the opposite?

An operator precedence parser usually has no ambiguity at all. However, the evaluation order is not determined by the parse tree, but by the operator precedences and associativities.

As a practical example, the Swift language doesn't define operator precedence or associativity in the language. It doesn't even define operators, except that the scanner knows which sequences of letters could be operators. The actual operators and precedence / associativity are define by the programmer, or as part of the standard library. As a result, a+b*c>d/e produces a parse tree that just consists of the five operands and four potential operators. The parse is unique, but doesn't tell how the expression should be evaluated.

The next phase checks that all the four potential operators are indeed operators. Then the priorities and associativity of the operators, as defined by the programmer or standard library, are examined. * and / have highest priority, + has lower, and > has even lower priority. If you had a-b-c, then the two operators have the same precedence, and both are left-associative, so the order is also clear. If you had two or more consecutive operators with same priority and different associativity, or with no associativity, that would be an error.

You couldn't define a grammar to handle operators, because their precedence and associativity are not even known when you start compiling.


Find plane within margin of error of >50% of points There are $N < 3\times10^4$ 3D points. At least 50% of them lie approximately in the same plane, i.e. the distance between the plane and each point is at most $p$. Find such a plane.

Attempt: since the number of points in the plane is at least 50%, we can randomly sample 3 points from the set. They will all be in the plane with probability 12.5%. We build a plane through these 3 points and check that at least 50% of points lie approximately in it. Within 10-20 samples we'll find the plane.

Problem: because of the margin of error there's not just one plane going through 3 points, but many possible planes. How do we examine all of them?

How would you tackle this problem?

One reasonable approach is to use RANSAC.

Pick three points.  Find the plane that goes through them.  Iterate through all the points and keep the points that are near that plane (the inliers) and discard the rest (the outliers).  If fewer than 50% of the points are inliers, discard this plane.  Otherwise, discard the plane you have so far and use linear regression to find the best plane that fits the inliers as well as possible.  That's a candidate plane.

Repeat this 1000 times, to get 1000 candidate planes.  Take the best one.  You can measure how good a candidate plane is by taking the average distance from the plane to each point, averaged over all the points that are close to that plane (ignore the ones that are far away; if 50% or more are far away, discard the plane).


Subset Sum algorithm, why not split by 3+? A classic algorithm for Subset Sum is to first split the input into two sets (A and B), evaluate the sums of the subsets of each, sort those sums for each A and B, then cleverly filter whole ranges of combinations by comparing the highest and lowest sums from each A and B.

Do we know (or does someone have an argument) why not to split the input into 3 or more sets rather than two?

I presume that there would be a combinatorial proof that doing so would either require the same or more number of steps.

First of all, let me mention that the algorithm you mention is attributed to Horowitz and Sahni (1974), whose algorithm achieves time $O(2^{n/2})$ and space $O(2^{n/2})$. A major improvement due to Schroeppel and Shamir (1981) reduces memory consumption to $O(2^{n/4})$ while keeping the same running time; this algorithm divides the input into four sets.

The topic is of interest to cryptographers, and there has been a recent line of improvements: Howgrave-Graham and Joux (2010), Becker, Coron and Joux (2011), Dinur, Dunkelman, Keller and Shamir (2012) and Austrin, Kaski, Koivisto and Määttä (2013), which seems to be the latest word on the subject; the authors of the last paper are actually not cryptographers.


If $L$ is a regular language, then $s(L)$ is also regular ...where $s$ is a substitution that replaces each symbol of each string in $L$ with a regular expression.

For example, if $L=a^*b$ and $s(a) =ab, s(b) = b^*$, we have $s(L) = (ab)^*b^*$.

My thoughts so far are that replacing characters in a regular expression with regular expressions still gives us a regular expression overall. Namely I can show for $x \in L$ that $s(x)$ will be a regular set, and then I can do a union over $s(x)$ for all $x \in L$ to show $s(L)$ is regular (by closure of union).

My problem here is carefully showing the substitution will produce a regular set. Does it suffice to say if $x$ is something captured by a regular expression, then $s(x)$ is regular as well? I'm not sure how to prove this.

First thing you must understand  is that regular expression are closed under union(+), closure(*) and concatenation (.)  . reason being every regex denotes a regular language and regular languages are closed under union, closure and concatenation.

Second thing you should know that if r1 and r2 are regex then the following regex are also regular

r1 + r2
r1.r2
r1* ,r2*

so if you are substituting a regex by another regex it should fall among the above three categories or in simple words you will be able to form the regex(after substitution) with use of above relation. coming to you question the language generated after substitution can be formed using above closed properties over regex. let say r1 = a , r2 =b  then we have

( ((r1.r2) * ) . r2* )  making it regular

one more thing the only operation defined to regex are the above three  and if so any substitution of regex by regex will have
either of the three operation associated with it thus making it regular again


How does a Turing machine with one tape read its input? It's often implicitly assumed that we don't have to pay much attention to the difference between the program (which specifies the function being computed) and the input (the value on which that function is evaluated) when reasoning about Turing machines. In particular, people are often happy to assume that the program and inputs are encoded on the same two-sided tape. How this actually works out okay isn't obvious to me though.

Let's say I have a UTM, $\Phi_f$, which has a partially filled two-sided tape specifying a program for calculating the function $f$. Since the program is a finite set of symbols, it begins on cell $b$ and ends on cell $e$ where $b < e$. Now I want to encode the input on the same tape, so I begin at cell $b-1$ and work in the negative direction to encode my specific input, taking up as much space as I need.

My understanding is that as long as the encoding methodology I use to specify the inputs is computable and fixed in advanced, I can use any input encoding I want. The fact that it needs to be fixed in advanced is clear, since the actual program for calculating $f$ for two different encodings is very likely different. Intuitively, it makes sense that I can use any encoding I want because if we fix some standard "base" encoding then computing $f$ on an input encoded by the function $g$ is the same as computing $f(g^{-1})$ on an input encoded by the base encoding.

I have two questions:

Is the above correct? In particular, is it always possible to pick an encoding and a function, and then find a single program that computes $f$ on an arbitrary input using that encoding?
On the tape, what does the operation of the TM look like? The symbols used to encode the input have a meaning to the TM as a program (or can), and that seems like it could cause problems. For example, the (2, 18) UTM has symbols that always result in the head moving left and others resulting in the head always moving right. It seems like if you chose those symbols to encode the input you could run into problems where the UTM could never escape the input section of the tape.

EDIT: You can read about the (2, 18) UTM I mention for free here. The table presented on page 237 of the journal / page 23 of the PDF shows the table defining the machine. It's a bit hard to read, but it's two main columns each with three subcolumns. A row of $q_1\;1c_2\;Lq_1$ is read "if you are in state $q_1$ and read the symbol $1$ write the symbol $c_2$, move Left, and transition to state $q_1$. The row with a dash instead of a transition is the halting condition.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Hoare's monitor - what happens after a "signal" Assume I have producer and consumer in a monitor.

The code of the consumer signals the producer and then does something else.
I know in a Hoare-style monitor, after signaling, the thread that is signaled wakes up and is is now schedule.
What about the other instructions in the consumer after the signal? When will the consumer continue?
What if the consumer sends the signal before the producer does the wait?   Will the producer be stuck forever?
If there is a context switch will the mutex of the monitor be released?

Here's the picture of a Hoare-style monitor from wikipedia user Theodore.norvell:

The circles are threads, the rooms off to the sides are various queues.  Think of the monitor as being protected by a mutex.  Only one thread gets the mutex at a time.  Once a thread has the mutex it keeps the mutex until it releases the mutex by (1) waiting (in which case it goes to sleep on a condition variable), (2) signalling (in which case it goes into the queue labeled s in the picture or (3) exiting the monitor completely.  The scheduling algorithm is given in the wikipedia article.  At any point in time the relative priorities to get into the monitor are: (1) the single thread that was most recently signalled, (2) threads in queue s (usually s is FIFO), (3) threads in queue e (the entry queue).
If the consumer sends the signal before the producer waits then the producer will be stuck forever.  This is sometimes called "the missed wakeup problem."  It is avoided by recognizing that you should really be waiting for some condition to become true (e.g., "the queue is no longer full"), not waiting for some condition variable to get signaled.  When the producer is in the monitor (has acquired the mutex) it only waits on the condition variable if it sees that the condition is not currently true.  The consumer signals the condition variable every time the condition (state) "queue is full" changes to "queue is not full", whether there is anyone waiting on the condition variable or not.
If there is a context switch the mutex of the monitor will not be released.


Most efficient way to check if key exist on a table Imagine a person called Albert. Albert lives in Europe and would love to move to America. One day he got his wish come true. A person called Margareta gave him a key. The value of the key is the same as the address for a house in USA. Albert doesn't have that much money to travel to America to confirm whether the key is a hoax or not, by going to the address of the key. He certainly doesn't have the money for a house in America. If the key turns out to be a hoax, Albert would have a very hard time to make a living in America. It would cost him dearly. One day, a postman who knew all the addresses in America visited Europe. He happened to meet Albert.

Can the postman carry a certain information that is less than the information of all addresses in America to confirm whether Albert's key is valid or not? Then what is the information and what kind of operations is made to make the confirmation?

Assume all information is numeric here.

Background:
I was looking at implementing a hash table for already known keys and I was wondering whether there exists efficient lookups where I don't have to visit a bucket in a hash table(America) to confirm whether a key exist or not.

Using Bloom filters you can store membership of $n$ elements using approximately $-1.44\cdot\log_2(p)\cdot n$ bits, where $p$ is your probability of a false positive (it does not have false negatives).

This is assuming you have perfect independent hash functions (which is a reasonable enough assumption).

So if Albert wants an 0.1% chance of wasting his time the postman needs to carry $\approx 14.4$ bits of information per address, which is definitely less than the amount of bits to uniquely store an address.


Concept used in the proof In the paper "Resolution for Quantified Boolean Formulas", I am unable to understand the proof of theorem 3.4. Please help me with the basic concept used on page 4:

The concept that I am referring to is:

  Then $\mathit{\Phi}$ is false if and only if there exists a clause $\phi \in N^+_\mathit{\Phi}$ or $\phi \in N_\mathit{\Phi}$ such that $\forall x_1\exists y_1\cdots y_{k-1}\forall x_k(P_\mathit{\Phi} \land \phi)$ is false.

An unquantified CNF formula consisting of clauses containing a single positive literal plus any number of negated literals is always satisfiable.  To produce a satisfying assignment, you simply set all the positive literals to true, satisfying all the clauses.  If you existentially quantify the variables associated with the positive literals and allow arbitrary quantification of the remaining variables, the formula is still satisfiable, and  for the same reason.  In the proof of the theorem, $P_\mathit{\Phi}$ is the subset of such clauses from the Horn formula $\mathit{\Phi}$.  Thus $P_\mathit{\Phi}$ by itself is always satisfiable.  It follows that $\mathit{\Phi}$ can only be unsatisfiable if, out of the sets of remaining clauses (denoted $N^+_\mathit{\Phi}$ and $N_\mathit{\Phi}$), a clause requires one of the previously set positive literals in $P_\mathit{\Phi}$ to be set false and there is no other way to satisfy the previously satisfied clause.


A Guess Turing Machine that accepts a random Binary number I'm trying to construct a turing machine that accepts any random binary numbers. From the theory (and partial example) in this video, I understand (correctly?) that this is something that is more easily doable with a Non deterministic turing machine.

So I have come up with a concept as such that I start with state Q1 (from the left side of the band) and upon reading a zero I move right, and upon reading a One 1 move right and the machine enters the same state, again and again until the complete word is read.

I understand that this is a way I can accept an input. What I dont understand is how to include accept and reject states on the machine? I would appreciate all help on the matter.

There can't be "random numbers", each number is exactly that one, not at all "random". You can talk about getting a number at random from a set, perhaps according to some distribution. You might talk about a stream of bits, each of which is selected at random. But then the sequence 010101... is perfectly possible as an outcome (if it can't appear, it isn't random!).


Quicksort explained to kids Last year, I was reading a fantastic paper on “Quantum Mechanics for Kindergarden”. It was not easy paper.

Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or at least handwave) that the average complexity is $O(n \log n)$, and what the best and the worst cases are, to a kindergarden class? Or at least in primary school?

Quicksort's actually pretty easy to understand, if they understand basic counting and division by 2.  Make a bunch of X flash cards, number them 1--X, and shuffle it.  Then here's the explanation:

  OK, we've got this deck of (let's say 20) cards here.  We want to put
  them in order, so 1 is first, then 2, then 3, and so on.  Here's a
  very quick way to do it.

  First, let's go through this deck and make two piles out of it.  Half
  of 20 is 10, so anything bigger than 10 goes in this pile on the
  right, and anything smaller goes in this pile on the left.  (Make sure
  to demonstrate as you go.)

  Now, let's do the same thing with the smaller piles.  What's half of
  10?  (Someone says "five!") That's right!  So anything bigger than 5
  goes in this pile on the right, and anything smaller goes in this pile
  on the left.

  And over here, we've got the group that's bigger than 10.  So half of
  10 is 5, and what's 10 plus 5? (Someone says "fifteen!") That's right!
  So anything bigger than 15 goes in this pile on the right, and
  anything smaller than 15 goes in this pile on the left.

  And now the piles are getting small enough that you can easily look at
  them and put them in order.  Look, here we've got 2, 4, 5, 3, 1.  So
  we just switch them around like this, and you can see 1, 2, 3, 4, 5.
  So let's do the same thing with the other piles, and then we just put
  the piles in order, and look!  They're in order from 1 to 20!

Congratulations.  You've just taught a bunch of children the basic principles of an adaptive quicksort algorithm!  You can go a bit deeper than that depending on mental maturity, but going much further beyond this point requires some understanding of formal logic.

As for proving its complexity, that's trickier.  It's one of the things that requires formal logic, and they'll have to understand the basic principles of big-O notation in the first place.  You might want to hold off on that part at first.


Complexity of the V-opt heuristic Traveling Salesman algorithm The paragraph on V-opt heuristic TSP algorithms at this site mentions a very effective algorithm due to Lin-Kernigham-Johnson. That page says:

  For many years Lin–Kernighan–Johnson had identified optimal solutions for all TSPs where an optimal solution was known and had identified the best known solutions for all other TSPs on which the method had been tried.

Impressive, so what is the complexity of that algorithm? Does the algorithm often work faster than predicted  based on theoretical complexity (if yes, how much)? Is that algorithm used most often in software that solves the TSP?

According to the original 1973 paper, the Lin-Kernighan algorithm

  ...produces optimum results with high frequency, in running times
  that grow about as $n^2$.

The iterated Lin-Kernighan variant, proposed by Johnson in 1990, offers an observed improvement to $O(n^{1.25})$; an experimental treatment of this and many other local optimization TSP heuristics can be found here.


How to prove that replacing a character in a string in both C and JavaScript is equivalent? I would like to try some different proofs, specifically in proving equivalence of the implementation of some feature in two different programming languages (C and JS in this question).

This is about proving that replacing one character in a string is equivalent in C and JS.

In JS, for example, strings are immutable, while in C, strings are mutable. So in JS you might have to do this:

functioni replaceAt(string, index, replacement) {
  return string.substr(0, index) + replacement + string.substr(index + replacement.length)
}

While in C you might just do something like this:

#include<stdio.h>

int
main() {
  char string[11] = "hello world";
  string[1] = 'i';
  printf("%s", string);
  return 0;
}

Basically, I am trying to come up with an example where, the perceived effect or desired outcome is for all intents and purposes the same. That is, the end result is that the character was replaced at a specific position (the same position in each language). Even though in one language the string was mutable, while in the other, it was immutable. What needs to be taken into account here to make a proof saying these are equivalent? How do we capture the notion of "partial equivalence" or "perceived equivalence"? (By that I mean, the outcome is roughly the same, so we want to make a proof statement that these are the same with regard to some spec).

I would start by creating a formal definition of the function that you want and then proving for correctness each of the implementations.

Consider the following axiomatic definition:

$$replaceAt: string * \mathbb Z *char \to string$$

$$\forall c:char . ( \forall i \in \mathbb Z~.~replaceAt(``,i,c) = `` )$$

$$\forall c:char . (\forall s:string . ( \forall i \in 0.. len(s)-1~.~replaceAt(s,i,c)[i] = c ))$$

$$\forall c:char . (\forall s:string . ( \forall i \in 0.. len(s)-1~.~len(replaceAt(s,i,c)) = len(s) ))$$

$$\forall c:char .(\forall s:string . ( \forall i,j \in 0..len(s)-1 . i \neq j \implies replaceAt(s,i,c)[j] = s[j] ))$$

$$\forall c:char .(\forall s:string . ( \forall i \in \mathbb Z . i \geq len(s) \implies replaceAt(s,i,c) = s ))$$

If you can prove the correctness of each implementation to these axioms I'd say they're equivalent. At the moment your C implementation is not even a function.  Your Javascript function takes a string and not a char.  None of them are defined for indexes greater than your input.

I don't think comparing implementation to implementation makes sense as there are lot of differences in the implementation models of each language.


What is the most efficient algorithm to compute polynomial coefficients from its roots? Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is $y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$. To get the coefficients (i.e. $y = \sum_{i}^n a_i x^i$), a straightforward expansion requires $O(n^2)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct with each other. The problem is equivalent to polynomial interpolation with $n$ points: $(x_1, 0), (x_2, 0), \dotsc, (x_n, 0)$. The fast polynomial interpolation algorithm can be run in $O(n\log^2(n))$ time.

I want to ask whether there is any more efficient algorithm better than $O(n^2)$? Even if there are duplicated values among $\{x_i\}$? If it helps, we can assume that the polynomial is over some prime finite field, i.e. $x_i \in \mathbf{F}_q$.

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method.

First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm).  Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$.  Next, compute the coefficients of $f(x)=f_0(x)f_1(x)$ using FFT-based polynomial multiplication.

This yields an algorithm whose running time satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n \log n).$$

The solution to this recurrence is $T(n) = O(n \log^2 n)$.  This all works even if there are duplicates in the $x_i$.

(You might also be interested in Multi-point evaluations of a polynomial mod p.)


Is it a problem to be a programmer with no knowledge about computational complexity? I've been assigned an exercise in my university. I took it home and tried to program an algorithm to solve it, it was something related to graphs, finding connected components, I guess.

Then I made the most trivial thing that came into my mind and then showed to my lecturer. After a brief observation, he perceived that the runtime complexity of my solution was inviable and shown something more efficient. And there is a tradition of programmers who have no idea on what is computational complexity (I was one of those), so is it a problem if a programmer has no idea on what is computational complexity?

Yes, I would say knowing something about computational complexity is a must for any serious programmer. So long as you are not dealing with huge data sets you will be fine not knowing complexity, but if you want to write a program that tackles serious problems you need it.

In your specific case, your example of finding connected components might have worked for graphs of up to say $100$ nodes. However, if you tried a graph with $100.000$ nodes then your lecturer's algorithm would probably have managed that in 1 second, while your algorithm would have (depending on how bad the complexity was) taken 1 hour, 1 day, or maybe even 1 eternity.

A somewhat common mistake students make in our algorithms course is to iterate over an array like this:

while array not empty
    examine first element of array
    remove first element from array

This might not be the most beautiful code but in a complicated program something like this might show up without the programmer being aware of it. Now, what is the problem with this program?

Suppose we run it on a data set of $100.000$ elements. Compared to the following program, the former program will run $50.000$ slower.

while array not empty
    examine last element of array
    remove last element from array

I hope you agree that having the knowledge to make your program run $50.000$ times faster is probably an important thing for a programmer. Understanding the difference between the two programs requires some basic knowledge about complexity theory and some knowledge about the particulars of the language you are programming in.

In my pseudocode language, "removing an element from an array" shifts all the elements to the right of the element being removed one position from the left. This makes removing the last element an $O(1)$ operation since in order to do that we only need to interact with 1 element. Removing the first element is $O(n)$ since in order to remove the first element we need to shift all the other $n-1$ elements one position to the left as well.

A very basic exercise in complexity is to prove that the first program will do $\frac{1}{2}n^2$ operations while the second program uses only $n$ operations. If you plug in $n=100.000$ you will see one program is drastically more efficient than the other.

This is just a toy example but it already requires a basic understanding of complexity to tell the difference between the two programs, and if you are actually trying to debug/optimize a more complicated program that has this mistake it takes an even greater understanding to find out where the bug is. Because a mistake like removing an element from an array in this fashion can be hidden very well by abstractions in the code.

Having a good understanding of complexity also helps when comparing two approaches to solve a problem. Suppose you had come up with two different approaches to solving the connected components problem on your own: in order to decide between them it would be very useful if you could (quickly) estimate their complexity and pick the better one.


Complexity of Double-Horn-SAT? On one hand, Horn-SAT is known to be tractable in linear time - where Horn-SAT is the problem of deciding whether a given set of propositional Horn clauses (with at most one positive literal) is satisfiable or not.
On the other hand, Double-SAT is NP-complete (see this post : Proving Double-SAT is NP-complete) - where Double-SAT is the problem of deciding whether a given set of propositionnal clauses has at least two models.

Let Double-Horn-SAT be the problem of deciding whether a given set of propositional Horn clauses has at least two models.

What is the complexity of Double-Horn-SAT ?

Double-Horn-SAT is polynomial-time solvable.

Given a set of Horn-clauses $X = \{C_1,C_2,...,C_n\}$ and a solution $x_1=b_1,x_2=b_2,...,x_n=b_n$, $b_i \in \{true,false\}$ we can observe that a second solution must differ in at least one variable $x_i$.
So we can run the Horn-SAT algorithm $n$ times on the augmented set $X_i' = X \cup \{ \lnot x_i \}$ if in the first solution $x_i = true$ or on the augmented set $X_i' = X \cup \{ x_i \}$ if in the first solution $x_i = false$. If we find  a solution for one of the $X_i'$ then it is a valid solution for the original set $X$, too and by construction it differs from the first one; otherwise the original set doesn't have a second solution, as can be easily proved by contradiction.

See also the question "Complexity of finding a second solution given a correct solution to an NP-complete problem" on cstheory and Laurent Juban, Dichotomy theorem for the generalized unique satisfiability problem (1999)


Cartesian product of regular expressions? My textbook has a problem to find the regular expression that describes the set of all strings of 0's and 1's whose number of 0's is divisible by 5 and whose number of 1's is even.

I can write a regular expression for each condition

a. $0^*(10^*1)^*$

b. $1^*(01^*01^*01^*01^*01^*)^*$

I am having trouble understanding how to combine these two regular expressions. If they were DFAs, I could combine them by taking their cartesian product. Is is possible to take the cartesian product of two regular expressions (without translating each to a DFA first)?

Gelade and Neven prove the following theorem in their paper Succinctness of the Complement and Intersection of
Regular Expressions:

  For every $n$ there exist two regular expressions $r_1,r_2$ of size $O(n^2)$ such that the smallest regular expression representing $L[r_1] \cap L[r_2]$ has size $\Omega(2^n)$.

This suggests that there is no analog of the product construction for regular expressions.


Lambda Calculus Prove Equality Excessive (Haskell-oriented) I'm on a lambda calculus with parametric polymorphism a la Hindley-Milner Haskell-oriented course and I'm currently facing this exercise which I got stuck on.

Prove that $(\forall m\downarrow, n\downarrow :: N)\space (m+n)-m=n$

Definitions:

$(+)=\backslash m \space n \rightarrow case \space m \space of \space \{0\rightarrow n, Sx \rightarrow S(x+n)\}$

$pred = \backslash n \rightarrow case \space n \space of\{0\rightarrow 0,Sx\rightarrow x\}$

$(-)= \backslash m \space n \rightarrow case \space n \space of \space \{0\rightarrow m,Sx\rightarrow pred(m-x)\}$

Seems super simple but there's a part at which I got stuck. I also can only use the following already proven statements (may not need all):

$1) \space m+0=m$

$2) \space m + Sx = S(m+x)$

$3) \space m+n=n+m$

So here's what I did so far: I decided to prove this by using induction over m

$m=0, \space (0+n)-0=n-0=n$ is true (applying the given definitions for the functions)

$m=x, \space (m+n)-m=n$ is true (Hypothesis)

$m=Sx, \space (Sx+n)-Sx=n$ is true (Thesis)

Proof for $m=Sx$:

$(Sx+n)-Sx=S(x+n)-Sx=pred(S(x+n)-x)$ At which point I got stuck. I obviously have to get that $S$ out of $S(x+n)-n$ to have $(x+n)-n$ and apply the Hypothesis but I can't figure out how. Any ideas?

Another way is to continue from where you got stuck, in the inductive step. You have:
$(Sx+n)−Sx=S(x+n)−Sx$

Now you can prove the following lemma by induction on y:

  Lemma:  $Sx - Sy = x - y$

  case 0:     $S(x) - S(0) = pred (S(x) - 0) = pred(S(x)) = x = x - 0$
  given $Sx - Sy = x - y$, case $Sy$

  $Sx - S(Sy) = pred (Sx - Sy) = pred (x - y) = x - Sy$

then you continue:

$(Sx+n)−Sx=S(x+n)−Sx =^{(lemma)} (x + n) - x =^{(IH)} n $


serial number of combination How can I find the serial number of an n-choose-k combination?

I would like a function that gets as input:

$n$,
$k$,
a set of $k$ elements out of the set ${0, 1, ... n-1}$.

The output should be a number in the range $[0, C(n,k)-1]$, such that:

Each different combination gets a different number;
All numbers in the range are covered (i.e. no holes in the index).

For example, for $n=3$, $k=2$, the function could be:

$serial(3, 2, {a,b}) = (a+b-1)$

Since there are only 3 combinations, and their sum is different. Obviously, this doesn't generalize to larger n and k.

One solution is: at the beginning of the program, loop over all combinations, and create a static map from a combination to its index. However, this is very inefficient when n is large.

We will use the notation $\binom{n}{k}$ instead of your $C(n,k)$. The idea is to use Pascal's identity $$ \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1} $$ and its proof: there are $\binom{n-1}{k}$ not containing $n$, and $\binom{n-1}{k-1}$ containing $n$. Suppose we want to encode combinations not containing $n$ before combinations containing $n$. We work recursively. If the input set $S$ doesn't contain $n$, then we recurse on $S$ as a combination in $[n-1]$. If it does contain $n$, we recurse on $S \setminus \{n\}$ as a combination in $[n-1]$ (of size $k-1$), and add $\binom{n-1}{k}$ to the result.

Here is Python code for the procedure:

def encode(n, k, S):
    if n == 0:
        return 0
    if n not in S:
        return encode(n-1, k, S)
    S.remove(n)
    return encode(n-1, k-1, S) + choose(n-1, k)

The function choose (not supplied) should compute the Binomial coefficient. You can also decode the resulting code:

def decode(n, k, C):
    if n == 0:
        return []
    if C < choose(n-1, k):
        return decode(n-1, k, C)
    C -= choose(n-1, k)
    return decode(n-1, k-1, C) + [n]


Why is the inverted index called so and not simply index? In my notes is represented like this:

From wikipedia:

In computer science, an inverted index (also referred to as a postings
file or inverted file) is a database index storing a mapping from
content, such as words or numbers, to its locations in a table, or in
a document or a set of documents.

Where is the inversion with respect to a normal index (like the one found at the end of books)?

Index: (in a book or set of books) an alphabetical list of names,
subjects, etc. with reference to the pages on which they are
mentioned.

Am I missing something? Like a nuance of the meaning of the name due to the fact that english is not my main language.

Here is an array:

A[0] = Alice
A[1] = Bob
A[2] = Charlie

Here 0,1,2 are indices.
Now suppose that we want to know which index contains a given word. Then we use a dictionary:

D[Alice] = 0
D[Bob] = 1
D[Charlie] = 2

This is an inverted index (according to your Wikipedia quote).

The word index has different meaning in different contexts:

Technical books often have an index of terms at the end.
The Catholic church held an index of forbidden books.
In economics, there are financial indices.
In computer science, an index is usually an integer used to index into an array.


Page Replacement optimal verses MRU A computer has twenty physical page frames which contain pages numbered 101 through 120. Now a program accesses the pages numbered 1, 2, …, 100 in that order, and repeats the access sequence THRICE. Which one of the following page replacement policies experiences the same number of page faults as the optimal page replacement policy for this program?

(A) Least-recently-used

(B) First-in-first-out

(C) Last-in-first-out

(D) Most-recently-used

=============================================================

First of all how many Page Faults are there in optimal PRA?

I'm getting as following -

100 PF in 1st access of 100 pages.

80 PF in 2nd access of 100 pages.

80 PF in 3rd access of 100 pages.

Totally = 100+80+80 = 260 PF are there out of total 300 references of 100 pages.

Is that correct? whereas some people are having like -

100+(100-19)+(100-19) PF and some are going for 4th round. why the need to go to 4th access of 100 pages?

As far as number of sequences are concerned, it depends on how you read the problem statement.

  Now a program accesses the pages numbered 1, 2, …, 100 in that order,
  and repeats the access sequence THRICE.

From this line, I perceive that program has accessed this sequence once and again repeats this sequence thrice. So, total four times.

But, I think here number of sequence is not that important. We just need to find page replacement pattern of the given policies in the options, which is similar to Optimal Page Replacement policy.

For the above sequence, which is

  1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100 1 2 3 4 .... 99 100

Both First-In-First-Out and Least-Recently-Used policies perform the same way and give same number of page faults. (Not always, but for this sequence)

For both of these policies, the number of page faults are 400. A program will make a replacement for every new page. For the first 20 pages from sequence, program replace the older pages 101 to 120. Then for every new page, a replacement is made in similar fashion.

21st page in place of 1st page

22nd page in place of 2nd page and so on.

After every 20 iteration, a frame will contain entire new set of pages.

Similarly, Last-In-First-Out performs the same way as Most-Recently-Used for this sequence and gives same number of page faults as Most-Recently-Used policy.

Here every time the last page is replaced by the new one.

So, 120th page is replaced by 1st page

1st page is replaced by 2 and so on.

So, here also 400 page faults occurs.

But, I don't think any of the given policy performs the same way as Optimal PR.

In Optimal PR, we'll have 100 + (100-19) + (100-19) + (100-20) = 342 page faults.


Approximate a float using a minimal fraction This sounds like it's probably a well-known problem, but I haven't been able to find references to it by searching.

Given a floating point value $x$ and an error range $\varepsilon$, how can I efficiently find a minimal positive integer $q$ such that $\left|x - \frac{p}{q}\right| < \varepsilon$ for some integer $p$?

The approach that seems obvious is to iterate from $q = 1$ upward (skipping composite numbers), computing $p := round(x * q)$ and checking whether $\left|x - \frac{p}{q}\right| < \varepsilon$. But I'm wondering if there's a smarter way.

The partial convergents of the continued fraction of $x$ consists of all the best rational approximations of $x$; see Wikipedia, for example. A best rational approximation of $x$ is a rational number $p/q$ such that $\left|x-\frac{p}{q}\right| \leq \left|x-\frac{p'}{q'}\right|$ for all $q' \leq q$. Your $p/q$ is in particular a best rational approximation, so it would be one of the convergents.


Non-Deterministic Turing machine vs Probabilistic Turing Machine vs Deterministic Turing Machine What is the difference between a Non-Deterministic Turing machine, Probabilistic Turing Machine and a Deterministic Turing Machine ?

A Turing machine is a computation model in theory only, able to simulate any computer algorithm. By formally defining this model mathematically, Its possible to draw conclusions and limits regarding the abilities of our computers.

There are many more models, and much more literature about each of them, but below is a short review of the three mentioned in your question

Deterministic Turing Machine (DTM):

For any given state $Q_i$ the machine is presently at, and for any given symbol under the input alphabet $\Sigma$ the head is at, there is exactly one action the machine can perform.

It means in every step, the transition (and write operation) is well established, or deterministic, under a certain set of rules predefined into the machine.

Non-Deterministic Turing Machine (NTM):

A machine like the DTM, with the important exception that in every step, it may make more than one transition. So for input symbol $s$ and state $Q_i$, it may transition to to $Q_j$, but it may also transition to $Q_k$ and so forth.

Since in no step is the transition well established, we say the NTM "guesses" the best transition that eventually leads to an accepting state $Q_{F}$ (if such a transition path exists).

Imagine being in a maze, and constantly having to decide whether to turn left, or right. If you always guessed the correct choice, then you will find the find the quickest way out possible (if there was one).

Probabilistic Turing Machine (PTM):

A machine like the NTM, only its transition is subject to a probabiliy function (that is well established) and not "guess" like the NTM. For example, suppose the current input symbol is $s$ and state $Q_i$, a transition can be defined as follows:

Flip 2 coins.

If the result is ($head$, $head$), move to state $Q_j$
Else, move to state $Q_k$

Unlike the DTM, we cannot say we know how the machine will act given the situation, since we don't know what the coin flip will show. However, its also not as "lucky" as the NTM, and we can often measure accurately the probability of a mistake.

Further reading on probabilistic classes:

Randomized polynomial time class

Bounded error polynomial time class


What is "rank" in a binary search tree and how can it be useful? I am having a bit of trouble wrapping my mind around what a ranked binary search tree is and why having a rank is important. I am hoping that someone can clarify a few things for me.

What I have looked into:
From what I have read, a ranked binary search tree is a tree where each node has a variable "rank" attached to it.

In the question here, someone states that in order to determine the rank of a node in a binary search tree you can do the following:

  Start the rank at zero. As the binary search proceeds down from the
  root, sum up the sizes of all the left subtrees that the search skips
  by. Also include the nodes along the path less than the searched item.
  These are just the parents of right children on the search path.

Questions:
The rank seems like it is just a number that reflects how many nodes it takes (plus one for the root) to get to a particular node in a tree. Is that right? It didn't seem right to me only because that seems like that would just make the rank of a node the same as the depth of a node.

Also, what is the difference between "weight" and "rank"? If a node in a particular binary search tree has a weight attached to it, is that just a random value assigned to it by the user/developer?

Lastly, what is the point of having a rank? My first thought is that it can be used to indicate priorities. However, in that case, why wouldn't the developer just use weights?

Other things:
I also took a look at the site here. It explains how to calculate rank, but I'm still not convinced I understand the concept yet.

Thanks for any help.

According to this book (Chapter 3.2), a node in a BST has rank $k$ if precisely $k$ other keys in the BST are smaller. So, if you order all the BST nodes according to their keys, then each node with rank $k$ will take $k$-th place.


Why are FPGA's less efficient than fully hard-coded ASIC's? A Field-programmable gate array (FPGA) is generally more efficient than using a "hard-coded" processor like a CPU or GPU for highly specific applications like bitcoin mining or doing structurally identical computations many times over.

however, FPGA as far as I know are beaten in computational efficiency by Application specific integrated circuits (ASIC's) that are specifically designed to the particular problem (again take Bitcoin mining as an example).

My question is: What are the sources of the efficiency gain of ASIC's over FPGA's, given that FPGA's already allow you to setup the circuitry for the specific problem at hand?

Functionality of FPGAs in very coarse lines:
At the core functionality of FPGAs are small memories called Look Up Tables (LUTs). An FPGA instead of actually compute in hardware the output of a function, say f(x), what it does is store in these small memories all possible outputs of f. So next time an input x is given fpga passes x as address in a small memory and "looks up" the answer. As it happens with all kind of memories the larger the memory the bigger the delay. So FPGAs are consisted of "a lot" of very small LUTs distributed all over their surface. Every LUT "solves" a tiny subproblem and passes the answer to subsequent LUTs for further processing (answers). Loading the LUTs with different answers and connecting them in a programmable way gives FPGAs the ability to solve any kind of problem.

LUTs are interconnected each other in an hierarchical manner. That is, as it happens with computer networks, or with buildings, it would be infeasible to connect via road each building with every other, buildings are interconnected in an hierachical manner where you have small streets, bigger streets, highways etc. So to route a package from A to B you don't have a direct-short/fast-link between A and B, but instead you may use a lengthier route which is consisted of various kinds of roads.
According to the previous analogy LUTs are the buildings and roads are the signal interconnections between LUTs. In FPGAs LUTs which are a kind of processing units are fixed in specific places, so in order to pass a signal from one LUT to another you have to follow the specific route hierarchy of FPGA. Instead in an ASIC you can place processing units in more efficient manner, and also make direct interconnection where is critical to do so, in order to minimize the delay.
Even the simplest form of processing in an FPGA (consisting only of programmable logic) has to be in the form of a LUT. For example to compute the output of a 2 input AND gate you would need a LUT. In an ASIC you would need just an AND gate. The total circuitry of the LUT certainly has greater delay that just an AND gate of the same technology.
To sum it up the sources of inefficiency of an FPGA are the

routing delay you might have due to fixed routing hierarchy and
circuitry overhead of LUTs themselves

Have in mind also that an FPGA is actually an ASIC, in which the "specific application" is to be programmable!


Project to L1 ball of specified radius The task

If $x \in \mathbb{R}^d$ is a $d$-dimensional vector, recall that the $\ell_1$ norm of $x$ is given by

$$||x||_1 = |x_1| + |x_2| + \dots + |x_d|.$$

The $\ell_1$-ball of radius $\lambda$ is the set of points $x$ such that $||x||_1 \le \lambda$.

Consider the following algorithmic task:

Input: $x \in \mathbb{R}^d$, $\lambda > 0$
Desired output: $y \in \mathbb{R}^d$ such that $||y||_1 \le \lambda$ and $||x-y||_2$ is minimized

In other words, given $x,\lambda$, the goal is to project $x$ to the nearest point in the $\ell_1$-ball of radius $\lambda$.

This problem comes up when we want to learn a linear SVM with L1 regularization using stochastic gradient descent.

A proposed solution in the literature

The following paper proposes a solution:

D. Sculley, Matthew Eric Otey, Michael Pohl, Bridget Spitznagel, John Hainsworth, Yunkai Zhou.  Detecting Adversarial Advertisements in the Wild.  KDD 2011.

They propose an iterative algorithm $A$, with the property that iterating $A$ on $x$ eventually converges to the desired $y$: i.e., the sequence $x,A(x),A(A(x)),A(A(A(x))),\dots$ converges to the desired value $y$.  Their algorithm is in Figure 2 and is as follows:

Algorithm $A$, with input $x$:
 1. $c := \max(\lambda - ||x||_1,0)$
 2. $d := ||x||_0$
 3. $\tau := c/d$
 4. for each non-zero element $i$ of $x$, do:
 5.     $\qquad s := \text{sign}(x_i)$
 6.     $\qquad x_i := s \times \max(|x_i - \tau|,0)$
 7. return $x$

However, I don't see why this algorithm works.  For instance, at minimum we'd want the output of this algorithm to always satisfy $\lambda \le ||A(x)||_1 < ||x||_1$, but this doesn't seem to hold.  This algorithm often does nothing to the input if $||x||_1 > \lambda$, and it typically shrinks $x$ if $||x||_1 \le \lambda$; this seems backwards (we want the reverse).

Also, $\max(|x_i - \tau|,0)$ is an odd expression, as we always have $\max(|x_i - \tau|,0) = |x_i - \tau|$, so I don't understand why the max is there.

My question

Does the algorithm from Sculley et al. actually work?  Is there a typo or an error in this algorithm?  If so, can it be fixed?

There are two typos in their algorithm.  Fixing them yields an algorithm that does work.  Here's the fixed algorithm:

Algorithm $A$, with input $x$:
 1. $c := \max(||x||_1 - \lambda,0)$
 2. $d := ||x||_0$
 3. $\tau := c/d$
 4. for each non-zero element $i$ of $x$, do:
 5.     $\qquad s := \text{sign}(x_i)$
 6.     $\qquad x_i := s \times \max(x_i - \tau,0)$
 7. return $x$

The first typo was in line 1: $\lambda - ||x||_1$ should have been $||x||_1 - \lambda$.

The second typo was in line 6: $|x_i - \tau|$ should have been $x_i - \tau$ (no absolute value).

With these changes, everything makes sense and the algorithm now seems to work correctly.  For instance:

If $||x||_1 \le \lambda$, then $A(x)=x$ (since $c=0$ in this case).
If $||x||_1 > \lambda$, then $\lambda \le ||A(x)||_1 < ||x||_1$ (since each $x_i$ gets mapped to something whose absolute value is smaller).
The sequence $x,A(x),A(A(x)),\dots$ converges to the desired $y$.
Convergence should typically be pretty fast.  In particular, if $\max_i |x_i|$ is not too much larger than $\lambda / ||x||_0$, then this procedure should converge exponentially fast.

(There are definitely some bad cases where this procedure converges very slowly: e.g., if $x$ has many elements whose absolute value is tiny but non-zero, and a single element whose absolute value is enormous.  In this case, the algorithm still converges, but it requires $\Theta(||x||_0)$ iterations, which might be as bad as $\Theta(d)$.  However, these bad cases are pretty rare.)


Among a number of sets, how to find the one that includes the highest number of other sets? I have a large number of sets, A, B, C, ... where each set includes a few integers. I would like to find the set that includes the highest number of other sets.

A brute-force solution is to compare each set with all other sets and count the number of sets that are included in this set. Finally, pick the set with the highest count. This brute-force solution has a quadratic complexity and is very slow for my large number of sets. Is there a better solution with lower complexity?

From the answer linked in D.W.'s comments, you wont be able to do this in less than quadratic time without more information.  The problem you are trying to solve is more difficult than the Subset Containment problem, which is quadratic with the number of sets.  We can, however, explore ways to make the average case better.

The first step is to identify if there is any pattern to the data which can be leveraged.  For example, if the sets are random, then you can leverage that to find better runtimes with some partitioning tricks.  If the values all happen to be less than 64, you could encode each set as a 64-bit numbers and do comparisons that way.

The most generic approach, however, is to try to minimize comparison time.  The first step would be to sort the elements in each set.  That makes it so you can always determine if one set is a subset of the other in linear time by scanning it.

Beyond that, you could look at bloom filters.  A bloom filter is basically an array of bits, and each bit corresponds to the result of hashing the data differently.  What is nice about bloom filters is that they allow you to combine values using OR logic.  Use a bloom filter to hash each of the elements in a set, and OR the results together.  Now it is easy to see that if you have a set $S_1$ and $S_2$ such that $S_1\subseteq S_2$ and you have their corresponding bloom filter arrays $B_1$ and $B_2$, then every bit in $B_1$ must also be set in $B_2$ (i.e. $B_2\land B_1=B_1$).

Thus, you will have to do $O(n^2)$ comparisons of the bloom filter arrays (which are bit-fields, so you can process them 32 or 64 bits at a time natively).  If $B_i\land B_j=B_j$ for any $i, j$, then you have a potential subset.  It's possible that you just had a bloom filter collision, so we have to test the arrays, which is linear with the size of each array.

Thus in the worst case, we don't save any time, but in the average case, we may be able to dramatically reduce the cost of comparing the sets.

There's a few more steps involved to make sure we don't saturate the bloom filters, but those can only be worked out when you know a little about the sizes of your sets, which I do not.


Minimum and maximum of sum of inverse degree of a graph Suppose we have a simple undirected graph $G(V,E)$, where $V$ and $E$ are the set of vertices and edges respectively. we denote $d(v)$ as the degree of a vertex $v \in V$. I am interested to find closed form or a tight bound  of the following quantity

$$
D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)}
$$

For example, suppose we have a complete graph with $n$ vertices. Then $D$ becomes $$ D = \frac{n(n-1)/2}{2(n-1)} = n/4$$.

For a path graph with $n$ vertices ($(n-1)$ edges) $D$ is $ \frac{(n-3)}{4}+2/3 $. My question is

Is there any closed form of $D$ for general graph that involves $|V|$?
If not is there any tight lower bound on the sum?
Can we claim something like that the $D \geq |V|/k$ where k is a constant and $k<<|V|$?

*Yuval conjectured that $D \geq 1−1/n$ for a connect graph with $n$ vertices.

Nice question!

There is no simple closed form of $D$ for general graphs that involves $|V|$ since $D$ can take at least two different values for any connected graph with more than 2 vertices. $D=1-\frac1{|V|}$ for a start graph and $D=\frac{|V|}4 > 1-\frac1{|V|}$ for a cycle graph. In fact, I would believe that the number of different values of $D$ for a graph of $n$ vertices grows exponentially with respect to $n$.

Yuval's tight lower bound
Claim: $D \geq 1−1/n$ for a connect graph with $n$ vertices, where the equality holds for and only for star graphs.
Proof. Let $G$ be a connect graph with $m$ edges. Since $G$ is connected, $m\ge n-1$, where the equality holds for and only for tree graphs. Let $e=\{u,v\}$ be an edge in $G$.
$$\begin{aligned}
d(u)+d(v) &= \Sigma_{s\in E,\, s \text { contains u}} 1 + \Sigma_{s\in E,\, s \text { contains v}} 1 \\
&= (1 + \Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1) + (1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1)  \\
&= 2 + (\Sigma_{s\in E,\, s \text { contains u},\, s\neq e} 1 + \Sigma_{s\in E,\, s \text { contains v},\, s\neq e} 1)  \\
&\le 2 + \Sigma_{s\in E,\, s\neq e} 1\\
&= 2 + (m -1)\\
&= m +1
\end{aligned}$$
The inequality above holds since the only edge that contains both $u$ and $v$ is $e$. The equality $d(u)+d(v)=m+1$ holds when every edge besides $e$ has a common vertex with $e$.
So,
$$
D = \sum_{e=\{u,v\} \in E} \frac{1}{d(u)+d(v)} \ge m\, \frac1{m+1} = 1 - \frac1{m+1} \ge 1-\frac1n
$$
The equality $D=1-\frac1n$ holds when there are $n-1$ edges in total and every two edge has a common vertex, which means the graph is a star graph.

There is no positive constant $k$ such that $D \geq |V|/k$, since $|V|/k$ goes to infinity while $1-1/|V|$ stays below 1 when $|V|$ goes to infinity.


Amount of expected loop iterations when searching an array by random index Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n

If we have a search algorithm like so:

while true:
  i := random(1, n)
  if A[i] == x
    break

random(a,b) picks a number uniformly from a to b

From this we know that the chances of finding x and terminating the program is k/n with each iteration. However what I would like to know is what would be the expected value for the number of iterations or more specifically the amount of times the array was accessed in this program given the array A as described above.

Let $N$ be the geometric R.V. that returns the number of times the array was accessed in order to search for the element, $A[x]$ until we successfully find it. We want to know $\mathbb{E}[N]$.

We can view the iterations of the while loop as a sequence of IID Bernoulli trials, each with a probability $p$ of succeeding, and $q = 1 - p$ of failure. Given the question, we want to know how many trials are needed to obtain a "success" which would be finding the element $A[x]$ thus the while loop terminates.

Since the $\Pr\{N = k\} = q^{k-1}p$, we have that $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \: q^{k-1}p$.

Thus, $\mathbb{E}[N] = \dfrac 1p$ where $p = \dfrac kn$ so $\mathbb{E}[N] = \dfrac nk$.

So on average, it takes $\dfrac nk$ accesses before we find the element, $A[x]$.


Why isn't the Swift programming language type inference more aggressive? Couldn't the type inference in Apple's new programming language Swift had been done more aggressive? For instance why can't the return type of a function be deduced?

func sayHello(personName: String) -> String {
   let greeting = "Hello, " + personName + "!"
   return greeting
}

I don't understand Swift's typing system yet, so I can only speculate, but I imagine that it's for the same reason that Scala doesn't have full type inference: nobody knows how to do it in a pragmatically viable way. The combination of parametric polymorphism and subtyping is deadly from the point of view of algorithmic complexity.


Are all MST minimum spanning trees reachable by Kruskal and Prim? I believe this is true but have not been able to get a formal proof for either. But is it true that any minimum spanning tree is reachable by applying Kruskal's algorithm? Similarly, is this true for Prim's algorithm?

EDIT: To be more precise, I want to know if given an MST for a connected, undirected, weighted graph, is it guaranteed that there is a sequence of steps using Kruskal or Prim which generates this MST. E.g. There are different choices for Kruskal when there are multiple edges with the same weight. Similarly for Prim.

As indicated by Raphael's comment and j_random_hacker's comment, the answer is positive. In fact, any MST is reachable by any MST algorithm with some minor exceptions.

For a graph $G$, two weight functions on all edges (to real numbers) are defined as (weakly) comparison-compatible (to each other) if we can extend the strict weak ordering on the edges induced by either weight function to the same strict total order. That is, we can devise consistent tie-breaking rules with each weight function so that the result of comparison of any two edges by one weight function and its tie-breaking rules is the same as the result by the other weight function and its tie-breaking rules.

  Lemma 1: Let $w_1$ and $w_2$ be two weight functions. The following five statements are equivalent to each other.

  $w_1$ and $w_2$ are comparison-compatible.
  In any set of edges, there is a common lightest edge by $w_1$ and by $w_2$.
  In any set of edges, there is a common heaviest edge by $w_1$ and by $w_2$.
  There exists a weight function $w_3$ that assign distinct weights to distinct edges such that $w_3$ is comparison-compatible to $w_1$ and to $w_2$.
  for any edge $e_1$ and $e_2$ such that $e_1$ is lighter than $e_2$ by one weight function, $e_1$ is as light as or lighter than $e_2$ by the other weight function.

Proof of lemma 1 is left as an easy exercise.

  Lemma 2: Let two weight functions $w_1$ and $w_2$ be such that if $e_1\lt_{w_1}e_2$, then $e_1\lt_{w_2}e_2$. Then they are comparison-comptible.

(Hint to) Proof: One approach is to verify the condition 5 of lemma 1. Another approach is to verify the condition 2 of lemma 1 by showing that in any set of edges, a lightest edge by $w_2$ is also a lightest edge by $w_1$,

A comparison-based algorithm on a graph $G$ is defined as comparison-compatible if for any two (weakly) comparison-compatible weight functions on all edges, we can run the algorithm with one weight function in a way that can be repeated without any change with the other weight function. In particular, those two runs of the algorithm will have the same output.

Please note that most if not all MST algorithms can be stated in two flavours. The first flavour assumes that distinct edges of $G$ have
distinct weights, which is used when the main concern is to find one MST (which is in fact also the unique MST). The second flavour allows distinct edges of $G$ to have same weights. Of course in this answer, where the main concern is to find all MSTs, we will only care MST algorithms in the second flavour.

A comparison-compatible MST algorithm can find all MSTs.

To prove the above proposition, we just need to adapt slightly the section, "Kruskal can find every MST" in the computation of the number of MSTs. For any MST $m$ of $G$ with weight function $w_1$, choose a positive weight that is lighter than the absolute difference between any pair of unequal edge weights. If we subtract that weight from the weight of each edge in $m$ without changing weights of other edges, we obtain a new weight function, say, $w_2$. If edge $e_1$ is lighter than $e_2$ by $w_1$, $e_1$ must be lighter than $e_2$ by $w_2$ as well. By lemma 2, $w_1$ and $w_2$ are comparison-compatible. Note that $m$ is the unique MST with $w_2$. (One way to show this uniqueness is to prove that whenever the weight of one MST edge is reduced, any MST with the new weight function must contain that edge.) So any run of the algorithm on $w_2$ will find $m$. Because the algorithm is comparison-compatible, we can run the algorithm the same way with $w_1$ or with $w_2$. Since that run will find the unique MST, $m$ with $w_2$, it will find $m$ as well with $w_1$.

Every MST algorithm is comparison-compatible

The above proposition sounds overbroad. Well, by every MST algorithm, I mean any general comparison-based MST algorithm that I have seen, excluding those apparently pathological ones such as wrong or having unnecessary steps. Since a comparison-compatible MST algorithm can find all MSTs, every MST algorithm can find all MSTs. In particular, each of  the four classic MST algorithms, namely Borůvka's, Prim's, Kruskal's and reverse-delete algorithms can find all MSTs.

Here are three more comparison-compatible MST algorithms.

the delete-heavy-edge algorithm. Start with all edges. Repeatedly find a cycle and remove one of its heaviest edge until no cycle remains.
the add-non-heavy-edge algorithm. Start with the empty set. Iterate through all edges. Each edge is added and, if a cycle is formed, remove one of it heaviest edges.
the replace-by-lighter-edge algorithm. Start with any spanning tree $T$.
Find the cycle in $T$ plus an edge $e$ not in $T$. If an edge $t$ in that cycle is heavier than $e$, remove $t$ from $T$ and add $e$ to $T$. Repeat until we cannot reduce the weight of $T$ any more.

The following MST algorithm is not comparison-compatible.

the degree-biased Kruskal's algorithm, which is Kruskal's algorithm with the following modification. Suppose when we are going to remove an edge with the minimum weight from $S$ as in the wikipedia's description of Kruskal's algorithm, we have multiple edges with the minimum weight to choose. The edge we choose to remove will be an edge whose sum of degrees of its two vertices is the largest among all choices. This algorithm cannot be comparison-compatible since it does not find the MST $\{ab,bc,cd\}$ of the graph with vertices $a,b,c$, and edge $ab$ of weight $1$ and edges $bc, cd, db$ of weight $2$. This algorithm is considered pathological because of that unnecessary modification.

Please note that all eight MST algorithms mentioned above are comparison-based.

How to show an algorithm is comparison-compatible?

I will use Kruskal's algorithm as an example. Here is the description of Kruskal's algorithm (in the second flavour) on a weighted undirected connected graph $G$.

create a graph $F$ that has the same vertices as $G$ but without edges. So $F$ is a forest of separated trees of a single vertex.
create a set $S$ containing all the edges in the graph.
while $S$ is nonempty and $F$ is not yet spanning

select an edge with minimum weight from $S$.
remove that edge from $S$.
If that edge connects two different trees then add it to the forest $F$, combining two trees into a single tree

output $F$.

Let $w_1$ and $w_2$ be two comparison-compatible weight functions on $G$. Kruskal's algorithm involves the weight function only in the step that "select an edge with minimum weight from $S$". The condition 2 of lemma 1 tells us that we can select a common lightest edge in this step. We can then check easily by induction that we can run all steps in the same way with $w_1$ and with $w_2$. So Kruskal's algorithm is comparison-compatible.

An algorithm is comparison-compatible if, in loose terms, it can be described in three kinds of steps.

do something that does not involve weight.
select an edge with the minimum weight in a given set of edges
select an edge with the maximum weight in a given set of edges

This sufficient condition covers Borůvka's, Prim's,  Kruskal's, reverse-delete, delete-heavy-edge and add-non-heavy-edge algorithm. Note that in order to fit this sufficient condition, we may have to change certain  descriptions of an algorithm without affecting the set of reachable MSTs. Because of the exception of the degree-biased Kruskal's algorithm being comparison-compatible, let me emphasize this sufficient condition is described in loose terms


The 'directionality' of reductions? I've been finding myself a bit confused with the direction of reductions used to show that certain languages are not recursive. For example, let us say we want to determine if the Halting Problem ($HALT_{TM}$)is undecidable. I know we can assume that it is decidable and then try to build a decider for the acceptance problem, which is impossible. But though we are using the Acceptance Problem ($A_{TM}$) to help solve the decidability of the Halting Problem, we have reduced the Acceptance Problem to the Halting Problem, not the other way around, right?

I sometimes get a little bit confused when I encounter questions that ask me to deploy a reduction; I will be asked to reduce language $x$ to $y$, but what that means is that $y$ is a simpler instance of a problem of $x$, right (or at least should be)? I'm assuming it's impossible to reduce a simpler version of a problem to a more complex version of a problem, am I right in believing that?

Don't worry – everybody gets confused by the direction of reductions. Even people who've been working in algorithms and complexity for decades occasionally have a, "Wait, were we supposed to be reducing $A$ to $B$ or $B$ to $A$?" moment.

Reducing $A$ to $B$ produces a statement of the form "If I could solve $B$, then I'd also know how to solve $A$". "Solve" in this sense could mean "compute using any Turing machine", or "compute in polynomial time" or whatever other notion of solution your context requires.

This may seem counterintuitive, since "$A$ reduces to $B$" implies that solving $B$ is at least as hard as solving $A$, so you haven't reduced the difficulty. However, you can think of it as reducing the number of problems you need to solve. Imagine that, at the start of the day, your goals were to find an algorithm for $A$ and an algorithm for $B$. Well, now that you've found a reduction from $A$ to $B$, you've reduced your goals to just finding an algorithm for $B$.


Get a fixed-size family of k-element subsets I have an n-element set, and I want to consider families of its k-element subsets of fixed size s. For example, if n = 3, k = 1, s = 2, we have these families:

{{1}, {2}}, {{1}, {3}}, {{2}, {3}}

In my problem n, k, s are not so small, e.g. s = n = 50, k = 20.

Let us say all such families are ordered lexicographically (or really in any clearly stated order). I want to have an efficient way to get a family by its number.

I have only a following idea: enumerate all k-element subsets of n-element set (there is an efficient algorithm to get i-th element by i). Then enumerate all s-element subsets of comb(n, k)-element set, using the same operation. Now we need to generate a number in range (0, comb(comb(n, k), s)) and turn it firstly to the number of s-element subset and then to a family of k-elements sets.

However, I want to know, if there is a more beautiful approach than just generating first combination and then second combination by its numbers.

In general, what you are looking for is a combinatorial number system (of degree $t$) , i.e., a correspondece between $\mathbb{N}$ and all $t$-combinations.

There is a large number of algorithms for $t$-combination generation from the last (at least) 50 years. In particular, the operations you are interested in are typically called rank and unrank.

For much more than what the Wikipedia article contains at the time of writing, you can have a look at say the book of Knuth [1] or the one by Kreher and Stinson [2]. Knuth's book contains pseudocode that is straightforward to write in your favorite language, and the nook of Kreher and Stinson is accompanied by source code (in C) that can be found online as well.

[1] Knuth, Donald E. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1. Pearson Education India, 2011.

[2] Kreher, Donald L., and Douglas R. Stinson. Combinatorial algorithms: generation, enumeration, and search. Vol. 7. CRC press, 1998.


Is Euclidean TSP strongly NP-hard Is Euclidean TSP strongly NP-hard? What I mean is if it is NP-hard with weights specified in unary?

Can someone provide a reference?

Yes, Papadimitriou in his "The Euclidean Traveling Salesman Problem Is NP-complete" paper reduces from Exact Cover to Euclidean TSP.

All the coordinates of the points are of polynomial magnitude.

And the required precision for the $L_0$ value in page 243 is to be able to distinguish between $a$ and ${(a^2+1)}^\frac12$. And near the end of page 241, he wrote "An adequate value of $a$ is 20." So the required precision is finite. Since you only have $n(4a + 13 + 2^\frac12)$, that would only magnify the difference.

All the page numbers above are in the proceedings containing his paper and can be seen once you have downloaded the paper.


Optimal Binary Search Trees Knuth Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica 1 (1): 14–25,doi:10.1007/BF00264289

Please have a look at this paper, specifically page 18 in which he tries to prove his lemma that $R_{0,n-1} \leq R_{0,n} $ here $R$ refers to the minimal optimal node which will be the root of the binary tree containing elements $a_{0} ... a_{n} $ .

I understood the idea of the proof using induction that for some $k \,  j_{k}=i_{k} $ . Now the next part of the proof is cutting and replacing,I have understood perfectly till there. What i don't understand is how $F''$ weighted path length is equal to weighted path length of $F'$ for all $a_{n}$. Can anyone please give me a hint or a solution to that.

I am thinking if jk = ik, let's denote jk=ik=m, then we think of subsequences of [0,m-1] and [m+1,n], treat [m+1,n] as a standalone tree. And according to the paper, T and T' will be of same weighted path length if αn = α. So let's make a tree of subsequence [m+1,n] with last item being α, with weighted path length sum being Tk. And then replace the right-subtree of jk/ik with Tk for both T and T'.
Let's denote the weighted path length sum of [0, m-1] of T and T' being T0 and T0'. Because jk = ik, the levels of T and T' are both k. SoC(T) = T0 + k*Ak + Tk(starting from level k+1); C(T') = T1 + k*Ak + Tk(starting from level k+1); And C(T) should be equal to C(T'). So T1 = T1'
Replace right subtree of ik of T with right subtree of jk of T' will yield T'' with same weighted path length as T'.
PS: actually I don't quite know how it proves j2<=i2, j3<=i3 using induction and left-right symmetry, anyone can help answer that?


Tips on speeding up hierarchical linkage clustering algorithm I implemented a hierarchical linkage algorithm for a set of 5,000 points. Each point is defined with a longitude and a latitude.
I read about this algorithm here.
These are the steps:

Compute distance matrix between all points (great-circle distance, not Euclidean)
Find the pair of points with the minimum distance between them
If the minimum distance is larger than a threshold value

the algorithm finishes

Otherwise

The two points are merged, and removed from the list of points.
The center point of this pair is added to the list of points

Go back to 1

I do not consider single, complete, etc. types of linkage, since the points are substituted by a central point. Therefore, the distance is just the distance between all points (instead of point-cluster).
It runs okay for small amount of pairs, but it takes 1 second per iteration as soon as I run it for 5,000 points; potentially 83 minutes although it probably stops halfway due to the distance threshold.
Although I use Haversine formulation in the calculation of distances, it does not change much if I use a simple Euclidean approach; it then takes 1 second for 3 iterations.
Am I making a mistake in understanding and implementing this algorithm? If not, are there ways in which this could be sped up?
I am using MATLAB R2018b.
Thank you!

Yes.  After you merge two points, you can update the distances of just the affected nodes, without having to recompute all pairs of distances again.  That will be vastly faster.