title: Human ranked/sorted items

text:
# Question
Title: Human ranked/sorted items
I'm trying to derive an algorithm or procedure I would use to have a human interactively rank a series of items based on importance by comparing a random-pairing of items at a time.

So, given an array of let's say 10 "things", I want to present two of the things, and have the user specify which is the more important of the two. What I don't know is:

* What is the proper name for this procedure/concept?
* Would I use some form of sorting algorithm?
* How could I determine when to stop? When is the ranking "done"?
* And, importantly, I would prefer not to present the same "thing" to the user in a row. That is, if comparing `Item B` and `Item K`, user selects `Item K` as more important, the next iteration should not present either `Item B` or `Item K`.

What I'm after seems similar to this question: Nearest neighbour based on subjective human comparison - is this a thing?

... but I'm not interested in similarity, just relative importance. Think prioritizing a to-do list or subjectively ranking vacation destinations, etc.

The Elo Rating System may be similar to what I'm after, as well.

# Answer
> 4 votes
There are statistical models for relative ranking. I'd suggest taking a look at the Bradley–Terry model. The data is sometimes known as paired comparison data.

See also Analysis and classification based on data points, Peer grading design - choosing a graph, to get accurate rankings/ratings, https://stats.stackexchange.com/q/83005/2921.

---
Tags: algorithms, sorting
---


# Question
Title: Construct a Turing Machine to increment any binary number
Construct a Turing Machine to increment any binary number .

(for example, if the input is 10010 then the output will be 10011 and if the input 111 then the output will be 1000

# Answer
I answered it here: https://cs.stackexchange.com/a/76316/72320

If you have any questions about it, I'll be glad to answer it.
> 0 votes

---
Tags: turing-machines
---


# Question
Title: Since programs are swapped from backing store to main memory why don't they get lost when the computer is suddenly turned off?
So when I play a video, that means the video is moved from backing store to main memory. Then if I remove my laptop's battery all of sudden, that means the video should get lost as main memory is volatile. Why doesn't this happen though?

# Answer
Because it isn't moved: it's copied.
> 12 votes

# Answer
Main memory is volatile, secondary memory is not. The video is physically stored in the secondary memory(hard drive). The main memory just fetches this data and copies it in a location on command by the program making the fetch. (video player for this example) This data is lost from the main memory since it requires constant "refreshes"(power) to access temporally stored data in it. Therefore if you remove the battery the main memory loses it but the secondary memory doesn't since it doesn't require a constant "refreshes", its magnetically saved and doesn't depend on a power source to stay there.
> 5 votes

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


# Question
Title: Asymptotic relationship of logarithms in different bases
I'm reading through the Khan Academy course on algorithms. I'm taking a quiz and finally got the right answer (all 3 of the options are true).

> For the functions $\lg n$ and $\log\_8 n$, what is the asymptotic relationship between these functions. Select all that apply.
>
> \[ \] $\lg n$ is $O(\log\_8 n)$
> \[ \] $\lg n$ is $\Omega(\log\_8 n)$
> \[ \] $\lg n$ is $\Theta(\log\_8 n)$

Why is this the case? I thought that the answer would be only the first one: $\log\_2 n$ would be the upper bound of $\log\_8 n$. Can someone explain this to a noob?

# Answer
> 5 votes
We'll show two results. The first is that for any positive constant $k$, we'll have $$ k\cdot f(n) = O(f(n)) $$ To see this, recall what it means for $g(n)=O(f(n))$: this is true when we can find two constants $c\>0, N\ge 0$ such that $g(n)\le c\cdot f(n)$ for all $n\ge N$. If we choose $g(n)$ to be $k\cdot f(n)$ then we have just what we need: we'll just use $k$ for our constant $c$ and select any $N$ we want. It's trivial to adapt this argument to big-$\Omega$, and so it also holds for big-$\Theta$ as well.

In simple terms: **Asymptotic notation ignores constant multiples.**

The second result we need is that logs to different bases are always going to be constant multiples of each other, namely $$ \log\_ax=(\log\_ab)\log\_bx $$ This is easy to see: just raise $a$ to each side power and you'll wind up with equal results.

In the problem stated, assuming that $\lg n$ is $\log\_2n$, we'll have $$ \lg n=(\log\_2 8)\log\_8n=3\log\_8n $$ and the two logs will differ only by a multiple of 3, which as we showed above, means that $\lg n$ and $\log\_8n$ are the same function, as far as big-whatever notation is concerned.

---
Tags: asymptotics, landau-notation
---


# Question
Title: How to prove the words in a regular language that start with abc constitute a regular language
Let $L$ be a regular language with alphabet $\Sigma = \\{a,b,c\\}$.

Prove that the following language is regular:

$\\{w | w \in L \text{ and } w \text{ starts with } abc \\}$.

I wonder what proof strategy I can use to prove this.

# Answer
Use closure properties of regular languages.
> 2 votes

---
Tags: regular-languages
---


# Question
Title: Are there lossless data compression techniques that do not exploit repetitive patterns?
*Lossless Data compression* (source coding) algorithms heavily rely on repetitive pattern (redundancy).

Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern (redundancy)?

**Note:**

Most lossless compression programs do two things in sequence: the first step generates a statistical model for the input data, and the second step uses this model to map input data to bit sequences in such a way that "probable" (e.g. frequently encountered) data will produce shorter output than "improbable" data.

Techniques take advantage of the specific characteristics of images such as the common phenomenon of contiguous 2-D areas of similar tones. ***Every pixel but the first is replaced by the difference to its left neighbor. This leads to small values having a much higher probability than large values.*** This is often also applied to sound files, and can compress files that contain mostly low frequencies and low volumes. For images, this step can be repeated by taking the difference to the top pixel, and then in videos, the difference to the pixel in the next frame can be taken.

***A hierarchical version of this technique takes neighboring pairs of data points, stores their difference and sum, and on a higher level with lower resolution continues with the sums.*** This is called discrete wavelet transform.

# Answer
Modeling data compression as a combination of statistical modeling and encoding seems a bit obsolete these days. In many compression algorithms, the most important step is combinatorial modeling, which finds structure in the data and uses the structure to transform the data into something that can be compressed with statistical methods. For example:

* Burrows-Wheeler transform permutes the characters based on the lexicographic ordering of the suffixes starting after them.
* Algorithms in the Lempel-Ziv family describe the text in terms of exact and/or inexact repeats.
* A graph can be described in terms of bicliques (subgraphs with an edge from every node in vertex set $A$ to every node in vertex set $B$).
* A text can be represented by a context-free grammar.
* A collection of similar strings can be described by the edit operations required to transform a reference string into each of the individual strings.
* The collection can also be described by a finite automaton recognizing a more general language, plus the paths used to produce each of the strings.
* A suffix array has self-repetitions, where each pointer in the source substring is incremented by 1 in the target substring.
* A (multi)set of integers can be represented as a binary sequence.

In principle, one can describe these combinatorial models in statistical terms, but the statistical viewpoint may not be very useful. Furthermore, many practical algorithms skip the statistical modeling/encoding part completely or do them in a naive way, as decompression speed may be more important than maximal compression.

All of these methods take advantage of the redundancy in the data or make it more explicit for the subsequent compression steps. After all, data compression is basically just getting rid of the redundancy in the data.
> 4 votes

# Answer
An interesting lossless compression algorithm for JPEG images was open-sourced this summer by Dropbox. The algorithm is called "Lepton" and achieves compression by "predicting coefficients in JPEG blocks and feeding those predictions as context into an arithmetic coder." The differences between the predictions and the actual coefficients are stored and these differences consume less space than the coefficients themselves. The algorithm takes advantage of the fact that real image data is rarely random and that gradients are smooth across blocks of pixels on average.
> 4 votes

# Answer
The answer to the question: **Is there a Lossless Data compression method/algorithm that is independent of repetitive pattern (redundancy)?**

Is: **Yes**

The probability of each symbol is used, the order of the symbol is not. Also know as an Order-0 Markov chain, are used to encode data to reduces the number of bits for frequently used symbols, and more bits for infrequently used symbols.

Some Forms of entropy encoding: Huffman coding, Arithmetic coding , and the Recent Asymmetric Numeral Systems.

No Patterns have to repeat in order to apply entropy compression.

In fact, given the same data in another file in any random order will produce a compressed file of exactly the same size (if only the entropy encoding is used). Each being able to be decoded back to their respective source.

Entropy encoding is often used as the last step of compression (IE: Hoffman / Arithmetic / rANS or tANS )

I suggest doing an internet search:

**Entropy encoding**

**Entropy shannon**
> 2 votes

---
Tags: reference-request, information-theory, data-compression
---


# Question
Title: Does KMP Algorithm handle finding multiple matches in overlapping cases?
I am wondering if KMP algorithm can find multiple matches in a given string when there is an overlap.

Here is an example.

> Word to Search from (S): `abcabcabc`
> Search word (W): `abcabc`

If you look at "W", it matches "S" from index 0 as well as from index 3

1. (abcabc)abc
2. abc(abcabc)

When I looked at the pseudo code on Wikipedia and implemented it, KMP algorithm seems to return only after the first match (`(abcabc)abc`).

Am I implementing it wrong or does KMP doesn't handle overlapping cases?

# Answer
> 6 votes
This most likely is dependent on the implementation. The failure function is used when the matching of "next" character *fails*, thus falling back to a prefix of the pattern which is the longest proper suffix up to that point.

Now when we find a match, we are at a accepting state. This accepting state has no need to look at the "next" character because it accepts no more characters thus it should **automatically fail** at the next character. This is easier to see in a String Matching DFA. Note that this comparison is valid because KMP is based on a string matching DFA.

We can create a DFA for "ABCABC" (dotted lines are failure functions):

The accepting state automatically fails on whatever input is next, but should pick back up at state 3. So if you implement the failures correctly, it should continue to find the overlapping occurrences.

If you look at the worked examples of the failure function you can see the last state (accepting state) has the length of the longest suffix which is also a proper prefix. This is what you should use to "auto-fail" back to after finding a match. I believe this is also captured in the pseudocode for KMP, where it sets `m` and `i`:

```
  ...
    if i = length(W) then
      return m (or store/use occurrence)
      let m = m + i - T[i], i = T[i] (preparing for search next occurrence)
  ...

```

The `return` here should be removed if you want to find more than one match.

---
Tags: algorithms
---


# Question
Title: Regular Language $a^n b^m c^k$ to Context free grammar
I am trying to convert a regular language to a context free grammar. The language is $L=\\{a^n b^m c^k |n=m\ or\ m\le k\\}$, my solution is: assume $m,n,k\ge0$

$S\to AS|BS|\lambda$

$A\to aAb|Ac|ab$

$B\to Bc|Bbc|aB$

Is this correct? Can somebody explain why it is correct or not correct?

# Answer
> 1 votes
Let us get things straight...the language $L$ is not regular (you can check using Pumping lemma) Although the language is Context Free as it is the union of two CFLs.

The grammar does not correspond to the language since the non-terminal $B$ can not be terminated. So only way to termiante it and get a word of the language is $S=A^\*$. But $A=aAb=aAcb=aabcb\notin L$

Correct grammar should be

$$S\to A|B$$ $$A\to Ac|aAb|\lambda$$ $$B\to aB|bBc|Bc|\lambda$$

Two non terminals $A$ and $B$ for the two CFLs whose union is $L$.

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


# Question
Title: Construct DFA’s Accept all strings containing “ 011 ” or “ 001 ” as a substring and should not contain “ 010 ” as substring
My question is

Accept all strings containing “ 011 ” or “ 001 ” as a substring and should not contain “ 010 ” as substring

for the following languages over the alphabet {0,1}

i have solve it but , i have doubt if i can make the string contain 010 as substring goes to dead state ?!!!

# Answer
To construct the DFA for a cross-section of the languages (string must be accepted by both DFAs) You can work as follows:

Make sure the transition function for the input DFAs is complete. The new set of states for the DFA is the cartesian product of the states of the 2 DFAs $Q' = Q\_1 \times Q\_2$. The transition function looks at the 2 states independently: $\delta'((Q\_1, Q\_2), s) = (\delta\_1(Q\_1, s), \delta\_2(Q\_2, s))$. The accepting states are those where both the original states are accepting $F' = F\_1 \times F\_2$.

For the union of the languages (string must be accepted by either DFA) it's the same except that the accepting state is where 1 or both of the states is accepting: $F' = (Q\_1, F\_2) \cup (F\_1, Q\_2)$. Here it is important that the transition functions are complete.

For completeness the negation of a DFA is the DFA where the accepting states are the states that are non accepting in the original DFA $F' = Q \backslash F$. Again it is important here that the transition function is complete.
> 0 votes

---
Tags: finite-automata
---


# Question
Title: What is the name the class of functions described by O(n log n)?
In "Big O", common notations have common names (instead of saying, "Oh of some constant factor"):

**O(1)** is "Constant"

**O(log n)** is "Logarithmic"

**O(n)** is "Linear"

**O(n^2)** is "Quadratic"

**O(n * log n)** is ???

Is it just "n log n" or does it have a special name like the above?

# Answer
It's called linearithmic time, and is a special case of a more general class known as *quasi linear*. As the name may suggests, the algorithms that fall in this class almost run in linear time; in fact they have a lower complexity than algorithms which run in $O(n^k)$ with $k \> 1$.
> 54 votes

# Answer
> linearithmic: adj.
>
> Of an algorithm, having running time that is O(N log N). Coined as a portmanteau of ‘linear’ and ‘logarithmic’ in *Algorithms In C* by Robert Sedgewick (Addison-Wesley 1990, ISBN 0-201-51425-7).

http://catb.org/jargon/html/L/linearithmic.html
> 17 votes

# Answer
I've always heard O(n log n) described as "log-linear" which seems about right to me.
> 11 votes

# Answer
This was too long for a comment, so I wrote an answer. I did not add this to my first answer because a lot of people already upvoted my first vanswer and I am not sure they agree with this answer, too.

* I don't think that *linearithmic* is a well established term as stated in a comment to the accepted answer. I googled some rather young articles using this term, a CS course and another book by Sedgewick that uses this term and a lot of online dictionaries.
* The term *quasilinear* I found in two articles:
> Satisfiability Is Quasilinear Complete in NQL
> C. P. Schnorr
> Journal of the Association for Computing Machinery,
> Vol 25. No 1, January 1978, pp 136-1,15

and in an article cited in the Wikipedia that deals with this Schorr's article. Schnorr introduces the complexity classes quasilinear (QL) and nondeterministic quasilinear (NQL).
Quasilinear seems to be used in the theory of partial differential equations, too.

All in all it seems that one or more Wikipedians wanted to supply names for this function that does not have a widely accepted name. But even now it seems to me that none of the names is widely accepted (besides that I think this is a kind of manipulation that Wikipedia should not do). I think one has to be cautious if one uses Wikipedia for terminology questions. And for this function it is not a sufficient source. I think the only widely accepted name for this function is *n log n*.
> 7 votes

---
Tags: asymptotics, terminology, big-o-notation, notation
---


# Question
Title: Designing CFG that accepts a^n b^m (n<m<2n)
Designing CFG for the following language $\\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n\le m \le 2n \\}$ is easy.

> $S \to aSb \mid aSbb \mid \lambda$

Then how about this? Language $\\{a^nb^m \hspace{0.2cm} | \hspace{0.2cm} n\ge0, m\ge0, n\<m\<2n \\}$.

It is somewhat difficult for me. I have no idea how to exclude $n=m$ or $m=2n$.

Could you give me some hints?

# Answer
Try this to remove the two cases the first time :

$$S\to aAb$$ $$A\to aCbb$$ $$C\to aCb|aCbb|\lambda$$

If you go to $A$ you cannot have $a^nb^{2n}$ and while going from $A$ to $aCbb$ you are removing the possiblity to get $a^nb^n$.
> 2 votes

# Answer
The only way in which your original grammar produces a string of the form $a^nb^n$ is if the production $S\to aSbb$ is never used. Similarly, the only way in which it produces $a^nb^{2n}$ is if $S \to aSb$ is never used. We thus want to force both of them to be used. Since all these productions "commute" (it doesn't matter in which order you apply them), we might as well assume that the first thing you do is apply these two productions, and the rest is arbitrary. The corresponding grammar is

$$ \begin{align\*} &S \to aaTbbb \\ &T \to aTb \mid aTbb \mid \lambda \end{align\*} $$

If instead we apply these two productions at the end, we get an even more succinct grammar: $$ S \to aSb \mid aSbb \mid aabbb $$

Alternatively, notice that $n \< m \< 2n$ is equivalent to $n-2 \leq m-3 \leq 2(n-2)$. This is since $n \< m$ iff $n-2 \leq m-3$, and similarly $m \< 2n$ iff $m-3 \leq 2n-4$. We can therefore write the language as $$ \begin{align\*} L &= \\{ a^nb^m \mid n-2 \leq m-3 \leq 2(n-2) \\} \\ &= \\{ a^{n+2} b^{m+3} \mid n \leq m \leq 2m \\}. \end{align\*} $$ The grammars above implement the latter form.
> 1 votes

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


# Question
Title: Why number of possible cuts in a graph differ from maximum number of minimum cuts?
According to this wikipedia link, under the title "Success probability of the contraction algorithm": Number of possible cuts in a graph is $2^{n-1}-1$, while maximum number of minimum cuts is ${n}\choose{2}$, where $n$ is number of vertices.

**My question:**
Why number of possible cuts differ from maximum number of minimum cuts? why isn't any cut a **candidate** minimum cut?

# Answer
> 8 votes
In a specific graph, not any cut is a minimum cut. What Wikipedia claims is that out of the $2^{n-1}-1$ potential cuts, at most $\binom{n}{2}$ can be minimum cuts in any given graph. Some graphs contain even fewer minimum cuts. For example, if you connect two cycles by a single edge then there is a unique minimum cut.

The upper bound on the number of minimum cuts follows by analyzing Karger's algorithm (linked to in the question): you can show that the probability that the algorithm produces any *specific* minimum cut is at least $1/\binom{n}{2}$, and so there can be at most $\binom{n}{2}$ of them.

---
Tags: algorithms, graphs
---


# Question
Title: Halting problem under spatial restrictions
Let $A(n, B, d)$, $B(n, d)$ be a {Turing machine, random-access machine, C program} with finite tape (which I'm going to denote "Turing machine\*" and "random-access machine\*" respectively), $n \in \mathbb{N}$. $A$ and $B$ are the same type of machine. For any $N \in \mathbb{N}$, statements where $n \leq N$, don't matter.

$n + |d|$ is the number of spatial units on $B$'s tape if $B$ is a Turing machine\* or random-access machine\*. If it is a C program, $n$ is the number of Bytes in $B$'s read-write memory (registers are neglected, see last sentence of previous pragraph). The memory $d$ takes up is read-only and not accounted for. All spatial units regarded are capable of holding the same amount of information.

$d$ is the argument data. You may assume $n$ to be included in $d$.

If $A$ is a Turing machine\* or random-access machine\*, it may access $2 \cdot (n + |d|) + c$ spatial units where $c$ is constant.

If $A$ is a C program, it may access $n + c$ Byte of read-write memory. The memory $d$ takes up is read-only and not accounted for. It may have a function which for any $p, k \in \mathbb{N}, B \in \\{\text{C program}\\}, d$ returns the $k$th Byte of $B(n, d)$'s memory after $p$ steps.

For any of the situations $B \in \\{\text{Turing machine\*}, \text{random-access machine\*}, \text{C program}\\}$: Is there an $A$ which decides whether $B(n, d)$ will halt?

I care about the reasons as to why this is the case. Unfortunately, I forgot a lot of what I learned about computability. I'm sorry if this is super trivial or unknown.

# Answer
## Yes (for Turing machines)

$A(n,B,d)$ can decide whether $B(n,d)$ will halt.

Note the fact that $B$'s writable memory is limited to $n$ units. This means that the number of possible states of $B$ is just $2^n$ (each possible memory configuration that $B$ may assume). Note also that $B$ halts iff it never goes back to a previously visited state, otherwise it would loop. This means that, if $B$ halts, it cannot do more than $2^n-1$ state transitions (as each state is visited only once).

Thus we can exploit the $2 \cdot n + c$ writable memory units of $A$ to build a machine which simulates B and counts the number of states it visits. We can do that by keeping the memory of $B$ in the first $n$ units, and a state counter $\gamma$ in some other $n+1$ units. We increment $\gamma$ at each state transition of $B$.

If $B$ halts, sooner or later the simulation of $B$ will reach a "HALT" instruction, and then we know $B$ halts. If $B$ does not halt, $\gamma$ will increase forever: as soon as $\gamma = 2^n$, we know that $B$ does not halt.
> 1 votes

---
Tags: turing-machines, undecidability, halting-problem
---


# Question
Title: How to verify that a heuristic is consistent?
> A heuristic function is said to be consistent, or monotone, if its estimate is always less than or equal to the estimated distance from any neighboring vertex to the goal, plus the step cost of reaching that neighbor.

I know I can be sure if a heuristic is consistent by verifying the property for each couple (node, child), but is there a smarter and quicker way for doing that?

# Answer
> 1 votes
Another option rather then verifying it for each couple node-child is to use some problem specific properties and prove it this way.

Iff it is known that the triangle inequality stands for the distance between the nodes in the specific problem, then the heuristic is consistent. The triangle inequality is part of definition of a metric. So if the distance in the problem space is some well known metric you can state that the heuristic is consistent. Example for that is the distance metric in the Euclidean geometry.

---
Tags: artificial-intelligence, heuristics
---


# Question
Title: How to show that a turtle graphic language is not regular?
I have to prove with the pumping lemma that $L$ is not regular or to give a regular expression for that.

Let $L$ be all combinations of commands such that in the complete drawn result no line is drawn above another. At the starting point the pen is down.

The turtle graphic is created by the following commands:

```
u - pen up
d - pen down
g - go
l - move 10° left
r - move 10° right

```

I think think that the language is not regular because I think there is an expression that crosses a line for a big enough $n \in \mathbb N$.

**Question**: How can I find an expression that helps me to prove that this language is not regular to use the pumping lemma?

And if the language is regular, what technique should I use to find a regular expression?

# Answer
> 2 votes
The program $g^nr^9gr^9g^mr^9gr^9g$ crosses a line iff $n \geq m$.

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


# Question
Title: Product of the entries of the product of two matrices
Let $A=(a\_{ij})$ and $B=(b\_{ij})$ be $n \times n$ integer matrices. Then $AB=(\Sigma\_{k=1}^n a\_{ik}b\_{kj})\_{ij}$. I am interested in finding the most efficient algorithm for computing the product of the entries of $AB$,

$\Pi\_{i,j=1}^n (\Sigma\_{k=1 }^n a\_{ik}b\_{kj}$).

Certainly, the most straightforward way of doing this (by using the above formula) is not the most efficient way of doing this, since there are algorithms like Strassen's algorithm which calculate all of the entries of the matrix $AB$ faster than simply applying the definition $AB=(\Sigma\_k a\_{ik}b\_{kj})\_{ij}$ to each entry.

Are there other efficient ways to compute the above product besides using algorithms like Strassen's algorithm?

Extra: What about computing the sum of the entries of $AB$,

$\Sigma\_{i,j,k=1}^n a\_{ik}b\_{kj}$?

# Answer
> 2 votes
You are asking two questions. I will only answer the second one. Let $1$ be the all ones column vector of dimension $n$. The sum of all entries of $AB$ is $1^TAB1 = (1^TA)(B1)$, which gives an $O(n^2)$ algorithm: compute the vectors $1^TA$ and $B1$, each in $O(n^2)$, and then compute their inner product in $O(n)$. This corresponds to the identity $$ \sum\_{i,j,k=1}^n a\_{ik} b\_{kj} = \sum\_{k=1}^n \left(\sum\_{i=1}^n a\_{ik}\right) \left(\sum\_{j=1}^n b\_{kj}\right). $$

As for the product of all entries, I suspect you can't do better than the trivial algorithm which first computes the entire product matrix, and runs in time $O(n^\omega)$.

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


# Question
Title: I don't know how to prove a simple theorem used with fixpoint in Coq
I am a beginner in coq and want to prove the following theorem t1. First I used `induction i` and `destruct j`, but it got bogged down in the middle. I would like some hints for this problem.

Function f takes two arguments of nat and returns Prop (e.g., f 2 4 = x 2 ∧ x 3 ∧ x 4 ∧ x 5).

Theorem t1 shows that a head of function f can be cut and concatenated (e.g., x 3 ∧ f 4 7 ⇔ f 3 8).

```
Parameter x : nat -> Prop.

Fixpoint f (o i : nat) : Prop :=
 match i with
 | S O =>  x (i+o-1)
 | S i' => f o i' /\ x (i+o-1)
 | _ => True
 end.

Theorem t1 : forall i j : nat,
    x i /\ f (S i) j <-> f i (S j).
Proof. Admitted.

```

# Answer
First of all, let's simplify `f` just a little bit, keeping the special case when it doesn't let the trailing `/\ True` to appear in the generated proposition (I also renamed the parameter names to make them correspond to the ones used by the theorem below):

```
Fixpoint f' (i j : nat) : Prop :=
 match j with
 | 0 => True
 | 1 => x i
 | S j' => f' i j' /\ x (j' + i)
 end.

```

Now we can `destruct j`, take care of `j = 0` case, then use `induction` on `j` again. Throwing in some automation we get the following:

```
Require Import Coq.Arith.Arith.

Theorem t1 : forall i j : nat,
  x i /\ f' (S i) j <-> f' i (S j).
Proof.
  destruct j.
  - easy.
  - induction j; firstorder; now rewrite Nat.add_succ_r in *.
Qed.

```

Notice that the structure of the proof mimics the definition of `f'`: we treat the cases `j = 0`, `j = 1` separately and then use the induction hypothesis (under the hood, `firstorder` does that) to prove the recursive case.
> 4 votes

# Answer
You are making your life difficult by defining things in convoluted ways. Here's how a better definition of the same thing makes the proof easy.

```
Fixpoint f_better n0 len : Prop :=
  match len with
  | 0 => True
  | S k => x n0 /\ f_better (S n0) k
end.

Theorem t1_better: forall n0 len,
    x n0 /\ f_better (S n0) len <-> f_better n0 (S len).
Proof.
  easy.
Qed.

```

If you really insist on using your version, we can prove that as well, but it'll be painful.
> 6 votes

---
Tags: coq
---


title: Why is Two-Phase Commit (2PC) blocking?

text:
# Question
Title: Why is Two-Phase Commit (2PC) blocking?
Can anyone let me know, why 2PC is blocking when the coordinator fails? Is it because the cohorts don't employ timeout concept in 2PC?

Good reference: *Analysis and Verification of Two-Phase Commit & Three-Phase Commit Protocols*, by Muhammad Atif,

**Elaboration of the question:**

Let’s say, a coordinator sends 1st message (PREPARE-COMMIT). At this point assuming all cohorts are reachable, there are two possible outcomes- either all cohorts reply YES or at least one cohort replies NO. In either way, let’s assume the coordinator crashes before it can send the 2nd message (COMMIT/ABORT). Since 2PC uses only 2 messages, in order to keep the cohorts consistent, the cohorts can never apply a commit without explicitly receiving a COMMIT message. So, when a coordinator crashes, the cohorts can either (1) apply a ABORT using a timeout or (2) can remain in waiting state indefinitely. It is hard to believe that a 2PC would employ option (2) i.e. waiting indefinitely. Therefore, if option (1) is chosen, then why do we tag 2PC as blocking when a coordinator dies?

# Answer
> 7 votes
> Is it because the cohorts don't employ timeout concept in 2PC?

Yes, in one case they can not use a timeout. It is described in the paper too (II.B.1):

> The Two-Phase Commit Protocol goes to a blocking state by the failure of the coordinator when the participants are in uncertain state. The participants keep locks on resources until they receive the next message from the coordinator after its recovery

In practice that 'uncertain state' means voting 'yes'. After a cohort votes 'yes', there is no going back, it waits for the global decision. (Other cases are fine: by voting 'no', the given cohort immediately knows that the global decision is also a 'no', and if the coordinator dies even before initiating the voting round, cohorts may decide voting 'no' based on a timeout)

# Answer
> 2 votes
> In either way, let’s assume the coordinator crashes before it can send the 2nd message (COMMIT/ABORT). Since 2PC uses only 2 messages, in order to keep the cohorts consistent, the cohorts can never apply a commit without explicitly receiving a COMMIT message. So, when a coordinator crashes, the cohorts can either (1) apply a ABORT using a timeout or (2) can remain in waiting state indefinitely. It is hard to believe that a 2PC would employ option (2) i.e. waiting indefinitely. Therefore, if option (1) is chosen, then why do we tag 2PC as blocking when a coordinator dies?

"Option 1" does not exist. When a cohort votes 'yes', it waits for the global decision indefinitely. That is 2PC. If you alter it because it does not look sane/plausible enough, that is not 2PC any more.

EDIT:

Some relaxation for the above: the Atif paper (and mostly Wikipedia too) describe the 'classroom' variant of 2PC. But in the original papers there were suggestions for distributed recovery too. You can find some description in the referred articles (both by Wikipedia and the Atif paper - http://dl.acm.org/citation.cfm?id=850772 is one I managed to access). The 3PC article on Wikipedia mentions it too, in its Motivation section.

I find it hard to access most of these papers (like the 'Gray 78' lecture notes from TU Munich), but as far as I understand:

* The recovery mechanism tries to get the global decision from practically anybody
* If the global decision is found anywhere, that is the global decision, and can be carried out. When the coordinator revives, it will do the same. In my interpretation, a cohort could also say 'abort', if its own vote was a 'no'. But again, I have not read the very original paper(s)
* If the global decision has not been found, and everyone (minus the coordinator) is alive, nothing happened so far (coordinator died before sending out 'commit'-s), the transaction can be aborted
* If the global decision has not been found, and there is at least one dead cohort (on top of the coordinator being dead too), that is a problem: in 2PC there is no way to tell if the unreachable cohort got a 'commit' message and carried it out before both of them died, or not. So even if there is a timeout or failure detection applied in the 'voted yes and waiting for global decision' step, there can be an indefinite waiting in the recovery procedure

(Here I was writing only about the case where the coordinator dies and cohort(s) try to deal with it)

---
Tags: distributed-systems
---


# Question
Title: TCP Connection Termination - FIN, FIN ACK, ACK
I've been reading that to terminate a TCP connection 3 handshakes are required: FIN, FIN ACK, and ACK. However, when closing a connection, Wireshark displays FIN ACK, FIN ACK, ACK; it never displays FIN by itself.

However, when establishing a connection Wireshark clearly displays the three handshakes: SYN, SIN ACK, ACK.

So I'm kinda confused why when closing the connection the three handshakes aren't displayed like that.

# Answer
A TCP implementation might send a standalone FIN in the first closing segment. However, it can *also* send a FIN ACK, instead.

The latter is strictly better: the implementation can bundle a "free" ACK with the FIN segment without making it longer. This is because, if you don't ACK, there is still room in the segment for the ACK number, which will be ignored, and waste bandwidth. Hence the last-sent ACK is simply re-sent, just in case the receiver missed it.

This is true for all TCP segments. Hence, except for the very first SYN segment, where the sender has no information about the ACK number, all the other segments will usually have the ACK flag on.
> 14 votes

---
Tags: computer-networks, communication-protocols
---


# Question
Title: Adding a character in the middle (rolling hash)
Is there a way to support adding characters in the middle and update the hash in O(1) ? All I have is the hash of ABBDE and I want to get the hash of ABBCDE.

# Answer
With just the Rolling HASH for the whole ABBDE, you can not insert into the middle of it.

**But...** as I understand rolling Hash...

If you are building the hashes up as you go (adding into the middle, adding other entries), you would need a little extra information to be able to insert into the middle at a latter access.

As I see it , You need need to know:

```
A) The whole hash (I assume you got by finding the entry there)
B) The hash for one of the halves (Left or Right)
C) A length of the HALF to know the offset that needs to be adjusted by.
D) An indicator to know which half is being adjusted to keep the halves balanced.`

```

Then all the parts can be used to recalculate, updated, replaced, and inserted to make new entries.

This would then give an O(1) time

BTW, what is this for?

**The answer to another question with a related general solution:** **Finding Hash of Substring \[i, j\] in O(1) using O(|S|) pre computation**
> 2 votes

---
Tags: modular-arithmetic, rolling-hash
---


# Question
Title: Space requirement of a universal Turing machine
Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$.

If $B$ is restricted to using at most $n$ memory cells of its tape and the memory cells of $A$ and $B$ can assume the same number of states, how much space does $A$ require at least to simulate any $B$?

$A$ knows the $n$ of the $B$ of the $g$ its given.

I'm not interested in how this behaves for small $n$ or constant additive terms but would like to know constant multiplicative factors. So if $A$'s space requirement is $3 \cdot n^2 + |g|$ memory cells, that'd be nice to know, not just that its space complexity is $\in \mathcal{O}(n^2 + |g|)$.

# Answer
> 2 votes
The constant depends on the size of the respective tape alphabets. If the two are the same and you're very careful, you can probably make do with only $n + O(1)$ space, where the constant only depends on the simulated machine. The idea is to store the tape of the simulated machine from the point of view of the cell pointed to by the head, interleaving both sides of the tape. This is not the most time-efficient simulation, but the blow-up in time is still only polynomial.

---
Tags: complexity-theory, turing-machines, space-complexity, simulation
---


# Question
Title: Computing exam averages in less than linear time
This is the question:

A spreadsheet keeps track of student scores on all the exams in a course. Each row of the spreadsheet corresponds to one student, and each column in a row corresponds to his/her score on one of the exams. There are r students and c exams, so the spreadsheet has r rows and c columns. Devise an algorithm to compute the exam averages for each student and the class average for each exam.

(It's from an ungraded practice problem set, not homework).

It seems fairly straightforward to me to do this in linear time($O(c\*r)$), but I suspect there is a faster way to do it. Is there a reasonable way to do this with better O()?

My thoughts: At first I thought I could do this by storing the average values and updating them, but I don't think this would really satisfy the requirements of the problem: given just the exam scores, getting the averages would take at least as much time, if not more.

Any help is appreciated! In particular, helpful hints are welcomed, and a helpful hint leading me to the answer will be accepted as an answer.

# Answer
To compute the exact mean (no confidence interval or estimate) of each exam, you must *at least* observe every student's exam score. This takes $\Omega(r)$ per exam. There are $c$ exams you must do this for, this problem should take at least $\Omega(c \cdot r)$ time.
> 30 votes

# Answer
I'm only looking at the mean of a set of numbers, the Student x Class is an unnecessary detail of the problem.

Assuming the data $d\[1..n\]$ sorted (this costs already a hefty $\Theta(n \log n)$) and and error margin $\epsilon$ of the acceptable result, we compute recursively the sum of $d$, $\sum\_{x \in \[a,b\]}d\[x\]$ as:

$d\[a\]$ if $a=b$

$(b-a)(d\[b\]+d\[a\])/2$ if $\frac{d\[b\]-d\[a\]}{b-a} \lt \epsilon$

$ \sum\_{x \in \[a, \frac{a+b}{2}\]} d\[x\] +\sum\_{x \in \[\frac{a+b}{2},b\]} d\[x\]$ otherwise

For a "large enough" $\epsilon$ or for large sets of repeating data, the method goes by $O(n / \log(n))$.

This guarantees (the proof by induction is left as an exercise to the reader) the average (total sum divided by numbers) to be within plus minus $\epsilon$. Statistical methods involving sampling only guarantee you to be within a specified range according to both the confidence level and conformity of the distribution with the one you assert it may fit (such as uniform or normal distribution).
> 0 votes

---
Tags: algorithms, time-complexity, arithmetic
---


# Question
Title: Prove that the language { uw : |u| =2 |w| } is regular
I have a problem with this following question:

> Prove that the language $\\{uw : |u|=2|w|\\}$ is regular.

I tried to give this regular expression $(uw²)^\*$ to resolve it.

# Answer
> 2 votes
Any string of the form $uw$ where $|u| = 2|w|$ is a string whose length is a multiple of $3$. We are therefore considering the language of strings over some alphabet $\Sigma = \\{ a\_1, \ldots, a\_k \\}$ (not specified in the question). whose length is a multiple of $3$. Let $\Sigma$ be the regular expression $a\_1 + \cdots + a\_k$. Then a regular expression descring the language in question is

$$(\Sigma\Sigma\Sigma)^\*$$

# Answer
> 1 votes
$r = (000 + 001 + 010 + 011 + 100 + 101 + 110 + 111)^\*$

Update:

**Proof**: Without loss of generality assume that our alphabet is $\\{0,1\\}$. Then $uw$ consists of 0 and 1. Any string of 0 and 1s may by written as a concatenation of two strings $u$ and $w$. For example $010101110$ may be written as a concatenation of $u=010101$ and $w=110$. But the problem says that the length of $u$ must be two times of that of $w$, which has nothing to do with the symbols of $u$ and $w$. In other words the condition does not stipulate anything regarding the content of the strings. The string $uw$ may be any string of 0 and 1s providing **it can be written as a concatenation of two strings $u$ and $w$** with length $|w|$ and $|u|=2|w|$. So, the string $uw$ has always length $|w| + 2|w| = 3|w|$, meaning that all strings in this language has lengths multiple of 3. Hence, any string of length 3k can be split up into $k$ substrings of length 3, that is one of $000, 001, 010, 011, 100, 101, 110,111$. QED

---

Example 1: $0101110 \notin L$ because its length is not multiple of 3.

Example 2: $010111000 \in L$ because its length is multiple of 3. We can take $w = 000$ and $u = 010111$.

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


# Question
Title: Algorithm to find the median with a complexity of nlog(n)
Does it exist an algorithm to find a median of table with a complexity nlog(n) Thank

# Answer
An algorithm I learned back in school was something along the following lines.

First, you will start out with one empty min-heap and one empty max-heap. You will then loop through your data, inserting the next piece of data into the max-heap. At each iteration of the loop, you check if the max-heap has 2 more pieces of data than the min-heap. If the max-heap does, you pop the max value in the max-heap and insert it into the min-heap.

After completing the insertion of the data stream, you then select the median value. If you have an odd number of data, you pop the max value off the max-heap as the median. If the data is even, you can pop the max/min value from the max/min heaps depending on what you decide is the median when data is an even size.

This approach is $O(n\log{n})$.
> 0 votes

# Answer
If the table has $n$ elements then use k-th order statistic algorithm to find n/2-th element. It runs in O(n) in the worst case.
> 1 votes

# Answer
Yes there is.

Sort the array. A quicksort or mergesort will have nlog(n) time complexity. Afterwards, find the middle element in your array (you can calculate it by dividing array.length by 2) which is a O(1) operation.

The combination of sorting and finding the middle element will be nlog(n).
> 0 votes

---
Tags: algorithms
---


title: What is "strobe"?

text:
# Question
Title: What is "strobe"?
For advancing the

address input of the RAM, we provide the

signal “strobe”.

Can anyone explain this in a bit more detail? Thanks.

# Answer
While the strobe is a hardware concept, it is sometimes directly referred to in software. A strobe is generally a voltage line in the computer, sometimes on the CPU or another chip on the motherboard, for example. The voltage of a strobe line will need to go high or low at certain times for certain things to happen. How's that for vague?

On an older computer like an Apple \]\[, you could directly read the strobe signal of the keyboard controller from a particular memory location. This would tell you whether the user had pressed a key or not and allow you to either handle it or continue on with other processing.
> 2 votes

---
Tags: cpu
---


# Question
Title: Maximize pairings subject to distance constraint
I have a list of people's locations on a world map and want to pair nearby people up such that the number of pairs is maximized.

For example, subject to the constraint that paired people are within d=10 miles of each other, I might find 742 pairs from a list of n=3000 people's locations.

Possible considerations:

* alright to assume the world is a 2D Euclidean plane
* alright to assume n \< 100000
* the distance constraint can be relaxed, for example to a cost function with a high value after 10
* as in real life, people cluster in cities, so there might be many people "0 miles apart" in New York City while people in Wyoming are few and far apart.
* any leads on the same problem above but for triplets would be great. That is, the same problem, but instead of two you take three people and group them together, preferably with the constraint still being that the three are contained in a d-diameter disc, though other similar constraints are fine.

A simple approach

* calculate all-pairs distances.

+ in the process create an array of pairs sorted from closest to farthest
    + in the process, for each person, store a list of people within d miles
* greedily pair together the closest unpaired people
* repeat the following until no progress has been made for a certain number of loops

+ find an unpaired person p\_1 with closest person p\_2 \<= d miles of them. person p\_2 is currently paired to person p\_3.
    + unpair p\_2 and p\_3 and pair p\_1 and p\_2. If any exist, pair p\_3 to a closest person p\_4 that is unpaired and within d miles.

I'm sure there are many interesting approaches to this problem, and would any love input on what research/search terms I could look into to learn more about it, any ideas for algorithms to solve this, and possibly bounds on how well the above algorithm would work on the problem.

Thank you

# Answer
You can formulate this as a maximum matching problem in an undirected graph, and then apply standard algorithms for this problem, such as Edmonds' algorithm. These algorithms are reasonably efficient and should be fast for your parameters, and they are guaranteed to find the optimal collection of pairings.

In particular, the graph is as follows. You have a vertex for each person. Draw an edge between two people if they are within 10 miles of each other. Now, you want a maximum matching in this undirected graph: i.e., a collection of edges (pairs of people) such that no two edges have a vertex in common (each person is paired up with at most one other person), and that is as large as possible.

There's lots written on the maximum matching problem; a search should turn up plenty of additional information.
> 2 votes

---
Tags: algorithms, graphs, optimization, approximation, linear-programming
---


# Question
Title: Relativized world where $LogCFL^A=PSPACE^A$
I wonder whether there is a known relativization barrier against proving $LogCFL\neq PSPACE$. Hence I'm looking for a language $A$ for which $LogCFL^A=PSPACE^A$.

One could try $A:=TQBF$, where $TQBF$ is the $PSPACE$-complete problem to decide true quantified Boolean formulas. But relativising space-bounded classes is a very tricky business, as Emil Jeřábek tried to explain to me.

Maybe it is easier to look at the problem from the other side: Both $NL\neq PSPACE$ and $CFL\neq PSPACE$ are known. I heard multiple times that one "usually considers LOGCFL instead of CFL, since it has nicer closure properties". So maybe $LogCFL\neq PSPACE$ is known. I noticed that the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, but I couldn't verify this. But if this should be known indeed, then I wonder whether it also applies to $AC^1$, or whether $LogCFL$ is really the current limit where separation from $PSPACE$ can still be proven.

# Answer
> Maybe it is easier to look at the problem from the other side: ... the German wikipedia article on NP claims that $LogCFL\neq PSPACE$ would be known, ...

It is know: $CFL \subset DSPACE(O(\log^2 n))$ was shown in \[ 1 \] and "generalized" in \[ 2 \] (whatever that means, I don't have full text access to those articles). This algorithm takes superpolynomial time, i.e. it is different from the CYK algorithm taught in Hopcroft and Ullman (and not even mentioned there, despite contrary claims). It directly follows that $LogCFL\subset DSPACE(O(\log^2 n))$ and hence $LogCFL \neq PSPACE$.

> But if this should be known indeed, then I wonder whether it also applies to $AC^1$, ...

The English wikipedia article on complexity classes claims that $NC\neq PSPACE$ would be known. Since $AC^1\subset NC$, this would mean that it also applies to $AC^1$. This separation can be deduced from $NC^k\subset DSPACE(O(\log^k n))$, see for example Lemma 5.4 *A circuit of depth* $D$ *can be simulated in* $O(D)$ *space* or slides 25-28 of this ppt. So it is well known indeed.

> But does this resolve the initial question whether there is a relativization barrier?

Who cares!

---

1 Lewis, P.M. II, R. E. Stearns, and J. Hartmanis. "Memory Bounds for the Recognition of Context-Free and Context Sensitive Languages." IEEE Conference Record on 1965 Symposium on Switching Circuit Theory and Logical Design.

2 Stephen A. Cook, Path systems and language recognition, Proceedings of the second annual ACM symposium on Theory of computing, p.70-72, May 04-06, 1970, Northampton, Massachusetts, United States
> 1 votes

---
Tags: complexity-theory, relativization
---


# Question
Title: How is segmentation different from multiprogramming with fixed partition?
As seen here: It works same like multiprogramming with fixed partition and also the memory is contiguous as well. How is it different and especially non-contiguous? What's happening here?

# Answer
> 2 votes
**Segmentation** partitions the address space into logically distinct parts usually with the high-order bits representing the *segment number*, within which the low order bits are a normal linear address space.

A *segment* is the unit of access control to memory: one process may be able to read it while another is allowed to write it.

* A process will generally have access to many segments.
* Several processes may access the same segment. This is a possible way for processes to communicate.

In **Multiprogramming** with fixed partitions, each process occupies a contiguous linear address space. It may or may not be aware of the position of the address space in the computer's memory. The process has complete access to its own address space and no access to any other process's. Any process, however, may make system calls.

You can put paging (virtual memory) underneath segmented or partitioned memory.

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


# Question
Title: Who was the first to define the RAM model?
I am working on a project where I refer to the RAM model, I explain what it is, but I am not sure who defined it first.

The wikipedia article is not very explicit about it, and the first citation is from 1946.

`Goldstine, Herman H., and von Neumann, John, "Planning and Coding of the Problems for an Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study, Princeton. Reprinted on pp. 92–119 in Bell, C. Gordon and Newell, Allen (1971), Computer Structures: Readings and Examples, McGraw-Hill Book Company, New York. ISBN 0-07-004357-4}.`

# Answer
According to the chapter notes of Chapter 1 of the book "Computational Complexity: A Conceptual Perspective" by Oded Goldreich,

> The RAM model is attributed to von Neumann's report \[234\].

where \[234\] refers to

> J. von Neumann. First Draft of a Report on the EDVAC, 1945. Contract No. W-670-ORD-492, Moore School of Electrical Engineering, Univ. of Pennsylvania. Reprinted (in part) in Origins of Digital Computers: Selected Papers, Springer-Verlag, pages 383--392, 1982.
> 2 votes

---
Tags: computation-models
---


# Question
Title: Prove that $L=\{x\mid K(x) \leq |x|-c\}$ is recognizable, where $x \in \{0,1\}^*$
Basically I want to prove that the set of all c-compressible binary strings is recognizable.

My goal is to construct a turing machine $N$ such that, given an input string $x$, $N$ accepts $x$ if there exist a turing machine $M$ and a string $s$ such that $M(s) = x$, and $|\langle M \rangle|+|s| \leq |x|-c$. Since both $|\langle M \rangle|$ and $|s|$ are bounded by $|x|$, there are only finitely many $M$ and $s$ to run through, and the output of each $M(s)$ is either $x$ or not $x$, hence the algorithm halts in finite time, and so $N$ is a decider for $L$.

But this is clearly not the case because $L$ is not co-recognizable. Where is the flaw?

# Answer
> 0 votes
The flaw in your argument is that Turing machines don't always halt. However, if a Turing machine does halt and prints $x$, then it gives you an upper bound on the Kolmogorov complexity.

---
Tags: complexity-theory, computability
---


# Question
Title: Is it true that PAC is a subset of agnostic PAC?
I would like to see the proof or a refernce to it. I feel it is obvious but my tutor insists the other way (agnostic PAC is a subset of PAC, and there are problems in PAC that are not angostic PAC).

# Answer
The trivial implication is:

$\mathcal{C}\subseteq 2^\mathcal{X}$ is agnostic PAC learnable $\Rightarrow$ $\mathcal{C}$ is PAC learnable

Intuitively, being agnostic PAC learnable is a stronger condition, since you can, for all distributions on $\mathcal{X}\times\\{-1,1\\}$, get close to the optimal error (in particular, you can do so when the labels are forced to be consistent with some $c\in\mathcal{C}$).

To see this formally, suppose a concept class $\mathcal{H}\subseteq 2^{\mathcal{X}}$ is agnostic PAC learnable. This means that there exists an algorithm $A$, such that for all $\epsilon,\delta\>0$ there exists $m\in\mathbb{N}$ such that for all distributions $\mathcal{D}$ over $\mathcal{X}\times\\{-1,1\\}$, and a set of labeled samples $(x\_i,y\_i)\_{i=1}^{n\ge m}$ drawn from $\mathcal{D}$, $A$ outputs $h\in\mathcal{H}$ such that:

$err(h)\le err^\*(\mathcal{D})+\epsilon$, with probability $\ge 1-\delta$, where $err^\*(\mathcal{D})$ is the error rate of the optimal hypothesis relative to $\mathcal{D}$.

To show that $\mathcal{H}$ is PAC learnable, let $h\in\mathcal{H}$ be some target concept, and let $\mathcal{D}$ be any distribution over $\mathcal{X}$. Examine the distribution $\mathcal{D}'$ on $\mathcal{X}\times\\{-1,1\\}$ obtained by drawing $x\in\mathcal{X}$ according to $\mathcal{D}$, and taking the pair $\left(x,h(x)\right)$. Note that $err^\*\left(\mathcal{D}'\right)=0$, which means there exists an algorithm $A$ which produces a hypothesis in $\mathcal{H}$ with small generalization error (you can complete the details yourself, this shows you that all you need to do is unfold the definitions).

The opposite implication (agnostic PAC learnability follows from PAC learnability) is also true, since they are both equivalent to $\mathcal{C}$ having a finite VC dimension, but this is much harder to show.
> 4 votes

---
Tags: machine-learning, learning-theory
---


# Question
Title: Can I prove that $\sqrt n\log{\sqrt n}=\Theta(n)$?
I'd like to prove that $\sqrt n\log{\sqrt n}=\Theta(n)$ but I'm not sure how to do it.

This is my attempt: $$ \lim\_{n \to \infty}\frac{\log{\sqrt n}}{\sqrt n}=0 \Rightarrow \log{\sqrt n}=o(\sqrt n) \text{(Little o)} $$

Therefore: $$ \sqrt n\log{\sqrt n}=o(\sqrt n\cdot \sqrt n)=o(n) $$ But this is too much as I need theta.

# Answer
> 1 votes
$$\lim\_{n\to\infty} \frac{\sqrt n \log\sqrt n}{n} = 0$$

Since this $\Theta(\sqrt n \log \sqrt n) = o(n) \< \Theta(n)$.

Two functions $f(x), g(x)$ are asymptotically equal iff

$$\lim\_{x\to\infty} \frac{f(x)}{g(x)} = c,\ c \in \mathbb{R},\ c \> 0$$

---
Tags: asymptotics
---


# Question
Title: Running time analysis for algorithm that merges $k$ sorted arrays to one sorted array
> Given $k$ sorted arrays, the size of each array is $n$ and we want to sort them to one sorted array. assume that $k=2^p$ i.e $k\in\\{ 2^1,2^2,2^3,2^4,\dots\\}$
>
> I the first step we will merge (the first and the second arrays),(the third and the fourth arrays),(the fifth and the sixth arrays),... till we get sorted arrays with length of $2n$
>
> In the second step we will merge again each successive pair till we get sorted arrays with length of $4n$

I need to find the time complexity of this algorithem.

**What I tried:**

I know that merging two sorted arrays one with length $t$ and the other with length $r$ takes $\Theta (t+r)$ .

In this case the length of each array in the first iteration is $n$, so:

* In the first iteration: merging each pair takes $\Theta(n+n)$ and there are $k/2$ merges so $\Longrightarrow \frac k 2 \Theta(2n)$
* In the second iteration: merging each pair takes $\Theta(2n+2n)$ and there are $k/2^2$ merges so $\Longrightarrow \frac k 4 \Theta(4n)$
* In the third iteration: merging each pair takes $\Theta(4n+4n)$ and there are $k/2^3$ merges so $\Longrightarrow \frac k 8 \Theta(8n)$
* In the i-th iteration: merging each pair takes $\Theta(2^in)$ and there are $k/2^i$ merges so $\Longrightarrow \frac k {2^i} \Theta(2^in)$

I got stuck here, I know that binary search takes $\Theta (\log n)$ because it divides the array to two in each iteration and here it should be ralated to $\log $ somehow,

# Answer
> 0 votes
You are almost there. In the first merge pass we do $\frac{k}{2}$ merges each taking time proportional to $2n$. In the second merge pass $\frac{k}{4}$ merges each taking $4n$ (note how nicely the factors 2 and 4 cancel and **each** merge pass runs in $\Theta(nk)$ time). Finally, since we need only $p = \log\_2k$ merge passes, we obtain the running time of $\Theta(nk \log k)$.

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


# Question
Title: Calculate the complexity of an algorithm
I have an algorithm here and it wants me to calculate the complexity:

```
for (i=1;i<n;i++)
  for (j=1;j<i*i;j++)
    if (j%i==0)
       for (k=0;k<j;k++)
          sum++;

```

First of all, I think that i have different complexities for best, average and worst case but I don't know how to find them. I have one though and I said that in the best case I will have the 2 fors and count as operation the 'if'. So i have a double sum (ΣΣ 1) with bounds being the values of i,j in the for loops. That's all i did.

# Answer
> 0 votes
The number of times that the *if* is executed is $$ \sum\_{i=1}^{n-1} (i^2-1) = \Theta(n^3). $$ The number of times that *sum* is incremented is $$ \sum\_{i=1}^{n-1} \sum\_{\substack{1 \leq j \< i^2 \\ i \mid j}} j = \sum\_{i=1}^{n-1} \sum\_{k=1}^{i-1} ki = \sum\_{i=1}^{n-1} i \binom{i}{2} = \Theta(n^4). $$ Altogether, we get a running time of $\Theta(n^4)$.

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


title: hamming distance of bloom filters

text:
# Question
Title: hamming distance of bloom filters
In the introduction of Distance-Sensitive Bloom Filters the authors state:

> The relative Hamming distance between two Bloom filters (of the same size, and created with the same hash functions) can be used as a measure of the similarity of the underlying sets.

This statement is followed by a reference to another paper, which could not clarify this statement for me.

**Question:** What is the precise relation between the hamming distance of two bloom filters and the similarity of the corresponding sets?

# Answer
> 1 votes
Let $S,T$ be two sets of size $n$. Suppose we hash each to a $m$-bit Bloom filter, using $k$ hash functions; let $x\_S$ be the $m$-bit vector corresponding to $S$, and $x\_T$ the $m$-bit vector corresponding to $T$.

If $S,T$ agree in a $p$ fraction of entries (i.e., $|S \cap T|=pn$), then the expected value of the Hamming distance between these two bit-vectors is

$$\mathbb{E}\[d(x\_S,x\_T)\] \approx 2 \exp\\{-kn/m\\} \times (1 - \exp\\{-k(1-p)n/m\\}).$$

This gives a relation between the similarity of the two sets (in terms of the number of elements they have in common) and the Hamming distance between their Bloom filters. In particular: the greater their similarity, the smaller the (expected) Hamming distance between their Bloom filters.

---

# Derivation and details

Where did I get this expression for the expected value of the Hamming distance from from? Well, consider the $i$th bit of $x\_S$. The probability that this is 0 is

$$\Pr\[x\_S\[i\]=0\] = \left( 1 - {1 \over m} \right)^{kn}.$$

For the corresponding bit of $x\_T$, the probability it is 1 is

$$\Pr\[x\_T\[i\]=1\] = 1 - \left( 1 - {1 \over m} \right)^{kn}.$$

How about the conjunction of these two events, i.e., that $x\_S\[i\]=0$ and $x\_T\[i\]=1$? We can't just multiply the two probabilities, because the two events aren't independent: the $pn$ elements in $S \cap T$ will certainly hash to the same place. However, we can take that into account by expressing the probability as

$$\Pr\[x\_S\[i\]=0 \land x\_T\[i\]=1\] = q\_1 \times q\_2 \times q\_3$$

where $q\_1$ is the probability that none of the elements of $S \setminus T$ hash to position $i$ (i.e., $\Pr\[x\_{S \setminus T}\[i\]=0\]$); $q\_2$ is the probability that none of the elements of $S \cap T$ hash to position $i$ (i.e., $\Pr\[x\_{S \cap T}\[i\]=0\]$); and $q\_3$ is the probability that at least one of the elements of $T \setminus S$ hashes to position $i$ (i.e., $\Pr\[x\_{T \setminus S}\[i\]=1\]$). Each of these can be computed as

$$\begin{align\*} q\_1 &= \left(1 - {1 \over m}\right)^{k \cdot |S \setminus T|} = \left(1 - {1 \over m}\right)^{k(1-p)n}\\ q\_2 &= \left(1 - {1 \over m}\right)^{k \cdot |S \cap T|} = \left(1 - {1 \over m}\right)^{kpn}\\ q\_3 &= 1 - \left(1 - {1 \over m}\right)^{k \cdot |T \setminus S|} = 1 - \left(1 - {1 \over m}\right)^{k(1-p)n}. \end{align\*}$$

Therefore, multiplying these quantities, we find that

$$\Pr\[x\_S\[i\]=0 \land x\_T\[i\]=1\] = \left(1 - {1 \over m}\right)^{kn} \times \left(1 - \left(1 - {1 \over m}\right)^{k(1-p)n} \right).$$

Using the approximation $(1 - 1/m)^t \approx e^{-t/m}$, we see that

$$\Pr\[x\_S\[i\]=0 \land x\_T\[i\]=1\] \approx \exp\\{-kn/m\\} \times (1 - \exp\\{-k(1-p)n/m\\}).$$

Now by symmetry,

$$\begin{align\*} \Pr\[x\_S\[i\] \ne x\_T\[i\]\] &= \Pr\[x\_S\[i\]=0 \land x\_T\[i\]=1\] + \Pr\[x\_S\[i\]=1 \land x\_T\[i\]=0\]\\ &\approx 2 \exp\\{-kn/m\\} \times (1 - \exp\\{-k(1-p)n/m\\}). \end{align\*}$$

Finally, linearity of expectation tells us that the expected Hamming distance between $x\_S$ and $x\_T$ is $m$ times the above quantity.

---
Tags: edit-distance, bloom-filters
---


# Question
Title: Examples of difference between Hidden Markov Model and Bayesian Network?
I am trying to more deeply understand the difference between Hidden Markov Models and Bayesian Network? The general idea is that HMMs have a single variable which has probabilities of entering different states, known and unknown, whereas the Bayesian network relates multiple random variables.

So, given that, what would examples of particular problems that would be appropriate for each?

# Answer
> 2 votes
A Hidden Markov Model can be expressed as an instance of a Bayesian network of a particular form. Consequently, a HMM can be viewed as an special case or kind of Bayesian network. Bayesian networks are more general, and can express other kinds of probabilistic structures as well. All HMM's are Bayesian networks, but not all Bayesian networks are HMMs.

---
Tags: probabilistic-algorithms, hidden-markov-models, bayesian-network
---


# Question
Title: 2-D peak finding complexity (MIT OCW 6.006)
In a recitation video for MIT OCW 6.006 at 43:30,

Given an $m \times n$ matrix $A$ with $m$ columns and $n$ rows, the 2-D peak finding algorithm, where a peak is any value greater than or equal to it's adjacent neighbors, was described as:

*Note: If there is confusion in describing columns via $n$, I apologize, but this is how the recitation video describes it and I tried to be consistent with the video. It confused me very much.*

> 1. Pick the middle column $n/2$ // *Has complexity $\Theta(1)$*
> 2. Find the max value of column $n/2$ //*Has complexity $\Theta(m)$ because there are $m$ rows in a column*
> 3. Check horiz. row neighbors of max value, if it is greater then a peak has been found, otherwise recurse with $T(n/2, m)$ //*Has complexity $T(n/2,m)$*

Then to evaluate the recursion, the recitation instructor says

> $T(1,m) = \Theta(m)$ because it finds the max value
>
> $$ T(n,m) = \Theta(1) + \Theta(m) + T(n/2, m) \tag{E1}$$

I understand the next part, at 52:09 in the video, where he says to treat $m$ like a constant, since the number of rows never changes. But I don't understand how that leads to the following product:

$$ T(n,m) = \Theta(m) \cdot \Theta(\log n) \tag{E2}$$

I think that, since $m$ is treated like a constant, it is thus treated like $\Theta(1)$ and eliminated in $(E1)$ above. But I'm having a hard time making the jump to $(E2)$. Is this because we are now considering the case of $T(n/2)$ with a constant $m$?

I think can "see" the overall idea is that a $\Theta(\log n)$ operation is performed, at worst, for m number of rows. What I'm trying to figure out is how to describe the jump from $(E1)$ to $(E2)$ to someone else, i.e. gain real understanding.

# Answer
> 2 votes
As I understand it, it takes $\Theta$(m) time to evaluate all the elements in given column and identify which of those elements is the global maximum. Where the $\Theta (\lg(n))$ comes in is that in the worst case scenario, the algorithm must evaluate $\lg(n)$ columns in the matrix before finding a peak. Total work would then be $\Theta(m\lg(n))$

For example, let's say your matrix has 32 columns and 8 rows.

1. You take the middle column, say column 16. You evaluate it and find that the column's global peak is superseded by an element to the right. You drop columns 1-16, and focus on columns 17-32
2. Find the middle column of the remaining matrix, which is column 24, and you evaluate for a global peak (this is your second column evaluation). You find you need to move to the right. Drop columns 17-24, focus on 25-32.
3. Find the middle (column 28) - you evaluate (third column evaluation), and you find you need to move to the right. Drop columns 25 - 28, and focus on 29 - 32.
4. Evaluate column 30 (fourth evaluation), find you need to move to the right, drop columns 29-30.
5. Evaluate one of the remaining columns (fifth column evaluation), and you're done.

In total, you completed five column evaluations. 5 = $\lg(32)$ = $\lg(n)$ where n is the number of columns in the matrix and lg is log base 2.

# Answer
> 2 votes
the analysis you outline appears to be incorrect. the correct complexity is $O(m)$ where $m$ is the larger dimension of the matrix (either rows or columns). see this other correct analysis for more/better detail. part of the mistake is not defining the recurrence relation $T(n,m)$ in terms of $T(n,m)$ only (which is handled correctly in the paper). the paper shows/uses an infinite series:

$ \begin{eqnarray\*} T(n) & = & T \left({n \over 2}\right) + cn \\ T(n) & = & T(1) + cn \left( 1 + {1 \over 2} + {1 \over 4} + {1 \over 8} + \cdots \right) \\ &= & O(n) \end{eqnarray\*} $

---
Tags: algorithms, algorithm-analysis, asymptotics, matrices
---


# Question
Title: Knapsack problem with the restriction on the number of items
Suppose $X$ is a set of integers. I am interested in the algorithm which computes the number of ways to represent an integer $W$ as a sum of exactly $k$ elements from $X$. Is it possible to modify the standard knapsack algorithm so that it does the job? Thank you for your suggestions!

# Answer
> -1 votes
Iterative solution (recursive is very similar too):

Have a 2d array $mat\[W\]\[k\]$ and let the columns be $0..k$ and the rows be from $0..W$. Let $mat\[x\]\[y\] = 0 \\;\forall \\;0\le x \le W, 0\le y \le k$. Let $mat\[0\]\[0\] = 1$.

Now run $i$ across $\[1,k\]$. Within the $i$ loop run another loop iterating $j$ across $\[1,W\]$. In every iteration of the inner loop, run through the set of elements and calculate this:

$${mat\[i\]\[j\] = \sum\_{l=1}^{|X|} mat\[i-1\]\[j-X\_l\] }\\:$$

$mat\[W\]\[k\]$ will store the final answer. Time complexity = $\mathcal{O}(W.k.|X|)$, and space complexity = $\mathcal{O}(W.k)$.

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


# Question
Title: Request for examples regarding PAC learnability
I am searching for 2 examples. At the bottom I give definitions I am using.

1. An example for H that is PAC learnable (according to 3.1) but not Agnostic PAC learnable (according to 3.3). We learned that such should exist. I saw in another post a comment that 3.1 and 3.3 are equivalent but i can't comment there (permissions) and don't see why - any way if you know such example or have a proof there is no, i'll be glad to read.
2. An example of H with 2 different non trivial loss functions (if one of them can be the 0-1 loss it will be great), which give as according to definition 3.4 that H is Agnostic PAC Learnable with one but not with the other.

> definition 2.1 (The Realizability Assumption) There exists $h\* \in H$ s.t. $L\_{(D,f)}(h\*) = 0.$. Note that this assumption implies that with probability 1 over random samples, S, where the instances of S are sampled according to D and are labeled by f, we have $L\_S(h\*) = 0$. $$$$ Definition 3.1 (PAC Learnability) A hypothesis class H is PAC learnable if there exist a function $m\_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X$, and for every labeling function $f \colon X \mapsto \\{0,1\\}$, if the realizability assumption holds with respect to $H,D,f$, then when running the learning algorithm on $m \geq m\_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$ and labeled by $f$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the examples), $$L\_{(D,f)}(h) \leq \varepsilon.$$
>
> Definition 3.3 (Agnostic PAC Learnability) A hypothesis class $H$ is agnostic PAC learnable if there exist a function $m\_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$, for every distribution $D$ over $X\times Y$, when running the learning algorithm on $m \geq m\_H(\varepsilon, \delta)$ i.i.d. samples generated by $D$, the algorithm returns a hypothesis $h$ such that, with probability of at least $1 - \delta$ (over the choice of the $m$ training examples), $$L\_D(h) \leq \min\_{h' \in H} L\_D(h') + \varepsilon. $$
>
> Definition 3.4 (Agnostic PAC Learnability for General Loss Functions) A hypothesis class H is agnostic PAC learnable with respect to a set Z=$X \times Y$ and a loss function $l : H \times Z \mapsto R\_+$, if there exist a function $m\_H\colon(0,1)^2 \mapsto N$ and a learning algorithm with the following property: For every $\varepsilon, \delta \in (0,1)$ and for every distribution D over Z, when running the learning algorithm on $m \geq m\_H(\varepsilon, \delta)$ i.i.d. examples generated by D, the algorithm returns $h \in H$ such that, with probability of at least $1 - \delta$ (over the choice of the m training examples), $L\_D(h) \leq \min\_{h' \in H} L\_D(h') + \varepsilon.$ where $L\_D(h) = E\_{z \sim D}\[l(h,z)\]$.

Thank you!

# Answer
You can find a proof for the equivalence between PAC and agnostic PAC learning in theorem 6.7 of "Understanding Machine Learning" by Shai Ben-David and Shai Shalev-Shwartz. The proof goes through showing:

1. $\mathcal{H}$ is PAC learnable $\Rightarrow$ $\mathcal{H}$ has finite VC dimension (lower bound on sample complexity).
2. $\mathcal{H}$ has finite VC dimension $\Rightarrow$ $\mathcal{H}$ is agnostic PAC learnable (upper bound on sample complexity)

If you don't care about the bounds being sharp, $1$ is not too hard, but $2$ is definitely beyond the scope of this site. Combining the above results with the fact that agnostic PAC learnability implies PAC learnability concludes the proof.

In regard to your second question, let $l\_1$ be the 0-1 loss function and $l\_2$ be a loss function which is nonzero only on a finite subset of $\mathcal{X}$ and is the 0-1 loss in that region (suppose you only care about very specific mistakes). Take any class with infinite VC dimension, then it is not agnostic PAC learnable with respect to $l\_1$, but is learnable with respect to $l\_2$ (If the loss function is nonzero only on a finite region, you can treat this case like having a finite hypothesis class).
> 1 votes

---
Tags: machine-learning
---


# Question
Title: $NP \ vs \ co-NP$: tautology to SAT and vice versa?
Let define formula $\Phi%$ given in CNF and it's complement $\overline \Phi$.

$\Phi$ is satisfiable iff $\overline \Phi$ is not tautology and vice versa.

$\Phi$ can be converted to $\overline \Phi$ in polynomial time using following method:

1. Change all literals with non-literals and vice versa: $\forall i:x\_i \Rightarrow \overline {x\_i}; \ \overline {x\_i} \Rightarrow x\_i$.
2. Change all disjunctions with conjunctions and vice versa.

This property is a corollary of CNF/DNF **definitions**.

This will give us a DNF $\ \overline \Phi\ $ of the same length as $\ \Phi$.

Assuming DIMACS format SAT solver can solve tautology this way:

1. Multiply all variables by $-1$.
2. Solve SAT.
3. Return $\overline {answer}$, where $answer$ is global (final) answer for SAT.

Example 1:

$\Phi = (x \lor y \lor \overline z) \land (\overline x \lor t) \land (\overline y \lor \overline t) = 1100.1010.0101.0000$ - is satisfiable.

$\overline \Phi = (\overline x \land \overline y \land z) \lor (x \land \overline t) \lor (y \land t) = 0011.0101.1010.1111$ - is not tautology.

Example 2:

$\Phi = (x \lor y) \land (\overline x \lor y) \land (\overline x \lor \overline y) \land (x \lor \overline y)= 0000$ - is not satisfiable.

$\overline \Phi = (\overline x \land \overline y) \lor (x \land \overline y) \lor (x \land y) \lor (\overline x \land y) = 1111$ - is tautology.

Does this proves that $NP = co-NP$? Or, maybe, somewhere I'm wrong with complexity classes?

# Answer
> 4 votes
Your algorithm doesn't prove NP = co-NP because you're using a Cook reduction to go from DNF-TAUTOLOGIES to CNF-SAT. NP and co-NP aren't separate complexity classes under Cook reductions, they are separate under Karp reductions. Under Karp reduction, changing the output of Turing machine after you've performed the polynomial-time transformation is specifically disallowed.

So while your algorithm is a way to use a SAT solver to validate proofs, it doesn't say anything about whether NP = co-NP.

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


# Question
Title: Prove that $L=\{a^i b^j c^k \mid i=1$ implies $j=k\}$ is NOT regular
Are there any closure properties which I can use to come up with a contradiction?

# Answer
$L\_1 = \\{a^ib^jc^k: i,j,k \ge0\\} = a^\*b^\*c^\*$ is regular.

Assume that $L = \\{a^ib^jc^k: (i=1) \Rightarrow (j=k)\\}$ is also regular.

Then $L\_2 = \\{ab^jc^k: j\neq k\\} = L\_1 - L$. By closure properties (difference of regular sets is regular) $L\_2$ is regular. But using Pumping lemma it is not difficult to prove that $L\_2$ is not regular. So we have a contradiction.

In fact we could prove that $L$ is not regular directly using Pumping lemma.
> 3 votes

# Answer
Let $h$ be the homomorphism defined by $h(a) = \epsilon$, $h(b) = b$, $h(c) = c$. Then $$ h(L \cap ab^\*c^\*) = \\{ b^n c^n : n \geq 0 \\}. $$
> 1 votes

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


# Question
Title: Dynamic programming, coming up with an algorithm
I've been banging my head against the wall for the past two days and can't seem to come up with anything useful. The problem that needs to be solved is the following: I get an array of integers and I must return an array containing the elements that would give the maximum sum with the following condition: If I select an element, then I cannot use the one before or after it. I think I must, like it often is with dynamic programming, somehow order my results in a matrix, but I have no idea how to go about it. Any help is greatly appreciated.

# Answer
For each $m$, let $\sigma(m)$ be the maximum sum of non-adjacent values among the first $m$ values of the array $A$. Then: $$ \begin{align\*} &\sigma(0) = 0, \\ &\sigma(1) = A(1), \\ &\sigma(m) = \max(A(m) + \sigma(m-2), \sigma(m-1)) \end{align\*} $$ As an exercise, now try to solve similar problems in which you slightly modify the constraints. For example, suppose that if you select an element then you are not allowed to use $a$ elements before or after it; or that among any $b$ adjacent elements, you are allowed to choose at most $c$.
> 1 votes

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


# Question
Title: Finding N most distinct values in set given distance metric
Let's say you are given a set with $V$ vectors and you are given a simple Euclidean distance metric $d(a,b)$ for $a, b \in V$. Then what would be the most efficient algorithm to build a subset $S$ of a desired size $k$ such that the sum of the distances between the elements of the subset is maximized?

In other words, how does one find a subset with the most *distinct* vectors?

I have tried modeling this as a complete graph where the nodes are vectors and the edges the Euclidean distances between them, but I couldn't find a graph algorithm that solves this problem. It seems like finding an independent set of given size $|S|$ with the maximum number distance between them.

# Answer
> 2 votes
This problem generalizes *maximum independent set* and its relatives. Indeed, suppose that you could solve your problem. Then you could use the solution for deciding whether a graph contains an independent set of size $k$. Given a graph $G = (V,E)$, form a metric space by setting $d(u,v) = 1$ if $\\{u,v\\} \in E$ and $d(u,v) = 2$ if $\\{u,v\\} \notin E$. The graph contains an independent set of size $k$ iff there are $k$ points in the metric space in which the sum of distances is $k(k-1)$.

---
Tags: graphs
---


# Question
Title: Retrieve shortest path between two nodes using Bellman-Ford-Moore algorithm sequentially
This is my first question here and I hope you can help mt clarifying a doubt.
Basically, I'm studying shortest path algorithms, for instance Dijkstra, Bellman-Ford-Moore, and I came up with a doubt.
From what I understood, given a node of a graph, these algorithms calculate all the shortest paths to the other nodes. So, if I block the execution when a specific condition is met, I can get just the shortest path between two nodes.
I don't have problems with Dijkstra but I can't prove this assumption with Bellman-Ford-Moore algorithm. Consider this example:
`G = (V,E)` *directed* graph where `V = {1,2,3,4,5,6}`, `E = {(1,3),(1,2),(3,2),(3,4),(2,5),(5,4),(4,6),(5,6)}` and each arch has the following `costs`, respectively: `2,1,3,3,1,2,2,5`.

The shortest path between `node 1` and `node 4` is: `1 -> 2 -> 5 -> 4` whose cost is 4.
If I try to execute BFM on this graph, assuming nodes are added in the queue with this order: `1,3,2,4,5`; the result is not what I'm expecting because the algorithm terminates returning the path `1 -> 3 -> 4`, whose cost is 5.

This is the pseudocode I'm using:

```
bfm(GRAPH G, NODE r, NODE s, integer[] T)
   integer[] d <- new integer[1...G.n]
   boolean[] b <- new integer[1...G.n]

   foreach u in G.V() - {r} do
      T[u] <- nil
      d[u] <- inf
      b[u] <- false

   T[r] <- nil
   d[r] <- 0
   b[r] <- true

   QUEUE S <- new Queue()
   Q.enqueue(r)

   while not S.isEmpty() do
      NODE u <- S.dequeue()
      b[u] <- false
      if u = s then return

      foreach v in G.adj(u) do
         if d[u] + w(u,v) < d[v] then
            if not b[v] then
               S.enqueue(v)
               b[v] <- true

            T[v] <- u
            d[v] <- d[u] + w(u,v)

```

`d` is a vector to track distances, `b` is a vector to track which node is currently in the queue, `T` is a vector of fathers, `G.adj(u)` returns all nodes adjacent to node `u` and `w(u,v)` is the cost function.

Since Dijkstra and BFM algorithms are quite similar, I thought my assumption would be valid for both of them but it seems that I'm wrong. Can you please help me understanding if and how I can use BFM to get the shortest path between two specific nodes?

Thank you so much!

# Answer
The correctness proof of the Bellman–Ford algorithm relies on the following lemma (compare Wikipedia):

> After $i$ iterations, $d\[v\]$ is at most the distance of the shortest path of length $i$ from the source vertex to $v$.

Indeed, if we perform all updates at a specific iteration in parallel, then $d\[v\]$ *equals* the distance of the shortest path of length $i$. When we perform the updates sequentially we might get lucky, and this depends on the order of vertices in the path.

This shows that in general you cannot stop Bellman–Ford early in the way you envision.
> 2 votes

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Find sum of values of points in 2D plane
Given $N$ points in 2D plane, and each point has some value. Have to answer $Q$ queries of the form:

Given $x\_1, x\_2, y\_1, y\_2$, find sum of values of all points $(x,y)$ such that $x\_1 \le x \le x\_2$ and $y\_1 \le y \le y\_2$. $N$ and $Q$ are $\le 10^6$. Also it will be helpful if someone can provide implementation.

# Answer
Possible solutions, if you're satisfied with fully offline solutions (all points and queries are known beforehand):

1. If coordinates are small enough (e.g. they're integers between $0$ and $C$), you can precalculate summed area table. Precalculate in $O(C^2)$ and answer each query online in $O(1)$. Memory consumption would be $O(C^2)$.
2. If they are not, you can use 2D segment tree with coordinate compression. Build the tree in $O(n \log n)$ (where $n$ is the number of points) and answer single query in $O(\log^2 n)$. Memory consumption would be $O(n \log n)$.
3. The previous solution can be further optimized by adding some precalculations which will exploit the static nature of the tree so that single query becomes $O(\log n)$.
4. You can use sweep line algorithm and a 1D segment tree to answer all queries in $O((n + m) log (n + m))$. This solution is probably the simplest to implement after summed area table.
> 3 votes

---
Tags: data-structures
---


# Question
Title: Understanding the binary and hexadecimal representations of UTF-8
Here is a code point: `U+091D`. The symbol it represents in UTF-8 is झ. In hex the symbol requires three bytes: `e0 a4 9d`. But it looks like the number `091D` requires two bytes. So why do we need three bytes to encode the symbol? Probably due to

> the restriction of the Unicode code-space to 21-bit values in 2003

Please see the beginning of the description section. OK, but why did they restrict the code-space to 21 bits?

I converted `e0 a4 9d` to binary, and the result is

> 11100000 10100100 10011101

Then I converted `091D` to binary and got

> 00001001 00011101

The two binary results seems to have little in common. So how did `091D` become `e0 a4 9d`?

# Answer
Where the 21 bits come from: The idea of unicode is based on the Universal Coded Character Sets (short UCS). It's a concept for a 31bit character set ordered as a 4D hypercube where the first three dimensions use 8bit and the fourth uses 7bit. Per row there are $2^8$ characters. Per plane there are $2^8$ rows $=65.536$ characters. Per cube there are $2^8$ planes and there are $2^7$ cubes. Unicode decided to just use a mere 17 planes (the code space 0 - 10FFFF), which corresponds to the 21bits.

UTF-8 is a variable length encoding mostly used for encoding unicode. Variable length means that it uses 1 to 4 byte to represent a certain code point, depending on its number of significant bits.

The scheme looks as following:

1 byte: At most 7 significant bits. From U+0000 to U+007F.
Scheme: 0xxxxxxx.

2 bytes: At most 11 significant bits. From U+0080 to U+07FF.
Scheme: 110xxxxx 10xxxxxx

3 bytes: At most 16 significant bits. From U+0800 to U+FFFF.
Scheme: 1110xxxx 10xxxxxx 10xxxxxx

4 bytes: At most 21 significant bits. From U+10000 to U+10FFFF.
Scheme: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx

In your example you have 12 significant bits and therefore the 3 bytes used for encoding.

For further details see https://en.wikipedia.org/wiki/UTF-8.
> 5 votes

# Answer
The code space isn't just restricted to 21 bits, it's restricted to values from 0 to 0x10ffff. 21 bits would be 0 to 0x1fffff, almost twice as many values.

The reason for the restriction is that this is intended for the storage of code points representing characters, and the Unicode standard doen't think that more than 17 x 65536 code points are or will ever be required. It also just so happens that the range from 0 to 0x10ffff is what can be easily represented in UTF-16 with up to two values, so a bigger range would cause problems there.

You could use a very similar scheme with up to 7 bytes storing integers up to 36 bit, but Unicode doesn't use that scheme.
> 0 votes

---
Tags: encoding-scheme
---


# Question
Title: Thompson's construction, transforming a regular expression into an equivalent NFA
There is this case of concatenation that says (from wikipedia):

> The initial state of N(s) is the initial state of the whole NFA. The final state of N(s) becomes the initial state of N(t). The final state of N(t) is the final state of the whole NFA.

My question is, does this mean that the final state of **N(s)** is *linked* to the initial state of **N(t)** with an edge labeled **ε** ?

# Answer
You can do concatenation with an epsilon transition, but it is not necessary. Many implementations avoid it because concatenations are common and the epsilon transitions significantly increase the machine size.

There is some nice code in Russ Cox's famous essay on regular expressions, which implements a common strategy: fragment machines are built without any endpoint. Instead, the fragment descriptor contains a list of states in the fragment which would have a transition to the endpoint if there were one. In this way, two fragments can be concatenated by backpatching the second fragment's start state number as the head (target) of all outgoing transitions from the states in the first fragment's endpoint list.

You will find real code (in C) in the linked essay; search for the heading starting "Implementation"
> 4 votes

# Answer
There is no need for an epsilon transition, it is a waste of space.

For a regular expression $E$, with resulting automaton $A$, must respect these properties of the transition function, $\delta$:

1. $A$ has exactly one initial state $q\_0$, which is not *accessible*$^{\*}$ from any state. That is, $$ \delta(q, a) \neq q\_0 \quad \forall q \in A, \forall a \in \Sigma$$
2. $A$ has exactly one final state $q\_f$, which is not *co-accessible*$^{\**}$ to any state. That is, $$ \delta(q\_f, a) = \emptyset \quad \forall a\in \Sigma$$

These two points are important. The initial state has no transitions into it, and the final state has no transitions out of it. This means we have no "merge conflicts", as it were.

Let $F$ be the set of all states co-accessible to the final state of $N(s)$, $s\_f$.

Let $T$ be the set of all states accessible from the initial state of $N(t)$, $t\_0$.

We then have the two states $s\_f$ and $t\_0$ and their transitions like so:

$$ \begin{align} F \rightarrow & s\_f \rightarrow \emptyset \\ \emptyset \rightarrow &t\_0 \rightarrow T \\ \end{align} $$

You can see how merging the two creates no conflicts or discrepancies:

$$ \begin{align} F \cup \emptyset \rightarrow & s\_ft\_0 \rightarrow \emptyset \cup T \\ F \rightarrow & s\_ft\_0 \rightarrow T \\ \end{align} $$

---

$^{\*}$ A state $q$ of $A$ is *accessible from a state* $p$ if there is a computation in $A$ whose source is $p$ and whose destination is $q$. A state $q$ is *accessible* if it is accessible from an initial state.

$^{\**}$ A state $p$ of $A$ is *co-accessible to a state* $q$ if there is a computation in $A$ whose source is $p$ and whose destination is $q$. A state $p$ is *co-accessible* if it is co-accessible to a final state.
> 2 votes

# Answer
Yes it is! But the final state of N(s) is no longer final
> 0 votes

---
Tags: finite-automata, compilers, lexical-analysis
---


title: Cuckoo hashing proof of cycle

text:
# Question
Title: Cuckoo hashing proof of cycle
If we come to the situation when we have to insert again the original key into the original table, I believe we have found a cycle. Is there a way to prove this?

# Answer
Yes there is, using algorithms such as Brent's cycle finding algorithm.

However, this is quite expensive and has fairly complicated code. What most implementations do is define some constant cycle/chain length, for example $\log n$ where $n$ is the number of elements in the hash table. If you find a chain (or cycle, but we never investigate whether it's actually a long chain or a cycle) larger than that constant we rehash or increase the hash table size.

But if your goal is merely the prove that you have a cycle, and you do not care about efficiency, the simplest method is to invoke the pigeonhole principle, and just loop $n + 1$ times where $n$ is the number of possible slots in the hash table. If you never find an empty slot you must have a cycle.
> 1 votes

# Answer
No, a repetition is not sufficient to demonstrate that there is a cycle.

If a key needs to be inserted into a cuckoo hash table, and it cannot be directly inserted (i.e. neither of the two hashes produces an empty nest), then there are two possible elements which could be evicted. The algorithm selects one of these two elements, and proceeds to do the eviction chain. After the first eviction, at each step there is only one possible choice, which is the "other hash". It's possible that this will lead back to the original element leading it to be evicted; this time, the other hash will be selected, so the next steps will not be the same as the cycle.

So a cycle results only if the same element is encountered *twice* during the eviction.

One useful way of looking at this is to consider the "cuckoo graph": a graph whose nodes are hash table positions (hash values) and whose edges are keys in the hash table. Each edge connects the two possible hash values for the key. A new key can be added provided that the SCC containing the new edge contains at most one cycle.

There is a good explanation of the cuckoo graph with a great animated graphic on Adrian Neumann's page on cuckoo hashing.

In fact, it is quite common for a key to repeat once during the cuckoo algorithm, so the using an unmodified cycle detection algorithm will result in too many rehashes, making the expected insertion time larger than $O(1)$. Instead of using a more complicated cycle detector, the usual approach is to simply cut off the eviction chain after it gets to some length. Since the probability that a chain reaches length $k$ is exponential in $k$, there is a threshold in $O(log N)$ (where $N$ is the size of the table) where the probability of a false positive is sufficiently low that the insertion time is still $O(1)$.
> 0 votes

---
Tags: hash-tables, hashing
---


title: Is following SAT case in $\mathsf{P}$?

text:
# Question
Title: Is following SAT case in $\mathsf{P}$?
```
f[1](2, 3, 20) : 10011010
f[2](4, 20, 21) : 10101001
f[3](4, 20, 22) : 10010110
f[4](2, 4, 23) : 10011010
f[5](5, 23, 24) : 10101001
f[6](5, 21, 23) : 01101001
f[7](2, 5, 26) : 10011010
f[8](2, 3, 33) : 10101001
f[9](3, 22, 33) : 10000110
f[10](3, 21, 40) : 10100110
f[11](3, 21, 41) : 01101001
f[12](21, 41, 42) : 10101001
f[13](40, 42, 44) : 10010110
f[14](3, 4, 45) : 10101001
f[15](26, 45, 46) : 10101001
f[16](26, 45, 47) : 10010110
f[17](24, 46, 47) : 11001001
f[18](24, 44, 47) : 01101001

```

Each `f[i](a, b, c) : truth-table` means some boolean formula of 3 variables $x\_a, x\_b, x\_c$. The main formula is conjunction of them all (I just converted CNF for `53` factorization circuit to such form and managed to reduce it to given instance).

$$\Phi = f\_1 \land f\_2 \land\ ...\ \land f\_n$$

What I think is that now I need only logarithmic (or even constant) amount of all possible assignments to see if it's satisfiable.

For example, I can take $x\_2 = 1$ and it'll automatically result in $x\_{20} = 0, x\_{21} = 0, x\_4 \neq x\_{22}, x\_{23} = 0,$ etc. It seems that half of all variables will automatically be assigned, if I'll just put one.

So, is it in $\mathsf{P}$?

# Answer
> 1 votes
This answer assumes the following interpretation of your question:

> What is the complexity of the following problem? Decide whether a given CSP is satisfiable, where at most half of the assignments satisfy each constraint.

It is likely that this problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete. In fact, if we bound the width of the constraints (how many variables appear in them), then Schaefer's dichotomy theorem implies that the problem is either in $\mathsf{P}$ or $\mathsf{NP}$-complete, giving a criterion to decide which of these possibilities holds.

In your case, it seems likely that the problem is $\mathsf{NP}$-complete already for width 3. You can verify (or refute) this using the criterion in Schaefer's theorem, which can be found in the Wikipedia article linked to above.

---
Tags: complexity-theory, satisfiability, 3-sat
---


# Question
Title: Is it possible to prove $\mathsf{BPP = NP}$ statistically?
Assuming that someone will find poly-time algorithm that statistically is wrong on ~1% of total (already runned) instances (which are very different), will it be a proof for $\mathsf{BPP = NP}$?

# Answer
One way to interpret your statement is:

> Suppose that $\mathsf{L\in NP}$, and there exists a polynomial time deterministic algorithm $A$ such that for all $n$: $\Pr\limits\_{x\sim U\_n}\left\[ A(x) = L(x)\right\]\ge 0.99$, where $U\_n$ is the uniform distribution over $\\{0,1\\}^n$, does this imply $\mathsf{L\in BPP}$?

As Yuval mentioned, the question (at heart) relates to the difference between randomized complexity and distributional (average case) complexity. Randomized complexity is the time required to correctly decide the membership of **all inputs** with high probability (where the probability is over the inner randomness of the algoirthm), whereas average case complexity is the time required for a deterministic algorithm to correctly decide "most" instances (relative to some distribution $\mathcal{D}$ over possible inputs).

This means that the question translates to whether the worst case hardness of an NP problem implies its average case hardness (the opposite direction is a result of Yao's principle, see this question for details). To the best of my knowledge, this is an open problem. There are many works on the subject, e.g. On Worst-Case to Average-Case Reductions for NP Problems by Andrej Bogdanov and Luca Trevisan. The paper defines what it means for a language to have a worst to average case reduction, and shows that unless the polynomial hierarchy collapses, such reductions cannot exist for NP complete problems (the implication might still hold, but not through their form of reduction).
> 3 votes

# Answer
Both $\mathsf{BPP}$ and $\mathsf{NP}$ are worst-case complexity classes. A problem belongs to one of these classes if there is a polynomial time algorithm (probabilistic or non-deterministic) which works correctly on *all* instances.

When talking about average-case complexity, you have to specify an input distribution. Some problems and input distributions are self-reducible: if you can solve 99% of the instances correctly (where 99% is measured according to the input distribution), then there is a probabilistic algorithm which solves *any given instance* correctly with probability 99% (the probability is now only on the coin tosses of the algorithm). In such cases there is no difference between average-case performance and worst-case performance.
> 1 votes

---
Tags: complexity-theory, np
---