# Question
Title: How can I use prefix sum of an array to solve this problem?
I attempted this question on hackerrank. It seemed simple enough, and my program ran on small inputs. But my approach was "naive". And failed for more computationally intensive inputs. Here is the question:

**Problem Statement**

You are given a list of size , initialized with zeroes. You have to perform operations on the list and output the maximum of final values of all the elements in the list. For every operation, you are given three integers , and and you have to add value to all the elements ranging from index to (both inclusive).

**Input Format**

First line will contain two integers and separated by a single space. Next lines will contain three integers , and separated by a single space. Numbers in list are numbered from to .

**Constraints**

2 ≤ N ≤ 10^7
1 ≤ M ≤ 2 * 10^5
1 ≤ a ≤ b ≤ N
0 ≤ k ≤ 10^9

**Output Format**

A single line containing maximum value in the updated list.

Here is the editorial describing how to solve the problem

> You are given a list of size N, initialized with zeroes. You have to perform M queries on the list and output the maximum of final values of all the N elements in the list. For every query, you are given three integers a, b and k and you have to add value k to all the elements ranging from index a to b(both inclusive).

First thought which comes into mind after reading this problem will be segment tree with lazy propogation but that will not pass here as N \<= 10^7 :)

So, We have to use some different kind of approach. We can do a O(1) update, i.e. given a b k add k to index a and add -k to index (b+1). By doing this kind of update ith number in array will be prefix sum of array from index 1 to i.

So, We can do all M updates in O(M) time. Now we have to check the largest number in the original array. i.e. the index i such that prefix sum attains maximum value.

We can calculate the all prefix sums as well as maximum prefix sum in O(N) time which will get Accepted. Another approach is we can do it in O(MlogM) time because we have to check the value of prefix sum at only 2\*M indices. i.e. a and b values of all the updates. See setter's code.

I don't understand how adding k to index a and adding -k to index (b+1) gives us an array in which the the ith number in the array is the prefix sum of the array from index 1 to i.

# Answer
> 2 votes
Consider a new type of query (t2q, type 2 query) of the form $(index, value)$ where we add $value$ to all items from $index$ to the end.

Then the original type of query (t1q, type 1 query) is equivalent to 2 t2q. $(lower, upper, value) \equiv (lower, value) \oplus (upper+1, -value)$. Notice that the second t2q cancels the first t2q over all items that should not be affected

Now, 2 t2q with the same $index$ could be reduced to a single t2q easily. $(index, valueA) \oplus (index, valueB) \equiv (index, valueA+valueB)$. Therefore, we have at most $N=\text{size of our vector}$ type 2 queries. In other words, we can store all those queries in a vector. And if there is an $index$ with no query associated, we just create a "dummy query" using the identity element of our operation (zero in this particular problem).

$$ (index, value) \equiv t2q\[index\]=value $$

Next, a particular item in our vector $v\[j\]$ is only affected by a t2q iff $index \<= j$. In other words, $v\[j\]$ is affected by all type 2 queries with lower $index$. To calculate the value of a particular $v\[j\]$ just add all $values$ of t2q with lower $index$ and add the value of $v\[j\]$ which is zero.

$$ v'\[j\] = v\[j\] + \sum\_{i=0}^j{t2q\[i\]} = \sum\_{i=0}^j{t2q\[i\]} $$

If we iterate from the beginning, then each item can be calculated in $\mathcal{O}(1)$ if we store the previous sum. And simultaneously, we look for the maximum.

$$ v'\[j+1\] = \sum\_{i=0}^{j+1}{t2q\[i\]} = t2q\[j+1\] + v'\[j\] $$

**Edit**

This approach will take $\mathcal{O}(M+N)$-time and $\mathcal{O}(N)$-space, because we first process every query in $\mathcal{O}(1)$ (updating two positions in our vector), adding $\mathcal{O}(M)$, and then we spend $\mathcal{O}(N)$ looking for the maximum.

Like you said, there are $\mathcal{O}(M)$ values different than zero in $t2q$. We can ignore those zeros using a Self-balancing Binary Search Tree instead of a vector. Then we go from $\mathcal{O}(1)$ to $\mathcal{O}(lg\\,M)$ while updating every entry (process every query) and from $\mathcal{O}(N)$ to $\mathcal{O}(M)$ for store all those entries.

So now, we first spend $\mathcal{O}(M\\,lg\\,M)$ to process all queries ($\mathcal{O}(M)$ insertions of $\mathcal{O}(lg\\, M)$. Then we traverse in-order looking for the maximum using the previous idea in $\mathcal{O}(M)$.

$$ v'\[j\] = t2q\[j\] + v'\[i\] \\, \text{iff} \\, (index, 0) \\, \forall i \< index \< j $$

Finally, this new approach takes $\mathcal{O}(M\\,lg\\,M)$-time ($\mathcal{O}(M\\,lg\\,M)$+$\mathcal{O}(M)$) and $\mathcal{O}(M)$-space. Even better, is (reasonably) independent $N$ (now we can handle $N \approx 2^{64}$).

---
Tags: algorithms, arrays
---


# Question
Title: How to conceptually represent attributes (characteristics) of an object in logics?
I am reading about/working on the knowledge representation using OpenCog framework http://wiki.opencog.org/w/OpenCog\_Framework which essentially is special kind of probabilistic logic (s.c. PLN - Probabilistic Logic Networks) that smoothly generalizes crisp logic (by assigning strength and confidence to the crisp truth value).

My question is - how to represent attributes in logic (in OpenCog or in any other logic). E.g. I want to express the statement `'An apple #1 has price 1$'` (`#1 is Apple; #1.price=1$`). How can I do this in any logic?

My current solution is that I need to define 3 entities: apple a1, price p1, 1$\_value v1 and enter those entities into whole-part relationships: whole\_part\_relation(a1, p1), whole\_part\_relation(p1, v1). Those relations are for instances and apparently similar relations can be formed for classes (concepts) as well. **Is my representation of attributes by whole-part-relationships acceptable?**

OpenCog has list of all supported types of terms (s.c. Atoms) and their relationships (e.g. Links) http://wiki.opencog.org/w/Category:Atom\_Types but one can see that attribute link/relationship is not first class citizen in this logic as it is not in many other logics as well.

So - my question is - **how to represent attributes in the logics in which attributes are not first class citizens?**

There is need to formalize software development, to mode real world, to create knowledge bases for e.g. robotics and therefore the conceptualization of notion of attribute (characteristic) is important!

# Answer
> 1 votes
For this discussion, I'll use classical first-order logic. I'll interpret your term "first-class citizens" to mean those objects which can be quantified over or passed as arguments to predicates and functions. The examples provided below are toy examples, purely for expository purposes. Have a look at the leading AI textbook which gives a much more extensive, proper introduction to this subject.

There are often many ways to formalize a given statement in logic. Let's consider your example 'An apple #1 has price 1$'. There are some naive ways that come to mind:

`price(apple1)` this is a function which yields the price
`Price(apple1,80)` this is a predicate

As for your question, "Is my representation of attributes by whole-part-relationships acceptable?", it at least raises eyebrows. Generally, whole-part relationships should reflect the notion that the part is part of the object structure itself, not some attribute of the object. So while `has-part(apple,stem)`, `has-part(apple,skin)`, `has-part(apple,seed)` seem reasonable, `has-part(apple,price)` does not.

Now for your main question, "how to represent attributes in the logics in which attributes are not first class citizens?" you can use either functions or predicates. Examples are given under the paragraph above describing some ways one can formalize a given statement in logic.

---
Tags: programming-languages, logic, modelling, knowledge-representation
---


# Question
Title: What is the theoretical speedup with pipeline system over a nonpipelined system?
What is the theoretical speedup that could be achieved with the pipeline system over a nonpipelined system?

The equation I use for speedup is

$$ S = \frac{nT}{(k+n-1)t}\\,$$

where:

* $n$ is the number of tasks
* $T$ is the time to process a task
* $k$ is the number of stages segments
* $t$ is the time per stage segment

I dont understand how to use this equation for this particular question.

# Answer
> 2 votes
The total time to compute $n$ tasks with no pipelining is $nT$ (the top of your fraction). The total time to compute $n$ tasks with a pipeline $k$ stages deep, and a clock cycle time of $t$ is $nt$ (to produce the results once the first task reaches the last pipeline stage) + $(k-1)t$ to get the first task from the beginning of the pipeline to the last stage. This is the $(k + n - 1)t$ in the bottom of your fraction.

The part you are missing is that $kt$ (the time for each task to get from beginning to end of the pipeline) must be larger than $T$. This is because in the perfect case you would divide the circuit of delay $T$ into $k$ exactly equal segment, but then you would need to insert a register between each segment and the next, which will add delay.

So replace $t$ with $T/k$ in your fraction and take the limit as $k\rightarrow\infty$ and you will have your answer.

More interesting is to replace $t$ with $T/k + r$ where $r$ is the constant extra register delay that you need to add between stages, take the derivative of your fraction with respect to $k$ and set it equal to 0 and solve

# Answer
> 2 votes
At the limit as $n \to \infty$, $k+n-1$ approaches $n$.

Assuming our pipeline is efficient, $T = kt + c$, where $c$ is small.

Substituting in, $\frac{nkt}{(k+n-1)t} \to k$ as $n \to \infty$.

In other words, the speedup due to pipelines is roughly $k$, the number of stages in the pipeline.

Of course, this implies the absurdity that all we need to do to add speed is to add stages... So you need to measure pipeline efficiency (that is, make sure the cost of staging, $c$, is small).

---
Tags: computer-architecture
---


# Question
Title: Pumping Lemma: Is language with equal number of "aa" and "bb" regular?
Given alphabet $\Sigma=\\{a,b\\}$, is the language $$L = \\{ w \mid w\text{ contains an equal number of substrings }aa\text{ and }bb \\}$$ regular? My initial though was no, because the language $L' = \\{a^nb^n\mid n\ge0\\}$, is not regular, and is of the same general form as $L$. However, I am confused about how $aa$ and $bb$ being substrings affects the proof, via pumping lemma. Is it proper to select a "specific" $s$ for the pumping lemma, such as

$$s = a^p(aa)^pb^p(bb)^p\\,?$$

Is there a better $s$ I could choose? In general, how would I pick an $s$ when I am dealing with a language written based upon substrings, like $L$?

# Answer
Your intuition is correct: regular languages can't count. Indeed, a quick way to prove that $L$ isn't regular is to observe that $L\cap \\{a^mb^n\mid m,n\geq 0\\} = L'\cup\\{a,b\\}$. Since the intersection of any two regular langauges is regular, and $\\{a^mb^n\mid m,n\geq 0\\}$ is certainly regular, it must be that $L$ is not – because if it was regular, then its intersection with $\\{a^mb^n\mid m,n\geq 0\\}$ would have to be regular, and it isn't.

To prove with the pumping lemma, you need to show that, for every $p\>0$, there is a string $s$ of length at least $p$ such that every way of writing $s=xyz$ with $|y|\geq 1$ and $|xy|\leq p$ has $xy^nz\notin L$ for some $n\geq 0$. (I originally wrote "just need to show" but deleted "just" because the statement that follows is such a mouthful!)

Your string $s$ works just fine. If we rewrite it in the required form $s=xyz$, the fact that $|xy|\leq p$ means that $x=a^k$, $y=a^\ell$, with $1\leq\ell\leq p$ and $0\leq k\leq p-\ell$. And $z$ is the rest of the string. But, now, for any $n\neq 1$, we have \begin{align\*} xy^nz &= a^ka^{n\ell}a^{p-k-\ell}(aa)^pb^p(bb)^p\\ &= a^{3p+(n-1)\ell}b^{3p}\\,, \end{align\*} and this string is not in $L$, since the number of $a$s at the front is different from the number of $b$s at the back, so the number of $aa$ substrings is different from the number of $bb$s.

Insofar as that proof works, there's no problem with your choice of $s$. But, if you read through the proof, you'll see that there would have been a bit less writing if you'd just chosen $a^pb^p$. The point is that, when something in the $a^p$ part gets "pumped", it breaks the required property of having the same number of $aa$s as $bb$s.

It's hard to give general advice, because proof is a creative act and you can't just follow recipes. The general scheme is to pick a string where repeating any sequence of characters from the first $p$ will break the property that defines the language.
> 3 votes

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


# Question
Title: Which one grows faster asymptotically: $\log(\log^an)$ or $\log^a(\log n)$
Could someone explain to me which function grows faster?

$f(n)=\log(\log^an)$ or $g(n)=\log^a(\log n)$

# Answer
Assuming $\log^a n$ means $\log n$, raised to the power $a$:

Let $t = \log \log n$, then the first expression equals $t·a$, while the second expression equals $t^a$. For $a \> 1$ the latter grows faster, for $a \< 1$ the former is faster, and for $a = 1$ they are identical.
> 8 votes

---
Tags: asymptotics
---


title: Regretting Computer Science?

text:
# Question
Title: Regretting Computer Science?
A message I sent to a CS professor:

So I have a question about computer science in general.

I would like to build "stuff" in the future, not just program my whole life. I'm not sure if I did right by majoring in Computer Science instead of an engineering field. I could always get my masters in Software Engineering but I was wondering, if I like to build "stuff" and watch it come to life, would computer science still be something I should major in?

Yes I like coding, but I would also like to build "stuff." By "stuff" I mean technology such as virtual reality goggles and so forth.

Can anyone answer this for me?

# Answer
> 3 votes
There are 2 parts of building "stuff". The physical components of the system and the behaviour of the system. To build the physical components of the system you need to learn about the physics and engineering but to implement complex behaviour of the system you need to learn computing. Basically any system behaviour can be implemented by connecting the parts of the system in a specific way (that's how machines before computing were built) but as the desired behaviour gets complex, the human mind cannot come up with the design using just connecting the part and that's were computing comes into picture.

For example: The VR goggles have a lot of physics and engineering involved but in the end all those components are measuring something aka input OR effecting something aka output and the software on these system is using these IO components and algorithms to derive the behaviour of the system.

---
Tags: software-engineering
---


title: The floor function

text:
# Question
Title: The floor function
How do I prove or disprove the following statements: $$(a) ∀n ∈ \mathbb N, ∃k ∈ \mathbb N, ∀x ∈ \mathbb R , \lfloor nx \rfloor − n \lfloor x \rfloor ≤ k$$ and $$ (b)\exists k \in \mathbb N, \forall n \in \mathbb N, \forall x \in \mathbb R, \lfloor nx \rfloor − n \lfloor x \rfloor ≤ k $$

I've also been given the following three properties to use: $ (i) \forall x \in \mathbb R, \exists \epsilon \in R, 0 ≤ \epsilon \< 1 ∧ x = \lfloor x \rfloor + \epsilon \\ (ii) \forall x \in \mathbb Z, \forall y \in \mathbb R, \lfloor x + y \rfloor = x + \lfloor y \rfloor \\ (iii) \forall x \in \mathbb Z, \lfloor x \rfloor = x $

I know that we must negate the statement$(a)$ first in order to pave the way for a disproof(if it false) by proving: $$ \exists n \in \mathbb N, \forall k \in \mathbb N, \exists x \in \mathbb R, \lfloor nx \rfloor - n \lfloor x \rfloor \> k $$ Other than that I have no idea which property to use and in which order. The help would be really appreciated.

# Answer
> 2 votes
You have been given that $$0\le\epsilon\<1$$ multiplying by $-1$ \begin{equation} \therefore 0\ge-\epsilon\>-1\tag{1} \end{equation} adding $x$ $$\therefore x\ge x-\epsilon\> x-1$$ \begin{equation} \therefore x\ge \lfloor x \rfloor \>x-1\tag{2} \end{equation} We can use this inequality $(2)$ to show that \begin{equation} \therefore nx\ge n\lfloor x\rfloor \> nx - n\tag{3} \end{equation} adding $nx$ to inequality $(1)$ we get $$nx\ge nx-\epsilon \> nx -1$$ \begin{equation} nx\ge \lfloor nx \rfloor \> nx -1 \tag{4} \end{equation} Using $(3)$ and $(4)$ we can write $$nx-1 - nx\<\lfloor nx\rfloor - n \lfloor x\rfloor\<nx - (nx - n)$$ $$\therefore -1\<\lfloor nx\rfloor - n \lfloor x\rfloor\<n $$

# Answer
> 2 votes
The first step is to understand for each $n,k$ the following property holds: $$ P(n,k) \Leftrightarrow \forall x \in \mathbb{R}, \lfloor nx \rfloor - n\lfloor x \rfloor \leq k. $$ If $nx = na + b + \epsilon$, where $a,b \in \mathbb{Z}$, $0 \leq b \< n$, and $0 \leq \epsilon \< 1$, then $$ \lfloor nx \rfloor = na + b, \quad n\lfloor x \rfloor = na \quad \Longrightarrow \quad \lfloor nx \rfloor - n \lfloor x \rfloor = b. $$ This means that $$\\{\lfloor nx \rfloor - n \lfloor x \rfloor : x \in \mathbb{R}\\} = \\{0,1,\ldots,n-1\\}.$$ In particular, $$ P(n,k) \Leftrightarrow k \geq n-1. $$ Your two statements are thus equivalent to $$ \forall n \in \mathbb{N} \exists k \in \mathbb{N}, k \geq n-1, \\ \exists n \in \mathbb{N} \forall k \in \mathbb{N}, k \geq n-1. $$ You take it from here.

---
Tags: proof-techniques
---


title: Is $(a+b)^*$ closed under reversal?

text:
# Question
Title: Is $(a+b)^*$ closed under reversal?
If you have a language $L\_1 = \\{ w | w \in \\{a,b\\}^\* \\}$. Then does the language $L\_1^R$ (the reversal of $L\_1$) have the exact same elements as the language $L\_1$?

My Logic: Since $L\_1$ can contain a string as well as the reversal of the string (ex. $L\_1 = \\{ababba, abbaba\\}$), then $L\_1^R$, over the same alphabet, can contain the same strings as what $L\_1$ has (ex. $L\_1^R = \\{abbaba, ababba\\}$ which is equivalent to $L\_1$)?

Am I looking at this correctly?

# Answer
If an arbitrary language $L$ is closed under reversal ($L=L^R$), then $L^\*$ is also closed under reversal, since

$$ \begin{array}{ll} L^R &= \\{ w\_1 \ldots w\_n \ |\ \forall i.\ w\_i \in L \\}^R \\ &= \\{ (w\_1 \ldots w\_n)^R \ |\ \forall i.\ w\_i \in L \\} \\ &= \\{ w\_n^R \ldots w\_1^R \ |\ \forall i.\ w\_i \in L \\} \\ &= \\{ x\_1 \ldots x\_n \ |\ \forall i.\ x\_i^R \in L \\} \\ &= \\{ x\_1 \ldots x\_n \ |\ \forall i.\ x\_i \in L^R \\} \\ &= \\{ x\_1 \ldots x\_n \ |\ \forall i.\ x\_i \in L \\} \\ \end{array} $$

So, being $\\{a,b\\}$ trivially closed under reversal (provided $a,b$ are letters, not words), $\\{a,b\\}^\*$ is such.
> 1 votes

# Answer
Going back to saying $L\_1 = \Sigma^\*$ is valid, as $\Sigma^\*$ is trivially closed under reversal.

If you're unsure, and the language is more complicated, you can do more legwork to make verify your claim: Create the minimal DFA for the language $L$, and create the minimal DFA for $REVERSE(L)$. It isn't the most efficient way, but it simplifies comparison. (It also allows to find a counter-example if the language isn't closed under reversal).
> 0 votes

# Answer
Yes, You are looking it the correct way. $L$ will contain all the string possible over alphabet $a$ and $b$ so $\forall w \in L$ there exist $ w^R \in L$
> 0 votes

---
Tags: formal-languages
---


# Question
Title: Regular Expressions. Reversal of concatenated strings verification
What is the significance of reversing string $v$ in the following? Can't the string $v$ contain exactly what is in the string $v^R$, since you are just choosing from the alphabet $\Sigma^\*$? I don't fully comprehend this question.

> Consider the language $$L = \\{uabcv\mid u,v\in\Sigma^\*\\}$$ over the alphabet $\Sigma = \\{a,b,c\\}$. Is it true that reversal of $L$ is the set $$L\_2 = \\{ucba(v^R)\mid u,v\in\Sigma^\*\\}\\,?$$ (Please note that the parentheses are used only to clarify that it is only the string $v$ that is reversed.)

Any help is appreciated.

# Answer
For the first part, $$L=\\{aw|w\in\\{a,b\\}^\*\\}$$ and $$L\_R=\\{wa|w\in\\{a,b\\}^\*\\}$$

It is true that $L\_R$ is the reverse of $L$. $L$ represents the set of strings starting with the symbol $a$, and $L\_R$ represents the set of strings ending with the symbol $a$. Note that for some $w$ such that $aw\in L$, you only need to find some $w'$ such that the reverse of $aw$ is $w'a$. You do not need $w=w'$, so your example does not counter the statement.

For every string $w\in\Sigma^\*$, where $\Sigma=\\{a,b\\}$, reversing the characters of $w$ must also belong to$\Sigma^\*$. Thus, every string $aw$ in $L$, there is a string which is its reverse in $L\_R$ and vice-versa.

For the second part, there is no significance in reversing $v$. It might be intentionally a part of the problem statement.
> 1 votes

# Answer
Any string $s\in L$ has this form: $$ s = \underbrace{x\_1\dotsm x\_n}\_ua\\,b\\,c\\,\underbrace{y\_1\dotsm y\_m}\_v $$ where $x\_i, y\_j\in \Sigma$. Its reversal, then, will be $$ s^R = \underbrace{y\_m\dotsm y\_1}c\\,b\\,a\underbrace{x\_n\dotsm x\_1} $$ Since you need this to be of the form $p\\,c\\,b\\,a\\,q^R$ (where I used different variables to lessen any possible confusion), it will suffice to have $$\begin{align} p&=y\_m\dotsm y\_1 = v^R\\ q^R&=x\_n\dotsm x\_1= u^R \end{align}$$
> 0 votes

---
Tags: formal-languages
---


# Question
Title: Can you apply the induction hypothesis to its outcome?
Assume a well-founded relation $\<$ over a set $S$ and a property $P$ on $S$ such that:

1. $P$ holds for all minimal elements of $S$.
2. For every $b \in P$ and $a \< b$ we have: if $P(a)$ then there exists $c \< b$ such that $P(c) \Rightarrow P(b)$.

Question: does it follow that $P(c)$ holds for all $c \in S$?

# Answer
> 3 votes
As stated, the reasoning does not make much sense to me.

You claim that, in your specific case, you have

* $a \< b \wedge P(a) \Longrightarrow \exists c \< b$
* $P(a) \wedge P(b) \Longrightarrow P(b)$

but these properties are trivial tautologies -- they tell nothing about your specific case.

In the first one, if $a \< b$, we already know $\exists c\<b$. We don't even need $P(a)$.

The second one is an instance of the tautology $p \land q \implies q$.

I'm not sure how these two properties help in the induction proof at all.

# Answer
> 2 votes
The answer is positive.

To show that $P$ holds for all $c \in S$, we need to establish, for all $b \in S$: $$(\forall a \< b . P(a)) \Rightarrow P(b).$$ Then we may apply the well-foundedness of $\<$ to $P$.

So consider any $b \in S$ and suppose $\forall a \< b . P(a)$. We need to show that $P(b)$ holds. There are two cases:

1. There is no $a \< b$. In this case $b$ is minimal and so $P(b)$ by the first assumption in the statement of the question.
2. There is some $a \< b$. Then we know that $P(a)$ holds. By the second assumption of the statement of the question there is $c \< b$ such that $P(c) \Rightarrow P(b)$. However, since $c \< b$ we do have $P(c)$ by assumption, and therefore $P(b)$.

QED.

---
Tags: logic, proof-techniques, induction
---


# Question
Title: How would you prove a family of functions is universal?
A set of functions from a universe U of keys to n buckets is universal if for every pair of keys in U, say x and y, such that x != y, the probability of h(x) = h(y) is less than or equal to 1/n, for a random function h in the set of functions.

Say you're given a prime number p, and a random integer n, such that p is greater than or equal to n. Say we want to look at the family of functions where we pick a random integer i, and define each function hi = ((i * x) mod p) mod n. The input can be any integer from 0 to p-1, and the the output can be any integer from 0 to n - 1.

How would you prove that this family of functions is universal. Or similarly, if you pick an arbitrary p and n, how would you come up with a counter example?

# Answer
> 1 votes
A good approach is to simultaneously try to prove it, and try to disprove it.

To try to prove it: look at what the definition says, plug in the definition of the hash function, and see what number-theoretic fact needs to be true. Can you find any proof for this number-theoretic fact?

To try to disprove it: look for a counterexample. When looking for a counterexample, I suggest starting with the smallest parameters you can, to make manual calculations tractable. In this case, you might start with prime $p=3$ and number $n=2$; I think that is the smallest possible parameter setting that meets your requirement. Now, calculate the probabilities explicitly and see if it meets the definition. (The numbers are so small you should be able to calculate that explicitly by just enumerating all cases.) What do you get?

If you try this, I think you'll be able to answer your own question. If you're still stuck, edit the question to show what you tried along each of these two directions and where you got stuck.

---
Tags: proof-techniques, probability-theory, hash, hashing
---


# Question
Title: Is this grammar right associative (why?)
Given a grammar as follows:

$\left\<stmt\right\> \rightarrow \left\<id\right\> = \left\<expr\right\>$

$\left\<const\right\> \rightarrow A | B$

$\left\<expr\right\> \rightarrow \left\<term\right\> \times \left\<expr\right\> | \left\<term\right\>$

$\left\<term\right\> \rightarrow \left\<factor\right\> + \left\<term\right\> | \left\<factor\right\>$

$\left\<factor\right\> \rightarrow (\left\<expr\right\>) | \left\<id\right\>$

I think this grammar is right associative because it expands on the right. Where I am confused is it can be expanded using other non-terminals on the left. For example,

$\left\<expr\right\> \rightarrow \left\<term\right\> \times \left\<expr\right\> | \left\<term\right\>$

Could be expanded via $\left\<term\right\>$ on the left, I think. Does this make the associativity ambiguous? Assuming it could be ambiguous, how would I fix this to make the grammar completely right associative?

# Answer
$\left\<expr\right\> \to \left\<term\right\>×\left\<expr\right\> | \left\<term\right\>$

could certainly expand $\left\<term\right\>$. But the operator in that expansion (if there is one) is certainly not $×$; it would have to be $+$. So associativity doesn't apply, since associativity is only about expressions involving two of the same operator.

So yes, in both operator productions in that grammar, the operator is right-associative.
> 2 votes

---
Tags: formal-grammars, programming-languages
---


# Question
Title: How do we adjust a model to fit our own dataset?
Often, I see people using networks like AlexNet, GoogLeNet, etc to train it on their dataset. These networks are trained or pretrained with a specific dataset, and people fine-tune it to their dataset.

However, is this really suitable? What if the custom dataset had a lot more images than the original or is detecting completely different classes?

In which ways could we modify the networks so they would fit our dataset better?

\*one example is faster-rcnn, where lots of people have done this

# Answer
> Is this really suitable?

Well, it works. At least, in some situations. And in machine learning, there's a sense in which that is the bottom line: is it useful? And yes, this approach does appear to be useful, in at least some situations.

Beyond that, I'm not sure what you mean by "suitable".

> What if the custom dataset had a lot more images than the original or is detecting completely different classes?

Sure. There will cases where fine-tuning probably isn't what I'd recommend you try first. Look at it this way. Fine-tuning is one thing you can try. It's not a silver bullet. It may work well in some situations. No one is claiming it will work well in all situations. There are plenty of situations where it might work poorly.

Fine-tuning is probably most useful if your training set is small (or, at least, not very large), and if there is a pre-trained network that solves a task that is somehow similar to the task you're trying to solve. The classes don't have to be identical -- for instance, if you are solving some kind of object detection task, but your classes aren't identical to ImageNet, then starting with a pre-trained network that was trained on ImageNet can still be useful, as the image features learned for ImageNet are likely to be useful for other object detection tasks as well -- but the task probably needs to be somehow similar.

If your training set is very large, then fine-tuning might not be the best answer. You might do better to train a network from scratch, yourself.

---

Finally: Machine learning is ultimately a pragmatic field. Don't try to look for the one right answer that works in all situations, and don't expect there to be some theory that can predict what the most effective approach to your problem will be. Instead, understand that it's a bit of an art; trial and error is often needed; and the ultimate metric is whether it works well enough for the particular problem you are facing right now.
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Linear time algorithm to sort points of a simple polygon
In triangulating a simple polygon, using the concept of sweep line helper vertices etc, the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$ (where $n$ is the number of vertices). I'm trying to work out why... Assume there's no degenerate case (for any pair of points belonging to the polygon their $y$ coordinates are different). Because of such property a strict order exists $y\_1\<y\_2\<\ldots\<y\_n$, assume each point is stored in floating point $y\_i = (e\_i,m\_i)$, I can't really see how to sort these points in linear time... could anyone give me an hint?

Source : Computational Geometry - Algorithm and application (DeBerg et all) chapter 3:

The claim is this

> We now analyze the running time of the algorithm. Constructing the priority queue $\mathcal{Q}$ takes linear time...

Any kind of priority involves order relationships, so I assume some kind of ordering algorithm is used. Eventually the priority queue can be implemented using binary trees or heaps (basically these are the same thing) but It would still require $O(n \log n)$. I know ordering algorithms that run in linear time, however I don't think any of those can be applied in case of floating point numbers.

# Answer
> 2 votes
You ask:

> the very first step is sorting the vertices of such polygon. Apparently this very step can be done in $O(n)$

but the book says

> We now analyze the running time of the algorithm. Constructing the priority queue QQ takes linear time...

Constructing a priority queue does not take as much time as sorting. Priority queues can be constructed in linear time. The most famous algorithm for doing this is called "heapify".

---
Tags: time-complexity, computational-geometry, sorting
---


# Question
Title: Substring in a infinite sequence of numbers
I have an infinite sequence of numbers, starting from 1 and need to find position of begin of some given substring of numbers.

Example:

12345678910111213**141**51617181920 ...

S = 141

Result: 18

All i think about is convert sequence to string and find substring using Rabin-Karp or KMP. But i feel that i can use it as numbers and there is some O(1) solution using math.

Another thought is split S on pieces:

141 = \[(1, 4, 1), (1, 41), (14, 1), (141)\]

And i have (1-9)(10-99)(100-999)(1000-9999)... which represents infinite sequence.

Than i can use this algo:

For (1, 41): try to find 1 from (1-9) and what goes next, if 41 is not next number, than try next tuple.

For (14, 1): try to find 14 from (10-99) and and what goes next, if 1 than find position of '14'.

But i'm not sure that this is correct solution. Maybe some advices?

# Answer
> 2 votes
Your algorithm is not correct. Consider 21:

21 = \[(2, 1), (21)\]

First we find 2 in (1-9): 1**2**3456789. However, a 3 follows, so it's not a solution.

Then we try to find 21 in (10-99). This finds a solution, but it's 21. However there is an earlier solution:

12345678910111**21**31415161718192021

So the solution is not correct.

The sequence you're after is A229186, but no simple formula is posted there.

# Answer
> 1 votes
I don't think an $\mathcal{O}(1)$ solution can be possible, since if nothing else, you need to examine all digits of your input. But if *n* is the number of digits in your input (such that the numerical value of your input is between $10^{n-1}$ and $10^n$), there's definitely a polynomial-time solution in *n*, whereas the substring–based approaches (that don't take into account the structure of the sequence) are necessarily $\Omega\left(10^n\right)$.

One approach:

* First, test the possibility that the last digit of your input corresponds to a single-digit number in the infinite sequence. (For example, $234$ passes this test: the $4$ is the sequence's $4$.) If so, you're done.
* Next, test the possibilities that the last digit of your input corresponds to:

+ the first digit of a two-digit number in the infinite sequence. (For example, $121$ passes this test: the second $1$ is the first digit of the sequence's $13$.)
    + the second (last) digit of a two-digit number in the infinite sequence. (For example, $112$ passes this test: the $12$ is the sequence's $12$.)

If either of these checks out, then you're done. (If *both* check out, then choose the one that gives you an earlier index.)
* Next, test the possibilities that the last digit of your input corresponds to the *first*, the *second*, or the *third* digit of a three-digit number in the infinite sequence.
* . . . and so on until you have a result. (It's guaranteed that you'll have results once you get to the possibilities where the last digit of the input corresponds to a digit of an *n*-digit number in the infinite sequence; so your algorithm will terminate there, if not before.)

Overall, you have to test at most $\Theta\left(n^2\right)$ possibilities. I haven't described exactly how you actually perform each test, but you should be able to do so in $\Theta\left(n\right)$ time, and you should be able to compare two successful possibilities in $\Theta\left(1\right)$ time to decide which one comes earlier in the sequence. You'll also need to translate the final result from something like "ends on the second digit of the sequence's $234$" to something like "starts at position 587"; but you can certainly do that in $\mathcal{O}\left(n^2\right)$ time (and probably $\Theta\left(n\right)$ time), so your total complexity should be worst-case $\Theta\left(n^2\right)$.

# Answer
> 0 votes
This would be an excellent place for a state machine. Create a state machine with states from S. You should have a state for "I haven't matched anything", one for "I've matched the first character," one for "I've matched the first two characters" and so on. In your example, we would have 4 states { "", "1", "14", "141" }. The final state is terminating. If you mach the whole string (141), then you have found your first match in the infinite string.

Now you can build your state transition diagram. The key to building this is that you can fail to match the next character, but not have to start over at the beginning. 141 is a bad example, but consider 444441. If I were to be matching "132444444..." I clearly start matching 444441 at the obvious point, but when I see a "4" when I wanted to see a "1", I shouldn't start over. I've still got a match of several 4's in a row. Maybe the next character will be a 1!

We can write up a transition diagram. In this case, I'll notate it with the current state on the left, a colon, and then a set of transitions on the right side of the colon. The inputs will be unquoted digits, and the new states will be quoted strings. In your simple example, 141, the transition diagram is:

```
"":   1 -> "1"           other -> ""
"1":  4 -> "14"  1-> "1" other -> ""
"14": 1 -> "141"         other -> ""
"141" terminates

```

This clearly can process each additional character of the string in O(1) time.

In a more complicated example, such as S = "5451" we need to take into account the possibility of a partial match. Otherwise, the process is the same

```
"":    5 -> "5"                     other -> ""
"5":   4 -> "54"  5-> "5"           other -> ""
"54":  5 -> "545"                   other -> ""
"545": 1 -> "5451" 4-> "54" 5-> "5" other -> ""
"5451" terminates

```

Note that on "545", there are many possible transitions which capture the fact that there were partial matches.

If you are interested in prior art KMP is a good algorithm to explore. There are also more exotic sub-linear ones which can actually skip characters entirely (as long as there's a way to go back and visit those characters if a potential match shows up).

# Answer
> -1 votes
Consider the number you want to search

eg 141 , see the digit in number lesser than or equal to the first digit

\[ Intuition: If less maybe , we can bring it to the front, If equal maybe the rest is the next number in the series\]

Following this:

See 141 , 1 in the third place is equal to the first digit.

So here we go position of 14 (with a check that 15 comes after 14, Maybe its like (191, where 19+1 = 20 in which case we are wrong )

Another example

21 , 1 is lesser than 2 , so 12 13 and we are done.

Another one 1254

Since no number is greater than or equal to 1 , answer is 1254

Another one 5421

1 is the least so 1542 1543

Another one 191

1 is least so, 19+1 = 20 (No!!) So answer is 191.

1911

Here we see we can solve by , 19 11 , take to front 11 **19 11** 20.

Or let the last one stay (tie as 1), so **191 1**92. So the answer is 191

In this case your algorithm will be max O(size of pattern) , instead of O(size of text) as in kmp, assuming you can calculate index in O(1) by a formula.

Code this up and you are done :)

---
Tags: algorithms, strings, exact-string-matching
---


# Question
Title: Given a list of students and their courses, place them in specific classes
I could use some help coming up with the best way to solve this problem. I've been curious as to how something like this would work, as the worst case seems way too bad.

## Problem

Given a group of students and the courses they are enrolled in, and a schedule with 8 class blocks in it, how could you place them in specific classes?

Keeping in mind you can have as many classes for a specific course as long as there is a teacher who is free to teach the class.

## Specifics

There are 8 class "slots" where you can put any class, but a teacher can not teach two classes at once.

## Inputs and outputs

The input is a list of students each with data on which courses they are taking. There is not specific data structure I have in mind, the problem is more theoretical than literal.

The output would be assigning a value 1-8 to each class, specifying when they would take it.

# Answer
At first glance, the stable matching problem's solution is discussed in the following pdf. https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pdf/01StableMatching.pdf

It would be hard to cast the course assignment problem as stable matching because he fact that the courses have a finite capacity

However, the following pdf states that, http://dss.in.tum.de/files/bichler-research/2014\_diebold\_matching\_course\_allocation.pdf

> The allocation of students to courses is a wide-spread and repeated task in higher education, often accomplished by a simple first-come first-served (FCFS) procedure. FCFS is neither stable nor strategy-proof, however. The Nobel Prize in Economic Sciences was awarded to Al Roth and Lloyd Shapley for their work on the theory of stable allocations. This theory was influential in many areas, but found surprisingly little application in course allocation as of yet. In this paper, we survey different approaches for course allocation with a focus on appropriate stable matching mechanisms. We will discuss two such mechanisms in more detail, the Gale-Shapley student optimal stable mechanism (SOSM) and the efficiency adjusted deferred acceptance mechanism (EADAM). EADAM can be seen as a fundamental recent contribution which recovers efficiency losses from SOSM at the expense of strategy-proofness. In addition to these two important mechanisms, we provide a survey of recent extensions with respect to the assignment of schedules of courses rather than individual courses. We complement the survey of the theoretical literature with results of a field experiment, which help understand the benefits of stable matching mechanisms in course allocation applications.
> -1 votes

---
Tags: algorithms, assignment-problem
---


# Question
Title: Is knapsack a Linear Programming problem?
Since Knapsack give Optimal solution as LP so is it also a LP or not ?

# Answer
The knapsack problem can be modelled as a mixed integer program (MIP) and the linear-programming relaxation of this model can be solved. The linear relaxation does not give a solution to the problem, but it will provide an upper bound to the solution of the knapsack problem (equivalent to a solution of the MIP) which helps the MIP solver in its quest to find the optimal integer solution.
> 2 votes

---
Tags: algorithms, linear-programming, knapsack-problems
---


# Question
Title: Determining asymptotic running time by profiling
> The purpose of performance proﬁling is to measure program performance. One part of your PA1 assignment asked to measure performance of your d-smooth algorithm to verify if the running time of the program corresponds to the desired $O(n \log n)$. Assume that you have performed an experimental analysis of an algorithm, and proﬁling returned the following times: for instances of sizes $2^{10}, 2^{11}, 2^{12}, 2^{13}, 2^{14}$ the corresponding times are approximately 300, 500, 1100, 2900, 8300 milliseconds. There is an extra overhead resulting from clocking program performance and functions calls, and this overhead has to be considered in analyzing data. That is, the measured time consists of two components: the time for executing the operations, plus the overhead from proﬁling. The estimated overhead due to proﬁling is about 200 milliseconds independently of the input size. (that is, 200 is always an additive “constant”). Based on these experimental results, what is the running time for executing operations in this algorithm? ($c$ is a constant) In particular, is your implementation running in $O(n \log n)$?
>
> 1. $c \log n$
> 2. $c n$
> 3. $c n \log n$
> 4. $c n\sqrt{n}$ \<----- Correct answer
> 5. $c n^2$

(editor's note: I changed 81200 to 8300; the setters added 200 to 81000 instead of to 8100)

Why is $c n\sqrt n$ the correct answer?

# Answer
If you remove the 200ms overhead, you get $$ \begin{array}{c|ccccc} n & 2^{10} & 2^{11} & 2^{12} & 2^{13} & 2^{14} \\ t & 100 & 300 & 900 & 2700 & 8100 \end{array} $$ This shows that when $n = 2^{10+k}$, $t = 100 \cdot 3^k$. You take it from here. (You won't get $cn^{3/2}$, by the way! The setters made a mistake.)
> 0 votes

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


# Question
Title: Prove that there exists an undecidable complementary language
Some language A ⊆ Σ∗ is called complementary if A ≤m complement of A. How can I show that there exists an undecidable complementary language?

# Answer
> 2 votes
Take $\Sigma=\\{0,1\\}$ for simplicity.

Define $A \oplus B = 0A + 1B$. We have that $(A \oplus B)^c \equiv\_m A^c \oplus B^c$ since they differ only by the empty string.

We now take any non recursive $A$, and consider $B = A \oplus A^c$. We have $A \leq\_m B$, so $B$ is not recursive as well. Further, $B = A \oplus A^c \equiv\_m (A^c \oplus A)^c \equiv\_m (A \oplus A^c)^c = B^c$.

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


# Question
Title: algorithm to delete nodes that completely removes connectivity
This is a distributed systems problem, but perhaps the graph theory gurus can help me.

I need an algorithm that that tells me which nodes to remove from the graph to completely remove connectivity.

See example:

The most intelligently thing to do would be to remove the bcasts nodes:

Can you help me? One way to solve this would using a SAT or ILP solver, but I want to if there are any other algorithms for this kind of task.

# Answer
Your problem is: given a graph, find a minimum-sized set of vertices whose removal disconnects the graph.

This is the "minimum vertex cut" problem. There are standard algorithms for this, based on network flow and the max-flow-min-cut theorem. You need to modify the graph slightly to make two copies of nodes, then apply network flow (network flow on the original graph finds a minimum edge cut; you want a minimum vertex cut). See https://en.wikipedia.org/wiki/Vertex\_separator, https://en.wikipedia.org/wiki/Cut\_(graph\_theory), https://cstheory.stackexchange.com/q/2877/5038.
> 2 votes

---
Tags: graphs
---


# Question
Title: How can I compare two recurrence relation to find which one is better on large inputs
I have two recurrences:

$T\_1(n) = 2 T\_1(n-1) + n$ if $n \> 1$, $1$ if $n = 1$

$T\_2(n) = 2 T\_2(\frac{n}{2}) + n^2$ if $n \> 1$, $2$ if $n = 1$

Does this mean $T\_1$ is better than $T\_2$ because it has less operations to do?

Edit: I looked at the master theorem and found out that the 2nd one has an $O(n^2)$ runtime.

# Answer
The simplest way is to solve both recurrence relations, and see whether one of them grows faster. In your case there is actually no need to do that, since we can observe that on the one hand $$ T\_1(n) \geq 2T\_1(n-1) \geq 2^2T\_1(n-2) \geq \cdots \geq 2^{n-1}T(1) = 2^{n-1}, $$ and on the other hand $$ T\_2(n) = O(n^2), $$ by the master theorem. This is enough to deduce that $T\_2(n) = o(T\_1(n))$, that is, $T\_1(n)$ grows faster than $T\_2(n)$.
> 3 votes

# Answer
I think before you use tools like the master theorem, you should be training your intuition a little bit. In the first case, $T\_1(n)$ is twice $T\_1(n-1)$, plus a bit more. So as you calculate $T\_1(1)$, $T\_1(2)$, $T\_1(3)$, and so on, each time the value is more than doubled. If you take $T\_1(1000)$, that is more than $T\_1(1)$ doubled 999 times, more than $2^{999}$.

Basically, anything that takes previous values only a fixed distance apart, and at least multiplies by a constant \> 1, you have exponential growth.

In the second case, it's $T\_2(2)$, $T\_2(4)$, $T\_2(8)$, $T\_2(16)$ and so on where $T\_2$ doubles. You have to double n to double $T\_2(n)$. That by itself is just linear. You add $n^2$, so you get at least $O (n^2)$, but probably not much more. If doubling n more than doubles n, then you may have more growth. Try to find a formula yourself for the case $T(n) = 3T(n/2)$ - it's n raised to some power, so find which one.

Basically, if multiplying n by one constant \> 1 multiplies T(n) by another constant \> 1, you get polynomial growth - depending on the constants.
> 1 votes

---
Tags: complexity-theory, asymptotics, recurrence-relation
---


# Question
Title: Is there a generic word for "thread or process"?
I'm writing about a problem that could be caused by race conditions between multiple threads, or OS-level processes on the same machine or different machines, or VM-level processes like the Erlang VM has.

In this context, the fact of parallel execution is the important part; the language or memory-sharing model is irrelevant.

**Is there a generic word that means "thread or process"?** "Concurrent unit of execution" is the best attempt I have so far, but it sounds awkward to me.

# Answer
> 6 votes
A process is a context with one or more threads of execution (concurrent with other threads of execution, either in the same process, or perhaps in other processes), *and* with its own address space (and usually other resources such as open file descriptors, IPC mechanisms, etc.). More subtle details and implications are described here

So, if address space (and other such resources) isn't relevant to your discussion (and it's probably not given your description), then I would say that the word **thread** is sufficient to describe the entities involved in your discussion. Historically **task** has also been used to describe a thread, and indeed it was perhaps the first word used to describe this concept (see this).

(Note of course there's a difference between concurrent threads and parallel threads -- concurrent threads may be executed in parallel, but it is not necessary for operations to occur in parallel for them to suffer from the issues related to concurrency.)

---
Tags: terminology, process-scheduling, threads
---


# Question
Title: For AVL trees, how do we know if a RL or a LR rotation is needed?
Suppose I am trying to construct a simple AVL tree:

Upon inserting 'B' the tree becomes imbalanced. How do I exactly know that I need a LR or RL rotation without making any guesses?

From what I heard is that if you insert at right side of tree and it becomes imbalanced then you need a LR rotation and vice-versa. I want to make sure that it is true.

# Answer
> 3 votes
In this case the tree is right-left unbalanced. That's because when you insert $B$ it causes the root node to become unbalanced. You can tell its right-left unbalanced from the path that goes from the newly inserted node to the root node i.e. $B$ is the *right* child of $A$ and $A$ is the *left* child of $C$. Therefore, it needs a left-right rotation.

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


# Question
Title: DP Knapsack Problem With Categorical Constraint
so I'm working on a variation of the knapsack problem which includes a constraint on the number of each item from each category in addition to a weight. For instance, we have a number of books each given a genre (1 of 3 genres), and our goal is to maximize the total weight as well as include at least G books from each genre.

The recursion is found below, but when trying to convert this to a DP solution I'm having some issue. Note that the problem specifically deals with books, their categories, and maximizing an enjoyment factor up to some k. It's identical to the knapsack problem beyond the fact that the items are categorized and we need at least N items from each category.

```
private double S2(int W, int k, List<Book> books, int F, int SC, int C) {
    if(W == 0 || k == -1) {
        if(F <= 0 && SC <= 0 && C <= 0) {
            return 0.0;
        } else {
            return Double.NEGATIVE_INFINITY;
        }
    }

    Book b = books.get(k);
    int w = b.getWeight();
    if(W-w >= 0) {
        int newF = F;
        int newSC = SC;
        int newC = C;
        if(b.getGenre() == Book.Genre.FANTASY) {
            newF = F-1;
        }
        if(b.getGenre() == Book.Genre.SCIENCE_FICTION) {
            newSC = SC-1;
        }
        if(b.getGenre() == Book.Genre.CLASSICS) {
            newC = C-1;
        }
        return Math.max(b.enjoyment+S2(W-w, k-1, books, newF, newSC, newC), S2(W, k-1, books, F, SC, C));
    } else {
        return S2(W, k-1, books, F, SC, C);
    }
}

```

My DP solution involves a 5 dimensional array for W, k, F, SC, C and I'm just traversing it in 5 dimensions and filling in each value based on the recursion but it's way too slow--in fact, slower than the recursion for small n (even though it should run in polynomial time as opposed to exponential time). Is there some quicker way to traverse the subproblems in the DP solution, in some specific order?

I'm basically doing "tabular memoization" in 3 extra dimensions for the original Knapsack problem with only 1 constraint. Is my recursion wrong? Or is this to be expected?

# Answer
> 2 votes
An alternative approach you could try: solve a knapsack problem for each category separately, then combine those solutions.

You'll probably find it more rewarding to work out how to do that on your own, but if you want a more detailed hint:

> For each category and each total weight $w$ and each integer $t$, compute the maximum enjoyment you can have by using at most $t$ books from that category and where the total weight is at most $w$.
>
> For instance, for each $w,t$, you'll compute the maximum enjoyment you can have by selecting at most $t$ fantasy books (and no science fiction or classic books) of weight at most $w$. Then do the same for science fiction, and the same for classic books.
>
> Then, combine these three results. I'll let you work out how to combine them.

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


# Question
Title: Why do people insist to use the term "multilayer perceptron" instead of "multilayer perceptron network"?
The **perceptron** model describes a **linear classifier**. Often people use the term "*multilayer perceptron*" to describe a feedforward neural network that uses perceptrons. This terminology simply sounds wrong to me, since this type of network does not necessarily behave like a perceptron; that is to say - it may act as a **nonlinear classifier**, which is clearly not a perceptron; it is not a single perceptron containing multiple layers, but a multilayer network containing perceptrons.

Wouldn't it be proper to use the term "*multilayer perceptron network*" to describe this type of network instead? I can't seem to find a reliable reference that discusses this issue, but there is a section about it in the corresponding Wikipedia article.

# Answer
Personally, I've seen "multilayer neural network" used more commonly than "multilayer perceptron". If you like the former term better, use it.

That said: multilayer perceptron is an accepted term of art. Your criticism is not unreasonable, but it is what it is. Language exists to help us communicate... so pick terms that will help you communicate your intended meaning to your intended audience as effectively as possible.

If it helps you come to some kind of acceptance for this usage, you can think of "multilayer perceptron" as a single term that has a particular definition: don't think of "multilayer" as an adjective modifying "perceptron", but thik of "multilayer perceptron" is a single atomic phrase that has a particular definition. For example, some mathematics textbooks define the term "ring" in a way such that a "commutative ring" is not actually a "ring"; that's just how it is, so just go with it and don't let it throw you. As another example, an "algebraic integer" is not an "integer"; it's a complex number with some special properties. This kind of situation appears all over the place in mathematics.

Ultimately, it's just a convention. And that's ultimately what language boils down to: a convention. These conventions sometimes can look a bit inconsistent or "improper", but if they are widely understood, then they still serve the ultimate goal, of clear and concise communication among folks who are knowledgeable in the field.

Bottom line: don't let a sense of what is "proper" overcome the real goal. Keep in mind the real purpose of these kinds of terms: namely, effective and efficient communication.
> 4 votes

---
Tags: terminology, neural-networks, perceptron
---


# Question
Title: Which language is accepted by this Muller Automaton?
In my opinon the Language recognised is this:

$(a + b)^\* (ab)^ω$ but the solution provided is: $(a + b)^\* (a + b)^ω$

Did I missunderstand the acceptance condition or is the solution wrong?

My reasoning is:
As far as I understood a Muller Automaton does accept a run if all the set of all infinitely often visited states can be found as acceptance condition.
E.g. if a run visits inf. often the states p & r and finitely often q then the set { p , r } has to be one of the set's of the acceptance condition.

I think in this case, that a word has to bounce inf. often between 2 of the 3 states (but is not allowed to visit the 3rd state inf. often). That means that in the end the word has to alternate between a & b inf. often after doing finitely often whatever it want's to do
=\> $(a + b)^\*$ ( = "do what ever you want to do finitly often and in the end") $(ab)^ω$ (= "iterate between a and b")

The given solution differs from my solution by accepting e.g. the following word: $aba^ω$

# Answer
> 2 votes
The solution given is incorrect.

The first clue that this might be the case is that $(a+b)^\*(a+b)^\omega$ is a strange way to write anything: any finite number of $a$s and/or $b$s, followed by infinitely many $a$s and/or $b$s is just infinitely many $a$s and/or $b$s, so the given language is just a strange way of writing $(a+b)^\omega$.

Muller automata accept if the set of states visited infinitely often is one of the specified sets. To see that the automaton doesn't accept $(a+b)^\omega$, consider the word $a^\omega$. This is a member of $(a+b)^\omega$ but it's not accepted by the automaton, since the run on that word visits every state infinitely often, and $\\{p,q,r\\}$ is not an accepting set.

If exactly two of the automaton's states are visited infinitely often, then there must be a point at which the third state is never visited again. From that point onwards, the automaton can only alternate between the remaining two states, so any accepted word must end $(ab)^\omega$. While the automaton is still visiting all three states, it can read in any word so, yes, the accepted language is $(a+b)(ab)^\omega$.

---
Tags: automata, regular-expressions, buchi-automata
---


# Question
Title: A basic question about recursive computation
I was going through the following paper: http://www-formal.stanford.edu/jmc/recursive.pdf

In the last part of the second section (at the end of page 7) he speaks about the inadequacy of lambda notion for naming functions described recursively.

The right hand side of the following expression $$\text{sqrt} = \lambda((a,x,\epsilon),(|x^2 -a|\<\epsilon \to x,T \to\text{sqrt}(a,\frac{1}{2}(x+\frac{a}{x}),\epsilon)))$$ cannot serve as an expression of function because there would be nothing to indicate that the reference to $\text{sqrt}$ within the expression stood for the expression as a whole. I did not get what it meant. Why should there be a further indication that the expression stood for whole? Please explain this point.

# Answer
> 3 votes
In pure untyped lambda calculus functions are anonymous. Generally, when you want to define a function recursively, you can simply have it "call" itself, for example:

> if $n=0$ then $f(n) = 1$
>
> if $n\>0$ then $f(n) = nf(n-1)$.

In lambda calculus we don't have the same luxury, functions don't even have "names" in the first place, they are defined in terms of variable binding and variable substitution.

Still, there is a way to implement recursion, discovered by Haskell Curry, by using a particular lambda-term, called *fixed-point combinator* (if you are interested in details, any reasonable source on lambda calculus covers this aspect).

With the new notation, the authors are effectively introducing a mechanism to give names to functions, removing the problem entirely.

# Answer
> 2 votes
If you view the $\text{sqrt} = \dots$ as meaning a syntactic abbreviation, that is, every place you see $\text{sqrt}$ you can replace it with the right hand side, then a "recursive" syntactic abbreviation doesn't make sense since it would expand into an infinitely large expression. $\text{sqrt}$ isn't a term in the lambda calculus, and so it doesn't make sense to even begin talking about "evaluating" ($\beta$-reducing) until we expand it (and all other syntactic abbreviations) fully. In other words, expanding syntactic abbreviations is a "preprocessing" step.

Now, since lambda calculus talks in terms of anonymous functions, there is no way to refer to a containing lambda term from a term within it and so there is no direct way of even writing down a recursive function. However, as I would've expected McCarthy to know, there *is* a way to handle recursion in the *untyped* lambda calculus, which is more or less the system he's describing (omitting $\text{label}$). This is the (now) well-known fixed-point combinator or $Y$ combinator. So McCarthy is mistaken (or at best unclear) when he talks about the inadequacy of lambda notation for recursive functions. On the other hand, in most *typed* lambda calculi the $Y$ combinator is either ill-typed or inexpressible. In those cases, a fixed point combinator needs to be added as a primitive or a mechanism akin to McCarthy's $\text{label}$ needs to be added. This is usually in the form of recursive `let` expressions.

---
Tags: lambda-calculus
---


# Question
Title: Deciding whether the language of a CFG equals some specific regular language
I was wandering if $L = \\{\langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = A \\}$ is decidable where A is a some regular language. Is $L' = \\{ \langle G \rangle \mid \ G \text{ is a context free grammar and } \mathcal L(G) = \overline A \\}$ decidable ? I feel like $L'$ should be decidable, but can't see how. Or does it depends on $A$?

# Answer
> 4 votes
It depends on your choice of $A$. For example, the problem $\\{\langle G \rangle \mid L(G) = \Sigma^\* \\}$ is undecidable, while $\\{\langle G \rangle \mid L(G) = \phi \\}$ is decidable.

Also, the two languages that you have given (the one with $A$ and the other with $\overline{A}$) are equivalent since regular languages are closed under complementation.

---
Tags: undecidability
---


title: Language to regular expression

text:
# Question
Title: Language to regular expression
Having difficulty grasping the concept of how a language and a regular expression are related. For example:

(In all cases, the alphabet is $\\{0,1\\}$)

The language $L = \\{100,10,011\\}$ ------\> Regular expression.

So far, I have:

$(0+1)$ since you can have either $0$ or $1$ in the first part...but...I'm not sure what would follow after that...I've tried making a DFA for it but I feel like I'm overcomplicating it. Any help would be great since I'm fairly confused. Thanks!

# Answer
If the language is finite like you have given in the question then regular expression is simple just write all string separated by $+$(union). So $$r = 100 + 10 + 011$$ further you have something common in first two string so $$r= 10(0+\epsilon) + 011$$

> I feel like I'm overcomplicating it.

For that You need to learn three operators $\*$ , $+$ and $.$ properly & understand the language given then It will be easy for you to make a regular expression without making a D.F.A..
> 0 votes

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


# Question
Title: Show that the class of regular languages is closed under shuffle
For languages A and B, let the shufﬂe of A and B be the language
$ \\{w| w = a\_1b\_1···a\_kb\_k,$ where $a\_1···a\_k ∈ A$ and $b\_1···b\_k ∈ B,$ each$ a\_i,b\_i ∈ Σ^∗\\}$.
Show that the class of regular languages is closed under shufﬂe.

Approach: If A and B are regular, then there exists an NFA R and T that recognizes them. I was thinking I could run R and T in parallel, so I would start running R by processing $a\_1$ and then by using non-determinism, I would jump to the NFA T to process $b\_1$. In this process I make sure that both NFAs aren't executed the original way because that would result in accepted strings that are not in the language, so I try to disconnect the edges in each NFA to jump to the other NFA and then disconnect again the edges of this NFA to come back to the previos NFA.. Is this process clear?

Here is the proof, but some lines are a bit unclear to me.

I can't understand d)i. I don't understand how the transition function works. How does it detect whether we are at DFA A OR B?

# Answer
Suppose, we have a simple string like $w = a\_1b\_1$ then what I understand you want to do is process $a\_1$ in $D\_A$ then jump to initial state of $D\_B$ using $\epsilon$-transition and the process $b\_1$ in $D\_B$ but **we don't know where $a\_1$ ends and $b\_1$ starts.** So using non determinism we check all possibilities of where $a\_i$ can end and $b\_i$ can start.

* To do that we start with a combined starting state $(q\_A,q\_B)$.
* We have all the states possible by making $Q = Q\_A \times Q\_B$
* Now we two kind of transitions from any state from $Q$ first we make transition in $D\_A$ ignoring the transition in $D\_B$ that way we can handle the case where the symbol is part of $a\_i$. In a similar way we will add second kind of transitions assuming symbol is part of $b\_i$.

Going this way there won't be any possibility left unchecked.

> How does it detect whether we are at DFA A OR B?

we don't have a marker between $a\_i$ and $b\_i$ so we make 2 guess at every state. First, The symbol is part of $a\_i$ or $b\_i$ we are currently in and second, that the current symbol is first symbol of the next $b\_i$ if we currently checking $a\_i$ and next $a\_{i+1}$ if currently checking $b\_i$
> 3 votes

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


title: Operations on asymptotic notations

text:
# Question
Title: Operations on asymptotic notations
How to use algebra in operations that involve asymptotic notation? Like for example:

* $C\_1(n)= O(n)$
* $C\_2(n) = O(n^2)$
* Is $C\_2(n)/C\_1(n) = O(n)$?

# Answer
> 1 votes
## Yes and no.

A function $f(n)$ is said to be $O(g(n))$ if there exists a constant $c$ such that

$$ \lim\_{n\rightarrow \infty}\dfrac{f(n)}{g(n)} \leq c $$

Knowing this, a few things immediately become apparent:

* Addition and subtraction *preserves* the largest $O$ of the result, thanks to the properties of limits.

For instance, $f(n) \pm h(n)$ are $O(g(n))$ if *both* $f$ and $h$ are individually $O(g(n))$.

This is why you can say, if two operations are $O(n)$, then the resulting sum/subtraction is also $O(n)$.

If either $f$ or $h$ were $O(n^{2})$, then the result would be $O(n^{2})$. This is in agreement with intuition.
* A function that is $O(n)$ is *also* $O(n^{2}), O(n^{3})$, etc. as you can prove by this definition.

For practical purposes, that is immaterial, as you only usually care about the *smallest* upper bound.
* Multiplication *can* be simplified in the manner you require.

For instance, say I have $f, h$ that are both $O(n)$. This means

$$ \lim\_{n \rightarrow \infty}\dfrac{f(n)}{n} \< c\\;\\;\mathrm{and} \\; \\; \lim\_{n \rightarrow \infty}\dfrac{h(n)}{n} \< c $$

or, equivalently,

$$ \lim\_{n \rightarrow \infty} f(n) \< \lim\_{n\rightarrow \infty} cn\\;\\;\mathrm{and} \\; \\; \lim\_{n \rightarrow \infty}h(n) \< \lim\_{n\rightarrow \infty} cn $$

I can then argue that $f \times h$ is $O(n^{2})$, since, when we go to calculate it, this would require:

$$ \lim\_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} \< c $$

which we can prove like so by substituting the inequalities above:

$$ \lim\_{n\rightarrow \infty}\dfrac{f \times h}{n^{2}} \< \lim\_{n\rightarrow \infty} \dfrac{cn \times cn}{n^{2}} \< c^{2}\\;\\;\mathrm{which\\;is\\;a\\;constant!} $$

In general, the product of two polynomial operations of order $O(n^{k}), O(n^{p})$ is at least $O(n^{k+p})$.
* Division is a bit trickier. Let's take your example: say we have $f, h$ both $O(n)$.

We now try to calculate the limit, using the properties formally stated above, and find:

$$ \lim\_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{n} \< \lim\_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{n} \< lim\_{n \rightarrow \infty} \dfrac{1}{n} = 0 \< c $$

so it *is* $O(n)$.

But wait a minute! It is *also* $O(1)$:

$$ \lim\_{n \rightarrow \infty}\dfrac{\frac{f}{h}}{1} \< \lim\_{n \rightarrow \infty} \dfrac{\frac{cn}{cn}}{1} \< lim\_{n \rightarrow \infty} \dfrac{1}{1} = 1 \< c $$

so the same operation is somehow *both* $O(1)$ and $O(n)$ at the same time.

No, this is not some quantum spookiness at work. Remember that a function that is $O(n^{c})$ is also $O(n^{k})$ if $k \> c$, as we stated above. Correctly speaking, it is not wrong to say either $O(1)$ or $O(n)$ or any other higher power (excluding deities).

In such cases, you may want to use the much stronger $\theta$ definition, which says a function $f$ is $\theta(g(n))$ if $f(n)$ is $O(g(n))$ and $g(n)$ is $O(f(n))$ i.e. they grow at the same pace.

# Answer
> 1 votes
You cannot divide asymptotic notations in this way, since big O is only an *upper* bound. For example, if you take $C\_1(n) = 1$ and $C\_2(n) = n^2$ then $C\_2(n)/C\_1(n)$ is not $O(n)$.

If you're confused, think instead of the following question:

* Given $C\_1(n) \leq n$ and $C\_2(n) \leq n^2$, does $C\_2(n)/C\_1(n) \leq n$ necessarily hold?

Big O is very similar to $\leq$, the main difference being that we ignore multiplicative constants.

---
Tags: asymptotics
---


title: Find initial ranks

text:
# Question
Title: Find initial ranks
Assume there is an array $A$ of $n$ elements. $A$ contains every number from $1$ to $n$. We are given an array $B$ of $n$ elements. If we move each element $A\[i\]$ left by $B\[i\]$ places starting from $i = 0$ until $n-1$, in the end array $A$ will be sorted in increasing order, i.e. it will be $A = \[1, 2, 3, ..., n\]$. Given array $B$, find the initial value of array $A$.

For example, if $B = \[0, 1, 2, 0, 1\]$, $A$ will be $\[3, 2, 1, 5, 4\]$: We move $A\[1\]$ left by $1$, then $A\[2\]$ left by $2$, then $A\[4\]$ left by $1$, and $A$ becomes $\[1, 2, 3, 4, 5\]$. A $Θ(n^2)$ algorithm for finding $A$ is trivial. I know that there is an $Θ(n \log n)$ algorithm using segment trees, but I can't figure it out.

# Answer
> 1 votes
Assuming you can perform arithmetic in $\Theta(1)$ time, you can solve the problem in linear time.

First of all, we observe that if we move an element $k$ positions to the left, then the $k$ previous elements get moved one space to the right. Therefore, if we keep the tally of how many places an element moved, we have a naive but workable solution.

We initialize an array $C$ of size $n$, where each cell is set to $0$. Then, for all $1 \le i \le n$, we set $C\[i\]$ to $C\[i\] - B\[i\]$ and increment $C\[i-1\], C\[i-2\], ..., C\[i-B\[i\]+1\]$ by $1$. At the end of this loop, we simply determine $A\[i\] = i + C\[i\]$ for all $i$.

However, this solution requires $\Theta(n^2)$ operations. We may obtain a more efficient algorithm by observing that all our update operations only involve consecutive cells of the array.

We initialize to all zeroes another array $D$ of size $n$. Rather than updating $C$ as described above, for all $1 \le i \le n$ we do the following assignments:

> $D\[i\] \leftarrow D\[i\] - D\[B\[i\]\]$
>
> $D\[i+1\] \leftarrow D\[i+1\] + D\[B\[i\]\]$
>
> $D\[i-B\[i\]\] \leftarrow D\[i-B\[i\]\] + 1$
>
> $D\[i\] \leftarrow D\[i\] - 1$

Imagine that we had also updated $C$ as in the first algorithm. Then, after all the operations on $D$ it would hold that for all $k$:

$$ C\[k\] = \sum\_{i = 1}^k D\[i\] $$

By the above invariant, we may just leave $C$ to zero until the end of the loop. Then we set :

> $C\[1\] \leftarrow D\[1\]$

and for all $i\>1$:

> $C\[i\] \leftarrow C\[i-1\] + D\[i\]$

And finally for all $i$:

> $A\[i\] = i + C\[i\]$

The main loop performs a constant number of additions for each element of the array and the rest of the algorithm is obviously $O(n)$, the overall complexity is therefore $\Theta(n)$.

# Answer
> -1 votes
Here's an $\theta(nlogn)$ solution using segment trees.

https://www.quora.com/What-are-the-ways-to-solve-this-spoj-problem-SPOJ-com-Problem-ORDERS#

---
Tags: sorting, binary-trees
---


# Question
Title: Metaprogramming taken to an unnecessarily high level- how can a program write not just other programs, but a programming language?
So basically, automated language-oriented programming. I've tried finding info on this concept, but have had some trouble, probably because my brain is having a bit of trouble grasping the subject while thinking about it. It could be better defined as metaprogramming going to a deeper level- rewriting the programming language *it is written in* as well as or instead of the program itself.

Theoretically, through this a program would be able to operate on an infinite number of levels. I think this should be a key part of artificial intelligence, as we humans have written numerous programming languages all on top of each other and from scratch, so our programs should be able to as well.

How or why someone would ever do this is not the question. The better question is, "why not?"

If you are able to answer this question, don't worry because I have more to back it up. What programming languages would be best for this kind of thing, and what are some terms I can use in the future to better describe and grasp this concept?

# Answer
Of course we could in principle auto-generate a full programming language. First we'd have to say *what* being a full programming language actually entails. Here is my attempt:

* Syntax of programs.
* A notion of value (programs that have no further reductions, but are not stuck).
* A reduction relation giving the operational semantic.
* A notion of program equality.

All of this can be specified syntactically and generated by a computer. There are tools for part of this purpose, e.g. Ott, but specifying the whole operational semantics of a realistic PL is extremely hard work. One could argue that for example the C used in programming the Linux kernel is only specified by the official GCC version used for compilation of the kernel.

As specifying all of this is such a pain, nobody has so far produced a full-spectrum meta-programming tool. At this point it is not clear how it would look like and how it would help.
> 0 votes

---
Tags: computability, programming-languages, artificial-intelligence, language-design, meta-programming
---


# Question
Title: Special term for a cycle containing a single vertex and edge
Is there a special term for a cycle containing a single vertex and edge? I feel like I read "self-cycle" somewhere, but can't find where.

# Answer
It is generally called a Self Loop.

It refers to an edge that connects a vertex to itself.
> 6 votes

---
Tags: graphs, terminology
---


title: Are constants faster than variables?

text:
# Question
Title: Are constants faster than variables?
It's said that constant references within a program are replaced by the value at compile time, where as, variable references will need to be looked up at run time - making them slower.

Yeah, it sounds faster, but won't they ultimately both be locations in memory (that will have to be looked up), with the difference being that the variable can be altered?

# Answer
Some machine instruction sets include instructions for which 'small' constants are *part of the instruction*, either explicitly or implicitly. E.g the set of 'add' instructions can include 'add *immediate*', where the value to be added fills out the rest of the instruction bits. In that case, the operation *does not* need to fetch the constant value from a separate location - it 'comes for free' during the 'add' instruction fetch. Not all constants can be handled in this manner, but a lot of the more common constants can.

Something similar has been done in certain interpreters. For example, the Pascal P-CODE interpreter implemented each instruction op-code as one byte, but all 128 of the positive byte values were interpreted as *immediate loads* \- e.g if the next op-code was the value 0x40 (the 'space' character), then the value 0x40 was pushed onto the expression stack. The Java Virtual Machine derives (at least conceptually) from the P-CODE interpreter, and may do the same thing.
> 5 votes

# Answer
An operation like a + c can often be implemented slightly faster if c is a constant that is known to the compiler because it can be made part of the instruction. Also if a value is known to be unchanged that gives opportunities to an optimising compiler. In the extreme case, if you calculate a\*c and know that c is the constant 1.0, you don't even to multiply.

There are exceptions: Some compilers seem to believe that constants are *always* faster. If a variable like c is used often, it gets loaded into a register and stays there. If c is a constant, the compiler loads it every single time it is used. I've had time critical code where execution time improved significantly when I convinced the compiler that a constant value *might* change (storing a constant into a variable didn't help because the compiler figured out the value never changed).

This is a compiler limitation. The point is: It's very hard to predict what exactly will run faster. And it can change as processors change, or as compilers change.
> 2 votes

---
Tags: memory-access
---


# Question
Title: Calculating the kth largest distance among $n$ points on a number line in $O(n\log n)$?
I have got some difficulties to solve this algorithm problem.

I have been given a set of n points on a number line. Those points are not sorted in the set. For any two points $(a, b)$ in the set, their distance is calculated as $|a-b|$. Now I need to calculated the kth largest among all possible distances of the n points in $O(n \log n)$ time using a randomized algorithm and a deterministic algorithm respectively.

To solve this problem, I begin with sorting the n points in $O(n \log n)$ time. I noticed that this problem it is similar to the quick select for the kth largest of the array. The naive approach is to calculate all possible distances and do quick select. But this takes $O(n^2)$ running time. It seems that I have to run the quick select with only necessary distances calculated. Now I have to do two things recursively:

1. partition all distances with a randomly chosen pivot, and
2. find out the numbers of distances on each side to determine which part for recursion.

There would be $O(n \log n)$ steps for the recursion. So, I have to do the two things above in $O(n)$ time. And I have difficulties with that.

Please help me. Thank you very much.

# Answer
> 1 votes
Given some pivot $K$, you can count the pairs with differences above it in $O(n)$, whether you use a random pivot or binary search.

The pairs form a kind of uneven grid in the plane, and you can search diagonally along the line $y = K+x$ to find the border between $x\_j - x\_i \le K$ and $x\_j - x\_i \gt K$ in $O(n)$ as follows (Bresenham's Line Drawing Algorithm):

1. Start at the y axis and find minimum $j$ so that $x\_j - x\_0 \> K$
2. $Count = n-j+1$
3. For $i = 1$ to $n-1$ do

While $x\_j - x\_i \< K$, $j = j+1$

If $j=n$ break

$Count = Count + n - j + 1$

(There are some adjustments for when K is larger than the range, but the main idea is here.)

Basically you move right and then slide $j$ up until you cross the line, then add all the entries above that point to the count. As you continue right you're always at or above the $j$ you used in the previous column, so you do $O(n)$ pair tests for the whole scan.

# Answer
> 0 votes
Given are numbers $x\_1$ to $x\_n$. We assume they are sorted in non-decreasing order (since they can be sorted in O (n log n)). We assume that the distance d (i, j) between $x\_i$ and $x\_j$ is calculated in constant time as $x\_j - x\_i$, if j ≥ i, with fixed precision. When we are looking for "the k-th largest distance", we look for a pair (i, j), i ≤ j, such that d (i', j') ≥ d (i, j) for exactly k pairs (i', j'), i' ≤ j'. The solution may be not unique. Assume 1 ≤ k ≤ n (n+1) / 2, otherwise there is no solution.

Subproblem: Given d ≥ 0, find how many pairs (i, j), i ≤ j, there are with d (i, j) ≥ d (we will want to find d such that this number is k). This can be done in linear time: For every i, 1 ≤ i ≤ n, let $j\_i$ be the smallest j, i ≤ j ≤ n, such that d (i, j) ≥ d, or $j\_i = n + 1$ if no such j exists. We get the number of pairs by adding $n - j\_i + 1$ for 1 ≤ i ≤ n.

To find $j\_i$, we let $j\_i = 1$ if i = 1, and $j\_i = max (i, j\_{i-1})$ if i \> 1. Then as long as $j\_i ≤ n$ and $d (i, j\_i) \< d$ we increase $j\_i$ by 1. This is all done in linear time, because we don't increase the various values of $j\_i$ more than n times in total.

Main problem: We know that 0 ≤ d (i, j) ≤ d (1, n). So we just perform a binary search to find d, 0 ≤ d ≤ d (1, n) such that exactly k values d (i, j) are ≤ d: Start with low = 0, high = d (1, n). If high = 0 then all distances are 0, and any (i, j), i ≤ j, is a solution.

Otherwise repeat as long as there are possible values between low and high: Pick mid between low and high with about equal numbers of values low \< mid and mid \< high (if the distances are floating-point numbers then mid is usually *not* (low + high) / 2). Find how many pairs (i, j) there are with d (i, j) ≥ mid. If that number is ≥ k then let high = mid, otherwise let low = mid.

Eventually low and high are consecutive possible values. If there are less than k pairs d (i, j) ≥ high then let d = low, otherwise d = hi. Use the (subproblem) algorithm above to find the pairs d (i, j) ≥ d; that algorithm will also find (i, j) with d (i, j) = d, and that's the solution.

---
Tags: algorithms, randomized-algorithms
---


title: What is a 'subrecursive algorithm'?

text:
# Question
Title: What is a 'subrecursive algorithm'?
I am reading Exploring Robotic Minds by Prof. Jun Tani, and came across the term `subrecursive`. Original context:

> Another possibility might be to assume *subrecursive* functions embedded in analogical processes rather than logical operations in FLB that can mimic recurssive operations for finite levels.

FLB is Noam Chomsky's *faculty of language in a broad sense*

I am have found the following definition from Campagnolo et al., but am having a hard time understanding it. Any help unpacking the following or an example would be greatly appreciated :)

> All functions in the Grzegorczyk hierarchy are subrecursive, meaning that they are computable in a number of steps which is a less computationally complex function of the input than the function itself

**Bonus question**

Are subrecursive algorithms the opposite of superrecursive algorithms? In either case can you help me understand the relationship between them?

# Answer
> 4 votes
There exist many interesting languages that do not have the full expressiveness of Turing Machines: these languages are traditionally called *subrecursive*.

The typical example is the language of primitive recursive algorithms, provably equivalent to the language of algorithms that can be written with "for-like" statements (fixed step, fixed bounds). Primitive recursive algorithms are total, hence they are not complete (that means that there are *total* functions not expressible in the formalism). A famous example of a total function not expressible in the primitive recursive setting is Ackermann function.

Other examples of subrecursive languages come from logic. It is well know that no logical system (rich enough to allow to reason about natural numbers) is complete. Hence you cannot expect to prove the totality of all algorithms in them. That is to say that any logical system characterizes a set of computable functions that are provably total in the given system. For instance, the set of computable functions provably total in Peano arithmetics is the so called Goedel's System T (a higher order generalization of primitive recursion); similarly, the set of computable functions provably total in second order arithmetics is Girard's System F, also know as polymorphic lambda calculus.

The interest of considering subrecursive languages consists in the fact of capturing *statically* , i.e. by the way the program is written, relevant *dynamic* aspects of the algorithm, such as *totality*, or complexity properties.

The problem of providing syntactical characterizations of subrecursive complexity classes such as P, Pspace, etc. has received much attention in the literature. The recent field of Implicit Complexity aims at studying the computational complexity of programs with no reference to a particular machine model and explicit bounds on time or memory, but instead relying on logical or computational principles that entail complexity properties, typically via a controlled use of the available resources. For an introduction to this topic, you may consult the special issue on Implicit Computational Complexity, ACM Trans. Comput. Log., Vol 10, n.4 2009.

Other interesting characterizations have been obtained restricting the interpretation of programming languages to finite domains. The seminal result in this area is an old work of Gurevich ("Algebras of feasible functions", FOCS 1983) where he proved that interpreting primitive recursive functions (resp. recursive functions) over finite structures one precisely get the log-space (resp. polynomial time) computable functions.

Please have a look at my article "Computational Complexity via Finite Types", ACM Trans. Comput. Log., Vol 16, n.15 2015, for more references in this area.

# Answer
> 2 votes
From http://www.cs.toronto.edu/~bor/Papers/subrecursive.pdf

> PR is called universal or general recursive. A language characterized by a subset of R is called subrecursive.

where

> Pn is all n argument partial functions
>
> PRn is all n argument partial recursive functions

---
Tags: algorithms, terminology, recursion
---


# Question
Title: How to get the quick answer to the "Is there AT LEAST ONE subset that contains all given elements?" question if the set of subsets is very large?
I have a very large amount of objects that look like this:

```
DataDict = {
id1: {"a": true, "b": true, "bc": true, "hgf": true},
id2: {"bcwe": true, "nKNNn": true, "mjj": true, "AAt": true},
id3: {"h": true, "a": true, "mjj": true, "ABwAU": true},
id4: {"wvzy": true, "zzba": true, "abc": true, "a": true},
...
}

```

or just (as a set of sets, note that `id`s may be excluded)

```
DataSet = {
{"a", "b", "bc", "hgf"},
{"bcwe", "nKNNn", "mjj", "AAt"},
{"h", "a", "mjj", "ABwAU"},
{"wvzy", "zzba", "abc", "a"},
...
}

```

Let `M` denote the total number of objects in `DataDict` (or subsets in `DataSet`), and let `N` denote the total number of unique names of properties found in `DataDict` (or the total number of unique strings found in `DataSet`).

The question is: given the set of strings `{string1, string2, string3, ...}`, how to get the **Yes/No** answer (assuming that there is a way to prepare the “index” for `DataSet`) to the “Does `DataSet` contain **at least one** subset that contains `string1` AND `string2` AND `string3` AND ...?” question as fast as possible?

In another form, the question is: given the array `A = [string1, string2, string3, ...]`, how to build the index (data structure) for `DataDict` that allows to quickly determine if it contains **at least one** object `obj` (I don’t care which object to choose, moreover, I don't want to return this object, all I want is that the function should return `true` if such an object exists, and `false` if not) such that `DataDict.obj.string1 is true AND DataDict.obj.string2 is true AND DataDict.obj.string3 is true AND ...`?

The only way that I see is to build the index like this:

```
{
"a": [1, 3, 4],
"abc": [4],
...
}

```

and, for example, if `A = ["a", "abc"]`, then I need to find the intersection of two arrays (`[1, 3, 4]` and `[4]`), but **stop as soon as one common element is found** and return `true` (if there are no common elements, return `false`). But these operations are very costly and time-consuming, which often leads to the unacceptable waiting time. Is there a way that guarantees a significantly better performance for all cases?

It would be extraordinarily nice if there exists a solution that (assuming that the index already exists) finds the answers depending on `A.length` time. The good solutions may depend on `log M` or `log N` or even close to `log M` multipled by `log N`, but I cannot imagine how to find such a solution...

# Answer
> 2 votes
It's possible to answer such queries in time $O(M^{1 - S/N})$, where $S$ is the size of the subset in the query, using a data structure from Ron Rivest:

Partial-Match Retrieval Algorithms. Ronald L. Rivest. SIAM Journal Computing, vol 5 no 1, March 1976.

Basically, you convert each set to a bitvector of length $N$, then use Rivest's partial-match queries. This is ever so slightly faster than the naive algorithm, whose running time will be about $O(M)$ (or a bit more).

---

Your idea using indices is another approach that might be faster in practice, especially if most sets are much smaller than $N$. Note that it's possible to optimize this a bit. Your index will have, for each string $x$, a list of indices of sets that contain $x$ *and* the length of that list. Now, given a set $A$, you can check for each $x \in A$ the length of the corresponding list in the index, and find the shortest such list, and enumerate all entries in that list to see if any of them are a superset of $A$. See also https://cstheory.stackexchange.com/q/19526/5038. I think the worst-case running time is no better than the naive algorithm, but in practice it might perform significantly better.

# Answer
> 0 votes
If this does not fit the format let me know and I will delete

I will call the individual elements words

**Algorithm**

1. Sort each subset
2. Sort the search
3. For each subset
    * Compare count - if search count \> subset count move on
    * Check first in search for \>= first element in subset
    * Check last in search for \<= last element in subset
    * For each word in search do a binary search on subset - quit when you don't get a hit
    * Can start the binary search on last match + 1

The complexity is a little complex as it will depend on the size of the individual subsets.
N is total number of words of all subsets
M is number of subsets
N/M is average subset size
S is number of search terms
I think this would be O(S * log(N/M - 1))
Worse case would be every subset has every word but the last
Since log is not linear taking the average N/M is not precise - should actually sum every log(dataset size)

It might be advantageous to start on the largest subsets as you have better chance of a match but you are also searching a larger subset.

**A database does this very efficiently**

1. Put the words in a table (dictionary) with an integer as a key and call it WordIndex. Create a separate index on the Word
2. Use an integer for the key on the input DataDict and call that DataSetKey
3. Create a table for the Content of WordIndexKey, DataSetKey as a composite PK
This table will have one row for each word in each DataSet

In search
1. First search WordIndex to make sure you have them all period
2. Save the WordIndex of the search in a set WordIndexs
3. Get a count of the words in the search S 4. The query is like this

```
select top (1) DataSetKey
from Content
where WordIndexKey in WordIndexs
group by DataSetKey
having count(*) = S

```

---
Tags: algorithms, data-structures, optimization, search-algorithms, performance
---


# Question
Title: Is this problem NP-hard? select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones
select k sets from a collection of sets such that each selected set has an empty intersection with the non selected ones

# Answer
Your problem can be solved in polynomial time. Form an undirected graph where each set is a vertex, and there is an edge between two sets if they have a non-empty intersection. Decompose it into connected components, and let the sizes of the connected components be $n\_1,\dots,n\_t$. Then there exists a solution to your problem if and only if there is a subset of the integers $n\_1,\dots,n\_t$ that sums to $k$. This is the unary subset-sum problem, and it has a polynomial-time algorithm (via dynamic programming). Consequently, your problem can be solved in polynomial time, too.

In contrast, set packing (does there exist a way to select k sets so that each selected set has an empty intersection with all the other selected ones?) is NP-hard.
> 1 votes

---
Tags: np-complete
---


title: Pumping Lemma String Choice

text:
# Question
Title: Pumping Lemma String Choice
Let $A = \\{ uu \text{ } | \text{ } u \in \\{a,b\\}^\* \\}$ be a language. Suppose that we want to prove that A is not regular via the pumping lemma, why is the string w = $a^{p} a^{p}$ not valid to derive a contradiction?

# Answer
The pumping lemma states that if a language $L$ is regular, then *there exists* a pumping length $p\gt0$ such that *for all* strings $s$ in $L$ with length at least $p$, *there exists* a way to split $s$ in the form $xyz$ such that *all* of the following are true:

1. $xy^iz\in L$ for all $i\ge0,i\in\mathbb Z$
2. $|y|\gt0$
3. $|xy|\le p$

The contrapositive is:

*For all* pumping lengths $p\gt0$, if *there exists* a string $s$ in $L$ of length at least $p$ such that *for all* ways to split $s$ in the form $xyz$, *at least* one of the three statements (those mentioned above) are false, then the language $L$ is not regular.

When you prove that a language $L$ is not regular using the pumping lemma, you generally assume that it is regular, and prove that the premise of the contrapositive of the pumping lemma is true. This implies that the language is not regular, leading to a contradiction.

Now, in your problem, you would like to choose the string $a^pa^p$. As you can see in the contrapositive statement, the choice of choosing $x,y,z$ does not lie with you. So, you need to show that the contrapositive holds true for every choice of $x,y,z$, i.e., at least one of the three statements in the pumping lemma is false for every choice of $x,y,z$.

So, in general, $$a^pa^p=a^{2p}=a^ia^ja^k$$ for some $i,j,k\ge0$ and $i+j+k=2p$. Note that $j\gt0$ for statement 2 to be true, and $i+j\le p$ from statement 3.

Now, all that needs to happen is $j$ to be even and $i=k$,which, in general, is possible as all possible ways of splitting the string need to be taken into account that suppose $j=2l$ for some $l\gt0$. Then, $$a^pa^p=a^ia^{2l}a^i=a^{i+l}a^{i+l}$$

Now, as per statement 1, suppose we pump $y$, we get $a^i(a^{2l})^na^i\in L$ for all $n\ge0,n\in \mathbb Z$. Note that for every choice of $n$, $$a^{i+ln}a^{i+ln}\in L$$

So, for this string $s$, we have managed to find a way to split it, for any $p$, such that all the conditions of the pumping lemma hold. This does not show that the premise of the contrapositive is true, and hence does not lead to a contradiction. Thus, to show that it is not regular, you need to *choose* a more suitable string $s$ for all $p$ that results in the premise being true, which would imply that $L$ is not regular, leading to a contradiction.
> 2 votes

# Answer
In this particular case you choose a string that only has a single letter $a$. That means any argument will also work for the restriction of $A$ to $\\{a\\}^\*$, which is $\\{ uu \mid u\in \\{a\\}^\*\\} = (aa)^\*$. Now that is a regular language, which by the pumping lemma can be pumped within $(aa)^\*$ and hence within $A$.
> 0 votes

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


# Question
Title: Find all rational roots of a polynomial equation
I'm going to try to design an algorithm to find all the rational roots of a polynomial equation in range \[a, b\]. Can someone please tell me which algorithm currently solves the problem with lowest worst-case complexity? This algorithm will be for a general purpose computer(Turing Machine).

# Answer
> 4 votes
If you only want to find all *rational* roots, you can simply use the *rational root theorem*. This theorem states that, given a polynomial $a\_n x^n + a\_{n-1}x^{n-1} + \ldots + a\_1x+a\_0$, for any rational root $x=p/q$, where $p,q\in \mathbb N$ and $GCD(p,q)=1$, we have:

* $p$ is a divisor of $a\_0$ and
* $q$ is a divisor of $a\_n$.

So, one possible algorithm is to factorise $a\_0$ and $a\_n$ to get all possible $p,q$ and simply 'fill in' the combinations as a ratio to see if it is a root. This way, we find all possible roots. The complexity of the root finding is negligible to the factorisation, so the complexity of this method is the complexity of factorising $a\_0$ and $a\_n$, which will take a long time for large $a\_0$ and $a\_n$ (but is fast for small $a\_0$ and $a\_n$, independent of the rest of the equation!)

There is a speedup, however. If a root $p/q\in \[a,b\]$, this means that $p\in \[aq,bq\]$ and $q\in \[p/b,p/a\]$. If $a\_0$ is small, but $a\_n$ is large, we can find all divisors $p\_i$ of $a\_0$ and test for all integers in the range $\[p\_i/b,p\_i/a\]$ whether they divide $a\_n$. If $a\_n$ is large and $\[a,b\]$ not too big, this will be a lot faster than factoring $a\_n$. This means that we only have to do one factorisation and can do it on the smallest of $a\_0$ and $a\_n$.

So, to get a complete overview of the worst case complexity for the methods described, define $a\_{\max}=\max\\{a\_0,a\_n\\}$ and $a\_{\min} = \min\\{a\_0,a\_n\\}$. Assume $b\geq a\>1$ (another worst case exists when $a,b\<1$, but that will have the same running time, only with $1/a$ and $1/b$). We will factor $a\_{\min}$ and consider all it's divisors, of which there are $O(\log n)$ *on average* (The actual worst case upper bound is $\exp(O(\frac{\log n}{\log\log n}))$, but this factor will likely be dominated anyway, so I'd rather keep it simple. A derivation and more is given here).

All divisors of $a\_{\min}$ are in the range $\[1,\sqrt{a\_{\min}}\]$, so we do at most $\lceil (b-a)\sqrt{a\_{\min}} \rceil$ divisor tests per factor of $a\_\min$. Since we know that any factor of $n$ must be in $\[1,\sqrt{n}\]$, we have that $b-a\leq \sqrt{a\_\max}$ to be useful (if not, replace $\[a,b\]$ by $\[1,\sqrt{a\_\max}\]$). So, we do at most $\lceil \sqrt{a\_{\min}a\_\max} \rceil$ divisor tests. Testing whether a number is a divisor of $a\_\max$ takes $O(\log a\_\max)$ time, using the Euclidean algorithm.

Factoring $a\_\min$ takes $O(F(a\_\min))$, where $F(n):=\exp ((\log n)^{1/3}(\log \log n)^{2/3})$.

So, in total, this algorithm has a worst case complexity of $O(F(a\_\min) + (b-a)\sqrt{a\_\min}\log{a\_\min}\log{a\_\max})$ time. Since we can assume $(b-a)\leq a\_\max$, the factoring is the only non-polynomial (in $a\_\min$ or $a\_\max$) part of this formula, so we get that the complexity is simply $O(F(a\_\min))$.

I highly doubt that it is possible to find all rational roots within a range without factoring at least one of the coefficients, because that would mean (by the rational root theorem), that we have found a more efficient algorithm for factoring! In that case, the algorithm I gave is asymptotically optimal, as it is the cost of factoring the smallest of the coefficients $a\_0$ and $a\_n$.

# Answer
> 2 votes
The paper Computing Real Roots of Real Polynomials by Sagraloff and Mehlhorn from 2015 provides an almost optimal algorithm and references for simpler algorithms that might be used in practice. The CGAL library (in version 4.9) for example uses the method developed by Arno Eigenwillig in his PhD thesis *Real Root Isolation for Exact and Approximate Polynomials Using Descartes' Rule of Signs*.

---
Tags: algorithms, polynomials, algorithm-design
---