# Question
Title: Regular Languages and Separating Suffixes
Preparing for the next semester, I wanted to give the following as a homework question, yet after a few attempts, I failed to solve it.

Given a language $L\subseteq \Sigma^\*$ and two words $x,y\in \Sigma^\*$, define the language $L\_{x,y}$ consisting of all the *separating suffixes* of the words $x,y$ relative to the *Myhill-Nerode* relation of $L$. That is, $$L\_{x,y} = \\{ z\in \Sigma^\*: (xz\in L \wedge yz\notin L) \lor (xz\notin L \wedge yz\in L) \\}$$ Is it true that if $L\_{x,y}$ is regular for every $x,y \in \Sigma^\*$ then $L$ is regular?

Thoughts:

* The solution I had in mind works only for languages that have bad prefixes. A word $y$ is a bad prefix for $L$ if you cannot extend $y$ to a word in $L$. That is, $y\cdot z \notin L$ for every $z \in \Sigma^\*$. If $y$ is a bad prefix for $L$, then $L = L\_{\epsilon,y}$, and so if $L\_{\epsilon,y}$ is regular, we're done. But clearly, some languages don't have bad prefixes.
* The opposite claim is correct: if $L$ is regular, then $L\_{x, y}$ is regular. This can be easily solved as follows. If $A = \langle Q, \Sigma, q\_0 , \delta, F \rangle$ is a DFA for $L$, then one can define a DFA $B$ for $L\_{x, y}$ over the product of $A$ with itself: $B = \langle Q^2, \Sigma, \langle \delta(q\_0, x), \delta(q\_0, y) \rangle, \delta', ((Q\setminus F) \times F) \cup (F \times (Q\setminus F))\rangle$. I omit the details.

# Answer
> 3 votes
For $\sigma \in \Sigma$, let $f\_\sigma$ be the indicator function of $L\_{\epsilon,\sigma}$, let $f$ be the indicator function of $L$, and let $b$ be the indicator of $\epsilon \in L$. If $w = \sigma\_1 \ldots \sigma\_n$ then $$ f(w) = f\_{\sigma\_1}(\sigma\_2 \ldots \sigma\_n) \oplus f\_{\sigma\_2}(\sigma\_3 \ldots \sigma\_n) \oplus \cdots \oplus f\_{\sigma\_n}(\epsilon) \oplus b. $$ Imagine a finite automaton reading the word in reverse (we know that regular languages are closed under reversal). The finite automaton maintains an accumulator $a$ initialized by $b$, and states of DFAs for the reverses of $L\_{\epsilon,\sigma}$ for all $\sigma \in \Sigma$. When reading $\sigma\_i$, it updates $a$ by $a \oplus f\_{\sigma\_i}(\sigma\_{i+1} \ldots \sigma\_n)$, and then updates the states of all DFAs. Finally, it accepts if $a = 1$.

---
Tags: regular-languages, finite-automata
---


# Question
Title: Find a linear bounded automaton that accepts the language $L = \{ a^{n!} : n \geq 0 \}$
I need to construct linear bounded automaton for the language $L = \\{ a^{n!} : n \geq 0 \\}$. I know how LBA functions, however, I don't have a thought how it can check the n! that to in the power of a. I might want to hear a few suggestions, as I am experiencing difficulty in developing the specific LBA for it.

# Answer
> 3 votes
The LBA maintains a counter $c$, initialized by $1$, which is stored on a parallel track. It thinks of the rest of the tape as an integer $m$. It then repeatedly executes the following instructions: divide $m$ by $c$, and increment $c$. The algorithm terminates when one of the following happens: $m = 1$, in which case you can declare success; or $m$ is not divisible by $c$, in which case you can declare failure.

---
Tags: automata, linear-bounded-automata
---


# Question
Title: Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable
How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable?

Intuitively speaking I think it is indeed undecidable because there seems to be no limit to the possible configurations, however I am not sure.

Thanks a lot in advance!

# Answer
If $M$ does not have the option to not move its head at all, as stated in a comment to the question, then the problem is trivially decidable by the Turing machine that immediately halts and accepts.

If $M$ might not move its head while computing $T(w)$ and the problem is to decide whether it actually does so, then the problem must be undecidable as otherwise the halting problem would also be decidable.

To see this, construct a Turing machine $M'$ that simulates $M$ while always moving its head. When the simulation terminates, $M'$ keeps its head in place for one more step, and then halts. It is not hard to come up with an algorithm that builds $M'$ from $M$, thus showing that $M'$ is computable. Then $\langle M', w \rangle \in L$ if and only if $M$ does not halt.
> 1 votes

# Answer
**Edit**: *the answer assumes that the tape of a TM is left bounded, that is, the tape has a leftmost cell.*

Given $\langle M, w\rangle$, $M$ does not move its head while running on the input $w$ when its in never the case that the head of $M$ is at the leftmost and the next transition suggests that $M$ moves its head to the left. Now can we decide whether this situation happens? Intuitively, the answer is no as $M$ may not halt on $w$ and this situation may not happen at all, in this case we can never know whether it will happen in the future or not, so we keep waiting. This smells like the halting problem.

Formally, we reduce the complement of the halting problem to your problem. For input $\langle M, w\rangle$, the reduction outputs $\langle K, w\rangle$, where $K$ is a machine that operates as follows. Given input $x$ for $K$, $K$ writes $\\#x$ on its tape (where $\\#$ is a special letter) without moving to the left while it is in it leftmost cell. Then, $K$ moves its head to the first letter after $\\#$, moves to the initial state of $M$, and runs on $x$ in the same $w$ that $M$ runs on $w$ with the following differences:

1- Whenever $K$ reads $\\#$ it stays in the same state of $M$ and moves to the right without modifying the tape. (Note that $\\#$ simulates the leftmost cell of $M$'s tape).

2- Instead of moving to the rejecting or accepting state of $M$, $K$ goes to a special state where it gets stuck and keeps going to the left without modifying its tape.

If $M$ does not halt on $w$, then $K$ does not halt on $w$, however by the way $K$ works, it moves its head in every transition (it always moves to the right when it is in the leftmost cell). Conversely, if $M$ halts on $w$, then eventually, $K$ gets stuck in the leftmost cell, in particular, it does not move its head in every step while running on $w$.
> 1 votes

---
Tags: turing-machines, reductions, undecidability, semi-decidability
---


# Question
Title: Finding a series of numbers that maximise $\ \sum f_i(x_i) $
Let $\ f\_1, f\_2, ... f\_m : \\{0, ..., m \\} \rightarrow \mathbb Z $

my task is to find an algorithm that find a series of numbers $\ x\_1, x\_2, ..., x\_m \in \\{ 0, ..., m \\} $ that maximise $\ \sum\_{i=1}^m f\_i(x\_i) $ and subjects to $\ \sum\_i^m x\_i \le m $

To be honest I can't really wrap my head around this problem. Any suggestions on ways to look at this problem differently?

# Answer
> 2 votes
Following is a trivial Dynamic Programming algorithm for your problem:

Let $T$ denote a table of size $(m+1)$ x $(m+1)$. Here, $T\[i\]\[j\]$ stores the maximum value of $\sum\_{t = 1}^{i}f\_{t}(x\_{t})$ such that $\sum\_{t = 1}^{i}x\_{t} \leq j$.

**Induction Case:** Since there are $m+1$ possible choices for $x\_{i}$, check each one of them. $$T\[i\]\[j\] = \max\_{p \in \\{0,\dotsc,m\\} \textrm{ and } p \leq j} \Big\\{T\[i-1\]\[j-p\] + f\_{i}(p)\Big\\}$$

**Base Case:** For $i = 0$ means there is no function. Therefore, the value is $0$. $$T\[0\]\[j\] = 0 \quad \forall j \in \\{0,\dotsc,m\\}$$

**Output:** The algorithm will output $T\[m\]\[m\]$ which is simply the maximum value of $\sum\_{t = 1}^{m}f\_{t}(x\_{t})$ such that $\sum\_{t =1}^{m} x\_{t} \leq m$

**Running Time Analysis:** Since the size of the table is $O(m^{2})$ and computing each entry takes $O(m)$ time. The overall running time is $O(m^{3})$.

# Answer
> 1 votes
This problem can be solved using dynamic programming.

For $i \in \\{1, \dots, m\\}$ define $F\_i(x)$ as the maximum value $\sum\_{j=1}^i f\_j(x\_j)$ attainable for a suitable choice of $x\_1, \dots, x\_i$ such that $x\_1 + \dots + x\_i \le x$. That is: $$F\_i(x) = \max\_{\substack{x\_1, \dots, x\_i \in \\{0, \dots, m\\} \\ x\_1 + \dots + x\_i \le x}} \sum\_{j=1}^i f\_j(x\_j). $$

As a special case let $F\_0(x) = 0$. You can then write $F\_i(x)$, with $i \ge 1$, as follows: $$ F\_i(x) = \max\_{y \in \\{0, \dots, x\\}} \big\\{ f\_i(y) + F\_{i-1}(x-y) \big\\}. $$

Computing all values $F\_i(0), \dots, F\_i(m)$ in increasing order of $i$ using the above identity immediately yields an algorithm with a running time of $O(m^3)$ to compute the optimal value of $\sum\_{i=1}^m f\_i(x\_i) = F\_m(m)$.

Using standard techniques you can then also find an optimal assignment to $x\_1, \dots, x\_m$.

---
Tags: algorithms
---


# Question
Title: Is this "superset existence" problem NP-complete?
The "Superset Existence Problem":

Let there be a set $S$, and $x$ subsets of $S$. Does there exist a set of size $y \< |S|$, which is a superset of at least $z$ of those subsets?

To me, this feels like it should be NP-complete (in $|S|$), since it seems intuitively related to covering problems and minimum $k$-union. But I'm not sure where to start with the reduction.

So: is this problem NP-complete?

# Answer
> 1 votes
The problem is NP complete. It is trivially in $NP$ (a certificate is the collection of the $y$ selected subsets of $S$), and it is $NP$-hard since it is the decision version of the Maximum Coverage Problem.

---
Tags: np-complete, decision-problem
---


# Question
Title: surprizing reducibility and challenge on it
Assume that Problem $A$ is polynomial-time reducible to problem $B$.

**Claim 1:** If problem $A$ is NP-hard then problem $B$ is NP-hard.

**Claim 2:** If problem $B$ is NP-hard then problem $A$ is NP-hard.

Claim 1 is obviously true, but why the second one is false?

# Answer
I am assuming that $A$ is a non-trivial problem. If $A$ is trivial, then the claims cannot be correct in their current form (make sure you understand why).

Consider an NP-complete problem $B$, and consider some non-trivial problem $A \in \text{P}$. Clearly, $A\leq\_p B$. If we assume that claim 2 is correct, then as $A\leq\_p B$, we get that $A$ is $\text{NP}$-hard and thus for every problem $L\in \text{NP}$, it holds that $ L\leq\_p A$. Hence, as $A\in \text{P}$, we get that $L\in \text{P}$ as well, and so $\text{NP}\subseteq \text{P}$. Conversely, if we assume that $\text{NP}\subseteq \text{P}$, then as every non-trivial problem is $\text{P}$-hard, we get that every non-trivial problem $A$ is $\text{NP}$-hard. Hence, claim 2 holds trivially.

So we have in total that claim 2 is correct iff $\text{P} = \text{NP}$ which is quite open.
> 1 votes

---
Tags: algorithms, complexity-theory, turing-machines, time-complexity, reductions
---


# Question
Title: show that NP is a subset of decidable languages
More specifically the problem says: "Let us call the set of decidable languages D. Show that NP ⊆ D"

My problem is that I always assumed that NP is decidable, but to prove it, I never thought it Somebody have any idea about how do it? or start resolving it?

I think I can prove it saying something like the NP problems effectively end in a polynomial time (although not deterministic) so there must be a MT-ND that accepts it and always ends, I suposse

# Answer
> 3 votes
Every language that is in NP is by definition decidable. Becase if a language L is in NP, than there is a nondeterministic Turing Machine that **decides** it in polynomial time, and thus L is decidable.

---
Tags: np, decision-problem
---


# Question
Title: $k$-SAT completeness proof when $k$ is linear in number of variables
I'm looking at a special version of SAT in which each clause has *exactly* $n/2$ literals, where $n$ is the number of variables. Can we prove NP-completeness of SAT in this case?

I tried reducing 3-SAT to it by expanding, but this introduces $2^{k-3}$ extra clauses per original 3-SAT clause, hence the reduction is not polynomial when $k=n/2$. Any ideas?

# Answer
> 1 votes
Your problem is actually in P. First of all, you can assume that no clause contains both a variable and its negation, since such clauses are always satisfied. Suppose that the instance contains $m$ clauses. Then a random assignment will falsify your formula with probability $m/2^{n/2}$. If $m \< 2^{n/2}$, then this means that your formula is satisfiable. Otherwise, the input is of size at least $2^{n/2}$, and so you can go over all $2^n$ truth assignments in polynomial time.

---
Tags: np-complete, satisfiability, polynomial-time-reductions
---


# Question
Title: Given the Turing machines M1 and M2, is L (M1) = L (M2)? is decidable?
I thought to reduce from the halting problem to conclude undecidability, yet I don't know how to do it. Perhaps the problem reduces to other decidable problem, and thus it is also decidable?

# Answer
As you suggested, think how to reduce from the halting problem $Halt\_{TM} = \\{ \langle M, w\rangle: \text{$M$ halts on $w$} \\}$. On input $\langle M, w\rangle$, the reduction should output a pair of TMs $\langle K\_1, K\_2\rangle$; such that $M$ halts on $w$ iff $L(K\_1) = L(K\_2)$.

This is somehow a basic reduction that can be done by standard tricks, so it would be a nice exercise to solve it alone. Here is a hint.

**Hint:** you can simplify things by fixing one of the machines $K\_1$ or $K\_2$ to be a constant machine that recognizes some fixed language. Then, think how to define the other machine depending on the reduction's input $\langle M, w\rangle$.
> 2 votes

---
Tags: turing-machines, undecidability, decision-problem
---


# Question
Title: Prove that $ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $ is $O(5^n)$
I need to prove that the following recurrence relation is $O(5^n)$: $$ T(n)=5^n+3T(\lfloor n^\frac{2}{5}\rfloor) $$ And $T(n)=\Theta(1)$ for $n\le 9$.

I am trying induction, and proving that there exists $c$ such that $T(n)\le c\cdot5^n$, but I am stuck at the induction step:

$T(n)=5^n+3T(\big\lfloor n^\frac{2}{5}\big\rfloor)\le5^n+3c\cdot 5^{\lfloor n^\frac{2}{5}\rfloor}\le5^n+3c \cdot 5^{n^{\frac{2}{5}}}=\bigg(1+\frac{3c}{5^{n- n^\frac{2}{5}}}\bigg)\cdot 5^n$.

How can I continue in the induction (turn the parenthesis into the constant $c$)?

# Answer
> 2 votes
Assume that $n \ge 4$ (the induction step is only handling $n \ge 10$ anyway), then $n-n^\frac{2}{5} \> n - \sqrt{n} \ge 2$ and you have: $$ \left( 1 + \frac{3c}{5^{n-n^\frac{2}{5}}} \right) \cdot 5^n \ge \left( 1 + \frac{3c}{5^2} \right) \cdot 5^n = \left( 1 + \frac{3}{25} c\right) \cdot 5^n. $$

The latter term is not larger than $c \cdot 5^n$ whenever $1 + \frac{3}{25} c \le c$, i.e., when $c \ge \frac{25}{22}$.

Pick $c$ large enough to satisfy $c \ge \frac{25}{22}$ and the base cases, and you're done.

# Answer
> 1 votes
In addition, if you are fine not using induction, you could do the following to get to a recurrence where the Master theorem can be applied.

First of all lets pretend there is no floor in the original recurrence (there are formal ways to get rid of that while obtaining the same asymptotic result), and define $S(n) = T(2^n)$. Then:

$$ S(n) = T(2^n) = 5^{2^n} + 3 T(2^{\frac{2}{5}n}) = 5^{2^n} +3 S\left(\frac{2}{5} n\right). $$

This recurrence has solution $S(n) = O(5^{2^n})$, hence: $$ T(n) = S(\log n) = O(5^{2^{\log n}}) = O(5^n). $$

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Solving $T(n) = 4T(n/2) + n^3$ with substituton method
I am trying to solve the following recurrence $T(n) = 4T(n/2) + n^3$ with substitution method. My guess is $T(n) = \Theta (n^3)$ (I used master theorem) and I tried to show that $T(n) \leq cn^3$. But, when I substitute I got $T(n) \leq c \frac{n^3}{2} + n^3$ and that's it not the exact form of the guess, so it doesn't work. How can I solve this recurrence?

# Answer
Your guess works: if $T(n) \le c n^3$ and $c \ge 2$ then $$ T(n) = 4c \frac{n^3}{8} + n^3 = \frac{c}{2} n^3 + n^3 = cn^3 \left(\frac{1}{2}+\frac{1}{c} \right) \le cn^3. $$
> 1 votes

---
Tags: asymptotics, recurrence-relation, master-theorem
---


title: Isn't linear time O(n)?

text:
# Question
Title: Isn't linear time O(n)?
In the question in this video about quicksort luckily picking the median in each recursive call. Tim Roughgarden, the presenter, says at 11:22

> Partition needs really linear time, not just $O(n)$ time.

What does he mean here? I thought linear time is $O(n)$. Does he mean $\Theta(n)$ or something else? I see how partition in quicksort here would be $\Theta(n)$ but I don't get the part that says "*not just $O(n)$ time*".

# Answer
Usually we call statement $A$ stronger than $B$ when $A$ implies $B$: $A \Rightarrow B$ (weaker-stronger). In other words, $B$ is weaker than $A$.

When the presenter is speaking about linear time for partition, this is a stronger statement than $O(n)$ time. All linear functions are in $O(n)$, but it also contains non-linear functions.

For example: $\sin n, \frac{1}{n}, \sqrt{n} $ are all in $O(n)$, but they are not linear. As was written in a comment, $O(n)$ is the set of functions **bounded by linear functions**, but not the set of *only* linear functions.

To be linear gives more information than to be in $O(n)$, to be in $\Omega(n)$, even to be in $\Theta(n)$.
> 8 votes

# Answer
> The partition needs really linear time

Here, the presenter meant that partition takes $\Omega(n)$ time.

> not just $O(n)$ time

Here, the presenter meant that this is a loose or weak statement. A stronger statement would be that partition takes $\Omega(n)$ and $O(n)$ time, which is equivalent to $\Theta(n)$, as you are saying.
> 3 votes

---
Tags: algorithms, asymptotics, big-o-notation, quicksort
---


# Question
Title: Given an undirected graph, find an orientation such that every vertex has out-degree at least 3
> Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3.

I know how to check if a vertex $v$ has at least $k$ edge-disjoint paths to any other vertex (using Ford-Fulkerson), so I thought I may use that for $k=3$.

Would appreciate your help :)

# Answer
> 2 votes
Given $G=(V,E)$, create a directed bipartite graph $H=(V+E, F)$ where there is an edge $(v,e) \in F$ iff $v \in V$ is an endpoint of $e \in E$. All these edges have capacity $1$.

Augment $H$ as follows: add two additional vertices $s$ and $t$; for each $v \in V$ add an edge $(s,v)$ with capacity $3$; for each $e \in E$ add the edge $(e, t)$ with capacity $1$.

Compute a maximum flow $\phi$ from $s$ to $t$ in the augmented version of $H$. Your problem admits a solution if and only if the amount of flow $|\phi|$ is $3|V|$.

To see this, first observe that $3|V|$ is an upper bound on $|\phi|$. Then suppose that there exists a feasible orientation $\mathcal{O}$ and look at any partial orientation $\mathcal{O}'$ in which each vertex $v$ has **exactly** three outgoing edges. A flow $\phi$ such that $|\phi|=3|V|$ is obtained by sending one unit of flow across each edge $(v,e) \in F$ such that $e$ is oriented away from $v$ in $\mathcal{O}'$, the flow across each edge $(s,v)$ is $3$, and the flow across $(e,t)$ is 1 if $e$ is oriented in $\mathcal{O}'$ and $0$ otherwise.

Suppose now that there is a flow $\phi$ such that $|\phi|=3|V|$. W.l.o.g., $\phi$ is integral. A feasible orientation is obtained by orienting each edge $e \in E$ away from the (at most one) endpoint $v$ of $e$ for which $\phi(v,e)=1$. If no such endpoint exists, then $e$ can be oriented arbitrarily. Notice that this procedure is constructive and immediately yields an algorithm for your problem.

---
Tags: algorithms, graphs, discrete-mathematics, network-flow, directed-graphs
---


# Question
Title: "For small values of n, O(n) can be treated as if it's O(1)"
I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1).

Example:

> The motivation for doing so is based on the incorrect idea that O(1) is always better than O(lg n), is always better than O(n). The asymptotic order of an operation is only relevant if under realistic conditions the size of the problem actually becomes large. *If n stays small then every problem is O(1)!*

What is sufficiently small? 10? 100? 1,000? At what point do you say "we can't treat this like a free operation anymore"? Is there a rule of thumb?

This seems like it could be domain- or case-specific, but are there any general rules of thumb about how to think about this?

# Answer
> 21 votes
All orders of magnitude involve a constant $C$, several of them actually. When the number of items are large enough that constant is irrelevant. The question is whether the number of items is small enough for that constant to dominate.

Here's a visual way to think about it.

All have a startup constant which determines their starting point on the Y axis. Each also has a critical constant $C$ dominating how fast they will increase.

* For $O(1)$, $C$ determines the time.
* $O(n)$ is really $C \times n$, where $C$ determines the angle.
* $O(n^2)$ is really $(C \times n)^2$, where $C$ determines the sharpness of the curve.

To determine which algorithm you should use, you need to estimate the spot where the runtimes intersect. For example, an $O(1)$ solution with a high startup time or a high $C$ will lose to an $O(n)$ solution with a low startup time and a low $C$ at fairly large numbers of items.

Here's a real world example. You have to move a bunch of bricks across a yard. You can move them a few at a time with your hands, or go get a huge, slow backhoe to lift and drive them over in one trip. What is your answer if there are three bricks? What is your answer if there are three thousand?

Here's a CS example. Let's say you need a list which is always sorted. You could use a tree which will keep itself in order for $O(\log{n})$. Or you could use an unsorted list and re-sort after every insert or deletion at $O(n \log{n})$. Because tree operations are complicated (they have a high constant), and sorting is so simple (low constant), the list will likely win out to hundreds or thousands of items.

You can eyeball this sort of thing, but in the end benchmarking is what will do it. You also have to eyeball how many items you'll typically have, and mitigate the risk of being handed more. You'll also want to document your assumption like "performance will degrade rapidly over $X$ items" or "we assume a maximum set size of $X$".

Because these requirements are subject to change, it's important to put these sorts of decisions behind an interface. In the tree/list example above, don't expose the tree or list. That way, if your assumptions turn out to be wrong, or you find a better algorithm, you can change your mind. You can even do a hybrid and dynamically switch algorithms as the number of items grows.

# Answer
> 45 votes
This is largely piggy-backing on the answers already posted, but may offer a different perspective.

It's revealing that the question discusses "sufficiently small values of ***n***". The whole point of Big-O is to describe how processing grows as a function of what's being processed. If the data being processed stays small, it's irrelevant to discuss the Big-O, because you're not interested in the growth (which isn't happening).

Put another way, if you're going a very short distance down the street, it may be equally fast to walk, use a bicycle, or drive. It may even be faster to walk if it would take a while to find your car keys, or if your car needs gas, etc.

For small ***n***, use whatever's convenient.

If you're taking a cross-country trip, then you need to look at ways to optimize your driving, your gas mileage, etc.

# Answer
> 15 votes
The quote is rather vague and imprecise. There are at least three related ways in which it can be interpreted.

The literal mathematical point behind it is that, if you're only interested in instances of size up to some limit then there are only finitely many possible instances. For example, there are only finitely many graphs on up to a hundred vertices. If there are only a finite number of instances, the you can, in principle, solve the problem by just constructing a look-up table of the all the answers to all the possible instances. Now, you can find the answer by first checking that the input isn't too big (which takes constant time: if the input is longer than $k$, it's invalid) and then look up the answer in the table (which takes constant time: there are a fixed number of entries in the table). Note, though, that the actual size of the table is probably infeasibly big. I said there are only a finite number of graphs on a hundred vertices and it's true. It's just that the finite number is bigger than the number of atoms in the observable universe.

A more practical point is that, when we say that the running time of an algorithm is $\Theta(n^2)$, that only means that it's *asymptotically* $cn^2$ steps, for some constant $C$. That is, there's some constant $n\_0$ such that, for all $n\geq n\_0$, the algorithm takes roughly $cn^2$ steps. But maybe $n\_0=100,000,000$ and you're only interested in instances of size much smaller than that. The asymptotic quadratic bound might not even apply to your small instances. You might be lucky and it might be faster on small inputs (or you might be unlucky and have it be slower). For example, for small $n$, $n^2 \< 1000n$ so you'd rather run a quadratic algorithm with good constants than a linear algorithm with bad constants. A real-life example of this is that the asymptotically most efficient matrix multiplication algorithms (variants of Coppersmith–Winograd, running in time $O(n^{2.3729})$) are seldom used in practice because Strassen's $O(n^{2.8074})$ algorithm is faster unless your matrices are really big.

A third point is that, if $n$ is small, $n^2$ and even $n^3$ are small. For example, if you need to sort a few thousand items of data and you only need to sort them once, any sorting algorithm is good enough: a $\Theta(n^2)$ algorithm is still only going to need maybe a few tens of millions of instructions to sort your data, which isn't much time at all on a CPU that can perform billions of instructions per second. OK, there are memory accesses, too, but even a slow algorithm will take less than a second so it's probably better to use a simple, slow algorithm and get it right than to use a complex, fast algorithm and find that it's lightning-fast but buggy and doesn't actually sort the data properly.

# Answer
> 9 votes
Big-O notation really only says something about the behaviour for arbitrary large n. For example, $f (n) = O (n^2)$ means that there is a constant c \> 0 and an integer $n\_0$ such that $f (n) \< c n^2$ for every $n \> n\_0$.

In many cases, you can find a constant c and say "For every n \> 0, f (n) is approximately $c n^2$". Which is useful information to have. But in some cases, this isn't true. If f (n) = $n^2 + 10^{18}$, then this is totally misleading. So just because something is O (n^2) doesn't mean you can switch your brain off and ignore the actual function.

On the other hand, if you only ever encounter the values n = 1, 2 and 3, then in practice it doesn't make a difference what f (n) does for n ≥ 4, so you might as well consider that f (n) = O (1), with c = max (f (1), f (2), f (3)). And that's what sufficiently small means: If the claim that f (n) = O (1) doesn't mislead you if the only values of f (n) that you encounter are "sufficiently small".

# Answer
> 5 votes
# If it doesn't grow, it's O(1)

The author's statement is a bit axiomatic.

Orders of growth describe what happens to the amount of work you must do as `N` increases. If you know that `N` doesn't increase, your problem is effectively `O(1)`.

Remember that `O(1)` doesn't mean "fast". An algorithm that always requires 1 trillion steps to complete is `O(1)`. An algorithm that takes anywhere from 1-200 steps, but never more, is `O(1)`. \[1\]

If your algorithm takes exactly `N ^ 3` steps, and you **know** that `N` can't be more than 5, it can never take more than 125 steps, so it's effectively `O(1)`.

But again, `O(1)` doesn't necessarily mean "fast enough". That's a separate question that depends on your context. If it takes a week to finish something, you probably don't care if it's technically `O(1)`.

---

\[1\] Eg, lookup in a hash is `O(1)`, even though hash collisions mean that you may have to look through several items in one bucket, as long as there's a hard limit on how many items can be in that bucket.

# Answer
> 2 votes
> Now, I can use a hashtable, and have O(1) lookups (leaving aside the specific implementation of the hashtable), but if I had e.g., a list, I would have O(n) lookups. Given this axiom, these two are the same if the collections are small enough. But at some point they diverge... what is that point?

Practically, it's the point where building the hash table takes more than the benefit you gain from the improved lookups. This will vary a lot based on how *often* you're doing the lookup, versus how often you're doing other things. O(1) vs O(10) isn't a big deal if you do it once. If you do it thousands of times a second, even that matters (though at least it matters at a linearly increasing rate).

# Answer
> 2 votes
While the quote is true (but vague) there are also dangers to it. Imo you should look at complexity in any stage of your application.

It's all too easy to say: hey I only have a small list, if I want to check if item A is in the list I'll just write an easy loop to traverse the list and compare the items.

Then your buddyprogrammer comes along needs to use the list, sees your function and is like: hey I don't want any duplicates in the list so he uses the function for every item added to the list.

(mind you, it's still a small list scenario.)

3 years later I come along and my boss has just made a big sale: our software is going to be used by a big national retailer. Before we only serviced small shops. And now my boss comes at me swearing and shouting, why the software, that has always "worked fine" now is so terribly slow.

Turns out, that list was a list of clients, and our customers had only like maybe a 100 clients, so nobody noticed. The operation of populating the list was basically an O(1) operation, because it took less then a millisecond. Well, not so much when there's 10.000 clients to be added to it.

And years after the original bad O(1) decision, the company almost lost a big client. All because of one little design/assumption error years before.

# Answer
> 1 votes
> The motivation for doing so is based on the incorrect idea that O(1) is always better than O(lg n), is always better than O(n). The asymptotic order of an operation is only relevant if under realistic conditions the size of the problem actually becomes large.

If I have two algorithms with these times:

* log(n)+10000
* n+1

Then there exists some point where they cross. For `n` smaller than that, the "linear" algorithm is faster, and for `n` larger than that, the "logarithmic" algorithm is faster. Many people make the mistake of assuming the logarithmic algorithm is faster, but for small `n`, it isn't.

> If n stays small then every problem is O(1)!

I *speculate* what's meant here is that if `n` is limited, then every problem is O(1). For instance, if we're sorting integers, we may chose to use the quicksort. `O(n*log(n))` obviously. But if we decide that there can't ever be more than `2^64=1.8446744e+19` integers, then we know that `n*log(n)` \<= `1.8446744e+19*log(1.8446744e+19)` \<= `1.1805916e+21`. Therefore, the algorithm will always take less than `1.1805916e+21` "units of time". As that's a constant time, we can say the algorithm can always be done in that constant time -\> `O(1)`. (Note that even if those units of time are nanoseconds, that's a grand total of over 37411 years). But still `O(1)`.

# Answer
> 0 votes
I suspect many of these answers are missing a fundamental concept. O(1) : O(n) is not the same as f(1) : f(n) where f is the same function, because O doesn't represent a single function. Even Schwern's nice graph isn't valid because it has the same Y axis for all lines. To all use the same axis the lines would have to be fn1,fn2 and fn3, where each was a function whose performance could be directly compared to the others.

> I've heard several times that for sufficiently small values of n, O(n) can be thought about/treated as if it's O(1)

Well, if n=1 are they are exactly the same? No. A function allowing a variable number of iterations has nothing in common with one that doesn't, big-O notation doesn't care, and neither should we.

Big-O notation is simply there to express what happens when we have an iterative process, and how will performance (time or resources) degrades as 'n' increases.

So to answer the actual question... I would say that those who make that claim don't understand Big-O notation properly, because it's an illogical comparison.

Here's a similar question: If I loop through a string of characters, and I know that in general my strings will be less than 10 characters, can I say that it's the equivalent of O(1), but if my strings were longer then I'd say it was O(n)?

No, because a string of 10 characters takes 10 times as long as a string of 1 character, but 100 times less than a string of 1000 characters! It's O(n).

# Answer
> 0 votes
I believe the text you quoted is quite inacurrate (using the word "better" is usually meaningless unless you provide the context: in terms of time, space etc.) Anyway, I believe the simplest explanation would be:

If time of execution grows with the size of an input then it is definitely not $O(1)$ and that should be clear. $O(1)$ does not mean *fast*. It just means (in terms of time complexity) that ***time of execution has a constant upper bound***.

Now, let's take a relatively small set of 10 elements and have a few algorithms to sort it (just an example). Let's assume that we keep the elements in a structure that also provides us with an algorithm capable of sorting the elements in constant time. Let's say our sorting-algorithms can have following complexities (with big-O notation):

1. $O(1)$
2. $O(n)$
3. $O(nlog(n))$
4. $O(n^2)$

Which algoritm would you choose? The first answer that comes to mind may be "of course I'll use the $O(1)$ one!", but this is not necessarily correct. What you forget when thinking like that is that the ***big-O notation hides the constant factor***. And if you know your set is pretty small, then this constant factor may be *much* more important than the asympthotic complexity.

Now let's "reveal" the *true* complexities of that sorting algorithms mentioned above (where "true" means not hiding the constant), represented by numbers of steps required to finish (and assume all steps take the same amount of time):

1. $200$ steps
2. $11n$ steps
3. $4nlog(n)$ steps (log with base 2)
4. $1n^2$ steps

If our input is of size 10, then these are exact amounts of steps for every algorithm mentioned above:

1. $200$ steps
2. $11 \times 10 = 110$ steps
3. $4 \times 10 \times 3.32 \approx 134$ steps
4. $1 \times 100 = 100$ steps

As you see, in this case the apparently worst algorithm with asympthotic complexity $O(n^2)$ is the fastest one, beating algorithms with $O(1), O(n)$ and $O(nlog(n))$ asympthotic complexities. The constant factor hidden by the big-O notation matters here. In my opinion it ***does not mean that we can treat $O(n^2)$ as better than $O(1)$*** (what would it mean anyway?) It means that for sufficiently small input (like you've seen in the example) the $O(n^2)$ may still be faster than $O(1)$ because of the hidden constant. **And if the constant is relatively large compared to the size of the input, it may matter more than the asympthotic complexity.**

# Answer
> 0 votes
My 2 cents:

sentence “For small values of $n$, $O(n)$ can be treated as if it's $O(1)$” considering from formal position, have no sense, because $O(n)$ is not a function, but set of functions, as well as $O(1)$.

It is possible to say more: $n$, as value, is not even in $O(n)$ definition, but rather there is identity function $\text{id}\_\mathbb{N}(n)=n$. Variables $n, C, N$ which appears in $O(n)$ definition are variables under quantifiers, so called bound variables, and free variable is only $\text{id}$ : $$O(\text{id})=\left\\{g \colon \exists C \> 0, \exists N \in \mathbb{N}, \forall n \> N, g(n) \leqslant C \cdot \text{id}(n)=n \right\\}$$ Really, we have $O(\text{id})$, but it is more habital to speak about it as about $O(n)$.

Now suppose we want to rephrase this sentence to elements of $O(n)$ and $O(1)$. Because $O(1) \subset O(n)$, then we can say, that, of course, some functions from $O(n)$, are $O(1)$.

And at end let me say, that $O$-notation, as asymptotical one, obviously, is not appropriate for some cases. For example, when we want to compare functions on some bounded set from $\mathbb{N}$, then we shouldn't use $O$-notation. Another example is factor constants: when they are important, then $O$ can give wrong answers. Nobody from us are agree to give $2$ billions instead of $1$, but $O(1) = O(2)$.

---
Tags: asymptotics
---


# Question
Title: Is the following Greedy algorithm to generate Gray Codes always correct?
I recently solved the basic problem of generating a n-bit Gray Code. The solution I used involved building larger-bit Gray Codes from smaller ones recursively (the solution I've seen on most websites).

However, I then had an idea for a Greedy Gray Code Algorithm: Start the Gray Code at 0 and at every step, find and change the single smallest bit such that we get a new, not-visited-before number. Keep on repeating this until we have exhausted all the `2^N` possible numbers with `N` bits.

I was sure that this approach wouldn't work for some values of `N`, but so far, it has worked for all `N` from 1 to 30. This was quite surprising for me, especially as I haven't seen this Greedy approach mentioned anywhere as a solution to the Gray Code Problem.

So, my question is, does this Greedy algorithm for generating N-bit Gray Codes *always* work? Is there a proof of its correctness? Otherwise, what value of `N` causes this algorithm to not be able to generate a correct Gray Code?

# Answer
> 2 votes
Your construction results in the standard binary-reflected Gray code, a recursive construction of which is described on Wikipedia, for example. We can also describe it in a different way: to generate the $m$'th codeword from the $(m-1)$'th, flip the least significant 1 bit of $m$. For example, when $n=3$, we have: $$ \begin{array}{c|c} 000 & 000 \\ 00\textbf{1} & 00\textbf{1} \\ 0\textbf{1}1 & 0\textbf{1}0 \\ 01\textbf{0} & 01\textbf{1} \\ \textbf{1}10 & \textbf{1}00 \\ 11\textbf{1} & 10\textbf{1} \\ 1\textbf{0}1 & 1\textbf{1}0 \\ 10\textbf{0} & 11\textbf{1} \end{array} $$

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


title: Can PDA have empty stack transition?

text:
# Question
Title: Can PDA have empty stack transition?
From a youtube video, this PDA can recognize any palindrom.

However, from wikipedia, here is one of the criteria of PDAs.

We clearly see that the transition function can't take an empty stack as input, as epsilon is not a part of Gamma. (but it can use it as output, and also epsilon input is allowed as we see in the union). But in the video, all transitions from q2 use empty stack as input stack character. What's wrong ?

# Answer
> 2 votes
1- The PDAs in the video seem to have a transition function of the form $\delta: Q\times (\Sigma\cup\\{\epsilon\\}) \times (\Gamma \cup \\{ \epsilon\\}) \to 2^{Q\times (\Gamma \cup \\{\epsilon\\})}$, so you are allowed to take a nondeterministic transition without reading any input letter and without popping a letter from the stack. Note however, that you are allowed to push a single letter (or none) to the stack in a transition that you take.

2- The PDAs from Wikipedia do not allow you to take a transition without popping a letter from the stack (note that as Yuval said: the stack is initialized with a "bottom of stack" symbol), however note that, unlike the PDAs in item 1, you can push an entire word in the stack in a transition that you take.

So you have two variants of PDAs that have slightly different syntax, however it is not hard to prove that a PDA from one variant can *simulate* a run of a PDA from the other variant, and thus both variants recognise the same class of languages, CFL. A high-level explanation of how both variants can simulate each other is given next. A PDA $A$ of the 1st variant simulates a run of a PDA B of the 2nd variant by first pushing a "buttom of stack letter", then $A$ mimics the transitions that $B$ takes: in the case where $B$ takes a transition that pushes a word of length $\geq 2$ into the stack, you can introduce new states that push that word, and then move to the state that $B$ moves to. Conversely, a PDA $B$ of the 2nd variant simulates a run of a PDA $A$ of the 1st variant by first popping the "buttom of stack letter", then $B$ mimics the transitions that $A$ takes: the non-trivial part here is to mimic popping $\epsilon$ from the stack. This is easy as $B$ is allowed to push an entire word into the stack: popping $\epsilon$, and then pushing a word $w$, is equivalent to popping a letter $\sigma$, and then pushing the word $\sigma\cdot w$.

---
Tags: pushdown-automata
---


# Question
Title: Clarifying the definition of reduction with regards to NP-complete problems
In my logic class we started learning about the different complexity classes. In particular, we focused on the NP complexity class. A problem is in NP if it is solvable in polynomial time using a nondeterministic Turing machine. To show that a problem $L$ is NP-compelete, we have to show that: $1)$ $L$ is in NP, and $2)$ if $L$ is solvable in polynomial time, then all problems in NP can be solved in polynomial time.

In regards to $2)$ we can use reduction. So if you already know a NP-complete problem $M$, then it is enough to show that we can use a polynomial time algorithm that we can use for $L$, in order to solve $M$ in polynomial time.

I'm not sure I understand the explanation for the reduction section.

# Answer
> 1 votes
A problem $L$ is $\text{NP}$-complete if $L$ is in $\text{NP}$, and $L$ is $\text{NP}$-hard (that is, $A\leq\_p L$ for all $A\in \text{NP}$ ). Consider the following claims.

**Claim 1:** if $L$ is $\text{NP}$-complete and $L\in \text{P}$, then $\text{NP} \subseteq \text{P}$ (that is, all problems in $\text{NP}$ can be solved in deterministic polynomial time).

**Claim 2:** If $ A \leq\_p B$, then $B\in \text{P} \to A \in \text{P}$.

What you asked about is claim 1. To begin with, its correctness follows from claim 2. Indeed, if $L$ is $\text{NP}$-complete, then for every $A\in \text{NP}$, it holds that $A\leq\_p L$. Thus, if we assume that $L\in \text{P}$, then we get by claim 2 that $A\in \text{P}$, and therefore $\text{NP} \subseteq \text{P}$. So what is missing for you is the proof of claim 2, and a sketch of its proof goes as follows. If $M\_f$ is a TM that computes a polynomial time reduction $f$ from $A$ to $B$, and $M\_B$ is a TM that decides $B$ in polynomial time, then a TM $M\_A$ that decides $A$ in polynomial time operates as follows. On input $x$, $M\_A$ computes $y = M\_f(x)$, then $M\_A$ runs $M\_B$ on $y$, and answers the same. What is left to show is that $M\_A$ decides $A$ in polynomial time, and I leave that to you (use the fact that |y| is polynomial, and the fact that a composition of polynomials is a polynomial).

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


title: Maximize number of subsets

text:
# Question
Title: Maximize number of subsets
Given a list of subsets $S\_1, \ldots, S\_n$ of the universal set $U = \\{e\_1,\ldots, e\_m\\}$, find a subset $S \subset U$ of size $k$ that contains the maximum number of subsets $S\_i$. In another words, $$\max\_{S \subset U\\ |S| = k} \sum\_{i = 1}^n \mathbb{1}\_{S\_i \subseteq S}$$ Where $\mathbb{1}$ is an indicator function.

For my application, $n, m \approx 10000$, $k = 16$, and $|S\_i| = 3$. Thus the naive brute-force approach will not work. (I think this is an NP-hard problem in general if you allow $k$ to vary).

Question: Find algorithm that get closest to the optimal solution within reasonable time ( ex $O(n^2)$)

As an approximation algorithm, I have tried the following greedy algorithm, but I would like a solution that gets closer to the optimal solution. We will start with $S = \emptyset$ and add one element at a time to $S$. Take $U = \\{e\_1,\ldots, e\_m\\}$. Rank each element using the following. Define $H\_{j,c}$ as number of sets $S\_i$ such that $|S\_i \setminus (S\cup \\{e\_j\\}| = c$. i.e. $$H\_{i,j} = \sum\_{i = 1}^n \mathbb{1}\_{|S\_i \setminus (S\cup \\{e\_j\\}| = c} $$

Add that element $e\_j$ to $S$ which has the maximum ordered value $(H\_{j,1}, H\_{j,2}, \ldots, H\_{j, m})$ as per the lexigraphical ordering. (Use $H\_{j,1}$ as the main score, and use $H\_{j,2}$ as a tie breaker and so forth).

Repeat until $|S| = k$.

PS.

1. I think I did a poor job of explaining the problem and my attempt at the problem. I would appreciate any edits to make this question clearer.
2. I am trying to use this problem, as a greedy approach to my previous question Graph partition that maximize the number of triangles within its parts. But I think this question is interesting as well.

# Answer
I'm not sure how well it'll work, but the idea is simple:

1. Consider a continuous relaxation of the function
2. Run projected gradient descent

1.) First, consider a discrete case: let $x\_i$ be $1$ if we pick an $i$-th element, and $0$ otherwise. The constraint is $\sum\_i x\_i \le k$. For each set $S\_j$, we want to write a function which is $1$ when all $i \in S\_j$ are picked, and $0$ otherwise. A natural choice is $g(S\_j, x) = \prod\_{i \in S\_j} x\_i$. Our objective is $f(x) = \sum\_j g(S\_j, x)$

Now, to make it continuous, let $x\_i$ vary in the range $\[0,1\]$ \- in other words, it represents a probability that we pick the $i$-th element. Now, $g(S\_j, x)$ represents the probability that the set $S\_j$ is chosen. The constraint $\sum\_i x\_i \le k$ and the objective $f$ are as before.

Therefore, the continuous relaxation is the following: \begin{align\*} f(x) &= \sum\_j \prod\_{i \in S\_j} x\_i \to \max & s.t.\\ x\_i &\in \[0,1\] \ \ \forall i \\ \sum\_i x\_i &\le k \\ \end{align\*}

2.) The gradient has a relatively simple form: $$(\nabla f(x))'\_{x\_i} = \sum\_{j\colon i \in S\_j} \prod\_{i' \in S\_j \setminus \\{i\\}} x\_{i'}$$

In other words, it's a sum of over terms containing $x\_i$: product of all factors except $x\_i$.

Since the problem is constrained, you need to run $projected$ gradient descent. I.e.

$$x^{(t+1)} \gets Proj(x^{(t)} - \gamma \nabla f(x^{(t)})),$$

where $Proj$ is a projection on the set $\\{x | \sum\_i x\_i \le k \land x\_i \in \[0,1\] \ \ \forall i\\}$. It may be hard to find the exact projection, but you can use Alternating projection or, better, Dykstra's projection. For that purpose, we rewrite our constraint set as $$\\{x| \sum\_i x\_i \le k\\} \cap (\cap\_i\\{x| x\_i \le 1\\}) \cap (\cap\_i\\{x| x\_i \ge 0\\}).$$

Now, we can project at each set in turns. Note that projection on $\\{x| x\_i \le 1\\}$ is trivial: when $x\_i \le 1$, don't do anything, otherwise $x\_i \gets 1$.

I'm not sure that the function is "good", and therefore I would try a smaller step size first. There are multiple optimizations that one can do, but I omit them here.
> 1 votes

# Answer
I can describe a solution that runs in linear time and is likely to give a solution that is close to optimal, *if* all of the sets $S\_i$ are chosen uniformly at random, and *only* for the specific parameters you mentioned. The method is easy to describe; explaining why it is likely to be close to optimal is much hairier.

# Algorithm

1. Pick two sets $S\_{i\_1},S\_{i\_2}$ that share two elements in common.
2. Pick $S\_{i\_3}$ that shares an element with $S\_{i\_2}$ and is different from $S\_{i\_1},S\_{i\_2}$.
3. Pick $S\_{i\_4}$ that shares an element with $S\_{i\_3}$ and is different from $S\_{i\_1},S\_{i\_2},S\_{i\_3}$.
4. Repeat until you have chosen $S\_{i\_8}$.
5. Output $S := S\_{i\_1} \cup \cdots \cup S\_{i\_8}$.

# Running time

This can be implemented in $O(n)$ time. In preprocessing, you build up a hash table that maps $e\_j$ to a list of all sets $S\_i$ that contain $e\_j$. This can be done by scanning through the sets and doing $3n$ inserts into the hash table. Also, build up a second hash table that maps the pair $(e\_j,e\_k)$ to the list of all sets $S\_i$ that contain both $e\_j$ and $e\_k$. This too can be done by scanning through the sets and doing $6n$ inserts. Then, step 1 of the algorithm above can be implemented efficiently using the second hash table, and each subsequent step can be implemented efficiently using the first hash table. When the algorithm says "pick", you can choose randomly from among all choices. If you ever get stuck (there are no valid choices), you can start over (this is unlikely to happen).

# Analysis of optimality

Why does this work? The reason involves some more combinatorics, and relies heavily on the assumption that the $S\_i$'s are random.

In particular, under this assumption, I believe it is overwhelmingly likely that the optimal solution covers 9 subsets. My estimates suggest that there is something like a $2/10^6$ chance that there exists a solution that covers 10 subsets; while the chance that there exists a solution that covers 9 subsets is nearly 1. So, we can focus on how to cover 9 subsets.

I also claim that the algorithm above is likely to give a solution that covers 8 subsets. In particular, by construction, if it terminates, it outputs a solution $S$ that covers 8 subsets, namely, it covers $S\_{i\_1},\dots,S\_{i\_8}$. Also, by construction, $S$ has $3 \times 8-2-6=16$ variables, as $S\_{i\_2}$ has two variables in common with $S\_{i\_1}$, and each subsequent set has one variable in common with the previous sets. Doing some combinatorics, it is overwhelmingly likely that there will exist some pair of sets $S\_{i\_1},S\_{i\_2}$ that have two variables in common (in fact we expect about 18 of them on average); and for each, set $S\_{i\_j}$, it is overwhelmingly likely that there will be another set we can choose for $S\_{i\_{j+1}}$ that has one variable in common with it (we expect about 8 or 9 of them on average). So the algorithm is overwhelmingly likely to succeed.

Thus, this gives an efficient algorithm that outputs a solution that covers 8 subsets; and the optimal solution likely covers 9 subsets; so this is quite close to optimal.

I hope I got all the combinatorics right... I recommend you test this to see if it actually works out as I am expecting.

# Caveats

As a reminder, this only works if the sets are chosen randomly. If they have some structure, it might fail badly. Also, it is very specific to the particular parameter settings you have listed (especially, $n \approx m$).
> 0 votes

---
Tags: optimization, np-complete, sets, greedy-algorithms
---


# Question
Title: Using A* path finding is giving me inaccurate results
So I am using A\* pathfinding to find a path from a person, to a node on a graph. This person has a few 'must pass' nodes that they must go through. So my solution was to run the algorithm for each of the must-pass nodes, to make sure they always go to each of these. My method for deciding which order nodes come in for their individual run through the algorithm is to use a distance between the person on the graph and the remaining nodes, the smallest distance will be put through the algorithm first.

Here is a diagram of what this looks like:

The person must visit the blue node last, which is why the distance hasn't been included for that node.

As you can see, the bottom right pink node is the first node to go through the algorithm since they have the smallest distance.

Here is where I come across a problem:

If the algorithm tries to find a path to this node on the bottom right, the person will actually travel across the edge with weight 1, since the distance between the node on the other side of the edge with the weight of 1, to the end node, is 6.25 (using a ruler by hand and making sure the diagram stays the same size on my screen at all times for all distances measured).

Would this not mean the person ends up traveling through all of the other must pass nodes on the graph before they even reach the first must pass node?

Are my criteria for picking the next node for the algorithm wrong?

What am I doing here that is wrong? Or is this a fault with A\*?

Note: The weights on each edge are measured fairly accurately by hand with a ruler, so I doubt that is the issue.

**EDIT**:

The one question I need to be answered is this. What is the best way to decide which node to path find for first? I'm starting to doubt if Euclidean distance is the best choice here.

# Answer
> 0 votes
Let's start this off with a quick review of A\*. A\* is a pathfinding algorithm that builds on some of the benefits that greedy searches and dijkstra searches have. Make sure that your implementation correctly combines both basic heuristics A\* uses:

1. `g(N)` = the cost to get from the starting node to the next node N
2. `h(N)` = the estimated cost to get to the goal from N

By expanding the nodes with the lowest `g(N) + h(N)` first, A\* quickly converges on the most efficient path when some costs are unknown. It's great for any graph search and I've used it to implement backtrackers for constraint solving.

---

Now, our review's over. Let's get to your problem!

You're trying to have a character visit certain subgoal nodes on the graph and finish on the goal node. This is actually a variant of the famous "Travelling Salesperson Problem". It is an example of an NP-complete problem, which means that even A\* isn't going to help you solve it quickly; you'll be doing a lot of backtracking or trial-by-error no matter what algorithm you use.

In order to adapt A\* to this problem, you will need to rewrite the logic for exiting the search. Instead of checking if `N_i == Blue_1`, you need to check if `{Blue_1, Pink_1, Pink_2, Pink_3}` is a subset of the path.

Right now your calculation for `h(N)` is based on **Euclidean distance from Blue**. Not a bad start, but it's not as efficient as simply setting `h(N) = 0` on this problem; dijkstra search is better than a too-greedy A\*. Because you aren't *actually* aiming for the blue node, you have an 'inadmissable' `h(N)` so you'll miss the optimal path sometimes:

> *"If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A\* is guaranteed to return a least-cost path from start to goal."*

You can get an admissible heuristic by setting `h(N)` = the distance to the nearest sub-goal. Once all sub-goals are reached, set `h(N)` = the distance from the blue goal. This means that each node in the pathfinder needs additional metadata. Add a field to pathfinding nodes that tracks which goals have already been hit.

---
Tags: algorithms, shortest-path, a-star-search
---


# Question
Title: How are programs split up into pages in Memory Paging?
I am a bit confused about how the logical addresses are generated in a paging memory architecture and where and when a program is split up into pages. I understand how logical addresses are translated to physical addresses and everything that happens after that. I just don't understand how a program is split into distinct pages and where and how this happens.

For example, if we consider a non-paging architecture which uses contiguous memory and execution-time binding, a CPU instruction like `JUMP 8`, where 8 is a logical address, I understand how an MMU with a base register can dynamically relocate a program anywhere in main memory by changing the value stored in base register, while the object code stored in memory is still using the logical address of 8. However, how is this `JUMP 8` instruction handled in a paging architecture, as in when will all these simple logical addresses like 8 be converted into logical addresses suitable for paging (with a page number and offset value), does the compiler split the program into pages?

Also, how is the program stored in memory, are the simple logical addresses stored like in execution-time binding, or is the program in memory stored with the paging logical addresses?

# Answer
The program is not really split up into pages. The program is unaware of where it lands in physical memory. This is all the essence of paging.

For example, if you take Linux on x86 CPUs and the C++ language, you will have the compiler generating machine code which will be linked into a final executable which has a .ELF extension.

ELF files support virtual addresses. ELF files specify the virtual addresses at which the code is going to land. The linker or compiler is going to write the starting virtual address at which the code is going to land. The default virtual address is 0x400000 with ld and g++.

So basically, the ELF executable specifies where the program lands in virtual memory. Since the default virtual address is always 0x400000, then a lot of programs will have that starting virtual address. The kernel thus creates page tables for each process (each executable that you start). These processes will land at different places in memory even if they all have the same virtual address. This is due to the fact that they have different page tables.

In fact Linux holds a `page` struct for every physical page in the system. This takes up quite some space and there have been discussion to change this pattern. I don't know if it is yet done. The `page` struct allows the kernel to map all physical pages to know what every page is used for.

So when you start an executable/process the kernel determines what physical pages are available and set up the page tables for that process so that virtual address 0x400000 lands there once translated by the MMU.

The JMP 8 instruction will be translated by the MMU before being placed on the address bus. So the 8 is a virtual address. This virtual address is determined by the compiler and the linker.

There are 2 different kinds of JMPs. Relative JMPs and absolute JMPs (far JMPs). Relative JMPs are calculated as an offset from the current position in the code. Far JMPs in the meantime are calculated as absolute address. They contain a virtual address where the JMP should go. They can JMP anywhere in RAM.

For example,

```
label:
jmp label

```

is a relative JMP, while

```
jmp 0x8000

```

is an absolute JMP. These jumps are calculated by the compiler and linker. The compiler places the functions you call from main at different positions in the code that it places in the relative JMPs. Far JMPs are mostly used in operating-system development.

The linker plays the role of linking several files. So you have a symbol section in the ELF file. This symbol section contains entries which associate each symbol with an address. I'm not totally aware since I never wrote an ELF interpreter. What I can tell is that the address is the address of the beginning of something like a variable or mostly functions. What happens is that the linker takes the symbol and checks it against other object files you included in the linking command. If it finds the symbol in another file, it places the address of the code in the relative JMP to tell the code where to JMP to get to that function. That is why it is called a linker, because it resolves links. This is why you have to include header files in C++. You tell the linker where to find these other symbols (functions, variables, classes).
> 1 votes

# Answer
On a consumer system, the page management is done by the kernel, but the translation is done by the MMU when you read and write to the memory. You got the idea of the MMU right, but nowadays it uses a page table which maps the virtual address space to your physical memory.

Pages are usually 4kB long, which means each contains 2^12 bytes. To find your page's number the MMU simply discards the 12 least significant bits of your address. Each process has its own page table (in fact there are many "layers" of page tables) and with each `context switch` (ie. when you change the process that is currently executing on a logical core) the kernel also restores the page table into memory. On x86 there is the CR3 register that holds the address of the page table so it can be read accessed by the MMU.

The page table entry contains a few flags, the most important one is the present/absent. It tells you whether the page is actually present in the memory or not. When your code will try to read or write to that page, if it is missing it will generate a `page fault` which will be handled by the kernel. If you're allowed to access the requested address (ie. no segmentation fault), the kernel will fetch the page from the disk (if needed to) and put it somewhere in memory and save its physical address in the page table.

The compiler is not usually involved in this process even though it does reorder your code so you ever only accessing a small part of your code. Imagine if all your virtual addresses were 4kB aligned : a char at 0x1000, another at 0x2000, etc. You would be wasting pages and physical memory. So the compiler "knows" paging and avoids doing that. But it does not split. Furthermore the binaries are not directly executed but interpreted instead so you would have to take that into account too.

Of course this process does not apply to the kernel as it cannot handle his own page faults.
> 0 votes

---
Tags: computer-architecture, memory-management, memory-hardware, virtual-memory, memory-allocation
---


title: Is Bitcoin mining NP-Hard?

text:
# Question
Title: Is Bitcoin mining NP-Hard?
I can't find this anywhere online. Is bitcoin mining NP-Hard?

If so, how would we be able to prove a reduction from a known NP-hard problem? I am a bit lost.

# Answer
> 4 votes
No. Bitcoin mining can be solved in $O(1)$ time. Unfortunately the hidden constant is quite large.

# Answer
> 0 votes
While Tom's answer is correct, I think there is more to be said. For example, there is a finite number of chess positions on an 8x8 board with the 50 moves rules, yet we can sometimes hear statements like "Chess is PSPACE-complete".

In order to study the complexity of such a problem, you have to generalize it, i.e. allow it to have arbitrarily large instances. For chess, a generalized board has size $n\times n$. Note that there may be different ways to generalize a problem, and they may yield different complexities.

If we generalize Bitcoin mining, parameterized by the number of bits oh the hash and the number of bits that you want to be 0 at the start, I think that we get an problem that is in NP (though I'm not sure we can guarantee that there exists a solution of polynomial size).

As for many problems used in cryptography, this problem is not known to be NP-hard: perhaps the structure of SHA256 has a weakness that allows to solve this problem efficiently. Moreover, it is not straightforward to build a reduction from SAT to this problem due to the structure of SHA256: it is not an arbitrary function.

---
Tags: np-complete, np-hard
---


title: Conditional branch instruction

text:
# Question
Title: Conditional branch instruction
How is a conditional branch instruction implemented in hardware? The instruction checks the sign bit, how does it decide to load pc with the branch address or increment pc to the next sequential address?

# Answer
A modern processor will first check whether it *knows* the value of the condition or not. For example, if you had a C statement "if (x / y \> 3) ... " then it will take quite a while until the value of the "\>" condition is known. If the condition is known, then the processor knows what to do.

If the condition is not (yet) known, then things get complicated. You don't want to wait until the condition is known. The processor will therefore use *branch prediction* to decide whether the branch is likely to be taken or not. For example, if this branch has been performed five times before, and each time the condition was true, then the processor will *guess* that the condition will be true again.

However, the guess might be wrong. Therefore all the following instruction are marked as "guessed", so the processor can undo the actions of each instruction. At the same time, the processor watches the condition: In the example, once the division x/y is complete, and the comparison x/y \> 3 is complete and the condition is known, the processor will know whether the guess about the condition was right or wrong. If it was wrong, then the processor undoes all the effects of instructions that were performed but shouldn't have been. If the guess was right then the processor marks all the instructions back to "not guessed". One thing that cannot be undone is storing results to memory, so while the condition was guessed, nothing has been stored to memory. All those store instructions are now started.
> 1 votes

---
Tags: cpu
---


# Question
Title: exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow
> Given a network flow and there exists (u,v) edge with positive capacity and there is not path from $s$ to $u$. and $(u,v)$ is with full capacity in some maximal flow.

I've had this questions with true or false and I thought it was false but apparently it is true. Can someone please explain me how this is possible?

# Answer
Since you just have to satisfy the conservation of flow property and capacity property. You can consider the following example:

$V = \\{s,t,u,v\\}$ and $E = \\{(s,t), (u,s), (u,v), (v,u)\\}$ with each edge of capacity 1.

You can send a flow of 1 via $(u,v)$, $(v,u)$, and $(s,t)$. It follows all properties of a valid flow. It does not have a path from $s$ to $u$. Also, the flow via $(u,v)$ is at its full capacity.
> 0 votes

---
Tags: graphs, network-flow
---


# Question
Title: Finding a grammar for $L = \{ 0^x1^y0^z1^w | x+w=y+z\}$
I have found an exercise where it tasks to provide a grammar and a pushdown automata for $L = \\{ 0^x1^y0^z1^w | x+w=y+z\\}$

While finding a pushdown automata for it is quite easy (four states and two stack symbols $p$ and $t$, where $0^x$'s push $p$, $1^t$'s and $0^z$'s pop $p$ or push $t$ if there are no $p$'s, and $1^w$'s pop $t$), I am unable to find an equivalent grammar for it. Perhaps there is some trick for this?

# Answer
> 2 votes
Let's write the condition $x+w=y+z$ in a different way: $x-y=z-w$. We consider two cases: $x \geq y$ and $y \geq x$. If $x \geq y$, let $x = y+a$. Then we are interested in words of the form $$ 0^{y+a} 1^y 0^{w+a} 1^w = 0^a 0^y 1^y 0^a 0^w 1^w. $$ If $y \geq x$, let $y=x+b$. Then we are interested in words of the form $$ 0^x 1^{x+b} 0^z 1^{z+b} = 0^x 1^x 1^b 0^z 1^z 1^b. $$ We can generate words of the first form using the grammar \begin{align} &T\_1 \to AW \\ &A \to 0A0 \mid Y \\ &Y \to 0Y1 \mid \epsilon \\ &W \to 0W1 \mid \epsilon \end{align} We can generate words of the second form using the grammar \begin{align} &T\_2 \to XB \\ &X \to 0X1 \mid \epsilon \\ &B \to 1B1 \mid Z \\ &Z \to 0Z1 \mid \epsilon \end{align} Taking these two grammars together and adding a new rule $S \to T\_1 \mid T\_2$, we get a grammar for your language. Note that you can merge $X,Y,Z,W$. The resulting grammar is \begin{align} &S \to AX \mid XB \\ &A \to 0A0 \mid X \\ &B \to 1B1 \mid X \\ &X \to 0X1 \mid \epsilon \end{align}

# Answer
> 1 votes
I don't know if $x$, $y$, etc. can be $0$, so maybe there's something to fix (e.g., you'll need $S\rightarrow \varepsilon$ etc.), but you can try something like this:

$S\rightarrow 0S1 \mid 0A0 \mid 1B1 $
$A \rightarrow 0A0 \mid 1C0$
$B \rightarrow 1B1 \mid 1C0$
$C \rightarrow 1C0 \mid \varepsilon$

Suppose $w\geq x$, then the idea is first generating the string $0^x S' 1^x$, then adding $w-x$ $1$'s on the right of the first $0$'s and the same number of $0$'s on the left of the last $1$'s, and so on; the case $x\geq w$ is similar.

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


title: Properties of Gomory-Hu trees

text:
# Question
Title: Properties of Gomory-Hu trees
Given an undirected graph $G=(V,E)$ a Gomory-Hu tree $T$ for $G$ has the following properties:

* $T$ has a node for each vertex in the graph G and each edge in the tree corresponds to a minimum cut separating the corresponding pair of vertices of G.
* $T$ has the property that *the minimum cut between vertices $s$ and $t$ in $G$ is the cut corresponding to the minimum weight edge along the path from $s$ to $t$ in the Gomory-Hu tree*.

In $\[1\]$, the author states the following lemma:

> Let $S$ be the union of cuts in $G$ associated with $n$ edges of $T$. Then removal of $S$ from $G$ leaves a graph with at least $n+1$ components.

Consider a complete graph $K\_4$ with all the edges having weight $1$.
A (possible) Gomory-Hu Tree $T$ for $K\_4$ is the following:

If we remove the cuts associated with all the $n=3$ edges of $T$ we might proceed as follows:

* $(3,0) \in T$ $\rightarrow$ remove $\\{(3,0),(3,1),(3,2)\\} \in G$
* $(3,1) \in T$ $\rightarrow$ remove $\\{(3,0),(3,1),(3,2)\\} \in G$
* $(3,2) \in T$ $\rightarrow$ remove $\\{(3,0),(3,1),(3,2)\\} \in G$

A potential result (among the different ones) is a graph with $2 \neq (n+1=4)$ connected components, i.e., $\\{3\\}$ and $\\{1,2,4\\}$.
So, my question is, am I missing something in the definition or properties of the Gomory-Hu trees?
Does the author mean that for each $(u,v)$ in $T$, all the minimum weight cuts between $u$ and $v$ in $G$ should be removed in order for the lemma to hold?

---

\[1\] Vazirani, Vijay V. *Approximation algorithms*. Springer Science & Business Media, 2013

# Answer
The book states the following definition of a *cut*:

> a cut is defined by a partition of $V$ into two sets say $V^{l}$ and $V \setminus V^{l}$ and consists of all edges that have one endpoint in each partition.

Therefore, removing a cut from the graph should mean that we are removing the edges that go across the cut.

Also, consider the following definition of the "cut associated with an edge $(u,v) \in T$ in $G$".

> Each edge $(u,v)$ in $T$ denotes a partition of $V$ given by the two connected components obtained by removing $(u,v)$ from $T$. Consider the cut defined in $G$ by this partition. We will say that this is the cut associated with $(u,v)$ in $G$.

Now, let us consider your example of Gomory-Hu tree for $K\_{4}$. We want to find the cut associated with the edge $(3,0) \in T$. If we remove $(3,0)$ from $T$, we obtain the partitioning $\\{1,2,3\\}$ and $\\{0\\}$. This defines the cut in $G$. Therefore, you should be removing the edges of $G$ that goes across this cut i.e., $(0,1)$ $(0,2)$ and $(0,3)$.

Similarly for the edge $(3,1) \in T$, you should be removing the edges: $(1,0)$, $(1,2)$, and $(1,3)$.

And, for the edge $(3,2) \in T$, you should be removing the edges: $(2,0)$, $(2,1)$, and $(2,3)$.

It means we are removing all edges from the graph. Therefore, the number of connected components in the remaning graph would be $4 = (n + 1)$, for $n = 3$.
> 1 votes

---
Tags: graphs, network-flow, minimum-cuts
---


# Question
Title: The probability that a person succeeds to pick the longest stick from a randomly ordered n sticks of distinct lengths following the optimal strategy?
To begin with, consider two persons(Px and Py) are playing a game. Px is the organiser of the game who has n sticks of distinct lengths and displaying them one by one to Py in a random order, with each order being equally likely. Given the fact that the lengths of sticks are not known to Py in advance. On each step, Py takes a single stick from Px. After that, he/she either picks the stick and finishes the game or discards the stick and moves on to the next stick. Note that Py can compare relative lengths of all already seen sticks.

* **Note that**: The answer is considered correct if the absolute or relative error does not exceed 10e-7
* **Constraints:** 1 \<= N \<= 10e5

---

**Sample Inputs and Outputs:(n -\> probability)**

* 1 -\> 1
* 2 -\> 0.5
* 3 -\> 0.5
* 10 -\> 0.398690476190

---

**Notes**: In the first test, Py chooses the first stick because it is the only one stick. In the second test, it does not matter if he/she chooses the first or the second stick. The probability of choosing the longest one is 0.5. In the third example, he bypasses the first stick, because if Py chooses it the probability would be 1/3. Then if the second stick is longer than the first one he/she chooses it and if it is smaller than the first one Py moves on to the third one.

---

**My Attempt:** I noticed that this is a binomial distribution problem since there are n attempts and each attempt is independent. Using the formula for the binomial distribution, I can not find the answer for n = 10, x =1, p = 1 /10, I got 0.387420489. I am struggling to find a solution is there any misconception I did? How to approach to a solution?

# Answer
> 1 votes
If you tried to get the longest stick out of 10, and they were shown to you in random order, how would you proceed?

Here’s a simple strategy, based on the simple idea that it’s daft to pick a stick that isn’t the longest so far: Don’t take any of the first four sticks, then pick the first stick that is longer than the longest so far. How will this work out?

If the first four contain the longest stick, you lose. If the first four contain the second longest stick, you win because you will pick the longest. If the first four contain the third longest stick, then you will pick the longest or second longest, 50% chance to win, and so on.

Chances are 65.61% that the first four don’t contain the longest, and 40.96% that they contain neither of the two longest; that alone gives you a 24.65% chance to win because you *must* pick the longest stick. You can calculate your chances to win quite easily: let p(k) be probability (“None of the p largest”) - probability (“None of the p+1 largest”), then your chance to win is p(1) + p(2)/2 + p(3)/3 ...

You would also check if skipping the first three or five or any other number might be better.

If you ignore about the first n/e sticks, this will give you a winning chance around 1/e even when n is very large.

---
Tags: algorithms, data-structures, probability-theory, game-theory, c++
---


# Question
Title: Question in coreset construction fro K-median clustering
I was reading Ke chen's paper about coreset construction for K-median clustering. In this paper, he assumed that $A$ is an $\[α, β\]$-bicriteria approximation for K-median clustering for some $α, β=O(1)$. I am wondering if the construction still work if $A$ is an arbitrary set of $αk$ centers? Can anyone help prove the correctness of my suggestion?

# Answer
> 2 votes
Of course not. Otherwise the construction would be "pick an arbitrary set of centers". You can follows the proof and see that the size of the coreset depends polynomially on $\beta$ and $\alpha$. If they are $O(1)$ they can be hidden in the $O()$ notation. Otherwise, someone needs to pay. See more details in Section 6 here: https://arxiv.org/abs/2011.09384

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


# Question
Title: Is type-checking "syntactic" or "semantic"?
On the wikipedia page on compilers, it says:

> **Semantic analysis** adds semantic information to the parse tree and builds the symbol table. This phase performs **semantic checks such as type checking** (checking for type errors), or object binding (associating variable and function references with their definitions), or definite assignment (requiring all local variables to be initialized before use), rejecting incorrect programs or issuing warnings. Semantic analysis usually requires a complete parse tree, meaning that this phase logically follows the parsing phase, and logically precedes the code generation phase, though it is often possible to fold multiple phases into one pass over the code in a compiler implementation.

I was somewhat surprised that type checking is categorized as semantics rather than syntax. Usually my impression is that types are called syntactic objects. Is type checking syntactic or semantic?

# Answer
Although I personally would describe type analysis as semantic, this question seems to start with the assumption that there is a clear, formally-definable dividing line between "syntax" and "semantics".

I don't think that is the case; even if most of us would put type-correctness into one category and missing parentheses into the other one, there is a fuzzy area in the middle where the answer is much less clear.

Consider, for example, the common case of a language which requires identifiers to be declared in the scope in which they are used. Clearly, then, the following is an error: (leaving aside the precise syntax of the language)

```
function ilog2(a:int) => int
  if a > 0 then
    let log:int = 0
    while a > 1
      a = a / 2
      log = log + 1
    end
  end
  return log
end

```

Many people would argue that the use of `log` in the `return` statement is a semantic error, since it has to do with the set of definitions in the outer scope of the function. On the other hand, it is quite feasible to construct a grammar (not a context-free grammar, but a grammar nonetheless) which rejects this program. It's not a coincidence that this scoping rule is called "lexical scoping" rather than, for example, nested semantic scoping.

A context-sensitive grammar can accomplish that in a straight-forward fashion by scanning backwards (and forwards, if declarations are allowed to follow use) skipping over inner scopes until it finds a declaration for the used identifier. Of course, that's not a very efficient algorithm but it's reasonable to assume that there are more efficient ways to implement such a grammar.

Even more generally, in the lengthy discussions which lead to the formalism of Algol 68, Adriaan van Wijngaarden proposed a syntactic formalism (link taken from this Wikipedia article) powerful enough to not just encompass declarations, but also to encompass static type checking. Although not everyone will agree with the judgement, van Wijngaarden's proposal was considered readable enough that it was eventually used in the formal definition of Algol 68. In that definition, type agreement (other than discriminated unions) is guaranteed by the grammar, while semantics is reserved for questions like the precise meaning of the `+` operator.

In retrospect, Van Wijngaarden's formalism turned out to be far too powerful to allow for automated parser generation, but it did spawn a number of simplified and less powerful formalisms, collectively called "attribute grammars", which have the potential to expand the formal power of syntactic descriptions while remaining practical tools for compiler writers. (There are few practical demonstrations, but there is still hope. :-) )

In short, if you consider "syntax" to be intimately linked to a particular syntax formalism (and hence to a particular parsing algorithm), then you will probably be able to make a clear distinction between syntax and semantics, but it might turn out to be a different distinction made by someone using a different parsing algorithm. So it's hard to see how write *universal* and non-overlapping definitions of syntax and semantics.
> 8 votes

# Answer
(From my limited experience) I would certainly call type-soundness a semantic property of a program, rather than a syntactic one.

In some dynamic languages (e.g., lisp, python sans type annotations & mypy, etc.), there is no syntax for types (and the semantic verification of type soundness is done at runtime in these languages).

In some static languages (such as SML), one can omit almost all syntactic type information; the program fails to compile if it does not type check. This is a semantic analysis because it requires type-inference, and there are not (necessarily) types in the text of the program. Of course, the programmer can (and arguably should) add type information to parts of the program; the same type-checker attempts to unify its inferences with what the programmer asserts to be true.
> 5 votes

# Answer
Terms such as "syntax", "semantics", and "pragmatics" were borrowed from linguistics. Linguists are trying to understand a *natural phenomenon*: human language. Theories about grammar and denotation are *models* of that natural phenomenon.

Computer scientists are not so constrained, in that their job (in this context) is to define artificial languages formally such that both humans and machines can understand them.

The job of lexical analysis, syntax analysis, and semantic analysis (wherever you draw the line) is to limit the number of valid program texts from $\Sigma^\*$ down to whatever strings make sense. Where you draw the line is somewhat arbitrary.

I suspect that the question is really about how errors are *reported*, and this is something that distinguishes natural languages from programming languages.

Error reporting is a neglected area of language design, and is usually treated as an implementation detail. Programmers spend a lot of their time reading messages from a compiler explaining why their alleged program is not valid, so this is probably the most important part of the user interface of a compiler.
> 1 votes

---
Tags: compilers, semantics, type-checking, syntax
---


# Question
Title: Is string spliting formally defined when the string delimiter is an empty string?
Depending on the API/language you use, splitting the string `"ABCD"` using `""` as a delimiter gets you:

* `["A", "B", "C", "D"]` in Java, Javascript, and Go
* `["", "A", "B", "C", "D", ""]` in Rust
* `["ABCD"]` in C#
* Fails with an Exception in Python3

From the perspective of formal language design, what is *the* correct result of such an operation? Is it defined?

Disclosure: This question was posted at stack overflow but was closed as opinion-based. I was directed to post my question here instead.

# Answer
> 1 votes
Given sequences $A = \[a\_1, \ldots, a\_n\]$ and $B = \[b\_1, \ldots, b\_m\]$, write $A + B = \[a\_1, \ldots, a\_n, b\_1, \ldots, b\_m\]$ for their concatenation. Given a sequence of sequences $C = \[C\_1, \ldots, C\_n\]$, write $\Sigma(C) = C\_1 + \cdots + C\_n$ for their concatenation.

Define a **splitting of a sequence $X$ by a sequence $Y$** to be a sequence of sequences $Z = \[Z\_1, \ldots, Z\_k\]$ such that $Z\_i \neq Y$ and $Z\_i \neq \[\]$ for all $i = 1, \ldots, k$, and $$X = \Sigma \[Z\_1, Y, Z\_2, Y, z\_3, \ldots, Y, Z\_k\].$$

For example, $\[\[a\], \[\], \[b, c\]\]$ is a splitting of $\[a, u, v, u, v, b, c\]$ by $\[u, v\]$.

Splitting by the empty sequence is not unique: $\[a, b, c\]$ may be split by $\[\]$ in several ways, among others $\[\[a\],\[b\],\[c\]\]$, $\[\[a,b\], \[c\]\]$ and $\[\[a,b,c\]\]$. From a theoretical point this is a rather trivial and non-interesting observation. The implementors of various string libraries need to deal with splitting by the empty sequence somehow, and as you show, they do.

---
Tags: strings, substrings, string-matching
---


# Question
Title: Route finding on a graph that must go through multiple edges
I have this graph

It shows a graph of a map that has nodes and segments (or edges), with weights, that connect these nodes. Some of these segments have addresses on, and some of these addresses are designated as restaurants. There are two chosen restaurants, and one chosen address.

Can someone point me in the direction of an algorithm that would calculate the best path to get from any segment, through each of the segments containing the chosen restaurants, and ending at the chosen address?

So far I have looked at Christofides Algorithm, and Dijkstra's Algorithm, neither of which seem to solve this problem, or atleast i cannot work out how to alter the algorithms to make them work for this problem.

# Answer
I have decided that the best solution to this is a variation on Dijkstra's algorithm. Since it doesn't require a Hamiltonian Circuit and makes it easy to manage the weights. I will also use Homeomorphism as suggested in the comments of the question to make weighting the distance between the nodes and addresses more accurate.
> 1 votes

# Answer
The statement that you want a path that "goes through multiple edges" is easily replaced with a normal path finding algorithm when you observe that you can *subdivide each edge* containing a place of interest.

Subdividing an edge $e = uv$ means that you create a new vertex $v\_e$ with $u$ and $v$ as neighbors, and then you delete the edge $e$ from the resulting graph. If the edges are weighted, there should be no issue in putting $w(e)/2$ on each of the two new edges (depending a bit on what the weights mean).

Once you have done that, the problem is a standard Euclidean TSP problem. There are many approximation algorithms (a very simple 2-approximation using minimum spanning trees), as well as numerous PTAS algorithms.

In the case where you only have a handful of, say, "terminals" (your restaurants), the very easily implementable classic exact DP algorithm running in $O(2^t t^2 \cdot (n+m))$ time should be very feasible (say for $t \leq 12$).
> 1 votes

---
Tags: algorithms, graphs, graph-traversal, traveling-salesman, routing
---


# Question
Title: Is there an online/offline tool that can perform K-means/median, given an initial centroid from the user?
The types of problems I am trying to solve are as follows:

Given a set of co-ordinates such as: (1,2), (3,3), (6,2), (7,1), a value of k such as k=3 and an initial set of centroids such as c1=(2,2) and c2=(5,4), perform the k-means/median algorithm.

Now, with samples that small, I can easily work it out on paper. However, if I have 200 co-ordinates to start with and 10 centroids, it starts to get a lot more tricky.

I have already found this calculator: https://scistatcalc.blogspot.com/2014/01/k-means-clustering-calculator.html and several others which serve a similar function. I have also found python code doing similar operations. However, all these tools initialize centroids randomly or using k-means++. I, on the other hand, want to initialize the centroids manually.

Is there an online/offline tool/code/platform that can achieve this?

# Answer
> 1 votes
I think this should be possible using the scikit-learn implementation; see here: https://stackoverflow.com/questions/38355153/initial-centroids-for-scikit-learn-kmeans-clustering.

---
Tags: machine-learning, clustering
---


title: Balanced Network max flow review

text:
# Question
Title: Balanced Network max flow review
I would like a review for my algorithm for the following question:
A flow network is a “balanced network” if for every $v∈V- {s,t}$ it holds that $c\_in (v)=c\_out (v).$ Let G be a balanced network in which in-degree(s)=out-degree(t)=0
Find max-flow for G. My Algorithm so far:

1. We will define the following capacity-function: $∀(u,v)∈E,f(ⅇ)=c(ⅇ)$
2. Run over the adj. list and update for every edge it to be our function, and return c(e)

I was also wondering how to prove its a max flow in the correctness part Thank you

# Answer
> 1 votes
1. The flow defined by you, satisfies both the constraints: a) conservation of flow at each vertex -- by the definition of balanced network and b) the capacity constraint because $f\_{e} = c\_{e}$ for every $e \in E$. Therefore, it is a valid flow.
2. It is a max-flow because it is sending the flow of value which is equal to the *capacity* of the cut $C$ defined as: $\\{s\\}$ and $V \setminus \\{s\\}$, i.e. max-flow = $\sum\_{(s,u) \in E} c(u,v)$ since there is no incoming edge to $s$. Note that any flow can not exceed the capacity of this cut. This fact follows from the *min-cut max-flow theorem*. i.e., **max-flow** $=$ **min capacity of an** $s$-$t$ **cut** $\leq$ **capacity of cut** $C$. Therefore, what we have is a max-flow.

---
Tags: algorithms, network-flow
---


# Question
Title: Segmented address / normal virtual address
In a cpu with segmented memory, can an address only be accessed with a segmented address, or can a normal virtual address also be used?

# Answer
A virtual address is not normal. It is used with paging. "Normal addresses" are direct physical addresses which access main memory directly. Intel's terminology says that virtual address will be translated by the segmentation unit to a linear address. The linear address will then be translated to physical address by the MMU.

With that said the answer to your question is quite complex since it involves understanding operating-system development concepts.

**Real mode**

x86 CPUs start with the 8086. Today, the 8086 is emulated at startup of every x86 processor for backward compatibility with older software. This is called real mode. In real mode physical addresses are calculated using the address you specify in the assembly code by implicitly adding ds as the segment selector. They are calculated by the formula `ds * 16 + offset`. For example,

```
mov ax, 0
mov ds, ax
mov word [0x1234], 0x1234

```

will move 0x1234 to the physical address `0x0 * 16 + 0x1234 = 0x1234`. With ds set as 0, real mode segmentation is ignored because the address you specify is translated to itself.

**Protected mode**

After real mode the OS will jump to protected mode. In protected mode there is segmentation and paging available for more recent CPUs. Before paging, there was only segmentation. Paging is more modern than segmentation. For an example on how to set up protected mode in NASM assembly look at the following code:

```
cli

lgdt[gdtr]

mov eax, cr0
or al, 1
mov cr0, eax

jmp 0x08:protectedMode       ;0x08 = 0b1000, 1 for segment selector
                             ;0 for gdt not ldt and 00 for privilege
bits 32
protectedMode:

gdt_start:
        dq 0x0      ;null descriptor
gdt_code:
        dw 0xFFFF   ;limit 0-15
        dw 0x0      ;base 0-15
        db 0x0      ;base 16-23
        db 10011010b    ;pr, privi (2), s, ex, dc, rw, ac
        db 11001111b    ;gr, sz, limit 16-19
        db 0x0      ;base 24-31
gdt_data:
        dw 0xFFFF
        dw 0x0
        db 0x0
        db 10010010b
        db 11001111b
        db 0x0
gdtr:
        dw 24
        dd gdt_start

```

The code disables interrupts, loads a GDT, enables protected mode by setting a bit in the CR0 control register then jumps to protected mode in segment 0x08. Segment 0x08 is the code segment. Segment 0 being the null descriptor. Here segmentation is enabled with a flat memory model.

The flat memory model is where you specify a base of 0x0 and a limit of 0xFFFFF with a granularity (gr) of 1. The granularity specify if the limit will be in blocks of 1 byte (0) or 4KB (1). If the limit is in blocks of 4KB and the base is 0 then the segment will span the whole 4GB available address space in protected mode (with a limit of 0xFFFFF). The flat memory model is often used in modern operating systems because it simplifies operations in transition modes before long mode is enabled.

**Long mode**

To enable long mode, you must enable paging and set certain bits in some registers. The following code enables long mode in NASM assembly:

```

mov eax, cr4            ;enable PAE-paging
or eax, 1 << 5
mov cr4, eax

mov ecx, 0xC0000080     ;set long mode bit in EFER MSR
rdmsr
or eax, 1 << 8
wrmsr

mov eax, cr0            ;enable paging
or eax, 1 << 31
mov cr0, eax

lgdt[gdtr]          ;load a 64 bit gdt (will be ignored afterwards)

jmp 0x08:longMode

bits 64

longMode:

gdt_start:
        dw 0xFFFF
        dw 0
        db 0
        db 0
        db 1
        db 0
gdt_code:
        dw 0x1111   ;limit 0-15
        dw 0x0      ;base 0-15
        db 0x0      ;base 16-23
        db 10011010b    ;pr, privi (2), s, ex, dc, rw, ac
        db 10101111b    ;gr, sz, limit 16-19
        db 0x0      ;base 24-31
gdt_data:
        dw 0x0000
        dw 0x0
        db 0x0
        db 10010010b
        db 00000000b
        db 0x0
gdtr:
        dw $ - gdt_start - 1
        dq gdt_start

```

The 64 bits GDT is necessary because as stated on osdev.org

> Notice that we set a 4gb limit for code. This is needed because the processor will make a last limit check before the jump, and having a limit of 0 will cause a #GP (tested in bochs). After that, the limit will be ignored.

So basically, before we jump in the 64 bits code selector to enter long mode, the processor makes a last limit check. After that, the limit is ignored. This is evident since the limit is only 20 bits and, with a granularity of 4KB, this limits the segments to 4GB. In long mode you have access to much more RAM than that.

Once in long mode, you have paging enabled and everything but the CR3 register is translated by the MMU to a physical address. Everything is a virtual address. Segmentation is ignored.
> 2 votes

---
Tags: memory-management, memory-hardware, memory-access, virtual-memory
---


# Question
Title: Does any language need to have a bottom type?
From wikipedia:

> In type theory, a theory within mathematical logic, the bottom type is the type that has no values. It is also called the zero or empty type, and is sometimes denoted with the up tack (⊥) symbol.

The "bottomest" types I can think of in js are `undefined` and `null`, both unity types.

Notice how in TypeScript there is the explicit `never` bottom type for function that are not supposed to return anything, or to always throw an exception.

The question is/are:

1. does JavaScript have no bottom type?
2. if so, does that mean that languages do not need to have a bottom type?

# Answer
> 8 votes
Javascript has no bottom type. It does not even really have types in the sense of type theory. Instead, values are tagged with information that is called "dynamic type".

Programming languages typically do not have the bottom type (it is also called the empty type) because they allow defintion by general recursion, which implies that all types are non-empty. For example, to define a value `v` of any type `T` in Java, we can do this:

```
static T f() { return f(); }
static T v = f();

```

# Answer
> 2 votes
In actual programming languages, a function is not forced to deal explicity with input is not meant to. For a function `f(x)` you can say something like:

```
// x must satisfy x != 0, otherwise inv(x) results in undefined behaviour.
double inv(double x) { return 1/x; }

```

In computer since though, using $\bot$ is a very useful symbolic tool to express such indefinitions in piecewise-defined functions:

$$ f(x):\Bbb R\rightarrow\Bbb R = \begin{cases} \frac{1}{x} & \quad x\neq 0\\ \bot & \quad\text{otherwise} \end{cases} $$

So in short no, a programming language doesn't require to have any equivalent symbol. A language is only required of course of having tools for implementing well-defined cases. Any other precondition could be expressed in comments, documentation, etc, so the responsability of checking the input is transfered to the caller (this strategy is called design by contract).

**NOTE:** Some languages also have exceptions, but exceptions are more of a helper tool for error handling methods and not so much for expressing undefinition.

---
Tags: type-theory
---


# Question
Title: If i use other peoples code for my final year project does that come under Plagiarism?
I want to make a facial recognition project but my coding ability is very limited so I am going to be relying on other peoples code but if i use their code even if i change the variables and make different functions to add their code under would that still be considered plagerism ?

# Answer
You should clearly talk to your supervisor or advisor about this, however there are some general principles you are often overlooked by students when doing their final year projects in computing disciplines.

Firstly you should be clear what plagiarism really is and fully understand it. Plagiarism is presenting someone else's work as your own to gain credit for it as if you had created it yourself. However, we all use the work of others. We read books, we read tutorials on the Internet, we read things on Stack Exchange. We should, if doing this properly be citing the work of others properly so it is clear when ideas, code, formulas and other elements of our work are attributable to others. If we have properly attributed the work, then those who assess you can clearly see which parts are yours and which are not. Then no plagiarism is involved. A good student **will** be reading much and citing much and will be including the work of others. It is just they cite it well. A weak student may often be someone who has read little, used little, cites nothing and hands in little. A really bad student would just hand in someone else's stuff. Hopefully the boundaries are a little clearer.

The next element, particularly for Computer based projects, is to realise that we are using the work of others and including it in our project all the time. You will be using an operating system, you will be using a language invented by someone else a compiler built by someone else that interacts with run-time libraries that were supplied with it. Yet, despite doing this all the time students worry little about these elements that were included in their submitted project. Where is the dividing line between the bits that are incorporated in your work and what you did? Who can tell? This is why citing everything you used is important.

The only way to really make the whole project fully self-created, you would *in extremis* have to start with clean sand, make your own processor chips to your own design, write the operating system and compilers for them to your own design and then use that as a platform for your project. But, of course, that is totally preposterous.

As Isaac Newton is credited with saying, we can see so far because we are standing on the shoulders of giants. You should do the same. Select the best components and use your skill and education to assemble them into the best creation that is your project. All good things are just made from components that are acknowledged and this is not plagiarism. The skill is in using the right components assembled in the right way.

How many of those things should be hand-crafted by you and how many are imported is the guidance you get from your project supervisor.
> 1 votes

---
Tags: algorithms, machine-learning, artificial-intelligence, neural-networks, python
---