# Question
Title: Proving that PP is closed under symmetric difference
I want to prove that PP is under symmertic difference. let A be a language in PP and B likewise. I tried showing that : (A\B) U (B\A) in PP , so by show each in PP and then showing that it's closed under union , I should be done. How do I show A\B in PP? Am I on the right track? Maybe there is an easier way?

# Answer
As stated in the Wikipedia article about PP, a proof that PP is closed under symmetric difference was a PhD thesis by David Russo Structural properties of complexity classes. Proving that PP is closed under union was also open for a long time until it was answered by R. Beigel, N. Reingold, and D. A. Spielman, "PP is closed under intersection", Proceedings of ACM Symposium on Theory of Computing 1991
> 5 votes

# Answer
There are several different definitions of $\mathsf{PP}$. I'll take this one: the class of languages $L$ such that there exists a probabilistic polytime Turing machine $T$ satisfying $$L = \\{x : \Pr\[T(x)=1\] \> 1/2\\}.$$ Let me stress that the Turing machine is only allowed to toss unbiased coins.

The first step is to show that for every language $L \in \mathsf{PP}$ there exists a probabilistic polytime Turing machine $S$ such that $$ L = \\{ x : \Pr\[S(x)=1\] \> 1/2 \\}, \\ \overline{L} = \\{ x : \Pr\[S(x)=1\] \< 1/2 \\}. $$ In other words, $\Pr\[S(x)=1\] \neq 1/2$ for all $x$. To show this, take the machine $T$ promised above, and suppose that on inputs of length $n$ it runs in time $p(n)$. Thus if $\Pr\[T(x)=1\] \> 1/2$ then $\Pr\[T(x)=1\] \geq 1/2 + 1/2^{p(n)}$. The new machine will output $T(x) \land B$, where $B$ is a random variable satisfying $\Pr\[B=0\] = 1/2^{p(n)}$ (we can realize such a variable $B$ in polytime). We have $$ \Pr\[S(x)=1\] = \left(1 - \frac{1}{2^{p(n)}}\right) \Pr\[T(x)=1\]. $$ If $x \in L$ then $$ \Pr\[S(x) = 1\] \geq \left(1 - \frac{1}{2^{p(n)}}\right) \left(\frac{1}{2} + \frac{1}{2^{p(n)}}\right) = \frac{1}{2} + \frac{1}{2^{p(n)+1}} - \frac{1}{2^{2p(n)}} \> 1/2. $$ In contrast, if $x \notin L$ then clearly $\Pr\[S(x) = 1\] \< \Pr\[T(x)=1\] \leq 1/2$.

Armed with this result, let now $A,B \in \mathsf{PP}$, with associated machines $S\_A,S\_B$, both satisfying the promise above. Our new machine $S$ will output $S\_A(x) \oplus S\_B(x)$. Using $p\_A(x),p\_B(x),p(x)$ to denote the probabilities that the machines $S\_A,S\_B,S$ (respectively) output $1$ on $x$, we have $$ p(x) = p\_A(x) (1-p\_B(x)) + p\_B(x) (1-p\_A(x)) = p\_A(x) + p\_B(x) - 2p\_A(x) p\_B(x). $$

We now have to consider three cases. Suppose first that $x \in A \Delta B$, say $x \in A$ and $x \notin B$. Then $p\_A(x) \> 1/2$ and $p\_B(x) \< 1/2$, and so $$ p(x) = p\_A(x) (1-2p\_B(x)) + p\_B(x) \> \frac{1}{2} (1-2p\_B(x)) + p\_B(x) = \frac{1}{2}. $$ A similar calculation works when $x \notin A$ and $x \in B$. So if $x \in A \Delta B$, we have $p(x) \> 1/2$.

Suppose next that $x \in A \cap B$. Then $p\_A(x),p\_B(x) \> 1/2$, and so $$ p(x) = p\_B(x) - p\_A(x) (2p\_B(x) - 1) \< p\_B(x) - \frac{1}{2} (2p\_B(x) - 1) = \frac{1}{2}. $$ Similarly, if $x \notin A \cup B$ then $p\_A(x),p\_B(x) \< 1/2$ and so $$ p(x) = p\_A(x) (1 - 2p\_B(x)) + p\_B(x) \< \frac{1}{2} (1 - 2p\_B(x)) + p\_B(x) = \frac{1}{2}. $$ We conclude that if $x \notin A \Delta B$ then $p(x) \< 1/2$.
> 5 votes

---
Tags: complexity-theory, closure-properties
---


title: Data Flow Analysis with exceptions

text:
# Question
Title: Data Flow Analysis with exceptions
Data flow analysis work over a control flow graph. When a language under consideration supports exceptions, control flow graph can explode.

What are the standard techniques for dealing with this blow-up? Can we soundly disregard edges induced by exception? Data flow analyses anyhow compute over-approximations, so we would end up with a less precise but sound solution. Is this true?

**Update**: Here are few useful links that I was able to dig out at the end:

# Answer
Ignoring exceptions is unsound. Example:

```
let g = {
     raise E;
}
let f = {
     x := interesting_stuff();
     g();
     x := 0;
}

```

When analyzing `f`, you need to take into account the fact that `g` raises an exception, otherwise you would incorrectly conclude that `x` is always 0 on return from `f`.

I don't know that there is a “standard” technique for dealing with exceptions. There's some literature on the topic, I don't have any more idea of what papers are relevant than I can find by a Google search.

Formally, exceptions can be turned into conditional statements that propagate up the call chain, which of course blows up the control flow graph. In many concrete cases, the exception case is the less interesting case, where a lot of data gets killed, so it should be handled lazily in a forward approach (no need to analyze the liveness *on* the exception path if the handler kills the data).
> 10 votes

---
Tags: programming-languages, program-optimization, software-verification
---


# Question
Title: Is it possible to prevent arithmetic errors with a dependent type system?
In a functional programming language I have functions like $$f\colon Int \times Int \times \cdots \times Int \to Int$$ which do some computation. However for certain arguments $(x\_0, \dots, x\_n)$ the function will cause arithmetic errors like *Integer overflows*, *Integer underflow* or even *Division by zero*. I do not want to handle those special cases within the function. Instead I would like to throw a type error at compile-time if someone calls the function with a undefined input.

So, my question is: Is possible to prevent arithmetic errors with a dependent type system?

And if so, does Adga, Idris or any other dependent type language support this?

# Answer
In theory, you can do anything of this sort with dependent types! Typically you would define your own (dependent) type, say

```
b_int = {z : Z | MIN_INT <= z <= MAX_INT}

```

Depending on the "flavor" of your dependent types, you might need a bunch of functions for going from `b_int` to `Z` and vice-versa (for well-defined values).

and then your function `f` would have to be of type:

```
 f : b_int * ... * b_int -> b_int

```

Now the tricky part. First you have to specify all the arithmetic operators, say `b_add : b_int * b_int -> b_int` in terms of the "ordinary" add function `add`. Ah except this isn't quite right. `b_add MAX_INT 1` shouldn't be allowed! So you would have to give it a stricter specification, along the lines of

```
 b_add : { (n, m) : b_int * b_int | MIN_INT <= n + m <= MAX_INT } -> b_int

```

Then you want to prove something along the lines of:

```
b_add_correct : forall n m, n + m = b_add(n,m)

```

where the pair `(n,m)` needs to be in the domain of definition of `b_add`. Here, again, there may be *a lot* of pain if you need to translate to and from the `Z` type of unbounded integers, depending on how explicit the sub-types are.

Similarly for division:

```
b_div : { (n, m) | MIN_INT <= n / m <= MAX_INT, m =/= 0 }

```

So, if your program only uses the bounded operations, then there should be no way of writing a type correct program that has overflow or NaN operations.

However, I hope to convince you as well that there may be a significant amount of pain if there are no natural inclusions of types into sub-types, `b_nat -> Z` and if proofs of the inequalities have to be carried around explicitly.

One example is if the coercion `box : Z -> b_nat` explicitly carries the proof of inequality, i.e. `box` actually has the type:

```
 box : (x : Z) -> (p : x <= MAX_INT) -> b_nat

```

(I'm omitting the lower bound for simplicity). Then the correctness for `b_add` might be something more like:

```
 b_add_correct : forall n m : Z, (p : n <= MAX_INT) ->
                                 (q : m <= MAX_INT) ->
                                 (r : n + m <= MAX_INT) ->
    n + m = unbox (b_add (box n p) (box m q) r)

```

Whew! It gets even worse if just *applying* a `bop` operation requires explicitly building a proof that some bound holds (for example if you know $n \< m$, then you might want to use the fact that $m - n \neq 0$ to do division). That can make your program look quite messy, and be hard to write, since your proof obligations and program writing become inextricably linked.
> 5 votes

---
Tags: programming-languages, functional-programming, dependent-types
---


# Question
Title: when can I know if a class (complexity) is closed under reduction (cook/karp)
How do I know if a class let's say PP , is closed under cook reduction or not closed?

I understand the concept of reduction (how to use it mainly) , but still can't figure out the meaning behind it, as to determine if some problem belong to that class if there is a reduction.

# Answer
> 2 votes
There's a clear definition of what it means for a complexity class to be closed under some kind of reductions: a class is closed if, whenever $Y$ is in the class and $X$ reduces to $Y$, then $X$ is also in the class. To know if a class is closed under some kind of reduction, you need to establish whether or not the class and the kind of reductions satisfy that definition. To establish this, you need to come up with a mathematical proof. Coming up with mathematical proofs is a creative act which can't be performed according to some fixed recipe.

In general, you should expect that a class is probably closed under some kind of reductions if the class allows computations that are at least as powerful as the reductions. So, for example, you should expect **EXP** to be closed under polynomial-time reductions but expect **P** to *not* be closed under exponential-time reductions. And you'd be correct in both cases.

---
Tags: complexity-theory, closure-properties
---


# Question
Title: proving that pp closed under cook reductions
I tried to prove or disprove that pp is closed under cook reductions. anyone has a idea or link to a answer?

# Answer
PH $\subseteq$ PPP  is known to hold, so if PP is closed under Cook reductions
then  PH $\subseteq$ PPP $\subseteq$ PPPP $\subseteq$ PP .     ( PH $\subseteq$ PP  is not known to hold.)

If  PP = PSPACE  then  PPPP = PPPSPACE = PSPACE = PP .
( PP ≠ PSPACE  is not known to hold.)

See the Counting Hierarchy.
> 2 votes

---
Tags: complexity-theory, reductions, closure-properties
---


# Question
Title: A question on the power of the operator in Grover's quantum algoritm
I'm new to quantum computing, so while studying Grover's algorithm I (and, I think a lot of other people too) could not help but notice that exactly the same operator is applied $\sqrt{N}$ times:

$$U = \[2 \left| \psi \right\> \left\<\psi \right| - I \]\mathcal{O} $$

Of course, it depends on the oracle $\mathcal{O}$ and, as far as I understood from David Roberts' comment in this discussion on mathoverflow

> More specifically, $U$ depends on $\left| \psi \right\>$ (and $N$, but that's a bit different) which is not always in the same relation to $\left| E \right\>$ in different concrete instances of the problem. Also, complexity is roughly an asymptotic measure, taken at worst case.

which (I think) means that in real tasks $\left| \psi \right\>$ can be not equal superposition of states.

**However, I don't see any prohibition here about $U^k$ ($k \in \mathbb{N}$, for example $k = \[\sqrt{N}\]+1$) be constructed previously for some specific range of tasks.**

So, my question is whether it is theoretically possible to obtain the short form for $U^k$ and apply a single operator instead of applying $U$ up to $\sqrt{N}$ times? May be it is impossible in general because of just analytic difficulties, but we can construct the operator $U^k$ for some specific example that allows simplification?

---

To illustrate my point of view, I theorized about the following problem: Suppose I want to compute my function $f(x)$ on some grid with $N\_1$ points and find whether $f(x)=a$ somewhere, if not - I will try bigger grid $N\_2\>N\_1$. Suppose I can efficiently construct an oracle $\mathcal{O}$ for this for any $N$.

My $\left| \psi \right\>$ is an equal superposition of states:

$$ \left| \psi \right\> = \frac{1}{\sqrt{N}}\sum\_{x=0}^{N-1}\left| x \right\>$$

I'll switch to the pure linear algebra, limiting to $4\times 4$ for simplicity:

$$\frac{1}{N}A := \left| \psi \right\> \left\<\psi \right| = \frac{1}{N}\begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 \end{bmatrix} $$

I will define $\tilde{I}$ - matrix representation of some arbitrary realization of oracle, e.g.

$$\tilde{I} = \begin{bmatrix} 1 & 0 & 0 & 0\\ 0 & -1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} $$

Let also denote

$$\tilde{A} = A\tilde{I} = \begin{bmatrix} 1 & -1 & 1 & 1\\ 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & 1 \\ 1 & -1 & 1 & 1 \end{bmatrix} $$

and notice that for $N=4$: $ \ \tilde{A}^k = 2^{k-1}\tilde{A} $ (for $N=5$ we have $3^{k-1}$).

Now we can compute:

$$U^k = ((\frac{2}{N}A - I)\tilde{I})^k = (\frac{2}{N}\tilde{A} - \tilde{I})^k = /\text{binomial theorem} / =$$ $$= \frac{2^k}{N^k}\tilde{A}^k+...+\begin{pmatrix}k \\ i\end{pmatrix}\frac{2^i}{N^i}\tilde{A}^i(-1)^{k-i}\tilde{I}^{k-i}+...+(-1)^k\tilde{I}^k=/\text{power of $\tilde{A}$}/=$$ $$=\frac{2^k}{N^k}2^{k-1}\tilde{A}+...+\begin{pmatrix}k \\ i\end{pmatrix}\frac{2^i}{N^i}2^{i-1}\tilde{A}(-1)^{k-i}\tilde{I}^{k-i}+...+(-1)^k\tilde{I}^k=/\text{$\tilde{A}=A\tilde{I}$}/= $$ $$=A\big(\frac{2^k}{N^k}2^{k-1}\tilde{I}+...+\begin{pmatrix}k \\ i\end{pmatrix}\frac{2^i2^{i-1}}{N^i}(-1)^{k-i}\tilde{I}^{k-i+1}+...+\begin{pmatrix}k \\ 1\end{pmatrix}(-1)^{k-1}2\tilde{I}^k\big)+(-1)^k\tilde{I}^k=$$ $$=\frac{1}{2}A\big(\frac{4}{N}I - \tilde{I}\big)^k\tilde{I} -A(-1)^k\tilde{I}^{k+1}+(-1)^k\tilde{I}^k =\frac{1}{2}A\big(\frac{4}{N}I - \tilde{I}\big)^k\tilde{I}+(-1)^k(I-A\tilde{I})\tilde{I}^k.$$

The matrices raised to power $k$ are just diagonal matrices based on the oracle and I think it is possible to implement them if we can implement the oracle itself. Since $\tilde{I}$ is arbitrary realization of the oracle, we can switch back to the "quantum" formula:

$$U^k =\frac{N}{2}\left| \psi \right\> \left\<\psi \right|\big(\frac{4}{N}I - \mathcal{O}\big)^k\mathcal{O}+(-1)^k(I-N\left| \psi \right\> \left\<\psi \right|\mathcal{O})\mathcal{O}^k = $$ $$=\frac{N}{2}\left| \psi \right\> \left\<\psi \right|\mathcal{O}'\mathcal{O}+(-1)^k(I-N\left| \psi \right\> \left\<\psi \right|\mathcal{O})\mathcal{O}'' $$

Thus we have much lesser structure to implement that will give us result in a few steps, not $\sqrt{N}$ in *this* *specific* *task*. Even if I made a mistake in calculations, the simplification approach is clear.

# Answer
> 1 votes
Did you check if your oracle is unitary? All quantum operations, including the oracles used in Grover's algorithm, have to be unitary.

For example, every row should be perpendicular to every other row. When I compute the dot product of two rows from your $U^k$ I don't get 0, so I don't think the rows are mutually perpendicular like they need to be.

Generally speaking, you need to be careful when adding together matrices to make quantum operations. If the matrices don't commute, weird things happen to the sum's eigendecomposition. If they do commute, you still might end up with eigenvalues that aren't on the complex unit circle. It's very easy to end up with a matrix that isn't unitary, and so doesn't correspond to a possible operation.

---
Tags: quantum-computing
---


title: Question regarding Karp-Lipton theorem

text:
# Question
Title: Question regarding Karp-Lipton theorem
In the proof in wikipedia, it goes like this:

Let $L \in \Pi\_{2}$, so we can describe membership in $L$ as a formula:

$\forall\_{y}\exists\_{z} V(x,y,z)=1 \iff x \in L$

(where V is polynomial deterministic verifier etc...)
Now they look at the subformula : $s(y)=\exists\_{z} V(x,y,z)$ and say that because it's an instance of $SAT$, and according to the hypothesis that $NP \subseteq P/poly$, its equivalent to $C(s(y))$, where $C$ is a valid circuit for solving $SAT$.

These are my questions:

1. What does $s(y)$ mean? Like what's the meaning of saying that something equals some predicate? It look like merely a technical part of the proof but I can't wrap my head around it.
2. What's the meaning of exchanging a logical predicate with circuit evaluation mean? Does it mean that we can decide if for every $y$ there exists $z$ such that $V(x,y,z)=1$ with a circuit?

# Answer
> 1 votes
The subformula $s(y) = \exists z V(x,y,z)$ is a Boolean function which depends on $x$ and $y$. In this context we can assume that $x$ is fixed, so we only show the dependence on $s(y)$. Here $\exists z V(x,y,z)$ is the definition of the function: the value of $s$ on an input $y$ equals the truth value of the formula $\exists z V(x,y,z)$ (recall we're assuming that $x$ is fixed).

Since $V$ runs in polynomial time, as in Cook's theorem we can encode $V(x,y,z)$ is a polynomial size formula in the variables $x,y,z$. Given the fixed input $x$ and an input $y$, we can substitute $x$ and $y$ in the formula for $V(x,y,z)$ to get a formula $\varphi\_{x,y}$ depending only on $z$. We can also convert this formula to CNF. The new formula is satisfiable, i.e. $s(y)$ is true, iff $\varphi\_{x,y} \in SAT$.

If we have a circuit $C$ solving SAT we can use it to check whether $\varphi\_{x,y}$ is satisfiable. That's what Wikipedia means when it writes $C(s(y))$: write $s(y)$ as an instance $\varphi\_{x,y}$ of SAT, and then run $C$ on the instance to get the truth value of $s(y)$. Since $C$ solves SAT, $C(s(y)) = s(y)$, that is, on input $\varphi\_{x,y}$ the circuit $C$ will output the truth value of $s(y)$.

---
Tags: complexity-theory, proof-techniques
---


# Question
Title: How many pages does the page table require?
I have found this exercise on the Internet but I´m having problems with sections 4 and 5, because I don´t understand where do the solutions appear from.

**Example: Mapping VAs to PAs**

**Suppose**
\- Virtual memory of 2^32 bytes
\- Physical memory of 2^24 bytes
\- Page size is 2^10 (1K) bytes

---

**1. How many pages can be stored in physical memory at once?**

2^(24-10) = 2^14

**2. How many entries are ther in the page table?**

2^22

**3. How many bits are necessary per entry in the page table? (Assume each entry has PPN, residentbit, dirty bit)**

16

**4. How many pages does the table require?**

2^23 bytes = 2^13 pages

**5. What is the largest fraction of VM that might be resident?**

1/(2^8)

**6. A portion of the page table is given to the left. What is the physical address for virtual address 0x1804?**

VPN = 6 --\> PPN = 2 --\> PA = 0x804

$$\begin{array}{c|c|c|} \text{VPN} & \text{D} & \text{R} & \text{PPN} \\ \hline \text{0} & 0 & 0 & 7 \\ \hline \text{1} & 1 & 1 & 9 \\ \hline \text{2} & 1 & 0 & 0 \\ \hline \text{3} & 0 & 0 & 5 \\ \hline \text{4} & 1 & 0 & 5 \\ \hline \text{5} & 0 & 0 & 3 \\ \hline \text{6} & 1 & 1 & 2 \\ \hline \text{7} & 1 & 0 & 4 \\ \hline \text{8} & 1 & 0 & 1 \\ \hline \text{...} & ... & ... & ... \\ \hline \end{array}$$

Could you help me with this two exercises?

Thank you in advance

# Answer
Here some of the answers seem incorrect to me.

**3\] Number of bits required for a page table entry.**

Page table Entry=\> R==D==PPN

R ==\>1bit

D ==\>1bit

Number of frames =2^14 ==\>14 bits

Number of bits in a page table entry= 1+1+14=16

**4\] Number of pages required by page table**

As the page table itself will be stored in main memory it will require some pages.

Amount of memory required for page table =size of an entry * Number of entries

```
                                     =16 bits * 2^22

                                     =67108864 bits =8388608 bytes

                                     =8192= 2^13 pages (: 1 page=1024 bytes)

```

**5\] What is the largest fraction of virtual memory resident:**

i.e. the amount of virtual memory that can reside in RAM.

i.e Total Physical memory / Total Virtual memory

```
                                     =2^24 /2^32

                                     =1 / 2^8

                                     =0.39% of virtual memory can be in RAM ant an instant of time.

```

Please go through Virtual memory from Charles C. Lin.

I hope this may help....
> 0 votes

---
Tags: operating-systems, virtual-memory
---


# Question
Title: More efficient vertex-labelling algorithm than BFS?
I am using the C++ boost library implementation of the push relabel algorithm to solve a max-flow problem. The output from that algorithm is a residual graph and in order to find the min-cut of my original graph, I need to find all of the vertices which are reachable from the source vertex in the residual graph.

I was planning to use BFS or DFS to traverse the residual graph, but I was wondering if there was any more efficient algorithms that anyone can suggest, as the size of my graphs are pretty large.

I plan on implementing my own, modified version of the push relabel algorithm eventually, and then I can probably label them as I go. But for now I would like to just run it with the boost library, so that I have something for comparison - but unfortunately that requires labelling the vertices separately.

Any suggestions would be greatly appreciated

# Answer
> 1 votes
For graphs that fit into main memory (or even in a largish L3 cache), you probably can't do much better than your library's traversal algorithm without significant effort.

But anyway, you're way into "try and measure" territory. Robert Sedgewick has a nice talk Putting the Science back into Computer Science, that explores flow problems as an example. He uses Ford-Fulkerson, not push-relabel.

# Answer
> 1 votes
It's quite clear that you can't be better in terms of asymptotic bounds, at least not without further knowledge of the graph.

There may be some margin of improvement in the implementation, though, in particular if the graph is huge: parallelisation, considering memory hierarchy, and so on.

Also, note that there may be ways in the max-flow algorithm to get around computing everything anew in every step. You may want to check out Dinic's algorithm.

# Answer
> 0 votes
The running time of BFS and DFS are asymptotically optimal (they can find all reachable vertices in linear time, i.e., linear in the number of reachable vertices), so you can't hope to do better by more than a constant factor.

Constant factors tend to depend heavily on platform-specific details (e.g., cache effects, the memory hierarchy) more than on algorithmics, so if you're looking for constant-factor speedups, that's probably off-topic here and more a matter of optimizing your code.

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


# Question
Title: Finding perfect matchings with as few database queries as possible
I am trying to research a problem similar to the stable matching problem with a few different rules. The problem is as follows:

* There are an equal number of men and women.
* Each man has a *perfect match* with one and only one other woman.
* No two men have a perfect match with the same woman.
* A *perfect matching* is a set of matches where all matches are perfect (as above).
* There exists a database that can determine how many matches are perfect in any set. You can query the database with a set to learn how many matches are perfect in that set, but you don't learn which matches.

I'm looking for an algorithm that finds a perfect matching that matches all the men and women, while querying the database the least amount of times.

Is there an efficient algorithm for this problem?

# Answer
> 2 votes
A $O(n \log n)$ solution works as follows:

For each man $M$, we find the matching woman in $O(\log n)$ queries. We start by dividing the women into two sets of size $n/2$. Using one query, we can find out which of the two halves contains $M$'s match. We recurse on that half.

# Answer
> 1 votes
Here is how to solve this in time $O(n^2)$, where $n$ is the number of women (or men). For each man and each woman, ask the database how many matches does the set consisting only of the two of them contain.

Presumably you can solve this much faster than $O(n^2)$, but this gives you something to start with.

---
Tags: algorithms, search-algorithms, efficiency, matching
---


# Question
Title: Describe an algorithm for painting cards in the following game
It's my first question out here, so please don't judge me too strictly.
I heard of the following game: there's set of cards with different set of objects (but the same number of them on every card) painted on cards, while for every pair of cards there's one and only one common object. The game is for two players. At each step each player draws a card and puts it along the card of the other player. The player who is the first to pronounce the common object wins the step and takes both cards. The one who attains all cards first is the winner.

Specifically:
1. There're 50 cards
2. Each card contains 8 different objects
3. There's set of 36 possible different objects (from which 8 objects are chosen)
4. The set of cards has the following property: for each pair of cards there's one (and only one) common object

What I'm asking is how to build an algorithm that chooses the subset of objects to paint on cards.

To make it strict:
Input:{N, O, K},
N-number of cards
O-total number of objects
K-number of objects on a card

Output:
N lines of k numbers each: n\_1, n\_2, ..., n\_N where
n\_1= {k1\_1, k1\_2, ..., k1\_K}
n\_2= {k2\_1, k2\_2, ..., k2\_K}
....
n\_N= {kN\_1, kN\_2, ..., kN\_K}
such that for any i,j\<=N exists |n\_i X n\_j|=1, where X is intersection of sets

It's clear to me, that not for all triples {N,O,K} there's a solution.
No limitations on time/space complexity. All supporting data structures are allowed.
Thanks in advance

# Answer
> 1 votes
The Ray-Chaudhuri–Wilson theorem states that the number of cards is at most the number of objects. See for example a paper of Noga Alon (in your case, $L = \\{1\\}$).

# Answer
> 0 votes
After a little digging I've found this twin question, which has a really great answer. Thanks for writing comments

---
Tags: algorithms, graphs, combinatorics, board-games
---


# Question
Title: Comparison of running times: Determine largest n to run in given time
I am browsing the "Introduction to Algorithms" book by Thomas H. Cormen. One of the very first tasks in the introduction chapter gives a couple of running time functions like

```
f(n)=lg n
f(n)=n!
f(n)=2^n

```

and the following durations: 1second, 1minute, 1hour, 1 day, 1month, 1year, 1century

The f(n) functions describe the time taken in microseconds and for each duration I should determine the largest n which still runs in the given time.

Quite easy for potency and faculty, but I am stuck at the logarithm (lg n). Even for one second n gets so sooo huge and later even wolframalpha does not calculate it for 1 day. It is just too huge.

Or ist it wrong to try to calcualte these equations?

```
1.000.000 = lg n [for 1 second]
60.000.000 = lg n [for 1 minute]

```

...

# Answer
That's the answer then. "It's so huge, it can't be written down at all".

If an algorithm takes ln (n) microseconds, where n is the problem size, then there is no way to represent a problem that cannot be solved within a second.

Your equation is absolutely fine, and the solution would be for example $n = e^{1,000,000}$. It's just a very, very large number.

BTW. It's a very useful thing to look at. For example, if your computer can solve a problem of size n in an hour, you would want to know "what size of problem could I solve in an hour if I bought a computer that is twice as fast, or ten times faster".
> 2 votes

---
Tags: time-complexity
---


# Question
Title: How does TCP manage to discard segment received from a source other than the one with which the connection has been established?
It is known that TCP is a connection *oriented* transport layer protocol of the TCP/IP suite. But TCP (and UDP) operate over a connection *less* network layer protocol, the IP (internet protocol). What this means is that in TCP, if a sender sends data to the receiver, at the network layer, the receiver will accept the packet, without bothering about the source IP address of the packet. The receiver network layer then strips-off the IP-header from the received packet (and the IP address information of the source and the destination get stripped along with it), and passes off the remaining segment to the transport layer.

Now the doubt arises is, since the IP address information has been stripped away from the *packet* before forwarding it to the transport layer, how does the TCP sitting at the transport layer manage to decide from which IP address the information has come, when the only address details the transport header contains is the source and destination port numbers of the processes running on the respective hosts?

# Answer
The TCP sitting at the transport layer, doesn't actually have the destination IP address, since the network layer indeed takes that information out before passing it to the transport layer. But to have a proper connection oriented protocol, we include a *pseudo-header*, which contains the important parts of the IP header, that is, source and destination IP addresses, protocol number and data length. This pseudo header is passed on to the transport layer of the receiver.

Using this pseudo header's fields TCP manages to get the source and destination IP addresses and hence, discard the packets received from the addresses other than the one with which the connection is established.
> 1 votes

# Answer
"Stripped away" is not strictly correct. A TCP packet is an IP header followed by the TCP-specific data. The IP-level information is needed, and used. In particular, the source IP address is needed (as you say) to decide which currently open TCP conversation should receive the packet that has just arrived.
> 1 votes

---
Tags: computer-networks, communication-protocols
---


title: Minimizing cost of bus travel

text:
# Question
Title: Minimizing cost of bus travel
A man has to travel for given number of days by bus. He can buy either:

* $1$ day ticket for $2Rs$ *(valid for 1 day)*
* $7$ days ticket for $7Rs$ *(valid for 7 consecutive days)*
* $30$ days ticket for $25Rs$ *(valid for 30 consecutive days)*

We are given an array, whose elements are the day numbers on which he travels.

For example, if the given array is $\\{1,3,5,8,9,10\\}$, then he travels on these $6$ days. Now we have to minimize the cost of his travel. What would be the best approach to solve this problem?

# Answer
> 4 votes
There's a rather simple algorithm for this.

You start at the end of the array, day 10. If you only wanted to travel from that day onwards, you could buy a 1 day, 7 day, or 30 day ticket. 1 day is optimal at a cost of 2.

Then you check the second to last entry, day 9. If you only wanted to travel from that day onwards, you could buy a 1 day ticket (and add the optimal combination of tickets from day 10 at cost 2, total cost = 4), or a 7 or 30 day ticket, which is more expensive.

Again from day 8, the cheapest is a day ticket plus the optimal combination from day 9 on, total cost 6. But then you check day 5: If you buy a single day ticket, you pay 2 plus 6 for travel from day 8, total 7. But if you buy a weekly ticket, the cost is only 7. You then proceed to the beginning of the array.

```
int n = 6;
int dates [n+1] = { 1, 3, 5, 8, 9, 10, infinity };
int ticket [n];
int cost [n+1];

cost [n] = 0;

for i = n-1 downto 0
    cost for 1 day = 2 + cost [i+1]
    let k7 = smallest k where dates [k] ≥ dates [i] + 7
    cost for 7 day = 7 + cost [k7]
    let k30 = smallest k where dates [k] ≥ dates [i] + 30
    cost for 30 days = 25 + cost [k30]

    if cost for 1 day is smallest
        ticket [i] = 1
        cost [i] = cost for 1 day
    else if cost for 7 day is smallest
        ticket [i] = 7
        cost [i] = cost for 7 days
    else
        ticket [i] = 30
        cost [i] = cost for 30 days
    endif

```

That's easily done in O (n) for any fixed number of different tickets. The answer would be a bit different if you have "weekly" tickets that are valid from Monday to Sunday, or from Sunday to Saturday, depending on the country, and "monthly" tickets that are valid from the 1st to the last day of a month.

---
Tags: algorithms, optimization
---


# Question
Title: Zero-based array implementation with logarithmic insertion time
Normal zero-based arrays (ie not those with a sort order) have constant lookup time, but linear insertion time.

For a specific problem I was musing about a balanced tree that would allow for an zero-based array implementation with logarithmic time for all of the following operations: insertion, removal and finding the next and previous element.

I'm reasonably sure it should be straight-forward to implement: The non-leaf nodes would have to store the count of elements in their left branch respectively.

Such a data structure should be useful in text editors, as the user obviously can insert text anywhere in the document and yet the editor is supposed to render a screenfull of text around a given location quickly as well.

My question: What's this data structure called? Is there a buzzword I can google? (Such as "B-tree", "red-black tree", etc. for key-ordered search trees?)

# Answer
All tree data structures that use pointers can be re-worked to use array indices as well, and that is probably your best bet. If you come across a design that uses NULL pointers, use the array index $-1$ to represent NULL.

In general, the best kind of structure to look for (and to arrayify if that is what you want to do) is a **rope**, which is a stronger kind of string (see Wikipedia). Ropes are designed for exactly this purpose.
> 4 votes

# Answer
The simplest approach is this: Take any search tree data structure (be it AVL trees, Red-Black trees, even B-trees), and store in each node one additional piece of information: The "size" of the node, that is, the number of elements stored in the node and its children. It's trivial to find the nth element in a tree if you have that information.

Since you're storing that information anyway, you may as well use some variant of weight-balanced trees, which have the nice property that the size information is precisely what they need to maintain their balance conditions. Two birds, one stone.

Having said that, I think Martin is correct that something like ropes, gap buffers, or enfilades would be better if you were actually implementing a text editor, because that's what they're designed for.
> 2 votes

# Answer
The structure that performs given operations in logarithmic time would be AVL tree or RB (red-black) tree with additional pointers for next and previous, which will be called augmented tree, more precisely doubly threaded.
The choice between AVL and RB depends on dominating operations or size (if dominating operation is search or the size of data is hige then AVL is better).
Left thread keeps inorder predecessor and right keeps inorder successor. The memory footprint will increase and insert operation will take more time, but prev/next will be constant time.
Alternative that you may find is tempting - keeping you might keep root pointer from node and traversing up and then performing search, it decreases memory footprint but in return you have to compare with root everytime and for example access to roots predecessor is just search from root.

About keeping element index in the sorted list count of elements i this will be Order statistic tree.
> 0 votes

---
Tags: data-structures, binary-trees, balanced-search-trees
---


# Question
Title: In instruction pipelining, can we forward an operand more than one clock cycle?
Most operand forwarding examples that use the standard 5-stage MIPS pipeline forward operands from EX or MEM by ONE clock cyle to a later instruction. Is it possible to do so for more than one (from the 5th to the 8th clock cycle, for example)?

# Answer
> 2 votes
Paul's Comment is correct: "Yes. This is one way of avoiding a structural hazard on the write ports of the register file with operations of several different latencies (i.e., having a single writeback stage for all operations). However, adding forwarding paths increases wiring and operand selection complexity."

In general, the amount of hazards and amount of opportunities for forwarding increase with pipeline depth. So a 10-stage pipeline will yield more hazards and more theoretical opportunities for forwarding than a 5-stage pipeline. However, the control logic to detect and schedule all the forwarding increases significantly (likely with a polynomial factor).

The distance of stages you can forward an operand is justified by the minimum of the two following things:

* The number of forward stages until the operand enters the register file.
* The number of reverse stages where the operand could logically be used.

In other words, it makes no sense to attempt to perform 5 cycles of forwarding on a 5-stage pipeline since all operands would have been in the register file anyway.

---
Tags: computer-architecture, cpu-pipelines
---


# Question
Title: Loading a word from a byte addressed cache
In a cache with byte addressing, the byte you want to load is selected using the block offset. But what if I execute a LW instruction and don't want a single byte but a full 32 bit word?

Is there some logic that selects whether you don't look at the block offset and just load the whole word (when you use a "load word" instruction) or you look at the block offset to choose the right byte (when you use a "load byte" instruction)?

# Answer
For nearly all major architectures, a cache line is 64 bytes wide. All memory transactions from your L1 cache all the way out to DRAM will use 64 byte lines. The only place where the byte address-ability comes into play is between the processor core and the L1 cache. It is common for L1 RAMs to be built with byte enables or some from of specification to a subset of the bytes from a 64 byte cache line.

Let's assume the interface from the processor to the L1 cache yields an address and a width (number of bytes). Suppose you want address 0xF002 and you want 4 bytes. The cache line is address 0xF000 (0xF002 & ~0x003f), the offset within the cache line is 0x0002 (0xF002 & 0x003f), and because you specified a 4 byte width you'd receive bytes 0xF002, 0xF003, 0xF004, and 0xF005.

Most processor/cache interfaces will only support common widths (1, 2, 4, 8 bytes), and basic architectures will force the addresses to be aligned (i.e., a 2 byte read can't start at an odd address). More advanced architectures will handle the misalignment in hardware (see MIPS unaligned load/store for a bad implementation). x86 allows unaligned loads and stores. Here is a short list of reasons unaligned memory accesses are bad:

> # Why unaligned access is bad
>
> The effects of performing an unaligned memory access vary from architecture to architecture. It would be easy to write a whole document on the differences here; a summary of the common scenarios is presented below:
>
> * Some architectures are able to perform unaligned memory accesses transparently, but there is usually a significant performance cost.
> * Some architectures raise processor exceptions when unaligned accesses happen. The exception handler is able to correct the unaligned access, at significant cost to performance.
> * Some architectures raise processor exceptions when unaligned accesses happen, but the exceptions do not contain enough information for the unaligned access to be corrected.
> * Some architectures are not capable of unaligned memory access, but will silently perform a different memory access to the one that was requested, resulting in a subtle code bug that is hard to detect!
>
> It should be obvious from the above that if your code causes unaligned memory accesses to happen, your code will not work correctly on certain platforms and will cause performance problems on others. from: https://www.kernel.org/doc/Documentation/unaligned-memory-access.txt
> 2 votes

---
Tags: computer-architecture, cpu-cache
---


# Question
Title: Membership problem for context sensitive languages PSPACE-complete
I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself.

Let's mark the membership problem for CSL as MEM. First I have to proof that $ MEM \in PSPACE $. This should be easy, just take Turing Machine that generate words from L in lexicographic order and check if any is the same as the input word w. We can stop with the Turing machine when we reach length w+1.

Seccond, make a reduction from some PSPACE language. Quantified Boolean formula problem (QBF) seems to be suitable for this reduction. I have seen how to make a reduction from MEM to QBF but here I need the opposite. If I had a word w, I could make a formula based on the configuration I must go through to get w and all those configurations would mean true for the QBF. The representation could be just going from the binary code to some formulas.

But when going from the opposite direction, I don't know how to make CSL work from any given formula.

# Answer
> 4 votes
I'm assuming that the context-sensitive language is given to you as a context-sensitive grammar. Summarizing the Wikipedia article, here is how to show that the word problem for context-sensitive grammars is $\mathsf{PSPACE}$-complete.

First, we show that the word problem is in $\mathsf{PSPACE}$. The productions in a context-sensitive grammar cannot decrease the size of the word. Therefore, given a context-sensitive grammar $G$ and a word $w$, we can repeatedly apply productions in reverse, in the hope of eventually reaching the starting symbol $S$. We also keep a counter, and give up after $|\Sigma|^{|w|}$ steps (this ensures that the machine always halts), where $\Sigma$ contains both terminals and non-terminals; the size of this counter is $|w| \log |\Sigma| = O(n\log n)$ (here $n$ is the input size). This puts the word problem in $\mathsf{NSPACE}(O(n\log n)) \subseteq \mathsf{NPSPACE} = \mathsf{PSPACE}$, using Savitch's theorem.

In the other direction, Kuroda showed how to convert a linear bounded automaton (that is, a machine in $\mathsf{NSPACE}(n)$) to a context-sensitive grammar in such a way that the LBA accepts a word iff the CSG accepts it. Given a language $L \in \mathsf{SPACE}(p(n))$, we consider the language $L' = \\{x\\#^{p(|x|)} : x \in L \\}$ obtained by padding $L$, and note that $L' \in \mathsf{NSPACE}(n)$. Kuroda's theorem gives an equivalent context-sensitive grammar $G'$. In order to check whether $x \in L$, we first compute $x' = x\\#^{p(x)}$, and then check whether $G'$ accepts $x'$. This gives a polynomial time reduction from any language in $\mathsf{PSPACE}$ to the word problem for context-sensitive grammars, and so the latter is $\mathsf{PSPACE}$-complete.

---
Tags: complexity-theory, space-complexity, context-sensitive
---


title: Correct way to implement linked list

text:
# Question
Title: Correct way to implement linked list
I'm doing this challenge on Hacker Rank that wants me to implement a linked list.

It seems to want me to find the last-added instance of node and change its head to link to my new instance of node. Therefore the last instance added would have `head=None` (I'm using Python).

This is the pic they provide -

Wouldn't it make more sense to create a node instance with its head linked to the previous node? That way the only node with `head=None` would be the first node created.

I've seen conflicting suggestions so far. I'm not a CS student or developer.

EDIT -

This example from Youtube (1.36) suggests the second method.

EDIT -

Sorry if this seemed like a programming question. I'm trying to see if there's a logical way to set up linked lists for my own benefit... solving the HackerRank challenge is not the issue.

# Answer
First of all, don't have a `head` pointer in your structure that doesn't point to the head of the list: it will confuse everyone. Call the pointer in your structure `next` or something!

You are right that in a singly-linked list (one with a `next` pointer but no `pre` pointer) it is illogical and inefficient to add new items to the end of the list. Singly-linked lists work best when you add each new item to the *beginning* of the list. Then all you need to do is:

1. Create a new item and fill in its data.
2. Set its `next` pointer to the value stored in the global `head` variable.
3. Set the global `head` variable to point to the new item.

Thus, as you say, only the first item to be added to the list will have `next=null`.

Adding items to the end of the list involves walking through the whole of the list every time, which is not efficient or sensible.

If you wanted a singly linked list to which you could add items at the end, you would have a second global variable (call it `tail`) pointing to the last item in the list. This makes for inelegant code, since you now have different kinds of behaviour when `tail` is null (which it will be at the beginning) and when `tail` is not null. In fact, a good way of handling matters in this case is to create the list with one fictional item in it already, and `tail` pointing to that item. This saves a lot of tests, but you will of course have to remember, when walking through the list, not to pay attention to that fictional item.
> 4 votes

# Answer
One of the solutions can be:

**Node\* insert(Node \*head,int data)**

{

```
Node *p,*q;

q=(struct Node *)malloc(sizeof(struct Node*));// Allocating memory for new node
if(q==NULL)
{
  printf("Memory Problem....");  //return if memory can't be allocated
  return 0;
}
q->data=data;                //Put data in data portion of the new node
q->next=NULL;                //The next link will point to NULL since it is getting added at the end of the list
if(head == NULL)             //Check out if the list is empty
{
    head=q;                  //If empty the new node will be 'head'
}
else
{
    p=head;
    while(p->next != NULL)    // Otherwise get to the end of the list
    {
        p=p->next;
    }

    p->next=q;                //last node of the list will point to the new node created

}
 return head;

```

}

I have tested, it is working on Hacker Rank. Whether the head is linked to previous or next it has to be singly linked list and we have to traverse to the end of the list for insertion of a node.

I hope this is helpful to you....
> 0 votes

---
Tags: data-structures, linked-lists
---


# Question
Title: Is intersection of regular language and context free language is "always" context free language
I have read that intersection of regular language and context-free language is always context-free. Most of the places an standard example has been used to prove this, e.g., \begin{align\*} L\_1 &= L(a^\*b^\*)\\ L\_2 &= \\{a^nb^n\mid n\geq 0\\} \quad\text{(which is context free)}\\ L\_1\cap L\_2 &= \\{a^nb^n\mid n\geq 0\\}\\,. \end{align\*} But my question is what if the regular language is finite, such as \begin{align\*} L\_1 &= \\{ab\\}\\ L\_2 &= \\{a^nb^n\mid n\geq 0\\}\\ L\_1\cap L\_2 = \\{ab\\}\\,. \end{align\*} Here intersection comes out to be finite and the language generated by intersection of both language is also finite which is regular (I know it's also context-free but regular is a stronger answer here).

What mistake am I making in understanding the concept?

# Answer
The claim is that the intersection of a regular language and a context-free language is context-free. You've intersected a regular language ($\\{ab\\}$) and a context-free language ($\\{a^nb^n\mid n\geq 0\\}$) and the result was a context-free language ($\\{a b\\}$). Sure, that language is also regular but every regular language is also context-free. The statement *isn't* that the intersection of a regular language and a context-free language is a non-regular context-free language.

Analogously, the child of two mammals is a mammal. You've taken two mammals and you're saying, "Why is their child a cat? It's supposed to be a mammal."
> 10 votes

# Answer
Your mistake is in interpreting the meaning of the statement

> The intersection of a regular language and a context-free language is a context-free language.

This statement means that if $R$ is regular and $L$ is context-free then $R \cap L$ is context-free. It *doesn't* state that $R \cap L$ is not regular; this is just not part of the claim.

Your first example shows that $R \cap L$ could be not regular, but it could also be regular, as your other example shows.
> 4 votes

---
Tags: formal-languages, regular-languages, context-free, closure-properties
---


# Question
Title: What is the relationship between tail recursion with other recursions?
I'm rather confused by the recursion theory.

From the link, the recursion theory was formed by Dedekind, Gödel and some other famous mathematicians. There are the following types of recursion. But where is tail recursion? can this concept parallel to these concepts? what else concept goes parallel to tail recursion?

```
 1.1 The Initial Functions
 1.2 Iteration
 1.3 Primitive recursion
 1.4 Primitive recursion with parameters
 1.5 Course-of-value recursion
 1.6 Double recursion
 1.7 Minimization (least search)

```

# Answer
We need to distinguish two things:

* Tail-calls are calls to functions that are made in tail position. Tail-recursion is a recursive tail-call.
* Tail-call optimization is the process by which tail-calls are turned into loops or GOTOs in compilers.

The second, as others have stated, is an implementation detail that falls in the theory of compilers, and isn't really recursion theory.

However, it is *absolutely* possible to study tail calls in the context of computability. In particular, there is something called Continuation Passing Style.

There exist CPS-transformations which can turn any lambda-function into one in continuation passing style. So the set of languages computed using only tail-calls is equivalent to the set of recursively-enumerable languages.

CPS has many applications in the theory of programming languages, and the concept of tail recursion is useful for more than just the tail-call optimization.
> 3 votes

# Answer
Tail recursion is a specific implementation detail. Mathematical functions are not algorithmic implementations, so the concept does not make sense.

To be precise, tail recursion is a specific optimization in which the epilogue of the caller and the prologue of the callee are ignored, by virtue of a direct transfer of execution. This is possible because the two deal with the management of the internal state of the function, and in a recursive call the caller and callee are the same function so their state will be similar. If the final state of the caller and the initial state of the callee can be linked by a relatively simple transform, such a direct transfer of execution may be more efficient than a regular function call. This is of course dependent on the execution architecture, but it is a common occurrence.
> 0 votes

---
Tags: recursion, recursion-theory, tail-recursion
---


title: Dijkstra with bitwise OR of edge costs

text:
# Question
Title: Dijkstra with bitwise OR of edge costs
Given a graph $G$ where loops and multiple edges are allowed. A path {$e\_1, e\_2, ..., e\_k$} (a sequence of edges) has a cost $$ cost = e\_1 | e\_2 |...|e\_k$$ where $|$ is the bitwise OR.

Assume for all edges in $G$, $e\_i \ge 0$.

Now, the triangle inequality is satisfied, for this definition of cost. Meaning, as the path size increases, the path cost can never decrease.

So theoretically, to find the shortest between two vertices, Dijkstra's algorithm should give the right answer?

# Answer
> 6 votes
I'm not sure if you can adapt Dijkstra specifically in any way to this problem, but there's a different efficient solution that's actually easier to come up with.

Because bitwise operators treat bits independently, you can try to fix each bit in your answer, iteratively, from highest to lowest. The first question is "can I *not* have the highest bit set to 1 in my answer?". If after removing all edges with the highest bit set to 1 from the graph, the source and destination are still connected, the answer is yes, you throw away all those edges for good and proceed with the next bit. If the answer is no, you put the removed edges back, because they might come in handy, and again proceed with the next bit.

Running time is $O(Elog MaxCost)$.

# Answer
> 4 votes
Nice question indeed! Very interesting!!

First, let me please summarize my understanding of your problem:

**Definition** Let $\omega(\pi)$ denote the cost of a path $\pi\langle n\_1, n\_2, n\_3, \ldots n\_k\rangle$ which is defined as $c(n\_1, n\_2)|\omega(\pi')$, $\pi'$ is the suffix path $\langle n\_2, n\_3, \ldots, n\_k\rangle$, $c(n\_1,n\_2)$ is the cost of the edge $\langle n\_1, n\_2\rangle$, and | is the bitwise or operator.

**Goal** To find a path $\pi^\*$ from a source vertex $s$ to a target vertex $t$ such that $\omega(\pi^\*)$ is minimized among all paths from $s$ to $t$.

Notice that $\omega(\cdot)$ is defined over the set of natural numbers $\mathbb{N}$. Indeed, if every vertex is characterized with $b$ bits, then the cost function takes values in the range $\[0, 2^b-1\]$.

Let me additionally highlight a couple of issues before going any further:

1. Your definition of *triangle inequality* is not very relevant to this case. *Triangle inequality* is used often in relation with the behaviour of *heuristics*. You might instead want to mean that costs grow monotonically and, as you are interested in minimizing the cost, this notion has been recently denoted as *monotonicity of state spaces* by Roni Stern et al.
2. A preferred way to verify theoretically whether Dijkstra/A$^\*$ can be applied or not is to check if you are using a cost algebra or not as defined by Stefan Edelkamp et al..

Regarding the second point, if a cost distribution model satisfies a cost algebra then we know that Dijkstra/A$^\*$ can be readily applied. This does not mean, however, that cost models which do not verify some properties of cost algebras can not be solved with the same algorithms ---or slightly modified versions of these algorithms.

Finally, note that you have not mentioned whether paths have to be simple or not so I will not address that issue here.

If my understanding is correct then, the cost of each edge is *state-dependent*: different paths to the same vertex have different costs, i.e. **the cost of an edge is** not a function of the out and in vertices connected through the edge (e.g., if vertices are locations over a map, then the edge cost is just the distance between them and this is a function just of the origin and target vertices of the edge), but **a function of all states traversed before taking the edge**!! This makes a huge difference with typical problems so that let me go deeper into this issue.

Consider the following simple digraph (i.e., no loops, no multiple edges are required to show the main difficulty in this problem):

where it is required to find the shortest path from 000 (in blue) to 100 (in red). Let us see how Dijkstra would work here:

1. s is expanded and $n\_1$ and $n\_2$ are inserted into OPEN in ascending order of their cost: $f(n\_1)= 001 (1)$ whereas $f(n\_2) = 110 (6)$, so that $n\_1$ goes first and $n\_2$ is inserted second. $n\_1$ is inserted into CLOSED.
2. $n\_1$ is expanded and $n\_3$ is generated with a cost equal to $f (n\_3) = 001 | 010 = 011 (3)$. Still, $n\_2$ is second as $n\_3$ is inserted before it. $n\_1$ is inserted into CLOSED.
3. $n\_3$ is expanded and the goal $t$ is generated with a cost equal to $f (t) = 011 | 100 = 111 (7)$. Hence, the goal is inserted into OPEN *after* $n\_2$. **$n\_3$ is inserted into CLOSED**
4. Now, $n\_2$ is expanded and $n\_3$ is generated with a cost equal to $f (n\_3) = 110 | 010 = 110 (6)$ which is lower than the cost of the next node in OPEN (the goal, with a cost equal to 7). Hence, $n\_3$ is re-inserted into OPEN with a cost equal to 6.
5. Phew! You might be thinking that $n\_2$ gets a chance to discover a cheapest path to the goal. Unfortunately not!! Point is that $n\_3$ is found in CLOSED and hence, it is immediately discarded!
6. The next node in OPEN is the goal with a cost equal to 7.

Dijkstra halts with the solution $\langle s, n\_1, n\_3, t\rangle$ which is incorrect as it has a cost equal to 7 units, whereas the path $\langle s, n\_2, n\_3, t\rangle$ has a lower cost, 6 units.

In the Figure above, thick vertices ($n\_1$, $n\_3$ and $t$) represent the *problematic* vertices: it can be easily verified that the bitwise OR of the involved costs equals 111 and, moreover, they are laid out in increasing order of cost so that there is no way for Dijkstra to foresee the trap until it is too late.

Fixing the problem does not seem easy. A simple way consists of getting rid of CLOSED and let Dijkstra just enumerate all paths in increasing order of their $f$-value. Note however that the number of paths can grow exponentially and hence this might be impractical. It is my feeling that there should be better ways than just running this modified version of Dijkstra.

Hope this helps,

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Fitness functions for low-dimensional parts of cooperative coevolution algorithms
In cooperative coevolution algorithms, a high dimensional vector is broken into smaller vectors, each of which is optimized separately using EAs for fewer dimensions and then recombined.

What is the fitness function used to optimize those? It can't be the same benchmark function, as those are for higher dimensions.

I am specifically talking with respect to the algorithm DECC-G (*"Large Scale Evolutionary Optimization Using Cooperative Coevolution"* by Z. Yang, K. Tang, X. Yao). What is the fitness function used to optimize `subpop` in SaNSDE and `wpop` in DE?

# Answer
> 2 votes
Every sub-vector is evaluated by concatenating it with the best-fit individuals (sub-vectors) from the rest of the sub-populations to form a so called *context vector*.

The *context vector* contains all the parameters required by the benchmark function and is fed into it for fitness evaluation.

This is actually where the cooperation happens.

DECC-G is "just" a cooperative co-evolutionary (*CC*) scheme based on Differential Evolution (*DE*) and a random split/grouping of the vectors/individuals (*-G*).

It shares with the other co-evolutionary algorithms the general architecture:

*(Coevolutionary model of three species shown from the perspective of each in turn. Image from Cooperative Coevolution: An Architecture for Evolving Coadapted Subcomponents by Mitchell A. Potter, Kenneth A. De Jong)*

---

As a side note the reference implementation of DECC-G can be found here.

---
Tags: algorithms, optimization, genetic-algorithms
---


# Question
Title: When reducing from HALT, can you create a Turing machine that asks whether a simulation stops?
Lets say I am doing a reduction from $\mathrm{HALT}\_{\mathrm{TM}}$ to another language $S$, in order to prove that $S$ is not decidable. For this I need to build a new Turing machine, $M'$. Can I create $M'$ in such a way that the next step is depended upon whether or not a simulation stops? Take the following two examples:

$M' = $ "on input $M, w$:

1. Simulate $M$ on input $w$. If $M$ stops, go to step 2. Else: go to step 3.
2. ....
3. ....."

And

$M'' = $ "on input $M, w$:

1. ...
2. Run $M$ on input $w$.
3. accept."

The first one requires the decider for $S$ to solve $\mathrm{HALT}\_{\mathrm{TM}}$ more explicitly then the second one. Is the first one wrong?

# Answer
> 5 votes
No, you can't.

First, as a technical point, it never makes sense to say "If this simulation halts", since that would require doing the whole simulation and, if it doesn't halt, you'd never finish simulating it. You can, in certain circumstances, ask whether a particular Turing machine halts on a particular input, but that's something subtly different.

But the main point is that your reduction looks backwards. You're supposed to be using the argument "$S$ must be undecidable because I could use the ability to decide $S$ to let me decide the halting problem, which is impossible." But, by basing decisions on whether some Turing machine halts or not, you're assuming that you can determine this, i.e., assuming that you can already decide the halting problem.

---
Tags: computability, reductions, proof-techniques, halting-problem
---


title: Cluster Edge Deletion on 2-trees

text:
# Question
Title: Cluster Edge Deletion on 2-trees
**Definitions:** Cluster Edge Deletion problem is a graph modification problem, in which we want to remove the minimum number of edges such that the resulting graph does not contain a $P\_3$ as an induced subgraph (that is, the resulting graph is a disjoin union of cliques).

The class of $k$-trees is defined as follows: a complete graph with $k$ vertices is a $k$-tree; a $k$-trees with $n + 1$ vertices $(n \> k)$ can be constructed from a $k$-tree $T$ with $n$ vertices by adding a vertex adjacent to all vertices of a $k$-clique of $T$, and only to these vertices.

**Question:** Does exist a polynomial-time algorithm to solve Cluster Edge Deletion on 2-trees?

**My idea:** Let $G$ be the 2-tree. I transform $G$ to a new graph $G'$ where, each node of $G'$ represents a $K\_3$ in $G$. And two nodes of $G'$ are adjacent if and only if their corresponding $K\_3$ share a common vertex in $G$.

Let $M$ be the resulting graph after removing the minimum edges from $G$. I think that if always exist some graph $M$ contains a 3-clique $H$ which has a node with minimum degree in $G'$, then I can solve this problem on $G \backslash H$.

For example as below figure, I choose node $x$ with minimum degree 3 in $G'$, and after remove all vertices of clique $\\{f,g,e\\}$ in $G$, I got an union disjoint of two clique $\\{f,g,e\\}$ and $\\{b,c,d\\}$ in $G$.

# Answer
Let me first formalize the problem:

> **Cluster edition**
>
> *Instance:* A graph $G$ and an integer $k$.
>
> *Question:* Can $G$ be transformed into a cluster graph by deleting at most $k$ edges?

It is not difficult to see that the problem is, already for general graphs, fixed-parameter tractable (FPT) parameterized by the number of edge deletions $k$. Being FPT means the problem is solvable in time $f(k) n^{O(1)}$, where $f$ is a computable function depending solely on $k$.

The observation is the following: cluster graphs are precisely the $P\_3$-free graphs, i.e., the graphs that don't contain the path on 3 vertices as an induced subgraph. So, in order to produce a cluster from $G$, the $k$ edge deletions must "hit" each $P\_3$. Clearly, there are two ways to destroy a $P\_3$: either we remove edge $a$ or edge $b$. The algorithm is as follows: as long as there is a $P\_3$, branch by choosing either one of its edges to delete. This will give you a straightforward $2^k n^{O(1)}$-time algorithm, that will be quite practical if $k$ is not too large.

Looking up the literature, the problem can be solved in $O^\*(1.77^k)$ time by a more clever yet simple branching algorithm (see Gramm et al. \[1\]). Here the $O^\*$ notation hides polynomially bounded factors.

It is interesting to ask whether you can do better for chordal graphs, or indeed $q$-trees (I'm using $q$ here to make a distinction between $k$). The problem is solvable in polynomial-time for cographs \[2\], but NP-complete for chordal graphs \[3\]. I don't know if the complexity for $q$-trees is known, and I also didn't think hard about it but merely glanced the literature.

---

\[1\] Gramm, Jens, Jiong Guo, Falk Hüffner, and Rolf Niedermeier. "Graph-modeled data clustering: Fixed-parameter algorithms for clique generation." In Italian Conference on Algorithms and Complexity, pp. 108-119. Springer Berlin Heidelberg, 2003.

\[2\] Gao, Yong, Donovan R. Hare, and James Nastos. "The cluster deletion problem for cographs." Discrete Mathematics 313, no. 23 (2013): 2763-2771.

\[3\] Bonomo, Flavia, Guillermo Duran, and Mario Valencia-Pabon. "Complexity of the cluster deletion problem on subclasses of chordal graphs." Theoretical Computer Science 600 (2015): 59-69.
> 3 votes

---
Tags: algorithms, graphs, clustering
---


# Question
Title: What would NP-complete solution in O(2^N/B) mean?
Suppose we had an algorithm that solved an **NP**-complete problem (SAT, TSP, etc.) in time $O(2^{N/B})$ where $B\>2$ is an input to the algorithm, along with the instance to be solved.

So for $B \< N$, we have a reduced exponential growth runtime, but for $B \geq N$ we actually have a constant runtime.

What would this say about **P** vs **NP**? Does this complexity class already exist or would it be a new one? Would this add anything significant to our current understanding of complexity theory?

# Answer
> 6 votes
It says nothing about the **P** vs **NP** question because no such algorithm can exist. If there is an algorithm that takes as its input a formula $\phi$ and an integer $B$ and determines whether $\phi$ is satisfiable in time $O(2^{N/B})$, where $N$ is the length of $\phi$, then we can decide SAT in constant time by calling the algorithm with $B=N$.

But we know that SAT cannot be solved in constant time because, in $k$ steps of the computation, you can only read the first $k$ characters of the input. That means that you have no way of distinguishing between the formulas $X\land X\land\dots \land X$ and $X\land X\land\dots \land X\land\neg X$, where $X$ is repeated, say, $k$ times. One of these formulas is satisfiable and the other isn't, but an algorithm running in $k$ steps would have to return "satisfiable" or "unsatisfiable" before seeing the $\neg X$ (or lack of it) at the end.

# Answer
> 0 votes
So, basically, you're asking about a hypothetical $O((1+\epsilon)^N)$ 3-SAT algorithm where $\epsilon$ can be as small as desired. (Because $2^{\frac{N}{B}} = (2^{\frac{1}{B}})^N = (1+\epsilon)^N$ via setting $\epsilon$ to $1-2^\frac{1}{B}$.)

Such an algorithm wouldn't resolve the $\text{P} =^? \text{NP}$ problem. It doesn't solve 3SAT in polynomial time, and it doesn't demonstrate that no algorithm can solve 3SAT in polynomial time.

However, it would disprove the exponential time hypothesis, which conjectures that 3SAT costs at least $2^{\Omega(n)}$ (i.e. $\Omega((1+c)^{n})$ for some constant $c \> 0$). It would be a big deal.

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


title: Finding odd directed circuit

text:
# Question
Title: Finding odd directed circuit
I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph.

Can anyone help me how to proceed with this problem???

# Answer
Firstly:

> König's Theorem (1936): A graph is 2-colorable iff it has no circuits of odd length.
>
> www-math.ucdenver.edu

Also:

> * A graph is bipartite if and only if it does not contain an odd cycle.
> * A graph is bipartite if and only if it is 2-colorable, (i.e. its chromatic number is less than or equal to 2).
>
> wikipedia

So we see we are looking for a 2-colorable graph, or a bipartite graph. These are all the same thing.

**Edit:**

> A digraph has an odd-length directed cycle if and only if one (or more) of its strong components is nonbipartite (when treated as an undirected graph).
>
> algs4.cs.princeton.edu

Since your graph is strongly connected, we can treat it as an undirected graph and test for bipartiteness using the regular testing algorithms.

The wikipedia article gives an example algorithm to test bipartiteness using *Breadth First Search*. A presentation explaining the algorithm is available from The University of Maryland website.
> 9 votes

# Answer
A strongly connected digraph is bipartite if and only if it has no directed cycle of odd length. (See Digrpah thm 2.2.1)

So you can decompose your digraph into strongly connected components (SCC). And for each SCC, run a depth-first-search to see if it is bipartite. If all SCCs are bipartite, then the whole digraph has no cycle of odd length. Otherwise it has one such cycle. This is a linear time algorithm.
> 1 votes

---
Tags: algorithms, graphs
---


title: A max-even subset problem

text:
# Question
Title: A max-even subset problem
I want to know if there is any polynomial algorithm for the problem, or any NP-completeness result.

* Given a set $S$ and $m$ subsets $C\_1, \dots, C\_m$ of $S$, we want to find a non-empty set $X\subseteq S$ such that $|X\cap C\_i|$ is even for as many $i$ as possible.

We can see this problem in another way: given $m$ $\\{0,1\\}$-vectors of size $n$, find a vector $X$ of size $n$ that has even inner product with the greatest possible number of the vectors.

# Answer
Your problem is:

Input: a $n \times n$ matrix $M$ of integers modulo 2
Goal: find a $n$-vector $x$ such that the Hamming weight of $Mx$ is as small as possible (with all arithmetic modulo 2)

This is the problem of finding a minimum-weight codeword for a linear code over $GF(2)$. This problem is NP-hard. See, e.g.,

Elwyn R. Berlekamp, Robert J. McEliece, and Henk C. A. van Tilborg. On the Inherent Intractability of Certain Coding Problems. IEEE Transactions on Information Theory 24 (1978), 384–386.

There are heuristics and algorithms that improve upon brute-force search, and algorithms that can work in polynomial time for certain special cases, but in the general case this is still hard if $n$ is large.
> 1 votes

---
Tags: algorithms, optimization, sets, linear-algebra, coding-theory
---


# Question
Title: Problems that are hard in the best case?
Are there any problems that are hard in the best case? In particular, I was wondering if there are problems that are NP-hard or #P-hard in the best case.

# Answer
To answer the question, one must first define what is meant by "best case".

One possible definition of "best case" complexity is, what is the running time for the best input? In other words, take the minimum over all instances, of the running time for that instance.

With that definition, there are no decision problems (problems with a yes/no answer) that are hard in the best case. That's because I could write a stupid algorithm that knows how to solve one particular problem instance efficiently (it has the solution for that instance hardcoded) and is slow on all else -- in the best case, this would be efficient.

For instance, consider 3-colorability problem, where given a graph we have to determine whether it is 3-colorable. Let's fix a single graph $G\_0$ that we know is 3-colorable. Now consider the following algorithm:

Algorithm:
Input: a graph $G$
1. If $G=G\_0$, output "Yes".
2. Otherwise, do something very slow to try to test whether $G$ is 3-colorable.

This algorithm is very slow in the worst case (and typical case), but it is fast in the best case: when the input is $G\_0$, it immediately outputs the correct answer. The existence of such an algorithm shows that 3-colorability is easy in the best case.

There was nothing special about 3-colorability that I used there. You can apply the same reasoning to any decision problem (or any problem where the output size is not too long).

---

In retrospect, that was probably the wrong definition. A better definition would be: for a fixed algorithm, let $T(n)$ denote the minimum over all instances *of size $n$*, of the running time of that instance. Then, the function $T(\cdot)$ is the best-case complexity of that algorithm (and of course we want to know the minimum over all algorithms, or a suitable lower bound that holds for all algorithms). This prevents hardcoding a single instance, because there will be a different best instance for each $n$. I don't know whether there are any problems that are hard, for this best-case complexity measure.

---

It's more interesting to look at average-case hardness. While many problems are hard in the worst case but easy on the average case, there *are* some problems that are both hard on the worst case and hard on the average case. One tool used to prove average-case hardness is random self-reducibility. For instance, the discrete log problem is believed to be hard on the average case. In particular, it is believed to be hard on the worst case, and we can prove that if it is worst-case hard, then it is average-case hard, too, using a random self-reduction.
> 5 votes

---
Tags: complexity-theory
---


# Question
Title: What is an example for a decidable language not in P?
I'm having trouble showing that $P\neq R$. Obviously $P\subseteq R$, but is there a decidable language which is definitely not (under all answers to open questions s.t. $P=NP$ or $NP=PSPACE$) in $P$ ?

# Answer
> 7 votes
Yes, there are decidable languages that are definitely not in **P**. The time hierarchy theorem says that **P$\\,\neq\\,$EXP**, so **P$\\,\neq\\,$R**, independently of the **P** vs **NP** problem. Any **EXP**-complete problem is definitely not in **P**: for example determining whether white has a winning strategy from a position in generalized chess ("generalized" in the sense of allowing a board of any dimensions, with any arrangement of any number of pieces, but otherwise following all the rules of standard chess).

---
Tags: complexity-theory, polynomial-time
---


# Question
Title: Is there a way to tell a picture has been resized?
I need to evaluate if the picture was resized (upscaled). Are there any approaches to that already? If not, what do you recommend me to start with?

# Answer
As Raphael already said, in general it's impossible.

There is the field of image forensics where people look for methods to detect tampering with images. For JPEG images for example, there is a paper about detecting resizing: A new approach for JPEG resize and image splicing detection.
> 2 votes

# Answer
On the conceptual level, the task is clearly impossible: you won't be able to detect size changes of mono-coloured images. Patterns with only right angles will always be identical modulo dimensions as well.

So you need assumptions on the image *and* knowledge about the specific algorithm used for upscaling. Something may be possible for specific combinations, but it's impossible to tell in general.
> 1 votes

---
Tags: algorithms, image-processing
---


# Question
Title: What is the compleixty of this algorithm?
The algorithm is as follows:

```
a = rand  % a random number between 0 and 1
b = a
while b == a
    b = rand
end

```

Here `rand` is a function that returns a random number, generated uniformly, between 0 and 1. Let us say that this is the MATLAB function rand.

What is the time complexity of this algorithm?

It looks like the best and average complexities are $O(1)$ and the worst complexity is unbounded.

# Answer
rand () is probably a random number generator, but the details are unknown. Since we don't know how exactly rand () behaves we don't know how long this will take.

I would assume that with many random number generators it is possible to prove that rand () will not be called more than three times (that is there is no state where rand () would return the same value three times in a row). Obviously if you use something like Mersenne Twister with thousands of bits of state, a rather lengthy sequence of identical numbers will happen in some states.
> 2 votes

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


# Question
Title: Where is the mistake in this apparently-O(n lg n) multiplication algorithm?
A recent puzzle blog post about finding three evenly spaced ones lead me to a stackoverflow question with a top answer that claims to do it in O(n lg n) time. The interesting part is that the solution involves squaring a polynomial, referencing a paper that describes how to do it in O(n lg n) time.

Now, multiplying polynomials is practically the same as multiplying numbers. The only real difference is the lack of carries. But... the carries can also be done in O(n lg n) time. For example:

```
    var value = 100; // = 0b1100100

    var inputBitCount = value.BitCount(); // 7 (because 2^7 > 100 >= 2^6)
    var n = inputBitCount * 2; // 14
    var lgn = n.BitCount(); // 4 (because 2^4 > 14 => 2^3)
    var c = lgn + 1; //5; enough space for 2n carries without overflowing

    // do apparently O(n log n) polynomial multiplication
    var p = ToPolynomialWhereBitsAreCoefficients(value); // x^6 + x^5 + x^2
    var p2 = SquarePolynomialInNLogNUsingFFT(p); // x^12 + 2x^11 + 2x^10 + x^8 + 2x^7 + x^4
    var s = CoefficientsOfPolynomial(p2); // [0,0,0,0,1,0,0,2,1,0,2,2,1]
    // note: s takes O(n lg n) space to store (each value requires at most c-1 bits)

    // propagate carries in O(n c) = O(n lg n) time
    for (var i = 0; i < n; i++)
        for (var j = 1; j < c; j++)
            if (s[i].Bit(j))
                s[i + j].IncrementInPlace();

    // extract bits of result (in little endian order)
    var r = new bool[n];
    for (var i = 0; i < n; i++)
        r[i] = s[i].Bit(0);

    // r encodes 0b10011100010000 = 10000

```

So my question is this: where's the mistake, here? Multiplying numbers in O(n lg n) is a gigantic open problem in computer science, and I really really doubt the answer would be this simple.

* Is the carrying wrong, or not O(n lg n)? I've worked out that lg n + 1 bits per value is enough to track the carries, and the algorithm is so simple I'd be surprised if it was wrong. Note that, although an individual increment can take O(lg n) time, the aggregate cost for x increments is O(x).
* Is the polynomial multiplication algorithm from the paper wrong, or have conditions that I'm violating? The paper uses a fast fourier transform instead of a number theoretic transform, which could be an issue.
* Have a lot of smart people missed an obvious variant of the Schönhage–Strassen algorithm for 40 years? This seems by far the least likely.

I've actually written code to implement this, except for the efficient polynomial multiplication (I don't understand the number theoretic transform well enough yet). Random testing appears to confirm the algorithm being correct, so the issue is likely in the time complexity analysis.

# Answer
Your algorithm is very similar to Schönhage–Strassen. In the FFT step, there are large numbers involved - as you mention, their size can be up to $O(\log n)$. Arithmetic on them doesn't come for free. You need to apply the construction recursively, and you'll lose something.
> 14 votes

# Answer
The "mistake" here is that a Fourier transform can be calculated in O (n log n) steps of adding or multiplying the numbers to be transformed, but as n grows really large, the numbers that are transformed get bigger as well, which adds another factor log log n.

In practice, I would think that using quad precision floating point (128 bit floating point using two double values) or 128 bit fixed point in the FFT would be enough for any product that is small enough to be calculated at all.
> 1 votes

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


# Question
Title: How can I efficiently find the optimal order to apply special offers to a shopping cart?
Given a list of items which represent items in a shopping cart, and a list of available special offers which replace one or more regular items to lower the cost of those items, how can I decide the order to apply the special offers to minimize the final basket price?

For example, I have in my cart 4 items:

* Coke \\$2
* Coke \\$2
* Sandwich \\$3
* Chocolate bar \\$1

Total: \\$8

There are two special offers in store:

* Buy one get one free coke (\\$2 saving).
* Coke, chocolate bar and a sandwich for \\$4.50 (\\$1.50 saving).

One method of determining the order offers are applied might be to sort them by the savings they give. After applying the offers using this method my cart now looks like this:

* Buy one get one free coke \\$2
* Sandwich \\$3
* Chocolate bar \\$1

Total: \\$6

There is no meal deal offer applied because after the Coke deal is applied there is not any coke items left to make a meal deal. This method of sorting by savings may seem to work, but there are cases in which it can fail, for example if the same deals were in place and my cart looked like this:

* Coke \\$2
* Sandwich \\$3
* Chocolate bar \\$1
* Coke \\$2
* Sandwich \\$3
* Chocolate bar \\$1

Total: \\$12

After deals are applied, the two Coke items are substituted for the promotional offer first (it being the deal with the greatest saving). There is no other applicable deal so the algorithm ends, reducing the basket price by \\$2. Obviously there is an error here because if two meal deals were applied before the coke deal, the price would have been reduced by $3.

The naive solution to this problem would be to enumerate each possible permutation of the list of special offers, and find the one that minimizes the basket total when applied. This would have a factorial runtime based on the number of special offers available.

Is it possible to improve on a factorial runtime and if not, are there any efficient approximate solutions?

# Answer
> 1 votes
Interesting problem. As noted, you can easily turn this into an integer programming problem. But if your numbers are small and nobody buys a warehouse full of goods an easy algorithm may work.

All you need to decide is how often each offer is applied. Sort the offers by percentage saved in descending order. Then an outer loop where the most saving offer is applied first as often as possible first descending. Then the second highest percentage saving etc. You reject a search path if it cannot be optimal.

In your example the first offer saves 50% and the second just 25%, so you would apply the first offer as often as possible,

It gets a bit more complicated if you accept offers where you deliver more than ordered. For example delivering an extra chocolate bar if it saves money

In your second example you would first try to apply the first deal once, then try again without it.

# Answer
> 0 votes
First, note that order does not matter. If it is possible to apply both offer 1 and offer 2, then it doesn't matter which order you apply them in: the result will be the same either way.

Probably the most pragmatic solution will be to use integer linear programming. Introduce a variable $x\_i$ to represent the number of times you apply offer $i$. Also, for each product $j$ in your initial order, have a variable $y\_j$ to represent the number of additional orders of project $j$ that are needed after you apply all the offers. You want to minimize $\sum\_i c\_i x\_i + \sum\_j c'\_j y\_j$, where $c\_i$ is the price for offer $i$ and $c'\_j$ is the price for product $j$. You have some linear equations, one for each product (to ensure that the total quantity of the final order matches the desired number), as well as the inequalities $x\_i \ge 0$, $y\_j \ge 0$. Now use an off-the-shelf integer linear programming (ILP) solver to find the best solution to that ILP instance.

ILP solvers implement a number of heuristics and techniques that are often effective at reducing the cost of finding a solution. Using an existing ILP solver will take a lot less time than trying to implement a custom algorithm just for your specific situation. And, if the number of products in your shopping cart is not too large, this approach might be efficient enough for practical purposes.

---
Tags: complexity-theory, optimization, combinatorics, knapsack-problems
---


title: ML function of type 'a -> 'b

text:
# Question
Title: ML function of type 'a -> 'b
Our professor asked us to think of a function in OCaml that has the type

```
'a -> 'b

```

i.e. a function of one argument that could be anything, and that can return a different anything.

I thought of using `raise` in a function that ignores its argument:

```
let f x = raise Exit

```

But the professor said there was a solution that doesn't require any function in the standard library. I'm confused: how can you make a `'b` if you don't have one in the first place?

<sub> I'm asking here rather than on Stack Overflow because I want to understand what's going on, I don't want to just see a program with no explanation. </sub>

# Answer
The skeleton is `let f x = BODY`. In BODY you must use x only in generic ways (for example, don't send it to a function that expects integers), and you must return a value of *any* other type. But how can the latter part be true? The only way to satisfy the statement "for all types `'b`, the returned value is a value of type `'b`" is to make sure the function does *not* return. There are exactly two possibilities: either BODY faults or it doesn't terminate. The function `raise` faults, the following doesn't terminate:

```
let rec f x = f x

```
> 18 votes

# Answer
First, some remarks. Using only the core typed lambda calculus it's not possible to obtain `'a -> 'b` because the typing system is in correspondence (via the Curry Howard isomorphism) to intuitionistic logics, and the corresponding formula `A → B` is not a tautology.

Other extensions such as tuples and matchings/conditionals still preserve some logic consistency adding product types `*` which correspond to the logical connective *and*, and sum types `|` which correspond to the *or*. Again, don't expect them to produce that `'a -> 'b` type, as it would allow one to prove some formula which is not a tautology.

So your only chances are using other constructions which escape from the logics like `raise` (but you're not allowed to in this case)… or `let rec`! Recursion allows to build programs which never terminate, and their results can be given an arbitrary return type as they will never be produced. Now if you think about the most trivial non terminating function (the one which directly calls itself to return a result):

```
let rec f x = f x

```

You'll notice that its type is exactly `'a -> 'b`: whatever is the provided argument, the result (which will never be computed) can be assumed to have any type.

Of course this `f` is not an interesting function, but that's the point. In OCaml, any function whose type does not look like a valid formula is a suspicious function.
> 19 votes

# Answer
Using a compiler primitive you can write this:

```
external magic: 'a -> 'b = "%identity"

```

(and indeed the compiler distribution provides this, though isn't part of the language). This is an unsafe identity cast.

Your professor almost certainly doesn't want this. However, this is also the only *useful* function with type `'a -> 'b` that I am aware of, and indeed it is used in the OCaml distribution itself.
> 1 votes

---
Tags: programming-languages, typing, functional-programming
---


# Question
Title: Why doesn't subset sum solution violate Exponential Time Hypothesis?
The quickest algorithm for solving subset sum currently is $2^{n/2}$ (via Wiki). Why doesn't this violate the Exponential Time Hypothesis which states that “there is no family of algorithms that can solve 3-SAT in $2^{o(n)}$ time.”

Couldn't a 3-SAT problem be translated to a subset sum problem in polynomial time and then solved in $2^{n/2}$ time. What am I missing here?

# Answer
Given a 3SAT problem of size $n$, you can convert that to a subset sum problem of size $n^2$ (roughly). Now you can apply the algorithm for subset sum to solve the subset sum in time $2^{n^2/2}$ (roughly). Remember, the running time depends on the size (length) of the input, and here the size of the input will be $n^2$, yielding the $2^{n^2/2}$ figure.

That will give you an algorithm for solving a 3SAT problem of size $n$ in $2^{n^2/2}$ time (roughly). But that's much worse than the naive algorithm, which takes $2^n$ time: $2^n$ is much smaller than $2^{n^2/2}$. So this reduction does not contradict the exponential time hypothesis: it doesn't give you a way to solve 3SAT faster than $2^n$ time.
> 3 votes

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


# Question
Title: Is it okay to select the best performers of test cases for scientific publication in neural network machine learning
If I split my data properly into 75% train, 15% test, and 15% validation, and there are over 100,000 samples, is it appropriate for me to train 100s of neural networks then select only a couple based on their testing set grades for publication in a research article?

The question is for neural network training in which the random initialization of weights can drastically affect test grades. Network parameters like the number of neurons, number of layers, etc all can change how the testing grade is. These are all things that are easy to modify, rather than data preparation which can take a long time.

Do I need to resplit my data every time I train a new network? What strategy do most NN theorists use?

# Answer
No. You must use the test set *only once*. Otherwise your result will not be representative of the true performance of your scheme. That's bad.

Instead, use the validation set for checking the performance of your algorithm on different parameters, different initialization strategies, different architectures, etc. That's what the validation set is there for. Each time you have a new idea for a different approach, you train a model on the 75% training set, then evaluate how well it performs on the 15% validation set, and use that to determine what other changes you might want to try. Repeat as many times as you like -- but never use the test set for any of this. Don't re-split the data.

After you've finished all your experimentation, and are ready to commit to a single solution, *now* evaluate it on your test set, and publish whatever you get. (But the one thing you absolutely must avoid is, after seeing its performance on the test set, deciding to go make other changes and then re-evaluate on the test set a second time. Don't do that!)

Alternatively, you can pool the training + validation data into a single group, and use cross-validation on that as you test each variation. Again, don't use the test data until the very end, and use it only once.

This should be well-documented in a good reference on machine learning.
> 4 votes

---
Tags: neural-networks, statistics, research
---


title: Shorten Length Reduction

text:
# Question
Title: Shorten Length Reduction
I've stumbled upon this Question:

* We say that a reduction $f$ of a language $A$ to a language $B$ is a Shorten length reduction, if there exists a number $ n\in N $ s.t for every $ w\in A $, s.t if $ |w| \geq n \ than \ |f(w)| \< |w| $. Also, $A,B \notin \\{\Sigma^\*,\emptyset \\} $. Prove there is such a reduction which is also polynomial-time reduction from any languages $ A,B \in P $.
* This was my approach: Take $ w' $ to be the shortest word in $B$ and define $f(w) = w'$ for every $w \in A $. I'm pretty sure the idea is correct because we simply choose $n = |w'| + 1$ and then obviously for every $w \ s.t \ |w| \>= n \ we \ get \ |w| \> n-1 = |w'| = |f(w)| $

So my question is, can I really choose a word $ w' $ to be the shortest word in $B$?

Also, am I correct with my approach?

Thanks!

# Answer
> 0 votes
In order to prove your result, you don't need to give an algorithm that gets a description of $A$ and $B$ and outputs a description of $f$, a polytime shortening reduction from $A$ to $B$. It's enough to show that for each $A$ and $B$, such an $f$ exists. If a language $B$ is different from $\emptyset$ and $\Sigma^\*$ then there is some word $x \in B$ and some other word $y \notin B$, and these are enough to carry out your construction (you don't actually need them to be the shortest word).

---
Tags: complexity-theory, reductions, polynomial-time
---


# Question
Title: Converting pseudo code to a recurrence relation equation?
The following is pseudo code and I need to turn it into a a recurrence relation that would possibly have either an arithmetic, geometric or harmonic series.

Pseudo code is below.

I have so far T(n) = T(n-5) + c

# Answer
> 1 votes
> T(n) = T(n-5) + c

**Solution by substitution:**

$T(n) = T(n-5) + c..................................(1)$

therefore, $T(n-5) = T(n-10) + c ....................(2)$

Substituting $(2)$ in $(1)$, gives

$T(n) = T(n-10) + c + c .............................(3)$

Similarly, $T(n-10) = T(n-15) + c ....................(4)$

Substituting $(4)$ in $(3)$, gives

$T(n) = T(n-15) + c + c + c .........................(5)$

and so on.

Finally, $T(n) = T(k) + \frac{cn}{5}$ where $k\<=4$

then $T(n) = 1 + \frac{cn}{5}$

therefore $f(n)=O(n)$ as $\frac{c}{5}$ is a constant.

---
Tags: algorithm-analysis, asymptotics, recurrence-relation
---


# Question
Title: Project to nearest point in convex polytope
Is there a reasonably efficient algorithm for the following task?

Input: a point $x \in \mathbb{R}^d$; a convex polytope $\mathcal{C} \subseteq \mathbb{R}^d$
Find: a point $y \in \mathcal{C}$ that is as close to $x$ as possible

Assume that $\mathcal{C}$ is specified by a collection of linear inequalities, that the dimension $d$ is fairly high, and "close" is measured using $L\_2$ distance, i.e., we want to minimize $||x-y||\_2$. is there an efficient algorithm for this problem?

---

I can see how to solve this in polynomial time using linear programming if "close" were measured using $L\_1$ or $L\_\infty$ distance, but I'm more interested in the $L\_2$ distance metric. I keep thinking there might be some algorithm based on identifying the set of inequalities that are violated by $x$ and then doing something, but I can't quite put together a working algorithm.

I found the following paper which describes an algorithm (exponential-time in the worst case but often efficient, like the simplex method):

Philip Wolfe. Finding the Nearest Point in a Polytope. Mathematical Programming, vol 11, 1976, pp.128--149.

However, that paper requires $\mathcal{C}$ to be presented as a list of vertices rather than a list of inequalities, so it can't be used for my problem. (Converting from inequalities to a set of vertices will cause an exponential blowup; typically the number of vertices is exponential in the number of inequalities.)

# Answer
> 8 votes
A quadratic program is an optimization problem where the goal is to minimize $y^T Q y + c^T y$ subject to $A y \leq b$. If $Q$ is positive definite, then this is a convex quadratic program and we can solve this problem in polynomial time using several methods, one being the ellipsoid method (originally due to Kozlov, Tarasov and Khachiyan \[1\]).

We can write $\\|y - x\\|\_2^2$ as $y^Ty - 2x^Ty + x^Tx$. Thus an equivalent problem is $$ \min\_y\ (y^Ty - 2x^Ty) \text{ such that } A y\leq b. $$ This is a convex quadratic program, since in this case $Q$ is the identity matrix, which is positive definite.

\[1\] *The polynomial solvability of quadratic programming*, USSR Computational Mathematics and Mathematical Physics, 20(5):223–228, 1980; Science Direct

---
Tags: algorithms, optimization, linear-programming, numerical-algorithms
---