# Question
Title: What algorithm is appropriate for a thermostat controlling the heating of a room with floor heating?
I built my own thermostat that controls the boiler heater for the radiant floor heating in my house and I would like to develop / implement a smarter temperature control algorithm. What I am specifically interested in is the ability to predict when to turn on the heating so that a certain temperature is achieved according to a schedule.

Suppose I want the temperature at 7 am to be 22 degrees Celsius. During the night I want it to be at 18C. Currently, I set the schedule up so that the heating is started at 6 am but depending on how cold it is during the night, an hour may be too little and the temperature does not rise to 22C or it may be to much and the temperature overshoots. I would like an algorithm that would automatically calculate the appropriate time at which to start heating.

I keep searching online and most results are for industrial uses and/or for heating systems that can be modulated such as electrical heaters. The heating system in my house consists of a boiler that heats the water in the floor tubing and I cannot modulate the output, I can only tell it to start or to stop via a mechanical relay that opens or closes a solenoid valve. This, I believe, renders a PID algorithm inappropriate. Fuzzy logic and just PI control may be suitable but can they be made to work with varying set points?

Supervised machine learning is overkill for my needs and I don't want to spend weeks to train it.

What other options would I have?

# Answer
> 0 votes
I too am working on something similar for a new house I'm building. In my system the boiler is controlled by an Opentherm interface I'm designing. This interface connects to fhem via software I'll also write. I chose fhem because it supports a wide range of kit, although perl probably wouldn't be my first choice of language. My radiators will have MAX eq-3 thermostat heads (as they were best bang-per-buck). Again fhem supports these and they can be talked to by low power radio cube which hangs off ethernet.

My radiator heads measure the room temperature and adjust the valve accordingly. They report back when they change so my idea is to use that to estimate the house demand and then use that to control the boiler. For example, say my lounge radiator is saying it is at 50% and I know it is a 1kW radiator, then I have 500W of demand. Say my boiler is 5kW then I need to set the duty cycle of that to 10%. Problems I see are that the valve is unlikely to linear so I'll need to derive some look up table to make it nearer linear. Radiator output will also depend on water temperature but I'll know that from Opentherm so I can adjust for that as I have a formula for that.

But coming back to OP's question I believe that smart thermostats learn how fast the temperature rises in a house. So if the house heats up at 2C/hr and you have set 20C at 8am then if house is 18C the heating will start at 6am. It might also be that the heating is backed off a bit during the warm up phase if it looks to be warming up faster than expected (which would be D of PID). And perhaps this degC/hr figure is always being adjusted so that it changes from autumn to winter to spring.

I think, from reading the CM67 datasheet, that smart stats have a proportional zone (1.5C typical on CM67). Outside of that heating is either all on or all off. Inside the range the duty cycle is controlled, 3-12 cycles per hour. That would P of PID. There might be I too. All of that just controls the duty cycle, for gas, every 10 minutes you get a burn of x minutes.

BTW Typically houses have a long time constant due to all the brick and concrete in them. That's why heating 16/24 is ~95% of the loss of heating 24/24. You can estimate that figure by knowing inside and outside temperatures. I did a thought experiment on this which I blogged here. Interestingly the better the house is insulated the less difference there is to heating 24/24. A controversial statement I know but maths don't lie.

Given you are heating the floor, a large mass, I would expect you'll have quite a time constant. I think you'll need to learn (somehow) what that is and use that to predict temperature rise if you are not to overshoot.

# Answer
> 1 votes
Maybe approach it from a "BTU's needed over time" standpoint. I don't know the exact maths off the top of my head, but consider:

* What is the temperature differential?
* What is the heating capacity (BTU's) of the radiant flooring system?
* How long does it take to start rendering 68% of that heat to the room?
* What is the heating load of the room in BTU's?
* How efficient is the heat generated?

Then do some math on these numbers. Something like...

$t\_{hours}=\dfrac{(T\_{end}-T\_{start})\cdot H\_{demand}}{H\_{supply}}\cdot \mathrm{eff}^{-1} + t\_{delay}$

So for an end temperature of 22°C and a start of 18°C, heat of 50kBTU, demand of 20kBTU, 90% efficiency, and 15 minutee delay:

$\begin{align\*}t\_{hours} &= \dfrac{(22°C-18°C)\cdot 20k\_{demand}}{50k\_{heat}}\cdot 0.90\_{\mathrm{eff}}^{-1} + 0.25h\_{delay}\\ &= \dfrac{80\mathrm{k}}{50\mathrm{k}}\cdot 1.\bar{1}+ 0.25\mathrm{h}\\ &= 2.02\bar{7}\mathrm{h} \end{align\*} $

Some analysis and experimentation will be needed to arrive at realistic values but hopefully this is a start.

# Answer
> 0 votes
I'm working on something similar. I have wall heating through the whole house and I am building an openTherm that can also measure outside temperature. the inside temperature will be provided by my home automation system.

OpenTherm can be used to set the temperature of the water coming from the heater. Through some experimentation I found that (for example) when the outside temperature is 3 degrees Celsius and I want 18 degrees Celsius inside I need to set the water temperature to 40 degrees Celcius (for my particular heating system layout)

I plan to take extend that idea to the following approach:

Create a lookup table with the difference between inside and outside temperature as key and the following values: \- required temperature of water from boiler \- time it takes to heat up by one degree when the boiler water temperature to the temperature for the next higher entry. For example how long does it take to increase the temperatur from 18 to 19 degrees when I increase the water temperature from 40 to 41.3 \- time it takes cool off by one degree when the heat is turned of

This allows me to calculate how long it (should) take for temperature increase to take effect, given how much I increase the heating water temperature. Or inversely I could calculate the heating water temperature required to achieve the desired increase in a given amount of time.

I will populate the table with some ibnitial reasonable values and than use my home automation system to measure the actual system response and use that to fine tune the table.

Required capacity and speed will also depend on: \- the amount ventilation (in my case this is also variable) \- which spaces are being heated (in my case spaces are only heated when in use, and or depending on an individual program)

Hope this gives you some ideas

# Answer
> 0 votes
I believe NEST and other thermostats use a Kalman filter / PID algorithm or a modification there of.

---
Tags: algorithms
---


title: Worst run-time for 3 nested loop

text:
# Question
Title: Worst run-time for 3 nested loop
Suppose we need to find a tight asymptotic bound on the worst case run time of the following program

```
t = 0;
for i = 0 to n-1 do
  for j = i+1 to n-1 do
    for k = j+1 to n-1 do
      t++;

```

I can't for the life of me figure out what the run-time would be. I have a feeling it would have n! in there somewhere, but I can't seem to wrap my head around it. All help is appreciated

# Answer
I suggest you slightly modify your program, as follows:

```
int i, j, k, t = 0;
for (i = 0; i <= n - 1; i++)
  for (j = i + 1; j <= n - 1; j++)
    for (k = j + 1; k <= n - 1; k++)
      t++;

```

Now run this program for various values of $n$ and print the corresponding values of $t$, which is your runtime $T(n)$. Make a guess at the growth rate of $T(n)$ based on this. Try to prove your guess.

Another idea is to try to understand what happens when you have only one loop, then two nested loops, and then all three nested loops. The first case in particular is pretty easy.
> 2 votes

# Answer
Others have explained how to get the correct answer so I'll explain why your guess of $n!$ is wrong and how you could have worked that out for yourself. I'm not trying to kick you while you're down, just to help you check your intuitions and working in the future, so you can quickly reject wrong answers and home in on something closer to the truth.

First, think about what $n!$ "means". $n!$ is the number of ways of arranging the numbers $1, \dots, n$ in a line. So, if the code fragment is going to take $n!$ steps to run, it has to do something involving as much work as considering all possible permutations of $1, \dots, n$ so, in particular, it must be "thinking about" $n$ different numbers at once. But it doesn't do that – at any one time, it's only keeping track of the three variables `i`, `j` and `k`. It doesn't seem to be doing nearly enough work to get up to $n!$.

Second, consider a simpler version of the program that you can analyze. For example,

```
t = 0;
for i = 0 to n-1 do
    for j = 0 to n-1 do
        for k = 0 to n-1 do
            t++;

```

This program definitely does more work than the real program because, here, we consider all possible values for `j` and `k`, whereas the real program only considers the values where `i < j < k`. So, however long the real program takes, it takes less than the simplified version, and the simplified version obviously takes $n^3$ steps.

So now you can think a bit harder about the real program, knowing that if you get an answer that's worse than $n^3$, you must have gone wrong somewhere. Perhaps the next step would be to consider the program

```
t = 0;
for i = 0 to n-1 do
    for j = i+1 to n-1 do
        for k = 0 to n-1 do
            t++;

```

which does the `j` loop properly but still simplifies the `k` loop. If you can figure out how many steps that program takes, you should then be able to move on to the full version.
> 1 votes

# Answer
Since the time is obviously less than $n^3$, make a guess that it is a third degree polynomial $an^3 + bn^2 + cn + d$. Put in the numbers for n = 0, 1, 2 and 3. You get four equations with four variables. Solve it.
> 1 votes

# Answer
(n-1)(n)(n+1)/6 This is the formula

n(n+1)(n+2)...(n+r-1)/r!

where r is the number of nested loops.
> -1 votes

---
Tags: asymptotics, runtime-analysis, lower-bounds
---


# Question
Title: Why exactly is Zero Knowledge Proof used here?
"The Ali Baba cave" example of ZKP is pictured below. There is no need for a probabilistic ZKP protocol to prove to the verifier of the statement (that the prover has the key to the door). It can be proved deterministically without the prover revealing any knowledge/information.

Assume that both the verifier and prover are both initially positioned at one side of the door. The verifier first walks back to the entrance. The prover opens the door and walks to the entrance to meet the verifier using the opposite route that the verifier took. Hence the prover proves to the verifier deterministically, without the need for repeated experiments.

# Answer
Yes, in cave example, it is possible to prove with a deterministic protocol. Why do people use a probabilistic proof in the cave example? Because that follows more closely to how most computational zero knowledge proofs work. Most computational zero knowledge proofs are probabilistic, and this is intended to be an analogy that helps you understand computational zero knowledge proofs. For computational zero knowledge proofs, it's usually not so easy to make a deterministic proof; often it's easier to find a probabilistic proof. The cave example is only an example intended to help give you some intuition that will be helpful to you when you study computational zero knowledge proofs, so don't worry too much about the details.
> 1 votes

# Answer
The example proves something stronger. Alice proves to Bob that she knows the secret word, but she actually *only* proves it to Bob. This is the reason, as in your illustration, Bob is initially waiting outside the cave.

Suppose that Bob was equipped with a camera and that Bob followed her to the entrance. Then he would have proof (on camera) that she knows the secret word.

But in the situation you have, even if Bob records the entire process, no-one would be convinced that Alice knows the secret word; Alice and Bob could have agreed on the order beforehand.

(Of course, he could still prove it for the world if he recorded the coin flips, what do I know ...)
> 1 votes

---
Tags: complexity-theory, zero-knowledge-proofs
---


# Question
Title: Can we solve a "very" exponential recurrence?
Can we solve this recurrence relation : $T\_n = \exp(T\_{n-1})$ ?

Thanks!

# Answer
It depends what you mean by "solve". This is tetration, and it has a number of "closed" forms. For example:

$$\begin{eqnarray\*}T\_0 & = & 1 \\ T\_{n+1} & = & 2^{T\_n}\end{eqnarray\*}$$

If $n \ge 3$, then:

$$\begin{eqnarray\*}T\_n & = & A(4, n-3) + 3\end{eqnarray\*}$$

Where $A()$ is Ackermann's function.

Or using the Hyperoperation sequence:

$$\begin{eqnarray\*}T\_n & = & H\_4(2,n)\end{eqnarray\*}$$

Or in Knuth's arrow notation:

$$\begin{eqnarray\*}T\_n & = & 2 \uparrow \uparrow n\end{eqnarray\*}$$
> 13 votes

---
Tags: complexity-theory, recurrence-relation, discrete-mathematics, theory
---


# Question
Title: A Turing machine with each cell accessed at most $10$ times has an equivalent NFA
I am confused by the following claim:

> Let $T$ be a (decider, single-tape) Turing machine with the property that for every input, every cell on its tape is accessed at most $10$ times. Then there is a (nondeterministic) finite automaton equivalent to $T$.

The assumption says that there are only finitely many possible crossing sequences, i.e. the sequence of internal states that the machine has at a given cell on a given input. The text says the proof is "just have enough states to remember the current crossing sequence and update that information as each successive input symbol is read."

I do not understand this construction at all. For example, to remember the crossing sequence at a given cell we need to keep track of the contents of the entire tape, and does the nondeterminism come in somehow when deciding on which cell to "track"?

The text is part of Sipser's solution manual, problem 7.20 or 7.49 depending on the edition. One idea I played with is to have a state of the NFA for every crossing sequence and move non-deterministically from it to every possible next sequence.

# Answer
I describe an NFA construction method for a non-deterministic Turing machine. Let's fix an input and fix a run of the Turing machine. Let $M$ be the maximum tape cell index visited by the run. For $1 \le i \le M$, let $1 \le k\_i \le K$ be the number of times tape cell $i$ is visited, where $K$ is the maximum visit count.

The head movement of the Turing machine can be represented by a Hamiltonian path of the directed graph $G = (V, E)$, $V = \\{ (i, j) \mid 1 \le i \le M, 1 \le j \le k\_i \\}$, $E = \\{ ((i, j\_1), (i+1, j\_2)), ((i+1, j\_2), (i, j\_1)) \mid 1 \le i \lt M, 1 \le j\_1 \le k\_i, 1 \le j\_2 \le k\_2, j\_1 \le j\_2 \\}$. The condition $j\_1 \le j\_2$ is to ensure the vertices ordering within a cell matches the order of visits.

The NFA will generate a Hamiltonian path, using only local states. The important thing is that the (undirected version of) graph $G$ has a small (~ $K$) path-width.

Below, the "previous cell" always means the tape cell $i-1$ when the current cell $i$ is processing.

The NFA guesses a visit count $k\_i$ and the state of the Turing machine before each visit. Then, NFA guesses a transition (a state, move direction, and cell symbol) after each visit of the current cell. For each visit, the NFA checks the transition is valid for the state and the current symbol on the cell (computed from the transition after the previous visit of the current cell). The NFA remembers the states and the transitions for the next cell.

Then, the NFA guesses a subset of edges between the current and the next cell. The NFA remembered these edges for the next cell. The state after and before the visit of the source and target vertices of an edge must match.

For each vertex of the current cell, compute the in-degree and the out-degree using the previous and current edge subsets. Both degrees must be $1$ except the start and the end vertex. The start vertex is always the first visit of the first cell. The end vertex can be anywhere with a halt transition, but a flag is remembered to ensure there is only one end vertex.

To be a Hamiltonian path, (undirected version of) generated subgraph must be connected. For the connectivity check, a partition of the vertices of the current cell is maintained. The partition represents the connected components of the partially generated graph. All previous vertices must be connected to a current vertex. This is the same technique often used for dynamic programming on a path/tree decomposition.

The NFA reads an input symbol for the first cells. After the input ends (guessed), the NFA starts an epsilon-transition-loop for a non-deterministic number of times. In the loop, the NFA emulates an empty symbol input.

The NFA accepts the input if the "end vertex seen" flag is on, the transitions of the current cell don't contain any right moves, and all the current vertices must be connected by the partition.

The state of the NFA mainly consists of Turing machine states after visits of the previous cell, an edge subset between the previous and current cell, and a connectivity partition of the current vertices. A rough estimate of the state size is $O((2 |Q| K^2)^K)$.
> 0 votes

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


# Question
Title: Clarification about RNN encoder-decoder equation
In the paper by Cho et.al., section 2.3 details the equations for the modified LSTM cell in RNN used in the paper's implementation. The equation in question is :

Here, the output of the reset gate (**r**) is element wise multiplied with the previous hidden state **h**\<*t*-1\>, and then matrix multiplied with the **U** matrix.

Later on, in the Appendix section **A.1.1** explains the equations for the decoder, specifically:

My question: Is the *r 'j* element-wise multiplied to the corresponding expression or not?

# Answer
> 2 votes
$\mathbf{r}$ is a vector; $r'\_j$ is a scalar; so this is multiplying a scalar ($r'\_j$) by a vector (the part in $\[...\]$). There is only one way to multiply a scalar by a vector: you multiply each coordinate of the vector by the scalar.

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


# Question
Title: Machine learning and test split for time series data
I have used different machine learning algorithms to predict solar panels' power output. There are ten independent features for weather data. In all models, I set time as an index and have used the following rule for splitting the data :

```
X_train, X_test, y_train, y_test = train_test_split(x, y, test_size=0.18, random_state=42)

```

With the mentioned splitting rule, all models perform well on the testing set, but I get the worst accuracy when not using a random rule for the testing set.

Does it make sense to use a random rule for splitting the dataset into training and testing sets? Or do I have to use only the latest data (20%) for the test split?

# Answer
In most contexts, random shuffling is absolutely required. If you do not randomly split the dataset, you might get misleading results. For instance, imagine that we have a dataset of patients, and we train a classifier on the first 60% and test it on the last 40% of patients. Well, if the patients happen to be ordered in the dataset in a particular order -- say, youngest to oldest -- then you might end up with a classifier that works well on young folks and poorly on old folks, and thus that achieves very poor accuracy on the test set (which is all old folks) even though it is better than that in practice.

In your situation, the obvious approach is to randomly shuffle. This assumes that there is no change over time in the underlying data distribution, and is appropriate if so. If that assumption is not correct (e.g., partway through the dataset you replaced the solar panels with new ones), then you'll need to do something more complex.
> 2 votes

---
Tags: machine-learning, python, data-mining
---


# Question
Title: Bellman ford shortest paths with at least k edges
I was able to understand the problem of at most k edges and exactly k edges but I am not able to wrap my head around how do I solve the problem of getting shortest paths with at least k edges. You can traverse same edge twice until you reach the minimum required number of edges. An example of implementation is going from one place to another but in between you want to get frequent flyer status and for that you must travel at least k places

Below are few web pages I followed

https://leetcode.com/problems/cheapest-flights-within-k-stops/discuss/686939/Python-by-DP-with-Bellman-Ford-algorithm-w-Comment https://courses.cs.washington.edu/courses/cse421/06au/slides/Lecture21/Summary21.html http://web.stanford.edu/class/archive/cs/cs161/cs161.1176/Slides/Lecture12-lowquality.pdf

# Answer
> 1 votes
Use a product construction: make $k$ copies of the graph, where each edge goes from the $i$th copy to the $i+1$th copy (and also edges from the $k$th copy to itself), then compute shortest paths in this graph. I'll let you fill in the details.

---
Tags: dynamic-programming
---


# Question
Title: Can we simply consider a pseudo random number generator to be a function $f: \Bbb{Z}_n \to \Bbb{Z}_n$ for ever-increasing $n$?
On modern architectures, random number generators get seeded by the current system time as a source of randomness, which is nice because it is kind of unpredictable when a process will switch to the current process. When this timer is in milliseconds or nanoseconds for example, you will get a good random number seed. But the time datatype is usually a 64-bit integer, so in problems concerning randomized algorithms algorithms, can we assume that the RNG they use is simply a map $f: \Bbb{Z}/{2^{64}}\to \Bbb{Z}/{2^{64}}$? Or must we always assume that it's $f: \Bbb{N} \to \Bbb{Z}/2^n$ where $n$ is the word size, could be ${64}$?

I think the first version lends itself to better analytical methods because there is then really only a finite number of possible RNG's at ("inductive stage") $n$, where inductive stage simply refers to the obvious method of induction you could then employ on $n$ in proofs concerning randomized algorithms. For example, it is still an open problem whether or not any randomized polynomial-time algorithm can be derandomized into a deterministic polynomial-time algorithm.

# Answer
> 1 votes
There is no single answer to this. It all depends on the PRNG.

The most common case is that the seed is of fixed length, i.e., it is in $\\{0,1\\}^c$ for some constant $c$ (e.g., $c=64$). You can think of this as $\mathbb{Z}/2^c\mathbb{Z}$ instead of $\\{0,1\\}^c$ if you prefer; they are isomorphic.

It is implementation-dependent how a PRNG is seeded. Don't assume it is necessarily the time of day. For instance, it might be seeded with rdrand, /dev/urandom, or any number of other possibilities.

I am commenting above about PRNGs in practice. If you are more interested in theory, PRNGs can be formalized precisely in several ways. If you are interested in theoretical foundations and asymptotics, I recommend learning about cryptographic pseudorandom generators, which have a precise formalization.

---
Tags: randomized-algorithms, polynomial-time, randomness, random-number-generator, open-problem
---


# Question
Title: What is the asymptotic bound for $T(n)= 3T(\sqrt[3]{n})+n^3$?
What is the asymptotic bound? How do you get to the result?

$$T(n)= 3 \cdot T(\sqrt\[3\]{n})+n^3$$

# Answer
> 2 votes
The lower bound of $$T(n)\mathcal={\Omega}(n^3).$$ Because of $T(n)$ have a term $n^3.$

To find the upper bound we can use induction: $$T(n)\leq cn^3$$ $$=3cn+n^3\leq cn^3$$ As $n\to \infty$ , and for all $c\geq 3$ $$=3cn+n^3\leq cn^3.\hspace{10pt}\square$$ So $$T(n)=\theta(n^3).$$

# Answer
> 1 votes
Use a change of variable: $n = a^k$, $T(a^k) = t(k)$ gives:

$$t(k) = 3 t(k/3) + a^{3 k}$$

Apply the Master Theorem to this.

# Answer
> 0 votes
As

$$ T\left(3^{\log\_3n}\right)=3T\left(3^{\log\_3 \sqrt\[3\]{n}}\right)+n^3 $$

making $\mathcal{T}\left(\cdot\right)= T\left(3^{(\cdot)}\right)$ and $z= \log\_3 n$ we follow with

$$ \mathcal{T}\left(z\right)= 3\mathcal{T}\left(\frac z3\right)+3^{3z} $$

now with an analog procedure, making $\mathbb{T}\left(\cdot\right)=\mathcal{T}\left(3^{(\cdot)}\right) $ and $\mu = \log\_3 z$ we follow with the recurrence

$$ \mathbb{T}\left(\mu\right)=3\mathbb{T}\left(\mu-1\right)+3^{3\cdot 3^{\mu}} $$

now this recurrence has as solution

$$ \mathbb{T}\left(\mu\right)=\frac 13\log\_3 \mu\left(c\_0+\sum\_{k=0}^{u-1}3^{3^{k+2}-k}\right) $$

and now going backwards with $\mu=\log\_3 z$ and $z = \log\_3 n$ we arrive at

$$ T(n) = \frac 13\log\_3 n\left(c\_0+\sum\_{k=0}^{\log\_3(\log\_3 n)-1}3^{3^{k+2}-k}\right) $$

now considering $k = \log\_3(\log\_3 n)-1$ we have for sure

$$ T(n) \ge n^3 $$

---
Tags: asymptotics, recurrence-relation, master-theorem, mathematical-analysis
---


# Question
Title: Circuit size of a random two to one function
Consider the set of all possible two-to-one functions that map inputs from $\\{0, 1\\}^{n}$ (domain) to outputs in $\\{0, 1\\}^{m}$ (co-domain) and let $m \> n$.

If I pick a function randomly from this set, what is the probability that it can be computed by a Boolean circuit of size $\text{poly}(m)$?

Note that while the co-domain of the set of functions so defined is $\\{0, 1\\}^{m}$. However, the range of each individual function is a set of size $2^{n-1}$. What that set looks like depends on what function we randomly pick.

---

I was thinking of using a counting argument here. Let $M = 2^{m}$ and $N = 2^{n}$. Then, the number of two-to-one functions is given by $$\frac{N!}{2^{N/2}}\times {M \choose N}.$$The number of circuits (made of AND, OR, and NOT gates) of size $k$ is at most $$2^{k^{2}} \times 3^{k}.$$

In general, in the asymptotic limit, the second expression is larger than the first expression -- which would indicate that, perhaps, all two-to-one functions can have polynomial sized circuit description.

However, not every circuit computes a two-to-one function. So, this does not tell me what fraction of two-to-one functions has polynomial sized circuits.

# Answer
Every function $f\colon \\{0,1\\}^n \to \\{0,1\\}^m$ can be computed by a bounded fan-in circuit of size $O(2^n m)$, which is polynomial in $m$ iff $m$ is exponential in $n$:

* First, for every $k \leq n$ and for every $y \in \\{0,1\\}^k$, we compute a gate $g(y)$ which expresses $x\_1 = y\_1 \land \cdots \land x\_k = y\_k$. This can be done recursively.
* Then, we compute the outputs using the formula $$ f\_i(x) = \bigvee\_{f\_i(y) = 1} g(y). $$

This can likely be improved to $O(\frac{2^n}{n} m)$ using standard tricks.

On the lower bound side, I claim that the first bit $f\_1$ of a random two-to-one function is already quite complex, requiring bounded fan-in circuits of size $\Omega(2^n/n)$. We can choose $f$ by first choosing its image (a choice of $2^{n-1}$ strings out of $2^m$), listing the image repeated twice, and then permuting the list at random. It is likely the the initial choice results in a balanced first bit (roughly half the strings start with $0$, and roughly half start with $1$). After permuting the list, we can choose a random function $f\colon \\{0,1\\}^n \to \\{0,1\\}$ with specified bias (i.e., $\Pr\[f=1\]$), where the bias is itself a random variable concentrated around $1/2$. This should imply the claimed lower bound using the standard counting argument; for example, if the bias is exactly $1/2$, then instead of the usual $2^{2^n}$ functions we have $\Theta(2^{2^n}/2^{n/2})$ out of which we choose one at random, which is not a big difference from this perspective.
> 3 votes

---
Tags: complexity-theory, polynomial-time, circuits
---


# Question
Title: Find all n bit numbers with k ones and unique under circular shift
I am trying to traverse through all uint64\_t with k 1s. Then I find that if x and y are circular shifts of each other, they will output the same result. So I'm trying to optimize my code.

The problem is I don't know how to exactly traverse through the set of numbers that has exactly k 1s, and also unique under circular shift.

I have some pretty close attempts that traverse **almost** without any redundancy. It involves cutting it into sequences of 1 and 0, recording their length, and ensuring the "largest substring of length" is at the lower digit. But it is not perfect.

Is there any elegant way to achieve this?

# Answer
> 7 votes
Binary strings considered up to rotation are known as *necklaces*. You are interested in enumerating binary necklaces with given density. You can find one solution in Wang and Savage, A Gray Code for Necklaces of Fixed Density.

---
Tags: algorithms, combinatorics, strings
---


# Question
Title: Find a maximum matching in linear time - How to prove it?
Let B be an undirected tree with |V| nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime O(|V|).

I understand that the solution is:
Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.

Like that described here: How to find maximum matching edges in undirected tree

But I did not understand how this can be proved by induction on the height of the tree. Can you help with this?

# Answer
> 2 votes
You don't have to prove it using induction, although you can. You can prove the following for general graphs.

Observation 1. If a vertex has degree 1, there is a maximum matching containing that vertex.

Proof. By an exchange argument, let M be maximum, not containing the vertex. Why? Because it's neighbor is matched to a different vertex. Create a new maximum matching containing the degree 1 vertex instead.

Observation 2. If an edge is chosen to be in the matching, we can delete the endpoints of the edge and continue with the smaller graph instance.

Proof. You can probably take it.

Observation 3. If a vertex has degree 0, you can delete it from the graph and continue with the smaller graph instance.

Now the correctness of the algorithm is immediate on forests, since any forest with an edge has a vertex with degree 1.

---
Tags: algorithms, graphs, matching
---


# Question
Title: Number of unique people who don't own trucks, but own cars
So, we have the tables:

```
Person (SIN, Name, Address, Owner_id)
Owner (Owner_id)
Vehicle (Vehicle_id, Plate_number)
Car (Vehicle_id, Cmodel, Cyear)
Truck (Vehicle_id, Tmodel, Tyear)
Owns (Owner_id, Vehicle_id)

```

How do I format a relational algebra statement so that I get the number of people who only own cars (not trucks)? We can assume that a Person might own more than one car, and we only want them to count for one person.

I don't even really know where to start with this question. I've been looking at it for a while and I'm very new to relational algebra, and having to potentially use all of these tables confuses me. Where do I start, and how do I extract the information to compare vehicle ownership?

# Answer
Get distinct car owners and do the set difference with truck owners.

Use the table `Owns` as an intermediary to join the table `Person` and any of the tables `Car` or `Truck`.
> 0 votes

---
Tags: relational-algebra
---


# Question
Title: In IPv4, why is the number of host addresses available per network given by $2^\textrm{host bits} - 2$? This is in the context of classes
For some reason—at least when classes are involved (which I don't know the reason for yet)—in IPv4 the number of host addresses available per network is given by $2^\textrm{host bits} - 2$. Why don't we have $2^\textrm{host bits}$ host addresses available?

# Answer
The addresses x.x.x.255 are reserved: they are the "broadcast address" (for /8 networks, i.e., where the "host bits" = 8).

The addresses x.x.x.0 are actually fine. However, they used to be reserved, so older sources might consider them unavailable. See https://stackoverflow.com/q/14915188/781723 and https://serverfault.com/q/135267/111679 and https://serverfault.com/q/10985/111679.

Thus, older sources might list it as "minus two"; a more modern view is that it is "minus one".
> 2 votes

---
Tags: computer-networks
---


# Question
Title: How to detect if a CFG can cause the parser ends up looping forever?
For example, the following grammar will never stop deriving a complete sentence:

```
S -> A b
A -> a A

```

Some other CFGs can derive a complete sentence, but it still is possible to wind up in a infinite loop, e.g.

```
S -> A b | b
A -> a A

```

Currently I am writing a LR parser generator. If it doesn't check if the input CFG is invalid like that, the generated parser will just trapped in a loop forever. I tested *Bison* and it can successfully detect such invalid grammar, how does it do it?

# Answer
> 1 votes
There seem to be some faulty premises here. Those CFGs are not invalid. Grammars themselves don't have a notion of "infinite loop" or "never stop deriving". They either derive a sentence or don't, it's yes or no. In other words, the sentence is either in the language generated by that CFG or it isn't, yes or no. Anything about infinite loops is about a particular parser. There are many ways to parse the same grammar. A correct parsing algorithm will not enter an infinite loop.

Perhaps you are asking whether a given grammar has any derivation of the form $A \stackrel{\*}{\Rightarrow} \cdots A \cdots$, i.e., $A$ derives some string that includes $A$. I'm guessing this is what you mean when you talk about "infinite loops". It is possible to test this by building an appropriate directed graph and testing whether the resulting graph has any cycles (e.g., by checking whether it can be topologically sorted). In particular, the graph has a vertex for each non-terminal and an edge $A \to B$ whenever the grammar has a production $A \to \cdots B \cdots$, i.e., a production rule where the left-hand side is $A$ and $B$ appears in the right-hand-side.

# Answer
> 1 votes
You shouldn't need to reduce a grammar in order to apply an LR parsing algorithm. Provided that the grammar is LR parsable (i.e. it has no parsing conflicts), the generated parser should execute without falling into an endless loop.

What bison does is to remove non-productive and non-reachable rules. Although not necessary, it's useful, in part because such rules are almost certainly an indication of a bug in the grammar specification, and in part because it reduces the size of the grammar.

The algorithm uses a workqueue which contains tuples consisting of a production and a point, rather similar to the LR(0) items in the LR algorithm. It also maintains a registry of *reachable* non-terminals. The output is a new reduced grammar whose non-terminal set and production sets are subsets of the original sets. We assume that there is an O(1) mechanism to determine if a non-terminal appears in the non-terminal set of the new grammar.

The algorithm can be implemented in time and space linear to the size of the grammar.

Initially, the Start symbol is marked as reachable and all of its productions are placed into the workqueue with their points at the beginning. The workqueue is then processed in order; for each item in the queue:

* if the point immediately precedes a sequence consisting of one or more terminals or non-terminals in the reduced grammar, the point is moved over that sequence.
* if the point is now at the end of the production, the production is added to reduced grammar and removed from the workqueue.
* if the point now precedes a non-terminal which was not previously marked as reachable, that non-terminal is marked as reachable and all of its rules are added to the end of the workqueue.

Once the workqueue has been fully scanned, if it still contains productions, it is scanned again, until a complete scan completes without adding any new productions to the reduced grammar. (Subsequent scans only need to consider items whose points immediately precede a non-terminal newly added to the reduced grammar. That optimisation is needed to ensure that the algorithm runs in linear time, although in practice the extra bookkeeping is not really worthwhile.)

There is a remarkable similarity of the above algorithm with the algorithm to identify nullable non-terminals. The only difference is the handling of terminal symbols. When the scan encounters an item whose point immediately precedes a terminal symbol, it removes the production from the workqueue instead of moving the point over the terminal symbol. Thus, the same function can be used for both analyses, with an additional parameter indicating the handling of terminals.

---
Tags: algorithms, parsers
---


# Question
Title: $T(n/2 +1)$ substitution in recurrence relation
How to find the recurrence relation using domain range substitution method for the below: $$ T(n) = 2T\left(\frac{n}{2} +1\right) + n -2 $$

I am unable to get a pattern with this relation as it is really confusing. I am guessing the below for $T(n/2 + 1)$: $$ T\left(\frac{n}{2} +1\right) = 2T\left(\frac{n+2}{4}+1\right)+ \frac{n+2}{2} - 2 $$

When I substitute this for $T(n)$ it becomes a mess.

Can someone guide me in this please.

# Answer
> 1 votes
Perhaps you can spot the pattern here: \begin{align} T(n) &= 2T\left(\frac{n+2}{2}\right) + n-2 \\ &= 4T\left(\frac{n+6}{4}\right) + 2n-4 \\ &= 8T\left(\frac{n+14}{8}\right) + 3n-6 \\ &= 16T\left(\frac{n+30}{16}\right) + 4n-8 \end{align} More generally, we have $$ T(n) = 2^k T\left(\frac{n-2}{2^k} + 2\right) + k(n-2). $$ This implies that $$ T(2^k+2) = 2^k T(3) + k2^k. $$

# Answer
> 0 votes
Hint.

Making $S(n) = T(n+a)$ we have

$$ S(n) = 2T\left(\frac{n+a}{2}+1\right)+n+a-2 $$

but

$$ T\left(\frac{n+a}{2}+1\right) = S\left(\frac{n+a}{2}+1-a\right) = S\left(\frac n2-\frac a2+1\right) $$

now choosing $a=2$ we follow with

$$ S(n)=2S\left(\frac n2\right)+n $$

etc.

---
Tags: recurrence-relation
---


# Question
Title: Knapsack Problem with exact required item number constraint
How would we solve the knapsack problem if we now have to fix the number of items in the knapsack by a constant $L$? This is the same problem (max weight of $W$, every item have a value $v$ and weight $w$), but you must add *exactly* $L$ item(s) to the knapsack (and obviously need to optimize the total value of the knapsack).

Every way I've thought of implementing this so far (dynamic programming, brute force) has resulted in either failure, or lifetime-of-universe level computation times. Any help or ideas are appreciated.

Edit: I am looking for pseudo-polynomial time solutions

# Answer
> 4 votes
You can transform this problem into an instance of Knapsack. Let $n$ be the number of items, $V$ be the maximum value of an item and suppose that each item weighs at most $W$ (otherwise it can be discarded).

To ensure that you select at least $L$ items:

* Add $n(V+1)$ to the value of every item.
* Now the problem is equivalent to that of maximizing the number of selected items, breaking ties in favor of set of items with largest original total value, subject to weight constraints. There is a solution that selects at least $L$ items iff the optimal solution has a value of at least $n(V+1)L$.

To ensure that you select at most $L$ items:

* Add $(W+1)$ to the weight of every item.
* Add $L(W+1)$ to $W$.
* Now every subset of more than $L$ items weighs at least $(L+1)(W+1) = L(W+1) + (W+1) \> L(W+1) + W$, and is hence not feasible. Every subset of $L$ items that had an overall weight of $w$, now weighs $L(W+1) + w$, and hence is feasible iff $w \le W$. A subset with less than $L$ items might be feasible even if its overall weight is more than $W$, however its total value will always be smaller than $n(V+1)L$.

# Answer
> 2 votes
Define a matrix $M$ of size $n \times W \times L$. The entry $M\[i\]\[j\]\[k\]$ denotes the maximum value of the knapsack when exactly $k$ items are chosen from $\\{1,\dotsc,i\\}$ and the allowed capacity of the knapsack is $j$.

**Final Solution:** The value of $M\[n\]\[W\]\[L\]$ (assuming 1 based indexing).

**Induction or DP:** $M\[i\]\[j\]\[k\]$ can be stated in terms of smaller subproblem as follows: $M\[i\]\[j\]\[k\] = \max\\,\\{\\,M\[i-1\]\[j-w\_i\]\[k-1\] + v\_i, \\, M\[i-1\]\[j\]\[k\]\\}$.

The first term denotes the scenario when the $i^{th}$ item is chosen in the knapsack, and the second term states the scenario when the $i^{th}$ item is not chosen in the knapsack.

**Base Case:**

1. For any entry with $k \> i$, $M\[i\]\[j\]\[k\] = -\infty$ since there are only $i$ available items and the desired quantity is $k$.
2. For every $j \in \\{1,\dotsc,W\\}$, $i \in \\{1,\dotsc,n\\}$, and $k = i$, the value $M\[i\]\[j\]\[i\] = \sum\_{p = 1}^{i} v\_p$ if $\sum\_{p = 1}^i w\_p \leq j$ else $M\[p\]\[j\]\[p\] = -\infty$. In other words, if there are only $i$ available items and the required quantity is also $i$, then pick all the items in the knapsack if and only if the items satisfy the capacity constraint, i.e., sum of weights of the items is at most $j$.

**Running Time:** $O(W\cdot L \cdot n)$

---
Tags: algorithms, optimization, knapsack-problems, pseudo-polynomial
---


# Question
Title: Free variables as defined in TAPL seems wrong
In "Types and Programming Languages" by Benjamin C. Pierce (WorldCat)

> 5.3.2 Definition: The set of *free variables* of a term **t**, written ***FV(t)***, is defined as follows:
>
> FV(x) = {x}
> FV(λx.t₁) = FV(t₁) \ {x}
> FV(t₁ t₂) = FV(t₁) ∪ FV(t₂)

\ is relative complement

---

Based on above definition of *free variables* my understanding is

For

`λx.x` x is not free

For

`(x y)` x is free and y is free

For

`(x λx.x)` the first x is free and the second x is not free.

So x is both free and not free in `(x λx.x)`.

Since x is both free and not free it seems the definition of **free variables** is wrong.

How should the definition be interpreted for `(x λx.x)`?

---

**Side notes**

These are here in case others are seeking specifics of why I ask this question but I think the question above is self contained.

---

***FV(t)*** is used for substitution in 5.3.5 and so has a more specific context, I.e.

> x ↦ s = λy.\[x ↦ s\]t₁ if y ≠ x and y ≠ ***FV(s)***

---

My implementation is in Prolog and the terms are converted to an AST before being passed to fv/2.

AST

```
app(abs(var(x),var(x)),var(x))

```

Prolog code

```
fv(var(V),[V]) :- !.
fv(abs(var(Binder),T),FV) :-
    fv(T,FV0),
    ord_subtract(FV0,[Binder],FV), !.
fv(app(T1,T2),FV) :-
    fv(T1,FV1),
    fv(T2,FV2),
    ord_union(FV1,FV2,FV).

```

Example run

```
?- fv(app(abs(var(x),var(x)),var(x)),Vs).
Vs = [x].

```

The result of the code is that `x` is a free variable because `app` is done last and the second `x` is free.

---

In TAPL chapter 6 the book switches to De Bruijn index and so the question becomes pointless for the remainder of the book.

---

AFAIK there is no official implementation of ***FV(t)*** provided for the book. The code for Lambda Calculus from Pierce is here but uses De Bruijn index so no need for ***FV(t)***

---

Nothing in the errata for the definition.

---

**EDIT** (01/30/2022)

"The Calculi of Lambda-Conversion" by Alonzo Church (pdf)

pp. 8-9

> A formula is any finite sequence of primitive symbols. Certain formulas are distinguished as well-formed formulas, and each occurrence of a variable in a well-formed formula is distinguished as free or bound, in accordance with the following rules (1-4), which constitute a definition of these terms by recursion:
>
> 1. A variable **x** is a well-formed formula, and the occurrence of the variable **x** in this formula is free.
> 2. If **F** and **A** are well-formed, (**FA**) is well-formed, and an occurrence of a variable **y** in **F** is free or bound in (**FA**) according as it is free or bound in **F**, and an occurrence of a variable **y** in **A** is free or bound in (**FA**) according as it is free or bound in **A**.
> 3. If **M** is well-formed and contains at least one free occurrence of **x**, then (**λxM**) is well-formed, and an occurrence of a variable **y**, other than **x**, in (**λxM**) is free or bound in (**λxM**) according as it is free or bound in **M**. All occurrences of **x** in (**λxM**) are bound.
> 4. A formula is well-formed, and an occurrence of a variable in it is free, or is bound, only when this follows from 1-3.
>
> The free variables of a formula are the variables which have at least one free occurrence in the formula. The bound variables of a formula are the variables which have at least one bound occurrence in the formula.

p. 14

> A well-formed formula will be said to be in principal normal form if it is in normal form, and no variable is both a bound variable and free variable of it, and the first bound variable occurring in it (in the left-to-right order of the symbols which compose the formula) is the same as the first variable in alphabetical order which is not a free variable of it, and the variables which occur in it immediately following the symbol λ are, when taken in the order in which they occur in the formula, in alphabetical order, without repetitions, and without omissions except of variables which are free variables of the formula.

p. 15

> 7 III. Every well-formed formula has one of the three forms, ***x*** where ***x*** is a variable, or (***FA***), where **F** and **A** are well-formed, or (**λxM**), where **M** is well-formed and **x** is a free variable of **M**.

p. 58

> 17. THE CALCULUS OF λ-K-CONVERSION. The calculus of λ-K-conversion is obtained if a single change is made in the construction of the calculus of λ-conversion which appears in §§ 5,6: namely, in the definition of well-formed formula (§5) deleting the words "and contains at least one free occurrence of x" from the rule 3.

# Answer
> Since x is both free and not free it seems the definition of free variables is wrong.

Why? There is no rule that says that the sets of free and bound variables have to be disjoint. Nothing breaks if they share elements. It is perfectly legitimate for a variable to occur both free and bound as in your example, so naturally it will be part of both sets. The definition is correct, and the only one that makes sense if you don't want to restrict variables to never occur both free and bound.
> 5 votes

# Answer
Although you don't actually need to do this to define free variables, it helps to think about bound and free *occurrences* of a variable in a term. An occurrence of a variable $x$ is bound in a term $t$ if it's under a syntax node that binds $x$, and it's free otherwise. The free variables of a term are the ones that have a free occurrence. It doesn't matter whether they have bound occurrences as well.

For example, in the term $T\_1 = (\lambda \color{blue}{x}. \color{blue}{x})$, both occurrences of $x$ are bound¹. This term has no free occurrences of any variables, so $\mathsf{FV}(T\_1) = \varnothing$.
In $T\_2 = \color{red}{x} (\lambda \color{blue}{x}. \color{blue}{x})$, the first (red) occurrence of $x$ is free and the other two (blue) are bound. Since $x$ has a free occurrence, $\mathsf{FV}(T\_2) = \\{\color{red}{x}\\}$.
In $T\_3 = \color{red}{x} \color{orange}{y} (\lambda \color{blue}{x}. (\lambda \color{magenta}{z}. \color{magenta}{z} \color{blue}{x}) (\lambda \color{cyan}{x}. \color{cyan}{x} \color{cyan}{x} \color{orange}{y}) \color{blue}{x})$, the first (red) occurrence of $x$ is free and both (orange) occurrences of $y$ are free, whereas the other occurrences (blue, cyan) of $x$ are bound (in two different scopes), and all the occurrences (magenta) of $z$ are bound. Since both $x$ and $y$ have free occurrences but $z$ doesn't, $\mathsf{FV}(T\_3) = \\{\color{red}{x}, \color{orange}{y}\\}$.

It is common when discussing languages with variable binding to use the *Barendregt convention*. This convention states that in a given term, you never use the name of a free variable as the name of a bound variable. If you need to build a term from multiple parts that have bound variables, you alpha-convert them to rename those variables to be unique. When you obey this convention, in a given term, a variable never has both bound occurrences and free occurrences. If you take the examples above, they don't obey the Barendregt convention if you consider the letters ($x$, $y$, $z$) to be the variable names. But if you consider the letters and their colors to constitute the variable names, they do obey the Barendregt convention: I assigned each distinct variable a different color (“distinct” meaning that alpha-conversion can map them to different names).

¹ <sub> Depending on how you define “bound”, the occurrence just after the $\lambda$ might be defined as *bound*, or as *binding* but not *bound*. It's more common to consider it not bound when discussing languages where variable binding is simple, such as the lambda calculus, but defining binding occurrences to be bound makes it easier to analyze languages with more complex binding constructions such as pattern matching. </sub>
> 3 votes

---
Tags: lambda-calculus, types-and-programming-languages
---


# Question
Title: Prove that f(T) = Ω(l log l) for any l-leaf binary tree T
I want to prove this: For any binary tree T, let f(T) denote the sum of the depths of all of the leaves of T. (The root is at depth 0, the children of the root are at depth 1, the grandchildren of the root are at depth 2, etc) Prove that f(T) = Ω(l log l) for any l-leaf binary tree T. Any suggestions?

# Answer
> 0 votes
You can show that $f(T) \ge l \log l$ by induction on the height of $T$. If the height of $T$ is $0$ then the claim is true since the only tree of height $0$ consists of a single node and $f(T) = 1 \log 1 = 0$.

If the height of $T$ is at least $1$, then let $r$ be the root of $T$ and call $T\_1$ (resp. $T\_2$) be the subtree of $T$ rooted in the left (resp. right) child of $r$. (Notice that we can assume that both $T\_1$ and $T\_2$ exist, otherwise the claim follows immediately by applying the induction hypothesis on the subtree rooted in the unique child of $r$).

Let $l$, $l\_1$, and $l\_2$ be the number of leaves of $T$, $T\_1$ and $T\_2$, respectively. $$ \begin{align\*} f(T) &= f(T\_1) + f(T\_2) + l \ge l\_1 \log l\_1 + l\_2 \log l\_2 + l = l\_1 (1 + \log l\_1) + l\_2 (1 + \log l\_2). \end{align\*} $$

Defining $\varphi(x) = x(1+ \log x)$, we have $f(T) \ge \varphi(l\_1) + \varphi(l\_2)$ . Since $\varphi(x)$ is a convex function, we can use Jensen's inequality to write: $$ f(T) \ge \varphi(l\_1) + \varphi(l\_2) \ge 2 \cdot \varphi\left(\frac{l\_1 + l\_2}{2}\right) = 2 \cdot \varphi\left( \frac{l}{2} \right) = 2 \cdot \frac{l}{2}\left( 1 + \log \frac{l}{2} \right) = l\log l. $$

---
Tags: binary-trees
---


# Question
Title: Fingerprint functions for set equality checks?
Given I have two sets of objects $A =\\{a, b, c\\}$ and $B = \\{a, b, c, a\\}$

* Based on the set equality, I want the fingerprint of these sets to be the same $F(A) = F(B)$.
* Additionally I want to be able merge fingerprints in order to calculate the fingerprint of the union. $F(\\{a,b\\} \cup \\{c,a\\}) = Merge(F(\\{a,b\\}), F(\\{c,a\\}))$

I think this resembles linear fingerprint functions (such as CRC) as in:

$CRC(x \oplus y \oplus z) = CRC(x) \oplus CRC(y)\oplus CRC(z)$

A similar concept exists in cryptography, called homomorphic hash functions:

$H(\\{a\\}) \oplus H(\\{b\\}) = H(\\{a, b\\})$

However, those can't be used for this purpose, as they won't handle duplications. Can you think of any fingerprint function that the probability of collision could be calculated?

*Note: Intuitively, a reasonable trade-off could be letting the fingerprint grow (ideally sublinearly) as the cardinality grows.*

# Answer
> 1 votes
A Bloom filter has this property. Use the Bloom filter itself as the fingerprint. The merge operation can be implemented as bitwise OR.

---

For multisets, see https://crypto.stackexchange.com/q/54544/351 and https://crypto.stackexchange.com/q/11420/351.

---
Tags: hash, algorithm-design, crc
---


# Question
Title: Encoding Turing machine-like behavior using families of sequences of vector spaces and modules. P=NP related
Let $F$ be a field. Suppose we have a machine $T$ that works with words that are elements of $F$, for exmaple $F = \Bbb{Z}/2, \Bbb{Q}$ (using arbitrary precision arithmetic), or $\Bbb{Z}/p$ for a prime $p$. Empty memory is represented by the vector space $F^0 := 0$. If an algorithm addresses $n$ memory slots, that would be $F^n$. And of course memory can grow, and we represent that by embeddings and certain consistency relationships.

Define $C$ to be a *computation category*, or in other words objects of $C$ are $F^n$ for $n \geq 0$, and the morphisms of $C$ are precisely the set of all compositions of the following:

1. $S = S(n,i,j) : F^n \to F^n = x \mapsto $ swap entries $x\_i$ and $x\_j$.
2. $A = A(n,i,j) : F^n \to F^n = x \mapsto $ add $x\_j$ to entry $x\_i$.
3. $M = M(n,i,c) : F^n \to F^n = x \mapsto $ multiply entry $x\_i$ by scalar $c \in F$.
4. $E = E(n,i) : F^n \to F^{n-1} = x \mapsto $ erase entry $x\_i$ or $ = x \mapsto (x\_1, .., x\_{i-1}, x\_{i+1}, .., x\_n)$.
5. $I = I(n, j) : F^n \to F^{n+1} = x \mapsto $ insert a new entry $0$ right after entry $x\_j$ or $ = x \mapsto (x\_1, .., x\_{j}, 0, x\_{j+1},..,x\_n)$ for $0 \leq j \leq n$.
6. $O = O(n,i,c) : F^n \to F^n = x \mapsto$ offset an etnry $x\_i$ by $c \in F$ or $ x\_i := x\_i + c$.

for all $n \in \Bbb{N}$ and $1 \leq i \leq n$. These represent all atomic operations on a typical machine as well as all compositions of operations (applying one instruction at a time, right-to-left), except for integer arithmetic (unless we use $F = \Bbb{Q}$ in which case it's except for multiplication of two memory variables) loops, & conditionals. Clearly, however, if we add in the concept of loops & conditionals (or something encoding those) one could write an algorithm for adding integers represented say in binary ($F = \Bbb{Z}/2$).

Without axiom 6, all morphisms of $C$ are $F$-linear maps, while with 6 all morphisms are $F$-affine maps. In either case, without axiom 4 and with some slight modifications such as $c \neq 0$ and $i \neq j$ we get that all morphisms are invertible. If a ring $R$ is used in place of $F$, then the same holds as long as in 4 we restrict our "code" to only use units $c \in R^{\times}$ there.

So leave the axioms as they are, and the category $C$ holds all operations required for "things to be Turing-complete".

Now consider $T = \bigoplus\_{n\geq 1} F^n$ to be the "tape space" which is sort of Turing-machine like in nature because $0$, which we'll call "blank" is the only symbol allowed to occur infinitely often at any given time. So if you wanted a binary representation of things and to be more Turing-like you should probably use $F = \Bbb{Z}/3$.

---

Now consider all endomorphisms of $T$ which can be constructed by changing each occurence of $F^n$ in the axioms with $T$.

**Definition 1.** One way to define a *deterministic algorithm* $f$, solving a problem $P : X \to Y$, in the computation category $C$ over $F$ is to define it to be a family of sequences (in $C$):

$$ M(x) = (M\_n(x), f\_n(x)) = (M\_1 \xrightarrow{f\_1} M\_2 \xrightarrow{f\_2} \dots) $$

indexed by $x \in X$, together with encode / decode maps $X \xrightarrow{g} \bigcup\_{n\geq 0} F^n \xrightarrow{h} Y$, such that for all $x \in X$ we have that $h(f\_{k(x)} \circ f\_{k(x)-1} \circ \cdots \circ f\_1(g(x))) = y$ for some $k(x) \in \Bbb{N}$, and such that each $f\_i$ is a morphism from one of axioms 1 - 6.

---

But a more convenient way is to define it as a family of sequences:

$$ 0 \to M \xrightarrow{f\_1} M \xrightarrow{f\_2} M \xrightarrow{f\_3} \cdots $$

of morphisms from the axiom list 1-4 but where $M$ is "big enough" to host the problem inputs / output encodings such as $M=T$ and 5 & 6 have been replaced with zeroing out and swapping entries.

---

Assume that $F = \Bbb{Z}$ for sake of argument.

Now under the latter setup, we have the concept of a while loop:

```
x2 = input
x1 = 0
while x2 != 0:
    x1 += x2
    x2 -= 1

```

encoded as:

$$ f(x) = \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}x + \begin{pmatrix} 0 \\ -1 \end{pmatrix} $$ iterated $x\_2$ times, or $$ P(n) = f^{n}\begin{pmatrix} 0 \\ n \end{pmatrix} $$ is the sum of the first $n$ natural numbers. Now, there is no $\dfrac{(n+1)n}{2}$ formula on our machine because there's no multiplication yet - it has to be defined first using the above "Turing-complete" set of axioms.

However, any time you have powering you have an efficient algorithm: Exponentiation by squaring.

---

In our example while-loop it was easy to calculate $n$ in it being just a component of our input vector. But usually in code it's difficult to compute how many times the loop will run precisely.

On the other hand, if $n$ is always increasing or always decreasing, meaning the value of $n$ a the $i$th iteration is $\lt$ the value of $n$ at the $i+1$th iteration (increasing), then squaring & checking will work efficiently.

For finite fields $F$ we need to define an ordering and be consistent with it. For $\Bbb{Z}, \Bbb{Q}$ etc, we define the ordering to be the usual ordered field, ring ordering.

---

**Question.** Does restricting our while-loop variable to be always increasing or always decreasing reduce the expressiveness of our collection of deterministic algorithms, meaning it would no longer be Turing-complete?

---

Feel free to answer in any programming language or math lingo you want. For instance can we solve the above issue by using a Python dictionary? I.e. it takes the loop variable $n$ modulo some small $m$ and maps it to the unrestricted loop variable's value. That's just a thought, and probably not sufficient to answer this.

---

**Motivation.** If the answer to the above is yes, then any algorithm that takes an exponential axiomatic steps to compute an answer can be done in close to $\log$ of that, meaning in polynomial-time. See: computational complexity of powering by squaring. This of course might help imply that P = NP.

---

To aid in understanding, a program computing an algorithm would end up looking something like:

$e\circ (f\circ (a\circ b^{x\_{1} \neq 0})^{x\_{3} \neq 0} \circ g)^{x\_7 \neq 0} \circ d^4$

where $a,b,c,d,e, f,g$ are all examples of axioms 1-6, and the exponent of the form $x\_i \neq 0$ means iterate until that condition is met, and a constant exponent will mean iterate a constant number of times.

So although a given algorithm may take exponential time to run, as long as there exists a program that takes up polynomial-space written like the above, you should be able to do powering-by-squaring & checking on each loop (as long as the answer to the above question is a yes). Thus reducing all exponential time algorithms logarithmically to polynomial-time. This argument is modulo some theory and math, but I have to keep things brief here.

# Answer
While loops with increasing variables are enough for Turing completeness. For instance, it is enough to implement cellular automata, and cellular automata are Turing-complete. While loops with increasing variables are also enough to implement a Turing machine: you have an outer while loop that iterates over steps of the Turing machine, and you can implement a single step of the Turing machine by a left-to-right scan of the entire tape (which can be implemented with a while loop with an increasing variable).
> 1 votes

---
Tags: complexity-theory, time-complexity, polynomial-time, turing-completeness, program-optimization
---


# Question
Title: How to prove correctness of a bidirectional converter between two CF grammars?
I have a converter between two context-free grammars which are both describing the same language but one uses infixes other than prefixes, has different symbols and sometimes switches order of nonterminals. It's a converter in a sense that it takes an expression in one grammar and outputs its equivalent counterpart in the other grammar and vice versa. All the rules for the translation are symmetrical.

I'd like to prove (at least beyond reasonable doubt) that my two-way converter works. Would it be sufficient to generate a lot of random expressions and show that when we put them through in both ways, the result is the same? I can't really decide what that would actually 'prove', if anything.

# Answer
No, looking at a lot of examples doesn't prove anything.

There is no general procedure that will work for all CFGs: testing equivalence of two context-free grammars is undecidable.

So, your proof will have to use special properties of the conversion process.
> 1 votes

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


# Question
Title: What is a program analysis technique for tracing assignments (mutations)?
I am looking to write a program analysis for Java programs that tracks assignments and is able to discern:

* whether a class field (static or not) is read and where the read originated
* whether a class field (static or not) is written and where the write originated
* properties of the value that is written: 1) is it a scalar 2) is the result of a composite expression (e.g. arithmetic expression or some other composite expression that involves applying operators to some operands)

This will need some sort of dependency resolution surrounding reads and writes to variables and (time permitting) consider variable aliasing as well.

I have been searching for various phrases that involve keywords "mutation" and "writes" but the results target mutation testing and other things that are not what I am looking for.

What is a technique or a class of techniques that fits these types of analyses and is there a fundamental technique that I can get started with?

# Answer
There are many techniques, with differing tradeoffs between the precision of the results vs the simplicity and running time of the algorithm.

I suggest looking at class hierarchy analysis (CHA), rapid type analysis (RTA), points-to analysis (e.g., Steensgaard's algorithm, Andersen's algorithm, and more), and more generally, alias analysis. You'll find a gazillion papers on these topics.

Note that in general this is an undecidable problem, so any analysis will output results that are an overapproximation (sound). Also, there are some complicated cases that for engineering reasons most analyses ignore (e.g., reflection).
> 0 votes

---
Tags: reference-request, programming-languages, compilers, static-analysis
---


# Question
Title: How to find time complexity of Breadth First Search for this tree?
This is what I got from another forum, but honestly doesn't make much sense to me.

> Time complexity for a single tree doesn't make a lot of sense, since the function in the big O notation might be nowhere near the actual computation time. Time complexity is all about how the algorithm scales as the inputs get larger. You can calculate the exact number of traversals needed, though.

# Answer
> 2 votes
It's true, time complexity for a single tree doesn't make sense. Aysmptotic notations are used to get bounds of how the algorithm scales in terms of its input size. The usual time complexity for BFS is given as $O(V^2)$ if adjacency matrix is used and $O(V+E)$ if adjacency list is used. This is however for a fixed no. of nodes.

Here a slightly modified analysis, which is used widely in the context of AI is better suited. Let $b$ be the branching factor, i.e. the maximum no. of children for any node in the tree and $d$ be the depth of the tree. Then an asymptotic upper bound for BFS would be $O(b^d)$.

---
Tags: artificial-intelligence, search, breadth-first-search
---


# Question
Title: Copying a linked list with additional arrows from each node
## Statement

Consider the following modified node structure for the linked list:

```
struct Node {
   int value;
   Node* next;
   Node* random;
}

```

The `next` field points to the next element in the list. The `random` field points to some other node, which is guaranteed to be in the same list. E.g. (black arrows denote `next`, purple - `random`):  Copy this list preserving the structure of arrows (time: $O(N)$, memory: $N$ cells for allocating a new list + $O(1)$)

## (Unsatisfactory) Solution

I came up with the following solution (I will explain what bothers me about it further):

Let's allocate $N$ cells for the new list *"in-between"* the nodes of the initial list, i.e. we insert the first cell, which will eventually end up in the new list, between the first and the second cells of the initial list; the second cell - between the second and the third; and so on... Thus, we get something like this:

Now, we can copy the structure of `random` arrows. We simply start traversing the list following the rule (keep in mind, black and blue nodes constantly alternate):

* whenever we enter a black node `N`, we find `R := N->random->next`, i.e. we store the node that succeeds the destination of the purple arrow pointing from the current node.
* whenever we enter a blue node `M`, we simply set `M->random := R`, that is assign the `random` field to be the `R`, acquired on the previous step.

Intuitively, I would draw this process like this (as physicist may put it, orange arrows denote *"distance"*, purple ones - the *"displacement"*):

And then we split this list into two (black and blue) in an additional third traverse. Voila!

## Question

What I dislike about this solution:

1. It does not work if the initial list is read-only
2. It uses 3 traverses, instead of just 1

So, my questions are:

1. Is there a way to do the same for a read-only list?
2. Is there a way to do the same in a single traverse?
3. Is there a way to do the same for a read-only list in a single traverse?

I would appreciate hints instead of full solutions :)

# Answer
> 1 votes
A very simple approach is to build up a hashtable that maps from the address of the original node to the copied node. Then, it is easy to copy the entire linked list. A single linear traversal of the list suffices, and the link can be read-only.

From a theoretical perspective, the expected running time is $O(n)$ if you use a good enough hash function (e.g., a 2-universal hash), though the worst-case time could be $O(n^2)$. From a practical perspective, you can expect $O(n)$ performance in practice if you have a good hash function.

---
Tags: algorithms, data-structures, discrete-mathematics, linked-lists
---


# Question
Title: Is there stubs and tests for data structures?
I want to implement all of the data structures from scratch but testing them is not an easy task. So, I wanted to ask if any of you know repository containing Class, Method Stubs for popular data structures and also their tests. Especially, unit tests are of a great importance.

Thanks in advance

# Answer
So, I found a great repo which contains not only DS implementations also some popular algorithms too. On top of that, it has a high unit test coverage. I'll use it: DSA by William Fiset

Even better, there are complementary video tutorials and they are freely available on YouTube: DS Tutorial by William Fiset @ FreeCodeCamp

Just wanted to post this answer here so someone who needs it doesn't waste days looking for it like I did.

---

**Good luck!**
> 1 votes

---
Tags: data-structures
---


# Question
Title: Solve the recurrence equation $T\left(n\right)\:=\:n\:+\:\sum _{i=1}^{n-1}\left(T\left(i\right)\right)$
I am trying to find the runtime of:

$T\left(n\right)\\:=\\:n\\:+\\:\sum \_{i=1}^{n-1}\left(T\left(i\right)\right)$

$T(1)= 1$

What is the way to solve this kind of problems?

# Answer
Hint.

$$ \cases{ T\_n = n +\sum\_{i=1}^{n-1}T\_i\\ T\_{n-1} = n-1 + \sum\_{i=1}^{n-2}T\_i } $$

subtracting the second from the firts we have

$$ T\_n-T\_{n-1}=1+T\_{n-1} $$

or

$$ T\_n -2T\_{n-1}= 1 $$

with solution (it is easy to solve)

$$ T\_n = c\_02^n+2^n-1 $$

and considering the initial value

$$ T\_n = 2^n-1 $$
> 1 votes

---
Tags: algorithms, complexity-theory, data-structures, runtime-analysis
---


# Question
Title: Confused about the appropriate slot in linear probing
The following paragraph is from the book CLRS:

Given an ordinary hash function $h' : U \rightarrow \\{0, 1, ..., m - 1\\}$, which we refer to as an auxiliary hash function, the method of linear probing uses the hash function $h(k, i) = (h'(k) + i) \\; \text{mod m}$ for $i = 0, \\: 1,\\: ... ,\\: m - 1$. Given key $k$, we first probe $T\[h'(k)\]$, i.e., the slot given by the auxiliary hash function. We next probe slot $T\[h'(k) + 1\]$, and so on up to slot $T\[m - 1\]$. Then we wrap around to slots $T\[0\]$, $T\[1\]$, $...$ until we finally probe slot $T\[h'(k) - 1\]$. Because the initial probe determines the entire probe sequence, there are only $m$ distinct probe sequences.

Now, in the fourth line I think we should probe $T\[(h'(k) + 1) \\: \text{mod m}\]$ other than $T\[h'(k) + 1\]$ because we are setting $i = 1$. Actually, if $0 \leqslant h'(k) \leqslant m - 2$, then these two are the same, but if $h'(k) = m - 1$, then they aren't. We simply should iterate over the probe sequence to find an empty slot for insertion but I don't know what's happening here.

# Answer
> 0 votes
You should probe $T\[h'(k)+1 \bmod m\]$, not $T\[h'(k)+1\] \bmod m$. This is already explained in the part you quoted: it says "up to slot $T\[m-1\]$. Then we wrap around..." -- and that is exactly the same as doing modular arithmetic, mod $m$.

---
Tags: hash, hash-tables
---


# Question
Title: Is the equality of Bloom filters analogous to set equivalence?
* I have two multisets $A$, $B$ where $A \subseteq B$.
* Using these two sets, we construct two Bloom filters $BF(A), BF(B)$; both using bitsets of size $n$ with the same $k$ hash functions.

What's the probability that:

$A \not\equiv B$ but $BF(A) = BF(B)$

**Notes:**

* Since $A$ and $B$ are multisets, they might have duplicate elements.
* However, duplications should not affect set equaivalence or subset relation. Due to lack of notation (on my side) please assume deduplication when checking for subsets or equivalence.
* By Bloom filter equality, I mean the bitsets being equal.
* I think we could assume hash functions are random and are independent of the elements of the sets.
* If needed, Jaccard index (ratio of intersection over union as an indicator of set similarity) could be approximated as $J(A,B) = \frac{|A|}{|B|}$ (or via MinHash)

# Answer
It is possible to find an upper bound on the probability of a collision in the fingerprint. Suppose the Bloom filter uses $k$ hash functions and maps into a bit array of size $m$.

---

The case $k=1$ is much easier to analyze explicitly, so I'll start with that case.

If $A\ne B$, there must be some element that is in $A$ but not $B$, let's say $a$. $a$ must hash to some bit of the array. With probability $(1-1/m)^{|B|}$, none of the elements of $B$ map to this bit position, and in this case, we necessarily have $BF(A)\ne BF(B)$.

So, if $A \ne B$, the probability that $BF(A)=BF(B)$ is at most $1 - (1-1/m)^{|B|}$. When $|B|$ is small compared to $m$, this is roughly $|B|/m$.

---

The calculations get messier when $k\>1$. If you're satisfied with an approximate upper bound, you can use the fact that when $k \ll \sqrt{m}$, $a$ will typically hash to $k$ different bits ($k$ different positions in the array). The probability that at least one of the elements of $B$ maps to a particular bit is roughly $|B|k/m$, assuming $|B| \ll m/k$ (following similar reasoning to that above). So, the probability that all of those $k$ bits are mapped to by some element of $B$ is roughly $(|B|k/m)^k$.

So, if $A \ne B$, the probability that $BF(A)=BF(B)$ is at most about $(|B|k/m)^k$, under the conditions that $|B| \ll m/k$ and $k \ll \sqrt{m}$.
> 1 votes

---
Tags: sets, streaming-algorithm, equality, bloom-filters
---


# Question
Title: When is a max heap tree invariant under a root removal, followed by a re-insertion of the root?
Let $T$ be a max heap tree with no duplicate values amongst the nodes. When does $T$ satisfy the following.

1. Remove the root, and restructure the tree to satisfy the heap property.
2. Reinsert the root, and restructure the tree to satisfy the heap property.

After 1, and 2, the resulting heap is exactly the same as the original heap. I'm trying to the exact condition that a max heap $T$ must have in order to satisfy this invariant property. i.e. a condition $\phi$ such that $T$ satisfies $\phi$ if and only if it is invariant after steps 1 and 2.

# Answer
> 1 votes
Start with the second step. When a large number is added as the last leaf to the (binary) heap, all elements on the path from the leaf to the root are swapped. Hence the first step (removing the maximum) must be like that, but in reverse.

---
Tags: trees, binary-trees, heaps
---


# Question
Title: Why is $a^mb^nc^pd^q$ with $m+p=n+q$ context-free?
$L = \\{$$a^mb^nc^pd^q \mid m+p = n+q,$$\text{ where } m, n, p, q \geqslant0\\}$

If, for instance, we try to construct a PDA for a similar language
$L2 = \\{$$a^mb^nc^pd^q \mid m=p $ $\text{and}$ $ n=q,$$\text{ where } m, n, p, q \geqslant0\\}$, it is clearly not possible to come up with one.

Then, why is $L$ context-free?

# Answer
We can keep the number $m-n+p-q$ on the stack of the PDA, and in the end check whether the result is zero. More precisely, we have the absolute value on stack, and the sign of the number in the state of the automaton.

We can also construct a context-free grammar, with a little case analysis. (The cases are equivalent to the question whether the pushdown-counter will drop below zero, or not.) Here was a recent similar question: Context free grammar for $1^n0^m1^k0^p$ where $n+k=m+p$.

The situation for $L2$ is quite different. There one would need to keep track two number differences $m-p$ and $m-q$ at the same time. This cannot be done by a PDA, so that is (at least intuitively) the reason the languages are different.
> 4 votes

---
Tags: context-free, pushdown-automata
---


# Question
Title: a question related to consensus number of a concurrent object
a) We know that solving consensus in asynchronous distributed systems is impossible.

b) Let the consensus number of a concurrent object be cn = 2, which means that two processes can solve consensus using the concurrent object.

From (a) and (b), can we conclude that the concurrent object cannot be implemented in asynchronous distributed systems?

# Answer
> 1 votes
Yes, if you add a few qualifiers to your statements. Consensus is unsolvable in an asynchronous shared-memory or message-passing system of n\>1 processes out of which at least one can fail. If you rule out failures, then consensus is solvable even if the system is asynchronous (e.g. just wait to hear all n proposals and then decide the smallest one).

If O is an object of consensus power 2, then it is impossible to implement O in an asynchronous shared-memory or message-passing system with failures. Otherwise, you could implement consensus for 2 processes, which would contradict the impossibility.

---
Tags: distributed-systems, consensus
---


title: Optimizing a sum of matrix chains

text:
# Question
Title: Optimizing a sum of matrix chains
**Edit** Jan 31: important special case is when the sums form a nested structure, search for "Hasse diagram is a tree" below

Here's a practically relevant variation on matrix chain problem:

Find optimal way to compute a sum over all weighted paths in a graph, where the weight of each path is the matrix product of edge labels (ie, a matrix chain)

For instance, take $Q$ corresponding to the sum of $$Q=A\_0 A\_1 A\_2 A\_3 A\_4 +A\_0 A\_1 A\_3 A\_4 +A\_0 A\_1 A\_4$$

We can represent it as the following sum over weighted paths

Now, we can count the number of matrix multiplications (in red) involved in computing this sum

Here's a more efficient way to compute $Q$

$$Q=A\_0A\_1(A\_2+I)A\_3A\_4 + A\_0A\_1A\_4$$

We can view it as following sum over paths:

Some edges are labeled with I, corresponding to multiplication by the identity matrix.

Given a list of matrix dimensions $d\_0,\ldots,d\_n$ corresponding to matrices $A\_0,\ldots,A\_{n-1}$ and a list of paths, the task is to figure out a sequence of matrix multiplications and additions which produces $Q$ using the smallest total number of scalar multiplications.

# Specifying Paths

Each term in the sum is specified as a pair of two numbers $(i,j)$, indicating that matrices $A\_{i+1},A\_{i+2},\ldots,A\_j$ are not present in the term.

For instance, for problem above, paths are $\[(), (1,2), (1,3)\]$. The second term is missing matrices $\\{A\_2\\}$ and the third term is missing $\\{A\_2,A\_3\\}$. Viewing paths as connected subgraphs of the chain graph, paths are partially ordered using subgraph relation. Therefore, the set of paths forms a lattice.

An important special case is when the Hasse diagram is a tree.

For example, consider this sum.

$$W=A\_0 A\_1 A\_3 A\_4 + A\_0 A\_1 A\_2 A\_4 + A\_0 A\_1 A\_4 + A\_0 A\_1 A\_2 A\_3$$

And the corresponding Hasse diagram:

Coming back to original example $Q$, we can order matrix products in the following way: $$Q=(A\_0 A\_1) A\_4 + (A\_0 A\_1) (A\_3 A\_4) + ((A\_0 A\_1) A\_2) (A\_3 A\_4)$$

Notice that some terms like $A\_0 A\_1$ are repeated, hence reuse this computation by introducing temporary variables like $T\_0=A\_0 A\_1$.

Now we can visualize a particular schedule below, and use this colab to find that it requires 7 scalar multiplications when $d\_0=d\_1=\ldots=1$

```
T0=matmul(A0, A1)
T1=matmul(T0,A4)
T2=matmul(A3,A4)
T3=matmul(T0,T2)
T4=add(T1,T3)
T5=matmul(T0,A2)
T6=matmul(T5,A3)
T7=matmul(T6,A4)
Q=add(T7,T4)

```

Now the question is -- how hard is this problem to solve or approximate:

1. when $d\_0=d\_1=\ldots=d\_n=1$
2. when $d\_i$'s are arbitrary positive integers

**Edit Feb 17** Example of problematic split mentioned in the comments

# Answer
One idea would be to generalize the O(N^3) DP for the case of a single path without skips to your case:

`d[i][j]` would be the cost of computing all the products of matrices \[A\_i ... A\_j) for all the paths for which all their missing matrices lie fully within the range. It can be done by iterating over a location to split the range \[i, j), recursively computing the best cost for the left and the right part. If some subtree lies entirely on one side of the split point, then I believe it just works. If the split point is in the middle of some subtree (and there will be at most one such subtree), the DP needs to be called recursively for the subtree, and the result needs to be added to the cost.

Below I have the code, without the proper handing of subtrees. For your particular example if already improves from 7 to 6 multiplications.

```
...

def compute_schedule(tensors, paths, cache, l = 0, r = -1):
    if r == -1:
        r = len(tensors)

    if r == l + 1:
        return tensors[l], "A%s" % l

    if (l, r) in cache:
        return cache[(l, r)]

    ret = None
    for mid in range(l + 1, r):
        lm, ls = compute_schedule(tensors, paths, cache, l, mid)
        rm, rs = compute_schedule(tensors, paths, cache, mid, r)
        cur = [lm @ rm, "%s @ %s" % (ls, rs)]

        # If the Hasse diagram is a tree, the `mid` will lie within at most one
        # child. The correct thing to do here would be to call the DP for such
        # subtree.
        # I don't do it here, and instead just compute the naive product from
        # left to right for all the runs in such subtree. This is not optimal
        # in general case.
        need_parens = False
        for path in paths:
            if l < path[0] and mid >= path[0] and mid < path[1] and r >= path[1]:
                t = tensors[l]
                ts = "A%s" % l
                for k in range(l + 1, r):
                    if k < path[0] or k >= path[1]:
                        t @= tensors[k] # don't actually need to multiply tensors here, enough to compute the shape
                        ts += " @ A%s" % k
                cur[0] += t
                cur[1] += " + %s" % ts
                need_parens = True

        if need_parens:
            cur[1] = "(" + cur[1] + ")"

        cur = tuple(cur)
        if ret is None or cost(cur[0]) < cost(ret[0]):
            ret = cur

    cache[(l, r)] = ret
    return ret

d = 1
ones = np.ones((d, d))
(A0, A1, A2, A3, A4) = (LeafNode(k * ones) for k in (1, 2, 3, 4, 5))
Q = A0 @ A1 @ A2 @ A3 @ A4 + A0 @ A1 @ A3 @ A4 + A0 @ A1 @ A4

Q2, Q2_str = compute_schedule([A0, A1, A2, A3, A4], [(2, 3), (2, 4)], {})
print(Q2_str)

np.testing.assert_almost_equal(Q.value, Q2.value)
assert cost(Q) == 9
assert cost(Q2) == 4
print(f"Schedule2 requires {cost(Q2)} scalar multiplications")

```

Yields

```
A0 @ ((A1 @ A2 + A1) @ A3 + A1) @ A4
Schedule2 requires 4 scalar multiplications

```
> 3 votes

---
Tags: dynamic-programming, matrices
---


# Question
Title: Question about max flow: If all edges have capacity in integers, does a max flow exist where the flow in every edge is in integers?
Let's assume that for every $e\in E$ it holds that $c(e)$ is an integer. Does it mean that there exists a max flow $f$ that for every $e\in E$ it holds that $f(e)$ is an integer? It sounds obvious but I can't exactly say why it is true.

# Answer
The integral flow theorem says "yes".
> 1 votes

---
Tags: algorithms, network-flow
---


title: Flow with edge-weight restrictions

text:
# Question
Title: Flow with edge-weight restrictions
I am given a graph $G=(V,E)$ undirected and two vertices, the source vertex $s$ and the target vertex $t$. Additionally, each edge comes with a capacity $c(e)$ (non-negative) and a set of weight functions $w\_1(e),...,w\_k(e)$. To simplify things, assume these weight functions are non-negative as well. I am also given a set of upper bounds $l\_1 ,...,l\_k$.

The weight of a set of edges under any $w\_i$ is additive. Denote $\tilde{E}$ as the set of edges (from the original graph) with positive flow (not back edges with the reverse flow, and not edges with a flow of zero). I would like to find the maximal flow between $s$ and $t$ such that $w\_i (\tilde{E} ) \leq l\_i$ for all indices $i$.

In other words, I am trying to find a flow under constraints for the edges that are being used.

I'm assuming this problem, as described, might be too hard to tackle. In this case, some assumptions can be made:

1. $c(e) = 1$ for all edges.
2. The goal is to find a flow $|f| \> 1$, but it does not have to be maximal, only non-trivial.

If this is still too hard, we can assume that $k=1$ and, for an edge, there is only the capacity and the weight. (I'm interested in the case of several weight functions, but if that approach is too hard, also a single weight function, and perhaps that idea can be generalized).

# Answer
> 2 votes
If $k=1$ and $c(e)=1$ for all edges $e$, then this looks equivalent to the minimum cost flow problem -- specifically, to finding an integral minimum cost flow. I believe combinatorial methods for the minimum cost flow problem are guaranteed to output an integral solution (if one exists).

If $k\>1$, this reminds me of multi commodity flow which is NP-hard. You might check whether the proof of NP-hardness for (integral) multi commodity flow can be adjusted to apply to your problem as well.

If I had to solve it in practice, I would start by formulating it as an integer linear program and applying an ILP solver. In particular, you could introduce a zero-or-one variable $x\_e$ for each edge $e$, with intention that if $x\_e=0$ then the flow through $e$ is 0, and if $x\_e=1$ then the flow through $e$ is non-zero. Assuming you are interested in integral flows (which you didn't actually state), then you can enforce this with the linear inequalities $f\_e \ge x\_e$ and $f\_e \le M x\_e$ where $M$ is a sufficiently large constant. Then add the flow conservation equations and minimize your objective function (which is a linear function of the $x$'s), and you should be good to go.

---
Tags: complexity-theory, graphs, shortest-path, weighted-graphs, network-flow
---


title: Compute accuracy of program?

text:
# Question
Title: Compute accuracy of program?
Is there a tool to compute the accuracy of a function in a program? Perhaps a static tool or some debugger-based tool that logs each time an arithmetic operator is applied? So one can avoid quirks in floating-point arithmetic, like destructive cancellation and similar.

# Answer
If you have a function and you want to monitor its (forward or backward) error, and you have a second function which is capable of measuring that error (say, for $f(x)=\mathrm{sqrt}(x)$, you could define $\mathrm{err}\_f(x)=\left|f(x)^2-x\right|$), then of course you can just add that error calculation into your function and have it store its results somewhere. But:

* Many "interesting" functions can't be inverted; and for those that can, it may be no easier to precisely evaluate that inverse. More broadly, implementing an error metric is often just as hard as implementing the function itself, and imprecision in the error metric is indistinguishable from imprecision in the original function.
* Measuring the error based on values passed in during testing may miss specific inputs which cause poor behavior. It's not always trivial to guess what those problematic inputs would be. Yet exhaustively exercising a function could be impractical, because of the huge possible range of inputs.

However, there are strategies which allow you to measure the potential imprecision of a computation for a given input, as long as your function sticks to simple numerical computation. The most common one is interval arithmetic, where the output of an operation is a range within which the true value is known to lie. While not a panacaea, interval arithmetic is easy to apply and is a good initial strategy for empirical analysis. There are interval arithmetic libraries available for many languages; see, for example, Boost's interval arithmetic library for C++ and PyInterval for Python.
> 1 votes

---
Tags: arithmetic
---


# Question
Title: Is reading contiguous pages (let's say 4KB) any faster than reading non-contiguous pages on SSDs?
I'm working my way on a problem which requires me to store elements in fixed 4KB-sized pages on an SSD. Each page is requested once for some computation on its elements, and then the CPU requests for another different page from the SSD. I'm trying to ascertain whether any page contiguous-ness can be exploited here for smaller latency times. Any research papers or articles on this area would be very appreciated.

# Answer
Short answer: no.

On an SSD, non-contiguous access (very slightly) increases the protocol and processing overhead - in theory, contiguous (or rather: longer) transfers could be slightly faster but you'd be hard pressed to actually measure that difference in real life, especially with NVMe.

That is caused in part by today's extremely fast processing capabilities but mostly due to the (almost) general overlap of I/O requests and data transfers using (deep) command queueing.

Note that I'm assuming a somewhat decent size of I/Os - most SSDs hit their peak (or even the interface's) with 4 KiB I/Os already.
> 1 votes

---
Tags: storage, caching
---


title: MaxClique is DP-hard

text:
# Question
Title: MaxClique is DP-hard
I want to show that

> MAX−CLIQUE={(G,k)|the largest clique of G is of size exactly k} is DP-complete

The idea is reduce MAX-CLIQUE to

> C={(G1,k1,G2,k2) | G1 has a k1-clique and G2 does not have any k2-clique}

which I already know is DP-hard.

I was seeing the solution on the second page of this link, but it seems that there is a mistake in the fifth paragraph, since the graph that builds G′\_1, is equal to the product tensor of the path of cardinality k1 with the graph G1, so the clique number is the minimum of the clique numbers of the factors. And this always gives 2, since every path has a clique number equal to 2.

# Answer
> 1 votes
Here's my take:

For every $(G\_1,k\_1,G\_2,k\_2)$ we make $(G\_3,k\_3)$ that satisfies: $$ (G\_1,k\_1,G\_2,k\_2) \in C \longleftrightarrow (G\_3,k\_3) \in \textit{MAX-CLIQUE}$$ For this to happen, $G\_3$ should have a maximum clique of size $k\_3$ only if $G\_1$ has a clique of size $k\_1$ and $G\_2$ not having a $k\_2$ clique.($G\_3$ should not have a maximum $k\_3$ clique because of $G\_2$)

Now considering these three observations:

1. If a graph $G=(V,E)$ have a clique of size $n$, one can make a graph $G'=(V',E')$ to have a maximum clique of size $n$: $$ V' = \\{ (i,v)| i \in \\{1,2,\cdots,k \\} \text{ and } v \in V \\}$$ $$ E' = \\{\\{(i,v),(j,u)\\}| i \neq j \text{ and } (i,v) \in V' \text{ and } (j,u) \in V' \text{ and } \\{v,u\\} \in E \\} $$ (Consider it as a $k$ cluster; edges are between two different clusters and there's no edge inside each cluster. With Pigeonhole principle, one can show this works.) (Symbol $^kG$)
2. If a graph $G=(V,E)$ has a maximum $k\text{-clique}$, one can make $G'=(V',E')$ to have a maximum clique of size $k+x$. Here's the procedure: $$ V' = V \cup \\{X\_1,X\_2,\cdots,X\_x | \forall 1\leq i\leq x, X\_i \not \in V \\} $$ $$ E' = E \cup \\{ \\{X\_i,X\_j\\} | 1\leq j \leq x \text{ and } 1\leq i \leq x \text{ and } i \neq j \\} \cup \\{ \\{X\_i,v\\} | v \in V \text{ and } 1\leq i \leq x \\} $$ (It's just adding a $x$ clique to the graph and connecting each of $x$ clique vertexes to all others )(Symbol $\_xG$)
3. If a graph $G=(V,E)$ has a maximum $k\text{-clique}$, one can make $G'=(V',E')$ to have a maximum clique of size $2k$. This is because the new graph $G'$ will have a $(2k-1)\text{-clique}$ if and only if $G'$ has a $2k\text{-clique}$. Here's the procedure: $$ V' = \\{ (i,v)| i \in \\{1,2\\} \text{ and } v \in V \\} $$ $$ E' = \\{\\{(i,v),(i,u)\\}| i \in \\{1,2\\} \text{ and } \\{u,v\\} \in E \\} \cup \\{\\{(i,v),(j,u)\\}| i,j \in \\{1,2\\} \text{ and } i \neq j \text{ and } u,v \in V \\} $$ (It's just like making another copy of $G$ and connecting all nodes to another one. And it can be proved by contradiction. Assuming that $G'$ has a $2k-1$ clique but no $2k$ clique.) (Symbol $G^2$)

There're two possibilities to make $(G\_3,k\_3)$:

1. $2k\_2 \> k\_1 \rightarrow G\_3=(G\_2^2)\cup(\_{(2k\_2-k\_1-1)}(^{k\_1}G\_1))$ and $k\_3=2k\_2-1$
2. $2k\_2 \leq k\_1 \rightarrow G\_3=(\_{k\_1 -2k\_2+1}(G\_2^2)) \cup ((^{k\_1}G\_1))$ and $k\_3=k\_1$

And link for Graph union. Also, it's trivial to show that it can be done polynomially.

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