# Question
Title: Transform unstructured flow charts into structured ones
Has anyone studied the problem of converting a generic flowchart to a semantically equivalent "structured flowchart" (i.e. one that only uses the 'if' and 'while' block structure)?

I can see this may be relevant to code generation and optimization but I've not been able to find anything on the topic.

Intuitively, I would say that the graph corresponding to a structured flowchart must have no intersecting cycle, if this is not the case some sort of auxiliary variable must be introduced.

In the picture below, for example, the graph for the unstructured flowchart has the two cycle that intersect. In case of nested loops, one would have had one of the two cycle completely contained in the other.

I'm pretty sure that there's much more than this.

Could anyone point me in the right direction?

# Answer
> 2 votes
Yes. This has been studied in the research literature under the name "goto removal" or "goto elimination": it is the problem of taking a program with gotos, and removing the gotos.

This became of interest after structured programming became more popular; one simplistic interpretation of structured programming was that you shouldn't use gotos. See also the structured program theorem.

If you search for "goto elimination" on Google Scholar, you will find a number of papers that discuss this topic, and from there you should be able to find many more.

---
Tags: graphs
---


# Question
Title: minimum number of states for the regular expression
Could somebody please tell me if there is a way to create a DFA with 8 states for the regular expression $$(111 + 11111)^\*$$ I was able to create a DFA with 8 states, but the place I saw the question has answer as 9 states. And if possible, could you please show me the DFA.

Thanks

# Answer
We can summarize this unary language by the list of possible lengths of words: $$ 0,3,5,6,8,9,10,11,12,\ldots. $$ Now let us look at (left) shifts of this list: $$ 0,3,5,6,8-\infty \\ 2,4,5,7-\infty \\ 1,3,4,6-\infty \\ 0,2,3,5-\infty \\ 1,2,4-\infty \\ 0,1,3-\infty \\ 0,2-\infty \\ 1-\infty \\ 0-\infty $$ There are 9 different shifts, and so 9 different states in the minimal DFA. In this case, the minimal DFA is very simple: it has 9 states $s\_0,\ldots,s\_8$, with arrows $s\_i \to s\_{i+1}$ (for $i \< 8$) and $s\_8\to s\_8$, starting state $s\_0$, and accepting states $s\_0,s\_3,s\_5,s\_6,s\_8$.

This sort of reasoning works for all unary languages, though sometimes the minimal DFA won't be a simple path. For languages of the form $(1^{n\_1}+\cdots+1^{n\_k})^\*$, the minimal DFA is in fact always a path, and assuming (without loss of generality) that $\mathrm{gcd}(n\_1,\ldots,n\_k)=1$, the number of states exactly equals $2$ plus the maximal integer *not* representable as a sum of non-negative multiples of $n\_1,\ldots,n\_k$ (in our case, $7$).
> 4 votes

---
Tags: finite-automata, regular-expressions
---


# Question
Title: Given a minimum vertex cover can we find all the others in polynomial time?
Having found one minimum vertex cover of a connected undirected graph, is there a known polynomial-time algorithm for finding all the other minimum vertex covers of the graph, or is this problem NP-complete as well?

**Another question:** what other ways (not necessarily polynomial-time) of finding the other MVCs when having one of them are there, Other than backtracking or re-running the algorithm that found the first MVC? A good answer to my original question would suffice marking it as such.

# Answer
Just complementing on D.W.'s already correct answer.

Take a collection of disjoint copies of triangles. This has $2^{n/3}$ many vertex covers. If you add a universal vertex (a vertex connected to every other vertex), the graph obviously becomes connected.

Now, this universal vertex is always going to be in any minimum vertex cover. However, for the rest of the graph (the original triangles), you still need to cover all the edges. There are of course $2^{n/3}$ ways of choosing vertices to the vertex cover.

However, there is a well-known algorithm which enumerates every *minimal* vertex cover with *polynomial delay*, meaning that it takes polynomial time between every output. This means that in graphs with few vertex covers, you can do this relatively quickly.

For your second question, the simplest is probably the $2^k n^2$ algorithm where $k$ is the size of the optimal vertex cover. You branch on edges, deleting the vertex you chose to the vertex cover, and when you have an edgeless graph, you output the set of vertices you deleted.
> 3 votes

# Answer
No, there is no polynomial-time algorithm: there can be exponentially many minimum vertex covers, so there is no way to list them all in polynomial time.
> 1 votes

# Answer
In general, there is little that we can say about \`\`promise'' variants of NP-hard problems. If I promise you that a solution to the problem exists, it is not clear that you'll be able to find it. There's another class of problems called PPAD, where you are *guaranteed* that a solution exists, but it is not known whether finding it can be done in polynomial time. Famous problems in PPAD include finding a fixed point of a function, and finding a Nash equilibrium in mixed strategies.

The following paper talks about such promise variants for SAT.

http://eccc.hpi-web.de/report/2013/159/
> 0 votes

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


# Question
Title: Finding undirected cycles in linear time (triangulating graphs while minimizing degree)
In the article \["Triangulating Planar Graphs While Minimizing the Maximum Degree"\] by Kant and Bodlaender \[1\], Section 4 briefly mentions the extraction of elementary cycles (no repeating edges) from what I assume is an undirected graph $H$. It has the following to say:

> $H$ is planar and bipartite.
>
> ...using a simple modification of Euler's technique to find an Eulerian cycle in a graph, we can extract the elementary cycles $C\_\mathrm{elem}$ from $H$.
>
> Thus $H - C\_\mathrm{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

In the proof section it mentions that extracting elementary cycles and disjoint paths can be executed in linear time, allowing the triangulation algorithm as a whole to do the same.

From what I understand, there are no algorithms that compute the simple cycles of an undirected graph in linear time, raising the following questions:

* Which algorithm does "Euler's technique to find an Eulerian cycle" refer to? There seem to be several algorithms with varying performance.
* What is the "simple modification" in question? The paper doesn't say, and I haven't been able to find anything on the net.

---

\[1\] G. Kant and H. Bodlaender, "Triangulating Planar Graphs While Minimizing the Maximum Degree". *Information and Computation*, 135:1(1–14), 1997. (Science Direct)

# Answer
> Which algorithm does "Eulers technique to find an Eulerian cycle" refer to?

It probably refers to the Hierholzer algorithm (wiki) which takes *linear time*.

The algorithm below is from the wiki article.

1. Choose any starting vertex $v$, and follow a trail of edges from that vertex until returning to $v$.
It is not possible to get stuck at any vertex other than $v$, because the even degree of all vertices ensures that, when the trail enters another vertex $w$ there must be an unused edge leaving $w$.
The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.
2. As long as there exists a vertex $u$ that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from $u$, following unused edges until returning to $u$, and join the tour formed in this way to the previous tour.

> What is the "simple modification" in question?

Hierholzer algorithm aims to apply to Eulerian graphs which are (and should be) graphs with every vertex of even degree. In your problem, $H$ is not necessarily an Eulerian graph.

So it needs modifications: In step 1, the closed tour from $v$ to $v$ may not exist at all; and in step 2, you may not be able to start another trail from $u$, or you may not be able to return to $u$.

> Thus $H−C\_{elem}$ consists of paths $P$ with disjoint begin- and endpoints.

This can be seen from Figure 7(b) in the paper.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Each finite segment of a noncomputable integer sequence is computable
Wikipedia claims that "each finite segment of noncomputable sequence of integers is computable".

It continues to clarify: For any noncomputable function, "for any given value of n, \[...\] a trivial algorithm exists (even though it may never be known or produced by anyone)".

While I do believe this for the given example with busy beavers, I am not certain this is always correct. Is there a proof of this statement?

# Answer
> 2 votes
This is quite a fundamental point in computability theory, which has to do with the difference between being able to *find* and algorithm and knowing that an algorithm *exists*.

To illustrate the point, suppose I tell you that I'm thinking of a number between 1 and 10. Is there an algorithm that prints the number I'm thinking of? Of course! for every $i\in \\{1,...,10\\}$ there is an algorithm that prints $i$ and halts, so in particular, there is an algorithm that prints the number I'm thinkng of.

Do you know which algorithm prints the number I'm thinking of? no.

Similarly, every finite sequence can be printed by some algorithm. If you have a computable representation of that sequence, you can also *find* that algorithm, but if this finite sequence is given as an uncomputable function, then you cannot find the algorithm.

One classic example for this issue is the following: consider some TM $M$ and input $w$, we define the number $t$ as follows: $t=1$ if $M$ accepts $w$, and $0$ otherwise.

Is there an algorithm that prints $t$? yes - either the algorithm that prints $1$ and halts, or the algorithm that prints $0$ and halts.

Is there an algorithm that, given $M$ and $w$, computes the algorithm that prints $t$? No - as this would contradict the fact that $A\_{TM}$ is undecidable.

---
Tags: computability
---


# Question
Title: Relation between sets and partially computable functions
I encountered this problem.

> Let $A$ , $B$ , $C$ be disjoint sets $(A\cap B = B\cap C = A\cap C = \emptyset)$. The $f\_1, f\_2$ and $f\_3$ are partially computable functions that are defined as follow:
>
> $$ f\_1(x) = \begin{cases} 1 & x \in A\cup B \\ 2 & x \in C \\ \uparrow & \text{otherwise.} \end{cases} $$
>
> $$ f\_2(x) = \begin{cases} \uparrow & x \in A\cup C \\ 0 & \text{otherwise.} \end{cases} $$
>
> $$ f\_3(x) = \begin{cases} \uparrow & x \in B\cup C \\ 0 & \text{otherwise.} \end{cases} $$
>
> Then which of the following is true?
>
> 1. $A,B,C$ are recursive.
> 2. $A,B,C$ are not r.e.
> 3. $A,B,C$ are r.e. but not recursive.
> 4. $C$ is recursive but $A,B$ are not recursive.

I really don't know how to understand what kind of sets the $A,B,C$ are! what information $f\_1,f\_2,f\_3$ are giving us about the sets?

# Answer
> 0 votes
The problem only makes sense if $A,B,C \subseteq \mathbb{N}$ and you are to *assume* that the $f\_i$ are partially computable functions.

Your task is to check the definitions of (semi)-decidability and show resp. refute that $A$, $B$ and $C$ fulfill them.

# Answer
> 0 votes
As you said yourself, 1 is true.

To decide one of the languages, you let Turing machines or some other model of computation of all the functions run in parallel. You do so until one of the following happens:

1. $f\_1$ halts with output 2: $x \notin A, x \notin B, x \in C$
2. $f\_1$ halts with output 1 and $f\_2$ halts: $x \notin A, x \in B, x \notin C$
3. $f\_1$ halts with output 1 and $f\_3$ halts: $x \in A, x \notin B, x \notin C$
4. $f\_2$ and $f\_3$ halt: $x \notin A, x \notin B, x \notin C$

One of these cases **must** happen at some point. Therefore, this algorithm decides A, B and C.

---
Tags: computability, undecidability, semi-decidability
---


# Question
Title: Is there a difference between the name scheduler and scheduling?
Sometimes I read about the term "scheduler" (offline-scheduler, online-scheduler,...) and then I see terms called "scheduling" (offline-scheduling, online-scheduling, preemptive scheduling, non preemptive scheduling). Currently I think, that scheduling is the real work and scheduler is just a umbrella term. Is that correct ?

# Answer
This is more a question of English than computer science. For almost any regular verb (and "schedule" is a perfect example), the \[verb\]er is the thing that does the \[verb\]ing. The scheduler is the software that schedules.
> 3 votes

---
Tags: terminology, scheduling
---


# Question
Title: first intersection of two arrays of integers - double binary search feasible?
I'm interested to find the fastest possible way to find the first element of an intersection of two integers arrays (first match)

Looking for the 'fastest' algorithm I have seen different methods with different time complexities (to calculate the arrays intersection)

i.e: $O(N+M)$, $O(N * log(M)$,...

Also I have seen some references to an algorithm able to do this by implementing a double binary search to find the first match with time complexity $O(log(n)+log(m))$

Do you know about some reliable source or pseudo-code about this algorithm if such exists?

# Answer
The $O(\log n + \log m)$ algorithm is impossible. Any algorithm that purports to find an intersection between the sets must be $\Omega(n)$, since if it is faster than $\Omega(n)$ it could not examine all elements from the array but it must do so in order to be correct.

Consider the input where one set is the even numbers $\\{2,4,6,\ldots,2n\\}$ and the other set the odd nubmers $\\{1,3,5,\ldots,2n-1\\}$. If on this input the algorithm doesn't examine all of the elements from the first array, then assume it does not examine the element $2k$ from the first array. Then if presented with the same input but with $2k$ replaced by $2k-1$ it will incorrectly report there is no intersection. So any correct algorithm must examine all elements from at least one of the arrays.

The $O(n \log m)$ algorithm is trivial, it involves doing a binary search on one of the sets for each of the elements of the other set. This requires one of the arrays to be sorted. The sorting can *almost* be done in $O(n \log m)$, but there is a slight problem when $m$ is much bigger than $n$ (but I doubt you are interested in such technicalities).

$O(n+m)$ is possible, but this requires (to my knowledge) the arrays to be sorted. This can be achieved by walking through both sorted arrays simultaneously, repeatedly advancing the pointer into the array whose current element is lowest until you reach the end of either array or find an intersection.
> 2 votes

# Answer
There is a double binary search algorithm. It will only work is both lists are sorted. It is basically as follows.

1. Check the first, lowest number on each list. Compare the numbers to find which number is higher. Assume that higher number is in List A
2. Take that higher number and do a binary search for it in list B.
3. If found done.
4. If not found take the number above the last search location in list B For example, assume list A had a 5, and in list B you do a binary search and find 6 and 4 with no five in between. Take the 6 from list B.
5. Do a binary search for that value is list A.
6. If found done
7. If not found take the number above the last search location in list A.
8. Repeat steps 3–7 switching back and forth between lists.

That is the basic idea, if you want further information, let me know.
> 3 votes

---
Tags: algorithms, binary-search
---


# Question
Title: Complexity of finding binomial coefficient which equals to a number
Assume you are getting a number $m$ (using $O(\log m)$ bits in binary encoding).

How fast can you find (or determine such does not exist) $$n,k\in \mathbb N, 1\<k\leq\frac{n}{2}:{n \choose k}=m$$ ?

---

For example, given the input $m=8436285$, one may output $n=27, k=10$.

---

A naive algorithm for the problem would go over all possible values for $n$, and search for a value of $k$ which satisfies the property.

A simple observation is that there no need to check values of $n$ smaller than $\log m$ or larger than $O(\sqrt m)$. However (even if we could check only $O(1)$ possible $k$ values per $n$ value) this ends up in an inefficient algorithm which is exponential in the input size.

An alternative approach would be to go over the possible values of $k$ (it's enough to check $\\{2,3,\ldots,2\log m\\}$) and for each check for possible $n$ values. We can then use: $$\left(\frac{n}{k}\right)^k\<{n\choose k}\< \frac{n^k}{k!}$$

So for a given $k$ we only need to check $n$ values in the range $\[\sqrt\[\leftroot{-2}\uproot{2}k\]{m\cdot k!},\sqrt\[\leftroot{-2}\uproot{2}k\]{m}\cdot{k}\]$, Doing so using binary search (when $k$ is fixed, $n \choose k$ is monotonically increasing in $n$), this gives a polynomial algorithm running in $O(\log^2m)$.

This still seems inefficient to me and I guess that this could be solved in linear time (in the input size).

# Answer
> 1 votes
It is not true that $(n-k)^k\<{n\choose k}$. For example ${9\choose 2} = 36 \< 49 = (9-2)^2$.

I haven't (yet) found a subtle solution using arithmetic properties of the binomial coefficients, however I can suggest a somewhat bruteforce one if that helps :-)

You could, for each $k$, solve for $n$ by taking an initial guess (say $\sqrt\[k\]{k!\cdot m}$) and using an analytical method such as Newton-Raphson. You want to solve ${n\choose k} - m = 0$. The derivative of the left hand side with respect to $n$ is $(\psi(n+1)-\psi(n-k+1)){n\choose k}$ where $\psi$ is the digamma function, which is easy to compute.

The complexity of a Newton-Raphson search only depends on the complexity of computing the function and its derivative, and the number of digits required for the solution (in our case we just need the closest integer).

So overall for each $k$ the search should be $O(1)$ (assuming, as you seem to have done, that computing a binomial coefficient takes constant time), hence the total complexity for the algorithm using your bounds for $k$ would be $O(\log(m))$.

---
Tags: algorithms, combinatorics
---


# Question
Title: Cognitive Computing vs Artificial Intelligence?
Can anyone please tell me the difference between them? A brief definition of Cognitive Computing would appreciated.

Also how does cognitive computing relate to neural networks?

# Answer
> 6 votes
A brief definition would be:

> Cognitive computing is the simulation of human thought processes in a computerized model.

more detailed explanation:

> Cognitive computing involves self-learning systems that use data mining, pattern recognition and natural language processing to mimic the way the human brain works. The goal of cognitive computing is to create automated IT systems that are capable of solving problems without requiring human assistance.

Cognitive computing is used in A.I. applications. Therefore I think it can be concluded that Cognitive Computing is a subset of Artificial Intelligence.

Cognitive Computing systems may include the following ostensible characteristics:

1. Natural Language Processing
2. Machine Learning
3. Algorithms that learn and adapt
4. Vision-based sensing and image recognition
5. Spatial and contextual awareness
6. Reasoning and decision automation
7. Sophisticated pattern recognition
8. Neural Networks
9. Semantic Understanding
10. Noise Filtering
11. Common Sense
12. Robotic Control
13. Emotional Intelligence

So basically, you can say that a cognitive computing system might be trained by neural networks.

Sources:

1. http://www.cognitivecomputingforum.com/
2. http://whatis.techtarget.com/definition/cognitive-computing

---
Tags: terminology, machine-learning, artificial-intelligence
---


title: Structural induction over list

text:
# Question
Title: Structural induction over list
I want to prove that `unique(reverse(L)) = reverse(unique(L))` where L is a List.

List has the following constructors:
`[] : -> List`
`[e] : Element -> List`
`cons(e, L) : Element x List -> List`

I defined unique and reverse as follows:
`unique : List -> List`
`reverse : List -> List`

`unique([]) = []`
`unique([e]) = [e]`
`unique(cons(e, L)) = cons(e, unique(L)), if member(e, L) = false` `unique(cons(e, L)) = unique(L), if member(e, L) = true`

`reverse([]) = []`
`reverse([e]) = [e]`
`reverse(cons(e, L)) = append(reverse(L), [e])`

also,
`member : Element x List -> {true, false}`
`member(e, []) = false`
`member(e, [a]) = (e == a)` (true, if a is equal to e; false, if a isn't equal to e)
`member(e, cons(a, L)) = (e == a) V member(e, L)` (V is logical disjunction)

`append : List x List -> List`
`append([], L) = L`
`append([e], L) = cons(e, L)`
`append(cons(e, L1), L2) = cons(e, append(L1, L2))`

Both base cases are easy to verify.

**Induction hypothesis:** I assume `unique(reverse(L)) = reverse(unique(L))` is true

**Inductive step:** I have to prove that `unique(reverse(cons(e, L))) = reverse(unique(cons(e, L)))` is true

I consider two cases:

1. `member(e, L) = true`, then:
`unique(reverse(cons(e, L))) = unique(append(reverse(L), [e]))`
`reverse(unique(cons(e, L))) = reverse(unique(L)) = unique(reverse(L))`
Those are obviously true, but I don't know how to formally prove it (I can explain it in words, but that's not the point).
2. `member(e, L) = false`, then:
`unique(reverse(cons(e, L))) = unique(append(reverse(L, [e])))`
`reverse(unique(cons(e, L))) = reverse(cons(e, unique(L))) = append(reverse(unique(L)), [e]) = append(unique(reverse(L)), [e])`
I'm stucked here.

unique, reverse, append and member don't have to be defined that way, but they have to do the same thing.

# Answer
> 2 votes
I am not entirely sure that what you're trying to prove is right.

```
unique [] = []
unique (x : xs) = if x `in` xs then unique xs else x : unique xs

reverse [] = []
reverse (x : xs) = reverse xs ++ [x]

```

If we take xs = \[a, b, a, c\] then:

```
unique [a, b, a, c]
= { unique.2 }
if a `in` [b, a, c] then unique [b, a, c] else a : unique [b, a, c]
= { ... }
[b, a, c]

reverse [b, a, c] = [c, a, b]

reverse [a, b, a, c] = [c, a, b, a]

unique [c, a, b, a]
= { unique.2 }
c : unique [a, b, a]
= { unique . 2 }
c : [b, a]
= [c, b, a]

```

Hence, unique (reverse \[a, b, a, c\]) = \[c, b, a\] and reverse (unique \[a, b, a, c\]) = \[c, a, b\].

---
Tags: discrete-mathematics, induction, lists
---


# Question
Title: Does randomness make exponential difference?
Schwartz–Zippel lemma can solve the polynomial identity testing in expected poly-time. As far as I know, there is no deterministic poly-time algorithm for the problem, but we do not know if the problem is NP-hard or not, right? Is there any NP-hard problem that can be solved in expected poly-time using a randomized algorithm? What are the consequences if such a thing exists?

# Answer
> 5 votes
It is a common belief that P=BPP. This means that any randomized polynomial time algorithm can be derandomized. The idea of the proof is to use a deterministic pseudorandom number generator to supply the randomized algorithm random bits. Such a pseudorandom number generator exists, for example, if SAT takes exponential time to solve (roughly).

Polynomial identity testing is usually presented as a slightly different kind of problem (or rather as several different kinds of problems), but again the common belief is that one should be able to do it deterministically.

(As common beliefs go, some people disagree.)

---
Tags: np-hard, randomized-algorithms
---


# Question
Title: Which of $2^{\log_*n}$ and $\log\log n$ grows faster?
Function 1: $2^{\log\_\*n}$

Function 2: $\log(\log n)$

The first function is 2 to the log-star of $n$, the second function is log of log of $n$. What I need to know is which one is Big-Omega of the other one, which means, which one grows faster. How can I figure that out? I know the definition of log-star (iterative logarithm) but I don't know how to apply it in order to compare the given functions. Could you guys give some help?

Thank you in advance.

# Answer
Consider $n\_k=2^{2^{2^{\cdots}}}$, $k$ levels. Then $\log\log n\_k = 2^{2^{2^{\cdots}}}$, $k-2$ levels, while $2^{\log^\* n\_k} = 2^k$. Does this help?
> 4 votes

---
Tags: asymptotics
---


title: Couting Self dual functions

text:
# Question
Title: Couting Self dual functions
The Dual of a Boolean function $F(x\_1, x\_2, ..., x\_n)$, written as $F^D$ is the same expression as that of $F$ with $+$ and $.$ swapped. $F$ is said to be self dual if $$F=F^D$$

How can we count total number of self dual function with $n$ Boolean variables.

I know For $n$ variables total $2^n$ minterms or maxterms are possible and any boolean function can be expressed as combination of minterms or maxterms. But what else is required to count all self dual functions of $n$ variable.

# Answer
Using de Morgan's laws, we get a more useful characterization of self-dual functions: those are functions satisfying $\lnot F(x\_1,\ldots,x\_n) = F(\lnot x\_1,\ldots,\lnot x\_n)$. Suppose that you knew the value of a self-dual function on all inputs in which $x\_1$ is false. Can you recover the rest of $F$? Can you deduce the number of self-dual functions?
> 1 votes

---
Tags: boolean-algebra
---


title: Constructing Turing machines

text:
# Question
Title: Constructing Turing machines
I get the main ideas of Turing machines. But I can't construct a Turing machine to solve a given question.

The question I'm trying to solve is "Construct a Turing machine that recognises the set of all strings that contain an even number of $1$s."

How can I think about all the cases? Is there a way to do it?

# Answer
> 2 votes
It is simpler than what you think. You don't even need a Turing machine that writes to the tape.

Here is a Turing machine whose final state would be $YES$ if the string (in tape) contains an even number of 1's, and in $NO$ if the string contains an odd number of 1's, assuming the string marks its end with a #, and it starts from left to right.

Let $ M = (Q, Γ, Σ, δ, s, B, F)$ be a Turing Machine with the definition

$$Q = \\{read\_0,read\_1,YES,NO\\}$$

$$Γ = \\{1,0,\\#\\}$$

$$Σ = \\{\\}$$

$$F = \\{YES,NO\\}$$

$$s = read\_0$$

$$B=\\#$$

$δ$ is given by $δ\_{q\ t} = ( move \\,\ next\ stage)$ where $t$ is the tape symbol that it reads, and $q$ represents each state:

$$δ\_{read\_0\ 0} = (R,read\_0)$$ $$δ\_{read\_0\ 1} = (R,read\_1)$$ $$δ\_{read\_0\ \\#} = (0,YES)$$ $$δ\_{read\_1\ 0} = (R,read\_1)$$ $$δ\_{read\_1\ 1} = (R,read\_0)$$ $$δ\_{read\_1\ \\#} = (0,NO)$$

---

Basically what it does is that if it see $1$ it alters between $read\_0$ and $read\_1$ states. And if it is in $read\_0$ state and sees $\\#$, which means the string ended, it would go to the final state, $YES$. If it is in $read\_1$ and sees $\\#$ it would go to $NO$.

So if the string contains three $1$s, the states change in this way $$read\_0 \rightarrow read\_1 \rightarrow read\_0 \rightarrow read\_1 \rightarrow NO$$ implying that it doesn't contain an even number of 1s.

# Answer
> 0 votes
Do I understand correctly that you are looking for a formal definition of a TM (i.e. with transition function and such) and that you are working on the alphabet $\Sigma = \\{0,1\\}$?

Checking whether a string has an even number of 1s is equal to counting the number of 1s in it and testing it that number is 0 mod 2. So basically, you want to process the string and count between "sum is 0 mod 2" and "sum is 1 mod 2". Finite counting in TMs is easily done by using different states for each of the counting possibilites. In this case, you would have one state for "sum is 0 mod 2" and one for "sum is 1 mod 2".

Therefore, a TM that solves your problem could possibly work like this:

1. Start in state $q\_0$
2. If the current state is $q\_0$ and the current symbol is $1$, change to state $q\_1$, else don't change state. Continue with step 4
3. If the current state is $q\_1$ and the current symbol is $1$, change to state $q\_0$, else don't change state. Continue with step 4
4. Move the head right
5. If the current symbol is Blank, go to step 6. Otherwise, go to step 2.
6. In state $q\_i$, write $i$ and change to final state $\overline{q}$

Just a remark: To do infinite counting (e.g. you want the TM to output the number of 1s in the input string in binary), you would usually introduce a second tape on which you save the sum of the counted 1s so far.

---
Tags: turing-machines
---


title: Spandex knapsack?

text:
# Question
Title: Spandex knapsack?
I'm going camping. While I'm away, I plan to eat only s'mores, which consist of 20% chocolate, 50% marshmallow, and 30% graham cracker. I did a thorough clean-out of my pantry, which revealed multiple packages of each of these ingredients in various sizes.

I'll need at least 5kg of food to get me through the weekend, but I'm willing to carry up to 10kg of weight if it means I can achieve a more perfect balance of chocolate, marshmallow, and graham cracker. (My camping companions like s'mores, too.)

I really don't care about the weight, as long as it's in the range of 5-10kg. But the farther away from a 20/50/30 split, the sadder I'll be. :-(

I'm willing to devote *some* computational resources to this problem, but not too much; the weekend will be here before you know it. Can Computer Science help me?

# Answer
This could be formulated as an ILP instance that searches for a feasible solution under your ratio constraints. However, you want to maintain the ratio as best as possible and not necessarily require it; therefore, we attempt to minimize the distance from this ratio by employing a Lagrangian relaxation of the constraints.

In this formulation $x\_c$ is the 0-1 variable over each chocolate (similarly for marshmellow and graham cracker). $x\_t$ is the integer variable that holds the number of selected items.

$$\min \lambda\_c (\sum\_c w\_c x\_c - .2 x\_t) + \lambda\_m (\sum\_m w\_m x\_m - .5 x\_t) + \lambda\_g (\sum\_g w\_g x\_g - .3 x\_t)$$ $$s.t. \sum w\_c x\_c + \sum w\_m x\_m + \sum w\_g x\_g \leq x\_t$$ $$\sum w\_c x\_c + \sum w\_m x\_m + \sum w\_g x\_g \leq 10$$ $$\sum w\_c x\_c + \sum w\_m x\_m + \sum w\_g x\_g \geq 5$$ $$ x\_c \in \\{0,1\\}, x\_g \in \\{0,1\\}, x\_m \in \\{0,1\\}$$ $$x\_t \geq 0$$
> 1 votes

---
Tags: optimization, knapsack-problems
---


# Question
Title: Understanding polynomial equality testing using randomized algorithms
A file is downloaded from a server and is represented as $a = \\{0, 1\\}^n$. The server has that file as $b = \\{0, 1\\}^n$. We want to ensure a degree of certainty that $a=b$, using a randomized algorithm.

So below is the procedure referenced from this lecture pdf .

I can't get my head around why some of the steps are necessary. So these are my questions.

1) In step 1, I believe $M$ should be chosen as $c \cdot n$, since if $M = 2^{n-1}$, it would defeat the purpose and we end up with $O(n)$, instead of $O(\log n)$; right ?

2) In step 2, we are picking a prime. Why is a prime necessary ? why can't we simply choose $M$ ?

3) In steps 3 & 4, we pick a random value $r$ and compute $a(r)(\mod p)$. Why can't we simply compute $a\_{dec} \mod p$ ? where $a\_{dec}$ is the decimal representation of the binary string $a$. Then, we could simply compare $a\_{dec} \mod p$ and $b\_{dec} \mod p$.

If you could lay down an example of how this works, it would be much appreciated. Let's say we have $a = 101100$ and $b = 111100$, how do we go about comparing them using this algorithm ?

Thanks.

# Answer
> 1 votes
Your lecture note contains the answer to your questions. Here are some hints.

> 1) In step 1, I believe $M$ should be chosen as $c \cdot n$, since if $M=2^n − 1$, it would defeat the purpose and we end up with $O(n)$, instead of $O(\log n)$; right?

Yes. That is exactly why we choose to work over a finite field (modulo a prime $p$) instead of over the whole integers. We do all calculations $\bmod p$, which guarantees that we never need more than $O(\log p)$ bits.

> 2) In step 2, we are picking a prime. Why is a prime necessary ? why can't we simply choose $M$?

We have decided to work over a finite field modulo a prime $p$. $p$ is used in step 4) and step 5).

> 3) In steps 3 & 4, we pick a random value $r$ and compute $a(r)(\bmod p)$. Why can't we simply compute $a\_{dec} \bmod p$?

We are thinking of a string as a polynomial: $$a(x) = \sum\_{i=1}^{n} a\_i x^i$$ and evaluate it at $r$. After all, we are doing *Polynomial Identity Testing*. However, $a\_{dec}$ has nothing to do with $r$ and polynomial (evaluation).

---
Tags: algorithms, probability-theory, randomized-algorithms, probabilistic-algorithms
---


# Question
Title: How to correctly contract an edge in a network?
Assuming an adjacency list as data structure of a directed Graph, it is not completely clear to me how "contraction of an edge" is defined.

Let me cite the definition I do have at hand:

Source: JAMES B. ORLIN - A FASTER STRONGLY POLYNOMIAL MINIMUM COST FLOW ALGORITHM, Section 4.1. Contraction

> \[...\] any edge, say $(k, \ell)$, can be contracted into a single node $p$. The contraction operation consists of: letting $b(p) = b(k) + b(\ell)$ and $e(p) = e(k) + e(\ell)$; replacing each edge $(i, k)$ or $(i, \ell)$ by the edge $(i, p)$; replacing each edge $(k, i)$ or $(\ell, i)$ by the edge $(p, i)$; and letting the cost of an edge in the contracted network equal that of the edge it replaces.\[...\]

$b$ and $p$ are functions defining values for certain properties of a node; their meaning is unimportant for understanding contraction.

Consider the following graph described in "adjacency speak", where e.g. node 0 has an edge to the nodes 1, 2 and 5; node 5 has no outgoing edges; node 3 has an edge to node 4 and so on...

```
0 -> 1, 2, 5
1 -> 2, 3
2 -> 1
3 -> 4
4 -> 5
5

```

Now I want to contract the edge $(1,2)$. Note that there is an edge $(2,1)$, too. Should the application of the contraction operation yield the following directed graph, where the newly introduced node $p$ has the id $6$?

```
0 -> 6, 5
3 -> 4
4 -> 5
5
6 -> 3, 3, 5, 6 # Note that we got two edges from node 6 to node 3.
                # Note that we also have an edge from 6 to 6, i.e. a loop.

```

Thanks a lot!

# Answer
> 3 votes
The very next sentence (!) of Orlin's paper says

> We point out that the contraction operation may lead to the creation of multiple arcs, i.e., several arcs with the same head and tale nodes.

In some contexts, you might want to replace multiple arcs between the same two nodes with a single arc whose weight (or capacity or whatever it's being called) is the sum of the weights of the original arcs; in other contexts, it might make more sense to keep them separate. Orlin is keeping them separate.

For example, if the arcs represent trading relationships between companies, it makes sense to merge the arcs: if companies $A$ and $B$ both sell to $C$ and $A$ and $B$ merge, it makes more sense to say that $C$ is a customer of the new company once, with a single arc, than to say that it's a customer twice, by having two arcs. On the other hand, if arcs represent roads between towns and two towns merge, it makes sense to keep the arcs separate: if there's a road from each of $A$ and $B$ to $C$ and $A$ and $B$ merge, there are still two roads from the merged town to $C$.

So, contracting the arc $(1,2)$ into a new node $6$ has the following effects:

* it converts the arc $(1,2)$ into the loop $(6,6)$;
* it converts the arc $(2,1)$ into a second copy of the loop $(6,6)$;
* replaces the arcs $(0,1)$ and $(0.2)$ with *two* copies of $(0,6)$;

---
Tags: graphs
---


# Question
Title: Doubt in derivation of a proof in Information Theory
In my class we were trying to derive Shannon's Source Theorem, first by proving the equivalent form in a weaker version.

The question is: Consider a biased coin with probability of heads $p \geq \frac{1}{2}$.We want to transfer this information with the code of minimum expected length.

To prove this, we can construct a code such that for any $\epsilon $, for large $n$, there exists a code such that average code length is less than $(1+\delta)nH(p) $ and also the lower limit of the code length is $(1-\delta)nH(p) $

We tried to prove it by first getting the inequalities $$ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} \leq 2^{nH(p)}$$ Both these inequalities are easy to derive. The problem comes with deriving the lower limit we try to prove that in an optimal code the length of the lower probability event is greater than equal to higher probability code, and then try to find the length of one of the events of higher probability an conclude by showing that since the lengths of events with lower probability is going to be more than this the expected length is more than $(1-\delta)nH(p) $

Hence, since $ \frac{2^{nH(p)}}{n+1}\leq{n \choose np} $, one of the events containing $np $ heads will be of length greater than $log\_{2}\frac{2^{nH(p)}}{n+1}$ . That is $ nH(p) -\log\_{2}(n+1) $ . However to complete this part of the proof I need to prove the probability of all events with less than $np$ heads is a constant. Is it true for a binomial distribution that for an event with probability of success greater than $c$ where $c$ is some constant independent of $p$? By proving this we can prove that the expected length of the code is greater than $ c \times (nH(p) -\log\_{2}(n+1)) $ which comes up to $(1-\delta)nH(p) $

# Answer
> 2 votes
For fixed $p$, the central limit theorem shows that $$ \begin{align\*} \lim\_{n\to\infty} \Pr\[\mathrm{Bin}(n,p) \leq np\] &= \lim\_{n\to\infty} \Pr\[\tfrac{1}{n}\mathrm{Bin}(n,p) \leq p\] \\ &= \Pr\[N(p,\tfrac{p(1-p)}{n}) \leq p\] \\ &= \frac{1}{2}. \end{align\*} $$ In this particular case you can get quantitative bounds in several ways, for example using the Berry–Esseen theorem or large deviation theorems such as the Chernoff bound.

---
Tags: information-theory
---


# Question
Title: Defining a new (informal) operator in CTL
If you were given a "new operator" **Wh** and a formula *a* **Wh** *b* meaning that *a* holds for at least as long as *b* does (in all executions). How would you define this operator in CTL? This is an exercise question in the book "Principles of Model Checking" (page 303) if anyone has a copy.

My first thoughts are that I'll definitely need to use the "FOR ALL" quantifier, but I'm not sure where to go from there. So I want to know the thought-process that I should have when dealing with these types of questions more than anything. What I'm looking for is for someone to perhaps give me a walk-through or a very quick guide to solving questions like these.

Thanks in advance for any input.

# Answer
> 2 votes
You seem to be stuck, so here is the answer:

You want $a$ to hold for at least as long as $b$ does. The alphabet consists of $2^{\\{a,b\\}}=\\{\emptyset, \\{a\\},\\{b\\},\\{a,b\\}\\}$.

Rephrasing the condition, it means that $\\{b\\}$ cannot appear before either $\\{a\\}$ or $\emptyset$ have appeared. Indeed, this is the only violation of the condition.

So once $\\{a\\}$ or $\emptyset$ hold, you're in the clear. You just need to make sure that *until* then (sounds familiar?), $\\{a,b\\}$ holds.

Thus, you have $$a\ Wh\ b\equiv (a\wedge b)U(\neg b)$$

---
Tags: logic, model-checking, computation-tree-logic
---


# Question
Title: Finding the Best Fitting Plane Given a Set of 3D Points
Suppose that we have $n$ points in 3D.

I want to find a plane $ax + by + cz + d$ such that sum of all the orthogonal distances to the plane is minimum.

I read this article. However, I need an algorithmic solution.

So far, this answer from SO was the simplest one. However, this solution projects the points onto $z=0$ plane all the time.

Could you help me to write the algorithm? I'll code it in Java.

# Answer
This is exactly the problem that PCA (principal component analysis) solves. So, use PCA -- that provides an algorithmic solution to this problem. See this explanation over at Statistics.SE for an explanation of why PCA solves this problem.

\[Least squares fitting is almost a solution to this problem, except that it doesn't minimize the orthogonal distance -- it minimizes the distance along the $y$ axis, or any single axis you might pick.\]

---

If for some reason you didn't want to use PCA, you could frame this as a mathematical optimization problem (the objective function is the total orthogonal distance) and then use any standard optimization technique -- e.g., gradient descent -- to find an approximate optimum.
> 1 votes

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


# Question
Title: Why we use context-free grammar for parsing?
Why we use context-free grammar for parsing? Why not regular expression and not context-sensitive grammar?

# Answer
> 7 votes
Because regular expressions are too weak and context-sensitive languages are too difficult to parse. More specifically, regular expressions can't specify that the brackets in your program match up; determining whether a string matches a context-sensitive language is **PSPACE**-complete (so probably takes exponential time).

---
Tags: compilers, parsers
---


title: Hardness of 3SAT-k

text:
# Question
Title: Hardness of 3SAT-k
According to these scribe notes (and a paper), 3SAT-5 is NP-hard. The problem is defined to be: given a 3SAT formula, each variable occurs in at most 5 clauses. It is also proven that 3SAT-4 is NP-hard.

What is the computational complexity of 3SAT-$k$ for $k \le 3$?

# Answer
> 4 votes
The paper "A Simplified NP-Complete Satisfibility Problem" given as a reference in the scribe note has actually answered your questions.

> Theorem 2.4: Every instance of $r,r$-SAT is satisfiable.

This implies that 3SAT-$3$ is satisfiable.

In addition, Section 3 gives polynomial algorithm for the 2-occurrence case for any $m$-SAT instances ($m \ge 2$).

This implies that 3SAT-$\le 2$ is polynomially tractable.

---
Tags: np-complete, np-hard, satisfiability, 3-sat
---


# Question
Title: Can a Minimum Possible Efficiency be proven?
Given a problem, is it possible to prove what the best worst-case efficiency of an algorithm to solve this problem would be?

For example, lets take the problem of sorting an array.

Many of the simpler sort algorithms have a worst-case efficiency of $O(n^2)$ such as Quick Sort and Bubble Sort. However, there are other algorithms such as Timsort and Smoothsort that have $O(n \log n)$, which is more efficient.

No other algorithm (to my knowledge) has been able to sort an array more efficiently than $\Theta(n\log n)$. Is it possible to prove that no other algorithm exists that is more efficient?

If there is a way to prove for sorting algorithms if an algorithm exists that is more efficient, does this apply to other problems as well?

# Answer
There are certainly ways to show that certain algorithms must take a certain amount of time or certain data structures require a certain amount of space. One common way is to use information theory.

An unsorted array is a permutation of the sorted array. There are $n!$ possible permutations. The job of sorting, in an information theoretic sense, is to discover precisely which permutation it is.

To transmit a number between $1$ and $m$ requires transmitting $\log\_2 m$ bits of information. To transmit a permutation of $n$ elements, therefore, requires $\log\_2 n!$ bits of information. By Stirling's approximation, this turns out to be $n \log\_2 n + O(\hbox{low order})$ bits.

A binary comparison operation discovers one bit of information. It follows that any sorting algorithm which only uses a binary comparison operation must perform at least $n \log\_2 n + o(n \log n)$ comparisons. If we assume that a comparison takes a constant amount of time, that means that the sort must take at least $\Omega(n \log n)$ time.

A radix sort could beat this by discovering more than one bit of information per query.

A similar argument shows that binary search is optimal. You are trying to find a number between $1$ and $n$, which means discovering $\log\_2 n$ bits of information. If your query operation returns one bit of information, you need at least $\log\_2 n$ queries to find an element.

It's a similar story with space usage. Suppose that you need to store a permutation in memory. By an identical argument, this requires at least $n \log\_2 n + o(n \log n)$ bits of storage. Since you need $\log\_2 n$ bits to store an integer between $1$ and $n$, you essentially can't do any better than storing $n$ integers.
> 11 votes

# Answer
Sorting, in fact, has been proven to take at least $O(n \log n)$ time if the sort is based on comparisons. For integers of fixed size, there are faster methods (radix sort).

However, sorting is one of the rare problems where this has been done. In general, we don't know lower bounds for the time complexity of most problems. For example, if we know that $O(2^n)$ was a lower bound for $NP$-complete problems, then we'd know that $P \neq NP$. But no such result has been proven, so $P$ vs $NP$ remains a mystery.

For problems in general, there is no algorithm which can take in a representation of a problem and return a lower bound on its time complexity. This is because the set of such complexities would be an index set: that is, it represents a property of languages (problems), not of algorithms. There's a result called Rice's Theorem which says that any such sets are undecidable.
> 7 votes

# Answer
In general this is possible, but it is **crucial** you specify the model of computation when doing so. A classic example well-known is the $\Omega(n \log n)$ bound on sorting in the decision tree model. To circumvent the sorting lower bound proven in the decision tree model, you must not perform comparisons.

Another example is the cell probe model. In addition to the examples on Wikipedia, you can look at e.g. Fredman-Saks (STOC'89). This is a strong model; if you'd like to beat a bound with an algorithm, you must not access memory.
> 2 votes

---
Tags: asymptotics, proof-techniques, efficiency
---


# Question
Title: Can approximation help find the exact answer?
Lets assume we have an array with 100 numbers and we want to find how many '1's there are. Best solution will be reading every numbers and counting. Now we get a hint that there are 50,51 or 52 '1' in the array, can this information help us count the '1's somehow?

What bothering me here is that we have a lot of information about the array but it still doesn't appear to help the find the amount of '1's.

# Answer
> 1 votes
Assume that someone hints you there are 50,51 or 52 '1's then as a first optimization (memory wise) you may want to use a 2-bit counter and count $\mod 3$. That said, you'll still need to go over the entire array to get the right answer in the worst-case)- assume you read 99 entries and found 51 '1's. How can you tell if there are 51 '1's or 52, without reading the last number?

# Answer
> 1 votes
In the worst-case, (maybe by an adversary argument), you still have to check all the numbers to determine the number of $1$.

A possible optimization: if you are *really* lucky that you have encountered `52` $1$s \[or `50` $\lnot 1$s (not $1$)\] *before* reaching the end of the array, you can conclude that there are totally `52` \[or `50`\] $1$s in the array.

# Answer
> 0 votes
Looking at your example first let's assume that what you mean by 'approximation' in your title question is to have some knowledge for the solution but not the full solution (which comes either by means of approximation or other means).

So, yes, having some knowledge about the solution does help us find the exact answer. Here is how and why using your example.

Knowing nothing about the solution would have us as you say look at all 100 elements to count 1's. But knowing that the 1's are either 50, 51 or 52 in the case of 52 we do not have to read all 100 elements, we can stop at the 52nd 1 found without checking any further elements. This helps us because it improves our overall average complexity to reading 92.32 elements instead of 100.

So, in conclusion, while having some knowledge about the solution does not provide any help using worst case complexities (i.e. considering the worst input case scenario) it does provide help generally i.e. when considering each input as likely or in the average case.

---
Tags: approximation, counting
---


title: conversion to base-R numbers

text:
# Question
Title: conversion to base-R numbers
I am reading Algorithms 4th edition by Robert Sedgewick and am stumped at a particular problem. On page 460 of the book the author is describing a technique to hash strings and use prime numbers for modular hashing. Starting from the fourth line:

```
 If R is greater than any character value, this computation would
 be equivalent to treating the String as an N-digit base-R integer,
 computing the remainder that results when dividing that number by M.

```

Where the algorithm being used to hash a N-character long String is:

```
int hash = 0;
for (int i = 0; i < s.length(); i++)
   hash = (R * hash + s.charAt(i)) % M;

```

How does the above algorithm result in a base-R integer?

Here M and R are integers (random) and s is the string of length N.

I am assuming that by the 'above computation' the author means the computation within the parentheses =\> R\*hash + s.charAt(i)

# Answer
> 0 votes
The iteration results in :

(R^2\*C + R^1\*B + R^0\*A + some constant)mod(M) for the string ABC, the value inside the brackets is a base 16 representation of CBA plus some constant value.

---
Tags: hash, hash-tables, primes, base-conversion
---


title: Lost in a "one directional" concert

text:
# Question
Title: Lost in a "one directional" concert
You and a friend lost each other on the line to a concert, and neither is sure which of you is further ahead. Formally, each is at some integer coordinate and may only walk towards a higher coordinate or stay in place.

Assuming you and your friend are following the exact same algorithm (and no, you may not say "if (name=="R B") do something :) ), and the initial distance between the two of you was $x$ (which is not known to you).

> **What is the algorithm which minimizes the expected walking distance till you and your friend meet?**

---

You may assume both your friend and yourself are moving in the same constant speed.

---

An example simple algorithm would be something like:

> 1. At stage $n$ (starting from $0$):
>
> * Walk $3^n$ steps to the right w.p. $\frac{1}{2}$ or wait $3^n$ time units otherwise.

To see this algorithm makes the friends meet with probability 1 consider what happens at stage $(\log\_3 x+1)$. Even if the friend that was $x$ step ahead always walked and the other always stayed in place, the distance between the two would be: $$x+1+3+9+\ldots+3^{\log\_3 x}=2x+\frac{x-1}{2}\leq 3x$$

Therefore, at the $\log\_3 x+1$ iteration, the friend which chooses to walk will cover distance of $3^{\log\_3 x+1}=3x$, hence with probability $\frac{1}{4}$, the friend which is behind will catch up and they will meet.

---

A simple optimization (to reduce walking distance) would be, instead of walking $3^x$ steps, walking $c^x$ steps, where $c$ is given by: $$2+\frac{1}{c-1}=c$$

Hence the optimal $c$ **for this algorithm** is $c=\frac{3+\sqrt 5}{2}\approx 2.618$

Unfortunately, while this algorithm guarantees that the friends will meet with probability 1, the expected walking distance is infinite, which is something I'd like to avoid if possible.

> **Is there a more efficient algorithm?**

# Answer
> At step $k$, draw a random number $q$ uniformly between $1$, $2$, and $3$.
>
> * if $q = 1$, walk $2^{k-1}$, wait $2^{k+1}$, walk $2^{k-1}$
> * if $q = 2$, wait $2^{k-1}$, walk $2^{k-1}$, wait $2^{k}$, walk $2^{k-1}$, wait $2^{k-1}$
> * if $q = 3$, wait $2^k$, walk $2^k$, wait $2^k$

At each step $k$, both friends will walk $2^k$ steps. If $k \< \log\_2(x) + 1$, they won't meet during that step, however if $k \>= \log\_2(x) + 1$, they will meet if and only if they don't draw the same number. The probability that this doesn't happen is only $1/3$ at each step.

Hence the expected walking distance is (bounded above by):

$$2\left(\sum\_{k=0}^{\lceil\log\_2(x)\rceil}2^k+3^{\lceil\log\_2(x)\rceil}\sum\_{k=\lceil\log\_2(x)\rceil+1}^{\infty}\left(\frac{2}{3}\right)^k\right)$$

Which is finite, and equal, if my napkin maths are to be trusted, to $2^{\lceil\log\_2(x)\rceil+3}-2 \le 16x$.

By the way, if $d$ is the random variable representing the distance walked, we still have that $\forall D\>0, \mathrm{P}(d\>D) \> 0$, i.e. the distance is unbounded and can end up being arbitrarily high. Luckily this probability vanishes fast enough to ensure that the infinite sum $\sum\_{D=0}^{\infty}\mathrm{P}(d=D)\cdot D = \mathbb{E}\[d\]$ converges. Having a finite upper bound for $d$ is a much stronger property and I reckon it's not possible to find a solution satisfying it.
> 4 votes

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: How to do high performance string matching when comparing unordered sets of tokens
This is the problem:

I have some strings stored in the database. Each of the strings can be seen as a set of tokens separated by comma with no repetition (I mean a token cannot appear more than one time in a string).

I want to know if a new string matches any of them without taking token order into account.

The metric I think about is something like this (comparing two strings at the time, this is the first thing that came to my mind when trying to solve the problem and don't know if it is already used), a matching percentage calculated like this:

```
Match_Metric(A, B) = number_of_matched_tokens(A, B) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100.

```

Example:

```
String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"
String 3: "aab, cde, ghi, abc, adc, dca"
String 4: "aab, cde, ghi, abc, adc, dca, rrrm, a"

1 vs 2 = 0%
1 vs 3 = 100%
1 vs 4 = 75%

```

What I am trying to avoid is to perform a one to one comparison between tokens, but I am finding that other techniques like edit distance won't give me an exact match in the case of 1 vs 3 unless I first order the tokens.

The problem can be extended to do a string search within the tokens, for example:

```
String 1: "abc, cde, ghi, adc, dca, aab"

String 2: "cd, r, a, x"

```

As "d" appears in one token in 2 and three tokens in 1, that can affect the metric. In this case an approximate string matching technique such as "edit distance" would be useful but in a token versus token approach. The formula would be more complicated in this case, instead of having an integer representing the number of matched tokens it would be a fraction number and could be calculated like this:

Comparing two tokens at the time one from the string A and one from the string B:

```
token_match(a,b) = 1 - edit_distance(a,b) / length_of_largest_token(a,b)

```

So the general metric would be:

```
String A = {a0, ..., an}
String B = {b0, ..., bm}

i = {0, ..., n}
j = {0, ..., m}

Match_Metric(A, B) = sum(token_match(ai, bj)) / max_number_of_tokens_in_any_of_two_strings(A,B) * 100

```

Any ideas on what technique/algorithm is more broadly adopted/used for this problem?

# Answer
> 2 votes
So you want to use the Jaccard index as your metric of similarity. Well, the Wikipedia page for the Jaccard index (and which I linked to in the comments above) already has some hints on methods for finding close matches, more efficiently than comparing all pairs. For instance, you can use locality-sensitive hashing. Hint for the future: you might want to do more research in the future based on feedback from folks, as locality-sensitive hashing was already suggested in the comments and a relevant Wikipedia page was also mentioned in the comments.

If tokens are not too common, there's another alternative method you could also try. You could build an inverted index: an index that, for each token, lists all of the strings that contain it. Now given a new string S, it's easy to enumerate over all of the tokens in it, look each one up in the inverted index, find all other strings that share at least one token in common with S, compute the similarity between that string and S, and keep the best one. As long as no string contains too many tokens and no token is present in too large a fraction of strings, this will perform better than all-pairs comparison.

---

Your "extended" problem is different in nature and would probably be better asked as a separate question. It might be a much harder problem.

---
Tags: search-algorithms, search-trees, matching, search-problem, string-metrics
---


# Question
Title: Rounding errors when converting floats to integers
Is it possible to have a rounding error when you convert a floating point number which can only be in increments of 0.01 to an integer by multiplying by 100 first? I would think that the lack of precision in representing floating point numbers is so small that it would never cause a rounding error when you only have to worry about 0.01 increments.

# Answer
It depends on :

* the range of your input numbers
* the FP type, typically IEEE single (32bits, 23bits precision) our double (64bits, 52bits precision)
* The rounding mode, which is almost always "round to nearest even"

0.01 ≈ 7bits, add 3 bits for correct rounding, so around 13 bits remains with single precision, which give a range around ≈ ±10000.

\[Well, I'm too lazy to give precise answers. The problem with FP is that every operation can slightly affect the precision, as well as the way the program is compiled and the target architecture, with or without FMA (fused multiply-add), for example.\]
> 1 votes

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


title: Example of a boolean function

text:
# Question
Title: Example of a boolean function
Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?

# Answer
> 2 votes
Yes. Using the convention that inputs and outputs are $\pm 1$, then the function is $$ \frac{a(x+y)+b(x-y)}{2}. $$ You could have found this function using exhaustive search – there are only $2^{16}$ functions on $4$ variables.

---
Tags: complexity-theory, boolean-algebra
---


# Question
Title: Longest Common Subsequence Via Dynamic Programming
I read the wikipedia page on the Longest Common Subsequence problem to understand the LCS Table approach, but it seems to result in different solutions given different orders of the original sequences. For example, the traceback table generated here is correct, since the longest common subsequence of AGCAT and GAC has a length of 2:

```
   |A  G  C  A  T
---+-------------
  G|0  1  1  1  1
  A|1  1  1  2  2
  C|1  1  2  2  2

```

From what I understand of how it's supposed to work, the length of the LCS should appear in the bottom right cell.

But using the same method for generating the table, which you can find here, if you rearrange the letters you get an incorrect solution.

```
   |A  A  G  C  T
---+-------------
  C|0  0  0  1  1
  G|0  0  1  1  1
  A|1  1  1  1  1

```

Length of the LCS shouldn't have changed, the bottom right value is no longer 2.

Is my question clear enough? Am I simply following the method incorrectly? From what I understand, the order of the original sequences shouldn't matter.

# Answer
Your question is clear and you are performing the method correctly, as far as see.

But it seems to be a misunderstanding about what the problem solves about strings. The *longest common subsequence* problem is about find out a **subsequence** of characters in the case of string, not necessary consecutive like substrings.

By example, some subsequences of `AAGCT` are: `AG`, `AT`, `ACT`, `AGT`
> 3 votes

---
Tags: dynamic-programming
---


# Question
Title: How do I prove a certain upper bound on the runtime of a probabilistic 2-SAT solver?
As a *homework* we had to prove a set of upper bounds on a given probabilistic algorithm to find a satisfying assignment for a satisfiable 2-CNF formula. The problem is reproduced below. I'm sorry for all the incorrect language; English is not my native language and scientific language is especially difficult for me.

> Observe the following algorithm:
>
> > **input:** A 2-CNF formula $F(x\_1,\dots,x\_n)$ with $n\ge1$ where each clause contains two literals.
> >
> > 1. Choose an arbitrary assignment $a$ for $x\_1,\dots,x\_n$
> > 2. **while** $F(a)=0$ **do**
> > 3. select a clause $C$ from $F$ with $C(a)=0$
> > 4. select a literal $l$ from $C$
> > 5. flip the value of $l$ in $a$
> >
> > **output:** $a$
>
> Let $F$ be a 2-CNF formula in $n$ variables (let each clause have two literals without loss of generality) and let $h$ be an assignment that satisfies $F$. Show that the expected runtime of the aforementioned algorithm is bounded above by a polynomial.
>
> *Hint:* Show that the following bounds for the expected number of loop iterations $t(i)$, where $i$ is the number of variables in which the initial assignment $a$ differs from $h$, hold:
>
> 1. $t(0)=0$ and $t(n)\le t(n-1)+1$,
> 2. $t(i)\le1+\frac12t(i-1)+\frac12t(i+1)$ for $i=1,\dots,n-1$,
> 3. $t(i)\le i(2n-i)$ for $i=0,\dots,n$.

It was easy for me to prove upper bounds (1) and (3), where (3) was proved using (1) and (2), but I wasn't able to prove (2). In fact, I believe that (2) might be incorrect.

The idea behind (2) is that when a clause $C$ is chosen in step 3, either one or both literals in $C$ are assigned incorrectly (i.e. not like in $h$) because if both were assigned like in $h$, $C(a)=1$ and $C$ would not have been chosen. Thus, the probability $P$ for increasing the number of correctly assigned literals is greater or equal to $0.5$.

Boundary (2) would work for a probability of exactly $0.5$, but I don't see how this follows. If $t(i)$ would be monotonous, this would be easy to see, but $t(i)$ might not be monotonous. For instance, construct a 2-CNF formula where $h$ and $\bar h$ (where $\bar h$ is $h$ with the value of all literals flipped) are the only satisfying assignments. Obviously, $t(0)=t(n)=0$ and $t(i)\>0$ for all $i=1,\dots,n-1$.

Can anybody help me with this proof? I handed in the assignment last Thursday without a conclusive proof for (2), but it bothers me that I was unable to find a solution for (2).

# Answer
Denote the probability for increasing from $i$ to $i+1$ by $P(i \to i+1)$ and denote the probability for decreasing from $i$ to $i-1$ by $P(i \to i-1)$.

Consider an assignment $a$. Either one or both literals in the chosen clause $C$ are assigned incorrectly.

*Case 1) Only one literal in $C$ is assigned incorrectly:* In this case, the algorithm choose a literal $l$ from $C$ randomly. The chances for increasing or decreasing are equal.

*Case 2) Both literals in $C$ are assigned incorrectly:* Decreasing must happen. (Recall that $i$ denotes the number of the *differences*.)

Therefore, $P(i \to i-1) \> P(i \to i+1)$, and $P(i \to i-1) \> 0.5, P(i \to i+1) \< 0.5$.

---

~~Because $t(i-1) \le t(i) \le t(i+1)$, so we have the *upper bound* by a little relaxation:~~

**Correction according to "Ref" below:** Consider a stochastic process (denoted $X$) $X\_0, X\_1, X\_2, \ldots$ (not necessarily a Markov Chain) over state space $\\{0, 1, \cdots, n \\}$. The state $i$ here corresponds to the difference $i$.

The randomized algorithm aims to head to the state $0$ (possibly not monotonically). Although the algorithm could terminate before $X$ reaches $0$ if it finds another satisfying assignment than $h$, but we consider the worst case in which the algorithm only stops when $X\_i = 0$. Also notice that $h$ here is arbitrary (meaning that the analysis is applicable to any satisfying assignment argument $h$; hence the worst case.)

Now we have

$$P(X\_{i+1} = 1 \mid X\_i = 0) = 1;$$ $$P(X\_{i+1} = j+1 \mid X\_i = j) \< 0.5, \quad P(X\_{i+1} = j-1 \mid X\_i = j) \> 0.5 \quad (1 \le j \le n-1).$$

Consider the following Markov Chain (denoted $Y$) $Y\_0, Y\_1, Y\_2, \ldots$: $$Y\_0 = X\_0;$$ $$P(Y\_{i+1} = 1 \mid Y\_i = 0) = 1;$$ $$P(Y\_{i+1} = j+1 \mid Y\_i = j) = 0.5, \quad P(Y\_{i+1} = j-1 \mid Y\_i = j) = 0.5 \quad (1 \le j \le n-1).$$

The process $Y$ can be regarded as a *pessimistic* version of $X$ because $X\_i$ which *decreases* at the next step with probability $\> 0.5$ in $X$ now *decreases* with probability exactly 0.5 in $Y$.
We are only interested in the case of $X$ reaching $X\_0$ by decreasing.

> Therefore, the expected time to reach $X\_0$ starting from any state is *larger* for $Y$ than for $X$.

*NOTE:* This is quite intuitive; however, the formal proof of this statement will involve some advanced techniques on Markov Chains. I have posted a follow-up problem at math.se).

Taking the place of $X$ by $Y$, we get the upper bound $$t(i) \le 1 + \frac{1}{2} t(i−1) + \frac{1}{2} t(i+1)$$

---

Ref: Section 7.1.1 of the book "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" by Eli Upfal et al. (2005)
> 1 votes

---
Tags: satisfiability, probabilistic-algorithms
---


# Question
Title: Finding $k$ claws ($K_{1,3}$ bipartite graphs) in a graph?
Usually questions deal with claw-free graphs, but suppose we are given a graph $G$ and there are $k$ vertex-disjoing claws in the graph, how can we derive a randomised algorithm using color coding to find them. My intuition is to approach this with $k$ colors, but not really sure how to start it. Could someone give me some hints and ideas on how to approach this?

# Answer
> 2 votes
Finding vertex-disjoint copies of a subgraph $H$ in a graph $G$ is known as *Graph Packing*.

You could use Divide and Color to find the claws in $O^\*(4^k)$, also deterministically (look for Chen et al. construction of universal set for derandomization).

---
Tags: graphs, randomized-algorithms, bipartite-matching, colorings
---


# Question
Title: Why do we care about random Boolean SAT formula?
I've been looking for a reference for the above question.

As far as I know the answer is:

If we can make a solver that is efficient for all randomly generated instances, it should be efficient for any instance.

i.e. if we make a solver that doesnt rely on any inherent structure, it will always be efficient.

Is this correct? Either way, does anyone have a reference to a paper I can cite for the answer.

# Answer
> 9 votes
If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in practice (meaning they are structured differently). For instance, you can read about the phase transition in random $k$-SAT: depending on the clause-to-variable ratio, an instance can be easy (not constrained enough, or too constrained) or hard (in some sense critically constrained). This phenomenon is rather fascinating in itself.

You can always argue that if you have a solver that does not exploit any structure of the input and is always rather magically efficient, much of the theory we have developed around SAT is useless. Unfortunately, many people have worked a lot on the problem, and we are still *unable* to give an efficient algorithm for e.g. SAT (not to mention an algorithm that would be efficient in practice as well!). So how do we cope with this? We look at e.g. structural aspects of the input: what can we leverage? How can we be fast at least sometimes? Because we can't solve a problem we care about, we look for other approaches and angles of attack.

I think the main reasons we have been interested in random $k$-SAT is that first, such instances are easy to generate to test our solvers. We have also learned that random instances are very different from instances that arise in practice (and of course those are the instances we often care about). This has increased our understanding of the nature of computation, heuristics, complexity, and ultimately made us able to build faster solvers as well.

# Answer
> 1 votes
the other answer is good, here is a bit additional context & 2 papers as requested. the discovery of phase transitions in NP complete problems associated with random inputs was a striking scientific discovery at the time (mid 1990s), worthy of publication in a leading/ elite scientific journal, Science magazine, typically reserved for only very remarkable and cross-cutting discoveries by top scientists. phase transitions are normally seen/ studied mostly in physics and this discovery links theoretical physics areas such as thermodynamics theory with computer science theory, and is still being explored decades later, and there are now many dozens of papers on the subject. from Selmans own web site

another area where random inputs is now shown to play a significant role is in lower bounds proofs involving monotone circuits. Razborov won a TCS Nevanlinna prize for early work in this area now extended by Rossman.

another way to regard random inputs however is just more generally as one of the most basic input distributions that can be studied for statistical/ average case complexity, for any algorithm. for example with sorting algorithms and many others, an easy way to test them is with random inputs.

---
Tags: satisfiability, randomness
---


# Question
Title: Linear programming formulation of cheapest k-edge path between two nodes
Given a directed graph $G = (V,E)$ with positive edge weights, find the minimum cost path between $s$ and $t$ that traverses exactly $k$ edges.

Here is my attempt using a flow network: \begin{align} \min \sum\_{(i,j) \in E} c\_{ij}x\_{ij} \end{align} \begin{align} \sum\_{j \in V} x\_{ji} - \sum\_{j \in V} x\_{ij} &= \begin{cases} -1,& \text{if } i = s\\ 1, & \text{if } i = t\\ 0, & \text{otherwise}\\ \end{cases} && \forall i \in V\\ \sum\_{(i,j) \in E} x\_{ij} &= k &&\\ x\_{ij} &\geq 0 && \forall (i,j) \in E\\ \end{align}

However, this doesn't eliminate cycles which are disjoint from the $s$-$t$ path. I can use subtour elimination constraints like in the Miller Tucker Zemlin formulation of the Travelling Salesman Problem but this enforces a simple path making the problem harder than it should be.

Any ideas on alternative formulations?

Update: This is part of a slightly bigger formulation here, where $z$ is a slack variable which scalarizes multiple objectives with a rectified-linear function:

\begin{align} \min \sum\_{k \in K} z\_{k} \end{align} \begin{align} \sum\_{(i,j) \in E} c^{k}\_{ij}x\_{ij} - z\_{k} &\leq 1 && \forall k \in K\\ \sum\_{j \in V} x\_{ji} - \sum\_{j \in V} x\_{ij} &= \begin{cases} -1,& \text{if } i = s\\ 1, & \text{if } i = t\\ 0, & \text{otherwise}\\ \end{cases} && \forall i \in V\\ x\_{ij} &\geq 0 && \forall (i,j) \in E\\ \end{align}

Solutions are integral when solving with a linear program, but suggestions for more efficient algorithms would be appreciated.

# Answer
> 2 votes
The simplest way to compute the shortest path from $s$ to $t$ that traverses exactly $k$ edges is by increasing the size of the graph $k$-fold.

In particular, make $k$ copies of the vertices and $k-1$ copies of the edges, where for each edge $(u,v)$ in the original graph, we add an edge from the $i$th copy of $u$ to the $i+1$th copy of $v$ (for all $i$). Now look for the shortest path from the 1st copy of $s$ to the $k$th copy of $t$ using a standard algorithm (e.g., Dijkstra's algorithm). The running time will be $O(kn+km\lg(kn))$.

Only you can determine whether this kind of formulation will be compatible with your additional constraints and objective function (since you haven't told us what they are), but this kind of modification to the graph is a general approach for this sort of problem that is pretty flexible and might meet your needs.

You could presumably also combine this with your network flow / LP formulation. Now there will be no cycles that can show up, as the resulting graph is acyclic (a dag). I don't know if that will meet your needs.

---
Tags: graphs, shortest-path, network-flow, linear-programming
---


# Question
Title: How many edges can a unipathic graph have?
A unipathic graph is a directed graph such that there is at most one simple path from any one vertex to any other vertex.

Unipathic graphs can have cycles. For example, a doubly linked list (not a circular one!) is a unipathic graph; if the list has $n$ elements, the graph has $n-1$ cycles of length 2, for a total of $2(n-1)$.

What is the maximum number of edges in a unipathic graph with $n$ vertices? An asymptotic bound would do (e.g. $O(n)$ or $\Theta(n^2)$).

Inspired by Find shortest paths in a weighed unipathic graph; in my proof, I initially wanted to claim that the number of edges was $O(n)$ but then realized that bounding the number of cycles was sufficient.

# Answer
> 12 votes
A unipathic graph can have $\Theta(n^2)$ edges. There's a well-known kind of graph that's unipathic and has $n^2/4$ edges.

> Consider a complete bipartite graph, with oriented edges $\forall (i,j) \in \[1,m\]^2, a\_i \rightarrow b\_j$. This graph is unipathic and has no cycle: all its paths have length $1$. It has $2m$ vertices and $m^2$ edges.

 (Follow-up question: is this ratio maximal? Probably not, but I don't have another example. This example is maximal in the sense that any one edge that you add between existing nodes will break the unipathic property.)

# Answer
> 1 votes
I don't know if there a unipathic graph on more than $\frac{n^2}{4}$ edges, but here's an argument showing that no more than $\frac{n^2}{2}+3$ edges are possible:

Assume by contradiction that $G=(V,E)$ is a unipathic graph such that $|E|\geq \frac{n^2}{2}+3$.

By the pigeonhole principle, there exist $v\in V$ such that $$d\_{\text{in}}(v)\geq \frac{n}{2}+1$$

Denote $U=\\{u\in V\mid (u,v)\in E\\}$

Notice that if there was a vertex $x\in V\setminus \\{v\\}$ such that $$\exists u\_1\neq u\_2\in U:(x,u\_1),(x,u\_2)\in E$$

Then the graph wouldn't be unipathic (as $(x\to u\_1\to v)$ and $(x\to u\_2\to v)$ are both valid paths).

This means that (adding the edges from $\\{v\\}\times U$): $$|E\cap (V\times U)|\leq2|U|$$

So the average in-degree of $U$'s vertices is at most 2, hence: $$|E|=|E\cap (V\times U)|+|E\cap (V\times (V\setminus U))|$$ $$\leq 2|U|+n|V\setminus U|\leq 2(\frac{n}{2}+1)+n(\frac{n}{2}-1)\<\frac{n^2}{2}+3$$

$\square$

---
Tags: graphs, combinatorics
---


# Question
Title: Can the runtime of functions with no loops change with the number of calls?
How can we perform time complexity analysis on a function that has no loops?

```
int somefunction(int param) {
  if (something)
    do this;
  else
    do this;
}

```

Would the time complexity of this function change depending on how many times the function is called within a program? I currently believe that the time complexity is O(n), because it is dependent on the amount of times that we call it.

# Answer
The complexity is typically understood to be for one call. If you want to talk about the complexity of a sequence of calls, then you would need to say so.

In your example, you don't really gain anything by looking at sequences of calls. But there are other situations (with loops or recursive calls allowed) in which you would indeed want to look at sequences of calls. One example is when the function typically takes little time but once in a while it decides to do a lot of work. In that case, you need to quantify how ‘once in a while’ compares to ‘a lot of work’. A natural way to do so is to see how much it takes to execute a long sequence of calls (keywords: "amortized analysis").
> 1 votes

# Answer
Depends on what `something` and `do this` are. In particular, do we have to assume global (or object) state?

Consider this:

```
int switch(int param) {
  if ( !set.contains(param) )
    set.add(param);
  else
    set.remove(param);
}

```

Now the runtime clearly depends on the implementation of `set` *and* the number of entries it has when `switch` is called. Calling `switch` $n$ times starting with an empty set and using pairwise distinct parameters, you might get $\omega(n)$ runtime in total, hence not all calls run in time $O(1)$.

On the other hand, if `somefunction` does *not* access state outside of its scope -- assuming that the function itself does not have persistent state -- the runtime can only depend on `param`. That does not mean runtime is in $O(1)$ -- `something` and `do this` may still do non-constant things. Call methods, recurse, etc.

Note that depending on the cost model you use, even adding two numbers has non-constant cost.
> 1 votes

# Answer
It does not become linear just because it is called by linear-worst-case code; it retains whatever complexity it would have in isolation, which here looks an awful lot like constant-time, barring certain odd edge cases. Big-O of a chunk of code is not evaluated based on code that might include it in its own Big-O; you don't consider a hashtable access linear just because there's code that uses the hashtable to process a whole list of items and increment their occurrence counts.
> -1 votes

---
Tags: algorithm-analysis, asymptotics, runtime-analysis
---


# Question
Title: The most efficient way of finding/storing neighbourhood info during octree creation
Currently I have a program which at some point creates an octree and AFTER the creation loops through all the nodes, for every node (O(n2/2)) and thus finds the neighbours, by a brute-force box-box intersection check.

Since that is causing a bottleneck in my program I am looking to optimise this stage by somehow assigning the neighbours during octree-creation stage.

I am building a 'depth-first' recursive octree, which means that I go to the deepest level for every node, before moving on to it's neighbour...

What would be the best way to do something like this?

**EDIT:** The definition of 'neighbours' is the following. A neighbour is each **node of the same level/depth** which **shares a face** with the current node. Nodes which only share an edge or vertex should not be considered as neighbours. The picture below provides more clarity...

# Answer
I don't know if there is a way while constructing the oct tree. But here is way after you created the tree, which runs in O(N), where N is the number of Nodes. For each node there has to be a maximal comparison of 8\*6+7 = 55. This might can be reduced but this might be fast enough.

loops through all nodes breadth-first. A neighbour of a child is a neighbour child of the parent or a child of a the parents neighbours.

The comparison if two points are neighbours is here distance(node\_1,node\_2) == SMALLEST. I don't know how you compare it. Maybe you can insert your code. You could caluclate for each level the Euclidian distance of the points if you have equally spaced cuboids and compare them. That would be the fastest way.

when nothing works, you can just make a list for each of the 8 comparisons, sort them and keep the lowest one.

call function `calc_neighbours(root_node)` after you created the oct tree

```
class Node:
    Node **childs // array of size 8 and pointers to the child node pointers
    Node *parent
    Neighbours **neighbours

function calc_neighbours(root_node):
    queue = create_queue()
    queue.add(root_node)
    while (queue.isEmpty() == false)
    {
        parent_node = queue.pop()
        for (int i = 0; i < 8; i++) // for each child_cube
        {
            queue.push(parent_node->child[i])
            for (int j = 0; j < 8; j++) // for each neighbour child_cube
                 if (i != j && distance(parent_node->child[i],parent_node->child[j]) == SMALLEST)
                    // filter out those who share only vertex/edge
                    parent_node->child[i]->neighbours.add(parent_node->child[j])
        }
        if (parent_node != root_node)
        // root node has no neighbours, loops through all neighbours of the parent's neighbour's child
            for (int n = 0; n < parent_node->neighbours->size(); n++)
                for (int i = 0; i < 8; i++) // for each child_cube
                    for (int j = 0; j < 8; j++) // for each neighbour child_cube
                         if (distance(parent_node->child[i],parent_node->neighbours[n]->child[j]) == SMALLEST)
                            parent_node->child[i]->neighbours.add(parent_node->neighbours[n]->child[j])
    }

```
> 0 votes

---
Tags: algorithms, data-structures, optimization
---


# Question
Title: Fixed base exponentiation with precomputations
I'm trying to compute $g^m$ mod $n$ where $m,n$ are 1024-bit numbers. The method I want to use is fixed base exponentiation with precomputations, also known as fixed-base windowing.The paper I'm following is Brickell et. al. "Fast Exponentiation with Precomputation: Algorithms and Lower Bounds" which can be found here.

Basically the idea is to precompute $g^{b^i}$ where $b$ is a radix. Now if we write $m$ in the radix base: $m=\sum\_{i=0}^k e\_i b^i$ then $g^m=\prod (g^{b^i})^{e\_i}$. For example: say we want to compute $g^{142}$ and we have chosen as radix $b=3$ (I'm aware of the more natural example of radix 2, but I'm experimenting with different radices to see if there is any speed-up). I write $m=(12021)\_3$ and compute $g^{142}=g^{3^4}\times(g^{3^3})^2\times (g^3)^2 \times g^3$.

The pseudo code given in the paper is:

```
b ← 1
a ← 1
for d = h to 1 by −1
    for each i such that a_i = d
        b ← b ∗ g^{x_i}
    a ← a ∗ b.
return a.

```

where $h$ is the range of $e\_i$, and $a\_i=e\_i$ and $x\_i=g^{b^i}$.

My question is: instead of going through $e\_i$ by tier as the pseudo code suggested, why don't we go through the base $b$ representation of $m$ one digit at a time and multiply as we go?

When I looked up fixed-base exponentiation in Henk and Tilborg "Encyclopedia of Cryptography and Security," they say that "there is time saved by multiplying together powers with identical coefficients, and then raising the intermediate products to powers step by step." I believe this is hinting at the answer to my question, but I don't understand the reasoning.

# Answer
> 3 votes
Your question hits at the main part of the faster algorithm presented in the paper. Many people know the usual (base-2) "repeated squaring" algorithm to compute $g^n$ is to write $n$ in binary: $$ n=\sum\_{i=0}^m e\_i2^i\qquad e\_i\in\\{0,1\\} $$ so $$ g^n=g^{e\_02^0+e\_12^1+e\_22^2+\dotsm}=(g^{2^0})^{e\_0}(g^{2^1})^{e\_1}(g^{2^2})^{e\_2}\dotsm $$ and observe that $g^{2^k}=(g^{2^{k-1}})^2$ so computation of the $g$ terms can be accomplished by repeated squaring, either in the body of the loop or by precomputation. The paper simply generalizes this using a base, $b$, other than $2$. If we keep with your example of $b=3$, then we're doing the same thing as the usual algorithm, only using repeated cubing, rather than repeated squaring, so if we have, in general $$ n=\sum\_{i=0}^m e\_ib^i\qquad e\_i\in\\{0,1,\dotsc,b-1\\} $$ then we can write $$ g^n=(g^{b^0})^{e\_0}(g^{b^1})^{e\_1}(g^{b^2})^{e\_2}\dotsm $$ and do the usual algorithm, forming the product *seriatim*, from $0$ up to the limit $m$, using repeated exponentiation of the terms, since $g^{b^k}=(g^{b^{k-1}})^b$ as above. This is your proposal and it will work just fine.

The key idea in the paper relies on the observation that the $e\_i$ are now not just $0$ or $1$, so we often have another exponentiation step for each term. Rather than do several of those, the paper just does it once, for each possible value of $e\_i$.

Here's your example, with $n=142$ and $b=3$. Since $142\_{10}=12021\_3$ we'll have $e\_4=1$, $e\_3=2$, $e\_2=0$, $e\_1=2$, $e\_0=1$. Looping from $i=0$ to $4$ you could successively form the product $$ g^{142}=(g^{3^0})^1(g^{3^1})^{2}(g^{3^2})^{0}(g^{3^3})^{2}(g^{3^4})^{1} $$ The paper instead loops first by the nonzero values of the $e\_i$, effectively grouping several exponentiations into one, doing this: $$ g^{142}=\left \[(g^{3^1})(g^{3^3})\right \]^2\left \[(g^{3^0})(g^{3^4})\right \]^1 $$ obviously saving some multiplications.

---
Tags: multiplication, modular-arithmetic
---


# Question
Title: Fastest way to find natural solutions to Linear equation
$$ a\_i * x\_i + b\_i * x\_j = N $$

$\text{given } a\_i, b\_i, N \in \mathbb{N}$

i want to find a solution where $x\_i, x\_j \in \mathbb{N}$ or output if there exists none.

What is the fastest way to calculate this?

# Answer
> 4 votes
We can write $N$ as a linear combination of $a$ and $b$ if and only if $N$ is a multiple of $d=\gcd(a,b)$. Using the extended Euclidean algorithm we can find integers $x,y$ such that $ax+by=d$ and this in turn yields a solution of the form $\frac{N}{d}(ax+by)=N$. Now $\frac{Nx}{d}$ and $\frac{Ny}{d}$ will not necessarily be positive.

However, for all integer $k$, $a\frac{Nx+bk}{d}+b\frac{Ny-ak}{d}=N$ will also be a solution. To determine whether the equation has any natural solutions, we must simply determine the range of $k$ for which $Nx+bk$ is positive and the range for which $Nx-ak$ is positive and determine whether the ranges overlap.

In the case with 3 unknowns, $ax\_1+bx\_2+cx\_3=N$, note that $bx\_2+cx\_3$ will always be a multiple of $\gcd(b,c)$. The problem thus comes down to solving $ax+y\gcd(b,c)=N$, picking an appropriate solution to that problem, and then solving $bx\_2+cx\_3=y\gcd(b,c)$. However it is not clear to me how to pick $y$ so that the second problem can be solved.

---
Tags: algorithms
---


title: How to decide if CSP is ambiguous?

text:
# Question
Title: How to decide if CSP is ambiguous?
When you pick up some reading about CSP the main focus is how to solve it. My goal is to compute/decide if CSP is ambiguous (has 2 or more solutions) or not (has 1 solution).

Of course brute-force approach would be to solve it and see the outcome. But I am looking for something simpler (read: way faster).

*Background: I would like to write Zebra puzzle generator. There is no much resources about it, as with regular CSP, most are solvers, and 2 links I followed take such approach -- start from all clues, at each step reduce by one and **solve** it. If it unsolvable, get back that clue, and continue.*

# Answer
You shouldn't be able to beat the complexity of brute-forcing (because of having to check all possible assignments in the case that the CSP is not satisfiable). Instead, I offer the possibility of *smart* brute-forcing:

Solve the CSP normally and find a single assignment that satisfies it, if one exists. Add the negation of that assignment as a new constraint and jump back to the immediate last decision assignment you made and continue from there. This is a typical procedure for SAT solvers which traverse Implication Graphs and add *conflicting clauses* as constraints before backtracking to the last assignment decision. However, in the case of solving a SAT problem, each boolean variable can only have one of two possible assignments which is not true for the domains of constraints of CSPs, so you might actually need to backtrack further to find another complete assignment of all variables if one should exist (as per usual brute-forcing).

Let's suppose you have a CSP of three variables $A, B, C$. If you find a solution to the CSP whereby (let's say) C was assigned last, you could backtrack to the point right before making the assignment to C and continue from there, seeing if the same assignments of $A$ and $B$ could lead to a second solution with a different assignment of $C$. After finding your second solution, you could immediately terminate, knowing that the CSP is ambiguous. However, you might have to very well check all possible assignments of each variable in the case your initial solution to the CSP were the only solution (or even when your CSP is not satisfiable), in which case it would be unambiguous. So clearly, this procedure would only improve your efficiency for ambiguous CSPs where any two of all solutions differ with a single variable assignment.
> 1 votes

---
Tags: ambiguity, constraint-programming
---


# Question
Title: "Minimum" maximum flow with extra capacities
**Problem:**

Suppose there is a graph, a source and a sink. Each edge has a capacity and an extra capacity that it can hold. If sink needs a defined amount of flow `F`, find a total extra capacity needed `E` so that maximum flow from source to sink is greater than or equal to `F` and flow in each edge that has nonzero flow.

I don't know how to solve this variation of maximum flow problem. It is obvious that if maximum flow I find without extra capacities is greater than or equal to `F`, then there is no need for extra capacity. If it is less than `F`, should I add extra capacity in each edge one by one and find max flow again till I find the closest one to `F` (if it is not enough, then take in pairs, triplets, etc.)? This solution seems inefficient to me.

**EDIT:**

Example:

Suppose source is node 0 and sink is node 5. Sink requires flow of 6 `(F = 6)`. For the following format

```
(1st node, 2nd node), current capacity, extra capacity that can be added

```

we have following edges

```
0 1 3 0
0 3 3 0
1 2 3 0
1 3 2 0
2 4 4 0
2 5 2 2
3 4 2 1
4 5 3 1

```

Maximum flow from current capacities is 5 which is not enough for the sink (5 \< `F`). The extra capacity from 3 to 4 and 4 to 5 is required. So total extra capacity is 2 (`E` = 2) and the flows are

```
0 1 3
0 3 3
1 2 3
2 4 1
2 5 2
3 4 3
4 5 4

```

# Answer
> 1 votes
The smarter Naive approach of extending a solution to the Maximum Flow problem to a similar graph with at least as much capacity is to only add flow to augmenting paths that you'd find from the Residual of the initial graph. And if no augmenting paths exist, then terminate. This is known as the Ford-Fulkerson Algorithm, and if you were to have run it on the a graph of $E$ edges initially, this would incur a runtime of $O(E\cdot f^\*)$, where $f^\*$ is the maximum flow in the graph.

In case you haven't heard of some of these terms, or the Algorithm, visit: http://en.wikipedia.org/wiki/Ford-Fulkerson\_algorithm

---
Tags: graphs, network-flow
---


# Question
Title: Dynamic Programming - Print all paths from (0,0) to (n,n) in Grid/Lattice
I'm trying to write an algorithm to print all the paths from point (0,0) to (n,n) in a grid.
The only possible moves are *right* and *up*.
Also, you can't move below the diagonal *y=x*. e.g if you're at (1,1) you can only move to *(1,2)*, but not to *(2,1)*, since it's below the *y=x* diagonal.

I wrote an algorithm that calculates the number of possible paths from *(0,0)* to any given *(x,y)*, such that the above limitations are held, but I can't find a way to print out the paths that give these numbers.

The algorithm I wrote is a *bottom-up* one, as follows:

```
JUMP(x, y)
1.  M[x-1,y+1] ← 1
2.  for i=0 to x+1
        M[i,y+1] ← 0
3.  for i=0 to y+1
        M[x+1,i] ← 0
4.  for j=0 to y-1
        for i=j+1 to x
            M[i,j] ← 0

5.  for j=y to 0
        for i=j to 0
            M[i,j] ← M[i+1,j] + M[i,j+1]

6.  return M[i,j]

```

Please advise on this.

# Answer
> 5 votes
You can solve this problem using a recursive formulation of print all paths from a point $(i,j)$ to the target $(n,n)$ in the grid. I call this function $f(i,j)$. So the all paths will be in $f(0,0)$ call.

$f(i,j) = \begin{cases} \emptyset & if\ \ {i\>j}\\ \emptyset & if\ \ \neg( {0\leq i\leq n\ \wedge 0\leq j\leq n) }\\ \\{(n,n)\\} & if \ \ i = n \wedge j = n\\ \bigcup\_{p\\,\in\\, f(i+1,j)\\,\cup\\,f(i,j+1) } \ \ \\{(i,j)\\}\cup p & \text{otherwise} \end{cases}$

By example, two of all paths from $f(0,0)$ when $n=4$ are:

blue path = {{0, 0}, {0, 1}, {1, 1}, {1, 2}, {2, 2}, {2, 3}, {3, 3}, {3, 4}, {4, 4}}

red path = {{0, 0}, {0, 1}, {0, 2}, {1, 2}, {1, 3}, {2, 3}, {2, 4}, {3, 4}, {4, 4}}

So, although programming is not in the scope of this site, I think is good to see a implementation for a memoization version of the above algorithm. asdf

```
from functools import wraps

def memo(func):
    cache = {}

    @wraps(func)
    def wrap(*args):
        if args not in cache:
            cache[args] = func(*args)
        return cache[args]
    return wrap

@memo
def f(i, j):
    global n
    if i > j:
        return []
    if not (0 <= i <= n and 0 <= j <= n):
        return []
    if i == n and j == n:
        return [[(n,n)]]
    alls = []
    for path in f(i, j+1)+f(i+1, j):
        if len(path) > 0:
            alls += [[(i,j)] + path]
    return alls

n = 4
for path in f(0,0):
    print path

```

# Answer
> 0 votes
In the case of an $x$ by $y$ grid (assuming we start at the bottom-left and travel toward the upper-right), you can notice that every possible path will always contain $x$ steps toward the right and $y$ steps upward. You could encode every possible path with a binary string of length $x+y$ where $0$ encodes "right" and $1$ encodes "up", and there are exactly $x$ $0$'s and exactly $y$ $1$'s in the string.

To solve the problem, you could follow this procedure:

* take a binary string of length $x+y$, starting with all $0$'s
* check if the string has $y$ bits equal to $1$
* if so, print the path the string represents, with $0$ = "right" and $1$ = "up"
* incrememt the binary string by $1$ and repeat

In pseudocode:

```
x = 7; //the grid is x by y in size
y = 9;
N = x+y; //length of the binary string

for i from 0 to (2^N)-1:
  if NumberOfOnes(i,N) == y:
    PrintPath(i,N);

```

To check if the least-significant bit is a `1`, we can just take `i mod 2` and check if the result is a `1`. We can check bit `j` in the same way just by bit-shifting `j` bits to to the right and repeating the processes.

```
function NumberOfOnes(i,N)
  ones = 0;
  zeroes = 0;
  bit = 0;
  for j from N-1 to 0
    temp = i >> j;     //ensures we read the string from left-to-right
    if (temp mod 2) == 1
     ones++
    else
     zeros++
    if zeros > ones  // this protects us from moving below the diagonal
     ones = -1;
     break;
  return ones

```

To print the string we use a similar process to find the `1`'s and let `0` mean "right" and `1` mean "up". We also need to read the string left-to-right.

```
function PrintPath(i,N)
  path_string = [empty]
  for j from N-1 to 0
    temp = i >> j          //ensures we read the string left-to-right
    if (temp mod 2) == 1
      path_string += 'up, '
    else
      path_string += 'right, '

  print(path_string)

```

This involves checking $2^{x+y}$ binary numbers and performing $x+y$ bit-shifts on each one.

Also for counting the paths, you can notice that the number of acceptable binary strings is just ${x + y \choose y}/2$ since we have $x+y$ binary digits and need to choose $y$ of them to be $1$, and divide by $2$ to ignore paths below the diagonal.

---
Tags: algorithms, dynamic-programming, enumeration
---


title: What is a rewrite-based system?

text:
# Question
Title: What is a rewrite-based system?
I am reading about this in the context of the K semantic framework. I keep encountering terms such as rewrite-term and rewrite logic. My main aim is to understand what is K doing and how it works, so maybe this would be a bit off-topic.

# Answer
I am assuming that you have some background in a functional programming language like Haskell or ML or OCaml because that is the easiest thing for me to explain this in terms of.

Haskell is, or can be viewed as, a rewrite system. When you simplify little expressions you are rewriting the expression in little steps until you get to the final result (normal form).

For instance a list like \[1, 2, 3\] can be denoted by the term (1 : (2 : (3 : \[\])))

Another term is a term like

```
(1 : (2 : [])) ++ (3 : [])

```

which can be reritten as

```
1 : ((2 : []) ++ (3 : []))

```

which can in tern be rewritten as

```
1 : (2 : ([] ++ (3 : [])))

```

which can (finally) be rewritten as

```
(1 : (2 : (3 : [])))

```

This was all based on the following rewrite rules

```
(x:xs) ++ ys -> x : (xs ++ ys)
[]     ++ ys -> ys

```

where x -\> y can be thought of as "if you see 'x' replace it with 'y'"

So basically a rewrite system is a system that has a set of rules that explain how to rewrite certain subterms of a term in a system. Once there are no rules left that apply the term is in normal form. Some times terms have no normal form however, these are either errors or infinite loops in systems like Haskell.

example:

```
addLots x -> 1 + addLots x

addLots 0 (this expression has no normal form as we just have to keep adding 1s on)

```

Haskell also gives us some guarantees on the order that it will apply the rewrite rules (but does not fully define it). For instance

```
case 1 : (addLots 0) of {x : xs -> 2}

```

will evaluate to 2. If the order was either unspecified or chose to fully evaluate 1 : (addLots 0) then it would have not ever reached it's normal form.

A rewrite system does not in general have to have such an order however; it just has to say which rewrites are valid. Another example of a rewrite system is first order logic. You are given a set of rewrite rules called "inference rules" and a set of terms called "first order logic terms". You can derive tons of expressions from other expressions in just such a way. Like the following two rewrite rules.

```
~~x -> x
x -> ~~x

```

we could keep gong back and forth between these and we would get an infinite loop but a human knows how to apply these in just the write way to derive interesting theorems.

edit: It seems to me (from a brief look) that the K semantic framework is a system for defining what terms on in the language (quite like data expressions in Haskell but more advanced) and then it lets you define rewrite rules on these expressions (a bit like functions in Haskell). In the K semantic framework syntax and rules are totally separated where as in Haskell data expressions define the syntax of normal forms and function definitions define a new bit of syntax along with a reduction rule on that new syntax.
> 3 votes

---
Tags: term-rewriting
---