title: Tokenization Problem

text:
# Question
Title: Tokenization Problem
Yes, this is a quiz question. It's from a self-paced course, but the answer just isn't correct to me no matter how I look at it. There isn't really an active community to consult.

My Regular Expression experience is profoundly in JavaScript and I'm concerned that it poisoned my thinking of Regular Expressions. For the life of me I can't figure this out. **Answer A** and **Answer B** I can rationalize, though my logic might be inherently flawed somehow. Being unable to understand how **Answer C** works brings me to the conclusion that I am profoundly missing something.

**The Problem**:

Consider the string `abbbaacc` Which of the following lexical specifications produces the tokenization ab/bb/a/acc ?

```
Answer A
a(b + c*)
b+

Answer B
ab
b+
ac*

Answer C
c*
b+
ab
ac*

```

**The two ways that I have tried to resolve Answer C**

**removing tokens**(*which I assumed is the correct way.*)

```
abbbaacc

c* passes and returns token **cc**  //abbbaa
b+ passes and returns token **bbb** //aaa
ab passes and returns no token //aaa
ac* passes and returns no token //aaa
ending tokens:
[cc, bbb]

```

**Keeping String Whole**:

```
abbbaacc

c* passes and returns **cc**
b+ passes and returns **bbb**
ab passes and returns **ab**
ac* passes and returns **acc**
ending tokens:
[cc, bbb, ab, acc]

```

I've tried other random ways as well but nothing turns out. I really am frustrated with this problem and I've been working on it for quite some time. I've reviewed the coursework that I have and I'm just at a loss. I am convinced that I must be conflating the more common Regular Expressions with this but I don't see where I'm doing so in any way that would make this answer correct. If anyone could provide any assistance I would greatly appreciate it!

# Answer
Tokenisation does not search. \[Note 1\]. At each step, it matches (and consumes) a match of one of the patterns starting precisely at the current input point.

Although there are other tokenisation algorithms, the most common one -- usually called maximal munch -- works as follows.

At each step:

* Find the longest match of each pattern starting at the current input point. (This can be done in a single linear-time left-to-right scan of the input.)
* Select the longest of all these matches. If more than one pattern has the same longest match, select the pattern which comes first in the list of patterns. Report the selected pattern and the corresponding matched prefix as the next token.
* Remove the matched prefix from the input, and continue from the first step.

In effect, the match in the first step is a match of a regular expression created from the disjunction of all the patterns. The regular expression matching algorithm is modified so that:

* It also reports which alternative matched, and
* It leaves unmatched input in the input strean, rather than insisting that the regular expression match the entire input.

For your answer C, the regular expression created is $c^\*+b^++ab+ac^\*$. (Some tokenisers would correct the first pattern to $c^+$ because selecting an empty match would cause the above algorithm to fall into an endless loop.)

The longest prefixes successively matched by this disjunction are:

* $ab$ (3rd alternative). The 4th alternative matches $a$, but that us shorter.
* $bb$ (2nd alternative) The second alternative will also match $b$, but that's not the longest prefix matched by this pattern.
* $a$ (4th alternative)
* $acc$ (4th alternative)

---

### Notes

1. This should be intuitive. After all, most programs are read left to right and token order matters: $a = b + c;$ cannot be written as $a b c =+ ;$, and the parser will expect to see the tokens in left-to-right order, so if the lexer produced the stream, $a b c =+ ;$, the parser would get confused.
> 4 votes

---
Tags: regular-languages, regular-expressions, compilers, parsers
---


# Question
Title: When represented as a function, why is the input of a decision problem a natural number?
Our professor explained that all programs can be thought of as the set of natural numbers, while decision problems can be thought of as the set or rational numbers.

Our notes say a decision problem can be represented as a function which takes a natural number as input and maps it to either 0 or 1. That the range is 0 or 1 is obvious but why is the input a natural number? What does it represent? I understand that a program can be represented by a natural number but a program isn't the input for a decision problem, is it? What is the input of a decision problem and why is it represented by a natural number?

# Answer
The number doesn't have to represent anything but itself. E.g. "Is a given natural number $n$ even" is a decision problem. Its input is $n$.

We aren't really *only* interested in decision problems on natural numbers. "Does program $p$ halt when started without arguments" is also a decision problem.

But to consider decision problems on some set $A$ it must be possible to encode all its elements by a finite string in some finite alphabet (otherwise we couldn't use them as input to anything). And for any finite alphabet, the set of all finite strings is countable and you can easily encode each string by a natural number and vice versa.
> 0 votes

# Answer
It's probably easier to understand if you think of a program as a bit-string, i.e., an element of $\\{0,1\\}^\*$; and think of a decision problem as a function that maps a bit-string to either 0 or 1, i.e., a function $\\{0,1\\}^\* \to \\{0,1\\}$. The input to the decision problem is a bit-string.

Why is this reasonable? Any program can be expressed as a sequence of bits (e.g., convert each character to bits, and concatenate them). The input to the program can be expressed as a sequence of bits. So everything is bits.

Hopefully that approach makes sense.

Now, why does your professor/textbook talk about natural numbers instead of bit-strings? That's just a convention. It turns out that every bit-string can be encoded as a natural number, and vice versa. Given a bit-string, you can think of it as the binary representation of a number; and given a number, you can turn it into a bit-string by expressing it in binary. So bit-strings and natural numbers are in some sense interchangeable or equivalent.
> 0 votes

---
Tags: complexity-theory
---


# Question
Title: When can you ignore certain numbers in a recurrence relation?
I am trying to understand how to work out time complexities given certain recurrence relation, however I know that in certain recurrence relation some numbers can be omitted since they make no difference when $n$ gets very large. The problem i'm having is being able to identify the numbers that can be omitted.

For example

$T(n) = 3T(n/3 - 2) + n/2$ Can we omit the 2's here and use the master theorem on

$T(n)=3T(n/3) + n$ ?

What about the following

$T(n) = T(n-2) + n^2$ can we say that $T(n) = T(n) + n^2$ and once again use the master theorem?

Not really clear to me when it is OK to omit numbers.

# Answer
> 1 votes
It depends on what you want to reach and on the recurrence relation.

For example, consider the following recurrence relation $$T(n) = T(n/2 - 1) + 6n, T(1) =1$$ and assume we are interested on its asymptotic growth. If we remove the factors $\frac{1}{2}$ in $T(n/2 - 1)$ and $6$ from $6n$ then we have the following relation

$$T(n) = T(n-1) + n$$ that is a closed formula for the sum of the first $n$ positive integers and is $\Theta(n^2)$.

If we omit only $-1$, then we are left with
$$T(n) = T(n/2) + 6n$$ which is $O(n)$. Thus, omitting factors may result in asymptotically different recurrence relations.

As for your examples, $T(n) = 3T(n/3 - 2) + n/2$ is clearly less than or equal to $T(n)=3T(n/3) + n$, so in order to obtain an upper bound for $3T(n/3 - 2) + n/2$ you can use the later relation, but their exact values for each $n$ is certainly differ. However, I don't see any meaning in the relation $T(n) = T(n) + n^2$ unless $n=0$.

---
Tags: time-complexity, recurrence-relation
---


# Question
Title: Approximate value iteration for continuous state space MDPs
I have a continuous state space MDP as a generative model. I input the state and action and it outputs the reward and the next state. Assume that I sampled $n$ state-reward-states. I wonder how I can implement value iteration using a function approximator. I couldn't find any implementation example online. Can you please point me some references?

# Answer
There are two primary methods to deal with continuous state MDPs. 1. State-space discretization. 2. Value function approximation. As for value function approximation, you can either go for a deterministic/stochastic black-box model or opt for fitted value iteration. You can find the algorithm for the same in pages 10-13 of this link.
> 2 votes

---
Tags: dynamic-programming, reinforcement-learning
---


# Question
Title: Inverse Reinforcement Learning and Apprenticeship Learning differences
IRL as I understand is where the AI is given a policy from an "expert" and needs to solve for the reward function which best fits the policy.

And Apprenticeship Learning via IRL was explained as an expert demonstrating a skill and the reward function also has to be derived using the expert behavior.

I don't necessarily understand the difference between the two since apprenticeship learning directly uses IRL. Any explanation of differences would be helpful.

# Answer
Apprenticeship Learning uses Inverse Reinforcement Learning and there is a subtle difference between the two. Inverse Reinforcement Learning tries to recover the reward function ($R^\*$) from demonstration trace of a teacher (an expert at the task being solved). Finding the optimal policy ($\pi^\*$) from that "guessed" reward is what is meant by Apprenticeship Learning. More information on this link.
> 1 votes

---
Tags: artificial-intelligence, reinforcement-learning
---


# Question
Title: The bounded halting problem is decidable. Why doesn't this conflict with Rice's theorem?
One statement of Rice's theorem is given on page 35 of "Computational Complexity: a Modern Approach" (Arora-Barak):

A partial function from $\\{0,1\\}^\*$ to $\\{0,1\\}^\*$ is a function that is not necessarily defined on all its inputs. We say that a TM $M$ computes a partial function $f$ if for every $x$ on which $f$ is defined, $M(x) = f(x)$ and for every $x$ on which $f$ is not defined $M$ goes into an infinite loop when executed on input $x$. If $S$ is a set of partial functions, we define $f\_S$ to be the boolean function that on input $\alpha$ outputs 1 iff $M\_\alpha$ computes a partial function in $S$. Rice's theorem says that for every nontrivial $S$, the function $f\_S$ is not computable.

Wikipedia states that languages of bounded time turing machines are EXPTIME complete. I expect this language looks something like $\\{(\alpha,x,n) : M\_\alpha $ accepts $x$ in less than $n$ steps$\\}$. So let $M$ be some DTM that decides this bounded language in exponential time. It seems like this DTM is deciding some property for ALL turing machines, so my intuition tells me that Rice's theorem precludes such a decision. But obviously $M$ computes a total function.

What am I missing about the relation between this language and Rice's theorem?

# Answer
> 14 votes
The language

$\qquad \\{(α,x,n):M\_α \text{ accepts } x \text{ in less than } n \text{ steps}\\}$

is not an index set, that is it is not of the form

$\qquad L\_P = \\{ \langle M \rangle \mid M \text{ is TM},\ \exists\\, f \in P.\ f\_M = f \\}$

for some set of (partial recursive) functions $P$, with $f\_M$ the (partial) function computed by TM $M$. Rice's theorem makes statements *only* about such $L\_P$; many "intuitive" rephrasings are not helpful. See also here.

Note that this is not only a technical detail here. Rice's theorem does not apply to

$\qquad L = \\{ \langle M \rangle \mid M \text{ accepts } \langle M \rangle \text{ in less than } \langle M \rangle \text{ steps} \\}$,

either. Can you see why?

> For every machine in $L$ you can easily construct many machines that accept the same language but run for more than $\langle M \rangle$ steps, and thus are not in $L$. Thus, $L$ is not an index set.

$L$ is decidable, using the same argument as for the original language we're discussing.

# Answer
> 6 votes
The Rice theorem says that you can't tell anything about the ultimate behavior of a program when it is left to run to infinity - no matter how you classify programs, there will be two programs that will converge to the same ultimate behavior (computed function) although you classified them differently.

But letting the programs run to infinity is essential. To find out what they do in the first $n$ steps, you could just simulate them for the first $n$ steps and then terminate giving your verdict on how the program behaved. Similar simulation till infinity doesn't work because if the simulated program never terminates on a simulated input, your classifier will diverge as well, instead of providing a classification.

# Answer
> 5 votes
First, the words in your language aren't encodings of machines, they contain more information, so you can't directly apply Rice theorem. That said, Rice's theorem talks about the impossibility of reasoning about the function computed by a Turing machine (namely, whether it lies in some set $S$). This is not the case here, since as Raphael mentioned, there exist two machines $M,M'$ who compute the same function, but one lies in your language and the other doesn't (here I am ignoring the syntactical issue, and forget about the fact that $x,n$ are part of the input). The point is that the property you are looking at here is mechanical, and not semantic (the machines may compute the same function, but in a different way).

# Answer
> 3 votes
Rice's theorem says that, for any nontrivial set $\mathcal{L}$ of languages, the set of Turing machines that recognize a language in $\mathcal{L}$ is undecidable. Wikipedia says that a specific language is decidable. So there's no contradiction.

---
Tags: computability, turing-machines, undecidability, rice-theorem
---


# Question
Title: Finding number of smaller elements for each element in an array efficiently
I am stuck on this problem:

> Given an array $A$ of the first $n$ natural numbers randomly permuted, an array $B$ is constructed, such that $B(k)$ is the number of elements from $A(1)$ to $A(k-1)$ which are smaller than $A(k)$.
>
> i) Given $A$ can you find $B$ in $O(n)$ time?
> ii) Given $B$ can you find $A$ in $O(n)$ time?

Here, $B(1) = 0$. For a concrete example: $$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & 4 & 4 \\ \end{vmatrix}$$

Can anyone help me? Thanks.

# Answer
> 1 votes
The naive algorithm for determining $B$ from $A$:

> For $k=1,\dots,n$, determine the value of $B(k)$ by comparing each $A(i)$ to $A(k)$ for $i=1,\dots,k$ and counting those that satisfy $A(i)\<A(k)$.

This algorithm compares $A(1)$ to all others ($n-1$ times), $A(2)$ to $n-2$ others, etc. so the total number of comparisons is $\frac{(n-1)(n-2)}{2}$. But that's not the best we can do. For example, looking at $B(n)$, we don't have to do any comparisons! $B(n)=A(n)-1$ because it's the *first* $n$ natural numbers, and it’s guaranteed (regardless of the permutation) that the $n-1$ lower natural numbers will be there. What about $B(n-1)$? Instead of checking $A(1)$ through $A(n-2)$, we could just check $A(n)$. That is:

> For $k=1, \dots,\frac{n}{2}$, use the algorithm above; for $k=\frac{n}{2},\dots,n$ use the reverse algorithm: determine $B(k)$ by setting it initially to $A(n)-1$ and then subtracting $1$ for each entry $A(i)$ for $i=k+1,\dots,n$ that is less than $A(k)$.

This would take $2\times\frac{(\frac{n}{2}-1) (\frac{n}{2}-2)}{2}=\frac{(n-2)(n-4)}{4}$ steps, which is still $O(n^2)$. Note also that in constructing $A$ from $B$, if $B(n)=A(n)-1$ then $A(n)=B(n)+1$.

But now for more finesse. If we’re allowed some additional space or sort in-place, we can sort the numbers as we’re comparing them. For example: $$\begin{vmatrix} A & 8 & 4 & 3 & 1 & 7 & 2 & 9 & 6 & 5 \\ S & 9 & 8 & 7 & 4 & 3 & 2 & 1 & 6 & 5 \\ B & 0 & 0 & 0 & 0 & 3 & 1 & 6 & & \\ \end{vmatrix}$$

Instead of checking all of them (or checking them in order), we could use binary search to determine each $B(k)$. However, the sorting still takes time $O(n\log n)$.

# Answer
> 0 votes
Rather than determining each $B(k)$ one at a time, we can be forward looking and only go through each number in $A$ *once*! But we'll use $n$ space:

$$\begin{vmatrix} A & & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & & B \\ 8 & & 0 & 0 & 0 & 0 & 0 & 0 & 0 & \color{red}{0} & 1 & & 0\\ 4 & & 0 & 0 & 0 & \color{red}{0} & 1 & 1 & 1 & 1 & 2 & & 0\\ 3 & & 0 & 0 & \color{red}{0} & 1 & 2 & 2 & 2 & 2 & 3 & & 0\\ 1 & & \color{red}{0} & 1 & 1 & 2 & 3 & 3 & 3 & 3 & 4 & & 0\\ 7 & & 0 & 1 & 1 & 2 & 3 & 3 & \color{red}{3} & 4 & 5 & & 3\\ 2 & & 0 & \color{red}{1} & 2 & 3 & 4 & 4 & 4 & 5 & 6 & & 1\\ 9 & & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 5 & \color{red}{6} & & 6\\ 6 & & 0 & 1 & 2 & 3 & 4 & \color{red}{4} & 5 & 6 & 7 & & 4\\ 5 & & 0 & 1 & 2 & 3 & \color{red}{4} & 5 & 6 & 7 & 8 & & 4\\ \end{vmatrix}$$

We could save even more time by not updating those that have already been determined (that is, there is no point in updating $8$ after the first step), but in the worst case, we still have to update $\frac{(n)(n+2)}{2}$ times

# Answer
> 0 votes
both I and II are solvable using #next\_greater\_element that i explained here. but its a little harder than just the problem but before solution you need to learn next greater element:

1. consider we have a vector for every element of $A$ name it $S\_i$ for element $i$. now once run the next greater algorithm starting from right to left but except setting element $i$ in $A$ its next greater element index , push in $S\_i$ the elements that $i$ is their next greater element.then iterate over the array left to right and then $B\[i\]=\sum\_{j=0}^x (S\_i\[j\]+1)$ where $x$ is the size of vector $S\_i$.and its $\Theta(n)$ because each the next greater algorithm is $\Theta(n)$ and also iterating is $\Theta(n)$

second part is also similar noting that we can get the value of the rightest element in $O(1)$ EDIT:my solution is wrong it seems that it dont have any$o(n)$ solution

---
Tags: algorithms, arrays, permutations
---


# Question
Title: Can any ambiguous context-free grammar be converted into Chomsky normal form?
Can an ambiguous context-free grammar be converted into Chomsky normal form? I think the answer is yes.

# Answer
> 3 votes
Any context free grammar can be converted into the equivalent Chomsky Normal Form. It does not matter if it is ambiguous or not.

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


title: Decidability of whether CFL = RL

text:
# Question
Title: Decidability of whether CFL = RL
Let L1 be a language generated by a CFG. Let L2 be a language generated by a regular grammar. Is L1 = L2 ?

Is the above problem decidable or undecidable ?

---

If L1 = L2 then L1 $\cap$ L2' = $\phi$

So the above problem can be written as

CFL $\cap$ RL = $\phi$ or CFL = $\phi$ which is decidable.

So the answer should be decidable according to me but my professor marked it wrong saying it's undecidable

Where am I going wrong ?

# Answer
> 2 votes
> If $L\_1 = L\_2$ then $L\_1 \cap \overline{L\_2} = \emptyset$

While that is true, the reverse is false. The right-hand side is also true if $L\_2 \supsetneq L\_2$. Therefore, deciding the right-hand side does not solve equality.

---
Tags: computability, formal-grammars, undecidability, decision-problem
---


# Question
Title: Set of all countably infinite strings over a finite alphabet >1
Is the set of all countably infinite strings over a finite alphabet that contains more than one letter countably infinite?

# Answer
> 2 votes
Consider an alphabet $\Sigma = \\{0,1\\}$ and the set of all infinite length strings over $\Sigma$. Then this set is of course infinite, but uncountable which can be easily proved by the diagonalization argument.

# Answer
> 2 votes
Take the alphabet $\Sigma = \\{0,1\\}$ and consider strings whose positions are indexed by $\mathbb{N}$ (also known as $\omega$-words). There is a one-to-one correspondence between these strings and subsets of $\mathbb{N}$ given by $x\_0x\_1x\_2\dots \leftrightarrow \\{i\in\mathbb{N}\mid x\_i=1\\}$. Therefore, there are as many $\omega$-words as there are subsets of $\mathbb{N}$, and this is an uncountable number.

This holds for any countably infinite word length.

---
Tags: formal-languages
---


# Question
Title: is it possible to do a DFA for these languages?
I have just started learning Automata Theory, so far I only know about regular languages, FSM (NFAs and DFAs) and regular grammars, but I come across a question like this:

"Given the next languages, design their respective DFAs"

$L := \\{a^nb^m |\ n\>m\ ∧ n-m = odd\\}$

$L := \\{a^nb^m |\ n\>m\ ∧ n-m = even\\}$

$L := \\{a^kb^mc^t |\ k \ \ is \ \ even \ \ ∧ \ \ m \ \ is \ \ odd \ \ ∧ \ \ t = 2m \ \\}$

Is this even possible? because I was told these languages are regular...

# Answer
Short answer - you're being lied to. From pumping lemma you can prove all three of these to not be regular languages.

Long answer - since you don't know it yet I don't know into how much detail I should go, but just for the sake of completeness I will give you the strings for given $p$ and the $n$ with which you would prove that the language does not have the pumping property.

For the first it would be for example $a^{p+1}b^{p}$. From this definition you know that because of $|xy|\le p$ and $|y|\ge 1$ you know that y will be $a^k$ where $k\>0$. Then for $n=0$ you get $xy^0z = a^lb^{p}$ where $l\<p+1 \implies l \le p$ which means this string is not from the first language $L$.

Similarly for the second language you can have $a^{p+2}b^p$. If $|y|\ge 2$ you can again chose $n = 0$ as in the last exercise. If $|y|=1$ you can chose $n = 2$ giving you string $a^{p+3}b^p$ which does not satisfy the condition $n-m=even$.

For the last I'd choose $a^0b^{2p+1}c^{4p+2}=b^{2p+1}c^{4p+2}$. Simiraly as in the first exercise you will alway only pump $b$ obviously violating $t=2m$ with any $n$ except for $1$.
> 0 votes

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


# Question
Title: About the 'trick' for finding the diameter of an graph in $O(n^2)$
The diameter of an undirected, unweighted graph can be found in $O(n^3)$ with e.g. the Floyd–Warshall algorithm. However, there is an idea how to improve the runtime:

1. Pick a vertex $v$
2. Find $u$ such that $d(v,u)$ is maximum
3. Find $w$ such that $d(u,w)$ is maximum
4. Return $d(u,w)$

This idea fails; for instance, when starting at $v$ here:

However, it is not immediately clear to me if we can not amend the above algorithm with another indirection, and also consider all nodes with maximum distance instead of only one. That is:

1. Pick a vertex $v$
2. Find the set $U$ such that $u \in U \implies d(v,u)$ is maximum
3. For each node $u$ in $U$, find the set $W\_u$ such that $w \in W \implies d(u,w)$ is maximum
4. Merge these sets $W\_u$ into a new set $W$
5. Calculate the eccentricity of all nodes in $W$
6. Return the maximum eccentricity found this way

The improved algorithm works for the above counterexample as well as others (e.g. this one).

I assume it is still wrong. If it were not, it would offer a significant improvement for at least some kinds of graphs. Is there a counterexample? And how could a counterexample for further additional indirections be constructed?

# Answer
The diameter of the following graph is $2a+4$. If you start from $v$, you will need $i=2a+1$ iterations to have $s,t\in W\_{i}$. It provides a family of counter-examples for an arbitrary large number of indirections (as $a \to \infty$).
> 2 votes

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


# Question
Title: Assuming $\mbox{BPP}\subseteq \Pi_2$ -What conclusions can we make?
I'd like your help with the following question:

Assume we proved that $\mbox{BPP}\subseteq \Pi\_2$ -What conclusions can you make?

BPP is the class of decision problems solvable by a probabilistic Turing machine in polynomial time, with an error probability of at most 1/3 for all instances,

$\Pi\_2$ is the class of all languages $L$ such that there's a polynomial algorithm $M$ and a polynom $p$ so that $\forall x.x\in L\Leftrightarrow \forall u\in \\{ 0,1 \\}^\*.\exists v \in \\{ 0,1 \\}^\*.M(x,u,v)=1$.

We already know that $\mbox{BPP}\subseteq \Sigma\_2$, so $\mbox{BPP}\subseteq \Pi\_2\cap \Sigma\_2$.

# Answer
It is known. As your final statement says, $\mbox{BPP} \subseteq \Pi\_2 \cap \Sigma\_2$. It is called the Sipser–Gács–Lautemann theorem. (All though your "so" is somewhat misleading.)

It can be strengthened to $\mbox{BPP} \subseteq \mbox{MA} \subseteq \mbox{S}^P\_2 \subseteq \Pi\_2 \cap \Sigma\_2 \subseteq \Pi\_2$ (see also Arthur-Merlin protocol).
> 6 votes

# Answer
Just to add a minor point to Pal GD's answer, $BPP$ is closed under complementation. So, once you prove that $BPP \subseteq \Sigma\_2$, you can easily deduce $BPP \subseteq \Sigma\_2 \cap \Pi\_2$. Also, (Just to improve the inclusions) even better $BPP \subseteq NP^{BPP} \subseteq MA \subseteq S\_{2}^{P} \cdots$ is known.
> 2 votes

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


# Question
Title: A O(n) algorithm for a point set triangulation
I'm currently stuck at the following task:

Consider a point set $S = \\{ p\_1, p\_2, ..., p\_n \\}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p\_i) \< y(p\_j) $ if and only if $i \< j$. Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I found out how to triangulate monotone polygons, which is pretty close to the task, but I don't know how to transfer this into a triangulation of point sets in case the monoton polygonial has a "notch".

I'd be thankful for any kind of help.

# Answer
> 3 votes
You can find one triangulation similar to finding the convex hull. On your conditions finding the convex hull can be solved in linear time.

In order to find the convex hull of a set of points in $R^2$ let's do two sweep lines, one from left to right to compute the upper-hull and another from right to left to find the lower-hull. In order to illustrate the algorithm better I will use pseudo from here.

I'll augment it to solve the triangulation problem. My comments start with #

```
Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# We can skip this since points are already sorted
Sort the points of P by x-coordinate (in case of a tie, sort by y-coordinate).

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from L and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

Remove the last point of each list (it's the same as the first point of the other list).
Concatenate L and U to obtain the convex hull of P.
Points in the result will be listed in counter-clockwise order.
# Triple of points in T will be the triangles

```

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


title: A variant of coin change problem

text:
# Question
Title: A variant of coin change problem
Consider a cashier machine that takes payments in coins. We feed the machine coins one by one until the value is more than the amount we should have paid. Then the machine returns the extra amount in coins in the least number of coins possible. So we have `k` type of coins and a limited amount of each type. Also the machine has an unlimited amount of each of the `k` types of coins so it can return us the exact amount it should (there is always coin with value `1`). So we want to minimize the number of coins we have after we have paid for the items we have bought. Consider this example: We have `3` kinds of coins of values `1`, `2` and `4` and we have to pay `15` dollars. We have `10` coins with value `1`, `7` coins with value `4` and `5` coins with value `2`. There are multiple ways to minimize our coins after the process. One of them is to give the machine 10 coins with value 1 and 3 coins with value 2. Thus we have paid 16 dollars with 13 coins and the machine should return to us 1 dollar and it returns us 1 coin with value 1. So we have spent 12 coins. The other way is to give the machine 9 coins with value 1 and 3 coins with value 2 and the machine doesn't return us anything. So we have paid 12 coins.

My approach to the problem is to divide the problem to two separate coin change problem. The easier problem is when the machine returns us the extra amount of money we have paid. I think this is a simple coin change problem that we want to change some amount of money to the minimum number of coins. The main problem is to pay the machine some maximal amount of coin with the restrictions mentioned above. The restrictions were that we have limited number of each coin and if want to pay `A` dollars the machine stops receiving coins when the amount of money we have paid becomes equal or greater than `A`. So For example if we have to pay to 15 dollars and we want to use a total amount of 18 dollars to pay we should use at least a coin with value 4 (18-15+1) or else at some point in the process of paying the amount we have given to the machine surpasses 15 and it won't receive any more coins.

So what I have done so far is this

```
A //amount we should pay
D //value of the coin with max value among all present coin types
for value_to_change in A to A+D-1
   clear the memoized table for maximal_change
   r = maximal_change(value_to_change,0,0)
   d = minimal_change(value_to_change-A)
   ans = max( ans, r-d )

max_coin // the maximum value of the coin we have used so far
maximal_change( value_to_change, index_of_coin_type, max_coin )
   if we have computed (value_to_change, index_of_coin_type)
       return the computed value
   if (it is the last coin type) AND (max_coin > A-value_to_change)
       if value_to_change % value[index_of_coin_type]==0
            return value_to_change / value[index_of_coin_type]
       else
            return we cant change this value with this coin // -1
   for i in [0, number_of_available_coins_with_this_type]
       n = maximal_change( value_to_change - i*value_of_this_coin_type,
                           index_of_coin_type+1,
                           max(max_coin, value_of_this_coin_type) )
       if n != -1 // we can change the value
           result = max(n+i, result)
   dp[value_to_change][index_of_coin_type] = result;
   return result

```

now my problem is my solution is slower than what is expected and I think it is because that I clear the memoized table for every value to change. This is only because in each value to change we are required to use a coin with value at least (value\_to\_change-A+1). Anybody has a better solution?

link of the full description of the problem
link of my implementation

# Answer
> 2 votes
I agree with your solution of the isolated case. Your problem is to reuse your memoisation table. Suppose there are *n* cases.

What I imagine you could do is:

Allocate a matrix to hold all cases. It has dimensions: *T*, 1 \<= coin value = 50. Call the maximum coin value *C*. The maximum number of coins is 1000. You could store each count in an unsigned 16 bit int. This max total memory so far of 100 * 50 * 16 = 80KB. We're given 65536, so this isn't too bad. Call this *M1*.

You now want to devise a plan to reuse your memoisation table as much as possible. As far as I can see, you can reuse a table if and only if the multi-set of coins of the next case is a superset of the previous.

You need to find a way of partitioning the rows into *M1* into sequences where each successive vector represents a superset of the previous. That is, the values of coin counts should be non-decreasing over successive vectors.

What you would like to do is minimise the number of partitions. Given two plans with the same number of partitions, you would choose the one which minimises the maximum number of differing coins for a given partition, which would in turn make the solution of the isolated cases cheaper.

I'm not completely sure about the complexity of this, although I imagine that it is NP-Hard, given the number of possible partitions and its similarity to the partition problem. It seems like there might be a cheap randomised greedy algorithm to find a set of initial sequences and work from there.

To run the plan, iterate over the sequences, initialising the memoisation table each time. Run the first case as normal. Run the second case by computing change combinations only for the set of new larger combinations of each coin.

---
Tags: algorithms, optimization, dynamic-programming, coin-change
---


# Question
Title: Decide if there is a sbugroup of edges in graph that every vertex meets exactly k edges from subgroup
I've been trying to solve the following question:

> Show a polynomial algorithm for the following problem. Let $G = (V, \> E)$ a graph. The goal is to decide if there is $E' ⊆ E$ , such that for every vertex $v ∈ V$, $v$ meets or exactly $k$ edges from $E'$. (Namely, for $k = 1$ you get the perfect matching problem). hint - start with $k = 2$, duplicate vertices.

I was able to develop an algorithm which works but I couldn't prove it find the largest subgroup, your help is needed :)

The algorithm:

For every $v$ in $V$:

1. Check the degree, if it equal to k or not connected to any edge in the subgroup - color it
2. Check if the colored $v$ has a colored vertex, if it has the edge between them belongs to the subgroup.
3. Traverse on all vertices (BFS or DFS) When done you'll find the subgroup, the only one thing the prove it is the largest and I couldn't find any proof for it.

Thanks in advance!

# Answer
> 1 votes
The question is a bit misleading, since the proposed algorithm finds whether there is a "multisubset" of the edges set which is $k$-regular — that is, you are allowed to take the same edge several times, if it helps. Deciding whether the graph contains a bona fide $k$-factor (a $k$-regular subgraph which touches all vertices) is much more tricky — see Meijer, Núñez-Rodríguez, and Rappaport, An algorithm for computing simple $k$-factors.

---
Tags: graphs, np, matching
---


# Question
Title: Understanding a boolean expression in λ-calculus
*(NOTE: This is not a homework question at at all. Rather, this was something that I thought that I understood (at least on the surface), but now appear to have no clue about, and am not currently finding any resources helpful. I know that we typically like to see what people have tried, but I am honestly discombobulated enough at this moment that I am truly unsure about where to even begin. If this turns out to be a duplicate that I haven't found, I would also be perfectly happy. I just want to understand.)*

Anyway, on to the question itself:

So, if $\lambda xy.x$ represents true, and $\lambda xy.y$ represents false, then I have been told that $(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x)$ is a `not` function, because the expression

$(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x) \ \lambda xy.x$ results in $\lambda xy.y$,

and the expression

$(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x) \ \lambda xy.x$ results in $\lambda xy.x$.

Where I am stuck is that I don't see how to apply $\beta$-reductions here. There are three expressions inside the parenthesis. How is one of them chosen by applying the outer expression?

# Answer
It's a very bad idea to omit parentheses. Correct is: $$\lambda b . b (\lambda x y . y) (\lambda x y . x)$$ Next, it is confusing to reuse bound variables, so let me rename them: $$\lambda b . b (\lambda x y . y) (\lambda u v . u)$$ And now we can apply this to $\lambda p q . p$ (which is just "true" with bound vraiables renamed yet again): \begin{align\*} (\lambda b . b (\lambda x y . y) (\lambda u v . u)) (\lambda p q . p) &=\_\beta (\lambda p q . p) (\lambda x y . y) (\lambda u v . u) \\ &=\_\beta (\lambda q . (\lambda x y . y)) (\lambda u v . u) \\ &=\_\beta (\lambda x y . y). \end{align\*} So we did get false. In every step there was exactly one $\beta$-redex. By the way, writing $A B C$ in $\lambda$-calculus means $(A B) C$ by convention.

I will leave the other one as exercise.
> 4 votes

---
Tags: lambda-calculus, term-rewriting
---


title: Congruence of Squares for Factoring

text:
# Question
Title: Congruence of Squares for Factoring
After coming across the assertion that given

$$ x^2 = y^2 \pmod n \\ x \neq \pm y \pmod n $$

we can then conclude that n factors into

$$ n = \mathrm{gcd}(n, x-y) \mathrm{gcd}(n, x+y). $$

in this article, I attempted my own example but it doesn't seem to work. I think there's a missing hypothesis, but more importantly, I'm interested in understanding why this would work under the correct conditions.

---

First, the example given was

$$ \begin{align\*} &6^2 = 1^2 \pmod {35} \\ &x+y = 7 \\ &x-y = 5 \end{align\*} $$

So applying the gcd with $35$ simply retains the values, yielding the correct factorization

$$35 = 7 \times 5.$$

---

However, my test example was

$$ \begin{align\*} &8^2 = 4^2 \pmod {24} \\ &x+y = 12 \\ &x-y = 4 \end{align\*} $$ If we just blindly applied the stated result, we would get

$$24 = 12 \times 4.$$

I would guess the problem is that my selected factors are not coprime. Does anyone have any intuition for why this method works (when it works) or any hints towards a proof?

---

After some brief pondering, I've noticed it certainly works if the values $x+y$ and $x-y$ are coprime. Their product divides $n$ yet they contain no overlapping factors, so by collecting the factors of $x+y$ and $x-y$ which are also factors of $n$, we will end up with precisely all the factors of $n$ and nothing extra.

# Answer
> 1 votes
The assertion is not correct in general, as you have discovered.

However, here is what *is* correct: $\gcd(x+y,n)$ is a factor of $n$, and $\gcd(x-y,n)$ is a factor of $n$. Why? Well, this is trivial: $\gcd(\text{anything},n)$ is always a factor of $n$. Of course, the gcd might be 1, but that's still a divisor of $n$.

We can say even more. If we let $r=\gcd(x+y,n)$ and $s=\gcd(x-y,n)$, then their product is a multiple of $n$: i.e., $rs$ is a multiple of $n$. Thus, you can replace $s$ with $s'=n/r$ and now $r,s'$ will have the property you want: both $r$ and $s'$ are divisors of $n$, and $rs'=n$. (Why is $rs$ a multiple of $n$? Because if $x^2 \equiv y^2 \pmod n$, then it follows that $x^2 - y^2 \equiv 0 \pmod n$. Now $x^2-y^2 = (x-y)(x+y)$, so it follows that $n$ divides $(x-y)(x+y)$, i.e., $n$ divides $rs$.)

This makes this method useful for factoring. However, beware that there is no guarantee that get a non-trivial factor out of this. For instance, consider $n=15$. Then if $x=8$ and $y=7$, we have $x^2 \equiv y^2 \equiv 4 \pmod n$, but $\gcd(x-y,n)=1 $ and $\gcd(x+y,n)=15$, so we obtain that $15 = 1 \times 15$ -- true, but not very useful for factoring $n$. What we can say is that if $n$ is the product of two large primes, and if you can randomly sample two $x,y$ such that $x^2 \equiv y^2 \pmod n$, then with probability about $1/2$, $\gcd(x-y,n)$ and $\gcd(x+y,n)$ will give you the full factorization of $n$.

If you want us to comment on an assertion it helps to give a reference for it. My guess would be that there is additional context you are not providing, such as the assumption that $n$ is a product of two primes.

---
Tags: factoring
---


# Question
Title: How to understand the probablistic analysis of skiplist?
I've been studying the skiplist analysis from the open data structures book here: Open Data Structures

I've understood the first 3 lemma's, (after looking at how they use indicator variables in the section 1.3.4 of the book). However, Lemma 4.4 seems pretty vague. Especially, how is $$\sum\_{r=1}^{\lfloor\log n\rfloor}1 + \sum\_{r=\lfloor\log n\rfloor+1}^\infty n/2^r\leq\log n + \sum\_{r=0}^\infty 1/2^r\\,?$$

# Answer
> 1 votes
The first sum is obviously equal to $\lfloor\log n\rfloor\leq\log n$.

For the second sum, assuming that logs are base-$2$ and using $r\>\lfloor\log n\rfloor$,

$$2^r = 2^{\lfloor\log n\rfloor+1}2^{r-\lfloor\log n\rfloor-1} \geq n2^{r-\lfloor\log n\rfloor-1}\\,,$$

and the result follows. If the logs aren't base-$2$, then there'll be a scaling factor but the second sum will still be $\Theta(1)$.

---
Tags: mathematical-foundations
---


# Question
Title: Exploration in reinforcement learning when state space is huge
When the state-action space is huge I know I can use function approximators to generalize but how can I explore? Doing an exhaustive search seems very naive. What DeepMind for example did to explore the state-action space in Atari games?

# Answer
In the Atari paper, an $\epsilon$-greedy strategy is used for state-space exploration. This means that the algorithm makes the deep network learn a greedy strategy to pick an action that maximises the $Q$-value of the current state ($a = max\_a Q(s, a; \theta)$. At each time-step in a game, the agent picks an action as per this greedy strategy with probability $1-\epsilon$ and it picks a random action to explore the state-space with probability $\epsilon$. The value of $\epsilon$ can be varied depending on whether we want the agent to explore more ($\epsilon$ value high) or learn from its past behaviour more ($\epsilon$ value low). In the paper, the authors mention that $\epsilon$ is annealed linearly from 1 to 0.1 over the first million frames, and fixed at 0.1 thereafter.
> 2 votes

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: Is there a usable implementation of PBFT?
In the original Practical Byzantine Fault Tolerance (PBFT) paper they mention they implemented a fault tolerant NFS service. To do that they made a library for PBFT. Does that exist anywhere?

As that paper is quite old now and was well received, I thought it should not be hard to find implementations. However so far I only found incomplete and abandoned experiments.

RAFT has a list of implementations on their website. I am looking for something like this in the byzantine case.

# Answer
> 1 votes
Not necessarily NFS, but Hyperledger used PBFT for their blockchain platform.

This is a Go implementation: https://github.com/hyperledger-archives/fabric/tree/master/consensus/pbft

That is an old repo, they seem to be currently using a new repo with implementations in other languages as well, however I haven't gone through it in detail: https://gerrit.hyperledger.org/r/#/admin/projects/

There are more related details in this question: https://stackoverflow.com/questions/41710738/pbft-algorithm-in-hyperledger

Good luck

---
Tags: fault-tolerance, byzantine
---


title: Term for incorrect primary key

text:
# Question
Title: Term for incorrect primary key
From a database theory point of view, what term can be used to refer to a key that does not violate the rules of the engine within which it is implemented, but fails to conform to any sort of normalisation? For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column is unique, the database engine may not detect any violation.

The reason for wanting to obtain a technical or academic term for this is to describe a situation where there is a primary key that has been technically successfully implemented, but is conceptually flawed.

# Answer
> For instance, if a timestamp was used as a primary key. Primary keys are supposed to ensure that no two rows refer to the same thing, but as long as the values within the so-called primary key column is unique, the database engine may not detect any violation.

For this example I would simply state that the problem is that the uniqueness of values of timestamps, if it happens to hold, is only accidental: there is generally no fundamental reason that the same timestamp (even with very high precision) could not be assigned to 2 separate records.

For a primary key uniqueness should not be accidental but fundamental.
> 2 votes

# Answer
Varchar2 is a datatype to store attributes of type character.

Timestamp is a datatype to store attributes of type "Date and time".

If this attribute (of type "data and time") is being used to uniquely identify a tuple, then it is called a primary key.

Also, Anything which is unique for each tuple(row) and which can be used to uniquely identify it, is called a primary key.

There is no need of any new terminology.
> 0 votes

---
Tags: terminology, database-theory
---


# Question
Title: Graph Coloring Problem : How to Think About Algorithms Exer 1.6.2
The problem says:

Given an undirected simple graph G such that each node has at most d + 1 neighbors, color each node with one of d + 1 colors so that for each edge the two nodes have different colors.

Hint : don't think too hard. just color the nodes. what loop invariant do you need?

I was trying to solve this.. but quickly realized a complete graph of 4 vertices, whose vertices have at most 3 neighbors, cannot be colored with one of 3 colors so that each node has different color nodes.

I did some research and it seems like the book had a typo and it should have been "... each node has at most d neighbors, color each node with one of d + 1 colors... "

It is possible to find a graph with maximum degree of d + 1 that can be colored with d + 1 colors but this cannot be true for any graph with max degree of d + 1, right?

Am I correct in assuming that the typo should be corrected like how I did so AND about the last remark?

# Answer
You're right that the statement is false. The correct statement states that every undirected simple graph in which each node has at most $d$ neighbors can be colored using $d+1$ colors so that each edge connects nodes having different color. Stated in more idiomatic language, every undirected simple graph of maximum degree $d$ can be (properly) colored using $d+1$ colors.
> 5 votes

---
Tags: graphs, colorings
---


title: General term for map/fmap

text:
# Question
Title: General term for map/fmap
The general term for folds is a catamorphism. The general term for unfold is an Anamorphism. Is there an equivalent term for map? I know that a map is a type of fold however restriction is significant. Also it would be useful to have an alternative term to use when the word “map” is ambiguous.

# Answer
In addition to being in agreement with Derek (that the ana/cata terminology doesn't bring much to the table) I'll note that the "category theoretic" terminology for the general `map` function of type $$\mathrm{map}:\forall \alpha\beta. (\alpha \rightarrow\beta)\rightarrow(F\ \alpha\rightarrow F\beta) $$ for a functor $F$ is simply "the functorial action of $F$", and is often written as $F$! For example, on lists, `map f l` would be written $\mathrm{List}(f)(l)$.

For some reason, computer scientists seem to prefer to have a seperate name for the type constructor and the action on morphisms, but mathematicians do not really consider non-functorial constructors anyways.
> 5 votes

# Answer
I think `fmap`, at least in the context of Haskell, is already the general term for the thing it does and the thing you're talking about.

The fact that a `map` function also exists, which is basically an `fmap` that only works on lists, is mostly a historical accident AFAIK.

Perhaps you're looking for the word `Functor`, being the thing that has an `fmap`?
> 1 votes

---
Tags: functional-programming
---


# Question
Title: Binary symmetric sources and information theory
How can we generate 3 or more binary Sources using BSC channel. As we know, BSC can be easily used to generate 2 binary sources with some cross-over-probability(say *p*). Eg, length of codeword(say *n*) `n = 1000; p = 0.2`, then input and output binary codeword will be having Hamming distance of approx 200. In this way we generate 2 Binary sources with 200 Hamming distance from each other.

My question is: How can we generate multiple Binary with same cross-over-probability or multiple binary sources with approx similar Hamming distance from each other. E.g: X, Y , Z, W. and they should have similar Hamming distance from each other(all combinations(X-Y)(X-Z) and so on).

And, there should be some way to calculate the joint entropy for them. I am trying to make some scheme to do that, if u have some ideas .. just discuss it. please let me know for any questions.. I will surely clear them

Thanks

# Answer
You want to generate $n$-bit random variables $X\_1,\dots,X\_m$ such that the Hamming distance between $X\_i,X\_j$ is about $pn$. Let me start by showing you how to do this for the special case where $n=1$; then I'll generalize.

Set $q = (1 - \sqrt{1-2p})/2$. Pick a set $S \subseteq \\{0,1\\}^m$ of $m$-bit values, such that every element $s \in S$ has Hamming weight $qk$. Now pick a random $s$ from $S$, randomly permute the bit positions of $s$, and assign this to $X\_1,\dots,X\_m$ (i.e., $X\_i$ is the $i$th bit of $s$). I claim this will have your desired property. Why? Well,

$$\Pr\[X\_i \ne X\_j\] = \Pr\[X\_i=0,X\_j=1\] + \Pr\[X\_i=1,X\_j=0\] = 2q(1-q) = p,$$

so the expected value of the Hamming distance between $X\_i,X\_j$ will be about $p$, as desired. The joint entropy is easy to calculate: it is simply $\log\_2 |S|$.

What if we want $n\>1$? Then we can just sample the first bit of $X\_1,\dots,X\_m$ as above; then sample the second bit of $X\_1,\dots,X\_m$ in the same way (iid; i.e., pick another $s$ from $S$, and randomly permute its bit-positions); and so on. This gives us a source where the expected value of the Hamming distance between any two $X\_i,X\_j$ is about $pn$, and where the joint entropy is $n \log\_2 |S|$.
> 1 votes

---
Tags: information-theory
---


# Question
Title: What is meant by problems not in NP but in NP hard?
If there is a proof that an NP-Hard problem which is not NP-Complete can be solved in P time, it does say that the verification time is polynomial too.

Why doesn't it then mean that all NP-Hard are NP (i.e. NPC)?

---

But, if there is something with exponential verification i.e. outside NP and since it can be reduced to an NPC problem in polynomial time which means it is also verifiable in polynomial time (As we assumed above). Isn't it? Which might say that all NP-hard is NP-complete...

I'm unable to grasp what is NP-hard but not NPC here? What is wrong in this reasoning?

Are there any problems which are outside Recursive Enumerable Languages in NP-Hard? Is that even possible?

# Answer
A language $L$ is NP-hard if you can reduce every language in NP to $L$ in polynomial time. For example, the halting problem is NP-hard: if $A$ is any language in NP, say accepted by a nondeterministic polynomial time Turing machine $T$, there there is a polynomial time reduction which accepts an input $x$ and constructs a Turing machine which simulates all computation paths of $T$ on $x$, and halts if and only if any of these paths accepts.

On the other hand, the halting problem is not in NP, since it is not computable. So the halting problem is an example of an NP-hard problem which is not in NP. You can think of NP-hard problems as being "at least as hard" as all of NP. They are allowed to be even harder.
> 1 votes

---
Tags: np-complete, np-hard, np
---


# Question
Title: How to prove or disprove the well-Definedness of the Operation $.\:$?
Let $L\subseteq \Sigma^\*$ a Language

$R\_L$ is the Myhill-Nerode-Relation of $L$

$\equiv\_L$ is the Syntactic Congruence of $L$

$R\_L$ and $\equiv\_L$ are equivalence relations and are defined as follows :

$x\\:R\_L\\:y \\:\Leftrightarrow \\: \[\forall w\in\Sigma^\* : xw\in L\Leftrightarrow yw\in L\] $

$u\\:\equiv\_L\\:v \\:\Leftrightarrow \\: \[\forall x,y\in\Sigma^\* : xuy\in L\Leftrightarrow xvy\in L\] $

How to prove or disprove the following statements :

a) $\[u\_1\]\_{R\_L} . \[u\_2\]\_{R\_L} = \[u\_1u\_2\]\_{R\_L}$ is well-defined.

b) $\[u\_1\]\_{\equiv\_L} . \[u\_2\]\_{\equiv\_L} = \[u\_1u\_2\]\_{\equiv\_L}$ is well-defined.

# Answer
> 3 votes
Let me try to guess where exactly is the problem here (without actually doing your exercise).

The point is that the operation is defined using equivalence classes, via the *representatives* of these classes. To show that the operation is well defined, you need to check that choosing other representatives (of the same classes) will give the same result of the operation.

So, in order to check that $\[u\_1\]\cdot \[u\_2\]$ is a well-defined operation, you need to show that if $\[u\_1\]=\[v\_1\]$ and $\[u\_2\]=\[v\_2\]$, then $\[u\_1u\_2\]=\[v\_1v\_2\]$.
(Or find a counter example in case the operations are not well-defined.)

Now it remains to plug-in the equivalence relations $R\_L$ and $\equiv\_L$ and see what happens.

# Answer
> 3 votes
(b) is correct.

**Hint**. I suffices to show that $\equiv\_L$ is a congruence on the free monoid $A^\*$, that is, $u \equiv\_L v$ implies $xuy \equiv\_L xvy$ for all $x, y \in A^\*$.

(a) This operation is not well defined, because $R\_L$ is only stable on one side: $u \mathop{R\_L} v$ implies $xu \mathop{R\_L} xv$ but does not necessarily implies that $uy \mathop{R\_L} vy$.

---
Tags: formal-languages
---


# Question
Title: Tight bound on the number of intersections between a line and a triangulation
I'm interested in the maximum number of intersections that a line and a triangulation on $n$ points could have. More specifically, given $n$, we are interested in the worst-case (maximum) number of intersections that any line could have with any triangulation on any point set.

There is an upper bound of $2n-5$ on the number of triangles for Delaunay triangulations, this implies an upper bound on the number of triangles for any triangulation, since any triangulation can be turned into a Delaunay triangulation using flips which don't change the number of triangles.

The first obvious upper bound is $3\cdot(2n-5)$ since there are at most $3$ edges per triangle. The next better obvious one is $2\cdot(2n-5)$ since a line can intersect at most $2$ edges of a triangle.

My current best lower bound (and I suspect that this is tight) on the number of intersections is $(n-2)\cdot2$ based on the following example (ignore the arrows, for every point added to the bottom we obtain 2 additional intersections by connecting it to the two top ones):

How to prove (or disprove) that the upper bound is $(n-2)\cdot2$?

# Answer
> 1 votes
Place $T$ triangles next to each other such that the line $l$ intersects them all. Observe how the number of intersections is $T+1$. Now substitute $T$ with the upper bound on the number of triangles for any triangulation that you mentioned, and we obtain $2n-5+1=2n-4$ as an upper bound on the number of intersections. The example provided in the question shows that the bound is tight.

---
Tags: computational-geometry, lower-bounds, upper-bound
---


# Question
Title: Proof of correctness for a triangulation-algorithm
I'm working on the following exercise:

> Consider a point set $S = \\{ p\_1, p\_2, ..., p\_n \\}$ in the plane in general position (i.e., no three points of $S$ are collinear). The points of $S$ have pairwise different $y$-coordinates and are sorted in increasing order of them, i.e., $y(p\_i) \< y(p\_j) $ if and only if $i \< j$. Develop an algorithm that computes a triangulation of $S$ and needs $O(n)$ runtime and memory.

I got the following algorithm (based on Andrew's monotone chain algorithm) from Marcelo Fornet in his answer to one of my previous questions (I condensed it a bit):

```
Input: a list P of points in the plane.

Precondition: There must be at least 3 points.

# Initialize T as empty list to store triangulation
Initialize U and L as empty lists.
The lists will hold the vertices of upper and lower hulls respectively.

for i = 1, 2, ..., n:
    while L contains at least two points and the sequence of last two points
            of L and the point P[i] does not make a counter-clockwise turn:
        Add the last two points from L and P[i] to T (the triangulation)
        remove the last point from L
    append P[i] to L

for i = n, n-1, ..., 1:
    while U contains at least two points and the sequence of last two points
            of U and the point P[i] does not make a counter-clockwise turn:
        # Add last two points from U and P[i] to T (the triangulation)
        remove the last point from U
    append P[i] to U

The triples of points in T will be the triangles

```

While I understand how this algorithm works I'm struggeling to show it's correctness in a formal way.

My idea would be to use induction on the invariant that this algorithm always prodcuces a triangulation of the given point set. This is what I tried:

Assertion: The said algorithm always returns a triangulation for a given point set.

The assertion is clear for a set of three points, so we got our induction start.

Now lets suppose the assertion holds for all sets with at most n points.

But I'm stuck at the induction step. I tried to make a case analysis wether the new point $p\_{n+1}$ lies in the upper or the lower half of the convex hull of $\\{p\_1,....,p\_n\\}$, but it didn't work out.

I'd be thankful for any kind of help.

# Answer
> 1 votes
I am here again :)

I prove it by induction as you already did. But instead of assuming that the new point is in the lower/upper hull, I assume that the point is the rightmost one (a stronger condition), so it will belong to both, lower and upper hull.

Applying euler formula we know that the total amount of triangles in a valid triangulation is $2\cdot n − h − 2$. Where $n$ is the amount of points and $h$ is the amount of points in the convex hull.

I change a bit the algorithm I proposed you before. Instead of making one sweep from left to right to build the upper hull and one from right to left to build the lower hull, lets build the lower hull with a sweep from left to right too, but this time changing the counter-clockwise condition for clockwise.

Applying the above algorithm to build the triangulation with this slightly new approach will lead you to the same solution. Let's work again on the induction, but this time assuming the new point is the rightmost one and prove the euler condition holds.

> Assertion: The said algorithm always returns a triangulation for a given point set.
>
> The assertion is clear for a set of three points, so we got our induction start.
>
> Now lets suppose the assertion holds for all sets with at most n points. The total number of triangles is $2n - h - 2$
>
> When you add a point in the rightmost position the amount of points will be $n\_1=n+1$ and the amount of points in the convex hull will be $h\_1 = h + 2 - t$ where $t$ is the total number of added triangles. The total number of triangles we are expecting is: $$2 \cdot n\_1 - h\_1 - 2 = 2 \cdot (n + 1) - (h + 2 - t) - 2$$ $$ =(2 \cdot n - h - 2) + t $$ Then the number of triangles that we have built in this last step is $t$ which implies that we have all triangles we need in the solution. Check the picture to get an intuitive idea about what is happening.

I have coded this solution in Codeforces problem, but I can't find it right now :(

---
Tags: algorithms, computational-geometry, correctness-proof
---


# Question
Title: Virtual Memory - Non-contiguous Memory Allocation
I'm studying for my operating systems final, and one question that my professor asked that I can't seem to find the answer to is the following:

"Why does virtual memory use non-contiguous memory allocation?"

The textbook only talks about virtual memory in the context of non-contiguous memory allocation, but never explains why. The only reason I can think of is because of page replacement, but I'm not even sure that's right. Anyone have any thoughts on this?

# Answer
Your professor asked you a tricky question. The answer is - *by definition*.

The virtual memory is a mechanism to map non-contiguous physical memory to contiguous logical memory (for each running process). Why does the *free* physical memory become non-contiguous? Well, processes start and stop in unpredictable order, so the memory of stopped processes ought to be reused.
> 1 votes

---
Tags: operating-systems, memory-management, virtual-memory
---


# Question
Title: Does a graph diameter equal to DFS tree depth?
given an unweighted graph, does the graph **diameter** equal to the maximum DFS tree **depth**?

and the same about BFS?

regarding both directed and undirected graphs.

thanks :)

# Answer
> 1 votes
Regarding DFS the answer is no. Here there is a counter example.

The red arcs represent the DFS tree starting from the topmost node. This tree depth is 5 while the diameter is 3.

On the other hand, the maximum BFS tree depth coincides with the diameter of the graph (of course, this is valid if the graph is connected). If you run BFS from a source node S, all path found from this point to any other point will be of minimal length, i.e it contains all shortest path from point S to any other point. Though the maximum BFS tree depth is the maximum among all shortest path.

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


# Question
Title: Syntax directed translation part of which compiler phase?
I am reading dragon book for compilers. I am not able to understand in which phase does syntax directed translation actually happen.

A CFG can have set of semantic rules attached to it which is evaluated. For example, we can have semantic rules attached to a CFG which adds the type of identifier in the symbol table. Does it happen in syntax analysis or semantic analysis phase?

# Answer
> 2 votes
I do not have the dragon book with me so my answer may be off. But generally speaking the syntax directed translation means that you start with a sequence of token (so right after the lexer) and produce *something*. The translation is said to be directed by the syntax because the *something* must be produced in a very specific way. For each grammar rule, the translation defines the translation of the left-hand-side nonterminal as a function of the right-hand-side nonterminals' translations, and the values of the right-hand-side terminals.

Here is an example. If you have the following grammar rule: $$stmt \rightarrow\boldsymbol{if}(expr)\text{ }stmt\text{ }\text{ }\boldsymbol{else}\text{ }stmt$$ And if we denote by $\[\cdot\]$ the translation then the above rule generates the translation rule $$\[\boldsymbol{if}(e)\text{ }s\_1\text{ }\text{ }\boldsymbol{else}\text{ }s\_2\]=T\_{if}(\[e\],\[s\_1\],\[s\_2\])$$ where $T\_{if}$ if the translation action for this rule.

One obvious use of SDT is to generate the AST of the input. In which case $T\_{if}$ would look something like (I use ML-like syntax) $$T\_{if}(e,s\_1,s\_2)=AstIfNode(e,s\_1,s\_2).$$ But they are other possibilities. Furthermore, it is possible to generate an AST with attributes so that we can perform semantic analysis at the same time. For example if we have the rule $$expr\rightarrow expr\boldsymbol{+}expr$$ then a translation for a "calculator-like" language could be $$T\_{+}(e\_1,e\_2)=\begin{cases}\\{type=int,val=e\_1.val+e\_2.val\\}&\text{if }e\_1.type=int\text{ and }e\_1.type=int\\\\{type=error\\}&\text{otherwise}\end{cases}$$

If we start to have identifiers, then we can attach a symbol table to the nodes. For a simple language you can build an entire compiler with a SDT (one-pass compiler), going from source code to machine code. But more advanced compilers usually just use SDT to produce an AST and then do more complicated things (notably they modify the AST).

---
Tags: compilers
---


# Question
Title: Find a simple path through a graph, vising as many vertices in Z as possible
Goal: Find a simple path in G, that visits the maximum number of vertices in Z and prove it is NP-complete.

G = (V , E)

Z is a subset of V

How would I go about doing this?

# Answer
By thinking about what **NP**-complete problems you already know about that involve finding very long paths in graphs.
> 1 votes

# Answer
First, a nitpick about your question: "and prove it is NP-complete" sounds like the problem asks to prove that the simple path is NP-complete, which is of course nonsense. Instead, your problem should probably state simply to find the path. So, while this may sound like a nitpick, so that we are sure we are on the same page, I will restate the problem:

> Input: A graph $G = (V, E)$ and a set $Z\subseteq V$.
> Output: A simple path in $G$ that maximizes the number of visited vertices in $Z$.

The question is then to show that the above problem is NP-complete. It may or may not be useful to consider a decision version of this problem: $L = \\{ \langle G, Z, k\rangle\mid G=(V,E)\text{ and }G\text{ contains a simple path visiting }k\text{ vertices of }Z\\}$

Nitpicking aside, let's examine the problem. To avoid simply handing out a solution without you having shown an effort to solve it yourself, I will be somewhat vague.

Remember that to show a problem is NP-complete, we must show a reduction from a known NP-Hard problem to the given problem. Try to think about what NP-Hard problems are similar to this problem. Can you think of any other problems on graphs that ask for a simple path that visits a large number of vertices?

If you're still having trouble, consider an instance of the stated problem where $Z=V(G)$ (and, for the decision version, $k=|V|$). Does this seem similar to an NP-complete problem you have heard of?
> 1 votes

---
Tags: algorithms, graphs, np-complete
---


title: Trying to find Worst Case complexity

text:
# Question
Title: Trying to find Worst Case complexity
I have to find computational complexity of an expression for Euclidean distance

```
d(x,y)= {(x1-x2)^2 + (y1-y2)^2}^1/2

```

But I have certain confusion because of which I am unable to proceed. Firstly there are two variables. Secondly since there is a root ,what will be its effect? If there were no roots, I can understand its worst case complexity would have been O(n^2).

I will really appreciate if someone can enlighten me in this regard Thanks in advance for your spending valuable time!

* Update

I assume that my program will run on abstract machine RAM.

# Answer
The computational complexity depends on what you want to measure. If you you're doing this computation on a common computer with floating point arithmetic, then you can estimate it mi $O(1)$, because every floating point operation (addition, multiplication and square root) is in $O(1)$.

If you use fixed point arithmetic for $n$-bit numbers, then addition can be done in $O(n)$, multiplication in $O(n^2)$, and square root in $O(n^2)$ steps (Note: For multiplication and addition are existing better bounds). Putting this together, you will add two $O(n)$-bit numbers and take the square root of the result which gives $O(n^2)$ steps.

As you can see, the runtime depends on the arithmetic used, and arithmetic determines what $n$ means. If you use $n$-bit complex number in a $n$ dimensional vector space (where $x^2$ denotes the scalar product), you probably will get other estimates.
> 1 votes

---
Tags: complexity-theory, asymptotics
---


# Question
Title: Does there exist a sorted search with $O(\log n)$ worst-case runtime and $O(\log \log n)$ on average?
I thought of some mixed algorithm: binary + interpolation search. While first has $O(\log n)$ runtime in both worst and average cases, second has $O(n)$ worst case runtime and $O(\log \log n)$ average case.

However, I think, if such algorithms can exist, there are more than one of them.

Anyway, what I want to know if there is any known algorithm with restrictions given in title.

*Note*. It must be appliable to simple arrays without repeatitions (no precomputing/hashing).

# Answer
> 5 votes
Yup. Do interpolation search, but after $\log n$ iterations, if you haven't found the answer yet, switch to binary search. This ensures a $O(\log n)$ worst-case running time, while retaining the $O(\log \log n)$ average-case running time. Note that the average case only applies if you make a particular assumption about the distribution of values in the array.

---
Tags: search-algorithms
---


# Question
Title: NP hardness of partitioning a graph into two subgraphs
Given a planner graph which it's vertexes have weights and an integer, W, this graph should be partitioned into two subgraphs which sum of weights for each subgraph becomes at least W.

I wanted to show this is np hard by reduction and I have used Max cut to show that (in max cut we have a graph with weights for edges and need to partition it's vertexes into two subgraph which the sum of weights of edges between these two subgraph, becomes at least K)

I'm not sure about how to change weights of edges in max cut to weights of vertexes in the new problem, I've considered for each vertex weight the max weight of edges which it is an endpoint for, and W=K, is this correct?? if not how to consider the weights for vertexes and W?? or another problem should be used?? I appreciate if anybody guides me by the reduction.

ps: please consider that we can not use partition since it says at least W not W, or subset sum.

# Answer
> 3 votes
I think you can in fact do this by showing a reduction from the Partition problem, as stated by Chapichap. Recall the direction of reduction that is needed to show a problem is NP-Hard. In general, it is *okay* if the problem you have is harder than the problem you are using to show hardness (in this case, the partition problem). This is because the reduction would *from* the partition problem *to* the given problem. For the partition problem, if we are given a set of numbers $S$, and we want to find a partition $S\_1,S\_2=S\setminus S\_1$, we need to show how to construct a graph $G$ and a number $W$ such that the vertices of $G$ can be partitioned as described (where the sum of weights of the vertices is at least $W$) if and only if the set $S$ can be partitioned.

Consider the following reduction: Let $G = (V,E)$ be a graph where $V=S$. That is, for each number in $S$, create a vertex in $G$. The edge set seems irrelevant here, so we can let $E=\varnothing$. The weight of each vertex is equivalent to the number in $S$ to which it corresponds. Finally, let $\lceil W=(\sum\_{x\in S} x)/2\rceil$. That is, $W$ is the sum of the weights of all the elements of $S$, divided by two.

Asking for a partition in $G$ such that each partition has total weight at least $W$ means asking for each partition to contain half of the total weight of the graph. To be thorough, consider the case where $\sum\_{x\in S}$ is even. Then $W$ is exactly half of the total weight of all vertices in the graph, and so for each partition to have a total weight of at least $W$, each partition must have equal weight. Thus such a partition of the vertices is equivalent to an equal-sum partition of the elements of the original set. Now, consider the case where $\sum\_{x\in S}$ is odd. In such a case, $S$ has no partition such that the sum of the partitions are equal. However, the way we constructed $W$ ensures that $2W = (\sum\_{x\in S})+1$ and so it is impossible to partition the graph so that each partition has total weight at least $W$ (the existence of such a partition would imply that the total weight of the graph is strictly greater than $\sum\_{x\in S}$, which is impossible).

Hopefully you can see from the above that $G$ has a partition into two subgraphs such that the sum of the weights of vertices in each partition is at least $W$ if and only if the original set $S$ had a partition of its elements into two subsets such that the sums of elements in each subset are equal.

# Answer
> 0 votes
What do edges represent in your initial graph?. I don't see why you need a graph structure to represent your problem. It may just as well be a set of numbers, which you want to partition into two subsets of weights at least $W$. Perhaps variations of the subset sum problem if some vertices have negative weights https://en.m.wikipedia.org/wiki/Subset\_sum\_problem Or the partition problem otherwise https://en.m.wikipedia.org/wiki/Partition\_problem would be more useful for your reduction.

---
Tags: complexity-theory, np-hard, max-cut
---


# Question
Title: How to prove that $n\log n$ is space constructible?
I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that if both $n$ and $\log n$ are space constructible, $n\log n$ will be space constructible as well.

I'm using Sipser's definition of space constructibility:

> A function $f\colon N\to N$, where $f(n)$ is at least $O(\log n)$, is called space constructible if the function that maps the string $1^n$ to the binary representation of $f(n)$ is computable in space $O(f(n))$.

# Answer
You are right that if we can construct both $n$ and $\log n$ in $O(n\log n)$ space, we can construct $n\log n$ by multiplying these two values. I think constructing $\log n$ is actually the harder part here, which you seem to have already figured out. But let's go through it.

First, recall that a $k$-tape Turing Machine can be simulated on a single-tape Turing Machine by concatenating all the tapes onto a single tape. I am glossing over the details a bit here (but see Sipser for the details), but the key observation is that the space complexity can equivalently be viewed as the total space used across all tapes of a $k$-tape Turing Machine. So if we can construct a procedure for a $k$-tape Turing Machine that uses $O(n\log n)$ space across all tapes, then we have shown that $n\log n$ is space constructible.

We can construct $\log n$ through repeated halving of $n$. Specifically, we can copy $1^n$ from our initial tape containing the input to a second tape. Then, we can blank half of the ones on this second tape. Once we have blanked half of the ones, this tape will store $1^{n/2}$. We can repeat this halving process until there is only a single $1$ left. We count the number of halvings performed, in binary. We simply maintain a binary counter on a third tape, and perform a binary increment each time we perform a halving on $n$. At the end, the third tape will store the binary representation of $\log n$.

I am assuming that you already had figured the above out since you said you managed to prove $\log n$ is space constructible. And indeed you are correct that if we can independently construct $n$, we can multiply $n$ by $\log n$ in binary, using at most $n\log n$ space (in fact we will need less). All we really need then is to write out the binary representation of $n$ to another tape. Recall how we convert numbers to binary representation: the least significant bit of the binary representation of $n$ is $n\bmod 2$. Then, we can convert $\lfloor n/2\rfloor$ to binary (in a recursive manner) to compute the remaining bits. So, our Turing Machine will continue as follows: Copy $1^n$ to an available tape. Then, compute $n\bmod 2$. Note that we can do this fairly easily (If you are following Sipser, you should hopefully be comfortable with the fact that the set of all even-length strings is even a regular language). We write out the value of $n\bmod 2$ to another tape (call this the "$n$ tape"). Then, we perform the halving procedure on the $1^n$ again. Here, we should be careful about how we handle the case where $n$ is odd: we round down (For example, if $n=5$, after the halving procedure, the tape should contain $11$, the unary representation of $2$). This is to ensure the halving semantics are consistent with $\lfloor n/2 \rfloor$. Then, we move the head on the "$n$ tape" to the left one space, compute the mod once again, and write the result to the "$n$ tape" again. If we continue this modding and halving, writing the results of the modding to the left of the previously written bits on the "$n$" tape, we will eventually write out the binary representation of $n$ (once the working tape has only a single $1$ on it, the "$n$ tape" will contain the binary representation of $n$).

After these two procedures, we should have $\log n$ on one tape and $n$ on another tape, both in binary. Then, as you have already recognized, we can compute the product in $O(n\log n)$ space.
> 2 votes

---
Tags: complexity-theory, space-complexity
---


# Question
Title: What is difference between nondeterministic polynomial time and exponential time?
I am not very into computer science theory but i feel like people are defining nondeterministic polynomial time as if it is another name of exponential time. I would be happy if you clarify it. thank you

# Answer
> 6 votes
Every nondeterministic polynomial time algorithm can be converted to an exponential time algorithm, where exponential means $O(e^{n^C})$ for some constant $C$. The converse probably doesn't hold.

# Answer
> 3 votes
The class of problems solvable by a nondeterministic Turing Machine in polynomial time is $\mathsf{NP}$, for Nondeterministic polynomial time. This definition has nothing to do with exponential time or exponential functions at all. The class of problems solvable by a deterministic Turing Machine in exponential time is $\mathsf{EXP}$.

However, can consider the computation tree for a nondeterministic polynomial time TM. If we perform breadth-first search on this tree, we can simulate all possible computational branches in deterministic exponential time. This shows that $\mathsf{NP}\subseteq\mathsf{EXP}$, though it certainly isn't necessarily the case that $\mathsf{NP} = \mathsf{EXP}$.

# Answer
> 0 votes
Nope. You are not right. As, a deterministic polynomial is a non-deterministic polynomial too. Hence, a non-deterministic polynomial class is not equivalent to exponential class.

To understand it better, you can think about the related Turing machine.

---
Tags: nondeterminism, polynomial-time
---


# Question
Title: P class definition in Garey and Johnson's Computers and Intractability
I'm reading right now Computers and Intractability by Garey and Johnson. I've found the definition of PTIME complexity class a little strange. This is how it looks:

Let $\Sigma = \\{ 0,1\\}$. By $\Sigma^{\*}$ we denote the set of all finite strings created from symbols from $\Sigma$. If a computation on a Deterministic Turing Machine with input $x \in \Sigma^{\*}$ ends in $q\_{y}$ (yes-state), it means that TM accepts this input. Language $L\_{M}$ recognised by the machine $M$ is given by:

$L\_{M} = \\{ x \in \Sigma^{\*} :$ $M$ accepts $x \\}$.

Time complexity function is given by:

$T\_{M} = max\\{ m : $ there is an $x \in \Sigma^{\*}$, with $|x| = n$, such that the computation of $M$ on input $x$ takes time $m$$\\}$.

We call program $M$ a polynomial time DTM program if there exists a polynomial $p$ such that, for all $n \in \mathbb{Z}^{+}$, $T\_{M}(n) \leq p(n)$.

Then they give such $P$ class definition:

$P = \\{ L :$ there is a polynomial time DTM program $M$ for which $L=L\_{M} \\}$

---

Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input? What about input that also causes halting, but in rejecting state $q\_{n}$? Shouldn't these be also in PTIME?

Do I understand this correctly? If yes, why they decided to define P class in such way?

P.S. Maybe that matters, I have the first edition of the book (1979).

# Answer
> 1 votes
The definition given is the standard one. Before reading the rest of this answer, I recommend that you carefully go over the definition again. A lot of what you're asking is "What does the definition say?" and you'll probably understand it better if you figure it out yourself. The rest of your question is, "Why did we choose that definition?"

---

The definition is equivalent to the following. A Turing machine $M$ "runs in polynomial time" if there is some polynomial $p$ such that $M$ halts in at most $p(n)$ steps for all inputs of length $n$. A language is in **P** if it is the set of strings accepted by some Turing machine that runs in polynomial time.

> Does this mean that their P complexity class contains only languages that are composed of yes-instances, i.e. languages recognised by $M$, consisted of $x$ strings such that $M$ always halts in accepting state for every of them as an input?

Yes, that's what the definition says. It also says a little more: the language recognised by $M$ doesn't include any of the "no" instances.

> What about input that also causes halting, but in rejecting state $q\_{n}$?

If a machine runs in polynomial time, it halts for *all* inputs. Thus, for any given input, the machine either accepts or rejects. The whole point is that the Turing machine tells you exactly which inputs are in the language and exactly which inputs are not. If the machine rejects an input, that input isn't in the language.

> Shouldn't these be also in PTIME?

This is a category error. **P** is a class of languages, not inputs.

However, you might be thinking of the following. We could also define a language that is the set of strings *rejected* by some Turing machine that runs in polynomial time. Perhaps you're wondering why that language isn't in **P**? Well, it is, because it's also the set of strings accepted by some polynomial-time Turing machine. Just take the machine that defines the language by rejecting and modify it so that every instruction "go to the accepting state" becomes "go to the rejecting state" and vice-versa. Now you have a Turing machine that defines the language you're interested in, but defines it by acceptance.

# Answer
> 0 votes
As you remark, inputs that halt in a rejecting state should also take polynomial time for $M$ to be a polynomial-time DTM.

Note that the running time $T\_M$ as defined in your question is indeed defined as the maximum over the running time of Turing machine $M$ for **any** size-$n$ input (namely, the running time for any $x \in \Sigma^\*$ with $|x| = n$).

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


# Question
Title: Algorithm. Input: pointers to k unsorted arrays of different lengths. Needed output: k sorted arrays
$k = \Theta(n)$

The arrays consist only natural numbers $1$ to $n$

The sum of the length of all arrays = $\Theta(n)$

It should return the $k$ original arrays, each sorted on its own.

The running time should be at worst $\Theta(n)$. How is it even possible? There's something I must be missing because I have no idea how to approach this. The data I gave you is all the given data. Any ideas?

Using counting sort on each array won't work, for it will be $\Theta(n^2)$, but maybe a different approach using this method?

# Answer
> 1 votes
You can solve the issue by using some pointers. First, run counting sort algorithm on all arrays in $\Theta(n)$ (suppose all of them are in a set). In the meanwhile, when running the algorithm, set a pointer for each number of each array to the sorted index of that number.

Using this data structure, you will have $k$ sorted arrays at the end.

---
Tags: algorithms, counting
---


# Question
Title: Can Hall's theorem be applied to scheduling problems?
If I have a scheduling problem, is it possible that Hall's theorem can be applied? I was thinking that the graph representation of the scheduling problem can be the preferences of the people / workers getting scheduled. Is there any such result or counter-claim?

# Answer
A Characterization of Open Shop Scheduling Problems Using the Hall Theorem and Network Flow, a thesis by Arunasri Chitti may provide what you need.

The abstract reads:

> Open shop scheduling problems are combinatorial problems where jobs with certain processing requirements on a number of different machines must be arranged in such a way that objectives related to completion time are optimized. Such problems have applications over a wide spectrum including such as communications, routing and manufacturing.
>
> Many open shop problems are NP-hard but there are a number of special cases which possess polynomial solutions in the case of few machines or few jobs or when preemption of jobs is permitted. Many such solutions are based in the theory of matching or Hall’s theorem, or more generally network flow. The primary focus of this thesis is to describe a number of polynomial-time solutions which are constructed using these related concepts and methods.

The paper discusses the problem of scheduling resources to needs in a reasonably optimized fashion, Open Shop Scheduling, and how a particular subset of those scheduling problems "are a number of special cases that do have polynomial solutions and those solutions often come from the theory of matching, network flow and Hall’s theorem, which are related concepts and methods." See What is an NP-complete in computer science as well as What are the differences between NP, NP-Complete and NP-Hard?. Also see the Wikipedia topics NP-hardness and NP-completeness.

Scheduling in the context of the paper is defined as:

> Scheduling deals with the arrangement of a given set of jobs, on the given machine such that the provided resources are assigned to the jobs in an optimal way. Scheduling provides us the starting and the completion time for each operation or job.

A Scheduling problems in the context of the paper is defined as:

> According to Peter Brucker \[1\], a Scheduling problem is defined as following: Given m machines Mj (j= 1, 2...m) and n jobs Ji (i= 1, 2…n), a schedule now is allocation of one or more time intervals for each job on one or more machines.

The thesis goes on to demonstrate the use of applying flow theory to a particular subset of matching resources to needs using graphs. The thesis concludes with:

> Open Shop Scheduling problem is different from other scheduling problems. This shop problem is very closely related to matching. Although, we have surveyed number of problems where Hall technique works, yet there are unexplored problems where matching is applied. The connection between algorithms of parallel machines and open shop are more close than other shop problems. In this thesis, we have learnt flow techinques are useful and seem to be one of the strongest tools available for non-NP Complete scheduling problem.
> 4 votes

---
Tags: graphs, discrete-mathematics
---


# Question
Title: Is there some mathematical properties of the distribution which is the output of a probabilistic polynomial-time Turing machine?
Let $S\_{n}$ be an input set whose elements are length $n$, namely $S\_{n} = \Sigma^{n}$. For every probabilistic polynomial-time algorithm $A$ and any $u \in \Sigma^{\*}$, there exists a function $f^{A}$ such that $f^A(u) = \mathrm{Pr}\[A(u) = 1\]$. And let $f^{A}\_{n} = \left.f^{A}\right\vert\_{S\_{n}}$ be a function from $S\_{n}$ to $\[0,1\]$.

Is there some properties about what $f^A\_n$ looks like? Or is there some references that introduce about this?

Indeed, let $F\_{n} = \\{ f^{A}\_n \mid A \text{ is a PPT algorithm} \\}$. And if we define $$\mathrm{Dist}\_{n}(f^{A},f^{B}) = \sum\_{u \in S\_{n}} \left\vert f^{A}(u) - f^{B}(u)\right\vert$$ and $$d\_{1}(n) = \inf \\{ \mathrm{Dist}\_{n}(f^{A},f^{B}) \mid f^{A} \neq f^{B} \\}$$ how does $d(n)$ grow?

How about $$d\_{2}(n) = \sup\_{g} \inf\_{A} \mathrm{Dist}\_{n}(f^{A},g)$$ where $g$ is a function from $\Sigma^{\*}$ to $\[0,1\]$.

# Answer
Given a probabilistic algorithm $A$, define $f^A(x)=\Pr\[A(x)=1\]$. To make the question interesting, you have to ask whether $f^A$ (with polynomial $A$) can be close to $g$, for infinitely many values of $n$. Otherwise, as Raphael mentioned, you can pretty much obtain any $g:\Sigma^n\rightarrow \[0,1\]$, while keeping $A$ polynomial (there is no asymptotics). Consider the problem of how $dist\_n(f^A,g)=\sum\limits\_{x\in S^n}\left|g(x)-f^A(x)\right|$ grows as a function of $n$. Obviously $dist\_n(f,g)\le 2^n$, and a random guessing $A$ achieves $dist\_n(f^A,g)\le 2^{n-1}$, can we find a probabilistic polynomial algorithm $A$ such that $dist\_n$ grows polynomialy?

Let $L\subseteq\Sigma^\*$ be some language, and $f^L:\Sigma^\*\rightarrow \\{0,1\\}$ be its indicator function, i.e. $f^L(x)=1\iff x\in L$. If for large enough $n$ it holds that $\sup\limits\_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le\frac{1}{2}-\epsilon$, then $\mathsf{L\in BPP}$ (simulate $A$ several times and take the majority vote, this works for $\epsilon=n^{-d}$). If for large enough $n$ you have $\sum\limits\_{x\in\Sigma^n}\left|f^L(x)-f^A(x)\right|\le poly(n)$, then $\mathsf{L\in P/Poly}$, since your advice can contain information about all strings $x\in\Sigma^n$ on which $f^L,f^A$ differ by more than (say) $\frac{1}{3}$, and on the rest of the strings you can take the majority vote as above.

Thus, to answer your question, if $g$ is an indicator function for a hard language, you can expect (under some hardness assumptions) that there is no probabilistic polynomial time algorithm $A$ for which $Dist\_n(f^A,g)$ is polynomial in $n$.
> 1 votes

---
Tags: probabilistic-algorithms
---


title: Logic Circuits - Binary divisible by 16

text:
# Question
Title: Logic Circuits - Binary divisible by 16
I have a question

```
  Given a 16-bit register A holding a number in 2’s complement form, use a
   single gate (e.g., AND, OR,
  XOR, NAND, NOR, NOT) with an arbitrary number of inputs to implement a
  circuit that produces an
  output 1 if the number is divisible by 16, and an output 0 otherwise. The
 bits are labelled A15, A14, ..., A0.

```

I'm confused at how this answer is expected because the question is only 2 marks my answer was that it would be a single XOR gate with inputs a0-a15 - would this be correct and why?

# Answer
> 0 votes
A decimal number is divisible by 100 if it ends with two zeroes. The same thing happens in your case, and leads to a solution using a single NOR gate.

---
Tags: logic, circuits, binary
---


# Question
Title: Cycles in undirected graph: reducing to minimum
I am working on the problem of finding cycles in an undirected graph. I made up my solution by first detecting if any cycles are present with a DFS algorithms and detecting any backtracking, and second, recursively explore all the found backtracked edges until I find the starting vertex. The problem I have is that this approach gives additional cycles, and I don't know how I can remove them in a post-processing step.

The classical way is to represent the cycles as binary vectors, and then XOR them by pairs: if the result is equal to another cycle, then the latter can be removed.

For example, consider the following graph, that obviously has only two basic cycles:

Exploring all possible cycles will give these 3:

```
c1: 1-2-3
c2: 2-3-4
c3: 1-2-4-3

```

Converting to binary vectors:

```
edge | c1   c2   c3
1-2  | 1    0    1
1-3  | 1    0    1
1-4  | 0    0    0
2-3  | 1    1    0
2-4  | 0    1    1
3-4  | 0    1    1

```

Computing $c1 \oplus c2$ will give 110011, which is equal to c3, so we can remove c3.

But in many situations, this is not enough. For example, consider the following graph, having $v=4$ vertices and $e=6$ edges.

A well know result states that for a single-connected graph with $v$ vertices and $e$ edges, the number of cycles will be $c=e-v+1$, so we have 6-4+1=3 cycles in this example.

But by proceeding with my approach, I get the following 4 cycles:

```
c1:   1-2-3
c2:   1-2-4
c3:   1-3-4
c4:   2-3-4

```

If I convert them to binary vectors and XOR them, I am not able to remove the additional cycle.

```
edge | c1  c2  c3  c4
1-2  | 1   1   0   0
1-3  | 1   0   1   0
1-4  | 0   1   1   0
2-3  | 1   0   0   1
2-4  | 0   1   0   1
3-4  | 0   0   1   1

```
* $c1 \oplus c2 = 011110$
* $c1 \oplus c3 = 101101$
* $c1 \oplus c4 = 110011$
* $c2 \oplus c3 = 110011$
* $c2 \oplus c4 = 101101$
* $c3 \oplus c4 = 011110$

All these computations produce binary vectors with 4 '1', while all the initial cycles have 3. Thus I can remove none.

Note that this not only a matter of a (single) one additional cycle. For more complex graph (say, Petersen graph for example), I get more than one additional cycles.

I am looking for any ideas on how to remove the additional cycles.

---

**Edit**: As suggested in answer, I have build the incidence matrices for the two examples above:

```
             A1                A2
vert:      1 2 3 4           1 2 3 4
       1 | 1 1 0 0 |     1 | 1 1 0 0 |
       2 | 0 1 1 0 |     2 | 0 1 1 0 |
edges: 3 | 1 0 1 0 |     3 | 1 0 1 0 |
       4 | 0 1 0 1 |     4 | 0 1 0 1 |
       5 | 0 0 1 1 |     5 | 0 0 1 1 |
                         6 | 1 0 0 1 |

```

**Edit 2** For A2, I computed the Reduced Echelon Form (that I understand is useful to find the solutions to $AX=0$):

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

But this stills end up with a null vector...

**Edit 3**: I come back to this question as I still didn't get it. The answer from @Yuval Filmus suggest to solve $A x = 0$ to find the cycle basis. But what exactly represents the different $x\_i$ values? Because if I make a parallel with linear algebra, then using the matrix $A2$, this would mean I need to solve this:

$ \begin{aligned} x\_1 + x\_2 &= 0 \\ x\_2 + x\_3 &= 0 \\ x\_1 + x\_3 &= 0 \\ x\_2 + x\_4 &= 0 \\ x\_3 + x\_4 &= 0 \\ x\_1 + x\_4 &= 0 \\ \end{aligned} $

Beside the fact that the solution to this is $\\{0,0,0,0\\}$, I don't understant what $x\_i$ represents.

# Answer
Consider the incidence matrix of your graph, which is the $E \times V$ matrix in which each row contains exactly two 1s, corresponding to the vertices constituting the given edge, and the rest of the entries are 0. We think of the entries as belonging to $\mathbb{Z}\_2$. A set of edges is in the left kernel of the matrix iff it is an XOR of cycles; it is known as the cycle space of your graph. You can find a basis for the cycle basis by finding a basis for the left kernel (this is an exercise in linear algebra). The basis will contain $|E|-|V|+c$ elements, where $c$ is the number of connected components.

If you don't like XOR, you can instead orient your edges arbitrarily, and then use the orientation to form a matrix in which each row contains one $1$ entry and one $-1$ entry. The left kernel of the matrix over the integers is known as the *integral cycle space* (also described in the link above), and it consists of sums (with integer coefficients) of cycles, where now a cycle is a sum of edges, some of which are possibly negated so that the orientations match.
> 2 votes

---
Tags: graphs
---


# Question
Title: Graph coloring decision problem NP-complete
> Given a graph $G = (V, E)$ and a natural number $k$, consider the problem of determining whether there is a way to color the vertices with two colors in such a way that at least $k$ edges are polychromatic.
>
> Prove that this problem is NP-complete.

I thought about reducing it to the 3-colorability problem, but I can't figure out a possible transformation that would work.

Any leads?

# Answer
> 1 votes
A simpler reduction is from MAX-CUT. The idea is to represent each edge as a gadget which is a complete bipartite graph having $N$ vertices on each side. By choosing $N$ large enough, we can force any potential coloring to color all vertices on one side using color 1, and all vertices on the other side using color 2. You can now connect these gadgets in such a way that the maximum number of bichromatic edges is closely related to the maximum cut in the original graph.

I'll let you work out the details.

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


# Question
Title: Worst time complexity for finding a median number for a list and array data structure
This was a question that came up in a past exam paper in my computer science course, it states:

"There are two simple, un-optimised sorted data structures, each storing n numbers. The first is a list; the second is an array. What is the worst-case complexity of extracting the median number from each data structure? Are the averages cases different? Why?"

I would like to know the answer to this question as I am confused on what is being asked? Should we not be analyzing algorithms like binary search and not the data structures themselves?

# Answer
> 1 votes
The term "data structure" typically refers to a way to organize/store data, *and* the operations to create, maintain, and access them.

The asker is probably expecting you to assume specific implementations, probably as given in the course, then come up with algorithms to access the median, and discuss their respective runtime cost.

# Answer
> 0 votes
If your data structure is sorted, you don't need to use binary search to find the median — you just need to access the correct element. Accessing an arbitrary element in an array takes time $O(1)$, but in a list it could take $\Theta(n)$. This shows that the running time of an algorithm could depend on the data structure, since the running time of operations on the data structure figures in the time complexity of the algorithm.

---
Tags: algorithm-analysis, data-structures, runtime-analysis
---


title: Self-Referential Proof

text:
# Question
Title: Self-Referential Proof
The theorem that "all languages are undecidable" offers the self-referential program as evidence in its proof, assuming that there exists a decider that decides L. The goal is to disproof this proof as it is not true that all languages are undecidable.

# Answer
The mistake is that the function `willAccept` doesn't necessarily halt, and so this program doesn't have to accept or reject — there is a third possibility, namely, that it never terminates. In fact, this proof shows that `willAccept` is not computable.
> 1 votes

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