# Question
Title: In Strassen's algorithm, why does padding the matrices with zeros not affect the asymptopic complexity?
In Strassen's algorithm, why does padding the matrices with zeros, in order to multiply matrices that are not powers of 2, not affect the asymptopic complexity?

Hi, I was reading this question but I do not follow Yuval Filmus's answer completely.

He offers two ways of padding the matrix with zeroes, I am interested in his first suggestion, padding the entire matrix with zeroes at the start such that the new matrix has dimensions $N\times N$ where $N = 2^c$.

He says "$N \< 2n$ so this doesn't affect the asymptotic complexity."

Could someone please elaborate as I do not follow, I understand calculating time complexity with the master theorem and $T(n) = aT(n/b) + f(n)$ so if someone could explain how this works in reference to that it would be greatly appreciated.

# Answer
Suppose that if $N = 2^c$ then you can multiply two $N \times N$ matrices in time $O(N^{\log\_2 7})$. For concreteness, let us say that two such matrices can be multiplied in time at most $CN^{\log\_27}$.

Now suppose that we are given two $n\times n$ matrices. We pad them to $N \times N$ matrices, where $N = 2^{\lceil \log\_2 n \rceil} \< 2n$. We can extract the product of the original matrices from the product of the new matrices. The two new matrices can be multiplied using at most this many operations: $$ CN^{\log\_2 7} \< C (2n)^{\log\_2 7} = 7C n^{\log\_2 7} = O(n^{\log\_2 7}). $$
> 3 votes

# Answer
You can take any matrix with N/2 \< n \< N rows and columns, pad it, and multiply it with Strassen's algorithm (or the naive algorithm for example), and then drop lots of zeroes that were created by the padding. But the execution time between N/2 and N rows only grows by a constant factor 7. Since we don't calculate the actual number of operations but only a Big-O expression, a constant factor of 7 doesn't change anything.
> 0 votes

# Answer
From $$n=2^c\le N\<2n=2^{c+1}$$ you draw

$$n^{\alpha}\le N^\alpha\<(2n)^{\alpha}=2^\alpha n.$$

As $2^\alpha$ is a constant, you can write $$N^\alpha=\Theta(n^\alpha).$$
> 0 votes

---
Tags: time-complexity, matrices, matrix-multiplication
---


# Question
Title: If we find that, e.g., T(n)<=d*n*lg(n) for some d that depends on n, is T(n)=o(nlgn)?
In the substitution method, if we find that, for instance, T(n) \< d*n*lg(n) but only for some d that depends on n, then can we say that T(n) = o(nlg(n)) (little-oh) in some cases? For example, in this case: we may find that the condition T(n) \<= d*n*lg(n) is only satisfied if d \<= n or, conversely, n\>=d. That would mean that, for every d, we can find an n0 such that T(n) \< d*n*lg(n) as long as n\>=n0=d, which is the condition for o(nlgn). I am not sure if this line of reasoning is correct.

# Answer
Yes, it is possible. Suppose $d=1/n$ and $T(n) = 0.5 \log n$. Then you'll find that $T(n) \< d n \log n$, and it is also true that $T(n) = o(n \log n)$.

In this case, it might be misleading to use a letter like $d$ for a function of $n$; people might expect you to write $d(n)$. Typically, letters like $c,d,\dots$ are used for constants (which don't depend on $n$).
> 1 votes

# Answer
Your reasoning is wrong. In the first place, unless $d(n)$ is constant, $n\ge n\_0=d$ does not hold. And even if that was the case, $dn\log(n)=o(n\log(n))$ would be incorrect (as is the statement "for every $d$").

Clearly

$$d(n)n\log(n)=o(n\log(n))$$ requires

$$d(n)=o(1).$$

---

Last but not least,

$$T(n)\le d(n)n\log(n)$$ is the very condition for

$$T(n)=O(d(n)n\log(n))$$ whatever the function $d(n)$.
> 1 votes

---
Tags: time-complexity, runtime-analysis
---


# Question
Title: Why $L$ = { $uc^nu$ | $u$ ∈ $P$, $n > 0$ } isn't context-free?
$P$ is the set of all words of even length on {0,1}.

Hi, i tried using pumping lemma to see why $L$ isn't a context-free language, but there's a decomposition where none of all three properties is violated ($|v|$ and $|x|$ iterating factors on $c^n$.).

I know this doesn't mean it's context-free, but to be sure it is not, what can i do?. If it isn't context-free i can't find an equivalent PDA, but why? has it to do with the stack?

As always, really thanks for your help.

# Answer
There is no problem using the pumping lemma here.

Assume that $L$ is context-free. Let $n$ be its pumping length and $u = 1^n0^nc1^n0^n\in L$.

By the pumping lemma, there exists a decomposition $u = vwxyz$ such that:

1. $|wxy|\leqslant n$;
2. $|wy| \> 0$;
3. for all $k\geqslant 0$, $vw^kxy^kz\in L$.

Let us distinguish cases:

* if $w$ or $y$ contains $c$, then $vxz$ does not contain any $c$ and therefore is not in $L$;
* if $w$ and $y$ are on the same side regarding the $c$, then $vxz = u\_1cu\_2$ with $|u\_1|\neq |u\_2|$, therefore is not in $L$;
* if $w$ and $y$ are of different length, the same reasonning as above can be done;
* since $|wxy| \leqslant n$, that means that $wxy$ is contained in the $0^nc1^n$ part, and that $w = 0^p$ and $y = 1^p$ with $1\leqslant p \< \frac{n}2$. That means that $vxz = 1^n0^{n-p}c1^{n-p}0^n$ is not in $L$.

We conclude by contradiction.
> 1 votes

---
Tags: context-free, pumping-lemma
---


# Question
Title: Is this variant of Exact Path Length Problem easy or NP Complete
I was reading about the longest path problem and it is NP Complete.

What about the problem where we need to find a path of some exact length $K$. All edges are directed. We are also allowed to repeat edges and vertices and all weights are positive.

The reason is where ever I look they in the definition emphasize:

1. Simple paths or
2. Weights are both positive and negative.

https://en.wikipedia.org/wiki/Longest\_path\_problem https://www.sciencedirect.com/science/article/abs/pii/S0196677401912015

So I wonder if those 2 conditions are necessary for NP Completeness.

# Answer
The reason for simple paths for the longest path problem is simple (pun not intended):

* either there is a cycle of positive weight, and therefore the longest path is not really defined as it could have an infinite weight;
* or all cycles have non-positive weight, and the longest path is a simple path.

As for weight values, if you can find a longest path in a graph with positive and negative weights, you can also do it in a graph with only positive weights (because no negative weights is only a particular case).

As for the exact weight path problem, it is also $\mathsf{NP}$-hard. There is a possible reduction from the Hamiltonian path problem.

Given a digraph $G = (V, E)$ with $V=\\{v\_1, …, v\_n\\}$, consider $G' = (V', E', f)$ such that:

* $V' = \\{v\_{i,k}\mid i,k \in \\{1, …, n\\}\\} \cup \\{s, t\\}$;
* $E' = \\{(v\_{i,k}, v\_{j,k+1})\mid k\in \\{1, …, n-1\\} \text{ and }(v\_i, v\_j)\in E\\}\cup \\{(s, v\_{i,1})\mid i\in \\{1, …, n\\}\\}\cup \\{(v\_{i,n}, t)\mid i\in \\{1, …, n\\}\\}$;
* for $e = (u, v)\in E'$, $f(e) = n^i$ if $v=v\_{i,k}$ and $f(e) = 1$ if $v = t$.

Then I claim (if I am not mistaken) that there exists a Hamiltonian path in $G$ if and only if there exists a path of weight $W=\sum\limits\_{i=0}^n n^i$ in $G'$. The idea is that given that the second index is incremented in each edge, a path in $G'$ can only contain at most $n+1$ edges (from $s$ to $t$). Also, it is not possible to cross two edges of the same weight twice (otherwise it would not be possible to get the total weight $W$).
> 5 votes

# Answer
It's NP-complete even with weights from $\mathbb N$, and polytime for unweighted.

Reference: *On the difficulty of finding walks of length $k$*, Basagni, Bruschi, Ravasio (1997).

The reduction is from Subset Sum (it's not trivial to see how it is even in NP, since a walk can be exponential in the input size), but they give a reasonable encoding.

The problem remains NP-hard on undirected graphs and even DAGs.
> 5 votes

---
Tags: algorithms, complexity-theory
---


# Question
Title: A variation of the maximum bipartite matching problem
Given a bipartite simple graph $G=(V,E)$, where $V=A\cup B$ and $A\cap B=\emptyset$, any edge in $E$ connects two vertices in $A$ and $B$, respectively. The maximum bipartite matching problem is to find the largest subset $E'\subseteq E$ such that no two edges in $E'$ share common vertices. We know that this can be addressed in $O\left(\sqrt{|V|}|E|\right)$ time. Now there is a variation. Each vertex in $A$ has exactly two edges connected with some vertex in $B$. We restrict each vertex in $A$ to be either unmatched, or matched with **exactly** two vertices in $B$. Each vertex in $B$ can only match at most one vertex in $A$. The question is: how many vertices in $A$ can be matched at most?

I've considered reducing this problem to max flow. I set up a super source $s$ and a super sink $t$. $s$ connects to all vertices in $A$, with the capacity of the edges being $2$. $t$ connects to all vertices in $B$, with the capacity of the edges being $1$. The edges between $A$ and $B$ have capacity $1$, and they're added according to the edge set $E$. Now the answer of the question is the max flow of the graph divided by $2$. But in this way, I can't restrict each vertex in $A$ *not* to match only *one* vertex in $B$. So it doesn't work.

My question is: Can this problem be reduced to some problem known to be in $\mathbf{P}$?

Background: This problem is derived from a "string merging" game. Let there be $m$ distinct strings with length $n$, and each string consists of $0$, $1$. If there is *one and only one* corresponding character in two strings being complement (i.e. $0$ and $1$), we can merge the two strings into a new string with the character replaced by $x$. For example, $10\color{green}{1}11$ and $10\color{green}{0}11$ can be merged into $10\color{blue}{x}11$. Each string can only be used once, and new strings cannot be furthur merged. Now given $m$ of such strings, the goal of the game is to merge them into as fewer strings as we can. However, one string can be merged with many strings, so we need to find out the most clever way.

Here is another example. Consider four strings:

```
(a) 0110
(b) 0010
(c) 0000
(d) 1000

```

(a), (b) can be merged into $0x10$, (b), (c) can be merged into $00x0$, and (c), (d) can be merged into $x000$. There are two strategies to perform merging: the first way is to merge (a), (b) and (c), (d), then we'll get two strings. The second is to merge (b), (c), but (a) and (d) cannot be merged, so we'll get three strings. Apparently the first strategy is more clever. Then the question is: what is the most clever way?

I've reduced the problem into a graph theory problem. Let the new strings form set $A$ and the original strings from set $B$. The vertex of the new string is connected to the two strings merged into it. Then the problem is to find the maximum match as I mentioned.

# Answer
> 0 votes
Yes, the problem is in $\mathbf{P}$. For every vertex $u\in A$, let $M(u)$ be the set of the two vertices in $B$ that is connected with $u$. For every vertex $v\in B$, let $N(v)=\\{u\in A|(u,v)\in E\\}$. We construct another undirected graph $G'=(V',E^\*)$, whose vertex set is $V'=B$. For every $v\_1,v\_2\in B\\,(v\_1\ne v\_2)$, we let $(v\_1,v\_2)\in E^\*$ if and only if $\exists u\in A$ such that $M(u)=\\{v\_1,v\_2\\}$. Now each (effective) $u\in A$ is converted to an $e^\*\in E^\*$ (for multiple $u$ that share common $M(u)$, we only take one of them). In $G$ we require that each vertex $v\in B$ can only match at most one $u\in A$, so equivalently we require every $e^\*\in E^\*$ we selected does not share a common vertex. Now the problem becomes the maximum matching problem, which can be addressed in $O\left(|E^\*|{|B|}^2\right)$ time using the blossom algorithm.

For the version of the "string merging" game, actually, the graph $G'$ is a bipartite graph and hence the problem can be solved with the Hopcroft-Karp algorithm. We can consider it in the following way. For two strings $s\_1, s\_2$, if they can be merged, we denote $g(s\_1,s\_2)$ as the specific position being merged. For example, $g(00\color{green}{1}1,00\color{green}{0}1)=3$, since the third characters in the strings are merged. The method to build $G'$ is as follows. Each string is equivalent to a vertex $v\in B$, so $B$ is simply the string set. We define $(s\_1,s\_2)\in E^\*$ iff the two strings $s\_1,s\_2$ can be merged. We now show that any cycle in $G'$ contains even amount of vertices (strings). Let $C$ be a cycle and $V(C)$ be its vertex set. We assert that if $s\_1,s\_2\in V(C)$ and $g(s\_1,s\_2)=p$, then there must be $s\_3,s\_4\in V(C)$ such that $\\{s\_1,s\_2\\}\cap\\{s\_3,s\_4\\}=\emptyset$ and $g(s\_3,s\_4)=p$. This is easy to understand. We take a tour along $C$: $s\_1\to s\_2\to \cdots\to s\_1$. Note that when the $p$-th character alters, the two adjacent strings can be merged. Now $s\_1\to s\_2$ is just an example of such situation. Without losing generality, lets say the $p$-th character in $s\_1$ is $0$ (written as $s\_1\[p\]=0$). Then we must have $s\_2\[p\]=1$. Now since the destination of our tour is $s\_1$, the $p$-th character transform from $1$ to $0$ along the tour. When it transforms, we found $s\_3$ and $s\_4$. By this approach we can prove that the graph $G'$ is a bipartite graph.

---
Tags: algorithms, graphs, network-flow, bipartite-matching
---


# Question
Title: De Casteljau's algorithm without temporaries / stack
De Casteljau's algorithm is a method for calculating a point on an order $N$ Bezier curve at time $t$ by performing a linear interpolation between two order $N-1$ Bezier curves at time $t$. You do this recursively until you reach order 0 which is single point / data value.

Calculating a point on an order 1 (linear) Bezier curve with control points $A$ and $B$ at time $t$ is done like this:

$\overline{AB} = A(1-t) + Bt$

Which you can see is just a linear interpolation between $A$ and $B$ at time $t$.

Calculating an order 2 (quadratic) Bezier curve with control points $A$,$B$ and $C$ is done by interpolating between $A$ and $B$, interpolating between $B$ and $C$ and interpolating between those results:

$\overline{AB} = A(1-t) + Bt$

$\overline{BC} = B(1-t) + Ct$

$\overline{ABC} = \overline{AB}(1-t) + \overline{BC}t$

Note that you could expand that out algebraically to get a polynomial in Bernstein form that doesn't use interpolation, but instead can be evaluated directly in one step:

$\overline{ABC} = A(1-t)^2 + 2B(1-t)t+Ct^2$

Calculating an order 3 (cubic) Bezier curve with control points $A$,$B$,$C$,$D$ at time $t$ would continue the pattern by doing a linear interpolation between $\overline{ABC}$ and $\overline{BCD}$ at time $t$.

When evaluating a curve using the De Casteljau algorithm, you need temporary storage. In the $\overline{ABC}$ case you need to first calculate $\overline{AB}$ and $\overline{BC}$ and then you combine those results. The storage needs get larger as the curve order increases.

My question is this:

Is there a way to reformulate the De Casteljau algorithm such that you can still use lerps to evaluate a point on the curve, but without the temporary storage needed?

# Answer
The OP has indicated in the comments that they are only interested in a specific time $t$. De Casteljau's algorithm can be described as follows:

* Input: order $N$, points $A\_0,\ldots,A\_N$, time $t \in (0,1)$.
* Calculate $\overline{A\_i A\_{i+1}} = A\_i(1-t) + A\_{i+1}t$ for $0 \leq i \leq N-1$.
* Calculate $\overline{A\_i A\_{i+1} A\_{i+2}} = \overline{A\_i A\_{i+1}} (1-t) + \overline{A\_{i+1} A\_{i+2}} t$ for $0 \leq i \leq N-2$.
* Continue similarly for $N-2$ more steps.
* Output $\overline{A\_0 A\_1 \ldots A\_n}$.

It is not completely clear what it does it mean to "implement" De Casteljau's algorithm. However, a reasonable informal interpretation of this statement is as follows:

> Schedule the computations in De Casteljau's algorithm in a way that uses the least amount of space and the least amount of computations.

Note that the two efficiency measures could potentially conflict.

There is an area of theoretical computer science covering exactly such questions, namely *pebbling*. See Jakob Nordström's survey-in-making. Your task exactly corresponds to pebbling a height $N$ pyramid. On the one hand, this is known to require $N+2$ pebbles (roughly temporary memory locations). On the other hand, there is a pebbling strategy using $N+2$ pebbles and a linear number of steps (a linear number of computations — we are allowing computing each node, i.e. $\overline{A\_i \ldots A\_j}$, more than once).

Here is how this pebbling strategy looks like in the case $N=2$:

* $T\_1 \gets A\_0$.
* $T\_2 \gets A\_1$.
* $T\_3 \gets T\_1(1-t) + T\_2t$.
* $T\_1 \gets A\_2$.
* $T\_4 \gets T\_2(1-t) + T\_1t$.
* $T\_1 \gets T\_3(1-t) + T\_4t$.

The output is in $T\_1$.
> 1 votes

# Answer
Direct evaluation of the Bernstein polynomials can be done in time linear in $N$, using the recurrence

$$B(t;i,N)=\frac t{1-t}\frac{N-i+1}iB(t;i-1,N),\\B(t;0,N)=(1-t)^N.$$

This can be used to compute the interpolant in time $O(N)$, with $O(1)$ temporary storage.
> 0 votes

---
Tags: algorithms
---


# Question
Title: In algorithms for matrix multiplication (eg Strassen), why do we say n is equal to the number of rows and not the number of elements in both matrices?
In Strassen's algorithm, we calculate the time complexity based on n being the number of rows of the square matrix. Why don't we take n to be the total number of entries in the matrices (so if we were multiplying two 2x2 matrices, we would have n = 8 for the four entries in each matrix)? Then, using the naïve method of multiplying matrices, we would end up with only n multiplications and n/2 additions. For instance, multiplying \[1 2, 3 4\] by \[5 6, 7 8\] yields \[1\*5+2\*7 1\*6+2\*8, 3\*5+4\*7 3\*6+4\*8\]. Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n).
Of course, this reasoning is wrong because the time complexity cannot be linear but I don't understand why. I would appreciate any input. Thank you!

# Answer
> Here, n = 8 and we are doing n = 8 multiplications and n/2 = 4 additions. So even a naïve multiplication algorithm would yield a time complexity of O(n).

That is wrong. It might work for a small example like $n = 8$, but for bigger ones it doesn't. E.g. if you have two square matrices with a total of $n = 200$ elements (two $10 \times 10$ matrices) you have already 1,000 multiplications, for $n=20\\,000$ you have $1\\,000\\,000$.

---

Now to the actual question. It is possible to give the number time complexity in terms of the number of matrix elements, but it is not very practical.

One problem is, that the complexity differs a lot depending on the shape of the matrix:

* A multiplication of a $1 \times N$ matrix with a $N \times 1$ matrix has time complexity $O(N)$ (linear in the number of matrix elements).
* But a multiplication of a $N \times 1$ matrix with a $1 \times N$ matrix takes $O(N^2)$ (quadratic in the number of elements).

So it's a lot harder to argue about time complexities when you only know the number of elements.

And it's also easier to talk about the matrices in general. It feels more natural. E.g. saying "I've doubled the number of rows of the first matrix" makes sense to everybody (and you immediately know that the algorithm will run about twice as slow, "I've doubled the both dimensions of both matrices" makes sense. But saying "I've double the number of elements" will confuse anybody, how does the matrix look like afterwards. Did you increase both dimensions by a factor of 1.41? Did the matrix change shape? Or what happen? And what impact does it have on the runtime...
> 20 votes

# Answer
Short answer: because it's natural and convenient.

Longer answer: The number of multiplications to multiply a matrix of size p,q with a matrix of size q,r is pqr with a naive algorithm, and something more complicated with a smarter algorithm. The number of multiplications to multiply two square matrices of size n,n is n^3 with a naive algorithm, and n^(some number) with a smarter algorithm. So, we simplify everything by only considering square n,n matrices and expressing the complexity in function of n.

Note that it's not just with matrices that you have to be careful what "n" means:

* With graphs, it's common to have "n" be the number of vertices, which means the length of the input representing the graph is probably about n², depending on the number of edges and on the choice of representation.
* When the input is a string of digits representing a number, if N is the number and n is the length of the input representing that number, then n = log(N) and N = 2^n, so be very careful whether it is n or N in the complexity.
* There are algorithms with so-called pseudo-polynomial time complexity, which means they take exponential time with respect to the length of their input, but polynomial time with respect to the number represented by their input.
* There is a simple dynamic programming algorithm to solve the Knapsack problem in pseudo-polynomial time, which for some applications can be good enough; this algorithm is polynomial in the maximum weight capacity, but exponential in the number of digits of the maximum weight capacity, which really means it's exponential in the precision, the number of digits, that we're asking for.
* Factorising a number N into a product of primes is said to be very hard, yet obviously this can be done in sublinear time with respect to N: iterate on all numbers below √N and check if any of them divides N. This algorithm is sublinear in N, but exponential in the number of digits of N, so it's really exponential in the length of the input.
> 9 votes

# Answer
For n = 100, the naive algorithm takes 1,000,000 multiplications and almost as many additions. If we let n = number of rows / columns, then it takes $n^3$ multiplications and $n^3 - n^2$ additions. If we let $m = 2n^2$, that is the total number of elements in both matrices, then it is $m^{1.5} / 2^{1.5}$ multiplications and $m^{1.5} / 2^{1.5} - m/2$ additions. Both numbers are $O(m^{1.5})$ and not $O(m)$.

But the reason why we argue in the number of rows and columns, and not the problem size, is that the number of rows and columns usually follows naturally from the problem we try to solve. And in case of the Strassen algorithm which recursively divides a matrix into smaller sub matrices, its easier to reason that you need 7 matrix multiplications of half size. The algorithm is based on number of rows and columns and not on number of elements. And lastly, if the matrices don't have identical size, the number of calculations can easily be found from the numbers of rows and columns, but number of elements leaves a lot of room how many operations are needed, depending on the shapes of the matrices.
> 6 votes

# Answer
Because **users** of matrices think in terms of the matrix *dimensions* rather than the number of elements. Because that's related to the "size" of their problem in some way. E.g., you have *n* linear equations to solve, you're working in an *n*-dimensional space, ...

IOW matrices aren't interesting to work with as a bunch of elements in a rectangular shape and no other reason for existing - they're interesting to work with to use to solve some problem you have and *that's* why we study how fast you can compute with them. How "big" of a problem can you actually solve?
> 2 votes

# Answer
One aspect I'd like to stress in addition to the other answers (already covered to some extent there):

With the `O(n)` notation we express how the run time / memory consumption / ... changes if we change the "input size". But it's completely up to you how you define the term "input size", so you have to document this definition (and many CS sources take "the natural definition" for granted, so they feel they need not specify what `n` means).

Let's take multiplication of two large integers a simple example:

* If you define M to be the first integer and N the second, primary-school multiplication will give you a stunning `O(logM logN)` performance.
* But more often, M and N are defined to be the number of (e.g. decimal) digits in the integers, and then the same algorithm now counts as `O(M N)`.

So, in your case, you can of course define `N` to be whatever you want, and then analyze how the run time changes if you supply inputs that vary in the aspect you called `N`. The results can be more or less useful, depending on your definition of `N`:

* If `N` is the value of the first entry of one of the arrays, changing `N` will not affect run time, and you get an `O(1)`. Though this is a formally valid definition, you'll agree that it isn't helpful.
* If `N` is the maximum row or column size in one of the two matrices (a commonly-used definition), the naive multiplication takes `O(N^3)`.
* If `N` is the number of entries of the bigger matrix (your suggestion), the same algorithm now has `O(N^1.5)`. It hasn't become faster, you just redefined the meaning of `N`.
> 2 votes

---
Tags: algorithms, time-complexity, matrices, multiplication
---


# Question
Title: Are two regularity properties on hypergraphs equivalent?
Let $H=\left( E\_0 ,E\_1 ,E\_2 , \ldots , E\_d \right)$ be a $d$-dimensional full-hyper graph/complex. That is to say, if for some $i\in \left\[d \right\]$ the hyper-edge $e\_j \in E\_i$ than for any $i-1$-dimensional $e\_k \subset e\_j$: $e\_k \in E\_{i-1}$. The vertices are $E\_0$, the hyper-edges between $2$ vertices are $E\_1$, between $3$ are $E\_2$ and so on.

I bring forward 2 definitions of regularity, and I'd like to show their equivalence:

* There exists $r\_1,\ldots , r\_d$ such that for each $1\leq i \leq d$ each vertex $v\in E\_0$ has exactly $r\_i$ hyper-edges from $E\_i$ to which it belongs.
* There exists $r\_1,\ldots , r\_d$ such that for each $1\leq i \leq d$ each $e\_j \in E\_{i-1}$ has exactly $r\_i$ hyper-edges from $E\_i$ that contain it.

I claim that the definitions are equivalent, obviously with different values of $r\_i$'s.

My attempted proof for the case of $d=3$:

$\Leftarrow$

Each vertex $v$ has $r\_1$ $2$-edges, each edge has $r\_2$ $3$-edges. Each $3$-edge, by definition, uses exactly a distinct pair of $v$'s $2$-edges. Therefore, each $3$-edge is counted twice - one per each $2$-edge of $v$. This makes the total number of $3$-edges exactly $\frac{r\_1\cdot r\_2}{2}$.

Having a bit trouble for the other direction. Could not disprove it, and I believe it holds, but not every pair of edges that share a common vertex must yield a $3$-edge.

Also, I'd like to try to generalize this for any $d$, but first, to understand the other direction for $d=3$.

Are the 2 definitions for regularity equivalent? I have 2 questions:

* For the case of d=3?
* For any d?

(What I provided was a proof in one direction. As for the other direction, I am not sure it holds.)

# Answer
> 3 votes
Consider the following full hypergraph $H$ (or abstract simplicial complex) of dimension $2$, represented as a simplicial complex (nodes are in black, $2$-edges in red, $3$-edges are turqoise triangles):

(or, algebraically: $E\_0 = \\{v\_1,v\_2,v\_3,v\_4,v\_5, v\_6\\}$, $E\_1=\\{(v\_1,v\_2), (v\_2,v\_3), (v\_3,v\_4), (v\_4,v\_5), (v\_5,v\_6), (v\_1,v\_6), (v\_1,v\_4), (v\_2,v\_6), (v\_3,v\_5)\\}$, $E\_2 =\\{(v\_1,v\_2,v\_6),(v\_3,v\_4,v\_5)\\}$ )

$H$ is regular according to the first definition, since each vertex belongs to 3 $2$-edges and 1 triangle. However, $H$ is not regular according tot the second definition, because e.g. $(v\_1,v\_2)$ is contained in 1 triangle while $(v\_2,v\_3)$ is contained in 0 triangles.

This means the "other direction" does not hold for dimensions $2$ and higher, so the two properties are not equivalent. (Of course, the two definitions are trivially equivalent for dimension $1$)

---

As for whether the second property implies the first, your proof (which seems to be for dimension $2$) looks correct to me. The step of going from $2$-edges to $3$-edges can be generalized into $i$-edges to $(i+1)$-edges, after the proof follows by induction. So, it seems the second property is stronger than the first.

---
Tags: algorithms, graphs, combinatorics, definitions
---


# Question
Title: Is there an algorithm that can get the minimal element of a min-heap in O(log* n)?
I came across this question when studying for an exam:

given a min-heap that has no prime numbers in it, is there an algorithm that can get and delete the minimum of that heap in O(log\* n) ?

The answer simply said no because in this case we can sort an array in o(n log n) which we’ve learned isn’t possible without additional data.. but I can’t see how exactly is it possible to sort an array in o(n log n) if the algorithm only works if the heap has no prime numbers…

Edited: The question asks “is there an algorithm as such”? Logically speaking the answer is no, but I couldn’t understand why? they tried to refute it by saying had there been such an algorithm we would’ve been able to sort an array in o(n log n) which isn’t possible. I think whether the algorithm works on prime numbers matters, if it works on all numbers then no matter what the input is, I can create a heap in O(n) and then get the value of delMin in O(log\* n) n times aka O(n log\* n) which is o(n log n), but since the said algorithm only works on non-prime numbers then I don’t think it’s possible to refute the statement.

# Answer
There are n! permutations how an array of n numbers could be arranged. To sort an array, you need to rearrange items so that they are in sorted order, and for every permutation a different rearrangement is needed. Every decision you make cuts the number of possibilities by half in the best case. Therefore any comparison-based sorting algorithm needs at least $\log\_2 (n!)$ comparisons. A very good estimate for n! is $n! ≈ n^n e^{-n} \sqrt (2 \pi n)$, and the base two logarithm is about $n (\log\_2 (n/e))$ which is $\Theta (n \log n)$. So that's the fastest possible time for sorting.

Building a min-heap takes n steps, and you can easily sort an array by building a min-heap and extracting the smallest element n times. It follows that the average time to extract the smallest element must be $\Theta (\log n)$. It cannot be smaller, or we would have a sorting algorithm that is faster than possible.
> 0 votes

---
Tags: data-structures, sorting, arrays, heaps
---


# Question
Title: Determining runtime of a theoretical program (question of extraordinary complexity)?
*I apologize in advance, as I don't have a clue to which stackexchange to post this question! I beg you to not delete this question, as I have chronic pain and it is very important to me!!! I actually written this hours, a lot of effort went into this question...*

### **How does one determine runtime of a theoretical program???**

* This is a theoretical question about a program I want to make. I might just ask now to save myself a lot of time!
* Is the following program even calculable on PC in general (my specs: Intel i5 9600KF, Geforce 3070) in reasonable time-frame??? As it is possible it would take years!
* It doesn't have to be an exact specification, but it can be an estimate! I Am more interested if it is even possible (right now)

# Description of a Program:

It is a diet program, which purpose is to give you foods in grams to eat to achieve dietary goals...

# **Number of permutations:**

Lets say: you have 10 nutrients in a tomato, that's 10 floating point numbers. Multiply this by 100, because you can select 1-100g of a food. And lets say you are choosing from a pool of 30 foods. That's (10\*100)^30 of permutations program would have to consider, not even mentioning doing actual calculations in practice!

# **What I want to achieve:**

**Now this is quite complicated and I have low verbal intelligence so listen closely!!!** I want to make a program which basic function would be: compare all permutations of substances included in foods with each other to give you amounts of foods to eat: so all your nutrient intakes (e.g. Vitamin D) would get closest to their respective RDA goals!

*Note: field of science "nutrigenetics" allows you to get estimates for your personal RDA goals!*

A program would have to take into an account all portions between 1-100gram of foods. E.g. it would enumerate amounts of nutrients contained per 1-100g of a tomato, so you would end up with a list of amounts of all nutrients per 1g, 2g, 3g... until 100g. And it would do this for all other foods in a database as well!

**So you would end up with a list of all substances contained per 1-100g of a range of foods.**
Like: contents of Vitamin A,B,C,D... per (1-100g) of a tomato, citrus, apple and so on... These numbers are usually in unit mg and they include mostly floating-point numbers e.g. 1.245mg of Vitamin C, 20.5mg of sugar, 4.6765mg of Vitamin D... anyways you get the picture.

So you would end up with a list (lets say you added 30 foods to your database) of 30 foods, which have all of their nutrients listed under them, i.e. for their respective portions (1-100g). And then the program would try to find the best permutation (between picking 1-100g amounts of all selected foods) so you reach your RDA goals...
**To further illustrate this:**
(You enter into your database nutrient contents of a food per 100g) e.g. in practice this would mean - food 1: tomato, portion selected: 1g, calculate contents of vitamin (A,B,C,D...) = 20.12, 10.542, 5.1123, 7.37... Then it would calculate amounts of nutrients for portion selected: 2g and so on...

Same process with a food 2: orange, portion selected: 1g, calculate contents of vitamin (A,B,C,D...) = 13.56, 23.5854, 10,332, 7,332...

# **Theoretical framework of the program:**

**Note:** I do not have actual understanding how this program would proceed programmatically in calculating this yet, so in theory only!

This program would have to add together large amounts of numbers of all substances from different foods. And then evaluate, if yields (of all substances of all foods added together) for selected amounts of foods are matching all your RDA goals!

But for example: (let's say you have 5 foods for simplicity) tomato, apple, orange, pear, kiwi. Let's say all have contents of Vitamin A. That would be 5 numbers to add together like: 1.23232 + 4.65 + 15.67 + 31.17 + 4.112 (this example omits 1-100g portions of all foods selected and all other nutrients contained within these foods). Then program would have to check if nutrients contained in amounts of foods (it selected) match all your RDA goals: *e.g. 40mg of sugar, 10 000mg of Vitamin A, 500mg of Vitamin D, 400 mg of magnesium, 1000 mg of calcium.*

*Aside: we could also allow 10% deviation from RDA goals and if not met: it would start calculations over.*

I guess because sheer amounts of calculations, for sake of performance: it would compare old results, to new permutations (once calculated) probably in bursts for sake of performance. Rather than calculating all permutations once and then picking the best one!

## Note:

*\- I use word substances and nutrients interchangeably!*
*\- I refer to a portion as selecting a part between 1-100g of a food e.g. tomato.*
*\- I Am not even sure, if I Am using word enumerate right in this context, I use it as taking all items from a list and assigning them some number like: giving variable "25mg of tomato" - value named "Vitamin C" = 1.13232. So in the end all foods have assigned all of their substances to them for their respective portions 1-100g!!!*

# Answer
This is feasible to compute in fairly fast (polynomial) time with linear programming.

This problem seems like a poster problem for linear programming where you specify a set of equalities and inequalities, e.g. tomato between 0 and 100 grams, apple between 0 and 100 grams and then if each gram of a tomato has 1 mg of vitamin X and each gram of an apple has 2 mg of vitamin X and you aim for 7 mg of vitamin X you specify $1 * tomato + 2 * apple = 7$.

In practice there may be no exactly correct solution so you will have to instead make some of the equalities into a function that will be optimized to match as closely to your goals as possible.

The program does not have to iterate over each gram of each food, it takes the inequalities and computes the correct weights of our foods.
> 1 votes

# Answer
I just copied my answer from a similar question: Since you are asking in Computer Science, I very much recommend George Dantzig's "Linear Programming and Extensions". It explains linear programming in a way that a normal human being (like me) can understand. The link has links to three .pdf files of this book.

https://www.rand.org/pubs/reports/R366.html

This was invented in 1952, I think, and was used for practical problems using mechanical calculators. No computers involved. For five items and ten ingredients this is quite a trivial problem actually, that should be solved in less than a millisecond.
> 0 votes

---
Tags: time-complexity, combinatorics, permutations, performance
---


# Question
Title: given an integer array of length n, find tuples $(a,b,c,d)$ such that $d=\sqrt{a^2+b^2+c^2}$
any reference on what kind of problem it is and what algorithm can solve this in $n^2\log n$?

for 5 as d, the numbers 4 and 3 and 0 would work. so i think there should be zero in the array.

maybe use naive approach($O(n^4)$) and memoize the raising to power 2 and adding up the results to decrease the running time?

# Answer
> 0 votes
You don't memoize "raising to the power of two". Looking up these powers in a table will take ten times longer than just multiplying.

You want $d^2 = a^2 + b^2 + c^2$ or $d^2 - a^2 = b^2 + c^2$.

You take all pairs of two integers x, y in the array and calculate x^2 + y^2 and store that into array A, and calculate x^2 - y^2 where x is the larger number and store that into array B. That takes O(n^2) steps. You want elements in array A and B that have the same value.

Sort both arrays in O (n^2 log n^2) = O (n^2 2 log n) = O (n^2 log n) steps. And then you iterate through both arrays from the start and find equal elements, another O (n^2). Total time O (n^2 log n).

---
Tags: algorithms
---


# Question
Title: Computing distance to clique in FPT time
I am a research scholar, and I currently work in parameterized algorithms. My current work involves proving that a problem is FPT for the parameter *distance to clique*. Although it is known that computing a *distance to clique* of size $k$ can be done in FPT time using a simple branching algorithm, I couldn't figure out how. Please elaborate on this. Once I get this, then I can assume that the *distance to clique* is given and solve the rest.
For a graph $G = (V, E)$, the parameter *distance to clique* is the cardinality of the smallest set $D \subseteq V$ such that $V \setminus D$ is a clique.

# Answer
> 1 votes
The distance to clique is the fewest number of vertices to remove such that the resulting graph is a clique.

Let us take the complement graph $\overline G$ of $G$. Now, we instead want to find the fewest number of vertices to remove such that the resulting graph is *edgeless*.

Recall that if $I$ is edgeless (i.e. an independent set), then $C$ is a *vertex cover* of $G$. Hence, distance to clique is simply vertex cover in the complement graph.

---
Tags: np-hard, parameterized-complexity
---


# Question
Title: Integer factorization: Why can't we use the test algorhitm to create an algorhitm to decide the factoring decision problem in polynomial time?
I'm reading Nielsen and Chuang. On page 142 the integer factoring decision problem is introduced: The integer factorization problem can be reduced to a decision problem:

Given a composite integer m and l \< m, does m have a non-trivial factor less than l?

For a given witness x \< l this problem can be checked in polynomial time. Now I'm asking myself why it should not be possible to use the algorithm for checking to construct a polynomial time algorithm to decide the decision problem. I'm thinking of something like this:

```
for x < l
  if check(x,l,m)
     return true
  else
     return false

```

This is basically just trying out all potential numbers of which there are at maximum m. So the time needed for this should be still linear because m times polynomial time (for the checking algorithm) should still be just polynomial I think.

I know something about this reasoning must be wrong but I'm completely stuck there.

# Answer
I think I found the solution by myself: It is called Pseudo-polynomial time - the time scales polynomial in the value of the number but not in the length.
> 1 votes

---
Tags: decision-problem
---


# Question
Title: Sampling from bins with ratio preservation
I have sequence of integers $a\_1, a\_2, .., a\_n$,
let $S\_a = \sum\_{i=1}^{N}{a\_i}$,
for any $k \in (0; 1)$ I need an algorthim to that maps every $a\_i$ into another integer $b\_i$ with 2 requirements:

1. $S\_b = \sum\_{i=1}^{N}{b\_i}$ is as close as possible to $k \cdot S\_a$, ideally $S\_b = Round(k \cdot S\_a)$
2. $b\_i$ is as close as possible to $k \cdot a\_i$, ideally $b\_i = Round(k \cdot a\_i)$

The first requirement is more important.

The problem can be formulated in simpler words as following:
How to generate a sample of a defined size from $N$ bins of different sizes while mantaining the original ratio of elements.

# Answer
> 3 votes
Compute the prefix sum of the $a\_i$, multiply all elements by $k$ and round. Now the desired integers are the pairwise differences of that sequence. The first condition is always honored.

E.g. $a=(3,6,2,7,9), k=0.8\to(3,9,11,18,27)\to(2,7,9,14,22)\to(2,5,2,5,8)$.

# Answer
> 0 votes
If $\sum\_{i=0}^{n-1}b\_i\>k\sum\_{i=0}^{n-1}a\_i$ then $b\_n = \lfloor ka\_n\rfloor$, else $b\_n = \lceil ka\_n \rceil$. This requires only one pass through $\\{a\_n\\}$.

---
Tags: algorithms, integers, sampling, rounding
---


title: Algorithm Asymptotic Analysis

text:
# Question
Title: Algorithm Asymptotic Analysis
I'm trying to solve this time complexity: $T(n) = 2T(n-2) + n$, but having some challenges addressing the $(-2)$ component. Any insights on this complexity?

Ended up with a section $\[2^2\cdot1 + 2^3\cdot2 + 2^4\cdot3 + \ldots + 2^{k+1}\cdot k$. Does it follow any existing number series?

# Answer
> 0 votes
**Hint:**

Set $n=2m$ and the recurrence turns to

$$T(2m)=2T(2(m-1))+2m$$ which can be written like a usual recurrence

$$S(m)=2S(m-1)+2m.$$

After solving for $S(m)$, you get $T(n)=S(\frac n2)$.

---

As the recurrence only involves numbers of the same parity, there are in fact two independent sequences, that correspond to the initial values $T(0)$ and $T(1)$.

---

The $S$ recurrence can be solved by variation of the constant, setting

$$S(m)=2^mR(m)$$ with implies

$$2^mR(m)=2^mR(m-1)+2m$$ or $$R(m)=R(m-1)+2m2^{-m}$$ which is solved by a mere summation.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: For a regular bipartite graph with vertices $X\cup Y$, prove that $|S|\leq|n(S)|$ $\forall S\subseteq X$
As the title states, we are given a bipartite undirected graph $G=(X\cup Y,E)$ such that every vertex $v\in V$ satisfies $d(v)=k$ for a constant $k$.

The general goal of the proof is to show that under these terms, the graph has a perfect matching (a subset of edges where all edges are disjoint in vertices, and the edges in said subset are reaching every vertex $v\in V$)

I wanted to use the proof of hall's marriage theorem, yet this requires that not only $|X|\leq |Y|$, but also that for every $S\subseteq X$, $|S|\leq |n(S)|$ where $n(S)$ is the group countaining neighbors of all vertices in $S$, which is the part I'm having a hard time proving.

I'm not sure how to explain that for every subset we choose $S\subseteq X$, the minimal size of $n(S)$ has to be $|S|$, which is due to the fact that every $v\in S$ has $k$ neighbors in $G$.

I've read about Konig's Theorem but I wasnt able to make the connection.

# Answer
Suppose $S\subseteq X$. Then $n(S)\subseteq Y$.

Consider all edges with one endpoint in $S$.

Since there are $k$ edges that start with any particular point in $S$ and all these edges are different for points in $S$, the number of those edges is $k|S|$.

Similarly, the number of all edges with one endpoint in $n(S)$ is $k|n(S)|$.

Since each edge with one endpoint in $S$ is also an edge with one endpoint in $n(S)$, we have $$ k|S|\le k|n(S)|,$$ which means $$ |S| \le |n(S)|.$$
> 2 votes

---
Tags: matching, bipartite-matching, bipartite-graph
---


title: find the minimization of the dfa

text:
# Question
Title: find the minimization of the dfa
so this is the question , I have to minimize this DFA

this is How I did it

but when I checked for answers , this is what it was,  can someone please explain to me what mistake I made? I have been wondering about this for past 2 days

# Answer
> 1 votes
None of these two automata is correct. The main reason is the following:

**You forgot the INITIAL STATE and the FINAL STATE.**

Please, don't forget to indicate those, this is a very common mistake, but without those, a correct automaton becomes an incorrect automaton.

Otherwise, the automaton seems correct, and the automaton in the "answer" is indeed not minimal. However, your method to find equivalences between states seems unclear (I doubt it would work for a bigger automaton).

Exercise: minimize the following automaton:

---
Tags: automata, finite-automata, compilers
---


# Question
Title: Why don't integer multiplication algorithms use lookup tables?
It seems to me that we can use lookup tables for multiplication of two integers of size $\log(n)/2$, and that the number of entries for each table of these numbers should be $O(n)$.

Now, multiplying two $n$-bit naturals together can be assisted by using an FFT of size $O(n / \log(n))$. It seems to me that we can then perform the multiplications and additions for the FFT using the lookup tables.

I'm wondering why this method doesn't or hasn't seemed to get any attention. Is it because of memory bandwidth problems?

It just seems to me that using tables would be quicker, so I'm hoping that someone can provide me with a better intuition.

# Answer
> 4 votes
Some integer multiplication algorithms do use lookup tables.

The IBM 1620 Model I "CADET" lacked a conventional ALU: addition and subtraction used a 100 digit table; multiplication used a 200 digit table. (Many joked that CADET stood for "Can't Add, Doesn't Even Try").

The IBM 1620 Model II had a simple ALU for addition and subtraction, but still used the same 200 digit table for multiplication.

While one might think that multiplying two 8-bit numbers together would require a table of 2^16 = 65,536 values, the "quarter square multiplication" technique uses a much smaller table of 510 values. Using such table-lookups is apparently the fastest way to multiply two arbitrary 8-bit numbers on the 6502 and Microchip PIC and other simple processors. Surprisingly, the quarter-square multiplication technique on the 8086 and 8088 is faster than the built-in multiply instruction when multiplying two arbitrary 8-bit numbers.

More expensive processors often include a larger, more complex ALU that multiplies "small" numbers in fewer CPU cycles than the 8086. While memory speeds have improved over the years, processor speeds have far outpaced memory speeds, and so recent high-end processors can generally multiply "small" numbers in much less time than a single main-memory memory cycle.

# Answer
> 5 votes
If you want to use lookup tables, and you have 4GB of memory, you'll only be able to use a lookup table with about $2^{32}$ entries or fewer, so you'll only be able to handle multiplication of numbers that are at most 16 bits long. If you want to multiply larger numbers, you won't be able to use lookup tables for multiplication. Typically we want to multiply numbers that are larger than that. And when we do want to multiply small numbers, using the CPU's built-in multiply instruction is usually faster than using a lookup table.

So there is no size (that I'm aware of) where a lookup table is a good solution for multiplying two numbers.

Now you're thinking that maybe the numbers that are generated by FFT should be multiplied with lookup tables. But those are just numbers, and as I said above, there is pretty much no situation where the fastest way to multiply two numbers is with a lookup table. It doesn't matter how those numbers were generated -- whether by FFT or by any other process.

So I'd say the reason it doesn't have more attention is because it doesn't deserve attention; it seems unlikely to be faster or better than existing schemes.

---

Lookup tables *are* occasionally used in cryptographic code, where constant-time access is needed. This is not because they are faster -- they're not; they're slower -- but because they have other properties that are beneficial. I don't know of any specific examples, but it wouldn't surprise me to discover that someone had used a lookup table for multiplication in some constant-time cryptographic code.

# Answer
> 0 votes
A lookup table for integer entries up to $n$ has size $O(n^2\log n)$. For $b$ bits numbers, this is $O(b\\,2^{2b})$.

FFT's are usually implemented with double precision floating-point arithmetic. With proper scaling, fixed-point and sacrificing a lot of accuracy, you might do with $b=20$ or so ($50$ Gb)...

---
Tags: algorithms, algorithm-analysis, memory-access, multiplication, intuition
---


# Question
Title: find the shortest path between two vertices with Dijkstra (Increase and deacrese wieght one by one)
We have a weighted and undirected graph. I want to find the shortest path between two vertices with Dijkstra algorithm. But in the path, the weight of the edges should be increased and decreased one by one. For example, in the below graph, the answer is the third path:

My idea: Remove the paths that do not meet the condition of the problem and then find the shortest paths with Dijkstra. But I don't know how to remove a path from Dijkstra's check without removing that edge (because one edge may participate in several paths) Or is there a better way for this problem?

# Answer
If I understand you correctly, it seems like the solution is to simply skip the frontier nodes that does not conform to the condition you have described.

> My idea: Remove the paths that do not meet the condition of the problem and then find the shortest paths with Dijkstra

I think you're on the right direction. To be more concrete, if you have a frontier node $n$, with parent node $x$ and child node $y$, and the cost function $C(a, b)$ denotes the cost of the path between nodes $a$ and $b$, and if $i$ represents the depth of node $n$, then you should remove node $n$ if

$$ \begin{array}{c l} C(x, n) \<= C(n, y) & \quad \textrm{if } i \textrm{ is odd} \\ C(x, n) \>= C(n, y) & \quad \textrm{otherwise} \end{array} $$

You may want to think about the scenario if the pattern starts with a *decrease* from the starting node to its child node, instead of an *increase* like the examples shown in your question. Think also about the edge cases: what if $n$ is the root node? How do you take that into account for the cost function $C$?
> 1 votes

---
Tags: graphs, shortest-path, weighted-graphs, dijkstras-algorithm
---


# Question
Title: How can dfa have more than one sink state? Isn’t it the same state?
I can’t understand How can dfa have more than one sink state? Isn’t it the same state? Maybe there is some examples

# Answer
> 1 votes
Consider the following automaton.

There are two sink states: $q\_3$ and $q\_4$. Of course, any automaton with multiple sink states is equivalent to an automaton with at most one sink state, and even to an automaton without any sink state if the automaton is not complete.

---
Tags: formal-languages, formal-grammars
---


# Question
Title: What Exactly Does the Term "Key" Mean with Regards to a Hash Table?
I know it is supposed to be some arbitrary term that is a stand-in for a large class of possible objects.

But I still don't understand what part of the array the term "key" is meant to represent or denote.

Does it mean an element of the array? The index of the element of the array? Some arbitrary function from the elements of the array to some subset of the natural numbers?

**EDIT:** Since many people seem not to understand the question, here is a quote from *Introduction to Algorithms* by Cormen et al.

> "With direct addressing, an element with key $k$ is stored in slot $k$. With hashing, this element is stored in slot $h(k)$; that is, we use a hash function to compute the slot from key $k$. Here $h$ maps the universe $U$ of keys into the slots of a hash table $T$... We also say that $h(k)$ is the hash value of key $k$."

It seems to me that the key, element index, and hash value are all different based on this.

Here is where the term is introduced in the chapter for the first time in a formal manner:

> "Suppose that an application needs a dynamic set in which each element has a key drawn from the universe $U=\\{0,1,\dots,m-1\\}$, where $m$ is not too large. We shall assume that no two elements have the same key."

From this I would draw the conclusion that a universe of keys cannot exist for a multiset of integers which allows duplicate values, since the former is a finite set which is in bijection with all possible elements of the array (implying that the set of all possible elements of the array is finite), whereas the latter has no bound on its cardinality (since it can increase in size with every operation, hence the "dynamic", and there is no bound to the number of elements which can be added because (1) duplicate elements are allowed and (2) the number of possible integers is infinite).

**Context:**

For instance, when discussing the "pth-smallest key" algorithm, you want to find the "key" with the pth-smallest "rank" -- so the "rank" is different from the "key", and you want to sort the "ranks" of the "keys", but usually the "keys" are numbers too, so why not sort them? And why would there be a "rank", a "key", a "hash value", an array element, and an array element index?

As another example of where seemingly imprecise terminology is confusing me, consider a dynamic multiset $S$ of integers which allows duplicate values. Would this object allow a hash function? If it would, what would be the "keys", and what would be the "hash values"? Both the universe of keys and the target space for the hash function are supposed to be finite, whereas $|S|$, the cardinality of $S$, is clearly potentially unbounded, and in fact any integer can appear arbitrarily many times -- so how could anything associated with this problem be a "key"?

It is seemingly similar to other problems that admit hash functions.

# Answer
> 0 votes
Their difference is the role that they have in the ordering and addressing of the table. The **key** is used to address a specific object (it's usually calculated using some algorithm or hashing function), while the **rank** is used to order objects and their respective keys using a specific ranking rule.

# Answer
> 4 votes
A hash table is an implementation of a more general principle: A key/value table. In a key/value table you can insert values according to a key, you cannot add two values under the same key. You can lookup a value based on the key, or delete it based on the key.

Very often the key can be anything that is "equatable" (that is you can take two keys and say if they are equal, with the properties that a = a, a = b implies b = a, and a = b plus b = c implies a = c), and preferable is "hashable" (that is you can calculate an integer hash value for each key with the property that hash(a) doesn't change during one run of your program, and a = b implies hash(a) = hash(b)).

# Answer
> 3 votes
A set is an abstract data type that stores "elements" such as integers, strings, points, or whatever. The elements must be unique and are stored in an unspecified order. Those elements are called the "keys".

A dictionary is like a set, but a value is associated to each key.

A set or a dictionary can be implemented by means of an array and a hashing function. The array slots are accessed by means of the hash, which is an integer computed from the key by some suitable rule. You lookup a key (to check its presence in the set or retrieve the associated value) by computing the hash and indexing the array with that number\*.

As sets are unordered, the rank plays no role.

\*This is a slightly simplified description: it turns out that two different keys may hash to the same index, and this needs to be somehow arbitrated.

# Answer
> 1 votes
You can say that a KEY is always unique or one to one mapping, corresponding to a certain element, while HASH function is not always one to one. HASH takes KEY as its input and different KEY may have same HASH value

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


title: Constant value NP-complete vs W[1]-hard

text:
# Question
Title: Constant value NP-complete vs W[1]-hard
I am a research scholar currently working in parameterized algorithms. I am studying the complexity of a problem (say $P$) for $\Delta\_{10}$ graphs and was able to provide a reduction from a known NP-complete problem. Hence, i have that $P$ is NP-complete on $\Delta\_{10}$ graphs. It is obvious that there is no FPT (fixed-parameter tractable) algorithm for the problem w.r.t. the parameter maximum degree. My question is, can I say that since the problem is NP-complete for constant maximum degree graphs, it is also W\[1\]-hard for the parameter maximum degree?

# Answer
> 3 votes
By definition, a parametrized reduction from a parametrized problem $A$ to $B$ needs to satisfy the following properties:

1. The reduction maps each instance $(x,k)$ of $A$ is mapped to some instance $(x',k')$ of $B$ such that $(x,k)$ is true if and only if $(x',k')$ is true.
2. The parameter $k'$ obtained after the reduction needs to be bounded by a function of $k$.
3. The reduction takes at most $f(k)\cdot|x|^{O(1)}$ time, for some computable function $f$.

A polynomial time reduction from $A'$ to $B'$ already satisfies property 1 and 3 if we add an arbitrary parameter to these problems. If we add a parameter $p$ to $B'$ such that $p\leq C$ on all instances for some constant $C$, then property 2 is also satisfied. So, there is a parametrized reduction from $A'$ with any parameter to $B'$ with a "bounded parameter".

Now take an NP-hard problem $X$ and a parameter $p$ that is bounded by a constant on all instances of $X$. There is a polynomial time reduction from CLIQUE to $X$, because $X$ is NP-hard and CLIQUE is in NP. By the argument above, there is a parametrized reduction from $k$-CLIQUE to $X$, so $X$ is W\[1\]-hard.

---

Now, to answer your question, yes, problems that are NP-hard become W\[1\]-hard if you add a parameter that is bounded by a constant on all inputs. However, the fact that your problem "$P$ for $\Delta\_{10}$ graphs" becomes W\[1\]-hard after adding a bounded parameter is not a insightful property of your particular problem, precisely because this is true for any NP-hard problem.

In fact, a way to interpret the fact that some problem is W\[1\]-hard for some parameter is that we expect the additional assumption that this parameter is small will not help us to construct a polynomial time algorithm. If the parameter chosen is already guaranteed to be small in the problem, then assuming it is small a second time does not help!

---
Tags: np-hard, parameterized-complexity
---


# Question
Title: I'm looking for an algorithm to find all subsets of a set S with subset sums between a given min and max
Given a set S of numbers, min and max. Find all sebsets of numbers from S with a subset sum larger or equal to min and smaller or equal to max. The following article says that there's an algorithm called ESS that solves this but I haven't been able to find the algorithm anywhere: "Cached Iterative Weakening for Optimal Multi-Way Number Partitioning" https://ojs.aaai.org/index.php/AAAI/article/view/9122/8981

# Answer
For arbitrary min and max the problem is weakly NP-complete. Let min=max=W and the answer is "at least one" if and only if the original instance is a yes instance.

In any case, solve the problem using dynamic programming and count the number of solutions for each number in \[min, max\].

While actually outputting all sets will most surely take exponential time, you can count them much faster.
> 1 votes

---
Tags: algorithms, subset-sum
---


# Question
Title: Why can't we just compose PRGs to get better PRGs?
I'm learning about (complexity-theoretic) pseudorandom number generators, and I have a pretty basic question about them that I couldn't find an answer to.

Let's say we have a PRG for $P$ that can fool any algorithm running over $n$ bits in time $poly(n)$ with seed length $O(\log^{10}(n))$. This would already be a breakthrough, as it would imply $BPP$ can be decided in deterministic polylog time. But why stop there? Now, every algorithm in $BPP$ only needs $O(\log^{10}(n))$ truly random bits -- why not just use our existing PRG again, so that we only need $O(\log^{10}(O(\log^{10}(n)))) = O(\log\log(n)^{10}) \subset o(\log(n))$ bits, and then $P = BPP$? (I'm not seriously suggesting this is possible; I'm trying to understand the flaw in the reasoning.)

One immediate concern is that if we use $o(\log(n))$ random bits at the end, the distinguisher could just memorize the correct words. But is that the only obstacle? Does that mean if we had a PRG with a "half-logarithmic" seed length, we could do the above strategy?

In general, why can't we just compose PRGs to get arbitrarily better PRGs?

# Answer
> 1 votes
Short answer: you can enumerate all possible seeds of length $O(\log^{10}(\log^{10}(n)))$ in $\text{poly}(\log n)$ time, so such a PRG cannot possible be secure against algorithms whose running time is polynomial in $\log n$, so such a PRG tells us nothing about BPP.

Slightly longer answer: Each PRG comes with a security level, a class of adversaries it is secure against. That class is specified as the set of adversaries whose running time is upper-bounded by some quantity -- the security level. Composition does not increase the security level. So at least in that sense, composition doesn't give us "better" PRGs.

Longer answer: a PRG is a family of functions that are associated with three quantities, the input length, the output length, and an upper bound on the adversary's running time. Typically, each of these may be a function of $n$. The guarantee is that the PRG will be secure against all adversaries whose running time is upper-bounded by the corresponding value. So, to make your argument more concrete, work out what are those values (especially, check out how the security level -- the upper bound on adversary running time -- of the composition of two PRGs depends on the security level of the underlying PRGs), and work out what they need to be for your claim about implications for BPP to hold, and you'll probably spot the issue.

---
Tags: randomized-algorithms, pseudo-random-generators
---


# Question
Title: In Context free languages, is it okay to substitute multiple same variables at the same time?
Let's say we have the following context free grammar:

$S \rightarrow a \\ S \rightarrow SS$

And we do the following two "derivations" for the same string:

aaa: $S \rightarrow SS \rightarrow SSS \rightarrow aaa$

aaa: $S \rightarrow SS \rightarrow SSS \rightarrow aSS \rightarrow aaS \rightarrow aaa$

The difference between the two derivation is that: in first derivation we just replaced multiple same variables at once, whilst in the second derivation we replaced multiple same variables one by one

Are these two different derivations? or just one derivation? Because their parse trees would look different. Which one should i stick to?

# Answer
It is possible, though it is often denoted with a $^\*$ to indicate that there is a sequence of replacement instead of just one replacement:

$$S\Rightarrow SS \Rightarrow SSS \Rightarrow^\* aaa$$

Note that I am using a $\Rightarrow$ symbol instead of a $\to$ one to distinguish derivations of strings from production rules.

Sure, parse trees could look different, but that is also the case when doing one replacement at a time: in your second derivation, the replacement $SS\Rightarrow SSS$ could be interpreted as "the first $S$ is replaced with $SS$" or as "the second $S$ is replaced with $SS$". This would lead to two different parse trees.

One can lift ambiguity of derivation (but not necessarily ambiguity of grammar) by considering only leftmost or rightmost derivations.
> 1 votes

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


# Question
Title: Generating parse trees when only a recognizer is given
I am trying to understand "On the complexity of general context-free language parsing and recognition" by Walter L. Ruzzo. One of the results from the paper is about generating a parse tree when only a (blackbox) recognizer is given. Unfortunately, I am stuck at the sentence "Given recognizers for these languages, we can implement the "divide and conquer" parsing strategy outlined above." from the paper (p 491).

The question is, where do these recognizers (that the paper mentions in that sentence) suddenly come from? Given the rather succinct explanation in the paper, I am also finding it difficult to form an intuition about how this algorithm works. What is required out of the blackbox recognizer to derive a parse tree using this algorithm? Do I need to keep information about which nonterminals recognize which parts of the input? (Given that multiple grammars can recognize the same language, this seems like a requirement, but the paper doesn't seem to say so) If not, how does this work?

Editing to provide additional context: The confusing aspect of this paper is its claim: "We will show how to construct from any recognizer a parser which is only about $log n$ times slower than the recognizer (on strings of length $n$)." A recognizer is an oracle that tells you whether a particular input is in the language or not. Given such a recognizer, and assuming the grammar is given, there is no mention in the paper anywhere about constructing additional recognizers for substrings of the language. Without such additional recognizers, I am not clear how the parse tree construction works in this algorithm.

My reference for background research as requested by D.W: Dick Grune and Ceriel J. H. Jacobs. Parsing Techniques: A Practical Guide (Second Edition). Springer, 2008.

# Answer
> 0 votes
A recognizer is any algorithm that, given a context-free grammar $G$ and a word $x \in \Sigma^\*$, tests whether $x \in L(G)$. There are standard algorithms to do that, e.g., Earley parsers or CYK parser.

The paper appears to essentially be saying: "given *any* recognizer (I don't care where you got it from), we can extend it to also provide the functionality of parsing".

---
Tags: context-free, parsers
---


# Question
Title: Dropping terms in proving the runtime for a recurrence?
I am trying to learn how to prove the runtime of a recurrence relation, particularly through induction. I was looking at this lecture PDF, and on the first page, the author writes this:

> **Recurrence:** $T(1)=1$ and $T(n)=2 T(\lfloor n / 2\rfloor)+n$ for $n\>1$. We guess that the solution is $T(n)=O(n \log n)$. So we must prove that $T(n) \leq c n \log n$ for some constant $c$. (We will get to $n\_0$ later, but for now let's try to prove the statement for all $n \geq 1$.)
>
> As our inductive hypothesis, we assume $T(n) \leq c n \log n$ for all positive numbers less than $n$. Therefore, $T(\lfloor n / 2\rfloor) \leq c\lfloor n / 2\rfloor \log (\lfloor n / 2\rfloor))$, and
>
> $$ \begin{aligned} T(n) & \leq 2(c\lfloor n / 2\rfloor \log (\lfloor n / 2\rfloor))+n \\ & \leq c n \log (n / 2)+n \\ & =c n \log n-c n \log 2+n \\ & =c n \log n-c n+n \\ & \leq c n \log n \quad(\text { for } c \geq 1) \end{aligned} $$

I have two questions:

1. In the last step, the author omits the $-cn$ and $n$ terms, and I *think* they did this because setting a bound for $c$ makes these terms irrelevant. Is this correct? If so, I was hoping someone could spell out why these terms can be removed :).
2. Could something similar be done for proving $\Theta(\cdot)$ (i.e. a lower and upper bound)?

# Answer
> 1 votes
1. In the last step, there is an inequality. Since it is assumed that $c\geqslant 1$, then $-cn + n = (1 - c) n \leqslant 0$, so the inequality is correct, it is not a matter of irrelevance or not.
2. For $\Theta$, it would be better to prove two different inequalities by induction, with different coefficients (however, the proof could be similar).

# Answer
> 0 votes
For 1. (though Nathaniel answered for the case in question) generally, in $f(n)+g(n)$ where $g(n)=o(f(n))$, you can drop the term $g(x)$ because it becomes negligible.

$$f(n)+g(n)=f(n)\left(1+\frac{g(n)}{f(n)}\right)=f(n)(1+\epsilon(n))$$ where the function $\epsilon$ tends to zero and the factor on the right can be bounded by a constant.

---
Tags: runtime-analysis, recurrence-relation, induction
---


title: What is the lower bound of n factorial

text:
# Question
Title: What is the lower bound of n factorial
The upper bound of $n!$ is $O(n^n)$. But I am not getting a way to compute the lower bound of n!.

We can write $n! = n\times(n-1)\times(n-2)\times\dots\times 1$. I can easily put all the terms as 1. The lower bound will be $\Omega(1)$. But I am not convinced with this answer.

# Answer
There is no "the" upper/lower bound. There are as many upper/lower bounds as you want. For instance, $n!=\Omega(1), n!=\Omega(n), n!=\Omega(n^{27}), n!=\Omega(10^n)$ are all true.

What you are probably after is a tight bound. As said by Nathaniel, $\Omega(n^{n+1/2}e^{-n})$ is tight, because the ratio tends to a constant. But $\Omega(25n^{n+1/2}e^{-n}+n^{n/3}\cos(n^2))$ and $\Omega(\Gamma(n+\frac12))$ are tight bounds as well.

---

By simple means, you can establish the following bracketing:

From

$$x-1\le\lfloor x\rfloor\le x$$ you deduce $$\log(x-1)\le \log(\lfloor x\rfloor)\le\log(x).$$ Then by integration,

$$\int\_2^{n+1}\log(x-1)\\,dx\le \int\_2^{n+1}\log(\lfloor x\rfloor)\\,dx=\sum\_{k=2}^n\log(k)\le\int\_2^{n+1}\log(x)\\,dx.$$

So

$$n(\log(n)-1)+1\le\log(n!)\le(n+1)(\log(n+1)-1)-(2\log(2)-2)$$

or

$$e\left(\frac ne\right)^n\le n!\le \frac{e^2}4\left(\frac{n+1}e\right)^{n+1}.$$

Not as tight as Stirling, but decent.
> 3 votes

# Answer
Stirling's approximation says that $$n! \sim \left(\frac{n}{e}\right)^n\sqrt{2\pi n}$$

That means that $n!\in \Theta\left(\left(\frac{n}{e}\right)^n\sqrt{n}\right)$ (this is a lower and upper bound).
> 2 votes

# Answer
You can look up Stirling's formula. If you want lower bounds that are much less good but mathematically very easy:

1. n! is the product of n numbers. All but $\sqrt n$ of them are greater than $\sqrt n$, so n! \> $(\sqrt n)^{n - \sqrt n}$ which is $n^{n/2 - \sqrt n/2}$.
2. n! is the product of n numbers. Half are less than n/2, and half are from n/2 to n. So you immediately get a lower bound $(n/2)^{n/2}$ and an upper bound $(n/2)^{n/2} \cdot n^{n/2}$.
3. You can split the numbers n into 4, 10 or 100 intervals instead of 2 and get better lower and upper bounds.
> 2 votes

# Answer
It is well known that $log(n!) =\Theta(n\log(n))$. Therefore, $\exists c\in \mathbb{R}^+, 0\<c\le 1$ such that:

$$log(n!)\ge cn\log(n)$$ For large enough values of $n$.

Because $e^x$ is monotonically increasing, we can order this a bit around, and get:

$$n!\ge e^{cn\log(n)}=\left(e^{\log(n)}\right)^{cn}=n^{cn}$$

Which gives a certain lower bound that depends on an unknown constant (but it is known to exist) and applies only for large enough values of $n$ (i.e, there is some $n\_0$ for which the statement holds for all $n$ bigger than it)
> 1 votes

---
Tags: algorithms, complexity-theory, asymptotics, big-o-notation
---


# Question
Title: How to define soundness and completeness of a transformation algorithm?
My algorithm takes a Java program as an input, modifies it to *eliminate* static attributes, and returns a new modified Java program without such attributes. What would be the soundness and completeness of this algorithm? Let's assume, the input program has $S$ static attributes and $N$ non-static ones. Let's also assume that the output program has $S'$ and $N'$ accordingly. I'm guessing, the completeness is $N'/(N+S)$, but I'm not sure about soundness.

# Answer
I ended up with the following. First, it's necessary to define what is "false positive" (FP) and "false negative" (FN) of the algorithm. Let's say, a static method that is not eliminated is a "false negative" result ("negative" because the algorithm said "There is NO static method to eliminate"). Then, if a non-static method is modified, it is a "false positive" outcome.

Then, the *precision* of the algorithm is `TP / (TP + FP)` and the *recall* is `TP / (TP + FN)`.

If we prove that the algorithm is *sound* (no false positives), its precision will always be 100%. If we prove that it's *complete* (no false negatives), the recall will always be 100%.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Is it possible to transmit bits digitally?
I have learnt that all data transmission is analog. Is there any mediums that could transmit bits digitally?

# Answer
Would you accept punched cards as carrying digital digits ?
> 1 votes

# Answer
HDMI interface is one example of being able to tranmit high-speed digital data. It works using an encoding technique called TMDS (Transition Minimized Differential Signaling) which you can read more about here

Also, HDMI can only be used with older analog-only devices (using connections such as VGA, etc.) by means of a digital-to-analog converter or AV receiver, as the interface does not carry any analog signals from Wikipedia
> 0 votes

# Answer
Yes, modern optical fibers are good enough for single-photon communication. This is essential when it comes to quantum cryptography, which works with photon pairs. These quantum systems are inherently digital; the photon polarization encodes a single bit.
> 0 votes

---
Tags: computer-architecture, computer-networks
---


# Question
Title: Generate a minimum number of clauses in 3-CNF form that give a unique solution
Suppose I would like to generate n clauses, in 3-CNF form, that would give a unique solution for m variables (m\<n). Example: for m=6, I've got **{a,b,c,d,e,f} = 111010**

How to generate these n 3-CNF clauses while minimizing this number of clauses (to avoid redundancies)? What would be the minimum number of clauses to generate ?

More precisely: I'm trying to find a boolean formula in 3-CNF with a minimal number of clauses that is satisfied only by the truth assignment.

# Answer
> 1 votes
Since the question has been clarified (by my comment) and its content is quite different than its initial formulation, I am posting a new answer.

Assume $\mathcal{V} = \\{x\_1, x\_2, …, x\_n\\}$ is a set of variables and $\mu \in \\{0,1\\}^{\mathcal{V}}$ is a truth assignment. For $i\in \\{1, …, n\\}$, consider $\mu\_i$ to be the restriction of $\mu$ to the $i$ first variables $\\{x\_1, …, x\_i\\}$. For $i\in \\{1, …, n\\}$, denote $\ell\_i$ the litteral of variable $x\_i$ that is satisfied by $\mu$ (meaning if $\mu(x\_1) = 1$, then $\ell\_1 = x\_1$, if $\mu(x\_4) = 0$, then $\ell\_4 = \neg x\_4$). Depending on what you call a clause, the solution could be different.

* If a clause can contain only one litteral, then the formula $\varphi = (\ell\_1)\land (\ell\_2) \land … \land (\ell\_n)$ is in 3-CNF and is satisfied only by $\mu$. It contains exactly $n$ clauses.
* If a clause must contain 3 litterals, but can contain the same litteral multiple times, then the formula: $$\varphi = (\ell\_1\lor \ell\_1 \lor \ell\_1)\land (\ell\_2\lor \ell\_2 \lor \ell\_2) \land … \land (\ell\_n\lor \ell\_n \lor \ell\_n)$$ is again in 3-CNF and satisfied only by $\mu$, and still contains $n$ clauses.
* If $n\geqslant 3$ and a clause must contain 3 litterals with different variables, one can construct a formula by induction on $n$:
    + if $n=3$, then the formula: $$\varphi\_3 = (\ell\_1\lor \ell\_2\lor \ell\_3)\land (\ell\_1 \lor \ell\_2 \lor \neg \ell\_3)\land (\ell\_1\lor \neg\ell\_2\lor \ell\_3)\land(\neg\ell\_1\lor \ell\_2\lor \ell\_3)\land(\ell\_1\lor \neg\ell\_2\lor \neg\ell\_3)\land(\neg\ell\_1\lor \ell\_2\lor \neg\ell\_3)\land(\neg\ell\_1\lor \neg\ell\_2\lor \ell\_3)$$ (all possible clauses except $\neg\ell\_1\lor \neg\ell\_2\lor \neg\ell\_3$) is in 3-CNF and satisfied only by $\mu$. It is of minimal size in that aspect (otherwise another truth assignment could satisfy $\varphi$).
    + if $n\geqslant 3$, then consider $\varphi\_{n-1}$ a formula that is satisfied by $\mu\_{n-1}$ ($\mu$ restricted to the first $n-1$ variables) and no other truth assignment over $\\{x\_1, …, x\_{n-1}\\}$. The formula: $$\varphi\_n = \varphi\_{n-1} \land (\neg \ell\_1 \lor \neg \ell\_2 \lor \ell\_n)$$ is in 3-CNF and satisfied only by $\mu$. It contains exactly $n+4$ clauses.

    Now assume that there exists $i\>3$ and a formula $\psi$ satisfied only by $\mu\_i$ with $i+3$ clauses or less. Consider such a $i$ minimal.

    Since $\psi$ is not satisfied when swapping the truth value of $x\_i$, that means that $\psi$ contains a clause $C = a\lor b \lor \ell\_i$, and $\mu(a) = \mu(b) = 0$.

    Now consider $\sigma$ obtained from $\psi$ by: \- deleting the clause $C$; \- in each other clause, replacing $\ell\_i$ with any $\ell\_j$ such that $j \< i$, and replacing $\neg \ell\_i$ with any $\neg \ell\_j$ such that $j\<i$, in each case with $j$ corresponding to a variable not already in the clause (possible given that $i \> 3$).

    Then $\sigma$ must be satisfied only by $\mu\_{i-1}$ but contains $(i-1) +3$ clauses or less, which contradicts the choice of $i$. By contradiction, we conclude that this construction is indeed minimal in the number of clauses.

# Answer
> 1 votes
For simplicity, I assume that such a clause contains exactly $3$ litterals, and that those litterals are on different variables.

To create such a clause, you can do the following:

* choose the $3$ variables that appear in the clause. There are $\binom{m}3$ such choices;
* there are $2^3=8$ possibilities to create a clause with $3$ variables (each litteral can be positive, some variable $x$, or negative, the negation of a variable $\neg x$). Among those $8$ possibilities, only one create a clause that is not satisfied by the truth assignment (the only one where each litteral is negated by the truth assignment).

That means that there is a total of $7\binom{m}3$ different clauses. If $n$ is smaller than that, it is possible to generate $n$ different clauses.

---
Tags: 3-sat
---


# Question
Title: On the logical and categorical interpretation of lambda calculi and type systems
There is a well-known Curry-Howard-Lambek correspondence between certain type systems, proof calculi and categories.

Some variants of Barendregt's pure type systems have the property of strong normalization, i.e. any term can be reduced to a normal form after a finite number of reduction steps, the other of them don't have this property, system U, for example.

My questions are:

1. In a pure untyped lambda calculus, the ability to construct terms like infinite loop term (\x -\> x x) (\x -\> x x) or the fixed-point combinator \f -\> (\x -\> f (x x)) (\x -\> f (x x)) entail Curry's paradox (P: P -\> Q) or, informally, "if this sentence is true, then Voldemort exists", which leads to the system being able to prove anything. In some pure type systems it's possible to construct such terms even if the system isn't self-referential (as mentioned above, system U is such an example). Does the inconsistency of the logical calculus always correspond to the nontermination of the type system and vice versa?
2. Wikipedia says that the inconsistency of the type system as a proof calculus follows from the impossibility of constructing an uninhabited (empty, or void) type in it. Does it have anything to do with nontermination? If so, how exactly does nontermination lead to the inhabitation of all types, is it not possible to define an empty type axiomatically?
3. It's possible to add some kind of recursion to the calculus of constructions in such a way that it remains strongly normalizing (in which case it's called the "calculus of inductive constructions", for example, it can define natural numbers as Nat: 0 | S Nat). How do these two kinds of recursions differ, if one of them does not make the proof-calculus inconsistent, unlike the other? (Maybe it's primitive and general recursion???)

# Answer
> 2 votes
(My answer is only about how non-termination relates to inconsistency.)

The general idea of the Curry-Howard correspondence is that a term having a type, corresponds to a proof for a theorem. A term is an instruction on how to build a proof. A non-terminating term (i.e. a term that does not have a value) does not actually allow constructing a proof of the theorem. If a type has non-terminating terms but no value, it does not correspond to a proven theorem.

A type containing only non-terminating terms corresponds to a theorem for which searching for a proof never actually finds a proof.

> Does the inconsistency of the logical calculus always correspond to the nontermination of the type system and vice versa?

Not necessarily, but it usually is.

The only counter-examples I can think of without research are “silly”. For example:

* Suppose non-termination is only allowed for terms that have certain known non-empty types. In other words, somehow, the typing rules ensure that if a type has non-terminating terms, it also has terminating terms. (This “somehow” restricts the compositionality of typing a lot.) Then the existence of these non-terminating terms doesn't affects which theorems are provable, so it doesn't make the type system inconsistent.
* There are other ways to make a type system inconsistent. You can just take `False` as an axiom, or $\forall P, P \wedge \neg P$. But that makes the type system useless. (Useless for the purpose of doing logic — it might be perfectly fine for doing programming.)

> inconsistency of the type system as a proof calculus follows from the impossibility of constructing an uninhabited (empty, or void) type in it. Does it have anything to do with nontermination?

I mostly answered that above at the beginning of my post. If a type only has nonterminating terms, it has no *values*, and thus the corresponding theorem is not guaranteed to have a proof. The set-theoretic denotation of a type is as the set of its values, thus “empty type” means a type with no values unless explicitly defined otherwise.

> If so, how exactly does nontermination lead to the inhabitation of all types, is it not possible to define an empty type axiomatically?

If you can make a non-terminating function $f$ of type $A \to B$, and you can construct a term $a$ of type $A$, then $f(a)$ has the type $B$, so $B$ is inhabited. In particular, if there is a generic fixpoint combinator, you can build a non-terminating function of type $A \to B$ for all types $A$ and $B$, thus (assuming the existence of at least one term of one type) all types are inhabited.

It is possible to define an empty type. For example, in Coq, the `False` type is defined as

```
Inductive False : Prop :=  .

```

That is, `False` is a proposition (which is a kind of type in Coq) for which there are zero ways of constructing a term (except by adding extra axioms — and any axiom that allows constructing a value of type `False` would make the system inconsistent).

> How do these two kinds of recursions differ, if one of them does not make the proof-calculus inconsistent, unlike the other? (Maybe it's primitive and general recursion???)

It's possible to have some recursion, but there has to be limits. The general idea is that a recursive call must be made to a *smaller* value. For example, a function defined recursively on the natural numbers is only allowed to call itself on smaller numbers. More generally, the usual mathematical tool is a well-order: a function that calls itself recursively (directly or indirectly) must only call itself on values that are smaller in some well-order. The well-ordering property guarantees that the recursive call will terminate. In the calculus of inductive constructions, the well-order on terms is based on needing fewer constructors to construct the value.

---
Tags: lambda-calculus, type-theory, category-theory, curry-howard
---


# Question
Title: Implementation details of "transitions" of Non-deterministic push-down automata
I am reading "Introduction to the Theory of Computation" 3rd edition ~ by Michael Sipser, page 113-114 - topic: "Context free languages, push down automata"

He states that the transition from one state to another would look as follows: "$a,b\rightarrow c$". But the way he states the usage confuses me

> We write "$a,b \rightarrow c$" to signify that when the machine is reading an $a$ from the input, it may replace the symbol $b$ on the top of the stack with a $c$. Any of $a,b \ and \ c"$ may be $ε$
>
> If $a$ is $ε$, the machine may make this transition without reading any symbol from the input
>
> If $b$ is $ε$, the machine may make this transition without reading and popping any symbol from the stack
>
> If $c$ is $ε$, the machine does not write any symbol on the stack when going along this transition

My question is what would happen in the following cases:

1. When $b$ is $ε$, and $c$ is $ε$
2. When $b$ is $ε$ and $c$ contains a symbol
3. When $b$ contains a symbol and $c$ is $ε$
4. When $b$ contains a symbol and $c$ contains a symbol, where both symbols are different
5. When $b$ contains a symbol and $c$ contains a symbol, where both symbols are same

My understanding is as follows: if $b$ is $ε$ then we "push" a symbol on stack, if $c$ is empty then we "pop" a symbol from the stack and when he says $a,b \rightarrow c$ he means, given $b$ is not $ε$, "if" $b$ is the top symbol of the stack then we can either pop or replace, and my answers to the above questions are as follows:

1. Push operation: Push empty string on stack, meaning make no changes to the stack ( not sure about this one because both $b$ and $c$ are $ε$ so it could be a push + pop operation??, clarify please this especially )
2. Push operation: Push the symbol $c$
3. Pop operation: Pop the top symbol $b$ from the stack
4. Replace operation: Replace the top symbol that is $b$ with $c$
5. Replace operation: Replace the top symbol that is $b$ with $c$, in this case the stack will remain the same

# Answer
Kindly read again the description you have quoted from the book. It states there that $b$ is the stack element to be read and popped and $c$ would be the symbol to be pushed on top of the stack. So to answer your questions:

1. Nothing will be popped and pushed
2. Nothing will be popped but $c$ will be pushed
3. Pop the stack and push nothing
4. Pop the stack and push $c$
5. Same as 4, as it doesn't matter if you pop and push the same symbol. You can think of this as the PDA inspecting (by popping) the top symbol and decided that this symbol is not yet meant to be popped in the current state, so it simply returned the popped symbol.
> 2 votes

# Answer
The standard/usual/common definition of a push-down automaton allows instructions of the form $(p,a,A,q,\alpha)$ meaning in state $p$ reading $a$ from the input and $A$ on top of the stack, we move to state $q$ and replace $A$ by $\alpha$ on the stack.
Thus, we always combine both a pop $A$ and a push $\alpha$.

There are some special cases.

* The input read can be $a=\varepsilon$, meaning that the input is ignored. The transition can take place whatever is on the input tape.
* We may push $\alpha=\varepsilon$, which means that only top $A$ is popped without replacement, so that is a "pure" pop.
* We may push $\alpha = A$: the symbol on top is returned, and we have only verified that the topmost symbol is indeed $A$.
* If we want to push a string $\gamma$ "on top of" the current $A$ we have to push $A\gamma$ to first return $A$ on the stack.

This definition *always* first pops a symbol from the stack. That means the PDA is not able to operate on the empty stack. Indeed, the definition of a PDA provides an initial stack symbol $Z$, and we may prefer to keep that on stack until accepting, in order to avoid the empty stack halfway through.

As far as I understand the usual assumption on $A/\alpha$ with nonempty $A$ is to keep the PDA quite similar to context-free grammar which also operates with rules $A\to\alpha$, except that a PDA additionally has states.

One of the few books I know that deviate from this is S\*pser, where now $A$ is allowed to be empty, so one may push symbols on the empty stack, without popping. This does not change the power of pushdown automata, except when considering determinism.
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: What books are there to learn to implement these graph algorithms?
I saw a post on Reddit (https://www.reddit.com/r/math/comments/ci50d3/visualizing\_mathematical\_subjects/) that utilizes label propagation, Fruchterman-Reingold algorithm, and edge betweenness clustering to classify mathematical subjects based on papers in 2018 on arxiv.org.

In a math book, definitions and theorems are often numbered. We can create a directed graph by using these numbers as nodes. If number A is referenced in the proof of number B, an arrow is drawn from A to B. The resulting directed graph represents the logical relationship (or understanding order) between these numbers. This graph can then be arranged as tree. The first layer usually will have the most nodes, but the nodes in the later layers are more likely to be the focus of an exam or be a book's main results. I think this graph has the following advantages:

1. Knowing the general structure of the book before reading
2. Easily allocating attention while reading, such as focusing on the current key number and ignoring non-essential (logical) relationships
3. Quickly finding numbers that were not fully understood, memorized when encountering a difficult number
4. Reading in reverse order, starting from the last few layers and reading backwards, which naturally engages more attention on the last few layers layers. So perhaps achieve the attention mode of the review stage after reading or when doing practice problems at the very beginning.

To draw the arrows between numbers, instead of manually searching for each number using ctrl+F in the PDF, it should also be possible to directly search for all numbers or keywords in the text and convert the order of numbers in the text to the graph, since if number A appears again between number B and C, it is likely that it is referenced in the proof of number B. It's worth noting that some math books number definitions and theorem separately, while others number them all together.

I have searched for pre-existing graph tools on the internet but have not found any that fit my needs. My questions are :

1. Are there any programming books that cover the implementation of algorithms such as label propagation, Fruchterman-Reingold, edge betweenness clustering, converting directed graphs to tree graphs, or other advanced graph algorithms? I'm a math back ground student, have basic knowledge of Python.
2. How can I retrieve all specified keywords in a PDF and generate their appearing order in the PDF?

Here is an example I created for a math lecture notes, of a course I take this year, using https://csacademy.com/app/graph\_editor/, I did it manually as I described above.

# Answer
> 1 votes
For question 1, I suggest that you start with basic programming courses. If you understand how to program, and you understand the specific algorithms you are referring to, you should be able to implement them. You should not need a specific course or textbook that is specifically on implementing those particular algorithms. There are many online resources for learning to program. You might start with a data structures course and an algorithms course.

Question 2 is off-topic here, as coding questions are outside of the scope of this site.

---
Tags: graphs, data-mining, knowledge-representation
---


# Question
Title: How is the direct product of the functions (A -> B) * (C -> D) equivalent to the function (A * C) -> (B * D)? Is there an error here?
In the simply typed lambda calculus we have type algebra - types can be added, multiplied and exponentiated, where addition corresponds to the sum type, multiplication to the product type, and functions to the exponential type (where A -\> B corresponds to B^A). Due to the commutativity and associativity of the sum type and product type, we will consider such types isomorphic up to a permutation, for example, A * B * C * D * E and C * E * B * A * D can be considered isomorphic.

For example, for any type T, the function type from 0 (void type) to T contains exactly one function, because T ^ 0 = 1. Currying works because nested returns of functions like A -\> (B -\> (C -\> (D -\> R))) corresponds to (((R ^ D) ^ C) ^ B) ^ A, which can be converted to R ^ (A * B * C * D), i.e. (A * B * C * D) -\> R. Intuitively, a "nullary" function returning a term of type T is equivalent to a term of type T itself. A nullary function can also be thought of as a function that takes an empty product type, i.e. 1 (unit type), which is completely consistent with the type algebra, because 1 -\> T corresponds to T ^ 1 = T, i.e. there are as many nullary functions returning a term of type T as there are terms of type T themselves.

In some sources, I have seen expressions like (A + B) -\> C = (A -\> C) * (B -\> C), which is completely valid, because C ^ (A + B) = (C ^ A) * (C ^ B), as well as A -\> (B * C) = (A -\> B) * (A -\> C), which is also completely valid, since (B * C) ^ A = (B ^ A) * (C ^ A). However, in the same sources, I also came across the expression (A -\> B) * (C -\> D) (i.e. the type of all tuples of functions from A to B and from C to D) = (A * C) -\> (B * D) (i.e. the type of all functions from a tuple of A and C to a tuple of B and D). But in general case (B ^ A) * (D ^ C) =/= (B * D) ^ (A * C)! In other words, the number of elements of type (A -\> B) * (C -\> D) in general case may differ from the number of elements of type (A * C) -\> (B * D).

It's some kind of mistake or I'm not understanding something?

Thanks in advance.

# Answer
> 1 votes
You are correct. They are not equivalent. For example, the function $f$ defined as $f(a,c)=(1,1)$ if $a=c$, otherwise $f(a,c)=(0,0)$, is in (A * C) -\> (B * D) (assuming $0,1 \in $ B,D), but has no corresponding element in (A -\> B) * (C -\> D). As you say, the number of elements in those two sets is different, so they cannot be isomorphic.

---
Tags: lambda-calculus, type-theory, sets
---


# Question
Title: When to use subscript and when to make it a function?
Let's say, I have a set of cats $C = \\{ a, b, c, ... \\}$. Each cat has a tail. I can say, that the lengths of the tails of cats are denoted as $t\_a$, $t\_b$, etc. Otherwise, I can say that they are denoted as $t(a)$, $t(b)$, etc. Which option is preferable and when?

# Answer
Both are valid, and the choice is based on personal preference and taste. One benefit of the notation $t(a),\dots$ is that it allows you to refer to the function $t$ that maps from $C$ to lengths, which may be useful in some contexts. One benefit of the notation $t\_a,\dots$ is that if $C$ is finite and small, in some settings it might be intuitive to think of $t\_a,t\_b,\dots$ as separate variables (though of course the two are still equivalent).
> 1 votes

---
Tags: notation
---


title: Generate uniform random vectors

text:
# Question
Title: Generate uniform random vectors
**Problem :** Consider a random vector $v$ which is uniformly distributed over the sample space $S = \\{v \in \mathbb{Z}^{n} : 1^Tv = a , v \ge 0\\}$ . How to efficiently generate such random vector ?

note : I'm actually interested in $n=6,a=30$ .

**Attempt :** The size of the sample space \[1\] is the coefficient $c$ of $x^a$ in $(1+x+...+x^a)^n$ . So the probability of choosing any $v\in S$ is $1/c$ .

However for generation of such random vector , I could only think of first brute forcing with a tree to generate the whole sample space , then form a one-to-one correspondence with $\[0,c\]$ , so the problem becomes generating uniform random variable in $\[0,c\]$ . I don't think this's efficient due to large brute forcing tree .

I wonder if there're any tricks to deal with this ?

\[1\] https://math.stackexchange.com/a/2947295/897319

# Answer
Note that the number of vectors $v \in \mathbb{Z}^n$ such that $v \ge 0$ and $1^\top v = a$ is (by a stars-and-bars argument) exactly

$${a+n-1 \choose n -1}.$$

The number of such vectors with $v\_1=b$ is exactly

$${a-b+n-2 \choose n-2}.$$

Therefore, the probability that $v\_1=b$ is exactly

$${{a-b+n-2 \choose n-2} \over {a+n-1 \choose n-1}} .$$

It is possible to calculate the value of this for $b=0,1,\dots,a$. So, calculate these values, then randomly choose $v\_1$ according to this distribution. Now you need to sample the value of $v'=(v\_2,\dots,v\_n)$ such that $v' \ge 0$ and $1^\top v' = a-b$. This can be done through a recursive invocation of the same procedure (with $n$ replaced by $n-1$, and $a$ replaced with $a-b$).

This should give you an algorithm for sampling from this distribution, with running time proportional to $O(an)$ computations of bignum binomial coefficients. For your values of $a,n$, this should be more than efficient enough.

**algorithm correctness :**

Since we require uniform distribution , the probability of any outcome should be $\frac{1}{\binom{a+n-1}{n-1}}$ .

In the algorithm the size of sample space at step $i+1$ is exactly the number of vectors with $v\_k = b\_k , \forall k \< i +1$ , so by this sampling procedure , the probability of any outcome is $$ \frac{\require{cancel}\bcancel{\binom{a-b\_1+n-2}{n-2}}}{\binom{a+n-1}{n-1}} \cdot \frac{\require{cancel}\bcancel{\binom{a-b\_1-b\_2+n-3}{n-3}}}{\require{cancel}\bcancel{\binom{a-b\_1+n-2}{n-2}}} ... \frac{\require{cancel}\bcancel{ \binom{a-(\sum\_{i=1,...,n-2}b\_i) + 1 }{1} }}{\require{cancel}\bcancel{\binom{a-(\sum\_{i=1,...,n-3}b\_i)+2}{2}}} \cdot \frac{\binom{a-\sum\_{i=1,...,n-1}b\_i}{0}}{\require{cancel}\bcancel{ \binom{a-(\sum\_{i=1,...,n-2}b\_i)+1}{1}}} = \frac{1}{\binom{a+n-1}{n-1}} $$
> 1 votes

---
Tags: algorithms, trees, combinatorics, probability-theory, random-number-generator
---