# Question
Title: Find all critical edges for minimum spanning tree
This is a problem from the textbook "Algorithms, 4th edition" by Robert Sedgewick and Kevin Wayne.

> **4.3.26** *Critical edges*. An MST edge whose deletion from the graph would cause the MST weight to increase is called a *critical edge*. Show how to find all critical edges in a graph in time proportional to $E \log E$. *Note*: This question assumes that edge weights are not necessarily distinct (otherwise all edges in the MST are critical).

There is an algorithm (see below), as well as an accepted answer, at stackoverflow. However, in my opinion, the correctness proof is not complete because it does not justify that *all* critical edges can be found. Moreover, I cannot figure out how the time complexity of $O(m \log m)$ is achieved in this algorithm (given the hint in the answer).

The algorithm is (in my understanding):

* Run Kruskal algorithm on this graph. Whenever we encounter an edge $e$ whose insertion in the MST creates a cycle, the edges in this cycle with smaller weights than $w(e)$ will be reported as critical edges.

***My questions are:***

* How to prove the correctness of this algorithm: (1) all edges reported are critical edges; (2) all critical edges are reported?
* How to achieve $O(m \log m)$ with appropriate data structures?
* If this algorithm is wrong, how to solve the problem?

# Answer
Since Kruskal's algorithm sorts the edges according to their lengths, the trick here i to partition the edges into subsets of edges with equal lengths.

For each subset (in increasing order) check which components are being joined using each edge of this set before joining them. If two (separate) components are being joined using more than one edge of this subset then both (all) these edges are non critical (since we can choose any of them and still get a spanning tree).

Now we are visiting each subset (and accordingly each edge) two times, the complexity is still in $O(|E|)$ and we need an additional $\log$ for the DSU join operations.

However, you should be aware of the case where for example three edges $\epsilon\_1,\ \epsilon\_2,\ \epsilon\_3$ of the same lengths joins components $V\_1-V\_2, V\_2-V\_3, V\_3-V\_1$ respectively, which makes non of them critical point since we can use any two of them and leave the third one. A solution of this problem is to add all this edges at first to the Graph, then you will have a non tree graph, with cycles in places where you had many choices, and that makes the critical edges exactly the **Bridges** (check the link) in this graph.

P.S since bridges can be found in $O(|V| + |E|)$ total runtime is still $O(|E|\*\log|E|)$
> 1 votes

# Answer
### The simplest and fastest algorithm

Here is a correct algorithm that finds all critical edges.

Input: a weighted connected undirected graph $G=(V, E)$.
Output: all critical MST edges.
Procedure:

1. Let $result$ be an empty list.
2. Make a disjoint-set data structure starting with $V$ with operations $\text{find}(\cdot)$ and $\text{union}(\cdot, \cdot)$. That is, each vertex will be represented by itself.
3. Sort all edges into blocks of edges of the same weight in strictly increasing order, $B\_1, B\_2, \cdots, B\_k$. That is, edges in $B\_1$ are of the same weight lighter than edges in $B\_2$. Edges in $B\_2$ are of the same weight lighter than edges in $B\_3$. Etc.
4. For each block $B$ in $B\_1, B\_2, \cdots, B\_k$, do:
    1. Create an empty graph $H$ and an empty map $\mathcal M$.
    2. For each edge $(u,v)$ in $B$,
        * if $\text{find}(u)$ is not a vertex of $H$, add it to $H$.
        * if $\text{find}(v)$ is not a vertex of $H$, add it to $H$.
        * if $\\{\text{find}(u), \text{find}(v)\\}$ is not an edge of $H$, add it to $H$ and let $\mathcal M$ map $\\{\text{find}(u),\text{find}(v)\\}$ to $\\{u,v\\}$.
    3. Find all bridges in $H$. This can be done as described at here or here.
    4. For each bridge $b$, add $\mathcal M\[b\]$ to $result$.
    5. For each edge $(u,v)$ in $H$, call $\text{union}(u,v)$.
5. Return $result$.

If $\text{find}(\cdot)$ and $\text{union}(\cdot,\cdot)$ and finding bridges are not implemented badly, this algorithm runs in $\mathcal O(E\log E)$.

### An edge is critical iff it appears in every MST.

It is easy to prove the proposition above. What is returned by the algorithm above is, in fact, all edges that must appear in every MST.

### Detailed analysis on the 3 questions of OP

Please see a previous version of this answer.
> 1 votes

---
Tags: data-structures, correctness-proof, minimum-spanning-tree
---


# Question
Title: What is the difference between "backhaul" and "core" network in cellular networks?
I was reading some publications on cellular networks. They constantly mention two similar concepts — **backhaul network** and **core network**. I am not sure if these two are the same stuff, or in any way they are different. Does anyone know the differences? thanks!

# Answer
> 2 votes
Let's have a little bit of a glimpse from the diagram below;

What you can analyse in that diagram,is a convention point to point (PTP) and line of sight (LOS), a microwave link uses atail node and aggregation node,which allows remote base station to access the **core network** through the **backhaul** link.

*Therefore,backhaul network is a side network which communicates with the core network,i.e. it links packets **to** and **from** the core network.*

That said, cellphones also communicates with a single cell tower which constitutes a local network (subnetwork);whereby the link between the celltower and rest of the world(to the core network) begins with the backhaul link. The rest of the world is termed as autonomous network system,which is administered by global internet providers.

A high-level summary is that cellular backhaul refers to transport from remote cell towers to mobile telephone switching offices (MTSO). This backhaul is frequently provided by a third-party internet service provider via layer 2 circuits. The ISP's edge device (optical switch or router) with a customer handoff point (UNI) is located at the cell tower and the network demarcation between the ISP and the cell provider's core network (ENNI) is located at the MTSO. An EVPL (point-to-multi-point) configuration is commonly implemented with both circuits traveling from the tower to the MTSO over divergent paths to provide redundancy.

*Hope this can give you some insights.*

# Answer
> 0 votes
I might be wrong, I did not read this anywhere, but, for me it would mean:

1. *Backhaul*: a service link, with the main purpose of carrying information from one point to another. When we think about this network, we mainly think about throughtput, latency, etc... it is its main task.
2. *Core*: network for the interconection of the different nodes. Its main purpose is to provide funcionality, but throughput is secondary (even though it can be high).

This is very loose, but I think those terms are equally loose too.

---
Tags: computer-networks
---


# Question
Title: Trick/insight to I implement given boolean function with minimum numbers of given gate
I solved bunch of questions which give some function and then ask to implement it with minimum number of gates of specific type, each having specific number inputs. I was making mistakes in all those problems by not implementing given function with minimum number of gates.

Let me give those problems one by one and explain my point.

---

> **Problem 1**
>
> What is minimum number of two input NAND gates required to implement the function:
> $f=\overline A \overline C+\overline A\overline B+\overline B \overline C$

I translated the function directly to the circuit as follows:

Then I converted this to NAND-only implementation as follows:

But when I checked the answer, it was saying lesser NAND gates. So I tried something different. I solved equation as follows:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}$
$=\overline{\overline{\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}.\overline{C}}}$
$=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

And realized that I will need seven NAND gates for following:

* $\overline{A}$
* $\overline{B}$
* $\overline{C}$
* $\overline{(\overline{A}.\overline{C})}$
* $\overline{(\overline{A}.\overline{B})}$
* $\overline{(\overline{B}.\overline{C})}$
* $=\overline{\overline{(\overline{A}.\overline{C})}.\overline{(\overline{A}.\overline{B})}.\overline{(\overline{B}.\overline{C})}}$

But then I checked detailed solution and found that the solution has come up with following equation:

$f=\overline{A}.\overline{C}+\overline{A}.\overline{B}+\overline{B}\overline{C}$
$=\overline{A}.\overline{C}+\overline{B}(\overline{A}+\overline{C})$
$=\overline{A}.\overline{C}+\overline{B}\overline{(\overline{A}.\overline{C})}$
$=\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

This requires six NANDs:

* $\overline{A}$
* $\overline{B}$
* $\overline{C}$
* $\overline{(\overline{A}.\overline{C})}$ (used twice in the equation)
* $\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}$
* $\overline{\overline{\overline(\overline{A}.\overline{C})}.\overline{\overline{B}\overline{(\overline{A}.\overline{C})}}}$

So I was wrong twice!!!

---

**Problem 2**
Another problem gave truth table of the function and asked to implement it with NOR gate. I prepared truth table for it and grouped zeroes as follows:

***Knowing that I have to use NOR, I thought I should form product of sum equation of this and then take double negation to get NOR friendly equation***. So, I formed equation for it as follows:

$f=(x+\overline y)(\overline x + y)$
$=\overline{\overline{(x+\overline y)(\overline x + y)}}$ (taking double complement)
$=\overline{\overline{(x+\overline y)}+\overline{(\overline x + y)}}$

Now this looks perfect NOR equation as thought and it requires five NORs. But when I checked the solution, I came to know that this is indeed ExNOR equation. The solution formed sum of product equation of K map:

$xy+\overline x \overline y$

and then implemented ExNOR with four NORs, something like this:

---

**Doubt**

I have solved many other problems. It almost always turned out that I have followed one approach and the solution followed another to further reduce the GATE count. I feel there should be some steps / methods to get idea how many minimum number of gated are required. I know this problem is NP complete. However I feel that there has to some definite patterns on k map which can lead us / give direction / provide hint to correct final answer.

Can there be any such method? trick?

# Answer
> 4 votes
There is no trick. There is no efficient method. The circuit minimization problem is NP-hard (in fact $\Sigma\_2^P$-hard), and I suspect that finding the smallest circuit with only NAND gates is NP-hard, too. That should tell you that there is no systematic approach that always works and is reasonably efficient. Instead, you will have to use heuristics and trial-and-error. For instance, you might have to try multiple methods and take the best circuit you can find among all of them.

---
Tags: digital-circuits
---


# Question
Title: How to determine seed collision probability in a PRNG?
I want to use a PRNG to generate random patterns. I would provide the PRNG with a hash value as a seed. Ideally, the seed size would be 64-bit or 128-bit and I would expect no collisions if the seeds are unique.

Do PRNGs encounter 'collisions', where two different seeds produce the exact same sequence of random numbers?

For example, if one initializes a PRNG with **all possible 32-bit, 64-bit or 128-bit numbers**, one would expect zero collisions since all seeds would be different.

When considering a Linear congruential generator, the seed gets divided into a multiplier. Since a Lehmer LCG uses a multiplier of 231-1, supplying a random 32-bit hash would cause collisions, since it is dividing all possible 32-bit numbers into 231-1 numbers. Thus, a seed of 1, 232-1 and 231 are equivalent and produce the same sequence of numbers. This is a problem since I am expecting the collision resistance of 64 or 128-bit hashes in the PRNG.

For more complicated algorithms, it's not as simple to determine these cases. My language of choice is JavaScript, which has no built-in seeded PRNG. There are of course many options to remedy this in the sense of libraries or standalone functions.

The best/fastest available PRNG for JavaScript seems to be Alea. It has a JS and C implementation and is based on Marsaglia's MWC algorithm. The JS implementation takes a *variable string seed*, so it is not clear how many unique seeds are possible. Alea is described as having a period length of 2116, which if I understand correctly, would mean it utilizes up to 116 bits of a supplied seed (e.g. a 128-bit hash).

Basically what I am asking is, **how would I determine if seeds collide in a PRNG? Is it based on the described period length?**

A good illustration of the issue is to compare Jenkin's small PRNG (2007) with xoshiro128+ (2018). They are quite similar. They both use 32-bit arithmetic, store the state in a 128-bit array composed of four uint32's and return one uint32 as the result. The main difference is that Jenkins only uses a 32-bit seed that is repeated in b,c,d. While in xoshiro128+ the entire initial state is the seed. Thus I can supply a 128-bit hash to the latter as the seed and still benefit from the quality of the generator (without modifying the algorithm). That is essentially what I mean - being able to provide a very large seed.

As a workaround to this potential issue, I thought about simply using the hash function itself, and running further iterations of the mixing function to obtain new pseudo-random bits (in the same way as obtaining a new number in a PRNG). It is deterministic and appears random enough, but it seems unlikely that hash function outputs pass "statistical randomness tests" such as Diehard or BigCrush since it was not designed as a PRNG.

Also, there are no cryptographic requirements here. The hash function I would use would be MurmurHash3 or similar--anything good enough to pass SMHasher suite of tests and produces 64-bit or 128-bit hashes.

# Answer
I think I understood your concern. So, the period length cannot be larger than the number of internal states. I.e. if internal state is 128 bits, then period cannot be larger than 2^128. Moreover, good PRNG try to implement longest possible period for given state size, f.e. 2^128-1 for 128-bit state.

Next point is that you can seed PRNG by directly assigning values to the internal state, except that you need to fulfill some requirements. In particular, http://xoshiro.di.unimi.it/ PRNGs can be initialized with any non-zero state. It's guaranteed that state will go through all other non-zero values before repeating the initial state (because each their PRNG with N-bit state has period of 2^N-1).

If last statement isn't clear enough, imagine PRNG with N bits of state and period of 2^N. Since there are exactly 2^N possible internal states, on order to have such large period, the PRNG has to ensure that state will go through all possible values before repeating the initial state.

All http://xoshiro.di.unimi.it/ PRNGs maps zero state to itself. So, in order to provide 2^N-1 period, they have to go through all non-zero states before repeating the state.

Now, if you have a PRNG with period of 2^116, it doesn't necessarily mean that it has only 116 bits of internal state. It may have f.e. 128 state bits, but all possible states are split into 2^12 groups, each containing 2^116 members. Inside each group, values are cycled, so we have a cycle (PRNG period) of 2^116 items. And remaining 12 bits essentially choose one of these groups. It's not strictly necessary, but what we can expect from a reasonable PRNG. Alternatively, bad PRNG may have just a single cycle of 2^116 values, and all other values converged to this cycle after a few steps.

Now, concrete answer to your question is that the seed collision probability is AT LEAST equal to MINIMUM of seed space and PRNG period, or in more strict math terms:

P \<= 1/min(2^seed\_bits, PRNG\_period)

(at least if each seed value maps to different internal state). But as you see, larger period means less independent cycle groups. Ans if period is (almost) equal to the internal state space, then each state is just a point in the one and only cycle.

So, yeah, in particular all own http://xoshiro.di.unimi.it/ PRNGs produce exact the same sequence of numbers and seed/state choose only the initial point in this sequence.

How you can live with it? If you plan to start less than 2^32 sequences, and request less than 2^32 numbers in each one, there are very good chances that you will never encounter overlap. If you need more - just choose PRNG with 256-bit (or longer) state.
> 1 votes

# Answer
It depends on the PRNG. But it doesn't matter in practice. As long as the probability of collisions is low enough, who cares? These are pseudorandom numbers, so no one ever claimed they are perfect (exactly uniformly distributed); at best they are indistinguishable from random by any procedure that uses a limited amount of computing power.
> 1 votes

---
Tags: algorithms, algorithm-analysis, probability-theory, randomness, pseudo-random-generators
---


# Question
Title: When is the minimum spanning tree for a graph not unique
Given a weighted, undirected graph G: Which **conditions** must hold true so that there are **multiple** minimum spanning trees for G?

I know that the MST is unique when all of the weights are distinct, but you can't reverse this statement. If there are muliple edges with the same weight in the graph, there *may be* multiple MSTs but there might also be just one:

In this example, the graph on the left has a unique MST but the right one does not.

The closest I could get to finding conditions for non-uniqueness of the MST was this:

Consider all of the *chordless* cycles (cycles that don't contain other cycles) in the graph G. If in any of these cycles the maximum weighted edge exists multiple times, then the graph does not have a unique minimum spanning tree.

My idea was that for a cycle like this

with n vertices, you can leave out exactly one of the edges and still have all of the vertices be connected. Therefore, you have multiple choices to remove the edge with the highest weight to get a MST, so the MST is not unique.

However, I then came up with this example:

You can see that this graph does have a cycle that fits my condition: **(E,F,G,H)** but as far as I can see, the minimum spanning tree is unique:

So it seems like my condition isn't correct (or maybe just not completely correct). I'd greaty appreciate any help on finding the necessary and sufficient conditions for the non uniqueness of the minimum spanning tree.

# Answer
> 13 votes
~~in the first picture: the right graph has a unique MST, by taking edges $(F,H)$ and $(F,G)$ with total weight of 2.~~

Given a graph $G=(V,E)$ and let $M=(V,F)$ be a minimum spanning tree (MST) in $G$.

If there exists an edge $e=\\{v,w\\}\in E \setminus F$ with weight $w(e)=m$ such that adding $e$ to our MST yields a cycle $C$, and let $m$ also be the lowest edge-weight from $F\cap C$, then we can create a second MST by swapping an edge from $F\cap C$ with edge-weight $m$ with $e$. Thus we do not have uniqueness.

# Answer
> 6 votes
A previous answer indicates an algorithm to determine whether there are multiple MSTs, which, for each edge $e$ not in $G$, find the cycle created by adding $e$ to a precomputed MST and check if $e$ is not the unique heaviest edge in that cycle. That algorithm is likely to run in $O(|E||V|)$ time.

**A simpler algorithm to determine whether there are multiple MSTs of G in $O(|E|\log(|V|))$ time-complexity**.

> $\ $1. Run Kruskal's algorithm on $G$ to find an MST $m$.
>
> $\ $2. Try running Kruskal's algorithm on $G$ again. In this run, whenever we have a choice among edges of equal weights, we will first try the edges not in $m$, after which we will try the edges in $m$. Whenever we have found an edge not in $m$ connects two different trees, we claim that there are multiple MSTs, terminating the algorithm.
>
> $\ $3. If we have reached here, then we claim that $G$ has a unique MST.

An ordinary run of Kruskal's algorithm takes $O(|E|\log(|V|))$ time. The extra selection of edges not in $m$ can be done in $O(|E|)$ time. So the algorithm achieves $O(|E|\log(|V|))$ time-complexity.

**Why can this algorithm determine if there are multiple MSTs?**

Suppose we have an MST $m'$ that is not the same as $m$. It is enough to show that the algorithm running on $G$ will not reach step 3, since the edge found at the end of step 2, which is not in $m$ and connecting two different trees would have been included in the resulting MST had we run Kruskal's algorithm to completion. Let $w$ be the largest weight such that for any edge weighing less than $w$, it is in $m$ if and only if it is in $m'$. Because $m$ and $m'$ have the same number of edges of weight $w$, there exist edges of weight $w$ that are in $m'$ but not in $m$. If the algorithm has exited before processing edges of those edges, we are done. Otherwise, suppose the algorithm is going to process the first edge $e'$ among those edges now. Let $S$ be the set of all edges that have been preserved so far to be included in the resulting MST. $S\subset m$. Since the algorithm have not finished processing edge of weight $w$ not in $m$ such as $e'$, it must have not begun processing edges of weight $w$ in $m$. So edges in $S$ weigh less than $w$. That means $S\subset m'.$ Recall that $e'$ is in $m'$. Since $\\{e'\\}\cup S\subset m'$, where $m'$ is a tree, $e'$ must connect two different trees in $S$ and the algorithm exits at this point.

**Note on further development**
Step 1 and step 2 can be interleaved so that we can terminate the algorithm as soon as possible without processing of edges of greater weights.
In case you want to compute the number of MSTs, you may check an answer to how to compute the number of MSTs.

# Answer
> 4 votes
Let $G$ be a (simple finite) edged-weighted undirected connected graph with at least two vertices. Let ST mean spanning tree and MST mean minimum spanning tree. Let me define some less common terms first.

* An edge is unique-cycle-heaviest if it is the unique heaviest edge in some cycle.
* An edge is non-cycle-heaviest if it is never a heaviest edge in any cycle.
* An edge is unique-cut-lightest if it is the unique lightest edge to cross some cut.
* An edge is non-cut-lightest if it is never a lightest edge to cross any cut.
* Two STs are adjacent if every ST has exactly one edge that is not in the other ST.
* An MST is an isolated MST if it is not adjacent to another MST (when both MSTs are considered as STs).

## When are there more than one minimum spanning tree?

To answer OP's question, here are **five characterizations of $G$ that has more than one MST**.

* There are two adjacent MSTs.
* There is no isolated MST.
* There is an ST which is as light as or lighter than all adjacent STs and which is as light as one adjacent ST.
* There is an edge which is neither unique-cycle-heaviest nor non-cycle-heaviest.
* There is an edge which is neither unique-cut-lightest nor non-cut-lightest

The novelty of this answer is mostly the last two characterizations. The second from last characterization can be considered as the very next step of the OP's approach. The first three characterizations together can be considered as a slightly enhanced version of dtt's answer.

It is easier to think in the opposite term, whether $G$ has a unique MST. The following is the opposite and equivalent version of the above characterizations.

## When is the minimum spanning trees unique?

**Theorem: the following properties of $G$ are equivalent.**

* **Uniqueness of MST**: There is a unique MST.
* **No adjacent MST**: there is no adjacent MSTs.
* **One isolated MST**: there is an isolated MST.
* **One local minimum ST**: there is an ST which is lighter than all adjacent STs.
* **Extreme cycle edge**: every edge is either unique-cycle-heaviest or non-cycle-heaviest.
* **Extreme cut edge**: every edge is either unique-cut-lightest or non-cut-lightest

Here comes my proof.

"Uniqueness of MST" =\> "No adjacent MST": obvious.

"No adjacent MSTs" =\> "One isolated MST": obvious.

"One isolated MST" =\> "One local minimum ST": An isolated MST is lighter than all adjacent STs.

"One local minimum ST" =\> "Extreme cycle edge": Let $m$ be an ST that is lighter than all adjacent STs.

* Every edge in $m$ must be non-cycle-heaviest. Here is the proof. Let $l$ be an edge in $m$. If $l$ does not belong to any cycle, we are done. Now suppose $l$ belongs to a cycle $c$. If we remove $l$ from $m$, $m$ will be split into two trees, which will be named $m\_1$ and $m\_2$. As a cycle that connects $m\_1$ and $m\_2$ with $l$, $c$ must have another edge that connects $m\_1$ and $m\_2$. Name that edge $l'$. Let $m'$ be the union of $m\_1$, $m\_2$ and $l'$, which must be a spanning tree of $G$ as well. Since $m$ and $m'$ are adjacent, $m$ is lighter than $m'$. That means, $l$ is lighter than $l'$. So $l$ is non-cycle-heaviest.
* Every edge not in $m$ must be unique-cycle-heaviest. Here is the proof. Let $h'$ be an edge not in $m$. If we add $h'$ to $m$, we will create a cycle $c$. Let $h$ be an edge in $c$ that is not $h'$. Consider the spanning tree $m'$ made from $m$ with $h$ replaced by $h'$. Since $m$ and $m'$ are adjacent, $m$ is lighter than $m'$. That means, $h$ is lighter than $h'$. So $h'$ is the unique heaviest edge in $c$. That is, $h'$ is unique-cycle-heaviest.

"Local minimum ST" =\> "Extreme cut edge": Proof is left as an exercise.

"Extreme cycle edge" =\> "Uniqueness of MST": Let $m$ be an MST. Let $e$ be an arbitrary edge. If $e$ is non-cycle-heaviest, $m$ must contain it. If edge $e$ is unique-cycle-heaviest, $m$ cannot contain it. (These two propositions can be proved by the standard reasoning about MST using cycle and edge exchange, similarly to what have been done just above). Hence $m$ is exactly the set of non-cycle-heaviest edges.

"Extreme cut edge" =\> "Uniqueness of MST": Proof is left as an exercise.

The above chains of implications proves the theorem.

Once again, the novelty of this answers is mostly the "extreme cycle edge" property and the "extreme cut edge" property, which uses the concepts, non-cycle-heaviest and non-cut-lightest. I have not seen those concepts elsewhere, although they are quite natural.

---

Here are two related interesting observations.

* For any edge $e$, $e$ is non-cycle-heaviest $\Leftrightarrow$ $e$ is unique-cut-lightest $\Leftrightarrow$ $e$ is in every MST
* For any edge $e$, $e$ is unique-cycle-heaviest $\Leftrightarrow$ $e$ is non-cut-lightest $\Leftrightarrow$ $e$ is not in any MST

---

## Two sufficient but not necessary conditions for unique MST

the uniqueness of the heaviest edge in every cycle implies the "extreme cycle edge" property. So it is a sufficient condition. A counterexample to its being necessary condition is the graph with weights $ab\rightarrow 1, bc\rightarrow 1, cd\rightarrow 1, da\rightarrow 2, ac\rightarrow 2$.

the uniqueness of the lightest edge in every cut-set implies the "extreme cut edge" property. So it is a sufficient. A counterexample to its being necessary condition is a triangle with weights $1,1,2$.

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


# Question
Title: Hypothetical question on floating point normalization
I've seen a few questions posted regarding the upsides/downsides of floating point formats that have explicit integrals vs. formats that have implicit integrals, but have not seen an answer that really handles my question about it. By integral, I mean the single digit to the left of the radix point.

Let's assume that the hypothetical formats in question both have adequate precision for every possible use they will be put to (so that we can avoid the obvious point that the implicit integral adds more precision in most circumstances).

In one format we have an implicit integral and the requirement that all operation results must be normalized. In the other format we have an explicit integral and do not have the requirement that operation results be normalized. What are the upsides/downsides to this second format in comparison to the first format?

My first observations are that: 1) The format with the explicit integral will have multiple valid representations for a large subset of representable numbers. The format with the implicit integral will have only one valid representation for any given representable number. I don't immediately see a reason why this would be a downside, but I feel like it could be.

2) The format with the explicit integral seems like it would have a marginally simpler hardware or software implementation. This doesn't look like much of an upside unless you are going for really intense performance optimizations, but it ought to be mentioned.

3) The big upside for the explicit integral is that it makes a special arrangement for subnormal numbers unnecessary. Every number that would have fallen into the not-quite-zero gap would just be another representable result with the same gap as between any other pair of results for a given exponent. It seems like this would also slightly simplify design implementations, but I don't take that as a certainty.

Is there anything obvious I'm missing? Anything non-obvious? I'm just trying to really understand this concept better from a purely theoretical CS perspective.

# Answer
> 1 votes
So first off, the implicit digit to the left of the radix point is not called an "integral". That's a very confusing use of that word. But I digress.

Having an unnormalised representation for floating-point numbers may simplify the *final* step of any basic floating point operation, because you don't need to re-normalise the result. But in turn, the *initial* steps of just about every floating point operation become more complex.

Let's take division as an example. Most modern floating-point hardware use Goldschmidt's algorithm, which is based on this idea:

Suppose that we want to calculate $\frac{n}{d}$, where $d$ is close to (but not equal to) one. Then we multiply both the numerator and the denominator by $2-d$.

Suppose $d = 1 + \epsilon$, then the new division problem is:

$$\frac{n}{1+\epsilon} = \frac{n(2-d)}{(1+\epsilon)(1-\epsilon)} = \frac{n(2-d)}{1-\epsilon^2}$$

This results in a denominator which is quadratically closer to 1. Repeat this operation until it gets close enough.

So Goldschmidt's algorithm works as follows. To calculate the quotient of two floating point numbers:

$$\frac{m\_1 \times 2^{e\_1}}{m\_2 \times 2^{e\_2}}$$

where $m\_1$ and $m\_2$ are between 1 and 2, we use a lookup table to find an approximation to $\frac{1}{m\_2}$, which we will call $R$. Then we calculate:

$$n\_1 = m\_1 R$$ $$d\_1 = m\_2 R$$ $$n\_{i+1} = n\_i (2-d\_i)$$ $$d\_{i+1} = d\_i (2-d\_i)$$

and when we have done enough iterations (say $j$), we return:

$$n\_j \times 2^{e\_1 - e\_2}$$

The final step will involve normalisation; $n\_j$ will not, in general, be between 1 and 2. So if we could have unnormalised floating point numbers, the final step will be a bit simpler.

But in return, the table lookup operation will be more complex. With normalised numbers, you can just use the first few bits of the significand. ("Significand", incidentally, refers to the part of the mantissa that is actually stored in a normal floating-point number, without the implicit leading 1.)

So in that sense, there is no advantage to having an unnormalised representation for floating-point numbers. What you gain in a simpler final step you lose by having more complex initial steps.

# Answer
> 1 votes
The IEEE 754 32 bit and 64 bit floating point formats have an *implicit* leading mantissa bit, while the 80 bit format has an *explicit* leading mantissa bit. "Implicit" means that we determine from other information whether that bit is 1 or 0 (for denormalised numbers, the implicit leading bit is zero).

80 bit numbers where the explicit leading is 0 where it would have been an implicit 1 in 32 or 64 bit are called "unnormalised" numbers (not "denormalised"). There are two ways to handle them, and I think an implementation is free to use either way: Either the unnormalised number is first converted to a normalised or denormalised number, or there is no requirement or guarantee how the number is treated at all. (It would also be Ok to raise an interrupt when unnormalised numbers are encountered, so the behaviour would be well-defined but sloooooow). It depends on what the implementation says. In no case is an implementation allowed to produce an unnormalised number as the result of an operation not involving unnormalised numbers.

So each number has only one canonical representation, and in many implementations only one legal representation. In practice, unnormalised numbers are just ignored. They would only come up if you use uninitialised memory which is undefined behaviour anyway. You can't use bytewise comparisons, but you can't use them anyway because of +0 and -0.

---
Tags: floating-point
---


# Question
Title: Why strokes are treated differently than fills in modern graphics pipelines
This article shows some of the issues. But basically, on the web, you have `fillStyle` and `strokeStyle`, and in WebGL you have those different ways of rendering primitive lines, but you end up needing workarounds to draw more complex lines. In CSS borders don't have patternable backgrounds, etc.

Wondering why this limitation is placed on strokes/borders, if it has some history or background on why. It seems like in many cases you want a line to have as much freedom as a "fill", such as gradients, patterns, animations, text, etc. For example, pen strokes vary in thickness all over the place, but strokes typically only support 1 width.

# Answer
Modern graphics hardware draws triangles. 99% of the hardware is dedicated to drawing triangles. One percent is support for line drawing, and it's mostly for historical reasons. If at all possible, line drawing will be done using the triangle drawing hardware.
> 2 votes

---
Tags: graphics, history
---


# Question
Title: How to implement insertion sort on linked list with best case performance O(n)?
I have an almost sorted linked list containing **N** distinct elements with only **1** element not in it's place. Every implementation I have seen start insertion from the beginning (unlike insertion sort on arrays) therefore the complexity will be **$O(N^2)$**.

# Answer
Best case performance is attained when only one element is not in place. Assume the following list

1-\>2-\>3-\>4-\>0

You can easily show that it takes you $O(n)$ to sort via insertion sort: The inner while loop will run $n$ times when the outer loop reaches node 0. Otherwise, it will never be executed.
> 1 votes

---
Tags: sorting
---


# Question
Title: How to solve $T(n)\leq n^2+n\left[T(n-m)+T(m-1)\right]$?
I am trying to find $T(n)=O(f(n))$, where $$T(n)\leq n^2+n\left\[T(n-m)+T(m-1)\right\],$$ where $m\in\\{1,2,\ldots,n\\}$.

Is it possible to find $f(n)$ such that $T(n)=O(f(n))$?

I started to fix $m=n/2$ (which I assume the worst scenario, isn't it?). I found $$\begin{align}T(n)&\leq n^2+\frac{n^3}{2}+\frac{n^4}{8}+\frac{n^5}{64}+\frac{n^4}{4}T(n/16),\\ &\\;\vdots\\\& \leq n^2+T(1)\sum\_{i=1}^{(\lg n)-2}\frac{n^{i+2}}{\sqrt{2^{i(i+1)}}}.\end{align}$$

# Answer
> 5 votes
On the one hand, we have $$ \begin{align\*} T(n) &\geq n^2 + nT(n-1) \\ &\geq n^2 + n(n-1)^2 + n(n-1) T(n-2) \\ &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + n(n-1)(n-2)T(n-3) \end{align\*} $$ and so on. Assuming, for simplicity, a base case of $T(0) = 0$, this gives $$ \begin{align\*} T(n) &\geq n^2 + n(n-1)^2 + n(n-1)(n-2)^2 + \cdots + n(n-1)\cdots (1)^2 \\ &= n! \left(\frac{n}{(n-1)!} + \frac{n-1}{(n-2)!} + \cdots + \frac{1}{0!} \right) \\ &= n! \left(n + \frac{1}{(n-1)!} + \frac{1}{(n-2)!} + \cdots + \frac{1}{1!}\right) \\ &= n! \left(n + e - 1 \right) - O(1). \end{align\*} $$ This should also work as an upper bound. To prove this rigorously, choose an upper bound $S(n)$ for which you can prove $S(n) \leq n^2 + n(S(n-1) + S(0))$ as well as that $S(n)$ is convex. Convexity will ensure that the values of $m$ maximizing the sum $S(n-m) + S(m-1)$ are $m=1$ and $m=n$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Local search to find minimum degree spanning tree
Suppose for a graph $G=(V,E)$ and a spanning tree T of G, $\Delta(T)$ is the largest degree of a vertex in T, and let $\Delta^\*$ be the smallest such quantity over all spanning trees of $G$.

We have the following local search procedure which can changes spanning tree $T$ into a different spanning tree $T'$: We find an edge $e$ not in $T$ and add it to $T$. This results in a cycle $C$ - call its vertices vertices $V(C)$. We then delete an edge in $C$ incident to a vertex in $V(C)$ with highest degree.

My question is this: if $\Delta(T) \> \Delta^\*$, can we always find an edge $e$ to add, such that the maximum degree of vertices in $V(C)$ is strictly less in $T'$ than it is in $T$?

# Answer
> 2 votes
No, we cannot always find an edge $e$ to add when $\Delta(T) \> \Delta^\*$.

The graph above was drawn at https://graphonline.ru/en

Here is an counterexample. Let $G$ be the 3-regular graph on the right side that has 14 vertices and 21 edges. Let $T$ be the spanning tree that consists of all the edges in bold. That is, $T$ has all the edges in $G$ except the innermost 7 edges and the edge at the top right. The graph on the left side shows a hamiltonian path of $G$. That is, $\Delta(T)=3$ and $\Delta^\*=2$.

Let $e$ be an edge not in $T$. If we add $e$ to $T$, the resulting cycle $C$ contains at least two non-adjacent vertices of degree 3 in $T$. If we further delete any edge in $C$ incident to a vertex in $C$ with the highest degree 3, we obtain graph $T'$. There is at least one vertex of degree 3 in $T'$. That is, the maximum degree of vertices in $V(C)$ in $T'$ is 3.

---
Tags: algorithms, spanning-trees, minimum-spanning-tree
---


# Question
Title: sort n numbers in the range [0,1] without multiplying or dividing
Given an array with n real numbers, each in the range \[0,1\], I need to sort them. Moreover, the only operations that are allowed are comparisons or copying.

It means I cannot multiply or divide the numbers, which prohibits me from using bucket sort.

From what I learned, when you use only comparisons you cant sort any faster that O(nlogn). That means that I can just use any sort algorithm that achieves this bound, let's say heapsort, and be done with it.

However, in this way i don't use the info that the numbers are from the range \[0,1\]. For this reason, I'm not sure if I'm right.

# Answer
> 3 votes
The $\Omega(n \log n)$ lower bound still applies; you still can't do better than $O(n \log n)$.

(Proof: Take any array of numbers. You can find the maximum and minimum in $O(n)$ time. Then, rescale the array. In particular, if the minimum and maximum are $\alpha$ and $\beta$, replace each element $x$ of the array with $(x-\alpha)/(\beta-\alpha)$. After the replacement, every element will be in the range $\[0,1\]$. If you had a way to sort such arrays faster than $O(n \log n)$, you'd immediately obtain a way to sort the original array faster than $O(n \log n)$.)

# Answer
> 0 votes
You can find the proof in TAOCP - there are n! (i.e. factorial of n) of possible orderings. Since each comparison returns only single bit of information and thus only halves amount of possibilities, you need to perform at least log(n!) comparisons which is O(n log n).

Of course, the same proof applies to the radix sort ;) The real difference between comparison-based sorts and radix is that you can reveal more than one bit of info by a single choose\_bucket operation.

The rest is just subtle difference of initial conditions - you can sort with comparisons faster than O(n log n) given sufficient amount of duplicates. And you cannot sort with radix faster than O(n log n) if all sorted values are unique.

In your particular case, do you mean theoretical unilimited-precision floating numbers? In this case, you cannot sort them with a fixed prescribed amount of radix sort passes. OTOH, if you mean real-world fixed size FP values, they can be sorted with a fixed amount of comparisons per array element although, well, this amount is pretty large ;)

---
Tags: algorithms, data-structures, sorting, comparison
---


# Question
Title: Why time complexity of union-find is $O(lgN)$ with only "Union by Rank"?
I'm studying time complexity of Union-Find data structure.

I saw time complexity of union and find function depends on some conditions.

1. without anything: $O(N)$
2. with Union by Rank: $O(\log N)$
3. with Path Compression: $O(\alpha(N))$ which is inverse Ackermann function.

I understood $O(N)$ because of skewed tree of disjoint set. But, I cannot understand $O(\log N)$. I looked on Wikipedia and Stack Overflow, but I couldn't find it. How can I prove second time complexity?

# Answer
> 4 votes
Firstly, here is the precise statement of the case 2 in OP's question.

> A sequence of m MAKE-SET, UNION, and FIND operations, n of which are MAKE-SET operations, can be performed on a disjoint-set forest with union by rank in worst-case time $O(m\log\_2 n)$.

In fact, it is trivial to see that the MAKE-SET and UNION operations run in $O(1)$ time. So the question is really about the time-complexity of the FIND operation.

Here are the properties of the disjoint-set forest you can prove.

1. Given any node $u$ that has been added to the set of union-find data structure, the ranks of the nodes in a path from $u$ to its root is strictly increasing.
2. A node $u$ which is root of a sub-tree with rank $r$ has at least $2^r$ nodes. (This fact can be proved by induction on $r$).
3. Every node has rank at most $\log\_2 n$.

With properties 1 and 3, it should be easy to prove the desired time complexity.

The above explanation follows roughly the section 21.4 in *Introduction To Algorithms*, third edition by CLRS. Readers are encouraged to read the chapter 21 of that book.

---
Tags: data-structures, time-complexity, union-find
---


# Question
Title: What fraction of all combinations is guaranteed to be deadlock free?
I found this question in the exercise of Tanenbaum (operating systems):

> Two processes, $A$ and $B$,each need three records $1, 2, \text{ and } 3$ in a database. If $A$ asks for them in the order $(1, 2, 3)$ and $B$ asks for them in the same order, deadlock is not possible. However, if B asks for them in the order $(3, 2, 1)$ then deadlock is possible. With three resources, there are $3!=6$ possible combinations each process can request resources. What fraction of all combinations is guaranteed to be deadlock free?

I haven't gotten any farther than that there are $6$ possible ways that $B$ can request: $(1,2,3), (1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1)$

Please help me out.

# Answer
Let's assume for simplicity that A and B take 5 seconds to request for the next resource and B starts requesting for resources 1 second after A's request.

* If A requests for 1 first and B requests for either 2/3 first, it will create a deadlock. This happens because when A requests for either 2/3 it will be blocked and B will be blocked when it requests for 1. So both processes will block each other and in turn will be blocked by each other.
* If A and B both request for 1, then A wins out and B will be blocked. So there will be no deadlock.

So the entire problems rests on B's choices. Therefore $\frac{1}{3}$rd of the cases will be deadlock free.
> 0 votes

---
Tags: concurrency, deadlocks
---


# Question
Title: What changes do I need to make to my algorithm to make this scene from a different angle?
The code below is in F#. It creates a scene which looks like a perspective coming from the top left. I thought if I would change `i % j = w` then it would come from the top right instead, but that doesn't work. So what change do I need to make for it to be able to come from the top right, bottom left, bottom right and even the top centre?

```
open System

let w = Console.WindowWidth
let h = Console.WindowHeight

for i in 1 .. w - 1 do
    for j in 1 .. h - 1 do
        Console.SetCursorPosition(i, j)
        if i % j = 0 then printf "."

Console.Read() |> ignore

```

Here is what the program looks like.

```
 .......................................................................................................................  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
   .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .
    .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .
     .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .    .
      .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .     .
       .      .      .      .      .      .      .      .      .      .      .      .      .      .      .      .      .        .       .       .       .       .       .       .       .       .       .       .       .       .       .
         .        .        .        .        .        .        .        .        .        .        .        .        .
          .         .         .         .         .         .         .         .         .         .         .
           .          .          .          .          .          .          .          .          .          .
            .           .           .           .           .           .           .           .           .
             .            .            .            .            .            .            .            .            .
              .             .             .             .             .             .             .             .
               .              .              .              .              .              .              .
                .               .               .               .               .               .               .
                 .                .                .                .                .                .                .                  .                 .                 .                 .                 .                 .
                   .                  .                  .                  .                  .                  .
                    .                   .                   .                   .                   .
                     .                    .                    .                    .                    .
                      .                     .                     .                     .                     .
                       .                      .                      .                      .                      .
                        .                       .                       .                       .
                         .                        .                        .                        .
                          .                         .                         .                         .
                           .                          .                          .                          .
                            .                           .                           .                           .
                             .                            .                            .                            .

```

# Answer
Can you try replacing the original condition `i % j == 0` with the following conditions? They work for me.

* For a perspective coming from the top right, `(w-i) %j == 0`
* For a perspective coming from the bottom left, `i %(h-j) == 0`
* For a perspective coming from the bottom right, `(w-i) % (h-j) == 0`
* For a perspective coming from the the top centre, `(w/2-i) % j == 0`
> 0 votes

---
Tags: algorithms, loops
---


# Question
Title: Is the capacity of a hash table a constant value?
In this paper, page 4, it is said:

"...there is always a constant expected number of elements that map to the same slot"

---

Assume we have a set $S$ of $n$ values, and we want to insert them into a hash table. Let's fix some parameters: let $d$ be the hash table's bin/slot capacity, i.e. the bin will get more than $d$ elements only with a negligible probability. Then, we set the hash table length, $h$.

**Question** 1: is it correct that the capacity of each bin is constant?

---

Moreover, assume we want to perform an operation on only one bin of the hash table.

**Question** 2: Is it correct to say the complexity of the operation is constant? because it performs the operation on a constant elements of the set $S$?

---

**Update**: Please note that the updated is inserted after the answer is given by provided by @D.W.

I am using a simple *static* hash table. Assume that the number of elements $n$ is known in advance. Also, for some reasons we want a bin capacity be $d$ with a high probability (e.g. $2^{40}$). Moreover, we use the equation in theorem 1, in here to calculate the number of bins (or hash table length) required. Furthermore, we want to perform a polynomial factorization, whose complexity is $O(d^{2})$, in one bin.

---

# Answer
> 2 votes
There are rare cases where the number of entries in a hashtable is fixed. There are some more cases where the number of entries *in one particular situation* is known, and the right number of slots can be allocated before you start filling the hash table.

But typical implementations start with a small number of slots, and if enough items are added so the expected number of collisions becomes too large, more slots are allocated and all items rearranged in the new slots.

Usually the implementation tries to keep the percentage of used slots in some range, say (just an example) between 45% and 70%, compromising between efficiency and used space. So as you add items and use more than 70% of slots are used, the implementer would increase the number of slots so that now 45% are used, and more items can be added. An implementer might also shrink the table if items are removed and say less than 30% of slots are used, but in practice hash tables tend to grow.

# Answer
> 2 votes
If I understood you correctly, your real need is a way to limit slot capacity with a high probability (BTW, probabilities cannot reach more than 100% == 20; what you mean is probably 1 - 2-40).

You can reach this goal with modified hash table handling procedure:

* Cuckoo hashing uses fixed-size slots with slower but still O(1) on average insert procedure, while allowing to reach load factor arbitrarily close to 100% by using larger slots
* Robin Hood hashing grows up the table when any hash chain becomes larger than prescribed value, but this event has very low probability (alternatively, you can just drop extra elements in such low-probable situation)
* Extensible hashing extends any approach by growing just the required parts of the hash table
* Perfect hash functions and Dynamic perfect hashing

# Answer
> 1 votes
I wonder if you've omitted some relevant context. If you insert $n$ items and ensure that the capacity of the hash table is $2n$, then the expected number of elements that map into any particular slot is constant ($1/2$).

The capacity of a bin depends on what kind of hashtable you're using, so it's not answerable without further context.

An operation that performs only a constant number of steps of computation, has constant complexity. So, you can count the number of steps of computation that are performed and you should be able to tell. If the expected number of elements in a slot is a constant, and if that operation takes a constant operations per element, then the *expected* complexity of that operation is a constant. (The worst case might be higher, as the worst-case number of elements per bin might be higher.)

---
Tags: complexity-theory, data-structures, asymptotics, hash, hash-tables
---


title: Neural Network Shape / Structure

text:
# Question
Title: Neural Network Shape / Structure
I am attempting to learn neural networks using the Keras libary on the MNIST hand written digit dataset, using dense layers only. I am trying to figure out what the best shape for the network should be but I can't seem to find any literature or discussion on the subject.

By shape, I mean should the hidden layers have more nodes as I go deeper, less nodes, or the same? I've taken to calling them square, pyramid, and reverse-pyramid because I couldn't find a better name. See the end of this post for clarification on shape

I've tried all 3 and the reverse pyramid is giving me the best at 80% accuracy but I can't imagine why. I feel like I would just be losing data and introducing noise by expanding the number of neurons as I go deeper.

Is there any literature or discussions about this subject? Perhaps, I'm not using the right keywords to look, I just don't know the correct terminology. I've tried neural network shape, structure, hidden layer layout, etc. with very little luck.

Thanks in advance.

Square - Hidden layers stay same size until the end

Pyramid - less neurons at each additonial hidden layer (pretend they are all hidden layers)

Reverse Pyramid - more neurons at each additiona hidden layer

# Answer
> 1 votes
Are you using the Training set for testing ? What is your train test split ?

With Neural Nets, it's always the pyramid shape that works. This is because as you go deeper, data about the input is condensed and we get a proper representation of the input for outputting the required class or regression value.

The only reason reverse pyramid nets will work well is overfitting, which accommodates noise and does not generalize well.

http://www.deeplearningbook.org/contents/mlp.html

Try the Bible of Deep Learning for more details.

# Answer
> 0 votes
The most common case I've seen is that the number of neurons at each hidden layer decreases as you get closer to the output. However, there are no hard-and-fast rules. It may require some experimentation to see what works best in your particular application.

When working with images, convolutional neural networks (CNNs) often perform better than fully connected neural networks.

---
Tags: artificial-intelligence, neural-networks
---


# Question
Title: What if Indexes in Hoare's Quick Sort Algorithm Both Land on Values Less than Pivot?
If I were to sort the list of numbers 1,7,**5**,7,1 using Hoare's algorithm as described at the very beginning of wikipedia item on Hoare partition scheme with 5 being the pivot, and the indexes start at 1 and 1, then what would happen? If they are switched, nothing is really sorted. And the same goes for the two indexes both landing on numbers greater than the pivot, for example, 7 and 7. How would Hoare's algorithm handle such a case?

# Answer
You've misunderstood the algorithm and it doesn't have the behaviour you suggest.

Let the pivot value be $p$. The algorithm searches from the left for a value $\ell\geq p$ and from the right for a value $r\leq p$. It then only swaps them if they're in the wrong order relative to each other, i.e., if $\ell\>r$, so it will never exchange two identical array elements.

In your example, the algorithm would either swap the 1 on the left with the 7 on the right, or the 7 on the left with the 1 on the right, depending on exactly how it is implemented.
> 1 votes

# Answer
Here is the pseudocode at wikipedia on quicksort using the Hoare partition scheme:

```
algorithm quicksort(A, lo, hi) is
  if lo < hi then
    p := partition(A, lo, hi)
    quicksort(A, lo, p)
    quicksort(A, p + 1, hi)

algorithm partition(A, lo, hi) is
  pivot := A[lo]
    i := lo - 1
    j := hi + 1
    loop forever
      do  i := i + 1  while A[i] < pivot
      do  j := j - 1  while A[j] > pivot
      if i >= j then
        return j
      swap A[i] with A[j]

```

The indexes *never* start at the same number in `partition`:
`hi` is *at least* `lo`+1 (`j` is at least `i+3`).
They start indexing "from the ends" to "meet in the middle".

Assuming the list a, g, **e**, g, a from the question, indexing starting at 1 and `pivot` "magically" assuming e (the pseudo-code shown would set it to a), `i` gets initialised to 0 and `i` to 6 in the first execution of `partition`.

The 1st "do - while" in the "forever-loop" would set `i` to 1 unconditionally *and to 2 because `A[i]`, which is `A[1]`, (a) is smaller than `pivot`(e)*.

The 2nd "do - while" would stop right after setting `j` to 5:
`A[5]` already is smaller than `pivot`.
`i` is smaller than `j`: `partition` isn't done
`i` and `j` index a pair of elements in `A` deserving a swap - guess what?
> 0 votes

---
Tags: algorithms, algorithm-analysis, sorting, quicksort
---


title: how does the parallel radix sort work?

text:
# Question
Title: how does the parallel radix sort work?
I'm currently learning computer science, and there is a slide of notes brief described the parallel radix sort under data parallelism.

```
number 101 110 011 001 111 (1st bit)
order    2   1   3   4   5 (new order)
number 110 101 011 001 111 (2nd bit)
order    3   1   4   2   5 (new order)
number 101 001 110 011 111 (3rd bit)
order    3   1   4   2   5 (new order)
number 001 011 101 110 111

```

I roughly know how to sort it from lecturer's explanation, but how is it related to parallel computing to increase the performance?

# Answer
> 3 votes
There are many ways to do it. The following approach allows to fairly split work between many cores. I believe that it's used even in GPU implementations of radix sort, such as ones provided by Boost.Compute and CUDA Thrust.

I describe here one pass of LSD radix sort that distributes data into R buckets:

* First stage: split input block into K parts, where K is number of cores sharing the work. Each core builds histogram for one part of data, counting how many elements from this part of data should go into each bucket: `Cnt[part][bucket]++`
* Second stage: Wait till all cores finished the stage one, and then compute partial sums over counts, thus revealing an initial index of each bucket for every part of data. This is sequential algorithm.
* Third stage: each core again process its own part of data, sending each element into position determined by `Cnt[part][bucket]`

In pseudocode the entire pass looks like:

```
parallel_for part in 0..K-1
  for i in indexes(part)
    bucket = compute_bucket(a[i])
    Cnt[part][bucket]++

base = 0
for bucket in 0..R-1
  for part in 0..K-1
    Cnt[part][bucket] += base
    base = Cnt[part][bucket]

parallel_for part in 0..K-1
  for i in indexes(part)
    bucket = compute_bucket(a[i])
    out[Cnt[part][bucket]++] = a[i]

```

# Answer
> 1 votes
It turns out that within each round of radix sort, we can take advantage of parallelism. We need to reorder the keys (in a stable manner) according to the relevant bit. The simplest to do this in parallel would be as follows:

```
/* perform one round of radix-sort on the given input
 * sequence, returning a new sequence reordered according
 * to the kth bit */
function radixRound(input, k):
  front = filter(input, kth bit is zero)
  back = filter(input, kth bit is one)
  return concatenate(front, back)

```

In this approach, on each round, we "filter" the sequence twice. The first filter selects the subsequence of elements whose kth bit is zero. The second filter similarly selects the elements whose kth bit is one. We then complete the round by returning the concatenation of these two sequences. Here's a trace of your small example:

```
round 0:
input = [101, 110, 011, 001, 111]
front = [110]
back = [101, 011, 001, 111]

round 1:
input = [110, 101, 011, 001, 111]
front = [101, 001]
back = [110, 011, 111]

round 2:
input = [101, 001, 110, 011, 111]
front = [001, 011]
back = [101, 110, 111]

round 3:
input = [001, 011, 101, 110, 111]
(done)

```

Now all we have to do is explain how to do `filter` and `concatenate` in parallel. Assuming sequences are just implemented as arrays, `concatenate` is pretty simple. All we have to do is allocate an output array of the appropriate size and then, in parallel, write all the elements out to this new array:

```
function concatenate(a, b):
   n = length(a)
   m = length(b)
   result = allocate(n+m)
   for i from 0 to n+m do in parallel:
     if i < n:
       result[i] = a[i]
     else:
       result[i] = b[i-n]
   return result

```

Implementing `filter` in parallel is not so immediately obvious. The basic idea which is typically used in practice is to do a parallel prefix sum to count, at each position, how many elements satisfy the predicate preceding that position. This gives you the index of each surviving element of the output, so that in parallel you can write them into an output array.

With this implementation, you can do each round of radix sort in $O(n)$ work and $O(\log n)$ parallel time. This gives you a work-efficient radix sort with total work $O(wn)$ and parallel time $O(w \log(n))$, assuming a bit width of $w$. In practice, you would want to optimize this implementation to not allocate too many intermediate arrays, and to hopefully only make a single "pass" over the input on each round.

---
Tags: algorithms, sorting, parallel-computing, radix-sort
---


# Question
Title: Peaking finding when equals is taken out of the equation
I am going through the online course MIT OCW 6.006, lecture 1. It introduces a binary search algorithm that finds a peak in O(lgN) time.

A peak A\[i\] is defined as `A[i]>=A[i-1] and A[i]>=A[i+1]`. But I wonder what if the definition takes the equal sign out `A[i]>A[i-1] and A[i]>A[i+1]`, a peak is defined as an element that is strictly larger than its neighbour.

Obviously, the binary search algorithm will not work without changes, because for a case that `A[i]=A[i-1] and A[i]=A[i+1]`, it cannot decide to go left or right.

So, is there any algorithm that stills take O(lgN) time? (I personally think no, because for an array of equal numbers, aka the case that a peak does not even exists, you need to examine all elements)

# Answer
I can further improve your approach - let's consider an array that has peak, but all but two elements in the array are equal. O(log n) comparisons can check only O(log n) elements, so it's not enough even to decide whether peak is in first or second half of the array.
> 1 votes

---
Tags: algorithms, binary-search
---


# Question
Title: Minimum distance between two convex hulls maximized
I want to implement a program that splits a set $S$ of $n$ points in the plane into two sets such that the distance of the convex hulls of the two sets is maximized.

It should be done in $O(n^3)$.

I have several ideas but I'm not sure whether they are correct:

1. I sort points by $X$ and then for each two points I find the distance but only if there's no any other point between them. Then I choose the closest point to the first one on the left and the closest point to the second one on the right (first point would be part of the first polygon and second one of the second polygon).

Then I find distance between point and line, line and line, line and point and point and point(but I already know that). That's how i find the maximal distance and then with Graham scan I create a convex hull. I repeat everything for $Y$, because maximal distance could be on $Y$, not on $X$.
2. I sort points by $X$ and then create a convex hull for first $3$ and another convex hull for other points. Then find a minimum distance between these two hulls. I save the distance and if it's greater than distance i saved before I overwrite it and remember polygons. And last step is when only $3$ points are left for the second convex hull. Then I do all these steps for $Y$.

What do you guys think about my ideas? Do you have any improvements or maybe another, better idea?

# Answer
Given a pair of points $A,B$, you can split the the data into the points that are to the left of the line $AB$ (or on the line) vs the points that are strictly to the right of $AB$. Then you can compute the convex hulls of these two sets and you can find the distance between the convex hulls in $O(n)$ time, for a particular split (use a Graham scan; pre-sort the points once). Since there are ${n \choose 2} = O(n^2)$ ways to choose $A,B$, this immediately gives a $O(n^3)$ time algorithm.

In fact, you don't need to compute both convex hulls. It suffices to find the points that are closest (on each side) to the line $AB$. It might be possible to do this faster than $O(n)$ time, which would improve the overall running time. I think it suffices to compute a Voronoi diagram of all the points (a one-time $O(n \log n)$ time cost), then find all Voronoi cells that the line $AB$ goes through. I don't know whether the worst-case complexity will be less than $O(n)$ but I bet in practice this will often lead to significant speedups.
> 1 votes

---
Tags: algorithms, computational-geometry, convex-hull
---


# Question
Title: Fast algorithms that work on some large percentage of possible inputs
I've been wondering if research of these algorithms exists. An example, let's say I'm fine with $p$% of possible inputs of size $n$ to be unsorted. Is there an algorithm that would allow me to sort $n$ integers in sublinear time with a guarantee that $(100-p)$% of all possible inputs will be sorted.

Algorithms don't have to be linked the sorting, let's say it's optimization, is there an algorithm that will find the optimal tour for 1% of all TSP inputs of size $n$ really fast and what that algorithm is?

Is there a fundamental reason why these algorithms shouldn't exist or are hard to analyze?

# Answer
> 2 votes
Not quite what you're looking for but the concept of a randomized approximation scheme (RAS) is closely related and very widely studied. This is an algorithm for computing a (numerical) quantity $f(x)$ given an input $x$ and an error tolerance $\varepsilon$. With probability at least $\tfrac23$, the algorithm returns a value $\hat{f}$ such that $(1-\varepsilon)f(x)\leq\hat{f}\leq(1-\varepsilon)f(x)$. With probability at most $\tfrac13$, the algorithm either returns an answer outside that range or says, "Uh, I dunno." If the algorithm runs in time polynomial in $|x|$ (the length of the input) and $\varepsilon^{-1}$, it's called a fully polynomial randomized approximation scheme (FPRAS).

Only succeeding with probability at least $\tfrac23$ sounds pretty terrible – "Oh, wow, it's wrong one time out of every three!". However, it's easy to boost that to any satisfactory probability by running the algorithm repeatedly and taking the median answer (counting, "Uh, I dunno" as $\infty$). By a Chernoff bound, taking the median of $O(\log |x|)$ runs gives failure probability polynomial in $|x|^{-1}$ and taking the median of polynomially many runs gives exponentially small failure probability.

# Answer
> 2 votes
Algorithm with sublinear time will check less than 1% of array elements, thus more than 99% of array elements will remain unsorted, and chances that the entire array will become sorted are MUCH less than 1%.

You can apply the same analysis to other algorithms. So first you need to find tasks where checking less than 1% of data elements still may allow to get right answer in more than 1% of cases.

---
Tags: algorithms, algorithm-analysis
---


title: Minimum number of letters

text:
# Question
Title: Minimum number of letters
I have an assignment that I have to do and the question is

> Draw a DPDA that accepts the language L = {ba(bb)^(n+1)a^(n – 1) |n \> 1}.

Im not looking for the answer but rather some direction. I would like to understand the 'n' powers.

Currently my understanding of the above language is that it will start with ba (obviously) Then it will have (bb) however this is where I am confused....

The last part says n \> 1 does that mean that n+1 will have a min value of 3 meaning the language will always start with abbbbbbb(bb)\* or does n \> 1 mean at least 1 i.e. n+1 min value is 2?

Again please dont give me the solution to the DPDA as I would like to figure that out on my own.

Thanks Jacques.

# Answer
> 1 votes
n\>1 means that minimum n value is 2.

(bb)^n means bb repeated n times, i.e. if n=2, then it's bbbb.

With n=2, it's "ba bbbbbb a" (I added spaces only for clarity).

With n=3, it's "ba bbbbbbbb aa" - as you see, teacher used n to regulate size of the first and the second repetition in sync.

---
Tags: regular-languages, regular-expressions, pushdown-automata
---


# Question
Title: Question about non recursively enumerable language
1. Is every language (including languages over alphabet having infinite symbols) which is not recursively enumerable, uncountable?

In other words, let $R$ be the set of languages (including languages over alphabet having infinite symbols). For all $L$, belonging to $R$, that are not recursively enumerable, can it be said that $L$ is uncountable?

2. Is any language (in the set $R$ defined above) recursively enumerable and uncountable?

NB : I am asking about the (un)countability of a language (set of strings) and not a set of languages.

# Answer
Definition: a string over an alphabet $A$ (of finitely many symbols) is a finite sequence of symbols in $A$.
Definition: a language over an alphabet $A$ is a set of strings over $A$.

1. Is every language which is not recursively enumerable, uncountable?

**No.** Any language is a subset of the complete language $A\_\*$, the set of strings over $A$, which is a countable set. So, in fact, any language is a countable set of strings.

2. Is there any language which is recursively enumerable and uncountable?

**No.** The reason is the same as above.

The answers and the reasons behind them remain the same even if we allow $A$ to be a countably infinite set.

These two questions are not the same as the questions in Is there a non-recursive and uncountable language L?. However, the answer with its the reasoning are the same as \[the answer to that question\](https://cs.stackexchange.com/a/55855/91753.

---

OP just updated the question. So the only case left unanswered is when $A$ is an uncountably infinite set.

In that case, the definition of a language being recursively enumerable such as the one at wikipedia becomes inapplicable since all (common) models of Turing machines require the number of symbols to be finite (or at most countably infinite). To continue the discussion, we will need to make a new list of definitions for the Turing machines of the extraordinary kinds(which is not the Turing machines we usually talk about) or even other kinds of machines for hypercomputation and what is means by a recursively enumerable language with respect to those machines. That would be too large a scope that I would prefer not to go into in this answer.
> 0 votes

---
Tags: complexity-theory, formal-languages, uncountability
---


# Question
Title: Understanding this explanation about Big O notation
I'm trying to learn the Big O Notation...and I got a bit confused by this article:

https://brilliant.org/practice/big-o-notation-2/?chapter=intro-to-algorithms&pane=1838

where it stands that f(x) = 4x and g(x) = 10x, (...), and that one could look at the Big O Notation by dividing f(x) by g(x): 10x/4x

Shouldn't it be 4x/10x instead in this very example? (since f(x) = 4x and g(x) = 10x) Or is just me who got it all wrong?...

Kind regards,

c

# Answer
> 1 votes
The best way to look at big $O$ notation is the following: $f(x)$ and $g(x)$ have the same $O$ complexity if you can find a positive constants $c\_1, c\_2 \in \mathbb{R}$ such that $f(x) \leq c\_1 \cdot g(x)$ and $g(x) \leq c\_2 \cdot f(x)$ for all $x$.

So, for example $4x$ and $10x$ are both in the same complexity class because $4x \leq 1 \cdot 10x$ and $10x \leq 3 \cdot 4x$. We name the complexity class they belong to $O(x)$, because $x$ is the simplest of all expressions of the form $c \cdot x$ so we use it as a representative.

Also, one can write equalities with big $O$; $$O(4x) = O(10x) = O(x) = O(192839182x) \neq O(x^2) $$

Some basic complexity classes are (in order of complexity, from lower to higher):

* $O(log n)$
* $O(n)$
* $O(n log n)$
* $O(n^2)$
* $\ldots$
* $O(n^k)$
* $\ldots$
* $O(2^n)$
* $\ldots$

and every complexity class on this list is not equal to any other.

---
Tags: asymptotics
---


# Question
Title: Modifying Floyd–Warshall Algorithm for Vertex Weights
I was trying to modify the Floyd–Warshall's algorithm to take into account the weights over the vertices, in addition to the weight of the edges, while computing the shortest path. The length of a path from vertex A to an adjacent vertex B, Path(A,B) , is defined as:

```
     Vertex_Weight(A) + Edge_Weight(AB)

```

For a vertex A:

```
      Path(A,A) = 0

```

I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work:

> The weight on a vertex V can be added to the weights of all the outgoing edges from V. Thus new edge weight **Edge\_Weight'** is:
>
> ```
>       Edge_Weight'(AB) =  Vertex_Weight(A) + Edge_Weight(AB)
>
> ```
>
> One can transform the original graph with the vertex weights to a graph without vertex weights, where the edge weights are modified as above. The normal Floyd–Warshall can be applied now.

If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful.

# Answer
> 2 votes
"I was wondering if the Floyd–Warshall can be modified to handle this, and in particular if the following idea will work."

Yes, your cool idea works! In fact, other people have found the same cool technique of including vertex weight in the new edge weight. By the way, I would not say you have modified the Floyd-Warshall algorithm. It is better to say that you have adapted the problem brilliantly so that Floyd-Warshall algorithm can be applied flawlessly.

"If anyone could envisage a scenario where this might not work or if anyone knew of a better way, I would be thankful"

It looks like there is little chance for you to become thankful by that cause.

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


title: Average height of a BST with n Nodes

text:
# Question
Title: Average height of a BST with n Nodes
I have to find the maximum, minimum, and average height of a BST with n nodes. After doing some researching I found that the maximum height is $n-1$ and the minimum height is $\log\_2(n+1)-1$. My question is how do I get the average height of a BST with n nodes?

# Answer
> 3 votes
Ok, so we need to get a bit mathematical here. Let's first define the following quantities

* $X\_n$ height of a tree composed of $n$ nodes.
* $Y\_n = 2^{X\_n}$ is referred to as the exponential height.

One of the BST's properties is that the left subtree must contain key values less than the root. Also, the right subtree contains key values greater than the root. This property is recursive so it applies to any node. Having said that, pick any node at random, call it the $i^{th}$ node, then, the left subtree has $i-1$ elements and the right subtree has $n-i$ elements. Therefore, $$Y\_n = 2 \max (Y\_{i-1},Y\_{n-i})$$ Assuming all nodes are picked with equal probability, so picking a node $i$ has the following probability $$Pr(i) = \frac{1}{n} \quad \forall i=1\ldots n$$ Now, let us find the expected value of $Y\_n$ \begin{align} E(Y\_n) &= E\[2 \max (Y\_{i-1},Y\_{n-i})\]\\ &= 2 \sum\limits\_{i=1}^n Pr(i)E\[\max (Y\_{i-1},Y\_{n-i})\] \\ &= \frac{2}{n} \sum\limits\_{i=1}^n E\[\max (Y\_{i-1},Y\_{n-i})\] \\ &\leq \frac{2}{n} \sum\limits\_{i=1}^n E(Y\_{i-1}) + \frac{2}{n} \sum\limits\_{i=1}^n E(Y\_{n-i}) \\ &= \frac{2}{n} \sum\limits\_{i=0}^{n-1} E(Y\_{i}) + \frac{2}{n} \sum\limits\_{i=0}^{n-1} E(Y\_i) \\ &= \frac{4}{n} \sum\limits\_{i=0}^{n-1} E(Y\_i) \end{align}

Now, by induction, you can actually prove \begin{equation} E(Y\_n) \leq \frac{1}{4} C\_{n+3}^3 \end{equation} Remember that we have \begin{equation} 2^{X\_n} = Y\_n \end{equation} or \begin{equation} E(2^{X\_n}) = E(Y\_n) \end{equation} Using Jensen's inequality, we can say that \begin{equation} 2^{E(X\_n)}\leq E(Y\_n) \end{equation} But \begin{equation} E(Y\_n) \leq \frac{1}{4} C\_{n+3}^3 \end{equation} So \begin{equation} 2^{E(X\_n)}\leq E(Y\_n) \leq \frac{1}{4} C\_{n+3}^3 \end{equation} And note that \begin{equation} C\_{n+3}^3 = \frac{(n+3)!}{3!n!} = \frac{(n+3)(n+2)(n+1)}{6} \sim O(n^3) \end{equation} So \begin{equation} 2^{E(X\_n)} \leq O(n^3) \end{equation} Take log on both sides, \begin{equation} E(X\_n) \leq O(\log n^3) = O(3 \log n) = O(\log n) \end{equation} Therefore, the average BST height is of order $O(\log n)$, which is what you'd expect out of Binary stuff, right ?

---
Tags: binary-trees, discrete-mathematics, binary-search-trees
---


title: Is Euclidean TSP strongly NP-hard

text:
# Question
Title: Is Euclidean TSP strongly NP-hard
Is Euclidean TSP strongly NP-hard? What I mean is if it is NP-hard with weights specified in unary?

Can someone provide a reference?

# Answer
> 1 votes
Yes, Papadimitriou in his "The Euclidean Traveling Salesman Problem Is NP-complete" paper reduces from Exact Cover to Euclidean TSP.

All the coordinates of the points are of polynomial magnitude.

And the required precision for the $L\_0$ value in page 243 is to be able to distinguish between $a$ and ${(a^2+1)}^\frac12$. And near the end of page 241, he wrote "An adequate value of $a$ is 20." So the required precision is finite. Since you only have $n(4a + 13 + 2^\frac12)$, that would only magnify the difference.

All the page numbers above are in the proceedings containing his paper and can be seen once you have downloaded the paper.

---
Tags: np-complete, traveling-salesman
---


# Question
Title: Inference of a measure for a decreasing chain
Set $I\_n = \\{0,\ldots,n-1\\}$.

Given integers $v\_0,\dots,v\_{n-1} \in \mathbb{N}$, find an integer $t\>0$, a map $f:\mathbb{N} \times I\_n \to \mathbb{N}^t$, and a well-founded order $\>\_t$ on $\mathbb{N}^t$ such that: $$\forall i \in I\_n, m \in \mathbb{N}. f(m,i) \>\_t f(m+v\_i,i+\_n 1)$$

where $+\_n$ is addition in $\mathbb{Z}\_n$ and $v\_0+\dots+v\_{n-1}\<0$. Is there an efficient algorithm to do that?

**Explanation and motivation**

The directed weighted graph $0 \stackrel{v\_0}\to 1 \stackrel{v\_2}\to \ldots \stackrel{v\_{n-2}}\to n-1 \stackrel{v\_{n-1}}\to 0$ describes how a magnitude $m \in \mathbb{N}$ varies. For transition $i \stackrel{v}{\to} j$, $m$ gets updated with $m+v$. It must hold that $\sum\_{i = 1}^n v\_i \< 0$. Consider the following problem:

Give an assignment of values in $\mathbb{N}^t$ to nodes and an order that decreases at each transition. That is, if $\text{nodes} = \\{0,\ldots,n-1\\}$, I want to build a map $f:\mathbb{N} \times \text{nodes} \to \mathbb{N}^t$ with $t \> 0$ satisfying: $\forall i \in \text{nodes}. f(m,i) \>\_t f(m+v\_i, i +\_n 1)$ where $\>\_t$ is a well-founded order on $\mathbb{N}^t$.

Is there an algorithm that can built such an $f$ and $\<\_t$?

**Example (my try):**

Assume you have the following chain is given:

$1 \stackrel{+3}{\to} 2 \stackrel{-2}{\to} 3 \stackrel{-2}{\to} 1$

In this case, $+3-2-2 = -1 \< 0$.

Let's start at 1.

Since $m$ increases, I will annotate measure $(2,m)$ in $1$ and measure $(1,m)$ in $2$ so that lexicographic order decreases.

At $2$, measure $m$ decreases so I can leave annotation $(1,m)$ as it was.

At $3$, measure $m$ decreases so I can copy annotation $(1,m)$ from $2$.

Coming back to $1$, I have a problem, since I had annotated $(2,m)$ before, but now I have annotated $(1,m)$ and these are clearly different measures.

Can you help me out of this problem?

**Note on the meaning of the specification**

Just to make sure the specification matches my needs, the problem tries to model how some quatity $m$ varies in a loop of successive function applications. The functions form a loop that ends at $0$. It is guaranteed that when traversing the whole loop, quantity $m$ decreases (according to the variations $v\_i$). In each function one have to check that in the next call certain measure $f$ (depending on the parameter $m$) decreases.

# Answer
> 3 votes
Yes. This is possible. $t=1$ suffices. Take

$$\begin{align\*} f(m,n-1) &= Cm + D\\ f(m,n-2) &= f(m+v\_{n-2},n-1) + 1 = Cm + C v\_{n-2} + D + 1\\ f(m,n-3) &= f(m+v\_{n-3},n-2) + 1 = Cm + C v\_{n-3} + C v\_{n-2} + D + 2\\ &\ldots\\ f(m,i) &= Cm + C v\_{i} + \dots + C v\_{n-2} + D + n-1-i \end{align\*}$$

where we take the constant $C\>0$ to be at least $n$; we choose a constant $D\>0$ that's large enough that the output of $f$ is always positive; we take $t=1$; and we use the standard order on $\mathbb{N}$. Then you can verify that this satisfies all the conditions.

How do you find this? As always, start with small cases. Start with $n=2$ and see what has to hold of $f$, and try to construct a $f$ that meets the conditions. (One way to ensure that $x\>\_t y$ is to set $x=y+1$; in the construction above, I used that to construct $f$ that satisfies the condition by definition.) Then try $n=3$. Then generalize. The above definition follows as a straightforward consequence of your requirements; if you choose elements of $f$ in the right order, it becomes routine to fill out the truth table of $f$ so all the requirements are met.

# Answer
> 0 votes
I have to post this answer since it is probably what I will implement in practice because it is more extendable to other settings and it can be well encoded in my system by logical formulas. However, I will still refer to D.W.'s approach since is mathematically more appealing and for me as a mathematician opens a lot of questions.

Here is the approach:

One begins with a measure $(m,0)$ at node $0$. And in subsequent nodes, makes reference to the decreased measure $m'$ which is obtained encoding the semantic meaning of transversing the loop one time ($m'$ is an expression, not an explicit number). More precisely, $m'$ will be different at each node: node $0$ takes into account all the loop, node $1$ takes into account the loop from $1$, and so on.

I was probably confused by the fact that my system failed with some of these instances. The problem is that measures need to be positive and again as in the case of D.W. we have to introduce a linear shift that gets all inferred measures to be positive.

---
Tags: graphs, functional-programming, order-theory, termination
---


# Question
Title: Why is the sequence "3,3,4,5,2" considered a bitonic sequence?
Why do we consider the sequence **"3,3,4,5,2"** a *bitonic* sequence?

In the sequence, "3,3,4,5,2", the sequence is

* constant for "3,3",
* increasing for "4,5", and
* decreasing for "5,2".

# Answer
Bitonic sequence is defined for example for parallel sort, as non-decreasing and then non-increasing sequence, to allow duplicates.

See here: Bitonic sequence. Also Wikipedia article about Bitonic sorter shows the same definition which is, afaik, the common one.
> 7 votes

# Answer
The words "increasing" and "decreasing" are used in inconsistent ways. Probably, you're assuming one definition while the author of the text that's confusing you is using the other. Say that the sequence $a\_1, \dots, a\_n$ is

* *type A* if $a\_1\leq a\_2\leq \dots\leq a\_n$;
* *type B* if $a\_1\<a\_2\<\dots\<a\_n$.

The problem is that

* some people refer to type A sequences as "nondecreasing" and type B sequences as "strictly increasing", which is unambiguous;
* some people call type A "nondecreasing" and type B "increasing";
* some people call type A "increasing" and type B "strictly increasing".

This means that the term "increasing" is ambiguous because some people use it for type A and some people use it for type B. (And ditto for variants of "decreasing".)

The same problem occurs, though to a much smaller extent; with the terms "nonnegative", "positive" and "strictly positive": the first definitely means $\geq 0$, the last definitely means $\>0$; the majority of people use "positive" to mean $\>0$ but a few use it for $\geq 0$. (And ditto for variants of "negative".)
> 11 votes

---
Tags: algorithms, parallel-computing
---


title: Markov Inequality in graph theory

text:
# Question
Title: Markov Inequality in graph theory
Fix an optimal solution G∗ to k-Cycle-Free Subgraph. Partition the vertex set V of G randomly into two subsets, A and B, each of size n/2, and remove edges internal to A or B. In expectation, the fraction of edges in G∗ that remain after this process is 1/2. ***With probability at least 2/3 the fraction of edges in G∗ that remain is at least 1/4; here we apply the Markov inequality on the fraction of edges inside A and B***.

I know Markov inequality in context of probability theory I don't know what it means here.

APPROXIMATING SUBGRAPHS WITHOUT SHORT CYCLES

# Answer
Let $X$ denote the fraction of remaining edges. We know that $0 \leq X \leq 1$ and $\mathbb{E}\[X\] = 1/2$. Let us define $Y = 1 - X$, which is the fraction of edges inside $A$ and $B$. This is a non-negative random variable whose expectation is $\mathbb{E}\[Y\] = 1/2$. According to Markov's inequality, $$ \Pr\[X \< 1/4\] = \Pr\[Y \> 3/4\] = \Pr\[Y \> \tfrac{3}{2} \mathbb{E}\[Y\]\] \< \frac{2}{3}. $$ Therefore $\Pr\[X \geq 1/4\] \> 1/3$.

Let us show that the similar inequality $\Pr\[X \> 1/4\] \geq 1/3$ is tight, that is, there exists a random variable satisfying $0 \leq X \leq 1$, $\mathbb{E}\[X\] = 1/2$, and $\Pr\[X \> 1/4\] = 1/3$. Indeed, take $\Pr\[X = 1/4\] = 2/3$ and $\Pr\[X = 1\] = 1/3$, and notice that $$ \mathbb{E}\[X\] = \frac{2}{3} \cdot \frac{1}{4} + \frac{1}{3} \cdot 1 = \frac{1}{6} + \frac{1}{3} = \frac{1}{2}. $$ In a similar way, one can show that $\Pr\[X \geq 1/4\]$ can be arbitrarily close to $1/3$.
> 0 votes

---
Tags: algorithms, graphs
---


# Question
Title: Abstract Data Types and their Implementation
I wanted to know if there is good resource to learn about the ADTs like set ADT, list, array, boolean etc and their implementation.

# Answer
I would say Algorithms by Robert Sedgewick and Kevin Wayne is a classic book which explains quite well the basics of these concepts.

However you could also find a lot of resources on the web for free.
> 1 votes

---
Tags: algorithms, data-structures, lists, data-sets, abstract-data-types
---


# Question
Title: Using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant?
I would like to get some opinions about using a context free grammar to generate sample utterances for Amazon Alexa/Google Assistant skills.

When developing these skills one has to provide a large number of sample utterances, i.e. sentences with which a user could try to invoke a particular feature of the skill. So when the skill is about ordering chocolate I would have to provide sentences like...

```
i would like to buy chocolate
i would like to order chocolate
we would like to buy chocolate
we would like to order chocolate

```

...and so on. the number of these sentences tends to grow almost exponentially, yet even with hundreds of them they still often become the bottleneck of the entire skill because users tend to come up with new formulations that weren't anticipated.

There are some tools available that can generate these sentences from simple patterns, i.e. this

```
{i|we} would like to {buy|order} chocolate

```

would produce the four variations given above. The drawback of this approach is that usually not all permutations of the pattern are valid (in most cases it is only a small subset of them) and one would thus need another "grammar" on top of these patterns to tell which are. The patterns are also not standardized and thus tied to one particular tool.

So I was looking for a better way to generate these sample utterances, and came across an approach that generates sentences from a context free grammar. This looks very promising to me, and in a small test script I was able to generate a large number of sentences from a very small grammar, with limitations on the sentences structure that I would have been able to include in the patterns of the existing tools.

I am however not a exactly an expert in Theoretical Computer Science and would like to ask a few questions before exploring this further:

* My understanding is that a CFG is basically a "pattern" in the form of a tree. It would thus work similar to the patterns described above, but with the additional benefit of having the rules about which permutations of variables are legal embedded in the pattern itself. Is that correct?
* If the CFG really is just a more complex pattern that would also mean that this approach (generating sentences from a CFG) can not produce grammatical variations of the generated sentences, e.g. it would not be able to generate pluralized forms like `i would like to see _my_ shopping cart` -\> `we would like to see _our_ shopping cart`. Is that right?
* More generally: From the hierarchy of formal languages, is a CFG really the best solution to this problem, our should I experiment with other types of grammars?

As I've said, it is entirely possible that I am misunderstanding some fundamental things about CFGs here, I am really just looking for some external feedback on this idea before investing more time in it. Thanks!

# Answer
> 1 votes
I don't think that will be effective. I don't recommend this approach. I think there's a significant risk that the machine learning will just learn to handle those specific synthetic variants, but not get any better at handling real speech. It might even get worse, if you cause the ML to overfit to your synthetic variants.

The problem is that real speech has a lot of variety in how people express things. Your synthetic examples are not going to capture that variety. Training machine learning on synthetic examples that aren't representative of what it will see during deployment is not likely to be effective. I suggest you try to obtain more realistic data, even if it can't be easily programmatically generated.

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


# Question
Title: What is the name of a rooted tree whose nodes may have edges to their descendants?
A tree is a special kind a graph.

However, I came across a data structure which is a like a rooted tree, but where nodes are authorized to have direct links to any of their descendants. Shortcuts if you will.

This is not a tree anymore.

This is a specialized DAG that has more restriction. That is, it has a single root (or source)

Does this type of graph have a name?

CLARIFICATION:

By 'tree', I'm referring to the tree data structure, not a tree in graph theory. It seems crazy to me that such related objects have the same name even though they don't mean the same thing. The tree data structure is always rooted but there are rooted DAG that are not trees.

{1→2, 2→3, 1→3, 4→2} doesn't qualify because 4→2 is an edge toward an ancestor, not a descendant. {1→2, 1→3, 2→4, 3→4} doesn't qualify.

{1→2, 2→3, 1→3} and {1→2, 1→3, 2→4, 3→5, 3→6, 1→4, 1→6} both qualify.

# Answer
This answer does not have a suggestion as to what existing names we might have. Rather, it is about what names are not appropriate.

To be clear, the OP talks about a graph that is a rooted tree with possibly extra edges from some nodes to its descendants. Let us call this kind of graph "Clement directed acycle graph" or, in short, "**Clement DAG**" for the lack of a better concise name (Clement is the OP's username).

The simplest example of Clement DAG that is not a tree is a graph on vertices $\\{1,2,3\\}$ with edges $\\{1\to 2,\ 2\to 3,\ 1\to 3\\}$.

One might be tempted to think "a Clement DAG" is none other than "a rooted directed acycle graph"(**rooted DAG**) or, what is equivalent, "a directed acyclic graph with a single source". Indeed, **a Clement DAG is always a rooted DAG. However, a rooted DAG is not necessarily a Clement DAG**! Here is an example given by David Richerby. Let $G$ be a graph vertices $\\{1,2,3,4\\}$ with edges $\\{1\to 2,\ 1\to 3,\ 2\to 4,\ 3\to 4\\}$. $G$ has a single root, $1$. If $G$ is a Clement DAG, $G$ must be a tree since it has no extra edge that connects any node to its descendants others than its children. However, $G$ has a cycle.
> 3 votes

# Answer
I'm not aware of any standard term. The graphs that you describe are subgraphs of the transitive closure of a tree, if that's of any help to you, but one wouldn't want to use that phrase twenty times in a paper.

But... as Pål GD alludes to in a comment, *every* DAG on $n$ vertices is a subgraph of the transitive closure of the $n$-vertex directed path. So this answer is a bit of a fail, really.
> 3 votes

---
Tags: graphs, data-structures, trees, graph-traversal, dag
---