# Question
Title: NFA or DFA for strings the contain exactly twice substring ab?
Given the language with alphabet: $\\{a, b, c\\}$ Draw an NFA or DFA for all the strings that have exactly twice substrings $ab$ and at least on $c$. I'm stuck with "exactly twice $ab$". Can somebody give me some ideas. It's also very good if you can suggest me the regular expression of this statement.

# Answer
> 3 votes
To answer these kind of questions try to break down your problem into smaller parts.

1. Can you find a NFA that accepts all words that contain the substring $ab$ exactly once?
2. If you have NFAs for the languages $L\_1$ and $L\_2$. Can you assemble the NFAs to a new NFA that accepts $L\_1\circ L\_2 =\\{uv\mid u\in L\_1 \text{ and } v\in L\_2\\}$?
3. Can you find a NFA that accepts all words that contain a $c$?
4. If you have NFAs for the languages $L\_1$ and $L\_2$. Can you assemble the NFAs to a new NFA that accepts $L\_1\cap L\_2 =\\{u \mid u\in L\_1 \text{ and } u\in L\_2\\}$?

Steps 2. and 4. are well known closure constructions for regular languages. Its not hard to come up with these constructions by yourself, but there are also part in most of the textbooks.

As pointed out in the comments, the concatenation is in your case more subtle, since the first string might end with $a$ and the second one might start with $b$. This can be fixed by setting $L\_1:=\\{w \mid \text{$w$ contains $ab$ once in the end}\\}$. In particular, you can always split the words of your language exactly after the first occurrence of $ab$.

# Answer
> 2 votes
Think of programming. What variables would you introduce if you had to write a program that tests a string letter-by-letter for two occurrences of $ab$ and at least once $c$?

* `ab-count`: with values 0,1,2, `too-much`
* `seen-c`: a boolean
* `last-letter-was-a`: a boolean. We want to count $ab$ occurrences, so a $b$ after $a$ is special, and we have to remember whether the previous letter read was $a$ to do this.

What do we do when we read $a$. We set `last-letter-was-a` to `true`.

What do we do when we read $b$. If `last-letter-was-a` is `false`, then we add one to `ab-count` (and all numbers more than 2 are stored as `too-much`). We set `last-letter-was-a` to `false`.

What do we do when we read $c$. We set `last-letter-was-a` to `false`. We set `seen-c` to `true`.

This is your finite state automaton. Each state represents a triple (`ab-count`, `seen-c`, `last-letter-was-a` ). Think about initial and final states.

# Answer
> 1 votes
$DFA\ \ M = (Q, \delta, q\_0,q\_a)$

where,

$Q = \\{q\_0,q\_1,q\_2,q\_3,q\_4,F=\\{q\_a,q\_4\\}\ \ \\}$ and

$ \delta : $

$(q\_0,a) \rightarrow q\_1 \\ (q\_0,b) \rightarrow q\_0 \\ (q\_0,c) \rightarrow q\_0 \\ (q\_1,a) \rightarrow q\_1 \\ (q\_1,b) \rightarrow q\_2 \\ (q\_1,c) \rightarrow q\_0 \\ (q\_2,a) \rightarrow q\_3 \\ (q\_2,b) \rightarrow q\_2 \\ (q\_2,c) \rightarrow q\_2 \\ (q\_3,a) \rightarrow q\_3 \\ (q\_3,b) \rightarrow q\_a \\ (q\_3,c) \rightarrow q\_2 \\ (q\_a,a) \rightarrow q\_4 \\ (q\_a,b) \rightarrow q\_a \\ (q\_a,c) \rightarrow q\_a \\ (q\_4,a) \rightarrow q\_4 \\ (q\_4,b) \rightarrow q\_5 \\ (q\_4,c) \rightarrow q\_a\\ (q\_5,a) \rightarrow q\_5 \\ (q\_5,b) \rightarrow q\_5 \\ (q\_5,c) \rightarrow q\_5 \\\$

Regular expression of string that does not have "ab" substring = $(a^\*c^+b^\*c^\*)^\* = S $ say then $SabSabS$ is the required RE

---
Tags: formal-languages, regular-languages, finite-automata, regular-expressions
---


# Question
Title: Solutions to synchronization problem need to be executed in critical section
I was reading about synchronization problems for cooperating processes and i learned that only hardware solutions like `test_and_wait()` and `compare_and_set()` are performed atomically at the hardware level and in all other software solutions like **mutex**, **semaphore** the code needs to be executed atomically and hence these have to be executed in the critical section themselves.

Does this mean that these software solutions have limited use when compared to the hardware solutions, though it seems that the former are used extensively?

# Answer
## Low-level atomicity primitives

At the level of the interface between hardware and software, atomicity is typically provided by an operation that combines a read and a write operation. Here are two common examples:

* test-and-set: read the old value of a memory location, and write a new value. This is an atomic operation: the read is always executed together with the subsequent write. If two threads execute test-and-set on the same location then one thread performs its read and its write first, then the other thread performs its read and its write.
* compare-and-swap: read the current value of a memory location, and if it has a given value, write a new value to it. This is an atomic operation: the read and comparison are always executed together with the subsequent write if any. If two threads execute compare-and-swap on the same location, then one thread performs its read and comparison and may or may not perform a write based on the current value, then the other thread compares the value that may or may not have changed and may or may not perform its write.

These primitives are awkward to use in applications for several reasons.

* They are not portable: different CPU types provide different atomic primitives. Unless you're writing software that's only meant for use on one particular CPU type, these primitives need to be wrapped inside a higher-level interface.
* They are not the whole story. This aspect is often neglected in introductory concurrency courses, which is understandable because it can get complicated. However, I've found that programmers who write low-level concurrent code are not always of it, which is more problematic. These primitives are not always sufficient to implement concurrency between threads that are running on different processors on a **multiprocessor** machine. (Here, by processor, I mean separate execution threads — you may prefer to use the word “core” instead.) If different processors share the same memory but have separate caches, then processor 1 may perform an atomic test-and-set to its cache while processor 2 performs an atomic test-and-set to its cache — and then there is no synchronization between the two processors. Depending on the processor type, the software may need to trigger a cache flush or invalidation.
* Continuing on “not the whole story”, even on a single processor, memory instructions may be executed out of order, to optimize the use of the memory bus. Consider for example a program uses one a CAS instruction to start a critical section that contains assignments. If the processor decides to reorder the assignments before the CAS instruction, the desired synchronization isn't happening! The software may need to generate appropriate memory barrier instructions.

Furthermore, these primitives only provide atomicity. Synchronization is more than that.

## Synchronization is atomicity plus events

Synchronization problems broadly fall into two categories:

* Avoid certain orders of operations which lead to wrong results — a common case is performing a series of elementary operations atomically.
* React to an event: do something when something else happens.

Consider what happens when two threads are competing for a critical section. One thread gets in, and the other thread doesn't thanks to the use of a low-level primitive. Now what? The other thread needs to wait until the resource is free.

At the hardware level, the most common mechanism to wait for an event is to wait for an interrupt. This is the pretty much universal mechanism to trigger software events from hardware events.

Interrupts are rarely applicable to synchronization between software. Waiting for a software event is usually provided by the operating system scheduler or the runtime library: the thread that needs to wait is suspended and placed on an event queue that is associated with the resource that the thread is waiting on. When the resource is released by its current holder, the thread at the front of the event queue is woken up. Depending on the design, it may either be assigned the resource at this point, or it may need to try acquiring the resource again.

There are cases when it is a good strategy to busy-wait: if the critical section is short and the threads are executing on separate processors in a multiprocessor machine, then it may be more efficient for the thread to try and try again until it managed to acquire the resource, than to go through the whole business with an event queue (which itself must be synchronized between the processors — see the part about cache coherency above). This is only a good strategy for short critical sections, otherwise the busy wait hogs the CPU (which can't be used to run other threads, and is consuming energy). This usually doesn't apply to single-processor systems as the active waiting is hogging the CPU, delaying the other thread from finishing, although it can sometimes be applicable to system with cooperative multiprocessing where the waiting thread yields execution to other threads.

A synchronization primitive such as a mutex is typically not executed as a critical section. For example, consider a typical spinlock operation (a mutex with busy-waiting) based on compare-and-swap in a coherent memory model (with no operation reordering and no need for cache operations). The mutex variable is initialized with the value 0. To acquire the mutex:

1. With CAS, set the mutex variable to 1 if it was equal to 0.
2. If CAS returns 0, the lock acquisition succeeded, so return to the caller.
3. Otherwise, the lock acquisition failed. Jump to step 1.

There is no need for the logic in steps 2 and 3 to be synchronized with what other threads are doing.
> 2 votes

# Answer
Atomicity and mutual exclusion are different concepts that are related in that either can be used to implement the other. The important property of mutexes and semaphores is not so much that they are atomic as they guarantee that only one process can get past a particular point at a time. Atomic read-modify-write hardware primitives like `test_and_set()` and `compare_and_swap()` can be used to implement mutual exclusion, but it is *not* true that atomic hardware operations are *required* to implement mutual exclusion - Lamport, Leslie; The Mutual Exclusion Problem Has Been Solved, *CACM* 34(1):110, 1991.

Mutual exclusion requires two different primitives. For example with a mutex you need both a `try_acquire()` operation and a `release()` operation. You would typically use something like a `test_and_set` instruction to implement `try_acquire()`, but a simple store operation is usually sufficient to implement `release()`. (And `test_and_set` is not *required* to implement `try_acquire()` as demonstrated by Lamport, it's just easier if you have such an atomic instruction.) Similarly, a semaphore has different `down()` and `up()` operations.

Further, most mutexes provide `acquire()` operations that do more than just `try_acquire()`, they also provide an efficient way of waiting for the mutex to become available if the `try_acquire()` should fail.

Conversely: a mutex can be used to implement a complex atomic operation. Suppose you want to implement an atomic increment operation on a machine that has a mutex (perhaps implemented without atomicity by using something like Lamport's Bakery Algorithm) but you don't have direct access to any atomic instructions. Something like the following will work:

```
mutex   m
integer i

atomic_increment():
  m.acquire()
  i = i+1      # only one process at a time can be at this code point
  m.release()

```

So neither mutual exclusion nor atomicity is more "fundamental" than the other, they are really two different things that can be used to implement each other.
> 5 votes

# Answer
Implementations of software primitives like mutexes and semaphores employ atomic hardware primitives such as `test_and_wait()` or `compare_and_set()`, and as a result they *behave* in an atomic fashion. Usually these software primitives are more powerful and easier to use than the hardware primitives, which is why you would rather use them. This is an example of the widespread idea of *reduction*: you can use any parallel primitive as long as it reduces to one of your hardware primitives, and so when hardware designers choose hardware primitives, they choose primitive which are powerful and versatile enough to enable implementation of as many other primitives as possible.
> 2 votes

---
Tags: operating-systems, concurrency, synchronization, mutual-exclusion
---


# Question
Title: Running time of this recursive relation: T(n) = (n/2)T(n/2) + O(n^2)
I encountered these few recursive relations:

`T(n) = (n/2)T(n/2) + O(n^2)`

`T(n) = T(n/2) + T(n/2-1) + ... + T(1) + O(n^2)`

I do notice that these recursions can be solved faster by DP. I'm just curious as to:

1. What's the big-O of the running time of these relations, if we follow the resursive formula
2. How do you analysis recursive relations like these.
3. Does the trailing term (in this case O(n^2)) matter?

Any help is much appreciated.

# Answer
> 1 votes
You can solve the first recurrence for powers of $2$. The recurrence (without the big O and with an arbitrary base case) reads $$ T(2^k) = 2^{k-1} T(2^{k-1}) + 4^k, \quad T(2^0) = 4^0. $$ Opening the recurrence, we get $$ T(2^k) = 4^k + 2^{k-1} \cdot 4^{k-1} + 2^{k-1+k-2} \cdot 4^{k-2} + \cdots + 2^{k-2+\cdots+1} 4^0. $$ Denote these by $T(2^k) = \alpha\_0 + \cdots + \alpha\_\ell$. We have $$ \frac{\alpha\_\ell}{\alpha\_{\ell-1}} = 2^{k-\ell-1}. $$ Therefore the largest term is $\alpha\_{k-1} = \alpha\_{k-2}$, and the rest of the terms decrease geometrically. This shows that $$ T(2^k) = \Theta(\alpha\_{k-1}) = \Theta(2^{k-1+\cdots+1} 4^1) = \Theta(2^{k(k-1)/2}). $$ As you can see, the term $O(n^2)$ in the recurrence isn't important, and you will get similar result for any term $O(n^c)$.

One could guess that the general solution to the first recurrence (with $\lfloor n/2 \rfloor$ replacing $n/2$) is $T(n) \Theta(2^{\log\_2 n(\log\_2 n - 1)/2})$, and one could further guess that the second recurrence has the same solution (though that's a wilder guess). I'm not sure these guesses are correct. At the very least, the first recurrence should have the solution $T(n) = 2^{\Theta(\log^2 n)}$.

---
Tags: algorithm-analysis, asymptotics
---


# Question
Title: Is it possible to modify dijkstra algorithm in order to get the longest path?
Is it possible to modify Dijkstra´s algorithm in order to get the longest path from $s$ to $t$ ?.

> My intuition says that I´ll need a different algorithm entirely. Finding the longest path is the same as finding the shortest path on a graph with negative weights. However, Dijkstra’s algorithm requires that the weights are positive, so it cannot be modified to calculate the longest path. A better algorithm to use could be: http://en.wikipedia.org/wiki/Longest\_path\_problem

Any idea of how to modify it?

# Answer
> 6 votes
Longest path is basically the **Hamiltonian Cycle problem** or the **Traveling Salesman Problem**, and it is NP-hard. So no, and if you find a way, then **${\rm \mathbf{P=NP}}$**.

The existence or non-existence of an algorithm to find the largest path, in polynomial time, is essentially part of the largest open problem in all of CS (and probably in math).

---

Incidentally, the Bellman–Ford algorithm can handle negative weights, so long as they don't form a cycle; in which case, if it encounters one (ie. if the cycle is reachable from the source), it would run forever, running 'round and 'round the cycle, accumulating a "shorter" and "shorter" path. Of course, it can detect this, and terminate, and is thus useful for detecting such cycles.

# Answer
> 0 votes
"sort-of-yes". there is a fairly natural modification to the algorithm to scan through the "frontier edges" by adding to the current spanning tree the *longest* 1st (by weight) instead of the *shortest* 1st. this will not result in the longest path, but it is a greedy-type algorithm that will result in a "longish" path. have not seen this variant/heuristic studied. it would be interesting to measure how close it comes to the optimum.

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


# Question
Title: Computing set difference between two large sets
I have two large sets of integers $A$ and $B$. Each set has about a million entries, and each entry is a positive integer that is at most 10 digits long.

What is the best algorithm to compute $A\setminus B$ and $B\setminus A$? In other words, how can I efficiently compute the list of entries of $A$ that are not in $B$ and vice versa? What would be the best data structure to represent these two sets, to make these operations efficient?

The best approach I can come up with is storing these two sets as sorted lists, and compare every element of $A$ against every element of $B$, in a linear fashion. Can we do better?

# Answer
> 9 votes
If you are willing to store the sets in a specialized data-structure, then you can possibly get some interesting complexities.

Let $I=\mathcal O\left(\min\left(|A|,|B|,|A\Delta B|\right)\right)$

Then you can do set operations $A\cup B, A\cap B,A\setminus B$ and $A\Delta B$, each in $\mathcal O\left(I\cdot\log\frac{|A|+|B|}{I}\right)$ expected time. So essentially, you get the minimum size of the two sets, or, the size of the symmetric difference, whichever is less. This is better than linear, if the symmetric difference is small; ie. if they have a large intersection. In fact, for the two set-difference operations you want, this is practically output-sensitive, since together they make up the size of the symmetric difference.

See Confluently Persistent Sets and Maps by Olle Liljenzin (2013) for more information.

# Answer
> 6 votes
A linear scan is the best that I know how to do, if the sets are represented as sorted linked lists. The running time is $O(|A| + |B|)$.

Note that you don't need to compare every element of $A$ against every element of $B$, pairwise. That would lead to a runtime of $O(|A| \times |B|)$, which is much worse. Instead, to compute the symmetric difference of these two sets, you can use a technique similar to the "merge" operation in mergesort, suitably modified to omit values that are common to both sets.

In more detail, you can build a recursive algorithm like the following to compute $A \setminus B$, assuming $A$ and $B$ are represented as linked lists with their values in sorted order:

```
difference(A, B):
    if len(B)=0:
        return A # return the leftover list
    if len(A)=0:
        return B # return the leftover list
    if A[0] < B[0]:
        return [A[0]] + difference(A[1:], B)
    elsif A[0] = B[0]:
        return difference(A[1:], B[1:])  # omit the common element
    else:
        return [B[0]] + difference(A, B[1:])

```

I've represented this in pseudo-Python. If you don't read Python, `A[0]` is the head of the linked list `A`, `A[1:]` is the rest of the list, and `+` represents concatenation of lists. For efficiency reasons, if you're working in Python, you probably wouldn't want to implement it exactly as above -- for instance, it might be better to use generators, to avoid building up many temporary lists -- but I wanted to show you the ideas in the simplest possible form. The purpose of this pseudo-code is just to illustrate the algorithm, not propose a concrete implementation.

I don't think it's possible to do any better, if your sets are represented as sorted lists and you want the output to be provided as a sorted list. You fundamentally have to look at every element of $A$ and $B$. Informal sketch of justification: If there is any element that you haven't looked at, you can't output it, so the only case where you can omit looking at an element is if you know it is present in both $A$ and $B$, but how could you know that it is present if you haven't looked at its value?

# Answer
> 2 votes
If A and B are of equal size, disjoint and interleaved (e.g. odd numbers in A and even numbers in B), then pairwise comparison of items in linear time is probably optimal.

If A and B contain blocks of items that are in exactly one of A or B, or in both of them, it is possible to compute set difference, union and intersection in sub linear time. As an example, if A and B differ in exactly one item, then the difference can be computed in O(log n).

http://arxiv.org/abs/1301.3388

# Answer
> 2 votes
one option is to use bitvectors to represent the sets (where the $n$th position represents presence or absence of an item) and set-type operations then reduce to binary operations which can be performed quickly (& on multiple bits in parallel) on digital computers. in this case $A-B$ = $a \wedge \overline b$ where $a,b$ are the bitvectors. the relative efficiency of this technique over other techniques also depends on the sparsity. for more dense sets it may be more efficient than other approaches. also of course the whole operation is embarrassingly parallel so set operations can be done in parallel.

---
Tags: algorithms, data-structures, sets
---


# Question
Title: Proving that the complexity class $P$ is closed under union
The following is my proof for $P$ being closed under union. I wish to know if my proof is correct in addition to what it means for the union of two problems.

Proof:

Let $p\_1, p\_2 \in P$ Then by definition of $P$ $p\_1$ is solvable in $O(n^k)$ for some $k\in\mathbb{N}$. Similarly $p\_2$ is solvable in $O(n^{k\_2}$) for some $k\_2\in\mathbb{N}$.

Then to solve $p\_1 \cup p\_2$, we solve $p\_1$ and $p\_2$. So the total running time would be $O(n^k) + O(n^{k\_2}) = O(n^{\max(k, k\_2)})$

1. What does it mean to solve $p\_1 \cup p\_2$?
2. Is my proof correct or on the right track?

# Answer
> 2 votes
Thinking about the problems as languages is probably the most illuminating way here. A language is a just a subset of all possible strings (over some alphabet $\Sigma$ which might as well be $\\{0,1\\}$). A language $\Pi \subseteq \Sigma^{\ast}$ is in $\mathsf{P}$ if there exists an algorithm that given a string $x \in \Sigma^{\ast}$ decides whether $x \in \Pi$ or $x \notin \Pi$ in time bounded by $\mathcal{O}(|x|^{c})$ for some constant $c$.

Relating that to the "problem" style definition, $x$ is the input (or rather the string that encodes the input) and $x \in \Pi$ is the same as saying $x$ is a Yes-instance of $\Pi$.

Taking the language definition though makes it easy to talk about the union, intersection etc., as languages/problems are just sets. So a string/instance being a member of the union of two languages/Yes-instance of the union of two problems, is exactly what it says on the tin: if the two problems are $p\_{1}$ and $p\_{2}$, then $x \in p\_{1}$ and $x \in p\_{2}$, or equivalently $x$ is a Yes-instance of $p\_{1}$ and $x$ is a Yes-instance of $p\_{2}$.

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


# Question
Title: Can be non-deterministic Turing machine simulated by $k$-tape deterministic TM where $k=\infty$ with preserving polynomially-same accepting times?
I know that for every $k$-tape DTM that runs in time $O(t(n))$, there exists a 1-tape DTM that runs in $O(t^2(n))$, no matter how large the $k$ (the $k$-part is a formulation from Wikipedia). But what if $k=\infty$?

If I understand it right, if $k=\infty$, then the alphabet of the $\infty$-tape DTM is infinite and therefore the transition function will be infinite as well. That is why it is not NTM by definition, however it should be much more powerful than a DTM (based on the argument that we can encode a countable infinitely long input into one symbol of countable infinitely large alphabet).

So, is it known if a NTM can be simulated by $\infty$-tape DTM (with preserving polynomially-same accepting times)?

# Answer
> 0 votes
This is a very nice question, which rises often in computability courses.

Once you allow infinitely many tapes, with infinitely many read/write heads, then the model becomes way too powerful. Formally, consider any language $L\subseteq \Sigma^\*$, here is an algorithm in your model that decides $L$ deterministically, and in linear time:

1. Scan the input tape, and write every letter on a new tape, move to state $q$.
2. We define the transition function as $\delta(q,w)=q\_{acc}$ if $w\in L$, and $\delta(q,w)=q\_{rej}$ otherwise.

By $\delta(q,w)$ we mean that the state is $q$, and the letters that are read by the infinite number of heads form the word $w$.

As you can see, we decide $L$ "by definition", and this definition is legitimate, since the transition table is infinite.

So your model can decide every language, which means that it provides no differentiation of language classes. So theoretically, we just showed that it's "not interesting".

---
Tags: turing-machines, time-complexity
---


title: Automatic speech correction

text:
# Question
Title: Automatic speech correction
When we are trying to learn a new language without any help from native speakers, the first thing we need is something/someone to correct our grammatical mistakes/improper word selection.

So is there any research done on building tools to help critique our spoken language? I often hear people saying that the more you try to speak, the better you get, so I'm wondering if automated tools could help provide feedback on our attempts at speaking in the new language.

# Answer
> 1 votes
This is part of the field called CALLS, or **computer-assisted language learning**.

It is an interesting subject, and the straight-forward approach would be to first do speech-recognition, then use NLP to find errors, and notify the user. Interestingly, I would think that any good speech recognition software would have to use NLP to disambiguate the speech (and possibly use NLP in additional ways).

So it is sort of a catch-22: in order to recognize the speech, some sort of assumption that the user is using (mostly) correct langauge is made, and therefore NLP can be used to assist the speech recognizer. But in this case, you have to be much much more sensitive to the user using incorrect language. So I think a different approach is necessary, where you integrate the "incorrectness detector" directly into the speech recognition somehow.

Or, perhaps use statistical/machine learning methods entirely (or a combination); ie. train the machine on data of non-native language speakers, and use a learning algorithm to teach the machine what mistakes commonly happen. I am unsure how feedback would work here though.

More info, on non-native pronunciation error detection and feedback:

Machine learning approaches:

This is all mostly about pronunciation. For grammar, you can tack on something to speech recognition, using NLP. The same caveats apply to grammatical error detection as to pronunciation; NLP would normally likely be used as part of speech recognition, so the error detector would likely have to be integrated directly into the speech recognition software.

More info on non-native grammatical error detection and feedback:

---
Tags: formal-grammars, natural-language-processing, software-engineering
---


title: Multicore SAT Solver

text:
# Question
Title: Multicore SAT Solver
I am trying to solve a 25k clauses 5k variables SAT problem. As it has been running for an hour (precosat) and I'd like to solve bigger ones afterwards, I'm looking for a multi-core SAT-Solver.

As there seem to be many SAT-Solvers, I'm quite lost.

Could anyone point me out the best one for my case?

I'd also be happy if someone could give me the approximate time (if possible).

# Answer
> 8 votes
Have a look at the results from this years SAT 2013 competition. Based on these results, definitely give Lingeling a try. Plingeling is the parallel variant of it.

If you don't need to prove unsatisfiability (perhaps you know the instance is satisfiable, and you just need to know an assignment making it SAT), you could try local search methods, too.

# Answer
> 4 votes
I'm not sure about the existence of practical multicore sat-solvers, but there are a few projects and papers:

I also found this interesting point: you can run a regular sat-solver multiple times with different seeds on the same problem in parallel, to get a multi-core effect.

**Edit:** Incorporating my comments on vzn's idea here:

> A similar alternate method is to simply choose a single variable, set its value to true, send that to one solver instance. Set its value to false, and send that to another solver instance. You can do this for $k$ variables, and run $2^k$ processes simultaniously. Choosing the variables to set could be a little tricky, ie. if they are directly dependent on each-other, then it is pointless to choose one and then another. A simplification step might be necessary to do successive/recursive choices.

---

> *(I'd also be happy if someone could give me the approximate time (if possible) to solve an X clauses Y variables SAT problem.)*

No one can give you an approximate time based on $m$ variables, $n$ clauses, because some SAT problems are extremely difficult (read: not gonna happen) to solve, even with a relatively small $m,n$; while other huge instances can be solved relatively quickly (and it is for these instances that sat solvers are useful).

# Answer
> 4 votes
There is actually a very simple way to turn any SAT solver into a parallel version because SAT is embarrassingly parallel in the following sense.

Choose some power of two to partition it by, $2^n$. Then choose $n$ variables and assign all possible boolean values. There will be $2^n$ resulting SAT formulas after the assignments. Solve each one separately (in parallel). There is an overall solution iff one of the separate solutions exists and the full solution is exactly the union of all the separate solutions.

---
Tags: algorithms, reference-request, parallel-computing, sat-solvers
---


# Question
Title: Algorithm to test whether a language is regular
Is there an algorithm/systematic procedure to test whether a language is regular?

In other words, given a language specified in algebraic form (think of something like $L=\\{a^n b^n : n \in \mathbb{N}\\}$), test whether the language is regular or not. Imagine we are writing a web service to help students with all their homeworks; the user specifies the language, and the web service responds with "regular", "not regular", or "I don't know". (We'd like the web service to answer "I don't know" as infrequently as possible.) Is there any good approach to automating this? Is this tractable? Is it decidable (i.e., is it possible to guarantee that we never need to answer "I don't know")? Are there reasonably efficient algorithms for solving this problem, and be able to provide an answer other than "don't know" for many/most languages that are likely to arise in practice?

The classic method for proving that a language is not regular is the pumping lemma. However, it looks like requires manual insight at some point (e.g., to choose the word to pump), so I'm not clear on whether this can be turned into something algorithmic.

A classic method for proving that a language is regular would be to use the Myhill–Nerode theorem to derive a finite-state automaton. This looks like a promising approach, but it does requires the ability to perform basic operations on languages in algebraic form. It's not clear to me whether there's a systematic way to symbolically perform all of the operations that may be needed, on languages in algebraic form.

---

To make this question well-posed, we need to decide how the user will specify the language. I'm open to suggestions, but I'm thinking something like this:

$$L = \\{E : S\\}$$

where $E$ is a word-expression and $S$ is a system of linear inequalities over the length-variables, with the following definitions:

* Each of $x,y,z,\dots$ is a word-expression. (These represent variables that can take on any word in $\Sigma^\*$.)
* Each of $x^r,y^r,z^r,\dots$ is a word-expression. (Here $x^r$ represents the reverse of the string $x$.)
* Each of $a,b,c,\dots$ is a word-expression. (Implicitly, $\Sigma=\\{a,b,c,\dots\\}$, so $a,b,c,\dots$ represent a single symbol in the underlying alphabet.)
* Each of $a^\eta,b^\eta,c^\eta,\dots$ is a word-expression, if $\eta$ is a length-variable.
* The concatenation of word-expressions is a word-expression.
* Each of $m,n,p,q,\dots$ is a length-variable. (These represent variables that can take on any natural number.)
* Each of $|x|,|y|,|z|,\dots$ is a length-variable. (These represent the length of a corresponding word.)

This seems broad enough to handle many of the cases we see in textbook exercises. Of course, you can substitute any other textual method of specifying a language in algebraic form, if you have a better suggestion.

# Answer
The answer is no. Deciding whether a given context-free grammar generates a regular language is an undecidable problem.

**Update**. I gave this negative answer to the general question

> Given a language specified in algebraic form, test whether the language is regular or not

since context-free languages are solutions of algebraic equations in languages: see Chapter II, Theorems 1.4 and 1.5 in the book of J. Berstel Transductions and Context-Free Languages.

However, the same question is decidable for deterministic context-free languages, a nontrivial result due to Stearns \[1\] and improved by Valiant \[2\]:
\[1\] R. E. Stearns, A Regularity Test for Pushdown Machines, *Information and Control* **11** 323-340 (1967). DOI:10.1016/S0019-9958(67)90591-8.
\[2\] L. G. Valiant. Regularity and related problems for deterministic pushdown automata *J. ACM* **22** (1975), pp. 1–10.

There is another positive result, closer to the specifications given in the second part of the question. Recall that the semilinear subsets of $\mathbb{N}^k$ are exactly the sets definable in Presburger arithmetic. There are also the rational subsets of $\mathbb{N}^k$. In particular, a subset of $\mathbb{N}^k$ defined by linear inequations is rational. Now, given a rational subset $R$ of $\mathbb{N}^k$, it is decidable whether the language $$ L(R) = \\{ u\_1^{n\_1} \dotsm u\_k^{n\_k} \mid (n\_1, ...,n\_k) \in R \\} $$ is regular. Indeed, it is known \[Ginsburg-Spanier\] that $L(R)$ is regular if and only if $R$ is a recognizable subset of $\mathbb{N}^k$ and it is decidable \[Ginsburg-Spanier\] whether a given rational subset of $\mathbb{N}^k$ is recognizable.

S. Ginsburg and E. H. Spanier., Semigroups, Presburger formulas, and languages, *Pacific J. Math.* **16** (1966), 285-296.

S. Ginsburg and E. H. Spanier. Bounded regular sets, *Proc. of the American Math. Soc.* **17**, 1043–1049 (1966).

This does not solve the second part of the question, which might be undecidable because of the word variables, but it gives a reasonable fragment to start with.
> 13 votes

---
Tags: algorithms, formal-languages, regular-languages, decision-problem
---


# Question
Title: Published or widely known failures of Page Rank algorithm
I use Google a lot for searching articles and publications. Occasionally, I find Google totally misses what I am looking for and I get completely unexpected results for some search queries.

> What are the published or widely known failures of PageRank algorithm?

EDIT: Changed the post to address comments.

# Answer
> 2 votes
yes this "problem" is quite well studied and google itself is researching ways to improve it. its called the word sense disambiguation problem and is under active/ongoing research, as its becoming a competitive feature between different search engines. quite simply, the same word has different meanings depending on context.

as for your more general question about "widely known failures of page rank", it is long known that it cannot necessarily distinguish spam web pages designed to fool it, and a related technique called a link farm with many external pages pointing to one site. in this sense google search is employing somewhat similar aims/techniques to spam-detecting algorithms employed largely/widely by mail providers.

google has proprietary/closely guarded techniques to detect/filter spam and these are a large part of the continually refining versions released. then advertisers attempt to respond with new techniques. this back-and-forth evolutionary dance/ "arms race" is also known as search engine optimization from the advertisers pov, but the term also somewhat applies to googles process of improvement! (SEO is a very large field with strong overlap with marketing and probably worldwide worth in the billions of dollars.)

somewhat similar, so-called "google bombing" where people create a mass movement to use words together to affect search engine results. it is somewhat subjective whether to call this a "failure" of the search engine or actually a "feature" (as from the perspective of those exploiting it, because in a way search engines actually by design measure meme prevalence in cyberspace!).

one method of dealing with word disambiguation is actually looking at trends in users personal search engine behaviors. in this way person A typing in a query will get different results than person B depending on their search histories.\[1\]

a related field called Latent semantic analysis helps with this somewhat by representing documents as sets-of-words with weights associated with each word, and the same word may have different weights in different documents or depending on document similarity measured by the vector cosine similarity technique.

an example paper from this field is K&M ref below. it actually uses & builds on results of *existing* google searches for word disambiguation.

yet another known issue is called "topic drift" where basically, if you search on two terms $x$ and $y$, if $y$ is more common it will tend to dominate and more results will be related to $y$ and "drown out" results with both $x$ and $y$. see eg \[2\]

---
Tags: algorithms, reference-request, searching
---


# Question
Title: What is growth of $\psi_q(m) = \min \{ p: m ∣ (q^p−1) \}$ for fixed $q$?
I have to estimate the computational complexity of some algorithm that does $\psi\_q(m)$ iterations. Assume that all inputs $m$ are coprime to $q$.

So I need to know what growth the $\psi(m)$ has.

# Answer
> 1 votes
Bottom line: I expect the answer to be $\psi\_q(m) = O(m)$, and this to be approximately tight: I don't expect you to be able to prove any significantly better upper bound on $\psi\_q(m)$.

Basically, $\psi\_q(m)$ is the order of $q$ in the multiplicative group of integers modulo $m$, i.e., in $(\mathbb{Z}/m\mathbb{Z})^\*$. In other words, it is the smallest natural number $p$ such that $q^p \equiv 1 \pmod m$.

The structure of $(\mathbb{Z}/m\mathbb{Z})^\*$ is well-characterized: for instance, when $m$ is prime, it is cyclic of order $m-1$. As a consequence, $\varphi(m-1)$ of the elements of this group will have order $m-1$ (where $\varphi(\cdot)$ denotes Euler's totient function). It's known that the typical value of Euler's totient function $\varphi(r)$ for a random value of $r$ near $N$ is about $6N/\pi^2$, i.e., $\Theta(N)$; so heuristically we can expect that the typical value of $\varphi(m-1)$ will be $\Theta(m)$ (roughly some constant times $m$). See, e.g., this summary on Wikipedia.

In particular, when $m$ is a random prime, close to half of all elements of $(\mathbb{Z}/m\mathbb{Z})^\*$ have order $m-1$: or to say this in a more careful way, we should expect that a constant fraction of group elements will have order $m-1$. This means that, for a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^\*$, the average order will be $\Theta(m)$. Of course, $q$ is not a random element -- it is a fixed number -- but as $m$ gets large, we can heuristically treat $q$ as a random element of $(\mathbb{Z}/m\mathbb{Z})^\*$.

Moreover, the primes are relatively dense among all the integers. (And even for a random composite, I think the same is still true: a randomly chosen element of $(\mathbb{Z}/m\mathbb{Z})^\*$ will have expected order $\Theta(m)$.)

Therefore, heuristically, I think $\psi\_q(m) = O(m)$ is about the best bound you're going to be able to get. This entire argument is based upon heuristics and is not something I can prove formally, but I think it should give an estimate that's good enough for evaluating the running time of your algorithm.

---
Tags: asymptotics, number-theory
---


# Question
Title: Counting occurrences of one vector inside another
I am asked to check if a vector contains another vector as a subvector. For example:

$$v\_1 = (4, \underline{3, 4}, 9, 10, 28, 5, 12, \underline{3, 4})$$ $$v\_2 = (3, 4)$$

The answer here will be two, since there are two instances of $v\_2$ in $v\_1$.

I know I have to use "if" but I dont really know how to write it down (I have tried).

# Answer
> 1 votes
This problem is known as **String Matching**. In case you don't care about performance Patricks answer is good. Notice that this linear search takes $O(n\cdot m)$ time, vor $n$ being the number of elements in $v\_1$ and $m$ being the number of elements in $v\_2$. This can be improved by more involved methods, i.e. the Knuth-Morris-Pratt algorithm needs only $O(n+m)$ time.

# Answer
> 0 votes
Pseudocode:

```
Count(source[1...n], target[1...m])
 1. count = 0
 2. for i = 1 to n - m + 1 do
 3.     match = true
 4.     for j = 1 to m do
 5.         if source[i + j - 1] != target[j] then match = false
 6.    if match then count++
 7. print "The count is " + count

```

The idea is straightforward: check all $n - m + 1$ subvectors of length $m$ and see if they match the target vector. This method will include overlapping occurrences of the target; another method can be used to avoid counting overlapping occurrences. The idea in that case is to step through the source, keeping track of how much of the target you've seen, resetting if you see the wrong thing, and incrementing the count if you see the whole thing.

---
Tags: algorithms, data-structures, lists
---


# Question
Title: Is SAT is in NL?( under certain conditions)
Consider a certicate for 3SAT that lists an assignment for each occurrence of a variable in the order of appearence,e.g. 100000 for ($x\bigvee$$y\bigvee$z)$\bigwedge$($\neg(w)$$\bigvee$$y\bigvee$z). This certicate is of polynomial length and can be read once to check the satisability of the given formula. Does this prove that SAT is in NL?

# Answer
The certificate could have linear size, and you need to remember it for the entire verification process. That is, you need to store in on the work tape and reference it as you read the clauses. You can't guess a satisfying assignment for each clause separately - under this model, every 3CNF is satisfiable. The oracle tape is consumed by each read - you can't go back and reread a previous symbol, which might be what's confusing you.
> 4 votes

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


# Question
Title: Rules regarding Chomsky Normal Form (CNF) grammars
I'm writing a context-free grammar that I hope will be in Chomsky Normal Form, and I have two questions:

1. Can I use a single variable (a non-terminal) on the left-hand side of multiple rules?
2. Can I use a single variable (a non-terminal) twice on the right-hand side of a single rule?

For instance, is the following grammar properly in Chomsky Normal Form? Is it OK that I have two rules with $S$ on the left-hand side? Is it OK that I have $X$ twice on the right-hand side of the second rule?

$$S\_0 \to S$$ $$S \to XX$$ $$S \to XZ$$ $$\vdots$$

# Answer
> 0 votes
The production

$$S\_0 \to S$$

is not in CNF. CNF requires that nonterminals produce either two nonterminals or one terminal. Since the above line shows a nonterminal producing a single nonterminal, it does not fit. The CFG in CNF would be just:

$$S\_0 \to XX$$ $$S\_0 \to XZ$$ $$\vdots$$

To answer your original questions, though, yes, you can do the above in CNF. There are no stipulations about how many times a nonterminal may appear on the left or whether it can be duplicated on the right.

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


# Question
Title: Complexity of the Kitten Adoption problem
This came up while I was trying to answer this question on Wiring Length Minimization. I was going to call this the "polygamous marriage" problem, but the internet, so kittens. Yay!

Suppose we have $M$ kittens that need to be adopted by $N$ people, $M \> N$. For each kitten, $i$ and each person $j$ there is a cost $c\_{ij}$. We would like to minimize the total cost of getting all the kittens adopted. There is also a set of constraints: each person $j$ is able to adopt no more than $u\_j$ kittens.

Without the constraints the problem is easy; each kitten $i$ goes with the person $j$ for which $c\_{ij}$ is minimal. With the constraints is there an efficient algorithm for this problem or is it NP-hard?

# Answer
> 5 votes
This is the min-cost max-flow problem.

Consider a graph $G=(A\cup B\cup \\{s,t\\},E)$, where $A$ is the set of kittens, $B$ is the set of people.

Let $C:E\to \mathbb{R}^+$ be the capacity of the edges, and $c:E\to \mathbb{R^+}$ be the cost of an edge. We make sure that

1. There is an edge between $a\_i,b\_j$, where $a\_i\in A$ and $b\_j\in B$, and $C(a\_i,b\_j)=1$, $c(a\_i,b\_j)=c\_{i,j}$.
2. There is an edge between $s$ and $a\_i\in A$, and $C(s,a\_i)=1$, $c(s,a\_i)=0$.
3. There is an edge between $b\_j\in B$ and $t$, and $C(b\_j,t)=u\_j$, $c(b\_j,t)=0$.

If the max flow is $M$, then we know there exist a solution. You can construct a min-cost solution from the min-cost max-flow.

# Answer
> 4 votes
This is the minimum weight perfect matching problem which is polynomial. Consider the complete bipartite graph $(L , R , E)$, in which $L$ contains a node $l\_i$ for each kitten $i$, $R$ consists of $u\_j$ copies of the node $r\_{j}$ for each person $j$, and edges $e\_{ij} \in E$ between $l\_i$ and each copy of $r\_{j}$, with weights $c\_{ij}$.

We know that $|L| \leq |R|$, otherwise not all kittens can be assigned to persons.

Since perfect matching must match all the nodes, we need to add dummy nodes to $L$ (to get $|L| = |R|$) and connect them with zero weight edges to all the nodes in $R$.

# Answer
> 2 votes
Possibly of interest is the observation that one can reduce Partition to a variant of this problem. Given is an instance of Partition with elements $\\{x\_1,\dots,x\_q\\}$ with $q$ even from which we have to choose a subset $S \subseteq \\{1,\dots,q\\}$ with $|S|=q/2$ such that $\sum\_{i\in S} x\_i = \sum\_{i\not\in S} x\_i = K$. (Note that the requirement to choose exactly half the elements is not the usual form but this form is still NP-hard.) Let each kitten be an element of the set; let there be two people; let the weights be $c\_{i1} = x\_i$ and $c\_{i2} = -x\_i$; let $u\_1 = u\_2 = q/2$. Then this instance of Kitten Adoption has a *maximum* of $0$ iff the instance of Partition has a solution.

If the costs in Kitten Adoption are meant to always be positive then one can just add a large enough constant $C$ to all weights to ensure they are the right sign, when the required threshold is $Cq$ instead of 0.

I am not sure what this says about the complexity of the original problem, but given the often-seen "one of minimize/maximize is NP-hard, the other is in P" setup for combinatorial optimization problems, I would start looking for an efficient algorithm.

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


# Question
Title: Making feature vector from Gabor filters for classification
My aim is to classify types of cars (Sedans,SUV,Hatchbacks) and earlier I was using corner features for classification but it didn't work out very well so now I am trying Gabor features.

code from here

Now the features are extracted and suppose when I give an image as input then for 5 scales and 8 orientations I get 2 \[1x40\] matrices.

**1. 40 columns of squared Energy.**

**2. 40 colums of mean Amplitude.**

Problem is I want to use these two matrices for classification and I have about 230 images of 3 classes (SUV,sedan,hatchback).

I do not know how to create a \[N x 230\] matrix which can be taken as vInputs by the neural netowrk in matlab.(where N be the total features of one image).

My question:

1. How to create a one dimensional image vector from the 2 \[1x40\] matrices for one image.(should I append the mean Amplitude to square energy matrix to get a \[1x80\] matrix or something else?)
2. Should I be using these gabor features for my purpose of classification in first place? if not then what?

Thanks in advance

# Answer
Well I figured it out myself that making a 1D vector of `[1x80]` by appending two `[1x40]` array worked and my classifier works very fine now
> 0 votes

---
Tags: machine-learning, neural-networks, image-processing, classification
---


# Question
Title: Computing parity function on n variables with O(n) gates
Sipser example 9.29

He says: "one way to do so (compute the parity function with O(n) gates. One way to do so is build a binary tree that computes the XOR function, where the XOR function is the same as parity on 2 variables, and then implement each XOR gate with two NOTs and two ANDs, and one OR. ... Let A be the language of strings that contain an odd number of 1's. Then A has circuit complexity O(n)."

I'm not seeing the steps that lead to saying that A has circuit complexity of O(n). Why can we say that if we implement a binary tree of XORs we can compute the parity with O(n) gates?

# Answer
> 2 votes
Because the parity is 1 if and only if the XOR of all the bits is 1. In other words, computing the parity is equivalent to computing the XOR of the bits. Sipser describes how to compute the XOR of the $n$ bits with $O(n)$ gates, which means that this same circuit computes the parity of those $n$ bits with $O(n)$ gates.

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


title: why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$

text:
# Question
Title: why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$
I have a question about simplifying O-notation. Specifically, why is $O(t(n)b^{t(n)}) = 2^{O(t(n))}$ where $t(n)$ is the running time of an algorithm?

# Answer
> 3 votes
I think I solved my problem...

Just as a simple numerical example: $2^6 = 2^{2\cdot3} = (2^{2})^3 = (2^{3})^2$

So if we have $2^{ct(n)}$ for some positive integer $c$ (as in the definition of O-notation) then we can choose a different base s.t. it is a power of two to the $t(n)$ power: \begin{equation} 2^{ct(n)} = (2^{c})^{t(n)} \end{equation}

Then clearly, we can choose $c$ s.t. $2^c \geq b$. Hence: \begin{equation} b^{t(n)} \leq (2^c)^{t(n)} \end{equation}

Now multiplying the LHS by $t(n)$ does not matter because I can still easily choose $c$ s.t: \begin{equation} t(n)b^{t(n)} \leq (2^c)^{t(n)} \end{equation}

Finally, we see that: \begin{equation} ct(n)b^{t(n)} \leq (2^c)^{t(n)} \end{equation}

because we can still easily choose $c$.

**EDIT** I made a mistake with thinking of the $t(n)$ term in front of $b^{t(n)}$ as a coefficient... Anyway, here is a revised solution:

\begin{align\*} O(t(n)b^{t(n)}) =& 2^{O(t(n))} \\ ct(n)b^{t(n)} =& 2^{ct(n)} \\ ct(n)b^{t(n)} =& (2^c)^{t(n)} \\ 2^{\log\_2(ct(n))}b^{t(n)} =& (2^c)^{t(n)} \end{align\*} Now suppose $b=2$. Then we can see that the term $2^{\log\_2(ct(n))}$ is dominated by $2^{t(n)}$. i.e. \begin{equation} 2^{\log\_2(ct(n))}2^{t(n)} = 2^{\log\_2(ct(n)) + t(n)} = 2^{O(t(n))} \end{equation} Now, for $b\geq 2$ we know the $2^{\log\_2(ct(n))}$ is negligible and so we are left with: \begin{align\*} O(b^{t(n)}) =& 2^{O(t(n))} \\ cb^{t(n)} =& (2^c)^{t(n)} \end{align\*} I think these two are asymptotically equivalent in the sense that $b$ is fixed and then we can choose some $c$ to satisfy the above, but what happens to the $\leq$ in the definition of $O$-notation?

1. Is this revision correct?
2. How does one read the original expression intuitively? Usually if you have $f(n) = O(g(n))$, we can think that $f$ is "bounded by" or "at most" $g$. In this scenario we have another $O$-notation as an exponent.

---
Tags: asymptotics
---


title: Task Dependency/Combinatorics

text:
# Question
Title: Task Dependency/Combinatorics
here is a competitive programming question:

You have a number of chores to do. You can only do one chore at a time and some of them depend on others. Suppose you have four tasks to complete. For convenience, we assume the tasks are numbered from 1 to 4. Suppose that task 4 depends on both task 2 and task 3, and task 2 depends on task 1. One possible sequence in which we can complete the given tasks is \[3,1,2,4\] - in this sequence, no task is attempted before any of the other tasks that it depends on. The sequence \[3,2,1,4\] would not be allowed because task 2 depends on task 1 but task 2 is scheduled before task 1. In this example, you can check that there exactly three possible sequences compatible with the dependencies: \[3,1,2,4\], \[1,2,3,4\] and \[1,3,2,4\]. In each of the cases below, you have N tasks numbered 1 to N with some dependencies between the tasks. You have to calculate the number of ways you can reorder all N tasks into a sequence that does not violate any dependencies.

\[Task, Dependency(s)\] : \[1, NA\], \[2,1\], \[3,2\], \[4,1\], \[5,4\], \[6, 3 and 5\], \[7,6\], \[8,7\], \[9,6\], \[10, 8 and 9\].

I inferred the following:

* Any sequence will always start with 1, since it has no dependencies.
* 6 will always be in the 6th position of any sequence.
* 10 will always be at the last position.

Then, by trial and error, and listing all possibilities for the two separate parts of the sequence (1 _ _ _ _ 6 and 6 _ _ _ 10), I got 6x3 = 18 possibilities. However, for a larger set of data, these deductions would not be easy. What is the way to calculate this logically and find the number of possibilities, and how can this be integrated into a program?

(I have tried to represent the question as clearly as possible, but you can visit this link to view the question (Q. No 4): http://www.iarcs.org.in/inoi/2013/zio2013/zio2013-qpaper.pdf)

I am a high school student preparing for a programming competition, and I haven't taken many courses on algorithm design, so this might be a trivial question - please excuse me!

# Answer
> 3 votes
It is a good question, certainly not trivial.

This problem is essentially counting the number of topological orderings. A topological ordering/sort is basically a valid ordering of completing the tasks in a dependency graph.

According to the link that @AndrásSalamon put into his comment, it is #P-complete: this means it is very hard to actually compute for a large number of tasks and dependencies.

They are expecting you to write a program that does it for just the small number of tasks that they give you. You probably need to do brute-force; i.e. try all possible orders, check if it is valid, and count them.

Alternatively, some smart variation of brute force, such as enumerating all possible topological orderings, and counting them.

Frequently this is the type of question asked by a competition:

* An impossibly difficult question if extended to large input size,
* Therefore, some sort of brute-force must be used,
* But a smart variation of brute-force,
* That can depend on the specific characteristics and limitations of the input they give you; if you don't take advantage of these limitations, and/or if you don't figure out the variation they want you to do, then your program will over-run its time limits.

You can also take a look at On Computing the Number of Topological Orderings of a Directed Acyclic Graph. To run this, you would make a dependency graph of the input tasks, then count the topological orderings using the algorithm(s) in this paper. I am not sure if this would finish in time on the input data you have; but one way to know would be to try it.

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


# Question
Title: How to avoid column wise access in matrix multiplication?
I know when we access elements in rows it will be much faster than if it is accessed column wise. In matrix multiplication one of the matrices must be accessed column wise. In GPUs with CUDA/OpenCL I could resolve this issue by explicitly copying both matrices row-wise into user-managed shared(cache)-memory (or local memory in OpenCL), and then can access data for matrix multiplication in anyway- no penalty for column access.

My question is how do I avoid such column access if I am implementing Matrix-multiplication on CPU, where I do not have any access to such shared memory as in GPU?

# Answer
I'm assuming you don't want to store a copy of the second matrix in column-wise order and then multiply. In this case maybe the best way is to take the most advantage of cache hierarchy in modern CPUs. There are many complexity results for such setting.

For matrix multiplication there is a cache-oblivious algorithm based on Strassen's algorithm. Here you can find it in details. Notice that their aim is to optimize I/O access, so it may not fully match your requirement.
> 2 votes

# Answer
You can transpose one matrix first. Then iterating that matrix can be done "in-sync" with the other.

Of course, now you have to find a nice transposition algorithm that avoids jumping around memory, but even if you don't, it will probably save you a lot of cache misses, when compared regular matrix multiplication.

For a square matrix, you can find a cache-aware matrix-transpose algorithm, as well as a cache-oblivious algorithm on the wikipedia page for **in-place matrix transposition**. See Cache-oblivious algorithms (Frigo et al., 1999) for more info.
> 0 votes

---
Tags: algorithms, cpu-cache, performance
---


# Question
Title: How do I find the shortest representation for a subset of a powerset?
I'm looking for an efficient algorithm for the following problem or a proof of NP-hardness.

Let $\Sigma$ be a set and $A\subseteq\mathcal{P}(\Sigma)$ a set of subsets of $\Sigma$. Find a sequence $w\in \Sigma^\*$ of least length such that for each $L\in A$, there is a $k\in\mathbb{N}$ such that $\\{ w\_{k+i} \mid 0\leq i \< |L| \\} = L$.

For example, for $A = \\{\\{a,b\\},\\{a,c\\}\\}$, the word $w = bac$ is a solution to the problem, since for $\\{a,b\\}$ there's $k=0$, for $\\{a,c\\}$ there's $k=1$.

As for my motivation, I'm trying to represent the set of edges of a finite automaton, where each edge can be labeled by a set of letters from the input alphabet. I'd like to store a single string and then keep a pair of pointers to that string in each edge. My goal is to minimize the length of that string.

# Answer
> 4 votes
I believe I found a reduction from Hamiltonian path, thus proving the problem NP-hard.

Call the word $w\in\Sigma^\*$ a witness for $A$, if it satisfies the condition from the question (for each $L\in A$, there's $m\geq 1$ such that $\\{w\_{m+i}\mid 0\leq i\<|L|\\} = L$).

Consider the decision version of the original problem, i.e. decide whether for some $A$ and $k\geq 0$, there's a witness for $A$ of length at most $k$. This problem can be solved using the original problem as an oracle in polynomial time (find the shortest witness, then compare its length to $k$).

Now for the core of the reduction. Let $G=(V,E)$ be a simple, undirected, connected graph. For each $v\in V$, let $L\_v=\\{v\\}\cup\\{e\in E\mid v\in e\\}$ be the set containing the vertex $v$ and all of its adjacent edges. Set $\Sigma=E$ and $A=\\{L\_v\mid v\in V\\}$. Then $G$ has a Hamiltonian path if and only if there is a witness for $A$ of length at most $2|E|+1$.

Proof. Let $v\_1e\_1v\_2\ldots e\_{n-1}v\_n$ be a Hamiltonian path in $G$ and $H=\\{e\_1, e\_2, \ldots, e\_{n-1}\\}$ the set of all edges on the path. For each vertex $v$, define the set $U\_v=L\_v\setminus H$. Choose an arbitrary ordering $\alpha\_v$ for each $U\_v$. The word $w=\alpha\_{v\_1}e\_1\alpha\_{v\_2}e\_2\ldots e\_{n-1}\alpha\_{v\_n}$ is a witness for $A$, since $L\_{v\_1}$ is represented by the substring $\alpha\_1e\_1$, $L\_{v\_n}$ by $e\_{n-1}\alpha\_n$, and for each $v\_i$, $i\notin\\{1, n\\}$, $L\_{v\_i}$ is represented by $e\_{i-1}u\_{v\_i}e\_i$. Furthermore, each edge in $E$ occurs twice in $w$ with the exception of $|V|-1$ edges in $H$, which occur once, and each vertex in $V$ occurs once, giving $|w|=2|E|+1$.

For the other direction, let $w$ be an arbitrary witness for $A$ of length at most $2|E|+1$. Clearly, each $e\in E$ and $v\in V$ occurs in $w$ at least once. Without loss of generality, assume that each $e\in E$ occurs in $w$ at most twice and each $v\in V$ occurs exactly once; otherwise a shorter witness can be found by removing elements from $w$. Let $H\subseteq E$ be the set of all edges occurring in $w$ exactly once. Given the assumptions above, it holds that $|w|=2|E|-|H|+|V|$.

Consider a contiguous substring of $w$ of the form $ue\_1e\_2\ldots e\_kv$, where $u,v\in V$, $e\_i\in E$. We say that $u,v$ are adjacent. Notice that if $e\_i\in H$, then $e\_i=\\{u,v\\}$, because $e\_i$ occurs only once, yet it is adjacent to two vertices in $G$. Therefore, at most one of $e\_i$ can be in $H$. Similarly, no edge in $H$ can occur in $w$ before the first vertex or after the last vertex.

Now, there are $|V|$ vertices, therefore $|H|\leq |V|-1$. From there, it follows that $|w|\geq 2|E|+1$. Since we assume $|w|\leq 2|E|+1$, we get equality. From there we get $|H|=|V|-1$. By pigeonhole principle, there is an edge from $H$ between each pair of vertices adjacent in $w$. Denote $h\_1h\_2\ldots h\_{n-1}$ all elements from $H$ in the order they appear in $w$. It follows that $v\_1h\_1v\_2h\_2\ldots h\_{n-1}v\_n$ is a Hamiltonian path in $G$. $\square$

Since the problem of deciding the existence of Hamiltonian path is NP-hard and the above reduction is polynomial, the original problem is NP-hard too.

---
Tags: algorithms, formal-languages, encoding-scheme
---


title: Problems in NP but not in #P

text:
# Question
Title: Problems in NP but not in #P
Are there problems that are in NP class but not in #P class? According to Wiki definition:

> More formally, #P is the class of function problems of the form "compute ƒ(x)," where ƒ is the number of accepting paths of a nondeterministic Turing machine running in polynomial time"

So I am thinking, if you already have a poly nondeterministic Turing machine that can accept correct paths, then you can just use this to count in poly time. Is there something I am missing here?

# Answer
NP is a class of decision problems, while #P is a class of functions. If a function $f$ is in #P then the decision problem $L = \\{ x : f(x) \> 0 \\}$ is in NP.

As far as I know, it is not expected that for every $f$ in #P, the decision problem $L = \\{ (x,y) : f(x) = y \\}$ is in NP. In particular, it is not clear how you would verify non-deterministically that a given non-deterministic machine has exactly $y$ (or even at most $y$ or at least $y$) accepting paths (where $y$ is encoded in binary; if it's encoded in unary, then the task is perfectly possible). Do you have any suggestions?
> 7 votes

# Answer
The simple answer to your question is "Yes, all of them!" No problem in NP is in #P because NP is a class of decision problems (problems where the answer is yes or no: for example, is this graph 3-colourable?), but #P is a class of function problems (problems where the answer is a non-negative integer: for example, how many 3-colourings does this graph have?).

You seem to be confused about the basic definitions. A decision problem is in NP if there is a nondeterministic, polynomial-time Turing machine that has at least one accepting path whenever the answer is "yes" and no accepting paths whenever the answer is "no". A function problem $f$ is in #P exactly when there is a nondeterministic, polynomial-time Turing machine that has exactly $f(x)$ accepting paths for every input $x$. So, NP is about the existence of accepting paths, while #P is about the number of them.

I'm not sure what you mean by "if you already have a \[...\] Turing machine that can accept correct paths". Turing machines don't accept paths — they accept (or reject) their input. An accepting path of a Turing machine is a computation that it makes, that ends in an accepting state.

Here are two facts that you might have been thinking about when you asked your question.

1. For every function $f$ in #P, the decision problem "Is $f(x)\>0$?" is in NP. This is because the Turing machine that computes $f$ (in the sense that it has $f(x)$ accepting paths for every input $x$) has at least one accepting path (i.e., accepts its input in the sense of NP) exactly when $f(x)\>0$.
2. Every decision problem in NP is contained in P<sup>#P</sup>. That is, if you have an oracle for any #P-complete problem, you can use it to answer any NP decision problem. This is because every problem in NP is accepted by some Turing machine $M$. The machine $M$ computes some function $f$, where $f(x)$ is the number of accepting paths that $M$ has for input $x$. So, to find out if $M$ has at least one accepting path, you just use the oracle to compute $f(x)$ and then check if that value is greater than zero.
> 2 votes

---
Tags: complexity-theory, complexity-classes, np
---


# Question
Title: Uniformly random efficient sampling of shortest s-t paths, with optimal random bits
Motivated by Efficiently sampling shortest s-t paths uniformly and independently at random,

The answers give methods of randomly sampling shortest $s\text{-}t$ paths. However, they use a lot of seemingly unnecessary random bits.

My question is:

> Can the solution be improved to use a single random number in interval $\[0,w(t))$, where $w(t)$ is the total number of shortest paths from $s\text{-}t$.
>
> Alternatively, can the solution be improved to use $\left\lceil \log\_2 w(t)\right\rceil $ random bits?

# Answer
> 4 votes
D. W. computes for each node $v \in S$ the number of paths $n(v)$ from $v$ to $t$. Using this information, it is easy to decode a number in the range $\[0,n(s))$ to a unique path from $s$ to $t$ in $S$ (and so in the original graph). More generally, at each node $v$ we will come up with a procedure to map $\[0,n(v))$ to a unique path from $v$ to $t$. Let the children of $v$ be $v\_1,\ldots,v\_k$. The idea is to write $$ \[0,n(v)) = \[0,n(v\_1)) \cup \[n(v\_1),n(v\_1)+n(v\_2)) \cup \cdots \[n(v\_1)+\cdots + n(v\_{k-1}), n(v\_1)+\cdots+n(v\_k)), $$ and use the $i$th component to encode paths going through $v\_i$. By subtracting $n(v\_1) + \cdots + n(v\_{i-1})$, we then reduce the problem to decoding a number in $\[0,n(v\_i))$ to a unique path from $v\_i$ to $t$. Pseudocode left to the reader.

# Answer
> 2 votes
The answer is yes, if you'll grant me some reasonable assumptions.

Generate a random seed (uniformly at random), then use a cryptographically secure pseudorandom generator to stretch it to an arbitrarily long sequence of pseudorandom bits. Under reasonable cryptographic assumptions, that pseudorandom sequence will be computationally indistinguishable from true randomness and so will be just as good as real randomness.

The cryptographic assumptions required are widely believed to be true, e.g., that AES is secure. The likelihood of a practical break of AES is almost certainly far smaller than the likelihood of a bug in your code -- so from a practical perspective, it's in the noise.

From a theoretical perspective, the situation is different. This answer is only implemented at practical implementation, not at proving theorems about complexity classes.

---
Tags: graphs, shortest-path, sampling, randomness
---


# Question
Title: Proper TSP implementation by brute force
I need to implement TSP algorithm by brute force for learning purposes.

I've understood there's a set of cities, let's call it ***`V`*** and it's possible to get a matrix representation for the costs for going from a ***`v1`*** city to a ***`v2`*** city. I'll assume there are not cycles, so it's no possible to going from ***`v1`*** back to ***`v1`***

Then, I should generate a matrix after these sum series:

**However, I really can't see in a practice way how a matrix would be outputed from restrictions.**

Let's say we got 3 cities:

> Madrid, Berlin and Malmo

So the path costs are (and they're not forced to be the same for ways back):

**From Madrid to:**

Berlin: 12
Malmo: 20

**From Berlin to**

Madrid: 32
Malmo: 12

**From Malmo to:**

Madrid: 14
Berlin: 17

So my input is:

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

How should the matrix be outputed according to the sum series?

> ***I assume the algorithm would need to generate a matrix from this exampple:***

There are 3 cities ***`x1`***, ***`x2`*** and ***`x3`*** and got the costs matrix shown below:

$$\begin{bmatrix} 10 & 2 & 1 \\ 3 & 10 & 2 \\ 11 & 2 & 10\end{bmatrix}$$

Following, example shows the next matrix:

$$\begin{bmatrix} x\_{11}+x\_{12}+x\_{13} & & \\ & x\_{21}+x\_{22}+x\_{23} & \\ & & x\_{31}+x\_{32}+x\_{33}\\x\_{11} & x\_{21} & x\_{31} \\ x\_{12} & x\_{22} & x\_{32} \\ x\_{13}& x\_{23} & x\_{33} \end{bmatrix}$$

Which would be the same as:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ \end{bmatrix}$$

Then, considering the power ser of the three cities, matrix got the following rows added:

$$\begin{bmatrix} 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

Finally, the whole generated matrix is:

$$\begin{bmatrix} 1&1&1&0&0&0&0&0&0\\ 0&0&0&1&1&1&0&0&0\\ 0&0&0&0&0&0&1&1&1\\ 1&0&0&1&0&0&0&1&0\\ 0&0&1&0&0&1&0&0&1\\ 0&1&0&0&1&0&0&1&0\\ 0&1&1 & 0&0&0 & 0&0&0 \\ 0&0&0 & 1&0&1 & 0&0&0 \\ 0&0&0 & 0&0&0 & 1&1&0 \\ 0&0&1 & 0&0&1 & 0&0&0 \\ 0&1&0 & 0&0&0 & 0&1&0 \\ 0&0&0 & 1&0&0 & 1&0&0 \end{bmatrix}$$

# Answer
I don't think you should build your matrix according to the integer program, but rather the distance matrix is given as input.

Label your cities in some way, for example let $1$ be Madrid, $2$ be Berlin, and $3$ be Malmo. In your matrix, the entry $(i,j)$ will contain the distance from the city $i$ to city $j$. So you'll get a $3 \times 3$ matrix with zeros on the diagonal (the distance from Madrid to Madrid is zero):

$$\begin{bmatrix} 0 & 12 & 20 \\ 32 & 0 & 12 \\ 14 & 17 & 0\end{bmatrix}$$

Notice that the matrix would be symmetric, if the distance from city $i$ to $j$ would equal the distance from $j$ to $i$.
> 2 votes

# Answer
You write: "I should generate a matrix given by..." That seems to come out of nowhere. You didn't explain why you think that is the way to solve this problem.

Anyway, if you want to solve it by exhaustive search, that's not the way to solve the problem. Exhaustive search means something different. It means you enumerate all possible solutions, compute how good each one is, and keep the best one.

Do you know what the set of possible solutions is? What does a possible solution look like? That would be a good place for you to start. Then, you should double-check that you know how to measure how good a possible solution is. From there, the solution should be straightforward.
> 2 votes

---
Tags: algorithms, traveling-salesman
---


title: Understanding Big O

text:
# Question
Title: Understanding Big O
I'm just trying to get my understanding of big O down. I know the concept and the basics but I'm a bit confused about what it means to be *equal* to big O of something.

For example, is $2^{2n} = O(2^{100n})$? From my understanding it is, since $2^{2n}$ is "faster" than $2^{100n}$, and so completes within the time $2^{100n}$. Is this correct? And if this is true, does it mean that $n$ could have any coefficient greater than $2$ (in this case) such that $2^{2n}$ is equal to $O(2^{mn})$, for all $m \> 2$?

# Answer
The equality symbol used in the Big-O notation is actually abuse of notation, at least this is the way I see it. It is used here for convenience, I guess. Actually, $O(f(n))$ is a set of functions $g(n)$ for which there exists $C$ and $n\_0$ such that $Cf(n) \geq g(n) \geq 0, n \geq n\_0$. Saying that $g(n) = O(f(n))$ you are actually saying $g(n) \in O(f(n))$.

More informally, $g(n)$ belongs to the set of those functions that can eventually be *bounded* from above by $f(n)$, up to some constant.
> 6 votes

---
Tags: asymptotics
---


# Question
Title: Can it be decided whether there exists a string accepted by a given NFA at least k ways?
Can I think this way:

We can convert a NFA to a RE using GFA.

We build a series of GFAs. At each step, one state (other than start or accept) is removed and replaced by transitions that have the same effect.

So, if we can convert k REs which have different forms but accept same language, then there must exists a string that the NFA accepts along k paths.

Does that sound right?

How to prove it properly?

# Answer
The idea is to use a construction very similar to the power set construction. In the usual power set construction, each NFA state has two possibilities: unreachable and reachable. In our case, each NFA state has three possibilities: unreachable, uniquely reachable, and multiply reachable. It is straightforward to carry out the construction, and I will not spell it out here. A state in the DFA is *accepting* if either it contains a multiply reachable NFA accepting state, or it contains at least two uniquely reachable NFA accepting states. There is a word accepted by the NFA using more than one path if the language of the new DFA is not empty. In fact, the language accepted by the DFA consists of all words accepted by more than one path.

Using the same idea, we can compute the language of words accepted by the NFA using exactly, at most, or at least $k$ paths.
> 6 votes

---
Tags: turing-machines, finite-automata, undecidability
---


title: About proofs in descriptive complexity

text:
# Question
Title: About proofs in descriptive complexity
In descriptive complexity, we have theorems that look like $\mathrm{ESO} = \mathrm{NP}$ or "on linearly ordered structures, $FO(LFP) = P$", but I don't really understand the proofs of those.

For the latter, the intuitive equality really means that the statement "$\mathcal A\models \varphi$" can be verified to be true on a linearly ordered structure $\mathcal A$ in time $n^k$ iff $\varphi$ is expressible in some fixpoint logic. The right-to-left inclusion then reads $\forall M\\; \mathrm{polytime \\;TM}, \exists \varphi\in\mathrm{FO(LFP)} \quad \left\[\mathcal A \models \varphi \Leftrightarrow M(\mathcal A) = 1\right\]$.

The proof I have been taught in class for the right-to-left inclusion goes as follows: from a Turing machine M (with set of states $S$), we build a formula on the language $\\{T\_0,T\_1\\} \cup \\{H\_i : i\in S\\}$, where all relations are of arity $2k$. This formula says that the structure it's being evaluated on is a correct computation of $M$ which ends in an accepting state. How does this prove the theorem? Of course, there is a bijection between accepting computations of $M$ and structures $\mathcal A$ s.t $M(\mathcal A) = 1$, but the statement of the theorem doesn't mention this bijection. In my opinion, the formula $\varphi$ that we create should really check properties of $\mathcal A$, and not properties of the computation of $M$ on $\mathcal A$... Where is my mistake? Am I overthinking this?

# Answer
Your intuition is correct, though it's probably more useful to think of the statement "\[Logic\] = \[Complexity Class\]" as "A property of relational structures can be decided in \[Complexity Class\] if, and only if, it is definable in \[Logic\]."

As for the proof, I think you're overthinking it. There's not just a bijection between accepting computations and structures $\cal{A}$ such that $M(\cal{A})=1$ — that's the *definition* of what it means for $M(\cal{A})$ to be $1$. The property of $\cal{A}$ that the formula verifies is "$\cal{A}$ is a structure accepted by $M$." There's really no difference between the statements (for example), "$\cal{A}$ is a connected graph", "$\cal{A}$ satisfies this formula that defines connectivity", "$\cal{A}$ is accepted by this Turing machine" and "this Turing machine accepts $\cal{A}$."

Perhaps it would help to give some intuition about how the proof works. The point about the linear order is that it lets us use the universe of the structure as digits, to write numbers in base $n=|\cal{A}|$. Since the machine we're dealing with runs in time $n^k$, we can index each time step of its computation by a $k$-digit number in base $n$ and likewise each used cell on its tape (in $n^k$ steps, it can't use more than $n^k$ tape cells). You can also use base-$n$ numbers (of fixed length) to represent the states of the Turing machine and the characters in its alphabet. You use this to build up relations that say things like, "At time $t$, cell $i$ of the tape contains character $c$", "At time $t$, the head is at position $p$", "At time $t$, the machine is in state $s$". Now, you write a formula that says:

* at time $0$, the tape contains the coding of $\cal{A}$, the head is at position $0$ (and the head is not anywhere else) and the machine is in its start state (and not in any other state) AND
* if, at time $t$, the machine is in some configuration, then the configuration at time $t+1$ is what the definition of the machine says it should be AND
* at some time $t$, the machine is in an accepting state.

Note that there are various different ways of coding the Turing machine's configuration in relations. For example, since there are only a fixed, finite number of machine states $s\_1, \dots, s\_\ell$, you could use $k$-ary relations $S\_1, \dots, S\_\ell$ such that each $S\_i$ contains the times at which the machine is in state $s\_i$. The tape symbols can be coded similarly.
> 5 votes

---
Tags: descriptive-complexity
---


# Question
Title: Defining a "repeat until"-construct in Denotational semantics
**My Problem is:** to define a "repeat until"-construct in terms of Denotational semantics. I made an attempt and now i need to know if i made it right.

**The Conditions are**: i used the language "While" as specified in "Semantics with Applications" by Nielson & Nielson (1992) (pdf) (WorldCat). I do not want to use the help of the While-construct.

In denotational semantics, we are interested in the effect of a program, rather than in "how" it is executed. Thats why semantic functions are defined compositionally. The corresponding definitions for the Denotational semantics (or "direct style semantics") can be found on page 86 in the Book from Nielson & Nielson (they made it avaible over the Internet).

**My Approach is**: $$\mathcal{S}\_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack = \text{FIX }F\\ \text{where }F\ g = \mathcal{S}\_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\circ\text{cond}(\mathcal{B}\lbrack\lbrack b\rbrack\rbrack , \mathcal{S}\_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\circ g, id)$$

As you might see, my approach is quite similar to the definition of while, but i cannot see a mistake in it.

**post scriptum**: Bounty given, and second edit: yes, i meant $$\mathcal{S}\_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack$$ .. typo corrected.

# Answer
Presumably you mean $\lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack$, which you can easily define using $\text{while}$ as follows.

$$ \mathcal{S}\_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack = \mathcal{S}\_{\text{ds}} \lbrack\lbrack S ; \text{while } \lnot b \text{ do } S\rbrack\rbrack $$

Note that typically, a $\text{repeat}$ construct loops while the condition is *false*; your definition keeps the condition positive.

Building on the above equation and expanding the right-hand side using the table on page 86, you get:

$$ \mathcal{S}\_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack = (\text{FIX }F)\circ \mathcal{S}\_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack\\ \text{where }F\ g = \text{cond}(\mathcal{B}\lbrack\lbrack \lnot b\rbrack\rbrack , g\circ\mathcal{S}\_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack, id) $$

You can transform the above to the following.

$$ \mathcal{S}\_{\text{ds}} \lbrack\lbrack\text{repeat } S \text{ until } b\rbrack\rbrack = \text{FIX }F\\ \text{where }F\ g = \text{cond}(\mathcal{B}\lbrack\lbrack \lnot b\rbrack\rbrack, g, id)\circ \mathcal{S}\_{\text{ds}}\lbrack\lbrack S\rbrack\rbrack $$

Your version is not correct in this regard, it would be equivalent to $\lbrack\lbrack \text{while } b \text{ do } S;S\rbrack\rbrack$, which evaluates the condition *before* rather than *after* the first execution of $S$.
> 3 votes

---
Tags: semantics, denotational-semantics
---


title: CFG for $\{a^ib^jc^k \mid i \neq j+k\}$

text:
# Question
Title: CFG for $\{a^ib^jc^k \mid i \neq j+k\}$
I am trying to design a context-free grammar for the language $L = \\{a^ib^jc^k \mid i\neq j+k\\}$ over the alphabet $\Sigma = \\{a,b,c\\}$.

I know that I can split this up into the union of two cfg's $S\_1$ and $S\_2$,
where $S\_1$ is the case where $\\#\_a \lt \\#\_b + \\#\_c$,
and $S\_2$ is the case where $\\#\_a \gt \\#\_b + \\#\_c$.

I keep producing the grammar that generates this language **but** not in the correct order, that is I am having a hard time keeping the $a$'s on the left, $b$'s in the middle, and $c$'s to the right. Is this even context free?

# Answer
> 3 votes
I would start by finding a CFG that generates the balanced version $\\{a^ib^jc^k\mid i=j+k\\}$ from nonterminal $C$.

> $C\rightarrow aCc\mid B \\ B\rightarrow aBb\mid\varepsilon$

Now, as you correctly note, there are two possibilities on how to get the unbalanced version; either there is $(a^+)$ to the left, or $(b^+\mid b^\*c^+)$ on the right. To deal with the former possibility, you simply add the following rules.

$ S\rightarrow aL\\ L\rightarrow aL\mid C $

You can deal with the other two possibilities in similar manner.

> $ S\rightarrow R\_bb\mid R\_cc\\R\_c\rightarrow R\_cc\mid R\_b\mid C\\R\_b\rightarrow R\_bb\mid B$

# Answer
> 1 votes
The split you made is actually a good design decision.

The language is context-free. Keep a central non-terminal, write $a$'s to the left, and $b,c$'s to the right. If you generate the $c$'s before you generate the $b$'s all letters stay in alphabetic order.

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


# Question
Title: Which theoretical parallel model is closest to CUDA?
Which theoretical parallel model is closest to CUDA/OpenCL programming model?

For example, it fits at some degree to the generic Parallel Random Access Machine (PRAM) model. However, that is too generic, since it makes abstraction of various memory access latencies and synchronization issues.

My question is which is the theoretical model that CUDA architecture fits closest (having in mind the hierarchical parallelism of threads and blocks of threads that cooperate)?

# Answer
To the best of my knowledge, it may be the Queuing Shared Memory (QSM) model, even though hierarchical parallelism of threads is not taken into account. However, accesses to local memory and global memory (different bandwidth), and bulk synchrony (in which threads can work asynchronously beetween barrier synchronizations) are considered.
> 6 votes

# Answer
Since all the SMs execute the same instruction from the CUDA kernel in lockstep, I would say it is plain old SIMD.
> 1 votes

---
Tags: parallel-computing, machine-models
---


# Question
Title: What is a protocol for determining which of two numbers is larger, without sharing those numbers?
**Situation**: Alice has selected a positive integer $a$, and Bob has selected a positive integer $b$. Alice and Bob want to know whether $a \> b$, $a = b$, or $a \< b$, but neither wishes to reveal their chosen number to the other party.

How can Alice and Bob make this determination?

# Answer
As pointed out by Luke Mathieson in the comments, this problem is called **Yao's Millionaire Problem**, for which protocols can easily be found by Googling.
> 1 votes

---
Tags: cryptography
---


# Question
Title: proof of convergence in arbitrary precision PRNGs
consider a program that generates a random walk using a PRNG, as in following pseudocode. it uses arbitrary precision arithmetic such that there is no limit on variable values (ie no overflow).

```
srand(x)
z = 0
while (z >= 0)
{
  r = rand(100)
  if (r <= 50) z -= 1
  else z += 1
}

```

the PRNG is inited with seed `x` *(also arbitrary precision).* the PRNG `rand(100)` generates a value between `0..99`. hence for 51 values the accumulator var `z` is decremented, for 49 values it is incremented.

it is expected due to the law of large numbers that this program will halt for all initial seeds `x`. however,

> how does one prove it will halt for all initial seeds `x`?

it seems such a proof must depend on the details of the construction of the PRNG. am assuming there exist PRNGs such that a different random sequence is generated for every initial seed `x` (ie the infinite set of naturals). that in itself may be up for question. are such PRNGs known? where are they used? etc.. so an answer may come up with an arbitrary PRNG for the purposes of the question. a single example fulfilling the criteria would be an acceptable answer.

looking for related literature, similar problems/proof considered, etc.

# Answer
You ask us for a proof this program will always halt for all initial seeds, but no such proof is possible in general. For instance, if the PRNG always outputs the number 66, then this will never halt (assuming you use big integers). Obviously that would be a really lousy PRNG, but if you aren't willing to assume that the PRNG is good, then no proof is possible.

On the other hand, if you assume that the PRNG is good (i.e., computationally indistinguishable from truly random values), then this is not really a question about PRNGs. Indeed, it's not even a question about computer science. It is a question about whether a particular random walk will eventually return to its starting point. (As such, this question really belongs on a mathematics site, not CS.SE.)

You ask for a proof that the random walk will never return to its starting point (that the probability of return to the initial point is exactly zero). I do not think any such proof is possible, because I do not think the statement is actually true.
> 3 votes

---
Tags: algorithms, reference-request, probability-theory, pseudo-random-generators, random-walks
---


# Question
Title: How does the kleene star and union work in a context free grammar?
Im in a functional languages computer science class and I have a question on the use of the kleene star and the Union in a context free grammar.

for the kleene star I have an idea of how I might do it. for example

```
 {0^n 1^n | n in the set of natural numbers}

```

I think it would look something like this.

```
 S-> 0S1 | A
 A-> S | lambda

```

where lambda would mark closing or ending the string. Is this right?

as for how the union would I dont understand at all how it would work. wer were given an example that looks like this

```
 {0^n1^n | n in the set of natural nubmer} U
 {0^n1^2n | n in the set of natural numbers}

```

I know how I would make a context free grammar for either of these alone but I dont know how the union comes into play with this.

# Answer
This is how you can implement star and union operations over context-free languages given their grammars.

Given a grammar $G$ for the language $L$, we can take a new non-terminal symbol $T$ not appearing in $G$, and add the following production:

$$ T \rightarrow TS \\;|\\; \epsilon$$

where $S$ is the start symbol of $G$. $T$ is now a new start symbol. The language of the resulting grammar is $L^{\*}$.

Similarly, given grammars $G\_1$ and $G\_2$ for languages $L\_1$ and $L\_2$, respectively, we can take a new non-terminal symbol $T$ not appearing in $G\_1$ nor in $G\_2$, and add the following production:

$$T \rightarrow S\_1 \\;| \\;S\_2 $$

where $S\_1$ and $S\_2$ are the starting symbols of $G\_1$ and $G\_2$, respectively. $T$ is now a new start symbol. The language of the resulting grammar is $L\_1 \cup L\_2$. Also, make sure that you use different non-terminal symbols in $G\_1$ ad $G\_2$.
> 6 votes

---
Tags: context-free
---


# Question
Title: Is the image of a function the codomain of a function?
Here is a definition from the functions section in my discrete math textbook (Discrete Mathematics and its Applications 7e, Rosen 2012):

> Let $f$ be a function from $A$ to $B$, and let $S$ be a subset of $A$. The image of S under the function $f$ is the subset of $B$ that consists of the images of the elements of $S$. We denote the image of $S$ by $f(S)$, so:
>
> $f(S) = \\{t \mid \exists s \in S (t = f(s)) \\}.$
>
> We also use the shorthand $\\{ f(s) \mid s \in S \\}$ to denote this set.

So I guess I am just a little confused with the idea of an image. Is it the same as the codomain? And where it says, "The image of $S$ under the function ...". What do you think it means by "under"? Some examples would be great.

# Answer
The image is the subset of the co-domain that the domain actually maps to. Take for instance the following function $$f: \mathbb{N} \rightarrow \mathbb{N}, \quad f(x) = 5.$$

It is simply the constant function that always "returns" 5, no matter what natural number is "passed in." The domain/co-domain defining $f$ is fine, but observe that the only value in the co-domain ever "used" is 5. In this case, the image of $f$ would just be the set $\\{5\\}.$

"The image of $S$ *under* $f$" is an explicit reference to the image of $f$ given $S$. That is to say, it is whatever each element in $S$ maps to as defined by $f$.
> 4 votes

---
Tags: discrete-mathematics, sets
---


# Question
Title: Is the set of non-deterministic Turing machines countable?
We know that deterministic TMs are countable (enumeration). Does the same hold for NTMs? Are TMs and NTMS equinumerous?

# Answer
> 1 votes
Why is the class of DTM countable? Because you can code every DTM as a string (the program) over some alphabet. Now you can sort these strings lexicographicaly. Then the function $$f(i\in \mathbb{N}):=\text{the $i$th string in the sorted sequence of DTMs},$$ is a bijection between the natural numbers and the set of DTMs. Hence the set of DTMs is countable.

Now here is the point. You can argue the same for NTMs. Hence the set of DTMs and NTMs are both countable and therefore equinumerous.

---
Tags: turing-machines, enumeration
---


# Question
Title: Traveling Salesman's Tour Approx Algorithm: is this really a Hamiltonian Path?
I'm given this problem:

Consider the following closest-point heuristic for building an approximate traveling-salesman tour. Begin with a trivial cycle consisting of a single arbitrarily chosen vertex. At each step, identify the vertex u that is not on the cycle but whose distance to any vertex on the cycle is minimum. Suppose that the vertex on the cycle that is nearest u is vertex v. Extend the cycle to include u by inserting u just after v. Repeat until all vertices are on the cycle. Prove that this heuristic returns a tour whose total cost is not more than twice the cost of an optimal tour.

This is the same as Prim's algorithm. Unless I'm missing something, this is not an approximate traveling salesman tour since the traveling salesman requires a Hamiltonian path where we don't revisit any nodes, but on many graphs this algorithm seems to require revisiting nodes to get back to the source node. Am I wrong or is this problem unclearly worded?

# Answer
> 0 votes
You're wrong and the question is also unclearly worded. First, TSP is usually defined in terms of Hamiltonian cycles, not paths. That is, the salesman is in each city exactly once, except for the start point, which he is in twice. Second, as @avakar explains in his first comment, the algorithm given doesn't repeat vertices.

Also, the question seems to be making an unstated assumption. To flesh out @avakar's second comment, suppose you are given cities $1, \dots, n$ where:

* $d(i,n)=k$ for $i\< n-2$
* $d(n-2,n)=d(n-1,n)=2$
* $d(n-2,i)=d(n-1,i)=0$ for $i\<n$
* $d(i,j)=1$ for all other pairs $i$,$j$.

The optimal tours have cost $n$: e.g., $1, 2, \dots, n-2, n, n-1, 1$. However, the given algorithm will produce a tour like $1, n-1, n-2, 2, 3, \dots, n-3, n, 1$ when started at any vertex except $n$. This has cost $n-5+2k$, which is more than twice the optimum whenever $k\>\tfrac12(n+5)$.

---
Tags: traveling-salesman, spanning-trees, approximation-algorithms
---


title: topological sort equivalence

text:
# Question
Title: topological sort equivalence
For a given acyclic graph $G$, a topological sort is an ordering $v\_1, \dots, v\_n$ of the vertices such that the arrows in the graph are all directed forward under that ordering.

Question: can all topological orders of a graph $G$ be obtained from a single ordering by iteratively swapping two vertices that are not connected by an edge?

Motivation. In a certain context I am trying to prove that all topological sorts of an acyclic graph are in fact "equivalent". I want to do this by comparing $v\_1, \dots, v, v', \dots v\_n$ and $v\_1, \dots, v', v, \dots v\_n$ where there is no edge between $v,v'$.

# Answer
> 1 votes
Let $\tau\_1: x\_1, x\_2, \dots, x\_n$ and $\tau\_2: y\_1, y\_2, \dots, y\_n$ be two topological orderings of the vertices of graph $G$. Our aim is to show that $\tau\_1$ can be transformed into $\tau\_2$ by a sequence of swaps, each changing the position of two vertices in the sequence, not connected to each other by an edge of $G$.

Starting from the beginning compare the vertices $x\_i$ and $y\_i$ and select the first pair that differs. For notational convenience we assume $x\_1 \neq y\_1$. As $y\_1$ must occurs in $\tau\_1$ we can find $x\_j=y\_1$, $j\>1$. Thus vertices $x\_1, \dots, x\_{j-1}$ are all *before* $x\_j=y\_1$ in ordering $\tau\_1$, but all *after* $y\_1=x\_j$ in ordering $\tau\_2$. This implies there is no edge in $G$ (in either direction) from $x\_j$ to each of $x\_1, \dots, x\_{j-1}$. Thus we can "legally" swap $x\_j$ with each of $x\_1, \dots, x\_{j-1}$ to get it to the first position. We obtain $\tau'\_1: x\_j, x\_1, \dots, x\_{j-1}, x\_{j+1}, \dots, x\_n$ which has the same first element as $\tau\_2$.

Iterate, or invoke induction.

(Thanks for your suggestions and support.)

---
Tags: graphs, sorting
---


# Question
Title: Computational complexity lecture/videos/exercise
I have basic background (at the level of Sipser's book), but am looking to brush it up and get to the more advanced part via self-study. I have two Computational Complexity books (Arora and Barak and Papadimitriou's).

I am looking for good lectures (online), exercises etc., possibly coursera style, for a faster progress with the material. Any recommendations would be greatly appreciated.

Thanks

# Answer
> 2 votes
Coursera has materials on Automata by Ullman. You can always "preview" that material. Also for a more complete reference on a first course, may I suggest Gusfield's Lectures (available in iTunesU)

For more advanced treatment, Tim Gowers has few online lectures on Computational Complexity and Quantum Computation

Also, the AB book is really good. you may want to stick with that.

If you want more advanced materials, looking into the proceedings of STOC or FOCS from the previous years, might be insightful.

---
Tags: complexity-theory
---


# Question
Title: Is the set-partition problem polynomial time reducible to the subset-sum problem?
There are many solutions on the web showing that the subset-sum problem is polynomial time reducible to the set-partition problem. However, during my search, I came across the following powerpoint presentation (slide 12), where it says that the inverse is also true. i.e. the set-partition problem is polynomial time reducible to the subset-sum problem. So far, I have been unable to find any proofs to show the same.

So, my question: How is the set-partition problem polynomial time reducible to the subset-sum problem, or was there an error on the presentation above?

# Answer
> 3 votes
First, both problems are NP-complete, and are therefore reducible to each other. A concrete reduction can go through the Cook-Levin theorem (i.e. SET-PARTITION$\le\_p$SAT$\le\_p$SUBSET-SUM).

However, in this case there is a fairly trivial direct reduction: given an instance $\\{x\_1,...,x\_n\\}$ for SET-PARTITION, compute $t=\sum\_{i=1}^n x\_i$ and output $\\{x\_1,...,x\_n\\},t/2$ as input for SUBSET-SUM. The correctness of this is very easy to show.

---
Tags: sets, polynomial-time
---


# Question
Title: How does the midpoint line drawing algorithm work?
I'm having trouble understanding the mechanics of the midpoint algorithm. I understand the gist of what it does; it keeps us within a half a pixel of where the actual line should be printed. It does this by updating this $d$ value for each pixel that we traverse.

However, even after drawing some samples and observing what the $d$ value does, I can't figure out the true inner workings of it, and how updating it by these $\Delta\_e$ and $\Delta\_{ne}$ symbols (which are also a bit of a mystery to me) keeps our pixel placement in check.

Can someone summarize it in simple terms for the good of all humanity?

**The Algorithm:**

```
Line (x1, y1, x2, y2)
    begin
    int x, y, dx, dy, d, deltaE, deltaNE;
    x <- x1;        y  <- y1;
    dx <- x2 - x1;  dy <- y2 - y1;
    d <- 2*dy - dx;
    deltaE <- 2*dy;     deltaNE <- 2*(dy - dx);

    PlotPixel(x, y);
    while ( x < x2) do
        if (d < 0) then
        begin
            d <- d + deltaE;
            x <- x + 1;
        end;
        else begin
            d <- d + deltaNE;
            x <- x + 1;
            y <- y + 1;
        end;
        PlotPixel (x, y);
    end;
end;

```

# Answer
This is not a self-contained answer, but you can find all the details and pictures in the link below. However, I'll give a summary of the idea behind this algorithm.

Take $F(x,y) = (x-x\_1)dy - (y-y\_1)dx$ as the line function. Let $p=(x\_p,y\_p)$ be the last pixel we turned on, then $m=(x\_p+1,y\_p+0.5)$ is the point exactly between the right and the right-top neighbouring pixels. This is the middle point as the title suggests.

Now, if $F(x\_m,y\_m) \> 0$ then the line is above $m$ and if $F(x\_m,y\_m) \< 0$ then it is below $m$, otherwise the line passes through $m$. In the first case we turn on the pixel above the midpoint (i.e. top-right of $p$), and the pixel bellow $m$ (right of $p$) for the second case, and an arbitrary one for the third case.

$d$ initially is the value of $2.F(x,y)$ for the first midpoint (the reason for doubling it to get an integer and avoid floating point calculations), so $d$ is guiding us which direction (N or NE) we should go next. At each iteration instead of recalculating $d$, depending on our last choice of direction we just need to add $\Delta\_{NE}$ or $\Delta\_E$ to get the new value for $d$.

http://www.dgp.toronto.edu/~karan/courses/csc418/fall\_2002/notes/lines.html

I hope it helps.
> 1 votes

---
Tags: algorithms, graphics
---