# Question
Title: in O(n) time: Find greatest element in set where comparison is not transitive
Title states the question.

We have as inputs a list of elements, that we can compare (determine which is **greatest**). No element can be equal.

Key points:

1. Comparison is **not transitive** (think rock paper scissors): this can be true: A \> B, B \> C, C \> A *(note this is not a valid input since there is no valid answer here, I'm only describing what "non-transitive comparison" means)*
2. Each input array will is guaranteed to have an answer
3. **greatest** means the element **must** be greater than every other element
4. Converse property holds i.e. A \> B implies that B \< A

Example:

```
Input: [A,B,C,D]
A > B, B > C, C > A
D > A, D > B, D > C
Output: D

```

I cannot figure out a way to do this in O(n) time, my best solution is O(n^2).

I get stuck on every approach because of the fact that to be certain of an answer, the element needs to be explicitly compared to every other element, to prove it is indeed the answer (because comparison is not transitive).

This rules out the use of a heap, sorting, etc.

# Answer
> 38 votes
The standard algorithm for finding a maximum still works. Start with $a\_1$ and go over the elements, if you see a larger value, update the maximum to be that value. The reason this works is that every element you skipped is smaller than at least one element, and can thus not be the maximum.

To be clear, by the "standard algorithm" I mean the following:

```
max <- a_1
for i=2 to n
   if a_i > max
      max <- a_i
output max

```

For completeness, I will discuss here the issues raised in the comments. The setting in the above discussion is finding a maximum relative to an anti symmetric relation $\<$, where $a\_i$ is a maximum if for all $j\neq i$ we have $a\_i\>a\_j$. The above algorithm works under the assumption that a maximum exists, however if this is not known, one can use it to verify the existence of a maximum (check whether the returned element is indeed greater than all other elements, this is mentioned in Chi's comment and in Ilmari Karonen answer).

If $\<$ is not necessarily anti symmetric, then the above algorithm fails (as Emil mentioned in the comments). If $\<$ is an arbitrary relation (i.e. we are relaxing both transitivity and anti symmetry), then it is not hard to show that finding a maximum in linear time is not possible. Denote by $\\#a\_i$ the number of times $a\_i$ participated in a query, we define an adversarial relation in a way that the maximum cannot be revealed without enough queries. Given the query $a\_i \>?a\_j $, answer $a\_i\>a\_j$ if $\\# a\_i \< n-1$ and $a\_i\ 25 votes
As Ariel notes, the standard maximum-finding algorithm given below:

```
def find_maximum(a):
    m = a[0]
    for x in a:
        if x > m: m = x
    return m

```

will in fact work without modification as long as:

* any pair of elements can be compared, and
* the input is guaranteed to contain a maximal element, i.e. an element that is pairwise greater than any other element in the input.

(The first assumption above can actually be relaxed, even without having to modify the algorithm, as long as we assume that the maximal element is comparable with every other element and that `x > y` is always false if the elements `x` and `y` are incomparable.)

In particular, your claim that:

> \[…\] to be certain of an answer, the element needs to be explicitly compared to every other element (because comparison is not transitive).

is not true under the assumptions given above. In fact, to prove that the algorithm above will always find the maximal element, it's sufficient to observe that:

1. since the loop iterates over all the input elements, at some iteration `x` will be the maximal element;
2. since the maximal element is pairwise greater than every other element, it follows that, at the end of that iteration, `m` will be the maximal element; and
3. since no other element can be pairwise greater than the maximal element, it follows that `m` will not change on any of the subsequent iterations.

Therefore, at the end of the loop, `m` will always be the maximal element, if the input contains one.

---

Ps. If the input does *not* necessarily always contain a maximal element, then verifying that fact will indeed require testing the candidate answer against every other element to verify that it is really maximal. However, we can still do that in O(*n*) time *after* running the maximum-finding algorithm above:

```
def find_maximum_if_any(a):
    # step 1: find the maximum, if one exists
    m = a[0]
    for x in a:
        if x > m: m = x

    # step 2: verify that the element we found is indeed maximal
    for x in a:
        if x > m: return None  # the input contains no maximal element
    return m  # yes, m is a maximal element

```

(I'm assuming here that the relation `>` is irreflexive, i.e. no element can be greater than itself. If that's not necessarily the case, the comparison `x > m` in step 2 should be replaced with `x ≠ m and x > m`, where  denotes identity comparison. Or we could just apply the optimization noted below.)

To prove the correctness of this variation of the algorithm, consider the two possible cases:

* If the input contains a maximal element, then step 1 will find it (as shown above) and step 2 will confirm it.
* If the input does *not* contain a maximal element, then step 1 will end up picking some arbitrary element as `m`. It doesn't matter which element it is, since it will in any case be non-maximal, and therefore step 2 will detect that and return `None`.

If we stored the index of `m` in the input array `a`, we could actually optimize step 2 to only check those elements that come before `m` in `a`, since any later elements have already been compared with `m` in step 1. But this optimization does not change the asymptotic time complexity of the algorithm, which is still O(*n*).

# Answer
> 5 votes
As an addition to Ariel's answer about the concerns raised by Emil Jeřábek: If we allow $A\<B$ and $B\<A$ then there is no O(n) algorithm:

Assume you have elements $A\_1 ... A\_n$. Your algorithm will in each step query $A\_i\<A\_j$ for some pair i and j. No matter in which order you query them, there is always a relation where you have to query all relations before finding the maximum. The reason for this is best described by assuming you have an adversary who can change the problem while your algorithm is running.

(Note that the argument is independent of what the algorithm actually does with the information he gets about the elements, since it explains that he cannot know that an element is maximal before making $n^2$ queries.)

For most of the algorithm the adversary will make sure to always return true for $A\_i\<A\_j$ until your last query for a given $j$. Note that you cannot know that one given element is maximal until you compared it to all other elements. Only for the last element for which you finish all relations the adversary will return true for the last element as well.

The resulting relation will always be such that there is some $j\_0$ for which $A\_i \< A\_{j\_0}\forall i$ and for all other $j$ there will be some $i\_j$ such that $A\_i\<A\_j \forall i\neq i\_j$ and we will not have $A\_{i\_j} \< A\_j$. The adversary chooses $j\_0$ and the $i\_j$s depending on your algorithm.

I hope this is somewhat understandable. Feel free to ask in comments or edit.

The basic idea is that you cannot gather any information about the remaining elements from the ones you already know if you allow a completely arbitrary relation.

The argument still works if we disallow $A\ 4 votes
"greatest means the element must be greater than every other element" is a huge hint on how to do this in $O(n)$.

If you go through your list comparing elements, any element that "loses" a comparison can be immediately discarded as, in order to be the greatest, it must be greater than ALL other elements so the single loss disqualifies it.

Once you think of it in that manner, then it's pretty obvious that you actually can make $n-1$ comparisons and end up with the greatest element as the result of your last comparison, by discarding a loser each and every time.

This solution is enabled by a subtlety: "No element can be equal" combined with the fact that there will always be a greatest element. If we map wins relationships as a directed graph, it is clear that we can reach the greatest element simply by following the wins.

# Answer
> 3 votes
I assume that the relation antisymmetric for at least a single element (which guarantees the existence of the greatest element), otherwise the task is impossible. If all elements in the finite set are comparable then usual finding-maximum procedure works.

If some elements are not comparable then the following procedure will work

```
max = nil
For i=1 to n
   if max is nil then
      max = a[i]
   if max and a[i] are not comparable then
      max = nil
   else if max < a[i] then
      max = a[i]
End

```

This is how the algorithm will work on input $A,B,C,D$ with $$A \> B, B \> C, C \> A $$ $$D \> A, D \> B, D \> C$$ as in your post.

Initially. max = nil
$i=1:$ $\max = A$
$i=2:$ $\max = A$ (since $A \> B$)
$i=3:$ $\max = C$ (since $A \< C$)
$i=4:$ $\max = D$ (since $D \> C$)

This algorithm works since if $m\>a$ (or $a \< m$) for all $a$ then $m$ is the greatest. If $m\ 1 votes
I'm going to cheat and call the number of `A > B` entries $n$ and you need to look at every entry at least once.

That way you can loop over just the entries and remove the element that is less than the other from the set of possible solutions. With a hashset or similar this is possible in $O(n)$

# Answer
> 0 votes
One approach is you can create hashmap.

Suppose that $a \> b$, then $m\[b\] = m\[a\] + 1$, i.e., $1$.

If $b \> c$ then $m\[c\] = m\[b\] + 1$, i.e., $2$.

If $a \> e$ then $m\[e\] = m\[a\] + 1$, i.e., $1$.

In this way, traverse the hashmap, and find the element whose value is zero.

---
Tags: algorithms, time-complexity, sets, transitivity
---


# Question
Title: PDA for the language of words $uv$ such that $|u| \geq |v|$ and $v$ contains 1
Consider the language $\\{ uv : \text{$|u| \ge |v|$ and $v$ contains a 1}\\}$.

I am unable to understand how to accept this language using a PDA. How to check the length condition as well as check if there's a 1 in the $v$ portion?

The question has previously been posted here but I couldn't figure out much from the answers to that. PDA recognising all strings with a $1$ in the second half

# Answer
A pushdown automaton accepting this language proceeds as follows:

1. Push a marker $S$ to the top of the stack.
2. Push $A$ to the stack for each input symbol read.
3. At some point, nondeterministically transition to the second phase.
4. Pop $A$ from the stack for each input symbol read, marking whether you ever read $1$.
5. Fail if you encounter $S$.
6. Succeed if you successfully read the entire input, and encountered $1$ during the second phase.

It is also easy to give a context-free grammar for this language, using $\Sigma$ as a shortcut for the alphabet: \begin{align} &S \to \Sigma S \mid \Sigma S \Sigma \mid \Sigma T 1 \\ &T \to \Sigma T \Sigma \mid \epsilon \end{align}
> 1 votes

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


# Question
Title: The Algorithm Design Manual - Working with the Big Oh
I'm reading *The Algorithm Design Manuel* and one part is kind of confusing to me

The part that's confusing to me is how in the "Proving the Theta" section he proves that selection sort is Ω(n^2). I mean, I understand that for some (c) c.n^2 can be a lower bound for selection sort, however I don't understand how he proves this in that section.

I would really appreciate it if you could help me understand that part. Thanks. .

# Answer
It is difficult to avoid what is repeating what is in the text, but you have exactly:

$T(n) = (n-1)+(n-2)+\ldots+1+0 =n\tfrac{n-1}{2} = \tfrac12n^2 -\tfrac12n$

and as an upper bound taking each value *up* to $n-1$:

$T(n) \le (n-1)+(n-1)+\ldots+(n-1)+(n-1) =n(n-1) = n^2-n$

and as an lower bound taking values of at least $\tfrac n2$ *down* to $\tfrac n2$ and other *down* to $0$ $($assuming $n$ is even; the odd case gives $\tfrac14n^2+\tfrac14 n)$:

$T(n) \ge \tfrac n2 +\ldots +\tfrac n2 +0+\ldots +0 = \tfrac n2 \times \tfrac n2 +\tfrac n2 \times 0 = \tfrac14n^2$

Since all three are essentially of the order of $n^2$ up to a constant, you can conclude $T(n)$ is $O(n^2)$ and $\Omega(n^2)$ and so $\Theta(n^2)$
> 1 votes

---
Tags: algorithms, asymptotics
---


# Question
Title: The Church-Turing thesis and Hyper-computation
I am not a computer scientist and this is my first question.

This question is a question in layman terms and I also want the answer in layman terms.

When I searched hyper-computation. There was a list of models of hyper-computers.

Now, my question is that what are the problems with those models and if it is possible to create models of computers which can compute non-Turing computable things then doesn't, that already proves the Church-Turing thesis wrong and if it does prove that Church-Turing thesis is wrong then why people still consider it to be a thing?

# Answer
The Church–Turing thesis is about physically realizable machines. To the best of our knowledge, hypercomputation models cannot be realized in the physical world. They are a figment of our imagination.

If someone would find a new law of physics which enables solving the halting problem, that would make a big fuss in the world of science. But I am not holding my breath.
> 5 votes

# Answer
I'll just address one model. WP says: *The Zeno machine performs its first computation step in (say) 1 minute, the second step in ½ minute, the third step in ¼ minute, etc. By summing 1+½+¼+... (a geometric series) we see that the machine performs infinitely many steps in a total of 2 minutes.* We can imagine all kinds of devices. But, looking around, we see that researchers who want to study an idealization of a physically-realizable machine, in order to get insights into what is mechanically computable, do not find that studying these is fruitful.
> 1 votes

---
Tags: church-turing-thesis, hypercomputation
---


# Question
Title: Does the host operating system know the content of your messages in a messaging applications?
Let's say you are using a messaging application (Microsoft Team, Skype, Telegram,..) on an operating system (Windows, MacOS, Linux). Does the OS know what you are sending or receiving? If yes, how? Assuming that the computer can be setup for monitoring (e.g. company's computer).

# Answer
If the OS is malicious or compromised, it can monitor everything you're sending or receiving. As one simple example, it can monitor every key press, every mouse event, and everything displayed on the screen. Why? Because the OS runs at ring 0, it has control over everything else.
> 1 votes

# Answer
The answer is basically yes, OS is a software that manages the computer hardware, resources, and etc, which means the software (that is in a higher level than the OS) (ex: a messaging app), needs to communicate to the OS to fetch / receive data from it's server.

```
[Software] --> [OS] --> [Driver] --> [Hardware (wifi adapter)] --> [Server]

```

In summary, the OS controls everything.
> 0 votes

---
Tags: operating-systems, computer-networks, security
---


# Question
Title: What is the minimum number of parts required to split the sequence S to in order to obtain sequence T?
Suppose a person has a sequence (S) consisting of integer numbers and would like to split the sequence into a number (possibly one) of continuous parts. For each part independently, I then choose any integer value and removes all occurrences of this value in the corresponding part (note that there could be no such occurrences). After that, the person will combine all parts in the same order to achieve a new sequence (T).
How to find out the minimum number of parts needed to split the sequence in order to achieve this goal .
let n = size of sequence S and m = size of sequence T

---

* **Constraints**:
1 \<= n,m \<= 2000

---

* **Input Format:** n m
Sequence S
Sequence T
* **Output Format:** if it is not possible to transform S into T output -1
otherwise, output min number of parts required.
* **Sample Input and Output**:

| Input | Output |
| --- | --- |
| 4 2
4 2 7 2
4 7 | 1 |
| 7 2
4 7 1 4 1 7 1
4 7 | 3 |
| 3 2
7 4 2
4 7 | -1 |

---

**My Attempt:** I did not understand how Sequence S={4,2,7,2} can be transformed to T = {4,7}. If I followed this procedure by splitting a sequence into parts such as {4} {2} {7} {2} and then iterate from 1st index and then the 2nd index until the end, and if I encounter the same value I delete all of its occurrences. When I do this, I get the sequence {4,2,7} and minpart is just 1.

And, for the sequence {4,7,1,4,1,7,1}, I am able to get {4,7,1} and minparts are 3.

But I do not understand, how both of these sequences: S = {4,2,7,2} and S = {4,7,1,4,1,7,1} can be transformed to the sequence T = {4,7}?

# Answer
1. To get the sequence $T = \\{4,7\\}$ from $S = \\{4,2,7,2\\}$, you can take the entire set S as a minipart and remove $2$ from it. Therefore, there is just *one* minipart.
2. To get the sequence $T = \\{4,7\\}$ from $S = \\{4,7,1,4,1,7,1\\}$, you can take *three* minimarts as follows:

* $P1 = \\{4\\}$
    * $P2 = \\{7\\}$
    * $P3 = \\{1,4,1,7,1\\}$

Now, remove $4$ from $P1$, remove $7$ from $P2$, and remove $1$ from $P3$. You will get the sequence $T = \\{4,7\\}$.
> 1 votes

---
Tags: algorithms, data-structures, dynamic-programming, subsequences, c++
---


# Question
Title: Trouble finding average case of a find max algorithm
I'm trying to find the average case number of times that max is assigned by the algorithm findMax included below.

```
findMax(list):
    maxNum = -oo  # negative infinity
    for k = 0 to len(list)-1:
        if list[k] > maxNum:
            maxNum= list[k]
    return maxNum

```
* The distribution I have considered is uniformly random.

At the back of the textbook I am currently using, the solution is said to be $O(logn)$, however, using the approach that I have came up with (which I'm not quite sure why is incorrect), I got $O(n)$ instead.

In my approach: I have used the following formula $$E\[t\_n\] = \sum^{n}\_{t=1}t \cdot Pr(t\_n=t)$$ And, I considered how many times **maxNum** was updated to calculate the expected value. First, I noticed that if the max would have been the first element, maxNum would have only been updated once. If the max was the second element, then it would have been updated twice, and so forth. Using this reasoning, I deduced that the probability of maxNum appearing in the nth position is $\frac{1}{n}$. Then, I got $$E\[t\_n\] = 1 \cdot Pr(t\_n = 1) + 2 \cdot Pr(t\_n = 2) + ... + n \cdot Pr(t\_n = n)$$ $$=\frac{n+1}{2}$$ $$\Rightarrow O(n)$$.

I am a bit lost and am unsure where my mistake took place exactly.

# Answer
Let me start with your main question "where my mistake took place exactly?" - in short, the whole point is in the wrong choice of the probability distribution for $Pr(t\_n=t)$. You are considering the number of changes in the maximum, i.e. how many times maxNum was updated, but you are using probabilities for the location the maximum in the array.

Before starting analysis, let me say, that, for example, CLRS Introduction to Algorithms, Third Edition, on page 120, calls formula you are using "cumbersome" for calculating and choose indicator function way. Donald Ervin Knuth in TAOCP Volume 1, Third Edition, 1997, pages 96-101 are using generating functions mechanism.

Now in more detail: for simplicity, let's consider the case when you have only 4 elements in the array and let us consider only such 4s in which all elements are different i.e. $(a, b, c, d)$, where all are different. I bring the pseudocode for this case from the book Jeffrey J. McConnell, Analysis of Algorithms: an Active Learning Approach , 2001, page 3

```
maxNum = a
if b > maxNum then
    maxNum = b
end if
if c > maxNum then
    maxNum = c
end if
if d > maxNum then
    maxNum = d
end if
return maxNum

```

where your loop is simply decomposed into separate lines and in 1-st line is not used negative infinity. As we are considering function $T$ the number of maxNum updatings, i.e. number of assignements, then, obviously $T$ have values 1,2,3,4. Probability distribution for $T$ can be counted directly and is

$Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$

$Pr(T=2)$: $\frac{1}{4}+\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{7}{16}$

$Pr(T=3)$: $\frac{1}{4}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}+\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{4}{16}$

$Pr(T=4)$: $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}=\frac{1}{16}$

Anticipating the question of how these calculations were obtained, let me say that it is enough to simply consider the possible options for finding the maximum in the all fours and count their fractions.

To calculate general case, where we have $n$ elements in array it's more easy to find reccurence relation for $T(n)$: $$T(n) = n \cdot T(n-1) + (n-1)!$$ and from here obtain expected value

$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum\_{i=1}^{n}\frac{1}{i} - 1 =\\ = \ln n + \gamma + \varepsilon\_{n} -1 = \ln n +O(1)$$

where $\gamma$ is Euler–Mascheroni constant and $\varepsilon\_{n} \sim \frac{1}{2n}, n\rightarrow \infty$.

**Addition.**

Now more about calculating probabilities in case of 4s $(a, b, c, d)$ where all are different:

The proportion of such fours in which the maximum is in the first place, i.e. maximum is $a$, is equal to the proportion of such fours in which the maximum is in second place , i.e. maximum is $b$, and is $\frac{1}{4}$. Same for cases with $c$ and $d$.

Such fours where maximum is $a$ and *only they* gives $1$ assignement for maxNum, i.e. $T=1$, and so we obtain $Pr(T=1)$: $\frac{1}{4}=\frac{4}{16}$.

Such fours where maximum is $b$ gives $2$ assignements, $T=2$, but we can obtain $2$ assignements also from cases where $c$ or $d$ is maximum, so we can say, that $Pr(T=2)$ includes $\frac{1}{4}$ plus some more numbers i.e. we obtain first summand for $Pr(T=2)$.

Now let's take fours where maximum is $c$. This case can produce values $2, 3$ for $T$: when $b \gt a$, then $T=3$ and when $b \lt a$, then $T=2$. As proportion for both is $\frac{1}{4}\cdot \frac{1}{2}$, then we obtain second summand for $Pr(T=2)$ and first summand for $Pr(T=3)$.

Last we consider 4s where maximum is $d$. Hope it's easy to understand, that here we have $4$ parts with equal proportion $\frac{1}{4}\cdot \frac{1}{2}\cdot \frac{1}{2}$: 1) $b \gt a, c \gt b$ which gives $T=4$, 2) $b \gt a, c \lt b$ and $b \lt a, c \gt a$ which gives $T=3$, 3)$b \lt a, c \lt a $ which gives $T=2$. Correspondingly we obtain all remained summands.

At end let me say, that it's easy to write code for some virtual experiment, for example on python from random import uniform, I can share if needed, and check, that practical frequences approximates theoretical probabilities.
> 2 votes

# Answer
If the maximum element is the $n$'th, then $\text{maxNum}$ is not necessarily updated n times. Consider for example the case where the second largest element is in first position. Then $\text{maxNum}$ is updated twice no matter where the largest element is.

Let $U\_n$ be the average number of updates of $\text{maxNum}$ for a list of size $n$. Let $i\_\max$ denote the index of the maximum element (or to be precise the random variable corresponding to that value). Notice that no update is done once $i\_\max$ is reached. Thus, conditioned on the fact that $i\_\max = i$, the average number of updates of $\text{maxNum}$ is $U\_{i-1}+1$ (where we define $U\_0=0$).

Using the law of total probability, we get $$U\_n = \sum\_{i=1}^{n} (U\_{i-1}+1) \cdot P(i\_\max = i) = \sum\_{i=0}^{n} (U\_{i-1}+1)/n.$$ (I start indexing at 1 like you did)

Multiplying this by $n$ we get $$n\cdot U\_n = \sum\_{i=0}^{n} (U\_{i-1}+1).$$

Similarly, we have $$(n-1)\cdot U\_{n-1} = \sum\_{i=0}^{n-1} (U\_{i-1}+1).$$

Subtracting the second from the first gives $$ n\cdot U\_n - (n-1)\cdot U\_{n-1} = U\_{n-1}+1$$.

Rearranging: $$U\_n = U\_{n-1} + \frac{1}{n}$$.

Expanding you get $U\_n = 1+\frac{1}{2}+\frac{1}{3}+\ldots \frac{1}{n}$. Thus $U\_n$ is the $n$'th harmonic sum $H\_n$. In fine, $U\_n = H\_n \in O(\log(n))$.
> 2 votes

---
Tags: complexity-theory, asymptotics, runtime-analysis, average-case
---


# Question
Title: What are the differences between LCF's Theorem and Automath's Prop?
How are the fundamental approaches to proving theorems by LCF and Automath different? Considering their modern descendants - Isabelle for LCF and Coq for Automath, both rely on type checking to do proof checking.

Theorems in Isabelle have a `theorem` type and the only functions that can create instances of this `theorem` type are inference rules of the logic.

Theorems in Coq have a `Prop` type and the only way to create `Prop`s is by creating proof terms that have the proposition as their types.

If I'm not wrong, LCF and Automath were developed independently around the same time so there wasn't an influence from one to the other, but perhaps by coincidence, is LCF's (Isabelle's) `Theorem` just a more generic version of Automath's (Coq's) `Prop`?

I would appreciate it if you could also point out any other fundamental differences between LCF and Automath that have manifested into their modern successors.

# Answer
> 1 votes
The difference is in what kind of type `theorem`/`Prop` is.

In Isabelle, `theorem` is a type in the underlying implementation language, that is made abstract so that the only way to create an inhabitant of that type (i.e. a valid theorem) is in the end to resort to the primitives provided by the kernel. So it is the typing constraints *of the implementation language* together with the restricted primitives that forces you to inhabit only correct theorems. Also, in that setting proofs can be any program in the implementation language producing an object of type `theorem`, but they have no specific status, and cannot be manipulated directly.

On the contrary, `Prop` is a type in the theory of Coq, but not in its implementation language: if you look at the OCaml code, there is no such thing as a `Prop` type, only a type of terms. Verifying that a term (written in a specific language called Gallina, the proof/programming language of Coq) is indeed a valid proof is a job of a *specific type-checker*. This type-checker is the kernel. In that setting, proofs have a specific status, being syntactical objects of a given type of terms in the implementation, and as such can be manipulated, inspected and so on. In particular, the tactic languages are used to generate such proofs, which is not the same as directly constructing an inhabitant of `theorem`, because such terms will still in the end be inspected by the kernel, which is the only judge of what is a valid proof.

---
Tags: proof-assistants, coq, curry-howard, isabelle
---


title: maximum cardinality weighted matching

text:
# Question
Title: maximum cardinality weighted matching
I am looking for a reference for maximum cardinality weighted matching and the best running time algorithm for it.

Maximum Cardinality Weighted Matching: Given an undirected weighted graph $G(\mathcal{V},\mathcal{E})$ where $\mathcal{V}$ is set of vertices and $\mathcal{E}$ is the set of edges where each edge $(i,j) \in \mathcal{E}$ assigned a positive weight $w\_{ij}$. Matching is the subset of edges such that no two edges share a vertex. The maximum cardinality weighted matching is the matching that maximizes the total weight of edges in the subset of matching that maximizes the total number of edges chosen in the matching

I searched but there is always maximum weighted matching which means the matching has maximum weight but may not has maximum cardinality all the time. I appreciate it if you can recommend a reference for the maximum cardinality weighted matching. I want the matching that maximizes the cardinality first then the weigt of the matching.

For example, 1 --- 2 --- 3 --- 4

The weight between 1 and 2 is 1. The weight between 2 and 3 is 10. The weight between 3 and 4 is 1.

The maximum cardinality weighted matching I want is 1--2 and 3--4.

The maximum weighted matching outputs 3--4

# Answer
If you take $S$ to be the sum of all the weights on all the edges in the graph and you add $S$ to all the weights in the graph, then a regular maximum weight matching will find you the matching you are looking for, since now with the large weights on all the edges, it will prefer a matching that uses the most number of edges first.

In your example of 1--2--3--4 with weights 1, 10, 1, here we have $S=12$, so add 12 to all the edges to have edge weights of 13, 22, 13 and now a regular max weight matching would prefer 13+13 over 22.

I'm not sure if it is easy to prove that $S$ is quite big enough, but it should be easy to prove that $mS$ is big enough to all to all edges (that is, sum of all edges times the number of edges).
> 1 votes

---
Tags: combinatorics, matching
---


# Question
Title: Strong Uniform Total Order vs Weak Uniform Total Order
The definition for SUTO and WUTO is the following:

Suto

> If some process TODelivers some message m before message mʹ, then a process TODelivers mʹonly after it has TODelivered m.

And for WUTO

> If process p and process q both TODdeliver messages m and mʹ, then p TODelivers m before mʹ if and only if q TODdelivers m before mʹ.

I have a hard time getting my head around this. For me, both of them sounds the same...

Any help?

# Answer
Consider for example two processes $p\_1$ and $p\_2$, with $p\_1$ that delivers in this order $m$ and then $m'$.

In SUTO, $p\_2$ will either deliver $m-m'$ as $p\_1$ did, or it won't deliver $m'$ at all. But why?

Because if $p\_2$ will deliver, for example, $m - m'' - m'$, then every process can deliver $m'$ only after $m''$. This means that once $p\_1$ and $p\_2$ don't deliver the same messages, the following messages delivered by $p\_1$ and $p\_2$ must be disjoint.

In WUTO instead it's possible to have $p\_1$ that delivers $m - m'$ and $p\_2$ that delivers $m - m'' - m'$.

This example is taken from Baldoni, Cimmino and Marchetti, A classification of total order specifications and its application to fixed sequencer-based implementations.
> 1 votes

---
Tags: distributed-systems
---


# Question
Title: Is a language recursive? 2 wrong ways of solving
Let's define:
$Disagree(M\_1,M\_2) = \\{x| $The result of $M\_1$ on $x$ different from the result of $M\_2$ on $x\\}$

that means: if $M\_1$ accept, $M\_2$ reject and vice versa

$NPA=\\{L|\exists M\_1,M\_2$ Nondeterministic polynomial TM $ s.t. Disagree(M\_1,M\_2)=L\\}$

Is $NPA=R$?

I thought about this problem from 2 clashing ways:

1. If I choose $M\_1$ to accept any input and $M\_2$ to reject any input, for given $L$ each $x\in L$ will be $x\in Disagree(M\_1,M\_2)$ so $NPA=R$
2. To accept $L$, $M\_1$ and $M\_2$ should run on every $x\in L$ and even if it's a single step the input ($L$) is a countably infinite set, so it's impossible to run on all the $x\in L$, so $NPA\neq R$

When I saw the answer, I understood that both of my ways wrong, but I can't understand in which step?

# Answer
I'll assume that $R$ is the set of recursive languages and that in the definition of $NPA$ we are talking about Nondeterministic Polynomial Time.

1. You are just proving that, for $L \in R$, $L \subseteq Disagree(M\_1, M\_2)=\Sigma{}^\*$ which says nothing about $NPA = R$.
2. To **accept** a language $L$, there must be some machine $M$ such that for each string $x \in L$ the computation $M(x)$ halts in the accepting state and for each string $x \not\in L$ the computation $M(x)$ does not halt. To **decide** a language $L$, the machine must halt in all inputs and, furthermore, if $x \in L$ the machine halts in accepting state, otherwise the machine halts in rejecting state. That doesn't mean that the machine is "tested" simultaneously on an infinite number of strings.

That being said, when you want to prove that two sets are equal you need to prove that each one includes the other. When you want to prove that two sets are different, it is sufficient to find some language that is in one set but non the other.

In your case, the requirement that $M\_1, M\_2$ must halt in a polynomial number of steps is suspicious.

If $L \in NPA$, then there are Nondeterministic machines $M\_1, M\_2$ such that they both halt in a polynomial number of steps and disagree precisely on $L$. From those machines, you can construct a Nondeterministic machine $M\_{1,2}$ that decides $L$ in polynomial time, hence $L \in \mathcal{NP}$ and this proves the inclusion $NPA \subseteq \mathcal{NP}$ by generality of $L$.

By the Time Hierarchy Theorem, $$NPA \subseteq \mathcal{NP} \subsetneq \mathcal{N}EXP \subseteq R$$

Hence $NPA \neq R$.
> 1 votes

---
Tags: complexity-theory, formal-languages, turing-machines, computability
---


# Question
Title: How to make efficient path minimum queries in a tree?
Given a tree in which each node has a given value, I want to process "Path Minimum Queries": **given two nodes, what is the minimal value of any node on the shortest path between them?**

My original idea was to solve Least Common Ancestor Queries on any two nodes (using an Eulerian Tour Tree or the Binary Lifting Method), then to split any path into one or two vertical paths that pass through the LCA. After this, we could process the path minimum query on the vertical paths.

However, processing the path minimum query on a vertical path proved to be pretty hard: in path sum queries (finding the sum of all node values on a path), if we know the sum of all nodes from an ancestor to the parent of node A, and also the sum of all nodes from that ancestor to node B, then the sum of all nodes from node A to node B is just equal to the second value minus the first one. In Range minimum Queries, however, this does not work.

**Is there any efficient way to solve this problem? Am I missing something in my current approach?**

# Answer
You can preprocess your tree in time $O(n \log n)$ so to obtain a data that uses $O(n)$ space that can answer path-minimum queries in constant time. See "Bottleneck Edge Queries" in this paper which shows how to answer queries that ask for the edge of minimum weight in the unique path between two given vertices in a tree.

You can easily reduce your problem by splitting each edge into two edges and then setting the weight of each edge incident to a vertex $v$ of the original tree to the weight of $w$ itself.

If you are find with a solution that is easier to implement but requires $O(n \log n)$ space and preprocessing time (rather than the $O(n)$ space of the paper I liked above), and supports $O(\log n)$-time queries, then you can do the following:

Start by constructing a LCA oracle for $T$. To do so consider an Euler tour $E = \langle u\_1, u\_2, \dots u\_{m}\rangle$ of your tree and construct an array $A\[1 \dots m\]$ where $A\[i\]$ contains the depth of $u\_i$. Here $m=2m-2$. Then construct a range minimum query (RMQ) oracle on $A$, so that the LCA $u\_k$ between $u\_i$ and $v\_j$ with $i\<j$ is such that $k$ is the index of the minimum $A\[k\]$ in $A\[i\], \dots, A\[j\]$.

A simple RMQ oracle is the following: for each index $i$ of $A$, and for each $j=0, 1, \dots, \lfloor \log m \rfloor$, store in $B\[i, j\]$ the index $k$ of the minimum $A\[k\]$ between $A\[i\], \dots, A\[i+2^j-1\]$. All the entries of $B$ can be found in $O(n \log n)$ time since, for $j\>0$, $B\[i,j\]$ is either $B\[i, j-1\]$ or $B\[i + 2^{j-1}, j-1\]$.

The answer to a RMQ query $(i,j)$ is then the index of $A$ with the minimum value among the two indices $B\[i, \Delta\]$ and $B\[j- \Delta, \Delta\]$, where $\Delta=\lfloor j-i+1 \rfloor$.

We are now able to find the LCA $w$ of two vertices $u$ and $v$ in constant time. Then your problem reduces to the one of finding the vertex of minimum weight in two ancestor-descendant paths, namely those between (i) $w$ and $u$, and (ii) $w$ and $v$.

This can be done using a trick similar to the previous one: For each vertex $z$ at depth $d$ maintain $\delta = \lfloor \log d \rfloor$ values $M\[z, 0\], \dots, M\[z, \delta\]$, where $M\[z, j\]$ is the minimum among the weights of the vertices $z= z\_1, z\_2, \dots, z\_{2^j}$ encountered by walking from $v$ towards the root for $2^j - 1$ steps. Moreover, for each vertex $v$, we explicitly store the $O(\log n)$ vertices $z\_{2^j}$.

As before, all the values $M\[z,j\]$ can be found in $O(n \log n)$ time and a path query on an ancestor-descendant path of length $L \ge 2$ can be answered by letting $\ell = \lfloor \log L \lfloor$ and selecting the minimum among $M\[z, \ell\]$ and a recursive query for the path of length $L - 2^\ell$ that ends with $z\_{2^\ell}$.

The query time can actually be improved to $O(1)$ if you additionally compute a long-path decomposition of your tree. The long path decomposition is defined recursively and is obtained by selecting the longest root-to-leaf path $P$, deleting (the edges and vertices of) $P$ from the tree and returning the union of $P$ with all the long-path decompositions of the trees in the resulting forest.

This decomposition can be found in $O(n)$ time and has the following property: given a vertex $v$, the (unique) path $P\_v$ that contains $v$ has a lenght |P\_v| not smaller than the height of the subtree rooted in $v$.

Let $P\_1, P\_2, \dots$ be the paths of the decomposition and for each $P\_i$ construct an array $P'\_i$ by extending $P\_i$ by $|P\_i|$ edges towards the root, and writing down the vertex weights along this extended path. Build a RMQ oracle on each of the obtained arrays and, for each $v$, keep a reference to the position of $v$ in the (unique) array associated with the path $P'\_v$ such that $v$ is contained in $P\_v$. The total size of the arrays is $O(n)$ and hence the total size of the RMQ oracles is $O(n \log n)$.

A query on an ancestor-descendant path can now be answered in $O(1)$ time by first looking at $M\[v, j\]$ and a then querying the oracle associated with $P'\_{z'}$, where $z'=z\_{2^\ell}$. This is because $L-2^\ell \< 2^\ell$ (by the choice of $\ell$), showing that $P\_{z'}$ has length at least $2^\ell-1$, and hence all the remaining $L-2^\ell$ proper ancestors of $z'$ (that were not already considered in $M\[v, j\]$) must be in $P'\_{z'}$.

There is a great paper explaining this technique that combines the lookup table $M$ with this extended path-decomposition. With some additional work you can even get rid of the $O(\log n)$ factor in the space complexity.
> 2 votes

# Answer
We consider a tree `T` where `T[v]` is the parent of `v` for any node `v`. A value `x[v]` is associated to each node `v`. I also assume that the depth of each node `v` is precomputed, and given by `depth[v]`.

Let `u` and `v` the two queried nodes. We are looking for the smallest value `x[w]` for any `w` on the shortest path between `u` and `v`. There may be faster algorithms, but I give one that is linear in the length of this path.

Let us initialize `r` to `min(x[u],x[v])`, `u'` to `u`, and `v'` to `v`. While `u'` is not equal to `v'`, iterate the following: if `depth[u']> depth[v']`then set `u'` to `T[u']`, otherwise set `v'` to `T[v']`; and, in both cases, set `r` to `min(x[u'],x[v'])`. The result is the final value of ̀`r`, if I am correct.
> 0 votes

---
Tags: algorithms, graphs, trees
---


# Question
Title: Local to global algorithms in gossip based P2P networks
Suppose we have a peer to peer network of, say, $n$ peers. Peers communicate by an asynchronous randomized gossip protocol (Push, Pull, Push/Pull doesn't really matter here). The task is for any local peer to get an (approximate) picture of the global communication in all of the network over time.

I mean after some time $t\_1$, each local peer $k$ should have a data structure that is the record of every gossip event that took place in all of the network up to a time $t\_2$, with $t\_2\leq t\_1$. This data structure should provide knowledge about the appearance of events globally over space and time.

To make it "simple", we can assume, that communication channels never fail. Every peer can reach every peer. However since peers might crash or disappear, we can not just choose some central peer that records everything and then redistributes its knowledge.

A solution exist in the so called hashgraph algorithm, which goes roughly as follows:

Every peer stores locally a directed acyclic graph, to record the gossip events. Vertices are the gossip event together with an identifier of sender and receiver. Each vertex has two incoming edges, which might be called $sender\\\_parent$ and $receiver\\\_parent$. $sender\\\_parent$ is an edge from the previous gossip event of the sender and $receiver\\\_parent$ is an edge from the previous gossip event of the receiver. Outgoing edges are of arbitrary number.

Each time a peer connects to another peer it askes for the previous gossip event of the receiver, then creates a new vertex locally to record \*this event. Then it transfers all of the graph along to the other peer. (This is a simplification for the push protocol and can be tweaked appropriately for pull or push/pull as well)

The question now is, whether or not this is essentially (up to isomorphism) the only way to do it. The hashgraph algorithm is patented. Therefore it would be good to know if other solutions exist. With such local to global views, network analysis can be quite efficient.

---

Edit: The system is free to implement any kind of communication contend, which makes the task possible.

# Answer
> 1 votes
Another solution would be to use SWIM gossip (**S**calable **W**eakly-consistent **I**nfection-style Process Group **M**embership Protocol), or it derivatives like Serf (which includes the vivaldi network and SWIM) or even Consul (which implements raft consensus, key value store, and Serf).

---
Tags: algorithms, graphs, computer-networks, peer-to-peer
---


# Question
Title: For all oracles A, If $P^A \neq PSPACE^A$, then Does it imply that $P \neq PSPACE$?
My question related to relativized world. I would like to know about how to show that class is different from another class in the oracle world and whether this applied to our real world.

For example, let us have the following assumption: suppose for all oracles A we have $P^A \neq PSPACE^A$, then Does it imply that $P = PSPACE$?

# Answer
> 2 votes
If $A = \emptyset$, or more generally, if $A \in \mathsf{P}$, then $\mathsf{P}^A = \mathsf{P}$ and $\mathsf{PSPACE}^A = \mathsf{PSPACE}$, and so $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ is the same as $\mathsf{P} \neq \mathsf{PSPACE}$.

It is also interesting to ask whether $\mathsf{P}^A \neq \mathsf{PSPACE}^A$ for a *random* oracle implies $\mathsf{P} \neq \mathsf{PSPACE}$. This was disproved (with $\mathsf{P}$ replaced by $\mathsf{IP}$) by Chang, Chor, Goldreich, Hartmanis, Håstad, Ranjan, and Rohatgi in their paper The random oracle hypothesis is false.

---
Tags: complexity-theory, oracles
---


# Question
Title: Counting letter frequency in array in O(1) with hash function
I want to calculate the frequency of each character in an array. (e.g \['a', 'b', 'o', 'p'\]

There are several ways to do this:

* A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ space
* Sorting the array first and serial counting the characters is a better solution with $O(n \log n)$ time and $O(n)$ space
* But the optimal solution is... using hash tables with $O(1)$ access time. The thing is, I do not quite understand why the complexity is supposed to be $O(1)$ and not $O(n)$. After all, we still have to iterate over the array. For example

```
def fCount(A):

  frequencies = new hashTable()

  for character in A: // This is O(n) !!!
      frequencies(character) += 1

```

Yes, the access time is $O(1)$ but in order to create the hash table, you still need $O(n)$ time and space.

So why is this supposedly $O(1)$ time and $O(1)$ space?

# Answer
> 3 votes
The complexity is $O(n)$. What is $O(1)$ is the time it takes to access a cell in the hash table.

By the way, assuming that each character is a byte, you can just use a plain old array of length 256.

---
Tags: complexity-theory, time-complexity, asymptotics, space-complexity, hash-tables
---


# Question
Title: OS: Are User-level threads and software threads (and also kernel-level threads and hardware threads) the same?
I am referencing the Book Fundamentals of Computer Algorithms" by Ellis Horowitz et al.

At the part which they talk about multi-threading models, user-level and kernel-level thread are introduced.

And at the scheduling chapter, under multi-core processors, they talk about software threads and hardware threads.

Even though both sections are titled 'multithreading', one deals with how user-threads are mapped to kernel threads and the other deals with hyperthreading. (correct me if I am wrong)

I just want to know whether they are talking about the same terms. If not, will you clarify *what is the difference between User-level threads vs software threads*?

Thank you.

# Answer
> 0 votes
Kernel threads and user threads are both software threads. This is only terminology, but I think that hardware threads in your book are the actual CPU cores including hyperthreading threads that the CPU can run at once. So a hardware thread is not instructions or an actual thread, it is simply the threads that the CPU supports. For example, if the CPU has 4 cores and each core uses hyperthreading to have 2 virtual threads each, then you would have 8 hardware threads available for software threads to run.

Kernel threads and user threads are separated by a permission bit in the page tables. Having a thread with a permission of 0 (kernel thread) doesn't make the thread a hardware thread. It is simply a software thread running in kernel mode.

---
Tags: operating-systems, process-scheduling, threads, os-kernel
---


# Question
Title: Analyzing the Runtime of Shuffling Algorithm
The following is psuedocode used to shuffle the contents of an array $A$ of length $n$. As a subroutine for shuffle, there is a call to *Random*$(m)$ which takes $O(m^2)$ time for an input $m$. Determine the runtime of the following algorithms.

**Algorithm 1:**

```
function Shuffle(A)
Split A into two equal pieces A, and B (this takes constant time)
A = Shuffle(A)
B = Shuffle(B)
for i = 0 to len(A)/2 − 1:
        for j = 0 to i − 1 do:
            B[j] = B[j] − A[i] + Random(10)
            A[i] = A[j] − B[i] + Random(10)
B = Shuffle(B)
A = Shuffle(A)
Combine A = A + B (this takes constant time)
return A

```

**Algorithm 2:**

```
function Shuffle1(A)
for i = 0 to len(A) − 1:
    for j = 0 to i − 1:
        for k = 0 to j − 1:
            A[k] = A[k] + A[j] + A[i] + Random(m)
return A

```

After a good amount of work, I believe that the runtime for *Shuffle1*$(A)$ to be $O(n^3 \cdot m^2)$ as there are three nested loops. In the innermost loop, the algorithm does the constant time array access and $O(m^2)$ work done. But, I am not quite sure. I am having difficulty tackling the runtime of *Shuffle(A)*. Should I be using the Master Theorem in any way? Any advice and help would be greatly appreciated!

# Answer
You are right about the running time of the second algorithm, i.e., *Shuffle1*$(A)$. Its running time is indeed $O(n^{3} \cdot m^2)$.

To analyze the running time of the first algorithm, i.e., *Shuffle*$(A)$, you can formulate the recurrence relation as follows:

$$T(n) = 4 \cdot T(n/2) + O(n^2)$$

Note that, *Random(10)* takes time $O(10^2) = O(1)$.

You can indeed solve this recurrence using the Master Theorem. The theorem gives $T(n) = O(n^{2} \log n)$ by applying Case $2$ of the theorem.

---

You can also solve the recurrence by the expansion method as described below:

$$ \begin{align} T(n) &= 4 \cdot T(n/2) + O(n^{2}) \\ &= 4 \cdot (4 \cdot T(n/4) + O(n^{2}/4)) + O(n^{2}) \\ &= 4^{3} \cdot T(n/8) + 4^{2} \cdot O(n/4^{2}) + 4 \cdot O(n^{2}/4) + O(n^{2}) \\ & \quad \\, \textrm{... on further expansion we get the following relation} \\ &= 4^{t} \cdot T(n/2^{t}) + \sum\_{i = 0}^{t} 4^{i} \cdot O(n^{2}/4^{i}) \\ \end{align} $$ When $t = \log n$, the value $T(n/2^{t})$ becomes $T(1)$. I am assuming that $T(1) = 1$ for the base case of your algorithm. (ttnick is asking the same question in the comment section also). Based on this assumption, we get the following relation:

$$T(n) = (4)^{\log n} \cdot 1 + \sum\_{i = 1}^{\log n} O(n^{2}) = n^{2} + \sum\_{i = 1}^{\log n} O(n^{2}) = O(n^2 \log n)$$.
> 1 votes

---
Tags: algorithms, runtime-analysis, big-o-notation
---


title: What is congruence in lambda-calculus

text:
# Question
Title: What is congruence in lambda-calculus
I see a lot of lecture notes where they use the term "congruence" (ex: congruence relation) or deriving usages such as "the expression e is alpha-congruent to e2".

Could someone please explain what congurence means exactly in this context and give some examples to a noob without much knowledge about math/lambda-calculus.

Thanks in advance

# Answer
"Congruence" in the context of lambda calculus is usually "alpha-congruence". "alpha-congruent" means "differring only if at all in the names of bound variables".

For instance, $\lambda x. x \equiv\_\alpha \lambda y.y$ and $\lambda xy.x(xy) \equiv\_\alpha \lambda yx.y(yx)$ (bound variables $x$ and $y$ were swapped), but $\lambda x.x \not \equiv\_\alpha \lambda x.xy$ (different term structure).

Formally,

$P\[\lambda x.M\] \equiv\_{1\alpha} P\[\lambda y.M\[y/x\]\]$

where $P\[\lambda x.M\]$ means that $\lambda x.M$ is a subterm in $P$, $y$ is a new variable that does not occur free in $M$, and $M\[y/x\]$ is the result of substituting every occurrence of $x$ with $y$ in $M$;

$P \equiv\_\alpha Q \text{ iff } P = P\_1 \equiv\_{1\alpha} \ldots \equiv\_{1\alpha} P\_n = Q$

i.e. $P$ is alpha-congruent to $Q$ if there is a chain of bound variable renamings from $P$ to $Q$.

The idea is that alpha-congruent terms "mean" the same, because the choice of names for bound variables does not affect a term's behavior in abstraction and application.
> 2 votes

# Answer
Generally speaking, in algebra, a congruence relation is an equivalence relation such that operations on equivalent objects yield equivalent objects. In the lambda calculus, a congruence is an equivalence relation such that constructing terms from equivalent terms yields equivalent terms: if $M \equiv M'$ and $N \equiv N'$ then $M\\,N \equiv M\\,N'$, and if $M \equiv M'$ then $\lambda x.M \equiv \lambda x.M'$.

“Alpha congruence” is another name for alpha equivalence, which is the relation such that two terms are alpha-equivalent if they are, intuitively speaking, the same except for renaming internal variables. Since this is not only an equivalence but even a congruence, it's called both “alpha equivalence” and “alpha congruence”.
> 6 votes

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


# Question
Title: Resources about implementing a database table
I'd like to understand more how data can be stored on disk so it can be read quickly. I don't want to say database record because I'm not asking how to build a database. My question is closer to how would I build a table.

I'm not asking about indexing. I'm thinking about you have an application that already has some a pointer to a record.

I've been trying to find some references e.g. papers, books, but everything so far focuses on database design as in writing DDL or structures for indexing like B+ trees.

Are there any references that talk about how tables are actually implemented and what are the tradeoffs?

# Answer
Databases have some issues that "mere mortal" data storage doesn't concern itself with, such as transaction safety and disk failure.

Here are a few classic papers on the topic:

There are also some good books that cover the relevant topics, such as *Database System Implementation* by Garcia-Molina, Ullman, and Widom.
> 1 votes

---
Tags: data-structures, database-theory, databases
---


# Question
Title: AI Search - State in the toy vacuum problem
I have been reading about AI search, specifically the toy vacuum cleaner problem and I would like to code an example of this but I am finding the description of the state hard to get my head around.

The problem states that the AI needs to be able to move between squares, either left or right and if there is dirt in the square it can clean it (suck).

Is the state something you are supposed to hard code in advance in AI search? This seems unlikely due to the possible number of potential states for a larger problem, so I am not sure how I can represent the state in a problem like this, or any other really.

In the vacuum problem the states are 'dirt left', 'dirt right' and 'vacuum position' and an action such as 'move left', 'move right' or 'suck' will leave the problem in a new state but how do you represent these changes?

Would state be an object with boolean properties for the dirt and an int value for the vacuum position of either 0 or 1 depending on which array element it is looking at?

In the context of a map program trying to get to somewhere I do understand the state might be `In(New York)` but I what I am struggling with is how I would represent something like that in code, or perhaps a maze where the current state might be the x, y coordinate of the square the agent is currently in, again would an object be the right thing to use to model state?

# Answer
"State" is the sum of all information that describes the current situation of the robot, and everything about that past that might be relevant. I don't understand your diagram so I can't tell you what it is specifically in your particular example, but it appears that the state includes the current location of the vacuum and which locations currently have dirt. So, you might have one variable that defines where the robot is located, one variable that indicates whether there is dirt in the left room, and one variable that indicates whether there is dirt in the right room.

In AI search, we often assume that we know the set of all possible states and all ways to transition between them. We give that information as input to the search algorithm, and it finds a way to reach a desired state from where we currently are.
> 0 votes

---
Tags: artificial-intelligence, search-problem
---


# Question
Title: Single tape Turing Machine that accepts string with at least five G's and at most three T's?
I am looking to create a single tape acceptor Turing machine acting upon the language of any ASCII string, that would only accept strings that contains **at least** five G's and **at most** three T's, and rejects any other ASCII string input. I am kind of stuck on how the machine would know that it had encountered greater than or equal to five G's **and** less than or equal to three T's.

# Answer
> 3 votes
In general, whenever you try to design a machine accepting a language with this kind of "finite conditions", the easiest solution is to hard-code those conditions directly into the states of your machine.

Here, you would have 24 "counting" states, labelled by $(g, t)$ for $0 \leq g \leq 5$ and $0 \leq t \leq 3$. Whenever you read some $G$ while already in state $(g, t)$, you move on to the corresponding state $(g+1, t)$ (and if you read a $T$, you go to $(g, t+1)$). Otherwise, you simply loop on your current state.

Now, you have to enforce your conditions: if you read a $T$ while in a state $(g, 3)$, you reject the word, and if your word end while you are in a state $(g, t)$ with $g \< 5$, you reject too.

Of course, there is probably some technical details to work out precisely, and there might exist some clever and trickier ideas to do this, but this method is easy to understand and can be immediately generalised to all the problems of this kind.

---
Tags: turing-machines
---


# Question
Title: How to create a subset with a given length and mean?
I have a set of numbers $P=\\{p\_1,\dotsc,p\_{|P|}\\}$, where $|P|$ is the length of the set. I want to select a subset, $S$, from $P$ such that its mean is approximately equal to a predefined value $\mu\_s$ .

$$\sum\_{x \in S} x \approx \mu\_s * |S|$$ My problem:

* $|P|$ = 5000
* $|S|$ = 1500
* $\mu\_s$ $\approx$ 90 $(target$ $mean)$
* $\mu\_p$ = 95
* $min(P)$ = 0
* $max(P)$ = 300

I am looking for algorithm suggestions so I can implement this in Python. I would also like $S$ to include a range of values, rather than just the naive approach of sorting from smallest to largest first, then applying a greedy algorithm.

Additional question is whether dynamic programming could be used for this type of problem (i.e. we have to select a certain number of items from a list such that the sum is as close as possible to the capacity limit)?

# Answer
> 1 votes
For every $i \in \\{0,\ldots,|P|\\}$, $j \in \\{0,\ldots,|S|\\}$, and $T \in \\{0,\ldots,\mathcal{T}\\}$ (I discuss $\mathcal{T}$ below), compute whether there is a subset of size $j$ of $p\_1,\ldots,p\_i$ which sums to $T$. You should take $\mathcal{T}$ to be your maximum allowable answer – $\max(P) \cdot |S|$ would definitely do, but you can probably pick something which is closer to $\mu\_S |S|$, say $\mu\_P |S|$. The running time is $O(|P| |S| \mathcal{T})$. In your case, assuming you choose $\mathcal{T} \approx \mu\_p |S|$, then $|P| |S| \mathcal{T} \approx 2^{40}$, so this is barely feasible.

This is a naive dynamic programming algorithm, which probably can be improved, especially since you're only looking for an approximation.

For example, you could only look for solutions such that $S \cap \\{0,\ldots,i\\} \approx \frac{|S|}{|P|} i$ and $\sum(S \cap \\{0,\ldots,i\\}) \approx \frac{|S|}{|P|} \mu\_S$, which will reduce the running time significantly. While this is only a heuristic, it might be possible to show that you get a decent approximation on average, if you randomize the order of $P$.

Another possible optimization is to quantize the partial sums, quantizing more aggressively as $i$ gets larger. If done carefully, you won't lose much in accuracy but will have a significant gain in running time.

---
Tags: dynamic-programming, knapsack-problems, python
---


# Question
Title: Group time series events into minimal amount of buckets
I'm trying to efficiently compute events in a time series by grouping them into buckets. My goal is to have as few buckets as possible. The constraint is that events within one bucket are all within a 30 minute time window.

To get more concrete, let's assume I've got these events:

| time | event |
| --- | --- |
| 15:15 | 1 |
| 16:58 | 2 |
| 17:13 | 3 |
| 17:21 | 4 |

A naive approach to group those events into 30 minute intervals would result in these 3 buckets

```
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:30-17:00 – event 2
bucket 3: 17:00-17:30 – event 3,4

```

A better solution with fewer buckets is possible though:

```
bucket 1: 15:00-15:30 – event 1
bucket 2: 16:58-17:28 – event 2,3,4

```

What kind of algorithm do I need to look for to efficiently find the fewest amount of buckets for this kind of data?

I'd prefer a fast solution (i.e less than $O(n^2)$) over an optimal one.

# Answer
The first event at time $t\_0$ needs to be in a bucket. We can safely choose the bucket $\[t\_0, t\_0+30\]$, as there is nothing to gain by making it start earlier. We then move on to the next event starting at $t\>t\_0+30$ (earlier events fall into the bucket we chose). We once again choose the latest bucket containing that event. It is not hard to prove that repeating this strategy until all events are covered is optimal (you can do it by induction).

This procedure runs in $O(n)$ time if your events are sorted, $O(n\log(n))$ if you need to sort them first.
> 4 votes

---
Tags: algorithms, clustering
---


title: Optimal pairing of points in a set

text:
# Question
Title: Optimal pairing of points in a set
I have an even number of points, each with coordinates $(x, y, z)$. I need to group these points into pairs. The cost of pairing two points is the Euclidean distance between them. I'd like to find the optimal pairing such that the total cost is minimized. What would be a good way/algorithm to solve this?

For example, if you have points $\\{a, b, c, d\\}$, one possible pairing might be $\\{a,d\\}, \\{b,c\\}$. Points can only belong to a single pair.

**My Ideas:**
The problem seems similar to finding the minimum weighted bipartite matching for a graph. However, I'm not trying to match between two sets of points, just find pairs in a single set. It seems like you might be able to convert this problem to a bipartite graph by duplicating the set of points. This doesn't seem like the right way to do it though (seems like you'd be solving for each pair twice).

You could solve it using an algorithm for weighted matching on general graphs. Just convert the set of points to a complete graph (drawing edges between all possible pairs). It doesn't seem like those algorithms were designed to solve this kind of problem, though (I could be wrong though). So I can't help but wonder if there is a better way to do it.

# Answer
This problem is the 3-dimensional variant of the *Euclidean min-cost perfect matching* problem (MCPM), and I don't know if it has been studied. The general problem (min-cost maximum-cardinality matching) can be solved in time $O(\sqrt n \cdot m )$ \[^1\].

However, the 2-dimensional version can be solved in time $O(n^{3/2} \log^5 n)$. Reading the article by Varadarajan \[^2\], I cannot see any issues lifting the result to 3-dimensional points.

\[^1\] Micali, Silvio, and Vijay V. Vazirani. "An $O(\sqrt{|v|} \cdot |E|)$ algorithm for finding maximum matching in general graphs." 21st Annual Symposium on Foundations of Computer Science (sfcs 1980). IEEE, 1980.

\[^2\] Varadarajan, Kasturi R. "A divide-and-conquer algorithm for min-cost perfect matching in the plane." Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No. 98CB36280). IEEE, 1998.
> 1 votes

---
Tags: optimization, matching
---


# Question
Title: is it possible to create an avl tree given any set of numbers?
I am studying balanced trees, especially AVL trees. My question is whether is it possible to create an avl tree given any set of numbers. is it possible to prove the following statement?

> Let $A$ be the set of integers. Given any set $A$, it's possible to create an avl tree corresponding to the given set of numbers.

Is there any way to prove or work out the above statement? I appreciate your answers.

# Answer
> 3 votes
Your question is not the right one.

An AVL tree is a binary tree that has additional properties. First it is a search tree, which means we can easily find each number in the tree. Second it is balanced, meaning that there are no leafs very far form the root. (Formal definitions on request.)

Assume you have a set of $n$ numbers in advance, and an arbitrary "empty" binary tree with $n$ nodes, you can make the tree into a search tree putting the nodes at a well defined position. So, If you can find an empty tree with AVL structure it is no problem to fill it with the values. And indeed, a completely balanced binary tree, adding nodes level by level, satisfies the requirement of AVL trees.

The proper question is: "*can we keep a binary tree in AVL form when the values are added and deleted one by one*". When we can do this we have build a quite efficient data structure for sets of values.

# Answer
> 3 votes
AVL trees are a kind of binary search trees. As such, they implement the following operations, among else:

* Initialize an empty tree.
* Add a value to the tree.
* Remove a value from the tree.
* Search a value in the tree.

Try to use some of these operations to answer your question.

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


title: Minimal DFA for $1\Sigma^*0$

text:
# Question
Title: Minimal DFA for $1\Sigma^*0$
What is the minimum number of states required in any DFA to accept the regular language $L$ over $\Sigma=\\{0,1\\}$ which accepts those strings that start with 1 and end with 0?

# Answer
Let $\mathcal{A} = \langle \Sigma, Q, q\_0, \delta, F\rangle$ be a DFA for $L$. Then, note that the $|Q|\geq 4$. Indeed, the states $q\_0, \delta(q\_0, 0), \delta(q\_0, 1)$ have to be distinct, and clearly all of them are rejecting (can you tell why they're rejecting?) and thus as there are words in $L$, we know that there has to be at least one additional accepting state. To see why the later states are distinct, note that we have:

* from $q\_0$ you can get to an accepting state, and from $\delta(q\_0, 0)$ you cannot get to an accepting state. Hence, $q\_0$ and $\delta(q\_0, 0)$ are distinct.
* from $\delta(q\_0, 1)$ you can get to an accepting state, and from $\delta(q\_0, 0)$ you cannot get to an accepting state. Hence, $\delta(q\_0, 1)$ and $\delta(q\_0, 0)$ are distinct.
* from $\delta(q\_0, 0)$ you cannot get to an accepting state, and from $\delta(\delta(q\_0, 1), 0)$ you can get to an accepting state. Hence, $q\_0$ and $\delta(q\_0, 1)$ are distinct.

Now you can actually, build a DFA for L consisting of exactly 4 states. You can start from what we already know: the above three states are rejecting, and the 4'th additional state have to be accepting. So you only need to add the transitions between the 4 states properly.
> 2 votes

# Answer
*The following answer assumes that each state in a DFA must contain an outgoing edge for each symbol. Otherwise, you might need one state fewer.*

Let us say that two words $x,y$ are *equivalent* modulo $L$ if for any word $z$, either both $xz$ and $yz$ are in $L$, or both of them are not in $L$.

If two words $x,y$ are *not* equivalent modulo $L$, and $A$ is any DFA accepting $L$, then the state of $A$ after reading $x$ must be different from the state of $B$ after reading $y$ (why?).

As a consequence, if $x\_1,\ldots,x\_n$ is a collection of words, any two of which are not equivalent modulo $L$, then any DFA for $L$ must contain at least $n$ states.

(Furthermore, it is known that if the minimal DFA for $L$ contains $n$ states, then we can find $n$ such words: for each state, we take some word leading to it; but we don't need this direction here.)

In your case, the following words are pairwise inequivalent: $\epsilon, 0, 1, 10$. To show this, we need to consider all six pairs:

* $\epsilon,0$ are inequivalent since $10 \in L$ but $010 \notin L$.
* $\epsilon,1$ are inequivalent since $0 \notin L$ but $10 \in L$.
* $\epsilon,10$ are inequivalent since $\epsilon \notin L$ but $10 \in L$.
* $0,1$ are inequivalent since $00 \notin L$ but $10 \in L$.
* $0,10$ are inequivalent since $0 \notin L$ but $10 \in L$.
* $1,10$ are inequivalent since $1 \notin L$ but $10 \in L$.

This shows that every DFA for $L$ contains at least $4$ states. Conversely, there is a DFA for $L$ containing $4$ states, which I will let you figure out.
> 4 votes

# Answer
The minimal DFA is attached. Here, q0 is the initial state and q2 is the final state.
> -2 votes

---
Tags: finite-automata
---


# Question
Title: Correctness proof of the algoritm to generate permutations in lexicographic order
The following algorithm generates the next permutation lexicographically after a given permutation. It changes the given permutation in-place.

1. Find the largest index k such that a\[k\] \< a\[k + 1\]. If no such index exists, the permutation is the last permutation.
2. Find the largest index l greater than k such that a\[k\] \< a\[l\].
3. Swap the value of a\[k\] with that of a\[l\].
4. Reverse the sequence from a\[k + 1\] up to and including the final element a\[n\].

(from https://en.wikipedia.org/wiki/Permutation#Generation\_in\_lexicographic\_order)

I would like to know a (possible formal) proof.

# Answer
> 3 votes
One can try to come up with the algorithm by oneself (thereby proving its correctness) after incremental understanding of: (a) how to define a permutation as "larger" (lexciographically) than another one, (b) what really the very next permutation of $P$ "looks like" compared to $P$ (how/where it differs from $P$). Once we find-out some properties, we may be able to write this algorithm ourselves.

Some outline:

1. define the "lexicographic order" of permutations $P\_1$ and $P\_2$. Say, $k$ is the very first index at which they differ. Then the "order" of their elements at index $k$ decides the "lexicographic order" of $P\_1$ and $P\_2$.
2. So what should be the smallest and largest permutation of array $a$ ?
3. Suppose array $a$ currently holds permutation $P$. Say $P'$ is the very next permutation of $P$ in the lexicographic-order, and they first differ at index $k$. Now, use the definition in (1) and the observation in (2) to find out what is the structure of elements in $P/P'$ at index $k$ and after it. You can argue that:

* elements in $P$ after $k$ must form a decreasing-sequence (call it $S$).
* element in $P$ at $k$ must be smaller than the largest element of $S$, which is $a\[k+1\]$.
* due to above, we must have an element $a\[l\]$ in $S$ which is the smallest element in $S$ larger than $a\[k\]$. In $P'$, this element must appear at index $k$.
* so the remaining (after $k$) elements of $P'$ are simply $S$ with $a\[l\]$ removed and $a\[k\]$ added.
* these remaining (after $k$) elements of $P'$, must be in increasing order (for $P'$ to be the smallest possible, but larger than $P$). The 4th step in the posted algorithm is simply obtaining this increasing order by reversing the existing decreasing-sequence $S$ (now modified via swap, but continues to remain decreasing).

For further details, refer to section "Lexicographical Order" in this article (written by me).

---
Tags: correctness-proof, permutations
---


# Question
Title: Fair assignment of storage for multiple writers (load balance)
I'm trying to optimize a system with a better algorithm for allocating storage. The system has 'N' writer processes and 'M' disks. (N \< 30, M \< 10. N can change, M is constant).

Any process can write to any disk and each process regularly writes a file every, say, 5 minutes, but the size of the file can be quite different. Each writer independently "chooses" which disk it writes to on a file-by-file basis; so it might write one file to Disk 2 and the next file a few minutes later to disk 8. There is no communication between writers.

This goes on forever.

In the steady state, all disks are "full" and a "deleter" process continuously deletes the oldest files until all disks are no longer "really full". (there are two water marks: "almost full" and "really full", if that helps), so the "deleter" wants:

```
        Almost Full    Really Full
Disk 1       Y             N
Disk 2       Y             N
Disk 3       Y             N

```

I need to optimize how the writer chooses which disk to write to such that, as much as possible, different writers are writing to different disks. This is important to balance I/O load.

I had thought this wouldn't be too hard, but the more I think of it, the more problems arise. I've tried a number of things:

* Randomly choose disk from those with free space. **However** since there aren't many disks (M is small), there is a good chance all writers will choose the same destination disk and overload the I/O system. Bad.
* Index/hash the writer number across the list of disks with free space. So if N == M, Writer 1 always ends up writing to Disk 1. **However** this fights with the deleter working to maintain free space by deleting the oldest files: eg, the first disk gets full but the oldest file is on a different disk.
* Use first free disk. **However** this ends up with all writers writing to the same disk.

# Answer
There are multiple solutions to this problem:

1. Consistent hashing with bounded loads
2. Generic Bin packing algorithm(Knapsack or other)

Both require that the writer know the free storage amount of the drives.

Consistent hashing with bounded loads is based on the consistent hashing algorithm published by akamai and fixed the issue of load inbalancing by overflowing across the ring to the next free "bin".
> 1 votes

---
Tags: assignment-problem, storage
---


# Question
Title: How to find all topological sortings of a special DAG in O(N^2)
I came across the following question in a hackerrank competition, which is based on topological sorting of a DAG.

https://www.hackerrank.com/contests/hourrank-29/challenges/birthday-assignment/forum

Problem description:

> Nikita has a family tree $T$ consisting of $N$ members number from $1$ to $N$. Each of the $N-1$ edges in the tree represents a directed relationship. Basically if there is an edge from member $A$ to $B$, it means $B$ was born before $A$. Now, Nikita knows that these $N$ members were born in last $M$ days and only $1$ person was born on a single day, She is interested in calculating the number of ways to assign birthdays to each of the $N$ family members.
>
> Since the required answer can be quite large, print it modulo $10^9+7$.

**Editorial:**

> By now, you might have got the problem is all about finding the number of topological sortings in the randomly directed tree $T$.
>
> Let randomly root the tree $T$ at any node say $1$. Lets calculate a $dp(i, j)$ denoting the number of topological sorts of subtree rooted at $i^{th}$ node such that $i^{th}$ node is placed at position. Assume that there are $X$ outgoing edges to the children from and $Y$ incoming edges. Note that all the $X$ children has to be placed on the left and all the $Y$ children has to be placed on the right side of $i^{th}$ in a valid topological sort.
>
> Now lets calculate another $dp(i, j)$ for those $X$ nodes. Similiarly, we will do for $Y$ nodes. Here $dp(i, j)$ denotes the number of ways of filling $j$ spaces using topological sorts of subtrees rooted at $X\_1, X\_2, \cdots X\_i$ such that $X\_1, X\_2, \cdots X\_i$ is placed in $j$ spaces. Note that to compute this $dp$, we can use the $DP$ already calculated at these children nodes.
>
> $$dp(i, j) = \sum\_{1 \le k \le |S\_i|} \left( nCr(j, k) \times dp(i-1, j-k) \times \sum\_{1\le l \le k} DP(i, l) \right)$$
>
> Note that this $\sum\_{1\le l \le k} DP(i, l)$ is just a prefix sum and can be precomputed.
>
> Now, for $X$ nodes basically you have computed $dp\_j$, number of filling up $j$ spaces using subtrees of $X$ nodes such that $X\_1, X\_2, \cdots X\_x$ is included. Lets call this $dp$ as $left\[\]$ and similary call the $dp$ for $Y$ nodes as $right\[\]$.
>
> $$DP(i, j) = \sum\_{1\le k \< j} nCr(j-1, k) \times {left}\_k \times nCr(a, b) \times {right}\_{a-b}$$
>
> Where $a = SZ\_i - j$, $b = SZ\_x - k$ and $SZ\_i$ denotes the size of subtree rooted at $i^{th}$ node & $SZ\_x$ denotes the sum of sizes of all subtrees rooted at all those $X$ nodes.

In the editorial section, it is claimed that the time complexity of the solution is $O(N^2)$. However, the problem is actually about finding all the topological sortings of a DAG, which to my knowledge is a NP-hard problem.

I believe that the added constraint that the number of edges is equal to $N-1$ simplifies the solution, and I couldn't think of any other possibility.

Could anyone kindly validate the solution?

# Answer
> 2 votes
First, the problem is about **counting**, not **finding**, all the topological sorts (though it is still hard for general DAGs). Second, the constraint that the graph is a tree makes this problem much simpler.

Consider a node $n$ with $k$ children $n\_1,\ldots,n\_k$. Suppose the subtrees rooted by $n\_1,\ldots,n\_k$ are respectively $T\_1,\ldots,T\_k$, the sizes of $T\_1,\ldots,T\_k$ are respectively $s\_1,\ldots,s\_k$, and the numbers of topological sorts of the members in $T\_1,\ldots,T\_k$ are respectively $c\_1,\ldots,c\_k$, then the number of topological sorts of the members in the tree rooted by $n$ is

$$\frac{(n\_1+\cdots+n\_k)!}{n\_1!n\_2!\cdots n\_k!}c\_1c\_2\cdots c\_k.$$

Using the formula above, you can compute the number of topological sorts of the members in each subtree from bottom to top. This results in an $O(N^2)$ algorithm.

# Answer
> 1 votes
The provided editorial is so hard to read. My solution is similar (or not?) to the provided one, but easier to understand.

Let $dp(u, i)$ be the number of topological sorts of subtree rooted at node $u$ such that node $u$ is placed at $i$-th position. The definition of $X$ and $Y$ are the same as the definition provided above.

Note that all the $X$ nodes has to be placed on the left and all the $Y$ nodes has to be placed on the right side of $u$ in a valid topological sort. Let's iterate through all the $X$ nodes; let the current one be $v$. We will try to merge the current topological sort with the topological sort of subtree rooted at $v$.

Denote $j$ as the position of $v$ in the topological sort we want to merge with. Let's fix some value $p$ \- the position of $u$ after the current topological sort be merged. Now we have a inequation:

$$ S\_u + S\_v - p - (S\_u - i) \ge S\_v - i + 1 $$

$$ i + j \ge p + 1 $$

We also have $p \ge i$ and $j \le S\_v$. Substituting this in the above inequation, we get:

$$ i + S\_v \ge i + j \ge p + 1 \ge i + 1 $$

Note that $i - 1$ elements of the current topological sort are placed before $p$-th position, and $S\_u - i$ elements of the current one are placed after $p$-th position. So we have the formula:

$$ dp(u, p) = dp(u, i) \cdot dp(v, j) \cdot \binom{p - 1}{i - 1} \cdot \binom{S\_u + S\_v - p}{S\_u - i} $$

Since there are no "$j$" in the binomial part, we use prefix sum / suffix sum to get sum of $dp(v, j)$ over all $j$ such that $p + 1 - i \le j \le S\_v$.

The same calculation can be done for all the $Y$ nodes. The answer of the problem is $\sum\_{i=1}^{n} dp(1, i)$. The total time complexity is $O(n^2)$.

---
Tags: algorithms, trees, counting, dag
---


# Question
Title: Using Rice's theorem to prove undecidability of $E_{TM}$
I saw this proof and I wondered if I could prove $E\_{TM}$ with Rice's theorem similar to the one described in the answer. Can you do the same thing by letting $M$ to only accept empty strings? (the $M$ that is described in the answer of the proof)

So

1. If $x$ is empty, accept
2. If $x$ is any non-empty string, reject.

# Answer
You have to be careful when you talk about accepting empty strings. Using the language from the linked question, what you are suggesting would yield $L(M\_x)$ = $\\{\epsilon\\}$ instead of $L(M\_x)$ = $\emptyset$.

You can use the same construction for machine $M\_x$, but just change the the non-trivial property to "whether this machine accepts on no inputs". It's clearly a non-trivial property since it's not empty (there are machines with empty language), and it's not the set of all Turing Machines (since not all Turing Machines have empty language).
> 0 votes

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


# Question
Title: Find optimal local alignment of two strings with restrictions
I have a homework question that I trying to solve for many hours without success, maybe someone can guide me to the right way of thinking about it.

**The problem:**

We want to find an optimal local alignment of two strings S1 and S2, we know that there exists such an alignment with the two aligned substrings of S1 and S2 both of length at most q. Besides, we know that the number of the table cells with the maximal value, opt, is at most r. Describe an algorithm solving the problem in time O(mn+r\*q^2) using working space of at most O(n+r+q^2).

**Restrictions:** run the algorithm of finding the optimal local alignment value, with additions to your choice (like the list of index pairs), only once. Besides, you can run any variant of the algorithm for solving the global optimal alignment problem as many times as you wish

I know the solution to this problem with running the local alignment many times and the global alignment only once, but not the opposite.

**the global alignment algorithm:**

**the local alignment algorithm:**

Any help would be appreciated.

# Answer
> 2 votes
1. Compute the optimal local alignment *score* OPT of both strings in $O(mn)$ time and $O(n)$ space by maintaining just a single row of the DP matrix. (Since we are only computing the score and don't need to perform traceback to build the full solution, we don't need to keep the full DP matrix.) As you do so, keep track of the highest cell value seen so far, as well as a list of the coordinates $(i, j)$ of cells having this value. Whenever a new maximum is seen, clear the list and update the maximum. Whenever a cell $\ge$ the current maximum is seen (including in the case where we just saw a new maximum), add the coordinates of the current cell to the list. At the end, we have a list of endpoints of all optimal local alignments; by assumption, there are at most $r$ of these.
2. For each entry $(i, j)$ in the list:
    1. Set $R1$ to the reverse of the substring $S1\[i-q+1..i\]$, and $R2$ to the reverse of $S2\[j-q+1..j\]$.
    2. Perform optimal global alignment of $R1$ and $R2$ in $O(q^2)$ time, maintaining the full $O(q^2)$ DP matrix this time.
    3. Search for the highest entry in the matrix (also $O(q^2)$ time; or you can perform this during the previous step).
    4. If this entry is OPT, we have found a solution: Trace back towards the top-left corner from this cell to find the full solution, reverse it, and output it, and stop.

By assumption, at least one of the alignments performed in the previous step reaches a score of OPT. (Note that reversing both strings does not change the score of an alignment.)

Step 2 iterates at most $r$ times, and does $O(q^2)$ work each time, using at most $O(q^2)$ space, so overall the time and space bounds are met.

(A simpler way, that avoids reversing strings, would be to simply perform *local* alignments of the length-$q$ substrings, but the restrictions appear to forbid this.)

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


# Question
Title: Have I proven P equals NP if I find an amortized O(n) algorithm for Subset Sum
I have found an algorithm that runs quite fast on Subset Sum problem few years ago (sometime around 2016). It basically sorts the input set in descending order (instead of the regular ascending) and does the backtracking then to arrive at results. It solves a 1,000,000 instance set in 5 minutes on my i5 8 GB RAM machine!
This year I stumbled upon this github repo: GitHub Link for Subset Sum
by another user, who claims to have solved it in amortized O(n) complexity as per his detailed analysis available on the repo. Does this prove P=NP as well, as maybe amortized O(n) implies polynomial complexity for the problem?
P.S. that I have come across many fast Subset Sum problems but I am just curious in this specific case as it relates to my algorithm too.

# Answer
This is not what amortized analysis means: you can not infer the worst case runtime of an algorithm by plotting the actual execution time on larger and larger instances of some specific structure. Sadly, that doesn't prove you have a polynomial-time algorithm. Even when you want to do experimental work, there are other parameters to vary besides the size of the input that will have a major impact on the runtime of the proposed solution. If you do so, you will have a result that roughly says "here's an algorithm that performs well in practice for instances that look like this, but I can't give any theoretical guarantees".

To summarize, it's not impressive to have an algorithm which solves huge instances belonging to a specific family of instances of an NP-hard problem quickly. What is impressive (or rather extremely remarkable), is to have an algorithm that you can prove runs in time that is polynomial in the size of the input regardless of the structure of the instance.
> 3 votes

# Answer
Subset-sum illustrates the importance of input encoding in defining NP-complete problems.

Subset-sum for $n$ integers in $\[1,k\]$ can be solved in $O(nk)$ worst-case time. That's a linear algorithm if the input is encoded in unary. But the problem is NP-complete if you encode the integers in binary, which takes $O(n\log k)$ bits.

The GitHub code that you linked defines the problem it solves as

> From a set of N numbers from 1 to 1,000,000, find a subset that sums up to a random number X (1,000,000 \< X \< N×1,000,000).

I don't know whether the code in the repo actually solves this in worst-case $O(n)$ time, but it's known to be possible to do so, even though subset-sum is NP-complete.

It's also possible to encode the input in $O(k\log n)$ bits by listing the multiplicity of each integer. For fixed $k$, $O(n)$ is exponential time if you use that encoding.
> 2 votes

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


# Question
Title: Algorithm of split graph $G=(V,E)$ to 2 groups that at least half of the edges are between the groups
Can someone remind me the algorithm that split vertex of graph to 2 groups that at least half of the edges are external, I mean between the groups. As I remember it was a greedy algorithm, each time chosen the vertex with highest number of edges, or something similar

# Answer
The solution and the analysis is given in Section 6.2.1 and 6.3 of the Book: Probability and Computing Randomized Algorithms and Probabilistic Analysis

Sometimes it is better to refer to a book rather than formulating an answer by ourselves :)
> 1 votes

---
Tags: algorithms, graphs, greedy-algorithms
---


# Question
Title: Replacement of a substring with another substring in a string
I apologize if this is not the right stackexchange for this question. I was playing around with the Python programming language, when I discovered something strange. It concerns replacing a substring of a string with another substring. For example, in "spammy", replacing "mm" with "xx" results in "spaxxy". However, in "spammmy", replacing "mm" with "xx" results in "spaxxmy", not "spaxxxxy" or even "spaxxxy". My question is, what is the proper, rigorous definition of replacing in a string $S$ a substring $T$ with a substring $T'$?

# Answer
There is no proper, rigorous definition. Or, rather, you can make multiple definitions. All are valid. You could provide a rigorous definition for replacing the first match, or a rigorous definition for replacing all matches. Mathematics doesn't tell you which definition is "proper" or "best" or "most useful".

A meta-comment: You might to be expecting more from mathematics than it can bear. Mathematics doesn't tell you what is "proper" or "right" or "best". It gives us a model for a world: if the structure satisfies such-and-such conditions, then it has such-and-such properties. You'll have to decide what conditions are appropriate, or what properties you want to have.
> 1 votes

---
Tags: strings
---


# Question
Title: Average-Case Analysis of a Simple Max-Finding Algorithm
Given this piece of code:

```
FindMax(L):
   k = len(L) - 1
   max = L[k]
   k = k - 1
   while(k >= 0):
      if(L[k] > max):
         max = L[k]
      k = k - 1
   return max

```

How would you go about computing the average-case complexity with respect to the number of times $max$ is assigned? The way I've been taught to approach a question like this is to partition the sample space into events that could represent all possible inputs. But I'm having a hard time deciding what that partition should be

# Answer
Don Knuth recently gave a recreation of his first lecture ever given at Stanford in which he addresses precisely this question with virtually the same code structure as what you have above. True to form, he showed up with a wig and authentic 1960's attire. You can watch a recording of that lecture online if you're interested.

Another way to derive this result is to use indicator variables. Let $X\_i$ be an indicator variable that is 1 if the value of max changes on the iteration of the loop corresponding to a length-$i$ subarray and 0 otherwise. Assuming the permutation given as input is uniformly random, this variable is 1 with probability $\frac{1}{i}$ because max only changes if the inspected element is the largest of its group. Using linearity of expectation, you can use this to show that the number of updates on expectation is $\Theta(\log n)$. Knuth's talk gives a different perspective using generating functions and derives a precise value as well as the variance.
> 4 votes

# Answer
The number of times that *max* is assigned to is known as the number of *records* (or *left-to-right maxima*) in the permutation. The following results are standard, and can be found in a paper of Kortchemski, which gives a much more refined analysis.

**Lemma 1.** Let $X\_1,\ldots,X\_n$ be indicator variables for the events that the $i$th element of a random permutation is a record (larger than all previous elements). Then $\Pr\[X\_i=1\] = 1/i$ and the $X\_i$ are independent.

**Corollary.** The expected number of records is $H\_n = \log n + \gamma + O(1/n)$ (the $n$th harmonic number).

This follows from linearity of expectation.

**Lemma 2.** The generating function for the number of records is $$ T\_n(q) = q(q+1)\cdots(q+n-1). $$ The coefficient $c(n,k)$ of $q^k$, which equals the number of permutations in $S\_n$ having $k$ records, is the $(n,k)$ Stirling number of the first kind.

**Corollary.** The variance of the number of records is $\log n + \gamma - \pi^2/6 + O(1/n)$.

Indeed, notice that $T''\_n(1) = \sum\_k k(k-1) c(n,k)$. On the other hand, $$ T''\_n(q) = \sum\_{0 \leq i \neq j \leq n-1} \frac{T\_n(q)}{(q+i)(q+j)}, $$ and substituting $q = 1$, $$ \frac{T''\_n(1)}{n!} = \sum\_{1 \leq i \neq j \leq n} \frac{1}{ij} = H\_n^2 - \sum\_{i=1}^n \frac{1}{i^2}. $$ Denoting by $R$ the number of records, this is a formula for $\mathbb{E}\[R(R-1)\]$. Now $$ \mathbb{V}\[R\] = \mathbb{E}\[R(R-1)\] + \mathbb{E}\[R\] - \mathbb{E}^2\[R\] = H\_n^2 - \sum\_{i=1}^n \frac{1}{i^2} + H\_n - H\_n^2 = H\_n - \sum\_{i=1}^n \frac{1}{i^2}. $$ It is well-known that $\sum\_{i=1}^\infty 1/i^2 = \pi^2/6$, and we can estimate $\sum\_{i=n+1}^\infty \leq \int\_n^\infty dx/x^2 = 1/n$. In particular, $$ \mathbb{V}\[R\] = H\_n - \frac{\pi^2}{6} + O(1/n). $$
> 3 votes

# Answer
Let me add one possible way of solution. By $T$ we denote the number of max updatings.

Direct analysis of cases after using mathematical induction gives

$$T(n) = n \cdot T(n-1) + (n-1)!$$ and from here obtain expected value

$$\frac{ T(n)}{n!} = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + ... + \frac{1}{n-1} + \frac{1}{n} = \sum\_{i=1}^{n}\frac{1}{i} - 1 =\\ = \ln n + \gamma + \varepsilon\_{n} -1 = \ln n +O(1)$$

where $\gamma$ is Euler–Mascheroni constant and $\varepsilon\_{n} \sim \frac{1}{2n}, n\rightarrow \infty$.
> 0 votes

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


# Question
Title: Hash functions producing uniform outputs
I've seen this question in a past exam paper, and I know that the answer given is **(b)**, but I'm not sure why.

> Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?
>
> (a) h(i) = i2 mod 10
>
> (b) h(i) = i3 mod 10
>
> (c) h(i) = (11 i2) mod 10
>
> (d) h(i) = (12 i) mod 10

I understand the number of buckets relating to the modulus, but not how the factor or power of i affects the uniformity of the distribution.

# Answer
What are the quadratic residues in $\mathbb{Z}\_{10}$? What about the cubic residues? What are the orders of $\[11\]$ and $\[12\]$ in the group $(\mathbb{Z}\_{10}, +)$?

A brief solution follows.

For the sake of clarity, we rename the four functions $a, b, c, d$. Let's analyze their range. Because of the closure properties of the modulo operation, we may do so in the ring $(\mathbb{Z}\_{10}, +, \cdot)$. We will prove that $a, c, d$ have a range that is a strict subset of $\mathbb{Z}\_{10}$, and can not therefore be uniform, while $b$ is a permutation of $\mathbb{Z}\_{10}$.

Since we are working over a finite ring, we could compute each of the functions on each element of $\mathbb{Z}\_{10}$ and prove our claim by exhaustion. Even though that's probably what the exercise wanted you to do, and what you should fall back on if you don't understand what follows, a true gentlemen never does that. Let's work out a more elegant way.

To begin with, we observe that $a(i) = i^2$ cannot be injective, and therefore, by piegonhole, not even surjective modulo any $m \> 2$ as $\[1\] \neq \[-1\]$ but $\[1\]^2 = \[1\] = \[-1\]^2$. This also rules out $c$, since $\[11\] = \[1\]$ in $\mathbb{Z}\_{10}$.

$d$ has to go as well; this stems from the more general fact, which I leave for you to prove, that if $\gcd(k, m) \neq 1$ then $f(i) = ki$ cannot be injective modulo $m$. (Hint: use the Bezout identity).

Now all is left is to prove that $b(i) = i^3$ is a permutation of $\mathbb{Z}\_{10}$. First of all, we observe that the ring $\mathbb{Z}\_{10}$ is isomorphic to the direct sum of $\mathbb{Z}\_5$ and $\mathbb{Z}\_2$. Since $b$ is clearly a permutation of $\mathbb{Z}\_2$, if we prove that it's also a permutation of $\mathbb{Z}\_5$ we are done. But $5$ is prime, so $i^3 \equiv i^{-1}$, which proves our claim.
> 3 votes

# Answer
Think of the hash function as a box with input and output values. Here, the number of possible output values is fixed to 10 (because of the `mod10`). Hence, uniformity depends on the input and the function. Our input *is* uniform in this case(whole numbers).

But the functions seem to mess up this uniformity(or variability). We'll choose the one which preserves uniformity.

Observe that the unit digit of the input solely decides the output: thanks to the `mod10`.

Comparing options:
A. i squared --\> Unit digits 2, 3, 7, 8 lost upon squaring.
B. i cubed --\> No loss
C. 11 * i squared --\> Same as A. Multiplying by 11 doesn't help.
D. 12 * i --\> Odd digits lost.

The answer is B, because it allows for more variety, and is therefore more uniform(for the given input range). Intuitively, a loss of variation results in the probability distribution becoming skewed, which is the reason for collisions.

PS: It is important to understand that there may exist hash function(s) that are better than these 4 options. But that's not being asked: we have to choose from the given options. Morever, as the question is from the Indian GATE exam, this is the practical approach: you only have around 2.5 minutes to solve a problem, on average.
> 1 votes

---
Tags: data-structures, hash, hash-tables
---


# Question
Title: In perfect hashing, why does a secondary hash table that is quadratic in size leads to no collisions?
See below a screenshot from CLRS 3rd Edition (Section 11.5, "**Perfect Hashing**"). The last sentence of the last paragraph says that the choice of $m\_j = n^2\_j$ leads to **collision-free** constant-time lookup.

Why? Is it because:

1. It assumes that one could, in theory, **try** or **sample** several hashing functions $\mathcal{h} \in \mathcal{H}$, checking for each for collisions, until we find one $h'$ that doesn't have them?
2. the probability of sampling $h$ without collisions is 1/2, so it shouldn't be that difficult to find $h'$?

If not, why?

# Answer
If $n\_j$ keys hash to slot $j$ of the first-level hashtable, and if $n\_j \> 1$, we will need to use a second-level hashtable for that slot. Theorem 11.9 helps us in the sense that, if we keep this second hashtable size as $n\_j^2$, then atleast 1/2 of the hash-functions in any universal-class (which all hash to range 0 to $n\_j^2-1$) must give no collisions for the $n\_j$ keys.

We can NOT conclude that if we pick any random function from this class, we will have a collision-free case. We will need to do some trials, and can hope to succeed for this set of $n\_j$ keys very soon, due to the 1/2 probability provided by Theorem 11.9.

Please also refer below answer for details: https://cs.stackexchange.com/a/134386/123596.
> 1 votes

---
Tags: algorithms, data-structures, hashing
---


# Question
Title: How does CNN deal with rotation invariant pictures?
I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply some rotation invariant techniques? . Few person on stack overflow says that max pooling does **rotational invariance** , some person says that there is **rotational invariant** CNN architecture . Give me solid reason that how CNN deal with rotational invariant pictures ? Elaborate the answer .

In machine learning , we do some features extraction techniques like SIFT , SURF etc. and apply some algorithm on it, their features are scale and rotation invariant . How about in **CNN** ?

# Answer
With a standard CNN, features are not rotation invariant, and the are not rotation equivariant. They are translation equivariant, but not rotation equivariant.

If you would like the model to be rotation invariance, then there are fancy methods to provide that, and simple methods.

The fancy method is to use a rotation-equivariant neural network. There are many research papers on this subject. See, e.g., Deep Rotation Equivariant Network by Li et al., Learning Steerable Filters for Rotation Equivariant CNNs by Weiler et al., and many others.

The simple method is to use data augmentation. During training time, randomly rotate the input image before feeding it to the neural network. You might need to train the neural network for more epochs.

Data augmentation is a lot easier to implement, and my impression is that it gives results that are close to what can be achieved with the fancy methods. Therefore, I suggest you try data augmentation first.
> 1 votes

---
Tags: algorithms, computability, machine-learning, trees, neural-networks
---