# Question
Title: Would adding recursive named functions to Simply typed lambda calculus make it Turing complete?
Say I have Simply typed lambda calculus, and add an assignment rule:

```
<identifier> : <type> = <abstraction>

```

Where `<identifier>` is the name of the function, `<type>` is the function type and `<abstraction>` is the abstraction to be assigned to the identifier.

Then I add a typing rule that says that when you see an assignment such as the above, you use a temporary type context, in which the declared type (the one in `<identifier> : <type>`) is associated with the identifier, to type check `<abstraction>` and then make sure the declared type equals the abstraction's type.

And finally I add another rule that would let me have a list of assignments on top of a lambda term which is the one I'd evaluate, such that all these assignments would be added to the global scope before the term is evaluated.

Seems to me that this alone would make it Turing complete since I'd be able to do stuff like:

```
stackoverflow: NUM -> NUM = λn:NUM.(stackoverflow n)
(stackoverflow 0)

```

And at the same time, everything I can define in this language would be "well typed" in the sense that it wouldn't be able to define infinite types (I wouldn't be able to define the Y combinator).

So my questions are, is this really Turing complete? And, am I missing something when I say everything would be "well typed" (like for instance, I could define the Y combinator in a way I haven't yet realized or is there any gotcha in this type system)?

# Answer
> 6 votes
If all you have this definition rule (which doesn't perform any computation), it won't help you. You also need a way to use this definition, like you did in your code example: you implicitly used another language construct, where a definition is available in the next line.

To make things precise, I'll consider a construct which combines a definition with a way to use that definition — a “let … in …” construct (a recursive one, since the function is available while you're defining it).

$$\frac{ \Gamma, f \colon T \vdash M : T \qquad \Gamma, f \colon T \vdash N : T' \qquad }{ \Gamma \vdash (\mathtt{let\\:} f \colon T = M \mathtt{\\:in\\:} N) : T' }$$

From a typing perspective, it doesn't matter whether $T$ is a function type or whether $M$ is an abstraction. These restrictions would ensure that you can find a nice execution semantics (the general rule like phrased above allows recursive definitions like `let x : int = x + 1 in x` which cannot be usefully evaluated, but you can always define such cases as looping forever).

With this language construct, you do have a Turing-complete language, and you can define a fixpoint combinator (even with the abstraction restriction).

```
let Y : (int→int)→(int→int)  = λg. g (Y g) in …

```

$Y$ is a fixpoint combinator over the integers. You can make a similar definition at any type.

You can't make a *polymorphic* fixpoint combinator. This restriction comes with the simply typed lambda calculus. If you added polymorphism (which in itself does not allow recursive functions, for example System F is normalizing), you could get a polymorphic fixpoint combinator with a suitably generalized recursive let construct.

---
Tags: lambda-calculus, recursion, type-theory, turing-completeness, typing
---


# Question
Title: Why do they say `A, B, C, ... implies M` instead of `A∧B∧ C∧ ... implies M`?
The conclusion follows from all the premises. It seems to me that this means that conclusion from the conjuntion of the premises. Right? Why does logic uses comma instead?

# Answer
> 6 votes
It's a distinction between language and metalanguage.

$A, B \vdash M$ says: if I have both $A$ and $B$ amongst my hypotheses, then I can deduce $M$.
$A \wedge B \vdash M$ says: if I have $A \wedge B$ amongst my hypotheses, then I can deduce $M$.
The fact that the two are equivalent comes from the definition of the operator $\wedge$.

I could define a new operator $?$ with these deduction rules (using the sequent calculus formulation): $$ \frac{A \vdash M}{A ? B \vdash M} \qquad \frac{B \vdash M}{A ? B \vdash M} \qquad \frac{\vdash A, M \quad \vdash B,M}{\vdash A?B,M} $$

This new operator has the same rules as $\wedge$ (in the sequent calculus), so I could substitute $?$ and $\wedge$ in a true judgement and still get a true judgement, and vice versa. Nonetheless, they are syntactically speaking two different propositions.

It takes a while to internalize the difference between the language and the metalanguage, especially in the beginning when you only study a logic which models our everyday reasoning. There are logics such as intuitionistic logic and linear logic which diverge further, and while these logics (especially linear logic) are more advanced, they are in some ways easier to handle because there is a clearer separation between the logic and the meta-logic.

I'll briefly discuss “and” in linear logic, to illustrate this point. To put it in a nutshell, in everyday logic, if you have a hypothesis, you can use it at multiple points in a proof. In linear logic, a hypothesis can only be used once, unless it's marked as reusable. Linear logic can thus model processes that aren't proofs as you think of them, but more physical processes, such as “if I have a cake before eating it, then I have no cake after eating it”. Linear logic has two conjunction operators. Both say: if I have a process that produces an $A$, and I have a process that produces a $B$, then I have a process that produces an $A$ “and” a $B$. They differ in how the processes are combined:

* Multiplicative conjunction puts the two processes next to each other: given $\vdash \Gamma, A$ and $\vdash \Delta, B$ (a process that produces an $A$ and some more stuff, and a process that produces an $B$ and some more stuff), I can combine them to make $A \otimes B$ and the combined output of the two processes: $\vdash \Gamma, \Delta, A \otimes B$. For example, if I make a plate of spaghetti and an apple pie, I can eat a plate of spaghetti and an apple pie.
* Additive conjunction runs the two processes together: given $\vdash \Gamma, A$ and $\vdash \Gamma, B$ (I can run the process and produce $\Gamma$ plus either $A$ or $B$), I can run that same process and produce both: $\vdash \Gamma, A \\& B$. For example, if I can spend \\$10 to get a plate of spaghetti or I can spend \\$10 to get an apple pie, then \\$10 gets me the choice of spaghetti or pie (but it doesn't get me $A \otimes B$, where I have both spaghetti and pie).

---
Tags: logic
---


# Question
Title: How to evaluate the accuracy of a method for the extraction of the principal lines of the palmprint
Let's assume that I've implemented a method for the extraction of the principal lines of the palmprint. For instance, let's say that I'm able to do a transformation like the following one (image from Patprapa Tunkpien, Sasipa Panduwadeethorn and Suphakant Phimoltares):

Now, I want to make an evaluation of the accuracy level of my algorithm. In order to do this, I have only the algorithm, and a big set of palmprint images (on which I can execute the extraction procedure to obtain the corresponding set of binary images of principal lines of the palmprint).

How can I evaluate the accuracy level of my algorithm, without having any kind of reference extraction method?

# Answer
> 1 votes
To understand how to evaluate the accuracy of your algorithm, the best way will be to understand how the result of your algorithm will be used.

It is likely that your algorithm is just a component in a system. After all, it's not like being able to visualize the right-hand picture is somehow a useful and important goal in its own right. Rather, it is likely a useful stepping stone along the way to some more meaningful goal.

For instance, maybe you want to do biometric authentication of the individual, and you are planning to use the palm print for authentication, so it is helpful to first extract the three principle lines of the palm. In that case, you will probably take the result of your transformation and then feed it in as input to the next step of processing; ultimately, the final answer of the authentication process will be "yes, accept this is the right person" or "no, this is not the right person". So, in this example, the ultimate goal is authentication. Therefore, I would suggest that the way to evaluate your algorithm is to evaluate how well the palmprint authentication process works, when it uses your algorithm. We could ask about the false accept rate (if an imposter tries to authenticate, what is the probability he/she is wrongly accepted?) and the false reject rate (if the legitimate individual tries to authenticate, what is the probability he/she is wrongly rejected?). Those are two useful metrics for evaluating the accuracy of biometric authentication, so you could evaluate how accurate the process is when using your particular transformation as one of the stages.

In general, a useful way to evaluate accuracy is to look at how the output of your transformation will be used, find some metric that is meaningful and relevant to that particular application, and then measure that metric when we use the output of your transformation as input to the next stage of processing. Of course, this does mean that we cannot evaluate your transformation in isolation -- but you know what? In some sense, that might be unavoidable.

---

There *is* another option, but it will require more work, and may yield results that are harder to interpret. You could hand-label each of the input images with a manually drawn line for each of the three principle lines. Call this the "golden reference" lines.

Then, you could manually or automatically process the output of your transformation to get the three lines (by extracting the center of each of the three broad brush strokes we can see in your right-hand image). Call these the "algorithmically inferred" lines.

Next, you could define some metric for the distance between the golden reference lines and the algorithmically inferred lines: for instance, maybe the average distance, or the root-mean-square distance. Finally, you could evaluate your algorithm on a reasonable test set, using this metric to quantify how close your lines are to the golden reference lines.

The problem with this approach is that it is harder to make sense of the results of such an accuracy metric. How do you tell when your algorithm is "good enough"? Beats me. The only way to know that is to look at how the output of your algorithm will be used -- which gets us back to my original suggestion of evaluating your algorithm as part of a larger system.

---
Tags: algorithms, algorithm-analysis, image-processing
---


# Question
Title: What is this algorithm? Create a tree's equivalent hierarchical network
This question was originally posted here: https://stackoverflow.com/q/20735339/2305618

I am surely not the first to have implemented code to perform the following graph transformation. But try as I might, I can't find a previous reference to it.

The transformation arises when creating a single graph that simultaneously models hierarchical inclusion relationships and other pairwise relationships between nodes.

The algorithm transforms a rooted directed tree DAG into an equivalent hierarchical network DAG. Equivalence in this sense - if the meaning of the tree structure is that parents 'consist of' or 'contain' their children the equivalent network structure would carry the same 'consisting of' or 'containment' information.

The tree hierarchy is represented in the network as sub-networks and sub-sub-networks. The tree's exterior nodes are copied across and each interior node X is represented by the pair: X' and X''

Does anyone know the name/reference of this transformation/ algorithm? :-)

Illustration image of this transformation:

Thanks

David

# Answer
Your question contains the implicit assumption/premise that this transformation has a name. I don't know why you would expect it to have a special name. The transformation is not anything special or complicated and as far as I know it does not have any special name. It appears that you are just taking a tree, and making a second copy of it (with all edges reversed; with all nodes cloned), and then just gluing the two copies together (identifying both copies of each leaf).

For future reference, I don't think questions like "please tell me if this function has a special name" are a good fit for this site. This site is for technical questions that admit an objectively evaluable answer and that relate to a real problem you have. How do you expect to evaluate an answer that says "No, it doesn't have a special name"? There is no reference one can cite to back up that answer, and no objectively verifiable evidence one can provide to support such an answer. Moreover, questions about naming aren't a very good fit. How will knowing whether there is a special name help you solve a real problem? (If you were thinking "it might help me find references that help me solve problem X", then you would be better off by just describing problem X.)
> 1 votes

---
Tags: algorithms, graphs, trees
---


title: A doubt in Ladner's Proof

text:
# Question
Title: A doubt in Ladner's Proof
I got stuck in Ladner's Proof while reading "Computational Complexity: A Modern Approach" by Sanjeev Arora and Boaz Barak. Pardon me if I'm missing something really obvious here but the authors do the following:

For every function $H\colon\mathbb{N}\to\mathbb{N}$ define

$$SAT\_H=\\{\psi01^{n^{H(n)}}: \psi \in SAT \ and \ n=|\psi|\\}$$

Now $H$ is defined as follows:

$H(n)$ is the smallest number $i\<\log \log n$ such that for every $x\in\\{0,1\\}^\*$ with $|x|\le \log n$, $M\_i$ (TM encoded by binary representation of $i$) outputs $SAT\_H (x)$ within $i|x|^i$ steps. If there is no such number $i$ then $H(n)=\log \log n$.

$M\_i$ outputs $SAT\_H (x)$ is equivalent to the statement that: The machine $M\_i$ on an input $x$ outputs a 1 $\iff$ $x \in SAT\_H$.

My question is: By definition of $SAT\_H$, every string in it will have length exactly $n+1+n^{H(n)}$.

For every string $x\in\\{0,1\\}^\*$ with $|x|\le \log n$, we note that $|x|\<n+1+n^{H(n)}$. So there does not exist any string $x\in\\{0,1\\}^\*$ with $|x|\le \log n$ and $x \in SAT\_H$.

This would mean that the machine $M\_i$ should trivially output 0 for every string $x\in\\{0,1\\}^\*$ with $|x|\le \log n$. But then how would such an argument be used for a proof? Where exactly am I going wrong?

# Answer
Every string in $SAT\_H$ has length $m+1+m^{H(m)}$ for some $m$. In particular, there will be strings of length at most $\log n$ whenever $m+1+m^{H(m)} \leq \log n$. For some reason you insist that $m$ equal $n$. Perhaps you should consider the following equivalent definition of $SAT\_H$: $$SAT\_H = \\{\psi01^{|\psi|^{H(|\psi|)}} : \psi \in SAT\\}. $$ There is, however, a subtle point: the definition of $H(n)$ relies on the set $SAT\_H$, whose definition in turn relies on the definition of $H(n)$ in what seems to be a circular fashion! However, if you work out the details you see that $H(n)$ relies on those parts of $SAT\_H$ which depend on $H(m)$ for much smaller $m$. Indeed, we need to know the members of $SAT\_H$ of size at most $\log n$. Each such member comes from a $\psi$ of size $m+1+m^{H(m)} \leq \log n$, and in particular $m \leq \log n$. So we only need to know the value of $H$ on the much smaller values up to $\log n$.
> 2 votes

---
Tags: complexity-theory
---


title: Find least probable path in graph

text:
# Question
Title: Find least probable path in graph
I am working on a special case of the longest path problem. For a cyclic directed graph $G=(V, E)$, where the edge-weights are probability values (i.e., $P(\\\_) = w(s, q)$ with $s,q \in V$), my aim is to find the least 'probable' path between two vertices.

My initial approach is to generate an graph $G'$ where the weights are the complementary probabilities $1- w(s, q)$ (with strictly positive values), and compute Dijkstra's shortest path on $G'$. Is this reasoning sound? Or am I getting myself into an NP-hard disaster?

# Answer
Your approach doesn't work. Presumably, you want to define the probability of a path to be the product of the probabilities on its edges. It sounds like you want to define the weight $w(e)$ on an edge $e$ to be $w(e)=1-p(e)$ (one minus its probability). However, doesn't work. It doesn't do what you want: you want $w(e)+w(e')$ to correspond to $p(e) \times p(e')$, but it doesn't.

Instead, you should be taking logarithms. In particular, you should define the weight on edge $e$ by $w(e) = -\log p(e)$. Now addition of weights corresponds to multiplication of probabilities:

$$w(e) + w(e') = -(\log p(e) + \log p(e')) = - \log(p(e) \times p(e')),$$

as desired. At this point all of the weights in $G'$ will be non-negative (do you see why?), so you can use Dijkstra's algorithm to find the shortest path in $G'$, and that will correspond to the path in $G$ with highest probability. As you can see, this is not a longest-path problem at all; it is just a straightforward shortest-paths problem.

The trick of taking logs to turn multiplication into addition is a standard one, including in many applications of graphs, so this is worth knowing.
> 3 votes

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


title: Class P is closed under rotation?

text:
# Question
Title: Class P is closed under rotation?
Is the complexity class $P$ closed under rotation, where rotation is defined as $\text{rot}(L) = \\{ wv \mid vw \in L \\}$? How would we prove it?

# Answer
> 5 votes
Yes. Suppose that $L \in P$, then $x \in rot(L)$ if and only if there exist $u,v$ such that $x = uv$ and $vu \in L$.

A simple polynomial time algorithm for deciding membership in $rot(L)$ is: given the input $x =x\_1 x\_2 ... x\_n$ generate the $n$ rotated strings $x\_1 x\_2 .. x\_n,\\, x\_2 x\_3 .. x\_n x\_1,\ldots, x\_n x\_1 .. x\_{n-1}$ and check in polynomial time whether at least one of them belongs to $L$; in that case accept ($x \in rot(L)$) otherwise reject ($x \notin rot(L)$).

---
Tags: complexity-theory
---


title: Finding squares touching points

text:
# Question
Title: Finding squares touching points
I am looking for an algorithm to solve the following problem:

INPUT: a set of $n$ points in the plane, $(x\_1,y\_1),...,(x\_n,y\_n)$.

OUTPUT: a set of $n-1$ axis-parallel interior-disjoint squares, such that the boundary of each square contains at least two points. (\*)

Here is an example of input (left) and possible output (right) for $n=4$:

Efficiency is not a concern right now - the time complexity may be exponential in $n$ (since I will usually use this algorithm with small $n$'s).

My first thought was along the following lines:

1. For every pair of points, find a square that touches these two points.
2. In the resulting set of $n(n-1)/2$ squares, find a subset with $n-1$ squares that are interior-disjoint, or report that such a set does not exist.

The problem is that, for every two points, there may be infinitely many squares that touch them. For example, the points $(0,0)$ and $(10,7)$ are touched by any square with a side-length of 10 and lower-left corner in $0 \times \[-3,0\]$.

How would you approach this problem?

(\*) NOTE: I don't know whether such a set of $n-1$ squares always exists. I want to play with points in order to gain some intuition about this question and maybe find a counter-example.

# Answer
> 1 votes
For a given pair of points, suppose you know which sides of the square they touch, and they are not touching the same side (of course, there are only 12 possibilities for this); fix this information about what side each is on. For example, with your example of points at $(0,0)$ and $(10,7)$, say that we've decided that $(0,0)$ will be on the left (west) side of the square and $(10,7)$ will be on the right (east) side of the square.

It is true that there there can be infinitely many possible squares that touch those points at the given sides, as you explain in the question. However, you can always reduce this to looking at finitely many possibilities. In particular, I think it suffices to consider at most $2n$ candidate squares, out of this infinite set: the $n$ candidates whose bottom (south) side is at $y$-value $y\_1$, $y\_2$, ..., or $y\_n$, and the $n$ candidates whose top (north) side is at $y$-value $y\_1$, $y\_2$, ..., or $y\_n$. In other words, you can consider only cases where the lower-left corner is at one of the points

$$\\{(0,y\_i) : i \in \\{1,\dots,n\\} \wedge -3 \le y \le 0\\} \cup \\{(0,y\_i-10) : i \in \\{1,\dots,n\\} \wedge -3 \le y \le 0\\}.$$

Of course, any square that contains some other point in its interior can be immediately ruled out.

(I don't have a proof of this statement; this is just what my intuition suggests.)

I'm not quite sure what to do if both points are on the same side (e.g., they have the same $x$-value or the same $y$-value). Perhaps we can use a similar argument to argue that there are at most $(2n)^2$ candidate squares that must be considered, but I'm not sure.

This immediately suggests an exponential-time algorithm. At each step, you non-deterministically select a pair of points that aren't already covered by the existing set of rectangles. Now you're going to enumerate all candidate squares that touch those two points and non-deterministically select one such square. To help with this, enumerate all 12 or 16 possibilities for which side of the square each point is on, and non-deterministically select one. Next consider the $\le 2n$ candidates suggested by these possibilities, and non-deterministically select one. This gives you a square; add it to your collection, and go on to the next step. You can resolve the non-determinism using backtracking. This algorithm might work well enough to experiment with many collections of points and see if you can find a counterexample for your conjecture that it is always possible to find such a set of $n-1$ squares.

---
Tags: algorithms, computational-geometry
---


title: Complexity of (SAT to 3-SAT) Problem?

text:
# Question
Title: Complexity of (SAT to 3-SAT) Problem?
It is well known that any CNF formula can be transform in polynomial time into a 3-CNF formula by using new variables (see here). If using new variables is not allowed, it is not always possible (take for instance the single clause formula : $(x\_1 \lor x\_2 \lor x\_3 \lor x\_4)$).

Let define the (SAT to 3-SAT) problem : Given $F$, a CNF formula. Is it possible to transform $F$ into an equivalent 3-CNF defined *on the same variables* as $F$ ? - where "equivalent" means with the same set of models.

What is the complexity of this problem ?

**Edit** : It has been shown on cstheory that the problem is co-NP hard.

# Answer
> 4 votes
This has been answered on the CS Theory StackExchange site: https://cstheory.stackexchange.com/a/19833/5038

(I'm posting an answer here, so this question does not get treated as a question-without-an-answer and get periodically rotated back onto the front page by the Community user. Normally, questions without any upvoted or accepted answer are re-displayed on the front page every so often. Since this question now has been solved answered elsewhere, there doesn't seem any need for that. As long as someone upvotes or accepts this answer, that should prevent this question from being rotated back onto the front page. I'm ticking the community wiki box so I won't get any rep from this answer.)

---
Tags: complexity-theory, satisfiability, decision-problem, complexity-classes
---


title: Fixed Parameter Algorithms

text:
# Question
Title: Fixed Parameter Algorithms
Suppose a parameter $\hat{k}$ is larger than another parameter $k$, assume that $k$ is bounded by a function $f$ of $\hat{k}$.

How can we prove that if a problem is FPT with respect to $k$ implies it is FPT w.r.to $\hat{k}$.

# Answer
> 0 votes
Just substitute the fact $k\leq \hat{k}\leq f(k)$ into the definition of what it means for the problem to be FPT with respect to $k$.

---
Tags: algorithms, complexity-theory
---


# Question
Title: Questions from Dijkstra's EWD 1300: "The notational conventions I adopted, and why"
A link to the transcript of the manuscript: http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1300.html

My questions:

What does Dijkstra mean by:

> "Do not introduce priority \[precedence\] rules that destroy symmetry. I remember how much more pleasant the predicate calculus became to work with after we had decided to give con- and disjunction the same binding power and thus to consider p ∧ q ∨ r an ill-formed formula."?

Specifically: can you illustrate how a precedence rule where conjunction has higher precedence than disjunction would destroy symmetry?

Then, what does he mean by (please note that he uses the "." operator to denote function application):

> "As time went on, I learned to appreciate expressions built with operators as a way of avoiding functional notation. We can write the difference a−b as dif.(a, b) or exc.(b, a), where min and exc are functions of an ordered pair. (I believe that the notion of “function of 2 arguments” is now obsolete.) But we can also write the “curried” versions (min. a). b and (sub. b). a in which, for instance, sub is a higher-order function such that sub. b decreases its argument by b (so that sub.(−1) would be the successor function). Functions dif, exc, min and sub are different functions and as soon as the operation of functional composition enters the game, the distinctions are essential. But as long as we don’t do functional composition, the choice between the four options is irrelevant and writing the expression a−b is a lovely way of avoiding being overspecific."?

Specifically: what is the function exc, and how is it that a-b can represent both exc and min? Am I correct in understanding that min is the minimum function?

# Answer
1. Conjunction and disjunction are dual, but if conjunction has higher precedence than disjunction, then dual to p ∧ q ∨ r is (p ∨ q) ∧ r != p ∨ q ∧ r.
2. As you can see `exc` is `dif` with its arguments flipped: `exc(x, y) = y - x`. `min` is probably short for "minus", not "minimum".
> 2 votes

---
Tags: formal-methods
---


# Question
Title: Satisfying condition to be in minimum spanning tree of an edge (maximum weight)
Let G be a weighted undirected graph and e be an edge with maximum weight in G.Suppose there is a minimum weight spanning tree in G containing the edge e.Which of the following statements is always TRUE?

1.There exists a cut in g having all edges if maximum weight

2.There exists a cycle in G having all edges of maximum weight

3.Edge e can not be contained in a cycle

4.All edges in G have the same weight

i think Option 4 and 1 is correct but which is always true .and what is the meaning of option 3.Can any body remove my confusion ??

# Answer
Homework question.

Anyway - about the third option: the question is whether it is possible that an edge with the maximal weight will be on some cycle (one of the cycles in the graph contains the edge e).

It is very easy question.

General hint: Remember that every MST doesn't contain the edge with the maximal weight of every cycle.

Specific hints:

1. What does it mean if there no cut in g having all edges of maximum weight?
2. Who said that G contains cycles?
3. Think about graphs where all the edges have the same weight.
4. see hint 2.
> 1 votes

---
Tags: algorithms, graphs, trees, spanning-trees
---


# Question
Title: Is the halting problem specific to Turing machines?
The proofs that the halting problem is undecidable seem to make very few assumptions about the kind of program/machine under consideration: just that the programs take one input and either loop or produce an output. Not just Turing machines have these characteristics: for example, a linear-bounded automaton can also loop.

So, as well as a proof that you can't use a Turing machine to decide whether a Turing machine will halt, is it not also a proof that you can't use a pushdown automaton to decide whether a pushdown automaton will halt, and so on, for any automaton/language that has the ability to loop?

# Answer
The halting problem applies to any model of computation: you can always ask, "Given this machine and this input for it, does the machine halt?" Indeed, for any two models of computation $A$ and $B$, you can always ask the more general question, "Is there an $A$-machine that, given a description of a $B$-machine and its input, determines whether that machine halts?" Often, we take $A=B$.

What does vary between machine models is decidability of the halting problem. If we say "decidable" on its own, it means Turing-decidable, i.e., model $A$ above is Turing machines. For, e.g., $B$ is DFAs or PDAs, the halting problem is decidable: the machine always halts because it halts when it reaches the end of its input, the input is finite and the machine consumes one character of input at every step. For $B=$Turing machines, the well-known diagonalization argument proves undecidability, and this extends by reduction to any Turing-equivalent model of computation. That is, any model of computation that can simulate and be simulated by Turing machines.

The diagonalization proof has few assumptions – see Wikipedia for more details. There needs to be a coding of machines so they can be used as inputs to the machines themselves and the machines need to be able to simulate an "if" statement, loop forever, return a value, duplicate a value and be closed under subprograms (i.e., the model wouldn't become more powerful if you let machines call each other as subroutines). Therefore, no model of computation that has these properties can decide its own halting problem.

Note that this includes any model that can simulate a Turing machine, even if that model is more powerful. For example, consider the class $H$ of Turing-like machines with an oracle for the Turing machine halting problem. That is, the machines operate just like Turing machines but have a special instruction that can look at the tape and give an immediate yes or no answer to the question, "Does the ordinary Turing machine described there halt on the input described?" Thus, the machines are more strictly powerful than ordinary Turing machines. These oracle machines cannot decide their own halting problem, by the same diagonalization proof as for ordinary Turing machines. In fact, there's a strict, infinite hierarchy of machines: consider machines $H'$ that have an oracle for the $H$-halting probem, and then machines $H''$ with an oracle for the $H$-halting problem and... See Turing degree and the arithmetical hierarchy for more on that.
> 13 votes

---
Tags: turing-machines, halting-problem
---


title: NP-hard: an instance or a set?

text:
# Question
Title: NP-hard: an instance or a set?
When we say a problem is NP-hard is that a property of a set of problems or is it a property of a instance of the set of problems?

# Answer
> 1 votes
You seem to be confused about terminology. You start correctly: "a problem is NP-hard". This already answers your question: hardness is a property of problems, not sets of problems or of instances.

To refresh, a problem is a question of the form, "Does the input object have this interesting property?" An instance is a specific object you're asking about. So, for example, 3-colourability is the problem, "Can the vertices of the input graph be coloured red, green and blue such that there is no edge between vertices of the same colour?" When you ask that question of a specific graph $G$, then $G$ is the instance. (And a set of problems is just a set of problems: you know what a set is and you know what a problem is.)

---
Tags: complexity-theory
---


# Question
Title: NP-hard proof: Polynomial time reduction
As I understand, to show that a certain problem $P$ is NP-hard we can reduce a known NP-hard problem $Q$ to a problem in $P$. This reduction, say $f$, has to be polynomial time.

Could someone please explain is it necessary that $f$ maps each instance of $q\in Q$ to $P$ or can we map a selected subset of $\tilde Q \subseteq Q$ to $P$? i.e. does pre-image of $f$ has to be be all of $Q$ or can it be a subset of $Q$?

Thanks

# Answer
Yes and no. To cut a long story short, it's enough that the pre-image of $f$ is NP-hard.

Intuitively, the point of NP-hardness is that, if you had an efficient algorithm for an NP-hard problem, then you would have an efficient algorithm for all problems in NP. Let's suppose you've come up with a new problem, Triomphe's Problem (TP), and you want to prove that it's NP-hard. You need to show that *every* problem in NP can be reduced to TP. There are, on the face of it, two ways of doing this.

The direct way. Show that there is a polynomial-time computable function $f$ with the following property: for any nondeterministic polynomial-time Turing machine $M$ and every input $x$, $f(M,x)$ is an instance of TP and $f(M,x)$ is a "yes" instance of TP if, and only if, $M$ accepts $x$. This is how Cook proved NP-completeness of Boolean satisfiability and how Fagin proved NP-completeness of evaluation of formulas of existential second-order logic.

The indirect way. Show that there is an NP-hard problem $P$ and a polynomial-time computable function $f$ with the following property: for any instance $x$ of $P$, $f(x)$ is an instance of TP and it is a "yes" instance of TP if, and only if, $p$ is a "yes" instance of $P$. This is how just about every other NP-hard problem, apart from the two listed above, was proven NP-hard.

The indirect way works through a chain of reductions. We need to establish that *every* problem in NP can be reduced to TP. So, we start with our nondeterministic polynomial-time Turing machine $M$ and its input $x$. We convert that to an instance of Boolean satisfiability. Then we convert that into, say, an instance of 3-SAT. Then we convert that into, say, an instance of 3-colourability. Then maybe we convert that into an instance of $P$ and, finally, convert that into an instance of our fictional problem TP. Because all of these reductions work for *every* instance of the problem, we have a reduction from our generic NP problem to TP.

Both in theory and in practice, that is how reductions are done: you need to translate *every* instance of the problem. But we don't actually need that much. Look at the first step of the chain of reductions in the previous paragraph. We started with *any* Turing machine at all, and we converted it into a Boolean formula. Without looking closer, all we know is that we've produced some Boolean formula, and we don't know any details about it. However, looking more closely at the reduction, we see that the formula is in conjunctive normal form (CNF) (or that the proof can easily be modified to make it so). For the next step, converting to 3-CNF, the definition of reductions tells us that we have to be able to translate *every* Boolean formula into one in 3-CNF, but we know we don't need to do that much. It would suffice to translate only the formulas that are already in conjunctive normal form, because those are the only ones that the translation from Turing machines will produce. And that's actually what the standard proof does.

Normally, when a new problem is proven NP-hard, a full reduction is given from some known NP-hard problem to the new problem, which translates all instances. However, in principal, you could get away with a reduction that does less than that, as long as it covers enough instances to establish the chain back to the generic Turing machine $M$ and its input $x$. To give another example, 3-colourability is NP-hard because of a standard reduction from 3-SAT. You could prove a new problem to be NP-hard by a reduction that only translates the instances of 3-colourability that could be produced by that reduction from 3-SAT. This works because 3-colourability is already NP-hard when its input is restricted to be from the class of graphs that can arise from the reduction from 3-SAT.

However, if you're a student doing exercises and exam questions, I'd recommend that you always produce reductions that map the whole problem, rather than just a subset of it.
> 4 votes

# Answer
I'm not sure I understood you. But I believe you wanted to ask the following question:

Assuming I have NPH problem $Q$, we usually refer it as a language/set. For example, the set of all the tuples $(G,k)$ such that $G$ is a graph and it has a vertex cover of size $k$.

To prove that a problem $P$ is NPH, it is enough to prove that given input $q$ to some NPH problem $Q$, you can map it in polynomial time (the mapping is the polynomial reduction function) to some input $p$ for the problem $P$, such that set of $q\in Q$ if and only if $p\in P$.

For example $Q$ as the vertex cover NPH problem, for every input to $Q$, a graph $G$ and integer $k$, you can map it in polynomial time to some input for the problem $P$, such that $q\in Q$ if and only if $p\in P$.

This proves that $P$ is also NPH, because if it is not, and you have polynomial time reduction, you can easily build a deterministic polynomial time algorithm that will solve the original NPH problem.

If you reduction is only from some subset of the inputs for the NPH problem, it won't work - because you cannot build deterministic polynomial time algorithm for $Q$, given the reduction and a deterministic algorithm that solves P in polynomial time.

(In my answer I assume the P != NP. Otherwise, for problems like VC, there is already a deterministic polynomial time algorithm)
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: In case of program overlays; is it necessary to have error handling routine in memory, regardless of error?
I came accross the question regarding program overlays,
`Program1 is of 100kB and program2 is of 90kB and common code is 10kB and overlay driver is 20kB and error handling routine is 50kB, min memory required when there is no error?`

according to me it should be 100 + 20 + 10 = 130; as there is no error..
but ans is 180; they are considering error handling routine also in account..

I am not getting why error handling routine, if there is no error?

# Answer
What would happen if the overlay driver experienced an error and the error handling routines weren't loaded? You should think of the error handling routines as being a necessary part of the overlay driver.
> 2 votes

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


# Question
Title: Finding edges with minimal weight sum, such that every simple cycle contain at least one edge
Given simple, udirected and connected graph with $n$ verticies. Every edge in this graph has some weight. I have to find (in polynomial time) a set of edges such that :

1.every simple cycle in graph contains at least one edge from this set
2.sum of weights of these edges is the least possible

I have derived the following algorithm to solve this problem.

First, apply DFS algorithm, starting from 1. vertex, to get all back edges. It is known that every simple cycle in this graph will contain at least one back edge, so 1. condition will be satisfied. To satisfy the 2. condition, we must apply DFS algorithm starting from 2. vertex, 3. vertex .... n. vertex, to get different sets of back edges, that all satisfy 1. condition, and choose set with the least sum of weights.

My question is will this algorithm give the right answer ? And if it won't, then why?

I have some doubdts about it, for example, is the set of back edges, given by DFS algorithm, is least possible to satisfy the condition that every simple cycle in the graph contain at least one edge from this set? For example, DFS has given me that $BE = \left\\{ e\_1, e\_2, e\_3, e\_4 \right\\}$ are the back edges of graph. So every simple cycyle will contain at least one edge from $BE$. But, is it possible that we can throw out, say, $e\_3$ and still every simple cycle in graph will contain at least one edge from $\left\\{ e\_1, e\_2, e\_4 \right\\}$ ?

# Answer
To turn some of my hints into an answer, the problem with your solution is that the DFS phase doesn't do anything to optimize the weight of the complement of the tree. Here is a solution.

Let $G=(V,E)$ be your graph, $w : E\to \mathbb{Z}$ the weight function, which we extend linearly to $2^E$. Call the set we are looking for $B$.

Property (1) implies that $C := E\setminus B$ is acyclic. Otherwise, $C$ contains some cycle, contradicting the fact that $B\cap X\neq \emptyset$ for every cycle $X$ in $G$.

Property (2) implies that $w(C)$ should be as large as possible. Since $w(B) = w(E) - w(C)$, minimizing $w(B)$ is just maximizing $w(C)$.

So, the algorithm is just to compute the maximum weight forest in $G$, and return the complement. (The MWF isn't necessarily a spanning tree if there are negative weights.)
> 1 votes

---
Tags: algorithms, graphs
---


# Question
Title: Finding minimum spanning tree with O(|V|)
Given an undirected weighted graph $G(V,E)$, where the number of edges is $|V|+10$, how can I find the minimum spanning tree of $G$ in $O(|V|)$?

Kruskal's algorithm is out of the question, since sorting alone is $O(|V|\log |V|)$, so I thought maybe using Prim's algorithm with minimum binary heap, but still - every iteration will cost $\log |V|$ for updating vertices keys in the heap, so altogether it's $|V|\log |V|$.
I know that the key here is to use the fact that $|E|=|V|+10$, so I start thinking maybe removing the 11 edges with the biggest weights, as long as the graph stays connected, but that's obviously a bad idea since it'll - again - require sorting.
I just can't figure it out. Any help would be greatly appreciated.

# Answer
Use DFS to find a cycle in the graph (in linear time). Save the maximum-weight edge while performing DFS, Delete it from the outputted cycle. Repeat 11 times. Done.
> 3 votes

---
Tags: graphs
---


title: Reduction from max-cut to min-cut

text:
# Question
Title: Reduction from max-cut to min-cut
Algorithms for the finding of an MST in a graph can be applied for both maximum and minimum spanning trees.

It is well known, however, that the finding of a max-cut in a graph is an NP-hard problem while the min-cut problem can be easily solved in polynomial time.

Why aren't the two equivalent?

What is the restriction that I’m missing here?

Thanks!

# Answer
Some intuition involves the notion of a *convex* function. You can look up the formal definition, or consider the quintessential example of a convex function, namely $x^2$. Minimizing a convex function is easy, since there is a unique minimum, and moreover if you start anywhere and keep going done, you will eventually reach the minimum. Maximizing a convex function is a different thing. Suppose for example that you want to maximize $x^2$ under the constraint $x \in \[\alpha,\beta\]$. In order to do that, you need to compute the function at both endpoints $\alpha,\beta$ and choose the maximum. Now imagine that you function is multivariate and has lots of inputs. Minimizing is still easy - there is a unique minimum that can be reached by descent - but maximizing is problematic, since there are many potential maxima.

MAX-CUT and MIN-CUT are related to the cut function, which gets as input a cut, and outputs the number of edges cut. This is a set function rather than a function on $\mathbb{R}^n$, but it has the property of *submodularity*, which is a form of convexity for set functions. Indeed, in general one can minimize submodular functions, but maximizing them is NP-hard.
> 3 votes

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


# Question
Title: Examples of context-free languages with a non-context-free complements
Context-free languages are not closed under complementation. In the lectures we have been given the same argument as here on Wikipedia: For $$A = \\{\mathtt a^n \mathtt b^n \mathtt c^m;~m, n ∈ ℕ\_0\\}\quad\text{and}\quad B = \\{\mathtt a^m \mathtt b^n \mathtt c^n;~m, n ∈ ℕ\_0\\},$$ both $A$ and $B$ are context-free, but their intersection $A ∩ B$ is not. Since context-free languages are closed under unions, they can’t be closed under complementation as well.

However, this only shows that one of the three languages $A$, $B$, and $\overline A \cup \overline B$ is a context-free language with a non-context-free complement, but not for which one of these this is true. So what is it?

Also, is there a minimal and elegant example of a context-free language with a non-context-free complement, maybe over a binary alphabet?

# Answer
The language $L\_1= \\{ww \mid w \in \\{a,b\\}^\*\\}$ is not context-free (as can be shown using the pumping lemma; see here). Its complement $L\_2 = \\{a,b\\}^\* \setminus L\_1$ is context-free (as shown here). This gives a simple and elegant example of a context-free language (over a binary alphabet) whose complement is not context-free, as you requested.
> 17 votes

# Answer
The example you see on Wikipedia: put $A=\\{a^n b^n c^m\\}$, $B=\\{a^m b^n c^n\\}$. It's easy to see $\overline{A}$ and $\overline{B}$ are context-free by defining a PDA; you can note that they're deterministic context-free languages, which is a class closed under complement. Therefore $\overline{A} \cup \overline{B}$ is a context-free language with a non-contextfree complement $A \cap B=\\{a^n b^n c^n\\}$.

In the same vein, the language $\\{a^n b^m c^n d^m\\}$ is not context-free but its complement is.
> 15 votes

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


title: Can't under stand change of variable

text:
# Question
Title: Can't under stand change of variable
T (n) = T(√n) + 1 The easy way to do this is with a change of variables. Let m = lg n and S(m) = T (2^m).

T(2^m) = T (2^(m/2)) + 1

S(m) = S(m/2) + 1

Can any one explain why 1 and 2 are same and this works ??

# Answer
Perhaps the concept will clear up if you try to solve the recurrence:

$T(n)=T(\sqrt{n})+1$.

Let $n\gt0$ which implies $\log\_2n$ exists.

Let $m=\log\_2n$ which implies $2^m=n$.

By the above statement and the first statement it is true that: $T(2^m)=T(2^{m/2})+1$. This is statement $A$

Define a new function $S$, such that $T(2^{\log\_2n})=S(\log\_2n)$.

$\implies T(2^m)=S(m)$ \[By definition of $m$\]

$\implies T(2^{m/2})=S(m/2)$.

By statement $A$ and above,

$S(m)=S(m/2)+1$.

Note that $m=\log\_2 n$ and now we let $m$ be a perfect power of 2. Let $m=2^k$ where $k\ge0$. Also note that by imposing this restriction, we have also made $n=2^{2^{k}}$ thus $n$ is two raised a perfect power of 2.

Expanding the recurrence,

$S(m)=S(m/2)+1\implies S(m)=S(m/4)+2 \implies ....\implies S(m)=S(m/2^k)+k\implies S(m)=S(1)+k \implies S(m)=S(1)+\log\_2 m.$

Now as $S(m)=T(n)$ \[By definition of $S$ and $m$\], we can write the last statement of the previous as follows:

$T(n)=\log\_2\log\_2 n+S(1)$

Again by definition of $S$, we get $S(1)=T(2)$ \[Remember $S$ is a function in $m$ and $T$ is a function in $n$, but $m$ and $n$ are not independent. Infact $m$ has been defined as $\log\_2 n$\].

Hence we have a solution to your original recurrence,

$T(n)=\log\_2\log\_2 n + T(2).$

\[Note that during the proof, we had restricted the values which $n$ could take up, but putting the solution back into the recurrence tells us that this solution works even when $dom(T)=\mathbb{R}^+$\]
> 3 votes

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


title: Number of Matchings in a Bipartite

text:
# Question
Title: Number of Matchings in a Bipartite
Given two sets A and B of sizes |A| = n and |B| = m, where m \>= n. There are edges from set A to set B. I need to find the `number` of matchings where all of vertices in set A have been matched with one vertex in set B. Is it possible to caclulate this quantity ?

(I have very little knowledge of Graph Thory and Bipartite Matching or how it is computed)

# Answer
A matching in which all the vertices in $A$ are matched is known as a *perfect matching*. When $n = m$, you need to compute the permanent of the bipartite adjacency matrix (defined in the same way as the determinant, only without the signs). This is conjectured to be rather difficult unfortunately, even in this special case in which the matrix in question is zero-one. The permanent-vs.-determinant question is analogous to the more famous P-vs.-NP question.

When $m \> n$, you can add $m-n$ dummy vertices to $A$ and connect them to all vertices in $B$. The number of perfect matchings in the new graph is exactly $(m-n)!$ times the number of perfect matchings in the old graph.
> 6 votes

---
Tags: graphs, combinatorics, bipartite-matching, matching
---


# Question
Title: graph isomorphism completeness of class X and not-X
there are many classes of graphs proved GI complete & many questions related to GI on tcs.se eg \[1\] & many others.

> suppose a class both $X$ and not-$X$ of graphs are proven GI complete. what are the implications of that?

\[1\] open problems related to GI

# Answer
Apparently, with graphs of class $X$ and not-$X$ you mean graphs that fulfill a property $X$ and those that don't. It is common that say a graph problem has a different complexity when the input graph is restricted to a certain class of graphs. In this sense, graph isomorphism is no different. As for your question, it is easy to come up with plenty of (even large) classes of graphs. For example, consider graphs that have an even number of vertices, and those that don't. Both are GI-complete, so at least in general, there are no implications.

If this is not satisfying, you need to address what you mean by "non-trivial graphs", but I don't think this would turn out to be too fruitful.
> 2 votes

---
Tags: graphs, graph-isomorphism
---


# Question
Title: optimal placement of fixed length items on a given length
I have got some equipment of standard lengths, say:

> equipment\_lengths = {60, 48, 36, 29}

that I have to place on a given length of, say 100. I have to place this equipment so as to minimize material waste while covering the given length. I am allowed to exceed the given length of 100 but keep the excess minimized. I am not allowed to drop short of the given length. Also I have an unlimited number of each equipment.

So, one solution to the above example would be:

> {60, 48} (excess = 60 + 48 - 100 = 8)

Another could be

> {60, 60} (excess = 60 + 60 - 100 = 20)

The first solution is preferable to the second one as it minimizes the excess.

My first approach has been to implement a greedy algorithm that takes the longest equipment and keeps placing those till I exceed the given length. Once that happens I remove the last equipment I placed and place the next smaller ones till I exceed again. In the end I select the combination with the least amount of excess. For example the algorithm will successively do the following:

* 60, 60 (excess = 20)
* 60, 48 (excess = 8)
* 60, 36, 36 (excess = 32)
* 60, 36, 29 (excess = 25)

So, now it will select {60, 48} as the optimal solution when you remove last one equipment on excess. The algorithm then repeats the exercise by removing the last two equipments and finds another optimal solution. Finally it chooses the best one among the two optimal solutions it found.

Now, I have been studying bin packing and knapsack problem variations and while these problems look similar, I haven't been able to apply them to my problem. Does my problem have a well known solution? If not, how should I go about it to efficiently find the globally optimum solution?

Additional information: I think giving preference to longer equipments should be a good idea as the equipments need to be joined with screws or bolts so joining two longer equipments would be less work than three shorter ones, but I don't think it's more important than material wastage.

# Answer
> 2 votes
Your problem is NP-hard. The decision problem version of your problem is to ask whether there exists a selection of equipment achieving an excess of $e$ or less (given $e$ as input, and all the lengths). The special case of $e=0$ is exactly the subset sum problem, which is NP-complete. Therefore, the decision version of your problem is NP-complete, so finding an optimal set of equipment is NP-hard. In other words, you cannot hope for a fully polynomial-time algorithm to solve this problem.

If the lengths are not too large, you can adapt the standard dynamic programming algorithm for subset sum to solve your problem as well. It applies almost directly: the dynamic programming algorithm tells you, for each integer $\ell$, whether there is a way to choose equipment whose lengths sum to exactly $\ell$. Now you can check whether there is a solution for $\ell=100$, $\ell=99$, $\ell=101$, $\ell=98$, $\ell=102$, etc. (in that order) and take the first solution you find. The running time will be tolerable if the desired length (e.g., 100) is not too large.

---
Tags: algorithms, optimization
---


title: Hardness proof of EVEN-ODD PARTITION

text:
# Question
Title: Hardness proof of EVEN-ODD PARTITION
The PARTITION problem is NP-complete:

INSTANCE: finite set $A$ and a size $s(a) \in \mathbb{Z}^+$ for each $a \in A$
QUESTION: Is there a subset $A' \subseteq A$ such that $\sum\_{a \in A'} s(a) = \sum\_{a \in A \setminus A'} s(a)$

The problem remains NP-complete even if the elements are ordered as $a\_1,a\_2,...,a\_{2n}$ and we require that $A'$ contains exactly one of $a\_{2i-1},a\_{2i}$ for $1 \leq i \leq n$ (Garey and Johnson, Computers and Intractability).

This variant should be known as EVEN-ODD PARTITION.

Do you see a quick reduction to prove its hardness? (or do you know the paper where it was first defined and proved)

# Answer
> 7 votes
Let $b\_i = a\_{2i} - a\_{2i-1}$. The problem is then finding $\sum \varepsilon\_i b\_i = 0$. Here $\varepsilon\_i = 1$ if $a\_{2i} \in A'$ and $-1$ otherwise. Let $B' = \\{b\_i \mid \varepsilon\_i = 1\\}$. Note that $\sum\_{b \in B'} b = \sum \_{b \in B \setminus B'} b$. Thus solving PARTITION of $B$ would solve EVEN-ODD PARTITION of $A$.

Let $b\_{2i} = a\_i$ and $b\_{2i-1} = 0$. Note that if $b\_{2i} \in B' \leftrightarrow a\_i \in A'$ and $\sum\_{B'} = \sum\_{B \setminus B'}$ then $\sum\_{A'} = \sum\_{A \setminus A'}$. Thus solving EVEN-ODD PARTITION on $B$ would solve PARTITION on $A$.

# Answer
> 2 votes
Another quick reduction is the following:

Let $2^k \> \sum\_{a \in A} s(a)$. Then for each element $a\_i \in A$ add to $B$ two elements:

$b\_{2i-1} = 2^{2k+2i} + a\_i$and
$b\_{2i} = 2^{2k+2i} + a\_i 2^k$.

The two consecutive elements cannot be contained in the same subset (due to the $2^{2k+2i}$ common "bit"), and $B$ can be even-odd partitioned into two equal sum subsets that have the same cardinality if and only if $A$ can be partitioned into two equal sum subsets.

---
Tags: np-complete, reference-request, partitions
---


# Question
Title: Number of ways to fill a 2xN grid with M colors
This question was asked in the onsite regionals for ACM ICPC 2013 at Amritapuri. In short, the question asked to find the number of ways to fill a $ 2\times N$ grid with $M$ colors such that no two cells with the same row or same column have the same color.

The limits given are $1 \leq N$, and $M \leq 1000$ with 1000 test cases per input.

Based on the constraints the approach that comes to my mind after a long struggle includes having a precomputed DP table which can be used for every test case. I tried to apply the inclusion-exclusion principle but could not come up with any solution. I also tried to solve it using bipartite perfect matchings, but no success. How should I approach this question?

# Answer
> 5 votes
You can use inclusion-exclusion. There are $M!/(M-N)!$ choices for the first row. Fix these choices. The number of choices for the second row in which $T$ specific columns are bad (but the row itself is good) is $(M-T)!/(M-N)!$. According to the inclusion-exclusion principle, the required number is $$ \frac{M!}{(M-N)!} \sum\_{T=0}^N (-1)^T \binom{N}{T} \frac{(M-T)!}{(M-N)!}. $$ I'll let you take it from here.

# Answer
> 3 votes
There is a simpler way to solve your problem, but just for fun, I'll outline a different approach that generalizes nicely. For a real-world implementation, the advantages should also be clear.

You can cast this problem, and similar problems like Sudoku as constraint satisfaction problems. After modeling the problem, you can feed it to a state-of-the-art solver such as MINION that does the dirty work for you. MINION can handle finding a single solution, as well as counting all the solutions to a problem.

In what follows, I'll present a short input file to MINION to solve an $2 \times M$ instance of your problem, where $M=3$.

```
MINION 3

**VARIABLES**
DISCRETE q[3] {0..2}
DISCRETE r[3] {0..2}

**CONSTRAINTS**
alldiff(q)
alldiff(r)
diseq(q[0],r[0])
diseq(q[1],r[1])
diseq(q[2],r[2])

**EOF**

```

There is a variable corresponding to every vertex in the grid graph, the other side of the graph is modeled by the array $q$, and the other one with $r$, if you will. Each one takes a value from the domain $0..M$, where $M=3$ in this example. The constraints ensure that vertices in a row must be colored with different colors, and that opposite vertices (meaning the two vertices in a column) receive different colors.

# Answer
> 2 votes
Your problem statement says you want to find one example of a solution. If that is really correct, here is a very simple way to find one solution.

* If $M \< N$, there is no solution. (Proof: consider how you're going to fill in the top row. You're screwed no matter what you do.)
* If $M=N$, it is easy solution. Fill in the top row with any permutation of the $M$ colors. You can make the second row the same as the first row, but shifted over by one place. That will satisfy all the constraints.
* If $M\>N$, then throw away $M-N$ of the colors (your solution won't use them) and fill in the grid using just the first $M$ colors, using the method of the previous case.

---
Tags: graphs, combinatorics, permutations, bipartite-matching
---


# Question
Title: Is Equational Reasoning an application of Referential Transparency?
In various discussions of the merits of functional programming, the phrase referential transparency or equational reasoning is often listed.

My question is - **are these roughly the same thing?** (One being the concept, and the second being the process of applying the concept?

# Answer
> 10 votes
Referential transparency is an **operational notion**: it describes what happens when you **evaluate** a same piece of code (typically a function) several times, namely, the return value is the same. In particular, the **evaluation context** can generally be ignored when considering the operational semantics of a referentially transparent language.

Equational reasoning is, well, a way to **reason** about code: it allows you to replace pieces of code with others without worrying about things like evaluation order or current state. This is usually valid *because of referential transparency*; in general the value of a given code block is dependent on it's *context* which prevents replacing a piece of code by another *regardless* of it's position within another block.

In conclusion, referential transparency is a **property of the evaluation semantics** and the ability to do equational reasoning is a **benefit** of this property.

---
Tags: functional-programming
---


# Question
Title: Minimal Spanning tree and Prim's Algorithm
Is there any example that anybody could come up with that shows Prim's algorithm does not always give the correct result when it comes knowing the minimal spanning tree.

# Answer
> 1 votes
For any un-directed graph `G` that is connected and weighted Prim's algorithm will produce the MST of the graph. However if the graph is directed this does not hold, as an example consider this directed graph:

```
╔═╗        ╔═╗        ╔═╗
║ ║---5--->║B║---5--->║ ║
║ ║        ╚═╝        ║ ║
║A║                   ║D║
║ ║        ╔═╗        ║ ║
║ ║---6--->║C║---1--->║ ║
╚═╝        ╚═╝        ╚═╝

```

Starting with `A` Prim's algorithm would choose edges `(A,B),(B,D),(A,C)` total weight of `16`. The MST (if it were undirected) however is given by the edges `(A,B),(A,C),(C,D)` with a total weight of `12`.

I should also clarify that directed graphs do not have MSTs (as they are only defined for undirected graphs). The closest notion for directed graphs would be Arborescence and an example of an algorithm which solves this similar question for directed graphs is Edmonds' Algorithm.

---
Tags: algorithms, greedy-algorithms, spanning-trees
---


# Question
Title: Algorithm to determine if recursion was breadth first or depth first
Given a tree $T$ and a sequence of nodes $S$, with the only constraint on $S$ being that it's done through some type of recursion - that is, a node can only appear in $S$ if all of its ancestors have already appeared, what's a good algorithm to determine if $S$ is a breadth first visit, a depth first visit, or neither?

A brute force approach is to compute every breadth first and depth first sequences and see if any is identical to $S$. Is there a better approach?

What if we don't want a yes or no answer, but a measure of distance. E.g. $breadth \< S \< R \< U \< depth$; what's a good algorithm to determine distance? (A brute force approach for this is just $max(length(longest{\\\_}common{\\\_}subsequence(S, breadth))/length(breadth))$ over every BFS - again, is there a better way to do this?)

# Answer
> 2 votes
Recall that both BFS and DFS are worklist algorithms. This means they maintain a "worklist" of vertices that need to be visited, but haven't been yet. You can think of the worklist as a list or set of "stuff that needs to be done", where here the kind of tasks that need to be done are of the form "visit vertex $v$". When DFS or BFS visits a vertex $v$, we find all its neighbors, and add each one that has not yet been visited to the worklist (if it is not already present in the worklist).

The only difference between DFS and BFS is in how they implement the worklist. DFS implements the worklist as a stack. BFS implements the worklist as a queue.

So, here is how you can test whether your sequence was obtained by DFS, by BFS, or by something else. Replay the sequence of visited nodes. Keep a worklist, just like DFS/BFS would, but use a set data structure, and add a timestamp to each item in the worklist recording when it first entered the worklist. At each step, when you visit a node $v$, check that $v$ is in the worklist, and check its timestamp. If its timestamp is the earliest of all items in the worklist, this is consistent with removal from a queue (i.e., BFS); if it is the latest of all items in the worklist, it is consistent with a stack (i.e., DFS); otherwise, it is neither. Then, add to the worklist each neighbor of $v$ that has not yet been visited and that isn't already in the worklist, using the same timestamp for all of them (since they all entered the worklist on the same step of the sequence).

Iterate through the entire sequence like this. If every step is consistent with DFS (i.e., consistently stack-like), then this sequence could have been generated by some DFS traversal. If every step is consistent with BFS (i.e., consistently queue-like), then this sequence could have been generated by some BFS traversal. If neither of these are true, then you know that this was generated by neither DFS nor BFS.

You can make this algorithm very efficient: at most a logarithmic slowdown compared to a DFS/BFS itself (and maybe even faster is possible).

# Answer
> 0 votes
If $S = a\_1,\dots,a\_n$, count the number of indices $i$ such that $a\_i$ is the parent of $a\_{i+1}$. Depth first maximizes this number. Breadth first minimizes it.

*(See comments that this is not correct: these are not unique maximums and minimums; there are nonDFS and nonBFS that also maximize or minimize)*

---
Tags: algorithms, trees, recursion, discrete-mathematics
---


# Question
Title: How are image files, sounds, data, etc. compiled/linked in to a single file?
I'm both asking for me & future readers as to how pictures, sounds, textures, assets, and such are compiled and linked in to one binary/program, and how that process works.

I have seen this in standalone programs I have downloaded on Windows, and I'm fairly certain any OS can implement this. It appears that, instead of keeping the data stored separately as individual files within the filesystem, all data is converged in to one file. When you run the program, it's as if the data could have just, instead of requiring multiple scattered files through the drive, directories, subdirectories, etc., been bound to one program with everything in it; no need for fragmentation, missing files, etc.

So, to sum this question up, let me first illustrate some key points:

I had originally thought that, ***since all files on the computer are basically high-and-low voltage sources at the lowest level***, files can be converged together, being similar to "zipping/unzipping files." Using this common ground, it's easy to see how the data of a file, ***any file***, could be bound/binded together with other data, and act, from the scope of the filesystem and GUI, as "just a file." But many things are actually in it that don't have to only represent just a typical idea of a "program" with some people's view of it as only instructions like adding, moving data around, etc.

I am not sure of this, but I have a good sense that it's similar, so this why I'm asking for clarification.

When you see a standalone program from one file that contains external assets when you run it (texture files, video data format, image data, sounds, other resources, etc.), it's clear that the single executable file has all the data necessary "packed" in to one somehow, or the such.

How does the compiler/linker do this, how would the program/library/etc. access the data converged in it as opposed to differing from separate "files" independently, and how are compiler's/linker's settings adjusted to do this in any general sense?

NOTE: Programmers, StackOverflow, Superuser, and few others deny this question, and give no reason why, so I figured this area might see it fit.

# Answer
A file is just a file. Any given sequence of bytes can be interpreted as instructions for the CPU, pixels of a graphics file or anything else. And a file can contain sequences of bytes that should be interpreted as instructions and sequences of bytes that should be interpreted as graphics. If the executable part has been written correctly, it will never try to interpret the graphics part of the file as CPU instructions; when it needs to refer to the graphics, it knows where they are in the file (and, hence, the memory image) and starts reading from the appropriate address. In principal, the operating system doesn't even need to know it's doing this.
> 2 votes

# Answer
Sounds like you've already have a good intuition for this; your understanding is about right. How do they do it? They include the external asset in the file, as part of the file. You understand how you can create a zip file that contains multiple files, right? Well, one can do the same thing when creating a standalone program (embed multiple other files or other resources in it). There's nothing super mysterious or magical about it: it's pretty much the obvious approach that you would probably come up with, if you faced this problem.
> 1 votes

---
Tags: terminology, data-structures, compilers
---


# Question
Title: Solution to recurrence $T(n) = T(n/2) + n^2$
I am getting confused with the solution to this recurrence - $T(n) = T(n/2) + n^2$

Recursion tree -

```
T(n)                      Height lg n + 1
 |
T(n/2)
 |
T(n/4)

```

So it turns out to be -

$T(n) = n^2(1 + 1/4 + (1/4)^2) + \ldots (1/4)^{\log\_2 n - 1})$

$T(n) = 4\*n^2(1- (1/4)^{\log\_2 n})/3 + n^2 $

$T(n) = 4\*n^2(1 - 1^{\log\_2 n} + 4^{\log\_2 n})/3 + n^2 $

$ T(n) = 4\*n^2(1 - 1 + n^{\log\_2 4})/3 + n^2$

$ T(n) = 4\*n^2(n^2)/3 + n^2$

$ T(n) = 4/3 * (n^4) + n^2 $

$ T(n) = \Theta(n^4) $

But according to the Master theorem, $a = 1, b = 2, f(n) = n^2 $, then $n^{\log\_2 1} = 1 $ which is polynomial times less than $ n^2 $ so the solution should be $ \Theta (n^2) $?

# Answer
> 3 votes
I believe you commit your error when you suggest $(1/4)^{\log\_2 n}=1-4^{\log\_2 n}$ when in fact you should make the substitution $(1/4)^{\log\_2 n}=4^{-\log\_2 n}$. If you continue your calculation with this instead it will not yield a $n^4$ term and the highest power of $n$ will remain 2 as desired.

# Answer
> 5 votes
Try this way: $$ \begin{align\*} T(n) &= T(n/2) + n^2 \\ T(n) &= T(n/4) + (n/2)^2 + n^2\text{ (expand $T(n/2)$)} \\ T(n) &= T(n/8) + (n/4)^2 + (n/2)^2 + n^2\text{ (expand $T(n/4)$)} \end{align\*} $$

You will end up with: $$ \begin{align\*} T(n) &= n^2 + (n/2)^2 + (n/4)^2 + (n/8)^2 + \cdots + (n/2^{\lg n})^2 \\ T(n) &= n^2 + n^2/4 + n^2/16 + n^2/64 + \cdots \end{align\*} $$

We can bound this from above as $T(n) \le 2 n^2$ and from below with $T(n) \ge n^2$, giving $T(n) = \Theta(n^2)$.

Note: we do not need to use induction to prove this; since we can create an upper bound of $T(n) \le c\_1f(n)$ and a lower bound of $T(n) \ge c\_2f(n)$, we can use the definition of $\Theta(n)$ to establish the time complexity of the relation.

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


# Question
Title: Understanding LEADING and TRAILING operations of an operator precedence grammar
I want to understand what the `LEADING` and `TRAILING` of non-terminal in an operator precedence grammar physically mean.

I am confused by the various definitions I have read on them.
I understand that the `LEADING` of a non-terminal is the first terminal which can be present in it's derivation.
On the other hand, the `TRAILING` of a non-terminal is the last terminal which can be present in it's derivation.
In the following example:

```
E   ->  E   +   T      -- I
E   ->  T              -- II
T   ->  T   *   F      -- III
T   ->  F              -- IV
F   ->  (   E   )      -- V
F   ->  id             -- VI

```

By my understanding,

```
LEADING(E) = { +, *, (, id }
LEADING(T) = { *, (, id }
LEADING(F) = { (, id }

```

This turns out fine, but my problem is in the TRAILING.

```
TRAILING(F) = { id, ) }
TRAILING(T) = TRAILING(F) = { id, ) }          -- (1)
TRAILING(E) = TRAILING(T) = { id, ) }          -- (2)

```

Reason for `(2)` is that according to productions `I` and `II`, the last terminal of the derivation of `E` will be last terminals in the derivation of `T`. Hence, `TRAILING(E) = TRAILING(T)`.
Similarly, `TRAILING(T) = TRAILING(F)`.
Unfortunately the solution to this problem states:

```
TRAILING(F) = { id, ) }
TRAILING(T) = TRAILING(F) `union` { * } = { *, id, ) }
TRAILING(E) = TRAILING(T) `union` { + } = { +, *, id, ) }

```

I don't see how `*` or `+` can be the last terminals in the derivation of `E`. Any derivation of `E` will always end with either an `id` or `)`. Similarly, case for `T`.

# Answer
@Raphael : Definition of trailing : Any terminal which is present at the last of a right sentential form (and not the sentence) which is derived from a non-terminal is the trailing of that non-terminal.

Trailing($E$) :

$E \rightarrow E + T$ --In this the trailing is '$+$'

$ \rightarrow E + T * F$ \[using $T \rightarrow T\*F$\] -- Here trailing is '$\*$'

$\rightarrow E + T * ( E )$ \[using $F \rightarrow ( E )$\] -- Here trailing is '$)$'

(from $E + T * F$) $\rightarrow E + T * id$ \[using $F \rightarrow id$\] -- Here trailing is '$id$'

Hence trailing($E$) = $\\{+,\*,),id\\}$

So the lesson here is that you must use the right sentential forms also and not just the sentence to find out the trailing.

Note : $E \rightarrow E + T \rightarrow E + T * F \rightarrow E + F * id \rightarrow T + id * id \rightarrow F + id * id$ are all right sentential forms of $E$ as they have at least one non-terminal.

However $id + id * id$ is a sentence because it has no non-terminals and you must not use just the sentence to find out the trailing.
> 1 votes

# Answer
I think this link will be a great help to find leading and trailing for every nonterminal involved in a given grammar. http://www.scribd.com/doc/51358638/16/Operator-Precedence-Relations It made the concept clear to me!
> 1 votes

---
Tags: terminology, formal-grammars, parsing
---


# Question
Title: Size of address registers and data registers in relation with memory size
Suppose that a processor can address directly up to 4 Gigabyte main memory and can operate words with size 32 bit. Find how big should be the size of the "MAR" (memory address registers), "MDR" (memory data registers) and accumulator registers in this computer?

My answer: MDR is 32 bit wide since it exchanges data not only via the data bus but with the CPU data registers. How about MAR and accumulator? how are they related to the 4 gigabyte main memory?

# Answer
This question is not so simple to answer. At first sight, 32 bit address registers seem to perfectly match 2^32 byte = 4 GB of physical memory. However, with 32 Bit you can also address more than 4 GB, like Physical Address Extension (PAE) does. The opposite way round means that you can access 4 GB with less than 32 bit address register.

The data registers are not related to the memory size at all in my opinion. The data registers are mainly an indicator how much data can be transferred at one time. If you want e.g. to crack SHA-512, then you could design a CPU which benefits from transferring 512 bit of data at one time, so you have 512 data registers.

The same SHA-512 cracker CPU brings us to the accumulator: ideally the CPU would also process 512 bit numbers in one cycle, so the accumulator is also 512 bit.
> 1 votes

---
Tags: computer-architecture, memory-management
---


title: Pumping lemma for {w | w = ddd}

text:
# Question
Title: Pumping lemma for {w | w = ddd}
I want to use the pumping lemma to show that the following language is not context free: $$ L = \\{w \in \\{a,b\\}^\* \mid \exists d \in \\{a,b\\}^\*, w=ddd \\} $$

We suppose that $L$ is context-free. Then from the pumping lemma there is a pumping length $p$. Which word $s$ do I have to use, that belongs to $L$ and such that dividing that in $uvxyz$, we can show that the pumping lemma is not satisfied? Could you give me a hint?

# Answer
Starting from what Yuval Filmus said:

$w = a^n b^n a^n b^n a^n b^n $ (this word is accepted by your language).

Then you'll have to start to "cut" the word into pieces, multiple times. Start with:

$ u = a^j \\ z = a^{n-i-j} b^n a^n b^n a^n b^n \\ vxy = a^i \to v^{i\_1}x^{i\_2}y^{i\_3} = a^i \Rightarrow i\_1 + i\_2 + i\_3 = i $

So now the word looks like this:

$ w = uvxyz = {a^j} \\:\ a^{ki\_1} \\:\ a^{i\_2} \\:\ a^{ki\_3} \\:\ a^{n-i-j} \\:\ b^n a^n b^n a^n b^n $

Now start to simplify it:

$ w = a^{ki\_1} \\:\ a^{i\_2} \\:\ a^{ki\_3} \\:\ a^{n-(i\_1 + i\_2 + i\_3)} \\:\ b^n a^n b^n a^n b^n =\\ \\:\\:\ = a^{(k-1)i\_1i\_1} \\:\ a^{i\_2} \\:\ a^{(k-1)i\_3i\_3} \\:\ a^{n-i\_1 - i\_2 - i\_3} \\:\ b^n a^n b^n a^n b^n = \\ \\:\\:\ = a^{(k-1)i\_1} \\:\ a^{(k-1)i\_3} \\:\ a^n \\:\ b^n a^n b^n a^n b^n = \\ \\:\\:\ = a^{(k-1)(i\_1 + i\_3)} \\:\ a^n \\:\ b^n a^n b^n a^n b^n = \\ \\:\\:\ = a^{n(k-1)(i\_1 + i\_3)} \\:\ b^n a^n b^n a^n b^n = $

$i\_1, i\_3 \> 0$ as the v and y must not be the empty word;

For $k \> 1, n(k-1)(i\_1\ i\_3) \neq n$

This is only the simplest case. From here you can say that this is true for $vxy = b^i$, then again for $a^i,b^i$ from the second and last $d\ in\ w=ddd$.

After this, you'll have to take cases like $vxy = a^pb^q$, for each $d\ in\ w=ddd$ and $vxy = b^pa^q$ for each $dd\ in\ w=ddd$.

As you can imagine, the cases go on, but be sure to not repeat yourself: ($u = \varepsilon$ is the same as $u = a^j,\ j = 0$), and be careful with cases that are equivalent.
> 0 votes

---
Tags: context-free, pumping-lemma
---


title: P vs NP: Assuming P = NP

text:
# Question
Title: P vs NP: Assuming P = NP
Lets assume $P = NP$. Can we say if every language $L \in P$, then $L \in NPC$?

I read $P \subseteq NP$, which means that $L\in NP$. So I know for example, that a language can be $NP \text{ hard}$, but it doesn't have to be in $NP$, e.g. $HALT$.

But what about the case above. Is the language also $NPC$?

# Answer
> 5 votes
Yes. Every\* problem in $P$ can be reduced to any other problem in $P$ using polynomial-time reductions (since the reduction is allowed to do polynomial work, it can just solve the problem itself).

If $P=NP$, then it follows that every\* problem in $NP$ can be reduced to any\* other problem in $NP$ -- in other words, every\* problem in $NP$ is $NP$-complete. This implies that if $L \in P$ and if $P=NP$ then\* $L$ is $NP$-complete.

Footnote \*: There is an exception for the empty language ($\emptyset$) and the universal language ($\Sigma^\*$). For purposes of gaining a rough conceptual understanding, this technical detail can probably be safely ignored.

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


# Question
Title: Undecidable unary languages (also known as Tally languages)
An exercise that was in a past session is the following:

> Prove that there exists an undecidable subset of $\\{1\\}^\*$

This exercise looks very strange to me, because I think that all subsets are decidable.

Is there a topic that I should read to find a possible answer?

# Answer
> 6 votes
Note that $\\{1\\}^\*$ is isomorphic to $\Bbb N$. There are uncountably many subsets of both $\\{1\\}^\*$ and $\Bbb N$.

Perhaps you are confused with the fact that there are only countably many *finite* subsets of $\\{1\\}^\*$ (and $\Bbb N$).

# Answer
> 2 votes
A related question on StackOverflow is this one. Also the answer by Haile to this one is there:

> Since the universe of strings over any finite alphabet is countable, every language can be mapped to a subset of the natural numbers. So you just have to take a Recursively enumerable language wich is not decidable and map it into a subset of $\\{1\\}^\*$.
>
> For example, in the classic version of the halting problem we enumerate every turing machine into a binary string; you can now sort all the turing machines and define a map $f : TM \rightarrow N$ from Turing machines to integers where $f(TM) = n$ if TM is the nth Turing Machine in the ordered list of all TM.
>
> Now, the halting problem for Turing Machines coded as unary numbers is r.e. but not decidable.

Another related question in this one.

---
Tags: reference-request, turing-machines, undecidability
---


# Question
Title: Why are there two different `until` ($\cup$) semantics in Timed Computation Tree Logic?
**Background:**
In the book of *Principles of Model Checking* (Christel Baier and Joost-Peter Katoen, MIT Press, 2007), Section 9.2, page 701, the semantics of the *until* modality is defined over some time-divergent path $\pi \in s\_0 \Rightarrow^{d\_0} s\_1 \Rightarrow^{d\_1} \cdots \Rightarrow^{d\_{i-1}} s\_i \Rightarrow^{d\_i} \cdots$ as follows:

(We can skip the formal definition at your first reading.)
$\pi \models \Phi \cup^{J} \Psi \iff$
$\exists i \ge 0. s\_i + d \models \Psi \textrm{ for some } d \in \[0,d\_i\] \textrm{ with } \sum\_{k=0}^{i-1}d\_k + d \in J \textrm{ and }$ $\forall j \le i. s\_j + d' \models \Phi \lor \Psi \textrm{ for any } d' \in \[0,d\_j\] \textrm{ with } \sum\_{k=0}^{j-1} d\_k + d' \le \sum\_{k=0}^{i-1} d\_k + d$.

> Intuitively, time-divergent path $\pi \in s\_0 \Rightarrow^{d\_0} s\_1 \Rightarrow^{d\_1} \cdots \Rightarrow^{d\_{i-1}} s\_i \Rightarrow^{d\_i} \cdots$ satisfies $\Phi \cup^{J} \Psi$ whenever at some time point in $J$, a state is reached satisfying $\Psi$ and at all previous time instants **$\Phi \lor \Psi$** holds.

However, in the book of Model Checking by E.M. Clarke (Section 16.3, Page 256), the semantics of the *until* modality is given as follows:

> $s \models E\[\Phi \cup\_{\[a,b\]} \Psi\]$ if and only if there exists a path $\pi = s\_0 s\_1 s\_2 \cdots$ starting at $s = s\_0$ and some $i$ such that $a \le i \le b$ and $s\_i \models \Psi$ and for all $j \< i, s\_j \models \Phi$.

As indicated, the second definition is stricter than the first one in that it does not allow the case of $\lnot \Phi \land \Psi$ before reaching a state satisfying $\Psi$.

**Questions:**

1. Why are there two different *until* ($\cup$) semantics in Timed Computation Tree Logic (TCTL)?
2. Which one is more official?

# Answer
> 2 votes
The two definitions are equivalent:

As you point out, the second one implies the first, as if $\phi$ holds, then clearly $\phi\vee \psi$ holds.

Conversely, consider a computation that satisfies the first definition, and assume by way of contradiction that it does not satisfy the second definition. Thus, there exists some time in which $\psi$ holds, and in all previous times, $\psi\vee \phi$ holds. However, there also exists a previous time $d$ where $\psi\wedge \neg \phi$ holds, otherwise the second definition would hols.

Consider the minimal (or infimum) time $d$ for which this happens. Then in that time, $\psi$ holds, and in all previous times, $\psi\wedge \phi$ holds, so the second definition also holds for time $d$, which implies it for any later time.

Another way of looking on it: assume that the second definition doesn't hold, so either $\psi$ never holds, in which case clearly the first definition fails, or there is some minimal time $d$ where $\phi$ doesn't hold, and $\psi$ doesn't hold before $d$. In the latter case, $\phi\vee \psi$ also doesn't hold at time $d$, so the first definition doesn't hold.

---
Tags: formal-languages, formal-methods, model-checking
---


# Question
Title: Partition points in a plane with a straigth line
Given are a 2D plane and a array of points in this plane, with every point having an integer value assigned.

Is there an algorithm which, when given a ratio a/b, divides the plane with a straight line, so that the values of the points are distributed as close as possible to the given ratio?

Points may be on the dividing line, then the are counted to the 'left/upper' partition.

# Answer
> 1 votes
There is a brute $O(n^3)$ algorithm.

There are $\binom n 2 = \frac {n(n-1)} 2$ lines over pairs of points. If a line goes over $k$ points, there are $2(k+1)$ ways to rotate the line by a negligible angle, so that no points go over it and each rotation partitions the $k$ points differently.

```
For each pair of vertices (v1, v2),
  rotate the space so that v1.y = v2.y = 0
  let UP be the sum of values of vertices with positive y
  let DOWN be the same for negative y
  let L be a list of vertices with y = 0, sorted by x

  For each of L.length+1 ways to cut L in two,
    let LEFT be the sum of values of vertices in L to the left of the cut
    let RIGHT be the same for vertices to the right

    check whether one of UP + LEFT, DOWN + RIGHT or UP + RIGHT, DOWN + LEFT
     is a better partition than your previous best.

```

---
Tags: algorithms, computational-geometry, partitions
---


title: SVM math question

text:
# Question
Title: SVM math question
I'm studying support vector machines and came across this paper. The following equation doesn't make sense to me, especially the part with the 0 ∀i. Any help understanding the basics of SVMs?

yi * (xi * w + b) - 1 \>= 0 ∀i

* xi - one input
* yi - the classification (+1 or -1)
* w and b - variables to find in order to "train up" the SVM (?)

Please forgive my ignorance on SVMs, a lot is still unclear to me and I'm trying to learn these bit by bit. Thanks!

# Answer
$\forall$ means "for all", i.e., the equation

$$y\_i (x\_i w + b) - 1 \ge 0$$

is supposed to hold for every value of $i$. To learn more about that, pick up a book on discrete mathematics and read its introduction to boolean logic and propositional logic. (You might need a certain amount of background in mathematics to make sense of those equations, I'm afraid.)
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Any way to optimize this with subset caching?
I have some algorithm and I wonder whether there is a way to optimize it beyond the naive approach.

Basically I have time steps and the current time is $t\_c$. At any given time step, a couple of "ranges" are active from now up to some given time $t\_i$ (i.e. $\forall t\leq t\_i: r\_i\in R(t)$).

```
   now       -time->
   v
r1 ****
r2 ***************
r3 *******
r4 *****************************
r5 ************

```

At each time $t$ I have to calculate some *expensive* function of all currently active ranges $f(\\{r|r\in R(t)\\})$ (in the diagram I'd have to calculated $f(r\_1, r\_2, r\_3, r\_4, r\_5)$ now and given nothing changes I need $f(r\_2, r\_4, r\_5)$ 9 steps later). Afterwards *new* ranges are generated and the time moves one step further. Therefore the existing ranges slowly change. Of course, past ranges are irrelevant. That's it.

```
    now      -time->
    v
r1 ****
r2 ***************
r3 *******
r4 *****************************
r5 ************
r6 **********

```

My function is associative and cumutative, which means I could make use of any cached function results on subsets of the currently active set. It also time-scales with the number of arguments. Therefore given $f(a,b,c)$ I can calculate $f(d,a,b,c,e)$ in only two calculations rather than five.

Can you see any way to optimize this which is faster than calculating the function at each time for each active range?

# Answer
It sounds like you are not entirely clear on the properties and structure of your function $f$, which makes things harder. So, my first advice would be to spend a little more time trying to characterize them, as they may help you select suitable algorithms. That said, I will suggest several methods below, which you might find helpful. I think you might find Method 3 perfect for your needs: it should help a lot.

## Method 1: Memoize $g$

Suppose

$$f(a,b,c,\dots) = g(a)+g(b)+g(c)+\cdots,$$

where $+$ is some fast monoid operation (i.e., commutative and associative).

Then a very simple approach is: whenever you see a new range $r$, compute $g(r)$, and remember the results of this computation (use memoization so you never need to compute $g(r)$ again).

Now, at each time step, you have some set of active ranges, say $a,b,c,d$. So, compute $f(a,b,c,d)$ by computing $g(a)+g(b)+g(c)+g(d)$, where you recompute the sum from scratch but you don't need to re-compute $g(\cdot)$ values you've computed before. If $a,b,c$ were previously present and only $d$ is new, then you'll only need to compute $g(d)$. You've previously computed $g(a),g(b),g(c)$, so there is no need to re-compute those values -- you can just look them up in your memoization table. Finally, you apply the $+$ operator three times to sum up the four values $g(a),g(b),g(c),g(d)$.

The running time of this method is $O(n)$ evaluations of the $+$ operator and $O(n\_+)$ evaluations of $g(\cdot)$ per time step, where $n$ is the total number of ranges active at that time step and $n\_+$ is the number of new ranges introduced at that time step (i.e., which weren't active at the previous time step).

The advantage of this method is that it is extremely simple: it should be very easy to implement. It might be the best choice when the $+$ operator is very fast and $g(\cdot)$ is very slow, because it avoids re-computing $g(\cdot)$ but it makes no attempt to minimize applications of $+$. If $+$ is also very slow, then you might do better using one of the more sophisticated methods below.

## Method 2: Prefix sums

Suppose $f$ is as above, but now evaluting $+$ is slow. Then the basic idea of Method 2 is that you can remember prefix sums. If you've computed the sum $g(a)+g(b)+g(c)+g(d)$, then the *prefix sums* are the sums of the prefixes of this expression: i.e., the values $g(a)$, $g(a)+g(b)$, and $g(a)+g(b)+g(c)$. Using the obvious method to compute the sum, it takes no extra effort to find the prefix sums (you generate them along the way). So, you might as well remember the value of all of those prefix sums, and reuse them whenever possible.

I suggest that initially, you take all of the ranges that are initially active, you sort them by their end date (so that the longest-lived ranges come first in the sequence), and then you compute prefix sums. Say the initial ranges are $a,b,c,d$, in order of decreasing end date. Then you compute $g(a)$, $g(a)+g(b)$, $g(a)+g(b)+g(c)$, and $g(a)+g(b)+g(c)+g(d)$. The latter value is exactly $f(a,b,c,d)$, which you output. However you also remember the prefix sums. At some point in the future, $d$ will expire, so now you can throw away the value of $g(a)+g(b)+g(c)+g(d)$ and remember just $g(a)$, $g(a)+g(b)$, and $g(a)+g(b)+g(c)$. You always use the longest of those prefix sums as the beginning point for adding in new elements.

Unfortunately, it's a bit of a challenge to turn this into a full algorithm that will be really useful, so I'll jump straight to Method 3, which is a generalization of this.

## Method 3: binary tree

Here's a better method. Sort the active ranges by decreasing end date. We'll maintain a binary tree, with one leaf per active range.

Annotate each node with the result of evaluating $f(\cdot)$ on all of the ranges underneath that node (e.g., if the leaves that are descendants of that node correspond to ranges $a,b,c,d,e$, then that node will be annotated with the value of $f(a,b,c,d,e)$). Notice that the annotation on the root is just the result of evaluating $f(\cdot)$ on the set of all active ranges, so it is the desired output.

When you move on to the next step, some ranges will expire and some new ranges will be added. This means you'll need to delete some existing leaves and insert some new leaves (in the appropriate place, maintaining the sorted order).

When you delete a leaf, you'll need to update the value on each of its ancestor nodes, but each ancestor node can be updated with $O(1)$ evaluations of $+$. Insertion works similarly. So, inserting or deleting a leaf at depth $d$ takes $O(d)$ work. If you use a balanced binary tree data structure, then the depth will be $O(\lg n)$, where $n$ is the total number of leaves, so each deleted/inserted leaf will take $O(\lg n)$ work. There are a variety of possible implementations, e.g., using AVL trees, red-black trees, or other balanced tree data structures. Or, you can ignore the rebalancing operations and hope that your tree will stay approximately balanced in practice and keep your implementation simple.

Ultimately, this requires $O(n\_+)$ evaluations of $g(\cdot)$ and $O((n\_+ + n\_-) \lg n)$ evaluations of $+$ per time step, where $n$ denotes the total number of ranges active at that time, $n\_+$ the number of ranges newly introduced at that time step, and $n\_-$ the number of ranges that expired at that time step. This is significantly better than Method 1, and it generalizes Method 2.

## Method 4: Group operation

Finally, for completeness, let me mention one specific situation where one can achieve better running time. Suppose the $+$ operation has an inverse. In other words, suppose

$$f(a,b,c,\dots) = g(a)+g(b)+g(c)+\cdots,$$

where $g$ is a slow function and $+$ is some group operation. (In other words, $+$ is a binary operator that is commutative, associative, and has an inverse operator $-$ with the obvious properties: e.g., $x+y-y=x$.) Assume $+$ and $-$ are fast to compute.

In this case, there is a good solution. You can simply update the value of $f(\cdots)$ on the fly. At each time step, some new ranges get added and some get removed, so you compute $g$ of each of those ranges and add the values that are being added and subtract the ones that are being removed.

For example, suppose at time step 0 we have $a,b,c$ active; then we compute $f(a,b,c)$. Now suppose at time step 1 just $b,c$ are active: then we can compute $f(b,c)=f(a,b,c)-f(a)$, using a single computation of $g$ and a single subtraction (since we already know the value of $f(a,b,c)$, no need to recompute it). Let's say that at time step 2 we have $b,c,d$ active: then $d$ is new, so we compute $f(b,c,d) = f(b,c)+f(d)$, which requires just a single computation of $g$ and a single addition.

You can further improve this using memoization: remember the value of $g$ at all the ranges you've computed it on. Then to get from $f(a,b,c)$ to $f(b,c)$ requires just a single subtraction: there's no need to recompute $f(a)=g(a)$, since you've previously computed it.

I know you said that this doesn't apply to you, since you don't have any way to compute the inverse operation -- but I'm mentioning this for completeness, in case anyone else comes across a similar situation but does have inverses.

## More reading, background, and tangential stuff

Here's some additional reading on topics that might be helpful or interesting to you.
> 1 votes

---
Tags: algorithms
---


# Question
Title: CLRS 4.4-3 Height of recursion tree for T(N) = 4T(n/2 +2) + n
I'm having a hard time with the following question:

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n/2 + 2) + n$. Use the substitution method to verify your answer.

This is not homework, I'm just practicing myself for an upcoming exam.

The thing I'm having a hard time with is the $n/2 + 2$, what will the height be of this recursion tree?

I came up with the following formula to calculate the cost of each level after a lot of labor: $2^i n + 2^{i+2}(2^i -1)$ not 100% sure this is correct either.

Any help appreciated, really looking forward to the answer :D
I often make stupid mistakes and I just started doing algo's for my first time.

# Answer
I'll suggest two methods, but since this is your exercise, you'll have to work out some of the details. Important: study them both.

---

## Method 1 (the dumb method)

We're going to use guess-and-check. In other words, we're going to guess a solution to the recurrence $T$, and then we'll check whether our guess is correct.

How do we come up with a reasonable guess? Well, we could try stuff blindly, but I have a better suggestion. The reason this recurrence is difficult is because of the nasty $+2$ in $T(n/2+2)$. So if that's inconvenient, let's throw it away: let's look at what happens with the related recurrence where that isn't present. In other words, define a new recurrence $U(\cdot)$ by

$$U(n) = 4 U(n/2) + n.$$

Now use your methods to find a solution to $U(n)$ (e.g., recursion tree, etc.). Finally, use that formulate for $U(n)$ and let's use that as our guess for $T(n)$: let's check whether it also provides an asympotically valid solution to $T(n)$. If it is, ta-da, you are done!

I call this a "dumb" method because, while it might happen to work on this example, there's no guarantee it will work in every situation. So that's why it is helpful to know a more powerful method:

---

## Method 2 (transform of variables)

My suggestion is to first apply a change of variables to make that nasty $+2$ go away, then solve the transformed recurrence using standard methods you already know.

Here's an example. Suppose we define a new recurrence for $S(n)$ by making the definition $S(n) = T(n+3)$. (This corresponds to the change of variables $n \mapsto n+3$.) Can you derive a recurrence relation for $S(n)$? Sure, with some simple manipulation of the definitions of $S$ and $T$, you ought to be able to derive a recurrence of the form

$$S(n) = 4 S(\text{something}) + \text{stuff}.$$

In particular, I think you'll find that the $\text{something}$ has the form $n/2+\text{blah}$. So, go do it. Sit down with a pencil and work out the exact recurrence for $S(n)$ (fill in the $\text{something}$ and $\text{stuff}$ parts with their exact expressions).

Now if we were lucky, we'd get a recurrence of the form $S(n) = 4 S(n/2) + \text{stuff}$. That'd be lucky, because then you could use your standard methods to solve that kind of recurrence (now that the nasty $+2$ is gone). Unfortunately, when you work this out, you will discover that you were not lucky. The nasty $+2$ got replaced by some other $+\text{blah}$, which is still nasty (since $\text{blah}\ne 0$).

But don't give up. It turns out that $S(n)=T(n+3)$ was not lucky. So try a different definition. Try replacing the $3$ with some other number. If you play around with it a bit, I think you will discover that there is another number you can use instead of $3$ that will be lucky: it'll make the recurrence look like

$$S(n) = 4S(n/2) + \text{stuff},$$

and that's a recurrence you should know how to solve (e.g., recursion trees nad such). Once you find a solution for $S(n)$, you can plug back into the definition $S(n)=T(n+3)$ to get a solution for $T(n)$, and you're good.

This will work. It takes a little more work, but it is more general, so it is worth knowing. I suspect it is the method that your instructor wanted you to learn.
> 8 votes

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


title: Simply Typed Combinatory Logic?

text:
# Question
Title: Simply Typed Combinatory Logic?
As there is an untyped lambda calculus, and a simply-typed lambda calculus (as described, for example, in Benjamin Pierce's book Types and Programming Languages), is there a simply-typed combinatory logic?

For example, it would seem that natural types for the combinators S, K, and I would be

```
S : (a -> b -> c) -> (a -> b) -> a -> c
K : a -> b -> a
I : a -> a

```

where a, b, and c are type variables ranging over some set of types T. Now, perhaps we could get started with a single base type, Bool. Our set of types T is then Bool along with whatever types can be formed using the three patterns

```
(a -> b -> c) -> (a -> b) -> a -> c
a -> b -> a
a -> a

```

where a, b, c in T.

There would be two new constants in the language.

```
T : Bool
F : Bool

```

So, this language consists of the symbols S, K, I, T, and F, along with parentheses. It has one base type Bool, and the "function types" that can be made from the S, K, and I combinator patterns.

Can this system be made to work? For example, is there a well-typed if-then-else construction that can be formed from only S, K, I, T, F?

# Answer
Quick note, I allow parametric polymorphism (System F) in this system so that `S`, `K` and `I` can work over all types.

Notice that without pattern matching, we can't write an `if` no matter what we do. We have absolutely no operations on booleans. There is no way to distinguish `True` from `False`. Instead try

```
true : a -> a -> a
true = \t -> \f -> t

false : a -> a -> a
false = \t -> \f -> f

```

Let's let `Bool = a -> a -> a` for clarity.

```
 if : Bool -> a -> a -> a
 if = \bool -> \a -> \b -> bool a b

```

Now it's just a matter of compiling some lambda calculus expressions to combinators, which is pretty trivial.

```
if : Bool -> a -> a -> a -- Or just Bool -> Bool
if    = I

true : a -> a -> a
true  = K

false : a -> a -> a
false = K I

```
> 11 votes

---
Tags: logic, lambda-calculus, functional-programming, types-and-programming-languages, combinatory-logic
---