# Question
Title: Every non-regular language has a subset which is a regular language?
Could anyone give me a counterexample so as to understand the proof? Thanks in advance

# Answer
Your claim is true, so there is no counterexample. $\emptyset$ is a regular language and is a subset of every (non-regular) language.
> 2 votes

# Answer
In order to make the question more interesting, let us ask for the regular subset to be *infinite*.

Here is an example of an infinite language with no infinite regular subset: $$ \\{ a^{n^2} : n \geq 0 \\}. $$ Indeed, suppose that $L$ is an infinite subset of this language which is regular. Let $p$ be the pumping length of $L$. Since $L$ is infinite, there is a word $a^{n^2} \in L$ such that $n \geq p$. The pumping lemma gives us a decomposition $a^{n^2} = xyz$ with $|xy| \leq p \leq n$ and $y$ non-empty. Then $xy^2z = a^{n^2+m}$, where $1 \leq m \leq n$. Since $n^2 \< n^2+m \< n^2 + 2n + 1 = (n+1)^2$, we know that $xy^2z \notin L$, contradicting the pumping lemma. Thus $L$ is not regular.

More generally, if $\mathcal{A} = \\{ A\_n : n \in \mathbb{N} \\}$ is any countable collection of infinite languages, then we can construct an infinite language $L$ such that no language in $\mathcal{A}$ is a subset of $L$. The construction is iterative. We will construct finite sets $L^+\_n,L^-\_n$, starting with $L^+\_0 = L^-\_0 = \emptyset$. Given $L^+\_n,L^-\_n$, we construct $L^+\_{n+1},L^-\_{n+1}$ as follows. First, choose some $w\_n \in A\_n \setminus L\_n^+$; this is possible since $A\_n$ is infinite. Let $L^-\_{n+1} = L^-\_n \cup \\{ w\_n \\}$. Second, choose some $x\_n \notin L^+\_n \cup L^-\_{n+1}$, and let $L^+\_{n+1} = L^+\_n \cup \\{ x\_n \\}$. Finally, take $L = \bigcup\_{n \geq 0} L^+\_n$. Since all $x\_n$ are different, $L$ is infinite. Since $w\_n \notin L$, we know that $L \neq A\_n$.
> 4 votes

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


# Question
Title: Best algorithm to calculate the integer partition number
The total number of ways a positive number $n$ can be partitioned is called the partition number $p(n)$. The best algorithm I found on the internet is a dynamic programming implementation of Euler's pentagonal formula. Is there any proof that there cannot be any better algorithm? Is there any better algorithm already?

# Answer
> 4 votes
Fredrik Johansson showed in his work Efficient implementation of the Hardy-Ramanujan-Rademacher formula how to compute $p(n)$ in time $O(\sqrt{n} \log^{4+o(1)} n)$ (the recent optimal integer multiplication algorithm might result in a removal of the $\log^{o(1)} n$ factor). This is nearly optimal, since the output length is $\Theta(\sqrt{n})$.

---
Tags: complexity-theory
---


# Question
Title: DFA for $a+b=c$, where $a,b,c$ are input in parallel
I've faced this question in my homework, it's a bonus question so it's harder than I could do now with my current knowledge, so if anyone could help I'll be thankful.

We're given $\Sigma=\\{0,1\\}^3$. We think of the 'letters' of the language as column vectors, so every $w\in\Sigma ^\*$ is a matrix $M\_w$ that consists of $3$ rows and $n$ columns. We refer to the binary numbers represented by $M\_w$ rows by $a\_w,b\_w,c\_w$. For example: if $w=(0,1,1)(1,0,1)$ so: $$ M\_w = \begin{array}{ccccc} 0&1&&a\_w&=01 \\ 1&0&\Longrightarrow&b\_w&=10 \\ 1&1&&c\_w&=11 \end{array} $$

We define the language $L=\\{w\in \Sigma ^\* \mid a\_w+b\_w=c\_w\\}$. For example, the $w$ above is related to $L$. However, $w'=(0,1,1)(1,0,1)(1,0,0)$ is not since $a\_w=011, b\_w=100, c\_w=110$.

**Question:** Describe DFA (Deterministic Finite Automata) that accepts $L$.

# Answer
> 3 votes
Define function $d:\Sigma^\*\to \mathbb Z$, $d(w)=a\_w+b\_w-c\_w$. So $w\in L\iff d(w)=0$.

Let us see how $d(w)$ changes if $w$ is extended by a letter $\sigma=\begin{pmatrix}a\\b\\c\end{pmatrix}\in\Sigma$.

Let $w'=w\sigma$. By the definition of a binary number, we have \begin{aligned} a\_{w'} &= 2\times a\_{w} + a\\ b\_{w'} &= 2\times b\_{w} + b\\ c\_{w'} &= 2\times c\_{w} + c\\ \end{aligned} So, $$d(w') = 2\times d(w) + d(\sigma)$$ Note that $-1\le d(\sigma)\le 2$.

* $d(w)\le -2 \implies d(w')\le -2$
* $d(w)=-1 \implies d(w')=-2 + d(\sigma)$
* $d(w)=0 \implies d(w')=d(\sigma)$
* $d(w)\ge 1 \implies d(w')\ge 1$

Let us construct a DFA with three states $q\_{\le-2\\,\text{or}\\,\ge1}$, $q\_{=-1}$, and $q\_{=0}$.

* $q\_{\le-2\\,\text{or}\\,\ge1}$ for $w$ such that $d(w)\le-2$ or $d(w)\ge1$.
* $q\_{=-1}$ for $w$ such that $d(w)=-1$.
* $q\_{=0}$ for $w$ such that $d(w)=0$.

Readers can specify the accept state and the transition function so that the DFA accepts $L$.

---

Here is a nice DFA provided by OP.

>

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


title: Useless states in a PDA

text:
# Question
Title: Useless states in a PDA
I am trying to solve a problem in Sipser's Introduction to the Theory of Computation book, which reads:

> 4.22 A ***useless state*** in a pushdown automaton is never entered on any input string. Consider the problem of determining whether a pushdown automaton has any useless states. Formulate this problem as a language and show that it is decidable.

I feel that I have a solution, but at the same time the solution makes no reference to the fact that the machine in question is a PDA, which makes me suspicious. Here is my proposed solution:

Formulate the problem as the language $$L = \\{\langle M, q, w \rangle \mid M \text{ is a PDA }, q \text{ is a state of M}, w \text{ is any word in } \Sigma(M)^\*\\}.$$ Then to decide this language, simply run $w$ in $M$, and see if we ever encounter $q$. Since PDAs are non-deterministic by definition, there may be branching choices, and so we just go through all possible branches. We accept if we encounter $q$ at some point, and reject if we don't. Since the PDA can't loop, then this process won't loop either, and so $L$ is decidable.

This seems to work to me, but as mentioned, it makes no real use of PDAs. It seems like this argument would also work if $M$ was more generally a Turing-decider. So basically, my question is, is this argument truly valid, or am I missing something? My only thought is that perhaps this language is not a true formulation of the problem. If so, how does one understand whether the language they have written is a correct formulation or not?

Thanks for reading, and for any insight.

# Answer
> 2 votes
Your formulation of the language is wrong. Your language is a collection of *pushdown automata*. A PDA $M$ is in your language if it has no useless states. This means that for every state $q$, there is an input $w$ and a run of the PDA on $w$ which causes $M$ to enter $q$.

Moreover, PDAs can definitely loop, since they have $\epsilon$ transitions, so your solution doesn't quite work even for your language. It definitely doesn't work for Turing machines; indeed, if $M$ is a Turing machine, then your language becomes undecidable.

---
Tags: formal-languages, pushdown-automata, decidability
---


# Question
Title: Argument as to why a word does not belong to a language (pumping lemma)
Given the language $D = \\{x^n y^n y^m \mid n,m \geq 0\\}$, I have applied the pumping lemma with $k\>0$, $n=k$ and $m=0$ and found a word $z = x^{k+q} y^k$ with $q\>0$ that does not belong to $D$.

However, it is not sufficient to argue that the number of $x$'s and $y$'s is not equal and thus the word does not belong to $D$, as $D$ does not need an equal number of $x$'s and $y$'s.

So how would one instead argue that $z$ does not belong to $D$?

# Answer
> 1 votes
Another way to write your language is $\\{x^n y^m \mid n \leq m\\}$. You can see this by proving that every word in $D$ belongs to this set, and vice versa (details left to you).

This shows that if $q \> 0$, then $x^{k+q} y^k \notin D$.

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


title: Find indices of equal cells in a matrix

text:
# Question
Title: Find indices of equal cells in a matrix
I am trying to find the indices of all the equal elements in a matrix $\left ( n\times m \right )$. For each pair of matching cell, I will perform a specific function on them. For example:

$ \begin{bmatrix} 2 & 1 & 3\\ 4 & 1 & 5\\ 2 & 3 & 2 \end{bmatrix}$

The cell (1, 1) whose value is 2 matches with cells (3, 1) and (3, 3). I tried to do this by looping through the whole matrix twice which is far away from being efficient $O(n^2m^2)$. Is there a more efficient way to do this search (at least to avoid duplicates)?

# Answer
You can use sorting ($O(nm \log nm)$) or a hash table (randomized $O(nm)$).
> 1 votes

---
Tags: algorithms, arrays, matrices
---


title: Lower bound for querying KD tree

text:
# Question
Title: Lower bound for querying KD tree
In the book Computational Geometry, Algorithms and Applications there is an exercise asking:

> In the proof of the query time of the kd-tree we found the following recurrence: $$ Q(n)= \begin{cases}O(1), & \text { if } n=1, \\ 2+2 Q(n / 4), & \text { if } n\>1 .\end{cases} $$ Prove that this recurrence solves to $Q(n)=O(\sqrt{n})$. Also show that $\Omega(\sqrt{n})$ is a lower bound for querying in a kd-tree by defining a set of $n$ points and a query rectangle appropriately.

The first part regarding the upper bound can be shown via the master method (the master method actually shows that this recurrence is $\Theta(n)$). However I am a bit uncertain about defining a set of points and a query rectangle that shows the lower bound.

Consider the example below where $n=4$. The points are the red dots, the median lines are the black lines, and the query rectangle is the blue rectangle. Does this show the lower bound, or do we need a more general construction since for $n=4$ we have $\log\_2(n) = \sqrt n$?

# Answer
No. To show a $\Omega(\sqrt{n})$ lower bound, it's not enough to show a lower bound for the single value $n=4$. I suggest you refer to the definition of big-Omega notation: https://en.wikipedia.org/wiki/Big\_O\_notation#The\_Knuth\_definition, https://en.wikipedia.org/wiki/Big\_O\_notation#Formal\_definition, How does one know which notation of time complexity analysis to use?.
> 1 votes

---
Tags: data-structures, computational-geometry, kd-tree
---


# Question
Title: (Algorithm required) How to determine if a point is in one of many rectangles
What I want to achive ist the following: I have a 2D plane and on this plane I will have a potentially large amount of rectangles (these are specified with 2 coordinates spanning it)

Whats the most efficient way to determine if a point is in one of the rectangles

From some previous research I found that quad trees are good for that and I think I also understand how they work but I can't figure out how they help to solve my problem. I can find points close to one point but how to I find out if my point is in one of the many rectangles?

# Answer
> 2 votes
Use a segment tree or interval tree.

---
Tags: algorithms, data-structures, trees, search-trees
---


# Question
Title: Time complexity of an algorithm in the $\Theta$ notation
Consider the following algorithm:

```
res := 0
for i := 1 to n do
    j := i
    while j mod 2 = 0 do
        j := j / 2
    res := res + j

```

What's its time complexity in terms of the $\Theta$ notation?

What I have so far:

* The complexity is $\Omega(n)$ and $O(n\log n)$, but I'm having trouble finding a tight bound (according to the $\Theta$ definition I would have to find a function $f$ such that the function describing the cost of the algorithm is $\Omega(f)$ and $O(f)$).
* The cost of the inner loop in the $i$-th iteration is $T(i)=\begin{cases} O(1)&i\ \text{is odd}\\ O(1)+T(i/2)&i\ \text{is even}\\ \end{cases}$

# Answer
The total number of inner loop tests is the sum of the number of trailing zeroes in the numbers from $1$ to $n$.

If $n=2^m$, every other number is even, every fourth number is a multiple of four and so on. Hence

$$T(n)=n+\frac n2+\frac n4+\frac n8+\cdots 1=2^{m+1}-1=2n-1.$$

When $n$ lies between two powers of $2$, $T(n)$ is intermediate as well.

> $$T(n)=\Theta(n)$$
> 3 votes

---
Tags: time-complexity, asymptotics
---


title: BST subtree value range

text:
# Question
Title: BST subtree value range
Suppose we have a node x in BST, and let max and min be the largest and smallest keys in the subtree rooted at x respectively. Prove that for any node n outside this subtree, the key of n is either greater than max or smaller than min. How should I approach this problem? I get that there are basiclly 3 cases for x,

1. x is the root of the entire tree, then this is trivial
2. x is the right child of its parent p, then p is smaller than min, also the left children of p is smaller than min
3. the reverse case of 2

I can basiclly recursively apply this, but how do I formally write a proof for it？

# Answer
From how you state the conditions, it appears that $x$ and its subtree belongs to a larger tree and what you need is to prove that any other node $n$ in the larger tree but not in the subtree of $x$ must be smaller than $min$ (of $x$'s subtree) or larger than $max$, thus I do not see the need for case 1. I would also assume that keys of the nodes are distinct.

For your cases 2 and 3, instead of the parent you can generalize it so that $n$ is an ancestor of all nodes in $x$'s subtree. So if $x$ and its subtree is part of the left subtree of $n$ then key of $n$ is larger than $max$, since $n$ must be larger than all keys on its left subtree. You can have an analogous reasoning for $min$ when $x$'s subtree is part of $n$'s right subtree.

An additional case here (with two subcases) is if $n$ is not an ancestor and it belongs to a separate subtree. In this case, $n$ and $x$ will have the lowest common ancestor (lca), $a$. If $x$ is in the left subtree of $a$ and $n$ is in the right subtree then $n \gt max$ since $max \lt a \lt n$. Again, an analogous reasoning can be made when $x$ is in the right subtree while $n$ is in the left subtree of $a$.
> 1 votes

---
Tags: proof-techniques, binary-search-trees
---


# Question
Title: Programmatically determine if a tie is possible in US elections
Problem 3.5 from book: "Algorithms for interviews".

There are 51 states (+ Washington DC), each with different amount of votes. Find the number of votes of each state here

Suppose there are two candidates in the presidential election. How would you programmatically determine if a tie is a possibility. The problem is in dynamic programming section.

Solution: We need to find out if there is a subset in the set of 51 state-votes such that its elements add up to 269. The number of possible subsets is 2^51, so bruteforce solution is out of question.

My approach is the following: Let `P(i,c)[0 < i < n, 0 < c < 269]` be a node in a graph. `i` represents the state index, `c` represents votes **left** to reach 269.

Each `P(i, c)` has two children: `P(i + 1, c), P(i + 1, c - V(i))` where `V(i)` is list of state-votes(i.e. either state `i` votes for our candidate or it doesn't). This leads to a graph(a tree actually) which interestingly has same amount of nodes as there are subsets: 2^51.

Starting from `P(0, 269)`, we do BFS until all states are exhausted or **c == 0**

The solution is quick with only ~20k nodes discovered(instead of 2^51) but I have a few doubts.

1. Worst case scenario of this solution has exponential complexity. Is this an NP complete problem?
2. Is there a better solution. Even if it's np complete, can we do better?
3. How can I model this problem with recurrence relation instead of graph?

Solution in Java:

```
    public boolean run() {
        List<Integer> stateVotes = List.of(9,3,10,6,55,9,7,3,27,15,4,4,21,11,7,6,8,9,4,10,12,17,10,6,11,3,5,5,4,15,5,31,15,3,20,7,7,21,4,8,3,11,34,5,3,13,11,5,10,3,3);

        //bfs
        var visited = new HashSet<Node>();
        var queue = new LinkedList<Node>();
        queue.add(new Node(0, 269));

        while(!queue.isEmpty()) {
            var node = queue.pop();
            if (node.y == 0) {
                return true;
            }

            if (visited.contains(node)) {
                continue;
            }
            visited.add(node);

            if (node.x < stateVotes.size() - 1) {
                queue.add(new Node(node.x + 1, node.y));
                queue.add(new Node(node.x + 1, node.y - stateVotes.get(node.x)));
            }
        }
        return false;
    }

```

# Answer
> 0 votes
Your problem is known as PARTITION, which is a special case of the well-known problem SUBSET SUM. Your algorithm is the standard dynamic programming solution. You can find a wealth of information on SUBSET SUM all over the internet.

# Answer
> 2 votes
Just create a bit array of say 600 entries, initially with bit 0 set. This array represents the possible number of votes from the first n state, for n = 0 initially.

Take the first state. If it has for example 13 votes, then set array\[I+13\] = 1 for all elements where a\[I\] is set. So that would give you bits 0 and 13 set - from the first state you can have either 0 or 13 votes.

Take the second state. If it has for example 9 votes, then set array\[I+9\] = 1 for all elements where a\[I\] is set. So that would give you bits 0, 9, 13 and 22. From the first two states you can have 0, 9, 13 or 22 votes.

Repeat with all the other states, and then check whether bit 269 is set. It turns out if all electoral votes go to the same party, then any votes other than 1 or 2, or all but one or two, are possible. But in Maine and Nebraska the votes can be split, and it is possible to have 1 or 2 electoral votes in these states, so every outcome is actually possible.

---
Tags: algorithms, graphs, np-complete, dynamic-programming, recurrence-relation
---


title: Recursion problem T(n)=3T(n/3)+3n

text:
# Question
Title: Recursion problem T(n)=3T(n/3)+3n
I just need help solving this problem. I know I'm supposed to be using the Master's Theorem but I don't know where to start

# Answer
> 0 votes
$$T(n)=3T\left(\frac n3\right)+3n=9T\left(\frac n9\right)+3\frac n3+3n=27T\left(\frac n{27}\right)+3\frac n{27}+3\frac n3+3n=\cdots$$

So for an exact power of $3$, you get

$$nT(1)+3\frac{3n-3}2.$$

---
Tags: recursion, discrete-mathematics
---


title: What does the program counter do?

text:
# Question
Title: What does the program counter do?
I was browsing the architecture of a simple CPU but there is one thing a cannot understand. Why is there data from the ALU going to the program counter and what is that data for?

# Answer
> 11 votes
Since this is a simple CPU, it's almost certainly to compute branch targets. Branch instructions typically represent the location to branch to as a small signed number to add to the program counter. The reason for this is that conditional branches almost always occur within a procedure or function, so it makes sense to encode them as an offset, which uses fewer bits.

In "real" CPUs, another common use case is to support position-independent code.

# Answer
> 5 votes
The program counter is a special processor register pointing to the next instruction to be fetched from memory and executed. When executing a non-branching instruction, the CPU increases the PC by 1 (or the size of instructions). Branching means assigning a new value to the program counter. Addresses to branch to are rarely absolute - usually they are relative to the current position, or to the beginning of a code segment. Therefore, such values need to be able to come from the ALU.

---
Tags: cpu
---


title: Decision problem

text:
# Question
Title: Decision problem
Prove the following theorem

* Let A and B be two languages on an alphabet Σ. If A ≤p B and B ∈ P, then A ∈ P.

Could anyone be able to prove it?

# Answer
This is a standard theorem. You can prove it using the definition of $\le\_p$ which guarantees some *poly-time* function $f:\Sigma^\*\rightarrow \Sigma^\*$ with the property that $x\in A\iff f(x)\in B$.

Since $f$ is poly-time computable, then $f(x)$ can be computed. Then, since $B\in P$, we can again answer whether $f(x)\in B$ with polynomial time.

There is a small caveat though - computing whether $f(x)\in B$ is polynomial with respect to the size of $f(x)$, and not of $x$ as we would like. But since $f$ is polynomially computable, we can guarantee that $|f(x)|$ is polynomial in $|x|$, and thus, since polynomials are preserved under composition - we know that a polynomial in $|f(x)|$ is a polynomial in $|x|$, solving the problem. Finally - this means we can compute whether $f(x)\in B$ in polynomial time with respect to $|x|$, and thus also $x\in A$ is polynomially computable.
> 0 votes

---
Tags: reductions, undecidability, decision-problem, decidability
---


title: What is a contiguous subarray?

text:
# Question
Title: What is a contiguous subarray?
What is a contiguous subarray? I have tried searching online and have found pages about solving the largest contiguous subarray problem but none with a definition or explanation of what **contiguous** in this actually is.

Ex: Wikipedia: Maximm subarray problem has no explanation of why the given "subarray" is **contiguous** or what contiguous means in the context.

# Answer
> 9 votes
This is just the ordinary dictionary definition of "contiguous": all adjacent in space. A subarray is defined by any subset of the indices of the original array; a contiguous subarray is defined by an interval of the indices: a first and last element and everything between them.

# Answer
> -1 votes
**EDIT:** I get what people are saying. The actual definition of contiguous subarray is any sub series of elements in a given array that are contiguous ie their indices are continuous.

So given \[1,2,3,4,5,6\]:

\[1,2,3\], \[3,4\], \[3,4,5,6\] are all valid contiguous subarrays. Any algorithm can be used to generate the subarrays.

Personal note: What was confusing for me was most explanations either use or reference a specific problem or condition set to generate the subarrays. Most don't specifically state there's no direct relationship between the problem and the definition of contiguous subarrays.

For me it's the same as asking:

Q: "What does + do?"

A: "4+4=8"

Me: "OK, so I can only use + with 4, got it."

This is how my brain worked to grok the definition, so hopefully it helps someone else out.

**ORIGIONAL ANSWER:**

OK from what I've worked out the term "contiguous subarray" is a misnomer.

Subarray = "any part or section of an array" Contiguous = "data that is moved or stored in a solid uninterrupted block."

But AFAIK "Contiguous" still needs to be qualified by further conditions.

For example this Facebook/Meta test question:

> Contiguous Subarrays
>
> You are given an array a of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfills the following conditions:
>
> The value at index i must be the maximum element in the contiguous subarrays, and These contiguous subarrays must either start from or end on index i.

Or this LeetCode Example:

> Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.

So just asking for "contiguous subarray" **without** the conditions of what makes a subarrary contiguous is invalid.

---
Tags: terminology, arrays, maximum-subarray
---


# Question
Title: Are there a Dynamic programming solution that partition number and minimize the sum of absolute difference of each partition?
Suppose given $n=2k$ numbers. We want partition numbers into two group $G\_1,G\_2$. Let $d\_1$ be the largest value of absolute difference between each pair of numbers in $G\_1$ and also $d\_2$ be the same as $d\_1$ but in respect to numbers in $G\_2$. Our goal is each group contains exactly $k$ numbers and minimizing $d\_1+d\_2$.

Is there any Dynamic programming solution for the above problem? I think many days but I can't figure out the solution if exists.

# Answer
> 0 votes
For simplicity I'll consider the case in which all numbers are distinct and $k \ge 2$. The argument below generalizes to the unrestricted case.

Let $G\_1, G\_2$ be the groups of an optimal solution and assume, w.l.o.g., that $\min G\_1 \le \min G\_2$.

Let $x=\max G\_1$ and $y= \min G\_2$. We must have $x \le y$ since otherwise we would have $x \> y$ and the sets $G\_1^\* = (G\_1 \setminus\\{x\\}) \cup \\{y\\}, G\_2^\* = (G\_2 \setminus\\{y\\}) \cup \\{x\\}$ would be a better solution.

Indeed: $(\max G\_1^\* - \min G\_1^\*) + (\max G\_2^\* - \min G\_2^\*) \< (x - \min G\_1) + (\max G\_2 - y) = (\max G\_1 - \min G\_1) + (\max G\_2 - \min G\_2).$

Since $|G\_1|=k$, it follows that $G\_1$ must contain the smallest $k$ numbers, which can be found in linear time by finding the median of your set of numbers.

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


# Question
Title: Isabelle (rule disjE) disjunction elimination rule
```
lemma ejercicio_36o:
    "(p ∨ q) ∧ (p ∨ r) ⟹ p ∨ (q ∧ r)"
      apply (frule conjunct1)
      apply (frule conjunct2)
      apply (erule disjE)
       apply (erule disjI1)
      apply (erule disjE)
       apply (erule disjI1)
      apply (rule disjI2)
      apply (erule conjI)
      apply assumption
      done

```

I managed to prove the one above, but not the one below. It should be possible to do it with just those rules.

```
lemma ejercicio_36:
  assumes "(p ∨ q) ∧ (p ∨ r)"
  shows "p ∨ (q ∧ r)"
proof -
  have "p ∨ q" using assms(1) by (rule conjunct1)
  have "p ∨ r" using assms(1) by (rule conjunct2)
  moreover
  {assume "p"
    hence "p ∨ (q ∧ r)" by (rule disjI1)}
  moreover
  {assume "q ∧ r"
    hence "p ∨ (q ∧ r)" by (rule disjI2)}
  ultimately show "p ∨ (q ∧ r)" by (rule disjE)
  oops

```

Thank you.

# Answer
> 1 votes
Thanks to Patrick Browne I got what I was looking for.

```
lemma exercise:
  assumes "(p ∨ q) ∧ (p ∨ r)"
  shows "p ∨ (q ∧ r)"
proof -
  have "p ∨ q" and "p ∨ r" using assms by (rule conjunct1, rule conjunct2)
  note ‹p ∨ q›
  moreover
  {assume "p"
    hence "p ∨ (q ∧ r)" by (rule disjI1)}
  moreover
  {assume "q"
    note ‹p ∨ r›
    moreover
    {assume "p"
      hence "p ∨ (q ∧ r)" by (rule disjI1)}
    moreover
    {assume "r"
      with ‹q› have "q ∧ r" by (rule conjI)
      hence "p ∨ (q ∧ r)" by (rule disjI2)}
    ultimately have "p ∨ (q ∧ r)" by (rule disjE)}
  ultimately show "p ∨ (q ∧ r)" by (rule disjE)
qed

```

---
Tags: proof-techniques, correctness-proof, isabelle
---


# Question
Title: Termination condition for max of array using divide and conuqer approach
I want termination proof of divide and conquer approach to find max of array,I want equational proof in form of lemma.Below is my attempt.I have got accepted everything in dafny ,it is only pointing the termination proof as false.Below is the code-

```
method maxofarray(a:seq<int>) returns (max1:int)
requires |a|>=0
ensures |a|==1==>max1==a[0]|||a|>1==>maxpred(max1,a[..|a|])
decreases |a[0..|a|/2]|
{
if (|a|==1)
{
max1:=a[0];
}
else
{
var middle:=|a|/2;
var m1:=maxofarray(a[0..middle]);
var m2:=maxofarray(a[middle..|a|]);
if (m1>=m2)
{
max1:=m1;
}
else
{
max1:=m2;
}
}
}
predicate maxpred(max1:int,a:seq<int>)
{
(|a|>1)==>max1==maxfunc(a)
}
function maxfunc(a:seq<int>):int
decreases |a|
{

if |a|==1 then a[0] else
 max2(
maxfunc(a[0..|a|/2]),
maxfunc(a[|a|/2..|a|])
)
}
function max2(a:int,b:int):int
requires a<b || a>b||a==b
{
if a>=b then a else b
}
I am getting the below error-

 Error: failure to decrease termination measure
Execution trace:
    (0,0): anon0
    (0,0): anon5_Else
C:\Users\Dell\Downloads\dafny\prog\recursion\intro\maxofarray.dfy(14,18): Error: failure to decrease termination measure
Execution trace:
    (0,0): anon0
    (0,0): anon5_Else
C:\Users\Dell\Downloads\dafny\prog\recursion\intro\maxofarray.dfy(35,0): Error: failure to decrease termination measure
Execution trace:

```

# Answer
> 1 votes
The problem got solved ,below is the fully verified code.

```
method maxofarray(a:seq<int>) returns (max1:int)
requires (|a|==1)|| (|a|>=2 && |a|>1  )
ensures (|a|==1==>max1==a[0])||(|a|>1==>|a|>=2 ==>maxpred(max1,a[..|a|]))
decreases |a|/2
{
if (|a|==1)
{
max1:=a[0];

}
else
{
var m1:=maxofarray(a[0..|a|/2]);
var m2:=maxofarray(a[|a|/2..(|a|/2+|a|/2)]);
if (m1>=m2)
{
max1:=m1;
}
else
{
max1:=m2;
}
}
}
predicate maxpred(max1:int,a:seq<int>)
{
|a|>1 ==> |a|>=2==>max1==maxfunc(a)
}
function maxfunc(a:seq<int>):int
requires (|a|==1)|| (|a|>=2  )
decreases |a|/2
{

if |a|==1 then a[0] else
 max2(
maxfunc(a[0..|a|/2]),
maxfunc(a[|a|/2..(|a|/2+|a|/2)])
)
}
function max2(a:int,b:int):int
requires a<b || a>b||a==b

{
if a>=b then a else b
}
method maxofarray(a:seq<int>) returns (max1:int)
requires (|a|==1)|| (|a|>=2 && |a|>1  )
ensures (|a|==1==>max1==a[0])||(|a|>1==>|a|>=2 ==>maxpred(max1,a[..|a|]))
decreases |a|/2
{
if (|a|==1)
{
max1:=a[0];

}
else
{
var m1:=maxofarray(a[0..|a|/2]);
var m2:=maxofarray(a[|a|/2..(|a|/2+|a|/2)]);
if (m1>=m2)
{
max1:=m1;
}
else
{
max1:=m2;
}
}
}
predicate maxpred(max1:int,a:seq<int>)
{
|a|>1 ==> |a|>=2==>max1==maxfunc(a)
}
function maxfunc(a:seq<int>):int
requires (|a|==1)|| (|a|>=2  )
decreases |a|/2
{

if |a|==1 then a[0] else
 max2(
maxfunc(a[0..|a|/2]),
maxfunc(a[|a|/2..(|a|/2+|a|/2)])
)
}
function max2(a:int,b:int):int
requires a<b || a>b||a==b

{
if a>=b then a else b
}
Dafny program verifier finished with 4 verified, 0 errors
Compiled assembly into maxofarray.dll

```

---
Tags: proof-techniques, recursion, arrays, divide-and-conquer, termination
---


# Question
Title: How does one prove that DEC does not parameterize DEC?
The $n$th slice of a set $A \subseteq \Sigma^{\*}$ is defined as:

$$A\_n = \\{x \in \Sigma^{\*}\mid\langle n,x\rangle \in A\\}$$

The definition of parameterization is as follows - $C$ parameterizes $D$ (also called $C$ is universal for $D$) if,

$$\exists A \in C \quad\text{s.t}\quad D = \\{A\_n|n\in \mathbb{N}\\}$$

However, I have no idea how to prove that the class of decidable languages (DEC) can parameterize DEC.

# Answer
Okay first you need to know that there exists a numbering $\phi$ for all the Turing-Machines that is $\phi: \mathbb{N} \to TM$ is a computable surjection. This is often called discription number. Now we define: $$ A = \\{\langle p,w \rangle | \text{ the TM } \phi(p) \text{ accepts } w\\} $$ This language is decidable since $\phi$ is computable and using the Universal TM we can simulate $\phi(p)$ on $w$. Thus $A \in DEC$. But now $$ \\{A\_n|\\, n\in \mathbb{N}\\} = DEC $$ because for every TM $B$ there exists a $n\in \mathbb{N}$ such that $\phi(n)$ is an encoding of $B$. Hence $A\_n$ is the language decided by $B$.
> 2 votes

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


title: Simulated Annealing with memory

text:
# Question
Title: Simulated Annealing with memory
I was asked in an exam wether we could improve the SA algorithm by keeping a memory of the best N solutions (so far).

I couldn't find any examples of this being done in practice.

I could only think that we could use this to avoid areas that seem to converge to higher energy levels, and thus complete the search faster.

Is this correct? Are there any other benefits in using memory?

# Answer
> 1 votes
The short answer is, surprisingly, no.

The usual "plain vanilla" SA algorithm keeps track of one best known solution and ultimately returns that. What would be the advantage in keeping track of N-1 additional ones? Remember that a lot of those others are likely to be close to the best known optimum anyway. So what would you do with them?

Restart strategies use the best known solution and restart the chain from there if the algorithm finds itself stuck in an area where the solution is significantly worse than the best known. I suppose that you could pick one of them at random. I don't know if anyone has ever looked into this.

A more common strategy, if you have memory, is to run multiple chains in parallel. This has the additional advantage that it works extremely well on parallel hardware.

Another area worth mentioning is genetic algorithms, which can be thought of as a variant of simulated annealing. This inherently uses a set of solutions rather than one, and solutions are both mutated like SA, and cross-bred.

# Answer
> 0 votes
I would agree with your answer. Also, the memory could help when you are stuck in a local minimum and you already visited a deeper minimum.

---
Tags: simulated-annealing
---


# Question
Title: Checking whether a set of points in the plane can be bi-partitioned with a certain diameter
I am working on a problem in geometry and I encounter the following problem.

> Suppose given $n=2k$ points $P$ in the plane. And we want partition points into two group

Is there an algorithm that decides whether we can $P$ into two groups the size of each group be exactly $k$ and diameter of each group be at most given input $d$? I try to use Linear separability but I get stuck.

# Answer
> 2 votes
Your problem may be mapped into graph partitioning algorithm. There you can use spectral graph partitioning algorithm.

---

I am just giving you brief here. What spectral graph partitioning does is:

1. First you calculate the adjacent matrix($W\_(ij)$) basis on connectivity of your points.
2. From $W\_(ij)$ calculate Degree Matrix(D). It is a kind of matrix where only diagonal elements are nonzero and those diagonal entry are the rowsum.
3. Then find Laplacian Matrix $L$ =$D$ \- $W$

Now there are many things to understand how can be this turned into a optimization problem.

Basically our aim to establish a weak relationship between two clusters(in your case) whose equation is R = $w\_(ij) * (f\_i - f\_j)^2$ where $f$ is the labelling column matrix in your case f consists only of $0$ and $1$.

So our aim is to minimize this R. This R can be mapped to $f^TLf$. So if we are able to determine that $f$ for which $f^TLf$ this minimizes our work will be done.

ONE particular lemma is there by Courant-fisher The second smallest eigen value is the minimum of $f^TLf$ for any $f$ belongs to $R$ subject to condition that $f^Tf = 1$. Taking Lagrange Multiplier as,

$La\_r(x,\lambda)$ = The $fun^c$ we want to optimize - $\lambda$(equality constraint)

$La\_r(x,\lambda)$ = $f^TLf$ \- $\lambda(f^Tf -1)$

If you now perform derivative to this expression wrt $f$ then u will get as

$Lf = \lambda f$ ... familiar with this right.

Now the vector($f$) corresponding to the smallest eigen value($\lambda$) is your labelling vector

**Points to be noted** 1 eigen value allows you to bipartition of the graph. If you have k clusters have to take k smallest eigen value. Now there is another theorem which tells If the graph has k connected components L has k eigenvectors with $\lambda = 0 $. So if you take smallest eigen value which is 0 that will be of no use because the eigen vector corresponding to that value will be constant only. Start from 2nd one if you have 1 connected graph.

For more info: A tutorial upon Spectral

*Time complexity*

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


# Question
Title: uniformly distributed edge weights in an MST
> Suppose that the edge weights in a graph are uniformly distributed over the halfopen interval \[0, 1).

> The question is, how can one sort the edge weights in linear expected time?

I know the definition of expected time for inputs of size n is $\max\_{I \in I\_n} \sum\_{R} P(R)T(I,R),$ where $I\_n$ is the set of all inputs of size $n$ and $R$ denotes the random outcomes on which execution depends, which would be the edge weights in this case.

To sort in linear time, bucket sort would probably be useful.

Source: CLRS, Ch 23, exercise 23.2-6.

# Answer
> 1 votes
Since your weights are reals, the answer probably depends on the specific model of computation that we are using. One strategy might be the following:

Select the first $\ell =3\log n$ bits in the binary representation of each number. In this way all the resulting (truncated) numbers will be distinct with high probability. Indeed, the probability that two *fixed* (truncated) numbers are the same is $2^{-\ell}$ and hence, the probability that there exists a pair of numbers that are the same is at most $n^2 2^{-\ell} = n^2 \cdot n^{-3} = n^{-1}$.

You can then multiply these numbers by $2^\ell$ to obtain integers between $0$ and $2^\ell = 2^{3 \log n} = n^3$. These integers can then be sorted in time $O(n)$ using radix sort.

This is a Monte-Carlo algorithm, i.e., there is a probability of at most $n^{-1}$ that the result will be incorrect. If this is undesirable then you can simply check (in $O(n)$ time) whether the resulting sequence of real numbers is sorted. If that's not the case, sort the reals using any $O(n^2)$-time algorithm. Since this only happens with probability at most $n^{-1}$, the overall contribution to the expected running time will be at most $O(n)$.

---
Tags: algorithms, algorithm-analysis, sorting
---


title: Can a language have more than one DFA?

text:
# Question
Title: Can a language have more than one DFA?
For Example when we consider a DFA that allows the strings having neither sub strings `00` or `11` I can produce the following two DFAs:

# Answer
> 39 votes
First of all, your left DFA is incorrect - it accepts e.g. 011.

Secondly, DFAs can be canonically minimized, so in that sense, you can always find one canonical DFA for a certain language.

But in general, there are infinitely many different DFAs for every language, so you could get different correct answers.

# Answer
> 0 votes
Yes it is possible to get different DFAs for a particular language, these differences often arise in the inclusion or exclusion of certain inputs. Redundant inputs don't negate the validity of DFAs as long as it's correctly accepting the strings in it's accept state & there are no two inputs path on a vertice in the transition diagram-- the main reason of the DFA. So keep cool, if you got an entirely different transition diagram different from that of your professor’s as long as the language gets accepted you're good to go

---
Tags: automata, finite-automata
---


# Question
Title: How to find the temperature scheduling for simulated annealing?
I have a combinatorial optimization problem that I try to solve using simulated annealing.

It is about finding the optimal configuration of N points on a grid. I have the operation swap (swap one point with another one) and move (move one point to a new coordinate on the grid).

I already implemented the simulated annealing algo and estimated the initial temperature.

Now I am wondering if there is a way to find a good temperature schedule. How should I start? So far I only found several schedulings, but it seems like I should use trial and error to find the best one for my problem.

Furthermore, I would like to know if it is ok to consider only one operation (move, swap) at once. Or should I apply several moves and/or swaps and then calculate the energy difference and accept or reject the new configuration. I think, if I make several moves/swaps at once, I will generate states that are far more rejected. Is this correct?

I still couldn't find any nice simulated annealing literature, so I would be happy for recommendations.

# Answer
> 0 votes
Trial and error is all that I know of, alas.

Yes, normally we apply one move, compute the effect on energy, and decide whether to accept this move or not.

# Answer
> 0 votes
I see no better way than to experiment with your problem, hoping that you can draw general conclusions about the behavior of annealing on it. Any problem-specific information you could have about the distribution of the local maxima can be useful.

You can try different starting temperatures and observe the number of trials it takes before the solution stops to improve. You can observe the spread of the values around that "steady state" solution, and possibly study a relation between the temperature and the spread.

Now if you can master this first step, restart observations with lower temperatures from this point, and so on. The goal is to minimize the total number of trials to reach a given accuracy.

---

Unless you have other degrees of freedom, combining several swaps and moves is a way to adjust the temperature. But you need a rule to decide which ones to apply at a given stage.

---
Tags: optimization, simulated-annealing
---


# Question
Title: Binary matrix optimization problem with element co-dependence
Suppose we have an optimization problem where we want to find a binary matrix $A \in \\{0, 1\\}^{n \times m}$ that minimizes the score function defined as $$S(A) = \sum^n\_i \sum^m\_j f\_{ij}(a\_{i-1j}, a\_{ij}, a\_{i+1j}, a\_{ij-1}, a\_{ij+1}) $$

where all $f\_{ij}$ are known, real-valued and bound within $\[-w, w\]$, except for every $f\_{ij}(1, 1, \cdot, \cdot, \cdot)$ and $f\_{ij}(\cdot, 1, 1, \cdot, \cdot)$ which are $+\infty$. In other words, the individual score of any $a\_{ij}$ depends on it and its orthogonal neighbors and no consecutive $1$s are allowed in any column. For the boundary elements, $f\_{ij}$ depends only on the subset of its arguments that exist in $A$.

1. Is there any efficient algorithm to optimally solve it?
2. Is there any efficient algorithm to approximate it?

Any hints/references as to how I can approach solving/approximating this problem (if possible)?

# Answer
If the functions $f\_{i,j}$ can be arbitrary (subject to the constraints in your question), then the problem is $\mathsf{NP}$-hard and inapproximable in polynomial-time unless $\mathsf{P}=\mathsf{NP}$. Unfortunately, the proof is a bit technical. It is a reduction from rectilinear planar 3-SAT. Essentially you can embed a 3-SAT formula into a grid $A$ (to be filled) and use the functions $f\_{i,j}$ to enforce some additional filling rules. In particular, if $A$ violates some rule we will have $S(A)\>0$. If $A$ does not violate any rule we will have $S(A)=0$. All the rules can be obeyed if and only if the 3-SAT instance admits a solution.

To ease the description allow me to forget about the constraint of not having two consecutive $1$s on a column.

There are essentially four types of cells:

* Empty cells: their corresponding function equals $0$ if the value in the cell is $0$ and $1$ otherwise. No other function will depend on these cells. We can essentially set these cells to $0$ and forget about them.
* Variable cells: each of these cells is associated with a variable $x\_i$ of the 3-SAT instance. Writing $0$ in the cell means setting $x\_i$ to false, while writing $1$ means setting $x\_i$ to true. You can imagine these cells as generating a true or false "signal". The function associated to these cells is the constant function $0$.
* Wire cells: these cells force you to copy the same value of some fixed neighboring cell, effectively carrying the signal from the variable cells to the clause cells (see the next item). Writing the "wrong" value in these cells will cause the associate function to equal $1$. Otherwise, the function will equal $0$.
* Clause cells: these cells represent a clause from the 3-SAT instance are always neighbors of $3$ wire cells, which carry the signal encoding the truth values of the variables in that clause. The function equals $0$ if these truth values satisfy the clause and $1$ otherwise. Notice that the function does not depend on the value written in the cell itself.

Here is an example showing a 3-SAT formula, it's planar rectilinear embedding, and the corresponding (still unfilled) grid with empty cells, variable cells, wire cells, and clause cells shown in white, blue, gray, and red, respectively. The arrow in the wire cells shows which value should be copied.

The matrix on the left in the next figure shows a solution $A$ with $S(A)=0$. To handle the restriction prohibiting two consecutive $1$s on the same column it suffices to (i) ensure that, in the embedding, no two wire cells referring to different variables appear as neighbors, (ii) flip the meaning of the values on the wire cells in a checkerboard pattern (see the matrix on the right).
> 3 votes

---
Tags: algorithms, optimization
---


# Question
Title: Period of modulo exponentiation function from factors
The calculation of the period of the "modulo exponentiation" function: $$ f\_a(r) = a^r (mod \ N) $$ is a step of the quantum algorithm for factorizing $N$, where $a$ is a number chosen with some limitation. The quantum circuit is able to find the period of $f(r)$ in time polynomial in the number of bits of $N$. This allows us to calculate the factors of $N$ in polynomial time.

I'm looking for an inverse relation. Is it possible to find the period, from the knowledge of the factors of $N$ (or even $N-1$), with a classical calculation, in polynomial time? Here, "period" means the minimum $r$ satisfying the equation $a^r=1 (mod \ N)$.

If the factors are not enough, I would like to know if there is any other characterization of $N$ that allows us to calculate the period in polynomial time. This latter question is quite vague, since the period itself can be seen as a "characterization" of $N$; to make it more precise, I specify that I'm looking for a "characterization" in the form of a set of numbers $v\_i$, depending on $N$ but not on $a$, such that the period of $f\_a(r)$ can be calculated in polynomial time from $v\_i$ and $a$.

I know that there are several results in number theory connected to this problem, e.g. if $N$ is prime then $r$ divides $N-1$, but I was not able to find a general recipe that always works in polynomial time, nor to show that it is not possible.

# Answer
> 3 votes
The quantity $r$ is known as the *order* of $a$ in the multiplicative group $\mathbb{Z}^\*\_N$. The order of the group is $\phi(N)$, which you can compute if you know the factorization of $N$. Next, you need to factor $\phi(N)$, say $\phi(N) = \prod\_{i=1}^m p\_i^{d\_i}$. For each $i$, find the largest $e\_i$ such that $a^{\phi(N)/p\_i^{e\_i}} \equiv 1 \pmod{N}$. The order of $a$ is then $\prod\_{i=1}^m p\_i^{d\_i-e\_i}$. This works since $\mathbb{Z}^\*\_N$ is an Abelian group which decomposes as a direct group of Abelian groups of orders $p\_1^{d\_1},\ldots,p\_m^{d\_m}$.

When $N$ is prime, $\phi(N) = N - 1$, and so all you need to know is the factorization of $N - 1$.

---
Tags: number-theory, factoring
---


title: Two formulations of path cover

text:
# Question
Title: Two formulations of path cover
Wikipedia gives the path cover definition as:

Given a directed graph $G = (V, E)$, a path cover is a set of directed paths such that every vertex $v \in V$ belongs to at least one path.

I'm reading the paper "On k-Path Covers and their Application" (Funke, S., Nusser, A., & Storandt, S. (2014)) and they gave the definition where we select a subset of vertices $C \subseteq V$ such that for every simple path $\pi$ in the graph we have that $C \cap \pi \neq \emptyset$. (There's also a $k$ constraint but it's not particularly relevant to my problem).

Are these definitions equivalent? One uses a set of vertices and the other uses a set of paths.

# Answer
The definitions are not equivalent. Clearly, as you point out, one is a set of paths while the other is a set of vertices, but even their sizes are unrelated. In fact, since a single edge is a path, the second definition would be equivalent to saying that $C$ is a vertex cover.\* If you want an explicit counterexample, think of a graph consisting of a path of length $2$.

From what I see at a quick glance, the paper studies $k$-Path covers. The $k$ here is critical, since a path $\pi$ needs to be covered by $C$ (i.e., it must contain at least one vertex in $C$) only if $\pi$ is a simple path containing at least $k-1$ edges (i.e., $k$ vertices).

* I'm actually disregarding paths with 0 edges here, otherwise the only feasibly set $C$ would be $V$ itself.
> 1 votes

---
Tags: graphs
---


title: MST with weights in {1, 2, 3, 4, 5}

text:
# Question
Title: MST with weights in {1, 2, 3, 4, 5}
I am given an undirected connected graph with $n$ nodes, average degree $\sqrt{\log n}$, and each edge having integer weight in $\\{1,..,5\\}$. I am asked to describe MST algorithm which is as efficient as possible.

I read https://en.wikipedia.org/wiki/Minimum\_spanning\_tree about Dense Graph and Integer weights, but it seems that I cannot satisfy the conditions to apply the strategy for Dense graphs, and it is unclear to me what is the benefit of the integer weights.

I am thinking of simply applying Kruskal or Prim, but then I am not making use of the additional information that I have on the degree and the weights.

Any suggestion is appreciated.

# Answer
Let $G\_0$ be your input graph, label each edge $(u,v)$ with $(u,v)$ itself. Repeat the following for all values of $i$ from $1$ to $5$:

* Compute a spanning forest $F\_i$ of the subgraph of $G\_{i-1}$ induced by the edges with weight $i$.
* Construct the graph $G\_{i}$ obtained from $G\_{i-1}$ by contracting all vertices in the same connected component (i.e., tree) in $F\_i$ into a single vertex. For each surviving edge, make sure to preserve the original label (even if one or both the original endvertices are now contracted into a new vertex).

At the end of this process, you can obtain a minimum spanning forest $F$ of $G\_0$ by selecting all edges $(u,v)$ such that $(u,v)$ is a label of an edge in some $F\_i$. If $G\_0$ is connected then $F$ is also a MST of $G\_0$.

Since each iteration can be performed in time $O(n \sqrt{\log n})$, the overall time complexity is also $O(n \sqrt{\log n})$. This is clearly optimal since $\Omega(n \sqrt{\log n})$ time is needed just to read the graph.
> 3 votes

---
Tags: algorithms, graphs, minimum-spanning-tree, prims-algorithm
---


# Question
Title: how many bits should I expect to flip, if I flip each bit with probability 1/n?
I am trying to work out some analysis for an algorithm I am trying to write, one step of what I am doing require knowing the answer to the above question.

I know it might sound a bit simple, but I am not sure of the approach (formally using probability theory).

Assume I have an algorithm that loops over a bitstring (x1,x2,x3...xn).

* If my loop decides at each iteration flip x\_i with probability 1/n. How many bits should I expect to flip at the end?
* or an alternative way to see this: If I decide I want to flip k bits in my string and sample u.a.r the number the k integers between \[1 and n\] . what is the probability for a single bit X\_i to be flipped?

Can someone please answer these and/(or preferably) explain the reasoning to answer such questions?

# Answer
> 4 votes
Let $X\_i$ be a random variable that equals $1$ if your algorithm flips the $i$-th bit and $0$ otherwise. Let $X = \sum\_{i=1}^n X\_i$ be the random variable counting the number of flipped bits. Your first question asks about $\mathbb{E}\[X\]$.

The expected value of a random variable is a linear function, therefore: $$ \begin{align\*} \mathbb{E}\[X\] &= \mathbb{E}\left\[\sum\_{i=1}^n X\_i\right\] = \sum\_{i=1}^n\mathbb{E}\left\[ X\_i\right\] = \sum\_{i=1}^n \left(0 \cdot \Pr(X\_i=0) + 1 \cdot \Pr(X\_i=1)\right) \\\&= \sum\_{i=1}^n \Pr(X\_i=1) = \sum\_{i=1}^n \frac{1}{n} = 1. \end{align\*} $$

Regarding the second question, since you say that you want to flip $k$ bits, I assume that you are sampling $k \le n$ elements from $\\{1, \dots, n\\}$ u.a.r. and *without replacement*. In that case the probability of flipping each bit is exactly $\frac{k}{n}$.

If you instead sample *with replacement*, fix some index $i$ and look at the probability of the event $E\_j$ = "the $j$-th sample is *not* $i$". The probability of $E\_j$ is $\frac{n-1}{n}=1-\frac{1}{n}$. Since the $E\_j$s are independent, the probability of *not* sampling $i$ is the product of the probabilities of $E\_1, \dots, E\_k$, i.e.: $$ \Pr\left(\bigcap\_{j=1}^k E\_j \right) = \prod\_{j=1}^k \Pr(E\_j) = \left( 1-\frac{1}{n} \right)^k. $$

Since you are interested in the complementary event, its probability is $1-\left( 1-\frac{1}{n} \right)^k$.

---
Tags: runtime-analysis, probability-theory
---


# Question
Title: Split a graph before actually creating it
Consider a weighted graph $G=(V,E)$ of vertex set $V = \\{v\_1, ..., v\_n\\}$ and weighted edge set $E = \\{\langle v\_i, v\_j, w(i,j)\rangle \mid i, j \in 1, ..., n\\}$, where $w$ is the function that assign the weight of a certain edge. This function $w$ is symmetric.

Suppose I want to partition the graph into multiple components $G\_1, ..., G\_k$:

* each component $G\_i = (V\_i, E\_i)$ is such that $V\_i \subseteq V$ and $E\_i = \\{ \langle v\_i, v\_j, w(i,j) \rangle \mid v\_i, v\_j \in V\_i \\} \subseteq E$;
* it holds that $\forall i, j \in 1, ..., k \quad V\_i \cap V\_j = \varnothing$ and $\bigcup\limits\_{i=1}^k V\_i = V$;
* the set of edges lost by performing the partition is denoted with $E\_\text{lost} = E \setminus (E\_1 \cup ... \cup E\_k)$ and the sum of lost weights is denoted with $w\_\text{lost} = \sum\limits\_{\langle v\_i,v\_j,w\_{ij}\rangle \in E\_\text{lost}} w\_{ij}$

Do exist in the literature heuristics to solve this weighted graph partition problem, running in *linear* or *quasi-linear* time in $n$ (\*), that minimize $w\_\text{lost}$:

1. supposing $w$ is a metric, and
2. supposing $w$ is not a metric, and no further hypothesis holds except for the symmetry?

(\*) solutions having quadratic complexity are not accepted

# Answer
You can't solve this in subquadratic time with any guarantees at all; there is a simple adversary argument. Consider any linear- or quasi-linear-time algorithm, and suppose it outputs the partition $G\_1,\dots,G\_k$. For any non-trivial\* partition, the number of lost edges is more than linear/quasi-linear, so there must exist some lost edge whose weight was not examined by the algorithm; call this edge $e$. It follows that this algorithm will produce the same output regardless of whether the weight on edge $e$ is $0$ or $10^9$ (or some other huge value). As a result, the value of $w\_\text{lost}$ can be arbitrarily high.

So, it follows that for any algorithm that runs in linear time or quasi-linear-time, there exists some input where the partition it suggests is horrible.

If you don't care about guarantees, then you can do anything you want. If you want a very simple heuristic, here is one. Randomly sample linearly (or quasi-linearly) many edges, calculate their edge weights, and compute the $k-1$ lowest-weight edges. For each those $k-1$ edges, arbitrarily pick one endpoint, and put it in a group of its own (containing only that one vertex and no other vertices). Finally, put the remaining $n-k+1$ vertices into the final group.

If the algorithm can choose $k$, then the optimal solution is to set $k=1$ and put all vertices into a single group.

* = for an appropriate definition of "non-trivial"
> 3 votes

---
Tags: algorithms, graphs, max-cut
---


title: Continuation passing transform

text:
# Question
Title: Continuation passing transform
I'm stuck on something in in Shan's article *Shift to Control*, about CPS. On page three he writes the CPS transform

```
x --> (lambda (c) (c x))

(lambda (x) E) --> (lambda (c) (c (lambda (x) E)))

(E1 E2) --> (lambda (c) (E1 (lambda (f) (E2 (lambda (x) ((f x) c))))))

```

Shouldn't the innermost expression on the third line be (c (f x)) instead? With c being the continuation applied to the value `f x`?

# Answer
I would recommend trying a few examples for yourself to see how the transformation works.

Think of the CPS transformation this way:

* Results are passed to continuations.
* Continuations are passed to functions *as the last argument*.

Remember that in the application rule, `f` is a *CPS transformed* version of the lambda, not the lambda itself.

Consider transforming the identity function `(lambda (x) x)`. You get:

```
(lambda (c') (c' (lambda (x) (lambda (c) (c x)))))

```

I have renamed the continuation in the outer lambda to make things clear. I want you to notice what this part means:

```
(lambda (x) (lambda (c) (c x))

```

This is a function of two arguments, `x` and `c`, and it returns `(c x)`. The continuation is passed as the last argument. The effect is that a transformed lambda "swaps" the position of `x` with `c`.

When you use this function in an application, the continuation is passed as the *last* argument to the lambda, `((f x) c)`. It's not backwards, because the *transformed* lambda, `f` swaps them back into the correct order.
> 1 votes

---
Tags: functional-programming, lisp, continuations
---


# Question
Title: Reasoning behind specifically doubling the array size upon reallocation
I am trying to understand the actual reasoning behind creating a new dynamic array of double the size of the original array once it gets full as opposed to any reasonably random number (not too small that buffer is getting filled up too often neither it being too large that half the indices are empty).

Apparently, it has to do with performance but can't get my head around it.

For instance:

```
// original array of size 3 has been allocated which gets filled up at some point

int *arr;
arr = new int[3];

// arr at some point: {1,2,3}

// now there's a request to add a 4 into the array but since arr is full, you delete arr, create a new arr with size 7 instead of 6

newArr: {1,2,3,4,0,0,0}; // assuming you init'd the array to 0

```

I observe the following:

* you copy the elements from the original array -\> O(N)
* you append 4 to the corresponding index -\> O(1)

and that's going to be the same if you were say double the array size as well except you'd be reallocating more frequently.

So where's the difference in performance between reallocating double the size vs any reasonably random size?

**Edit:**

My incomplete understanding:

Sum of power of 2 = `Σ2^(N-1)`

```
N=2 -> Σ2^(1)  = 2^0 + 2^1 = 1 + 2 = 3 (+1) = 4

```

Therefore:

```
1 + 2 + 4 + 8 + ... + Σ2^(N-1) == 3/2 * 2^N ≈ O(N)

```

And, with `M` number of insertions:

```
O(N) / O(M) = O(1)

```

Is ny understanding somewhat correct? If so, how would the equation be different for increasing the array size by a constant `k` (say 100) factor as opposed to doubling?

# Answer
> 1 votes
Lets analyze both the cases.

Assume the growth factor to be $k$.

**Case 1**: Increasing the size by a *constant* factor. The amount of work done to resize the array $m$ times would be

$(1)+(1+k)+(1+2k)+(1+3k)....+(1+mk)$. This is an arithmetic progression whose sum is given by $(m/2)\*(2+(m-1)\*k)$, so of the order $O(m^2)$.

**Case 2**: Increasing the size *exponentially*. The amount of work done to resize the array $m$ times would be

$1+k+k^2+k^3....+k^m$. This is a geometric progression whose sum is given by $(k^m - 1)/(k-1)$, so of the order $O(k^m)$.

Upon looking at these expressions directly, it's easy to say that growing the array exponentially would drag the performance down much more than what growing it linearly would do. And while that is true, the fact is that we won't be growing the array the same number of times in both the cases(unless you somehow manage infinite memory and input).

Lets assume now that you have $n$ elements to be stored.

**Case 1**: $1+mk=n$ --\> $m=(n-1)/k$

**Case 2**: $k^m=n$ --\> $m=log(n)/log(k)$

Clearly When increasing the size exponentially, you in turn have to perform the resizing very few times as compared to growing it linearly. Dynamic memory allocation itself has its associated costs, which you can read upon from here. As to why doubling is used, it mostly makes the calculations easier. There are other options too and this post has some decent discussions on those. A major part of the ***performance*** impact would be the frequency of the resize operations.

---
Tags: time-complexity, arrays, performance
---


# Question
Title: Regular expressions and equivalence classes
I need a little help regarding this problem: Let L = {w ∈ {0, 1} ∗ : w has an even number of 0s and the last character of w is a 1}. Give the equivalence classes of the relation ≡L using regular expressions.

What does it mean with equivalence classes? Is it right that i have found a regular expression for it: 1\*(1*01*0)1 --(i think this a right regular expression)

# Answer
I'm going to take a guess and assume that $\equiv\_L$ is defined as the set of all pairs $(x,y) \in \Sigma^\* \times \Sigma^\*$ such that either (i) $x \in L$ and $y \in L$, or (ii) $x \not\in L$ and $y \not\in L$.

In this case $\Sigma^\* / \equiv\_L$ contains two equivalence classes, namely $L$ itself and its complement $\Sigma^\* \setminus L$.

A regular expression for $L$ is $1^\*(01^\*01^\*)^\*1$. Essentially we make sure that $0$s always come in pairs and that the last character is a $1$.

A regular expression for $\Sigma^\* \setminus L$ is $\varepsilon \mid (0\mid1)^\*0 \mid 1^\*(01^\*01^\*)^\*01^\*$. The first part of the regular expression (i.e., $\varepsilon$) matches the empty word. The second part (i.e., $(0\mid1)^\*0$) matches all words that end with $0$, and the third part (i.e., $1^\*(01^\*01^\*)^\*01^\*$) matches all words with an odd number of $0$s.

---

As Nir Shahar points out, another definition of $\equiv\_L$ could be $x \equiv\_L y$ if and only if $\not\exists z \in \mathbb \Sigma^\*$ such that either (i) $xz \in L$ and $yz \not\in L$ or (ii) $xz \not\in L$ and $yz \in L$. This is the definition used in the Myhill-Nerode theorem, and word $z$ satisfying either (i) or (ii) is called a distinguishing extension for $x$ and $y$.

In this case $\Sigma^\* / \equiv\_L$ contains the following classes:

* $C\_1$: The set of all words that have an even number of $0$s and end with $1$, i.e., $L$ itself. A regular expression for $C\_1$ is given above.
* $C\_2$: The set of all words that have an odd number of $0$s. A regular expression for $C\_2$ is given above.
* $C\_3$: The set of all words that have an even number of $0$s but do not end with $1$. A regular expression for $C\_3$ is $(1^\* 0 1^\* 0)^\*$.

It is easy to see that $C\_1, C\_2, C\_3$ partition $\Sigma^\*$. We just need to show that (A) any two words in $x,y \in C\_i$ satisfy $x \equiv\_L y$, and (B) for $i \neq j$ there are two words $x \in C\_i$, $y \in C\_j$ that do not satisfy $x \equiv\_L y$.

**Regarding (A):** If $z$ were a distinguishing extensions for either two words in $x,y \in C\_1$ or two words $x,y \in C\_3$, then since at least one of $xz$ and $xz$ must belong to $L$ and we must have $z \neq \varepsilon$, $z$ must end with $1$ and must contain an even number of zeroes. However, any such $z$ is such that both $xz \in L$ and $xz \in L$.

If $z$ were a distinguishing extensions for two words in $x,y, \in C\_2$, then since at least one of $xz$ and $xz$ must belong to $L$, $z$ must end with $1$ and must contain an odd number of zeroes. However, any such $z$ is such that both $xz \in L$ and $xz \in L$.

**Regarding (B):** $\varepsilon$ is a distinguishing extension for $1 \in C\_1$ and $0 \in C\_2$. $1$ is a distinguishing extension for $0 \in C\_2$ and $\varepsilon \in C\_3$. Finally, $\varepsilon$ is a distinguishing extension for $1 \in C\_1$ and $\varepsilon \in C\_3$.
> 2 votes

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


# Question
Title: Efficient "radius-search-based averaging" algorithm on a set of 3-D points that lends itself to massive parallelization without locking
I'm looking for a good algorithm for "simple radius-search-based averaging" (or "radius search based sub-sampling") as referred to section 3.4 of the DynamicFusion article.

Relevant excerpt from the paper (to save you some reading time):

> The set of all unsupported vertices is then spatially sub-sampled using a simple radius search averaging to reduce the vertices to a set of new node positions ... that are at least $\epsilon$ distance apart.

As a complication, I need this to run efficiently on a GPU, hence in a setting with massive parallelism *without locking*.

Here is the best I could conjure up so far (I apologize in advance if I'm straying from local norms for writing pseudocode using MathJax + Markdown) :

1. Store vertices (set $V$) in a KD-Tree structure.
2. For each vertex, find all neighbors within fixed radius $\epsilon$ and store their indices in a 2D table, $N$, where $N\_{i}$ is the set of fixed-radius neighbors of vertex $v\_{i}$
3. Initialize Array $F := \emptyset$, for filtered vertex indices, array $A := \emptyset$, for averages, two atomic counters $c\_{ready} := 0$ and $c\_{candidate} := 0$, and the boolean mask array $M$ such that $|M|$ = $|V|$, with each entry of $M$ initialized to $true$.
4. **For each** vertex index $i$ (in parallel):

1. Retrieve $v\_{i}$ from $V$, $v\_{i} := V(i)$
    2. $i\_{filtered} = 0$
    3. $c\_{filtered} = 0$ // regular, local, non-atomic variable
    4. **do**

    {

    1. **Loop** $c\_{filtered} := c\_{candidate}$ **until** $c\_{filtered} = c\_{ready}$
        2. **while** ( $i\_{filtered} \< c\_{filtered}$)

        **exit procedure** if $M(i)=false$ **or** $ distance(V(F(i\_{filtered}), v\_{i}) \< \epsilon$, otherwise $i\_{filtered} := i\_{filtered} + 1$

    } **while** (atomic\_compare\_exchange($c\_{candidate}$, $c\_{filtered}$, $c\_{filtered } + 1$)
    5. $F(c\_{filtered}) := i$
    6. atomic\_increment($c\_{ready}$)
    7. $N\_{i} = N(i)$
    8. Vertex $A\_i := V\_i$
    9. $c\_{vertices} = 0$ // local counter for averaging
    10. **For all** $j$ in $N\_{i}:

    1. $M(j) := false$
        2. $A\_i = A\_i + V\_j$
    11. $A\_i = A\_i / c\_{vertices}$
    12. $A(i) = A\_i$

In the end, we can just mask $A$ using $M$ to get the final set of averaged vertices. Aside from utter ugliness, the obvious problem with this algorithm is that it doesn't actually produce points that are guaranteed to be $\epsilon$ apart, since the averages of these vertex groups are different from the central point of each group. My hope is there will be negligible and there won't be much need to run this recursively (some preliminary experiments seem to confirm this for my input domain).

Another problem is that I'm not sure the whole schema with the counters is going to work properly (my current testing version is single-threaded, python, dumbed-down version of this).

If you see a problem with this approach stemming from parallelization, please save me from hours and hours of debugging :) Also, if you can recommend any viable alternative (or an approach that is guaranteed to produce averages $\epsilon$ apart), please do!

# Answer
> 1 votes
**Why the original proposal doesn't work**

I implemented my original algorithm, and I'll say right away that although it seems to work fine on the CPU, since the two atomics essentially constitute a critical section, on the GPU it causes deadlock. There do exist workarounds, but they critically impact thread occupancy, which makes the idea not worthwhile in my humble understanding.

**A better solution**

I found a much more suitable algorithm for this that is much more easy to parallelize on GPU.

The idea is simple. Here it is for a 2D set of points, but it's easily extendable to the third spatial dimension.

1. We're aiming to bin all points in a square grid, with each square bin having size $r$. This precludes that a rectangular bounding box of the point cloud is pre-computed, which is easy enough to do with a kernel that keeps track of six atomic variables -- maximum and minimum coordinates of the bounding box -- as it's traversing the points. With the minima and maxima computed, it's simple enough to come up with a bin (integral type) coordinate space. In the most basic/simple version of this algorithm, bins can be represented densely by a linear raster array in memory.
2. Subsequent point-binning can be done in a kernel that runs on every point and determines the point's bin based on its coordinates, the pre-computed point cloud extrema / bin coordinate space, and the value of $r$. In the basic version, the bin index can be computed directly from its integral coordinates in the bin space. Instead of storing references to points, each bin can simply contain the (atomic) aggregate and the total (atomic) count of all points that happen to reside in the bin, for easy averaging later.
3. Using the aggregates and the counts, we can then average the points within each bin (in a kernel that runs on all bins with non-zero point counts).
4. Finally, we perform merging of each bin with its immediate neighbor(s) in each direction via weighted averaging (using the counts in each bin). It may be more efficient to run this as a separable kernel that loops the entirety of a spatial dimension (right, down, down-right diagonal), but, for my purposes, I think a more suitable variant will have each kernel work on bin pairs, the pair being neighbors in one dimension, thus running twice for each dimension of interest.

If you just do steps (1-3), you have yourself a regular grid downsampling algorithm.

**Caveats**

While the algorithm certainly satisfies the requirement that no resulting point is within $r$ of any other point, it does not make any guarantee that the set of average points has maximal-possible density. In other words, there certainly might be a more optimal way to pick clusters of points and then average each cluster, still satisfying the $r$-size-gap requirement, but coming up with many more points in the end.

**Potential Improvements**

If the points are clustered in such a way that there are large gaps between the clusters, direct raster approach to storing bins can be sub-optimal, since many of the bins will remain empty and will result in poor thread occupancy. A simple way around this is to use a spatial hashing technique (for an example, refer to this article) or a quadtree/octree structure.

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


# Question
Title: When average , worst and best case time complexity happens in quick sort?
I know recurrence relation corresponding to quick sort worst case is

$T(n)=T(n-1)+T(0)+\Theta(n)$

and time complexity is $O(n^2)$.

This happens when we select pivot which is either largest element or smallest element in the current sub problem.

This can occur when array is sorted in either descending or ascending order and we select either largest or smallest element as pivot.

I also know that best case occurs when median is chosen as pivot, giving recurrence relation

$T(n)=T(n/2)+T(n/2)+\Theta(n)$.

and time complexity $O(n \log n)$.

> **Statement 1:** Any other partition should result in average case.

I have come across problems each time choosing pivot which partition array in some fixed proportion (say $T(n)=T(n/10)+T(9n/10)+\Theta(n)$) ending in average case performance of $O(n \log n)$ (and I understand its proof).

However I have also came across text saying:

> **Statement 2:** Any pivot which does not partition array in some proportion should result in worst case. If $n$th smallest or largest element is selected as pivot, it will result in worst case.

**Q1.** Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?

**Q2.** Is statement 2 true?

# Answer
> 1 votes
The time complexity for particular runs of quicksort can be anywhere between the best case and the worse case. It can be $\Theta(n(\log n)^2)$, $\Theta(n^{\frac32})$, $\Theta(n^{\frac{19}{10}})$ or $\Theta(n^2/\log n)$. Given any $f$ such that $n\log n\le f(n)\le n^2$, we can construct runs of quicksort whose time-complexity is $\Theta(f(n))$.

Let $q$ be a quicksort algorithm. Let $c\_q(A)$ be the number of comparisons used by $q$ on input array $A$. Let $m\_{q,n}=\min\_{\\#A=n}c\_q(A)$ and $M\_{q,n}=\max\_{\\#A=n}c\_q(A)$ for $n\>0$. The following property holds for various versions of quicksort.

**Continuum of comparisons by quicksort**: Given any integer $i$ between $m\_{q,n}$ and $M\_{q,n}$, there is an array $A$ of size $n$ such that $c\_q(A)=i$.

We can replace "comparisons" above by "swaps".

---

> Statement 1: Any other partition should result in average case.
>
> Q1. Is statement 1 true? If no, which other pivot selection strategies could result in worst case or best case behavior?

The "continuum of comparisons by quicksort" shows statement 1 does not make much sense. To determine the asymptotic behavior of a quicksort algorithm, we need to specify the version of quicksort with its partition scheme and which kind of input arrays might be given. It does not make much sense to say $O(n\log n)$ is the time-complexity of the average case without specifying "the average case".

Instead of statement 1, here is the clearer summary, where the average case is when the given input arrays are uniformly random, as described here.

* All quicksort algorithms (that I have seen, including these variants) takes $\Theta(n \log n)$ time in expectation in the average case.
* Some quicksort algorithms choose the pivot that partition an array within some fixed proportion. Those algorithms run in $\Theta(n\log n)$-time in all cases, assuming a linear-time algorithm is used to choose the pivot. However, the constant factors hidden in the big $\Theta$-notations for these algorithms are much larger than those factors for other algorithms.

---

> Statement 2: Any pivot which does not partition array in some proportion should result in worst case. If nth smallest or largest element is selected as pivot, it will result in worst case.
>
> Q2. Is statement 2 true?

Although sounds reasonable, statement 2 is too ambiguous to be verified or refuted. The following is a version that could be proved.

**Statement 3**: The classic quicksort with Lomuto partition scheme or Hoare partition scheme runs in $\Theta(n^2)$-time if the pivoting on every array partition the array into two parts with one part of size $O(1)$. In particular, for any constant $c$, if $c$-th smallest or $c$-th largest element is selected as pivot whenever the size is no less than $c$, it runs in $\Theta(n^2)$ time.

---

**Exercise 1**. Prove statement 3.

**Exercise 2**. Prove "continuum of comparisons by quicksort" for a version of quicksort known to you.

# Answer
> 0 votes
One addition: Always picking the median element is not necessarily optimal. Quicksort spends time *comparing* items and time *moving* items. Picking the median element minimises the number of comparisons, but the number of moves is smaller if we don't pick exactly the median. Depending on the relative cost of comparing and moving items, picking a pivot a bit away from the median can be faster.

# Answer
> 0 votes
It is true that when all partitions fulfill a constant proportion (or better), the $n\log n$ behavior occurs. This is because the size of the partitions decreases in geometric progression.

In particular, the median-of-medians strategy ensures such a ratio.

It is also true that when no partition fulfills a constant proportion, the $n^2$ behavior occurs. This is because the size of the partitions decreases in arithmetic progression.

Statement 1 is wrong. (Unless part of the context is missing or "any other partition" has a special meaning.)

Statement 2 is right.

# Answer
> -1 votes
Remember, for big-O we care about the asymptotic limit. If you choose the $k$th largest (or smallest) element, for constant $k$, then when you make $n$ big enough it's as though you chose the single largest or smallest. The $k$ elements on the other side just aren't enough to matter any more. So statement 2 is true.

Statement 1 is also true; you say you understand the proof of it, so I'm not sure how much detail to go into here. But intuitively, the amount on each side of the pivot grows proportionally to $n$. That's what makes it different from the constant $k$.

---
Tags: sorting, quicksort
---


# Question
Title: What distributed consensus algorithms don't rely on a time source?
I'm looking for information about distributed consensus algorithms that:

* maintain a consistent transaction log across all healthy nodes
* have similar high-availability properties to Paxos (i.e. not liveness, but practically very likely to terminate in reasonable time)
* make progress with 2F+1 nodes despite F simultaneous node failures
* where failures can include complete/partial/simplex network partitions
* work over a reliable, unicast-ordered, but potentially non-timely network
* do not use system/wall clock time

Paxos and Raft both fulfil all criteria but the last – I'm wondering if there are any variants or other algorithms that fulfil all? I have looked but all variants I've come across seem to use some form of timeouts.

# Answer
> -1 votes
All of consensus (and not only consensus) algorithms use time for timeouts - e.g. if no heart beat happened for X milliseconds of wall clock time, then assume an issue and fix it.

How would you define timeout without time? And in general, how do you define fail mode in your system without using time?

---
Tags: distributed-systems, consensus
---


# Question
Title: How does a single-node system get Availability in CAP theorem?
I have a question. I read many blogs, websites about CAP theorem. They say that single-node systems are CA, but how can it be "A" if that single node goes down ? Because if it does, the system will be unavailable, right ? And is "availability" in CAP equal to "availability" in HA of distributed systems ?

# Answer
> 2 votes
Awesome question!

1. We can build this chain:

One have to pick between C and A only when partitioning is happening. If there is no partitioning at any given time, then both C and A are reachable.

Since a single node system can not be partitioned, then it has to be both C and A.

2. Another option is to take a system and try to put it into a category: CP, AP or CA.

* CP - those system who sacrifice availability when partitioned
* AP - those system who sacrifice consistency when partitioned
* CA - those system who sacrifice partitioning; but there is only one type of systems without partitioning - single node systems!

3.

At the end of the day, this confusion is based on theorem being applied out of context.

Every theorem has a specific context where it can be applied. CAP is applicable for distributed systems, hence it is not applicable to single node system.

---
Tags: distributed-systems, computer-networks
---


# Question
Title: How to generate globally unique timestamps for transactions in distributed database systems?
According the paper \[1\] (Section 4), **timestamp ordering (T/O)** is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following, it reads

> Each transaction is assigned a unique timestamp by its TM (transaction manager). The TM attaches the timestamp to all `dm-reads` and `dm-writes` issued on behalf of the transaction, and DMs (data manager) are required to process *conflicting* operations in timestamp order.

However, this paper did not explain

> **Question:** How to generate the globally unique timestamps for transactions in distributed database systems (assuming no centralized coordination)? What are the commonly used techniques (with references) in this area?

Specifically, is the `<local clock, site-id>` pair sufficient and appropriate as a timestamp mechanism? If not, why?

---

\[1\] Concurrency Control in Distributed Database Systems by Philip A. Bernstein and Nathan Goodman. Computing Surveys, Vol.13, No., 2, June 1981.

# Answer
> 1 votes
If the only property you need is global uniqueness - serverId+timestamp is good enough. Since every server has one Transaction Manager, that will guarantee uniqueness within one server and ordering; combine with unique server id and that gives global uniqueness.

This types of ids are globally unique, but are not globally ordered. Which is alright in case of transactions itself not being distributed - one transaction is executed by one server.

Edit below is about ordering

In the proposed method (nodeId+timestamp) all transactions do have total order - this comes from the definition - since every transaction id is unique, then we can take any two transactions and compare which one goes first.

But it is important to remember, that that order is not really related to real time - there is no (reliable) way to say which transaction happened first in practice.

Also, this order won't give causality. For example, let's say we executed transaction Ta on node A and based on result of Ta we executed transaction Tb on B.

In total order it is possible that Tb will come before Ta.

And to close the ordering note: if you do need total order with respect of causality, Lamport Timestamp is the way to go.

---
Tags: reference-request, distributed-systems, concurrency, database-theory, databases
---


# Question
Title: Why doesn't this implementation of Skip List simply return the current node when its key is equal to the query key?
I was studying Skip Lists in section 3.10 of *Advanced Data Structures* by Peter Brass and was confused about a detail of how the search algorithm in implemented. (This is self-study, *not* homework).

The book explains the `find` algorithm for a Skip List as follows:

> ...any access to an item, given a query key, starts on the list of the maximum level that currently exists. On this list we move until the key of the next item on the list will be past the query key; then we go down a level and repeat the procedure until we are at the bottom level. There we either find the queried item, or, when the next item is already past the query key, no such item exists.

The code sample for this (written in C) from the book is as follows.

First, they define the following structure:

```
typedef struct tr_n_t {
    key_t key;
    struct tr_n_t *next;
    struct tr_n_t *down;
    /* Possibly other information */
} tree_node_t;

```

Next, here is the actual `find` method:

```
object_t *find(tree_note_t *tree, key_t query_key)
{
   tree_note_t *current_node;
   int beyond-placeholder = 0; /* This is a C idiom where ints can be used like booleans - 0 is false and 1 is true */
   if (tree->next == NULL) /* empty skip list */
       return(NULL);
   else
   {
       current_node = tree;
       while (current_node->down != NULL)
       {
           while (current_node->next != NULL && current_node->next->key <= query_key)
           {
               current_node = current_node->next;
               beyond_placeholder = 1;
           }

           current_node = current_node->down;
       }
       /* This is the code I'm confused about */
       if (beyond_placeholder && current_node->key == query_key)
          /* Why not just return current_node here? Why current_node->next? */
          return ((object_t *)current_node->next);
       else
          return(NULL);
   }
}

```

I'm particularly confused about the following:

```
if (beyond_placeholder && current_node->key == query_key)
   return ((object_t *)current_node->next);

```

Why does it return `current_node->next` instead of just returning `current_node`? Am I missing something about how the algorithm works?

# Answer
> 1 votes
I have checked the book and it seems that in the implementation, when the node holding the queried key is found, the code `current_node->next` retrieves the object held by the node, which is also the reason for the cast:

> `((object_t *)current_node->next)`.

You can check the diagram of the skip list below, which was taken from the book and notice that the `next` field of the nodes at the lowest level points to an object instead of a node:

If you check the implementation of find for search trees (pages 31-32), the same idea is used, but instead of `next`, the `left` field was used to hold the object.

---
Tags: data-structures, lists
---


# Question
Title: Why does a prepare message wants a promise that an acceptor is never to accept a proposal numbered less than its propose sequence value? (Paxos)
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

On page 4 of the paper, at the bottom where they outline what a prepare request looks like it says:

> "A proposer chooses a new proposal number n and sends a request to each member of some set of acceptors, asking it to respond with:
>
> (a) A promise never again to accept a proposal numbered less than n,
>
> (b) ... "

Why does prepare message extract such promise from the set of acceptors that receive such a prepare message? What is the goal and what safety guarantee does it provide? How does it aid Paxos into reaching a consensus to a certain value? How is it crucial so that a majority can reach agreement?

I did some further research to try to answer this question and went to the following yale university notes:

http://pine.cs.yale.edu/pinewiki/Paxos

These notes try to justify this point by saying:

> "... proposer tests the waters by sending a prepare(n) message to all accepters where n is the proposal number. An accepter responds to this with a promise never to accept any proposal with a number less than n (**so that old proposals don't suddenly get ratified**)... "

Basically, the way they justify that step is by saying so that old proposals don't get ratified/accepted. Which I kind of see why they said that, since if a decision has happened, that rule definitively avoids the consensus from being reversed, which is nice. But, however, the reason I did not feel very convinced about it yet is because it seems to damage termination a lot. What if if a majority was about to be formed in the past and the proposer was ready to send the propose(n) and now because a different prepare(n') was sent its not able to reach agreement? I can't seem to convince myself that that this step is 100% a good idea.

Unless the only reason for that step is because they just want to guarantee that once a value has been chosen/decided, by adopting this rule, its impossible that any old proposal reverses the decision?

Again, I did some further research by reading the yale article and now it says:

> "The rule that an acceptor doesn't accept any proposal earlier than a round it has acknowledged means that the value v in an ack(n, v, n\_v) message never goes out of date—there is no possibility that an acceptor might retroactively accept some later value in round n' with nv \< n' \< n. So the ack message values tell a consistent story about the history of the protocol, even if the rounds execute out of order."

However, its not obvious to me why retroactivity might be bad (unless in the case that I already mentioned). Retroactivity could be good if it somehow manages our protocol to reach consensus. Still the only reason I see for such a rule is so that one doesn't reverse a decision by accident once a value has been agreed on.

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

# Answer
Without N being monotonically incremented this may happen:

1. Proposer P1 get promises from every Acceptor for N=1
2. Proposer P1 goes to slip (e.g. java garbage collection kicks in)
3. Another proposer P2 with N=2 gets promises and gets its value V2 accepted by all acceptors - consensus happened.
4. Proposer P1 wakes up and sends accepts to all, without smaller N being rejected, the consensus will change its decision - broken logic.

You could find other examples, when increasing N is important. Think about case when acceptors already accepted some values and proposers has to respect that.

The important part to understand about epaxos - it does not really have to stop; after a consensus happened, proposers may keep proposing new values and N will keep increasing. The algorithm makes sure that while N keep increasing, the same value is kept being sent to learners.

Since in reality proposers, learners and acceptors are same boxes (each box/server/node runs all three nodes), proposers should stop proposing after their learned about a consensus.
> 0 votes

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


title: Distributed transaction problem

text:
# Question
Title: Distributed transaction problem
Let's suppose there are two banks, Bank A and Bank B. A transaction needs to happen that transfers money from an account in Bank A to an account in Bank B. Bank A and Bank B have separate banking systems which makes this transaction a distributed one. From what I understand following is what happens, I refer the system of bank A as A and the system of bank B as B,

```
A initiates the transaction
A sends a message including the amount to B
A waits for a response from B
B adds the amount to the account send a response to A
A receives the response and deduct the amount from account
Transaction completes.

```

A can complete the transaction if it received the response since it is a guarantee that B has done the addition, but if A doesn't receive a response, it cannot guarantee that B has done the addition, so it cannot complete the transaction. In that case, what if B has done the addition successfully but the response message was lost in transit. Now A hasn't done the deduction while B has done the addition which is an inconsistent state. How do we solve that problem?

# Answer
> 0 votes
May I ask to read about two phase commit, and then three phase commit?(wikipedia has a good enough summary on that)

The high level idea is that there is a transaction coordinator, which makes sure everything goes as it should. That coordinator commits a distributed transaction by first asking every system to prepare for commit; and after every system reports back the coordinator asks to execute the actual commit.

In case the coordinator can't reach a system for a commit - the coordinator will retry forever (or notify admin). During that time, the overall transaction will be partially committed.

It is completely different topic on how to make the coordinator fault tolerant.

---
Tags: distributed-systems, transactions
---


# Question
Title: Why does the proposer sends an accept request with the same value it got from the acceptor?
In the second phase of the paxos algorithm, the proposer issues an accept request with the number `n` and the value `v` it got from the acceptor, if the acceptor has already chosen a value previously. My questions is why the proposer is doing this? Because once a value if chosen it is permanent and cannot be changed, so in this case the proposer is just learning the chosen value, which was sent in the response of the prepare request. Why would it asks to accept a value already accepted?

# Answer
> 1 votes
This is to make sure that consensus value won't change.

For example, let's say we have a system with two proposers (P1, P2) and three acceptors (A1, A2, A3) (and few learners).

Let's say that both P1 and P2 are trying to get their values accepted: V1 and V2.

Due to some delay (e.g. garbage collector, network issue) P2 is delayed, so P1 gets its value V1 to all acceptors. As soon as two nodes accepted the value, the consensus is reached and learners will learn about it.

Now P2 wakes up (or network gets a fix) - P2 offers its value to every acceptor, but gets back \[some N, V1\]. If P2 ignores V1 and keep pushing V2 - that will override the current value, and consensus will change - learners will see that suddenly there is another value as agreed one.

To make sure the selected value never changes, proposers have to re-propose a value which has been already proposed, instead of pushing their new one.

---
Tags: distributed-systems
---


# Question
Title: What is the difference between broadcast and gossip/epidemics?
Everything is in the title.

What is the difference between broadcast and gossip in the context of message-passing distributed systems?

According to Wikipedia, gossip and epidemic protocols/epidemics are synonym.

Thank you for your help.

# Answer
While sometimes used as synonyms, to me, gossiping protocols are certain flavor of broadcast algorithms, where the message is flooded in a non-structural (commonly, random) way and spreads to the network.

In contrast, a non-gossiping broadcast algorithm may, for instance, deliver the message via a (predetermined) spanning tree, rather than let the message spread arbitrarily.

See, e.g., https://www.gsd.inesc-id.pt/~ler/reports/joaoleitaomsc.pdf
> 2 votes

# Answer
With some generalization (and subjectiveness), gossip is set of one-to-one communications and broadcast is one-to-many communication. From this definition, gossip is a subset of broadcast.

Or, broadcast is the goal, and gossip is one of tools.

Or (and?):

In gossip, after a node decided to spread a message, they rely on others to get that done and the original node has no info on progress.

In broadcast case, there is a dedicated node, whose job is to push message to other nodes, maybe even to other broadcasters.
> 0 votes

---
Tags: distributed-systems, computer-networks, network-topology, message-passing
---


# Question
Title: Approximation ratio on (1, 2)-metric Travelling Salesman Problem (TSP)
I encountered a problem, where I am given a (fully-connected) graph within a metric space, where each edge weight is either 1 or 2.

My task is to prove that the following greedy algorithm gives a $\frac{3}{2}$-approximation for finding a TSP path: Start from an arbitrary node, pick the nearest neighbour node, go to this node and pick its nearest neighbour. Procedure is repeated until all nodes are picked, so that a valid cycle is produced.

I have seen more advanced techniques to solve the problem more efficiently here, which, however, did not help me.

My attempt was: Take any 3 nodes. Since we have a fully connected graph, the edges between the 3 nodes must form a triangle, and since we have a metric space, possible triangle sides are: $\\{ (1,1,1), (2,2,2), (2,2,1) \\}$. Since we are looking for path, we will never take all sides of this triangle, but at most 2. Since we always make our choice greedily, if the triangle is with sides $(2,2,1)$, we will never pick the 2 sides of length 2 together, but we will pick a side of length 1, and a side of length 2, hence resulting of weight from this triangle is 3.

I am stopping here, as I am not confident already.

# Answer
> 3 votes
Call an edge of weight $1$ a light edge.
Call a node incident to a light edge a light node.
Suppose the optimal travelling cycle contains $k$ light edges.

Consider those $k$ edges. Since these edges are part of a cycle, a node is incident to at most two of them. Since every edge is incident to two nodes, there are at least $k$ nodes that are incident to them. That is, there are at last $k$ light nodes.

For each light node, the greedy algorithm will choose at least one light edge incident to it unless it is the last node chosen by the greedy algorithm. So at least $(k-1)/2$ light edges will be selected by the greedy algorithm.

Let $n$ be the number of nodes in the graph. Since the number of edges in the travelling cycle is $n$, $k\le n$.
The weight of the optimal travelling cycle is $2n - k$.
The weight of the cycle selected by the greedy algorithm is at most $2n - (k-1)/2$.

$$(2n-(k-1)/2)- \frac32(2n-k)=\frac{k+1}2-n\le \frac{n+n}2-n=0. \quad\checkmark$$.

---
Tags: algorithms, graphs, traveling-salesman, path, metrics
---


# Question
Title: What's the difference between strong consistency and sequential consistency?
How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs

> ... the result of any execution is the same as if the operations of all the processors were executed in some sequential order, and the operations of each individual processor appear in this sequence in the order specified by its program. A multiprocessor satisfying this condition will be called **sequentially consistent**.

Spanner docs:

> Strong Consistency All accesses are seen by all parallel processes (or nodes, processors, etc.) in the same order (sequentially)5 In some definitions, a replication protocol exhibits "**strong consistency**" if the replicated objects are linearizable.

The `5` in that doc is a link to the wikipedia page, which apparently hasn't ever cited any sources. I can't seem to find any original source for it. The "some definitions" mentioned seem to be nowhere to find online.

What's the difference between strong and sequential consistency?

# Answer
Let me describe sequential and then strong consistency to highlight the difference.

Sequential consistency implies that there is some order without any timing guaranties. For example, let's say we have a system where nodes have some state machines and these machines process some events.

In a sequentially consistent system, all these events have the same processing order - A,B,C,D - hence state machines execute exactly same sequence. But if you ask a specific node about its state - you can get any of those, as there is no timing guarantee. From a readers point of view - different nodes return different results.

But if a reader reads from one singe node, in a sequential system, the reader will see states in the same correct order: A,B,C,D - again - there is no timing guarantee when it will happen, but if it will, the order is set.

Imagine a counter in a sequentially consistent system - let's say the counter counts visitors on a website. Clearly the counter is always increasing. If a reader will keep reading the counter from the same node, they will see increasing counter - the counter never moves in an opposite direction. But reads from different nodes may give any results.

Keeping in mind a visitor counter example; what will make that system strongly consistent? This should be true:

* after a counter increment happened
* all next reads will see the new value

It's the same as - there is a point in time, when all reads will see the new value.

There are some details about reads being executed before the write ended (writes and read happening at the same time), I'll leave that for another post.

Edit: I woke up with a though to clarify sequential consistency

Sequential consistency has SOME order - this order will be respected on each node. So if I send three signals to a sequentially consistent system: A, B and C; there will be SOME order for these events to be processed - ABC, BCA, CBA... But whatever order will happen, the order will be the SAME everywhere.

In a sequential system order of events may not match real life order of events. In strongly consistent system the order will be predictable - sending events one by one A,B,C will create a processing order of A, B, C
> 1 votes

# Answer
In the case of the Spanner doc: it appears to be more strict than linearizability due to transactions. The difference between linearizability and sequential consistency is that latter doesn't need to preserve the real time ordering of requests.

https://jepsen.io/consistency/models/linearizable

The combination of linearizability and transactions is called strict serializability:

https://jepsen.io/consistency/models/strict-serializable

I'm not sure if spanner is supporting strict serializability.
> 1 votes

# Answer
This is sequential consistency:
> 1 votes

---
Tags: distributed-systems
---