Chaitin's elegant programs I need help to understand Chaitin's elegant program proof. An elegant program is the shortest program that produces a given output.
Here is the proof:

Construct a program $B$ that takes as input a number $N$ and enumerates all possible programs $P_k$ longer than $N$. $B$ runs the elegance tester $\mathrm{ET}$ on each enumerated program $P_k$ in turn until it finds some $P_k$ which $\mathrm{ET}$ claims is elegant. $B$ then runs that $P_k$, thus producing the same output as that $P_k$.
Lemma: B must produce some output.
Proof: There are an infinite number of elegant programs, as noted earlier. So if $\mathrm{ET}$ works as assumed, $B$ must eventually find one of those elegant programs whereupon it will produce that program's output.
Now run $B$ with $N$ set to $|B| + 1$ (See note 1). (This is the "threshold size" mentioned in the theorem.) $B$ now will produce the same output as some program $P_k$ which $\mathrm{ET}$ claimed was elegant. But $P_k$ is longer than $B$, so $P_k$ cannot be elegant because $B$, which is shorter, produced the same output. Therefore, $\mathrm{ET}$ was wrong when it claimed $P_k$ was elegant. QED.

My question is: The proof begins with a program $B$ that is a program "that takes as input a number $N$ and enumerates all possible programs $P_k$ longer than $N$" But because of the halting problem such a program is not possible, so the proof starts dead? There is something I'm not understanding here.

The algorithm $B$ is described in a mildly sloppy way. You can look at it as a two-step process:

Find suitable $P_k$.
Run $P_k$.

Now, step 1 can be done one program at a time since the set of all programs is recursively enumerable and we assume that a recursive (and total) elegance tester $\mathrm{ET}$ exists. Note that we use $\mathrm{ET}$ as an oracle.

So, the algorithm is this:

def B(N,x)
  E = program_enumerator

  do
    P = E.next
    if ( length(P) <= N )
      continue
  while ( !ET(P) )

  return P(x)
end

Why is this a proof? We call the underlying technique proof by contradiction. Here is what happens:

Assume that a general, total elegance checker $\mathrm{ET}$ exists.
Under this assumption, construct a (computable!) program $B$ that is equivalent to a program $P$ so that $B$ is smaller than $P$ but $\mathrm{ET}$ says that $P$ is elegant (i.e. smallest).
Since this is a contradiction, the assumption has to be false; that is, such an elegance checker can not exist.


LR(1) parsing, problem with look ahead symbols I understand the concept of LR(1) parsing and lookahead symbols. I have the solution to the exercise and it does not agree with my solution.

I'm trying to fill the LR(1) parsing table for the grammar below:

S->xAz
S->BAx
A->Ay
A->e
B->yB
B->y

Ι don't have to extend the grammar since S does not appear in any right hand side of any rule.

First(A)=y,e
First(Ax)=x,y
First(B)=y
First(Ay)=y

Lookahead symbols in brackets.

So,
I0 = Closure(S->.xAz($) , S->.BAx($) ) =

S->.xAz($)
S->.BAx($)
B->.yB(x,y)
B->.y(x,y)

When i try GOTO(0,x) i think that i should go to:

S->x.Az($)
A->.Ay(z)
A->. (z)

To find the lookahead symbol for A->. & A->.Ay i take First(z). But the official book solution says the lookeahead is (z,y).
Where does that y comes from?

Thank you in advance!

Since $A\to .Ay$ is in the state constructed for $GOTO(0, x)$, $A\to .A(y)$ and $A\to .(y)$ are also in that state. These combine with the other items for the same productions, which have lookahead $z$.


How to Determine Existence of Turing Reducible Languages? Are finite and recursive instances of $L$ possible with the following constraints?

$\text{L $\subseteq$ {0,1}*}$ and $L \leq HALT \leq \overline L$ where $\overline L = \{\text{ x $\in$ {0,1}* : x $\notin$ L }\}$.

NOTE: Raphael and Yuval kindly pointed out that I was overlooking $\overline L$ is undecidable. Aside from this oversight, are there any other issues, e.g. conceptual misunderstandings, logical fallacies, etc. in the explanation below?

As I understand it:

A finite instance of $L$ is possible. Since the language is finite, an evaluating Turing Machine (TM) could not loop indefinitely on input, and consequently would halt either in an "accept" or "reject" state. Since the language stops on all inputs, it is recursive and thus can be reduced to $HALT$, which is recursively enumerable.
Since a finite instance (which is recursive) is possible, logically a recursive $L$ must also be possible.

To narrow down the search space, consider what you know about closure properties and HPL.

The class of decidable languages $R$ is closed against complement.
HPL is not in $R$.

You can conclude that $L \not\in R$;¹ otherwise, $\overline{L} \in R$ and therefore $\mathrm{HPL} \not\leq_T \overline{L}$.

On the other end, you need that $L \in RE$ (the set of semi-decidable languages) -- otherwise $L \not\leq_T \mathrm{HPL}$.

In combination, you need $L \in RE \setminus R$ which answers your question².

In particular, $L$ can not be finite since all such languages are decidable. The decider just checks a hard-coded table of all words in the language. With the same table you can also decide the complement.
Note how this implies $\overline{L} \not\in R$ which is enough for $HPL \leq_T \overline{L}$.


modify Dijkstra's algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex i want to modify Dijkstra algorithm to compute shortest path only for the vertex which is no more than three edges away from the start vertex

I tried it with BFS(breadth first search). Initially calculates the number of edges away from source to each vertex v. Then run Dijkstra's algorithm with a constraint like relaxation u if and only if edges size from the source to u is no longer than three. Is it correct or Are there another method to find it.(using Dijkstra algorithm)

I assume you want to only calculate shortest paths, starting from $s$, to vertices in its 3-hop neighborhood, i.e. vertices which are reachable from the start vertex $s$ with a path length $\leq 3$.

Use a limited breadth-first search and save the frontier vertices in a queue which is sorted according to its edge-weights. By doing that you have a priority queue and can update vertices like in the regular Dijkstra's algorithm. Note that you need to keep track of the current depth of the breadth-first search.


Intuition behind the condition |xy| ≤ p in pumping lemma for regular languages When I take a look at the proofs for pumping lemma, I have a feeling that I am often missing the intuition behind the condition |xy| ≤ p.

What exactly is the reason behind this condition? All the literature I have taken a look at are either silent (no proof, no discussion, only a statement) about this point, or state that we want the first repetition to occur not too far from the start.

But when there is an inequality involved, with very precise symbols and operators, don't we expect there to be a clear proof where we ultimately reach this condition?

What I am looking for are,

Mathematical proof for the condition, |xy| ≤ p.
Intuition behind the same condition.

To make the strings sufficiently long we have the condition string size at least p. My specific issue is why it is needed that |xy| ≤ p? And what does it break if |xy| ≤ p is not true?

(What's the reason for the second condition of the pumping lemma(s)?, does not exacly answer my question. The question is perhaps alright, but the answers only give some examples without much deep intuition.)

It's not needed for the proof. You can prove the lemma without this condition. Adding this condition makes the statement stronger and so more useful.

The intuition here is that if a DFA has $p$ states and there is a list of $p+1$ of them, then the list must contain two states which are the same. The string $x$ is the part that stretches from the beginning of the input to the first occurrence of the double state, and the string $y$ stretches until the second occurrence. By considering the first repeat we can guarantee that $|xy| \leq p$, since after reading $p$ characters we have seen $p+1$ states.


Which of $e^n$ and $2n^2$ grows faster? How would you prove/disprove that $e^n = O(2n^2)$? It's unclear to me which function grows faster.

Try plotting them. You can also notice that as $n$ increases by one, $e^n$ increases by a multiplicative factor of $e^{n+1}/e^n=e$, while $2n^2$ increases by a multiplicative factor of $\frac{2(n+1)^2}{2n^2} \longrightarrow 1$.


Rounding errors when converting floats to integers Is it possible to have a rounding error when you convert a floating point number which can only be in increments of 0.01 to an integer by multiplying by 100 first?  I would think that the lack of precision in representing floating point numbers is so small that it would never cause a rounding error when you only have to worry about 0.01 increments.

It depends on :

the range of your input numbers
the FP type, typically IEEE single (32bits, 23bits precision) our double (64bits, 52bits precision)
The rounding mode, which is almost always "round to nearest even"

0.01 ≈ 7bits, add 3 bits for correct rounding, so around 13 bits remains with single precision, which give a range around ≈ ±10000.

[Well, I'm too lazy to give precise answers. The problem with FP is that every operation can slightly affect the precision, as well as the way the program is compiled and the target architecture, with or without FMA (fused multiply-add), for example.]


Applying Machine learning in biological data I am trying to solve the following question: Given a text file containing a bunch of biological information, find out the one gene which is {up/down}regulated. Now, for this I have many such (60K) files and have annotated some (1000) of them as to which gene is {up/down}regulated.
Conditions

Many sentences in the file have some gene name mention and some of them also have neighboring text that can help one decide if this is indeed the gene being modulated.
Some files also have NO gene modulated. But these still have gene mentions.

Given this, I wanted to ask (having absolutely no background in ML), what sequence learning algorithm/tool do I use that can take in my annotated (training) data (after probably converting the text to vectors somehow!) and can build a good model on which I can then test more files?
Example data

Title:    Assessment of Thermotolerance in preshocked hsp70(-/-) and
(+/+) cells
Organism:  Mus musculus
Experiment type:   Expression profiling by array
Summary:   From preliminary experiments, HSP70  deficient MEF cells display moderate thermotolerance to a severe heatshock of 45.5 degrees after a mild preshock at 43 degrees, even in the absence of hsp70 protein. We would like to determine which genes in these cells are being activated to account for this thermotolerance. AQP has also been reported to be important.
Keywords: thermal stress, heat shock response, knockout, cell culture, hsp70
Overall design:    Two cell lines are analyzed - hsp70 knockout and hsp70 rescue cells. 6 microarrays from the (-/-)knockout cells are analyzed (3 Pretreated vs 3 unheated controls). For the (+/+) rescue cells, 4 microarrays are used (2 pretreated and 2 unheated controls). Cells were plated at 3k/well in a 96 well plate, covered with a gas permeable sealer and heat shocked at  43degrees for 30 minutes at the 20 hr time point. The RNA was harvested at 3hrs after heat treatment

Here my main gene is hsp70 and it is down-regulated (deducible from hsp(-/-) or HSP70 deficient). Many other gene names are also there like AQP.
There could be another file with no gene modified at all. In fact, more files have no actual gene modulation than those who do, and all contain gene name mentions.
Any idea would be great!!

A simple starting point would be to apply a bag-of-words feature vector and try using a naive Bayes or logistic regression classifier.  You'll probably want to apply stemming and lemmatization and remove stop words.

Going based on this one example, determining which gene is regulated looks like it might be plausibly feasible, but determining whether it is up- or down-regulated might be pretty tough, especially given the limited training set you have.  Of course, it's hard to know without seeing more examples and without some domain knowledge in biology.

There are lots of techniques in the NLP literature, and probably your best bet is to start by reading up on standard NLP methods and start trying some of them, and see if that raises a more narrowly targeted question.  Machine learning often requires significant experimentation (try a bunch of things).  It's also helpful to know standard techniques so you can use your domain knowledge of these documents to help you brainstorm possible features.


What decompression algorithms have the shortest implementations? I am writing an executable compressor for small (roughly 1 kilobyte) executable files.

I am exploring compression algorithms that are well suited for this task. The amount of time required to compress and decompress is not important for my purposes, nor is the complexity of the compressor. I am limited to 4 GB of RAM while decompressing and I am chiefly concerned with maximizing the compression ratio while minimizing the size of the decompression stub.

I am currently experimenting with arithmetic encoding using various models to predict the posterior probability. This results in a decompression stub around 200 to 300 bytes in size. I have also experimented with LZ based methods, but have rejected them because their implementation is more complex and their performance is both theoretically and empirically inferior to arithmetic encoding with context modeling.

What other compression algorithms might be useful candidates for this task?

I expect short decompressors with algorithms that do not maintain an explicit model and use "simple" encodings. An LZ encoding might use (length, offset) with Fibonacci coding, with an offset of 0 meaning a run of length literal codes, (minus) one a repetition of the last code, ….
I expect decompressor size to depend on (possibly abstract) machine - "MS Windows x64", NC4000, …
(The implied model being Things seen before are more likely than anything new, with short, local repetitions more likely than large ones from way back.)
That said, you may be after shortest length of compressed code+decompressor - Kolmogorov complexity.


An example where the algorithm of Hopcroft and Karp performs poorly? I have been trying to construct an example, where Hopcroft and Karp's algorithm for the maximum matching problem performs poorly (say at least $\Omega(\log n)$ rounds). However, all the examples I came up with where solved on paper in almost constant number of rounds.

Other questions here in the community targeting this problem tackle the worst-case running time or the time-bound proven in the original paper.

This running time seems to be a bit too loose, especially because the maximum matching problem in general and in bipartite graphs lacks a conditional lower-bound on its running time and I couldn't find any tight lower-bound on the number of needed rounds. I couldn't find a bound on the number of needed operations in constrained models of computing either (For example binary decision tree or so).

On the other side, the $O(\sqrt n)$ bound on the number of rounds from the original paper has not been improved since was found in the 1973 except in the parameterized context and in special classes of graphs.

Any ideas/suggestions are much appreciated :)

I was able to construct a simple example where the algorithm taken literally is easy to trick. The case goes as follows. Given a bipartite graph consisting of a union of simple paths of odd lengths $P_1, P_3, P_5, \dots, P_{2r-1}$ for some $r \in \mathbb{N}$. Assuming $P_i = v_{i,0}, v_{i,1} \dots v_{i,i}$ for $i = 2k-1; k \in [r]$. The shortest augmenting path in the first iteration has length one (namely any edge in the graph is such a path). Consider the following scenario of the algorithm.

In the first iteration, the algorithm chooses $\left\lfloor \frac{i}{2} \right\rfloor$ edges from each path $P_i$, namely the edges $v_{i, 2}, v_{i, 4}, \dots v_{i, i-1}$ as a maximal set of shortest augmenting paths. The set is maximal, since any other edge share an endpoint with an edge in the set. However, the matching resulting from these edges admits an augmenting path in each path $P_i$ of the length $i$. Since all paths have distinct lengths, the algorithm as given in the paper from Hopcroft and Karp augment exactly one path in each phase (in the pahse $j$ it will not look for paths longer than $2j-1$ since an augmenting path of this length exists). In total we need $\Omega(r)$ phases which is $\Omega(\sqrt n)$ with simple math. This bound is tight to the proven bound.

I considered this case trivial, since all augmenting paths are vertex disjoint and instead of looking for maximal set of vertex-disjoint shortest augmenting paths in each phase, we can look for a maximal set of vertex-disjoint augmenting paths with monoton-increasing lengths of the paths. I mean with that, that in each phase, after we run the BFS, we do not stop when a maximal set of vertex disjoint shortest augmenting paths are found, but we look further for (second-shortest) augmenting paths that are vertex-disjoint from what we already found and so on. In this case we would have considered all augmenting paths in the given graph in the previous example in one step.

On the other hand, it is not directly clear how to implement this kind of rounds in linear or almost-linear time from the given implementation of the algorithm in the paper of Hopcroft and Karp.

I was able to go further and construct examples with a bit more complicated structures and the same number of rounds, where we add edges arbitrarily between the middles of these given simple paths or parallel copies of subpaths. Even though, these edges might change the sequence of the algorithm, since they can be chosen at the first round of the algorithm, it is not hard to see that the total number of rounds does not change critically.

On the other hand, dense graphs seem to need less rounds in general. This can also be seen "intuitively" from results proben by Hegerfeld and Kratsch in this paper, which gives more insight about the number of needed rounds.


Linear/affine lifetimes without subtyping Are there any type systems similar to rust that don't depend on subtyping ? Can we express that one value must be consumed or dropped before another? For instance if I had an array of huge values on the heap and I would like to operate on a single item using a reference to it, the compiler would need to be sure I had finished with the reference before I could mutate or drop the parent array.

Linear and affine typing systems have been developed in the context of linear logic and process calculi. Most developments of such types do not use subtyping. The system in (1) is pioneering for its use of linearity, as are (2, 3) which introduced session types which are heavily based on linearity. See also the CSTheory Stackexchange thread Determinism and pi-calculus for some other (related) typing systems that make heavy use of linearity and affinity. While all this work is for process calculi, note that sequential behaviour is a well-behaved special case of concurrency and affinity in Rust is closely related (the same) as affinity in process theory.

 N. Kobayashi, B. C. Pierce, D. N. Turner, Linearity and the Pi-Calculus.

 K. Takeuchi, K. Honda, M. Kubo, An Interaction-based Language and its Typing System.

 K. Honda, V. T. Vasconcelos, M. Kubo, Language Primitives and Type Disciplines for Structured Communication-based Programming.


Knapsack Problem with exact required item number constraint How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$), but you must add exactly $L$ item(s) to the knapsack (and obviously need to optimize the total value of the knapsack).

Every way I've thought of implementing this so far (dynamic programming, brute force) has resulted in either failure, or lifetime-of-universe level computation times. Any help or ideas are appreciated.

Edit: I am looking for pseudo-polynomial time solutions

You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be discarded).

To ensure that you select at least $L$ items:

Add $n(V+1)$ to the value of every item.
Now the problem is equivalent to that of maximizing the number of selected items, breaking ties in favor of set of items with largest original total value, subject to weight constraints. There is a solution that selects at least $L$ items iff the optimal solution has a value of at least $n(V+1)L$.

To ensure that you select at most $L$ items:

Add $(W+1)$ to the weight of every item.
Add $L(W+1)$ to $W$.
Now every subset of more than $L$ items weighs at least $(L+1)(W+1) = L(W+1) + (W+1) > L(W+1) + W$, and is hence not feasible. Every subset of $L$ items that had an overall weight of $w$, now weighs $L(W+1) + w$, and hence is  feasible iff $w \le W$.
A subset with less than $L$ items might be feasible even if its overall weight is more than $W$, however its total value will always be smaller than $n(V+1)L$.


How to prove that Bellman-Ford algorithm detects a negative cycle? I have read that if we run the outer-loop of the Bellman-Ford algorithm for |V| times (where |V| is the number of nodes in the graph) and check if any distance has changed in the |V|th iteration (i.e. the last iteration) then there exists at least one negative weight cycle in the graph. But why does this work? Why only run for |V| times, why not more than that?

I am looking for a mathematical proof on why a change in the value of the distance of a node during the last iteration (|V|th iteration) implies that there is a negative weight cycle?

Can we detect all the nodes that are either reachable or are parts of the negative weight cycles after the |V|th iteration (can this also be proved mathematically)?

It would be helpful if someone can either provide the proofs and explanations or direct to the relevant resources.
Thank you.

Let us start by observing that after the $k$-th iteration in the main loop, the Bellman-Ford algorithm has computed minimal weight paths (or the weight of such a path if we do not store the predecessors) of length at most $k$ from the starting vertex $s$ to every other vertex of our graph $G$ (if such paths exists).
To prove this, we can use induction:
Clearly this holds after the first step as a path of length $1$ is just an edge connecting two vertices.
Now suppose we found minimal weight paths from $s$ to any other vertex of length $\leq k$ after the $k$-th step and we execute the $(k + 1)$-th step.
Note that any path $p_{sv}$ of length $k + 1$ from $s$ to some vertex $v$ can be formed by taking some path $p_{sw}$ of length $k$ from $s$ to a neighbor $w$ of $v$ and then appending the edge $wv$ and in particular we find that if $p_{sv}$ is of minimal weight w.r.t. all $s$-$v$-paths of length $k + 1$ then $p_{sw}$ must already be weight-minimal w.r.t. all $s$-$w$-paths of length $k$ (otherwise one could use a better path from $s$ to $w$ and adjoin $wv$ to get a path with less weight than $p_{sv}$) and the claim follows.
Now let us address your first question.
Note that any simple path (i.e. one that does not self-intersect) between any two vertices in $G$ is of length at most $|V(G)| - 1$ and conversely, any path of length $\geq |V(G)|$ must contain a cycle.
Hence, a path from $s$ to $v$ of length $|V(G)|$ (or greater) can be decomposed into three parts: some initial path segment starting at $s$ and ending at some vertex $w$, a cycle (of positive length) starting and ending at $w$ and some final path segment from $w$ to $v$ (note that the path segments need not be cycle-free themselves).
If $G$ contained no negative cycles, then the path obtained from appending the final path segment to the initial one is cannot be of larger weight than the one also containing the cycle and thus, the weight of any path containing a cycle can never be shorter than the cycle-free path obtained from cutting said cycle out in the manner I outlined and in particular, this means that the algorithm cannot improve on the paths it found in $|V(G)| - 1$ steps.
However, if at least one negative cycle exists in $G$ we can use the lemma we proved in the beginning we get that the Bellman-Ford-algorithm will find an improved path in the $|V(G)|$-th step which could not exist in a graph with no negative cycles, showing that the graph contains a negative cycle if and only if we detect such an improvement in the $|V(G)|$-th step.
The answer to your second question is negative and it is easy to construct counterexamples where arbitrarily many iterations are needed to find all vertices reachable via paths including negative cycles:
Consider the butterfly graph $B$ on the five vertices $v_1, ..., v_5$ such that both $C_1 = \{v_1, v_2, v_3\}$ and $C_3 = \{v_3, v_4, v_5\}$ are the triangles of $B$ (i.e. $v_3$ is the "center vertex" of degree 4) and set the weights such that $C_2$ forms a negative cycle of weight $-1$ while $v_1 v_2$ and $v_1 v_3$ have both weight $0$ and $v_2 v_3$ has weight $n$.
Now consider the paths from $v_1$ to $v_2$ -- using the negative cycle $n + 1$ times we are able to find a path better than the one consisting only of the edge $v_1 v_2$ but such a path has length $2 + 3 \cdot (n + 1)$ and hence by choosing $n$ to be some large enough value (really $n > 1$ suffices) and recalling our initial result we can see that the Bellman-Ford algorithm will not find that $v_2$ can be reached via a negative cycle until step $2 + 3 \cdot (n + 1)$.
Since of course every vertex in such a negative weight cycle is also one reachable via one, this also negatively answers the second part of this question.
However, note that if some vertex $v$ cannot be reached via a negative cycle from the starting vertex $s$ then the distance (in the algorithm's table) between $s$ and $v$ can only decrease at most $|V(G)| - 1$ times while for any vertex that can be reached via a negative cycle said distance can decrease arbitrarily often, so it is possible to find all such vertices eventually with some additional bookkeeping.


Finding median of 2 sorted arrays in O(log n) If there are given two arrays, A and B, each containing n real numbers in sorted order. How to compute the median of all the numbers in A and B, in O(log n) time. I have to make an algorithm that takes at most logarithmic time.

My idea:

A = 1, 3, 6, 8, 10, 15, 20

B = 1, 2, 3, 7, 10, 30

C = sort(A, B)

a = len(A) // 7
b = len(B) // 6
M = (a+b)/2 // 6.5
if M is a fraction:
    Median = C[M+0.5]
else:
    Median = (C[M]+C[M+1])/2

How to write sort function under complexity O(log n)?
I don't even have to sort all the elements of A and B, I only need the first M+1 elements of C because of above method.

There are two arrays: $A, B$ with lengths $n, m$. Finding median in the sorted array takes constant time (just access middle element or take a mean of two center elements).

To find the median of all elements in $\mathcal O(min(\log n, \log m))$ perform the following steps:

If $(length(A) \le 2$ or $length(B) \le 2)$ or $(A _{last} \le B_{first}$ or $B_{last} \le A_{first})$ calculate median and return.
Set $A_m = median(A), B_m = median(B)$ and compare them. If $A_m = B_m$ return result. If $A_m < B_m$ then discard first half of $A$ and the same amount of elements from the second half of $B$. else if $A_m > B_m$ then discard second half of $A$ and the same amount of elements from the first half of $B$.
Goto 1

This algorithm runs in logarithmic time. Minimum in the complexity reflects the fact that when the smaller array has length $\le 2$ the procedure terminates. At step 2 the both arrays get halved (or procedure is terminated) so it will be performed at most $\log_2(min(n, m))$ times.

By calculate median there are two cases: at least one arrays length was $\le 2$, so shift the median of the second array accordingly, or arrays do not overlap (or share the boundary element) then the median is the center element of two arrays concatenated in ascending order. In fact only index is calculated, no actual concatenation takes place.

Why the procedure stops when at least one of lengths is $\le 2$? Consider the corner case, e.g. A = [2, 9], B = [3, 11], the median is 6, but taking them separately yields 5.5 and 7, which in turn yields incorrect result 6.25.

For example:
$A = [1, 2, 6, 8, 12, 15], B = [2, 5, 8, 15]$  to keep an overview, the whole sorted array $C = [1, 2, 2, 5, 6, 8, 8, 12, 15, 15], C_m = 7$.
$A_m = 7, B_m = 6.5$ now $A_m > B_m$ so we drop [12, 15] from $A$ and we drop [2, 5] from $B$. Why $8$ is not dropped from $A$? Bacause we cannot drop $8$ from $B$, and in order to preserve median we can only drop the same number of elements ftom the both arrays at the opposite sites of the mean.
So $A = [1, 2, 6, 8], B = [8, 15]$. Now back to step 1, the arrays do overlap by common element at the end so we take $AB$, the lengths are 4, 2, so it is a mean of 3rd and 4th element $\frac{6 + 8}{2} = 7$.


Generative Machine Learning algorithms on tree structure I'm looking into PCFG sentence grammar dependency structure parsing using StanfordNLP PCFG parser. It generates tree structures represented as a string like this:

 Happy new year => (ROOT (VP (VBN Happy) (NP (JJ new) (NN year))))

Or in a more visual way, the tree structure looks like this:

(ROOT
  (VBN (JJ Happy)
    (NP (JJ new) (NN year))))

Since some machine learning algorithms are generative, and I'm wondering if I group tree structures into two sets: one set contains sentences with negative emotions, one set on positive emotions. Can I use the machine learning algorithm to get the most commonly occurred subtree structure within each set?

I'm very sorry if I caused any confusion. First of all, I want to know if this problem is solvable in the realm of machine learning.

Remember topic modeling? Where the algorithm reads large chunks of text and generate similar topics and return keyword strings grouped together as a topic? One topic could be: Gun, ship, sailer, ocean, fish, war, Gulf, oil

It provides an insight into what computer understands what this document might be talking about, so we can compare it with what humans think.

However, what I want to do, is ask the question if I can find common syntactical subtree structures in a sentence that might indicate the attribute of this sentence: negative or positive.

No, I am not asking for a sentiment analysis classifier, and that is not my interest at all.

For example, (this is an unpublished study right now), as us humans, we can say certain things about the future, and it will appear in a special structure, like "I will go to the mall" or "I'm going to jogging." You can see that "will" or "going to" might appear in many sentences, and serve as a common grammatical/syntactical structure. Those structures can be spotted by us human beings (namely linguists), however, is it possible to let machine find such common pattern?

I know in data science, or in realm of machine learning, people use algorithms to find/generate common patterns. I can group my parsed sentences (as tree structures represented above) into two groups: negative group and positive group (NOT emotions, just names for two groups), and then I want to use this algorithm to see if one or multiple subtree structures are very common among the group so I can extract them out.

As I stated before, I only need two things:

Is this solvable in Machine Learning realm?
If it is, which algorithm should I use?

It sounds like what you want is a machine learning algorithm that works on trees, in the supervised learning context.  I'd imagine there are probably many machine learning algorithms that could be adapted to this setting, but a natural one to try first is naive Bayes.  So, let me sketch how to use naive Bayes in this setting.

First, we need a feature set.  A simple feature set would be: each possible subtree that appears anywhere in the training set is a feature.  So, in the example in the question, your feature set would include the subtree (NP (JJ new) (NN year)) and (JJ new) and every subtree of every parse tree that appears in the training set.  Let $S_1,\dots,S_n$ denote these $n$ subtrees.  This gives you a bunch of features.  Now you can label each sentence with its label (positive or negative); and for each, you know whether it contains that feature or not.

Now remember how Naive bayes works.  We have a boolean random variable $Y$ that indicates the class of an item, and $n$ boolean random variables $X_1,\dots,X_n$ that indicate which features it has.  In particular, $X_i=+$ means that the $i$th feature is positive, i.e., that the $i$th subtree $S_i$ is a subtree of the current item.  We want to calculate

$$\Pr[Y=+ | X_1=x_1,\dots,X_n=x_n].$$

We do this using Bayes theorem.  In particular, we use our training set to calculate

$$\Pr[X_i=x_i | Y=y],$$

for each of the 4 possibilities of $x_i,y$.  Then, we use Bayes theorem to compute $\Pr[Y=+ | X_1=x_1,\dots,X_n=x_n]$.

Now everything works as usual for naive Bayes.  We've converted this into a situation where there's a set of $n$ features that can be present or absent for each item, and we want to label all the items; there's no more need to reason about the tree structure, we can just use a standard classifier like naive Bayes.  You could also plug in some other classifier as well, too; hopefully you can see how this might work, from here.


Are two strings equal if all deciders for a language take the same amount of time for both? Let $X_*^L$ be the set of all deterministic Turing machines $M$ which decide the language $L$ and have the property:

$\forall x,y \in \Sigma^*: t_M(xy) \ge t_M(x) + t_M(y)$ (**)

where $t_M(w)$ is the time of $M$ on input $w$.

Define for all $x,y\in \Sigma^*$:

$d(x,y) := \max_{M \in X_*^L} \frac{|t_M(x) - t_M(y)|}{t_M(xy)+t_M(yx)}$

Then, because of (**) we have
$t_M(yx) + t_M(xy) \ge 2(t_M(x)+t_M(y))$ from which it follows that:
$\frac{|t_M(x) - t_M(y)|}{t_M(xy) + t_M(yx)} \le 1/2 \frac{|t_M(x)-t_M(y)|}{t_M(x) + t_M(y)} \le 1/2 \frac{ |t_M(x)| + |t_M(y)|}{t_M(x) + t_M(y)} = \frac{1}{2}$
Hence we get
$d(x,y) \le 1/2$.

My question is this:

Does $d(x,y) = 0$ which is equivalent to $\forall M \in X_*^L: t_M(x) = t_M(y)$ imply that $x = y$?

The reason for asking this question, is that I am trying to define a metric on strings which has "something to do with the time-complexity of Turing machines".
If we define $d(x,y) = \max_{M \in X^L} |t_M(x) - t_M(y)|$ (where the maximum is taken over all machines which decide $L$.). Then I can show, that $d(x,y) = 0$ implies $x = y$. But the problem with this definition, is that $d(x,y)$ can be $\infty$. Or am I wrong with this?

Your "distance" $d(x,y)$ is never zero for distinct, non-trivial $x$ and $y$.

Let $M$ be a decider for $L$ and $x,y \in \Sigma^*$ with $\varepsilon \neq x \neq y$. Let furthermore $T = 1 + \max \{ t_M(x), t_M(y) \}$. Now we construct a machine $M'$ like this:

M'(z) {
  if x == z or xy is a prefix of z
    wait for T steps
  return M(z)
}

We observe that $t_{M'}(x) - t_{M'}(y) \geq T > 0$ since $x \neq y$. Condition (**) is satisfied by increasing the running-time on all inputs that begin with $xy$ as well; hence, $M' \in X^L_*$ and thus $d(x,y) > 0$.

This constructions works for all pairs of distinct $x$ and $y$, proving the claim. Your claim follows since trivially $d(x,x) = 0$ for all $x$.

I think the problem is that $d(x,y)$ is not well-defined. With a similar construction as above, we can increase the difference between $t_M(x)$ and $t_M(y)$ by an additional $i$ for all $i \in \mathbb{N}$. Since the sum of $t_M(xy)$ and $t_M(yx)$ grows with $i$ as well (unless either is $\varepsilon$), $d(x,y)$ approaches a constant for $i \to \infty$ and the maxium does not exist.


Loop invariant for adding 2 arrays storing binary value of integer Question:

Given 2 arrays of size $n$, $A = \langle a_1,a_2,\dots,a_n \rangle$ and $B = \langle b_1,b_2,\dots,b_n\rangle$, where $A$ and $B$ store the binary value of an integer. Find $A + B$ and stores the result in array $C$ of size $[n+1]$, $C = \langle c_1,c_2,\dots,c_{n+1}\rangle$.

Pseudocode:

ADD-BINARY(A,B)
C = new integer[A.length + 1]
carry = 0

for i = A.length to i = 1
    C[i] = (A[i] + B[i] + carry) % 2
    carry = (A[i] + B[i] + carry) / 2

C[1] = carry

return c

After writing the pseudo-code, I'm trying to find the loop invariant. One of the statement I can think of is

At the start of each iteration in the for loop, C[A.length...i] consists of the sum of binary A[A.length...i] and B[A.length...i].

But I check the initialization stage and found out that it is invalid because at the beginning of the for loop C[A.length] does not have the sum yet(it just got initialized). So I'm puzzled whether I'm approaching it the right way.

Step 1: Fix the typo in c[i=]. That's obviously wrong. (Done).

Step 1a: Try what happens when your algorithm adds 11 and 01. Notice that the result is wrong.

Step 1b: Fix the bug in your code. Check what happens in your algorithm again.

Step 2: Write down what is true at the end of the function which proves that the code is correct.

Step 3: Write down what is correct after the last iteration where i = 1, before setting C [1] = carry, which will lead to the statement in Step 2.

Step 4: Write down what is correct after each loop iteration, for each value of i.

Step 5: Write down what must be true before each loop iteration to get the result in Step 4.

Step 6: Figure out how Step 4 leads to Step 5.

Step 7: Check that Step 5 is true before the first iteration.


Analysis of the Banana Game My computer science professor introduced an interesting game in order to get us (his students) more familiar with the Stack and Queue ADTs.

Game Description

The banana game is played with a container -- e.g., a queue or a stack. The object of the game is to find a sequence of steps that will read a given string (i.e., sequence of letters) and print a given output string. There are 3 types of steps.

IN: Read the next letter from input and insert it into the container.
PR: Read the next letter from input and print it.
EX: Extract a letter from the container and print it.

If such a sequence exists, then we want to find a shortest one. Otherwise we want to briefly and clearly explain why no such sequence exists.
Link to original text: https://www.utsc.utoronto.ca/~nick/CSCA48/banana.html

Since the purpose of the game was only to play it, our professor never discussed any theory, or strategy for the game. Some students have come up with ways to generate solutions (for example by enumerating all sequences of valid moves and seeing if any of the results are equal to the destination string), but being first year students, none of our solutions were particularly novel or interesting. I have searched for a similar game, but my searches have not been fruitful. I am really interested in seeing the minimum time complexity algorithms for:

Finding the shortest solution
Finding out whether a given game is possible
Checking if a given solution is correct

Perhaps there are ways of representing this game that will make these thing easier to do (a graph or a tree)? I have also thought about this as some special version of The Tower of Hanoi (at least for the Stack ADT), but in this game you are not allowed to transfer characters back to the original "peg" so I guess it isn't very helpful. Note: this game can also be played with an ADT called Bucket which can only store one element.

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

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

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

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

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


Array accesses and basic operations I was looking through some lecture slides on algorithm analysis and found that in general an array access counted as a basic operation, but it did not seem to count as one when accessing the first element (e.g. A[i] is a basic operation but A[0] isn't). Does only accessing the first element count as a basic operation, and if it doesn't, does accessing  an array by a predefined index (e.g. A[5]) count as one, and why is this the case?

It usually doesn't matter, since we're usually only interested in the order of growth of the number of steps.  As long as we both agree that evaluating A[i] is a constant number of steps, independent of i, it doesn't actually matter what that constant is and we don't need to agree that it's the same constant.  We'll both agree that the algorithm is, say, $\Theta(n^2)$, even if I think the running time is $45n^2 + 16n + 18$ and you think it's $68n^2+25n+21$.  (And, in reality, neither of us is likely to be able to evaluate the running time to that level of precision.

So, it's usually fine to say that A[0] is a single step, as is A[5] (any sane compiler would compute "five cells beyond A[0]" at compile-time anyway) and A[i] where i is some variable. It won't make any difference to most analyses if you say that A[5] and A[i] are two operations due to having to compute the offset.

In some models of computation, things might be a bit more complicated because, if i is an arbitrary integer, it might not be sensible to assume that you can manipulate it in a constant number of steps. For example, on a standard Turing machine, you need to  read $\log\texttt{i}$ tape cells just to know what i is. But that doesn't look much like what a real computer does.


Is there an efficient algorithm for WEAK-PARTITION? Suppose that we are given a list of non-zero integers $(a_1,...,a_n)$ and we want to decide whether there exist $(x_1,...,x_n)$ such that

$x_1a_1 + x_2a_2 + ... + x_na_n = 0$,

$x_i$ $\in$ $\{-1,0,1\}$, with at least one $x_i \neq$ 0.

Note that this is not the same as PARTITION, where the restriction $x_i \in \{-1,1\}$ would give a solution. Of course we should also be aware that with $x_i \in \{0,1\}$ is the NP complete problem SUBSET-SUM. I don't see any obvious way of reducing SUBSET-SUM or PARTITION to this problem. For example, attempting to reduce a 0-1 problem to $\{-1,0,1\}$ problem by appending the list with negative elements appears to accomplish nothing.

The closest problem that I found was described this post, calling the problem WEAK-PARTITION. However, the link that the original poster provided is currently broken.

I would like to know whether there is an efficient (i.e. polynomial time) algorithm known for this problem and whether anyone knows of further references to this problem.

Your problem is NP-complete, as proved by Adi Shamir in his paper On the cryptocomplexity of knapsack systems.


Euclidean Steiner Tree Question in Approximation Algorithms Given $n$ points in $\mathbf{R}^2$, define the optimal Euclidean Steiner tree to be a minimum (Euclidean) length tree containing all $n$ points and any other subset of points from $\mathbf{R}^2$.
Prove that each of the additional points must have degree 3, with all three angles being $120^\circ$.

Hint 1: If there is a vertex that violate this condition, say a degree 3 vertex, take this vertex out. Now there are three vertices that have lost an edge remaining. Construct the Euclidean ST for these three points and add it back. Obviously your new solution cant be worse than what you head before. Now it remains to check that for 3 arbitrary points in the plane, the Euclidean ST fulfills the angle criterion mentioned in your question.

Hint 2: For a higher degree $v$, replace two consecutive edges $(v,u_1), (v,u_2)$ by the Euclidean ST spanned between $v,u_1,u_2$.


Inverting radial distortion I'm trying to understand the math behind correcting a radial distortion (caused by a lens), but I'm failing to have it explained in simple terms.

I found several examples that proceed this way: a starting point $P = (x, y)$ is given and it is transformed to another point $P'=(x', y')$ with the following equations

$$\begin{align*}
x' &= x \cdot (1-a \cdot \|P\|) \\
y' &= y \cdot (1-b \cdot \|P\|)\,.
\end{align*}
$$

This causes radial distortion, depending on the constants $a$ and $b$. Here $\|P\|$ is the euclidean norm of the vector from the origin to the point P, i.e. $\|P\|=\sqrt{x^2 + y^2}$.

How can I invert these equations?  In other words, given $x',y'$, I want to get back $x,y$.

I'm not sure inverting these equations will help you gain any understanding. Consider for example the simple case in which $a = b$. In that case,
$$
x'^2 + y'^2 = (x^2 + y^2) (1- a\|P\|)^2 = \|P\|^2(1-a\|P\|)^2,
$$
and taking square roots,
$$
\sqrt{x'^2+y'^2} = \|P\|\,\big|1-a\|P\|\big|.
$$
You know the left-hand side. The right-hand side is either $\|P\|(1-a\|P\|)$ or $\|P\|(a\|P\|-1)$ (though I'm not sure the latter is physically possible in your case), and in each case you get a quadratic for $\|P\|$. You get at most four solutions for $\|P\|$, and for each positive one you can substitute back, calculate $x,y$, and check that the equations are satisfied.

The case $a \neq b$ looks more complicated, but perhaps can be solved explicitly using a bit of creative algebra. Failing that, there are numerical method that can invert these equations.


INOI 2017 Problem 2 - Training INOI 2017, Problem 2, Training
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it
passes through N cities, numbered 1, 2, …, N, and in this order.

When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they
travel they may increase his strength and experience value in a manner to be described below.
In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The
Gym-leader in ith city has experience E[i]. If Pikachu enters a city i with strength S and decides to train, then
this increases his strength by the cube of the sum of the digits in his current strength.

For example, if he
entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other
hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value
XV by S*E[i].
Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.

Input
The first line contains two space separated integers, N and Sin, which are the number of cities, and the
initial strength, respectively.
The second line contains N space separated integers, which correspond to E[1], E[2],..., E[N].

Output
A single integer which is the maximum XV that Pikachu can attain.
Constraints

For all test cases you may assume that:
1 ≤ N ≤ 5000
0 ≤ Sin ≤ 109
0 ≤ E[i] ≤ 104

Subtask 1: For 10% of the score,
N ≤ 20 and Sin = 1
Subtask 2: For further 40% of the score,
E[i] = k for all i
i.e. E[i] is some constant k, for all i
Subtask 3: For further 50% of the score,
No further constraints.

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

I managed to solve the first subtask by employing a brute force solution (O(2^n)). But for the second and third subtasks I don't think that a brute force solution will be optimal.
Also, for the second subtask I have a vague idea. Taking X to be the number of trainings, then N-X is the number of battles. By maximizing experience gained  from N-X battles, we might get the answer, but I'm not sure if it's the right way.
I do not have any idea of how to solve the 3rd Subtask without using a brute force algorithm. Help would be appreciated.
Edit: Link to the above question in the IARCS website : https://www.iarcs.org.in/inoi/2017/

Here is how I would approach it. Yes, dynamic programming is a way to solve this problem efficiently.

A few notations to note before hand :

prefix[k] = sum of all terms from 0 to k ( k included ).
best[k] = max possible XV till term k ( k included )

Algorithm :

 1. prefix[0] = A[i];
 2. best[0] = cubed sum A[i]

 for array A:
    // max ( m,n ) --> max of m and n.
    3. best[i] = max ( cubed sum (prefix[i-1] + A[i]), best[i-1] * A[i]);

 return best[n]. n --> size of array.

In other words, you choose the max value of either including the current strength into sum or by competing.


Autocorrect algorithm - How to implement a decent "apostrophe & elision" feature? shorter version of the original question (as requests in comments)

What is the algorithm to handle missing apostrophe as it is done in auto-correct feature of Android virtual keyboard?

(If it helps / makes sense, feel free to give info about how such feature handles the detection and 2 words being written without any space between them?)

I need this in French where this happens much more than in English.

Example

Jai -> J'ai ('I have' in French)

Regex could be part of the solution?

Here are some regex to recognize the beginning of some (french) words, but these do generate way too many false positive candidates

\b(c)(h?[aeiou])
\b(j)(h?[aeiou])
\b(n)(h?[aeiou])
\b(m)(h?[aeiou])
\b(t)(h?[aeiou])
\b(s)(h?[aeiou])
\b(l)(h?[aeiou])
\b(d)(h?[aeiou])
\b(qu)(h?[aeiou])

Note:
For sake of completeness, I alreay have the 2 remaining simple cases already covered in the dictionary xml file

<word src="sil">s'il</word>
<word src="sils">s'ils</word>

Keeping original question for reference purposes:

Context

Using the opensource AnyosftKeyboard keayboard provider app, I would like to add an "elision/apostrophe" feature to make it aware of missing apostrophe in typed word and add it in the frame of its autocorrect feature.

A word about apostrophe & elision

"The apostrophe in French is used to replace a final vowel which is not pronounced because the next word also start with a vowel or silent “h”. The removing of a final silent vowel is called the ELISION.

In written French, elision takes place only with the following words : ce, je, ne, me, te, se, le, la, de, que, and si (only with “il” and “ils”)."

Source, where you can read more for some examples: https://frenchforenglishhindispeakers.wordpress.com/2012/09/25/lapostrophe/

Example

He is my friend -> Ce est mon ami (incorrect)
'Ce' is followed by 'est' -> elision (deletion) of the 'e' of 'Ce')
                -> C'est mon ami (correct)

Goal

Given the former example, I would like to implement a feature that would detect

Cest

and replace it by

C'est

That would allow the user to type faster by just ignoring apostrophe.
This behavior is already implemented in default Android keyboard

Questions

1 - What would be a proper algorithm to implement this "apostrophe & elison" feature?
 2 - How is this feature implemented in Android keyboard(s)?

PS

I am not sure if this is the right place to ask such question. If not, please let me know where I should ask it. Thanks.

You've asked two questions: about what algorithm can be used, and how it is implemented in Android.  Only the former is on-topic here, so I'll answer the former.  (Also, our guidelines are that you should generally ask only one question per post.)

Suppose French has the rule that the two words "X Y" are always replaced by an elided single-word replacement if X is one of ce, je, ne, me, te, se, le, la, de, que, or si and if Y starts with a vowel or silent "h".  I don't know French well enough to know if this is indeed the rule, so I'll assume that's how French works.

To suggest elisions, you could precompute a mini-dictionary of all words Y that start with a vowel or silent "h".  Then, it is easy to search all text entered to see whether it contains a pair of words of the form "X Y" where X is one of ce, je, ne, me, te, se, le, la, de, que, or si and Y is in the mini-dictionary.  If you find such a pair, then you can programmatically generate the correct elision and automatically suggest it.  This should be straightforward to implement.

Precomputing the mini-dictionary should be feasible.  It should be easy to find a dictionary of all valid French words and identify which ones start with a vowel and which ones start with an "h".  The trickiest bit is you'll need a way to identify all French words that start with a silent "h".  I don't know enough about French to know whether there's a clever way to do that.  However, a brute-force method is probably sufficient: I expect it would be sufficient to do it manually (list all words that start with a "h" and identify which have a silent "h"), or crowdsource it (something like Amazon Mechnical Turk, targeted at native French speakers).  This only needs to be done once, so generating the mini-dictionary should be feasible.

I'll also mention a complementary method that's probably also worth adopting.  Compute the list of all elisions, as above (by iterating over all valid pairs "X Y" that will trigger elision, then programmatically computing the correct elision).  Then, add each possible elided form listed above to your spelling dictionary.  In other words, extend your dictionary to include all valid elisions that can ever be encountered.  This may be a useful supplement to the method above, as it will help detect typos when people try to type in the elided form but make a small mistake.

These two methods are complementary.  In particular, if someone types the unelided form (e.g., "Ce est"), the first method above will auto-suggest correcting that to the elided form ("C'est").  And, if someone tries to type the elided form but makes a typo (e.g., "C'ext"), the second method will auto-suggest how to correct the typo ("C'est").  You can decide whether both of those problems are important to solve, or whether you only want to solve one of these two problems, and use that to determine which of these methods to implement.


DFA for the set of strings of 0’s and 1’s such that there are two 0’s separated by a number of positions that is a multiple of 4 I've being trying to understand this statement for quite a long time especially the "number of positions" part, but i can't seem to interpret it correctly.What i understand is that the statement means that there should be two 0's seperated by a number of symbols that are multiples of 4 i-e (0 , 4 , 8 , 16...), according to my understanding the string "01110", should not be in the language as the 0's are seperated by three 1's which is clearly not a multiple of 4, but the solution to the problem i've seen here:

https://www.google.com.pk/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjxtfzov9jWAhXGJ8AKHfP6D6gQFggmMAA&url=http%3A%2F%2Fwww.ics.uci.edu%2F~goodrich%2Fteach%2Fcs162%2Fhw%2FHW1Sols.pdf&usg=AOvVaw2XrD6v28VSz30I7l5jvdLd

Suggests that "01110" is in the language.

Can someone please help me with understanding what the question statement means?

Your interpretation is correct. It looks to me like the "solution" is wrong (and the solution isn't strictly a DFA).

Assuming you don't mind an NFA (getting a DFA is a bit fiddly, but obviously doable), you can fix the solution by removing the $(q_{4},0) \rightarrow q_{5}$ transition, and adding $(q_{5}, 0) \rightarrow q_{5}$ and $(q_{5}, 1) \rightarrow q_{5}$ transitions.

After some fiddling, it seems like a minimal DFA for this has 23 states... not so much fun.


Computing the minimal flexible distance of two vectors using dynamic programming I can't figure out a recurrence equation for a dynamic programming assignment. Formally, we aim
to minimize the total sum of distances between matched points with the following constraints:

Every point from both vectors has to be matched at least once, but can be matched multiple
times.
A point i can only be matched with a point j if no point o is matched with a point u such that i < o and j > u or i > o and
j < u, i.e., the ‘lines’ of the matches are not allowed to cross.

In order to compute the distance between two matched points, we use the absolute difference.

(Easy) Example input:

1.0 2.0 2.4 3.5
2.0 2.1 2.0 3.2

Should output:

1.8

Because in this example |1.0 - 2.0| + |2.0 - 2.1| + |2.4 - 2.0| + |3.5 - 3.2| is optimal

The assignment hints to sequence alignment which I thoroughly studied and came across the Needleman-Wunsch algorithm. However, I can't figure out how to adapt it to this problem.

Since this is a programming assignment, I only show some hints.

Consider two vectors $\vec{a} = a_1 \cdots a_i \cdots a_m$ and $\vec{b} = b_1 \cdots b_j \cdots b_n$.

First, please prove the following

  Observation: $a_m$ must be matched with $b_n$.

Second, consider the following subproblems,

$$D(i,j) \triangleq \text{the optimal (matching) distance between } a_1 \cdots a_i \text{ and } b_1 \cdots b_j.$$

and answer the following question

  Given the observation above, what is the relationship between $D_{i,j}$ and $D(i-1, j)$, $D(i, j-1)$, or maybe $D(i-1, j-1)$?


Algorithm to find a line that divides the number of points equally I have recently been asked in an interview to devise an algorithm that divides a set of points in a coordinate system so that half of the points lie on one side of the line, and the rest on the other side.

The points are unevenly placed and the line must not pass through any of the points.

Can any one give any approach to solve the problem? Analysis of the algorithm is appreciated.

Hints: Count the points, use medians.

The number of points is assumed to be even.

One approach is choosing a "generic" direction (in practice, a random direction), projecting all points along this direction, and then using a median algorithm (your line should correspond to any translation which lies between the two medians). If you choose a bad direction then points might clump together, making it impossible to separate them along that direction. However, if you choose a "generic" direction then this won't happen (assuming that the points are distinct). Since there are linear time median algorithms, this is an $O(n)$ algorithm. Using the randomized quickselect algorithm, you get a practical linear time algorithm.


Paradox? Pure Prolog is Turing-complete and yet incapable of expressing list intersection? Pure Prolog (Prolog limited to Horn clauses only) is Turing-complete. In fact, a single Horn clause is enough for Turing-completeness.
However, pure Prolog is incapable of expressing list intersection. (Disequality, dif/2, would allow it to do it, but dif/2 is not Horn, unlike equality).
This seems like a paradox, at first glance. Is there a simple explanation?

Turing-complete means "can compute every function on natural numbers that a Turing machine can compute". It means exactly that and only that.
A list is not a natural number, and list intersection is not a function on natural numbers.
Note: it is, of course, possible to encode lists as natural numbers, which would then make list intersection a function on natural numbers. And I have no doubt that, given you chose a suitable encoding of lists, Pure Prolog will be perfectly capable of expressing list intersection.
To put it another way: just because Pure Prolog is not capable of expressing list intersection using the particular representation of lists that was chosen for General Prolog does not mean that there does not exist a representation of lists more suitable for use with Pure Prolog such that Pure Prolog is capable of expressing intersection of those particular lists.


Calculating a jackpot winner based on probabilities Imagine a jackpot where users can bet as much as they want, and each bet increases their winning chance. Given a roll [0-100], how would you calculate the winner?
My solution and the pitfall
To determine winning users, you could check if a drawn roll [0-100] falls between a stack of users' winning probabilities.
Winning probability for each user is calculated by applying Fc(Bet, Pot Size) = Bet * 100 / Pot size.
The only algorithm I have in mind to determine who the winner is, is to perform math server-side and iterate each user's winning probability, and check if roll falls within:
user_bets = [250,250,500]
pot_size = sum(user_bets)
roll = 32.21;
cur_range = [0,0]
for bet in user_bets:
    win_chance = bet * 100 / pot_size
    cur_range = [  cur_range[1] , win_chance + cur_range[1] ]
    if roll >= cur_range[0] and roll <= cur_range[1]:
        # cur_range[0] = 25, cur_range[1] = 50
        # We found the winner
        break

Goal
The goal is to possibly adopt a one-liner algorithm to determine the winner within SQL language, whereas no iteration is involved
Graphic example
User X = BET    =  $13.000
User Y = BET    =   $6.500
User Z = BET    =   $3.250

POT_SIZE        =  $22.750
----------------------------------------------------------------------------------------------------
User X Win range               = 0 ->  57,14     (57% win chance)
User Y Win range               = 57.15 ->  85,71 (29% win chance)
User Z  Win range              = 85,72 ->  100   (14% win chance)
----------------------------------------------------------------------------------------------------
ROLL Example          = 32.27...
WINNER                = User X
----------------------------------------------------------------------------------------------------
ROLL Example          = 91.38...
WINNER                = User Z

For each user, sample the exponential distribution with rate equal to the size of that user's bet. The user with the smallest random variate wins the pot. Generation is something like $-\log(1 - \text{random}()) / \text{bet}$ where $\text{random}()$ returns a random number in $[0, 1)$.


Wagner Fischer Algorithm and the Empty String In the Wagner Fischer algorithm to calculate the Levenshtein distance for two input strings, the first step is to compare each input string with the empty string for each input. Why is this step necessary? Is the purpose simply to keep the algorithm consistent when checking the strings for matches and mismatches to determine the distance between two prefixes?

Thanks!

The Wagner–Fischer is a dynamic programming algorithm. You can think of a dynamic programming algorithm like a recursion. Every recursion needs a base case (like in induction). In this case, the base case is prefixes of length zero. We could also use prefixes of length one as a base case, but the simplest implementation of the algorithms starts with prefixes of length zero.

The prefix zero case can actually happen, for example when both strings have disjoint sets of letters.


Is there an algorithm to find all connected sub-graphs of size K? I was just wondering if there is an efficient algorithm that given a undirected graph G, finds all the sub-graphs whose size is k (or less)?

I searched around, and only found problems about finding the connected components. But I am interested in the smaller and more local connected sub-graphs.

To clarify, the graph of interest (road networks) has n vertices, and has a relatively low degree (4 to 10). I am interested in finding/enumerating all connected sub-graphs with size k(in terms of nodes), e.g. by listing the vertices of each. k is relatively small.

There can be exponentially many such subgraphs, so any such algorithm will necessarily be slow.

To enumerate all of them, choose any number $i$ in the range $[1,k]$, choose any subset $S$ of $i$ of the vertices, discard all edges that have an endpoint not in $S$, choose any subset of the remaining edges, then check if the graph with vertex set $S$ and the chosen edge subset is connected; if not, discard the graph; if yes, output the subgraph.  If you implement each "choose" with an for-loop that enumerates over all possibilities, this will enumerate over all graphs.  There are standard ways to enumerate all subsets of a set.

You can make it a bit more efficient by choosing the edges in a particular order:

for each $i \in [1,k]$:

for each subset $S$ of exactly $i$ of the vertices: (*)

let $E_1 = \{(u,v) \in E : u \in S, v \in S\}$ and $T := \emptyset$.
for each $v \in S$:

let $E_2 = \{(u,v) \in E : u \in S\}$.
if $E_2$ is empty and $T$ has no edge incident on $V$, go to the next iteration of the loop marked (*).
if $E_2$ is non-empty:

choose a non-empty subset $E_3$ of $E_2$.
set $T := T \cup E_3$ and $E_1 := E_1 \setminus E_2$.

if the graph $(S,T)$ with vertex set $S$ and edge set $T$ is connected, output it

I don't know how to guarantee polynomial delay, but this might be fine for your particular application.


Does Peterson's 2-process mutual exclusion algorithm account for dying processes? I think that in Peterson's algorithm for mutual exclusion, if the process first to enter the critical section were to die or be cancelled, the other process would loop forever, waiting to enter the critical section.

In the picture, if process 1 is stopped, the rest of the processes behind process 1 will execute up to where of process 1 is but then loop.

What happens if the process that reaches the critical section first dies before leaving it?

This depends on how locks are implemented. If you do it as in the Wikipedia article, i.e. guarding the critical section with one boolean per process¹, you are certainly in trouble. If one process dies, it never resets its flag so the other process loops forever.

In practice, you can safeguard your code against many ways of dying. For example, take this Java-style implementation:

flag[1] = true;
turn = 1;
while ( flag[0] == true && turn == 1 ) { Thread.yield(); }
try {
  // critical section
}
finally {
  flag[1] = false;
}

This will make sure the flag is reset whatever happens in the critical section, as long as the system is handling the error. In Java, that is true even for stack and heap overflows. So unless the process literally vanishes (kill², processor failure, network disconnect, ...) you are safe. Note that most non-critical software fails in these cases -- how can it handle an error it it's not running? -- so that has to be accepted in many cases. You can handle inconsistencies upon restart if necessary.

If you use proper, language-level locks, the runtime system may handle vanishing lock owners, i.e. release locks with dead owners. You can simulate this yourself by giving each process a dead man's switch the others can read, or check directly whether the lock owning process is still alive (if the system supports it).

That does not scale well, anyway.
In Java, I think finalize should execute even on kill, but this is not guarenteed by the spec. kill -9 is probably a death sentence for any solution that requires the dying process to do something.


Sampling from a set of numbers with a fixed sum Let $s = \{x_1, x_2, \ldots, x_n\}$ be a set of $n$ random non-negative integers where $\sum_i x_i = n$. And let $\{y_1, y_2, \ldots, y_{\sqrt{n}}\}$ denote a subset of size $\sqrt{n}$ of $s$, chosen uniformly at random. Defining $y$ to be $\sum_i y_i$ I am interested in calculating the value of $y$.

By linearity of expectation, I know $E[y] = \sum_i E[y_i] = \sqrt{n}$. But can I prove with high probability that $y$ is close to its mean?

I tried using Chernoff bound but unfortunately since $x_i$'s and therefore $y_i$'s are not independent, I can't apply it here.

I also tried using Chebyshev's inequality since $y_i$'s seem to be negatively correlated but I can't calculate the variance of $y_i$ and the proof would be messy even if I do.

Does anyone have any idea for a simpler proof?

You can bound the variance as follows. Let $b_i$ be an indicator variable signaling that $x_i$ was chosen. You are interested in $y = \sum_i b_i x_i$. We have
$$
\mathbb{E}[(b_ix_i)^2] = \frac{x_i^2}{\sqrt{n}},
\quad
\mathbb{E}[b_ix_i\cdot b_jx_j] = \frac{\sqrt{n}(\sqrt{n}-1)}{n(n-1)}x_ix_j = (1-O(1/\sqrt{n}))\frac{x_ix_j}{n}.
$$
Therefore
$$
\mathbb{E}[y^2]=\sum_i \frac{x_i^2}{\sqrt{n}}+\frac{1-O(1/\sqrt{n})}{n}\sum_{i \neq j} x_ix_j \leq \frac{(x_1+\cdots+x_n)^2}{n} + \frac{\sum_i x_i^2}{\sqrt{n}}.
$$
This shows that
$$
\mathbb{V}[y] \leq n + \frac{\sum_i x_i^2}{\sqrt{n}} - (\sqrt{n})^2 = \frac{\sum_i x_i^2}{\sqrt{n}}.
$$
The error in this estimate is quite small. The quantity $\sum_i x_i^2$ is maximized when $x_i = n$ for some $i$, and we conclude that $\mathbb{V}[y] \leq n^{3/2}$. This is of course not very helpful, if you are trying to use Chebyshev's inequality!

A cheap way out is to "filter out" all elements which are at least, say, $n^{1/2+\epsilon}$. There are at most $n^{1/2-\epsilon}$ of these, and so it is very likely that the sample contains none of them. This allows us to essentially assume that all $x_i$ are at most $n^{1/2+\epsilon}$, and so
$$\sum_i x_i^2 \leq \left(\sum_i x_i\right) \max_i x_i \leq n^{3/2+\epsilon}.$$
This shows that the "effective" variance is at most $n^{1+\epsilon}$, and so with high probability the deviation from the mean is at most, say, $n^{1/2+2\epsilon}$.

You can probably get better bounds with improved technology, but this bound is already pretty reasonable. When $x_1 = n$, you are always within distance at least $\sqrt{n}$ from the mean.


Choosing an independent hash function, given hash function value Supposed we have a function $h:U\to [m_1]$. Given this hash function,  can we generate without using randomization or a universal hash collection another hash $h':U \to [m_2]$, which depends on $h$ and the values of $h'(x)$ are uniform? i.e., for every value $y\in [m_2]$ we have $\Pr_{x} (h'(x)=y|h(x)=t)=1/m_2$ ($x$ is chosen at random).

I know that if $U=[2^t]$, $m_1=2^{n_1}$, $m_2=2^{n_2}$, $t>n_1+n_2$ and $h(x)$ is the first $n_1$ bits of $x$ this problem is easy: we can select $h'(x)$ to be the bits $n_1+1$ till $n_2$ of $x$. My question is how to generalized this approche.

From what I have understand from your question, I think you are looking for a way to transform a probability distribution to another probability distribution. For example, if your first hash function distributes your data into a gaussian/normal form into the buckets, then you need a function that takes the index of this bucket as input and gives you another bucket which must be chosen uniformally. This post may be helpful if I ve understand correctly what you are trying to achieve: https://stats.stackexchange.com/questions/223317/how-to-transform-one-pdf-into-another-graphically
My personal opinion is that a successful transformation depends a lot in your data. A hash function tries to distribute the data uniformally in the first place. But, even if you have a function G that distributes your data in a "weird" way then you can make a transformation T: G -> F so that F is whatever distribution you like.

[EDIT]
I don't think that this is achievable without using randomization. For example, if you have a hash function that maps all your data into one bin (for example the bin 0) then this function is constant. So, you are trying to create a function that takes a constant value and maps it uniformally, which cannot be done if you don't use any randomness or internal memory. By internal memory, I mean that your function "should remember" what kind of inputs has already "seen", and map them in a different value each time.


Equivalence of states between two "quasi-deterministic" strongly connected Büchi automata accepting the same $\omega$-language Hope someone can point me to the right direction to solve this problem.

Premise.
I call quasi-deterministic Büchi automaton (qDBA) a Büchi automaton $B = \langle S, \Sigma, S_0, \delta, F \rangle$, where $S$ is the set of states, $\Sigma$ the alphabet of transition labels, $S_0 \subseteq S$ the set of initial states, $\delta: S \times \Sigma \rightarrow S$ a partial transition function, and $F \subseteq S$ the set of accepting states. That is, a Büchi automaton where the only place of nondeterminism is in the initial state, while the transition function is deterministic.
An $\omega$-word is accepted by $B$ iff any of the infinite runs induced by the word on $B$ passes infinitely many times through some states of $F$.

Given a qDBA $B$ and a state $s \in S$, let $B/s = \langle S, \Sigma, s, \delta, F \rangle$ denote the deterministic Büchi automaton accepting all the $\omega$-words inducing runs of $B$ starting from $s$ (where $s$ may also be a non-initial state in B). Two states $s_1$ of the qDBA $B_1$ and $s_2$ of the qDBA $B_2$ are equivalent iff the language of the $\omega$-words accepted by $B_1/s_1$ is the same as the one accepted by $B_2/s_2$.

Finally, I say that $B$ is strongly connected if for any two states $s_1$ and $s_2$ there is a finite path connecting $s_1$ to $s_2$ and vice versa.

Question. Let $B_1 = \langle S_1, \Sigma, S_{0,1}, \delta_1, F_1 \rangle$ and $B_2 = \langle S_2, \Sigma, S_{0,2}, \delta_2, F_2 \rangle$ be two strongly connected qDBAs accepting the same $\omega$-language, $L(B_1) = L(B_2) = L$. I want to prove that for every state $s_1 \in S_1$ there exists at least one state $s_2 \in S_2$ equivalent to $s_1$.

Does this property hold in general? I tried to construct counterexamples to this property, but in every case I could think of, in order to falsify the conclusion, I always needed either to drop the assumption that $\delta_2$ was a deterministic transition function, or that $B_2$ was strongly connected.

I have a strong sense this property should hold. It might even be trivial, but maybe I am using the wrong vocabulary and I cannot find this result.

My intuition so far. Suppose there are two $\omega$-words $w'$ and $w''$ accepted by $B_1/s_1$. Since $B_1$ is strongly connected, one can construct accepted words by starting with the first symbols of $w'$, then taking a path back to $s_1$, then continuing with some symbols from $w''$, then back to $s_1$, and again following $w'$ in any combination. Since $B_2$ also accepts all of these combinations but has a finite number of states, the runs corresponding to these words must eventually reach some state $s_2$ from which both $w'$ and $w''$ are possible continuations of the runs. This must hold for every set of words accepted by $B_1/s_1$. But I am not able to turn this (possibly wrong) reasoning in general, formal terms. Could you please help me do so, if possible?

Your property does not hold.

Consider the following languages over $\Sigma = \{a,b\}$:

There are infinitely many $a$s at even positions in a word
There are infinitely many $a$s at odd positions in a word

Both are representation as DBAs with the same set of states (of size 3). We can build DBAs for them that only differ in their initial states.

If we want to build an automaton for the disjunction of these languages, we can do so by taking both initial states for both of them as new initial states. This gives us a qDBA $B_1$.

The disjuction is equivalent to the language "there are infinitely many $a$s", for which a DFA $B_2$ only needs two states, each of which have the same language.

Now, $B_1$ and $B_2$ are a counter-example to your conjecture.


A decision algorithm to choose what partner to use Background

I have a setup where I need to make an API call to a partner to initiate a financial transaction. I have multiple partners, and I need to choose which one to use each time a transaction needs to happen. The characteristics differentiating two partners are:

if the transaction is accepted or not (acceptance)
the cost of the transaction (fee charged by the partner, assumed to be constant over time)
the speed of the transaction (assumed to be constant over timefor each partner)

The characteristics of a transaction are especially:

amount
currency
(several other factors such as the user's country, the payment method he chose, etc)

Additional info: the acceptance rate of a partner is subject to
   change arbitrarily over time.

.

Algorithm

As you probably guessed, I am currently thinking about solutions and algorithms that could be used to solve the following problem.

  Inputs:

  a transaction (with all its characteristics)
  the database of all transactions having ever happened, containing for each transaction

  the partner used
  the fee charged
  if the transaction was accepted or not

  Output: the best partner to use to execute the transaction.

Obviously, the first step is to define best. Do we value speed more than cost? Do we value the expected acceptance rate more than both the cost and speed? etc.

Another important aspect I mentioned earlier is that the acceptance of the same transaction by the same partner might change over time. This means that the algorithm should sometimes try a partner that is believed not to be currently the best just to be able to, for instance, check if a partner's acceptance rate has improved over time.

My question

I'm obviously not asking someone to write a magic algorithm solving that. I have a background of CS, but I am unsure about what algorithms and types of algorithms are usually used to solve this kind of problem. I would be grateful to be given some extra terminology (e.g. if this is a typical problem with a particular name in the domain) and resources to be able to dig into the problem.

Please don't hesitate to ask if something is unclear.

Thank you!

[Edit] After searching a bit more on the web, it seems that this problem has a lot in common with the multi-armed bandit problem. However I believe that the algorithms presented to solve this problem (e.g. UCB1) could be suboptimal in this context, because they wouldn't take into account the characteristics of a transaction and act as if the partner didn't take them into account.

Techniques developed for the multi-armed bandit problem might be useful for discovering the partner with the best acceptance rate and dealing with the changing acceptance rate over time.  Those techniques balance "exploration" (sending transactions to a partner as a way to learn more information about their acceptance rate) vs "exploitation (sending transactions to the partner with the highest acceptance rate, to make use of the information gained previously).  You'll probably be especially interested in the non-stationary bandit problem.


Help with finding a flaw in argument simulating large Turing machines with smaller ones I have an argument which, if it goes through, just about proves that either:

Programming languages are more powerful than Turing machines
The busy beaver function ($BB()$) on Turing machines is computable

Now, I understand that it's vastly more likely that my argument has some flaw that I can't find.  But it's more interesting to me how I'm wrong, rather than whether I'm wrong.
Argument
Construct a Turing machine $M_1$ as which takes as arguments (on the tape) $n, k$, simulates all Turing machines with $n$ states until $k$ of them halt, and then halts itself.  This is easy to write in a programming language, as demonstrated by the following Python snippet:
def M1(n, k):
    all_machines = generate_turing_machines(n)
    is_halted = [0] * len(generate_turing_machines)
    while sum(is_halted) < k:
        for (i, machine) in enumerate(all_machines):
            machine.step()
            if machine.is_halted():
                is_halted[i] = 1

Now, let $m_1$ be the number of states required by $M_1$.  Fix $n$ much greater than $m_1$.  Let $k_1$ be the largest number such that $M_1(n, k_1)$ halts and $k_0$ be the smallest number such that when $M_1(n, k_0)$ halts, $k_1$ simulated Turing machines have halted (as all equivalent machines will halt on the same step).  Choose $k$ with $k_0\leq k\leq k_1$.  This means that $M_1(n,k)$ halts in about $BB(n)$ steps.
Construct $M_2$ which is the same as $M_1$ except the first thing it does is write $n$ and $k$ to the tape.  Let $m_2$ be the number of states required by $M_2$.  Then $m_1+K(n)+K(k)+C=m_2$ for some small $C$ (which is probably constant and likely $0$), with $K(n)$ being the Kolmogorov complexity of $n$ in Turing machine states.
Now, $K(n)$ is at most $O(\log(n))$.  There are about $n^n$ machines with $n$ states, so $k$ is about $n^n$, and thus $K(k)$ is at most $O(\log(n^n))=O(n \cdot \log(n))$.  That means that $m_2>n$.  But here we have a problem: if $k$ is easier to write to the tape (so that $K(k)<n-\log(n)$), then $m_2$ would be slightly smaller than $n$.  That would mean $BB(m_2)>BB(n)$ and $m_2<n$, a clear contradiction.
In my mind, these are the possible resolutions:

$M_1$ is impossible to create as a Turing machine, meaning that Python is more powerful than Turing machines are.
There is some transfinite extension to Turing machines which is not much more powerful than Turing machines in general, and $M_1$ can be written in this extension.  In other words, $M_1$ is the limit of a set of machines $M_{1,N}$, each of which can handle any $n<N$.  This would probably entail the busy beaver function being computable.
There is a large set of numbers which cannot be written by a Turing machine in much fewer than $\log(k)=n$ states (we need $K(k)<n-\log(n)$).  It seems impossible to me that no candidate for $(n, k)$ could be sufficiently compressed.

Where is the error in this logic?

I had previously said that $K(k)\leq O(n)$, but @6005 pointed out that was suspect.  With that fixed (to $O(n \cdot \log(n))$), it still seems very surprising to me that we can't achieve a reduction from $K(k)\approx n \cdot \log(n)$ to $K(k)<n-\log(n)$ for any potential value of $(n,k)$, but no longer inconceivable.

Your flaw seems to be here:

  Now, $K(n)$ is at most $O(\log(n))$.  $k$ is about $n^n$, so $K(k)$ is at most $O(n)$.  That puts $m_2$ just slightly larger than $n$.

It's true that $k$ is about $n^n$ (more precisely, $k = n^{\Theta(n)}$ or $k = 2^{\Theta(n \log n)}$, and this can be shown by upper bounding $k$ by the number of Turing machines, and lower bounding by finding a family of simple halting Turing machines). However, that doesn't imply that $K(k)$ is at most $O(n)$.
Rather, we only know that $K(k)$ is at most
$$
O(\log(n^n)) = O(n \log n).
$$

Your contradiction relies on picking $k$ so that $K(k)$ is $o(n)$ (a bit smaller than $n$). Your reasoning shows that this is impossible.

But this is not too surprising: most $k$ we expect to be about $O(n \log n)$, and $k$ is a number that holds a lot of information about Turing machines with $n$ states, so we don't expect to be able to compress such a number to smaller than $O(n)$ states itself.

P.S. Putting aside the question of whether Python is really equivalent to Turing machines (probably no one knows, as it hasn't been formally shown), your program M1 is in fact clearly expressible as a Turing machine. From this, you should be able to see that the resolutions based on M1 not being expressible as a Turing machine are not correct.


What graph data structure works fastest with Dijkstra's algorithm? What data structure should I store my graph in to get the best performance from the Dijkstra algorithm?

Object-pointer? Adjacency list? Something else?

I want the lowest O(). Any other tips are appreciated too!

Implementing Dijkstra's algorithm with a Fibonacci-heap gives $O(|E|+|V|\log |V|)$ time, and is the fastest implementation known.

As for the representation of the graph - theoretically, Dijkstra may scan the entire graph, so an adjacency list should work best, since from every vertex the algorithm scans all its neighbors.


Sampling in large graph using simple random walk I'm studying sampling techniques in online social networks. The assumption is we don't have full access to the network(i.e, we don’t know the size of the network). However crawling is supported, i.e,  starting with any arbitrary node we can access its neighbors. Hence we go for random walk(Markov Chain) based crawling techniques as it requires only neighborhood information for any node.

Let's assume we choose simple random walk(SRW) for crawling the network.

In SRW we start with an arbitrary seed node then choose one of the neighbors as new node. At the new node we choose one of its neighbors and this process continues.

Let G be our graph show in above figure, assume graph is large and size of the graph is not known. We go for SRW with node 'A' as initial node.

Since the size of the graph is not known how do we select initial distribution $X_0$(at time 0), and initial transition probabilities $P_0$(at time 0). After time 0 if I choose one of the neighbors(say B), how the transition probabilities $P_1$(at time 1) and distribution $X_1$(at time 1) are calculated.

While the algorithm doesn't know the graph, when you are analyzing the performance of the algorithm on a graph, you do know the graph.

For a similar example, take the egg dropping puzzle. In this puzzle, the algorithm doesn't know the value of $T$, but when analyzing the algorithm, you are allowed to use the value of $T$; indeed, otherwise it's not clear how you'd ever end up with a running time depending on $T$.


Category theory (not) for Programming? After learning Haskell and other not so pure FP languages I decided to read about Category theory. After gaining good understanding of Category theory I started thinking about how the concepts of category theory can be used to think about designing programs but no matter how hard I tried it seems this is not the way to go.

After spending many unsuccessful attempts to relate category theory to designing programs I came to the conclusion that:

Category theory is useful when designing a programming language.
Category theory is not something that you use when designing programs (even when using a language which was designed based on category principles). For example: When programming in Haskell you will use types, types constructor, functions, higher order functions etc to design your program, not category theory concepts.

In summary we have below layer system (order is low to high):

Category theory -> Programming language -> Program

At a particular layer you use the concepts of the immediate underlying layer.

Is this understanding correct? If not and you believe that in designing programs we can directly use category theory concepts, please refer some articles or blog posts where it is being demonstrated.

NOTE: By designing programs I mean designing programs based on different concepts, like concurrency, parallelism, reactive, message passing etc.

Well, that of course depends on what sort of program you are trying to design.

If you are designing an accounting program for your aunt's chocolate shop, I very much doubt category theory will be of much use.

But there are of course situations in which category theory is enormously useful in design of programs (by which I also mean data structures, libraries, and so on). Such situations occur mostly when the programs involved are of a mathematical nature.

If you want to write programs that compute with exact real numbers and other structures occurring in mathematical analysis, the first question you need to answer is what it means to correctly implement a complicated mathematical object (such as a differentiable function, a manifold, etc.). Here it helps very much to know some category theory and logic, because they give you a systematic way of translating definitions of mathematical structures to specifications and implementations of corresponding data structures. The buzzword you should look for is realizability theory. But this is just one example.

The best way to see how category theory comes in handy is to look at programs written by people who know a lot of category theory (and mathematics in general). An obvious example of this is Martín Escardó and his impossible functionals, for instance:

  M. Escardó and P. Oliva: What Sequential Games, the Tychonoff Theorem
  and the Double-Negation Shift have in Common, Mathematically Structured Functional Programming 2010, ACM Press. (with companion Haskell and Agda files)

You may complain that this is not just category theory but also logic and topology. Such complaints would be severely misguided. The best category theory is always mixed with other things.

Lastly, I would advise against drawing grand conclusions about nature of things based on a bit of self-assigned reading.


Representation of the concatenation at the type level I would like to learn more about concatenative programming through the creation of a small simple language, based on the stack and following the concatenative paradigm.

Unfortunately, I haven't found many resources concerning concatenative languages and their implementation, so excuse me in advance for my possible naivety.

I therefore defined my language as a simple sequence of concatenation of functions, represented in the AST as a list:

data Operation
    = Concat [Operation]
    | Quotation Operation
    | Var String
    | Lit Literal
    | LitOp LiteralOperation

data Literal
    = Int Int
    | Float Float

data LiteralOperation
    = Add | Sub | Mul | Div

The following program, 4 2 swap dup * + (corresponding to 2 * 2 + 4) once parsed, will give the following AST:

Concat [Lit (Int 4), Lit (Int 2), Var "swap", Var "dup", LitOp Mul, LitOp Add]

Now I have to infer and check the types.

I wrote this type system:

data Type
    = TBasic BasicType   -- 'Int' or 'Float'
    | TVar String        -- Variable type
    | TQuoteE String     -- Empty stack, noted 'A'
    | TQuote String Type -- Non empty stack, noted 'A t'
    | TConc Type Type    -- A type for the concatenation
    | TFun Type Type     -- The type of functions

That's where my question comes in, because I don't know what type to infer from that expression. The resulting type is obvious, it is Int, but I don't know how to actually entirely check this program at the type level.

At the beginning, as you can see above, I had thought of a TConc type that represents concatenation in the same way as the TFun type represents a function, because in the end the concatenation sequence forms an unique function.

Another option, which I have not yet explored, would be to apply the function composition inference rule to each element of this expression sequence. I don't know how it would work with the stack-based.

The question is so: how do we do it? Which algorithm to use, and which approach at the type level should be preferred?

A major idea of concatenative languages is that the syntax and semantic domain form monoids and the semantics is a monoid homomorphism. The syntax is the free monoid generated by the basic operations, better known as a list. It's operation is list concatenation, i.e. (++) in Haskell. In the untyped context, the semantic domain is just the monoid of endofunctions (on stacks) with composition as the operation. In other words, an interpreter should look like the following:

data Op = PushInt Int| Call Name | Quote Code | Add | ... -- etc.
type Code = [Op]

-- Run-time values
data Value = Q (Endo Stack) | I Int | ... -- etc.
type Stack = [Value]

-- You'd probably add an environment of type Map Name (Endo Stack)
interpretOp :: Op -> Endo Stack
interpretOp (PushInt n) = Endo (I n:)
interpretOp (Quote c) = Endo (Q (interpetCode c):)
interpretOp op = ... -- etc.

interpretCode :: Code -> Endo Stack
interpretCode = foldMap interpretOp

runCode :: Code -> Stack
runCode code = case interpretCode code of Endo f -> f []

Making a (very naive) compiler is just as simple. The only thing that changes is the target monoid which will now be a syntactic monoid built out of a fragment of the syntax of the target language thus interpretOp will become compileOp. This target monoid may be sequences of statements with the operation of sequential composition, i.e. ;. You can be quite a lot more sophisticated though.

Type systems for concatenative languages are not as obvious, and there are almost no typed concatenative languages. Cat is the most significant example I'm aware of. One way to start to approach it and experience some of the issues that come up is to embed a concatenative language in Haskell. You quickly discover that you don't want add :: (Int, Int) -> Int as this won't compose. Instead, you have add :: (Int, (Int, s)) -> (Int, s). This works extremely well for simple things. This is also relatively clearly poor man's row types. One of the first and most significant hurdles you'll hit is dealing with quotations. The problem is that [add] should correspond to something with a type like s -> ((forall s'. (Int, (Int, s')) -> (Int, s')), s) which requires higher-rank types and impredicative instantiation. Cat appears to have both. It certainly has higher ranked types, and it will substitute a polytype for a type variable. It may be doing things in a way that can be understood without impredicativity. Accomplishing this with an embedding in Haskell might be doable using type-level lists, (closed) type families, and local universal quantification. At this point though, making a custom type system likely makes more sense.

Operations with non-uniform stack effects are also likely to be problematic, but, in most cases, it makes sense to just omit them and provide alternative means of doing things that guarantee a consistent stack.


Backpropagation in multiple output neural networks I want to understand how the backpropagation algorithm would work on a neural network with multiple outputs.

More specifically, I have a network with 21 binary (0/1) outputs and I want to minimize the number of outputs that I get correctly; in other words, I want to minimize the hamming distance between the output vector and the desired vector.

How does the loss function work here? How do I backpropagate the error and update the weights?
I know this might be long to explain so I'm also happy with links to some good references that I could read on the matter.

You have to pick a loss function before you can apply backpropagation or train your network.  Once you do, you can apply backpropagation.  Backpropagation doesn't tell you how to pick a loss function; that's something you have to do, based on what you're trying to achieve.

Neural networks don't have binary outputs.  Rather, they have continuous outputs.  You might want to use a logistic loss on each of the 21 outputs, and sum up those 21 losses and use that as your overall loss function.  The logistic loss is effectively a generalization of the 0-or-1 loss to the case where you have a continuous output and you want to predict either 0 or 1.


Reduce 4-SAT to 5-SAT given is a reduction from 4-SAT to 5-SAT.
How is it possible to describe such a function?
I found some informations about reduction 3-SAT to 4-SAT here, but it can't help me so much.

Here is a translation of the answer how to prove 4-SAT CNF is NP-complete to the current situation.

Suppose an instance of 4-SAT over variables $x_1,x_2,\cdots, x_m$ is given as a boolean formula $$f=c_1\land c_2\land \cdots\land c_m,$$ where $c_i$ is a disjunction that has exactly 4 literals for all $i$.

Introduce a new variable $s$. Suppose $c_i=w\lor x \lor y \lor z$ for some literal $w,x,y,z$. Let
$$\begin{aligned}
c_{i+}&=w\lor x \lor y \lor z\lor s\\
c_{i-}&=w\lor x \lor y \lor z\lor \neg s.
\end{aligned}$$

If $c_i$ can be satisfied by an assignment, then $c_{i+}\land c_{i-}$ is satisfied by the same assignment plus $s=0$ (or $s=1$).
If $c_{i+}\land c_{i-}$ can be satisfied by an assignment, the same assignment without considering $s$ must satisfy $c_i$ since one of $s$ and $\neg s$ must be false.

Construct an instance of 5-SAT over variables $x_1,x_2,\cdots, x_m, s$, $$g=c_{1+}\land c_{1-}\land c_{2+}\land c_{2-}\land\cdots\land c_{m+}\land c_{m-}.$$

Because of the relation between $c_i$ and $c_{i+}\land c_{i-}$,

If $f$ is satisfied by an assignment, then $g$ is satisfied by the same assignment plus $s=0$.
Conversely, if $g$ is satisfied by an assignment, then $f$ is satisfied by the same assignment without considering $s$.

The above means the transformation from $f$ to $g$ is a reduction from 4-SAT to 5-SAT. It runs in polynomial time.

For simplicity of explanation, the above restricts $k$-SAT to CNF formulas with exactly $k$ literals without duplicates. Thanks to a similar simple padding technique, it is does not matter to the construction of reduction above whether we allow at most $k$ literals with or without duplicates when we define $k$-SAT.