# Question
Title: On a table there are $N$ stacks. Stack $i$ contains $i$ tokens. Minimum number of moves to make all stacks empty
On a table there are $n$ stacks (numbered $1$ to $n$). Stack $i$ contains $i$ tokens ($1 \leq i \leq n$). During a move, a set of stacks can be chosen and the same number of chips can be drawn from each stack that is part of the chosen set. What is the minimum number of moves to make all stacks empty? For example if $n=3$, the answer is $2$. On the first move, you can choose stacks $2$ and $3$ and remove $2$ chips from them and in the second move you can choose stacks $1$ and $3$ and remove one chip from them.

My approach would be to split the stacks in half, and removing $n/2$ tokens from the second half. Now, the problem size is reduced in half and we can solve it recursively.

I don't know if this approach results in the minimum number of moves or if it does how to prove it.

# Answer
Let $k$ be the smallest integer such that $2^k \> n$.

**Any solution must use at least $k$ moves**

Suppose towards a contradiction that there exists a winning strategy using at most $k-1$ moves $m\_1, m\_2, \dots$. Label each stack $i$ with the set $M(i)$ of moves $m\_j$ that involve $i$ and notice that no label can be empty. Since the number of possible labels (i.e., the number of possible non-empty sets of moves) is at most $2^{k-1} - 1 \le n - 1$, there must be at least two distinct stacks $i,j$ such that $M(i) = M(j)$. This means that the winning strategy removes the same number of tokens from $i$ and $j$, which is a contradiction.

**The divide and-conquer algorithm uses exactly $k$ moves**

Consider now the following recursive algorithm (which is probably the one you are describing in your question):

* If $k=1$ (i.e., $n=1$), let $m$ be the move that removes the only remaining token from the only existing stack and return $\\{m\\}$.
* Split the stacks into two sets $S\_1 = \\{1, \dots, 2^{k-1} - 1\\}$, $S\_2 = \\{ 2^{k-1}, \dots, n\\}$.
* Consider the move $m$ that removes $2^{k-1}$ tokens from each stack in $S\_2$. After $m$, one stack in $S\_2$ is empty and the other $r = n - 2^{k-1} \< 2^k - 2^{k-1} = 2^{k-1}$ stacks contain $1, 2, \dots, r$ tokens.
* Call the algorithm recursively on $S\_1$, to obtain a set $M = \\{m\_1, m\_2, \dots\\}$ of moves that makes $S\_1$ empty.
* Construct a modified set of moves $M'$ that contains all moves $m\_i$ from $M$, with the exception that whenever a move $m\_i$ removes some number $x$ of tokes from the $i$-th stack (which is in $S\_1$), we also remove $x$ tokens from the $(2^{k-1}+i)$-th stack (i.e., from the $(i+1)$-th stack in $S\_2$), if it exists. Notice that this does not increase the number of moves.
* Return $\\{m\\} \cup M'$.

Each invocation of the above algorithm increases the number of moves by $1$, therefore the overall number of moves is equal to the maximum number of recursive calls. Since each invocation decreases the value of $k$ by $1$ and the base case corresponds to $k=1$, we can conclude that the algorithm returns a sequence with exactly $k$ moves.
> 3 votes

---
Tags: recurrence-relation, greedy-algorithms
---


# Question
Title: Computability = Enumerating a sequence in the particular order?
In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a **sequence** (NOT a set) $S=(s\_1,s\_2,\ldots)$ is 1-computable if (I state it differently from the paper but equivalently) there is a Turing machine that writes this sequence to the tape in the **correct** order. A **set** $S$ is 1-enumerable if there is a Turing machine which prints exactly the elements of $S$ but in **any** order.

However, what we usually understand is that "computable" means a Turing machine which guarantees to halt and can find out whether an element belongs to a set $S.$

Is there any relation between those two different definitions of computability?

# Answer
> 1 votes
If you have one of:

1. A machine that takes an index $i$ and definitely terminates with $s\_i$ as a result
2. A machine that takes an index $i$ and a value $s$ and definitely terminates, indicating whether $s$ is the $i$th value of the sequence

then you can write out the sequence in order by simulating one of the above machines for each index in turn. #2 requires searching for the right $s$, but that can be done.

You can also go in the opposite direction. Simulate the machine that writes the sequence in order until it produces the $i$th element, then either yield it for #1, or check it against the input for #2 (assuming representations of $S$ can be compared computably).

---

If you have:

* A machine that takes a value $s$ and definitely terminates if $s \in S$, and otherwise might not halt.

Then you can make a machine that enumerates all of $S$ in an arbitrary order by dovetailing. You simultaneously simulate the machine on ever more candidates, and finalize a result whenever one of the simulations halts. The order that you'll enumerate the values depends on how long it takes for the input machine to halt, though, and you have to interleave simulations to avoid getting stuck on a simulation that will never halt. So no order can be guaranteed.

You can also go backwards in this scenario. Given a machine that enumerates $S$ in an arbitrary order, you can produce a machine that given $s$, definitely terminates if $s \in S$, and loops otherwise. You just simulate the enumerator, and check $s$ against what it produces. If $s \in S$ then you will eventually get a match. Otherwise you will keep looking forever, because there is no guarantee about the order of the enumeration.

---

The first scenario is "recursive" or "computable." The second scenario is "recursively enumerable" or "computably enumerable."

---
Tags: computability, terminology, history, recursively-enumerable
---


# Question
Title: Algorithmic Complexity of Recognizing Claw-Free Graphs
Let $H=\left(V\_H, E\_H\right)$ and $G=(V, E)$ be graphs. A *subgraph isomorphism* from $H$ to $G$ is a function $f: V\_H \rightarrow V$ such that if $(u, v) \in E\_H$, then $(f(u), f(v)) \in E$. $f$ is an *induced subgraph isomorphism* if in addition if $(u, v) \notin E\_H$, then $(f(u), f(v)) \notin E$.

A *claw* is another name for the complete bipartite graph $K\_{1,3}$. A *claw-free* graph is a graph that does not have a claw as an induced subgraph.

I know, in general, that induced subgraph isomorphism is an NP-complete problem. However, the situation may be different for certain special induced-subgraphs. For example, $C\_3$.

Claw-free graphs were initially studied as a generalization of line graphs （the line graph $L(G)$ of any graph $G$ is claw-free), and Roussopoulos (1973) and Lehot (1974) described **linear time algorithms** for recognizing line graphs and reconstructing their original graphs.

Our question is, what is the algorithmic complexity of identifying whether a graph contains an induced claw? Are they polynomial, or even linear?

# Answer
A graph is, as you say, claw-free if and only if it does not contain $K\_{1,3}$ as an induced subgraph.

This gives rise to the trivial $n^4$ algorithm: for every set of four vertices, is the degrees of the induced subgraph $3,1,1,1$?

Steven, in another thread, points to a paper by Williams, Wang, Williams, and Yu that give an algorithm for claw detection running in matrix-multiplication time $O(n^\omega)$, where $\omega \< 2.3728$.

Williams, Wang, Williams, and Yu, Finding Four-Node Subgraphs in Triangle Time, SODA 2015.
> 12 votes

# Answer
Let $G$ be our graph. For each vertex $v \in V(G)$, let $H\_v$ be the complement of the subgraph consisting of all vertices adjacent to $v$. We find an induced $K\_{1,3}$ in $G$ if and only if there is any vertex $v$ for which $H\_v$ contains a triangle.

Of course, there is the trivial $O(n^3)$ algorithm for testing if $H\_v$ contains a triangle, for an overall $O(n^4)$ algorithm for the original problem. But we can do better for large graphs: if $A\_v$ is the adjacency matrix of $H\_v$, then $H\_v$ contains a triangle if and only if $(A\_v)^3$ has any nonzero diagonal entries. This gets our complexity down to $O(n^{\omega+1})$, where $\omega$ is the exponent for fast matrix multiplication.

---

Let $m$ be the number of edges in $G$. There's also an $O(n^2m)$ algorithm useful for sparse graphs (and related to the $O(nm)$ algorithm for triangles). Looping over every edge $xy$ and every non-adjacent pair $\\{u,v\\}$, check whether one of $x,y$ is adjacent to both $u$ and $v$ and the other is adjacent to neither. This happens exactly when $x,y,u,v$ induce a $K\_{1,3}$.

With a little bit more care, we can make this $O(m^2)$ (where I am assuming $m \ge n$). Instead of the above, for every edge $xy$:

1. Go through all the edges $uv$ and find how many satisfy the same condition: $u$ and $v$ are both adjacent to $x$ but not $y$, or vice versa. This counts the paw graphs in which $xy$ is the non-cycle edge.
2. Going through all the vertices other than $x$ and $y$, let $n\_x$ be the number adjacent to $x$ but not $y$, and let $n\_y$ be the number adjacent to $y$ but not $x$. Then $\binom{n\_x}{2} + \binom{n\_y}{2}$ counts the number of both claws containing $xy$ *and* paws in which $xy$ is the non-cycle edge.

Subtracting, we determine whether $xy$ is part of any claw.

---

As a lower bound, we can't beat the complexity of triangle-finding, because for any graph $H$, we can construct $G$ by taking the complement and adding a new vertex adjacent to all vertices of the resulting graph. Then, $H$ is triangle-free if and only if $G$ is claw-free.
> 7 votes

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


title: Complexity of Integer Division

text:
# Question
Title: Complexity of Integer Division
My favourite algorithm textbook: The Algorithm Design Manual S. Skiena.pdf had this interesting problem:

> 1-28. \[5\] Write a function to perform integer division without using either the / or * operators. Find a fast way to do it.

What's the lower bound for asymptotic complexity of this problem? \`

P.S: I know repeated subtraction with `a` will work. It has asymptotic linear complexity with `b` (case where `a = 1`). However, repeated subtraction has exponential complexity with $n$ where $n$ is the number of bits needed to represent the number. Specifically it is $\Theta(2^n)$. So it is definitely not fast.

# Answer
Wikipedia has a nice page about the complexity of mathematical operations, and there is also a dedicated page about division. Asymptotically, division has the same complexity as multiplication. The fastest known algorithm, due to Harvey and van der Hoeven, runs in time $O(n\log n)$. However, this algorithm isn't practical (it is not fast in practice, since the integers aren't large enough). Wikipedia lists no known lower bounds, though some people believe that the complexity should be $\Omega(n\log n)$, and there are some bounds in weak models. See for example Lower Bounds for Multiplication via Network Coding by Afshani, Freksen, Kamma, and Larsen.
> 9 votes

# Answer
I believe that the answer the author has in mind is something more in the line of binary long division, which can be "efficiently" implemented with shifts, subtractions and comparisons in $O(W)$ steps where $W$ is the machine word length in bits.

Notice that using bit shifts, which could be interpreted as a way to reintroduce multiplication thru the back door, is not a necessary condition to obtain an algorithm linear in $W$ given that they can in turn be substituted by iterated doubling of the dividend,

```
const int W = 8*sizeof(int);
int p2w[W];
p2w[0]=p;
for (int w=0; w<W-1; ++w)
    p2w[w+1]=p2w[w]+p2w[w];

```

which can generate all the necessary elements in the sequence ${2^w p}$ for $0\le w \le W$ also in linear time, at the cost of $O(W)$ extra memory.

We can then divide $q=a/p$ using no more than $O(W)$ operations as follows:

```
int q=0;
for (int w=W-1; w>=0; --w) {
    q+=q; // same idea as before
    // binary long division
    if (a>p2w[w]) {
        a-=p2w[w];
        ++q;
    }
}

```

This analysis obviates the complexity and delay of the digital circuits implemented in hardware and assumes addition and the other instructions run in constant time. A more sophisticated analysis could take into account the combined algorithmic+circuit complexity by counting the total number of gates and the cycles necessary to execute the solution, which is similar to the concept of PDP (power-delay product) in electronic engineering.
> 0 votes

# Answer
If you don’t have a multiplication operation, you can implement for example a 64x64 bit product with 63 additions, in constant time. So your asymptotic behaviour doesn’t change.
> 0 votes

---
Tags: complexity-theory, arithmetic, integers
---


# Question
Title: Implementing algorithms from online courses in code to solidify understanding
I came across the online course Design And Analysis Of Algorithms and the assignments have several questions that ask you to design algorithms, but you are not asked to implement them in code. I think I would have a deeper understanding if I could see how to implement them in code, but there are questions covered on various topics such as network flows and linear programming that you would not find on websites like Leetcode or Codeforces where you could implement the code. Does anyone have suggestions on how you could implement the algorithms and similar to with Leetcode get some feedback on whether your implementation is correct and efficient?

# Answer
> 0 votes
For execution time, you just measure with problems of different sizes. Take a problem of size n big enough so it takes ten seconds to solve, then solve problems of size 1.1n, 1.2n and see how the time behaves.

Correctness: That’s a problem you will always have, in every programming job you do, when there is nobody to follow. Many problems produce a solution that can be checked. With optimisation problems, you can check that a solution is correct, checking that it is optimal can be difficult. Sometimes you have a fast and difficult, plus a slow and simple algorithm and can compare their outputs. And sometimes you can construct problem instances with a given solution.

---
Tags: coding-theory
---


# Question
Title: An efficient way to find a pair of unrelated edges
I'm writing a program which uses an undirected graph to represent certain social connections, and I'm trying to check whether or not it's contains a specific induced subgraph.

Given a dense an undirected graph $G=(V,E)$ where I have a large amount of vertices and $|E|\in O(|V|^2)$ many edges, I would like to check whether it contains a cross/parallel (unrelated) edge pair. These are $2$ edges $\left(v\_1, v\_2\right)$ and $\left(v\_3, v\_4\right)$ such that for any $i\<j$ (excluding $i=1,j=2$ and $i=3,j=4$) there is no edge $\left( v\_i , v\_j \right)$. In other words, the only $2$ edges are $\left(v\_1, v\_2\right)$ and $\left(v\_3, v\_4\right)$.

This is a subroutine that is expected to be called frequently (on different graphs, so I can't use partial results from previous iterations), so I'm trying to save valuable runtime.

The initial naive approach is $|E|^2 = |V|^4$ by having's $O(1)$ boolean conditions to be checked for any pair of edges, but this is highly not effective.

I have been thinking to look at $\overline{G}$, and check to see if it is a chordal graph and also if it contains $C\_4$. I know that a LEX-BFS approach can verify in $O(|V|+|E|)$ if $\overline{G}$ is chordal or not (see Rose, Lueker & Tarjan (1976)), and that in $O(|V|^2)$ it is possible to check if $\overline{G}$ contains $C\_4$ by a variant of BFS.

However, I am not sure if this approach if there is a more efficient approach. It seems that too much time is "wasted" upon checking if $C\_4$ exists, and that's why I'm looking for an alternative way.

Clarifications:

* I'm looking for a subset of $4$ vertices $\left\\{ v\_1 ,\ldots , v\_4 \right\\}$ such that $\left(v\_1,v\_2\right),\left(v\_3,v\_4\right) \in E$ and these are the only edges induces by these vertices.
* In other words, for any other $i,j$ there is no edge $\left(v\_i , v\_j \right)\notin E$.
* My usecase for this graph is dense, so may assume $|E| \in O(|V|^2)$.
* The graph itself is persumed to have many vertices, so I'm trying to reduce the runtime somewhere to linear or $|V| \log |V|$ or $|V|^2$ but $|V|^3$ can take too much considering the amount of vertices I have (Because this is a subroutine that would be invoked many times).

# Answer
> 3 votes
This 2015 paper by Williams et al. considers **induced** subgraphs and shows how to find $C\_4$ and co-$C\_4$ in a graph $G$ time $O(\min\\{n^\omega, m^{\frac{4\omega-1}{2\omega+1}}\\})$, where $n$, $m$ are the number of vertices and edges of $G$, respectively, and $\omega$ is the matrix-multiplication exponent.

Since $\omega \< 2.372$, this is a subcubic algorithm.

---
Tags: graphs, runtime-analysis, graph-traversal, breadth-first-search
---


# Question
Title: Number of decycling sets in a 3-regular planar graph
*Defintitions*: A graph is said to be **r-regular** if every of its vertex has a degree $r$. A graph is **planar** if it can be drawn in a plane without any of its edges intersecting each other except at their endpoints. A graph is **connected** if there exists at least one path between every pair of its vertices. A **tree** is connected acyclic graph and a **forest** is a disconnected acyclic graph. A graph G' is an **induced subgraph** of a graph G if it inherits all edges over a particular vertex subset of G. A **decycling set** in a graph is a subset of its vertices, deletion of which induces a forest.

*Question:* Let $S\_n$ be the set of all possible 3-regular connected planar graphs on $n$ vertices. Let *N(g)* be the number of decycling sets which induce a tree(not a forest) in graph $g$. Let $N\_n^\*$ = $max\\{N(g)\ \forall g\in S\_n\\}$. Give the smallest order function $f(n)$ such that $N\_n^\* = O(f(n))$. In other words, give a tight upper bound in terms of n, on the number of tree inducing decycling sets in a 3-regular connected planar graph.

A very loose upper bound of course is $2^n$, which is the number of subsets of vertices. However, not all subsets are trees. And not all trees are induced trees. Moreover, 3-regular graphs are much sparser than a complete graph, and connected planar 3-regular graphs is an even smaller subset of 3-regular graphs. Many applications require the enumeration of certain set of objects associated with a graph, such as the number of spanning trees, or the number of cycles(sometimes special cycles such as cycle basis) or the number of cliques etc. It is natural to wonder if the tight upper bound on the number of objects such as induced trees, and that too in a quite restricted class of graphs i.e. 3-regular connected planar graphs is sub-exponential or even polynomial ?

*Illustration:* The illustration below shows such a tree in a 3-regular planar graph. The vertices that are not part of the tree compose the decycling set.

# Answer
> 1 votes
The tight bound on the number of decycling sets is $2^{\Theta(|V|)}$. Consider the following $3$-regular planar graph.

In the decycling set, for each $i \in \\{1,\dotsc,n\\}$ choose either $a\_i$ or $b\_i$. Moreover, choose the vertex $c\_n$ in the decycling set. Note that removing these vertices induces a tree on the remaining vertices. Thus, there are $2^{n} = 2^{\Omega(|V|)}$ choices for a decycling set. The upper bound is naturally $2^{O(|V|)}$ for any input graph (as you mentioned in the question as well). Thus, the tight bound is $2^{\Theta(|V|)}$.

---
Tags: graphs, planar-graphs
---


# Question
Title: Is there an efficient algorithm for this ecommerce optimization problem?
Consider the problem of minimizing the checkout price of a shopping basket in the presence of some discount rules:

There are $n \gt 0$ distinct products in our shopping basket. Each product is associated with a price $price\_i \geq 0$ and a quantity $quantity\_i \gt 0$. Without applying any discounts, the checkout price is simply $\Sigma\_{i=1}^n price\_i \times quantity\_i$.

There are 2 different product categories, Category A and Category B. Each product can be placed into either one of the categories, but certain products might be placed into both categories at the same time.

Discount works as follow: if $a$ pieces of products in Category A and $b$ pieces of products in Category B have been purchased, the full bundle of the $(a+b)$ pieces will cost a total of \\$C. There are no constraints on \\$C. It can be very very high and everyone would just ignore the discount.

For example, suppose $n=2$, $a=2$, $b=3$, $C=100$, we are buying product X (category A, price=30, quantity=3) and product Y (category B, price=40, quantity=3). The original price is $30 \times 3 + 40 \times 3 = 210$, but after applying the discount, it becomes $100 + 30 = 130$

Example 2: suppose $n=4$, $a=1$, $b=1$, $C=20$, we are buying product W (category A, price=30, quantity=3), product X (category A, price=40, quantity=3), product Y (category B, price=50, quantity=4) and product Z (in both categories A & B, price=60, quantity=4). The original price is $30 \times 3 + 40 \times 3 + 50 \times 4 + 60 \times 4 = 650$. Assuming the discount can only be applied once, we will apply the discount on product Z+Z, and the checkout price becomes $30 \times 3 + 40 \times 3 + 50 \times 4 + 60 \times (4-2) + 20 = 550$.

However, if the discount can be applied unlimited number of times, the optimal choice is to pair up all of the items, and the checkout price will be $7 \times 20 = 140$

Is there an efficient algorithm to compute the minimum checkout price if there is only 1 such discount rule and it can only be applied once? What if it can be applied unlimited number of times? What if there are multiple such discount rules?

Note that each piece of item in the basket can only be discounted once in any cases.

# Answer
The usual rule on this site is to ask only one question per post, so I'll answer the first question. Specifically, I'll focus on the case where there is only one discount rule, and it can only be applied once. In that case, the problem can be solved with a greedy algorithm:

* Let $n\_a := a, n\_b := b, n\_x := 0$.
* Sort all the products, by decreasing price. (If a price has quantity higher than one, it is duplicated that many times in the sorted list.)
* While $n\_a\>0$ or $n\_b\>0$ or $n\_x\>0$ and the list is non-empty:

+ Take the next product from the sorted list.
    + If this product is of category A and B:
        - If $n\_a\>0$ and $n\_b\>0$, set $n\_a := n\_a-1$ and $n\_b := n\_b-1$ and $n\_x := n\_x+1$ and mark this product.
        - Otherwise, if $n\_a\>0$ and $n\_b=0$, set $n\_a := n\_a-1$ and mark this product; if $n\_a=0$ and $n\_b\>0$, set $n\_b := n\_b-1$ and mark this product; if $n\_a=0$ and $n\_b=0$ and $n\_x\>0$, set $n\_x := n\_x-1$ and mark this product.
    + If this product is of category A only:
        - If $n\_a\>0$, set $n\_a := n\_a-1$ and mark this product.
        - Otherwise, if $n\_a=0$ and $n\_x\>0$, set $n\_x := n\_x-1$ and mark this product.
    + If this product is of category B only:
        - If $n\_b\>0$, set $ n\_b := n\_b - 1 $ and mark this product.
        - Otherwise, if $n\_b=0$ and $n\_x\>0$, set $n\_x := n\_x-1$ and mark this product.
* At the end, if $n\_a=0$ and $n\_b=0$ and $n\_x=0$, combine all marked products into the discount bundle. This is the optimal selection of items to use the discount on.

The intuition is that marked items are selected to be in the bundle, and we proceed down the list, from most expensive product to least expensive. At any intermediate stage of the algorithm, $n\_a$ counts the number of additional items we need from category A to complete the bundle, $n\_b$ counts the number of additional items we need from category B to complete the bundle, and $n\_x$ counts the number of other items we need (they can be any category) to complete the bundle.

Regarding a discount code that can be applied an unlimited number of times, I suggest spending some time trying to figure out if you can adapt this greedy strategy to that case; if not, ask a new question about that case, and share what progress you've made.
> 0 votes

---
Tags: algorithms, np-complete, np-hard, combinatorics
---


# Question
Title: How proof of Huffman algorithm greedy property starts with optimal tree T?
In this paper Claim 1 states that *x* and *y* are smallest probability and *there is optimal code tree in which these two characters are siblings at the maximum depth*. In proof to that claim, author starts with tree *T* which has *b* and *c* at the maximum depth of tree.
I can't understand why tree *T* is called optimal, because if *x* and *y* have smallest probabilities, then tree T cannot be optimal because the Huffman algorithm won't build such tree.
I think my problem here is with understanding what optimal tree means.

If someone comes from CLRS this is about lemma 16.2 and proof to that.

# Answer
> 0 votes
A code tree is *optimal* if the average codeword length is minimal. This has nothing to do with Huffman's algorithm. Huffman's algorithm is guaranteed to produce an optimal code tree, but there might be other code trees. In fact, Huffman's algorithm could produce different code trees using different tie-breaking rules. Moreover, not every optimal code tree can be produced using Huffman's algorithm, even with an arbitrary tie-breaking rule.

Here is a formal definition of an optimal code tree. Let $\pi$ be a distribution. The *$\pi$-cost* of a code tree is the expected length of a codeword, where the expectation is taken with respect to $\pi$. A code tree is *optimal for $\pi$* if its $\pi$-cost is equal to the minimum $\pi$-cost of any code tree.

# Answer
> 0 votes
Optimal tree means it has the minimum bit length. Huffman trees are an example of Optimal trees (in fact Huffman can produce different optimal trees using tie breaking rules) but there are also optimal trees that are non Huffman where the least frequency nodes are not at the deepest depth and yet end up having the same bit length as the Huffman one.
What makes a tree optimal is the Average Bit length or the weighted path cost of the tree, not its construction. There could be various trees of various configurations with the same bit length.
In Lemma one all it is saying is another optimal tree can be converted to a Huffman like tree with an exchange. With the exchange you can show that it does not decrease the weighted path cost.

---
Tags: correctness-proof, greedy-algorithms
---


# Question
Title: Converting encrypted messages to unencrypted results of an equally hard to reverse function
If we have some function, $f$ with an exponentially sized domain, mapping the set $\\{0, 1\\}^N$ to $\\{0, 1\\}$, could we do something like this:

For ease, let's say $E(x) = x^e (\text{mod} \\; n)$. This is the encryption function.

Now, let's say we represent $f$ with some $x$. I'm not exactly sure how this can be done---maybe $f$ can be represented as a circuit or something like that?

Our subject then encrypts $f$'s representation using $E$---$E(f)$---and broadcasts this to their peers.

The peers receive this encrypted function, and want to call it on some values $\\{a, b, c, \cdots\\}$ and obtain the result.

Because $f$ is hard to reverse without any information on its implementation (it will take $O(2^N)$), this doesn't break encryption.

I think this may relate to homomorphic encryption---we want to perform the operation of calling $f$ with input $a$, and compute an output. The difference is that we don't want to the result to be encrypted.

Is there any method of doing such a thing?

# Answer
> 0 votes
Yes, this is possible, if you're willing to involve the holder of the private key. Let $U$ be a universal circuit, so that $U(f,v)=f(v)$. (There will be some upper limit on the size of circuit $f$ that is supported by $U$. Presumably that will be OK.) Then you can use homomorphic encryption to encrypt $f$ and then compute an encrypted form of $U(f,v)$ from the encrypted form of $f$. Whoever holds the private key can then decrypt to obtain $U(f,v)=f(v)$.

---

No, I don't think this is not possible, if you want it be done without cooperation of the holder of the private key and you want to be able to recover the value $f(v)$ in unencrypted form. If there was some such protocol that allowed anyone to compute $f(v)$, given $E(f)$ and $v$, then that would mean the encryption is not secure. In particular, it would violate semantic security. You say it "doesn't break encryption", but in fact it does violate the standard requirements for encryption to count as secure. Also, for many function classes, given many input-output pairs $(v,f(v))$, it is often possible to recover $f$, which would be a total break of $E$.

Perhaps there is some way to formulate the problem so that $E(f)$ must not leak anything more than ability to compute $f(v)$ for any choice of $v$. I suspect that would be a pretty weak form of encryption, but perhaps it could be possible to create such a scheme. I don't know how, though.

---

You might also be interested in Yao's garbled circuits, which has some limitations but is an adjacent space to what you asked for.

---
Tags: time-complexity, cryptography, encryption
---


title: Algorithm for optimal item selections

text:
# Question
Title: Algorithm for optimal item selections
I'm trying to find an algorithm for this problem:

I'm going to the shop and need to buy X grams of an ingredient.

The shop does not necessarily have an "X grams of ingredient" product. But they have N products with different weights.

Which combination of products should I buy so I end up with at least X grams of the ingredient and the amount of ingredient the closest to X as possible? I can select the same product several times.

---

Example 1 :

I want to buy 1.4kg of pasta. The shop has these products:

* Product A: 1kg of pasta
* Product B: 500g of pasta
* Product C: 300g of pasta

Solution: I need to buy 1 product B and 3 products C (500g + 3 x 300g = 1.4kg)

because it's the exact amount I need.

---

Example 2 :

I want to buy 300 grams of rice. The shop has these products:

* Product A: 1kg of rice
* Product B: 500g of rice
* Product C: 200g of rice

Solution: I need to buy 2 products C.

Because it ends up being 400g, which is lighter than 1 product B (2x200g \< 500g)

# Answer
> 1 votes
This problem is NP-Hard by a reduction from the following version of subset sum: given a multi-set $X$ of $2n$ numbers $\\{x\_1, \dots, x\_{2n}\\}$ and a target $T$, is there a subset $X'$ of $X$ with $|X'|=n$ and $\sum\_{x \in X'} =T$?

However, the problem admits a pseudopolynomial-time dynamic programming algorithm when all weights are integers.

Let $OPT\[x\]$ be true ($\top$) if there is a way to choose a subset of products whose sum of weights is exactly $x$, and false ($\bot$) otherwise. Clearly $OPT\[0\]= \top$ and $OPT\[x\]=\bot$ for $x\<0$. Moreover, denoting by $w\_i$ the weight of the $i$-th product, whenever $x\>0$ you have: $$ OPT\[x\] = \bigvee\_{i=1}^N OPT\[x-w\_i\]. $$

Each value $OPT\[x\]$ for $x = 0, \dots, X$ can be computed in time $O(N)$, and hence all such values can be found in time $O(N \cdot X)$.

The minimum amount $X^\*$ that is not smaller than $X$ can be found in an additional $O(N \cdot X)$ time since either $OPT\[X\]=\top$ (i.e., $X^\* = X$) or it can be found by adding one more product to some achievable amount $x$, i.e., $$ X^\* = \min\_{i=1,\dots,N} \left( w\_i + \min\_{\substack{x = \max (0, X-w\_i+1), \dots, X-1 \\ OPT\[x\]=\top}} x \right), $$ where we treat a minimum over an empty range as $+\infty$.

The actual solution can be found (in the same asymptotic time) by retracing the optimal choices backwards.

---
Tags: algorithms
---


# Question
Title: Representing binary functions with a finite gate set without exponential blow-up?
It is pretty well taught that any binary function can be represented using CNF. But conversion to CNF can take an exponential number of gates. The truth table is exponentially sized relative to the number of input variables.

Is there any form of representing truth tables that requires only a polynomial or quasipolynomial number of gates? I know there are ones that preserve satisfiability, not equality---but is there anything that preserves equality?

# Answer
No. No matter what representation of functions as circuits/formulas you use, there will exist some functions that require exponential size to represent. This was proven by Shannon in 1949. See Shannon's result that some Boolean functions require exponential circuits.

Intuitively, you can count the number of circuits/formulas of polynomial size, and it is much less than the number of functions.
> 13 votes

---
Tags: logic, circuits, boolean-algebra
---


# Question
Title: Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time
Suppose I have a dynamic table supporting $Insert$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $q \> 1$. (I have proof that that arrangement leads to amortized constant time for $Insert$: see this post.)

My best attempt so far is: $\Phi\_i = \alpha n\_i + \beta N\_i$, where $n\_i$ is the number of elements in the dynamic table after the $i$th operation, and $N\_i$ is the total capacity of the underlying array after the $i$th operation.

The above leads to:

(1) If there is more room for a new value, $n\_i = n\_{i - 1} + 1$, and $N\_i = N\_{i - 1}$: \begin{aligned} \hat{c\_i} &= c\_i + \Phi\_i - \Phi\_{i - 1} \\ &= 1 + (\alpha n\_i + \beta N\_i) - (\alpha n\_{i - 1} + \beta N\_{i - 1}) \\ &= 1 + (\alpha n\_{i - 1} + \alpha + \beta N\_{i - 1}) - (\alpha n\_{i - 1} + \beta N\_{i - 1}) \\ &= 1 + \alpha \\ &= \Theta(1). \end{aligned}

(2) However, if there is no more room for the new value, we need to make the underlying array larger; in our case, we multiply its capacity by a constant $q \> 1$:

Now, we have: $n\_i = n\_{i - 1} + 1$ and $N\_i = qN\_{i - 1}$: \begin{aligned} \hat{c}\_i &= c\_i + \Phi\_i - \Phi\_{i - 1} \\ &= 1 + (\alpha n\_i + \beta N\_i) - (\alpha n\_{i - 1} + \beta N\_{i - 1}) \\ &= 1 + (\alpha n\_{i - 1} + \alpha + \beta qN\_{i - 1}) - (\alpha n\_{i - 1} + \beta N\_{i - 1}) \\ &= 1 + \alpha + (q - 1) \beta N\_{i - 1}. \end{aligned} ... and at this point, I am stuck.

# Answer
> 0 votes
I don't understand why you used $1$ as the non-amortized cost of a resizing.

Define $\Phi\_i$ as $\frac{q^2}{q-1}$ times the number of elements inserted in the table since the last resizing. In formulas let $\Phi\_i = \frac{q^2}{q-1} \cdot ( i - \frac{N\_i}{q} ) = \frac{q^2}{q-1} i - \frac{q}{q-1} N\_i$.

If the $i$-th element is inserted and no resizing happens then the worst-case cost of the operation is $1$ and $N\_i = N\_{i-1}$. $$ \begin{align\*} 1 + \Phi\_i - \Phi\_{i-1} &= 1 + \left(\frac{q^2}{q-1} i - \frac{q}{q-1} N\_{i-1} \right) - \left( \frac{q^2}{q-1} (i-1) - \frac{q}{q-1} N\_{i-1} \right) \\ &= 1+ \frac{q^2}{q-1}. \end{align\*} $$

If the $i$-th element is inserted an a resizing happens then $N\_i = q N\_{i-1}$ and the worst-case cost of the operation is $1 + N\_i = 1 + q N\_{i-1}$. $$ \begin{align\*} 1 + q N\_{i-1} + \Phi\_i - \Phi\_{i-1} &= 1 + q N\_{i-1} + \left(\frac{q^2}{q-1} i - \frac{q^2}{q-1} N\_{i-1} \right) - \left( \frac{q^2}{q-1}(i-1) - \frac{q}{q-1} N\_{i-1} \right)\\ &= 1 + q N\_{i-1} + \frac{q^2}{q-1} - (\frac{q^2}{q-1} - \frac{q}{q-1}) N\_{i-1} \\ &= 1 + q N\_{i-1} + \frac{q^2}{q-1} - q N\_{i-1} \\ &= 1+ \frac{q^2}{q-1}. \end{align\*} $$

---
Tags: runtime-analysis, arrays, amortized-analysis, dynamic-array
---


# Question
Title: Same Address and Write signal for two block of RAM?
I don't know if I asked the question in correct way but I will try to explain what's the thing I am not getting. I am currently reading book titled "Code: The Hidden Language of Computer Hardware and Software". In chapter sixteen, the book discusses structure of memory starting from latch. Following image shows 1 byte of memory where each bit is addressed by $s\_0$, $s\_1$ and $s\_2$.

Above memory structure is reduced into the block diagram as show below.

Now, the book shows connecting two memory block. Now things got confusing for me from here.

Let us assume that both the memory block have some data in it. Now I would like to overwrite all the bits in $1st$ block of memory. So, I give signal to $A\_0 , A\_1$ and $A\_2$ ranging from $000$ to $111$ while feeding $DI$ of the $1st$ block of memory. To write those data on our 1st block of RAM, I have to send write signal too. The write signal line and the address line both are connected to another block of memory too. Now when I send address and write signal, the second block of memory gets the signal too. But, I am not sending any data to second block of memory which essentially means 0 at Data In of second block. We assumed that the second block of memory also has some bit stored in it. When trying to write data on 1st block of memory, haven't I set all the bits in the second memory to zero? This wasn't what I wanted to do. How do I write in 1st block of memory without overwriting the data on second block of memory? Please enlighten me!

# Answer
You *do* write data in second block whenever you write data in 1st block of memory.
You *can* provide *independent* Data In to each block and expect it to be readable independently at the Data Outs: the second diagram depicts an 8 words of 2 bit memory.
The first one does *not* depict `1 byte of memory`, but an 8 words of 1 bit memory.
> 1 votes

---
Tags: memory-hardware, memory-access
---


# Question
Title: Complexity of non-commutative range multiplication operation
Let $G$ be a non-commutative group, such as $\operatorname{GL}\_k(\mathbb F\_p)$. Given a list $\vec{a}=(a\_1, \cdots, a\_n) \in G^n$, we use $(p, q, x)$ to denote the operation that maps $\vec{a}$ to $(a\_1, \cdots, a\_{p-1}, a\_p x, \cdots, a\_q x, a\_{q+1}, \cdots, a\_n)$. Do we have an algorithm running in time complexity $O(n^{1+\epsilon})$, such that when input a sequence of operations $(p\_i, q\_i, x\_i)\_{i \leqslant l}$ where $l = O(n), p\_i \leqslant q\_i \leqslant n$, it computes the result of these operations on list $(1, 1, \cdots, 1)$?

When the group operation is commutative, it can be computed using a textbook segmented tree or Fenwick tree, where each operation takes time $O(\log n)$, and all these $l$ operations take time $O(n \log n)$.

# Answer
> 0 votes
Yes, it can be done in $O(n \log^2 n)$ time. Build a balanced binary tree over the $n$ leaves. Store a group element in each node. Initialize the tree by storing the element $1$ in each node.

Identify each leaf with an index $j$ in the range $1 \le j \le n$. The idea is that, at any point during the execution of the algorithm, the value of the $j$th list element will be $g\_1 g\_2 \dots g\_k$, where $g\_1,\dots,g\_k$ are the group elements obtained by traversing the tree starting at leaf $j$ and proceeding upwards until you reach the root.

Define the pushdown($v$) operation as follows: given an internal node $v$ of the tree, let $\ell,r$ be $v$'s left and right children, and $g\_v,g\_\ell,g\_r$ be the group elements stored at $v,\ell,r$. Then we replace $g\_v,g\_\ell,g\_r$ with $1,g\_\ell g\_v, g\_r g\_v$. This takes $O(1)$ time.

Define the megapush($w$) operation as follows: we iterate through the nodes on the path from the root to $w$, executing pushdown($v$) on each such node $v$ (starting with the root first and proceeding downwards). This takes $O(\log n)$ time, as the height of the tree is $O(\log n)$, since the tree is balanced.

Identify each internal node with a range of indices, namely, the range of indices associated with the leaves that are descendants of that node. Any range of indices $\[\ell,u\]$ can be written as the disjoint union of $O(\log n)$ ranges $\[\ell\_i,u\_i\]$, such that each $\[\ell\_i,u\_i\]$ is the range associated with a node of the tree.

To handle the operation $(p,q,x)$, express the range $\[p,q+1\]$ as a disjoint union of $O(\log n)$ ranges $\[\ell\_i,u\_i\]$ as above. For each node $v$ associated with one of these ranges, first execute megapush($v$), then multiply the group element stored at $v$ by $x$. In other words, if $g\_v$ was previously stored at that node (after the megapush), replace it with $g\_v x$. This takes $O(\log^2 n)$ time, since we call megapush on $O(\log n)$ nodes.

Finally, after all of these operations, you can traverse the nodes of the tree in pre-order, executing pushdown($v$) on each node $v$. (In other words, first you execute pushdown on the root, then on its two children, then on its four grandchildren, and so on.)

Then you can read off the results, as the leaf associated with index $j$ will store the value of the $j$th list item after executing all operations.

Each operation takes $O(\log^2 n)$ time ($O(\log n)$ time to execute megapush on each of $O(\log n)$ nodes), and there are at most $n$ operations, so the operations take $O(n \log^2 n)$ time. All other operations can be done in $O(n)$ time.

Therefore, the total running time is $O(n \log^2 n) = O(n^{1+o(1)})$.

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


# Question
Title: What is practically preventing us from applying set-theoretic types in engineering?
I know the title is sort of misleading because we do have set-theoretic types in several languages:) From a theoretic view, set-theoretic types such as intersection, union, and negation may bring some troubles, as the proof object they do not encode the derivation, thus making it hard to find a logical part through the C-H correspondence, moreover, negation is not able to be encoded at all because the normal semantic of complement in set theory contradicts the rejection of the non-existing of the double negation elimination in the intuitionistic logic (**Question**: is this viewpoint correct? that the set-theoretic approach contrast fundamentally with the central of the BHK interpretation of the intuitionistic logic). But from a practical view, it seems that there aren't so many obstacles, and we don't face that many problems we need to be concerned about in the theory: we are doing neither proof verifications nor automated reasoning, so my problems are:

* Why set-theoretic types are relatively rare in the languages?
* Can we define the *negation type* `a: not A` if `a` is not of type `A` (if we only consider the practical part of this problem)?
* Is subtyping also a *set-theoretic* definition? Since the subtyping also does not record the derivation, if this is true, then is subtyping some meta-theoretic level notation, and we need to put intersection/union/negation types at the same level as the subtyping relation.

**Postscriptum:** I've read MLTT and some topology & category theory, not yet started reading the HoTT Book (I want to do this after I've read algebraic topology and some higher category theory, though I might be aware of the fact that the HoTT book does not require so many preliminaries)

# Answer
> 4 votes
1. Negation is certainly possible in these systems. It's discussed in the best introductory materials, in particular: https://www.irif.fr/~gc/papers/covcon-again.pdf https://pnwamk.github.io/sst-tutorial/ This however doesn't have anything to do with double negation elimination or classical logic.
2. As to why these systems are not widely used, there are a few reasons. One is just that the type systems are more complex, and harder to learn about and implement. Additionally, important features such as polymorphism have only been developed recently (e.g., in the last 10 years). The necessary algorithms are also quite expensive, as required by the expressiveness of the type system. Finally, most such type systems rely on runtime type information, which is available in runtimes for e.g. Lua or Erlang but not in conventional typed languages like ML or C.

But these type systems are becoming more common as these constraints get met. E.g., Luau in Roblox uses set-theoretic types, and the new proposals for Erlang and Elixir and Ballerina do as well (designed by the originator of these systems).
3. Finally, true union and intersection types have become more common as well, even if they don't adopt the semantic subtyping perspective (often for performance reasons). See TypeScript, Flow, Typed Racket, and more.

# Answer
> 4 votes
Let me first answer the easy part. The negation sign in the judgement `a : ¬ A` does not modify `:` but `A`. In particular, the standard way to define `¬ A` is to equate it with `A → ∅`.

A major obstacle to using set-theoretic semantics for a programming language is *general recursion*. Concretely, the fixed-point operator

```
fix : {A : Set} → (A → A) → A
fix f = f (fix f)

```

can be defined in general-purpose programming languages. (The above definition works for a functional language, but the same kind of problem arises in any language with general recursion).

If we interpret `fix` in set theory, it says that for every set `A` and every map `f : A → A` there is `a ∈ A` such that `f a = a`. Indeed, just take `a := fix f`. However, if `A` has at least two elements, say `a₁` and `a₂`, then the map `g x := (if x = a₁ then a₂ else a₁)` does not have a fixed point. So sets cannot be used to interpret general recursive functions.

If we remove general recursion, but keep structural recursion (which is always guaranteed to terminate), then we *can* use set-theoretic semantics. For example Martin-Löf type theory can be interpreted in set theory, and so can Coq's calculus of inductive constructions, and Agda's type theory with inductive-recursive defintions. All of these languages strictly control what form of recursion is allowed (namely structural recursion), so as to prevent existence of `fix`.

Another obstacle to set-theoretic semantics is polymorphism, see John Reynold's classic paper Polymorphism is not set-theoretic.

If you are willing to switch to **intuitionistic** set theory, then set-theoretic semantics *can* be recovered. See Andy Pitt's Polymorphism is set-theoretic, constructively and Alex Simpon's Computational adequacy for recursive types in models of intuitionistic set theory.

# Answer
> 2 votes
Generally, and to build upon this discussion, there is plenty of work which describes types exactly as you'd like, that is as a collection of "values" of a certain shape, with natural set theoretic operations on them, like complement, union and intersection.

Worth remembering that union and intersection should be *untagged* if you want them to be "set-like", that is an element of `Nat + Bool` should look like `5` or `true` rather than `Left(5)` or `Right(true)`, otherwise you're in "structural land", and it doesn't really matter whether you think of types as sets (though it's possible as Andrej points out).

As the infinitely knowledgeable Noam notes, you have to be very careful if you have union or intersection types in the presence of mutation though, or polymorphism, because the type system quickly becomes unsound!

The example given in Davies and Pfenning (Intersection Types and Computational Effects) is simply:

```
   let x : ref nat /\ ref pos = ref 1 in
   x := 0;
   let z : pos = x! in
   z

```

With union types and negation, you can even break subject reduction on open terms without mutation! An example is given by Castagna *et al* in On Type-Cases, Union Elimination, and Occurence Typing.

I'll let you draw your own conclusions, but it's pretty clear that

1. Types as a set-theoretic concept is quite well-studied, so not quite as "relatively rare" as you suggest.
2. There are subtleties with the computational content of (untagged) intersection and union types in the presence of effects or other constructs, beyond the simple lack of logical correspondence.

---
Tags: logic, type-theory
---


# Question
Title: How does a regular expression match `.+x`?
A quick test shows what I'm describing:

```
> const text = 'foobarhelloworld'
> const pattern = /.+or/
> text.match(pattern) //=> 'foobarhellowor'

```

What is the basic algorithm for matching "anything up to some explicit text"?

The reason I ask is I am working on hacking together a spell checker / morphological analyzer, building off the ideas from Hunspell, and I want to say "match anything from the start of the word for as much as you can, then if the next character is NOT `[aeiou]`, and the character *after that* is `y`, then make it `ied`." To do that I am creating a JSON DSL, which I need to implement a processor for like processing regular expressions. The DSL will be something like (very rough prototype, still have a lot of thinking/refining to do):

```
{
  load: [
    { name: 'base', base: true, form: 'walker', test: {
      form: 'pattern',
      text: '.'
    } },
    { name: 'note', form: 'not', test: { form: 'or', text: 'aeiou' } },
    { text: 'y', head: true }
  ],
  save: [
    { name: 'base' },
    { name: 'note' },
    { text: 'ied' },
  ]
}

```

You "load" the input text/word, and "save" the output. So we load "candy", and save "candied" in this case.

I just don't see how you would go about implementing this functionality without resorting to using regular expressions (I would like to basically learn how they are implemented, at least at a high level, for this situation). I would like to avoid using regular expressions other than possibly the `.` character for matching anything, or the other helpful character matching shortcuts `\n` and `\w`, etc..

The way I'm thinking about it:

* We are on the first pattern we named "base". It is a "walker" on `.` pattern, meaning in regexp terms, `.+`. So we go to the first character, the second character, the next character, etc... Then we are at the end now!! Are we supposed now go onto the next rule, and backtrack? Or should we have not stepped forward each tick, and instead used the 2nd rule to check if it matches, only falling back down to the `.+` rule #1 if rule #2 doesn't match?

So instead of something like this, which would simply get greedy with the first pattern all the way to the end:

```
let r_i = 0 # rule index
let rule = rules[r_i++]
let w_i = 0 # word index
while true
  let char = word[w_i]
  if rule.match(char)
    w_i++
  else
    raise 'error'
return true

```

Maybe it's more along these lines or something? Not sure:

```
let r_i = 0 # rule index
let rule = rules[r_i++]
let w_i = 0 # word index
while true
  let char = word[w_i]
  if rule.match(char)
    w_i++
  else
    let next_rule = rules[r_i]
    if next_rule.match(char)
      # because of this, will match twice, one more on next loop
      r_i++
    else
      raise 'error'
return true

```

But that seems like it would get stuck too:

```
> const text = 'foobarhelloworld'
> const pattern = /.+ow/
> text.match(pattern) //=> 'foobarhellow'
// could have got stuck at the first `o` in `foo`

```

So what *is* the basic high-level algorithm for implementing this regexp `.+` functionality?

**Related**: What do 'lazy' and 'greedy' mean in the context of regular expressions?

# Answer
This is probably the main difference between "regular expressions" as a formal language, and "regexes" as an implementation tool.

Extending a regular expression matching algorithm to support greedy capture (i.e. the maximal munch rule) is straightforward. Consider this DFA:

Essentially, you run this DFA as is, but whenever you hit the final state, you record the point in the input string where you were, but continue matching. When you reach the end of the input string, the *last* place where you were in a final state is the end of the match.

This approach is enough for a tool like lex/flex; lexical analysis always starts a lexeme exactly where the last one ended, and lexical languages are typically designed so that you don't need to scan to the end of the input file or line to find the end of a lexeme.

However, if you have multiple captures, as you find with capturing brackets in POSIX and Perl regexes, or an ambiguous *start* point, things get a little more complex. It's a broadly similar approach, but in general, finding substrings (as opposed to merely recognising them) may, in the general case, require backtracking.

This is one reason why POSIX/Perl regexes generally don't use deterministic automata, but rather compile to an abstract intermediate representation that supports backtracking execution. See, for example, the article by Russ Cox, *Regular Expression Matching: the Virtual Machine Approach*.
> 2 votes

---
Tags: algorithms, regular-expressions
---


title: Maximizing sum and product of an array

text:
# Question
Title: Maximizing sum and product of an array
Given an array of *positive* numbers with allowed replication, what is the algorithm to find the max amount possible only with summing or multiplying elements? All numbers must be involved in some operation.

I don't know how to look at this problem with greedy approach.

For example, given the array $\[1, 1, 1, 1, 2, 2, 2, 3\]$. The maximum amount is possible using the following set of operations: $(2+1) \cdot (2+1) \cdot (2+1) \cdot (3+1) = 108$

# Answer
Let the array contains $n$ elements. We use the following four lemmas/observations to design an $O(n^3)$ time algorithm.

*Lemma 1*: In any optimal solution $O$, if there is any addition operation $a + b$, then either $a = 1$ or $b = 1$. The vice-versa statement is true as well. That is, if the array contains $1$, then in any optimal solution $O$, $1$ must be part of an addition operation.

*Proof:* ($\to$) For the sake of contradiction assume that $a \> 1$ and $b \> 1$. Then, replacing $a+b$ with $a \cdot b$ gives a solution with the higher value. Thus, contradicting that $O$ is an optimal solution.

($\gets$) For the sake of contradiction assume that the array contains $1$ and the optimal solution has a multiplication operation $a \cdot 1$ for some element $a$. Then, replacing $a \cdot 1$ with $a + 1$ gives a solution with the higher value. Thus, contradicting that $O$ is an optimal solution.

*Lemma 2:* There exists an optimal solution where all the addition operations happen before the multiplication operations.

*Proof*: For the sake of contradiction, assume that in some optimal solution $O$ there is a multiplication operation followed by an addition operation. Let $a$ and $b$ be the elements involved in multiplication operation. Then, there are two possibilities:

1. Addition operation is done on the output of $a \cdot b$ with some element $c$. That is, $a \cdot b + c$. In this case, $(a+c) \cdot b \geq a \cdot b + c$ since $b$ is a positive integer. There are further two possibilities. The first is that if $(a+c) \cdot b \> a \cdot b + c$, then replacing $a \cdot b + c$ with $(a+c) \cdot b$ gives a solution with the higher value. Thus, $O$ is not optimal, which is a contradiction. The second possibility is that $(a+c) \cdot b = a \cdot b + c$. In this case, the order of the operations can be swapped and the value of the solution does not change.
2. Addition operation is not done on the output of $a \cdot b$; it is done between some elements $c$ and $d$, i.e., $c + d$. In this case the order of the multiplication and addition operations can be swapped and the value of the solution does not change.

*Lemma 3*: In any solution, if there are two addition operations on any variable $a \> 1$, then $(a + 1 + 1)$ can be replaced with $a\cdot(1+1)$. It will only increase the value of the solution or keeps it the same. Thus, we can assume that in an optimal solution there cannot be two or more addition operations on any variable $a \> 1$. In a similar manner, we can show that there cannot be three addition operations on any variable $a = 1$.

*Lemma 4*: Let $a$ and $b$ be the elements such that $b \geq a \> 1$. Then, $(a+1) \cdot b \geq a \cdot (b+1)$. (the proof is trivial)

Based on the above lemmas, the following is a simple greedy algorithm for the problem:

1. If all elements in the array are strictly greater than $1$, then the optimal solution does not contain any addition operation (using Lemma $1$). Thus, the algorithm simply multiplies the elements of the array to get the optimal solution.
2. If the array contains $p \> 0$ elements of the value $1$. Let the set of remaining elements be denoted by $S$. By Lemma $1$ and Lemma $2$, there exists an optimal solution where all the initial operations are addition operations and all the $1$s are one of the operands of these addition operations. By Lemma $3$, there cannot be three addition operations on any $1$. Therefore, all the $1$s can only form the elements of value $3$ or $2$ using the addition operations among themselves. Let $k$ and $\ell$ be the number of $2$s and $3$s obtained using addition operations on $1$s. The algorithm guesses the value of $k$ and $\ell$. The remaining $p' := p - 2k -3 \ell$ elements of value $1$s are directly added with the elements in set $S$. Note that using Lemma $3$, we have that no element in set $S$ can have two or more addition operations. Therefore, by Lemma $4$, the algorithm adds $1$ to each of the top $p'$ smallest elements in $S$. The algorithm does this for each value of $k$ and $\ell$; and then choose the solution with the highest value

---

*Overall Running Time*: $O(n^3)$.

Sorting the elements in $S$ takes $O(n \log n)$ time. Furthermore, there are $n$ possibilities for $k$ and $\ell$ each. For each possibility, finding the value of the solution takes $O(n)$ time. Thus, we get $O(n^3)$ running time.
> 0 votes

---
Tags: greedy-algorithms
---


title: Increasing families of expander graphs

text:
# Question
Title: Increasing families of expander graphs
I would like to know if there is any research dealing with the problem of constructing an increasing family of expander graphs.

The goal is to find a family of **expander graphs** $(G\_i)\_{i \in \mathbb{N}} = ((V\_i,E\_i ))\_{i \in \mathbb{N}} $ satisfying $V\_1 \subseteq V\_2 \ldots \subseteq V\_n$ and $E\_1 \subseteq E\_2 \ldots \subseteq E\_n$ for all $n \in \mathbb{N}$

and more idealy a family where $V\_i = \\{1,2 \ldots, n \\}$.

# Answer
> 3 votes
You can construct such a family, with $|V\_{n+1}| = 2|V\_n|$, using random lifts. The classical work in the area is Bilu and Linial, Lifts, discrepancy and nearly optimal spectral gap. There are several recent papers of Marcus, Spielman and Srivastava on the topic (Interlacing families  and IV), which improve the bounds in the bipartite case; see also Hall, Puder and Sawin, Ramanujan coverings of graphs.

A related notion is *expanding expanders*, see for example Gil Cohan and Itay Cohen, Spectral expanding expanders.

---
Tags: graphs, expanders
---


# Question
Title: Is the class NP closed under complement? (Follow-up)
As a follow up to this question already been asked here, I was wondering - if we supposed that P != NP, would then the following reasoning be correct:

In NP problems we can only verify in poly-time whether x is in L based on the certificate that is also given as input. Hence we could be inputting the wrong certificate and therefore x still is in L even though the output we receive is 0. In this case, NP is not closed under complement as we cannot invert the response of our verifying TM to check for the membership in coNP.

# Answer
As A. Schulz said here, it is not known if $\operatorname{P} \neq \operatorname{NP} \implies \operatorname{NP} \neq \operatorname{coNP}$.

The fact that we don't know how to build a polytime NTM for $\bar{L}$ if we have a polytime NTM that decides $L$ doesn't mean there is no way to do it: we simply don't know.
> 1 votes

---
Tags: np, co-np
---


# Question
Title: solve $T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$ using Akra-Bazzi method
Assume we have this recurrence: $$T(n)=2T(\dfrac{n}{2})+\dfrac{8}{9}T(\dfrac{3n}{4})+\Theta(\dfrac{n^2}{\log{n}})$$ We want to solve it using Akra-Bazzi method. As we know, $\sum\_{i=1}^k\dfrac{a\_i}{b\_i^p}=1$. So $\dfrac{2}{2^p}+\dfrac{\dfrac{8}{9}}{(\dfrac{4}{3})^p}=1$ and we get $p=2$. We know: $$T(n)=\Theta\left(n^p(1+\int\_1^n{\dfrac{f(x)}{x^{p+1}}\text{d}x})\right)$$ Which $f(x)$ is the cost of dividing and merging of the problem. Here, $f(x)=\Theta(\dfrac{n^2}{\log{n}})$. Using Akra-Bazzi method, integrations part converts to: $\log{\log{x}}|\_1^n$. But for $x=1$ the integral is divergent. So, how can I deal with these kinds of problem that integral goes to infinity?

# Answer
It is sufficient for the lower limit of integration to be large enough (see the original paper).

If you pick any $n\_1 \> 1$, $\log \log n\_1$ exists and is just some constant. Then $$\int\_{n\_1}^n \frac{1}{x \log x} \text{d}x = \log \log n - \log \log n\_1 = \Theta(\log \log n),$$ and the solution of the recurrence is $\Theta(n^2 \log \log n)$. For convenience you can pick $n\_1 = e$.

Alternatively, you can rewrite your recurrence replacing $f(n)=\frac{n^2}{\log n}$ with some function $g(n) = \Theta(f(n))$ that yields an integrand that is defined over the domain of integration. E.g., $g(n) = \frac{(2n)^2}{\log 2n}$ results in the integral $$ \begin{align\*} \int\_{1}^n \frac{4x^2}{x^3 \log 2x} \text{d}x&= \int\_{1}^n \frac{4}{x \log 2x} \text{d}x = \int\_{2}^{2n} \frac{4}{t \log t} \text{d}t = \left. 4 \log \log 2t\right|\_{t=2}^{2n} \\ &= 4 \log \log 2n - 4 \log \log 2 = \Theta(\log \log n). \end{align\*} $$
> 0 votes

---
Tags: recurrence-relation
---


title: Can a trie or DAWG loop?

text:
# Question
Title: Can a trie or DAWG loop?
I am looking at DAWGs, which are compressed tries, like this:

It is an *acyclic* graph though, and I'm wondering if you are allowed to create loops or cycles in such a data structure.

For example, I am thinking how to represent and store Turkish words in some sort of trie. Turkish can have almost an infinite number of words, because allows "sentence words" basically. They are formed from a word "base", and a set of suffixes, out of say ~1000 possible suffixes. So you can have upward of 10 suffixes appended to a base, that is 10^10 or at least 10 billion possibilities, on top of say 10,000 base words, that is a lot of possibilities. Maybe there are more or less, not totally sure, but it's probably too many to store in memory on a modest computer (and would be impractical).

So I'm imagining a case where you have a trie composed of the 11000 fragments (bases or suffixes). Each trie node has a `constraint` which says that if it is a "leaf", whether or not it is accepted as a fragment. So say you have these example fragments and composed "words":

**bases**:

```
foo
bar
baz

```

**suffixes**:

```
he
she
be
ke
la
ma
na
pa
po

```

composed **words**:

```
fooheshebelanapo
foo
fooshelapo
barla
bazpomala
...

```

The constraint might say things like:

* You can't repeat a suffix more than once.

So suffixes and words would be marked `leaf: true`, but with a `constraint: 'only-once'` sort of thing on them. As you are traversing the trie, you would keep track of the serialized string you have traversed, and only "accept" the fragment if it statisfies the `only-once` constraint when tested against the serialized string.

```
query: barlala

b: not-accepted
ba: not-accepted
bar: ACCEPTED, now loop back around and start at the beginning of the trie
barl: not-accepted
barla: ACCEPTED, loop back...
barlal: not-accepted
barlala: not-accepted, because we already included that `la` suffix

```

Is this an acceptable data structure? Is there a better way to accomplish it? Once again, this would be 1 trie with 11000 fragments (10k words, 1k suffixes), and they would all loop, with constraints. Is there literature on such a structure, or any problems it will face? Can a DAWG loop basically? Will it solve this problem?

# Answer
> 1 votes
I will try to answer your questions from my personal experience with tries. Some time ago I had to face a similar problem: I had to store all well-formed meaningful Italian words (300'000 more or less) using a trie for detecting duplicates in a text and possibly suggest them to the user during typing. I didn't have the necessity to match suffixes, however. In my use case, the matching algorithm was implemented in C++ and was quite efficient, it could answer in less than 50 milliseconds.

Telling whether the data structure is acceptable depends on you, which time guarantees do you want to achieve? In my case I had to support the user and as we know users are a slow information source.

If I were you I would first try something simpler: I would design the trie for matching words and in case a match exists, switch to a second trie that matches suffixes only. Consequently, the problem of matching suffixes would be captured by the second trie, and constraints could be encoded in the trie rather than annotated on the data structure. This would allow you to trade space for implementation simplicity: you could use the same matching algorithm for both tries. Since I don't know Turkish I don't know which combinations of suffixes make sense, but I would insert in the "suffixes trie" only those combinations that are meaningful. To recap my suggestion is: to collapse contraints in a second trie and see whether it is effective for your use case.

It is even possible the second trie should not be a trie, but the min-DFA matching meaningful suffixes. This would allow you to minimize the space required for matching suffixes, however, you must compute it using well-known algorithms.

Regarding literature, the use case you are mentioning reminds me of the problem considered in this article by Aho and Corasick, however, the encoding of loops in their case does not limit the number of matches you could have. The described automaton has loops but they are encoded through a separate function.

I hope this will be useful!

---
Tags: graphs, data-structures, loops, dag, trie
---


# Question
Title: Given a Tree decomposition, How to find the tree decomposition of its subgraph?
You are given a tree decomposition of a large graph with not so small bounded tree-width.

Suppose now you need to solve a dynamic programming problem inside a subgraph and does not have time to do another costly tree decomposition.

How do I find the tree decomposition of a subgraph given the decomposition of its "father" graph?

(I googled for some data structure inside each bag of the tree decomposition but I haven't found anything.)

Thanks in advance.

# Answer
> 1 votes
A valid tree decomposition of a graph $G =(V,E)$ is also a valid tree decomposition of any subgraph $G' = (V', E') $ provided that you simply remove all vertices $v \in V \setminus V'$ from all the bags.

Let's look at the definition. A tree decomposition $\mathcal T$ of $G$ is a tree of "bags" where each bag is a subset of vertices from $G$ restricted to the following three constraints:

1. The union of all the bags equals $V(G)$
2. Every edge $e \in E(G)$ is in some bag of $\mathcal T$, i.e. if $e = uv$, then there is a bag $B\_i \in V(\mathcal T)$ such that $\\{u,v\\} \subseteq B\_i$, and
3. for every vertex $v \in V(G)$, $\mathcal T\_v$ the subgraph consisting of all bags of $\mathcal T$ containing $v$ is *connected*, i.e., $\mathcal T\_v$ is itself a tree.

Let $\mathcal T$ be a tree decomposition of $G$, let $G' = (V', E')$ be a subgraph of $G$, and let $\mathcal{T'}=\mathcal{T}\_{|V'}$ be the tree $\mathcal T$ but where you delete all vertices not in $V'$.

Clearly (1) the union of the bags in $\mathcal{T}'$ is $V'$, (2) every edge $uv \in E'$ is in some bag in $\mathcal{T}'$ since $\\{u,v\\} \subseteq V'$ and therefore they must be in some bag in $\mathcal{T}$, and (3), the connectivity constraint holds for $v \in V'$ since it holds in $\mathcal{T}$.

# Answer
> 0 votes
To find the tree decomposition of a subgraph, you can first identify the bags of the tree decomposition that correspond to the vertices of the subgraph. Then, you can use these bags to construct a new tree decomposition for the subgraph. To do this, you can start by creating a new bag for the root of the subgraph's decomposition, which consists of the vertices in the subgraph. Next, you can recursively add child bags to the root bag by selecting a vertex in the subgraph and considering its neighbors in the original graph. Each child bag will consist of the vertices in the subgraph that are adjacent to the selected vertex, along with the selected vertex itself. This process continues until every vertex in the subgraph has been included in some bag. This will give you the tree decomposition of the subgraph.

---
Tags: dynamic-programming
---


# Question
Title: Lower Bound on Parity of Boolean Functions
Let's say we have boolean functions $f\_1, \cdots, f\_n$, each of which operates on pairwise disjoint variables (i.e. the variables for each function are unique to that function). Then, how can we show that $L(f\_1 \oplus \cdots \oplus f\_n) \geq \frac{1}{2}\sum\_{i = 1}^n L(f\_i)$ (where we use the De Morgan basis)? Here, we mean $L(f)$ is the size of the boolean function $f$ which is the minimum number of $\wedge, \vee, \neg$ input gates across all boolean circuits that compute $f$.

It makes intuitive sense that you need at least half the bits going into the gates to compute the overall parity, but I'm not exactly sure how to rigorously show this. Also, I suppose the functions should be non-constant or else this lower bound may not hold. I'm not sure we can know what the circuit for $f\_1 \oplus \cdots \oplus f\_n$ looks like, but perhaps there are some theorems that give intuition about the size of such a circuit. Any help is appreciated!

# Answer
This is false, various construction for computing simultaneously the same function on disjoint sets of variables are discussed in this cstheory.stackoverflow question.
> 0 votes

---
Tags: complexity-theory, space-complexity, complexity-classes, lower-bounds, boolean-complexity
---


# Question
Title: Proving lower bound by proving not little o
I have been reading these distributed computing notes. In some of the proofs, for proving lower bound of $\Omega(f(n))$, we prove that no algorithm which solves the problem in $o(f(n))$ exists.

I can't see how not having a $o(f(n))$ algorithm proves the lower bound is $\Omega(f(n))$.

I tried using the definitions, but not having an $o(f(n))$ algorithm implies, for all algorithms $\exists c\>0 $ such that $\forall n\_0 \exists n \geq n\_0$ such that there exists an input of size $n$ which takes at least time $cf(n)$.

For $\Omega(f(n))$, we would require $\exists c\>0,n\_0 $ such that $\forall n \geq n\_0$ there exists an input of size $n$ which takes at least time $cf(n)$.

Any help is appreciated, thanks.

# Answer
Your confusion is completely justified.

When we say that some problem $A$ has a lower bound of $\Omega(f(n))$ usually we mean that "No algorithm that runs in time $o(f(n))$ solves $A$" or equivalently, "there is an infinite class of instances for which any algorithm that solves $A$ requires time at least $cf(n)$ for some constant $c\>0$".

This matches the Hardy-Littlewood version of the $\Omega(\cdot)$ notation.

This is in contrast with "any algorithm that solves $A$ requires time at least $cf(n)$ on all sufficiently large instances", which is what you were expecting.
> 1 votes

---
Tags: time-complexity, lower-bounds
---


# Question
Title: What happens for hardware Interrupts in non-preemptive scheduling?
In non-preemptive scheduling, the running process cant be interrupted .But what will when the CPU receive a hardware interrupt such as the an interrupt from the printer indicating that the current job has been completed ? Does the CPU will preempt the current running process and handles the interrupt ( run its interrupt service routine ) or this interrupt will be stored and then handled when the current running process leaves the CPU ?

# Answer
> 1 votes
In a non-preemptive scheduler, the running process cannot be interrupted by **another process**. The running process **can** be interrupted by hardware interrupts.

---
Tags: operating-systems, process-scheduling
---


title: Time complexity of search algorithms?

text:
# Question
Title: Time complexity of search algorithms?
Can we prove that classical search algorithms cannot do better than a binary search algorithm with complexity $O(log(n))$ ? If so, how do we prove it?

# Answer
> 1 votes
Let $A$ be a comparison-based search algorithm that takes a collection $C$ of $n$ elements and an element $x$ as input and outputs the position of $x$ in $C$, or reports that $x \not\in C$.

Let $c(n)$ be the maximum number of comparisons performed by $A$ over all possible inputs where $C$ has $n$ elements. Since $A$ needs to be able to return $1+n$ different outputs, and each comparison can only return two different outcomes, we need to have $2^{c(n)} \ge n+1$, hence $c(n) \ge \lceil \log(n+1)\rceil = \Omega(\log n)$. The number of comparisons is also a lower bound to the running time of $A$.

---
Tags: complexity-theory, search-algorithms, lower-bounds
---


# Question
Title: Is the class of star-free languages just the complement to counter languages within the regular language class?
So I'm kind of confused as I'm not that deep into the algebraic theory of languages.

The wikipedia article states:

> Another way to state Schützenberger's theorem is that star-free languages and counter-free languages are the same thing.

What does counter-free languages mean here?

Let's say that $CL$ denotes the class of counter languages, i.e. the languages that a DFA emplyong one or more counters can accept \[e.g. $(a^nb^{n+1})\*$\]. Clearly, for the class of regular languages $R \subset CL$.

Now I don't quite get what the class counter-free $CF$ is meant to represent here. Is it just the complement to counter-languages within the regular language class?

I.e. more precisely, my question would be:

$SF = CF \stackrel{?}{=} R \setminus CL$

This means: are regular languages either star-free or a counter language?

Thank you in advance!

Edit: Made things more clear

Edit 2: Ok the below resolved this

$SF = CF \neq R \setminus CL$

# Answer
These languages families are related by similar names only, both formalisms have their own relation to the concept of counting.

The beauty of regular languages is that they can be defined using (finite) automata, (regular) expressions and (monadic second order) logic. The Myhill-Nerode theorem shows that (minimal deterministic) automata are precisely equivalent to the algebraic syntactic monoid defined by the language.

Surprisingly (at least to me) there is a subfamily of the regular languages that has similar but restricted characterizations. Star-free languages are defined by operations (boolan operations and concatenation, no star). They can be characterized by either aperiodic syntactic monoids or first-order logic (Results by Schützenberger, McNaughton and Papert). The aperiodic monoid characterization can be rephrased as counter-free languages. In my intuition counter-free means we cannot hide a (modulo) counter inside the language: there is an integer $n$ such that for all words $x, y, z$ and integers $m \ge n$ we have $xy^mz \in L$ if and only if $xy^nz \in L$. https://en.wikipedia.org/wiki/Aperiodic\_finite\_state\_automaton

The counter-automata start from pushdown automata with a single pushdown symbol (plus bottom-of-stack) which can basically only count up and down and check whether their counter equals zero. Thus one-counter languages are a subfamily of the context-free languages. It includes all regular languages. https://en.wikipedia.org/wiki/Counter\_automaton

With two or more counters one can simulate a Turing machine by encoding the tape as a pair of numbers. This is nontrivial.
> 2 votes

---
Tags: formal-languages, regular-languages, formal-grammars, kleene-star
---


# Question
Title: Roles of 80386 MMU Paging Unit and similarity with modern CPU MMU
While searching for the structure of the MMU, I found the image below (80386 Internal Architecture).

I have three questions.

**Q1. I'd like to know the roles of 'Adder', 'Page Cache', and 'Control and Attribute PLA'.**

I found some description for 'Control and Attribute PLA' (link below), but I still can't understand it. https://www.pcpolytechnic.com/entc/pdf/architecture%20pdf.pdf

"The control and attribute PLA checks the privileges at the page level."

**Q2. Does Modern CPU MMU (like the Intel core series) use a structure similar to 80386 MMU?**

**Q3. If not, How is it structured?**

# Answer
> 1 votes
That's three questions, but I'll try my best. I looked at other techincal papers about the i386, and this is my best guess.

**1. I'd like to know the roles of 'Adder', 'Page Cache', and 'Control and Attribute PLA'.**

I can't work out why there's an adder in the paging unit. It's not needed in the i386 to calculate page table entries or the final physical address because everything can be done with simple wiring.

I'm 99% sure that the "page cache" is what would, in more customary terminology, be called a Translation Lookaside Buffer. The purpose is to cache page table entries so that the CPU does not need to traverse the page table structure on every memory access.

A PLA is one way to design combinational circuits. The main job of the PLA is presumably to ensure that the memory access is not a page fault, such as if the instruction attempts to write to a read-only page.

**Q2. Does Modern CPU MMU (like the Intel core series) use a structure similar to 80386 MMU?**

Surprisingly, yes. There are a few differences for the modern era, such as:

* Support for large pages, and larger physical memories (e.g. PAE).
* Support for 64-bit addressing. In 64 bit mode (called "long mode" in Intel-speak), some of the 286 and 386-era protection mechanisms are not supported, and neither is segmentation.
* Support for process context identifiers (PCID). The idea is that TLB entries can be tagged with the process id that they belong to, so that the TLB does not need to be flushed on every context switch.
* Instructions (and hardware to support them) to selectively invalidate individual TLB entries. This is required to support virtual memory coherency among multiple CPUs.

This complicates the control logic, but the overall structure is quite similar.

Non-Intel CPUs don't always work the same way, however. MIPS and Alpha, for example, have a software-managed TLB, so that operating systems can implement their own cache policies. But you specifically asked about Intel/AMD/etc, so that's not relevant here.

---
Tags: operating-systems, memory-management, cpu
---


# Question
Title: Union of non regular and regular language
So I have a regular language L and a non-regular language L' and i want to proof wether the union of both is regular or not.

Since I found counterexamples for both cases I want to look at more distinct cases to show when the union is regular and when it isn't:

case 1: L ⊆ L'

case 2: L ⊇ L'

case 3: L ∩ L' regular

case 4: L ∩ L' not regular

case 5: L U L' = Sigma\*

I am not really sure about those cases and im stuck at case 4.

Is there a better approach? How can i prove case 4? What do you think?

# Answer
Cases $1$, $2$, and $5$ are trivial:

* If $L \subseteq L'$ then $L \cup L' = L'$, which is non-regular by hypothesis.
* If $L' \subseteq L$ then $L \cup L' = L$, which is regular by hypothesis.
* When $L \cup L'' = \Sigma^\*$ this language is clearly regular.

If $L \cap L'$ is regular then you cannot conclude anything about $L \cup L'$, indeed:

* When $L=\emptyset$, $L \cap L' = \emptyset$ is regular and $L \cup L' = L'$ is not regular.
* Let $L$ be the set of all words that start with $0$, and let $L'$ be a non-regular language such that all words in $L'$ start with $1$ (e.g., $L' = \\{1^n0^n \mid n \ge 1\\}$). Then $L \cap L' = \emptyset$ is regular and $L'' = L \cup L'$ is not regular. Indeed, if $L''$ were regular, the closure properties of regular languages would imply the regularity of $L'' \setminus L = L'' \setminus (L'' \cap L) = L'' \setminus \emptyset = L'$, which is a contradiction.

If $L \cap L'$ is not regular then you cannot conclude anything about $L \cup L'$, indeed:

* When $L=\Sigma^\*$, $L \cap L' = L'$ is not regular and $L \cup L' = \Sigma^\*$ is regular.
* When $L=\\{0^{2n} 1^{m} \mid n,m \ge 0\\}$ and $L' = \\{ 0^n 1^n \mid n \ge 0 \\}$, $L \cap L' = \\{ 0^{2n} 1^{2n} \mid n \ge 0\\}$ is not regular and $L'' = L \cup L'$ is not regular. If $L''$ were regular, then so would be $L'' \setminus L = \\{0^{2n+1} 1^{2n+1} \mid n \ge 0\\}$. However a simple application of the pumping lemma shows that $L'' \setminus L$ is not regular.
> 1 votes

# Answer
Given regular $R$ and nonregular $N$ you investigate whether their union $R\cup N$ is regular or not, and you state that you are aware that the outcome depends. Now you consider special cases. Two of these cases consider the intersection $R\cap N$ of both languages.

It turns out that not this intersection, but the set difference $N \setminus R$ (everything in $N$ that is not already in $R$) determines whether the union is regular.

**Claim.** $R\cup N$ is regular iff $N \setminus R$ is regular.

This follows from the closure properties of the regular languages, as follows.

**(1)** If both $R$ and $R\cup N$ are regular, then so are their boolean combinations. Thus $N \setminus R = (R\cup N) \setminus R$ is regular.

**(2)** Similarly, if both $R$ and $N \setminus R$ are regular, then so is $R\cup N = R \cup (N \setminus R)$.

Intuitively the staement of the Claim is clear. When adding $N$ to regular $R$, the part $R\cap N$ is already in $R$. It is the new part $N\setminus R$ that determines regularity.
> 1 votes

---
Tags: formal-languages, regular-languages, proof-techniques, check-my-answer
---


# Question
Title: Is there a model for the given logical formula, and if not, why?
I'm trying to determine whether there exists a model for the following logical formula: $(p\_1 \to (p\_2 \lor p\_3)) \land(p\_2 \to \neg p\_3) \land ((p\_1 \lor p\_3) \to \neg p\_2)$. Here's my understanding of the formula: If p1 is true, then either p2 or p3 must be true, and if p2 is true, then p3 must be false. However, this seems to create a conflict because if p1 is true, p2 cannot be false. Can anyone confirm whether a model exists for this formula or explain why it might not be possible? Thank you!

# Answer
> 1 votes
Set all variables to false, that way each implication has a false left-hand-side and thus it's satisfied.

# Answer
> 0 votes
Be lazy: encode your problem in the input language of your favourite SAT solver and feed the resultung term to it. If it answers "SAT" it'll also provide a model. If not, then there's no model.

---
Tags: logic, propositional-logic, model-checking
---


# Question
Title: Complexity of simulations in simulations
This video of a group, who simulated (a very simple version of) Minecraft inside Minecraft itself got me thinking about the performance of such setups.

Another example to what I'm referring to, would be Conway's Game of Life simulating itself.

The first example runs through a bunch of modifications at 0.1fps and the second example is obviously also significantly slower than the original.

Can something be said about the performance/complexity of such systems, besides that they obviously have to be way slower than the original they're simulating?

Bonus question: Maybe the question could be more precise posed as 'How many states does a Turing machine need at minimum, if it simulates another Turing machine with N states?', but I assume if one interprets "simulating" as producing the same output for the same input, the answer is simply N?

(I am not sure that I'm not confusing space- and time complexity with the second question. The main question is about time complexity.)

# Answer
> 2 votes
You can build a universal Turing machine with only 7 states, or only 15 states if you require that the tape store binary symbols. See https://en.wikipedia.org/wiki/Universal\_Turing\_machine#Smallest\_machines.

It follows that there is always a way to simulate a Turing machine with N states, using a Turing machine with 15 states. So the minimum is guaranteed to be small, even if N is very large.

As far as your question about the time complexity of simulating a machine of type A with a machine of system B, the answer depends on A and B. Often it will be possible to simulate efficiently (e.g., in linear or quadratic time), but it depends on what A,B are (Turing machines? RAM machines? tag systems? Conway's game of life? Magic the Gathering decks?).

---
Tags: complexity-theory, turing-machines, computability, recursion, simulation
---


# Question
Title: Counting the expected number of CPU cycles for n-number of assembly instructions
I was trying to count the cpu\_cycles from an ARM processor 4 core Cortex A78 to be exact) using the PMU registers. Now, at the beginning, I read the cpu cycles counter register, then for test just run one `asm("nop")` and then read the cpu cycles register back. I consistently get the result 7. At this point, if I add up to 15 more `nop` instructions, I still get 7 cycles. After this point, every 4 instructions gives me 1 more cycle.

Tried with the following instead of `nop`:

```
  asm volatile ("ADD %w[result], %w[in1], %w[in2]"
            : [result]"=r"(i)
            : [in1] "r" (i), [in2] "r" (j));

```

And get the same exact results.

I would like to understand why this is the case. Is it due to pipeline that I see this effect? Thank you in advance.

# Answer
> 1 votes
Two effects:

1. instructions measuring cycles have their own effects and they can't be used for such a small code snippet. they are better used for code running for thousands of cycles
2. Modern CPUs are OoOE and they execute multiple instructions per cycle and in arbitrary order. before trying to measure anything you have to learn how it works at all

---
Tags: computer-architecture, performance
---


# Question
Title: Dinitz’ algorithm in simple unit-capacity networks
I am studying for an algorithm design course, and can't understand this demonstration about how Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.

This is what is written on the slides I am reading:

> Theorem. \[Even–Tarjan 1975\] In simple unit-capacity networks, Dinitz’ algorithm computes a maximum flow in $O(m \sqrt{n})$ time.
>
> Pf.
>
> ・Lemma 1. Each phase of normal augmentations takes $O(m)$ time.
>
> ・Lemma 2. After $\sqrt{n}$ phases, $val( f ) ≥ val( f \*) – \sqrt{n}$.
>
> ・Lemma 3. After $≤ \sqrt{n}$ additional augmentations, flow is optimal.

I think I get the first lemma: normal augmentation phase takes up to $O(m)$ because this is the cost of generating a level graph $L\_G$. However, I have not understood what exactly happens after the "normal" augmentation (in what does the "special" augmentation phase consist? How many "phases" are needed?)

I have no clue about how the values in the other two lemmas are brought up. Could someone help me understand it?

Here are the slides I am referring to, in particular the ones between 92-96

Thanks a lot

# Answer
> 1 votes
> I have no clue about how the values in the other two lemmas are brought up.

The *how* is this: What are the values $a$ and $b$ such that $ab = n$ and $O(a + b)$ is minimized?

The answer is $\sqrt n$, and that value is *chosen* in the argument above for that precise reason.

After $\sqrt n$ phases, we know that the BFS layer graph must have *at least* $\sqrt n$ many layers, which means that there is a layer with *at most* $\sqrt n$ many vertices. But if there is a layer with at most $\sqrt n$ many vertices, then the $s$-$t$-cut is at most $\sqrt n$ in this graph.

To see this: Let $L\_i$ be a layer with $\leq \sqrt n$ many vertices. And let $L\_i^\leftarrow$ be the set of vertices in $L\_i$ with *exactly one in-edge*, and let $L\_i^\rightarrow$ be all other vertices in $L\_i$ (they all have *exactly one out-edge* since $G$ is a unit-capacity network). Notice that $L\_i^\leftarrow, L\_i^\rightarrow$ partitions $L\_i$.

Now, let $A$ be the set of vertices in layers $L\_j$ for $j \< i$, plus $L\_i^\leftarrow$. You should be able to draw a figure that convinces you of the fact that the capacity of the cut $A,B$ is at most $\sqrt n$.

This implies that $v(f) \geq v(f^\*) - \sqrt n$.

But then, after an additional $\sqrt n$ phases, we have reached $v(f^\*)$.

Hence, after at most $2\sqrt n$ phases, we have reached the optimal flow. Since each phase can be performed in time $O(m)$, the algorithm runs in time $O(\sqrt n)$.

---
Tags: complexity-theory, graphs, network-flow, bipartite-matching, bipartite-graph
---


# Question
Title: Find a substring length $k$ with maximum occurrences
Given a string length $S$, find a substring length $k$ that has the most occurrences in the given string.

We want $O(S)$ time complexity in an average case.

I think the solution lies in sophisticated use of *Rabin-Karp algorithm*.

I've tried to use the sliding window method, but that results in $O(S * k)$ time complexity, because when inserting into the hash table we have to actually compare the substrings in $O(k)$ time.

So how can I improve it to the desired time complexity?

# Answer
> 0 votes
Each substring occurrence of your length $k$ pattern is the suffix of a of a substring. As such, a *suffix tree* will provide a fast way to store all possible suffixes and - in particular in your case - all substrings of length $k$, as well as provide a way to detect when you are reading a $k$-substring that has been seen before.

In your particular case of only caring about length $k$-substrings, you can improve the suffix tree to only keep nodes up to depth $k$ as you don't need to go beyond that.

Suffix trees give $\Theta(n)$ runtimes for a lot of String-processing problems. See a list of such problems on the wiki page: https://en.wikipedia.org/wiki/Suffix\_tree

---
Tags: algorithms, data-structures, strings, big-o-notation, hash-tables
---


title: Which one is an LL(2) but not an LL(1)

text:
# Question
Title: Which one is an LL(2) but not an LL(1)
I'm pretty sure b and d are ll2 and not one but not 100% sure.

(a) S → aaScc | aaBbc | aaBbb | aBb | ac | Ʌ
B → aBb | Ʌ

(b) S → aaScc | aaBbc | aBb | ac | Ʌ
B → aBb | Ʌ

(c) S → aaScc | aaBbc | B | ac | Ʌ
B → aBb | Ʌ

(d) S → aaScc | aaBbc | B | ac
B → aBb | Ʌ

# Answer
> 1 votes
Prove that you always know what rule to apply if you know the next two symbols. Then show a sentence where knowing only the next symbol doesn’t determine the next rule.

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