# Question
Title: Constructing a crown graph given an independent set
A **crown** in a graph $G$ is a pair $(H, C)$, where $H \subseteq V(G)$ and $C \subseteq V(G)$ with $H ∩ C = ∅$ such that the following conditions hold:

(a) The set of neighbors of vertices in $C$ is precisely $H$, i.e. $H = N(C)$,

(b) $C = C\_m \cup C\_u$ is an independent set, and

(c) There is a perfect matching between $C\_m$ and $H$

**Theorem**:

Any graph $G(V,E)$ with an independent set $I$, where $|I| ≥ \dfrac{2n}{3}$ , has a crown $(H, C)$, where $H ⊆ N(I), C ⊆ I$ and $C\_u \ne ∅$, that can be found in time $O(nm)$ given $I$. $(n=|V|, m = |E|)$

---

I am trying to code an algorithm to find such a crown in $O(nm)$ time

The only way I could think of finding a crown given an independent set is to take subsets of the set: $I$ and check for all the three conditions of a crown. However, taking all subsets of $I$ will take exponential time right? How to find it in $O(nm)$ time. I just want an algorithm with polynomial time. It need not be $O(nm)$... It can be in the form $O(n^c m^d)$ where $c,d$ are constants.

# Answer
> 2 votes
In the book Kernelization by Fomin, Lokshtanov, Saurabh, Zehavi (which is downloadable as a PDF on the first author's homepage) you find **Chapter 4. Crown decomposition**. This should point you to the answer.

---
Tags: algorithms, graphs, data-structures, trees, parameterized-complexity
---


# Question
Title: Algorithm to check two binary expression trees for equivalence
Is there any known algorithm to check for equivalence of two binary expression trees over a field $\mathbb{F}$?

For example for the expression $a+b = b+a$ it should return true (since $\mathbb{F}$ is commutative) and $a^b = b^a$ should return false as well as for $a^2 = a$.

I can think of a naive implementation which is basically brute-force creating all equivalent binary expression trees for LHS and for RHS and check for a non empty intersection.

Is there a real-world-efficient algorithm to do this? I mean it isn't a must to be polynomial time but will work fast for common or relatively small problems (trees with at most ~100 nodes).

Wikipedia doesn't give any reference to the problem of comparing two for equivalence over some algebraic structure.

# Answer
The answer depends heavily on what operations you allow to appear in the trees.

If the tree uses only addition, subtraction, and multiplication, this is an instance of the polynomial identity testing problem, which can be solved in polynomial time by a randomized algorithm. Basically, you pick random values for $a,b$ and check whether both trees return the same value; and repeat a few hundred times. See https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel\_lemma and Is there an efficient algorithm for expression equivalence?.

Division can also be handled by expressing the tree as a rational polynomial (ratio of two polynomials), then again using polynomial identity testing.

If you can have addition, subtraction, multiplication, division, and exponentiation, then I don't know whether there are efficient algorithms. I think that problem, or some variant of it, is addressed here: Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials.

---

(Possibly loosely related: Decidability of Equality of Radical Expressions)

Let me also highlight that expressions like $a^b$ "smell fishy" and don't typecheck when $a,b \in \mathbb{F}$ are elements of a finite field. For instance, if $\mathbb{F}=GF(p)$, then exponentiation $a^b$ is well-defined if $a$ is taken modulo $p$ and $b$ is taken modulo $p-1$ (not modulo $p$). In particular, $(a+p)^b=a^b$ modulo $p$, but $a^{b+p} \ne a^b$ modulo $p$. So, to make an expression like $a^b$ make sense, $a^b$ has to be interpreted as $a^{f(b)}$ where $f$ maps from elements of $GF(p)$ to numbers $\\{0,1,\dots,p-2\\}$. There is a natural way to do that, e.g., $f(0)=0$, $f(1)=1$, ..., $f(p-2)=p-2$, $f(p-1)=0$. But then when you do that, exponentiation doesn't have the properties you might expect. In particular, $a^{b+c}$ is no longer equal to $a^b \times a^c$. For instance, if $b=1$ and $c=p-1$, then $a^{b+c}=a^{p-1+1}=a^0=1$, but $a^b = a^1 = a$ and $a^c = a^{p-1} = 1$, so $a^{b+c}=1$ but $a^b \times a^c = a$. So I would be pretty suspicious of any expression that contains exponentiation where the expression in the exponent is an element of $\mathbb{F}$.
> 7 votes

---
Tags: algorithms, graphs
---


# Question
Title: How to prove the existence of the spectral expander with the given parameteres?
I need to prove the existence of the $(1944, 144, 0.5)$ spectral expander. I tried to construct it using tensor product of the following graphs: $$ (1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (24, 16, 0.5) $$ I already know that expander with parameters $(9^2, 9, 1/3)$ exists and corresponds to the affine expander, but I am not sure about $(24, 16, 0.5)$ one.

# Answer
There are also expanders with the following parameters: $(3, 2, 1/2)$ — complete graph on 3 vertices and $(8,8, 0)$ — complete graph on 8 vertices with the loop in each vertex. So we have the following tensor product: $$ (1944, 144, 0.5) = (9^2, 9, 1/3) \otimes (3, 2, 1/2) \otimes (8,8, 0) $$
> 0 votes

---
Tags: graphs, regular-expressions, expanders
---


# Question
Title: What is the right data structure for MST in a stream
In a single pass stream you can compute the minimum spanning tree (MST) in an undirected graph using the following algorithm:

```
H ← ∅
for each (u,v) in the stream
    H ← (u, v)
    if H includes a cycle
            remove largest weight edge in the cycle

```

To make this fast we need a data structure that allows you to check if (u,v) makes a cycle and also allows you to remove the largest weight edge from a cycle.

What is a suitable data structure for this?

# Answer
> 1 votes
By noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens, you can use a ST-Tree\[1\], which you can easily modify to support queries of the form "what is the maximum weight edge on the path from $a$ to $b$"

Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find). If they are not, you add it as possible. Otherwise, if its weight is smaller than $max( a \to b)$, you replace with $(a,b)$ the max. weight edge.

\[1\]https://en.wikipedia.org/wiki/Link/cut\_tree

---
Tags: algorithms, data-structures, streaming-algorithm
---


# Question
Title: Finding values in a space that matches a relational query
Assume we have 26 vectors ${A,B,C,....,Z}$ all have 1 million integers. given a query: $$ \vec{query} = (r\_a, r\_b, r\_c, ..., r\_c) $$ I want to find a match vector $\vec{m\_{1 \times 26}} = (a, b, c, ..., z)$ that satisfies the following criterias:

$$ a \in A, b \in B, c \in C, ..., z \in Z \\ \text{and} \\ r\_{a} = \frac{a}{\sum\_{\theta \in m}{\theta}}, r\_{b} = \frac{b}{\sum\_{\theta \in m}{\theta}}, ..., r\_{z} = \frac{z}{\sum\_{\theta \in m}{\theta}} $$ in which $\sum\_{\theta \in m}{\theta}$ is basically sum of the values in vector `m`. In other words, let say given the amount of share each $a, b, c, ..., z$ has in my math vector `m`, I want to find the elements. Of course, one yet not feasible solution is checking all ${(10^6)^{26}}$ possible combinations and check if there exists any match. There could be multiple answers, but any of them is fine.

**Example:** Let say all ${A,B,C,....,Z}$ are equal to each other and contains elements between $1$ and $10^6$ like $\\{1,2,3,...,10^6\\}$. given query $\vec{query} = (\frac{1}{26}, \frac{1}{26}, \frac{1}{26}, ..., \frac{1}{26})$, $m$ is one of the many possible solutions: $$ \vec{m} = (1,1,1,...,1). $$

My question is, what could be the fastest algorithm for solving this problem?

# Answer
> 1 votes
One approach is to guess $a$ (i.e., iterate over all possibilities for it, and the following for each possibility). Then, you can infer the value of $b$, namely, $b = a r\_b/r\_a$, so test whether $b \in B$. Do the same for each of $c,\dots,z$. If they all work, then you have found a solution; otherwise, proceed on to your next guess at $a$. This should give you approximately a linear running time if you use the right data structures for storing the vectors (e.g., a hashtable).

A similar approach is to compute the vectors $A/r\_a$, $B/r\_b$, ..., $Z/r\_z$, and then look for an item that occurs in all of those scaled vectors, e.g., using a hashtable or a counter or by sorting and merging the sorted lists.

---
Tags: algorithms
---


# Question
Title: Linear program for min-length pair of edge-disjoint paths problem
Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}\_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, B)$ of edge-disjoint paths between $s$ and $t$ such that $$ \sum\_{e \in A}l(e) + \sum\_{e \in B} l(e) \to \min $$ How can I formulate this problem in terms of ILP ?

# Answer
> 2 votes
I think this can be solved in polynomial time by finding a minimum-cost maximum flow in the graph, where you set the capacity of each edge to $1$ and the cost of each edge $e$ to $-l(e)$, and add a source node $s\_0$ with an edge $s\_0 \to s$ of capacity 2 and cost 0. (You might need to add a "demand" that the edge $s\_0 \to s$ has exactly 2 units of flow along it.)

If you must formulate it as an ILP, introduce a zero-or-one variable $x\_e$ for each edge, with the intended semantics that $x\_e=1$ means that edge $e$ is in the first path. Add a constraint that, for each vertex $v$ other than the source/sink, $\sum\_w x\_{(v,w)}$ is 0 or 2; for the source and sink, it must be 1. This captures the requirement that you have a path from $s$ to $t$. Add another zero-or-one variable $y\_e$ for each edge, with similar constraints to ensure it represents a path from $s$ to $t$. Finally, enforce the disjointness requirement: $x\_e + y\_e \le 1$. The objective function to maximize is $\sum\_e l(e) x\_e + l(e) y\_e$.

You can enforce a constraint that a variable $z$ is 0 or 2 by requiring $z=2t$ where $0\le t \le 1$ is a fresh zero-or-one integer variable.

# Answer
> 1 votes
**Optimization Function:** *minimize* $\sum\_{e \in E} l(e) \cdot x\_{1}(e) + \sum\_{e \in E} l(e) \cdot x\_{2}(e)$

**Constraints:** $$\sum\_{(u,v) \in C} x\_{1}(u,v) \geq 1 \quad \textrm{for every $(s,t)$ cut $C$ in the graph}$$ $$\sum\_{(u,v) \in C} x\_{2}(u,v) \geq 1 \quad \textrm{for every $(s,t)$ cut $C$ in the graph}$$ $$x\_{1}(u,v) + x\_{2}(u,v) \leq 1 \quad \textrm{for every edge $(u,v) \in E$}$$ $$x\_{1}(u,v), x\_{2}(u,v) \in \\{0,1\\} \quad \textrm{for every edge $(u,v) \in E$}$$ **Correctness:**

* For an edge $e = (u,v)$, $x\_{1}(e) = 1$ denotes if $e$ is in the path $A$; otherwise $x\_{1}(e) = 0$. Similarly, $x\_{2}(e) = 1$ denotes if $e$ is in the path $B$; otherwise $x\_{1}(e) = 0$. Note that I have used the variables $x\_{1}(e)$ and $x\_{1}(u,v)$ interchangebly.
* The first constraint is for path $A$ from $s$ to $t$.
* The second constraint is for path $B$ from $s$ to $t$.
* The third constraint makes the paths $A$ and $B$ disjoint.

---
Tags: graphs, shortest-path, linear-programming, integer-programming
---


# Question
Title: Insertion sort Pseudo code vs implementation?
So I'm trying to implement an `insertion sort` algorithms based on page 18 Cormen psuedocode but I'm confused by `for j = 2 to A:length`. Specifically, what does the `j=2` mean? I'm implementing it using the below python code and it only works when the range is the entire length of the array:

```
def insertion_sort(arr):
    # length of array
    n = len(arr)

    # traverse through array
    for i in range(n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

```

Could someone explain?

# Answer
> 1 votes
The following two points might clear your confusion.

1. The pseudocode in the book is following $1$ based indexing. Your code is following $0$ based indexing.
2. Your code is technically doing nothing in the first iteration of the while loop. In the first iteration $i = 0$, therefore $j = -1$. Since $j\<0$, the inside while loop is not executed. And it keeps $A\[0\] = key$ to its original value. Effectively, your code starts executing from $i = 1$, which is equivalent to $j = 2$ in CLRS implementation.

---
Tags: sorting, python
---


title: DFA for language

text:
# Question
Title: DFA for language
I want to give a DFA for the language which contains the words X ∈ {0,1,2}\* for which the number of 0's + number of 1's is even AND the number of 1's + the number of 2's is odd.

I tried many automatons so far but I haven't succeeded with any.

# Answer
**Hint**. Whether or not a word $u$ belongs to your language only depends on the parity of two parameters: $x(u) = |u|\_0 + |u|\_1$ and $y(u) = |u|\_1 + |u|\_2$. Computing modulo $2$, this gives you four states, $(0, 0), (0,1), (1,0), (1,1)$. It remains to find the transitions. For this, you just have to compute $x(uc)$ and $y(uc)$ for each letter $c \in \\{0, 1, 2\\}$.
> 2 votes

---
Tags: complexity-theory, automata, finite-automata
---


# Question
Title: Can synchronous data transfer be used for transferring large data in case of computer architecture and organization?
I am learning computer architecture and organization.

> I have this confusion, can synchronous data transfer be used for transferring large data in case of computer architecture and organization?

I have read that synchronous data transfer can be used for transferring large data but I think it is true only in case of computer networks, in case of computer architecture and organization I think DMA is used for transferring large data. So if someone asks me if synchronous data transfer be used for transferring large data in case of computer architecture and organization. Should I say yes or no?

# Answer
> 2 votes
I think that the question has no clear answer. Data can be transferred in a synchronous or asynchronous manner. Each has its own pros and cons. Synchronous communication is irrelevant for some systems, e.g., when there is no joint clock or where the distance causes too large clock skews. Both methods are capable of transferring large amounts of data. For instance, USB is kinda asynchronous, in the sense it has no clock (it uses synchronization strings to maintain synchronization) and yet it is capable of transferring large amount of data.

DMA is a mechanism within some chip that allows transferring data (small amount or large amount) without the involvement of the CPU. Within a chip most communication is synchronous (there are exceptions). However, the DMA communication might have gaps within its transmissions as the BUS might be needed for the CPU. It might depend on the exact mode of DMA operation.

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


# Question
Title: Turing machine generating $a^b$ for given a and b
I want to draw an state diagram for a Turing machine such as:
If "a" and "b" are the inputs, output in tape will be $a^b$.

I saw many Turing machines that output:

$a+b$ $~~$ ,$~~$ $a-b$ $~~$ , $~~$$a\*b$ $~~$ ,$~~$ $a/b$

And also I know how to design a Turing machine for **accepting** $x^{2^n}$,$x^{3^n}$ and ... But for **generating** I have no idea...

**Question 1:**

Is it possible to improve $a\*b$ Turing machine inorder to generate $a^b$ ? How ?

**Question 2:**

Should we add more than one tape to this machine or thats easy to show even with only one tape?

# Answer
> 1 votes
1. It is possible. Practically, $a^b=a\*a\*a\*\dots\*a$, hence can be computed using a combination of the multiplication turing machine (to compute the multiplications), and the subtraction TM, in order to count the number of multiplications.
2. There is a reduction from multiple tapes TM to a single tape TM, so anything possible with multiple tapes is also possible with a single tape (with increased time complexity). To see why, try to think of the "even" spots in a tape as one single tape, and all the "odd" spots as another tape. This allows us to effectively place any number of TM tapes inside one single tape, but if you look carefully into the way its implemented you will see that it will come at the cost of increased time complexity (specifically, its bounded by the space complexity times the time complexity of the multiple tape machine)

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


# Question
Title: Proof that class of languages accepted by DPDA by empty stack is not closed under union
My first intuition was to take two languages $L\_1$ and $L\_2$ (symbol $d$ at the end is to fulfill prefix property):

$$L\_1 = \\{ a^i b^i c^j d : i,j \ge 0 \\} \mathrm{\ \ and\ \ } L\_2 = \\{ a^i b^j c^j d : i,j \ge 0 \\}$$

So their union would be: $ L = L\_1 \cup L\_2 = \\{ a^i b^i c^k d : i=j \lor j=k \\} $

Then to prove $L$ not even being DCFL (e.g. in similar way as *Example 10.1* from "*Introduction to Automata Theory, Languages, and Computation*" by Hopcroft & Ullman).

Big inconvenience would be the need to include in the proof also the proofs of all other properties (assuming this class is - just as "regular" DCFL - closed under complement etc.)

---

But I was told that precisely because the question is about DCFL being accepted **by empty stack**, the proof is actually trivial and could be expressed in just few sentences.

# Answer
> 1 votes
Indeed, the requirement that the DPDA accepts by empty stack has some "severe" consequences.

Under the standard definitions, an automaton with empty stack is blocked from further computations, as normally one would pop a stack single symbol at each computational step. As a consequence DPDA languages by empty stack are *prefix-free*: if the accepted language contains a string $x$ then it will not contain any string $xy$ with $y\neq \varepsilon$.

Now the language $\\{a,aa\\}$ is an easy counterexample.

---
Tags: formal-languages, pushdown-automata, closure-properties, nondeterminism
---


# Question
Title: How to sort an array $A[1..n]$ where all but $\lfloor \sqrt n \rfloor$ elements are integers in range $\sqrt n$ to $n\sqrt n$, at $\Theta(n)$ time?
Without the unknown $\lfloor \sqrt n \rfloor$ elements this question wouldn't be hard.

After a long time trying to solve the question, the best partial idea I have is to use *Radix sort* for the $n-\sqrt n$ elements which are in the given range. Then I would need to sort the $\lfloor \sqrt n \rfloor$ elements in a decent time.

Any help would be much appreciated.

# Answer
In the rest of the answer I will slightly abuse the notation by treating $A$ as a set. For simplicity I will also assume that the integers to sort are distinct, so that we are dealing with sets instead of multisets. This assumption is easy to remove.

Construct a min-heap $H^-$ and a max-heap $H^+$, each containing all elements in $A$. Extract the minimum $\lfloor \sqrt{n} \rfloor$ times from $H^-$ and let $S^-$ be the set of the extracted elements. Similarly, extract the maximum $\lfloor \sqrt{n} \rfloor$ times from $H^+$, and let $S^+$ be the set of the extracted elements. The overall time required so far is $O(n) + O(\sqrt{n} \log n) = O(n)$. (Notice also that $S^- \cap S^+ = \emptyset$ since $2 \lfloor \sqrt{n} \rfloor \le n$ for $n \> 1$).

Now you know that all the elements in $A \setminus (S^- \cup S^+)$ are integers between $0$ and $n^{3/2}$ (actually, between $\sqrt{n}$ and $n^{3/2}$, but this is irrelevant), and therefore can be sorted in time $O(n)$ using Radix sort (indeed, each integer in $S \setminus (S^- \cup S^+)$ has just two digits when written in base $n$). Let $A'$ be the sorted version of $A \setminus (S^- \cup S^+)$.

To obtain a sorted version of $A$, we just need to insert the elements in $S^- \cup S^+$ into the right position of $A'$. This can be done by first sorting $S^- \cup S^+$ in time $O(n)$ (any quadratic-time algorithm suffices since $|S^- \cup S^+| \le 2 \sqrt{n}$) and then merging the resulting sorted sequence with $A'$ a-la-Mergesort.
> 1 votes

---
Tags: algorithms, sorting
---


# Question
Title: Douglas-Peucker line simplification algorithm time complexity
I am analyzing the time complexity of the Douglas-Peucker line simplification algorithm. Reading online I've found that it has a worst-case running time of $O(n^2)$ where $n$ is the number of points on the line. However, I haven't been able to provide complete proof. Here is the pseudo-code I am working with:

Here is my analysis:

**Line 1:** $O(1)$

**Line 2:** We can say that it goes through all points in the polyline formed by the first point and the last point in $PL$ and return the point with the maximum distance to the straight line between the mentioned points. We can safely say this is $O(n)$

**Lines 4-6:** If we are here we are doing two recursive calls. **The number of elements used in each call could be different (not always in half). Depends on the point found in Line 2**. Leaving implementation details aside, we can say that splitting is $O(1)$. Also, we have a $JOIN$ operation which would take $O(n)$ to join both lists.

**Line 8:** This is also a $JOIN$ operation but this only takes $O(1)$.

After looking at these steps I think we have the following recurrence relation:

$T(n) = T(index + 1) + T(n - index) + 2n$ where $index \in \\{1, \dots, n-1\\}$

Am I right? If so, how could I prove this is $O(n^2)$? Master Theorem?

Thank you very much in advance

EDIT: Changed description on Lines 4-6. Thus, also changed recurrence formula.

# Answer
Your analysis seems correct, except for that you need $T(n)=T(index)+T(n-index+1)+2n$ instead because when $index$ is either $0$ or $n-1$ you won't get in the right hand side another factor of $T(n)$, which is not allowed.

In fact, it will yield something very close to the recurrence of the running time in the quicksort algorithm.

## Worst case scenario

When `index` is either $0$ or $n-1$, the recurrence will boil down to $T(n)=T(1)+T(n-1)+2n = T(n-1) + (2n + T(1))$. You can easily show by induction that $T(n)=\Theta(n^2)$ in this case.

## Best case scenario

We assume the input in the recursion will always be cut down by half. That is, the recursion is $T(n)=2T(n/2)+2n$.

Define $b=a=2$ and $f(n)=2n$. Then, $T(n)=aT(n/b)+f(n)$.

We can calculate $c\_{crit}=\log\_{b}(a)=\log\_2(2)=1$ and thus $f(n)=2n=\Theta(n)=\Theta(n^{c\_{crit}})$.

Now we can directly use the second case to get that $T(n)=\Theta(n^{c\_{crit}}\log(n))=\Theta(n\log(n))=O(n^2)$

## Average case scenario

If we assume that the input is a random variable, such that the choice of $index$ is uniformly distributed in $\\{0,\dots,n-1\\}$, then the algorithm takes expected time $\Theta(n\log(n))$. Take a look at the proof for quicksort to see how its done.
> 1 votes

---
Tags: complexity-theory, asymptotics, check-my-answer
---


title: PushDown Automata

text:
# Question
Title: PushDown Automata
Let Sigma = {a,b,c} and let L be the language of all words in which all the a’s come before the b’s and there are the same number of a’s as b’s and arbitrarily many c’s that can be in front, behind, or among the a’s and b’s. Some words in L are , abc, caabcb, ccacaabcccbccbc.

How can I solve this problem by empty stack model? My solution is that we push A for each 'a' and pop B for each 'b'. But how can we pop out all of 'c'? Can anyone give me some idea please?

# Answer
For CF languages I really like to construct the grammar first. For $a^nb^n$ of course it is easy to construct a grammar:

$ S \rightarrow a S b \\ S \rightarrow \varepsilon $

Notice how it enforces the same amount of letters: A substitution of *S* generates an *a* in the front and a *b* in the back. Now what we need is to sprinkle in some *c* terminals among these. We can just use a rule like so:

$ X \rightarrow XX \\ X \rightarrow c \\ X \rightarrow \varepsilon $

This essentially generates an arbitrary amount of *c* terminals. Now all we need to do is to add it to *S*:

$ S \rightarrow XSX \\ S \rightarrow aSb \\ S \rightarrow \varepsilon $

From a CF grammar of course you can construct a PDA.

**Edit:**

If you need to think about PDAs "directly", then construct the PDA for $a^nb^n$, but allow consuming *c* terminals in every state without modifying the stack.
> 0 votes

---
Tags: pushdown-automata
---


title: Loop invariant for a division algorithm

text:
# Question
Title: Loop invariant for a division algorithm
I'm having problems trying to understand the concept of loop invariants.

I have the following code, where M and N are predefined constants.

```
a = 0
b = M
c = 1
while M - c * N >= 0:
  a = c
  c = c + 1
  b = M - a * N
print(a, b)

```

I have figured out this code is actually a division algorithm, where in the end prints out `a` as the quotient of `M/N` and `b` as the remainder. But it's unclear to me what the invariant here is. Can I say `c-a` is the invariant since `c-a=1` is always true before and after every iteration? How could I prove that in a mathematical perspective?

# Answer
> 8 votes
A loop invariant is an expression that is true through all iterations. But it should also lead to the post-condition being true when the loop terminates. Although c-a=1 is true, It doesn't help you in achieving the post-condition.

Intuitively, You would want the invariant to be `a*N + b = M` because that's what division is and that's what guarantees that you'll get the post-condition ( `a=quotient, b=remainder`) when the termination condition ( `b < N` ) is true.

The formal proof should follow from this idea.

# Answer
> 0 votes
Assume $M$ and $N$ are both non-negative. There are a few invariants for the loop (we can verify them to hold prior to the loop, and after each iteration):

$P\colon M = aN + b$

$Q\colon c-a = 1$

$R\colon M-aN \ge 0$

Note, $P \land R \Rightarrow b \ge 0$

The loop's condition is:

$C\colon M-cN \ge 0$

$\Leftrightarrow M-(a+1)N \ge 0$ {due to $Q$}

$\Leftrightarrow M-aN \ge N$

Upon termination, $C$ is false, so following would hold:

$M-aN \< N$

$\Leftrightarrow b \< N$ {due to $P$}

Also,

$b \ge 0$ {due to $P \land R$}

So, $a$ and $b$ must contain the desired quotient and remainder ($0 \le b \< N$) such that: $M = aN + b$.

---
Tags: algorithms, loop-invariants
---


# Question
Title: Pseudo-dimension of a subset of affine functions
Let's say there are two sets of affine functions.

1. $\mathcal{A} = \\{ax +b \mid a,b \in \mathbb{R}\\}$
2. $\mathcal{H} = \\{2x + 1, x, 3x + 4, 4x\\}$

I know that the $\mathrm{Pdim}(\mathcal{A}) = 2$. From my understanding the $\mathrm{Pdim}(\mathcal{H})$ is also equal to 2 as I can find $\\{x\_1, x\_2\\}$ and $z\_1, z\_2$ such that for all subsets $T \subseteq \\{x\_1, x\_2\\}$, there is a function $f \in \mathcal{H}$ such that $\forall x \in T, f(x) \geq z\_1$ and $\forall x \notin T f(x) \< z\_1$.

Is my intuition correct?

# Answer
> 1 votes
I am using the definition of pseudo-dimension found here, page 10 of the pdf.

Denote $h\_1(x) = 2x+1$, $h\_2(x) = 4x$, $h\_3(x) = x$ and $h\_4(x) =3x+4$.

Let's consider $C = (-2, 2)$ a vector. Then $r = (-2.5, 6)$ is a witness that proves that $C$ is pseudo-shattered by $\mathcal{H}$:

* $h\_1(-2) = -3 \<-2.5$, $h\_1(2) = 5 \<6$;
* $h\_2(-2) = -8 \<-2.5$, $h\_2(2) = 8 \>6$;
* $h\_3(-2) = -2\>-2.5$, $h\_3(2) = 2\<6$;
* $h\_4(-2) = -2 \>-2.5$, $h\_4(2) = 10 \>6$.

Clearly $\text{Pdim}(\mathcal{H})\< 3$ since the pseudo-dimension cannot be greater than $\log\_2 |\mathcal{H}|$.

That proves that $\text{Pdim}(\mathcal{H}) = 2$.

---
Tags: machine-learning, learning-theory, vc-dimension
---


title: Reduction from 3SAT to SUBSET-SUM

text:
# Question
Title: Reduction from 3SAT to SUBSET-SUM
The reduction from 3SAT to SUBSET-SUM includes building a table as follows:

Where base 10 representation is used for the rows in the table. I would like to know if the reduction will still be correct if we replace the base 10 representation with the following bases: 2, 3 or 6?

# Answer
> 1 votes
This was an examination paper question for Computability and Complexity, as the deadline has now passed, I am able to answer:

The basic answer to this is that it is quite literally, base 2, 3 and base 6. If my answer itself was correct, you can see in the table we must have the second half of the answer to contain only "3" values, that is to say, 33333,...33333.

It quite literally does mean "base x" here, in that base 10 (our usual numbering system base) would give us the ranges of {0,1,2,3,4,5,6,7,8,9}.

As such, base 10 is appropriate, as its set contains 3.

Base 2 and 3 will give us {0,1} and {0,1,2} respectively. As such they cannot represent "3" and would not work in the general answer.

Base 6 however, gives us the set {0,1,2,3,4,5} which as it contains 3, gives us a base capable of representing the table.

As such, base 4 is the minimum base required to represent the table as this is the lowest value that includes 3. ({0,1,2,3})

I hope you figured this out in the exam, a useful link for this would have been: https://math.stackexchange.com/questions/2630604/reduction-3sat-to-subset-sum

Which better explains the reasoning, I have only tried to explain the exact answer.

---
Tags: complexity-theory, np-complete, reductions, decision-problem, polynomial-time-reductions
---


# Question
Title: Time complexity of checking whether a string exists in a HashSet
From what I know hash sets generally have complexity of $O(1)$ (unless the hash function is bad, but let's just ignore that for this question). However, sets need to either read the full data so as to make a hash function that's guaranteed to return a unique result for every input or they need to make a comparison to make sure the data is the same otherwise. Doesn't that mean that the complexity for strings should be $O(m)$, where $m$ is the length of the string, at least if we accept that these strings can get arbitrarily large? Is there something I do not understand?

The reason I'm asking is because I solved a problem with a trie and the provided solution was solved with a set (that was the only difference), but it assumed that arbitrarily large strings can be found to exist or to not exist in a set in $O(1)$ time. The problem is to find which words in a set of words can be formed using other words in the set (words can be used multiple times) — for example in "a", "bc", "cd", "acd", "abcd", only "acd" can be formed using other words, though I don't think the specific problems matters much.

# Answer
You are right in that to check membership (or to retrieve) using a hash function, you also need to check that the retrieved element is equal to the element in question. For a string, you should assume that this takes time linear in the length.

Hence checking membership in a hash set is indeed expected $O(m)$.
> 3 votes

---
Tags: time-complexity, hash-tables
---


# Question
Title: Finding which strings in a set of strings have a certain prefix - can it be smaller than O(number of strings*length of prefix)
If I have a set of words and need to return which of them start with a certain prefix, can that complexity be less than O(n\*d), where n is the number of words and d is the prefix. I'm asking because of this video: https://www.youtube.com/watch?v=QGVCnjXmrNg (1:20 starts discussing the solution), where it says it can be lowered through using a trie with all of the words, but I think the creation of the trie would take O(n\*t) complexity, where t is the average length of the words. Assume that all words will be at least as long as d (any word which has length smaller than d is disregarded immediately in the solution below, but is still considered during the creation of the trie in the video).

My idea for the solution is the simple one: go through each word and check if it starts with the same prefix. If it does, add it to the list of words which start with that prefix, otherwise don't. The reason I think this is the best solution possible in terms of worst-case complexity is as follows: if we skip even one character or one string, we may return the wrong answer. This is the minimum input that is to be considered and in any other case, it is also considered (for example, in the solution that input is considered during the creation of the trie).

Example javascript code:

```
function solve(prefix, words) {
    //startsWith has worst-case complexity O(d) where d is the length of the prefix
    function startsWith(word, prefix) {
        //this doesn't change worst-case complexity but means that the only disregardable input is disregarded
        if (prefix.length > word.length) return false;

        for (let i = 0; i < prefix.length; i++) {
            if (prefix[i] !== word[i]) {
                return false;
            }
        }

        return true;
    }

    const wordsArray = [];

    //since there are n (n is the length of the words array) and every iteration has worst-case complexity O(d),
    // we have a worst-case complexity of O(n*d)
    for (let i = 0; i < words.length; i++) {
        if (startsWith(words[i], prefix)) {
            wordsArray.push(words[i]);
        }
    }

    return wordsArray;
}

console.log(solve("do", ["dog", "dark", "cat", "door", "dodge"]));

```

I'm asking that because in the video it was mentioned that it can be faster than O(n\*d), but I believe the solution was wrongly analyzed. I, however, am just a hobbyist and feel like it is more likely I'm missing something here.

# Answer
> 2 votes
In the worst case, it has to be $n \cdot d$: You must check $d$ symbols of each of the $n$ strings to confirm they all start with the prefix, if you leave any out it might be different. This is essentially an adversarial argument.

You certainly can speed it up for non-matching strings, like comparing lengths, just check some positions to rule out prefixes. If the strings are random, checking just the first symbol will weed out all but a fraction of the strings (like the program you show does, bailing out early).

If you assume random strings over an alphabet of $m$ symbols, they will agree with the first $k$ symbols of your needle (which you are looking for in the haystack) $1/m^k$ of the times. The number of checks to do for each string will then be on average:

$\begin{align\*} c &= 1 + \sum\_{2 \le k \le d} \frac{k}{m^k} \end{align\*}$

(you do $1$ check regardless, then $k$ more checks if $k$ symbols match).

To compute this sum, note that:

$\begin{align\*} f(z) &= \sum\_{0 \le k \le d} \frac{z^k}{m^k} \\ &= \frac{1 - z^{k + 1} / m^{k + 1}}{1 - z / m} \\ &= \frac{m^{k + 1} - z^{k + 1}}{m^{k + 1} - z m^k} \\ f'(z) &= \sum\_{0 \le k \le d} \frac{k z^{k - 1}}{m^k} \\ f'(1) &= \sum\_{0 \le k \le d} \frac{k}{m^k} \\ &= \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \\ c &= 1 + f'(1) \\ &= 1 + \frac{m^{d + 1} - (d + 1) m + d}{m^d (m - 1)^2} \end{align\*}$

Thus the number of symbol comparisons for one string is approximately $(m + 1) / m$, as you'd suspect.

---
Tags: time-complexity, strings, string-matching
---


# Question
Title: What exactly is execution-time address binding?
According to these two definitions:

> **Logical address**: every memory address generated by the CPU.

> **Physical address**: address which identifies uniquely a (real) memory cell.

my textbook (Operating systems concepts - Silberschatz, Galvin, Gagne) says that address binding at compile-time and load-time both generate identical logical and physical addresses, while execution-time binding produces different logical and physical address.

I've googled a lot, but every article which tries to explain this concept is not that clear. I can't understand what happens in the practice. I'll give you an example to let you understand what I mean:

The source code (high-level language instructions) contains symbolic addresses (like `count`) that are replaced (by the compiler) by:

* physical addresses (compile-time binding) if the location in memory of the process can be known in advance (non-multi-programmed systems);
* relocatable addresses (load-time binding) in the opposite case (most common).

Once the loader puts the obj into memory it replaces relocatable addresses with physical addresses (if there are any) and the program can be finally executed. The CPU can read and refer to physical addresses, so logical and physical addresses are the same. In both previous cases the binding is static: once loaded, the process can't be moved from one segment of memory to another.

In order to manage the memory in an efficient way, the system should be able to move a process from a location of the memory to another: this means that the process physical addresses can change at run-time. In order to implement this mechanism logical addresses and physical addresses must be different: logical addresses can change in an interval `[0, max]` and physical ones between `[r, r+max]`, where `r` is the relocation register.

Does this mean that, in execution-time binding, the obj file contains virtual addresses (`[0, max]`), which are converted time by time by the system into physical ones? In other words, is true that the obj file doesn't contain any physical address (but a data structure of the OS keeps the informations about the process address binding) so each time the CPU reads (for example) `ADD 100 105` the addresses `100` and `105` are converted into physical ones by the system (using MMU and data structures)?

Please correct any mistake I made, the textbook is not so clear.

# Answer
> 1 votes
Until the program is running, physical addresses make little (or no) sense: The instructions make reference to logical addresses.

While the program runs, the CPU maps logical addresses to physical addresses (they could be just exactly the same, or change e.g. by paging or just by relocation --- add the contents of a special register to each logical address to give the pysical address, used in some early machines to be able to place several programs tightly in memory and be able to move them around). If you look e.g. at the intel 8088/8086 (infamous CPUs for the original PC), it sports *segment registers*, so you can move say the stack around in RAM and the program doesn't care where it is.

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


# Question
Title: Rank operation in search tree, number of nodes between 2 values
What kind of search tree should I use in which I will have operation Rank\[x, y\] which will return number of existing nodes/values between x and y in time O(depth of tree) so the operations find, insert and delete will have also time complexity O(depth of tree)? I was thinking about a-b tree, which has find, insert and delete in O(log n), but I do not know how should I implement the rank operation. I was thinking to add each value in node information about number of its children but it wont be in O(log n) time.

# Answer
> 0 votes
Use an AVL tree $T$ that is augmented so that each vertex $v$ also stores the number of vertices in the subtree of $T$ rooted at $v$.

Given two vertices $u$ and $v$ of the tree you can find the number of values between $u$'s and $v$'s key by summing the sizes of at most $O(\log n)$ subtrees of $T$ dangling from the (unique) path from $u$ to $v$ in $T$.

These are exactly the highlighted trees/vertices in this answer, which also gives you a $O(\log n)$-time algorithm to find them.

The time complexities of insertions, deletions, and searches are asymptotically unaffected (i.e., they are in $O(\log n)$).

---
Tags: search-trees
---


# Question
Title: Is there any algorithm that finds the time complexity of another algorithm provided that it halts?
Let us suppose that we have some algorithm A that halts for all valid inputs, can we prove the existence of another algorithm B that takes A as input and calculates the time complexity of A.

Are there any examples of existing algorithms/programs that do this?

# Answer
I think this is correct and incorrect at the same time. It depends on how we define the problem we want to solve.

## Formulation I

If we are interested in an algorithm that given $\langle M, w\rangle$ will tell you how much time $M$ runs on $w$ (assuming it halts), then there is such an algorithm: emulate $M$ on $w$ and count the number of steps it does until it halts.

---

## Formulation II

**But,** if we are interested in an algorithm that given $\langle M\rangle$ will give you a function $f:\mathbb{N}\rightarrow \mathbb{N}$ that bounds the running time of $M$, things get a little bit more complicated.

First, how do we describe a function $f$ with finite storage? there are $|\mathbb{N}^\mathbb{N}|=2^{\aleph\_0}$ functions, and $2^{\aleph\_0}$ words in $\\{0,1\\}^\*$ as well. This means there is some way to map each word to a function and vice versa. We will ignore from now the problem of computing this mapping between words and functions, and will still show there is no algorithm for the problem.

Assume towards contradiction there is some $\hat M$ that solves our problem. Let us create a new machine $M'$ that given input $\langle M\rangle $, will first emulate $\hat M$ on $M$ to find some $f$ which describes the upper bound on the time it takes $M$ to halt (assuming it halts). Then, $M'$ will enter a loop for $f(|\langle M'\rangle |) + 1$ steps.

Now, consider what happens when $M'$ runs on the input $\langle M'\rangle$. $\hat M$ will give an upper bound $f$ on the running time of $M'$, and $M'$ will run for **more** than $f(|\langle M' \rangle|)$ steps, contradicting that $f$ is an upper bound (since the original input of $M'$ was $\langle M'\rangle$).

Thus, no such $\hat M$ can ever exist!
> 2 votes

# Answer
The answer by nir shahar goes to the point.

Another way to see this is to consider Radó's non-computable function $S(n)$ (the maximum number of steps a Turing machine with $n$ states does when started with an empty tape before halting). If you could compute your function $M$, you could compute $S$ (for each TM of $n$ states compute your function $M$, run the TM for $M$ steps, if it hasn't stopped yet, it won't halt; the maximal value found that way is $S(n)$).

The paper is rather simple, and enlightening: Radó, "On Non‐Computable Functions", Bell System Technical Journal 41(3), pp. 877-884 (may 1962), doi https://doi.org/10.1002/j.1538-7305.1962.tb00480.x.
> 2 votes

---
Tags: algorithms, time-complexity, decision-problem
---


# Question
Title: Constructing PDA to accept language $L=\{a^i b^j c^k \mid k\geq \min(i,j)\}$
How can I construct a PDA which accepts the language $\\{a^i b^j c^k \mid k\geq \min(i,j)\\}$

I think about different solutions such as building a stack with two-state. one state is for $i \< j$ and another is for $i \> j$, But I think it doesn't work.

also, The idea of poping and pushing a and b is not good. I tried it. Can Someone give me a little hint?

# Answer
Your idea to differentiate between $i\<j$ and $i \>j$ is good.

To help you building the PDA, note that $L = \\{a^ib^jc^k | k \geq i\\} \cup \\{a^ib^jc^k|k\geq j\\}$.

I hope that hint is enough.
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: What does "satisfactory definition" mean?
I am reading the book Artificial Intelligence (A modern approach) by Stuart Russell and Peter Norvig. While reading the book, I saw the below sentence in the book.

> The Turing Test, proposed by Alan Turing (1950), was designed to provide a satisfactory operational definition of intelligence.

Now the question is, what does the writer mean by saying ***satisfactory definition***? Does it have a special mathematical meaning (like as we say in some problems: *f(x) satisfies some conditions*)? or does the *satisfactory* adjective just mean *good enough* (as stated in Longman dictionary)?

# Answer
It means nothing in particular. You can read it as "good enough". It is not encoding some specific technical meaning.
> 3 votes

---
Tags: turing-machines, artificial-intelligence, turing-test
---


# Question
Title: Dynamic All Pairs Shortest Paths algorithm
I heard about the following problem in a competitive programming camp:

Given an undirected weighted graph $G$ with one vertex initially.

Suppose you are given two types of queries:

1. Add a new vertex to $G$ with some undirected weighted edges between this vertex and subset of vertices added previously to $G$ in time complexity **$O(n^2)$**, where negative weights are allowed.
2. Find the length of the shortest path between two vertices in $O(1)$.

Note: Floyd Warshall's algorithm is $O(n^3)$ for each query of type 1.

I'm looking for (in addition to your answer):

* Any useful reference to solve such a problem.
* Links for similar problems in online judges (Codeforces, SPOJ .. etc).

# Answer
You maintain a table $d$ where $d(i,j)$ represents the length of the shortest path from vertex $i$ to vertex $j$, so query 2 can be done in $O(1)$.

For query 1, when a new vertex $u$ is added, for each old vertex $v$, calculate the length of the shortest path from $u$ to $v$ by

$$d(u,v),d(v,u)\leftarrow\min\_s(w(u,s)+d(s,v)).$$

where $s$ varies among all neighbors of $u$, and $w(u,s)$ represents the weight of edge $(u,s)$. This process takes $O(n^2)$. Now if there is no negative cycle, for each old vertex $v$, $d(u,v)$ and $d(v,u)$ correctly record the length of the shortest path from $u$ to $v$. It's also not hard to detect if there is a negative cycle.

Then, for any old vertices $s,t$, update $d(s,t)$ to

$$d(s,t)\leftarrow\min\\{d(s,t),d(s,u)+d(u,t)\\}.$$

This can also be done in $O(n^2)$.

Now after the two steps above, if there is no negative cycle, for each pair of vertices $x,y$, $d(x,y)$ correctly records the length of the shortest path from $x$ to $y$.
> 1 votes

# Answer
It called incremental all pairs shortest paths. Because you just add edges you don't have to deal with destroyed shortest paths but you only need to check if the added edge allows shorter paths. Notice that the affect is not local (i.e. after adding edge a shortest path between s to t might be replaced by a distinct path).

Suppose you add $e=(v,u)$. What you have to do is find with Bellman-Ford all shortest paths to $v$ and all shortest paths from $u$ (Bellman-Ford on reversed graph edges). Then for every $s, t \in V$ let $d\_{G\cup e}(s, t)=\min(d\_G(s,t), d\_{G\cup e}(s, v)+w(e)+d\_{G\cup e}{d(u, t)})$.

I hope this helps.
> 1 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: What other implementation styles are there besides compilation, interpretation and transpilation?
Obviously there is JIT but it is basically run-time compilation. There is also implementing things in VHDL or ASIC. But my question is more towards software techniques for program building and execution

# Answer
Fundamentally, there are only the two: *compilation* and *interpretation*.

**tl;dr**: An interpreter *runs* the program, a compiler *translates* the program to another language.

An *interpreter* for language **X** is a program (or a machine, or just some kind of mechanism in general) that executes any program **p** written in language **X** such that it performs the effects and evaluates the results as prescribed by the specification of **X**. CPUs are usually interpreters for their respective instructions sets, although modern high-performance workstation and server CPUs are actually more complex than that; they may actually have an underlying proprietary private instruction set and either translate (compile) or interpret the externally visible public instruction set.

A *compiler* from **X** to **Y** is a program (or a machine, or just some kind of mechanism in general) that translates any program **p** from some language **X** into a semantically equivalent program **p′** in some language **Y** in such a way that the semantics of the program are preserved, i.e. that interpreting **p′** with an interpreter for **Y** will yield the same results and have the same effects as interpreting **p** with an interpreter for **X**. (Note that **X** and **Y** may be the same language.)

In some cases, we have more specialized names for certain kinds of compilers, depending on what **X** and **Y** are, and what the compiler does:

* if **X** is perceived to be assembly language and **Y** is perceived to be machine language, then we call it an *assembler*,
* if **X** is perceived to be machine language and **Y** is perceived to be assembly language, then we call it a *disassembler*,
* if **X** is perceived to be lower-level than **Y**, then we call it a *decompiler*,
* if **X** and **Y** are the same language, and the resulting program is in some way faster or lighter, then we call it an *optimizer*,
* if **X** and **Y** are the same languages, and the resulting program is smaller, then we call it a *minifier*,
* if **X** and **Y** are the same languages, and the resulting program is less readable, then we call it an *obfuscator*,
* if **X** and **Y** are perceived to be at roughly the same level of abstraction, then we call it a *transpiler*, and
* if **X** and **Y** are perceived to be at roughly the same level of abstraction and the resulting program preserves formatting, comments, and programmer intent such that it is possible to maintain the resulting the program in the same fashion as the original program, then we call it a *re-engineering tool*.

Also, note that older sources may use the terms "translation" and "translator" instead of "compilation" and "compiler". For example, C talks about "translation units".

You may also stumble across the term "language processor". This can mean either a compiler, an interpreter, or both compilers and interpreters depending on the definition.

The terms *Ahead-of-Time (AOT)* and *Just-in-Time (JIT)* refer to *when* compilation takes place: the "time" referred to in those terms is "runtime", i.e. a JIT compiler compiles the program *as it is running*, an AOT compiler compiles the program *before it is running*. Note that this requires that a JIT compiler from language **X** to language **Y** must somehow work together with an interpreter for language **Y**, otherwise there wouldn't be any way to run the program. (So, for example, a JIT compiler which compiles JavaScript to x86 machine code doesn't make sense without an x86 CPU; it compiles the program while it is running, but without the x86 CPU the program wouldn't be running.)

So, we have:

* AOT compiler: compiles before running
* JIT compiler: compiles while running
* interpreter: runs

# JIT Compilers

Within the family of JIT compilers, there are still many differences as to when *exactly* they compile, *how often*, and at what granularity.

Some JIT compilers for example only compils code *once* (when it is loaded) and compiles a whole module at a time. Other compilers may gather information while the program is running and recompile code several times as new information becomes available that allows them to better optimize it. Some JIT compilers are even capable of *de-optimizing* code. Now, you might ask yourself why one would ever want to do that? De-optimizing allows you to perform very aggressive optimizations that might actually be unsafe: if it turns out you were *too* aggressive you can just back out again, whereas, with a JIT compiler that cannot de-optimize, the program would crash or return a wrong result; in other words, you simply can't allow yourself to perform the aggressive optimizations in the first place.

JIT compilers may either compile some static unit of code in one go (one module, one class, one function, one method, …; these are typically called *method-at-a-time* JIT, for example) or they may *trace* the dynamic execution of code to find dynamic *traces* (typically loops) that they will then compile (these are called *tracing* JITs).

# Combining Interpreters and Compilers

Interpreters and compilers may be combined into a single language execution engine. There are two typical scenarios where this is done.

Combining an AOT compiler from **X** to **Y** with an interpreter for **Y**. Here, typically **X** is some higher-level language optimized for readability by humans, whereas **Y** is a compact language (often some kind of bytecode) optimized for interpretability by machines. For example, the CPython Python execution engine has an AOT compiler that compiles Python sourcecode to CPython bytecode and an interpreter that interprets CPython bytecode. Likewise, the YARV Ruby execution engine has an AOT compiler that compiles Ruby sourcecode to YARV bytecode and an interpreter that interprets YARV bytecode. Why would you want to do that? Ruby and Python are both very high-level and somewhat complex languages, so we first compile them into a language that is easier to parse and easier to interpret, and then interpret *that* language.

The other way to combine an interpreter and a compiler is a *mixed-mode* execution engine. Here, we "mix" two "modes" of implementing the *same* language together, i.e. an interpreter for **X** and a JIT compiler from **X** to **Y**. (So, the difference here is that in the above case, we had multiple "stages" with the compiler compiling the program and then feeding the result into the interpreter, here we have the two working *side-by-side* on the same language.) Code that has been compiled by a compiler tends to run faster than code that is executed by an interpreter, but actually compiling the code first takes time (and particularly, if you want to heavily optimize the code to run *really* fast, it takes a *lot* of time). So, to bridge this time where the JIT compiler is busy compiling the code, the interpreter can already start running the code, and once the JIT is finished compiling, we can switch execution over to the compiled code. This means that we get both the best possible performance of the compiled code, but we don't have to wait for the compilation to finish, and our application starts running straight away (although not as fast as could be).

This is actually just the simplest possible application of a mixed-mode execution engine. More interesting possibilities are, for example, to not start compiling right away, but let the interpreter run for a bit, and collect statistics, profiling information, type information, information about the likelihood of which specific conditional branches are taken, which methods are called most often etc. and then feed this dynamic information to the compiler so that it can generate more optimized code. This is also a way to implement the de-optimization I talked about above: if it turns out that you were too aggressive in optimizing, you can throw away (a part of) the code and revert back to interpreting. The HotSpot JVM does this, for example. It contains both an interpreter for JVM bytecode as well as a compiler for JVM bytecode. (In fact, it actually contains *two* compilers!)

It is also possible and in fact common to combine those two approaches: two phases with the first being an AOT compiler that compiles **X** to **Y** and the second phase being a mixed-mode engine that both interprets **Y** and compiles **Y** to **Z**. The Rubinius Ruby execution engine works this way, for example: it has an AOT compiler that compiles Ruby sourcecode to Rubinius bytecode and a mixed-mode engine that first interprets Rubinius bytecode and once it has gathered some information compiles the most often called methods into native machine code.

Note that the role that the interpreter plays in the case of a mixed-mode execution engine, namely providing fast startup, and also potentially collecting information and providing fallback capability may alternatively also be played by a second JIT compiler.

This is how the second generation of Google's V8 ECMAScript engine worked, for example. This generation of V8 never interprets, it always compiles. The first compiler is a very fast, very slim compiler that starts up very quick. The code it produces isn't very fast, though. This compiler also injects profiling code into the code it generates. The other compiler is slower and uses more memory, but produces much faster code, and it can use the profiling information collected by running the code compiled by the first compiler.
> 4 votes

---
Tags: programming-languages, compilers, interpreters
---


# Question
Title: Can given grammar be parsed using recursive descent?
I have this Grammar below:

```
Expr ::= Term "(" Term ")"

Term ::= Ident | "(" Expr ")"

Start symbol: <Expr>
Terminal symbol: Ident ::= [a-z]+

```

And I wonder if it is possible to construct a recursive descent parser for grammar G2?

I think this won't be able to do that?

# Answer
> 2 votes
You will be able to.

Consider what happens when you try parsing a string as an Expr: you will need to read a term. If your term is starts with an english alphabet character, then its an Ident and once you stop seeing letters a-z, then you have finished reading Term. If it does not start with an alphabet character, then you need to see a '(' and you will retry reading an expression from there (by induction this will work), and finally read a ')'.

So we can successfully read the first Term, and after that we just need to see a '(', another Term (and again by induction we can do that) and finally a ')'

This language has no ambiguity so its pretty easy to parse.

---
Tags: parsers
---


title: A question on decidability

text:
# Question
Title: A question on decidability
I have a homework question that is as follows:

*L(P) is a language of ASCII input strings for which a given program, P, returns "yes". Is the set of all input strings P decidable, such that P is a decision program and L(P) is decidable?*

My intuition leads me to believe that the set is, in fact, decidable but I am having a tough time proving my answer.

Would appreciate any help on this. Thanks

# Answer
Let $L=\\{\langle M \rangle \mid M \text{ is a TM such }L(M)\in R\\}$, where $\langle M\rangle$ is the encoding of a TM $M$, and $R$ is the set of all decidable languages. This is the language in question.

Notice that $R\neq \emptyset$ and also since there are languages not in $R$ (like the halting problem), then $R\neq RE$. Simply put, $R$ is *not* trivial (obviously).

Apply Rice's theorem on the property $"R"$, to directly get that $L$ is not decidable.
> 1 votes

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


# Question
Title: Existence of a function between two functions $f$ and $g$ where $f \in o(g)$
Is this statement true?

> For each two functions $f$ and $g$, where $f \in o(g)$, there exists a function $h$ where $f \in o(h)$ and $h \in o(g)$

Please note that I am using small $o$ notation.

# Answer
Yes.

For example, let $h=\sqrt{fg}$, assuming $f$ and $g$ are positive.

If not, we can let $h(x)=\max(\sqrt{|f(x)g(x)|}, g(x)/(|x|+1))$. The term, $g(x)/(|x|+1)$ makes sure that $h(x)$ will stay positive eventually.

---

Exercise. For each two functions $f$ and $g$, where $f \in \omega(g)$, there exists a function $h$ where $f \in \omega(h)$ and $h \in \omega(g)$.
> 3 votes

---
Tags: time-complexity
---


# Question
Title: Why cannot Operand forwarding remove all RAW hazards?
I read a statement in the textbook that : Operand Forwarding cannot remove all RAW Hazards in Pipelined Processor but am unable to conceptualize that in my brain. Can you please explain it with an example where Operand Forwarding will not be able to remove RAW Hazard .

# Answer
Sure! And I can assure that is a fairly good question, if you are not able to see all the combinations.

See, operand forwarding can indeed remove all RAW hazards inside CPU but it is helpless when not all execution inside the CPU.

What I mean is all the RAW hazard scenarios, that we can write involving REGISTERS only and execution is some ALU operation, operand forwarding can escape the hazard.

like:

r1 \<- r2 + r3 : I1
r4 \<- r1 - r3 : I2

r1 is being calculated in ALU for I1, while I2 needs to load r1 as operand for ALU. Here the trick is even though you load the operands of ALU for execution, bt ALU will first execute I1 and then I2 in that order. So, even though r1 is not ready at the assigned time for operand fetch phase of I2, but it will be available before ALU starts execution of I2, and thus taking the benefit of same fact:

> CPU notes that I2 is wanting the ALU execution output as an operand. So, CPU saves this information as setting a bit inside the circuitry. And allowing I2 to proceed with "OPERAND FETCH PHASE" while skipping fetch of I2.

(Fetch of I2 is actually done, when CPU sees the RAW and sets the bit, but that's just assurance of fetch done, NOT THE ACTUAL FETCH)

THIS IS OPERAND FORWADING!

Now as soon as ALU computes the value, as the bit of oprand forwarding is 1, it transfers the contents of ALU output to the ALU operand.

(NOW THE GUARANTEE HAS BEEN COMPLETE, AND r1 for I2 has been fetched).

But observe, the write to r1 by I1 may be not done yet and in next cycles this be done. But I2 might be in ALU execution phase at this cycle. So, as the FUTURE OPERAND(r1) is inside CPU and ALU being sequential, we could solve RAW.

But the problem is with LOAD/STORE involved in RAW.

load r1, Address1 : I1

r3 \<- r1 + r2 : I2

Now the ALU for I2 can't get r1 before complete I1 is executed and r1 has been really written into. So, this time "OPERAND FETCH PHASE" of I2 will have stall and can't proceed.

Hope this helps.
> 2 votes

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: Zero knowledge proof - case of graph 3-coloring (not understanding the concept)
In zero knowledge, in the context of graph 3-coloring, I do not understand how the prover is actually showing that he solved the problem.

The context:

* both know the graph (the prover and the verifier)
* the prover solves a 3-coloring of the graph
* repeat:

\*the prover randomly permutes the colors

\*the verifier asks for the coloring of an edge

\*if the colors are different the process continues, and the verifier is more convinced that the prover actually solved the 3-coloring, if not, the verifier knows that the prover did not solve the 3-coloring

My question is: why couldn't a false prover (someone that does not know how to solve for the coloring) just always provide 2 different random colors?

# Answer
Your misunderstanding stems from stating a wrong protocol for ZK 3-color verification. In fact the protocol is a bit more complex:

The prover first "commits" to colors. This means that he cannot change its commitment afterwards, but at the same time, he does not reveal the colors themselves.

Then, once the verifier asks for an edge, the prover "opens" its commitment, revealing the colors of that edge alone.

Since its commitment is binding, the prover cannot change the colors after committing to them. So if the prover does not have a legal coloring, he must commit to some invalid coloring of at least one edge, and will be found with some small probability.

This is repeated, each time with a new permutation of the colors, and new commitments.
> 1 votes

---
Tags: cryptography, zero-knowledge-proofs
---


title: Why do Bloom filters work?

text:
# Question
Title: Why do Bloom filters work?
Let's say I am using Bloom filters to create a function to check if a word exists in a document or not. If I pick a hash function to fill out a bit bucket for all words in my document. Then if for a given number of words, wouldn't the whole bit bucket be all 1s? If so then checking for any word will return true? What am I missing here?

# Answer
Given that you want to insert $n$ words into the Bloom filter, and you want a false positive probability of $p$, the wikipedia page on Bloom filters gives the following formulas for choosing $m$, the number of bits in your table and $k$, the number of hash functions that you are going to use. They give $ m = - \frac{n \ln p}{(\ln 2)^2} $ and $$ k = \frac{m}{n}\ln 2=-\frac{\ln p}{\ln 2}=-\lg\_2p, $$ so you should choose $$ m=\frac{nk}{\ln 2}. $$

That actually works out quite nicely. You are going to get a table with about half the bits set and half cleared, so the entropy per bit is going to be maximal, and the probability of a false positive is going to be $0.5^k$.
> 6 votes

# Answer
This is how I use Bloom filter: suppose that full dictionary check is 10x slower than checking a bit in the Bloom filter. Then if you make a Bloom filter having $N$ bits per dictionary word, then average time required for one check would be $1+10/N$. For example, with $N=8$ (i.e., use one byte in Bloom filter per dictionary word), the avg.time will be 2.25 units, i.e., more than 4 times less than 10 units required without Bloom filter.

So, you trade space occupied by Bloom filter for a time spent by each dictionary check. Of course, you also need time to build the filter hash table.
> 3 votes

# Answer
You choose the size of your Bloom filter according to the expected occupancy. If your Bloom filter is full of 1s then it's too small for the number of words you're putting it. Words in a document tend to repeat, so when estimating how big the filter should be, count the number of *unique* words in your document.
> 2 votes

# Answer
The short answer is yes. Because of information theoretical bounds, any probabilistic data structure representing a set that stores arbitrarily large keys with bounded space per key and lets you query arbitrary data for membership must use $\log\_2(1/\epsilon)$ bits per inserted element, where $\epsilon$ is the false positive rate. Afaik, optimal bloom filters use $\sqrt{2}\log\_2(1/\epsilon)$ bits per element. Cuckoo filters can outperform in space but have other tradeoffs.

The advantage of probabilistic filters is not that you avoid linear space bounds, but that they don't require you to store the elements (so the coefficient of the linear growth is very small), and so their size is independent of the type of data you originally stored in them. Furthermore, adding a new element is cheap.

However, bloom filters specifically do not actually save space or lookup time over taking the last $\log\_2(1/\epsilon)$ bits of a good hash function (any suboptimality of hash functions affects bloom tables as well), storing them in a sorted array, and checking set membership with binary search. What they do offer over that is that it is cheap to store one extra element in the filter. Putting the last-bits of hashes in an exact set (BTree, cuckoo hash, etc etc) is the other way to do this, with a few practical tradeoffs vs bloom filters. Bloom filters have the advantage of having reliable asymptotics for every operation and no amortized big-O's.
> 1 votes

---
Tags: data-structures, probabilistic-algorithms, bloom-filters, dictionaries
---


# Question
Title: Translating the in-order index of a node in a complete, balanced binary tree into the level-order index
Consider the topmost part of a complete, balanced binary tree of **all** 64-bit numbers, exemplified here. As highlighted by the lack of a `7*2^64/8` term it is not necessarily full, but it is always complete. The nodes are stored in numerical order (in-order) in a list of which I know the size, and I have the index (call it the *in-order index*) of a node in that sorted list.

I'm trying to get the index (call it *level-order index*) of that same node if the array was stored according to the breadth-first traversal order (level-order) of the tree instead. In the example, the tree root would have level-order index 0 and in-order index 3.

What I've found already is that the level-order index consists of two parts:

* A *base* part which is the amount of nodes contained in the perfect tree above the level in which the node resides.
* An *offset* part which is the amount of nodes to the left of this node in the level in which it is contained.

Summed together, they produce the level-order index.

I have no idea how to find either of these parts from the in-order index. Of course, it is possible by iterating the tree programmatically, but since the exact layout and contents of the entire tree are known simply from the amount of nodes that it contains, I was wondering whether a mathematical relation between these two indices holds. Does anyone have an idea?

# Answer
> 1 votes
I think it is possible by *rescaling* the in-order index to what it would be in a complete and full (perfect) tree, i.e. $perfect\\\_index = index\*\frac{ceil\_2(size + 1)}{size}$ where $ceil\_2(arg)$ computes the next power of two of $arg$.

Then, the level at which this perfect-tree in-order index sits is given as follows: $level = \left \lfloor{log\_2(size)}\right \rfloor - nr\\\_divisible\_2(perfect\\\_index + 1)$ where $nr\\\_divisible\_2(arg)$ computes the number of times $arg$ is divisible by 2. This works because it seems like in a perfect tree, the number of times the $index + 1$ of a node is divisible by 2 corresponds to the *inverse* zero-indexed level number of the level it is contained in. $1 + \left \lfloor{log\_2(size)}\right \rfloor$ represents the total number of levels ($nr\\\_levels$) in a complete tree, so that minus the *inverse* level index minus 1 should give the zero-indexed level index in narrow-to-wide (top to bottom) tree orientation.

Then, the numerical spacing between in-order node indices in zero-indexed top-to-bottom level $L$ is 2 for the bottom level, 4 one up, 8 one up etc, in other words: $spacing = 2^{nr\\\_levels - L}$. For a 1-indexed in-order index, there is an additional spacing of $\frac{spacing}{2}$ at the beginning of the level. The horizontal offset of the node into the level is therefore given by $h\\\_offset = \frac{perfect\\\_index + 1 - \frac{spacing}{2}}{spacing}$.

Lastly, the amount of nodes preceeding the level this index is contained in is given by the size of a perfect tree of depth $nr\\\_levels - 1$, which is $base = 2^{nr\\\_levels}−1$.

The zero-indexed level-order index into the perfect tree should now be $base + h\\\_offset$. Since the level-order index of the first $size$ (counted in breadth-first traversal order) nodes is the same whether the tree is perfect or complete, I *think* this index will also be the level-order index into the complete tree.

Note that I have no proof of any of this, and have not tested it yet. Specifically, what worries me most is the rescaling at the beginning and if that is allowed/will work at all. The rest might contain errors but is not fundamentally flawed I think.

---
Tags: algorithms, data-structures, binary-trees, mathematical-foundations, breadth-first-search
---


# Question
Title: Which could be a possible time complexity?
I have the following algorithmen (picture) which calculates a Vertex Cover and gets an undirected $G(V,E)$ Graph as input.

The following task is to find the possible Time complexity (estimate) while $n = |V|$, $m = |E|$, $n \le m + 1$ and $deg(v) = |N(v)|$:

a) $O(n log n)$

b) $O(n + m)$

c) $O(2^n\*m)$

d) $O(n^k\*m)$

e) $|V| \choose k$ * $\sum\_{v \in V} deg(v) $

---

Clearly a,b cannot be an estimate running time for the algorithm.

e) looks correct, but c and d?

# Answer
$n=|V|$, and $\sum\_{v\in V}deg(v) = 2\cdot |E| = 2m$ (each edge is counted exactly twice).

Take a look here for a proof why ${n \choose k} = \Theta(n^k)$ **for a fixed $k$**. Substitute everything, and get that also $O(n^k\*m)$ is a valid estimate (again, only if $k$ is a fixed number!).

c) Is clearly not a tight bound, since it doesn't even depend on $k$ (although, this statement is by no means a proof).
> 0 votes

---
Tags: time-complexity
---


# Question
Title: Half precision floating point question -- smallest non-zero number
There's a floating point question that popped up and I'm confused about the solution. It states that

> IEEE 754-2008 introduces half precision, which is a binary floating-point representation that uses 16 bits: 1 sign bit, 5 exponent bits (with a bias of 15) and 10 significand bits. This format uses the same rules for special numbers that IEEE754 uses. Considering this half-precision floating point format, answer the following questions: ....
>
> What is the smallest positive non-zero number it can represent?

The answer says: bias = 15 Binary representation is: $0 \\, 00000 \\, 0000000001 = 2^{-14} * 2^{-10}=2^{-24}$

I've understood the binary representation part, but how does it get to those exponents of 2??

# Answer
In this example, $2^{-10}$ is the mantissa, and $2^{-14}$ is the exponent.

For a fuller explanation of subnormal numbers in IEEE-754 floating point, see this previous answer.

Your example binary16 (i.e. half-precision) floating point number is a subnormal number because the exponent field is the "all zeroes" pattern. This means:

* The significand field contains the fractional part of the mantissa, with an implicit "0" to the left of the binary point.
* The exponent is set to $2^{-14}$. For binary32 (i.e. single precision) this would be $2^{-126}$ and for binary64 (i.e. double precision) it would be $2^{-1022}$.

So the number is $+0.0000000001\_2 \times 2^{-14} = 2^{-24}$.
> 1 votes

# Answer
Three simple steps:

1. Write down how the number 1.0 is represented.
2. Write down how the smallest normalised number is represented, and find its value.
3. Find out how denormalised numbers are represented, and find the representation and value of the smallest denormalised number.
> 0 votes

---
Tags: number-theory, floating-point, binary
---


# Question
Title: Computing the right tangent of two convex hulls
My question deals with the algorithm of computing the convex hull in 2D by Preparata.

Let us assume we have two sets, $A$, $B$, of points in the plane. Let $CH(A)$ and $CH(B)$, denote the convex hulls of the two sets, A and B respectively. And suppose that $y(a) \< y(b)$ for all $a \in A$ and $b \in B$.

Let $CH(A) = \\{a\_{0},...,a\_{n}\\}$ and $CH(B) = \\{b\_{0},...,b\_{m}\\}$ such that we have indexed both sets to be clockwise sequences.

Now there is $k$ such that $x(a\_{k}) = \text{max}(x(a\_{i}))$ for all $ 0\leq i \leq n$ and $j$ such that $x(b\_{j}) = \text{max}(b\_{l}))$ for all $0 \leq l \leq m$.

Now our first task is to find the common tangents of $CH(A)$ and $CH(B)$. My question is about finding the right tangent.

Now let $\alpha\_{i, i+1}$ denote the slope of the two points $a\_{i}$ and $a\_{i+1}$; $\beta\_{j,j+1}$ denote the slope of the two points $b\_{j}$ and $b\_{j+1}$; $\gamma\_{i,j}$ denote the slope of the two points $a\_{i}$ and $b\_{j}$ (all indices are taken mod n and mod m).

Suppose $a\_{i^{\*}}$ and $b\_{j^{\*}}$ denote the two endpoints of the right tangent. Preparata states the two endpoints of the right tangent satisfy the following:

(1) $i^{\*} \> 0: \alpha\_{i^{\*},i^{\*}+1} \< \gamma\_{i^{\*},j^{\*}} \leq \alpha\_{i^{\*}-1,i^{\*}}$

(2) $i^{\*} = 0 : \alpha\_{0,1} \< \gamma\_{1,j^{\*}}$

(3) $j^{\*} \> 0: \beta\_{j^{\*},j^{\*}+1} \leq \gamma\_{i^{\*},j^{\*}} \< \beta\_{j^{\*}-1,j^{\*}}$

(4) $j^{\*} = 0: \beta\_{1,2} \leq \gamma\_{i^{\*},1}$

However I found that if we take $A = \\{(0.2,0.2),(0.3,1.3),(1.2,1)\\}$ and $B = \\{(2,2),(2,3),(2,3)\\}$ then we have the following picture:

We see that the left endpoint (i.e. the endpoint in $CH(A)$) of the right common tangent should be $(0.2,0.2)$ and the right endpoint (i.e. the endpoint in $CH(B)$) should be $(3,2)$ .

However the criterion that Preparata claims does not select $(0.2,0.2)$ as the left endpoint, since it does not satisfy $(2)$, but $(0.3,1.3)$. Why does this occur? Does Preparata's algorithm have some other claim that it needs to be correct?

Here is a link to the original paper:

http://www.cs.jhu.edu/~misha/Spring16/Preparata77.pdf

The section I'm referring to is called "Merge Algorithm for Two-Dimensional Sets."

# Answer
The paper of Preparata and Hong says:

> We let $l\_A$ and $r\_A$ be two points of A such that $x\_2(l\_A) = \min\_i {x\_2(a\_i)}$ and $x\_2(r\_A) = \max\_i{x\_2(a\_i)}$; similarly $l\_B$ and $r\_B$ are defined in B.

and:

> Without loss of generality, we shall also assume that $r\_A = a\_1$ and $r\_B = b\_1$.

So, in this notation, vertices in your two polygons will be numbered differently:

$$A=((1.2,1),(0.2,0.2),(0.3,1.3))$$ $$B=((3,2),(2,2),(2,3))$$

In simple words, the algorithm starts from rightmost vertices on both polygons and continues clockwise potentially until leftmost vertices - so, only lower sides of both polygons will be involved. Tangential vertices $(0.2,0.2)$ and $(3,2)$ will be found.

This paper has been published long time ago, and since then this algorithm has been clarified and simplified. The newest version of it starts from the **rightmost** vertex on the **left** polygon and the **leftmost** vertex on the **right** polygon, and continues clockwise for the left polygon and counterclockwise for the right polygon (to find *lower* tangential line). Also they usually check a vertex location relative to a line using the dot product instead of calculating and comparing slopes - because the tangential vertex has to have both its neighbors on the same side of the tangential line. For more information, pictures and code - please see this monograph, Section 3.8.
> 1 votes

---
Tags: algorithms, computational-geometry
---


# Question
Title: Do relativized relations between complexity classes tell us anything about the nonrelativized relation?
The existence of relativized relations between complexity classes seems to often be treated as "circumstantial" evidence about the "true" or "real-world" (i.e. nonrelativized) relation between the classes. (For example, this lecture describes one particular oracle separation as "formal evidence" that the complexity classes are unconditionally distinct.) However, as far as I understand (please correct me if I am wrong), for complexity classes $A$ and $B$ and an oracle for a language $L$, all four of these cases are logically possible:

1. $A = B$ and $A^L = B^L$
2. $A = B$ and $A^L \neq B^L$
3. $A \neq B$ and $A^L = B^L$
4. $A \neq B$ and $A^L \neq B^L$

So presuming that at the end of the day the unrelativized result is what we really care about, what are relativized results "good for"?

I can see one application: if we happen to be able to find oracles for two languages $L$ and $L'$ such that $A^L = B^L$ and $A^{L'} \neq B^{L'}$, then that tells us that any proof that either $A = B$ or $A \neq B$ cannot relativize, and this fact saves us a lot of time by allowing us to immediately skip many potential proofs.

But do oracle results give us any evidence about the actual relation? In particular, why are oracle separations treated as "evidence" (though not a proof) that the complexity classes are unequal? How strong does the complexity-theory community consider such evidence to be? (I know that last question is subjective and hard to answer precisely.)

# Answer
I am by no means an expert, but 2 things come to mind:

1. Because if we know things like $A^L \neq B^L$, for some $L$, then a proof of $A = B$ need to be non-relativizing. This puts constrains on the techniques used for such a proof, and thus it is helpful in the way towards getting a proof.
2. Because if you prove $A^L = B^L$, and the oracle is not very strong, then it seems that you are narrowing down the possibility of $A \neq B$, as with some extra help they become equal. This can arguably be evidence towards believing that $A = B$. To me it feels like saying that John and Peter were equally strong in a fight with boxing gloves. That doesn't necesarily mean that they will be equally strong without the gloves, as one of them could be weaker but use the gloves better. Nevertheless, the information about their fight with gloves is arguable evidence of their relative strength.
> 4 votes

---
Tags: complexity-theory, complexity-classes, oracle-machines, relativization
---


# Question
Title: Proof of NP-completeness via extra information
I have a set of multisets $S = \\{ X\_1, \dots, X\_K\\}$ where $X\_i \subset \mathbb{R}$. I need to find an optimal partition $L^\*, R^\*$ such that this $E(L) + E(R)$ is minimized. Denote $K(X) = \cup\_{I \in X} I$, then $E(X) := \sum\_{i \in K(X)} |i - \text{median}(K(X))|$, where $|.|$ is the absolute value. $X\_i$ might contains duplicated elements and all operations are on multisets; in $K(X)$, $\cup$ is a union of multisets, and in $E(X)$, $\sum$ adds "with repetition" (repeated elements are summed multiple times).

I want to prove this problem is hard, but I don't have a very straightforward way to prove it's NP-complete. What I did instead was assuming given extra information, suppose I know the median of both $K(L^\*)$ and $K(R^\*)$, and then I can show find the optimal partition is an integer linear programming problem, which is NP-complete. Can I conclude the original problem is at least NP-complete?

---

For the sake of sharing, a wrong attempt I did on proving NP-completeness of with extra information problem.

I was converting this "given $m\_L = \textbf{median}(L), m\_R = \textbf{median}(R)$ and $S$, find $L$ and $R$" problem into a integer programming feasibility problem. Thanks to D.W helped me, I should do the opposite. Maybe doing the opposite is also possible. So sharing my effort in case it helps.

We can collect two vectors $A, B$ with length $K$, for every $X\_i \in S$, get the imbalance with respect to $m\_L$ and $m\_R$. Namely $A\[i\] = \sum\_{j \in X\_i} sign(m\_L - j) $, $B\[i\] = \sum\_{j \in X\_i} sign(m\_R - j) $, where $$\text{sign}(x) = \begin{cases} 1 &\text{if }x\>0\\ 0 &\text{if }x=0\\ -1 &\text{if }x\<0 \end{cases}$$

Now we can introduce another boolean indicator vector $I = \\{0, 1\\}^K$. When $I\[i\] = 0$, we assign $X\_i$ to $L$, if $I\[i\] = 1$, we assigns $X\_i$ to $R$.

$$ \langle I, A \rangle = 0 \\ \langle 1-I, B \rangle = 0 $$

Since $m\_l$ is the median of $L$, we would definitely have the sum of imbalance equals to 0. The same applies to $m\_R$. And here $A, B$ are coefficients and $I$ is the variable. If such a problem has any solutions, then we found $L$, $R$.

And clearly, the newly formed problem is an integer programming problem. Which is well-known NP-complete. Whether if it is possible to convert any such type of problem into our set partition problem in polynomial time, I still need some help

# Answer
No. Your argument is not valid; it doesn't prove NP-completeness. You have shown that an ILP solver can be used to solve your problem. But an ILP solver can be used to solve easy problems, too, so it doesn't rule out the possibility that your problem might be easy (solvable in polynomial time). The reduction needs to go the other way. I suggest studying standard material on NP-completeness and reductions, e.g., What is the definition of P, NP, NP-complete and NP-hard? and What are common techniques for reducing problems to each other? and How do I construct reductions between problems to prove a problem is NP-complete?.

As it happens, I believe your problem can be solved in polynomial time; in other words, I believe it is not hard. I believe the following algorithm solves your problem:

* Enumerate over all possibilities $m\_L,m\_R$ for $\text{median}(K(L))$ and $\text{median}(K(R))$. For each such possibility:

+ Find the partition $L,R$ that minimizes $E(L)+E(R)$, subject to the requirement that $\text{median}(L)=\mu\_L$ and $\text{median}(R)=\mu\_R$.
* Output the best solution found at any of these stages.

I show below how to do the innermost step in polynomial time. This gives a polynomial-time algorithm for your problem, as there are only $O(n^2)$ possibilities for $m\_L,m\_R$ (i.e., each $m\_L,m\_R$ must be an element of $\cup\_i X\_i$).

We'll use dynamic programming for this. Let $\text{imb}(T,m)$ be defined by

$$\text{imb}(T,m) = (\sum\_{t \in T} \text{sgn}(t-m), \sum\_{t \in T} (t=m))$$

where the sum is "with repetition", and where

$$\text{sgn}(x) = \begin{cases} 1 &\text{if }x\>0\\ 0 &\text{if }x=0\\ -1 &\text{if }x\<0 \end{cases}$$

$$(x=y) = \begin{cases} 1 &\text{if }x=y\\ 0 &\text{otherwise} \end{cases}$$

Define the imbalance of a partition $L,R$ with respect to $m\_L,m\_R$ to be the pair $(\vec{b\_L},\vec{b\_R})$ where $\vec{b\_L}=\text{imb}(L,m\_L)$ and $\vec{b\_R}=\text{imb}(R,m\_R)$. Then we can reformulate the problem as follows:

Given $m\_L,m\_R$, find $L,R$ that minimizes $E(L)+E(R)$ subject to the requirement that the imbalance of $L,R$ with respect to $m\_L,m\_R$ is $(0,0)$ (or $+\infty$ if no such partition exists).

Now we can solve that using dynamic programming. Define $A\[k,\vec{b\_L},\vec{b\_R}\]$ to be the smallest possible value of $E(L)+E(R)$ subject to the requirements that $L,R$ are a partition of $X\_1,\dots,X\_k$ with imbalance $(\vec{b\_L},\vec{b\_R})$ with respect to $m\_L,m\_R$ (or $+\infty$ if no such partition exists). Then $A$ satisfies the recurrence relation

$$A\[k,\vec{b\_L},\vec{b\_R}\] = \min(A\[k-1,\vec{b\_L}-\text{imb}(X\_k,m\_L),\vec{b\_R}\] + \sum\_{i \in X\_k} |i - m\_L|,A\[k-1,\vec{b\_L},\vec{b\_R}-\text{imb}(X\_k,m\_R)\] + \sum\_{i \in X\_k} |i - m\_R|).$$

Using this recurrence, you can fill in the array $A$ in $O(Kn^4)$ time, where $n=|\cup\_i X\_i|$ is the number of elements (counting repetitions): you just initialize every entry to $+\infty$ except that $A\[0,0,0\]=0$, then fill it in, in order of increasing $k$. Then, scan all $A\[K,(a,b),(c,d)\]$ such that (i) $|a|\<b$ and $b\>0$, or $a=0$, and (ii) $|c|\<d$ and $d\>0$, or $c=0$; the smallest such value is the answer to the original problem.
> 2 votes

---
Tags: complexity-theory, np-complete
---


# Question
Title: What's the name of this packing problem?
I'm trying to pack sets of intervals, to find distinct buckets of intervals. The buckets should not be overlapping.

For example if I have these intervals:

```
A: [ [0, 10] ]
B: [ [1, 3], [5, 7] ]
C: [ [8, 10] ]

```

I want to get the following result:

```
[0, 1]: [A]
[1, 3]: [A, B]
[3, 5]: [A]
[5, 7]: [A, B]
[7, 8]: [A]
[8, 10]: [A, C]

```

What's the name of this problem?

# Answer
The problem can be stated as finding the elementary intervals for a given set of intervals. It is a technique frequently used for problems in computational geometry (as suggested by nir shahar also).
> 1 votes

---
Tags: algorithms, terminology, intervals, packing
---


# Question
Title: How many vertices should be disconnected to make a graph acyclic?
Given an undirected graph with some cycles:

we can "disconnect" the red vertex by adding a separate vertex to each of the edges adjacent to it:

In this case, disconnecting a single vertex makes the graph acyclic.

My questions:

* What is a term for the smallest number of vertices that must be "disconnected" like this, to make the graph acyclic?
* What is an algorithm for finding a smallest such set of vertices?

(I found some related concepts, but they are different:

* The circuit rank is the number of *edges* that have to be removed to make the graph acyclic; it always equals the number of edges minus the number of vertices plus the number of components.
* The vertex connectivity is the number of vertices that have to be removed to make the graph *disconnected*.)

# Answer
A set of vertices whose removal makes the graph acyclic is called a feedback vertex set (FVS). What you seem to be doing is finding the smallest FVS, subdividing all edges incident to each vertex in the FVS, and finally deleting the vertices in the FVS.

Computing the smallest FVS is NP-hard, but it admits 2-approximation.
> 4 votes

# Answer
If you have a connected graph, e.g. Prim's algorithm gives you a spanning tree (no cycles).
> -2 votes

---
Tags: graphs
---


# Question
Title: The subset sum problem is not in P because the question is about lossy compressed data? Why not?
Where is there a gap or error in my reasoning?

The subset sum problem deals with a set of n numbers, which is the result of lossy compression of an array r of numbers (r = (2^n)-1).

The compression algorithm in brief:

1. check if the size of the set r +1 is a power of two. If not, terminate compression
2. check all combinations without repetition of size log2(r+1) if any of them can be decompressed (summing all possible subsets without empty subset) to the set r of numbers. If so, return the combination
3. if no suitable combination is found, terminate compression.

The subset sum problem is to check whether the set r of numbers (that is, the set of sums of subsets of the set n of numbers) contains the number you are looking for. To do this, you can represent the set r of numbers as an array and search it. Searching the array in the worst case requires checking each element, which is O(r) (for a decompressed set) or O(2^n) (for a compressed set). Faster ways such as binary search are known, but they require knowledge of the ordering of numbers, so that by checking one number we also gain knowledge of where to look for other numbers. Without knowing anything about the ordering of the numbers in the array, you can't search the array faster than linearly, because by checking the numbers one by one, you don't get any knowledge of where the number you're looking for might be.

Does the compressed set of n numbers have information about the ordering of the array of r numbers? No.

The number of possible orderings of a set r of numbers is r!, or ((2^n)-1)!, which is a number greater than n! Pigeonhole principle says that if we have 'a' objects that we put into b drawers and a \> b then there must be at least one drawer where there will be at least two objects. According to this rule, the set of n numbers cannot contain explicit information about the ordering of the elements in the array r of numbers, because many orderings of the array r of numbers can be compressed into the same array of n numbers, with the same elements and their ordering, and we do not get any other information besides this set. The ways to generate combinations in the compression algorithm are many, by which we can consider that every ordering of an array r of numbers can be compressed into every possible ordering of a set of n numbers.

If the subset sum problem is in P, then there exists a search algorithm that will answer the subset sum problem in polynomial time calculated from the size of the compressed set of n numbers. From this, we can conclude that to find a number in an array r of numbers in faster than linear time, it is sufficient to subject the array to lossy compression rather than sorting. When we subject the sorted array r of numbers to compression, we retain the ability to search it in faster-than-linear time, despite the fact that the compression was lossy and as a result, we lost ordering knowledge and most of the content knowledge. The data can be reconstructed, but only by generating the sums of every possible subset and sorting them, since we know from principle pigeonhole that the original ordering knowledge has been lost and must be acquired anew.

Losing knowledge of the ordering of an array r of numbers ( and most of its contents) while still being able to search it in faster than linear time does not make sense, from which it follows that there is no algorithm that allows this, which means that the subset sum problem is not in P, and since SSP is in NP then P != NP.

# Answer
> 1 votes
The subset sum problem is quite different from your problem: Given a list of integers and a target sum $S$, it asks if there is a subset of the list that sums to $S$. No "compression", lossy or not. Any lossy technique will (by definition) tend to miss the target (because it works with an approximation). And we are looking for an *exact* solution, not one that is 10% off, it has to be right on.

It looks to me that the collection of subsets for which you need to compute the sums is even larger than the numbers in the original list. If so, it isn't any speedup.

---
Tags: complexity-theory, np-complete, p-vs-np, subset-sum
---


# Question
Title: Representing abstract syntax tree as a graph
Does it make sense to represent an AST as a graph? How can one achieve a mapping between ASTs and graphs that preserves both semantic and syntactic properties of source code?

The goal and application of such a transformation would be to use graph neural networks and other deep "graph" learning techniques to extracts features, clustering source code, find code similarities and suggest code completion tasks.

Any suggestion of current algorithms and research in this area?

# Answer
> 3 votes
Every tree is itself a graph, so of course an AST is a graph -- no mapping is needed, it is already a graph. I don't see any way that this is useful in practice, though.

Rather than trying to convert to a graph and then use graph neural networks, I suggest using a more direct approach: e.g., using a neural network on the AST or on the code itself. Since you haven't told us what you want to do with the neural network, it's impossible to suggest something more concrete, but I encourage you to do a literature search; there are many recent papers on using neural networks on code.

---

Alternatively, if you insist on having a graph somewhere, perhaps you will be interested in learning about control-flow graphs, which are one use of graphs in program analysis where the graph structure is useful.

---
Tags: graphs, machine-learning, trees, compilers
---


# Question
Title: Proof of Correctness : Arranging the sheep
I've come across a question in Codeforces contest 719(Div - 3).

The problem goes like this :

I was able to solve the problem by using another approach but had to use 4\*n auxiliary space, where n is the length of the input string however the solution given in the editorial is way more efficient

The editorial goes like this

It basically says to choose the sheep whose number is ⌈k/2⌉ as pivot.(In the editorial they gave it as n/2 which is wrong. Consider it to be k/2, where k is the number of sheep in the given string.)

Here's my doubt Why sheep at present at ⌈k/2⌉ should make 0 moves to get an optimal solution. I've searched the internet but couldn't find the proof. Can someone give me a generalized proof for this?.. Thanks in advance :)

Problem Link :- https://codeforces.com/contest/1520/problem/E

Editorial Link :- https://codeforces.com/blog/entry/90342

Note :- The editorial link has the solutions for all the problems. Scroll down to find the editorial for Arranging the Sheep problem.

# Answer
> 0 votes
The reason is instead of aligning the sheep at the edge, you want to align them at that sheep.

Example:

`*.*.*`

Here, instead of solution `..***` (3 moves) or `***..` (3 moves), the ideal solution is `.***.` (2 moves).

Proof:

Clearly, some sheep makes 0 moves in the optimal solution. Assume in the optimal solution, `i < m` is that sheep, and the solution takes less steps than using `m`.

Since the solution takes less steps than the `m` solution, we know `m` makes at least one step, and all `j > m` also make at least one step. If instead we use `m` as pivot, we save either one or zero steps, as now the lower half has to make the same steps instead, but that is at most one more than the upper half had to do (because there is at most one more sheep in the lower half). Together with the step `m` doesn't need to make, we get the contradiction that the `m` solution has to be at least as good as the `i` solution.

---
Tags: algorithms, algorithm-analysis, greedy-algorithms, correctness-proof, mathematical-programming
---


# Question
Title: Minimizing sum of $w_i(y_i - y_c)$ over $y_c$
A person wants to connect $n$ circuit points to the clock signal. Now, the clock signal is going to pass parallel to the x-axis and all those circuit points are going to be connected by vertical to the clock line. Suppose the widths of the vertical wires in the given diagram also vary varying.

If the coordinates $(x\_i,y\_i)$ for each circuit point $c\_i$ to be connected are given, find $y=y\_c$, through which the clock line should pass to minimize the expression

$$L = \sum\_{i=1}^n w\_i(y\_i - y\_c)$$

Also prove that your solution is optimal.

# Answer
> 1 votes
$x\_i$ is irrelevant, it doesn't appear in the objective function.

$y\_i$ and $w\_i$ are constant.

So the minimization simplifies to:

$$\operatorname\*{argmin}\_{y\_c} \sum{i=1}^n w\_i(y\_i - y\_c) = \operatorname\*{argmin}\_{y\_c} \sum\_{i=1}^n w\_iy\_i - \sum\_{i=1}^n w\_iy\_c,$$

which is either

$$\operatorname\*{argmin}\_{y\_c} -\left(\sum\_{i=1}^n w\_i\right) y\_c $$

or

$$\operatorname\*{argmax}\_{y\_c} \left(\sum\_{i=1}^n w\_i\right) y\_c $$

So depending on whether the sum of your weights is positive or negative, either the highest or lowest $c\_i$ should be $c$.

---
Tags: algorithms
---


# Question
Title: Difference between specifying argument and not in NumPy
Running these lines in Colab:

```
import numpy as np
size  = 2**13
%timeit np.random.normal(size=(size, size))
print("-----------")
%timeit np.random.normal((size, size))

```

yields:

```
1 loop, best of 5: 2.67 s per loop
-----------
The slowest run took 7.05 times longer than the fastest. This could mean that an intermediate result is being cached.
10000 loops, best of 5: 16.3 µs per loop

```

Why is the difference in computational time between these two lines of code so large? In my mind they should be the same.

# Answer
> 0 votes
This due to the order of optional arguments. Perhaps this example can explain thing for you:

```
def foo(x = 1, y = 2, z = 3):
    print((x, y, z))

```

```
In [1]: foo()
(1, 2, 3)

In [2]: foo(4)
(4, 2, 3)

In [3]: foo(z = 4)
(1, 2, 4)

```

Now looking at help about `np.random.normal`, we get:

```
In [4]: help(np.random.normal)
Help on built-in function normal:

normal(...) method of mtrand.RandomState instance
    normal(loc=0.0, scale=1.0, size=None)

```

That means that since `loc` is the first optional argument, `np.random.normal((size, size))` is interpreted as `np.random.normal(loc = (size, size))` and not as `np.random.normal(size = (size, size))`

---
Tags: python
---