# Question
Title: Help me identify the type of Knapack Problem I am dealing with
I have a multiple knapsack problem I am trying to solve. To get the right solution, we need to ask the right question. My question is simply to identify what type of problem I have, not to solve the problem itself.

**The Problem**

I have a theoretically large model train track with dozens of short identical trains on it. I need to buy some power supplies to power my model trains.

The track is split in to equal length sections. I have a data structure that describes the power consumption for each individual length of track based on the movement of the trains. Each length has a peak power consumption (for example, when a train needs to accelerate), and an RMS power consumption.

I need to hook my track up to the power supplies, but I can only power contiguous lengths of track for each power supply. I can't power track section 1 with power supply A, then skip track section 2 and power track section 3 with the same power supply A. I have to power either track section 1, 2, and 3, or just 1 and 2, or just 1.

There is only one type of power supply that has a peak and RMS power output limit. When looking at a combination of lengths of track, I combine their power profiles to get a new RMS and peak power for the combined section. If one of these values goes over the power supply limit, it will not work. Assume that no individual length of track on its own will violate the RMS/peak limit of a power supply.

You cannot/will not have more than 1 power supply per length of track.

You can have at most 10 lengths of track on one power supply. You cannot have 11+ lengths of track hooked up to one power supply. The cord is not long enough.

The goal is to FIRST minimize the number of power supplies (these things are expensive) I have to purchase and THEN determine the most optimal distribution of power such that no power supply is loaded significantly heavier or lighter than any other.

Another way of looking at it is:

**Limits**

* All knapsacks have the same capacity (10 items max).
* All items have the same volume.
* All items have different weights (densities).
* All items come in a specific order (a circuit) and must be put into a knapsack with only adjacent items.

**Goals**

1. Minimize (optimize) the number of knapsacks first.
2. Distribute the items as equally as possible such that no backpack is lighter or heavier than it should be.

**Considerations**

I might be asking more than one question here: One about optimization and the other about the knapsack classification. Is this actually a knapsack problem since the items don't have a value/profit? Does the adjacent/contiguous limit I put on the problem make it easier or harder to solve? Should I be considering anything from graph theory because my track is like a bunch of nodes and edges? Or is that an unnecessary complication.

The question still remains: Classify the type of knapsack problem, or at least extract the correct one from the above problem statement.

Please point me in the right direction.

**Notes**

The weights can be rounded to integers if that helps.

# Answer
> 1 votes
There's no special "name" for this problem that I'm aware of. Don't assume that problem specifications this specific will necessarily have a "name" or "type".

Instead, it's simply one of many problems that can be solved straightforwardly with dynamic programming. You fill in an array $A\[1..n\]$, defined as follows: $A\[i\]$ is the minimum number of power supplies needed to provide power to sections $1,2,3,\dots,i$. Then there is a simple recurrence for $A\[i\]$ that allows you to fill in the entire array in $O(n)$ time, namely,

$$A\[i\] = 1 + \min \\{ A\[j\] : 10-i \le j \< i \text{ and } P(j,i-1)\\}$$

where $P(j,i-1)$ is true if a single power supply can power sections $j,j+1,\dots,i-1$ simultaneously.

This allows you to compute the minimal number of power supplies needed.

Then, once you know this number, you can know optimize things to find the most equal distribution of power. Let $k$ denote the number of power supplies, and $\mu$ denote the average power per supply when using $k$ supplies. Given a constant threshold $t$, you can determine whether there exists a way to power all sections using $k$ power supplies such that every power supply's power consumption falls in the range $\mu-t \dots \mu+t$, using similar methods. Now use binary search on $t$ to find the minimal $t$ such that this is possible. This will give you the solution to your problem.

In general, computer science provides many techniques that can be combined in creative ways to solve problems. When you have a new problem with multiple specific requirements, you might have to look for how to apply those techniques in a way specific to your particular situation; there's no guarantee that it will fall cleanly into some existing "category" or "type".

---
Tags: optimization, knapsack-problems, packing
---


title: Output cycle found by DFS

text:
# Question
Title: Output cycle found by DFS
We can use DFS to find a cycle in a given graph. The idea is that a cycle exists if we can find back edge in the graph. First I just want to detect if a cycle exists, if so return true else false. Here is what I have got so far:

```
DFS(G,s)
  for all v in V do
    color[v] <- white; parent[v] <- nil
  end for
  DFS-Visit(s)

```

`G` is the given graph and `s` is the starting node.

```
DFS-Visit(u)
  color[u] <- gray
  for all v in Ajd[u] do
    if color[v] = gray then
       return true // found cycle
    if color[v] = white AND DFS-Visit(v) then
       return true // found cycle rooted in v
  end for
  color[u] <- black
  return false // no cycle found

```

`Ajd[u]` is the list of u's neighbours. So by processing the children of u we might discover a node that is marked gray. If so u and v are connected with a back edge and we found a cycle.

Now I want to extend this algorithm to output the found cycle. Any ideas on how to do that? I thought about using a stack and simply push all u's in DFS-Visit onto the stack. When true is returned I can output the cycle by taking the nodes from the stack. What do you think?

---

Using a stack won't solve my problem, because the stack will contain nodes that are not part of the cycle.

---

I have another idea. When we found a cycle we know `v=u`. To print the cycle we have to go back using the parent list until we reach `u`:

```
DFS-Visit(u)

  color[u] <- gray
  foundCycle <- false
  vv <- nil

  for all v in Ajd[u] do
    if color[v] = gray then
       vv <- v
       foundCycle <- true // found cycle
       break
    if color[v] = white then
       parent[v] <- u
       DFS-Visit(v)
  end for
  color[u] <- black

  if foundCylce then
      printCycle(vv, u)

printCycle(v,u)
  if v=u then
     print v
  else
     print v
     printCycle(parent[v], u)

```

# Answer
> 2 votes
> When true is returned I can output the cycle by taking the nodes from the stack.

The stack contains the nodes you still have to visit, so they can not be part of the cycle.

There are at least two options to actually obtain data from a DFS.

* Create the DFS tree explicitly; this gives you full information.
* If you only want one cycle, you can store a pointer to the visited node's parent (the tree edge) instead of labelling it `gray`.

---
Tags: algorithms, graphs, graph-traversal, searching
---


# Question
Title: What does tilde mean, in big-O notation?
I'm reading a paper, and it says in its time complexity description that time complexity is $\tilde{O}(2^{2n})$.

I have searched the internet and wikipedia, but I can't find what this tilde signifies in big-O/Landau notation. In the paper itself I have also found no clue about this. What does $\tilde{O}(\cdot)$ mean?

# Answer
> 38 votes
It's a variant of the big-O that “ignores” logarithmic factors:

$$f(n) \in \tilde O(h(n))$$

is equivalent to:

$$ \exists k : f(n) \in O \\!\left( h(n)\log^k(h(n)) \right) $$

From Wikipedia:

> Essentially, it is big-$O$ notation, ignoring logarithmic factors because the growth-rate effects of some other super-logarithmic function indicate a growth-rate explosion for large-sized input parameters that is more important to predicting bad run-time performance than the finer-point effects contributed by the logarithmic-growth factor(s). This notation is often used to obviate the “nitpicking” within growth-rates that are stated as too tightly bounded for the matters at hand (since $\log^k n$ is always $o(n^\varepsilon)$ for any constant $k$ and any $\varepsilon \> 0$).

---
Tags: landau-notation
---


# Question
Title: How does an NFA use epsilon transitions?
In the picture below, I'm trying to figure out what exactly this NFA is accepting.

What's confusing me is the $\epsilon$ jump at $q\_0$.

* If a $0$ is entered, does the system move to both $q\_0$ **and** $q\_1$ (the accept state)?
* If a $1$ is entered, does the system move to both $q\_1$ and $q\_2$?
* Does the system only move to $q\_1$ (accept state), if *no input* is given (empty string)?

# Answer
> 14 votes
Every time you are in a state which has a $\epsilon$ transition, it means you automatically are in BOTH states, to simplify this to you:

If the string is $\epsilon$ then your automata ends both in $q\_0$ and $q\_1$

If your string is '0' it'll be again in $q\_0$ and $q\_1$

If your string is '1', it'll be only in $q\_2$, because if you look from the point of $q\_0$, you have a '1' transition to $q\_2$, but you have also to look at case you're in $q\_1$(if you were in $q\_0$ you always were in $q\_1$ also) then there is no '1' transition, so this alternative path just "dies".

Just by looking at these cases its easy to see that your automata accepts $\epsilon$, $0^\*$, and going from $q\_0$ to $q\_1$, the only way to reach $q\_2$ is $0^\*11^\*1$, so, this resumes your automata to $\epsilon$, $0^\*$, $0^\*11^\*1$

Hope this helped you, if you have any further doubts, just ask!

# Answer
> 6 votes
In state $q\_0$ without reading any input the NFA both stays in $q\_0$ and (in an alternative universe, if you will) it also moves to state $q\_1$. This is similar to what would happen in an NFA which had two transitions to different states on an input of a character. In particular, your NFA accepts the empty string, since on no input it can make a transition to the accept state $q\_1$.

Continuing your example, from state $q\_0$ seeing input $0$, it would consume that symbol, stay in state $q\_0$ (the loop) and also go to state $q\_1$, thereby accepting input $0$. In state $q\_0$ reading input $1$, the NFA would go to state $q\_2$. It might also not consume the $1$, change to state $q\_1$ in another universe and get stuck there (and not accept, since it hadn't read all the input), since there's no transition from $q\_1$ on a $1$.

See if you can convince yourself that the language accepted by this machine is denoted by the regular expression $0^\*+0^\*11^\*1$, i.e., any string consisting of zero or more $0$s followed by either nothing at all or two or more $1$s.

---

By the way, there's an algorithm which takes an NFA with $\epsilon$-moves and produces an equivalent NFA without $\epsilon$-moves, which I expect you'll learn shortly.

# Answer
> -1 votes
I tried construct DFA for this NFA

$\sum$ - alphabet set

$Q$ -states set

$\sigma(Q\times (\sum \cup {\epsilon} )) \to P(Q)$ state func

$q\_0 = q\_0$

$ F \subseteq Q, F = \\{q\_0\\}$

Because every NFA has equal DFA lets construct DFA $M'$ for this given NFA.

alphabet - the same

$Q' = P(Q)$ - states

Current state is $R \in P(Q)$

$E(R)$ - epsilon closure return set of states reachable over zero or more $\epsilon$ - connections for every $r \in R$

$\sigma'(R,a) = \bigcup\_{r \in R} E(\sigma(r,a)) $ -transitions

$q'\_{0} = E(\\{q\_0\\})$

$F' = P(Q) \div F$

Some compute on this FSM

$1.$ $\epsilon$ on input: $q'\_{0} = E(\\{q0\\}) = \\{q\_0, q\_1\\}$ initial state include $q\_1$ so FSM accept $\epsilon$

$2.$ $0\*$ on input: $ \sigma'(\\{q\_0, q\_1\\}, 0) = E(\sigma(q\_0,0)) \cup E(\sigma(q\_1,0)) = \\{q\_0, q\_1\\} \cup \\{ \\} = \\{q\_0, q\_1\\}$ so FSM accept $0\*$

at least $\\{\epsilon, 0\* \\} \subset L (M')$

Thanks to David Richerby

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Training a model based on polynomial regression and then putting that into a linear regression, vs just using the linear regression
I'm doing some machine learning work in python with sklearn. Basically the problem is trying to predict how long an event will take based on 4 correlated pieces of data. What I've been doing is I have four polynomial regression trained on each piece of data respectively. Then I take the output of these polynomial regressions and train a linear regression based on that. Testing this against historically data has show that the two step process has about 10% less sum-squared-error than just using the linear regression. Should I not be doing it this way? What is the theory behind just using a one step process vs. using both steps?

# Answer
There's no one answer about how you should/shouldn't do it. There are two perspectives out there:

**If it works, go for it.** One perspective is: if it gives good results, that's all that matters. So, if you get more accurate regression, great for you. Try a bunch of approaches and pick whatever works best (taking care to avoid overfitting).

**Model the underlying phenomenom.** The other perspective is: choose a model that represents how the underlying physical process works. So, from this perspective, we can't say what you should do, since you haven't told us how the underlying process works; we have no basis for evaluating whether that's a reasonable way to model reality.

There are many possible models one could imagine that map 4 continuous features $x\_1,x\_2,x\_3,x\_4$ to a continuous output $y$. You could use linear regression:

$$y = a\_1 x\_1 + a\_2 x\_2 + a\_3 x\_3 + a\_4 x\_4 + b$$

Or you could use polynomial regression:

$$y = p(x\_1,x\_2,x\_3,x\_4)$$

where $p(\cdot)$ is some multivariate polynomial in 4 variables with degree at most $d$ (for some $d$ you choose). Or you could use what you're doing:

$$y = a\_1 p\_1(x\_1) + a\_2 p\_2(x\_2) + a\_3 p\_3(x\_3) + a\_4 p\_4(x\_4) + b$$

where $p\_1(\cdot),\dots,p\_4(\cdot)$ are univariate polynomials with degree at most $d$.

Or you could fit some other nonlinear function (see nonlinear regression), or fit a piecewise linear function, or use cubic splines, or use kernel smoothing or LOESS regression (see local regression). There are so many options. We can't tell you which to use from the information you've provided.

**Advice.** Usually, a good rule of thumb is that if you understand the underlying process well, use a model that matches the underlying reality. If you don't know the underlying process, try multiple approaches and see which works best (using cross-validation to avoid overfitting).
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Find perfect matching faster than MCM, in graph that has perfect matching?
Given an unweighted bipartite graph which has a perfect matching, is there an algorithm for finding a perfect matching in the graph that is faster than the best known algorithm for finding a maximum cardinality matching (MCM)? For example, is there some way to take advantage of the fact that the graph is known to have some perfect matching to help find one faster?

If yes, could you please help to point out some references? If it is impossible, could you briefly explain the reason? Comments and suggestions are also welcomed.

# Answer
> 1 votes
Hopcroft-Karp isn't necessarily optimal, and you can already find asymptotically faster algorithms in the relevant Wikipedia pages: https://en.wikipedia.org/wiki/Matching\_(graph\_theory)#In\_unweighted\_bipartite\_graphs, https://en.wikipedia.org/wiki/Maximum\_flow\_problem#Solutions. Note that you can use any network flow algorithm to find a perfect matching.

For instance, you can achieve $O(n^{2.373})$ running time using fast matrix multiplication, though this is only a theoretical result; in practice it's slower. However, this is already enough to demonstrate that there's no way we're going to prove that you can't do better than Hopcroft-Karp (because you *can*). For sparse graphs ($|E|=O(n)$), Madry's algorithm achieves $O(n^{1.43})$ running time. Neither of these use/exploit the fact that the graph already contains a perfect matching.

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


# Question
Title: Decision problems: Does a "constant" characteristic function describe a language in P?
I am new to complexity theory and I have some maybe stupid questions:

Are "decision problems" with the characteristic functions x(t)=1 or x(t)=0 "decision problems" or not?

If yes: Are the corresponding formal languages members of P or not?

(The calculation time needed is constant.)

If the answer is yes in both cases:

If $P\neq NP$ no P decision problem can be NP-complete. This is easy to prove.

I have read that if $P=NP$ all P decision problems would be NP-complete. This is easy to prove for all other problems however the problems described above cannot be complete in any way.

Are these problems an exception?

# Answer
Yes, of course they're in **P**: you can decide them in constant time, which is certainly bounded by a polynomial.

Anybody who tells you that **P$\\,=\\,$NP** implies that every problem in **P** is **NP**-complete has forgotten about these two trivial problems. Neither of them can be **NP**-complete, because **NP**-completeness is defined in terms of many-one reductions, but there cannot be a many-one reduction from a non-trivial probelm to either of the trivial problems. A many-one reduction from $A$ to $B$ must map "yes" instances of $A$ to "yes" instances of $B$, and "no" instances to "no" instances. But one of the trivial problems has no "yes" instances and the other has no "no" instances, so a problem that has both "yes" instances and "no" instances cannot be reduced to either.
> 2 votes

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


# Question
Title: Minor Mistake in Computability, Complexity, and Languages?
In the book *Computability, Complexity, and Languages* (2nd edition), Martin Davis writes in chapter 1 (Preliminaries), section 2 (Functions):

> A *partial function on a set* $S$ is simply a function whose domain is a subset of $S$. An example of a **partial function on $\mathbb{N}$ is given by** $g(n) = \sqrt n$, where the domain of $g$ is the set of perfect squares.

So far so simple. But he goes ahead and writes a couple lines later at the end of the section:

> We will sometimes refer to the idea of *closure*. If $S$ is a set and $f$ is a partial function on $S$, then $S$ is *closed under* $f$ if the range of $f$ is a subset of $S$. For example, $\mathbb{N}$ is closed under $f(n) = n^2$, but is not closed under $h(n) = \sqrt n$ (**where $h$ is a *total* function on $\mathbb{N}$**).

So in the first quote $\sqrt n$ on $\mathbb{N}$ is an example for a *partial* function, whereas in the second quote the same function is an example for a *total* function.

Both examples seem to contradict each other. Or am I missing something in regard to closures here?

# Answer
There's no contradiction, here. The first case defines the partial function $g\colon \mathbb{N}\to\mathbb{N}$ given by $$g(n) = \begin{cases} x &\text{if $x\in\mathbb{N}$ and }x^2=n\\ \text{undefined} &\text{if no such $x$ exists.} \end{cases}$$ As the text says, "the domain of $g$ is the set of perfect squares."

The second case defines the total function $h\colon\mathbb{N}\to\mathbb{R}$ given by $$h(n) = x \quad \text{if }x\in\mathbb{R}\_{\geq 0} \text{ and } x^2=n\\,.$$ The domain of $h$ is the set of all the natural numbers.

You say that these are the same function, but they are not. $g(2)$ is undefined but $h(2)$ is defined (and equal to $\sqrt{2}$). $h$ associates a square root with every natural number but $g$ only associates square roots with natural numbers that are perfect squares.

$\mathbb{N}$ is closed under $g$ because, whenever $g$ is defined, $g(n)\in\mathbb{N}$. $\mathbb{N}$ is not closed under $h$ because, for example, $2\in\mathbb{N}$ but $h(2)\notin\mathbb{N}$.
> 12 votes

# Answer
In the second example, $h(n)$ is defined for all natural numbers $n$; when $n$ is not a square, $h(n)$ is some irrational quantity, and in particular not a natural number.

In other words, the set of natural numbers is not closed under taking square roots: for example, $\sqrt{2}$ is not a natural number.
> 6 votes

---
Tags: mathematical-foundations
---


title: What is a sparse classifier?

text:
# Question
Title: What is a sparse classifier?
Given a two-dimensional data set where each point is labeled $ \\{0,1\\}$, I want to implement a sparse classifier with $L\_p \ \text({ 0\<p \leq 1) }$.

I have been reading on logistic regression and regularization. Let me give you an example of what I have been working on. The concrete example is: Let $\left((x^{(i)},y^{(i)} )\right)\_{i\in \\{1,\dots, m\\}} $ be my data set with $y^{(i)}\in \\{0,1\\} $ and $x^{(i)}\in \mathbb{R}^2$. And the cost function I minimized is

$ J(\theta) = - \frac{1}{m} \cdot \sum\_{i=1}^m \large\[ y^{(i)}\ \log (h\_\theta (x^{(i)})) + (1 - y^{(i)})\ \log (1 - h\_\theta(x^{(i)}))\large\] + \frac{\lambda}{2m}\sum\_{j=1}^n \theta\_j^2$.

where $h\_\theta(x) = \frac{1}{1+e^{-\theta^{T}x}}$. I thought that this would be a good introduction to sparse.
Currently I use a neural networks and was wondering if I am heading in the right direction in understanding sparse methods.

That leaves me with the question:

What is the definition of sparse classifiers? What would be an example?

# Answer
I'll provide an example model using linear regression, however the idea translates to classification in a straightforward manner.

Sparse linear regression is used when we have a model $y = X\beta + \epsilon$ where $y \in \mathbb{R}^n$, $X \in \mathbb{R}^{n \times p}$, $\beta \in \mathbb{R}^p$ and $\epsilon \in \mathbb{R}^n$ when $n \ll p$. If we expect only a small number of columns in $X$ to actually contribute to $y$ then we can impose a penalty on $\beta$ such that "non-important" columns $X\_i$ have their corresponding $\beta\_i = 0$. We can formally write this as $$\arg \min\_{\beta} \\|y - X\beta \\|^2\_2 + \lambda\\|\beta\\|\_0$$ where $\\|\cdot\\|\_0$ is the $\ell\_0$ norm that counts the number of non-zero entries. Unfortunately fitting this model exactly is difficult. We can approximate this objective by using the $\ell\_1$ norm instead. That is we find $\beta$ for $$\arg \min\_{\beta} \\|y - X\beta \\|^2\_2 + \lambda\\|\beta\\|\_1.$$ This model is known as LASSO in the context of linear regression and can be fit by a variety of methods in relatively little time.

All of this hinges on $n \ll p$. If your data are of the form when $n \approx p$ or $n \> p$ I'm not sure if sparsity will help much, as you should have enough data to guide inference to true $\beta$ values (provided other assumptions hold, heteroskedasticity, independence, etc). The key takeaway is that you have a large number of predictors and you suspect a small amount of them to actually characterize $y$.
> 1 votes

# Answer
Sparsity implies that only a small portion of input variables are influencing classification. So sparse classifier's job is to find this small portion of variables. An example would be L1-norm based SVM.
> 0 votes

---
Tags: machine-learning, classification
---


# Question
Title: two laws of De Morgans law and its used as NAND gates and NOR gates
how the all gates can be made by only these two . Yes i know the circuit diagram of basic gates by universal gates which i have learnt. but if there is complex circuit like XOR gate or any other expression how would you make it please upload some links or material to explain the stuffs

# Answer
> 1 votes
Instead of asking, finding out yourself is a very helpful learning experience.

Given two possible inputs x and y, how many possible logical functions are there?

a. Which functions of x and y can you implement using a single NAND gate? (Hint: The possible inputs are x and x, y and y, x and y).

b. Which functions of x and y can you implement using a NAND gate and inputs x, y, or a function found in (a)?

c. Which functions of x and y can you implement using a NAND gate and inputs x, y, or a function found in (a) or (b)?

and so on until you found how to implement each possible function.

---
Tags: digital-circuits
---


# Question
Title: Enumerate all ways to bin a series of integers into N bins, where each bin only contains contiguous numbers
I want an algorithm to list all possible ways to map a series of integers $M = \\{1,2,3,...,m\\}$ to another series of integers $N = \\{1,2,3,...,n\\}$ where $m \> n$, subject to the constraint that only contiguous integers in $M$ map to the same integer in $N$.

E.g.: 5 -\> 2:
(1, 2, 3, 4), (5)
(1), (2, 3, 4, 5)
(1, 2, 3), (4, 5)
(1, 2), (3, 4, 5)

This seems like it should be a standard problem with a well known solution, but I can't find it.

To clarify, I am not looking for the total number of solutions, but for pseudocode or the name of a corresponding algorithm to exhaustively list all solutions.

# Answer
Suppose that the image of your mapping has size $k$. This implies a division of $\\{1,\ldots,M\\}$ into $k$ contiguous intervals. By identifying each such interval with its largest point, we see that there are $\binom{M-1}{k-1}$ such partitions (since $M$ is always one of the $k$ largest points). For the actual colors chosen, the number of choices is $N(N-1)\cdots(N-k+1) = N!/(N-k)!$. The total number of mappings is thus $$ \sum\_{k=1}^N \frac{N!}{(N-k)!} \binom{M-1}{k-1}. $$ Using this argument, it is not too hard to construct an algorithm to list all such mappings; the algorithm completely mirrors the argument.
> 1 votes

# Answer
Enumerating all of them is quite easy:

The first number goes into the first bin.

For all other numbers: If you used n numbers, put the next number into the last bin (because you can't start another bin). If the number of remaining numbers equals the number of empty bins, put the next number into the next empty bin (because you wanted to use n bins; you need to use the next bin or you will have unused bins). Otherwise, enumerate both choices, where you put the next number into the last used bin or the first unused bin.

The execution time would be proportional to the size of the output
> 0 votes

# Answer
Attempted a solution in python (`start` corresponds to the first element in $M$, `stop`-1 corresponds to the last element in $M$, and `nbins` corresponds to $|N|$):

```
import itertools
def find_bins(start, stop, nbins):
    if (nbins > 1):
        return list(list(itertools.product([range(start, ii)], find_bins(ii, stop, nbins-1))) for ii in range(start+1, stop-nbins+2))
    else:
        return [range(start, stop)]

```

It gives a human readable answer, but the output needs some cleanup.
> -2 votes

---
Tags: algorithms, enumeration
---


# Question
Title: How a computer ensures that a location in RAM is empty
When we declare a variable, how does it get stored in a memory? How does the compiler know from within millions of memory locations which ones are currently not in use or are empty so that it can store the variable there? If it traverses each memory location the whole memory address space and checks on each location whether it is used by some other process or not, it will take like forever until it can allocate memory for a single variable.

# Answer
In a multitasking system, every process receives its own *virtual address space*, i.e. the system maps the addresses from $0\_h$ to $FFF\cdots F\_h$ to available storage space which can reside partly in RAM memory and partly on disk (*physical storage*). The mapping is made for every process independently, allocating whole *pages* (typically 2K bytes) at a time.

The compiler is completely unaware of where the data will actually be stored and is free to use the whole address space. The system does the necessary housekeeping and ensures that there are no conflicts.

Actually, the mapping is completely dynamic and pages are moved between RAM and disk, following the needs of the processes and in a way to optimize the access speed. There is not even a relation between the size of the virtual address space and the amount of RAM and disk available.

To summarize, memory allocation is transparent to the compiler, as if the process was alone; only the system knowns which physical pages are free or allocated to a particular process.
> 2 votes

---
Tags: memory-management
---


# Question
Title: What is the optimal substructure for this greedy-algorithm solvable problem (Domino Piling)?
On Codeforces, the first problem that comes up for the tag "greedy" is "50A: Domino Piling". Here is the problem:

> You are given a rectangular board of M × N squares. Also you are given an unlimited number of standard domino pieces of 2 × 1 squares. You are allowed to rotate the pieces. Find the maximum number of dominoes you can place on the board so that each domino covers exactly 2 squares and no dominoes overlap.

I solved it quite easily: the solution is just `floor(M*N/2)`.

I read that in order for a problem to be solved Greedily, it needs to have "optimal substructures". For this problem, what were the "optimal substructures"?

Thank you in advance.

# Answer
> 1 votes
I think there's a slight misunderstanding in the question. The phrase is "optimal substructure", not "optimal substructures". It's not a matter of looking at the individual substructures (e.g., regions of the grid you're trying to tile) and saying, "This one's optimal", "This one's optimal", "This one isn't". Rather, it's a matter of looking at the structure and interactions of the subproblems and saying, "The substructures of this problem (i.e., the subproblems) interact in a way that lets me find an optimal solution easily."

I also don't think this is a great example for greedy algorithms, since greedy algorithms are naturally somewhat recursive and it's so easy to domino-tile a grid iteratively that it feels artificial to force it into a recursive solution. But here goes...

One example of optimal substructure is that, if you can divide your grid into rectangles $A$ and $B$ and you can perfectly tile $A$, then an optimal tiling of the whole grid can be made from the perfect tiling of $A$ along with an optimal tiling of $B$. This gives the following greedy algorithm.

```
function tile (int width, int height, int startrow)
if (startrow <= height-1)
    perfectly tile rows startrow and startrow+1 like this | | ... |
    tile (width, height, startrow+2)
else if (startrow == height) then
    tile the last row like this -- -- ... -- , with one empty square
    at the end if width is odd
/* else startrow > height and there's nothing to do */

```

Note that this just produces tilings like this one for a $7\times3$ grid,

```
| | | | | | |
| | | | | | |
--- --- ---

```

which is exactly what you'd do iteratively.

---
Tags: algorithms, greedy-algorithms
---


# Question
Title: History/Etymology- Map/[Hash]Map vs map()
Forgive me/delete this question if it doesn't qualify as Computer Science:

I've always wondered about the relationship between Map the data structure and map() the function. I know they are two different things. Why share the name?

# Answer
> 0 votes
Well, I am only a beginning MSc student in computerscience but if if followed the classes correctly the purpose of a hash is to create some memory space, let say this memory space is 10 adresses big. With a hashmap, every value you put in the hashmap gets coupled with a key. That key will first be mapped by a hashfunction to produce a unique number. That number is within the range of possible adresses in the vector. $ f: A \mapsto B $ with A the collection of possible keys and B a collection of possible adresses. Mathematically speaking this is a mapping. The value gets then saved to that adress. Now it is possible that you want to save more values than the vector allows or the hashfuntion is not completely one on one (that is every y has a unique x value it corresponds to) In that case you wil need to make the vector longer and remap every value within the vector or you reshash the value from the hashfunction with that same same value it has returned (usualy slightly edited to avoid all values being at the same place in the vector) as the parameter to find a new adress that wasn't used before. There are a number of other techniques involved and other methods but that is beside the point. Long story short. This mapping of key values is, i believe, the reason it is called a hashmap.

---
Tags: data-structures
---


# Question
Title: What are some possible "functional" memory structures?
With my thin knowledge on embedded systems, compilers, and computer architectures, I know that the basics of computer memory(physical) are sort of like an array, with addressing which work like pointers. I see that imperative programming(which eventually unwraps to assembly, or the Turing Machine) fits this architecture very well.

I am a bit interested to see if there is a counterpart of physical memory that might fit the functional programming style. By "fitting", I am making the assumption that all pure functional languages can unwrap to be immutable lambda expressions(via Lambda Calculus). Now, with the array-like memory structure, we have to allocate and gc objects under the scene in order to get lambdas to work(because lambda expressions do not address operations on memory directly). Just as a thought experiment, is it possible to have a device that fits the need of memory in lambda expressions, while not containing a garbage collector?

Yes, I know that some imperative programming languages do use garbage collectors. However, when boiled down to assembly, it doesn't. So I am more curious about the evaluation of "pure" lambda expressions.

Just as a note, the *lambda expressions* I talk about include the fixed point operator(i.e. recursion).

# Answer
> 3 votes
The topic is fairly broad.

Functional hardware has been explored in e.g. Lisp machines.

More on the theoretical side, you may want to read about the various abstract machines which have been proposed for running functional languages. Some of them are the SECD machine, the CAM (categorical), the Krivine machine, the STG machine.

Perhaps a more radical approach can be learnt by looking at the various graph-reduction machines. A pioneering work by Lamping describes how lambda can be run faster by rewriting graphs (!), instead of expressions. More recently, linear logic simplified the several rewriting rules.

Some of these approaches can give you some hint at how a custom functional hardware should be made to speed up execution.

For conventional hardware, the STG machine seems one of the most promising approaches.

---
Tags: functional-programming, garbage-collection, lambda-calculus
---


title: K String Turing machine

text:
# Question
Title: K String Turing machine
Given any $k$-string Turing machine $M$ operating within time $f(n)$, we can construct a single-string Turing machine $M$ operating within time $O(f(n)^2)$ such that for any input $x$, $M(x)=M(x)$

How can we prove that converse is false?

# Answer
Just take $k=1$ and use the time hierarchy theorem.
> 1 votes

---
Tags: algorithms, algorithm-analysis, turing-machines
---


# Question
Title: How do I find the roots of the disconnected subgraphs of a directed graph?
If I have a directed acyclic graph $G(V,E)$, which may consist of several disconnected subgraphs $G\_i(V\_i,E\_i) \subset G(V,E)$, how do I find the root of every subgraph $G\_i(V\_i,E\_i)$?

# Answer
You can apply the following algorithm:

1. Identify the weakly connected components (i.e., the disconnected subgraphs). To do this, you can turn all edges into undirected edges and, then, use a graph traversal algorithm.
2. For each component, select the node that has no incoming edges (i.e., the *source* node) as the root. If there is more than one source node, then there is no root in this component.

Note that this solution assumes the root of a directed acyclic graph $G=(V,E)$ to be a node $r$ such that $\forall v \in V-\\{r\\} \Rightarrow \exists P=\[(r, v\_1),(v\_1,v\_2), ...,(v\_{n-1},v)\]$, where $P$ represents a directed path from $r$ to $v$.
> 1 votes

# Answer
It should be:

$V - \\{ b\ | \exists a. (a,b) \in E \\}$

This is, all the vertices exept those which are the destination of some directed edge
> 1 votes

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


title: Compute RTT in theoretical system

text:
# Question
Title: Compute RTT in theoretical system
This is problem from my Networks class. It wants us to compute the round trip time of a point-to-point network and I'm just not sure which information is pertinent. The question:

NASA deployed its latest 622Mbps point-to-point laser link between Earth and a
new lunar base. The distance from the Moon to Earth is approximately 385,000 km, and data travels over the link at the speed of light 3 x 10^8 m/s.

(a) Calculate the minimum RTT for the link

I'm not sure whether I should be using the 622 Mbps or the distance and speed of light. My initial thought was using distance and speed of light. Meaning, the minimum would be (385,000\*1000)m /(3x10^8 m/s)\*2 = 2.56666 seconds.

But if you use the 622 Mbps you can compute, for the minimum it would be quickest if you only sent one bit, and the other host immediately responded with one bit meaning that the RTT would be 2\*(1/(622\*1,000,000)) = 3.215 e-9 seconds.

To me it seems like it should be the former, but if the link is 622 Mbps why would it take longer?

EDIT: to clarify don't tell me which answer is correct, as it is homework. I would like to understand the concepts involved with why RTT is unrelated to Mbps.

# Answer
Why would it take longer than a few nanoseconds to get a message to the Moon and back? Because physics. Nothing can go faster than the speed of light.

Instead of packets on a network, think of suitcases on the baggage reclaim belt at an airport. The number of suitcases the airport workers put on the belt each second is the data rate; the length of time it takes a suitcase to go all the way around the belt is the round-trip time.

Suppose the airport employs more staff to throw luggage around. They can now put, say, twice as many suitcases onto the belt every second, but the belt doesn't move any faster so each individual bag still takes the same amount of time to go around. They've increased the data rate but not the round-trip time. Because they're putting bags onto the belt more quickly, but the belt itself isn't moving any faster, there will be more bags in transit on the belt at any time.

Suppose that, instead of hiring more staff, they make the belt move twice as fast. Now, you don't get any more bags per second but each bag only takes half the time to go around. They've decreased the round-trip time but not the data rate. Because bags now get delivered to waiting passengers faster, but they only appear at the original rate, there will be fewer bags in transit on the belt at any time.

So, you see that data rate and round trip time are essentially independent. The data rate is how many bits you can send each second, and the trip time is how long each individual bit takes to reach its destination. You should now be able to figure out what the round trip time is, and also answer more complicated question like, "How long does it take to get a gigabyte of data to the moon on this link, and receive an acknowledgment that the final packet arrived?"
> 1 votes

---
Tags: computer-networks
---


# Question
Title: Find unambiguous grammar for an ambiguous grammar
Hi I want to find an unambiguous grammar for a known ambiguous one, and the production is like this:

```
S->bA|aB
A->a|aS|bAA
B->b|bS|aBB

```

I have found the string to prove this grammar is ambiguous: bbaaba. I wonder whether it is doable to convert the grammar into unambiguous. I have approached it from this perspective: in the above counter-example, the difference shows up when we have AA in the list, then whether we are changing the first A to contain S or the second will make the next step different. So I think maybe I can restrict A to go only via the first or the second A and hence eliminate the ambiguity, like this:

```
S->bA|aB
A->a|aS|baA|baSA
B->b|bS|abB|abSB

```

I'm not sure whether my approach or answer is correct or not. I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

# Answer
> I'm not sure whether my approach or answer is correct or not.

It is not correct. Your modified grammar can produce at most three consecutive 'a's or 'b's, while the original grammar can produce an unbounded number of consecutive 'a's or 'b's.

Your approach starts fine by looking for counterexamples, but then runs into a trap by staying too close to the given grammar. This is a trap, because the problem asks for extensional equality of languages. After you isolated the critical part of the grammar which generates the problem, you should first try to understand the generated language (that interacts with that part), before starting to modify the grammar.

> I understand there is no algo for this kind of conversion, but are there any kind of 'common steps' for getting the unambiguous grammar?

1. Your first step to look for a counterexample and isolate the part of the grammar which generates the problem makes sense.
2. My next step would be trying to understand the generated language. Let me try your example:

From S, I can generate any number of 'a's, followed by the same number of 'b's, and end up in S again. Can I ever generate more 'a's than 'b's? No, the number of 'a' or 'A' on the left side is identical to the number of 'a' or 'A' minus 'b' or 'B' on the right side for all rules. Can I generate any string with the same number of 'a's and 'b's? Yes, because ...

Ah, so the generated language is simply the language where the number of 'a's equals the number of 'b's.

3. After you understood the generated language, you can try to determine whether it can be generated by an unambiguous grammar, and write down such a grammar if desired. Let me try for your example:

The generated language is so simple, I would have heard if this language were ambiguous. It should even be deterministic, I can just push 'a's on the stack when there are more 'a's than 'b's, and push 'b's on the stack when there are more 'b's than 'a's. Of course, when the symbol on top of the stack differs from the current symbol, then I will just pop it. I know it is possible to convert this sort of deterministic PDA into a deterministic grammar, so I'm done without even trying to write down any specific deterministic grammar.
> 1 votes

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


# Question
Title: Is every undecidable language reducible to any other undecidable language?
For the undecidable languages I have seen so far , I am able to give a reduction from one language to other . Is it the case that every undecidable language is reducible to every other undecidable language?

If not can you prove that there exists 2 undecidable languages A and B such that A is not reducible to B.

Note : I am not talking only about mappping reducibility . I am talking about reducibility in general .

# Answer
> 7 votes
There is no concept of "reducibility in general". You always have to specify the power of the reduction. For example, if you allow mapping reductions but with literally any function (not necessarily a computable function) performing the mapping, then any language is reducible to any non-trivial language (i.e., anything other than $\emptyset$ or $\Sigma^\*$).

If you do limit the power of the reduction in any way, then there are always pairs of problems $X$ and $Y$ such that $X\not\leq Y$. For example, take any language $X$ that isn't decidable in whatever model of computation you're using to define your reductions. Under that model of reductions, $X\not\leq \\{0\\}$.

OK, but you asked about undecidable languages and $\\{0\\}$ isn't undecidable. So, let $H\_0$ be the halting problem for the model of computation you're using for your reductions. Let $H\_1$ be the halting problem for Turing machines that have an oracle for $H\_0$ (if $H\_0$ is decidable, this is just the ordinary Turing machine halting problem), and let $H\_2$ be the halting problem for Turing machines that have an oracle for $H\_1$. Essentially the same proof that the ordinary Turing machine halting problem is undecidable shows that $H\_2\not\leq H\_1$, and both of these languages are undecidable.

---

Actually, I don't think that last paragraph is *quite* right. In the case that your model of reductions is more powerful than Turing machines, you probably need to use the reduction model instead of Turing machines to define the pair of halting problems. I don't have time to fix this right now but I'll come back to it this evening (UK time).

# Answer
> 3 votes
You are probably thinking about undecidable languages which are computably enumerable. Otherwise, the diagonalization technique described in answers to similar questions would have provided simple counterexamples. If you don't care about the computably enumerable part, then I would say that your question is simply a duplicate of one of the similar questions.

The halting problem is at least as strong than any such language, because you can just fix the string for which you want to know whether it is in the language, define a Turing machine which enumerates the strings in the language until it finds the given string and then stops, and then ask the halting oracle whether that Turing machine will stop.

So are there such languages which are weaker than the halting problem and still undecidable? Yes, there are (at least ZFC claims that there are, and most other reasonable formal systems will think so too). Can I write down such a language? No, not at the moment. Does anybody knows how to write down such a language? Maybe, I don't know.

Why do I write an answer, if I can't really provide an explicit answer? Because I want to point out a connection to formal systems. A language strong enough to complement a given axiom system (able to talk about TM like Peano arithmetic (PA) for example) to a consistent set of axioms complete for $\Pi^0\_1$ sentences (i.e. the halting problem) provides enough computational power to construct a model of the given axiom system, and the set of $\Pi^0\_1$ sentences of any model gives such language. The following answer by Noah Schweber first defines what it means to complement PA (as an example)

> A set $A$ of (indices for) $\Pi^0\_1$ sentences is *plausible* if $PA\cup A\cup\\{\neg \varphi: \varphi\in\Pi^0\_1\setminus A\\}$ is consistent.

And then proceeds to show how Rosser's trick can be used to show

> I claim that every plausible set $A$ is of **PA degree**

i.e. construct a model of the given axiom system (PA in this case). And if you had a stronger axiom system like ZFC, then being plausible with respect to ZFC would define you a **ZFC degree**, which is at least as strong as the PA degree. (I guess there are languages of PA degree which are not of ZFC degree, but in this case I don't even know whether ZFC claims this.)

---
Tags: computability, turing-machines, reductions, undecidability
---


# Question
Title: Mapping graph to another graph's sub-graph
How to solve the induced sub-graph isomorphism problem?

# Answer
> 3 votes
To answer the updated question, yes, it can be solved with a SAT solver. The problem is NP-complete, so it is in NP, so therefore it can be reduced to SAT, i.e., expressed in CNF-SAT (see What is the definition of P, NP, NP-complete and NP-hard?). Then you can use an off-the-shelf SAT solver to solve here.

For general techniques, take a look at Converting (math) problems to SAT instances and NP to SAT. How does it works?.

Here are some questions that might also be useful:

# Answer
> 4 votes
This is the induced subgraph isomorphism problem, which was one of the problems proven **NP**-complete in Cook's original paper on **NP**-completeness. For a quick way to see that it's **NP**-complete, you can let $G$ be a complete graph on $k$ vertices to solve CLIQUE on $G'$. Unless you can restrict the form of $G$ and/or $G'$, you're probably out of luck in your quest for a good algorithm.

The problem seems to be easier if you insist that $G$ and $G'$ have the same number of vertices. In this case, you have the graph isomorphism problem. This is generally thought not to be **NP**-complete and, in December 2015, Babai announced an subexponential-time algorithm, which runs in time $\exp\exp(\tilde{O}(\sqrt{\log n}))$, where $\tilde{O}$ denotes hidden factors of $O(\log\log n)$. This is faster than $O(\mathrm{e}^{n^\epsilon})$ for all $\epsilon\>0$. (The algorithm was originally announced as having quasipolynomial running time but an error in the analysis came to light in January 2017.)

---
Tags: algorithms, graphs
---


title: Recurence for Insertion Sort

text:
# Question
Title: Recurence for Insertion Sort
We can express insertion sort as a recursive procedure as follows. In order to sort $A\[1,...,n\]$ we recursively sort $A\[1,...,n-1\]$ and then insert $A\[n\]$ into the sorted array $A\[1,...n-1\]$.

How can I write a recurrence for the running time of this recursive version of insertion sort?

# Answer
> 1 votes
Actually, it is pretty simple. Let $T\_n$ be the running time for a given array $A\[1,...,n\]$. As you've mentioned, we first sort $A\[1,...,n - 1\]$ whose running time is $T\_{n-1}$ (since it has $n-1$ elements) and then we inset $A\[n\]$ to the sorted list, whose running time is $O(n)$ (since we need iterate over the whole array at the worst case).

Therefore, $T\_n = T\_{n-1} + O(n)$. And do not forget about the base case which is $T\_1 = O(1)$.

---
Tags: algorithms
---


# Question
Title: Reduction to longest path from longest chain of tiles
We have some tiles that each tile has 2 number written on it. We can rotate each tile in order to swap the position of numbers. We want to find the longest chain of tiles starting with a certain tile so that adjacent tiles have the same number on their common endpoint. If the tiles were

```
 7-4, 11-8, 11-11, 4-2, 7-5, 11-10, 10-5

```

the longest chain starting with tile `11-8` would be:

```
8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2

```

I tried to reduce this problem to the longest path problem:

* Consider every tile as a vertex.
* If two tiles have a common number in them they are adjacent.
* create a sink vertex and connect it to every other vertices.

the resulting adjacency list of graph is:

```
7-4  : 4-2, 7-5, sink
11-8 : 11-11, 11-10, sink
11-11: 11-8, 11-10, sink
4-2  : 7-4, sink
7-5  : 7-4, sink
11-10: 11-8, 11-11, sink
10-5 : 11-10, 7-5, sink

```

Now for finding the longest chain starting vertex `11-8` you simply have to find the longest simple path form `11-8` to sink which is `8-11, 11-11, 11-10, 10-5, 5-7, 7-4, 4-2`.

But I am being told that in order to say that this problem is reducible to longest path problem I have to prove it the other way around. It means I have to prove that every graph can be represented by some configuration of tiles. However I know that some graphs can't be represented by tiles for example the below graph couldn't be represented by any such tiles.

```
A-----B
|   / |
| /   |
C-----D

```

So technically my approach is wrong. But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles, why isn't it enough to show that this problem can't be solved in polynomial time? Why is it necessary to show that all the graphs can be represented by a combination of such tiles?

# Answer
> 5 votes
> But I wonder, I have shown that in general you have to solve the longest path problem to find the longest chain of such tiles

Not exactly, you have given *a way* of finding the longest chain of tiles (transform the tiles into a graph and solve longest path). There are many other possible approaches (you can try to transform it into a boolean formula and solve a SAT instance).... how do you know that *none* of them is easier? You could also use undecidable problems to solve your tile question (build a turing machine that halts iff the tiles have a solution of some size), it doesn't mean that your problem is undecidable.

Reductions work the other way around. I like to see an NP-hard problem as "a tool that may be used to solve any other NP problem". So **you need to show that your tile problem is one possible tool for solving longest path**. That is, you are given a graph, and you need to describe a set of tiles with the good property (the tiles have a length-k solution iff the graph has a length-k path). This way, you know that your tile problem is a new possible tool for solving longest path, and, in turn, every other NP problem.

PS: there are also errors in the reduction you describe, beside the method problem discussed here: if the same integer appears in three different tiles (say, 4-2,4-7,4-9), then theses three nodes would form a valid path in the graph, but not a valid sequence of tiles. You'll find it easier to see a tile as an edge rather than a vertex

# Answer
> 1 votes
It is much simpler to prove that your problem is NP-hard by reducing it from another problem than longest path problem. It's name is longest trail problem and you are asked to find the longest path in an undirected graph such that no edge is repeated. Note that in longest path problem, no vertex is repeated.

So, given a longest trail problem, every edge corresponds to a tile in your problem. And longest chain in your problem, corresponds to the longest trail in the graph.

See this question, for NP-hardness proof of longest trail problem.

So, if you can solve your problem in polynomial time, you can also solve longest trial problem in polynomial time. However, since longest trial problem is NP-hard, this is not possible unless P = NP. Therefore, we proved that your problem is also NP-hard.

Note that you should always reduce from a problem that you know NP-hard to the problem that you want to prove that is NP-hard.

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


# Question
Title: Algorithms to convert 2D videos to 3D ones
Are there published algorithms that can convert 2D videos to 3D ones? If there are few published algorithms for this I am also interested to know how the conversion quality is.

# Answer
Sure, there are many algorithms for this:

1. Some works, which directly work on H264 domain, such as:

> Real-Time 2D to 3D Conversion from H.264 Video Compression, *Nir Shabat, Gil Shabat and Amir Averbuch* http://www.cs.tau.ac.il/~amir1/PS/3d.pdf

2. Some deep learning methods already exist on the topic: http://homes.cs.washington.edu/~jxie/pdf/deep3d.pdf (this is the review version of the paper, so I could not cite)
3. There are many other works which use images in many ways to create 3D:

http://live.ece.utexas.edu/publications/2011/cao\_mag\_2011.pdf

https://people.mpi-inf.mpg.de/~pdidyk/papers/2D-to-3D/2D-to-3D.pdf
> 2 votes

---
Tags: algorithms, image-processing, computer-vision, graphics
---


# Question
Title: Generate string with large Kolmogrov complexity
Given $c$, can you generate a string $s$ with $K(s) \ge c$, along with a proof of that fact?

I think the answer is no except for small $c$, but I'm not sure.

# Answer
> 7 votes
No. This is basically Chaitin's incompleteness theorem.

Roughly, the theorem says that there exists a concrete constant $C$ (which is a function of your consistent set of axioms) for which no fixed string can be proven to have Kolmogorov complexity larger than $C$. The core idea is that if you *could* do it for every string, then you can write a program of size $\log n + O(1)$ to search for and eventually output strings with complexity $n$, which is a contradiction for sufficiently large $n$.

---
Tags: kolmogorov-complexity, randomness
---


title: How to solve this graph problem

text:
# Question
Title: How to solve this graph problem
If we are given an undirected graph and we want to find if the graph can be broken down to two subsets of vertices at maximum and not more than that. The vertices in each set are such that each vertex has edge with all other vertices . A single vertex can also be a part of the subsets formed.

Example The graph edges are as follows The graph is undirected 1-2 2-3 1-3 2-4 4-5 5-6 4-6 In this graph we can make {1,2,3} ,{4,5,6}

# Answer
> 1 votes
This sounds like it would require checking all possible subsets. If so, you can solve the problem by enumerating every single subset and checking **all of them**, but that will not be practical for N \> 10 or so.

If I'm understanding correctly, it sounds very similar to the Vertex Cover problem. Which is NP-Hard.

If this for a class, that answer might suffice.

If this is for a project, you're better off finding an approximate answer, where you are certain you are correct with some degree of probability. You can use statistical optimization techniques like simulated annealing to get an answer with some reasonable degree of certainty.

It could be that I misread/misunderstand the problem though, so pardon me if so.

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


# Question
Title: What does the actual parameter A[i] refer to in this example of call by value-result?
From Programming Languages: Principles and Paradigms, by Maurizio Gabbrielli, Simone Martini

> ```
> void fiefoo (valueresult int x, valueresult int y) {
> x = x+1;
> y = 1;
> }
> ...
> int i = 1;
> int[] A = new int[5];
> A[1]=4;
> fiefoo(i,A[i]);
>
> ```
>
> we are to execute `fiefoo` with parameters passed by value-result. On termination, we will have `A[1]` with value `1` and `i` with value `2`, while the rest of the array `A` has not been touched.

Why is it `A[1]` instead of `A[2]` whose value is `1`?

My thought is that when returning from the function `fiefoo`, `x`'s value `2` is assigned to `i`, so `A[i]` is evaluated to be `A[2]`, and `y`'s value `1` is assigned to `A[i]`.

My thought is according to what the book says

> It should be clear that, as in call by value, the following questions about **evaluation order in call by return** must be answered. If there is more than one result parameter, in which order (for example, from left to right) should the corresponding “backward assignment” from the actual to formal be performed?
>
> Finally, **when is the actual parameter’s l-value determined**? It is reasonable to determine it both when the function is called and when it terminates. We can construct an example which gives different results if the l-value of the actual is determined at call time or when the procedure terminates.

Thanks.

# Answer
This example is to get readers to think about the consequences of how `A[i]` is resolved in a call by value-result setting- should it be before or after the function call to fiefoo?

The example assumes that `A[i]` is resolved before the call, and hence `i` and `A[1]` are assigned values `1` and `2` respectively. It has the nice property that `fiefoo` can only modify those variables.

On the other hand, you can imagine a programming language designer who chooses to resolve the value of `A[i]` after `fiefoo` returns, but there's two possible outcomes depending on the order in which the value-results are assigned: 1) `A[old i] = y`, `i = x`; and 2) `i = x`, `A[updated i]`. Case #2 being what you proposed.

When the designer is faced with these design decisions, she would likely opt to resolve before the call to `fiefoo` to avoid the possible ambiguity associated with resolving after the call to `fiefoo`.
> 3 votes

---
Tags: programming-languages
---


# Question
Title: Algorithm Time complexity analysis for algorithm having two different time complexities
I'm implementing an algorithm that analyze several properties on large set of integers, the time complexity is bound to $N$ (set length) and $M$ (bits to represent the numbers). I'm having some trouble to figure out how to express its time complexity because I don't know how to handle next situation:

The asymptotic analysis establish that when $N$ is constant and $M$ grows the operations count grows at constant rate ($R1$) until it reaches a threshold that depended on the value of $N$, then the operations count does not grow anymore.

On the other hand when $M$ is constant and $N$ grows the operations count grows also at constant rate ($R2$) until it reaches a threshold that depends on the value of $M$, then, it continues growing but at a slower rate.

My understanding that the algorithm has two different time complexities depending on the values of $N$ and $M$.

Is there any way to integrate this behavior in a single Big-Oh expression?

And if not possible, how will be the right way to describe the time complexity for an algorithm with these properties?

# Answer
> 1 votes
No, you can't determine the asymptotic worst-case running time from these two graphs.

First, plotting empirical running times is not a reliable way to determine worst-case running time: How to fool the plot inspection heuristic?. So, the approach of graphing performance on some testcases isn't a reliable way to get a "big-O" running time.

Second, knowing just these two graphs isn't enough to uniquely determine how it depends as a function of both $N,M$. There are multiple possibilities for functions $f(N,M)$ that are consistent with both of these graphs. For example, a two-variable function $f(N,M)$ is not uniquely determined by the one-variable functions $f(100,M)$ and $f(N,100)$.

Third, I strongly suspect that those two graphs don't tell the whole story. For instance, you show us only a single graph for when $N$ is held constant and $M$ is varied. But I suspect the shape of the graph (or the slope of the line) might depend on exactly which constant value of $N$ you choose: a very large value of $N$ might lead to a different graph than a small value of $N$. This further highlights that we don't have enough information to uniquely infer the running time.

---

So what *should* you do? Rather than plotting running times and treating the algorithm as a black box, it's probably to start by looking at the algorithm itself. Look at the pseudocode of the algorithm and analyze its worst-case running time using standard techniques. See, e.g., Is there a system behind the magic of algorithm analysis? and How to come up with the runtime of algorithms?. This allows mathematically rigorous analysis that is provably correct and that can analyze the running time for all combinations of $N,M$.

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: existence of a permutation that satisfies order-constraints
I would like to know if there is a simple algorithm for checking the existence of a permutation that satisfies a number of order-constraints.

For example, suppose we have a set (1, 2, 3, 4, 5) and a number of constraints:

* 1 should be before 2
* 2 should be before 4
* 4 should be before 1

(which is of course infeasible).

Is there a simple algorithm for checking the feasibility of order-constraints? (that does not rely on lp-solvers)?

I do not have anything against Lp-solving, but i suspect that simpler algorithms are available.

# Answer
Yes.  That task is called topological sorting.
> 5 votes

---
Tags: permutations, constraint-satisfaction, ordering
---


# Question
Title: How to prove that the complement of a regular language is always regular?
If A & B are regular languages, prove that complement of A is also regular language. (Closure of regular languages under complementation)

Can anyone help me with the proof??

# Answer
> 4 votes
If a language is indeed regular that means there is an FA that accepts it. The complement of L is just the language of all words that are not in L.

Thanks to Rick Decker for mentioning in the comments that this only works for FAs that are deterministic and to D.W for correcting the answer.

Now, a trick we can perform to test that the complement of L, namely L', is actually regular is to take the FA that accepts L and reverse all `final states to non-final states` and all `non-final states to final states`. Note that start states in the old FA become start and final states in the new FA.

This new FA will then accept all words present in L' which are words not in L.

In conclusion, take the FA accepting L and then form a new FA by:

* Changing all final states to non-final states
* Changing all non-final states to final states

The new FA accepts all words not in L, which is the language L'.

---
Tags: finite-automata
---


# Question
Title: A* algorithm how to choose $h(n)$, a heuristic estimation of the cost of node n
I'm trying to understand the A$^\*$ search algorithm. I read in wikipedia that A$^\*$ chooses nodes based on their cost, calculated as $f(n)=g(n)+h(n)$, where $h(n)$ is a heuristic estimation of the cost to reach the target from node $n$. But I don't understand how to determine its value.

Thanks for your help.

# Answer
Let's try to walk together through the $f$ function!

The intuition here is that we want to choose nodes in our exploration frontier which are:

1. Close to the start state
2. Close to a goal state

The shortest distance to the start state can be calculated recursively for every node in the search space pretty much as we do in uniform cost search.

However, the distance of a node to a goal state cannot be precisely calculated (for that we would need to know the shortest path to a goal, which would mean we have already solved the problem).

Thus the best we can do is try **estimating** it, using a heuristic function $h$. Obviously, we want this estimation to be as precise as possible, but we also want some other properties to hold:

* (**admissibility**) we want $h$ to never overestimate the cost to the goal from any given node.
* (**consistency**) we want $h(n)$ to not be greater than $h(n')+c(n,n')$ for any successor $n'$ of $n$, where $c(n,n')$ is the cost of the path that joins both states. In other words, the true cost of going from any given node to another must be less than the difference between the heuristic value of both nodes.

If we impose the restriction that $h(n)=0$ if $n$ is a goal state, then it is easy to see that consistency implies admissibility.

These properties guarantee that the algorithm is sound, complete and optimal for tree-search (admissibility) and graph-search (consistency).

Now, there are many heuristics out there for each problem.

One example is the trivial heuristic which assigns $h(n)=0$ for every $n$. This heuristic is indeed consistent. In this case, $A^\*$ behaves as uniform cost search.

We can find heuristics better suited to solve a problem. One way to do so is by relaxing the conditions to solve the problem, and calculating the exact solution of the relaxed problem from the state we are in.

For example, we can take the $n$-queens problem, where each step consists in moving one queen, and take as a heuristic the number of queens under attack minus one (or zero if no queen is under attack).
> 4 votes

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


# Question
Title: Latency vs IOPS. How can one conflict with the other?
I was reading about latency and IOPS, and I understood what they mean and their significance in the storage world. But what I do not understand (many places it is mentioned) is that how can the numbers actually conflict with each other when an example is given.

In this explanation, the author states one of the examples saying..

> Mr. Customer, our box can do a quarter million random 4K IOPS – and not from cache!”
>
> …at 50ms latency.

Here, if the latency in **50ms** then 4K IO's should take 200s. And if really 4K IO's is being completed in 1 sec, then should'nt the average latency be 4ms?

Can someone please explain what I am missing here.

# Answer
As an example, you might be able to sort requests so that they can be handled in an optimal order. That's mostly relevant for hard drive access, where the time for one access depends strongly on where the previous access was. So you don't respond to a request as quickly as possible, but you wait until you have a few request going to nearby locations on your drive, doing something else in between, and then the total time for n requests is much faster than the average time for a single request would be.

It's like the postman in the post office who first sorts his letters before he starts delivering them.

By grouping more requests together, you can handle them more efficiently, so throughput goes up, but on the other hand you wait longer until you start handling each request, so latency goes up as well. And of course you can group fewer requests together for the opposite effect.
> 0 votes

---
Tags: storage
---


# Question
Title: Show this function is partially computable
Let B(x) be a computable predicate. Show that \begin{equation} G\_B(r)= \begin{cases} 1 \\;\\;\\;\\;\\;\text{ if there are at least r numbers n such that B(k) = 1 } \\ \uparrow \\;\\;\\;\\;\\; \text{ otherwise} \end{cases} \end{equation} I want to write a program with just these four instructions to compute $G\_B$(r)

\begin{array} \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;Y \gets 0 \\ \\;\\;\\;\\;\\;\\;\\;\\;\\;\text{IF } X \neq 0 \text{ GOTO } A \\ \[E\] \\;\\;\\;\text{ GOTO } E \\ \[A\]\\;\\;\\;\\; Y \gets Y+1 \end{array}

The book gives examples for writing programs to compute $G(x\_1,x\_2)$ but does not give any when predicates are involved. Could someone give just an example for even a completely different function with predicates or just point me in the correct direction.

# Answer
Since $B$ is a computable predicate, there is one procedure that computes it. We can call this procedure in any point of our program.

```
K <- k
i <- 0
LOOP
    RESULT <- B(i)
    IF RESULT != 0 GOTO TRUE
        GOTO ELSE
        TRUE
        K<-K-1
    ELSE
    IF K != 0 GOTO KEEP_GOING
        GOTO BREAK
    KEEP_GOING
    i <- i+1
GOTO LOOP

BREAK
RETURN 1

```

You will need to substitute the instruction `K <- K-1` by an appropriate procedure.

To understand what is going on, we are looping through every natural number and checking whether it satisfies the predicate $B$, keeping a counter that diminishes every time we find one such number. So when the counter `K` reaches zero we know that the function should return `1`, and we proceed to do exactly that.
> 1 votes

---
Tags: computability, computation-models
---


# Question
Title: Proof of equality with destructuring let...in
I have some expression (`f n` in the example below) returning a tuple. I would like to prove that `f n` is equal to `let (x, y) := f n in (x, y)`, which seems like it should be easy. **What tactic should I use?**

```
Definition f (n : nat) : nat * nat :=
  match n with
    | 0 => (3, 4)
    | _ => (2, 3)
  end.
Lemma foo : forall n, f n = (let (x, y) := f n in (x, y)).
  auto. (*doesn't do anything*)
  destruct n.
  auto.
  auto.
Qed.

```

The same task with `let tup := f n in tup` can be done with the tactic `trivial`. The same task with both `f n` replaced by an explicit tuple `(f n, 12)` is also covered by `trivial`. Here I had to `destruct n` (or do a pointless `induction n`) to make the "tupleness" of `f n` be manifest.

# Answer
> 7 votes
You can `destruct` not only on variables, but on expressions like `f n` as well. So, this will get you a solution:

```
Lemma foo : forall n, f n = (let (x, y) := f n in (x, y)).
  intro n.
  now destruct (f n).    (* or destruct (f n). reflexivity. *)
Qed.

```

# Answer
> 5 votes
You could also consider a more equational proof that will avoid/encapsulate the destruction:

```
Lemma foo n : f n = (let (x, y) := f n in (x, y)).
Proof. now rewrite (surjective_pairing (f n)). Qed.

```

---
Tags: coq
---


# Question
Title: k-Closest pairs in Delaunay triangulation
Assume there is a set of points $S$ in $\mathbb{R^2}$. In this set of points there is a pair of points which are the nearest neighbors, the second-nearest neighbors and the third-nearest neighbors.

I want to show that the pair of points which represent:

1. the nearest neighbors,
2. the second nearest neighbors,
3. the third nearest neigbors

are also an edge in the corresponding Delaunay Triangulation.

Any hints on how to prove this?

# Answer
> 4 votes
This article \[1\] shows that this is not always true for the second-nearest neighbour and forth. It shows that it is indeed the case for the (1st) nearest neighbour, and it's trivial, given the theorem that claims that if the circle defined by 2 points (as its diameter) is empty of other points then these points lie on an edge of the delaunay triangulation.

I didn't find a proper proof for that, and it is definitely not true for the opposite direction (not every edge of the DT defines an empty circle), but I have an idea of why this is true -

Let the points a,b define a circle Cab, having a-b as its diameter, empty of other points. The circle is empty of points, but cannot be empty of edges (the line connecting **any** pair of points must either be an edge or intersect an edge (by convexity of the map, and the fact that there are no diagonals in triangles). Suppose a-b is not an edge of the DT, then it intersects an edge c-d, with both c and d out of Cab, that is part of a triangle c-d-e that either has w.l.o.g e=a, or e != a and is also outside of Cab, but this doesn't matter. Anyway, the angles $\angle acb$ and $\angle adb$ have to be both sharp, as they are supported by the diameter of Cab, a-b, and lie outside of it, so this means $\angle cad + \angle cbd \> 180^{\circ}$ (sum of angles in tetragon is 360), but as c-d is a chord in Ccde, so this means that at least one of the points a,b lies in Ccde, so c-d-e is not a legal delaunay triangle - contradiction.

Hope this hand waving is sufficient for your understanding.

1. All closest neighbors are proper Delaunay edges generalized, and its application to parallel algorithms by Arne Maus and Jon Moen Drange (2010)

---
Tags: computational-geometry
---


# Question
Title: How do I approach inductive design problems with no information or context given?
As a starting point for our course in Artificial Intelligence, we are being taught induction. We received a number of homework assignments where we have to show our inductive approach for a given problem.

An example of such a problem: "Sort an array of N numbers".

Reading through the course material and online sources I feel I have grasped the first concepts of induction. I have successfully proven some statements using induction, such as the number of steps for the Tower of Hanoi problem. However, I was able to prove it because I had some information beforehand, such as the number of steps required to move the tower in the form of a formula.

In the problems handed to us, we get a sentence like the one above and are asked: "Describe the inductive approach"

Should I select an arbitrary sorting algorithm, make my own assumptions and devise my own hypothesis and try to prove that? I just want to prove that the array is indeed sorted for any given number of N. What are some exemplary steps I could take in order to provide the inductive approach *given* that single sentence of "Sort an array of N elements"

# Answer
> 3 votes
It seems to me that your teacher wants a induction proof where the induction is on the length of the array. It seems weird that your teacher does not provide a sorting algorithm .

If the task is to sort an array, I would assume that your teacher is looking for an, as you say, arbitrary sorting algorithm and prove it with that.

But if the teacher means that you should check if an array is sorted, it is of course way simpler to show for different sizes of the array.

Either way it sounds like your teacher wants you to identify a base case and show that the induction holds (array is sorted) for $n$ given that it's sorted for an array size of $n-1$

With more details, or the full problem one might be able to draw more conclusions.

# Answer
> 2 votes
Most questions in AI textbooks of this style are intended to be open ended so that the student can experiment on its own with the problem. So the golden rule is do as you see fit to provide the best learning!

In particular for this problem, your approach seems appropriate.

Since most sorting algorithms fall into a divide and conquer schema, you won't have problem fitting it into an inductive schema.

For example, you could take quicksort, which is usually implemented recursively. And then prove that it indeed sorts an array of size $n$ assuming that it sorts an array of size less than $n$.

---
Tags: sorting, induction, towers-of-hanoi
---


title: Computing composite functions

text:
# Question
Title: Computing composite functions
This may not be strictly a computer science question but is related.

Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? Or is computing in composite/series a required limitation of the brain?

For instance, to add three numbers, we add two and then and the third to the result of the first addition. Is it possible for the brain to take all three numbers and process them at once with no intermediate step? Is it possible for machines? Is it possible with quantum computing?

In the case of the brain's inability to make this computation, is it because we are trained to compute in a certain way or is it an inherent limitation?

# Answer
Definitely possible for a computer, since three-input logic gates exist. Possible for humans too, at least as far as conscious operations are concerned. If you show me a partition of 13 into no more than 4 parts (e.g. 5+3+4+1), I can recognize it without any intermediate calculation simply from long experience playing bridge.
> 3 votes

# Answer
> Whenever there is some function that computes more than two elements, is it possible that all elements are computed at once? \[...\] For instance, to add three numbers, we add two and then and the third to the result of the first addition.

If your question is, "*is it possible to add numbers in parallel?*" then the answer is *yes*, since addition is associative. I.e., the serial approach would be *(a+(b+(c+...)))*, and one parallel approach could be *(a+b)+(c+d)*, in which *a+b* and *c+d* can be computed independently before being added together.

If your question is, "*can I add three numbers in such a way that I begin operating on the third number before I'm done operating on the first two?*" then the answer is *yes*, since addition typically works from the least towards the most significant digit. Once the least significant digits of the first two numbers have been added, and the result has been carried, the least significant digit of the third number can be added, and the result likewise carried.

Different *hardware adders* add numbers differently. For example, carry-save adders accumulate the carries instead of applying them from digit to digit.

> Or is computing in composite/series a required limitation of the brain? \[...\] Is it possible for the brain to take all three numbers and process them at once with no intermediate step? Is it possible for machines? Is it possible with quantum computing?

I'm not sure if your question really relates to adding numbers, inherent properties of computation, or analogies between modern-day computers and human brains. I'm also not sure what you mean by "no intermediate step". Are you?

The brain is indeed a parallel processor. Unfortunately, you have reached the wrong forum for such a question, although I can tell you that slapping "quantum" onto an ill-understood problem does not make it more solvable, so don't do that. ;-) See for example the question/answer Difference between parallel processing done by human brain and by computers on the Cognitive Sciences Stack Exchange.

> In the case of the brain's inability to make this computation, is it because we are trained to compute in a certain way or is it an inherent limitation?

We do compute in certain ways, in part because of training. I don't know if anyone has ever practiced adding numbers in parallel, but I imagine one approach would be visual/geometric, like this trick for multiplying:

https://www.youtube.com/watch?v=0SZw8jpfAk0
> 1 votes

# Answer
I think this is partly a matter of definition: what sorts of processes are we willing to *call* "a computation"?

Let's suppose we're charged with the task to compute, given any natural number $n$, the $n$th Fibonacci number. It is defined as follows: if $F(n)$ stands for the $n$th Fibonacci number, then $F(1) = F(2) = 1$ and $F(n) = F(n-1) + F(n-2)$ for all $n \> 2$.

We could actually define it that way in most programming languages. For instance, in C:

```
int fibonacci(int n)
{
    if (i < 2)
    {
       return 1;
    }
    else
    {
       return fibonacci(n-1) + fibonacci(n-2);
    }
 }

```

This is a valid (and inefficient) way to compute Fibonacci numbers in C.

But does it define a *computation* to compute the $n$th Fibonacci number? You tell me.

In C, the order of evaluation of arguments of `+` is undefined. One implementation may always evaluate the left operand first, then the right. Another may choose an evaluation order depending on the weather. Yet another may evaluate them in parallel (I do believe this is valid). C programs mostly run in multiprocessing environments, so a parallel implementation could actually be implemented most of the time.

Let's suppose you use such a parallel implementation. It is certainly a way to compute the $n$th Fibonacci number. But is it "a computation"? I'm not sure. I think for most of us, a computation is a stepwise process, executed by a single processor strictly sequentially, one step at a time. Not because computation must be done that way (that isn't the case) but because we don't call the process "a computation" otherwise.

Modern computers and the human brain don't quite work strictly sequentially. It's our conception of computation, an abstraction of what really happens, that does. We say a computer or a human brain performs computation when it does something that is equivalent to what that abstraction does - even when how it actually does it deviates from that.

This is part of why the human brain finds it difficult to come to terms with inherently concurrent or parallel computational processes. We're trained to think of computation as a strictly sequential single-processor process.

If you want to meet a different perspective on computation, familiarize yourself with dataflow processing, e.g. Unix pipes, or typical setups for signal processing, such as audio and video processing. What those systems do is computation, and it is a pretty mainstream way of using computers, but it is not adequately described by Turing machines.
> 1 votes

---
Tags: computation-models, arithmetic
---


title: CFG for $L=\{w_1cw_2:w_1\neq w_2^{R}\}$

text:
# Question
Title: CFG for $L=\{w_1cw_2:w_1\neq w_2^{R}\}$
I am trying to construct a context-free grammar for the following language: $$L=\\{w\_1cw\_2:w\_1\neq w\_2^{R}\\},$$ where words are over $\\{a,b,c\\}$.

I have tried to do this by taking the union of two sub-languages:

1. The length of $w\_1$ is not equal to the length of $w\_2$.
2. The lengths are equal.

For 1, I've already written the grammar. But I'm having difficulty with 2. In terms of a PDA I think non-determinism can solve this. However, what is the CFG for 2? If I can find it, I will union 1 and 2 to get the final solution.

# Answer
> 1 votes
Here's a hint for part (2): work from the inside out. A string of the form $w\_1cw\_2$ where $|w\_1|=|w\_2|$ is "matched" ($w\_1=w\_2^R$) if and only if it is of the form

* $c$, or
* (any character $x$) ("matched" string) (character $x$)

Similarly, such a string is "unmatched" if and only it is of the form

* (any character) ("unmatched" string) (any character), or
* (any character $x$) ("matched" string) (any character $y\ne x$)

Thus, we can make a grammar where the "matched" strings are generated by $$ M\rightarrow c\mid aMa\mid bMb\mid cMc $$ We can make the "unmatched" strings ($w\_1\ne w\_2$) generated by similar productions, which I'll let you do, using the variable $U$. Finally, you want to generate "unmatched" strings, so $U$ will be the start variable for your grammar.

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


title: delaunay sweep circle initialization

text:
# Question
Title: delaunay sweep circle initialization
I recently came accross an interesting "sweep circle" algorithm for delaunay triangulation \[1\].

It's basic idea is seeding with a trivial triangulation (3 points), then gradually extending it outwards (points are sorted by their distance from a chosen origin - the sweep-circle center) while preserving the legality of the triangulation by flipping triangles if needed, always starting from the new one, and continueing to neighbouring triangles of flipped ones.

I've implemented it, and it works nicely, but I still struggle with making the seeding part flawless.

The thing is :

* In order to ensure that each new point is outside of the current envelope ("frontier" in the article), you have to make sure that the swept points are closer to the origin than the unswept points.
* In order to find where to connect the new point, you have to have the origin inside the envelope (so angular sort of the envelope and binary search will do).

Starting at some iteration this will natuarally happen, but the problem is making it happen for the seed points.

So what I aim at is finding an origin which fulfills :

* Be inside the seed triangulation.
* Have the seed points the closest points to it (have the sweep circle strictly containing the seed points empty of other points).

The article suggests taking some average point as the origin, and start with the 3 points closest to it, but this clearly fails if these 3 points are on the same side of the chosen origin, so they form a triangle that is not containing it.

A different but somewhat similar algorithm \[2\] is suggesting choosing an arbitrary point, then taking the point closest to it, and the point that creates the smallest circumcircle with the other two, and fix the origin as the center of their circumcircle, but that's clearly not working either, unless these 3 points happen to form an acute triangle (is this circle even ensured to be empty of other points?).

Currently I use a similar idea - arbitrary point + 2 closest points to it, as the first 3 points, but I fix the origin as some point inside the formed triangle (e.g their average), which basically works, but can fail in principal.

I'm looking for another simple way to do it, or a way to detect when the proposed method is not working and fix it in a clever way involving the point that "ruined it", before the iterations begin and without having to deal with more than 2 seed triangles (4 points), or having to make many iterations or guesses at init stage.

I know I can take the first point and shift it by some small $\epsilon$ towards inside the triangle, and it should work, as long as it's smaller than say the minimum distance bewteen 2 points, but I'm looking for a clever solution, and I am especially interested in a solution that can chose an integer origin for a set of integer points, for then the whole algorithm can be implemented using only integral arithmetics (faster, less error prone).

**Bottom line :**

I think it all comes down to this :

Given a set of n points in the plane, find a point O which lies strictly inside the triangle formed by the 3 points of the set closest to it (to O).

But I guess that put in the context, there might be solutions to implementing a working version of the algorithm that bypass this question.

**References :**

1. A faster circle-sweep Delaunay triangulation algorithm by Ahmad Biniaz and Gholamhossein Dastghaibyfard (2011)
2. S-hull: a fast radial sweep-hull routine for Delaunay triangulation by D. A. Sinclair (2016)

# Answer
> 1 votes
I just realized that my question is irrelevant to making the algorithm work. I mixed the radial and angular atributes of the points and mistakably thought them to need to be based at the same origin, but that's just confusing semantics. Actually, the radial origin decides on the order of insertion of points and if set correctly, ensures no new point will apear inside an existing triangle, and the angular origin only helps to find the projection of a new point on the envelope (frontier / convex-hull in the case of \[2\]), so the angular origin indeed needs to be inside the seed envelope, but the radial origin need not. Moving the angular-origin inside the seed envelope will affect the actual progression of the algorithm, but will not affect correctness.

This makes things a lot easier - taking arbitrary point of the set, or somewhere in the plane and find the 2/3 points closest to it will work in general position, but it may result in a colinear triplet. Following \[2\] and taking a point from the set, its nearest neighbour, and a 3rd point that creates the smallest circumcircle with them will always work as this is a delaunay triangle (nearest-neighbours are always delaunay edges, and the 2 triangles based on this edge have to create an empty circumcircle, so one of them has to be the smallest) which makes the circumcircle empty of other points, so using its origin as the radial origin is correct.

To do this for integers, we may take the second approach and round the result (checking for super-edge-cases), or take the first approach which is more straight forward for integer radial origin, and restart if we find a colinear triplet, or when the triangle is too obtuse to contain an integer point in its interior. The last condition is only for making the algorithm fully integral (e.g for machines wihout Floating Point Arithmetics), but using precalculated float pseudo-angles \[3\] (avoiding use of slow atan2) and comparing them later in the binary search (tree), might be faster than using fully integral orientation test by demand.

3. pseudo-angles

---
Tags: computational-geometry
---


# Question
Title: Relationship between Coloring a graph and its complement
Let $G = (V, E)$ be a graph and $G^\*$ its edge complement (that is, $G^\* = (V, E^\*)$, where an edge $\\{u, v\\} \in E^\* \Leftrightarrow \\{u, v\\} \not \in E$).

What is the relationship between a coloring in $G$ and a coloring in $G^\*$ ?

I was expecting something like

"If $G$ accepts a $k$-coloring, than $G^\*$ accepts a $(n - k)$-coloring"

but I can't prove that.

(Of course, I am dealing with *proper* coloring)

# Answer
Sorry, this is false:

For example, take $G$ as a size-$10$ independent set. It has a $1$-coloring, or even a $3$-coloring... its complement is a clique, which admits neither a $9$- nor $7$-coloring.
> 2 votes

---
Tags: graphs, colorings
---


# Question
Title: How big is the class of problems that can be analysed to halt with static analysis. Is this class sufficient for any practical purposes?
When the halting problem is discussed, often the counterproof consists of some unsolved mathematical problem or a self-reference.

Is the halting problem decidable for pure programs on an ideal computer?

Is this of any relevance for most programms not even remotely dealing with complex math ? I often hear that performing static analysis on any program is useless, because "Halting-problem". I find this argument weak, to make a statement from a few theoretical counter examples to say that static analysis on any programm is useless.

And what about a modified version of the halting problem?

What about outputting those 3 possibilities:

Halts. Does not halt. Unknown.

Doesn't this simplify the halting problem enough to make a statement about any program in finite time ?

# Answer
When you hear about "static analysis" in the context of programming languages, you will often have the three results "passes the test", "doesn't pass the test", "is rejected". In that context, the analysis is supposed to help the software developer. If the developer writes code that is too hard to analyse, that's the developer's problem because he isn't going to get the answer he wants.

As an example, the Java language insists that a variable must be assigned a value before it is accessed. Testing that in general would require solving the halting problem. However, the Java language defines a precise method how it would go about verifying this property, and if your program cannot be analysed by this method, then it is rejected. No attempt at solving the halting problem is made.
> 4 votes

---
Tags: halting-problem
---


# Question
Title: Is the language of TMs that accept finite languages in $\mathbf{0}'$?
In this question it is asked, "Is the language of TMs that accept finite languages Turing-recognizable?". It turns out this language $L=\\{ \langle M \rangle \mid |L(M)| \< \infty \\}$ is not. I ask this: We know that the halting problem is Turing-reducible to $L$ but is $L$ Turing-reducible to the halting problem?

# Answer
> 3 votes
Your language $L$ is usually known as Fin or FIN, and is $\Sigma\_2$-complete; see for example lecture notes of Cohen Wallace. Since the halting problem is in $\Sigma\_1$, it follows that $L$ cannot be reduced to the halting problem.

---
Tags: formal-languages, computability, turing-machines, undecidability
---


# Question
Title: Proving complexity by reduction using strongly NP-hard problem
I have a decision problem $X$ of which I think I can show its complexity by using a reduction from a problem $Y$ that has been shown to be strongly NP-hard.

I tried to follow the same procedure as for proving NP-completeness which I try to summarize here:

1. Show that problem $X$ is in NP (polynomial time verifiable)
2. Make the Karp reduction from a known NP-complete problem by finding a poly-time algorithm that transforms the instances $y$ of $Y$ to instances $x$ of $X$
3. Show correctness of algorithm: Show that for every *yes/no* answer to an instance of $Y$, the *algorithm* also returns *yes/no*

The problem I'm currently facing concern point 1 and 2:

* I'm sure that $X$ is in NP, but $Y$ is not necessarily, right? Is it a problem when I try to reduce an NP-hard problem to an NP-complete one?
* The strongly NP-hard problem $Y$ is not necessarily NP-complete, right? Can I still use $Y$ here?

Another open question regards the fact that $Y$ is *strongly* NP-hard:

* Assuming that I can do the reduction as outlined above, is then $X$ also strongly NP-complete?

# Answer
> 2 votes
I will assume that your definition is the one on Wikipedia.

We wish to prove that $X$ is strongly NP-Complete. Here's how you do that. First, show that $X$ is strongly NP$^1$. Next, find a strongly NP-Complete problem $Y$ and reduce $Y$ to $X$. That is, provide an algorithm which takes an instance $y$ of $Y$ and produces $f(y)$ such that if $y\in Y$ then $f(y)\in X$ and otherwise, if $y\not\in Y$ then $f(y)\not\in X$.

I remember in which way to reduce a problem (was it $X$ to $Y$ or $Y$ to $X$?) by framing it as a conversation which I've laid out here in this other answer(link): someone challenges me by saying $X$ is easy. Then I say, nonsense, if $X$ were easy, then I could solve very hard problem $Y$. And then I show how to do that: I take an instance of $Y$, rewrite it into an instance of $X$, and then you're done. You've shown that $X$ is at least as hard as $Y$, so we write $Y\leq X$.

$^1$ best I can figure, strongly NP means it has logarithmically-sized certificates

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


# Question
Title: Does the closure of a function include the actual parameter passed to the function?
A closure of a function includes the environment when calling the function.

Does the environment included in a closure of a function include the actual parameters for the function?

If I am correct, from mathematical logic point of view, a closure for an expression consists of the free variables of the expression. So I guess the answer to the question is no.

# Answer
No. A closure is a function, and, as such, its parameters are passed when the function is called. The main difference between *closures* and *plain functions* is that closures are associated with an environment. This environment stores the values of the free variables\* that were in scope when the function was created.

* The term *free variable* refers to those variables which are used locally within a function but are defined outside of this function (i.e., in an enclosing scope).
> 5 votes

---
Tags: programming-languages, functional-programming, semantics
---