What is the right data structure for MST in a stream In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:
H ← ∅
for each (u,v) in the stream
    H ← (u, v)
    if H includes a cycle
            remove largest weight edge in the cycle

To make this fast we need a data structure that allows you to check if (u,v) makes a cycle and also allows you to remove the largest weight edge from a cycle.
What is a suitable data structure for this?

By  noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens,
you can use a ST-Tree[1],  which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $a$ to $b$"
Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find).
If they are not, you add it as possible. Otherwise, if its weight is smaller than $max( a \to b)$, you replace with $(a,b)$ the max. weight edge.
[1]https://en.wikipedia.org/wiki/Link/cut_tree


What does "local" mean? I study graph theory on my own using Diestel's Graph Theory book (with Algorithmic graph theory in mind). I don't understand what local property, global property, locality mean given a graph $G$.

For example, on the page 5 it says

  The average degree quantifies globally what is measured locally by the
  vertex degrees: the number of edges of $G$ per vertex. Sometimes it will
  be convenient to express this ratio directly, as $\varepsilon(G) := |E|/|V|$.

In particular, I found the following phrases including the word local...

local information (pg. 46)
maximum local density (pg. 61)
the above local structures (pg. 101)
locally looks like a tree (pg. 110)
there is a local reason for it (pg. 110)
we are looking for local implications of global assumptions (pg. 181).

and many more...

Could someone explain (possibly with examples) what these local and global mean in the context of the graph theory?

Local property - a property that relates to a specific vertex and its near neighbors. For example, the number of neighbors or 2nd order neighbors a vertex $v$ has. "locally looks like a tree" more formally could be written as the sub-graph of vertices with distance $k$ or less of the vertex $v$ is a tree.

Global property - a property that relates to the graph, like its diameter, average degree, number of connected components or even its size.


Optimization version of decision problems It is known that each optimization/search problem has an equivalent decision problem. For example the shortest path problem

  optimization/search version:
  Given an undirected unweighted graph $G = (V, E)$ and two vertices $v,u\in V$, find a shortest path between $v$ and $u$.
  decision version:
  Given an undirected unweighted graph $G = (V, E)$, two vertices $v,u\in V$, and a non-negative integer $k$, is there a path in $G$ between $u$ and $v$ whose length is at most $k$?

In general, "Find $x^*\in X$ s.t. $f(x^*) = \min\{f(x)\mid x\in X\}$!" becomes "Is there $x\in X$ s.t. $f(x) \leq k$?".

But is the reverse also true, i.e. is there an equivalent optimization problem for every decision problem? If not, what is an example of a decision problem that has no equivalent optimization problem?

As already stated in the comments, it depends on the definitions, as usual. My attempt to answer this needs quite a few definitions, so this will be another example of my inability to give concise answers.

Definition: An optimization problem is a tuple $(X,F,Z,\odot)$ with

$X$ the set of suitably encoded (strings) instances or inputs.
$F$ is a function that maps each instance $x\in X$ to a set $F(x)$ of feasible solutions of $x$.
$Z$ is the objective function that maps each pair $(x, y)$, where $x \in X$ and $y\in F(x)$, to a real number $Z(x, y)$ called the value of $y$.
$\odot$ is the optimization direction, either $\min$ or $\max$.

Definition: An optimal solution of an instance $x\in X$ of an optimization problem $P_O$ is a feasible solution $y\in F(x)$ for which $Z(x, y)=\odot\{Z(x, y')\mid y'\in F(x)\}$. The value of an optimal solution is denoted with $Opt(x)$ and called the optimum.
Definition: The evaluation problem, denoted $P_E$, corresponding to the optimization problem $P_O$ is the following: Given an instance $x\in X$, compute $Opt(x)$ if $x$ has an optimal solution and output “no optimal solution” otherwise.
Note that this just asks for the value of the optimal solution not the whole solution itself with all its details.
Definition: The decision problem, denoted $P_D$ corresponding to the optimization problem $P_O$ is the following: Given a pair $(x, k)$, where $x\in X$ and $k\in\mathbb{Q}$, decide whether $x$ has a feasible solution $y$ such that $Z(x, y)\le k$ if $\odot=\min$ and such that $Z(x, y)\ge k$ if $\odot=\max$.
A first observation is now that $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$. The proof is not difficult and omitted here.
Now intuitively $P_E$ and $P_D$ corresponding to $P_O$ are not more difficult than $P_O$ itself. To express this feeling formally (thereby defining what equivalent is supposed to mean) we will use reductions.
Recall that a language $L_1$ is polynomial-time reducible to another language $L_2$ if there is a function $f$, computable in polynomial time, such that for all words $x$, $x\in L_1\Leftrightarrow f(x)\in L_2$. This kind of reducibility is known as Karp or many-to-one reducibility, and if $L_1$  is reducible to $L_2$ in this manner, we express this by writing $L_1\le_m L_2$. This is a central concept in the definition of NP-completness.
Unfortunately, many-to-one reductions go between languages and it is not clear how to employ them in the context of optimization problems. Therefore we need to consider a different kind of reducibility, Turing reducibility. First we need this:
Definition: An oracle for a problem $P$ is a (hypothetical) subroutine that can solve instances of $P$ in constant time.
Definition: A problem $P_1$ is polynomial-time Turing-reducible to a problem $P_2$, written $P_1\le_T P_2$, if instances of $P_1$ can be solved in polynomial time by an algorithm with access to an oracle for $P_2$.
Informally, just as with $\le_m$, the relation $P_1\le_T P_2$ expresses, that $P_1$ is no more difficult than $P_2$. It is also easy to see that if $P_2$ can be solved in polynomial time, so can $P_1$. Again $\le_T$ is a transitive relation. The following fact is obvious:
Let $P_O\in \mathrm{NPO}$, then $P_D\le_T P_E\le_T P_O$.
Because given the full solution, computing its value and deciding whether it meets the bound $k$ is simple.
Definition: If for two problems $P_1$ and $P_2$ both relations $P_1\le_T P_2$, $P_2\le P_1$ hold, we write $P_1\equiv_T P_2$; our notion of equivalence.
We are now ready to proof that $P_D\equiv_T P_E$ given the corresponding optimization problem is $P_O\in \mathrm{NPO}$ and $Z$ is integer valued. We have to show that $P_E \le_T P_D$ holds. We can determine $\odot\{Z(x,y)\mid y\in F(x)\}$ with a binary search usign the orcale for $P_D$. The definition of $\mathrm{NPO}$ ensures that $|Z(x, y)|\le 2^{q(|x|)}$ for some polynomial $q$, so the number of steps in the binary search is polynomial in $|x|$. $\Box$
For an optimization problem $P_O$ the relation to $P_E$ is less clear. In many concrete cases, one can show directly that $P_D\equiv_T P_E \equiv_T P_O$. To prove that this holds generally within the framework given here we need an additional assumption.
First we need to extend $\le_m$ from pairs of languages to pairs of the corresponding  decision problems. Then it is easy to see that $\le_T$ is more general than $\le_m$.
Let $P$ and $P'$ be decision problems; then $P\le_m P' \Rightarrow P\le_T P'$. This holds because a many-to-one reduction can be interpreted as making use of an oracle in a very restricted way: The oracle is called once, at the very end, and its result is also returned as the overall result. $\Box$
Now we are ready for the finale:
Let $P_O\in \mathrm{NPO}$ and suppose $Z$ is integer-valued and that $P_D$ is NP-complete, then $$P_D\equiv_T P_E \equiv_T P_O.$$ With the previous observations it remains to show $P_O\le_T P_E$. To do this we will exhibit a problem $P_O'\in \mathrm{NPO}$ such that $P_O\le_T P_E'$. Then we have $$P_O\le_T P_E' \le_T P_D'\le_T P_D\le_T P_E.$$ The second and third $\le_T$ hold because of the equivalence of the decision and evaluation version proofed earlier. The third $\le_T$ follows from the NP-completness of $P_D$ and the two facts mentioned before, namely $P_O\in \mathrm{NPO} \Rightarrow P_D\in \mathrm{NP}$ and $P\le_m P_O' \Rightarrow P\le_T P_O'$.
Now the details: Assume that the feasible solutions of $P_O$ are encoded using an alphabet $\Sigma$ equipped with a total order. Let $w_0, w_1, \ldots$ be the words from $\Sigma^*$ listed in order of nondecreasing length and lexicographic order within the blocks of words with common length. (Thus $w_0$ is the empty word.)  For all $y\in\Sigma^*$ let $\sigma(y)$ denote the unique integer $i$ such that $y=w_i$. Both $\sigma$ and $\sigma^{-1}$ can be computed in polynomial time. Let $q$ be a polynomial such that for all $x\in X$ and all $y\in F(x)$ we have $\sigma(y)<2^{q(|x|)}$.
Now the problem $P_O'$ is identical to $P_O$ except for a modified objective function $Z'$. For $x\in X$ and $y\in F(x)$ we take $Z'(x, y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$.  $Z'$ is computable in polynomial time thus $P_O'\in \mathrm{NPO}$.
To show that $P_O\le_T P_E'$ we observe that $x$ is feasible for $P_O$ if and only if it is feasible for $P_E'$. We can assume that this is the case, since the opposite case is trivial to handle.
The substituion of $Z'$ for $Z$ is monotonic in the sense that for all $y_1, y_2\in F(x)$, if $Z(x, y_1)<Z(x, y_2)$ then $Z'(x, y_1)<Z'(x, y_2)$. This implies that every optimal solution for $x$ in $P_O'$ is an optimal solution of $x$ in $P_O$. Thus our task reduces to the computation of an optimal solution $y$ of $x$ in $P_O'$.
Querying the oracle for $P_E'$ we can get the value of $Z'(x,y)=2^{q(|x|)}\cdot Z(x,y)+\sigma(y)$. Forming the remainder of this number modulo $2^{q(|x|)}$ yields $\sigma(y)$ from which $y$ can be computed in polynomial time.


Counting permutations whose elements are not exactly their index ± 1 This is a special case of the question:
Counting permutations whose elements are not exactly their index ± M

The $M=0$ case has already been solved, but no one was sure how to work out the non-zero cases.

So I decided to try to just brute force some values and search the results for a recursion relation.  As a test I first tried $M=0$ and searched for recursion relations that looked like:
$$ a_n = \sum_{1\le i \le k} (A_i n + B_i) a_{n-i} $$
where $k$ is some cutoff of how far back to search, $A_i \in \{-1,0,1\}$ and $B_i$ some small integers.  It was correctly able to find:
$$a_n= (n-1)a_{n-1} +(n-1)a_{n-2}$$

So I then tried for $M=1$ and found:
$$ a_n= (n) a_{n-1} +(-n+2) a_{n-3} + (-1)a_{n-4} $$

It's possible it's just a coincidence, but I ran a brute force approach to calculating the $M=1$ cases overnight to get a couple more values and it still holds. But even with this potential answer in hand, I cannot figure out a reason this recursion would hold.

Is there a simple combinatoric argument I'm missing here?

Checkout Derangements

"Suppose that there are n people who are numbered 1, 2, ..., n. Let there be n hats also numbered 1, 2, ..., n. We have to find the number of ways in which no one gets the hat having same number as their number."

In applying this to your problem, there would be two hats: the element's index +1, the elements index -1.

I'm not certain this solves the problem, but it seems like a step in the right direction.


What programming language should I use to run physics simulations of CO2 being absorbed by different materials? I want to model the absorption of CO2 with multiple different materials such as cement, limestone, wood, etc? I know Matlab is capable of these types of physics simulation according to this research paper: Research Paper, however, I am not sure if Python or another programming language could complete this task easier.

That depends on a lot of factors, mostly on available software for the task (you don't want to do the whole job yourself, if it is already done, or there are pieces you can combine with little effort, use that), in second line on how detailed your model (and it's computing requirements) is might force the use of inconvenient but efficient languages/packages.
This is probably a question better asked elsewhere, perhaps on a physics or chemistry forum (for the modelling aspects, and possibly for software alternatives in common use), or (given much more detailed requirements and specifications) on a forum on programming.


Examples of an I/O interface In computer architecture class, my lecturer was explaining about I/O interfaces and modules, but somehow neither me nor my classmates understood almost a word he said.. We still don't get which parts of a computer is an I/O interface.
For example, which one of these are an I/O interface? A VGA card or PCI Express?

I would use the term I/O interface to refer to the set of CPU instructions that one uses to read and write data from or to an I/O device.  There are generally two parts to this.

One is the interrupt mechanism, by which I/O devices can communicate asynchronous information to the CPU.  Generally there is a pin, or several pins, on the CPU chip package that can be used to trigger an interrupt.  Triggering an external interrupt on most CPU architectures will cause the processor to save some (or all) of its register state and jump to a predetermined location to run the interrupt service routine.  (On some architectures there is a way of triggering different interrupt routines for different purposes, while on others there is a single external interrupt routine and there needs to be additional communication done in the interrupt service routine to figure out which device needed service.)

The second part is the way that data gets communicated back and forth between the CPU and the I/O device.  This is generally done one of two different ways: memory mapped or "port mapped".  In memory mapped I/O the registers on the I/O device are mapped to particular locations in the CPU's memory space, and the CPU uses normal load and store instructions to read and write those registers.  In port mapped I/O the registers on the I/O device are mapped to particular locations in something called "port space."  The instructions you use to access the I/O device's registers are often called something like in and out, but they are pretty similar to load and store instructions.  There are other possibilities that get more complicated, but I've probably already given you more detail than you want.

For every specific device there is then some set of device registers that need to be read and/or written with specific values in some specific order. The protocols for what you need to read/write in which registers can get exceedingly complex.

To make this clearer let me give you an example.  Let's take the PC keyboard (from the old days before we had USB).  Here is the first thing that came up when I googled: http://www.oopweb.com/Assembly/Documents/ArtOfAssembly/Volume/Chapter_20/CH20-2.html#HEADING2-1.  The keyboard controller has two 8-bit registers mapped to port addresses 60h and 64h (hexadecmial).  You read these registers using inb and outb instructions which moves data between the ports and the CPU registers.

The keyboard will additionally cause an interrupt to interrupt number 9 (out of 255) every time a key is pressed or released.  So the interrupt service routine associated with interrupt 9 reads port 64h and looks at bit 1 to see if there is a data byte ready. If there is it reads the byte out of port 60h and copies it into some memory buffer for software to read later.  (The reason you do the test is that several different hardware devices may be sharing the interrupt.)


Prove the upper bound on $T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$ I need some help with the following recursion:

$T\left(n\right)=T\left(\log_{2}n\right)+O\left(\sqrt{n}\right)$

More specifically I wish to find and prove the upper bound on it.

I have a hunch it is $O\left(\sqrt{n}\right)$ but have gotten stuck proving it really is this.

Any help is appreciated

Thank you!

By simple substitution, you can see that $T(n) = O(\sqrt{n}) + O(\sqrt{\log n}) + O(\sqrt{\log\log n}) + \dots = O(\sqrt{n})$.


Search for numerical solutions of underdetermined systems of quadratic equations I'm looking for an algorithm that can quickly generate an approximate real number solutions of an underdetermined quadratic system. My task is to explore its algebraic variety. I'm interested in a special cases of quadratic systems that arise from mechanics:

set of variables $X = \{ x_i, y_i, z_i | 1 \leqslant i \leqslant N\}$ (3*N variables for $N \in \mathbb{N}$),

a system consists of two kinds of equations:

1) $(x_i-x_j)^2+(y_i-y_j)^2+(z_i-z_j)^2 + p_{ij} = 0$ for $i, j \in [1,N]$ and $p_{ij} \in \mathbb{R}$.

2) a more general case of 1: $(x_i-x_k)(x_j-x_k)+(y_i-y_k)(y_j-y_k)+(z_i-z_k)(z_j-z_k) + a_{ijk} = 0 $ for $i, j, k \in [1,N]$ and $a_{ijk} \in \mathbb{R}$.

It's guaranteed that variety of solutions is stable under small changes of coefficients.
Here is an example with six-dimensional variety of solutions:

(x1-x2)^2 + (y1-y2)^2 + (z1-z2)^2 - 1 = 0
(x3-x2)^2 + (y3-y2)^2 + (z3-z2)^2 - 1 = 0
(x3-x4)^2 + (y3-y4)^2 + (z3-z4)^2 - 1 = 0
(x1-x4)^2 + (y1-y4)^2 + (z1-z4)^2 - 1 = 0
(x2-x1)*(x4-x1) + (y2-y1)*(y4-y1) + (z2-z1)*(z4-z1) - 1/3 = 0
(x1-x2)*(x3-x2) + (y1-y2)*(y3-y2) + (z1-z2)*(z3-z2) - 1/3 = 0
(x2-x3)*(x4-x3) + (y2-y3)*(y4-y3) + (z2-z3)*(z4-z3) - 1/3 = 0
(x1-x4)*(x3-x4) + (y1-y4)*(y3-y4) + (z1-z4)*(z3-z4) - 1/3 = 0

First, the algorithm is allowed to process this underdetermined system for some time. After that, it should get as input a set of constraints, like $x_1 = 0$ or $z_N = 1$, that turn the system into determined and quickly generate real solutions of it. For instance, one can find 8 real solutions of the system above after constraining all of $\{x_4,y_4,z_4,y_3,z_3,z_2\}$ to zero.
I need the algorithm to be scalable so it can be applied for N=25-30, however high precision of solutions isn't required, 3-4 orders will do.

I've come up with a few approaches:

I tried to calculate Gröbner bases for such systems in Magma:

    P< x1,y1,z1,... > := PolynomialRing(RationalField(),3*N);
    I := ideal<P | my equations >;
    Groebner(I);

It works for zero-dimensional ideals, but coefficients were big even for N=7. In cases with dimensions >0, calculation took too long (with enough RAM) and I have been able to compute Gröbner bases only for small systems.
So I tried compute approximate Gröbner bases by running OpenF4 algorithm with datatype of coefficients changed on double, but the error grew significantly on each step of the computation.

Also I consider a calculation of Gröbner basis in grevlex order with subsequent transformation to lexicographic using FGLM-like algorithm.
I found this article https://arxiv.org/abs/1703.07810 and this looks useful for my purpose. I'm not familiar with such methods, but probably this is exactly what I need.

Here are my questions:

Is there a way to calculate an approximate Gröbner bases in reasonable time using my idea or any other approach, maybe for other order with subsequent transformation to lexicographic?

Can this problem be solved without Gröbner bases using methods like №3 or any other?

Any comments on my ideas and new suggestions would be highly appreciated.

This is a bit late for you, perhaps, but it might be worth looking at cylindrical algebraic decomposition. CAD takes a general statement in the real closed fields (i.e. an arbitrary boolean statement involving equalities and inequalities), and returns a finite set of "solutions", each of which is a "procedure" to find those solutions by assigning the unknown variables.

I haven't tried it on your example (because I don't have any software handy to do it!), but as an example, here is the CAD of $x^2 + y^2 = 1$:

$-1 < x < 1\,\wedge\,y = \sqrt{1-x^2}$
$-1 < x < 1\,\wedge\,y = -\sqrt{1-x^2}$
$x = -1\,\wedge\,y = 0$
$x = 1\,\wedge\,y = 0$

There are four "solutions" in this decomposition, and each one gives you a way to find it, by first determining an assignment to $x$, and using that to get an assignment to $y$.

This would work extremely well if you knew which variables were going to be constrained, because you could specify that they appear first in each "solution". In this case, if you added the constraint that $x = 0$, you would just go through each solution and find that $y=1$ and $y=-1$ are the only solutions, since the last two don't apply.


Can a cycle be represented by L1 metric? Let G be a graph that forms a cycle on $n$ vertices, with non-negative weights on the edges.
Can you give each vertex v a vector $\mathbb{R}^m$ (for some $m\in \mathbb N^+$) such that the L1 distance (taxicab distance) between two vectors is the same as the distance between them in $G$?

Prove for a general circular graph or give a counter example with proof.

(I was told it is true so I have a good reason to think it is but I can't prove it.)

Firstly for a fixed $n$, consider a path around the hypercube which is $$P_n=(0,0,\dots,0)\to(1,0,\dots,0)\to(1,1,0,\dots,0)\to\dots\to(1,1,\dots,1)\to(0,1,\dots,1)\to\dots\to(0,0,\dots,0,1)\to(0,0,\dots,0).$$ Notice that if I give you two points $p,q\in P_n$, then the $L_1$-distance between $p$ and $q$ is exactly the distance between $p$ and $q$ in $P_n$ (the shortest distance, not necessarily following the arrows in $P_n$). Now, suppose we're given a cycle $C_n$ with all edge weights $w_e\in\mathbb{Z}^+$ and $w=\sum_e w_e$ is even. We will do the following: Let $p_1=0$ and $p_i=p_{i-1}+w_{i-1,i}$, so $p_i$ is the weight of the path in $C_n$ from vertex $1$ to vertex $i$ going clockwise. Label the vectors on $P_{w/2}$ starting with $(0,0,\dots,0)$ having label $0$ and going around and map vertex $i$ of $C_n$ to the $p_i$'th vector in $P_{w/2}$. By the previous comment, this is an $L_1$-embedding.

Now, if each $w_e$ is rational, we can find some $M$ for which $Mw_e\in\mathbb{Z}$ for all $e$ and $M\sum_e w_e$ is even, so we can use the previous embedding and then scale.

Now for the irrationals.

Now, for a finite set $V$ and a subset $S\subseteq V$, we define the metric $\mu_S$ on $V$ by $\mu_S(x,x)=0$ and $\mu_S(x,y)=\mathbf{1}[|S\cap\{x,y\}|=1]$ if $x\neq y$. It is not difficult to prove that any metric of the form $\mu=\sum_{S\subseteq V}c_S\mu_S$ is $L_1$-embeddable for any $c_S\geq 0$. I claim that, in fact, if $V$ is any finite subset of $L_1^n$, then there are constants $c_S\geq 0$ for which $\Vert x-y\Vert_1=\sum_{S\subseteq V}c_s\mu_S(x,y)$ for every $x,y\in V$. First, if $V\subseteq L_1^1$, then write the points $V=\{v_1\leq v_2\leq\dots\leq v_k\}$. Then we have
$$
\Vert x-y\Vert_1=\sum_{r=1}^k\Vert v_{r+1}-v_r\Vert_1\mu_{\{v_1,\dots,v_r\}}(x,y),$$ for any $x,y\in V$. For a general $V\subseteq L_1^n$, we can do this construction in each coordinate direction $e_i$ for $i\in[n]$ since the $L_1$ metric is additive over the coordinates. Thus, if $\mu$ is a metric on a finite set $V$, then $\mu$ is $L_1$-embeddable if and only if $\mu=\sum_{S\subseteq V}c_S\mu_S$ for some constants $c_S\geq 0$.

Now, suppose that some edge-weights are irrational, so suppose $w_e^{(k)}$ are rational numbers with $w_e^{(k)}\to w_e$. Let $\mu^{(k)}$ be the metric induced by the weights $w_e^{(k)}$. By above, we know that each $\mu^{(k)}$ is $L_1$-embeddable, so we can write $\mu^{(k)}=\sum_{S\subseteq V}c_S^{(k)}\mu_S$. By compactness, without loss, we may suppose $c_S^{(k)}\to c_S$. Finally, since $\mu^{(k)}\to\mu$, we must have $\mu=\sum_{S\subseteq V}c_S\mu_S$, so $\mu$ must be $L_1$-embeddable.


Graphs that cause DFS and BFS to process nodes in the exact same order For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-shaped (trees of depth $1$ with an arbitrary number of children). Is there some way for categorizing graphs that satisfy this property?

Assume our BFS and DFS have the rule to start from a specific node and both of them then visit the node with the lowest degree:

Start from left most black node, then both (BFS and DFS) traversals will visit left most red node, then they will visit next black node, and so on. To make it more general, you could add some paths in between triangles, or add star after finishing triangles.


Shortest Path Variant (constrained max hop) INPUT: directed non negative weighted graph, s, t, k

OUTPUT: SSSP from s to t where the path has $\leq k$ vertices

MY PROGRESS:

heap.add(s,0) where s is vertex and 0 is weight and heap is minheap
depth[s] = 1;
do
  c = heap.poll();
  SSSP[c] = c.weight
  if(depth[c] >= k) continue loop;
  for v in c's adjacent vertices
    if SSSP[v] is infinite
      heap.add(v, SSSP[c] + weight c to v)
      depth[v] = depth[c] + 1;
    else if getHeapNode(v).weight > SSSP[c] + weight c to v
      getHeapNode(v).weight = SSSP[c] + weight c to v
      heapify/shiftup
      depth[v] = depth[c] + 1;
while(!heap.isEmpty())

ans = SSSP[t];

Here is my approach and it doesn't work because I think there can be a case where a vertex that has been polled from the heap that exceeds $k$ when later is revisted by a longer (greater weight) path BUT at depth $\leq k-2$. This means that the neighbour of the polled vertex is reachable by the slower path but is not computable as the vertex has already been polled. I don't think this is the only criteria for max-k hops constrained shortest path. How should i go about doing this?

The "best" way to solve your problem is by dynamic programming. This will give you a running time of O(knMaxDegree).

The program is almost identical to the one for the knapsack. The basic idea is that you create a space (node, remaining hops), start at the destination (s,k) and then visit the neighbours of s, and so on.

For a deeper explanation, this problem is known as Constrained Shortest Path.


Closure under intersection of context free binary trees Some sets of ordered binary trees can be represented as a CFG with rules of the form

A -> aBC
A -> b

Where A,B,C are nonterminals and a and b are terminals representing internal nodes and leaf nodes respectively. The tree can be recovered from any word in the language by a preorder traversal.

The set of all such grammars forms a class of languages which is a subset of context free languages but isomorphic to a superset of regular languages (by unary encoding the alphabet and adding a dummy terminal for the second nonterminal in every production). It is obviously closed under union as you can simply concatenate the lists of productions to get a new tree grammar.

My question is whether this class is closed under intersection. I have been unable to prove that is either closed or not closed, and I figured I should see if anyone else can see how to do this.

If I correctly read your question there are two types of terminal symbols, disjoint sets for internal labels and leaf labels. In that way the structure of the tree is uniquely determined by the string.

Then your formalism is known as regular tree grammars. A production $A \to a BC$ seems to label a tree node by $a$ while attaching children $B$ and $C$. This formalism is closed under intersection. This can be proved precisely as for finite state automata or right-linear grammars. Simulate the two in parallel, as a product construction. With productions $A \to_1 a BC$ and $P\to_2 a QR$ we join them to $(A,P) \to a (B,Q)(C,R)$ and $A \to_1 a$ and $P\to_2 a$ are joined to $(A,P)\to a$.


Can the Same Function Have Different Asymptotic? Say we had a function $4^k$.

The asymptotic of this function would be $\Theta(4^k)$, and thus we would say the function has exponential run-time.

But what if $k = \log{n}$? Then our same function would be $4^k = 4^{\log{n}} = n^{\log{4}} \in \Theta(n^{\log{4}})$.

(Step 2 to 3 is accomplished via a change of logarithm base).

Would we now say the function runs in polynomial time?

Or something more nuanced, like

“The function is exponential in respect to k, and polynomial in respect to n”?

The asymptotic behaviour of a function always depends on the parameter in the function. So for your example, I'd say that claiming that the function is exponential w.r.t. $k$, but polynomial w.r.t. to $n$ is correct.

When we look at the running time of algorithms, we consider it to be a function of the size of the input (usually the number of bits in a binary encoding). So, for an algorithm, it is always well defined whether it is for instance polynomial or not, but this can depend on how you define or encode your input.


What is the implication of NP-completeness if P=NP? If a certain problem $X$ is NP-complete and $P\neq NP$, then $X$ is not polynomial. But we still don't know that $P\neq NP$, so in theory $X$ may be polynomial. Does the fact that $X$ is NP-complete say anything about it being more difficult than other polynomial problems? In particular:

Does it mean that $X$ cannot be solved in linear time? (alternatively, are there NP-complete problems that can be solved in linear time if $P=NP$)?
Does it mean that $X$ cannot be solved in quadratic time? (alternatively, are there NP-complete problems that can be solved in quadratic time if $P=NP$)?
If $X$ is NP-complete, and I prove a lower bound of $\Omega(n^2)$ on the run time of $X$ (a lower bound that does not depend on whether $P=NP$), did I prove anything new?

Yes, but without further information, only that $X$ has a lower bound of $\Omega(n^{2})$. (I'm assuming that, in line with the title, you're interested in what happens if it turns out that $P=NP$) The problem with transferring this information elsewhere is with the reductions used. As the only constraint is that they're computable in polynomial time, we can easily have the case that we simply solve the problem as part of the reduction (again assuming $P=NP$), so we can reduce it to any other problem in $P$ (this is why $P$-completeness is defined using more restrictive reductions - $NC$ reductions or logspace reductions, or similar, depending on exactly what version you're going for).

With some more specific information we can say something. If we have a problem $W$ where $X \leq_{P} W$ and we can compute the reduction in $O(n^{c})$ where $c < 2$, then we know that $W$ has a lower bound of $\Omega(n^{2/c})$ essentially because an upper bound on the problem tells us something. Say $A$ has an upper bound of $O(n^{c_1})$ for some $c_1$, we have a problem $B$ such that $B \leq_{P} A$ and we can compute this reduction in $O(n^{c_{2}})$, then $B$ has, at worst, a $O(n^{c_{1}c_{2}})$ algorithm - at worst we can convert the instance of $B$ to an instance of $A$ and solve that instead. So in our case, if $W$ had an upper bound of $O(n^{2/c - \varepsilon})$ for any $\varepsilon > 0$, then $X$ could be solved in $O(n^{c\cdot (2/c - \varepsilon)}) = O(n^{2-c\varepsilon})$, contradicting the lower bound.

Note of course that none of this really has anything to do with $X$ being $NP$-complete, it's true for any problem in $P$.


What does Θ(1) memory mean? I have the definition of an in-situ algorithm from the professor, but I don't understand it.

  In-situ algorithms refer to algorithms that operate with Θ(1) memory.

What does that mean?

First, let's unpack what $\Theta(1)$ means.

Big $O$, and big $\Theta$, are classes of functions. There's a formal definition here, but for the purposes of this question, we say that a function $f$ is in $O(1)$ if there's a constant $c$ where, for all $x$, $f(x) \leq C$. That is, $f$ grows at most as fast as a constant function.

Big-$\Theta$ doesn't mean much for constant functions, because when describing algorithm time or space usage, there isn't much below constant. But to explain what it means, $f \in \Theta(1)$ if there are some constants $c,d$ such that, for all $x$, $d \leq f(x) \leq c$. That is, $f$ grows at least as fast, and at most as fast, as a constant function.

Now what does this have to do with memory usage? Consider some algorithm $A$. There is some (mathematical) function which, given an input $n$, gives the maximum memory usage of your algorithm $A$ on any input of size $n$. Let's call this function $mem$.

So, now we combine our two concepts. If an algorithm uses $\Theta(1)$ memory, then its memory usage function is in $\Theta(1)$, meaning that there exists some $d,c$ such that, for any input, the memory used is between $d$ and $c$.

In short, this means that the memory usage of the algorithm is in some constant range, regardless of the input.

Usually, the memory function does not account for the memory used to store the input to the algorithm, since otherwise memory usage would always be at least $\Theta(n)$.


Chernoff bounds and Monte Carlo algorithms One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p > 1/2$. Basically, Chernoff bounds are used to bound the error probability of $A$ using repeated calls to $A$ and majority agreement.

I don't understand how, to be frank. It would be nice if somebody could break it down piece by piece. Moreover, does it matter whether $A$ is a decision algorithm or can return more values? How are Chernoff bounds in general used for Monte Carlo algorithms?

Let's suppose that we have a polynomial time randomized algorithm $A$ for a decision problem $\Pi$ with the property that
$$
\mathrm{Pr}[A \text{ is right}] > 1/2
$$
for all inputs.  (In particular, independent of the input length $n$.)

We can use Chernoff bounds to show something stronger, namely that for any fixed $c$, there is a polynomial time, randomized algorithm for $\Pi$ that is correct with probability at least $1-n^{-c}$.

The algorithm is very simple: On an input of length $n$, we run $A$ a polynomial number of times $N$ (to be determined below) and then report the majority answer.  Call this algorithm $A'$.

What we need is a bound on
$$
\mathrm{Pr}[A' \text{ is wrong}]
$$
in terms of the number of repetitions $N$.  The hypothesis about $A$ implies that there is an $\epsilon > 0$ such that
$$
\mathrm{Pr}[A \text{ is right}] \ge 1/2 + \epsilon
$$
Since the $N$ runs of $A$ are independent, for any $k\in [N]$ we have
$$
\mathrm{Pr}[k \text{ of } N \text{ runs of } A \text{ are right}]\ge Pr[X = k]
$$
where $X$ is a binomial random variable with parameters $N$ and $1/2+\epsilon$.  Since the algorithm $A'$ is wrong exactly when at most $N/2$ of the runs of $A$ are right, we obtain an upper bound on the failure probability by a "tail estimate" bounding
$$
\mathrm{Pr}[X \le N/2]
$$
This is a prototypical time to use a Chernoff bound, since a binomial r.v. is the sum of $N$ independent random variables.  One instance of the Chernoff bound says that if $Y$ is the sum of $N$ independent r.v.'s with support in $[0,1]$ and $t > 0$, then
$$
\mathrm{Pr}[Y < E[Y] - t] \le e^{-2t^2/N}
$$
Thus, since $E[X] = N/2 + N\epsilon$, we take $t = N\epsilon$ to obtain
$$
\mathrm{Pr}[A' \text{ is wrong}]\le e^{-2\epsilon^2 N}
$$
So we can take $N = (1/2)\epsilon^{-2}c\log n$, and we get the claimed error probability for $A'$.


What untyped term inhabits induction on natural numbers in CoC? Induction on Church-encoded natural numbers (which I will call indNat) can not be defined within the Calculus of Constructions.

If we assumed indNat as an axiom, is there an untyped term that would have the semantics of the induction function? What if we had Scott-encoded natural numbers and fix?

Can induction be inhabited in CoC + fix (such that the function would have the proper semantics, not an infinite loop)?

Yes, there is such an untyped function, and it turns out that it is equivalent to the untyped erasure of iteration for church numerals.

The Cedille project has been doing lots to give types to these functions, and the core concept there is the dependent intersection, which provides a limited form of self reference that is enough to derive induction principles.
This paper will probably interest you.

If you have $fix$ you can definitely implement induction principles, using structural recursion on the natural number. This is how they do it in CiC and Coq, with an extra restriction that the recursive calls must be on a structurally smaller value. Without this condition, you can write induction, but you also can write nonterminating terms with the same type as an induction principle.


Finding a minimal cover of a subset of a finite cartesian product by cartesian products Given a subset of a cartesian product $I \times J$ of two finite sets, I wish to find a minimal cover of it by sets which are cartesian products themselves.

For example, given a product between $I=\{A,B,C\}$ and $J=\{1,2,3\}$, I may observe the subset $\{(A,2), (B,3), (B,2)\}$ and try to cover it with a minimal number of cartesian products.

Two ways to do so are $\{A\} \times \{2\} + B \times \{2,3\}$ and $\{A,B\}\times \{2\} + \{B\}\times \{3\}$, both requiring 2 products. A sub-optimal solution may be breaking it into 3 trivial products.

Can such an optimal cover be found efficiently (e.g., in polynomial time)?

NM reformulates this problem in comments as finding minimum number of bipartite cliques (bi-cliques) that cover a bipartite graph. the two sets you mention are the 2 vertex sets of the bipartite graph. the cartesian products of subsets of the two vertex sets are bicliques. wikipedia states this is the bipartite dimension problem and is problem GT18 in Garey and Johnson, proved NP complete based on straightforward reformulation of set basis problem SP7.


Why we treat sentence letter $Q$ as conclusion in one form and premise in other? Sorry for asking such a dumb question.

I am CS student and I am trying to understand the basic tenets of Logic. I am new to the subject and I am lost understanding Implication.

In formal logic, $(P\rightarrow Q)$, The sentence letter $P$ is premise and $Q$ is conclusion, right?

Now, we know that $(P\rightarrow Q)$ is equivalent to $-(P\wedge -Q)$ i.e. It is not the case that $P$ and not $Q$. Here, $Q$ acts as premise, right?

So, why we treat sentence letter $Q$ as conclusion in form and premise in other?

I completely agree with others that the terms "premise" and "conclusion" don't apply to things that aren't implications. By analogy, in $P\land Q$, $P$ and $Q$ are called "conjuncts", but it would make no sense to ask what the conjuncts of $P\to Q$ are.

However, there is terminology that could make sense of the connection that is more commonly used in type theory than logic but is just as applicable to logic. We can talk about "positive" and "negative" positions. In $P\to Q$, the premise, $P$, is in negative position and the conclusion is in positive position. These senses "multiply" in that in $(R\to S)\to Q$, $S$ is in negative position, but $R$ is in positive position (because it's in a negative position within a formula that is itself in negative position). Since $\neg P\equiv (P\to \bot)$, ($\bot$ is the always false formula) negation effectively swaps negative and positive. In $P\land Q$ and $P\lor Q$, both positions are positive. (The general intuition is that propositions in positive positions are possibly asserted, while propositions in negative position are possibly being assumed. They might not actually be asserted/assumed, e.g. in $P\lor Q$.)

This positive/negative notion can be a quick sanity check for equivalences and can help guide proof search. (Negative propositions will likely need to be assumed at some point and positive ones proven. Also, particularly for purely logical theorems, you are often trying to bring negative and positive occurrences together, e.g. as in $P\to P$.) For your equivalence $$P\to Q \equiv \neg (P\land\neg Q)$$ we can see on the right-hand side that $P$ occurs in a positive position within a formula in negative position and so is negative, while $Q$ occurs in negative position within a formula in negative position and so is positive. This matches the left hand side.


supply a matching data structure that supports MakeEmpty, Insert and DeleteFreq I've been struggling with solving the following question:

Supply an ADT that stores members (not necessarily unique) and supports the following functionalities:
1) MakeEmpty - creates an empty data structure - complexity in time Θ(1) worst case
2) Insert - inserts a member into the data structure - complexity Θ(1) in average case
3) DeleteFreq - gets out the most frequent member from the data structure (the member exists the maximal number of times in the data structure) - time complexity Θ(log(n) in worst case

At the beginning I was thinking about using a hash table (because of the average time of Insert function) and the hash-table based on keys of the members. In addition, for each cell in the hash-table I thought about holding a pointer to AVL/2-3 Search Tree.

But then, I'm thinking it's possibly not correct because only hash-table initialization (all pointers to NULL) gonna cost Θ(hash-table-size). Furthermore, Insert function could be much more expensive if the load factor isn't good.

I would appreciate your advice and guiding

"""

This file is both Markdown and Python.

We keep the keys in two data structures. One is a
doubly-linked list, like this:

| <- [] <-> [] <-> [] <-> [] -> |

Here, [] is a node and | is None. Pointers are one-way
(->) or two-way (<->).

Instead of being terminated by null pointers, the list
will be terminated by nodes that point to themselves. An
empty list looks like this:

[o] <-> [o]

Here [o] is a node that points to itself. These nodes
are called "sentinals".

Nodes keep two other pieces of data. The first is a set of
keys. The second is a frequency, which represents the
number of times each of those keys is in the multiset. For
instance, If you insert a twice and b seven times and
c seven times, there is a node in the list with
frequency set to 7 and the set of keys {b, c}.

[o] <-> [7, {b,c}] <-> [3, {a}] <-> [o]

The other invariants that are maintained:

The nodes are stored in frequency order
The sentinal at the high-frequency end has frequency
None
The sentinal at the low-frequency end has frequency 0
No node has negative frequency
No two nodes have the same frequency
The sentinals have empty key sets, but no other nodes
have empty key sets

So:

"""
class FreqBucket(object):
  def __init__(self, lo, hi, freq):
    self.lo = lo
    self.hi = hi
    self.freq = freq
    self.kids = set()

  def __repr__(self):
    return ("FreqBucket({}, {}, {}, {})"
            .format(self.lo.freq, self.hi.freq,
                    self.freq, self.kids))

  def unlink(self, key):
    """Remove key and remove self from the list if necessary"""
    if key in self.kids: self.kids.remove(key)
    if not self.kids:
      self.hi.lo = self.lo
      self.lo.hi = self.hi

  def increase(self, key):
    """Increase the frequency of the given key from this node"""
    result = self.hi
    if self.hi.freq != self.freq + 1:
      # There is no FreqBucket with the right .freq, so we
      # must make a new one:
      old_hi = self.hi
      self.hi = FreqBucket(self, self.hi, self.freq + 1)
      old_hi.lo = self.hi
      result = self.hi
    # Move the key to the next FreqBucket:
    result.kids.add(key)
    self.unlink(key)
    return result
"""

TallPoppies uses the list of FreqBuckets described
above. It keeps a map in which each key in the structure
maps to its corresponding FreqBucket.

"""
class TallPoppies(object):
  def __init__(self):
    # The keys of the self.keys dictionary are the inserted
    # objects; the values are FreqBuckets.
    self.keys = {}
    # Make the sentinels and link them to each other and
    # themselves. We need mini for inserts and maxi for
    # deletes.
    self.mini = FreqBucket(None, None, 0)
    self.mini.lo = self.mini
    self.maxi = FreqBucket(None, None, None)
    self.maxi.lo = self.mini
    self.maxi.hi = self.maxi
    self.mini.hi = self.maxi

  def __repr__(self):
    return ("TallPoppies({}, {}, {})"
            .format(self.keys, self.mini, self.maxi))

  def insert(self, key):
    if key in self.keys:
      self.keys[key] = self.keys[key].increase(key)
    else:
      self.keys[key] = self.mini.increase(key)

  def delete_freq(self):
    result = self.maxi.lo.kids.pop()
    self.maxi.lo.unlink(result)
    del self.keys[result]
    return result

insert and delete_freq take expected amortized O(1) time. You need hash tables and linked lists, but not search trees.


Does the AND-compression of SAT depends on the number of SAT instances? From a paper

  An AND-compression is a deterministic polynomial-time algorithm that maps a set of SAT-instances $x_1,\dots,x_t$ to a single SAT-instance $y$ of size $poly(\max |x_i|)$ such that $y$ is satisfiable if and only if all $x_i$ are satisfiable.

My question is: Is $t$ treated as constant?

Another paper gives related definition, explicitly stating
that the strong AND compression must be independent of $t$.
.

Let me help you determine how you would answer your own question.

The way is to read the paper, and in particular, look at the theorems and the definitions of the notation and the assumptions.  Don't just read the abstract.  You have to read the whole paper.

For instance, you can look at Theorem 1.1, noticing the phrase "...for some $n$ and $t$..." -- to me, that suggests that $t$ is a constant in Theorem 1.

Or, you could look at Theorem 3.1, which explicitly mentions that $t$ is polynomial in $n$, where $n$ is the length of the SAT-instances, in the context of Theorem 3.1.

It's also often helpful to go back to the original paper that introduced the conjecture, and see how they formulated it.  In this case, you can learn (from reading the introduction to the paper you link to) that Bodlaender [2] was the originator of the conjecture, and Fortnow and Santhanam [3] proved the conjecture under a certain assumption.  The paper you link to (the Dell paper) might be assuming papers have read those prior work and are familiar with the technical details of the formulation of the conjecture.  So, go read those papers, too.

Bottom line: you can't stop at reading just the abstract or just the first sentence of the introduction.  You may have to dive into the details, and even into prior papers, to resolve questions like this.  These papers are written for other researchers (who are comfortable doing all that).


Methods to evaluate a system of written rules I was trying to come up with a system that would evaluate bylaws for an organization as to determine their underlying logic.

I think a first-order predicate system would work for representing the rules, which could be translated from the text via part-of-speech tagging and other NLP techniques.

Is there a systematic way to interpret the first-order logic rules as a whole, or some type of ML architecture that would work as a second layer to find similarities between the elements.

For example,

  List of fun activities:

  golf
  coffee break
  pizza

  Bylaws:

  On Friday, we play golf
  On Friday or Saturday, we take a quick coffee break, and if it's Saturday, we get pizza

Conclusion: our group has fun on weekends

It sounds far fetched, but I'm curious if it's possible.  I also realize that perhaps more first-order logic would be a better fit for driving the conclusions of the second layer.

The trick here is that this works well provided that your rules can be expressed in predicate form. Is golf still fun if it's raining, or if you play poorly?

If you need something more flexible, you might want to look at some statistical/Baysean tools. There, you'd say that golf had a high probability of being fun, not that it was always fun all the time ever.


What is the name of the data structure that is a tree on the backend but has a list like API? I'm looking for the name of a data structure.  It is organized like a balanced tree.  The elements need not be comparable.  Instead of asking if the tree contains a thing (like you would with a collection of comparables), you can query for any k'th element in logarithmic time.  You can insert before or after any k'th element.  So the API is a bit like a list, except all operations are logarithmic.

I think "rope" might be similar but those seem to be restricted to strings only.  It could be thought of as a segment tree, where every leaf has a weight of 1, but instead of storing the weights in the leaves the entry itself is stored.

Edit: I think it could also be referred to as an "Order Statistic Tree" but without the comparison operations.

In "Optimal  Algorithms for List Indexing and Subset Rank" by Paul F. Dietz this data structure is called an "indexed list" and an algorithm is given that has complexity $O(\log n / \log\log n)$ for all operations. Unfortunately this term has little value as a search term.

While that is complex data structure note that you can transform any self-balanced tree into the data structure you want. Just replace the key field of each node with a field that keeps track of the number of elements to the left of it, and update this on inserts/deletes (takes $O(\log n)$ time). Then use that field as your key when searching for element $i$ in the tree.

Also check out "tiered vectors".


How can I do a subtraction with a two tape Turing machine I have already made a Turing machine with just one tape that solves a subtraction between two numbers, but I trying to do the same but with TWO tapes.
As an example, how can I solve 4-2?
Taking account that 4 can be represented as 0000, 2 as 00 and the - as 1.
So, in this case the input will be 0000100.

Copy the second number (from the second tape) to the first tape, and then use the already existing TM that subtracts the numbers


Is Pattern Matching as expressive as Case Expression in Haskell? Nomenclature

The term expressive in the question shall bear the same meaning as in the following sentence:

  A Turing Machine is as expressive as Lambda Calculus.

Introduction

While learning Haskell, I had noticed that there are 2 ways to achieve the same effect, namely Pattern Matching and Case Expression. For example,

-- Pattern Matching
not True  = False
not False = True

-- Case Expression
not x = case x of True  -> False
                  False -> True

I am also fully aware that Pattern Matching is actually a form of syntax sugar that will be compiled into Case Expression.

Therefore, we can be very sure that every Pattern Matching expression can be converted to Case Expression.

Question

So, this is my question: Is the following statement true?

  Every Case Expression can be re-written using Pattern Matching.

Regardless of the truthiness of the statement above, I would be glad if you could provide a formal proof to support your answer.

P/S

The motivation that drove me to seek answer for this question is because I'm currently designing my own language, which I wish to have as less feature as possible, but not too minimal like Lambda Calculus which only have 3 features.

The expression

case e of
  p1 -> e1
  p2 -> e2
  ...

can be rewritten as

let k p1 = e1
    k p2 = e2
    ...
 in k e

where k is a fresh identifier.

This translation assumes that the language has some way to define a local function by pattern matching (e.g. let).

If local functions can not be defined, there's always the possibility of lifting the definition to the top level. Indeed, any local definition

let f x1 ... xk = e in e'

having free variables v1 .. vn can be rewritten written as

(\f -> e') (globalF v1 ... vn)

provided that we also define a global function

globalF v1 ... vn x1 ... xk = e

Note that globalF has no free variables, by construction. I believe it is sometimes called a "supercombinator".

This naturally extends to the case where x1 ... xk are patterns, and we have multiple defining equations for f / globalF.

For example,

case x of True  -> False
          False -> True

cab be rewritten as

let f True  = False
    f False = True
 in f x


Removing epsilon transition from the grammar. What's the difference between accepting languages? I want to remove the epsilon transition from following grammar:
\begin{eqnarray}
S & \rightarrow & A | B \\
A & \rightarrow & \epsilon \\
B & \rightarrow &  aBa \\
B & \rightarrow & b \\
\end{eqnarray}
This is the result of removing $\epsilon$ transition:
\begin{eqnarray}
S & \rightarrow & \epsilon | B \\
B & \rightarrow & aBa \\
B & \rightarrow & b
\end{eqnarray}

My question is what's the difference between languages that accept these two grammars?

There is no difference. Both grammars describe the same language $$L = \{ \epsilon \} \cup \{ a^nba^n  | \forall n > 0\}.$$


Reduction of graph chromatic number to hypergraph 2-colorability I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this paper, the author tries to reduce graph chromatic number to hypergraph 2-colorability (same as set splitting).

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

I'm reproducing the reduction below.

Let $G$ be a graph, $V(G) = \{x_1,\dots,x_n\}$. Let $G_i$ be an isomorphic copy of $G$, $(i=1,\dots,k)$, $V(G_i) = \{x_{i,1},\dots,x_{i,n}\}$ ($x_{i,v}$ is a point corresponding to $x_v$). Take a new point $y$ and let $f_v = \{x_{1,v},\dots,x_{k,v},y\}$. Define hypergraph $H$ by
$$
  H = E(G_1) \cup \dots \cup E(G_k) \cup \{f_1,\dots,f_n\}.
$$
Then $H$ is 2-colorable if and only if $G$ is $k$-colorable. I don't understand this conclusion and the only example I've been able to come up with where this is true is $k = 1$.

This is an error in Lovász' paper. However, a correct reduction is not too hard to come by. See this answer on math.se, in which a slight modification of the reduction you quote is shown to work.


Terminology for worst-case N-complexity on $O(1)$ insert after amortisation Normally, when discussing amortisation and worst-case complexity, amortisation negates the worst-case scenarios, and the BigO describes the average for the operation (the way it's used in interviews nowadays).

For example, when an insertion of an element requires reallocation and copying of the array, increasing the size in two, it is still said that insertion is $O(1)$, not $O(n)$; the worst-case performance is rarely mentioned.  Compare this with sorting algorithms, where the worst case could be $O(n^2)$, whereas the average case could be $O(n\log{}n)$, and this is always specified and discussed.

What is the terminology to express this N-level complexity for the $O(1)$ insertion that requires reallocation with copy of $O(N)$ elements?
What is the alternative terminology for expressing an optimisation approach, with delayed copy, where the worst-case complexity remains constant-time, provided the operation to allocate new chunk of memory itself is constant.  In other words, where you keep both arrays, and do a lazy-copy approach.

Specifically, both of the above could be described as amortisation.  But I'm having trouble finding out the absolutely correct terminology for this nuanced problem, as how do you distinguish between these two different scenarios in describing amortisation?!

The case, when the operation performs the worst, is commonly called the worst case.

The common name for the optimization you mentioned is de-amortization.

To denote the fact that operations take $O(1)$ on average, you may say that the time complexity of a single operation is amortized $O(1)$.

As far as I know, amortized complexity analysis was first introduced by Robert Tarjan in his “Amortized Computational Complexity”, where you can look up more usages of the term.


Key differences between interactive and time sharing operating systems? Couldn't find much online on how an interactive system is different from a time-sharing system, or the different traits of both.

My understanding of a time-sharing system is many people at terminals being able to use the system at the same time, and the CPU's aim is to maximise response time not CPU time (unlike a multiprogrammed batch system). The switches between jobs are very frequent, and users get immediate responses, when for example submitting interrupts via keyboard inputs. There is very little CPU idle time, duplication of software etc, but it is less reliable, there might be lower security and integrity, and potentially bad data communication. An example would be a chat messaging client or system.

Time sharing is a system of multi-tasking designed to allow multiple users to use a single machine at the same time.
A time sharing operating system is one that supports multi-tasking and multi-user.
In a time-sharing system the user typically interacts with the operating system through a secondary machine called a terminal.

In an interactive operating system there is typically only one user on the system that has full control over the system.

Because of the environment in which time-sharing machines are used (large cooperations and banks) security and separation between users is a prime concern.

Interactive computing originates from the hobby and personal computing revolution. Because there is only a single user security was initially not a concern.

From these starting points the lines have blurred.
First single user systems gained multi-tasking and then multi-user concepts were copied over from time-sharing systems into the interactive OS'es.

Meanwhile the security and performance of time sharing systems have also improved.


Is it axiomatic that the Time Hierarchy Theorem holds true in all relativized worlds? I learned from this post that ${\sf DTIME}^{\text{EXP}}(n^k) \neq \text{EXP}$ for a fixed $k$ for otherwise the Time Hierarchy Theorem would fail in that relativized world.  However, is it possible to prove that no oracles exist in which the Time Hierarchy Theorem fails?  Or is it just that we have not been able to discover any, that we assume that the Time Hierarchy Theorem never fails. Thanks.

The proof of the time hierarchy theorem relativizes. This means that all the steps remain true if all Turing machines are given access to the same oracle $O$ (for arbitrary $O$). This implies that the theorem itself remains true if all Turing machines are given access to the oracle $O$.

So yes, it is possible to prove that no oracles exist with respect to which the time hierarchy theorem fails.


Do "inductively" and "recursively" have very similar meanings? Do "inductively" and "recursively" mean very similar?

For example, if there is an algorithm that determines a n-dim vector by determine its first k+1 components based on its first k components having been determined, and is initialized with the first component, would you call it works recursively or inductively? I have been using "recursively", but today someone said it "inductively".

No, but not for the reasons other people have given. The difference between recursion and induction is not that recursion is "top-down" and induction is "bottom-up." Induction is isomorphic to something called "primitve recursion," but, in general, recursion is strictly more powerful than induction.

The distinction between top-down and bottom up is trivial -- any "top-down" primitive recursive program can be mechanically converted into something "bottom-up." In fact, any proof by induction can be turned into a recursive program. In the framework of the calculus of inductive constructions, if you want to prove that every natural number is froopulous, you'd write it as a function that constructs a proof that n is froopulous by making a recursive call to construct a proof that n-1 is froopulous.

The key factor of induction is that things are defined in terms of smaller things, and they "bottom out" after finitely many steps. Natural numbers are inductive because every natural is either 0, or the successor of a smaller natural. Lists are inductive because every list is either empty, or can be broken down ("unfolded") into an element and a smaller list.

Sometimes recursive programs aren't written in terms of smaller things though. For example, take this Collatz funtion:

fun collatz(n)
   if n <= 1
      return 0;
   else if n % 2 == 0
     return 1 + collatz(n / 2)
   else
     return 1 + collatz(3 * n + 1)
end

This function goes neither top-down nor bottom-up, and is thus not inductive over the natural numbers.

There might be an ordering to treat that inductively, but for most things there's simply no way. Functions over infinite streams are a great example. In fact, streams are the prototypical example of a "coinductive" type.

Bob Harper's "Practical Foundations for Programming Languages," available free online, has a nice introduction to inductive, coinductive, and recursive types.


Implementing an interval tree using arrays? Is it possible to create an interval tree using an array instead of the traditional pointer method? I know that for segment trees this is commonly done where the children of any element with index i are stored in 2i and 2i + 1 and the range is halved. For interval trees however, because the ranges added are not guaranteed to be halved each time, it seems like it might not be possible.

Could anyone prove or disprove whether interval trees can be implemented in this manner?

To a mathematician "prove or disprove" is a very strict requirement. I do not know how serious I should take this.

Every tree that has been implemented using pointers also has a array implementation. The trick is to do the addresses yourself as indexes to an array. That is usually called a cursor implementation.

Binary trees can be implemented, as you say, storing children of node $i$ at indices $2i$ and $2i+1$. This is sometimes called an implicit representation as no explicit structure is stored. The method is  alwaus possible, but only advisable when the tree is perfect (all levels completely filled) or near perfect, like the complete trees used to store a binary heap. Otherwise it is a waste of space. When some node $i$ is missing in the tree then also nodes $2i$ and $2i+1$ are missing, and $4i,\dots, 4i+4$, etc.


Request for examples regarding PAC learnability I am searching for 2 examples.
At the bottom I give definitions I am using.

An example for H that is PAC learnable (according to 3.1) but not Agnostic PAC learnable (according to 3.3). We learned that such should exist. I saw in another post a comment that 3.1 and 3.3 are equivalent but i can't comment there (permissions) and don't see why - any way if you know such example or have a proof there is no, i'll be glad to read.
An example of H with 2 different non trivial loss functions (if one of them can be the 0-1 loss it will be great), which give as according to definition 3.4 that H is Agnostic PAC Learnable with one but not with the other.

  definition 2.1 (The Realizability Assumption) There exists $h* \in H$ s.t.
  $L_{(D,f)}(h*) = 0.$. Note that this assumption implies that with probability 1 over
  random samples, S, where the instances of S are sampled according to D and
  are labeled by f, we have $L_S(h*) = 0$.
  $$$$
  Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable
  if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the
  following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and
  for every labeling function $f \colon X \mapsto  \{0,1\}$,  if the realizability assumption holds
  with respect to $H,D,f$, then when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns
  a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L_{(D,f)}(h) \leq \varepsilon.$$

  Definition 3.3 (Agnostic PAC Learnability) A hypothesis class $H$ is agnostic
  PAC learnable if there exist a function $m_H\colon(0,1)^2 \mapsto N$ and a learning algorithm
  with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$
  over $X\times Y$, when running the learning algorithm on $m \geq m_H(\varepsilon, \delta)$ i.i.d. samples
  generated by $D$, the algorithm returns a hypothesis $h$ such that, with probability
  of at least $1 - \delta$ (over the choice of the $m$ training examples),
  $$L_D(h) \leq \min_{h' \in H}
L_D(h') + \varepsilon.
$$

  Definition 3.4 (Agnostic PAC Learnability for General Loss Functions) A
  hypothesis class H is agnostic PAC learnable with respect to a set Z=$X \times Y$ and a
  loss function $l : H \times Z \mapsto R_+$, if there exist a function $m_H\colon(0,1)^2 \mapsto N$
  and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$
  and for every distribution D over Z, when running the learning algorithm on
  $m \geq m_H(\varepsilon, \delta)$ i.i.d. examples generated by D, the algorithm returns $h \in H$
  such that, with probability of at least $1 - \delta$ (over the choice of the m training
  examples),
  $L_D(h) \leq \min_{h' \in H}
L_D(h') + \varepsilon.$
  where $L_D(h) = E_{z \sim D}[l(h,z)]$.

Thank you!

You can find a proof for the equivalence between PAC and agnostic PAC learning in theorem 6.7 of "Understanding Machine Learning" by Shai Ben-David and Shai Shalev-Shwartz. The proof goes through showing:

$\mathcal{H}$ is PAC learnable $\Rightarrow$ $\mathcal{H}$ has finite VC dimension (lower bound on sample complexity).
$\mathcal{H}$ has finite VC dimension $\Rightarrow$ $\mathcal{H}$ is agnostic PAC learnable (upper bound on sample complexity)

If you don't care about the bounds being sharp, $1$ is not too hard, but $2$ is definitely beyond the scope of this site. Combining the above results with the fact that agnostic PAC learnability implies PAC learnability concludes the proof.

In regard to your second question, let $l_1$ be the 0-1 loss function and $l_2$ be a loss function which is nonzero only on a finite subset of $\mathcal{X}$ and is the 0-1 loss in that region (suppose you only care about very specific mistakes). Take any class with infinite VC dimension, then it is not agnostic PAC learnable with respect to $l_1$, but is learnable with respect to $l_2$ (If the loss function is nonzero only on a finite region, you can treat this case like having a finite hypothesis class).


Dynamically Learning Haar Cascade (in OpenCV) I am new to computer vision so please excuse me if this question is very simple.

I am trying to learn how to use the Haar Cascade creation tool provided with OpenCV to train a cascade classifier. It seems relatively easy, with the tools provided, but I was wondering if there was a way to improve the network after the initial training. I plan to gather an initial set of positive images and train the cascade on those, but afterwards, continue collection and feed new positive images into the cascade to improve detection rates, reduce false positives and allow for better results in more difficult scenarios. Instead of retraining the cascade every time a new batch of positive images is produced, it would be extremely helpful if the cascade could prune itself and improve predictions based on the new images. I was wondering if this is possible, and how one would go about implementing it.

(Note: In this tutorial, the author discusses the use of more than one training epochs in a Deep Belief Network to improve detection rates by strengthening connections that result don't. I'm not sure how this works, but I would assume that if new images are added in each epoch, they could be incorporated without a full retraining, just a pruning. I would like to apply a similar approach to the cascade classifier.)

(Note on Note: The reason that I am using a cascade classifier and not a DBN is because I don't want to be restricted to defining a set number of output neurons. There may any number of detectable objects in the image, in addition to the fact that some results may be a plain boolean value. It doesn't seem that a DBN will work well. However, I have relatively little knowledge of the subjects and any suggestions on what approach to take to achieve the above implementation would be helpful.)

Thank you.

Sadly, I don't know of any simple way to achieve this, for Haar cascades.

The problem is that Haar cascades are trained using boosting.  A cascade is a multi-stage classifier: we use the first stage to quickly discard candidates: if the first stage says "no", we immediately reject, and only go on to process the input with the second stage if the first stage says "yes".  That means that the second stage is trained on only images that the first stage classifies "yes".  If you add some more training examples and want to update the first stage, then now this has cascading effects on all of the subsequent stages: naively, you need to re-train all subsequent stages, because the set of images they should be trained on has now changed.

There might be a clever way to do it, but it's not straightforward.


If A is polynomial time reducible to B does that imply not(A) is polynomial reducible to not(B) $A\leq_p B \iff \bar{A}\leq_p \bar{B}$ (if A is polynomial time reducible to B does that imply that complement of A is polynomial reducible to complement of B)

I was told that this is the case based on the definition of $\leq_p$ but I am having trouble proving this.

In case you were wondering, the answer is yes.

Here is the reasoning.

Lemma: Let $f$ be a reduction from $A$ to $B$. Then $f$ is also a reduction from $\overline A$ to $\overline B$.
Proof: By the definition of a reduction, $f$ maps $A$ to $B$ and $f$ maps the complement of $A$ to the complement of $B$. So $f$ maps the complement of the complement of $A$, which is $A$ itself, to $B$, which is the complement of the complement of $B$. By the definition of a reduction again, $f$ is a reduction from the complement of $A$ to the complement of $B$. QED.

Suppose $A$ is polynomial-time reducible to $B$. Let $f$ be a polynomial reduction from $A$ to $B$. The lemmas shows that $f$ is also a reduction from the complement of $A$ to the complement of $B$. Since $f$ is polynomial-time, $\overline A$ is polynomial-time reduced to $\overline B$ by $f$.

With $A$ replaced by $\overline A$ and $B$ by $\overline B$, the above paragraph also shows $\overline A$ is polynomial-time reducible to $\overline B$ implies $A$ is polynomial-time reduced to $B$.

The above two paragraphs shows the equivalence of $A\leq_p B$ and $\overline{A}\leq_p \overline{B}$.


Round-Robin fashion exercise In my Operating Systems class I have an exercise to sketch out how a round-robin algorithm would apply to a specific scenario, which is the following:

Now the correction that I was provided with by the lecturer is the following:

But I do not understand how this is correct. After referring to the lecture that was given on this specific topic, I understood that Round-Robin maintains a queue with threads and each thread has a time quantum of tens of milliseconds of CPU time. When a thread has exhausted its time quantum CPU time it goes straight to the end of the queue. I also know that, threads that do not full use their time quantum CPU time, will be put in a separated queue, resulting in multilevel queue. After my understanding, this last part is ignored here. Here is the resolution of the exercise that I came up with:

The "-" stand for executing time, the "v^v^v" stands for blocking time, pretty much like in the correction picture.
Note that my version, and the version of the correction match up until the 1st pink dashed line.

Finally, the question is: How come that after the 1st pink dashed line, A is assigned to the CPU? (in the correction version), instead of B, which is, after my understanding, the next process in the queue to be executed(See "Ready queue") in my version of the exercise.

Please note that there are priorities, but according to the definition of round-robin fashion, priorities are not considered for it(I know that in most OSs the plain vanilla round-robin is not applied, but please ignore that); priorities are there for other parts of the exercise which have nothing to do with this issue.

A round robin scheduler has a fifo queue of processes in state runnable.  At each time step the scheduler runs the process at the head of the queue for one quantum.

At the end of each time quantum the running process is interrupted and placed at the tail of the queue.  If the process blocks (requests i/o) during the time quantum it is typically completely removed from the queue.

The difference between your solution and your instructor's solution is the assumption you are making about what happens when a process's i/o request finishes, and the process again becomes runnable.   Your instructor assumes that the process is placed on the tail of the queue.  You seem to be assuming that the process is placed at the head of the queue.

Either choice (placing the newly unblocked process at the tail or at the head) is reasonable, but they have different consequences as described by @Gille's answer to a broader question.

If you place the newly unblocked process at the tail of the queue then you maintain the guarantee that no process will ever be starved.  In practice however, i/o-bound jobs are sometimes given higher priority, both to reduce the latency of those jobs, and to maximize throughput of i/o devices.  You could implement this increase in priority by putting newly unblocked processes at the head of the queue instead of the tail, but you would lose your starvation-freeness guarantees.


Is there a decidable problem which has a proof that it cannot be proved to have a particular deciding Turing machine? I came across the question Is there an algorithm that provably exists although we don't know what it is? I was able to follow the example "Given an integer $n\ge0$ is there a run of $n$ or more consecutive 7s in the decimal expansion of $\pi?$" given in one of the answers. The answer shows that the problem in example is decidable although we don't know which is the correct algorithm. Let $P$ be a problem which is decidable, we know that for some for some finite integer $k > 1$ one of the Turing machines $M_1,M_2,..,M_k$ decides the problem, but we don't know which of them exactly is the decider. Is it possible that $P$ has a finite proof which tells us that it is not possible to prove exactly which of the machines is the decider ? Or is it always, that the proof exists proving that exactly one of the machines is the decider but we don't know it ?

I am not even sure if my question makes sense. I could make changes or remove the question if it does not not. Sorry for the vague definition of a proof.

Let us examine the following language:

$x\in L \iff ZFC \hspace{1mm} \text{is consistent}$.

Clearly, $L$ is decidable, and is decided by either the constant 1 or 0 machines.

Proofs from ZFC for the statements "$M_0$ decides $L$", "$M_1$ decides $L$" cannot exist  (if ZFC is consistent), since any of those would imply a proof from ZFC about its own consistency (see Godels's second incompleteness).

Note that i can however, provide a proof that the following machine $M$ decides $L$:

Given input $x$, check if there exists a proof for the consistency of ZFC, of length$\le |x|$. If such proof is found, return 0, otherwise return 1.

If ZFC is consistent, the above machine outputs 1 for all $x$. If it isn't, we also have a proof that the above machine decides $L$ (An inconsistent system can prove any statement). The problem is that i cant prove whether or not $M$ computes the constant 1 function.


Turing Machines and Algorithm for Language Acceptance Is there an algorithm to decide if any two Turing machines accept the same language?  I can't find a definite answer to this.  My guess is that there isn't, because then we would be able to decide if a Turing machine accepts a given language and halts, which is undecidable.  Is there a better explanation for why this is or is not the case?

Your guess is correct: deciding whether two Turing machines are equivalent (i.e. accept the same language) is an undedicable problem.

To prove this, it should be possible to reduce this problem to the halting problem.

You can also use Rice's theorem.

The theorem states the following:

  Let P be any non-trivial property of languages of Turing
  machines. Then, the following language is undecidable, $LP=\{\langle M\rangle : L(M) \text{ satisfies } P\}$.

Note that $L \text{ satisfies } P$ means $L \in P$.

Note also that a “trivial property” is a property that is either satisfied by all languages, or a property that is not satisfied by any language.

Now, if you consider two machines $M_1$ and $M_2$, deciding whether $L(M_1) = L(M_2)$ is deciding whether $M_2 \in \{\langle M \rangle : L(M) \text{ satisfies } \{L(M_1)\}\}$.

Since $\{L(M_1)\}$ is non trivial (there exist machines which recognize it and there exist machines which do not recognize it), this problem is undecidable.


What is the difference between Babbage's analytical and difference engine? What is the difference between Babbage's analytical and difference engine? Can they even be compared?

They would be different from each other in a very significant way. In the comments there is a link to the Wikipedia articles on both machines - which are quite informative - but I'll assume they weren't useful to you.

You can think of the Analytical Engine basically as a regular computer, which would have a program coded in punched cards, that were attached to each other forming a chain (there would actually be three kinds of cards, each with its own reader, check this out). The machine also had a control unit whose job was to decode the instructions of this program and perform them on the data that was stored in a memory capable of holding a thousand numbers.

The Difference Engine, on the other hand, would have been exactly a calculator, and one that could perform just one kind of operation, repeatedly, on a sequence of numbers. In the "Sketch of the Analytical Engine", authored by Luigi Menabrea, and famously translated by Ada Lovelace, the nature and general applicability of this operation is detailed:

  The theorem on which is based the construction of the machine we have just been describing, is a particular case of the following more general theorem: that if in any polynomial whatever, the highest power of whose variable is m, this same variable be increased by equal degrees; the corresponding values of the polynomial then calculated, and the first, second, third, &c. differences of these be taken (as for the preceding series of squares); the mth differences will all be equal to each other. So that, in order to reproduce the series of values of the polynomial by means of a machine analogous to the one above described, it is sufficient that there be (m+1) dials, having the mutual relations we have indicated. As the differences may be either positive or negative, the machine will have a contrivance for either advancing or retrograding each needle, according as the number to be algebraically added may have the sign plus or minus. (emphasis added)

By calculating series of values of polynomial functions many useful calculations can be approximated, including those of trigonometric and logarithmic functions. This method has its limits, though, which are explained a bit further in the document. In doing that, the justification for the construction of the new machine is given:

  We see that its use is confined to cases where the numbers required are such as can be obtained by means of simple additions or subtractions; that the machine is, so to speak, merely the expression of one particular theorem of analysis; and that, in short, its operations cannot be extended so as to embrace the solution of an infinity of other questions included within the domain of mathematical analysis. It was while contemplating the vast field which yet remained to be traversed, that Mr. Babbage, renouncing his original essays, conceived the plan of another system of mechanism whose operations should themselves possess all the generality of algebraical notation, and which, on this account, he denominates the Analytical Engine. (emphasis added)


Given a set of intervals $(I_n)_n$ contained in $[0, L]$, compute the longest interval in $[0, L]$ which has empty intersection with all $(I_n)_n$ Let be $(I_n)_n$ a set of $p$ intervals each contained in $[0, L]$ for $L \geq 1$.

I define $(J_n = [a_n, b_n])_n$ the set of intervals which have empty intersection with $I_n$ for all $n \in [[1, p]]$.

I'd like to efficiently compute $\max_n (b_n - a_n + 1)$.

A basic idea I'd try would be to:

(1) Create a segment tree for $(I_n)_n$ in $O(p \ln p)$

(2) Iterate over $[0, L]$ and count the longest line before encountering an interval covered by $(I_n)_n$ (resetting the "max value" to 0 until the next of a certain $J_q$)

Which could give me an algorithm in $O(L + p \ln p)$, the problem is that $L$ is really big in my instances, I'd like to have an algorithm which does not depend on $L$.

(From your notations, I assume the intervals are all discrete as otherwise some of the $J_n$ would not be closed. Furthermore, the length of the intervals would not be $b_n-a_n+1$ so I'm fairly certain that assumption is safe. If however that was not your intention, it should be straightforward enough to adapt the algorithm to the continuous case).

Consider all intervals $(I_n=[\![s_n,e_n]\!])_{0\leq n<p}$, and sort them by increasing start time $s_n$, breaking ties arbitrarily  [time $\mathcal{O}(p\cdot \log p)$]
Build a stack containing only the first interval (i.e. the one with the smallest start). For each subsequent interval: if [the interval doesn't overlap with the head of the stack] then [push it] else [merge it with the head of the stack] [time $\mathcal{O}(p)$]

What we've done here is merge the intervals $(I_n)_n$ so as to rewrite $\bigcup I_n$ as an ordered stack of disjoint intervals. We shall call these intervals $(\tilde{I}_n=[\![\tilde{s}_n,\tilde{b}_n]\!])_n$

Now iterate linearly through the stack to find the largest interval separating two successive intervals on the stack (without forgetting the two intervals $[\![0,\tilde{s}_0[\![$ and $]\!]\tilde{s}_{-1},L]\!]$) [time $\mathcal{O}(p)$]

Overall the runtime is $\mathcal{O}(p\cdot \log p)$.


ILP representation of the number of maximal 1 sequences in a row I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some consecutive range $(i,j)$ and no two events can overlap. Therefore, I can represent events by some matrix $a=\{0, 1\}^{n\times n}$ where $a_{i,j} = 1$ iff there is an event that begins at $i$ and ends at $j$ ($i<=j$).

Unfortunately, this results in $O(n^2)$ variables and in some cases $O(n^3)$ or greater number of constraints. It would be ideal if instead I could represent these events as a row $a'=\{0,1\}^n$, where $a'_i = 1 \iff \exists a_{p,q}\quad  \text{s.t.}\quad  p\leq i\leq q \land a_{p,q} = 1$
i.e. a position $a'_i=1$ iff there is an event that modifies position $i$.

Since I am optimizing over the number of events, at the moment I am minimizing $\sum a_{p,q}$, since it represents the number of events. If I ditch $a$ and try to only use $a'$, I am left with some row, for example $a'=[1,1,0,...,1,0,1]$.

Question 1: I want to represent the total number of events given $a'$. Currently, I am thinking $\sum a_i(1-a_{i+1})$ to count the number of "ends" of events. Obviously I can deal with the edge case as well. Unfortunately, this results in a product of binary variables. I know that I can represent this with a helper variable, and just sum over that, but I was wondering if there was any more efficient ways.

Question 2: This question is more important, since my whole model revolves around this. An event will only affect the input elements after the end of the event. Think of events as duplications. If some range $(i,j)$ is duplicated, all elements after $j$ would shift to the right by $j-i+1$ slots. Following this idea of events being duplications, consider the input below:

$a,b,c,d,e$ and the desired sequence $a,b,a,b,c,d,e,d,e$. We can achieve this by duplicating $a,b$ and $d,e$ i.e. $a'=[1,1,0,1,1]$. Notice how positions $0$ and $1$ did not shift at all, positions $2,3,4,5,6$ were originally $0,1,2,3,4$, and positions $7$ and $8$ were originally $3$ and $4$.

Essentially, for every position $i$ in the resulting sequence, I would like to be able to determine which position $j$ it came from in the original sequence. Consider position $6$ in the resulting sequence, we can clearly see it came from position $4$. We notice that this shift of $2$. Similarly, position $5$ came from position $3$. A pattern unfolds such that the shift of position $i$ is always equal to the $\sum_{j<k} a'_j$ where $k$ is the largest index such that $k\leq i \land a_k=0$. This is the same as saying that we are taking the sum of all values of $a'$ up to the most recent $0$ before or at $i$ in $a'$.

How can I model such shifting in an ILP? I.e. given $a’$, how can I create a variable $h$ in the ILP such that $h_{r, l}=1$ iff $\sum_{j<k} a'_j= l$ where $k$ is the largest index such that $k\leq r \land a_k=0$.

I think this can be done with $9n$ variables, instead of $n^2$.  Define the following integer variables for use in your linear program:

$a_i = 1$ if index $i$ is within an event
$s_i = 1$ if an event starts at index $i$
$e_i = 1$ if an event ends at index $i$
$c_i = $ the number of positions until the end of this event (so that index $i+c_i-1$ is the end of the event containing $i$), if $i$ is in an event, or $0$ if $i$ is not in an event
$d_i = $ is how many positions since the start of the event (so that index $i-d_i+1$ is the start of the event containing $i$), if $i$ is in an event, or $0$ if $i$ is not in an event
$\ell^1_i = $ the length of the event containing $i$, if $i$ is the end of an event, or $0$ if $i$ is not the end of an event
$\ell^2_i = $ the length of the event containing $i$, if $i$ is the start of an event, or $0$ if $i$ is not the start of an event
$o^1_i = $ the amount index $i$ is shifted when copying to the new array, for the first copy of that element
$o^2_i = $ the amount index $i$ is shifted when copying to the new array, for the second copy of that element

These can be enforced with the following equations:

$s_i = a_i \land \neg a_{i-1}$ (see Express boolean logic operations in zero-one integer linear programming (ILP) for how to enforce this)
$e_i = a_i \land \neg a_{i+1}$
$c_i \ge c_{i+1} + 1 - n s_{i-1}$, $c_i \le c_{i+1} + 1$, $c_i \le n a_i$, $c_i \ge e_i$, $c_i \ge 0$
$d_i \ge d_{i-1} + 1 - n e_{i-1}$, $d_i \le d_{i-1} + 1$, $d_i \le n a_i$, $d_i \ge s_i$, $d_i \ge 0$
$\ell^1_i \le n e_i$, $\ell^1_i \ge d_i - n(1-e_i)$, $\ell^1_i \ge 0$
$\ell^2_i \le n s_i$, $\ell^2_i \ge c_i - n (1-s_i)$, $\ell^2_i \ge 0$
$o^1_i = o^1_{i-1} + \ell^1_{i-1}$, $o^1_0 = 0$
$o^2_i = o^2_{i-1} + \ell^2_i$, $o^2_0 = 0$

Then the total number of events is $s_1+\dots+s_n$, and you can model shifting as follows: index $i$ in the original array is shifted to indices $i+o^1_i$ and $i+o^2_i$ in the new array.

Do check my work carefully. There could easily be off-by-one errors or other mistakes in the above.


Algorithm to find pronounciation rules Suppose that you have a large dictionary with spellings and pronounciations of foreign words, and you want to find a set of pronunciation rules. They should have the simplest form: a sequence of letters to a sequence of sounds.

For example, in French, c [k], i [i] and ci [si].

The rules may be long: tion [sjɔ̃] (instead of [tjɔ̃]).
They may be rare: à [a] is used only in a dozen of words.
They may be both: aill [aj] (as a-ill, instead of ai-ll [ɛl]).

Fortunately, such rules are rare enough: for the most part, the letters are pronounced by itself, even most of them in complicated rules. For examples, cercle [sɛʀkl] instead of [kɛʀklɛ]: the algorithm should notice the corresponding sounds in the middle of the word.

Maybe, there is a standard algorithm to extract candidates for such rules? I would like to have an explicit list of rules, rather than a method predicting  pronunciation.

Broadly, I can see two possible approaches: machine learning, or data mining

Machine learning

You could look into using machine learning to learn a transducer that transforms the input sequence (the letters in the word) to the output sequence (the pronunciation).  This approach doesn't try to find an explicit set of rules; it just tries to find a method that is effective in practice at producing the right pronunciation.

You could try training a recurrent neural network (RNN), and/or a LSTM network.  LSTM's have been effective at related tasks, and since you have a large training set, they might possibly be effective here.  Bi-directional RNN's/LSTM's might be worth exploring.

Data mining

Alternatively, you could use data mining techniques to try to find an explicit set of rules that seem to have good support among your dictionary.

This problem fits into the general area of sequence mining (also known as sequential pattern mining) and association rule learning.  I think it might be fruitful to try applying one of the algorithms from that field, to your problem.

In your case, you could consider each possible substring of the word or pronunciation to be a possible item, and your goal is to find rules of the form $x \Rightarrow y$, where $x$ is a substring of the word and $y$ is a substring of the pronunciation.  This is a special case of itemset mining, where your itemsets are restricted to have size 1.  You could then adapt any standard itemset algorithm (e.g., Apriori, FP-growth) to this problem.

For instance, here is an adaptation of Apriori.  You consider all possible rules of the form $x \Rightarrow y$, where $x$ and $y$ are length 1.  For each, you compute their support or some probabilistic measure of the strength of the association (e.g., out of all words that contain $x$, what fraction contain $y$?).  Discard all candidate rules for which this metric is below some threshold.  Then, try all extensions of this rule by extending either $x$ or $y$ by one character to the left or right side of it; this gives you a bunch more candidates.  For each such candidate, compute the metric and discard those that are below the threshold.  Keep expanding your set of candidates until no new candidates can be identified.  This is basically a form of "breadth-first search".  Finally, at the end, prune your rules by eliminating rules with a containment relationship (e.g., if you have a rule $x \Rightarrow y$, then you might want to remove all other rules of the form $x' \Rightarrow y'$ where $x'$ is a substring of $x$ and $y'$ is a substring of $y$).

You could also consider similar tweaks to FP-growth.

However, it's not clear to me how well a data mining-based approach will work: while it does consider order to some extent, it doesn't take into account the position within the word, and it doesn't consider whether a set of rules fully covers all of the characters in the word, and it doesn't take into account rule overlap (e.g., $x_1 \Rightarrow y_1$ and $x_2 \Rightarrow y_2$ where $x_1,x_2$ overlap partially).


Why does it take $O(f(n)^2)$ to simulate a 3-tape $O(f(n))$-time TM on a 1-tape  TM? This looks like a fundamental result but I can't find a resource online that gives an intuitive interpretation of this complexity. Any basic explanation is appreciated.

Have a look in the book of Hopcroft and Ullman "Introduction to automata theory, languages and computation" (ISBN 0-201-02988-X). I have only the German version of this book, but there it is mentioned as Theorem 12.5.

However the basic idea behind the tape-reduction from $k$ tapes to 1 is quite easy. Assume the running time is bounded by $f(n)$. You boost you working alphabet $\Gamma$, such that every super-character represents $k$ original characters and $k$ Flags. The flags store the position of the head of the corresponding simulated tape. To simulate one step of the old machine, we have to scan through the whole tape. However, the tape contains at most $O(f(n))$ characters, hence the scan needs $O(f(n))$ time. Since we simulate $O(f(n))$ steps the 1-tape machine runs in $O(f(n)^2)$. I think from here you can work out the details on your own.


Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.? So in regular algebra we have some basic operations defined such as multiplication, addition, subtraction and division.

For these operations/operators, we have some properties like commutativity, associativity and distributivity.

Is there an analogue set of properties for the operations/operators on that we do with Regular Expressions?

I also believe that the set of all regular expressions together with its operations that are defined on the members of regular expression set form an algebraic structure similar to the integers and common operators that we learn about at arithmetics.

There are several known axiomatizations of the equational theory of Kleene algebra, see lecture notes from a course by Dexter Kozen. These axiomatizations give you a complete set of rules that can be used to deduce any identity involving regular expressions. The first ones were given in a classic paper of Salomaa, and others are also known.


In what ways can we distinguish between a human and bot behavior? Updated based on comments:

In what ways can we distinguish a human being doing certain activities online and a bot programmed to do similar activities, say checking email, downloading some music files, shopping on ebay, searching on Google etc., or maybe trying to deface/hack a website, brute force a log-in password etc.

To limit the scope of the question and make it more clear, let us restrict our observations only to network-oriented behavior, some examples being- the amount of time spent doing XYZ thing online, the amount/type of data downloaded (say) from a file sharing website, the number of friends/followers on Social media websites, etc.

I guess it should possible to obtain some 'patterns' which will distinguish human behavior and programmed behavior.

The Turing test is not what I am looking for.

What techniques can be useful here? Machine learning? Game theory?

References to relevant academic/research articles will also be good.

The most common/obvious way is a challenge-response test that is easy for humans but hard for computers (of course, but not only, CAPTCHA).

This kind of test is very effective{1} but falls under the HIP (Human Interactive Proofs) area: it's not transparent.

Typical, "simple" approaches to distinguish human website traffic from Bot are:

time it takes to populate all the fields and click the submit button of an input form (frequently used but simple to bypass).

Watching the cadence / pace of the communication is a more secure alternative (this is one of the feature of Google's No CAPTCHA reCAPTCHA);
honeypots (i.e. traps for bots that consist of a link or field present on the page that isn't visible to the human eye)
analysis of maximal continuous session length (humans have to rest) and correlation with time of day (see Distinguishing Humans from Bots
in Web Search Logs)

It must be considered that bot characteristics exhibit a wide variability for different crawler / different sites, therefore it's difficult to derive simple, deterministic heuristics: rule based systems imply a long list of static rules that are difficult to define and maintain (even by experts).

Machine learning techniques are often used:

Web robot detection: A probabilistic reasoning approach constructs a Bayesian Network that classifies automatically log sessions as being crawler or human induced
Discovery of web robot sessions based on their navigational patterns
uses C4.5 decision tree algorithm (after deriving the session features)
Detecting Click Fraud in Pay-Per-Click Streams of Online Advertising Networks develops Bloom Filter-derived techniques.
Neural networks applied to speed cheating detection in online computer games adopts an artificial neural network for bot detection in MMORPGs
Using Sentiment to Detect Bots on Twitter: Are Humans more Opinionated than Bots? tries Gaussian naive Bayes, Support Vector Machines and  Random Forests

Almost every available AI/ML "tool" has been experimented. The main problem using these supervised machine learning tools is labeling the training dataset.

Even restricting the analysis to network-oriented behavior, this is a question of tremendous scope, for this reason I'm giving some keywords for further searches.

Notes

Machine Learning based attacks are improving and CAPTCHAs also serves as a benchmark task for artificial intelligence technologies (e.g. The End is Nigh: Generic Solving of Text-based CAPTCHAs)

Keywords

HIP (Human Interactive Proofs), CAPTCHA, Keystroke dynamics, Keystroke cadence, typing dynamics, IDS (Intrusion Detection System), honeypot, click fraud, spambot

References

Designing Human Friendly Human Interaction Proofs (HIPs) by Kumar Chellapilla, Kevin Larson, Patrice Simard, Mary Czerwinski (Microsoft Research)
The End is Nigh: Generic Solving of Text-based CAPTCHAs by Elie Bursztein, Jonathan Aigrain, Angelika Moscicki, John C.Mitchell (2014)
Keystroke Dynamics User Authentication Based on Gaussian Mixture Model and Deep Belief Nets by Yunbin Deng, Yu Zhong (2013)
User Authentication Through Typing Biometrics Features by Lívia C. F. Araújo, Luiz H. R. Sucupira Jr., Miguel G. Lizárraga, Lee L. Ling, andJoão B. T. Yabu-Uti (2005)
Distinguishing Humans from Bots in Web Search Logs by Omer M. Duskin Dror, G. Feitelson
Web robot detection: A probabilistic reasoning approach by Athena Stassopouloua, Marios D. Dikaiakos (2008)
An investigation of WWW crawler behavior: characterization and metrics by M.D. Dikaiakos, A. Stassopoulou, L. Papageorgiou (Computer Communications, 2005)
Discovery of web robot sessions based on their navigational patterns by Pang-Ning Tan, Vipin Kumar (2002)
Telling humans and computers apart automatically by Luis von Ahn, Manuel Blum, John Langford (Comm. ACM, 2004)
Detecting Click Fraud in Pay-Per-Click Streams of Online Advertising Networks by Linfeng Zhang, Young Guan (IEEE, 2008)
Bots Problem in Online Games by Dewanshu Jain, Alok Gupta
Neural networks applied to speed cheating detection in online computer games by Gaspareto, Barone, Schneider (2008)
Quantifying Online Advertising Fraud: Ad-Click Bots vs Humans by Adrian Neal, Sander Kouwenhoven (2015)
Comparison of Classification Algorithms to tell Bots and Humans Apart by Christian Hadiwijaya Saputra, Erwin Adi, Shintia Revina, Bina Nusantara (2014)
Using Sentiment to Detect Bots on Twitter: Are Humans more Opinionated than Bots? by John P. Dickerson, Vadim Kagan, V.S. Subrahmanian (2014)