# Question
Title: Algorithm Question: Stacking bricks of different colours?
I have a bunch of coloured bricks. There are X different colours, and a random number of each colour. How do I stack them up into Y columns so that a) no row has two bricks of the same colour and b) the height of the *largest* column is minimised?

There is an obvious lower bound of highest number of bricks of a single colour but beyond that I don't know where to go. This is equivalent to an optimisation problem I'm trying to solve and I'd be grateful if someone recognised the problem!

# Answer
> 1 votes
Let $n$ be the number of bricks and $c\_i$ be the number of bricks of color $i$. First notice that in a $w \times h$ grid we can fit at most $wh$ bricks. Therefore, $\lceil \frac{n}{Y} \rceil$ is a lower bound on your height. The minimum height $h$ to stack all your bricks without violating the constraint will be $\max(\max\_i(c\_i), \lceil \frac{n}{Y} \rceil)$.

The idea is to go from left to right (column 1 to X) and keep pushing a brick of the same color on to the left most non-full stack. And by non-full I mean that the size of the stack is lower than our defined height $h$. No two colors will be in the same row and it is also obviously true, that we have enough room for all $n$ bricks.

A pseudo code is also provided:

```
color_count[i] = number of bricks of color i
height = max(max(color_count), ceil(n / Y))

current_column = 1
current_row = 1
current_color = 1
while current_color <= X
  while color_count[current_color] > 0
    put a brick at (current_row, current_column) with current_color
    color_count[current_color] -= 1
    if current_row == height
      current_column += 1
      current_row = 1
    else
      current_row += 1
  current_color += 1

```

# Answer
> 0 votes
I propose a solution, but don't know if it's correct. Here are the steps :

Let $C$ be the array that stores the colors, and $Y$ the one for the columns, with $Y\_i$ the height of column $i$.

1. Count for each color the number of bricks that have this color.
2. Sort $C$ in descending order according to the number of bricks of each color.
3. Create a first column, and put in it all the bricks of color $c\_1$.
4. Create a new empty column.
5. Now, fill the new empty column with bricks of color $c\_2$. Because $C$ is sorted in descending order, after filling this column, $Y\_2 \leq Y\_1$.
6. Continue to fill the last column with next bricks until $Y\_1 = Y\_2$. When finish, create a new empty column.
7. Repeat 5 with the rest of the bricks.

Here's an example :

First iteration :

First column is full with all the bricks of color 1.

Second iteration :

We have put all the bricks of color 2. We have an empty cell, we can put a brick of color 3 and create a new column.

We now fill the new column with the rest of the bricks.

---
Tags: algorithms, optimization
---


# Question
Title: Closure of a CFL under specific operation
Consider the following operation on language $L$:

$\mathrm{inv}(L) = \\{ xy^Rz \mid x,y,z\in \Sigma^\*, xyz\in L \\}$

I understand that if $L$ is regular, then $\mathrm{inv}(L)$ is regular too, and proved it by guesing when $y^R$ starts and running it on the inverse DFA. However, if $L$ is a CFL, then $\mathrm{inv}(L)$ is not, and I don't understand why. Can't we just also guess when $y^R$ starts, insert all of it into the stack, then simulate the DFA of $L$ on each item we take out, then continue on $z$ when it's empty?

thanks.

# Answer
You are right, regular languages are closed under inversion $\mathrm{inv}$, using some proper guesses, or see my answer to a relevant question here.

Context-free languages are not closed under $\mathrm{inv}$. Your intuition does not work. We cannot push $y$ on the stack because it will make the 'real' stack below it inaccessible for the simulation.

Here is a possible counter example. Consider $L = \\{ a^nb^nc^md^m \mid m,n\ge 1 \\}$. Then try $\mathrm{inv}(L) \cap a^\*c^\*b^\*d^\* $.
> 0 votes

---
Tags: context-free, computation-models, closure-properties, pushdown-automata, nondeterminism
---


# Question
Title: Whether the algorithm is polynomial or not with input size which is not polynomial
> A problem may require memory space which is not polynomial with respect to the input size but may still have polynomial run time.

Is this true or false? and why? any idea?

# Answer
This depends on how precisely the words are meant.

In computer science, we often lack perfect (or even good) information about the behavior of algorithms. As a result, we tend to approximate or create upper bounds and talk about those instead of actual behavior. In most contexts, when you say “the algorithm requires superpolynomial space” what you mean is that *in the worst case, we cannot prove that the algorithm uses less than superpolynomial space*.

This is very different from the literal interpretation of your words, where an algorithm requires superpolynomial space if there exists an input for which it use superpolynomial space.

**So why does this matter?** Writing $k$ units of space generally requires at least $k$ units of time in the contexts where we are interested in doing space analysis. Therefore if the algorithm in fact requires superpolynomial space, it must require superpolynomial time. Additionally, if we cannot prove it doesn’t require superpolynomial space, then it follows that we cannot prove that it doesn’t require superpolynomial time. However, it is possible for us to not be able to prove that it doesn’t require superpolynomial space and in fact requires polynomial time.

Additionally, it’s possible that in your context writing $k$ units of space can be done in much less than $k$ time. There do exist computation models where space is much cheaper than time in this sense, but in those contexts we rarely care about space complexity, because it’s so cheap.

So, **the answer in most contexts is no**, but it’s very important to think carefully about what your words mean.
> 0 votes

---
Tags: algorithms, polynomial-time, pseudo-polynomial
---


title: Concatenation of two Turing machines

text:
# Question
Title: Concatenation of two Turing machines
If I have two Turing machines A and B, and I want to use an output of A as an input to B, how is it going to work? Can I just run A, keep the input tape, and then run B (without affecting the number of states A and B? Or do I have to combine an halting state of machine and an initial state of the other machine?

# Answer
> 1 votes
Given two Turing machines $M\_1$ and $M\_2$, assume that their state sets are disjoint, i.e, $Q\_1 \cap Q\_2 = \emptyset$. Define $\Sigma\_3 = \Sigma\_1 \cup \Sigma\_2, Q\_3=Q\_1\cup Q\_2, F\_3=F\_2$.

Modify $M\_1$ so that it prints its output starting from the first (leftmost) tape cell, then move the tape head to the leftmost cell and enter the $M\_2$'s start state. This makes sure that $M\_2$'s input is the $M\_1$'s output. You may also need to add new states to $Q\_3$ .

---
Tags: turing-machines
---


title: Is there really a $ O(1/n) $ algorithm?

text:
# Question
Title: Is there really a $ O(1/n) $ algorithm?
What kind of algorithm can have $O(1/n)$ complexity, where $n$ is a natural number?

Or, is there any algorithm that the time it takes decreases when the data input increases?

# Answer
No algorithm really has an $O(1/n)$ running time, but that notation might be used informally for an algorithm who's running time is really $O(m/n)$ where $m$ is large and not expected to vary. Here's an example of such an algorithm:

Given an unordered set (e.g. a hash table) containing $n$ values from the integer range $0 \le x \lt m $ (for some $ m \in \Bbb{N}^\* $). (Note that $ n \le m $, as a set can't contain any duplicate values.)

We want to find the minimum value in the set as efficiently as possible.

If $n$ is much smaller than $m$, then a linear scan through the values in the set is the most efficient solution ($O(n)$).

But if $n$ is greater than $\sqrt m$, it will often be more efficient to iterate over the potential values starting with $0$ and going up, testing each one to see if it's in the set. We can of course stop as soon as we find one, since it will be the smallest one.

The expected number of tests (assuming the data is randomly distributed over the range) is $m/n$. If we consider $m$ to be a constant (as in real-world applications it will often be determined by something we can't easily change like the size of our integer data type), this seems like it would be $O(1/n)$ (with a large constant factor of $m$). And that does give an accurate description of how the performance of the algorithm changes as $n$ goes from $ \sqrt m $ towards $m$ while $m$ remains the same.

But the notation is not strictly correct. Asymptotic notation is intended to describe behavior as its variable terms go towards infinity. If an $O(1 / n)$ algorithm could run for $n$ approaching infinity, its running time would tend towards zero, but the $1 / n$ term would be dominated by constant terms (and so $O(1)$ would be a better description of its performance). For an algorithm that only makes sense on a bounded $n$, it's not correct to use asymptotic notation. For a strict asymptotic analysis, you need to consider $m$ a variable too so that both $m$ and $n$ can increase towards infinity.

I suspect that if you ever see $O(1/n)$, it's being used as an informal shorthand for $O(m/n)$.
> 11 votes

# Answer
Considering that even the algorithm

```
return 1

```

has $\Omega(1)$ running-time cost, it seems obvious that running-time in $o(1)$ is impossible.

Other cost measures are often equated with running time, e.g. comparisons in sorting. That makes sort of sense since, usually, we pick dominant operations that have the same $\Theta$-class as the "running time". Such a cost measure might turn out to have growth in $o(1)$ -- but then it can not be dominant!
> 5 votes

# Answer
An algorithm, as I understand it, can not have less than 1 step making the minimum complexity O(1). So I can't see how an algorithm can run in O(1/n) steps.
> 2 votes

# Answer
$1/n$ is a monotonously decreasing function. Even if it is theoretically possible that there are algorithms which become faster with larger input, this does not make sense in practice.

A monotonously falling function $f$ can always be estimated by a constant, and thus $O(f) \subseteq O(1)$.
> 2 votes

---
Tags: algorithms, algorithm-analysis, runtime-analysis
---


# Question
Title: For a cycle with $n$ vertices, how many distinct chords are possible?
*Note:* This is almost certainly an elementary problem with a well known solution. Therefore pointers to existing references will be accepted as good answers.

> **Question:** Given a cycle with exactly $n$ vertices, how many distinct chords are possible?

This question is motivated by the definition of chordal graph, which only requires the cycles in the graph to have chords if the cycles have four or more vertices.

Doodling on paper I realized that this is because, for the smallest possible number of vertices in a cycle, namely three, the existence of a chord is impossible. But as soon as the cycle contains at least four vertices the existence of a chord is possible.

For the four-vertex cycle, it seems that there are only two possible chords. Since a chord is formed between two distinct vertices in a cycle, and $2$ might be the first term in a sequence of coefficients of the form $\binom{f(n)}{2}$ for some $f(n)$, I thought that the solution might be similar to the handshake problem and involve $\binom{n}{2}$ or $\binom{n-1}{2}$ somehow.

But this seems to fail already when $n = 5$, because instead of getting $\binom{4}{2} = 6$, which I had expected, instead I counted 5 distinct chords. So then I thought that maybe the answer is the Catalan numbers, since after $1$ they start with $2,5,\dots$, have a form similar to the $\binom{n}{2}$ from the handshake problem, and show up in all sorts of unexpected places.

But this conjecture also fails, since for the cycle with $n=6$ vertices I counted 9 (or maybe 8) distinct chords, and this obviously isn't the third non-unit Catalan number 14, nor is it $\binom{5}{2} = 10$. I somewhat expect the numbers/sequences to differ for odd and even number of vertices however, for a reason analogous to why a graph is Eulerian if and only if each of its vertices has even degree.

I would like to know the answer not only out of sheer curiosity, but also for some intuitive insight into how one can then go on to count the number of possible chordal completions of a graph (which one then uses to calculate the treewidth) -- that is all outside the scope of this question however.

# Answer
> 2 votes
A chord consists of a vertex $i$ and a different nonadjacent vertex $j$. There are $n$ options for $i$, and $n-3$ options for $j$ (since we can't choose $i$ or any of its two adjacent vertices). Since we can switch $i,j$ and get the same chord, we have to divide by 2. Overall, we get that the number of chords is $$ \frac{n(n-3)}{2}. $$ When $n=3,4,5,6$, this gives $0,2,5,9$, matching your values.

# Answer
> 1 votes
Based on the Online Encyclopedia of Integer Sequences page on this sequence and it’s references, it seems that the answer to this question is not known.

The answer is known for labeled chordal graphs via a rather non-elementary approach.

---
Tags: graphs, combinatorics
---


# Question
Title: Prove that $\{1^m+1^n = 1^{m+n}\}$ is not regular using Myhill–Nerode
> Consider the alphabet $Σ = \\{1, +, =\\}$ and the following language, $PLUS = \\{ 1^m + 1^n = 1^{m+n} \mid m, n ∈ ℕ \\}$. Prove with Myhill-Nerode that PLUS is not a regular language.

I know how I should use Myhill-Nerode here and how I should show that any two strings in the infinite set $S$ are distinguishable, but I am stuck at defining my infinite set S for this language. I tried $S = \\{1^n \mid \text{$n$ is a natural number} \\}$ but I don't think it works.

# Answer
If $n \neq m$ then $1^m+1=1^{m+1} \in PLUS$ but $1^n+1=1^{m+1} \notin PLUS$.
> 2 votes

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


# Question
Title: Interview question (constant-time algorithm, ILP)
A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact numbers are relatively small (0-1000), integral, and known ahead of time

Input: cup size (mL), amount to fill (mL)

Output: whether or not a sequence of button presses can be constructed that is guaranteed to fill the cup with at least amount\_to\_fill mL while not overflowing the cup. A different sequence of button presses cannot be performed depending on how much the previous button presses ended up filling the cup, ie the sequence must be fully determined before any of the buttons are pressed.

This trivially reduces to the integer linear programming problem:

Given a,b,c,d,e,f,G (all integers, G very large, the rest relatively small)

maximize: ax+by+cz s.t. dx+ey+fz \< G and x,y,z are integers

for which, the maximum can apparently be found in constant time. Denote this maximum M(a,b,c,d,e,f,G). What is the closed-form solution to M?

# Answer
After glancing at http://www.lume.ufrgs.br/bitstream/handle/10183/66091/000870881.pdf;sequence=1,

I think I figured it out.

Something along the lines of, wlog, let (a,d) have ratio a/d \>= b/e \>= c/f.

Then y is capped at d/gcf(e,d) and z is capped at d/gcf(f,d). brute force all possible (y,z) possibilities in constant time, fill in the corresponding x=floor\[(G-e*y-f*z)/d\] (constant time), and select the maximum ax+by+cz (constant time). QED.

This solution seems a bit inefficient and although there may be a better constant-time solution out there (particularly, for d\>100), it scales well for large G which is all that really matters for this question.
> 1 votes

# Answer
Your problem is equivalent to the unbounded knapsack problem(https://en.wikipedia.org/wiki/List\_of\_knapsack\_problems). Hence, I think the problem is NP-Hard. Typically such problems are solved dynamic programming.
> 0 votes

---
Tags: integer-programming, constant-time
---


# Question
Title: Whether the 2 minimum spanning tree of same graph contains the lowest edges in common?
> If two minimum spanning trees on the same graph only have 2 edges in common, then those two edges must be the lowest costs edges in the graph.

True/false? and why?

Because according to me if there is a only edge which connects 2 subgraphs then that will be included in the MST whatever might be the value. So according to me the answer is False but the solution says the answer to be true. Please explain.

# Answer
To prove that it's false you just need a counter-example.

The two MST can be

Noticed that the only two common edge is not the lowest cost edge. Hence the statement is **FALSE**.

---

However, if all the edges have unique weights, the answer is **TRUE**.

> Any MST of a size larger than 1 contains the smallest and the second smallest edge.

The smallest edge must be in any MST. Suppose not, we can always include it and form a cycle, and remove the largest edge in the cycle to form a smaller tree.

The second smallest edge must also be in any MST (of the size larger than 1). Suppose not; we can include it and form a cycle. Noticed that a cycle must have at least 3 edges. Hence, the largest edge that is removed must be larger than the second smallest edge. Hence we also form a smaller tree.

Since any MST must contain the 2 smallest edge, when they only have 2 edges in common, it must be both of them, which are also the lowest costs edge in the graph.
> 2 votes

---
Tags: minimum-spanning-tree
---


# Question
Title: Solve Max 3 color problem using 3 color decision problem
I've been stumped on this question for a while and can't find a solution. How can I find the max 3 colorability of a graph(optimization problem) with 3 colorability (decision problem) without brute force searching every combinations of edges?

# Answer
> 1 votes
The problem "Can a given graph $G$ be 3-colored so that at least $m$ edges are bichromatic?" is in NP, and therefore can be reduced to 3-colorability (since 3-colorability is NP-hard). Using this, you can solve maximum 3 colorability, employing a simple binary search that invokes a 3-colorability oracle $O(\log n)$ times.

There might be a more direct reduction (which might have been the point of the question), but there is no real problem with this answer as well.

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


# Question
Title: Dynamic Programming Recursive Algorithm - Number of heads in a series
So I have this programming prompt which asks me to figure out how many permutations of a 32 coin toss sequence do not have three or more heads consecutively tossed. We are supposed to use Dynamic Programming to do this and I'm having a hell of a time identifying the recursive algorithm for this.

My first thought was a bottom up approach where I start from a singular toss and then increment a variable whenever I find a sequence that has three heads in a row and then subtract that number from the total number of possible permutations to get the answer but I'm having trouble implementing the logic behind that.

I see that instead of thinking increasingly large sequences, it would be better to think of each individual toss in the sequence. Mostly what I'm having trouble with is how I should be keeping track of all this.

For example, the first toss is a H, that affects the rest of the sequence because I can't have 2 more H's consecutively, but if the first toss is a T, that doesn't affect the rest of the sequence. So, do I wait till the third toss to tell if I increment? Do I discard the first toss if it's a T? I'm having quite a bit of trouble visualizing and comprehending this problem.

# Answer
**Method 1: DFA.** Construct a DFA that accepts the language of valid coin tosses (of any length). Let $A$ be a $Q \times Q$ matrix (where $Q$ is a set of states) such that $A(j,i)$ is the number of symbols that cause the DFA to transition from state $i$ to state $j$. The number of coin tosses that you're after is $1\_F A^{32} 1\_{\\{q\_0\\}}$, where $q\_0$ is the initial state, $F$ is the set of final states, and $1\_S$ is the characteristic vector of $S \subseteq Q$.

This method actually works with more general automaton models. For example, you can have a DFA in which some transitions are "missing": when at state $i$, upon reading a symbol $\sigma$ you might just get stuck. More generally, UFAs would work.

**Method 2: Recurrence relation.** This is a reformulation of the DFA approach without mentioning DFAs. Let $A(n,i)$ be the number of binary words $w$ of length $n$ such that $wH^i \notin L$ but (if $i \neq 0$) $wH^{i-1} \in L$, where $L$ consists of all strings with no three consecutive heads. You're after $B(n) = A(n,1) + A(n,2) + A(n,3)$. These sequences are given by the following recurrence:

* $A(0,1) = A(0,2) = 0$, $A(0,3) = 1$.
* $A(n+1,1) = A(n,2)$.
* $A(n+1,2) = A(n,3)$.
* $A(n+1,3) = A(n,1) + A(n,2) + A(n,3)$.

I'll let you figure out where these recurrences come from.

We can also come up with a direct recurrence for $B$:

* $B(0) = 1$, $B(1) = 2$, $B(2) = 4$.
* $B(n+3) = B(n+2) + B(n+1) + B(n)$.

You can prove this recurrence from the preceding ones for $A(n,i)$, and also directly.

Standard methods show that $B(n) \sim C \alpha^n$, where $\alpha \approx 1.839$ and $C \approx 1.137$. In fact, $B(n)$ can be calculated as the integer closest to $C \alpha^n$ for $n$ larger than some constant.
> 3 votes

---
Tags: algorithms, dynamic-programming, recursion
---


# Question
Title: Max-min of a nonconvex quadratic problem
I am trying to solve the following problem, which is a simplification of our original question:

$\max\limits\_{x,y}\min \\{x\_iy\_i-b\_i \mbox{ for } i=1,\ldots, n: x,y\in \Delta\_n\\}$

where $\Delta\_n$ is n-dimensional unit simplex and $b\_i$'s are arbitrary nonnegative numbers. $x\_i,y\_i$ is the $i^\mbox{th}$ entry of $x,y$ resp..

When all $b\_i=0$, I can argue the optimum is $\frac1{n^2}$. But in general I have no progress. On the other hand, it would also be nice to show that this problem is NP-hard, but I am unable to think of a reduction from a combinatorial problem. It would be awesome to hear some suggestions! Thanks in advance.

Orion

# Answer
I assume that your "unit simplex" is the set of all nonnegative points whose coordinates sum to 1, $\\{x: x\_i\ge 0, \sum x\_i = 0\\}.$

Note that the max occurs when $x=y$ as $x\_iy\_i\le \left(\frac{x\_i+y\_i}2\right)^2$. This makes your problem easy to solve, as at the optimal $x$ either $x\_i^2-b\_i$ is the solution, or $x\_i=0$ and the solution is less than $-b\_i$, so a binary search on the sorted $b\_i$ should get your answer quickly.
> 2 votes

---
Tags: complexity-theory, quadratic-programming
---


title: Two's complement 8-bit subtractor?

text:
# Question
Title: Two's complement 8-bit subtractor?
Please help me! I've been asked to make a circuit using only Logic Gates to implement an 8-bit 2's complement subtractor.

I was thinking of somehow modifying an 8-bit adder, but I figured it isn't 2's complement so it won't be of much use to me.

Any help is greatly appreciated, even if it's a pointer to the right approach to take in this.

# Answer
> 2 votes
It may seem at first as though computing the two's complement of `b` would cost you a whole separate incrementer, but you can easily merge it into the adder that you need anyway: just set the carry-in.

Alternatively (for example if you are somehow forced to use an adder without carry-in, or if it just works out better in combination with other logic) you may used that `a - b = ~(~a + b)`, which obviously only ever needs inverters and a normal adder. This does put inverters before and after though, whereas to calculate the two's complement of `b` you'd only need inverters before the adder (and a carry-in but that's almost free).

# Answer
> 1 votes
Subtraction $a-b$ can be implemented by computing the 2's complement $c$ of $b$ and then adding $a+c$. So to construct your circuit, combine a circuit which computes 2's complement with one that computes addition.

---
Tags: logic
---


title: Y combinator, function composition

text:
# Question
Title: Y combinator, function composition
I am trying to understand Y combinators. Could you please explain why the following are equivalent

```
(Y (f ∘ g))
(f (Y (g ∘ f)))

```

(Y is a fixed point combination)

# Answer
It depends on the notion of equivalence you are using.

Suppose we compare these terms according to their denotational semantics, on $\omega$-CPO domains. Denote with $F,G$ the semantics of the terms $f,g$. Thus, $F,G$ are Scott-continuous functions. Then, we have that the semantics of $Y(f \circ g)$ is, according to the Kleene's fixed point theorem

$$ (1) = \[\\!\[ Y(f\circ g) \]\\!\] = \bigsqcup\\{ \bot, F(G(\bot)),F(G(F(G(\bot)))),\ldots\\} $$ where $\bigsqcup$ denotes the supremum / least upper bound.

Similarly, we get

$$ (2) = \[\\!\[ f(Y(g\circ f) \]\\!\] = F(\bigsqcup\\{ \bot, G(F(\bot)),G(F(G(F(\bot)))),\ldots\\}) $$

By continuity, we get $$ (2) = \bigsqcup\\{ F(\bot), F(G(F(\bot))),F(G(F(G(F(\bot))))),\ldots\\} $$

One can then prove that $(1)=(2)$ by observing that any element of any one chain is bounded above by some element of the other chain. Indeed, we have $$ \bot \sqsubseteq F(\bot), F(G(\bot)) \sqsubseteq F(G(F(\bot))), \ldots $$ estabilishing that $(1)\sqsubseteq(2)$. Further, $$ F(\bot) \sqsubseteq F(G(\bot)), F(G(F(\bot))) \sqsubseteq F(G(F(G(\bot)))), \ldots $$ estabilishing that $(2)\sqsubseteq(1)$, concluding the proof.

---

Much less formally, the term $Y(f \circ g)$ expresses the infinite application $$ f(g(f(g(\ldots)))) $$ and, similarly, $Y(g \circ f)$ expresses $$ g(f(g(f(\ldots)))) $$ It is fairly natural, then, that applying a single $f$ on top of the second one results in the first one. The above domain-theoretic proof provides a formal justification of that.
> 6 votes

---
Tags: lambda-calculus, functional-programming, combinatory-logic
---


# Question
Title: What is the meaning of a prefix-free language?
Tried a bunch of resources to read about it, still don't really get it.

This is what Wikipedia says

> A prefix code is a type of code system (typically a variable-length code) distinguished by its possession of the "prefix property", which requires that there is no whole code word in the system that is a prefix (initial segment) of any other code word in the system.

This is my understanding so far: I have a language L that has all these words `L = {"a", "b"}`. From my understanding, right now my language L is prefix free, but if I add a new word to it like "ac", so that my language becomes `L = {"a", "b", "ac"}`, its not prefix-free anymore?

Is my thinking correct? or am I missing anything?

# Answer
> 7 votes
You are correct: `{a, b}` is prefix-free, but `{a, b, ac}` is not.

The idea of a prefix-free code is that once you recognize a word you know for sure it's a word. So for instance a code that includes both `CONNECT` and `CONNECTICUT` is not prefix-free, because if you start parsing a phrase like

```
ACONNECTICUTYANKEEINKINGARTHURSCOURT

```

taking every word as soon as you see it you're going to read this as

```
A, CONNECT, I, CUT, YANK, (error)

```

since you can't do anything with the string `EEINKINGARTHURSCOURT`. (That's assuming you don't also consider `CON` a word also; if so, things would be even worse.)

Note that adding spaces between words is basically a way of making a code prefix-free: if "connect" by itself isn't considered a word, but "connect " is, then you'll have no trouble parsing

```
A CONNECTICUT YANKEE IN KING ARTHURS COURT

```

---
Tags: regular-languages
---


title: Turing Machine - Tape Question

text:
# Question
Title: Turing Machine - Tape Question
I have a question regarding Turing machines.

Are these two tapes the same thing?

First one = _ _ _ _ * A A A B B B

Second one = * A A A B B B

_ denotes a blank tape cell.

# Answer
Well, kind of, but not really. A defining characteristic of a Turing machine is its current *head position*, where the head is reading and writing from the tape. These two tapes appear to be identical, but the tape head isn't in the same place. It depends on how you define "the same thing": the tapes themselves are the same, but the Turing machines' states are not.
> 1 votes

---
Tags: turing-machines
---


# Question
Title: Can two deterministic turing-machines avoid each other in a sidewalk?
Imagine a turn-based game where two robots are placed on opposite sides of a 16x16 board, facing each-other. Each robot, at each turn, can perform one of 2 moves: **move** (moves forward), **turn** (turns 90 degree; clockwise for the first robot, anti-clockwise for the second). They can also send messages to each-other, and behave according to arbitrary deterministic computations.

```
|_|_|_|_|v|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|
|_|_|_|_|^|_|_|_|_|

```

For simplicity, assume the behavior of the robots is determined by a Python function such as:

```
# just an example, not used
state = {}

# always go forwards
def brain(otherPos, myPos, message):
    return ("move", "hello")

```

This behavior is, of course, stupid, as it always goes forward and broadcasts the same message, ignoring the position of the other robot and the message sent by it. On this case, the robots would just go forward, until they colide and stop moving forever. But any logic could be implemented and the robots could collaborate in arbitrary ways. An improvement would be:

```
# just an example, not used
state = {turn: 0}

# always go forwards
def brain(otherPos, myPos, message):
    if state.turn === 0:
        return ("turn", "I'm turning")
    elif state.turn === 1:
        return ("move", "I'm moving horizontally")
    elif state.turn <= 4:
        return ("turn", "I'm turning again")
    else:
        return ("move", "Now I'm going forward, forever!")

```

This one would cause both robots to turn 90 degrees, move, then turn 3 times, and then move forward forever. They'd still collide and get stuck on the same column, though, because, as one turns clockwise, the other one turns anti-clockwise.

My question is: **is it possible to program a `brain` function in such a way that, after N turns, each robot ends up on the other side?**

# Answer
You have to teach the robots how to keep track of their identity, either by remembering the initial position, or by signing their messages. Then they can perform their individual programs. Something like this:

```
t = "turn"
m = "move"
program1 = [t, m, t, t, t, m, m, m, m, m, m, m]
program2 = [t, t, t, m, t, m, m, m, m, m, m, m]

def brain(otherPos, myPos, message):
    if message == "1":
        return (program1.pop(0), "2")
    else:
        return (program2.pop(0), "1")

```
> 2 votes

# Answer
The only way I can think of is to make them choose a random direction (left or right) and broadcast it, if they broadcast one direction and receive the other then they repeat and they do this until they both go once in the same direction. When they know this they move up the board.
> 0 votes

---
Tags: computability, turing-machines
---


# Question
Title: Is there an polynomial time algorithm to find that sum of square-roots is less than an integer?
**Given:** A list of $n$ integers $x\_1,x\_2,\dots,x\_n$ and an integer $k$.

**Determine:** Is $\sqrt x\_1 + \sqrt x\_2 \cdots \sqrt x\_n \le k$?

**Question:** Is there any polynomial time algorithm for the above problem? If yes, give an algorithm; otherwise prove it.

# Answer
In case David's answer is not clear: Let's say you have 10,000 integers $x\_i$ and k = 1,000,000. You can easily add the square roots of n integers using floating-point operations in $O(n)$. And if the result is say 999,999.537 or 1,000,000.214 then you have the answer. If the result is close to 1,000,000 then you can do a very careful analysis of floating-point rounding errors, and if the sum is say 999,999.999999999 then you probably get your answer. If the sum is too close to k, then you can do arithmetic with higher precision. So there will be a constant c, depending on the exact implementation, so you can find the correct answer in $cn$ time for the huge majority of all cases (if n is truly large then it will take a bit longer because the numbers involved just get huge, but then the time will be longer than your lifetime anyway).

The problem is that there are sums of square roots that can get very, very close to k. For example, you can define f(x) = number of choices for $x\_i$ such that the sum of the square roots is ≤ x, then you expect 2f'(k) * eps choices of $x\_i$ so the sum of square roots is within eps away from k. You expect *one* combination where the sum of square roots is within eps away from k if eps ≥ 1 / 2f'(k). You can calculate an estimate of this eps, figure out what precision your calculations would need to get the right answer, and how long it would take you to get the result with this precision. This might or might not be polynomial, depending on how small eps is.

But it is worse: What I said above is how close you *expect* a sum to be to k. But it might be a lot closer by coincidence. It would be very, very hard to prove that it cannot get an awful lot closer. So it might be the case that you find the answer in linear time in most cases (\> 99.9999999999%), that you expect to find the answer in polynomial time in all cases (or not), but in any case you cannot (easily) prove this, and nobody has done so yet.

It *might* be that you could answer the question without calculating the sum, but according to what David says, nobody has shown a way to do that in polynomial time either.

If anyone has done a calculation how close we expect sums of square roots to come close to any integers, I'd be happy to know. BTW. I think the sum of square roots of integers is only equal to an integer if all square roots are integers, so that is easily excluded.

PS. A rough estimate: Let's say we add 10,000 square roots of integers, each less than 1,000,000. That's square roots of $10^{12}$ integers, and since their order is not relevant, there are about $(10^{12})^{10,000} / 10,000!$ sums. That's more than $10^{80,000}$ sums. So we expect one of these sums to be within $10^{-80,000}$ distance to an integer, requiring calculations with more than 80,000 digits precision.

PS. Given integers a, b, c, d, k, and using IEEE 754 double precision arithmetic, the first case where sqrt(a)+sqrt(b)+sqrt(c)+sqrt(d) \< k gives a different result from the mathematically correct one is for a, b, c, d = 4640, 5397, 3001, 3322 and k = 254. In this case, the sum is calculated as exactly 254, when the mathematical result is less than 254. Obviously when the floating-point result equals the integer, we cannot know whether it was rounded up or down, so in this case the result should never have been trusted.

With a, b, c, d = 6222, 8801, 14431, 8132 and k = 383, the calculated sum is greater than k, while the mathematical result is less. The order of the numbers doesn't matter except that 14431 must be the third number.

If we change the order of operations by adding (sqrt(a)+sqrt(b)) + (sqrt(c)+sqrt(d)) (note the added parentheses), which will *change* the rounding errors and tend to decrease them, then a, b, c, d = 12558, 407, 16501, 18308 and k = 396 is the first case where the calculated sum is greater than k, while the mathematical result is less.
> 12 votes

# Answer
The complexity of the square-root sum problem is a long-standing open question. The stumbling block is that, although we know how to compute square roots efficiently, we don't know if it's possible to determine whether $\sum\_i \sqrt{x\_i}\leq k$ by evaluating only a polynomial number of bits of each square root.

The specific problem with the algorithm you propose in the question is that the phrase "compute the square root of each value" is underspecified. Any irrational square root (e.g., $\sqrt{2}$) requires computing an infinite number of bits, so you need to state what precision you're using.
> 21 votes

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


# Question
Title: Given two formulae E[G F p] (which is CTL*) and EG EF p ( which is a CTL) with a Model prove that they are not equivalent
I am trying to prove they are not equivalent , a model which satisfies the fist one but not the second since I think EG EF p is stronger than E\[GF p\],any leads would be helpful. Thanks.

# Answer
> 1 votes
Consider a system with 3 states, $s\_1,s\_2,s\_3$ and the following transitions: $s\_1\to s\_1$, $s\_1\to s\_2$, $s\_2\to s\_3$ and $s\_3\to s\_3$.

The state $s\_2$ is labelled $p$.

Clearly $E\[GF p\]$ doesn't hold, since every path from $s\_1$ has at most one $p$.

However, there exists a path, namely $s\_1^\omega$, such that in every state along this path, i.e. in $s\_1$, there exists a path that eventually sees $p$, so $E G EF p$ does hold.

---
Tags: logic, model-checking, temporal-logic
---


# Question
Title: Prove correctness of this (context-free) grammar
I created a context free grammar for the language which has words where twice as many `a` than `b` occur.

So as example, the language would accept the words `baaaab` and `bbbaaaaaa`, `aab`, etc.

The context free grammar is

```
G = ({X} {a,b}, P, X)
P: X -> XaXaXbX, XaXbXaX, XbXaXaX, epsilon (where epsilon is the empty word)

```

Now how can you justify the correctness of this grammar? So I'm not asking for a strict proof, just rather a way to reason the correctness of this grammar.

The smallest possible strings are `aab, aba, baa`.

And somewhere, in between one of these characters, you can insert any of these three possibilities or just the empty word epsilon.

You will always end up with twice as many `a` than `b` because all our combinations satisfy this condition and we are only using these conditions. So in the end the condition will be the same and be satisfied.

Would you count this as a "reasoning of correctness"? If I read what I have written once again, it sounds a bit cheap :p

# Answer
> 1 votes
> Now how can you justify the correctness of this grammar?

In order to prove that some grammar $G$ generates a language $L$, i.e. $L= L(G)$, you need to prove two things:

* for any string $w \in L$, $G$ yields/generates $w$, i.e., $S \Rightarrow^\* w $, and
* for any string $w$ (consisiting of only terminal symbols), if $G$ yields/generates $w$, then $w \in L$

In your particular example, you first need to prove that if $w$ has twice as many $a$s than $b$s then your grammar $G$ yields $w$, and if $G$ yields some string $w$ then $w$ has twice as many $a$s than $b$s. Induction on the length of $w$ or the number of steps of application of derivation rule might be helpful.

This is our reference question which may be helpful to prove that a language is context free.

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


# Question
Title: Confusion about Definition of DPDA and $\epsilon$-move
The DPDA definition is from sipser's book, and it mentions that the following PDA can convert to DPDA.

I tried it, then I confused the definition!

By definition, I could construct these

$\delta(q\_1,\epsilon,\epsilon)=(q\_2,\\$) $

and because of "exactly one of the values"

$\delta(q\_1,0 ,0 \text{ or } \\$ \text{ or } \epsilon) = \varnothing$

$\delta(q\_1,1 ,0 \text{ or } \\$ \text{ or } \epsilon) = \varnothing$

$\delta(q\_1,\epsilon ,0 \text{ or } \\$ ) = \varnothing$

---

However, how about $\delta(q\_1,\epsilon,\epsilon)$ , when I handle the $\\{ 0^n1^n|n=0 \\}$ ?

Does it means we can stop at two states $q\_1,q\_2$ with same string?

1. to stop at the $q\_1$ is from no input string
2. to stop at the $q\_2$ is from no input string, but $\epsilon$-move

And is it "deterministic" ?

Or why can definition allow $\delta(q,\epsilon,\epsilon)$?

Doesn't it break "deterministic" ?

---

Could I think that it finally stops at $\\{q1, q2 \\}$, and it at least contains one accept states $q1$ , so we accept it ?

---

Hence, by omitting the intermediate steps, I also can construct

$\delta(q\_4,\epsilon ,\epsilon ) = q\_r$, where $q\_r$ is non-accept state with $\delta(q\_r,\epsilon ,\epsilon ) = q\_r$,

then all done.

# Answer
> 2 votes
The *deterministic* concept in pushdown automata means that next move of automata is determined ***uniquely***.

This concept contains two points. First, there are no multiple choices in reading an alphabet from the input. For example, you should not have both of following rules is your transition rule

$$\delta(q,a,\alpha)=(p,\beta), \delta(q,\epsilon, \alpha)=(p',\gamma),$$

because you either can choose the first rule (that is $\delta(q,a,\alpha)=(p,\beta)$ ) read the $a$ then go to next state, or you can choose the second one (that is $\delta(q,\epsilon, \alpha)=(p',\gamma)$ ) do some other job before reading $a$ by $\epsilon$-transition. In the other words your choice in reading $a$ is not unique.

The second point of the definition is that you should exactly know what to do when you are reading an alphabet. Pay attention that the definition says $$\forall q\in Q, a\in \Sigma, x\in \Gamma,$$ which means there should be no ambiguity when you read an alphabet. For example, in above state diagram, one of the undefined rules is $\delta(q\_3,0,x)$, where $x\in \Gamma$. Of course, this undefined rule is not important in our intuition that the PDA works correctly, but if we want to satisfy the definition of DPDA, then *we should not let machine crash in the middle of reading an input*. In the other words, the DPDA should read all characters of its input, then stop either in final state or non-final state.

I hope the above explanations help you in understanding Deterministic pushdown automata.

Now let's take a look at your first question. You've asked is it possible to stop at two states with the same string? The answer is no. I want to draw your attention to this part of definition again that says $\forall q\in Q, a\in \Sigma, x\in \Gamma.$ You missed the second point in the concept of determinism in the definition, that is you should define the rule $\delta(q\_2,\epsilon,\\$)$ for your DPDA. If we define $\delta(q\_2,\epsilon,\\$)=(\epsilon,q\_4)$ and assume $q\_4$ be the *only* final state, then the problem you arose will be solved.

To answer your second question, the definition allows $\delta(q,\epsilon,\epsilon)$ mostly because of the first transition rule. You will find some different definition for DPDA in some other books which handle the first transition rule in some other ways. For example, some people agree that at the beginning we already have $\\$$ on the stack.

your statement about $q\_4$ is ok.

---
Tags: automata, pushdown-automata
---


title: Infinite union of regular language

text:
# Question
Title: Infinite union of regular language
Deciding if the infinite union of a set of regular languages is regular is undecidable.

By closure property of regular languages, regular language is not closed under infinite union so is the above problem undecidable?

# Answer
> 4 votes
The question is not well defined, so the answer can be either decidable or undecidable.

Here are two extreme (and naive) examples of this issue.

1. Suppose your input consists of a single DFA $A$ (i.e. we input a single regular language), and the question is whether $\bigcup\_{i\in \mathbb{N}} L(A)$ is regular. That is, we take an infinite union of the same language. This is clearly decidable, as the answer is always "yes" (the language is always regular).
2. Suppose your input is a Turing Machine $M$ that takes as input a natural number $n$ (in binary) and either halts on $n$ or doesn't. We define our regular languages $L\_n$ for every $n\in \mathbb{N}$ such that $L\_n$ contains a single word, which is the binary encoding of $n$. Then, the question at hand is equivalent to asking of the language of $M$ is regular, which is famously undecidable (in fact, it's neither in $RE$ nor in $coRE$).

Thus, there is clearly something missing in the question.

# Answer
> 5 votes
Since every language is a countable union of regular languages, you're basically asking whether one can decide whether a given language is regular. Thus, for any reasonable representation, this task will be undecidable.

Consider the following representation of your problem, say a machine $M$ represents an infinite series of regular expressions if given input $i$, $M$ produces a regular expression $r^M\_i$. You now ask whether the following language is decidable:

$L=\left\\{\langle M\rangle \Big| \text{$\bigcup\limits\_{i}L\left(r\_i^M\right)$ is regular}\right\\}$

If $M$ does not represent a series of regular expressions, i.e. on some input $i$, $M(i)$ is not a valid regular expression, then $\langle M\rangle\notin L$. $L$ is undecidable, since you can reduce the language $L\_R=\\{\langle M\rangle | \text{$L(M)$ is regular}\\}$ to it ($L\_R$ is trivially undecidable by Rice theorem). Your reduction will, given $M$, generate a machine $M'$ which on input $i$ will simulate $M$ on all inputs of length $\le i$ for $i$ steps, and according to the result, will generate a regular expression which corresponds to the union of all words that were accepted during this simulation. Clearly $\bigcup\limits\_{i}L\left(r\_i^{M'}\right)=L(M)$, and the validity of the reduction immediately follows.

---
Tags: computability, regular-languages
---


# Question
Title: Find Length of longest substring with all 1's in a binary string with k queries
Given a string of size n consisting of 0s and/or 1s.you have to perform **k** queries and there are **two** types of queries possible.

1. "1"(without quotes): Print length of the longest substring with all '1'.
2. "2 X"(without quotes): where X is an Integer between 1 to n.In this query, you will change character at Xth position to '1' (it is possible that the character at ith position was already '1')

Input Format:

* First Line of input contains n and k, where n is string length and k is the number of queries.
* Next line contains a string of 0's and/or 1's of length n.
* Each of next k lines contains query of any one type (i.e 1 or 2).

Output Format: For each query of type 1, print in new line the maximum size of subarray with all 1's.

```
     Example Input:                        Example Output:
     5 7                                   0
     00000                                 1
     1                                     1
     2 3                                   3
     1
     2 5
     1
     2 4
     1

```

My Solution: O(k\*n) (if most of the queries of type 1)

```
 if(type==1){
        int count=0, ans=0;
        for(int i=0;i<str.size();i++){  //longest len substring
            if(str[i]=='1'){
                count++;
            }else{
               ans=max(ans,count);
               count=0;
            }
        }

        printf("%d\n",ans);
 }else{
        int xth;
        scanf("%d",&xth);
        str[xth-1]='1';   //update
 }

```

I am not able to figure out an efficient solution, as for 'type 1' query only solution I could think of is to iterate through string every time and maintain a "count" variable with all 1's consecutively and finally update "ans" variable when ith str becomes '0'.

I am thinking of using segment tree but don't know how to do. As required good solution should be O(k\*log(n)) (doing "type1" query in log(n) time)

# Answer
**Observation**: Type 2 query can only make the longest substring of 1 longer.

Let's call a substring of 1's a *component*. For example, there are 3 components in this string

```
1 1 1 0 0 1 0 1 1 1 1 0

```

When a 0 is changed to 1, only the components to its immediate left and right will be affected. The length of the other components remains the same.

```
string: 1 1 1 0 0 1 0 1 1 1 1 0
size  : 3 3 3 0 0 1 0 4 4 4 4 0

update position 7 to 1 (1-index)
string: 1 1 1 0 0 1 1 1 1 1 1 0
size  : 3 3 3 0 0 6 6 6 6 6 6 0

```

Hence, all you need to do is to keep track of the size of each component and merge them when necessary. You can do so using a Union-Find Disjoint Set data structure. You can have a variable to keep track of the size of the largest component and update its value if, after the merge, you get a larger component.
> 2 votes

---
Tags: algorithms, complexity-theory, data-structures, time-complexity, c++
---


# Question
Title: Predicate calculus- meaning of the word "any"
In the following 2 statements -

```
1. Anyone who eats any pumpkin is a nutrition fanatic.
&forall x ((&exist y (PUMPKIN(y) &and EAT(x,y))) &rarr FANATIC(x))

2. Anyone who buys any pumpkin either carves it or eats it.
&forall x &forall y (PUMPKIN(y) &and BUY(x,y) &rarr CARVE(x,y) &or EAT(x,y))

```

In the first case `any pumpkin` is given by `&exist` and

in the second case `any pumpkin` is given by `&forall`

Why the second case is also not given by `&exist`?

# Answer
I think your answer is that because the second case is written in prenex normal form while the first one isn't. You can read about prenex normal form in logic more for example here and here.

If I want to explain your cases briefly we have followings in the formal predicate calculus (from page 84 of Logics for mathematicians, Hamilton)

Let $\mathcal{A}$ and $\mathcal{B}$ be two statements and $x\_i$ be the statements variables

First, if $x\_i$ does not occur free in $\mathcal{B}$, then we have

$$\vdash ((\forall x\_i) (\mathcal{A} \rightarrow \mathcal{B})\iff ((\exists x\_i)\mathcal{A} \rightarrow \mathcal{B})) \quad\*\\ \vdash ((\exists x\_i) (\mathcal{A} \rightarrow \mathcal{B})\iff ((\forall x\_i)\mathcal{A} \rightarrow \mathcal{B})) $$

second, if $x\_i$ doesn't occur free in $\mathcal{A}$ we have

$$\vdash ((\forall x\_i) (\mathcal{A} \rightarrow \mathcal{B})\iff (\mathcal{A} \rightarrow (\forall x\_i)\mathcal{B}))\\ \vdash ((\exists x\_i) (\mathcal{A} \rightarrow \mathcal{B})\iff (\mathcal{A} \rightarrow (\exists x\_i)\mathcal{B}))$$

Let $x\_i$ be the $y$ you've denoted as a pumpkin. Also, let $\mathcal{A}$ be $\mathbf{pumpkin}(y)\\, \wedge \mathbf{buy}(x,y)$ and $\mathcal{B}$ be $\mathbf{carve(x,y)} \wedge \mathbf{eat}(x,y)$. We have following statement by ignoreing the part *anyone who*

$$(\exists y) \mathcal{A} \rightarrow \mathcal{B} ,$$

that we can rewrite it by above proposition $\*$ as follows (Note $y$ is not free in $\mathcal{B}$)

$$(\forall y) (\mathcal{A} \rightarrow \mathcal{B}) $$

Therefore two following statements are equivalent in logic by considering the first part we have ignored, that is

$$(\forall x)(\forall y) (\mathcal{A} \rightarrow \mathcal{B}) \equiv (\forall x) ((\exists y) \mathcal{A} \rightarrow \mathcal{B}) .$$

Note that you are not allowed to write your first statement in prenex normal form because $y$ is free in $\mathcal{B}=\mathbf{fanatic}(x)$.

As a practice, you can prove the four above propositions.
> 1 votes

# Answer
So I am assuming your question is: Why is the formula to "Anyone who buys any pumpkin either carves it or eats it."

$\forall x \forall y (\text{pumpkin}(y) \wedge \text{buy}(x, y) \implies \text{carve}(x, y) \vee \text{eat}(x, y)) $

instead of

$\forall x \exists y (\text{pumpkin}(y) \wedge \text{buy}(x, y) \implies \text{carve}(x, y) \vee \text{eat}(x, y)) $

The problem with your version is that there might be someone who buys a pumpkin and decides not to eat or carve it and this would contradict the statement that *every* bought pumpkin (by a person $x$) will be either carved or eaten.
> 1 votes

---
Tags: first-order-logic
---


# Question
Title: For each $i$, find minimal $j>i$ such that $A[j]>A[i]$
I have the following problem:

> Given an array $A$, I need to construct an array $B$ such that $B\[i\]$ is the minimum $j\>i$ such that $A\[j\]\>A\[i\]$, or Null if no such $j$ exists.
>
> For example, if $A = \[23,45,13,10,33\]$ then $B = \[2,Null,5,5,Null\]$.
>
> The algorithm should run in time $\Theta(n)$.

# Answer
its next greater element problem
its solvable using stack u can learn it from here (in method 2) for more practice of this useful method u can solve these problems:

Largest Rectangle https://www.hackerrank.com/challenges/largest-rectangle/

And xor Or https://www.hackerrank.com/challenges/and-xor-or

Poisonous Plants https://www.hackerrank.com/challenges/poisonous-plants

196A - Codeforces http://codeforces.com/problemset/problem/196/A

319B - Codeforces http://codeforces.com/problemset/problem/319/B

Minimum Sum http://agc005.contest.atcoder.jp/tasks/agc005\_b

these are solvable using #next\_greater\_element
> 2 votes

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


# Question
Title: What does $|w|$ mean in the statement " $|w|$ where $w \in L \subset \Sigma^*$"?
In my assignment I find these symbols:

$|w|$ where $w \in L \subset \Sigma^\*$

I believe it means the lexikografic value of a word, but I am not 100% certain.

Let me phrase my question this way: could this notation have any other meaning ?

# Answer
> 4 votes
Usually, $\Sigma^\*$ denotes the set of all strings obtainable from an alphabet $\Sigma$.

Most probably, $L$ is a *language* and $w$ is a *word*. A language is a subset of the alphabet $\Sigma^\*$, thus $L \subset \Sigma^\*$.

A word, on the other hand, is a single string obtained from the language $L$.

As an example:

$\Sigma = \\{0,1\\}$
$\Sigma^\* = \\{0, 01, 10, 11, 100, 101, \dots, 1011001001, \dots\\}$
$L \gets$ all strings containing an even number of zeroes
$w \gets 100010$

And $|w|$ is probably the length of $w$.

---
Tags: formal-languages, notation
---


# Question
Title: Biggest number of components in a graph?
What is the biggest number of components in a graph that has 14 vertices and 44 edges?

Since total degree of all vertices in a graph equals to 2 * number of edges, I calculated that for 44 edges, 14 vertices together must have 88 degrees. 88 / 14 = 6, therefore each of them would have to be connected to other 6 vertices and we would still have 4 edges left. So, the only solution I see is using a full graph K10, where we'd have 90 edges ((n\*(n-1))/2). We'd use 10 vertices and eliminate 2 edges. And the rest 4 vertices we would leave isolated, so we'd get 5 components all together.

# Answer
Suppose that a graph having $n$ vertices and $m$ edges consists of $k$ connected components, say of sizes $n\_1,\ldots,n\_k$. Then $$ m \leq \binom{n\_1}{2} + \cdots + \binom{n\_k}{2}. $$ Conversely, given $n\_1,\ldots,n\_k$ summing to $n$ which satisfy this inequality, we can construct a graph with $n$ vertices, $m$ edges, and at least $k$ connected components. We conclude that the maximum number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that we can find $n\_1,\ldots,n\_k \geq 1$ summing to $n$ satisfying the inequality above.

This leads to the following question: given $k$, maximize $\binom{n\_1}{2} + \cdots + \binom{n\_k}{2}$ subject to the constraint that $n\_1,\ldots,n\_k \geq 1$ are integers summing to $n$. The key is the following observation: $$ \binom{a+1}{2} + \binom{b-1}{2} - \binom{a}{2} - \binom{b}{2} = a-b+1. $$ This shows that as long as $n\_i \geq n\_j$, moving a vertex from $n\_j$ to $n\_i$ increases $\binom{n\_i}{2} + \binom{n\_j}{2}$. It follows that the choice of $n\_1,\ldots,n\_k$ maximizing $\binom{n\_1}{2} + \cdots + \binom{n\_k}{2}$ is $n\_1=n-k+1$, $n\_2=\cdots=n\_k=1$.

We have proved: the maximal number of connected components of a graph with $n$ vertices and $m$ edges is the maximal $k$ such that $$ m \leq \binom{n-k+1}{2}. $$
> 1 votes

---
Tags: graphs
---


title: How does SETH implies ETH?

text:
# Question
Title: How does SETH implies ETH?
I know that ETH states that 3-SAT is not solvable in $2^{o(n)}$ time, the best known bound for 3-SAT is around $O(2^{.38n})$. Whereas, SETH states that there is no universal $\delta$ such that for every positive integer $k$, a $k$-SAT problem is solvable in $O(2^{\delta n})$ time.

It is not clear to me that how does SETH is stronger, and SETH implies ETH.

Thanks

# Answer
> 6 votes
The more usual (and slightly stronger) formulation of the exponential time hypothesis is that there is $\epsilon \> 0$ such that solving 3SAT requires time $\Omega(2^{\epsilon n})$ (see, for example, Abboud, Backurs and Williams), where $n$ is the number of variables.

The strong exponential time hypothesis states that for each $\epsilon \> 0$ there exists $k\ge3$ such that solving $k$SAT requires time $\Omega(2^{(1-\epsilon)n})$ (again, see the paper mentioned above).

Showing that SETH implies ETH isn't trivial. The idea is to show that $k$SAT reduces to sparse $k$SAT, which is $k$SAT restricted to instances with $O(n)$ clauses. Such instances can be coded as 3SAT instances with $O(n)$ variables. Therefore if we can solve 3SAT in time $O(2^{\gamma n})$ for every $\gamma\>0$, then we can also solve $k$SAT in time $O(2^{\gamma n})$ for every $\gamma\>0$. For the details, consult Impagliazzo, Paturi and Zane, Which problems Have strongly exponential Complexity?.

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


# Question
Title: Reduction of graph chromatic number to hypergraph 2-colorability
I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this paper, the author tries to reduce graph chromatic number to hypergraph 2-colorability (same as set splitting).

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

I'm reproducing the reduction below.

Let $G$ be a graph, $V(G) = \\{x\_1,\dots,x\_n\\}$. Let $G\_i$ be an isomorphic copy of $G$, $(i=1,\dots,k)$, $V(G\_i) = \\{x\_{i,1},\dots,x\_{i,n}\\}$ ($x\_{i,v}$ is a point corresponding to $x\_v$). Take a new point $y$ and let $f\_v = \\{x\_{1,v},\dots,x\_{k,v},y\\}$. Define hypergraph $H$ by $$ H = E(G\_1) \cup \dots \cup E(G\_k) \cup \\{f\_1,\dots,f\_n\\}. $$ *Then $H$ is 2-colorable if and only if $G$ is $k$-colorable.* I don't understand this conclusion and the only example I've been able to come up with where this is true is $k = 1$.

# Answer
> 1 votes
This is an error in Lovász' paper. However, a correct reduction is not too hard to come by. See this answer on math.se, in which a slight modification of the reduction you quote is shown to work.

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


title: Decomposing a graph into paths

text:
# Question
Title: Decomposing a graph into paths
> Given a simple graph with $n$ vertices, show that you can remove all edges in $O(n\log n)$ rounds, where in each round you are allowed to remove all edges of any (single) path.

# Answer
A classical result of Lovász (On covering of graphs) states that a graph on $n$ vertices can be decomposed into at most $n/2$ paths and cycles, and so into at most $n$ paths.
> 3 votes

---
Tags: graphs
---


# Question
Title: decidability about NFA accepting an input
Let A = {(B,w) | B is an NFA that accepts w}. To prove that N is a decidable language,

M = "on input (B,w) where B is NFA and w is a string, simulate B on w. If B accepts w, accept. Otherwise, reject"

Is this a false proof? The proof from the textbook says that I have to convert NFA into equivalent DFA but I'm not sure why this would be necessary. Is it not possible to simulate NFA directly without conversion?

# Answer
The textbook probably suggests you convert into a DFA because it is easier to simulate a DFA than to simulate a NFA and determine whether the DFA accepts the word w. This is trickier on a NFA (but still possible, if you know how).
> 2 votes

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


title: what is halting problem?

text:
# Question
Title: what is halting problem?
i have researched it on wikipedia and it produces me an unusual example and stories about Turing,so what i understand is if an program run in loop,an electronic device in cpu or in computer structure would stop that program,or an code will be processed by the input to decide if the program will be executed or will be halted after that.So what is the halting problem actually?

# Answer
Consider the set of all possible pairs $ \langle M, w \rangle$, where $M$ is a Turing machine and $w$ is some string on a fixed alphabet. Also note that some $M$ may halt on input $w$, and some may not.

Basically, the Halting problem asks to create a Turing machine that takes a pair $ \langle M, w \rangle$ as input, and eventually halts with answer "YES" if $M(w)$ halts, and "NO" if $M(w)$ does not halt.

If you are familiar with programming you could interpret this problem as following. The Halting problem asks you to write a C++ program which reads another target program together with its input written in C/C++, and always stops and prints "YES" if the target program eventually stops on the input, and prints "NO" otherwise. Note that your program must work for any finite size of target program and any finite size of input.

As for its history, this is one of famous David Hilbert's 23 questions posed in 1900 at the Second International Congress of Mathematicians in Paris, and later in 1936 was solved by Alan Turing to show that such algorithm deciding on all possible pairs $ \langle M, w \rangle$ cannot exist.

This Wikipedia article provides a formal definition of the problem and sketch of proof.
> 4 votes

# Answer
You should be familiar with the concept of coding of a program if we want to explain Halting Problem informally without using formal definition of Turing machine.

Coding of a program contains all instructions that the program follows to process its input. Let's call coding of program $P$ as $\<p\>$.

Suppose someone gives a $\<p\>$. Can you understand will $P$ outputs anything and halt if it runs input $w$? You can not unless you run $w$ on $\<p\>$ and wait to see its result.

The point of this experiment is that if $P$ halts you will understand at *a time in future*, but you'll never understand if stuck in a loop. Note that you don't know *how long you should wait to see its result* and this makes the halting problem hard.

Halting problem says there is no program $\mathcal{P}$ that given $\<p\>, w$ as its input and can determine whether $P$ will halt running $w$ or not.

To better intuition, let's define two languages.

$$L\_{halt}=\\{(\<p\>,w)| \text{P halts on w}\\}\\ L\_{\overline{halt}}=\\{(\<p\>,w)| \text{P doesn't halts on w} \\}. $$

As I explained above you can enumerate $L\_{halt}$ but you can't do it for $L\_{\overline{halt}}$. Halting problem says you can't write any program that given $(\<p\>,w)$ and *decides* whether $(\<p\>,w) \in L\_{halt}$ or $(\<p\>,w) \in L\_{\overline{halt}}$.

Edit: I changed *check membership of $L\_{halt}$* to *enumerate* with the subtle point Yuval mentioned.
> 1 votes

---
Tags: halting-problem, loops
---


# Question
Title: Finding optimum point that minimizes maximum distance
Does anyone know how I should approach this algorithm? It needs to have $O(n^3)$ complexity and I can only come up with an algorithm that has $O(n^4)$ complexity (of doing a n^2 min path from each vertex to $n-1$ other vertexes, and since I need to do this n times, it will be $n^4$ or so I think...

> *Input*: Array $A\[1...n\]\[1...n\]$ such that $A\[i\]\[j\]$ gives length of edge(distance) between two points or $-1$ if there isn't and edge.
>
> *Output*: a vertex $v$, such that distances(total lengths) to all other vertexes are minimized.

Can someone explain in pseudocode or in words how to do this?

# Answer
> 3 votes
you can use Floyd Warshall algorithm to find distance of every pair and then just use a simple for to find the sum of distance of any of vertices and print the minimum of them

---
Tags: graphs, graph-traversal
---


# Question
Title: How do stack-based cache algorithms avoid Belady's anomaly?
I was going through page replacement algorithms from Galvin's Operating System book. I encountered this line about LRU:

> A stack algorithm is one in which the pages kept in memory for a frame set of size N will always be a subset of the pages kept for a frame size of N + 1.

And it states that stack based algorithm does not suffer from Belady's anomaly. Can anyone explain how it avoids Belady's anomaly?

# Answer
> 3 votes
Stack based algorithms implies that a set of n pages will be a subset of n+1 pages. Why?

In LRU every time a page is referenced it is moved at the top of the stack, therefore the top n pages of the stack are the n most recently used pages. Furthermore, since in LRU the near future is an approximation of recent past, we effectively will reduce the page faults if we increase n.

That is, if number of frames are now made n + 1, top of the stack will have n+1 most recently used pages. Hence, set of n pages are a subset of n+1 pages and as page faults are directly proportional to n (due to the LRU assumption) increasing n will never increase page faults.

An intuitive case(special case) is to think that the LRU stack uses n = number of total pages required by the process. There will be no page faults. And if n=1, there will be page faults equal to total pages required by the process.

---
Tags: operating-systems, memory-management, cpu-cache
---


# Question
Title: Are probabilisitc algorithms deterministic?
I got confused with deterministic and probabilistic algorithms. Am I right by assuming that algorithms are called probabilistic once they use some sort of randomness?

Initially, I thought only algorithms outputting random numbers are called probabilistic. They are obviously non-deterministic.

However, what about the following algorithm: Take BubbelSort and randomly decide whether to start sorting from left to right or from right to left. If you modify the sorting order, the algorithm is deterministic, because small values will always be on the left and great values on the right side (or vice versa). As there is some randomness in the algorithm, do we call this algorithm probabilistic?

In short: Any algorithm using some randomness is called probabilistic. Is that correct? However, this term has nothing to do with determinism and non-determinism. Is that correct?

# Answer
> 2 votes
A probabilistic algorithm is one which has access to the output of a random source during its computation. It might be the case that although the algorithm uses randomness, the output is deterministic, i.e. for every possible random string obtained from the source the output is the same (you can always just ignore the source and act solely on the input).

Note that when you're dealing with probabilistic algorithms, your output becomes a random variable. The output can be deterministic in the sense that it is always the same, or can take some value with probability 1 (which is a weaker statement).

---
Tags: algorithms, nondeterminism, probabilistic-algorithms
---


# Question
Title: Expected Linear time Minimum Spanning Tree algorithm
I am trying to understand the proposed "Randomized Linear-Time Algorithm to Find MST".

My findings: I have read and search almost every available resource( main paper, wiki, reports on paper, lecture on paper ) but not getting any clue regarding my confusion.

Question: In the original paper **Section 3: The Algorithm** "***Step 2***" says "In the contracted graph, choose a subgraph H by selecting each edge independently with probability 1/2."

If I have 6 vertexes with 14 edges. And if I choose 7 edges with probability 1/2 then there might be some isolated vertex. In that case, what will happen to that isolated vertex?

# Answer
Nothing in particular happens if there is an isolated vertex. The algorithm is correct even if $H$ consists of no edges, or if it consists of all edges. The algorithm proceeds by finding a minimum spanning forest on $H$, and using it to prune the contracted graph. IF $H$ consists of no edges, then nothing is pruned, but the algorithm remains correct - this only affects the running time.

Note also that the algorithm is for the more general minimum spanning *forest* problem. Hence there is absolutely no problem if the graph is not connected. The algorithm will find a minimum spanning tree in each connected component.
> 1 votes

---
Tags: randomness, minimum-spanning-tree
---


# Question
Title: Why the $\textbf{PCP}(\log n, 1)$ construction of completeness $c$ and soundness $s$ for an $NP$ language $L$ implies $s/c$ inapproximability for $L$?
In the introductory chapter of $\textbf{PCP}$ in Arora and Barak, I read the proof that why a $\textbf{PCP}(\log n, 1)$ of completeness 1 and soundness 1/2 for an $NPC$ language $L$ will imply that there exists a $\rho$ for which $\rho$-approximation algorithm for MAX-3-SAT does not exist unless $P = NP$. But in the paper, https://www.cs.cmu.edu/~odonnell/papers/maxcut.pdf authors say that "We construct a PCP that reads two bits from the proof and accepts if and only if the two bits are unequal. The completeness and soundness are $c$ and $s$ respectively. This implies that MAX-CUT is $NP$-hard to approximate within any factor greater than $s/c$." What is the proof for this?

# Answer
The authors give a reduction $x \mapsto f(x)$ from some NP-hard problem $X$ to MAX-CUT with the following properties:

* If $x$ is a YES instance then $OPT(f(x)) \geq c$.
* If $x$ is a NO instance then $OPT(f(x)) \leq s$.

Here $OPT(y)$ is the optimal value of the MAX-CUT instance $y$.

Suppose now that you had an algorithm for MAX-CUT with approximation ratio $\rho \> s/c$, which means that for every instance $y$, $ALG(y) \geq \rho OPT(y)$, where $ALG(y)$ is the value of the instance produced by the algorithm. We can use this algorithm to solve $X$, since $x$ is a YES instance of $X$ iff $OPT(f(x))\>s$ (I'll let you verify that).

This informally explains the statement in the paper. Any more formal explanation requires a definition of "NP-hard to approximate". One possibility is as follows. Let $Y$ be a maximization problem. We say that $Y$ is *NP-hard to approximate within a factor of $\rho$* if for every problem $X \in \mathsf{NP}$ there exists a polytime computable reduction $f$ which on input $x$ produces a tuple $(y,v)$, where $y$ is an instance of $Y$ and $v$ is a number, with the following properties:

* If $x$ is a YES instance of $X$ then $OPT(y) \geq v$.
* If $x$ is a NO instance of $X$ then $OPT(y) \< \rho v$.

This generalizes the usual definition of NP-hardness for optimization problems, which corresponds to the choice $\rho = 1$. Under this definition, if $Y$ is NP-hard to approximate within a factor of $\rho$ and there is a polytime $\rho$-approximation algorithm for $Y$, then $\mathsf{P} = \mathsf{NP}$. Finally, according to this definition, MAX-CUT is indeed NP-hard to approximate to within any factor strictly larger than $s/c$.
> 1 votes

---
Tags: complexity-theory
---


title: How to find a regular expression

text:
# Question
Title: How to find a regular expression
I know how to find a regular expression when given a FA. But how do I find a regular expression given just a language and its rules?

For example, for the language $L \subset \\{ a,b\\}^\* $ which accepts all words that contain exactly one $aa$. How do I find a regular expression in this case?

I know that I would be able to FA and convert it into a regular expression, but this can be time-consuming. Is there a faster/easier way that I could use in an exam to save time?

# Answer
I'm not aware of any general methods, and personally I'm not interested in tricks which are only useful in exams. However, I can explain how to find an expression for your particular example. The way to get better with this kind of exercise is to solve a few of them.

A word which contains exactly one $aa$ has the form $xaay$, where $x,y$ contain no $aa$, $x$ doesn't end with $a$, and $y$ doesn't start with $a$. This suggests first determining how to write a regular expression for the set of words avoiding $aa$.

If a word avoids $aa$, then any two occurrences of $a$ are separated by $b^+$. We can describe all such words by the following infinite regular expression: $$b^\* + b^\*ab^\* + b^\*ab^+ab^\* + b^\*ab^+ab^+ab^\* + \cdots.$$ This can be represented by the finite regular expression $b^\* + b^\*(ab^+)^\*ab^\*$.

For the sake of our original problem, we need to impose the further constraint that the word not end with $a$. We obtain the following infinite regular expression for the set of all words avoiding $aa$ and not ending with $a$: $$ b^\* + b^\*ab^+ + b^\*ab^+ab^+ + \cdots = b^\*(ab^+)^\*. $$ Similarly, a regular expression for the set of all words avoiding $aa$ and not starting with $a$ is $(b^+a)^\*b^\*$.

Putting everything together, a regular expression for the set of all words containing exactly one copy of $aa$ is $$ b^\*(ab^+)^\*aa(b^+a)^\*b^\*. $$
> 1 votes

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


# Question
Title: Prove that an infinite set is semidecidible
I have been asked to prove that:

Being *C* an infinite set. Prove that *C* is semidecidable if and only if exists a total computable function that is injective and whose image is *C*.

I've read the wikipedia articles of computable function and recursively enumerable set and I saw these properties are true. But I have no idea how to start the proof.

Could you please help me?

Thanks in advance.

# Answer
Here is a rough sketch.

If $M$ recognizes $C$, we can exploit $M$ to craft $N$ which enumerates the language of $M$, writing all its words on an output tape, clearly separated, in infinite time. For that, it suffices to exploit dovetailing to generate all the pairs $(w,k)$, where $w$ is a word and $k$ a natural. For each such pair, we run $M$ on $w$ for $k$ steps -- if $M$ accepts, we add $w$ to the output tape, otherwise we try the next pair.

Exploiting $N$ is then possible to define a total computable $f$ whose image is $C$.

---

For the other direction, given a total computable $f$, we can craft $M$ such that on input $w$ compares it to $f(0),f(1),f(2),\ldots$. In this way we can make $M$ recognize the image of $f$, i.e. $C$.
> 1 votes

---
Tags: turing-machines, semi-decidability
---


# Question
Title: LP formulation and integer solution existance
I’m trying to prove that the following problem has an integer optimal solution. This will hold if the corresponding linear program would have totally unimodular constraint matrix.

We have $m$ pieces of contiguous land parcels $\\{1,...,m\\}$ and $n$ agents with a simple valuation function that assigns $0$ to all the subset of parcels but $S\_i = \\{l,l+1,l+2,...,k\\}$ for which it assigns $v\_i(S\_i)$. We would like to find such an allocation of agents to the parcels that maximizes welfare (sum of obtained values).

Let’s define $S=\\{S\_1,S\_2,...,S\_n\\}$. My try for a relaxed LP is as follows: $$\max \sum\limits\_iv\_i(S\_i)\*x\_i\\ s.t.\\ x\_i\leq 1 \ \forall i\\ \sum\limits\_{x\_i: S\_i\in T} x\_i\leq 1\ \forall T\subseteq S: \cap T \neq \emptyset, T \textrm{ is maximal}\\ x\_i\geq 0$$

First off, is it the correct formualtion? I add the second constraint to mean „for each set of agents with contiguous set of parcels that share at least one parcel, and which is a maximal set with that property, only one agent at most can get its desired plot of land”. In other words, I sum $x\_i$’s of those agents who chose their subset of lands sharing at least one plot. I do not want repetetiveness so I only take maximal amount of agents with that property each time. The other constraints are just relaxed constraint in $x\_i$ which means that either agent $i$ gets his desired set or not.

Secondly, I do not really see why would constraint matrix be totally unimodular. It will have an identity matrix in is upper part and sth that cannot be specified in general in its bottim part. Perhaps there’s some simpler LP formulation that I haven’t thought of? I must add I did not leverage the form of the sets valued by the agents anywhere, so it can be that I am missing something.

I kindly ask for your help.

Example: We have $3$ plots of land $\\{1,2,3\\}$ and $3$ agents with valuations $v\_1(\\{1,2\\})=2$, $v\_2(\\{2,3\\})=3$, $v\_3(\\{3\\})=2$, so $S\_1=\\{1,2\\}$, $S\_2=\\{2,3\\}$, $S\_3=\\{3\\}$. Then the corresponding LP is $$\max v\_1(S\_1)\*x\_1 + v\_2(S\_2)\*x\_2 + v\_3(S\_3)\*x\_3\\ s.t.\\ x\_i\leq 1 \ \forall i\\ x\_1 + x\_2 \leq 1\\ x\_2 + x\_3 \leq 1\\ x\_i\geq 0$$ The contraints mean that "at most one from $S\_1$ and $S\_2$ can be chosen and at most one from $S\_2$ and $S\_3$".

# Answer
I don't know why you added this in your second constraint:

> ..., and which is a maximal set with that property, ...

I would model it simply as: "For every two agents $x\_i$ and $x\_j$, if their sets $S\_i$ and $S\_j$ intersect, then $x\_i + x\_j \leq 1$" $$ x\_i + x\_j \leq 1 \quad \forall (i,j): i \lt j \text{ and } S\_i \cap S\_j \neq \emptyset$$

~~Notice that every row in the constraint matrix has exactly two ones, and we can think of it as a bipartite graph, which is TUM.~~

This matrix is not TUM, and there is no guarantee that it will provide Integer Solutions, as we can see in the counter-example: $$ S\_1 \cap S\_2 \neq \emptyset, S\_1 \cap S\_3 \neq \emptyset, S\_2 \cap S\_3 \neq \emptyset $$ \begin{bmatrix} 1 & 1 & 0\\ 1 & 0 & 1\\ 0 & 1 & 1\\ \end{bmatrix}

That doesn't mean that your problem does not have an integer optimal solution, simply that this Linear Formulation will not always yield an integer solution. For example, the solution of your LP might be $x\_1 = 0.23848$, which satisfies all the constraints and is the optimal solution, but it is not integer.

If your goal is to solve this problem, and get the Integer Optimal Solution, you can use an Integer Linear Formulation and use any ILP solver to get to that solution.

The Integer Linear Formulation allows constraints like $ x\_1 \in \\{0, 1\\}$, that will ensure that this variable will be either 0 or 1.

The purpose of proving that it is TUM, is to avoid using Integer Linear Formulations, since they are slower to solve than Linear Programs.
> 1 votes

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


# Question
Title: How can the intersection of CFLs and REGs be CFL if REG is a proper subset of CFL?
Intersection of CFL and regular is always CFL. But according to Chomsky hierarchy diagram, regular languages lie **completely inside CFL**. So, as regular set is completely inside CFL set, their intersection should be regular right ?

Am I interpreting Chomsky diagram wrongly ?

# Answer
No, you are misinterpreting stuff.

The set of languages (DFL, regular, ...) and the set of strings in a language are independent.

It is entirely possible that a regular language contains strings that are not inside a Context free language.

The trivial example is where the regular language is all strings $\Sigma^\*$ and the CFL is any other language. The intersection between them is the original CFL.
> 8 votes

# Answer
You are confusing two different statements.

1. $\mathrm{CFL} \cap \mathrm{REG} = \mathrm{REG}$ or, equivalently,
for all $L\_1 \in \mathrm{REG}$ : $L\_1 \in \mathrm{CFL}$.
2. For all $L\_1 \in \mathrm{REG}$, $L\_2 \in \mathrm{CFL}$ : $L\_1 \cap L\_2 \in \mathrm{CFL}$.

The first makes a statement on two sets of languages (aka language classes), the second makes one over (many) pairs of sets of strings (aka languages). So in mixing the two, you are creating a type error.

Also, you seem to suggest that if a language is context-free, it's not regular. That is false; we have $\mathrm{REG} \subsetneq \mathrm{CFL}$ (cf. 1.), so showing a language is CFL (using 2.) does not preclude it from being regular. Specifically, it's easy to find examples of a non-regular context-free and a regular language whose intersection is regular.
> 11 votes

---
Tags: formal-languages, regular-languages, context-free, chomsky-hierarchy
---


title: Max() in Domain Relational Calculus

text:
# Question
Title: Max() in Domain Relational Calculus
I was looking through my notes on domain relational calculus, and noticed an interesting result in a question about finding the *most expensive* pizza(s), given a pizza table with schema $\text{pizza}(\underline{id}, size)$. The first idea that came to me was:

$$\\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)\\}$$

i.e. A pizza which is at least at big as every other pizza is the most expensive. But the answer given was instead:

$$\\{id1\ |\ \exists size1, \forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land (\text{pizza}(id2, size2) \to size1 \ge size2))\\}$$

The subtle change being that the last $\land$ was switched with a $\to$. I tried converting the if/then to $\lnot pizza(\ldots)\lor size1 \ge size2$ to get an intuitive idea on what exactly causes my former answer to be wrong, but can't seem to put my finger on it. Can anyone grok the differences between both expressions, and why the former isn't the answer? Appreciate it!

# Answer
Assume $id1$ belongs to the first set. By definition we get that, for some value of $size1$, we have

$$\forall id2, \forall size2 \ (\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2)$$

The above says that, no matter what values we choose for $id2$ and $size2$, we have $\text{pizza}(id1, size1) \land \text{pizza}(id2, size2) \land size1 \ge size2$.

In particular, for any arbitrary value of $size2$, we have $size1 \ge size2$.

But this can't be the case! Indeed, the above implies that, even if we take $size2 = size1 + 1$, we still get a smaller or equal size than $size1$, which is absurd.

Having obtained a contradiction, we have to conclude that out initial assumption, $id1$ belonging to the set, is false. Hence, no value $id1$ can belong to the set -- it is completely empty.

(By the way, the above also implies that any pizza $id2$ has any size $size2$, which is likely not to be the case in your intended model.)

The point is: you don't want to require that $size1$ is larger (or equal) than any number $size2$. That would be requiring too much. You want to require that $size1$ is larger (or equal) than any $size2$, **provided** $size2$ is the size of some pizza. Or, "if $size2$ is the size of some pizza, then $size1 \ge size2$".

The latter can be written as $$ (\exists size2\ pizza(id2, size2)) \implies size1 \ge size2 $$ or equivalently $$ \forall size2\ (pizza(id2, size2) \implies size1 \ge size2) $$ The latter can then be adapted to also require that $size1$ is indeed the size of $id1$, as the correct solution does.
> 2 votes

# Answer
For the first solution suppose, given $id2$ and $size2$ which $\neg pizza(id2, size2)$ and $size1 \< size2$. Although, the first solution said $pizza(id1, size1)$ is not maximum (because it is not true for all $id2$ and $size2$), but it can be false. Because, if $(id1, size1)$ is the only member of the table, it is the maximum. Therefore, the first solution have some fallacy.

To correct the case, you should mention that if $(id2,size2)$ is member of $pizza$ relation, then $size1 \geq size2$ and you can write this proposition as $pizza(id2, size2) \rightarrow size1 \geq size 2$.
> 2 votes

---
Tags: logic, database-theory, first-order-logic, relational-algebra
---


# Question
Title: How to solve the following recurrence? $T(n) = 4T(\frac{n}{2})+n!$
Hello all I am kinda confused on how to solve the above recurrence since the masters theorem would not work with the above equation. Could anyone please help me solving this and showing me the steps? Requirement is to find asymptotically tightest bound.

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

# Answer
> 1 votes
"... the masters theorem would not work with the above equation" is not right. From the master theorem, as we know $n! = \Omega(n^3)$, and $4\left(\frac{n}{2}\right)! \< 0.9 n!$ ($k = 0.9$) for large enough $n$, so $T(n) = \Theta(n!)$.

To know more about this case, follow this link and find third case of the master theorem.

---
Tags: asymptotics, recurrence-relation
---


title: Mother vertex of a graph

text:
# Question
Title: Mother vertex of a graph
I am trying to find all mother vertex in a directed graph.

A mother vertex in a directed graph G = (V,E) is a vertex v such that all other vertices in G can be reached by a path from v.

My Approach:

Do DFS on each vertex and check if all the vertex are reached on each start node. Time complexity : O(V\*(V+E)).

I am looking for any better solutions with better complexity.

Any help would be appreciated.

# Answer
> 5 votes
Find the strongly connected components. If the component graph has more than one source, then there are no mother vertices. Otherwise, the mother vertices are those that belong to the single source.

---
Tags: algorithms, graphs, graph-traversal
---


# Question
Title: Hardness of checking maximal magnitude of a sum of a subset of vectors
The problem I wish to solve is the following:

Given a set $V \subset \mathbb{Z}^2$ find the set $S \subset V$ such that $|\sum\_{v \in S} v|$ is maximal.

By simply enumerating subsets we can solve this problem in $O(2^n)$. This problem feels a lot like the euclidian traveling salesmen problem to me but I can't quite make it fit. I've tried other numerical optimization techniques like giving each vector an associated scalar variable, the idea being that if the variable was 0 then you'd exclude the associated vector it and if it was 1 then you'd include it. Then the goal is to find an assignment of the variables that maximizes this (I used Lagrange's method). That pretty much just got me back to a clearly equivalent problem that I had no more hope of solving efficiently. I can't seem to find any way to do this any faster. Additionally, I'm having trouble concluding that it's NP-hard but it's my bet that it is. For such a simple problem I'd imagine it's been considered before.

Is this problem known NP-hard? Is there a reduction I just haven't seen yet? Is there some efficient algorithm I just haven't seen?

# Answer
I suppose you are talking about the euclidean norm. Consider the optimal solution $S$ and let $w=\sum\_{v\in S}v$, and we assume there's no zero vector in $V$.

For any $v\notin S$, it must holds $v\cdot w\<0$, otherwise $\\|w+v\\|^2\geq \\|w\\|^2+\\|v\\|^2\>\\|w\\|^2$. Similarly for $v\in S$ it holds $v\cdot w\>0$, otherwise $\\|w-v\\|\>\\|w\\|$.

That means $S$ is exactly determined by the direction of $w$. You can exhaust the possibilities by sorting the polar angles of the vectors, and rotate the orthogonal line of $w$ which has only $n$ essentially different partitions.
> 1 votes

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


# Question
Title: What is the exact algorithm to find maximum clique of a given unit disk graph?
A unit disk graph is an intersection graph $G = (V,E)$, such that given $n$ disks on the plane with identical radius. Each disk $d\_u$ corresponds to a vertex $u \in V$, and there is an edge $uv \in E$ if, and only if $d\_u$ and $d\_v$ intersects.

In 1990, Clark, Colbourn, and Johnson showed that the problem can be solved in polynomial time. However, the linked paper does not provide an exact algorithm.

I have been studying the paper for some time, and I still don't see how the observations in Section 3 can be utilized to develop an algorithm. Mostly because point sets that are used to prove the claims are infinite.

Moreover, I have scanned through many papers, and all of them mention the polynomial-time solvability only. I could not even find a verbal definition of the algorithm anywhere.

I am not asking for coding or some well-defined algorithm, but I would really appreciate a roughly written complete algorithm.

# Answer
First note that the algorithm is expressed in the so-called *proximity model* (see preliminaries), so in what follows the points considered will be the centers of your circles, and $d$ will be their common diameter.

It may be confusing, as the circles drawn in the observations are not directly related to the circles from the intersection model (the radius is $d(a,b)$).

---

With the notations of the article, $H\_{A,B}$ is finite because $V$ itself is finite ($H\_{A,B}$ is a subset of the $n$ input points).

```
Input: d, G = (V, E) with V set of points in the plane, and E is the set
       of {u, v} s.t. d(u, v) <= d
best clique = empty
for all pair of points (u, v) from V:
    let V' = set of vertices w of V s.t. d(u, w) <= d and d(v, w) <= d
    let E' = set of {x, y} s.t. x and y are in V' and d(x, y) > d
    // G' = (V', E') is bipartite
    candidate clique = MaxIndependentSet(G')
    best clique = max(best clique, candidate clique)
return best clique

```

If you want to use Hopcroft-Karp, you may need to have an explicit partition $V'=A\cup B$ s.t. all edges of $E'$ are connecting a vertex of $A$ and a vertex of $B$. This can be done by checking the sign of the cross product $(\textbf{w}-\textbf{u})\times(\textbf{v}-\textbf{u})$.
> 2 votes

---
Tags: graphs, computational-geometry, clique
---


# Question
Title: Semantics of Regex with boundary matchers
The regex `/^(abc)$/` matches `abc` but why not `abcdabc`, `abcdabc` also begins with `abc` and ends with `abc`.

I am not sure about the semantics of this regex. Any explanation is welcome.

# Answer
> 1 votes
First of all, what we usually call *Regex*, for instance, in the context of programming languages, is not the same as pure regular expressions. That should not come as a surprise: all computational models have to be adapted to the real world to be made useful. In this case, besides being enriched by features that just enlarge the range of languages it can specify (such as numbered back references), Regex has other features that would require a completely different set of tools to be formalized properly.

What comes after `^` will not be matched to a prefix of the input string. What happens is that `^` is a reference to an **event** (as is `$`, they are called *anchors*). In abstract terms, you can think of the input of a Regex as continuous stream of symbols, unbounded, that is divided in units of limited size, separated from each other by a special symbol. Where should the matching process begin? This is where anchors come to the rescue.

In this context, `^` refers to the event of finding the special symbol, and forcing the Regex to match beginning with whatever comes right after, instead of $\unicode{x2013}$ for instance $\unicode{x2013}$ continuously trying to match a string starting with each symbol from the input, and backtracking to the next, in case of failure.

What the actual input unit is, pragmatically, depends on the context of application of the formalism. Usually we are talking about lines in a text file, separated by line break characters, or the successive contents of an input buffer.

---
Tags: regular-expressions
---


# Question
Title: Pumping lemma with multiple of prime number + a constant
Given the language $$L = \big\\{ 0^{m} 1 0^{2m+k} \mid m \text{ prime and } k \ge 1 \big\\} $$ show that $L$ is not context free by giving a counterexample of the context free pumping lemma. It may be userful the pumping lemma of the language of prime numbers, you can find it here.

A counterexample must be a string $z \in L$ whose length $|z|$ is greater than a generic h such that for any the decompositions $uvwxy=z$ with $|v|+|x|\ge 1$ and $|vwx|\<h$ exists an i such that $uv^iwx^iy \not\in L$. Generally we have to find a contraddiction of $|v|+|x|\ge 1$ or $|vwx|\<h$.

There are five possible decompositions of the string. **The only required case is the one with $v$ completely in the first part of the string and $x$ completely in the second part**.

Now follows some failed attempts:

1. This one was posted as answer I deleted because incorrect. I took as string $z = 0^{2h}10^{5h}$ which is in the language for $m = 2h$ and $k = h$. The problem here is that $m$ is prime, so $m = 2h \iff h = 1$ which means $h$ is not a generic length anymore. Here it follows the **incorrect** attempt:

> $$ uv^iwx^iy = 0^{2h + |v|(i-1)} 1 0^{5h + |x|(i-1)} = 0^{m} 1 0^{2m+k} \in L $$ The equation has solution iff has solution the system $$ \begin{cases} 2h + |v|(i-1) = m, m \text{ prime} \\ 5h + |x|(i-1) = 2m + k \\ \end{cases} $$ For $i = h + 1$ we have $$ 2h + h|v| = h(|v| + 2) = m $$ But $m$ cannot be prime because it's a moltiplication of two terms $h$ and $(|v| + 2)$. Contraddiction!

We need to choose $m$ as something like $h$ or $ah + b$ in order to avoid this issue.
2. I took as string $z = 0^h 1 0^{2h+1}$ which is in the language for $m = h, k = 1$. We have $$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{2h + 1 + |x|(i-1)} $$ We have to solve the system $$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\ 2h + 1 + |x|(i-1) = 2m + k\end{cases} $$

* Trying with $i = h + 1$ does not work: the first equation becomes

    > $$ h + h|v| = h(1 + |v|) = m \text{ prime} \iff |v| = 0$$ so the second equation results in $$ 2h + 1 + h|x| = 2h + k \Rightarrow |x| = \frac{k-1}{h} $$ so the string results in $0^{m} 1 0^{2m+k} \in L$ with $m = h$, $k = h + 1$ from the decomposition with $$ |v| = 0 \qquad |x| = \frac{(h+1) - 1}{h} = 1$$
    * Trying with $i = 0$ leads to

    > $$ \begin{cases} h - |v| = m \\ 2h + 1 - |x| = 2m + k \end{cases}$$ which results in \begin{align\*} 2h + 1 - |x| &= 2h - 2|v| + k \\ 2|v| - |x| &= k - 1 \end{align\*} which results in as many string $\in L$ as you want (for example $k = 3, |x| = 0, |v| = 1$ gives $0^{h-|v|} 1 0^{2h-2|v|+1} = 0^{h-1} 1 0^{2h-1} \in L$)
3. I took the string $z = 0^{h} 1 0^{3h}$ which is in the language for $m = h, k = h$. We have $$ uv^iwx^iy = 0^{h+|v|(i-1)} 1 0^{3h + |x|(i-1)} $$ We have to solve the system $$ \begin{cases} h + |v|(i-1) = m, m \text{ prime} \\ 3h + |x|(i-1) = 2m + k\end{cases} $$

* Trying with $i = h + 1$ we have
    > $$ h = m \qquad |v| = 0 \qquad 3h + h|x| = 2h + k$$ which results in $ |x| = \frac{k}{h} - 1$; then we can take $k = 3h$ so $|x| = 2$, and the result is the string $0^{h} 1 0^{4h} \in L$

As you can see, I can't find a combination of string and $i$ that generates a contraddiction. How would you proceed?

# Answer
> 1 votes
Your error is that you assume that you must find one $i$ to satisfy all the subdivisions $uvwxy$ of the lemma. The lemma is actually much weaker in that you need to find any $i$ for every subdivision $uvwxy$ of a string $s$ in $L$ longer than $h$. Without loss of generality, I will assume that any given $h$ is prime, because if it were not, I would just substitude all next occurances with any higher prime number and everything would still work the same way (I never needed the condition $|vwx|\le h$).

That said you can take your second try from the question and then fork it into two cases where:

1. $v \neq \epsilon$ (where $\epsilon$ means empty string, I don't know if that's international notaion. It can be otherwise written as $|v|\neq0$ )
From your first equation $$h + |v|(i-1) = m, m \text{ prime}$$ with $i = h + 1$ you get $$h + |v|h = (1+|v|)h$$ which is composite number because of our assumption $v \ne \epsilon$, meaning the string is not from $L$.
2. $|v|=0$ where we can pick **another** $i$ because it is different division of the string $s$. Here we get $$|v|=0 \land |vx| \ge 1 \implies |x|\ge 1$$ And we can trivially chose $i=0$, because now we actually subtract from the second string of zeroes, which was originally $2h+1$ long. The new length will be shorter than that, meaning we'll get a string $0^{h}10^{g}$ where $g\<2h+1$ thus the string is not from the language $L$.

On final note, if you were to use this as a rigorous proof, you would need to address all the other options including those, where the $1$ is part of either of the pumped strings, it is part of either $u$ or $y$ and so on. I covered only the two interesting options and the others should now be trivial to you (I assume that is why you never mentioned them in your question and assumed that 1 is part of the $w$ string).

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