Adding a node between two others, minimizing its maximum distance to any other node We are given an undirected graph weighted with positive arc lengths
and a distinguished edge $(a,b)$ in the graph. The problem is to
replace this edge by two edges $(a,c)$ and $(c,b)$ where $c$ is a new
node, such that the length of the path $(a,c,b)$ is equal to the
inital length of $(a,b)$, and such that the choice of the length of
$(a,c)$ minimizes the maximum distance of node $c$ to any other node
of the graph.  Is there any graph-theory based algorithm that can solve such problem rather than brute force?

Actually, the existence of the original edge $(a,b)$ is not
essential. Only the end nodes $a$ and $b$, and the length matter.

For example we have a graph:

1 2 10
2 3 10
3 4 1
4 1 5

In every line the first two values indicate the node number, and the 3rd one is the corresponding edge value. Now I want to find a new node $c$ between nodes 1 and 2. The answer gives
a node $c$ at distance 2 to node 1 (and distance 8 to node 2). The
distance of node $c$ is 2 to node 1, 8 to node 2, 1+5+2=8 to node 3, and
5+2=7 to node 4. The maximum distance is 8, which is minimal for all
possible choices of the length of $(a,c)$.

Introduction

This answer is in two parts.

The first is an analysis of the problem mixed with a sketch of the
algorithm to solve it. As it is my first version, it is detailed, but
results in an algorithm that is a bit more complex than needed.

It is followed by a pseudo-code version of the algorithm, written sometime later, as the algorithm was clearer. This pseudo-code is more
direct, and somewhat simpler, but probably easier to understand after
reading the first part.

In retrospect, the more important ideas are:

to see that the maximum distance of a node to the new node C, as a
function of the length of $(A,C)$, is given by the superposition of
roof shaped (inverted V) curves, characterized by their top,
associated to nodes of the graph.
to see that irrelevant curves can be eliminated efficiently by a
scan in monotonic order of abscissa of tops (with minimum backtrack).
then minimal points can be enumerated simply by intersecting the remaining
curves two by two, again in monotonic order of abscissa of tops.

Sketch of an algorithm

NOTE: I changed the initial presentation of the question to get a more
standard view of graphs, by considering that the edge $(A,B)$ is
replaced by a new node $C$ and two edges $(A,C)$ and $(C,B)$ with the
same total length as $(A,B)$.

Let $(A,B)$ be the distinguished edge, and let $l$ be its length. Let
$e$ and $n$ be respectively the number of edges and the number of
nodes in the graph.

First you remove the edge $(A,B)$. Then, for every node $U$ of the
graph, you compute the distance $\alpha(U)$ between $A$ and $U$, and
the distance $\beta(U)$ between $B$ and $U$. This can be done with
Dijkstra's shortest path algorithm, in time $O(e+n\log n)$.

Then you add a new node $C$ with an edge $(A,C)$ and an edge $(C,B)$,
of length respectively $a$ and $b$, such that $a+b=l$. The
length $a$ is not known, and is to be found so as to minimize the
distance of the most remote node to node $C$. The distance of $C$ to
$A$ or $B$ may be 0.

The difficulty of the problem is that the node most distant from $C$
via $A$ may be close to $C$ via $B$, and thus does not matter. Also, a
node closer to $C$ via $A$ than via $B$ may inverse that situation as
$C$ moves between $A$ and $B$, i.e. as $a$ varies in $[0,l]$.

We consider three sets of nodes in the graph, forming a partition of
all nodes:

the set $N_A$ of nodes that are always closer to $C$ via $A$
independently of the value of $a$:
$N_A=\{U|\alpha(U)+l\leq\beta(U)\}$
the set $N_B$ of nodes that are always closer to $C$ via $B$ independently
of the value of $a$:
$N_B=\{U|\beta(U)+l\leq\alpha(U)\}$
and $N_{AB}$ the set of nodes that can be closer to $C$ via $A$ or
via $B$, depending on the value of $a$, actually closer via $A$ for
smaller values of $a$, and closer via $B$ for larger values of $a$ in $[0,l]$:
$N_{AB}=\{U\mid\alpha(U)+l>\beta(U) \wedge \beta(U)+l>\alpha(U)\}$

Let $U_A$ the node in $N_A$ most remote from $A$, and $U_B$ the node
in $N_B$ most remote from $B$.

No other node in $N_A\cup N_B$ is ever more distant from $C$ than the
more distant of these two nodes, whatever the distance $a$ of $(A,C)$.
Hence all other nodes in $N_A\cup N_B$ can be discarded for the
computation of the optimal value of $a$.

Note that it may happen that $N_A$, or $N_B$, or both, are empty. In
which case, the corresponding nodes $U_A$ and/or $U_B$ do not exist.

We will build a distance curve on a plane with coordinate $(x,y)$, which will
ultimately represent the longest distance $y$ of a node from $C$ as a
function of the distance $x=a$ of $C$ from $A$. Hence $x=a\in[0,l]$

This distance curve is actually a zig-zag composed of segments angled $\pm
45^\circ$. Once it is built, the point minimizing the longest distance
is to be found in the minimal points of the curve. There may be
several such points. All these points have to be computed, and then
compared.

We describe below how to compute them.

Actually, we consider a collection of simpler distance curves, with only one or
two segments in the interval $[0,l]$, such that the longest distance of
a node from $C$ is always on or above the curve. The final curve is
obtained by taking for every value of $x$ the maximum value of $y$
given by one of the distance curves. This can be done formally by computing the
intersection of the segments in an ordered fashion.

First we have (at most) two distance curves composed of only one segment. These
are the curves corresponding to the distance of $U_A$ and $U_B$ to
$C$. The first is upward at a $45^\circ$ angle, and the second is
downward at a $45^\circ$ angle.

Assuming no other node is ever more distant from $C$, the optimal
value of $a$ is the abcissa of their intersection. At that abscissa,
that value for $a$, the nodes $U_A$ and $U_B$ are at the same distance
from $C$. Hence the distance is minimum when $a$ satisfies the
equation $\alpha(U_A)+a=\beta(U_B)+b$. Since $a+b=l$, this gives
$\alpha(U_A)+a=\beta(U_B)+l-a$, and finally
$a=(\beta(U_B)-\alpha(U_A)+l)/2$. This corresponds to a distance
$y=(\alpha(U_A)+\beta(U_B)+l)/2$ of both nodes to $C$.

Together, the two curves give a V shaped curve, with a minimum at the
point just computed.

But we also have to account for all the nodes in $N_{AB}$. The
distance of a node $U\in N_{AB}$ to $C$ first increases with $x$ while
the shortest path goes through $A$, them it decreases with $x$ when
the shortest path goes through $B$. Hence, the corresponding distance curve is
formed of two segments, roof shaped, with a maximum at an abscissa
such that the distance to $C$ is the same through $A$ or through $B$.
This gives the equation $\alpha(U)+a=\beta(U)+b$. Resolving it as
above, we get $x=a=(\beta(U)-\alpha(U)+l)/2$, and
$y=\alpha(U)+\beta(U)+l)/2$. We note $T_U$ (for Top of $U$) the point
with these coordinate. The top $T_U$ characterizes the roof shaped distance
curve for node $U$ since the slope of both side is $\pm 45^\circ$.

Now all the difficulty of the problem is that several nodes $U\in
N_{AB}$ may be such that $T_U$ is above our first V-shaped curve,
which will lead to the final zig-zag line.

But, we first can eliminate all nodes $U\in N_{AB}$ such that $T_U$ is
below the V-shaped distance curve, as they will not ever contribute to the
longest distance. This is easily done and is skipped here for clarity.

Then we want also to eliminates all nodes $U\in N_{AB}$ such that
their roof-shaped curve is always below the curve of another node
$V\in N_{AB}$. This is determined by the position of their tops, and
we say that $T_V$ dominates $T_U$, or that $V$ dominates $U$. Actually
$T_V$ and $T_U$ are in a domination relation iff the absolute value
of the abcissa difference is less than the absolute value of the
ordinate difference. The dominating node/top is the one with the
highest ordinate.

For this purpose, we first sort all tops of the remanining nodes of
$N_{AB}$ in ascending order of increasing abscissa. This is done in
time $O(n\log n)$.

Then we remark that if top $T_U$ dominate a non adjacent top $T_V$,
then any intermediary top $T_W$ dominate $T_V$, or is dominated by
$T_U$, or both. Hence, to eliminate all nodes/tops that are dominated,
on can simply proceed from left to right (by increasing abscissa),
comparing only adjacent nodes, and removing any that is dominated.  If
the node on the right is dominated, it is removed and the node on the
left is compared again to the next right. If the node on the left is
dominated, it is removed and the node on the right is then compared
with the previous one on its left. If none dominates the other, then the node on left
is kept, and the node on right
is then compared with the next right. This is repeated until the
rightmost node/top has been thus processed, in time $O(n)$.

Whatever nodes have been kept do contribute to the final curve, in
left to right order of their tops, with the line for $U_A$ at the left
and the line for $U_B$ at the right, if they exist. The minima are
easy to compute by considering the intersections of the contributing
curves from left to right, in time $O(n)$.

Finally, the abcissa for the smallest distance of all nodes to $C$ may be
found by a linear scan of all minima for the lowest ones. They may
actually be several such abscissa, i.e. values for the length $a$ of
edge $(A,C)$.

If the distances have to be integers, the abscissa of the minima can be
rounded up or down.

The time complexity of the algorithm is: $O(e+n\log n)$.

With thanks to user3153970 who remarked that my initial solution was
not quite correct.

Pseudo-code version

The procedure described in the analysis of the problem is modified or
improved in some ways.

the length l is changed to d to avoid confusion with the number 1.
for simplification, the V curve is replaced by two tops of roof curves placed on
both end of the interval [0,d].
the sets $N_A$ and $N_B$ need not be created. Only $d_A$ and $d_B$
are needed, briefly, to crate the two extra tops.
the set $N_AB$ is not created either, only the corresponding set
(actually a multiset, or bag, that may be implemented as a list) of tops, as two distinct nodes may
produce the same top, if at the same distance of A and B.

(bugs are provided free of charge)

d := distance (A,B)
none := -1     % programming trick - none is for distances to be ignored %
Remove the edge (A,B) from the graph.
Using Dijkstra's shortest path algorithm, for every node $U$ compute its shortest
    distances α(U) and β(U) to respectively A and B.
d_A := none
d_B := none
  % We use lists of pairs, representing the [x,y] coordinate of points, where the %
  % abcissa x stands for the choice of length (A,C), and the ordinate y stands is the %
  % distance of some node to C. %
  % The call first(L) returns a pointer to the first pair of list L. %
  % Given a pointer t to a pair, t.x and t.y give the two components of the pair, %
  % and the functions prev and next return a pointer to the previous or the next pair, or %
  % NIL if it does not exist. The call add([a, b], L) adds the pair [a, b] to the list L. %
  % The call remove(t) removes the element pointed by t from its list. %
For every node U do
T := []     % T is the list of tops of curves for individual nodes %
    if    α(U)+d ≤ β(U) then d_A := max(d_A, α(U))
    elsif β(U)+d ≤ α(U) then d_B := max(d_B, β(U))
    else add( [(β(U)-α(U)+d)/2, (β(U)+α(U)+d)/2], T)
% Instead of V curve, create dummy tops at ends of [0,d] interval %
if d_A ≠none then add( [d, d_A+d], T)
if d_B ≠none then add( [0, d_B+d], T)
Sort T in increasng order of abscissa
% Remove from T all tops that are dominated by another top %
t1 := first(T)
t2 := next(t1)
Repeat
    if abs(t1.x-t2.x) ≤abs(t1.y-t2.y)
    then  % one top dominates the other %
        if t1.y≥t2.y
            then  % t1 dominates %
            remove(t2)
            t2 := next(t1)
            if t2=NIL then exit loop
        else % t2 dominates %
            remove(t1)
            t1 := pred(t2)
            if t1=NIL then
                t1 := t2;
                t2 := next(t1)
                if t2=NIL then exit loop
     else % neither top dominate the other %
         t1 := t2
         t2 := next(t1)
         if t2=NIL then exit loop
% Compute all local minima %
M := []  % M is the list of minima, where roof shaped curves intersect, %
         % or intersect the boundaries of the interval [0.d]. %
t2 := first(T);
if t2.x≠0 then add( [0, t2.y-t2.x], M)
repeat
    t1 := t2
    t2 := next(t1)
    if t2=NIL then exit loop
    add( [(t1.y-t2.y+t1.x+t2.x)/2, (t1.y+t2.y+t1.x-t2.x)/2], M)
if t2.x≠d then add( [d, t2.y-d+t2.x], M)
Select in M the pairs with the smallest ordinates. Their abcissas are all
    the possible answers to the problem.

If the solutions must be in integer values, it is possible to round
the coordinates of the points in M to the nearest integer(s), before
selecting the pairs with smallest ordinates. However some more
analysis is needed to check whether it can involve passing over a top,
and whether abcissas and ordinates are always integer simultaneously.
This is left to the reader as an exercise.

All bug reports are welcome.


Can you generate random linear programming problems? I looked at Linear Programming, and it are problems like this:

You know that Cabinet X costs 10 cents per unit, requires 6 square feet
of floor space, and holds 8 cubic feet of files.
Cabinet Y costs 20 dollars per unit, requires 8 square feet of floor
space, and holds 12 cubic feet of files.
You have been given 140 dollar for this purchase, though you don't have
to spend that much. The office has room for no more than 72 square feet
of cabinets.
How many of which model should you buy, in order to maximize storage volume?

But you notate them in special form, so that you can genericly describe many of such problems.
Now suppose I replace all the values in this problem (10, 6, 8, 20, 12, 140, 72) with random other numbers, so I randomly create a completely new problem.

Do they take longer to solve, than to verify the solution?
Can I check that they are solveable without solving them?
Can I check how difficult they will be to solve, without solving them?

Sure, of course you can create random linear programming problems.  Why not?

Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution.  Verifying the solution just involves plugging into the equations and checking that all equations hold.  Finding the solution requires a bit more work (e.g., the simplex method, interior point method, ellipsoid method, something else).

However, as you may know, linear programming problems can be solved in polynomial time, and solutions can be verified in polynomial time.  Therefore, the difference between "time to solve" and "time to verify" is not as huge as for (say) NP-complete problems.

The best way to check that a linear programming problem is solvable is to solve it.  If you want a slight improvement, you can simply test whether the constraints admit any feasible solution.  The way you test feasibility is by omitting the objective function (or replacing it with a trivial objective function) and giving it to a LP solver; the solver will then tell you whether the linear program has a feasible solution or not.  If it has a feasible solution, then it is solvable; if it doesn't have any feasible solution, it isn't solvable.  In practice, testing for feasibility might be somewhat faster than solving it, for many problems.  However, there are no guarantees.  Based on theoretical work, we know that the worst-case running time to test for feasibility is approximately the same as the worst-case running time to find the optimal solution.

I know of no perfect way to test how difficult they will be to solve, other than solving it.  In practice, though, linear programming solvers are so efficient that a problem of the sort you list (with half a dozen variables and a dozen or so constraints) will be solved almost instantaneously, no matter what values you use -- so there is no point in trying to figure out how difficult it will be to solve.


DQQD algorithm for Frobenius numbers As a hobbyist problem-solver, recently I stumbled upon two problems related to Frobenius numbers on one of competitive coding websites I like: Zombie Apocalypse: the Last Number Standing and Matunga coins. I did some research (i.e. googling), found some information, and most notably a paper which describes a couple of approaches: Faster Algorithms for Frobenius Numbers. I succesfully managed to implement Round Robin, BFD and BFDU algorithms and with that I managed to solve the tasks (yay!). However I also wanted to implement DQQD(U) algorithms described there, and I cannot get the implementation right.

Pseudocode for BFD presented on page 9 is rather clear and I managed to implement it without any special problem. Adding one small update step I also got BFDU right. But with pseudocode for DQQD on p. 15, I always get to the point that first iteration seems to produce expected values like in example table, but things start to go wrong on second iteration.

Pseudocode as given in the paper:

Either I am getting things mixed up because of inconsistent indexing used in the paper (1-based for vector A, 0-based for other stuff), or
I am misinterpreting some ambiguous symbols (for example, w mutates through the iteration, and Qw can mean different things, depending on whether we use Qw determined on the beginning of the iteration, or we use different Qw every time w changes), or
there is a typo or some other mistake somewhere in the pseudocode, or
everything is OK there and it's just my mathematical ineptitude getting in the way. Unfortunately, I am not a mathematician, and theoretical basis for the algorithm is beyond my comprehension skills :( Maybe I should just GIT GUD?

I already tried changing here-or-there, but it was just a guessing game. I tried to find other implementations of DQQD, especially one in Mathematica, but they do not seem to be available. I also do not need to have the code written for me. All I need is someone to take a peek at pseudocode of DQQD in mentioned paper, and, if possible, try to implement it or verify it in any way if it's correct and I suck, or if it indeed has some typos, mistakes, or other issues.

Next step: overkilling the problem with FROBENIUS NUMBERS BY LATTICE POINT ENUMERATION :)

Try to undestand how the algorithm is supposed to work, and write your own, clean/consistent pseudocode (or directly Python) from it.

You already searched for implementations, look for comments on this paper. You might find corrections published elsewhere...

It is unlikely, but possible, that the given pseudocode or even the proposed algorithm itself is wrong. Mistakes happen.


n! mod p Fast Factorial I need to find N! (mod 232-5) such that 0 ≤ N ≤ 264 for i cases, 0 ≤ i ≤ 1000 in 1 sec.

Credits: https://dmoj.ca/problem/factorial2

I am aware that I only have to handle 0 ≤ N ≤ 2 ≤ 232-6 because once N ≥ 232-5, N!≡0 (mod 232-5) . A naive solution would take O((232-6)*1000). I have also tried using Wilson’s Theorem and a naive solution, which would run in approximately O(4000000000*1000) time (Calculated from the highest point when O(N) intersects with O(232-5-N)log(N))).

I cannot find a solution to this problem with a fast enough run time.
Any help would be appreciated.

First use Yuval's advice: With p = 2^32 - 5, remove all N ≥ p (the result is 0), then sort the rest, so now you have up to 1,000 numbers in sorted order from 0 to p-1. This is trivial to do by multiplying up to almost 2^32 numbers modulo p and recording results at the right moment; that's not much above a second worth of work but more than a second.

Let's say you have r processors, and you want to use them simultaneously. The largest number is t < p. You make each processor responsible for multiplying s = ceil (t / r) numbers. For example if r = 8 and t = 2^32 - 6, then s = 2^29. Processor 0 multiplies numbers from 1 to s, processor 1 multiplies numbers from s+1 to 2s and so on. Let's say one of your N's is 3s + 15900: Processor 3 multiplies 3s+1 to 4s. At some point you record the product of numbers 3s+1 to 3s+15,900. And when all the processors are done, you multiply with the final results of processors 0, 1 and 2.

You may have vector units being able to do for example 4 operations in parallel. In that case, you would multiply r by 4, and have 8 processors calculating 4 results simultaneously.

Say you have calculated x (x+1) modulo p, the product of two numbers. How can you get (x+2)(x+3) modulo p, the next product? (x+2)(x+3)-x(x+1) = 4x + 6, so the product modulo p changes by (4x + 6) modulo p. Let d(x) = (4x + 6) modulo p. As you increase x by 2, d(x) changes by 8 (modulo p), so the products x(x+1) modulo p, (x+2)(x+3) modulo p, (x+4)(x+5) modulo p etc. can be calculated very quickly. I think that should be enough to get you below one second.

Some additions: One, if p = $2^{32}-5$ is not prime, that makes the problem just faster to solve. If all prime factors are ≤ $p^{1/2}$ then the problem is trivial because N! = 0 (modulo p) if N ≥ $2^{17}$ (must be careful in case p is the square of a prime). Otherwise let p = a·q, where a ≥ 2 and q is a prime q ≥ $p^{1/2}$, then we can calculate N! modulo p easily from N! modulo a and N! modulo q. Since $a ≤ 2^{16}$ and N! modulo a = 0 if N ≥ a, calculating N! modulo a is trivial (only 65535 products needed). b would be at most half as large as p, making the problem at least twice as fast to solve. After applying this, we can assume p is prime.

Two, Wilson's Theorem lets you cut the time in half. We now assume p is prime (having cut down the time earlier if the original p wasn't). Wilson's Theorem says (p-1)! = -1 (modulo p). Now say we want to calculate (p-k)! modulo p. We have obviously (p-k)! · ((p-k+1)·(p-k+2)· ... · (p-1)) = (p-1)!. This product is equal to (p-k)! · (-(k-1))·(-(k-2))· ... · (-1)) = (p-k)! · (k-1)! · (-1)^(k-1). The result modulo p is -1, so (p-k)!·(k-1)! = (-1)^k modulo p. So if p/2 ≤ N < p, then we let k = p - N, calculate (k-1)! modulo p, and solve N! · (k-1)! = (-1)^k modulo p. The problem is now mostly reduced to the problem of calculating N! modulo p for about 1,000 values 0 ≤ N ≤ p/2 ≤ $2^{31}$.

Three, Yuval's idea using a table with pre-calculated values N! modulo p will work if the task is to solve the problem for fixed p and different sets of 1,000 values N. If there are 1,000 values N you need 1,000k precalculated values to save a factor k. It doesn't work if p is variable.
And if it is possible to use multiple processors or vector units to do k calculations in parallel, then a factor k in time can be saved. Without these savings, it's 2 billion products modulo p in 1 second.

One idea is factoring N! into a product of powers primes. There are less than 100 million primes < $2^{31}$. However, since we have 1,000 values $N < 2^{31}$, I think many primes will have to be multiplied multiple times. Doing this in one second is tough.


Partitioning a Number on the basis of an equation I have an equation $x = 3a+4b+2c+4d$, where $a$, $b$, $c$ and $d$ are nonnegative integers such that $a+b+c+d=5$.
What algorithm can I use to calculate maximum value of $x$?

Non-negative means that they can be 0. So set everything to $0$ except $b$ and $d$ because they have the highest coefficient.

$x=3*0+4b+2*0+4d$ and $0+b+0+d=5$

$x=4b+4d$ and $b+d=5$

$x=4(b+d)$ and $b+d=5$

$x = 4*5 = 20$


Language of a Turing Machine that runs its input on two other Turing Machines Given two Turing Machines M1 and M2, we build a new machine M that does the following on input x:

Run M1 on x. If M1 accepts x, then go to an accept state.
Run M2 on x. If m2 accepts x, then go to an accept state.

What would be the language of such a Turing Machine? My first intuition was that $L(M)=L(M1) \cup L(M2)$ , but this can't be the case since if $x \notin L(M1)$ and $x \in L(M2)$, then there is the possibility that M1 runs forever, so M2 will never get the chance to recognize x and go to an accept state.

Unless we assume that M1 never runs forever, how is it possible to express $L(M)$? Thanks!

You're right: it might happen that $M_1$ might run forever on input $x$, so you'd never get to the "run $M_2$ on $x$" part. This problem goes away if $M_1$ and $M_2$ were deciders, i.e., if they are guaranteed to halt on any input in either an accept state or a reject state. In that case we would have $L(M)=L(M_1)\cup L(M_2)$ and would have proven that decidable (aka recursive) languages are closed under union.

All is not lost, though, to show that this holds for more general languages. Suppose that we know that we have languages $L_1,L_2$ such that there are TMs $M_1, M_2$ with $L_1=L(M_1)$ and $L_2=L(M_2)$. Then we can make a TM $M$ such that $L(M) = L_1\cup L_2$ by a very useful technique known as dovetailing, like this

M(x) =
   repeat
      run M_1(x) for one move (beyond any that have been made already)
      if M_1 accepts
         return accept
      run M_2(x) for one move (ditto)
      if M_2 accepts
         return accept
   // end repeat

If either $M_1$ or $M_2$ accepts $x$ then it will do so in some finite number of moves, and that's all we need for $M$ to accept $x$. So for this machine, we'll have $L(M)=L(M_1)\cup L(M_2)$, exactly as needed.


Functional dependencies on relational schema Given a relational schema $R(V,W,X,Y,Z)$ with functional dependencies $F = \{VW \to X, X \to YZ, W \to VX, V \to W, Z \to XY\}$. What are the keys of $R$?

Is the key just $V$? If so,  is $\{ R_2(V,W,Z), R_3(V,X,Y) \}$ the lossless-join decomposition of $R$?

I assume, by key, you mean the candidate key.

Let's check whether V is a candidate key:

closure(V) = {V, W, X, Y, Z}

Hence, V is a candidate key.

closure(W) = {W, V, X, Y, Z}

Hence, W is also a candidate key.

closure(X) = {X, Y, Z}

closure(Y) = {Y}

closure(Z) = {Z, X, Y}

By checking all the other possible keys, one can see that only V and W are candidate keys.

The lossless-join decomposition of R does not have to be unique.

One can be described as follows:

R = {R1(V, W, X), R2(X, Y, Z)}

Since R1 ⋂ R2 = {X} And X -> {X, Y, Z}.

Hence, X -> R2.

Hence, R1 ⋂ R2 -> R2. Hence, this decomposition is a lossless join decomposition.

R2 can be further divided as
R2 = {R3(X, Y), R4(X, Z)}

Similarly, R1 = {R5(V, W), R6(W, X)}

Hence R = {R5(V, W), R6(W, X), R3(X, Y), R4(X, Z)}


If $L$ is regular then $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free I have found a problem about proving whether $L^{|2|}=\{w_1w_2 \mid w_1,w_2\in L, |w_1|=|w_2|\}$ is context-free or not, knowing that $L$ is regular
So far I know that:

There are examples where $L$ is regular and $L^{|2|}$ is regular (for example $L=\{a,b\}$)
There are examples where $L$ is regular and $L^{|2|}$ is not (for example $L=\{w \mid w=a^N \text{ or } w= b^N\ , N\ge0\}$)

But I am not sure how to prove that it's context-free regardless of which regular language I use. I have found similar problems with the same language without imposing restrictions on which words to use, but I am not sure if those apply to this one.

Let $\Sigma' = \{\sigma' : \sigma \in \Sigma\}$ be a tagged version of the alphabet of $\Sigma$. Let $L'$ be a version of $L$ obtained by tagging all letters. Let $h\colon \Sigma \cup \Sigma' \to \Sigma$ be a homomorphism which removes tags. Then
$$
L^{|2|} = h(LL' \cap \{xy : x \in \Sigma^n, y \in \Sigma^{\prime n} \text{ for some } n\}).
$$
Standard closure properties of context-free languages imply that $L^{|2|}$ is context-free.


Random observations of a total ordering, how much they tell us? Suppose we have a total ordering over elements $a_1,a_2, ..., a_n$, meaning there is permutation $\pi$ such that $a_{\pi(1)}<a_{\pi(2)}<...<a_{\pi(n)}$. But we don't know $\pi$. What we know is a set of random observations from pairwise order of the elements. The observation matrix $B\in\{0,1\}^{n\times n}$ is  generated randomly as follows:
$$B_{i,j} \sim \begin{cases} \text{Bernoulli}(p)\qquad  \text{ if } i>j \\ 0  \qquad \qquad \qquad \text{ otherwise} \end{cases}$$
in which $p\in[0,1]$ is a constant. The formula above means that elements above diagonal are drawn iid from $\text{Bernoulli}(p)$ and the rest of the elements are $0$. Matrix $B$ denotes our observations of the ordering, i.e. if $B_{i,j}=1$ we know the the the order of $a_i$ and $a_j$, and otherwise don't. The reason that elements on the lower triangle of $B$ are zero is because symmetric observations are reduntant.

Question 1

Let $K$ denote the number of orderings of $a_1,..., a_n$ that are consistent with our partial observations. Since $B$ is a random variable, $K$ is also a random variable. The question is, what the expected value of $K$ and what is its concentration around the mean as a function of $p$? There are two extreme cases: (1) if $p=0$ all orderings are valid and hence $K=n!$ (2) if $p=1$ we have the complete ordering and $K=1$.

For $0<p<1$ however $K$ would not be a constant. My guess is that for sufficiently large $n$ if $p\gg \mathcal{O}(\frac{\log n}{n})$ would lead to to $\mathbb{E}[K]\to 1$. The rationale behind this is that we would have $\omega(np) = \omega(n \log n)$ comparisons which is an asymptotically larger than the number of comparisons most sorting algorithms make. However, this is far from clear since the observations are taken at random.

The answer is ideally a distribution with parameter $p$ for the number of possibilities. But if that's not possible, tail bounds or the expected value and variance are also acceptable.

Question 2

The motivation behind the definition of $K$ was to capture how much uncertainty is left. But it seems to be overestimating it or not express it very well, because if we don't know a few pairs $K$ will grow exponentially with this number. So I was thinking of another natural way to define it.

Let $O\in\{0,1\}^{n\times n}$ be the result of our observations, in which $O_{i,j}=1$ designates that we have observed $a_i<a_j$. From this matrix we can compute the transitive closure $O^\star$, which applies transitive property to find all the "smaller-than" relations in the data. For example if we have $O_{i,j}=1$ and $O_{j,k}=1$ we will have $O^\star_{i,k}=1$. This holds also for a chain of arbitrary length.

Let $S$ be the sum of all elements of $O^\star$. If we can conclude the relations between all pairs, $S$ will attain its maximum value of $S=n(n-1)/2$, and so $I=\frac{S}{(n(n-1)/2)}$ is a value which will show how much we know about the ordering, with $1$ meaning we exactly know the ordering, and $0$ meaning we don't know anything. Now the question is: what is its mean $\mathbb{E}[I]$ as a function of $n$ and $p$? And if it's possible to analyze, what is the concentration of $I$ around its mean? Also, what is the threshold for $p$ as a function of $n$ that makes $\mathbb{E}[I]$ jump to $0$ or $1$?

By simulations I found that when $n\to\infty$, even for a small value of $p=\frac{\log n}{n}$ leads to $I\to1$ with high probability. The reason for this seeming discrepancy between $I$ and $K$ is that if we have $m$ unknown pairs in $O^\star$, then $K$ will grow exponentially w.r.t $m$ while $S$ will only be affected linearly. Although the $I$ and $\log K$ are related, I don't think there is an exact relationship between them.

Answer to Question 1

We can assume without loss of generality that the original ordering is the usual one: $a_1 < a_2 < \cdots < a_n$. Some ordering $\pi$ is compatible with our observations if whenever $\pi(i) < \pi(j)$ for some $i > j$, this observation is missing. In other words, $\pi$ is compatible with probability $(1-p)^{\operatorname{inv}(\pi)}$, where $\operatorname{inv}(\pi)$ is the number of inversions of $\pi$. Using the generating function of the number of inversions, we get that the expected number of compatible orderings is exactly
$$
\mathbb{E}[K] = \prod_{m=2}^n \frac{1-(1-p)^m}{p}.
$$
In the same way you might be able to compute larger moments of $K$, and so obtain some concentration bounds. Whether one should expect good concentration, and for which values of $p$, remains to be seen, though perhaps it's best to perform some numerical experiments to get a feel for how this behaves.

Answer to Question 2

Let $q_\delta$ be the probability that $O^*$ contains $(i,i+\delta)$. We can compute by brute force
\begin{align*}
q_1 &= p, \\
q_2 &= p + p^2 - p^3, \\
q_3 &= p + 2p^2 - p^3 - 4p^4 + 4p^5 - p^6, \\
q_4 &= p + 3p^2 - 11p^4 + p^5 + 30p^6 - 42p^7 + 26p^8 - 8p^9 + p^{10},
\end{align*}
and so on. Consulting the OEIS, we find the sequence of coefficients (for $-q_\delta(-p)$) as A214670.

Given the $q_\delta$, it is easy to compute the expectation of $I$, though since there isn't a particularly nice formula for $q_\delta$, this won't result in a reasonable formula for $\mathbb{E}[I]$.

You could ask for the threshold behavior of $\mathbb{E}[I]$, that is, at what value of $p$ does the expectation jump from 0 to 1, and how quickly. This is a different and interesting question.


Distibutional problem Given: $n$ tasks with accomplishment times $t_1, t_2, \ldots , t_n$. There is no such task that its accomplishment time is greater than the overall accomplishment time of other tasks.

Question: How to distribute these tasks between two workers in a such way that $|T_1 - T_2|$ is minimum ($T_i$ - the overall accompl. time for the $i$-th worker accordingly).

We will use the local search algorithm, starting with a random distribution and redistributing one task on every step only if it leads to reducing $|T_1 - T_2|$ as long as it's possible.

Does this algorithm find the optimal distribution or is there any counterexample?

We can consider the more general problem of makespan, in which we wish to partition the tasks into $m$ sets as evenly as possible (your case is $m=2$). We measure the quality of our solution using the maximum total sum of a set, which we wish to minimize. Finn and Horowitz showed that the locality gap for this problem is $2-2/(m+1)$. This means that a locally optimal solution has objective value larger by a factor of at most $2-2/(m+1)$, and moreover there are examples in which the ratio approaches $2-2/(m+1)$. In particular, local search doesn't always give the optimal solution.

For other local search algorithms for makespan, consult the survey of Schuurman and Vredeveld.


smaller size approximation to minimum vertex cover Does there exist a simple approximation to the minimum vertex cover problem that aims to find a smaller (or equal) set to the minimum?

Usual algorithms seems to aim to find an approximation such that the output is a cover, but may have more vertices than the minimum cover. Instead, I want a smaller set - I don't mind if some edges are still left and is therefore not a cover. Between two smaller sets, the one that covers more (total number of edges) is preferable.

Do you want a set whose size is a lower bound? Or do you want a lower bound on the size?

If you want a set, does it need to be a subset of a minimum vertex cover, or just a smaller set (in the latter case, any set of the appropriate cardinality would do)?

Since there is a well-known approximation algorithm that is a factor of two over-approximation, you can divide the result by two to get a factor of two under-approximation. In fact, these notes use a lower bound to prove the over-approximation factor.


How to correctly describe this action, deleting an edge that "shortcut" some vertices Haven't written a proof in years, not sure how to describe an algorithm like this ? Let us what we have a graph. like this below:

1). How to describe edge removal of{ (0, 1),(3,4), (1,2) }done in linear time ?  Basically, we don't want any edges that shortcuts our visit as every vertices need to be visited.

Here is something:
Such edge removal can be achieved in linear time by scanning trough all the vertices in graph in the topological order, and for every outgoing edge(a, c) of v checking if the b comes after the vertex。

How can I correctly describe that if an algorithm remove (0,1),(3,4),(1,2) edges in this graph?

Your operation replaces your graph with one of its directed spanning trees. See for example lectuire notes of Uri Zwick.


What is the relation between EXPTIME and NP HARD complexity classes? Need to know the relation between EXPTIME and NP HARD complexity classes.

There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, however, and NP-complete is of course contained in NP.


Question about set-associative cache mapping I found a question:

  Let a two-way set-associative cache of 4 memory blocks, each block containing one word.

  What is the number of misses and hits considering the following sequence of block addresses: 0, 8, 0, 6, 8 ?

  a) 4 misses and 1 hit
  b) 3 misses and 2 hits
  c) 1 miss and 4 hits
  d) 2 misses and 3 hits

Although I understand how set-associative cache mapping works, I don't understand how can you tell if it will be a hit or a miss if you don't know the tags and what is stored on the cache memory.

Can you please point me in the right direction? How should I think about this problem?

You're absolutely right: the question is unanswerable as stated because you don't know what's in the cache at the start of the sequence of memory accesses. You're probably expected to assume that the cache is initially empty but, if this is an exercise you've been set, you should ask your instructor to clarify.


Decidability of checking whether all words accepted by a TM have an even number of 1s Let $\Sigma = \{0,1\}$, and consider the language
$$L = \{\langle M \rangle \mid
M \text{ is a TM and } L(M) \text{ is a subset of } Σ^* \text{ and all strings in this set have an even number of 1s}\}.$$

I think $L$ is undecidable. But I am stuck on proving it. I think it is equivalent to prove $L = \{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a specific set with an even number of 1s}\}$ is undecidable. How can I do some reduction for it?

First, it can be shown easily by Rice's theorem.

Alternatively, you can show a reduction from $\overline{HP}$ as follows:

$$f(\left< M \right>,x)=\left<M_x\right>$$

$M_x$ on input $w$:

run $M$ on $x$ for $|w|$ steps.
if M stopped then accept.
if the number of 1's in $w$ is even then accept, otherwise reject.

I'll let you verify the correctness.


Why do we consider enumeration up to $\omega$ instead of leaving it to as many ordinal numbers? A few minutes ago I asked a question about a "proof" that $\mathbb{R}$ is enumerable that crossed my mind: What's wrong with this "proof" that $\mathbb{R}$ is enumerable?
I was told to look into ordinal numbers, and that after crossing $\omega$ we stop considering something to be an enumeration.
Why is this the case? Are there negative consequences if we don't put this limitation?
Edit:
I always thought of $\mathbb{N}$ as the "counting numbers" - but... when we cross over to ordinals like $\omega$, $\omega+1$, etc, aren't we still effectively counting?

A set $S$ is enumerable (or, countable) if we can enumerate it:
$$
S = \{s_1,s_2,s_3,\ldots\}
$$
In other words, there is a mapping from $\mathbb{N}$ onto $S$.
Cantor showed that $\mathbb{R}$ isn't enumerable.
We can consider more relaxed notions of enumeration. For example, a set $S$ is well-orderable if there is a linear order $<$ on $S$ such that any non-empty subset of $S$ has a minimum. This encompasses your examples, and much more.
The axiom of choice is equivalent to the well-ordering principle, which states that every set can be well-ordered. Hence if you assume the axiom of choice, every set can be enumerated in this sense.


std::hash and separate chaining I'm attempting to implement my own generic hash table using separate chaining.  I'm using the std::hash() method to create my hash function.  I noticed in the description of std::hash() that:

For two different parameters k1 and k2 that are not equal, the probability that std::hash()(k1) == std::hash()(k2) should be very small, approaching 1.0/std::numeric_limits::max()

Does this mean that given any two unequal strings, std::hash() will more than likely not select the same bucket?  Does this mean my attempt to implement the hash table using separate chaining is moot considering this?

I'm implementing my hash table as a vector of lists.  I thought there would be more collisions and therefore more elements in each list, but using the above function pretty much always gives me only one element in each list.

Please let me know if I'm misunderstanding this.  Thanks.

No, 1/numeric_limits::max() is the probability that two randomly picked objects have same hash code, not more.

Probability of collisions during insertion into hash table is calculated differently.

Given your vector has size M (i. e. $M$ buckets), and you already inserted $N$ entries into the hash table, the fraction of empty slots, i. e. the slots with zero entries, is $e^{-N/M}$, because in hash tables with separate chaining slots with 0, 1, 2, ... entries are Poisson-distributed. This means that the probability of any collision during inserting N+1-th entry is $1 - e ^{-N/M}$.

For example, if your vector has size 64 and you inserted 32 entries, probability of collision during insertion 33-th entry is $1 - e ^{-0.5} \approx 0.39$.


Any common problems solvable by DFA/NFA or PDA except recognizing languages? I understand that DFAs recognize regular languages, and PDAs context-free languages, but these are a little bit too theoretical. I am wondering if we can implement common functions or solve common problems with DFAs and PDAs instead of Turing machines (or in a Turing-complete language).

By "common", I mean either one of the following:

problems like those in algorithm analysis and data structures, i.e. sorting, shortest path, etc.
functions seen in the everyday work of a common programmer, probably some useful business logic.

In imperative programming, state machines are quite common, and they usually look more or less like the following pseudo-code:

state = INITIAL_STATE;

while (token = read_an_input_token(input))
{
   if (state == STATE_1)
   {
      if ([some condition on the token])
      {
         [some actions]
         state = [some state]
      }
      else if ([another condition on the token])
      [etc.]
   }
   else if (state == STATE_2)
   [etc.]
}

if (state != ACCEPTING_STATE)
{
   [error handling, perhaps abort]
}
else
{
   [apply finishing touches]
}

All kinds of variations may occur: you'll see case statements being used in languages that have them, the order in which the conditions are tested and the way they are grouped may vary, more input scanning may occur than just reading separate tokens, et cetera.

You're likely to see similar loops wherever a regular language needs to be parsed. For instance, command line utilities usually parse their arguments in this way. (Mine do, anyway.)

There are other approaches to using state machines in software; I think this is the most popular and most informal one.


Is the algorithm implemented by git bisect optimal? Let $G$ be a DAG. We know that some nodes in $G$ are "bad", while the others are "good"; a descendant of a bad node is bad while the ancestors of a good node are good. We also know that bad nodes have a unique minimal element in $G$ which we'd like to find querying as few nodes as possible with queries of the type "Are you good or bad?".

This problem is solved in Git, the popular version control system, by the command git-bisect, which helps a programmer find the first commit in which a bug was introduced.

At the start, the algorithm implemented by Git assumes to know a single bad commit and one or more good commits. At each step of its execution, the algorithm finds a commit using the following steps (taken from here):

Keep only the commits that:

a) are an ancestor of the bad commit (including the bad commit itself), and

b) are not an ancestor of a good commit (excluding the good commits).
Starting from the good ends of the resulting graph, associate to each
commit the number of ancestors it has plus one.
Associate to each commit $\min(X, N-X)$, where $X$ is the value associated to the commit in step 2, and $N$ is the total number of commits in the graph (after it was reduced in step 1).
The best bisection point is the commit with the highest associated
number.

This algorithm is essentially finding the commit that achieves the "worst best case": in fact, $\min(X,N-X)$ is the number of nodes in the DAG at the next iteration in the best case, thus $\max\min(X,N-X)$ is the worst best case.

I'm wondering:

Does it make any difference if we select the "best worst case", that is, the node that achieves $\min\max(X,N-X)$?
Is this algorithm worst-case optimal?

EDIT: I've noticed that this problem has a $\Omega(N)$ bound. Consider the DAG formed by a single node $b$ with $N-1$ parents called $g_1,\dots,g_{N-1}$. If we know that $b$ is bad then we have check each of the parents to see if they are the minimal bad node.

EDIT 2: The previous is actually a $\Omega(w)$ bound, where $w$ is the width of the poset. An alternative algorithm for this problem is given in this answer on cstheory.stackexchange that uses $O(w\log{n})$ queries.

Here's some intuition for what $X$ and $N$ are doing.  Focus on a particular commit $c$.  Suppose we test $c$ and classify it as either "good" or "bad".  Until we test it, we don't know whether it is good or bad, but we can predict in advance how much smaller the graph will get in each of those two cases.  In particular, $X$ is the number of commits that would be trimmed away if commit $c$ turns out to be good, and $N-X$ is the number of commits that would be trimmed away if commit $c$ turns out to be bad.

Therefore, the value $\min(X,N-X)$ is a lower bound on the number of commits we'll be able to trim away in the next step, no matter how the test turns out.  The idea of the Git algorithm is to maximize of this metric.  In other words, Git picks a threshold $t$ that is as large as possible, and a commit $c$ to test next, such that Git can be sure that it'll be able to trim away at least $t$ commits in the next step.

If we have no information about whether each commit is likely to turn out good or bad, so it's equally likely that it's good or bad, then this looks like a locally optimal choice.  Thus, the Git algorithm is a greedy algorithm.

Is the Git algorithm globally optimal?  That will depend upon the definition of "optimal", and (probably) on the distribution of DAGs one encounters in practice.  Probably there is no simple characterization of the probability distribution on DAGs one encounters in practice, so I'd expect it is probably going to be difficult to find an optimality result for this problem.


TM decidable or undecidable problem Problem:

  Given a TM $M$ on the alphabet $\{0,1\}$, determine if there is some input  on which $M$ executes for at least 5 steps.

Is this problem decidable or not?

To check if the problem is decidable or undecidable, I describe an algorithm as follow:

$A$: on input the TM $M$

$A$ generates all strings $w$ of length at least 5 characters.
For each string $w_i$, $A$ runs $M$ on $w_i$ and checks whether it performs at least 5 steps. If yes, $A$ accepts, otherwise $A$ repeats the control on the string $w_{i+1}$.

Algorithm $A$ could run forever, and so one could not tell whether $M$ performs at least 4 steps on some input string. The problem sounds to me undecidable. However I can build a complementary algorithm of $A$ (i.e. $A'$) and I can build a new algorithm $B$ using $A$ and $A'$ in parallel. In this case the problem sounds to me decidable.

Your problem is decidable. If $M$ always executes less than 5 steps, then it never sees more than the first 4 symbols of its input. Hence it suffices to run $M$ on all inputs of length at most 4.


DAG for contiguous subsequence of maximum sum I have trouble understanding DAG behind the "contiguous subsequence of maximum sum problem". Let's say I denote by S(i) maximum of sums of contiguous subsequences ending in i. So S(i) are my subproblems. To calculate S(i) I need S(i-1) so the edge will be between node i and i-1. Denoting the sequence by a_i, I think my DAG will look like this:
a_1 -> a_2 -> ... -> a_n
I feel like this doesn't tell me anything. In Chapter $6$ of the book Algorithms (Dasgupta et al.), they find a correspondence between problem and edges in the graph. I don't really see that here. I don't know if I grasped the idea of DAG right, something feels off.

You grasped the idea right. For the problem of finding "contiguous subsequence of maximum sum", the DAG is indeed $a_1 \to a_2 \to ... \to a_n$, since the sequence is contiguous.
To get a better feel for DAG, you should consider the problem of finding an "increasing subsequence of maximum sum" problem. By increasing subsequence, I mean that $a_{i} \leq a_{j}$ for any two consecutive elements $a_{i}$ and $a_{j}$ in the sequence.
Note that, an increasing subsequence might not be contiguous. And, to calculate $S(i)$, you will need $S(j)$ such that $a_{j}\leq a_{i}$. So there will be an edge between the nodes $j$ and $i$ if and only if $a_{j}\leq a_{i}$ and $j < i$. You will get your DAG. Here, DAG might not contain the edges between $a_{i}$ and $a_{i+1}$, as it was in the previous problem.
You can also consider the problem of finding the "subsequence of maximum sum". Here the subsequence is neither contiguous nor increasing. Here DAG will contain an edge between every pair of nodes $a_{i}$ and $a_{j}$ for $i<j$. And, the maximum value is trivially the sum of all positive values in the array.


How can we get small test error reducing only train error? My question is about mathematical part of machine learning algorithms, especially about using it in neural networks. We train network reducing train error and I was thinking about how then test error is also small (discarding overfitting and underfitting), what is mathematical proof for it. I found about that in this book http://www.deeplearningbook.org, chapter 5.2. Here is a part of that chapter:

  How can we affect performance on the test set when we can observe only
  the training set? The field of statistical learning theory provides
  some answers. If the training and the test set are collected
  arbitrarily, there is indeed little we can do. If we are allowed to
  make some assumptions about how the training and test set are
  collected, then we can make some progress. The training and test data
  are generated by a probability distribution over datasets called the
  data-generating process. We typically make a set of assumptions known
  collectively as the i.i.d. assumptions. These assumptions are that the
  examples in each dataset are independent from each other, and that the
  training set and test set are identically distributed, drawn from the
  same probability distribution as each other. This assumption enables
  us to describe the data-generating process with a probability
  distribution over a single example. The same distribution is then used
  to generate every train example and every test example.

I want to transfer this theoretical part to a more concrete example for better understanding. Assume we have images and we need to select train and test datasets. My questions are

What the author means by "example"? Is it every image? If yes, is that mean, that we consider every image as a random variable and every time it selected or not?
I totally can't understand why we need to do this assumption: "the examples in each dataset are independent from each other". Maybe I misunderstood the example part in my first question and it's come from that.
If the training set and test set are identically distributed why always in practice the training set is about 90% of all data and the test set is 10%, I can't see identical distribution in this situation.

Also, I would be glad if you will give me some references to read about this in other books/topics.

Yes, if you are classifying images, each example would be an image.  There is some distribution on images that are likely to arise in practice.

We need independence and identical distributions because without it we can't learn.  If we practice five times, but then are tested on something entirely different, our practice might not be useful.

The distribution refers to the distribution of each single image.  That has nothing to do with how many images you draw from that distribution.  Imagine flipping a biased coin.  I could flip the coin 100 times; each outcome would be a sample from that (biased) distribution, and that's true whether we have 10 coin flips or 1000 coin flips.


Valid bit incoherence between TLB and Page Table In the fourth row of the TLB the valid bit is 0. The corresponding row in the pagle table (fifht row) has the valid bit 1. How is this possible? What events leads to this incoherence?

The typical scenario where this kind of incoherence can occur is when the page table has been changed. In this case, an invalid PTE has become valid; perhaps the area of address space has been allocated, or a page has been swapped in.

"But", I hear you say, "why wasn't the TLB entry flushed when the PTE changed?" Well, it probably was, but the change may have happened on a different core.

The way this is typically handled in a multiprocessing operating system is to perform a "TLB shootdown". The core which changed the PTE issues an inter-processor interrupt (also known as a "crosscall") to any other CPU which may have a copy in its TLB to instruct it to flush.

An inter-processor interrupt is an expensive operation. But, of course, it doesn't need to happen a lot of the time. For example, if the other CPU is not currently using an address space which uses the TLB entry, it can't possibly access the entry until it performs a context switch, so the flush can be delayed until the next time the CPU enters the kernel (say).

But even if the other CPU is using the address space right now, you still don't need to perform a shootdown in this specific case, because the stale TLB entry is invalid. Attempting to access it will cause a page fault, so any attempt to use the stale TLB entry will be resolved by the page fault handler. And if that never happens, you've saved yourself a costly inter-processor interrupt.


Theoretical lower bound of finding number of occurrences of a target integer in a sorted array Given a sorted array of integers and a target integer, find the number of occurrences of the target integer.

It is well-known that a binary search has time complexity $O(\lg n) $ where $n$ is the size of the array.
For example, given an array $[1,2,3,3,4,5]$ and a target $3,$ the algorithm should return $2$ since there are two copies of $3$ in the array.

  Question: Is there a faster algorithms which has time complexity less than $O(\lg n)?$ Otherwise, is there a proof to prove that $\Omega(\lg n)$ is the theoretical lower bound?

The problem requires $\Omega(\log n)$ accesses to memory even if you are promised that the target integer appears at most once. You can prove it using an adversary argument.

Say that the target is zero. If the first access to the array is left of center, answer $-1$, and mentally set the elements to the left to be $-2,-3,\ldots$. If the first access is right of center, answer $+1$, and mentally set the elements to the right to be $2,3,\ldots$.

Suppose the first access was right of center, say position $i$, and consider the second access. If it it to the right of the first access, then you already know what to answer. Otherwise, there are two cases. If the accessed position $j$ is less than $i/2$, answer $-1$ (and fill in elements to the left). If it was more than $i/2$, answer $+1/2$ (and fill in elements to the right up to position $i$).

Continuing in this way, at each step the number of positions which could contain the target element is at most halved at each step. Finally, when only one element is still at stake, without querying it, the algorithm cannot know for sure whether the array contains the target element or not. It takes $\log_2 n$ steps to reach this step.

The foregoing actually shows that binary search is optimal for searching a sorted array.


Why is unification so important to inference engines? I am learning Automated Theorem Proving / SMT solvers / Proof Assistants by myself and post a series of questions about the process, starting here.

I keep reading about the Unification Algorithm.

What is it and why is so important to Inference Engines?
Why is it so important to Computer Science?

Unification is such a fundamental concept in computer science that perhaps at time we even take it for granted. Any time we have a rule or equation or pattern and want to apply it to some data, unification is used to specialize the rule to the data. Or if we want to combine two general but overlapping rules, unification provides us with the most general combined rule. Unification is at the core of

Theorem provers and proof assistants, include some based on higher-order unification.
Prolog implementations (as Resolution).
Type inference algorithms.
Computational linguistics/natural language processing.
Term rewriting systems such as Maude,  which can be used as the basis of programming language semantics.
Deductive databases.
Expert systems or more generally Artificial intelligence.
Computer algebra systems.
Pattern matching in functional languages (at least in part ... only matching).
Some parsing approaches.
Some query languages, especially involving the Semantic Web.


Questions on the definition of polynomial time I been reading Wikipedia for polynomial time, and it says:

  An algorithm is said to be of polynomial time if its running time is
  upper bounded by a polynomial expression in the size of the input for
  the algorithm, i.e., $T(n) = O(n^k)$ for some constant $k$.

My questions are:

Why do we have addition and multiplication but no division?
Why do we have both multiplication and addition, couldn't we express one with the other?
What is the difference between polynomial time and exponential time by definition?

You seem to be struggling with a lot of the fundamental concepts, here. All the NP-completeness stuff is cool and fascinating and I can absolutely see why you're attracted to it. But you really aren't going to get anywhere with this stuff until you have a good grasp of the basics. If you want to work on NP-completeness, you need first to get a good book on basic discrete mathematics and you need to study it until you understand it. I know that's kind of dull but there is no other way. There might be a question here already about recommendations for discrete maths books.

This is a technical, precise subject where every little part of every little sentence has some special meaning. It's not like, say, the rules of some sport that you can pick up more or less just by watching people play.  Yes, you can get a general, intuitive understanding of why, say, an NP-complete problem seems to be very hard to solve, in just the same way that you can get a general, intuitive understanding of how quantum tunnelling allows radioactive decay to happen.  But, if you want to discover new things about it, you need to understand the underlying mathematics.  There is no other way.

If all you want to do is talk about the running time of algorithms, you don't need to worry about polynomial expressions; just about polynomials. Polynomial expressions are generalizations of polynomials to be functions of things other than numbers.  Over numbers (integers, reals, complex, anything else), the polynomials are the functions of the form
$$f(x) = a_kx^k + a_{k-1}x^{k-1} + \dots + a_1x + a_0\,,$$
where $k$ is an integer constant and the $a_{i}$ are constants of the same kind of number as $x$ will be.

1. Why do we have addition and multiplication but not division?The unhelpful answer is "Because that's the definition," just like CNF is defined using AND and OR rather than, say, XOR and NOR. The reason for forbidding division is that you might want to have a polynomial in a situation where division doesn't make sense (e.g., if you're working mod 2, or $x$ is an integer and you want to guarantee that $f(x)$ is also an integer). The kind of function you can make by dividing one polynomial by another is called a rational function and these are also widely studied and very useful in many situations. Why don't we use rational functions instead of polynomials in complexity theory? It's mostly because we don't need that level of detail: we already say that $4x^3 + 2x + 1$ is basically just some constant times $x^3$ so we wouldn't gain anything by bringing division to the party.

2. Why do we have both multiplication and addition, couldn't we express one with the other?Because there's no way to express all the multiplications in a polynomial as repeated addition, while still keeping the form of a polynomial. Sure, you could write $3x$ as $x+x+x$ but that would be hard to read and wouldn't gain anything. But there's no way to write $x^2$ using a fixed number of additions: there's nothing in the definition of a polynomial that lets you write
$$\underbrace{x + \dots + x}_{x \text{ times}}\,.$$

3. What is the difference between polynomial time and exponential time by definition?An exponential function is one of the form $k^x$ for some constant $k$. Note that this is different to a polynomial: polynomials are "variable-to-the-constant" and exponentials are "constant-to-the-variable". Exponentials grow much faster than polynomials. For example, see this plot. As G. Bach points out in his comment, if you're defining complexity classes around exponential functions, you need to take $k>1$.


Clarifications about CPU working: as the functions to get the operands are physically generated? I ask patience to help me to have clarity because I tend to equivocate between formal rappresentation like

like operator is a token
bit
it is determined which operation is to be performed and how to get the   operands, according to a function whose domain consists...

and what is physically-electronic-logic rappresentation CPU elements operation like

CPU configuration signal
Registers
pulses

about some with respect to certain specific technical processes.
The cause is related to mixing high bit, operator, operand when it working like functions.

I don't what mean for 'value' - what is this 'value' ? A logic state, adressing mode? i don't understand why operands may as a constant value

Often, one group of bits (that is, a "field") within the instruction, called the opcode, indicates which operation is to be performed, while the remaining fields usually provide supplemental information required for the operation, such as the operands. Those operands may be pecified as a constant value

What it mean 'pulses' ? I don't understand well the connection of bit like rappresentation and its physical state version. This pulses are generated about what electronic component ?

the control unit produces the sequence of pulses on each control signal line required to implement that instruction

I really don't understand if this functions are math or logic states about operand assembly (decode).

Operand Assembly: once the word has been taken from memory, it is determined which operation is to be performed and how to get the operands, according to a function whose domain consists of the operating codes (typically the high order bits of the word) and the co-domain consists of the microprogram to be executed

But..as these functions are generated to get the addresses from which electronic element ? Registers ? Addressing Mode ? I don't understand if it refers about instruction sets, a part of the architecture or if one process?

I don't understand well this electronic logic passage. Hardwired ? Multiple clock pulses ? Is there some link to understand better this ?

In some CPU designs the instruction decoder is implemented as a hardwired, unchangeable circuit. In others, a microprogram is used to translate instructions into sets of CPU configuration signals that are applied sequentially over multiple clock pulses. In some cases the memory that stores the microprogram is rewritable, making it possible to change the way in which the CPU decodes instructions.

what is configuration signals physically-logic ?

is used to translate instructions into sets of CPU configuration signals

But it is done by the ALU or not?

I don't understand Microcode

The microcode is a layer of hardware-level instructions that implement higher-level machine code instructions or internal state machine sequencing in many digital processing elements

Operand: numerical data on which the product is an arithmetic or logic

I understand mean of high-order bit and high word
http://www.gamedev.net/topic/414290-please-explain-high-and-low-order-bitword-terminology/

I understand what is word
http://whatis.techtarget.com/definition/word

and is ok also operand definition (wiki) but I don't understand WHAT THEY ARE like LOGIC_PHYSICALLY ?
How they are made to logical-physical level?

I don't understand why defined bit length of a word is equivalent to the width of the computer's data bus so that a word can be moved in a single operation from storage to a processor register.

It seems that you have two texts here, one talking about CPUs in the most clumsy way imaginable, and one sounding like a quite reasonable text book, and you can't get the terms of that clumsy text explained by the text book.

I suggest you read that text book, and that text book alone, because the other text isn't going to help your understanding at all. Something like "the control unit produces the sequence of pulses on each control signal line required to implement that instruction" sounds like someone with no understanding at all trying to hide behind big words.


01 Knapsack with selection of items with minimum total weight I have a slightly modified version of a classical 01 knapsack problem. Specifically, the problem has an additional constraint which requires that if more than one feasible selection with equal value exists then the selection with minimum total weight be selected. For example, consider a knapsack with size 3 and the following set of items to choose from; tuple is defined as ("name", weight, value):

items = (("alpha", 3, 4), ("beta", 1, 3), ("gamma", 1, 1))

There exist two possible selections with total weight <= 3 and value = 4:

Selection 1:

[alpha] with a total value of 4 and weight 3

Selection 2:

[beta, gamma] with a total value of 4 and weight 2

Due to the additional constraint, selection 2 is the correct answer. However, the classical 01 knapsack doesn't ensure this. So my question is, does there exist a variant of 01 knapsack which handles this? If not how do I tackle this additional constraint.

So far, I have the following two approaches which can possibly work:

Calculate the density of the objects and then perform knapsack using
density as the value. This approach however is suited to fractional
knapsack where any arbitrary amount of an item can be taken. In this
case, the item, if taken, must be taken in its entirety.
Sort the items with respect to weights before running knapsack on
them.

Sure.  It's easy to take any algorithm to solve the ordinary knapsack problem, and apply it to your problem.  In the ordinary knapsack problem, we specify an upper bound on the weight.  Once we find the maximum value achievable with that weight, next we'll try to see if we can reduce its weight further.  Do this by solving a new version of the knapsack problem, the same as the original, except the maximum weight has been reduced.  See how far you can reduce the maximum weight while still achieving the same value.  You can use binary search for that.


Team construction in tri-partite graph The government wants to create a team with one alchemist, one builder, and one computer-scientist.

In order to have good cooperation, it is important that the 3 team-members like each other.

Therefore, the government gathers $k$ candidates of each profession, and creates their "liking" graph. This is a tri-partite graph, where there is an edge between $a$ and $b$ iff $a$ likes $b$.

(Note that the "like" relation is symmetric but not transitive, i.e.: if $a$ likes $b$ then $b$ likes $a$, but if $a$ likes $b$ and $b$ likes $c$, then not necessarily $a$ likes $c$).

Is this always possible to create a team? Of course not. For example, it is possible that no alchemist likes any builder.

However, suppose the "liking" graph has the following property: in each group of 3 alchemists and 3 builders, there is at least a single alchemist-builder pair that like each other; ditto for alchemists-computerists and builders-computerists.

Given this property, is this always possible to create a team where all 3 members like each other? If so, what is the minimum number of candidates of each type ($k$) that the government will have to gather?

I would like to both find k and prove that it is the minimum.

A possibly related sub-question is: in a group of $k$ alchemists and $k$ builders, what is the minimum number of pairs that like each other? For $k=3$, by the assumption of the question, that number is 1. What about $k>3$?

A third question is: what is the name of this kind of problems?

An upper bound on the first question is $k\leq 15$: Take a set of $5$ $a$s $A=\{a_1,\dots,a_5\}$, $5$ $b$s $B_1=\{b_1,\dots,b_5\}$ and $5$ $c$s $C_1=\{c_1,\dots,c_5\}$. We know that at most 2 of the $a$s don't have a neighbor among the $B$s, otherwise we found a complement of a $K_{3,3}$, which is forbidden. The same holds for $a$s and $c$s. Thus there must be one $a_1'$ that has a neighbor among both sets. We call these neighbors $b_1'$ and $c_1'$ respectively.

We now fix the set $A$ and consider $10$ additional pairs of sets of $b$s and $c$s $(B_i,C_i)_{i\in\{2,\dots,11\}}$ with
$$B_i=\{b_{i+4}\}\cup(B_{i-1}\setminus \{b_{i-1}'\})$$ and
$$C_i=\{c_{i+4}\}\cup(C_{i-1}\setminus \{c_{i-1}'\})$$
and choose $b_i'$ and $c_i'$ such that they're both neighbors of the same $a_i' \in A$ (which all exist by the observation above).

Now at least $3$  pairs of sets agree on the same $a$ by the pigeonhole principle, i.e. there is an $a_l\in A$ and pairwise different $m_1,m_2,m_3 \in \{1,\dots,11\}$ such that $a_l = a_{m_1}' = a_{m_2}' = a_{m_3}'$.
Now $b_{m_p}'$ and $c_{m_p}'$ are neighbors of $a_l$ for $p\in\{1,\dots,3\}$. Thus for some $p,p'\in \{1,2,3\}$ the set $\{a_l,b_{m_p}',c_{m_{p'}}'\}$ induces a triangle of friends.


Analysis of Basic Recursive Functions I'm trying to understand the contrast between run-time for this function

public static String f(int N) {
    if (N == 0) return "";
    String s = f(N / 2);
    if (N % 2 == 0) return s + s;
    else            return s + s + "x";
}

and this function

public static String f(int N) {
    if (N == 0) return "";
    if (N == 1) return "x";
    return f(N/2) + f(N - N/2);
}

where string concatenation takes time proportional to the size of the strings.

So far, I believe that the first function is called log(N) times for input N and the second 2log(N) times.  Is that right?  Beyond that, I'm not sure how to think about how many operations happen in each of those calls.  I know that for the first function, in the base case there are 0 operations (no concatenation), then 1 operation (concatenation of two null strings with a string of length 1?), then 2 operations.  In general I believe the string produced by a call with N is of length N?  But I just don't know where to start thinking about how it all adds up.

For the second one likewise I'm a little lost.  I just need a way to approach the analysis.  Keep in mind I'm not great with symbols, so if you're going to show off with symbols, I'd appreciate an explanation that will help me follow the symbols as well.

Set them up as recurrences. First, note that both just return $N$ characters $x$. Call the time taken by the first function for $N$ $A(N)$ and similarly $B(N)$ for the second. For the first version, the function calls itself with $\lfloor N / 2 \rfloor$ (I'm taking your language to be Java or similar, dividing integers truncates), and then concatenates some strings. As noted, $f(N)$ is just $N$ times 'x'. Consider teh different cases, and what work is done in each of them:

$$A(N) = \begin{cases}
            0                                           & N = 0 \\
            A(\lfloor N / 2 \rfloor) + 2 \cdot N / 2   & N > 0 \wedge 2 \mid N \\
            A(\lfloor N / 2 \rfloor) + 2 \cdot (N - 1) / 2 + 1     & \text{otherwise}
         \end{cases}$$

You see that both last cases simplify to just $A(\lfloor N / 2 \rfloor) + N$. Your recurrence is $A(N) = A(\lfloor N / 2 \rfloor) + N, A(0) = 0$

For the second one, you get $B(N) = B(\lfloor N / 2 \rfloor) + B(\lceil N / 2\rceil) + N, B(0) = B(1) = 0$


Given grammar, a nonterminal, and a string, does there exist a parse tree that uses the nonterminal? Let $G$ be a CFG, let $A$ be one of its non-terminals, and let $x$ be a string. Define the language = $ \{ \langle G,A,x\rangle|$there exists a derivation of $x$ in which $A$ is used  $\}$. Is this language T-recognizable? Is it decidable?

Obviously, we can determine if there is at least one derivation for $G$, since context-free languages are decidable. But we cannot print every derivation. One idea could be to convert to Chomsky normal, and then print all possible derivations up to a certain length, but I am not sure if it would work.

Could one start with first designing a recognizer that is not necessarily decidable and then tweak it to be a decider?

You are asking two different questions, I will answer only the first one.

  Is this language T-recognizable?

Designing first recognizer and then transforming it into a decider will not always work. A language may be undecidable but recursively enumerable.

Your approach is correct. This language is recognizable (recursively enumerable). Just systematically generate all possible sentences (for example by breadth first search algorithm) every time by checking if any derivation contains the nonterminal $A$ and the derived sentence is $x$. If the test passes then ACCEPT.

A hint for the second question: $x$ has some certain length $n$. Can derivation of all sentences of length $n$ help us decide?

Also, a decidable language is also recursively enumerable, but the converse is not always true.


Is the union of NP Complete language and a finite language (in P) NP Complete? Let there be a language $A$ which is NP complete and language $B$ which is a finite language, is the union of $A \cup B$ NP complete language?

The answer is yes, and this is a special case of the following statement:

Let $X$, $Y$ be non-trivial languages (ie either empty nor everything) such that the symmetric difference $(X \setminus Y) \cup (X \setminus Y)$ is finite. Then $X \leq Y$ (linear time, constant space manyone reduction).

The reduction just tests whether the input is any of the finitely many values in $(X \setminus Y) \cup (X \setminus Y)$ and proceeds in a hard-coded way there. This takes constant time+space. Otherwise, it copies the input, since $X$ and $Y$ will agree there.

How to use this: For NP-hardness of $A \cup B$, set $X := A$ and $Y := A \cup B$. For NP-membership of $A \cup B$, set $X := A \cup B$ and $Y := A$. Note that the symmetric difference of $A$ and $A \cup B$ is included in $B$, hence if $B$ is finite, so is the symmetric difference.


Is the halting problem claim true with the advent of AI Alan Turing states that, there can't be a program that can decide if a program will ever stop. But with such advances in AI, won't computers will be able to analyze code and decide like humans on whether a program will halt or not.

Am I missing something in his claim?

Or is it too fictitious?

Even if we can design better AI solving problems we did not think possible even 10 years ago, they will always be computer programs. And as you said it yourself, "Alan Turing states that, there can't be a program that can decide if a program will ever stop." (he actually proved it and not only stated it...). Thus even the best AI you can think of will not be able to decide this problem, this is uncomputable.

This is a theorem, and unless we find a new device doing computation beyond the power of Turing machine (I am not talking about faster computation, but really a new kind of computing), this will remain impossible. Even if we have whole new kind of computer defining a new concept of computation, let's call them hypercomputers, it is very likely that those hypercomputers will not be able to decide
if a hypercomputer ever stops.

However, you are right in the sense that in every day life, many programs are simple enough to be analyzed and proven to terminate. Thus we can still hope to have better algorithm (using for example advances in AI), that can generate proof of terminations for a large class of programs. See for example Microsoft Terminator [1] which precisely address this problem in practice.

[1] https://en.wikipedia.org/wiki/Microsoft_Terminator


How to check if an algorithm's running time is linear/polynomial in its input size? Multiple variables I am reading a proof that the Subset Sum decision problem is NP-complete.
I know that the time complexity is always calculated based on the number of bits of the input in binary, hence the $\log{W}$.
Also, for this specific problem the size/length of the input is $(n+1)\log{W}$, with $n$ and $W$ being two integer variables ($n$ is the number of available elements in the set and $W$ is the sum we are seeking).
However I am having some trouble when trying to understand the terminology be linear/polynomial in the input size, specifically with these two lines:

The input length is (n + 1) log W, and the running time of O(nW) is
not polynomial in this input length.

and

takes O(n log W) time, linear in the input size.

How can I mathematically prove the above two lines? Or what is the mathematical reasoning behind those two statements?
I don't have this conceptual problem when there is only one variable. For example, let's say I have an algorithm with a complexity of $O(x)$ and an input size of $\log_2{x}$. Then, I can express $x$ in terms of the problem size like this: $O(2^{size})$. Now, I can see that the complexity is exponential in the size (in bits) of the problem.
But I don't know how to do this when there are two or more variables in the complexity function (in this case $W$ and $n$).

Suppose that the function $\ell$ represents the input length of an algorithm, in terms of several parameters $\vec{x}$, and suppose that the function $T$ represents its running time, in terms of the same parameters $\vec{x}$. Furthermore, there is a collection of valid parameter settings.
We say that $T$ is linear in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C \ell(\vec{x})$.
Similarly, we say that $T$ is polynomial in $\ell$ if there exist $M,C$ such that for any valid parameter setting $\vec{x}$, if $\ell(\vec{x}) \ge M$ then $T(\vec{x}) \leq C\ell(\vec{x})^C$.
(We get these definitions from the usual definitions of time complexity.)
In your case, $\ell$ and $T$ depend on two parameters $n,W$, and $\ell(n,W) = (n+1)\log W$. A parameter setting is valid if $n \geq 1$ and $W \geq 2$ (this unstated assumption is needed to guarantee that your running times are positive). You are interested in two functions $T$: $T_1(n,W) = nW$ and $T_2(n,W) = n\log W$.
Let us start with the second function $T_2$. For any valid $n,W$ we have $n+1 \leq 2n$ and so $\ell(n,W) \leq 2T_2(n,W)$. Therefore $T_2$ is linear in $\ell$, with $M = 1$ and $C = 2$.
Now let us consider the first function $T_1$. Suppose that $T_1$ were polynomial in $\ell$, with parameters $M,C$. Thus if $n \geq 1$, $W \geq 2$, and $(n+1)\log W \geq M$, then $nW \leq C[(n+1)\log W]^C$. In particular, taking $n=1$, we get that for any $W \geq 2$, $W \leq C2^C(\log W)^C$. Equivalently, $W = O(\log^C W)$. However, this is clearly false. Therefore $T_1$ is not polynomial in $\ell$.


How to prove: If $\textsf{EXP} \subseteq \textsf{P/poly} $ then $\textsf{EXP} = \Sigma^p_2$ Following is a theorem from Sanjeev Arora and Boaz Barak I am unable to prove :

  If $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \Sigma^p_2$.

The previous similar theorem was

  If $\textsf{NP} \subseteq \textsf{P/poly}$ then $\textsf{PH}=\Sigma_2^p$.

The second theorem was easy to prove  as $\textsf{NP}=\Sigma_1^p$. But $\textsf{EXP}$ does not have such characteristic. How do I prove the first theorem. Any hints?

The more classical statement is that if $\textsf{EXP} \subseteq \textsf{P/poly}$ then $\textsf{EXP} = \textsf{MA}$, due to Babai, Fortnow and Lund. Impagliazzo, Kabanets and Wigderson showed that $\textsf{NEXP} \subseteq \textsf{P/poly}$ iff $\textsf{NEXP} = \textsf{MA}$. See lecture notes of Bogdanov for proof sketches.


Minimum number of people required to invite everyone to a reunion I'm trying to organise a large reunion though facebook. Over the years we've all drifted apart, and so there isn't anyone who is still facebook friends with everyone.

You need to be facebook friends to invite someone to the facebook event and I have invited all the people that I can. I also know that each of the uninvited people has at least one friend amongst the invited people, and by checking for 'mutual friends' I can know who they are.

In order to get everyone invited to the reunion I'm going to ask some of the invited people to invite the uninvited people.

My question is, does anyone happen to know an algorithm to find the minimum number of invited people that are required to message all of the uninvited people? I don't need anything super detailed, just something to point me in the right direction.

One way to think about it is to make an undirected graph, and have every person be a vertex. There is an edge between two people if they are Facebook friends.

Now, assuming that you're asking people to invite their friends, and have those people invite their friends, and so on, then your problem basically boils down to finding the connected components of the graph you just made. (Two vertices are in the same connected component iff there exists a path between them)

Actually finding them isn't that bad; it's basically a slightly modified DFS.


How to work out if an IEEE 754 floating point number is normalized? How do I tell whether a particular IEEE 754 floating point number is a normalized floating point number?  Is there some way to recognize an IEEE 754 normalized floating point number?

For single-precision floating-point numbers you need to check if the following condition holds for the exponent $e$: $0 < e < 255$. The exponent occupies bits $30 .. 23$ (including both ends) of a floating-point number.

For double-precision floating-point numbers you need to check if $0 < e < 2047$. The exponent occupies bits $62 .. 52$ in this case.

Essentially, for IEEE 754 floating-point numbers one has to check that the bits of the exponent are not all 1's and not all 0's. All zero bits correspond either to subnormal numbers or to signed zero. And when all bits of the exponent are ones it corresponds to $+\infty, -\infty$ or NaN (not a number).


Dominating set in bounded degeneracy and bounded degree graphs I believe Minimum Dominating Set (MDS) is NP-hard for bounded
degeneracy and their subset bounded degree graphs, but
a paper appear to suggest tractability.
Enumeration of Minimal Dominating Sets and Variants p.5

  Proposition 1. Dom admits a polynomial delay algorithm when restricted to

Strongly chordal graphs.
Graph classes of bounded degeneracy.

The delay of the algorithm is the time between enumerating two MDSs
after polynomial preprocessing (unless I have misunderstood the
definitions on p. 3).
According to graphclasses.org MDS is linear for strongly chordal graphs.

Does the paper imply $\exp(o(n))$ complexity of MDS
for graphs of bounded degeneracy (and bounded degree)?

No it does not. The problem DOM considered by the paper seems to be the enumeration of minimal, not minimum dominating sets. Usually minimal means a solution $X$ such that there is no other solution $X'$ with $X' \subsetneq X$. The solution $X$ is not necessarily the minimum size. While minimal dominating sets can be enumerated with polynomial delay in bounded degeneracy graphs, there seems to be no guarantees that this enumeration finds the minimum dominating set before enumerating an exponential number of dominating sets that are minimal, but not minimum.


What do you get when you add $O(n)$ to itself $n$ times? I was watching this video on Algorithms and counting number of inversions and he mentioned being cautions when $O(n) + O (n) = O(n)$, saying that is not true if you add $O(n)$ to itself $n$ times. Is the answer $O(n^2)$?

The notation $O(n)$ stands for a function which is bounded by $Cn$ for some constant $C>0$ and large enough $n$.
If you have a two functions $f_1,f_2$ which are both $O(n)$, then so is their sum $f_1+f_2$: indeed, suppose that $f_1(n) \leq C_1n$ and $f_2(n) \leq C_2n$ for large enough $n$. Then $f_1(n) + f_2(n) \leq (C_1 + C_2)(n)$ for large enough $n$.
Similarly, if you have a single function $f(n)$ which is $O(n)$ and you add it to itself $n$ times then you get a function $nf(n)$ which is $O(n^2)$.
However, this fails when you add $n$ different functions which are $O(n)$. For example, consider the functions $f_k(n) = kn$ and the function $g(n) = f_1(n) + \cdots + f_n(n)$. Then $f_k(n) = O(n)$ for all $k$, but it is not true that $g(n) = O(n^2)$; rather, $g(n) = \Theta(n^3)$. (This means that $cn^3 \leq g(n) \leq Cn^3$ for some $c,C>0$ and large enough $n$.)
If we know that the functions $f_k$ are uniformly $O(n)$, that is, there is a single $C>0$ and a single $N>0$ such that $f_k(n) \leq Cn$ whenever $n>N$, then it does hold that $f_k(1) + \cdots + f_k(n) = O(n^2)$.
(It doesn't suffice to require just $C$ to be uniform. For example, if $f_k(n) = n+k^2$ then $f_k(n) \leq 2n$ for large enough $n$, but $f_1(n) + \cdots + f_n(n) = \Theta(n^3)$.)


IS Array of Positive Integers Always 'Equalizable' With This Strategy? A little bit of history first. I have asked this question here some days ago. Quoting from there:

  An array $A$ is given that has only positive integers in it. The objective is to equalize the array in minimum possible steps. In every step all but one element are incremented by a fixed step size. The possible step sizes are given in another array $D$.For example, if $A=\{2,2,3,7\}$ and $D=\{1,2,5\}$ we can equalize $A$ in two steps, first adding $A=\{5,5,5,0\}$ to get $A=\{7,7,8,7\}$ and then adding $\{1,1,0,1\}$ to get $A=\{8,8,8,8\}$.

If $A$ has just two elements, this reduces to something like a change-making problem. If $\Delta=min(A[0],A[1])$, if I can make change for $\Delta$ using only the given steps from $D=\{1,2,5\}$, I can equalize the array by holding the larger element constant while incrementing the smaller element by the same values that I used to make change for $\Delta$. However,if it's not possible to make change for delta, it's not clear if the two elements can converge two some larger value following this strategy.

I would like to know if this strategy of withholding one element and incrementing the rest by a chosen 'delta' will always make all elements equal in some finite number of steps.

If the GCD of the array D is larger than 1, then this cannot always be done. The simplest example is $A = \{1,2\},D=\{2\}$. In contrast, if the GCD of the array D is 1, then it is known that large enough integers can be represented as positive linear combinations of elements of D. In particular, there is an integer $N$ such that $N-a$ can be represented for all $a \in A$. Summing all these representations will equalize the array.

For example, when $A = \{2,3,7\}$ and $D = \{1,2,5\}$, we can add $\{1,0,0\}$ once and $\{1,1,0\}$ four times, reflecting the representations $7-2=5 \times 1$, $7-3=4 \times 1$, $7-7 = 0 \times 1$. Even when $D = \{2,5\}$ this has a solution: using $11 = 3 \times 2 + 1 \times 5$, $10 = 2 \times 5$, $6 = 3 \times 2$, we can add $\{2,0,2\}$ three times, $\{5,5,0\}$ once, and $\{0,5,0\}$ once to get $\{13,13,13\}$.


Reducing one variant of Hamiltonian path to another Define

$A = \{<G,s,t> :G$  is un directed graph that has a Hamilton path from $s$ to $t\}$

$B = \{<G> :G$  is un directed graph that has a Hamilton path$\}$

I would like to show that $A \le_p B$.

My attempt:

Given $<G,s,t>$ , the reduction outputs $<G'>$ where $G'$ defines as follows:

we take $v_s$ and $v_t$ s.t there is an edge $e_s$ between $s$ and$v_s$ and an edge $e_t$ between $v_t$ and $t$.

Now we define $G' = (V',E')$ where $V' = V \cup \{v_0 , v_1\}$ and $E' = (E-\{e' :e' \ne e_s , s\in e'\} -\{e' :e' \ne e_t , t\in e'\}) \cup \{ \{v_0,v \} :\{v,s\} \in E \} \cup  \{ \{v_1,v \} :\{v,t\} \in E \} \cup \{ \{v_0,s \}\ , \{v_1,t\} \}$.

Now, if $<G,s,t> \in A$  , let $s , u_1,\dots ,u_n ,t$ be the Hamilton path , then $s , v_0 , u_1 , \dots , u_n, v_1 ,t$ is a Hamilton path in $G'$.

The other direction does not work for me , if $G'$ has a Hamilton path then I want to say that the "end points" must be around $s,t$ but i'm not sure how to do that.

The simplest reduction, which is similar to what you were trying but simpler, is to add two new vertices to the graph in the instance of A: a vertex $v_s$ connected to $s$, and a vertex $v_t$ connected to $t$. Any Hamiltonian path in the new graph will connect $v_s$ to $v_t$, and so will restrict to a Hamiltonian path connecting $s$ to $t$. Vice versa, any Hamiltonian path in the original graph connecting $s$ to $t$ extends to a Hamiltonian path in the new graph connecting $v_s$ to $v_t$.


Fast and space efficient data structure for nearest neighbors in 3 dimensions? I am looking for data structures to answer nearest neighbor queries in 3D which are reasonably space efficient (ie use at most $O(n^{1+\epsilon})$ space) and fast ($O(n^{\epsilon})$ or $O(log^k(n))$ query time in the worst case).

As a summary of what I already know:

1D is trivial (just sort the points and use binary search).
2D is a bit trickier, but with a point location data structure + voronoi diagram you can do it in $O(n)$ space and $O(log(n))$ query time.
In 3D and above, that solution breaks down since the Voronoi diagram of a set of points is $O(n^{floor(d/2)})$.

I am aware of approximate techniques based on kd-trees or grid based methods, though these are dependent on assuming either a uniform distribution of points or something about the distance to the nearest neighbor, and don't perform so well in all cases.  I am not interested in these randomized or approximate solutions - I want something that works for any data set in the worst case.  Is there anything out there that does this, or is there some lower bound which blows this idea out of the water?

I like Drost's hierarchical voxel hashing. It has an average time complexity of $O(log(log(|D|)))$, where $|D|$ is the number of points in data cloud. While the construction is a bit more tedious, searching gets much faster.

The method is also extended to a journal version, found under this link.


Proof of an Infinite Binary Sequence I have a problem where given an infinite binary sequence S ∈ {0, 1}∞ to be "prefix-repetitive" if there are infinitely many strings w ∈ {0, 1}*
such that ww is a prefix of S.

I need to prove that if the bits of a sequence S ∈ {0, 1}∞ are chosen by independent tosses of a fair coin, then
Prob[S is prefix-repetitive] = 0

My first instinct to tackling this problem was that the probability was 0, because of Cantor's diagonal argument, because we can construct an sequence s0 that is not in the set S. This would mean that S is countably infinite and the set of "all" possible infinite binary sequences is uncountable.

Any help or suggestions to see if I'm on the right track to proving this problem would be great!

Here is a formal or informal proof, depending on how the probability distribution is defined.

Let $S_k=\left\{vvs\in\{0,1\}^\infty\mid v\in\{0,1\}^k,\ s\in\{0,1\}^\infty \right\}$, the sequences of infinite binary digits that repeat their initial $k$ binary digits immediately once (or more), where $k\ge1$.

$$\begin{align}
\text{Prob[$S_k$]}
&\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w\text{ can be extended to an element in } S_k\right\}\\
&\le\frac1{2^{2k}}\#\left\{w\in\{0,1\}^{2k}\mid w=vv \text{ for some } k \text{ binary digits } v\right\}\\
&=\frac1{2^{2k}}\#\left\{v\in\{0,1\}^{k}\right\}\\
&=\frac1{2^{2k}}2^{k}\\
&=\frac1{2^k}\,.
\end{align}$$

Given an integer $i\ge1$ and a prefix-repetitive toss $S$, we know $S$ must be contained in $S_k$ for some $k\ge i$ since there infinitely many initial segments $v$ such that $vv$ is a prefix of S. Hence,
$$\begin{align}
\text{Prob[$S$ is prefix-repetitive]}
&\le\sum_{k=i}^\infty\text{Prob[$S_k$]}\\
&\le\sum_{k=i}^\infty\frac1{2^{k}}\\
&=\frac1{2^{i-1}}\,.\\
\end{align}$$

Let $i$ go to infinity, we see that
$$\text{Prob[$S$ is prefix-repetitive]} = 0\,.$$

Here are three related exercises.

Exercise 1. Show that the number of all prefix-repetitive tosses are more than countably infinite. Hence the approach mentioned in the question is unlikely to succeed.

Exercise 2. Show that if the bits of a sequence $S \in \{0, 1\}^\infty$ are chosen by independent tosses of an unfair coin, then Prob[S is prefix-repetitive] = 0.

Exercise 3. An infinite binary sequence $S \in \{0, 1\}^\infty$ is prefix-palindrome if there are infinitely many strings $v \in \{0, 1\}^*$ such that $vv^R$ is a prefix of $S$, where $v^R$ is the reverse of $v$. Show that if the bits of a sequence $S \in \{0, 1\}^\infty$ are chosen by independent tosses of a coin, then Prob[S is prefix-palindrome] = 0.


Min cost max flow in bipartite run time I have a bipartite graph with $|E|=O(|V|^2)$, a super-source and a super-sink. I am looking for the min-cost max-flow (the max-flow of all possible max-flows that has the minimum cost).

For the sake of my question, denote $n=|E|$.

Are there algorithms that will run in $O(n^2)$, or even $O(n\log(n))$, or for that matter anything less than $O(n^3)$? In my case, $n$ is ~100,000, so $O(n^3)$ is impractical for me.

'Extra' questions (should these go under a separate question?):

Do any of these supper multi-graphs (I have 2 edges from my super-source node to each of the "blue" nodes in my bipartite graph, and 2 edges from each of the "red" nodes to my super-sink node)?
Are there efficient implementations of such algorithms (that run in less than $O(n^3)$, and support multi-graphs) in C++, C, or Python?
If the answer is 'no', what are popular approximation algorithms and their associated run times?

Assuming your edges have unit capacity, but non-unit costs, you can reduce this to a maximum-weight bipartite matching, that is, the assignment problem. For this, just make a copy of each vertex. The assignment problem can be solved in $O(n^{1.5})$ time.


Fastest algorithm for matrix inversion What is the fastest way to compute the inverse of the matrix, whose entries are from file $\mathbb{R}$ (set of real numbers)?

One way to calculate the inverse is using the gaussian elimination method. In this method append more columns(double the number of columns ) to the input matrix and then we try to make last row zero except the last column entry and second last and so on until we get a identity matrix and then we stop and we have a inverse of input matrix. Consider the cost of one multiplication, division  and addition is constant. Then total $O(n^2)$ many operations is needed.

Is there any algorithm which is faster than the above algorithm? Please give the algorithm or reference to the algorithm

Gaussian elimination requires $O(n^3)$ operations, not $O(n^2)$.

In general, matrix inversion has the same exponent as matrix multiplication (any matrix multiplication algorithm faster than $O(n^3)$ gives a matrix inversion algorithm faster than $O(n^3)$), see for example P.Burgisser, M.Clausen, M.A.Shokrollahi "Algebraic complexity theory", Chapter 16 "Problems related to matrix multiplication".


Equivalent definitions for subgraph I know that a graph G' is a subgraph for G if V(G')⊆V(G) and E(G')⊆E(G).

Today my professor wrote that G' is a subgraph for G if G' is a graph and V(G')⊆V(G), and then he told us that this definition is equivalent to the one we've seen before (= the first line in this post).

However, I don't think that these definitions are equivalent. In fact, if this is G:

       2
     /   \
    1     3

and this is G':

    1 - 3

we have that G' is a subgraph for G according to the second definition (wrong), while it is not according to the first one (right).

Am I missing something or was the professor wrong?

The alternative definition that you attribute to your professor is wrong, as your counterexample clearly shows.

I hope your professor actually said something else and you misunderstood him/her!


How to get the intersection of two regular languages? I was trying to figure out the value of the following expression.

(0 | 1)*00 ∩ (0 | 1)*01

I tried drawing DFAs for(0 | 1)*00 and (0 | 1)*01 separately and combine them using a table.

Is it the approach I should use? or is there any better way?

One approach is to convert each regexp to a NFA, then use the product construction to compute the intersection of those two NFA, then convert back to a regexp if necessary.  Whether this is better or not, I can't say, as that depends what you mean by "better".  One advantage of this approach is that it uses only standard techniques that hopefully you've already learned in your automata theory course and doesn't require memorization of specialized algorithms.


Confusion about the Time Hierarchy Theorem and relativization I know that $\mathsf{P}^A = \mathsf{EXP}$
for any $\mathsf{EXPTIME}$-complete language $A$.

Is it true that $\mathsf{DTIME}^A(n^k) = \mathsf{EXP}$
for any fixed $k$ and any $\mathsf{EXPTIME}$-complete oracle $A$?
If not, what do these complexity classes equal and why?

I am just confused because then it seems to me that we would then have
$\mathsf{DTIME}^A(n^k) = \mathsf{DTIME}^A(n^j)$ for $k < j$ and
this would contradict the fact that the Time Hierarchy Theorem holds under any oracle.

It is not true that for $A$ being $\sf EXP$-complete ${\sf DTIME}^A(n^k) = {\sf EXP}$, but you are right with ${\sf P}^A={\sf EXP}$.

Here is the reason for this. In order to make use of the oracle you have to transform your problem via a reduction. This reduction is a polynomial reduction. The running time of this particular reduction might need $\omega(n^k)$ steps. In this case you cannot use the oracle in the desired way.

As you already observed ${\sf DTIME}^A(n^k) \neq {\sf EXP}$ because this would imply  for all $k,j$ that ${\sf DTIME}^A(n^k)={\sf DTIME}^A(n^j)$, which cannot be true since the time hierarchy theorem relativizes.