# Question
Title: Probability distribution of runs given k bits set in an n-bit circular buffer
Imagine you have a circular buffer holding `n` bits. You (uniformly) randomly set `k` of those `n` bits. (This is without replacement, so you are left with a buffer of `n` bits of which `k`bits are set.)

Now you randomly select a location in the buffer. What is the probability distribution of the run of set bits starting at that location? And what is the mean length of said run?

It's trivial that `P(k,n,0) = 1 - k/n` (that is, the first bit will be set with a probability of `k/n`, so there's a `1 - k/n` chance that it will be unset.).

I think this has something to do with the hyper-geometric distribution, but I am not sure.

# Answer
Note first that there is no need to randomly select a location in the buffer – we can fix one as we please. From that location, the probability that a run will be at least $t$ long is the probability that the $k$-set includes the first $t$ locations, which is $$ \Pr\[R \geq t\] = \frac{\binom{n-t}{k-t}}{\binom{n}{k}}. $$ Similarly, the probability that a run will be exactly $t$ long is the probability that the $k$-set includes the first $t$ locations but not the one after it, which is $$ \Pr\[R = t\] = \frac{\binom{n-t-1}{k-t}}{\binom{n}{k}}. $$

---

The expectation of $R$ is $$ \mathbb{E}\[R\] = \sum\_{t \geq 1} \Pr\[R \geq t\] = \frac{\sum\_{t \geq 1} \binom{n-t}{n-k}}{\binom{n}{k}} = \frac{\binom{n}{n-k+1}}{\binom{n}{k}} = \frac{k}{n-k+1}, $$ using the formula $\sum\_{x=r}^m \binom{x}{r} = \binom{m+1}{r+1}$.
> 2 votes

---
Tags: combinatorics
---


# Question
Title: Can you do operations on the halt state of a turing machine?
As the title says, can operations be performed by a turing machine after it has transitioned to the halt state like shown in the following image.

# Answer
> 2 votes
It may depend on the exact definition you're using for Turing machines, but most reasonable definitions will probably halt at the halt state. Your transition function can include transitions at the halt state, they just won't be executed. It's also possible that your particular definition prohibits such transitions.

In summary, your definition will tell you everything you need to know. Take a look!

---
Tags: turing-machines
---


# Question
Title: I can find in a graph a path between two input nodes to be exactly of length k
I have in input an undirected graph and two nodes. It is possible to find a path of lenght k, where k is a constant, in polynomial deterministic times? Or this problem belongs to NPC?

Thanks

# Answer
> -1 votes
If you could solve this in polynomial time, you could solve the longest path problem in polynomial time by checking, for each pair of nodes $u,v \in V(G)$ and each length $\ell \in \\{1, \dots, |V(G)|-1\\}$, whether a $uv$-path of length $\ell$ exists. Hence no poly-time algorithm for this problem exists, unless P=NP.

---
Tags: complexity-theory, graphs, np-complete
---


# Question
Title: Is there Any difference between dynamic programming vs branch-bound vs delayed column generation
I was reading about cutting stock problem https://en.wikipedia.org/wiki/Cutting\_stock\_problem , this is best solved using dynamic programming but wiki page mentions 2 other techniques names Branch-Bound and delayed column generation... I read them but it all look same ...every case we break problem into sub problem

Can anyone shed some more light with some example.?

# Answer
* Dynamic programming is a strategy which avoids explicit enumeration of all possible solutions in the cutting stock problem.
* Branch and bound is a search based technique also based on pruning. However in branch and bound you might in the worst case need to search over all possible solutions.
* Column generation is a variant of branch and bound where instead of creating all variables at once they are generated sequentially based on which ones are more "attractive".

In terms of implementation you can implement dynamic programming in any general purpose programming language like C or Java while for column generation you will need to use specialised linear programming solvers as also for Linear programming based branch and bound.
> -1 votes

---
Tags: algorithms, dynamic-programming, algorithm-design, branch-and-bound
---


# Question
Title: Find a CFG for palindromes with at most three c's
I'm trying to figure this one out, as I've found the CFG for the palindrome language. I can't work on a solution that also covers #c(w) \<= 3.

Find a CFG for the language {w∈{a,b,c} | Reverse(w)=w, #c(w)\<=3}?

Would appreciate your help

# Answer
Call $$ P=\\{w\in\\{a,b,c\\}^\*\mid w=w^R\\} $$ the palindrome language and $$ Q=\\{w\in\\{a,b,c\\}^\*\mid |w|\_c\le 3\\} $$ the language of strings having at most 3 $c$'s. Then your language is $L=P\cap Q$ and so is a CFL, since we know the intersection of a CFL (which $P$ is) and a regular language (which $Q$ is) is a CFL. With that out of the way, let's get a CFG for $L$.

---

You know that a grammar for $P$ can be given by the productions $$ S\rightarrow aSa\mid bSb\mid cSc\mid a\mid b\mid c\mid\epsilon $$ Now let's modify this grammar so that it generates palindromes with at most 3 $c$'s. The production $S\rightarrow cSc$ will add two $c$'s to the string being generated, so we want to limit ourself to subsequent productions that generate at most one more $c$. We can do that by changing $S\rightarrow cSc$ to $S\rightarrow cTc$ and forcing $T$ to generate palindromes with at most one $c$. This is simple enough: we can add these productions, $$ T\rightarrow aTa\mid bTb\mid a\mid b\mid c\mid \epsilon $$ So finally we have the grammar $$\begin{eqnarray} S&\rightarrow& aSa\mid bSb\mid cTc\mid a\mid b\mid c\mid\epsilon \\ T&\rightarrow& aTa\mid bTb\mid a\mid b\mid c\mid \epsilon \end{eqnarray}$$
> 4 votes

---
Tags: formal-languages, context-free, formal-grammars
---


# Question
Title: Why is the zero-th power of the empty set {ε}?
It has been asked before why $\emptyset^\star=\\{\epsilon\\}$. The answer boils down to $\emptyset^\star$ being defined as $$ L^\star = \bigcup\_{i=0}^\infty L^i, $$ where a word in $L^i$ is the concatenation of $i$ words from $L$. So, for the empty language this leaves empty sets for all $i\>0$, "but $L^0 = \\{ \epsilon \\}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$." *(quoted from the answer.)*

And that's what I'm curious about: is there a good reason to say that the concatenation of zero words is $\epsilon$ even for the empty set? Can you compare it to $0^0=1$ in arithmetics (where it's just more or less arbitrary) or is there a strong logical reason for this to be true?

# Answer
Strings with concatenation and the empty word form a monoid.

In monoids, the empty concatenation/sum/product yields the neutral element, i.e. $\varepsilon$/0/1.

An empty concatenation does not need any words to start with, so $\emptyset^0 = \\{\varepsilon\\}$.

Intuitively, if you specialize

> $L^n$ is the set of all words obtained by $n$-fold concatenation of words in $L$

to

> $L^0$ is the set of all words obtained by zero concatenations (of words in $L$)

you can just stop reading after "concatenations" and the contents of $L$ do not matter; we don't even need it to be non-empty.
> 6 votes

---
Tags: formal-languages, mathematical-foundations
---


# Question
Title: () = ( − 2) + 4, giving asymptotic bounds
How do I go about solving this? When I try to google examples I only see problems with "+1" or "+n" constants and never anything above that.

If possible could anyone also describe the suggest method to solve these as well?

() = 3( − 1) + 3

() = 2 (/8) + 4^2

Update: I couldn't find any examples or helpful resources for solving recurrences with "weird" constants so I figured it would be unique enough to ask here.

# Answer
Take the first example. Start calculating T (100) = T (98) + 4 = T (96) + 4 + 4 = T (94) + 12 = T (92) + 16 ...

Seriously, that's the first thing you do. You have a problem, you try what happens. At this point it should be absolutely obvious to you what happens, right? I hope I don't have to write down the solution?

The next one: T (100) = 3 T (99) + 3 = 9 T (98) + 9 + 3 = 9 * T (98) + 12 = 27 * T (97) + 39 = 81 * T (96) + 120 ... Slightly more complicated, but you see that one of the numbers is a power of 3, and the other one is slightly less obvious $(3^k - 3) / 2$. Figure it out from there.

The next one: Well, I'll start with 512. T (512) = $2 T (64) + 4 * 512^2$ $2 * (2 T (8) + 4 * 64^2) + 1024^2$ = $4 T (8) + 8 * 64^2 + 4 * 512^2$ = $4 * (2 T (1) + 4 * 8^2) + 8 * 64^2 + 4 * 512^2$ = $8 T (1) + 8 * 8^2 + 8 * 64^2 + 4 * 512^2$ - it should be clear what the dominating factor is in this equation.

This is all mathematically trivial. All you had to do to solve these problems is to not look at them and be stunned by the strange formulas but having a go and starting to calculate and see what happens.

PS. The answer was intended to demonstrate that seemingly hard problems can often be attacked quite easily, that overcoming your fear of the unknown and jumping in and seeing what happens is often enough. That is much, much more important than solving one particular problem. You may call this a "waste of time", but I Don't Think So.

The quoted "reference answer" may answer the question, but doesn't inspire anyone to try finding the answer themselves.
> 1 votes

# Answer
Its all about manipulating the equation into a form you understand.

If we say $T(n) = T(n-2) + 4$, all we mean is that $T(n)$ is four larger than it was when n is two less, regardless of n. For a given n, we are therefore just adding on 4s in a linear way for every other n. This is the same as going up by 2 for each term.

$T(n) = 2n + c$ fulfills this. Asymptotically, this is $O(n)$.

The same idea applies to your other equations, that we just need to understand what your recursive function is stating to decide a form that we can use.

For $T(n) = 3T(n-1) + 3$ we separate the two sides and solve for each.

$3T(n-1$) triples every time, so it follows $T^3$, and $+ 3$ adds three every time, so we have $3n$.

Therefore, we decide $T(n) = c(T^3) + 3n + d$. Which asymptotically is just O(n^3)

We can leave the third for practice, but the ideas still apply (note that $2T(n/8)$ doubles every 8 values of n).
> 0 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Multi-point evaluations of a polynomial mod p
Given a polynomial of degree $n$ modulo a prime number $p$, I want to evaluate that polynomial at multiple values of the variable $x$, what is the best way to do this?
I tried using Berlekamp's algorithm for factorization but it takes $O(n^3)$ just to factorize and then $O(n)$ per point evaluation. Is there any other way to bring the complexity down considerably like to $n\log(q)$ where $q$ is the number of points I want to evaluate the polynomial at? Or possibly polynomial time? All the coefficients and the values of $x$ that the polynomial is to be evaluated at lie between the $0$ and $prime - 1$, the prime is of order $10^6$.

# Answer
> 14 votes
No, $O(n \lg q)$ running time is not achievable. It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$.

However, you can find algorithms that are more efficient than the naive solution. The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ time, by using Horner's rule $q$ times. It turns out there are faster algorithms to do this, namely, in $O(\max(n,q) \log^2 \max(n,q))$ time. For simplicity of exposition, let me assume $q=n$, so the goal is to evaluate the polynomial $f(x)$ at points $x\_1,\dots,x\_n$.

We're going to use divide-and-conquer. Define

$$\begin{align\*} f\_0(x) &= f(x) \bmod (x-x\_1)(x-x\_2)\cdots(x-x\_{n/2})\\ f\_1(x) &= f(x) \bmod (x-x\_{n/2+1})\cdots(x-x\_n) \end{align\*}$$

Now we have

$$f(x\_i) = \begin{cases} f\_0(x\_i) &\text{if }i\le n/2\\ f\_1(x\_i) &\text{otherwise.}\end{cases}$$

Thus, it suffices to evaluate $f\_0(x)$ at the points $x\_1,\dots,x\_{n/2}$ and evaluate $f\_1(x)$ at the points $x\_{n/2+1},\dots,x\_n$. We can do this by a recursive invocation of the same procedure. Since both $f\_0(x)$ and $f\_1(x)$ have degree at most $n/2$, we're invoking the procedure recursively on two subproblems of size $n/2$.

This requires us compute $f\_0(x)$ and $f\_1(x)$ from $f(x)$. This can be done in $O(n \log n)$ time, using FFT-based polynomial division, which works similar to FFT-based polynomial multiplication (see here, here, and these slides).

The running time of this divide-and-conquer algorithm is

$$T(n) = 2 T(n/2) + O(n \log n),$$

which has the solution $T(n) = O(n \log^2 n)$. Thus, you can evaluate a polynomial of degree $n$ at $n$ arbitrary points in $O(n \log^2 n)$ time.

Since you are working modulo $p$, you want to use a Discrete Fourier Transform designed for mod $p$ arithmetic.

Thanks to Niklas B. for pointing me to http://www.dis.uniroma1.it/~sankowski/lecture4.pdf.

---
Tags: algorithms, numerical-algorithms, polynomials
---


# Question
Title: Is converting an ambiguous grammar to an unambiguous grammar computable?
Is the problem of converting ambiguous grammar into unambiguous grammar computable? (Consider Domain as all context free languages).

# Answer
I assume that question is about derivation, otherwise the outcome does not change, but please read Yuval's comment for further details.

No it is not computable in the domain of your choice. There are inherently ambigous grammars, which are subset of context-free grammars. For the subset without inherently ambigous ones it is computable.

I like to point to thesis about ambiguous grammars, which is consistent with what I wrote, contains the same proof as TCS topic.

Since the problem of finding out whether grammar is inherently ambiguous is undecidable then you cannot build halting Turing Machine for such task. And yes, if you could built one it would be decidable.
> 0 votes

---
Tags: computability, context-free, formal-grammars, undecidability
---


# Question
Title: Find member of CFL that is Levenshtein-closest to non-member string
Is there an (efficient?) algorithm which given a context-free language $L$ (given as a grammar) and a string $x$ with $x \not \in L$ computes a $y$ with $y \in L$ and $\forall y': y' \in L \implies d(x, y) \le d(x, y')$, where $d$ is the Levenshtein distance? (Secondarily, can one enumerate all such $y$?)

The motivation is to give more useful parse error messages: if you give me an almost-valid C program, I would like to tell you "if you delete these parentheses and insert a semicolon here, it'll parse".

A family of related questions:

* What happens when you vary the distance function? (Can you think of other candidates? Do non-metric distance functions make sense? Do they change the answer?)
* Does the answer change if you restrict $y$ to e.g.
    + $x$ is a prefix of $y$ (i.e. you can do append-only error-correction)
    + $y$ is a prefix of $x$ (i.e. you can do pop-last-only error-correction)
    + all the characters of $x$ occur in $y$ and in the same relative order, but maybe not adjacently (i.e. you can error-correct by inserting anywhere)
    + \[...\] $y$ occur in $x$ \[...\] by deleting anywhere.
* Does the answer change if you change the optimization criterion? E.g. "find a $y$ in $L$ which maximizes the length of common\_prefix(x, y)", or something else?
* Does the answer change for other language classes, e.g. regular?
* Does this change if the language is given as $LALR(k)$, $LL(k)$, deterministic or other sub-CF grammar?

# Answer
> 4 votes
Yes. This can be done, using Levenshtein automata.

Let $S\_k = \\{y \in \\{0,1\\}^\* : d(x,y) \le k)\\}$. Then the set $S\_k$ is regular, and one can construct a finite-state automaton for it, called a Levenshtein automaton. Now the intersection of a CFL and a regular language is another CFL. Also, given a CFL, you can efficiently determine whether it is non-empty or not, and if not, you can efficiently find an example of an element of it.

So, we obtain the following simple algorithm:

* For $k:= 1,2,3,\dots$, do:
    + If $L \cap S\_k$ is non-empty, find $y \in L \cap S\_k$ and output it.

This can be sped up by using binary search to find the smallest $k$ such that $L \cap S\_k$ is non-empty.

The same approach can handle your proposed restrictions as well, as those simply amount to intersecting with another regular language. It also works if $L$ is regular, as any regular language is necessarily context-free.

# Answer
> 1 votes
If we limited ourselves to those $y$ with $|y| \le |x|$ (or any finite set) and a computable strict partial order, we can construct the (finite) DAG of the order on our $y$s and find the set of all nodes of in-degree 0, those being the optimal ones. Given this set, we can answer is-empty, enumerate-all and arbitrary-member queries.

This addresses the question where $y$ is a prefix of $x$ and where $y$ is a delete-anywhere substring of $x$, for any decidable language class (e.g. context-free and regular).

The downside is that for delete-anywhere, we iterate a $y$-set of size $2^{|x|}-1$ (we can omit $x$ itself since it's not a member). For prefix-only $y$s it's only $|x|$ strings which is reasonable.

# Answer
> 1 votes
The language $E = \\{x\\} \cdot \Sigma^\*$ is regular, as is $I = \Sigma^\* \\{x\_1\\} \Sigma^\* \\{x\_2\\} \Sigma^\* \cdots \Sigma^\* \\{x\_n\\} \Sigma^\*$. For any language class of $L$ for which we can compute the shortest member of $L \cap R$ for regular $R$, we can answer the insert-at-end and insert-anywhere optimization problem (note that shorter implies smaller edit distance when we have only done inserts).

This is the case for regular and context-free languages:

If we have a DFA for $L$ we can use the product construction to get the language of valid candidates $C \in \\{L \cap I, L \cap E\\}$ as appropriate. Given this we can test $C$ for emptiness and (if not) find a shortest path from the starting state to an accept state, giving us the desired $y$.

The intersection of a context-free and a regular language is context free. We can compute the shortest string in a context-free language, see https://math.stackexchange.com/questions/606518/the-shortest-word-in-context-free-language. (My slight modification: for $k$ in 1..\*: If $A → w$ with $|w| \le k$ replace $A$ with $w$ in all right-hand-sides. Once $S$ produces a string, that's your result.)

By computing $C\_i = L \cap (\\{x\_1 \cdots x\_i\\} \cdot \Sigma^\*)$ for $i = 0, \ldots, |x| - 1$ and testing for non-emptiness, we can find the $y$ in $L$ which shares the longest prefix with $x$. Among them, we can also find the shortest by the above method.

---
Tags: formal-languages, context-free, string-metrics, edit-distance
---


# Question
Title: Is this argument wrong "since DOM is special kind of RDOM, then RDOM is NP-hard"?
The domination problem $DOM$ is defined as $$ DOM = \\{ \langle G,k \rangle\ | \ G \text{ has a domination of size } k, K \in \mathbb{N} \\}, $$ and the rainbow domination problem $RDOM$ is defined as $$ RDOM = \\{ \langle G,r,k \rangle \ | \ G \text{ has a r-dominating set of size } k; r,k \in \mathbb{N} \\}. $$ A $r$-rainbow domination for a graph $G=(V,E)$ is a mapping of the form $f:V \rightarrow 2^{\\{ 1,\ldots, r\\}}$ such that $f(v) = \emptyset$ implies $\cup\_{u \in N(v)} f(u) = \\{ 1,\ldots , r\\}$ where $N(v) = \\{ u \ | \ \\{u,v\\} \in E \\}$. The size of $r$-domination is defined as $\sum\_{v \in V} |f(v)|$.

To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM \leq\_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance $\langle G',r,k' \rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only if $\langle G',r,K' \rangle \in RDOM$.

My friend states that we know that a domination is a $1$-rainbow domination in the same graph, i.e. domination is a special kind of rainbow-domination, and since domination is $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to convince him that this is wrong? or this argument is correct?

# Answer
> 2 votes
There are two statements here that rule the argument. The first statement:

> **Statement 1.** To show that $RDOM$ is $\mathbf{NP}$-hard, one must show that $DOM \leq\_P RDOM$, i.e. given an instance $\langle G,k \rangle$, construct an instance $\langle G',r,k'\rangle$ in polynomial time such that $\langle G,k \rangle \in DOM$ if and only if $\langle G',r,K'\rangle \in RDOM$.

is a general framework for showing that *RDOM* is NP-hard. However, in this statement, you have not shown how to prove that this reduction works. You just said how to prove that this problem (or any problem) is NP-hard. In order to prove it, you need a proper reduction from all instances of *DOM* to instances of *RDOM*. The second argument however,

> **Statement 2.** By the way, my friend states that we know that a domination is a $1$-rainbow domination in the same graph, i.e. domination is a special kind of rainbow-domination, and since domination is $\mathbf{NP}$-hard, then $RDOM$ is also $\mathbf{NP}$-hard. How to convince him that this is wrong? or Is this argument correct?

looks like a proper reduction. If "every domination is a $1$-rainbow domination in the same graph", then this proof is completely right. This is a proper reduction from every instance of *DOM* problem to instances of *RDOM* or *1DOM* problem. However, if "every domination is NOT a $1$-rainbow domination in the same graph", then this proof is completely wrong.

My understanding is that a *domination*, can be any of *1-rainbow domination*, ...,or *|V|-rainbow domination*. In this case, it is implied that by having a polynomial algorithm for RDOM problem, you can iterate $|V|$ times thorough $r$-dominations and determine if the graph is dominating. Thus, if you have a polynomial algorithm for *RDOM* problem, you can solve the *DOM* problem polynomially.

---
Tags: complexity-theory, np-complete, reductions, proof-techniques, np-hard
---


# Question
Title: Solving inhomogeneous recursion using quadratic particular solution
I am interested in solving recursions and while I was trying to solve this one: $a\_n=a\_{n-1}+4n-3$

I ran onto a problem, I don't see how to find an explicit solution using standard inhomogeneous method(finding homogeneous and particular solution). Specifically I have a problem with finding particular solution. Problem for me is how to find expression to represent $f(n)=4n-3$. I do know how to solve for $f(n)=n$ with representing $f(n)$ as polynomial $an+b$ and substituting in the recursion. Is there a way to solve this type of recursions when $f(n)$ isn't depending just on $n$. Can we solve for even more complicated expressions such as $f(n)=5n^2+2n+4$ or any polynomial of degree $n$

# Answer
Given:

$a(n) = a(n-1) + 5n^2 + 2n + 4$

We hypothesise that because the difference is quadratic, $a(n)$ is cubic. In particular:

$a(n) = a\_3 n^3 + a\_2 n^2 + a\_1 n + a\_0$

So:

$a\_3 n^3 + a\_2 n^2 + a\_1 n + a\_0 = a\_3 (n-1)^3 + a\_2 (n-1)^2 + a\_1 (n-1) + a\_0 + 5n^2 + 2n + 4$

$\Rightarrow 3 a\_3 n^2 + (-3 a\_3 + 2 a\_2) n + (a\_3 - a\_2 + a\_1) = 5n^2 + 2n + 4$

This must be true for all $n$. Therefore:

$3 a\_3 = 5$

$-3 a\_3 + 2 a\_2 = 2$

$a\_3 - a\_2 + a\_1 = 4$

Note that $a\_0$ doesn't appear in these equations, so this is effectively a linear system, three equations in three unknowns. The unique solution is:

$a\_3 = \frac{5}{3}$

$a\_2 = \frac{7}{2}$

$a\_1 = \frac{35}{6}$

And so:

$a(n) = \frac{5}{3} n^3 + \frac{7}{2} n^2 + \frac{35}{6} n + a\_0$

is a solution to the recurrence equation for any $a\_0$.
> 1 votes

---
Tags: recurrence-relation, mathematical-foundations
---


# Question
Title: Is bounded waiting ensured in given version of Dekker's solution for critical section problem?
William Stallings discuss various step by step process in developing Dekker's algorithm in his Operating Systems book. In process, he reaches to following version of algorithm (which is incomplete as it results in livelock):

```
1
2    /*    PROCESS 0    */
3    .
4    .
5    flag[0] = true;
6    while (flag[1])
7    {
8       flag[0] = false;
9       /* delay */ ;
10       flag[0] = true;
11    }
12    /* critical section*/;
13    flag[0] = false;.
14
15    .
16
17    /*    PROCESS 1   */
18    .
19    .
20    flag[1] = true;
21    while (flag[0])
22    {
23       flag[1] = false;
24       /* do */ ;
25       flag[1] = true;
26    }
27    /* critical section*/;
28    flag[1] = false;.
29
30    .
31
32

```

I want to know whether above algorithm satisfies the "bounded waiting" requirement of critical section solution.

My current opinion is that, if process 0 fails on lines 6,7,8,11,12,13,14,15, that is all lines where `flag[0]` is already set to true, then process 1 will be blocked and hence will result in unbounded waiting. Am I correct?

Also is there easy way to find whether given/proposed algorithm for critical section problem solution satisfies "bounded waiting" requirement?

# Answer
> 3 votes
A reasonable definition of *bounded waiting* is:

> After a process made a request to enter its critical section and before it is granted the permission to enter, there exists a bound on the number of turns that other processes are allowed to enter. \[1\]

In your case each process makes its *request* to enter by setting its flag (line 5 for Process 0, line 20 for Process 1. The *granting of permission* is the test of the other process' flag (`flag[1]` false on line 6 grants permission to Process 0, `flag[0]` false on line 21 grants permission to Process 1).

So the only way to test the bounded waiting requirement here is to consider the case that Process 0 has just tested `flag[1]` on line 6, and found it `true`, and ask, "how many times can Process 1 leave and reenter the critical section while Process 0 is stuck in the loop?" (Hint: consider the case where Process 0 has really bad luck, and Process 1 is able to leave and reenter the critical section during Process 0's delay on line 9).

\[1\] source: http://www.csl.mtu.edu/cs3331.ck/common/05-Sync-Basics.pdf

# Answer
> 0 votes
Dekker's algorithm operates in strict alternation format i.e. 2 processes will alternatively gain Critical section.

As the definition given above by Wandering Logic, there is only one process for which another process has to wait.For example if process P1 wants to enter critical section then at most it has to wait for only one process(i.e. P0) for gaining control of CS.

This shows that Dekker's algorithm ensures bounded waiting property.

---
Tags: algorithms, operating-systems, concurrency, correctness-proof, process-scheduling
---


# Question
Title: Which is the most efficient out of Bubble Sort, Selection Sort, Insertion Sort for a identical set of elements?
Which of the sorting algorithm is (classical implementation with no enhancements) the fastest for a data set with all identical elements? And why?

How would one justify the answer to the above question logically? Logically as in without implementing the algorithms and finding the average time consumed for few sample data sets.

# Answer
All elements being the same is equivalent to data being sorted. The class of algorithms you are looking for is adaptive sort, which benefits from presortedness of the input data - this is the justification - since data is already sorted we have to find algorithm that uses this fact. The classic example is the insertion sort, but also Timsort (a variant of natural merge sort) and other exist. All adaptive algorithms should show the best case performance as $\mathcal{O}(N)$, which in case of insertion sort is exactly $N - 1$ comparisons, where $N$ is the length of input data.
There is no need to implement or run those algorithms, it is suficcient to show that part responsible for swapping elements is never executed, show that appropriate conditions are always true (or false depending on code) so analysis is easier.

From the possible algorithms you have provided the best cases are: Bubble sort - $\mathcal{O}(N)$, Selection Sort - $\mathcal{O}(N^2)$ and Insertion Sort - $\mathcal{O}(N)$.
> 0 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: Is it possible to create a chatbot that doesn't fall into an infinite loop under some restrictions?
Consider a chatbot that runs on a turing machine. It has some restrictions:

1. It must talk to itself 1 sentence at a time.
2. It is forced to use English words to reply. (so only around say 80 k different words to pick from)
3. A sentence cannot be longer than N words (say N=100)

Is it possible to create such a bot (computer program) such that it will not repeat itself over and over, i.e. fall into an infinite loop?

I think that yes, it's possible. For example the sequence: "Hello, how are you? \> Good, and you? \> Not so good, and you? \> Good and you? \> Good and you? \> Good and you? \> Not so good, and you? \>..."

I could write the above as 10110111011110111110... where 1 represents "Good, and you?" and 0 represents "Not so good, and you?".

But a friend is telling me that the example does not work because "it's not a cycle, so it's not possible on a finite state machine".

Edit: I'm asked whether the TM can maintain state during inputs. My answer is "yes if a common household computer can, no otherwise."

**Edit for the bounty:** I'd like the answer to be clear on whether a common household computer can run such a program, i.e. a program that never cycles under the above restrictions.

Thus far, **on one hand Anrej Bauer's answer explain that it's impossible.** On the other hand, in the comments I am told by D.W. that "*Or, to put it another way: yes, a common household computer can retain state if you invoke it in a way that allows retaining state; it can't retain state if you invoke it in a way that doesn't allow it to retain state.*" and by David Richerby that "*Is the Turing machine allowed to maintain state between inputs? If so, you can implement your 10110111011110... sequence exactly as you describe.*". Which would make the answer as "**yes, it is possible even when the TM is a common household computer**". This is why I am reluctant to accept the answer and bounty so far.

**EDIT 2:** To make the question well definied, I must pick whether I want the TM to retain state between inputs. Since it is possible to do so on a household computer with say Python as a programming language, I pick that yes, the TM can retain state between inputs.

# Answer
> 4 votes
If the computer can retain state between inputs (e.g., you're using an interactive Turing machine), then yes, you can avoid an infinite loop.

For instance, the machine can just have a counter that counts 1,2,3,4,5,...; it can then map the counter to a sentence. When the counter is $i$, it can look up the $i$th bit of the binary expansion of pi; if this bit is even, it outputs "Not so good, and you?" and if it is odd, it outputs "Good, and you?". Since the bits of pi never repeat, this will never repeat either. There are other ways to do it as well; this is just one example.

---

To respond to the original version of the question: If invoke the Turing machine separately on each input string, then it will have no way to retain state across sentences. In that case, no, It's not possible. By the pigeonhole principle, there will exist a loop. The set of possible sentences is finite, so this will eventually enter a loop.

If you take any function $f:S \to S$ where $S$ is a finite set, and you pick a single starting point $x \in S$ and then compute the sequence $x,f(x),f(f(x)),\dots$, eventually some value must appear twice. In particular, once you've looked at $n+1$ different values, each of which is selected from a set of size $n$, by the pigeonhole principle, there must be some value that appeared at least twice. In other words, $f^i(x)=f^{i+r}(x)$ for some $i,r$. This means that $f$ has entered a cycle: $f^{j+r}(x)=f^j(x)$ for all $j\ge i$.

Here $S$ represents the set of all sentences (there are finitely many of them), and $f$ represents the function computed by your chatbox (which accepts a single sentence on its input, and outputs a single sentence, and is deterministic).

Of course, with an appropriately constructed algorithm, it may take longer than the lifetime of the universe to enter a loop. Nonetheless, mathematically, it will eventually loop.

Your specific example doesn't work: it can't be implemented by a deterministic function. If on input "Good, and you?" it outputs "Not so good, and you?", then that's what it will always output on that input. Thus, you can't have a Turing machine that on input "Good, and you?" will sometimes output "Not so good, and you?" and sometimes output "Good, and you?". Code running on a Turing machine is deterministic and memoryless.

# Answer
> 4 votes
For the purposes of this problem it is irrelevant that we are talking about a chatbot. The question really boils down to: **Can a machine produce an infinite stream of strings which never repeats?**

The answer depends on what kind of machine we have.

If the machine has **unlimited** amount of memory then the answer is **yes**. Such a machine can simply produce the sequence of outputs

```
0
00
000
0000
00000
...

```

each time outputting one more zero (if you are not happy with strings of `0`'s you can use something else, for instance it can just keep counting numbers in binary). For this purpose it needs a counter that tells it how far it got. Because it has an unlimited amount of memory, it will never run out of space to store the counter.

If the machine has a **limited** amount of memory then it **must eventually repeat whatever it is doing**. This is so because the machine can be in a finite number of states, and there are a finite number of possible configurations of memory, so the combined number of state/memory configurations is still finte. Each transition takes the machine from one state/memory configuration to another. As there are only finitely many configurations, it must eventually revisit one of them. At that point it will just keep repeating things in a loop (because its next state/memory configuration is completely determined by the current state/memory configuration).

This leaves us with the practical question on what is doable with real-world computers. Clearly, the computer in your lap has a limited amount of memory, so it must eventually repeat itself (in fact it does every time you reset the machine). But the number of possible configurations is huge. For instance, if we use 1GB of memory for a counter then the machine will be able to count up to $2^{2^{30}}$ which is an unimaginably large number. If the machine could increase the counter $2^{100}$ times per second (much much faster than current computers), it would still take many many many times more for it to enter a loop than it will take the universe to experience heat death or any of the grim predictions about its future.

Thus, as far as mathematical modeling of computers is concerned, it is often a good idea to approximate $2^{2^{30}}$ with $\infty$.

**Supplemental:** Apparently I missed the fact that the chatbot is passing itself some input. I find the description of the problem unclear, so I am going to make a guess that:

1. In each round of the conversation the chatbot receieves and input and produces an output.
2. The output of the $n$-th round is the input of the $n+1$-st round.
3. As noted in the question, there is a bound on the input/output messages.

If this is what the problem is about, then nothing has changed because the messages are bounded in size and so there are only finitely many possible messages to communicate. To see this, consider all possible combinations of input, machine state and memory configuration – there are only finitely many of them. In each round the chatbot passes from one such combination to another. Eventually it has to repeat a configuration, and that is when it enters the loop.

If we allow messages of unlimited size then it is trivially the case that the chatbot could go on forever without repeating itself, even with finite amount of memory. It just has to copy the input to the output and add the charcter `0` to it, and this requires no memory at all.

---
Tags: turing-machines
---


# Question
Title: What is the need of re-sampling the image for HOG features?
I read Dalal and Triggs paper for HOG description and a blog Chris McCormick HOG regarding the same. The blog says that the image needs to be re-sampled at different scales to recognize different person.

My question is: Already we have a window which we place on the image having a size of 64\*128 and which slides over the image. Then why re-sampling instead of sliding the whole window over the image which can detect the persons instead. ?

Please rectify if I am wrong, thanks in advance !!

# Answer
> 1 votes
You are indeed sliding window over the image which has fixed size, but the picture may have different resolution or simply the person in the photo is in some distance from the camera (so the face size in the picture will be related to distance) but your classifier should work anyway, so checking at different sizes is one of the ways to detect people at different depth.

---
Tags: machine-learning, image-processing, computer-vision, classification
---


# Question
Title: Heterogenous and Asymmetric Computing's differences
The definition of the both architecture looks pretty same. They are parallel computing architecture with different type of cores.

What distinguish their definition, actually?

# Answer
Heterogenous computing as opossite to homogenous or symmetric means that processing units differ, which is exactly the same as asymmetric (which is just not symmetric).
But there are more usage differences - asymmetric computing (processing) is more about different CPUs which are used to perform assigned tasks, in embedded systems this is by design, in general purpose by executing in given context, commonly about "local" environment.
Heterogenous is used to talk about tasks computed on different processing units (CPU, GPU and dedicated hardware), also used to describe distributed systems where processing takes place on totally random devices connected.

To make it full - symmetric means exactly the same vector, while homogenous is less strict and requires the results to be the same among devices (the same floating point representation), but does not require exact devices.
> 0 votes

---
Tags: terminology, computer-architecture, parallel-computing
---


title: Designing a scheduling algorithm

text:
# Question
Title: Designing a scheduling algorithm
I have only intro CS under my belt, so I'm looking for some fast advice. I want to write a scheduling algorithm for the following scenario.

I have customers who have selected how many hours they want and what times they are available (choosing in 4 hour increments). I have 1 service person I then need to schedule to maximize the number of hours scheduled (so only 1 service person at a time). There is no ranking of preferences by customers, just a binary availability for each time slot and a number of hours. My thought was to start with the biggest job, schedule that, and then work downwards greedy-style. I also thought this must be a well-known problem. Can someone tell me the name of this 'problem' or what else I should be looking at? I can also restructure the inputs if that would help finesse this into an optimized algorithm that exists out there.

# Answer
> 3 votes
Since a customer must either be assigned all the requested hours or none at all, this problem is $NP$-complete. This can be seen by reduction from Exact Cover.

A polynomial algorithm is unlikely to exist. Starting with biggest job first might be a reasonable heuristic for many cases, but there are no performance guarantees.

---
Tags: algorithms, optimization, scheduling
---


# Question
Title: Count all numbers up to X that are divisible by at least two of their digits
I want to count how may numbers are there in range \[1,X\] which are divisible by at least two of their digits, different and \>1. I found a sequence on OEIS, but this will take lot of time to generate all such numbers as X can be $10^{18}$. How to do this efficiently?

# Answer
> 2 votes
Note: You are not asked to give a list of all numbers. You are asked how many there are. A simpler question: How many integers from 1 to $10^{18}-1$ are divisible by both 2 and 3? You can figure this out without giving a list of all those numbers. It's actually quite easy, so figure this out first. That's just to get you to understand the idea, and to get you warmed up. And this being computer science, expect to write some code :-)

Now slightly more difficult: How many numbers contain the digits 2 and 3, and are divisible by both 2 and 3? That's not trivial, but you should be able to figure it out. Then the same for 2 and 4, ... , 2 and 9, ..., 8 and 9. Then add up the numbers.

The problem is that you counted some numbers twice. If a number has digits 2, 3, 4 and is divisible by 2, 3, and 4, then you counted it under (2, 3), under (2, 4) and under (3, 4), that is you counted it 3 times instead of once. So subtract twice the count of these numbers. And then the same for (2, 3, 5), (2, 3, 6), ... up to (7, 8, 9).

Now numbers with digits 2, 3, 4, 5 and divisible by 2, 3, 4, 5: Any of these numbers, you counted under (2, 3), (2, 4), ..., (4, 5), a total of six times. You subtracted it twice under (2, 3, 4), (2, 3, 5), (2, 4, 5), and (3, 4, 5); total 8 times, so you counted it -2 times instead of +1 times. So add the count of these numbers three times. Same for the other combinations.

And you go on like that. It's a lot of work, but not too bad and should be doable in a few seconds CPU time.

# Answer
> 0 votes
Counting all such numbers less than X can actually be done quite easily in $O (\log x)$ steps with a rather large constant, which would let us find the count for large values like X = $10^{100}$ quite easily. We use the fact that we can determine which factors \< 10 a number x has if we know x (modulo 2520).

For each subset S of { 2, 3, 4, 5, 6, 7, 8, 9 } and for every r, 0 ≤ r \< 2520, and for various values Y and Z, we determine how many numbers 0 ≤ x \< Y and how many numbers 0 ≤ x \< Z where x = r (modulo 2520) have all the digits in the set S, and no others except 0 and 1. These numbers can be stored in two table of 256 x 2520 = 645,120 elements each.

We build such tables first for Y = 10 and for Z = X (modulo Y); that is quite easy because most table entries are zero, except the entries for ( {}, 0), ( {}, 1), ( {2}, 2), ... ( {9}, 9) have a count of 1 when Z = 10, and fewer entries when Z = X (modulo 10).

We then build tables with Y = $10^k$ and Z = X (modulo Y), up to and including the first k where $Y = 10^k \> X$ and therefore Z = X. We build the table for Y by adding a digit from 0 to 9 in front of each number in the table for Y/10 that we built just before; if the previous table had a count c for the set S and some r, then we add c in the new table to the entries (S, r), (S, (r + $10^{k-1}$ modulo 2520), (S + {2}, (r + $2 · 10^{k-1}$ modulo 2520), ..., (S + {9}, (r + $9 · 10^{k-1}$ modulo 2520). For the table for Z, we only process some digits like this, and one digit uses the previous table for Z = X modulo ($10^{k-1}$).

For example, if X = 123,456, we build tables for Y = 10, Z = 6, then Y = 100, Z = 56, then Y = 1000, Z = 456, and so on. Each table is a few million operations, and we do this $\log\_{10} X$ times.

Once we have the table for Z = X, we add up all the counts for entries where r is divisible by all elements of S. So the total time is O ($\log X$), but with a huge constant. If X is truly large then adding numbers is not an elementary operation anymore, so we would have another factor of log X for multi-precision addition, for a total of O ($\log^2 X$).

To give a bit more of an example: For example, the number 2 \< 10 has the set of digits { 2 } and is 2 (modulo 2520). Therefore the entry ( {2}, 2) gets a count of 1.

In the second round, we add digits 0, 1, 2, ..., 9 in front of the digit 2. That gives the numbers 02, 12, 22, 32, 42, .., 92. The sets of digits are {2}, {2}, {2}, {2, 3}, {2, 4}, ..., {2, 9} because we ignore the digits 0 and 1, and 22 still has only the digit 2. The entries ( {2}, 2), ({2}, 12), ({2}, 22), ({2,3}, 32),..., ({ 2, 9}, 92) will get a count of 1.

Since the table has about 600,000 entries, it will take quite a few rounds until the counts grow big, but when Y = $10^{18}$, the counts will be roughly around $10^{12}$. So each round is considerable but not excessive work, but as Y gets larger, it doesn't get more work.

Now lets say you have built the tables to the end, and you have say an entry ( {2, 4, 5, 6, 7}, 30) with a count of 12,590. Just an example. If you have a number x with x = 30 (modulo 2520), then the divisors of 30 that interest us are 2, 3, 5, 6. Each such x has divisors 2, 3, 5, 6 and no others up to 9 (we don't care about the divisor 1). Three of these are in the set {2, 4, 5, 6, 7} so all the 12,590 numbers count towards your total.

The same (with the set {2, 4, 5, 6, 7}) happens with the modulo 32 (divisors 2, 4), 35 (divisors 5, 7), 36 (divisors 2, 4, 6), 40 (divisors 2, 4, 5), 42 (divisors, 2, 6, 7), etc. but not with the other moduli (31, 33, 34, 37, 38, 39, 41, 43 etc. ). So you add the counts for some moduli, not for others.

---
Tags: algorithms, enumeration, counting, mathematical-programming
---


# Question
Title: Can a unnormalized floating point number be recognized also when exponent is not zero?
From Tanebaum's *Structed Computer Organization*.

> ## Exercise 4 of Appendix B
>
> The following binary floating-point number consist of a sign bit, an excess $64$, radix $2$ exponent, and a $16$-bit fraction. Normalize $0$ $1000000$ $0001010100000001$ ($\star$).

As far as I've studied, the number ($\star$) is already normalized and it is a representation of the number $1.0001010100000001 \times 2^0$.
Moreover, according to the IEEE754, if one is meant to represent an **un**normalized number, she would have to set the exponent-related bits at $0$ --which is not the case.

*My question is*: what is the exercise asking to me? Can that be an unormalized number?

Maybe Tanebaum's simply asking the reader to multiply ($\star$) by $2^3$ then to subtract $3$ from the exponent. Yet to me, that has no sense at all --instead, you're really changing the value ...

# Answer
> 1 votes
I had to re-read your question a few times to have an opinion. The question states that there exists a sign, an excess 64 exponent, and a 16-bit mantissa. It then asks you to normalize a given bit pattern. It's my opinion that you are supposed to make some inferences.

First off, an excess 64 suggests that you have a 7-bit mantissa. (It's not certain as one technically could have an excess 64 applied to an 8-bit or even a 9-bit mantissa, but those are all highly unlikely in normal circumstances.) This appears to be confirmed in the sense that they supply what appears to be one bit, followed by 7 bits, followed by 16 bits.

Second, you are being asked to normalize a value. This is commonly asked by providing you with the signed number and a positioned radix, leaving you to figure out the sign, exponent, and mantissa. But in this case, their question must be taken to imply that they are giving you a denormalized value. So I believe they want you to accept the last 16 bits just as it is given to you and to do the necessary shifting to put it back into a properly normalized form. And I therefore think they want you to accept the given exponent as a starting point that you assume is correct for the given value.

This leads to the third problem. You inserted a hidden bit on your own, on the assumption that the denormalized value carries a hidden bit. But denormalized values, even in FP formats supporting hidden bits (and not all do that) do not have an implied hidden bit. So I wonder why you inserted one on your own, writing "$1.0001010100000001\times 2^0$." If you were right about that, then why in the world would they now ask you to normalize it?? It doesn't make any sense, neither in the format of the question nor in actual experience with common cases. So I think here you must assume the opposite... that the 16 bit mantissa they gave you is instead just a pure 16-bit integer that has not been normalized and doesn't imply a hidden bit. Otherwise, what could they possibly be asking you to do?

That said, I haven't worked from your book. So I don't know the context here. You will have to use your own judgment about what I write here and see if you think I might be right about it.

If I am right, then you are being told $sign=0$, $exponent=0$ as it is in excess 64, and $value=5377$ (decimal.) And you are then asked to normalize it and create a proper 24-bit FP formatted value. Since you mentioned IEEE754, which uses hidden bit notation, I'd assume that this novel 24-bit FP format also uses hidden bit notation. I wish I had your book, as that would help to gain context, but I get something like the following: $0 \\,\\, 1001100 \\,\\,\\, 0101000000010000$

# Answer
> 0 votes
No, according to IEEE754 any number where the exponent $\ne$ 0 cannot be a denormalized number.

> A denormal number is represented with a biased exponent of all 0 bits.

IEEE754 allows denormalized numbers in order to allow gradual underflow.
This comes at a price of decreased range. The exponent -126 would have been represented by all zeros *(for single precision)* has been sacrificed to express denormal numbers instead.

If other exponents would be sacrificed as well (e.g. to enable gradual overflow to infinity) the range would decrease further. IEEE754 opted not to allow this and for this reason denormal numbers in IEEE754 have a zero exponent by definition.

# Answer
> 0 votes
For 32 and 64 bit floating point, there is always an implicit leading 1 bit in the mantissa unless the exponent is zero. With a zero exponent, the implicit leading bit is zero. All the mantissa bits actually have the same value as if the exponents were 1.

For 80 bit extended precision floating point, the full 64 bit of the mantissa is stored, including the leading bit. If the exponent is not zero, the leading bit of the mantissa should be 1. A number with a non-zero exponent and a zero as the highest bit of the mantissa is called "unnormalised". The result of any arithmetic operation is never an unnormalised number, and it depends on the processor how exactly unnormalised (not denormalised) numbers are treated.

---
Tags: floating-point, number-formats
---


title: blockchain database - why so redundant

text:
# Question
Title: blockchain database - why so redundant
I've become interested in blockchain databases. Everywhere I've read it said that each user has to have his/her own copy of database.

Why can't distributed blockchain database be 'distributed' to reside partly on many computers to achieve say fixed 10 times redundancy, not times number of users redundancy? Will speed be times slower or other reason it's not done?

# Answer
See https://en.wikipedia.org/wiki/Blockchain\_(database)#Decentralization, which states that *"Every node in a decentralized system has a copy of the blockchain. This avoids the need to have a centralized database managed by a trusted third party."*

This is as true of 10 computers as it is of one. It's not about redundancy from this perspective, though that is certainly a motivating factor. *It's about having zero centralized authorities,* and the only way to do that is to allow everyone to have a copy of the blockchain.
> 4 votes

---
Tags: distributed-systems, databases
---


title: Variants of the 3-Partition problem

text:
# Question
Title: Variants of the 3-Partition problem
The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known that the 3SAT problem has a plenty of variants. Are there some variants of the 3-Partition problem discussed in the literature?

# Answer
One variant of 3-partition is the following distinct 3-partition problem, shown to be NP-complete in \[1\].

> **Distinct 3-partition**
>
> **Input:** A set $X = \\{a\_1,a\_2,\ldots,a\_{3n}\\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma\_{i=1}^{3n} a\_i = nB$, and $B/4 \< a\_i \< B/2$, where $i \in \[3n\]$.
>
> **Question:** Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?

The problem is also NP-complete when $B$ is bounded above by a polynomial in $n$. For an "application", a reduction from the problem is used in \[2\] to show a certain graph problem is hard.

---

\[1\] H. Hulett, T.G. Will, G.J. Woeginger, Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, Operations Research Letters 36 (2008) 594–596.

\[2\] Bonato, Anthony, Jeannette Janssen, and Elham Roshanbin. "Burning a graph is hard." arXiv preprint arXiv:1511.06774 (2015).
> 3 votes

---
Tags: complexity-theory, reference-request, np-complete
---


title: Book for algorithms beyond Cormen

text:
# Question
Title: Book for algorithms beyond Cormen
I've finished most of the material in Cormen's Intro to Algorithms book and I am looking for an algorithms book that covers material beyond Corman's book. Are there any recommendations?

NOTE: I asked this on stackoverflow but wasn't all too happy with the answer.

NOTE: Looking at most of the comments I think ideally I would like to find a book that would cover the material of the the 787 course in this course description.

# Answer
```
I am looking for an algorithms book that covers material beyond Corman's book.

```

This can be answered in numerous different ways, depending on what you want "beyond". I would recommend asking much more specific directions, as you are more likely to get specific answers that are helpful. As for some general guidance though:

* You may find a handful of general books that explore general algorithmic topics in more depth than Corman, but for the most part, you need to start specialising if the book is going to be *significantly* more in depth. Otherwise it is likely to be bloated and lacking in usefulness.
* So, instead look for specific topics. There is plenty of advanced material if you focus on specific topics. Are you intersted in:
    + sorting algorithms?
    + string algorithms?
    + number theoretic algorithms?
    + matrix algorithms?
    + graph algorithms?
    + geometric algorithms?
    + quantum algorithms?
    + stochastic/randomised algorithms?
    + linear programming?
    + models of computation?
    + foundational complexity theory and algorithmics?
* If you want to understand how to derive your own algorithms, focus on understanding the known data structures used in the problem space you are investgating (so, get good depth of existing knowledge) and look to have a good understanding of complexity theory and models of computation. These will give good intuitive feeling of what is possible for a given problem, and what approaches will likely have better success, even if you have a hard time proving lower bounds formally.

Books like Papadimitriou's several or Arora/Barak on Complexity Theory would be my suggestion for follow up to Corman to understand better what algorithms are possible and build up some intuition, but I would just look to modern overview papers on particular areas and look to graduate and research level books on more specific topics if you want familiarity with the modern level of understanding.
> 11 votes

# Answer
As others have noted, books about (advanced) algorithms are best selected by topic. A good but heavy-weight general reference with rigorous analysis is probably The Art of Computer Programming by Knuth.

As for analysis techniques, you may be interested in An Introduction to the Analysis of Algorithms by Sedgewick and Flajolet, and Algorithmic Combinatorics by Flajolet and Sedgewick for more theory in the same direction.

For approaches on tackling hard problems, see Algorithmics for Hard Problems by Hromkovič.
> 18 votes

# Answer
Have you looked at Handbook of Theoretical Computer Science

If you want to move beyond imperative algorithms and move into functional programming, take a look at Purely Functional Data Structures. I know the title says data structures but the algorithms in the book may open your eyes to a different way of programming.

EDIT

I took a look at the course description for CS 787, and current classes

It notes

> We will mainly use papers from the literature. These will be made available either as handouts or via the web. Several books on algorithms will be put on reserve at Wendt library.

If it were me I would contact the instructor directory. :)
> 5 votes

# Answer
The computer algorithms are very complex and hard to understand topic, so there is no best book, i.e. just one book which will explain you everything. You need to read couple of them to get hold of this topic.

here are my 2 cents based upon my 10 years of programming and attending numerous interviews:

1. Algorithm Design Manual by Steven S. Skiena
2. Algorithms (http://algs4.cs.princeton.edu/home/) by Sedgwick
3. Introduction to Algorithms By Thomas Cormen
4. Algorithms for Interviews by Adnan Aziz
5. Python Algorithms: Mastering Basic Algorithms in the Python Language
6. Algorithms Unlocked by Thomas Cormen

**Reference:**
> -2 votes

---
Tags: algorithms, reference-request, books
---


# Question
Title: Proving a grammar/language as not regular
$D → T ∨ D | T$

$T → C ∧ T | C$

$C → ¬C | name | ( D )$

$name → a | b | c | d$

I am not looking for the complete answer, but more the methodology of working this out. How would I go about proving that this language is not regular?

# Answer
> 1 votes
* First you need to have a good idea of what the language really looks like. The grammar does not tell you much in an obvious way. Play around with some examples of derivations.
* The most common way of proving that a language is not regular is the pumping lemma for regular languages. In this case it might no be easy to apply it. A good option is to
* simplify the language using closure properties. For example, the intersection of two regular languages is regular again. Now check what the intersection of you language with the regular $(^+ a )^+$ is. On this you should be able to apply the pumping lemma without big complications. If you manage to prove that this intersection is not regular, your original language cannot have been regular.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Is Green's the best 16-input sorting network so far?
Every paper says that Green's construction is the best 16-input sorting network as for now.

But why does Wikipedia says: "Size, lower bound: 53"?

I thought "lower bound" meant:"If there exists at least an algorithm that can...". Am I wrong?

# Answer
> 8 votes
No, a lower bound means that somebody has proved that anything smaller than 53 is impossible. That doesn't mean that a 53-gate network is known or even necessarily possible; just that there cannot be a smaller one than that.

# Answer
> 6 votes
The lower bound for an problem states that "no algorithm can do better than this". In your case, it means that no sorting network for 16 inputs can have fewer than 53 gates.

Sometimes there can be confusion between the reader and writer regarding whether a lower bound is tight or not. A tight lower bound states, "no algorithm can do better than this, **and** this number is achievable in practice".

A tight lower bound can come from a non-constructive proof or from an actual example that can be applied in practice.

---

Here is an example from comparison-based sorting algorithms. By combinatorics, the lower bound is $\Omega(n \log n)$ operations to perform sorting. But we also have algorithms like heap sort that take $O(n \log n)$ running time. Therefore in this case, the lower bound is a tight one.

But a different example is the number of moves to solve a standard Rubik's cube. The simple lower bound started at 18, and it took years of research and computation to raise this number to the tight lower bound of 20.

# Answer
> -2 votes
there are relatively new results in this area using SAT solvers and some new theory. optimal networks up to *n*=16 are now known/ constructed. this paper explains the techniques and following is a link given in the paper to optimal sorting network constructions up to n=16. (the paper does not mention Greens construction in particular but it does reference Knuth and maybe that is enough to correlate precisely if Knuth refers to Greens construction.)

---
Tags: complexity-theory, terminology, sorting, lower-bounds, circuits
---


# Question
Title: How to find greatest set intersection of at least a given cardinality?
While dealing with a problem, I uncovered this subproblem:

Input: A set of sets $S = \\{S\_1,...,S\_r\\}$ where $\mid$ $S\_1$ $\cup$ ... $\cup$ $S\_r$$\mid = n$, as well as a number $k\<n$.

Output: A subset of $S$, $T = \\{S\_{t\_{1}},...,S\_{t\_{p}}\\}$ so that $\mid$ $S\_{t\_{1}}$ $\cap$ ... $\cap$ $S\_{t\_{p}}$$\mid$ $\geq k$ with $p=\mid T \mid$ maximized.

I.e. find the greatest number of sets in $S$ whose intersection preserves at least $k$ elements.

Is there any way of solving this problem in reasonable time, say polynomial in $r$ and $n$?

I tried to create an algorithm to solve the problem in reasonable time for large sets and $n$ and got nowhere. There's the obvious brute force algorithm that runs in $n2^r$ time. I also tried to construct a DP algorithm that used smaller subsets for optimal substructure, i.e. making use of $(A \cap B) \cap C = A \cap B \cap C$ and that if $\mid A \cap B \mid \< k$, then it's not worth searching any further with $A\cap B$. However, I didn't get anywhere since the number of different subsets grows too quickly.

On the one hand, the problem feels kind of "set coverish" and thus I suspect it's hard. On the other, I'd imagine a problem this simple to be mentioned in some list of hard problems if it were intractable.

# Answer
> 6 votes
Here is how to reduce clique to your problem. Given a graph $G = (V,E)$ and a number $\ell$, for each vertex $x$ let $$ S\_x = \left\\{\\{y,z\\} \in \binom{V}{2} : y,z \neq x\right\\} \cup \\{ \\{x,y\\} : \\{x,y\\} \in E \\}. $$ In words, $S\_x$ contains all edges in the graph touching $x$, and all edges not touching $x$, whether or not they're in the graph.

One can then show that for every set of vertices $A$, $$ \bigcap\_{x \in A} S\_x = \left\\{\\{y,z\\} \in \binom{V}{2} : y,z \notin A\right\\} \cup \\{ \\{x,y\\} : x \in A \text{ and } \\{x,y\\} \in E \\}. $$ In words, the intersection of $S\_x$ for $x \in A$ consists of all edges in the graph touching $A$, as well as all edges not touching $A$ (whether in the graph or not). The size of this intersection reaches its maximum $\binom{|V|-|A|}{2} + \binom{|A|}{2}$ if and only if $A$ is a clique in the graph.

Choosing $k = \binom{|V|-\ell}{2} + \binom{\ell}{2}$, the graph contains an $\ell$-clique if and only if there are $p=\ell$ sets whose intersection contains at least $k$ points. The value of $n$ for this instance is $n = \binom{|V|}{2}$.

---
Tags: algorithms, optimization, combinatorics
---


# Question
Title: Optimizing neural network on small training set
I'm in the process of optimizing my neural network. I'd like to optimize on a small training set (1000 rows) as opposed to my full training set (100K rows) for speed reasons.

Will the optimal hyper-parameters (i.e. my learning rate, dropout prob, regularization parameter, # of hidden units, etc...) for my small training set also be optimal for my large training set? In other words, which parameters can I optimize on my small training set, and which must I try to optimize on my large?

Thanks--

# Answer
> 2 votes
This is a bad idea. For many tasks, you'll likely get poor performance. For many machine learning tasks, having a lot of data is essential to getting good results.

Instead, I recommend you set yourself up with software and hardware that can train your network on the full training set efficiently: buy a fast GPU, use software that can use the GPU for training, use stochastic gradient descent with mini-batches and other standard techniques.

You'll likely need to optimize all of your hyper-parameters on the full training set. I don't think optimizing the hyper-parameters on a small training set is likely to work well. If there's any past research on similar machine learning tasks, you might look at what network architecture and hyper-parameters they used as use that as a starting point for your exploration.

---
Tags: machine-learning, neural-networks
---


# Question
Title: Hyperplane through origin which goes through most number of points
Given $M$ points in $\mathbb{R}^{N}$ (where $M$ is larger than $N$), I was wondering if there is an algorithm to find a $N-1$-dimensional hyperplane which goes through the **origin** and also intersects as many points as possible.

Specifically, does there exist an algorithm which runs faster than $O(M^{N})$ time? This is achieved by looking at all subspaces defined by each subset of $N-1$ points.

Furthermore, if there is no faster exact algorithm, I was wondering if there are any constant factor approximations which run faster than $O(M^{N})$. It would be greatly appreciated if someone can point me to the correct papers or references for these.

# Answer
I suspect your problem might be hard, for the following reason: The corresponding problem when working over a finite field is NP-hard.

Your problem is equivalent to the following:

*Inputs:* a $M \times N$ matrix $A$, with real-valued entries
*Goal:* Find $x \in \mathbb{R}^N$ that maximizes the number of 0 entries in $Ax$

The corresponding problem for a finite field (e.g., working with integers modulo a prime $p$, rather than real numbers) is known as the minimum-weight codeword problem for linear codes, and it is known to be NP-hard. See, e.g., https://cs.stackexchange.com/a/59922/755, Solving/Optimizing a linear system in a finite field (Z/2Z), https://cstheory.stackexchange.com/q/27460/5038, https://cstheory.stackexchange.com/q/21678/5038. It's always possible that the problem is dramatically easier for real numbers than over a finite field, but that seems like it might be a lot to hope for.

Anyway, I don't know if there are algorithms with running time better than $O(M^N)$, but I suspect it's hard (not likely to have a polynomial-time solution).

See also https://cstheory.stackexchange.com/q/3719/5038 for a related but different problem.
> 2 votes

---
Tags: algorithms, optimization, computational-geometry, discrete-mathematics, graphics
---


title: The nearest points in a set

text:
# Question
Title: The nearest points in a set
I have $N$ points and I have a distance between every pair of points stored in a 2D matrix. The goal is to find the nearest $K$ points among these $N$ points. "Nearest" means the sum of all distances between the $K$ points is smallest. A brute-force way is to search all combinations of $K$ points from the $N$ points. However, $K \ll N$. For example, $K$ is 5 and $N$ is 100. It is infeasible to search all ${100 \choose 5}$ combinations.

Actually, the distance between points is a metric to measure the difference between elements in the set, so it is better to describe the problem using graph rather than computational geometry.

I have read Clique problem on wiki, but I think the setting is different from my context here.

More info: The elements are probability discrete distributions. The metric here is Hellinger distance en.wikipedia.org/wiki/Hellinger\_distance, which is to measure the difference between two probability distributions. I like to find the most similar probability distribution subset from a set.

# Answer
> 3 votes
This problem does generalize the clique problem.

One example of a metric is the shortest path distance in a connected, unweighted graph $G$, where the distance between vertices $u$ and $v$, $d(u,v)$, is the length of the shortest path between them. There exists a clique of size $K$ in this graph if and only if we can find $K$ points whose distances sum to ${K \choose 2}$.

For finding cliques of size $5$ you can do slightly better than brute force: see this answer. However without more structure on the metric you are interested in it is an open problem to do significantly better.

# Answer
> -1 votes
If the distances are a metric that would mean if A is close to B, C, D and E, then B, C, D and E should be close to each other. . Unless someone constructed the data to make it hard, the solution ought to be one data point and four of the data points closest to it.

For every point, create a list of all the other points, sorted by distance in ascending order. For each list calculate the sum of distances between the first point and the four nearest; the smallest sum would be your benchmark. Sort the points by this sum in ascending order. You now have everything arranged in an order that would tend to give you small sums of distances.

Now you can do an exhaustive search with shortcuts: You iterate through the first points with the smallest sum first, the second points in order of distance to the first points, etc. Most important that you ignore anything that cannot be optimal. Say your smallest sum of distances so far is 40, and you picked four points with a sum of distances of 26.9, then the fifth point cannot be further than 13.1 away from the first point. If the distances obey the triangular equation then you can take further shortcuts.

Say you have three points with a sum of distances of 7, the second and third points are at distance 2 and 3 from the first point, and the fourth point is at a distance d from the first point (and therefore the fifth at a distance at least d), then the last two points are at least d, d-2, and d-4 away from the first three points, so the sum of distances is at least 7 + 2 (3d - 6) = 6d - 5. So if the sum to beat is 40, we must have 6d - 5 ≤ 40 or d ≤ 7.5. That should seriously restrict the choice of the fourth point.

I'm sure it's possible to construct examples where this doesn't work well, but if you take say the locations of the largest 1000 cities in the world and you want the five closest to each other this would work quite well.

About proof that it gives the correct answer: Well, obviously yes. It does in principle an exhaustive search, except that it orders items in a way that small sums tend to be examined at the start of the search, and we can prune off search branches when it can be proven that they cannot lead to an optimal result. Sorting first means we get good (not optimal) results quickly which make the pruning more effective.

The counter example isn't a counter example. Yes, we will start with sorted lists that start with a point A on the inner n-gon, a few of the neighbouring points on the same n-gon, and some on the outer n-gon which isn't optimal. But that's just the starting point of the search. There was the assumption k \<\< n, which is violated (k = n/2), so it will be harder to prune the search tree effectively. But that's because we don't have k \<\< n.

---
Tags: algorithms, graphs, cluster, clustering
---


title: Term for open-ended algorithms

text:
# Question
Title: Term for open-ended algorithms
There are some enumeration problems which have little input, except for some termination criterion. Examples for the question at hand would be

* enumeration of prime numbers in ascending order
* enumeration of grid points by increasing distance

For these there exist two fundamentally different techniques:

1. With one class of approaches you have to state the scope of your question up front. You'd state the upper bound for the primes you want, the maximal distance, or similar. The Sieve of Eratosthenes would fall into this category, as would an algorithm enumerating all points in a rectangle and then sorting them by distance.
2. With another class of approaches, you *don't* have to state the extent of the required output up front. You can see the enumeration as a lazily evaluated infinite sequence, and feed it to some other part of your code that should eventually terminate the generation once a generated output satisfies your requirements. Testing each odd number against a list of already found primes would be an example from this class.

Now I'm looking for a term to distinguish these two forms. Somehow the latter approach feels closely related to online algorithms, which is why I added that tag. But every deifnition I could find specifies an online algorithm as processing its *input* incrementally. There is almost no input here, unless you count the one-bit decision between “give me the next item” and “that's it, stop now” as an incremental input. Would calling this an online algorithm be appropriate, or is there a better term?

# Answer
> 1 votes
Informally, you might call this lazy evaluation, or a lazily-evaluated stream.

A *$O(f(n))$-time delay algorithm* is guaranteed to output a stream of answers, with a delay of at most $O(f(n))$ time between answers. One consequence is that outputting $k$ answers will take at most $O(k \times f(n))$ time -- but you also know that you won't ever have to wait too long for the next output. (So, this helps rule out algorithms that return the first $n$ answers very rapidly and then take a really long time to return the $n+1$th answer).

An *output-sensitive* algorithm is an algorithm that outputs a stream of answers, and where the running time is some function of the length of the *output*. Normally we evaluate the running time of an algorithm as a function of the length of the *input*, but an output-sensitive algorithm is analyzed in terms of the length of the *output*. That's potentially relevant here. Suppose your goal is to enumerate all fidgets in a warbuggle. If you find an polynomial output-sensitive algorithm for this task, then you have an algorithm that's potentially useful for streaming purposes -- in particular, the *average* delay between outputs isn't too large (though the worst-case delay could potentially be quite high).

If neither of them captures exactly the concept you have in mind, then I suggest you just describe in text what properties your algorithm has, and don't worry too much about finding a short term for it.

---
Tags: algorithms, terminology, enumeration, online-algorithms
---


# Question
Title: Algorithm to enclose a 2D-gridbased-room efficient
I have the problem that I have a grid-based room which has 1 or more exits and I want to "secure" the room with minimal effort.

Here a little Example:

In this example black squares are not passable, white ones are and the ones with the arrows are the exits that should not be able to be reached.

I wan't to enclose the yellow square by converting white squares into black ones. I want to use as few conversions as possible.

Two ideas I found until now:

**1** The *fastest algorithm* in my opinion would be to just *convert all squares around the exits* but it would not be the most efficient algorithm since in this example it would cost 9 conversions (13 if diagonal movement is possible) but its possible to enclose the yellow block with only 3 (5) conversions.

**2** I found the Flood fill Algorithm, which would enable me to check if the area around the yellow square is enclosed but I can't think of a (cpu-)efficient method to try out possible conversions until I find the solution with the least conversions needed.

The Method should be able to enclose more then one targets, since otherwise an optimal solution would be often to just enclose the yellow block with 9 conversions around him. Therefore I added to my picture the green block, so the algorithm should be able to enclose all targets.

If you don't have an idea how to solve it but a hint where I could look into to find a possible solution I would be happy to hear it!

Thanks, Niko

# Answer
This is a graph cut problem.

Build a graph with one vertex per square. Add an edge between each pair of adjacent vertices (i.e., where you can go from one to the other in a single step). Add an extra "source" vertex $s$, and an edge from $s$ to each starting point (yellow/green block). Add an extra "sink" vertex $t$, and an edge from each exit to $t$.

Now your mission is to find a minimum vertex cut that separates $s$ from $t$, i.e., a subset $S$ of vertices such that every path from $s$ to $t$ traverses at least one vertex of $S$. There are standard algorithms for the minimum vertex cut problem, which you can find by searching the literature.

See also https://en.wikipedia.org/wiki/Vertex\_separator and https://cstheory.stackexchange.com/q/2877/5038 and https://cstheory.stackexchange.com/q/29464/5038.

You'll need to add the extra constraint that the subset $S$ cannot include $s$ nor $t$, but I expect it should be easy to incorporate this constraint into standard algorithms for vertex cut.
> 5 votes

---
Tags: algorithms, optimization, computational-geometry
---


title: Is FKS hashing really linear space?

text:
# Question
Title: Is FKS hashing really linear space?
In FKS hashing, I wonder if the size of the table $G\[1..n\]$ (used to record the functions $g\_i$ which is chosen randomly; one entry per bucket) is really strictly $O(n)$. Given that the probability of a hash function $g\_i$ is higher than 0.5, I can see that it will mostly hold small values (assuming we start with $g\_0$, and if that doesn't work, try $g\_1$ and so on). But I think for $n$ to $\infty$ there will be larger values as well, so that the number of bits for each entry is $log^\*(n)$ and not fixed. Right?

The reason I ask is that many minimal perfect hash functions, such as the CHD algorithm, rely on a similar mechanism, and those algorithms claim to be strict $O(n)$ space.

# Answer
> 2 votes
Space is counted in *machine words* rather than in *bits*. A machine word is allowed to contain a member of the universe $U$, and so is $O(\log |U|)$ bits wide. The array $G$ stores hash functions, via their index inside some collection of universal hash functions. The lecture notes don't mention this, but there are collections of universal hash functions of size $O(|U|^2)$. If you use one of these collections, each entry of $G$ takes $O(\log (|U|^2)) = O(\log |U|)$ bits to store, and so $O(1)$ machine words.

Why is it meaningful to count space in machine words? First of all, even if you store your set as an array (with logarithmic access time, using binary search), the number of bits is $O(n \log |U|)$ rather than $O(n)$. If we want such an array to be considered taking up linear space, we need to "divide" by $\log |U|$, and the simplest way to accomplish this is to allow each memory cell to contain $O(\log |U|)$ bits (the exact constant doesn't matter).

Another reason we would like to allow cells to contain an unbounded number of bits is so that they can store *indices*. When you implement binary search, or any other algorithm, you have variables which store indices in the array. These variables take $O(\log n)$ bits to store. When discussing algorithms, however, we often think of an index as taking $O(1)$ space. Again, the way to accomplish this is to allow each memory cell to contain at least $\log n$ bits.

On the other hand, if we allow memory cells to be of arbitrary size, then the space measure becomes trivial, since anything can be done in $O(1)$ space (though depending on the exact computation model, you might have to pay in terms of running time). The usual convention in algorithms is to allow each memory cell to contain $O(\log n)$ bits, where $n$ is the input size (in bits). In this particular case, it is more meaningful to allow a machine word to contain $O(\max(\log n, \log |U|))$ bits, and this is the way we measure the space consumption of the algorithm.

---
Tags: data-structures, hash-tables, hashing, space-analysis
---


# Question
Title: Is the prime factorization problem not an instance of the change making problem?
When using as the set of coins all logarithms of the prime numbers or numbers in general, and when using the logarithm of the number to be factored. The problem is just finding the logarithms that can be used to make the total. But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete. Can anyone explain why this is?

# Answer
> 1 votes
> When using as the set of coins all logarithms of the prime numbers or numbers in general

The change-making typically assumes a *finite* set of coins.

You can, of course, extend it to infinite sets of coins but then you get a different problem. Depending on the exact formulation, it seems plausible that integer factorization would reduce to that new problem.

> But then the change making problem is listed as non NP problem, but the prime factorization problem is found to be NP complete.

Careful with your terminology there.

The general change-making problem is certainly in NP since it can be solved by integer programming. I do not know if it is NP-hard, but the common algorithms do *not* show that it is in P since they are only pseudo-polynomial. This shows, at least, that the problem is not *strongly* NP-hard.

Real-world change-making usually deals with *canonical* sets of coins for which a simple greedy algorithm works; it runs in constant time assuming a constant set of coins and the uniform cost model.

Integer factoring, on the other hand, is not known to be in P nor NP-hard; it's an open problem, and if P ≠ NP it may be in neither (but in NPI instead).

---
Tags: complexity-theory, optimization, factoring, primes
---


# Question
Title: Linear time algorithm for finding $k$ shortest paths from $s$ to $t$
> **Definition.** Given a graph $G=(V,E)$ and two vertices $s$ and $t$, the $k$-shortest-paths problem is finding the $k$ shortest simple paths between $s$ and $t$ in $G$.

Note that the length of these paths is not necessarily equal, and vertices $s$ and $t$ are necessarily $k$-connected. I was wondering if there is a linear time (in terms of $n$ and $m$) algorithm for this problem.

I have looked at a few papers in the literature, such as "*A New Implementation Of Yen's Ranking Loopless Paths Algorithm*" but the time complexity is really high $O(Kn(m+nlogn))$. Also, the other paper by Epstein "*Finding the k shortest paths*" presents an algorithm that finds the $k$ shortest paths that are not necessarily simple paths with running time $O(n+m+k)$.

Is there a linear-time algorithm for the $k$-simple-shortest-paths problem?

# Answer
> 7 votes
First of all, the answer that applies here was already given by Raphael in the comments to the question: "*Given that we don't even know how to find one simple shortest path in linear time, I doubt it.*" In the following, thus, I will assume you are interested in knowing about the best available algorithms in the current state of the art. In the following, I describe the best worst-case bound (to the best of my knowledge) but also an algorithm that might run in *linear* time in some specific cases.

But before describing the latest developments in the state of the art, I wanted to **emphasize** the importance of *simple paths* in this specific problem. As a matter of fact, many people overlooks the importance of this requirement and some do not even understand it at first glance.

When computing the shortest path from a start vertex to a goal vertex, the optimal path is necessarily *simple*, i.e., it does not repeat any vertices. However, when computing $k$ optimal paths, the second, third, ... best paths might not be simple. To prove it, I provide here an example that has been slightly adapted from Hershberger, Maxel & Suri, 2007:

The Figure shows a digraph whose optimal solution (from the source vertex $s$ to the goal vertex $t$) is the path $\pi\_1 : \langle s, A, B, C, D, t\rangle$ with a cost equal to 5. If paths are not required to be simple, then the second and third optimal paths are $\pi\_2 : \langle s, A, B, C, D, C, D, t\rangle$ and $\pi\_3 : \langle s, A, B, A, B, C, D, t\rangle$ both with a cost equal to 7. However, if paths are required to be simple, then the second and third optimal paths would be $\pi\_2 : \langle s, F, t\rangle$ and $\pi\_3 : \langle s, G, t\rangle $ with costs 10 and 11, respectively.

Given a graph $G(V, E)$ where $V$ is the set of vertices and $\langle u, v\rangle\in E, u, v\in V$ if there is an edge between vertices $u$ and $v$, the current state of the art for this problem to the best of my knowledge is described below:

The first significant improvement to solve the $k$ optimal paths problem is Eppstein's algorithm (Eppstein, 1998) which runs in $O(|E|+|V|\log |V|+k)$. However, this algorithm requires the graph to be given explicitly. $K^\*$ alleviates this requirement while maintaining the low complexity (Aljazzar & Leue, 2011) and, additionally, enables the application of admissible heuristics. In both cases, the output computed by these algorithms are not necessarily simple paths.

In case that paths are required to be simple, the best results is due to Yen (Yen, 1971, 1972), generalized later by Lawler (Lawler, 1972), which using modern data structures can be implemented in $O(k|V|(|E|+|V|\log |V|))$ worst-case time. In the case of undirected graphs, Katoh, Ibaraki and Mine (Katoh, Ibaraki & Mine, 1982) improve Yen's algorithm to $O(k(|E|+|V|\log |V|))$ time. While Yen's asymptotic worst-case bound for enumerating $k$ simple shortest paths in a directed graph remains unbeaten (again, to the best of my knowledge!), several attempts have been done to outperform it in practice.

One of such works is due to John Hershberger et al., who introduced a *replacement paths algorithm* which is known to fail scarcely. As a result, their algorithm delivers a speedup that grows linearly with the average number of edges in the $k$ shortest paths but, for some cases (as random graphs), this speedup is minimized.

Hope this helps,

**Bibliography**

Aljazzar, H. & Leue, S. (2011). $K^\*$: A heuristic search algorithm for finding the $k$ shortest paths. Artificial Intelligence, 175(18), 2129-2154.

Eppstein, D. (1998). Finding the $k$ shortest paths. SIAM Journal on Computing, 28(2), 652-673.

Hershberger, J., Maxel, M. & Suri, S. (2007). Finding the $k$ shortest simple paths: A new algorithm and its implementation. ACM Transactions on Algorithms, 3(4), 45-46

Katoh, N., Ibaraki, T. & Mine, H. (1982). An efficient algorithm for $k$ shortest simple paths. Networks, 12, 411-427.

Lawler, E. L. (1972). A procedure for computing the $k$ best solutions to discrete optimization problems and its application to the shortest path problem. Management Science, 18, 401-405.

Yen, J.Y. (1971). Finding the $k$ shortest loopless paths in a network. Management Sciences, 17, 712-716.

Yen, J.Y. (1972). Another algorithm for finding the $k$ shortest loopless network paths. Proceedings of 41st Management Operations Research Society of America, 20.

---
Tags: algorithms, graphs, optimization, shortest-path, enumeration
---


# Question
Title: Terminology for a graph obtained from another by adding edges
$H$ is a supergraph of $G$ if it can be obtained from $G$ by adding, edges, vertices, or both.

Is there a standard terminology for a graph that can be obtained from $G$ only by adding edges?

# Answer
If $H$ is made by adding only edges to $G$, then $G$ is a *spanning subgraph* of $H$. However, I'm not aware of any way of phrasing it that makes $H$ the subject of the sentence.
> 3 votes

# Answer
In *graph modification algorithms*, a graph $H$ is called a *completion* of $G$ if there exists a set of edges $F \subseteq \[V(G)\]^2$ such that $G+F \cong H$.

You can search on arxiv for examples such as

See also:
> 3 votes

# Answer
We often think of a graph as the set of its edges, the vertex set being fixed. This is not a universal point of view, but is common enough. In that case you can just write $H \supseteq G$, and say that $H$ is a supergraph of $G$. Just make sure that you explain what you mean by these notations.

Generally speaking, *subgraph* is ambiguous — it's not clear whether you're allowed to remove vertices. *Supergraph* is somewhat less common, and suffers from similar ambiguity. Whenever a notion is ambiguous, and you are worried that the reader won't be able to guess correctly from context, you should explain clearly what you mean, humpty-dumpty style.
> 2 votes

---
Tags: graphs, terminology
---


# Question
Title: What is the fastest way to check if an integer is divisible by another?
What would the Big O be? Can something like this be done in O(log(n)) where n is the number of bits?

# Answer
## Integer division

The best algorithm known for integer division has running time that is slightly more than linear, i.e., a bit more than $O(n)$. In particular, it is something like $O(n \lg n 2^{\Theta(\lg^\* n}))$ (which is a bit faster than $O(n \lg n \lg \lg n)$. The time complexity of integer division is the same as the time complexity of integer multiplication. See https://en.wikipedia.org/wiki/Division\_algorithm and https://en.wikipedia.org/wiki/Multiplication\_algorithm.

Caution: these algorithms are purely theoretical. The constants hidden by the big-O notation make them impractical for most sizes you'll run into in real life. But there are plenty of other algorithms that are faster than the naive algorithm and are useful in practice.

No, you can't do it in $O(\lg n)$ time, where $n$ is the number of bits in the input: you obviously can't do it in less than $O(n)$ time, since it takes that much time just to read in the entire input.

## Testing divisibility

The problem of testing divisibility could in theory be easier: it asks for just a yes-or-no answer (is $y$ divisible by $x$ or not?) instead of the result of the full division (compute $\lfloor y/x \rfloor$). Obviously, you can use any algorithm for integer division to test integer divisibility (with the same running time). I don't know if there is any faster way to test integer divisibility.

A conceptually simple way to test whether $y$ is divisible by $x$ is to check whether $y \bmod x$ is zero or not. However, I don't know of any way to compute the remainder $y \bmod x$ in linear time (in time linear in the number of bits of the input, i.e., in $O(n)$ time, where $n=\lg(x)+\lg(y)$). As before, you obviously can't do it in less than $O(n)$ time.

See also https://cstheory.stackexchange.com/q/16788/5038, which basically states the same thing: no faster algorithms are known, but no one has proven lower bounds ruling out the possibility of faster algorithms.
> 4 votes

---
Tags: algorithms, decision-problem, efficiency, number-theory
---


# Question
Title: Problems that are easy on bipartite but hard on general graphs
Are there any problems that are easy for bipartite graphs, but hard for general graphs?

I am asking because some classical problems are formulated in reference to people looking for a spouse, such as the marriage problem (for straight people) and the stable marriage problem (for straight people). Both are in FP.

If one removes the requirement that there are two genders and that every man has to marry exactly one women, the *general stable marriage problem* (my term) is the same as the stable roommates problem, and a solution is no longer guaranteed to exist. I wonder if there are other problems which are explained using similar metaphors for which there is also an increase in complexity.

# Answer
> 7 votes
There are several well-known NP-complete problems that become solvable in polynomial-time for bipartite graphs. For example, 3-coloring is easy as bipartite graphs are precisely the 2-colorable graphs. Another example is independent set which is made easy by König's theorem.

Wikipedia also lists a problem that is NP-hard for general graphs but is trivially in P for bipartite graphs: the odd cycle transversal problem.

---
Tags: complexity-theory, graphs, bipartite-matching
---


# Question
Title: Compute height of AVL tree as efficiently as possible
Given an AVL tree, I want to compute its height as efficiently as possible. $\newcommand{\bf}{\text{bf}}\newcommand{\height}{\text{height}}$

Each node of an AVL tree stores its balance factor ($\bf$), defined as

$$\bf(v)=\height(v.\text{left}) - \height(v.\text{right}).$$

We can recursively compute the height of an AVL tree in $O(\log n)$ time, using the following recursive procedure:

Height($v$):
1. If $v$ is a leaf node, return 0.
2. If $\bf(v)=+1$, return Height($v.\text{left}$).
3. If $\bf(v)=-1$, return Height($v.\text{right}$).
4. If $\bf(v)=0$, return Height($v.\text{left}$). (returning Height($v.\text{right}$) would work too)

This recursive algorithm works, because the balance factor tells us which is taller, the left subtree or the right subtree, and the algorithm always recurses into the taller subtree.

My question is: Is there a faster algorithm? Can we do better than $O(\log n)$ time? Assume we can't augment the tree to store extra information in it; we are restricted to only the information that is already normally stored in an AVL tree.

# Answer
No. There's a $\Omega(\lg n)$ lower bound. You can't do better than $O(\lg n)$ time. In fact, any algorithm has to visit at least $H-1$ nodes, where $H$ is the height of the tree.

Let $T\_1$ be a tree of height $H$, where the balance factor at every node at all but the bottom two levels is 0. In other words, it is a perfect binary tree of height $H$, except that some subset of the leaves are missing; at the level above the leaves, all nodes have balance factor $+1$, $0$, or $-1$; and at all levels above that, the balance factor is $0$.

Let $T\_2$ be an analogous tree of height $H+1$, i.e., it has height $H+1$ and the balance factor at all but the bottom two levels is 0.

Both $T\_1$ and $T\_2$ are AVL trees.

Now note that any algorithm has to visit at least $H-1$ nodes to distinguish $T\_1$ from $T\_2$. Their first $H-2$ levels look identical (every node has two children and has balance factor 0), so you can't tell them apart until you have visited at least $H-1$ nodes. To count as a correct algorithm for this problem, the algorithm has to produce the right answer on both $T\_1$ and on $T\_2$.

Consequently, any algorithm has to have worst-case running time at least $H-1$, i.e., $\Omega(H)$.
> 4 votes

# Answer
There is a $\Omega(\lg \lg n)$ lower bound: you can't hope for an algorithm that is faster than $O(\lg \lg n)$ time.

Let the height of the tree be $H$. AVL trees are balanced, so as a result the height is $H=\Theta(\lg n)$.

Suppose we solve the height problem by visiting the nodes in a longest path, one by one. The longest path has length $H$, so this approach will take $\Theta(H) = \Theta(\lg n)$ time.

Alternatively, suppose (just suppose) that we actually stored the height on a node at all times. Then we could get the height in $O(1)$ time easily. Of course, AVL trees don't actually store the height in each node, so we can't actually do that in this case.

Nonethelesss, this suggests we can model the problem as a communication problem. During tree manipulation, each node has some information to communicate to the algorithm, but the channel is limited to just $1.6$ bits per node (and you cannot choose that bit, it has to be the balance factor). Why $1.6$ bits? Because there are only three possible values for the balance factor, $-1$, $0$, or $+1$, and $\lg 3 \approx 1.6$.

We'd like this channel to communicate the integer $H$. Obviously, this will require at least $\lg H$ bits. Since each node carries only $1.6$ bits of information, that means that we're going to need to visit at least $(\lg H)/1.6 = \Omega(\lg H) = \Omega(\lg \lg n)$ nodes. Therefore, the optimal algorithm cannot possibly be faster than $\Omega(\lg \lg n)$ time.

In particular, there is no hope for an $O(1)$-time algorithm, assuming you are using an unaugmented AVL tree.
> 3 votes

# Answer
For every node in the AVL, we keep the height of the node as well - so that the balance factor can be calculated in constant time. Can you expand the definition for your "height()" function?
> -1 votes

---
Tags: algorithms, data-structures, binary-trees, search-trees, balanced-search-trees
---


title: What does detection stability mean?

text:
# Question
Title: What does detection stability mean?
I am reading the paper "A new approach to intrusion detection using Artificial Neural Networks and fuzzy clustering" by Gang Wang, Jinxing Hao, Jian Ma and Lihua Huang (*Expert Systems with Applications*, 37(9):6225–6232, 2010, available at Science Direct). I don't understand the term "detection stability". What does that mean?

The context is that existing intrusion detection systems are claimed to have poor "detection stability" when it comes to rare attacks.

# Answer
Detection stability is about consistency of detection, in this case rare events are classified independent of small changes. One might think of detector having smooth function when it is stable and chaos-like, heavily discontinous when it is not.

Detection stability in the case of rare events (rare attacks) is about consistency and fluctuation. The lack of stability means that similar events, that differ marginaly will not be detected, becase the techniques are very prone to fluctuations - that is a very bad property, malicious query with e.g. $99\\%$ classification when changed slightly might drop below detection threshold. Another outcome is that slight changes to the rest of population will influence rare queries.
> 1 votes

---
Tags: terminology
---