# Question
Title: Fundamental motivation behind the use of bits and binary representation
This is a naive question, but what makes binary representation special from a theoretical standpoint and from the standpoint of information theory?

If for technical reasons building ternary computers where the information is encoded as trits was easier than building traditional binary computers, I get the feeling that most theoretical computer science and information theory would still use bits and base-2 representation by default.

Even if I have an intuitive feeling of why, I would have liked to know a formal explanation of that: from a purely theoretical standpoint what makes bits and binary representation special compared to any other base?

If the answer is more complex than one may first think, links to books and scientific papers are welcome.

# Answer
Well, the fact is that binary values *are* much easier to handle technically that ternary values. And there are reasons for it. So if there was some technical breakthrough where suddenly ternary values become easy to handle, there would be a good reason to believe that binary values would have a similar breakthrough very soon.

So yours is a purely hypothetical question. And you are making assumptions about how people would react in a purely hypothetical situation.

In lots of situations, for many algorithms, binary or ternary doesn't matter. At a high level, we just talk about integers. But for many basic operations, ternary is at a disadvantage. Design a format for signed integers. Preferably one where the same representation is used for positive signed integers and for unsigned integers. You have a problem unless you use one trit and use it as a sign bit. Which means you now have a representation where not every trit value is valid.

Floating-point arithmetic: I don't remember if it was Knuth and Kahan who showed that "round to nearest even" has some very nice properties, and then showed that you have these nice properties whenever the floating-point base is 8k + 2 (including binary and decimal, what a luck) but not for base 3.

Design the logic for a full-adder. Two inputs from 0 to 2 and one input 0 or 1 (the carry from the previous operation). Quite complicated. Much much more complicated than binary. Going one level down, is there anything like NAND and NOR for trits that can serve as the basis of all logical operations? Try creating a fast multiplier. For binary, the basis for this is an operation which produces x\*0 or x\*1. Now you need something that produces x\*0, x\*1 or x\*2. Wait, that can't be stored in a single trit. Trouble. Plus you can't use the ordinary full adder to finish off the fast multiplier.
> 1 votes

# Answer
There are two parts to the answer.

One part is about how computers are designerad internally. There is altardy a good answer to that.

The other part is about information theory. In information theory the unit is bits.
> 0 votes

---
Tags: information-theory, coding-theory, binary, bit-manipulation
---


# Question
Title: Algorithm undirected graph to directed strongly connected graph
For an undirected connected graph $G=(V,E)$ given as adjacency list I want to find a directed strongly connected graph $G=(V,E')$ where each $e' \in E'$ is either $(u,v)$ or $(v,u)$ if we look at its original $e=\\{u,v\\}$. Also we're assuming there are no bridges in the given graph G (which I'm checking before hand).

# Answer
The idea is that if we find a cycle in $G$, then we can orient its edges so that the nodes in the cycle will be all strongly connected. The cycle can then be collapsed into a single node. If the graph had no bridges the new graph will also have no bridges and this procedure can be repeated. Eventually, you will be left with a single node, meaning that the whole graph is a single strongly connected component, as desired.

More precisely, you can iteratively do the following:

* Find a cycle $C $in $G$;
* Orient the edges of $C = \langle u\_1, u\_2, \dots, u\_k, u\_{k+1} = u\_1 \rangle$ in an arbitrary but consistent direction w.r.t. $C$. For example, for $i=1, \dots, k$ orient $(u\_i, u\_{i+1})$ towards $u\_{i+1}$;
* Orient the chords of $C$ in an arbitrary direction.
* Identify the vertices in $C$, possibly creating parallel edges (but ignoring self-loops). This means replacing $u\_1, \dots, u\_k$ with a new super-vertex $\overline{u}$. For every edge $(x,y)$ where $x \in C$ and $y \not\in C$, add a new edge $(\overline{u}, y)$.
* Repeat until a single vertex is left in $G$.

Notice that if there are two or more vertices left in $G$ then there must still be a cycle (otherwise there is a bridge that was also bridge in the original graph). This means that you will eventually be left with a single vertex. When this happens, all edges in the original graph $G$ must have been assigned a direction and you are done.

If you think of using the above algorithm while performing a single DFS visit to discover the cycles to contract, then all the cycles $C$ will be of the form $\langle u\_1, \dots, u\_k, u\_{k+1} = u\_1 \rangle$, where for $i=1,\dots,k-1$, $u\_{i}$ is the parent of $u\_{i+1}$ in the DFS tree, and $(u\_k, u\_1)$ is a back-edge. If you use the above choice for the orientation of the edges of $C$, then this is equivalent to this simpler algorithm:

* Perform a DFS visit of $G$ from an arbitrary vertex $r$ to obtain a tree $T$.
* Orient all the edges of $T$ away from $r$.
* Orient the edges not in $T$ towards $r$ (notice that this is well defined since there will be no edges between two nodes at the same depth in $T$).

You can also give a direct proof that the orientation $G'$ computed by this second algorithm is a strongly-connected graph. It is clear that there is a path from $r$ to any other vertex in $G'$. The following claim implies the converse.

**Claim:** Let $(u,v)$ be an edge of $T$, with $u$ being the parent of $v$. There is a path from $v$ to $u$ in $G'$.

Proof: Since $(u,v)$ is not a bridge, there must be a cycle of the form $C = \langle u\_1 = u, u\_2 = v, u\_3, \dots, u\_k, u\_{k+1} = u\_1 \rangle$. Let $i$ be the smallest index in $\\{1, \dots, k\\}$ such that $u\_i$ lies in the subtree $T\_v$ of $T$ rooted at $v$ and $u\_{i+1} \not\in T\_v$ (this edge must always exist). Since $u\_i \in T\_v$, there is a (possibly empty) directed path $P$ from $v$ to $u\_i$ in $G'$. Since $u\_{i+1}$ is an ancestor of $v$ and $u\_{i+1} \not\in T\_v$, $u\_{i+1}$ must be an ancestor of $u$ (possibly $u$ itself). This means that there is a (possibly empty) directed path $Q$ from $u\_{i+1}$ to $u$ in $G'$. Finally, $(u\_i, u\_{i+1})$ is not a tree edge, hence it is directed towards $u\_{i+1}$. This means that $P \circ (u\_i, u\_{i+1}) \circ Q$ is a path from $v$ to $u$ in $G'$ (where $\circ$ denotes concatenation). $\quad\square$
> 3 votes

---
Tags: algorithms, graphs
---


title: Meaning of $a\lor b \to b' \lor c'$

text:
# Question
Title: Meaning of $a\lor b \to b' \lor c'$
So I have done part **a)** but I have no clue what I am supposed to do for part **b)**, I have been trying for days to wrap my head around and even asked my fellow course mates, none of which seem to know themselves.

The way I understand it they give me automaton of

> a-\>b-\>c

But what do they mean about the next state a',b',c' automaton for which is not displayed.

# Answer
If the current state is one of $a,b$, then the following state is one of $b,c$.
> 1 votes

---
Tags: finite-automata, logic
---


# Question
Title: Simplification of a multi-index Boolean expression towards computation in fewer steps
Let $x\_{ij} \in \\{0,1\\}$, $1 \leq i \leq M$ (typically, $M = 2000$), $1 \leq j \leq N$ (typically, $N = 10$), be Boolean variables. If possible at all, I would like to simplify the following expression $$ \bigvee\_{i\_1,\dots,i\_N} \left(\bigwedge\_{k=1}^N x\_{i\_k k} \right), $$ where the join operation is taken over all indices $(i\_1,\dots,i\_N) \in \\{1,\dots,M \\}^N$, so that it can be computed faster instead of looping through all multi-indices.

Apologies if this is a well-known problem (with or without solution). This is very much outside of my field of expertise, so I am hoping someone around here could give some feedback on it. Feel free to edit the tags as you see more appropriate.

Thanks!

# Answer
> 2 votes
It is equivalent to

$$\bigwedge\_{k=1}^{N} \bigvee\_{i\_k=1}^{M} x\_{i\_k k}.$$

This is a much simpler expression: $NM$ terms instead of $M^N$ terms, if you expand everything out.

---
Tags: algorithms, logic, boolean-algebra, performance
---


# Question
Title: How many "compressible" strings are there?
Let's say that a string of length $N$ is "compressible" iff its Kolmogorov complexity is less than $N$. To keep it simple, we can assume binary strings for this.

It is easy to see that almost all binary strings of length $N$ are incompressible by using the pigeonhole principle.

So my question is, how many strings of length $N$ *are* compressible?

In particular, let's assume that $K(S)$ is the Kolmogorov complexity of binary string $S$, which is of length $N$. Then I have the following three questions:

1. Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N-1$?
2. Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq N/2$?
3. Of the $2^N$ binary strings $S$ of length $N$, how many have $K(S) \leq \log N$?

All of the above are for sufficiently large $N$.

# Answer
A simple counting argument shows that the number of strings of length $N$ such that $K(S) \leq M$ is at most $2^{M+1}$.

Conversely, considering the program $\Pi$ that gets an integer $r$ and a string $x$, and outputs $x$ together with $r$ many zeroes. Going over all strings of length $\ell$, this gives us $2^\ell$ many strings whose complexity is at most $\ell + O(\log N)$. Choosing $\ell = M - O(\log N)$, this shows that the number of strings of length $N$ such that $K(S) \leq M$ is at least $2^M/N^{O(1)}$.

This answers your first two questions up to a small multiplicative error. I suspect that the answer to the third one depends heavily on $N$.
> 6 votes

---
Tags: strings, data-compression, kolmogorov-complexity
---


title: Evaluating predicate on binary strings

text:
# Question
Title: Evaluating predicate on binary strings
Consider two *unknown* binary strings $$X = x\_{1} x\_{2} \dots x\_{n^{2}}, \quad Y = y\_{1} y\_{2} \dots y\_{n^{2}}, \quad x\_{i}, y\_{i} \in \\{0, 1\\} .$$ We may request a string $Z = z\_{1} z\_{2} \dots z\_{n^{2}}$, where $z\_{i} = x\_{i}$ or $z\_{i} = y\_{i}$, no more than $n + 1$ times. So, for every request we set required $z\_{i}$ (that is, $x\_{i}$ or $y\_{i}$) for every $i$.

Moreover, we have $n$ bits of unwritable memory, namely, every bit of that memory is set once and then does not change. This memory is avaliable all the time, but requested $Z$ strings drop out before the next request, so, we don't have complete list of all requested $Z$ strings.

The problem is to check if $X = Y$ with given $n$ bits and $n + 1$ times for $Z$ string request.

There is an extra question: is it possible to use $\mathcal{O}(\log^{2}(n))$ bits of memory and $\mathcal{O}(\log(r))$ requests.

I don't really understand area of CS that is closely related to the problem, could anyone give a hint?

# Answer
> 0 votes
You can think of $X,Y$ as $n\times n$ matrices with rows $a\_1,\ldots,a\_n$ and $b\_1,\ldots,b\_n$, respectively. Then $X = Y$ iff $$ a\_1 \oplus \cdots \oplus a\_n = b\_1 \oplus a\_2 \oplus \cdots \oplus a\_n = b\_1 \oplus b\_2 \oplus a\_3 \oplus \cdots \oplus a\_n = \cdots = b\_1 \oplus \cdots \oplus b\_n. $$

---
Tags: strings, bit-manipulation
---


# Question
Title: Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?
So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time complexity faster than O(N log N)? So I'm going to go into what I've been pondering, but have a couple specific questions at the bottom.

**Comparision based** So the baseline case would just be to compare every element in array\_a against every element in array\_b, being O(N^2). So what I was thinking was using a sort O(N log N), and then iterating through each of the arrays, making comparing array\[i\] with array\[i+1\], if they are not equal, copy array\[i\] to a new array (or a linked list, since I'd just be accessing it in order for the next step) and then increment i, so that way I have arrays without duplicates. Then do a preliminary check to see whether the # of elements are the same in both lists. Then with the list, compare whether the first element in the linked lists are equivalent, then check the next node in the linked list, and so on. If all checks are equal then they represent the same set. So this would be O(N log N). Doing a sort with a tree might work as well, but again would still be in the same complexity class of O(N log N)...

**Hashing?** So what I was thinking initially was looking at using hashsets to remove duplicates since operations with those would be amortised constant time, doing a preliminary check by checking whether both arrays have the same amount of distinct elements, adding the hashes of the elements of both arrays if they are not equal then there's no point in checking every element of each array and comparing it so that way a response of false would be relatively quick, if they are equal, then to check against collisions I'd sort it and then check arr\_1\[i\] with arr2\_\[i\] for i = 0, ..., n-1 - so the step of sorting would be the slowest giving this a time complexity of O(n log n) based on the sorting function used.

**Questions** Other than using hashing-based structures or algorithms that would require elements to be sorted first,, what other data structures (like trees would work I'd supposed) could I use to remove duplicates in an efficient way? Are there any novel data structures (even if impractical in practice) or different approaches for removing duplicates?

If the only information known about the sets is that they have a total order relation, would this make any impact on whether each element can be hashed and the quality of the hashes on a theoretical point of view?

Are there any properties in set theory that I could exploit somehow for a faster algorithm design in a language-agnostic way?

# Answer
I believe a hashing approach should give you $O(N)$ time, where $N$ is the length of the longer array (we can relax the constraint that they are the same size).

Simply put all the elements in the first array into a hashset, and then check whether each element in the second array exists in the hashset.

You could even account for duplicates by instead using a hashmap and storing the counts of each element in the first array. When checking elements in the second array for inclusion (or nonzero value), decrement the value of each key that is a match.
> 4 votes

---
Tags: complexity-theory, graphs, runtime-analysis, sorting, sets
---


title: Injective burrows wheeler

text:
# Question
Title: Injective burrows wheeler
We know that the Burrows-Wheeler Transform is reversible, in the sense that, given s=BWT(w) and an index I, it is possible to recover w by an algorithm. But how to prove that w is unique? In other way how to prove that Burrows-Wheeler is injective?

# Answer
> 0 votes
Let $\mathsf{BWT}^{-1}$ be the inverse Burrows-Wheeler transform, that is, $\mathsf{BWT}^{-1}(\mathsf{BWT}(w)) = w$.

If $\mathsf{BWT}(x) = \mathsf{BWT}(y)$ then $$ x = \mathsf{BWT}^{-1}(\mathsf{BWT}(x)) = \mathsf{BWT}^{-1}(\mathsf{BWT}(y)) = y. $$

---
Tags: algorithms
---


# Question
Title: How to find maximum matching edges in undirected tree
Let $B$ be an undirected tree with $|V|$ nodes given as adjacency list. I want to develop a greedy algorithm using pseudo code to find a maximal matching in runtime $\mathcal{O}(|V|)$.

**My approach:**

Find all leaves. For each leaf if the parent edge has not been seen by another leaf, mark the edge to its parent as matching edge. Now delete all found leaves, its parents and the associated edges of the parents. Start over from the beginning.

**Pseudo code:**

```
graph = {
     1: [2, 3],
     2: [1, 4, 5],
     3: [1, 6],
     4: [2, 7, 8],
     5: [2, 9],
     6: [3],
     7: [4, 10, 11],
     8: [4, 12, 13],
     9: [5],
    10: [7, 14],
    11: [7],
    12: [8],
    13: [8, 15, 16],
    14: [10],
    15: [13],
    16: [13],
}
# example graph I used for testing purposes

while we haven't seen all nodes:
    leaves = [i for i in graph if len(graph[i]) == 1]
    seen += leaves
    for leaf in leaves:
        parent = graph[leaf][0]
        del graph[leaf]  # Throw away all leaves
        if not parent in seen:
            del graph[parent] # And throw away their parent
            matching_edges += [(leaf, parent)]
            seen += [parent]
            next_round_nodes += [parent]

```

But I'm afraid that is not linear, is it? Because first we look at $|V|$ and perform our algo. Then we do the same with $|V|-c$ leaves, where $c$ could actually be 2, if I understand that correctly, looking at graph which is a "line". So, really that seems quadratic.

**TL;DR:**

1. Is my algorithm correct?
2. What is the runtime?
3. If it is not linear, what other approach could I chose?

# Answer
It is correct and runs in linear time. You can run a DFS to find the height and the parent node of each vertex and visit the vertices according to their heights in ascending order.

The correctness of such algortihms is usually proved using an exchange argument. Assume $M$ is the matching computed by your algortihm and $M\_{\mathrm{OPT}}$ an arbitrary maximum matching. Show that you can turn $M\_{\mathrm{OPT}}$ into $M$ by removing and adding edges to the matching where its size never gos smaller.
> 0 votes

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


# Question
Title: Why can humans solve certain "undecidable" problems?
High-order pattern matching is an undecidable problem. That means there is no algorithm that, given an equation `a => b`, where `a` and `b` are open terms on the simply typed lambda calculus, finds a substitution `S` such that `aS => bS`, where `=>` stands for "has the same Bn normal form". Yet, humans can solve that problem efficiently. For example, given the following problem:

```
a = (λt . t
    (F (λ f x . (f (f (f x)))))
    (F (λ f x . (f (f x)))))
b = (λ t . t
    (λ f x . (f (f (f (f (f (f x)))))))
    (λ f x . (f (f (f (f x))))))

```

Any human with sufficient knowledge on the lambda calculus will be able to notice `F` is the "double" function for church numbers, quickly coming with the solution that

```
 F = (λ a b c . (a b (a b c)))

```

My question is: if that problem is undecidable, how can humans quickly and effortlessly solve it?

# Answer
> 88 votes
Humans can solve *some instances* of that problem efficiently, but there is no reason to believe that humans can solve *all instances* efficiently. Showing one instance that a human can solve efficiently does not imply that humans can solve all instances efficiently.

Undecidable means "there is no algorithm that can solve all instances and that always terminates". There could still be an algorithm that can solve *some instances*, even for an undecidable problem.

So there is no contradiction.

# Answer
> 4 votes
As one of the comments notes, one should be aware that there are some pretty good algorithms for solving Higher Order Pattern Matching *in practice* (as a quick google search will reveal).

I don't know of any that solve this particular problem, but this "doubling" problem feels closer to the field of program synthesis. I do believe that there are program synthesis systems which can tackle this kind of problem.

It's easy to create examples which make those system choke though, and it does seem that humans are particularly good at these kinds of problems. Creating algorithms which are closer to humans in their ability to solve these kinds of problems is the purview of **automatic theorem proving** and **artificial intelligence** (for the more ambitious/unrealistic attempts).

# Answer
> 3 votes
Humans can solve *some* instances of undecidable problems and so can computers. Computers cannot solve *all* instances of undecidable problems, and not can humans.

# Answer
> 1 votes
Humans always try to solve the problem with their own knowledge , so humans develop some algorithm to solve the problem with some instances of problem .So human develop an algorithm, but there is no surety that the particular algorithm can solve every single problem . So no algorithm can solve every problem , but there is still some problem that can be solve by human even though there is not a perfect algorithm for that like we can say that we know how to solve a problem but we don't have an algorithm.

---
Tags: computability, philosophy, computer-vs-human
---


# Question
Title: Standard information-theoretic lower bound?
There should be a simple argument, but I'm struggling to see it.

Suppose Alice has a string $x \in \\{0, 1\\}^n$ and sends a message $s = s(x)$ to Bob. And suppose that given $s$, Bob can reconstruct *each* bit of $x$ with probability $2/3$ (say). (Note that this is weaker than the claim "with probability $2/3$, Bob can recover the entire string $x$." A clean proof of this case would be appreciated too.)

Then we should be able to conclude $|s| = \Omega(n)$, and this seems obvious, but can someone formalize this for me?

# Answer
> 3 votes
I understand your question this way:

> Assume Alice has some $X\in\\{0,1\\}^n$. Alice encodes (compresses) $X$ into $s = s(X)$, where $|s|\le n$. Bob decodes $s$ to obtain $X'=dec(s)$. Show that unless $|s|=\Omega(n)$ it cannot hold that Hamming$(X,X') \< n/3$.

If this is what you meant, then this follows from the fact that most strings cannot be compressed. Assume that for any $X$, $|s(X)|=o(n)$. Note that there are at most $2^{|s|}\ll 2^n$ such strings. More accurately, $2^{|s|} / 2^n \to\_{n\to\infty} 0$.

Then, for each possible $s$ construct $dec(s)$ and define $Y\_s$ to be a Hamming ball of radius $n/3$ centered at $dec(s)$. Verify that $|Y\_s| = \sum\_{d=0}^{n/3}\binom{n}{d} \< 2^{n\cdot h(1/3)}$, with $h(\cdot)$ the binary entropy function. Thus $\left|\bigcup\_s |Y\_s|\right| \le 2^{o(n)}2^{0.92n} \ll 2^n$. This means that there exists a string $X$ not covered by the $Y\_s$ for any $s$, i.e., not within a Hamming-distance of $n/3$ from any of the decoding of any $s$.

---

If this is not what you meant, you will have to formulate your statement in a proper way. For instance, you say "with probability 2/3", but there is no probability space defined in your statement, etc.

---
Tags: information-theory, lower-bounds
---


# Question
Title: how to check whether a flow network contains unique maximum flow?
I have been stuck on this problem for few hours, my assignment asks to design an efficient algorithm(polynomial running time) that check whether a given flow network graph contains a unique maximum flow or not. I have been search everything I could, and some people said run an algorithm that able to find a max flow first, then modified the edges capacity, and run the algorithm one more time to see if we get the same flow value. But this seems never works for me especially when we are given arbitrary flow network, like non-integer flow graph. How should I start a good approach? (Literally stuck for few hours)

# Answer
Find a maximum flow. Then create m new flow networks: one for each edge in the maximum flow. In each new configuration, reduce the capacity of one of the edges to an amount just below its flow. Find the maximum flow on each of the new flow networks. If any of the new configurations generate the same maximum flow value as the original graph, then that new flow is also a maximum flow in the original graph. Hence, the original maximum flow is not unique.
> 4 votes

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


# Question
Title: Optimal flow in a network with non-constant edges' weights
I've recently come across the problem that seems to be quite interesting but i don't know how to tackle it. I suppose that it might be a special case of maximum flow problem but it seems to be rather different so i need an advice.

Suppose that we have a weighted directed graph with two (possibly the same) vertices designated as "source" (S) and "target" (T). We can imagine that vertices represent the currencies and edges are conversion options. There is some initial amount of money in vertex S and it has to be converted to vertex T in such way that the resulting sum is maximum possible.

Conversion can be done in parts so if there is some sum S at vertex V and there are several edges coming from V then we can send different amounts of money along these edges (i.e. we are not obliged to use only one edge or to divide the sum in equal parts or to use multiples of some fixed lot etc.). We are also not obliged to convert total sum. It can be the case that the best option is to convert some part of it.

Now comes the trickiest part. Each edge's weight depends on amount of money that must be transported through an edge. For each edge E there is some function F(E) that receives amount of money entering the edge and returns amount of money leaving the edge. We can assume that ratio of output/input gets smaller when input gets bigger.

Thank you very much for any ideas. Any help will be highly appreciated.

# Answer
Your problem is a generalization of the Longest Path problem, which is NP-hard. If the functions are constant and every conversion increases the amount of money, then there's no reason not to convert all of the money at once. At that point, you are just looking for the longest path.

Your generalization, allowing partial conversions, non-constant functions, etc. cannot be easier than that.
> 2 votes

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


# Question
Title: How to prove NP-completeness of this variant of the set cover problem?
The problem exactly:

Suppose you're helping to organize a summer sports camp, and the following problem comes up. For each of the n sports offered at this camp, the camp is supposed to have at least two counselors who are skilled at this sport. They have received job applications from m potential counselors. For each of the n sports, there is some subset of m applicants qualified in that sport. The question is: For a given k \< m, is it possible to hire at most k of the counselors and have have **at least two** qualified in each of the n sports?

So, you are given a set U of elements, a collection of S1, S2...SM subsets of U, and an integer k. The original vertex-cover problem asks if there exists a collection of \<= k of these sets whose union is equal to U. This question seems to ask how would we prove this is NP-Complete if we instead had to find a collection of \<=k of these sets whose union covered the elements in U at least twice.

My first thought was to try to reduce the set cover problem. I was going to try to extend it to make it have to cover the union twice, but have no idea how to do that.

My next thought was to use 3-SAT since everything comes from that it seems, but I will die of old age before I figure that out.

My question is, what problem should I try to reduce from? Any could I get a hint for a first step to take? I've never proved one of these before so I'm really lost. I've been staring at this problem for 3 hours now.

# Answer
> 1 votes
Your first guess is correct. You misinterpreted however the meaning of reductions. When we prove the hardness of a problem $A$ by a reduction from $B$, we aim to reduce $B$ to $A$ and hence, given an instance $I$ of $B$, we want to build an instance $I'$ of $A$ such that $I$ is a yes-instance if and only if $I'$ is.

Now by reducing set cover to your problem, given an instance $(U, \mathcal{F}, k)$ of set cover, where $U$ is the universe, $\mathcal{F} := \\{F\_1, \dots, F\_m\\}$ the collection of sets and $k$ the maximum number of sets in the answer. We build the instance $(U, \mathcal{F}', k')$ as follows. If $k$ equals 0, then we output No. Otherwise, if $U \in \mathcal{F}$, we output yes. Else, Let $\mathcal{F}' := \mathcal{F} \cup \\{U\\}$, which means we add a new set to the collection, namely the set consisting of the whole universe. We also set $k' = k + 1$. We claim the original insatnce has a solution of size $k$ for the set cover problem if and only if the new instance has a solution of size $k+1$ of your problem.

For the first direction, given a solution of size $k$ for thr set cover problem, add the new universal set to the solution to build a solution for your problem of size $k+1$. (Why does this work?)

Now the harder direction, given a solution for the built instance of your problem of size at most $k+1$, if the universal set is a part of thr solution, the we can remove it to get a solution for the original insatnce of set cover with size at most $k$. If the universal set is not present, then remove any set from the solution (since you can switch this set with the universal set getting back to the previous case).

By this far we proved the hardness of the problem. For the completeness proof, note that given a solution of size $k+1$, we can count for each element in the universe how many times it was covered in the solution in polynomial time. Hence we can proof a positive witness in polynomial time and the problem is NP-complete.

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


# Question
Title: Are there any proofs of exponential lower bound time complexity
I'm trying to understand what are the techniques to prove an exponential time lower bound.

For some problems, we can prove that the size of the output is exponential is the size of the input, thus it takes an exponential number of steps just to write the output. For example for some generalized board games, if the input is the size of the board and the output is the sequence of winning steps.

But what about decision problems, where $|output|=1$ ? Are there any decision problems in $EXPTIME$ with known exponential lower-bounds ?

I don't see how we can prove such a lower bound. Like if we take again the generalized board game and ask the question if there is a winning strategy, we can prove that evaluating all strategies will take (in the worst case) exponential time, but how can we prove that evaluating all strategies is the only way to answer the question ?

Or if I take another example, if my input is a number $x$ and the output is $1$ iff there exist a permutation $p$ such as shuffling the bits of $x$ makes it prime, i.e. $p(x)$ is prime. Exhaustively exploring all permutations and running a primality test will probably be exponential in $|x|$, but what if there is a smart way to answer just by looking at $x$ (in sub-exponential time) ?

I hope that looking at an example of such a proof will help me grasp the principles involved.

# Answer
> 9 votes
The Time Hierarchy Theorem states that for any (reasonable) function $f$, there exists a problem that cannot be solved in time substantially faster than $f(n)$. The proof of this is similar to the proof of the undecidability of the Halting problem: we construct the decision problem "given a description of a Turing machine, does it halt in time at most $f(n)$ and then show that it cannot be decided substantially faster than $f(n)$, in a very similar way to showing that "does this Turing machine halt in finite time" cannot be decided (in finite time).

In the case of generalized board games (e.g., Chess), these are often $EXPTIME$-complete. This means any problem in $EXPTIME$ can be reduced in polynomial time to it. Since (by the Time Hierarchy Theorem) there are problems in $EXPTIME$ that cannot be solved in subexponential time, neither can Chess (or any other $EXPTIME$-complete problem).

Your other example (shuffling bits to get a prime number) probably doesn't require exponential time. The chance that a random permutation of the bits results in a prime is quite high, and only a polynomial number of guesses would be required to find a prime. The problem is in $NP$, so a proof that it requires exponential time would be a somewhat significant breakthrough.

# Answer
> 1 votes
Regarding the specific problem you pose about whether the bit of a number can be permuted to give a prime, I believe the following to be an algorithm in P.

If the number has fewer than 100 zeros in it or fewer than 100 ones in it, enumerate all permutations and test them all for primality using a primality test (e.g. AKS) and output accordingly. Otherwise output 1.

The correctness of this algorithm rests on the assumption that no number containing 100 ones and 100 zeros can't be rearranged into a prime. To see this heuristically, if $n$ is the number of ones and $m$ the number of zeros note that there are on the order of $(n+m)^{\min(n,m)}$ premutations and that $1$ in $\log(m+n)$ of them "should" be prime. Even summing over all $n,m\>99$, it seems very unlikely that there is an exception to this assumption.

That it is polynomial time follows from the fact that if $n\<100$ or $m\<100$ then the number of permutations is at most $(n+m)^{99}$ and each can be tested in polynomial time using AKS.

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


title: O(n) external intersection points?

text:
# Question
Title: O(n) external intersection points?
I have a doubt. For a given n (axis-parallel) squares in a plane, where there are Ω(n²) intersection points between the edges of the square, is it possible to have O(n) external intersection points? (external intersection meaning if the point is not contained in the interior of the union of all the squares).

# Answer
> 3 votes
Consider $n$ axis-parallel squares of equal size shifted along the line $y = x$ such that the bottom-left corners of the squares all fit within the first square. E.g. for $n = 4$:

Then you have $2(n - 1)$ external intersection points but $(n-1)(n-2)$ internal ones (and thus $n(n-1)$ total).

---
Tags: algorithms, data-structures, computational-geometry, discrete-mathematics
---


title: Graph 3-colorability is self-reducible

text:
# Question
Title: Graph 3-colorability is self-reducible
I am interested in self-reducibility of Graph 3-Coloralibity problem.

**Definition of Graph 3-Coloralibity problem.**

Given an undirected graph $G$ does there exists a way to color the nodes red, green, and blue so that no adjacent nodes have the same color?

**Definition of self-reducibility.**

A language $L$ is self-reducible if a oracle turing machine TM $T$ exists such that $L=L(T^L)$ and for any input $x$ of length $n$, $T^L(x)$ queries the oracle for words of length at most $n-1$.

I would like to show in very strict and formal way that Graph 3-colorability is self-reducible.

Proof of self-reducibility of SAT can be used as example (self-reducibility of SAT).

In my opinion, the general idea of proof of self-reducibility of Graph 3-colorability is different from proof of SAT self-reducibility in few aspects.

* SAT has two choices for every literal (true or false) and Graph 3-colorability has three choices (namely, red green blue).
* Choices of SAT literal are independent on each other and choices of colors of Graph 3 colorability are strictly dependent, any adjacent node must have different color, this property potentially could help to make less iteration among all colors.

**The general idea of proof**.

Let's denote by $c\_{v\_i}$ the color of the vertex $v\_i$, which can take one of the following values (red,green,blue). Define graph $G'$ from a given graph $G$ by coloring the arbitrary vertex $v\_0$, assign $c\_{v\_0}$ to 'red' and put the graph $G'$ with colored vertex $v\_0$ to the input of the oracle. If oracle answers 1, which means that the modified graph is still 3-colorable, save the current assignments and start new iteration, with the different vertex $v\_1$ chosen arbitrarily, color vertex $v\_1$ according to the colors of the adjacent vertices. if oracle answers 0, which means the previous assignment has broken 3 colorability, pick different color from the set of three colors, but still according to colors of adjacent vertices.

The previous proof is not mathematical robust, the question is how to improve it and to make it more formal and mathematical strict. It looks like I need more carefully distinguish the cases when new vertex doesn't have any edges with already colored vertices and when the new vertex is adjacent to already colored vertices.

In addition I would like to prove that Graph 3-colorability is downward self-reducible.

**Definition of downward self-reducible language.**

The language $A$ is said to be downward self-reducible if it is possible to determine in polynomial time if $x \in A$ using the results of shortest queries.

The idea seems to be simple and intuitive: start with coloring an arbitrary vertex, and on each iteration add one more colored vertex and check by oracle if graph is still 3-colorable, if not reverse previous coloring and check another color.

But how to write the proof in a strict way and more important how to find an appropriate encoding of a graph.

In short, I would like to show that Graph 3-colorability is self-reducible and downward self-reducible in strict and formal way.

I will appreciate sharing your thoughts with us.

**Update:**

**downward self-reducibility**

Downward self-reducibility is applied to decision problem and it's oracle answers the same decision problem with shorter input, at the end of the process of downward self-reduction we should have the right color assignments.

Every 3 - colorable graph $G$ with more than three vertices, has two vertices $x,y$ with the same color. Apparently, there is only three colors and more than three vertices so some number of non-adjacent vertices might have the same color. If we merge $x$ and $y$ with the same color as the result we still have 3 - colorable graph, just because, if graph is 3 - colorable, then there are exist right assignment of all vertices that are adjacent to $x$ and $y$ according to the same color of $x, y$, so by merging $x, y$ we don't need to change any color of any vertices, we only need to add more edges between already correctly colored vertices (I know it's not the best explanation, I will appreciate if someone could explain it better). On every iteration we take two non-adjacent vertices $x,y$ of graph $G$, merge $x$ and $y$ and get graph $G'$ which is our shorter input to the oracle. Oracle answers if it's 3-colorable or not. Now the problem is before setting $G'$ on the input of oracle I should color the merged vertex and test colorability of $G'$, if it's not 3-colorable change the color, but how to implement it correctly, I need right encoding for it.

**self-reducibility**

First, we should check if a given graph $G$ is 3-colorable at all, so set it on input of oracle, and oracle will answer if it's 3 - colorable, if yes then start the process. Any two nonadjacent vertices can have the same color in 3-colorable graph. The process of self-reducibility we should run in iterations, I think we can start from small subgraph $G'$ of a given graph $G$ and on every iteration add one more vertices from $G$ to $G'$. In paralel, we should maintain the assignment of already colored vertices. Unfortunately, I still don't get the idea completely. Would appreciate for help and hints.

# Answer
As Vor mentions in his comment, your reduction doesn't work, since 3-colorability doesn't accept partial assignments of colors. The problem goes even deeper, since setting the color of a single vertex doesn't make *any* progress in determining whether the graph is 3-colorable: indeed, the graph is 3-colorable iff there is a 3-coloring in which vertex $v$ is assigned color $c$, for any $v,c$ you choose.

Here is a hint on how to solve your exercise, second part. In any 3-coloring of a graph $G$ on more than three vertices, there are two vertices $x,y$ getting the same color (why?). If we merge $x$ and $y$, the resulting graph is still 3-colorable (why?). Try to use this idea to construct a downward self-reducing algorithm for 3-colorability.

Edit: And here is a hint on how to solve the exercise, first part. Consider any two unconnected vertices $x,y$. If there is a coloring in which they get the same color then $G\_{xy}$ is 3-colorable (why?), and a coloring of $G$ can be extracted from a coloring of $G\_{xy}$ (how?). When will this process stop?
> 8 votes

# Answer
Maybe like this. We can add two connected vertex l1 and l2. First, we connect them with any vertex v\*. Notice that this behavior means that at last, we just lock some color come vertexes including v\*.

Then we run the decision version of the 3-colorability, if the decision algorithm accepts, then we add this vertex into s\_1. we repeat this step with every vertex(connect l1 and l2 with another vertex), we will find that at last, all the vertex with the same color (denoted it by red) are found, and these vertexes with red color denoted by s\_1.

If there are any problem, please point out.

Next, just like what we do above, add another two connected vertexes(l3 l4), First, we connect them with any vertex except those in s\_1, run decision algorithm. Then another.....
> 0 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Trading Auction - Need help with calculating price / quantity of restricted underlying securities for matching
I'm having some difficulty with implementing a non-brute force algorithm for solving the following Problem. If I can get something even close to O(N^3) i'd be happy at this point.

Auction: https://www.investopedia.com/terms/a/auctionmarket.asp

I have an algorithm in place that can do a generic Auction (accumulating bids and offers over a fixed period of time, leading up to an event whereby bids and offers are matched to determine a reference price (the price securities are sold at in the auction)however we've just implemented a level of complexity that is throwing me for a loop.

We have a security with underlying shares that contain restrictions on who can own them. During an auction, we need to ensure that buyers can only buy shares they're allowed based on the underlying restriction.

Example:

Security: **Foo** -Class A Shares -Class B Shares -Class C Shares

Buy Orders

1. John can only buy Class A and Class B (Wants to buy 500 at $1.50)
2. Sally can only buy Class B, and Class C (Wants to buy 300 at $1.52)
3. Joel can buy any class. ((Wants to buy 200 @ 1.49)

Sell Orders

1. Xavier owns 500 (200 Class A, 300 class B) and is selling 400 at $1.42
2. Jennifer owns 1000 shares (800 Class B, 200 class C) and is selling 650 at $1.50
3. Martha owns 1500 shares (300 Class A, 1200 class C) and is selling 400 at $1.52

---

When a user puts in Buy / Sell auction order, they don't care what class of shares they're buying or selling, we can determine what they are buying or selling.

The goal is trying to find the price point where the most shares can be sold, while making sure that we're filling all orders that can be filled.

I've ran through multiple scenarios on calculating it from a price perspective, and the underlying class perspective, calculating the # of shares that can be sold at each price point, but I'm at a blank as each way I do it, i find I'm missing shares that could be traded.

Example: The following illustrates (when we have a correct price) that we also need to match buyer & seller using the most restricted / least tradable security so we match those who can't trade with much first, then go for those that are less restricted.

The above isn't hard to solve, it's getting to that point, to figure out the best price and tradeable amount.

Any thoughts or ideas on this?

# Answer
I would do this iteratively going through buyers ready to pay the highest price. I assume you can have partial fills if buyer and seller quantity don't match?

Step 1. Sort the buyers with MAX price at the top.
Step 2. Sort the sellers with LEAST price at the top.
Step 3. Take the topmost buyer from step 1 and try to fill its order, taking into consideration any restrictions, with a matching seller from the top. This will be your reference price. To match the seller you would need to traverse from top, comparing one by one to see which seller matches.
Step 4. Update the seller and buyer quantities based on the match in step 3.
Step 5. Repeat from step 1.

Hope that helps. Have a wonderful day!
> 0 votes

---
Tags: algorithms
---


# Question
Title: Why is finding the closest pair of points by brute force search O(n^2)?
If I have n points `A, B, C, D` it seems like finding the closest pair via brute force search would go like:

* Compare A to every item (n-1)
* Compare B to every item (except A which it has already been compared to)
* etc for every element.

This seems like it would be less than $O(n^2)$ because the you are comparing to a progressively smaller number of elements each time you go to the next element.

Can someone explain to me why this is $O(n^2)$?

# Answer
It's not clear what you think $O(n^2)$ means. $O(n^2)$ means that there is a constant $c$ so that, when $n$ is large enough, your algorithm takes no more than $cn^2$ time.

As you observed, the algorithm takes $(n-1)+(n-2) + \ldots + 1 $ time. This is equal to $\frac12 (n^2-n)$. This quantity is less than $2n^2$ whenever $n$ is larger than $10$. So it is indeed $O(n^2)$.

Another way to understand $O(n^2)$ is: if $n$ doubles, the algorithm will take about four times as long. For $n=10$, your algorithm takes $9+8+\ldots + 1 = 45$ steps. When $n=20$, it takes $ 19+18+\ldots + 1 = 190$ steps. That is indeed pretty close to $4\cdot 45=180$ steps. Similarly when $n=40$ it takes $780$ steps, which is again pretty close to $4\cdot 190 = 760$.
> 2 votes

# Answer
Here's a hint. Break the question into two parts:

1. Given $n$ elements, compute the (exact) number $C$ of comparisons following your scheme. If you are stuck here, (i) look at gradually growing examples and see how $C$ behaves and (ii) try to express $C$ as a sum and perhaps use a suitable sum identity.
2. Prove that $C = O(n^2)$.
> 1 votes

# Answer
# Your problem is equivalent to determining the number of edges in a complete graph with $n$ nodes and undirected edges.

Model each point as a node of a graph. You now have a graph with $n$ nodes. You have to look at the relation between every pair of nodes. This is equivalent to iterating over all edges precisely once. That means that you need to consider the number of edges.

As every of those $n$ nodes is connected to $n-1$ other nodes, and you want to avoid counting edges twice, the number of edges is $\frac{n(n-1)}{2}$.

Show that this is in $\mathcal{O}(n^2)$.
> 0 votes

# Answer
o(n^2) means that n^2 is an upper bound. So even if it is smaller than n^2 but not so far from it, it still is o(n^2). Like 1/2 n^2 is also o(n^2)
> 0 votes

# Answer
The big-o notation ignores coefficients. Both $n^2$ and $n^2/2$ are $O(n^2)$.
> 0 votes

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


# Question
Title: HashTable open-addressing is used for main array or buckets
I am trying to understand the HashTable open-addressing technique. I see there are three approaches: linear, quadratic and double hashing. I'm wondering are these techniques used:

* to find an index of the main array and no bucketing is involved
* or used when our buckets are arrays too and we are trying to add it to the bucket and we are not sure where to add.

Thanks in advance.

# Answer
Open addressing is a method for handling collisions. Another method is chaining, in which we have lists at our table indices, like you say.

In other words, open addressing means that all elements are stored inside a *single table*. In particular, to resolve a collision, the probing sequence finds a free slot in our table.
> 2 votes

---
Tags: hash-tables
---


# Question
Title: Why it is said that LBA is a non deterministic Turing Machine
I have read that linear bounded automaton is a Non deterministic Turing machine. Why is it so?

# Answer
The definition of LBA (for example given in Wikipedia) is a non-deterministic Turing machine which uses linear space. So an LBA is a (space-restricted) non-deterministic Turing machine by definition. There could be other, equivalent definitions.
> 4 votes

# Answer
If we are saying non deterministic Turing machine and LBA are same then its wrong. If we say non deterministic Turing machine with limited space then we can call it as LBA. LBA has space boundaries where as Turing machine don't have.
> 1 votes

---
Tags: terminology, turing-machines, automata, nondeterminism, linear-bounded-automata
---


# Question
Title: How are Complex Numbers and Complex Analysis used in CS?
The world is 3D and data of it is usually (as far as I know) represented and processed with *real* numbers. I've seen very few cases where complex numbers are used in programming and none when it comes to processing anything that doesn't explicitly require complex numbers.

How are complex numbers used it Computer Science and Programming? Which areas in CS/IT use it?

# Answer
I haven't seen them pop up a lot in "Computer Science" per say but there are quite a few closely related fields where they are very present.

I can think of signal processing for example, where Fourier transforms and other complex transformations are fundamental tools. Designing filters for signals also often boils down to placing poles in the complex plane.

In control theory and the analysis of complex systems you also sometimes analyse the stability of systems by looking at complex poles of algebraic fractions.

I imagine complex numbers must pup op a lot in quantum computing also, as a pure quantum state is represented as a complex vector in some basis.

I am only passingly familiar with the fields I mentioned so there might be a lot more ways complex numbers are used in them, and also a lot more fields I am not familiar with.
> 1 votes

---
Tags: mathematical-foundations
---


# Question
Title: Searching for points near given point in a multidimensional space
I want to search many times, not identical elements but similar, for something a similar image or fingerprint without having to search the whole space. When I have a 1D case I sort it first. For 2D I can make boxes big enough to be not wasted on boxes containing no elements, these boxes have subboxes and these have elements.

There is a problem: because when the width is 100, then if I'm looking for a 401 I can find a 490 and I can't find a close element 399. You would have to look in the boxes around, in 9 instead of in one. It's still possible, but for 3D it will be 27, generally 3^n, what if we have 512D?

# Answer
> 1 votes
If you don't want the exact nearest neighbour but would be satisfied with finding points that are not too far off, then you should take a look at Approximate nearest neighbour search.

Wikipedia suggests the following approaches:

Depending on the distribution of your data, not all dimensions may be equally relevant (maybe all points are bunched together along some line or hyperplane) and you could also use dimensionality reduction techniques, the main one being PCA (or maybe autoencoders nowadays).

Of course you can combine both, and that is also what I would recommend you to do in most cases.

If you want the exact nearest neighbour, unfortunately research suggests that this is very hard in high dimensions (see curse of dimensionality), and with a 512 dimensional space "clever" methods can very well end up being worse in practice than simply searching through all points.

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


title: Summation of asymptotic notation

text:
# Question
Title: Summation of asymptotic notation
How can we solve summation of asymptotic notations like given below: $$ \sum\_{k=1}^{n-1} O(n). $$

# Answer
> 8 votes
You should be very careful when summing up a variable number of terms in asymptotic notation, as the result actually depends on the hidden constants.

Consider the following example: $f\_i(n) = i\cdot n$ for all integers $i$ and $n$. Then, for any integer $i$, $f\_i(n) \in O(n)$.

If you are not careful, you could end up writing something like: $$\sum\_{i=1}^n f\_i(n) = \sum\_{i=1}^n O(n) = O(\sum\_{i=1}^n n) = O(n^2).$$ And get $O(n^2)$. But this is totally wrong!

If you do the computation without the asymptotic notation, you get: $$\sum\_{i=1}^n f\_i(n) = \sum\_{i=1}^n i\cdot n = n\sum\_{i=1}^n i = n\frac{n(n+1)}{2} = \frac{n^2(n+1)}{2}.$$ And this is not in $O(n^2)$, as it is in $\Theta(n^3)$.

Now some authors define $\sum\_{i=1}^n O(n)$ as meaning that the hidden constants are the same for every $O$ and in this case you can sum things together. But this is not always the case so I recommend not using $O$ notation with variable-length sums (as well as when doing induction, where similar problems appear).

# Answer
> 0 votes
To express the sum over k in big o notation, use the formulae that express the sum of the $i$th powers of the first $n$ positive integers as a polynomial of degree $i+1$.

For example, $\sum\_{k=1}^n k$ is the quadratic function $n(n+1)/2 = O(n^2)$. The sum $\sum\_{k=1}^n k^2$ is a cubic polynomial in $n$ and hence is $O(n^3)$, etc.

---
Tags: asymptotics, landau-notation, big-o-notation, summation
---


title: Datatypes as initial algebras

text:
# Question
Title: Datatypes as initial algebras
I'm refining my understanding of the connection between initial algebras and datatypes. This paper suggests that one could even represent the categories corresponding to datatypes definitions:

as follows:

Where $1$ is the terminal object of the category.

My question is, how can I justify that $1$ is the terminal object of the category? Do I have to postulate that any type has a unique morphism to $1$? This morphisms would be different that the datatype definitions which would not be nice...

# Answer
An empty product is the same thing as a terminal object by definition of the product: it's an object $1$ such that for every object $A$, there is a unique morphism $1\_A : A \rightarrow 1$. ($1$ is a product of a family indexed by an empty set iff there exists an empty family of morphisms such that for every object $A$ and every empty family of morphisms, there is a morphism $1\_A : A \rightarrow 1$ satisfying an empty family of properties.)

An empty product has a simple computational interpretation: it's a type with a single element. Haskell writes `()` for both the type and its value. ML calls the type `unit` and the value `()`. A function whose interpretation is $1\_A$ is a constant function taking an object of type $A$ as its argument and returning the value `()` of type $1$. It's the only total function of this type.

Likewise an empty coproduct $0$ is an initial object: an object such as for every $A$ there is a unique morphism $0\_A : 0 \rightarrow A$. The computational interpretation is an empty type. Writing a function whose denotation is $0\_A$ is tricky: most programming languages don't allow it without using features that don't fit well in a simple categorical semantics such as exceptions or recursion.

When you're building the categorical semantics, you do need to define everything, including “trivial” cases like terminal objects. You can't just assume that one exists. To give a concrete example, if you take a simple subset of the types of the C programming language allowing only basic types such as `int` and `char` and compound types built with `struct`, you can build binary products using `struct`, but you cannot build an empty product, because C forbids objects of size 0 and an object whose type is an empty `struct` would have the size 0.
> 1 votes

---
Tags: category-theory, inductive-datatypes
---


# Question
Title: Determine the optimal value of K - K-means clustering
I am trying to determine the optimal value of k. I have used a graph to plot the SSE against the values of k.

Using the elbow method, what would be the optimal value of k? I am unsure as to whether 7 or 8 would be most suitable because the line changes significantly at several points.

# Answer
The elbow method is not a well-defined algorithm that provides an unambiguous result. Rather, it is a heuristic that involves subjective interpretation. As Wikipedia says, "it is often ambiguous and not very reliable". So, there is no one answer to your question. And, your plot shows an example of a situation that the elbow method is not well-suited to.
> 0 votes

---
Tags: clustering
---


# Question
Title: Is it possible that the subtraction between two undecidable languages is regular?
If $L\_1$ and $L\_2$ are both non-decidable languages (Not decidable, so can be SD or $\lnot$SD), is it possible that $L\_1-L\_2$ is regular and $L\_1-L\_2\neq\phi$, where $\phi$ is the empty set?

What's a good way of tackling this question? Me and some classmates have been stuck on this question for a while, and this was the best we've got:

It should be possible given the following example:

Let $L\_1=H\cup a^\*$ and $L\_2=H$, where $H=\\{\<M,w\>:$ Turing machine $M$ halts on $w$$\\}$, so $L\_1-L\_2=L\_1\cap \lnot L\_2=(H\cup a^\*)\cap \lnot H=\lnot H\cap a^\* = a^\*$ which is regular. (we are saying $H$ does not contain $a^\*$, so $\lnot H$ must contain $a^\*$, hence why the intersection gives $a^\*$.)

But we are not confident this is correct due to the last part with the intersection does not feel right. What's the answer to this question?

# Answer
Your example almost works. You need to make sure that the regular part is disjoint from the non-decidable part.

Suppose our alphabet has at least two symbols, say $a$ and $b$. Consider any undecidable langauge $H$, for example the halting set, and define $$L\_2 = \lbrace b w \mid w \in H\rbrace$$ and $$L\_1 = L\_2 \cup \lbrace a \rbrace.$$ Now it is obvious that $a \not\in L\_2$ because all words in $L\_2$ start with $b$. Also, $L\_2$ and $L\_1$ are undecidable because there are easy reductions from $H$ to them, and back. And of course we have $$L\_1 \setminus L\_2 = \\{a\\},$$ which is decidable. You can make the example more complicated by taking any decidable langauge $D$ and define $L\_2$ as before, but change $L\_1$ to $$L\_1 = L\_2 \cup \\{a w \mid w \in D\\}.$$ This way $L\_1 \setminus L\_2$ is computably isomorphic to $D$.
> 3 votes

# Answer
Just take for $L\_2$ an undecidable language of $a^\*$ and take $L\_1 = L\_2 \cup \\{b\\}$. Then $L\_2$ is also undecidable and $L\_2 - L\_1 = \\{b\\}$ is regular.
> 3 votes

# Answer
As you suspected, it can happen that $L\_1-L\_2\not=a^\*$. The assumption that $H$ does not contain $a^\*$ does not imply that $\lnot H$ must contain $a^\*$. For example, if $H\cap a^\*= \\{a^2\\}$, then $\lnot H$ does not contain $a^2$, let alone $a^\*$.

The technique to arrive at a simple solution is to let the regular part be disjoint with $L\_2$.

Here is the simplest way to find $L\_2$ so that $L\_1-L\_2$ is undecidable, given any undecidable language $L\_1$. Since $L\_1$ is undecidable, it must contain at least one word. Let $w\in L\_1$. Let $L\_2$ be $L\_1$ without $w$. Then $L\_1-L\_2=\\{w\\}$ is regular. You can check that $L\_2$ is undecidable.

---

Exercise 1. (easy) Given an undecidable language $L\_2$, find an undecidable language $L\_1$ such that $L\_1-L\_2$ is regular.

Exercise 2. (easy) Give an example where the subtraction between two non-context-free languages is regular.

Exercise 3. (one or several minutes) Give any regular language $R$, find an example such that the subtraction between two undecidable languages is $R$.
> 2 votes

---
Tags: turing-machines, regular-languages, undecidability, semi-decidability
---


# Question
Title: How to find the substitutions that convert the starting sequence into the final sequence? CCC19J5
Here is Canadian Computing Competition 2019 Junior problem 5 on dmoj.ca. You can also see the original problem at cemc.uwaterloo.ca as well.

> A substitution rule describes how to take a sequence of symbols and convert it into a different sequence of symbols. For example, **ABA→BBB**, is a substitution rule which means that **ABA** can be replaced with **BBB**. Using this rule, the sequence **AABAA** would be transformed into the sequence **ABBBA** (the substituted symbols are in bold).
>
> In this task, you will be given three substitution rules, a starting sequence of symbols and a final sequence of symbols. You are to use the substitution rules to convert the starting sequence into the final sequence, using a specified number of substitutions.
>
> For example, if the three substitution rules were:
>
> **AA → AB**
> **AB → BB**
> **B → AA**
>
> We could convert the sequence **AB** into **AAAB** in 4 steps, by the following substitutions:
>
> **AB → BB → AAB → AAAA → AAAB**,
>
> where the symbols to be replaced are shown in bold. More specifically, from the initial sequence **AB**, substitute rule 2 starting at position 1, to get the result **BB**. From **BB**, substitute rule 3, starting at position 1, to get the result **AAB**. From **AAB**, substitute rule 3, starting at position 3, to get the result **AAAA**. From **AAAA**, substitute rule 1, starting at position 3, to get the result **AAAB**, which is the final sequence.
>
> **Input Specification**
>
> The first three lines will contain the substitution rules. Each substitution rule will be a sequence of `A`'s and `B`'s, followed by a space following by another sequence of `A`'s and `B`'s. Both sequences will have between one and five symbols.
>
> The next line contains three space separated values, $S$, $I$ and $F$. The value $S(1\le S\le 15)$ is an integer specifying the number of steps that must be used, and the values $I$ (the initial sequence) and $F$ (the final sequence) are sequences of `A`'s and `B`'s, where there are at least one and at most 5 symbols in $I$ and at least one and at most 50 symbols in $F$.
>
> For 7 of the 15 marks available, $S\le 6$.
>
> For an additional 7 of the 15 available marks, $S\le 12$.
>
> ***Output Specification***
>
> The output will be $S$ lines long and describes the substitutions in order.
>
> Line $i$ of the output will contain three space-separated values, $R\_i$, $P\_i$, and $W\_i$:
>
> $R\_i$ is the substitution rule number (either 1, 2 or 3) that will be used. $P\_i$ is the starting position index of where the substitution rule will be applied in the sequence. Notice that the string is 1-indexed (i.e., the first character of the string is at index 1). $W\_i$ is the sequence that results from this substitution. Specifically, $W\_i$ is the sequence of symbols that results by applying substitution rule $R\_i$ starting at position $P\_i$ from the previous sequence of symbols, $W\_{i−1}$, where we define $W\_0$ to be the initial sequence $I$. Note that $W\_S=F$, the final sequence.
>
> There will always be at least one sequence of $S$ substitutions that will convert $I$ into $F$. If there is more than one possible sequence of substitutions, any valid sequence will be accepted.

I tried using recursion but the program isn't fast enough. Can anyone help?

# Answer
Lookup “depth first” and “breadth first” search. I’d guess you tried depth first and it fails. Try breadth first, and make sure that when a sequence can be produced in two or more ways, you ignore the second and further ways.
> 0 votes

---
Tags: algorithms, recursion, divide-and-conquer, context-sensitive, programming-contest
---


# Question
Title: Is this solution to the dining philosopher's problem entirely valid?
In a question on Stack Overflow, the answer by Patrick Trentin lists the following solution to the dining philosopher's problem:

> A possible approach for avoiding deadlock without incurring starvation is to introduce the concept of **altruistic philosopher**, that is a philosopher which drops the fork that it holds when it realises that he can not eat because the other fork is already used.
>
> Having just one altruistic philosopher is sufficient in order to avoid deadlock, and thus all other philosophers can continue being greedy and attempt to grab as many forks as possible.
>
> However, if you never change who is the altruistic philosopher during your execution, then you might end up with that guy starving himself to death. Thus, the solution is to change the altruistic philosopher infinitely often. A fair strategy is to change it in a round robin fashion each time that one philosopher acts altruistically. In that way, no philosopher is penalised and you can actually verify that no philosopher starves under the fairness condition that the scheduler gives a chance to every philosopher to execute infinitely often.

I was intrigued by this solution because I hadn't heard it before. However, I can find no references to it anywhere in the existing literature.

* I did a quick check, and saw that it isn't listed on Wikipedia as a standard solution.
* Googling 'altruistic philosopher dining' yields only one result from Google Books that does not discuss the round robin strategy and only vaguely alludes to the altruistic philosopher to talk about the perils of starvation.
* I tried looking up *altruistic philosopher* on ArXiv, only to return no results.
* Trentin cites a book about nuXmv, a symbolic model checker, as his source but only provides a link to his own lab slides.

So my question: does this naive yet seemingly remarkable solution actually *work*? Or are there pitfalls that have been overlooked? I find it hard to believe that, if it works, it wouldn't have at least some mention somewhere - but at the same time I can't see why it wouldn't work, as it's a fairly naive solution.

If it does work, can I either a) have a reference to a proof, or b) an actual proof that this solves the dining philosopher's problem? If it doesn't, same standards apply, except for the negation of a proof. :)

# Answer
> 3 votes
The description of an **altruistic philosopher** given in this answer, that you quoted in your question, is slightly imprecise. What it really is going on is that:

> A possible approach for avoiding **deadlock** without incurring in **starvation** is to introduce the concept of **altruistic philosopher**, that is a *philosopher* which drops the fork that it holds **when it realizes that no one can eat because there is a deadlock situation**.

So the actual condition for altruism is **stronger** than the one in your quote. Another important condition is that the *fork* that is put down by the altruistic philosopher is handed over to the philosopher waiting for it, ***e.g.*** *by waking up the process that is waiting on the resource*. (Otherwise the deadlock situation could actually reappear one instant later).

I apologize for the confusion I may have created in this regard. In my stackoverflow answer I simplified the actual model to convey the basic idea, but this left out some details that are important for *"formally proving"* the correctness of the solution.

---

***Note:*** *I don't have the time to write down a formal proof in this moment, so I will try to make a simple argument.*

The pre-conditions are as follows:

* `Ph_i` is the altruistic philosopher
* `Ph_i` holds the left fork and the right fork is hold by its successor `Ph_{i+1}`
* There must be a deadlock: every `Ph_k` is holding the left fork

the actions performed are:

* `Ph_i` gives his left fork to its predecessor `Ph_{i-1}`

the post-conditions are as follows:

* `Ph_{i+1}` becomes the **new** altruistic philosopher
* `Ph_{i-1}` is now holding two forks and can eat
* After eating, `Ph_{i-1}` puts down both forks.

The important **invariant** is that *the predecessor of the altruistic philosopher is guaranteed to eat after a deadlock situation*.

Given `N` philosophers, the **round robin** policy guarantees that each philosopher becomes altruistic exactly **once** in a sequence of `N` deadlocks. Hence, *each philosopher is guaranteed to eat (at least) once every `N` deadlocks* (because it is the predecessor of an altruistic philosopher exactly once every `N` deadlocks).

This is, of course, the analysis of the worst-case possible outcome. Depending on the work-load, deadlocks may not arise so frequently and in this case each philosopher would have the chance to eat pretty much anytime it wants.

---

The *naive* solution to the dining philosophers presented in this answer is quite effective for the limited purposes of *teaching Model Checking / Formal Verification techniques*. However, I would not assume that it is the best engineering solution for practical situations because it requires one to detect a deadlock. Also, it may be hard to reduce practical problems to the simple scenario of the dining philosophers *(e.g. there could be many more resources involved, the order in which resources are grabbed is not fixed, etc.)*.

---
Tags: algorithms, concurrency, deadlocks
---


title: Period of sum of two periodic sequences

text:
# Question
Title: Period of sum of two periodic sequences
I was wondering, what is to be the shortest possible key using Vigenere encryption, if a text is ciphered one time with a key of length $i$ using Vigenere and second time with a key of length $j$ using Vigenere?

From what I understand, each time it is encrypted, each character shifts using the first key and then using the second one, so I believe that for each pair there's an equivalent shifting. but if the two keys have a different length, how can I find the shortest possible key?

I think it has to be something with lowest common denominator, but I am not sure. how can this be shown mathematically?

my previous edit was a mistake and i deeply sorry for it. i read the book wrong and didn't interpret what's written well. very sorry for it. yuval explained to me well and i continue to research it using his given information

# Answer
> 4 votes
If you sum a sequence with period $a$ and a sequence with period $b$, then you get a sequence which is $\mathsf{LCM}(a,b)$-periodic. But the new sequence might have a smaller period, as the following example demonstrates (addition is modulo 10):

```
022441133502244113350224411335
000772999611888000772999611888
022113022113022113022113022113

```

The first sequence has period 10 (0224411335), the second sequence as period 15 (000772999611888), and the sum sequence has period 6 (022113), although the LCM is 30.

More generally, the sum of a sequence of period $i$ and a sequence of period $j$ could have period exactly $k$ iff $\mathsf{LCM}(i,j) = \mathsf{LCM}(i,k) = \mathsf{LCM}(j,k)$. See Restrepo and Chacon, On the period of sums of discrete periodic signals.

---
Tags: cryptography, encoding-scheme, encryption
---


# Question
Title: Is finding the minimum feedback arc set on graph with two outgoing arcs for each node np-complete?
I have a graph with at most two outgoing arcs for each node and I need to extract a DAG by removing the least number of arcs. I know that the general problem is np-complete but i can't reduce it to the other one.

I know that each graph can be mapped to a graph with only two outgoing edges for each node, but i can't find a way to convert from many edges to two edges that allows me to perform the reduction. If I convert a node with 3 edges to something like

```
A----B-OUT1
|    |
OUT3 OUT2

```

Then the mimimun edge set will contain AB instead of B-OUT2 and B-OUT1, provided that OUT1 and OUT2 are generating a cycle, since by cutting AB it will save a point in the objective function.

Is this reduction possible?

# Answer
The reduction is possible.

I'll give a reduction of minimum feedback arc set to minimum feedback arc set with maximum outdegree two. The basic idea is that if node $i$ has outdegree $d\_{i}$, we make $d\_{i}$ copies of node $i$. We add new nodes representing edges so that edges can still be cut in one operation.

Say the graph we want to solve minimum feedback arc set in is (V, E). We'll build a graph (V', E') such that (V', E') has a feedback arc set of size k or less if and only if (V, E) has a feedback arc set of size k or less, and the maximum outdegree of any node in (V', E') is two.

Let $d\_{i}$ be the outdegree of node $v\_{i}$ in $(V, E)$. Corresponding to node $v\_{i}$ in $V$ we'll have nodes $v'\_{i, 1} \dots v'\_{i, d\_{i}}$ in $V'$. For every node $v'\_{i, j}$ we'll also have $d\_{i}$ nodes $x'\_{i, j, 1}, \dots, x'\_{i, j, d\_{i}}$.

Corresponding to edge $e\_{i} = (s\_{i}, t\_{i})$ from node indexed $s\_{i}$ to the one indexed $t\_{i}$ in $E$, we'll have the node $e'\_{i}$ and nodes $y'\_{i, 1}, \dots, y'\_{i, d\_{t\_{i}}}$ in $V'$.

For all vertices $v\_{i} \in V$, let $id\_{i, k}$ be the index of the $k$th edge leaving node $i$. In $E'$, for every $1 \leq j \leq d\_{i}$ we'll have the edge $(v'\_{i, j}, x'\_{i, j, 1})$ and further for $1 \leq k \< d\_{i}$ the edge $(x'\_{i, j, k}, x'\_{i, j, k+1})$ and for $1 \leq k \leq d\_{i}$ the edge $(x'\_{i, j, k}, e\_{id\_{i, k}})$.

For all edges $e\_{i} = (s\_{i}, t\_{i})$ in $E$, we have the edges $(e'\_{i}, y'\_{i, 1})$, for $1 \leq j \< d\_{t\_{i}}$ the edge $(y'\_{i, j}, y'\_{i, j+1})$, and for $1 \leq j \leq d\_{t\_{i}}$ the edges $(y'\_{i, j}, v'\_{t\_{i}, j})$.

By the way we defined the nodes, clearly every node has outdegree at most two.

I'll embed an image of an example of the reduction at the bottom of the proof.

Now we'll prove the main claim.

Clearly if $(V, E)$ has a feedback arc set of size $k$, so does $(V', E')$ (cut edge $(e'\_{i}, y\_{i, 1})$ for every edge $e\_{i})$ cut in the original graph).

For the other direction, Take any feedback arc set of size $k'$ in $(V', E')$. We'll build a feedback arc set of cost $k \leq k'$ for $(V, E)$, by cutting edge $e\_{i}$ if and only if one or both of the following hold:

1. One of the edges corresponding to $e\_{i}$ in $E'$ is cut in $(V', E')$
2. For all of $v'\_{s\_{i}, 1}, \dots, v'\_{s\_{i}, d\_{s\_{i}}}$, at least one edge corresponding to them has been cut.

Note that the second case only happens if we make at least $d\_{s\_{i}}$ cuts in the copies corresponding to node $v\_{s\_{i}}$, so $k \leq k'$. Now assume that with these cuts $(V, E)$ has a directed cycle $v\_{p\_{1}}, \dots, v\_{p\_{m}}$. Then for the copies corresponding to $v\_{p\_{j}}$, at least one, say $v'\_{p\_{j}, h\_{j}, 1}$ has has none of its or its $x'$s edges touched, otherwise by condition 2 for cutting an edge we would have no edges leaving $v\_{p\_{j}}$ in our solution in $(V, E)$.

But then $(V', E')$ also has a directed cycle: the cycle goes through $v'\_{p\_{j}, h\_{j}}$ to $x'\_{p\_{j}, h\_{j}, 1}$ to $\dots$ to $x'\_{p\_{j}, h\_{j}, out\_{p\_{j}, p\_{j+1}}}$ (where $out\_{a, b}$ is the index in the edges out of $a$ of the edge to $b$) to $e'\_{edi\_{p\_{j}, p\_{j+1}}}$ (where $edi\_{a, b}$ is the index of the edge from $a$ to $b$) to $y\_{edi\_{p\_{j}, p\_{j+1}}, 1}$ to $\dots$ to $y\_{edi\_{p\_{j}, p\_{j+1}}, h\_{j+1}}$ to $v'\_{p\_{j+1}, h\_{j+1}}$.

Since a contradiction followed, we must have that the cuts in $(V, E)$ form a feedback arc set, completing the proof.

---

Here's an image of the reduction graph for $V = \\{1, 2, 3, 4, 5\\}$, $E = \\{(1, 2), (1, 3), (2, 4), (2, 5), (4, 1), (3, 1)\\}$. Sorry for the massive size. The rectangles at the top-right show the graph $(V, E)$.
> 5 votes

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


# Question
Title: Why are some programming languages "faster" or "slower" than others?
I have noticed that some applications or algorithms that are built on a programming language, say C++/Rust run faster or snappier than those built on say, Java/Node.js, running on the same machine. I have a few question regarding this:

1. Why does this happen?
2. What governs the "speed" of a programming language?
3. Has this anything to do with memory management?

I'd really appreciate if someone broke this down for me.

# Answer
> 104 votes
In programming language design and implementation, there is a large number of choices that can affect performance. I'll only mention a few.

Every language ultimately has to be run by executing machine code. A "compiled" language such as C++ is parsed, decoded, and translated to machine code only once, at compile-time. An "interpreted" language, if implemented in a direct way, is decoded at runtime, at every step, every time. That is, every time we run a statement, the intepreter has to check whether that is an if-then-else, or an assignment, etc. and act accordingly. This means that if we loop 100 times, we decode the same code 100 times, wasting time. Fortunately, interpreters often optimize this through e.g. a just-in-time compiling system. (More correctly, there's no such a thing as a "compiled" or "interpreted" language -- it is a property of the implementation, not of the language. Still, each language often has one widespread implementation, only.)

Different compilers/interpreters perform different optimizations.

If the language has automatic memory management, its implementation has to perform garbage collection. This has a runtime cost, but relieves the programmer from an error-prone task.

A language might be closer to the machine, allowing the expert programmer to micro-optimize everything and squeeze more performance out of the CPU. However, it is arguable if this is actually beneficial in practice, since most programmers do not really micro-optimize, and often a good higher level language can be optimized by the compiler better than what the average programmer would do. (However, sometimes being farther from the machine might have its benefits too! For instance, Haskell is extremely high level, but thanks to its design choices is able to feature very lightweight green threads.)

Static type checking can also help in optimization. In a dynamically typed, interpreted language, every time one computes `x - y`, the interpreter often has to check whether both `x,y` are numbers and (e.g.) raise an exception otherwise. This check can be skipped if types were already checked at compile time.

Some languages always report runtime errors in a sane way. If you write `a[100]` in Java where `a` has only 20 elements, you get a runtime exception. This requires a runtime check, but provides a much nicer semantics to the programmer than in C, where that would cause undefined behavior, meaning that the program might crash, overwrite some random data in memory, or even perform *absolutely anything* else (the ISO C standard poses no limits whatsoever).

However, keep in mind that, when evaluating a language, performance is not everything. Don't be obsessed about it. It is a common trap to try to micro-optimize everything, and yet fail to spot that an inefficient algorithm/data structure is being used. Knuth once said "premature optimization is the root of all evil".

Don't underestimate how hard it is to write a program *right*. Often, it can be better to choose a "slower" language which has a more human-friendly semantics. Further, if there are some specific performance critical parts, those can always be implemented in another language. Just as a reference, in the 2016 ICFP programming contest, these were the languages used by the winners:

```
1   700327  Unagi                       Java,C++,C#,PHP,Haskell
2   268752  天羽々斬                     C++, Ruby, Python, Haskell, Java, JavaScript
3   243456  Cult of the Bound Variable  C++, Standard ML, Python

```

None of them used a single language.

# Answer
> 20 votes
> What governs the "speed" of a programming language?

There is no such thing as the "speed" of a programming language. There is only the speed of a particular program written by a particular progammer executed by a particular version of a particular implementation of a particular execution engine running within a particular environment.

There can be huge performance differences in running the same code written in the same language on the same machine using different implementations. Or even using different versions of the same implementation. For example, running the exact same ECMAScript benchmark on the exact same machine using a version of SpiderMonkey from 10 years ago vs a version from this year will probably yield a performance increase anywhere between 2×–5×, maybe even 10×. Does that then mean that ECMAScript is 2× faster than ECMAScript, because running the same program on the same machine is 2× faster with the newer implementation? That doesn't make sense.

> Has this anything to do with memory management?

Not really.

> Why does this happen?

Resources. Money. Microsoft probably employs more people making coffee for their compiler programmers than the entire PHP, Ruby, and Python community combined has people working on their VMs.

For more or less any feature of a programming language that impacts performance in some way, there is also a solution. For example, C (I'm using C here as a stand-in for a class of similar languages, some of which even existed before C) is not memory-safe, so that multiple C programs running at the same time can trample on each other's memory. So, we invent virtual memory, and make all C programs go through a layer of indirection so that they can pretend they are the only ones running on the machine. However, that is slow, and so, we invent the MMU, and implement virtual memory in hardware to speed it up.

But! Memory-safe languages don't need all that! Having virtual memory doesn't help them one bit. Actually, it's worse: not only does virtual memory not help memory-safe languages, virtual memory, even when implemented in hardware, still impacts performance. It can be especially harmful to the performance of garbage collectors (which is what a significant number of implementations of memory-safe languages use).

Another example: modern mainstream general purpose CPUs employ sophisticated tricks to reduce the frequency of cache misses. A lot of those tricks amount to trying to predict what code is going to be executed and what memory is going to be needed in the future. However, for languages with a high degree of runtime polymorphism (e.g. OO languages) it is really, really hard to predict those access patterns.

But, there is another way: the total cost of cache misses is the number of cache misses multiplied by the cost of an individual cache miss. Mainstream CPUs try to reduce the number of misses, but what if you could reduce the cost of an individual miss?

The Azul Vega-3 CPU was specifically designed for running virtualized JVMs, and it had a very powerful MMU with some specialized instructions for helping garbage collection and escape detection (the dynamic equivalent to static escape analysis) and powerful memory controllers, and the entire system could still make progress with over 20000 outstanding cache misses in flight. Unfortunately, like most language-specific CPUs, its design was simply out-spent and out-brute-forced by the "giants" Intel, AMD, IBM, and the likes.

The CPU architecture is just *one* example that has an impact on how easy or how hard it is to have a high-performance implementation of a language. A language like C, C++, D, Rust that is a good fit for the modern mainstream CPU programming model will be easier to make fast than a language that has to "fight" and circumvent the CPU, like Java, ECMAScript, Python, Ruby, PHP.

Really, it's all a question of money. If you spend equal amounts of money to develop a high-performance algorithm in ECMAScript, a high-performance implementation of ECMAScript, a high-performance operating system designed for ECMAScript, a high-performance CPU designed for ECMAScript as has been spent over the last decades to make C-like languages go fast, then you will likely see equal performance. It's just that, at this time, much more money has been spent making C-like languages fast than making ECMAScript-like languages fast, and the assumptions of C-like languages are baked into the entire stack from MMUs and CPUs to operating systems and virtual memory systems up to libraries and frameworks.

Personally, I am most familiar with Ruby (which is generally considered to be a "slow language"), so I will give two examples: the `Hash` class (one of the central data structures in Ruby, a key-value dictionary) in the Rubinius Ruby implementation is written in 100% pure Ruby, and it has about the same performance as the `Hash` class in YARV (the most widely-used implementation), which is written in C. And there is an image manipulation library written as a C extension for YARV, that also has a (slow) pure Ruby "fallback version" for implementations that don't support C which uses a ton of highly-dynamic and reflective Ruby tricks; an experimental branch of JRuby, utilizing the Truffle AST interpreter framework and Graal JIT compilation framework by Oracle Labs, can execute that pure Ruby "fallback version" as fast as the YARV can execute the original highly-optimized C version. This is simply (well, anything but) achieved by some really clever people doing really clever stuff with dynamic runtime optimizations, JIT compilation, and partial evaluation.

# Answer
> 8 votes
Theoretically, if you write code that does exactly the same in two languages and compile both using a "perfect" compiler, the performance of both should be the same.

In practice, there are several reasons why the performance is going to be different:

1. Some languages are harder to optimize.

This includes especially features that make code more dynamic (dynamic typing, virtual methods, function pointers), but also for example garbage collection.

There are various ways to make code using such features fast, but it usually still ends up at least somewhat slower than without using them.
2. Some language implementations have to do some compiling at runtime.

This applies especially to languages with virtual machines (like Java) and languages that execute the source code, with no intermediate step for binary (like JavaScript).

Such language implementations have to do more work at runtime, which affects performance, especially startup time/performance soon after startup.
3. Language implementations intentionally spend less time on optimizations than they could.

All compilers care about performance of the compiler itself, not just of the generated code. This is especially important for runtime compilers (JIT compilers), where taking too long to compile slows down the application execution. But it applies to ahead-of-time compilers, like those for C++ too. For example register allocation is an NP-complete problem, so it's not realistic to solve it perfectly and instead heuristics that execute in reasonable time are used.
4. Differences in idioms in different languages.

Code written in the style common for a certain language (idiomatic code) using common libraries can result in difference in performance, because such idiomatic code behaves subtly differently in each language.

As an example, consider `vector[i]` in C++, `list[i]` in C# and `list.get(i)` in Java. The C++ code likely does no range checking and performs no virtual calls, the C# code performs range checking, but no virtual calls and the Java code performs range checking and it's a virtual call. All three languages support virtual and non-virtual methods and both C++ and C# can include range checking or avoid it when accessing the underlying array. But the standard libraries of these languages decided to write these equivalent functions differently, and, as a consequence, their performance will be different.
5. Some compilers might be missing some optimizations.

Compiler writers have finite resources, so they can't implement every possible optimization, even ignoring the other issues. And the resources they have might be focused on one area of optimization more than others. As a consequence, code written in different languages can have different performance because of differences in their compilers, even if there is no fundamental reason why one language should be faster or even easier to optimize than the other.

# Answer
> 1 votes
This is a very general question, but in your case the answer could be simple. C++ compiles to machine code, where Java compiles to Java byte code, which is then run of a Java virtual machine (though there is also just-in-time compiling, which further compiles the Java byte code to native machine code). Another difference could be garbage collection, which is a service that only Java provides.

# Answer
> 0 votes
Simple answer is, the closer a language is to the hardware the faster it would be.

The more a language depends on libraries and other functions to do it's tasks the longer it takes for program execution in that language.

# Answer
> 0 votes
It bears repeating that the algoritm used is most important.

An example might be you writing your oen bubble sort on a million records in the worlds fastest language. Compared it to using a really slow language with a built in really good sort. Your fast language will be mighty slow in comparison.

# Answer
> -5 votes
Your question is too general, so I'm afraid I can't give an exact answer that you need.

For my best explanation, let's look at C++ and .Net platform.

C++, very close to machine code and one of the favor programming in the older time (like more than 10+ years ago?) because of the performance. There isn't much resources needed to develop and execute C++ program even with the IDE, they are consider very light weight and very fast. You can also write C++ code in console and develop a game from there. In terms of memory and resources, I forgotten roughly how much capacity it takes in a computer but the capacity is something that you can't compare with current generation of programming language.

Now let's look at .Net. The prerequisite to do .Net development is one giant IDE that consists of not just one type of programming languages. Even if you just want to developer in let's say C#, the IDE itself will includes many programming platforms by default such as J#, VB, mobile and etc by default. Unless you do custom install and only install exactly what you want, provided that you are experience enough to play with the IDE installation.

Other than installing the IDE software itself, .Net also comes with huge capacity of libraries and frameworks for the purpose of ease of access to any kind of platform that developers need AND don't need.

Developing in .Net can be a fun experience because many common function and components are available by default. You can drag-and-drop and use many validation method, file reading, database access and much more in the IDE.

As a result, it's a trade off between computer resources and speed of development. Those libraries and framework takes up memory and resources. When you execute a program in .Net IDE, it may consume tons of time trying to compile the libraries, components and all of your files. And when you do debugging, your computer require lots of resources to manage the debugging process in your IDE.

Usually, in order to do .Net development, you need a good computer with the some Ram and processor. Otherwise, you might as well don't programming at all. In this aspect, C++ platform is much better than .Net. Although you still need a good computer, but capacity won't be too much of concern compare to .Net.

Hope my answer could help with your question. Let me know in case you want to know more.

EDIT:

Just a clarification to the my main point, I mainly answer to the question of "What's govern the speed of programming".

In IDE standpoint, using C++ or .Net language in the relative IDE does not affect the speed of writing the code, but it will affect the speed of development because Visual Studio compiler take longer time to execute the program, but C++ IDE is much lighter and consume less computer resources. So in the long run, you can do programming faster with C++ type of IDE compare with .Net IDE which heavily depending on libraries and framework. If you take in the amount of time of waiting the IDE to start up, compile, execute the program and etc, it will affect the speed of programming. Unless "the speed of programming" is actually only focus on "speed of writing code".

The amount of libraries and framework in Visual Studio also consume the computer capacity. I'm not sure if this answer the question of "memory management", but I just want to point out that Visual Studio IDE can take up lots of resources when running it, and thus slow down the overall "speed of programming". Of course, this has nothing to do with "speed of writing code".

As you may have guessed, I don't know too much of C++ as I just use it as example, my main point is about Visual Studio type of heavy IDE that consume computer resources.

If I got the idea and did not answer the thread starter question at all, apologize for the long post. But I would advice the thread starter to make the question clear and ask exactly what he/she need to know about "faster" and "slower"

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


# Question
Title: Find lines segment portions close together
I have two lines segment in 3D space. Lines segment are defined by 2 points each: $A\_1$, $B\_1$ and $A\_2$, $B\_2$ (see left part in the below schema).

I would a like to find an algorithm to detect which portion of the line segment 1 has a distance less than or equal to $x$ to the line segment 2 (and the opposite). The expected result of the algorithm is represented by the red lines in the schema:

Could you please provide me some tips & tricks? I do not know where to start. Thank you.

# Answer
Here is a derivation that shows how to solve this problem, using a bit of vector arithmetic.

You can project a point $P$ onto the line $A\_1B\_1$ using vector arithmetic; in particular, the projection of $P$ is $${(B\_1-A\_1)^\top (P-A\_1) \over \\|B\_1-A\_1\\|\_2^2} (B\_1-A\_1) + A\_1,$$ where $v^\top$ denotes the transpose of vector $v$, so the vector measuring the orthogonal distance from $A\_1B\_1$ to $P$ is

$$D=P-{(B\_1-A\_1)^\top (P-A\_1) \over \\|B\_1-A\_1\\|\_2^2} (B\_1-A\_1) - A\_1.$$

Every point $P$ on the line segment $A\_2B\_2$ has the form $P=\alpha A\_2 + (1-\alpha)B\_2$, for some $\alpha \in \[0,1\]$. So, we can write $D$ in the form

$$ \begin{align\*} D=\\;&\alpha A\_2 + (1-\alpha)B\_2 - A\_1\\ &- {(B\_1-A\_1)^\top (\alpha A\_2 + (1-\alpha)B\_2-A\_1) \over \\|B\_1-A\_1\\|\_2^2} (B\_1-A\_1). \end{align\*} $$

Notice that this is a linear function of $\alpha$, when $A\_1,B\_1,A\_2,B\_2$ are fixed.

Let the $x,y$-coordinates of $D$ be $x\_D,y\_D$, i.e., $D=(x\_D,y\_D)$. The above equation implies that there are constants $a\_0,a\_1,a\_2,a\_3$ such that

$$x\_D=a\_0 \alpha + a\_1, y\_D = a\_2 \alpha + a\_3.$$

The $a\_0,\dots,a\_3$ depend only on $A\_1,A\_2,B\_1,B\_2$ (but not on $\alpha$) and can be readily computed using the formula above.

Now we want this vector $D$ to be of length at most $\tau$, i.e., $\\|D\\|\_2 \le \tau$. In other words, we want

$$x\_D^2 + y\_D^2 \le \tau.$$

This is equivalent to

$$(a\_0 \alpha + a\_1)^2 + (a\_2 \alpha + a\_3)^2 \le \tau.$$

That is a quadratic in the unknown $\alpha$, so we can readily find the range of $\alpha$ where this inequality holds by using the quadratic formula (basically, find the roots of the quadratic equation $(a\_0 \alpha + a\_1)^2 + (a\_2 \alpha + a\_3)^2 = \tau$, and these are the endpoints of that range, except that you should clamp to the range $\[0,1\]$). Say that the inequality holds for $\alpha$ in the range $\[\alpha\_\ell,\alpha\_u\]$. Then it follows that the points on the line segment $A\_3B\_3$ are all of distance at most $\tau$ to the line $A\_1B\_1$, where $A\_3 = \alpha\_\ell A\_2 + (1-\alpha\_\ell) B\_2$ and $B\_3 = \alpha\_u A\_2 + (1-\alpha\_u) B\_2$.

This would describe how to find all points on the line segment $A\_2B\_2$ that are distance at most $\tau$ from the *line* connecting $A\_1$ and $B\_1$. However, we really want to find all points that are distance at most $\tau$ from the *line segment* $A\_1B\_1$. So, we want to constrain the projection of $P$ to be between $A\_1$ and $B\_1$, i.e., we want to constrain $D$ to be between $0$ and $B\_1-A\_1$. By solving systems of linear equations, you can find $\alpha\_0$ such that $(a\_0 \alpha\_0+a\_1,b\_0 \alpha\_0+b\_1)=(0,0)$ and $(a\_0 \alpha\_1+a\_1,b\_0 \alpha\_1+b\_1)=B\_1-A\_1$. Then, we replace $\[\alpha\_\ell,\alpha\_u\]$ (obtained above by the quadratic formula) with the intersection of ranges $\[\alpha\_\ell,\alpha\_u\] \cap \[\alpha\_0,\alpha\_1\]$. *This* gives us all points on the line segment $A\_2B\_2$ that are distance at most $\tau$ from the line segment $A\_1B\_1$.

This solves your question of how to find all points on the line segment $A\_2B\_2$ that are distance at most $\tau$ from the line segment $A\_1B\_1$. You can repeat the same procedure a second time to find all points on the line segment $A\_1B\_1$ that are distance at most $\tau$ from $A\_2B\_2$.
> 1 votes

# Answer
Here's a way to think of the 2D problem:

I'm focusing on the part of $\overline{AB}$ that is distance $\leq x$ from $\overline{CD}$. First draw a right triangle on $\overline{CD}$ whose leg has length $x$. As a comment pointed out, the shortest distance from a point to a line is given by the perpendicular. Then everything shaded in red has distance $\leq x$. By rotating the triangle $180^\circ$ you get the same red portion on the other side.

How can you express your answer? One way is to say "everything on line $\overline{AB}$ distance $d$ from the intersection, where $d = \\|EF\\|$ in the picture. Here is where coordinates enter: distance $d = \frac{x}{\sin \theta}$ and you can express the angle $\theta$ in terms of $A,B,C,D$ using the vectors $\vec{AB}$ and $\vec{CD}$.

As a comment: if you want to locate the relevant portion of $\overline{CD}$ that is distance $\leq x$ from $\overline{AB}$, you could repeat the analysis with the roles of $\overline{AB}, \overline{CD}$ switched, or better yet, observe that the reflection about the angle bisector takes one line to the other, and preserves distances. This means that the red portions you would draw on both lines have the same length.

Extending to 3D: if the two lines are intersecting then the above analysis goes through unchanged. If the lines are skew, well, first you may have the empty set if $x$ is too small. Here it helps to know that skew lines belong to parallel planes. The answer, if it is nonempty, is going to be some part of the line equidistant from the intersection of the projection. This can be expressed in terms of the relevant angles without much extra difficulty.
> 1 votes

---
Tags: algorithms, mathematical-programming
---