# Question
Title: Is queue a storage allocation area in memory?
We mainly study about heap and stack data structures which act as storage allocation area in memory. Is it that queue is also a storage allocation area in memory? As far as I know, process control blocks are made in OS region and actually they also act as storage allocation area only so can I consider queue to be a storage allocation area in memory?

# Answer
You've been misled by homonyms.

There is a data structure called *stack*: a container where items can be added at any time but only the most recently added can be removed. And there is an area in memory called *stack*, which is where function arguments, local variables, return values and return addresses are stored¹. There's one stack memory area per thread. The two concepts have the same name because the stack memory area is organized as a stack data structure: an item is added when a function call is executed, and it is removed upon return from a function; since function calls are nested, the item that's removed is the last one that was added and not yet removed.

There is a data structure called *heap*: a tree of ordered items where each node holds a smaller value than all of its children². And there is an area in memory called *heap*, which is where storage is allocated dynamically. There is one heap per process. The two concepts are completely unrelated, they have the same name because there's a finite supply of English words with roughly the right connotations and it happens that the same word was picked for both.

There is no reason why a word that is a name for a data structure should also be a name for an area in memory. There can be queue data structures in an operating system, of course, but there's no area in memory that's called “the queue”.

Process control blocks are not organized as a queue, and they are not a storage allocation area, they're just a common name for the place in memory where the operating system stores information about each process (and not every operating system has all the information in one place, so not every OS's description mentions a “process control block”).

¹ <sub> This is just the 10000-foot view. Return addresses and arguments could be placed in different areas, some arguments typically end up in registers, etc. </sub>
² <sub> That's a min-heap; a max-heap is a tree where each node holds a larger value than all of its children. </sub>
> 4 votes

# Answer
it seems that you haven't studied computer architecture yet. I'll try to explain. You can't in OS use queue to be a storage location in memory because the heap and stack is implented in the hardware. To use queue as a storage area you'll need do your own hardwares. To know how the heap work see: http://gribblelab.org/CBootcamp/7\_Memory\_Stack\_vs\_Heap.html.
> -1 votes

---
Tags: data-structures, operating-systems
---


# Question
Title: Do Karnaugh maps yield the simplest solution possible?
I'm learning to use a Karnaugh map, but I'm not sure if I obtained the simplest expression possible. Have a look at this example:

Truth table (inputs are A B C; output is F):

```
A   B   C   |   F
0   0   0   |   1
0   0   1   |   0
0   1   0   |   1
1   0   0   |   0
0   1   1   |   1
1   0   1   |   1
1   1   0   |   0
1   1   1   |   1

```

The Karnaugh map looks like this:

```
AB
--
C|

    00  01  11  10
    --------------
0|  (1  1)  0   (1)
1|  0   (1  1)  (1)

```

And this yields $\bar{C}\bar{A}+CB+A\bar{B}$. Is there any simpler way of choosing the 1s from the map and getting a simpler result? Are Karnaugh maps guaranteed to always yield the simplest result possible?

# Answer
The only other way to group the 1's into pairs would be to group the ones in indices 0,2/1,5/and 6,7. All of these are groups of two, like your original solution, and no 1 is left on it's own. This solution would give you a result of equal simplicity. No, this is the minimum representation.

If it were not the minimum representation, you would see terms that differ by only one term in the disjunctive normal form.
> 1 votes

# Answer
Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://web.archive.org/web/20190920201621/https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html).
> 5 votes

---
Tags: logic, boolean-algebra, digital-circuits, karnaugh-map
---


# Question
Title: Counting words that satisfy SAT-like constraints with BDDs
I have the following #P-complete problem:

Given an alphabet $\Sigma$ and a matrix $M$ where each entry can be a symbol from $\Sigma$ or the wildcard symbol $\*$, find the number of strings $s$ with the property that there exists $i$ such that for all $j$, $M\_{i,j} \neq \*$ implies $s\_j = M\_{i,j}$.

**Example:** If $\Sigma = \\{a,b,c\\}$ and $M$ = $$\left(\begin{matrix} a&\*&b \\ \*&c&\* \end{matrix} \right)$$ then there are three satisfying strings: $aab,abb,acb$.

I was told this can be solved using BDDs, somehow, such that a lot of caching is possible. How does that work? Also, what are other algorithms for this?

**Proof of #P-completeness:** We reduce from #UNSAT, the problem of counting the number of unsatisfying assignments for a boolean formula. Given a formula $\varphi$ with $n$ variables and $m$ clauses, make an $m$ by $n$ matrix $M$ over the alphabet $\Sigma = \\{0,1\\}$ such that $$M\_{i,j} = \begin{cases} 1\text{ if the $j^{th}$ literal is unnegated in the $i^{th}$ clause,} \\ 0\text{ if the $j^{th}$ literal is negated in the $i^{th}$ clause,} \\ \*\text{ otherwise.} \end{cases} $$ Then the number of strings with the above property equals the number of unsatisfying assignments for $\varphi$.

# Answer
Yes, you can use a BDD to solve this, but BDD's aren't magic: they don't magically allow you to solve a #P-complete problem efficiently. You can use BDD's to solve this, but the resulting solution might be highly inefficient.

How do you use BDD's to solve this? Broadly, you build a BDD that represents all strings that satisfy the property, and then you count how many strings are accepted by this BDD.

To learn how to build a BDD that accepts all strings that satisfy the property, I suggest that you study basic material on BDDs. The key property that's relevant here is that given BDDs for the sets $S,S'$, it is easy to construct a BDD for the set $S \cup S'$. So, you build a BDD for the set of strings that are accepted by each row of the matrix, and then you take their union to get a BDD for the union. Beware that the resulting BDD could have exponential size.

Once you have a BDD, it's easy to count the number of strings accepted by a BDD. It's an especially simple application of dynamic programming: for each node $n$ in the BDD, you count the number of paths from $n$ to some leaf. These numbers can be filled in by visiting the nodes in bottom-up order, and using dynamic programming.

There's nothing fancy here. Once you are familiar with BDD's, everything here should look bog-standard. So, if this looks mysterious, I recommend you spend some quality time with a textbook that explains how BDD's work.

---

Other algorithms: you could also use any algorithm for #SAT. There are off-the-shelf algorithms and tools for computing #SAT. It's straightforward to translate your problem to an instance of #SAT, and then apply one of those tools. See, e.g., https://cstheory.stackexchange.com/q/1295/5038, Is there a sometimes-efficient algorithm to solve #SAT?, https://cstheory.stackexchange.com/q/18135/5038.
> 1 votes

---
Tags: algorithms, combinatorics, counting, bdd
---


# Question
Title: Is < binary relation a strict partial order on IEEE doubles?
To me it looks that it is:

* irreflexivity: NaN \< NaN == false
* transitivity: if a \< b and b \< c then a \< c (the antecedent is never true for NaNs)
* asymmetry: if a \< b then not b \< a (again, the antecedent is never true for NaNs)

However, it cannot be extended to non-strict partial ordering \<= because there's no (reflexive) equality for doubles (NaN != NaN).

# Answer
Yes, it is. (Though you need to consider signed zero as well as NaNs.) For extra confirmation:

> > So, the floating-point operator\< does not form weak order and therefore does not form a total order. It is, however, a partial order.
>
> However, it cannot be extended to non-strict partial ordering \<= because there's no (reflexive) equality for doubles (NaN != NaN).

It *can* be extended, but `<=` as defined by IEEE isn't that extension.
> 4 votes

---
Tags: floating-point, partial-order
---


# Question
Title: Can we enumerate provably non-terminating functions?
In trying to understand the Halting Problem better, I am trying to come up with classes of provably non-terminating programs.

For example, any program (including input) which leads to a finite-length infinite loop (with perfectly repeating state+tape) should be detectable. That leaves mostly induction/search problems like "get the first non-Goldbach even number above 4" as candidates.

Clearly, some of these halt, and some can be proven non-halting (eg we know "find $n$ such that $n\cdot 0=5$ " and "find a proof that the Poincare Conjecture is false" would not halt). More generally, it seems every non-halting problem corresponds to a Diophantine equation which (provably or not) has no solutions. This leads to a seemingly fairly general algorithm to find many non-halting programs:

1. Convert Turing machine to corresponding Diophantine equation with one unknown
2. Feed the equation, along with First-Order Peano Arithmetic, to Prolog/Isabelle/your favorite proof assistant
3. Assert the existence of a solution
4. Derive 0=1

So, my questions:

* Is there a more natural way to search for such contradictions using the formalism of Turing Machines (or some other more conventional model of computation), without converting to Diophantine equations?
* Are there *provably* non-terminating functions that can be found using some other algorithm, but not this one? What algorithm(s)? Would that require a "stronger" version of arithmetic?
* If there are such algorithms, is there any notion of a "biggest" class of provably non-halting programs, or would that somehow lead to solving the Halting Problem (or some other contradiction)?
* Are there any good references/keywords for this? I've searched for "provably non-terminating functions", but haven't come up with much

PS Feel free to fix/reformat anything, alert me to obvious theoretical mistakes, or let me know if this is a bad question.

EDIT: Some points to address responses so far:

* I know that it's "easy" to prove that a program halts--just run it until it does; the challenge is to prove that a program does not halt, which obviously isn't always possible.
* Re: D.W.♦, I know we can't enumerate all non-halting programs, and I know we can come up with many provable examples of non-terminating functions, I'm asking if there's a *most general* method of finding all non-halting programs that *can be* found/proven
* I am aware of the Curry-Howard correspondance that directly relates programs and mathematical proofs. However, because of the halting problem there can be no type for "non-terminating programs", and it's not immediately obvious how to type "provably non-terminating" either
* @chi's answer is exactly what I am looking for. To make sure I understand fully, let me restate my understanding of your enumeration of non-terminating programs, using the simplest possible axioms I can think of:

1. Start with a basic definition of "strings" in pure First-Order Logic: 0,1,add0,add1,equality
    2. Define Turing machines using a rewrite relation on strings that captures the mechanics of a calculation step (ie, eval)
    3. Define big-step calculation $\rightarrow$ as the transitive closure of one-step eval
    4. Define a halting predicate as the existence of a fixed point
    5. For a given program $x$, prove $\forall y.x\rightarrow y\Rightarrow \exists z\ne y.y\rightarrow z$

So, would the above work? Is it equivalent to my Diophantine equation scheme? Is there a yet simpler version? Would more axioms (eg using naturals under Peano Arithmetic to encode the machines) be able to prove more non-terminating programs than this version, ie is there a more general method?

# Answer
> Is there a more natural way to search for such contradictions using the formalism of Turing Machines (or some other more conventional model of computation), without converting to Diophantine equations?

You do not need this conversion. One can directly formalize what a Turing machine is in Coq/Isabelle/... and directly define its semantics there.

That is, it is possible to define a function `eval (tm: TuringMachine) (input: nat) (steps: nat)` which returns the Turing machine configuration (state & tape) obtained by running `tm` with an initial tape carrying the `input` for that many `steps`. From this, defining non-termination is simple.

Note, however, that enumerating non-terminating Turing machines in this way will generate the same set of machines as if you converted to Diophantine equations. Indeed, if you can prove the soundness and completeness of the conversion in your proof system, then a direct proof of non-termination exists iff a proof for no-solution in the Diophantine system exists. This is because the conversion theorem allows to transform one proof into the other.
> 2 votes

# Answer
Here is a simple non-terminating function:

```
while (true):
    do nothing

```

This certainly does not terminate.

On the other hand, it is not possible to enumerate all non-terminating functions. The halting problem is recursively enumerable but not decidable, from which it follows that the complement of the halting problem is not recursively enumerable (if it were, the halting problem would be decidable). See https://en.wikipedia.org/wiki/Recursively\_enumerable\_language and https://en.wikipedia.org/wiki/RE\_%28complexity%29.
> 3 votes

---
Tags: halting-problem, correctness-proof
---


# Question
Title: 2 approximation algorithm for the single machine scheduling problem
We are given one machine and $n$ jobs that we want to process.

For the $n$ jobs we have the following data:

$r\_{1}, ... , r\_{n}$ are the release times

$p\_{1}, ... , p\_{n}$ are the processing times

$d\_{1}, ... , d\_{n}$ are the deadlines/due dates

$c\_{1}, ... , c\_{n}$ are the completion times(when the jobs are finished executing)

$l\_{1}, ... , l\_{n}$ are the latenesses achieved where $l\_{j} = c\_{j} - d\_{j}$

Our goal is to find a schedule that minimizes the maximum lateness achieved ($L^{\*}\_{max}$)

Since even deciding whether there is a schedule such that $L^{\*}\_{max} \leq 0$ is np hard, this implies that we can not come up with an approximation algorithm of any ratio $\rho \> 0$ that runs in polynomial time and produces a schedule with maximum lateness at most $\rho L^{\*}\_{max}$. So this is why we make the assumption that the due dates are negative, ie $d\_{i} \< 0$

Before trying to come up with an algorithm, we can prove that for any subset $S$ of jobs, $L^{\*}\_{max} \geq r(S) + p(S) - d(S)$ where $r(S) = min\_{j\in S}r\_{j}$, $p(S) = \sum\_{j\in S}p\_{j}$ and $d(S) = max\_{j \in S} d\_{j}$.

To prove this what we have to do is look at the last job of the optimal schedule and try to find its lateness, which will also be a lower bound for the maximum lateness achieved.

Now, having this as a fact for any schedule, assume our algorithm produces a schedule as follows. At each moment the machine is idle, start processing next the available job with the earliest due date.

The analysis I have in my book (the design and analysis of algorithms by Williamson and Shmoys) is as follows:

We consider the schedule produced by our algorithm and let $j$ be the job of maximum lateness in the schedule. That is $L\_{max} = c\_{j} - d\_{j}$. We focus on the time $c\_{j}$ in this schedule and try to find the earliest point in time $t \leq c\_{j}$ such that the machine was processing without any idle time for the entire period $\[t, c\_{j})$. By our choice of $t$, we have $r(S)=t$. Let $S$ be the set of jobs that are processed in that interval. From the bound about the maximum lateness we found before, we have that $L^{\*}\_{max} \geq r(S) + p(S) -d(S) \geq r(S) + p(S) = t+p(S) = c\_{j}$

Then we only focus at the last job $j$, so we get $L^{\*}\_{max} \geq r\_{j} + p\_{j} - d\_{j} \geq -d\_{j}$

combining both the equations we get $c\_{j} - d\_{j} \leq 2L^{\*}\_{max}$

what I don't understand is, where do we actually need the earliest due time rule? Where do we use it in the analysis? What would happen if we used the longest due time rule? Could we then apply the same analysis to come up with the same approximation ratio?

# Answer
This is an error in the book. The earliest deadline condition is not used any where in the analysis. This means that we can achieve the 2-approximation algorithm even if we drop this condition.
> 0 votes

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


title: Will encoding affect computability?

text:
# Question
Title: Will encoding affect computability?
I think this question arises from not having a clear idea on encoding. So, If I have a problem intuitively there may be many ways of encoding it using TM's alphabet set. Slight variation in the encoding may(intuitively) not affect the computability of the problem, Is it true? Can I have a computable problem which on changing the encoding turns uncomputable?For eg given a graph and two vertices, the problem is whether there is path between them. We know this is compuatable. But if we consider encoding as just a mapping, then If I have encoding such that set of all instance of the problem with the answer as yes mapped to some undecidable language(bijectively)?Is it possible?

# Answer
> 7 votes
As long as there's a computable mapping between the two encodings, changing from one to the other won't affect computability, since computable functions compose. If there isn't a computable mapping between the encodings, you can't effectively use at least one of them, since there's no way to figure out what the encoding of your input should be in that scheme. (For example, suppose you come up with a coding of graphs that isn't computably translatable from the adjacency matrix. How would you use that encoding? If I give you a graph, you can't figure out what string encodes it.)

# Answer
> 2 votes
A TM is not the sole means of implementing an 'Effective procedure' while the ones it does carry out are constrained to accept input only as strings of symbols over some finite alphabet.

But it is widely believed that every effectively calculable function...i.e one calculated through an effective procedure can also be carried out through a TM.(Church -Turing thesis)

In view of above the entire process of assigning a unique string to an object of input space...and its further manipulation to reach a decision...is one single 'effective procedure'...if at all one exists:part of which is carried out by a TM.

And if the problem is not decidable then no such procedure exists.

Hence the decidability status of the problem is inherent to the problem itself...

And if an effective procedure does produce a string having one to one correspondence with the problem...then a TM can decide it (if the problem is decidable through an effective procedure)...irrespective of the encoding.

---
Tags: computability, undecidability, decision-problem
---


# Question
Title: How many recursive calls does it take to compute binomial probability weights?
I was given an algorithm and I was asked to estimate how often it would be called if I was trying to calculate ${100 \choose 50}0,25^{50}0.75^{50}$, the Binomial distribution of $50$ elements chosen within $100$ elements with $0.25$ their probability to appear.

This is the method:

```
binomial1(int N, int k, double p) {
    if (N == 0 && k == 0) return 1.0;
    if (N < 0 || k < 0) return 0.0;

    return (1.0 - p) * binomial1(N-1, k, p)
         + p * binomial1(N-1, k-1, p);
}

```

The question is, how many calls to `binomial1` would be required to evaluate `binomial1(100, 50, 0.25)`?

I tried first the fool strategy to implements a `system.out.println` within the code with an indice increasing each time the algorithm was called. But I realised that it was something fool when I noticed I reached:

```
passed 2485266 times

```

Thus I was wondering that as far that the algorithm is called twice every time it is called, I was wondering if it was simply called $2^{100}$ times? Yet, `p*binomial1(N-1, k-1, p)` seemed to be called only $50$ times with a parameter $k=50$...

I'm only asking for a hint.

# Answer
If we let $T(n,k)$ represent the number of times that `binomial1` is called when computing `binomial1(n, k, p)` we'll have $T(n,k) = T(n-1, k) + T(n-1, k-1)+1$ and $T(-1, k) = T(k, -1) = T(0,0)=1$. The closed form expression for $T(n,k)$ is a bit messy, but fortunately we don't need it.

Note that the binomial coefficients $\binom{n}{k}$ are defined by the nearly similar recurrence $\binom{n-1}{k} + \binom{n-1}{k-1}$ so we'll have $T(n,k)\ge \binom{n}{k}$ and in particular $T(100, 50)\ge \binom{100}{50}$ and by Stirling's approximation we'll have $T(100,50)\approx 2^{100}/\sqrt{50\pi}$, which is pretty much what you guessed.

\[In fact, it turns out that $T(n,k)$ is quite a bit larger than $\binom{n}{k}$.\]
> 2 votes

# Answer
Hint1:

Try to figure out by hand the invocations of binomial1 for similar, but smaller numbers, e.g. `binomia1l(4,2,p)`, `binomial1(10,5,p)`, or for not so similar number pairs like `binomial1(10,7,p)`.

Hint2:

You don't need a formal analysis to answer the question how often binomal1 is called when you invoke binomial1(100,50). You can write a program to calculate this value. This program must be more efficient than binomial1, e.g. by remembering the values already calculated.
> 1 votes

---
Tags: algorithm-analysis, runtime-analysis, recursion
---


# Question
Title: How would I add 0.0.15.255. to 172.1.6.255.?
How would I add 0.0.15.255 to 172.1.6.255, talking about IPv4 networks here. I have done things like 192.168.1.15 plus 0.0.1.30 to be 192.168.2.45. but when it goes over the limit of 255, I just do not now how to do this... Help?

This is the what I am assigned to do:

I am given the block of adresses 172.16.0.0. and am told to design a scheme/ diagram of an adressing of the following given network, using basic subnetting:

1.HQ Lan (500 hosts) 2.West Lan(400 hosts) 3. East Lan (400 hosts)... .... ... .. 15. WAN 8 (2 hosts)

So the assignment is done like $2^p\geq15 \implies p=4$ So, since the default subnet for our given adress is $/ 16 + /p= /20\implies 12$ bits are left for hosts.(meaning 12 $1's$ to add to an adress to get the broadcast..)$2^{12}-2 \> 500,$(because of HQ Lan , with the most number of hosts..) therefore subnetting is possible. Then it says that the IP of the subnetworks are as follows (with broadcast adresses.)

$$1. \text{HQ Lan:} \ \ 172.16.0.0. \ \ \text{ Broadcast adress: } \ \ 172.16.15.255. \\ 2.\text{West Lan:} \ \ 172.16.16.0. \ \ \text{ Broadcast adress: } \ \ 172.16.31.255. \\ 3. \text{East Lan:} \ \ 172.16.32.0. \ \ \text{ Broadcast adress: } \ \ 172.47.255.255. \\ ... \\ 15. \text{WAN 8:} \ \ 172.16.224.0. \ \ \text{ Broadcast adress: } \ \ 172.16.239.255.$$

I can assume from this context one can deduct can deduct from what I mean by "add". If I had the example: $$\text{Example LAN:172.1.6.255. } \text{ Subnetmask: ???}$$ I would have to add by $0.0.15.255. $

# Answer
You don't. Adding IP addresses makes no sense. It's like asking "How would I add an apple to a kiwi?" (Sounds like a setup for some bad joke, I know.) Not all things can be added. There's no reason why you'd ever need to add two arbitrary IP adresses.

---

Based on the edited question, it appears that you want to design a scheme to assign IP addresses, and your idea was to do this by somehow adding IP addresses to each other. Time to try a new idea. There are ways to solve the design problem without trying to "add" IP addresses (which doesn't mean anything anyway). In other words, you've got an XY problem. You might start by reading about netmasks, subnets, and local-area networks in your favorite networking textbook.
> 5 votes

---
Tags: computer-networks
---


# Question
Title: Termination of Moore's algorithm to minimize deterministic automata
I use Moore's algorithm to minimize DFA as concluded below.

1. We start with the complete graph with vertices `Q` and edges `E = { {p, q} | p = q ∈ Q }`
2. We mark all edges `{p, q} ∈ E` with `p ∈ F` and `q ∈ F`
3. As long as there exist marked edges in `E`, we repeat the following procedure. We choose some marked edge `{p , q } ∈ E`. Then we mark all unmarked edges `{p, q} ∈ E` with `{p , q } = {p · a, q · a}` for some `a ∈ Σ`. Afterwards we remove the edge `{p , q }` from `E`.
4. All marked edges are eventually removed.

Then I guess a new minimal automata is obtained by joining the states linked by the remaining unmarked edges. Is it true?

If so, what about this case?

```
States: {1, 2, 3}
Alphabet: {a, b}
Start: 1
Final: {3}
Transition: {(1, a, 2), (2, b, 3)}

```

By Moore's algorithm, at the end of loop we will have one unmarked edge between state `1` and `2`. As my guess above, the next step is joining both states. But the result doesn't make sense.

# Answer
Most minimization algorithms assume automata to be **complete** s.t. for every state `p` and alphabet `a`, there is a transition where `(p, a, q)`. Hence, for the case, we need to add one more state as a sink state. The DFA becomes:

```
States: {1, 2, 3, 4}
Alphabet: {a, b}
Start : 1
Final : {3}
Transition :
{(1, a, 2), (1, b, 4), (2, a, 4), (2, b, 3), (3, a, 4), (3, b, 4),
(4, a, 4), (4, b, 4)}

```

By Moore's algorithm:

Picking `edge(3,4)` causes we mark `edge(2,1)` and `edge(2,4)` by `b`-transition.

Picking `edge(2,4)` causes we mark `edge(1,4)` by `a`-transition.

Now we don't have any unmarked edges left. Hence, no states has to be joined.
> 0 votes

---
Tags: algorithms, automata
---


# Question
Title: 3SAT with an oracle for expanding the clauses
Let's consider 3SAT, so we have clauses like:

(A or B or C) and (A or not B or D) and ...

If we distribute the "and" over the first two clauses, we get the disjunction of:

```
      A and A --> simplifies to A

      A and not B

      A and D

      B and A

      B and not B --> simplifies to false

      B and D

      C and A

      C and not B

      C and D

```

I presume the brute force strategy of expanding all the clauses and simplifying when possible would take exponential time. My question: what if an oracle gives you a certificate telling you which clauses to expand? Is it known whether this could get you down to polynomial time?

Let's call this language 3SAT^A, so it's something like: 3SAT^A = {(x, A(x)) : x is a 3SAT formula}, where A(x) tells you how to expand the clauses in x.

Is it known whether there is an A such that 3SAT^A is in P? If so, could one hope to show P != NP by showing that no such A is computable in polynomial time?

# Answer
Your question seems closely related to the question of whether $NP=coNP$. It seems that the existence of such an oracle would imply $NP=coNP$ since the oracle would give you a polynomial certificate for "no"-instances of $SAT$.

I don't think this would be a viable way to show $P\not = NP$ since all you'd be showing is that there's no way to expand clauses in polynomial time, but that does not rule out other approaches for solving $SAT$.
> 1 votes

---
Tags: p-vs-np, 3-sat
---


# Question
Title: Genetic Algorithm Neural Network- Inputs for evolving creatures
I made a GANN program for evolving creatures. The genes that get put into the GA for each ind are the weights that go into the neural net for each creature. The NN is a basic 1 hidden layer NN with bias neurons and it uses TANH so the weights are from -1 to 1. The GA uses .8 crossover rate (.3 elitism) and .003 mutation chance per gene/weight. Ranked selection is used and 1 point crossover.

The creatures go after food that spawns in a random location after pickup and there are also traps to avoid that done move. A food raises the fitness by 1 and the trap makes it lose 1 fitness point. They start at 1 fitness (health) and if they hit to many traps and get to 0 they die and their genes aren't used in the next evolution. But not many die anyway only like 5 to 10/50 per gen. There are 20 of both traps and food and 50 creatures. There are two sensors on the creatures. One on the left side about 30 degrees from the center face and one on the right. The inputs are each sensors dis from the closest food and from the closest trap.The outputs are 2 numbers. I pick which is highest get the abs value and multiply it by a max angle of 15 degrees and the creature rotates by that amount either right or left depending on which output neuron was the highest.

Before I added in the traps the creatures were very good at getting to food quickly and accurately. And they learned how to do it relatively quickly per test (after like 15 gens they were very good). Then I added in traps and just added the inputs that were the distances from the sensors to these traps just like with the food. **With both inputs to food and traps they no longer learn.** They just kind of make circles or do random stuff. They aren't dying that often (their fitness starts at 1 but if they hit food before they hit a trap they wont die just lose a fitness) but they aren't learning anymore. I tried normalizing (dividing by the env square side length) but didnt change anything. **So is the issue with the inputs or something else?**

# Answer
> 3 votes
If I understand well, your neural net have 4 inputs. But let's take this example :

* The black circle is your creature
* Grey circles are your sensors
* Green circle is food
* Red circle is a trap

Does the left sensor "see" the trap closer than the food ?

**If yes, you're doing it wrong**

A better way to do it would be to "simulate" real eyes, like this, where each sensor can only see what is in its field of view

Your neural net can take 2 inputs per sensor, as you did, with the distance to the closest food/trap **it can see**.

A second thing to try would be to only take in account the closest item for each sensor.

Another interesting thing to do would be to decrease the fitness over time, avoiding passive bots

---
Tags: neural-networks
---


title: Minimum size of largest clique in graph

text:
# Question
Title: Minimum size of largest clique in graph
I'm having trouble with a problem from HackerRank, and I'm hoping someone here can enlighten me. The problem is stated like this:

> What is the minimum size of the largest clique in any graph with N nodes and M edges?

The hints suggest using Turan's theorem, but it's not clear to me how to get from that to a solution.

How can I solve this problem, either with or without Turan's theorem?

The full questions is here.

# Answer
Turán's theorem states that if a graph on $n$ vertices doesn't contain an $(r+1)$-clique then it has at most $\lfloor \frac{r-1}{r} \frac{n^2}{2} \rfloor$ edges. You take it from here.
> 2 votes

# Answer
Turan's theorem states the following:

If a graph with $n$ vertices does not contain a clique of size $r+1$, then the number of edges in that graph is at most $\frac{1}{2}(n^2 - (n\\,\bmod\\,r)\lceil n/r\rceil^2 - (r-(n\\,\bmod\\,r))\lfloor n/r\rfloor^2)$.

The former statement is equivalent to the following statement:

If a graph with $n$ vertices has more than $\frac{1}{2}(n^2 - (n\\,\bmod\\,r)\lceil n/r\rceil^2 - (r-(n\\,\bmod\\,r))\lfloor n/r\rfloor^2)$ edges, then it does contain a clique of size $r+1$.

The minimum size of the largest clique in any graph with $n \geq 2$ vertices and $m \geq 1$ edges can then be computed in a naive way as follows:

(1.) set $r=n-1$

(2.) compute $m^\*(r) = \frac{1}{2}(n^2 - (n\\,\bmod\\,r)\lceil n/r\rceil^2 - (r-(n\\,\bmod\\,r))\lfloor n/r\rfloor^2)$

(3.) if $m \> m^\*(r)$ return $r+1$ else decrement $r$ by 1 and go to (2.)

The algorithm above runs in linear time. A more efficient solution runs in logarithmic time. The idea is to utilize binary search to find the value $r+1$ such that $m\>m^\*(r)$ and $m \leq m^\*(r+1)$.
> 1 votes

---
Tags: graphs, combinatorics, clique
---


title: Two's complement Using ONLY Logic Gates

text:
# Question
Title: Two's complement Using ONLY Logic Gates
How can a 4-bit two's complement operation be implemented using only boolean logic gates (AND, OR, NOR, NOT, NAND, XOR, and XNOR)?

(This question was redirected to CS from Stack Overflow)

# Answer
> 2 votes
A two's complement operation is simply a one's complement operation followed by the addition of `1` to the result. One's complement is easy: simply invert all of the input bits.

The addition of `1` must be done with a 4-bit adder. A 4-bit adder is constructed using four stages of a 1-bit full adder. The 1-bit full adder accepts two bits, plus a Carry input, and generates the sum of the two bits, plus a Carry output. The following diagram is a 1-bit full adder:

We can cascade four of the 1-bit full adder stages together, feeding the Carry output of each stage to the Carry input of the next stage. The inverted (one's complement) inputs are applied to the `B` inputs of the four stages. To perform an addition of `1`, we apply the 4-bit binary value `0001` to the `A` inputs. The complete boolean circuit is shown below:

The above circuit can be reduced by noting that each XOR operation on the input of each adder stage can be replaced either with an inverter if the `A` input is a `0`, or a NOP (no operation) if the `A` input is a `1`. On further analysis, further reductions may be made to the circuit, as well.

---
Tags: logic, boolean-algebra
---


title: Longest cycle in a digraph

text:
# Question
Title: Longest cycle in a digraph
Given a directed graph $G$, we want a (simple) cycle in $G$ of maximal length. The cycle does not need to be an induced subgraph of $G$. What is known about this optimization problem?

Do we know its complexity? Is it much harder than the decision problem of detecting a Hamiltonian cycle? How well-approximable is the problem?

For the exact problem, is there a more efficient algorithm than exhaustive search using Johnson's cycle-enumeration algorithm?

Ideally, for the complexity question, I would like a description similar to here and here for related problems on undirected graphs: Longest induced cycle, Longest path, and Longest induced path. Longest cycle (for undirected graphs) is discussed in "A Structural Overview of NP Optimization Problems", although I have a harder time understanding that account.

FWIW, I'm particularly interested in (approximate) solutions for strongly connected digraphs of 100-500 vertices having average vertex degree ~10 and several induced tournaments on 5-10 vertices. I've been playing with genetic algorithms, and I'd like to know (1) whether better methods are available and (2) what level of performance I can reasonably aim for.

# Answer
> 1 votes
By querying for a cycle of each length, your problem is in P||FNP.
The following is a reduction from FP||FNP to your problem,

If there are no queries then just compute the output.  If there's exactly one query then Connect up the paths (search for "Connecting up").  Otherwise, for each query, for the CNF-SAT instance representing that query, create a new variable, put that variable into each clause, and create a new clause with just the negation of that variable.  Connect up the paths, but instead of putting in the magenta edge on those pages, string those graphs together cyclically by merging each t vertex with an s vertex (from a different query).  For each s-t portion, if the cycle traverses the
\[variable that wasn't originally in the corresponding CNF-SAT instance\] in the False direction,
then \[the truth values encoded by its directions along the s-t portion's other chains\]
are a witness for the corresponding query, else there are no witnesses for
the corresponding query.  Use the resulting witnesses to compute the output.

since

a \[cycle that doesn't use any s-t vertex\] must stay within a single s-t portion,
whereas a cycle that uses the s-t vertices in their cyclic order can use all of them
and all-but-at-most-one from each s-t portion, so if there's more than one query
then cycles that don't use any s-t vertex can't be longest cycles
  and
a cycle that uses at least one s-t vertex must use them all,
so it must use as many vertices as possible in each s-t portion
  and
for each s-t portion, if the original CNF-SAT representing the corresponding query is satisfiable then there's a path through that portion which uses all of its vertices, else there's
a path through that portion which uses all but one of those vertices (traverse the
\[variable that wasn't originally in the CNF-SAT instance\] in the False direction)

.
(Thus, your problem is FP||FNP-complete.
That reduction goes    FP||FNP  -\>  MAX-SAT  -\>  your problem  .)

For approximation, this is the main paper, although I'm annoyed
at how they very-nearly show things but don't state them.

Since for a fresh variable h, R($\hspace{.02 in}$g,h,g) will force g to be False, and then such g
can be used everywhere, including in R(+x,g,-x) constraints to force +x and -x
to take on opposite truth values, wikipedia's formula induces a reduction from
m-clause n-variable 3-SAT to ((5$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$m)+n+1)-clause ((6$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$m)+(2$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$n)+2)-variable *monotone* 1-in-3 SAT.
By digging through section 7 ("Proof of Proposition 1"), one can see that they have a reduction from the search version of m-clause n-variable *monotone* 1-in-3 SAT to the search version of
((145$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$m)+n+2)-vertex R2VDP with in-degree and out-degree both bounded by 3 which works even if some clause(s) has(ve) more than one of the same variable.    (If I'm wrong about the last part
of my previous sentence, then one can just replace R($\hspace{.02 in}$g,h,g) with  R(u,g,v) ∧ R(u,v,w) ∧ R(v,g,w) .)
Since one can \[$\hspace{.03 in}$just output a cycle for sizes that are at most 3$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$v\] and \[replace the 2-\>3 edges
along the bottom of figure 1 with paths that each have at most 2$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$v *internal* vertices\],
figure 1 (with each G a copy of the input instance) yields \[a reduction from v-vertex R2VDP to digraphs whose number of vertices is *at least three but otherwise arbitrary*\] such that, given a
full solution to the R2VDP instance (i.e., one that exhausts all the vertices) one can efficiently
find a Hamiltonian cycle in the output graph, and given \[a cycle in the output graph whose
length exceeds 3$\hspace{-0.02 in}\cdot \hspace{-0.02 in}$v\] one can efficiently find a not-necessarily-full solution to the R2VDP instance.

Clearly, only the last of the previous paragraph's three sentences (the really-long one) might
yield any meaningful concrete lower bounds for your input sizes.  However, one can alternatively reduce from \[the modification of 2VDP to promise that if there are any such pairs of paths then there is such a pair of paths that together use *enough* of the vertices\] at the cost of replacing \["Hamiltonian cycle" with "cycle that uses *enough* of the vertices"\] and \["full" with "full-*enough*"\].
In the positive direction:

That paper also \[references an algorithm that you should consider\]
and \[gives an algorithm that you should consider\].
You can find both of those by going to the bottom paragraph on the page before section 2.
Color-coding can efficiently find short-enough cycles.  This paper's algorithm can more-efficiently
find short-enough *paths*, and it seems plausible that either it or one of the algorithms it
references can be modified to find short-enough cycles more efficiently than color-coding.

# Answer
> 2 votes
The problem of finding a longest simple cycle in a digraph is **NP**-hard, since the problem of finding a longest simple cycle in an undirected graph is a special case: you can consider an undirected graph to be a digraph with a symmetric edge relation. (Longest simple cycle is **NP**-hard since it lets you solve Hamiltonian cycle.)

---
Tags: complexity-theory, graphs, optimization
---


# Question
Title: Proving/Disproving that language L is non-regular/CFL
Here are three examples of questions I run into. **I'm not looking for solutions.**

> 1. If $L$ is CFL then $L' = \\{ ww^R | w \in L \\}$ is non-regular.
> 2. If $L$ is non-regular then $L' = \\{ ww^R | w \in L \\}$ is non-regular too.
> 3. If $L\_2, L\_3, L\_4$ are regular languages and $L\_1 \cup L\_2 = L\_3$ and $L\_1 \cap L\_2 = L\_4$, then $L\_1$ is regular.

The problem I'm facing here is that I'm having hard time to figure out what how to prove such claims.

Lets say I'd like to prove claim 1, I can't seem to understand what exactly should I prove? If I assume that $L'$ is regular, then what way can I follow that will lead me to contradiction? I would go for the intersection with CFL language, but this won't help me as CFL is closed under intersection with regular languages. So I'm pretty lost here.

Take claim 3 for example, after spending a lot of time trying to find a counter-example, I have strong feeling that this claim is true. (**please don't tell me if I'm wrong, this post is not about the answers**). Yet I couldn't find out what exactly should I prove? Of course that $L\_1$ is regular but in what way may I do that?

I hope you get my situation. What I'm asking from you is to describe how would your proof be written in the above claims? What would you try to archive in your proof?

Thanks a lot for your time.

# Answer
> 4 votes
In fact it turns out that there is no simple method to prove things like this. Except when you want to *disprove* a statement, then a well-chosen counter example suffices. But also here there are no guidelines how to find them. Experience and trial and error, I would say. In your three questions I see three different approaches.

For (1) go look for a counter-example. Since the statement is true for most languages, you have to look for trivial special cases, but still contradicting the general claim.

For (2) you can try contra-positive. Instead of $A \Rightarrow B$ consider the equivalent $\lnot B \Rightarrow \lnot A$. This is then a (somewhat exotic) closure property. Can you recover $L$ from $L'$?

And I am afraid that (3) looks like simple Boolean set algebra. It is in fact the most straightforward of the three questions.

# Answer
> 1 votes
For regular languages, my go-to tool is the Myhill-Nerode theorem. Sometimes, for explicitly proving that a language is non-regular, I reach for the pumping lemma.

So my first instincts would be to reach for the pumping lemma for problem 1, and the Myhill-Nerode theorem for problems 2 and 3. The reason that I don't reach for the pumping lemma in problem 2 is because knowing that a language is non-regular gets you very little useful information usually, so I expect that the proof for 2 will have to flow the other way, and that you'll end up proving that if $L'$ is regular, then $L$ is also regular.

Incidentally, I don't believe that proposition 1 is true. After all, what if $L$ is the CFL defined by $S \to aSa \\:|\\: \epsilon $ ? Then, $L'$ is the regular language given by the regular expression $ (aaaa){\*} $.

# Answer
> -1 votes
For 1, it is clear that L' is a palindrome, actually. So, it is really easy to prove that a set of palindromes is non-regular through pumping lemma. Here is one good solution

2nd statement also appears to be pretty much similar.

And for the 3rd statement, you should look into the closure properties of regular languages, especially, "closure under union".

---
Tags: formal-languages, context-free, finite-automata, proof-techniques
---


# Question
Title: Order of growth definition from Reynolds & Tymann
I am reading a book called *Principles of Computer Science* (2008), by Carl Reynolds and Paul Tymann (published by Schaum's Outlines).

The second chapter introduces algorithms with an example of a sequential search which simply iterates through a list of names and returns TRUE if a given name is found in the list.

The author goes on to say (page 17):

> We say that the "order of growth" of the sequential search algorithm is n. The notation for this is T(n). We also say that an algorithm whose order of growth is within some constant factor of T(n) has a theta of NL say. "The sequential search has a theta of n." The size of the problem is n, the length of the list being searched.

I find this really hard to follow. The book is riddled with errors, so I am not sure if I am missing something or if the there is a typo in the paragraph above. In general English I rarely see any sentence end with "...say".

I am very confused.

What does T stand for? The book does not explain. Is it for Time or for Theta?

If "a theta of NL" means "The sequential search has a theta of n." What does L stand for? 'Linear' or 'length'?

I have written to the publishers asking for an explanation. They said they would forward my message to authors. They have not replied. I have also tried looking at other sources but I still get the naggling feeling that I am misunderstanding something - so cannot rest until I have decoded this paragraph.

If anyone has a copy of that book, and has understood that paragraph. Then, I'd appreciate if you could let me know if that paragraph is accurate or explain it in other words. Thanks.

# Answer
The paragraph is wrong. Unfortunately, it looks exactly like the kind of thing that a student who does not understand the material would write as an answer to an exercise. This sort of nonsense has no place in a textbook. Make no sudden movements. Put the book down. Step away from the book.

> We say that the "order of growth" of the sequential search algorithm is n. The notation for this is $T(n)$.

No. $T(n)$ is the notation for a function called $T$, which takes an argument called $n$. That function could be used to mean anything whatsoever. There is something of a tradition of writing recurrence relations for the running time of programs in the form, e.g., $$\begin{align\*} T(1)&=k\\ T(n)&=T(n-1)+\log n \quad\text{for }n\>1 \end{align\*}$$ But $T$ is not an "order of growth", here: it is a specific function defined through a recurrence relation. And you cannot just write "$T(n)=\text{blah}$" and expect people to read your mind and know that the function $T$ denotes the running time of some algorithm. $T$ here stands for time.

> We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of NL say. "The sequential search has a theta of $n$."

This has obviously been mangled. I think the authors intended to write something like,

> We also say that an algorithm whose order of growth is within some constant factor of $T(n)$ has a theta of **$\boldsymbol{n}$ and we say,** "The sequential search has a theta of $n$."

But, please, we do not say "has a theta of $n$," just as, if $h$ is your notation for height, you wouldn't say "John has an $h$ of 180cm." It's just not a correct form of words. We actually say, "The running time of the algorithm is theta $n$ (or theta of $n$)." Note in particular, that $\Theta$ is a tool for talking about mathematical functions, not algorithms. Theta doesn't mean that the running time is something; rather, it's something you can use to talk about the running time.

"NL", by the way, denotes the complexity class nondeterministic logspace, which makes no sense at all in the position it appeared in the original quote.
> 78 votes

# Answer
It sounds like the author is attempting to explain **Big O** notation, but has renamed it $T$ for no particular reason, and mangled the text completely.

For a good description of **Big O** notation (as well as little-o and Theta), I recommend the MIT book Introduction to Algorithms by Prof. Leiserson.

It does seem that one important distinction is that $O-notation$ refers to the total complexity of an algorithm, which is typically *time*, *space* or both.
*(e.g. Some algorithms run slower with larger data sets; some require more storage space with larger data; and some require both more time and more space)*.

It seems that this $T-notation$ refers ***only*** to the time-measurement of an algorithm, and doesn't account for storage requirements.
> 2 votes

---
Tags: algorithms, algorithm-analysis, landau-notation, notation
---


# Question
Title: Is a Pushdown Automata possible for this language?
PDA for a Language L = { $a^i b^j \mid i \neq 2j+1 \\}$ over the Alphabet $\Sigma = \\{a,b\\}$

If it can be constructed, how?

**Edit** : I've tried make the PDA for $$L = \\{ a^i b^j \mid i = 2j+1 \\}$$ (with the intention of editing the PDA to accept if $a$ or $b$ is leftover) but can't figure out how to push the proper number of $a$'s.

# Answer
> 1 votes
The construction for PDA will be as follows :

1) Push all $a's$ into stack

2) For every $b$ pop two $a'$ from stack, continue this till all $b$ exhaust there will be three condition for acceptance -

1) If stack got empty before $b$ exhaust

2) If stack got empty and $b$ exhaust

3) If there exist more than one $a$ in stack after $b's$ exhaustion.

else REJECT.

---
Tags: automata, pushdown-automata
---


# Question
Title: When proving NP-completeness do I only need one instance of a problem or all of them?
I saw a proof of reduction of hamiltonian path to spanning tree with inner vertices having degree of k.

The person, who proved it, constructed a spanning tree from a hamiltonian path, basically u-x1-...-xi-...-xn-v, and where xi are inner vertices and then appended k-2 leaves to each one of those vertices.

I understand that that is indeed a correct spanning tree for the problem, and the u-v path does form a hamiltonian path.

But my question is, is this reduced algorithm supposed to find all such spanning trees or not?

I can create a spanning tree with inner vertices of degree k, in which there's no such hamiltonian path that spans all inner vertices, for example, and clearly this method won't work. So this makes the shown construction isolated, meaning it doesn't describe a general case of a spanning tree.

So is it enough to to just construct a certain instance of the problem B we want to prove to be NP-complete, or do we need to reduce a known problem A to the general case of B?

I am confused about this, because, for example, we can prove INDEPENDENT-SET to be NP-complete by reducing CLIQUE to it, and it involves just taking the inverse of the graph and then finding a clique in it. This case does reduce problem CLIQUE to the general case of INDEPENDENT-SET.

P.S. I am very new to NP-completeness.

# Answer
When you reduce Hamiltonian-Path (HP) to Spanning-Tree-with-inner-degree-$k$ (ST), you show that if you could solve ST then you could solve HP, and moreover in a specific way. If the resulting tree is not completely general, say it is always a Hamiltonian path with attached leaves, then you are actually proving the stronger result that the corresponding *promise problem* is already NP-hard.

A promise problem is one in which it is guaranteed that the input is either a Yes instance or a No instance, and the task is to distinguish only those two cases. In your case, the promise version is defined in this way:

* Yes instance: the graph contains a spanning tree formed by a Hamiltonian path backbone and $k-2$ leaves attached to all internal vertices;
* No instance: the graph contains no spanning tree in which the degrees of all internal vertices are $k$.

If a graph falls into neither class, we don't care what the answer is. Your proof shows that it is NP-hard to distinguish the Yes instances from the No instances.

We usually don't formulate NP-hardness results this way since it is more cumbersome, but you're right that the proof shows something more. However, if you only cared about the NP-hardness of ST, then there is no need for the reduction to potentially produce all Yes instances of ST. This is because the proof that the reduction implies NP-hardness of ST doesn't require this feature. Here is the proof:

> Suppose $A$ is NP-hard, and $f$ is a polynomial time reduction from $A$ to $B$ such that $x \in A$ iff $f(x) \in B$. Since $A$ is NP-hard, for every $L$ in NP there exists a polynomial time reduction $g$ such that $x \in L$ iff $g(x) \in A$, and so $x \in L$ iff $f(g(x)) \in B$. Since $x \mapsto f(g(x))$ is also polynomial time, this shows that $B$ is NP-hard.

At no point of this proof do we use anything about the possible instances produced by $f$.

---

Another situation in which we can conclude an improved result is when the instance (rather than the solution) has a specific form. Suppose, for example, that we were able to reduce HP to ST, and the resulting graph never has triangles (I'm not claiming that this is possible; this is just for illustration). In this case, we could conclude also that ST-for-triangle-free-graphs is also NP-hard. It still remains true that ST itself is NP-hard; if a special case is NP-hard, then the general case is a fortiori NP-hard.
> 2 votes

# Answer
To show the one direction you show that there is an algorithm that reduces one problem to another in polynomial time. If you reduce Hamiltonian Path to Spanning Tree, you always get spanning trees of some form (because that's how you construct HP instances in ST). You usually can't generate all ST instances via reduction from a HP problem.

So reduction is ANY HP to some ST where solution to ST is interpretation for solution for HP.

If you want to show that both are in the same complexity class, you'd want to show the reverse as well.

ANY ST to SOME HP where solution to HP is interpretation for solution for ST.
> 1 votes

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


# Question
Title: Is an expression in normal form if terminates on normal order but not applicative?
Just wondering if something like this...

```
(λx. y)((λx. (x x))(λx. (x x)))

```

Would be considered to be in normal form since it terminates with y if done by normal order but does not terminate if done by applicative order

# Answer
> 3 votes
The expression $(\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$ is not in normal form because it can be further reduced using the β-rule.

Also, as you noted, **Applicative Order** is not a *normalising reduction strategy*. For the expression $(\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$ it fails to find the normal form. This is because $(\lambda x.(x \ \ x) \ \lambda x.(x \ \ x))$ is a non-terminating argument, it has no normal form, then it will loop forever.

On the other side, **Normal Order** is a *normalising reduction strategy* because it will always find the normal form, if it exists of course. In fact this a practical consequence of the second Church-Rosser theorem. For the expression $(\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$ it finds the normal form. In this case, since $\lambda x. y$ is a constant function, it will ignore its (non-terminating) argument.

---
Tags: lambda-calculus
---


# Question
Title: What is the earliest use of "trees" in computer science?
I have a little history question, namely, as the title says, I am looking for early uses of *trees* (as a data structure, search tree, whatever) in computer science.

# Answer
Wikipedia says that the first use of tree in mathematics was by Cayley in 1857.

Since the use in computer science is taken directly from mathematics, it seems more fundamental to ask when they originated there. Unless computer scientists originally called trees something else, the first computer scientist to use "tree" doesn't seem any more significant than, say, the first Australian to use "tree".
> 13 votes

# Answer
According to Donald Knuth's TAOCP, Vol. 1, pg. 459 the following papers might be considered as one of the first appearances of trees in CS.

* H. G. Kahrimanian, *Analytical Differentiation by a Digital Computer*, Symposium on Automatic Programming, 6–14, 1952
* K.E. Iverson and L.R. Johnson, *IBM Corp. research reports RC-390, RC-603*, 1961
* A.J. Perils and C. Thornton, *Threaded trees*, CACM 3, 195–204, 1960

Check out TAOCP for more information and more references.
> 11 votes

# Answer
Isaiah: ""And there shall come forth a rod out of the stem of Jesse, and a Branch shall grow out of his roots"

The tree as a data model for genealogical information is very ancient indeed.
> 7 votes

# Answer
I found this paper in the (BCS) Computer Journal for 1960:

P. F. Windley: Trees, forests, and rearranging.

He introduces the concept of "trees", "described briefly by Douglas (1959)" \[Sandy Douglas\] "and attributed to Berners-Lee" \[Conway Berners-Lee, father of Tim\].

Interestingly his trees are botanically more accurate than modern CS trees, in that they have the root at the bottom rather than the top!

http://comjnl.oxfordjournals.org/content/3/2/84.full.pdf+html?sid=a1c02733-1497-49e9-b308-a05c1dcca1df

Coincidentally, the last citation in the paper is to a paper which Windley co-authored with Tony Rowland Jones and "L. F. Kay", which is a misprint for L. R. Kay, my father, who went on to run UCCA, the central University Admissions system in the UK.

A letter from Conway B-L to the Computer Journal commenting on this paper, and a response from Windley, is split between pages 174 and 184 of the following issue:

http://comjnl.oxfordjournals.org/content/3/3/174.full.pdf+html http://comjnl.oxfordjournals.org/content/3/3/175.full.pdf+html
> 4 votes

# Answer
Lambda calculus dates back to the 1930's. Its grammar is an early application of trees, specifically abstract syntax trees. Every LC term is a tree. Variables are the leaf nodes. Both abstraction and application terms consist of other terms, so they are non-leaf nodes.

I don't know when LC terms were first thought of as trees. However, the early proofs involving LC required case analysis, much like what programmers writing programs to walk ASTs do now.
> 3 votes

---
Tags: data-structures, reference-request, trees, history
---


# Question
Title: Finding a method to classify pixels according to how drastic their intensity change
I am looking for a method to classify pixels into three groups: (1) Pixels which does not change their intensity much in general (the slight changes may be due to noise only), (2) Pixels which change their intensity very slowly, in general monotonically and gradually, and (3) Pixels which change their intensity drastically over a certain threshold.

I tried using the Running Gaussian Average Method, such as checking how many standard deviations the current pixel is away from the running mean. The pixel is classified as group (1) when the result is very small, as group (3) when the result is very large, and (2) otherwise. But it does not seem to work very well, especially for group (2) because by definition, this group contains pixels which change their intensity moderately instead.

I expect I may need to build 2 or more models, because background subtraction methods normally result in classifying the pixels into 2 groups only, but here I need to classify pixels into 3 groups. Any ideas will be welcome. Thanks!

# Answer
> 2 votes
One approach to distinguish between (1) vs (2)-or-(3) is to use a statistical hypothesis test. A statistical hypothesis test can tell you whether the amount of change is too large to be explained by random chance. One reasonable approach might be to use linear regression: try to model intensity as a linear function of time $y = at+b$, and then use a statistical hypothesis test to see whether the coefficient $a$ is positive (i.e., $a\>0$ and the null hypothesis $a=0$ can be rejected at a 99% significance level).

Once you've identified all the type-(1) pixels, it's not clear how to distinguish between (2) vs (3), because you haven't given us a precise definition of what counts as drastic vs slow. One reasonable approach would be to again use linear regression, and then use a threshold $\alpha$: if it's not a type-(1) pixel and $0\<a\le \alpha$, then classify it as type (2), else if if it's not a type-(1) pixel and $a \ge \alpha$, then classify it as type (3). You'd have to set the threshold $\alpha$ in some way that's appropriate for your application. You could of course consider variations on this, e.g., where the linear regression only considers observations from the last 10 seconds of time (or whatever), or weights more recent observations more highly, etc.

---
Tags: computer-vision, modelling
---


title: How do genetic algorithms work exactly?

text:
# Question
Title: How do genetic algorithms work exactly?
I was looking at the basic genetic algorithm here

http://www.ai-junkie.com/ga/intro/gat1.html

But I have some questions about things I didn't get.

To reiterate:

---

You have a problem you want a good enough solution to.

You create `N` random solutions (encoded as bits of 0 and 1)

You evaluate a fitness or score for each for how good a solution it is.

Pick randomly 2 different of them. Based on each score, they have a higher chance of being picked. (i.e. higher score = higher chance of being picked, but the sum of all probabilities add to 100%)

Then for those 2 (call it `A` and `B`) picked, there is a cross over step. There is a chance associated with a crossover. The link uses 70%. So if the crossover happens, then we pick a random point and exchange the bits of both A and B after the point. This creates `C`.

1. We created a new solution. Do we remove one of the existing ones? If so, which one?

Then there is a mutation step. This is the part that confuses me most.

1. Does mutation step occur regardless of if the crossover step happened or not?
2. What do we mutate? `A` or `B` or `C`?
3. For whatever we mutate, does mutate mean we iterate over each bit, and for each bit there is a 0.1% chance to flip the bit?

Finally reevaluate the score for all and repeat all of this until you find a good enough solution.

---

Does anyone know?

# Answer
Looking at the code the tutorial provides answers your questions. First of all, as it's described/implemented, crossover doesn't create a new string, it just modifies the two selected ones. So,

1. Yes, mutation always occurs
2. You mutate both A and B. There is no C
3. Yes.
> 1 votes

# Answer
There isn't *one* genetic algorithm, there are many variants on the same theme. All use a *population* (set of candidates); *generations*, where better candidates are kept; most use the idea of *mutations* (change some candidate at random) and/or *crossover* (take two, perhaps more, candidates and splice them together to get new ones). Details vary wildly, some don't use one or the other of the basic operations. Most use descriptions of candidates that codify potential solutions so that specialized "mutation" operations, not just random bit changes, don't create nonsense; some have mutation operators that "repair" broken candidates; the "crossover" is codified so the result is viable (again possibly with a repair step). Some even apply improvement operations on the newly created candidates after mutation/crossover, by doing local changes aimed at making the candidate somehow better. The right codification of the potential solutions (candidates) is crucial to simplify the above operations. And so is the proper generation of the starting population. Then they are tuned by selecting population size, probability of mutation, probability of crossover, the exact method used to select the members of the next generation (keep the best ones, select at random with a bias towards the better ones, ...). Bad candidates can very well carry parts of the optimal solution.

All of this is highly problem dependent.
> 1 votes

---
Tags: genetic-algorithms
---


# Question
Title: Is the terminology of the word optimal substructure same for divide-conquer and dynamic programming technique?
why do we use the word optimal in case of optimal sub-structure , I guess in case of divide and conquer also we have sub-problems and they too when merged together provide the solution for entire problem .So what is the difference in terminology of sub-problems in divide and conquer and dynamic programming except for the fact that in the latter case we have overlapping sub-problems since both tend to imply that we have some sub-problems which combine to give an optimal solution to entire problem so in case of divide and conquer can we say that each sub-problem also gives us optimal solution ?

# Answer
The CLRS definition of optimal substructure:

> A problem exhibits optimal substructure if any optimal solution to the problem contains within it optimal solutions to subproblems.

This make sense for both methods.

Divide&Conquer is used when subproblems are independent, there is no overlapping subproblems. In this case you just combine solutions to resolve the main problem.

Dynamic Programming is used when subproblems are dependent, there are overlapping subproblems and results are typically stored in some data structure for later reuse.
> 1 votes

---
Tags: dynamic-programming, divide-and-conquer
---


# Question
Title: Prove that {⟨M,w⟩∣M accepts w only} is unrecognizable
$$L = \\{\langle M,w\rangle \mid \text{\\(M\\) accepts \\(w\\) only}\\}$$ How can I prove this language is unacceptable (unrecognisable)? I think I should use a reduction, I'm not sure how.

# Answer
> 4 votes
Let $A\_w=\\{\langle\\,M\\,\rangle\mid L(M)=\\{w\\}\\}$ and $\mathrm{HALT}=\\{(\langle\\,M\\,\rangle, w)\mid M\text{ halts on }w\\}$. It's known that the complement, $\overline{\mathrm{HALT}}$, is unrecognizable, so if we could establish a mapping reduction $\overline{\mathrm{HALT}}\le A\_w$, we'd have shown $A\_w$ is unrecognizable. Since mapping reducibility is closed under complements, we'll show that $\mathrm{HALT}\le \overline{A\_w}$, where, of course, $\overline{A\_w}=\\{\langle\\,M\\,\rangle\mid L(M)\ne \\{w\\}\\}$.

Define the mapping $f: (\langle\\,M\\,\rangle, w)\longrightarrow \langle\\,N\\,\rangle$ where

```
N(x) =
   if x = w
      accept
   if M(w) halts
      accept

```

Now

* If $(\langle\\,M\\,\rangle,w)\in \mathrm{HALT}$ we'll have $L(N)=\Sigma^\*$ so $\langle\\,N\\,\rangle\in \overline{A\_w}$
* If $(\langle\\,M\\,\rangle,w)\notin \mathrm{HALT}$ we'll have $L(N)=\\{w\\}$ so $\langle\\,N\\,\rangle\notin \overline{A\_w}$ Thus establishing the reduction we need.

---
Tags: turing-machines, undecidability
---


# Question
Title: Conditionals with normal order evaluation
From what I've read, conditionals (like the **cond** statement in lisp) do not need to be primitive if normal order evaluation is used.

Using lambda calculus and normal order evaluation, how can you emulate **if** and **cond** statements?

```
(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (<pn> <en>))

(if <predicate> <consequent> <alternative>)

```

References to SICP are welcome, though a simpler example would be helpful.

(Definitions of **cond** and **if** taken from Section 1.1.6 of SICP)

# Answer
Here is the church notation:

**TRUE**: $\lambda ab.a$

**FALSE**: $\lambda ab.b$

**IF**: $\lambda pxy.pxy$

By passing a church boolean as a predicate to the **IF** function, we choose one of two alternatives. **TRUE** chooses the first argument passed to it, and **FALSE** chooses the second.

We can derive **COND** by folding **IF** across a list of (condition, result) pairs

You can find wikipedia's explanation here, as well as assorted lambda calculus derivations here.
> 0 votes

---
Tags: lambda-calculus, evaluation-strategies
---


title: How Splitting Summation method works

text:
# Question
Title: How Splitting Summation method works
I'm reading Cormen, Leiserson, Rivest and Stein, *Introduction to Algorithms*, Appendix A, page 1152. They discuss a method called "Splitting Summations", where they split the summation and bound each term separately. For example,

$$\begin{align\*} \sum\_{k=1}^{n} k &= \sum\_{k=1}^{n/2} k + \sum\_{k=n/2 + 1}^{n} k\\ &\geq \sum\_{k=1}^{n/2} 0 + \sum\_{k=n/2 + 1}^{n} (n/2)\\ &= (n/2)^2\\ &= \Omega(n^2)\\,\end{align\*}$$

I didn't understand step 2 where they have replaced $k$ with $0$ in one part and $k$ with $n/2$ in other. How does this method work? Can anybody explain?

# Answer
> 2 votes
$$\begin{align\*} 55 = 1 + 2 + \dots + 10 &= (1 + 2 + 3 + 4 + 5) + (6 + 7 + 8 + 9 + 10)\\ &\color{red}{\geq} (0 + 0 + 0 + 0 + 0) + (5 + 5 + 5 + 5 + 5) \\ &= (10/2)(10/2) = 25\\,.\end{align\*}$$

If you're wondering how to come up with such substitutions, there's no general method: this is one of the creative things you have to do to produce mathematical proofs.

---
Tags: algorithm-analysis, proof-techniques, approximation
---


# Question
Title: Number of words within Hamming distance $\delta$
This is a problem I'm having reading Arora & Barak's book, page 378-379. They define:

> For two words $x, y \in \\{0, 1\\}^m$, the fractional Hamming distance of $x$ and $y$ is equal to the fraction of bits on which they differ, i.e. $\frac{1}{m} \cdot |\\{i : x\_i \neq y\_i\\}|$, where the $x\_i$ refers to the $i$-th bit of $x$ (same for $y\_i$).

Now, in the proof of Lemma 18.9, they use the fact that

> for every string $y\_i$ of $m$ bits, the number of strings that are of distance at most $\delta$ to it is ${m \choose \lceil \delta m \rceil}$

meaning that there are ${m \choose \lceil \delta m \rceil}$ words that disagree on not more than a $\delta$ fraction of bits.

But, I can't convince myself of that. Suppose for simplicity that $y\_i = 0000 \ldots 000$. Here are the words that are of distance at most $\delta m$: all the words that have exactly one $1$, or two, or three, up to $\lfloor \delta m \rfloor$ of bits set to $1$. Thus I rather think that this number is

$$ \sum\_{k = 1}^{\lfloor \delta m \rfloor} {m \choose k} $$

Can anyone explain?

# Answer
> 3 votes
That's an inaccuracy. If $\delta \< 1/2$ is constant then it is the case that $\sum\_{k=0}^{\delta m} \binom{m}{k} = O\left(\binom{m}{\delta m}\right)$, since the binomial coefficients increase very fast until they finally level out around the central binomial coefficient. The hidden constant depends on $\delta$. (When $\delta$ is close to $1/2$ this doesn't hold: for example, $\sum\_{k=0}^{m/2} \binom{m}{k} = 2^{m-1}$ for even $m$, while $\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right)$.)

At any rate, what they are interested in really is the estimate $\sum\_{k=0}^{\delta m} \binom{m}{k} \leq (1-\epsilon) 2^{H(\delta)m}$, which holds for every $\epsilon \> 0$ and large enough $m$ (depending on $\epsilon,\delta$).

---
Tags: combinatorics, coding-theory, word-combinatorics
---


title: How to prove P$\neq$NP?

text:
# Question
Title: How to prove P$\neq$NP?
I am aware that this seems a very stupid (or too obvious to state) question. However, I am confused at some point.

We can show that **P $=$ NP** if and only if we can design an algorithm that solves any given instance of problem in **NP** in polynomial time.

However, I do not understand how on earth can we prove that **P**$\neq$**NP**. Please excuse me for the following similitude as it might be so irrelevant, but telling someone to prove if **P** is not equal to **NP** appears to me like telling someone to prove that God does not exists.

There is a set of problems, those are unable to be solved by a Non-deterministic Finite Automata (NFA) with polynomial number of states regardless of the current technology (I know this is a sloppy definition). In addition, we have a considerably large set of algorithms which make some crucial problems (shortest path, minimum spanning tree, and even sum of integers ($1 + 2 + \dots + n$) polynomial-time problems.

> My question in short: If I believe that **P $=$ NP**, you would say "then show your algorithm that solves an **NP** problem in polynomial time!". Suppose that I believe **P**$\neq$**NP**. Then what would you exactly ask? What would you want me to show?

The answer is clearly "your proof". However, what kind of proof shows that an algorithm cannot exist? (in this case, a polynomial time algorithm for an **NP** problem)

# Answer
> 30 votes
There are three main ways I'm aware of that could prove that **P$\\,\neq\\,$NP**.

1. Showing that there is some problem that is in **NP** but not in **P**. You're probably familiar with the proof that comparison-based sorting need time $\Omega(n\log n)$ to sort a list of $n$ items. One could, in principle, produce a similar proof showing that 3SAT or some other **NP**-complete problem can't be solved in time $O(n^c)$ for any constant $c$. Geometric Complexity Theory seeks to use tools from algebraic geometry and group representation theory to prove such lower bounds, by considering the symmetries that problems possess. Circuit Complexity is another.
2. Showing that **P** and **NP** have different structural properties. For example, **P** is closed under complementation. If you could show that **NP$\\,\neq\\,$co-NP** (i.e., that **NP** is not closed under complementation), then is must be that **P$\\,\neq\\,$NP**. Of course, this is just pushing the problem one level deeper – how would you prove that **NP$\\,\neq\\,$co-NP**?

Another possibility is that we know that **NP** is exactly the class of problems that can be defined in something called existential second-order logic. If one could show that there's no logic corresponding exactly to **P** (or if there is a logic but it's different to $\exists\mathrm{SO}$), then **P** and **NP** must be different. A related (in fact, equivalent) idea is to show that **P** doesn't have complete problems under reductions defined by first-order logic, since it's known that **NP** does have complete problems under these reductions.
3. Prove that some problem isn't **NP**-complete. If **P$\\,=\\,$NP**, then every non-trivial problem in **NP** is **NP**-complete under polynomial-time many-one reductions ("non-trivial" here means not $\emptyset$ or $\Sigma^\*$). So, if you can show that some problem in **NP** *isn't* **NP**-complete, then we must have **P$\\,\neq\\,$NP**.

# Answer
> 6 votes
> My question in short: If I believe that **P=NP**, you would say "then show your algorithm that solves an **NP** problem in polynomial time!".

Don't forget that you still have to prove that your algorithm solves the problem, and that it runs in polynomial time.

> Suppose that I believe **P≠NP**. Then what would you exactly ask? What would you want me to show?

First, try to explain "why" **P≠NP**, and why this reason can be used to prove **P≠NP** in a suitable logical framework. Then sketch a proof, and explain how its most dubious parts can be defended. Next, break down this proof into simpler statements, which can be verified independently.

* For example, the logical framework provided by ZFC is good (even too good in a certain sense) at proving the existence of models (of explicitly given sets of axioms, often even satisfying additional metalogical properties). So if you know a reason for **P≠NP** related to the existence of a model with some strange properties, then first explain this reason, and then show how the corresponding model can be constructed within ZFC.
* As a non-example, I believe that one reason "why" **P≠NP** is that mathematics can approximate nearly everything that occurs in the physical world, including randomness. However, it is a known fact that formal systems are very limited in their ability to prove a given string, number, "object", or "artifact" as being essentially random, so it is unlikely that this reason can be used for a proof in any explicitly given deterministic formal system. Maybe if you designed a probabilistic (quantum) proof system were you can verify certain proofs in the system only up to a finite probability depending on your available physical resources ...
* As a likely non-example, the law of the excluded middle basically reflects a static view of the (mathematical) universe, and hence is *extremely unlikely* to hold in a dynamical universe. Now **NP=coNP** (or any other collapse of the polynomial hierarchy) would basically be an approximate version of the law of excluded middle with respect to time complexity, but time complexity is too close to a dynamical universe for this to be possible. There are logical frameworks like Girard's linear logic which are able to capture dynamic aspects of the universe, so ... Note however that Brouwer was in a similar situation and already stated the necessary failure of Hilbert's program as fact in his inaugural address Intuitionism and Formalism in 1912 (explaining why it would be circular reasoning), but still was unable to even sketch Gödel's incompleteness proof from 1930.
* As an approximate example, let's try to capture some of the available evidence for **P≠NP**, namely the exponential lower bound for the traveling salesman polytope, and the intractablilty of resolution based procedures for satisfiability due to weak pigeonhole principles. The "why" in this case is that a certain class of NP-complete problems cannot be solved efficiently by algorithms relying on certain natural (for the class of NP-complete problems considered) principles, like linear programming formulations for TSP, or resolution based proof methods for SAT. Different papers gave different independent reasons why this could be used to prove something, the last paper on TSP for example cited a "close connection between semidefinite programming reformulations of LPs and one-way quantum communication protocols" as reason, while the last paper on resolution cited two independent reasons, namely lower bounds "for a class of formulas representing the pigeonhole principle and for randomly generated formulas".
You can also observe that there were attempts to strengthen the results over time. The initial results for TSP only concerned symmetric linear programming formulation, while the latest results have no such restriction, and also apply to the maximum cut and maximum stable set problems in addition to TSP. The initial results for resolution considered just basic Davis-Putnam resolution procedures and a single class of artificial counter-examples, while the latest results cover large classes of resolution based methods, and give multiple classes of naturally occurring counter-examples.
For TSP, I have no idea how the results should be strengthened further, except maybe by applying to more problems in addition to TSP, maximum cut, and maximum stable set. For resolution, I would have many ideas how to strengthen the results further, but the article I linked to is from 2002, Stephen Cook and Phuong Nguyen published a monograph *Logical Foundations of Proof Complexity* in 2010 which I haven't even browsed, and I guess it will already cover many of my ideas. It is interesting to note how little difference it actually makes to most of us how much these results have been strengthened over time, despite our interest in the **P≠NP** question. Even if it would have been proven in the meantime that algorithms relying on logical systems without an equivalent of the cut rule cannot efficiently solve satisfiability problems, we would still believe that there has been essentially no progress on **P≠NP**, that the problem is essentially still as widely open as ever.

---
Tags: complexity-theory, p-vs-np
---


# Question
Title: Algorithm for multiplying multivariate polynomials
Let $R$ be a commutative ring. Let $f(x\_1, \dots, x\_n), g(x\_1, \dots, x\_n)$ be two multidimensional polynomials in $R$ with maximal total degree $\delta$. How fast can we compute the product of $f$ and $g$, i.e. the resulting coefficients of each term?

I have only been able to find a non-trivial algorithm for when $R$ is a field of characteristic 0, but not for $R$ being a general commutative ring.

# Answer
There is a general method for efficient multiplication in any ring. This would cover the case where the degree is bounded in each dimension separately, because a polynomial $p\in R\[x,y\]$ in variables $x$, $y$ over the ring $R$ can be interpreted as a polynomial $p\in R\[x\]\[y\]$ in the variable $y$ over the ring $R\[x\]$. This is essentially the case I thought about in my comment above. However, the total degree limitation from the question requires a different method. Such total degree limitations occur for determinants and permanents, but have little to do with convolution. It is not even covered in the general overview of multiplication algorithms. At least we may assume WLOG that the ring has has characteristic $p^m$ or 0, because it is easy and canonical to decompose a ring into simpler rings (and because factoring the characteristic is not part of the cost of multiplying two polynomials, even if it might be more expensive than the multiplication itself).

---

For $n\geq 2\delta$, the resulting polynomial $fg$ can have up to $2^{2\delta}$ monomial terms. For $R=\mathbb Z$, the coefficients of the monomial terms can all be different, so we can't do better than $O(2^{2\delta})$. The question had probably something like $O(N^2)$ versus $O(N \log N \log \log N)$ in mind. But if $N$ would measure the number of coefficients (of monomial terms) of the input polynomials $f$ and $g$, then $O(N^2)$ would be the optimal worst case bound. But what should $N$ measure instead?

---

Let's assume that $fg$ is determined uniquely by its values $fg(\underline{x}^1),\ldots,fg(\underline{x}^N)$ for suitable points $\underline{x}^1,\ldots,\underline{x}^N$. Then a possible way to compute $fg$ is to evaluate $f$ and $g$ at the points $\underline{x}^1,\ldots,\underline{x}^N$, multiply these values pointwise, and then determine $fg$ from these products. This is more or less also what happens when the FFT is used to compute a convolution.

The paper On Zeros of a Polynomial in a Finite Grid cited in the recent answer by Anurag Bishnoi gives sharp bounds on the number of zeros of a polynomial on a finite grid satisfying condition (D). A nonempty subset $S \subset R$ is said to satisfy **Condition (D)** if for all $x\neq y\in S$, the element $x−y\in R$ is not a zero divisor. For $n \in \mathbb Z^+$ we put $\[n\] = \\{1,2,\ldots,n\\}$. We have

> **Theorem 1.2** (Generalized Alon-Füredi Theorem). *Let $R$ be a ring, and let $A\_1, \ldots, A\_n$ be non-empty finite subsets of $R$ that satisfy Condition (D). For $i \in \[n\]$, let $b\_i$ be an integer such that $1 \leq b\_i \leq \\#A\_i$. Let $f \in R\[\underline{t}\] = R\[t\_1,\ldots,t\_n\]$ be a non-zero polynomial such that $\deg\_{t\_i} f \leq \\# A\_i − b\_i$ for all $i \in \[n\]$. Let $\mathfrak U\_A = \\{x \in A : f(x)\neq 0\\}$ where $A=A\_1 \times\dots\times A\_n \subseteq R^n$. Then we have (see §2.1 for the notation) $$\\# \mathfrak U\_A \geq \mathfrak m(\\#A\_1,\ldots,\\#A\_n;b\_1,\ldots, b\_n;\sum\_{i=1}^n\\#A\_i −\deg f).$$ Moreover, this bound is sharp in all cases.*
> 2 votes

---
Tags: algorithms, arithmetic, integers, polynomials, multiplication
---


# Question
Title: How to find a subset of numbers such that its average is close to the average of the full set?
I have a set of *n* numbers whose average (arithmetic mean) is *x*. I have to choose a subset of *k* numbers from *n* such that its average is closest to *x*. Please note that *k* is the upper bound. If the average can be represented with less than *k* numbers, then that set is chosen.

For example:
set = {1, 2, 3, 4, 5, 6} (n = 6) (average = 3.5)
If k = 1 then the subset can be either {3} or {4}
If k = 2 then the subset is {3, 4}
If k = 3 then the subset is still {3, 4}

I have to write an algorithm for the same. If this problem is not solvable in polynomial time, what would be a good approach to solve it? Any heuristic approach?

# Answer
> 1 votes
I am not sure if you are allowed to use a solver for this, but this problem can be easily formulated as a Mixed Integer Nonlinear Programming (MINLP) problem.

This can be solved with open source solvers like Couenne or Bonmin. Actually this model can be linearized so it can even be solved with linear Mixed Integer Programming (MIP) solvers.

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


# Question
Title: Cast to boolean, for integer linear programming
I want to express the following constraint, in an integer linear program:

$$y = \begin{cases} 0 &\text{if } x=0\\ 1 &\text{if } x\ne 0. \end{cases}$$

I already have the integer variables $x,y$ and I'm promised that $-100 \le x \le 100$. How can I express the above constraint, in a form suitable for use with an integer linear programming solver?

This will presumably require introducing some additional variables. What new variables and constraints do I need to add? Can it be done cleanly with one new variable? Two?

Equivalently, this is asking how to enforce the constraint

$$y \ne 0 \text{ if and only if } x \ne 0.$$

in the context where I already have constraints that imply $|x| \le 100$ and $0 \le y \le 1$.

---

(My goal is to fix an error in https://cs.stackexchange.com/a/12118/755.)

# Answer
I think I can do it with one extra binary variable $\delta \in \\{0,1\\}$:

$$ -100y \le x \le 100 y $$ $$ 0.001y-100.001\delta \le x \le -0.001y+100.001 (1-\delta) $$

**Update**

This assumes $x$ is a **continuous variable**. If we restrict $x$ to be **integer valued**, then the second constraint can be simplified to: $$ y-101\delta \le x \le -y+101 (1-\delta) $$
> 7 votes

# Answer
The following isn't pretty by any means, but it works. Let $0 \leq x \leq N$, $N=100$ in the specific case in the question. Then we have the following constraints.

1. $0 \leq z\_1, z\_2, z \leq 1$
2. $x - N(1-z\_1) \leq 0$
3. $-x -Nz\_1 \leq -1$
4. $-x -N(1-z\_2) \leq 0$
5. $x -Nz\_2 \leq -1$
6. $z\_1 + z\_2 - 1 \leq z$
7. $z \leq z\_1$
8. $z \leq z\_2$

The intuition is as follows. $z\_1 = 1 \iff x \leq 0$. This is encoded in constraints 2 and 3. Similarly constraints 4 and 5 encode $z\_2 = 1 \iff x \geq 0$. The last three constraints express $z = z\_1 \land z\_2$.
> 1 votes

# Answer
Here's a solution that uses two temporary variables. Let $t,u$ be integer zero-or-one variables, with the intended meaning that $t=1$ if $x \ge 0$, $u=1$ if $x \le 0$, and $y=\neg(t \land u)$. These can be enforced with the following constraints:

$$\begin{align\*} 0 &\le t,u,y \le 1\\ 1+x &\le 101t \le 101 + x\\ 1-x &\le 101u \le 101-x\\ t+u-1 &\le 1-y\\ 1-y &\le t\\ 1-y &\le u \end{align\*}$$
> 1 votes

---
Tags: linear-programming, integer-programming
---


# Question
Title: what does "reduce A problem to B problem in polynomial time" mean?
It is kind of NP-complete problem.
For example,

* **A problem**:
Given a sequence of numbers, return the maximum value within these numbers.
* **B problem**:
Given a sequence of numbers, return start index and end index of the maximum sum segment within these numbers.

To show how to reduce A problem to B problem in O(n) time.
Does this means we could solve A problem by solving B problems?
It seems a little bit strange for this case.

# Answer
> 1 votes
There are several types of reductions, the most common of which are *many-one reductions* and *oracle reductions*.

A **many-one reduction** from $A$ to $B$ is a computable function $f$ mapping strings to strings such that $x \in A$ iff $f(x) \in B$.

An **oracle reduction** from $A$ to $B$ is a computable function $f$ which has access to a $B$-oracle, and satisfies $f(x) = 1$ iff $x \in A$. That is, $f$ decides membership in $A$. The machine has a mechanism for accessing the oracle. When the oracle is presented a string $y$, it tells the program whether $y \in B$ or not.

Every many-one reduction $f$ can be formulated as an oracle reduction: the oracle reduction first computes $f(x)$, then asks the oracle whether $f(x) \in B$, and outputs the oracle's answer.

In the theory of NP-completeness, we always use many-one reductions. Reducing a problem A to a problem B in time $T(n)$ means giving a many-one reduction from A to B which runs in time $T(n)$. In particular, reducing A to B in polynomial time means reducing A to B in time $O(n^k)$ for some fixed $k$.

In your particular case it is hard to tell which kind of reduction is meant, since your problems are not decision problems. Perhaps some restricted kind of linear time oracle reduction, say one accessing the oracle only once. It's also not clear what computation model you should use. Under some computation models you can solve problem A in linear time, and so such a reduction trivially exists (it never asks the oracle anything).

---
Tags: algorithms, np-complete, reductions
---


title: How is $\emptyset^* = \{\epsilon\}$?

text:
# Question
Title: How is $\emptyset^* = \{\epsilon\}$?
I know that $\emptyset$ is a an empty language, i.e. language containing no string.

A law involving empty language is:

> $\emptyset L = L\emptyset = \emptyset$

It correctly states that we cannot concatenate non empty language $L$ with a language $\emptyset$ containing no string (as their is no string to concatenate in $\emptyset$), it yields empty language.

Then how concatenating a language containing no string with itself any number of times can yield even empty string? That is, how following law exist:

> $\emptyset^\* = \\{\epsilon\\}$

# Answer
> 10 votes
For any language $L$, by definition $$ L^\* = \bigcup\_{i=0}^\infty L^i, $$ where a word in $L^i$ is the concatenation of $i$ words from $L$. In particular, $L^0 = \\{ \epsilon \\}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing *zero* words from $L$.

# Answer
> 5 votes
$L^\*$ can be defined as the smallest language satisfying the recursive equation

$$ L^\* = \\{\epsilon\\} \cup L L^\* $$

or, equivalently as the the least fixed point of the (monotonic, Scott-continuous) language-valued function

$$ f(M) = \\{\epsilon\\} \cup L M $$

over the complete lattice of languages (hence, by Tarski, such a fixed point exists).

The above definition may look quite abstract, but one can find it quite natural when comparing it to the usual definition of lists in functional languages as a recursive type:

```
data List l = Nil | Cons l (List l)

```

From the equation above, we can see that $ \epsilon \in L^\* $ is trivially true whatever is $L$. (Not unlike the empty list being a list of `l`, whatever type `l` is.)

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: How can we prove that an enumerable/decidable group of languages is closed under an operation?
For example:

If the XOR operation on two languages, A and B, is described as: $A\\;\mathrm{XOR}\\;B = (A \cup B) \setminus (A \cap B)$,

1) How can we prove that the set of enumerable languages is closed under the XOR operation?

2) How can we prove that the set of decidable languages is closed under the XOR operation?

# Answer
Here is a similar example, with the *minority* operator: the minority of three languages $A,B,C$ consists of words belonging to at most 1 of $A,B,C$.

If $A,B,C$ are decidable then so is their minority. Indeed, given a word $w$, first determine whether $w$ belongs to $A$, to $B$, and to $C$. You can do this since $A,B,C$ are decidable. Depending on this data, either accept or reject $w$. This is an algorithm deciding the minority.

If $A,B,C$ are enumerable, then their minority need not be so. Indeed, let $A$ be a language which is enumerable but not co-enumerable (for example, the set of halting programs). The minority of $A,A,A$ consists of all words *not* in $A$, i.e., the complement of $A$. By assumption $A$ is not co-enumerable, so the minority of $A,A,A$ is not enumerable.
> 3 votes

---
Tags: computability
---


title: Modified counting sort algorithm?

text:
# Question
Title: Modified counting sort algorithm?
So I **have** an array $A$, already sorted with CountingSort. Now I reduce one randomly chosen element $j$ with $A\[j\]\>0$ by $x \in \\{1 \dots A\[j\]\\}$. I still have the counting array $C$, since I have sorted the array with counting sort.

The **question** is: how can I now sort the modified array in $O(k)$?

**So far**: Obviously I won't need to check all the elements of $A$ again, otherwise it would be $O(n)$. I have to modify the $C$ array somehow. If you subtract $C\[j+1\] - C\[j\]$ you have the number of elements in the respective interval (like $0 - 0=0$ are 0 Elements of value 0, $1-0 = 1$ is 1 Element of value 1). But this is still only for the old array.

How can I understand which element from $A$ is reduced only by looking at $C$?

Example:

Sorted $A\[4\] = \\{1,3,4,4\\}$, reduce let\`s say $j = 2$ with $A\[2\] = 4$ by $x \in \\{1, \dots , 4\\}$. Let $x = 4$ then we have $A\[4\] = \\{1,3,0,4\\}$. How can I sort it now in $O(k)$ like $A\[4\] = \\{0,1,3,4\\}$?

# Answer
> How can I understand which element from A is reduced only by looking at C?

I guess you can make $C$ array two-dimensional $C\[2\]\[n\]$ and in the second array you will initially (and after the counting step) store `0`-es only. (This means when counting you will fill only the $C\[0\]\[n\])

After, the counting step, your $C$ array should look like (taking the example above):

```
0 1 0 0 2  <- count of the elements with value i (i >= 0)
0 0 0 0 0  <- flag if the i-th element has been reduced.

```

When you reduce an element with value $j$, you will do:

1. $C\[0\]\[j\]$--; // decrease the count of $j$
2. $C\[0\]\[j - x\]++$; // increase the count of $(j - x)$
3. $C\[1\]\[j\]$ = 1; // set $j$ as decreased

This way, when you want to check if a value $j$ was reduced, you can just get the value of $C\[1\]\[j\]$ and check if it is $1$. The complexity of this will be $O(1)$.

> How can I sort it now in $O(k)$?

For the further sorting of the array, I don't think it's possible to do it in linear time (as Quicksort's complexity is $O(nlogn)$). You can, however, *shift* the decreased element to the left or to the right.
> 1 votes

# Answer
Here is an example. Suppose that the sorted array looks like this:

$$ 0000111222233444. $$

Now we reduce one of the $3$ entries to $1$. The new sorted array is

$$ 0000111122223444. $$

Let's put them side by side:

$$ 0000111222233444 \\ 0000111\mathbf{1}222\mathbf{2}3444 $$

The number of changes is bounded by the number of distinct elements (presumably, your $k$). Moreover, you can find the indices of the changes using your array $C$. This allows you to update the sorted array in time $O(k)$. I'm leaving the details to you.
> 0 votes

---
Tags: algorithms, sorting, arrays
---


title: A question on encoding

text:
# Question
Title: A question on encoding
Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this machine...

Q1. Is there a not trivial example of a Turing decidable problem which still remains decidable once encoded with a non-Turing computable function?

Q2. Is there a counter example?

# Answer
Q1. The empty language is decidable however you encode it.

Q2. Represent the natural number $n$ as the encoding of the $n$th Turing machine that halts when started with a blank tape. Under this encoding, any set of natural numbers, except for $0$ and $\mathbb{N}$ is undecidable.
> 2 votes

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


title: Combining adjacent memory blocks

text:
# Question
Title: Combining adjacent memory blocks
This is a conceptual issue that I am having in designing an algorithm for a memory allocator that works in conjunction with memory pooling. Free blocks are put on one of several free lists within the pool. The size of the block determines which list it is on. The question is how to figure out if the adjacent physical memory blocks are free and available for coalescing when they are on different lists? Or, in other words, how to figure out if physically adjacent memory blocks are also free when the blocks are on different lists and then combine them.

Granted, the time on this is expensive so I plan to run this only when a suitable block cannot be found or carved out of an existing block.

The only viable approach that I can think of is to scan the entire pool while looking for a signature. Then search all the lists to verify that the address of that block is on a list.

I have done some research and found the following links:

How does worst-fit memory allocation react when encountering contiguous empty memory blocks? http://faculty.kfupm.edu.sa/ICS/saquib/ICS202/Unit34\_MemoryManagement.pdf

Any suggestions or ideas?

# Answer
I would suggest keeping a hash table (which you possibly are) to search for addresses. Use one table for *all* the different pools. Do not keep separate tables for each pool.

The idea is that you start from a newly released block. You know its start address and its length.

To find blocks *after* the newly released one we simply calculate the first address after the block and search for it. If we find one we join them.

Now we search backwards.

To search backwards our address table must contain not only the start, but the end of blocks.

We search the table for entries matching our end-of-block address. Again if we find them we join.

If we are doing this check every time we get a newly released block then we do not need to check more than one post- and pre- address block each time. As these are hash table look-ups they'll be fast.

If we do this check periodically we will need to scan all blocks systematically for matches, including rechecking new joined up super blocks for additional matches.
> 1 votes

---
Tags: algorithms, memory-management, memory-allocation
---


title: How to parse data in a text file?

text:
# Question
Title: How to parse data in a text file?
I had a question about altering a text file. I have data in the following format.

```
1 a,b,c
2 d,e
3 a, l, m,n

```

**Note that some of them have spaces after the coma**

Now I have to resort the data in the following format

```
1 a
1 b
1 c
2 d
2 e
3 a
3 l
3 m
3 n

```

Now my plan is to first parse the data, and hold a count of how many data elements there are for each number. (Ex. for the number 1, there are 3 elements). Then I would move down the data by 3 spaces, starting from the bottom. Kinda like moving an array. (The main concern here is space more than time complexity)

Then I would enter each data element at the top.

My first question is, how exactly would I parse the data in a txt file and indicate delimiters such as the coma and the possible spaces.

Second, having done this, how would I just move down a whole line inside a text file down one?

I am very sorry if my question is convoluted. I will gladly clarify anything. Thank you so much for your time! Please let me know if there is anything i need to add. Also, I'm comfortable in both java and c. So advice on either language is useful.

# Answer
> 1 votes
I propose this, more direct to code (in java, c, etc.)

* read each line (until CR/LF)
* at begining, read a number, until spaces =\> number n
* after that, take next characters of line
* split them by ,
* for each, trim (delete space before or after) =\> strings s1, s2, s3
* then output n s1 CRLF n s2 CRLF n s3, etc.

---
Tags: data-sets, filesystems
---