Does a collision oracle for the pigeonhole subset sum problem produce solutions? I am reading "Efficient Cryptographic Schemes Provably as Secure as Subset Sum" by R. Impagliazzo and M. Naor (paper) and came across the following statement in the proof of Theorem 3.1 (pages 10-11):

  Let $\  l(n) = (1-c)n \ $ for $ \ c > 0  \ $ ...

  Given $a_1, a_2, \cdots, a_n \in \{0,1\}^{l(n)}$ and a target sum $T$, we construct an input to the collision finding algorithm as follows:

  Let the collision finding algorithm select a (non-empty) $ s_1 \in \{0,1\}^n $
  compute $T' = \sum_{i \in s_1} a_i$.  Choose a random $j$ such that $j \in s_1$ and define $a_j' = a_j - T' + T$.
  Give the instance $a_1, a_2, \cdots , a_j', \cdots, a_n$ and $s_1$ to the algorithm that finds collisions.  The algorithm attempts to find $s_2$ such that $f_{(a_1, a_2, \cdots, a_j', \cdots, a_n)}(s_2) = T'$.

  If the algorithm returns $s_2$ that collides with $s_1$ and $j \notin s_2$, then $s_2$ is a solution to our original problem, since swapping $a_j$ and $a_j'$ does not affect the sum over $s_2$.

Where the emphasis is mine.

Where $f$ concatenates $\stackrel{\rightarrow}{a}$ with the sum of the $a_i$'s:

$$ f( \stackrel{\rightarrow}{ a } , S) = f_{(a_1, a_2, \cdots, a_n)}(S) = \ \stackrel{\rightarrow}{a}, \sum_{i \in S} a_i \mod 2^{l(n)} $$

(taken from the top of page 3 from the same paper).

For the life of me, I don't understand how $s_2$ is a solution to the original instance.  Can someone elaborate on what they mean?  What am I missing?

The above definition for the subset sum problem is, if I'm not mistaken, just another form of the pigeonhole subset sum problem (i.e. $\sum_j a_j < 2^n -1$ ).  If I read the above right, they are claiming that, given an oracle that finds collisions, they can then construct a solution to the original (pigeonhole) subset sum problem but I do not see how this is done.  Any help would be appreciated.

The way I understand it is the following.

Note that for $s_1$, $f_\vec{a'}(s_1)=T$  (because the sum was $T'$ and we replaced $a_j$ with $a'_j$ and we know that $j\in s_1$.

Now, they search for a collision, i.e., another $s_2$ such that $j\notin s_2$,
but $f_\vec{a'}(s_2)=T$. (is there a typo there, having $T'$ instead?)
Now, what is $f_\vec{a}(s_2)$? also $T$, right? since $j\notin s_2$...

Does it help?


Hindley-Milner system with let expansion I'm reading these slides that present Hindley-Milner type inference. In the system HM, we have the following let rule:

$\dfrac{\Gamma \vdash t:S \;\; \Gamma,x:S \vdash t':T }{\Gamma \vdash \text{let} \, x = t \, \text{in} \, t':T}$

Here $S$ is a type scheme, i.e $S ::= S | \forall a. S$, which allows polymophism only on let expressions. Then, the following let rule is proposed for a system HM':

$\dfrac{\Gamma \vdash t:T \;\; \Gamma \vdash [t|x]t':U }{\Gamma \vdash \text{let} \, x = t \, \text{in} \, t':U}$

so all the occurrences of the binding are replaced and the result needs to be type checked. There is a theorem relating the two approaches:

$\Gamma \vdash_{HM} t:S \iff \Gamma \vdash_{HM'} t: S$

and as a consequence the following corollary is established:

  Let $t^*$ be the result of expanding all let's in $t$ according to the rule. $let \, x = t \, \text{in} \, t' \to [t|x]t'$. Then, $\Gamma \vdash_{HM} t:T \implies \Gamma \vdash_{F_1} t^*: T$. Furthermore, if every let-bound name is used at least once, we also have the reverse $\Gamma \vdash_{F_1} t^*: T \implies \Gamma \vdash_{HM} t:T $.

Here $F_1$ is the simply-typed lambda-calculus.

I would like to gain some intuition on why this reverse direction holds. How does a let-bound name that is not used affect typing? Any reference is also appreciated.

I think something somewhat trivial is happening here, that is if the let binding is not used, then you can let bind an ill-typed term, e.g. if:

$t =\ $let x = (if 3 then 4 else false) in 5

then $t^* =\ $ 5 which is well-typed in $\mathrm{HM}$, even though t is not. If every let-binding is used, though, then this pathology can't happen.


Algorithm complexity similar to Selection Sort I'm working on an algorithm that takes an array of $N$ values and it will iterate through each of the values and in each of them iterate through the rest of the array to the right. So the first value will check $N-1$ positions, the next one will check $N-2$, etc

I'm a bit confused about the time complexity of my algorithm. I remembered that Selection Sort does a similar operation and I checked it's considered $O(N^2)$ best and worst case. Why is that? If both algorithms check less and less positions every new position I imagined it would be some complexity between $O(N)$ and $O(N*log(N))$ and not $O(N^2)$.

Another question. If I did my algorithm only for half of the array what would the complexity be? I mean starting at the middle position and only doing the algorithm to the right side for example so the middle position would check only $N/2-1$ positions and the next only $N/2-2$, etc.
I guess it would be $O((N/2)^2)$ which would be $O(N^2/4)$ and so still $O(N^2)$?

You have to count. Intuition is necessary, but you must calculate.

$$ 1+2+\cdots+N-1 = N(N-1)/2 \in \mathcal{O}(N^2)$$ by Gaussian summation rules.

In asymptotic notation, the constants are removed. For example.

$\mathcal{O}(N/k) = \mathcal{O}(N)$ as long as $k$ is a constant.


Explain this Neural Network used for Knowledge Graph Embedding I am interested in better understanding the neural network used in the paper LogicENN A Neural Based Knowledge Graphs Embedding Model with Logical Rules. To my knowledge this is the most advanced and complex knowledge graph embedding.

The neural network is described as follows:

Entity pairs, $[h,t]$ , are input and relations are output.

The score of a given triple $(h, r, t)$ is $f^r_{h,t}$ and is given by:

The beta vector are the embedding of relations.

The phi vector is the feature mapping of the hidden layer of the network which is shared between all relations.

This neural network works with a single hidden layer.

The first problem is: when I look at the picture, I think this neural network should have multiple hidden layers but in the text it's written "we use a single hidden layer".

The second problem is: when I look at the picture, I think that there is no direct relation between the outputs and the hidden layers but in text it's written "the feature mapping of the hidden layer of the network which is shared between all relations".

Please, explain this neural network. Any help is appreciated.

Well basically, without loss of generality, they use a single hidden layer for the neural network to show theoretical capabilities of those networks. Practically, sometimes it is better to use more hidden layers and sometimes, on the other hand, adding more hidden layers only adds complexity and it is more time consuming for a model to be trained. if your data is linearly separable (which you often know by the time you begin coding a NN) then you don't need any hidden layers at all. Of course, you don't need an NN to resolve your data either, but it will still do the job.

In their experiment, they are using 3 hidden layers. People usually come up with the best number of hidden layers by experiment. There is no magic formula for selecting the optimum number of hidden neurons. However, some thumb rules are available for calculating the number of hidden neurons. A rough approximation can be obtained by the geometric pyramid rule proposed by Masters (1993). For a three layer network with n input and m output neurons, the hidden layer would have $ \sqrt{n \times m} $ neurons.


Can we improve internet speed by serializing timestamps? If we (scientists) came up with a way of representing numerical timestamps as letters hence reducing the number of bytes needed to represent timestamps, would that mean an improvement in internet speed as less data needs to be serialized?

If we restrict ourselves to the 52 letters from the Latin alphabet that are commonly used in English (i.e. we exclude letters like ï as seen in words like naïve), then we need 6 bits to encode each letter.
However, in 6 bits, we can encode 64 different numbers.
That means our encoding using letters is only 81.25% as dense as the encoding using numbers.
This is actually the best case scenario. Most protocols are octet-oriented, so we have to pad our representation to a full octet boundary. That means that a single letter will be encoded in 8 bits. A single letter can express 52 timestamps, but 8 bits can express 256 numbers.
We could try to find an alphabet with 64 letters (or even better 256 letters), then the representation using letters would be as good as the representation using numbers … but why go through all the trouble of representing timestamps (which, after all, are numbers) as letters, then at the other side of the transmission turn them back into numbers again when simply representing them as numbers is in the worst case just as efficient as when using letters and in the best and average case is significantly more efficient?
After all, computers and networks can only process and transport numbers, so whatever representation using letters you find, you will have to represent that representation using numbers again, and this representation cannot be more efficient than the original one.
Basically, you start off with a timestamp, which is a number, you need to end with a timestamp at the other end, which is a number, and the network can only transport numbers.
Your proposal looks like this:

Encode the number as letters
Encode the letters as a number
Transmit the number
Decode the number as letters
Decode the letter as a number

Whereas what we are doing today is:

Transmit the number

Which is more efficient.


How does a computer determine the data type of a byte? For example, if the computer has 10111100 stored on one particular byte of RAM, how does the computer know to interpret this byte as an integer, ASCII character, or something else? Is type data stored in an adjacent byte? (I don't think this would be the case as this would result in using twice the amount of space for one byte.)

I suspect that perhaps a computer does not even know the type of data, that only the program using it knows. My guess is that because RAM is RAM and therefore not read sequentially, that a particular program just tells the CPU to fetch the info from a specific address and the program defines how to treat it. This would seem to fit with programming things such as the need for typecasting.

Am I on the right track?

Your suspicion is correct. The CPU doesn't care about the semantics of your data. Sometimes, though, it does make a difference. For example, some arithmetic operations produce different results when the arguments are semantically signed or unsigned. In that case you need to tell the CPU which interpretation you intended.

It is up to the programmer to make sense of her data. The CPU only obeys orders, blissfully unaware of their meaning or goals.


What is the time complexity of this function? This is an example in my lecture notes.
Is this function with time complexity $O(n \log n)$?.
Because the worst case is the funtion goes into else branch, and 2 nested loops with time complexity of $\log n$ and $n$, so it is $O(n \log n)$. Am I right?

int j = 3;
int k = j * n / 345;
if(k > 100){
    System.out.println("k: " + k);
}else{
    for(int i=1; i<n; i*=2){
        for(int j=0; j<i; j++){
            k++;
        }
    }
}

Time complexity of mentioned algorithm is $O(1)$, because for $K>100$ you have a constant operation (println), and you know: $j=3,k = 3 \cdot n / 345 \implies 100 = 3\cdot n / 345 \implies n=11500$, means for $n\ge 11500$ your algorithm has a constant running time (also other part is constant, because just for $n<11500$ will be called).

For being more clear take a look at this question.


Can a language be Turing Complete if its only provision for unlimited code/memory is through recursion? We've developed an esoteric language. In this language, a program contains a static amount of code, and a static amount of storage space. However, parts of the program can recurse, so the interpreter will spawn another copy of a subset of the code and additional storage space to match. Can this language be Turing Complete?

Given your very strict interpretation of limited memory size, limiting
also the size of integers, one consequence is that it is not possible
to play encoding games with integers (such as Gödel enumerations or
encodings).

Another consequence is that you cannot have a way of retrieving the
address of a memory location in order to make pointers. The reason is
that unbounded recursion implies that memory addresses will have
unbounded size (which is a bit inconsistent on the implementation
side, but I guess I have to ignore it). If there was an instruction to
retrieve the address of a variable, the space needed to store this
address could well exceed all of the memory available for a given
recursive call. Hence there is no hope of manipulating addresses.

Hence, each recursive call can only access a finite amount of
information, say $n$ bits, which may be seen also a one of $2^n$
symbols. There is as much information, i.e. one of those symbols,
memorized for each of the previous calls, but not accessible on the
recursion stack.

Of course a little bit of information is passed as parameter at each
recursive call, and some is returned when it terminates.

So all this pretty well describes a pushdown automaton.

Hence all you can do is recognize or generate context-free languages,
or some equivalent computation. You are pretty far from Turing
completeness.

But if your model allowed storing pointers to local variables, then,
even without Gödel encodings in integers, you could have Turing
completeness.


Number of sentences and sentential forms generated by a grammar In this question, I'm considering only "finite grammars". A finite grammar can only produce a finite number of distinct sentences. The following grammar is finite in my definition:
S         → AB
A         → B | a
B         → a | b

It can only generate the following finite number of sentences: aa, ab, ba, bb
On the other hand, the following grammar is not finite:
S         → AB
A         → AA | B | a
B         → a | b

Because it can create an infinite number of sentences: aa, aaa, aaaa, aaaaa, ...
Now to the actual question. Suppose the following finite grammar:
S         → variable = math_expr
variable  → a | b | c
math_expr → INT | function
function  → func_1() | func_2(INT, INT, INT, INT)
INT       → 1 | 2 | 3 | 4 | 5

I want to know if there is some kind of formula that calculate the number of sentences and sentential forms that can be generated by a finite grammar.
Example of sentences: b = func_2(2,4,3,3), a = func_1()
Example of sentential forms: b = func_2(2,2,INT,INT), c = math_expr,  S
At the moment, I am able to know the number of sentences and sentential forms by applying a Breadth-First Search (BFS) starting from the S node.
However, because I'm working with search in program synthesis, it would be great to know the size of the domain without the need of applying an exhaustive search on it.
Question: How can I find the number of sentences and sentential forms given only an arbitrary finite grammar?
For the first finite grammar I showed here, the answer is easy to calculate by hand:
Sentences: aa, ab, ba, bb
Sentential forms: S, AB, BB, aB, bB, Aa, Ab
So the final answer would be 4 + 7 = 11
However, for the second finite grammar I showed, it is not that easy to calculate it.
PS.: In my original problem, I am working with program synthesis with a Domain Specific Language (DSL). I tagged CFG with the hope that the same applies, granted I'm not 100% sure.

If the context-free grammar is unambiguous, you can count the number of sentences it generates in a linear scan with a carefully chosen order.
I'll assume we have removed all useless symbols and cycles from the grammar.  If it is finite and free of useless symbols and cycles, then it should not contain any recursion.
Let $N(A)$ denote the number of sentences that can be constructed starting from nonterminal $A$, i.e., $N(A) = |L(A)|$.  If the grammar is unambiguous and has no recursion, you can compute $N(A)$ for each nonterminal as follows.  Construct a dependency graph with one vertex per nonterminal, and an edge $A \to B$ whenever the grammar contains a rule $B ::= \cdots A \cdots$, i.e., a rule with $B$ on the left-hand side and $A$ on the right-hand side.  If the grammar has no recursion, then this is a dag.  Visit the vertices of this graph in topologically sorted order.  Then it is easy to compute the number of sentences: for example, if we have the rule $A ::= BaC | DE$, then we have
$$N(A) = N(BaC) + N(DE) = N(B) N(a) N(C) + N(D) N(E).$$
That's an example, but you can do the same for any number of alternatives on the right-hand side and any string of symbols in each alternative.  Note that we have the base case $N(a) = 1$, for any terminal $a$.
I expect this can be adjusted to count the number of sentential forms as well, but I haven't tried to work out the details.
This relies crucially on the grammar to be unambiguous.  If the grammar is ambiguous, I'm not sure whether there is any efficient algorithm -- I just don't know.
For unambiguous grammars, see also https://en.wikipedia.org/wiki/Chomsky%E2%80%93Sch%C3%BCtzenberger_enumeration_theorem, which shows how to count the number of sentences of a particular length, even if the grammar is not finite.


Irregularity of L = {a^i b^(j+3)| i!=j } I have a question to find out that $L = \{a^i b^{j+3}\mid i\ne j \}$ is regular or not. I know that it is not regular. I tried with pumping lemma but I am finding just a specific number of $v$'s in $u v^i w$ that not satisfies the language condition, but not ALL $v$'s. What are the best choices for $i$ and $j$ to prove with pumping lemma that this is not a regular language?

When you get stuck trying to prove a language is not regular by the Pumping Lemma, as in this example, because there doesn't seem to be a good choice of $u,v,w$, it's sometimes helpful to use closure properties first, to transform the problem. This is a good example of when this paradigm is useful.

We'll do this by contradiction. Suppose that $L$ were regular. Then since regular languages are closed under complement, $\overline{L}$ would be regular. Now $\overline{L}$ isn't particularly easy to describe, since it contains strings like $bababbba$, but what is $\overline{L}\cap a^*b^*$? This is just $a^nb^{n+3}=a^nb^nb^3$. Since regular languages are closed under intersection and $a^*b^*$ is regular, that would mean that $a^nb^nb^3$ would be regular. I'll bet you can now do a pumping lemma proof to show that this language wasn't regular.


Easy instances of the coloring problem on graphs with degree at most 4 Given a graph with some set of colors, the goal of the coloring problem is to color the input graph with as few number of colors as possible, such that no adjacent vertices have the same color.

In general, the problem is hard. For trees and cycles, the problem is solvable in polynomial time. I am interested in bounded degree instances or more precisely graphs of degree at most 4. Is there any non-trivial subclass of graphs of degree at most 4 for which the coloring problem is solvable in polynomial time?

You can of course take any graph class for which coloring is easy, and additionally require that the maximum degree is at most 4. For example, every bipartite graph of maximum degree at most 4 works. Or "bipartite" could be replaced with say "outerplanar" or more generally "small cliquewidth".

But having maximum degree at most 4 alone will not work. That is, coloring remains hard for (i) 4-regular graphs and (ii) planar graphs of maximum degree 4.


Amortizing or batching circuit evaluation for many different inputs? Suppose that I have a boolean function of size $k$ with $n$ inputs. I would expect to be able to evaluate it on all possible inputs in time $O(k*2^n)$ simply by calculating all the intermediate values for every possible input. Is it possible to do this faster in general, for example in time $(k+2^n)$?

In the special case of linear functions I would expect to be able to do this by going from point to point in gray code order, so that only one bit changes each time, or by calculating tables of size $1,2,4,8,\dots,2^n$ for the functions produced by holding the last $n-i$ bits at zero, using each table to calculate the next one. Are there generalizations of this for general boolean circuits, or are there proofs that no such generalizations are possible?

I have a slightly off-the-wall motivation for this. I am interested in the simulation hypothesis. One reason for running a large number of simulations would be to investigate the result of running the same scenario for all possible inputs.
I would be interested to learn that there was, or was not, a significantly more efficient approach which would achieve the same ends, especially as such a more efficient approach would not have a direct link between any particular set of simulated histories and any particular act of the program, as the increased efficiency of the program would be mean that it could not be the case that every possible history could be mapped to its own set of program activity.

Edit - batch calculation as described above is more powerful when the batch step is used inside a recursive call, as then you don't need to go through all 2^n answers at once. For #P-complete problems, each recursive call returns the number of solutions found within some range of values. For NP-complete problems, each recursive call returns whether a solution is found in some range of values.

Each recursive call uses the batch mechanism to compute the answers for 2^k different problems. This corresponds to k bits of the n bits available. So the lowest level of the recursion just looks at 2^k different results to see whether they are solutions or not, but the highest level looks at 2^k results which are each e.g. the number of solutions found within 2^(n-k) evaluations, each with the k top bits of n set to a different value. Here I assume that the language used to express our function f() is sufficiently flexible that level i+1 can treat level i as just a function f() to consider at 2^k points, even though this f() amounts to a transformation of the original f() producing a function which counts the number of solutions in a particular range or says whether this number is non-zero.

If the cost of level i+1 of the recursion is X_i+1 = b + a*X_i then for a!=1 we get
X_i = a^i + b/(1 - a) and for a=1 we get X_i = ib (with variations depending on what X_0 is). Remember that the number of possible solutions examined at each level is 2^(ik) so for small a compared to 2^k this is a large speedup, and for the case of a=1 we would find that P=NP and even P=#P.

(I remain interested in answers that would firm this up or extend this)

Some further thoughts, at least for the case when batch generation is done by feeding a gray code or other simply generated sequence into a circuit with internal memory.

For an ordinary combinatorial logic circuit without memory, we can bound the size of a circuit needed to evaluate a general function on n bits in two ways: by providing a general construction with known size, or by observing that 2^2^n different functions require 2^2^n different circuits, so the size of the largest circuit encountered cannot be so small that there are less than 2^2^n different circuits of up to that size. Knuth Vol 4A section 7.1.2 Theorem L shows that these bounds are in fact very close together, and require a circuit of size O(2^n/n) for a general function on n bits. So combinatorial logic circuits without memory do not waste much complexity by having many different circuits computing the same function.

If we stick to the design of a gray code generator feeding a circuit with internal memory, the only source of variation is the choice of the circuit, which now includes memory elements. The description of such a circuit needs a few more bits per item to offer the possibility of memory elements, but this is just a constant factor. By the requirement that to be able to compute any of 2^2^n different functions we must provide 2^2^n different circuits, and by the observation that ordinary combinatorial logic circuits do not have staggering inefficiencies, I think we find that introducing internal memory into an otherwise pedestrian design will not allow all possible functions to be calculated using only circuits of size significantly smaller than their best combinatorial logic implementation.

(but if P=NP our simulator has other options, such as Valiant Approximate Counting, which allow them to estimate the fraction of input states leading to a particular outcome in a simulation, without actually simulating all possibilities).

I remain interested in any comments, pointers, or whatever, about anything that bears on this.


The upper bound on a Nondeterministic Finite Automata's configurations number In "Engineering: A Compiler" 2nd ed. by Cooper and Torczon,
in 2.4.1 "Nondeterministic Finite Automata" of Chapter 2,
section "Equivalence of NFAs and DFAs"

discusses the upper bound of a NFA's configurations number.

Here

NFA stands for Nondeterministic Finite Automata
DFA stands for Deterministic Finite Automata

NFA is a  is a five-tuple $(S, \Sigma, \delta, s_0 , S_A)$, where

$S$ is the finite set of states in the recognizer, along with an error state $s_e$.
$\Sigma$ is the finite alphabet used by the FA. Typically, $\Sigma$ is the union
of the edge labels in the transition diagram.
$\delta(s,c)$ is the FA's transition function. It maps each state $s ∈ S$
and each character $c \in \Sigma$ into some next state. In state $s_i$ with input
character $c$, the FA takes the transition $s_i \xrightarrow{\text{c}}\delta(s_i ,c)$.
$s_0 \in S$ is the designated start state.
$S_A$ is the set of accepting states, $S_A \subseteq S$.

A configuration of a NFA is defined as follows

  Each time the NFA must make a nondeterministic choice, the NFA clones
  itself to pursue each possible transition. Thus, for a given input
  character, the NFA is in a specific set of states, taken across all of
  its clones.

  In this model, the NFA pursues all paths concurrently. At
  any point, we call the specific set of states in which the NFA is
  active its configuration.

  When the NFA reaches a configuration in
  which it has exhausted the input and one or
  more of the clones has reached an accepting state, the NFA accepts the
  string.

Given the definitions above, the books states

  Consider the state of an NFA when it has reached some point in the
  input string. [...] the NFA has some
  finite set of operating clones.

  The number of these configurations can be bounded;

  for each state, the configuration either includes one or
  more clones in that state or it does not. Thus, an NFA with $n$ states
  produces at most $\lvert\Sigma\rvert^n$ configurations.

My question.

Please explain in as much details as possible, how $\lvert\Sigma\rvert^n$ is derived.

I need help, because while trying to follow the book's reasoning, I get lost right after this sentence

  for each state, the configuration either includes one or
  more clones in that state or it does not.

This sounds like the upper bound on the number of configurations should be $2^n$, but instead the book gives $\lvert\Sigma\rvert^n$ bringing in $\Sigma$ seemingly out of the blue.

Remember that:
We can view a nondeterministic computation as a directed acyclic graph of configurations indexed by time.

I have a guess that in your eyes:
$2^n$ for both, one directs itself and one directs others and at most every has the $\Sigma$ chance to go next state, maybe to itself, maybe the other state, so from $1$ to $n$ state, an NFA produces at most $\mid\Sigma\mid^n$ configurations.

Here are more details: http://www.cse.msu.edu/~torng/360Book/NFA/


using orientation sensor data to predict image points I want to use Android's gyro/accelerometer/magnetometer to predict (over a very short time interval) how image points corresponding to a fixed object will change (without trying to scan for them in the image).  In particular, suppose we have an object of known size with model points $v_1, \dots, v_N$.  In this question, all vectors are assumed to be in homogenous form.

Here is what I am trying:

Detect the object.  Let the pixel coordinates of the model points be denoted by $u_1, \dots, u_N$.  Given the calibration matrix $K$ and negligible lens distortion, solve the PnP problem to get rotation $R_0$ and translation $t_0$ from the coordinates in which the vectors $v_1, \dots, v_N$ are defined into camera-centric coordinates, shown in black in the image above.
In particular, the solution to the PnP problem solves the following equation.
$$
u_i = K \begin{bmatrix} R_0 &  t_0 \\ 0^\top & 1\end{bmatrix} v_i.
$$
Simultaneously query the Android rotation sensor for a rotation matrix.
This is the relative orientation from Earth coordinates to the device coordinates (colored frame in the picture above).
The direction of the this transformation is discussed informally in the Android developer site:

  The rotation vector represents the orientation of the device as a combination of an angle and an axis, in which the device has rotated through an angle $\theta$ around an axis ($x$,$ y$, or $z)$.

Let $R_1$ denote this rotation matrix.

Rotate the phone a small amount and query the rotation sensor again for $R_2$.
Render the predicted location to the pixel coordinates.  For this, lets assume the sensors and the camera are collocated, so that the transformation from camera coordinates to device coordinates is a pure rotation:
$$
D=
\begin{bmatrix}
0 & -1 & 0 & 0\\
-1 & 0 & 0 & 0 \\
0 & 0 & -1 & 0 \\
0 & 0 & 0 & 1
\end{bmatrix}
$$
This matrix maps the black frame to the colorful frame in the picture.
Note that the $+z$ axis of the camera frame (black in the picture) is meant to point out of the back of the phone, so that it constitutes a right-handed coordinate frame.

The transformation from the body coordinates of the object $v_1, \dots, v_N$ to the image coordinates in the perturbed camera frame $u_1', \dots, u_N'$ are given by
$$
u_i'
=KD\begin{bmatrix}R_2 R_1^\top & 0 \\ 0^\top & 1 \end{bmatrix} D \begin{bmatrix} R_0 &  t_0 \\ 0^\top & 1 \end{bmatrix} v_i,
$$
where we used the fact that $D=D^{-1}.$

Right now, I am stuck tying to verify that this equation actually works.  Here is a simple experiment (that I have tried in Python).
Let $v = (0, 0, 1)^\top,$ and suppose it is already defined in the camera coordinate frame, i.e., $R_0=I$ and $t_0=0.$
Moreover assume that $R_1= I,$
Then, I rotate the device by a small angle about the $x$ or $y$ axis (which are the same for the device and for the Earth because $R_1=I.$)
This rotation constitutes $R_2$ from the equations above.
When I try this in Python, this is what I observe for various counter-clockwise rotations:

test rotation of device :: expected result :: observed result

rotate device about $+x$ :: $x$ pixel coordinate increases ::  opposite behavior

rotate device about $-x$ :: $x$ pixel coordinate decreases :: opposite behavior

rotate device about $+y$ :: $y$ pixel coordinate decreases :: as expected

rotate device about $-y$ :: $y$ pixel coordinate increases :: as expected

It turns out that I had two bugs that broke my experimental results:

Even though the rotation matrix reports the rotation from Earth to Device, I should have been applying the opposite rotation to the point. It took me a day to convince myself of this.  Basically, if you rotate the whole frame about, e.g., $+x$, then coordinates that remained fixed w.r.t. the device will rotate w.r.t. the Device frame about $-x$.
I had a wrong minus sign in the rotation about the y-axis in the experimental results that I reported at the end.  Note that y-axis rotations have a different +/- pattern than x- and z- axis rotations.  See wikipedia for basic rotations.

The method described herein works fine (at least in theory).  I'll post an update after I port my python dummy code into Android and see how it works.


Facebook Hackercup 2013: Balanced Smileys On Facebook HackerCup 2013, they asked the following question:

  Your friend John uses a lot of emoticons when you talk to him on
  Messenger. In addition to being a person who likes to express himself
  through emoticons, he hates unbalanced parenthesis so much that it
  makes him go :(

  Sometimes he puts emoticons within parentheses, and you find it hard
  to tell if a parenthesis really is a parenthesis or part of an
  emoticon.

  A message has balanced parentheses if it consists of one of the
  following:

  An empty string ""
  One or more of the following characters: 'a' to
  'z', ' ' (a space) or ':' (a colon)
  An open parenthesis '(', followed
  by a message with balanced parentheses, followed by a close
  parenthesis ')'.
  A message with balanced parentheses followed by
  another message with balanced parentheses.
  A smiley face ":)" or a
  frowny face ":("

  Write a program that determines if there is a way to
  interpret his message while leaving the parentheses balanced.

Balancing parentheses is talked about in a lot of places.  E.g. (()) vs ()().  You can count

'(' = +1
')' = -1

Then you have to make sure your sum never falls below 0.

In this question they consider :) and :( as balanced and I wonder how much it changes things. One solution says that you can replace r'[^a-z:() ], '', ':)' -> '}' and ':(' -> '{'.

While I agree with the first sub, why are the last two substitutions valid?

The solution is correct because the "}" and "{" symbols are considered "optional" parentheses.

(:):):(:::) → (}}{}

The left one is an example of an input string, the right is the preprocessed version of it.  If you read the algorithm, you see that they keep two values,

min_level, max_level = (0, 0).

Reading the actual solution should convince you.


how to calculate $2^{5000}$ mod 10 without calculator in fast way? How is it possible to calculate $2^{5000}$ mod 10 without using a calculator in a fast way?
The result with calculator was 6.

Consider the first few powers of 2:

  1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024…

Now take all of those mod 10:

  1, 2, 4, 8, 6, 2, 4, 8, 6, 2, 4…

Try to solve it yourself, from this, before continuing to read.

There's a theorem that says, if $x \times y \cong z \mod m$, then $x' \times y \cong z \mod m$, for any $x' \cong x \mod m$. This means that, if you ever find two powers of two that are congruent (mod 10), the values in between them will form a cycle that loops forever. And it'll always be possible to find such congruent powers, so there'll always be such a cycle with ten or fewer elements in it. (All three of these statements can and should be proven, but those proofs are left as an exercise for the reader.)

In this case, the first such pair of values are 2 and 32. In other words, $2^5 \cong 2^1 \mod 10$. Which means that $2^6 \cong 2^2 \mod 10$, and $2^7 \cong 2^3 \mod 10$, and so on. In general, $2^x \cong 2^y \mod 10$ iff $x \cong y \mod 4$ (for integers $x, y \geq 1$).

So all you have to do now is reduce 5000 mod 4; since we know that $100 \cong 0 \mod 4$, 5000 must also be congruent to zero (and, more relevantly, to four, since our formula only holds for integers ≥ 1—do you see why?). Therefore, $2^{5000} \cong 2^4 \mod 10$. Now you just need to know the first few powers of two, or multiply them out longhand, to find that the answer is $2^{5000} \cong 2^4 \cong 6$.


Pebble game lower bound? This paper says pebble games have super linear lower bound for every fixed $k$ https://dl.acm.org/citation.cfm?doid=62.322433.

Why is it not considered proof of constructive example for a function in $NP$ which requires superlinear runtime?

The time hierarchy theorem gives, for every $k$, a function in P with a runtime lower bound of $\Omega(n^k)$. Unfortunately, this is not enough to separate P from NP: to do this, we need a function in NP with a superpolynomial runtime lower bound.

One popular approach for tackling the P vs NP question is via circuits. The best lower bounds for explicit functions are only linear. Perhaps this is the context in which you heard of superlinear lower bounds as a seeming barrier.


What is the single type in a dynamic typing language? Regarding static typing and dynamic typing, Practical Foundation of Programming Languages by Harper says:

  There have been many attempts by advocates of dynamic typing to
  distinguish dynamic from static languages. It is useful to consider
  the supposed distinctions from the present viewpoint.

  Dynamic languages associate types with  values, whereas static languages associate
  types to variables. Dynamic languages associate  classes, not types, to  values  by tagging them with identiﬁers such as num and
  fun. This form of classiﬁcation amounts to a use of recursive sum
  types within a statically typed language, and hence cannot be seen as
  a distinguishing feature of dynamic languages. Moreover, static
  languages assign types to expressions, not just variables. Because
  dynamic languages are just particular static languages (with a single
  type), the same can be said of dynamic languages.
  Dynamic languages check types at run-time, whereas static language check types at compile time. Dynamic languages are just as surely
  statically typed as static languages, albeit for a degenerate type
  system with only one type. As we have seen, dynamic languages do
  perform class checks at run-time, but so too do static languages that
  admit sum types. The difference is only the extent to which we must
  use classiﬁcation: always in a dynamic language, only as necessary in
  a static language.
  Dynamic languages support heterogeneous collections, whereas static languages sup-
  port homogeneous collections. The purpose of sum types is to support heterogeneity,
  so that any static language with sums admits heterogeneous data structures. A typical
  example is a list such as

 cons(num[1]; cons(fun(x.x); nil))

  (written in abstract syntax for emphasis). It is sometimes said that such a list is not
  representable in a static language, because of the disparate nature of its components.
  Whether in a static or a dynamic language, lists are type homogeneous, but can be class
  heterogeneous. All elements of the above list are of type dyn; the ﬁrst is of class num,
  and the second is of class fun.

  Thus, the seeming opposition between static and dynamic typing is an illusion. The
  question is not whether to have static typing, but rather how best to embrace it. Conﬁning
  one’s attention to a single recursive type seems pointlessly restrictive. Indeed, many so-
  called untyped languages have implicit concessions to there being more than one type.
  The classic example is the ubiquitous concept of “multi-argument functions,” which are
  a concession to the existence of products of the type of values (with pattern matching).
  It is then a short path to considering “multi-result functions,” and other ad hoc language
  features that amount to admitting a richer and richer static type discipline.

So "dynamic languages are just particular static languages (with a single type)". What is the single type in a dynamic  language?

For example, Python is said to use the reference model of variables, as opposed to the value model of variables. References are not explicit.

Is it because of references that a list in Python can have elements of different "types", i.e. achieving heterogeneous collections in the quote?
Is the "single type"  in Python the type for all the references?  Is it the same for other dynamic  typing languages, i.e. is  the "single type"  in a dynamic typing language the type for all the references? Or is reference just an implementation option of the single type in a dynamic language, and there might be other implementation options?
Do references which refer to values of different "types" have the same type?

Thanks.

The "single type" for Python is called "object" and described in https://docs.python.org/3/reference/datamodel.html:

Objects are Python’s abstraction for data. All data in a Python program is represented by objects or by relations between objects. (In a sense, and in conformance to Von Neumann’s model of a “stored program computer”, code is also represented by objects.)
Every object has an identity, a type and a value. An object’s identity never changes once it has been created; you may think of it as the object’s address in memory... An object’s type determines the operations that the object supports (e.g., “does it have a length?”) and also defines the possible values for objects of that type... The value of some objects can change. Objects whose value can change are said to be mutable; objects whose value is unchangeable once they are created are called immutable.

Of course, note that "type" and "value" are not used here in the same way as in Harper's book: Python's "type" is what Harper calls "class".


Store a n-bit string using only O(log n) space Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.

There are $2^n$ many $n$-bit strings, but only polynomially many strings of length $O(\log n)$.


Proving $\{ a^n b^m \mid n \leq m^2 \}$ is not context-free using pumping lemma I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof.
The language is
$$L =  \{ a^n b^m \mid n \leq m^2 \}$$
Assume Demon picks $p$ and I choose $s = a^{p^2}b^p$ and $s = uvwxy$ such that $p \geq |vwx|$.
The first case is $vwx = b^j$. If we choose $i = 0$ everything is ok and the relationship isn't right.
The second case is $vwx = a^j$. If we choose $i = 2$ every thing is ok.
I get stuck when  $vwx = a^j b^k$. How can I finish the proof in this case?
Did I choose the right string? I repeated them for $s =  a^{p}b^p$ but it didn't work.

When $vwx = a^j b^k$, there are two possibilities:

$v$ contains both $a$s and $b$s, or $x$ contains both $a$s and $b$s. In this case $uv^2wx^2y \notin a^*b^*$, and in particular $uv^2wx^2y \notin L$.
$v = a^s$ and $x = b^t$, where $s,t>0$ and $s+t \leq p$ (since $|vwx| \leq p$). In this case, $uv^0wx^0y = a^{p^2-s}b^{p-t}$, and so $p^2 - s \leq (p-t)^2 \leq (p-1)^2$, which translates to $s \geq 2p-1$, which is impossible, since $s \leq p-1$.


Find the smallest group of numbers with sum bigger then $X$ Given a list of numbers $S$ where $0 < s_i < 100$, find the minimum sum group of numbers with a sum bigger than $X$.
Each number can be used multiple times.
Ex: for $S = [3,4.1], X = 10$ the solution is $[3, 3, 4.1]$
Is it a known problem? What will be the best way of solving it?
For now, my best solution is to randomly pick numbers and repeat the process multiple times.

Assuming you are looking for $S' \subset S$ with minimal $\sum_{x \in S'} x > X$ like Steven suggested, then you should be able to reduce the problem to an instance of knapsack with weights $w_i$ and costs $c_i$ with $w_i = c_i = s_i$ for every $s_i \in S$ where the weight of the knapsack is bounded by $X$.
If the solution $K := \sum_{x \in S'} x$ is not greater than $X$, you need to repeat the process by setting $X := X + \varepsilon$ where $\varepsilon$ is the minimal distance between any two subset sums of $S$ and running knapsack again until it yields a solution $K > X$.
Edit: Turns out that finding $\varepsilon$ isn't an easy problem. I first assumed $\varepsilon$ is the minimum between any two numbers in $S$, which can be found by sorting the list and finding the minimum between two adjacent elements. This would yield a good approximation in most cases, but it might not be the optimal solution. If your problem statement uses $\geq$ instead of $>$, transforming the problem into knapsack will yield an optimal solution, no repetitions required.


Difference between selecting a large pool of individuals for reproduction, and selecting two parents specifically I have implemented a genetic algorithm for an optimization problem and I'm now trying to improve it to see if I can find better solutions or faster convergence.

I am confused about the selection part of the algorithm and how it relates to selecting parents for cross-over. In my mind these things are not the same yet many resources seem to treat them the same, and I can't figure out how or why.

As far as I understand the terms:

Selection means: selecting a subset of the current population (e.g. half) which will reproduce to form the new generation. Non-selected individuals are discarded. Selection should be based on fitness in some way such that more fit individuals are selected with higher probability (but bad individuals can still be selected for sufficient genetic diversity).
Selecting parents for cross-over means: from the group of selected individuals, take two parents to cross-over and form one child. (I know schemes are possible with more than two parents and/or more than one children but let's keep it simple). This step should be repeated until I filled the new population.

Let's say I have a population of 50 and select half of them, leaving me with 25 parents which will now reproduce to form 50 new individuals. Since there are only 25 parents and I need 50 children, probability is high that one parent can have multiple children. There is of course a chance that the same parent reproduces with itself giving an identical copy (ignoring mutation for now).

My point here is that the two concepts are not the same. In 1 I select many individuals that will later reproduce, but for now I am merely letting the non-selected individuals die. In 2 I then select two parents specifically to cross-over and form one new individual. It is entirely possible (though obviously very unlikely) that I keep selecting the same 2 parents from my pool 25 and ignore the others.

I know of various selection operators but I am confused about which is applied to which scenario. For example:

Tournament selection: grab a few (e.g. 2 or 4) individuals at random, and then take the best. This gives me just one individual. I can use this 25 times to select the 25 individuals (1), or I can use this twice on the group of selected individuals to select two parents for reproduction (2). Which one is it?
Roulette wheel or fitness proportionate selection: grab an individual at random but with probability based on their fitness. Again: I can use this 25 times to form my pool of selected individuals, or I can use it just twice on that subset of individuals to select the two parents. Which one?
Stochastic universal sampling (SUS): sample several individuals at equally spaced intervals based on fitness. Here it seems clear I am selecting multiple individuals at once (though I suppose it could be "2"), so it seems likely this can be used to form my pool of 25 individuals.
Truncation: simply take the best x% and discard the rest (I know this isn't good for genetic diversity). Clearly this can be used to select the pool of 25 individuals (e.g. discard the worst 25) but how do I now proceed to select two parents?

In general I can apply all of these selection operators to select a large group of individuals, but then I still don't know how to select (from that subset) two parents to reproduce. Is this secondary selection just random? Or should I take fitness into account again here (seems counterproductive, I already selected on fitness previously)? Or should I make sure every parent is equally selected?

The approach defined in 1 is known as Elitism approach or Elitism based selection, which is usually done by selecting the fittest individuals. link1 and link2.

The approach defined in 2 is commonly known as crossover where 2 individuals are repeatedly selected via different algorithms like Tournament selection, Roulette wheel, etc. until the max population is reached.


Do networking ports come from "port-mapped I/O"? Do networking ports come from "port-mapped I/O"?

I was watching a hardware basic video by Brian Will:

https://www.youtube.com/watch?v=9-KUm9YpPm0

And they brought up this concept at 18:15

Initially, I thought it makes sense that networking ports come from the implementation of port-mapped I/O, but it's strange that the video uses the term "devices" instead of "applications" when referring to doing I/O tasks with ports.

Moving my comment to an answer, while the word "port" is being used in the same non-technical sense for both "port-mapped I/O" and for "network ports", they have literally no technical connection.

In port-mapped I/O, the "ports" are accessed with special CPU instructions (in, out in the x86 family) which communicate with hardware devices. For x86, at least, due to the limited "address space" of port-mapped IO (and other reasons), memory-mapped IO or direct memory access are used for bulk data movement. There's nothing magical about port-mapped I/O.  Modern ARM processors, for example, don't have it at all and instead rely entirely on memory-mapped I/O.

Network "ports" are just pieces of data in TCP or UDP packets to allow multiplexing connections to a single IP address (or host because it technically could be over a network level protocol other than IP).  As far as the network hardware and CPU is concerned, the port is just another piece of data in the packet like any other.  The operating system will use the port to route the packet to the appropriate application on the host


When is a permutation k-wise independent? I am a bit confused about what it means for a permutation to be k-wise independent.

If I pick a permutation uniformly at random from $\sigma \in S_n$ then isn't it true that for any $k$ integers, $i_1,i_2,..,i_k$ $\in \{1,2,..,n\}$, the numbers $\sigma(i_1),\sigma(i_2),..,\sigma(i_k)$ are k-wise independent?

A permutation cannot be $k$-wise independent. A distribution of permutations is $k$-wise independent if for $\pi$ sampled according to the distribution and any $k$ different indices $i_1,\ldots,i_k$ and $k$ different values $j_1,\ldots,j_k$, the probability that $\pi(i_1)=j_1,\ldots,\pi(i_k)=j_k$ is $1/n(n-1)\cdots(n-k+1)$. (An earlier version of this answer contained a different definition that, while interesting, is not the standard one.)

A $k$-wise independent distribution is $\ell$-wise independent for any $\ell \leq k$, and the uniform distribution over all permutations is trivially $n$-wise independent. A $k$-wise independent distribution is a distribution which "looks like" the uniform distribution when considering at most $k$ points at a time.

It is easy to see that any $k$-wise independent distribution needs to have support $n^{\Omega(k)}$, and conversely, Alon and Lovett construct such distributions with support $n^{O(k)}$.

Here is a simple example of a $1$-wise independent distribution: it is the uniform distribution over the permutations $\pi_1,\ldots,\pi_n$ given by $\pi_t(x) = (x+t) \pmod{n}$. It is easy to check that for all $1 \leq i,j \leq n$, the probability that $\pi_t(i) = j$ is exactly $1/n$.


Linear programming formulation for the single-source shortest path problem In this course lecture; section 5.1, single-source shortest path (SSSP) is formulated as the following linear program (LP):

\begin{align}
\max &\sum d_u \\
\text{subject to} & \\
d_v &\le d_u + l_{uv} \quad \forall (u,v) \in E \\
d_s &= 0
\end{align}

The comment on the objective function is as follows (emphasis added):

  The variables $d_u$ represent the distances from $s$ to each vertex $u$. Maximizing the sum of the $d_u$ is done by maximizing each one individually, since increasing any single $d_u$ never forces us to decrease some other $d_v$.

I can get its basic idea. However, how to argue that $(\max d_u \;\forall u \in V)$ is equivalent to $(\max \sum d_u)$ more rigorously? Specifically, why is that "increasing any single $d_u$ never forces us to decrease some other $d_v$"?

Any optimal solution to the problem must satisfy
$$
d_v = \min_{u\colon (u,v) \in E} (d_u + \ell_{uv}),
$$
as well as $d_s = 0$, of course. Assuming the graph is connected, you can prove by induction on the length (number of edges) of a shortest path from $s$ to $v$ that $d_v$ is at most the distance from $s$ to $v$, which we denote by $d^*_v$. In particular, the optimal value is at most $\sum_v d^*_v$.

On the other hand, it is not hard to check that $d_v = d^*_v$ (for all $v$) itself is a feasible solution, showing that the optimal value is exactly $\sum_v d^*_v$, and it is achieved only when $d_v = d^*_v$ for all $v$.


What exactly state is in Model Checking So I finally realized the difference between transition systems and automata, and now am closer to understanding Model Checking. One of the last pieces is understanding what exactly "state" is in Model Checking.

It is mentioned that you create a Kripke Structure, which is pretty much just a state-transition system. But the thing is, I don't know what exactly the states are.

In my confusion, I think I see 3 or 4 different interpretations of states in regards to Model Checking.

States are steps in a Control-Flow Graph (CFG).
States are combinations of Boolean Variables or Atomic Propositions.
States are just identifiers or labels.
States are the values of the variables (any data variable, Boolean or not).

There is a problem with (1). Specifically, you may perform an action, and yet the value of all your atomic propositions stay the same. So it seems there is a distinction between "state as in a program step" and "state as in a set of atomic propositions". In scheduling/planning, I think this is how they conceive of states, as CFG nodes along with some Atomic Propositions.

There is a problem with (2) as well. You can create all kinds of combinations of Atomic Propositions, like even creating a Power Set of every number and combination. I wonder if these "objects" are actually called states, or if I am confusing something here. If they are states, then states are completely independent of the program CFG, though it might be correlated in some cases. Also in this case, states can be nested, because you can have states part of larger and larger sets.

My feeling about (3) is that this is what Finite State Automata and other automata typically use for state. But it seems like in some places Model Checking might be defining states as labels instead of more complex objects like (1) and (2) or even (4).

In reactive systems state is considered the "whole application state", meaning the valuations of the state variables. I don't think this is what Model Checking means when they talk about state.

So my question is, what exactly state is in Model Checking. Until today I have always imagined it as CFG nodes like in (1), in which case there is a relatively small number of them. But now I am starting to think they are more like (2), independent of CFG nodes. I can't tell yet. Program changing/running and state changing are things that almost always happen together. But I'm confused, thinking maybe the states in a state-transition graph / Kripke Structure are really just an abstract collection of Boolean Variables or Atomic Propositions. Please let me know if I am wrong.

My vote is on (4) from an intuition point of view.

I just started learning this recently so take this with a grain of salt but as mentioned by D.W. the set of states can be anything you want. It is an abstract concept. However, it is natural to think of states as being valuations of the variables in the system. For example, we may think of the current state of the solar system as the current values of all variables of interest to us, such as all positions and velocities of the 8 planets in it.

Seeing it this way has another advantage. If we take the atomic propositions to be formulas of the form $x = v$ where $x$ is a variable and $v$ is a value, then the labeling function is simply the identity function: $L(S) = S$, and an atomic proposition $P$ is true in state $S$ iff $P \in S$.

The fact that the state space becomes the power set of all n-tuples of valuations of variables is not really a downside. Many of these states would simply be unreachable in any practical Kripke structure. As for your concern about states being "nested", first of all note that $S_1 \subset S_2$ means that they are actually different states. Secondly, if $S_1 \subseteq S_2$, then you have the property that anything true in $S_1$ is also true in $S_2$!

In fact, as far as I have seen, this is the interpretation used in many of the practical uses of Kripke structures that I have seen, such as in model checking in the context of formal verification.


Algorithm Time complexity analysis for algorithm having two different time complexities I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to $N$ (set length) and $M$ (bits to represent the numbers). I'm having some trouble to figure out how to express its time complexity because I don't know how to handle next situation:

The asymptotic analysis establish that when $N$ is constant and $M$ grows the operations count grows at constant rate ($R1$) until it reaches a threshold that depended on the value of $N$, then the operations count does not grow anymore.

On the other hand when $M$ is constant and $N$ grows the operations count grows also at constant rate ($R2$) until it reaches a threshold that depends on the value of $M$, then, it continues growing but at a slower rate.

My understanding that the algorithm has two different time complexities depending on the values of $N$ and $M$.

Is there any way to integrate this behavior in a single Big-Oh expression?

And if not possible, how will be the right way to describe the time complexity for an algorithm with these properties?

No, you can't determine the asymptotic worst-case running time from these two graphs.

First, plotting empirical running times is not a reliable way to determine worst-case running time: How to fool the plot inspection heuristic?.  So, the approach of graphing performance on some testcases isn't a reliable way to get a "big-O" running time.

Second, knowing just these two graphs isn't enough to uniquely determine how it depends as a function of both $N,M$.  There are multiple possibilities for functions $f(N,M)$ that are consistent with both of these graphs.  For example, a two-variable function $f(N,M)$ is not uniquely determined by the one-variable functions $f(100,M)$ and $f(N,100)$.

Third, I strongly suspect that those two graphs don't tell the whole story.  For instance, you show us only a single graph for when $N$ is held constant and $M$ is varied.  But I suspect the shape of the graph (or the slope of the line) might depend on exactly which constant value of $N$ you choose: a very large value of $N$ might lead to a different graph than a small value of $N$.  This further highlights that we don't have enough information to uniquely infer the running time.

So what should you do?  Rather than plotting running times and treating the algorithm as a black box, it's probably to start by looking at the algorithm itself.  Look at the pseudocode of the algorithm and analyze its worst-case running time using standard techniques.  See, e.g., Is there a system behind the magic of algorithm analysis? and How to come up with the runtime of algorithms?.  This allows mathematically rigorous analysis that is provably correct and that can analyze the running time for all combinations of $N,M$.


can network layers communicate between each other? in a network architecture can two layers in different machines communicate between each other using some protocols, without having to go through the layers below, if yes how briefly ?

No. Ultimately, for two computers to communicate, something physical (such as a bunch of electrons or photons) must pass between them and that's the lowest possible level of the OSI model.

In general, though, you shouldn't view the layers too rigidly. They're a vocabulary for talking about networking, rather than a requirement for writing network protocols.


The PDA have to finish reading the input? I have PDA which has final state that accept 'c' char, and there isn't any cross to other state.
The input abca will accept, because there is 'c', or the PDA would stuck?

I think the PDA would stuck as to accept the input string "abcd", the complete input string needs to be read. But your PDA will work only till 'c' is read and get stuck when it finds another letter 'd', but has no transition state.


How to enumerate all Turing machines? Why is this true: “There are countably many Turing Machines”

In the top answer for this question a description of how to enumerate all Turing machines is given.

It all is clear except for one part: how do you know if a string is a valid encoding of a Turing machine? In step 3 the algorithm needs to check if a string is a valid encoding of a Turing machine. How is this done?

A turing machine has a representation as a string. more specifically, you write the transition function. to do this, simply think of it as one big table, having in each row two states a letter, and a head transition (L for left or R for right).

Now, encode every entry of the transition function table, and space between them with 3 zeroes (its like a "magic number" so we would know where entries start and end). every entry will contain two numbers - each number representing one state, another bit for the letter and another bit for the head transition (say 1 would be R and 0 is L).

between the two numbers and the other bits put 2 more zeroes, just so you would be able to distinguish between them.

Now, to enumerate on all of the turing machines, just enumerate on all strings and check if they are in the format described above


Marginalise edge weights on graph I have a directed acyclic graph with a score on each edge.  The score of a path is defined to be the sum of the scores on the edges along this path.  The probability of a path is the score of such a path divided by the sum of the scores of all paths.

I would like to compute the marginal probability of each edge; i.e., the probability that the edge is present in a path drawn randomly from the above probability distribution on paths.  Is there an efficient algorithm to do this?

I know that I could simply calculate the probability of each path through the graph and then for each edge sum the probabilities of the paths on which the edge occurs but this seems a very inefficient way of doing things. Is there some way to use dynamic programming to solve this issue?

Yes, this can be solved with dynamic programming.  In fact, it can be done in linear time.

I'll assume there is a single source $s$ and a single sink $t$ (if not, add $s$ and edges with score 0 from $s$ to each original source; and similarly for $t$).

Then, let $f(v)$ denote the sum of the scores of all paths from $s$ to $v$, and $f'(v)$ denote the number of such paths.   You can compute both of them using dynamic programming.  For instance,

$$f(v) = \sum_u f(u) + s(u,v)$$

where the sum is over all vertices $u$ such that $(u,v)$ is an edge in the graph, and where $s(u,v)$ denotes the score on the edge $(u,v)$.  If you topologically sort the graph, then you can fill in the $f(v)$ values using the above recurrence in linear time.  Similarly,

$$f'(v) = \sum_u f'(v)$$

which gives a way to fill in the $f'(v)$ values in linear time as well.

Let $g(v)$ denote the sum of the scores of all paths from $v$ to $t$, and $g'(v)$ the number of such paths.  You can fill in these values similarly.

Finally, you can compute the marginal probability of an edge $(u,v)$ as

$$\Pr[(u,v)] = {f(u) g(v)  +  s(u,v) f'(u) g'(v) \over f(t)}.$$

The numerator has the total score of all paths that go through $(u,v)$, and the denominator has the total score of all paths in the graph.


Static vs dynamic allocated arrays I am trying to learn CS fundamentals and I am confused by static vs dynamic allocated arrays.  My only programming experience is JavaScript and all online resources I am using refer to C language.

A dynamic allocated array is made when the application starts and it cannot be resized.  So how is this different from static allocated array, if to expand the array you have to make a new and bigger array and copy over the contents?

No, a dynamically allocated array is created when the program creates it, in the size the program wants to create it, and it exists until the point of time when the program destroys it.


Are there problems with complexity between $O(n^c/\log^b n)$ and $O(n^{c - \varepsilon})$? I am having an extremely tough time with this homework question, wondering if anyone could help me (for all you theory aficionados, this one's for you).

There is a language $L$ with the following property: There is a Turing machine that decides $L$ in time $O(n^{2013}/\log^{2012} n)$, but there is no Turing machine that decides $L$ in time $O(n^{2012.9})$. Is this statement TRUE or FALSE?

My notion/idea is to use this Corollary that stems from the Time Hierarchy Theorem: For any two real numbers $1 \le e_1 < e_2$, we have $\mathrm{TIME}(n^{e_1}) \subsetneq \mathrm{TIME}(n^{e_2})$. I think I am on the right track but I need some help with this proof.

The question is about upper bound (which is $O(n^{2013} / (\log n)^{2012})$) and lower bound (which is $O(n^{2012.9})$) – do they correspond to each other?

According to definitions of Big-O and Ω we have to find constants $c_1$, $c_2$, and $n_0$ such that for $n\geq n_0$ two following inequalities are true:

$$c_1 n^{2012.9} \leq T(n) \leq c_2 n^{2013} / (\log n)^{2012}.$$

If such constants exist, then the lower bound must be less than upper bound for sufficiently large $n$:

$$c_1 n^{2012.9} \leq c_2 n^{2013} / (\log n)^{2012}.$$

Let's simplify this a little:

$$c_1 (\log n)^{2012} \leq c_2 n^{0.1}.$$

Can we find $n_0$ such that this inequality is true when $n \geq n_0$? Yes, sure – the power function eventually wins over the logarithm function, so the answer is TRUE.


What are some complexity classes for neural networks? Turing machines and neural networks are equivalent in their expressive powers, but as models of computation they are different. Turing machines come pre-configured with their transition functions while the neural networks configure weights to build learnable computable functions using input data.

Is the class of problems efficiently solvable by a neural network equivalent to the class P or NP... or some normal complexity class or do they have their own complexity classes that are not equivalent to normal ones.

Basically, no one has proven anything useful about which tasks a neural networks are able to efficiently learn to solve.

What we can say is: they're not magic pixie dust.  They can't solve NP-complete problems in polynomial time, unless P = NP.

In practice, for most tasks that you'd find in a classical algorithms class, human-made algorithms vastly outperform neural networks.  The situations where neural networks are better tends to be tasks that don't admit a crisp problem statement or specification of the desired behavior.


Algorithm: Calculate every number in a given list using addition and numbers you've created I'm creating an algorithm to calculate every number in an array using only addition and numbers we've created - in the shortest amount of steps. That's confusing so here is an example:

input: [5, 11], used numbers (start with 1): [1]
1+1=2, used: [1, 2]
2+2=4, used: [1, 2, 4]
1+4=5, [1, 2, 4, 5]
5+5=10, [1, 2, 4, 5, 10]
10+1=11, [1, 2, 4, 5, 10, 11]

We have hit 5 and 11 so we are done in 5 steps. There are other ways to get [5, 11], eg. [1, 2, 3, 5, 6, 11]. They are the same amount of steps. Imagine we have input [5, 11, 20]. Now it matters which we choose above because [1, 2, 4, 5, 10, 11] only requires one more step, 10+10.

The input can be hundreds of numbers. Certainly I can't attempt every possibility. I was thinking about an "elegant" solution using prime factors. If my input is [16, 30, 36, 40], does it help me to think about this as [2*2*2*2, 2*3*5, 2*2*3*3, 2*2*2*5]? I'm not sure. I've also thought about using the differences of each input, eg. [16, 30, 36, 40] would give me [14, 6, 4, 20, 24, 10], but I'm not sure how to use that either.

Any thoughts?

You're looking for an algorithm to generate an addition chain that includes each of the specified numbers.  As Wikipedia explains, the problem is NP-complete in general.  However, there are approximation algorithms and heuristics.  Searching for algorithms for computing addition chains should give you some candidate methods.


Counting in Automata theory Is it possible to count in Automata theory?

I am begginer in Automata theory and I am trying to do some examples.

Currently I am working on a program that will recognise equal numbers of 0 and 1, but they are orderd in such manner that they are together, example:
$$
000111\rightarrow true \quad
0001111\rightarrow false \quad
00011 \rightarrow false \quad
010101\rightarrow false  \quad
$$
I am trying to figure out is there any possibility to count in Automation theory. If not can you please advise me how it would be possible to solve this assingment, because the only way for me is counting.

Thanks.

Well, it depends of the kind of automata you are using. Roughly speaking, finite automata can only count modulo $d$ for some fixed $d$: for instance, you can test whether a word contains an odd number of $0$ or whether its length is a multiple of $5$. For your problem, finite automata will not suffice and you need a more powerful model of automata, for instance a pushdown automaton.


Can the shortest simple cycle between two given nodes be found in polynomial time? Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, the problem is NP-complete if the two constraint were changed to arbitrary, but what if the number is given?

The problem isn't NP-hard, one way to solve it is to treat the graph as a flow network where each edge has capacity $1$ and cost $1$, and set $s$ as the source and $t$ as the sink, if you find a minimum-cost flow of $2$, you have two edge-disjoint paths from $s$ to $t$ (just finding a flow of 2 or more gives disjoint paths - this is basically Menger's Theorem - the min-cost part will lead to shortest cycles).

Of course what we really want is vertex disjoint paths, rather than edge disjoint. If we treat the input graph $G$ as a digraph $D$, replacing each edge $uv$ with two edges $(u,v)$ and $(v,u)$, we can create a new graph $D'$ by splitting each vertex $v$ into $v_{1}$ and $v_{2}$ with the edge $(v_{1},v_{2})$ with cost zero, and any edge $(u,w)$ in $D$ becomes $(u_{2},w_{1})$ in $D'$. Then edges disjoint paths in $D'$ correspond to vertex disjoint paths in $D$ (and hence $G$).

Now we only need to solve the min-cost part. Suurballe & Tarjan (Networks 14(2), pp. 325–336, 1984) give an algorithm to do this with running time $O(m\log_{1+m/n}n)$ where $m$ is number of edges and $n$ the number of vertices, which is somwhere between $O(n^{2})$ and $O(n\log n)$, depending on how dense the graph is.

This may not be the fastest though: Bjorklund, Husfeldt & Taslaman (published at SODA '12, the linked version is a preprint) give a randomised FPT algorithm for finding the shortest cycle that includes a set of $k$ specified vertices, but in the introduction they also mention a (deterministic) linear time algorithm for $k=3$, which suggests $k=2$ should be quicker than the older algorithms suggest too.

What is NP-hard is finding long cycles (the  extreme case is Hamiltonian Cycle).


Is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP? I was reading a paper and I came to the following :

"Since independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP (see [19]) for any fixed $\epsilon> 0$, the ..." where [19] is the following article : D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In STOC, pages 681–690, 2006.

My question: is it true that independent set is $Ω(n^{1−\epsilon})$-inapproximable unless P=NP? Because I cannot find this result in the cited article. However, I can find the results about max clique and chromatic number. What I am missing?

Yes, this is true.

To see this, notice that cliques and independent sets are complementary. That is, a set of vertices $S$ is independent precisely when $S$ forms a clique in the complement of the graph. Intuitively, this means that if you had an approximation algorithm for finding a maximum clique, you could use it to find a maximum independent set by executing it on the complement graph.


Number of instances of SAT (boolean satisfiability) problems of size N? I assume the size of an instance of the SAT problem is measured by its number of (Boolean) variables.  What is total number of instances of SAT problems of size N?

I guess that amounts to counting the number of "distinct" formulas that can be formed by N boolean variables, using a normal form such as CNF or DNF.

Update:  this question is partly answered for the 3SAT case:
https://cstheory.stackexchange.com/q/2168/15553

and the number of distinct clauses is:
$$ C = 2N \times 2(N-1) \times 2(N -2) / 3! = 4 N(N-1)(N-2)/3 $$

If you consider 3-Conjunctive Normal Form (3CNF) (every clause has exactly three literals) and you allow clauses with repeated variables, then it is easy to see that using $N$ variables the number of different 3SAT clauses is $(2N)^3$
($2N$ because every literal can appear unnegated or negated).

So the total number of distinct 3CNF formulas (without repeated clauses) is $2^{(2N)^3}$.

But be careful because the "size" of a 3CNF formula (e.g. considered as an input of a decision problem) is usually the size of its representation. For example, using alphabet $\Sigma = \{0,...,9,``,",-\}$
the 3CNF formula $(x_1\lor\bar{x}_2\lor x_3)\land (\lor x_2 \lor \bar{x}_3 \lor \bar{x}_4)$ can be represented with the string:

1,-2,3,2,-3,-4

and its length is 14.


Manipulating stack pointer in assembly I have written an assembly program to store digits in a stack. And to print the digits I have used
loop2:
mov ah,2
int 21h
sub cl,1
jnz loop2

But this would only print them in reverse order as the SP is pointing to the last element,
Now, I have a very simple yet very interesting question, I was very curious to know
If I were to print it in the same way it was entered, how would I do that? I could use another stack but it would be quite complicated.

A stack is a last-in-first-out structure. This causes the reverse order you experience. What you need is a first-in-first-out structure, i.e., a queue.
This way or another, the stack in x86 is just a region in the memory you can access directly. Instead of popping each digit, initialize BP to point at the bottom of your stack (the first digit), then print it, and then advance BP to the next digit (i.e., decrease BP since the stack grows towards lower addresses). At the end of the print loop, just clean the stack by popping everything out, or by changing SP directly.
MOV BP, SP    ; init BP to the first digit

... <push digits> , <init CX> ...

PrintLoop:
   MOV DX, [BP]
   MOV AH, 2
   INT 21h            ; print

   SUB BP, 2          ; assuming each digit is a word
   LOOP PrintLoop     ; Loop according to CX

MOV SP, <...>         ; restore stack / "pop" everything


how to express the performance of a policy in policy parameters Suppose a leauge of tic-tac-toe playing agents. As the league proceeds, the bad players are kicked out, and better players come in. The problem resides on how to at least approximate the better player.

One way to think of is an evolutionary approach. By random mutation possibly followed by crossovers, you may expect that slowly the players will converge to the optimum.

But I want something more deterministic. Assuming the policy function of each agent is differentiable, there are many methods to speed up the optimization. I will use the term policy as a function that takes the current board as input and ouputs the best move to play. Whatever method I choose, they need the performance as input. One obvious performance metric is the winrate, which usually works fine to approximate the performance itself, but it doesn't contain any parameter from the policy function. To optimize the policy to maximize the performance, things work best when the performance can be expressed in the parameters defining the policy, so that I can take the gradient of the performance with respect to the policy parameters, and update the policy following the gradient; that is, gradient ascent.

So back to the title, what is a good way to express the performance of a policy in policy parameters?

I suggest you study reinforcement learning, and possibly Q-learning.  They are aimed at dealing with this kind of situation.

The short answer is that we almost never have a way to give a closed-form formula that measures how good a policy is, as a function of the policy parameters.  Rather, we use simulations: we conduct a bunch of simulations using that policy, measure how well it performs in simulation, and use that our estimate of the quality of the policy.  Then we apply stochastic gradient descent or other optimization methods to find parameter values that maximize the quality of the policy.


Using Myhill-Nerode to prove a language is non-regular I'm trying to prove

L={w∈{0,1}∗:w contains more 00 substrings than 11 substrings}

is a non regular language using Myhill-Nerode theorem.

I'm a bit lost and not sure what to do. Thanks

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

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

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

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

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


What is the most efficient algorithm for creating a list of unique values from a list of pairs of value? Background

I have a list of 50 million $A-A_i$ pairs, where $i>1$, and $A$ and $A_i$ are some text. I need to extract the $A$ values from the list, so I get a new list of unique $A$ values.:

$$
\text{New List}= \{A, B, C, ...\}
$$

Here is a generic illustration of what the list of pairs looks like:

list of pairs = [['A', 'A1'],
                 ['A', 'A2'],
                 ['A', 'A3'],
                 ['B', 'B1'],
                 ['C', 'C1'],
                  ...

Here is some actual data:

`['394.NGR_c13430',
  '(3R)-hydroxymyristoyl-[acyl-carrier-protein] dehydratase'],`
`['394.NGR_c31790',
  '(Di)nucleoside polyphosphate hydrolase'],`
`['394.NGR_c00410',
  '(Dimethylallyl)adenosine tRNA methylthiotransferase MiaB'],`
`['394.NGR_c28950',
  '1,4-alpha-D-glucan:1,4-alpha-D-glucan 6-glucosyl-transferase'],`
`['394.NGR_c28950',
  '1,4-alpha-glucan branching enzyme GlgB'],`
`['394.NGR_c34010', '1-(5-phosphoribosyl)-5-[(5-ph']]`
`    9606.ENSP00000170630   1IAR`
`    9606.ENSP00000170630   1ITE`
`    9606.ENSP00000170630   287261`
`    9606.ENSP00000170630   287263`
`    9606.ENSP00000170630   287265`
`    9606.ENSP00000170630   287267`
`    9606.ENSP00000170630   287269`
`    9606.ENSP00000170630   287271`
`    9606.ENSP00000170630   3566`

(Sorry for the sloppy formatting, but I hope you get the idea.)

My Attempt

I'm doing:

    names := empty list
    for row in list:
    |   name := first element in row
    |   for name in names:
    |   |    if name not in names:
    |   |    |   append name to names

for line in proteins:
|    name := first element in "line"
|    for prot in prots:
|    |    if prot in name:
|    |    |    append alias to D_{prot}

Where D_{prot} is $D_{prot}$, a sublist in D containing the $A_{i's}$ of prot.

However, this approach is extremely slow. Even running this on only 10 million of the pairs takes more than half an hour. I'm only a statistician and not familiar with the intricacies of computer science or Python. Is there a better way of doing this?

Also...

I know for a fact that there are only 10 million unique values ($A$ values).

With $n$ = 50 million and $p$ = 10 million, I thought my algorithm was $O(np)$. Is it? Is this efficient?

Thank you

Question 1: How to solve the finding uniques problem
If your data is consistently formatted in this way:
[
  ['somestring', 'someotherstring'],
  ['anotherstring', 'anotherotherstring'],
]

And so on, you can actually just call dict directly on it and it will reduce all of the first items to keys, and keep the last of the second items as the values, and this runs extremely quickly. You can then retrieve the keys from the dictionary to get your unique list.
Here is an example:
a = [
  ['somestring', 'someotherstring'],
  ['anotherstring', 'anotherotherstring'],
]
b = dict(a)
print(list(b.keys()))

I tested this with a data set resembling the one you describe, with 50 million entries and 10 million unique values. On a single core in my laptop it took only about 15 seconds to run and used about 5.5 GB of memory. It actually took 10 times as long to make the data as it did to reduce it to a unique list. I have included the code I used to test below:
import random
import string
import time

def make_data(n, min_len, max_len, repeat_chance=0.0):
    dataset = []
    for i in range(n):
        if random.random() < repeat_chance and len(dataset) > 1:
            dataset.append([random.choice(dataset)[0], ''])
        else:
            key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
            dataset.append([key, ''])
    return dataset

def main():
    random.seed(42) # For reproducibility
    start_time = time.time()
    x = make_data(50000000, 10, 100, 0.8) # 50 M with 80% repeats for ~10 M unique
    mid_time = time.time()
    y = dict(x) # Reduce to unique keys
    end_time = time.time()

    print('Make data:  {0:.2f} s'.format(mid_time - start_time))
    print('Make dict:  {0:.2f} s'.format(end_time - mid_time))
    print('Total time: {0:.2f} s'.format(end_time - start_time))
    print('Total items:  ', len(x))
    print('Unique items: ', len(y))

if __name__ == '__main__':
    main()

And got the following output which is consistent with the specifications of 50 million entries and 10 million unique values
Make data:  169.61 s
Make dict:  15.47 s
Total time: 185.08 s
Total items:   50000000
Unique items:  10000776

Question 2: What is the complexity of that algorithm?
Is adding p unique values to a list and then searching the list for each new value from a list of n values to determine if its unique a O(np) problem?
Intuitively, I expect this to be a O(np2) problem. As n goes up, we must go through each one only once, so linear in n. As p goes up, we must go through more uniques to tell if the new value coming in is unique, so p2. This wiki page has almost exactly this situation, and shows how to derive the O(n2) complexity. But let's not let intuition guess for us, lets do the work.
Here is a plot of n with constant-ish p of 5000 and the time it takes to process it using your algorithm on the vertical axis.

Here is a plot of p with constant n of 1 million and the time it takes to process on the vertical axis.

These plots suggest that the list algorithm offers the complexity we expected of O(np2).
Bonus Question: How does the dict method compare to the list method?
Just for the intrigue, I also compared the dict method to your list algorithm and plotted them together. Blue is the list algorithm, and orange is the dict method.

Since the orange line is a little difficult to see, here is a rerun with only the dict method.

As you can see, the dict method maintains linear performance with respect to p, offering an overall performance of O(np) while the list algorithm offers the complexity we expected of O(np2). The dict method also outperformed the list algorithm at every test point.
If anyone is so inclined, here is the code used to generate that data.
import random
import string
import time
import matplotlib.pyplot as plot

def make_data(n, min_len, max_len, repeat_chance=0.0):
    dataset = []
    for i in range(n):
        if random.random() < repeat_chance and len(dataset) > 1:
            dataset.append([random.choice(dataset)[0], ''])
        else:
            key = ''.join(random.choices(string.printable, k=random.randint(min_len, max_len)))
            dataset.append([key, ''])
    return dataset

def get_uniques_listwise(dataset):
    uniqueset = []
    for datapoint in dataset:
        if not datapoint[0] in uniqueset:
            uniqueset.append(datapoint[0])
    return uniqueset

def get_uniques_dict(dataset):
    return list(dict(dataset).keys())

def makechart(testpoints, index, xlabel, ylabel, title, f0, f1=None):
    n_times0 = []
    n_times1 = []
    for testpoint in testpoints:
        dataset = make_data(testpoint[0], 10, 100, 1 - testpoint[1] / testpoint[0])
        start_time = time.time()
        f0(dataset)
        end_time = time.time()
        n_times0.append(end_time - start_time)
        if not f1 is None:
            start_time = time.time()
            f1(dataset)
            end_time = time.time()
            n_times1.append(end_time - start_time)

    plot.plot([x[index] for x in testpoints], n_times0)
    if not f1 is None:
        plot.plot([x[index] for x in testpoints], n_times1)
    plot.xlabel(xlabel)
    plot.ylabel(ylabel)
    plot.title(title)
    plot.show()

def main():
    random.seed(42) # For reproducibility
    n_p_testpoints_n = [
        [100000, 5000],
        [500000, 5000],
        [1000000, 5000],
        [2000000, 5000],
        [5000000, 5000],
        [7000000, 5000],
        [8000000, 5000],
        [9000000, 5000],
        [10000000, 5000]
    ]
    makechart(
        n_p_testpoints_n,
        0,
        'n',
        'time to find uniques',
        'varying n with near constant p=5000',
        get_uniques_listwise,
        get_uniques_dict
    )

    random.seed(42) # For reproducibility
    n_p_testpoints_p = [
        [1000000, 10000],
        [1000000, 15000],
        [1000000, 20000],
        [1000000, 25000],
        [1000000, 30000],
        [1000000, 35000],
        [1000000, 40000],
        [1000000, 45000],
        [1000000, 50000],
    ]
    makechart(
        n_p_testpoints_p,
        1,
        'p',
        'time to find uniques',
        'varying p with constant n=1000000',
        get_uniques_listwise,
        get_uniques_dict
    )

if __name__ == '__main__':
    main()


Algorithm for closest available resource My apologies if question is not in correct format. I don't post here often. I don't know what tags would be appropriate for this question, or even if this is an appropriate question.

Looking for algorithm for closest available resource.

n people P1-Pn, n taxis T1-Tn, are in a 2 dimensional coordinate system eg x,y

Determine Person Taxi pairs if each person walks to the closest taxi that will be available to them, and not taken by another person. Ties of two (or more) people to same taxi can go to the person of lower index. Ties of two (or more) taxis as closest taxi can go to taxi of lowest index.

Does this go by a common problem name? What algorithms exist?

As for what algorithms exist, I can think of 2 right off but I doubt they be considered efficient.
1. use recursion, eg find closest person taxi pair, remove both from available list, and run again.
2. enumerate (n squared) all possible P-T pairs into binary tree sorted by distance value, and then traverse binary tree starting with lowest value until each P has unique T.
3. or can someone offer better algorithms?
Thank you

I would call this problem as closest matching between two equal sets with priority.

Here is an $O(n\log n)$ algorithm, assuming the distance is the 2-dimensional Euclidean distance. It might work with the Manhattan distance as well; however, I have not double checked that.

Build a balanced 2-d tree for all taxis in $O(n\log n)$ time. Attach to each node an inventory number, the number of all points in the rectangle or half plane represented by that node, which can be done in an $O(n)$-time tree traversal.

Now iterate over $P_1, P_2, \cdots, P_n$ in that order. For each person $P$, do the following.

  Find all nearest taxis of $P$, using the inventory number and ignore the unavailable taxis, which takes (amortized) $O(\log n)$ time. Assign the taxi with the lowest index among them to $P$. Mark that taxi as unavailable. Subtract one from the inventory number attached to each node that contain $P$, which takes $O(\log n)$ time.


Is this a valid use of big-O notation? Suppose that $m=O(n^{c+1/2})$ for some real $c>0$ and $x=O(\sqrt{\log m})$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results.

Computation 1
\begin{align}
f(x)\leq \exp(-x^2/2)&=\exp(-O(\log m))\\
&=\exp(-O(\log O(n^{c+1/2})))\\
&=\exp(-O(\log n^{c+1/2}))\\
&\leq \exp(-K_1\log n^{c+1/2})))\\
&=n^{-O(1)}
\end{align}
where $K_1>0$ when $n$ is sufficiently large (i.e. there exists $K_1>0$, $n_0$ such that when $n\geq n_0$, $\exp(-O(\log n^{c+1/2}))\leq  \exp(-K_1\log n^{c+1/2})))$. The last quantity $n^{-O(1)}$ represents the set of polynomially-bounded functions (see accepted answer in this post).

Computation 2
$$
f(x)\frac{m}{n^{1/2}} \leq n^{-O(1)}\frac{m}{n^{1/2}}=\leq n^{-O(1)}\frac{m}{n^{c+1/2-c}}=O(1)??
$$

If these computations appear in a paper for me to review, I would like to ask the author to rewrite.

  $$\exp(-x^2/2)\leq \exp\left(-K_1\log n^{c+1/2\,}\right), \text{ where } K_1>0$$

This is wrong. The direction of inequality should be switched. For example, let $n\to\infty$ and $x$ be constant 1, the left hand side remains a constant while the right hand side goes to 0. This error means "Computation 2" is wrong from the start.

  The last quantity $n^{-O(1)}$ represents the set of polynomially-bounded functions.

Instead of $n^{-O(1)}\,$, $n^{O(1)}$ represents asymptotically the set of polynomially-bounded functions.


Solving Independent Set through Vertex Cover I have an Independent Set problem, in which I have to check if given graph has a IS of given size $k$. I've already written a Vertex Cover algorithm a while back and I hope I can reuse it here. Those algorithms are closely related, since if graph $G = (V, E)$ has IS of size $k$ iff it has VC of size $V - k$. So am I right that I can I just use my VC algorithm with $k' = V - k$?

I've read this and this question and after that I've started doubting that this is that simple.

It is that simple, those questions are talking about fixed parameter tractable algorithms w.r.t. the size $k$ of an independent set/vertex cover. Your algorithm will work just fine setting $k' = |V| - k$. Clearly, the new value $k'$ also affects the running time of your algorithm.


What problem is this? Largest sum produced by selecting one number at each index from n lists, with restrictions Suppose you have an $n\times m$ 2D array consisting of each $n$ rows of $m$ real numbers. What is the sequence of indexes $i_1,i_2...i_m$ such that $\sum_{j=1}^mA[i_j, j]$ is maximized, subject to the constraint that each run of a value in $i_1...i_m$ must be at least $r$ entries long?
A correct algorithm with time linear in $m$ seems possible with dynamic programming. It would be even nicer to know the name of the problem and some academic reference to a correct solution. This is a minor methodological step in an analysis I'm doing for an interpersonal communication research paper, so ideally I'd like to find a paper to cite. This smells very similar to the dynamic programming homework problems I did in undergrad, so I'd be surprised if there isn't work on it.
In practice, $m \approx 12000$, $n=3$, and $20 \leq r \leq 200$.

I believe this can be solved in $O(nm)$ time using dynamic programming:
$$\begin{align*}
B[i,k] &= A[i,k] + \dots + A[i,k+r-1] + C[i,r]\\
C[i,k] &= \max(A[i,k] + C[i,k+1], \max_{i'} B[i',k])
\end{align*}$$
Note that you can compute $A[i,k] + \dots + A[i,k+r-1]$ in $O(1)$ time as the difference of two prefix sums (assuming you have done a one-time precomputation to compute all prefix-sums).
The answer is then $\max_i B[i,1]$.  Computing it takes $O(nm)$ time, as there are $O(nm)$ entries to fill in, and each one takes $O(1)$ time to fill in, using the equations above.
Interpretation:

$B[i,k]$ is the maximum possible value of $\sum_{j=k}^m A[i_j,j]$ such that $i_k=i$ and $i_k,\dots,i_m$ satisfy the repetition rule

$C[i,k]$ is the maximum possible value of $\sum_{j=k}^m A[i_j,j]$ such that $i_k,\dots,i_m$ satisfy the repetition rule except that if $i_k=i$, the run starting at $i_k$ can be of any length (but all subsequent runs must be at least $r$ long).  In other words,
$$C[i,k] = \max_\ell A[i,k] + \dots + A[i,k+\ell-1] + \max_{i'} B[i',k+\ell]$$

Generally, this is not the kind of thing I would expect to find papers about.  I would expect to see a one-sentence "can be solved by dynamic programming", possibly with an explanation of the max-trick above to reduce the running time from $O(nmr)$ to $O(nm)$, but not an entire paper about it.  So I would not bet on such a paper existing.  But I could be wrong.  It's certainly possible there could be such a paper.  I would not know how to go about looking for it.


Sifting algorithm for group generated by a set On page 38 of  "Lecture Notes in Computer Science" by Christoph M. Hoffmann, there is an algorithm (ALGORITHM 2).

I have some confusions.

Why it is written that an entry $M_{i,j}, j < i$, cannot be referenced? what is the meaning  of "reference" here?

Thanks.

One possible explanation is that it is indicating that you should never try to read or use any matrix element $M_{i,j}$ where $i<j$.  "Referenced" might be talking about "de-referencing" a pointer, i.e., reading a memory cell, i.e., reading an entry of the matrix.  Perhaps the text is indicating that the matrix entries $M_{i,j}$ are only defined for $i \ge j$.

I suggest you read the text with this possible perspective in mind and see if it seems consistent with the surrounding context.


Self loops in max flow problem So, there can be different types of edges in a directed graph while solving the max flow problem. There can be reverse edges, multiple edges and self loops.

What is the significance of self loops in it?

How is it related to flow in the graph?

Let there be a graph like this 1->2->3 and 2 has a self loop. So, can I interpret it like this-

1->2a--2b->3 ? where -- denotes an edge from 2a->2b and an edge from 2b->2a.

So, How would I represent this in a graph using adjacency list?

for the max flow problem you should remove the self loops and solve it. self loops don't effect on final solution because when there exists a loop on a vertex, it means a flow from the vertex (with an arbitrary capacity) goes on pipe that connect to itself, it means the flow doesn't waste, it just return to the vertex. it's like you connect a water hose from a tank to itself. you don't limit the input flow to the tank or output flow from it. so you can ignore self loops and solve the problem.


Complexity of Solving a System of Polynomial Equations It can be easily seen that solving systems of polynomial (i.e. not necessarily linear) equations is NP-Hard via reduction from SAT. Furthermore, because the existential theory of the reals is decidable in PSPACE, solving systems of polynomial equations is as well. What else is known about the complexity of this problem? For example, I have been unable to determine if it is known to be $\exists R$-Complete, or PSPACE-Complete.

Solving systems of polynomial equations over the reals is $\exists \mathbb R$-complete by definition, and it is a major open problem whether this complexity class equals PSPACE. See this.


Max-Flow: Detect if a given edge is found in some Min-Cut Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$.
Another question is, how do I decide whether if $e$ is the lightest edge of at least one minimal cut?

I've thought about running Ford-Fulkerson algorithm, and then increasing / decreasing the capacity of the given edge and see what happens, but I haven't came up with something that might help me solve the problem.

I'd be grateful if anyone could point me to the solution, thanks in advance.

Here is a solution for the first question: Suppose $w(e)$ is the weight of $e$, calculate min-cut value for $G$, suppose is $C$. Then we remove $e$ from $G$ to make $G'$; again we calculate the min-cut value for $G'$, suppose is $C'$, if $C-C'\ge w(e)$, then this concludes that $e$, participating in at least one min-cut (that you already know it), otherwise $e$ does not belong to any min-cut.

Link to SO answer.