# Question
Title: Is it feasible to generate every possible RGB image?
This topic is normally brought up in computer science as a demonstration of how to calculate permutations but it stops there since we usually end up calculating that there are more images of a decent resolution then that of all the atoms we estimate are visible in our universe.

This makes sense because an image of a decent resolution (like the image displayed your computer monitor) should be able to contain every picture imaginable, every frame from every movie ever made and never made. It would contain every correct and incorrect mathematical equation. Or even every book/webpage that will exist or can exist. It's intriguing to think it would be possible to generate every possible image because it contains all knowledge but also all anti-knowledge which means there is a lot of stuff to sift through including lots of random noise.

The only other research into this topic that I could find is this art project, where they wrote some code to generate all `15x10 pixel` black and white images which is estimated to take approximately `46 quinvigintillion` or 4.6x1079 years to complete.

So is it feasible to generate every possible RGB image (of a decent resolution)?

# Answer
The number of such images is exponentially large in the dimensions of the image (even after taking into account symmetries), and grows enormous rapidly. For all but very small images, no, it's not feasible to enumerate all such images within the lifetime of the solar system. (There's something wrong with your reasoning if you've concluded it's reasonably possible to enumerate all such images.)
> 8 votes

# Answer
TLDR;
No it is not feasible at all, the numbers you provided are small in compare with space you want to generate. So you have provided very strong hint yourself. TLDR;

You can say that $Q = 24bpp * Width * Height$ is your bits array. Since this are bits there are $2^Q$ images.
And now comes question (which I hope answers something): what will you do next and why you want to generate them all?

This number is way too huge to give you something useful, let me assume you can have it tommorow, what then?
You will not have enough time to just look at them, storage space - you do not have it. And there will be very large number of pictures that are beyond your perception are the same. If you take picture of yourself and change one pixel, you will not notice it. Even changing all pixels by 2 least significant bits will show low artifacts, lower than jpeg compression.

But assuming you have space and those images - what is next step? Looking for similarities? Trying to find your friends picture? Well, no, you ended up with enumerating all possible images (which are numbers), and now you want do to something more than posses them.
So probably, you will transform them - scale down, make grayscale and tell the program to get rid of too close pictures (since there are in your perception, the same scene), and then you try to let say find something.
Still the space is way to big to operate on, algorithms like SSIM (to compare two images) have big runtimes. So waiting for prescreened results (meaningful and interesting) is still out of reach.

This is the reason that nobody enumerated these images, do not generate all possibilities, because even under assumption you can have them, there is nothing useful there.
So the answer is no, and all projects of this type are just for fun, showing that somebody can use two nested loops and arithmetic on RGB, make show or intrigue people, but under no circumstances this is feasible.

Take natural numbers. Up to say 2^240000 which is equivalent to all 100px x 100px 24bit images - looks like quite big number. And now try to find me picture which is miniature of red-blue dragon. Would you really generate and save all possibilities on some storage and than review them?

And another thing, to make color-\>grayscale based on luminance it would be nice to have 2^24 precalculated colors - have you seen such array? It does not fit cache, and it takes a while to generate, while calculations on fly are in realtime.
> 2 votes

# Answer
*It is actually more feasible then you might imagine. I've been researching this topic and surrounding ones involving images on and off for a while now. Welcome to part 1 of many parts to come of my research into the exciting area of digital images. The rest will be posted on here using the same question and answer format. An accompanying Mathematica notebook can be downloaded here:* http://www29.zippyshare.com/v/6ZntKnfL/file.html

---

## Getting Started

First we need to define what every possible image means more clearly. For an image to exist we need to define three things: a color space, a width, and a height. Once those three things are defined we have defined a set of images, and once we have a set of images to work with we can calculate the total possible or the total number/amount of images in that set using this Mathematica function I wrote:

```
totalPossibleImages[numberOfColors_, numberOfPixels_] := numberOfColors^numberOfPixels

```

*In thinking about this problem, I figured that a lot of images that you would end up generating would be similar or the same as other images, so you don't need to generate all of them. To investigate this I started looking at small black and white images and wrote a function to generate every possible black and white image so that I could study them for patterns.*

```
allBlackAndWhiteImages[imageWidth_, imageHeight_] :=
...continued in notebook...

```

To summarize, the function works by counting up from `0` in binary. Each count gives us an image because we interpret each `0` as a black pixel and each `1` as a white pixel as they are contained in each number as we count up. We know when to stop by taking the total number of possible images, subtracting `1`, and converting it to binary (which conveniently will always be the last image we need to generate in every set, an all-white image).

*Notice that this is the same algorithm that is used for generating password sets when doing a brute force password attack.*

So now let's start generating some sets and see what we find.

## Generating Some Image Sets

### 1x1 B&W

Nothing particularity surprising or out of the ordinary here. Now we will continue to increase our width, then height, by `1` and continue to investigate.

### 2x1 B&W

Again nothing particularly interesting here. We are essentially just visualizing counting in binary.

*Notice I'm skipping `1x2` since it ends up being the same number of images as `2x1` but is shaped differently. This holds some importance later on with other equivalence cases and will be detailed in my next posting.*

### 2x2 B&W

*Take a moment to look at this set and see if you notice the beautiful pattern before reading on!*

What I noticed was that the 8th and 9th images were the inverted versions of each other, then the 7th and 10th, 6th and 11th, 5th and 12th and so on. There is a line of symmetry exactly in the middle, between the 8th and 9th images. Where have we seen this pattern before? The integer number line:

*The integer's number line has a line of symmetry at `0`. However in our example we don't have a `0`. We are effectively "subtracting" or skipping the zero. I'm not sure of the mathematical importance of skipping the zero is but it feels like it relates to the subtracting of `1` that we are always doing when performing a loop in programming (if you want to loop `n` times your counter counts from `0` to `n-1` just like the `totalPossibleImages` function).*

If you go back and look at the other image sets they have the same pattern and this pattern continues for any black and white image.

So then I put this integer line idea back into a new image generating function, `allBlackAndWhiteImagesWithInts`, and looked at the `2x2 B&W` set.

### 2x2 B&W

What I noticed when using the integer number line is that it gives us a mathematical formula for inverting any black and white image: multiplying by `-1`. But we have to convert existing images to integer form first. If we compare this to the current algorithm for inverting images, it is exactly the same thing happening but it is just represented differently. The loop over each pixel is abstracted away to a mathematical, versus a computer science, operation.

*This leads me to predict that there must exist other mathematical abstractions for other image operations like rotation and scaling (yet to be investigated).*

Bringing this back to generating every possible image, this means that for any black and white image set, you only need to generate the first half of the set since the second half of the set can be produced by inverting any image generated in the first half and vice versa.

But the original question was whether it was feasible to generate every possible RGB image. Once we choose a different color space other than black and white then this theory of only needing to generate the first or last half of the set doesn't hold up. For example:

### 3x1 B&W&Red all over

*Notice here I just did the permutations manually since I didn't find it intuitive to program Mathematica to use an easily calculable amount of colors like `3`. Instead of rendering an image we just use the convention that `0=black`, `1=red`, `2=white` (white is always the highest number and black is always the lowest in images). The problem here is that using `3` colors gives results in an odd amount of images meaning we can't easily just stop half way. And even if we were able to there is no symmetry near the halfway point in this set anyways.*

So in order to continue we need to rethink the RGB part of the question. An RGB image is made up of `3` greyscale images which are colored in red, green, and blue. This means that every RGB image is actually made up of `3` images picked from the exact same set of greyscale images. This means that we can rephrase the question and easily eliminate a lot of images that we would need to generate in trying to answer the original question.

## Is it feasible to generate every possible *greyscale* image?

Now that the question is framed more accurately we can investigate this much more easily. For the remainder we will be assuming a `256 bit` greyscale image where `0=black` and `255=white`.

*Since we are saying that inverted images are the same, meaning we only need to generate one of the inverted pairs in an image set, I began to think about what what the inversion process does in terms of greyscale. And all it is doing is just shifting the values of all of the pixels in the image by the same amount: `±128` (rolling over `255` to `0` and vice versa). So then what happens when we shift all of the pixels in the image by a different amount like `±1`? Well then we just get a brighter or darker image respectively. So really inversion just happens to be one specific spot along this relative scale of brightness. Which means that we only need to generate images with one brightness level out of `256` possible ones in the set. That's cool but how do we know where those other brightness levels are in relation to each other when generating an image set sequentially so that we know when to stop?*

*To figure this out I looked back at the `3x1`, black & white & red all over set.*

*Then I derived this algorithm to reorganize the appearance of the set into the different relative brightness levels.*

```
Start at the leftmost column, 000, and make this the number we are working on.

1. Increase all of the digits by 1 resulting in a new number (if the digit is a 2 then it wraps around to a 0)
2. Find this new number in the columns and cross it off
3. Write this new number underneath the number we are working on
4. Make this new number the number we are working on and repeat step 1 to get another number
    a. If this other number doesn't exist in the column we are working on then repeat steps 2-4
    b. If this other number does exist in the column we are working on then make the number in the next column the number we are working on and go to step 1

```

*Which gave me the resulting table:*

There are a few interesting things to notice here.

* The first digit in each number:
    + is the logical index of what row it is in
    + is used to define all of the shades for an image set
* The last two rows don't have any immediately recognizable patterns as sets on their own (*I assume there is a pattern, need to investigate more*)
* Finally, we were getting a `1/3` reduction in the total number of images that we needed to generate (3 being the number of colors in the image set)

This reduction is much larger than the half reduction we got from looking at the inversion which we would expect since we are getting rid of more information.

## Conclusion

So if we want to generate every possible image, the amount of images we need to generate becomes too large to compute as we reach a decent enough resolution to see the detail we would like. In order to reduce how many possible images we would need to generate for a given set of images, we need to be able to efficiently eliminate images that are equivalent (or can be non-destructively transformed into other images in the set - hence they don't need to be generated). The first case where we noticed this was possible was color inversion of an image; however the algorithm for doing so didn't easily apply to different image sets. From there we realized that inversion was really just one step on the scale of changing the relative brightness level of all the pixels in the image. Then from organizing a small image set into its relative brightness levels we could see how when we generate the images sequentially, the relative brightness level equivalent images are generated in a predicable enough way that we know exactly when to stop generating images so that we can eliminate them effectively: `1/(number of colors)` the way through generating every possible image. And we know how many possible images we need to generate by taking `numberOfColors^numberOfPixels` in the set. So if we only want to generate `1/(number of colors)` of `numberOfColors^numberOfPixels` total possible images in the set, we can simplify that down to generating `numberOfColors^(numberOfPixels-1)` which we can read simply as skipping the last exponentiation when generating the entire set.

Looking back at the original example of generating every possible `320x240` RGB image we can use a cop-out and make ourselves feel good and get an instant `1/3` reduction by saying we can only look at every possible `320x240` greyscale image. Then we can reduce that further buy skipping the last exponentiation when generating every possible image. But this still leaves way to many images to generate.

---

What we have done is eliminate an equivalence case: relative brightness of an image. But what other equivalence cases can we come up with? Can we eliminate them? Can we eliminate enough so that it becomes feasible to generate every possible "usable" image in a set of a decent resolution so that we can find extraordinary information?

This is where my affirmative results for this question end. I am currently researching other equivalence cases that can be eliminated and will publish them here when I have some results.

---

And again here is the Mathematica Notebook. It also contains some history on how I became interested in this problem in the first place and a few extra details here and there. http://www29.zippyshare.com/v/6ZntKnfL/file.html
> 1 votes

# Answer
A perhaps more interesting question is:

> Can we generate all RGB images up to "indistinguishability"?

That is, if two images "look the same", it's enough to generate one of them.

To answer this question, let's assume that JPEG does a decent job of compressing images. That is, two images which compress to different JPEG files are "distinguishable". Let's also assume that the average JPEG image takes up B bytes. Then the number of different images is at least $256^B$ (this is what we would get if all JPEG images where *exactly* $B$ bytes; other distributions with expectation $B$ are even worse).

To estimate $B$ (which depends on image resolution and the threshold of distinguishability), I looked at this page and concluded that $B \geq 10000$. In particular, there are at least $256^{10000}$ images, which is a **huge** number.

(For more, you might want to look up rate-distortion theory.)
> 1 votes

---
Tags: combinatorics, efficiency, discrete-mathematics, enumeration
---


# Question
Title: Floating point format: why must `1−emax ≤ q+p−1 ≤ emax`?
From the Wikipedia page on the IEEE Standard for Floating-Point Arithmetic,

> The possible finite values that can be represented in a format are determined by the base (b), the number of digits in the significand (precision, p), and the exponent (`q`) parameter `emax`:
>
> ...
>
> q must be an integer such that `1−emax ≤ q+p−1 ≤ emax` (e.g., if p=7 and emax=96 then q is −101 through 90).

I can't figure out the reasoning behind the above inequality. I would've thought (in my simplicity) that it would be `-emax ≤ q ≤ emax` or something similar. What am I missing?

# Answer
> 3 votes
The reason we get a larger range is *denormalized numbers*. Generally speaking, floating point numbers have three physical parts: sign (1 bit), mantissa $M$ and exponent $e$. Most of the time we think of the number as $\operatorname{sgn} \times 1.M \times 2^{e-e\_0}$, where $e\_0 = 2^{|e|}-1$ (e.g. for single precision, it's 127, since the exponent is allotted seven bits). Here "$1.M$" means the number you obtain by writing $M$ as a binary string and prefixing $1.$.

For reasons having to do with underflow (non-zero numbers turning to zero), it is important to be able to store numbers very close to zero. These numbers, named *denormalized numbers* or *subnormalized numbers*, have $e = 0$ and represent $\operatorname{sgn} \times 0.M \times 2^{1-e\_0}$. (This means that *normal numbers* cannot have $e = 0$.) This explains the extended range mentioned in the Wikipedia page.

Other numbers having special encodings are $\pm \infty$ and NaN (not a number), which represent some illegal operation (division by zero, taking the logarithm of a non-positive number, taking the square root of a negative number, and so on). For more details, consult the Wikipedia page regarding the original standard.

# Answer
> 1 votes
I don't think 'subnormality' is at play here. However, 'normality' is!

The Wiki-page you refer to represents a number *x* to be
*x = c . bq* with *c = 0 ... bp-1* (1)
However, the number we would want to store as an IEEE754 floating point number is represented differently:
*x = c' . bq'* with *c' = 0 ... 1-b-p* (2)
This is the 'normalization' I referred to earlier.

We can relate (1) and (2) by reforming (1):
*x = c . bq = c . b-p+1 . bp-1 . bq = c' . bp-1 . bq = c' . bq+p-1*
Therefore:
*q' = q+p-1* (3)

We want to store *q'* using a limited number range. According to the IEEE 754 standard, we'll do this using 'bias'. Let's define the bias to be *emax \- 1* (with *emax* being half the number range we have available. E.g., in the binary32 case we have 8 bits available in the exponent of a float. This leads to an *emax = 0.5 . 28 = 128*).
In view of this, we can write:
*-emax+1 ≤ q' ≤ emax* (4)
This ensures that *q'* plus the bias fully covers the available (but limited) range.

Combining (3) and (4) yields the (at first sight) not so obvious equation of the wiki-page:
*-emax+1 ≤ q+p-1 ≤ emax*

I hope this helps!

Note: the true IEEE754 binary case also assumes the 'silent leading bit 1' which further complicates the matter and is indeed the root of subnormal numbers.

---
Tags: floating-point, number-formats
---


# Question
Title: Is there a zero-knowledge protocol for bit vector agreement?
Suppose Alice knows a secret vector of $N$ bits, say $A=\langle a\_1, a\_2, \ldots, a\_N\rangle$ and Bob similarly knows $B=\langle b\_1, b\_2, \ldots, b\_N\rangle$. Is there a protocol that allows them to determine the number of bits that their vectors have in common, without revealing any additional information about what the vectors are or what positions agree?

That is, we would like Alice and Bob to be able to determine the size of the set $$X(A,B) = \\{i\mid a\_i=b\_i\\}$$ without learning anything else about $A$ and $B$, and without revealing any information to an eavesdropper.

Obviously if $X(A,B) = N$ or $X(A,B)=0$, then Alice now knows Bob's vector and vice versa, and in other cases each gets some incomplete information about the other vector, but that is unavoidable. Perhaps that means that a true zero-knowledge protocol is by definition impossible. But I would like the information leakage to be no greater than this necessary amount.

# Answer
> 2 votes
I think you actually want secure multi-party computation, not zero-knowledge proofs. In secure multi-party computation, Alice has a secret input $a$, Bob has a secret input $b$, and we want to compute $f(a,b)$ so that both Alice and Bob learn $f(a,b)$ but neither one learns anything more about the other's secret. That maps directly to your situation. In your situation, $f$ is the Hamming distance function that counts the number of positions where Alice and Bob's bitvectors agree.

It's a standard theorem that for every poly-time computable $f$, there is a poly-time protocol to compute $f(a,b)$ in a secure multi-party computation sense. There are also toolkits to automatically derive such protocols, given a circuit/description of $f$. For instance, you could look at VIFF or UVA's toolkit.

You'll want to be aware of the differences in threat model between the honest-but-curious threat model (aka semi-honest threat model) vs malicious threat model. The honest-but-curious threat model is a bit of an academic curiousity; for most real applications, I suspect the malicious threat model will be more appropriate, but the protocols do tend to be more expensive.

---

The following paper might be of interest as well, not for your particular problem, but as an interesting tool for computing monotonic functions, where the inputs are sets:

Lea Kissner and Dawn Song. Privacy-Preserving Set Operations, CMU-CS-05-113.

(I previously thought your problem could be reduced to Cardinality Set Intersection, from Section 5.2 of the following paper, by making Alice's set is $S\_1 = \\{i : a\_i=1\\}$, Bob's set is $S\_2 = \\{i : b\_i=1\\}$, and computing $|S\_1 \cap S\_2|$ -- but as you accurately point out, that doesn't work, because you actually want to compute $|S\_1 \Delta S\_2|$.)

---

There are a bunch of cryptographers who hang out on Cryptography.SE and who are knowledgeable about this area.

---
Tags: cryptography, protocols
---


# Question
Title: Is there an algorithm for algorithms time/space complexity optimisation?
In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of algorithms?

For example an implementation of bubble sort as an input for such an algorithm would produce an implementation of a sorting algorithm with time complexity closer to $O(n\log n)$.

# Answer
Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the same job that is faster by any specified margin for almost all input data.

By Rice's theorem, it is impossible to know if two given programs do the same job.

Yes, for some *very restricted* notions of "program", given an example one can construct the "best possible" program for the job. Important classes, even. But a very far cry from anything which is able to express bubblesort.
> 11 votes

---
Tags: algorithms, turing-machines, time-complexity, optimization, space-complexity
---


# Question
Title: Efficient algorithm to compute the minimum of multiple piecewise linear functions
Let $f\_i(x)$ be a continuous, convex, piecewise-linear function for $i=1,\ldots,n$. Define $$g(x) = \min\_{1\leq i\leq n} f\_i(x).$$ Clearly, $g(x)$ is also a piecewise linear function. What would be a good approach to compute all the pieces? In other words, it's clear that $g(x)$ can be represented as $$g(x) = c\_k + d\_k x,\quad \text{for } x\in\[e\_k,e\_{k+1}),$$ for some choice of $(c\_k,d\_k,e\_k)$'s. How do I compute these $(c\_k,d\_k,e\_k)$'s in an efficient way, given the $f\_i$'s?

# Answer
This is basically an instance of the line segment intersection problem. One standard approach is to use a sweep line algorithm. For instance, the Bentley-Ottman algorithm would be a reasonable choice, and is not too difficult to implement.

At each iteration of the algorithm, we have some value of $x$, and we calculate what is the next largest value of $x$ where something interesting happens. Here, "something interesting" is either (1) two pieces intersect each other at a point, or (2) we reach the end of one of the current pieces. Then we advance $x$ to this next value.

At each iteration, we keep track of which pieces are currently active (i.e., $x$ is within the domain of that piece) and the order of the pieces, ordered by their $y$-value for that particular value of $x$. Store them in sorted order, sorted by $y$-value.

All of the interesting bit is in how we determine the next largest value of $x$ where "something interesting" happens. Fortunately, this is easy. For each pair of adjacent active pieces (adjacent in their sorted order), we can find whether they intersect and where, and if it corresponds to a larger value of $x$, add it to a priority queue. Also, for each active piece, we can add its right endpoint (the largest value of $x$ in its domain) to the priority queue. Then finding the next "interesting" value of $x$ amounts to an ExtractMin operation on the priority queue. Also, when you move to the next largest interesting value of $x$, it's easy to update the set of active pieces and maintain them in sorted order.

Let $n$ denote the total number of pieces among the $f\_i$'s, and $k$ the total number of intersections between pieces. Then each iteration can be implemented in $O(\lg n)$ time, and the number of iterations can be upper bounded by $O(n+k)$, so the running time will be $O((n+k) \lg n)$.
> 4 votes

---
Tags: algorithms, computational-geometry, efficiency, numerical-algorithms
---


title: Is search a binary heap operation?

text:
# Question
Title: Is search a binary heap operation?
According to the Wikipedia page, search is "not an operation" on binary heaps (see complexity box at top-right).

Why not? Binary heaps may not be sorted, but they are ordered, and a full graph traversal can find any object in $O(n)$ time, no?

Is the page wrong or am I?

# Answer
> 12 votes
Actually it depends on your point of view, or level of detail.

The **heap**, or better **priority queue**, as abstract data structure usually supports operations like *is-empty*, *add-element*, *delete-min*. And usually not *find-element*. This is the data structure seen as a specification, fixing the set of operations and their behaviour. The implementation is unknown, it can be a linked tree or array.

The wikipedia page however is concerned with the implementation. That is even clear from the title **binary heap**. (You understand the binary heap by looking as if it is a tree, you implement it using an array). In this implementation it is easily seen how to program your operation *find-element*. Technically, that is another abstract data structure (as it has an additional operation aprt from standard heap operations).

In practice heaps (priority queues) are often used for graph algorithms like Dijkstra. There it is important that the priorities stored in the heap can be changed (if we find a shorter route). That is only possible if we are able to find the element in the heap so we can adjust its priority (and reposition the element in the heap). Usually that is done by building another structure on top of the heap so we can efficiently find the positions where elements are stored.

# Answer
> 0 votes
In a binary heap, values are indeed ordered, and a search operation degenerates to a scan of the array if the value/key is \>= last value in the array. If however the value you are searching is close to the first (i.e index close to 0), then you will be able to stop early and not scan the array looking for a value that is not there.

For example(C++), an implementation such as this for a Vector that holds the binary heap:

```
template <class Compare>
uint32_t SearchHeapImpl(const uint32_t idx, const T V, const Compare &cmp) const
{
    if (slots[idx] == V)
        return idx;
     else if (cmp(slots[idx], V))
         return UINT32_MAX;

     const auto leftChild = 2 * idx + 1;

     if (leftChild >= nElements)
         return UINT32_MAX;

     const auto i = SearchHeapImpl(leftChild, V, cmp);

     if (i != UINT32_MAX)
         return i;

     const auto rightChild = leftChild + 1;

     return rightChild >= nElements ? UINT32_MAX : SearchHeapImpl(rightChild, V, cmp);
}

template<class Compare = std::greater<T>>
uint32_t SearchHeap(const T V, const Compare cmp = Compare()) const
{
    return nElements ? SearchHeapImpl(0, V, cmp) : UINT32_MAX;
}

```

will abort search early if `cmp(slots[idx], V) == true`

As others have mentioned, such data structures are suited for O(1) peek, and O(log n) insert and delete operations. A skip list or a self balancing binary tree(e.g red black trees) are usually a better alternative, if you need O(log n) search (you trade O(1) for peek, for O(log n) for search). Of course, they usually more complex, require more memory, and random access patterns may impact performance due to cache hit misses, etc. Win some, lose some.

---
Tags: data-structures, search-algorithms, heaps
---


# Question
Title: Probability Distributions and Computational Complexity
This question is about the intersection of probability theory and computational complexity. One key observation is that some distributions are easier to generate than others. For example, the problem

> Given a number $n$, return a uniformly distributed number $i$ with $0 \leq i \< n$.

is easy to solve. On the other hand, the following problem is or appears to be much harder.

> Given a number $n$, return a number $i$ such that $i$ is (the Gödel number of) a valid proof of length n in Peano arithmetic. Moreover, if the number of such proofs is $pr(n)$, then the probability to get any specific proof of length $n$ should be $\frac{1}{pr(n)}$.

This suggests to me that probability distributions come with a notion of computational complexity. Moreover, this complexity is probably closely related to the underlying decision problems (whether sub-recursive, e.g. $P$, $EXP$, recursive, recursively enumerable, or worse).

My question is: how does one define the computational complexity of probability distributions, especially where the underlying decision problem is not decidable. I'm sure this has been investigated already, but I'm not sure where to look.

# Answer
The complexity of probability distributions comes up particularly in the study of *distributional* problems like DistNP in Levin's theory of average case complexity theory.

A distribution is *P-computable* if its cumulative density function can be evaluated in polynomial time.

A distribution is *P-samplable* if we can sample from them in polynomial time.

If a distribution is P-computable then it is P-sampable. The reverse is not true if certain one-way functions exist.

You can extend the definitions to other complexity classes.

Oded Goldreich has a nice introductory notes on the topic that you may want to check.
> 2 votes

---
Tags: complexity-theory, reference-request, probability-theory, probabilistic-algorithms
---


# Question
Title: Deterministic linear time algorithm to check if one array is a sorted version of the other
Consider the following problem:

**Input:** two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order.

**Query:** do $A$ and $B$ contain the same items (with their multiplicity)?

What is the fastest deterministic algorithm for this problem?
Can it be solved faster than sorting them? Can this problem be solved in deterministic linear time?

# Answer
You haven't specified your computation model, so I will assume the comparison model.

Consider the special case in which the array $B$ is taken from the list $$ \\{1,2\\} \times \\{3,4\\} \times \cdots \times \\{2n-1,2n\\}. $$ In words, the $i$th element is either $2i-1$ or $2i$.

I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, that the algorithm has compared each element in $B$ to its counterpart in $A$. Indeed, suppose that the algorithm concludes that $A$ and $B$ contain the same elements, but never compares the first element of $B$ to its counterpart in $A$. If we switch the first element then the algorithm would proceed in exactly the same way, even though the answer is different. This shows that the algorithm must compare the first element (and any other element) to its counterpart in $A$.

This means that if $A$ and $B$ contain the same elements, then after verifying this the algorithm knows the sorted order of $A$. Hence it must have at least $n!$ different leaves, and so it takes time $\Omega(n\log n)$.
> 14 votes

# Answer
This answer considers a different model of computation: the unit-cost RAM model. In this model, machine words have size $O(\log n)$, and operations on them take $O(1)$ time. We also assume for simplicity that each array element fits in one machine word (and so is at most $n^{O(1)}$ in magnitude).

We will construct a linear time *randomized* algorithm with one-sided error (the algorithm might declare the two arrays to contain the same elements even if this is not the case) for the more difficult problem of determining whether two arrays $a\_1,\ldots,a\_n$ and $b\_1,\ldots,b\_n$ contain the same elements. (We don't require any of them to be sorted.) Our algorithm will make an error with probability at most $1/n$.

The idea is that the following identity holds iff the arrays contain the same elements: $$ \prod\_{i=1}^n (x-a\_i) = \prod\_{i=1}^n (x-b\_i). $$ Computing these polynomials exactly will take too much time. Instead, we choose a random prime $p$ and a random $x\_0$ and test whether $$ \prod\_{i=1}^n (x\_0-a\_i) \equiv \prod\_{i=1}^n (x\_0-b\_i) \pmod{p}. $$ If the arrays are equal, the test will always pass, so let's concentrate on the cases in which the arrays are different. In particular, some coefficient of $\prod\_{i=1}^n (x-a\_i) - \prod\_{i=1}^n (x-b\_i)$ is non-zero. Since $a\_i,b\_i$ have magnitude $n^{O(1)}$, this coefficient has magnitude $2^n n^{O(n)} = n^{O(n)}$, and so it has at most $O(n)$ prime factors of size $\Omega(n)$. This means that if we choose a set of at least $n^2$ primes $p$ of size at least $n^2$ (say), then for a random prime $p$ of this set it will hold with probability at least $1-1/n$ that $$ \prod\_{i=1}^n (x-a\_i) - \prod\_{i=1}^n (x-b\_i) \not\equiv 0 \pmod{p}. $$ A random $x\_0$ modulo $p$ will witness this with probability $1-n/p \geq 1-1/n$ (since a polynomial of degree at most $n$ has at most $n$ roots).

In conclusion, if we choose a random $p$ of size roughly $n^2$ among a set of at least $n^2$ different primes, and a random $x\_0$ modulo $p$, then when the arrays don't contain the same elements, our test will fail with probability $1-O(1/n)$. Running the test takes time $O(n)$ since $p$ fits into a constant number of machine words.

Using polynomial time primality testing and since the density of primes of size roughly $n^2$ is $\Omega(1/\log n)$, we can choose a random prime $p$ in time $(\log n)^{O(1)}$. Choosing a random $x\_0$ modulo $p$ can be implemented in various ways, and is made easier since in our case we don't need a completely uniform random $x\_0$.

In conclusion, our algorithm runs in time $O(n)$, always outputs YES if the arrays contain the same elements, and outputs NO with probability $1-O(1/n)$ if the arrays don't contain the same elements. We can improve the error probability to $1-O(1/n^C)$ for any constant $C$.
> 10 votes

---
Tags: algorithms, reference-request, sorting
---


# Question
Title: Decision vs Optimization version for Problems of two Parameters
Let's say I have an optimization problem called $k$-foo which asks for a solution of size $k$ minimizing some quality criterion.

Now the corresponding decision problem $foo(M)$ would be:
Is there a solution to foo with quality at least $M$ of size $k$.

For problems on one parameter (for example vertex cover) it is obvious that solving the optimization problem sovles the decision problem.

But here I do not see such a correspondance between the $k$-foo optimization problem and the $foo(M)$ decision problem. How does for example showing that $foo(M)$ is NP-hard implies that $k$-foo is NP-hard?

The $k$-center problem is an example of such a problem where the decision version takes the radius as input and asks wether a solution of size $k$ exists.

# Answer
> 2 votes
Having more than one input doesn't change anything:

Consider an optimization problem $MinQ$:

> **Input:** $x, k$
> **Output:** find $y$ satisfying $Q(x,k,y)$ which minimizes $f(x,k,y)$: $$g(x,k) = \min\_{y : Q(x,k,y)} f(x,k,y)$$

The corresponding decision problem $Q$ is:

> **Input:** $x, k, l$
> **Query:** is there a $y$ satisfying $Q(x,k,l)$ such that $f(x,k,y) \leq l$?

To solve the decision problem, we can solve the optimization problem, then check if the output is less than $l$. I.e. there is a very easy reduction from $Q$ to $MinQ$:

> input: $x,k,l$
> 1. $m = MinQ(x,k)$
> 2. return $m \leq k$

---
Tags: reductions, optimization, np-hard, decision-problem
---


title: Parallel vs Distributed Algorithms

text:
# Question
Title: Parallel vs Distributed Algorithms
Let me clear first that I am not asking about parallel (data/task) or distributed computing architecture. A lot had been discussed here. I am just asking a plain theoretical question. What is core principal difference between Parallel and Distributed Algorithms? Below are my under standings:

In parallel algorithms (task parallelism), A big task is divided into two or more sub tasks and each sub task is executed by one processing element (PE) parallely. All sub tasks are depended on each other. What I further understand, a parallel algorithm can be coded using OpenMP which runs on multiprocessors as well as can be coded using MPI which runs on message passing systems. on the other hand, in distributed algorithm, every processing element or node executes the same copy of algorithm. They are totally independent and exchange messages to achieve the common goal. I think distributed algorithms are designed only for multi-computer systems.

It is requested to provide parallel and distributed algorithm for a same example problem for better understanding.

# Answer
An algorithm is *parallel* if there are several processes (tasks, threads, processors) working on it at the same time. Often the tasks run in the same address space, and can communicate/reference results by others freely (low cost).

An algorithm is *distributed* if it is parallel and the tasks run on separate machines (separate address spaces), one task has no direct access to the work of the others. It has to request needed data, or just wait until it is sent to it.

Yes, it is a fuzzy distinction.
> 11 votes

# Answer
One important quantitative distinction is that communication often costs more in distributed computing than in parallel computing.

An important *qualitative* distinction is that distributed algorithms often must deal with failure (e.g., one machine crashes, one machine starts misbehaving and sending spurious messages, or messages get lost or corrupted). In contrast, parallel algorithms typically assume there are no failures and do not have to deal with failures. Thus in the distributed algorithms literature we get algorithms for consensus, Byzantine fault tolerance, and more; those are issues that are specific to distributed systems and normally don't arise in parallel computing (or don't have much importance there).
> 7 votes

# Answer
The terms can mean almost anything, but I will try to present here *one* way in which the terms "parallel algorithms" and "distributed algorithms" are understood. Here we interpret "distributed algorithms" from the perspective of "network computing" (think: algorithms that keep the Internet running).

I will use as a running example the problem of finding a **proper 3-colouring of a directed path** (linked list). I will first describe the problem from the perspective of "traditional" algorithms — those are also known as *centralised algorithms*, to emphasise that they are not distributed, or *sequential algorithms*, to emphasise that they are not parallelised.

## Centralised sequential algorithms

The model of computing is e.g. the familiar **RAM model**.

The input is a linked list that is stored in the main memory of the computer. There is a read-only array $x$ with $n$ elements; node number $x\[i\]$ is the successor of node number $i$.

The output will be also stored in the main memory of the computer. There is a write-only array $y$ with $n$ elements.

We need to find a proper colouring of the list with $3$ colours. That is, for each index $i$ we must choose a colour $y\[i\] \in \\{1,2,3\\}$ such that $y\[i\] \ne y\[j\]$ whenever node $j$ is the successor of node $i$.

There is a single processor that can directly access any part of the main memory. In one time unit, the processor can read from main memory, write to main memory, or perform elementary operations such as arithmetic or comparisons. The **running time** of the algorithm is defined to be the number of time units until the algorithms stops.

Clearly, the problem can be solved in time $O(n)$, and this is optimal. For the upper bound, follow the linked list and colour the nodes with e.g. colours $1,2,1,2,\dotsc$. For the lower bound, observe that we need to write $\Omega(n)$ elements of output.

## Parallel algorithms

The only difference between parallel and sequential algorithms is that we will use the **PRAM model** instead of the **RAM model**. In the PRAM model we can consider any number of processors, but here a particularly interesting case is what happens if there are precisely $n$ processors.

While we will have **multiple processors**, there is still just **one main memory**. As before, the input is stored as a single array in the main memory, and the output will be written in a single array in the main memory.

Now in one time unit, each processor in parallel can read from main memory, write to main memory, or perform elementary operations such as arithmetic or comparisons. Some care is needed with memory accesses that may conflict. For the sake of concreteness, let us focus on the CREW PRAM model: the processors may freely read any part of the memory, but concurrent writes are forbidden.

Now in this setting it is not at all obvious what is the time complexity of $3$-colouring linked lists. Perhaps we could solve the problem in $O(1)$ time, as we have $n$ processors, and only $n$ units of input to read and $n$ units of output to write?

However, it turns out that the time complexity of this problem is precisely $\Theta(\log \log^\* n)$. So it can be solved in *almost* constant time, but not quite.

## Distributed algorithms

Now things change radically. The model of computing is e.g. the **LOCAL model**, which has very little resemblance to RAM or PRAM.

There is no "main memory". There are no "arrays".

We are only given a **computer network** that consists of $n$ nodes. Each node is labelled with a unique identifier (say, a number from $\\{1,2,\dotsc,n\\}$). Each node has two communication ports: one port that connects the node with its successor, and one port that connects it with its predecessor.

**The same (unknown) computer network is both our input and the tool that we are supposed to use to solve the problem.** Each node is a computational entity that has to output its own colour, and the colours have to form a proper colouring of the network (i.e., my colour has to be different from the colours of my neighbours).

Note that everything is distributed: no single entity holds the entire input, and no single entity needs to know the entire output.

All nodes run the same algorithm. In one time unit, all nodes in parallel can send messages to their neighbours, receive messages from their neighbours, or perform elementary operations. The **running time** of the algorithm is defined to be the number of time units until all nodes have stopped and produced their local outputs.

Again, it is not at all obvious what is the time complexity of $3$-colouring. It turns out that it is precisely $\Theta(\log^\* n)$.

---

From this perspective:

* Research on parallel algorithms is primarily about **understanding how to harness the computational power of a massively parallel computer**. For practical applications, consider high-performance computing, number-crunching, multicore, GPU computing, OpenMP, MPI, grids, clouds, clusters, etc.
* Research on distributed algorithms is primarily about **understanding which tasks can be solved efficiently in a distributed system**. For practical applications, consider computer networks, communication networks, social networks, markets, biological systems, chemical systems, physical systems, etc.

For example:

* If you want to know how to multiply two huge matrices efficiently with modern computer hardware, it may be a good idea to first have a look at research related to "parallel algorithms".
* If you want to know if there is any hope people could form stable marriages in their real-world social network, by just exchanging information with those whom they know, it may be a good idea to first have a look at research related to "distributed algorithms".

---

Once again, I emphasise that this is just one way in which the terms are used. There are many other interpretations. However, this is perhaps the most interesting interpretation in the sense that e.g. PRAM and LOCAL are radically different models.

As many other answers show, another possible interpretation is to understand "distributed algorithms" from the perspective of e.g. distributed high-performance computing (computer clusters, cloud computing, MPI, etc.). Then you could indeed say that distributed algorithms are not necessarily that different from e.g. I/O efficient parallel algorithms. At least if we put aside e.g. issues related to fault tolerance.

Incidentally, there is apparently some interest in the community to make the terminology slightly less confusing. People occasionally use the term *distributed graph algorithms* (cf. http://adga.hiit.fi/) or the term *network computing* to emphasise the perspective that I described here. However, there is not that much pressure to do that, as we can use formally precise terms such as "LOCAL" and "CONGEST" for distributed graph algorithms, "PRAM" for parallel algorithms, and e.g. "congested clique" and "BSP" (bulk synchronous parallel) for various in-between cases.

## References
> 6 votes

# Answer
You should distinguish two concepts that are orthogonal:

* system architecture, which can be shared or distributed, meaning that the processing elements have direct access to common resources or on the opposite manage some local resources and can only access the resources of their fellows through them;
* programming model, which can be synchronous (SIMD) or asynchronous (MIMD), meaning that the processing elements execute the same instructions concurrently or independently of each other; one can further distinguish the case where the processing elements use the same code (SPMD) or different pieces (asymmetric processing).

Parallel is a general qualifier that can cover any form of multiprocessing. Distributed is more related to loosely coupled systems.

Multicore parallelism falls in the shared-memory MIMD category. GPGPU supports a mix of shared and distributed memory, operating in a kind of multi-SIMD mode. PC farms are clearly distributed MIMD.
> 2 votes

# Answer
There is no strict theoretical distinction between a parallel algorithm and a distributed one. The meaning of these terms is derived from their conventional use in computing.

A parallel algorithm is one that can be executed by a *parallel computer*. Here, parallelism refers only to the fact that the computer can execute multiple sequential programs simultaneously. (Strictly, even some sequential processors could be called parallel because they execute instructions simultaneously, but this is not the conventional usage of the term parallel computing.) The use of the term *parallel algorithm* also does not imply anything about the programming model or structure of the algorithm (i.e. whether it is shared memory, written in OpenMP or SIMD, MIMD etc.).

A distributed algorithm is one that can be executed by a *distributed computer*, which consists of multiple processors with separate memories. The processors are connected by a communication network allowing them to transfer data between themselves. Typically, distributed computing refers to supercomputers or grid processing systems, however, there are examples of distributed chip multi-processor architectures such as the MIT RAW and Kalray MPPA processors. As with parallel algorithms, the use of the term *distributed algorithm* also does not imply anything about the programming model or algorithm structure. Indeed, it is possible to implement shared memory with a distributed algorithm.
> 1 votes

# Answer
By no means distributed nodes are SIMD or homogenous.

IMO, distributed means that computers are separated is space. The further you separate computing nodes the more distributed your system is. Parallel computing is also distributed but it is not that obvious if it runs within single processor.

That is why you deal with node and transmission failures when regard distributed computing. If all your computation is parallel, it fail at once if your processor is down. It all goes down if something bad happens in that location. The distributed nodes can fail independly however and can experience communication failures when distributed over wide area in space. They can provide redundancy. You also distribute your redundant data to reduce the risk of loosing it.

Another answer also agrees with this point. It identifies multicomputers with distributed whereas says that multiprocessor is parallel. They both are parallel and distributed but there are more chances that you abandon the common memory at larger distances so you can speak about `distributed` here.

This also accommodates the definition given in the most popular answer as soon as we understand that shared-mem threads are basically virtual multiprocessors whereas private-memory processes are virtual multicomputers. Here again, shared mem computing nodes are called 'parallel' computing nodes whereas more loosely coupled private mem coputing nodes are 'distributed'.

It seems that multiprocessor/multicomputer is a computer engeneering division whereas CS community prefer to speak in SW terms of threads and processes.

Distributed computation can even be sequential. Yes, client may make a blocking call to a web-server, which makes blocking calls to DB. There is not parallelism in this model but there is a distribution -- all components are located in different places.
> 0 votes

---
Tags: algorithms, terminology, distributed-systems, parallel-computing
---


# Question
Title: Relations between statements involving universal quantifier, conditional and biconditional
If we consider two predicates:

$b(x)$: x is a boy

$c(x)$: x is clever

Then, there are four statements involving $∀, b(x), c(x), →$ and $↔$ . These are below along with my interpretation of their meaning. Correct me if I am wrong in any of these interpretations.

**(a)** $∀x(b(x)→c(x))$ - All boys are clever

**(b)** $∀x(b(x))→∀x(c(x))$ - If all are boys, then all are clever

**(c)** $∀x(b(x)↔c(x))$ - All boys are clever & all those who are clever are boys

**(d)** $∀x(b(x))↔∀x(c(x))$ - If all are boys, then all are clever & if all are clever then all are boys

I am trying to determine all conditional $(→,↛)$ / bi-conditional $(↔)$ relations between each two of above four. Between any two of these, if there is $↔$, then there is only one relation. However, if there is conditional relation in one direction, then conditional relation in other direction will be invalid. That is there can be $(→,↛)$. So at max there will be $4C\_2\times 2=12$ such relations.

Now to understand these relations, I prepared below table. I considered that there are only two person in the universe $x\_1,x\_2$. $\\{(b,c),(¬b,¬c)\\}$ means $x\_1$ is boy and is clever and $x\_2$ is not a boy and is not clever. The truth values (in table) in boldface (all other than vi, viii and xiv) are one which I feel are correct, though I am not sure. The non bold-faced truth values (vi, viii and xiv) are ones which I am unsure. So, I am more likely make mistake with them.

Based on the truth values in above table, I prepared following relations:

**Q.** Are relations 1 to 12 correct?

**Q.** Also is there some fault in the example predicates $b(x)$ and $c(x)$ themselves?

Actually, I must doing similar for existential quantifier. But afterwards. But am I correct with all this thinking or am just over thinking? Or am severly screwed with my logics?

# Answer
> 1 votes
Reasoning based on examples is fine for *disproving* implications, as you have done. In order to prove that an implication holds, however, you need something more elaborate. One possibility, as mentioned in the comments, is to use resolution to prove the implications. For example, suppose you want to show that (a) implies (b), i.e. that

$\varphi:=(\forall x.(b(c)\to c(x)))\to((\forall x.b(x))\to(\forall x.c(x)))$

is valid. We will do this by deriving a contradiction from $\neg\varphi$, which (using standard equivalences) is equivalent to

$\forall x.(\neg b(x)\vee c(x)))\wedge\forall x.b(x)\wedge\exists x.\neg c(x)$.

Skolemization results in

$(\neg b(x)\vee c(x))\wedge b(x)\wedge\neg c(a)$,

from which resolution derives first $\neg b(a)$ and then an empty clause, i.e. false. Therefore the original implication is valid.

As for your table, note that the example I gave also shows that (d) does not imply (a); the remaining 5 implications look ok.

---
Tags: logic, first-order-logic, propositional-logic
---


# Question
Title: Showing a problem is NP complete? Reducing CLIQUE to KITE.
I've got an exam next week all about this sort of thing. Ie: Find polynomial certifier for a problem, give a polynomial reduction, prove problem X reduces to Y and etc.

The problem is, there doesn't seem to be anyone available in my department to help me until after the test. I really struggle to understand it and get confused all too often when looking at it. So I was wondering if my wonderful chums of the internet could work through a problem with me! (Problem is below if you wanna skip my waffle) I apologise if there is an awful lot of it, I hope this will be useful for me or future lurkers though. Feel free to only answer part of it.

I get that $X \leq\_p Y$ means that given an oracle for Y, we can solve X using a polynomial number of standard computational operations plus a polynomial number of calls to that oracle for Y. I also get that to show a problem Y is NP complete we show:

> There exists a polynomial time certifier for problem Y.
>
> We give a reduction $X \leq\_p Y$ from a known NP problem X. Ie: Showing that X is no harder than Y.

But in practise, I really struggle to do both of these things. It all seems a bit hand wavy at times and the slides used by my course don't really help me, they seem to be used all over the place, here's a copy: http://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/08IntractabilityI.pdf

So, I thought we'd look at a problem that was included on an earlier test for my own module.

# Given that CLIQUE is NP-complete, show that KITE is NP-complete

The CLIQUE decision problem is given a graph G and integer k; decide whether there is an induced complete subgraph of size k. The KITE decision problem is to decide whether there is a kite subgraph of size 2k, which consists of a clique of size k with a k-size tail.

### Creating the certifier

So, how exactly should I write a certifier for KITE? I don't really understand what my certificates should be to be honest. I assume I want an input graph $G=(V,E)$ and then maybe a graph $H=(V',E')$ with an integer $k$ such that $H$ is a kite of $2k$. And then check if G contains H as an induced subgraph? But that seems way too easy considering it was worth 20% of the example paper.

```
algo kiteCertifier(Graph G, Graph H, int k) {
  for each v in V'
    if v not in V
      return no

   for each (u,v) in E'
      if (u,v) not in E
          return no

   return yes
}

```

I suppose what really confuses me is that I don't get how to pick a certificate for problems, perhaps I don't really get what a certificate is or what a certifier should actually be doing.

### Showing $CLIQUE \leq\_p KITE$

This is where I often get confused I think. I've seen different reduction examples showing an implication in one direction, then the other, and many just show iff.

Again, it can't just be as simple as saying every kite has a clique in it can it? That's almost axiomic! I wondered if perhaps I should show a graph contains a clique iff it contains a kite.

Given a clique C of size $2k$ or $2k+1$ (i.e.: odd or even clique) we show there always exists a kite of size $2k$ within it. Consider any k nodes $\\{v\_1,v\_2,...,v\_k\\}$ in the clique. These nodes also form a clique because every node v in the clique is connected to every other node w by an edge. Now consider the nodes $\\{v\_{k+1},v\_{k+2},...,v\_{2k}\\}$. Each node $v\_j$ in this set is connected by an edge to $v\_{j+1}$ since C is a clique. We also have that $v\_k$ is connected to $v\_{k+1}$ and so we now have a kite of size 2k.

Now suppose we have a kite of size 2k, by definition, it contains a clique of size k.

But again, I really don't feel confident enough on this, am I even doing anything vaguely correct? :p Any help would be greatly appreciated.

Thanks very much!

# Answer
With regards to the reduction, you need to show that given an oracle for Kite, you can solve Clique in polynomial time. It doesn't really help that every Kite has a Clique in it: we're interested in solving Clique, but a graph that has a Clique doesn't necessarily have a Kite (if it has a Kite, then it certainly has a Clique - but that's not enough). You need to modify the graph so that if(f) it has a Clique, then it also has a Kite and pass that modified graph as an input to the oracle.

We don't ordinarily believe that an NP-complete problem can be solved in polynomial time. The point of a verifier/certifiate is that *with help*, we can solve it in polynomial time. The certificate is the "help", and you can define the certificate to be almost anything you like. For instance, for Clique, we can ask that the certificate be a list of the vertices that make up the Clique. Verifying then becomes easy: we can check we've indeed been given $k$ vertices, and that there are edges between all of these vertices. If you like, you can think of the certificate as a solution to the problem, and the verifier's job is to check that the solution is correct.
> 2 votes

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


# Question
Title: Recurrence for the number of strings defined by a homomorphism
Let $h$ be the homomorphism defined by $$ h(a) = \mathtt{01}, \quad h(b) = \mathtt{10}, \quad h(c) = \mathtt{0}, \quad h(d) = \mathtt{1} $$ and extended to strings in the usual way. Then the inverse function $h^{-1}$ is defined by $$ h^{-1}(w) = \\{z\in\\{a,b,c,d\\}^\*\mid h(z)=w\\} $$ for any $w\in\\{0,1\\}^\*$. For any such string, define $N(w)=\left|\\,h^{-1}(w)\\,\right|$, namely the number of strings over $a,b,c,d$ that map to $w$. For example, $N(\mathtt{1100})=2$, since $h(ddcc)=h(dbc)=\mathtt{1100}$ and no other strings map to $\mathtt{1100}$.

Give a recursive definition of $N$. For example, if $w = \mathtt{00}x$ for some string $x$, then $N(\mathtt{00}x) = N(\mathtt{0}x)$, since the first $\mathtt{0}$ in $w$ can only be produced from $c$, not from $a$.

Having done that, compute $N(\mathtt{10100101})$.

# Answer
The recurrence relation for $N$ may be defined as $$\begin{align} N(\mathtt{00}x) &= N(\mathtt{0}x)\\ N(\mathtt{01}x) &= N(x)+N(\mathtt{1}x)&\text{from $(a+)\ x$ or $(c+)\ \mathtt{1}x$}\\ N(\mathtt{10}x) &= N(x)+N(\mathtt{0}x)\\ N(\mathtt{11}x) &= N(\mathtt{1}x)\\ N(\mathtt{1}) &= N(\epsilon)&\text{from $(d+)\ \epsilon$}\\ N(\mathtt{0}) &= N(\epsilon)\\ N(\epsilon) &= 1 \end{align}$$

To see this in action, here's what happens when computing $N(\mathtt{0101})$:

You see that $N(\mathtt{0101})=5$, corresponding to the preimages $\\{aa, acd, cbd,cda,cdcd\\}$. To get $N(\mathtt{10100101})$ we can do the same thing and we find that we wind up with five nodes with values $\mathtt{0101}$ so $N(\mathtt{10100101})=25$.
> 1 votes

---
Tags: recurrence-relation
---


# Question
Title: $O(\frac{\log n}{\log \log n})$ algorithm for the prefix parity problem
The prefix parity problem can be defined as follows. You are given a string $S$ of length $n$ and initially every character is $0$. Then you want to build a data structure that can support updates such as follows.

1. For a given $i$ change $S\[i\]$ to either $0$ or $1$
2. for a given $i$ find the parity of $S\[1\]+S\[2\]+...+S\[i\]$.

From the top of my head, there is a solution that can support these type of queries in $O(\log n)$ time, while only using linear space and linear preprocessing time to build the data structure. The idea is to build a complete binary search tree on top of the string where the leafs correspond to individual characters of $S$ and in every internal node we store the sum of all the characters that are leafs in the sub tree defined by that node. In this way we can trivially support both of the updates in $O(\log n)$ time.

However, I found a paper proving a lower bound for this problem, stating that you can not do better than $O(\frac{\log n}{\log \log n})$ for the updates, and I also found the following paper http://link.springer.com/chapter/10.1007%2F3-540-51542-9\_5, and a direct link to the pdf, giving an algorithm achieving that bound, thus being optimal.

I would like to understand this algorithm however the explanation is like 1 page, and a lot of details are missing.

So I was wondering if there is any other source on this problem, because I find it very hard to find any, or is this is the only source available?

thank you in advance

# Answer
I did a quick read over the paper you linked. Based on the ideas given in that paper, here's a simple data structure that obtains an $O(\frac{\log n}{\log\log n})$ time bound on each operation.

You mentioned in your question that you can use balanced, augmented trees to speed this up. In particular, if you have a binary tree and augment each node with the parity of its left subtree, then you can do updates and lookups in time $O(\log n)$ each. That's fast, but not fast enough.

Now, consider the following generalization of your idea. Suppose that instead of using a binary tree, we use a multiway tree with branching factor $k$. We augment each key in each node with the parity of the all the subtrees preceding it (this generalizes the idea of storing the parity of the left subtree). Now, let's think about how we'd do a lookup or update in this tree. To do a lookup, we use a slightly modified version of the binary tree lookup algorithm from before: walk from the top of the tree down to the bottom, at each step accumulating the parity of the subtree purely to the left of each node. The height of the tree in this case will be $O(\log\_k n)$ and we do $O(1)$ work per node, so the cost of doing a lookup will be $O(\log\_k n)$.

However, with this setup, the cost of doing an update increases. In particular, if we change the parity of an element, we need to walk up from the bottom of the tree to the top, changing the stored parity of every key in every node on the path upward. There are $k$ keys per node and $O(\log\_k n)$ nodes on the path upward from the leaves, so the cost of performing an operation like this will be $O(k \log\_k n) = O(\frac{k}{\log k} \log n)$, which is too slow. If we could somehow eliminate this extra $k$ term, then we'd be in business.

The insight the paper has is the following. If you think about our initial problem, we had an array of size $n$ and wanted to be able to compute prefix parities. We now have a $k$-ary tree where, at each node, we need to be able to solve the prefix parity problem on arrays of size $k$ each, since each node caches information about the layers below it. In the above data structure, we solved the prefix parity problem at each node by just storing an array of the prefix parities, which means that if we need to perform an update, the cost is $O(k)$. The paper's insight is that by using a more clever data structure at each node, you can perform these updates significantly more efficiently.

In particular, the paper makes the following insight. Let's suppose that $k$ is "small," for some definition of small that we'll pick later. If you want to solve the prefix parity problem on an array of size $k$, then there are only $2^k$ different possible bit arrays of length $k$. Additionally, there are only $k$ possible lookup queries you could make on a bit array of size $k$. As a result, the number of possible combinations of an array and a query is $k 2^k$. If we pick $k$ to be small enough, we can make this quantity so small that it becomes feasible to precompute the result of every possible array and every possible query. If we do that, then we can update our data structure as follows. In each node of the $k$-way tree, rather than having each key store the parity of its left subtree, we instead store an array of $k$ bits, one for each key in the node. When we want to find the parity of all the nodes to the left of the $i$th child, we just do a lookup in a table indexed by those $k$ bits (treated as an integer) and the index $i$. Provided we can compute this table fast enough, this means that doing a prefix parity query will still take time $O(\log\_k n)$, but now updates take time $O(\log\_k n)$ as well because the cost of a prefix parity query on a given node will be $O(1)$.

The authors of the paper noticed that if you pick $k = \frac{\lg n}{2}$, then the number of possible queries that can be made is $\frac{\lg n}{2} 2^{\frac{\lg n}{2}} = \frac{\lg n}{2} \sqrt{n} = o(n)$. Additionally, the cost of performing any operation on the resulting tree will be $O(\log\_k n) = O(\frac{\log n}{\log \frac{\lg n}{2}}) = O(\frac{\log n}{\log \log n})$. The catch is that you now need to do $o(n)$ precomputation at the start of setting up the data structure. The authors give a way to amortize this cost away by using a different data structure for the initial queries until enough work has been done to justify performing the work necessary to set up the table, though you could argue that you need to spend $O(n)$ time building up the tree in the first place and that this won't affect the overall runtime.

So, in summary, the idea is the following:

* Instead of using an augmented binary tree, use an augmented $k$-ary tree.
* Notice that with small $k$, all possible $k$-bit lists and queries on those lists can be precomputed.
* Use this precomputed data structure at each node in the tree.
* Choose $k = \frac{\lg n}{2}$ to make the tree height, and, therefore, the cost per operations, $O(\frac{\log n}{\log \log n})$.
* Avoid the upfront precomputation cost by using a temporary replacement data structure in each node until the precomputation becomes worthwhile.

All in all, it's a clever data structure. Thanks for asking this question and linking it - I learned a lot in the process!

As an addendum, many of the techniques that went into this data structure are common strategies for speeding up seemingly optimal solutions. The idea of precomputing all possible queries on objects of a small size is often called the Method of Four Russians and can be seen in other data structures like the Fischer-Heun data structure for range minimum queries or the decremental algorithm for tree connectivity. Similarly, the technique of using augmented balanced multiway trees with a logarithmic branching factor comes up in other contexts, like the original deterministic data structure for dynamic graph connectivity, where such an approach is used to speed up connectivity queries from $O(\log n)$ to $O(\frac{\log n}{\log \log n})$.
> 10 votes

---
Tags: algorithms, algorithm-analysis, search-algorithms, lower-bounds
---


# Question
Title: Reccurrence equation and finding suitable algorithm
I'm given the following recurrence equation:

$$\begin{align\*} T(1) &= 0\\ T(n) &= T(n/2) + 1 && \text{when $n \> 1$ is even}\\ T(n) &= T((n+1)/2) + 1 && \text{when $n \> 1$ is odd.} \end{align\*}$$

The problems I have are the following:

1) What does $T(1) = 0$ mean when it comes to writing computer program? It cannot be

```
return some_constant;

```

because this gives the complexity of $T(1) = 1$. Am I right?

2) I'm supposed to find an algorithm whose time complexity can be described using the given equation. I was thinking of Fast Power algorithm, because it has the same $O(n) = \log(n)$, but it's described differently:

$$\begin{align\*} T(1) &= 1\\ T(n) &= T(n/2) + 1 &&\text{when $n \> 1$ is even}\\ T(n) &= T((n-1)/2) + 1 &&\text{when $n \> 1$ is odd.} \end{align\*}$$

# Answer
1) It doesn't mean anything, for two reasons:

* First of all, it's important to distinguish between an algorithm vs the running time of an algorithm. $T(\cdot)$ is not an algorithm; it's a function. For instance, $T(n)$ might be the running time of a computer program, as a function of the size of its input, but it's not the program itself. Anyway, $T(n)$ is just a mathematical function: if it is intended to represent the running time of some algorithm, that should be stated explicitly.
* Second, every algorithm needs to take at least at least one step, so the running time always has to be at least one: it can never be zero. Therefore, it doesn't make sense to have a running time of zero. This might be a bit of a quibble/nitpick.

2) I suggest you do a bit more practice with the reverse: given a simple algorithm, work out a recurrence relation for its running time. Once you feel like you're able to do that confidently, you'll probably find this exercise easy.

See also our reference question, How to come up with the runtime of algorithms?. There's also a more advanced, sophisticated treatment at Is there a system behind the magic of algorithm analysis?.
> 3 votes

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


# Question
Title: Does this algorithm on a circular linked list ever terminate?
Suppose we have a circular linked list that has nodes $1$ to $n$. `L` is a pointer that points to node `1` (with label $1$). Note `i` has a link to `i+1` and we have a link from node `n` to node `1` because the list is circular.

Now we have following pesudo-code:

```
Int SO(LIST *L) {

  While ( L->Next != L ) {
    L->Next = L->Next->Next;
    L = L->Next;
  }

  return L->Data;
}

```

The question is: what is the output for $n=729$ and $n=2200$ what is the output of the above code.

My solution: I check the pesudo-code. My idea is this code has a problem and `L` and `L->Next` never become equal so an infinite loop occurs. Is this correct?

# Answer
> 5 votes
The algorithm will always terminate. Look at the case where $n=2$. Initially we'll have `1->next = 2` and `2->next = 1`. In the first iteration we'll change `1->next` to `1->next->next = (1->next)->next = 2->next = 1` so `1->next` will point to `1` and the loop termination condition applies, so we bail and return `1->data`.

If $n\>2$, every iteration of the loop will point around a node, eliminating it forever from consideration, so every iteration of the loop decreases the number of nodes in play, so we'll always get to the $n=2$ case eventually and then halt.

It might help to think of this as the nightmarish situation where a group of $n$ people have been captured by bloodthirsty pirates. The pirates arrange the group in a circle and, starting at person 1, go around the circle, shooting every other person until only one remains. Where do you want to position yourself so that you are the last surviving person?

This is a well-known problem, called the problem of Josephus, and is often assigned as an exercise in a beginning programming class. The solution is nifty: Given $n$, write it as $n=2^m+k$, where $0\le k \< 2^m$, then the last survivor is the one in initial position $2k+1$ (starting at position 1). Given this, we have that with $n=729$ the survivor will be the one in position 435 and with $n=2200$ the survivor (after a heck of a lot of shooting) will be the one in initial position 305.

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


# Question
Title: Data structure for set of intervals - query for all intervals contains given point
We're given a set of $n$ intervals $\[a\_i, b\_i\]$, $i=1...n$. I am looking for a data structure which makes it possible to query for all intervals that contain the point $x$.

My proposition is using two-dimensional interval (sometimes name is segment) tree. Each query will take $O(\log^2 n + k)$ time, where $k$ is number of interval such that contains point $x$.

Is this correct? Is there a better solution?

# Answer
There are many algorithms for this kind of problem. See, e.g., segment trees and interval trees. The kind of query you mention is known as a "stabbing query".

A segment tree takes $O(n \lg n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time, where $n$ is the number of intervals and $k$ is the number of intervals that contain $x$. An interval tree takes $O(n)$ space, can be built in $O(n \lg n)$ time, and can answer a stabbing query in $O(k + \lg n)$ time. Segment trees are static: they can't be easily modified after they're created. Interval trees are dynamic: you can insert or delete an interval in $O(\lg n)$ time.

Other data structures exist as well. There are also generalizations to higher dimensions, though the running time gets worse in higher dimensions.
> 5 votes

---
Tags: data-structures, intervals
---


# Question
Title: The Inverse of a function with logic operators
How would one be able to tell whether or not a function has an Inverse? I've got a question in my discrete mathematics/ combinatorics class that asks whether or not the following function has an Inverse and if so give the Inverse.

{(p, q) | q =¬p}

where p and q are elements of the set {T, F} where T is tautology and F is contradiction.

I know for regular xy functions, it has an Inverse if it is one to one and also how to find the Inverse. But how would I apply that knowledge to this question?

# Answer
> 1 votes
> The above is an injective function so that means it has an Inverse but will that be p= ¬q?

Yup. We have $f(T)=F, f(F)=T$ so $f^{-1}(F)=T, f^{-1}(T)=F$, which means that $f^{-1}(q)=\lnot q$. In this case $f^{-1}=f$: they're the same function.

---
Tags: discrete-mathematics
---


# Question
Title: In top-down parser how do you match a product $A \rightarrow a_1 | a_2 | ...$, $a_i$s terminals
One procedure for table-driven top-down parsing is given here:
https://www.cs.rochester.edu/~nelson/courses/csc\_173/grammars/parsing.html

This gives for matching the input the lines:

```
else if NextInputSymbol == top then
    /* Match terminal symbol in input */
    Pop(stack)
    /* Get next terminal symbol in input */
    scanner(NextInputSymbol)

```

Which seems to be assuming that every product leading to terminal symbols has only one terminal.

But what if the product leading to terminals is of the following form:
$$A \rightarrow a\_1 | a\_2 | ...$$
where $a\_i$s terminals.

How do you match for such product?

Merely by trying out each terminal symbol?
But reading them all to the stack would cause some overhead for keeping account of how many terminals symbols were added?

---

In predict table form:

# Answer
If a symbol is on the top of the stack, it must have gotten there after being pushed by the code just above the test:

```
        for each symbol on RHS #action do
            Push(symbol)

```

(There is a small imprecision in that code; it doesn't mention that "for each symbol on RHS" actually means "for each symbol on RHS *from right to left*" but that's evident from examining the example stack sequence.)

That code snippet, in turn, was executed after the parse table is used to decide which production will apply, which it did by examining the next input token:

```
    if top is a nonterminal then
        action = ParseTable[top,NextInputSymbol]

```

So let's read the code forwards instead of backwards. We'll suppose that $A$ is on top of the stack, and that $A$ has productions as you indicate:

$$A\to a\_1\\ A\to a\_2\\ ...\\ A\to a\_n$$

Now, we can only push one of those productions. Which one will we push? By the construction of the $ParseTable$, we can say that we will push the production whose $FIRST$ set includes the next input symbol. But in this case, that's even simpler because the $FIRST$ set of each of those productions obviously comprises the single terminal on the RHS of the production. So if the next input symbol is $a\_2$, for example, the ParseTable will indicate an action corresponding to $A\to a\_2$. So the $A$ will be popped from the top of the stack and then $a\_2$ will be pushed.

At the next step, the top of the stack is a terminal; precisely the terminal $a\_2$. And, surprise!, the next input symbol is also $a\_2$. So we can just pop the stack and continue with the parse.

In short, the $ParseTable$ lookup substitutes for that long imaginary sequence of `if` statements. The lookup could internally be implemented with such a chain, but in real-life it would probably turn out to be a more efficient table lookup algorithm.
> 2 votes

---
Tags: parsers
---


# Question
Title: What is the Haskell-style type signature called (i.e., who is it named after)?
A type signature in Haskell is written in the following format:

```
functionName :: arg1Type -> arg2Type -> returnType

```

There's a (hyphenated, after a person or persons) name for this style of type signature (which predates Haskell), but it's escaping me and I can't find it anywhere.

# Answer
> 2 votes
Is it Hindley-Milner type system by any chance?

---
Tags: reference-request, programming-languages, type-theory, notation
---


# Question
Title: Complexity of solving LP with a non-linear growth in variables/constraints
It has been shown that any Linear Program (LP) can be solved in a polynomial number of steps. An example of such algorithm is the ellipsoid method.

> To solve a problem which has $k$ variables and can be encoded in $L$ input bits, this algorithm uses $O(k^4L)$ pseudo-arithmetic operations on numbers with $O(L)$ digits.

I have a problem that can be formulated as a LP, but yet has been proven to be NP-hard. The proof is rather hard and complicated for my understanding, so I just want to argue why it is, at least, not in P.

Consider the following excerpts from here.

I can see why the ellipsoid algorithm (or any LP solving algorithm) would take exponential amount of steps because the number of variables $k$ is exponential in $n$ ($k = m^n$).

Now the number of variables is not exponential anymore ($k = nm^2$) and I can not argue why solving the Dual LP would take an exponential number of steps. The only thing I could come up with is that $L$ (number of input bits) could be exponential in size because of the exponential number of constraints ($m^n$). But that is just a wild guess.

Additionally, if the statement about $L$ is true, than it is exponential in the primal LP as well, meaning that both $k$ and $L$ in $O(k^4L)$ are exponential. Does that mean that solving the dual LP is more efficient than solving the primal one, in which only $L$ is exponential but not $k$?

NB: The context is finding optimal correlated equilibria in succinct games.

# Answer
The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of *constraints*. This is hidden in the parameter $L$ which is the input size; clearly $L$ is at least the number of constraints. If there are exponentially many constraints, then *any* generic algorithms must take exponential time, since it has to consider all the constraints.

In some cases it is possible to solve linear programs with exponentially many constraints efficiently. This is the case if there is a *separation oracle* which, given a variable assignment, outputs a violated constraint (if any). If this can be done efficiently, then the ellipsoid algorithm can solve the linear program efficiently (at least approximately). If your problem is NP-hard then there is (probably) no efficient separation oracle for the dual LP. (Another possible reason for your problem to be hard is that *rounding* a solution could be hard or, perhaps, impossible.)
> 6 votes

---
Tags: time-complexity, optimization, np-hard, linear-programming, game-theory
---


# Question
Title: Is it possible to use a copy-on-write strategy to modify a B+ tree?
Alright, I'm not sure if this is more of a stack overflow question, but I'm going to try here because you folks seem more suited.

CouchDB makes an interesting claim about using an "append only" B+ tree to index its documents. Specifically...

> "In a B-tree, data is kept only in leaf nodes. CouchDB B-trees append data only to the database file that keeps the B-tree on disk and grows only at the end. Add a new document? The file grows at the end. Delete a document? That gets recorded at the end of the file."

and

> "CouchDB is actually using a B+ tree, which is a slight variation of the B-tree that trades a bit of (disk) space for speed. When we say B-tree, we mean CouchDB’s B+ tree."

SOURCE: CouchDB Documentation

This paper, describes the problem with an "append only" or "copy on write" implementation of a B+ tree. It suggests that such optimistic concurrency strategies are only available to a standard B tree. Specifically...

> "In a regular b-tree leaves are chained together. This is used for tree rebalancing and range lookups. In a b-tree that is updated using copy-on- write leaves cannot be linked together. For example, Figure 2 shows a tree whose rightmost leaf node is C and where the leaves are linked from left to right. If C is updated the entire tree needs to be shadowed. Without leaf-pointers only C, B, and A require shadowing."

SOURCE: Rodeh O.

So the actual question...

Is possible to implement a copy-on-write B+ tree?

# Answer
Yes it is. The trick is to use the size of file (where is the tree stored) as the means of calculating offset of the new root. In other words, when one modifies a leaf, most of the tree wont change and the blocks which do change get appended at the end, with root coming last.

More here: http://www.bzero.se/ldapd/btree.html
> 3 votes

---
Tags: algorithms, trees, search-trees
---


# Question
Title: Show this language is non-regular using pumping lemma: B = {ww | w ∈ {a,b,c,...,z)*}
The question I'm working from is:

Prove whether or not a finite automation exists that recognises the following language:

B = {ww | w ∈ {a,b,c,...,z)\*}

***EDIT***

So I believe this is a non-regular language. My understanding of pumping lemma is not great but this was my solution:

S = apbapb

Where S is a valid string in the language and p is the pumping length.

S = aaaabaaaab for example when p = 4

S = xyz // s can be split into xyz components

| x y | \<= p

SO y must be all a's before the first b e.g. a | aaa | baaaab

xy2z = aaaaaaabaaaab

xy2z is not in B

Therefore B is not regular

Apparently though this is wrong, please could someone explain why / how to obtain the right answer?

# Answer
> 2 votes
Your proof using the pumping lemma is wrong. You choose a pumping lemma constant $p=4$ but what happens if $p=5$ works? The pumping lemma tell us that there exists a constant $p$. Now you have to try all the remaining possible values of $p$.

I recommend you to study carefully the pumping lemma first. It is a bad idea to try using it without understanding it. After that if you want to assimilate it more you can check this answer: https://cs.stackexchange.com/a/50618/31129 where I explain some common mistakes.

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


# Question
Title: Why is c) a combinational circuit, but d) not?
I am doing practice after just learning what combinational circuits are, yet I am unsure of why (c) is combinational, but (d) is not. Can someone please explain to me why this is? The Solution mentions that for (d) node n6 connects to the output terminals of both I3 and I4, but how is this different from the circuit in (c)?

---

# Answer
A combinatorial circuit corresponds to a "straight-line program" that computes the outputs of the circuit given its inputs. (It has to satisfy some constraints that will exclude circuit (f) among others.)

As an example, if we denote the inputs of circuit (c) by $x\_1,x\_2,x\_3,x\_4$ (top to bottom) and the output by $o$, then using $g\_1,g\_2$ for the intermediate gates, the circuit corresponds to the program

> $g\_1 = x\_1 \land x\_2$
>
> $g\_2 = x\_3 \land x\_4$
>
> $o = g\_1 \lor g\_2$

It also corresponds to the formula $(x\_1 \land x\_2) \lor (x\_3 \land x\_4)$. However, not every circuit corresponds to a formula. (The difference is that in some circuits, the output of a gate can appear as an input to more than one gate.)

Circuit (d) cannot be written in this form, since the outputs of I3 and I4 are wired together. What is the relation between the input to the rightmost gate and the outputs of I3 and I4? Not something that can be described combinatorially.

The difference between circuit (c) and circuit (d) is that in circuit (c) wires are not joined together. Rather, the output of each of the AND gates is connected to its own input of the OR gate. In contrast, in circuit (d) the rightmost NOT gate has only one input, but two incoming wires that must share the same input pin.
> 4 votes

---
Tags: computer-architecture, logic, circuits, digital-circuits
---


# Question
Title: Recommender System - Binary Ratings without explicit dislike
I'm currently looking into developing a system in which media from various sources is collected, with the notion that the media collected for each user is media they **'like'**. This results in a set of *n* users, each with their own respective set of *m* liked items.

Most papers on recommender systems I find either require explicit ratings, or work within a binary domain with likes **and dislikes.**

How would I go about making recommendations based mainly on what is in a users preferred / liked set, without information on what they dislike?

Thanks.

# Answer
> 2 votes
You can use one-class classification, in which the learner is given only positive examples, but must later on classify new instance into positive and negative. An example is intrusion detection – the learner is given the network in its working state, and tries to identify outlying behavior.

---
Tags: machine-learning
---


# Question
Title: Doesn't this method of Machine Learning do perfectly fine?
There's many types of Machine Learning methods, but one sticks in my mind, and I don't understand why for ex. Q Learning was made instead of just using the following method:

Method: Say we give the robot some Triggers, we will implant a pre-installed image of a girl, taste of fries, sound of birds, and acceleration. When it Guesses Actions - that get a trigger, it saves actions just done and links them to senses just saved and labels the senses&actions as + or - based on if matched a + or - trigger and gives it a rating of how much it matched, then when it senses it again later, it matches memory and links to the actions and they are initiated, it walks to the girl/sound of birds chirping.

Seeing that, why is Q Learning so complex the way it works?

# Answer
What you are describing is similar to what virus detection software does. It is given a list of signatures and then searches for them in its input stream. In contrast, machine learning works in a setting in which you don't expect identical inputs to typically appear. For example, consider the task of recognizing digits. Here are some examples of the digit 2, from a paper of Mayraz and Hinton:

None of these is identical to the others. Suppose that you only train your learner with the upper half. When encountering a digit from the bottom half, how would you recognize it as 2? You need to generalize your training examples. This is what machine learning is about.
> 2 votes

---
Tags: machine-learning
---


# Question
Title: Check if given vertices form a connected subtree in a graph
**The approach described in this question is wrong. It'll find false positives for disconnected components with multiple vertices. See D.W.'s answer for a reliable alternative.**

This might be a simple question, but I can't seem to find a clear cut algorithm for this. I'm given a set of vertices from a graph and I need to determine whether they form a connected subtree in this original graph. I also have the neighbors of each of the vertices and an edge list to work with.

My approach would be to loop over the vertices and check if each one has at least one of the other given vertices as a direct neighbor. If one of them hasn't, it must be disconnected from the rest of the vertices, so the set can't form a connected subtree and we can return false early. So like this:

```
foreach (vertex in input)
{
   connectedToAny = false;

   foreach(other in input)
   {
          if (vertex.neighbors.contains(other))
          {
                 connectedToAny = true;
                 break;
          }
   }

   if (!connectedToAny)
   {
          return false;
   }
}

return true;

```

I'm aware this doesn't preclude the existence of cycles, but I'm happy to ignore this for now.

> My main question is if this approach is in fact correct, or whether I'm missing cases where this could lead to false positives or negatives.

I'd also be happy to hear if there's a more efficient approach. I have also considered using a more conventional depth first search from any of the input vertices to see if they're connected, but I think I'd have to compute $neighbors \cap input$ at each recursion to specialize from simply *connected* (possibly via other vertices) to *directly connected subtree*, right?

# Answer
You can do this in linear time. You can tell if they're connected by keeping only those vertices and edges between them, and testing if the resulting graph is connected using standard algorithms (e.g., DFS). You can tell if they're a tree by testing if the resulting graph has any cycles (e.g., using DFS).
> 1 votes

---
Tags: graphs, connected, subtree
---


title: L=ww is not a CFL

text:
# Question
Title: L=ww is not a CFL
I am studying CFL at the moment and I found this confusing. What I've just read is that, $L=\\{ww\\}$ is not a CFL. The proof showed it by using pumping lemma for CFL. ($w=0^n1^n0^n1^n$) and I fully understood the proof.

Here comes the question. I understand that $L1=\\{ww^R\\}$ can be constructed by NPDA, and thus a CFL. However, if I use pumping lemma for this, i.e., $w=0^n1^n1^n0^n$, I can show that this specific sentence does not satisfy pumping lemma as well.

**Pumping lemma**

Let $L1$ be a CFL. Then, there exists n such that for any $w ∈ L$ and $|w|\geq n$, $w$ can be decomposed as $w=uvxyz$ such that

1) $|vxy|\leq n$

2) $|vy| \geq 1$

3) $w\_i=uv^ixy^iz$ ∈ $L1$, for all $i \geq 0$

By setting $w=0^n1^n1^n0^n$ and if $v,y$ ∈ $0^+$ in the first half, regardless of how many times I pump, $ww^R$ does not belong to $L1$ anymore. Thus, since the pumping lemma should be satisfied for every possible case, I can conclude that it is not CFL.

Note again that I know $L1$ can be designed with NPDA. **What is my mistake while proving using pumping lemma?**

I am really confused about this. Can anyone answer my question?

My first guess is...

In order to show a language is CFL, I should first try to construct a PDA accepting the language, and if it is not possible, I should show that it is not a CFL by using pumping lemma. However, what if I could not find a PDA although there exists one?

P.S. I actually posted this question yesterday with not much detailed explanation, therefore I posted again.

Thanks in advance

# Answer
> 3 votes
You are right in one thing. You can't pump the first half. But you clearly are confusing the pumping lemma for CFL with the version for regular languages. As you wrote the decomposition of $w$ is $uvxyz$. You can use a large substring $u$ to pump in the second half of $w$ but that generate the same conclusion as pumping the first half. What to do then? You can pump in the half of the word. Each time you add a 1 in the first half you can add a 1 in the second half so the decomposition exist and you can´t say that $L1$ is not CFL.

Summarizing the decomposition exists. For example:

$u=0^n1^{n-1}$

$v=1$

$x=\epsilon$

$y=1$

$z=1^{n-1}0^n$

So we can't conclude anything from the pumping lemma. It is time to choose another word to try it again or generate a PDA to prove that $L1$ is CFL.

---
Tags: formal-languages, pumping-lemma
---


# Question
Title: What does the term "Finite" stands for in Finite State Machines?
Do we consider Pushdown Automata, Turing Machines in Finite State Machines?
If we don't, then what does the term "Finite" stands for in Finite state machines, as PDAs & TMs are also defined to have Finite Number of States?

# Answer
The number of states is finite in *finite state machines* (aka regular laguages).

In contrast, in a push-down machine (PDA) the number of states is potentialy infinite (more correctly unbounded, leaving out stack size limitations), but the machine itself does not bound the number of states (that is why a stack is used) (aka context-free languages)

To put it in another way, a finite state machine can **store all its needed *state* (in the general sense, including transition rules, current symbol etc..)** only in **fixed finite storage**, unlike push-down machine (or other automaton) which cannot do that.

A PDA, for example, by its design and definition, does not determine a fixed size needed for all its *state* (it is *unbounded*, aka *infinite* in this respect)

And to clear up the confusion, PDAs (and other automata) may have *finite number of transition rules* but *not finite number of (potential) states (also refered as configurations)* (see above).

**update**

**note** that a PDA does not necesarily need infinite storage, for example any given PDA can at any given time only need finite storage and even during its whole operation its storage size does not exceed an upper limit. However this is not fixed before-hand by the machine itself (like for FSMs) and thus is formaly unbounded. In fact for PDAs the storage size is determined by the input size itself and is a linear function of the length of the input (which are part of automata refered as LBAs, linear-bounded-automata, in which one end is always fixed, the bottom of the stack)
> 5 votes

---
Tags: terminology, automata, finite-automata
---


# Question
Title: What is the difference between an embedded system and dedicated system?
To my understanding,

a dedicated system is a computer system capable of performing 1 specific task an embedded system is a computer system within a larger system that performs a specific task

Is there a difference that i'm missing or is dedicated system just a more generic term for referring to things like 'file server'.

Thanks

# Answer
An embedded system is embedded in some larger device/system. For example, a computer used to control a car is embedded, or the microprocessor controlling e.g. a washing machine.

A dedicated system is one which is used for one task only, like file serving or running a database.

Most embedded systems are dedicated (to their specific task(s)). There isn't a clear cut definition.
> 2 votes

# Answer
An embedded system, is like a microprocessor, not to be confused with a CPU. It requires no extra software to work.
> -2 votes

---
Tags: terminology
---


# Question
Title: Where can I find a reasonable NLP CFG or CSG for English?
I'm looking to do natural language parsing and looking for how the CFG (or CSG) should be defined for English.

Surely one'd expect to find one from the internet already, but do you know where?

**It needs to be in "formal grammar" form**, not an implementation (e.g. a Python library).

It has to allow for as wide range of sentences as possible to be parsed correctly.

---

Something that I could be looking at:

```
S -> NP VP | VP
NP -> D N | N | N NP
VP -> V | V NP | V PP | V NP PP
PP -> P NP

```

But how sufficient is this?

---

Related:
https://english.stackexchange.com/questions/32447/is-there-an-ebnf-that-covers-all-of-english

# Answer
It is uncommon to use a "closed set" context free grammar because the number of production rules is staggeringly large. The typical approach is to recover a probabilistic context free grammar from a treebank (e.g., the Penn Treebank) in order to do statistical parsing (via probabilistic CKY, Earley, etc).

The only time you might want a "closed set" is when working with toy data in which case you may define an overly simplistic subset of English grammar dealing with sentences, noun phrases, verb phrases, and so on. Such miniature grammars can be found in standard NLP texts such as Jurafsky and Martin, and Manning and Schuetz.
> 1 votes

---
Tags: context-free, formal-grammars, natural-language-processing
---


# Question
Title: How to detect plurals in English sentences?
I'm wondering how to detect English plurals in natural language sentences.

Such as:

fish
computer**s**
house**s**
...

Using Earley parsing I'm able to get to the **s** or **no-s**, but I have difficulties in understanding how to figure out whether the ending **s** is because the word is in plural form. Or whether with **no-s** the word is in plural form.

Is this kind of thing doable without some database of words and their plurals? I could leverage such database though, if such exists.

# Answer
> 4 votes
Morphological parsing requires a lexicon (stems and their part of speech) , morphotactics (ordering of morpheme classes), and orthographic rules (e.g. fox + PL = foxes rather than foxs).

The preferred approach is to use a composition of finite state transducers to map a surface level representation (e.g., foxes) into its lexical representation (e.g., fox +N +Pl).

For a robust method, you are better off using an existing system like Foma, lttoolbox, or SFST than writing your own system since these systems come with rich morphological data sets.

---
Tags: parsers, natural-language-processing
---