Efficiently selecting a random subset of size $m$ from a set of size $n$ This is a cross post of my question here on math.se.
I have a list of $n$ items and would like to randomly select an $m$ set from it efficiently (in terms of time complexity). Also, I want all possible subsets to be selected with equal probability. The obvious solution is to pick a random integer from $1$ to $n$ and choose the corresponding element, then repeat $m$ times, not counting the event in which one chooses and already chosen element. This becomes increasingly inefficient as $m$ approaches $n$ so for $m>n/2$ it would make sense to instead to pick a $(n-m)$-set and return its compliment.
For values of $m$ close to $n/2$, a better solution I think would be to consider each of the $n$ elements and decide either to pick that element or discard it, each time updating the probability of picking or discarding depending on the number of elements chosen vs discarded prior. Specifically, the algorithm would go as follows (python):
def randomSubset(n,m):
  L = []
  for i in range(n):
    if uniform(0,1)<m/(n-i): L,m = L+[i],m-1
  return L

However I am concerned that this may not result in each subset being chosen with equal probability.
I have two questions. First, does this algorithm pick subsets with equal probability (if so, I'd like a proof that it does and if not I'd also like a proof that it doesn't). Second, more broadly I would like to know what good solutions exist to this problem. Clearly if $m<<n$ then the first method is better than the second however at some point the second method (if it does in fact work) is better than the first. Moreover, an entirely different approach may be best in general.

The probability that the element $1$ belongs to a random $m$-subset of an $n$-element set is $m/n$. Therefore you should include $1$ in your subset with probability $m/n$.
If you put $1$ in your subset, then you are left with choosing an $(m-1)$-subset of an $(n-1)$-element set.
If you didn't put $1$ in your subset, then you are left with choosing an $m$-subset of an $(n-1)$-element set.
This means that you have to slightly update your algorithm, replacing $m$ with $m-|L|$.
The resulting algorithm is somewhat similar to reservoir sampling.
A third approach, with some similarities, is generating a random permutation of $1,\ldots,n$ and selecting the first $m$ entries.
The downside of all of these approaches are that they run in time $\Theta(n)$, whereas for $m \ll \sqrt{n}$, your first algorithm runs in (expected) time $\tilde\Theta(m)$.
We can improve on the $\Theta(n)$ running time as follows. We will generate a random ordered $m$-subset given $m$ indices $i_1,\ldots,i_m$, where $i_j \in \{1,\ldots,n-(j-1)\}$. The $j$'th element in the subset will be the $i_j$'th smallest number in $\{1,\ldots,n\}$ out of the numbers not already chosen.
In order to complete the description of the algorithm, we need to solve the following problem: given $S \subseteq \{1,\ldots,n\}$ and $i$, find the $i$'th smallest element in $\overline{S}$. We can assume that $S$ is stored in a structure (such as a self-balancing binary tree) which can efficiently answer the following type of query: given $x$, how many elements in $S$ are smaller than $x$. We can then find the $i$'th smallest number in $\overline{S}$ using binary search.
Overall, this algorithm runs in $\tilde\Theta(m)$ for all values of $m$, where the tilde hides factors logarithmic in $n$. (When $m \ll \sqrt{n}$ we can use your first approach, thus getting rid of this dependence on $n$.)


Can a collection of oracle machines decide every language? If I have a collection of oracle machines, can I decide every language? (I got this question from a former university exam and it sparked my interest).

I thought if my collection has to be countable than I can't decide every language, since there's an uncountable amount of languages.

But if my collection can be of any kind I figured could just add an oracle machine for every language with an oracle for that language, which would be sort of a trivial - brute force approach (the size of the collection would be uncountable than).

Is there an issue with my approach / did I miss something? What happens if I have a countable number of oracles that can be used?

This answer assumes that "a collection of oracle machines" means "a sequence of oracles", that is, you have a Turing machine with access to a sequence of oracles.

A sequence of oracles is equivalent to a single oracle: if the original sequence is $O_i$, choose some pairing function $\langle \cdot,\cdot \rangle$ (e.g. $\langle x,y \rangle = 2^x (2y+1)$), and define a single oracle $O$ by $\langle x,y \rangle \in O$ if $y \in O_x$.

It is known that a machine with oracle access to $O$ cannot decide all languages, for reasons of cardinality. We can also exhibit a specific language undecidable by such a machine, namely the halting problem for oracle machines with oracle access to $O$.


Are there decision problems outside of NP? Consider any problem in NP-hard, then it has a polynomial reduction from a problem in NP in polynomial time. Though, it isn't clear by this definition whether there are decision problems in NP-hard that are not in NP.

Are there any known ones?

The nondeterministic time hierarchy theorem shows that, e.g., $\mathrm{NP}\subsetneq\mathrm{NEXP}$, so any $\mathrm{NEXP}$-complete problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$.  For a more extreme example, the halting problem is $\mathrm{NP}$-hard but not in $\mathrm{NP}$.


Path on an edge-colored DAG using exactly $k$ colors I have the following problem:

  Given an edge-colored DAG $G = (V,A)$, vertices $s$ and $t$, a set of colors $C$ and $k \in \mathbb{N}$,
   does there exist a path from $s$ to $t$ using exactly $k$ distinct colors?

Can anyone provide pointers to the complexity of this problem?  More specific, is it $\mathsf{NP}$-complete or in $\mathsf{P}$?

Here is a reduction of CNF-SAT.

In a given CNF formula, assume we have variables $x_1, \dots, x_n$ and clauses $C_1, \dots, C_m$.

We construct a DAG with edge colors as follows.

We have $m$ colors, and each color corresponds to a clause.  In our DAG, we have vertices $v_0$, $v_1$, ..., $v_n$, and $v_0$ is the source and $v_n$ is the sink.  (There will be more vertices in our DAG.)

From $v_{i-1}$ to $v_{i}$, we have a pair of vertex-disjoint paths (you may think they are parallel), one for TRUE and one for FALSE corresponding to the assignment to $x_i$.  On the path for TRUE, we have edges with the colors corresponding to the clauses with $x_i$ appearing as positive literals.  On the path for FALSE, we have edges with the colors corresponding to the clauses with $x_i$ appearing as negative literals.

A path exists from $v_0$ to $v_n$ with $m$ colors if and only if the given formula is satisfiable.


Why is ZPP = RP ∩ co-RP? I am trying to prove the theorem that ZPP = RP $\; \cap \; co-RP$. If $L \in \; \subseteq RP \; \cap \; co-RP$ then I can see that it belongs to $ZPP$. But I am unable to prove the reverse direction, as definitions of $RP$ and $co-RP$ don't include Turing machines whose expected running time is polynomial, but $ZPP$'s definition does. Am I missing something ? How should I proceed ?

The solution is given in the link provided by you in wikipedia article ZPP. See the section Intersection Definition in the link. You need to know about Markov's Inequality though.

Markov's inequality is $P[ X \geq a] \leq E[X]/a$ if $X \geq 0$. If we substitude $a = 2E[X]$ then we will have $P[ X \geq 2 E[X]] \leq 1/2$.

So, basically we run the algorithm that witnesses $L \in \textrm{ZPP}$ for at least double its expected running time. If it gives an answer, then we give that answer. If it doesn't give any answer before we stop it, we give NO answer. The probability of incorrect NO answer is $\leq 1/2$. This polynomial time algorithm proves $L \in \textrm{RP}$.

If we give answer YES on forced stoppage then that algorithm proves $L \in \textrm{co-RP}$. Thus $\textrm{ZPP} \subseteq \textrm{RP} \cap \textrm{co-RP}$.

For the sake of completeness, I also give the proof of $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.

Suppose we have a language $L \in \textrm{RP} \cap \textrm{co-RP}$. Then $L$ has a polynomial time algorithm $A$ that answers YES at least 1/2 times for $x \in L$  and a polynomial time algorithm $B$ that answers NO at least 1/2 times for $x \not\in L$. In one iteration we do the following: Given an input $x$ in $L$, we run $A$ on $x$. If it returns YES, the answer must be YES, so we return YES. Otherwise, we are in doubt so we run $B$ on the input. If it returns NO, the answer must be NO, so we return NO. If neither occurs, we repeat this iteration. We can show that the expected running time of this algorithm is still polynomial. Thus
 $\textrm{RP} \cap \textrm{co-RP}\subseteq\textrm{ZPP}$.


Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs A graph $G = (V, E)$ is called an $(n, d, \varepsilon)$-expander if the graph has $n$ vertices, maximum degree $d$, and satisfies the following expansion property:

for every subset $W\subset V$ such that $|W|\leq n/2$, $|W\cup N(W)|\ge (1+\varepsilon)|W|$

where $N(W)$ is the neighborhood of $W$ in $G$.  The expansion property means, informally, that the neighborhood of $W$ is "large" when $W$ is "small".  That expanders exist can be shown with the probabilistic method (see, e.g., this writeup from Ellis).

I'm trying to show that expanders can be used to amplify the success probability of one-sided Monte Carlo algorithms.  In particular, given a polynomial time algorithm $A$ for a problem in RP that uses $n$ random bits and gives false negatives with probability at most $1/2$ we want to show there is a polynomial time algorithm that uses $n$ random bits and gives false negatives with probability at most $n^{-c}$ for a fixed constant $c$.

Here is the method I've been asked to analyze.  We regard $A$ as a function $A(x,r)$ where $x$ is the input and $r$ is a string representing the random bits.  On the input $x$ we then:

Fix a $(2^n,d,\varepsilon)$-expander $G$ and identify its vertices with $\{0,1\}^n$
Select a vertex $r$ of $G$ uniformly at random
Compute the set $y_1,y_2,\ldots, y_t$ of vertices at distance at most $\delta$ from $r$ in $G$
Say "no" if and only if $A(x,r),A(x,y_1), \ldots, A(x,y_t)$ are all "no"

What I need to show is that for $\delta = O(\log n)$ the probability of a false negative is at most $n^{-c}$.

As a side note, this is actually enough to accomplish the original goal.  A result of Gabber and Galil is that there is a family of $(2^n, 5,(2 - \sqrt{3})/4)$-expanders with the additional property that the neighbors of any vertex can be enumerated in polynomial time.  This means that $d$ and $\varepsilon$ can be taken uniformly in $n$, and that we can implement BFS from $r$ in polynomial time per vertex considered. Since $t\le d^{\delta + 1}$, the new algorithm runs $A$ a number of times polynomial in $n$ for $\delta = O(\log n)$ and $n$ is polynomial in the input size.  Since $G$ is deterministic and does not depend on $A$, there is also clearly no new randomness.

Here is how I approached the problem thus far.

Let $G$ be given. Since $|V| = 2^n$, we have an identification $V \cong \{0,1\}^n$. Let $r \in \{0,1\}^n$ be chosen at random so that $r$ corresponds to a random starting point in $G$. Define a ball $B(v,\delta) = \{u \in V: d(u,v) \leq \delta\}$ where $d(u,v)$ is the length of the shortest $uv$-path. We are only interested in the number of bad balls, namely balls such that all $u\in B(v,\delta)$ result in false negatives, that is, our $\mathsf{RP}$ algorithm should accept but reject nonetheless. If we can bound above the number of bad balls by $2^n/n^c$ for some constant $c$, then we are done since an error occur if and only if the chosen vertex $y_i$ is such that $B(y_i,\delta)$ is bad.

I tried bounding the number of vertices in a bad ball using the expansion property of $G$, but I am not sure how this could help considering balls are certainly not disjoint. We also know that at most $1/2$ of the vertices will result in a false negative.

Any help would be greatly appreciated.

Since nobody else answered, here is what I had in mind when I made my comment.  The basic idea behind the proposed amplification algorithm is that expanders are "negatively curved" in the sense that small sets in degree-bounded expanders should have a lot of their volume near the boundary. This then suggests that a ball centered in a small set should quickly "escape" with reasonable probability.

To answer a question from your comment, since the ball around a random vertex isn't a uniformly random set, we wouldn't expect a bound like $2^{-s}$ for the probability of being bad. Instead we get something that depends on $\epsilon$ and $d$ (with bigger $\epsilon$ and smaller $d$ being better if the other parameter is held fixed).

As in my comment, set $X\subset \{0,1\}^n$ to be the random strings where our RP algorithm $A(x,r)$ gives false negatives and $Y$ be the complement.  Since $G$ is a $(N,d,\epsilon)$-expander with $N = 2^n$, and $|X|\le N/2$ by hypothesis, we know that:

at least $\epsilon |X| / d$ different vertices in $X$ have a neighbor in $Y$

Notice that this already gives us something, since if we took $\delta = 1$, the improved algorithm now gives a false negative with probability only $1/2 - \epsilon/d$. The question just asks us to be a bit more ambitious.

To this end, define
$$
X_i := \{r : d(r,Y) \ge i\}
$$
What we just argued was that $|X_2| \le (1-\epsilon/d)|X|\le (1-\epsilon/d)N/2$.  From the way we've defined $X_i$, we the neighborhood of $X_i$ is contained in $X_{i-1}$ for $i\ge 3$.  This lets us replay the same argument to show that, for $i\ge 3$ we get $|X_i|\le (1-\epsilon/d)|X_{i-1}|$.  By induction we then get that  $|X_s|\le (1-\epsilon/d)^{s-1}N/2$.

Finally, observe that the improved algorithm fails when the chosen $r$ is in $X_{s+1}$. For $s=\Theta_{\epsilon,d}(\log n)$ this probability is $n^{-c}$.


CFLs are inherently unambiguous? As reading the textbook of Introduction to the theory of computation_third edition - Michael Sipser, which have the concept that we call a context-free language L inherently unambiguous if there does not exist an ambiguous CFG that generates L.

Do we have any CFLs are inherently unambiguous? if so, can you please give me an example?

Every non-empty context-free language has an ambiguous grammar. Indeed, take any context-free grammar for the language, and add to it the production $S \to S$ (if it is not already there), where $S$ is the start symbol. Every word in the language has infinitely many derivations, since given a derivation, we can always come up with a longer one by adding an application of the rule $S \to S$ at the very beginning.


Can I say is lossy compression to discard data having a way to recover it? I'm working on a compression algorithm for a specific kind of data. I have found a way to discard (important) parts of the data during compression as I have also found a way to recover the missing parts during decompression.

The decompression algorithm most of the times will infer the data equal to the discarded one. However, in punctual cases, it will infer similar data that works just as well as the original.

So my question is: Can I claim that my algorithm is lossy?

However, in punctual cases, it will infer similar data that works just as well as the original.

From this I would conclude it is lossy because it is similar data, rather than lossless, which would be a perfect reconstruction.

That being said, I'm not entirely what you mean by "data that works just as well", but if the data works exactly how the original data would work, for your use case it might be considered lossless because the information you need and compress is not lost. You must be careful to specify that the compression of the information you wish to recover is lossless, but the compression of the data as a whole is lossy.

As example, if my goal is to save (using compression) simple arithmetic equations to later determine if they are odd or even. I might compress $f = 4 + 3 + 8 +1$ into the number of even ($e$) and odd ($o$) terms it has: $ C(f) = 2e2o$. This is clearly lossy, I can't perfectly reconstruct which terms created $f$, but for my purposes I can clearly determine whether it is odd or even after compression. Even further I could reconstruct similar data (as you stated) that works just as well as the original, for my purposes.


Algorithm for seeing if there exists a min s-t cut (A,B) in a flow network with node u in A and node v in B We are given a flow network and two nodes $u$ and $v$. We want to create an algorithm that tells us whether or not there is a minimum s-t cut so that $u$ belongs to the same side of the cut as the source node $s$ and $v$ belongs to the same side of the cut as the sink node $t$.
My initial idea was to run Ford-Fulkerson to get the residual graph $G_f$ at the end. Then use that to find all nodes reachable from $s$ in $G_f$ (call this set $A$) then $B=V-A$ where $V$ is the vertex set. Then $(A,B)$ is a min s-t cut and if $u \in A, v \in B$ output true, else false.
But since there may be more than one min cut I'm a bit stuck.

The easy solution is to add an edge between $s$ and $u$ with infinite weight and $t$ and $v$ with infinite weight.
Note though that this doesn't mean that $s$ and $u$ will be connected in $G[A]$.


Dancing links algorithm solutions Right now I am working on my implementation of Knuth's DLX algorithm.

I did understand the exact cover problem. But I didn't fully understand how Dancing links works. Here is Knuth's paper.
The question is about the solutions presented in the paper. I don't understand how these solutions make sense taking into account the matrix that he uses.

Matrix for the exact cover problem

     A B C D E F G
  1  0 0 1 0 1 1 0
  2  1 0 0 1 0 0 1
  3  0 1 1 0 0 1 0
  4  1 0 0 1 0 0 0
  5  0 1 0 0 0 0 1
  6  0 0 0 1 1 0 1

And solutions are:

A D
B G
C E F

But how come these solutions are valid? Isn't it supposed to be answered like A B E? Where in each row there is only one 1.

Knuth is trying to cover the columns using rows. The solution you describe consists of rows 4, 5, 1, in this order (counting from 1). Each row is represented by its 1-columns. For example, row 4 is 1001000, and its 1-columns are AD.


Reduction to Maximum Independent Set Suppose you had a set $P$ of people. Every person $p_j \in P$ is familiar with atleast one other person $p_i$ (familiarity is symmetric). Is there a subset $S$ of people such that for $|S| \ge k$, no two people in $S$ know each other? Show that the problem is NP-Complete.

Clearly this resembles the Maximum Independent Set problem, however, I am having trouble seeing how to do the reduction. My idea is to generate a graph $G'$ such that vertices represents people and an edge between two vertices means those two people know each other.

The problem is, this graph can be disconnected so any ideas as to how this can be reduced?

EDIT:

Take for instance this graph $G'$

One possible Maximum Independent Set is clearly $\{2,3,7,5\}$ but does it matter if the graph is disconnected?

Your problem, as stated, is already the independent set problem, as defined e.g. on Wikipedia.
A very similar NP-Complete problem is Clique, which is part of Karp's original 21 NP-complete problems, where, given a graph $G$ and an integer $k$, you try to find a complete subgraph of size $k$. It is easy to see that looking for an independent set in a graph is the same as looking for a clique in its complement graph.
In Karp's paper one can also find a straightforward reduction from SAT to Clique, and the reduction does not depend on whether the graph is connected or not. Hence it does not matter whether your graph is connected or disconnected.


Can constraint satisfaction problems be solved with Prolog? Is "party attendance" type of problems solvable in Prolog? For example:

  Burdock Muldoon and Carlotta Pinkstone both said they would come if Albus Dumbledore came. Albus Dumbledore and Daisy Dodderidge both said they would come if Carlotta Pinkstone came. Albus Dumbledore, Burdock Muldoon, and Carlotta Pinkstone all said they would come if Elfrida Clagg came. Carlotta Pinkstone and Daisy Dodderidge both said they would come if Falco Aesalon came. Burdock Muldoon, Elfrida Clagg, and Falco Aesalon all said they would come if Carlotta Pinkstone and Daisy Dodderidge both came. Daisy Dodderidge said she would come if Albus Dumbledore and Burdock Muldoon both came.
  Whom is needs to be persuaded to attend the party in order to ensure that all her invitees attend?

I have tried to express this in GNU Prolog:

attend(BM) :- attend(AD).
attend(CP) :- attend(AD).
attend(AD) :- attend(CP).
attend(DD) :- attend(CP).
attend(AD) :- attend(EC).
attend(BM) :- attend(EC).
attend(CP) :- attend(EC).
attend(CP) :- attend(FA).
attend(DD) :- attend(FA).
attend(BM) :- attend(CP),attend(DD).
attend(EC) :- attend(CP),attend(DD).
attend(FA) :- attend(CP),attend(DD).
attend(DD) :- attend(AD),attend(BM).

attend(FA). /* try different seed invitees in order to see if all would attend*/

/* input:
write('invited:'),nl,
  attend(X),write(X),nl,
  fail.*/

I'm experiencing stack overflow (no pun), and have no knowledge of prolog evaluation, this is why I'm asking.

Generally speaking, this problem can be cast into Boolean CNF satisfaction formula (with 6 boolean variables). Therefore, does the prolog perspective have any merit?

To solve a problem with Prolog, as with any programming language, be it declarative or imperative, you have to think about the representation of the solution and the input.

Since this is a programming question, it would've been popular on StackOverflow.com where programmers solve programming problems. Here I would attempt to be more scientific.

To solve the problem in the OP one has to reverse the relation defined by the dependencies stated in the input. Clauses of the form $Attend(X) \to Attend(Y) \wedge Attend(Z)$ are easy to reverse. The clauses $Attend(AD)\wedge Attend(BM)\to Attend(DD)$ like

  Daisy Dodderidge said she would come if Albus Dumbledore and Burdock
  Muldoon both came

are more difficult to treat.

With Prolog the first simple approach is to avoid a full reversal of the  relationship and be goal directed instead.

Assume an ordering on the list of guests and use a rule

$\qquad \left\{\begin{align}
 A(X)\wedge A(Y) &\to A(Z), \\
 A(W)&\to A(X), \\
 A(W)&\to A(Y), \\
 X&<Z, \\
 Y&<Z\end{align}\right\}\quad \vdash \quad A(W) \to A(Z)$

(We use $A(X)$ instead of $Attend(X)$ to keep it short)

This rule is easy to implement.

A rather naive approach

For readability let follows be the relation given as an input, and brings be its reverse.

Then the input is given by

follows(bm,[ad]).
follows(cp,[ad]).
follows(ad,[cp]).
follows(dd,[cp]).
follows(ad,[ec]).
follows(bm,[ec]).
follows(cp,[ec]).
follows(cp,[fa]).
follows(dd,[fa]).
follows(bm,[cp,dd]).
follows(ec,[cp,dd]).
follows(fa,[cp,dd]).
follows(dd,[ad,bm]).

And brings can be defined as follows:

brings(X,S):-brings(X,S,[]).

brings(_X,[],_S).
brings(X,[X|L],S):-brings(X,L,[X|S]).
brings(X,[Y|L],S):-follows(Y,[X]),brings(X,L,[Y|S]).
brings(X,[Y|L],S):-follows(Y,[A,B]),
          member(A,S),member(B,S),brings(X,L,[Y|S]).

Here the third argument in brings/3(X,L,S) is the list of guests that were already proven to attend if $X$ attends.

If we define

 partymaker(X):-Guests=[ad,bm,cp,dd,ec,fa],member(X,Guests),brings(X,Guests).

We get the following unique solutions:

 [ad,ec]

This is not the complete list, since under the alphabetical ordering the clause

 follows(bm,[cp,dd]).

is not working.

A rather involved solution to the original puzzle

To solve the problem completely you have to actually let the system try to prove attendance for later guests without introducing infinite loops to the search tree. There are multiple ways to accomplish this goal. Each has its advantages and disadvantages.

One way is to redefine brings/2 as follows:

brings(X,S):-brings(X,S,[],[]).

% brings(X,RemainsToBring,AlreadyTaken,AlreadyTried).
%
% Problem solved
brings(_X,[],_S,_N).
% Self
brings(X,[X|L],S,N):-brings(X,L,[X|S],N).
% Follower
brings(X,[Y|L],S,N):-follows(Y,[X]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 2
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),
                   follows(Y,[A,B]),
                   try_bring(X,A,L,S,[Y|N]),
                   try_bring(X,B,L,S,[Y|N]),brings(X,L,[Y|S],N).
% Y is not a follower, but X can bring 1
brings(X,[Y|L],S,N):- \+member(Y,N),\+follows(Y,[X]),\+follows(Y,[_A,_B]),
                   follows(Y,[C]),
                   try_bring(X,C,L,S,[Y|N]),brings(X,L,[Y|S],N).

try_bring(_X,A,_L,S,_N):-member(A,S).
try_bring(X,A,L,S,N):- \+member(A,S),sort([A|L],Y),brings(X,Y,S,N).

The last argument in brings/4 is necessary to avoid an infinite loop in try_bring.

This gives the following answers: Albus, Carlotta, Elfrida and Falco. However this solution is not the most efficient one since backtracking is introduced where it sometimes can be avoided.

A general solution

After the link to the Third International NoCOUG SQL & NoSQL Challenge was added to the original question, it became clear that what we are after is a general reachability checker on the set of subsets of the set of guests, where
the transition relation is defined by rules given such that
an application of the rule $r(X,S): V \to V'$ is a guarded command:

  if $S \subseteq V$ then $V' = V \cup \{X\}$.

We are interested in the minimal subsets $V$ such that the whole set $U$ of guests is reachable from $V$ after a finite sequence of rule applications.

add_element(X,V,U):- ( var(V) -> % set difference that works in both modes
                           member(X,U),subtract(U,[X],V);
                      \+member(X,V),sort([X|V],U) ).

support(V,U):- guests(G), % rule application
               member(X,G),
               add_element(X,V,U),
               follows(X,S),
               subset(S,V).

set_support(U,V):- support(V1,U), % sort of a minimal set
               ( support(_V2,V1) ->
                      set_support(V1,V) ;
                 V = V1).

is_duplicate(X,[Y|L]):- ( subset(Y,X) ; is_duplicate(X,L) ).

% purging solutions that are not truly minimal
minimal_support(U,L):-minimal_support(U,[],L).
minimal_support([],L,L).
minimal_support([X|L],L1,L2):-( append(L,L1,U),is_duplicate(X,U) ->
                                    minimal_support(L,L1,L2);
                                minimal_support(L,[X|L1],L2) ).

solution(L):- guests(G),setof(X,set_support(G,X),S),
              minimal_support(S,L).

Now if for instance dataset #2 is given as

follows(fa,[dd,ec]).
follows(cp,[ad,bm]).
guests([ad,bm,cp,dd,ec,fa]).

We get the answer L = [[ad, bm, dd, ec]]. Which means that all guests but Carlotte and Falco must be invited.

The answers this solution gave me matched the solutions given in the Wicked Witch article with the exception of dataset #6, where more solutions were produced. This seems to be the correct solution.

Finally, I must mention the CLP(FD) library of Prolog that is particularly suitable for this sort of problems.


Show L1 /L2 is regular Let $L_1$ and $L_2$ be two languages over an alphabet $\Sigma$. The quotient of $L_1$ and $L_2$ is the language
  $L_1/L_2 = \{x : \exists y \in L_2, xy \in L_1\}$

  Show that if $L_1$ is regular and $L_2$ is any language, then $L_1/L_2$ is regular.

I've looked up online how to do this but it not very helpful. So far I know that $L_1$ and $L_2 \in \Sigma^*$    and that $L_1 = \{xy \mid x \in \Sigma^* \text{ and } y \in \Sigma^*\}$ and we can say it is regular by concatenation and $L_2 \in \Sigma^*$  which is any language.

From here, we can say that in $L_1$, $x$ has an accept state before going to the DFA for $y$ and $L_1 / L_2$ would just be eliminating the DFA for $y$, leaving you with just $x$, which still has an accept state, which makes it regular. I don't know how to put this in words and not pictures.

Let $A$ be a DFA accepting $L_1$, and let $Q$ be its set of states. Denote by $L_A(q)$ the set of words which cause $A$ to move from its initial state to state $q$. For each state $q$ and word $w$, one of the following holds (exercise):

For every $x \in L_A(q)$, $xw \in L_1$.
For every $x \in L_A(q)$, $xw \notin L_1$.

We now modify $A$ by determining its accepting states as follows. A state $q$ is accepting if for some word $w \in L_2$, $xw \in L_1$ for all $x \in L_A(q)$. It is not too hard to show that the modified automaton accepts $L_1/L_2$ (exercise).


Does quantum computing convert any O(2^n) algorithm into a polynomial running time and how? For example, if it is a $ O(2^n) $ algorithm that loops through 0 to $ 2^n - 1 $ and check whether the number of 1 bits is divisible by 3, 5, 7, 9, 11, does quantum computing reduce it to non-exponential time and how?

No it does not. I mean probably. Because no-one really knows.

What do I mean by we don't know? We're not even 100 % sure whether P=NP or not and if it does, sure a quantum computer can solve any NP problem in polynomial time, same as a deterministic Turing machine.

However we assume that is not the case and we also expect the classes of NP and BQP (bounded-error quantum polynomial-time) to overlap, but each may contain problems the other one does not (i.e. neither contains the other). If NP contains something BQP does not, it surely has to be at least all NP-complete problems, including the TSP you mentioned in one of your comments. With these assumptions quantum computer cannot solve TSP in polynomial time (even with a given probability).

What we do have right now is Grover's algorithm, which provides quadratic speedup for black-box problems. Which means if the best we can come up with is brute force in $O(2^n)$ steps, Grover can solve it in $O(2^{(n/2)})=O(\sqrt{2}^n)$ steps with a given probability. That is it gives a quadratic speed-up, not exponential.


Lower bounds for space with some probability of error There is an  information theoretic lower bound of $\log_2 {U \choose x}$  for the number of bits to represent a subset of $x$ elements chosen from a universe of size $U$.  We can in principle use this representation (perhaps inefficiently) as a data structure to test if any query is part of this subset.

How can you show a similar information theoretic lower bound if we are happy to have false positives with some probability $p$?

In "Network applications of Bloom filters: A survey", Broder and Mitzenmacher show an $x \log_2 (1/p)$ lower bound on the space usage.


Count of distinct substrings in string inside range Having string $S$ of length $n$, finding the count of distinct substrings can be done in linear time using LCP array. Instead of asking for unique substrings count in whole string $S$, query $q$ containing indexing $(i,j)$ where $0 \le i \le  j < n$ is asking for count of distinct substring inside given query range for string $S[i..j]$.

My approach is just applying linear time construction of LCP array to each query. It gives complexity $O(|q|n)$. Number of queries could raise to order of $n$ so answering all queries makes it $O(n^2)$.

Can it be done better, than linear time for every query?

In general, if one process substring of string for which we already have suffix array, suffix tree, lcp array, are those structures not relevant anymore, and must be build from scratch again?

The question does not motivate the number of queries being $O(n)$, which seems an arbitrary worst case since the number of unique possible queries is the number of ordered pairs and thus $O(n^2)$.

Here are two different solutions with better time complexity for the $O(n^2)$ case based on (implicit) suffix trees constructed incrementally with Ukkonen's algorithm. Both solutions are based on preprocessing and have complexity $O(n^2 + |Q|)$ where $Q$ is the set of queries. The second solution runs in $O(n + |Q|)$ if all queries have the same width.

Solution 1 - Preprocess all unique queries

Iterate over the suffixes of $S$. For each suffix $S_i=S[i..n]$, build the suffix tree of $S_i$ with Ukkonen's algorithm. After update $j$ to the current suffix tree, store the tree size in a matrix at position $(i,i+j-1)$. A query for the range $[x,y]$ is answered by the matrix element at $(x,y)$.

Suffix tree size can be stored along with the suffix tree and updated in constant time at each step by modifying the update procedure in Ukkonen's algorithm. For each update the size increases by the current number of leaves.

Solution 2 - Preprocess unique query widths

This solution is harder to implement but requires less preprocessing work if there are few query widths. Preprocessing takes $O(n)$ time if there is only one query width.

For each query width $w$, use a sliding window of width $w$ and incrementally build a suffix tree. Remove the suffix starting one character to the left of the window by remove the longest suffix from the tree. At each step, the current number of substrings within the sliding window is the tree size.

All queries can then be answered in linear time by using the results of the precomputation.

Note: removing the longest suffix can be done by removing the oldest leaf of the suffix tree. It is not easy to implement correctly.


What complexity class decision problems can be solved by only addition, multiplication, division and subtraction? So in what complexity class would all decision problems in that class can be transformed into a problem (by many-one reduction) that its solution only involves basic arithmetic operation of multiplication, division, addition and subtraction?

So, like this: for every problem, there is input and output (we consider only those that halt) and my question is that is there any complexity class that all problems in the class can be transformed into a problem that involves only elementary arithmetic of the form of arithmetic function involving only arithmetic like $2^x+x^5/4-4x+2$ where $x$ is input coded as natural number.

The question isn't exactly well-defined, but seems like a good/interesting question to me. I believe the answer you might be looking for is the class of Elementary Recursive functions. This class consists of almost exactly what you described: Problems solvable by functions that can be written with only addition, subtraction, and multiplication of integers. (Except, we also require a zero function and a "projection" function that outputs one of the inputs.)

You can get more functions (the Primitive Recursive functions) by additionally allowing functions that call themselves (but are guaranteed to terminate). Finally, you can get the class of all Turing-computable functions by introducing a minimization operator: find the minimum $x$ such that $f(x) = 0$.

Anyway, it turns out that $\mathsf{EXPTIME} \subsetneq \mathsf{ELEMENTARY}$, so it includes many (most?) problems that we'd usually consider interesting.


What is happening in this part of the LC3? This is a diagram of the LC3 Computer

I am trying to understand what is happening in the parts I highlighted. The part I had highlighted had the instruction bit sign extended to 16 bits and then passed on to the SR2 Mux. Does anyone know what instruction is being carried out here or what the role of the mux(SR2) is here?

This would appear to be a picture of the LC-3 data path from the book Patt, Yale N; Patel, Sanjay J: Introduction to Computing Systems.

The IR is the instruction register, the register where the actual bits of the instruction are fetched in the beginning cycles of processing the instruction.  The SEXT unit takes the immediate field out of the instruction.  The SR2MUX is used by the control unit to control whether the second operand of the instruction comes from a register operand or the immediate operand.


Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases I am trying to design a parallel scheduling algorithm based on a constraint graph $G=(V,E)$ in which each node represents a task and each edge $e=(v_1, v_2)$ signifies, that tasks $v_1$ and $v_2$ can not be executed in parallel. Each task is executed exactly once, so the problem is finding "good" independent sets $V_i$, so that
$$
\bigcup_{i=1}^{k} V_i = V\\
$$
with all independent sets $V_i, V_j$ being pairwise disjoint. Since MaxIS is NP-Hard my approach would be solving MIS repeatedly (finding some maximal independent set, removing those vertices and start again until the Graph is empty). I know that in the worst case of $G$ being a clique this approach would yield $n$ iterations, however in my instance i would have the guarantee that the number of neighbors of each node would be upper-bound by $c \ll |V|$.
My question is: Given such a $c$ is there any upper bound on the number of necessary steps $k$?

A partition of a graph into independent set is the same as graph coloring. Therefore we can reformulate your question as follows:

Can we bound the chromatic number of a graph in terms of its maximum degree?

If every vertex has at most $c$ different neighbors, then the chromatic number is at most $c+1$, and this can be achieved using a greedy approach: scan the vertices in an arbitrary order, and color each vertex in a color different from all its already colored neighbors (this will always succeed since there are $c+1$ possible colors and only $c$ potential already colored neighbors).
There are graphs with maximum degree $c$ which have chromatic number $c+1$, for example the clique $K_{c+1}$ on $c+1$ vertices, so this bound is tight.


How to prove a language isn't necessarily regular? Assuming we have a regular language $L$, how can we prove that $L'= \{ xz \mid \exists y : xyz \in L \text{ and } |x|=|y|=|z|\}$ isn't necessarily regular.
So far I can't come up with much for how to solve this. I was thinking we could solve this by either generating an example where $L'$ isn't regular or we could use the pumping-lemma, but I'm unsure how to get started. This was the hardest one in my set of practice problems.

If we take $L = \{a^n \mid n \in \mathbb{N}\}$, then $L' = \{a^{2n} \mid n \in \mathbb{N}\}$, which is a perfectly fine regular language. Or even more trival, we could observe that $\emptyset' = \emptyset$.
As such, it does not hold that $L'$ is never regular for a regular language $L$. This means that answering the question will involve constructing a particular language $L$ for which you can prove that $L'$ is not regular (and such a proof could use the pumping lemma).
As a heuristic for how to attempt this, I would first look at some typical examples of non-regular languages, and try to find a way to express them as $L'$ for some regular language.  If I don't succeed with that, I'd attempt to built $L$ by simultaneously ensuring that $L$ itself is regular, and by running the pumping lemma on $L'$ to prove that it is not.


How to test image segmentation algorithms? What would be an ideal environment/manner to judge the effectiveness of multiple segmentation algorithms? The goal is to determine which algorithms provide the best results for pre-clinical imaging. Our group has considered a GUI in MATLAB, and have different modules for different algorithms. Various papers have conducted such algorithm analyses in clinical scenarios, but none give an indication to their environment.

Google "image segmentation benchmark".  You will find various data sets with ground truth, such as this one.


Circuits for Modular Arithmetic I've read this which describes how to do do integer arithmetic in circuits. The one thing that it does not describe is how to do these operations with a modulus. How can modular arithmetic be done in circuits? Can someone point me to a resource or describe the modular step here?

In general, everything that you can describe in pseudocode, you can convert into a circuit. So if you can do modular arithmetic by hand, then a circuit can do it. More to the point, here are some concrete ideas for doing modular arithmetic, where the modulus is $m$:

Addition: You already know how to add two numbers. Assuming both numbers were in $\{0,\ldots,m-1\}$, the answer lies in $\{0,\ldots,2m-2\}$, so it is enough to check whether the results is at least $m$, and if so, subtract $m$.
Subtraction: This is similar to addition. The idea is that $-a = m-a$.
Multiplication: Here the basic idea is to compute the result $ab$, divide by $m$, and keep the remainder. You can (possibly) optimize this by doing modular reductions along the way.
Division: This is more complicated, and is probably better implemented in microcode or software. Suppose we want to compute $a/b$. If $m$ is prime then we can assume that $b \neq 0$. We compute the modular reciprocal $b^{-1}$ of $b$ using the extended Euclidean algorithm, and then multiply $a$ by $b^{-1}$. If $m$ is composite then the situation is slightly more complicated since $b$ doesn't always have an inverse. In that case we first compute the GCD $g = (a,b)$, and $a' = a/g$, $b' = b/g$. There is a quotient $a/b$ only if $(b',m) = 1$, in which case we can proceed as before.
Powering: This is again quite complicated, and better implemented in microcode or software. Here the idea is to use the repeated squaring algorithm, reducing modulo $m$ at every step.
Discrete logarithm: Given $g$ and $g^a$, find $a$. This is complicated enough that it probably isn't implemented in hardware.


Shortest continuous path between shapes without passing thru other shapes, in a specific order? I have the following points, shapes, and paths.  I would like to find a path that goes through all of them:

I want a path that first traverses the circle, then traverses the square, then traverses the star in the middle, in that order.

It's simple to go to the circle from the bottom left and around it, hitting each point.  However, the second shape (the square) is in the top right corner, so I have to go around the star (so I don't cross it) and traverse the square. Finally, I go to the middle, hit each of the points of the star and done. Once that is done, going backwards is pretty easy.

This is an easy example.  In my situation, though, there can be hundreds of shapes in between each of them and I have to go to each shape in the order they are stated.

How do I calculate a path that avoids a particular shape (e.g., the star)? I'm not sure what algorithm to look for. Is it a Travelling salesman problem? A*?

The shapes are defined on a grid. This is what I mean:

"1" means the path must go thru here and "0" is empty space which can be used to get to from one place to another.

The key step is: get from point $Q$ to shape $S$, while avoiding shape $A$.  For instance, point $Q$ might be the last point you visit on the circle, $S$ might be the square, and $A$ might be the star.

This can be solved using breadth-first search or A*.  The vertices are the grid points labelled "0".  You star the search at point $Q$, and try to find the shortest path to some point on $S$ (while at each step you only go through squares marked 0).  You can solve this with either BFS or A*: BFS is simpler to implement, A* will run faster.

If you additionally want to find the shortest path through all of the shapes (something that's not stated in the question), then you can fo the following: for all points $Q$ in shape $S_1$, and all points $R$ in shape $S_2$, calculate the shortest way to get from $Q$ to $R$ while avoiding shape $A$.  Then add these as edges to a directed graph (where the length of the edge $Q\to R$ corresponds to the length of the shortest such path).  Also add edges $R \to R'$ for each pair of points $R,R'$ in the same shape where you can enter the shape via $R$ and exit via $R'$.  Finally, you can compute the shortest path in this directed graph.


How can it be detected that a number generator is not really random? I heard that random number generation in computers isn't really random, but there is no efficient algorithm to detect it. How can it be detected at all ?

Computers Being Really Random:

True randomness is impossible for Turing Machines in a theoretical sense, and most computers can't generate truly random output.  Therefore, some modern computers include hardware that allows the computer to access an outside source which will hopefully include some randomness.   One example of how this can be accomplished is to track small fluctuations in temperature inside the computer.  Randomness can be obtained from an outside source as well.  But from the tone of your post I don't think that outside sources of randomness are what you're interested in.

Seeds:

Without an outside addition, everything a computer does is deterministic.  This leads to a big issue: if you call a random number generation program, it will give you the same result every time if you give it the same input.  Clearly, we need a program that outputs a random number to change its behavior each time it's run (otherwise we'll keep getting the same "random" number, which is not particularly helpful).  One idea is to give the program some input, which changes each time the program is run, so that a different number will be output.  We call this input a "seed."  The random number generator needs to take in a seed, perform some operations, and give us a random number.

The current system time is a classic example of a seed.  This gives a long string with high entropy, and if the time is kept track of in a sufficiently granular fashion (i.e. if your system clock uses hours then "time" is a pretty poor seed), you're unlikely to feed the pseudorandom number generator the same number twice.

Algorithms that are Random Enough:

Now we have an algorithm that at least has some way to be different each time it's run.  We give it a seed, and while the algorithm gives the same number when prompted with the same seed, we want the numbers it generates to be random otherwise.  This acts like the above--you take in some input, and it produces some (hopefully different enough from the input to be "random") output.

Now let's say you came up with your own algorithm to do this, and you claim that the numbers you come up with are pretty close to random when you gave it a bunch of different seeds.  How would we test how good it is?

Now we want some algorithm that will take in a seed, do some operations, and produce a random number.  At the simplest, the algorithm could just output the seed--it's not giving us the same number each time, and random seeds give us random outputs.  But clearly that's not what we want.  On the other hand, an algorithm can be fairly complicated, like many actual pseudorandom generators.  How can we tell which algorithms give us "random" numbers  from our not-necessarily-random seeds?  If we can't get it exactly, how can we tell which are best?

It's hard to tell which of those tests are ideal, but it's easy to come up with some minimum requirements these algorithms should meet before we say they give us "random" numbers.  Maybe we want to make sure that your algorithm gives even numbers half the time.  Maybe  we want to make sure that if I ask for a random number between $1$ and $n$, all numbers in that range will be output for some input to your function.  Clearly there are a lot of tests we can run; if your algorithm passes some suite of tests it's a pseudorandom generator.  Which tests to use is a very interesting and well used/studied area of computer science.

Random Enough to Fool an Attacker:

Now what you MAY be referring to is Cryptographially Secure Pseudorandom Generators.  I think the best way to explain this is in the context of the above--here, we're using our randomness for cryptography, so when we're designing tests what we really care about is that someone won't be able to break our security by predicting what random number we picked.   I don't know your level of familiarity with cryptography, but imagine we're doing a simple replacement cypher---each letter is replaced with some other letter.  We want to pick these replacements randomly, so they're hard for an attacker to guess.  But if he can figure out how my random number generator works, he'll be able to solve the whole cipher!  Therefore, cryptographic algorithms require random number generators that are specifically hard to guess.  Specific cryptographic algorithms may require additional tests (like for some sort of nice-enough distribution as mentioned above).

For this reason, CSPRGs are defined in terms of how well other algorithms solve them (which is where we finally come to your question).  Specifically, let's say I have a CSPRG which I'll call R.  R is a CSPRG if and only if there is NO feasible algorithm that can guess which bit it will output next.  This is true even if you know all the previous bits it output!

So let's say that the first five bits my CSPRG has output are 10100.  You don't know the input I used to the program, but you have access to the code I used to write my CSPRG.   Then the claim is that it's impossible for you to write a program to decide if the next bit output will be 101000 or 101001.

So for reasons of cryptography, sometimes how well a pseudorandom number generator does is defined in terms of how predictable it is to other programs.  Note that this still gives much of the intuition of "randomness," as (say) if you know all of the random outputs will be odd it is neither cryptographically secure nor does it pass a common-sense randomness test.


Interactive proof system for graph nonisomorphism $\mathit{GNI} \in \mathrm{PCP}(\mathit{poly}(n),1)$

  GNI is the language of nonisomorphic graphs. Given two grapsh $G_0$ and $G_1$ with $n$ vertices, a verifier expects $\pi$ to contain, for each labeled graph $H$ with $n$ vertices, a bit $\pi[H] \in \{0,1\}$ corresponding to whether $H \equiv G_0$ or $H \equiv G_1$ (arbitrary if neither case holds). Then the verifier can pick a random bit $b \in \{0,1\}$ and a random permutation of $G_b$, $H$. The verifier accepts iff the corresponding bit of $\pi[H]$ is $b$. If $G_0 \not\equiv G_1$ then the verifier accepts with probability $1$ while if $G_0 \equiv G_1$, then the probability of accepting is at most $1/2$.

I was reading this slide and got confused about the following part:

  A bit $\pi[H]\in\{0,1\}$ corresponding to whether $H=G_0$ or $H=G_1$ (arbitrary if
  neither case holds)

But what if both cases hold? In that case, $G_0$ and $G_1$ are isomorphic, and how should we assign the bit? I hope that there's an example.

The slide describes a proof system for graph non-isomorphism. This is a way for the prover to convince the verifier that the two graphs are non-isormorphic. The soundness of this proof system derives from the fact that it cannot work if the graphs are isomorphic. If $G_0 \equiv G_1$ then no matter what the prover does, the acceptance probability is only $1/2$.

How should we assign the bit? Proof systems don't work in this way. A proof system has two guarantees:

Completeness: if the input belongs to the language (in this case, the two graphs are not isomorphic), then there is a proof that convinces the verifier.
Soundness: if the input doesn't belong to the language (in this case, the two graphs are isomorphic), then no proof convinces the verifier.

When proving these two properties of the proof system, we specify a proof only in the first case. In the second case we have to show, instead, that no proof works. It's a different quantifier:

Completeness: if $G_0 \not\equiv G_1$ then there exists a proof which convinces the verifier with probability 1. (When proving completeness, we need to specify the proof that convinces the verifier.)
Soundness: if $G_0 \equiv G_1$ then all proofs convince the verifier with probability 1/2. (When proving soundness, we don't need to specify a proof. Indeed, we need to show that all proofs perform badly. In a sense, a proof is given to us, and we have to show that it doesn't convince the verifier.)


How, in hardware, MIPS can access a word in the middle of an address This is am example of a RAM address in the MIPS architecture (32 bits)

I can imagine the RAM as having 32 pins just to inform the RAM address I want to access, so I can access each of these words in the image (because I saw in this vídeo). I think, then, it should need another 32 pins to inform what's the word in that address, just like in the vídeo. I don't know, however, how the CPU could support 2 different 32 pins bus (but this is another problem).

What I don't understand, for real, is why I need and offset in the instruction "load word", if I can only access one address at the time! What if I say "load word", give the address number 2, and then say na offset of 4? It will load part of the word from the address 2, and part from the address 3? How is this possible?

First of all, to short circuit your question, I must say that you can not ready from multiple memory locations at the same time in the MIPS architecture.

Second, your interpretation of the offset is wrong. You assumed the offset is a bit offset, while it's actually an offset in bytes. Meaning if you give the address 2 and offset 4, the memory location to be read from will be 6 (2+4).

Third, more details into the MIPS lw (load word) instruction. The syntax is as follow:
lw  \$d, off(\$r), where \$d is the destination register (where the word is loaded to), off is an immediate 32 bit constant and \$r is your base register. What happens is as follow:

The target ram address is calculated by adding off and the value in \$r.
The calculated address in loaded in the memory register
The control unit enabled the RAM to get the value at the address
The value is set to the \$d register

Fourth, something I haven't mentioned before, related to the addressing pattern of the ram. As you may know, the ram stores bytes, no actual words. What's the problem you may wonder? It's something called word alignment, and it's the reason why you couldn't load a word from address 6. A word is a 4 byte value, and for fast design purposes, when loading a word, the address has to be a multiple of 4. I won't go in the design details, but suffice to say that this permits greater memory transfer speed than allowing any address.

What this means is that when loading and storing words, you have to respect the word boundaries. If you try to read from a bad memory location i.e. not a multiple of 4, e.g. 6, you will have a memory exception; meaning you program likely crashes.

In practice, this mean that if you have to store tree words a,b and c, you could store them at address 0x01234560, 0x01234564 and 0x01234568.

EXTRA: why use an offset

So, in my last example, you might have noticed my words were close in memory, but i didn't start at 0x00000000. Actually, the first word starts at adress 0x01234560. Here's how you can take that into consideration with the lw syntax.

First, set the value of \$r to 0x01234560
Then, to load a, you write lw \$d, 0(\$r). The will load the value at 0+\$r, 0 + 0x01234560 = 0x01234560
Then, to load b, you write lw \$d, 4(\$r). The will load the value at 4+\$r, 4 + 0x01234560 = 0x01234564
Then, to load c, you write lw \$d, 8(\$r). The will load the value at 8+\$r, 8 + 0x01234560 = 0x01234568

I hope this completely answers your question. The only thing I haven't touched is why you'd end up at such complex memory locations. Short answer: it's due to the structure of the compiled program and the way it's loaded into memory. I suggest you look further into that before delving deeper into the world of computer electronics. A sound knowledge of the structure of a program will greatly help understand why the CPU and instruction set were made that way.


Parameter sharing / weight constraints in Neural Networks I would like to train a neural network whose parameters (alternatively, weights) are subject to linear constraints such as

$w_{i,j} = w_{i',j'}$,

where $w_{i,j}$ denotes the weight from input node $i$ to hidden node $j$ in the case of a network with a single layer. (In the case of several hidden layers, it is okay to assume that only weights stemming from the same layer can be related to each other).

It seems that a special case of this is known as parameter sharing in the context of convolutional neural networks where weights have to coincide, roughly speaking, across different layers.

Surprisingly, it seems that there is not much work / need for more general parameter constraints. Being not a machine learning expert, I am wondering whether I am using the wrong keywords in my literature research.

It would be great if someone could point me towards a tool / framework which allows for linear parameter constraints. Mathematically speaking, I would like to specify a linear subspace of the parameter space and project, at each step of the backwardpropagation, the update vector $\Delta w$ onto this very subspace.

Any help will be greatly appreciated.

I'll list two approaches, either of which should work.

Projected gradient descent

One general approach would be to use projected gradient descent, which provides a way to accommodate these kinds of constraints.  For specific kinds of constraints there may be a better way.

Let's recall how we train neural networks.  We have an objective function $\Psi$ that computes the total loss, as a function of the weights $w$.  Training a neural network amounts to solving the optimization problem "minimize $\Psi(w)$".  This is typically done using (stochastic) gradient descent to find the weights $w$ that minimize $\Psi(w)$.  In each iteration, you take a single gradient step to update $w$ (backpropagation is just a way to help you compute the gradient $\nabla \Psi(w)$, to help you take this step).

Now you want to add some constraints on $w$.  Let $\mathcal{R}$ denote the region (linear subspace) of $w$'s that satisfy all your constraints.  Now we want to solve the optimization problem "minimize $\Psi(w)$ subject to $w \in \mathcal{R}$".  One standard way to solve such an optimization problem is to use projected gradient descent: in each iteration, you take a single gradient step to update $w$, then project $w$ to the nearest point in $\mathcal{R}$; and repeat.  So this amounts to doing the standard backprop training procedure for a neural network, but after each weight update, projecting the weights to the nearest valid value that satisfies all the constraints.  You can read more about projected gradient descent in standard resources. In your situation, it is easy to project onto a linear subspace; this is a simple matter of linear algebra.  So projected gradient descent should be straightforward to apply.  It also shouldn't be too hard to add the projection step, in a framework like Tensorflow.  This also has the nice benefit of generalizing beyond linear constraints.

Reparameterization

The other plausible approach would be a reparameterization trick.  If you have $m$ weights, your region $\mathcal{R}$ has the form $\{w : Aw=c\}$, where $A$ is a $m \times n$ matrix and $c$ a constant $m$-vector.  This can be reparametrized into the form $\{Bv\}$ where $B$ is a $n\times n-m$ matrix and $v$ ranges over all possible $n-m$-vectors.  In other words, we can find a matrix $B$ such that every valid weight value $w$ can be expressed as $w=Bv$ for some $v$.  (I think you can compute $B$ as the pseudoinverse of $A$.)  Then, instead of solving the optimization problem "minimize $\Psi(w)$ subject to $w \in \mathcal{R}$", you can solve the optimization problem "minimize $\Psi(Bv)$", where now there are no constraints on $v$.  This in turn can be done using gradient descent.

Once you've found the matrix $B$, you'll probably find the latter approach very easy to implement in frameworks like Tensorflow; you just let $v$ be the variables you are trying to solve for, compute $w$ from $v$ using $w=Bv$, and then the neural network uses these derived weights $w$, and you can ask Tensorflow to minimize the loss as usual.


Lamport's Bakery algorithm I have problems understanding Lamport's bakery algorithm. The thing I do understand is that each thread ask all other threads what number they have.Then the thread takes the maximum number and add 1 to that and give that number to itself. The thread with the lowest number can enter the critical zone and if two or more threads have the lowest number then the thread with the lowest process id will be allowed to enter the critical area. When a thread exits the critical area then it put it's number to 0, meaning it's not interested in going inside the critical area. First when it picks a number higher than 0 it is interested going inside the critical area.

Now here is what I don't understand:

If a thread wants to get into the critical area it picks a number, but what if it changes its mind while it's waiting in line? does it then change its number to 0 or does it go through the critical area anyway when it is its turn?
In Lamport's bakery algorithm there is a Boolean value of "true" or "false". If a thread wants to enter it sets the Boolean value to true, but what is that Boolean value used for in the code? Because when a thread has been inside the critical area it changes its number to 0, so other threads in that way can see it's not interested in going inside the critical area, and if it decides it wants inside the critical area again, then it has to ask all the other threads what their number is and then add 1 to the maximum value which will be its number. So the true and false Boolean seems useless to me. Anybody understand why they are there?

Let me try to help you with.

1) The problem here is that you are missing the big picture. Lamport's Bakery Algorithm (LBA) is just a deadlock-free algorithm that is used for mutual exclusion, so inside a bigger software. One typical way to use it is this (Java-like example):

mutex.lock();
try {
    CS(); // critical section
} finally {
    mutex.unlock(); // mutex has to be released also in case of error
}

For the way LBA is designed it does not allow a thread to "change idea" while waiting (there is no timeout notion in the algorithm): once a thread has called lock() it has to wait until lock() returns (possibly waiting all the other threads' unlock()). This does not mean that a thread is forced to enter in the CS once the lock is acquired. One thread could call lock(), wait until it returns and check if it is still required to run the CS. See below:

mutex.lock();
try {
    if(!tooMuchTimeHasPassed()) {  // is it still meaningful to enter CS?
        CS(); // critical section
    }
} finally {
    mutex.unlock(); // mutex has to be released also in any case
}

The example allow this scenario: one thread acquires the lock, notices that running CS is useless and stops by releasing the lock.

2) The boolean value, as you can see here, is not used to notify other threads about the fact that you have a certain priority or that you are inside the CS: it is only used to say to the other threads that you are still choosing a number. How can some threads decide which of them has the highest priority if some threads have not picked a number yet? In order to acquire the lock one thread A must ensure he has a priority higher then all the others (the outer for loop). If A discovers that another thread B is still searching for a number (the max() operation is not atomic and may require a lot of time) then it waits for B to pick a number and later checks who can go first.

Hope it helped!


Is there a system behind the magic of algorithm analysis? There are lots of questions about how to analyze the running time of algorithms (see, e.g., runtime-analysis and algorithm-analysis).  Many are similar, for instance those asking for a cost analysis of nested loops or divide & conquer algorithms, but most answers seem to be tailor-made.

On the other hand, the answers to another general question explain the larger picture (in particular regarding asymptotic analysis) with some examples, but not how to get your hands dirty.

Is there a structured, general method for analysing the cost of algorithms?  The cost might be the running time (time complexity), or some other measure of cost, such as the number of comparisons executed, the space complexity, or something else.

This is supposed to become a reference question that can be used to point beginners to; hence its broader-than-usual scope. Please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

Translating Code to Mathematics

Given a (more or less) formal operational semantics you can translate an algorithm's (pseudo-)code quite literally into a mathematical expression that gives you the result, provided you can manipulate the expression into a useful form. This works well for additive cost measures such as number of comparisons, swaps, statements, memory accesses, cycles some abstract machine needs, and so on.

Example: Comparisons in Bubblesort

Consider this algorithm that sorts a given array A:

 bubblesort(A) do                   1
  n = A.length;                     2
  for ( i = 0 to n-2 ) do           3
    for ( j = 0 to n-i-2 ) do       4
      if ( A[j] > A[j+1] ) then     5
        tmp    = A[j];              6
        A[j]   = A[j+1];            7
        A[j+1] = tmp;               8
      end                           9
    end                             10
  end                               11
end                                 12

Let's say we want to perform the usual sorting algorithm analysis, that is count the number of element comparisons (line 5). We note immediately that this quantity does not depend on the content of array A, only on its length $n$. So we can translate the (nested) for-loops quite literally into (nested) sums; the loop variable becomes the summation variable and the range carries over. We get:

$\qquad\displaystyle C_{\text{cmp}}(n) = \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1 = \dots = \frac{n(n-1)}{2} = \binom{n}{2}$,

where $1$ is the cost for each execution of line 5 (which we count).

Example: Swaps in Bubblesort

I'll denote by $P_{i,j}$ the subprogram that consists of lines i to j and by $C_{i,j}$ the costs for executing this subprogram (once).

Now let's say we want to count swaps, that is how often $P_{6,8}$ is executed. This is a "basic block", that is a subprogram that is always executed atomically and has some constant cost (here, $1$). Contracting such blocks is one useful simplification that we often apply without thinking or talking about it.

With a similar translation as above we come to the following formula:

$\qquad\displaystyle C_{\text{swaps}}(A) =  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$.

$A^{(i,j)}$ denotes the array's state before the $(i,j)$-th iteration of $P_{5,9}$.

Note that I use $A$ instead of $n$ as parameter; we'll soon see why. I don't add $i$ and $j$ as parameters of $C_{5,9}$ since the costs do not depend on them here (in the uniform cost model, that is); in general, they just might.

Clearly, the costs of $P_{5,9}$ depend on the content of $A$ (the values A[j] and A[j+1], specifically) so we have to account for that. Now we face a challenge: how do we "unwrap" $C_{5,9}$? Well, we can make the dependency on the content of $A$ explicit:

$\qquad\displaystyle C_{5,9}(A^{(i,j)}) = C_5(A^{(i,j)}) +
    \begin{cases}
        1 &, \mathtt{A^{(i,j)}[j] > A^{(i,j)}[j+1]}  \\
        0 &, \text{else}
    \end{cases}$.

For any given input array, these costs are well-defined, but we want a more general statement; we need to make stronger assumptions. Let us investigate three typical cases.

The worst case

Just from looking at the sum and noting that $C_{5,9}(A^{(i,j)}) \in \{0,1\}$, we can find a trivial upper bound for cost:

$\qquad\displaystyle C_{\text{swaps}}(A) \leq  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 1
    = \frac{n(n-1)}{2} = \binom{n}{2}$.

But can this happen, i.e. is there an $A$ for this upper bound is attained? As it turns out, yes: if we input an inversely sorted array of pairwise distinct elements, every iteration must perform a swap¹. Therefore, we have derived the exact worst-case number of swaps of Bubblesort.
The best case

Conversely, there is a trivial lower bound:

$\qquad\displaystyle C_{\text{swaps}}(A) \geq  \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} 0
    = 0$.

This can also happen: on an array that is already sorted, Bubblesort does not execute a single swap.
The average case

Worst and best case open quite a gap. But what is the typical number of swaps? In order to answer this question, we need to define what "typical" means. In theory, we have no reason to prefer one input over another and so we usually assume a uniform distribution over all possible inputs, that is every input is equally likely. We restrict ourselves to arrays with pairwise distinct elements and thus assume the random permutation model.

Then, we can rewrite our costs like this²:

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \sum_{i=0}^{n-2} \sum_{j=0}^{n-i-2} C_{5,9}(A^{(i,j)})$

Now we have to go beyond simple manipulation of sums. By looking at the algorithm, we note that every swap removes exactly one inversion in $A$ (we only ever swap neighbours³). That is, the number of swaps performed on $A$ is exactly the number of inversions $\operatorname{inv}(A)$ of $A$. Thus, we can replace the inner two sums and get

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{n!} \sum_{A} \operatorname{inv}(A)$.

Lucky for us, the average number of inversions has been determined to be

$\qquad\displaystyle \mathbb{E}[C_{\text{swaps}}] = \frac{1}{2} \cdot \binom{n}{2}$

which is our final result. Note that this is exactly half the worst-case cost.

Note that the algorithm was carefully formulated so that "the last" iteration with i = n-1 of the outer loop that never does anything is not executed.
"$\mathbb{E}$" is mathematical notation for "expected value", which here is just the average.
We learn along the way that no algorithm that only swaps neighbouring elements can be asymptotically faster than Bubblesort (even on average) -- the number of inversions is a lower bound for all such algorithms. This applies to e.g. Insertion Sort and Selection Sort.

The General Method

We have seen in the example that we have to translate control structure into mathematics; I will present a typical ensemble of translation rules. We have also seen that the cost of any given subprogram may depend on the current state, that is (roughly) the current values of variables. Since the algorithm (usually) modifies the state, the general method is slightly cumbersome to notate. If you start feeling confused, I suggest you go back to the example or make up your own.

We denote with $\psi$ the current state (imagine it as a set of variable assignments). When we execute a program P starting in state $\psi$, we end up in state $\psi / \mathtt{P}$ (provided P terminates).

Individual statements

Given just a single statement S;, you assign it costs $C_S(\psi)$. This will typically be a constant function.
Expressions

If you have an expression E of the form E1 ∘ E2 (say, an arithmetic expression where ∘ may be addition or multiplication, you add up costs recursively:

$\qquad\displaystyle C_E(\psi) = c_{\circ} + C_{E_1}(\psi) + C_{E_2}(\psi)$.

Note that

the operation cost $c_{\circ}$ may not be constant but depend on the values of $E_1$ and $E_2$ and
evaluation of expressions may change the state in many languages,

so you may have to be flexible with this rule.
Sequence

Given a program P as sequence of programs Q;R, you add the costs to

$\qquad\displaystyle C_P(\psi) = C_Q(\psi) + C_R(\psi / \mathtt{Q})$.
Conditionals

Given a program P of the form if A then Q else R end, the costs depend on the state:

$\qquad\displaystyle C_P(\psi) = C_A(\psi) +
    \begin{cases}
        C_Q(\psi/\mathtt{A}) &, \mathtt{A} \text{ evaluates to true under } \psi \\
        C_R(\psi/\mathtt{A}) &, \text{else}
    \end{cases}$

In general, evaluating A may very well change the state, hence the update for the costs of the individual branches.
For-Loops

Given a program P of the form for x = [x1, ..., xk] do Q end, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{init_for}} + \sum_{i=1}^k c_{\text{step_for}} + C_Q(\psi_i \circ \{\mathtt{x := xi\}})$

where $\psi_i$ is the state before processing Q for value xi, i.e. after the iteration with x being set tox1, ..., xi-1.

Note the extra constants for loop maintenance; the loop variable has to be created ($c_{\text{init_for}}$) and assigned its values ($c_{\text{step_for}}$). This is relevant since

computing the next xi may be costly and
a for-loop with empty body (e.g. after simplifying in a best-case setting with a specific cost) does not have zero cost if it performs iterations.

While-Loops

Given a program P of the form while A do Q end, assign costs

$\qquad\displaystyle C_P(\psi) \\\qquad\ = C_A(\psi) +
    \begin{cases}
        0 &, \mathtt{A} \text{ evaluates to false under } \psi \\
        C_Q(\psi/\mathtt{A}) + C_P(\psi/\mathtt{A;Q}) &, \text{ else}
    \end{cases}$

By inspecting the algorithm, this recurrence can often be represented nicely as a sum similar to the one for for-loops.

Example: Consider this short algorithm:

while x > 0 do    1
  i += 1          2
  x = x/2         3
end               4

By applying the rule, we get

$\qquad\displaystyle C_{1,4}(\{i := i_0; x := x_0\}) \\\qquad\ = c_< +
    \begin{cases}
        0 &, x_0 \leq 0 \\
        c_{+=} + c_/ + C_{1,4}(\{i := i_0 + 1; x := \lfloor x_0/2 \rfloor\}) &, \text{ else}
    \end{cases}$

with some constant costs $c_{\dots}$ for the individual statements. We assume implicitly that these do not depend on state (the values of i and x); this may or may not be true in "reality": think of overflows!

Now we have to solve this recurrence for $C_{1,4}$. We note that neither the number of iterations not the cost of the loop body depend on the value of i, so we can drop it. We are left with this recurrence:

$\qquad\displaystyle C_{1,4}(x) =
    \begin{cases}
        c_> &, x \leq 0 \\
        c_> +  c_{+=} + c_/ + C_{1,4}(\lfloor x/2 \rfloor) &, \text{ else}
    \end{cases}$

This solves with elementary means to

$\qquad\displaystyle C_{1,4}(\psi) = \lceil \log_2 \psi(x) \rceil \cdot (c_> +  c_{+=} + c_/) + c_>$,

reintroducing the full state symbolically; if $\psi = \{ \dots, x := 5, \dots\}$, then $\psi(x) = 5$.
Procedure Calls

Given a program P of the form M(x) for some parameter(s) x where M is a procedure with (named) parameter p, assign costs

$\qquad\displaystyle C_P(\psi) = c_{\text{call}} + C_M(\psi_{\text{glob}} \circ \{p := x\})$.

Note again the extra constant $c_{\text{call}}$ (which might in fact depend on $\psi$!). Procedure calls are expensive due to how they are implemented on real machines, and sometimes even dominate runtime (e.g. evaluating the Fibonacci number recurrence naively).

I gloss over some semantic issues you might have with the state here. You will want to distinguish global state and such local to procedure calls. Let's just assume we pass only global state here and M gets a new local state, initialized by setting the value ofp to x. Furthermore, x may be an expression which we (usually) assume to be evaluated before passing it.

Example: Consider the procedure

fac(n) do
  if ( n <= 1 ) do         1
    return 1               2
  else                     3
    return n * fac(n-1)    4
  end                      5
end

As per the rule(s), we get:

$\qquad\displaystyle\begin{align*} C_{\text{fac}}(\{n := n_0\})
  &= C_{1,5}(\{n := n_0\}) \\
  &= c_{\leq} +
    \begin{cases}
      C_2(\{n := n_0 \}) &, n_0 \leq 1 \\
      C_4(\{n := n_0 \}) &, \text{ else}
    \end{cases} \\
  &= c_{\leq} +
    \begin{cases}
      c_{\text{return}} &, n_0 \leq 1 \\
      c_{\text{return}} + c_* + c_{\text{call}} + C_{\text{fac}}(\{n := n_0 - 1\})
       &, \text{ else}
    \end{cases}
\end{align*}$

Note that we disregard global state, as fac clearly does not access any. This particular recurrence is easy to solve to

$\qquad\displaystyle C_{\text{fac}}(\psi) = \psi(n) \cdot (c_{\leq} + c_{\text{return}})
                                        + (\psi(n) - 1) \cdot (c_* + c_{\text{call}})$

We have covered the language features you will encounter in typical pseudo code. Beware hidden costs when analysing high-level pseudo code; if in doubt, unfold. The notation may seem cumbersome and is certainly a matter of taste; the concepts listed can not be ignored, though. However, with some experience you will be able to see right away which parts of the state are relevant for which cost measure, for instance "problem size" or "number of vertices". The rest can be dropped -- this simplifies things significantly!

If you think now that this is far too complicated, be advised: it is! Deriving exact costs of algorithms in any model that is so close to real machines as to enable runtime predictions (even relative ones) is a tough endeavour. And that's not even considering caching and other nasty effects on real machines.

Therefore, algorithm analysis is often simplified to the point of being mathematically tractable. For instance, if you don't need exact costs, you can over- or underestimate at any point (for upper resp. lower bounds): reduce the set of constants, get rid of conditionals, simplify sums, and so on.

A note on asymptotic cost

What you will usually find in literature and on the webs is the "Big-Oh analysis". The proper term is asymptotic analysis which means that instead of deriving exact costs as we did in the examples, you only give costs up to a constant factor and in the limit (roughly speaking, "for big $n$").

This is (often) fair since abstract statements have some (generally unknown) costs in reality, depending on machine, operating system and other factors, and short runtimes may be dominated by the operating system setting up the process in the first place and whatnot. So you get some perturbation, anyway.

Here is how asymptotic analysis relates to this approach.

Identify dominant operations (that induce costs), that is operations that occur most often (up to constant factors). In the Bubblesort example, one possible choice is the comparison in line 5.

Alternatively, bound all constants for elementary operations by their maximum (from above) resp. their minimum (from below) and perform the usual analysis.
Perform the analysis using execution counts of this operation as cost.
When simplifying, allow estimations. Take care to only allow estimations from above if your goal is an upper bound ($O$) resp. from below if you want lower bounds ($\Omega$).

Make sure you understand the meaning of Landau symbols. Remember that such bounds exist for all three cases; using $O$ does not imply a worst-case analysis.

Further reading

There are many more challenges and tricks in algorithm analysis. Here is some recommended reading.

How to come up with the runtime of algorithms?
How to describe algorithms, prove and analyse them?
Why use comparisons instead of runtime for comparing two algorithms?
How can we assume that basic operations on numbers take constant time?
What constitutes one unit of time in runtime analysis?
Solving or approximating recurrence relations for sequences of numbers
Basics of Amortised Analysis

There are many questions tagged algorithm-analysis around that use techniques similar to this.


How can I explain lossless compression to a misguided audio engineer? I have recently been involved in a discussion with someone who doesn't accept that lossless compression is possible, even in principle. This person considers himself to be technically literate, and an expert in his field of audio engineering.
I and several others have patiently tried to explain how lossless compression is possible, using simple examples such as run-length encoding and delta encoding, but he refuses to believe that it's possible for a lossless audio codec such as FLAC, for example, to exactly reproduce the input bitstream from the raw PCM data.
His response is always along the lines of:

it's getting smaller, so it must be losing data
"lossless" is just a buzzword used by software companies to sell their software, it doesn't actually mean lossless

Are there any other examples I can use to demonstrate conclusively that lossless compression is actually possible?

Tell him to write out the integers between 1 and 100, inclusive. Ask him how it can be that your instruction was so much shorter than the list of numbers he wrote out. Did that brevity cause him to write out the wrong thing?


Does upgrading after all locks and before all unlocks violate 2PL? 2PL's rule says:

Upgrading of lock (from S(a) to X (a)) is allowed in growing phase.

But what if upgrading lies after the last lock and before the first unlock? Does it still count "in the growing phase"? For example, is the transaction below a 2PL?
begin
lock-S(X)
read(X)
lock-S(Y)
read(Y)
**upgrade(Y)**
write(Y)
unlock(X)
unlock(Y)
commit

It's allowed.
You can upgrade any locks during the growing phase, and downgrade any locks you want during the shrinking phase, and it's a valid 2PL. What you can't do is release/downgrade during the growing phase, or acquire/upgrade during the shrinking phase, because this breaks the phase ordering rule.
Note that even during the shrinking phase, downgrading breaks strict 2PL, because it releases an exclusive lock. More on this in a moment.
I think the reason why you may be asking is that your example transaction reads Y, then upgrades, then writes Y. You may be wondering what happens if some other transaction holds a shared lock on Y, and also wants to upgrade.
This is a deadlock situation, so one of them wins and the other transaction is aborted, or rolled back to at least the point where the shared lock on Y was acquired. The lock upgrade operation can and does cause aborts. Similarly, downgrading can cause cascading aborts, which is yet another reason why most database systems prefer strict locking.


Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$? It is known that any (deterministic, single-taped) Turing-machine that runs in time $o(n\log n)$, decides a regular language (e.g., see this link). Thus, there exists an equivalent Turing-machine that runs in time $O(n)$. In other words, if $t(n)=o(n\log n)$ then $$\mathsf{DTIME}\left(t\left(n\right)\right)\backslash\mathsf{DTIME}\left(n\right)=\emptyset.$$

I was wondering whether there exists an example in which the original Turing-machine was not already running in time $O(n)$.

To sum up: Does there exist a Turing-machine that runs in time $o(n\log n)$, but not $O(n)$?

The answer seems to be negative, according to Corollary 4.12 of Verifying Time Complexity of Deterministic Turing Machines by David Gajser (ArXiv).


Maximal Minimum Spanning Tree by Removing $k$ Edges The problem is as follows:

  Consider a connected, undirected, and weighted graph $G = (V, E, w)$ and an integer $0 < k < |E| - |V| + 1$. Describe and analyze and efficient algorithm to remove at most $k$ edges from $E$ such that the resulting graph $G' = (V, E' \subseteq E, w)$ has a maximal weight minimum spanning tree over all possible $G'$.

I initially thought a greedy algorithm would work with "just remove the $k$ smallest edges as long as the graph remains connected." However, this does not work, consider the following graph and $k = 1$:

The MST of $G$ has weight 9. If we remove the minimal edge $(B, C)$, the MST of the resulting graph has weight 12. However, if we remove the edge $(A, B)$, the MST of the resulting graph has weight 13. So this greedy strategy does not work.

Other strategies, we can first note that it only helps to remove edges that are in the MST of $G$ initially. So we can first determine $T = MST(G)$. The next (inefficient) thing we could do is consider each edge in $e \in T$ and do:

Remove $e$ from $T$, cutting $T$ into $T_1$ and $T_2$.
Determine the next smallest edge $e'$ spanning $T_1$ and $T_2$ in $G$.
Keep track of $e$ such that it maximizes $w(e') - w(e)$.

Repeat this $k$ times. This doesn't seem very efficient though. This would be something like $O(k \cdot n \cdot (n + m))$ I think. We could optimize this a bit by keeping track of an ordered set of edges on the cuts.

I am wondering if there exists an algorithm that is $O(km \log n)$ or better. Any approaches / advice would be appreciated.

This is known as the $k$ most vital edges for the minimum spanning tree problem. It has been proved as NP-hard [1].

For fixed $k$, Weifa Liang proposed an $O\left(n^k\alpha((k+1)(n-1),n)\right)$ algorithm where $\alpha$ is a functional inverse of Ackermann’s function [2], and can be improved to $O\left(n^k\log\alpha((k+1)(n-1),n)\right)$ using Seth Pettie's sensitivity analysis [3].

[1] Frederickson, G. N., & Solis-Oba, R. (1999). Increasing the weight of minimum spanning trees. Journal of Algorithms, 33(2), 244-266.

[2] Liang, W. (2001). Finding the k most vital edges with respect to minimum spanning trees for fixed k. Discrete Applied Mathematics, 113(2-3), 319-327.

[3] Pettie, S. (2005, December). Sensitivity analysis of minimum spanning trees in sub-inverse-Ackermann time. In International Symposium on Algorithms and Computation (pp. 964-973). Springer, Berlin, Heidelberg.


How the LZ77 compression algorithm handles the case when the entire look-ahead buffer is matched in the search buffer The LZ77 compression algorithm uses a sliding window technique, where the window consists of a look-ahead puffer and a search-buffer. What I am wondering is how the algorithm handles the case if the match of the word in the search-buffer is the entire word in the look-ahead buffer? According to the desriptions I find, the algorithm matches as long as it can, and then outputs the offset, the length of the match and the next token after the matched portion in the look-ahead buffer, but in case the entire look-ahead buffer is matched we do not have a next token to output?

I nowhere find this case described, for example the pseudocode just states "X first char after p in view", but I am asking about the case where we have no char after p in the view, as p is entire view?

For example, consider a search buffer of size 5 and a look-ahead buffer of size 4 and we read in

|abrar|rarr|ad

then we find a match at offset 3, and the match (which extends behind the boundary between both puffers, but this is no problem) goes up to all of rarr, even the next a could be matched, but what we should do now, should we output (3,4, C(a)) where C(a) denotes the code of a which is not in the look-ahead buffer, or should we just match the first 3 tokens?

A simple solution:  your look ahead buffer is no smaller than your longest match length.
  As long as the start position is in the Search Buffer(a min of 1 byte), then the look-ahead buffer will have that one extra byte available to use as the follow byte


Fast k mismatch string matching algorithm I am looking for a fast k-mismatch string matching algorithm. Given a pattern string P of length m, and a text string T of length n, I need a fast (linear time) algorithm to find all positions where P matches a substring of T with at most k mismatches. This is different from the k-differences problem (edit distance). A mismatch implies the substring and the pattern have a different letter in at most k positions. I really only require k=1 (at most 1 mismatch), so a fast algorithm for the specific case of k=1 will also suffice. The alphabet size is 26 (case-insensitive english text), so space requirement should not grow too fast with the size of the alphabet (eg., the FAAST algorithm, I believe, takes space exponential in the size of the alphabet, and so is suitable only for protein and gene sequences).

A dynamic programming based approach will tend to be O(mn) in the worst case, which will be too slow. I believe there are modifications of the Boyer-Moore algorithm for this, but I am not able to get my hands on such papers. I do not have subscription to access academic journals or publications, so any references will have to be in the public domain.

I would greatly appreciate any pointers, or references to freely available documents, or the algorithm itself for this problem.

Suffix arrays can be used for this problem. They contain the starting positions of each suffix of the string sorted in lexicographic order. Even though they can be constructed naively in $O(n\log n)$ complexity, there are methods to construct them in $\Theta(n)$ complexity. See for example this and this. Let us call this suffix array SA.

Once the suffix array has been constructed, we need to construct a Longest Common Prefix (LCP) array for the suffix array. The LCP array stores the length of the longest common prefix between two consecutive prefixes in the suffix array (lexicographic consecutive suffixes). Thus, LCP[i] contains the length of the longest common prefix between SA[i] and SA[i+1]. This array can also be constructed in linear time: see here, here and here for some good references.

Now, to compute the length of the longest prefix common to any two suffixes in the suffix tree (instead of consecutive suffixes), we need to use some RMQ data structure. It has been shown in the references above (and can be seen easily if the array is visualized as a suffix tree), that the length of the longest common prefix between two suffixes having positions $u$ and $v$ ($u < v$) in the suffix array, can be obtained as $min_{u<=k<=v-1}{LCP[k]}$. A good RMQ can pre-process the $LCP$ array in $O(n)$ or $O(n\log n)$ time and respond to queries of the form $LCP[u, v]$ in $O(1)$ time. See here for a succint RMQ algorithm, and here for a good tutorial on RMQ's, and the relationship (and reductions) between LCA and RMQs. This has another nice alternative approach.

With this information, we construct the suffix array and associated arrays (as described above) for the concatenation of the two strings with a delimiter in between (such as T#P, where '#' does not occur in either string). Then, we can perform k mismatch string matching using the "kangaroo" method. This and this explain the kangaroo method in the context of suffix trees, but can be directly applied to suffix arrays too. For every index $i$ of the text $T$, find the $LCP$ of the suffix of $T$ starting at $i$ and the suffix of $P$ starting at 0. This gives the location after which the first mismatch occurs when matching $P$ with $T[i]$. Let this length be $l_0$. Skip the mismatching character in both $T$ and $P$ and try to match the remaining strings. That is, again find the $LCP$ of $T[i + l_0 + 1]$ and $P[l_0 + 1]$. Repeat this till you obtain $k$ mismatches, or either string finishes. Each $LCP$ is $O(1)$. There are $O(k)$ $LCP$'s for each index $i$ of $T$, giving this a total complexity of $O(nk)$.

I used an easier to implement RMQ giving a total complexity of $O(nk + (n+m)\log(n+m))$, or $O(nk + n\log n)$ if $m = O(n)$, but it can be done in $O(nk)$ too as described above. There may be other direct methods for this problem, but this is a powerful and generic approach that can be applied to a lot of similar problems.


Contrasting Peterson’s and Dekker’s algorithms I am trying to understand the algorithms by Peterson and Dekker which are very similar and display a lot of symmetries.

I tried to formulate the algorithms in informal language like follows:

Peterson's: "I want to enter."                 flag[0]=true;
            "You can enter next."              turn=1;
            "If you want to enter and          while(flag[1]==true&&turn==1){
            it's your turn I'll wait."         }
            Else: Enter CS!                    // CS
            "I don't want to enter any more."  flag[0]=false;

Dekker's:   "I want to enter."                 flag[0]=true;
            "If you want to enter              while(flag[1]==true){
             and if it's your turn               if(turn!=0){
             I don't want to enter any more."      flag[0]=false;
            "If it's your turn                     while(turn!=0){
             I'll wait."                           }
            "I want to enter."                     flag[0]=true;
                                                 }
                                               }
            Enter CS!                          // CS
            "You can enter next."              turn=1;
            "I don't want to enter any more."  flag[0]=false;

The difference seems to be the point where "You can enter next." occurs and the fact that "if it's your turn I don't want to enter any more." occurs in Dekker's.

In Peterson's algorithm, the two processes seem to be dominant. A process seems to force his way in into the critical section unless it's the other one's turn.

Conversely, in Dekker's algorithm, the two processes seem to be submissive and polite. If both processes want to enter the critical section, and it's the other one's turn, the process decides to no longer want to enter. (Is this needed for starvation-freedom? Why?)

How exactly do these algorithms differ? I imagine that when both processes try to enter the critical section, in Peterson's, the process says "I enter", while in Dekker's the process says "You may enter". Can someone clear up the way the processes behave in each algorithm? Is my way of putting it in informal terms correct?

Your informal descriptions of the algorithms is wonderful.

I think in both cases the author was trying to come up with the simplest solution they could think of that guaranteed both mutual exclusion and deadlock freedom.  Neither algorithm is starvation free or fair.[ed: as pointed out in the comments, both algorithms are starvation free, and Peterson's algorithm is also fair].  Dekker's solution was the first mutual exclusion algorithm using just load and store instructions.  It was introduced in Dijkstra, Edsger W.; "Cooperating sequential processes", in F. Genuys, ed., Programming Languages: NATO Advanced Study Institute, pp. 43-112, Academic Press, 1968.  If you read through the paper you see Dijkstra work through a number of attempts, recognizing the problem with each, and then adding a little bit more for the next version.  Part of the inefficiency of his algorithm comes from the fact that he starts with a turn-taking algorithm and then tries to modify it to allow the processes to progress in any order.  (Not just 0,1,0,1,...)

Peterson's algorithm was published in 1981, after more than a decade of experience and hindsight about Dekker's algorithm.  Peterson wanted a much simpler algorithm than Dekker so that the proof of correctness is much easier. You can see that he was feeling some frustration with the community from the title of his paper.  Peterson, G.L.; "Myths about the mutual exclusion problem," Inf. Proc. Lett., 12(3): 115-116, 1981. Very quick read and very well written. (And the snide remarks about formal methods are priceless.)  Peterson's paper also discusses the process by which he built his solution from simpler attempts.  (Since his solution is simpler, it required fewer intermediate steps.)  Note that the main difference (what you call "dominance" rather than "submissiveness") is that because Peterson started out fresh (not from the turn-taking algorithm Dijkstra started with) his wait loop is simpler and more efficient.  He realizes that he can just get away with simple looped testing while Dijkstra had to backoff and retry each time.

I feel I must also mention Lamport's classic Bakery algorithm paper: Lamport, Leslie; "A New Solution of Dijkstra's Concurrent Programming Problem", Comm ACM 17(8):453-455, 1974.  The Bakery algorithm is arguably simpler than Dekker's algorithm (and certainly simpler in the case of more than 2 processors), and is specifically designed to be fault tolerant.  I specifically mention it for two reasons.  First, because it gives a little bit of history about the definition of the mutual exclusion problem and attempts to solve it up to 1974.  Second because the Bakery algorithm demonstrates that no hardware atomicity is required to solve the mutual exclusion problem.  Reads that overlap writes to the same location can return any value and the algorithm still works.

Finally, a particular favorite of mine is Lamport, Leslie; "A Fast Mutual Exclusion Algorithm," ACM Trans. Comp. Sys., 5(1):1-11, 1987.  In this paper Lamport was trying to optimize a solution to the mutual exclusion problem in the (common) case that there is little contention for the critical section.  Again, it guarantees mutual exclusion and deadlock freedom, but not fairness.  It is (I believe) the first mutual exclusion algorithm using only normal reads and writes that can synchronize N processors in O(1) time when there is no contention.  (When there is contention, it falls back on an O(N) test.)  He gives an informal demonstration that the best you can do in the contention free case is seven memory accesses.  (Dekker and Peterson both do it with 4, but they can only handle 2 processors, when you extend their algorithms to N they have to add an extra O(N) accesses.)

In all: I'd say Dekker's algorithm itself is interesting mainly from a historical perspective.  Dijkstra's paper explained the importance of the mutual exclusion problem, and demonstrated that it could be solved.  But with many years of hindsight simpler (and more efficient) solutions than Dekker's have been found.