# Question
Title: A way to express LTL (varient) to enforce a stream of data to satisfy some linear time logic
*Linear Time Logic* (LTL) is used for *system verification*. In my case, I am investing some time, to see the feasibility of using LTL this time to enforce a constraint on a stream of data. Enough of generalities, let's take a simple example:

The operator **UNTIL** in the expression `u Until v` in LTL means, event `u` until `v`, it is a general formula that *an infinite number* of signal traces could satisfy. see it's definition here: page4

like:

```
u,u,u,v,v,v,...
u,u,u,u,u,u,...
u,v,v,v,v,v,...

```

In my case, I want to enforce an LTL like formulae to a system receiving a stream of data; Again let's take the same operator Until.

let's say we have two input signals, one for constant u, and one for constant v.

```
u,u,u,u,u,u,...
 , , , ,v,v,...

```

The stream processor taking these inputs, if it is an "UNTIL\*" node, would output:

```
u,u,u,u,v,v,...

```

The reason I differentiate **UNTIL** with an asterisk is the whole point of the question, "u UNTIL\* v" is only true when v is taken as output as soon as it appears in the second stream, it is one single trace satisfying "u UNTIL\* v" given our input signals. **How to express this constraint ?! LTL seems very general for this "constraint enforcing mechanism".**

*note: Please bear with me, I am no computer scientist, nor a mathematician, I am an average programmer who tries to learn new things.*

# Answer
> 2 votes
This is an interesting question.

It is not directly an LTL (Linear Temporal Logic) question -- rather a question about whether there is an algorithm or tool that takes an input stream and modifies it a somewhat minimal way to satisfy a given LTL property.

Whether that you want can be done or has been done depends on what exactly the allowed modifications to the stream are. In your example, you are, in a sense, remixing two streams. Note that LTL is defined over alphabets in which every character can have multiple propositions that are TRUE at the time. So in your example, you could have just mixed the u and v stream together to obtain:

```
u,u,u,u,{u,v},{u,v},....

```

This would have satisfied the LTL formula as well. If the way in which you remix is that the proposition in the output stream is always a subset of the propositions set in the input stream, then you can use *reactive synthesis* to obtain a transducer that does the stream mixing/fixing. However, this will only work if for every output stream there actually is a way to perform the mix.

If there is some quantitative notion of mixing/fixing, then quantitative synthesis may be a research area that may have some results. But you would need a description of the precise stream modification optimization criterion to see if any of the results from that area are applicable.

---
Tags: linear-temporal-logic, streaming-algorithm
---


title: Algorithm to check Gibbs' Phase Rule

text:
# Question
Title: Algorithm to check Gibbs' Phase Rule
I am looking for an algorithm to solve the following problem. I am unsure whether to post this in computational science or here, but since this is an algorithm I thought I would try here first.

I have a set of species made from a number of components.
Let's number each component $0, 1, 2 ... n$.
So now each species can be described as a set of these components. Each species is unique.

I am given a set of species, and I need to check whether any subset of these species fulfills the following condition: that the number of species in this subset is greater than the number of unique components in this subset.

For example: the set of species {\[0, 1, 2\], \[0, 2\], \[1, 2\], \[0, 1\]} fulfills the criterion, as the set has 4 species and 3 unique components. The set of species {\[0, 1, 2\], \[0, 2\], \[1, 2\], \[0,1\], \[3,4\]} also fulfills the criterion, as a subset of the set fulfills the criterion. The system {\[0, 1, 2\], \[0, 2\]} does not fulfill the criterion, as there are 2 species and 3 unique components.
In case it is relevant: there can be many species and components (20) but the number of components per species remains relatively small (2-5)

An easier version of this problem is also of interest to me: I have system which I know does not fulfill the criterion. The question is: if I add this species, will it fulfill the criterion?

This problem is equivalent to determining if a system of equations is over determined.

Edit: The criterion is equivalent to checking if the Gibbs Phase Rule is being violated in a system with only pure solid phases with at least 1 degree of freedom in addition to pressure and temperature. In this situation the number of phases is equal to the number of solids. There has a 0 or positive number of degrees of freedom left in the system or it becomes over constrained, so $0 \geq \text{number of components} - \text{number of species}$

# Answer
The gibbs phase rule is simply a way of determining whether the system of equations which describes the system will be overdetermined.

As we are talking about (usually) solids, this system of equations looks like $K=A^nB^m...$
If we take the log of both sides, this can be simplified to $\log{k}=n\log{A}+m\log{B}...$.
If we substitute $a=\log{A}, b=\log{B}$ then this becomes a system of linear equations $\log{k}=n\*a+m\*b...$

Now we can represent this system of linear of equations as a coefficient matrix and then use the Rouche Cappeli Theorem to determine whether the system is overdetermined. Since each species each unique in your system, you simply need to determine if there are any rank deficiencies in your coefficient matrix.

In the first example: {\[0, 1, 2\], \[0, 2\], \[1, 2\]} can be represented as the matrix $$\begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 1\\ 0 & 1 & 1\\ 0 & 1 & 0 \end{bmatrix}$$ Which has a rank deficiency, therefore is overdetermined.
> 1 votes

---
Tags: algorithms, sets
---


# Question
Title: Do any single-cell organisms exist that approximate NP-hard problems within a factor better than $1/2$ $log$2?
I've seen on Wikipedia; that *set covering cannot be approximated in polynomial time to within a factor* mentioned above. Unless $NP$ has quasipoly-time algorithms.

Now, this must pertain to classical algorithms and does not mention any approximation algorithms that may only work in nature.

(eg. Things like Amoebas solving $TSP$ problems)

* *Do any single-cell organisms show any promise in solving $NP$-hard problems in polynomial-time?*
* Or approximating them better than any known classical algorithms?

# Answer
In the realm of classical physics (where you don't need quantum mechanics to predict what is going on), we have no known method of computation that will be significantly faster than a standard classical computer. Indeed, it is a standard belief that none exists.

The one exception is quantum mechanics. Quantum computers are believed to be able to solve some problems significantly faster than classical computers -- though only a few special problems; for most, they offer no benefit (and quantum computers are not expected to offer any significant speedup for NP-complete problems). It is a standard belief that no physical process that can be described by quantum mechanics offers any significant speedup over a quantum computer (in particular, a quantum computer is universal and can simulate any quantum mechanical process).

In short, the answer to your question is "no, there is no known physical process that holds any promise for solving NP-hard problems in polynomial time".
> 2 votes

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


# Question
Title: Force-directed graph optimization with step-wise costs and constraints
## Introduction

I have an optimization problem. There are up to 25 nodes. The connectivity between the nodes is far less important than the Cartesian placement of the nodes. Since all nodes can potentially affect each other in the optimization problem it is safe to model this as a complete, undirected graph.

In most modes of this optimization problem there are between 2-3 regions extending out infinitely from the origin separated by straight lines, i.e.

```
 A | B
--------
   C

```

Each region exactly encompasses one or more Cartesian quadrants. Each imposes a fixed cost or benefit to each node, but this cost does not change the "farther into the region" a node gets.

## Costs

This is the exhaustive list of costs and constraints on the nodes; all factors are cost multipliers (higher is worse). Distances are shown in metres but are really just discrete integers.

* The distance between any two nodes must be at least 4m
* For each node pair within 25m, there is a factor of 1.04
* For each node, if there are three or fewer other nodes within 120m, there is a factor of 0.90
* Depending on what region a node is in, the node has a factor between 0.90 and 1.10
* For every node, there is an individual edge factor to every other node within 25m of between 0.90 and 1.10
* The product of all of the above factors, for each node, will have a set minimum of 0.67 and a set maximum of 1.50

So none of the factors are continuous, and none are differentiable in space since they are all step-wise.

## Search space

The 2D coordinates of each node are discrete and unbounded. Since there are 25 nodes, there are 50 integer variables (xy for each node) to optimize. The hope is that even though there are no bounds, there will be enough sub-1.0 factors to have the optimization converge rather than force the nodes to fly apart.

If I get this working well enough for a given region configuration, I might expand this to selection of a region configuration, for which there are currently 46 possibilities.

## Optimization

Since none of the cost factors are space-differentiable, something like Gradient Descent would not be possible.

I have read about force-directed graph drawing; in particular this is interesting:

> using the Kamada–Kawai algorithm to quickly generate a reasonable initial layout and then the Fruchterman–Reingold algorithm to improve the placement of neighbouring nodes.

Unfortunately, it seems that these methods have no notion of cost tied to absolute location, only distance of nodes relative to each other.

## Implementation

I will probably end up implementing this in Python.

Any hints on how to approach this would be appreciated.

# Answer
> 1 votes
This is a discrete optimization problem. I think one possible approach would be to approximate the discrete elements with continuous, differentiable functions and then optimize the resulting substitute problem.

Consider the function $f(x)=1$ if $x\ge 0$, or $f(x)=0$ if $x\<0$. This is a discrete function, which can be approximated by the sigmoid function $S\_\alpha(x) = 1/(1+e^{-\alpha x})$. The sigmoid is effectively a "softened" version of $f$. The larger that $\alpha$ is, the better the approximation. And notice that the sigmoid function is continuous and differentiable and monotonic. Similarly, the function $f(x)=c$ if $x \ge t$, or $f(x)=0$ if $x\<t$, can be approximated by $c/(1+e^{-\alpha (x-t)})$.

So, take your problem, and replace each of the discrete decisions with a softened version. For instance, you have a rule that says "if a pair of nodes is at distance $\le$ 25m, then multiply a factor of 1.04". I suggest you replace this with the rule "multiply a factor of $1.04/(1+e^{-\alpha(25-d)})$ where $d$ is the distance between those two nodes". In this way, each rule can be replaced with a "softened" version, where the parameter $\alpha$ determines how soft it is: the smaller $\alpha$ is, the smoother the function; the larger $\alpha$ is, the better an approximation it is to the discrete rule. Your requirement that the product be between 0.67 to 1.5 can be replaced with a version that applies a penalty if the product is below 0.67 or above 1.5, and then you compute a softened version of this penalty for each node. Finally, the objective function can be the sum of these penalties.

Once you've done that, you have a continuous, differentiable objective function, so you can minimize it using gradient descent. I suggest that you initially set $\alpha$ to be a fairly small value, and during gradient descent you gradually increase $\alpha$ until finally it is a very large value (i.e., slightly increasing $\alpha$ after each iteration of gradient descent).

As a side note, instead of working with the product of factors, I recommend you take the log of everything, so that work with the sum of log factors. Usually summations behave more nicely with gradient descent than products.

I suggest that you use gradient descent with random restarts. For instance, you might do 1000 trials, where in each trial you start with randomly chosen initial positions, and then do gradient descent from there until convergence; and you take the best result across all of these 1000 trials.

You could also try replacing gradient descent with any other iterative method, such as Newton's method.

I don't know whether this will work well for your particular problem, but it is one thing you could try that might work.

---
Tags: graphs, optimization
---


# Question
Title: I'm looking for an algorithm to find unknown patterns in a string
I am trying to detect patterns in huge code bases. I managed to filter the entire codebase into a tagged string, as in: ABACBABAABBCBABA

The result should be: ABA \*3 CBA \*2

I'm trying to build / use an algorithm which will find ANY unknown repeating pattern inside the string. The length of the pattern, it's composition, and the number of repeats is unknow.

To be a pattern it must occur atleast twice. And have atleast 2 items. Once I detect the patterns I can represent them back in their original context

I have tried iterating over each tag. For each tag find the following tag in the string. continue until adding a tag matches only one repeat - hence no more pattern.

I get lost in implemetation (in JS or Python) and I'm hoping there is a better way. Thanks.

# Answer
Here is a simple search in Python:

```
s = "ABACBABAABBCBABA"
d={}
for sublen in range(MINLEN,int(len(s)/MINCNT)):
    for i in range(0,len(s)-sublen):
        sub = s[i:i+sublen]
        cnt = s.count(sub)
        if cnt >= MINCNT and sub not in d:
             d[sub] = cnt

```

Where MINLEN is the minimum length of pattern you want to find and MINCNT is the minimum number of occurrences of that pattern. This runs in O(n^3) (nested for loop + .count()).

If you set MINCNT=2 and MINLEN=2 the result of running this is `d = {'CB': 2, 'BABA': 2, 'AB': 4, 'CBAB': 2, 'CBABA': 2, 'BAB': 2, 'BA': 5, 'ABA': 3, 'CBA': 2}`

These are all of the patterns that match your string given your description. Your question is a bit unclear in the example, if this is not what you are looking for let me know.
> 3 votes

# Answer
Construct the suffix tree of your string, which takes time linear in the length of the string (assuming a finite alphabet). Every inner node represents a repeat, their respective descendant leaves encode the positions.
> 5 votes

# Answer
What you need looks exactly like an LZ77 algorithm. It has many possible implementations. In particular, you can perform suffix sort on input data (current algorithms are so efficient that they can sort 10 megabytes in less than a second), and get index into your text, sorted on full string being pointed. One particular fast implementation is https://github.com/y-256/libdivsufsort \- I think it should be more efficient and easier to use than the suffix tree.
> 2 votes

# Answer
I am put this just in case if someone else is interested with this topic. I find the following work easy to understand and implement for pattern discovery in string.

E. Keogh, J. Lin and A. Fu (2005). HOT SAX: Efficiently Finding the Most Unusual Time Series Subsequence. In Proc. of the 5th IEEE International Conference on Data Mining (ICDM 2005), pp. 226 - 233., Houston, Texas, Nov 27-30, 2005.

The paper is available here. https://www.cs.ucr.edu/~eamonn/HOT%20SAX%20%20long-ver.pdf
> 1 votes

# Answer
If I understand correctly, what you're asking is pretty much the opposite of the question "How truly random a string is?".
There's a huge literature on this in Cryptography and specifically random and pseudorandom generators, you can use statistical tests and tools to recognize recurring patterns.
But first you must have a clear vision on how to sort the significance of these patterns, I recommend defining a utility function u(n, r) in which n is the length of the pattern and r is it's repetition.
> -1 votes

---
Tags: algorithms, search-algorithms, strings, substrings
---


# Question
Title: Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset
I am working on a problem defined as the following

Given a set of $n$ elements called $R \subseteq \mathbb{N} \times \mathbb{N}$ and numbers $Z,G \in \mathbb{N}$, where $Z$ is a measure of our resources and $G$ is our necessary minimal reward, is there a set $R' \subseteq R$, so that $\sum\_{(z,g)\in R'}z \leq Z$ and $\sum\_{(z,g)\in R'}g \geq G$?

I want to show its NP-completeness and have shown that it is in NP already. I am struggling with the NP-hardness. My known NP-hard problems are the SAT, 3SAT, partition, subset sum and bin packing.

My struggle seems to be mostly with the fact that we have to balance two different values now, the cost and the reward. This is not the case in any of the set related problems I mentioned and I am unable to think of how to model this in SAT or 3SAT. What am I missing here? How can I show the NP-hardness and as such the NP-completeness of this problem using only these given problems?

# Answer
This sounds to me like the Knapsack problem where

* $z$ is the *weight* of each item,
* $Z$ is the *capacity* of the knapsack,
* $g$ the value of the item, and
* $G$ the value to be achieved.

The problem is *NP-complete* but solvable, using dynamic programming, in *pseudo-polynomial time* $O(n \cdot W)$ where $W = \max\_{(z,g) \in R}(g)$.

You can prove that the Knapsack Problem is NP-complete by reducing from the Subset sum problem. Indeed, Subset Sum is a special case of Knapsack where $z = g$; The "weight" of each problem is the same as its "value".
> 3 votes

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


# Question
Title: Pumping lemma for regular languages vs. Pumping lemma for context-free languages
How can I prove the next claim:

If a language $L$ meets the pumping lemma for regular languages then $L$ meets the pumping lemma for context-free languages?

(Without any pre-condition about the regularity of $L$)

# Answer
> 1 votes
The pumping lemma of context-free languages means finding $x,y,z,v,u$ such $w=xvyuz, |vu|\>0,|vxu|\le p$, and for all $n\in\mathbb N$, $xv^nyu^nz$

The regular pumping lemma means finding only $v,y,u$ where $w=abc,|b|\>0,|ab|\le p$ and $ab^nc\in L$. ("a","b","c" here are representing sub-words of w)

So, simply take $x=a,v=b,y=c,u=\epsilon,z=\epsilon$

---
Tags: pumping-lemma
---


# Question
Title: Estimating the bit operations using big O notation
Using big- O notation estimate in terms of a simple function of $ n $ the number of bit operations required to compute $3^n$ in binary.

I need some help with the above question. The number of bit operations required to multiply two k- bit numbers is $O(k^2)$. In the first step I am multiplying two 2-bit numbers, in the 2nd step a 4-bit and a 2-bit number and so on. So the total bit operations will be I feel $O(k^2) + O(k^2 * k) +.... + O(k^{n-1} * k) \\,\\,with \\,\\, k \\,= 2 $

How will the above sum be estimated as a function of n?

# Answer
> 1 votes
There are several problems. First, the time complexity of multiplying two k-bit numbers is much less than O(k^2). More like O(k log k). Since this is an important open research problem, you usually assume it is O(M(k)) for some function M and use that further.

Second, you are not multiplying two k bit numbers. You are multiplying one k-bit number by 3, which is done easily in O(k). This would get you a total of O(n^2).

Third, that’s not a clever method to calculate $3^n$. Much better is repeated squaring/multiplying. For example to calculate $3^{100}$: Start with 3, square, multiply by 3, square, square, square, multiply by 3, square, square. Since the number of bits starts small and doubles every time, this works in O(M(n)).

---
Tags: time-complexity
---


# Question
Title: Scaling down a set of points into a smaller area
A visibility graph $G(P) = (V,E)$ of a set $P = \\{p\_1, \dots, p\_n\\}$ of points is defined as follows.

* Each vertex $u \in V$ corresponds to a point $p\_u \in P$.
* There exists an edge $uv \in E$ if, and only if the line segment $\overline{p\_up\_v}$ does not contain any other points in $P$.

Assume that the coordinates of every $p\_i \in P$ has $O(n^c)$ digits, where $c$ is a constant.

My aim is to scale the point set, without changing the relative positions, into a smaller area. For the sake of simplicity, assume that the area is a circle of raduis 1.

Consider three points: $p\_1(100, 340)$, $p\_2(500,150)$, $p\_3(240, -600)$.

The new coordinates after scaling would be $p'\_1(0.1, 0.34)$, $p'\_2(0.5, 0.15)$, $p'\_3(0.24, -0.6)$, and the relative positions stay the same, as well as the visibility relations.

My question is two folded:

1. In the very simple example above, the coordiantes are divided by $100$, and it is pretty easy to find that number. But what is the algorithm to find this number for any given point set?
2. Assuming that the coordinates are of $O(n^c)$ length, can there be a coordinate of $O(d^n)$ (exponential) length?

Regarding Discrete lizard's comment,

$100$ is an integer, which can be represented using $O(\log n)$ bits.

However, instead of $100$, the number was say $1998.12341234123422335$, then (i) it is not trivial to determine the number, and (ii) the division itself requires exponentially many digits.

# Answer
> 1 votes
The following procedure achieves your requirements:

Step 1: Find the smallest circle that encloses all points. (There are standard algorithms for this.)

Step 2: Compute the area of that circle.

Step 3: Compute the scaling ratio $c$ needed to achieve the desired area. (For instance if the area of that circle is 100 and you want area 5, then your scaling ratio is $c = \sqrt{100/5} = \sqrt{20}$.)

Step 4: Scale everything down by a factor of $c$, centered at the center of the circle found in Step 1.

This can be implemented in linear time, so it should be very efficient.

---
Tags: computational-geometry, euclidean-distance
---


# Question
Title: What is the difference between these two Edit Distance Algorithm
Edit Distance is very well known problem in computer science. Came up with following algorithm after reading through CLRS but it doesn't work. Check the working algorithm below, I couldn't find why first algorithm doesn't work while second one does.

```
  public int find (String word1, String word2, int i, int j, int count) {
    if (i >= word1.length()) return  count + word2.length() - j;
    if (j >= word2.length()) return  count + word1.length() - i;

    if (dp[i][j] != -1) return dp[i][j];

    if (word1.charAt(i) == word2.charAt(j)) {
        dp[i][j] = find(word1, word2, i+1, j+1, count);
    } else {
        int replace = find(word1, word2, i+1, j+1, count + 1);
        int delete = find(word1, word2, i+1, j, count + 1);
        int insert = find(word1, word2, i, j+1, count + 1);

        dp[i][j] = Math.min(replace, Math.min(delete, insert));
    }

    return dp[i][j];
}

```

Notice, how I'm passing the cost of edit in method argument. Now, the algorithm which works. Here I'm not passing the edit distance in the method parameter instead of I'm adding 1 to recursive method.

```
  public int find (String word1, String word2, int i, int j) {
    if (i >= word1.length()) return  word2.length() - j;
    if (j >= word2.length()) return  word1.length() - i;

    if (dp[i][j] != -1) return dp[i][j];

    if (word1.charAt(i) == word2.charAt(j)) {
        dp[i][j]  = find(word1, word2, i+1, j+1, count);
    } else {
        int replace = find(word1, word2, i+1, j+1, count + 1);
        int delete = find(word1, word2, i+1, j, count + 1);
        int insert = find(word1, word2, i, j+1, count + 1);

        dp[i][j] = 1 + Math.min(replace, Math.min(delete, insert));
    }

    return dp[i][j];
}

```

I'm not able to think why first algorithm fails. Appreciate, if you can point my error in understanding.

# Answer
I'm going to assume by "doesn't work" you mean "gives the wrong answer".

In dynamic programming, every cell in the table is supposed to represent a solution to a subproblem. In the case of edit distance, the subproblem is

* Let `dp[i][j]` be the distance between `word1.substring(i)` and `word2.substring(j)`

But in your code, the statement of the subproblem is ambiguous. The cell `dp[i][j]` contains something that depends on `count`, but which `count`? It might very well be that many different `count`s correspond to the same pair `i,j`, because you can get to it by different "routes". If that happens, your program will just use whatever `count` it encountered first, write the answer to the table and never revise it again. Therefore, if the first route you took is not the optimal one, then the result will be wrong.

Consider what happens when I give your program the words "WORD" and "SWORD". Which number will be in `dp[3][4]`? The correct program will write 0 into that cell, and eventually it will find a route that leads to the point `3,4` and has a cost of 1. Your program, on the other hand, will write the `count` of the first route it takes, which in this case will be 4. And even though it may later find a better route, it will still trust that 4, because that's what the table says.

In summary, you make a subproblem with the indices `i,j` depend on some other quantity, which violates the principles of dynamic programming. If your `dp` table had a third dimension, as in `dp[i][j][count]`, then it might have worked, because then every subproblem would be fully specified.
> 1 votes

---
Tags: dynamic-programming, recursion, edit-distance
---


title: 1-sparse recovery algorithm

text:
# Question
Title: 1-sparse recovery algorithm
In the reference below, a 1-sparse recovery algorithm over a vector $a \in R^n$ is defined as follows. My question is why do we need the modulus (i.e. $x \mod p$)?

**Algorithm:**

1. Keep track of $$ \begin{split} w\_1 &= \sum a\_i \\ w\_2 &= \sum i a\_i \\ w\_3 &= \sum a\_i z^i \mod p \end{split} $$
2. Test if $$ \begin{split} w\_3 \equiv w\_1 \cdot z^{w\_2 / w\_1} \mod p \end{split} $$ For some large prime $p$.

Reference: Section 3.2, "1-sparse recovery: second attempt", https://web.stanford.edu/class/cs369g/files/lectures/lec11.pdf

# Answer
Without the mod p, the running time to check the condition would be exponential, which is unacceptable. Also, it would require exponential space to store $w\_3$ and to check the condition.

Also, the procedure involves choosing an integer $z$ uniformly at random from $\\\>0,\dots,p-1\\}$. You can choose an integer uniformly at random from $\\{0,\dots,p-1\\}$, but you can't choose it uniformly at random from the set of all integers. So, you'd have to think about exactly what alternative approach you had in mind if you wanted to omit the mod p.
> 1 votes

---
Tags: algorithms, randomized-algorithms, streaming-algorithm
---


# Question
Title: Streaming algorithm for counting triangles in a graph
As described in the reference, the algorithm (see at the bottom) supposes to output an estimator $\hat T$ for the # of triangles in a given graph $G = (V, E)$, denoted $T$. It is written that "it can easily be shown" that $$ E\[\hat T\] = T $$ But unfortunately, I'm not seeing it. Trying to analyze $E\[\hat T\]$, I think as follows:

* At line 1, denote the probability to randomly (and uniformly) choose an edge which is part of a triangle as $p$. Since triangles can share edges, $$ \frac T m \le p \le \frac {3T} m $$ For example, consider the following case:

The central triangle doesn't add new edges to the # of possibilities to choose an edge which is part of a triangle. You can imagine a different configuration, in which there are only the 3 outer triangles and they don't touch each other (in this configuration, we won't see the central 4th triangle). In both cases ((case i) 4 triangles as seen in the image; (case ii) 3 disjoint triangles), the probability to choose an edge which is part of a triangle is 1 (although the # of triangles is different).
* At line 2, the probability to choose uniformly at random a vertex which "closes a triangle" with the edge from the previous step is exactly $\frac 1 {n-2}$.

Therefore I only see that

$$ T \le E\[\hat T\] \le 3T $$

What am I missing?

---

Another question I have is regarding line 3. The stream is ordered, and we first pick a random edge $(u, v)$ (line 1), then a random vertex $w$ from $V \backslash \\{u, v\\}$ (line 2). I feel that the analysis should take into account that at line 3 we check whether $(u, w)$ and $(v, w)$ appear **after** $(u, v)$ in the stream. Maybe after I'll understand the answer to my first question, it will be clearer.

---

**Algorithm:**

1. Pick an edge $(u, v)$ uniformly at random from the stream.
2. Pick a vertex $w$ uniformly at random from $V \backslash \\{u, v\\}$
3. If $(u, w)$ and $(v, w)$ appear after $(u, v)$ in the stream, then *output* $m(n-2)$. Else, *output* $0$.

Also, although I didn't see it written, I believe there's an assumption that $V$ is known ahead.

---

Reference: Data streams lecture notes by Prof. Amit Chakrabarti, section "15.3 Triangle Counting", https://www.cs.dartmouth.edu/~ac/Teach/data-streams-lecnotes.pdf

---

Best regards

# Answer
Let $(u,v,w)$ be a particular triangle in the stream, and suppose that the edge $(u,v)$ appears first. The probability that we chose $(u,v)$ in the first step is $1/m$. The probability that we chose $w$ in the second step is $1/(n-2)$. Hence the probability that we chose the triangle $(u,v,w)$ is $1/\[m(n-2)\]$. Let us denote this event by $E\_{u,v,w}$.

If $(u\_1,v\_1,w\_1)$ and $(u\_2,v\_2,w\_2)$ are two different triangles that the events $E\_{u\_1,v\_1,w\_1}$ and $E\_{u\_2,v\_2,w\_2}$ are disjoint (note that the triangles don't have to be disjoint). Therefore if there are $T$ triangles, then the probability that we chose one of them is exactly $T/\[m(n-2)\]$. Therefore the expected output of the algorithm is exactly $T$.
> 3 votes

---
Tags: graphs, combinatorics, randomized-algorithms, streaming-algorithm
---


title: Arthur-Merlin protocol

text:
# Question
Title: Arthur-Merlin protocol
I recently learned about the Arthur-Merlin protocol, and we defined the complexity classes $AM,MA$.

We have also seen that there exists a theorem stating that $AMAMAM...AM=AM$, however we have not formally defined $AMAMAMAM...AM$.

We did give a brief definition for it as a protocol, but i would like to see a formal definition **without protocols**, just like $AM$ and $MA$ (and $MAM$)

A definition for $AMA$ should suffice for me, just to get the hang of how it should look.

Thanks!

# Answer
$AMA$ is basically a 3-round interactive proof system where the verifier (Arthur) is only allowed to send randomness to the prover (Merlin).
I haven't seen such an explicit definition yet, but I think we can formulate it as follows. The first round of AM\[3\] starts with Merlin sending a message $m\_1$ to Arthur. In the second round, Arthur sends randomness $r$ to Merlin, which is followed by the final third round in which Merlin sends a message $m\_2$. Arthur then decides to accept/reject using deterministic polynomial-time verifier $V$.

I think we can define the class as follows.
**Definition:** $L ∈ AMA$ if there exists a poly-time deterministic algorithm $V$ such that:

* If $x \in L \\;(|x| = n)$ then $\exists P. Pr\_{r \in \\{0,1\\}^{p(n)}} \left( V(x, m\_1, r, m\_2) = 1 \right) \ge 2/3$ where $\\; m\_1 = P(x),\\; m\_2 = P(x, r)$
* If $x \notin L \\;(|x| = n)$ then $\forall P. Pr\_{r \in \\{0,1\\}^{p(n)}} \left( V(x, m\_1, r, m\_2) = 1 \right) \le 1/3$ where $\\; m\_1 = P(x),\\; m\_2 = P(x, r)$

Note the prover $P$ is a function $P: \\{0,1\\}^\* \rightarrow \\{0,1\\}^{q(n)}$, where $q(n)$ is a polynomial.

See: Computational Complxity by Arora-Barak's section 8.1.
> 1 votes

---
Tags: complexity-theory, complexity-classes, protocols
---


# Question
Title: Line-search does not guarantee convergence so how to use it?
Line-search/backtracking in gradient descent methods essentially boils down to picking the current estimate $\theta\_n$ (which depends on the stepsize $\gamma$ and the prior estimate $\theta\_{n-1}$) by performing line-search and finding the appropiate $\gamma$.

This search depends on a 'sufficient descent' criterion.

It can happen that the sufficient descent criterion simply is not going to be satisfied for any reasonable $\gamma$. That is, you are at a part in your search for the optimal point where no matter how small a step-size you take, you are not getting sufficient descent.

Here, line-search would get stuck in an infinite loop (or, a near-infinite loop: the sufficient descent criterion might be satisfied eventually due to numerical errors)

So, how should this be fixed? One option is to omit line-search completely: fixing $\gamma$ to be a constant, you will eventually converge if $\gamma$ is small enough.

A second option is to do line-search for an optimal $\gamma$, but only for a small amount of time (say, 20 iterations). If you haven't found a optimal $\gamma$ by then, then just take any fixed step and hope you get back towards convergence.

What do people do?

# Answer
First of all, if we have a descent direction, we can always find a step size $\tau$ that is arbitrary small, such that "the sufficient descent criterion" is satisfied (see the Wikipedia article 'Backtracking line search'). This essentially rules out the infinite loop issue.

For example, consider Armijo condition as "the sufficient descent criterion", which is $$ f(\bar{x}+\tau d) \leq f(\bar{x})+\gamma \tau\langle\nabla f(\bar{x}), d\rangle $$ for $\gamma \in (0,1)$ and where $d$ satisfies $\langle\nabla f(\bar{x}), d\rangle \< 0$.

If the function is twice differentiable, we can consider its Taylor expansion around the current iterate $x\_k$ and show that as $\tau \to 0$, the Armijo condition is satisfied. However the step size could be arbitrarily small, when we consider the backtracking algorithm. To prevent this, we impose additional constraints on the step size, that prevent $\tau$ from being too small, while preserving the guarantee that such a step size still exists. For further details, you can check the Wikipedia article above.
> 2 votes

# Answer
I'm not sure what 'sufficient descent' criterion you have in mind, but you can use gradient descent + line-search even if it doesn't make sufficient progress -- it just might not work very well. Yes, in the worst case, if you have a sufficiently nasty objective function, gradient descent can get stuck in an area where it makes very slow progress; that absolutely can happen. I'm not sure what more there is to say. Gradient descent is a heuristic. There is no claim that it works well on all objective functions.

How should this be fixed? What do people do? That's too broad to answer in general. What to do about it will depend on your specific situation and your particular objective function. If you have an objective function where gradient descent doesn't work well, maybe don't use gradient descent: maybe consider using another optimization method.

I realize this might not be very helpful, but I'm not sure how to be more helpful without looking at a more specific situation.
> 0 votes

---
Tags: backtracking, gradient-descent
---


# Question
Title: Analogue of the topology-computability correspondence for computational complexity
There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with continuous functions (in fact it can perhaps be traced back to Brouwer).

Complexity theory can be seen as a refinement of computability theory: we are interested in not only whether a problem is solvable or not but also the efficiency with which it is solvable. Taking this view of complexity theory as a refinement of computability theory, I wonder if there is any research on analogous mathematical structures to provide efficiency-sensitive denotational semantics to programming languages.

The point of topology is that it is distance-blind which is in accord with the efficiency-blind approach in computability theory. So it seems to me that an efficiency-sensitive denotational structure should be a topological space with a notion of distance, i.e., a metric space or something like that.

Has someone worked this out or is this a nonsensical question? If it is the latter, please explain why.

# Answer
> 2 votes
The answer to your literal question is *neither*. The reasoning in your question makes perfect sense, and there are several researchers working on the details on what exactly is analogous to complexity theory in the same way topology is analagous to computability. However, I don't think I am unfair in claiming that this is nowhere near completed.

In a compact metric context, notions such as metric entropy seem to be important, and the counterpart to "continuous" seems to be "having a modulus of continuity of particular growth". Beyond compact metric, the picture quickly gets very unclear.

I don't know of a comprehensive written treatment, but Martin Ziegler just gave a tutorial on this at the conference "Computability in Europe". The talks are up on this Youtube channel, specifically "Quantitative Coding and Complexity theory...".

---
Tags: complexity-theory, turing-machines, computability, semantics, topology
---


# Question
Title: Efficiently storing and modifying a reorderable data structure in a database
I'm trying to create a list curation web app. One thing that's important to me is being able to drag-and-drop reorder items in the list easily. At first I thought I could just store the order of each item, but with the reordering requirements, that would mean renumbering everything with a higher order (down the list) than the place where you removed or where you inserted the moved item. So I started looking at data structures that were friendly to reordering, or to both deletion and insertion. I'm looking at binary trees, probably red-black trees or something like that. I feel like I could with great effort probably implement the algorithms for manipulating those.

So here's my actual question. All the tree tutorials assume you're creating these trees in memory, usually through instantiating a simple Node class or whatever. But I'm going to be using a database to persist these structures, right? So one issue is how do I represent this data, which is kind of a broad question, sure. I would like to not have to read the whole tree from the database to update the order of one item in the list. But then again if I have to modify a lot of nodes that are stored as separate documents, that's going to be expensive too, even if I have an index on the relevant fields, right? Like, every time I need to manipulate a node I need to actually *find* it in the database first, I think.

Also, I obviously need the content and order of each node on the front end in order to display the list, but do I need the client to know the whole tree structure in order to be able to send updates to the server, or can I just send the item id and its new position in the list or something?

I'm sorry if this veers too practical but I thought someone might want to take a crack at it.

# Answer
> 2 votes
There are two questions here:

1. How do you implement a pointer data structure such as a red-black tree in a database?
2. *Should* you implement a pointer data structure in your database to solve this problem in practice?

The answer to (1) is easy: add arbitrary IDs to each of your items and use those when you need to store a "pointer" to an item. For example, to implement red-black trees in a typical relational database, you would have a table with one row for each node, with the following columns:

* an autoincrement non-nullable integer primary key column, storing the node ID
* three nullable integer columns, storing the left, right, and parent node IDs
* a non-nullable bit column, storing the red-black flag
* columns for whatever actual data is associated with each node

And then you would have a table with one row for each tree, with an integer column pointing to the root node for that tree.

As for (2): if your lists are less than a few thousand elements, it's definitely likely—as @D.W. points out—that the best way to store the ordering in a database is *not* to do the above. Skip the pointer columns and just give your table of lists a blob column that stores that list's item IDs in order as a series of 2-byte or 4-byte ints. When your app wants to show the list, it reads the entire blob for that list; when it wants to reorder a list, it overwrites that list's blob with an entire new blob. \[\*\]

If your lists are large enough, you might want to start profiling different options' performance. But you mention a drag-and-drop UI, and such UIs are rarely amenable to reordering lists longer than even a few dozen elements.

\[\*\] Implementation note: If you go with this option, make sure you have another column on the items tracking which list each item belongs to, rather than just using a single autoincrement ID column. Otherwise, repeatedly creating and deleting lists could overflow your IDs even if each individual list only has a few items in it!

---
Tags: data-structures, binary-trees, databases, memory-access
---


title: Minimum pumping length of (01)*

text:
# Question
Title: Minimum pumping length of (01)*
Michael Sipser offers the definition:

*The pumping lemma says that every regular language has a pumping length p, such that every string in the language can be pumped if it has length p or more. If p is a pumping length for language A, so is any length p′ ≥ p. The minimum pumping length for A is the smallest p that is a pumping length for A.*

Now, (01)\* in set notation is {€, 01,0101,010101....} Taking minimum pumping length = 1, according to the definition, we have the statement if a string in the language has length 1 or more, it can be pumped.

This statement is true for all elements of the above mentioned set, so can the minimum pumping length be 1?

p.s. the minimum pumping length for (01)\* has been asked here before but it doesn't answer my doubt that since the condition holds for minimum pumping length = 1, why is it not the answer?

# Answer
The minimum pumping length $\ell$ of $(01)^\*$ is $2$.

First of all notice that there are no words of length $1$ in the language. Then, if you look at a formal definition of the pumping lemma for regular languages (what you wrote is still informal) you'll find that the length $|xy|$ of the prefix $xy$ of a word in the language that can be pumped must be $\le \ell$.

This allows you to prove that the minimum pumping length $\ell$ must be $2$ by showing:

* That there is a DFA for $(01)^\*$ that uses at most $2$ states, implying $\ell \le 2$. This DFA is trivial to obtain.
* That $\ell=1$ is not a valid pumping length. This is true since $|y|$ must be positive and, together with $|xy| \le \ell$, this implies $|y|=1$. In other words $x = \epsilon$ and $y=0$. It is easy to obtain a word not in the language by repeating $y$ either $0$ or at least $2$ times.
> 2 votes

---
Tags: regular-languages, pumping-lemma
---


# Question
Title: What does the notation $ [ i \neq k ] $ mean?
I can't figure out what the notation $\[x \neq k \]$ means. Here's a bit of context:

The formula is: $Pr\[A\_i^k = 1\] = \frac{\[i\neq k\]}{|k-i| + 1} = \begin{cases} \frac{1}{k-i+1} \text{ if } i \lt k \\ 0 \text { if } i = k \\ \frac{1}{i-k+1} \text{ if } i \gt k \end{cases}$

and is part of a chapter where the average expected time of operations of a randomised treap are proved.

$A\_i^k$ is an indicator variable defined as $\[ x\_i \text{ is a proper ancestor of }x\_k \]$ where $x\_n$ is the node with the $n$-th smallest search key. That probability comes up because $\text{depth}(x\_k) = \sum\_{i=1}^{n} A\_i^k$ and $\mathbf{E}\[\text{depth}(x\_k)\] = \sum\_{i=1}^nPr\[A\_i^k = 1\]$.

I have no access to the pages that explain the notation since I'm studying from a pdf of a few pages taken from a book.

# Answer
> 6 votes
It is used like a boolean where $\[i \neq k\] = 1$ if $i \neq k$ and $0$ otherwise. Notice that $\[i \neq k\]$ is equivalent to $i \< k$ or $i \> k$ for numbers, which is the right part of the equation you wrote.

It is called Iverson bracket and in general $\[statement\] = 1$ if $statement$ is true and $0$ otherwise.

---
Tags: notation
---


# Question
Title: Tight upper bound for forming an $n$ element Red-Black Tree from scratch
I learnt that in a order-statistic tree (augmented Red-Black Tree, in which each node $x$ contains an extra field denoting the number of nodes in the sub-tree rooted at $x$) finding the $i$ th order statistics can be done in $O(lg(n))$ time in the worst case. Now in case of an array representing the dynamic set of elements finding the $i$ th order statistic can be achieved in the $O(n)$ time in the worst case.\[ where $n$ is the number of elements\].

Now I felt like finding a tight upper bound for forming an $n$ element Red-Black Tree so that I could comment about which alternative is better : "maintain the set elements in an array and perform query in $O(n)$ time" or "maintaining the elements in a Red-Black Tree (formation of which takes $O(f(n))$ time say) and then perform query in $O(lg(n))$ time".

---

So a very rough analysis is as follows, inserting an element into an $n$ element Red-Black Tree takes $O(lg(n))$ time and there are $n$ elements to insert , so it takes $O(nlg(n))$ time. Now this analysis is quite loose as when there are only few elements in the Red-Black tree the height is quite less and so is the time to insert in the tree.

I tried to attempt a detailed analysis as follows (but failed however):

Let while trying to insert the $j=i+1$ th element the height of the tree is atmost $2.lg(i+1)+1$. For an appropriate $c$, the total running time,

$$T(n)\leq \sum\_{j=1}^{n}c.(2.lg(i+1)+1)$$

$$=c.\sum\_{i=0}^{n-1}(2.lg(i+1)+1)$$

$$=c.\left\[\sum\_{i=0}^{n-1}2.lg(i+1)+\sum\_{i=0}^{n-1}1\right\]$$

$$=2c\sum\_{i=0}^{n-1}lg(i+1)+cn\tag1$$

Now

$$\sum\_{i=0}^{n-1}lg(i+1)=lg(1)+lg(2)+lg(3)+...+lg(n)=lg(1.2.3....n)\tag2$$

Now $$\prod\_{k=1}^{n}k\leq n^n, \text{which is a very loose upper bound}\tag 3$$

Using $(3)$ in $(2)$ and substituting the result in $(1)$ we have $T(n)=O(nlg(n))$ which is the same as the rough analysis...

Can I do anything better than $(3)$?

---

All the nodes referred to are the internal nodes in the Red-Black Tree.

# Answer
To construct a red-black tree on $n$ elements you need to spend time $\Omega(n \log n)$, if you are only allowed to compare the elements' keys. To see this notice that an in-order visit of any BST visits the nodes in increasing order of their keys.

If you were able to construct a red-black tree in time $t(n) = o(n \log n)$ then you'd also be able to sort $n$ elements in time $O(t(n) + n) = o(n \log n)$, contradicting the lower bound on sorting for comparison-based algorithms.

On the other hand, if the elements are already sorted then you can build a red-black-tree in time $O(n)$: just recursively build a balanced BST, if the last level is incomplete color its nodes as red, and color every other node black. This requires linear time since the time complexity of the recursive algorithm can be described by the recurrence equation $T(n) = 2T(n/2) + O(1)$.
> 1 votes

---
Tags: algorithms, algorithm-analysis, data-structures, runtime-analysis, red-black-trees
---


title: How does Warrens Abstract Machine work?

text:
# Question
Title: How does Warrens Abstract Machine work?
I've recently learned about Prolog and Logic programming which I find pretty cool, but the compiler is currently like magic to me and I want to know how they work.

After a little bit of research I discovered that logical compilers are based on Warrens Abstract Machine (WAM). I've tried to find some information on WAM, but the Wikipedia page only describes what it is and not how it works and the book Warrens Abstract Machine: A Tutorial Reconstruction doesn't read very well for me.

Could I please have basic explanation of how WAM works?

# Answer
> 1 votes
This may be a question that's too broad to cover here.

The WAM covers a lot of Prolog-specific capabilities (e.g. unification, nondeterminism, the cut) that other abstract machines do not, and its design is also quite subtle in its details (e.g. garbage collection on backtracking is designed into the machine). There is a reason why the WAM Book is 130 pages long: it is complicated and hard to understand!

Still, the WAM Book is the best explanation that I'm aware of, and there may be no substitute for going through that, working through the exercises, hand-compiling small examples of your own, and possibly even implementing parts of the WAM in a suitable language.

I'm going to suggest that you try with it again, and ask specific questions here if you get stuck on something.

But if that doesn't sound like something that you want to do right now, you may want to go through a less complicated abstract machine first, such as the SECD machine. The WAM was, after all, influenced by abstract machines that came before it, and that is assumed knowledge.

---
Tags: compilers, prolog, logic-programming
---


# Question
Title: Recurrence relation for the number of "references" to two mutually recursive function
I was going through the Dynamic Programming section of Introduction to Algorithms (2nd Edition) by Cormen et. al. where I came across the following recurrence relations in the context of assembly line scheduling

(Note: Assembly line scheduling or dynamic programming is not required to answer to the question though, it is just for information so that it shall help relating the context).

---

$(1),(2),(3)$ are three relations as shown.

$$f\_{1}\[j\] = \begin{cases} e\_1+a\_{1,1} &\quad\text{if } j=1\\ \min(f\_1\[j-1\]+a\_{1,j},f\_2\[j-1\]+t\_{2,j-1}+a\_{1,j})&\quad\text{if } j\geq2\\ \end{cases}\tag 1$$

Symmetrically,

$$f\_{2}\[j\] = \begin{cases} e\_2+a\_{2,1} &\quad\text{if } j=1\\ \min(f\_2\[j-1\]+a\_{2,j},f\_1\[j-1\]+t\_{1,j-1}+a\_{2,j})&\quad\text{if } j\geq2\\ \end{cases}\tag 2$$

(where $e\_i,a\_{i,j},t\_{2,j-1}$ are constants for $i=1,2$ and $j=1,2,3,...,n$)

$$f^\star=\min(f\_1\[n\]+x\_1,f\_2\[n\]+x\_2)\tag 3$$

---

The text tries to find the recurrence relation of the number of times $f\_i\[j\]$ ($i=1,2$ and $j=1,2,3,...,n$) is referenced if we write a mutual recursive code for $f\_1\[j\]$ and $f\_2\[j\]$. Let $r\_i(j)$ denote the number of times $f\_i\[j\]$ is referenced.

They say that,

From $(3)$,

$$r\_1(n)=r\_2(n)=1.\tag4$$

From $(1)$ and $(2)$,

$$r\_1(j)=r\_2(j)=r\_1(j+1)+r\_2(j+1)\tag 5$$

---

***I could not quite understand how the relations of $(4)$ and $(5)$ are obtained from the three corresponding relations. (directly without any proof, is it so trivial?)***

Thought I could make out intuitively that as there is only one place where $f\_1\[n\]$ and $f\_2\[n\]$ are called, which is in $f^\star$, so probably in $(4)$ we get the required relation.

But as I had not encountered such concept before I do not quite know how to proceed. I would be grateful if someone guides me with the mathematical prove of the derivation as well as the intuition.

\[Note: However an alternative to mathematical induction shall be more helpful as it is a mechanical cookbook method without giving much insight into the problem though (but if in case there is no other way out, then even mathematical induction is appreciated if I can get the intuition behind the proof)\].

# Answer
It looks like that you are exhausted after a long and tiring journey that you have taken to comprehend the setup of assembly-line scheduling, the step 1 on the structure of the fastest way through the factory and the step 2 on a recursive solution.

It is straightforward to understand formula (4) and (5).

When we program a recursion solution using formula (1), (2) and (3), the left-hand side of each formula is transformed to the signature of its implementing method while the right-hand side is transformed to the body of the method.

For example, (3) is transformed to pseudo-Python code

```
def f_star(n):
    return min(f_1(n) + x_1, f_2(n) + x_2)

```

So, when $f^\star$ is referenced, i.e., when `f_star` is called, $f\_1\[n\]$ and $f\_2\[n\]$ will be referenced, i.e., `f_1(n)` and `f_2(n)` will be called, where `f_1(.)` and `f_2(.)` will be explained below. Since we will call `f_star(n)` once, which is enough to get the value of $f^\star$, we get formula (4).

Formula (1) is transformed to pseudo-Python code

```
def f_1(j):
    if j == 1:
        return e[1] + a[1][1]
    else:
        return min(f_1(j - 1) + a[1][j], f_2(j - 1) + t[2][j - 1] + a[1][j])

```

So whenever $f\_1\[j\]$ is referenced, i.e., when $f\_1(j)$ is called, $f\_1\[j-1\]$ will be referenced exactly one, i.e., `f_1(j-1)` will be called exactly once.

Similarly, whenever $f\_2\[j\]$ is referenced, $f\_1\[j-1\]$ will be referenced exactly once. (You can write the function `f_2(j)` explicitly yourself to check it out.)

Note that any reference to $f\_1\[j-1\]$ must be brought by either a reference to $f\_1\[j\]$ or a reference to $f\_2\[j\]$. So we have $$r\_1(j-1) = r\_1(j) + r\_2(j).$$

Similarly or by symmetry, we also have $$r\_2(j-1) = r\_1(j) + r\_2(j).$$

Replacing $j$ by $j+1$, we get formula (5).
> 2 votes

---
Tags: proof-techniques, recurrence-relation, recursion
---


# Question
Title: Finding maximum subgraph with vertices of degree at most k
Let $G = (V, E)$ be an undirected graph and $U \subseteq V$ some subset of its vertices. An induced graph $G\[U\]$ is graph created from $G$ by removing all vertices that are not part of the set $U$.

I want to find a polynomial time algorithm that has graph $G = (V, E)$ and integer $k$ as input and returns a maximum set $U \subseteq V$ with largest size such that all vertices of $G\[U\]$ have degree at most $k$.

My idea with greedy algorithm that removes vertices with largest degree or vertices connected with most vertices with degree greater than $k$ doesn't work.

Does anyone know how to solve this problem in polynomial time?

# Answer
> 4 votes
Let $G$ be any graph and let $k = 0$.

This problem is, as you correctly pointed out in a comment, better known as Independent Set and is famously NP-complete.

It is therefore unlikely that there is an algorithm solving your problem (which is slightly more general) in polynomial time.

---
Tags: graphs
---


# Question
Title: Proof of inequality $\lceil x \rceil \le x+1$
I went through the Master Theorum extension for floors and ceiling section **4.6.2** in the book **Introduction to Algorithms**

It had the following statement:

> Using the inequality $\lceil x \rceil \le x+1$

But I haven't seen the inequality anywhere and could not understand the verifiability of inequality.

Instead the Chapter Floors and ceilings defined floors and ceilings as:

$$x-1 \lt \lfloor x \rfloor \le x \le \lceil x \rceil \lt x+1 $$

Please clear my doubt over this.

On how to use this identity and which identity to be considered when because both of them define completely different inequalities.

Thank you.

# Answer
The definition of $\lceil x \rceil$ is:

> $\lceil x \rceil$ is the minimal integer $n$ such that $n \geq x$.

(The existence of such an integer makes the reals an *Archimedean* field.)

Let us assume, for the sake of contradiction, that $\lceil x \rceil \geq x + 1$. Then $\lceil x \rceil - 1 \geq x$. Since $\lceil x \rceil - 1$ is also an integer, this contradicts the definition of $\lceil x \rceil$. Thus $\lceil x \rceil \< x + 1$.

It is also easy to check that the inequality is tight, in the sense that $1$ cannot be replaced by any smaller $\theta$. Indeed, if $\theta = 1 - \epsilon$ for $\epsilon \in (0,1)$, then $\lceil \epsilon \rceil = 1 = \epsilon + \theta$.
> 2 votes

---
Tags: master-theorem
---


# Question
Title: Computing automaton for $L(A) / L(B)$ gives ones for $A,B$
I'm trying to figure out whether infinite language change the answer.

> Show that the following language is decidable: $$L=\\{\langle A,B \rangle : \text{$A,B$ are DFAs, $L(B)$ is finite, and $L(A)/ L(B)=L(0^\*1^\*)$}\\}.$$

(I am talking about right division.)

We know how to check whether the language of a DFA is finite, and given two DFAs, we know how to check whether their languages are equal. The algorithms I know to the above problems uses the DFA's, so it is necessary having the DFA's in order to decide those problems.

I'm trying to figure out whether $|L(B)|=\infty$ changes the answer. To the best of my understanding, because $|L(B)|\<\infty$, we can explicitly construct a DFA that accepts $L(A)/ L(B)$, whereas if $L (B)=\infty$ all we know is about the existence of $DFA$ that accepts $L(A)/ L(B)$.

However, even if $L(B)$ is an infinite language, since there is a finite number of DFAs, one of which accepts $L(A) / L(B)$, I can certainly know that there is a Turing machine that decides the language $L$. Right?

# Answer
> 2 votes
What you are really asking is whether given automata $A,B$, we can construct an automaton whose language is the left quotient $$ L(A) \backslash L(B) = \\{ w : \exists x \in \Sigma^\* \text{ s.t. } x \in L(A) \text{ and } xw \in L(B) \\}. $$ (The question has meanwhile changed to refer to right quotient, which can be handled similarly.)

Here is such a construction. Suppose that $A,B$ are DFAs with states $Q\_A,Q\_B$, initial states $q\_{0A},q\_{0B}$, transition functions $\delta\_A,\delta\_B$, and final states $F\_A,F\_B$. We construct an NFA with states $Q = (\\{0\\} \times Q\_A \times Q\_B) \cup (\\{1\\} \times Q\_B)$, initial state $\langle 0, q\_{0A}, q\_{0B} \rangle$, final states $\\{1\\} \times F\_B$, and the following transition function $\delta$:

* $\delta(\langle 0, q\_A, q\_B \rangle, \epsilon) = \\{ \langle 0, \delta\_A(q\_A,\sigma), \delta\_B(q\_B,\sigma) \rangle : \sigma \in \Sigma \\}$ for all $q\_A \in Q\_A \setminus F\_A$ and $q\_B \in Q\_B$.
* $\delta(\langle 0, q\_A, q\_B \rangle, \epsilon) = \\{ \langle 0, \delta\_A(q\_A,\sigma), \delta\_B(q\_B,\sigma) \rangle : \sigma \in \Sigma \\} \cup \\{ \langle 1, q\_B \rangle \\}$ for all $q\_A \in F\_A$ and $q\_B \in Q\_B$.
* $\delta(\langle 1, q\_B \rangle, \sigma) = \\{ \langle 1, \delta\_B(q\_B, \sigma) \rangle \\}$ for all $\sigma \in \Sigma$ and $q\_B \in Q\_B$.

# Answer
> 3 votes
This answers a different version of the question, in which the language in question is $L(A) \setminus L(B)$.

Here is an algorithm for deciding $L$:

* Use the product construction to construct a DFA $C$ whose language is $L(A) \setminus L(B)$.
* Let $D$ be a DFA whose language is $0^\*1^\*$.
* Use the product construction again to construct a DFA $E$ whose language is $L(C) \Delta L(D)$.
* Check (using BFS/DFS) whether some final state of $E$ is reachable from its initial state.
* Output "yes" if no final state is reachable from the initial state. Otherwise output "no".

As you can see, whether the languages encountered along the way are finite or infinite makes absolutely no difference for this algorithm.

---
Tags: turing-machines, finite-automata, decision-problem
---


# Question
Title: How does an inverted index reduce storage requirements?
In p. 7 of the book "Introduction to Information Retrieval" (by Manning et al), the authors explain how, given a collection of text documents, an inverted index is built by tokenizing, then sorting the (term, docID) pairs, merging multiple occurrences of the same pairs, and the pairs for each term are grouped into a posting list. It is then mentioned that "Because a term generally occurs in a number of documents, this data organization already reduces the storage requirements of the index." My question is: how are the storage requirements reduced? It seems to me that if a term occurs in $k$ documents, then these $k$ documents' ID's must all be mentioned in the linked list for this term.

If a term occurs multiple times in the same document, then because the inverted index mentions a docID at most once in a term's list, there is a reduction in storage. But this condition is different from the condition that a term occurs in multiple (distinct) documents.

# Answer
> 1 votes
I think the author meant that by separating the index into the "dictionary" part and the "postings" part, we reduce the storage requirements of *the strings themselves*, because now we only have to store one string for each unique word. It's as if you are storing the vocabulary of the language itself, independent from the documents. It is also mentioned later that the dictionary is usually kept *in memory*, so it is important to make sure it doesn't take up much space.

---
Tags: data-mining, information-retrieval
---


# Question
Title: closure of Context free grammer to homomorphism using PDA
I was looking online, on sipser book, and on lecture notes and I can't find a proof to closure of context free languages to homomorphism that using PDA instead of CFG. I'm not looking for a full and formal proof, I just want to understand the general idea.

# Answer
The idea is to replace a single transition by a sequence of transitions.

Suppose for example that $h(\sigma) = \tau\_1 \ldots \tau\_\ell$, and consider a transition at state $p$ which replaces the symbol $A$ on the stack with the string $\alpha$, and moves to state $q$.

We replace this transition by a sequence of transitions $p \to s\_1 \to \cdots \to s\_{\ell-1} \to q$, which read the letters $\tau\_1,\ldots,\ell$ in sequence; the states $s\_1,\ldots,s\_{\ell-1}$ are unique for handling this transition. The first transition $p \to s\_1$ replaces $A$ with $\alpha$, and the rest don't change the stack.
> 2 votes

---
Tags: context-free, closure-properties
---


# Question
Title: What subfields in computer sciences may one study without learning Object Oriented Programming?
What subfields in computer sciences may one study without learning Object Oriented Programming or is there some kind of degree in Computer Science without the OOP knowledge requirement?

Is there a language without OOP?

Does one need to know OOP to simulate a CPU?

I wanted to earn a CS degree without ever learning OOP. Is there a name for that?

My guess what that Computer science without OOP is simply applied Statistics or Machine Learning using SKlearn and packages.

# Answer
Object Oriented Programming is a type of programming paradigm.

A Computer Science degree is mostly theoretical (not only machine learning and applied statistics! Believe me there is so much more), so you wont see any of this in *most* courses, however, in a Software Engineering degree I suppose you do learn more about OOP.

Anyways, OOP is always good to know. Its not as complicated as you would think from its fancy name, and it gives a nice way to write organized code, and most programming languages support that kind of programming.

However, there are some programming languages that use a different type of programming paradigm called "functional programming". I recommend you to take a look at it too.

If you are wondering about what kinds of things there are in a CS degree, feel free to ask me!

BTW: This Stack Exchange site is for theoretical computer science, so questions about theoretical computer science problems are seen here all of the time.
> 2 votes

# Answer
Depending on where you study, you might be able to get a CS degree without Object Oriented Programming, but the chances are slim. Most degrees would require you to take some programming courses using some general purpose languages along the way, and that will often be Java, C++ or similar, and there you have OOP. Hard to avoid.

But that's good for you, because if you want any job outside university, and you have not a clue about OOP, your chances are practically zero to get any job.
> 3 votes

---
Tags: cpu, simulation, object-oriented
---


# Question
Title: C++ STL: How does the distance() method work for a set/ multiset (stored internally as a self balancing tree)?
I'm working on the problem: Count smaller elements on right side using Set in C++ STL

The solution is to add each element to the set and then to count the elements on the left, the distance function is called.

This is the algo:

```
1. Traverse the array element from i=len-1 to 0 and insert every element in a set.
2. Find the first element that is lower than A[i] using lower_bound function.
3. Find the distance between above found element and the beginning of the set using distance function.
4. Store the distance in another array Lets say CountSmaller.
4. Print that array

```

I'm having a hard time to visualize or understand how can distance function be used with a set like structure since internally, the set data is stored as a self balanced tree (Red Black Tree). Whats the concept of distance for a self balancing tree and how does calling distance() give us the count of smaller elements on the right side?

# Answer
> 2 votes
The complexity of the distance function depends on the type of the iterators supplied: in general it only required to take linear time in the distance but, in the special case in which the input iterators are random access iterators, the worst-case running time is linear. (I believe this is accounting for the time spent in the function in itself, and assumes that the time needed to advance iterators is constant).

The C++ specification do not mandate any particular implementation as long as it conforms to the required complexity so your question cannot be answered without inspecting the particular implementation that you are using. However, just to convey the intuition, here are two possible implementations that would conform to the requirements:

* Given random access iterators $x$ and $y$, distance($x$, $y$) returns $y-x$.
* For general iterators increment $x$ until it equals $y$. Return the number of increments performed.

The type `std::set` does not return a random access iterator, therefore `std::distance` can take linear time and the second implementation above can be used. Now your question reduces to "how can the standard library iterate over the elements of a `std::set` in sorted order?"

The answer to this question depends once again on the implementation as there is no particular data structure mandated by the standard to implement `std::set`. Since you mention red-black trees, which are a special kind of BSTs, this can easily be done by noticing that the order of iteration coincides with the order in which the vertices of a BST are visited by an in-order visit.

Notice that the concept of distance completely abstracts from the data structure used to store the elements of the set. Instead it only refers to the positions in which two elements appear when using an iterator to access the collection's contents.

In the case of `std::set` the elements appear in sorted order. This also means that the distance between an iterator pointing to the beginning of the collection and an iterator pointing to an element $x$ is exactly the number of elements that are smaller than $x$.

---
Tags: sets, c++
---


# Question
Title: If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?
As posed in the question; the statement naively seems like it should be self-evident but there are no algorithms that come immediately to mind. Suppose I have some domain $A$ (in my case a subset of $\mathbb{Z}^n$ for some $n$, but I would expect any answer to be independent of that structure), and a domain $B\subset A$. If I have an efficient algorithm for uniformly sampling from $A$, and an efficient algorithm for uniformly sampling from $B$, is there any way of 'combining' these to get an efficient algorithm for uniformly sampling $A-B$? I can certainly rejection-sample, but if $|A-B|\ll|A|$ then there's no guarantee that that will be efficient.

# Answer
**Theorem:** For any given $A$, either there are good algorithms to sample *every* subset of $A$, or what you're describing is impossible.

**Proof** *(perhaps slightly informal)*: Suppose there are some "problematic" subsets of $A$ (those which cannot be efficiently sampled). Let $C$ be one of those subsets. From the fact that $C$ is problematic, it follows that $|C| \ll |A|$ (otherwise $C$ could be dealt with by rejection-sampling). Now let $B = A \setminus C$. Clearly, rejection-sampling *does* work on $B$, because $B$ is almost the entirety of $A$. So now we have algorithms for both $A$ and $B$, but no algorithm for $C$. Q.E.D.

Here's a ridiculous example: $A = \\{(x\_1, x\_2, x\_3, x\_4) \mid x\_i \in \mathbb{Z},\\; 2 \< x\_i \< 10^{10^{10^{1000}}}\\}$ and $B$ contains only those quadruplets of numbers which are *not* counterexamples to Fermat's Last Theorem (i.e. such that $x\_1^{x\_4} + x\_2^{x\_4} \neq x\_3^{x\_4}$). It's trivially easy to sample $B$, but that gives us no clue whatsoever about how to do $A \setminus B$.
> 3 votes

# Answer
In general it is not possible to construct an efficient sampling algorithm for $A\setminus B$ given efficient ones for $A$ and $B$ (depending on your definition of efficient). Here is a simple counter-example, where efficient means $o(n)$ where $n$ is the size of $A$. Also for simplicity let $A$ be a set of integer. Now, define $B$ as $A\setminus \\{x\\}$ where $x$ is any integer. Then, if we have an efficient sampling algorithm for $A$ and $B$ and could create an efficient one for $A\setminus B$ which is equal to $\\{x\\}$, we could use it to efficiently check if $x$ is in $A$. However, by our definition of efficient this would mean that we could check membership in a without looking at all elements in a which is not possible :)
> 0 votes

---
Tags: probability-theory, sampling, random-number-generator
---


# Question
Title: A question regarding definition of Deterministic Subexponential Time (SUBEXP)
First Look at the definition of SUBEXP from Complexity Zoo:

> **SUBEXP: (Deterministic Subexponential-Time)** The intersection of DTIME($2^{n^\epsilon}$) over all $\epsilon$\>0. (Note that the algorithm used may vary with $\epsilon$.) or it can be written as: SUBEXP = $\bigcap\_{\epsilon\>0}$**DTIME**$(2^{n^\epsilon})$.

So, I bring the definition of EXP which is:

> EXP = $\bigcup\_{k\geq 1}$**DTIME**$(2^{n^k})$

The definition of EXP is clear, since it includes all polynomial of n to the power of 2. (e.g. $2^{n^{30}}$ or $100^{n^{99}}$ etc.)

First question: what is domain of $\epsilon$? I guess it is between 0 and 1 but it didn't specify in the definition. Is it usual that when we have $\epsilon$ then it means between 0 and 1.

Second question: Now, in case of SUBEXP, it is not clear how the definition is about the intersection? I mean, Shouldn't be written as following: $\bigcup\_{1\>\epsilon\>0}$**DTIME**$(2^{n^\epsilon})$. For example by definition above what is the intersection of: $2^{n^{0.01}} \bigcap 2^{n^{0.02}} ?$

Third question: There are two definition of SUBEXP in wikipedia, Is there definition that take over all subexponential or we don't since this is why we have two definitions.

Thank you!

# Answer
> 1 votes
In the definition of SUBEXP, $\epsilon$ ranges over all positive reals. But you get the same definition if you ask that $\epsilon \< \epsilon\_0$, for an $\epsilon\_0\>0$ of your choice; if you ask that $\epsilon$ be rational; if you only go over $\epsilon = 1/n$; and so on. This is because DTIME is monotone: if $f \leq g$ then $\mathsf{DTIME}(f) \subseteq \mathsf{DTIME}(g)$.

An alternative definition of SUBEXP would be: $$ \mathsf{SUBEXP} = \bigcup\_{g(n) = o(1)} \mathsf{DTIME}(2^{n^{g(n)}}), $$ often denoted simply by $\mathsf{DTIME}(2^{n^{o(1)}})$.

Some examples: $\mathsf{P} \subseteq \mathsf{SUBEXP}$; a function which can be computed in time $2^{n^{1/\log\log n}}$ is in $\mathsf{SUBEXP}$; and a function which can be computed in time $2^{\log^{10} n}$ is in $\mathsf{SUBEXP}$.

In contrast, a function which can be computed in time $2^{n^{1/10}}$ is not necessarily in $\mathsf{SUBEXP}$ (and by the time hierarchy theorem, there is such a function which lies outside $\mathsf{SUBEXP}$).

A function in $\mathsf{DTIME}(2^{n/\log n})$ lies in SUBEPT but not necessarily in SUBEXP.

---
Tags: complexity-classes, definitions
---


title: Convert HSV to RGB colors

text:
# Question
Title: Convert HSV to RGB colors
HSV colors are composed of a triple of numbers: hue $\in \[0, 360)$ (in degrees), saturation $\in \[0, 1\]$ and value or brightness $\in \[0, 1\]$. RGB colors instead are more well-known and are also composed of a triple of numbers all of them in the range $\[0, 1\]$ or in a byte $\[0, 255\]$.

I was trying to implement an algorithm that converts HSV colors to the corresponding RGB ones, and I managed to do it based on the following algorithm provided by Wikipedia. (I'm reporting the whole related text).

> $C = V \times S$
>
> \begin{align} H^\prime &= \frac{H}{60^\circ} \\ X &= C (1 - |H^\prime \\;\bmod 2 - 1|) \end{align}
>
> ($R\_1$, $G\_1$, $B\_1$) = \begin{cases} (0, 0, 0) &\mbox{if } H \mbox{ is undefined} \\ (C, X, 0) &\mbox{if } 0 \leq H^\prime \< 1 \\ (X, C, 0) &\mbox{if } 1 \leq H^\prime \< 2 \\ (0, C, X) &\mbox{if } 2 \leq H^\prime \< 3 \\ (0, X, C) &\mbox{if } 3 \leq H^\prime \< 4 \\ (X, 0, C) &\mbox{if } 4 \leq H^\prime \< 5 \\ (C, 0, X) &\mbox{if } 5 \leq H^\prime \< 6 \end{cases}
>
> Finally, we can find $R$, $G$, and $B$ by adding the same amount to each component, to match value
>
> \begin{align} &m = V - C \\ &(R, G, B) = (R\_1 + m, G\_1 + m, B\_1 + m) \end{align}

where $H$ is the hue, $V$ is the value, $S$ is the saturation, $C$ is what Wikipedia calls the *chroma* and $R, G, B$ are correspondingly the values of red, green and blue.

Before wanting to find a way to convert HSV colors to RGB Colors, I had already a formula to convert RGB colors to HSV, which I wanted to manipulate to obtain a inverse formula, but I didn't manage to do it.

Here's a picture:

*I could show you my attempts, but they are not useful*.

## Question

* How is the formula (provided by Wikipedia) to convert a HSV to RGB colors derived from the formula in the picture above to convert RGB to HSV colors?

*I'm asking this question here because I'm looking for a mathematical manipulation of one formula to arrive at another. I'm also asking this question because I think it could be interesting also for others. If you think this question should be moved to another stackexchange's website, feel free to migrate it or just tell me and I will post it where you indicate me.*

# Answer
This is my first post on StackExchange! I realize it's on a fairly old post but perhaps someone else will appreciate an explanation!

I will preface this by saying that I come from a background in software development and mathematics, but I'm going to try and lay it all out, step-by-step without using coding concepts, just math.

All of the formulae will be at the bottom, in case you are uninterested in the explanation behind each.

From here on, $H$ will represent Hue, $S$ will represent saturation, and $V$ will represent value. We will also need to represent Chroma, which is the difference between max and min values of the RGB model, which will be represented by $C$.

Also, red, green, and blue will be represented by $R$, $G$, and $B$ respectively.

First we will find some intermediary values that we will need in order to derive other values. We will start with finding the max, which in the HSV model is coincidentally the value attribute itself.

$$max = V$$

---

Now we will find the Chroma. I'll post the formula first then show how it is derived.

$$C = S * V$$

This comes from the formula to calculate the saturation in your RGB to HSV image above, in which

$$S = (Max(R,G,B) - Min(R,G,B)) / Max(R,G,B)$$

As we just discovered, $V$ is equal to $Max(R,G,B)$, so we can replace it in the previous formula, to arrive at

$$S = (V - Min(R,G,B)) / V$$

Therefore we can find $C$ by multiplying $S$ by $V$, thus eliminating $V$ from the denominator on the right hand side.

$$C = S * V = (V - Min(R,G,B)) / V * V$$

---

Knowing $C$, we can now find $min$.

$$min = max - C$$

This comes from the formula for $C$ itself. All we need to do is rearrange the variables. We can do this two ways, but I'll keep it to the one that just uses addition and subtraction operations.

First we need to get min to the other side, which will negate it's value implicitly. We do this by adding $min$ to both sides.

$$C + min = max - min + min$$

so

$$C + min = max$$

Then we need to move $C$ to the other side, this time we will subtract it from both sides.

$$C - C + min = max - C$$

The $C$ values on the left hand side cancel out and we are left with our formula for $min$ above.

---

Our last variable to calculate will be $H'$, but we have to prepare it first. This explanation will be a bit long and also a little "leap-of-faithy" which I was hoping to avoid, but hopefully I can give enough detail to make the reasoning behind a later step a little more understandable.

Recall that $H$ in the RGB to HSV conversion is calculated differently depending on the max value. There are $3$ ways to calculate it. We also know that the range for $H$ is $\[0$ to $360)$.

Therefore each of the $3$ equations must result in a unique range of $120$ values each, as $360 / 3 = 120$

Let's first take a look at the calculation for $H$ when $R$ is the $max$,

$$H = 60 * (0 + (G - B) / (R - min))$$

Assuming that $G$ is larger than $B$, our result will always be positive. If $R = 1$, $G = 1$, and $B = 0$, $min$ would be equal to $B$, and our formula would look like

$$H = 60 * (0 + (1 - 0) / (1 - 0))$$

which resolves to

$$H = 60$$

On the opposite side, let's assume that $B$ is larger than $G$. Now our result will always be negative. Let's use the same values from the last example, but switch the $G$ and $B$ values, so now $G = 0$ and $B = 1$. The $min$ remains $0$ as $G$ is now the smallest of the RGB values. Our new formula looks like

$$H = 60 * (0 + (0 - 1) / (1 - 0))$$

resolving to

$$H = -60$$

Notice the range of the results from these two examples?

$$range = 60 - (-60) = 120$$

So we know that these are the minimum and maximum values for $H$ when $R$ is the largest of the RGB values. Now let's take a look at just one half of the formula for when $G$ is the largest.

Recall

$$H = 2 + (B - R) / (G - min)$$

Assuming that $R$ is greater than $B$, our result will again be negative. We'll let $G = 1$, $B = 0$, and $R = 1$ (For the sake of readability and ease-of-understanding, I'm allowing $R$ to equal 1. In reality, it could only approach $1$ but never equal it exactly, as that would force $H$ to take the first formula since it would consider $R$ as the $max$ value). The $min$ value is equal to 0. Our formula will look like

$$H = 60 * (2 + (0 - 1) / (1 - 0))$$

resolving to

$$H = 60$$

We already know that this must be the smallest value for $H$ when $G$ is the largest RGB value, and you can check for when $B$ is the largest if you like, but this means that the only negative values we can have for $H$ are in the range $\[-60$ to $0)$. This also indicates that the range of values to multiply by $60$ when solving for $H$ must be in the range $\[-1$ to $5)$. The range has $6$ values $5 - (-1) = 6$, so $60 * 6 = 360$.

Okay, that was a whole load of information just to say that we need to convert $H$ back into this "pre-scaled" range of $\[-1$ to $5)$, that will be called $H'$. This is done simply enough by $$H' = (H - 360) / 60$$ when $H \>= 300$, and $$H' = H / 60$$ when $H \< 300$

The variable $H'$ is equal to a value in the range

* $\[-1$ to $1)$ when the $max$ is $R$,
* $\[1$ to $3)$ when the $max$ is $G$,
* $\[3$ to $5)$ when the $max$ is $B$,

---

Okay, those are all of the intermediary variables we need in order to finally solve for our $R$, $G$, $B$ values.

First, we have to determine what range $H'$ is between in order to know which RGB components we are solving for in each subsequent step.

If $H'$ is in the range $\[-1$ to $1)$, then we will be solving for $G$ and $B$. We know from your RGB to HSV conversion that our minimum and maximum values for $H$ are $\[-60$ to $60)$ when $R$ is the largest. So, when we divide that range by $60$ to arrive at $H'$, we get the range $\[-1$ to $1)$. This also means that

$$R = max$$

Recall that this range depends on the relationship between $G$ and $B$. If $G \> B$, the resulting value was positive, and if $G \< B$, then the resulting value was negative.

With that in mind, we need to find out the sign polarity of $H'$. There is a slight modification in the following formula that will become apparent when I explain what to do if $G$ or $B$ is the maximum value instead of $R$.

If $H' - 0 \< 0$, then

$$G = min$$

and using our $H'$ formula for when $R$ is the maximum value, we can substitute in our values for $H'$, $R$, and now $G$, which will allow us to rearrange the formula and solve for $B$. We also already have a variable for $R - min$, which is the same as $max - min$, which in turn is equal to $C$.

$$H' = 0 + (G - B) / C$$

In theory we must first subtract $0$ to the other side, but since it doesn't affect anything at the moment, I'll ignore it. We first multiply out the denominator on the right hand side to get

$$H' * C = G - B$$

and then subtract $G$

$$H' * C - G = -B$$

finally we need to invert the entire equation. I will swap the right and left hand sides as well for readability

$$B = G - H' * C$$

Therefore, when $H'$ is in the range $\[-1$ to $1)$ and $H' - 0 \< 0$ $$R = max,$$ $$G = min,$$ $$B = G - H' * C$$

---

What if $H' - 0 \>= 0$?

This just means that instead of $G$ being less than $B$, now it's greater than $B$.

There is a slight alteration to the formula for $G$, which isn't quite the same as it was for when $G$ was less than $B$.

Recall that

$$H' = 0 + (G - B) / C$$

But this time we know $H'$, $R$, and $B$, which means we must solve for $G$

Again, I'll ignore the 0, and multiply out the denominator from the right hand side

$$H' * C = G - B$$

and finally add $B$ to both sides to remove it from the right hand side,

$$H' * C + B = G$$

Therefore, when $H'$ is in the range $\[-1$ to $1)$ and $H' - 0 \>= 0$ $$R = max,$$ $$G = B + H' * C,$$ $$B = min$$

---

The other cases are derived in much the same way, with slight modifications.

* if $H'$ is in the range $\[1$ to $3)$, the $max$ value will be $G$
* if $H'$ is in the range $\[3$ to $5)$, the $max$ value will be $B$

Let's assume our max value is $G$. Our $H'$ equation is now

$$H' = 2 + (B - R) / (G - min)$$

Since our max is now $G$, the expression $G - min$ is the same as $C$, so

$$H' = 2 + (B - R) / C$$

Remember when I said I'd make as small modification to a formula that might not make sense straight away but would come into play later? Well, it's back. To check for polarity here, we must subtract the value corresponding to which RGB value is greatest from $H'$.

So, we check for polarity by

* $H' - 0$ when $max$ is $R$,
* $H' - 2$ when $max$ is $G$, and
* $H' - 4$ when $max$ is $B$

Now, we can't ignore the $2$ in our new $H'$ formula, so we'll first subtract it from both sides

$$H' - 2 = (B - R) / C$$

then multiply out the denominator

$$(H' - 2) * C = B - R$$

At this stage, if $(H' - 2) \< 0$, we will be solving for $R$ since we know that in order for that sign to have been negative, $R$ must have been greater than $B$, meaning

$$B = min$$

and after subtracting $B$ to the other side and inverting the entire equation,

$$R = B - (H' - 2) * C$$

So, when $H'$ is in the range $\[1$ to $3)$ and $H' - 2 \< 0$ $$R = B - (H' - 2) * C,$$ $$G = max,$$ $$B = min$$

Similarly to our case from earlier, if $min$ was $R$ instead of $B$, then

$$B = R + (H' - 2) * C$$

So, when $H'$ is in the range $\[1$ to $3)$ and $H' - 2 \>= 0$ $$R = min,$$ $$G = max,$$ $$B = R + (H' - 2) * C$$

---

Similarly, with no more explanation, it should hopefully be apparent that

When $H'$ is in the range $\[3$ to $5)$ and $H' - 4 \< 0$ $$R = min,$$ $$G = R - (H' - 4) * C,$$ $$B = max$$

And when $H'$ is in the range $\[3$ to $5)$ and $H' - 4 \>= 0$ $$R = G + (H' - 4) * C,$$ $$G = min,$$ $$B = max$$

---

Hopefully that fully explains everything! I know it was quite a long read but I wanted to give as thorough an explanation as possible. I don't believe I missed anything, but if I did please let me know so I can amend it. Also, with a bit of rearranging, you can arrive at the formulae given on the Wikipedia page, but this post is already so long!

The formulae for everything are included below, thanks for reading!

---

$$max = V$$ $$C = S * V$$ $$min = max - C$$

---

If $H \>= 300$ then $$H' = (H - 360) / 60$$ otherwise if $H \< 300$ then $$H' = H / 60$$

---

If $H'$ is in the range $\[-1$ to $1)$

* If $H' - 0 \< 0$
    + $R = max$
    + $G = min$
    + $B = G - H' * C$
* Otherwise if $H' - 0 \>= 0$
    + $R = max$
    + $G = B + H' * C$
    + $B = min$

---

If $H'$ is in the range $\[1$ to $3)$

* If $H' - 2 \< 0$
    + $R = B - (H' - 2) * C$
    + $G = max$
    + $B = min$
* Otherwise if $H' - 2 \>= 0$
    + $R = min$
    + $G = max$
    + $B = R + (H' - 2) * C$

---

If $H'$ is in the range $\[3$ to $5)$

* If $H' - 4 \< 0$
    + $R = min$
    + $G = R - (H' - 4) * C$
    + $B = max$
* Otherwise if $H' - 4 \>= 0$
    + $R = G + (H' - 4) * C$
    + $G = min$
    + $B = max$
> 9 votes

---
Tags: algorithms, computer-vision, algebra
---


title: Counting on a matrix

text:
# Question
Title: Counting on a matrix
I have an $n \times m$ matrix, and fill it with numbers of $1 \dots k$.

If a matrix can be turned into another matrix by exchanging its lines and exchanging its columns, the two matrices are considered to be the same.

I know that I can easily computed the numbers of the different matrices out in $O((n\times m)^k)$ time, but is there any better algorithms for this problems?

Also, I am wondering whether $\texttt{Burnside's lemma}$ or $\texttt{Polya's Theorem}$ work here. I am having no ideas with them.

# Answer
Copied from here.

# The mathematics

Consider the group $G=S\_w\times S\_h$, where $S\_w$ and $S\_h$ are the symmetric group of the sets $W=\\{1,2,3,\ldots,w\\}$ and $H=\\{1,2,3,\ldots,h\\}$ with $w$ and $h$ elements, respectively. The group $G$ acts on the set $X=W\times H$, which we view as the set of indexes of the entries of the matrices.

Each matrix is a function $f:X\to S$, and element $f\in S^X$.

So, the problem consists of computing the cardinality

$$\left|S^X/G\right|$$

## Cycle index polynomial of a group of permutations

For a permutation group $G$ acting on a set $X=\\{1,2,3,\ldots,n\\}$ define the polynomial

$$Z(G,s\_1,s\_2,s\_3,\ldots,s\_n)=|G|^{-1}\sum\_{g\in G}\prod\_{k=1}^{n}s\_k^{c\_k(g)}$$

where $c\_k(g)$ is the number of cycles of length $k$ in the cycle decomposition of the permutation $g$.

**Polya's enumeration theorem** tell us that

$$\left|S^X/G\right|=Z(G,s,s,\ldots,s)=|G|^{-1}\sum\_{g\in G}s^{c\_k(g)}$$

## Cycle index of the Cartesian product

In our case, $G$ is the Cartesian product $S\_w\times S\_h$. In this paper they prove the following formula

$$Z(G\_1\times G\_2,s\_1,s\_2,\ldots,s\_{n\_1\cdot n\_2}) = Z(G\_1,s\_1,\ldots,s\_{n\_1})\otimes Z(G\_1,s\_1,s\_2,\ldots,s\_{n\_2})$$ where the product $\otimes$ (In the paper they use the symbol text reference mark) of polynomials is defined by:

If

$$f(x\_1,x\_2,...,x\_m)=\sum a\_{i\_1i\_2\ldots i\_m}x\_1^{i\_1}x\_2^{i\_2}\dotsm x\_m^{i\_m}\text{ and }g(x\_1,x\_2,...,x\_n)=\sum b\_{j\_1j\_2\ldots j\_n}x\_1^{j\_1}x\_2^{j\_2}\dotsm x\_n^{j\_n}$$

then

$$f(x\_1,x\_2,\ldots,x\_m)\otimes g(x\_1,x\_2,\ldots,x\_n)=\sum a\_{i\_1i\_2\ldots i\_m}b\_{j\_1j\_2\ldots j\_n}\times\prod\_{\substack{1\leq r\leq m\\1\leq s\leq n}}(x\_{r}^{i\_l}\otimes x\_{s}^{j\_s})$$

where

$$x\_{r}^{i\_l}\otimes x\_{s}^{j\_s} = x\_{\operatorname{lcm}(r,s)}^{\gcd(r,s)i\_rj\_s}$$

## Cycle index of the symmetric group

For the case of the symmetric group $S\_n$ acting on $\\\{1,2,3,\ldots,n\\\}$ we have

$$Z(S\_n)=\frac{1}{n}\sum\_{k=1}^{n}s\_kZ(S\_{n-k})$$

or explicitly

$$Z(S\_n,s\_1,s\_2,\ldots,s\_n)=\sum\_{r\_1+2r\_2+3r\_3+\ldots nr\_n=n}\frac{s\_1^{r\_1}s\_2^{r\_2}\dotsm s\_n^{r\_n}}{1^{r\_1}r\_1!2^{r\_2}r\_2!\dotsm n^{r\_n}r\_n!}$$

## Solution of the problem

Combining the results above we obtain that the number of classes of $w\times h$ matrices on $s$ symbols up to permutations of the rows and columns is $$N=\frac{1}{w!h!}\sum\_{\substack{i\in P(W)\\j\in P(H)}}\frac{w!}{1^{i\_1}i\_1!2^{i\_2}i\_2!\dotsm w^{i\_w}i\_w!}\frac{h!}{1^{j\_1}j\_1!2^{j\_2}j\_2!\dotsm h^{j\_h}j\_h!}s^{\sum\_{\substack{a\in i\\b\in j}}\gcd(a,b)}$$
where the outer sums runs over the partitions $i=(i\_1,i\_2,\ldots,i\_w)$ and $j=(j\_1,j\_2,\ldots,j\_h)$ of $w$ and $h$, respectively. This is, $i\_1+2i\_2+\ldots+wi\_w=w$ and $j\_1+2j\_2+\ldots+hj\_h=h$. The inner sums run over the elements $a$ and $b$ of the partitions $i$ and $j$. This is, $a$ takes the value $1$, $i\_1$ times, the value $2$ $i\_2$ times, and so on and likewise $b$ takes the value $1$ $j\_1$ times, the value $2$ $j\_2$ times, etc.

# Implementation

As seen in the final formula, we need to compute:

1. Partitions of a number
2. Greatest common divisors (gcd) of many numbers.
3. Factorials of many numbers.

For these, we can do:

1. To compute all partitions one can use the iterative algorithms here.
2. An efficient way to compute `gcd` one could use Euclidean algorithm. However, since we are going to need the gcd of all pairs of numbers in a range and each one many times. It is better to pre-compute the full table of gcd all at once by *dynamic programming*. If `a>b`, then `gcd(a,b)=gcd(a-b,b)`. This recurrence equation allows to compute gcd of larger pairs in terms of that of smaller pairs. In the table, one has the initial values `gcd(1,a)=gcd(a,1)=1` and `gcd(a,a)=a`, for all `a`.
3. The same happens for factorials. The formula will require the factorials of all numbers in a range many times each. So, it is better to compute them all from the bottom up using that `n! = n(n-1)!` and `0!=1!=1`.
4. The powers of $s$, which are also needed repeatedly in the sum could also be pre-computed.

An implementation in Python could look like this. Feel free to improve it.
> 4 votes

---
Tags: algorithms, complexity-theory, matrices, counting
---


# Question
Title: Why is there so little literature on partial order production?
Please excuse or improve the poor title of this question.

My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem.

So there is plenty of work on sorting algorithms.

Sorting is usually understood as creating a / *the one correct* total order given a set of elements `X` and their pairwise relationship `x >= x'` for all `x` in `X`. Or actually `>=` is the total order and the task is to create a sequence or directed graph s.t. `x` comes after `x'` iff `x>=x'`.

Now you want to do the exact same thing, only `>=` does not define a total order over `X`, but only a partial order.

This seems like a very straightforward generalization that I can only imagine is required quite often. Still, under the term **partial order production**, I find only very little literature on the topic / task.

Am I missing something?

**EDIT: Alternative Formulation**

Given a set of elements `X` and a function `f` that returns the relationship between any two elements `x,x'` in `X`. Create a DAG with an edge `x->x'` if the relationship is `>=` and `x'->x` if the relationship `f((x,x'))` is `<`. Then create the transitive reduction of the DAG.

1. `f(x,x')` is either `>=` or `<`. This is normal sorting.
2. `f(x,x')` is either `>=`, `<` or `?` (not comparable). This is partial order production.

I would say both are clearly ordering problems, given the relationship function `f` (*the order*) and the elements `X` to order.

Still you find so much on case (1) and hardly anything on case (2).

# Answer
This is a very well-known problem, known as topological sorting.

Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.
> 1 votes

# Answer
*This is a comment*

There is a confusion when you say that sorting is creating the correct total order. When sorting, the total order is input as the relation $\geq$. What sorting does is output the order-preserving map from the natural numbers $0,1,2,...$ to the totally ordered set (or multiset) that was input. Typically, when this is implemented the map is given in the form of an array in which the assignation $\operatorname{index}\mapsto\operatorname{value}$ is the map from the natural numbers.

With this in mind, you should try to rephrase ... (Well, you already rephrased what you intended to ask)

With your rephrasing, you essentially answered your own question.

Producing the graph, is a step that depends on your implementation. In principle the graph is already given in the input in the form of the relation $\geq$, which is the adjacency matrix and the set, or multiset, of values, which are the vertices (which you could consider weighted if you allow repetitions of the values). So, the only problem left in your interpretation of *ordering in partial orders* is the computation of transitive reduction.
> 1 votes

---
Tags: algorithms, sorting, dag, partial-order
---


# Question
Title: What is the time complexity of sorting n words length wise and then alphabetically? Should we consider the length of the strings in the complexity?
Let's assume I have a list of some words found in the English dictionary: \["hat", "assume", "prepare", "cat", "ball", "brave", "help" .... \]

I want to sort these words (which are n in number) in a way, such that they are ordered based on their length, but if 2 words have the same length, they are ordered alphabetically.

What is the time complexity of this sorting operation?

Would it be fair to say that the complexity is just O(nlogn) and not take into consideration the length of the strings? If the largest length is `S`, can the complexity also involve a factor of S?

# Answer
This algorithm requires at most $O(n \log n)$ string comparisons, assuming you use a suitable sorting algorithm.

If strings are at most $S$ characters long, each string comparison can take up to $S$ operations. So, the worst-case running time could be as large as $O(S n \log n)$.

If the size of the character set is constant, then it is possible to solve your problem in $O(n(S+\log n))$ time with a slightly different algorithm: compute the length of each string ($O(nS)$ time), sort the strings by length ($O(n \log n)$ time), then for each length, use radix sort on the strings of that length ($O(nS)$ time).
> 2 votes

# Answer
D.W's answer gives a good and practical complexity analysis for this question.

If you really wanna analyze the complexity in terms of the memory it takes to store the entire array (as a side note, all array elements must have the same length - so instead of storing the string you store a pointer to it) and you assume the alphabet is finite and the elements in the array are unique **then:**

If $n$ is the number of elements, notice that defining $s$ to be the total storage the array takes, then since all elements are unique, we have that the smallest case for $s$ would have 2 elements of size 1, 4 of size 2, 8 of size 3 and so on. this means $n=\Sigma\_{i=1}^k2^i=2^{k+1}-1\rightarrow k\approx log(n)$ and thus, $s=\Sigma\_{i=1}^ki2^i=\Theta(k2^k)=\Theta(nlog(n)).$ Then, from that if we want to find worst case for $n$ in terms of $s$, we have $O(nlogn)=O(s)$. Now you can substitute this into any running time of an algorithm you already know.

**Notice** that doing this wont really help you at all! Its better to think about the complexity in terms of the number of elements $n$ instead
> 0 votes

---
Tags: time-complexity
---


# Question
Title: What is the theoretical result of flattening a list containing only itself?
Consider the following python code

```
X = [None]
X[0] = X

```

This has many fun properties such as

```
X[0] == X

```

and

```
X[0][0][0][0][0][0][0][0] == X

```

I understand how this works from a practical standpoint, as it's all just the same pointer.

Now, when flattening a list, we tend to convert things from

```
[[1, 2, 3], [[4, 5], [6, 7]], 8, 9]

```

to

```
[1, 2, 3, 4, 5, 6, 7, 8, 9]

```

In this case, I am considering flattening to be reducing a multi-dimensional list down to a single list of only non-list elements.

In practice, flattening this list would be impossible, as it would create an infinite loop.

This may be more mathematical in nature, but I'm unsure how to put it in mathematical terms. Suppose we could flatten this list, would the result simply be the empty list?

For context, I initially got this idea by considering the list

```
X = [[], []]
X[0] = X

```

It is clear to see that at each *pass* of flattening, the empty list that is the second element simply disappears. This lead me to think that the overall result, may be the empty list.

Could it be possible that flattening this list would theoretically produce an infinitely long list of the list itself, as in

```
X == [X, X, X, X, X, X, ..., X]

```

This is purely a fun thought exercise. Any insight and discussion on this would be appreciated.

P.S. Although I'm looking for an answer in plain terms, if anyone is more mathematically inclined, I would be interested to see how this problem could be formulated in some sort of set notation. Please feel free to point me to a relevant math exchange thread as well.

P.P.S. I would also be interested in a solid proof (not formal) to go along with the answer.

# Answer
From a mathematical point of view, this is impossible: there is no such a thing as a set containing itself (in normal logic sense) or a vector who has itself as an element, so this question doesn't really mean anything outside the realm of using pointers in a list

**BUT,** on a second thought: I might be able to formulate what "flattening" is if you allow me to define things however I want.

Lets say our world is some graph $G$, nodes in it would be elements, and an edge $(v,u)$ would mean that the element $v$ contains the pointer to $u$. Then, in those terms, the array \[\[5,6\],,\[7\]\] might look like this:

Flattening the graph in this sense means to take every non-direct child of the root node (the array's node) and make it a direct child of it. Then, your array `X` looks like this:

And when you flatten it you would remain with the exact same graph, and therefore in this sense when you flatten `X` you would get simply `X` itself.

However, this is truly meaningless because it's only by the definition I just made up: you could have defined it in another way and it would have resulted in something else maybe!
> -1 votes

---
Tags: computability, logic, lists
---