title: network address translation

text:
# Question
Title: network address translation
I'm having some difficulty understanding ip addresses. Let's say:

**Question Info:**

private subnet 192.168.0.0/24

IP addresses 212.201.49.1-5

Now, a host 192.168.0.2:1234 retrieves a web page from the web server at 42.35.12.33.

Then, host 192.168.0.5:1234 retrieves a web page from the web server at 100.12.45.11

**Answer Part:**

Now, I have this information for first the **request** part:

internal

192.168.0.2:1234 (src)

42.35.12.33:80 (dest)

external:

212.201.49.1:1234 (src)

43.35.12.33:80 (dest)

**Where does 80 come from at the end of dest?**

Now, for the second request, the src address of external is 212.201.49.2:1234.

**Why is it 2.1234? In the 3rd one, it was 1 again.**

# Answer
Usually writing an ip address and a number after the : ,it means the number after the : is the port

In the internal part: 192.168.0.2 is the private ip address of the host its his ip address inside the network,notice that we have 2 types of ip addresses: private ip address-which is the ip address inisde out network and public ip address which is our ip address in the "internet" so 192.168.0.2 its the private ip address of the host and the 1234 its the port of the client-the host

now the 42.35.12.33 is the ip address of the web page and the page listens to the port 80

In the external part: we can see the ip address of the host has changed,why has it changed?because what i said before about private and public ip addresses this-this ip is the external ip which the host was provided(i suggest reading about NAT if you want to understand this part deeper) the port of the host stays 1234
> 1 votes

---
Tags: computer-networks, tcp, ip
---


# Question
Title: interval scheduling variant: 1 machine with 2 tasks need to complete only
I am looking for an optimal solution of an interval scheduling variant.

Basically, given n tasks with the start time Si and end time Ei, select EXACTLY two tasks whose execution periods are maximum and do not over lap (Equal start/end time counts as overlapping).

So if there are these task \[9-14\], \[7-13\],\[1,4\],\[2-5\],\[2-10\],\[4-9\]

The answer would be \[1,4\] and \[7-13\], whose execution time are 3+6=9 in total.

I can only think of an algorithm with n^2 complexity. That is the obvious solution of matching every period together, check if they overlap, and if they don't, replace a previously initialized Max value with their sum if it \> Max. It does not seem to be optimal, as it does not pass the time test in my professor exercise.

So anyway, can anyone think of a more optimal solution?

# Answer
> 0 votes
Let $max$ be the maximum period of the tasks we have checked so far. Let $max2$ be the maximum sum of two non-overlapping tasks we have checked so far. Both of them are 0 initially.

Sort all start times and end times of the given tasks. Iterate over them, from the smallest to largest.

* A start time is encountered. If the sum of the period of the corresponding task and $max$ is greater than $max2$, update $max2$.
* An end time is encountered. If the period of the corresponding task is greater than $max$, update $max$.

Now $max2$ is what we wanted. The algorithm runs in $O(n\log n)$.

The above algorithm does not specify what to do when multiple times are encountered at the same time. That part should be easy for you to fill in.

---
Tags: algorithms, optimization, dynamic-programming, scheduling
---


title: Proving 2 heuristics are admissible

text:
# Question
Title: Proving 2 heuristics are admissible
We have $h\_1(n)$ and $h\_2(n)$ which are both admissible heuristics. We know that $h\_1(n) \< h\_2(n)$ for every state $n$ in a search problem.

Now we are given two heuristics $h\_3(n)=\frac{h\_1(n)}{1+h\_2(n)}$ and $h\_4(n)=\frac{h\_2(n)}{1+h1(n)}$ and we want to prove $h\_3(n)$ and $h\_4(n)$ are both admissible.

# Answer
The only additional constraint which is required for $h\_3$ and $h\_4$ to be admissible is that both $h\_1(n)$ and $h\_2(n)$ return non-negative values for any state $n$, but this is always accomplished ---even if a heuristic function might return a negative value it just suffices to take the maximum between the value returned and 0, and this operation clearly preserves admissibility.

Thus, given that $h\_1(n), h\_2(n) \geq 0$ for every state $n$ and that both are admissible, it is easy to see that the values of $h\_3(n)$ are upper bounded by those of $h\_1(n)$ (the maximum value taking place when $h\_2(n)=0$) Since $h\_1$ is admissible so it is $h\_3$; conversely, if $h\_2(n)$ returns any strictly positive value then $h\_3(n) \< h\_1(n)$. Now, if $h\_1(n)$ is not overestimating the effort to reach the goal, then $h\_3(n)$ is neither as well and thus, $h\_3$ is admissible in this case also.

The proof of admissibility of $h\_4$ follows the same lines.

Note that in these proofs it is never required for any heuristic function to strictly dominate another, i.e., the condition $h\_1(n) \< h\_2(n)$ is useless and not necessary at all. The only important requirement is that none ever return negative values, but this is a trivial requirement.

To conclude, I think this is mostly a theoretical exercise. Note that as mentioned above $h\_3$ and $h\_4$ are upper bounded by $h\_1$ and $h\_2$ respectively so that, in other words, they are less informed than them. In other words, these transformations are of no interest.

Hope this helps,
> 2 votes

---
Tags: search-algorithms, heuristics
---


# Question
Title: PAC learning vs. learning on uniform distribution
The class of function $\mathcal{F}$ is PAC-learnable if there exists an algorithm $A$ such that for *any* distribution $D$, any unknown function $f$ and any $\epsilon, \delta$ it holds that there exists $m$ such that on an input of $m$ i.i.d samples $(x, f(x))$ where $x\sim D$, $A$ returns, with probability larger than $1-\delta$, a function which is $\epsilon$-close to $f$ (with respect to $D$). The class $\mathcal{F}$ is efficiently PAC learnable if it is PAC learnable, and $A$ runs in time $\text{poly}(1/\epsilon, 1/\delta, n)$ (where $|x| = n$) and the description of $f$.

Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?

# Answer
> 2 votes
> Is there a case where a class $\mathcal{F}$ is not efficiently PAC learnable, yet it is efficiently learnable on the uniform distribution?

This has been asked on TCS.SE. It looks like the short answer is yes -- Aaron Roth gives the example of width-$k$ conjunctions for $k \gg \log n$. And in the comments, Avrim Blum is quoted as giving the answer of $2$-term DNF.

I don't totally understand the examples there -- it must take a bit more work to really derive the result (I will update this answer if I find a self-contained proof). But the general problem here with the uniform distribution is that if the target function $f$ is "sparse", meaning it labels at most a $\delta$ fraction of the input distribution with $1$, then it is easy to learn by simply guessing $0$.

---

Beyond just efficient (polynomial) PAC learning, there are other examples where the uniform distribution seems to help. For example, a classic hard problem for PAC learning is DNF, a problem which is conjectured to be not PAC learnable, and quite hard. On the other hand DNF over the uniform distribution is almost PAC learnable: we have a *qausi*polynomial time algorithm for it. See these notes and these notes.

In summary, there appears to be a lot of work on learning under the uniform distribution (search "PAC learning under uniform distribution" for additional references). And it seems that this problem is easier than studying PAC learning, where we aren't able to prove much. Quoting Ryan O'Donnell's notes above:

> General PAC-learning insists that one algorithm works simultaneously for all distributions. In fact, the machine learning community interested in real-world applications finds the uniform setting questionable: "They’ll punch you in the nose if you try to tell them about algorithms in this framework." --Ryan. But, in a more general framework, no one can really prove anything.

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


# Question
Title: Preprocess data such that locations within a rectangle drawn on a map can be found in less than O(n) time
I came across this problem online and found no solutions or insight. The problem is stated as:

> Given a map as a square, and a set of locations on the map, users are able to select a rectangle on the map and all of the locations on the map are returned How would you preprocess the map data so that the find operation for the locations in the inner rectangle can be done in less than O(n) time?

I'm really stumped on this as the only thing I could think of is to create a hashmap that contains every single possible rectangle within the map with values that are lists of locations within said rectangle. However, it would not be practically feasible to store that much data.

Any help would be appreciated!

# Answer
You should look into R-Trees.

> R-trees are tree data structures used for spatial access methods, i.e., for indexing multi-dimensional information such as geographical coordinates, rectangles or polygons.

The parts that apply the most to your case are the ones described on the Search subsection. This operation on this kind of trees have a complexity of O(logMn):

> In range searching, the input is a search rectangle (Query box). \[...\] the elements are tested against the search rectangle and their objects (if there are any) are put into the result set if they lie within the search rectangle.

Good luck!
> 2 votes

---
Tags: algorithms
---


# Question
Title: Has anyone seen a NP graph problem like this before?
I have a following graph-based problem:

1. Input: positive integers K and L, undirected graph G
2. I have to choose K vertices from this graph
3. In the path between each pair of chosen K vertices there has to be at least L vertices, i. e. there has to be a "space between" each two of chosen vertices made of at least L vertices.

The above of course may not be possible for a given instance of a problem, then I have to check that. I'm quite sure that this problem is NP or even NP-complete, since it has to do with paths with length constraint. Have you ever met a similar problem? Do you have an idea how to reduce it to some more well-known problem, possibly NP, e. g. vertex cover or graph coloring?

Also, note that my graph is a grid graph, which might not be "full" but a subgraph of a full rectangular grid.

# Answer
This is known as the distance-$d$ independent set, i.e., you are looking for an independent set of size $k$ where the distance between every two elements in the solution is at least $d$.

The problem is NP-complete even on planar graphs according to \[1\], but I don't know about its complexity on partial grids.

Regarding reductions, you can probably take the $d$'th power of the graph and find a (distance-1) independent set in that. The claim is that any solution here is a distance-$d$ independent set in the original, but you need to verify this.

---

\[1\] Eto, Hiroshi, Fengrui Guo, and Eiji Miyano. "Distance-$d$ independent set problems for bipartite and chordal graphs." Journal of Combinatorial Optimization 27, no. 1 (2014): 88-99.
> 5 votes

# Answer
In the special case where $L=1$, this is the maximum independent set problem, which is NP-hard on general graphs. Therefore, your problem is NP-hard on general graphs as well.

You could try to hope for an algorithm that is specific to the class of graphs you have (I think the maximum independent set can be computed efficiently in bipartite graphs, and grid graphs are bipartite, so you could try to generalize that algorithm), or you could try using a standard algorithm for maximum independent set / clique, or you could try using a SAT solver. It should be easy to formulate this as a MaxSAT instance: you have a clause for each pair of vertices that are within distance $L+1$ (or less), and you ask the SAT solver to minimize the number of variables set to true.
> 2 votes

# Answer
Seems like checking if there is a K-vertices subgraph of G that is L- colorable using the rules of the graph coloring problem. I mean if all the K vertices are colored with the same color they satisfy ur condition.

Since Graph coloring in NP-Complete u can verify a given solution in polynomial time.

So maybe, just maybe this a first sight answer, u have to

1-check if ur Graph is L-colorable

2-search for a color with a set of K vertices
> 1 votes

---
Tags: graphs, np-complete, reductions, np
---


# Question
Title: What complexity class does is this set of grammars? NL-complete?
> The unrestricted grammars characterize the recursively enumerable languages. This is the same as saying that for every unrestricted grammar `G` there exists some Turing machine capable of recognizing `L(G)` and vice versa.

Context: Grammars are Turing-complete. Therefore complexity classes like NL have equivalences in grammars.

> One important NL-complete problem is ST-connectivity (or "Reachability") (Papadimitriou 1994 Thrm. 16.2), the problem of determining whether, given a directed graph G and two nodes s and t on that graph, there is a path from s to t. ST-connectivity can be seen to be in NL, because we start at the node s and nondeterministically walk to every other reachable node. ST-connectivity can be seen to be NL-hard by considering the computation state graph of any other NL algorithm, and considering that the other algorithm will accept if and only if there is a (nondetermistic) path from the starting state to an accepting state.

Given a directed graph, deciding if `a->b` is a directed path is NL-complete.

We will reduce the directed graph to a grammar rules with one symbol on each side:

For each directed edge in the graph, add a grammar rule. The directed edge `a->b` becomes the grammar rule `a|b`.

The NL-complete query becomes, "If I set `a` to the start symbol, can I derive symbol `b` using the grammar rules?"

Each grammar rule has one symbol on each side (i.e. `a|b`).

Therefore grammar rules with one symbol on each side is NL-complete.

Are grammars consisting only of rules with one symbol on each side NL-complete?

**Related questions:**

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? P-hard?

What complexity class does this correspond to?

# Answer
> 1 votes
Yes, you can build a reduction to show that the following problem is NL-complete:

> Given a grammar where every rule has the form $X \to Y$ or $X \to a$ where $X,Y$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

This problem is equivalent to testing whether $a$ is reachable from $S$ in the corresponding directed graph, which is exactly the ST-connectivity problem.

---

I didn't understand what you meant by `a|b`.

---
Tags: complexity-theory, formal-grammars
---


title: Proving that $S^* = (S^*)^*$

text:
# Question
Title: Proving that $S^* = (S^*)^*$
I am going through some past exam paper questions on regular languages for some revision, and I am having a bit of trouble with converting general ideas into formal mathematical proofs.

The question is:

> **Given regular expression $S$, prove formally that $S^\* = (S^\*)^\*$**.

My problem is expressing this in a formal proof. Here is what I have worked through so far (it is a bit all over the place and just a collection of ways to express the problem mostly)

$S^\* = (S^\*)^\*$

this implies:

$S^\* \subseteq (S^\*)^\*$ **and** $S^\* \supseteq (S^\*)^\*$

if we assume that there exists $w\_k$ such that $w\_k \in S^\*$

then the base case for the proof is:

$k = 0$ $(w\_k = \epsilon)$ (empty word, always in $S^\*$ and $(S^\*)^\*$ by definition)

$k = 1$ $(w\_k \in S^\*)$

and that's kind of where my ability to reason ends.

I think the rest of it will be something like:

$w\_{k+1} = w\_kx$

ie. $w\_k$ concatenated with $x$ where $x \in S^\*$

but how can I show that $w\_{k+1} \in (S^\*)^\*$?

Any help to push me in the right direction would be greatly appreciated.

# Answer
As you observed, to show $S^\*=(S^\*)^\*$ it will suffice to show $S^\*\subseteq(S^\*)^\*$ and $(S^\*)^\*\subseteq S^\*$. Here's a sketch of a proof of both containments.

For a language $A$, define $A^\*=\\{x\_1x\_2\dots x\_n\mid n\ge 0\text{ and each }x\_i\in A\\}$. Then (with $n=1$) it's clear that for all $x\in A$ we'll have $x\in A^\*$, establishing that $S^\*\subseteq(S^\*)^\*$.

To show containment in the opposite direction, let $x\in (S^\*)^\*$, then by definition we'll have $x=y\_1y\_2\dots y\_n$ where $y\_i\in S^\*$ for all $1 \le i\le n$. Then, again by definition, we'll have $y\_i=z\_{i1}z\_{i2}\dots z\_{in\_i}$ where $z\_{ij}\in S$ for all suitable $i$. We'll then have $$ x=(z\_{11}z\_{12}\dots z\_{1n\_1})(z\_{21}z\_{22}\dots z\_{2n\_2})\dots(z\_{n1}z\_{n2}\dots z\_{nn\_n}) $$ where each $z\_{ij}\in S$. Applying the definition of star one more time we see that $x\in S^\*$, establishing that $(S^\*)^\*\subseteq S^\*$ and hence the desired equality.
> 2 votes

# Answer
Let L be the set of strings derived from S. Prove that both expressions produce exactly the strings $L\_1 L\_2 ... L\_k$ for k \>= 0 where each $L\_j$ is in L, and no others.

You can also check what happens if you replace one, two, or three of the stars in the expression with “+”. With some changes the expression stays true.
> 0 votes

---
Tags: regular-languages, proof-techniques, induction
---


# Question
Title: Why is the second operation of a Monad called bind?
I understand how monadic computation works, I am just wondering where does the name come from. I cannot relate the thing that the `bind` operator actually does (i.e. unbox the monadic value, and then apply a function to produce another monadic value) and the name `bind` (which, to me, means associate two things together).

I understand why we have the name `return` (I suspect it has to do with the Haskell do-notation), although IMHO it isn't a good name either. Return indicates a change in control flow but it really isn't, all it does is produce a monadic value.

# Answer
In Haskell the syntactic sugar for `bind e₁ (λ x . e₂)` is

```
do x ← e₁
   e₂

```

That is, the result of the computation `e₁` is *bound* to `x`, after which `e₂` is computed.

In ML-like languages the same thing is written as

```
let x = e₁ in e₂

```

which again is a form of binding a variable to a value.

As for `return` being a control-flow mechanism – that's precisely what it is. You are probably thinking of control mechanisms for branching, looping, raising exceptions etc. Well, `return` is the one that ends a computation and yields a result.
> 5 votes

# Answer
In λ-calculus, the term $\lambda x. y$ binds $x$ in $y$. Once a value is given to $x$, any well-scoped reference to $x$ in $y$ will be replaced by that same value.

Function composition $(f\circ g)$ can be seen as an operator that binds the result of $g$ to $f$'s argument. In a similar way, you can view `bind : Monad m => m a -> (a -> m b) -> m b` as an operator that binds the contents (the value underneath the monadic wrapper) of its first argument to the function supplied as its 2nd argument (`a -> m b`).

What if the 1st argument of type `m a` is the result of some previously applied function? In general, you can make consecutive applications of `bind` to mimic something like function composition, but under a monad.
> 4 votes

---
Tags: terminology, functional-programming
---


title: New special data-structure

text:
# Question
Title: New special data-structure
I want such data-structure, which can:

1. add element at the end of the array in $O(log (n))$.
2. find out the minimum value in the sub-segment in $O(1)$

# Answer
You can use a Sparse-Table for these type of queries.

Most implementations/tutorials on Sparse-Tables don't actually cover/support the usecase of adding new values (actually I've never seen one before), however it shouldn't be too hard to modify a typical implementation. You basically only need to invert what each entry stores.

Normally a sparse table stores the following things for each element at position $i$. It stores the minimum of the range $\[i, i+1)$, the minimum of the interval $\[i, i+2)$, the minimum of of the range $\[i, i+4)$, the minimum of the interval $\[i, i+8)$, and so forth.

This is a problem when you want to append a new value, because it will affect at least one range for each element, so adding a new element is $O(n)$.

However if you point the ranges in the opposite direction, you do better. So for each element at position $i$, you store the minimum of the ranges $(i-1, i\]$, $(i-2, i\]$, $(i-4, i\]$, and so forth. You can still do the answer minimum queries in $O(1)$, but now if you add a new element at the end, you only need to recompute $O(\log n)$ ranges, namely the new ones for the new element. You don't need to modify the other entries.

One thing that you additionally should take into care. Whenever your array gets gets bigger than a power of 2, you need to compute a new range for each element (in $O(n)$ time). But that's still amortized $O(\log n)$.

---

edit: Actually, now that I think about it more, this $O(n)$ recomputation can be avoided. Notice, that a those new ranges $(i-2^{\log n + 1}, i\]$ will contain exactly the same values as the previous ranges $(i-2^{\log n}, i\]$. Therefore you can always just lookup the largest range $(i-2^j, i\]$ if you want to want to know the range $(i-2^k, i\]$ with $k \ge j$. Then adding a new element works in true $O(\log n)$ time, and not just in amortized time.
> 3 votes

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


# Question
Title: Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree?
Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T\_a$ and $T\_b$, where $Ta$ contains the vertex $a$ and $T\_b$ contains the vertex $b$. Now consider the subgraph of $G$, $G\_a$, which contains the vertices of $G$ that are in $T\_a$, and the edges of $G$ that have both endpoints in $T\_a$

Is $T\_a$ an MST for the subgraph $G\_a$?

Intuitively, I believe $T\_a$ is an MST for the subgraph $G\_a$, but I'm having a lot of difficulty proving the result.

# Answer
Let’s prove this by contradiction. Say $T\_a$ is not an MST of $G\_a$, that means there is some cheaper MST $T\_a^\*$. However, if that were true, then by reconnecting $T\_a^\*$ to $T\_b$ we would obtain a tree that spans $G\_a$ that has a lower weight than the MST $T$, which is a contradiction.
> 2 votes

---
Tags: graphs, weighted-graphs, minimum-spanning-tree, subgraphs
---


title: binary code to encode binary tree

text:
# Question
Title: binary code to encode binary tree
I would like to encode a binary tree where every node has either 0 or 2 kids into a binary word.

I was thinking about marking every left edge with a "0" and every right edge with a "1" and then use every path from root to a leaf concatenated to encode the tree, but I'm not sure if this results in a unique code for every tree?

I thought about it for quite some time but I can not figure out... maybe you know?

# Answer
First of all, let's consider that we are talking about labeled trees. Otherwise it will be difficult to find bijection between trees and binary strings.

Then we can traverse a given tree in-order (https://en.wikipedia.org/wiki/Tree\_traversal#In-order\_(LNR)) and print $1$ each time, when we enter some vertex, and $0$ each time, when we leave some vertex.

Another possible encoding can be constructed in the following way. Let's enumerate all vertices by layers from root to bottom (and from left to right inside each layer). And then let's construct binary string of length $|V|$ where the $i$-th position is $1$ if the corresponding vertex has children and $0$ otherwise.
> 1 votes

---
Tags: binary-trees
---


# Question
Title: What complexity class is this set of grammars? RE?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$, $X \to a$, or $X \to \epsilon$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

(Thanks Yuval Filmus for pointing out this characterization - see first comment in linked question)

What complexity class does this correspond to? RE?

**Related questions:**

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? In between NL and P?

What complexity class is this set of grammars?

# Answer
That grammar is unrestricted (not context free, as there are right hand sides shorter than the corresponding left hand side). The languages they generate are recursively enumerable, recursive only in special cases.
> 2 votes

---
Tags: complexity-theory, formal-grammars
---


# Question
Title: Updating a mst after increasing the weight of an edge in the mst
Suppose we have a weighted undirected graph $G$ and a minimum spanning tree $T$ Let $G2$ be a new graph by increasing the weight of one edge $e = (a,b)$ that is part of $T$.

I'm using a common algorithm to update $T$ so we don't have to find a mst of $G\_2$ from scratch. The algorithm is to first take out $e$ from $T$, which will result in two subtrees $T\_a$, which contains $a$, and $T\_b$ which contains $b$. Then, I iterate over all the edges in $G\_2$ and find the edge with the minimum weight that has one ed in $T\_a$ and the other end in $T\_b$. Call this edge $e\_2$. Then I add this edge into $T$ to get $T\_2$.

I'm having a lot of difficulty proving that $T\_2$ is a mst for $G\_2$. I've proved that $T\_2$ is a spanning tree of $G\_2$, but again, I'm having a lot of difficulty with proving that $T\_2$ is a **minimum** spanning tree.

Any help would be greatly appreciated!

# Answer
> 1 votes
Let $S$ be a spanning tree of an edge-weighted graph. We call $S$ a local-minimum spanning tree (local-MST) of the graph if every edge not in $S$ weighs the heaviest in the cycle created when that edge is added to $S$.

Here is a very useful characterization of MST.

### A spanning tree is an MST if and only if it is a local-MST.

Proofs of the above theorem can be found here or here.

---

Once we are armed with above theorem, it is easy to prove the algorithm in the question does produce an MST.

**Proof of the algorithm**: $G$ and $G\_2$ will be referred as $(G, w\_1)$ and $(G, w\_2)$ respectively, where $w\_1$ is the the original weight function and and $w\_2$ is the updated weight function. $w\_1$ and $w\_2$ are the same except on $e$.

Let $G\_a$ be the subgraph spanned by $T\_a$ and $G\_b$ be the subgraph spanned by $T\_b$. Every vertex of $G$ is either in $G\_a$ or in $G\_b$.

Consider an arbitrary edge $f$ of $G$. Let $\mathcal C$ be the cycle created when we add $f$ to $T\_2$.

* If $f$ is in $G\_a$ or $G\_b$, then $e$ is not part of $\mathcal C$. So $\mathcal C$ is also the cycle created when we add $f$ to $T$. Since $T$ is an MST of $(G, w\_1)$, $f$ weighs the heaviest in that cycle with respect to $w\_1$ and, hence, with respect to $w\_2$ as well.
* Otherwise, $f$ connects one vertex in $G\_a$ and one vertex in $G\_b$. $\mathcal C$, as a cycle, must include $e\_2$ since $e\_2$ is the only edge in $T\_2$ that connect $G\_a$ and $G\_b$.

In the above illustration, all green edges together with $e$ is the cycle created when $e\_2$ is added to $T$. All blue edges together with $e$ is the cycle created when $f$ is added to $T$. All green and blue edges together is $\mathcal C$.

Since $T$ is a local-MST w.r.t $w\_1$, $e\_2$ weighs the heaviest on the green cycle w.r.t. $w\_1$. Since $w\_2$ and $w\_1$ agrees except on $e$, $$w\_2(e\_2)\ge w\_2(\text{every green edge}).$$

Similarlyly we have
$$w\_2(f)\ge w\_2(\text{every blue edge}).$$

Since $w\_2(f)\ge w\_2(e\_2)$ by the specification of the algorithm, $f$ weighs the heaviest among all green edges and all green edges. That is, $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w\_2$.

There are configurations other than the illustration. For example, $e\_2$ or $f$ might be the same as $e$. The green cycle and the blue cycle might have multiple overlapping segments. In every case, similar argument with the same inequalities shows that $f$ weighs the heaviest in $\mathcal C$ w.r.t. $w\_2$.

So we have shown that $T\_2$ is a local-MST of $(G, w\_2)$. By the above theorem, $T\_2$ is an MST of $(G, w\_2)$.

---
Tags: graphs, graph-traversal, weighted-graphs, minimum-spanning-tree
---


title: Big-Oh of recursive function

text:
# Question
Title: Big-Oh of recursive function
Can someone please explain to me why this function runs in O($n^2$) rather than O($n^3$). I feel like since that for loop runs in O($n^2$) and f() is recursively called around n times, that it should end up being $n\cdot n^2$ for an overall O($n^3$).

```
f(n) {
    if (n == 0) {
        return 0
    }

    int result = 0
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            result += j

        }
    }
    return f(n/2) + result + f(n/2)
}

```

# Answer
The reason is easier to see when you figure the big-$\mathrm O$ of the loop and the recursion (last line) separately and then add them. The loop takes $\mathrm O(n^2)$ time, and the recursive part takes twice the time of $f(n/2)$.

So we get $$\mathrm{time} (f(n))=\mathrm O(n^2 + 2\mathrm{time}(f(n/2)))\tag a$$

and we can simplify this by noticing that this will form a geometric sequence.

$$ = \mathrm O(n^2+2\left(n/2\right)^2 + 4\mathrm{time}(f(n/4)))\tag b$$ $$ = \mathrm O(n^2 + 2(n/2)^2 + 4(n/4)^2 + 8\mathrm{time}(f(n/8)))\tag c$$ $$= \mathrm O\left(\sum\_{i=0}^{\inf} \frac{n^2}{2^{i}}\right)\tag d$$ $$= \mathrm O\left( n^2\sum\_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)\right)\tag e$$

$\sum\_{i=0}^{\inf}\left(\frac{1}{2^{i}}\right)$ on line $\mathrm (e)$ converges to a nonzero value that is not dependant on $n$ (specifically, $2$), so it can be removed from the $\mathrm {O}()$, to give just $\mathrm O(n^2)$

---

Note that this way of solving (leaving constant factors and ignoring the base case of recursion) will not work for all problems.

For example what if the inner loop had time complexity $\mathrm O(n)$? $$\mathrm{time}(f(n)) = \mathrm O(n + 2\mathrm{time}f(n/2)) = \mathrm O(n + 2\frac{n}2+4\mathrm{time}f(n/4)) = ...$$ which would give $\mathrm O\left( n^2\sum\_{i=0}^{\inf}1\right)$, which is obviously not correct because it diverges.
However, if we ingore the constant factor of 2, we get $$\mathrm{time}(f(n)) = \mathrm O(n + \mathrm{time}f(n/2)) = \mathrm O(n + \frac{n}2+\mathrm{time}f(n/4)) = ...$$ which gives $\mathrm O\left( n^2\sum\_{i=0}^{\inf}\frac1{2^n}\right)$, which converges to $2$

-- End note
> 3 votes

# Answer
Let n = 1024 and write down the number of additions in each call. With concrete numbers. See how the numbers develop. Then see if the numbers agree with your hypothesis. Since they don't, fix your hypothesis.
> 0 votes

# Answer
Suppose the time complexity of running $f(n)$ is denoted by $T(n)$. As the computing the `result` takes $\sum\_{i=0}^{n-1}\sum\_{j=0}^{i-1}1 = \sum\_{i=0}^{n-1} i = \frac{(n-1)n}{2} = \Theta(n^2)$, we can write:

$$ T(n) = 2T(\frac{n}{2})+ \Theta(n^2) $$

Now, using the master theorem, as $n^{\log\_2(2)} = n$ and $\log(n) = o (\frac{n^2}{n})= o(n)$, we can say $T(n) = \Theta(n^2)$.
> 0 votes

---
Tags: asymptotics
---


# Question
Title: Understanding depth-limited BFS time complexity
I'm trying to implement graph power calculation using BFS. According to Wikipedia, BFS with depth limit k will suffice (I'm using adjacency list representation, my graphs are sparse, so adjacency matrix power is not optimal).

Complexity of BFS is O(V+E), running it for every vertex is trivially O(V\*(V+E)). I also have depth limit k here and Wikipedia claims (in the page linked above) that running BFS with this constraint for every vertex will be O(V\*E). Why is that? In the worst case when every vertex is in the "range" of k from every other vertex I'll have to search the entire graph V times, after all.

# Answer
There are two cases.

First. $V-1 \leq E$. Then $O(V \cdot (V + E))$ and $O(V \cdot E)$ are equivalent.

Second. $E \< V-1$. Then graph is disconnected and the biggest component has size at most $E + 1$. The whole algorithm will consist of $V$ BFS runs each on the component which has at most $E + 1$ vertices and at most $E$ edges. So each BFS run will take $O(E)$ time and the whole algorithm - $O(VE)$.

Note: this reasoning does not depend on $k$.
> 2 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: classify location of the expiry date on drug label and lot number
Is it possible that using the Machine Learning classification model we can classify/predict the LOCATION/ORIENTATION of the lot number and expiration date on different vials label?

If yes, possible approaches.

Update: So far what I have observed is with EAST model https://arxiv.org/abs/1704.03155

one can locate text in the scene and then use OCR s/w like Textract to read those locations. Now, the real challenge is when you have lots of text available in the image vertical and horizontal and when you don't know where the particular text would appear in the image like expiry date - Is it possible to train a system to give just one or two locations which will be expiry date and lot number?

The challenge here I feel is the location but what features we would take to train as it's just text. I feel it's a classification problem with supervised learning but I may be wrong. Comment?

Thanks

# Answer
It seems plausible that it might be doable, using methods in the research literature on object detection and localization (Yolo, Faster R-CNN, etc.). The only way to tell for sure is to acquire a large dataset of such images and try it out and see how well it works on your data.
> 0 votes

---
Tags: classification
---


# Question
Title: How can divide by 2 blocksize bubblesort followed by a final mergesort be optimized in a particular environment?
I am wondering if we had a large array to sort (let's say 1,048,576 random integers), chosen because it is a perfect power of 2, if we can just keep dividing those blocks into smaller and smaller half size blocks, how would someone know (on a particular computer using a particular language and complier) what the ideal blocksize would be to get the best actual runtime speed using mergesort to put them all back together? For example, what if someone had 1024 sorted blocks of size 1024, but it could that be beaten by some other combination? Is there anyway to predict this or someone has to just code them and try them all and pick the best? Perhaps for simplicity they would want to use some simple bubblesort on the 1024 size blocks, then merge them all together at the end using mergesort. Of course the mergesort portion would only work on 2 sorted blocks at a time, merging them into 1 larger sorted block.

Also, what about the time complexity analysis on something like this? Would all divide and conquer variations of this be of the same time complexity? The 2 extremes would be 2 sorted blocks (of size 524,288) or 1,048,576 "sorted" blocks of size 1, handed over to a merge process at that point.

# Answer
The normal way to tell is through measurement: we try different choices for the threshold, benchmark each one, and choose the best. This can be tricky, as the best threshold might vary from computer to computer (depending on, e.g., the relative speeds of CPU vs RAM, the size of various caches, and so on). So, a plausible approach might be to benchmark on multiple different platforms and then choose one threshold that seems to do ok on most of them.

Asymptotic running time analysis probably won't be very helpful, because the constants matter a lot; and because the cache/memory hierarchy probably matters a lot, and standard running time analysis doesn't model the memory hierarchy very well.
> 1 votes

---
Tags: optimization, sorting, mergesort
---


# Question
Title: "Real World" Applications of an Efficient Root Finder
I don't know this is off-topic (if not, someone can direct me to the proper Stack), but here goes: Let's say there is some algorithm $T$ that can find the integer roots of any arbitrary real-valued continuous univariate function $f(x)$. For any value of $x$, $f$ can be computed efficiently ($O(n^k)$, where $k$ is some small constant). $T$ is similarly efficient. Are there any real life problems that would be benefited by having such an algorithm?

# Answer
> 2 votes
Sure. If this works for any function $f$ that can be computed efficiently, such an algorithm would let you solve any NP problem.

Let $g:\\{0,1\\}^n \to \\{0,1\\}$ be an arbitrary function that is efficiently computable. When $x$ is an integer, define $f(x) = g(x\_1,\dots,x\_n)$ where $x\_1\cdots x\_n$ is the binary representation of $x$; when $x$ is not an integer, define $f(x)$ to linearly interpolate between $f(\lfloor x \rfloor)$ and $f(\lceil x \rceil)$, i.e.,

$$f(x) = f(\lfloor x \rfloor) + (f(\lceil x \rceil) - f(\lfloor x \rfloor))(x - \lfloor x \rfloor).$$

Then if we apply your algorithm to $f$, we find an efficient way to compute $x\_1,\dots,x\_n$ such that $g(x\_1,\dots,x\_n)=0$. This in turn lets you efficiently solve any NP problem.

For instance, you could break the RSA cryptosystem efficiently, you could mint Bitcoin coins efficiently, you could solve optimization and operations research problems efficiently, and so on.

---

If this is restricted to only $f$ that are low degree polynomials, we already know of algorithms to solve the problem, so it likely would not represent an advance over the state of the art and likely wouldn't have much of an impact in practice, unless your method was significantly more efficient than existing methods.

---
Tags: algorithms, applications
---


# Question
Title: Is there any connection between imperative programming and the Von Neumann architecture?
I have ran into a wall with this question in the exercise my teacher gave me, is there any actual connetion between the Von Neumann architecture and imperative programming ?

I have tried googling and finding questions similar to this, but I couldn't find anything, and the one question that I have found actually said that there shouldn't be any connection between the Von Neumann architecture and programming paradigms.

Any help would be appreciated, I'm new to StackExchange, so if I'm breaking any rules please do tell me :)

# Answer
von Neumann architecture is memory for data and instructions and a CPU that fetches and executes instructions one after the other. That is intrinsecally imperative. Compare with functional programming (define functions that call among themselves) or logic programming (search for a solution to a set of logic statements). Other paradigms like OOP are more or less orthogonal to the above.
> 1 votes

---
Tags: programming-paradigms
---


# Question
Title: Add on interval, Query for number of elements less than val
We have an array of numbers and we are supposed to do the following queries on it:

1. Add number `x` to all elements on the subarray with indices `[ L, R ]` of the array.
2. Query for number of elements less than number `x` of the whole array.

Note that `x` is given in each query and is not fixed.

I have a solution with time complexity $O(q \cdot log(n) \cdot \sqrt n)$ where $n$ is the size of the array and $q$ is the number of the queries (Storing sorted subarray in each block). However for constraints $n, q \< 1e5$ with time limit of 2 seconds this is not efficient enough. So how to solve it on these constraints?

The only constraint is that the solution should work for 2 seconds when $n, q \< 1e5$ and you can answer queries offline. Total complexity should fit in the constraints and the complexity for each query is not important.

# Answer
> 0 votes
Decompose the array to blocks of size $T = \sqrt{n \cdot log(n)}$ and Store the sorted corresponding subarray in each block. For each block $k$ store variable $bound\[k\]$ which is the number added to the whole subarray of the block. For the second query iterate over blocks and use binary search over $x - bound\[k\]$ on $k$th block. Time complexity would be $O(\frac n T log(T)) = O(\frac{n \cdot log(n)}{\sqrt{n \cdot log(n)}}) = O(\sqrt{n \cdot log(n)})$.

For updating queries, for each block $k$ that it's subarray is completely in the interval `[ L, R ]` update $bound\[k\]$ to $bound\[k\] + x$. Now we have at most two blocks which are modified but their subarray are not completely in the query interval. Iterate over the modified elements and update them by $x$. Now in each of those blocks you have two sorted arrays (modified and unmodified elements) and you are trying to merge them into one. This can be done in linear time, so rebuilding those two blocks takes $O(T)$. This way time complexity of each update query would be $O(\frac n T + T) = O(\sqrt{n \cdot log(n)})$.

Total complexity: $O((n + q)\sqrt{n\cdot log(n)})$.

---
Tags: data-structures
---


# Question
Title: Perfect matching in a graph and complete matching in bipartite graph
When I google for complete matching, first link points to perfect matching on wolfram.

It defines perfect matching as follows:

> A perfect matching of a graph is a matching (i.e., an independent edge set) in which every vertex of the graph is incident to exactly one edge of the matching. A perfect matching is therefore a matching containing $n/2$ edges (the largest possible), meaning perfect matchings are only possible on graphs with an even number of vertices.

However below graph contains even number of vertices (10 vertices), but still I cant guess the perfect matching - ***in which every vertex of of the graph is incident to exactly one edge***. One of the matching can be $\\{E\_1,E\_4,E\_6\\}$. However not every vertex (here, $\\{V\_5,V\_6,V\_9,V\_{10}\\}$) is incident to exactly one edge in this matching as required by above definition. So this is not definitely a perfect matching as desired by wolfram's definition. Also I cannot add any other edge to this matching as it will make two edges to share a vertex.

**Q1.** Is perfect matching possible with this graph?

I am also reading the same topic from the book by Narsingh Deo. It defines the complete matching in the context of bipartite graph:

> In a bipartite graph having a vertex partition $V\_1$ and $V\_2$ a **complete matching of vertices in set $V\_1$ into those in $V\_2$** is a matching in which there is one edge incident with every vertex in $V\_1$. In other words, every vertex in $V\_1$ is matched against some vertex in $V\_2$.

I am not able to understand if these two (wolfram's and book's) definitions point to two different concepts or they are one and same.

By my understanding, according to Deo's definition, $V\_2$ may contain more vertices than that in $V\_1$, thus the size matching may be less than $n/2$. However, wolfram says perfect matching contains $n/2$ edges. For example in above graph the **complete matching of vertices in set $P\_1$ into those in $P\_2$** can be $\\{E\_1,E\_4,E\_6\\}$ as one edge in this matching is incident with every vertex in $P\_1$.

**Q2.** So the two definitions (wolfram's and book's) must be different concepts. Am I correct?

# Answer
> 7 votes
These are two different concepts. A *perfect matching* is a matching involving all the vertices. A *bipartite perfect matching* (especially in the context of Hall's theorem) is a matching in a bipartite graph which involves completely one of the bipartitions. If the bipartite graph is balanced – both bipartitions have the same number of vertices – then the concepts coincide.

The term *bipartite perfect matching* is not standard – in fact I just made it up. Usually *perfect matching* just means a matching involving all the vertices.

# Answer
> 1 votes
Yuval is right. A perfect matching in a bipartite graph, may be restricted and defined differently as a matching, which covers only one part of the graph. Note that according to such a definition, the number of vertices in the graph may be odd. For example, you can delete say $V\_{10}$ of your example, and your matching is still perfect in the restricted sense.

---
Tags: graphs, matching, bipartite-matching
---


title: How do I convert this PDA to CFG?

text:
# Question
Title: How do I convert this PDA to CFG?
How do I convert this PDA to CFG?

I am currently stuck with this, any help would be appreciated, thank you in advance!

# Answer
> 1 votes
From the PDA diagram we get the transition function as follows:

1. $\delta(q,a,Z\_0)=(q,ZZ\_0)$
2. $\delta(q,a,Z)=(q,ZZ)$
3. $\delta(q,\epsilon,Z)=(r,Z)$
4. $\delta(r,b,Z)=(r,\epsilon)$
5. $\delta(r,\epsilon,Z)=(p,\epsilon)$
6. $\delta(p,\epsilon,Z)=(p,\epsilon)$
7. $\delta(p,\epsilon,Z\_0)=(p,\epsilon)$

Now let $G$ be the context free grammar and V be the set of variables. Now we represent a variable depending on the state $p$ which the PDA was in before having the ultimate effect of popping an element $X$ from the stack and ultimately landing in the state $q$, as $\[pXq\]$ where $p$,$q$ are any arbitrary states in the PDA and $X$ is any arbitrary stack symbol.

So our variables will be of the form $\[\\{p,q,r\\} \times \\{Z,Z\_0\\} \times \\{p,q,r\\}\]$

So corresponding to the transition 1 we have the following productions:

1.$\[qZ\_0q\] \rightarrow a\[qZq\]\[qZ\_0q\]$

2.$\[qZ\_0q\] \rightarrow a\[qZr\]\[rZ\_0q\]$

3.$\[qZ\_0q\] \rightarrow a\[qZp\]\[pZ\_0q\]$

4.$\[qZ\_0p\] \rightarrow a\[qZq\]\[qZ\_0p\]$

5.$\[qZ\_0p\] \rightarrow a\[qZp\]\[pZ\_0p\]$

6.$\[qZ\_0p\] \rightarrow a\[qZr\]\[rZ\_0p\]$

7.$\[qZ\_0r\] \rightarrow a\[qZq\]\[qZ\_0r\]$

8.$\[qZ\_0r\] \rightarrow a\[qZp\]\[pZ\_0r\]$

9.$\[qZ\_0r\] \rightarrow a\[qZr\]\[rZ\_0r\]$

From transition 2 we have:

10.$\[qZq\] \rightarrow a\[qZq\]\[qZq\]$

11.$\[qZq\] \rightarrow a\[qZp\]\[pZq\]$

12.$\[qZq\] \rightarrow a\[qZr\]\[rZq\]$

13.$\[qZp\] \rightarrow a\[qZq\]\[qZp\]$

14.$\[qZp\] \rightarrow a\[qZp\]\[pZp\]$

15.$\[qZp\] \rightarrow a\[qZr\]\[rZp\]$

16.$\[qZr\] \rightarrow a\[qZq\]\[qZr\]$

17.$\[qZr\] \rightarrow a\[qZp\]\[pZr\]$

18.$\[qZr\] \rightarrow a\[qZr\]\[rZr\]$

From transition $3$ we have:

19.$\[qZq\] \rightarrow \[rZq\]$

20.$\[qZp\] \rightarrow \[rZp\]$

21.$\[qZr\] \rightarrow \[rZr\]$

from transition $4$ we have:

22.$\[rZr\] \rightarrow b$

from transition $5$ we have:

23.$\[rZp\] \rightarrow \epsilon$

From transition $6$ we have:

24.$\[pZp\] \rightarrow \epsilon$

From transition $7$ we have:

25.$\[pZ\_0p\] \rightarrow \epsilon$

Now let us rename our variables which occur on the $LHS$ of the productions using simpler names as:

$\[qZ\_0q\] = A$, $\[qZ\_0p\] = B$,$\[qZ\_0r\] = C$,$\[qZq\] = D$,$\[qZp\] = E$,$\[qZr\] = F$, $\[rZr\] = G$,$\[rZp\] = H$,$\[pZp\] = I$,$\[pZ\_0p\] = J$

Now we rewrite the productions with the new variable names substituted but we omit those productions whose body has a variable of the form $\[pXq\]$ which cannot be expanded so, for this reason productions $2,3,6,8,9,11,12,17,19$ are discarded.

So we have:

$A \rightarrow aDA$

$B \rightarrow aDB | aEJ$

$C \rightarrow aDC$

$D \rightarrow aDD$

$E \rightarrow aDE | aEI | aFH | H$

$F \rightarrow aDF | aFG | G$

$G \rightarrow b$

$H \rightarrow \epsilon$

$I \rightarrow \epsilon$

$J \rightarrow \epsilon$

Now let $S$ be the start symbol and we add productions:

$S \rightarrow A | B | C $

So the resulting CFG $G'$ is

$G' = (\\{S,A,B,C,D,E,F,G,H,I,J\\},\\{a,b\\},P,S)$ where $P$ contained the productions described above.

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


# Question
Title: Ambiguous Grammar to Unambiguous Grammar
I'm wondering if somebody can please help me to understand how I go about converting this grammar to an unambiguous grammar. If you can point me in the right direction, I would greatly appreciate it.

S -\> AB | aaB

A -\> a | Aa

B -\> b

# Answer
First, there is a difference between a language and a grammar. A language is just a set of strings, while a grammar is a way to specify such languages. The attribute "ambiguous" applies to grammars. There is no such thing as a "unambiguous language". What you want is an unambiguous grammar for the same language.

In general, it is not possible to give an unambiguous grammar for an arbitrary ambiguous grammar, because there exist (context free) languages for which no unambiguous grammar exists.

In your case, however, an unambiguous grammar does exist. To find it, you have to analyse the grammar. What string are generated by the variable B? What strings are generated by the variable A? So, what strings can be derived from AB and what strings from aaB? From the answer to this last question you will see how the grammar can be simplified without changing the language it generates.
> 4 votes

# Answer
It is quite simple, basically your CFG is ambiguous because of production $S\rightarrow aaB$. We can remove it but CFG must derive this means if we remove and CFG does not generate $aab$ then our approach will be waste so you just remove it and after removing you grammar will be like \begin{align} &S\rightarrow AB\\ &A\rightarrow a \mid Aa\\ &B\rightarrow b\\ \end{align} Now there is no ambiguity, you can check and suggest me if I'm wrong.
> 1 votes

---
Tags: formal-grammars, ambiguity
---


# Question
Title: Is time complexity of the greedy set cover algorithm cubic?
I claim that the greedy algorithm for solving the set cover problem given below has time complexity proportional to $M^2N$, where $M$ denotes the number of sets, and $N$ the overall number of elements.

Question: true or false?

**Approximation Algorithms**, Vazirani, 2001, 1e, p.16, Algorithm 2.2:

> 1. $C \leftarrow \varnothing$
> 2. While $C \neq U$ do Find the set whose cost-effectiveness is smallest, say $S$.
>
> Let $\alpha = \frac{c(S)}{|S - C|}$, i.e., the cost-effectiveness of $S$.
>
> Pick $S$, and for each $e \in S - C$, set $\text{price}(e) = \alpha$.
>
> $C \leftarrow C \cup S.$
>
> 3. Output the picked sets.

In the first iteration, the cost-effectiveness of $M$ sets have to be computed.

In the second iteration, the cost-effectiveness of $M-1$ sets have to be computed.

Since everything between $1$ and $M$ iterations may be needed to find the sets that cover all elements, in the mean it may be $M/2$ iterations.

I.e. in the worst case we need to compute $M + (M-1) + (M-2) + ... + 1 = M(M+1)/2$ times the cost effectiveness.

Determining cost-effectiveness requires the computation of a difference which has time complexity proportional to the number of elements.

Hence, the time complexity is dominated by the term $M^2N$.

---

**EDIT**

If the greedy algorithm outlined above does **not** have time complexity of $M^2N$, where's the flaw in estimating the computation time?

The following diagram shows the computation time per atomic operation versus the test index of 65 tests I ran my code on. The tests range from 6 sets to 1215 sets, and the values on the y-axis are computed as

$$ \text{computation time per atomic operation} = \text{cpu time used} / (M^2N). $$

From what I can tell, the assumed time complexity $M^2N$ seems to model the behavior well. Otherwise, the computation time per atomic operation wouldn't be that stable. Small values for the y-axis are either due to the computation time being too short to be measured, or if the number of elements is substantially smaller than the number of sets ($N \ll M$).

---

**EDIT (Sun APR 19 2020)**

This post cites exercise 35.3-3 taken from **Introduction to Algorithms** (3e) claiming that the (unweighted) set cover problem can be solved in time

$$ \mathcal{O}\left(\sum\_{S \in \mathcal{F}}|S|\right), $$

where $S$ is a set of the problem description, and $\mathcal{F}$ are all the sets in the problem description.

Compared to the naming convention I'm using, this would mean that the problem can be solved in quadratic time $\mathcal{O}(MN)$. But how?

The algorithm still requires to find the set with the maximum number of elements involved, which requires to evaluate every set modulo the recently added one. Hence,

$$ M + (M - 1) + ... + 1 = (M + 1)M / 2, $$

which is quadratic in $M$ again.

Or is there a more efficient way to do so?

---

**EDIT (Mon APR 20 2020)**

My initial estimate of $\mathcal{O}(M^2N)$ does not seem to be that bad. Refering to **Introduction to Algorithms** (3e), page 1119, last paragraph of section **A greedy approximation algorithm**, it is said

> a simple implementation runs in time $\mathcal{O}(|X||\mathcal{F}|\min(|X|, |\mathcal{F}|))$

where $|X|$ is the overall number of elements, and $|\mathcal{F}|$ reflects the overall number of sets.

Dividing the cpu time by this new upper bound, the variance of the time per atomic operation is clearly smaller compared to the upper bound used initially:

# Answer
Acc. to **Introductions to Algorithms** (3e), given a "simple implementation" of the above given greedy set cover algorithm, and assuming the overall number of elements equals the overall number of sets ($|X| = |\mathcal{F}|$), the code runs in time $\mathcal{O}(|X|^3)$. So there are cases when the algorithm behaves cubic.
> 1 votes

---
Tags: time-complexity, set-cover
---


title: Algorithm to calculate Polylogarithm

text:
# Question
Title: Algorithm to calculate Polylogarithm
In my code i want to solve the Fermi-Dirac-Integral numerically. This can be achieved with a Polylogarithm.

Actually I'm coding in `C#`, so my function to calculate this polylogarithm looks like that:

```
public double PolyLog(double s, double z)
{
    double sum = 0;
    for (int k = 0; k < 1e5; k++)
        sum += Math.Pow(z, k) / Math.Pow(k, s);
    return sum;
}

```

This actually does it's job pretty well for values `|z| < 1`. However, I need to calculate the polylogarithm also for values that are bigger than 1.

**Is there any code, that calculates polylogarithms for |z|\>1?**
Probably this would be done by any kind of analytic continuation. Although, I'm using `C#`, I don't care about the language. I can easily translate any code to `C#`.

# Answer
> 4 votes
"Note on fast polylogarithm computation" by R. E. Crandall contains an explicit algorithm for computing the polylogarithm.

---
Tags: numerical-algorithms
---


# Question
Title: Minimum number of ways to write a string
Consider the following question

There are K magical pens (numbered 1 through K). You are given strings P1,P2,…,PK (each of which consists of characters from 'a', 'b', …, 't') ; for each valid i, the i-th pen can only write letters from the string Pi

.

You want to write a word S of length N. All the characters of S are between 'a' and 't' inclusive. This string must be written from left to right. To write it, you pick up some pen and start writing; after you've written some prefix of S, you can put down that pen, pick up another pen, continue writing S from the point where you put down the previous pen, later pick up another pen (any pen) and continue writing S with that pen, and so on until you write the whole string S You may pick up each pen any number of times, including zero. You have to find a way of writing the word S such that the number of times you change the pen (put down the pen you're currently writing with and pick up another) is the smallest possible. If there are multiple solutions, you may find any one. It is guaranteed that it is possible to write S with the given pens.

I know that to represnt a pen as a number using bitset and solve it ,but how can i solve it faster.

Link for the question https://www.codechef.com/ICPCIN19/problems/PENS

# Answer
First observation: As first pen you can always take a pen with which you can write the longest prefix.

Let's consider given pen-strings as bit stings. For each such bit string let's generate all substrings which correspond to subsets of an initial bit string and put them in hashtable. Moreover, let's generate them in descending (by nesting) order and when we generate some bit string which is already in hashtable, we terminate this branch of recursion. So each of $2^{20}$ possible bit strings will be generated at most twice.

Precompute for each prefix of string $S$ the number of times $i$-th letter occurs in it.

Then let's walk by string $S$ from left right and on each step let's check whether current prefix can be written with a single pen. We can do it in $O(1)$ using precomputed hashtable and prefixes.

So the overall complexity is $O(2^\alpha + K + N\cdot\alpha)$, where $\alpha$ is an alphabet size ($20$ in our case).
> 1 votes

# Answer
There's a simple $O(nk)$ greedy algorithm that assumes there is a solution:

1. Start with all pens in an array.
2. Eliminate all pens from your array that can not be used to write the next character. If this would remove all pens, instead output one of them and go back to 1.
3. Write the next character and go back to 2 if there are more characters to write.
4. Output one of the pens in your array and done.

If there are instances without a solution you need to detect, just check in step 2 whether you are removing all pens from a freshly created array.
> 0 votes

# Answer
"Making it faster" by tweaking data representation won't buy much. It could speed it up by, say, a factor of 2 if you are lucky (or the original is very badly written). To get *real* speedup you need to use another approach (change basic algorithm).

I suspect the obvious greedy algorithm succeeds: Take as the next pen those that allows you to write the longest prefix of what remains. There must always be one (as each symbol can be written by some pen), and no pen selection can block a later one (if you can write $\alpha \beta$, you certainly can write $\beta$ with that same pen).
> 0 votes

---
Tags: algorithms, dynamic-programming, bit-manipulation
---


# Question
Title: Number of nodes of given height in binary heap
> Show that there are at most $\lceil n/2^{h+1}\rceil$ nodes of height $h$ in any $n$-element binary heap.

How can I show this? Or, how can I prove this?

# Answer
> 1 votes
Suppose towards a contradiction that your heap $H$ contains at least $\lceil n/2^{h+1} \rceil + 1$ nodes of height $h$, for some choice of $h$.

At least $\lceil n/2^{h+1} \rceil$ of these nodes are the roots of a complete binary subtree of the heap. Therefore each of these subtrees contains $\sum\_{i=0}^h 2^i = 2^{h+1}-1$ nodes.

The subtree of $H$ rooted in any of the remaining nodes of height $h$, contains at least $1$ vertex (stronger lower bounds are possible, but this is all we need).

Since the subset of nodes having height at least $h$ in $H$ induces a binary tree $T$ whose leaves are the nodes of height exactly $h$ in $H$, we know that $T'$ must have at least $\lceil n/2^{h+1} \rceil + 1 - 1$ internal nodes. This means that the number of nodes of height larger than $h$ in $H$ is at least $\lceil n/2^{h+1} \rceil$.

Then, the total number $n$ of nodes in $T$ must be at least:

$$ \begin{align\*} n \ge \lceil n/2^{h+1} \rceil \cdot (2^{h+1}-1) + \lceil n/2^{h+1} \rceil + 1 = \lceil n/2^{h+1} \rceil \cdot 2^{h+1} + 1 \ge n + 1. \end{align\*} $$

This is a contradiction.

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


# Question
Title: What complexity class is this set of grammars? In between NL and P?
Given a grammar where (every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$), (($X \to YZ$) implies ($X \to ZY$)) and (($XY \to Z$) implies ($YX \to Z$)) where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

What complexity class does this correspond to?

It appears to be the problem of finding an "all-in-path" in a "3-digraph" (See: Is there a name for this directed graph and path concept? 3-digraph and all-in-path?).

**Related questions:**

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars?

What complexity class is this set of grammars? RE?

# Answer
> 0 votes
This appears "almost P-complete".

I think this is existential and P-complete is universal.

This problem corresponds to, "given (1) a SAT problem, (2) a candidate solution, and (3) a variable A, does (A imply (not A))?" This problem shows the existence of a contradiction (for a single variable).

P-complete corresponds to "given (1) a SAT problem, and (2) a candidate solution, does there exist a variable X such that (X implies (not X))?" By showing there exists a solution, you show the non-existence of a contradiction (for all variables).

Sometimes it's easier to find a contradiction than a solution. Consider a Horn-SAT problem containing the clauses `A` and `(not A)`. You don't need to check the other clauses.

This assumes the original question is equivalent to finding an "all-in-path" in a "3-digraph" (See: Is there a name for this directed graph and path concept? 3-digraph and all-in-path?

Given a 3-SAT instance `S`, candidate solution `Candidate` and a target variable, `X`, does `X` imply not `X`?

We will construct a 3-digraph:

For each literal `A` and its negation `nA`, in `S`, create a vertex.

Rewrite each or-clause in `S`:

`(A or B or C)`

`((A or B) or C)`

`(not(not((A or B))) or C)`

`(not(not(A) and not(B))) or C)`

`(not(A) and not(B)) implies C)`

Since there are 6 permutations of `A`,`B`,`C`, there are 6 rewrites. For each rewrite, add 2 directed edges: `nA->C` and `nB->C`.

Create a new vertex, `Candidate`. For each literal `A` in `Candidate`, add a directed edge `Candidate->A`.

Create a new vertex, `XContradiction`. Add directed edges `X->Xcontradiction` `nX->Xcontradiction`.

(After adding edges, ensure this is a trigraph.)

Is there an all-in-path from `S` to `Xcontradiction`?

If we show the non-existence of an all-in-path for each literal (and not just `X`), then we have decided the corresponding P problem (does `Candidate` satisfy).

---
Tags: complexity-theory, formal-grammars
---


# Question
Title: Least number of comparisons needed to sort (order) 5 elements
Find the least number of comparisons needed to sort (order) five elements and devise an algorithm that sorts these elements using this number of comparisons.

> *Solution:* There are 5! = 120 possible outcomes. Therefore a binary tree for the sorting procedure will have at least 7 levels. Indeed, $2^h$ ≥ 120 implies $h $ ≥ 7. But 7 comparisons is not enough. The least number of comparisons needed to sort (order) five elements is 8.

Here is my actual question: I did find an algorithm that does it in 8 comparison but how can I prove that it *can't* be done in 7 comparisons?

# Answer
> 32 votes
The solution is wrong. Demuth \[1; via 2, sec. 5.3.1\] shows that five values can be sorted using only seven comparisons, i.e. that the "information theoretic" lower bound is tight in this instance.

The answer is a method tailored to $n=5$, not a general algorithm. It's also not very nice. This is the outline:

1. Sort the first two pairs.
2. Order the pairs w.r.t. their respective larger element.

Call the result $\[a,b,c,d,e\]$; we know $a\<b\<d$ and $c\<d$.
3. Insert $e$ into $\[a,b,d\]$.
4. Insert $c$ into the result of step 3.

The first step clearly takes two comparisons, the second only one. The last two steps take two comparisons each; we insert into a three-element list in both cases (for step 4., note that we know from $c\<d$ that $c$ is smaller than the last element of the list at hand) and compare with the middle element first. That makes a total of seven comparisons.

Since I don't see how to write "nice" pseudocode of this, see here for a tested (and hopefully readable) implementation.

---

1. Ph.D. thesis (Stanford University) by H.B. Demuth (1956)

See also Electronic Data Sorting by H.B. Demuth (1985)
2. Sorting and Searching by Donald E. Knuth; *The Art of Computer Programming* Vol. 3 (2nd ed, 1998)

# Answer
> 1 votes
The theoretical lower bound on comparison based sorting is $\log(n!)$. That is to say that to sort $n$ items using only $\<$ or $\>$ comparisons it takes *at least* the base 2 logarithm of $n!$, hence $\log(5!) \approx 6.91$ operations.

Since $5!= 120$ and $2^7= 128$, using a binary decision tree you can sort 5 items in 7 comparisons. The tree figures out exactly which of the 120 permutations you have, then does the swaps needed to sort it.

It's not pretty or short code, and you should probably use code generation methods to create the decision tree and swaps rather than coding it by hand, but it works; and provably works for any possible permutation of 5 items, thus proving you can sort 5 items in no more than 7 comparisons.

# Answer
> -1 votes
Some problems are that the question is (1)incompletely stated, and (2)includes unwarranted presumptions:

> how can I prove that it can't be done in 7 comparisons?

On the first point, it is unclear what the domain of the sorting problem is: is it random real numbers (with some specified or unspecified distribution), or integers (in some specified or unspecified range), or some other type of objects; are the values guaranteed to be distinct, or could there be duplicates (triplicates, etc.), and so on? If there are duplicates, etc., does it matter whether the partial ordering of items which compare equal is maintained (a.k.a. stable sorting)? None of these things are specified, and they all affect possible (and/or inapplicable) potential solutions to the sorting problem which is behind the stated question. It's also unclear whether the question is about best-case, average-case, or worst-case comparisons (under some specified conditions for some problem domain). And it's unclear whether anything other than comparisons (e.g. amount of data movement, partial-order stability as mentioned above, etc.) is a consideration.

On the second point, one of the responses notes Demuth's 7 comparison solution to non-stable sorting, so the question as stated is an impossible quest; one cannot in fact (correctly) prove the impossibility of something which is in fact possible.

So the short answer to the question as stated is "you can't" (in part because there **is** a 7 comparison solution to sorting 5 elements with certain constraints (and lacking others), and partly because the question and background do not specify any relevant constraints, details of the problem domain, etc.).

# Answer
> -2 votes
i was thinking quicksort. you select as pivot the element that just happens to be the middle element. compare the pivot to the remaining 4 items resulting in two piles to be sorted. each of those piles can be sorted in 1 comparison. unless i have made a terrible mistake, the 5 items were fully sorted in just 6 comparisons and i think that is the absolute fewest number of comparisons needed to do the job. the original question was find the least number of comparisons to sort 5 elements.

# Answer
> -3 votes
If you can test algorithm, test it on all number combinations. If you have lot of number, test on lot of random combinations. Not precise, but faster than all combinations.
Minimal
a \< b \< c = 2
a \< b \< c \< d = 3
a \< b \< c \< d \< e = 4

Maximal
3^3
4^4
5^5
Insert to middle use 3-6 for 4 numbers.
Merging use 4-5 for 4 numbers.
Minimal compare by wiki is 5 for 4 numbers :) For 5 is 7. You use 8, still so much.
https://en.wikipedia.org/wiki/Comparison\_sort#Number\_of\_comparisons\_required\_to\_sort\_a\_list
If you know all before comparations, you can go down with comparations. My average for 4 numbers is 3.96 / 1024 all combinations.

---
Tags: algorithms, sorting, lower-bounds
---


# Question
Title: What complexity class is this set of grammars?
Given a grammar where every rule has the form $X \to YZ$, $XY \to Z$ or $X \to a$ where $X,Y,Z$ range over nonterminals and $a$ ranges over terminals, and given a nonterminal $S$ and a terminal $a$, determine whether $S$ can derive $a$.

What complexity class does this correspond to?

**Related questions:**

What complexity class does is this set of grammars? L-complete?

What complexity class does is this set of grammars? NL-complete?

What complexity class is this set of grammars? In between NL and P?

What complexity class is this set of grammars? RE?

# Answer
> 1 votes
Every unrestricted grammar can be converted to one with the following types of rules: $$ AB \to CD \\ A \to BC \\ A \to a \\ A \to \epsilon $$ Wikipedia calls this Kuroda normal form for unrestricted grammars.

You can convert a rule of the form $AB \to CD$ to a pair of rules $AB \to X\_{ABCD}$, $X\_{ABCD} \to CD$. Following the OP's suggestion, we can convert $A \to \epsilon$ to the rule $A \to E$, and add rules $BE \to B$ and $EB \to B$ for any nonterminal $B$. This allows us to obtain a grammar in your form equivalent to the original one, up to not being able to generate $\epsilon$.

---
Tags: formal-grammars, complexity-classes
---


title: A query about Complexity Class $NC$

text:
# Question
Title: A query about Complexity Class $NC$
Given a polynomial circuit consisting of only $AND$ and $OR$ gates. Is it true that any such circuit is easily parallelizable i.e. it belongs to the complexity class $NC$?

I think this is the case but I can't find a source confirming it.

# Answer
> 2 votes
The complexity class $\mathsf{NC}$ is a *uniform* class. There are *constant size* circuits which don't belong to $\mathsf{NC}$.

What does that mean? Most circuit complexity classes don't really make sense for *individual* circuits. A single circuit can't have polynomial size, or rather, this doesn't mean anything (every circuit has size at most $n^k$ for some $k$). Instead, when talking about a circuit belong to a complexity class, we are really talking about *sequences* of circuits. These sequences can be uniform – that is, can be generated by a Turing machine – or arbitrary. (In the uniform case, you can get different complexity classes by constraining the strength of the Turing machine.)

The complexity class $\mathsf{NC}$ consists of uniform circuits of polynomial size and polylogarithmic depth. Consider the following sequence of circuits: $C\_n$ (with $n$ inputs) is either the constant 0 or the constant 1, depending on whether the $n$th Turing machine halts on the empty input. This sequence doesn't belong to $\mathsf{NC}$ (since it's not even computable), but all circuits have constant size.

In order to compare $\mathsf{NC}$ and polynomial size circuits, you have two options. Either you compare $\mathsf{NC}$ to $\mathsf{P}$, which is the uniform analog of polynomial size circuits, or you compare non-uniform $\mathsf{NC}$ to polynomial size circuits (a complexity class known as $\mathsf{P/poly}$). In both cases, it is conjectured that the two classes are different, but this hasn't been proved yet.

One way of separating $\mathsf{NC}$ from $\mathsf{P}$ would be to separate non-uniform $\mathsf{NC}$ from $\mathsf{P}$, that is, to give an example of a problem in $\mathsf{P}$ (say, some $\mathsf{P}$-complete problem) that cannot be solved using $\mathsf{NC}$-circuits. In the same way, you could prove that $\mathsf{P} \neq \mathsf{NP}$ by showing that $\mathsf{SAT}$ doesn't have polynomial size circuits. In both cases, you are actually trying to prove stronger claims, which are believed to hold.

---
Tags: complexity-theory
---


# Question
Title: Examples for derandomization via small sample spaces
People in theoretical computer science stack exchange advises me to ask this question here. I ask the same problem in https://cstheory.stackexchange.com/questions/46668/examples-for-derandomization-via-small-sample-spaces and if you are interested in answers there, you can go to see it.

I read the book the Probabilistic Method and the lecture note Pseudorandomness to study techniques of derandomization and completed some of exercises.

I'm trying the technique of "Derandomization" for some algorithms, and I find some samples using the derandomization via small sample spaces and feel very interested.

To deepen the impression on derandomization via small sample space, I want to see more papers using that.

# Answer
> 1 votes
There is a survey by Luby and Wigderson: Pairwise independence and derandomization.

---
Tags: reference-request
---


# Question
Title: When should we construct trees, graphs to analyse an algorithm?
In many algorithms, it's easy to understand how the algorithm is executed, but as for why it works well and how it can work, it's not very easy to see, sometimes, authors construct trees or graphs to put things analysed in them and use those structures to describe the property of the research object and prove some property of the structures to finally give an explanation why it works well...

When should we use trees, graphs to analyse an algorithm? Or equivalently, what property do trees or graphs do well in describing in theory?

Like, in sort algorithms, many algorithms are analysed with a binary tree, in 2SAT algorithms, the core of the problem is decribed as a graph.

Well, for the problems with fixed mode, the structures can be implied easily, like the problems in OI or leetcode, however, in research such situation is not so likely to happen.

If the best probably answer is: well, when you feel some structures are proper, you can try them, it is hard to say which must be used and which shouldn't. I accept it. I look forward to a more inspiring answer.

# Answer
The answer could be like a promo for data structures course!

You probably studied data structures within the study of a programming language, not in an abstract manner.

You should know the main characteristics of a data structure and that of ur problem to choose the most suitable one for it(by suitable we usually mean efficient in time&space complexity of main operations, and hopefully meaningful too I mean easy to understand the representation)

For example u use BST if u want fast search/insert (O(log n)), then u may prefer AVL trees if worry about worst case and want to keep the tree balanced; prefer Hu-Tucker OAT if u think the difference of frequency between ur search items is considerable that it has an impact on the performance. Huffman trees for coding, hash tables if ur items r scattered in the range and u want fast search/insertion (const in av),.... B-trees, B+-trees,... The same goes for choosing bet arrays, linked lists, stacks,....

You may have a look at knuth The art of Computer Programming, Vol 3 Searching & Sorting

Then u may move on more practical problems and consider the nature & relations between ur elements. Choose trees if they have a Hierarchical nature, graph if the connection varies, and vertices or edges may have values to represent cost or profit; sometimes u might rethink about ur choice which data to put vertices and which as edges, in this case u think of the problem u r solving and the performance of the well known algorithms u r going to map it to in each case to make ur choice.

I hope this was helpful
> 2 votes

# Answer
There's no hard-and-fast rule. Use them if they are useful; don't if they are not. As a broad guideline:

Graphs are often useful when you have relationships between a pair of items.

Trees are often useful when you have a hierarchical relationship.
> 3 votes

---
Tags: algorithms, trees, binary-trees
---


# Question
Title: Can any problem in P be converted to any other problem in P in polynomial time?
Is it possible to convert **any** problem in P to any other problem in **P** in **polynomial time**?

# Answer
> 14 votes
If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to **any non-trivial** problem $B$ in $P$.

Here "non trivial" means that $B$ has at least one yes instance $I\_Y$ and at least one no instance $I\_N$ (i.e., the language associated to $B$ is not $\emptyset$ nor $\Sigma^\*$).

To map an instance $I\_A$ of $A$ to an instance $I\_B$ of $B$ simply solve $A$ using a polynomial-time algorithm. If $I\_A$ is a yes instance let $I\_B = I\_Y$, otherwise let $I\_B = I\_N$.

It is not possible to reduce any problem $A \in P$ to any problem $B \in P$. To see this let $A$ be a non-trivial problem and let $B$ be a trivial problem. Two possible languages corresponding to $A$ and $B$ are $\\{ \varepsilon \\}$ and $\emptyset$, respectively.

---
Tags: time-complexity, complexity-classes
---


# Question
Title: Difference between *device descriptor* and *device handler*
I am studying Computer Architecture, and am a bit confused about the difference between device descriptors and device handlers in operating systems. Am I correct in saying that a device handler is actually a device driver?

What confuse me is that while the terms *device handler* and *device handler* appear in the course slides, I couldn't find then in the course textbook. The closest term I could find there is *device driver*.

# Answer
Where did you find that terminology? Check how it is defined there.

If it was up to me, a "device descriptor" would be a way to describe a device, perhaps a data structure giving details on it (or some sort of reference to it, like a pointer or an index into an array of the above).

As you state, in my book a "device handler" would be some sort of routine (or a set of routines) to manage it, a driver.
> 3 votes

---
Tags: operating-systems
---


# Question
Title: What needs led to the implementation of ASCII codes?
Prior to ASCII existing, we already had at least four number systems, namely

```
Binary
Decimal
Octal
Hexadecimal

```

So what were the needs that lead to the implementation of ASCII codes? Why was this code chosen, from a computer architecture perspective? I have searched online, but I haven't found a satisfactory answer.

# Answer
Those r "number" systems they represent just numerical values. ASCII is a standard "coding" that include characters

(encode them as digital binary number, for example "A" is represented as 65)

Think of it as a fn that maps each number/character/symbol(enter for ex. has a code that I don't remember now) to a code number that will be represented to the computer in binary format
> 1 votes

# Answer
There were several different coding systems for *characters* around. The best known (alive up to this day) was IBM's EBCDIC, but most any manufacturer had their own. We had a DEC 2020, which handled several different character coding systems with it's 36-bit (!) words, a 6-bit DEC own, at least one 7-bit one (I think it was ASCII, with no parity bit) and 8-bit ones. If I remember right, it handled EBCDIC too, for IBM compatibility. All in the interest of scrimping a few bits per character (memory was *precious* in the '70es!).

Defining a character code of some sort was clearly a requirement if you wanted to read/write anything that wasn't just numbers, and that means agreeing on some mapping of (a subset of) the characters in use to numbers (the natural language inside the computer). You can get away with e.g. 6 bits (64 possible characters) if you restrict yourself a lot, ASCII's 7 bits (128 possibilities) is *very* cramped (specially if you want to write some non-English text, or even such English words as rôle, naïve, fiancé or others borrowed from other languages).

Even the prehistoric Morse code is a coding system for characters, just not in numbers. See also character encoding for it's history.
> 0 votes

---
Tags: computer-architecture, number-formats, binary
---


# Question
Title: Consequences of a language that hides his lower level rappresentations
*I know it's a silly scenario but I wolud like to know if it's relevant and maybe there are some sort of theory/studies on it or it's merely a non-sense situation.*

Immagine a language much close to a Turing machine that is compiled in an higher language (let's say C). This language can accept an integer as input, but using his syntax i don't have any access to his internal rappresentation of this integer, that is the integer wolud be located in one single cell and the only operation I can do on a cell are:

```
 +1, -1, copy/paste from a register, set to 0, chek if it's non-zero.

```

Now if I want to output the sign of the integer I would create a copy of it so that in one cell the value gets incremented and in the other gets decremented. Until I reach 0 and then I would stop and correctly tell the sign.

The interesting part is that under the hood, this program would surely use the information of the sign of the integer to execute +1 and -1 correctlty...

So I'm using operations that would use information x to obtain information x... Normally I would have access to the rappresentation of the integers and to check the sign consists in looking at one particular bit. But in this case some information is hidden from me.

It reminds me of solving the limit sin(x)/x as x goes to 0 by de l'Hopital rule... It's a logical fallacy because that limit is required in order to differentiate sin(x)

Could there be situations when this is not generated explicitly by us and it's inevitable? Has it more profound consequences?

# Answer
> 2 votes
There's plenty of precedent for this in real programming languages. One obvious example is pointers/references, which are internally just an address (probably). The language/runtime must know this, but in managed languages you don't have access to that.

One of my favourite examples of "useful information that must be there but is hidden" is in C++. You can allocate an array of objects using the `new[]` operator and deallocate them with `delete[]`:

```
Object* objs = new Object[25];
// do stuff to objs
delete[] objs;

```

C++ does not provide a way to obtain the number of elements in array. However, the `delete[]` operator *must* have access to this information, because it needs to execute the destructors of those elements.

---
Tags: logical-validity
---


# Question
Title: Reframing decision, counting, enumeration, and search as optimization
The top accepted answers to the questions below allude to two complexity classes of **optimization** problems: **NPO** and **PO** (in relation to NP and P for **decision** problems):

The way these questions and answers are written, I get the impression that many problems such as **counting**, **enumeration**, or **searching** problems could be framed as general **optimization problems** even if their formulation does **not** have an explicit **objective function** (i.e. mathematical programming problems). Is that correct?

Take decision problems for example, one often casts decisions in machine learning (ML) as those that ***minimize regret***, or e.g. an expected error in the evaluation against a loss function (e.g. 0/1 for decision problems).

These types of decisions or **search as-optimization** formulations for a wide variety of problems are fairly ubiquitous in ML.

Take some other common examples:

* Find the $n$th Fibonacci term
* Find the GCD of a set of numbers
* Enumerate the subsets for which 3SUM answers "Yes"
* Count all hamiltonian cycles in a graph
* etc.

Couldn't one *easily* reframe many of them as optimization problems using a loss function as well? e.g. $\text{argmin}\_x f(x)$, where $f$ is a measure of error defined on the solution space of the desired problem? Or is that reduction, despite its prevalence in e.g. ML, not always "easy", feasible or useful?

More generally, how does the ***family*** of complexity classes (and their associated types of reductions and definitions) for **search**, **enumeration** and **counting** relate to the family of their "reduction-equivalent" **optimization** problems?

# Answer
Search problems are in NP if you can verify a solution in polynomial time.

Counting problems are ♯P if you're counting the number of solutions to an NP search problem.

Enumeration problems are not particularly special.

See https://en.wikipedia.org/wiki/Computational\_problem.
> 1 votes

---
Tags: complexity-theory, optimization
---


# Question
Title: What's the most time efficient way to find the number of nodes reachable from each root and no other root?
Suppose there are `n` nodes.
These nodes are connected by `m` unique directed edges. Sets of these edges may form cycles.
Each node has an associated quantity.
`r` of these nodes are selected as root nodes.

A node `a` can be said to reach node `b` if

* `a` is `b` or
* there exists a directed path from `a` to `b`.

The goal: For each root node, find the sum of the quantities of all nodes which **it can reach** and **no other root can reach**.

This includes the root itself. For example, if root 2 can reach root 1, then root 1's associated quantity will be counted to neither root 1 nor root 2's sum. On the other hand, if no root other than root 1 can reach root 1, then root 1's associated quantity will be counted toward root 1's sum.

I'm trying to puzzle out how to do this with the minimum number of calculations, but I think I need to brush up on my graph theory. This problem is quite a lot easier on a tree, but I've found dealing with cycles makes things much more complicated. I'm having a tough time finding a solution which doesn't incessantly re-traverse the graph.

# Answer
> 0 votes
This can be solved in linear time:

Initially, treat all vertices as unmarked.

In phase 1, do a DFS from the first root $r\_1$, and mark all reachable vertices as reachable from $r\_1$.

Next, in phase 2, do a DFS from the second root $r\_2$. Mark all reachable vertices as reachable from $r\_2$, except that if you ever encounter a vertex that was previously marked as reachable by $r\_1$, delete that vertex and all vertices reachable from it and don't continue the DFS from that vertex.

Repeat, with one phase per root. At each stage, if you ever encounter a vertex that was previously marked as reachable from some other root, then you delete that vertex from the graph and all vertices reachable from it and don't continue the traversal from there.

At the end, do a linear scan over all vertices that have not yet been deleted. Each vertex will either be unmarked or will be marked as reachable from a single root. You can easily count the number that are reachable from each root (and no other) during this linear scan.

Correctness: any vertex that is reachable from two or more vertices are deleted. So, we only consider vertices that are reachable from one root and not any other.

Running time: each vertex is visited during at most two phases: once when it is initially marked as reachable, and possibly a second phase where it is reachable from some other root (but there won't be a third or later phase, because if it is visited in two different phases, it will be deleted). Thus, the total running time for all the phases is at most twice the cost of a DFS, i.e., $O(|V|+|E|)$. The running time for the final scan is $O(|V|)$. Consequently, the total running time is $O(|V|+|E|)$.

# Answer
> 0 votes
A rough sketch, you can fill in the details:

Using Strongly Connected Components (SCCs), you can reduce the graph to a DAG. If you run topological sort on this DAG, all incoming edges to a node will be processed before any outgoing edges. Then just store at each node which root has reached it, or if none/more than one roots have reached it.

---
Tags: algorithms, graphs, efficiency
---


# Question
Title: How does the length of the output of a problem inform its complexity?
Consider the **decision** problem: Subset sum. For an input set of integers, it asks for a **Yes/No answer** to the question of whether or not we can find a subset of elements of this input that add up to 0. The output for this problem is $O(1)$ and simple (e.g. 1/0). This problem is **NP-Complete**, which as far as I understand is only defined for **decision problems**.

Now consider a problem associated with Subset sum that asks to **output** all **such subsets** that add up to 0. As far as I understand, this is an **optimization problem**.

Moreover, the **output** of this problem **could grow** as $O(2^N)$ if $N$ is the size of the input array (i.e. the output grows as fast as the cardinality of the power set of the input). If so, what does this say about the **complexity** or **complexity class** of this optimization problem?

More generally speaking, does the size of the output of an optimization problem provide a necessary lower bound on the complexity of the optimization or associated decision problems?

# Answer
No, it's not an optimization problem. It takes at least one step of computation per bit or word of output (depending on the model of computation), so since the output can be $\Omega(2^N)$, that means the worst-case running time will be $\Omega(2^N)$, no matter what algorithm you use. Thus, the complexity is $\Omega(2^N)$.

Yes, the size of the output is a lower bound on the running time to produce that output.
> 4 votes

---
Tags: algorithms, complexity-theory, optimization, decision-problem
---


# Question
Title: What practical/efficient algorithms exist for minimum weighted set cover problem (MIN-WSCP)?
For TSP there are well known heuristic and approximation solutions which run in low-polynomial time, like Christofides / 2-OPT and so on.

I need a practical, fast algorithm, ideally sub-quadratic complexity, to solve the minimum weighted set cover problem (which is NP hard). It solves subproblems in a genetic algorithm so needs to be fast rather than optimal. Are there any standard algorithms used to solve this?

# Answer
One possibility is to use the standard greedy algorithm. It can be adapted to weighted set cover by counting the total weight of previously uncovered elements that will be covered by adding a particular set, instead of counting the number of such elements. This is standard and covered in standard textbooks and resources. Another option is to use linear programming or integer linear programming. A little research on set cover approximation algorithms will find much more that is written on the subject. In the future, I suggest doing more research before asking here.
> 1 votes

---
Tags: optimization, set-cover
---


# Question
Title: Using Subset Sum algorithm $O(n)$ times to find the subset
Subset Sum is a well-known dynamic programming problem, which states that given a succession of numbers and a number, the algorithm determines if exists a subset that its sum is equal to the given number. I was asked to use this algorithm (however it is implemented) at most $O(n)$ times to build a subset which satisfies the sum. My solution is given below:

```
    findSubset(A[1,...,n], sum){
      if(blackBox(A,sum)){
        for i = 1 to n do
          if(blackBox(A - A[i], sum))
               return findSubset(A - A[i],sum);
          endif
      return A;
      }else
        return [];
      endif
    }

```

The problem with this solution is that it uses the subSetSum algorithm $O(n^2)$ times. As a hint to optimize the problem to $O(n)$ is that I should not use the loop and appeal only to recursion. Can anyone give a hint for an optimal solution to this problem?

# Answer
> 2 votes
Suppose that $\mathit{sum}$ is the sum of some subset of $A\[2\],\ldots,A\[n\]$. Then you can just remove $A\[1\]$.

Conversely, if $\mathit{sum}$ is not the some of any subset of $A\[2\],\ldots,A\[n\]$, then any subset summing to $\mathit{sum}$ must contain $A\[1\]$. Therefore it consists of $A\[1\]$ together with a subset of $A\[2\],\ldots,A\[n\]$ summing to $\mathit{sum}-A\[1\]$.

Either way, we have eliminated $A\[1\]$. We can then go on and eliminate $A\[2\],\ldots,A\[n\]$ in sequence.

---
Tags: algorithms, time-complexity, dynamic-programming, recursion
---


# Question
Title: What is a polynomial-time algorithm for determining whether two trees, with colored nodes, are isomorphic or not
Provide ***any*** polynomial-time algorithm (even a large degree polynomial) which determines whether two rooted colored trees are isomorphic to each-other or not.

For example, consider the following two trees:

Example trees `T` and `U` ***are*** isomorphic.
An isomorphism (bijection) is described in the table below:

```
  T          U
  1          2
  2          4
  3          1
  4          5
  5          3
  "white"    "green"
  "blue"     "white"

```

Below are some things to know about the problem:

* Nodes are colored
* edges are not colored.
* Nodes are free to be any color. Adjacent nodes are allowed to be the same color.
* which node is the root node of each tree cannot be changed.
* children are un-ordered.
* the tree is not necessarily a binary tree. a node could have 3 children, 4 children, 5, etc...

Formally, a ***colored tree*** is a tuple `(VS, ES, root, color_set, color_map)` such that:

* `VS` is the vertex set
* `ES` is the edge set
* `(VS, ES)` is a undirected tree
* `root` is a element of `VS`
* `color_set` is a set of objects called "colors"
* `color_map` is a mapping from `VS` to `color_set`
* every element of `color_set` appears in the range of `color_map` at least once. That is, every color is applied to at least one node.

colored trees `T` and `U` are ***isomorphic*** if and only if there exists a bijection, `PHI` from the vertex set of `T`, `VT`, to the vertex set of `U`, `VU` such that:

* the root of one tree is matched to the root of the other tree
* `for all nodes v, w in VT, {v, w} is an edge in tree T if and only if {PHI(v), PHI(w)} is an edge in tree U`
* `for all nodes v, w in VT, v and w are the same color in tree T if and only if PHI(v), PHI(w) are the same color in tree U`

# Answer
Why should we even expect that there is such a polynomial-time algorithm? The comment

> Do you know how to solve this without the colors? That would be a good start. – Yuval Filmus Jun 15 '19 at 14:24

has an upvote, but it only hints implicitly that there is a (simple?) solution. Let me try to guess the (simple?) solution that is expected here. The AHU algorithm by Aho, Hopcroft and Ullman produces a canonical labeling of trees. Let's interpret the AHU algorithm as an efficient implementation of color refinement for rooted trees, and ask whether color refinement for "labeled trees" (isomorphism of "colored trees" would not allow to swap colors) would always be able to decide isomorphism. The answer is "no", because isomorphism of labeled trees is GI complete:

> From a graph G, construct a rooted labeled tree T by putting a node below the root of the tree for every vertex of G. For every edge of G, put two nodes with the same label on the next lower level. An edge has two endpoints, connect the corresponding vertices (or rather the tree nodes corresponding to them) each with one of the tree nodes corresponding to the edge.

The link above also makes it clear that this is well known by citing

> > **Theorem:** Marked tree isomorphism is isomorphism complete
>
> from section 6.4 Marked Graphs and Marked Trees in Booth, Kellogg S.; Colbourn, C. J. (1977), Problems polynomially equivalent to graph isomorphism, Technical Report CS-77-04, Computer Science Department, University of Waterloo. They used the definition that “A marked graph is a graph together with a partition of its vertices. An isomorphism of marked graphs is an isomorphism of the underlying graphs which preserves the partitioning.”
> 1 votes

# Answer
Let f be a function from the color set of the first tree to the color set of the second tree. The function f is initially defined only partially, for e.g. that f(color(root of first tree)) = color(root of second tree).

At each node of the tree, isomorphism is checked by trying both ways of mapping its children and checking whether the sub tree rooted at the left child of first tree is isomorphic to the left or the right subtree of the node in the second tree. This can be checked by recursive function calls, which can pass the current root node of the two trees and existing f as arguments in the recursive function calls.

It appears that this algorithm perhaps even runs in linear time. As the recursion gets deeper, f would be more fully defined and number of recursive function calls might reduce. The function modifying f must keep it consistent with the previous f which it received as parameter.
> 0 votes

---
Tags: graphs, trees, colorings, graph-isomorphism
---


# Question
Title: Alternative algorithms for calculating x^2?
I'm emulating 128-bit arithmetic. At the moment I'm calculating $x^2$ by computing $x\cdot x$. What might be some alternative methods that aren't simply dressing up multiplication?

# Answer
> 4 votes
Base on the fact that:

If n is an even number $(n = 2m) \implies n^2 = 4m^2$

If n is an odd number $(n = 2m + 1) \implies n^2 = 4m^2 + 4m + 1$

And you can calculate $m$ by bitwise shifting right of $n$, calculate $4m$ (or $4m^2$) by bitwise shifting left.

So you can apply the recursion method to this process to establish the result with $O(\log n)$ time complexity.

# Answer
> 0 votes
You can use $x^2 = \exp(2\log x)$.

However, this is probably inferior to using $x^2 = x \cdot x$ in almost all situations.

# Answer
> -3 votes
You can simply use `pow(x,2)` this comes under the library `#include<math.h>`

---
Tags: algorithms, arithmetic
---