# Question
Title: Infer a list of numbers from observations of subranges
There's a list of (unknown) integers, in `[0...20]`. They are generated from a uniform distribution via a RNG.

The input is observations of the form:

* in a subrange `[i,j)` of the list, and some given threshold T in `[0...20]`, how many sextuples exist (not necessarily of consecutive numbers) consisting of numbers that are **less than T**.

Example: `[0..12), there are 0 sextuples of numbers < 2` This means that for the 12 first numbers of the list, there don't exist 6 numbers which are all less than 2. Another way to view this would be that there exist at least 7 numbers in this range that are `>= 2`.

Another example: `[0..18), there are 1 sextuples of numbers < 7`

For the 18 first numbers of the list, there exists one sextuple of numbers that are less than 7 (there could be up to 11 such numbers, but not 12, otherwise there would be *two* sextuples). Another way to state this would be that, for this range, there exist at least 7 numbers which are `>= 7`.

Here's an example input, describing known facts about a list of `102` unknown numbers in \[0..20\] `[0..12), there are 0 sextuples of numbers < 2
[0..60), there are 1 sextuples of numbers < 2
[0..18), there are 1 sextuples of numbers < 7
[0..36), there are 2 sextuples of numbers < 7
[0..30), there are 1 sextuples of numbers < 8
[0..36), there are 2 sextuples of numbers < 8
[0..60), there are 3 sextuples of numbers < 8
[0..18), there are 1 sextuples of numbers < 9
[0..42), there are 3 sextuples of numbers < 9
[0..30), there are 2 sextuples of numbers < 10
[0..36), there are 2 sextuples of numbers < 10
[0..60), there are 4 sextuples of numbers < 10
[0..42), there are 4 sextuples of numbers < 13
[0..60), there are 5 sextuples of numbers < 13
[12..72), there are 6 sextuples of numbers < 14
[18..42), there are 1 sextuples of numbers < 10
[18..42), there are 2 sextuples of numbers < 12
[30..60), there are 1 sextuples of numbers < 8
[30..60), there are 2 sextuples of numbers < 11
[36..66), there are 2 sextuples of numbers < 8
[36..66), there are 3 sextuples of numbers < 11
[36..66), there are 3 sextuples of numbers < 12
[42..102), there are 1 sextuples of numbers < 2
[42..102), there are 1 sextuples of numbers < 2
[42..66), there are 1 sextuples of numbers < 7
[42..78), there are 2 sextuples of numbers < 7
[42..102), there are 3 sextuples of numbers < 7
[42..78), there are 2 sextuples of numbers < 8
[42..66), there are 2 sextuples of numbers < 10
[42..72), there are 2 sextuples of numbers < 10
[42..78), there are 3 sextuples of numbers < 10
[42..84), there are 3 sextuples of numbers < 10
[42..102), there are 5 sextuples of numbers < 10
[42..102), there are 6 sextuples of numbers < 13
[60..72), there are 0 sextuples of numbers < 2
[60..78), there are 1 sextuples of numbers < 7
[60..90), there are 2 sextuples of numbers < 8
[60..78), there are 1 sextuples of numbers < 9
[60..90), there are 2 sextuples of numbers < 11
[60..102), there are 4 sextuples of numbers < 11
[60..102), there are 4 sextuples of numbers < 13
[72..102), there are 1 sextuples of numbers < 8
[78..102), there are 1 sextuples of numbers < 10
[78..108), there are 2 sextuples of numbers < 11
[78..102), there are 2 sextuples of numbers < 12
[84..102), there are 0 sextuples of numbers < 7`

The question is, how do I infer as much info as possible for the unknown numbers. The problem may be under-specified. But still, when two subranges overlap (or especially when one is a prefix or suffix of another), then it becomes possible to infer something new, and with enough observations, the unknown numbers could be narrowed down to small margins.

Examples:

`[0..18), there are 1 sextuples of numbers < 7
[0..18), there are 1 sextuples of numbers < 9`

Here, the second observation can be dropped, the first is more restrictive.

`[0..30), there are 1 sextuples of numbers < 8
[0..36), there are 2 sextuples of numbers < 8` Here, the first is a prefix of the second. And both observations are for the same threshold, 8. All numbers of the first range exist in the second range. Hence, we can infer that there exist at least one number in \[30..36) which is \< 8 (it could be all 6 of them).

`[0..12), there are 0 sextuples of numbers < 2
[0..60), there are 1 sextuples of numbers < 2` A similar example. From these two, we can infer that in the range \[12..60), there exist `{1..6}` numbers that are `< 2`.

---

Any advice on how I should approach this? I wonder if coding such heuristics will get me anywhere, or I need some more generalized algorithm to help me. This is likely not a polynomial problem, though with enough observations about small subranges (these seem to be the most useful), this may be tractable. But no appropriate algorithm comes to mind. Thanks for any suggestion!

# Answer
> 1 votes
Hint: If you know that there are $n$ sextuples of numbers less than $T$ among the numbers $x\_i,\dots,x\_j$, you can infer how many numbers less than $T$ there are among $x\_i,\dots,x\_j$. See if you can figure out how.

That sounds like a very useful first step for your algorithm.

After that, you could apply integer linear programming.

There is not likely to be any polynomial-time algorithm; you can show a reduction from 3SAT with a little creativity.

# Answer
> 0 votes
I'll use Constraint Programming, via this library: google/or-tools/constraint\_solver.h

Given that the ordering of numbers in the sextuples doesn't matter, I'll model it as follows:

`S(i,j)`, a subrange of 6 numbers (starting at a multiple of 6). * i is the index of the range, e.g. `S(5)` would be subrange `[30..36)` * j is *how many numbers in this range are equal to `j`*

Hence `S(0,20)` would be "how many 20s exist in the \[0..6)".

Obviously `0 <= S(i,j) <= 6`, each number can appear at most 6 times in a range of length 6.

Also: `Σ(S(i,j)) = 6` for some `i`, and for `j=1..20`, i.e. there are exactly 6 numbers in every range of length 6.

Then, given an observation of the form:

`In the range [0..12), there is exactly 1 sextuple of numbers < 3` I add a constraint that looks like this:

`6 <= S(0,0) + S(0, 1) + S(0, 2) +
 S(1,1) + S(1, 0) + S(0, 2) < 12` I.e. "if there are 6 numbers in \[0..12) that are less than 3, then there have to be at least 6 numbers that are either {0,1,2} in the subranges \[0..6) and \[6..12). But there can't be 12 such numbers there.

I'm using subranges of length 6 since this is the minimum resolution I can get observations for, and it doesn't make sense to model the problem as if I'm trying to locate the exact ordering of numbers in these subranges, this is always impossible.

The library apparently lets me find multiple solutions iteratively, hopefully I'll get some useful output out of it.

---
Tags: algorithms, combinatorics
---


title: Is $\Gamma = Inv(Pol(\Gamma))$?

text:
# Question
Title: Is $\Gamma = Inv(Pol(\Gamma))$?
I'm reading A Rendezvous of Logic, Complexity and Algebra, my first introduction to the world of CSP. Let $\Gamma$ be a finite constraint language. It says in Pg. 9 that

> $Pol(\Gamma)$ is used to denote the set of all polymorphisms of $\Gamma$, that is, $$Pol(Γ) = \\{f : \forall R \in \Gamma, \textrm{ f is a polymorphism of }R\\}.$$ Also, for a set of operations $O$, we use $Inv(O)$ to denote the set of relations having all operations in $O$ as a polymorphism, that is, $$Inv(O) = \\{R : \forall f \in O, \textrm{ f is a polymorphism of } R\\}.$$

The answer to my question is: No (in fact it is a subset of $\Gamma$). But I don't understand why:

1. Isn't every $R\in \Gamma$ in $Inv(Pol(\Gamma))$?
2. Are the $R$'s from $Inv(O)$ allowed to come only from $\Gamma$?

# Answer
The operation $\operatorname{Inv}(\operatorname{Pol}(\cdot))$ is a *closure* operation. This means that

1. $\Gamma \subseteq \operatorname{Inv}(\operatorname{Pol}(\Gamma))$.
2. $\operatorname{Inv}(\operatorname{Pol}(\Gamma)) = \operatorname{Inv}(\operatorname{Pol}(\operatorname{Inv}(\operatorname{Pol}(\Gamma))))$.

See for example lecture notes of Jin-Yi Cai.
> 0 votes

---
Tags: constraint-satisfaction
---


# Question
Title: Maximizing the sum of selected elements in a matrix
I’m trying to find an efficient algorithm for the following optimization problem:

Given a matrix $A$ with elements $a\_{ij}$ and dimension $k$, select exactly $n$ elements from $A$ ($n\<k$) such that the sum of the elements is maximized, subject to the constraint that any index of $a\_{ij}$ is only used once. In other words: if element $a\_{ij}$ has been selected, no other elements from rows and columns *i* and *j* can be selected.

Notes:
\- It is allowed to select elements from the diagonal.
\- The order of magnitude of $k$ is 10,000.

I have a dynamic programming algorithm but the downside is that it can't be parallelized.

The problem resembles the assignment problem. This can be solved using the Hungarian Algorithm, which can be easily parallelized using Java 8 streams. However, the assignment problem has the constraint that from each row and column only one element can be selected. This is less strict than above problem since it allows to select both $a\_{ij}$ and $a\_{ji}$.

**Question:** do you know how to adjust the Hungarian Problem for the stricter constraint?

**Context:**
This algorithm is used to optimize large-scale power storage, which can be modelled as a collection of spread options.

# Answer
The problem you want to solve is (a slight variation of) maximum weighted matching in *general* (i.e., not necessarily bipartite) graphs. There are several algorithms with various worst-case bounds:

The above algorithms don't allow "self-edges" (choosing elements along the diagonal). To accommodate these, for every vertex $v\_i$, create an extra vertex $u\_i$, and an edge $(v\_i, u\_i)$ with weight $a\_{ii}$.

Note that while some of these papers talk about the maximum weight *perfect* matching problem, in which we have the additional constraint that every vertex must be incident on an edge in the matching, you can turn any instance of the plain maximum weight matching problem into an instance of the perfect kind by adding, for every existing vertex $v\_i$, a new vertex $v'\_i$, a zero-cost edge $(v\_i, v'\_i)$, and another zero-cost edge between every pair ($v'\_i, v'\_j)$ of new vertices. (Perhaps another construction using fewer zero-weight edges is possible?)

I found most of the above information in https://people.mpi-inf.mpg.de/~mehlhorn/ftp/WeightedMatchings.pdf, which has a lot of useful information on implementation and theory.
> 5 votes

---
Tags: algorithms, optimization, assignment-problem
---


# Question
Title: calculting distance between a person and the object in the image
Let's say a person took an image like this

I have access to all image attributes (like for example image format, resolution and so on), and I know the location of the person - basically the place where he made the photo. Also I know all the data about the camera - model, resolution and others.

Is there an algorithm that allows to calculate the real distance between a person and the object on the image?

# Answer
No, it's not possible without extra information. Just think: if the house was 20 feet tall and 100 feet away, you couldn't distinguish that from the case where the house was 30 feet tall and 150 feet away. Those two would lead to exactly the same image.

Here are some possible options you could consider:

1. If you have two pictures of the same house taken from two different positions, and you know the relative positions (e.g., one was 10 feet to the right of the other), then you may be able to infer the distance to the house, using parallax.
2. If you know the height of some feature in the image -- say, the door -- and you know all of the camera parameters (in particular, the angular resolution of a single pixel or of the field of view), then you can work out the distance to the house. So if you could calibrate the camera in advance, and make a guess/assumption about the height of the door, you could draw an inference about the distance to the house.

However this does require knowing all the camera parameters, which will probably require some calibration; I just knowing the image format, resolution, etc. and the camera resolution etc. will not be enough, and even knowing the model of the camera will probably not be enough. (Possibly if you knew the exact model of the camera and could go buy another camera of the same model, you might be able to calibrate the second one and assume both cameras have the same calibration. I don't know if that would work.)

See also Using Headpose Vector and 2D Points to Compute Distances. You might also look into camera intrinsics, camera extrinsics, the pinhole camera, and similar topics from computer graphics / computer vision.
> 2 votes

---
Tags: image-processing
---


# Question
Title: Add a road to a network (Graph problem with Dijkstra)
Recently i have found a problem stating: There is a network of roads G=(V,E)(it is not directed) connecting a set of cities V. The length of each road e ∈ E is le. There is a proposal to add one new road to this network, and there is a list E′ of pairs of cities between which the new road can be built. Each such potential road e′∈ E has an associated length. As a designer for the public works department you are asked to determine the road e′ ∈ E whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.

The basic solution was to apply to 2 times Dijkstra (from s to city x and from t to a city y) and then try all the edges from E' which would result into

2\*(Dijkstra) + (|E'|) = ((|V|+|E|)⋅ log |V|+|E’|)

But then on the web I found an altrenative solution:

> If you run Dijkstra for every edge in E’, the running time is (|E|⋅|E’|⋅ log |E|)

I do not understand this alternative. Could anybody explain this strategy to me? Thanks in advance!

# Answer
> 0 votes
Who knows. You'd have to ask them; that doesn't provide enough details to narrow it down.

If I had to guess, I imagine that perhaps they had in mind that they would do Dijkstra's algorithm once to measure the distance from $s$ to each vertex; then for each candidate edge $(u,v) \in E'$, they would use Dijkstra's algorithm to find the distance from $u$ to $t$ assuming $(u,v)$ has been added to the graph; and use this to find the best edge to add.

In any case, their alternative solution is considerably slower, so it's a poor choice and should not be used. It's far faster to use the first solution you listed.

---
Tags: complexity-theory, graphs, time-complexity
---


# Question
Title: Algorithm for checking if a list of integers is pairwise coprime
Are thre any efficient algorithms for checking if a list of integers is pairwise coprime, or would a more general algorithm be the best option available?

# Answer
> 9 votes
First, two facts about coprime integers:

* Iff $a$ and $b$ are coprime, then $ab = \mathrm{lcm}(a,b)$
* Iff $a$ is coprime to both $b$ and $c$, then $a$ is coprime to $bc$

It follows from this that a set of distinct integers $\\{a, b, \cdots z\\}$ is pairwise coprime if its product is equal to its least common multiple.

You can compute the least common multiple by using the following identity:

$$\mathrm{lcm}(a,b,c) = \mathrm{lcm}(a,\mathrm{lcm}(b,c))$$

Assuming you have $n$ numbers with $k$ digits each, and multiplying/dividing/modding two numbers is $O(1)$ (which may or may not be a good assumption depending on your model), then:

* Calculating the product of your set takes $O(n)$
* Calculating the gcd of two numbers takes $O(k)$
* Calculating the lcm of two numbers thus also takes $O(k)$, by reduction to gcd
* So calculating the lcm of your entire set takes $O(nk)$

Thus, the time complexity of the entire algorithm is $O(nk)$.

# Answer
> 5 votes
Yes. The naive approach of checking each pair of numbers takes quadratic time, but there are more efficient algorithms. There is a nearly-linear time algorithm, described in the following paper:

Daniel J. Bernstein. Factoring into coprimes in essentially linear time. Journal of Algorithms 54 (2005), 1--30.

See also https://cstheory.stackexchange.com/q/3393/5038. That's almost as efficient as you could possibly hope for.

To clarify how this helps with your situation, once you've found a coprime basis and factored each element over the basis, it is trivial to check whether they are pairwise coprime: if they are not pairwise coprime, then some pair will have a common factor, and that will be a factor that is in the coprime basis and that is present in the factorization of both. If there is no factor that is common to present in the factorization of two or more numbers, then you know the numbers are pairwise coprime. Once you have the factorizations, it is easy to check in linear time whether any numbers in more than one factorization.

# Answer
> 2 votes
Find the prime factors of each number. The numbers are all pairwise coprime if and only if every prime in the entire collection is distinct. This check can be done in O(n) time using a hash table.

Edit: Draconis' answer is better though, because it doesn't require any factorization. GCD computation is faster if your numbers are big and/or prime.

---
Tags: algorithms, primes
---


title: BDD to CNF in linear time

text:
# Question
Title: BDD to CNF in linear time
I have a book from my university that claims:

> There is an linear algorithm that can convert BDD to CNF in linear time, and generate CNF in linear length of the BDD size (number of nodes).

Then they wrote an exercise to find one...

Actually I tried to do so, I thought to find the paths that brings me to 0, and then translate them to clause (with the opposite value of the variables), and use Tseytin transformation to create linear length of CNF.

The problem are:

1. How can I find all the paths to 0? I thought about DFS but it seems to be complex task for DFS because I need the variables value (the naive algorithm is exponential)
2. The other problem is the variables to add, when should I create a new variable, every move? It can cause an exponential number of variables, which is not good.

So what is the correct algorithm to do that?

# Answer
Thanks to D.W. hints here is the solution:

Let's introduce a boolean variable $x\_v$ for each node $v$ in the BDD.

Start scanning the BDD from the leaf $1$ backward (with BFS for example). For each node that we visit, we will use Tseitin transform and we will be treated as an Or Gate. Its parents (in the original BDD direction) will be the input (the value of the variable of the parent should be the same as the edge in the BDD) and it will be the output. At the end of the search, we will combine each such CNF with conjunctions and will get one CNF that represents the BDD.

The search is done in linear time. Let $n$ to be the number of the vertex in the BDD. Each node adds at most 3 clauses (for the Or gate) and each clause has $n$ variables at most. So the complexity of the CNF length is $O(n\*3n)=O(n^2)$ which means that we have linear running time and linear CNF length.
> 0 votes

# Answer
This is a nice exercise. I'll give you a series of hints. Click on each hint only after you've spent a good amount of time thinking on the previous one. You'll get the most value by solving this on your own.

Hint #1:

> Add extra variables.

Hint #2:

> Use the Tseitin transform. Review to convert CircuitSAT to SAT.

Hint #3:

> Introduce a boolean variable $x\_v$ for each node $v$ in the BDD.

Hint #4:

> The idea is that $x\_v$ should be true iff the path you follow goes through $x\_v$. Can you write clauses to ensure all of this?
> 0 votes

---
Tags: bdd
---


# Question
Title: Maximum number of distinct values for bitwise OR
> You are given an array with $N$ elements. The values of the elements may be any number in the interval $\[0,10^9\]$. Define $f(a,b)$ as the bitwise or of all the values in the subarray $\[a,b\]$. Find a bound on the number of distinct values of $f(a,b)$.

**Attempts**: I have tried to brute force cases to find a pattern but was unsuccessful.

Please explain the reasoning behind your answer. I am a complete beginner.

# Answer
> 1 votes
Notice that the max value here given is 1e9. Therefore at most log(1e9) bits can be there. Suppose we fix an 'a' and iterate over 'b' such that b\>=a. Thus this will form a monotonic function as bitwise OR can only increase the value of the initial operands. Moreover the OR operation can only turn a bit ON from OFF and not the other way round. So whenever the values increases that means a new bit has to be set ON. However for a fixed value of 'a' we can only turn on at most log(1e9) bits. Hence when we iterate over 'a' we can have a maximum bound of O(n)*O(log(1e9)) distinct values. Hence the bound is O(n*log(MAX\_VALUE))

---
Tags: logic, arrays
---


# Question
Title: Python: Clustering based on pairwise distance matrix
I have a matrix which represents the distances between every two relevant items. For example, M\[i\]\[j\] holds the distance between items i and j. My next aim is to cluster items by these distances. I can provide some parameters: maximal number of clusters, maximal distance between two items in a cluster and minimal number of items in a cluster. I cannot, however, provide the "central items" which the algorithm should start with. I went through some of python's clustering packages, like scikit-learn, but did not find anything that matches.

Any ideas?

Thank you :)

# Answer
The constraints you have are not very clear (why should you start with "central items" ?). You should maybe try to come up with a well defined problem by precisely defining the clustering(s) you are looking for.

For example, if the clustering you want is such that the maximum number of clusters is $k\_{max}$ and the maximum distance between two elements in a cluster is $d\_{max}$, one possible approach is to perform a Complete-linkage Hierarchical clustering of your items. Possible clusterings then correspond to cuts in the resulting dendogram. Most library include the possibility of finding a cut that correspond to $k$ clusters or at a "height" $d$. A cut at height $d\_{max}$ corresponds to the smallest clustering that respect the distance constraint. If the latter is not possible with the library you are using, you can explore every cut from size $1$ to size $k\_{max}$ and select one that respects the distance constraint (Note it may not always be possible to found one *e.g.* with $d\_{max}$ close to $0$ and $k\_{max}$ close to $1$.)
> 1 votes

---
Tags: clustering, python
---


title: Solving double recurrence relation

text:
# Question
Title: Solving double recurrence relation
How to calculate the rate of growth of the below function $f(x)$? $$ \begin{align\*} f(x) &= \begin{cases} f(x-1) + g(x) & \text{if } x \> 1, \\ 1 & \text{if } x \leq 1. \end{cases} \\ g(x) &= \begin{cases} f(x-1) + g(x/2) & \text{if } x \> 1, \\ 1 & \text{if } x \leq 1. \end{cases} \end{align\*} $$

# Answer
By induction, $f(x)$ can be expressed non-recursively as a sum over $g$. That can be substituted into the definition of $g$ to get a single recursion, which can be compared to a well-known standard recurrence to show a lower bound. Finally, the comparison is close enough to hint that the upper bound must be similar to the lower bound, so you should be able to guess an upper bound and prove it.
> 0 votes

---
Tags: time-complexity, asymptotics, recursion
---


# Question
Title: Don't understand one step for AVL tree height log n proof
I came across a proof that an AVL tree has $O(\log n)$ height and there's one step which I do not understand.

Let $N\_h$ represent the minimum number of nodes that can form an AVL tree of height $h$. Since we're looking for the **minimum** number of nodes, let its children's number of nodes be $N\_{h-1}$ and $N\_{h-2}$.

Proof:

$$N\_h = N\_{h-1} + N\_{h-2} + 1 \tag{1}$$ $$N\_{h-1} = N\_{h-2} + N\_{h-3} + 1 \tag{2}$$ $$ N\_h = (N\_{h-2} + N\_{h-3} + 1) + N\_{h-2} + 1 \tag{3}$$ $$ N\_h \> 2N\_{h-2} \tag{4}$$ $$N\_h \> 2^{h/2} \tag{5} $$

I do not understand how we went from (4) to (5). If anyone could explain, that'd be great.

# Answer
> 6 votes
You can continue as same as line 4 the process like that:

$$ N\_h \> 2N\_{h-2}\> 2(2 N\_{h-4})\>2(2(2 N\_{h-6}))\>\cdots$$ As you can see, the indexs are decreasing by substracting $2$ in each step when you use the inequality. So, the process stops when the index $h$ takes $0$, but from the indexs behavior the half of $h$ (floor) will be the quantity of times that we substract $2$ from $h$.

$$ N\_h \> 2N\_{h-2}\>\cdots\>2(2(2(2(2h^{h-10}))))\> 2^{\frac{h}{2}}$$

# Answer
> 2 votes
Assuming $h$ even, by induction

$$N\_h\>2N\_{h-2}\>2^2N\_{h-4}\>2^3N\_{h-6}\>\cdots 2^{h/2}N\_0$$

because you go up two levels $h/2$ times.

# Answer
> 0 votes
After drawing some trees, I realized that the minimum number of nodes of a tree with height $h-2$ is in fact $2^{h/2}$.

# Answer
> 0 votes
Let's consider an example of an AVL tree with height of 4, then:

$N\_8 \> 2 N\_{6} \ \ \ \Longleftrightarrow \ \ N\_8 \> 2^1 N\_{8 - 2 \cdot 1}$

$N\_8 \> 4 N\_{4} \ \ \ \Longleftrightarrow \ \ N\_8 \> 2^2 N\_{8 - 2 \cdot 2}$

$N\_8 \> 8 N\_{2} \ \ \ \Longleftrightarrow \ \ N\_8 \> 2^3 N\_{8 - 2 \cdot 3}$

$N\_8 \> 16 N\_{0} \ \Longleftrightarrow \ \ N\_8 \> 2^4 N\_{8 - 2 \cdot 4}$

recall, that a tree with only one node (root) has height of 0, so $N\_{h=0} = 1$. Hence,

$N\_8 \> 16 N\_{0} \ \ \ \ \Longleftrightarrow \ \ \ \ N\_8 \> 2^4$

and this is exactly $N\_h \> 2^{h/2}$.

---

The most interesting part of this proof is **generalization**. Did you notice a pattern in our example?

$N\_h \> 2^i N\_{h - 2 \cdot i}$ $\qquad (1)$

Can we compute the value of $i$ when $N\_{h - 2 \cdot i}$ becomes $N\_{h=0}$?

Yes, we can get the value of $i$ by solving this equation: $h - 2 \cdot i = 0$. The answer of the equation is $i=h/2$.

The next step is to substitute $N\_{h - 2 \cdot i}$ with $N\_{h=0}$ and $i$ with $h/2$ in the $(1)$ equation, which is:

$N\_h \> 2^{h/2} N\_0 \ \ \ \ \Longleftrightarrow \ \ N\_h \> 2^{h/2}$

Proved.

---
Tags: data-structures, search-trees, balanced-search-trees, avl-trees
---


# Question
Title: Multi-processing cpu utilization estimate
I find a formula on my book to estimate cpu utilization under multi-processing.

$ U = 1 - P^n $

U: cpu utilization P: cpu idle

I want to know why or how to proof.

Edit:

The book is about operating system, not in english.

This may be like https://stackoverflow.com/questions/20328619/calculate-cpu-utilization/20328695?noredirect=1#comment88673153\_20328695

I get an answer that is

> it's just basic probability theory

# Answer
> 0 votes
$P^n$ is the probability that all "cores" are idle simultaneously, hence $1-P^n$ is the probability that at least one core is in use.

---
Tags: operating-systems
---


# Question
Title: Is there a computer science theory behind automatic source code generation
The OpenAPI specification aims at standardizing the representation of REST based systems in json and yaml formats. A short version of the petstore is below:

```
{
 "swagger": "2.0",
 "info": {},
 "host": "petstore.swagger.io",
 "basePath": "/v2",
  "tags": [],
  "schemes": [
 "http"
 ],
 "paths": {},
 "securityDefinitions": {},
 "definitions": {},
 "externalDocs": {
 "description": "Find out more about Swagger",
 "url": "http://swagger.io"
 }
}

```

Based on this document, client and server stubs can be generated in different programming languages/frameworks using the OpenAPI codegen project. Is there a computer science theory behind this ? **To be more precise**, I want to specifically know if there are theoretical concepts behind taking an input, (in this case a json/yaml document) and getting a source code representation in one or more programming languages that represents the initial input ?

# Answer
> 1 votes
I don't know anything about it but the field as a whole is called "automatic programming", which should give you pointers of where to look.

---
Tags: code-generation
---


# Question
Title: Minimal number of nodes needed to connect a disconnected graph
Given a graph $G = (V, E)$ with $V = U \uplus T$ (let's say the vertices are labelled $U$ or $T$), I am looking for the smallest set $U' \subseteq U$ such that $G\[U' \cup T\]$ is connected.

If we eleminate all the type-U nodes from the graph, the type-T nodes (terminals) might form several disconnected subgraphs. That is, the graph $G\[T\]$ on only the "terminal nodes" might be disconnected, and I want to pick as few vertices from $U$ as possible to make the graph connected again.

*What kind of graph problem* does this relate to?

# Answer
I think you are looking for the vertex version of the *Steiner tree* where

* $A$ is the set of terminal nodes and
* $B$ is the set of vertices you want to use to create a tree.

In the Vertex-Weighted Steiner Tree problem you are given a graph $G = (V,E)$ and a set of terminal nodes $T \subseteq V$ and are asked for a minimum set $U$ such that $T \subseteq U$ and $G\[U\]$ is connected.

This problem has been studied as the *node‐weighted Steiner tree problem* by

* Segev, 1987, *The node‐weighted steiner tree problem*, Networks.
* Yeh and Chang, 1998, *Weighted connected domination and Steiner trees in distance-hereditary graphs*, Discrete Applied Mathematics.

and is indeed NP-complete.

On the positive side, it might be solvable in time $3^k \text{poly}(n)$ where $k$ is the number of connected components in $G\[T\]$. The simplest preprocessing step is to contract all the edges in $G\[T\]$ first, that is, replace all the connected components with a single node, and remove parallel edges. (That is, it is *fixed-parameter tractable* (FPT) in the number of connected components in $G\[T\]$).
> 2 votes

# Answer
The problem is NP-hard.

A *connected vertex cover* is a vertex cover where the subgraph induced by these vertices is connected. Consider the following connected vertex cover problem (CVC):
**Input:** a graph and an integer $k$.
**Output:** whether there is a connected vertex cover of size no more than $k$.

CVC is proved to be NP-hard even if the graph is planar and has maximum degree 4 \[1\]. I'll reduce CVC to the decision version of this problem (say CDC for simplify).

Given an instance of CVC $G=(V,E)$, for each edge $e\in E$, create a vertex $v\_e$. Let $V\_E=\\{v\_e\mid e\in E\\}$. Create a new bipartite graph $G'$ whose vertex set is $V\uplus V\_E$, and there is an edge between $v\in V$ and $v\_e\in V\_E$ iff $v$ is an endpoint of $e$ in $G$. The instance of CDC is $G'$ where vertices in $V\_E$ are type-A vertices and vertices in $V$ are type-B vertices.

Note a connected vertex cover $U\subseteq V$ of $G$ makes the subgraph of $G'$ induced by $U\cup V\_E$ connected, and vice versa. Therefore, the instance of CVC has a solution iff the instance of CDC has a solution.

---

\[1\] Garey, Michael R., and David S. Johnson. "The rectilinear Steiner tree problem is NP-complete." *SIAM Journal on Applied Mathematics* 32.4 (1977): 826-834.
> 2 votes

# Answer
One starting point could be to take a simpler case: $G=(A \cup B,E)$ is a connected bipartite graph. I think this problem may relate to the Connected dominating set problem (CDS) in this case. The idea would be that if we have a method to solve your problem we could construct a solution to CDS in $G$ because the method could be apply for nodes in A or nodes in B.
> 0 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: How can I find $\Theta(log(m_1)+...+log(m_k))$ as related to $m$?
given: $$m\_1+m\_2+...+m\_k=m$$ How can I find $\Theta(log(m\_1)+...+log(m\_k))$ as related to $m$?

I know that i can doing that: $O(log(m\_1)+...log(m\_k))=O(log(m)+...+log(m))=O(k \cdot log(m))$ , but can I find something without $k$ ?

# Answer
The $\log$ function is concave so, by Jensen's inequality, $$\frac{1}{k}\sum\_{i=1}^k\log m\_i \leq \log\Big(\frac1k\sum\_{i=1}^k m\_i\Big)$$ i.e., $$\sum\_{i=1}^k \log m\_i \leq k\log\frac{m}{k} = k\\,(\log m - \log k)\\,,$$ which is basically what you got by bounding $\log m\_i\leq \log m$. We can't do any better than this because we could have $m\_1 = \dots = k\_m = \tfrac{m}{k}$, in which case $\sum\_i\log m\_i = k\log\tfrac{m}{k}$.

However, if $k$ is a fixed constant, then $k\log\tfrac{m}{k}=O(\log m)$.
> 2 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Is the isometric path cover problem NP-complete?
Isometric path (like geodesic) is yet another name for shortest path. An isometric path cover is a set $S$ of isometric paths such that every vertex $v ∈ V$ belongs to at least one isometric path of $S$. The isometric path cover problem is to find a minimum cardinality isometric path cover of $G$. Is the isometric path cover problem NP-complete for general graphs?

# Answer
This question is mentioned in a recent (2017) paper, Strong geodetic problem in networks: computational complexity and solution for Apollonian networks by Paul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, and Elizabeth Thomas. On page 8, they state:

> To our knowledge, the complexity status of the isometric path problem is not known.
> 3 votes

# Answer
The isometric problem is important because of the following reasons: The path cover problem is NP-complete. The induced path-cover problem is NP-compete. The status of the isometric path cover problem is unknown.
> 0 votes

---
Tags: algorithms, graphs, np-complete
---


# Question
Title: Does adding S->SS in a context-free grammar change the language to its Kleene star?
Let $L$ be the language generated by a context-free grammar whose start variable is $S$. Does adding $S \rightarrow SS$ in this grammar creating language $L^\*$, why? What about grammars in Chomsky normal form?

# Answer
As chi pointed out in the comment, since $\varepsilon\in L^\*$ and $\varepsilon$ may not belong to the new grammar, so adding $S\rightarrow SS$ does not always generate $L^\*$. It makes more sense to ask whether it generates $L^+$, so the following answer focuses on $L^+$.

---

# General Form

Consider the following grammar:

\begin{align} S&\rightarrow aSb\\ S&\rightarrow \varepsilon \end{align}

It generates the language $L=\\{a^nb^n\mid n\in\mathbb{N}\\}$.

Now after adding $S\rightarrow SS$ in this grammar, the string $aababb$ can be generated by the grammar but it does not belong to $L^+$.

# Chomsky Normal Form

Easy to see $L^+$ can be generated by the new grammar. Now for any string $s$ generated by the new grammar, we can prove $s\in L^+$ by mathematical induction on the depth of its parse tree. Consider the derivation process of $s$.

If the first derivation does not use the rule $S\rightarrow SS$, we can conclude $S$ does not show up in the following derivation since $S$ does not show up in the right hand side of a CFG of Chomsky normal form. As a result, $s\in L$.

If the first derivation uses the rule $S\rightarrow SS$, the strings generated respectively by the two $S$'s in the right hand side must belong to $L^+$ due to inductive assumption, thus $s$, which is formed by concatenating the two strings, also belongs to $L^+$.
> 6 votes

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


# Question
Title: Complexity of CFG grammar for a regular language
I know that each regular language can be generated by a CFG. This makes, in one sense at least: context-free languages more general than regular languages.

Are there known results about the 'complexity' of regular languages in the CFG context? For example, is it true that every regular language can be generated by an unambiguous LL(1) grammar? Or is something similar true?

The general question above comes from the attempts I made to build a 'simple' grammar generating $L=\\{(ab)^i|(ba)^i : i\geq 0\\}$. None of the grammars I could build were 'simple'.

# Answer
> 5 votes
A regular grammar is context-free. So regular languages are context-free.

Every regular language has a right regular grammar, which is simply derived from a finaite state automaton for that language.

Every regular language can be recognized by a deterministic finite state au tomaton. From that deterministic FSA you can construct a right regular grammar which is LL(1) since you can decide what to do for parsing by simply looking at the terminal on the rules applicable at any time. There always is only one such rule. Actually you do not even need the pushdown, and use the non-terminal for the states. (this is a bit informal, but it is so simple being formal seems silly).

The key part is producing the deterministic FSA.

So, yes, every regular language can be generated by a LL(1) grammar.

A LL(1) grammar is always unambiguous, as it allows constructing a deterministic push-down automaton. So it is unnecessary to specify that it is unambiguous.

As for your language, it seems strangely defined, and I wonder whether you copied that correctly. What is the "$+$" supposed to mean ?

# Answer
> 2 votes
Regular languages are described by regular grammars. These come in two varieties: left-regular and right-regular. Right-regular grammars encode the computation of an NFA: the non-terminals represent the states of the NFA, and the rules encode the transitions. Left-regular grammars do everything in reverse. This is the simple class of grammars you are looking for.

# Answer
> 2 votes
As beginner in CS, I also became interested in CFG descriptional complexity. First of all I considered its variables complexity and got the following results for the particular language $L = (ab)^\* + (ba)^\*$:

1. There exists CFG with two variables which generates $L$
2. There exist no CFG with one variable which generates $L$

For proving (1) we may just consider the following CFG $$ S \rightarrow bAa \mid A , \\, A \rightarrow abA \mid \varepsilon$$ The second proposition is a bit more tricky. Suppose that there exists CFG $G = (\\{S\\}, \\{a, b\\}, P, S)$ such that $L = L(G)$. Every production is $S \rightarrow \alpha$ for some $\alpha \in \\{a, b, S\\}^\*$. Say, $\alpha$ contains $k$ instances of $S$; for every $u\_1, \ldots u\_k$ define the $\widetilde{\alpha}(u\_1, \ldots u\_k) \in \\{a, b\\}^\*$ to be the word obtained from $\alpha$ by substituting $u\_1$ into the first instance of $S$, $u\_2$ into the second and so on. Then $u\_1, \ldots u\_k \in L$ implies $\widetilde{\alpha}(u\_1, \ldots u\_k) \in L$: as $L$ is generated by $G$, one can derive $\widetilde{\alpha}(u\_1, \ldots u\_k) \in L$ by using $S \rightarrow \alpha$ and then deriving every $u\_i$ from $S$'s. By using that we can prove that in right-hand side of every production $S$ can't be followed immediately by any symbol:

* if $S$ is followed by $a$, we have subword $Sa$ in $\alpha$, then we can derive $ba$ from $S$, thus we can derive the word which contains two $a$'s in the row, which obviously doesn't lie in $L$;
* if $S$ is followed by $b$, having subsword $Sb$ of $\alpha$ we can derive $ab$ from $S$ and thus obtain the word which contains two $b$'s in the row;
* if we have subword $SS$ of $\alpha$, we can derive $ab$ from the first $S$ and $ba$ from the second.

Also $S$ can't follow neither letter nor $S$ in right-hand side of every production. So $G$ can only have productions of sort $S \rightarrow S$ and $S \rightarrow w$ for $w \in L$. Thus $L(G)$ is finite, which is contradiction.

You can also look to the Grushka's paper: https://www.sciencedirect.com/science/article/pii/S0019995871905195

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


# Question
Title: Count nodes within K-distance from all nodes in a set
The problem is - Given an undirected tree with some marked nodes in a set and a positive number K. We need to print the count of all such nodes which have distance from all marked nodes less than K.

My first approach-

I ran bfs on every from each marked node given in the set and takes the intersection of the respective answers. The time complexity of this solution if there are m notes in the set would be O(m\*(V+E)). Can it be further optimized ?

My second approach-

If I find two nodes from set which are maximum distance from each other, I can say that all the nodes which are a distance less than k from these two nodes will also be at a distance less than k from other marked nodes in the set. Now, I have to apply bfs at only those two extreme nodes. But, the problem is How to find two nodes from set which are maximum distance from each other? I can only think of floyd warshall over here but that would be O(V^3).

What would be the most optimal solution to this problem?

# Answer
> 1 votes
Add a new node(let's say s) and connect it to all the marked nodes in the set. Then, find all the nodes which are at a distance less than k+1 from s and subtract number of marked nodes from it. T(n)=O(V+E)

In the second approach, we can actually find the two nodes (let's say uand v) with maximum distance between them in O(V+E). How do we find those vertices? Pick a vertex w and place it in a queue. While the queue is non-empty add the neighbors of the next vertex in the queue to the end of the queue. When the queue is empty, take note of the most recently removed vertex. This will be u. Perform the procedure again and you will have v. Check this link for proof. https://stackoverflow.com/questions/9951363/finding-the-root-that-minimize-tree-depth

---
Tags: algorithms, graphs
---


title: Simplification of regular expression

text:
# Question
Title: Simplification of regular expression
I have some issue with how to simplify regular expression. I cannot find any suitable method to approach these types of problems.

How would one approach simplifying the following regular expression:

(01(11)\* (10+0)+00+1)\* 0(11)\*

Thanks in advance,

Erik

# Answer
Minimizing a regular expression is PSPACE-hard, so there is no general method that is generally applicable and can be completed in a reasonable amount of time. You'll need to inspect each individual situation on a case-by-case basis.

If you want to read about general methods, see https://cstheory.stackexchange.com/q/31630/5038 and https://cstheory.stackexchange.com/q/12361/5038. CSTheory has a nice blog post with an overview of the field. The alternative is to stare at that regular expression, understand very well what language it recognizes, and write down a shorter regexp. You might be able to find some simplifications that work for that particular case, even though they are not general.
> 7 votes

# Answer
It is indeed possible to simplify your expression. Proceed as follows:

(1) Compute the minimal automaton of your language:

(2) Observe that your language is $P^\*0(11)^\*$, where $P^\*$ is the label of all paths from $1$ to $1$. Then $P$ is known to be a prefix code, which is easy to compute by unfolding the minimal automaton:

Thus $P = (01^\*0 + 1)$ and your language is $(01^\*0 + 1)^\*0(11)^\*$.
> 5 votes

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


# Question
Title: Calculate the number of trailing zeros in equation f(n) = f(n-1) * f(n-2) where f(0) and f(1) are any given arbitary numbers
This question is doable if you can calculate the number by multiplying `f(n-1) and f(n-2)`.

**Is it possible to do this question if we entirely want to skip multiplying these 2 numbers and still be able to calculate say the number of trailing zeros in f(20).**

Why do I want to skip multiplying these two numbers?
Because as this function grows exponentially, so does the value. We might get an integer overflow on some languages. Hence.
Also, our aim is to calculate the number of trailing zeros and not calculate the number itself.

What I tried. To try and calculate trailing zeros and f(n-1) and f(n-2), So that I deduce the number of trailing zeros in f(n) and go on from there.

But to calculate trailing zeros in f(n-1), I need to know what f(n-1) is? Which is where my whole approach fails.

# Answer
> 4 votes
Assuming f(0) and f(1) are integers, find which powers of two and of five are factors of f(0) and f(1). The powers in f(n) can be calculated like a Fibonacci sequence and the number of trailing zeroes is the smaller of both sequences.

The Fibonacci series is defined by $fib(0)=0$, $fib(1)=1$, and for $n≥2$ we have $fib(n) = fib(n-2)+fib(n-1)$, so the series starts (0, 1, 1, 2, 3, 5, 8, 13 ...). If we start with different values and use the same recursion formula, we get for example the sequence (1, 0, 1, 1, 2, 3, 5, 8, 13...). If we define $fib(-1)=1$, then the n-th element of this sequence equals $fib(n-1)$.

The sequence starting with (x, y) and the same recursion formula (x, y, x+y, x+2y, 2x + 3y ...) equals $x \cdot fib(n-1) + y \cdot fib (n)$.

Let $f(0)$ have the factor $2^x$ and $f(1)$ the factor $2^y$ and no higher power of two, then $f(n)$ has the factor $2^z$, where $z = x \cdot fib(n-1) + y \cdot fib (n)$.

Likewise, let $f(0)$ have the factor $5^a$ and $f(1)$ the factor $5^b$ and no higher power of five, then $f(n)$ has the factor $5^c$, where $c = a \cdot fib(n-1) + b \cdot fib (n)$.

The number of trailing zeroes in $f(n)$ is

```
    $min(z_n, c_n)$ where

    $z_n = x \cdot fib(n-1) + y \cdot fib (n)$
    $c_n = a \cdot fib(n-1) + b \cdot fib (n)$

```

# Answer
> 2 votes
You can prove by induction that your sequence is actually f(n) = $2^{u\_n}$ with $u\_n$ the n-th term of the fibonacci sequence. The number of trailing zeroes in base 2 is thus $u\_n$.

In base 10 however, the number of trailing zeroes will always be 0, because for any n, there is no 5 in the prime decomposition of f(n).

---
Tags: dynamic-programming, recurrence-relation, program-optimization
---


title: Is Coq synthetic or analytic?

text:
# Question
Title: Is Coq synthetic or analytic?
In CMU's HoTT course, lecture 1, which can be found here: https://scs.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=0945cc7f-48b7-4803-81af-e7193a3f461d

At 33:52, Harper was giving parallel comparison between synthetic theories and analytic ones, and when he reached PL theory, he said Coq is analytic and said Coq only proves a language in its grammar but not the parser itself.

I have a strong desire to disagree somehow but I don't have a clear idea why I would want to do that. I believe that Coq is very synthetic, so are any other proof assistants based on dependent type theory, because all these languages do nothing but build programs. We can also express axiomatic algebra in Coq by using type classes for example, and concretize whenever suitable. This pattern is especially the case in Agda.

So my question is, was Harper right? If he's right, which part of my view causes my misunderstanding?

# Answer
> 12 votes
The remark is about one specific usage of Coq, namely formalization of programming language theory.

Let us first make clear the distinction between *synthetic* and *analytic*:

* In a *synthetic* approach to a subject we say that there are things whose basic properties and structure are postulated in one way or another. We then study these things by relying only on the postulated properties and structure.
* In an *analytic* approach to a subject we discover that there are certain things. To learn more about them, we take them apart, we study how they are made and we analze them. This way we discover their properties and structure.

How would one study a programming language in these two ways?

Synthetically, we would postulate the constituent parts of the language (there are terms, there are types), their basic structure (these are the ways of building terms) and basic properties. We do not ask what the terms and type are made of, or whether the terms are trees or strings, or whether the collection of types is built in a particular way.

Analytically, we would start with a mathematical setup that allows us to do many things, such as use inductive definitions to construct mathematical objects. We woudl build terms and types as particular inductively defined sets or types. Then we would study their structure, how we can transform them, etc.

It should be clear that Coq is of the analytic kind. When you implement a programming language in Coq, you define inductive types of terms and types. Then you analyze them using induction, define operational semantics as a recursive function on the syntax of terms, etc.

On the other hand, Twelf is of the synthetic kind. We postulate that there is a type of terms and a type of types, but we do *not* tell Twelf that these are inductive types (there's no way to say that in Twelf). We define operational semantics by providing basic transition rules. There is no mention of recursively defined functions (there's no way to define functions in Twelf), we just rely on the postulates that we wrote down.

You should compare the above situation to planar geometry. Hilbert's approach to geometry is synthetic (but his ideas are rooted in Euclid), Descartes' are analytic. The analytic geometry is so called because a line is not a primitive concepts: it has an inner structure, namely it is a set of points.

---
Tags: type-theory, proof-assistants, philosophy
---


# Question
Title: Find the smallest binary digit multiple of given number
I was reading an article on Find the smallest binary digit multiple of given number. The problem is - We are given a decimal number N, we need to find the smallest multiple of N which is binary digit number.

There is an optimization done i.e. if a string with same mod value is previously occurred we won’t push this new string into our queue. The explanation given is-

Let x and y be strings, which gives same modular value with n. Let x be the smaller one. let z be another string which when appended to y gives us a number divisible by N. If so, then we can also append this string to x, which is smaller than y, and still get a number divisible by n. So we can safely ignore y, as the smallest result will be obtained via x only.

How can we say that, we can also append this string to x, which is smaller than y, and still get a number divisible by n ?

And how can we say that the smallest result will be obtained via x only?

# Answer
> 1 votes
No idea where you got that 9 from, in the last line of the question.

Having said that, You have to know that "concatenating" numbers is equivalent to multiplying the first number by a power of 10, followed by adding the second number. E.g. 42|7 = (42\*10)+7.

Now obviously 42 is divisible by 6, but therefore so is 420. Furthermore, 42 mod 5 = 2, therefore 420 mod 5 = 20 mod 5. "42 is divisible by 6" in fact means "42 mod 6 = 0"

---
Tags: algorithms, graphs
---


# Question
Title: Complexity of Longest Palindromic Subsequence Algorithm
I'm trying to find the longest palindromic subsequence for any string and I've tried two approaches:

1. Recursive Algoritm
2. Dynamic Programming

Dynamic programming should be the better option in this case because of the time complexity but the time complexity of both algorithms is $O(n^2)$. My question is if the time complexity is the same for both algorithms, why is the dynamic programming approach considered better than recursive solution? I'm following the algoritms in this post. It says that the time complexity of dynamic programming algorithm is much better than the worst case time complexity of naive recursive implementation. What could be the worst case?

# Answer
The dynamic programming approach is indeed `O(n^2)`. However, the recursive solution is exponential in `n`: any time two characters don't match, a subproblem of size `k` is converted into `2` subproblems of size `k-1` each. It's easy to see that, with all letters different, this produces a complexity of `O(2^n)`.

Here is the example from the page you mention, modified to count and output the number of calls. A local copy to prevent link rot:

```
#include <stdio.h>
#include <string.h>

int max (int x, int y) {return (x > y) ? x : y;}

int count;

int lps (char * seq, int i, int j)
{
   count += 1;
   if (i == j)
      return 1;
   if (seq[i] == seq[j] && i + 1 == j)
      return 2;
   if (seq[i] == seq[j])
      return lps (seq, i + 1, j - 1) + 2;
   return max (lps (seq, i, j - 1), lps(seq, i + 1, j));
}

int main ()
{
    char seq [] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
    for (int n = 1; n <= 26; n++)
    {
       count = 0;
       printf ("n = %d: answer = %d", n, lps (seq, 0, n - 1));
       printf (", count = %d\n", count);
    }
    return 0;
}

```

The output is:

```
n = 1: answer = 1, count = 1
n = 2: answer = 1, count = 3
n = 3: answer = 1, count = 7
n = 4: answer = 1, count = 15
n = 5: answer = 1, count = 31
...
n = 24: answer = 1, count = 16777215
n = 25: answer = 1, count = 33554431
n = 26: answer = 1, count = 67108863

```
> 3 votes

---
Tags: algorithms, time-complexity, strings, subsequences
---


# Question
Title: Convert for loop into math sigma notation
Have some code (written in C), need the equivalent notation for mathematics. Is it possible using if-statements and sigma notation for this, and if so, how?

```
int res = 0;
for (int i=0; i < (N/2)+1; i=i+1)
  if (N % pow(2, i) == 0) res = i;

```

I have gotten as far as:

$$ \sum \_{i=0}^{{N\over2}+1}\\:(N \mod 2^i )$$ *(missing the == 0 and res = i)*

Ideas or a solution are welcome.

# Answer
> 2 votes
Let me define $$f(x) = \begin{cases} 0 & x \ne 0 \\ 1 & x = 0\end{cases}$$ Now it is $$ \sum \_{i=0}^{{N\over2}+1}\\:f(N \text { mod } 2^i)$$ The code calculates how many times number is divisible by two (which by the way could be simplified to checking number of trailing zeros in binary representation, say hacky method x & -x).

You can define {N, 2} for the highest power of a prime 2 that divides N, and it is the valid notation. There are other approaches and notations of greatest power of two dividing N at MathOverflow.

---
Tags: notation, c
---


# Question
Title: A question about proving Rice's Theorem by reducing it to the Halting Problem
I've read the definition for Rice's Theorem, here's the one from Wikipedia:

> In computability theory, Rice's theorem states that all non-trivial, semantic properties of programs are undecidable.

The classical proof for proving Rice's Theorem is on Wikipedia, which is similar to other sources.

However, I have a problem with this proof, made clear (hopefully) in the paragraphs following.

This proof goes like this:

> if we had an oracle for deciding these properties of program behavior, we would be able to use it to solve the Halting Problem, but the Halting Problem is undecidable, so an oracle for deciding these properties cannot exist either.

However, as far as I know, the impossibility of the Halting Program only occurs if the program checking whether something halts or not is trying to prove the hypothetical `does_it_halt(a, i)` wrong by using self-referencing tricks. But, in this proof, the oracle that is trying to decide the property is not trying to do that. So, it should be able to do its job without solving the Halting Problem.

I had some hope at the beginning that this proof may be wrong, but since it is apparently the "classical" proof for proving Rice's Theorem, I must be missing something. What is it that I am missing ?

# Answer
> However, as far as I know, the impossibility of the Halting \[Problem\] only occurs if the program checking whether something halts or not is trying to prove the hypothetical `does_it_halt(a, i)` wrong by using self-referencing tricks. But, in this proof, the oracle that is trying to decide the property is not trying to do that. So, it should be able to do its job without solving the Halting Problem.

The proof shows that, if we had a machine $M$ to decide a nontrivial semantic property, we can craft another machine $N$ to solve the Halting problem.

With "$N$ solves the Halting problem" we mean that $N$ can decide the termination of absolutely any other Turing machine, including those using "self-referencing tricks" -- no exceptions.

In a nutshell, "for all" means "for all". If we show that a machine decides a problem, then it must always do its job on all inputs. The mentioned proof crafts a machine $N$ which does not "decide the Halting problem, except for self-referencing cases" (whatever that might actually mean in formal terms). $N$ is proved to work "for all" inputs.

By the way, it's a common misconception to think that we actually detect when a program is "self-referencing", and that we could work around the impossibility of deciding the halting problem by weakening the goal to "decide whether $T$ halts on input $x$, as long as there is no self-referencing". What actually happens is that there are infinitely many machines $U$ equivalent to $T$ we could use for the "self-referencing", and (by Rice!) deciding whether $T$ and an arbitrary $U$ are equivalent or not is impossible. No algorithmic "syntactic inspection" on two programs can hope to decide whether they are equivalent on all cases.

Indeed, at first the self-referencing trick looks as a quite unsatisfactory negative proof, making one think that it could be worked around easily by just excluding that case. However, it is far more general than it looks at first.
> 1 votes

---
Tags: computability, undecidability, rice-theorem
---


# Question
Title: Turing machine that does not halt on any input
I'm struggling to find a way to show that $$T = \\{ \langle M \rangle\mid M \text{does not halt on any input}\\}$$ is undecidable. Should I use reduction? If so, reduce this to what &ndashp the halting problem?

# Answer
> 2 votes
To use reduction, you would need to show that the halting problem reduces $T$, not the other way around.

The reduction* in this case is a standard one. You want to know if $M$ halts on input $w$ but all you have is this lousy T-shirt a procedure that tells you if a machine loops on every input. So you construct a machine $M'$ such that does the same thing on every input, so that whether or not $M'\in T$ tells you whether or not $M$ halts on input $w$.

* Well, strictly *a* reduction: if there's one, there are infinitely many.

---
Tags: turing-machines, undecidability
---


# Question
Title: Would a modern processor/ALU process data bit or byte wise?
We look at 32 bit and 64 bit systems with octal-core processors. What does all that mean? As in, does it have 8 processors that operate bit wise? Or do they all operate on 32/64 bit blocks. I was studying Crypto with stream and block ciphers. And this has been confusing me now. Also, is it fair to say that a computer has no value for "bytes" as there aren't anything more than our way of grouping bits to make them more convenient to read?

# Answer
> 1 votes
Modern processors have 32/64 bits integer and 32/64/80 bits floating-point registers and ALUs. With the addition of SIMD instructions, extra vectorized ALUs are available and can perform operation on up to 64 bytes or 32 shorts (16 bits) or 16 ints (32 bits) or 8 long ints (64 bits) simultaneously and similar figures in floating-point (hence 512 bits at a time - Intel AVX).

A core is a full processing unit packaged in the same physical (multi-)processor.

So in a way, you can say that an octo-core can process 4096 bits of data at a time.

---

It is not fair to say that a processor ignores bytes, because the arithmetic operations need to know how many useful bits there are, to handle borrows, carries, overflows... Not to mention the floating-point data types, such that the value is split in several bit fields with different roles (sign, exponent, mantissa). In fact, a processor distinguishes dozens of data types of various lenghts.

It would be more true to say that processors don't known about bits because these are never handled individually, but as a minimum grouped in bytes. Even the very first microprocessor in history, the 4004, was handling nibbles (4 bits at a time).

---
Tags: computer-architecture
---


# Question
Title: Show how lack of universe levels would create contradiction in homotopy type theory (in Agda)
The homotopy type theory book claims in section 1.3 that "As in naive set theory, we might wish for a universe of all types" but from this one could "deduce from it that every type, including the empty type representing the proposition False, is inhabited"

The reference that it gives uses notation that I don't understand, however.

**Could someone write invalid Agda code which produces a element of $\bot$, but which would be valid if Agda had a single universe that contains itself?**

# Answer
> 8 votes
The problem is not specific to homotopy type theory. In type theory in general, if there is a type of all types, then every type is inhabited. This was shown first by Girard who encoded the Burali-Forti paradox in type theory.

A simplification of the paradox was found by Hurkens. Here is Agda code for it, and here is Coq code.

---
Tags: dependent-types, homotopy-type-theory
---


title: Water Jug Problem

text:
# Question
Title: Water Jug Problem
I was reading an article on Water Jug Problem. The problem is -You are given a m litre jug and a n litre jug where 0 \< m \< n. Both the jugs are initially empty. The jugs don’t have markings to allow measuring smaller quantities. You have to use the jugs to measure d litres of water where d \< n.

I solved the problem using recursion that at every time I can do some possible number of operations, I try to perform all those operations and if I reach to some previous state, then I return from it. The time complexity of this solution is O(m\*n).

Now, the method in the article says that the problem can be modeled by means of Diophantine equation of the form mx + ny = d which is solvable if and only if gcd(m, n) divides d. Also, the solution x,y for which equation is satisfied can be given using the Extended Euclid algorithm for GCD.

Then, we apply the following algorithm to find the solution-

1. Fill the m litre jug and empty it into n litre jug.
2. Whenever the m litre jug becomes empty fill it.
3. Whenever the n litre jug becomes full empty it.
4. Repeat steps 1,2,3 till either n litre jug or the m litre jug contains d litres of water.

So, What is the intuition behind these 4 steps, that when they are done in this order they will always give the right answer?

Moreover, we are not using x and y that we found using the extended euclidean, then why are we finding them?

# Answer
> 2 votes
The numbers $x$ and $y$ will turn up in the algorithm as the number of times you fill and empty the two jugs. You don't need to know them if you can tell when you have $d$ liters of water in one of the jugs.

But if you can't tell when you have $d$ liters (since the jugs have no markings), you'll need to count the fillings and emptyings. You'll fill the size $m$ container $x$ times. You'll empty the size $n$ container $-y$ times ($y$ will be negative, so $-y$ is positive and suitable for counting). Once you've done the respective operations the right number of times, you'll have $d$ liters of water left.

---
Tags: algorithms, recursion
---


# Question
Title: Will this program terminate for every Integer?
In a Part Test for GATE Preparation there was a question :

```
f(n):
     if n is even: f(n) = n/2
     else f(n) = f(f(n-1))

```

I answered "It will terminate for all integers", because even for some negative integers, it will terminate as **Stack Overflow Error**.

But my friend disagreed saying that since this is not implemented code and just pseudocode, it will be infinite recursion in case of some negative integers.

Which answer is correct and why?

# Answer
The correct answer is that this function does not terminate for all integers (specifically, it does not terminate on -1). Your friend is correct in stating that this is pseudocode and pseudocode does not terminate on a stack overflow. Pseudocode is not formally defined, but the idea is that it does what is says on the tin. If the code doesn't say "terminate with a stack overflow error" then there is no stack overflow error.

Even if this was a real programming language, the correct answer would still be "does not terminate", unless the use of a stack is part of the definition of the language. Most languages do not specify the behavior of programs that might overflow the stack, because it's difficult to know precisely how much stack a program will use.

If running the code on an actual interpreter or compiler causes a stack overflow, in many languages, that's a discrepancy between the formal semantics of the language and the implementation. It is generally understood that implementations of a language will only do what can be done on a concrete computer with finite memory. If the program dies with a stack overflow, you're supposed to buy a bigger computer, recompile the system if necessary to support all that memory, and try again. If the program is non-terminating then you may have to keep doing this forever.

Even the fact that a program will or will not overflow the stack is not well-defined, since some optimizations such as tail call optimization and memoization can allow an infinite chain of function calls in constant-bound stack space. Some language specifications even mandate that implementations perform tail call optimization when possible (this is common in functional programming languages). For this function, `f(-1)` expands to `f(f(-2))`; the outer call to `f` is a tail call so it doesn't push anything on the stack, thus only `f(-2)` goes onto the stack, and that returns `-1`, so the stack is back to the same state it was in at the beginning. Thus with tail call optimization `f(-1)` loops forever in constant memory.
> 49 votes

# Answer
If we look at this in terms of the C language, an implementation is free to replace code with code that produces the same result in all cases where the original doesn't invoke undefined behaviour. So it can replace

```
f(n):
   if n is even: f(n) = n/2
   else f(n) = f(f(n-1))

```

with

```
f(n):
   if n is even: f(n) = n/2
   else f(n) = f((n-1) / 2)

```

Now the implementation is allowed to apply tail recursion:

```
f(n):
   while n is not even do n = (n-1) / 2
   f(n) = n/2

```

And this loops forever if and only if n = -1.
> 5 votes

---
Tags: algorithms, recursion, pseudocode
---


# Question
Title: How many candidate keys are there in the table shown below?
One candidate key is (report\_no, author\_id). What are the other candidate keys?

# Answer
> 0 votes
"We have to consider all the relations that might be assigned to a relvar to determine whether a certain set of attributes is a candidate key. ... However, we might be able to conclude from such a relation that a certain set is not a candidate key, " as it says in the first place I looked

"The set of all candidate keys can be computed e.g. from the set of functional dependencies. "

So are you told the functional dependencies for this table? Or anything about the meaning or structure of the contents?

I notice looking at just columns `{report_no, editor, dept_no, dept_name, dept_address}`, the first three rows of the table have same content; rows 4 to 6 have the same content. Is that an accident, or a consequence of the structure?

*If* `{report_no, author_id}` is a CK (how are you determining that?), then it's looking like any one of those columns with `author_id` could be a CK.

Similarly, looking at this content the columns `{author_id, author_name, author_addr}` show a pattern. Perhaps there's a functional dependency? It's looking like `author_name` with any one of the 5 left columns could be a CK.

There's only one column that definitely can't be an element of a candidate key, going by this content. That's `author_addr`: look at the rows with `author_addr = mathrev`. There's no pattern of content in other columns for those rows.

I notice the table is labelled "(1NF)". I'd take that as a hint to find out about 2NF, 3NF.

# Answer
> -1 votes
One candidate key is (report\_no, author\_id).

It can uniquely determine a row in the REPORT table shown above.

Second candidate key is (dept\_no, author\_id).

It can also uniquely determine a row in the REPORT table shown above.

---
Tags: database-theory, databases
---


# Question
Title: Defining decision-problem complexity classes by counting branches of a polynomial-time NTM
This answer on another SE community discusses the concept of a "counting complexity class". As far as I can tell, the author is using that term in a slightly nonstandard way: most sources (PS format) use that term to refer to complexity class like #P of *counting* problems that count the accepting branches of a polynomial-time nondeterministic Turing machine (NTM). The author of the linked answer seems to be using the term to mean a complexity class **C** for *decision* problems such that **C** can be defined in terms of this count. Am I understanding this correctly?

If so, then I believe that all of the following counting complexity classes (in the latter sense of the term) can be defined in the form "**C** is the set of decision problems for which there exists a polynomial-time NTM such that ...". Am I completing the sentences correctly for each counting complexity class?

1. **P**: if the answer is yes then every branch accepts, and if the answer is no then every branch rejects. (My answer below explains why this definition is equivalent to the usual one.)
2. **RP**: if the answer is yes then a fraction $p$ of the branches accept, where $p$ is a positive number that does not depend on the input size. If the answer is no then every branch rejects.
3. **co-RP**: if the answer is yes then every branch accepts. If the answer is no then a fraction $p$ of the branches reject, where $p$ is a positive number that does not depend on the input size.
4. **BPP**: if the answer is yes then a fraction *p* of the branches accept, where $p \> 1/2$ does not depend on the input size. If the answer is no then a fraction *q* of the branches reject, where $q \> 1/2$ does not depend on the input size.
5. **NP**: if the answer is yes then at least one branch accepts. If the answer is no then every branch rejects.
6. **co-NP**: if the answer is yes then every branch accepts. If the answer is no then at least one branch rejects.
7. **C**$ \_=$**P**: if the answer is yes then exactly half the branches accept. If the answer is no then the fraction of accepting branches does not equal $1/2$.
8. **PP**: if the answer is yes then most branch accept, and if the answer is no then at least half the branches reject.

One advantage of this formulation is that it makes obvious the class inclusions **P** $\subset$ (**co-**)**RP** $\subset$ **BPP** (using this trick) $\subset$ **PP** and (**co-**)**RP** $\subset$ (**co-**)**NP** $\subset$ **PP** (using Buchfuhrer's trick here).

**Note:** In order to make this question clearer and more useful for future viewers, I have edited it to make every definition correct. The definitions in the original version of my question (available in the question history) had a few errors, which Ariel pointed out in their answer.

# Answer
In the abstract of Counting classes: thresholds, parity, mods, and fewness”, by Beigel and Gill, any class of languages whose membership of some input $x$ can be determined by some function of $\\#M(x)$ (the number of accepting paths of the NTM $M$ on input $x$) is considered a counting class.

In regards to your "counting description" of some known classes, your characterization of $\mathsf{ZPP}$ is actually a description of $\mathsf{P}$ (there is no mentioning of the power of expected polynomial time over worst case polynomial time). Additionally, your description of $\mathsf{P}$ is not very clear, a Turing machine can be either deterministic or non deterministic (those are different models of computation), so there is no NTM which is "actually deterministic". It is not clear how to give a counting characterization of $\mathsf{ZPP}$, since it differs from the rest of the classes by relaxing the polynomial time property.

Additionally, note that in the NP/coNP case you have an equivalence, i.e. $x\in L$ iff there exists some accepting path/ iff all paths are accepting. Requiring only one implication results in a stronger class.
> 1 votes

# Answer
Ariel explained to me in chat the way to see why the definition 1 above is equivalent to the usual definition of **P**, which is the set of problems solvable by a polynomial-time deterministic Turing machine.

The $\Leftarrow$ direction is trivial: just choose a formally nondeterministic Turing machine that never branches and is functionally identical to the deterministic Turing machine. (I tried to choose my words carefully ... Ariel feels strongly that such a machine is not in fact deterministic, but nondeterministic with a transition relation that happens to to be single-valued.)

The $\Rightarrow$ direction is also easy: since every branch of the NTM gets the right answer, just make it deterministic by arbitrarily choosing a single branch and choosing a DTM equivalent to that branch.
> 0 votes

---
Tags: complexity-theory, complexity-classes, randomized-algorithms, counting
---


# Question
Title: Is there an $O(n^2)$ or $O(n^3)$ time algorithm to check if a number is a sum of $k$ elements of sorted array?
> Let $A$ be a sorted array of $n$ positive integers (sorted in non-decreasing order, that is there can be equal consecutive elements). Can we check whether some positive integer $x$ is a sum of $k$ elements of $A$ in $O(n^2)$ or $O(n^3)$ time complexity? If yes what would be the pseudocode?

This seems to be a knapsack problem to me and according to Wikipedia it's an NP-complete problem. So even if the array was unsorted in the first place and we wanted to sort it it would take $O(n\log n)$ time which doesn't really help if the problem is NP-complete anyway. Yet I wonder if some optimization may be made to achieve better time.

Please treat $x$ and $k$ as constants, for running time analysis.

# Answer
> 1 votes
It depends on the numbers in the array. For example if all array elements are positive integers, and the requested sum is S, then O(nS) is easy.

# Answer
> 1 votes
If $x$ and $k$ are to be treated as constants, as you propose, then there is a solution with running time $O(n)$: use dynamic programming, and let $B\[s,i,j\]$ indicate whether there is a combination of $i$ elements from $A\[1..j\]$ that sums to $s$. The $B$ array can be filled in, in $O(nkx)=O(n)$ time, using dynamic programming.

In practice I'm skeptical that one can reasonably consider $x,k$ to be constants; unless $x,k$ are particularly small, calling this $O(n)$ running time might give a misleading impression about how fast it will be.

# Answer
> 1 votes
If you allow to use every number from the array only once then it is indeed a knapsack problem. If you can use every number multiple times then you consecutively generate sets of number which can be generated with sums of 1, 2, 3 ... k elements of the array. Every step is `O(n*x)`. Overall complexity will be `O(k*n*x)`.

---
Tags: algorithms, time-complexity, knapsack-problems
---


# Question
Title: Efficient method to compute weighted Jaccard similarity?
I'm looking for pointers for high-performance calculation of the weighted Jaccard similarity between two sparse count vectors. I would like to speed up my code by at least 5x.

I have a database of about 2 million count vectors. Each count vector is sparse, with about 50 non-zero terms in the range 0-(2\**32-1). (The number of terms ranges from 1 to 230, the 1st quartile is 41 and the 3rd quartile is 58. The count ranges from 1 to 230.) Technically these are Morgan count fingerprints for molecules, generated by the RDKit cheminformatics toolkit.

The database is used to find similar molecules. Someone enters a molecule, which is converted into a new count vector, and the nearest 100 or so vectors are found, and the associated molecules returned. The similarity could be as low as 0.4 and still be meaningful.

I have previously implemented Jaccard search for the binary case, where the features have been reduced to a bitstring of length 1024 bits or so. I used several papers (eg, 10.1021/ci600358f, 10.1093/comjnl/bxx046, 10.1021/ci200235e) to help get the performance. The second uses AVX2 instructions.

I would like similar pointers for how to improve weighted Jaccard search performance.

Here is what I do now. I store the count vector as a vector of keys and a vector of counts, both uint32\_t for now. I store the keys in sorted order.

I want to compute the weighted Jaccard similarity between these vectors. This is defined in the usual way, described at https://en.wikipedia.org/wiki/Jaccard\_index#Generalized\_Jaccard\_similarity\_and\_distance . The implementation is something like:

```
intersect_count = sum(min(count1[i], count2[j]))
     where key1[i] == key2[j];
union_count = sum(count1[i]) + sum(count2[j])
similarity = intersect_count / (union_count - intersect_count)

```

The tricky part is to find where key1\[i\] == key2\[j\]. Since I stored them in sorted order, I can compare them like doing a merge sort. If they are equal then I can compute the min of the corresponding counts. Otherwise if key\[i\] is smaller then I increment i, otherwise I increment j.

Here's the heart of the method

```
/* earlier, union_count = sum of counts1 and counts2 */
k1 = keys1[f1];
k2 = keys2[f2];
f1 = f2 = 0;

while (1) {
  /* If the two keys match then increase the intersection count */
  /* and advance to the next keys */
  if (k1 == k2) {
    if (counts1[f1] <= counts2[f2]) {
      intersect_count += counts1[f1];
    } else {
      intersect_count += counts2[f2];
    }
    f1++;
    f2++;
    if ((f1 == num_features1) ||
        (f2 == num_features2)) {
        goto end;
    }
    k1 = keys1[f1];
    k2 = keys2[f2];
    continue;
  }
  /* If the first key is smaller, advance it by one */
  if (k1 < k2) {  /* Profiling says 20% of the time is spent here */
    f1++;
    if (f1 == num_features1) {
      goto end;
    }
    k1 = keys1[f1];
    continue;
  } else {
    /* otherwise, advance the other key by one */
    f2++;
    if (f2 == num_features2) {
      goto end;
    }
    k2 = keys2[f2];
    continue;
  }
}
end:
return ((double) intersect_count) / (union_count - intersect_count);

```

There's are a lot of branches in the code, which surely doesn't help. The profiler shows that 20% of the time is spend on integer comparison, which makes me wonder if vectorized approach, eg, with Intel intrinsics, might help.

Another approach might an inverted index. There is much work on finding the intersection of postings lists, which is related, but I need to find the sum of the intersection of weighted postings. My own attempt resulted in slightly faster code than the brute force one (0.3 instead of 0.5 seconds) but unlike the brute force one it cannot easily be parallelized.

I looked for previous work, since Jaccard similarity is so popular for a wide number of search domains, but failed to find any leads.

In principle a MinHash or other approximation might help, but we already use an approximation technique to map count vectors down to bit vectors for fast unweighted Jaccard search. We want an exact method so we can quantify the effect of the approximations.

I have also looked into LSH, but our similarity threshold is so low (0.5 or so) that I think the methods for high similarity search don't work, and that fast brute force search is the right way to take on the curse of dimensionality.

A suggestion of something to try, or a pointer to existing code, technical paper, or blog entry would be most helpful.

# Answer
This is exactly the problem for which locality-sensitive hashing was invented. In particular, MinHash looks perfect for your needs. You build up a sort of "index" once, which involves a linear scan through all the 2 million vectors in your database. Then, given a new vector $x$, you can quickly find all matches that have high Jaccard similarity with $x$, using that index -- it is much faster than comparing $x$ to each of the 2 million vectors in your database. You should be able to get huge speedups in this way.
> 1 votes

---
Tags: algorithms
---


title: P, NP Problem and Turing Machines

text:
# Question
Title: P, NP Problem and Turing Machines
My first question here, I think this will be an easy one.

As for definition:

NP: NP is the set of decision problems solvable in polynomial time by a theoretical non-deterministic Turing machine. (wiki)

P: P Contains all decision problems that can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time. (wiki)

(a) I thought, that you can convert every Non-deterministic Turing machine into a equivalent deterministic Turing machine ?

I am not sure about that I know it is possible with NFA's to DFA's.

But if (a) is true, wouldn't that mean that P=NP?

# Answer
> 3 votes
Yes, a non-deterministic Turing machine can be converted into an equivalent deterministic Turing machine, but it is not known that if a polynomial time non-deterministic Turing machine can be converted into an equivalent **polynomial time** deterministic Turing machine.

Note "equivalent" only means they accept the same language, it does not mean they run in the same time.

---
Tags: complexity-theory, turing-machines
---


title: Least fix point of CTL formula

text:
# Question
Title: Least fix point of CTL formula
In the book Logic in Computer Science on page 244, there is a proof that $\[\[E(\phi U\psi)\]\]$ is the least fixed point of $G(X)=\[\[\psi\]\] \cup (\[\[\phi\]\]\cap\mathop{\textrm{pre}}\_\exists(X))$. I don't get the idea of point 2. I tried to understand why this proof says that $\[\[E(\phi U\psi)\]\]$ is the least fixed point of $G$.

They prove that $G^{k+1}(\emptyset)\subseteq\[\[E(\phi U\psi)\]\]$ for each $k\geq0$.
This is fine, I understand each step on their the proof, I just don't understand why this proves that $\[\[E(\phi U\psi)\]\]$ is the least fixed point of $G$...

I can prove that $G^{k+1}(\emptyset)\subseteq S$ when $S$ is the group of all the states. $G$ is still the same function, and of course that for each such $i\geq0, G^i(\emptyset)\subseteq S$. This doesn't mean that $S$ is the least fixed point, or that each fixed point contains $S$.

So why this proof claims that $\[\[E(\phi U\psi)\]\]$ is the least fixed point of $G$?

# Answer
> 2 votes
They actually start by proving that $\[\[E(\varphi U\psi)\]\]=\bigcup\limits\_{k\ge 1}G^k(\emptyset)$.

You can see (or prove by induction for the general case) that repeated applications of $G$ starting with the empty set yields:

$G(\emptyset)=\[\[\psi\]\]$,

$G^2(\emptyset)=\[\[\psi\]\]\cup (\[\[\varphi\]\]\cap pre\_\exists(\[\[\psi\]\]))=\[\[\psi\]\]\cup\left\\{s\in S | s\in\[\[\varphi\]\] \land \exists s' \left(s\rightarrow s' \land s'\in\[\[\psi\]\]\right)\right\\}$

$\vdots$

$G^{i+1}(\emptyset)=G^i(\emptyset)\cup \left\\{s\in S| s\in\[\[\varphi\]\]\land\exists s' \left( s\rightarrow s'\land s'\in G^i(\emptyset)\right)\right\\}$

The union of the above sets exactly coincides with the definition of $\[\[E(\varphi U \psi)\]\]$. To conclude the proof, they use the fact that $G$ is montone and that $G^{n+1}(\emptyset)$ is a fixed point of $G$, thus $\bigcup\limits\_{k\ge 1}G^k(\emptyset)=G^{n+1}(\emptyset)$, which is the least fixed point of $G$.

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


title: What is $C_4$ + two "ears" called?

text:
# Question
Title: What is $C_4$ + two "ears" called?
A graph with $C\_3$ + 3 "ears" is called a net graph.

In general, $C\_n$ + $n$ pendant vertices are called sunlet graphs.

Is there a name for 4-sunlet graph minus two pendant vertices?

# Answer
> 4 votes
According to ISGCI this graph is known as "A".

Looking at some references, it also seems that there is really no common well-known name.

---
Tags: graphs, terminology
---


# Question
Title: Nondeterministic PDA for the following language with Kleene star
I had a question regarding converting a language with the Kleene star production into a PDA. Here's the particular language I was looking at in my textbook:

$$L = (aaa^\*bab)$$

My normal approach to constructing PDA's for languages would be to determine the pattern or rule of the language, and think to myself that it's sort of like counting the number of symbols using a stack, and determining whether the stack is empty at the end of the computation.

However, I'm not sure how to construct a PDA for languages like the one above where there isn't a particular rule regarding the $a^\*$ production.

How would one normally handle these types of situations? Thank you.

# Answer
I figured out the answer and hope this will help anyone with similar confusion in the future.

Since a pushdown automaton is essentially a finite automaton with an extra component called the stack which is used for storage, if we are presented with a regular language like the one given above, we simply need to create a PDA that does not use the stack. This concept confused me at first, but here's what I mean:

$$L = (aaa^\*bab)$$

$\space$

$$M = (Q, \Sigma, \Gamma, \delta, q\_0, z, F)$$ $$Q = \\{q\_0,\ q\_1,\ q\_2,\ q\_3,\ q\_4,\ q\_5\\}$$ $$\Sigma = \\{a,\ b\\}$$ $$\Gamma = \\{$\\}$$ $$z = \\$$$ $$F = \\{q\_5\\}$$

$\space$

$$\delta(q\_0, a, $) = \\{(q\_1,\ $)\\}$$ $$\delta(q\_1, a, $) = \\{(q\_2,\ $)\\}$$ $$\delta(q\_2, a, $) = \\{(q\_2,\ $)\\}$$ $$\delta(q\_2, b, $) = \\{(q\_3,\ $)\\}$$ $$\delta(q\_3, a, $) = \\{(q\_4,\ $)\\}$$ $$\delta(q\_4, b, $) = \\{(q\_5,\ $)\\}$$

$\space$

I'm not completely certain about the stack start symbol, because I've noticed some resources use it regardless, while others assume that at the beginning the stack is empty ($\lambda$) and push the start symbol at the first step.

Anyway, I hope this answer helps anyone else.
> 2 votes

---
Tags: pushdown-automata, kleene-star
---


# Question
Title: Is there an algorithm to find out if a truthtable can be represented as 2-sat, and if so find its 2-cnf?
I know that not all truthtables have a corresponding 2-cnf representation, but is there a way to find out if a given truthtable has a 2-cnf representation, and if so to find what that is?

# Answer
> 3 votes
This answer assumes that a *2CNF representation* of a function is a 2CNF (on the same set of variables) that agrees with the function on all inputs.

Let's say that a clause $C$ is *consistent* with a function $f$ if $\lnot C \Rightarrow \lnot f$. Let $C\_1,\ldots,C\_m$ be the collection of 2-clauses consistent with your function $f$. Then $f$ has a 2CNF representation if and only if $f = C\_1 \lor \cdots \lor C\_m$. This gives a quasilinear time algorithm for deciding whether $f$, given as a truth table, has a 2CNF representation.

---
Tags: satisfiability, 2-sat
---


title: Storing a playlist as plain text file

text:
# Question
Title: Storing a playlist as plain text file
**What are the disadvantages of storing a playlist as plain text in a text file?**

This is what I thought:

The main disadvantage of storing the play list as plain text is its simplicity. The basic conceptual structure of the rows of values can be very inefficient and inappropriate for data sets with complex structure. The low-level format of storing everything as characters with one byte per character is very inefficient in terms of amount of computer or phone memory required. It can also lead to massive redundancy (repetition of values). The speed of access and space efficiency for large data set is also not ideal. The second disadvantage is the fundamental structure of plain text file format means that each line of the file contains exactly one record or case in the data set. This only works well when a data set only contains information about one type of object. However, this is not the case as storing the playlist would mean that we also need to store all the information about the songs such as the name and song time. So there would be information about two different types of objects. A plain text file format does not allow for sophisticated data models. A plain text format is unable to provide appropriate representation of complex data structure like a playlist.

**Now my question is instead of storing the playlist as plain text in a text file, what would be a more suitable way of storing objects? Please explain. Thank you.**

# Answer
I don't see anything wrong with storing a playlist as a plain text file. Simplicity is not a disadvantage. It's likely to be more than efficient enough, given the size of a typical playlist (implement it and see!).
> 1 votes

---
Tags: data-structures, software-engineering
---


# Question
Title: Why doesn't Godel's Second Incompleteness Theorem rule out a formalizable proof of P!=NP?
I'm sure there must be something wrong with the following reasoning because otherwise a lot of P vs. NP research would be curtailed but I cannot determine my error:

For any fixed integer $k\>0$ define $$B\_k := \\{ \langle \varphi \rangle | \\; \varphi \\; \text{is a wff of ZF and has a proof of length} \\; \leq k{|\varphi|}^k \\; \\}$$

Now for all $k$, the language $B\_k$ is in NP since a valid proof for $\varphi$ of length $\leq k{|\varphi|}^k$ can be a NP-witness verified by an automated proof-checker in polynomial time. Furthermore, for sufficiently large enough $k$, $B\_k$ is NP-complete since SAT reduces to it: that is, for an instance $\phi$ of SAT make a corresponding wff of ZF $\varphi$ using existential quantifiers. Then a satisfying truth assignment of $\phi$ can be made into a formal proof of $\varphi$ of length polynomial in $|\varphi|$ since a truth assignment of $\phi$ is linear in $|\phi|$.

Now, if ZF is inconsistent, this means that there is a formal statement $\sigma$ such that both $\sigma$ and $\neg \sigma$ have proofs in ZF. As is well known, any other statement $\tau$ can then be derived from the contradictory conjunction $\langle \sigma \wedge \neg \sigma \rangle$ (that is by following the path: $$\langle \sigma \wedge \neg \sigma \rangle \implies \text{both} \\; \sigma \\; \text{and} \\; \neg \sigma \\; \text{are true} \implies \langle \neg \tau \rightarrow \sigma \rangle \\; \text{is true (since regardless of} \\; \tau \\; \text{the implication is valid since} \\; \sigma \\; \text{is true)} \implies \langle \neg \sigma \rightarrow \tau \rangle \\; \text{(by contraposition and double negation)} \implies \tau \\; \text{ is true (by modus ponens with} \\; \neg \sigma \\, )$$

). Thus if ZF is inconsistent, then every statement $\varphi$ has a proof polynomial (it seems to me even just linear) in $|\varphi|$.

Let $B:=B\_k$ for a sufficiently large $k$ a referred to above to allow for $B$ to be NP-complete. Then if ZF is inconsistent, there are only finitely many $\varphi$ such that $\langle \varphi \rangle \notin B$ because the high-degree polynomial proof length allowance of $B$ is enough to cover the guaranteed short proofs of wffs of sufficient length. This implies that $B$ is decidable in polynomial time which by its NP-completeness implies that P=NP. If we rephrase this chain of reasoning in terms of contrapositives, if P!=NP then ZF is not inconsistent (that is it is consistent).

Therefore If we have a formal proof of P!=NP then we have a formal proof of the consistency of ZF. But by Godel's Second Incompleteness theorem, this implies that ZF is inconsistent which in turn get P=NP as outlined above (as well as the theoremhood of any negated theorem).

This is not exactly a proof that P vs. NP is independent of ZF. It could be that ZF is consistent and that P=NP or that P!=NP can be proven through techniques not formalizable within ZF. However, it does present another formidable barrier to resolving P vs. NP.

# Answer
> 6 votes
There seems to be a flaw as alluded to by Arno in his answer. While the reduction $SAT \leq B$ seems innocuous enough (and is indeed a textbook exercise as pointed out by Ariel in his comment) it implicitly assumes the consistency of ZF. Otherwise, if ZF is inconsistent, since every statement of ZF would then have a proof, unsatisfiable SAT-instances would not necessarily be mapped to wffs $\varphi$ which do not have a relatively short proof.

Thus, if we assume that ZF is consistent and $ZF \vdash P \neq NP$ then although we can conclude metamathematically that $B \notin P$ (because being NP-complete, $B$ could not be in $P$ since we are assuming $P \neq NP$) we would not have a formal deduction of $ZF \vdash B \notin P$ (since this depends on $B$ being an established NP-complete set, so if we want to use the reduction above, we must assume that ZF is consistent, which cannot be formally asserted by Godel's Second Incompleteness Theorem). Thus this argument cannot suggest any necessary implications of $ZF \vdash P \neq NP$.

# Answer
> 4 votes
The problem is in your assertion that for sufficiently big $k$, the language $B\_k$ is NP-complete. In your proposed reduction, you only argue that any satisfiable SAT-instance is to a ZF-formula with "short" proof. However, you also need to argue that whenever the resulting ZF-formula has a short proof, then the original SAT-instance is satisfiable. This of course just boils down to saying that if ZF proves that the SAT-instance is satisfiable, then it really is - but here we are using soundness of ZF.

---
Tags: complexity-theory, np-complete, logic, p-vs-np
---


title: Byte/word addressing in cache

text:
# Question
Title: Byte/word addressing in cache
When dealing with caches, the address is split in three parts - offset, index and tag. Question is: if we are given a word address, do we first have to shift left by 2 bits by adding 00 at the end of address?

Suppose cache block size is 4 . block offset is 2 LSBs of the address. If we were to add 00 at end of every memory address, then block offset would always be 00. That means, we could never have access to any other byte rather than one at position 00 in our block?

# Answer
Huh? Let's modernise what you are saying a bit. Typical cache size nowadays is 64 bytes. So here is what a processor will typically do for such a cache:

Step 1a: Take the number of bytes accessed by the instruction, and the lowest six bits of the address, and determine whether the data is all within one cache line or straddles over two cache lines. (For example two consecutive bytes will in most cases be in one cache line, except if the lowest six bits are equal to 63. 16 consecutive bytes will often be in one cache line, except if the lowest six bits are greater than 48).

Step 1b: Use the other bits to determine the cache line where the data *might* be stored. If the cache has more than one way (say four way cache) this actually determines four possible cache lines.

Step 1c: Take the whole of the address to determine which of the possible ways contains the data. Also detect if the data is in the cache at all, and if not, start loading the data into cache which is *much* too complicated to explain here. When done, start all over again.

Steps 1a to 1c are performed in parallel if at all possible. Once the cache line containing the data, or the first part of the data is found, take the lowest six bits of the address, combine with the data size, and transfer as many bytes as needed and available.

If not all bytes needed are in the same cache line, repeat everything to get the remaining bytes.

Where your ideas went wrong: We don't set any bits of the address to zero, and we don't shift anything. We just take the parts of the address that are needed for every operation. To determine the cache line, you don't shift the address, you just take the address bits that are needed and you don't take the bits that are not needed. Since the lowest two bits are never zeroed, there is no problem accessing a byte anywhere in a cache line.
> 1 votes

---
Tags: cpu-cache
---


# Question
Title: Time complexity of travelling salesman problem
Time complexity of travelling salesman problem is $O(n^2\*2^n)$ using held-karp algorithm. Now, if don't use dynamic programming and solve it using the recursive procedure, time complexity is still $O(n^2\*2^n)$. I know there are overlapping of subproblems and there will be less computations but the time complexity is not getting better with the use of dynamic programming. Moreover, space complexity using held-karp is also $O(n\*2^n)$ which is very large. We mostly use dynamic programming when we can improve the time complexity.

So, should we use dynamic programming here?

Here is the recursive approach..

```
TSP(graph, start, target) {
  if start == target {
    return 0;
  }

  min = infinity;
  for neighbor in neighbors(graph, start, target) {
    tour_length = TSP(remove(graph, start), neighbor, target)
                  + distance(graph, start, neighbor);
    if tour_length < min {
      min = tour_length;
    }
  }
  return min;
}

```

# Answer
Time complexity using the recursive method is trying all "reachable" permutations of nodes before getting back to the first node which is in worst case $O(n!)$ (if all permutations are reachable).

However using recursion with memory may reduce it to the complexity of the DP solution. But using memory in itself is the idea behind the DP solution.
> 2 votes

---
Tags: algorithms, graphs
---