# Question
Title: simple uniform hashing: unclear definition of probability
I am trying to understand the assumption of Simple Uniform Hashing (SUHA) as e.g., in CLRS textbook; or other courses about hashing.

The usual description given to SUHA is (cf. CLRS):

> "we shall assume that any given element \[i.e., key\] is equally likely to hash into any of the m slots, independently of where any other element has hashed to. We call this the assumption of simple uniform hashing."

However this is quite informal, and thus I don't fully understand it. My understanding is that the assumption supposedly means that

$ Pr\[h(k)=\ell\]=1/m\\,$, for any given key $k$ and slot in the table $\ell=0,\ldots,m-1$, where $m$ is the number of slots in the table. But since given a key $k$ the deterministic hash function $h$ is fixed on $k$, there is **no** probability distribution here!

Perhaps it is meant here that $k$ is a random variable distributed uniformly over all keys?

> **Question**: what is the distribution the probability $ Pr\[h(k)=\ell\]=1/m\\,$ is defined over in SUHA?

---

## EDIT:

My understanding is the SUHA is an (idealized) assumption that formally means that the probability $Pr\[h(k)\]$ is the probability of the *event* of inserting a key to the table *nevertheless the time of insertion (it might be the first key I insert or the last one)*.

In other words, the **sample space** of probability $\Omega$ is

$\Omega:=($the set of all \[ordered\] sequences of insertions to the hash table$)$.

The probability **event** $h(k)=\ell$ is thus the set of all \[ordered\] sequences of insertions to the hash table in which the $n+1$th insertion hashes to $\ell$, where $n+1$ is the \`\`current'' insertion that I'm analyzing and where $n$ is the current number of keys in my hash table.

In SUHA we shall *also* assume that $h(k)=\ell$ *for every $n$ (the current position of insertion in the sequence)*; namely, we assume that the event $h(k)=\ell$ is completely independent of the sequence.

> To sum up the answer: the probability $Pr\[h(k)=\ell\]$ is taken over all possible ordered sequences of insertions to the hash table.

# Answer
First, the outcome of a situation being deterministic doesn't mean we will necessarily assign a probability of $1$ or $0$ to it. If I say I'm going to flip a coin, but it is actually a double-sided coin meaning both sides are heads or both sides are tails, the probability that it comes up heads is still $0.5$. Indeed, with respect to classical mechanics, the outcome of a normal coin flip is a deterministic function of the state of the universe, and even quantum mechanics would at best predict near certainty of the classical outcome. But you are correct, that if we knew $h$ and $k$ and $\ell$, then $h(k)=\ell$ would be either a logical tautology or a logical contradiction, and thus of probability $1$ or $0$ respectively.

We could consider any of $h$, $k$, or $\ell$ to be random variables, but the most natural choice would be $k$. I'll write $K$ for the random variable of the keys and reserve $k$ for some particular key. We have $$P(h(K)=\ell)=P(K\in h^{-1}(\ell)) = \mu\_K(h^{-1}(\ell))$$ where $\mu\_K$ is the probability measure corresponding to $K$. The simple uniform hashing assumption (SUHA) states that $$\mu\_K(h^{-1}(\ell))=\frac{1}{m}$$ for every $\ell\in\\{0,\dots,m-1\\}$. This is simply a *constraint* on the probability measure $\mu\_K$. There is no assumption that $K$ is "uniformly distributed" in any (other) sense. $K$ could be wildly "non-uniform" and still satisfy SUHA. Indeed, it would *have* to be for some hash functions, $h$.

For example, let's say $m=2$ and $h^{-1}(0)=\\{k\_0\\}$ and thus $h^{-1}(1)=X\setminus \\{k\_0\\}$ where $X$ is the domain of $h$. Let's further say $|X|=101$. Then for this $h$ to satisfy SUHA, it must be the case that $P(K=k\_0)=\frac{1}{2}$. For $k\in X\setminus \\{k\_0\\}$, it could be the case that there's a $k\_1\in X\setminus \\{k\_0\\}$ such that $P(K=k\_1)=\frac{1}{2}$ and thus if $k\neq k\_1$ then $P(K=k)=0$. Or maybe, $P(K=k)=\frac{1}{200}$ for any $k\in X\setminus \\{k\_0\\}$. In fact, *any* distribution over the elements of $X\setminus \\{k\_0\\}$ that sums to $\frac{1}{2}$ will suffice.

Typically, we would specify a distribution for $K$ and then SUHA would constrain what $h$ could be. The point is that the hash function is "well matched" to the distribution of keys whatever that is. There is no sense in stating a hash function satisfies SUHA without specifying the distribution of keys, but we *can* say a pair of a hash function and a distribution of keys satisfy SUHA while giving the details of neither. This is all that is needed to prove many results about hashing. We don't want to limit ourselves to only talking about "uniformly" distributed keys. A hash table will still gave the same performance guarantees for "non-uniformly" distributed keys as long as the hash function is chosen to "compensate" for the "non-uniform" distribution, i.e. to satisfy SUHA.
> 5 votes

# Answer
The way I think about Simple Uniform Hashing is like this:

Since CLRS assumes the universe of keys $U$ fixed, it is also natural to assume that the probability distribution of keys is also fixed by the problem at hand. In fact, this is what CLRS say on page 274 (3rd edition) in the context of open-addressing:

> Of course, a given key has a unique fixed probe sequence associated with it; what we mean here is that, considering the probability distribution on the space of keys and the operation of the hash function on the keys, each possible probe sequence is equally likely.

So let $$K: S \to U$$ be the random variable of choosing a key with its own probability distribution (which is not assumed uniform(!): some keys might be chosen much more often than the other ones).

Then if one composes $K$ with the hash function (which is a deterministic object) $$h: U \to \\{0,1,...,m-1\\},$$ one gets a new random variable$$h(K): S \to \\{0,1,...,m-1\\}$$ that would have its own probability distribution showing how often certain hash-values would be used in our experiment of randomly choosing keys.

Then the hash function $h$ satisfies SUHA when $h(K)$ has $Unif \ \\{0,1,...,m-1\\}$ distribution.

For example, if $U = \\{k\_1, k\_2,k\_3,k\_4 \\}$ consists of only four keys with $$P(K=k\_1) = P(K=k\_2) = 1/3, \ P(K=k\_3) = P(K=k\_4) = 1/6, $$ the appropriate hashing function with $m=2$ slots would e.g. be $$h(k\_1)=h(k\_3)=0, \quad h(k\_2)=h(k\_4)=1,$$ because then $$P(h(K)=0)=1/2, \quad P(h(K)=1)=1/2.$$

Certainly, for some configurations of $U, K$ and $m$ there might be no hash function $h$ satisfying SUHA. Take e.g. $U=\\{k\_1, k\_2, k\_3 \\}$ with $$P(K=k\_1)=2/3, P(K=k\_2)=P(K=k\_3)=1/6,$$ and $m = 2$. There is no way to evenly spread out $k\_1,k\_2,k\_3$ in just two slots - if you set $h(k\_1)=j$, then $$P(h(K)=j) \geq 2/3$$no matter what $h$ was.
> 2 votes

---
Tags: hashing
---


# Question
Title: Why does the converse of the clock condition imply that any two concurrent events occur at the same time?
In Lamport's paper, Time, Clocks, and the ordering of Events in a Distributed System he says that the converse of the clock condition does not hold and if it did, we could expect concurrent events to occur at the same time. I am not sure how he arrives at this conclusion.

The Clock Condition is:

For any events a, b in a distributed system: if a -\> b then C(a) \< C(b).

The converse does not hold: if C(a) \< C(b) then a -\> b.

Where C(n) assigns a logical clock number to any event in the system. Logical clock numbers monotonically increasing values for each process in the system and two conditions hold in order for partial orderings given that the clock condition is true:

1. if a and b are both events in a process P\_i and a comes before b, then C\_i(a) \< C\_i(b)
2. if a is a sending event in P\_i and b is a receiving event in P\_j then C\_i(a) \< C\_j(b).

Intuitively I can see why the converse does not hold. It is possible in the system of logical clocks that C(a) \< C(b) when we do not have a partial ordering that guarantees the relation a -\> b. But I have no clue why the converse being true would imply that any two concurrent events occur at the same time.

# Answer
> 1 votes
Assume the clock condition AND its converse: $$C(a)\lt C(b) \Rightarrow a \rightarrow b \tag{\*}\label{\*}$$

Next, take note that $\neg(a \rightarrow b)$ implies either $b \rightarrow a$ or $a \nrightarrow b$ (i.e. if '$a$ does NOT happen before $b$' then either '$b$ happens before $a$' or they are concurrent events).

Now, since the implication $\eqref{\*}$ is (assumed) true, its contrapositive must also be true: $$\neg(a \rightarrow b) \Rightarrow C(a)\geq C(b)$$

Applying our negation rule, we find either $b \rightarrow a \Rightarrow C(a)\geq C(b)$ (which reduces to the clock condition) or $$a \nrightarrow b \Rightarrow C(a)\geq C(b)$$

Lamport is only interested in the latter case: "...we cannot expect the converse condition to hold as well, since that would imply that any two $\mathbf{concurrent}$ events must occur at the same time."

To show this, remember Lamport said when $a,b$ are concurrent then both $a \nrightarrow b$ and $b \nrightarrow a$ so $$b \nrightarrow a \Rightarrow C(b)\geq C(a)$$ The last two equations imply if $a$ and $b$ are concurrent, $C(a)=C(b)$.

To derive the contradiction, take any two events $a, b$ concurrent but on separate processes. Then their clock numbers must be the same. Now if there is another concurrent event before or after $a$ (on the same process), then it too must have the same clock number as $b$ and therefore $a$. But that contradicts the clock condition (e.g. see condition C1 in the paper).

---
Tags: distributed-systems, clocks
---


# Question
Title: Algorithm To Compute The Gaps Between A Set of Intervals
**Problem**

Given a set of intervals with possibly non-distinct start and end points, find all maximal gaps. A gap is defined as an interval that does not overlap with any given interval. All endpoints are integers and inclusive.

For example, given the following set of intervals:

$\\{\[2,6\], \[1,9\], \[12,19\]\\}$

The set of all maximal gaps is:

$\\{\[10,11\]\\}$

For the following set of intervals:

$\\{\[2,6\], \[1,9\], \[3,12\], \[18,20\]\\}$

The set of all maximal gaps is:

$\\{\[13,17\]\\}$

because that produces the maximal gap.

**Proposed Algorithm**

My proposed algorithm (modified approach taken by John L.) to compute these gaps is:

1. Order the intervals by ascending start date.
2. Initialise an empty list `gaps` that will store gaps
3. Initialise a variable, `last_covered_point`, to the end point of the first interval.
4. Iterate through all intervals in the sorted order. For each interval `[start, end]`, do the following.
    1. If `start > last_covered_point + 1`, add the gap, `[last_covered_point + 1, start - 1]` to `gaps`.
    2. Assign `max(last_covered_point, end)` to `last_covered_point`.
5. Return `gaps`

I have tested my algorithm on a few cases and it produces the correct results. But I cannot say with 100% guarantee that it works for every interval permutation and combination. Is there a way to prove this handles every permutation and combination?

# Answer
> 3 votes
The key to prove your algorithm is correct is to find enough invariants of the loop, step 4 so that we apply use mathematical induction.

---

Let $I\_1, I\_2, \cdots, I\_n$ denote the sorted intervals. When the algorithm has just finished processing $I\_i$, we record the values of `gaps` and `last_covered_point` as $\text{gaps}\_i$ and $\text{last\_covered\_point}\_i$ respectively.

Let us prove the following proposition, $P(i)$, for $i=1, 2, \cdots, n$.

> $\text{gaps}\_i$ is the set of all maximal gaps for $I\_1, I\_2, \cdots, I\_i$ and $\text{last\_covered\_point}\_i$ is the maximum of all right endpoints of $I\_1, I\_2, \cdots, I\_i$.

When $i=1$, $\text{gaps}\_1$ is the empty set and $\text{last\_covered\_point}\_1$ is the right endpoint of $I\_1$. So $P(1)$ is correct.

For the sake of mathematical induction, assume $P(i)$ is correct, where $1\le i\lt n$. Let $I\_{i+1}=\[s, e\]$. There are two cases.

1. If $s\gt\text{last\_covered\_point}\_i+1$, then $$\text{gaps}\_i\cup\[\text{last\_covered\_point}\_i +1, s-1\]=\text{gaps}\_{i+1}.$$
Let $m$ be any point between the start point of $I\_1$ and the maximum of all right endpoints of $I\_1, I\_2, \cdots, I\_{i+1}$. Suppose $m$ not covered by any of $I\_1, I\_2, \cdots, I\_{i+1}$.

* If $m\le\text{last\_covered\_point}\_i$, the induction hypothesis says that $m$ is covered by some interval in $\text{gap}\_i$.
    * Otherwise, $m\gt\text{last\_covered\_point}\_i$. Since $m$ is not covered by $I\_{i+1}$, we know $m\<s$. So $m$ is covered by $\[\text{last\_covered\_point}\_i +1, s-1\]$.

In both cases, $m$ is covered by some interval in $\text{gaps}\_{i+1}$. Since $\text{last\_covered\_point}\_i$ is the largest point covered by one of $I\_1, I\_2, \cdots, I\_i$ and $s$ is the smallest point covered by $I\_{i+1}$, $\[\text{last\_covered\_point}\_i +1, s-1\]$ is a maximal gap.
2. Otherwise, we have $s\le\text{last\_covered\_point}\_i$+1. We can also verify that $\text{gaps}\_{i+1}=\text{gaps}\_{i}$ is the set of all maximal gaps for $I\_1, I\_2, \cdots, I\_{i+1}$.

Finally, since step 4.2 says $\text{last\_covered\_point}\_{i+1}=\max(\text{last\_covered\_point}\_i, e)$ and $\text{last\_covered\_point}\_i$ is the maximum of all right endpoints of $I\_1, I\_2, \cdots, I\_i$, $\text{last\_covered\_point}\_{i+1}$ is the maximum of all right endpoints of $I\_1, I\_2, \cdots, I\_{i+1}$.

So, $P(i+1)$ is correct. $\quad\checkmark$.

# Answer
> 4 votes
I'd like to propose a quite simple algorithm as well. The idea is this: we're going to place open and close parentheses on the number line at the boundaries of each interval. For example, for the intervals $(1,5), (2,7), (9, 10)$, the number line would look like this:

```
1 2 3 4 5 6 7 8 9 10
( (     )   )   ( )

```

Then we'll just scan left to right, counting parentheses. When all the parentheses get closed, we start a gap. Note in particular that in the above diagram, we have *lost* the information about which close parenthesis is paired with which open parenthesis -- because it doesn't actually matter. So:

1. Convert each interval $(a,b)$ to pairs $(a,\mathtt o),(b,\mathtt c)$. ($\mathtt o$ and $\mathtt c$ are for *open* and *close*, respectively.)
2. Sort all the pairs you get from this process. (When sorting, use lexicographic ordering and $\mathtt o \< \mathtt c$.)
3. Iterate through them, keeping a counter that starts from $0$.
    * When you see a pair with $\mathtt o$ in the second part, increment the counter.
    * When you see a pair with $\mathtt c$ in the second part, decrement the counter.
    * When you decrement the counter, if that causes it to drop to $0$, then look at the next element of the list to decide what to do; empty list means you're done, otherwise if the next pair's first part is just one bigger than the current one's you do nothing, and in the last case you record a maximal gap between the current end point and the next open point.

---
Tags: algorithms, intervals
---


# Question
Title: Another version of the 3-coloring decision problem?
Given a graph $G$, is there a 3-coloring with colors $c1$, $c2$ and $c3$ such that at most $k$ nodes are given the color $c1$ and that no two adjacent nodes are given the same color?

Is there a decently fast algorithm to solve this? My only solution is to go through every subsets of size $1$ to $k$ and remove those nodes and check if the graph is bipartite. I am also not sure if this runs in polynomial time.

# Answer
> 2 votes
Note that when $k$ is a fixed constant (that is, $k$ is not part of the input, for example $k = 17$ ), then the problem is easy. Indeed, in this case, your suggestion works because $n \choose l$ is polynomial in $n$, for every $l\leq k$. Also, checking whether a graph is bipartite can be done in polynomial time.

If $k$ is part of the input, then your problem is harder than the NP-complete *vertex-deletion graph bipartization* problem. The later problem is defined as follows. Given a graph $G$ and an integer $k\geq 0$, find a subset of at most $k$ vertices such that removing these vertices results in a bipartite graph.

To see why your problem is harder, assume that you have indeed succeeded in coloring a graph with $c\_1, c\_2$ and $c\_3$, where at most $k$ vertices are colored with $c\_1$. Then, removing the vertices that are colored with $c\_1$ leaves us with a subgraph colored with $c\_2$ and $c\_3$, and thus the remaining subgraph has to be bipartite as two vertices with same color cannot be neighbors.

The vertex-deletion graph bipartization problem is known to be NP-complete even when restricted to planar graphs. See here.

---
Tags: graphs, decision-problem, colorings
---


# Question
Title: Number of vertices of a graph in vertex cover of size $m$
Let $G$ have a vertex cover of size at most $m$ and let the degree of $G$ be bounded by $k$. Then $G$ has at most $m(k+1)$ vertices.

Note: Remove all vertices of degree $0$.

---

Answer:

The idea is to have $m$ graphs like the below one.

But how can I prove this proposition formally?

Thank you in advance for your answers.

# Answer
Consider the graph $G=(V, E)$, where each vertex in $G$ has at most $k$ neighbours. Let $C\subseteq V$ be a vertex cover of size at most $m$. For a vertex $v\in C$, let $c(v) = \\{v\\} \cup \\{ u\in V: \\{u, v \\}\in E\\}$, that is, $c(v)$ is the set of vertices that are covered by the vertex $v$ (including $v$ itself).

*A side note: the subgraph induced by the vertices in $c(v)$, for any $v$, is a "star" graph (similar to the one you attached, yet the number of vertices that are neighbours of $v$ in this subgraph can be strictly less than $k$). The idea is to consider star graphs corresponding to the vertices in $C$, and then use the union bound for sets.*

Now $C$ being a vertex cover implies that $\bigcup\limits\_{v\in C} c(v) = V$. This is easy, yet we prove it for completentss: the $\subseteq$-containment is trivial. The other direction follows as for every vertex $v\in V$, one of the following holds:

* $v\in C$: in this case, as $v\in c(v)$, we have that $v\in \bigcup\limits\_{v\in C} c(v)$.
* there is $u\in C$ such that $\\{u, v\\}\in E$: in this case, as $v\in c(u)$, we have that $v\in \bigcup\limits\_{v\in C} c(v)$.

Finally, the following holds $$ |V| = |\bigcup\limits\_{v\in C} c(v)| \leq \sum\limits\_{v\in C} |c(v)| \leq |C|\cdot max\_{v\in C} (|c(v)|) \\\leq |C|\cdot max\_{v\in C}(degree(v) + 1) \leq |C|\cdot (k + 1) \leq m\cdot(k+1)$$
> 1 votes

---
Tags: graphs, vertex-cover
---


# Question
Title: Time complexity of a recursive function which generates all combinations of an array
The following function **getCombinations**, is a recursive function that can be used to generate all combinations of an array. How exactly can we find the time complexity of this function? I would appreciate the workings or simply an idea about how to approach this. Thanks in advance

```
function getCombinations(chars) {
  var result = [];
  var f = function(prefix, chars) {
    for (var i = 0; i < chars.length; i++) {
      result.push(prefix + chars[i]);
      f(prefix + chars[i], chars.slice(i + 1));
    }
  }
  f('', chars);
  return result;
}

```

# Answer
Denote by $T(n)$ the running time of your function on an input of length $n$, assuming that all operations are $O(1)$. Then $T(0) = O(1)$, and for $n \> 0$, $$ T(n) = O(n) + \sum\_{m=0}^{n-1} T(m). $$ Let us replace $O(n)$ with $Cn$. Then $$ T(n) - T(n-1) = Cn + \sum\_{m=0}^{n-1} T(m) - C(n-1) - \sum\_{m=0}^{n-2} T(m) = C + T(n-1), $$ and so $T(n) = 2T(n-1) + C$, implying that $T(n) + C = 2(T(n-1) + C)$. Therefore $T(n) = 2^n(T(0) + C) - C = O(2^n)$.
> 1 votes

---
Tags: time-complexity, recursion
---


# Question
Title: About the properties of the coresets in k-median clustering
I have seen two observations from the paper by Har-Peled but I do not know how to prove them (i) If $C1$ and $C2$ are the $(k, ε)$-coresets for disjoint sets P1 and P2 respectively, then $C1 ∪ C2$ is a $(k, ε)$-coreset for $P1 ∪ P2$. (ii) If $C1$ is $(k, ε)$-coreset for $C2$, and $C2$ is a$(k, δ)$-coreset for $C3$, then $C1$ is a $(k, ε+δ)$\- coreset for $C3$

Can anyone please figure it out?

# Answer
The k-medians clustering objective is defined here as

```
sum_{p in points} weight(p) distance(p, centers)

```

where `centers` is the set of `k` centers and `distance(p, centers)` is the distance to the closest center.

The first observation amounts to observing that the objective function is additive. Letting `(C1, w1)` and `(C2, w2)` be the core-sets, we consider the core-set `(C1 union C2, w1 union w2)`, which satisfies

```
sum_{p in C1 union C2} (w1 union w2)(p) distance(p, centers)
= sum_{p in C1} w1(p) distance(p, centers) + sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) sum_{p in P1} weight(p) distance(p, centers) + exp(eps) sum_{p in P2} weight(p) distance(p, centers)
= exp(eps) (sum_{p in P1 union P2} weight(p) distance(p, centers))

```

and similarly for the lower bound.

As for the second observation,

```
sum_{p in C1} w1(p) distance(p, centers)
<= exp(eps) sum_{p in C2} w2(p) distance(p, centers)
<= exp(eps) exp(delta) sum_{p in C3} w3(p) distance(p, centers)
= exp(eps + delta) sum_{p in C3} w3(p) distance(p, centers),

```

and similarly for the lower bound.
> 0 votes

# Answer
Proof of claim 1:

For every query q of k points we have:

$Cost(C1\bigcup C2,q)=Cost(C1,q)+Cost(C2,q)\\ \leq (1+\epsilon)\cdot Cost(P1,q)+(1+\epsilon)\cdot Cost(P2,q)=(1+\epsilon)Cost(P1\bigcup P2,q)$

And a similar proof can be made for the lower bound.

Claim 2 is only approximately correct for small values of $\epsilon,\delta$.

Proof of claim 2:

$Cost(C1,q)\leq (1+\epsilon)Cost(C2,q)\leq (1+\epsilon)(1+\delta)Cost(C3,q)=\\\(1+\epsilon+\delta+\epsilon\cdot\delta)Cost(C3,q)\approx (1+\epsilon+\delta)Cost(C3,q)$

And a similar proof can be made for the lower bound.
> 0 votes

---
Tags: algorithms, randomized-algorithms
---


# Question
Title: Chebyshev’s inequality problem in one exercises I can't understand if I did it right or not
This is what do I have to solve:

Byron Book: Exercise 8.3 chapter 8 Verify the use of Chebyshev’s inequality in (8.6) of Example 8.16. Show that if the population mean is indeed 48.2333 and the population standard deviation is indeed 26.5170, then at least 8/9 of all tasks require less than 127.78 seconds of CPU time.

This is how I did it :

So first I calculated: 127.78-48.23 = 79.5

Then I wrote P(X\<127) \< (26.5^2)/(79.5^2) = 0.11

I don't understand if I did it right because I did not use this part : at least 8/9 of... and I think it is important.

Can anyone help me with this ? Thank you in advance.

# Answer
> -1 votes
The exercise above is right but is missing something. You need to do 1-0.11 since you need to find the \<, not the \>. When I wrote 0.11 I have found the \> but I need the \< so 1-.. .

---
Tags: probability-theory, statistics
---


# Question
Title: Local Search Optimization Algorithms in Applied Settings -- How best to explain to applied researchers?
I realize this may be an opinion-based question, but relevant nonetheless in my opinion.

**Context:**

I have a local search optimization algorithm, ***A***.

I designed ***A*** to address a specific biological question.

***A*** returns many local optima and often gets stuck near said optima.

My target audience (biologists) don't understand this. They want a single plausible answer (the global optimum) or at least many plausible answers (local optima) with low variability. The reason for this is that biologists will need to incur high cost and large effort to reach their end goal. They feel uneasy that ***A*** returns many plausible solutions.

**Specifics**:

The problem faced by the biologists revolves around sampling. Specifically, they would like to know, given current sampling levels, how much more sampling is required to estimate genetic diversity within species.

Unfortunately, there is no means of comparison with other algorithms because this problem hasn't been thought about in a computational light before. Biologists just sample randomly in the field. Crude estimates of necessary sample sizes range from 5-10 individuals, but sometimes only 1-2 can be reasonably collected (due to say, species rarity and/or project budget).

Algorithm ***A*** suggests sample sizes 1-2 orders of magnitude larger than the crude estimate, but the variability is large.

For instance, ***A*** might suggest anywhere from 200-250 individuals should be sampled to capture 95% of existing genetic variation for a given species.

All plausible sample sizes returned by ***A*** are close to the required 95% cutoff, yet the variation in the estimates themselves is quite large.

The makes the biologists uncomfortable because it suggests that ***A*** is not very good.

One way I try to frame things is with the analogy of climbing a mountain or hill. We want to get to the top (the global optimum), but there are a lot of obstacles (local optima) in the form of ridges and valleys in the way.

**Putting this into a more CS-centric context:**

The Travelling Salesman Problem (TSP) is an NP hard problem of great theoretical interest. For this reason, TSP is often solved via local search (e.g., simulated annealing (SA) or genetic algorithms (GA)). Since both SA and GA are stochastic, they will return different routes each time the algorithm is run.

Clearly, the shortest route is targeted. If many local routes are possible, why use local search in the first place?

I realize the answer to the about question is "to get a 'good enough' solution in a finite amount of computation time". However, this doesn't fit well with applied researchers.

Put another way:

In the case of TSP, why would an airport rely on a local search algorithm to find the optimal path if this could mean wasted money and resources?

**My question**: How can we justify the use of local search algorithms with the same kind of behaviour as ***A*** to researchers in very applied fields who otherwise lack math/stats/computer science knowledge?

# Answer
The question is a bit unclear, but just to add my two cents:

* Simulated Annealing and Genetic Algorithms are not classified as ”local” optimization algorithms. They have been designed to overcome the limitations of local searches so they are usually put in the “global” optimization basket.
* The fact that they are stochastic doesn’t mean that their results are not reproducible. Standard implementations of SA and GA allow you to specify a random seed, so the optimizations are perfectly reproducible.

So you have many local optima from your algorithm. Do the “better” local optima tell you anything more than the worse ones? What is the actual, physical meaning of your optima? Is there any way you could compare your algorithm with other, established optimization procedures to assess the quality of your implementation? How many parameters (optimization variables) does your model have? Is your objective function expensive to evaluate or quick? We haven’t seen your model so it’s difficult to suggest anything about possible arguments to convince your colleagues.

That said, having an objective function full of local optima is nothing new, very many real life applications are like that. However, in almost all cases we strive for better and better optima all the time (I.e. lower objective functions in minimizations, higher for maximizations) and when we have to account for many optima (for example, for forecasting a matched model) we usually have a good, physical explanation for what we are doing.

I have to admit that your case is a bit unusual, as having orders of magnitude different optima is unheard of (at least for me). But since you haven’t provided a model nor benchmarked your algorithm against others I am afraid these is the best suggestions I can come up with.
> 1 votes

---
Tags: optimization
---


# Question
Title: How does one sketch a proof to show that the following problem is in the P Complexity Class?
I have the following problem. I do not know where to start or how I should approach this problem. I am not sure about how to prove if a problem is in a complexity class of P . I know how to do NP but P confuses me.

# Answer
> -1 votes
So to prove that the following problem is in $\mathcal{P}$, we need to construct an algorithm that solves the problem in polynomial time.

First we analyse the problem. We know that we are given $n$ boolean expressions of the form $$C\_1 \land C\_2 \land \dots \land C\_n $$ with $C\_i$ a disjunction of literals.

So the solve this problem, we reduce it by first analyzing whether each $C\_i$ is true or false. Then we save the boolean of each $C\_i$ in a list. This list will now contain the boolean of each $C\_i$. All we have to do now is to check if the conjuction of all the elements inside this list is true or false. A conjunction is false iff there exists only one element in the list that is false. Thus if we find one single element that is false, we return false, otherwise we return true.

Below you can find a high level algorithm.

Lets say that $C\_1 \land C\_2 \land \dots \land C\_n $ = $C\_{total}$

If $n$ is the number of elements in $C\_{total}$ and $m$ is the average number of elements in $C\_i$, the complexity of this algorithm is $\mathcal{O}(n\*m)$, which is polynomial.

I hope this helped you out, let me know if you have any question in the comments below.

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


# Question
Title: How to read a number from highest place value to lowest?
So we all know it's easy to read a number from lowest place value to highest. A simple algorithm would be like :

```
while(n):
    a=n%10;
    n/=10;

```

but the question is how do you read it oppositely?

for eg : 12312. must result in me getting first 1 then 2 then 3 and so on.

I don't wanna form an array or reverse the number, unless there is a way to reverse the number with constant time-complexity.

Edit : I think the question is extremely vague so I'll try to explain what I need it for.

So i've been working on optimizing my code for an algorithm to convert binary to decimal.

My algorithm is : while(n) c+=(n%2)\<\<b++ , n/=10;

But then I figured I don't need the variable b, if i could somehow start from the front then an algorithm like c=2\*c+n%2 would work.

I don't really wanna use a while loop to reverse a number as I think it would be inefficient than just having an extra variable.

An alternative that I thought of was having a float c then c=c/2+n%2 but the you'll need to know the number of digits of n. Which I could use logarithm for but I don't know that at that point if it is just better to use another variable. At its heart it is a time vs space complexity problem.

# Answer
Well, you could construct the inverse of that number. 12312 will become 21321 and then use the piece of code you wrote. So: while (n) {inverse = inverse * 10 + (a % 10), a /= 10;}.
> 1 votes

---
Tags: algorithms
---


# Question
Title: Find nth number which does not contain the digit c
This problem was given to 9-graders. We write down numbers except for the ones which contain the digit c. Find the nth such number. I looked at the indications, but the algorithm used there stumped me. I will describe in here: if $c \ne 0$, then we transform the number n - 1 (since 0 is part of the series) in the 9th base. Then each digit in the representation of the 9th base which is bigger of equal than c and smaller than 9 will be incremented with 1. The number we obtain is the number we are looking for, BUT IN BASE 10. How? Could anyone explain it to me? Also, please, be patient since I have just started Competitive Programming and I am not really that good.

# Answer
> 2 votes
Let's do it in base 3.

Here are the first 8 numbers without 2 (left column) and the first 8 numbers without 1 (right column), with zero padding:

```
000    000
001    002
010    020
011    022
100    200
101    202
110    220
111    222

```

Hopefully you can take it from here.

---
Tags: algorithms
---


# Question
Title: Determine if there's a $P_3$ as an induced subgraph in a graph $G$
> Given a graph $G$ on $n$ vertices with $m$ edges, show an algorithm that determines if there's a $P\_3$ as an induced subgraph in $G$ in $O(m+n)$ time. ($P\_3$ is the path on 3 vertices).

What I was thinking at first is that any vertex $v$ that has at least two neighbors could indicate a $P\_3$ but it wouldn't be induced since these two neighbors might be connected. So that would mean I would have to iterate over all pairs of neighbors of every vertex to determine if they're connected and I would exceed the requested runtime. Plus, that way I would actually be able to not only tell if there's a $P\_3$ but also find it, which kinda tells me this isn't what I should be doing.

Any suggestions? Or hints?

# Answer
Without loss of generality, we can assume that the graph is connected and contains at least three vertices. If the graph is a clique, it doesn't contain an induced $P\_3$. What happens if it is not a clique?
> 3 votes

---
Tags: algorithms, graphs, subgraphs, path
---


title: How is code executed in the computer

text:
# Question
Title: How is code executed in the computer
I started to learn about compilers and interpreters. But I still can't understand how program execution happens under the hood.

This is what I have understood so far.

**Compiler**

The Compiler does not run a code, instead, just converts the code into another (low-level) code. This part is clear to me.

**Interpreter**

First I thought the interpreter converts some high-level code or byte code into machine language and then executes it. But then I realized that interpreters not convert code into machine code, instead, that instruction becomes an input to the interpreter application and it activate some particular function of the interpreter, which has been already converted into the machine code.

Refer to this pseudo code. Imagine I create a programming language that is interpreted by an interpreter created by python.

```
add 5 + 3
sub 5 - 3

```

**Interpreter**

```
def add(a, b):
    print(a+b)

def sub(a,b)
    print(a-b)

# Parsing
code = [] #list of instructinos

for instruction in code:
    if instruction.command == "add":
        add(instruction.a, instruction.b)
    elif instruction.command == "sub":
        sub(instruction.a, instruction.b)
    else:
        print("incorrect instruction)

```

I am not sure whether my understanding of the interpreter is correct. If it is not, I want to know how the interpreter works internally. I mean how the interpreter executes a code without translating it into machine code.

# Answer
> 3 votes
> I mean how the interpreter executes a code without translating it into machine code

TL;DR It's the interpreter's (machine) code that executes your program's code.

To explain it better, consider these lines taken from your example:

```
def sub(a,b)
    print(a-b)

```

I think you got this point wrong: when you write `x-y` in an interpreted programming language it's because you want to know the result (for example to save it into a variable) rather than to be printed. Also, the variables of the interpreter are not mixed with the ones of the interpreted programs: for example the variables `x` and `y` could have some meaning for the interpreter and another meaning for the final program. Usually the interpreter does not make any assumption on the program's variable, it just stores them into a "memory" which is just a set of pairs \<variable\_name, value\>.

So, when there is an instruction like `z = x-y` in your program, the interpreter does the following:

1. look into the memory, retrieve the current value for `x`
2. look into the memory, retrieve the current value for `y`
3. compute `x-y` (call the result `R`).
4. set the value for `z` to be `R` in the memory.

Point 3. in the list above is crucial. If this was a real interpreter, it would not be a Python program but a compiled one, thus the implementation of point 3. would be a bunch of machine code that eventually contains a `sub` machine instruction, or some other sequence of machine instructions that together implement the subtraction.

So **every instruction of every language is executed as machine code** eventually:

* in the compiled languages the higher level instructions are translated into machine code;
* in the interpreted languages it's the interpreter's machine code to be executed.

Read the last paragraph again.

Actually you could write an interpreter using Python, but in this case it's the Python interpreter's machine code to be executed. Or it could have been any chain of pairs \<interpreted language $L\_i$, interpreter for $L\_i$\>, the point is that the last interpreter must be compiled, and thus at the very last it's just machine code to be executed because that is the only languages that the processor understands

# Answer
> 2 votes
> I mean how the interpreter executes a code without translating it into machine code.

There is a fuzzy line between interpreters and compilers, but the basic idea is this:

* If it is translated into machine code *before* being executed, it is probably a "compiler".
* If it is translated into machine code *while* being executed, it is probably an "interpreter".

That last one sounds a bit odd, but think about it analogously to human language translation. You could give a document to a translator who translates it from one language to another. A "static" translation, if you will. Or you could have someone translate as a person is speaking. This is a "dynamic" translation.

This latter option is usually what we think of as "interpretation". An "interpreter" takes some kind of high-level representation, and works out what it means in terms of the native machine's code *while the program is being run*.

---
Tags: compilers, interpreters
---


# Question
Title: How can the local feature size become arbitrarily small?
I am stuck at the following exericse:

> Let $\rho$ denote the local feature size. Draw an example where the curve C contains the line segment from $(-1, 0)$ to $(1, 0)$, but where $\rho( (0,0) )$ is arbitrarily small.

Here are the definitions that I heard in class:

> Let $C$ be a smooth closed curve in the plane, and let $x$ be a point of $C$. The local feature size $\rho(x)$ of x is the shortest distance from $x$ to the medial axis of C. (The medial axis $M(C)$ of a closed smooth curve $C$ is the locus of the centers of disks that touch $C$ at two or more distinct points.)

I do not understand how it should be possible for the local feature size to become arbitrarily small, since we are looking at *smooth* plane curves. I have tried to draw some examples, but the ones I found were always non-smooth, like the one below. (The image comes from Wikipedia's article on cusps.)

# Answer
> 3 votes
As you have suspected, it is impossible for a **simple** smooth closed curve to contain the line segment from (−1,0) to (1,0) such that its local feature size at $(0,0)$ is arbitrarily small.

On other hand, it is easy to draw a self-intersecting smooth curve with that property. Here is an example.

In fact, for every smooth curve that contains the line segment from (−1,0) to (1,0) and intersects itself at $(0,0)$, its local feature size at $(0,0)$ will be arbitrarily small.

---
Tags: computational-geometry
---


# Question
Title: Context-free grammar for all words not of the form w#w
I was asked to define a CFG for the complement of $\\{w\\#w \mid w \in \\{0,1\\}^\*\\}$ and I'm struggling to define it. I think it is quite similar to defining a CFG for the complement of $\\{ww \mid w \in \\{0,1\\}^\*\\}$, but I'm finding that the '#' really messes things up. Is the language even context-free?

# Answer
> 4 votes
If a word is *not* of the form $w\\#w$ then one of the following must happen:

* It contains no $\\#$.
* It contains more than one $\\#$.
* It is of the form $x\\#y$, where $x,y \in \\{0,1\\}^\*$ and $x \neq y$, in which case one of the following must happen:
    + $|x| \> |y|$ or $|x| \< |y|$.
    + $x\_i = 0$ and $y\_i = 1$ for some $i$, or vice versa.

The only case which is non-trivial to handle is the last one, in which case we have a word of the form $$ x\_1 0 x\_2 \\# y\_1 1 y\_2, $$ where $|x\_1| = |y\_1|$. We can split this into $$ x\_1 \\;\\; 0x\_2\\# \\;\\; y\_1 \\;\\; 1y\_2, $$ where $|x\_1| = |y\_1|$. This should make it clear how to construct a CFG for such words.

---

Altogether, we obtain the following grammar: \begin{align} &S \to A \mid B \mid C \mid D \mid E \mid F \\ &A \to 0A \mid 1A \mid \epsilon \\ &B \to A\\#B \mid A\\#A\\#A \\ &C \to A0G \mid A1G \\ &D \to G0A \mid G1A \\ &G \to 0G0 \mid 0G1 \mid 1G0 \mid 1G1 \mid \\# \\ &E \to E\_11A \\ &E\_1 \to 0E\_10 \mid 0E\_11 \mid 1E\_10 \mid 1E\_11 \mid 0A\\# \\ &F \to F\_10A \\ &F\_1 \to 0F\_10 \mid 0F\_11 \mid 1F\_10 \mid 1F\_11 \mid 1A\\# \\ \end{align}

In this grammar:

* $A$ generates words without $\\#$
* $B$ generates words with more than one $\\#$
* $C$ generates words of the form $x\\#y$ with $|x| \> |y|$
* $D$ generates words of the form $x\\#y$ with $|x| \< |y|$
* $E$ generates words of the form $x\_10x\_2\\#y\_11y\_2$ with $|x\_1|=|y\_1|$
* $F$ generates words of the form $x\_11x\_2\\#y\_10y\_2$ with $|x\_1|=|y\_1|$
* $G$ generates words of the form $x\\#y$ with $|x| = |y|$

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


title: Quicksort T(n)=2T(n/2)+n

text:
# Question
Title: Quicksort T(n)=2T(n/2)+n
In Quicksort we devide the array in to about an half (not worst case) and we have left and right sides so it is 2T(n/2), now why in the end it is T(n)=2T(n/2)+n as we may need to go over all the array to arrange it to left and right sides?

# Answer
$T(n)$ is number of comparisons done when quicksort sorts an array of length $n$.

To sort an array of length $n$, we must split it into two halves and sort the halves. To split the array, we must compare each element of the array against the pivot, which is $n$ comparisons. (Perhaps $n-1$ if the pivot is an actual array value rather than, say, an estimate of the median.) Then, we must recursively sort the two halves, which requires $T(n/2)$ comparisons each.
> 1 votes

# Answer
This last term n should, more precisely, be n-1, not n. It arises out of the fact that for splitting the array into 2 parts: one part consisting of all elements smaller than pivot and another consisting of all elements greater than or equal to pivot, we have to perform exactly n-1 (comparison) operations.
> 0 votes

---
Tags: complexity-theory, sorting
---


title: Building non-deterministic automata

text:
# Question
Title: Building non-deterministic automata
I'm trying to make non deterministic automata for specific language . I cant understand my mistake! Rules: 1){a,b,c} 2) if I have the sequence "bb" and later in the word I have the sequence "cc" so this is not possible that I have the sequence "cba" between them. Thank you !

# Answer
I have tried this question to the best of my ability. Feel free to ask for any clarification or raise any doubts in the comments.

Apart from issues like nullifying the effect of some useful transitions, the problem in your solution is that you've started out at a rejecting state, but unless the string has encountered $bb$ and then $cba$ and subsequently $cc$, it should be accepted.

I've laid out the transitions in a step wise manner, jumping about the states to "reset" the logic that proceeds to rejecting state.

**Update:** You can think about the automata as comprising of $3$ parts. q0,q1 check for first occurrence of $bb$. q2,q3,q4 detect the string $cba$. Finally, q5,q6,q7 test for the string $cc$.
> 0 votes

---
Tags: automata, nondeterminism
---


# Question
Title: how to get rows with more than 1 appearance of a specific column in relational algebra
I have a table like this:

```
PostId   |    Body    |    AuthorId
  2             b               F
  2             b               E
  2             b               C
  4             d               A
  4             d               E
  8             h               F

```

So what I want is to get all the rows that have more that 1 appearance of `PostId`. Here the result would be 2 and 4 because they appear more than 1 time. I want this in relational algebra.
I have already a relation that works just fine but in this relation I use aggregation methods and I don't really what to use `count` in my relation. I am wondering if there is a way to this with subtraction or division operators?
What I do for now is `π PostId (σ c ≥ 2 ( γ Body; COUNT(PostId)->c R2))` to get the row with more than 1 appearance of `PostId`.
Thanks in advance for help

# Answer
What about $\pi\_{PostId}(\sigma\_{\text{PostId} = \text{PostId} ~AND~ (\text{Body} \<\> \text{Body} ~OR~ \text{AuthorId} \<\> \text{AuthorId}}(R\_2 \times R\_2))$? It does not use relational division neither substraction, but I think that fits your needs (relational algebra without counting).

The idea is to make a cartesian product of $R\_2$ with itself. Hence, you have pairs of tuples of $R\_2$. Then, the idea is to look for two pairs that have the same PostId but are not the exact same tuple (i.e., whose Body or AuthorId are different). If you have at least one pair, then, the PostId of such pair appears at least twice (possibly more). Once you have this, you can project the PostId column.
> 1 votes

# Answer
Here is a relational algebra expression given $R\_2$ described in the question that uses set division operator

$$ \Pi\_{\text{PostId}, \text{AuthorId}}(R\_2) \div \sigma\_{\text{AuthorId} = E}(\Pi\_{\text{AuthorId}}(R\_2)) $$

$\sigma\_{\text{AuthorId} = E}(\Pi\_{\text{AuthorId}}(R\_2))$ will return a set $\\{E\\}$. Then by the definition of set division operator, we can see that only $(2,E)$ and $(4,E)$ belong to the $R\_2$. Thus, the above relational algebra expression will return $\\{2,4\\}$. Also, we observe that both 2 and 4 are the only PostIDs that have more than one appearance. Thus, the above relational algebra expression gives the right answer.
> 0 votes

---
Tags: database-theory, databases, relational-algebra
---


# Question
Title: LinkedList: Remove the kth node form the end
**Question:** Write a function that takes in the head of a `Singly Linked` List and an integer k and removes the kth node from the end of the list. The removal should be done in place, meaning that the original data structure should be mutated (no new structure should be created). Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed. In other words, if the head is the node that's supposed to be removed, your function should simply mutate its value and next pointer. Note that your function doesn't need to return anything. You can assume that the input Linked List will always have at least two nodes and, more specifically, at least k nodes.

Each LinkedList node has an integer value as well as a next node pointing to the next node in the list or to None / null. if it's the tail of the list.

**The Solution:**

```
class LinkedList {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

function removeKthNodeFromEnd(head, k) {
  let first = head;
    let second = head;
    let i = 1;
    while(i <= k){
        second = second.next;
        i++
    }
    if(second == null){
        head.value = head.next.value; // Why can't I do: head = head.next
        head.next = head.next.next;
        return
    }

    while(second.next !==null){
        second = second.next;
        first = first.next;
    }
    first.next = first.next.next;

}

```

I have understood the above algorithm for the most part. Except why I need to have:

```
        head.value = head.next.value;
        head.next = head.next.next;

```

Why can't I just replace the above lines with a single:

```
head = head.next

```

# Answer
> 1 votes
```
head = head.next

```

would accomplish nothing. It would only change the local variable head.

Read the question again:

> Furthermore, the input head of the linked list should remain the head of the linked list after the removal is done, even if the head is the node that's supposed to be removed.

Since you cannot change what node is the head, you change the contents of that node.

---
Tags: algorithms, data-structures, arrays, linked-lists, in-place
---


# Question
Title: Do nodes represented as NIL contribute to the height of a 2-3-4 tree?
Does the following 2-3-4 tree have a height of 3 or 2?

If I count from the external nodes i.e. the ones with the square boxes then **height should be 3**.
Not sure if they are to be included in the height as they are represented as NIL.
If they are not to be included then the **height of the tree should be 2.**

Any clarification on this?

# Answer
> 1 votes
Citing from the Wikipedia article on B-tree

> Every node (leaf or internal) is a 2-node, 3-node or a 4-node, and holds one, two, or three data elements, respectively.

Thus, since the squares in the bottom row do not hold data elements, they are not nodes of the 2-3-4 tree.

Then, using the definition of height from the answer to the post what is the difference between tree depth and height?, the height of your tree is 2.

---
Tags: trees, b-tree
---


# Question
Title: Difference between Recursion Tree & Binary Tree
What's the difference? is a Recursion tree private case of Binary tree?

# Answer
A binary tree is a rooted tree where every internal node has at most two children.

A recursion tree is a rooted tree which traces the execution of a recursive procedure. It need not be binary.
> 1 votes

---
Tags: graphs, binary-trees, recursion
---


# Question
Title: How can I get index of combination from element indices
An array of combinations is generated from two arrays,

```
               indices:  0   1   2   3   4   5
               array 1: [a,  b]
               array 2: [A,  B,  C]
     repeating array 1:  a,  b,  a,  b,  a,  b
     repeating array 2:   A,  B,  C,  A,  B,  C
          combinations: [aA, bB, aC, bA, aB, bC]    length = LCM(2, 3)

INPUT : a, C
OUTPUT: 2, which the index of aC in the generated combinations.

```

Say, when `a` and `C` are given whose indices are already known as `0` and `2` in the original arrays, how to find the index of `aC`, which is `2`? Is there any algorithmic way to do this?

For detailed background information, please check version 1 of this question.

# Answer
> 2 votes
(BTW, I think the code in the first edition of the question was the issue -- not the background info with respect to the sexagenary cycle, which is actually good to include to understand the motivation for the problem).

To put the problem a bit differently, you have the sets $\mathbb{Z}/m\mathbb{Z}$ = $\\{0,1,...,m-1\\}$ and $\mathbb{Z}/n\mathbb{Z} = \\{0,1,...,n-1\\}$, and you start with the pair (0,0), then (1,1), etc., basically applying the mapping $(x,y)\mapsto(x+1 \mod m,y+1 \mod n)$, until you wrap back around to $(0,0)$. In the easy case where $m=n$ then, you can see that $(i,i)$ was the $i$-th term in the sequence (0-based). In general, if you are asking about the index of $(i,j)$, then you are effectively trying to solve the system of congruences \begin{align\*} x &\equiv i \mod m \\ x &\equiv j \mod n \end{align\*} for $x$. Here $x$ represents how many times you did the $(+1,+1)$ operation starting with $(0,0)$.

When $m$ and $n$ are coprime, the Chinese remainder theorem gives you an algorithm to compute the solution. When they are not coprime, then that system in general may not have a solution, but in the case where the system was created by the above construction, it does. This math.stackexchange answer shows you how to find the (unique) solution in the range $\[0,LCM(m,n))$.

# Answer
> -1 votes
Yes, there is. Because everything is given, you only want to solve a specific instance of a more general problem. The solution is:

```
return 2;

```

---
Tags: algorithms, search-algorithms, rank
---


title: Greatest fixpoint of the type of lists

text:
# Question
Title: Greatest fixpoint of the type of lists
I'm working through Samuel Mimram's book *Program = Proof*. In the first chapter, he discusses recursive types in OCaml, and inductive types. An exercise he provides on the topic has me a little bit confused. In the exercise, he asks the reader to define the function induced by the inductively defined type of lists, and then show that it has a greatest fixpoint, distinct from the smallest fixpoint, and provide a concrete description of it.

I believe I'm able to define the function he mentions. If we had the type of lists of integers:

```
type list =
    | Nil
    | Cons of int * list

```

Then our induced function $F : \mathcal{P}(\mathcal{U}) \rightarrow \mathcal{P}(\mathcal{U})$ (where $\mathcal{P}(\mathcal{U})$ is the powerset of all possible values of our type `list`) looks like:

$$ F(X) = \\{ \mathrm{Cons}(n, l) \ | \ n \in \mathbb{Z},\ l \in X \\} \cup \\{ \mathrm{Nil} \\} $$

In the book, we learn that the least fixpoint of such a function defines the set of values inhabiting our type. That makes sense. He also goes through a proof of the Knaster-Tarski theorem to demonstrate that such a least fixpoint will exist, due to the fact that $\langle \mathcal{P}(\mathcal{U}), \subseteq\rangle$ is a semilattice and $F$ is monotonic.

I can't find any intuition for reasoning about the greatest fixpoint of this function. My naïve assumption is simply that the greatest fixpoint would be the set of all infinite lists, but I think I'm missing a really crucial idea here, and I can't tie it down in my understanding. If anybody could provide some information or input on this, I would really appreciate it!

# Answer
The greatest fixed point cannot contain only the infinite lists, because it must contain all the elements of the least fixed point (and every other fixed point). Another way to see this is that just the infinite lists are not even a fixed point, since applying $F$ will add $\mathrm{Nil}$, which is not infinite.

However, adding the infinite lists is the right thing to do. I'm not familiar with the book you're reading at all, so I don't know exactly how this would be realized in its setting. For instance, I don't know what $\mathrm{Cons}$ and $\mathrm{Nil}$ are intended to *be* exactly as operations on $\mathcal{U}$ (or what $\mathcal U$ consists of). But the idea would likely be that $\mathcal U$ has both finite and infinite things built completely out of them, the least fixed point collects just the finite ones, and the greatest fixed point collects all of them.
> 4 votes

---
Tags: type-theory, inductive-datatypes, lattices
---


# Question
Title: The number of connected components in the context of cyclomatic complexity
Cyclomatic Complexity is defined with reference to the control flow graph of the program through this formula (borrowed from Wikipedia):

```
M = E − N + 2P,
where
E = the number of edges of the graph.
N = the number of nodes of the graph.
P = the number of connected components.

```

I can't understand the last. What is "the number of connected components" in this context? Wikipedia itself uses the notion of (connected) components in relation to undirected graphs only.

There is also the concept of strongly connected component: a directed graph is said to be strongly connected if every vertex is reachable from every other vertex. So one can guess that the number of connected components is the number of strongly connected components of the control flow graph. Is it right? If not, can someone provide samples of control flow graphs with differerent numbers of connected components?

# Answer
When they say connected component, they mean a weakly connected component. Take a look at the third formula they provide in the Wiki.

> For a single program (or subroutine or method), P is always equal to 1. So a simpler formula for a single subroutine is M = E − N + 2.

This implies that for $P \> 1$ is used for multiple programs. In other words, it is used for programs with multiple start points with distinct end points.

So for the first formula, it takes in consideration of multiple programs, subroutines, or methods that are completely disconnected from each other (i.e. they do not call upon or interfere with each other) in a single program control graph.

The following is an example where the first formula would be applied. Here $M = 9 - 8 + 2\*2 = 5$.
> 0 votes

---
Tags: graphs, connected-components
---


# Question
Title: How does an operating system implement the C library?
I have an idea of how a C program is turned into machine code by the compiler. I also know how the processor processes the instructions (https://www.youtube.com/watch?v=cNN\_tTXABUA this video has a good introduction). But what I don't understand, is how an operating system (most times written in C or some low-level language) can run programs also in C (or other low-level language). I don't understand this. Does the OS read the code and then processes it with some internal functions, or does it only open the machine code and send it to the processor, that makes the rest? In case of the second option, how the OS take care of which instructions are allowed to be executed, and which are not? (example: I may write a program that has an instruction that jumps to a forbidden part of the memory RAM, how the OS protect it from happening?)

I don't expect to understand it fully in this post's answers, but if you guys could give me an idea and then some books or tags to search, I'd be happy!

# Answer
It's hard to give a full answer to this question, as it would basically amount to an introductory text in operating system design, so I will try to give some pointers.

First of all, if you really want to know (including all the gritty details) how an operating system actually works, there's probably no way around looking at an actual implementation of one. Luckily, there's xv6 providing quite a good example, see xv6 and follow the references there.

Before diving into the code, it's probably a good idea to have a look at the basic components of an operating system, see Operating System Components.

I think your question has three main aspects

1. How does an operating system load a (compiled) C program?
2. How does such a program interact with the system it runs on?
3. How does the operating system prevent bad things from happening and regain control once the program is running?

(Warning: The following might be oversimplifying things)

For the first question, see Loader. A compiled C program is just binary data. When loading (let us ignore some bookkeeping that is also going on around this), the operating system copies this binary data simply into memory, does some initialisation (e.g. copy arguments at places the program can find it) and then sets the instruction pointer to the start of the loaded program. Basically, from this point on the program is in control (see below). Eventually, the program (hopefully) will issue a system call, namely `exit`, when it is done, thus handing control back to the operating system, see Exit (system call (it might also terminate by using a simple `return` in `main`, but let us ignore that case for the moment).

This leads to the second question. The interaction with the operating system takes place via system calls. These, in turns, are implemented via interrupts. Roughly speaking, you can think of a special processor instruction being called (i.e., it's a feature of the processor), which stops the execution of the current code and starts the execution of an interrupt handler, which is part of the operating system. The interrupt handler than tries to figure out why it was called and will act accordingly. How does the processor know where to find the interrupt handler? This is part of the loading process of the operating system at boot time, see e.g. Kernel startup stage.

For the third question, see Process management:

> There are two possible ways for an OS to regain control of the processor during a program’s execution in order for the OS to perform de-allocation or allocation:
>
> 1. The process issues a system call (sometimes called a software interrupt); for example, an I/O request occurs requesting to access a file on hard disk.
> 2. A hardware interrupt occurs; for example, a key was pressed on the keyboard, or a timer runs out (used in pre-emptive multitasking).

The situation is slightly different on multi-core architectures, as there obviously the operating system and the loaded program can run concurrently.

For the memory related question, see Memory protection. Again, the short answer is that this is supported by processor features, i.e., the operating system can set boundaries when loading a program leading to an interrupt when these boundaries are violated. Another important feature related to this are CPU modes.

To sum things up, in order to understand operating systems, it's also important to understand computer architecture, as many features of an operating system are based in corresponding features of processors. I always found the following a good introductory textbook: "Computer Organization and Design: The Hardware/Software Interface" by David Patterson and John Hennessy.

Finally, the following (Linux-specific) example might help. The usual

```
#include <stdlib.h>
#include <stdio.h>

int main(void) {
    printf("Hello, world!");
    exit(0);
}

```

will turn into assembler code as follows (more or less..., stolen from the Wikipedia article on Netwide Assembler)

```
; compile on 64-bit Linux using
; nasm -f elf syscall.asm
; ld -m elf_i386 -s -o syscall syscall.o

global _start

section .text
_start:
    mov eax, 4 ; system call number 4: write
    mov ebx, 1 ; file descriptor 1: stdout
    mov ecx, msg
    mov edx, msg.len
    int  0x80  ; Passes control to interrupt vector
                   ; invokes system call, in this case system call
                   ; write(stdout, msg, strlen(msg));

    mov eax, 1 ; system call number 1: exit()
    mov ebx, 0 ; exit status 0
    int 0x80   ; Passes control to interrupt vector
               ; invokes system call, in this case system call
               ; number 1 with argument 0, i.e., exit(0)

section .data
msg:    db  "Hello, world!", 10
.len:   equ $ - msg

```

Once actually compiled, this will look like (just the part between the first and last column, the rest is for illustration purposes, generated using `xxd programName`)

```
0000000: 7f45 4c46 0101 0100 0000 0000 0000 0000  .ELF............
0000010: 0200 0300 0100 0000 8080 0408 3400 0000  ............4...
0000020: cc00 0000 0000 0000 3400 2000 0200 2800  ........4. ...(.
0000030: 0400 0300 0100 0000 0000 0000 0080 0408  ................
0000040: 0080 0408 a200 0000 a200 0000 0500 0000  ................
0000050: 0010 0000 0100 0000 a400 0000 a490 0408  ................
0000060: a490 0408 0e00 0000 0e00 0000 0600 0000  ................
0000070: 0010 0000 0000 0000 0000 0000 0000 0000  ................
0000080: b804 0000 00bb 0100 0000 b9a4 9004 08ba  ................
0000090: 0e00 0000 cd80 b801 0000 00bb 0000 0000  ................
00000a0: cd80 0000 4865 6c6c 6f2c 2077 6f72 6c64  ....Hello, world
00000b0: 210a 002e 7368 7374 7274 6162 002e 7465  !...shstrtab..te
00000c0: 7874 002e 6461 7461 0000 0000 0000 0000  xt..data........
00000d0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000e0: 0000 0000 0000 0000 0000 0000 0000 0000  ................
00000f0: 0000 0000 0b00 0000 0100 0000 0600 0000  ................
0000100: 8080 0408 8000 0000 2200 0000 0000 0000  ........".......
0000110: 0000 0000 1000 0000 0000 0000 1100 0000  ................
0000120: 0100 0000 0300 0000 a490 0408 a400 0000  ................
0000130: 0e00 0000 0000 0000 0000 0000 0400 0000  ................
0000140: 0000 0000 0100 0000 0300 0000 0000 0000  ................
0000150: 0000 0000 b200 0000 1700 0000 0000 0000  ................
0000160: 0000 0000 0100 0000 0000 0000            ............

```

This is the thing (or rather, a binary representation thereof) the operating system loads into memory. We might also want to have a look at it with `objdump -s -d programName` which gives some more information

```
Contents of section .text:
 8048080 b8040000 00bb0100 0000b9a4 900408ba  ................
 8048090 0e000000 cd80b801 000000bb 00000000  ................
 80480a0 cd80                                 ..
Contents of section .data:
 80490a4 48656c6c 6f2c2077 6f726c64 210a      Hello, world!.

Disassembly of section .text:

08048080 <.text>:
8048080: b8 04 00 00 00       mov    $0x4,%eax
    8048085: bb 01 00 00 00       mov    $0x1,%ebx
804808a: b9 a4 90 04 08       mov    $0x80490a4,%ecx
    804808f: ba 0e 00 00 00       mov    $0xe,%edx
8048094: cd 80                int    $0x80
    8048096: b8 01 00 00 00       mov    $0x1,%eax
804809b: bb 00 00 00 00       mov    $0x0,%ebx
    80480a0: cd 80                int    $0x80

```

You see that this program has two system calls. The first one is `write` which outputs the "Hello, world!", the second one is the `exit`. These two system calls correspond to the `int 0x80` in the assembler code that generates a software interrupt, see INT instruction and http://www.linfo.org/int\_0x80.html Before making a system call via `int 0x80` we need to tell the Linux, which system call we want (plus set up any other relevant parameters). System calls are identified by numbers, e.g. `1` is `exit`, `4` is `write`, see http://syscalls.kernelgrok.com/

Again, to sum this part up: System calls are translated into `int 0x80` instructions (plus necessary parameter handling before that). Once the program runs and hits an `int 0x80` instruction, the processor will give control to the operating systems interrupt handler which sees that it has to handle a system call and then does things accordingly.
> 14 votes

# Answer
When you compile a C program, the program is turned into an executable. You can think of an executable basically as raw machine code — the real picture is more complicated, but you can ignore these details for now. When you run a program from the command line (say), what the operating systems does is it *loads* (i.e., copies) the machine code found in the executable into memory, and then transfers control (jumps) there. In Unix, this is accomplished by the system call `execve`. The loading process is more complicated, since the operating system has to set up the environment and load dynamic libraries, but you can ignore these details for now.

If the code jumps into a forbidden location, then an interrupt is triggered. An interrupt is basically a jump to some location determined earlier by the operating system (in modern CPUs, only the operating system can modify these addresses). The operating system then triggers a signal (SIGSEGV or Segmentation fault) which eventually leads to a *core dump* (unless it is handled otherwise by the thread calling `execve`). The interpretation of *forbidden location* depends on the CPU and the operating system — indeed, buffer overflows take advantage of weaknesses in this mechanism.

Some programs are run on a virtual machine, for example Java and C#. From the point of view of the operating system, it all looks the same (unless the interpreter of the virtual machine is part of the OS itself), but the code itself is run on an imaginary CPU simulated by the interpreter in one way or another (see JIT compilation for the latest word on the subject). The interpreter can in principle ensure that the program doesn't do anything crazy.

Finally, regarding the title of your question: this has nothing to do with the C library. The loader is part of the operating system, not of the standard C library `libc`. An operating system usually provides a standard C library, but there are several other options, and you can choose for example to use GNU's `glibc` over the native standard C library (if it is different).
> 6 votes

# Answer
A very practical way to look at this is from the point of view of the shell you'd use after you log in to Linux. The shell itself will probably be written in C. The shell will call fork() to divide itself into two processes, and then call exec() from the second of those processes to replace the second process's code with that of the program you asked the shell to run. The shell's calls to fork() or exec() would go to functions in the C runtime library. The C runtime library provides all the functions specified as library functions in the C specification and/or POSIX specification. In general, fork(), exec() and all the other C library functions that rely on the OS will ultimately call syscall() which transitions into the kernel. The kernel has its own memory layout but can carefully access memory on behalf of a user process. The parameters to syscall() specify which OS function should be run and are a version of the parameters passed to the C runtime function. The syscall() piece is optimized in some Linux implementations but in others it is a software interrupt or trap, and the optimization implemented in for example x86 architecture is pretty much just a speedier way of doing the exact same thing. This interrupt or trap causes the kernel to execute from some fixed address within the kernel code, which translates the parameters that syscall was passed into a call to the appropriate C function in the kernel itself. If the parameters to the C runtime library function involve pointers to strings or buffers, those are passed across the syscall call, and then the function in the kernel that implements the OS function will probably need to obtain versions of those pointers that are valid in the context of the kernel.

Your question also asks about memory access protection. Very generally speaking, a user process or the kernel itself have access to defined regions of memory, which are described in tables that the kernel programs into the CPU. A table entry in the CPU will specify a range of memory in terms of virtual addresses, the same range as physical addresses, and whether that should be accessible to the user program or just to the kernel. This table is known as the GDT on the x86 architecture. Additional features of such an entry could include whether reading, writing or executing are allowed for that chunk of memory. But when the CPU is running the user process, the only valid memory accesses are the ones that are specified for the user process. You have multiple user processes running, and to simplify, when the kernel switches from running one user process to running another, it switches out the old user process memory map and switches in a new user process memory map, so that the processes don't have a way to see each other's memory. If a process tries to violate the rules of the memory map, it results in running a trap handler in the kernel.

Within the memory mapping system I described there are optimizations. One allows some sharing of the code when programs are linked to the same dynamic shared object (libc.so being an important example of one that it pays well to share) and for optimizing other things.

Some of the interface between the CPU itself and the kernel involves special functions executing. These functions can be written in C as long as they are tagged with special attributes to cause the C compiler to generate the entry code of the function in a way that is compatible with how the CPU will call the function. GCC supports the attribute "interrupt" as one way to code such functions but the details depend on the architecture.
> 1 votes

# Answer
I think what is being asked is more of a chicken vs. egg problem. If an operating system is written in C, but you have to a compiler/compiled version of the operating system to run a C program, how do you even run the OS in the first place??? The short answer is a bootstrap program. When you turn on the computer hardware will run some tests, then proceed to run a small program saved in ROM/BIOS/Firmware. This in turn gets the OS up and running. This is my general understanding anyway. https://www.cs.rutgers.edu/~pxk/416/notes/02-boot.html This article helped me wrap my brain around the concept.
> 0 votes

# Answer
You can write simple assembly code and have it execute on a CPU or microprocessor. On embedded devices, typically 1 program runs (1 main function) and has access to all of the memory and hardware.

An operating system makes each program "feel" it is the only thing running on a device, it "feels" it has access to all the memory and "believes" it talks to hardware directly.

To achieve this - oversimplified, things like the kernel set up the virtual environment for each program to run. This is done so if a program crashes or infinitely loops, it does not take down the rest of the system.

The kernel itself is a program that is run early, just after boot or during. It controls resources for all other programs. The kernel is more privileged than other programs and usually does things for other programs.

A better detail summary with visuals can be seen here
> 0 votes

---
Tags: programming-languages, operating-systems, compilers
---


title: Image selection for Object detection

text:
# Question
Title: Image selection for Object detection
I'm relatively new and am still learning the basics. I've used NVIDIA DIGITS in the past, and am now looking at Tensorflow. While I've been able to fumble my way around creating some models for a few projects I'm working on, I really want to start diving deeper into what I'm doing, how I'm doing it, and ultimately a better understanding of why.

One area that I would like to start with is the Images that I'm using for training and testing. Can anyone point me to a blog, an article, a paper, or give me some insight in what I need to consider when selecting images to train a new model on. Up until recently, I've been using datasets that have already been selected and that are available for download. Lets say I'm going to start working on a project that involves object detection of ships from a variety of distances and angles.

So my thoughts would be

1) I need a large quantity of images. 2) The images need to contain ships of the different types I would like to detect. (lets just say one class, ships, don't care what type of ships) 3) I also need to have images that have a great variety of distance perspective for the different types of ships.

Ultimately, my thoughts are that the images need to reflect the distance, perspective, and types of ships I would ideally want to identify from the video. Seems simple enough.

However, there are a number of questions

Does the images need to be the same/similar resolution as the camera I'll be using, for best results? Does the images all need to be the same resolution? Can I use a single image and just digitally zoom out on the image to give the illusion of different distances?

I'm sure there are a number of other questions that I'm not asking, or should be asking. Are there any guide lines available for creating a solid collection of images to use when creating the collection of images for training and validation?

# Answer
> 1 votes
**Do the images need to be the same/similar resolution as the camera I'll be using, for best results?**

Technically yes, for best results, you should use as close as possible images that you train them on to predict, for example, HD camera and webcam images are quite different, but in real life, it is not usually possible, as it is costly. You don't need the same resolution images, but if you resize from 30 x 30 x 3 to 256 x 256 x 3 or 1024 x 768 x 3 it to 256 x 256 x 3 makes a difference in how the image looks after transformation, but You can use different resolution images, but you need to resize them, using letterbox (padded image while preserving aspect ratio), or crop, or even in some cases just resizing without preserving aspect ratio gives good results. It depends on a case by case.

**Does the images all need to be the same resolution? Can I use a single image and just digitally zoom out on the image to give the illusion of different distances?** No, you don't have to have them in the same resolution. You can always resize images. If the object is small in the image it could be possible, but remember it's better to have more unique data for generalization of the network. But for augmentation usually one of the augmentation techniques is zooming in (center crop and resize), and you could use zoom out as well. There are other various techniques rotation, HSV transformations, shear, and many more you can use for augmentation.

# Answer
> 0 votes
The criterion is: the training set needs to have the same distribution as the test set. In other words, the images in the training set must come from the same distribution as test images will come from. Think about what images you plan to use the classifier on, and what distribution they come from; then the training set should be assembled by choosing images from that same distribution.

---
Tags: computer-vision
---


# Question
Title: "Term Rewriting and All That" - Exercise 3.10
I am studying Term Rewriting by reading Baader/Nipkow's book "Term Rewriting and All That". I am in chapter 3 - Universal Algebra, in the section 3.2 - Algebras, homomorphism and congruences. I am trying to do exercise 3.10:

> Let $\mathcal{Z}$ be the additive group of integers.
>
> (a) - Determine all subalgebras of $\mathcal{Z}$ and all congruences on $\mathcal{Z}$.
>
> (b) - Characterize those subsets of $\mathbb{Z}$ of cardinality 2 that generate $\mathcal{Z}$.
>
> (c) - Given the integers $a, b, c \in \mathbb{Z}$, we define the mapping $h\_{}: \mathbb{Z} \rightarrow \mathbb{Z}$ by: $$h\_{(a, b, c)}(z) := az^2 + bz + c.$$ For what triples (a, b, c) is $h\_{(a, b, c)}$ an endomorphism of $\mathcal{Z}$?
>
> (d) - Given the integers $a, b$, we define the mapping $g\_{(a, b)}: \mathbb{Z} \times \mathbb{Z} \rightarrow \mathbb{Z}$ by $$ g\_{(a, b)}(z\_1, z\_2) := a z\_1 + b z\_2 .$$ Show that $g\_{(a, b)}$ is a homomorphism of the direct product $\mathcal{Z} \times \mathcal{Z}$ into $\mathcal{Z}$. For what tuples $(a, b)$ is $g\_{(a, b)}$ onto?

I think I was able to do items (a), (b) and (c), but I am having problems with item (d).

For item (a):

> The subalgebras of $\mathcal{Z}$ are all of the form $\mathcal{nZ}$ where the carrier is $\mathbb{nZ} \ := \ \\{ n z \ |\ z \in \mathbb{Z} \\}$. This subalgebra is generated by $\\{ n \\}$.
>
> The congruences on $\mathcal{Z}$ are all of the form $\equiv\_{n} := \ \\{(z\_1, z\_2) \ | \ n \text{ is a divisor of } z\_1 - z\_2 \\}$.

For item (b):

> A subset of cardinality 2 $\\{ z\_1, z\_2 \\}$ generates $\mathbb{Z}$ if and only if it generates {1}. This happens if and only if $gcd(z\_1, z\_2) = 1$. So, the subsets of $\mathbb{Z}$ of cardinality 2 that generate $\mathcal{Z}$ are of the form $\\{z\_1, z\_2 \ | \ gcd(z\_1, z\_2) = 1 \\}$.

For item (c):

> It suffices to guarantee that $h(z\_1) + h(z\_2) = h(z\_1 + z\_2)$ for all $z\_1, z\_2$. Notice that:
>
> $h(z\_1) + h(z\_2) = a (z\_{1}^{2} + z\_{2}^2) + b (z\_1 + z\_2) + c $
>
> $h(z\_1 + z\_2) = a (z\_{1} + z\_{2})^2 + b (z\_1 + z\_2) + c$
>
> Since this equality must hold for all $z\_1, z\_2$, we must have $a (z\_{1}^{2} + z\_{2}^2) = a (z\_{1} + z\_{2})^2$ for all $z\_1, z\_2$. This is only possible if $a = 0$. There are no restrictions on $b$ and $c$. So, the triples $\\{(0, b, c) \\}$ make $h\_{(a, b, c)}$ an endomorphism of $\mathcal{Z}$.

For item (d), I was able to prove that $g(a, b)$ is a homomorphism of the direct product $\mathcal{Z} \times \mathcal{Z}$ into $\mathcal{Z}$:

> Taking arbitraries $z = (z\_1, z\_2)$ and $z' = (z'\_1, z'\_2)$ in $\mathcal{Z} \times \mathcal{Z}$ we have:
>
> $$g(z) + g(z') = (a z\_1 + b z\_2) + (a z'\_1 + b z'\_2) = a (z\_1 + z'\_1) + b (z\_2 + z'\_2) = g(z + z')$$

But I couldn't prove for what tuples $(a, b)$ we have that $g\_{(a, b)}$ onto.
Can anyone help me with this part of item (d)? Also, are my proofs of items (a), (b) and (c) correct? Thanks in advance.

# Answer
> 0 votes
If we can find $(z\_1, z\_2)$ such that $a z\_1 + b z\_2 = 1$ then we can take $(k z\_1, k z\_2)$ to obtain an arbitrary number $k (a z\_1 + b z\_2) = k \in \mathbb{Z}$ and then it is proved that $g\_{(a, b)}$ is onto. However, every linear combination of two numbers $(a, b)$ is a multiple of their $gcd$. So, $g\_{(a, b)}$ is onto if and only if $gcd(a, b) = 1$.

---
Tags: term-rewriting, algebra
---


# Question
Title: What are the units for time complexity graphs?
I often see big-O notation for time complexity algorithms and I see an equation that looks like $O(n) = n\log n$, which naturally generates a graph like the bottom one:

I know the x-axis represents some amount of information, and the y-axis represents some amount of time. However, what is the amount of actual time or data represented, does it depend on different types of computers or is it a standard (e.g.) bytes to seconds or KB to minutes?

# Answer
> 1 votes
We use Big-O notation to describe how "fast" an algorithm runs with respect to the size of the input in the worst case scenario. This input can be a number, a list of numbers, a matrix, etc. By fast, it essentially translates to number of steps the algorithm takes based on the size of the input in the worst case scenario.

I should start by describing the difference between an algorithm and an implementation of an algorithm. An algorithm is just a set of instructions that solves a problem. An implementation of an algorithm is code that is run on hardware that actually performs the set of instructions.

Suppose we have a simple problem, "given a list of numbers of arbitrary size and in no particular order, find the maximum value in the list". We solve this problem with an algorithm. Below is a solution to the problem.

```
FindMax(ls)
   m <- null
   for each x in ls
      if x > m
         m <- x

   return m

```

To analyze how good this solution is, we to find what the worst case is for this algorithm to handle. For this algorithm, the worst case would be a sorted list in ascending order. This is because the if statement will always be true (adding more steps).

Let $n$ be the size of the input list. Now let's count the number of steps our algorithm takes to complete (in the worst case). The initialization is 1 step (`m <- null`). The for loop will loop $n$ times. The amount it does inside the loop will be 2 steps (1for the if statement check and 1 for its body). Finally, 1 step for `return m`.

Let $T(n)$ be the worst case runtime for our algorithm. From above we have $T(n) = 1 + 2\*n + 1 = 2\*n + 2$.

This is where big-O notation will help us. We need to find a function $g(n)$ grows at a similar rate as $T(n)$; this function will be our upper bound. In other words, we need to find a function $g(n)$ where $T(n) \leq k\*g(n)$ for all $n \geq n\_0$.

Let's try $g(n) = 1$. Here we see that no matter what $k$ we try, $T(n)$ will always be greater at some point; more precisely, when $n\>k$ then $T(n) \> k\*g(n)$. This means $g(n) 1$ is not big enough.

Let's try $g(n) = n$. Here we see that if we choose $k \geq 3$ and $n\_0 = 1$, $k\*g(n) \geq T(n)$ for $n \geq n\_0.

What we proven is that $T(n)$ is bounded above by $g(n) = n$. This means that $T(n) \in O(g(n))$; in other words $T(n) \in O(n)$. Notice how I used $\in$ instead of $=$. This is because $O(g(n))$ is the set of all functions that are bounded above by $g(n)$. However, it is common practice to abuse the notation $T(n) = O(n)$.

The purpose of this example is to show you the context of big-O notation. Big-O notation is purely abstract in that we count the number of steps of the algorithm, not the amount of time (in seconds) it takes to complete. If we implement this algorithm in a program language (like C/C++ or Java) and run it on the computer, then we have many more factors to consider:

* Number of cores of CPU
* Clock speed of CPU
* Amount of memory
* I/O speed of the input
* Language specific performance issues (e.g. C/C++ faster than Java)
* etc.

None of these factors describes how well an algorithm performs; rather they show how well the implementation performs. See Big O Notation for an example and more information.

# Answer
> 0 votes
The point of the O(.) notation is to do away with the parts of the real world that hinder our understanding of how an algorithm scales, namely because you would get a different graph depending on the computer you use.

You get to pick the units of your X-axis, as long as they accurately measure the size of your input (typically: the size of its binary representation); and the same goes for your Y-axis, whose units measure the amount of computation the algorithm spends on the input. This might be seconds, milliseconds, cycles, ... but usually, we just speak of an abstract time unit, and more precision would require more information on the target architecture, which would defeat the purpose of using O(.).

---
Tags: algorithms, time-complexity
---


title: Floyd Warshall with constraints

text:
# Question
Title: Floyd Warshall with constraints
I was wondering if its possible to use floyd warshall with constraints meaning lets say you have a group of "special vertices" of size logn and you want to calculate all the shortest paths but each path has to go through at least one "special vertex" is this even possible or is it hard n

# Answer
Yes, and you can even use the Floyd–Warshall algorithm as a black box, together with a post-processing step to achieve this.

First, compute the shortest path between every pair of vertices using the Floyd–Warshall algorithm. Then, for each pair of vertices u and v and every special vertex w, compute the sum of the two shortest paths, the one from u to w and the one from w to v. The constrained shortest path from u to v is realized by the special vertex w that minimizes the sum of the u-w path's length and the w-v path's length.

Since the number of special vertices is obviously at most n, the computational complexity of the post-processing step is O(n^3). Because the computational complexity of the Floyd–Warshall algorithm is O(n^3) as well, the total computational complexity of this algorithm is O(n^3).

(credit to snakile)
> 0 votes

---
Tags: algorithms, graphs, algorithm-analysis, graph-traversal
---


# Question
Title: Selecting random element from complement of set
Let $\[n\] = \\{1, 2, \dots, n\\}$. Suppose we have a subset $S$ of $\[n\]$ of size $k$.

Can we sample one element uniformly at random from $\[n\] \setminus S$ in $O(k)$ time?

It's okay to use $O(n)$ auxiliary memory assumed to be initialized with zeros, as long as your algorithm can run and clean up back to the initial zero state all in $O(k)$ time.

# Answer
Yes actually, and it's quite simple.

1. Sample a random integer $q$ from $\[n-k\]$.
2. Initialize $c = |\\{x \in S \mid x \leq q\\}|$.
3. While $c \> 0$, let $q \leftarrow q + 1$ and if $q \notin S$ decrement $c$.
4. Return $q$.

This works because steps 2 and 3 forms a bijective mapping from $\[n -k\]$ to $\[n\] \setminus S$. Finally the algorithm runs in $O(k)$ because it's possible to check if $q \notin S$ in $O(1)$ time either by using a $O(n)$ memory bitset or a hash table and both steps $2$ and $3$ take at most $k$ steps.
> 2 votes

---
Tags: complexity-theory, sampling
---


# Question
Title: Finding all subsets of a set of MultiSets made of elements from a single MultiSet (without replacement)
(originally asked on StackOverflow)

---

Two recent questions on StackOverflow by the same author1 are generally solved by the same technique. This feels to me like it would be a studied and perhaps well-solved problem.

I would like to know what it might be called and where to find more information about it, assuming it is a well-known problem

This is my own phrasing of the question:

If we have a Set, $M$, of MultiSets, $M\_1$ \- $M\_n$ made up of elements of Set $S$, and we have a MultiSet of components, $C$, also drawn from $S$, how do we find all subsets of $M$ such that the for each subset, the multiplicities of each element of $S$ in its union is no greater than the multiplicity of that element in $C$ ?2

For example, paraphrasing my own answer to the first question:

> I think I understand that what you want would be for something like this:
>
> ```
> const catalog= ["ad", "aab", "ace", "cd", "ba", "bd", "adf", "def"]
> const components = ["a", "b", "a", "c", "d", "e"]
>
> simultaneousItems (catalog, components)
>
> ```
>
> to yield
>
> ```
> [
>   ["ad", "ace"], ["ad", "ba"], ["ad"], ["aab", "cd"], ["aab"], ["ace", "ba"],
>   ["ace", "bd"], ["ace"],["cd", "ba"], ["cd"], ["ba"], ["bd"], []
> ]
>
> ```
>
> where every array in the result is subset of catalog items that can be made together out of the components supplied. So, for instance, none of the output arrays contains `"adf"` or `"def"`, since we have no `"f"` in the components, and none of them contain *both* `"ad"` and `"aab"` since we only have two `"a"`s in the component list.

Note that I'm using `"abc"` as a shorthand for the set containing the strings `"a"`, `"b"`, and `"c"`.

The original problems seemed to be looking for maximal subsets, so there is one additional step, and that is perhaps an equally interesting problem, but I'm more curious about the version above.

Please don't look at my solution as any sort of algorithmic ideal. It was the first idea that came to mind.

Is this a well-known problem? There's some vague relationship to the Knapsack problem, and other packing problems, but I can't quite figure out what and where to search.

---

1 The first one is closer to what I think is the fundamental algorithmic question. I'm assuming the second one is closer to the real problem the OP is trying to solve. Without any feedback yet from the OP, I don't know for certain that my answers match the real need, but I find this an interesting question regardless.

2 More explicitly (and forgive me for being too far away from formal Math classes) if $C$ = ${\\{S\_1^{m(z\_1)}, S\_2^{m(z\_2)}, ... S\_j^{m(z\_j)}\\}}$ for some integer $j$, and $S\_1$, $S\_2$, ... $S\_j$ in $S$, and if $N$ = ${\\{M\_{a\_1}, M\_{a\_2}, ... M\_{a\_k}\\}}$ is one of the subset of $M$ in the result, and ${∪\\{{M\_{a\_1}, M\_{a\_2}, ... M\_{a\_k}}\\}}$ = ${\\{S\_1^{m(x\_1)}, S\_2^{m(x\_2)}, ... S\_j^{m(x\_j)}\\}}$, then for all $i$, $x\_i$$z\_i$.

# Answer
This problem (at least assuming you wish to find some sort of maximal subset) is simply the multidimensional knapsack problem, see e.g. *"The Multidimensional Knapsack Problem: Structure and Algorithms"* by Jakob Puchinger, Günther Raidl, Ulrich Pferschy.

To read that paper in your terminology, a quick translation. Your 'components' are known as *resources*, their multiplicities as *capacities*. The $i$th resource $S\_i$ has capacity $c\_i$. Each of your multisets $M\_j$ is an *item*, and it consumes $w\_{ij}$ of the $j$th resource. Thus $w\_{ij}$ is the multiplicity of $S\_i$ in $M\_j$.

Finally in the optimization version that's studied in the linked paper we wish to know the most *profitable* solution. In this context each of your multisets $M\_j$ (AKA *items*) has an associated profit $p\_j$. The paper selects $x\_j \in \\{0, 1\\}$ to determine whether item $j$ is part of the optimal solution, and thus solves the following problem:

\begin{align} \text{max }\\;\\; & z = \sum\_{j=1}^n p\_jx\_j\\ \text{s.t. }\\;\\; &\sum\_{j=1}^nw\_{ij}x\_j \leq c\_i, \quad i =1,\dots,m,\\ &x\_j\in\\{0, 1\\},\quad j = 1,\dots,n. \end{align}

Note that the paper uses $m$ as the number of components/resources and $n$ as the number of multisets/items.
> 1 votes

---
Tags: sets
---


# Question
Title: What are the modern alternatives to Backus–Naur form and what are their advantages?
I am very new to the whole concept of context-free grammars to represent the syntax tree of formal languages (i.e., programming languages). It seems that the Backus–Naur form (BNF) is the oldest of all possible notations and the most prevalent one. Though it looks like to be an ancient piece of art. Now I'm wondering that if you want to invent a new programing language what modern alternative you should use and why?

These are what I have found so far:

* ISO extended Backus–Naur form (EBNF)
* W3C-BNF
* augmented Backus–Naur form (ABNF)
* Extreme BNF (XBNF)
* Translational Backus–Naur form
* ANother Tool for Language Recognition (ANTLR)
* Wirth syntax notation (WSN)
* Van Wijngaarden grammar
* Microsoft “M” modeling language
* Compiler Description Language (CDL)
* Xtext grammar language
* definite clause grammar (DCG)
* META II

I would like to know what are the advantages and disadvantages of these options?

# Answer
# Answer 1: The question is meaningless as written.

You are mixing different *kinds* of notations here that are intended for different purposes.

* BNF and ABNF are concrete notations for writing the abstract concept of a context-free grammar.
* "Van Wijngaarden grammar" refers either to an abstract type of grammar a la "context-free grammar", or to a concrete notation for writing this type of grammar. Van Wijngaarden grammars are strictly more expressive than context-free grammars. In fact, parsing them is undecidable in general, making them more like an esoteric programming language in some respects.
* ANTLR is a particular software tool for generating parsers. It has a language for writing grammars that it accepts as input. Like most other parser generators, ANTLR includes specialized features in its grammar language for manipulating the generated parser code. For example, it is possible in an ANTLR input file to directly insert Java code that is to be executed by the generated parser when a certain token is encountered. This sort of feature only makes sense in the context of a parser generator.

# Answer 2: It mostly doesn't matter.

If, as you say, "you want to invent a new programing language," there are two situations where writing down a grammar is relevant:

1. Writing a parser as part of the compiler implementation. Your choice of how to express the grammar here is dictated by how your parser is implemented. Whether you use an ANTLR/Yacc/Bison-style parser generator, a parser combinator library, etc. will determine what your grammar looks like in the source code.
2. Writing a language specification. Most programming language specifications are written to be read by humans, not computers. Therefore, anything that is sufficiently clear to a human reader is an acceptable choice of notation. It is common for a language specification to define its own grammar notation, rendering the particular choice of notation largely irrelevant. For example, the "Lexical Structure" chapter of the Haskell 2010 Language Report starts with a "Notational Conventions" section that defines how the grammar will be written.
> 5 votes

# Answer
Here are a couple of pertinent references which support the idea "It mostly doesn't matter/write your own":

1. different parsing approaches: https://code.jsoftware.com/wiki/Guides/Parsing
2. a simple table-based (state machine) parser: https://www.jsoftware.com/help/dictionary/dicte.htm
> 3 votes

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


# Question
Title: Where is the problem in this proof that deciders are no stronger than LBAs?
So I've been working on a problem for fun and I'm worried I've run into some sort of contradiction, so I'm trying to figure out where I went wrong. I've simplified the issue down to this:

**Decider acceptance can be reduced to LBA acceptance**

Part 1: A decider can be reduced to a decider with an empty input alphabet.

1. Let $D$ be a decider with input alphabet $\Sigma$ and $\omega$ be an input string in $\Sigma^\*$
2. Construct a decider $D\_0$ with an empty input alphabet and the same tape alphabet as $D$, which starts by writing the characters of $\omega$ to the tape, returns to the left side, and then executes identically to $D$
3. $D\_0$ accepts the empty string $\epsilon$ iff $D$ accepts $\omega$

Part 2: A decider with an empty input alphabet can be reduced to an LBA

1. Let $D\_0$ be a decider with an empty input alphabet
2. $D\_0$ halts in finite time, and therefore uses finite portion of the tape of size $m$
3. Construct an LBA $A$ with the same states, symbols, and transitions as $D\_0$ where the length of the tape is given by linear function $f(x)=x+m$
4. The only possible input is $\epsilon$, so the size of the tape will be $m$, so $A$ will execute identically to $D\_0$ and not go out of bounds
5. $A$ accepts $\epsilon$ iff $D\_0$ accepts $\epsilon$

This seems to prove that a decider can be reduced to an LBA, which is well known to be incorrect. I have a couple of guesses for where the error might be:

* It could be in part 1, if you can't call a machine without input as powerful as a machine with input. After all, the only languages $D\_0$ could accept are $\emptyset$ and $\\{\epsilon\\}$, which are both regular, not recursive. So you can't say that an input-less decider accepts the same set of languages as a decider, but maybe it's as "powerful" in a more abstract sense?
* It could be in part 2, with the main problem being that computing $m$ would require running the decider, so the reduction to the LBA would be just as difficult as the acceptance problem. In other words, does the information you have prior to running automata change how powerful you can consider the automata to be?

Basically, I'm wondering if either of these concerns is the actual issue or if it's something else. And if either of these concerns isn't actually an issue, could you explain why? Thanks!

Edit: As pointed out, I should've represented these as decision problems, so part 1 would be a reduction from $\\{(D,\omega) | D\textrm{ is a decider that accepts } \omega\\}$ to $\\{D\_0 | D\_0 \textrm{ is an inputless decider that accepts}\\}$ and part 2 a reduction to $\\{A | A\textrm{ is an inputless LBA that accepts}\\}$. I believe the first two of these problems are recursive and the third is context-sensitive, so the first reduction is possible but the second isn't, due to $m$ not being computed.

# Answer
> 1 votes
You seem to be mixing some concepts. Over an empty input alphabet, there are no decision problems, so as a model, Turing machines with empty input alphabets are not interesting.

It is true that the problem of deciding whether a given TM accepts the empty word is interesting (and undecidable), but it's not the same thing as having an empty input alphabet.

So the "reductions" you describe are not exactly reductions in the formal sense, just some translations between models.

As for a concrete problem with your argument: first, an LBA runs on a fixed portion of the tape which is prescribed by the input length. If you have an empty input, the LBA is not allowed to touch the tape, so it can't really do anything. An LBA doesn't just mean that the space is linear in the input. So you can't manually add the "m" input cells. This breaks your argument.

But also note that the definition of the function $f(x)=x+m$ is a bit strange, since on an empty input alphabet, you always have $x=0$.

---
Tags: complexity-theory, turing-machines
---