title: Converting CFG to PDA

text:
# Question
Title: Converting CFG to PDA
I have the following CFG,

$S \rightarrow CB$
$C \rightarrow aCa \text{ }|\text{ } bCb \text{ }|\text{ } \text{#}B$
$B \rightarrow AB \text{ }|\text{ } \varepsilon$
$A \rightarrow a\text{ }|\text{ }b$

This is the CFG for the following language:

$$L= \left\\{w \text{#} x\mid w^R \text{ is a substring of }\ x \text{, where } x,w\in \\{a, b\\}^\*\right \\}$$

I have a problem with constructing PDA for this CFG.

**My attempt**

My idea was to store characters in stack until "#" character, then as soon as the sequence of reversed characters go, pop from the stack. If at the end of input stack is empty, then we are done.

The problem is that for the following string, for example:

abbaa#aabbbbbbb(aabba)bbbbbb

when we read characters after "#", PDA will pop 4 characters, the it will see that the sequence is not valid and proceed with input. How can I return these 4 characters back so that I can check sequence again because I need full stack to proceed with accepted reversed substring that I have showed in brackets?

# Answer
There is a general method to convert any CFG into a PDA. That's what jmite meant. You can find more details on that in wikipedia, or by searching this site.

But once you realized the language is $L=\\{w\\#x \mid w^R \text{ is a substring of }x\\}$, you can forget about the grammar and directly construct a PDA.

The PDA works like what you describe in your question - it begins by putting $w$ into the stack. Then it needs to pop it out and compare it to $x$. But it might be that the substring $w^R$ is not a prefix of $x$, which causes your confusion.

The idea you are missing is the power of non-determinism: allowing the PDA to "magically" select the right way out of many possible ways to proceed.

In more details, the PDA will do the following. It will read some letters from the $x$ part of the input and just ignore them. Then, at some point which will be chosen "non-deterministically" (or, "magically", if you prefer), it will start comparing the input to the stack (and accept if there is a match; reject otherwise).

If indeed $w^R$ is a substring of $x$, there is a way for the PDA to make the right choice and start comparing the input to the stack *exactly* at the right position. This is enough to show that the PDA accepts (at least) $L$.

The concept of non-determinism is very strange, but think about it that way: the construction above defines infinitely many possibly (deterministic) PDAs: each one starts to pop the stack at a different time. "Accepting" a word in a non-deterministic way is defined as the event that **at least one** of the above machines accepts. The case of "Rejecting" a word is defined to be the event in which **all** the above machines reject.
> 3 votes

# Answer
You follow an algorithm similar to a "shift-reduce" parser. You only need one state. From this state, you can read the empty symbol and pop symbol X off the stack and replace it with the right side of any of its productions. Alternately, if the top of the stack is a terminal, and that terminal is next on the input tape, you read the letter and pop the letter. You start with S on the stack and you finish when the stack is empty.

If $\epsilon$ is the empty symbol, and $Z\_0$ is the stack bottom, your automataon's transitions then are:

$\epsilon, Z\_0/SZ\_0$

$(\epsilon, X/\alpha )$ for each production $X \rightarrow \alpha $ in the grammar

$(a, a/\epsilon )$ for each terminal $a$

There is one state, each transition loops from this state to itself. You halt when you've read all symbols and the stack is empty.
> 2 votes

---
Tags: context-free, formal-grammars, pushdown-automata
---


# Question
Title: What makes lambda calculus relevant to study?
I'm starting an undergraduate computer science course next fall, but I can't really understand λ-calculus in the context of functional programming. I may be misinterpreting this completely, but based on this definition from the Stanford Encyclopedia of Philosophy, it's just another notation for functions.

If it *is* just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?

# Answer
> 14 votes
In computer science we want to analyze and understand source-code with mathematical rigour. That's the only way to prove interesting properties (such as termination) with absolute certainty. For that we need a language with a very well-defined meaning for every construct.

In theory this could be any language with a good formal semantics. But to make things less complicated and less prone to error, it's best to use a language that is as simple as possible but still able to express any program (i.e. is Turing complete). For reasoning about imperative code, there are Turing machines. But for reasoning about functional programming, there is the $\lambda$-calculus.

The basic $\lambda$-calculus is like a functional programming language, but with a lot of 'baggage' taken out. It's not important that this be a nice language to actually write programs in, nor that it be an efficient language. Just that it is simple and expressive. For example, we don't need loops, because we can simulate them with recursion. And we don't need functions with multiple parameters, since we can simulate them with Currying.

Now, at some point you may want to prove properties about constructs that are not part of the basic (untyped) $\lambda$-calculus. That's why computer scientists have extended it in different directions over the years. For example, to reason about type-systems there are a great many variations of typed $\lambda$-calculi.

# Answer
> 1 votes
strangely a lot of books talk about $\lambda$ calculus without mentioning Lisp or Scheme, modern programming languages based on it, leaving students unfortunately with the idea that its old and abstract and mostly theoretical. studying Lisp or Scheme can be a great angle to immensely help understand $\lambda$ calculus.

> If it *is* just that, why is it advantageous to use λ-calculus over regular function notations to calculate algorithm run time?

there are many advantages to using Lisp or functional programming and calculating algorithm run time is just one possibility (although it would be helpful if you cited a ref for that). since its already in functional notation sometimes determining the formulas for run time via induction or recurrence relations may have a stronger or more obvious relationship to the original code. other types of analysis of the algorithm are simplified also.

another main advantage is syntactical simplicity. parsers for other languages are very complex but the Lisp parsers are very simple. so Lisp is a great language to study the theory of parsing in.

another key aspect is analyzing software more from a *logical* or *mathematical* lens/view rather than a "computer-scientific" perspective.

as the other answer points out, Lisp is all about recursion instead of iteration and recursion is very much at the heart of CS.

more advocation for a "$\lambda$-view" and detail can be found in \[1\], a free online and semifamous ref.

\[1\] Structure & Interpretation of computer programs, by Abelson & Sussman

---
Tags: programming-languages, lambda-calculus
---


# Question
Title: What's harder: Shuffling a sorted deck or sorting a shuffled one?
You have an array of $n$ distinct elements. You have access to a comparator (a black box function taking two elements $a$ and $b$ and returning true iff $a \< b$) and a truly random source of bits (a black box function taking no arguments and returning an independently uniformly random bit). Consider the following two tasks:

1. The array is currently sorted. Produce a uniformly (or approximately uniformly) randomly selected permutation.
2. The array consists of some permutation selected uniformly at random by nature. Produce a sorted array.

My question is

> Which task requires more energy asymptotically?

I am unable to define the question more precisely because I don't know enough about the connection between information theory, thermodynamics, or whatever else is needed to answer this question. However, I think the question can be made well-defined (and am hoping someone helps me with this in an answer!).

Now, algorithmically, my intuition is that they are equal. Notice that every sort is a shuffle in reverse, and vice versa. Sorting requires $\log n! \approx n \log n$ comparisons, while shuffling, since it picks a random permutation from $n!$ choices, requires $\log n! \approx n \log n$ random bits. Both shuffling and sorting require about $n$ swaps.

However, I feel like there should be an answer applying Landauer's principle, which says that it requires energy to "erase" a bit. Intuitively, I think this means that sorting the array is more difficult, because it requires "erasing" $n \log n$ bits of information, going from a low-energy, high-entropy ground state of disorder to a highly ordered one. But on the other hand, for any given computation, sorting just transforms one permutation to another one. Since I'm a complete non-expert here, I was hoping someone with a knowledge of the connection to physics could help "sort" this out!

(The question didn't get any answers on math.se, so I'm reposting it here. Hope that is ok.)

# Answer
> 6 votes
By Landauer's principle, if you want to take a uniform random permutation of $n$ keys to a sorted one, and not keep any bits in the computer which reveal what the uniform random permutation was, you need to erase $log n! \approx n \log\_2 n$ bits. This will take $(n \ln n) k T$ energy. On the other hand, the computation taking the sorted array and $n \log\_2 n$ random bits to the random array is reversible, and thus the energy expended can be made arbitrarily small.

Note that these are just theoretical lower bounds. The energy currently consumed by these processes on an actual digital computer bears no relation to the above analysis.

# Answer
> 3 votes
Neither. Any circuit can be made reversible by keeping track of the input, and the energy dissipation of reversible computation can be made arbitrarily small.

---
Tags: algorithms, algorithm-analysis, information-theory, permutations, entropy
---


# Question
Title: The physical implementation of quantum annealing algorithm
From that question about differences between Quantum annealing and simulated annealing, we found (in commets to answer) that physical implementation of quantum annealing is exists (D-Wave quantum computers).

Can anyone explain that algorithm in terms of quantum gates and quantum algorithms, or in physical terms (a part of algorithm that depends on quantum hardware)?

Does anyone have any ideas about that? Please tell me, if you know some links related this question.

# Answer
From \[FT11\] (emphasis added):

> Quantum annealing (QA) is a *classical* randomized algorithm ... suggested by the behaviour of quantum systems.

Thus, there is no part of QA that necessarily "depends on quantum hardware."

In classical annealing (CA), a term analogous to *temperature* is the source of the random perturbations that allow the algorithm to explore a problem's solution space. In QA, the temperature term is replaced by a term analogous to *quantum tunneling field strength*. Presumably, in a quantum implementation of QA, steps involving quantum tunneling would be carried out directly in hardware.

A comparison of the two techniques can be found here, and D-Wave's explanation here.

EDIT: from D-Wave's Processor operation documentation (emphasis added): Let there be an optimization problem of the form

$E(\vec{s})=-\sum\limits\_ih\_is\_i + \sum\limits\_{i,j\>i}K\_{ij}s\_is\_j$

where $-1\leq h\_i$, $K\_{ij} \leq +1$ and $s\_i = \pm1$. There exists an optimal solution $\vec{s}\_{gs}$ that minimizes the objective $E$. Map the problem onto a quantum Ising spin glass (QSG) Hamiltonian

$\frac{\mathcal{H}\_{QSG}(t)}{E\_0(t)}=-\sum\limits\_ih\_i\sigma\_z^{(i)}+\sum\limits\_{i,j\>i}K\_{ij}\sigma\_z^{(i)}\sigma\_z^{(j)}-\Gamma(t)\sum\limits\_i\sigma\_x^{(i)}$

**Use a physical system** to find the $|\vec{s\_{gs}}\rangle$ by evolving $\Gamma(t)$ such that

$\Gamma(0) \ll h\_i,K\_{ij}$

$\Gamma(t\_f) \gg h\_i,K\_{ij}$
> 5 votes

# Answer
The approach to quantum computing that you are referring to is something called the adiabatic model. It's actually based on continuous time evolution of quantum systems, rather than on discretized-time models (i.e. no gates). It turns out that it is possible to approximate continuous time evolution with a discrete set of gates, and so the algorithm can be implemented in any universal model of quantum computation.

In order to understand the algorithm and how it works, you need to know some physics. A Hamiltonian, $H$, is an observable which corresponds to the total energy of the system. Any eigenstate, $\psi$, of $H$ corresponds to a configuration of the system for which there is a definite energy, $E$, equal to the corresponding eigenvalue of $H$.

The dynamics of a quantum system are determined by its Hamiltonian, and for a fixed Hamiltonian, the evolution is given by $\psi(t) = e^{-iHt/\hbar}\psi(0)$.

The adiabatic algorithm is based on the adiabatic theorem, which roughly speaking, states that if you start in the ground state (the lowest energy state of the system) of some Hamiltonian $H\_0$ and slowly change the Hamiltonian as a function of time, then you will continue to remain in the ground state (or rather very close to it) of the instantaneous Hamiltonian, provided that the speed at which the Hamiltonian changes is sufficiently slow. How slow this must be depends on the minimum gap between the ground state and the next lowest energy level, and varies from one Hamiltonian to the other.

The adiabatic algorithm is simply to start in the ground state of some simple Hamiltonian, $H\_0$, for which the ground state is easy to prepare, and slowly interpolate between it and some target Hamiltonian, $H\_1$, which encodes in its ground state the solution to the problem you are trying to solve. Thus, the time varying Hamiltonian may look something like $H(t) = (1-t/T)H\_0 + (t/T)H\_1$, where $T$ is the total time for the adiabatic evolution. As long as $T$ is sufficiently large, the adiabatic theorem guarantees that the resulting state at time $T$ will be very close to the ground state of $H\_1$.

It should be noted that the linear interpolation above is certainly not the only possible choice, and indeed looking for better paths between $H\_0$ and $H\_1$ is an active area of research, since the path determines the minimum value which can be taken by $T$. None the less, the above should give you a taste of how the algorithm works.
> 7 votes

# Answer
This is an answer I gave to the question of how adiabatic quantum computing works in layman's terms on Quora. Just to warn you, it's a little simplistic and verbose. Here's the link: https://www.quora.com/Quantum-Computation/How-does-adiabatic-quantum-computation-work-in-laymans-terms/answer/Hadayat-Seddiqi

Adiabatic quantum computing (AQC, henceforth) is a fundamentally different paradigm to the quantum circuit or gate model that most researchers are working on. I will spare the details for the latter and refer you to questions such as the following:

https://www.quora.com/Quantum-Computation/How-does-quantum-computing-work

But I will point out that it's been mathematically shown that the adiabatic model and the gate model are equivalent, so that it is possible to find any equivalent algorithm that can be run on one type of machine for the other, though there is no guarantee on efficiency. That's important to note. Someone may find the adiabatic version of Shor's algorithm, but it's likely that it won't even beat classical computation methods.

In the adiabatic model, you have a few important things that go on, and they are outlined below:

-Encode your problem (in terms of a Boolean SAT problem) -Prepare initial state of qubits (program your problem) -Annealing process (slowly change from initial to final state) -Measure the system to get your answer

Looking at it that way, computing using an AQC seems very simple.

**Encoding the problem** At first you will need to translate your problem into one that the AQC can handle. In general, this will be in the form of a Boolean satisfiability problem. This will have a specific form in terms of mathematical notation, but the main idea behind it is that you will have an optimization problem that you need to find the minimum or maximum of. There will also be many constraints. Think in terms of a graph. You have a collection of nodes in a grid, and they're all connected at first. This graph is analogous to the "program" in an AQC, where the initial state of qubits are connected in a certain way.

**Initial State** For any QC, you need an initial state. In classical computing they are bits, in quantum computing they are qubits. I'll refer you again to the broader question of how QC works above to understand how qubits and QC in general work.

In AQC, the qubits have a certain connectivity. For example, if your qubits are the magnetic field direction (either up or down depending on if the current goes clockwise or counterclockwise around, but because of the Josephson junction it will be superposition of the two) through the loop of a superconducting quantum interference device (SQUID), then you have superconducting wires connecting these SQUIDs. These wires can be "turned off" as needed in order to encode the initial problem onto the device.

This is what an rf-SQUID with a Josephson junction looks like:

<sub>(source: www.quora.com)</sub>

Here is another diagram from D-Wave's blog. The right figure shows the connectivity in their own machine.

Something important to note here is that D-Wave's system is not fully connected, which you can see because nodes 1,2,3, and 4 are not connected to each other. This means that their machine is a subset of a more powerful theoretical AQC, but because of experimental constraints they have gone with the architecture shown.

**Annealing Process** Now this is where the computation actually happens. I've come up with what I think is a decent analogy, so see if it makes sense to you.

Imagine you put a block of ice in a cup, and you turn up the heat to make it melt. Your goal is to make the ice melt as slowly as possible, so that when you have your cup of water, you have absolutely zero vibrations or waves. You can imagine that by some super-heating method that if the ice cube were to instantaneously turn into water, there would be waves going everywhere since the water would be rushing out to the walls of the cup. What you want to do is heat it slowly so that this never happens, not even in the slightest. Your tolerance is, say, 99%. If your ice cube is an AQC, vibrations in the final state (the water) are "excitations", which basically mean errors and, thus, giving you wrong answers. They may be close, but they wouldn't be optimal.

So you have this system of connected qubits in SQUID form is that you prepare this system with a magnetic field that is going a certain way. You then you slowly turn off your initial state while slowly turning on your final state. So basically you're going through a mixed state of initial and final energy, though by the end there will be basically no initial parts of the problem left in the state and you're left only with the final state. An alternative way is to start with both states on, but have the initial state be much, much stronger than the final part of the state, and then slowly turn off the very large, initial state. If you find this confusing, take a look at this equation

H stands for Hamiltonian, which is just a name for a matrix that defines the total energy state of the system. The three terms, you'll notice, can be grouped into two terms really. The big Z and X are referring to the spin matrices. So in terms of this equation, your initial state is governed by the last term, and your final state is governed by the first two terms. The spin matrices show the change from the X-basis state to the Z-basis state. When you prepare your initial system of qubits, you put them all into the X-spin state and then anneal to the Z-spin state. Imagine that h and J are much, much smaller than K initially. When you anneal, you slowly turn off K so that when you're done, you're only left with whatever is in the first two terms. This is how the annealing process works. You can think of a plot that looks like a symmetric X; one cross of the X is the linearly decreasing K coefficients, and the other cross is the linearly increasing h and J coefficients.

Now in order to anneal properly so that you get the correct answer, you need to be sure you're giving it enough time to settle without excitations. The above equation is time-dependent, or more specifically, the h, J, and K terms are time-dependent. Now the adiabatic theorem will tell you that unless you run for t = infinity, you will not reach 100% accuracy. Still, we can get close. Even 90% isn't so bad, given that you're quickly reaching a somewhat optimal solution.

In terms of the math and quantum mechanics, your state vector always needs to be in the lowest eigenstate of the Hamiltonian. An eigenstate, in linear algebra, would be equivalent to an eigenvector of some matrix. If you're familiar with quantum mechanics, you'll know that particles can only be in discrete energy states. The energy of this system would be the Hamiltonian, which is a matrix, and the lowest energy state is given by the lowest eigenvector of this Hamiltonian. If you wanted to know the actual energy level, that would be the lowest eigenvalue that goes with the aforementioned eigenvector/eigenstate. Now when you're annealing, you always want to be in the ground state. This is why you must move slowly, because if you move too quickly you are imparting energy into the system, causing excitations and jumps to higher energy levels. This is not good because that's where your errors come from.

**Final State** Once you've gone through the annealing process, you'll wonder a few things. How do I know I've gotten the right answer? How much time should I have given my program to run? Is there a way to do some on-the-fly error correction?

Well, you will have to do tests on your problem to know if you got the right answer. Typically if you're solving an NP-complete problem, you can check if your solution is correct pretty quickly. Still, you will want to run the computation many times until you put that particular algorithm to use in any serious case. There are measures for this as well, however, and they have to do with tracking the actual energy of the Hamiltonian, finding its ground state eigenvector, and then comparing it with what your qubit state actually is. The inner product of the two will show you your error. Note that this can only be done theoretically, as you wouldn't be able to track your quantum state without observing it (and therefore, changing it).

On the fly error correction is also possible in a simulation of an AQC. Let me back up here. There is an idea that you can write some numerical software so that you can simulate the annealing process and come up with a time-scheme for your particular algorithm. Since it's a simulation, you have access to your state vector at all times and you can measure the predicted error according to the mathematics. You can do on-the-fly error correction by looking at the measures of error and correctness, and then adjusting your annealing timesteps accordingly. Take a look at this graph:

This is what is called the eigenspectrum of a 1-qubit simulation. Basically, it is showing you the energies through the annealing time for 1 qubit. Look at the x-axis as time. The bottom curve is the ground state, and the upper curve is the first excited state. Notice how at some point you will get that the two curves are very close. This is a crucial point, because the smaller this energy "gap" is, the more likely it is that the state of the system will jump to this higher energy state instead of stay in the ground state. Clearly this is a time where you want to move very slowly. Conversely, when the energy gap is very large, you can move rather quickly without worrying if you're going to jump to a higher state since it's pretty unlikely. You can come up with a time-scheme that means you go very fast up until that n = 0.5 point, and start to go much more slowly until you've passed the small-gap threshold.

Anyway, so that's basically it. AQC hasn't been around for a long time, so people are still figuring out a lot of things about it, like how to characterize that energy gap and how they're related to your annealing times. It has lots of potential applications, of which I make note of in my answer to the question I linked at the top of this answer.
> 5 votes

# Answer
will take this question as basically "describe/clarify the approach of Dwave systems computers for quantum annealing & QM computation". a basic announcement of their approach in their initial Orion computer can be found in \[1\] and is apparently also the design used in later iterations.

another way of looking at it is their idea is to find an NP complete problem that is closely related to the natural physical dynamics and energy state evolution of a quantum mechanical qubit system. in this case it is Ising model(s), a mathematical model of ferromagnetism in statistical mechanics. it has been proven theoretically that finding solutions to the Ising model is NP complete (including the 2d version implemented in DWave computers).\[2\] but note a link apparently with further detail referred in \[1\] is currently missing on their site.\[3\]

so then the idea is that any NP complete problem can be converted to the 2-d Ising model problem. but note that conversions between most practical problems would involve many qbits and Dwave's current limit is 128 qbits (Dwave1 "Ranier"). they have announced a 512 qbit version "Vesuvius" that hasnt been released yet. DWave recently announced a sale to Lockheed Martin of the Dwave1 machine and for further development.\[4\] a detailed scientific paper was released in Nature\[5\].

\[1\] Quantum Computing Demo Announcement, 2007 Dr Georde Rose, Dwave systems

\[2\] The Ising Model Is NP-Complete Barry A. Cipra

\[3\] "two dimensional Ising model in a magnetic field" **currently 404**

\[4\] A Strange Computer Promises Great Speed

\[5\] Quantum annealing with manufactured spins Johnson et al
> 2 votes

---
Tags: algorithms, randomized-algorithms, quantum-computing
---


title: NP hardness through Restriction

text:
# Question
Title: NP hardness through Restriction
Let's say I have a decision problem $P$ on graphs for which I know that it is NP-hard on graphs with maximum degree $d$. Does this then imply that it is NP-hard on $d$-regular graphs? Although it might seem obviously true, maybe it is inherent in the reduction to show that $P$ is hard, that some vertices have degree less than $d$.

# Answer
> 6 votes
No, it is not true in general.

A general problem being NP-Hard does not imply a specialization will be NP-Hard. It is true the other way round.

For instance, MAX-CUT is NP-Hard for general graphs, but for the class of planar graphs, it is in P.

In your case, the $d$-regular graphs are a special case of graphs of max degree $d$, so NP-Hardness for max degree $d$ is not an automatic proof of NP-Hardness of $d$ regular graphs.

In fact, for a concrete example, look at this cstheory question: Is there a problem that is easy for cubic graph but hard for graphs with maximum degree 3? with the following answer(by David Eppstein) in the affirmative (copied for convenience):

> Here's a reasonably natural one: on an input $(G,k)$, determine whether $G$ has a connected regular subgraph with at least $k$ edges. For 3-regular graphs this is trivial, but if max degree is 3 and the input is connected, not a tree, and not regular, then the largest such subgraph is the longest cycle, so the problem is NP-complete.

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


# Question
Title: Is there an algorithm for checking if a string is a catenation of palindromes?
Is there a linear-time algorithm to check that a sequence of characters is a concatenation of palindromes? The only thing that comes to my mind is the naive solution:

```
1. k = 1
2. Split string into k substrings (all possibilities) and check
3. k++
4. repeat

```

Note: the answer is trivially yes if length 1-strings are defined to be palindromes. Let's assume that this is not the case.

# Answer
Assuming you want disjoint palindromes, this is known as the PALSTAR problem, and there is a linear time algorithm by Zvi Galil and Joel Seiferas. A Linear-Time On-Line Recognition Algorithm for \`\`Palstar'.

You can find an explanation of the algorithm in the book here: Text Algorithms (look at linked page and the preceding pages).

If you are ok with a quadratic time algorithm, straight-forward dynamic programming seems to work.

Given a string $s\[1,\dots n\]$, we maintain an array telling us whether $s\[1,\dots j\]$ can be decomposed into palindromes.

We also maintain an 2D table which tells us whether $s\[i, \dots j\]$ is a palindrome or not. This we can construct in $O(n^2)$ time by choosing a center and moving two pointers outwards, checking for palindromes with that center. Do this for each possible center: $\Theta(n)$ centers, each taking $O(n)$ time.

Now, you can check $s\[1, \dots j+1\]$ whether can be decomposed into palindromes, by checking for each $1 \le i \le j-1$ whether $s\[1,\dots i\]$ can be decomposed, and if $s\[i+1,\dots, j+1\]$ is a palindrome (using the above 2D table). This yields a $\Theta(n^2)$ time and $\Theta(n^2)$ space algorithm.

The space usage can be brought down to $O(n)$, if you use Manacher's on-line algorithm to compute whether $s\[i+1,\dots j+1\]$ is a palindrome (as $i$ goes from $j-1$ to $1$), basically getting rid of the 2D table.
> 8 votes

# Answer
If overlapping is allowed, it can be done in linear time (in the size of the input string).

## Some definitions

Let's define the concept of *maximal palindrome*:

A **maximal palindrome of radius k** of a string S is a substring S' such that

* starting from the centre, S' reads the same k characters in both directions
* but not for k+1 characters
* k \> 1 (so a single character is not a palindrome)

for example, if `S = banana`, then `S' = anana` is a maximal palindrome of radius 2.

A **maximal palindrome** is a maximal palindrome of radius k for some k.

For example, if `S = banana`, `"ana"`, `"anana"`, are all its maximal palindromes.

## Using maximal palindromes

Now, if we could **locate all maximal palindromes of a string**, it would be simple to check if the whole string is a concatenation of palindromes.

Take `S = abbaccazayaz`. Its maximal palindromes are:

* abba, centered between position 2 and 3, radius = 2
* acca, centered between position 5 and 6, radius = 2
* zayaz, centered in position 10, radius = 2

so "abba" spans over \[1..4\], "acca" spans over \[4..7\], "zayaz" spans over \[8..12\]. Since the concatenation of this three palindromes (overlapping is permitted?) spans over the whole string, it follows that "abbaccazayaz" is concatenation of palindromes.

## Computing maximal palindromes in linear time

Now, it turns out that **we can locate all maximal palindromes of a string S in linear time**! `*`

The idea is to use a suffix tree for S equipped with constant-time lowest common ancestor queries.

So we can check if a string S of length m is a concatenation of palindromes in O(n) time.

`*` Gusfield, Dan (1997), "9.2 Finding all maximal palindromes in linear time", Algorithms on Strings, Trees, and Sequences
> 4 votes

# Answer
Suppose Palindrome\[\]\[\] is an array and Palindrome(i,j) is a function which checks, whether substring from i to j is palindrome and returns 1 if is palindrome or returns infinity if is not palindrome, and you looking for smallest number of partitions, create it bottom up:

$$Palindrome\[i\]\[i\] = 1.$$ $$\forall 0\le i \< j \< n : Palindrome\[i\]\[j\] = \min\\{Palindrome(i,j), \min\_{i\le k\<j} \\{Palindrome\[i,k\] + Palindrome\[i+1,k\]\\}\\}$$

You should fill $O(n^2)$ cells and each cell takes at most $O(n)$ so algorithm is $O(n^3)$, with a little modification (preprocessing) you can improve it to $O(n^2)$, Also finding this partition is not hard.
> 2 votes

---
Tags: algorithms, efficiency, strings
---


# Question
Title: How does the problem of having a coffee-machine close relate to vertex cover?
> Meeting rooms on university campuses may or may not contain coffee machines. We would like to ensure that every meeting room either has a coffee machine or is close enough to a meeting room that does have a coffee machine. (For any two meeting rooms, the architect has told us whether or not they are close enough.) Our problem is to determine among all the meeting rooms of any university campus, which ones should have coffee machines so that we use as few coffee machines as possible. Specify this problem as an optimization problem on a graph. Formulate the corresponding Coffee-machine Decision Problem (abbreviated Coffee). Prove that the Coffee Machine Decision Problem is NP-complete.
>
> Hint: You could use Vertex Cover. For every edge, add two more edges and one more vertex.

I'm confused at the hint given and why this problem isn't just a straight reduction from Vertex Cover. What's the point of adding two more edges and a vertex for every edge?

# Answer
As I already pointed out in my comment, there is in fact a need for a transformation of the problem. The problem you ask for is not known as vertex cover, but as dominating set. The proof then goes as follows:

We transform an instance of vertex cover $(V, E, k)$ as follows (we assume that the graph $(V,E)$ is connected). For every edge - just as the hint says - add two edges and one vertex. More precisely, for an edge $uv \in E$, add a new node $w \not\in V$ and edges $vw, wu$ to the graph. The resulting graph constitutes an instance of Coffee in the obvious way, that is, the "close-enough"-relation is represented by edges and the meeting rooms are represented by vertices. Let $(V', E', k)$ denote the instance of coffee produced by the transformation.

We now need to show now that $(V, E)$ has a vertex cover of size $\leq k$ if and only if for $(V', E')$ it suffices to use $\leq k$ coffee machines.

"$\Rightarrow$": Let $v\_1, \ldots, v\_l, l \leq k$ be a vertex cover of $(V,E)$. It is clear that the same choice of nodes produces a valid choice for coffee machine placement on $(V', E')$, as we assumed $(V, E)$ to be connected.

"$\Leftarrow$": Let $v\_1, \ldots, v\_l, l \leq k$ be a valid choice for coffee machine placement. WLOG, assume that $\forall i \in \\{1, \ldots, l\\}: v\_i \in V$, for if $v\_s \in V' - V$ with $1 \leq s \leq l$, we can obtain another valid choice for coffee machine placement by replacing $v\_s$ with $v \in V$ such that $vv\_s \in E' - E$, that is, with one of the two nodes "between" which $v\_s$ was inserted by the transformation. Note that these two nodes were also precisely the ones that were covered by choosing $v\_s$ to have a coffee machine. By construction, there must have been an edge between the two nodes and an edge between $v\_s$ and each of the two nodes. So by replacing $v\_s$ with one of them, we don't shrink the set of covered nodes. Then, $v\_1, \ldots, v\_l$ constitutes a vertex cover of $(V, E)$. To show this, let $uv \in E$. By construction, there is $w \in V' - V$ and $uw, wv \in E' - E$, and no other edges are incident to $w$. As $(V', E')$ covers $w$, one of $u$ or $v$ need must have been chosen as places for a coffee machine, and thus, $uv$ is incident to at least one node in $\\{v\_1, \ldots, v\_l\\}$. Thus, $v\_1, \ldots, v\_l$ is a vertex cover of size $l \leq k$.
> 5 votes

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


# Question
Title: Prove NP-completeness of deciding whether there is an edge-tour of at most a given length
We are given a graph G, integer b \< |E|, and subset F in E. The problem is to detect whether there is a cycle in the graph with length at most b and includes each edge in F. Prove that this is NP Complete.

I'm thinking of reducing from Hamiltonian Path, but still can't think of the appropriate transformation function.

# Answer
It is a standard variation of the Travelling Salesman Problem.

To force an edge to be a part of the answer, break it in half and insert a new vertex.

**Update** A reduction in the other direction consists of "breaking all vertices in two".

More precisely, given a directed graph $G$, form another graph $G'$. For each vertex $v$ in $G$, create a pair of vertices $v\_i$, $v\_o$ in $G'$. For each edge $(uv)$ in $G$, create an edge $(u\_ov\_i)$ in $G'$. Also, for each $v\_i$, $v\_o$ add an edge ($v\_iv\_o)$, and let it belong to $F$. Now every cycle in $G'$ that contains all edges in $F$ also contains all vertices, and corresponds to a Hamiltonian cycle in $G$.
> 2 votes

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


# Question
Title: How to distinguish between the different frequency domains?
Sometimes the terms 'Fourier domain', 'complex frequency domain', 'Frequency domain' and 's domain' are used interchangeably. Take these answers here for example.

Can you really use them interchangeably all the time, without being technically wrong? So, could you describe what would be wrong if I would replace 's domain' by 'fourier domain' for example? Or replacing 'complex frequency domain' by 'frequency domain'?

# Answer
Hopefully whoever you are talking to would actually define the terms they were using before they started slinging them around. I've heard some of these used in multiple contexts. Wikipedia has an article that tries to encompass some of the different things people might be talking about when they use the term *frequency domain*.

The *domain* we are referring to here is the well-defined mathematical term for the set of legal inputs to a function. There are multiple kinds of transforms (Laplace, Z, various kinds of Fourier transforms). The domains we are referring to are the (mathematical) domains of the function that results from the transform.

I tend to think of the *s-domain* as being associated with the Laplace transform: $F(s) = \mathcal{L}\[f\] = \int\_0^{\infty} e^{-st}f(t) \mathrm{d} t$. The function $F(s)$ is potentially defined for the entire *continuous* complex plane, so the domain is the complex plane. (Although for most functions $f$ there would be a region of convergence.) I haven't personally heard the term s-domain in any other context. For the Z transform you might hear "Z-domain" (which is also the entire continuous complex plane).

I think if I heard a scientist use the term *Fourier domain* my initial assumption would be that they were (probably) talking about the Fourier decomposition of a *periodic* function into a Fourier series. (If I heard an engineer use the term Fourier domain I would think they were probably talking about a discrete Fourier transform, see below.) Most people who use Fourier series in their daily work use the exponential Fourier series: $c\_n = F(n) = \mathcal{F}\[f\] = \frac{1}{2\pi}\int\_{-\pi}^{\pi}f(x)e^{-inx}\mathrm{d}x$. So the domain here (the subscript $n$ of $c\_n$) is the integers. (If I were talking to a student I would assume they were talking about the sine/cosine version, which is also defined across the integers (but inconveniently with two different series across the non-negative integers (once for sines and once for the cosines))).

For an engineer, and especially a computer engineer like me, I would assume that we were talking about the discrete Fourier transform. This applies to periodic functions that are band limited (i.e., have very little energy in frequencies above some value.) In that case the time (or space)-domain signal can be sampled at a finite rate and the transform is: $X\_k = \mathcal{F}\[\\{x\_n\\}\] = \sum\_{n=0}^{N-1}x\_n e^{-2\pi i k n / N}$. Here again the domain (the subscript $k$ of $X\_k$) is the integers, and in this case just a finite sequence of integers $\\{0, N-1\\}$.

Finally, if I was talking to a scientist or mathematician and they used the term *Fourier domain*, my initial assumption that they were talking about a Fourier decomposition might be wrong. They might instead be talking about a *continuous* Fourier transform: $F(\omega) = \mathcal{F}\[f\] = \int\_{-\infty}^{\infty}f(t)e^{-2\pi i \omega t} \mathrm{d} t$. The domain of the function $F$ is the entire real line. Note that there is some similarity with the Laplace transform but with the Fourier transform we are *typically* only looking at $s=2\pi i \omega$, the complex unit circle, (although sometimes it might be useful to look at the rest of the plane), and for the Laplace transform we are only looking at positive time.

*Complex frequency domain* could refer to the continuous Fourier transform, I suppose, but I would tend to think of it as referring to the same thing as the s-domain.

All these transforms are related, but in any conversation you need to be clear whether the time domain is continuous or discrete and whether the time domain function/signal repeats or not. You should also make clear whether the time domain function's *range* is real or complex. Then in the frequency domain you might be talking about complex frequencies (like in the Laplace transform or Z transform) or real frequencies, and, if real frequencies, continuous or discrete. Sometimes you can infer from context, but sometimes not. The *range* in the frequency domain is more often the complexes rather than the reals.

You should start every conversation with a boring list of definitions.
> 4 votes

---
Tags: terminology, fourier-transform
---


# Question
Title: Is there a difference between pure binary and binary?
In some books and on the internet I occasionally find "pure binary" and "binary" on its own, is there a difference between these two terms? If so, can someone describe briefly what they are?

# Answer
> 3 votes
I'm guessing here for lack of context, but I think the following distinction is reasonable.

A *binary* encoding is anything that maps stuff to bit strings. There are many, including two's complement, IEEE float, ASCII, and so on.

*Pure binary* probably refers to bland natural numbers written in base two, i.e. if $n\_{(2)} = a\_k\dots a\_0$ then

$\qquad\displaystyle n = \sum\_{i=0}^{k} 2^ia\_i$.

# Answer
> 1 votes
The only contexts I know where *pure binary* is used when referencing the C standard which has a definition for the concept

> A positional representation for integers that uses the binary digits 0 and 1, in which the values represented by successive bits are additive, begin with 1, and are multiplied by successive integral powers of 2, except perhaps the bit with the highest position.

The rationale for the C standard mentions the desire to avoid things like Gray code.

---
Tags: terminology, encoding-scheme
---


# Question
Title: From Whence the Randomization in Randomized Quicksort
Cormen talks briefly about the advantages of picking a random pivot in quicksort. However as pointed out here(4th to the last paragraph):

> Using a random number generator to choose the positions is relatively expensive

So how is picking a random pivot actually implemented in practice, and how random is it? It can't be too expensive, since from what I understand one of quicksort's main advantages over other $\cal{O}(n \lg n)$ sorts is the small constant factors, and spending allot of cycles picking pivots would undermine that advantage.

**EDIT**

As an example, the `C` code from "Three Beautiful Quicksorts" actually calls the `C` library `rand` function:

```
int randint(int l, int u) {
    return rand()%(u-l+1)+l;
}

void quicksort(int l, int u) {
    int i, m;
    if (l >= u) return;
    swap(l, randint(l, u));
    m = l;
    for (i = l+1; i <= u; i++)
        if (x[i] < x[l])
            swap(++m, i);
    swap(l, m);
    quicksort(l, m-1);
    quicksort(m+1, u);
}

```

While the pivot picking code here is clearly $\cal{O}(1)$, it would seem that the hidden $c$ here is relatively high.

# Answer
> 4 votes
Take a look at McIllroy and Douglas' "A Killer Adversary for Quicksort" (Software -- Practice and Experience 29(4): 341-344 (1999)) or Crosby and Wallach's "Denial of Service via Algorithmic Complexity Attacks" for the *reason* behind randomizing. Quicksort behaves *very* badly if you pick (nearly) the largest/smallest as pivot each time. For randomization to make sense, it has to *be* random (if I know how you pick pivots *deterministically*, I can cook up an array that forces you to go into $O(n^2)$ behaviour, see the paper mentioned for details). But a fancy RNG is costlier than, say, taking 3 or another smallish odd number of elements, and pick the median of those as pivot, which is another way to counteract bad behaviour. So if you choose randomization, use a *fast* RNG seeded appropiately (probably a linear congruential scheme will be enough).

Algorithms can (and should) be compared by $O(\cdot)$, but if you are talking about different implementations of the same algorithm one must switch to more detailed analysis. In fact, Sedgewick and Flajolet in "An introduction to the analysis of algorithms" argue that one shouldn't use $T(n) = O(f(n))$ at all, but should strive to get $T(n) \sim f(n)$ type asymptotics.

# Answer
> 1 votes
So after taking the time to sit down and actually watch Bentley's google lecture, Three Beautiful Quicksorts, it turns out that randomized pivot's *are not* faster than other methods. Specifically, according to Bently - who with McIlroy - rewrote the standard C library qsort function, we have the following from their paper, Engineering a Sort Function:

* $1.386\\;\cdot n \lg n$ average comparisons using first, middle or a randomized pivot
* $1.188\\;\cdot n \lg n$ average comparisons using a median of 3 pivot
* $1.094\\;\cdot n \lg n$ average comparisons using a median of 3 medians pivot

According to the above paper:

> Our final code therefore chooses the middle element of smaller arrays, the median of the first, middle and last elements of a mid-sized array, and the pseudo-median of nine evenly spaced elements of a large array.

I read the following in Data Structures Using C, by Tenenbaum, Langsam and Augenstein:

> It is possible to speed up quicksort for sorted files by choosing a ***random*** element of each subfile as the pivot value. If a file is known to be nearly sorted, this might be a good strategy ( although, in that case choosing the middle element as a pivot would be even better ). ***However, if nothing is known about the file, such a strategy does not improve the worst case behaviour***, since it is possible (although improbably) that the random element chosen each time might consistently be the smallest element of each subfile. As a practical matter, sorted files are more common than a good random number generator happening to choose the smallest element repeatedly.

In their book they use the Hoare partition scheme. Further down they say:

> It can be shown, however, that on the average (over all files of size $n$), the quicksort makes approximately $1.386 n \lg n$ comparisons even in its unmodified version.

He's referring here to picking the first element as the pivot.

**EDIT**

I think I just stumbled on the answer to how a deterministic selection of pivot outperforms a randomized one.

Question 9.3-3 in Cormen is, "*Show how quicksort can be made to run in $O(n \lg n)$ time in the worst case.*"

The answer is to use deterministic selection to select the median element each time. Since deterministic selection runs in $O(n)$ time worst case, you get the worst case recursion $$T(n)=2T(n/2)+Θ(n)=Θ(n \lg n)$$ for this deterministic quicksort, admittedly with a large hidden constant factor in there.

I think that what Bentely is doing is an extension of this idea using a pseudo median. Bentely's paper references another paper which quantifies the quality of these pseudo medians.

The cost of computing the pseudo median is $\Theta(1)$ whereas finding the real median is $O(n)$. This is probably a big part of where his very small constant factor comes from. I assume that the paper Bentely references proves somehow that the pseudo median is "good enough" to guarantee a high enough percentage of good splits by the partition function to give the above run times.

---
Tags: algorithms, randomized-algorithms, quicksort
---


title: Loop Invariants as Tautologies

text:
# Question
Title: Loop Invariants as Tautologies
Would it be correct to characterize loop invariants as a type of tautology? I ask since the invariant must basically always be true, before the loop starts, before each iteration and after the loop terminates. I realize that there is the possibility that the invariant could become false during the body of the loop. But since inside the loop "doesn't count" is it fair to characterize the invariant as a tautology?

# Answer
> 5 votes
A Tautology is a formula (in a certain logic) that is true under *every* model of that logic. That is, it is equivalent to the formula "$True$".

A loop invariant, however, is a certain claim that is usually true under some models, and false under others (a model in this case is an algorithm). Then, you prove that the invariant is true under your specific model.

If you add axioms to your logic that forces then only model to be the one of your specific program, then indeed this would be a tautology. But such a process (adding axioms and proving that something is a tautology), is what is more commonly known as "proof". (For clarification: even if you add enough axioms, you may not be able to prove your claim, even if it's a tautology, in case of incomplete systems).

For example, consider a loop that increases a variable $i$ by $1$. An invariant of the loop may be that if before the loop $i\>0$, then after the loop $i\>0$. Indeed, this loop satisfies it. But it is not a tautology, since we can come up with other loops that do not satisfy it.

# Answer
> 5 votes
The word tautology is a technical word. The following is a tautology of classical propositional logic.

> $\vdash p \lor \neg p$

When interpreted over the natural numbers, the following is a theorem.

> $ (\mathbb{N},\<)\vdash \forall x. \exists y. x \< y$

But we do not say it is a tautology in the strict logical sense of the word because there are structures where this is not true.

> Considering $S = \\{a,b\\}$, $\<$ defined as $\\{(a,b)\\}$, we have $(S,\<) \not \vdash \forall x. \exists y. x \< y$

Similarly, if you think of a loop $P$ as implicitly defining the axioms of a theory, then a loop invariant $I$ as satisfying

> $P \vdash \text{Every execution satisfies } I $

Thus, in exactly the same way as the existence of successors is a theorem of arithmetic, a loop invariant is a theorem of a logical theory defined by the program. A loop invariant is not a tautology in the standard mathematical sense of the word tautology. A tautology in this context would satisfy

> $ \vdash \text{Every execution satisfies } I $

From which we can conclude that every tautology is a loop invariant, but not every loop invariant is a tautology.

# Answer
> 4 votes
I am guessing that, by "tautology," you mean a property that is true in *all* states. (I have seen some Lecturers use the term in that way, e.g., $x \> 1 \Longrightarrow x \> 0$, which is true in all states no matter what $x$ is, might be called a "tautology". The technical definition of "tautology" in logic is more narrow, but I will continue to use your terminology.)

A loop invariant is only true at a particular program point in the loop. It is true for every state encountered at that point, but it might be false for states encountered at other program points (inside the loop as well as *outside* the loop). So, clearly, it is not a "tautology" in the sense I stated above.

However, there is an interesting proof rule formulated in Reynolds's extension of Hoare Logic. If, in a particular piece of code, there are no operations that affect the truth/falsity of an assertion, and we know that the assertion is true at the beginning of the code, then we can pretend that the assertion is a "tautology" in the middle of that code.

A good example of this is a binary search procedure for an array $A$. Before the procedure starts, the pre-condition states that the array is sorted. Inside the binary search procedure, we don't do anything to modify the array. So, it will continue to be sorted throughout the procedure. Reynolds's rule says that, for the duration of the procedure, we can pretend that "$A$ is sorted" is a "tautology". This is a useful trick to use. Without it we would need to add "$A$ is sorted" in *every* assertion in the middle of the procedure, and we can see that it is quite pointless to keep repeating this silly condition because we are never modifying the array. Reynolds's rule allows to avoid the silliness.

For interesting applications of this rule, see the Chapter 5 of Reynolds's Craft of Programming.

---
Tags: algorithm-analysis, logic, correctness-proof, loop-invariants, program-correctness
---


# Question
Title: Bellman-Ford parent pointer (?) negative cycle
First of all, let me preface by saying that this question is not completly new but the original question hasn't been answered. More important, this is only basic question on understanding the proof itself.

So after some search in the site I found the following question : Bellman-Ford algorthm and negative cycle proof.

The guy is trying to understand how to prove *that a cycle in parent pointer is necessarily a negative cycle*.

My question is very basic and isn't duplicate, I just couldn't find anything in the document on the related question which answers my question.

What does it mean a cycle in the parent pointer? I mean I could a graph whereas the cycle in the parent pointer isn't a negative cycle... I don't understand why It must be a negative cycle.

See an example of a graph I have in mind :

Now suppose the first node we start with is (a) and suppose the we travling the edges in the following order: ab,bc,cd.

and here we goes, we have a cycle in the parent pointer, and as far as I understand that is (c) becuase it is the parent of (d) and yet the cycle isn't negative cycle.

# Answer
In the notation here, a vertex $v$ is called a parent pointer of a vertex $u$, if a shortest path to $u$, found so far in the algorithm, has $v$ preceding $u$. So in the graph above, starting at $a$ and moving to $b,c,d$ in that order, the parent pointers are $a,b,c$ respectively for $b,c,d$.

We say there is a loop in parent pointers if we have vertices $v\_1,v\_2, \ldots ,v\_n$ such that $v\_i$ is a parent of $v\_{i+1}$ and $v\_n$ is a parent of $v\_1$. Notice that this is not happening in the earlier example. But if we change the weight of edge $(c,a)$ to $-3$, then we have $a$ as parent of $b$, $b$ parent of $c$ and $c$ as parent of $a$, forming a loop in parent pointers, indicating a negative cycle.

Proof for why this finds negative cycles is given in the document referred in that earlier post

**Edit:**

Suppose we have found a cycle $v\_1,v\_2,\ldots , v\_n$ in parent pointers ($v\_i$ is parent of $v\_{i+1}$ and $v\_n$ is parent of $v\_1$). Let $P(v)$ denote the shortest path length obtained to vertex $v$ so far. Then, as $v\_i$ is parent of $v\_{i+1}$, we get $P(v\_{i+1}) = P(v\_i) + w(v\_i,v\_{i+1})$, where $w(u,v)$ is weight of the edge from $u$ to $v$. So $P(v\_n) = P(v\_1) + \sum\_{i=1}^{n-1} {w(v\_i,v\_{i+1})}$. We have reached $v\_n$ so far and now looking at its neighbour $v\_1$. And $v\_n$ is made parent of $v\_1$. Which means the shortest path length to $v\_1$ ($P(v\_1)$) found so far is bigger than the path coming from $v\_n$. That is, $P(v\_1) \> P(v\_n) + w(v\_n,v\_1)$. Hence,

$$ P(v\_1) \> P(v\_1) + \sum\_{i=1}^{n-1} {w(v\_i,v\_{i+1})} $$ $$ 0 \> \sum\_{i=1}^{n-1} {w(v\_i,v\_{i+1})} $$

So any cycle in parent pointers corresponds to a negative cycle in the graph.

Note that this is only one half of the proof. We still need to show the converse (whenever there is a negative cycle in the graph, we will get a cycle in parent pointers).
> 1 votes

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


# Question
Title: The difference between a bit and a Qubit
Ok, I have done a lot of research on Quantum computers. I understand that they are possibly the future of computers and may be commonplace in approximately 30-50 years time.

I know that a Binary is either 0 or 1, but a Qubit can be 0 or 1. But what I don't understand is how it can be anything other then 0 or 1. Surely a computer can only understand on and off, despite however fast it may be?

# Answer
> 5 votes
Probably the easiest analogy is to probabilities. If your computer can flip fair coins, you can think of each coin being in state Tails with probability 1/2 and in state Heads with probability half. So it's appropriate to think of a coin not as a bit but as a vector of two elements $(p\_T, p\_H)$, where $p\_T$ is the probability of tails, $p\_H$ is the probability of heads and we have that $p\_T \geq 0$, $p\_H \geq 0$, and $p\_T + p\_H = 1$. Once we sample a coin its state "collapses" to either tails or heads.

Just about the same happens with qubits. You can also think of quibit as being "in between" two states. It's also easiest to think of qubit not as a bit but as a vector of two elements $(q\_0, q\_1)$. Now, however, we allo $q\_0$ and $q\_1$ to be negative, and even further, to be any two complex numbers, as long as $|q\_0|^2 + |q\_1|^2 = 1$. Just as with sampling coins, once you measure a qubit, it collapses to either $0$ or $1$, and in fact you get $0$ with probability $|q\_0|^2$ and $1$ with probability $|q\_1|^2$. However, and this is the crucial part, these quantum probabilities can be made to cancel each other because they take negative values; this cannot happen with classical probability. This is the power of qubits.

BTW these complex valued quantities describe amplitudes and are related to the wave-particle duality, i.e. the discovery that particles in fact behave as waves, until you measure them, and then they behave as particles. The cancelation I am talking about is in fact interference between waves. So another answer to your question is that a qubit is not a discrete object that's either in one state or not, it's a wave..until you measure it.

# Answer
> 3 votes
Here is the crux of the matter.

> what I don't understand is how it can be anything other then 0 or 1.

This is actually a physics question in disguise, but I think that this forum is still a good place to address it. The two key facts are that information is physical at its root, and that physics is described well by quantum mechanics.

**On the physical storage of information**

What is a "bit"? It's a system with two easily distinguishable states. This could be a zero or a one written on paper; those are clearly distinguishable symbols, and importantly the ink and the paper are fairly stable with time, so that the ink on the paper can be used to "store" that information. (If it weren't stable, books would have to work differently, and the main reason why we have books is for storage of information.) In conventional electronics, we implement bits by having wires with two different voltage levels, "high" and "low" — separated by a gap of of *other* voltages, which we actively try to prevent the wire from having; but this gap ensures that the "high" and "low" voltages are easily distinguished from one another. In hard drives, the distinct states are represented by magnetic domains pointing in different directions. But in each case, a bit is represented by the states of a physical system which we can easily distinguish from one another.

**A simple quantum-mechanical system**

An example of a physical system with two easily distinguished states, among very small physical systems, is the orientation of the spin of a single particle, such as a proton. "Spin" is a vector quantity which is akin to angular momentum (hence the term), but does not actually arise from the particle revolving on an axis. Nevertheless, it has a magnetic moment (*i.e.* it acts like a microscopic bar magnet), and we can talk about which direction that bar magnet points: the direction in this case is what "spin" refers to. In particular, we can easily distinguish when it is pointing "up" from when it is pointing "down", *e.g.* using equipment such as in the Stern–Gerlach experiment.

There are other ways that the spin of a proton can point. If we use X, Y, and Z axes, and if "up" is in the +Z direction, we can also consider the spin pointing in the +X direction, the +Y direction, the −X direction, or in fact any direction described by a non-zero vector in three dimensions. Furthermore, the +X direction is distinguishable from the −X direction, and more generally any direction is clearly distinguishable from the opposite direction.

**Measurement of a quantum system**

In the usual representation of qubits, we identify 0 and 1 with the spin-directions +Z and −Z respectively. However, all of the other spin directions, such as +X, −X, +Y, −Y, and all of the other directions in 3D space are also legitimate possibilities for the proton's spin state. The point at which quantum mechanics rears its head is this: *is the +X direction, the +Y direction, or any other direction than −Z clearly distinguishable from +Z*?

Obviously, −Z ought to be *the most easily* distinguished state from +Z, but one might guess that we could detect if the spin were pointing in a slightly different direction than +Z. However, it turns out to be the case that if you attempt to measure the spin of a proton, a single measurement can only distinguish two opposite states: and that if you measure a particle whose spin is *different* from those states, you get an outcome which is **(a)** random and **(b)** indistinguishable from having randomly been in one of the two opposite outcomes in the first place. Furthermore, the spin of the particle changes to be consistent with the measurement outcome — if you measure it again, you will always get the same outcome — so that any information about the original state of the system (aside from the fact that it was not pointing opposite to the outcome which you obtained) is in effect destroyed; only if you have many copies of "the same state", stored by many other particles, can you get the statistical information required to determine what orientation the particle actually had to begin with.

*Why* this is the case I cannot tell you, and it's outside of the scope of this forum besides. I can only report that it *apparently is* the case, supported by something approaching a century of experimental observation.

**The importance of quantum states as intermediate states**

One simple reaction to this state of affairs would be to say: if the other spin directions don't seem to be distinguishable from +Z and −Z, then let's just not use them. This is one thing that you could do from the point of information storage: though avoiding them physically is not really practical, we can try to make fast transitions the way we currently do with voltages in electronics today.

However, we aren't really interested in quantum information as a way of describing how to *store* information, but for *transformations* of it — ways that you can use with it, either on your own (computation) or with others (communication) to evaluate functions and obtain the properties of structures represented by the information. While the information is being transformed, we don't necessarily have to care about how to describe the intermediate steps of the computation in terms of distinguishable states; and so this limitation of measurement, and the idea of distinguishing the possible states that a single "quantum bit" may have, is less important.

As far as we are able to determine, this freedom to ignore the distinguishability of the various states of a qubit in the midst of a computation is crucial: it is in effect the source of the (likely) power of quantum computation beyond classical computation. Ignoring the distinguishability of *possible* states of particles in mid-computation allows us to make use of the full state-space of a qubit; and importantly, also allows us to explore the full state-space of multi-particle states. Doing so allows us to perform computations in a manner which are popularly described as happening in "multiple worlds"; but given that we can only access the information computed by these multiple "worlds" if we can arrange for most of them to conspire to yield similar answers with high probability by so-called "interference", I think it is much better to recognise that the expanded state-space allows us more flexibility in how we transform information, allowing us literally to short-cut (*i.e.* find a shorter route than one might expect) through computational space to obtain solutions more quickly.

What are the nature of these short-cuts? Well, although we cannot perfectly distinguish +X from +Z, or −X from −Z, we can certainly perform operations on a quantum bit which transforms +Z to +X, and −Z to −X; or in fact any rotation of the direction of spin of a single qubit. This, together with *controlled-not* operations (which may be understood as essentially a reversible *exclusive or* operation on classical bits, where again we represent the classical bits 0 and 1 in terms of the +Z / −Z spin directions), is in principle enough to perform universal quantum computation.

But what do these single-qubit rotations mean *in terms of the information stored in a single bit*? Well: like a single-bit NOT operation, there isn't very much that you can do with them on their own. But the distinction between classical computation and quantum computation — and the distinction between mere shared randomness and entanglement — essentially boils down to the fact that these operations are sensible; that the +X state is as sensible a state in its own right as +Z, and that −X is as distinct from +X as +Z is from −Z. These other directions are sometimes described as being "in between" +Z and −Z, but it is equally correct to say that +Z and −Z are "in between" +X and −X. The different axes along which a qubits state may point are in themselves equally legitimate, and in their own way *completely determined* (as opposed to random) states which may represent pieces of information.

In short: that a quantum bit may meaningfully store information *in a manner other than the states which you use to represent 0 and 1*, in a way which is important when considering the intermediate steps of a computation. That is as much as I think anyone can tell you about quantum bits, without actually getting into physics, or linear algebra over the complex numbers.

# Answer
> 2 votes
Why are you so certain that "Surely a computer can only understand on and off"? Even classical (non-quantum) computers can deal with more than just "off" (no voltage) and "on" (high-voltage): look at Fuzzt Logic or Many valued logic in which the electrical circuit behaves differently according to the voltage level and not only "on" and "off". Analog devices (like microphones/headsets) use all the voltage scale, etc. (yet, later this voltage level will be sampled, since *digital* computers commonly use bits)

Quantum computers take this idea one step further, and instead of using "voltage" they use other features, that behave differently (as defined by quantum-mechanics). This gives a hardware that is capable of more than just processing "0"s and "1"s.

# Answer
> -1 votes
In Quantum theory, a Qubit has an extra state (superposition) which differentiates it from a regular bit. A regular bit can have states 0 ("off") or 1 ("on"). A Qubit, can have one extra state, which is a superposition of both 0 or 1. This is essentially a "do not know" state (or both), since we don't know whether it will be a 0 or a 1. However, there are probabilities in which it can be a 0, or can be a 1. When observed, it can be decided if it's a 0 or a 1.

---
Tags: terminology, quantum-computing
---


title: The List functor

text:
# Question
Title: The List functor
I have been reading some notes on Category Theory. One question that is posed is to verify the definition of $\operatorname{List}$ is a functor...

$\operatorname{List}(g \circ f) = (\operatorname{List} g) \circ (\operatorname{List} f)$

I can see this makes sense in programming terms whereby a function $f$ is mapped to a function $\operatorname{map} f$ but how do you prove this in a mathematically rigorous way?

Thanks!

# Answer
The property in your question is that a functor preserves morphism composition between categories. In functional programming, the `map` function provides the morphism-mapping part of the List functor. This property can be proved by induction over the structure of the list datatype, using the definition of `map`.

I'll use Haskell here as its syntax is fairly clean. `map` is defined:

```
 map :: (a -> b) -> [a] -> [b]
 map f [] = []
 map f (x:xs) = (f x) : (map f xs)

```

The property we want to prove is:

```
 map (g . f) = (map g) . (map f)

```

We will proceed by reducing the left-hand side (LHS) and right-hand side (RHS) of this equation, for the base and inductive cases, and showing them equal.

* Base case: `[]`

On the LHS:

```
 map (g . f) []
= []                     {map defn. [1st case]}

```

On the RHS:

```
  ((map g) . (map f)) []
= (map g) []             {map defn. [1st case], on the right of .}
= []                     {map defn. [1st case]}

```
* Inductive case: `x:xs`. The *inductive hypothesis* is that

```
(map (g . f)) xs = ((map g) . (map f)) xs

```

On the LHS:

```
  map (g . f) (x:xs)
= ((g . f) x) : (map (g . f) xs)         {map defn. [2nd case]}

```

On the RHS:

```
  ((map g) . (map f)) (x:xs)
= (map g) ((f x) : (map f xs))            {map defn. [2nd case], on right of .}
= (g (f x)) : (map g (map f xs))          {map defn. [second case]}
= ((g . f) x) : (((map g) . (map f)) xs)  {definition of composition .}
= ((g . f) x) : (map (g . f) xs)          {by inductive hypothesis}

```

This completes both cases of the inductive proof for the preservation of morphism composition by `map` for the List functor.
> 5 votes

---
Tags: category-theory
---


# Question
Title: Algorithm to determine if a number is perfect on a Turing Machine
I've been trying for a while now to find a solution for the problem in the title: determining if a number is perfect using a Turing Machine. I only had one class on the TM and while I did "get" how it works, this particular algorithm is being really hard for me to develop.

The algorithm I'm trying to implement on the TM is basically this (on C, returns `true` iff `n` is a perfect number):

```
int main(int n) {
  int i=1, sum=0;

  while ( n > i ) {
    if ( n % i == 0 ) {
      sum = sum + i;
    }
    i++;
  }

  return sum == n
}

```

The tough part for me right now is the `while(n>i)` loop and the `n%i` inside it.

Since I already have a program that does `a%b`, I was trying to build the TM graph around it, but I'm not sure it's the best idea, specially since the `b` on this case changes on every iteration. The software I'm using to simulate the TM is called JFlap.

The algorithm on table or graph form would be perfect.

# Answer
> 1 votes
You need do do:

* Factor the number given
* Add up the factors, and check they add up to $n$

It should be something like:

```
sum = 0;
for(k = 1; k < n; k++) {
     if(n % k == 0)
         sum += k;
}
return sum == n;

```

To get n % k == 0 you can:

```
tmp = n;
while(tmp > 0)
    tmp -= k;
return tmp == 0;

```

Translating into TM-speak and splicing all this together isn't hard, just *very* tedious. Use a multitape TM to simplify your description.

---
Tags: algorithms, turing-machines, decision-problem, integers
---


# Question
Title: Identifying an object in an image based on color (AI ?)
*First off, I am not sure if this is the correct stackexchange site to ask this question on, so moderators can feel free to move it.*

I am working on an application that identifies an object in an image. For example, let's say that the object is an apple, and the apple can be green, red, or both.

My plan is to create an array the same size as the image, then scan through the image, pixel by pixel, and if the current pixel is within my range of colors (green-ish or red-ish), add a 1 to the corresponding location in the array, else add a 0.

After this scan through the array, I will have an array of 1s and 0s, which will hopefully contain a concentration of 1s, representing the apple.

---

I am a computer science student, but have yet to take an AI class. So my question is: is this a good way to go about doing this? Or are there more established AI methods (or algorithms) for identifying objects in an image based on color?

EDIT: I should clarify that the problem isn't identifying if the image contains an apple, the problem is identifying where the apple is in the image.

# Answer
The general class for this problem is Template matching. The most common approach is performing a cross correlation of the template, in your example an apple, and an image which may contain the template.

A Google search for "template matching fast normalized cross correlation" will bring up some literature that should be helpful.
> 3 votes

---
Tags: algorithms, artificial-intelligence, image-processing
---


title: Backtracking for listing k elements

text:
# Question
Title: Backtracking for listing k elements
Can someone give me a hand here, I am new to backtracking, and preparing for an interview. I couldn't even attempt this question, please help.

Describe a back tracking algorithm for efficiently listing all k-element subsets of `n` items.

For `n = 5` the 3 element subsets are `(1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5), (2,3,4), (2,3,5), (2,4,5), (3,4,5)`

In particular, I am interesting in first describing the solution vector representation to use, and then how I would partition the work among construct-candidates, is-a-solution and process-solution functions.

# Answer
Unfortunately, backtracking is not taught in many universities although it is a basic technique in algorithms and programming. You can backtrack using two methods: recursive or iterative. In the iterative, you use a stack. In the recursive version, you use the built-in memory stack by calling functions recursively.

A code that generates something similar to what you want is the following (it is left as an exercise to do exactly what you want.).

```
void backtrack(vector<int> v, int index, int max, int n) {

1)  v.push_back(index);
2)  if (v.size() == n) { print(&v); }
    else {
3)      for (int i = index + 1; i <= max; i++) {
4)          backtrack(v, i, max, n);
        }
    }

}

```

This is called from the main function as: backtrack(v, 1, 5, 3); where v is a vector, and 1 is the initial element to be inserted in the vector.

You can implement your print as following:

```
void print(vector<int>* v) {
printf("( ");
for (int i = 0; i < v->size(); i++) {
    printf("%d ", v->at(i));
    if (i < v->size() - 1) { printf(", "); }
}
printf(") \n");
}

```

Note that the output of the program above is: (1,2,3), (1,2,4), (1,2,5), (1,3,4), (1,3,5), (1,4,5). -- Try to correct it. \[Hint: use a for-loop in main\]. Usually, a backtrack function has a a helper function (e.g. backtrack\_helper). I haven't used a helper in here. But you can use it in your improved version.

*Remark:* I added some comments in the backtrack version to show how I got this backtracking. In 1) I did the action that is supposed to be taken. In 2) I check whether I have reached a *correct solution* . In our case, a correct solution is when we have a vector of size n (3). If I dont reach the correct solution, I go to backtrack more. The for-loop is the most important thing in the program. I check the last element to be inserted in the vector (call it index). Then in the for-loop I call backtrack for all the neighbors of this element. These neighbors are the elements that can be inserted after index. These are called sometimes legal neighbors of index. -- It may sound weird a bet now. Let me know if you need more clarifications.
> 1 votes

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


title: Showing transitivity of PSPACE?

text:
# Question
Title: Showing transitivity of PSPACE?
For the following question:

If B is an element of PSPACE and A is an element of PSPACE-Complete, and A polynomial reduces to B, then B is an element of PSPACE-Complete.

I am trying to prove this, but I don't understand how to get started. Can anyone help please?

# Answer
If $A$ is PSPACE-Complete, then any $A' \in$ PSPACE can be reduced to $A$ in polynomial time. What can you say about a polynomial time reduction from $A'$ to $B$?
> 1 votes

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


# Question
Title: Computing number of block reads given relational algebra statement
So I'm just starting to learn about query processing and such in databases and I'm having some trouble. I don't really understand how to compute the minimum number of block reads given a relation and a query I guess you could say. If anyone could help me out, it'd be much appreciated. Here is an example that I'm working on:

* R1(A,B,C) A is a primary key and C is a foreign key to R2.C
* R2(C,D,E) C is a primary key
* R1 has 20,000 records, with 200 records per block. There is a primary B+-tree index on A with height h = 3
* R2 has 45,000 records, with 4,500 records per block. There is a primary B+-tree index on C with height hC = 3 and a secondary B+-tree index on D with height hD = 2.

Find the minimum number of block reads for each statement. I can only hold one block of memory for each relation at a time.

* Where B=1(R1)
* Where C=1(R2)

I'm not looking for answers. I'm looking for explanation of how to actually do it and guide me along the way. Aka equations, etc. It's kind of difficult to find anything beneficial online at all.

# Answer
`select * from R1 Where B=1`

You don't have any index on a search field (B), hence you have to do a full table scan. It means that you fetch all relation's blocks one by one and take the records which satisfy the condition `B=1`. (Cost - 200000/200 = 200 blocks)

`select * from R2 Where C=1`

There is not enough information - you have to know(at least approximately) how many records in R2 satisfy the condition `C=1`. For example in case that all the records in R2 have `C=1` you'll do the full table scan like above (cost - 45000/4500 = 10 blocks) On the other hand if you have only one record with `C=1` you'll read 3 blocks of index and another one from disk(cost 3 + 1 = 4 blocks)
> 2 votes

---
Tags: database-theory, databases, relational-algebra
---


# Question
Title: How to distinguish empty cells from cells outside of the input cells?
**Setup**

I need to develop a Turing Machine that accepts a string m that has the same number of a's and b's. My alphabet is {a,b}, and we use a diamond in class to represent an empty space.

**Problem**

The part I'm having trouble with is returning to the beginning of the string.

**So far**

At first I was planning on taking a character(a) marking it with a diamond, moving right until the other character(b) is found, marking that with a diamond, then moving left until the other's other character(a) is found, and repeating the process. The parenthesis are for example, it could have been b,a,b just as well.

Then at the end if there is an outlier I will know the number of a's and b's was not similar.

But then I developed an example language ab... and realized that this process will never end in this case, so instead I need a way of determining when I have reached the beginning of the string.

**So now my question...**

Is it possible to determine when I have reached the beginning of the string without introducing another letter into the alphabet, or another special character like the diamond?

# Answer
> 1 votes
I think it's intuitively clear that it's not possible. You have to be able to distinguish working and "outside" part of the tape, and on both sides!

There are two common ways to solve this:

* Assume the input is delimited by special characters.
* Overwrite with a new special tape symbol.

Both are fair and there is no reason not to.

# Answer
> 1 votes
The common definition of the Turing machine is that when you go left when you're at the furthest left point on the tape, is to stay on that spot. So if you want to determine where it began, mark it off, as you said, with a diamond or similar.

---
Tags: turing-machines, discrete-mathematics
---


title: Null Hypothesis in Analysis and Testing

text:
# Question
Title: Null Hypothesis in Analysis and Testing
I have my end of year exams next Thursday. I'm generally doing fine but I am having some major issues with this strand of my course, this has to be the biggest issue I have. So, here is the question in the past paper:

> You have been tasked with determining the validity of a manufacturer’s claim that their widget is more reliable than their main competitors’ widgets.
>
> In order to verify this assertion you test a sample of 25 widgets from the manufacturer’s range and find a mean pass rate of 992 per 1000 with a standard deviation of 15 per 1000.
>
> Previous studies have shown that the mean pass rate of all other widgets on the market is 979.4 per1000.
>
> In order to increase the confidence in the making a decision about the null hypothesis you choose a 99.5% confidence level and find the corresponding t-table value to be 2.947.
>
> * State the null hypothesis.

I have revision notes in front of me, but I just don't understand what this question is actually asking. Am I just writing down my own hypothesis, or do I need to use this equation?

> H0; μ
> H1; μ

If anyone could go through step by step for what I need to do, then that would be fantastic. My notes are just confusing!

# Answer
> 1 votes
For your particular problem, the null hypothesis is

$H\_0: \mu\_{manifacturer} = \mu\_{competitors}$

and the alternative hypothesis is

$H\_1: \mu\_{manifacturer} \> \mu\_{competitors}$.

Basically, the null hypothesis states that there is no difference between the widget under test and the widgets made by other competitors. The alternative hypothesis states that, instead, there is a difference and the widget under test is better than the widgets made by the competitors.

Now, in your statistical significance test, you are trying to determine if you can reject the null hypothesis, i.e, if the data can be used to demonstrate for a specific confidence level that the widget made by this manufacturer *may be* better than the ones made by the competitors on the market. Note that I wrote "may be". If you can not reject the null hypothesis on the basis of the available data, this is interpreted by saying that statistically the data do not provide enough evidence to support your assumption that the widget under test is better.

See this Wikipedia article and this one on Statistical hypothesis testing for additional information.

---
Tags: probability-theory, statistics, reliability
---


# Question
Title: Prove that context free languages are not closed under swapping prefixes and suffixes
Prove that context free languages aren't closed under this operation: $ A(L) = \\{ zyx \mid x,y,z \in \\{0,1 \\}^\*, xyz \in L \\} $

Obviously, we need to find a context free language $L$ such that $A(L)$ isn't context free. Here are some of my failed attempts:

Take the language $ L = \\{\ 0^n1^n \mid n \in N \\} $ and then (since the intersection of a context free language with a regular language is context free) we get: $ A(L) \cap 1^\*0^\*1^\*0^\* = \\{\ 1^{m}0^{n-k}1^{n-m}0^{k} \mid n,k,m \in N, m,k\le n \\} $ which might look promising at first, but unfortunately this language is context free...

I also tried my luck with the following languages:
$ L = \\{\ 0^n1^m0^m1^n \mid n,m \in N \\} $
$ L = \\{\ ww^R \mid w \in \\{0,1 \\}^\* \\} $

but these languages didn't help me either...

# Answer
> 4 votes
Did you try $\\{\ a^nb^nc^md^m \mid m,n \ge 1 \\}$?

Or, if you insist on alphabet $\\{0,1\\}$, consider $\\{\ (01)^n(011)^n(0111)^m(01111)^m \mid m,n \ge 1 \\}$?

And be shure to intersect with a nice regular language after the operation, but from your question I see that you know how that works.

---
Tags: formal-languages, context-free, closure-properties, pumping-lemma
---


# Question
Title: Predicting energy consumption of households
I have the dataset which you can find here, containing many different characteristics of different houses, including their types of heating, or the number of adults and children living in the house. In total there are about 500 records. I want to use an algorithm, that can be trained using the dataset above, in order to be able to predict the electricity consumption of a house that is not in the set.

I have tried every possible machine learning algorithm (using weka) (linear regression, SVM etc) . However I had about 350 mean absolute error, which is not good. I tried to make my data to take values from 0 to 1, or to delete some characteristics. I did not managed to find some good results.

I also tried to use R tool, and I did not have good results either...

I would be very grateful, if someone could give me some advice, or if you could examine a little the dataset and run some algorithms on it. What type of preprocessing should I use, and what type of algorithm?

I have posted a similar question last month, but I did not get any useful answers.

# Answer
> 2 votes
I am not an expert in machine learning, but here is one problem: most of your data is binary. Since you have *many* such paramters, very little can be derived in terms of correlation between any given parameter and the target quantity. Therefore, statistic methods will have a hard time.

Furthermore, you have a small data set but many parameters. Get rid of some.

Another problem can be that you have mutually exclusive data: for example, the first three parameters (`URBAN`, `RURAL` and `MOUNTAINOUS`) can not be set at the same time. You might want to combine them into one category parameter; thus, the algorithms don't have to find a multi-dimensional anti-correlation and correlate the vector to energy consumption, but use that one parameter directly. Note how this also reduces the number of parameters.
If you can make assumptions about which areas inherently cause more energy consumption, consider turning the parameter into an appropriate interval (of reals).

As a general rule, machine learning is what you do if *other methods don't work*. In this case, I don't see the need for machine learning unless you show that reasonable other approaches fail.

For instance: Research energy consumption of the appliances you have parameters for and assume average values resp. values fitting the total area covered. Research and/or make reasonable assumptions for the number of light bulbs, air conditioning, etc based on total area. If this does not already solve your problem, it should reduce the number of parameters with unknown influence.

# Answer
> 1 votes
You should use a scoring system. A simple system is to use a weighting of 1.0 for every column. With each input record you would match all the fields to each record of the dataset. If a field matches then that dataset record will have it's matching score increased by 1.0 (the weight). After matching all fields, the dataset record with the highest score wins and it's TOTAL\_CONSUMPTION amount is taken as the value to apply to the input record.

That is the simple way. A better way would be to weight each column as you see fit. For example you might give POOL a weight of 0.2 and FLOOR\_HEATING a weight of 0.8.

So far I have been inferring that an exact match only is counted. A further step would be to scale the weighting based on the closeness of the matched field values. So the ADULTS column could have a weighting of 2.5. If the input record has 3 ADULTS and a dataset record has 5 ADULTS then you could take the difference as 2 (=5-3) and then divide the weight by that, leaving a score of 1.25.

One further step would be to average the TOTAL\_CONSUMPTION from all matching dataset records, based on their score.

---
Tags: algorithms, machine-learning, statistics
---


# Question
Title: Proving that finding wheel subgraphs is NP-complete
Can you help me with this problem ?

> Given an undirected graph $G$ and an integer $n$, prove that determining whether the graph has wheel on $n$ vertices $W\_{n}$ (a wheel $W\_{i}$ is such that $i$ nodes form a cycle and a $i+1$st node is connected to all other nodes, resulting in $2i$ edges) is NP-complete.

# Answer
Hint: Hamiltonian Cycle is $NP$-Complete.
> 5 votes

# Answer
Following the advice in our reference post, check out related NP-complete problems in order to find a suitable reduction partner.

> Hamiltonian cycle does indeed look promising: note that $W\_n$ contains a simple cycle.
> 1 votes

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


# Question
Title: Finding the largest 3-clique-free induced subgraph
Consider this problem:

> Given an undirected graph $G = (V, E)$, find $G' = (V', E')$ such that:
>
> 1. $G'$ is an induced subgraph of $G$
> 2. $G'$ has no 3-cliques
> 3. $|V'|$ is maximal

So the least number of vertices must be eliminated from $G$ so that 3-cliques are eliminated.

An equivalent problem would be to find a 2-coloring for $G$ such that if $(v\_1, v\_2, v\_3) \in V$ and $((v\_1, v\_2), (v\_2, v\_3), (v\_3, v\_1)) \in V$,

1. $(v\_1.color == v\_2.color \wedge v\_2.color == v\_3.color \wedge v\_3.color == v\_1.color) = False$
2. The (absolute) difference between the number of nodes with color 1 and the number of nodes with color 2 is maximal.

Can anyone think of a polynomial-time algorithm to solve one of these problems?

# Answer
Both definitions leave your problem NP-hard, and have been answered on cstheory.

* Interpretation 1, where you require the largest triangle free sub-graph, is NP-Hard and has been answered here.
* Intepretation 2, where you need a partition such that both the induced sub-graphs are triangle free, has been answered here.

Note that the answers I linked to are for general $H$-freeness and are a class of $NP$-Hard problems.
> 5 votes

---
Tags: algorithms, graphs, optimization
---


# Question
Title: How to prove Transitive property of Reducibility with a TM?
How can we prove that $h(x) = g(f(x))$ is a reduction function for $A \leq\_m C$,

if $f$ is the reduction function of $A \leq\_m B$ and $g$ is the reduction function for $B \leq\_m C$

The given Proposition is: $A \leq\_m B, B \leq\_m C \Rightarrow A \leq\_m C$

I was thinking about using $HALT\_{TM}$ for A. So on input $\langle M, w\rangle \in A$ if and only if $\langle M'',w'' \rangle \in C$

The output of A would be $ \langle M', w' \rangle$ and the output of B would be $\langle M'',w'' \rangle$

If the constructed $M$ rejects the input $x$, then it loops forever, so $C$ is not recursive if $A$ is not recursive

If this isn't sufficient, then what am I missing?

# Answer
> 5 votes
The properties that reductions have are:

* They preserve language membership (or Yes-instances, or whichever phrasing you prefer).
* They are computable.

So then given that you have two reductions $f$, which takes instances of $A$ and produces instances of $B$ such that $x \in A \Leftrightarrow f(x) \in B$, and $g$ which does the same for $B$ and $C$, you need to show:

1. $x \in A \Leftrightarrow g(f(x)) \in C$.
2. $f\cdot g$ is computable.

The first should be a fairly straightforward application of basic logic. The second is also easy.

You can't just take $A=HALT\_{TM}$ though, as all you would show then is that $HALT\_{TM} \leq\_{m} C$, whereas your question (appears) to ask for a proof of the transitivity of many-one reductions *in general*. (As a comparison would showing that $(10^{100} \< b) \wedge (b \<c) \Rightarrow (10^{100} \< c)$ show that $(a \< b) \wedge (b \<c) \Rightarrow (a \< c)$?)

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


title: Reduction from 3-SAT to a graph problem

text:
# Question
Title: Reduction from 3-SAT to a graph problem
I have a question, i was trying to reduce 3-SAT to a particular graph problem and i'm not quite sure about a thing i used in the reduction. In fact the reduction build a bipartite graph, the edge $(x\_1,c\_1)$ exist if the variable $x\_1$ is in the clause number 1, the costs on that edge are dependent on the truthfulness of the variable $x\_1$, cost 1 if $x\_1$ is true and 0 elsewhere. My question :is it permitted in a reduction or should i have the entire graph instance independent from values taken by the variables ?

Thank you all!

# Answer
> 3 votes
If I understand your question correctly, you're asking whether you can construct a reduction where the truth assignment changes the construction.

In short, no. The whole point of a reduction from problem $A$ to problem $B$ is to show that we can solve $A$ using an algorithm for $B$ - if we already know the solution to $A$, then we could trivially reduce it to virtually any other problem.

In your particular case, if you already know the truth assignment to the variables, then you've already answered whether the input formula to the 3-SAT instance is satisfiable or not, what you want is a reduction that takes the formula, turns it into an instance of your graph problem, where solving the graph problem would tell you what to set the variables in the 3-SAT instance to.

---
Tags: complexity-theory, graphs, np-complete, reductions, 3-sat
---


# Question
Title: How to construct and write down a Turing machine for a given language?
In my class we just started learning about Turing machines. I think I understand the concept but am unsure how to syntactically solve any problem related to one. I am presented with the problem:

> Build a Turing machine accepting $(b + c)^+$$\\#a^+$ (Please comment your code. Any uncommented solutions will not be graded.)

I am unsure of how to actually begin devising this machine? Could someone please help get me started?

# Answer
> 6 votes
What all strategies to devise a program for a Turing machine - or for any other machine, for that matter - boil down to is this: learn how to write programs for easy languages, and then use these programs and rules of composition to figure out more complicated ones. Programming languages - including Turing machine programs - expose an interface to the underlying computer, which allows you to perform some limited number of operations. Programming is the art and science of finding a sequence of such operations to solve your problem.

1. Can you write a Turing machine to recognize $a^+$?
2. Change the Turing machine in (1) to recognize $\\#$ only. *Hint: it's a different symbol and you only want one of them.*
3. Change the Turing machine in (1) to recognize $(b + c)^\*$. *Hint: you'll now take either of two symbols instead of one symbol.*
4. Take the machines from steps (3), (2) and (1). Create a new machine that does what (3) does, but instead of accepting, it does what (2) does, but instead of accepting, it does what (1) does.

In TM pseudocode, what you get is something along the following lines:

1. Move one cell to the right.
2. If the cell is $b$ or $c$, move to the right; else, halt reject.
3. If the cell is $b$ or $c$, move to the right, and repeat this step. Otherwise, if the cell is $\\#$, move to the right and go to the next step. Halt reject in any other case.
4. If the cell is $a$, move to the right; else, halt reject.
5. If the cell is $a$, move to the right. Else, if the cell is blank, halt accept. Halt reject in any other case.

Those would serve as decent comments, but coming up with the TM and verifying that it works should also accompany any correct answer.

# Answer
> 3 votes
ok I think I got it. does this look right?

$\delta(q\_0,\*) = (q\_1, \*, R)$ where $\* = c,b$ // Read at least one c or b

$\delta(q\_1,\*) = (q\_1,\*,R)$ where $\* = c,b$ // Continue reading c or b while moving right

$\delta(q\_1,\\#) = (q\_2,\\#,R)$ // End of block, skip right to next block

$\delta(q\_2,a) = (q\_3,a,R)$ // Read at least 1 a

$\delta(q\_3, a) = (q\_3, a,R)$ // Continue reading a's and moving right

$\delta(q\_3, B) = (q\_4, B, S)$ // When we reach the end of the tape, halt

# Answer
> 1 votes
What I believe you're asking is essentially you want to build a finite state machine (FSM). These machines are built up using many states (generally represented by circles). Given some input, they then react to that input and either the current state changes, or it remains the same.

Here's a nice example taken from wikipedia:

This shows that we begin first at state $S\_1$, represented by the arrow pointing to it. From $S\_1$, there are two inputs that could be received: a 0, or a 1 (our input language would then be $\\{0,1\\}^\*$). If $S\_1$ reads a 1, then it remains there. If it receives a 0, then it moves to state $S\_2$.

What this machine does is checks for odd or even amounts of 0's in the given string, ie $L = \\{w\ | w\ \in \\{0,1\\}^\*,\ w\ has\ an\ even\ amount\ of\ 0's\\}$.

So some strategies on making yours; First, build up your turing machine so that it handles the base case, which for you could be simply (b + c)#a. Then, write out some other cases that could happen, such as (b + c)(b + c)#a, and see how you could handle that, until you match the language you are creating. Try splitting the language into sections, and create a machine for those, ie one section is (a + b)$^+$, while another would be #.

In the case of regular expressions, there are algorithms to convert them to finite automata systematically. You can check a textbook on automata or, for example, this link. Note that in simple cases like yours, it's probably easier to write down an automaton directly.

---
Tags: turing-machines
---