# Question
Title: Space complexity for connectivity problem with given graph diameter
Given $(G,D,d)$, a graph, the graph diameter and the maximum outdegree of the graph. Verify that $G$ is strongly connected in $O(D\log d + \log n)$ space complexity.

---

I thought about using the $STCON$ problem for the whole nodes in the graph, but that will yield a space complexity of $O(n^2 \log^2n)$ (according to Savitch's theorem).

Then I thought about using a DFS traversal (it will be needed twice, actually), but I don't know how to prove it's space complexity.

# Answer
> 1 votes
The idea here is to use a reachability-based approach. Given $u, v \in V$ we ask ourselves whether $u$ reaches $v$ in $G$. By definition, there exists a path that connects $u$ and $v$ if and only if there exists a path of length at most $D$; there are at most $d^D$ such paths.

Loop over all pairs of nodes and all paths to answer the original question. The total space required by this procedure is $\left \lceil \log(n^2d^D) \right \rceil$ plus a constant amount.

---
Tags: graphs, space-complexity
---


# Question
Title: How to figure out whether two texts refer to the same object or event
Let's assume there is something happen in the world - Football world cup final. And team-1 beat team-2 with the score 3:2. So there is whole bunch of articles on every website about it, each contains slightly different wording, sometimes even on different language, but they all about the same event, and contains mostly the same info. Who won, who scored, timing, etc...

So, let's assume we have a 1000 texts about 10 different situation. What is modern approaches in cs, which could

1) group texts about the same situation together (so, instead of 1000 texts - there is 10 groups based on expressed object)

2) packing 1000 texts about the same object into 1, but which contains all new information about object. (Let's say in some text there wasn't coach interview, in some others - no timing where goals was scored, but result text should contain all unique info from each text)

# Answer
> 1 votes
This is a *document clusterization* problem. A general solution is to define some sort of *distance* between documents and apply a standard clusterization algorithm, such as k-means or expectation maximization. There are different approaches to picking distance measure $L$:

* Build a common vocabulary and convert each document into a bag of words, i.e. a long vector consisting of zeros and ones of length $|Vocab|$. Then let $L$ be the Hamming distance between these two representations.
* Compute word2vec embeddings of each word in a document and average them (can be also weighted by TF-IDF -- see this question on SO for details). This will produce a dense $d$-dimensional vector per each document. The distance $L$ can then be defined as Euclidean, Minkowski or more sophisticated distance on vectors in $\mathbb{R}^d$.
* Compute doc2vec embedding directly. Once again it's a dense $d$-dimensional vector per document, so the same choice of vector distances applies.

---
Tags: machine-learning, natural-language-processing, data-mining, information-retrieval
---


# Question
Title: Why does the distribution of pseudorandom numbers change when operating like this?
We were introduced to the standard C `rand()` function, and how to use it.

At some point during the class we were asked how to roll a die. The simple answer was to create a random number, take its modulo 6, and add 1.

```
rand()%6 + 1

```

However, the right answer was building a function that returns a value in the range \[0,1) and then operating with that function to get a random number between 1 and 6.

Since most people in my class haven't seen probability yet, we weren't told why this was the right answer, but the class's assistant told us that taking the modulo of the random number produces a normal distribution of the numbers, while the other function we built:

```
rand / ((double) RAND_MAX + 1)

```

produces a uniform distribution.

Could anyone explain why this happens? I'm not a CS student myself so my knowledge is very basic

Thanks in advance.

# Answer
> 4 votes
rand() returns an integer uniformly distributed between 0 (inclusive) and RAND\_MAX (exclusive).

When using modulo to partition those possibilities into 6 buckets you will end up with a few buckets that has 1 more possibility than the others. This means the random result ends up biased.

However the *exact same thing happens* if you use divide. The only difference lies in which buckets get biased.

This is due to pigeon stuffing. There is no way to divide a population of $2^n$ individuals into 6 groups perfectly evenly.

Instead you should check whether one of the biassing results is returned from `rand()` and generate a new number if so:

```
int bias = RAND_MAX % 6;
int divisor = (RAND_MAX - bias)/6;

while(true){
    int random = rand();
    if(random < RAND_MAX - bias)
        return random / divisor;
}

```

The difference between divide and modulo for partitioning the data has to do with which bits are more random. Many implementations of `rand()` use a simple linear congruential generator where the more significant bits have better randomness than the lesser significant bits. In a good RNG every bit is equally random and it does not matter whether you use modulo or divide.

Having said all that if you really cared about randomness you would use a proper high quality random number generator that doesn't have some of the well known issues you'll find in a LCG.

# Answer
> 1 votes
If your class assistant is indeed telling you that rand() % 6 + 1 produces a normal distributed random variable, that’s total and utter nonsense. Please check that this is indeed what he has been telling you.

Fact is that pseudo random number generators often produce reasonably well distributed numbers in a large range, but the lowest bits are often not very random. You might have 64 but random numbers where the lowest bits alternate between 0 and 1.. rand() % 6 + 1 would then alternate between 1/3/5 and 2/4/6 - not very random, but not random distributed either. That’s why you would avoid using the lowest bits.

In reality, you would write code that picks numbers from 1 to 6 using any method you like, and then *test it*. (The first random number generator u ever used had the nice property that out of any two consecutive random numbers, the second one was larger 60% of the time).

---
Tags: probability-theory, pseudo-random-generators
---


# Question
Title: An algorithm for k-way array partitioning
I am trying to implement samplesort in MPI. The first step of samplesort is to partition the array with $n - 1$ splitters $s\_1, s\_2, \cdots, s\_{n-1}$ into $n$ subsequences, where subsequence $i$ all have values in the range of $\[s\_i, s\_{i + 1})$ (let $s\_0 = -\inf, s\_n = \inf$).

My question is: how to implement this efficiently, preferably in place?

I can't even figure out how to do it out of place, other than allocating $n$ dynamic sized arrays and finally concatenating them together. In the case of single splitter, we can successively push the values smaller and larger than the splitter to the two ends respectively, but for more splitters, I don't know how to do it efficiently.

# Answer
> I can't even figure out how to do it out of place, other than allocating n dynamic sized arrays and finally concatenating them together.

Which is the approach used by the explanation in Wikipedia, so it's not necessarily a bad one.

> My question is: how to implement this efficiently, preferably in place?

I assume you know how to do a quicksort partition. To do the multi-way split in place, you can turn it into a series of quicksort partitions.

```
# Splitters are sorted
# min and max indices are inclusive
multipartition(array A, int Amin, int Amax, array Splitters, int Smin, int Smax):
    if Amax <= Amin:
        return
    if Smax < Smin:
        inner_sort(A, Amin, Amax)
    else:
        Smid = Smin + (Smax - Smin) / 2
        split_idx = partition(A, Amin, Amax, Splitters[Smid])
        multipartition(A, Amin, split_idx - 1, Splitters, Smin, Smid - 1)
        multipartition(A, split_idx + 1, Amax, Splitters, Smid + 1, Smax)

```

I assert that this is as efficient as the non-in-place approach based on binary search given in the Wikipedia article, because each element of A will take place in $\log(|\text{Splitters}|)$ calls to `partition`, which is linear time.
> 3 votes

---
Tags: sorting, quicksort, partitions
---


# Question
Title: Defining polynomial hierarchy with oracle machines and quantifiers
While trying to understand the concept of polynomial hierarchy, I noticed that there are several ways to define it. And the most confusing thing about the situation is to see the equivalence between those definitions intuitively. What I want to know for now is the relation between oracle machines and existential/universal quantifiers from the viewpoint of polynomial hierarchy.

By Wiki, the polynomial hierarchy is the generalization of the classes P, NP, and co-NP to oracle machines. The addition of oracles (not sure this is a suitable expression) results in the increase of the hierarchy.

On the other hand, another way to define the polynomial hierarchy is to use the quantifiers $\forall$ and $\exists$. According to this lecture note (http://www.cs.cornell.edu/courses/cs6810/2009sp/scribe/lecture5.pdf), a language $L$ is in $\Sigma\_i$ iff $\exists$ a polynomial time relation $R$ s.t. $x\in L$ iff \begin{equation} \exists y\_1\forall y\_2\cdots Q\_iy\_iR(x,y\_1,\cdots y\_i), \end{equation} where $Q\_j=\forall$ if $j$ is even and $Q\_j=\exists$ if $j$ is odd. And $L$ is in $\Pi\_i$ iff its complementary $\bar{L}$ is in $\Sigma\_i$.

From the above definitions, it seems that there exist a sort of one-to-one correspondence between the inclusion of oracle and the addition of quantifiers.

Can anyone help me understand how the oracles in a Turing machine plays the role of quantifiers in predicates?

# Answer
The oracles do not play the role of quantifiers, they play the role of everything but the first quantifiers.

First, observe how NP relates to $\exists yR(x,y)$ with $R$ in P. That means that NP allows existential nondeterminism followed by computation in P.

Similarly, $\Pi\_1$ "is" $\forall yR(x,y)$ with $R$ in P. Now for $\Sigma\_2$ we have the same with an additional $\exists$ at the front: $\exists y\_1\forall y\_2R(x,y\_1,y\_2)$ with $R$ in P. Or, in other words, $\exists y\_1 R'(x,y\_1)$ with $R'$ in $\Pi\_1$. So we have existential nondeterminism followed by computation in $\Pi\_1$. And that is more or less the same as NP with a $\Pi\_1$ oracle.

In general, the first quantifier specifies whether we are in the existential or universal case. The rest of the formula then describes a lower level of the hierarchy which we use as an oracle.
> 2 votes

---
Tags: polynomial-time, oracle-machines
---


title: Is the following figure DAG?

text:
# Question
Title: Is the following figure DAG?
I have been through multiple definitions of DAG and all of them say that it is a directed graph without cycles. Also, it is said that it has topological ordering.

Now the following figure is directed graph and does not have cycles.

But looking at the ordering of edges (look at edge (2,1)), it is not topologically ordered.

Is this still a DAG or every edge must be topologically ordered for this graph to be a DAG??

# Answer
> 5 votes
The acronym *DAG* stands for directed acyclic graph. In other words, a DAG is a (finite) digraph without directed cycles. A digraph is a DAG if and only if it has a topological ordering.

In your example you have a labeled DAG. The labels do not constitute a topological ordering of the DAG, but the underlying digraph is still a DAG.

---
Tags: graphs, data-structures, dag
---


# Question
Title: What is the difference between centralised, decentralised, distributed, fully-distributed?
What is the difference between centralised, decentralised, distributed, fully-distributed, partially-centralised, partially-decentralised system? Which type or topology is the system attached in the picture below? For instance, A is a master node (coordinator) of A1, A2, A3, which makes this part a centralised system. A, B, C and D are all connected between each other, which makes this system a decentralised one. But then, what are fully-distributed, partially-centralised, partially-decentralised systems?

# Answer
> 1 votes
You need to differentiate between centralization/decentralization on the one hand and distributed/non-distributed on the other hand.

**Centralization**
Centralization tells you where the processing gets done.
Fully centralized systems do all their processing in one place.

**Distribution**
Distribution has nothing to do with processing. It just relates to systems that communicate via messages.
A non-distributed system is a stand-alone PC with no clients, or a server with dumb clients.

A fully distributed system does not have a single source of truth, however that does not mean that all nodes have to be equal. You can have 'supernodes' mixed with lesser nodes and still be fully distributed.

**Distribution = network**
The current incarnation of distributed systems are networked systems, but of course it's perfectly possible to pass messages using a serial cable, sneakernet or carrier pigeon. Is that a distributed system?
Yes if both systems do actual work, No if one system is simply a recipient of data (printer/terminal etc).

**Peripherals do not count**
*The passing of screen and keyboard data between the terminal and the server is not deemed substantial enough to qualify as message passing.*

**Caveat**
The definition of distributed computing is best narrowed down in the context of a specific protocol or algorithm (e.g. bittorrent or mapreduce)
Outside that context it becomes exceedingly vague to the point of being meaningless.

**The mysterious diagram**
The diagram in the question seems to hint at some sort of hierarchy and thus centralisation.
Obviously the systems A,B,C and D cannot be peripherals (because they are not leaf nodes) and thus some message passing (aka network activity) ought to take place.
What the nature of the leaf nodes (A123 et al) is is unclear, but these leafs do seem subservient to A,B and C proper.

# Answer
> 0 votes
In addition to Johan's answer:

A decentralised system is a fully distributed system where all the nodes in the network are equal so that there is no "authority" node in the network. Bitcoin Network is an example of this.

---
Tags: distributed-systems, computer-networks, network-topology
---


# Question
Title: Find if *any* path exists between vertices in a directed acyclic graph
Given a directed acyclic (and unweighted) graph and two distinct vertices S and T, is there an algorithm that will tell me if there is *any* path (not necessarily the shortest one) between the two? If it helps, I don't need the list of vertices on this path, just the fact that path exists.

I sure know of all the graph shortest-path algorithms (Dijsktra/Bellman-Ford/topological sorting/etc.), but I don't actually need the shortest one. Is there a speedy method of finding any arbitrary path in a DAG between two nodes? Pretty sure there is aplenty of specialized algorithms for that, just not sure where to search for.

# Answer
> 2 votes
Think of it that way: If given a DAG and two vertices $s,t$ (with no other information) you can't get any better than linear time.

Once you understand that, asymptotically you won't get any better than algorithms such as BFS or DFS. So in your case, solving a "harder" problem (i.e finding the shortest path) is the same (complexity-wise) as solving your problem (finding any path). Therefore BFS or DFS will be the exactly algorithms you search for.

# Answer
> 1 votes
Literally any search algorithm will do this; the simplest are probably breadth-first- and depth-first search.

---
Tags: graphs
---


# Question
Title: Finding a minimum weight perfect matching in Christofides TSP algorithm
Context: After creating the minimum spanning tree, the next step in Christofides' TSP algorithm is to find all the N vertices with odd degree and find a minimum weight perfect matching for these odd vertices. N is even, so a bipartite matching is possible.

When the N odd-degree vertices are found, there are $n \choose \frac{n}{2}$ possible ways to split them into two sets. Does Christofides' algorithm really need to run a min-weight bipartite matching for all of these possible partitions? Or is there a better way?

I realize there is an approximate solution, which is to greedily match each vertex with another vertex that is closest to it. However, if the exact solution is to try all possible partitions, this seems inefficient.

# Answer
There is the Blossom algorithm by Edmonds that determines a maximal matching for a weighted graph.
> 3 votes

# Answer
The blossom algorithm can be used to find a minimal matching of an arbitrary graph. It's nicer to use than a bipartite matching algorithm on all possible bipartitions, and will always find a minimal perfect matching in the TSP case.
> 0 votes

---
Tags: traveling-salesman, bipartite-matching
---


# Question
Title: Using Myhill-Nerode to prove that language is not regular
L = {$xy ∈ \\{a, b\\}^∗ : |x| = |y|$ and x contains the substring aa}

I am trying to prove that this language is not regular using MyHill-Nerode theorem but I am unable to find equivelance classes of this language. Thanks.

# Answer
> 4 votes
Consider two words $u\_i = b^i aa, u\_j = b^j aa \in \\{a, b\\}^\ast$ with $i \< j$. We have that $u\_i \not\sim\_L u\_j$ because if you concatenate the word $v = b^{i+2}$ to both words we obtain $$u\_i \cdot v = b^i aa \cdot b^{i+2} \in L \text{, but } u\_j \cdot v = b^j aa \cdot b^{i+2} \notin L.$$ Thus, $v$ separates $u\_i$ and $u\_j$ for $L$. Since we can find infinitely many $i, j \in \mathbb{N}$ with $i \< j$ we have also infinitely many Myhill-Nerode-equivalence classes.

---
Tags: formal-languages, regular-languages
---


# Question
Title: Higher Residuocity Problem w.r.t. a composite Modulus
An integer $q$ is called a quadratic residue modulo $N$ if it is congruent to a perfect square modulo $N$; i.e., if there exists an integer $x$ such that: $x^2≡q\ (mod\ n)$.

Otherwise, $q$ is called a quadratic non-residue modulo $N$.

Given that $N$ is a composite number (whose prime factorization is known beforehand) can someone help with the generic *higher residuocity* problem of the form:

$(x^2-c^2)^k≡q\ (mod\ n)$.

Find $x$ (where $c$ is some random integer value)? $k$ is an even number (say 2).

I think we can solve it using an approach similar to the original QRP, but I am struggling with the exact approach. Can someone please help with an explicit example?

# Answer
Testing whether $q$ is a quadratic residue modulo $n$ is hard when $N$ is composite: it is as hard as factoring $N$, which is believed to be hard when $N$ is large.

The same is true for your problem.

If the factorization of $n$ is known and $k=2$, you can test whether $q$ is a quadratic residue; find all square roots, call it $y$, such that $y^2 \equiv q \pmod n$, then for each such square root $y$, test whether $y + c^2 \bmod n$ is a quadratic residue and find a square root of it, i.e., an $x$ such that $x^2 = y + c^2 \pmod n$, and then you will have a solution to your original problem. This will be efficient if there aren't too many square roots, i.e., if $N$ doesn't have too many different prime factors.

Alternatively, assuming $n$ is squarefree and has known factorization $n=p\_1 \cdots p\_m$ and assuming $k$ is not too large, you can factor the polynomial $(x^2-c^2)^k-q$ over $\mathbb{Z}/p\_i\mathbb{Z}$ (separately for each prime factor $p\_i$ of $n$), then if this polynomial has a root modulo every $p\_i$, combine solutions via the Chinese remainder theorem.
> 1 votes

---
Tags: algorithms, number-theory
---


# Question
Title: What is the complexity class of this variant of Subset sum?
Let's represent Subset Sum problem with binary arrays instead of numbers. Example: given two-dimensional array

```
[1, 0, 0] (4)
[1, 0, 1] (5)
[0, 0, 1] (1)

```

is there set of one-dimensional arrays, sum of which is equal to

```
[1, 0, 0, 1] (9)

```

In this problem sum of bits in each position can have carry-over. If carry-overs are forbidden (bit positions are independent) and we ask instead: are there arrays which sums to

```
[2, 0, 1]

```

then what complexity class such problems belong to? In what papers it was studied?

# Answer
This is NP-hard. The associated decision problem is NP-complete.

There are various ways to prove that. For instance, there's a straightforward reduction from exact cover; let the target array be all-ones, and then you have an instance of the exact cover problem, which is NP-hard.

Your problem is an instance of multi-dimensional subset sum (or multi-dimensional knapsack), for which you can find algorithms and approximation algorithms in the literature.

Related: https://cstheory.stackexchange.com/q/19976/5038, How to find subset of vectors whose sum has certain characteristics, https://cstheory.stackexchange.com/q/21865/5038, https://en.wikipedia.org/wiki/List\_of\_knapsack\_problems#Multiple\_constraints
> 3 votes

---
Tags: complexity-theory, np-complete, subset-sum
---


# Question
Title: How is an OS page stored in a k-way set-associative cache?
I have been reading about set-associative caches. As far as I have read, in case of n-way set-associative cache each way stores, a block (let's say 16 bytes) and therefore each set will be of size 16n bytes. But what if I have to load a whole page into the cache. Since the size of a page is much larger than a block, how is that distributed over the cache? Another question is what would be the distribution in case of a shared NUCA cache design? Assume that a single tile has a private L1 cache and shared L2 cache.

# Answer
> 1 votes
There are few things to be cleared first.

Lets assume a `a`way set associative cache with `b`wide cache-lines and `c` number of cache lines. In this configuration, size of the cache is `a X b X c`. Number of bits needed to represent the number of cachelines, is called index bits. (ex: 1024 cachelines will need 10 bits). When we need to load data, the index bits of the memory address tells us in which cache line this data will be stored. Since our cache is `a`way, there are `a` number of cachelines, all indexed by this index bits, this data can be stored. If there are empty lines, we will use them, otherwise we have to replace and entry and store the newly fetched data.

Now coming back to your original question,

Think of "loading the page to cache" as reading the entire page in cacheline quantities. Assuming all the cache entries are invalid, first `n` reads will be stored in the first entry in each block of cachelines, the second `n` reads will be stored in the second entry in each block.

In a 2-way set assoc cache with 4 cachelines, this is how it would look like.

`cacheline 1 set0 - addr 0
cacheline 1 set1 - addr 4
cacheline 2 set0 - addr 1
cacheline 2 set1 - addr 5
cacheline 3 set0 - addr 2
cacheline 3 set1 - addr 5
cacheline 4 set0 - addr 3
cacheline 4 set1 - addr 7`

# Answer
> 0 votes
> But what if I have to load a whole page into the cache.

There is generally no operation to load a whole page into the cache.

In fact, there is generally no mechanism to request the loading of even a single cache line.

Instead there are CPU instructions that request memory contents (reads/writes or loads/stores) — these CPU instructions that operate in terms of bytes, 16-bit half words, 32-bit long words, 64-bit words, ...) but usually the maximum is less than a whole cache line.

(*The cache line size is typically chosen such that it is larger than the largest read (or write) request a processor instruction can make; this is so that a miss will at least somewhat "read ahead". (Modulo vector instructions, which can have very large operand sizes..)*)

What will happen is that the program (section) that we say is accessing the whole page will actually decompose into individually executed CPU instructions (often in loops) that access individual memory locations (e.g. as bytes, longs, quads).

(*Ideally, such a program section accessing memory from some page or pages will do so sequentially, which will capitalize on the a read-ahead effect to the cache. A read for a 64-bit word that misses will cause a whole line to be read in, and then a read for the next sequential 64-bit word will already be in the cache.*)

The state of the cache upon completion of the program (section) will be how it is left after its last instruction. There is no guarantee that the whole page still remains in the cache, though it is possible that this happens.

The point is that the processor simply executes and handles each instruction in sequence and those cause occasional cache misses and the end state of the cache is the result of cumulative effect of the individual instructions rather than some more global "load *this* page into the cache".

> Since the size of a page is much larger than a block, how is that distributed over the cache?

Each individual cache miss is handled separately, and may evict other cache lines, in accordance with the associativity, meaning that only lines with at the same index (in the associativity set at that index) are eligible for eviction on a miss.

The total result is a combination of the overall cache construction & hardware algorithm, and the sequence of CPU instructions executed in any given software algorithm, and is arrived at by the compounding cache misses and the resulting evictions and lines loaded. (Cache hits may also modify priorities of subsequent evictions, of course).

---
Tags: computer-architecture, cpu-cache, memory-hierarchy
---


title: Existential Theory of the Reals in NP?

text:
# Question
Title: Existential Theory of the Reals in NP?
It is known that the existential theory of the reals is decidable in PSPACE (via John Canny), but as far as I can tell no one has demonstrated that it is in NP. This confuses me because it seems like a short certificate for a given formula would be an example of values for the variables included in the formula that demonstrates a valid assignment. Why is this argument invalid?

# Answer
> 5 votes
No, unfortunately that doesn't work. The certificate needs to be a sequence of bits that is verifiable in polynomial time -- and thus the length of the certificate has to be at most a polynomial in the length of the input instance. If your certificate is the value of some variables, and those values are real numbers, you might not be able to write down their binary representation in any reasonable amount of space (indeed, their binary representation might be infinite-length).

For instance, consider the sentence $\exists x . x^2 = 2$. This sentence is valid, as $x= \sqrt{2}$ is an example that makes $x^2=2$ true. However, when you try to write out $\sqrt{2}$ in binary, you get an infinite sequence, so it's not clear what the short certificate would be. (Certificates need to be of finite length, certainly.) In general, representing real numbers in binary is messy business; no matter what representation you choose, there will always be some real numbers you can't represent finitely.

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


# Question
Title: Maximum sum subset of an array with an extra condition
We are given numbers $n \leq 200$, $k \leq 10$ and an array of $3n$ positive integers not greater than $10^6$. Find the maximum possible sum of a subset of elements of this array, such that in every contiguous $n$ elements there are at most $k$ chosen.

As this is an old high-school level contest problem, I ask for some hints. Also, this means **I know there exists a solution far quicker than the proposed by D.W.** and most likely not very complicated, so the question is still open.

My ideas mostly involved dynamic programming. I was trying to calculate, for each prefix of the array, best score we can acquire. However, in order to do this, I think I would need to calculate it for every prefix, and every possible choosing of $k$ numbers in the last $n$ numbers of this prefix, resulting in complexity $O(n^{k+1})$, which is far from acceptable. Also, I thought of looking at pairs of positions in the array which are distant by $n$ and their relation to each other, but this approach fails, as in an optimal solution not in every contiguous $n$ element we would choose exactly $k$, sometimes it could be less.

# Answer
> 2 votes
Let's call the length of the array $t \cdot n$, so in your task $t=3$. Since in every fragment $\[1, n\], \[n+1, 2n\] \ldots \[(t-1)n+1, tn\]$ we can't take more than $k$ elements, so the number of taken elements won't be larger than $t\cdot k$. Let's call the indices of taken elements in the given array $x\_1, x\_2 \ldots x\_{tn}$. It's easy to notice that $x\_i + n \le x\_{i+k}$, because there can't be more than $k$ elements in any window of size $n$.

With this knowledge we are ready to construct dynamic programming solution, which would choose in parallel indices for every segment $\[x\_1 \ldots x\_k\], \[x\_{k+1} \ldots x\_{2k}\] \ldots \[x\_{(t-1)k+1} \ldots x\_{tk}\]$ separately.

$$dp\[k+1\]\[k+1\]\[k+1\]...(t\\,times)\[tn\]$$ We would iterate trough positions $i$ from $1$ to $tn$ and every time decide whether we want to take one more element in the first segment from the position $i$, in the second segment from the position $i+n$, in the third segment from the position $i+2n$ etc. Bear in mind that at any point any segment cannot have more chosen elements than one of its preceding segments.

For $t = 3$: $$dp\[a\]\[b\]\[c\]\[i\] = max(dp\[a\]\[b\]\[c\]\[i-1\], dp\[a-1\]\[b\]\[c\]\[i-1\] + A\[i\], dp\[a\]\[b-1\]\[c\]\[i-1\] + A\[n + i\], dp\[a\]\[b\]\[c-1\]\[i-1\] + A\[2n + i\], dp\[a-1\]\[b-1\]\[c\]\[i-1\] + A\[i\] + A\[n+i\] \ldots)$$ There are in total $3^t$ different combinations of taking elements from $i$-th position and it can be easily fixed in code using additional $3^t$ states. if $a \le b \le c$ is not met: $$dp\[a\]\[b\]\[c\]\[i\] = -inf$$

Result of the given task is stored in one of $dp\[x\]\[0\]\[0\]\[tn\], dp\[k\]\[x\]\[0\], dp\[k\]\[k\]\[x\]$ states for any $x$ depending on how many elements does the optimal solution use.

So overall time complexity is $O(tn(k+1)^t3^t)$ and space complexity is $O(tn(k+1)^t)$.

# Answer
> 1 votes
## Method 1: Merging lazy streams

One approach you could try involves iterating through partial solutions for a part of the array, in decreasing merit, and then merging them:

1. Enumerate the ways of selecting at most $k$ out of the first $n$ elements, in decreasing order of their sum. But don't try to build a list that lists all of these possibilities: instead, build a lazy stream that lets you iterate through this list one by one.
2. Similarly, construct a lazy stream that iterates through the ways of selecting at most $k$ out of the second $n$ elements, in decreasing order of sum; and a lazy stream that iterates through the ways of selecting at most $k$ out of the last $n$ elements.
3. Merge these streams. Basically, given streams $S\_1,S\_2,S\_3$, construct a stream $S$ of elements $s\_1+s\_2+s\_3$, sorted by decreasing order, where $s\_1 \in S\_1,s\_2 \in S\_2, s\_3 \in S\_3$.
4. Iterate through the stream $S$, in decreasing order. Each one gives you a candidate solution. Check whether it satisfies the requirements: i.e., whether for every sequence of $n$ consecutive elements, at most $k$ of them have been chosen. As soon as you have found a single one that satisfies the requirement, you are done; you know that one must be optimal.

So, the problem boils down to how to iterate lazily through these streams. There, I think you can work out a clean way to do that, using priority queues.

There are no guarantees on the running time of this procedure. A worst-case input could force this to run a very long time.

But I expect most inputs will behave better. That's because for many input arrays, if at most $k$ out of the first $n$ elements are selected, and same for the middle $n$ and the last $n$, then there is a fair chance that in every $n$ contiguous elements, at most $k$ are selected.

## Method 2: Divide-and-conquer

We can improve method 1 by noting that once we know which ones have been selected from the middle, we can separately find the best for the left side and the best for the right side:

1. Enumerate all ways of choosing at most $k$ out of the middle $n$ elements ($A\[n..2n-1\]$), ordered by decreasing sum.
2. For each, find the best way to select a subset of the first $n$ elements ($A\[0..n-1\]$) that can be combined with these middle ones. Separately, find the best way to select a subset of the last $n$ elements ($A\[2n..3n-1\]$) that can be combined with these middle ones. (These two searches can be done independently.) This gives you a candidate subset of the entire array; compute its sum, and if it is the best seen so far, remember it.

Basically, what we are exploiting is that, given information about which subset of the middle $n$ have been chosen, the subset of the first third is conditionally independent of the subset of the last third. The choice of which ones you select from the first third does not affect your options about which ones you select from the last third.

So, how do we do step 2 efficiently? In other words, given a subset of the middle third of the array, how do we find all ways to extend that to a subset of the first two-thirds that doesn't violate any constraints?

One way is to lazily enumerate all ways of selecting at most $k$ out of the first $n$ elements, in decreasing sum, and then for each test whether it can be combined with the selection you've already got for the middle $n$. This is already enough to do significantly better than method 1. If we have to look $d$ deep into each of the three streams, method 1 will look at $O(d^3)$ combinations, whereas method 2 will look at $O(d^2)$ combinations.

I think the process of selecting the subset of the first third can be sped up a bit further, using your knowledge of the subset of the middle third. Let $i\_1,i\_2,\dots,i\_k$ be the indices of the subset of the middle third that was chosen, where $n \le i\_1 \< i\_2 \< \dots \< i\_k \le 2n-1$. Then this breaks up $A\[0..n-1\]$ into $k+1$ segments: $A\[0..i\_1-n\]$, $A\[i\_1+1-n..i\_2-n\]$, ..., $A\[i\_{k-1}+1-n..i\_k-n\]$, $A\[i\_k+1-n..n-1\]$. Let $m\_0,m\_1,\dots,m\_k$ denote the number of items we've selected in each of those segments. Then these numbers must obey all of the following constraints: $m\_k = 10-k$, $m\_k+m\_{k-1} \le 11-k$, $m\_k+m\_{k-1}+m\_{k-2} \le 12-k$, \dots, $m\_k+\dots+m\_1+m\_0 \le 10$. So, enumerate through all of the combinations $m\_0,m\_1,\dots,m\_k$ that satisfy all of these constraints. Then, choose the $m\_i$ largest numbers in the $i$th segment of $A\[0..n-1\]$, and add them to your selection (no need to enumerate over combinations here).

---
Tags: algorithms, optimization, dynamic-programming, subsequences
---


title: Does a DPDA halt on all inputs?

text:
# Question
Title: Does a DPDA halt on all inputs?
Given a deterministic DPA, is it possible to tell whether it halts on all possible inputs? Is this problem decidable?

The standard halting problem is "Given a DPDA and an input $x$, determine whether it halts on input $x$", and that problem *is* decidable. But what about the variant above?

# Answer
Yes, this problem is decidable. It can be answered in polynomial time. We can check whether there exists any input $x$ that causes it to enter an infinite loop, by characterizing the states from which it could enter an infinite loop.

First, let me establish some terminology. Let $Q$ denote the set of states of the DPDA, and $\Gamma$ the stack alphabet. A configuration is a pair $(q,t)$ with $q \in Q$, $t \in \Gamma^\*$, where $q$ represents the state of the automaton and $t$ the contents of its stack. Define the *status* of the automaton at any point to be a pair $(q,\gamma)$ where $q \in Q$ represents the state of the automaton and $\gamma \in \Gamma$ the symbol at the top of the stack. Thus, the status gives only partial information about the configuration of the automaton.

Now, the strategy is going to be twofold:

1. We will determine, for each possible status $(q,\gamma)$, whether that status is reachable (i.e., whether there is some input $x$ that takes the automaton to a point where it is in that status).
2. We will also determine, for each possible status $(q,\gamma)$, whether the automaton enters a particular kind of infinite loop if the automaton starts in the configuration $(q,\gamma)$ and then reads the input $\epsilon$ (the empty word). In particular, if it starts in configuration $(q,\gamma)$ and reads the input $\epsilon$, we'll test whether it transitions to any configuration $(q,t)$ where $t$ has the form $\cdots \gamma$ (i.e., $\gamma$ at the top of the stack, with some other stuff below it in the stack) in the process of reading the empty word.

Putting these two together, if there is a status $(q,\gamma)$ for which the answer to both questions is yes, then we will learn that the input $x$ causes the automaton to enter an infinite loop. We will show a polynomial-time algorithm for each. Since there are only finitely (in fact, polynomially) many possibilities for the status, this gives a polynomial-time algorithm for the original problem. So, on to the details of how to check each of these things.

First, reachability is easy and can be tested using standard methods. (For instance, construct a new automaton that halts when it enters the status $(q,\gamma)$ and otherwise doesn't halt, then check whether that automaton accepts the empty language or not; there is a standard algorithm for that.)

Second, it's easy to find all statuses $(q,\gamma)$ where an automaton that starts in configuration $(q,\gamma)$ and reads the empty word will enter an infinite loop of the particular kind mentioned above. (One way is to reduce this to reachability; construct a new automaton that starts in configuration $(q,\gamma)$ and halt if it reaches any configuration of the form $(q,\dots \gamma)$ apart from the initial state, discarding all non-$\epsilon$ transitions from the original automaton and keeping only the $\epsilon$ transitions. Then, check whether this new automaton accepts a non-empty language.)

This yields an algorithm for the original problem. Why is it correct?

Well, if this algorithm outputs "yes", then it is correct -- there exists an input $x$ that causes the automaton to halt. In particular, we know there exists an input $x$ that causes the automaton to transition to status $(q,\gamma)$, i.e., to some configuration of the form $(q,t\_0 \gamma)$. Suppose reading the empty word causes the automaton to transition from configuration $(q,\gamma)$ to $(q,t\_1 \gamma)$; then it follows it will subsequently transition to $(q,t\_1 t\_1 \gamma)$ and even later to $(q,t\_1 t\_1 t\_1 \gamma)$ and so on, entering an infinite loop. Thus, reading the empty word will cause the automaton to transition from the configuration $(q,t\_0 \gamma)$ to the configurations $(q, t\_0 t\_1 \gamma)$ and $(q, t\_0 t\_1 t\_1 \gamma)$ and so on, thus entering an infinite loop. Since the input $x$ takes us to that configuration $(q,t\_0 \gamma)$, we have found an input $x$ that causes the DPDA to enter an infinite loop. So if the algorithm says "yes", it is correct.

What about the converse? Let's suppose there exists some input $x$ that causes the DPDA to enter an infinite loop. It follows that the infinite loop must happen during the $\epsilon$-transitions that follow some finite prefix of $x$, say $x'$. Let $(q',t')$ denote the configuration of the automaton immediately after reading the last letter of $x'$ (but before following any of the subsequent $\epsilon$-transitions). Let's consider the sequence of configurations that the DPDA visits after that point, by following the $\epsilon$-transitions. By assumption, this is an infinite sequence. Consider the corresponding sequence of statuses. Since that is infinite sequence, and there are only finitely many statuses, there must be at least one status that appears infinitely many times. Discard a large enough prefix of the sequence so that you remove all the statuses that occur only finitely many times, so that now we have a sequence where all statuses recur infinitely many times; such a prefix must exist. Among all configurations in the resulting sequence, pick the configuration where the height of the stack is minimal. Call this configuration $(q,t)$ where $t=t\_0 \gamma$. By the choice of $(q,t)$, it follows that in all subsequent configurations the stack is at least as tall, so the original symbols $t\_0$ are never popped, i.e., all subsequent configurations are of the form $(q',t\_0 u)$ for some $q' \in Q$, $u \in \Gamma^+$. Also since the status $(q,\gamma)$ recurs infinitely often in the sequence and since $(q,t\_0 \gamma)$ was the one of minimal height, there must be some subsequent configuration of the form $(q, t\_0 t\_1 \gamma)$ (i.e., some subsequent configuration with the same status, but stack at least as high). And since we got from $(q, t\_0 \gamma)$ to $(q, t\_0 t\_1 \gamma)$ by $\epsilon$-transitions, without ever popping off the $t\_0$ part, this means we'll enter an infinite sequence $(q, t\_0 \gamma) \leadsto (q, t\_0 t\_1 \gamma) \leadsto (q, t\_0 t\_1 t\_1 \gamma) \leadsto (q, t\_0 t\_1 t\_1 t\_1 \gamma) \leadsto \cdots$. Since the $t\_0 \gamma$ was never popped off, that also means that if we had started in the configuration $(q, \gamma)$, we would also have entered an infinite sequence $(q, \gamma) \leadsto (q, t\_1 \gamma) \leadsto (q, t\_1 t\_1 \gamma) \leadsto \cdots$, and this would have been detected in step 2 of the algorithm. Also, by assumption, since the configuration $(q, t\_0 \gamma)$ is reachable on input $x'$, the status $(q,\gamma)$ is reachable and this would be detected in step 1 of the algorithm. In summary, if there exists an input $x$ that causes the DPDA to enter an infinite loop, there exists a status $(q,\gamma)$ that is reachable and that triggers an infinite loop of the specific kind detected in step 2 of the algorithm, so the algorithm will output "yes".
> 4 votes

---
Tags: automata, pushdown-automata, halting-problem
---


# Question
Title: Are there any stochastic models of non determinism in the rate of program execution?
We know that typical operating systems and high level languages (especially those with garbage collection) cannot be used for real time operating systems. Java & jet engines don't mix, and consequently a lot of study has gone into researching and developing real time operating systems.

Is there any research as to exactly why a traditional operating system and high level garbage collecting language **can't** be used? I'm interested in any stochastic modelling that might have been done, rather than lots of words. So as a simple example, is there a mathematical model for the execution rate of say a simple FOR /NEXT loop on something like \*nix + Java? Ideally this should refer to contemporary micro processors with all their associated speculative execution, interrupt handling and other modern optimisations like memory reclamation and parallel processing.

I would also extend this reference request to any models that might try to equate the mensuration of the execution rate of such a FOR /NEXT loop, with the Observer Effect as found in quantum mechanics.

# Answer
> 1 votes
There *is* work on estimating the worst-case execution time for code (sometimes called WCET analysis). You can start with the Wikipedia article on the subject and use Google Scholar to find many research papers on that topic.

However, in traditional systems, the problem is not that the running time is random (well, that's one problem, but it's not the most serious one). The more serious one is that the running time is *unpredictable*. We can't even assign a probability distribution to it -- we have no basis for doing that.

For instance, in many garbage-collected languages, response time is unpredictable and real-time operation cannot be guaranteed. The garbage collector might kick in at any point and pause your program for a very long time. The point where that happens is not predictable, and the amount of time it will take is also not (usefully) predictable -- we can't even assign a stochastic model to it.

We can't really call the garbage collector random, as it might be triggered by some sequence of events that is in principle deterministic but is in practice too complex to model and thus is for all engineering purposes unpredictable. You might be tempted to say "treat the time when garbage collection happens as random and uniformly distributed", but that's not valid. For all we know, the garbage collector might kick in at the worst possible time. Maybe there is some code that does a bunch of stuff (e.g., creating lots of short-lived objects and then immediately destroying all references to them) that tends to trigger the garbage collector, right before some other code that does something really time-critical (e.g., update flight control surfaces). If you modelled the time of garbage collection as random, you would fail to recognize that the flight-control code might systematically fail at a higher probability than your stochastic model predicts. All we can safely do is assume conservatively that the garbage collector might run at the worst possible time, and take essentially forever to do its job. That renders worst-case execution time analysis impossible or unhelpful.

Similarly comments can be made about many other elements that make running time analysis hard, such as interrupts, caches, speculative execution, and so on.

---
Tags: reference-request, operating-systems, randomness
---


# Question
Title: Algorithm for weighted elliptic curve fit
**Background:** I was trying to detect a face solely on the bases of features and the confidence of the features found. I am using a method to identify the features along with the response (confidence). Stronger features have higher responses. I was trying to identify rotations of face. So, I was thinking about using ellipse bound to identify single face from image.

**Question:** Is there any standard algorithm/standard library that does weighted elliptic curve fit for all the points?

(Mostly, the points would be in and around the ellipse with weights. However, there may be outliers. All points will have to be considered. The outliers will have less weight though.)

Inputs to the algorithm: coordinates of the points and the weights of the points.

Expected output from the algorithm: Minor axis, major axis, 2D orientation angle and the centre of the ellipse (using weighted curve fitting).

If there are 'n' number of features, I could calculate the centre of ellipse using the weighted average of features. But, how would I determine minor axis, major axis and the rotation of the ellipse?

**Attempts:** I tried with circle and it works very well. But, it does not have rotational information (it just draws a circle when face is rotated). I found literature survey about elliptical curve fits using iterative methods. I also ideated that rectangular curve fit would also do (as length of the rectangle can be major axis of ellipse and breadth of rectangle can be minor axis of ellipse).

But, I have been unable to observe any 'universal' solution. (For example, if the face is far from the camera, ellipse should be smaller accordingly. Many curve fitting algorithms use parameters which are translation variant)

**Images for unweighted and weighted curve fitting:**

Unweighted elliptical curve fitting would be as shown in left. It would probably just use least mean square fitting (with iterations for angles). But, this method is not desired as it would not account for the importance of features (for example, a feature of a shirt in an image would be "less important" than the one on face. Hard thresholding or binarising destroys information). Desired weighted elliptic curve fitting is as shown in right.

# Answer
> 0 votes
Fitting an ellipse to a set of points is sometimes known as elliptical regression. Doing a Google search on that phrase will find you many resources on the subject (e.g., , , etc.; I can't vouch for any of these).

Let's focus first on the case where you ignore outliers. Then, there are two methods. One way is to use least-squares fitting and directly compute a best fit (e.g., the method of Fitzgibbon et al). An alternative method is to use iterative methods, where you write an objective function $\Phi(p)$ that captures how well the ellipse parameters $p$ fit the data and then use gradient descent, the Gauss-Newton method, or some other method of optimization. See, e.g., the Levenberg-Marquardt algorithm.

You'll also need to decide on objective function, or equivalently, on the error model. Standard methods typically measure the "goodness of fit" by measuring the vertical error: for each point, you measure the length of the vertical line from that point to the fitted ellipse, and that is the error associated with that point; then, you sum up the squares of those errors. This is the right model if you think that your measurement of the $x$-coordinate is perfect and your measurement of the $y$-coordinate is corrupted by random errors. However, in practice that's probably often not the case; rather, we probably think that the location of the point has been shifted from the ellipse in a random direction. In that case, a better measure of "goodness of fit" would be to measure the distance from the point to the ellipse (in whatever direction makes that distance minimized; not restricting only to a vertical distance), and then take the sum of those squared distances. This does require you to use iterative methods to minimize this objective function. A similar issue arises in linear regression (see here) and it might be easier to understand in that scenario first.

OK, that should handle the case where you have no outliers. What if you do have outliers? Then there are multiple reasonable approaches. One is to use an objective function that is robust to outliers: for instance, use the median of the squared distances rather than the sum of squared distances, or use the Huber loss function instead of the square. The downside of these methods is that they make it harder to compute the gradient and thus harder to apply iterative methods (and the non-iterative methods probably can't be used at all).

An alternative way to deal with outliers is to use RANSAC, which is a general procedure for dealing with outliers. An overview is that you pick a small random sample of the points, hope that the random sample has no outliers, tentatively fit an ellipse to the sample, use the tentative ellipse to classify the points into inliers vs outliers based on how far they are from the tentative ellipse, then fit a new ellipse to all the inliers; and repeat 1000 times with 1000 different random samples, taking the best solution found. This is a generic method for dealing with outliers that has the advantage of being usable with existing non-robust methods for elliptical regression. You don't need to modify the loss function, objective function, or algorithm at all, since you are only applying elliptical regression to inliers, so you can use any method for elliptical regression without needing it to be robust to outliers.

---
Tags: algorithms, image-processing, mathematical-programming, video
---


# Question
Title: Given a number, getting a grid position in a spiral pattern
```
+---------------+---------------+---------------+---------------+---------------+
| id:  20       | id:  19       | id:  18       | id:  17       | id:  16       |
| pos: (-2, -2) | pos: (-1, -2) | pos: (0, -2)  | pos: (1, -2)  | pos: (2, -2)  |
+---------------+---------------+---------------+---------------+---------------+
| id:  21       | id:  6        | id:  5        | id:  4        | id:  15       |
| pos: (-2, -1) | pos: (-1, -1) | pos: (0, -1)  | pos: (1, -1)  | pos: (2, -1)  |
+---------------+---------------+---------------+---------------+---------------+
| id:  22       | id:  7        | id:  0        | id:  3        | id:  14       |
| pos: (-2, 0)  | pos: (-1, 0)  | pos: (0, 0)   | pos: (1, 0)   | pos: (2, 0)   |
+---------------+---------------+---------------+---------------+---------------+
| id:  23       | id:  8        | id:  1        | id:  2        | id:  13       |
| pos: (-2, 1)  | pos: (-1, 1)  | pos: (0, 1)   | pos: (1, 1)   | pos: (2, 1)   |
+---------------+---------------+---------------+---------------+---------------+
| id:  24       | id:  9        | id:  10       | id:  11       | id:  12       |
| pos: (-2, 2)  | pos: (-1, 2)  | pos: (0, 2)   | pos: (1, 2)   | pos: (2, 2)   |
+---------------+---------------+---------------+---------------+---------------+

```

Given a grid, starting at the center and spiraling out like the above. I'm trying to find an algorithm that given an `id` returns a `pos`. Is there an algorithm that works like this? I don't want to use a lookup table or anything like that as the grid could be any size.

# Answer
I'll give a hint by breaking down the problem into nice looking components. I'll leave it to you to implement the components and use them yourself.

1) A function from `id` to the `ring number` it is in. For example,

* `id` 0 is in the 0th ring.
* `id` 1,2,3,4,5,6,7,8 is in the 1st ring.

2) A function from `ring number` to the last `id` of the ring. For example,

* 0th ring's last `id` is 0
* 1st ring's last `id` is 8
* 2nd ring's last `id` is 24

3) A function from `ring number` to the last `pos` of the ring. For example,

* 0th ring's last `pos` is (0,0)
* 1st ring's last `pos` is (-1,1)
* 2nd ring's last `pos` is (-2,2)

4) A function from `id` to the `increment of pos` to reach the next `id`. Let's call this function $g$. For example,

* $g(10) = (1,0)$
* $g(20) = (0,-1)$

It has to do with what part of the ring the `id` is in.

Hopefully, this has structured the problem in a way you can see the solution easier by yourself.
> 2 votes

# Answer
My javascript implementation...

```
function getRing (id) {
 return Math.ceil((Math.sqrt(id + 1) - 1) / 2);
}

function getMinRingID (r) {
 if (r == 0) {
   return 0;
 }
 return Math.pow((2 * (r - 1) + 1), 2);
}

function getRingLegFromID (id) {
 if (id == 0) {
   return 0;
 }

 var r = getRing(id);
 var m = getMinRingID(r);
 if (id >= m && id < m + (2 * r)) {
   return 0;
 } else if (id >=  m + (2 * r) && id <  m + (4 * r)) {
   return 1;
 } else if (id >=  m + (4 * r) && id <  m + (6 * r)) {
   return 2;
 } else if (id >=  m + (6 * r)) {
   return 3;
 }
}

```

With the above basics, you can get the position with...

```
function getPos (id) {
 var ring = getRing(id);
 var min = getMinRingID(ring);
 var leg = getRingLegFromID(id);

 if (id === 0) {
   return [0, 0];
 }

 switch (leg) {
   case 0:
     return [-ring + ((id - min) + 1), ring];
     break;
   case 1:
     return [ring, ring - ((id - min) - ((2 * ring) - 1))];
     break;
   case 2:
     return [ring - ((id - min) - ((4 * ring) - 1)), -ring];
     break;
   case 3:
     return [-ring, -ring + ((id - min) - ((6 * ring) - 1))];
     break;
 }
}

```

The test...

```
for (var id = 0; id < 49; id ++) {
 var ring = getRing(id);
 var min = getMinRingID(ring);
 var leg = getRingLegFromID(id);
 var pos = getPos(id);

 console.log('id = ' + id + '; ring = ' + ring + '; leg = ' + leg + '; pos = ' + pos);
}

```
> 0 votes

---
Tags: algorithms
---


# Question
Title: Algorithm to find a shortest past under a special condition
I am trying to come up with an algorithm that calculates the length of shortest rectangle movement in a given bitmap.

For example, let's say we have a 24x24 bitmap where 1 is black pixel and 0 is a white pixel.

```
{{0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,1,1,1,0,0,1,0,1,1,1,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,0,0,1,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,1,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,1,1},
 {0,1,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0},
 {1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,0},
 {0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
 {0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1},
 {0,0,0,0,0,1,0,0,0,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0},
 {0,0,1,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,1,0,0,0,0},
 {0,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,0,0,1,0,0,0,0,0},
 {0,1,0,0,0,0,0,0,1,0,0,0,1,1,1,1,0,0,1,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0},
 {1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0,0,0,0,1},
 {0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,0},
 {0,0,1,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,0,0,0,0,0,0},
 {0,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0},
 {0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,1,0,0,0,1,0,0,0,0}}

```

This game is played on an n x n map of black/white pixels and the player moves a rectangle through this map. In the player's rectangle movement, it should not contain a black pixel. In a single rectangle movement, the player can replace the current rectangle r with any rectangle r2 that either contains r or is contained in r.

Initially, the player starts at the upper-left corner and tries to reach the bottom right pixel.

Under this condition, I am trying to find an algorithm to get the shortest rectangular move needed to reach the bottom right corner.

The input of the algorithm that I am using will be the `map[n,n]` which just looks like the bitmap above.

What is a good approach, or a good way to think about this problem?

# Answer
> 1 votes
Use a pathfinding algorithm, such as BFS, A\*, or some other suitable algorithm. Here each rectangle is treated as a vertex of the graph, and you imagine an edge from rectangle r1 to rectangle r2 if that's an allowed move (if you currently have rectangle r1, you can get to r2 in a single step).

Think of the rectangle as the "state" of the system at any point in time. When you want to explore the statespace of a system, pathfinding algorithms are often worth a try.

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


# Question
Title: Algorithm: Shortest path (walk) with keys and doors
I'm trying to solve the following algorithm question:

> A maze is given by a graph (with let's say $v$ vertices and $e$ edges), where $k$ vertices are different keys and, $k$ vertices are the corresponding doors (there is always one key for a single door) and one vertex is the end of the maze. Find the shortest path (it's actually a walk because it makes sense to move back after a key is found) from a given vertex to the end.

*I should note that it is a homework for a class, where only DFS and BFS graph traversing algorithms were used so far, so it should be possible to solve this using only these two algorithms to search the graph.*

**My approach so far:**

I've tried a recursive DFS (to better keep track of the current path and all the keys found on it) with a concept of multiple levels of "found vertices" - when a key is found, the previously found vertices are saved for later use, but at current iterations, it continues as if no vertices were found. When the current recursive call ends, the algorithm moves back a few vertices, when it removes a key it gets back to the previous level of found vertices.

This algorithm should be possible to use but I found it quite hard to figure out the asymptotic time complexity.

Then I realized that it could be simplified. First, do a BFS from the start node (that's $O(v+e)$), get the shortest paths to the keys and to the end and make a new graph of these shortest paths. Then do a BFS again from the first key (some doors could have opened, so it makes sense to search it all over again), get the shortest paths to all other keys and to the end and add these to the graph. **Continue for the rest of the keys**. At the end do a BFS on the new graph again.

The problem is with the "Continue for the rest of the keys" part, as there are $k!$ ways to collect the keys in different orders, and the new graph would have something like $1+k+k(k-1)+\cdots+k!+k!$ vertices.

---

**Is there any way not to check all the possible permutations?** It seems to me, that you can never know, whether there is a possibility of a better path before collecting the keys in a different order.

---

## Update

After submitting the solution, the teacher said, that $k$ was meant as a constant, not the input, so the goal was to minimize the time complexity relative to $v$ and $e$ after all.

# Answer
This other question about mazes is closely related. It deals with the simpler problem of having to collect each of the items before leaving the maze. One can make the analogy that there is a single door at the end of the maze, but it has a very complicated lock and you must collect all the keys to get through it.

The complexity depends on the structure of the maze. In particular, my answer to the other question proves that, if the maze is a general graph, the collect-all-the-items version of the problem is **NP**-complete and, in fact, the same holds for planar graphs. This means that your problem is also **NP**-complete on general (or planar) graphs. Here's a sketch of the reduction. You simulate the door with the complicated lock by replacing the exit to the maze with a very long passage that ends with the $k$ doors one after another. You make the passage long enough that the optimal solution is definitely to collect all the keys first and then walk down that passage and unlock the doors, because walking back and forth between keys and doors would simply be too long. Now the hardness of the collect-all-the-items problem implies that your problem is hard, too.

If your maze is a tree, the problem might be easier – the collect-all-the-items version has a polynomial-time algorithm in that case. And, in any case, the more general problem being **NP**-complete doesn't mean there aren't more efficient algorithms than brute force: but it does mean you shouldn't expect a polynomial-time algorithm.
> 5 votes

# Answer
It is a homework, so I will not give a full answer.

The update (that $k$ is a constant) is the key to an efficient algorithm.

Suppose further, that the order in which the keys are collected is fixed. Then you have to find a path from the start to the first key, from there to the second key, from there to the third key and so on. Doors may olny be passed in path segment which occur after collecting the respective key.

Try to find an algorithm for that further restriction, then solve the general case.
> 1 votes

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


# Question
Title: Is the set of all Context free languages a Context sensitive Language? ( can we build a LBA that decides whether a given language is CFL or not?)
What i mean is that can we code each CFL ( the same way we code each turing machine in the Universal Turing Machine ) and build a Linear bounded Automata in such a way that for each input ( which is a code of a particular CFL) decides whether this is a context free language ( accept ) or not?

I hope my question makes sense or maybe I'm confused, because i know that set of all regular expressions(regular languages) is a Context sensitive language because we can make a context sensitive grammar for it so i was wondering what can we say about the set of all context free languages?

# Answer
> 2 votes
If you consider a grammar $(N, \Sigma, P, S)$ you could actually give a regular expression for the production rules $P$, which pretty much determines the whole grammar: $$r = S \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast (, \bar{N} \to (\bar{N} + \bar{\Sigma})^\ast (| (\bar{N} + \bar{\Sigma})^\ast)^\ast)^\ast$$ over the alphabet $N \cup \Sigma \cup \\{,, |, \to\\}$, where we use the $\bar{N}, \bar{\Sigma}$ as shortcuts for $\sum\_{A \in N} A$ and $\sum\_{a \in \Sigma} a$.

So you could pass the grammar (the "code" of the CFL) to a finite automaton to check whether it is a context-free-grammar.

Basically, you just have to check whether there is only one single non-terminal in front of a $\to$. There is no nesting in context-free grammars in contrast to regular expressions.

---
Tags: formal-languages, turing-machines, automata, context-free
---


# Question
Title: The minimum number of bits required for an instruction
For a computer architecture, called ComputerA, a MIPS-like instruction set will be used. 64 instructions are reserved for R-type instructions and 64 more instructions are reserved for I-type and J-type instructions in total. Also, there are 128 registers in the system and the size of one register is 64 bits. According to the given configurations, what would be the minimum number of bits required for an instruction in ComputerA? Note that, In MIPS, opcode of the all R-type instructions will be 0 (zero). The arithmetic operation is selected according to the function code (funct). MIPS is a RISC instruction set, therefore its instruction length is fixed.

# Answer
> 1 votes
Naively, as you have 128 registers, that means 7-bit register fields.

We would expect that a processor described as MIPS-style RISC, would have R type instructions with 3 register operands. Thus, an R type instruction would use 3 (register operands) x 7 (bits per register operand) or 21 bits total for the 3 operands. That leaves 11 bits for opcode (2048 values) — assuming 32-bit fixed sized instructions.

2048 is not a lot of opcode space, if you realize that the opcode field must also be shared by I type and J type instructions as well, plus coprocessor instructions that work on floating point, plus other instruction set extensions like vector operations.

One advantage that the x86/x64 instruction set have with their variable length encodings is a practically infinite ability to extend the instruction set with more opcodes. This has been used to great advantage over the long history of the ISA, for example, with SIMD instruction extensions, such as with SSE & AVX.

Thought the x86 went through a number of major architectural changes (808x, 386, x64), I think it would have been interesting and somewhat more challenging for a RISC architecture to be similarly extended and re-extended over 40+ years.

Using a MIPS fixed instruction size, you will probably want to relax that a bit to allow for 32-bit and 64-bit instructions, for long term extensibility.

Also, there is often a need for 4 operand instructions (e.g. fused multiply add, and also some vector instructions). 4 x 7 = 28, meaning you need 28 bits to describe 4 register operands, and that means there is no room left for a realistic opcode. 4 operands of 7 bits wide is only be practical in a larger (e.g. 64-bit) instruction.

So, in summary, given 128 registers, I'd support both 32-bit and 64-bit instructions from the start. Then encode the most common instructions in 32-bits using 11 bit opcode field and 3x7-bit register fields, while allowing some of the 11-bit opcode space to describe 64-bit instructions.

---

What you're doing with 128 registers is a trade off that makes certain complex algorithms work well at the cost of extra space required to encode simpler algorithms. A smaller number of registers (e.g. 32 as in MIPS) means less registers for complex algorithms, but less bits (3x5=15 vs 3x7=21) required for encoding simpler algorithms into instructions.

All instruction sets have this trade off. Stack-oriented instruction sets generally are the most compact, and compactness translates into better instruction cache utilization. However, they require more effort in execution since the same software algorithm encodes into more instructions (not to mention the variable length nature of the instructions).

See also this question for a discussion comparing various kinds of instruction set styles in the context of an add instruction.

---
Tags: computer-architecture
---


# Question
Title: Search algorithm that returns the lowest cost path to one, of many possible goal nodes?
I am working on a problem where I have a set of goal nodes of which some, all, or none of will appear in a search tree.

***Is there a search algorithm which returns the lowest cost path to one goal node, when there are potentially many different goal nodes present in a tree, or failure?***

This can obviously be solved by iterating through the set of goal nodes and applying a search algorithm on each of the goals and then comparing the paths to find the lowest cost path, but I would like know if there is a more elegant solution.

Thanks

# Answer
> 1 votes
Yes, any of the standard search algorithms will do that.

You seem to be under the misapprehension that search algorithms stop "when they reach node $x$." They don't: they stop when they reach a node with any property you tell them to use. That property could be "node $x$", or "any node in $x\_1, \dots, x\_k$", or "any node with score more than $10$" or any other condition you choose.

---
Tags: graphs
---


title: Complexity for nested #P?

text:
# Question
Title: Complexity for nested #P?
Consider a problem such as weighted model counting for propositional logic. The problem of enumerating all models `M` of a logic formula `f` and summing their weights `w(M)` is #P. What happens if the weight is a function of the model and the task of computing the weight `w(M)` given M is in itself #P? Whats the complexity of the total problem?

# Answer
> 2 votes
The result is in #P. Suppose there are 50 states, and each state has 10 cities. Then how many cities are there in total?

Now suppose we have a polytime verifier for states: $S(x)$ outputs 1 iff $x$ is a state. We also have a polytime verifier for cities: $C(x,y)$ outputs 1 iff $y$ is a city in state $x$. Then counting the number of states is in #P: it's the number of $x$ such that $S(x)=1$. If you think a bit, you can see that counting the number of cities is also in #P: it's the number of pairs $(x,y)$ such that $S(x)=1 \land C(x,y)=1$. Can you come up with a polytime verifier $V$ such that $V(x,y)=1$ iff $x$ is a state and $y$ is a cities in that state? I bet you can. Consequently, counting the number of such pairs (i.e., counting the number of cities) is in #P.

Now apply the same idea to your problem, and you should be able to figure out the answer.

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


# Question
Title: Can the turing machine accept these type of languages in O(n)? or better? $L = \{a^n b^n c^n ... d^n | n > 0\}$
$L = \\{a^n b^n c^n ... d^n | n\>0 \\}$

so for example $L = \\{a^n b^n | n\>0 \\}$ , $L = \\{a^n b^n c^n| n\>0 \\}$ and such

can the turing machine accept these in O(n)? if yes then what about a better time complexity like O(logn) or O(1)?

my take on this is: yes because we can use n number of tapes and we go through all of them word by word altogether, but a book i was reading said the best time is $O(n^2)$ so i got confused, maybe it was referring to standard turing machine but idk

so my question is this :

1. can a turing machine do this in O(n) ?
2. if yes, then is there a better time complexity?

# Answer
> 4 votes
Yes a TM with multiple head for example can easily do this. for $a^nb^n$ you can have two heads one at the first occurence of A's and other at the first occurence of B. Then at each iteration you can cross each off. If both see blank accept. If A head does not see A or B head does not see a B reject. Else cross both off with some special character.

Clearly this takes one linear pass in time O(N). Now for the lower bound. It is not possible to do with less than O(N). If you use N number of tapes by definition then it is $\Omega{(N)}$. If you use K number of tapes then it is $K \times (N/K)$ which is still O(N). The reason for this lower bound is that you have check each character since any one character can break the rule of this language. Thus we get a linear lower bound.

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: Counting $k$-Colorings $\mathcal{O}(\phi^{n + m})$ Solution
Given an undirected graph $G = (V, E)$ with $n$ vertices and $m$ edges, how many $k$-colorings of $G$ exist? A $k$-coloring is a function $c: V \to \\{ 1, 2, \dots, k \\}$ such that $c(u) \neq c(v)$ for all edges $\\{ u, v \\} \in E$. Let $f(G, k)$ denote the number of $k$-colorings of $G$.

There is a well-known formula, sometimes called *Fundamental Reduction Theorem*:

$\displaystyle f(G, k) = f(G - e, k) - f(G\\,/\\, e, k)$ for all $e \in E$.

Note that $G - e$ is $G$ without edge $e$ and $G\\,/\\,e$ is $G$ with edge $e$ contracted.

Using this formula, it is easy to figure out a recursive algorithm. We just need to choose an arbitrary edge and recurse on $G - e$ and $G\\,/\\, e$. The base case is a graph without edges. If $T(n + m)$ denotes the time complexity, we have $T(n + m) \le T(n + m - 1) + T(n + m - 2)$ which is just fibonacci recurrence and establishes a time complexity of $\mathcal{O}(\phi^{n + m})$ where $\displaystyle \phi = \frac{1 + \sqrt{5}}{2}$ denotes the golden ratio. So far, so good.

But we made an assumption: Can $G - e$ and $G\\,/\\,e$ really be obtained from $G$ in $\mathcal{O}(1)$ time? It seems like we cannot avoid a polynomial factor:

* If $G$ is represented by an adjacency matrix, vertex removal (needed for contraction) does not shrink the matrix and we always need $\mathcal{O}(n)$ time to access the edges of a single vertex. And another problem: How to select an arbitrary edge fast?
* If $G$ is represented by adjacency lists, edge removal is fast. But edge contraction requires moving/copying neighbour vertices to another adjacency lists which is expensive.
* If $G$ is represented by an edge list, edge selecting is fast. Edge removal is also fast, because the edge is arbitrary and we can always take the first edge in the list. But again, edge contraction causes many edges to be updated (i.e. assigned another endpoint)...

Is there a way to really achieve $\mathcal{O}(\phi^{n + m})$ without a factor of $n$, $m$ or $n + m$ using an appropiate data structure or modification of the algorithm?

# Answer
> 1 votes
Use an adjacency list representation, together with a Union-Find data structure on the vertices. Augment the Union-Find data structure so you can quickly enumerate the list of all edges incident on any vertex within a particular partition (you can keep track of them with a doubly linked list, and splice the lists together whenever you do a Union operation). Now edge contraction can be done in $O(\alpha(n))$ time, by simply doing a Union operation on the two vertices. Edge removal can be done in $O(1)$ time, due to the adjacency list representation. You can also find an arbitrary edge in $O(1)$ time, thanks to the augmentation of the Union-Find data structure.

This avoids the factor of $n$. You still pay a factor of $O(\alpha(n))$ instead of $O(1)$, but $O(\alpha(n))$ is so small that it might as well be $O(1)$ for all practical purposes, and in any case it is far smaller than $n$.

Actually, I think you pay more than that, because you'll need to undo the Union operations after returning from the recursive call. To deal with that, you can use a persistent Union-Find data structure. I'm not familiar with the asymptotic running time for those data structures, but I think given how it is used here it will be pretty close to as efficient as the plain Union-Find.

Usually we don't worry too much about polynomial factors when analyzing exponential-time algorithms, because the polynomial factor is tiny compared to the exponential factor, so a polynomial speedup won't change much in practice. But here is a case where the polynomial speedup you desired can be achieved.

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


# Question
Title: Is {a^n (a+b)^n | n>0} a Deterministic CFL?
$L = \\{ a^n (a+b)^n | n\>0\\}$

A book I'm reading says it is, but considering we can't know where the second part gonna start, and it might start with a as well, then how can we accept this using a DPDA? Like after reading the first part ($a^n$) how can we be sure that it's the end of the first part or not considering the second part can also start with $a? $

Is this Deterministic?

# Answer
You needn't determine the end of "first part".

Note $L$ is exactly the set of strings satisfying the following three constraints:

1. Its length is even.
2. It only contains $a$ and $b$.
3. The first $b$ appears in its latter half.

Constraints 1 and 2 are easy to check. To check constraint 3, the DPDA can push a symbol to its stack each time it reads a character until the first $b$ appears (excluding), and then pop a symbol each time it reads a character. Constraint 3 is satisfied if and only if the initial stack symbol is never read during the popping process.
> 11 votes

# Answer
In case it's clearer, here's a CFG corresponding to xskxzr's DPDA:

$$\begin{align} S&\to \epsilon \\ S&\to B \\ S&\to a a S \\ B&\to a b \\ B&\to a B a \\ B&\to a B b \\ \end{align} $$

The slightly simpler CFG below is ambiguous for inputs consisting only of an even number of $a$s, but it still works with the LALR(1) algorithm using the "standard" conflict resolution algorithm: "in case of ambiguity, shift":

$$\begin{align} S&\to B \\ S&\to a a S \\ B&\to \epsilon \\ B&\to a B a \\ B&\to a B b \\ \end{align} $$
> 4 votes

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


# Question
Title: SAT Solver Front-End: Strategy to order Quantifiers
I am working on a small project. The goal is to implement a compiler from a quite simple, custom syntax of logical formulae (including variables over finite domains) to conjunctive normal form (CNF). The compiler should for every formula $\varphi$ from the custom language produce a standard propositional formula in conjunctive normal form (CNF), $\text{cnf}(\varphi)$.

Desiderata:

* The size of $\text{cnf}(\varphi)$ should be as small as possible compared to the size of $\varphi$.
* The two formulae $\text{cnf}(\varphi)$ and $\varphi$ should be equisatisfiable.
* For every model of $\text{cnf}(\varphi)$ it should be possible to construct a model of $\varphi$. I am not entirely sure whether that is the correct term, but I would consider the models of $\text{cnf}(\varphi)$ *conservative extensions* of $\varphi$. The algorithm outlined below ensures this.

## Input

The input contains the usual logical connectives, terms as constants and terms as integers (with some arithmetic). Further, it may contain universal and existential quantifications of the following form:

```
(forall $x in {a, b} (exists $y in {$x, c} (p($x,$y))))

```

As you can see, variables are associated with (finite) domains. A semantically equivalent ground formula in this case would be:

```
((p(a,a) | p(a,c)) & (p(b,b) | p(b,c)))

```

A more complex example which encodes the "subgrid constraint" of sudoku:

```
(forall #d in [0...8]
    (forall #ro in [0...2]
        (forall #co in [0...2]
            (forall #i in [0...7]
                (forall #i1 in [#i+1...8]
                    (
                        v(((3*#ro) + (#i/3)), ((3*#co) + (#i%3)), #d)
                        ->
                        ~v(((3*#ro) + (#i1/3)), ((3*#co) + (#i1%3)), #d)
                    )
                )
            )
        )
    )
)

```

## Conversion Algorithm

The conversion algorithm that I have implemented currently is as follows:

1. Replace all connectives with `|` (logical or) and `&` (logical and), and "push down" negation towards atoms. This yields a formula using only the two basic connectives in negation normal form (NNF).
2. Standardize variables apart, i.e. make sure that no two quantifications use the same variable name, globally.
3. "Pull out" the quantifiers, which yields a formula in prenex normal form (PNF), where the matrix is in negation normal form.
4. Expand universal quantifications into conjunctions and existential quantifications into disjunctions, to get a ground formula.
5. If the result of (4.) is in CNF, return it. Otherwise, apply Tseitin's transformation, to get a formula in CNF.

## Issues and Question

I initially introduced step (3.) in order to be in a position to optimize the ordering of quantifiers in the matrix of the formula. Ideally, universal quantifiers should be "left" and existential quantifiers should be "right" in order to directly expand to CNF. There are some dependencies between quantifiers that prevent moving them over each other, but I think I got those conditions covered.

However, by introducing (3.) some of my test instances exploded. Since the connection between a quantifier and its scope is completely lost in step (3.), inevitably step (4.) will generate a huge cross product over all possible variable substitutions for all quantifiers, and for each of those, the whole formula will be ground and duplicated. This is clearly the wrong approach.

From here, I thought that it would be a good idea to go the other way and actually try to push quantifiers down, in order to minimize their scope. Then, for any clusters of quantifiers that are immediately next to each other in the formula, their order can be optimized.

My question is whether I am missing some trick that could help me, and especially what is the best (known) approach to reorder/move quantifiers. I found quite some information about QBF solving, but that does not help me much.

Edit: Since I asked this question I changed my approach. It turned out that targeting Prenex Normal Form actually was a very bad idea, since then the scope of all quantifiers is at least the size of the whole formula (except quantifiers). This just explodes. So instead of "pulling out" in step (3.) I now "push down" the quantifiers with the goal of minimizing their scope. If two quantifiers are then "next" to each other, I try to move universal quantifiers to the left and existenstial quantifiers to the right, since this way the expansion will be closer to CNF.

# Answer
I don't think there is any way to compile efficiently to SAT. That's because your problem is (or contains) QBF, and QBF is believed to be harder than SAT: QBF is PSPACE-complete, whereas SAT is NP-complete, and it is widely believed that PSPACE != NP. If you found an efficient and general way to compile QBF formulas to SAT, then you would have proven PSPACE = NP, which seems unlikely.

What does your problem have to do with QBF? Well, we imagine that we restrict your formulas so they are over not just a finite domain, but a domain of size two. Moreover, we get rid of all integers. Then every variable is boolean, and you have boolean formula with quantifiers -- i.e., an instance of QBF.

Fortunately, there are QBF solvers. Unfortunately, they are significantly slower than SAT solvers. In any case, it looks like you should be using (or compiling to) a QBF solver, rather than a SAT solver. (If you're lucky, and there are only two alternating quantifiers, then your problem becomes 2QBF, which is considerably easier than QBF.)
> 3 votes

---
Tags: logic, compilers, satisfiability
---


# Question
Title: Doubt regarding binary trees and counting
**Question:**

A binary Tree T is semi-balanced, if for every node m in T: $$ \frac{R(m)}{2} \<= L(m) \<= 2\*R(m) $$ where, L(m) is the number of nodes in the left sub-tree of m and

R(m) is the number of nodes in the right sub-tree of m.

Write a recurrence relation to count the number of semi-balanced binary trees with N nodes.

**My Attempt:**

Let T(N) denote the number of semi-balanced trees with N nodes.

For N = 1, T(N) = 1 (Trivial)

For N \> 1, T(N) can be found by splitting N into 3 parts, a root, a left subtree and a right subtree, let M be the number of nodes in the left portion, then the N - M - 1 is the number of nodes in the right portion, so by the constraint in the question,

$$ \frac{N-1}{3} \<= M \<= \frac{2\*(N-1)}{3} $$

So for N \> 1,$$ T(N) = \sum\_{M=\frac{N-1}{3}}^{\frac{2\*(N-1)}{3}} T(M) * T(N-M-1) $$

**However, the answer is given as,**$$ T(N) = \sum\_{M=\frac{N-1}{3}}^{\frac{2\*(N-1)}{3}} 2 * T(M) * T(N-M-1) $$

Why is there a factor of 2 in the solution?

# Answer
> 0 votes
I think your answer is correct. Without bothering with recursive relations, we can observe that the only semi-balanced binary trees are perfect trees.

In fact, the only semi-balanced binary trees of heights $1$ and $2$ respectively are perfect (obvious for height $1$, casework for height $2$). Now, assume by inductive hypothesis that all semi-balanced binary trees of height at most $n$ are perfect trees. By definition, the root of a semi-balanced binary tree of height $n+1$ must have two semi-balanced subtrees as children, one of which has height $n$. By inductive hypothesis, that subtree is exactly the perfect binary tree of height $n$. By inductive hypothesis and definition of semi-balanced binary tree, the other subtree must therefore be too the perfect binary tree of height $n$, which completes the proof.

We can see that for e.g. $N=7$ the presence of a factor $2$ yields a wrong answer.

Nitpicky thing: you should take the upper integer part of the lower limit of the sum, and the lower integer part of the upper limit.

---
Tags: recurrence-relation, binary-trees
---


# Question
Title: Can we convert any given turing machine to a turing machine with only 2 states? if so, how?
So i remember reading somewhere that we can convert any turing machine into a turing machine with 2 states (or 3, i don't remember) but there was no proof for it and i couldn't find it either

So my question is :

For every turing machine, what is the minimum number of states that we can have after converting it to this minimal state turing machine?

and what is the properties of this turing machine that we have converted our original turing machine to?is this a standard turing machine or we do this by increasing the number of tapes or...? ( how is this possible?)

What i mean by convert is build a Turing machine which accepts the same language but only with 2 or 3 states

# Answer
Ariel's answer shows that you cannot fix the number of states if the tape alphabet is constant. There are two ways out:

* Allow the Turing machine access to a "hint" written on an auxiliary tape. You can then use a universal Turing machine with a fixed number of states, which gets as auxiliary input the description of another Turing machine that it executes.
* Allow the tape alphabet to be arbitrary. You can then simulate the auxiliary tape, that is, you can design a Turing machine with a fixed number of states that first writes on a tape the description of another Turing machine, and then switches over to a universal Turing machine that executes it.

In the second case, the tape alphabet is still finite, but its size depends on the machine. This allows us to use a bina fide Turing machine with a fixed number of states but with an unbounded description length, thus bypassing the limitation presented in Ariel's answer.

Whether you can do it with N states could depend on the exact semantics of your Turing machine, but in both cases you should be able to make do with some constant N.
> 3 votes

# Answer
You can't always find an equivalent Turing machine (in the sense that it has the same language) having less than $N$ states.

Note that the semantics of a Turing machine is determined by its states and transition function. After fixing the alphabet, to fully describe a machine you only need to specify how it reacts to every symbol from every state. This description has length of $O(|Q|\log |Q|)$. Thus, if you bound the number of states by some constant $N$, then there's only a finite number of different machines ($\sim N^N)$, which means that not every decidable language has an equivalent machine in this set.
> 4 votes

---
Tags: formal-languages, turing-machines, automata
---


# Question
Title: Reduce ATM to the language of TM encodings concatenated by a string where the TM accepts both the string and its reverse
Prove that the language $LM =\\{\langle M,x\rangle\mid \ M \text{ accepts }x\text{ and rev}(x) \\}$, where $\mathrm{rev}(x)$ is the reverse of the string $x$, is undecidable with a reduction from $A\_{\mathrm{TM}}$. Note that the empty string belongs to $LM$.

# Answer
> 0 votes
# Hint

Forget the similarity between $LM$ and $A\_{\mathrm{TM}}$, and for an input $\langle M,x\rangle$ of the reduction, try to build a **new** TM $N$ such that $M$ accepts $x$ if and only if $N$ accepts $0$, i.e. $\langle N,0\rangle\in LM$.

# Complete answer

> Given $\langle M,x\rangle$, build a TM $N\_{M,x}$ that on any input always simulates $M$ on $x$. Therefore if $M$ accepts $x$, $N\_{M,x}$ accepts everything, otherwise $N\_{M,x}$ rejects anything. Now we can see $M$ accepts $x$ if and only if $N\_{M,x}$ accepts $0$, i.e. $\langle N\_{M,x},0\rangle\in LM$. All above completes the reduction.

---
Tags: turing-machines, reductions, undecidability
---