# Question
Title: Do different variants of Mergesort have different runtime?
One of my courses introduced the following question:

> Given the recurrence relation for mergesort:
>
> $T(n) = 2T(n/2) + n$
>
> How would the following parameter passing strategies influence the relation and running time of the algorithm:
>
> 1. A pointer to the array is passed to the sorting function,
> 2. The entire array is copied to a separate location before applying the sorting function,
> 3. A subsection of the array is copied to a separate location before applying the sorting function on that subsection.

For 1., since this is how mergesort is used most of the time, we can solve it easily using the master theorem.

$f(n) = \Theta(n^{\log\_b a}) = \Theta(n) \implies T(n) = \Theta(n \log n)$

For 2. however, I am a bit baffled. Although we do an additional work of $O(n)$, we are only doing so *once* at the beginning of the sort. Hence, doing one additional instance of $O(n)$ work should not influence the order of the running time (because it already *is* of a larger order). Hence, for both 2. and 3. the running time would remain at $T(n) = \Theta(n \log n)$.

Is this reasoning valid? Something tells me that the $O(n)$ copying should have more of an impact, but I can't seem to give myself a good enough reason that it should be responsible to slow it down enough so that it would worse (i.e. $O(n^2)$).

Any thoughts or hints would be quite appreciated!

# Answer
Note first that we are talking about an algorithmic *idea* here; in order to apply a meaningful analysis, we would need at least pseudocode for the three variants.

Note furthermore that the given recurrence is most likely only valid in the limit. It is also not clear what the complexity measure is. Comparisons? In that case, it is clear that none of the adaptions change the measure at all. Basic operations? That would make more sense.

1. I agree with your reasoning; this seems to be the basic variant. Note again, however, that you'd have to look in the actual algorithm for its analysis. In particular, applying Mergesort in-place is uncommon.
2. Copying the entire array *once* adds a linear term globally, so the recurrence does not change. If you are only after $\Theta$-behaviour, ignore it (since the actual algorithm dominates).
3. Now this adds linear overhead to *every call* of the routine, changing the recurrence from $\ldots + n$ to something like $\ldots + 2n$. Of course, this results only in a different constant so the result is again not influenced (see Master Theorem).
> 4 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis, recurrence-relation, sorting
---


# Question
Title: Why does the map function in MapReduce take two parameters?
I am playing around with MapReduce and wanted to ask why the `map` function takes two inputs `(key, value)`? Why not just pass along the value?

Specifically, if you look at the word count example on Wikipedia page you will see that the map function is:

```
function map(String name, String document):
// name: document name
// document: document contents
  for each word w in document:
    emit (w, 1)

```

However, the function never does anything with the parameter "name". Why even pass it in?

# Answer
Let me quote the documentation (emphasis mine):

> *Map* You write a map function that runs once for each input value. It **returns a collection of name-value pairs** which are passed on to the next stage. If there are many, many input values, then this function runs many, many times. The framework divides up the input so that subsets are **handled in parallel on multiple instances of your application**. A typical map function could count things that occur in each input value that matches some filter.

So there are two immediate uses I can imagine:

* Use the "chunk" name in the returned names. For example, you might want to distinguish `bible_author` from `fiftyshadesofgrey_author` in the result.
* Identify "subprocesses". If anything goes wrong (and something *will* go wrong) an error message like "Error processing `bible`: Illegal character at position 666" is obviously only useful if you include the document name.

And, of course, you may also want to use the name in the actual computation. A general API should cover that case.
> 1 votes

---
Tags: terminology, programming-languages, parallel-computing
---


title: Help with recurrence solutions

text:
# Question
Title: Help with recurrence solutions
We started learning recurrences and I am having trouble with some of the problems. Our professor is having us substitute in $n=2^m$ and $S(m)=T(2^m)$ then writing down equations and summing them all up. I understand the substitution part, but not how to simplify the end result.

One of the problems I am stuck on is $T(n)=2T(n/2)+n^3$ where $T(2)=c$, When I sub in $n=2^m$ and $S(m)=T(2^m)$ I get:

$S(m)=2S(m-1)+(2^m)^3$

$S(m-1)=2S(m-2)+(2^{m-1})^3$

...

$S(3)=2S(2)+(2^{3})^3$

$S(2)=2S(1)+(2^{2})^3$

$S(1)=c$

Now because there is a coefficient on the right side we have to multiply each equation by a power of 2 so we can sum them.

$S(m)=2S(m-1)+(2^m)^3$

$2\*S(m-1)=2^2S(m-2)+2\*(2^{m-1})^3$

...

$2^{m-3}\*S(3)=2^{m-2}S(2)+2^{m-3}(2^{3})^3$

$2^{m-2}\*S(2)=2^{m-1}S(1)+2^{m-2}(2^{2})^3$

$2^{m-1}S(1)=c\*2^{m-1}$

So sum these and we get:

$S(m)=(2^m)^3+2\*(2^{m-1})^3+2^2\*(2^{m-2})^3+...+2^{m-3}(2^{3})^3+2^{m-2}(2^{2})^3+c\*2^{m-1}$

And this is where I get stuck, how can I simplify this? I tried dividing by $(2^m)^3$ but that came out to a awful mess. The other two I'm having trouble with are $T(n)=16T(n/4)+n^2$ and $T(n)=7T(n/2)+n^2$ Any help would be appreciated.

# Answer
> 2 votes
Once you have $S(m) = 2 S(m-1) + 2^{3m}$, you can divide by $2^m$ and obtain : $$\frac{S(m)}{2^m} = \frac{S(m-1)}{2^{m-1}} + 2^{2m}$$ Thus, setting $P(m) = \frac{S(m)}{2^m}$, you should be able to find $P(m)$, then $S(m)$.

---
Tags: proof-techniques, recurrence-relation
---


# Question
Title: Are there problems that are polynomial-time equivalent to factoring composites?
It seems that factoring a number known to be composite is in its own interesting little complexity class, e.g. polynomial time using quantum computing even though no one has proved $\mathsf{P} = \mathsf{NP}$ for quantum computing.

Are there interesting, non-obvious examples of problems with polynomial-time verifiability for solutions, which have been shown to be polynomial-time equivalent to factoring a composite number into primes, under the classical non-quantum computational model?

# Answer
> 2 votes
I assume that you meant to consider the difference between $BQP$ and $NP$ rather than $P$ and $NP$. $P$ is primarily only defined using deterministic time bounded Turing Machines while $BQP$ is specific to bounded error polytime quantum computers.

*Factoring* is, of course, in $NP$ (function version being in $\mathcal{F}\_{NP}$), so it should easily follow that anything polynomial time reducible to factoring is going to have a polynomial time verifier. If you were actually asking if any polynomial time verifiers share the same "hardness" as factoring, then the answer is: no idea. It would require making assumptions about whether or not factoring is in $P$.

I am afraid that I could not find a non-number theoretic set of problems that are known to be polynomial time reducible to factoring. Despite much study, the complexity of factoring is still very open. Knowing where it falls will provide many additional answers to your question. I'll go over what I have:

Two well known ones are computing *Quadratic Residuosity* and computing the *Euler Totient*, $\phi (n)$. The equivalence between factoring and Euler totient is very straight forward, especially to those that have ever looked into RSA.

A paper by Tibor Jager and Jorg Schwenk shows that the *Quadratic Residuosity Problem* and *Subgroup Membership Problem* are "generically equivalent" to factoring.

It is still open as to whether or not the *Discrete Log Problem* and the decision version of *Composite Residuosity* are also equivalent. Though, Pomykała wrote on the polynomial time reducibility of *Discrete Log* (composite moduli) to *Factoring* recently and presented a deterministic subexponential time algorithm for just that.

You may have a lot of success researching the *Hidden Subgroup Problem*. For finite Abelian groups, quantum computers have the advantage of being able to do this in polynomial time via Fourier transforms. Shor uses the fact that *Factoring*, *Discrete Log*, and some others are special cases of this problem.

---
Tags: complexity-theory, complexity-classes, factoring
---


title: Confused by Floating Point Spacing

text:
# Question
Title: Confused by Floating Point Spacing
I'm currently taking a numerical analysis class in college and we're covering floating point systems. For the most part, I have a good grasp on it. However, something I can't seem to visualize, and haven't seen any totally lucid explanations about after searching extensively, is spacing between floating point numbers. Also of note is that I'm talking about IEEE-754 here, but it applies to general systems too.

### The Things I Do Understand:

* The area between $\[-1,1\]$ is a denormalized area.
* The areas after $1$ and less than $-1$ are where the normalized floating point numbers reside.
* The floating point numbers *between* perfect powers of the base are uniformly spaced, but the spacing varies from one perfect power of the base to another.
* The spacing between values between two perfect powers is proportional to the power on the left for positive numbers and the power on the right for negative numbers. (i.e. on a number line, the uniformly-spaced values between two low powers are closer together than between a higher power.)

### What I'm Struggling to Understand

* From my understanding, the machine epsilon $\epsilon$ is a fundamental unit of spacing with respect to the floating point number line. That is, between $\[1,B\]$ where $B$ is the base, all values are $\epsilon$ apart. Then, you can scale any arbitrary floating point number by that fundamental machine epsilon and that product is the uniform spacing for that floating point number's associated power range. Is this even a correct interpretation?

I also read that $\epsilon$ is an upper bound for relative error, so I'm not really sure how that fits into my explanation of it being an indivisible spacing unit.
* One of the questions I haven't been able to answer is what the minimum and maximum spacing between two positive floating point numbers is. I can trick myself into thinking I understand why multiplying the x's associated $B^e \cdot \epsilon$, where x is an arbitrary floating point number and $e$ is that number's corresponding exponent, yields the upper bound on error and therefore spacing, so $B^e \cdot \epsilon$ would be the maximum spacing.

Minimum spacing truly boggles my mind right now, though. If the machine epsilon is the indivisible unit of spacing, then for example, how could we have more minimal spacing than between $1$ and $1 + \epsilon$? Wouldn't that just be left to the rounding rule used (if round-to-nearest, it would depend whether the number is closer to $1$ or $1 + \epsilon$, since it'll be rounded to one of those two).

Basically, if you could explain this in plain-english it would really help me get a solid understanding of what's going on at the number line level.

# Answer
> 7 votes
This is best explained in the base 10 equivalent: scientific notation

In scientific notation you have a mantissa and a exponent such that the value is $\mathrm{mantissa} \cdot 10^{\mathrm{exponent}}$.

In a computer floating point the mantissa is always the same size of significant digits (a double precision has around 16 digits) and the exponent is bounded.

Let's take a arbitrary format for our examples: a 4 digit mantissa and a 1 digit exponent

* 1 is then represented by $1.000 \cdot 10 ^ 0$
* the maximum value you can represent is $9.999 \cdot 10 ^ 9$
* the minimum absolute value you can represent in a normalized fashion (first digit is not 0) is $1.000 \cdot 10 ^ {-9}$
* $2\\,147\\,483\\,648$ is most closely represented by $2.147 \cdot 10 ^ 9$ (note that this is actually $2\\,147\\,000\\,000$)

Here you'll see that to represent that large number there is an absolute error of $483\\,648$ or a relative error of $0.0002$.

A denormalized value would be when the first digit is 0 like with $0.001 \cdot 10 ^ {-9}$, here it isn't that significant but in binary the first digit of the mantissa is assumed to be $1$. So that first bullet point is false, denormalised is all values in $(0,B^{\mathrm{minExp}}) $and $(-B^{\mathrm{minExp}},0)$.

Our machine epsilon here is $0.001$ (going from 1 to the next representable value 1.001).

So for numbers with exponent $0$ there is an accuracy of $0.001$, while for numbers with exponent 5 there is a accuracy of $100$.

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


title: Post-selection and complexity theory

text:
# Question
Title: Post-selection and complexity theory
I read about post-selection and didn't understand the meaning behind this thing. I didn't understand the Wikipedia article well, so what is a simple but understandable explanation of post-selection and how to use it in complexity?

# Answer
> 4 votes
I went ahead and looked to see if there was a good resource that I could provide, but beyond some resources that Aaronson wrote, I could not find any good additional supplements. You should check out what he says and see if that helps. However, I'll do my best to provide a very quick and potentially hand wavy interpretation.

**Basic Quantum Computing: (If Needed)**

Consider a quantum computer with some number of quantum bits. Before we measure quantum bits, they are in a superposition of many possible output states. When measured, they collapse to a single state that is sampled from a probability distribution of states. In other words, during measurement, some state is "chosen" randomly from all possible states, with some more likely than others to be "chosen".

A quantum computation takes these unmeasured qbits and methodically applies quantum logic gates. Doing this influences that superposition (the probability distribution of final states). When we are done applying quantum gates, we perform a measurement on the entangled qbits (final quantum state). This gives us a result we can use, but all the underlying quantum information is lost, preventing us from measuring again. The quantum computation would have to be repeated from scratch in order to perform another measurement. To account for errors, quantum computations are usually performed multiple times to build up additional confidence in the final result.

**Postselection in a Computation:**

When computing a decision problem, let us just designate a single quantum bit, $q\_1$, as our "answer" where $\lvert1\rangle$ and $\lvert0\rangle$ correspond to accept and reject.

*Postselection* introduces conditional probability into the mix. We say we want to *postselect* a quantum bit, $q\_1$,for a specified outcome of a second bit, $q\_2$. To simplify matters, let us assume that this is the last thing that we do before measuring. Without postselecting, our machine would accept with $\mathbb{P}\left\[q\_1=\lvert1\rangle\right\]$. If we use post selection as described above, we are telling $q\_1$ to only be in a superposition of states that work given that $q\_2=\lvert1\rangle$. The probability that the computation accepts now becomes $\mathbb{P}\left\[q\_1=\lvert1\rangle\mid q\_2=\lvert1\rangle \right\]$. This essentially filters out all possible states that $q\_1$ could have been in if $q\_2 = \lvert0\rangle$.

If $q\_2$ happened to be defined as an indicator of a "good" computation in our experiment, then, by using postselection, we would have thrown out all the "bad" computations.

**Note:** $\mathbb{P}\left\[q\_2=\lvert1\rangle\right\]$ must be $\>0$ or else the conditional probability measure is not well defined.

So in short, postselection gives us the ability to force quantum bits to think that another quantum bit is in a specific state we choose. This lets us filter out a lot of results that we consider to be useless to us when we measure our quantum state. As demonstrated in Aaronson's proof of $\text{PostBQP = PP}$, the ability to postselect provides significant computational advantage over vanilla models of quantum computation.

---
Tags: complexity-theory, terminology, probability-theory
---


# Question
Title: Shortest Minimax Path via Floyd-Warshall
I am trying to modify the Floyd-Warshall algorithm to find all-pairs minimax paths in a graph. (That is, the shortest length paths such that the maximum edge weight along a path is minimized.)

Floyd-Warshall algorithm contains the following loop to enhance the distance (`ds`) and the next vertex (`ns`) matrices at each iteration.

```
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ds[i][k] != inf && ds[k][j] != inf) {
                final int d = ds[i][k] + ds[k][j];
                if (d < ds[i][j]) {
                    ds[i][j] = d;
                    ns[i][j] = k;
                }
            }

```

I replaced `ds` with two new matrices: `ws` (weights) and `ls` (lengths). Further, updated the iteration step as follows:

```
for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (ws[i][k] != inf && ws[k][j] != inf) {
                final int w = Math.max(ws[i][k], ws[k][j]);
                final int l = ls[i][k] + ls[k][j];
                if (w < ws[i][j] || (w == ws[i][j] && l < ls[i][j])) {
                    ws[i][j] = w;
                    ls[i][j] = l;
                    ns[i][j] = k;
                }
            }

```

However, the modified algorithm finds paths with loops, that is, paths such as 1-**3-2-3**-4. While the maximum edge weight of the paths 1-3-2-3-4 and 1-3-4 are identical, the latter has a shorter path length and supposed to be returned by the enhanced Floyd-Warshall. Any ideas?

A working Java version of both algorithms and a test case which produces a path with loop can be found here.

**Edit:** Since no solutions were presented yet, I implemented my own shortest minimax path algorithm using incremental link removal method. Java sources to the solutions can be accessed from the above link.

# Answer
No need to introduce two arrays. In the original algorithm the distance equals the minimum (over all paths) of the **sum** of edges (in the path). The new variant defines a distance as the minimum (over all paths) of the **maximum** of edges (in the path).

Then one only needs to rethink the instruction

```
       final int d = ds[i][k] + ds[k][j];

```

In my understanding of Floyd-Warshall the array `ns` stores the highest number of the shortest path: it is updated to `k` each time a shorter path is found. To retrieve the path itself I would use a recursive procedure `short[i,j] = short[i,k] + short[k,j]` where `k=ns[i,j]` and provided `k<>i` and `k<>j`. (adapted to your programming syntax)

In that way no vertex will be repeated on a shortest path, but that part of Foyd-Warshall I always find hard to explain.
> 2 votes

# Answer
I deleted my previous answer because it was incorrect. Maybe the following is what is happening.

When the nested for loops reach:

```
i = 1, j = 4, k = 2

```

Let's suppose 1-2-4 is better than 1-4. Then we reach:

```
i = 1, j = 2, k = 3

```

Let's suppose 1-3-2 is better than 1-2. Then the current best path from 1 to 4 becomes 1-3-2-4. Then we reach:

```
i = 1, j = 4, k = 3

```

If 1-3-2-4 is better than 1-3-4 no change will occur.

Then we reach:

```
i = 2, j = 4, k = 3

```

If 2-3-4 is better than 2-4, the problem that you are seeing will occur. Because now the best path from 1 to 4 is 1-3-2-3-4.

---

EDIT: The above example has been shown to be impossible (in the comments). Leaving the answer rather than deleting it to prevent others from making the same mistake.
> 1 votes

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


# Question
Title: Count elements of a sorted matrix that fall into a given interval
I have a $n\times n$ matrix called $M$, and two integers $k\_\min$ and $k\_\max$. Each row and each column of M is sorted in the increasing order.

I would like to know if there is way I can count the number of its elements which are inside $\[k\_\min, k\_\max\]$, using a $O(n)$ algorithm.

# Answer
First, notice that you only need to know how to count the number of elements bigger than $k\_{min}$, because then, by a very simple transformation, you can count the number of element smaller than $k\_{max}$, and compute the desired result : since the set $A$ of element bigger than $k\_{min}$ is of the form $\[a;max\]$, and the set $B$ of element smaller than $k\_{max}$ is $\[min;b\]$, you have $|A \cap B| = |A| + |B| - n^2$

Now, find the last element smaller than $k\_{min}$ on the last row, at column $c\_0$. On this last row, exactly $n - c\_0$ elements are bigger than $k\_{min}$. On the row above, the last element smaller than $k\_{min}$ has to be right to $c\_0$, because otherwise, since $M$ is sorted on row and column, you would have a contradiction. Hence, in order to find the last element smaller than $k\_{min}$ on this row, you can start at column $c\_0$ and go right to find $c\_1$. Then again, the number of elements bigger than $k\_{min}$ on this row is $n - c\_1$.

Repeating this process, you then sum the number of elements on each row to compute the result, and you'll scan only at most $2n$ elements since the path followed by the algorithm is a path from the point $(0,n-1)$ to the point $(n-1,0)$, going only up and left, and these kind of path have length $2n$. This is hence indeed an $\mathcal{O}(n)$ algorithm.

EDIT: details added
> 1 votes

---
Tags: algorithms, search-algorithms, matrices, counting
---


# Question
Title: Pros and cons of representing strings as lists of characters
I am writing a compiler for my programming language (both almost complete), but they are stuck in the, I would call, "String vs List-of-Char dilemma". Maybe some more experienced compiler programmer could help.

It is a functional, strongly typed (with inference) and almost pure (immutable vars) language. As I could perceive, using a list of chars is better for simplicity/generality of the language. But it adds complexity to the runtime/stdlib, because the user may require sometimes to print a List-of-Char as a text and sometimes as a list.

Perhaps a built-in function just to print a List-of-Char as text would be a good compromise? I may be missing something here.

In the other hand, defining a "String" type different from "List", requires duplicity of all list functions like "head", "tail", "replace" etc. to preserve the soundness and simplicity of the type system. It also requires duplicity from the user when implementing similar methods.

Perhaps a built-in function just to convert a List-of-Char to String and vice-versa would be a good compromise? I may also be missing something here.

obs.: The code is in github if anyone has interest into delving in the problem.

# Answer
I'd say that the main reason for having a separate `String` representation is performance. For example, Haskell defines a string to be a list of characters `type String = [Char]`. But in many applications it turns out that this is too slow \- you have one constructor for every character, which requires a lot of work from the garbage collector. Then of course you have to duplicate most of the string functions, but the benefit is that you can implement them natively to be very fast.

So I'd suggest: If you are concerned about performance, define a native string type. If not, use list of characters instead.
> 1 votes

---
Tags: programming-languages, compilers, functional-programming
---


title: Is it possible to prove thread safety?

text:
# Question
Title: Is it possible to prove thread safety?
Given a program consisting of variables and instructions which modify these variables, and a synchronization primitive (a monitor, mutex, java's synchronized or C#'s lock), is it possible to prove that such a program is thread safe?

Is there even a formal model for describing things like thread safety or racing conditions?

# Answer
Proving that a program is "thread safe" is hard. It is possible, however, to concretely and formally define the term "data race." And it is possible to determine whether an execution trace of a specific run of a program does or does not have a data race in time proportional to the size of the trace. This type of analysis goes back at least to 1988: Barton P. Miller, Jong-Deok Choi, "A Mechanism for Efficient Debugging of Parallel Programs", *Conf. on Prog. Lang. Dsgn. and Impl.* (PLDI-1988):135-144.

Given a trace of an execution we first define a *happens-before partial-order* between events in the trace. Given two events $a$ and $b$ that occur on the same thread then $a \< b$ or $b \< a$. (The events on the same thread form a total order given by the sequential semantics of the programming language.) *Synchronization events* (these could be mutex acquires and releases, for example), give an additional inter-thread happens-before partial order. (If thread $S$ releases a mutex and then thread $T$ acquires that mutex we say that the release happens-before the acquire.)

Then given two *data accesses* (reads or writes to variables that are *not* synchronization variables) $a$ and $b$ that are to the same memory location, but by different threads and where either $a$ or $b$ is a write operation we say that there is a data-race between $a$ and $b$ if neither $a \< b$ nor $b \< a$.

The C++11 standard is a good example. (The relevant section is 1.10 in the draft specs that are available online.) C++11 distinguishes between synchronization objects (mutexes, and variables declared with an `atomic<>` type) and all other data. The C++11 spec says that the programmer can reason about the data accesses on a trace of a multithreaded program as if it were sequentially consistent if the data accesses are all data-race free.

The Helgrind tool (part of Valgrind) performs this kind of happens-before based data-raced detection as do several commercial tools (e.g., Intel Inspector XE.) The algorithms in modern tools are based on keeping vector clocks associated with every thread and synchronization object. I *think* this technique of using vector clocks for data-race detection was pioneered by Michiel Ronsse; Koen De Bosschere: "RecPlay: a fully integrated practical record/replay system", *ACM Trans. Comput. Syst.* 17(2):133-152, 1999.
> 12 votes

# Answer
From the pratical side, there is a verification system VCC which can be used to formally prove thread safety of C programs.

This is a citation from the web site:

> VCC supports concurrency -- you can use VCC to verify programs that use both coarse-grained and fine-grained concurrency. You can even use it to verify your concurrency control primitives. Verifying a function implicitly guarantees its thread safety in any concurrent environment that respects the contracts on its functions and data structures.
> 6 votes

# Answer
This is a very difficult area to ensure program correctness as far as ruling out race conditions, a sort of "achilles heel" of parallel processing. The best approach for program correctness is generally to avoid low-level primitives and work with higher-level design patterns (eg from libraries) that ensure thread synchronization. There is one model CSP, communicating sequential processes by Hoare, that has some proofs of correctness given that developers limit themselves to the "framework". It has some conceptual similarity & chronological origination/overlap to unix "pipes and filters" although havent (yet?) found a direct link between the two.

Two other frameworks that attempt to improve parallelization correctness through design patterns, and which have most of the standard/known algorithms/design patterns for this purpose:
> 1 votes

---
Tags: proof-techniques, correctness-proof, concurrency, threads
---


# Question
Title: What is the optimal solution to prove the reachbility of a node from the root?
I have a finite automaton with these properties:

* Contains cycles
* It's a directed graph
* All the states/nodes are initialy reachable from the initial state
* It has final states but I guess it isn't relevant for my issue
* It's a random generated automaton, and the generation isn't meant to satisfy properties like strongly connected components or connected components

Let's suppose I have to delete an edge.

I need to know if there's a way to prove that the reached state by this edge is still reachable from the initial state without using a classical search (DFS or BFS); obviously, if there is any.

# Answer
> 5 votes
This seems to be a difficult problem. For undirected graphs, this is known as "dynamic connectivity". You can see slides describing an $O(\log^2 n)$ algorithm, or the paper itself. For directed graphs, there is an algorithm no better than DFS described in this paper (the algorithm is better than DFS if you are making several connectivity queries each time). A paper by Pătraşcu gives evidence that polylogarithmic update time isn't possible for directed graphs.

---
Tags: graphs, finite-automata, graph-traversal
---


title: Modulo operation in monotone complexity

text:
# Question
Title: Modulo operation in monotone complexity
Given $x\in\Bbb N$, I would like to find $x\bmod N$, where $N$ is composite. For example $N=35$, $x=53$ and $x\bmod N=18$. Is this operation considered monotone in circuit/algebraic complexity language? I also want to have consider $x\_1+x\_2\bmod N = x\_1\bmod N+x\_2\bmod N$ and $x\_1x\_2\bmod N = (x\_1\bmod N)(x\_2\bmod N)$.

# Answer
In circuit complexity, a monotone operation is a function $f$ which is also *monotone*: if $x \leq y$ then $f(x) \leq f(y)$, where $x \leq y$ is a shorthand for $x\_i \leq y\_i$ for all $i$. There are many ways to define modulo $N$, but most of them are probably either uninteresting or not monotone. For example, consider the function which is true if the input is divisible by $N$. Then $f(0) = 1$ while $f(1) = 0$, and $0 \leq 1$ no matter what the actual length of the input is.
> 5 votes

---
Tags: complexity-theory, circuits
---


# Question
Title: Proving that a derived language is regular
Suppose I have a DFA recognizing a regular language $L$, how do I prove that $$\text{lefthalf}(L)= \\{ w\_1 \mid \exists w\_2 \in \Sigma^\* ,w\_1w\_2 \in L \land \\|w\_1\\| = \\|w\_2\\| \\}$$ is also a regular language?

# Answer
Hint: while reading $w\_1$, guess $w\_2$ and gather enough information so that in the end you can decide whether $w\_1 w\_2 \in L$.
> 1 votes

# Answer
Hint: while reading $w\_1$, guess $w\_2$ from the end, and see where you meet in the middle. Thus you can take as the set of states a subset of $Q^2$.
> 1 votes

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


# Question
Title: Compute 'permutation' like problem with modulo
Say, I have some permutation or combination formula like this,
$$\frac{n!}{(n-r)!r!},$$ and I want to $\bmod$ the result with some big prime ($10^9+7$ for example).

I already tried with modular operation and multiplicative inverse but failed (I don't quite understand them). Can someone give me some example in code so I can grasp the idea? (I prefer C).

# Answer
> 0 votes
The formula $\frac{n!}{(n-r)!r!}$ can also be written as $$\prod^n\_{i=r+1}{\frac{i}{n-i}}$$

You can rearrange the numerators so you never need to modulo divide (for each $i$ there is a $n-i'$ that divides it)

```
BigInt* res=new BigInt(1);
bool flags[r]=//all false
//flags is there to make sure we don't divide twice
for(int i=r+1;r<=n;i++)
{
    int num = i;
    for(int j=0;j<r;j++)
    {
        if(!flag[j] && num%j==0)
        {
            flag[j]=true;
            num/=j;
        }
    }
    res=multmod(res,num,prime);
}

```

# Answer
> 2 votes
The idea is that $(a + b) \pmod{p} = ((a \pmod{p}) + (b \pmod{p})) \pmod{p}$ and $(ab) \pmod{p} = ((a\pmod{p})(b\pmod{p})\pmod{p}$. In C code, computing $a + bc \pmod{p}$ is accomplished by

> t = (b\*c) % p; return (a + t) % p;

Regarding inverses, when $p$ is prime and $1 \leq a \leq p-1$ there is an element $1 \leq b \leq p-1$ satisfying $ab = 1 \pmod{p}$, and so $(x/a) \pmod{p} = (xb) \pmod{p}$. To find $b$ use the extended GCD algorithm to find $b,c$ such that $ab + cp = 1$.

---
Tags: arithmetic
---


# Question
Title: How to include calls to an $O(n)$ subroutine on finite-sized inputs in an analysis?
I am trying to calculate the runtime complexity of a function that does not have fixed size input, but uses several helper methods that do have fixed size input. I was unsure of how to include the helper methods in my calculations.

If I have an array with a fixed size of 32 indices, and I have a function that sums up the elements in that array, will that function be $O(n)$, or $O(1)$? I think that a function that sums up the elements of an array is $O(n)$ because each element of an $n$-length array must be visited, but if the function only sums up arrays of length 32, is it still $O(n)$?

# Answer
> 4 votes
There are some things to consider here.

*Conceptually*, an algorithm that iterates once over the input array has runtime $\Omega(n)$ (and $O(n)$ if it does constant-time work per element), $n$ being the size of the array.

*In application*, if the algorithm is only ever called with arrays of length $n \leq n\_0$ for some *constant* $n\_0$, you may treat the used time as $O(n) \subseteq O(n\_0) = O(1)$. Note that the $n$ here is probably not the one you use for your whole algorithm!

*In practice*, every algorithm runs constant time as real computers have finite memory. This is not an interesting model in the sense that it does not help to differentiate between algorithms that *do* behave very differently in practice, so we don't use it.

You may be interested in some of our reference questions on asymptotics, runtime analysis and the time used by arithmetic operations.

# Answer
> 2 votes
Any constant amount of work is O(1), whether it is summing up 32 values or brute forcing a 256 bit AES key.

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


# Question
Title: Find a simple path visiting all marked vertices
Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is *marked* if $v\in M$. The problem is to find a simple path in $G$ that visits the maximum possible number of marked vertices. The associated decision problem is: is there a simple path that visits every $v\in M$?

The problem is obviously more general than the problem of finding a Hamiltonian path in an arbitrary graph, so it is NP-hard.

I see no obvious strategy; one can't simply disregard the unmarked vertices, since they (and their incident edges) may be part of the optimal path. Indeed, omitting them may disconnect the graph completely.

My questions:

1. Does this problem have a well-known name?
2. Are there any good approximation algorithms, heuristics, or simple reductions to problems I might know more about?
3. Where can I find this problem discussed in the literature?

# Answer
> 3 votes
This problem is close to Steiner tree problem, just by two restriction:

1. Instead of tree we have path.
2. Is not necessary to have shortest path which contains required node.

There is a recent work1 on similar topic, the only difference with your problem statement is they are looking for shortest path which contains all required vertices. They name it Steiner Path problem.

1: Shanti Swaroop Moharana, Ankit Joshi, and Swapnil Vijay. Steiner path for trees. International Journal of Computer Applications, August 2013. Published by Foundation of Computer Science, New York, USA. (doi)

# Answer
> 2 votes
The nearest neighbor method is often used as a heuristic for different problems. Sometimes the method gives an effective approximation algorithm as well. You could employ it here as well. Here's a skeleton for a heuristic method that maintains a stack $S$ of vertices representing the resulting simple path. Let $F$ be a set containing forbidden vertices, that is, vertices that have already been used in our final path. $F$ should be a data structure supporting fast insertion and lookup, such as a hash table or even a bitvector.

1. Pick a start node $s\_0 \in M$ and let $S := \\{s\_0\\}$, and $F = \emptyset$.
2. Choose a successor $s\_i$ to $\text{top}(S)$, and try to find a path $s\_{i-1} \leadsto s\_i$ avoiding vertices in $F$. If a path is found, insert the vertices on the path $s\_{i-1} \leadsto s\_i$ to $F$.
3. Repeat step 2 until no successor can be found

For a more concrete implementation, consider the following:

1. Let $\text{Per}\_M(G)$ be the *marked periphery*, that is, the marked vertices with highest eccentricity. Pick the start node $s\_0$ such that $s\_0 \in \text{Per}\_M(G)$.
2. Using BFS, find the closest vertex to $\text{top}(S)$, where $S$ is the stack maintaining the path. Push the successor to the stack $S$. If a vertex $v$ is forbidden, i.e. $v \in F$, then the BFS won't visit it.
3. Repeat step 2 until no successor can be found.

I'll argue for the concrete implementation above:

1. You can think of picking the start vertex $s\_0$ from the "convex hull" of $M$. Roughly, the idea is that you only need to expand the path into one direction, thus maximizing the "freedom of movement".
2. BFS seems like the simplest idea; alternatively one could experiment with other search methods, such as bidirectional search or randomized DFS. A randomized DFS might be a bad choice when there's only a few elements in $F$, then it's possible it'll produce very long paths between two marked vertices. On the other hand, running a randomized DFS -based heuristic resembles the idea of random restarts, which has been *very* effective in say SAT/CSP solvers or local search methods.

If you are able to find any additional properties of your input graphs and/or $M$, it might very well help you in tuning this heuristic.

---
Tags: algorithms, graphs, reference-request, np-hard, hamiltonian-path
---


# Question
Title: Can the Lambda Calculus or Turing Machines model signals, callbacks, sleep/wait, or buses?
I have a deep appreciation for formalisms like the Turing Machine and the $\lambda$-Calculus, and enjoy studying them and learning more about how they relate to physical computers. I am now learning about writing GUI programs, and the graphical library (GTK) relies on things like signals and callbacks, which I have not seen modeled by either Turing Machines or the $\lambda$-Calculus; **can either the $\lambda$-Calculus or Turing Machines model things like signals, callbacks, sleeping/waiting, or buses?** If so, where can I find some good reference material to learn more? If not, why not? and are there any formalisms which are capable of expressing such things?

# Answer
Yes, there are natural extensions of the $\lambda$-calculus for handling I/O, parallelism, concurrency, exceptions, timeouts, etc. In general such things are viewed as *computational effects* and there is a rich theory of $\lambda$-calculus for computational effects. This is what Haskell monads are about -- Haskell *is* $\lambda$-calculus extended with features that you are asking about.

But let me point out that you mix a bunch of features together which are really of two different kinds:

1. *Interaction with external environment:* I/O, communication, timeouts, concurrency, etc.
2. *Programming models:* callbacks, semaphores, shared memory, parallelism, etc.

A classical Turing machine does not interact with an external environment, but it can be modified to do so. For instance, an oracle is essentially an input stream. The so-called "type 2 machines" are Turing machines with infinite input and output tapes which correspond to an input and an output channel, etc. I am sure someone invented "real-time Turing machines", but I think such endaveours miss the point of mathematical models of computation. A mathematical model is designed specifically to fit well a chosen set of features that we want to model. Turing machines were invented to explain what "possible to compute" means, not "how to compute". If you want to model I/O and such then there are better mathematical models to stick to ($\pi$-calculus was suggested by someone).

The second set of features you asked about is really a bunch of programming methods. As is well known, any Turing complete computational model can be used to simulate any other such model. For instance, a Turing machine can compute things in parallel through a technique known as *dovetailing*. I would not be surprised if dovetailing was invented several decades before the first parallel operating sytem came into existence. (In fact, it must be the case that dovetailing appreaded already in Turing's original 1936 paper, can someone confirm this?)

Callbacks are well known to functional programers, as these are just functions (but if you spend your life programming operating systems in C you will think they are special), while threads and coroutines are known as continuations. So some concepts that look fancy from one perspective are basic and straightforward from another. Another that comes to mind is the object-oriented idea of an "iterator" which gets vastly generalized in functional programming.
> 3 votes

# Answer
This question mixes two disparate areas of CS and attempts to use analogies that are relevant in one realm in the other realm (or in English vernacular "mixing apples and oranges"). On one end of the spectrum, Turing machines (TM) are an abstraction to understand computation. On the other end of the spectrum are practical "design patterns" and software architecture concepts such as "signals", "callback functions," "GUI" APIs etc.

A TM can implement any programming design pattern hence the term "Turing complete". However, this would require a TM compiler for a high-level language. Apparently almost nobody has written actual high-level language compilers for TMs. The theoretical crowd would regard it as a waste of time and the practical/pragmatic/applied crowd do also. So the theory guarantees it can be done, but not beyond that.

In at least one item you're missing the nearly obvious: in $\lambda$-calculus a lambda function can also function as a "callback".

Buses are more of an EE concept. Signals, sleep, and wait are modelled with *threads*, *processes*, or *parallelism*.
> -1 votes

---
Tags: turing-machines, computer-architecture, lambda-calculus, church-turing-thesis
---


# Question
Title: Enumerating all set covers when knowing one set at least
I have an index taking as keys values from the power set $P(S)$ of a set $S$, except for $\emptyset$ and $S$.

Then I have a query $Q=(s, k)$, where $s \in P(S) - \\{\emptyset \cup S\\}$ and $ 1 \< k \le |S|$.

The result of the query is the set of covers $R$ of $S$; $\forall r \in R, |r| \le k$.

So for instance, if $S = \\{a, b, c, d\\}$ and $Q=( \\{a,b\\}, 3 )$, $R$ should return all covers of $S$ formed by $\\{a, b\\}$ and $k = (3 - 1 = ) 2$ or less other subsets of $P(S) - \\{\emptyset \cup S\\}$, namely: $R = \\{$ $$ \\{a,b\\} , \\{c\\} , \\{d\\}$$ $$ \\{a,b\\} , \\{c, d\\} $$ $$ \\{a,b\\} , \\{a, c, d\\} $$ $$ \\{a,b\\} , \\{b, c, d\\} $$ $\\}$

I want to know if there is an efficient algorithm that can give me all of these combinations of covers.

In other words, I want to know if there is an efficient way to get all covers formed by at most $k$ elements, where I only know 1 element out of k.

# Answer
> 2 votes
The first step is to eliminate the known set $s$. The idea is to find all covers of $S \setminus s$ using at most $k-1$ sets, and then augment the solution by adding all subsets of $s$ to all sets in any given cover in all possible ways. Details omitted.

For the new problem, it is enough to find all covers of $S$ of size exactly $k$ which don't use $S$ or $\emptyset$. In fact, we can ignore these restrictions, and just drop the (relatively) few solutions using these sets. We will generate them ordered, incurring a factor of $k!$ in efficiency; I'm sure that can be avoided, but I'll leave the details for you. Consider the sets $S\_1,\ldots,S\_k$ in order, and suppose that they cover $a\_1,\ldots,a\_k$ "new" elements, that is $|S\_1| = a\_1$, $|S\_2 \setminus S\_1| = a\_2$ and so on. Then $a\_1 + \cdots + a\_k = |S|$, and we can enumerate over all such sequences (including zeroes). For each sequence, we can enumerate over the new elements themselves. Finally, we enumerate over all possible ways of adding "old" elements to sets, for example $S\_3$ could additionally to $a\_3$ new elements contain any subset of $S\_1 \cup S\_2$.

---
Tags: sets, set-cover
---


# Question
Title: Running time and stack depth of a lisp recurrence
Consider the following sequence $a\_n$:

\begin{align\*} a\_0 &= \alpha \\ a\_k &= \beta a\_{k-1} + \kappa \end{align\*}

Now consider the implementation of this sequence via lisp:

```
(defun an (k)
  (if (= k 0) alpha
    (+ (* beta (an (- k 1))) kappa)))

```

What is the running time to compute `(an k)` just as it is written? Also, what would be the maximum stack depth reached? My hypothesis would be that both the running time and stack depth are $O(k)$ because it takes $k$ recursive calls to get to the base case and there is one call per step and one stack push per step.\ .

Is this analysis corect?

# Answer
> 3 votes
The time and other resources (such as stack consumption) needed to run `an` with the argument $x \in \mathbb{N}^\*$ is the sum of:

* the resources needed to compute `(- k 1)` with `k` bound to $x$;
* the resources needed to compute `an` with the argument $x-1$;
* the resources needed to compute `(if (= k 0) alpha (+ (* beta`$y$\`) kappa))\` where $y$ is the value returned by the recursive call to `an`.

Let $T(x)$ be the running time of this computation. For $x \gt 0$, by the analysis above, $T(x) = T(x-1) + C$ for some constant $C$ (assuming that the arithmetic operations take constant time). A very simple induction shows that $T(x) = C \\, x + T(0)$, i.e. $T(x) = \Theta(x)$. The same goes for stack consumption.

There is more than one stack push per recursive call, (3 in a naive interpreted Lisp such as Emacs Lisp), but that doesn't affect the $O$ or $\Theta$ analysis. Other than this minor detail your analysis is correct.

Are you sure that you typed the right code? Emacs has a fairly low limit on stack usage but even it can sustain more recursive calls (up to 123 in Emacs 23 where `max-lisp-eval-depth` is 500).

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


title: Finding users covering a set x by x

text:
# Question
Title: Finding users covering a set x by x
I have a Set $S$ of objects, a set $U$ of users and a map $c: U \rightarrow S^{\prime}$, where
$S^{\prime} \subset S$ and $\emptyset \notin S^{\prime}$.

Every time I add a new entry to $c$, i.e. adding a new user $u$ with her associated subset of $S^{\prime}$, I need to get the list of other users with whom she covers $S$. However, I don't need to get all possible covers. I only need to get with how many $x$ other users she covers $S$, at most. In other words, I need to find who's complementing each other to cover $S$ 2 by 2, 3 by 3, ... , $x$ by $x$.

Is there an efficient method to do it? Or an efficient data structure? If no, is there any trick I can make to get good results? e.g. encode the elements of $S$ and do some sort of mathematical operations? Is any efficient solution possible at all?

Please let me know if I haven't explained my problem well enough.

# Answer
Since SET COVER can be reduced to this problem, you can't expect it to have an efficient solution. To reduce SET COVER to your problem, add a dummy user $u$ covering an auxiliary element, add the other users corresponding to the sets in the instance of SET COVER, determine the counts as in your problem, and then you can tell whether there is a set cover of given size.
> 3 votes

---
Tags: data-structures, efficiency, sets
---


# Question
Title: Sphere, triangle, and other primitive shape intersection
In a three dimensional Cartesian space, given a ray in its parametric form: $r(t) = \[1, 1, 1\] + t\[-1, -1, -1\]$ find the intersection points between the ray and the following primitives.

**a)** A sphere centered at the origin with a radius of $1$, and

**b)** a triangle with vertices $\\{\[1,0,0\]^T , \[0,1,0\]^T , \[0,0,1\]^T \\}$.

Represent the intersections in their Cartesian coordinates as well as the ray parameters. Write down the intermediate steps of your derivations clearly.

The next part asks me to choose another primitive 3D shape, decide on implicit or parametric surface functions, then make an equation for ray-surface intersection and derive the analytic solution.

I am a little confused on this assignment because I haven't had a physics class before and I don't understand the basics of 3D shapes' geometry or vectors. It's not entirely clear to me what I am supposed to find as an answer or in what form the answers should be written. I looked up the formulas for sphere and triangle intersection, but I can't find a similar example, so I don't know how to solve the problems.

# Answer
> 2 votes
A sphere centered at the origin with a radius $1$ consists of all points whose distance from the origin is at most $1$. The distance between two points $(x\_1,y\_1,z\_1),(x\_2,y\_2,z\_2)$ is $\sqrt{(x\_1-x\_2)^2+(y\_1-y\_2)^2+(z\_1-z\_2)^2}$. This gives you enough information to describe the sphere: $\\{ (x,y,z) : x^2+y^2+z^2 \leq 1 \\}$.

A triangle with vertices $p\_1,p\_2,p\_3$ is (by definition) the convex hull of $p\_1,p\_2,p\_3$, which is the set of all points $a\_1 p\_1 + a\_2 p\_2 + a\_3 p\_3$ for $a\_1,a\_2,a\_3 \geq 0$ satisfying $a\_1 + a\_2 + a\_3 \leq 1$. In our case, the triangle is defined by $\\{ (x,y,z) : x+y+z = 1, \\; x,y,z \geq 0 \\}$.

The intersection of a shape $S$ and the ray $r$ is just the set of points which belong to both $S$ and $r$. You can find these points by solving a system of equations: every point $(x,y,z)$ on the ray is of the form $x = 1-t,y = 1-t, z=1-t$ for some $t$. You can simplify this by making the substitution $s = 1-t$ to get $(s,s,s)$ instead of $(1-t,1-t,1-t)$. Now you can find the set of points in the intersection by solving a system of inequalities (I'll leave that to you). Having found the solution, the *ray parameter* is just the corresponding value of $t$, namely $t = 1-s$.

That should be enough to get you started.

---
Tags: computational-geometry, graphics
---


# Question
Title: Approximation algorithm for Feedback Arc Set
Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set.

I want to find out about is there some approximation algorithm around this problem.

# Answer
> 7 votes
Kann's online compendium of NPO problems is a good place to start. Feedback Arc Set (the "Directed part is redundant when you use "arc") is:

* APX-hard,
* Approximable within $\mathcal{O}(\log n \log \log n)$ (where $n$ is the number of vertices).

The problem is also fixed-parameter tractable1, so it *might* make more sense to solve the problem exactly, rather than use what looks like a bad approximation algorithm. (Or as Pål points out below, the running time is a bit... unpleasant, so maybe not.)

**Notes**

1 - JACM publication, Razgon & Sullivan's preprint, Chen, Liu and Lu's preprint \- the problem was independently solved and the results combined to one publication

---
Tags: algorithms, graphs, approximation
---


# Question
Title: Recover the path to a goal state in A* search algorithm
In the A\* search algorithm, we use a priority queue with heuristic function to find optimum result with minimum cost. But, how do we get the path after reaching goal?

# Answer
> 3 votes
Every node should have been given a pointer to the node it was reached from. Then you only need to follow and reverse a linked list.

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


title: Class of a Language

text:
# Question
Title: Class of a Language
What are the common ways to check if a given language is regular, context free, or context sensitive?

Any surveys or notes would also be helpful. There's no need to describe your suggestions. eg. it is sufficient to say a language is regular if it can be recognized by a DFA.

# Answer
**Regular languages**

Elementary methods

1. Finite automata (possibly nondeterministic, with empty transitions).
2. Regular expressions.
3. Right (or Left, but not both) linear equations, like $X = KX + L$ where $K$ and $L$ are regular.
4. Operations preserving regular languages (Boolean operations, product, star, shuffle, morphisms, inverses of morphisms, reversal, etc.)
5. Pumping lemmas (mostly used to prove non regularity).

Logical methods (often used in formal verification)

1. Monadic second order logic (Büchi's theorem).
2. Linear temporal logic (Kamp's theorem).
3. Rabin's tree theorem (Monadic second order logic with two successors). Very powerful.

Advanced methods

1. Well quasi orders. See W. Bucher, A. Ehrenfeucht, D. Haussler, On total regulators generated by derivation relations, *Theor. Comput. Sci.* **40** (1985) 131–148, and M. Kunz, Regular Solutions of Language Inequalities and Well Quasi-orders.
2. Algebraic methods based on Transductions.

**Context-free languages**

1. Pushdown automata.
2. Context-free grammars.
3. Operations preserving context-free languages (morphisms, inverses of morphisms, union, product, star, reversal, intersection with a regular language).
4. Pumping lemmas (mostly used to prove that a language is not context-free).
5. Rational transductions (they preserve context-free languages). Very powerful.

**Context-sensitive languages**

1. Context-sensitive grammar.
2. Operations preserving context-sensitive languages (Boolean operations, product, star, etc.).
> 5 votes

# Answer
For a language that is regular but not CF or CS,

1. construct a DFA/NFA that accepts it
2. convert it to a regular expression
3. show that it can be represented as an union, intersection or concatenation of two or more regular languages.

For Context Free language that is not CS,

1. construct push down automaton that accepts it.
2. show that *some other language* that contains (is a superset of) the language Context Free.

(there might be more ways though)
> 1 votes

---
Tags: formal-languages, formal-grammars
---


# Question
Title: What are some applications of computing the permanent of a matrix?
What are some applications that require computing the permanent of a matrix?

One application I know of is related to graph theory and matchings. Apparently, the number of perfect matchings of a bipartite graph is the permanent of its incidence matrix.

I am curious to know more applications of matrix permanent.

# Answer
Valiant proved that the permanent is $\\# P$-complete, which means that an efficient algorithm for computing the permanent can be used to solve any problem in $\\# P$, such as counting the number of satisfying assignment to a CNF, the number of Hamiltonian circuits, the number of $k$-colorings and so on. In particular, it could be used to solve NP-complete problems.
> 5 votes

---
Tags: linear-algebra, matrices
---


# Question
Title: Why is discrete mathematics required for data structures?
Data Structures is the second CS course taught at Columbia University and it lists Discrete Mathematics as a Co-Req.

I have a BSEE and have not taken any discrete mathematics and am having a hard time understanding why I need to take this to do things like create data structures?

Is this just so the university can cram useless info in my head and make more money, or is there a real relation to discrete math and data structures?

# Answer
A course on data structures will not be about "creating data structures". You can expect to analyse data structures, prove various properties of them, and create your own to solve some highly nontrivial problems.

Every single data structure you intend to build must be rigorously defined. Each method on a data structure must be proven rigorously to be correct. The time and space complexity of each method must be rigorously proven to follow a particular asymptotic bound. This all involves some nontrivial discrete mathematics. You'd also need to have a solid handle on probability when randomized inputs and data structures start being used, which you should expect for a decent course on data structures. If you're still unconvinced, look up Cuckoo Hashing and show that the insert time is, on average, $O(1)$, or take a look at a van Emde Boes tree and just attempt to figure out how the hell it works in the first place. You'll quickly realise that there's far more to it than just writing code to build obvious structures.

However, if you go into this course believing it to be beneath you, I can guarantee that you'll get nothing out of it. I would be very surprised indeed if an Ivy League university is "trying to cram useless info into your head and make more money".
> 9 votes

# Answer
Universities are not in the business of cramming useless info. If what they were teaching wasn't useful, they wouldn't bother. I recommend taking a more accepting attitude to life. If you go to college expecting to learn nothing, this is a self-fulfilling prophecy: you will learn nothing, so college will be wasted and you might as well start flipping burgers now.

---

Integers are a very simple form of data structures. Many of the algebraic structures that come up when studying functions that operate on integers also arise in the study of data structures.

Taking the size of a data structure maps the algebraic constructions on data structures to the corresponding algebraic constructions on integers. For example, the length of the concatenation of two lists is the sum of the length. This applies more generally to taking the site of a slice of a data structure, for example counting the substructures of a certain shape. For this reason, discrete mathematics often come up when studying the complexity of algorithms on data structures.

For examples of discrete mathematics at work, see

I recommend the book *Concrete Mathematics* by Ronald Graham, Donald Knuth, and Oren Patashnik.

Mathematics of almost any kind is also a way to gently introduce important concepts of rigorous proofs and abstraction. When reasoning about computer programs, you often need to keep track both of what is mathematically true, and of what the computer knows to be true, so to speak — the data that is available at each point of the program. It helps to first train your brain to cope with the mathematical truths, and gently graduate to following both the math and the program.
> 7 votes

# Answer
Discrete Mathematics is pretty important for almost anything.

Direct applications of Discrete Math in DS:

1. The Foundations of Logic and Proofs - Without being able to write good proofs, we can never claim a data structure/algorithm to be correct.
2. Graph Theory: without the fundamental knowledge of Graph Theory, tree data structures cannot be understood. Moreover Graphs are one of the most important components in DS. Almost all good DS use graphs in some way or the other.
3. Functions: we always write functions in a program, but what does that really mean?
4. Algorithms and recursion: Teaches asymptotic analysis : needed to analyze programs and run times.
5. Discrete Probability: if you look into more advanced Data Structures, many of them use randomized algorithms. Without probability, it would be difficult to argue about their correctness and efficiency.

On an informal note, Discrete Math is one of the best subjects in CS, without it, most other subjects would be really difficult to appreciate.
> 5 votes

---
Tags: data-structures, discrete-mathematics
---


# Question
Title: What does it mean to multiply or divide polynomials?
What does it mean to multiply or divide polynomials?

I have used them so many times, in error correcting codes, cryptography, etc. but it was never clear to me what would be a graphical representation/ interpretation.

I have always pondered what did it mean when someone multiplies a line with a curve to get another hyperplane of a bigger dimension.

I know the formulae and properties of polynomial multiplication & division, I am specifically looking for a graphical/algebraic interpretation of it.

# Answer
I am a bit uncertain by what you mean by graphical. One notion is to plot or graph a function, like $y=f(x)$, as you would in a highschool level algebra course. Another notion of "graphical" may include some similar to a Cayley graph. I just want to be upfront that the extent of my knowledge does not extend greatly into topology and some algebraic geometry. I will go off on the assumption that overly abstract "graphical" representations do not count.

**Graphical Plots:** In abstract algebra, the polynomials that work with the $y$ vs. $x$ type of graphing are in the ring of polynomials over $\mathbb{R}$, otherwise known as $\mathbb{R}\[x\]$. Evaluating any of these for an $x \in \mathbb{R}$ gives you a continuous function that you can plot. This works for $\mathbb{R}\[X\]$'s extensions, too ($\mathbb{C}\[X\]$).

**Graphs:** Cryptography and coding theory involve a massive number of structures, each of which can be represented as a graph. A notable set of examples are graphs depicting algebras over structures of finite size. Rings of polynomials are not one of them, since they contain, at minimum, a countable number of elements. Some intuition can be gathered from how these graphs change as you vary/limit the degree of your polynomial (more on this later). Though I imagine that this is not the kind of representation that you had hoped.

For other graphical/geometrical/topological aspects of crypto and coding theory, you might want to look into things like vector spaces, sphere packing, and lattices.

**Polynomials Over Finite Fields:**

Even so, it is important to realize that the inclusion of rings of polynomials in cryptography and coding theory are over *finite fields*. That is, they usually only consider $\mathbb{F}\_q\[X\]$, which is the finite field with $q$ elements. An easily recognized one would be $\mathbb{F}\_2^k = \\{0,1\\}^k$ (your typical algebra over binary strings).

A slight extension of this idea, rings of *multivariate* polynomials, are also useful. They are typically represented by $\mathbb{F}\[X\_1,X\_2,...\]$ where $\mathbb{F}$ is a field. An algebra of multivariate polynomial over $\mathbb{F}\_2$ is equivalent to a boolean algebra. A boolean formula, $\varphi(x\_1,x\_2,...,x\_n)$, would be equivalent to evaluating a degree $n$ multivariate polynomial over $\mathbb{F}\_2$. The intuition behind this is to see that $+$ and $\times$ act like XOR and AND logic gates on your binary inputs, $x\_1,x\_2,...,x\_n \in \\{0,1\\}$.

Beyond drawing something fundamentally equivalent to circuit diagrams, I do not see a fruitful way to represent this graphically. Though, this did not stop these guys from trying (I still think it is the same): http://polybori.sourceforge.net/zdd.html

There are obviously way more concepts from abstract algebra that are involved in these areas (e.g. $\mathbb{Z}\_p$, the ring integers mod $p$). Some may even have graphical representations that make the idea more intuitive. Though these fall outside the scope of the question, which is specific to algebras over polynomials.
> 3 votes

# Answer
You should not try to visualize this. Algebraic properties can span to multi dimensions.. try to ask what would an algebraic interpretation of it? Use linear algebra to reason about it.
> -1 votes

---
Tags: mathematical-analysis, intuition, polynomials
---


title: Converting NFA to DFA

text:
# Question
Title: Converting NFA to DFA
I've converted an NFA to a DFA. But even after checking over it a few times, it still doesn't feel right. I'm sure this is trivial, but I'd like someone to give me an idea where I went totally wrong on this.

NFA:

DFA:

# Answer
> 3 votes
Well, of course you have to merge the two empty states and there should be two transitions $(\\{q\_5\\}, a, \emptyset)$ and $(\\{q\_5\\}, b, \emptyset)$ if you want a complete automaton, but otherwise, it looks right and I agree with Subhayan: both automata accept $ab^+ \cup ab^+a$.

# Answer
> 2 votes
Based on your constructions, it seems like both machines accept the same language, i.e. $ab^+ \cup ab^+a$.

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


title: MapReduce Pseudocode

text:
# Question
Title: MapReduce Pseudocode
Consider the following pseudo code for mapreduce to find the frequency of words in a collection of documents:

```
map(String key, String value)
// key: document name
// value: document contents
 for each word w in value
   EmitIntermediate(w, "1")

reduce(String key, Iterator values):
// key: word
// values: a list of counts
  for each v in values:
    result += ParseInt(v);
    Emit(AsString(result));

```

So the map step gets each word as a key and output its frequency in a document. Does the reduce step sum the counts of each word?

# Answer
MapReduce groups everything by key, in this case the word. So the reducer gets the word, followed by a list of 1's. The length of that list is the number of times this word occurs in the text. The reducers sums up the ones to count the word.
> 2 votes

---
Tags: algorithms, parallel-computing
---


# Question
Title: Coordinated Attack Problem On The Arbitrary Graph
Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack.

It's well known that Two Generals' Problem represents a version of the Consensus Problem with unlimited number of the stopping failures, I think this is the only reason why Two Generals' Problem and Generals' Problem (with $n$ generals) don't have solution.

There is a proof of lacking solution for Two Generals' Problem (can be found in the textbook of Lynch).

The following is the exercise from the textbook of Lynch, that I have not solved so far.

Show that a solution to the (deterministic) coordinated attack problem (Generals' Problem) for any nontrivial connected graph implies a solution for the simple graph consisting of two processes connected by one edge. (Therefore, this problem is unsolvable in any nontrivial graph.)

Apparently, there is a reduction from an edge case to graph. But how to show it mathematically rigorous?

**Addendum:**

Can I say something like this? When we are given the primary problem of Two Generals and they initial values $a\_i$ (inclination whether to attack or not), we in arbitrarily add more dummy generals with the only requirement if $a\_1=a\_0=a$ for primary problem set all dummy's general input to $a$, otherwise set arbitrary input value $b \in \\{0,1\\}$. Find the solution on the graph, the solution on the graph is the solution for the primary problem.

# Answer
The easiest way to do the reduction is to decompose your graph into two pieces $G\_1,G\_2$ arbitrarily, let one general "play" $G\_1$, and the other one $G\_2$. Details left for you.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs, reductions, distributed-systems
---


# Question
Title: How does DNS work if there is no recursive querying?
Suppose I type in the website  `www.youtube.com.` The computer first asks a local domain name server (DNS) what the IP address of this website is. If it can't find it, it then asks the root server, etc. This is recursive querying.

How does DNS work if there is no recursive querying? Is the root server the only one that is used to find the IP address of the website?

# Answer
> 2 votes
If a resolver tries to send its recursive DNS queries to a server that refuses those queries, or the queries time out, then the resolver was originally supposed to try to do an iterative query itself: ask the roots, follow referrals until an error is detected or an answer is seen. However, nearly all resolvers are *stub resolvers* and simply choke at this point: they rely on being pointed to a short list of DNS servers where they can send recursive queries, and don't support doing iterative queries. Moreover, some networks only allow DNS queries to go to a small list of approved DNS servers providing recursive service. In this case iterative resolution wouldn't help.

(As Martin Berger points out, if the DNS server where a recursive query is sent happens to have the answer in its cache, and it is prepared to handle the recursive query, then it will supply the answer from its cache. Presumably your phrase "if there is no recursive querying" rules this out.)

The root servers answer recursive queries with referrals to other servers. This usually does not answer the query, and further queries are required.

If the DNS servers to which the resolver sends queries are not reachable, a DHCP lease refresh may provide a new list of servers and fix the problem.

A packet capture tool like Wireshark can show the DNS queries generated by your machine and the answers it receives.

---

For completeness, this is how the DNS works.

Usually the resolver is set up as a *stub resolver*, to send all DNS queries to a server. This is often done by including the IP address of this server in the DHCP negotiation when connecting to the network. The server's IP address can also be in `/etc/resolv.conf` or some equivalent configuration entry. When a DNS server sees a *recursive query*, and it is willing to provide an answer to that recursive query, then it usually does *iterative resolution*.

Iterative resolution works by sending the query to the servers for the root domain. This is a list of servers that changes infrequently; the latest one is available by FTP.

Queries to the servers for the root domain result in a *referral*, giving a list of name servers that are more likely to be able to answer. The resolver picks one of these, and sends the query there. This continues until it receives an answer, or something goes wrong: a loop occurs, a server responds with "NXDOMAIN" (no such entry exists in the DNS), or the query times out.

Name servers also keep a cache of previously seen name servers. When a DNS server is started, the first query works as above, but subsequent iterative queries will use the cache to short-circuit the process and will be sent directly to the best server, if one is known.

Instead of the term "recursive server", it is more correct to refer to a DNS server being prepared to answer recursive queries. Many DNS servers are prepared to answer recursive queries for some "trusted" clients but not for the Internet as a whole.

# Answer
> 1 votes
If there's no recursive query then the DNS query will succeed exactly when the local DNS server has an entry for the given fully qualified domain name (FQDN).

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


# Question
Title: Number of words of a given length in a regular language
Is there an algebraic characterization of the number of words of a given length in a regular language?

Wikipedia states a result somewhat imprecisely:

> For any regular language $L$ there exist constants $\lambda\_1,\\,\ldots,\\,\lambda\_k$ and polynomials $p\_1(x),\\,\ldots,\\,p\_k(x)$ such that for every $n$ the number $s\_L(n)$ of words of length $n$ in $L$ satisfies the equation $s\_L(n)=p\_1(n)\lambda\_1^n+\dotsb+p\_k(n)\lambda\_k^n$.

It's not stated what space the $\lambda$'s live in ($\mathbb{C}$, I presume) and whether the function is required to have nonnegative integer values over all of $\mathbb{N}$. I would like a precise statement, and a sketch or reference for the proof.

Bonus question: is the converse true, i.e. given a function of this form, is there always a regular language whose number of words per length is equal to this function?

<sub> This question generalizes Number of words in the regular language $(00)^\*$ </sub>

# Answer
Given a regular language $L$, consider some DFA accepting $L$, let $A$ be its transfer matrix ($A\_{ij}$ is the number of edges leading from state $i$ to state $j$), let $x$ be the characteristic vector of the initial state, and let $y$ be the characteristic vector of the accepting states. Then $$ s\_L(n) = x^T A^n y. $$

Jordan's theorem states that over the complex numbers, $A$ is similar to a matrix with blocks of one of the forms $$ \begin{pmatrix} \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 \\ 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 \\ 0 & \lambda & 1 \\ 0 & 0 & \lambda \end{pmatrix}, \begin{pmatrix} \lambda & 1 & 0 & 0 \\ 0 & \lambda & 1 & 0 \\ 0 & 0 & \lambda & 1 \\ 0 & 0 & 0 & \lambda \end{pmatrix}, \ldots $$ If $\lambda \neq 0$, then the $n$th powers of these blocks are $$ \begin{pmatrix} \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} \\ 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2} \lambda^{n-2} \\ 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & \lambda^n \end{pmatrix}, \begin{pmatrix} \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} & \binom{n}{3}\lambda^{n-3} \\ 0 & \lambda^n & n\lambda^{n-1} & \binom{n}{2}\lambda^{n-2} \\ 0 & 0 & \lambda^n & n\lambda^{n-1} \\ 0 & 0 & 0 & \lambda^n \end{pmatrix}, \ldots $$ Here's how we got to these formulas: write the block as $B = \lambda + N$. Successive powers of $N$ are successive secondary diagonals of the matrix. Using the binomial theorem (using the fact that $\lambda$ commutes with $N$), $$ B^n = (\lambda + n)^N = \lambda^n + n \lambda^{n-1} N + \binom{n}{2} \lambda^{n-2} N^2 + \cdots. $$ When $\lambda = 0$, the block is nilpotent, and we get the following matrices (the notation $\[n = k\]$ is $1$ if $n=k$ and $0$ otherwise): $$ \begin{pmatrix} \[n=0\] \end{pmatrix}, \begin{pmatrix} \[n=0\] & \[n=1\] \\ 0 & \[n=0\] \end{pmatrix}, \begin{pmatrix} \[n=0\] & \[n=1\] & \[n=2\] \\ 0 & \[n=0\] & \[n=1\] \\ 0 & 0 & \[n=0\] \end{pmatrix}, \begin{pmatrix} \[n=0\] & \[n=1\] & \[n=2\] & \[n=3\] \\ 0 & \[n=0\] & \[n=1\] & \[n=2\] \\ 0 & 0 & \[n=0\] & \[n=1\] \\ 0 & 0 & 0 & \[n=0\] \end{pmatrix} $$

Summarizing, every entry in $A^n$ is either of the form $\binom{n}{k} \lambda^{n-k}$ or of the form $\[n=k\]$, and we deduce that $$ s\_L(n) = \sum\_i p\_i(n) \lambda\_i^n + \sum\_j c\_j \[n=j\], $$ for some complex $\lambda\_i,c\_j$ and complex polynomials $p\_i$. In particular, *for large enough $n$*, $$ s\_L(n) = \sum\_i p\_i(n) \lambda\_i^n. $$ This is the precise statement of the result.

We can go on and obtain asymptotic information about $s\_L(n)$, but this is surprisingly non-trivial. If there is a unique $\lambda\_i$ of largest magnitude, say $\lambda\_1$, then $$ s\_L(n) = p\_1(n) \lambda\_1^n (1 + o(1)). $$ Things get more complicated when there are several $\lambda$s of largest magnitude. It so happens that their angle must be rational (i.e. up to magnitude, they are roots of unity). If the LCM of the denominators is $d$, then the asymptotics of $s\_L$ will very according to the remainder of $n$ modulo $d$. For some of these remainders, all $\lambda$s of largest magnitude cancel, and then the asymptotics "drops", and we have to iterate this procedure. The interested reader can check the details in Flajolet and Sedgewick's Analytic Combinatorics, Theorem V.3. They prove that for some $d$, integers $p\_0,\ldots,p\_{d-1}$ and reals $\lambda\_0,\ldots,\lambda\_{d-1}$, $$ s\_L(n) = n^{p\_{n\pmod{d}}} \lambda\_{n\pmod{d}}^n (1 + o(1)). $$
> 13 votes

# Answer
Let $L \subseteq \Sigma^\*$ a regular language and

$\qquad \displaystyle L(z) = \sum\limits\_{n \geq 0} |L\_n|z^n$

its generating function, where $L\_n = L \cap \Sigma^n$ and so $|L\_n|=s\_L(n)$.

It is known that $L(z)$ is *rational*, i.e.

$\qquad \displaystyle \frac{P(z)}{Q(z)}$

with $P,Q$ polynomials; this is easiest seen by translating a right-linear grammar for $L$ into a (linear!) equation system whose solution is $L(z)$.

The roots of $Q$ are essentially responsible for the $|L\_n|$, leading to the form stated on Wikipedia. This is immediately related with the method of characteristic polynomials for solving recurrences (via the recurrence which describes $(|L\_n|)\_{n \in \mathbb{N}}$) .
> 8 votes

---
Tags: formal-languages, regular-languages, word-combinatorics
---


# Question
Title: Solving a recurrence with the Master Theorem
Problem taken from here (page 3): http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-Handout.pdf

$T(n) = 3T(\frac{n}{2}) + \frac{3}{4}n + 1$

$f(n) = \frac{3}{4}n + 1$

It says we cannot use the traditional Master Theorem because $f(n)$ is not a polynomial. How is $\frac{3}{4}n + 1$ not a polynomial? It's a polynomial of degree one with a fractional coefficient.

# Answer
$\tfrac{3}{4}n+1$ is polynomial, as you say.

You seem to have misunderstood the handout. The example you quote is on slide 7 refers to case 3 of the Master Theorem, as presented on slide 3. The rest of slide 7 uses the Master Theorem to solve the recurrence you're asking about.

Slide 8 says, "Recall that we cannot use the Master Theorem when $f(n)$ \[...\] is not polynomial." It goes on to give a limited case where the Master Theorem can work with polylogarithmic $f(n)$, with an example on slide 9. This is completely separate from the example you're asking about on slide 7.
> 3 votes

---
Tags: asymptotics, master-theorem
---


title: String inputs in Machine Learning

text:
# Question
Title: String inputs in Machine Learning
Several popular machine learning algorithms such as Logistic regression or Neural networks require its inputs to be numeric.

What I'm interested in is how you make these algorithms work on non-numeric inputs (such as short strings).

As an example, let's say we're building an email classification system (spam/not spam), where one of the input features is the sender address.

To be able to use a learning algorithm, we need to represent the sender address as a number. One way is to simply number the senders 1..n. Our training set might then look like this:

This won't work, however, because algorithms such as Logistic regression or Neural networks learn patterns in the input data, while in our example, the output looks totally random to the algorithm. Indeed, once in a university class, we tried to train a Neural network on a dataset that looked like this and the network was unable to learn anything (the learning curve was flat).

Would you use Logistic regression or Neural networks in this example at all? If yes, in which way? If not, what would be a good way to classify emails based on sender address?

A perfect answer would discuss the email classification example as well as handling short strings in ML in general.

# Answer
One of the popular models is the Bag of Words model

Also, you can model the words as integers.. they have 'relative distance metrics' for that, and capture the very essence of the classification process. However a downside to that is the preprocessing step is expensive and also you need to have *some* domain knowledge.

A pretty famous distance metric is the Levenshtein distance which is based on the the number of single character edits. eg. that is, $d(walk,talk)\<d(walk,plod)$.

The metrics depend upon the context of the classification process.. for example your distance metric for classifying rhyming words will be different from those designed to classify synonyms/words conveying similar meanings.For a list of string metrics, take a look at this wikipedia article.

Also, you can take a look at this review paper.
> 4 votes

---
Tags: machine-learning, data-mining
---


# Question
Title: Perfectly Secure Ciphers known other than the OTP
By Information-Theoretic definitions, the One Time Pad (OTP) is called/was proved to be a Perfectly Secure Cipher. For the sake of completeness, we define

* OTP: An enc/dec function, $f:\mathcal{P} \times \mathcal{K} \rightarrow \mathcal{C}$
* Perfect Security: Given $m, m^\* \in \mathcal{M}$, $$P\big(m=m^\* \mid E\_\mathcal{K}(m) = c\big) = P(m=m^\*) $$

I ask, **Are there any more Perfectly Secure Ciphers known other than the OTP?**

# Answer
> 3 votes
I have looked into this question before and came up very short. From it, I believe that it may be the case that a cipher with this property is simply the Vernam Cipher (OTP) in disguise. It is still an interesting question as to how the use of additional resources or changes in protocol can potentially implement an equivalent to OTP with less effort. While it, itself, might not be exactly considered a cipher (or even a huge deviation from the one time pad), I found the following information theoretically cryptosystem to be incredibly interesting when I stumbled upon it a couple years back:

There is a more recent scheme (early 2000's), by Michael Rabin, called *hyper-encryption*, that can be shown to be information theoretically secure given the assumption that your adversary is space bounded (most others have assumptions on time bounds). As required by the scheme, there must be a very large, public, source of random bits.

The basic premise is for the sender and recipient to use the key to methodically pick out a one time pad from the random source of bits (using randomness extractors). In order to get this pad, the adversary would have to not only store the ciphertext, but also would need to store almost all of the random bits for use later. Their limited ability to store information would prevent them from doing this.

After the transmission is complete, access to the random bits is closed. The theory here is that, even if the key was revealed afterwards, that the adversary would not have enough information to establish anything about the plaintext. This remains true even if they had unlimited computational power, since no amount of post-analysis will get around the fact that the one time pad used depended on information that the adversary did not store. Since this security is not compromised even if the key is revealed after the transmission, the scheme is said to have *perfect forward secrecy*.

# Answer
> 0 votes
Any perfect cipher that you will ever encounter will be a one time pad or a variant of it.

---
Tags: cryptography
---


# Question
Title: Regex for all odd length string that contains exactly 2 0's with language {0,1}
I just started learning about formal lang and automata theory, and recently learned about regex, so I don't know any complicated symbols, so please stick with basic symbols.

The question is: Write a regex for the following language over {0,1} that is a set of all odd length strings that contain exactly two 0's.

I've got the first part finished (the odd part), it should be:

(0+1)\[(0+1)(0+1)\]\* ( + is the same as | (or) I believe, we learnt it as +)

However, when I think about having exactly two 0's it gets really messed up. I can only see that I can use * with 1 only since # of 0's are limited to 2. But if i do (11)\* , I can't get the permutation of 0's inside the 1's. (e.g. can't get 10101 with (11)\*).

What I know:

1. Only 1's can use *
2. In the regex only two 0's will be used
3. The way to make odd length is to add an odd length to an even length (even length needs to have empty string within it's set)
4. Odd length should not use * since 2 odd = even, so only even length can use *

For possible hints or answer, please use 0,1,+/|,\*,(,) only. Some other expressions I will not be able to understand.

# Answer
**Hint.** You did a good start, except maybe for (4). Note that $(11)^\*1$ is a regular expression for the set of words of odd length (on the alphabet $\\{1\\}$). Does that help you?

**Hint 2.** Consider a word in your language. You know you have exactly two $0$ and hence your word is of the form $1^i01^j01^k$ for some $i, j, k \geqslant 0$ such that $i + j + k$ is an odd number.

**Answer** $(11)^\*10(11)^\*10(11)^\*1 + (11)^\*10(11)^\*0(11)^\* + (11)^\*0(11)^\*10(11)^\* + (11)^\*0(11)^\*0(11)^\*1$
> 3 votes

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


# Question
Title: Can a method be written if the language is undecidable?
If a language is decidable, we can write a method that always halts and returns `true` for each string that is an element of the language and `false` otherwise.

If a language is undecidable, what does that mean? Does it mean:

a.) We cannot write a method; we cannot even conceive of a method.

b.) We can write a method that returns `true` for each string that is an element of the language; for strings that are not an element of the language, the method may return `false` or it may loop indefinitely.

c.) Other (what?)

# Answer
> 3 votes
(c) If a language is undecidable, we can write a method that returns `true` for some strings that are an element of the language and `false` for some strings that are not an element of the language. But such methods will always return an incorrect result or not terminate on at least some elements of in the language.

(b) describes a particular kind of undecidable languages: the languages that are semi-decidable. A semi-decidable language is one such that there is a way to enumerate all the elements of the language with a Turing machine (or other equivalent computation method). So the method can go on enumerating the language until it finds its argument; this method loops indefinitely if the argument isn't in the language.

An example of a semi-decidable language which isn't decidable is the set of provable statements in any reasonable foundation of mathematics. (Note that I wrote *provable*, not *true*. The opposite of a provable statement is a statement that admits no proof; this statement might not be *false*: there may be no way to prove its opposite either.) Given a potential proof, you can easily verify that it's correct, and thus provable statements can always be recognized as such. However, it can happen that neither the statement nor its negation is provable, in which case the search for a proof would loop forever.

An example of a language that isn't semi-decidable, and whose complement isn't semi-decidable either is the set of programs in a Turing-complete programming language that take an argument and return true for all arguments. This is the halting problem. For a language that isn't semi-decidable, (b) doesn't apply: it is impossible to write a function that returns `true` for all programs that terminate on all arguments and loops forever (or returns `false`) on all programs that loop on at least one input.

# Answer
> 1 votes
First of all, the word "conceive" is not clear. What's the different between writing and conceiving?

This question relates to the classes $RE$ and $coRE$. The class $RE$ is the set of languages that are recognizable by a TM. For such languages you can write a method that returns "true" on yes-instances, but might not halt on no-instances.

A language is in $coRE$ if its complement is in $RE$. Thus, for such languages you can write a method that returns "false" on no-instances, but may not halt on yes-instances.

There are languages that are not in $RE\cup coRE$ (e.g. $\\{\langle M\rangle\\}: L(M)=\Sigma^\*$). For such languages there is no method that always halts on no- or on yes-instances.

For further reading, try the computability part in Sipser's book.

This also relates to the Arithmetical hierarchy, but I think it is a bit out of scope for this question.

---
Tags: formal-grammars, undecidability, decision-problem, halting-problem, turing-completeness
---


# Question
Title: Good "serializer" ADT implementations for Synchronization
I am looking for a library which provides a "serializer" ADT for synchronization. (http://courses.cs.vt.edu/~cs5204/fall99/Summaries/Concurrency/serializers2.html)

Googling leads me to nowhere, unlike monitors,semaphores and other constructs, serializers are hardly discussed over the web in depth.

Any other pointers are welcome. :)

# Answer
This is the first I've ever heard of serializers, and I don't know of any libraries that implement them. From reading the course notes you pointed to and the paper by Hewitt and Atkinson referenced in the course notes, there seem to be two differences between serializers and monitors. The first is that serializers have a more "elegant" but less efficient way of waiting for invariants to become true, the second is that a notion of reader/writer locks seems to be built-in to serializers, but wasn't built in to the original notion of monitors.

The present-day conception of a monitor largely follows Lampson and Redell. "Experience with processes and monitors in Mesa," *Comm. ACM* 23(2):106-117, 1980. A monitor is an object (some private data with public methods that act as the interface to the abstract data type that the object implements) with a private mutex. Every public method starts by acquiring the mutex, and releases the mutex on exit. In Java this would be equivalent to marking every public method "synchronized". In C++11 this would be equivalent to declaring a private `mutex`, `m`, and having every public method begin with a declaration `std::unique_lock<std::mutex> lock(m)` (an RAII-style critical section).

While in monitors the notion of condition variables is explicit, in a serializer the condition variables are implicit in the `enqueue...until` statement. In a monitor you could implement something similar by associating a condition variable, `cv`, with each monitor. Then the `enqueue...until (<invariant-test>)` statement is written `cv.wait(m, []{return <invariant-test>;})` (that's C++ syntax for an anonymous function that returns true when the invariant is satisfied.) And you would then need to make sure that you `cv.notify_all()` at the end of each public procedure (in C++ I would do this by subclassing `unique_lock`, giving it a destructor that calls `cv.notify_all()` in addition to releasing the mutex.)

Finally, the serializer has this bizarre `join_crowd/leave_crowd` operation. It took me a while to figure this one out, but as best I've been able to determine it is a slightly weird way of implementing a reader-writer lock. In a serializer when you want a reader-lock you join the crowd and you release the reader-lock by leaving the crowd. (The "crowd" is the set of readers.) I think monitors make this operation much clearer. You can protect a monitor by a reader/writer mutex instead of a normal mutex. The rule for when you can acquire the read lock instead of the write lock is completely clear in monitors: a method that does any mutation of the data structure *must* be protected with a write-lock. Only if the method is completely immutable (`const` in C++ parlance) can you protect it with the read-lock. (Note though that C++11 didn't include reader/writer locks for very good reasons, so if you wanted to do this in C++ you'd need to use Boost's reader/writer locks.)

I can hazard some guesses about why serializers never got much notice. The first reason is that they were proposed by Carl Hewitt, who was the primary proponent of the Actor model of concurrent programming, and the Actor model uses different terminology than most people in the systems programming community are used to. The second reason is that the serializer `enqueue...until` statement requires you to add a `notify_all()` at the end of each public method. This in turn causes every thread waiting on an invariant to wake up and retest its invariant. Standard condition variables allow you to put `notify_one()` statements only where they are actually useful, which can lead to real performance benefits. Finally, it is not clear (to me) how to use the `join_crowd/leave_crowd` operation correctly, while it is at least easy to state what you must not do with a reader/writer lock (and even then reader/writer locks are one of the most common causes of bugs in multi threaded programs, so who knows what horrors would have been perpetrated in a world where serializers were standard practice.)
> 1 votes

---
Tags: operating-systems, synchronization
---


# Question
Title: FFT for expanded form of equation multiplication
I know how to use the FFT for multiplying two equations in $O(n\\,log\\,n)$ time, but is there a way to use FFT to compute the expanded equation before simplifying?

For example, if you are multiplying $A(x) = 1 + 2x + 6x^2$ and $B(x) = 4 + 5x + 3x^2$ such that you get $C(x) = A(x) \cdot B(x) = 4 + 5x + 3x^2 + 8x + 10x^2 + 6x^3 + 24x^2 + 30x^3 + 18x^4$ without going directly to the simplified answer?

Furthermore, is it possible to use FFT to do this expanded form multiplication in $O(n\\,log\\,n)$ time? If so, can you show me how to apply FFT to this scenario?

# Answer
> 3 votes
The trivial algorithm that multiplies every monomial in $A$ by every monomial in $B$ takes time $O(|A| \cdot |B|)$ (where $|A|$ is the number of monomials in $A$ or $\deg A + 1$, depending on the representation), which is the same order of magnitude as the size of the output, and so optimal. You only need FFT if you want to actually compute the product $AB$. In particular, there is *no way* to compute your function in time $O(n\log n)$, simply because the length of the output is $\Omega(n^2)$.

---
Tags: algorithms, algorithm-analysis, randomized-algorithms, fourier-transform
---


# Question
Title: Fundamental algorithms in formal language-automata theory
I'm willing to take a course in formal languages and automata theory , where we will explore side by side a functional programming language to implement the different algorithms we will encounter ,despite i am new to the language , i am assuming i've learned what's nessecary to move to the theoretical part , so i'm wondering what are the must-knows of FL & AT to a programmmer , that is what are the most fundamentals algorithms one necesserily have to know while studying formal languages and automata theory ?

# Answer
They're simple, but the various DFA $\leftrightarrow$ NFA $\leftrightarrow$ RE conversions are quite handy.

Also, being able to find the Parikh mapping of a semilinear language is quite useful for more advanced applications (especially when you get out of the regular languages), since it lets you answer a lot of decidable properties.
> 3 votes

# Answer
One of the important classes of languages you will be introduced to is *regular languages*. While studying them, you will learn the fundamental Myhill-Nerode theorem. This will teach you how to connect abstract mathematical concepts like equivalence classes, to specific algorithmic constructs. In terms of algorithms, this will relate to minimization algorithms for DFAs and understanding why similar algorithms don't exist for NFAs.
> 3 votes

---
Tags: algorithms, formal-languages, automata
---


# Question
Title: How does Grover's Quantum Sorting avoid reading the list?
It is well known now that Grover's quantum algorithm can **SORT** a database of $N$ entries in $O(\sqrt{N})$ time. How can an algorithm work without reading through the list of entries which needs $O(N)$ operation. How does Grover's algorithm avoid reading the list? Is there a special representation that can be used classically as well? I understand any such representation will not help the classical case. However I am curious to understand how Grover avoids reading the list?

# Answer
> 2 votes
The list (or database) is given implicitly by an "oracle" function, which is called $\Theta(\sqrt{N})$ times throughout the algorithm. Suppose for example you're looking for a divisor of some number $N$. Then the function could map $k \leq \sqrt{N}$ to *true* if $k$ is a non-trivial divisor of $N$, and *false* otherwise. Grover's algorithm will then find a non-trivial divisor of $N$ in time $\tilde{O}(\sqrt\[4\]{N})$ instead of the usual $\tilde{O}(\sqrt{N})$ (note that better algorithms are available in this case, even for a classical computer).

# Answer
> 1 votes
The premise of your question is faulty. Grover's algorithm can not sort a list in $O(\sqrt{N})$ time. Informally, Grover's algorithm is for *searching* a list, not *sorting* a list. Beware that "searching a list" is an informal description of what Grover's algorithm does, that should not be taken too seriously; what Grover's algorithm actually does is a little different, and you can find a good description on Wikipedia.

---
Tags: algorithms, sorting, quantum-computing
---


# Question
Title: Equivalence of Context-Free-Grammar and Context-Free-Grammar in CNF
* Given any *Context-Free-Grammar, $G$*, and another in *Chomsky Normal Form, $G\_c$*, how can we check if both $G$ and $G\_c$ generate the same language?

One of the trivial ways I know of is to convert $G$ into a CNF form. which motivates my second question,

* Can two different *Context-Free-Grammars* in CNF, $G\_c$ and $G\_c^\prime$, generate the same language? (I would appreciate a proof of it)

# Answer
Chomsky normal forms are not unique. If they were, we'd have an algorithm for deciding whether two CF grammars are equal. But equivalence of CF grammars is undecidable.
> 4 votes

# Answer
Compare $$\begin{align}S &\to AB \\ B &\to BB \\ A &\to a \\ B &\to b\end{align}$$ With $$\begin{align}S &\to AB \\ A &\to AB \\ A &\to a \\ B &\to b \end{align}$$ By what comparison would these grammars be equal?
> 1 votes

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


# Question
Title: Use pumping lemma to show L is not context free
Show that L = $\\{0^{2^n}| n\geq 0\\}$ is not a context free language.

Let string $s = 0^{2^p}$. Then we know we can write $s$ as $s = uvxyz$. I know that |vy| \> 0 and $|vxy| \leq p$.

So how do I show that $uv^2xy^2z$ is not in $L$.

# Answer
> 4 votes
$\\{ 0^{2^n} \mid n \ge 0 \\}$ is not context-free.

To show this, you can use any of the usual techniques to show that a language is not context-free, such as the pumping lemma for context-free languages.

The pumping lemma states that if $L$ is context-free, then there exists a pumping length $p$ such that for all $n \ge p$, there exist $u,v,x,y,z$ such that $0^{2^n} = uvxyz$ and $|vy| \ge 1$ and for all $k \ge 0$, $uv^kxy^kz \in L$. Take $n = p$: for all $k \ge 0$, $|uv^kxy^kz| = |uxz| + k |vy|$ must be a power of $2$. This is not possible for large $k$ since it would imply that the distance between consecutive powers of $2$ is never more than $|vy|.

You can also use Parikh's theorem, which states that the set of possible numbers of occurrences of a letter in a context-free language is semi-linear (i.e. it's of the form $\\{a p + b \mid a \in \mathbb{N}, b \in B\\} \cup C$ for some integer $p$ and some finite sets $B$ and $C$). For a language with a singleton alphabet, this means that the set of lengths of words in the language is semi-linear, which $\\{2^n \mid n\in\mathbb{N}\\}$ isn't.

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