Parity check and magnitude comparison in Residue Number Systems Let

$\{m_1,...,m_t\}$ be a set of relatively coprime integers
$M=\prod_{i=1}^tm_i$ the range of this system
$X$ an integer such that $X \in [0,M-1]$

This forms a Residue Number System and every integer $X$ can be uniquely represented in RNS format as
$(x_1,\dots,x_t)$, where $x_i = X\bmod m_i, \forall i\in[0,t]$.

One can add,subtract,multiply efficiently in RNS by adding,subtracting,multiplying modulo $m_i$ in parallel the corresponding RNS digits as in

$X\otimes Y=(x_1,\dots,x_t)\otimes(y_1,\cdots,y_t)=(x_1 \otimes y_1,\cdots,x_t \otimes y_t)$, where $\otimes=(+,-,\times) \bmod m_i$

There are various operations though that are not efficient in RNS, like parity check or magnitude comparison. I've encountered an interesting algorithm for parity check directly in RNS and I would like to take advantage of it to perform sign detection (in fact checking whether the result of $X-Y$ is negative or not). The idea comes from another topic where I quote exactly the part I don't understand:

"...one can compute $X-Y$ and if it underflows, the parity will be unexpected. That is, if $p(X)=X \bmod 2$,   $p(X)\in\{0,1\}$ is the parity function, then $p(X−Y) \equiv p(X)+p(Y) \bmod 2$. However, if it underflows, it will wrap around to $M−1$. Therefore if the parity is off after $X−Y$, you know that $Y>X$".

What is meant by "parity if off?" How can I check an underflow by just checking the parities?

The "parity check" of a number $X$ is 0 or 1 according to whether $X$ is even or odd.  In other words, the parity of $X$ is $X \bmod 2$.  We are assuming that you have a way to compute the parity of $X$, from the RNS representation of $X$.  Let $p(X)$ denote the parity of $X$, i.e., $p(X) = X \bmod 2$.

Now let's suppose $X,Y$ are integers in $[0,M-1]$ that we have stored in RNS representation, and let's look at what happens when we subtract the RNS representations.  If $X$ is represented as $(x_1,\dots,x_t)$ and $Y$ is represented as $(y_1,\dots,y_t)$, the result of the subtraction operation will be the RNS representation $(z_1,\dots,z_t)$ where $z_i = x_i-y_i \bmod m_i$.

What number $Z$ is $(z_1,\dots,z_t)$ the representation of?  Well, if $X\ge Y$, then $Z$ will be $X-Y$.  But -- and here is the key point -- if $X<Y$, then $Z$ will not be $X-Y$, as $X-Y$ is negative and RNS can only represent numbers in the range $[0,M-1]$.  Instead, what will happen is that we'll have $Z \equiv X-Y \pmod M$.  Therefore, if $X<Y$, we'll have $Z = X-Y+M$... which is not the same as $X-Y$.

If $X\ge Y$, then $X-Y \ge 0$ and we say that the subtraction $X-Y$ doesn't underflow; in this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ modulo 2.  In other words, if $X \ge Y$, we will have $Z=X-Y$ and therefore using the properties of modulo-2 arithmetic we have

$$p(Z) = p(X-Y) \equiv X-Y \equiv p(X)-p(Y) \pmod 2.$$

In contrast, if $X < Y$, then $X-Y < 0$ and we say that the subtraction $X-Y$ underflows.  In this case, $p(Z)$ will be $p(X)$ minus $p(Y)$ plus 1 modulo 2.  In other words, if $X<Y$, we will have $Z=X-Y+M$ and therefore

$$p(Z) = p(X-Y+M) \equiv X-Y+M \equiv p(X)-p(Y)+1 \pmod 2.$$

Here I have used the fact that $M$ will always be odd, so $p(M)=1$.

This gives you a way to check whether $X\le Y$, given RNS representations for $X,Y$: you subtract them to get a RNS representation of some integer $Z$, and then test whether $p(Z) \stackrel{?}{\equiv} p(X)-p(Y) \pmod 2$.

The key observation is that "subtraction" of RNS representations is not actually computing the subtraction (of integers).   Rather, it is computing the subtraction modulo $M$.  If the result of the subtraction is in the range $[0,M-1]$, that's equivalent to subtraction in the integers.  But if subtraction underflows, it's different.

This might look mysterious, but it's not as unfamiliar as it might feel.  If you use twos-complement arithmetic on 32-bit integers, that is basically doing modulo $2^{32}$ arithmetic: addition of 32-bit ints is not actually addition (of integers), but addition modulo $2^{32}$.  In other words, with twos-complement addition of 32-bit integers, the results of arithmetic operations "wrap around" modulo $2^{32}$.  RNS is just like that, except that it "wraps around" modulo $M$ instead of modulo $2^{32}$.

"parity is off" means "parity is wrong", i.e., the parity doesn't match what you'd expect to get, if subtraction of RNS representations behaved like subtraction of integers.


O(n) sorting array by value - get indexes I am in search of a linear-time sorting algorithm that is capable of returning an array B of indices A, sorted on the value of the corresponding element of A.

For example:

Input = [2, 6, 8, 9, 1, 7, 0]
Output = [6, 4, 0, 1, 5, 2, 3]

Things I have tried:

Storing the index and value in one number, using something like this:

long number = value << 16 | index;

And then applying Countingsort. This however did not work since the JVM couldn't handle an array of ~ 2 million elements. (= the highest "number" value).

The logical solution to that problem was put everything in a map, but I was unsure whether it would still be linear..

Every problem can be solved with yet another indirection:

First create B as an array of self-indexes - i.e set B[i] = i for all i.  Next create a 'comparator' object around A, which compares integers i and j by actually comparing A[i] with A[j].  Now sort B using this comparator.


Integer Problem Solving with two boolean selection variables I am trying to solve a two dimensional combinatorial problem.
Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible variations for each of these elements {1,2}. I have an objective function to maximize and i have some constraints. Based on these i have to make above selections. Can anyone please tell me if there is any optimization algorithm already available which serves my purpose. In reality i have a huge input space, so any existing algorithm is prefered

Sure, try integer linear programming.  Let $x_{RA1}$ be a zero-or-one variable that is 1 if you select RA1, or 0 if you don't.  Then each of your constraints can be expressed as linear inequalities with these variables.  You can then try applying an off-the-shelf ILP solver.

There are a bunch of other questions on this site with further examples of using ILP to solve combinatorial problems (e.g., Express boolean logic operations in zero-one integer linear programming (ILP)), so feel free to look around.


What does $O(\alpha(n))$ amortized time mean? DELETE(S, i): Delete integer $i$ from the set $S$. if $i \notin S$, there is no effect.

from a set of consectutive integers like $S = \{1,2,3,5,6\}$

Provide a data structure and an algorithm for DELETE that takes $O(\alpha(n))$ amortized time

not sure what what does $O(\alpha(n))$ amortized time mean?

I was thinking AVL trees ? I know the worst case is $O(\log n)$ for that. Not sure what $O(\alpha(n))$ amortized time means though.

$\alpha$ indicates the Inverse Ackermann Function: $\alpha(n)$ is the number such that $A(\alpha(n), \alpha(n)) = n$.

In practice, $\alpha(n) \lt 5$ for any input less than about $^72$. So $O(\alpha(n))$ is basically $O(1)$. The difference only matters in theory, never really in practice. You'll find $O(\alpha(n))$ mostly when working with disjoint sets, which are pretty much the fastest data structures you'll ever use.

EDIT: $^nb$ indicates "tetration", that is, iterated exponents. It grows ridiculously quickly: $O(^n2)$ is worse than $O(n!)$.


If $A,B$ are r.e. and $A\cup B,A \cap B$ are recursive, then so are $A,B$ Let be $A, B \subset \mathbb{N}$ are recursively enumerable, $A\cup B$ and $A \cap B$ recursive. I want to show that $A$ and $B$ are recursive.

By negation theorem $X \subset \mathbb{N}$ is recursive iff $X$ and $X^c$ are recursively enumerable.

How do I complete the proof using that?

The basic observation is
$$
\begin{align*}
A^c &= (A^c \cap B^c) \cup (A^c \cap B) \\ &=
(A \cup B)^c \cup (B \cap (A^c \cup B^c)) \\ &=
(A \cup B)^c \cup (B \cap (A \cap B)^c).
\end{align*}
$$
Using this you can recursively enumerate $A^c$. I'll let you figure out how.


Question regarding Cook-Levin theorem proof I know a key part of the Cook-Levin theorem proof (as presented in the book by Sipser) is that given two rows of configurations, if the upper row is a valid configuration of a nondeterministic Turing machine $N$, and every 2×3 window is consistent with $N$, then the second row is either identical with the upper row or follows from it by a transition of $N$.

Would this still remain true if we were to replace the 2x3 window with a 2x2 window?

No, it would not. The reason is that the encoding of configurations might change in 3 consecutive places with a single transition. Specifically, this happens with transitions where the head moves to the left.

For example, consider the configuration $aabqcaa$, which means that the tape contains $aabcaa$ and the head is on $c$. Now, assume that we have the transition $\delta(q,c)=\{(s,d,L)\}$. So the $c$ should be replaced with $d$, the head should move left, and the state should change to $s$. Thus, the new configuration is $aasbdaa$. You can see that the change is in 3 consecutive places.

Had you only tracked changes is 2x2 windows, you should have allowed (for example) $qc$ to turn to $bd$, meaning that you allow the head to just "disappear".


Using base 80 for compressing files I want to compress file size through making my own numbering system which is 80-based number, I do really want to know whether this even possible ? I learnt that Hexadecimal uses symbols like A, B, C, D, E, F to represent 10,11,12,13,14,15 -- and that's what i want to do to my own numbering system but in a bigger scale . Please correct me if i'm missing something .

Is it possible ?

While you will need fewer 80-based numbers than 2-based numbers (bits) to encode the same file, the only way to store these 80-based numbers on a computer is to encode them as bits. So you do not gain anything.

In fact you actually lose space, since 80 is not a power of 2: You will need 7 bits for each 80-based number, but in these 7 bits you could instead encoed 128 different states, if you used them directly.


Prove correctness of iterative LCM algorithm I have been trying to prove the following algorithm, without success.

Here is the C-Style pseudocode:

//j,k >= 0
int get_lcm(int j, int k){
    int c = j;
    int d = k;
    while(c != d){
        if(c < d){
            c += j;
        } else {
            d += k;
        }
    }
    return c;
}

I tried to find the loop invariant, which ended up being something like:
$$
\begin{aligned}
&c\le\text{LCM}(j,k) \wedge d\le\text{LCM}(j,k) \wedge c=aj \wedge d =bk\\
&(a,b \in N)
\end{aligned}
$$
I'm not sure how to proceed from here. I understand intuitively why the algorithm works, but I'm having trouble putting out an actual formal proof of it.

I need to come up with an invariant such that $c=d=LCM(j,k)$ when $c=d$. I'm having trouble showing how $c, d \le LCM(j,k)$ after one iteration.

Can anybody please help me? Thank you for your time.

Assume j, k > 0.

You have your loop invariant. Every iteration, one of c or d gets larger. They cannot forever stay ≤ LCM (i, j), therefore the loop must finish.

Because c and d are multiples of i, j, they cannot change directly from being < LCM (i, j) to > LCM (i, j), instead there must be a step for each of c and d where it is equal.

If both are = LCM (i, j) then c = d and the algorithm exits. If one is = LCM (i, j) then the other one is smaller and gets increased.


For which level of PH is $\operatorname{VALID}$ complete I have the decision problem $\operatorname{VALID}$ which is the set of all valid propositional formulas (tautologies), I know that $$\overline{\operatorname{SAT}}\equiv_m^p \operatorname{VALID}.$$
This can easily be seen by changing instances of each problem into their logical negation, then a formula is a tautology iff its negation is not satisfiable.

My question is now, for which level of the polynomial time hierarchy PH is $\operatorname{VALID}$ complete. Here a quick definition of PH

$$  \Sigma_0 = \Pi_0=\operatorname{P},\quad \Sigma_{n+1} = \operatorname{NP}(\Sigma_n),\quad  \Pi_{n+1} = \operatorname{co}-\Sigma_{n+1},\quad \Delta_{n+1} =  \operatorname{P}(\Sigma_{n}).$$

I made the following observations: $\overline{\operatorname{SAT}}\in \operatorname{co}-\operatorname{NP}$, so that by the reduction given earlier we have that $\operatorname{VALID}  \in \operatorname{P}(\operatorname{co}-\operatorname{NP})= \operatorname{P}(\operatorname{NP}) = \Delta_2$. So my quess would be that the first level of PH for which $\operatorname{VALID}$ is complete is $\Delta_2$.

If $\overline{\operatorname{SAT}}$ is hard for $\operatorname{co}-\operatorname{NP}$ then I think the result follows, but I cannot seem to corroborate this with solid arguments.

Also, the reduction given seems so simple ($\phi \mapsto \lnot \phi$) that it seems that the class $\operatorname{P}(\operatorname{co}-\operatorname{NP})$ might be a bit overkill.

I would be grateful for any shared insights into this problem.

Just like SAT is NP-complete, $\overline{SAT}$ is coNP-complete. More generally, if $L$ is $\Sigma_k$-complete then $\overline{L}$ is $\Pi_k$-complete (and vice versa). You can prove this using the definitions.


Why do operating systems freeze? I am currently writing from a computer on which a VM has just frozen due to exhausted RAM. I am obviously no expert in the field of operating systems but i know that they implement certain memory management methods so why can't my OS handle my alt-f4 request to kill the troublesome process in a reasonable time?

Why can't other processess still run normally?

Shouldn't operating system swap between active tasks so that my keyboard input reaches said process?

Operating system in itself should be of top priority with handling user input isn't that right?

Therefore my question remains: how come, despite all the round-robin and/or other scheduling mechanics my OS still freezes?

Thank You for all the answers.
Cheers.

A "system freeze" is normally due to the system running out of some resource and spending it's limited resources left trying frantically to fix up the mess. I.e., too much CPU load, has no processing power left for the user. Memory overload, keeps trying to free memory and gets nowhere, no time left for the user (and no memory to load programs).

It might also be a deadlock (some tasks inside the system are holding resources others require, and are waiting for still others to be released, but that will never happen as everybody is waiting for somebody else's resources).


Is there an algorithm to find all vertices that are inside of a shape? In computational geometry, is there any algorithm to find all vertices that are inside of a shape?

All vertices of graph has $x$- and $y$-coordinates
Shape is a set of points with $x$- and $y$-coordinates (unicyclic graph)
I need a fast algorithm. I am trying to avoid iterating over all vertices

Example:

It seems to me that the problem is not about graph theory, but computational geometry. Phrased slightly differently, your input is a set of two-dimensional points $P$ (corresponding to the coordinates of the vertices of some graph drawing) and a polygon $Q$. The task to determine a subset $P'$ of the points $P$ that are contained within $Q$.

One possible algorithm is to iterate over each point $p$ in $P$, and check whether $p$ is inside $Q$. This classic point in polygon problem has many simple and efficient algorithms.


Binarization of Constraints I am trying to solve a Constraint Satisfaction Problem that involves lots of n-ary constraints. But the solver I have implemented only works with algorithms for binary constraints.

I've been reading into the topic of the biniraztion of constraints (http://ktiml.mff.cuni.cz/~bartak/constraints/binary.html) but I am still not entirely sure how that would work. I thought if someone could help me convert one of the real-world constraints I am dealing with, this could help my understanding.

More specifically:

I have a set of variables: {C1, C2, C3, P}.

Each variable has a domain {0, 1}.

And a constraint: (C1 → (¬C2 ∧ ¬C3 ∧ P)) ∨ (C2 → (¬C1 ∧ ¬C3 ∧ P)) ∨ (C3 → (¬C1 ∧ ¬C2 ∧ P))

How can I convert this constraint into multiple binary constraints?

Introduce a new variable $Q$, whose domain is $\{0000,0001,0010,\dots,1111\}$.  It represents the value of $C1,C2,C3,P$. For instance, if $Q=0001$, that means that $C1=0$, $C2=0$, $C3=1$, $P=0$.   Then, you add a constraint that the first bit of $Q$ is equal to $C1$ (that's a binary constraint), a constraint that the second bit of $Q$ is equal to $C2$ (another binary constraint), and so on.


Understanding Decision Stump in Adaboost I am trying to understand how Adaboost works, and many of the tutorials online involve the use of a decision tree stump. For example, http://www.cc.gatech.edu/~thad/6601-gradAI-fall2013/boosting.pdf or http://www.fromdev.com/2012/04/creating-weak-learner-with-decision.html. However, I am confused on how the plot is actually generated. Say I have the following training set:

               Event 1     Event 2     Event 3
Classifier 1      -1          1          1
Classifier 2      1           -1         1
Classifier 3      1           1          -1

How should I generate a decision stump for this?

I wonder if you what decision stump is.

Decision stump is simply a decision tree with only one node. It is usually considered as the weak classifier in boosting algorithms since due to its simplicity it will not overfit.

In your question it is not clear what is even 1 .. 3. Anyhow, the classifiers can be : decision stump1, decision stump2 and decision stump3.


if $f(n)$ is defined in the domain [0,1] then what $f(n) = O(1/n)$ actually means? We know that $f(n) \in O(g(n))$ notation means shortly, that $f(n) \leq cg(n)$ for $n>n_o$ where n and c are some positive constants. And actually it gives the behavior of $f$ as $n$ goes to infinity.

But in the case $f(n) \in O(\frac{1}{n})$ where n is at most 1, shouldn't be more intuitive to say that the behavior of $f$ as $n$ goes to zero (and not to infinity) is $\frac{1}{n}$?

For example if $f$ gives the space consumption of an algorithm, then $f \in O(\frac{1}{n^2})$ is a lot better from $f \in O(\frac{1}{n})$ if we allow n>1. But if for any reason algorithm is restricted in the range $n \in [0,1]$ then we would like $f$ resembles $\frac{1}{n}$ and not $\frac{1}{n^2}$.

To make things even weirder suppose that $f(n) \leq \frac{1}{n}+\frac{1}{n^2}$. For n>1 the dominant term is the $\frac{1}{n}$ and someone could easily say that $f(n) \in O(1/n)$.
But if we restrict $n$ to be in $[0,1]$, the dominant term is the $\frac{1}{n^2}$. In that case is it right to say $f\in O(\frac{1}{n^2})$?

In this context it is clear that big O is taken as $n\to0$, rather than $n\to\infty$ as is more usual for us. For a function $f(x)$ defined on $(0,1)$, we say that $f(x) = O(1/x)$ if there exists a constant $C>0$ such that $f(x) < C/x$ (or, depending on the exact definition, $|f(x)| < C/x$.

This definition is by and large equivalent to the more usual definition which states that $f(x) = O(1/x)$ if there exist two constants $x_0 \in (0,1)$ and $C>0$ such that $f(x) < C/x$ for all $x \leq x_0$.

If you are confused, note that $f(x) = O(1/x)$ under these definitions iff $g(n) = O(n)$ under the usual definition, where $g(n) = f(1/n)$.

For $n$ in this range, we usually use symbols like $\epsilon$ or $\delta$ to emphasize that we are taking the asymptotics as the variable tends to 0 rather than as the variable tends to infinity.


Sqrt(x) function implementation; what is $(i^2 \leq x) \land ((i + 1)^2 > x)$ checking? Recently I was working on a LeetCode question

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only
the integer part of the result is returned.

Example 1:

Input: 4
Output: 2
Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since
             the decimal part is truncated, 2 is returned.

Here is a solution that I really like and understand, except for one line. It is using binary search to get to the solution:

int mySqrt(int x) {
    if (x == 0) return x;
    int left = 1, right = INT_MAX, mid;
    while(left < right) {
        mid = left + (right - left)/2;
        if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {
            return mid;
        }
        if (mid < x/mid) {
            left = mid + 1;
        } else { // mid > x/mid
            right = mid;
        }
    }
    return right;
}

The conceptual question is: why is it true that given a particular number, say $i$, $$(i^2 \leq x) \land ((i + 1)^2 > x)$$ returns whether or not $i$ is the truncated integer representation of the square root of $x$? (The code block above returns on the identical condition, but inequality is rearranged to avoid integer overflow)

I'll put the two inequalities together, for readability: $i^2 \leq x < (i+1)^2$.

Taking the positive square of a positive number is a monotone function. Hence,
$$i^2 \leq x < (i+1)^2 \implies i \leq |\sqrt{x}| < i +1$$

Then, the interger part of $|\sqrt{x}|$ is obviously $i$.


find a regular expression and FA that each define $L_1 \cap L_2$ I am trying to find a regular expression and finite automaton that each define $L_1 \cap L_2$, where $L_1 = (ab^*)^*$ and $L_2 = b(a+b)^*$.

How would I start doing this problem?

So I would draw a FA and when I draw it I would have a complement meaning take anywhere you have a plus, get rid of it and anywhere you didn't have a plus add one in. Am I on the right track?

Hint: Every non-empty string in $L_1$ starts with $a$. Every string in $L_2$ starts with $b$.


How does the processor find kernel code after an interrupt? When an interrupt occurs, the processor preempts the current process and calls kernel code to handle the interrupt. How does the processor know where to enter the kernel?

I understand that there are interrupt handlers which can be installed for each interrupt line. But since the processor only executes 'hardwired logic', there has to exist some predefined place that points to either an interrupt handler itself, or some code that executes before the handler (since there can be multiple handlers for one interrupt line, I assume the latter).

On startup, the kernel will initialize an interrupt vector table (called an interrupt descriptor table or IDT on x86) that points to an interrupt handler for each line.

Before the 80286, the IDT was always stored at a fixed address; starting with the 80286, the IDT is loaded using the LIDT instruction.

Interrupt vector tables point to a single handler per interrupt line; that being said, a kernel could choose to, for example, provide an interrupt handler that runs several other interrupt routines, or provide a single handler that covers some or all interrupts. Linux does  these things by providing a generic interrupt handler that determines which interrupt line was called and finds the appropriate downstream handler to call.


Input that causes an operation on a binomial heap to run in $\Omega(\log n)$ time? I was studying binomial heaps and its time analysis. Are there any inputs that cause DELETE-MIN, DECREASE-KEY, and DELETE to run in $\Omega(\log n)$ time for a binomial heap rather than $O(\log n)$?

This paper shows that for each priority queue implementation satisfying some technical condition (which holds for binomial heaps) there is a sequence of operations consisting of $n$ INSERTs, $n$ DELETEs and $n$ FIND-MINs that takes time $\Omega(n\log n)$. Since INSERTs are amortized $O(1)$ in binomial heaps, the DELETEs and FIND-MINs together must take time $\Omega(n\log n)$. Unfortunately, in the construction the INSERTs are interspersed between the other operations.

This is of course overkill for the case of binomial heaps.In the implementation in which FIND-MIN is implemented by comparing the roots of all trees. If we INSERT $2^m-1$ elements then we will have $m = \log(n+1)$ trees, and so FIND-MIN will take time $\Omega(\log n)$. In other implementations, it shouldn't be hard to concoct examples in which some MERGE operation (used inside all the others) takes time $\Omega(\log n)$.

You might be worried that even though these examples show that some operations could require logarithmic time, the amortized complexity is still better. You'll have to work harder, but after some though you should be able to come up with a sequence of $n$ INSERTs and DELETEs which takes amortized time $\Omega(\log n)$.


How do we know $\neg \neg LEM$ isn't provable in MLTT? I've been trying (fruitlessly) to prove something which I now know is not provable. Take the following definitions:
$$LEM \equiv \prod_{A : Type} \neg A \vee A$$
$$DNE \equiv \prod_{A : Type} \neg \neg A \to A$$
$$C(x) \equiv DNE \to x$$
I wanted to prove $\prod_{A : Type} C(A) \to \neg \neg A$. In trying to prove it the key thing to prove seemed to be $\neg \neg DNE$. I couldn't figure out how to prove this however. I thought it must be provabale however. Note that the above would be logically equivalent (implication goes both ways) to $\neg \neg DNE$ because the formula trivially implies it.

But this simple formula proved tricky. It feels like $\neg \neg DNE$ should hold because $DNE$ is consistent with MLTT. At least I had it in my mind that it already held but I couldn't seem to find a prove of it. Finally I started searching. I knew that $\neg \neg LEM$ was equivalent and found this: https://ncatlab.org/nlab/show/excluded+middle#DoubleNegatedPEM

This states that $\neg \neg LEM$ is not provable. This is the same as saying that $\neg LEM$ is consistent, at least in MLTT and other such theories. I'm certainly aware that there exist statements for which both the statement and its negation are equivalent but I hadn't realized that $LEM$ and $DNE$ were examples of this in MLTT. I'm kind of baffled that $\neg \neg \neg A \to \neg A$ holds but $\neg DNE$ is still consistent. That's a subtle point about quantifier placement that I must of missed last time I thought about this sort of thing.

Normally in logic when we want to show that something isn't provable we either show that a property that is preserved by all the inference rules (and holds for all axioms) is false for the given statement or we directly find a model for the logic and show that the given statement is false in the model. The only models I know for constructive logics are fairly complicated. For propositional logic we have Heyting algebra but the quantifier here leaves us no hope of using that. I vaguely recall that it is possible to extend these algebras to the quantifier case by doing something like taking the least upper bound or greatest lower bound of a set of instances of the algebra generated by substituting constants in the set being quantified over into the formula. I don't remember exactly how this works nor am I really clear that I could extend a result from first order constrictive logic (the logic of constructive set theory).

How do we know this? Do we have a simple enough model that would explain this? Do we just know from trying to prove it that we get stuck? After trying to prove it myself I feel intuitively that we'll always get stuck and I can explain it more or less as "you have a very limited number of ways to dig down and after digging down, you get stuck really quickly" but that's quite informal. Is there a meaty formal explanation of why this isn't provable?

The task here is indeed to find a model of MLTT in which $\neg LEM$ holds (and so $\neg\neg\neg LEM$ holds as well). Realizability models have this feature, for instance; see also this. Here, MLTT functions are interpreted with codes of computable recursive functions, so the usual uncomputable functions, e.g. halting oracles, cause $LEM$ to fail.

If you define $LEM$ as ranging over all types, and not just types which are propositional (i.e. have at most one inhabitant up to propositional equality), then it is also the case that $LEM$ is inconsistent with the univalence axiom of homotopy type theory, so this version of $LEM$ is also refuted by any model which can interpret the univalence axiom. Such are the simplicial set and cubical set models.

$LEM$ is also inconsistent with parametricity, so models validating parametricity also refute $LEM$. I think formally these are considerably simpler than univalent or realizability models; see for example the reflexive graph model. Intuitively, this works by noticing that MLTT does not allow inspecting the structure of types, so any function with type $\prod_{A : Type} A \rightarrow A$ must be the identity function. However, $LEM$ allows one to branch on whether two types are equal, allowing a function with the above type which is not the identity function on all types, e.g. negates Boolean inputs.


How did the word "production" end up being a synonym with the word "rule" in the context of Computer Science? I am studying formal languages and production bases systems (rule-bases systems) and I am a little confused about why do these two word "production" and "rule" mean the same thing in so many context in Computer Science.

In English Language they do not seem to mean the same thing. I am not a native English speaker but I know that a rule refers to something that one should/should not do when talking about people or something that if repeated for many times will give the same result and we say that it works by some rules (the way it works defined by some protocol/procedures that are the same every time).

Production refers to something completely different... the phase of some physical goods or software that are currently being made/produced. THe act of making something either physical or some piece of art, some writing, some drawing, something that is made with physical or mental capacities of someone. We say that the specific thing is produced.

However in Computer science these words that represent completely different things in English mean the same thing in CS. How did this terms ended up being similar in CS.

Is there some sort of etymological dictionary for computer science. A dictionary that tells us how the terms in computer science ended up to be ?

BTW: Interesting fact: neither production neither rule are tags in this Stack Exchange site.

A grammar has "Production rules:" rules about the new sequences of symbols that you can produce from old sequences. In the cases of context-free grammars, this the old sequence is always a single non-terminal symbol.

Sometimes people abbreviate "production rules" to "productions". Sometimes people abbreviate "production rules" to "rules".

The two are not synonymous: there are plenty of things which are rules but are not productions, and people may call a single use of a rule a production, or the rule itself a production. Generally, the hope is that it's clear from the context what is meant.


What is the minimal number of states for the DFA? Let the regular expression $R = ((a^*\cup \emptyset \cup \varepsilon^*)^*b)^*$ above $\Sigma = \{a,b,c,d\}$. What is the minimal number of states for a DFA accepting this regex?

$1$
$2$
$4$
$5$ or more

So for my understanding, this regex is equivalent to $(a^*b)^*$. I was able to build the following DFA, nevertheless, I know the answer is $2$. How is it possible?

Your $\Sigma=\{a,b,c,d\}$ so you have to add at least one dead state. The DFA is:


Why should we study all the three forms of representation of finite automata? DFA, NFA and epsilon NFA all the three allow us to represent a particular regular language. With any of those representations we can arrive to the same regular expression, then why do we need to study all the three form of representation of finite automata? There can some explanation on what NFA can do which DFA cannot , that is NFA might help us in designing uncertainties. For example in designing a game (chess), we have many options to move a particular piece from a particular location which can be easily represented using NFA. But what is the use of epsilon NFA when the same can done using NFA or DFA?

Add regular grammars for a fourth. There are others...

Part of the interest in DFA + NFA is that they are simple computation models, with NFA (and $\epsilon$-NFA) examples of nondeterminism (a crucial idea for more elaborate models). To prove DFA and NFA accept the same set of languages is also exploring a very important phenomenon in a simple, understandable setting.

Regular expressions (and also regular grammars) are completely different formalisms, that happen to describe the same set of languages. Again, the proof of this fact explores important cross-relations, and are an example that formalisms might look very diffent, be based on radically dissimilar concepts, but describe the same languages. Again, in a rather simple setting.

For "real world" use, you can start with a regular expression and get a minimal DFA for high-performance searching. Digital circuits are essentially DFAs, understanding them is central in computer engineering. Last but not least, often systems can be modelled as "being in a state" and "moving to another one" on external stimuli, even if the system is very far from a real DFA viewing it this way might help understanding it.

Added later: As noted by Raphael, it may be more efficient to interpret an NFA directly for searching, because creating a DFA can be expensive, and an NFA may be much smaller.


Algorithm for animating/morphing convex polygon diagrams I am trying to find an algorithm to smoothly morph a (given) diagram made of convex polygons into another (given) diagram of the same type.

The target diagram is usually generated from the source, where all kind of operations may happen (new polygon popping up, polygon gets deleted etc.)

So for example I may want to go from

To

with the following constraints:

Morphing between the two diagrams should be smooth (e.g: new polygons should not pop up but kind of grow)
In all intermediate diagrams the polygons should be simple and convex

I tried looking around for papers and/or previous work on that, but failed spectacularly in finding anything, so...

Does anyone here have any idea/references?

(Heck, I'm not even sure this is the right stack exchange board to ask for it)

If your initial set of polygons is a power-diagram, you can insert a new polygon by inserting a new center and growing its power circle smoothly. You don't have direct control of the polygons but rather of the underlying power circles. Power diagrams as Voronoi diagrams are always made of convex polygons.
https://diglib.eg.org/bitstream/handle/10.2312/evs20201057/109-113.pdf
Another way is to subdivide one of the polygons slicing it with a straight line, similar to a spatial partition tree, to ensure the resulting polygon is still convex. http://proceedings.mlr.press/v84/fan18b/fan18b.pdf


Why aren't primality tests easily linear in time complexity? Why don't we consider them as linear? I don't understand. You just have to check for factorization up to sqrt of n.  So it's even faster than linear.
I assume it's not linear only if we compare the number of operations relative to the input in terms of binary representation.  But why would we do so?
It seems to me wrong.  The growth in calculation should be calculated compared to the number itself.  Why do we compare it to the binary representation?

It seems that the main sticking point of the question here is: Why express runtime in terms of the size of the input, rather than the numeric value that the input represents? And indeed in some cases it doesn't make much difference which way you choose to express it. For instance, we could say that the time to read all values in an $N\times N$ matrix is quadratic in the number of columns, or we could say it is linear in the number of cells, and the meaning of these is the same, just with different conventions.
So let's look at some reasons why it is conventional to express operations on numbers in terms of the length of the number rather than its numeric value:

It is more easily comparable to operations on other kinds of data, since every possible form of input has a length but not all forms of input have a numeric value. By consistently using the length of the input as our reference point across a variety of problem types, we also get some nice properties like "the runtime of an algorithm that reads the entire input can never be better than linear."

It provides more useful time complexities in context. For instance, a common use for primality testing is for cryptography. When we're doing cryptography, we might use say a 512-bit number as a key. We would like to have algorithms that scale proportional to the length of the number (512), rather than its numeric value (about $2^{512}$), since $2^{512}$ is such an astronomically large number that even a "linear" time algorithm would never realistically finish.

It relates better to the actual operations performed by the computer. Many people are accustomed to implicitly treating all numbers as capped at some fairly large constant like $2^{64}$, and thus all arithmetic operations are constant-time and the actual internal representation of the number is irrelevant. But when we are analyzing the big-O performance of operations on the number itself we cannot assume that numbers are always small enough to ignore their internal representation. Ultimately, these operations are performed on bits so the number of bits is a good reference point to use for describing the performance.
As a thought experiment, try analyzing the performance of the addition operation. You may have always considered it a constant-time operation, but what happens if the numbers in question get arbitrarily large? Ultimately, you'll need to sum each digit one-by-one, carrying as necessary. It makes sense to describe this as a linear-time operation based on the length of the input, rather than logarithmic time based on the numeric value of the input.


Implementing wait-free consensus with queues Using Herlihy's model and definition of the wait-free hierarchy, a queue (a shared object with enqueue and dequeue) has consensus number 2, because we can initialize the queue with some value, and the first process to dequeue it "wins".

However, it is also possible to do wait-free consensus with queues that start off empty (for example, given as an assignment here, question 1).

I wasn't able to come up with the algorithm - would like help.

A hand-wave explanation: Two processors run asynchronously and communicate via shared memory, with atomic reads and writes being basic operations. We want to solve the wait free consensus problem, where each process starts with a bit value and they need to agree on one of the values, in a way that is wait free: each processor can finish in a finite number of its own steps, regardless of the progress of the others. A result says that such a task can't be done, so we include objects with more powerful operations that will allow consensus. The consensus number of an object is the number of processors in the model that can reach consensus using it. The consensus number of a queue with just enq and deq is 2. Intuitively it isn't 3 because if a processor deqs empty, it can't know which of the other processors deqd the value.

This paper Some results on the impossibility, universality, and decidability of consensus (by Prasad Jayanti and Sam Toueg, 1992) directly answers your question.

We study how initialization of shared objects affects their ability to solve consensus. In particular, although a queue or a stack can solve name-consensus
between two processes, we prove that an initially empty queue or stack cannot.
However, with a tiny extra resource such as a 1-bit safe register, an empty queue or stack suffices to solve consensus.

Please check Section 5 for impossibility proof and algorithm.

Please also check the paper "On the Importance of Registers for Computability" by Rati Gelashvili, Mohsen Ghaffari, Jerry Li, and Nir Shavit, 2014.
In the second paragraph of Introduction, the authors claim that:

(1) We show that $\ldots$ two queues in arbitrary initial states are sufficient for solving two process consensus.
(2) On the other hand, we prove that it is impossible to solve two process consensus using a single empty queue.

A little conclusion is:

In other words, unless you have multiple queues or multiple registers, a queue’s ability to solve consensus is completely dependent on its initialization.

There are many propositions/lemmas/theorems in this paper. And they are not limited to the queue object. I think it may contain what you want to know (I will read it carefully when I have time).


Is it possible to add "memory" to a neural network? Suppose I have a NN with one hidden layer, 10 inputs and 5 outputs, intended to be used as a (for example) game-bot AI. Would it make any sense to add, say, 5 (insert any number here) more inputs and outputs, and directly link these outputs from a previous step to these additional inputs of the next?

I imagine it could work as a RAM of sorts, making it possible to "save" some data that the network finds useful and use it later, therefore enabling the network to make decision not only on the current situation, but also on whatever it may "remember".

But maybe it's better to just hard-code these variables as actual variables and write only what the programmer decided to, such as "enemies killed", without the network being able to save whatever it finds useful?

Yes it is possible.
Recurrent neural networks address this issue. They are networks with loops in them, allowing information to persist.These loops make recurrent neural networks seem kind of mysterious. However, if you think a bit more, it turns out that they aren’t all that different than a normal neural network. A recurrent neural network can be thought of as multiple copies of the same network, each passing a message to a successor.

Visit
http://colah.github.io/posts/2015-08-Understanding-LSTMs/
: This blog explains Recurrent Neural Network(RNN) and LSTM from scratch and also discuss few examples where LSTM is preferred over RNN.


Is the halting problem solvable for NPDAs? After the total silence in response to my last question, I am rethinking my assumptions.  DPDAs are, of course, solvable, and I believe that their loops can be found in the manner I described in my prior question:

arrive at the same state as you were in previously
with the same top symbol as you had last time
without consuming anything on the stack, and
without consuming any input.

But is my last question actually unanswerable because we cannot, in fact, determine whether a NPDA will halt?  Is the halting problem even solvable for NPDAs?

There is no "minimal normal form" or the like for PDAs. If there was, a first step would be to minimize the PDA. This minimal type of machine would certainly not allow pathological examples like the one in your other post. We can, however, do something similar.

You can convert any NPDA to an equivalent context-free grammar. For these there are ways to remove useless rules and simplify them, and there are normal forms (Greibach and Chomsky).  Definitely GNF allows answering the "halting problem", because a word of length n is generated in n steps. Going from GNF back to a PDA you get one with a similar property.

Maybe this method is not satisfactory for you, because you would like a more direct analysis of the given NPDA. But as you have observed, this can be very hard, because of possible very complex epsilon-loops.

To summarize: it is decidable whether for a given NPDA, there exists an equivalent one that always halts. But probably this is always true, because there is (e.g. Greibach NF for all context-free languages).

But you ask about a given PDA, not about whether a halting one exists for the same language. Thus for an answer to your question, one might have to analyze which kind of thing the mentioned grammar transformations eliminate and what that means in terms of PDAs.

Therefore, there is strong evidence that the question is decidable, but I have no definite method. In the transformations, one does not detect whether "useless" loops in the PDA/grammar would halt or not - they are simply eliminated, all of them.


Proof of Brzozowski's algorithm for DFA minimization? Brzozowki's algorithm is cited widely.  Several questions here give examples or discuss its complexity. But I haven't been able to find a proof of correctness for the algorithm. How do we prove it correct?
Any proof accessible to CS undergraduates would be very welcome.

The proof of Brzozowski's result is technical, but not very complicated.
In fact we only have to consider one sequence of reversal-determinization, to obtain the minimality result we want. (The first sequence of reversal determination leads to a deterministic FSA for the reversal of the original language; the minimality proof is for the second reversal-determinization.)

First one needs some good view of the different automata involved.
And nerves of steel.

The construction of Brzozowski.
Let $A = (Q, \Sigma, \delta, q_0, F)$ be a deterministic automaton for the language $L=L(A)$. We assume that all states of $Q$ are reachable from the initial state $q_0$.

In the first step one reverses the automaton: all edges are inverted, and inital and final states are swapped. Informally we get the automaton $\mathrm{rev}(A) = (Q, \Sigma, \delta^{-1}, F, q_0)$.

In the second step one determinizes the automaton so obtained, by the standard construction, but keeping only reachable states. We get $A'= \mathrm{det}(\mathrm{rev}(A)) = (Q', \Sigma, \delta', q'_0, F')$.
The states of $A'$ are sets of states for $\mathrm{rev}(A)$: $Q'\subseteq 2^Q$;
the initial state consists of the initial states for $\mathrm{rev}(A)$, which are final states in $Q$: $q'_0 = F$;
the final states in $A'$ are the states that contain a final state for $\mathrm{rev}(A)$: $U\in F'$ iff $q_0\in U$.

The key of the proof is the following important relation between automata $A$ and $A'$.

  Basic Observation: $q\in \delta'(X,w^R)$ iff $\delta(q,w) \in X$.

Proof (one side only). $q\in \delta'(X,w^R)$ iff there exists a state $p$ in $X$ and a path from $p$ to $q$ in $\mathrm{rev}(A)$ with label $w^R$. But that means there is a path from $q$ to $p$ with label $w$ in $A$, or $\delta(q,w) = p$; thus $\delta(q,w) \in X$. end-of-proof.

As announced, this is used to prove the essential property we need.

  Property: $A'$ is minimal (and deterministic for $L^R$).

Proof. Let $U$ and $V$ be two states in $A'$ that cannot be distinguished. This means that for any string $w^R$ we have $\delta'(U,w^R) \in F'$ iff $\delta'(V,w^R) \in F'$. We show that now $U$ and $V$ are equal.

By the construction of $F'$ we can rephrase indistinguishability as $\delta'(U,w^R) \ni q_0$ iff $\delta'(V,w^R) \ni q_0$.

Apply the Basic Observation, and we have $\delta(q_0,w) \in U$ iff $\delta(q_0,w) \in V$.

From this equality $U=V$ follows, as all states in $Q$ are assumed to be reachable, thus for any state $p$ in $U$ or $V$ there is a string $w$ such that $p = \delta(q_0,w)$.
end-of-proof.

But even after proving, the result is still real magic!


How to remove 'skip' edges from a DAG? (How to find only the longest path from each node to each of its sinks?) In two separate projects, I have come across this problem and I still don't have a good solution for it, so I thought it was worth describing here. Consider the following problem:

I have a set of strings that appear in a corpus with their counts. I would like to merge the counts into any substrings that also appear in the corpus.

Here's a close, but incorrect example to demonstrate it. We create a directed graph of strings, where an edge exists from each node to each of its substrings. We then sum counts in topological order.

counts = {"hi":1, "hillo": 1,  "hillotoo":1, "hillotoothree": 1, "what": 1}

graph = nx.DiGraph()
graph.add_nodes_from(counts.keys())

for str1, str2 in combinations(graph.nodes, 2):
    if str1 in str2:
        graph.add_edge(str2, str1)
    elif str2 in str1:
        graph.add_edge(str1, str2)

for node in nx.topological_sort(graph):
    for neighbor in graph.neighbors(node):
        counts[neighbor] += counts[node]

In the end, 'hi's count should be 4, hi + hillo + hillotoo + hillotoothree. However, this code produces:
{'hi': 8, 'hillo': 4, 'hillotoo': 2, 'hillotoothree': 1, 'what': 1}, because there's many more paths to 'hi' that get exponentially summed. This is because with substrings, there is a direct edge from every string to every one of its substrings by definition. Instead, I need to sum counts from each node to the next smaller substring on each path from that node to a sink in the graph, and remove/avoid "skip" edges from nodes to nodes further down paths to a sink.

(NOTE: This simple string example actually has a straightforward solution: copy the counts first, and only add the original counts to the new ones. However, this works only because there is a direct edge from every string to every one of its substrings, so this solution sidesteps the graph entirely. In the general case, this assumption does not hold. There, we do need to sum along paths, but only along the longest path from each node to each of its sinks, without taking any "skip" edges to avoid overcounting.)

Have a crack at this! Thanks.

On the question from title

For fixed sink $s \in S$ you can find maximal distance from each vertex to this sink by running dynamic programming on topological order:
$$
d(v)=
\begin{cases}
0\text{ if } v = s\\
-\infty \text{ if } v \not= s \land v \in S\\
1 + max_{(v, u) \in E} d(u)
\end{cases}
$$
You can run this algorithm for every $s \in S$ to get the solution for whole problem.

On your problem

Unfortunately your approach won't work, look at this graph:

A
|\
B |
| D
C |
|/
E

If you would look only for longest path to E from A, you would ignore existence of node D. So unfortunately I think you need to go with more "brute force" approach where you will have to run BFS/DFS from every node in the graph and check the number of reached nodes.


Can all NP-hard problems be reduced to one another? I know that all NP-complete problems can be reduced to each other, but how about NP-hard problems? Can all NP-hard problems be reduced to one another?

The answer to your question is no. Take for example the $SAT$ problem and Halting problem. Both are NP- Hard but second can't be reduced to first.


Decidability of equivalence to existential formulas I'm looking for an algorithm to decide if a given first order formula over a fixed vocabulary admits a logically equivalent existential one (i.e. a formula in prenex form where all quantifiers are existentials).

Is it known if such an algorithm exists or does not exist? At least when no functions symbols are admitted? And if it actually exists, which is its complexity?

I know that, given a formula, we can build an equivalent one in prenex form. However, here is an example which illustrates that a formula, equivalent to an existential one, admits also an equivalent prenex formula which is not existential:

Consider the vocabulary $L=\{E\}$, where $E$ is a binary relation symbol. Then the formula
$$\exists x\,E(x,x)$$
which states that a directed graph admits a loop, is an existential formula and is equivalent to
$$\exists x\forall y\,\,\,\,x=y\rightarrow E(x,y)$$
which is in prenex form, but not existential. So applying the algorithm to build a prenex form to the second formula would not produce an existential one.

Surely, no such algorithm can exist in the general case: for a statement of the form $\forall x.\varphi$ statement in arithmetic, with $\varphi$ quantifier-free, there is a $\exists y.\psi$ statement such that

$$ \forall x.\varphi\ \Leftrightarrow \exists y.\psi$$

if and only if the statement is $\Delta_0$, aka decidable. Because $\forall$ statements are undecidable in general, such an algorithm cannot exist.

Edit: The above reasoning is wrong! Indeed, the Bernays-Shönfinkel class of formulas includes the set of $\forall^*\exists^*$ formulas without function symbols (but with arbitrary relational symbols) and is decidable. The $\Delta_0$ statements of arithmetic are not strictly speaking, quantifier free, but only contain bounded quantifiers (which are still quantifiers in FOL!)

However, this suggests an alternate proof: if there were a decision procedure which decides whether an arbitrary sentence were equivalent to some $\exists^*$ sentence, then there would be a decision procedure for arbitrary (function-free) formulas as follows:

Given $\phi$ check whether it is equivalent to an existential formula $\psi$. If it is not, $\phi$ is not provable (otherwise it would be equivalent to the formula $\exists x.\top$).

If it is, then find such a $\psi$ (it's easy to show this is possible) and apply the decision procedure for the B-S class.

Finally, an exercise: repair the above proof using the undecidability of arithmetic.


How to random-generate a graph with Pareto-Lognormal degree nodes? I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution.

Where can I find a kind of algorithm that will produce a random graph with this distribution?

See for example the paper Revisiting Degree Distribution Models for Social Graph Analysis (page 4, equation 1) for a mathematical description (distribution function) of the kind of distribution I'm interested in.

To generate a graph from a prescribed degree sequence (regardless of the degree sequence), one can use an algorithm by Blitzstein and Diaconis:

"A sequential importance sampling algorithm for generating random graphs with prescribed degrees" by J. Blitzstein and P. Diaconis

Unfortunately their algorithm is potentially  $O(n^2 \bar{d})$, for $n$ vertices with average degree $\bar{d}$, so this might not be fast enough depending on the size of your graph and the application involved.

Molloy and Reed introduced the "Erased Configuration Model" which pairs vertices based on a degree sequence chosen proportional to the remaining free slots.

"A critical point for random graphs with a given degree sequence" by M. Molloy and B. Reed

A paper by Britton, Deijfen and Martin-Lof show that the Erased Configuration Model asymptotically approaches the prescribed degree distribution chosen.
While not guaranteeing the exact degree sequence input, I would recommend the erased configuration model for its simplicity and speed.

"Generating simple random graphs with prescribed degree distribution" by T. Britton, M. Deijfen and A. Martin-Lof

Briefly, the erased configuration model graph generation algorithm creates "hooks" for each vertex, where the number of hooks for each vertex is initially given by the degree sequence.  Going from the vertex with the most hooks first, another hook is chosen uniformly at random from the pool still unattached.  A connection is made for this pairing.  Once the pool of hooks is exhausted, self loops are removed and multi-edges are collapsed into one.

Since self loops are allowed and multi-edges collapsed, the resulting degree sequence could potentially be different than the input sequence, so this method is not exact.  If exactness is preferred, the algorithm by Blitzstein and Diaconus can be used at a higher computational cost.  Note that the algorithm of Blitzstein and Diaconus checks whether a prescribed degree sequence is feasible (or "graphical" in their parlance), so degree sequences might need to be regenerated should they not be realizable.

Degree sequences can be chosen under any distribution you want.  In your case, you would want to choose them based on a Pareto-Lognormal distribution.

I would also like to briefly note that generating graphs with prescribed degree sequences that follow a particular distribution, the Pareto-Lognormal distribution say, might not generate the type of "knowledge" graphs you want.  The degree distribution is just a profile of a graph and says nothing about other features which might be present in the original graph ensemble you would be trying to model.  As Raphael points out in the comments, Wikipedia's page on scale-free networks is a good starting point for some review.


Is a stack machine with a forward read iterator Turing complete? It is well known that a machine with a single stack as only unlimited storage is not Turing complete, if it can only read from the top of the stack. I want a machine which is (slightly) more powerful than a stack machine, but still not Turing complete. (I wonder whether there exists a non-Turing complete machine, which can deterministically simulate any non-deterministic pushdown automata with an only polynomial slow-down.) The most benign (straightforward) extension that came to my mind was a (single) forward read iterator.

Let me elaborate the implementation details, to make it clear what I mean by a forward read iterator. A singly linked list can be used for implementing a stack. Let the list be implemented by a pointer pTop, which is either zero, or points to an SList node. An SList node consists of a payload field value and a pointer field pNext, where pNext is either zero, or points to an SList node. Let the forward read iterator be implemented by a pointer pRead, which is either zero, or points to an SListnode. The pointers pTop and pRead cannot be accessed directly, but can only be used via the following methods:

Push(val) creates a new SList node n with n.value = val and n.pNext = pTop, and sets pTop = &n.
Pop() aborts if pTop == 0 or pRead == pTop. Otherwise it reads val = pTop->value and pTopNext = pTop->pNext, frees the SList node pointed to by pTop, sets pTop = pTopNext and returns val.
ReadBegin() sets pRead = pTop.
ReadNext() aborts if pRead == 0. Otherwise it reads val = pRead->value, sets pRead = pRead->pNext and returns val.
ReadFinished() returns true if pRead == 0, and false otherwise.

Your model is Turing-complete, unfortunately.

You can simulate a queue in your data structure using the following algorithm. It introduced 3 new stack symbols: $d, x, y$.

Enqueue(val) is just Push(val).

For Dequeue():

ReadBegin().
Count the number of anything else - number of $d$ in the whole stack (which should be always non-negative). Push $y$ or pop $x$ for every $d$, and push $x$ or pop $y$ for anything else. Always prefer pop to push. Finally there won't be any $y$ in the stack and the result will be the number of $x$ on the top of the stack.
ReadBegin().
While pTop is a $x$:

Repeat ReadNext() until it returned something other than $x$ and $d$.
Pop().

Push a $d$.
The last result of ReadNext() is returned as the result of Dequeue.

The proof is straightforward. Check the revision history for a more complicated version firstly reducing it to a two-way version.


Building probability distribution functions from observation There are N players and M objects, each of the objects has a value. Each player has a strategy in choosing an object. Each round a player will choose an object, many players can choose the same object. However the value of each object is divided evenly among every player that has chosen it. There will be 9000 rounds(choices) per game. Our goal is to maximize the values that we accumulate at the end of the game.

Question: how can I build a probability distribution function for each playing assuming that their decisions are random variables?

Current Approach: My current approach is to count the frequency of a player choosing a specific object and dividing by the total number of rounds, that would give a probability a player is likely to choose that specific object.

Problem: With each player playing aggressively trying to be unpredictable as possible(noise), with my current approach the probability distribution functions are not accurate(9000 rounds doesn't seem to be enough data). Is there a better way to build these distribution functions?

Note: I've read somewhere that (Bayes model and HMM) are more superior than frequency counts, but I am not sure how to adapt it to this situation.

i am not sure i understand correctly what the question is or rather what are the observations from which the (experimental) distributions are going to be estimated.

The problem of a distribution estimation is related more to statistics than computer science althougn it can be relevant in this area as well.

There are various methods using 2 main approaches:

Parametrized models of a probability distribution, where one (assuming prior knowledge) uses a pre-defined model (or form or function) of the distribution (e.g a Gaussian) with some free parameters depending on data (observations) and estimates these parameters (eg through Maximum Likelihood or EM algorithm or Maximum Entropy etc..). Even if the form of the prob distribution is not known this method can still be used on approximations like Gauusian Mixture Models. This method produces smooth (and usually robust) estimated distributions assuming the prior form is close to the underlying prob. distribution.
Un-parametrized models, estimate the whole PD (including its form) directly from the data. methods in this category are Parzen windows and kernel estimation. This method can be better from parametrized estimation provided the form of the underlying pdf is completely unknown or non-trivial or irregular in some sense.

All the previous methods are computationally efficient (although not necessarily polynomial). This is like the way the Simplex algorithm works, although it is not polynomial-time, it is efficient in many practical situations.


Using Headpose Vector and 2D Points to Compute Distances I have a frame taken from a video. The frame contains a face and I have the (x, y) locations of the features (corners of lips, edge of eyebrows, etc.) and the headpose vector (pitch, yaw, roll), which shows the direction that the face is looking in degrees ((0, 0, 0) would be at the camera).

I need to calculate distances between specific points in real (3D) space. How can I map the feature locations to 3D space?

You don't have enough information to calculate 3D points for anything--all your information is relative right now. You need something that establishes a measurement, and some way to determine depth. If you know how far a point is from the camera (or can estimate it), then you can at least start calculating locations of features you know to be within the vertical plane containing that point. Or if you know how large a feature is, then you can calculate the sizes of features also assumed to be in the same vertical plane.
Alternatively, if you can use information from other frames, then you can assume a rigid model for certain facial features and begin to make estimates, but it's still all scale-free until you can pin down a distance somewhere.


Prove: possible to construct automata accepting all strings of other automata sans 1-length strings I believe that I have a procedure for doing this, but I don't know how to approach the proof (and for that matter I'm not entirely sure the procedure is correct).

Here's the exact problem statement:

  Given DFA $A = (\Sigma, Q, q_0, F, \delta)$ construct DFA $B$ from $A$ s.t. it accepts all words of the language of $A$ which have length distinct from 1.

And here's pseudocode that has to solve the problem followed by some explanation:

def ensure_word_length_ne_one(alphabet,
                              states,
                              initial,
                              final,
                              transition_function)
 loops = [i for i in alphabet if transition_function(initial, i) == initial)]
 new = make_new_accepting_state()
 # all arcs to the states directly accessible from the initial state
 # except the arcs from the initial state
 backarcs = [(arc.source, arc.destination, arc.input)
             for arc in arcs_to(set(for arc in arcs_from(initial))) -
                                set(arcs_from(initial))]
 for input in loops:
   # Remove all loops from the first state
   add_transition(initial, new, input)
   remove_transition(initial, initial, input)
   add_transition(new, new, input)
 for input in alphabet:
   # Bounce back from the new state to the first state
   add_transition(new, initial, input)
 for source, destination, input in backarcs:
   # For each state directly reachable
   # from the first state reattach
   # all inbound transitions
   # to the new state
   new = make_new_accepting_state()
   remove_transition(source, destination, input)
   add_transition(source, new, input)
   outbound = [(arc.input, arc.destination) for arc in arcs_from(new)]
   for input, destination in outbound:
     # Bounce back from the new state
     # to the states immediately
     # reachable from source state
     add_transition(new, destination, input)

The code tries to be more or less Python.  Auxiliary functions do what their name suggests.  The basic idea is as follows:

A DFA can accept words of length 1 in only these two scenarios:

It loops on some input in the first accepting state.
The state directly linked from the first state is accepting.

Below is the procedure to remove these accepting states while accepting
all other inputs.

If the first state loops on some inputs add a new state $q_1$, remove
all transitions from $q_0$ to itself and add transitions for the same
inputs from $q_0$ to $q_1$.  Add transitions on all inputs from
$q_1$ back to itself.

For any input which on which $q_0$ used to loop $B$ now necessary makes
at least two transitions before accepting it, possibly accepted string
with prefixes that did not cause the automate to loop on $q_0$ are
still accepted (nothing has changed).
For each accepting state $q_n$ directly linked from $q_0$ we do the
following:

change $q_n$ from accepting to non-accepting.
add a new accepting state $q_2$.
remove transitions from states $Q_i$ directly leading to $q_n$, unless they originate in $q_0$, for
each transition removed add a new one for the same input from $Q_i$
to $q_2$.
for each outbound transition from $q_n$ add new transition on the
same input from $q_2$.

Most proofs related to automata I've read so far use structural induction for similar tasks, but I cannot think about a way to approach the proof.  The difficulty is in ensuring that all strings accepted by $A$ are still accepted.

PS. I have the pseudocode set in LaTeX, if it is necessary, I can add it to the post.

Basically, the answer is what @Shaull says in the comments: construct a product automaton with the one that accepts all strings of length unequal 1.
What we use here is the fact that regular languages are closed under intersection. The product construction takes two automata, and simulates them in parallel. States are pairs of states of the original two automata. The combination accepts if both components accept.

But you ask for "minimal operations". So, have a look at what is in fact the automaton that accepts strings of length not 1. It simply has three states "zero", "one" and "many" with a loop for each letter at the last state. It simply counts letters up to length two (and then keeps in that state).

The product construction for this specific automaton is rather straightforward. Set aside a copy of your original automaton $A$. (You might add label "many" to each of the states, but that is extra.) Now add to these fresh copies of the original initial state and all states reachable in one step from the initial state. If the initial state has a loop, it is copied twice. (If you fancy it these get extra labels "zero" and "one"). Now remove final states from the "one"s and copy the original wiring.

Like I said, this is just a particular case of the product construction. In fact it might be even what is in your own pseudo code.


Why is $\log_{2}n = O(n^{0.00001})$? Why is $\log_{2}n = O(n^{0.00001})$ true?

This is obvious to me when the exponent is $> 1$ but i'm having trouble understanding the cases where the exponent is very close to $0$. I would have to find some constants $c$ and $n_0$ where $\log_{2}n \le cn^{0.00001}$ for all $n \gt n_0$.

Where I'm stumped is that $n^{0.00001} \approx 1$ and $\log_{2}n$ approaches infinity as $n$ gets larger. It feels like regardless of whatever $c$ and $n_0$ I choose, if $n$ was large enough, I could show that $\log_{2}n \ge c$.


Visual Programming languages Most of us learned programming using "textual" programming languages like Basic, C/C++, and Java. I believe it is more natural and efficient for humans to think visually. Visual programming allows developers to write programs by manipulating graphical elements. I guess using visual programming should improve the quality of code and reduce programming bugs. I'm aware of a few visual languages such as App Inventor, Scratch, and LabView.

Why are there no mainstream, general-purpose visual languages for developers? What are the advantages and disadvantages of visual programming?

In general, there is a trade-off in programming language design between ease of use and expressiveness (power).  Writing a simple "Hello, world" program in a beginner language, such as Scratch or App Inventor, is generally easier than writing it in a general-purpose programming language such as Java or C++, where you might have a choice of several streams to output to, different character sets, the opportunity to change the syntax, dynamic types, etc.

During the creation of App Inventor (which I was part of), our design philosophy was to make programming simple for the beginner.  A trivial example was basing our array indices at 1, rather than 0, even though that makes calculations likely to be performed by advanced programmers slightly more complex.

The main way, however, that visual programming languages tend to be designed for beginners is by eliminating the possibility of syntax errors by making it impossible to create syntactically invalid programs.  For example, the block languages don't let you make an rvalue the destination of an assignment statement.  This philosophy tends to yield simpler grammars and languages.

When users start building more complex programs in a blocks language, they find that dragging and dropping blocks is slower than typing would be.  Would you rather type "a*x^2+b*x+c" or create it with blocks?

Justice can't be given to this topic (at least by me) in a few paragraphs, but some of the main reasons are:

Block languages tend to be designed for beginners so are not as powerful by design.
There is no nice visual way of expressing some complex concepts, such as type systems, that you find in general-purpose programming languages.
Using blocks is unwieldy for complex programs.


Why does this recurrence give O(n) time? Given this following recurrence: $$T(n) =  T(n/2) + O(n)$$Find the final time complexity.

My first thought is $O(n\log n)$, since there is at most $\log n$ times the
$O(n)$ will appear.

However, if we adopt the following analysis and let $n=2^m$, then we have:

$$T(2^m) = T(2^{m-1}) + k(2^m) = T(2^{m-2}) + k(2^m + 2^{m-1})...$$

Which we can then condense to have the cost become:

$$2^m + 2^{m-1} .... + 1 = 2^{m+1} - 1$$

And so since the cost is $O(2^m)$, we have our $O(n)$ time as required.

Is the analysis valid? Because I have so very often seen proofs using recurrences of the form $T(n) = T(n/2) + ...$, and they all similarly concluded that there will be $\log n$ times of the relationship.

Which is correct?

Your second analysis is correct, and $T(n) \in \Theta(n)$. You can also use the Master Theorem to verify this.

The reason that the first "naive" analysis fails is that you don't have $O(n)$ at each step, you have $O(\frac{n}{2^{i}})$ where $i$ is how far down the recursion you've gone.

Ignoring the constant multipliers for the moment, this gives
$$
\sum_{i=0}^{\log n} \frac{n}{2^{i}} = \frac{\sum_{i=0}^{\log n}n}{\sum_{i=0}^{\log n}2^{i}} = \frac{n\log n}{2^{log n + 1}} = \frac{n\log n}{2 \log n} = \frac{n}{2}
$$

Your second analysis basically does the same thing, just using variable substitution instead.


Capacity of binary not symmetrical channel I have to solve this exercise in information theory:

A binary not symmetrical channel has probability of transition from 0 to 1 $P(output=1|input=0)=p$ and probability of transition from 1 to 0 $P(output=0|input=1)=q$.
I have to calculate the channel capacity and the input distribution that leads to this capacity value.

I thought that the channel was the following:

So:
$$P(Y|X)=\begin{pmatrix}
1-p & p\\
q & 1-q
\end{pmatrix}$$

Then I tried to calculate the capacity:

$$C=\max_{p(x)}I(X;Y)$$

where

$$I(X;Y)=H(Y)-H(Y|X)$$

where

$$H(Y)=-(1-p+q)\log (1-p+q) - (p+1-q) \log (p+1-q) = ?$$

I don't think is correct. How do I calculate $H(Y)$ and $H(Y|X)$?

I tried to solve the exercise in this way.

$$\pi = Pr(X=0), 1 - \pi = Pr(X=1)$$

$$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q))$$

If I call:
$$\pi(1-p)+(1-\pi)q = a$$
$$\pi + p(1-\pi)(1-q) = b$$
then
$$H(Y)=H(\pi(1-p)+(1-\pi)q, \pi + p(1-\pi)(1-q)) = -a \log a - b \log b$$

Now I have to calculate:
$$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi H(Y|X=0)+ (1- \pi)H(Y|X=1)$$
where

$$H(Y|X=0) = -P(Y=0|X=0) \log P(Y=0|X=0) - P(Y=1|X=0) \log P(Y=1|X=0) = -(1-p) \log (1-p) - p \log p$$
$$H(Y|X=1) = -P(Y=0|X=1) \log P(Y=0|X=1) - P(Y=1|X=1) \log P(Y=1|X=1) = - q \log q-(1-q) \log (1-q) $$

So:
$$H(Y|X)=Pr(X=0)H(Y|X=0)+Pr(X=1)H(Y|X=1) = \pi [-(1-p) \log (1-p) - p \log p]+ (1- \pi)[- q \log q-(1-q) \log (1-q)]$$
and if I call:
$$[-(1-p) \log (1-p) - p \log p]=c$$
$$[- q \log q-(1-q) \log (1-q)]=d$$
then
$$I(X;Y)=H(Y) - H(Y|X)=-a \log a - b \log b + \pi c + (1-\pi)d$$

it's right? Thanks

You need to compute $H(Y)$ by its definition:

$$ H(Y) \triangleq \Pr(Y=0) \log \frac{1}{\Pr(Y=0)} + \Pr(Y=1)\log\frac{1}{\Pr(Y=1)}$$

To be able to compute this formula, you need to figure out what is $\Pr(Y=1)$ and $\Pr(Y=0)$. These two measures actually depend on the distribution of $X$.

To compute $H(X|Y)$ again, use the definition.
$$H(Y|X) \triangleq \Pr(X=0) H(Y| X=0) + \Pr(X=1)H(Y|X=1)$$

where $H(Y | X=0)$ is easy to compute from the original entropy definition $H(Z)$, for a random variable $Z$ that is distributed same as $(Y|X=0)$. This is immediately given by your $P(Y|X)$.

In order to compute the channel's capacity, you will need to find the distribution $p(x)$ that maximizes $H(Y)-H(Y|X)$.

Maybe you should also check a textbook about information and entropy. For instance, try Cover & Thomas, "Elements of Information Theory", Chapter 7 (Channel Capacity).


How do I find running time for the following divide and conquer problem? Question is to find the runtime $T(n)$ of following problem by solving the recurrence.

$T(n)=16\cdot T(\frac{n}{4}) + n!$.

I went through the following theory.

If the recurrence relation is of the form $T(n)=aT(\frac{n}{b}) + \Theta(n^k(\log n)^p)$,where $a \geq 1$ , $b \gt 1$, $k \ge 0$ and $p$ is a real number, then:

If $a \gt b^k$, then $T(n)=\Theta(n^{\log_b a})$.
If $a=b^k$

If $p \gt -1 $, then $T(n)=\Theta(n^{\log_b a}(\log n)^{p+1})$.
If $p=-1 $ then $T(n)=\Theta((n^{\log_b a}\log \log n)$.
If $p \lt -1 $, then $T(n)=\Theta(n^{\log_b a})$.

If $a \lt b^k$

If $p \ge 0 $, then $T(n)=\Theta(n^k(\log n)^p)$.
If $p \lt 0 $, then $T(n)=O(n^k)$.

Now I want to know how do I compare the second terms of the the equations ($n!$ and $\Theta(n^k(\log n)^p) $) to obtain $k$ so that I can check which of the above case holds true ?

You cannot use the Master Theorem to solve this recurrence, since $n!$ doesn't grow like $n^c$ for any $c$. Instead, Stirling's approximation shows that $n! \sim \sqrt{2\pi n} (n/e)^n$. Rather, expand the recurrence to get
$$
T(n) = n! + 16 (n/4)! + 16^2 (n/16)! + \cdots.
$$
Stirling's approximation shows that the latter terms are tiny compared to the first one. Therefore
$$
T(n) \sim n!.
$$
This is just shorthand for
$$
\lim_{n \to \infty} \frac{T(n)}{n!} = 1.
$$

If you want to prove this formally, one way is as follows. Start with the observation that $n/16 \geq 4$,
$$
16 (n/4)! \leq (n/4+1)(n/4)! = (n/4+1)! \leq \frac{1}{n} n!.
$$
The first inequality uses $n \geq 60$, and the second $n \geq 4$. Continuing in this vain, for $n/16^2 \geq 4$,
$$
16^2 (n/16)! \leq \frac{1}{n/4} (n/4)! \leq \frac{1}{n/4} \frac{1}{n} n! \leq \frac{1}{n} n!.
$$
In the same way we show that $16^k (n/4^k) \leq n!/n$ for $n/4^k \geq 4$. Therefore
$$
T(n) = n! + 16(n/4)! + 16^2(n/4^2)! + \cdots \leq n! + n!/n + n!/n + \cdots + 16^r T(4),
$$
where $n/4^r = 4$, and so $r = \log_4 n - 1$, which implies $16^r = n^2/16$. Since there are $r-1 = \log_4 n - 2$ summands of the form $n!/n$, we certainly have
$$
T(n) \leq n! + \frac{\log_4 n}{n} n! + \frac{T(4)}{16} n^2.
$$
This shows that $T(n) = n! + f(n)$, where
$$
f(n) = \frac{\log_4 n}{n} n! + \frac{T(4)}{16} n^2
$$
is a function satisfying
$$
\lim_{n \to \infty} \frac{f(n)}{n!} = 0.
$$
On the other hand, clearly $T(n) \geq n!$. This implies what we claimed above, $T(n) \sim n!$.


Equivalence of dfferent TM definitions I stumbled upon these two defintions of a turing machine:

http://www.cs.um.edu.mt/gordon.pace/Teaching/Complexity/CoursePage/Notes/chapter5.pdf

http://scholar.harvard.edu/files/harrylewis/files/s6_sols.pdf

The difference which bothers me is that the second one allows only left and right movements whereas the first allows left, right and not moving the head at all.

First definition:  $\delta_1: Q_1 \times \Gamma_1 \mapsto Q_1 \times \Gamma_1 \times \{L,R,S\}$

Second definition:  $\delta_2: Q_2 \times \Gamma_2 \mapsto Q_2 \times \Gamma_2 \times \{L,R\}$

Are they equivalent? If they are equivalent it should be possible to transform a TM that can do $\{L,R,S\}$ into a TM which always has to move left or right (does only $\{L,R\}$)?

How is this possible?

Yes they are equivalent and it is always possible. Informally: you can exchange any $S$ move state with pair of states that goes $L$ then $R$ (or in the other direction).

Formally:
Prove that standard Turing Machine is equivalent to class of Turing Machines with $S$ (no move).
Let $M$ denote standard TM, there exists a TM $M'$ with no move option such that $L(M) = L(M')$. This way is trivial, simply do not use $S$ move in the extended version.
In the other direction:
Given TM $M'$ with no move option, construct equivalent TM $M$ such that $L(M') = L(M)$.
Construct new transition function $\delta'$ for $M$ such that for each state with move $\in \{L, R\}$ in $\delta$ there is equivalent state in $\delta'$.
For each $S$ move in $\delta$ put two states in $\delta'$.
So for $\delta(q_x, a, b, S, q_y)$ put two states to $\delta'$, $\delta(q_x, a, b, L, q_n)$ and $\delta(q_n, *, *, R, q_y)$. The $q_n$ matches the acceptance with $q_x$.  If the $S$ move was accepting state, make the second state accepting. This gives the equivalence in the accepting states and the head (heads) position.
$L(M') = L(M)$, so these classes are equivalent.


counting arithmetic progressions $a, a+r, a+2r$ in a list I have a large list $L$ of numbers and I need to count instances of elements $a,b,c \in L$ such that $a +c = 2b$. A brute-force approach would be to check all possible triples $(a,b,c)$ and this will run in $L^3$ time.

Can I do any better?

Given that the OP is rather unprecise as to the kind of numbers he is
considering (though he later said integers or integers modulo $p$ in a comment), I will try to answer nevertheless, by trying to limit the
number of assumptions I can make. And while I am at it anyway, I will
generalize a bit.

This builds on the contributions of previous answer and comments, by
Rick Decker, Hendrik Jan. and HEKTO.

Generalized statement of the problem

We consider four sets of values $\mathcal{U}, \mathcal{V}, \mathcal{W}, \mathcal{Z}$, two functions $f:\mathcal{U}\times
\mathcal{V}\to \mathcal{Z}$ and $g:\mathcal{W}\to\mathcal{Z}$. Given 3
sets or
lists of values $U,V,W$, respectively from $\mathcal{U}, \mathcal{V},
\mathcal{W}$,  count the number of triples $(u,v,w)\in U\times V\times W$ such
that $f(u,v)=g(w)$. Each computation of the functions $f$ and $g$ is supposed to
be in constant time.

Let $n=max(|U|,|V|,|W|)$

General solution

This is essentially HEKTO's suggestion.

Build a hash table containing each value $w\in W$ indexed by
$g(w)$. This has a cost $O(n)$ under the Simple Uniform Hashing Assumption(SUHA). Without the SUHA, one can use a balanced tree with complexity $O(n\log n)$.

Then for each $u\in U$ and for each $v\in V$ check whether
$f(u,v)$ is in the hash table in constant time (or in the balanced tree in logarithmic time). If it is in an entry $g(w)$, then add $(u,v,w)$ to the
list of solutions (or increase the solution count by one).

Complexity is $O(n^2)$ with hash table, under SUHA, or $O(n^2\log n)$ with a balanced tree.

Case of ordered sets

This is essentially Hendrik Jan's suggestion.

We assume that one of the two sets $\mathcal{U}$ or $\mathcal{V}$ (say $\mathcal{V}$, w.l.o.g.) and the
set $\mathcal{Z}$ are totally ordered and that the function $f$ is monotonic with respect to
the argument in the ordered set (here the second argument).

Then we can have a modified algorithm that does not need a hash table.

First sort the set $V$.

Build a list $L$ of pairs $(w,g(w))$ for all $w\in W$, sorted with respect
to the second element.

Then for each $u\in U$, compare the ordered values of $f(u,v)$ with
the ordered values $g(w)$ of the pairs in $L$, by moving up the two
list $V$ and $L$ as you would do for set intersection, and add the answer
$(u,v,w)$ whenever $f(u,v)=g(w)$ for some pair $(w,g(w))$.

Complexity is $O(n^2)$.

Application to "numbers" and arithmetic progression

We consider the initial problem of detecting arithmetic progressions
in the elements of a list.

The three lists of the abstract case are the same list. The function $f$
is addition, and the function $g$ is doubling (i.e. product by 2).

The ordered set solution applies well to integers, rationals, or reals (with
some care).

Complex numbers are not an ordered field. However they can be considered as an ordered groups with respect to addition, by prioritizing coordinates, so that $a+ib> a'+ib'$ iff $a>a' \vee (a=a' \wedge b>b')$. So the ordered set construction can be used.

The hash table algorithm seems necessary in the case of
$\mathbb{Z}/p$ (i.e. integers modulo $P$) since non-trivial linearly ordered groups are
necessarily infinite, which is not the case for $\mathbb{Z}/p$.

However the ordered set construction could be adapted to
$\mathbb{Z}/p$ without loss in complexity, by allowing the list $L$
to be scanned twice, with some proper bookkeeping.


Is SAT sparse? Is this an understood problem? Intuition suggests that SAT is definitely not sparse. For any well-formed SAT problem $\phi$, we have $(\phi \in SAT) \vee (\neg\phi \in SAT)$, and $\exists \phi : (\phi \in SAT) \wedge (\neg\phi \in SAT)$ (perhaps "many" such $\phi$ satisfy this).

The set of well-formed queries is not sparse, consider $a_1 \wedge \cdots \wedge a_n$ with each $a_n \in \{x_1, \neg x_1\}$.

But this proof is not complete since negation of a DNF and CNF and forcing canonical form changes length, and if canonical form is dropped then it is not obvious how problems relate to representations of their inverses.

Is it known that SAT is not sparse?
Is it possible for a dense language to reduce to a sparse language, as is supposed in Mahaney's theorem?

SAT is not sparse. For example, we have exponentially many monotone formulas per input length, and they are all satisfiable.

Regarding your second question, since most people conjecture that P≠NP, according to Mahaney's theorem those people don't expect NP-complete problems to be reducible to sparse languages.


Decision problem which belongs to P reduced to a decision problem which belongs to NP? Is it possible to have a decision problem $A$ which belongs to P and reduce it to a decision problem $B$ which belongs to NP, i.e. $A \leq_{\mathrm{p}} B$, where $A$ belongs to P, $B$ belongs to NP?

Of course. Just take B=A, since every P problem is in NP.


Confluent directed acyclic graph A directed acyclic graph $G$ is confluent, if any two vertices
  ${v_1},{v_2}$ in $G$ which have a common ancestor $u$ also have a
  common successor $w$. (I.e. if there are paths from some $u$ to both
  ${v_1}$ and ${v_2}$, then there are also paths from ${v_1}$ and
  ${v_2}$ to some $w$. Vertices $u,{v_1},{v_2}$ and $w$ do not need to
  be distinct, thus e.g. a single "line" of vertices is trivially
  confluent) Design a linear-time algorithm that determines whether
  a given DAG $G$ is confluent.

Is the "line" with $3$ vertices $u \to v \to w$ s.t. ${v_1} = {v_2}$ trivially confluent? Or is it nesseccary to have ${v_1} \ne {v_2}$ and thus the smallest number of vertices such line may have is $4$ $u \to {v_1} \to {v_2} \to w$?

Edit: Solved the problem.

Yes, the "line" $u \to v \to w$ is trivially confluent, and so are the empty graph, the graph with a single node, and the "line" $u \to w$. In the case of a graph with a single node $v$ there is only one case to consider, with $v_1 = v_2 = v$. The common ancestor is then $v$ itself, and the common successor is also $v$.


Any finite Graph G with all V have at least degree of 2, is it true that every vertex is necessarily contained IN a cycle? As title, (note: this questions is asking weather or not all vertices are contained IN a cycle not asking if the G contains a cycle.
My attempt is that:

So this graph would be an counter example that disprove that every vertex is contained in a cycle. Would like to know if this is a valid counter-example since V1 is not contained in a cycle.
PS: As I was finding examples, also observed that if the all V have exactly degree of 2, then it is necessary that all vertices are contained in a cycle. Please prove if I am missing something.

You are asking two questions. The first question is whether your graph is a counterexample to the claim that in a graph with minimum degree 2, every vertex lies in a simple cycle.
Unfortunately, your graph is not simple, so if by graph you mean simple undirected graph, then your graph is not a counterexample. However, if you replace the self-loop by a cycle, you should get a valid counterexample.

The second question is whether the claim is true if the graph is 2-regular (all degrees are 2). Indeed, a 2-regular graph is a disjoint union of cycles. I'll leave you to figure out a proof.


Trying to Classify MNIST where pixels are shuffled with a seed.Why is it not working? I transformed the MNIST dataset as follows:(X (70000 x 784) is the training matrix)

np.random.seed(42)
def transform_X():
    for i in range(len(X[:,1])):
        np.random.shuffle(X[i,:])

I had thought that shuffling the pixels in an image would make the digits unrecognizable by humans,but the machine learning algorithms would still be able to learn from the images with shuffled pixels correctly.

I cannot understand the mathematical reason behind not learning. Do you think this should work and I should recheck my code for any mistakes?
I trained on SVC and SGDClassifier of sklearn.Results from both are just randomness.

A good indication, although quite rough, if an algorithm is capable of solving a task (especially pattern recognition tasks) is to check if humans can. We evolved to be quite good at it.

Obviously, that might not always be true. But in your case, by shuffling you loose all the structure of the data. The only possible feature your ML algorithm can use is the number of pixels set vs unset (or the pixel values, for grayscale images), thus basically losing all the structure. The problem is that this is a bad feature since there is little correlation between the number of pixels set and the digit. There is no pattern left, and any attempt to learn a pattern is doomed to fail. Thus, your algorithm may:

try to learn a pattern where there is none
not have enough features to do the classification

or a combination of the 2.


How to derive the worst case time complexity of Heapify algorithm? I would like to know how to derive the time complexity for the Heapify Algorithm for Heap Data Structure.
I am asking this question in the light of the book "Fundamentals of Computer Algorithms" by Ellis Horowitz et al. I am adding some screenshots of the algorithm as well as the derivation given in the book.
Algorithm for Heapify():
procedure $HEAPIFY(A,n)$
   //Readjust the elements in A(1:n) to form a heap//
   integer $n,i$
   for $i\leftarrow\lfloor n/2 \rfloor$ to $1$ by $-1$ do
      call $ADJUST(A, i, n)$
   repeat
end $HEAPIFY$

Derivation for worst case complexity:

I understood the first part and last part of this calculation but I cannot figure out how $2^{i-1}(k-i)$ changed into $i 2^{k-i-1}$.
All the derivations I can find in the internet takes a different approach by considering the height of the tree differently. I know that approach also leads to the same answer but I would like to know about this approach.
You might need the following information:
$2^k-1 = n$ or approximately $2^k = n$, where $k$ is the number of levels, starting from the root node and the level of root is 1 (not 0) and $n$ is the number of nodes.
Also the worst case time complexity of the Adjust() function is proportional to the height of the sub-tree it is called, that is $O(log n)$, where $n$ is the total number of elements in the sub-tree.

It's a variable substitution.
First, realize that in the leftmost side of the equation, the last term of the sum is zero (because when $i = k$, $k-i = 0$). So, the range of the first summation can be written as $1 \le i \le k-1$. Now, substitute $i$ with $k-i$. $i$ iterates over the set ${1, 2, ... , k-1}$ and $k-i$ iterates over the set ${k-1, ... 2, 1}$, they are the same set, so, we can do this.


Prove the equivalence of regular expressions I have a question relating to regular expressions that I'm a bit confused about, If someone can help me out, that would be very much appreciated.

Suppose there exists regular expressions R, S and T.

Then is R* ≡ R* R*?

I know the way to prove this is by showing that L(R*) is a subset of L(R*R*) and vice versa, but I have no idea how to do that.. Just started learning about regular languages so I'm a bit confused. Can I please get any direction on how to do this?

Start with
$$
R^*R^* = \left(\bigcup_{i=0}^\infty R^i\right) \left(\bigcup_{j=0}^\infty R^j\right) = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^i R^j = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^{i+j}.
$$
As $i,j$ go over all pairs of non-negative integers, $i+j$ goes over all non-negative integers, hence
$$
R^*R^* = \bigcup_{i=0}^\infty \bigcup_{j=0}^\infty R^{i+j} = \bigcup_{k=0}^\infty R^k = R^*.
$$


Find the element $x$ that maximizes $f(x)$ for $x \in \sum A_i$ I have a collection of sets $A_i \subset \mathbb{Z}$ where I want to find the global maximum after combining the sets using sumset.
The sumset is
$$ A + B = \{ a + b : a \in A , b \in B \} $$
and $R$ is the combination of each set $A_i$
$$ R = \sum A_i $$
Then with some function $f : \mathbb{Z} \rightarrow \mathbb R$, I want to select the element $x \in R$ such that $f(x)$ is maximized.
Practically, each element in a set is a 64 bit unsigned integer, so each set is bounded by $M = 2^{64}-1$ and the output of a sumset operation never produces an element exceeding that bound. Also each set is sparse.
I have a solution for this but I am looking for optimizations or different approaches. I currently use sparse polynomial convolution based on Johnson's Sparse Polynomial Arithmetic (1974) [1]. In summary, I am implementing sparse polynomial convolution first, and then iterating over terms of that result to select the element such that $f$ is maximized.
My current method is to represent each set by its characteristic function. Then the sumset operation becomes the convolution of two of polynomials. Normally, FFT would be used next but since the set is sparse, using a dense array to hold the polynomial produces many zeros, so I instead resort to using a sparse polynomial where each is a sorted array of integers representing the exponents with non-zero coefficient. This step is computed by distributing the terms of one polynomial over the other to create a set of polynomials multiplied by one term. Since each term is represented solely by the exponent, this is just adding to each value in an array, which maintains the sorted property. Then I combine them using a $k$-way merge using a heap. Then, after each convolution is performed ending with the resulting polynomial $r$, the function $f$ is mapped over the exponents of $r$, and the exponent that maximizes the value of $f$ is the solution.
I've implemented this approach and it works well on small cases, but as each $|A_i|$ increases, $|R|$ increases exponentially and won't fit in machine memory. The issue is that I am generating the entire set $R$ whereas I only need a single element of $R$. A followup would be finding the elements $x_k$ that result in the top $k$ values of $f(x_k)$, in which case generating the entire set $R$ allows it to be ranked for any value $k$.
The most recent research I found on sparse polynomial multiplication is Roche's What Can (and Can’t) we Do with Sparse Polynomials? (2018) [2], which continues from Johnson's work and notes that there hasn't been any significant change in this problem since the idea of using a heap.
[1]: http://www.cecm.sfu.ca/~mmonagan/teaching/TopicsinCA11/johnson.pdf
[2]: https://arxiv.org/pdf/1807.08289.pdf

Unless you have some further structure to the problem (i.e., the function) you can't do better than  checking all.


Looking for an "intuitive" regular expression for $\{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}$ Let $L \subseteq \Sigma^{\ast}$ with $\Sigma = \{0,1\}$ be the language such that two times the number of $1$'s in a word in $L$ plus the number of $0$'s is divisible by $3$, i.e. if we denote by $|w|_1$ the number the symbol $1$ occurs in $w$ and by $|w|_0$ the number the symbols $0$ occurs, then
$$
 L = \{ w \in \Sigma^{\ast} \mid 2|w|_1 + |w|_0 \equiv 0 \pmod{3} \}.
$$
I know this language to be regular, as it is quite easy to give an automaton for it. I also got a (quite complicated) regular expression for it using an algorithm going from the automaton. But is there any regular expression that is easy in the sense that it gives some insight into why it is a regular expression for the language?

Not that for example for the language $\{ w \mid |w|_0 \equiv 0 \pmod{3} \}$ it is quite easy to give a regular expression, it would be $1^{\ast}(01^{\ast}01^{\ast}01^{\ast})^{\ast}$, or for $\{ w \mid |w| \equiv 0 \pmod{3} \}$ as it would be $(\Sigma\Sigma\Sigma)^{\ast}$. But the above language somehow combines these conditions.

The automaton for that language is, as you say, extremely simple: it consists of a triangle, in which 0s move clockwise and 1s move counterclockwise:

A classic way to turn this into a regular expression is to eliminate states one at a time, converting transitions through each state into regular expressions. Eliminating state 2 is easy since there are no epsilon transitions or self-loops, so we end up with:

$$\begin{align}s0 \to s0&: 10 \\
s0 \to s1&: 0 + 11 \\
s1 \to s0&: 1 + 00 \\
s1 \to s1&: 01 \\
\end{align}$$

When we then eliminate state 1, we produce a relatively simple regular expression:

$$(10 + (0+11)(01)^*(1+00))^*$$

Is that regex intuitive? I guess that depends on your intuitions. $10$ and $01$ both have no effect on $2|w|_1 + |w|_0 \pmod{3}$; $0+11$ adds 1, and $1+00$ subtracts 1. So the regex definitely shows the path around the three possible values of $2|w|_1 + |w|_0 \pmod{3}$


Why arrival process of packets at a switch is not a Poisson Process? "Packet arrivals are not Poisson
.... but some events are, such as web requests and new flow arrivals"
I know since the network traffic is very bursty, they are not Poisson.
But I am unable to understand what "new flow arrivals" mean here and
how web requests and new flow arrivals can be considered as Poisson processes.

"new flow arrivals" means "arrivals of new flows".  A flow is a TCP connection (roughly); each individual TCP connection is a separate "flow".  So, this is talking about new TCP connections, and the rate/time at which the server receives new TCP connections.

Contrarily to the statement you quoted, web requests won't necessarily be Poisson.  There are many factors that can cause web requests to be other-than-Poisson-distributed.  For instance, the Olympics web site receives a lot more traffic when the Olympics events are happening than when they aren't.  Many web sites receive more traffic during the time of day when their primary user population is awake than when they're not.  In addition, visiting one page on a site typically triggers many requests for other related resources (e.g., images that are loaded on that page).

However, during any sufficiently short time period, if their user base is sufficiently large, the arrival process for a particular type of web request might well be approximately Poisson.

See, e.g., https://en.wikipedia.org/wiki/Poisson_distribution#Occurrence.