# Question
Title: Online set cover variant? Routing of requests
We have a set of $k$ path requests from $src$ to $dst$ that arrive sequentially.

Each request may have multiple paths, but can choose only *one* of them. For example, in the Figure shown, there are two paths from $s1$ to $s4$ i.e., path1 : $s1-s2-s3-s4$ and path 2: $s1-s5-s6-s4$.

Further, each node on the path has an associated table that records entries. When a path is chosen, an entry *may* or *may not* be added to each node on the path. Whether an entry is added or not depends on the nature of the request, but that is not relevant here. Also, the node tables are independent of each other.

Each table has a limit on the number of entries. Suppose each table can hold a maximum of $n$ entries. When a table is full, that node cannot be chosen on any path. The blue boxes in the figure represent the percent full of each table. The node $s3$ is more utilised than the other nodes. If $s3$ becomes full, the path $s1-s2-s3-s4$ cannot be used to route any more requests.

Now, the challenge is to route the maximum number of requests, as they arrive sequentially. Here is what I have so far.

* Heuristic 1: Choose the path with the least *total* new table entries added. Using this heuristic, however, can lead to non-uniform utilisation of the tables. Suppose that on the $s1-s2-s3-s4$ path, entries are added only at $s3$. And using the other path, entries are added at $s1$, $s5$, and $s6$. Heuristic 1 will choose path 1, but this may lead to faster fill-up of $s3$ and path1 cannot be used to route more requests.
* Heuristic 2: Choose a cost function for each node based on a) cost to add new entry and b) percentage utilisation of table. Then choose the path with least *total* cost.

Let us define the cost metric as $ cost\_{node} = cost\_{new\\;entry} + \frac{|existing\\;entries|}{n}$

Using this heuristic, path 2 will be chosen, given the conditions stated above.

Now my question is two fold:

* Is there a better way of going about this?
* Given the two heuristics, how would I go about showing the competitive ratio?

Any help in this regard is appreciated.

**Edited**: For the sake of simplicity, let us consider for each node on a candidate path, a new table entry is added with a probability $p\_i$ and not added with probability $1-p\_i$.

Note:

* When a request arrives, and we get a set of candidate paths, we can know in $\mathcal{O}(1)$ time for each node in the path, whether it will have an entry added to its table or not. So in $\mathcal{O}(l)$ time we can know the number of *new* table entries for a path, where $l$ is the length of the path.
* We have global knowledge about the number of entries in a table of each node at every time instant.

# Answer
> 2 votes
In general, there are two approaches you can take here:

**Empirical evaluation.** Pick a realistic workload (a data set with a bunch of scenarios, where each scenario is a sequence of requests). Use this as a benchmark. Test each candidate heuristic on that benchmark, and see which one performs the best on this benchmark.

**Theoretical analysis.** Alternatively, you can try to prove a theorem about the competitive ratio of these two heuristics. That may be very difficult.

I suspect it's going to be a lot more feasible -- and potentially more useful -- to take the former approach. It does require you to have a dataset of representative requests.

---

I can suggest another plausible heuristic. Given a graph, you can find use bottleneck shortest paths to find the best path from $s$ to $t$, where "best" is measured by the number of slots in the least empty node that's visited along that path. The larger that number, the better (it means there exists a path with plenty of spare capacity). So, one possible heuristic is to choose whichever path reduces this number the least.

There are probably many other heuristics you could come up with. I suggest brainstorming a few, then evaluating them empirically using the approach listed above.

---
Tags: algorithms, graphs, dynamic-programming, online-algorithms
---


title: function application of N x N -> N

text:
# Question
Title: function application of N x N -> N
Let the function cane and its auxiliary helping function down be the smallest functions satisfying the following requirement. For every x∈ℕ, for every y∈ℕ, and for p=(x,y), all of the following statements hold:

*down(x+1,y)=(x,y+1)*

*down(0,y+1)=(y,0)*

*cane(p)= 0 if down(p) is undefined*

*cane(p)=1+cane(down(p)) if both down(p) and cane(down(p)) are defined.*

(NOTE: p above is a pair.)

For every x ∈ ℕ and y ∈ ℕ such that x+y ≤ 2 (there are six such pairs), calculate the value, if there is one, of down(x,y) and also of cane(x,y). Put your answers in two tables, one for down and one for cane, of this form:

Hint: It might help you for the later parts of this question if you he k these two functions with more values for x and y.

Describe in words how the function cane and its auxiliary helping function down work, and what they accomplish. Explain any wider significance ane these functions might have. My question is how am I supposed to fill in this table;

for example, if I take in x to be 0 and y to be 0 then my down function would be as follows;

down(0+1,0)=(0,0+1)==(1,0)=(0,1) and down(0,0+1)=(0,0)==(0,1)=(0,0) I believe then that when x=0 and y=0 then the position in the table is "undefined" and true for all other coordinates of the table because they form a trail back to (0,0).

Could someone please help me understand this?

# Answer
A more formal way to define the down function is $$ \mathit{down}(x,y) = \begin{cases} (x-1,y) & \text{if } x \> 0, \\ (y-1,0) & \text{if } x = 0 \text{ and } y \> 0, \\ \text{undefined} & \text{if } x=y=0. \end{cases} $$
> 1 votes

---
Tags: computability
---


title: Definition of InLeft and InRight

text:
# Question
Title: Definition of InLeft and InRight
So in reading I have come across the terms "InLeft" and "InRight" and I am unable to find a concrete definition for it.

I have found it used in the specification for COQ, and in some notes on compilers (there it was refered to as INL and INR).

As far as I am able to ascertain it is to do with making a difference between two options. However the seems like a weird nomenclature for something so simple.

# Answer
The page you reference for Coq defines `inLeft` and `inRight` as constructors of the inductive type `sumor`. The names themselves come from "left/right injection", as in the left/right injection into a sum type. Other names commonly used are `inl`/`inr`, `Left`/`Right`, $\iota\_0$/$\iota\_1$, and variations on these (e.g. that Coq file also defines `left`/`right` in the definition of `sumbool`). It also defines `inl`/`inr` as the constructors of the general `sum` type. `sum`, `sumor`, and `sumbool` are minor, technical variations of each other.

Which terms are used depends on the author, but they are most commonly used for injections into a sum type, particularly in a type theory/category theory context. Of course, an author is always free to use them for something else if they provide a definition.
> 4 votes

# Answer
There is no accepted definition for this. You'll presumably need to infer what the authors had in mind based on all of the available context (e.g., all of the code), in which case it might not be a suitable question here.
> 1 votes

---
Tags: terminology, proof-techniques, compilers, proof-assistants
---


# Question
Title: Prove or disprove whether L is regular by definiton
Assume L is regular language, define 1 = {: ∈ , ∉ }, prove or dispute L1 regular or not ?

# Answer
> 1 votes
It’s regular.

First we can gain a DFA $M$ which accepts the given language $L$. Similarly we have a DFA $\bar M$ which accepts regular language $\bar L$.

Then we can construct a new NFA by adding an $\epsilon$ transition from all the final states in $M$ to $\bar M$’s initial state, which accepts that required language.

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


title: Booth bit-pair recoding technique

text:
# Question
Title: Booth bit-pair recoding technique
In Booth's bit-pair recording technique how to multiply a multiplicand with -2 or 2? For example while multiplying 01101(+13, multiplicand) and 11010(-6, multiplier), we get 01101 x 0-1-2.

How to multiply the multiplicand using -2?

# Answer
> 1 votes
In bit recoding multiplication, e.g. 01101 times 0, -1, or -2.

* For multiplying with -1: Take 2's complement of 01101 i.e: 10011
* For multiplying with -2: Add 2's complement of 01101 i.e: 10011 + 10011= 100110

# Answer
> 1 votes
multiplying with -2 : Take 2's complement and Shift Left one bit

# Answer
> -1 votes
First you must come to thr lsb of bit pair recoding i.e say 0 -1 2. So here lsb is 2 it means we must multiply 10 with multiplicand because based in the recoding table if it is positive 2 then we multiply and same procedure must be followed for next bit i.e -1 and so on

---
Tags: arithmetic, multiplication
---


title: Syntax of recurrence formula not clear

text:
# Question
Title: Syntax of recurrence formula not clear
I have this task for Analysis of Algorithms module in university

$$ \begin{align\*} W, V &= \\{v\_1, v\_2, v\_n\\}, S = \\{s\_1, s\_2, s\_n\\}\\ G(W) &= \max~\_{i:w\_i\leq w} ~\\{G(W-s\_i) + v\_i\\}, G(0)=0\\ \end{align\*} $$

I am not sure what does the marked text mean in this recurrence formula. Because I think $W$ is a variable not an array so $i\colon w\_i\<w$ does not really make sense to me. Could someone please explain this to me?

# Answer
The notation is a crossover between

$\qquad\displaystyle \max\_{i}$

and

$\qquad\displaystyle \max \\{ \dots \mid i \\}$.

It means the same as

$\qquad\displaystyle \max \\{ G(W - s\_i) + v\_i \mid 0 \leq i \leq n, w\_i \leq W \\}$,

guessing about the domain of $i$.
> 1 votes

---
Tags: recurrence-relation, notation, mathematical-foundations
---


# Question
Title: Questions on Sipser's NP implying verifiability?
I've revisited trying to understand the proof to why NTM exists iff there is a verifier. I think I'm finally understanding the proof but I want to make sure and thus have some questions as follow up along with to check if I'm understanding.

1. For the forward implication (there exists a verifier $V$ and we want to show this implies the existence of an NTM $N$), we can, according to Sipser, "Nondeterministically select string $c$ of length at most $n^k$. Then we run $V$ on input $(w,c)$ and accept if $V$ accepts, otherwise reject." I'm wondering if $V$ would be run as part of the algorithm on each branch of $N$. In other words, for any node in the computation tree of $N$, the verifier will be run on the that current string, and the branch will produce a YES answer only if the verifier accepts that string. Am I understanding this correctly? So it would run concurrently, and since the verifier runs in $O(n^k)$ and the NTM runs in $O(n^q)$, then this still runs in polynomial time if the verifier is run at every step in the computation.
2. For the backward implication, we assume $A$ is decided by a polynomial time NTM and construct a polynomial time verifier $V$. When we say that $A$ "is decided by" $N$, does this mean that $N$ is correctly able to determine if any given branch of computation results in accept or reject? This feels a bit cyclic to me, since we are trying to construct the verifier $V$ given $N$. I don't see how $N$ could decide $A$ without $N$ having a verifier constructed already. In other words, without a verifier, how would the NTM know if it should accept/reject on any of its given branches?

# Answer
> 4 votes
1. Essentially, yes. Though I usually find it easier to think of nondeterministic machines as guessing what to do. So, as the machine runs, it starts by repeatedly doing the following: either it guesses that the current string is good, and verifies it, or it guesses what the next character should be, and it repeats. Thus, if there's some string that the verifier will accept, some sequence of guesses will lead to the machine producing that exact string and then deciding to verify it, so the machine will accept. (Also, the machine needs to keep track of how long the string is, so it can stop if it gets too long.)
2. We have a nondeterministic Turing machine $N$ and the guesses it makes lead it down some path of the tree of possible computations. If that path ends in an accepting state, the machine is defined to accept its input; if no path ends in an accepting state, it is defined to reject. There's no circularity: that's just the definition of what it means for a nondeterministic machine to accept or reject.

From this machine, we build a verifier. The input to the verifier is a description of a computation path, and the verifier checks that each action taken on that path is a thing that $N$ could do in that state, and that the path ends in an accepting state. If those conditions are met, the verifier has verified that $N$ really would accept the given input.

---
Tags: complexity-theory, turing-machines, np, nondeterminism
---


# Question
Title: Edit distance of list with unique elements
Levenshtein-Distance edit distance between lists is a well studied problem. But I can't find much on possible improvements if *it is known that no element does occurs more than once in each list*.

Let's also assume that the elements are comparable/sortable (but the lists to compare are not sorted to begin with).

In particular I am interested if the uniqueness of elements makes it possible to improve upon Ukkonen's algorithm for edit distance which has time complexity $O(\min(m,n)s)$ and space complexity $O(\min(s,m,n)s)$, where $s$ is the minimum cost of the editing steps.

More formally,

> how efficiently can we compute the edit distance between two given strings $s,t \in \Sigma^\*$ with the promise that they don't have any repeated letters?

$\Sigma$ is a very large alphabet.

# Answer
**TL;DR: A slightly more restrictive kind of edit distance, in which we can only insert and delete individual characters, can be computed in linearithmic time when both (or even just one) of the strings have unique characters. This gives useful upper and lower bounds on the Levenshtein edit distance.**

## Insert/delete edit distance, and longest common subsequences

Levenshtein edit distance allows single-character insertions, deletions and substitutions, assigning each a cost of 1. If we restrict to just insertions and deletions, we get a similar distance measure that now causes substitutions to have a cost of 2 (since any substitution can be mimicked using an insertion and a deletion). I don't know a standard name for this more restrictive kind of edit distance, so I'll call it "insert/delete edit distance". It corresponds closely to the longest common subsequence (LCS) problem, in which we are given two strings, of length $m$ and $n$, respectively, and want to know the length of the longest subsequence that appears in both. **If two strings have LCS $L$, then they have insert/delete edit distance $n+m-2L$**: the easiest way to see this is to align the strings so that characters in the LCS appear stacked on top of each other, while characters not in the LCS appear opposite a `-` gap character. It will then be apparent that we can edit the first string into the second by making an insertion wherever there is a `-` in the top row, and a deletion wherever there is a `-` in the bottom row. For example:

```
-C-IRC-LE
T-RI-CKLE

```

Here the LCS of `CIRCLE` and `TRICKLE`, `ICLE`, has length 4, and the edit distance is indeed $6+7-2\*4=5$.

## Longest increasing subsequences

The reason for this detour is that there is a very efficient way to calculate the LCS (and thus the insert/delete edit distance) when at least one of the sequences contains only distinct characters: In this case, the LCS problem can be transformed into the problem of finding a longest increasing subsequence, which can be solved in time $O(n \log n)$. Suppose we are given two strings $A$ and $B$, and string $A$ has distinct characters. We can rename the first character in $A$ to 1, the second to 2 and so on, keeping track of what number we assigned to each character in a table. Then in $B$, we rename its characters using this table (i.e., every occurrence of whatever was the first character in `A` is changed to 1, etc.). Finally, we look for a longest increasing subsequence in `B`. This corresponds to a LCS between `A` and `B`, and from there we can immediately calculate the insert/delete edit distance. The total time needed is just $O(n + m\log m)$ if $A$ and $B$ have lengths $n$ and $m$, respectively.

## Bounds on Levenshtein edit distance

The insert/delete distance clearly provides an upper bound on the Levenshtein distance (since any valid sequence of edit operations under the insert/delete distance is also a valid sequence of Levenshtein edit operations). Dividing the insert/delete edit distance by 2 also gives a lower bound, since in the worst case any Levenshtein edit operation can be changed into 2 insert/delete edit operations.

## Generalisations

Already in 1977, Hunt and Szymanski came up with an algorithm that can be viewed as a generalisation of the longest increasing subsequence algorithm. It is efficient whenever the number of pairs of matching character positions between the two strings is small. If there are $r$ such pairs, their algorithm takes $O((r + n)\log n)$ time. (Notice that $r \le n$ if all characters in one string are distinct.) This algorithm was the basis of the original `diff` program, which treated entire lines of text as individual characters. `diff` later switched to using Myers's $O(nd)$-time algorithm, where $d$ is the insert/delete edit distance, as this performs better when overall differences are small but some "characters" (text lines) appear frequently (such as a line containing just an opening brace in C program code).

> Hunt, J.; Szymanski, T. (1977), "A fast algorithm for computing longest common subsequences", Communications of the ACM, 20 (5): 350–353, doi:10.1145/359581.359603
> 3 votes

---
Tags: algorithms, strings, string-metrics, edit-distance
---


# Question
Title: Algorithm for solving planar constraint problem ("Pokemon Go monster finding")
\[Note: This problem was inspired by Pokemon Go. I will first explain the problem in mathematical terms, then explain the connection to Pokemon Go. My goal is not to cheat in the game. If I wanted to cheat, better information would be available more easily.\]

Suppose there are $N$ points (the "unknown points") in a plane, call them $n\_1,\dots,n\_N$, with unknown coordinates. Moreover, we have $M$ measurements taken at known locations $m\_1,\dots,m\_M$.

Let $\text{dist}(m\_i, n\_j)$ be the (generally unknown) Euclidean distance from measurement point $m\_i$ to the unknown point $n\_j$.

For each measurement $m\_i$, we have the following information:

1. The exact coordinates of each unknown point $n\_j$ for which $\text{dist}(m\_i, n\_j)\<d\_\text{min}$ for some known constant $d\_\text{min}$; and
2. A list of all indices $j$ for which $\text{dist}(m\_i, n\_j) \< d\_\text{max}$ for some known constant $d\_\text{max}\>d\_\text{min}$, sorted by $\text{dist}(m\_i, n\_j)$.

Is there an efficient algorithm for calculating the areas of the plane where the unknown points, or a given unknown point $n\_j$, can be? The algorithm is given the coordinates $(X\_i,Y\_i)$ of the measurement points, the measurement information listed above, and the number $N$ of unknown points; the goal is to narrow down the region of possible locations for each of the unknown points $n\_1,\dots,n\_N$ as much as possible.

The Pokemon connection:

In Pokemon Go, an augmented reality game, the goal is to find Pokemons in nature. Every now and then, the game shows the Pokemons in a "visible range" ($d\_{min}$) of the player's position. Moreover, it has a "Pokemon finder" which shows a list of nearby ($dist\<d\_{max}$) Pokemons, sorted by distance. (It's also supposed to show an approximate distance as one, two or three footsteps, but apparently there's a bug and it always shows three footsteps.)

# Answer
> 3 votes
I think you could use a "spatial join". I haven't played the game, but I assume $d\_{max}$ is rather small, i.e. there are in the order of 10 or so $n$ and $m$ in the neighborhood of each $m$. I further assume that $N$ and $M$ are large, say 1,000,000 or more.

1. Put all $m$ as 2D points in a spatial index
2. For each $m\_1$ in the index, perform a spatial range query with distance $2\*d\_{max}$. This gives you all other $m\_x$ that can potentially contain the same $n$ as $m\_1$. This should be manageable because the number of $m\_x$ should be small (as I assumed above).
3. Now, by getting all other estimated measurements for a particular $n$, you can try to approximate the correct $n$
4. (Potential optimisation): Depending on your spatial index, you can remove the $m\_1$ after processing all it's $n$. This makes the dataset smaller for the following range queries. Also,

Somehow you would also need to uniquely identify each $n$, so that you don't calculate the position of $n$ again if it turns up when processing another $m$.

As an optimisation, you may want to use window queries (rectangular) rather than circular range queries. Window queries can be much faster and give only slightly more results. Also, it could be that the game actually does not use euclidean distance (circles) but the faster manhatten distance, which would be exactly a rectangle.

For such a spatial join you can use any spatial index, such as R-Tree, kd-Tree, quadtree or any of their variants.

For large datasets I would probably not use a R-Tree (R+tree, R\*-tree, X-Tree), or a special variant of the quadtree, the PH-Tree, which is well suited for range queries as well as allowing fast removal (or addition) of points.

For Java, implementations of R-Trees can be found in the anywhere on the internet, for example in the ELKI framework or my own TinSpin Index library. The PH-Tree is also available in Java.

A generic spatial join algorithm is called TOUCH, but I don't think it is open source.

# Answer
> 1 votes
If some object position $n\_j$ is known exactly (e.g., because it is within $d\_{min}$ of some measurement), then whenever this $n\_j$ appears in the annulus for some measurement $m\_i$ (meaning $d\_{min} \le dist(m\_i, n\_j) \< d\_{max}$), we can shrink the possible regions for other unknown positions in that same annulus. Specifically, we can simply calculate $d\_{ij} = dist(m\_i, n\_j)$ since we know both positions ($m\_i$ and $n\_j$) exactly, and we can then split the annulus for $m\_i$ into two sub-annuli: a "near" piece (containing all points $p$ such that $d\_{min} \le dist(m\_i, p) \< d\_{ij}$) and a "far" piece (containing all points $p$ such that $d\_{ij} \le dist(m\_i, p) \< d\_{max}$). Every object listed before $n\_j$ for measurement $m\_i$ is necessarily confined to the near annulus, and every object listed after $n\_j$ is confined to the far annulus.

What can be done (beyond the intersection of annuli already suggested by Tom van der Zanden in a comment) for object positions that aren't related to some already-known object position in this way? This seems very hard. The statement

"$n\_j$ cannot appear at $p$"

is equivalent to

"For *all possible placements* of all remaining unknown points, setting $n\_j = p$, together with the distance inequalities implied by the order in which objects belonging to the annulus of each measurement are listed, leads to a contradiction".

It seems to me that to get anywhere, we need to have (at least) 2 unknown object positions that appear in the annulus of (at least) the same 2 measurements. But while this information will rule out many *pairs of* positions for the two objects, I wasn't able to come up with any circumstance in which a position could be ruled out for just one of them, independently of the other object's position.

---
Tags: algorithms, computational-geometry, constraint-satisfaction
---


title: Recurrence equation calculation

text:
# Question
Title: Recurrence equation calculation
I have a recurrece equation

Changed notations: $\qquad\displaystyle G(W) = \max \\{ G(W - s\_i) + v\_i \mid 0 \leq i \leq n, w\_i \leq W \\}$,

I am not sure if I understand $\ w\_i $ correctly.

On each iteration my $ w\_i \leq W $ . So my $ w\_i $ will be previous $ W-s\_i $ since G takes one argument?

# Answer
> 1 votes
Here is pseudocode for computing your function:

> Parameters:
>
> * Integer $n$
> * Arrays $W,V,S$ of length $n$
>
> function G(w):
>
> * If $w = 0$, return $0$
> * Let $\mathrm{max} \gets -\infty$
> * For $i$ from $1$ to $n$:
> * + If $W\[i\] \leq w$:
> * + - Let $x \gets G(w-S\[i\])+V\[i\]$
> * + - If $x \> \mathrm{max}$, let $\mathrm{max} \gets x$
> * Return $\mathrm{max}$

I used the notation $W\[i\],V\[i\],S\[i\]$ rather than $w\_i,v\_i,s\_i$.

---
Tags: recurrence-relation, recursion
---


# Question
Title: Transform 2D range query matrix into segment tree to make memory usage lower
Let's say we have given matrix $N\cdot N$, with zeros and ones only at $P$ position at it. We want to implement queries $q(x\_1, y\_1, x\_2, y\_2)$ which will return the number of ones in the sub-rectangle described with those two points. Since $N$ can be up to $10^4$ we cannot create standard DP matrix for answering the queries in $O(1)$. Is it possible to answer such queries without generating the DP matrix?

# Answer
> 1 votes
You could use a quadtree or kD-Tree. They are multidimensional indexes (your case only needs 2D) that perform insertion, deletion and window queries (rectangle defined by two coordinates) in $O(log (n))$.

In your case you would simply insert all coordinates/cells with '1' into the quadtree/kd-tree. Then you can perform a window query that returns all '1' in a given rectangle. For example, to define a '1' at $(3,7)$:

```
KDTree<Boolean> tree = new KDTree<>(2); //2 dimensions
tree.put(3, 7, 1); //You could ommit the '1', since all entries will have a '1'.

```

To perform a query between $(1,1)$ and $( 4,6)$:

```
Iterator<Entry> iter = tree.query(1,1,4,7);

```

The iterator contains a sequence of `Entries`, where each entry has coordinates and a value, such as '1'. The example should return exactly one Entry for $(3,7)$. The syntax will differ between implementations, but they should all be similar.

Be aware that this is only useful if $N$ is large and $P$ is small, because there is some storage overhead.

There are example implementations all over the web, also referenced from the Wikipedia pages. I also have my own Java implementations here, however, they are implemented to work with any dimensionality and take any Object as values so they are a bit overkill if you just use 2D and only store boolean 1/0.

---
Tags: trees, dynamic-programming
---


# Question
Title: What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another?
So i came upon this thread :

https://gateoverflow.in/57631/relation-between-np-recursive-and-recusive-enumerable

and the guy says Every language in NP is recursive and Every language in NP is recursively enumerable.

but i dont get it, isn't NP the set of problems which we can only determine if a given answer is true in polynomial? doesn't that mean if the answer is no we may not know?

So i'm kinda confused here and really can't put all these together

so overall my question is : **can someone please tell me what is the relation between NP/NP-hard/NP-complete problems and Recursive/RE languages ?**

i read about these stuff in different courses but non of them combined all of them together for a bigger picture

(also i know that Recursive languages are a subset of RE)

also based on this : https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

NP should not be recursive because NP is set of problems which IF the answer is yes we can detect it in polynomial, but that thread doesn't say anything about what happens if its not NP

# Answer
> 6 votes
Overall: $NP\text{-complete} \subseteq NP \subsetneq R \subsetneq RE$

$NP\text{-complete} \subseteq NP$ by definition. It is unknown whether or not there are problems in $NP$ that are not $NP\text{-complete}$.

$NP \subseteq R$ as explained in Yuval Filmus's answer. The subset relation is strict ($NP \subsetneq R$) because we know there are problems in $R$ that are not in $NP$.

Since every $NP$ problem is in $R$ and as you pointed out $R$ is a subset of $RE$, $NP \subsetneq RE$ as well.

$NP\text{-hard}$ problems are *at least* as hard as the hardest problems in $NP$ but there's no upper limit on how hard they themselves can be. There are $NP\text{-hard}$ problems that are:

* In $NP$ (take any $NP\text{-complete}$ problem as an example)
* Not in $NP$ but in $R$ (see the second link)
* Not in $NP$ and not $R$ (eg. the halting problem)
* Not even in $RE$ (eg. the complement of the halting problem)

Putting this all together, you can visualize these classes in a Venn diagram like so:

(If $P = NP$, then the innermost region would be a single circle representing $P = NP = NP\text{-complete}$)

# Answer
> 7 votes
Every problem in NP can be decided in exponential time (and so it is recursive). Recall that one of the definitions of NP goes via *witnesses*:

> A language $L$ is in NP if there is a polynomial $P$ and a predicate $f$ computable in polynomial time such that $x \in L$ if and only if there exists a "witness" $y$ of length at most $P(|x|)$ such that $f(x,y) = \mathrm{True}$.

(A predicate is a function which returns *True* or *False*.)

Let's suppose that $y$ is in binary. Given an input $x$, in time $2^{P(|x|)}$ we can go over all potential witnesses $y$, and for each of them calculate $f(x,y)$. If $f(x,y) = \mathrm{True}$ for any of them, then $x$ is in $L$, and otherwise $x$ is not in $L$.

---
Tags: formal-languages, turing-machines, np-complete, np, decision-problem
---


# Question
Title: What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity?
So considering CYK is O(n^3) and since we can just use LR(k) algorithms for DCFG's which they can check if a string is in the language in O(n) then whats the usage of CYK?

is it being used anywhere?

If I'm not mistaken(correct me If I'm wrong) the benefit of CYK is that since we can convert any CFG to CNF form therefore i guess we can apply this to non deterministic CFG's and also Inherently ambiguous grammars which are CFG

but are these really benefits? i mean whats the usage of using membership algorithm for Inherently ambiguous CFG's or non deterministic CFG's? where would we use a Inherently ambiguous CFG or non deterministic CFG ?!

Isn't the main usage of membership for compilers? which they already use LR algorithms?

# Answer
Here is one benefit:

Some grammars aren't LR(k). Then it's useful to have CYK or some other form of GLR parsing. GLR parsing is used in some compilers, where the most natural way to express the grammar leads to a grammar that isn't LR(k), or where ambiguities are resolved in a later pass (not part of the parser).
> 5 votes

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


# Question
Title: What is the regular expression for strings containing at least one a and at least one b?
$L = \\{w \in \\{a, b, c\\}^\*\mid w\text{ contains at least one }a\text{ and at least one }b\\}$.

what's the proper regular expression for the following language?

# Answer
> -1 votes
The DFA of this language can be easily written.

Apply state removal method to this machine, then you can receive a regular expression.

Reference to state removal method: How to convert finite automata to regular expressions?

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


# Question
Title: How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?
How to solve the recurrence $T(n) = T(n/2) + T(n/4) + T(n/8)$?

We assume that $T(n)$ is constant for sufficiently small $n$.

# Answer
Use the Akra-Bazzi theorem, a generalization of the master theorem which captures recurrences such as yours. The method immediately gives $T(n) = \Theta(n^p)$, where $(1/2)^p + (1/4)^p + (1/8)^p = 1$.

In contrast to your method, the Akra-Bazzi theorem can also handle inhomogeneous recurrence relations (i.e., $T(n) = T(n/2) + T(n/4) + T(n/8) + g(n)$), and it can also handle floors and ceilings (i.e., $T(\lfloor n/2 \rfloor)$ instead of $T(n/2)$) and beyond.
> 2 votes

# Answer
We guess that $T(n) = \Theta(n^{\alpha})$, where $\alpha \> 0$ is a constant.

To find $c$, we use the substitution method.

Assume that $T(n) \le cn^{\alpha}$. (The other direction $T(n) \ge cn^{\alpha}$ is similar.)

Then, we have $$T(n) \le c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha}.$$

Letting $$c(n/2)^{\alpha} + c(n/4)^{\alpha} + c(n/8)^{\alpha} = cn^{\alpha},$$ we obtain that $$(1/2)^{\alpha} + (1/4)^{\alpha} + (1/8)^{\alpha} = 1.$$

Solving this equation (using Mathematica) yields $$\alpha = 0.879146.$$
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Is the union of two non-regular context-free languages always non-regular?
I had this question in my HW:

> Prove of disprove: If $L\_1$ and $L\_2$ are non-regular context free languages then $L\_1 ∪ L\_2$ is not **regular**.

My intuition is that it is wrong. I thought about the following two languages:

* $L\_1 = \\{a^ib^jc^k : 0 \leq i \leq j \leq k\\}$ and
* $L\_2 = \\{a^ib^jc^k : j\<i \lor j\>k\\}$.

The union of these two languages is $a^\*b^\*c^\*$ which is regular, but I didn't succeed to prove that $L\_2$ is not a CFL (tried with the pumping lemma and stuck in the case that $vxy$ contains two types of letters).

Am I right with my intuition? if do so, how can I prove that $L\_2$ isn't a CFL, or which other two languages disprove this claim?

# Answer
Let $L$ be any non-regular context-free language over $\\{0,1\\}$, for example $\\{ 0^n 1^n : n \geq 0 \\}$. Take $$ \begin{align\*} L\_1 &= 0L \cup 1\Sigma^\* \cup \\{\epsilon\\}, \\ L\_2 &= 1L \cup 0\Sigma^\* \cup \\{\epsilon\\}. \end{align\*} $$ Then $L\_1$ and $L\_2$ are also non-regular context-free (exercise), but $L\_1 \cup L\_2 = \Sigma^\*$.
> 2 votes

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


# Question
Title: Little bit confusing to compute time complexity of nested loop
```
1 for(i=1; i<=n; i++){
2    for(j=1; j<=n; j*=2){
3      a[i][j]=b[i][j-1]+1;
4    }
5 }

```

line 1 : n+1 times

lnie 2 : n/2+1 times

line 3 : constant time c

so, I computed $(n+1)(n/2+1)c=(n^2+2n+2)/2+c=\theta(n^2)$

Is it right computation?

# Answer
> 1 votes
Line $2$ is executed for $j=1,2,4,\cdots 2^k$ where $k$ is such that $2^k\le n\<2^{k+1}$. Hence, taking the logarithm

$$k\le\log\_2n\<k+1$$or

$$k=\lfloor\log\_2n\rfloor.$$

So the total time is

$$n\lfloor\log\_2n\rfloor c=\Theta(n\log n).$$

---
Tags: algorithm-analysis, runtime-analysis, loops
---


# Question
Title: Computational Complexity of Solutions of the Traveling Purchaser Problem on a Small Data Set
I have encountered a problem that is essentially the textbook statement of the Traveling Purchaser Problem. I don't know if this is the proper place to put this, if not then I will delete it.

Also a note is that while I have done some studying on my own of computer science, I did not have much formal education in it. I do have a reasonably strong math background though.

Now on to the background of the problem:

I know the Traveling Purchaser Problem is NP-Hard, and thus there is no optimal solution algorithm known. I know that as such, there are many different solution algorithms, of varying efficiency. The (admittedly few) papers that I have seen though use this on sets of 100s of nodes, and don't explicitly state the complexity of the algorithm in terms of big-O notation or similar functions. Since my data set is relatively small (7 nodes and about 50 items to purchase). I was wondering if it might be a waste of time to implement a complex, if efficient, algorithm. But that is not my question, as I think such questions would be out of place here, it is just the background.

My question is the following:

What are some of the common algorithms for approximating the solution to the Traveling Purchaser Problem along with their computational complexity in terms of the number of nodes and the number of items to purchase.

# Answer
> 1 votes
First, it is good to observe that the problem is very difficult to approximate (see e.g., my earlier answer on it here).

Second, there is very recent survey on the traveling purchaser problem and its variants by Manerba et al. \[1\]. Essentially, you will find discussion on relevant methods that have been applied to solve the problem in practical settings. If you want theoretical time bounds for heuristics, see Section 6.1.1. on page 13.

---

\[1\] Manerba, Daniele, Renata Mansini, and Jorge Riera-Ledesma. "The traveling purchaser problem and its variants." European Journal of Operational Research 259.1 (2017): 1-18.

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity, np-hard
---


# Question
Title: Reduce undecidable language to decidable language?
What happens if I build the following mapping function from $A\_{\mathrm{TM}}$ to $A\_{\mathrm{LBA}}$ (LBA means linear TM with a limited tape space and $A\_{\mathrm{LBA}}$ **is** decidable):

If $M$ accepts $w$ then returns an LBA which decides the language {'111'}.

Clearly if $(M,w)$ is in $A\_{\mathrm{TM}}$ then $f(M,w)$ is in $A\_{\mathrm{LBA}}$ but then $A\_{\mathrm{TM}}$ would be decidable!

What am I missing here?

# Answer
> ... but then $A\_{\mathrm{TM}}$ would be decidable!

No. Because your $f$ is not computable since one cannot compute whether $M$ accepts $w$, as Yuval Filmus said in the comment.
> 2 votes

# Answer
If a language $B$ is decidable, there is an algorithm that computes it. If a language $A$ is mapping-reducible to $B$, then you have the following algorithm for $A$: first compute the translation given by the mapping reduction; then use the algorithm for $B$.

So, if $A$ has a mapping reduction to some decidable language, then $A$ must also be decidable. OK, I don't think I've yet told you anything you don't know. We can conclude that either the halting problem is decidable, or the halting problem for LBAs is undecidable or the thing that you're calling a mapping reduction isn't actually a mapping reduction.

It's the third option. A mapping reduction from $A$ to $B$ is a computable function $f\colon\Sigma^\*\to\Sigma^\*$ such that $x\in A$ if, and only if, $f(x)\in B$. Well, first things first, you haven't actually defined a function from $\Sigma^\*$ to $\Sigma^\*$: you've only defined a function from $A\_\mathrm{TM}$ to $\Sigma^\*$. Specifically, you've not said what $f(x)$ is when $x\notin A\_\mathrm{TM}$.

So, suppose we extend your definition to be $$f(\langle M,w\rangle)=\begin{cases}\langle A,111\rangle&\text{if $M(w)$ halts}\\ \langle A,000\rangle&\text{if $M(w)$ does not halt,} \end{cases}$$ where $A$ is some LBA that accepts the langauge $\\{111\\}$.

This function $f$ certainly has the $x\in A\Leftrightarrow f(x)\in B$ property but it's not computable, so it doesn't define a mapping reduction. In particular, you'd have to solve the halting problem to compute it, since it's of the form, “If the input halts, do $X$; else, do $Y$.” If you could compute $f$, you'd already be able to solve the halting problem, so you wouldn't need to use the reduction!
> 1 votes

---
Tags: turing-machines, computability, reductions, linear-bounded-automata
---


title: Proof of big-o propositions

text:
# Question
Title: Proof of big-o propositions
I don't understand the proof of below sentences.

1. $O(f(n))=O(g(n)) \iff \Omega(f(n))=\Omega(g(n)) \iff \theta(f(n))=\theta(g(n))$
2. $f(n)=\theta(g(n)) \iff g(n)=\theta(f(n))$

How can I prove these statements?

# Answer
We will be using the following definitions:

> Let $f\colon \mathbb{Z}\_+ \to \mathbb{Z}\_+$ be a function mapping positive integers to positive integers.
>
> The class $O(f)$ consists of all functions $g\colon \mathbb{Z}\_+ \to \mathbb{Z}\_+$ such that for some real $C\>0$, for all $n \in \mathbb{Z}\_+$ we have $g(n) \leq Cf(n)$.
>
> The class $\Omega(f)$ consists of all functions $g\colon \mathbb{Z}\_+ \to \mathbb{Z}\_+$ such that for some real $c\>0$, for all $n \in \mathbb{Z}\_+$ we have $g(n) \geq cf(n)$.
>
> The class $\Theta(f)$ consists of all functions $g\colon \mathbb{Z}\_+ \to \mathbb{Z}\_+$ such that for some real $C,c\>0$, for all $n \in \mathbb{Z}\_+$ we have $cf(n) \leq g(n) \leq Cf(n)$.
>
> We also write $g(n) = O(f(n))$ instead of $g(n) \in O(f(n))$, and similarly for the other two.

These are equivalent to the more standard definition in which the above only has to hold for large enough $n$. You can also carry out the proofs below using the standard definitions — this entails only small changes.

Let's start with the second statement: $f(n) = \Theta(g(n))$ iff $g(n) = \Theta(f(n))$.

Suppose that $f(n) = \Theta(g(n))$. Then there exist $C,c\>0$ such that for all $n$ we have $cf(n) \leq g(n) \leq Cf(n)$. Therefore for all $n$ we have $C^{-1} g(n) \leq f(n) \leq c^{-1} g(n)$, and so $g(n) = \Theta(f(n))$. Similarly, if $g(n) = \Theta(f(n))$ then $f(n) = \Theta(g(n))$.

Now let us go back to the first statement: $O(f(n)) = O(g(n))$ iff $\Omega(f(n)) = \Omega(g(n))$ iff $\Theta(f(n)) = \Theta(g(n))$.

Suppose that $O(f(n)) = O(g(n))$. It is easy to check that $g(n) = O(g(n))$ (take $C = 1$), and so $O(f(n)) = O(g(n))$ implies that $g(n) = O(f(n))$. That is, there exists $D\>0$ such that $g(n) \leq Df(n)$ for all $n$. Similarly, $f(n) = O(g(n))$, and so there exists $E\>0$ such that $f(n) \leq Eg(n)$ for all $n$. Suppose now that $h(n) = \Theta(f(n))$. Then there exist $C,c\>0$ such that $cf(n) \leq h(n) \leq Cf(n)$ for all $n$. This implies that $cD^{-1} g(n) \leq h(n) \leq CEg(n)$, and so $h(n) = \Theta(g(n))$. Similarly, if $h(n) = \Theta(g(n))$ then $h(n) = \Theta(f(n))$, and so $\Theta(f(n)) = \Theta(g(n))$.

Similarly, if $\Omega(f(n)) = \Omega(g(n))$ then $\Theta(f(n)) = \Theta(g(n))$.

Conversely, if $\Theta(f(n)) = \Theta(g(n))$ then, as before, $f(n) = \Theta(g(n))$. This means that there exist $C,c\>0$ such that $cg(n) \leq f(n) \leq Cg(n)$ for all $n$. Now suppose that $h(n) = O(f(n))$. Then there exists $D\>0$ such that $h(n) \leq Df(n)$ for all $n$. Since $h(n) \leq Df(n) \leq DCg(n)$, we see that $h(n) = O(g(n))$. Similarly, if $h(n) = O(g(n))$ then there exists $E\>0$ such that $h(n) \leq Eg(n)$. This implies that $h(n) \leq Ec^{-1} f(n)$, and so $h(n) = O(f(n))$. Thus $O(g(n)) = O(f(n))$. Similarly, $\Omega(g(n)) = \Omega(f(n))$.
> 0 votes

---
Tags: asymptotics
---


title: Proving that language is regular or not

text:
# Question
Title: Proving that language is regular or not
How to prove that the language over the alphabet $\\{0, 1, +, =\\}$ is regular or not:

$\\{a+b=c:a,b,c \text{ are integers in binary for which } a \text{ plus } b\text{ equals } c\\}$

I started with the pumping lemma:

> 1. |$y$| ≥ 1
> 2. |$xy$| ≤ $p$
> 3. for all $i$ ≥ 0, $xy^iz$ ∈ $L$

But I don't know what to do next. How can split "$a+b=c$" string to start with the pumping lemma? Or I should apply another method?

# Answer
> 2 votes
The easiest way is to take the intersection of your language with $1^\*+0=1^\*$, which is $$ \\{ 1^n+0=1^n : n \geq 0 \\}. $$ A similar option is to intersect with $1^\*+1=10^\*$, which gives $$ \\{ 1^n+1 = 10^n : n \geq 0 \\}. $$ I'll let you finish the argument.

---
Tags: regular-languages, pumping-lemma
---


title: Why is this not a valid Red-Black tree?

text:
# Question
Title: Why is this not a valid Red-Black tree?
I'm having some difficulty understanding the rules for valid red-black tree. If my understanding is correct there are 4 rules that a tree has to follow to be a red-black tree.

1. Every node has a color either red or black.
2. Root of tree is always black.
3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4. Every path from root to a NULL node has same number of black nodes.

So I drew the tree below in a quiz, and apparently it's not valid. Could someone tell me why this tree is invalid?

Thank you!

# Answer
If you go to the empty leaf from the root in the pattern \[Right, Left\], you get to an empty leaf encountering 1 black node. If you go \[Right, Right, Left\] or \[Right, Right, Right\], you get to an empty leaf hitting 2 black nodes. This is not allowed in a Red Black Tree because by definition a path from root to an empty leaf should contain the same amount of black nodes as every other path from root to an empty leaf.

The other important thing to know is that NULL nodes (leaves) aren't drawn; only the internal nodes are drawn. By convention, all leaves (NULL nodes) automatically are considered to be colored black.
> 5 votes

# Answer
There are 5 nodes with \<2 children. In red-black trees, all nodes with \<2 children must have the same black-depth, i.e. the number of black parents between it and the root, a black node with \<2 children is a +1 in its own black depth. The node directly to the right of the root has black depth of 1 while every other node with \<2 children has a black depth of 2.
> 0 votes

---
Tags: data-structures, binary-trees, search-trees, balanced-search-trees
---


# Question
Title: What kind of math problems can be solved by automated theorem provers?
Can I prove following statements with using available automated theorem provers?

1. $(a+b)^2=a^2+b^2+2ab$.
2. If $ 11 \mid 2a-3b$, then $ 11 \mid 7a-5b $.
3. If $ ax^2+bx+c=0$, then $x=\frac{-b\pm\sqrt{b^2-4ac} }{2a}$.
4. If $a$ is even then $4a$ is even.

and so on!

I am asking this question because I just found the application of Automated theorem provers in proving theorems in logic.

# Answer
> 20 votes
Most of your statements are elementary algebra, so these can be proved automatically by a computer algebra system (CAS), such as Maple or Mathematica.

(In case you're interested in the mathematics behind CAS, I can recommend the book *Modern Computer Algebra* by Joachim von zur Gathen and Jürgen Gerhard, a beautiful book, considered the 'bible' of the field)

Automated theorem proving tends to be mostly a case of doing heuristic search on a structure that represents proofs, if the proof is not one of the few cases for which there is an algorithm that can conclusively solve it. Given that this statements aren't very complicated, it is likely that an automated prover is able to 'find' a proof.

However, I think it is interesting to say a bit more about the statements for which there are nice algorithms:

Statement 3 is (a very simple case of) about roots of a (system of) polynomial equations and can be solved by finding a Gröbner basis with Buchberger's algorithm. The Gröbner basis and Buchberger's algorithm to find one are very nice tools for automated theorem proving. For example, we can even automatically prove elementary theorems in geometry by automatically transforming the problem to finding a root of a polynomial equation in a clever way!

Another interesting class of theorems are statements expressible in quantifier-free Presburger arithmetic (in particular, this arithmetic is without multiplication, so this doesn't apply to your statements), as there is an algorithm to solve all such statements, even though the algorithm is a bit slow.

---
Tags: automated-theorem-proving
---


# Question
Title: Showing that there exists an algorithm, that converts NFA to DFA under some cirumstances
We are given NFA $A$, which for every input word $w$ has at most 10 runs over word $w$, beginning at the starting state. Show that there exists an algorithm, that converts such NFA to DFA in polynomial time. We don't need that algorithm to work if given automata is not such a NFA.

I think we need to construct DFA with $2^{10}$ states, such that every state would correspond to some run in the NFA - but im not sure about the details.

Any ideas?

# Answer
> 1 votes
The main idea is that if the NFA has at most 10 runs over each word, then when reading a word, at any given point the NFA can be in at most 10 states. Therefore in the powerset construction it suffices to consider sets of at most 10 states, of which there are polynomially many.

All remaining details are left to you.

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


# Question
Title: How to check if $m$ numbers in a sequence satisfy a condition, such that all these numbers are spaced apart by at least $k$?
Suppose we have a sequence $s$ with $n$ elements from $s\[1..n\]$. I want to check if there exists $m \leq n$ elements in this sequence that each satisfy some simple condition (that can be tested in $O(1)$ for each $s\[i\]$), such that all of these elements are spaced apart by at least $k$. Is there an algorithm that can achieve this in $O(n)$ time?

For example, suppose we have $s=\[3, 4, 13, 2, 6, 4, 1, 9, 11, 5\]$ and we are trying to verify if there exists $m=3$ elements that satisfy the condition $s\[i\] \leq 4$ and are spaced apart by at least $k=2$. This is true because $s\[1\] = 3, s\[4\] = 2, s\[7\] = 1$ and $s\[1\], s\[4\], s\[7\]$ are spaced apart by at least $2$.

A naive solution that I thought of involved iterating through the sequence and recording each $s\[i\]$ that satisfies the condition, and then for each $s\[i\]$, trying to find $m-1$ others that don't violate the spacing requirement. I'm not sure how I can do this in $O(n)$ time. Is it possible?

# Answer
As Yuval Filmus said in the comment, you can solve the optimization version (finding maximum viable $m$, which is a stronger version) by dynamic programming.

Let $m\_i$ be the maximum viable elements of the sub-problem on $s\[1..i\]$. Consider the sub-problem on $s\[1..i\]$. An optimal solution has two choices.

1. It excludes $s\[i\]$, then it must choose an optimal solution of the sub-problem on $s\[1..(i-1)\]$.
2. It includes $s\[i\]$, then it cannot include $s\[i-1\],\ldots,s\[i-k+1\]$, and must choose an optimal solution of the sub-problem on $s\[1..(i-k)\]$.

Now you can write a recursion formula for $m\_i$, and compute $m\_1,\ldots,m\_n$ in order in $O(n)$ time.
> 2 votes

---
Tags: algorithms, arrays, subsequences
---


# Question
Title: How to efficiently find line-segment intersections between two sets?
So I'm building this iterative simulation of a surface (composed of line segments) that cannot self-intersect, which means I have to check intersections at the end of a timestep. The thing is, I know, at the beginning of every timestep, that no intersections exist within the set of all line segments that constitute the surface, and at every timestep, a fixed number of nodes is altered (if this produces intersections, the simulation resets). Let's call the set of all lines after an alteration N and the lines that have been altered K. I then know that I should only look for intersections **within K** and **between K and {N - K}**, because I know there can be no intersections within {N - K}. This is equivalent to wanting to find intersections **between K and N**.

When I first tackled this problem, I just implemented sweepline, but now I realize that it finds intersections **within** a set. As far as I can tell, adapting the algorithm to find intersections between **segments in a set X** and **segments in a set Y** is quite tricky; I haven't been able to work that out. The only things I thought of is doing brute force (which amounts to |K| * |N|) and just ignoring K and applying sweepline, which is |N|lg|N|. If there's a way to combine the best of both approaches,I'd expect there to be a big difference in the performance of my code. Is there such a way?

# Answer
> 3 votes
The problem you describe is known as the *red-blue intersection problem*. Here, we have a red set of $n\_1$ segments and a blue set of $n\_2$ segments and we know that there are only intersections between segments of different colour. Although this special case has been extensively studied, the $O(n\log n + k)$ algorithm, with $n=n\_1+n\_2$ is still optimal1 when if we have no further information.

In particular, we cannot easily combine the two approaches. To get some intuition on why adapting the sweepline algorithm in particular doesn't simply work, consider the case where $n\_1=1$ and $n\_2 = 1000$ and take a large blue segment such that the rectangle that has this segment as a diagonal contains all endpoints of the red segments. In this case, all red segments *could* be intersecting the single blue segment, so the sweepline has to consider all points in $n\_2$ as event points and hence it is possible we have to spend at least $\Omega(n\_2\log n\_2)$ time on our sweepline algorithm.

---

There is one special case in which we can be faster. A planar subdivision is *simply connected* when each closed path over the edges within the same region of a subdivision can be topologically contracted to a point, i.e. a region cannot contain another region (similar to a simply connected space). If the two sets of segments form two simply connected planar subdivisions, we can use the algorithm by U. Finke and K. Hinrichs. to find all intersections in $O(n+k)$ time.

1. Optimal if $n\_1\approx n\_2$. Of course, if $n\_2 \ll\log n\_1$, we can do better with the naive algorithm, but that is rarely the case.

---
Tags: algorithms, computational-geometry, polygons
---


# Question
Title: Show that C(n) = {a^k | k is a multiple of n} is a regular language
I came across this question in an exam book and was unable to find a solution:

Prove that C(n) = {a^k | k is a multiple of n} is a regular language for every natural number n ≥ 1.

I wasn't able to construct a DFA as the number n is left variable in the original question. Is it possible to construct a DFA with a variable number of states?

Any help would be greatly appreciated. Thank you!

# Answer
It’s easy to construct a DFA which recognize $a^n$.

Then add an $\epsilon$ transition from all its final state to its initial state.
> 1 votes

---
Tags: regular-languages, finite-automata, proof-techniques
---


# Question
Title: What structure is used for accessing the most frequent elements top k over a stream of elements?
Let's say you want the top k elements. Then given the array, there is an O(n) O(n) space approach. But what if you have a stream of elements, this means that each time you'd append an element to the end of your list, you'd have to do this O(n) time O(n) space approach. Let's say your elements are distinct elements of a set. You can maintain a frequency map, but you'd still have to do the O(n) approach to find the top k elements. Is this is what is done in production? What data structure is used to efficiently keep top k elements with updated frequencies?

# Answer
> 2 votes
This is possible in $\mathcal O(\log n)$ time using self-balancing tree (or heap), using frequencies as keys. This extends the node to keep a list (or once more a tree) of elements of equal frequency.
To access top k elements you can either augment the tree with additional pointers to allow traversal in $k$ steps or use $\mathcal O(\log n)$ recursive one.
Better approach is to keep $k$ elements in that tree-like structure and in another one the rest.

If elements are fixed, you can use hash-table to store them, so keeping a table per frequency would result in expected time $\mathcal O(1)$, here using knowledge of the elements will help to minimize number of collisions.

---
Tags: algorithms
---


# Question
Title: How realistic is the i.i.d assumption in the definition of Shannon's entropy?
Let me first say I come from a physics background and have about zero exposure to computer science, so the question may be very naive. Shannon's entropy looks perfectly natural and useful from a statistical/thermal physics point of view, but now I'm trying to understand how it is applied for real computers.

Normally the messages we want to store and process in a computer have grammar and meanings, which seems to suggest the symbols constituting the message must follow some conditional probability distribution, and the utterance of the symbol at the nth position should change the probability distribution of the symbol that will appear at the (n+1)-th position. However, in Shannon's definition symbols are assumed to be independent and identically distributed random variables, which seems to be far from realistic, so how come it is still a useful concept for computers?

# Answer
> 4 votes
No. Shannon's definition is perfectly general.

There is a special case when the symbols are iid random variables, and you might have seen a formula for that special case (which is indeed simpler), but the definition is fully general. Note that when we write the entropy $H(X)$, you should take the random variable $X$ to be the entire sequence of symbols. Then the standard definition applies directly, and doesn't assume that each individual symbol in $X$ is iid.

---
Tags: information-theory, entropy
---


title: Is $O(|V||E|)$ polynomial time?

text:
# Question
Title: Is $O(|V||E|)$ polynomial time?
If an algorithm runs in $O(|V||E|)$, is its running time bounded by some polynomial of $|V|+|E|$? If not, what is its running time called?

# Answer
> 3 votes
Since $(a+b)^2 = a^2 + 2ab + b^2 \geq 2ab$, it is indeed true that $|V||E|$ is bounded by a polynomial in $|V|+|E|$.

---
Tags: asymptotics
---


# Question
Title: How do I know the height from recursion tree of $T(n)=4T(n/2+2)+n$?
I already saw this answer. But I didn't understand totally.

So I found the solution to this equation $T(n)=4T(n/2+2)+n$.

Here is the recursion tree. But I can't compute the height as $lgn$ from this tree.

How to compute height? (Image is from solution)

# Answer
Suppose that $n = 2^m+4$. Then $$ \frac{n}{2} + 2 = \frac{2^m+4}{2} + 2 = (2^{m-1} + 2) + 2 = 2^{m-1} + 4. $$ We conclude that if $n = 2^m+4$ then the height is $m$ (or $m+1$, depending on how you count), with $T(5)$ in the leaves. This shows that for this type of $n$, the height of the recursion is $\log\_2(n-4)$ (or $\log\_2(n-4)+1$, depending on how you count).

For general $n$, the exact answer depends on the interpretation of $n/2$ — whether you take floor, ceiling, or anything else — but the height will still be very close to $\log\_2 n$.
> 5 votes

---
Tags: recurrence-relation
---


# Question
Title: Why is this expression (A and ¬A |= C) entailed?
Hopefully I am posting this in the right place, I am currently in a course of knowledge representation, and I came across an exercise about entailment: $$A\land\neg A\vDash C\\,.$$

I would argue that this expression is not entail, but it is actually entailed, but I don't see how, can you help me figure out why?

# Answer
> 10 votes
The statement $X\vDash Y$ means "every assignment to the variables that makes $X$ true also makes $Y$ true." Or to put it another way, "There is no assignment of variables that makes $X$ true but fails to make $Y$ true." Well, there's no assignment of variables that makes $A\land\neg A$ true, so there's certianly no assignment that makes $A\land\neg A$ true and also makes $C$ false. So $A\land\neg A\vDash C$ is a true statement.

False entails anything is a rule, analogous to false implies anything.

---
Tags: logic, knowledge-representation, reasoning
---


# Question
Title: Minimum cost to convert one array to another
Given two arrays $A$ and $B$ of integers, both of size $N$, such that for all $0 \le i \le N-1$, $A\[i\] \ge B\[i\]$, we have to convert array $A$ to array $B$. For this we can do only one type of operation: choose some $l$ and $r$ ($0 \le l \le r \le N-1$) and set the values of $A\[l\],A\[l+1\],\ldots,A\[r\]$ to $k$, where $k \le A\[i\]$ for all $l \le i \le r$. Find out minimum operations to convert $A$ to $B$.

I was thinking about dynamic programming solution but could not figure it out.

# Answer
Let distinct elements of $B$ be $b\_1,b\_2,\ldots$ where $b\_1\>b\_2\>\cdots$. There must be an optimal solution where it first sets a range to $k\_1$ then set a range to $k\_2$ and so on, such that $k\_1\ge k\_2\ge\cdots$ (otherwise one can swap related operations to meet the constraint without changing the result), and $k\_1,k\_2,\ldots\in\\{b\_1,b\_2,\ldots\\}$ (otherwise, say $k\_i\notin\\{b\_1,b\_2,\ldots\\}$, one can delete the $i$th operation without changing the result).

Using the property above, we have the following greedy algorithm.

Let $B\[i\_1\],B\[i\_2\],\ldots$ ($i\_1\<i\_2\<\cdots$) be the greatest elements, i.e. $b\_1$. The algorithm firstly sets $A\[i\_1\],A\[i\_2\],\ldots$ to $b\_1$ using as little operations as possible. More specifically, it checks whether $A\[i\_1\]\>b\_1$ to see whether an operation is required to set $A\[i\_1\]$ to $b\_1$. If so, it then checks whether $A\[i\_1+1\],\ldots,A\[i\_2-1\]\ge b\_1$* by range minimum query to see whether this operation can be merged with the operation corresponding to $A\[i\_2\]$. It then goes on with $A\[i\_2\],A\[i\_3\],\ldots$ For example, say

```
A: 3 3 3 3 2 1 3
B: 2 1 2 1 2 1 2

```

Now $b\_1=2$ and $i\_1=0, i\_2=2, i\_3 = 4, i\_4=6$. It requires 2 operations to set $A\[i\_1\],A\[i\_2\],\ldots$ to $b\_1$: first setting $A\[0\], \ldots, A\[2\]$, then setting $A\[6\]$.

The algorithm then repeats the above process for $b\_2,b\_3,\ldots$

This algorithm runs in $O(n\log n)$.

---

*Note, for example, when dealing with $b\_2$ instead of $b\_1$, no operation can be performed on a range containing $i\_j$ for some $j$, otherwise $A\[i\_j\]$ will be less than $B\[i\_j\]$ and cannot be recovered. Therefore we must also check this constraint here. This can be done by maintaining a sorted index array of all elements greater than $b\_m$ when dealing with $b\_m$.
> 1 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: Show that the following language is not recursive:
$L = \\{w \mid M\_w \text{exists and it accepts a word } x\_1 = 0x \text{ if and only if it accepts } x\_2 = 1x\\}$ ($x \in \Sigma^\*$, so $x\_1$ is starting with a 0 and $x\_2$ is obtained from $x\_1$ by changing the first 0 to a 1).

# Answer
> 1 votes
We say a language $L$ is *good* if "$0x\in L$ if and only if $1x\in L$". Let $\mathcal{L}$ be the set of all good languages. Then you are trying to determine whether the language recognized by a given TM belongs to $\mathcal{L}$. Since $\mathcal{L}$ is non-trivial, according to Rice's theorem, this is undecidable.

If you want a proof without Rice's theorem, you can take a look at the proof of Rice's theorem and try to write a proof for this specific problem. This is not hard.

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


# Question
Title: Closed-Form Expression for Recursive Function
> Let $k \in \mathbb{N}$ and $m \in \mathbb{R}$. Consider the following function $S\colon \mathbb{R} \times \mathbb{N} \to \mathbb{R}$: $$ S(m,k) = \begin{cases} 3m & \text{if } k = 0, \\ 4S(\tfrac{m}{2},k-1)+3m & \text{if } k \geq 1. \end{cases} $$ Find a closed-form expression for $S(m,k)$ using repeated substitution.
>
> Prove the correctness of the expression you obtained.

When using repeated substitution, I found the formula $$ \sum\_{i=0}^{k} 4^i\frac {3m}{2^i}, $$

whereas the solution has the formula,

$$ 6m2^k - 3m.$$

I wrote my sum (as well as the original recurrence relation) in Python, and plugged in values from 0 to a 100 for both $m$ and $k$.

For some reason, the sum gets wrong values starting at $m, k = 47, 47$, and follows a weird pattern after that.

Does anyone have any idea what is going on?

# Answer
> 1 votes
The two formulas agree: $$ \sum\_{i=0}^k 4^i \frac{3m}{2^i} = 3m \sum\_{i=0}^k 2^i = 3m(2^{k+1}-1) = 6m2^k - 3m. $$

---
Tags: recurrence-relation
---


# Question
Title: Difference between Time-sharing computers and computers which use Round Robin scheduling algorithm?
So maybe I'm confused in these concepts

but i thought that time sharing computer is a computer which the processor switches between different processes quickly to achieve a good response time

but isn't this the same as Round Robin algorithm?! i mean aren't we scheduling between different processes in Time sharing computer just like Round robin? or am i missing something here? what is the difference?

# Answer
No, they are not equivalent, but you are right to note a similarity.

Yes, a time sharing computer is one in which the computer switches between different processes. The *schedular* is the part of the operating system that determines when to switch between processes, and which process to switch to. A round robin scheduler is one particular type of scheduling strategy that could be used in a time sharing computer, but there are other possible scheduling strategies as well.
> 2 votes

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Does Gödel's first incompleteness theorem apply to quantifier-free arithmetics?
Gödel's first incompleteness theorem states roughly that *"for any axiomatization of arithmetic, there are statements that can neither be proven to be false nor true."*

Does this *still hold when it comes to quantifier-free statements*?

I.e. if we have the structure of arithmetic: $(\mathbb N, +,\cdot, 0,1)$, and we restrict to sentences $\Phi^{QF}$ about this structure that don't contain $\exists, \forall$, can we then for all $\phi\in \Phi^{QF}$ either prove or disprove $\phi$?

# Answer
> 4 votes
What you are referring to is called Baby Arithmetic ($\mathsf{BA}$) in Peter Smith's book *An introduction to Gödel's Theorems*.

> $\mathsf{BA}$'s language \[has\] one single individual constant $0$, the one-place function symbol $S$, and the two-place function symbols $+$ and $\times$. \[...\] it lacks quantifiers and variables.

$\mathsf{BA}$ is complete, negation complete, and decidable.

# Answer
> 0 votes
I would say that any quantifier-free sentence $\varphi$ is true in $\mathbb{N}$ must be provable from, say, $PA^-$, since it can only be a boolean combination of things like $t\_1(n\_1,\dots,n\_a)\leq t\_2(m\_1,\dots,m\_b)$, where the $n$'s and $m$'s are just expressions of the form $1+\dots+1$, and it can be seen quite easily that weak theories (like $PA^-$) decide all of them.

i think this would also be true for formulas where only bounded quantifiers are used (this follows for example from absoluteness of $\Delta\_0$ formulas by end-extensions of $\mathbb{N}$).

---
Tags: incompleteness
---


# Question
Title: Generating all words of length n in a CFG
Given a CFG for a (infinite) language $L$, is there an efficient algorithm that generates all possible words of length $n$ in $L$?

Preferably efficient in time, and with low memory usage.

I'm only interested in the words themselves - not their derivations. If the language is ambiguous and has multiple derivations for a word it would be nice if there is an efficient way to make sure each word is only output once.

The order of the words is irrelevant. If time can be saved by preprocessing the grammar $G$ (e.g. to CNF) then that's perfectly fine.

# Answer
> 2 votes
I can suggest one possible algorithm based on memoization of a rather naive recursive algorithm, with some corner cases cleaned up. I don't know if there might be a better approach.

Convert the grammar to Chomsky normal form. Let $L(A,\ell)$ denote the set of words of length $\ell$ in $L(A)$ (i.e., all words of length $\ell$ that can be derived from $A$). We'll construct an algorithm to compute $L(S,n)$ recursively, where $S$ is the start symbol of the grammar.

The recursive algorithm for computing $L(A,\ell)$ works as follows. If we have a rule $A \to \varepsilon$ and $\ell=0$, add $\varepsilon$ to the output; for each rule $A \to a$, if $\ell=1$, add $a$ to the output; for each rule $A \to BC$ and each $0 \le i \le \ell$, add $uv$ to the output for each $u \in L(B,i)$ and $v \in L(C,\ell-i)$.

Memoize this algorithm.

As an optimization, when considering a rule $A \to BC$, only iterate over $i$ such that $0 \le i \le \ell$ and $L(B,i)$ is non-empty and $L(C,\ell-i)$ is non-empty. This prevents generating a long list of candidate values for $u$ that you'll never use. (You can precompute whether $L(A,i)$ is empty or not, for each symbol $A$ and each $0 \le i \le n$, in $O(n^2 |G|)$ time using dynamic programming, where $|G|$ is the number of rules in the grammar.) Or equivalently, when you implement the recursive algorithm, implement it using lazy lists, so that the output of $L(A,\ell)$ is a lazy list with elements generated on demand.

With this optimization, I think the total running time of this algorithm should now become something like $O(m n^2 |G|)$, where $m$ is the total number of words of length $n$ in $L$ and $|G|$ is the number of rules in the grammar. Maybe there is a tighter bound on the running time: this might be pessimistic.

---
Tags: algorithms, context-free, enumeration
---


# Question
Title: All possible Red Black Trees with this set {1,2,3,4,5}
I have to write all possible Red Black Trees which can represent these 5 numbers {1,2,3,4,5}.

Now we have 120 ways to write 1,2,3,4,5

```
{1,2,3,4,5} {1,2,3,5,4} {1,2,4,3,5} {1,2,4,5,3} {1,2,5,3,4}
{1,2,5,4,3} {1,3,2,4,5} {1,3,2,5,4} {1,3,4,2,5} {1,3,4,5,2}
{1,3,5,2,4} {1,3,5,4,2} {1,4,2,3,5} {1,4,2,5,3} {1,4,3,2,5}
{1,4,3,5,2} {1,4,5,2,3} {1,4,5,3,2} {1,5,2,3,4} {1,5,2,4,3}
{1,5,3,2,4} {1,5,3,4,2} {1,5,4,2,3} {1,5,4,3,2} {2,1,3,4,5}
{2,1,3,5,4} {2,1,4,3,5} {2,1,4,5,3} {2,1,5,3,4} {2,1,5,4,3}
{2,3,1,4,5} {2,3,1,5,4} {2,3,4,1,5} {2,3,4,5,1} {2,3,5,1,4}
{2,3,5,4,1} {2,4,1,3,5} {2,4,1,5,3} {2,4,3,1,5} {2,4,3,5,1}
{2,4,5,1,3} {2,4,5,3,1} {2,5,1,3,4} {2,5,1,4,3} {2,5,3,1,4}
{2,5,3,4,1} {2,5,4,1,3} {2,5,4,3,1} {3,1,2,4,5} {3,1,2,5,4}
{3,1,4,2,5} {3,1,4,5,2} {3,1,5,2,4} {3,1,5,4,2} {3,2,1,4,5}
{3,2,1,5,4} {3,2,4,1,5} {3,2,4,5,1} {3,2,5,1,4} {3,2,5,4,1}
{3,4,1,2,5} {3,4,1,5,2} {3,4,2,1,5} {3,4,2,5,1} {3,4,5,1,2}
{3,4,5,2,1} {3,5,1,2,4} {3,5,1,4,2} {3,5,2,1,4} {3,5,2,4,1}
{3,5,4,1,2} {3,5,4,2,1} {4,1,2,3,5} {4,1,2,5,3} {4,1,3,2,5}
{4,1,3,5,2} {4,1,5,2,3} {4,1,5,3,2} {4,2,1,3,5} {4,2,1,5,3}
{4,2,3,1,5} {4,2,3,5,1} {4,2,5,1,3} {4,2,5,3,1} {4,3,1,2,5}
{4,3,1,5,2} {4,3,2,1,5} {4,3,2,5,1} {4,3,5,1,2} {4,3,5,2,1}
{4,5,1,2,3} {4,5,1,3,2} {4,5,2,1,3} {4,5,2,3,1} {4,5,3,1,2}
{4,5,3,2,1} {5,1,2,3,4} {5,1,2,4,3} {5,1,3,2,4} {5,1,3,4,2}
{5,1,4,2,3} {5,1,4,3,2} {5,2,1,3,4} {5,2,1,4,3} {5,2,3,1,4}
{5,2,3,4,1} {5,2,4,1,3} {5,2,4,3,1} {5,3,1,2,4} {5,3,1,4,2}
{5,3,2,1,4} {5,3,2,4,1} {5,3,4,1,2} {5,3,4,2,1} {5,4,1,2,3}
{5,4,1,3,2} {5,4,2,1,3} {5,4,2,3,1} {5,4,3,1,2} {5,4,3,2,1}

```

But this is too much, I need to construct 120 RBT and then take out the ones which are the same, is there any tip how can I take some out immediately before even trying to construct the RBT for them ?

# Answer
Testing all 120 insertion orders is indeed much to much work in order to check out all trees. Moreover, there might be trees that are valid, but which are not found by inserting keys in some order.

A better appraoch would be to designing the trees by level. The number of black nodes on each path is equal, so a RB-tree with five keys can at most have two levels with black nodes: three levels would need seven keys.

It is perhaps helpful to consider a black node together with its red children as one single node with 1,2 or 3 keys (and 2,3 or 4 children). (In that way we get 2-3-4-trees.) Now either (1) the root has 2 keys and three children with each a single child, or (2) the root has 1 key with 2 children with a total of 4 keys. Remember a node with two keys can be represented in two ways as a RB-tree (the red child can be left or right.)

According to the OEIS there are eight such trees. Good luck.
> 1 votes

---
Tags: data-structures, search-trees, enumeration, balanced-search-trees, binary-search-trees
---


title: CFG With unambiguous if-else statement

text:
# Question
Title: CFG With unambiguous if-else statement
I am writting a small compiler for a compilers' class. The algorithm is having a shift/reduce conflict when I try to enclose if-else with braces '{', '}'. The non-ambiguous if-else statement I took from the dragon book, which turns to be ambiguous when I add the braces. To build the parser and test it I am using the Ply library written in Python.

The grammar terminals/nonterminals specification is backwards here - Uppercase strings are the terminals and Lowercase are the non-terminals. Also the grammar below is not ambiguous untill you try to enclose the if-else with {} which is tokenized as LBRACE and RBRACE.

Below is the grammar specification:

```
Rule 0     S' -> program
Rule 1     program -> function_definition program
Rule 2     program -> empty
Rule 3     function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN block
Rule 4     function_definition_args -> var_list
Rule 5     function_definition_args -> empty
Rule 6     var_list -> var_declaration COMMA var_list
Rule 7     var_list -> var_declaration
Rule 8     var_declaration -> data_type ID
Rule 9     data_type -> VOID
Rule 10    data_type -> INT
Rule 11    data_type -> FLOAT
Rule 12    data_type -> STRING
Rule 13    data_type -> CHAR
Rule 14    block -> LBRACE statements RBRACE
Rule 15    statements -> statement statements
Rule 16    statements -> empty
Rule 17    statement -> matched_statement
Rule 18    statement -> unmatched_statement
Rule 19    matched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE matched_statement RBRACE
Rule 20    matched_statement -> command
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE
Rule 23    logical_expression -> logical_term OR logical_term
Rule 24    logical_expression -> logical_term
Rule 25    logical_term -> logical_factor AND logical_factor
Rule 26    logical_term -> logical_factor
Rule 27    logical_factor -> boolean_statement
Rule 28    logical_factor -> NOT logical_factor
Rule 29    logical_factor -> LPAREN logical_expression RPAREN
Rule 30    boolean_statement -> value comparison_op value
Rule 31    boolean_statement -> value
Rule 32    value -> ID
Rule 33    value -> NUMBER
Rule 34    comparison_op -> LESS_THAN
Rule 35    comparison_op -> LESS_EQUAL
Rule 36    comparison_op -> GREATER_THAN
Rule 37    comparison_op -> GREATER_EQUAL
Rule 38    comparison_op -> EQUAL
Rule 39    command -> compound_statement
Rule 40    command -> simple_statement
Rule 41    compound_statement -> WHILE LPAREN logical_expression RPAREN block
Rule 42    simple_statement -> expression
Rule 43    expression -> expression PLUS term
Rule 44    expression -> expression MINUS term
Rule 45    expression -> term
Rule 46    term -> term TIMES factor
Rule 47    term -> term DIVIDE factor
Rule 48    term -> factor
Rule 49    factor -> NUMBER
Rule 50    factor -> ID
Rule 51    factor -> LPAREN expression RPAREN
Rule 52    uminus_expression -> MINUS LPAREN expression RPAREN
Rule 53    empty -> <empty>
Rule 54    function_definition -> DEFINE data_type ID LPAREN function_definition_args RPAREN error

```

The following change bellow is the one which causes the shif/reduce conflicts

```
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE

```

# Answer
If you insist that the alternatives in a conditional statement be blocks, then the dangling-else ambiguity vanishes.

The dangling else ambiguity is something like this, where the `else` could be attached to either `if`:

```
if (a > 3) if (b > 4) do_something else do_something_else

```

However, if the statements in the conditional must be surrounded by braces, that is a syntax error. You would have to write either:

```
if (a > 3) { if (b > 4) { do_something } else { do_something_else } }

```

or

```
if (a > 3) { if (b > 4) { do_something } } else { do_something_else }

```

and both of those are quite explicit about which `if` the `else` belongs to.

In effect, a braced statement list (or `block`, as you refer to it in the context of a `while` statement) is a `matched_statement`, and you could just add it to the set of possibilities for that non-terminal. But that's only necessary if you want the braces to be optional; if you're going to require them, then you can scrap all that matched- and unmatched- statement stuff, and just use `block` in your `if` statement, just as with your `while` statement.

In any case, the problem is

```
Rule 20    matched_statement -> command
Rule 21    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE command RBRACE
Rule 22    unmatched_statement -> IF LPAREN logical_expression RPAREN LBRACE matched_statement RBRACE ELSE LBRACE unmatched_statement RBRACE

```

Since `matched_statement -> command` (rule 20), the `RBRACE` in rule 21 induces a shift-reduce conflict. Assuming a `command` has just been reduced, the parser has to decide whether rule 20 should be applied (a reduce), which is necessary if the input is the start of rule 22, or whether the `RBRACE` should just be shifted, necessary if the input is the start of rule 21. And it can't know that by just looking at the `RBRACE`, since that is the same in both rules.

However, as I said, it doesn't matter. You don't need two different non-terminals for a `block`, and just using `block` will avoid the problem.
> 1 votes

---
Tags: formal-languages, compilers
---


# Question
Title: How to find middle element of doubly linked list using head and tail?
Is there a way possible to find the middle element of a doubly linked list using head and tail. I tried traversing to the next element from the starting node and the previous element from the end node and check if the reference of both is same or not. This works fine if there are odd number of elements in the list. I am not able to find when should I stop in case the number of elements in the list is even.

```
while(head.next != end.previous) {
    head = head.next;
    end = end.previous;
}

```

# Answer
Start with a pointer $x$ at the beginning and a pointer $y$ at the end. Repeatedly execute the following steps:

* If $x=y$, stop.
* Advance $x$ forward.
* If $x=y$, stop.
* Advance $y$ backward.

This should work out for both even and odd length.
> 2 votes

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


title: Variant of 3-SAT is NP complete?

text:
# Question
Title: Variant of 3-SAT is NP complete?
Consider a restriction on 3-SAT in which no literal occurs in more than two clauses. How do we show that this is NP complete ?

(edit - I was getting confused over the definition on the 3-SAT,here by 3-SAT it implies that a clause can have at most 3 literals.)

# Answer
I have found a reduction from 3-SAT.

For every instance of variable $y$, I will put a new variable $y\_i$ in its place. Suppose there were $K$ such instances then after replacing each instance of $y$, I will add clauses $\bar y\_1 \vee y\_2, \bar y\_2 \vee y\_3, \ldots, \bar y\_K \vee y\_1$. This ensures that $y\_1,\ldots,y\_K$ will be assigned the same value.
> 2 votes

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


title: Optimal 4-input sorting network

text:
# Question
Title: Optimal 4-input sorting network
In his paper *The Bose-Nelson Sorting Problem* (1973, Chapter 15 of *A Survey of Combinatorial theory* on page 163 available on Google books), Knuth says that the optimal bound of 5 comparators for a 4-input sorting network comes from an "elementary information-theoretic argument".

Information theory is not a part of my tool set, yet I have to prove this result.

---

I have managed to construct a 5-comparator network that solves the problem, and am trying to prove that any 4-comparator network does not work.

I have managed to prove that 3 comparators are needed if we want the top output to be the max of all inputs. In fact, for each input, at least three comparators are needed, but I cannot prove that they are different for each output.

# Answer
Suppose that there were a network using only 4 comparators. The correct order of the inputs can be recovered by known the result of all 4 comparisons, since given these results, you can simulate the effect of the network. However, there are only $2^4 = 16$ possible results of the comparisons, whereas there are $4! = 24$ possible orders of inputs.
> 2 votes

---
Tags: logic, sorting
---


# Question
Title: Bisimilarity and Trace Equivalence in Labelled Transition Systems
I'm a bit confused regarding the relation between trace equivalence and bisimilarity. These lecture notes I found and a few others documents I've read state that "if an LTS is deterministic then two states are bisimilar if they are trace equivalent".

When reading around the topic I found this page, which shows the following image:

These LTS' are trace equivalent and deterministic(?), why does the rule not hold that they are then bisimilar?

# Answer
The answer is that the LTS on the left isn't deterministic, as the label (or action) `open_door` doesn't go to a single state and hence that action is non-deterministic.

This example shows that determinism is indeed required for trace equivalence and bisimilarity to be equivalent.
> 2 votes

---
Tags: terminology
---


title: Path in a graph with durations

text:
# Question
Title: Path in a graph with durations
I have the following problem:

given

* a directed graph $G=(V,E,d)$, where $d:V\to\mathcal{I}(\mathbb{Q}\_0^+\cup\\{+\infty\\})$ *(here $\mathbb{Q}\_0^+$ denotes the set of non-negative rationals and $\mathcal{I}(\mathbb{Q}\_0^+\cup\\{+\infty\\})$ the set of intervals, bounded or unbounded above, with non-negative rational bounds)* is a function associating with each vertex $v\in V$ a "minimum/maximum duration" $d(v)=\[a,b\]$ for some $a\in \mathbb{Q}\_0^+,b\in \mathbb{Q}\_0^+\cup\\{+\infty\\}$ and $a\leq b$,
* two vertices $s,t\in V$ and
* an integer $h$ *encoded in binary*,

we have to decide whether or not there exist

* a path in $G$, possibly with repeated vertices and edges, $v\_0 \cdot v\_1 \cdots v\_{n-1}\cdot v\_n$, with $v\_0=s$ and $v\_n=t$ and
* a list of values $d\_0,\ldots,d\_n\in\mathbb{Q}\_0^+$, such that $\sum\_{i=0}^n d\_i = h$ and for all $i=0,\ldots, n$, $d\_i\in d(v\_i)$.

Intuitively, we have to find a path in $G$, possibly where we get to the same vertices/edges also more than once, and where we remain in each vertex a non-negative rational amount of time allowed by the minimum/maximum duration function, such that the overall time of the path equals $h$.

This can be solved easily in PSPACE. We conjecture it to be in NP (we already know it is NP-hard!). This is not trivial to prove, as we may have $h\in\Theta(2^n)$, for instance. Thus the required path may have length exponential in both $|V|$ and in the binary encoding of $h$.

Is this problem in NP?

# Answer
> 2 votes
This solution is by Gerhard Woeginger.

In order to prove that this problem belongs to NP, we provide a polynomial-size certificate, and then we show how to check it in deterministic polynomial time.

The certificate is just the following: a set of integers $\\{x\_{u,v}\mid (u,v)\in E\\}$. Intuitively, $x\_{u,v}$ is the number of times the solution path traverses $(u,v)$.

We now describe the verification algorithm.

1. We consider the subset $E'$ of edges of $G$, $E':=\\{(u,v)\in E\mid x\_{u,v}\>0\\}$. We check whether $E'$ induces a strongly (undirected) connected subgraph of $G$.
2. We check whether

* $\sum\_{(u,v)\in E'} x\_{u,v}=\sum\_{(v,w)\in E'} x\_{v,w}$, for all $v \in V\setminus\\{s,t\\}$;
    * $\sum\_{(u,s)\in E'} x\_{u,s}=\sum\_{(s,w)\in E'} x\_{s,w}-1$;
    * $\sum\_{(u,t)\in E'} x\_{u,t}=\sum\_{(t,w)\in E'} x\_{t,w}+1$.
3. For all $v \in V\setminus\\{s\\}$, we define $y\_v:=\sum\_{(u,v)\in E'} x\_{u,v}$, i.e., the number of times the solution path gets into $v$. Moreover, $y\_s := \sum\_{(s,u)\in E'} x\_{s,u}$.
4. We check whether there exist real values $z\_v$, for every $v \in V$, such that

* $d\_{min}(v)\cdot y\_v \leq z\_v \leq d\_{max}(v)\cdot y\_v$ (here $d\_{min}(v)$ and $d\_{max}(v)$ denote resp. the lower and the upper bound of the rational interval $d(v)$), and
    * $\sum\_{v \in V} z\_v = h$.

We now sketch the correctness:

Steps 1. and 2. together check that the values $x\_{u,v}$ for the arcs specify a directed Eulerian path from $s$ to $t$ (we refer to http://www.maths.manchester.ac.uk/~mrm/Teaching/DiscreteMaths/LectureNotes/EulerianMultigraphs.pdf)

Steps 3. and 4. calculate $z\_v$, for all $v\in V$, which is the total waiting time of the path on the node $v$. We observe that the (in)equalities of step 4. form a linear program (LP), which can be solved in deterministic polynomial time (e.g., using the ellipsoid algorithm).

---
Tags: graphs, np-complete, decision-problem
---


# Question
Title: Are there algorithms for proving two finite state machines are equivalent?
Suppose we call two finite state machines equivalent if they "perform the same computation" - they accept the same language, or they produce the same output for any given input. Is there an algorithm for checking if two finite state machines are equivalent?

# Answer
> 7 votes
Given two deterministic finite automata $A\_1,A\_2$, you can construct the product automaton $A\_1 \times A\_2$ using the product construction. Let a *mixed state* be one which is accepting in $A\_1$ and rejecting in $A\_2$, or vice versa. The two automata are equivalent iff no mixed stated is reachable from the initial state.

---
Tags: finite-automata
---


# Question
Title: Number of pairs of indexes of two arrays such that one element is greater than the other
> Let $A$ and $B$ be two arrays of size $n$. How many pairs of indices $i, j$ satisfy $1 \le i \< j \le n$ and $A\[i\] \> B\[j\]$?

After quite a bit of thinking the best i had gotten to was make a for loop inside of another, which i don´t think it´s a good solution. So i´d like to know some ideas on how to implement this algorithm more efficiently (possibly $O(n)$, if it´s possible).

Thanks ahead.

# Answer
When $A = B$, this is the same as counting the number of inversions, which can be accomplished in $O(n\log n)$ time using a divide-and-conquer algorithm, and in $O(n\sqrt{\log n})$ time using more sophisticated techniques (see Counting Inversions, Offline Orthogonal Range Counting, and Related Problems by Chan and Pătraşcu).

---

In the other direction, here is how to solve a similar but not identical problem.

Given $A,B$, let us construct the following array: $$ C := A\[1\],B\[1\],A\[2\],B\[2\],\ldots,A\[n\],B\[n\]. $$ An inversion in this array is one of the follows:

* A pair $A\[i\] \> A\[j\]$ for $i \< j$.
* A pair $B\[i\] \> B\[j\]$ for $i \< j$.
* A pair $A\[i\] \> B\[j\]$ for $i \< j$.
* A pair $B\[i\] \> A\[j\]$ for $i \< j$.
* A pair $A\[i\] \> B\[i\]$.

Therefore you can deduce the number of $i \< j$ such that either $A\[i\] \> B\[j\]$ or $B\[i\] \> A\[j\]$ given the number of inversions in each of $A,B,C$, augmented by the number of indices $i$ such that $A\[i\] \> B\[i\]$. This yields a simple $O(n\log n)$ algorithm and a more complicated $O(n\sqrt{\log n})$ algorithm, as described above.
> 4 votes

# Answer
This is a bit heavy-weight, but: one way of thinking about this is as a series of spatial queries. If you conceptualise $B$ as a set of 2D points $(j, B\[j\])$ then you want to sum over $i$ the number of points $(j, B\[j\])$ in the quarter plane defined by $j \> i$ and $B\[j\] \< A\[i\]$.

You can build a 2D range tree in $O(n \lg n)$ time and space, and each query then takes $O(\lg^2 n)$ (or maybe $O(\lg n)$ using fractional cascading: the Wikipedia article is a mess, and I haven't dug out the primary sources) for an overall running time of at worst $O(n \lg^2 n)$ and maybe $O(n \lg n)$.
> 0 votes

---
Tags: algorithms, time-complexity, arrays
---


# Question
Title: Loop invariant for adding 2 arrays storing binary value of integer
### Question:

Given 2 arrays of size $n$, $A = \langle a\_1,a\_2,\dots,a\_n \rangle$ and $B = \langle b\_1,b\_2,\dots,b\_n\rangle$, where $A$ and $B$ store the binary value of an integer. Find $A + B$ and stores the result in array $C$ of size $\[n+1\]$, $C = \langle c\_1,c\_2,\dots,c\_{n+1}\rangle$.

### Pseudocode:

```
ADD-BINARY(A,B)
C = new integer[A.length + 1]
carry = 0

for i = A.length to i = 1
    C[i] = (A[i] + B[i] + carry) % 2
    carry = (A[i] + B[i] + carry) / 2

C[1] = carry

return c

```

After writing the pseudo-code, I'm trying to find the loop invariant. One of the statement I can think of is

`At the start of each iteration in the for loop, C[A.length...i] consists of the sum of binary A[A.length...i] and B[A.length...i].`

But I check the initialization stage and found out that it is invalid because at the beginning of the for loop `C[A.length]` does not have the sum yet(it just got initialized). So I'm puzzled whether I'm approaching it the right way.

# Answer
Step 1: Fix the typo in c\[i=\]. That's obviously wrong. (Done).

Step 1a: Try what happens when your algorithm adds 11 and 01. Notice that the result is wrong.

Step 1b: Fix the bug in your code. Check what happens in your algorithm again.

Step 2: Write down what is true at the end of the function which proves that the code is correct.

Step 3: Write down what is correct after the last iteration where i = 1, before setting C \[1\] = carry, which will lead to the statement in Step 2.

Step 4: Write down what is correct after each loop iteration, for each value of i.

Step 5: Write down what must be true *before* each loop iteration to get the result in Step 4.

Step 6: Figure out how Step 4 leads to Step 5.

Step 7: Check that Step 5 is true before the first iteration.
> 2 votes

# Answer
Pseudocode:

```
ADD-BINARY(A,B)

carry = 0

for i = length[A] to 1
   C[i+1] = ( A[i] + B[i] + carry ) % 2
   carry  = ( A[i] + B[i] + carry ) / 2

C[1] = carry

```

Loop invariant :

Concatenating carry and C\[ i+2, i+3, i+4......\] gives the binary sum of A\[ i+1, i+2, i+3.........\] and B\[ i+1, i+2, i+3...........\].

Before the first iteration it says that carry and c\[n+2\] is sum of A\[n+1\] and B\[n+1\]. Now A,B and C have invalid array index, so the statement should hold true.

After first iteration (i=n) it says the same as above. After second iteration (i=n-1) it says carry and C\[n+1\] = A\[n\] + B\[n\] which is true and same is true for other values of i.

The loop terminates when i=0 and it fails the test i should be upto 1. Now it says that carry and C\[2......n+1\] = A\[1.....n\] + B\[1.....n\]. ( the value of C\[1\] is given by the carry.) This is also true and we have the required answer.
> 1 votes

---
Tags: loop-invariants
---


# Question
Title: Proving Clique Number of a Regular Graph
I am very new to Graph Theory and I am trying to prove the following statement from a problem set for my class:

Prove that if G is a regular graph on n vertices $(n \ge 2)$, then $\omega(G) \in \\{1, 2, 3,... \lfloor n / 2 \rfloor, n\\}$

I am confused by the part where it places the clique number to be in this set: $\omega(G) \in \\{1, 2, 3,... \lfloor n / 2 \rfloor, n\\}$. Why can the clique number be only in the first half of this set (or it can be n) and why can't it be anything between $\lfloor n / 2 \rfloor$ and $ n$?

How can I go about proving this claim? Any tips would be appreciated.

# Answer
Let $G$ be a $d$-regular graph on $n$ vertices containing an $a$-clique $A$, and let $B$ denote the other $b:=n-a$ vertices. Suppose that $a\>b$.

Let $e$ be the number of edges connecting $A$ to $B$. Every vertex in $A$ has $a-1$ edges going to the other vertices in $A$, and so $d-(a-1)$ edges going to vertices in $B$. Hence $e = a(d-(a-1))$. Similarly, every vertex in $B$ has at most $b-1$ edges going to the other vertices in $B$, and so at least $d-(b-1)$ edges going to vertices in $A$. Hence $e \geq b(d-(b-1))$. It follows that $$ b(d-(b-1)) \leq a(d-(a-1)). $$ Subtracting the left-hand side from the right=hand side, we get $$ 0 \leq (ad-a^2+a)-(bd-b^2+b) = (ad-bd)-(a^2-b^2)+(a-b) = (a-b)(d-a-b+1). $$ Since $a \> b$, it follows that $d \geq a+b-1 = n-1$. In other words, $G$ is the complete graph.

Summarizing, if a regular graph contains a clique on more than half the vertices then it is the complete graph. Therefore the clique number of a regular graph is either at most $\lfloor n/2 \rfloor$ or $n$.

---

Let us now show that the upper bound $\lfloor n/2 \rfloor$ is tight. That is, for every $n$ there exists a regular graph on $n$ vertices whose clique number is $\lfloor n/2 \rfloor$.

When $n$ is even, there exist regular graphs on $n$ vertices with clique number $n/2$, for example two disjoint copies of $K\_{n/2}$.

When $n=4m+1$, there exist regular graphs on $n$ vertices with clique number $2m$: take two disjoint copies of $K\_{2m}$, add a new vertex connected to $m$ vertices from each copy of $K\_{2m}$, and add a matching between the remaining $m$ vertices of each copy of $K\_{2m}$. When $m=1$, this gives the 5-cycle.

When $n=4m+3$, the following construction gives a regular graph on $n$ vertices with clique number $2m+1$. Take two disjoint copies of $K\_{2m+1}$, say on vertices $x\_1,\ldots,x\_{2m+1}$ and $y\_1,\ldots,y\_{2m+1}$. Connect $x\_i$ to $y\_i$ for all $i$, and connect $x\_i$ to $y\_{i+1}$ for $i=1,\ldots,m$. Finally, add an additional vertex connected to $x\_{m+1},\ldots,x\_{2m+1}$ and to $y\_1,y\_{m+2},\ldots,y\_{2m+1}$.
> 2 votes

---
Tags: graphs, clique
---


# Question
Title: How can I build a fool proof security system?
From what I understand, designing an IT security systems requires to build an algorithm D which can decide whether any program M is malicious or not.

That tasks looks very similar to me than deciding a non-trivial property of an arbitrary large set of programs. And as we know by Rice or diagonalization or many different methods, **this problem is undecidable**.

That means (if I am not wrong) that for some input D might run forever without sending a reply. **Obviously that's not acceptable for a security system. Let's assume for sake of simplicity, that I need a guaranteed YES or a NO.**

How can that be implemented in reality? And what are the consequences for the results?

# Answer
It is true that there is no general algorithm $D$ which can take as input *any* program $M$ and decide whether $M$ is malicious or not. Rice's theorem applies, here.

However, Rice's theorem does not imply that there is no $D$ that can do its job on a useful subset of programs $M$. This subset can not be the whole set of programs, according to Rice, but it could still be large enough to be useful in practice.

I'd say that most of the research in formal verification is about finding such a $D$ for specific cases. Usually the typical verifier $D$ outputs results meaning "I established that $M$ is malicious", "I established that $M$ is not malicious", or "my analysis was inconclusive, $M$ is too complex for me".

Essentially, we allow $D$ to throw the sponge, but hope that it won't. We can't have a guaranteed YES or NO without also having, in infinitely many cases, the "inconclusive" result.

A naive technique to implement a $D$ could be to run $M$ for 1000 steps, and sees is $M$ does something bad. If it does, output "$M$ is malicious", otherwise output "inconclusive".

Static analyzers and model checkers (to mention two common approaches) only succeed on a subset of cases, but they can still be quite useful.
> 1 votes

---
Tags: computability, rice-theorem
---


# Question
Title: Constructing an optimal solution to bin packing using a "magical function" $\phi$
I am taking an introductory course in complexity theory, and as an exercise, we were given the following problem.

Consider the bin packing problem, with objects of positive (rational) weights $W = \\{w\_1, w\_2, ..., w\_n\\}$ ($0 \< w\_i \leq 1 \forall i$) that should be placed in bins of capacity 1. Imagine that you are given a "magical function" $\phi$ that, given a set $W$ of weights, gives you the minimum number $k$ of bins needed to pack the corresponding objects, i.e., $\phi(W) = k$. Let $T(n)$ denote the running time of the implementation of $\phi(W)$ and construct an algorithm that returns an optimal packing and runs in $O(f(n) + g(n)T(n))$ time, where $f(n)$ and $g(n)$ are polynomials.

First, I tried to recursively make binary partitions of $W$ by using that $\phi(W\_1) + \phi(W\_2) = \phi(W)$ for any partition $W\_1 \cup W\_2 = W$ such that $W\_1$ and $W\_2$ separates objects that are in different bins in an optimal solution (that is, there is an optimal solution such that no weights in $W\_1$ share bins with any weight in $W\_2$). When we eventually get $\phi(W\_j) = 1$, we know that $W\_j$ corresponds to the objects in bin $j$ in an optimal solution. However, my attempts here only yield algorithms with $g(n)$ being exponential in $n$.

Second, I tried to construct the bins one by one, using that, for all bins $B\_j$, $\phi(B\_j) + \phi(W \setminus B\_j) = k$. Again, I have yet to find an algorithm where $g(n)$ is polynomial.

It's rather frustrating, as this seems to be a simple problem. Any suggestions on where I should begin?

# Answer
> 2 votes
Starting with $W$, repeatedly try to find two weights $w\_i,w\_j$ such that merging them (i.e., replacing both of them with $w\_i+w\_j$) doesn't increase the number of bins needed. Eventually, you will be left with $\phi(W)$ merged weights, which form a solution to the bin packing problem.

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


# Question
Title: Halting problem for polynomial space bounded Turing machines
A polynomially bounded Turing machine is the one which, on input $w$, uses no more than $f(|w|)$ cells on its tape, where $f$ is a polynomial. For this problem halting is decidable.

I do not understand why is halting decidable for this problem because $f$ is unknown to us.

# Answer
> 3 votes
You don't need to know $f$. It is sufficient to use the fact that there are only finite possible configurations.

Given an input $\langle \langle M\rangle,w\rangle$ where $M$ is a polynomially bounded TM, simulate $M$ on $w$ and record its configuration at every step. Whenever we find a repeated configuration, we can assert that $M$ does not halt on $w$.

Note if $M$ does not halt on $w$, it must experience a repeated configuration, so the process described above will always halt. Therefore this process is the decider for the halting problem.

---
Tags: computability, undecidability
---