# Question
Title: Diameter-constrained Minimum Spanning Tree Problem
The diameter-constrained Minimum Spanning Tree (MST) problem is as follows: you have a undirected weighted graph $G = (V,E)$ of different weights where $V$ is the set of vertices and $E$ is the set of edges between vertices, and a constant $d$. The goal is to find an MST such that the diameter (i.e., the maximum distance of the shortest paths between vertices) of the MST is at most $d$. My question is that I am debating whether the following is true or not:

> Once you have an MST of a graph $G$, if the diameter of the MST is $\>d$, then is it true to say that there exist no feasible solution.

Also, once you have a MST of $G$, then is the diameter of that MST the maximum diameter of $G$? or minimum? or what could be said about the diameter of a MST?

# Answer
There is no direct relationship between the diameter of a (minimum) spanning tree and the total cost of the tree1. Consider the following example:

The spanning tree on the left (whose edges are highlighted in red) is minimum. Its total cost is 7 and the diameter is equal to 5. In contrast, the spanning tree on the right is not minimum (since its total cost is 12), but it has a smaller diameter: 4.

The same situation may occur when two spanning trees are minimum, as suggested by Yuval. Consider the following example (for the complete graph $K\_4$):

In this case, the total cost of the two Minimum Spanning Trees (MST) is 3; however, the MST on the left has a diameter that is equal to 3, while the MST on the right has a smaller diameter: 2.

This counter-example disproves your assumption:

> It is, indeed, possible to find two different MSTs $T$ and $T'$ whose diameters are $\gt d$ and $\leq d$, respectively, within the same weighted undirected graph $G$.

---

1. Note that **Minimum-Diameter Spanning Trees** (MDST) can be found in polynomial time, but the problem becomes NP-Hard when we also want the MDST to be minimum (i.e., when we want the total cost of the tree to be minimized).
> 7 votes

# Answer
Consider the complete graph $K\_n$ in which all edges have the same cost. All trees are MSTs. They have diameter ranging from $2$ all the way to $n-1$.
> 8 votes

---
Tags: graphs, weighted-graphs, spanning-trees, minimum-spanning-tree
---


# Question
Title: Triple nested loop where outer and inner loop are dependent on n
I am trying to count the exact/total number of iterations these nested for-loops are executed:

```
procedure P (integer n);
 for (i: 1 to n)
  for (j: 1 to 10)
   for (k: n to n+5)
    x := x + 1;

```

I know that the first for loop runs (n-1) times, the second loop runs 10-1 (9) times, thus making the time complexity so far 9(n-1). I know that the the third loop will run n+5-n (5) times, but I am not completely sure because of the n involved. I believe with this calculation added, the total runtime will be 5(9(n-1)) which will translate to O(n). In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates. Thanks in advance.

# Answer
> In general, I am wondering if this approach of multiplying the iterations of each loop is a good approach to solving worst case running time and big-Theta estimates.

Basically, yes. But you don't really multiply: As explained here at length, you have *nested sums*. In your case,

$\qquad\displaystyle \sum\_{i=1}^n \sum\_{j=1}^{10} \sum\_{k=n}^{n+5} 1$

(if we count the number of assignment operations) is easy to evaluate because the loops do not depend on each other. It *looks* like multiplication here, but if you get things like

```
  for i = 1 to n
      for j = 1 to i
          foo

```

that does not work anymore.

Note that worst-case considerations and asymptotics do not enter the picture here.
> 0 votes

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


# Question
Title: Longest double increasing subsequence (LIS variant)
I'll start with the definitions:
Let $S = s\_1s\_2...s\_n$ be a sequence of $n$ integers. A double increasing subsequence of $S$ is a sequence $P=p\_1p\_2...p\_k$ (not necessarily continuous) where for each $2\<i\leq k$ we have $p\_{i-2} \< p\_i$. For example, if $S = 1 \space 4\space 2\space 7\space 1\space 6$, a possible double increasing subsequence is $P = 1\space 2\space 7\space 6$ because $7 \> 1$ and $6 \> 2$. (For every sequence $S$ with more than 2 elements, there's a trivial subsequence of length 2) The problem is to determine the length of longest double increasing subsequence (LDIS) of a given series of integers, $S$.

This is what I've done: I defined $C\[i\]$ to be the length of the LDIS of the series that ends with $s\_i$, and $E\[i\]$ to be the element before the last element of the LDIS that ends with $s\_i$. In the example aforementioned, $C\[6\] = 5$, and $E\[6\]=7$. If there are several options for $E\[i\]$, we'll take the minimal one. For example for $C\[5\] = 2$ we have 3 different options for LDIS, all of lengths 2: $4 \space 1$, $2 \space 1$ and $7 \space 1$ (Trivial LDIS's), so we'll define $E\[5\] = 2$.

Now my dynamic programming solution is just like LIS solution (the $n^2$, not the $nlogn$):
If $C$ and $E$ are my $n$-sized arrays, $C\[1\] = 1, E\[1\] = \inf$(meaning there's no previous value), $C\[2\]=2,E\[2\]=s\_1$, and for every $2\<i\leq n$ we finding $C\[i\]$ by iterating over the previous $i$ calculates values, and we take the maximum over the $C\[i\]$'s such that $s\_i\>E\[i\]$, plus 1. (Again, if there are several candidates, we take E\[i\] as the minimal of the possible options) After calculating all $n$ values, we iterate over the array and choose the index that hold the maximal $C\[i\]$.

This is my mind set in general, maybe I've missed several details but I believe I delivered the idea. Now these are my problems with my solution:
1) It misses strong, well defined recursive formula. I can phrase some sort of recursive relation according to the regularity of the question, but it feels kinda forced. (Despite of the iterative solution I've describe, which is fairly simple)
2) I've ran the algorithm on several examples and it seems to give a right answer, but as a consequence of 1, I have hard time "believing" my solution is correct. I feel like there's more simple and elegant solution to the problem.

Any ideas will be vastly appreciated, thanks in advance.

# Answer
> 1 votes
A counter example where your algorithm fails: S = 0 7 1 4 6 5 3 2.

Expected : 5, your algorithm would produce 3

There is an O(n^3) dynamic programming based algorithm for this if you are interested :)

---
Tags: algorithms, dynamic-programming, recursion, correctness-proof
---


# Question
Title: What language should the following DFA recognise?
My question is: what language should the following DFA recognise?

It seems that it should contain an odd number of substrings in the form 11\*0. However, I am not sure whether there are any other conditions.

# Answer
> 1 votes
Arrive at the answer by following all paths from the start state to the accepting state identifying the 'tail recursion':

```
  0*1+0+(1+0+1+0+)*
= 0*1*100*(1*100*1*100*)*
= 0*11*00*(11*00*11*00*)*

```

Intuitively, these are all strings over `{0,1}*` with an odd number of `10` substrings which is equivalent to the characterization you gave.

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


# Question
Title: Solve recurrence by repeated substitution
I am solving a recurrence using repeated substitution method and I am almost done but it seems to me that I need some additional work to finish correctly. I am including an image of my work because typing would be very time-consuming. I will appreciate your feedback.

I can see that the problem says that $n = 2^k$ so $k = log\_{2}n$ so I can replace every $k$ by $log\_{2}n$

# Answer
Question:

> $T(n) = 4T(\frac{n} {2})+n ,\hspace{0.5cm} if \hspace{0.5cm}n \geq 2 $
>
> $\hspace{1.0cm} = 1 ,\hspace{2.2cm} if \hspace{0.5cm}n = 1 $

Solution by substitution method:

Generalized form:

$T(n) = 4^kT(\frac{n} {2^k})+n\sum\_{n=1}^{k-1}2^i$

Until here you are good, but after this we can further simplify as below:

> $\sum\_{n=1}^{k-1}2^i$ is a finite geometric progression(GP), thus we use the formula:
>
> $S\_n=\frac{a\_1(1-r^n)} {1-r} \hspace{0.5cm} when \hspace{0.5cm} r\neq1$
>
> $S\_n$ = sum of GP with n terms
>
> $a\_1$ = the first term
>
> r = common ratio
>
> n = number of terms

$T(n) = 4^kT(\frac{n} {2^k})+n(2^{k-1}-1)$

put $\frac{n} {2^k}= 1$ ie., $k=\log\_2 n$

> $T(n) = 1 ,\hspace{2.2cm} if \hspace{0.5cm}n = 1 $

$T(n) = 4^{\log\_2 n}T(1)+n(\frac{n} {2}-1)$

$T(n) = n^{\log\_2 4}+n(\frac{n} {2}-1)$

$T(n) = n^2+\frac{n^2} {2}-n$

Thus, $T(n)=O(n^2)$
> 2 votes

# Answer
This is the guess & proof method as explained over at our reference question. You have a guess, now prove it correct! The canonical choice would be an inductive proof.
> 2 votes

---
Tags: recurrence-relation
---


title: Reader and Writer mutex

text:
# Question
Title: Reader and Writer mutex
I am looking over the classic **Reader and Writer Problem**

Just to give a quick overview:

* Many readers can be in CS (*as long as no writers are*)
* Only one writer can be in the CS (*with no combination of other readers/writers*)

So the solution is:

> binary semaphore wrt, mutex = 1;
>
> int No\_of\_Readers = 0;

**Writer Process**

```
wait(wrt);
write
signal(wrt);

```

**Reader Process**

```
wait(mutex);
No_of_Readers ++;
if (No_of_Readers == 1)
   wait(wrt);
signal(mutex);

Read
wait(mutex);
No_of_Readers --;
if (No_of_Readers == 0)
   signal(wrt);
signal(mutex);

```

My question is simple but I just don't understand it, what is the use of the binary semaphore mutex? why do we have to `wait(mutex)` when we enter **Reader Process** and then also `wait(mutex)` after we *Read* ?

If someone can give a clear explanation that would help me completely understand this algorithm I am just getting tripped up on that little part.

# Answer
> 4 votes
Lets begin with defining some terms.

> Semaphore is one form of software implementation for process synchronization. It's an *int* value that is used by processes for the purpose of signalling. Only three atomic operations: initialize, increment and decrement, can be performed.
> A binary semaphore is restricted type of semaphore which only takes three values, 0 and 1.
>
> wait(): Process executing wait() is blocked if the value is zero. If the value is one then, the process is allowed in critical section and value is decremented to 0.
> signal(): This checks if any process(es) are blocked (semaphore value equals 0). If yes, then a process is unblocked. If no, then value of semaphore is set to one.

**Writer's Code**
Writer process code is simple. wait() is used to enforce mutual exclusion. When wait(wrt) is executed wrt is decremented to 0 from 1. So, as long as there is on writer in the critical section, no other writer or reader process has access to the section. After performing it's task, signal() is implemented to allow other blocked process (if any) to execute over the critical section. signal(wrt) increments the value of wrt from 0 to 1.
**Reader's Code**
'mutex' variable is used for synchronization among different reader processes. No\_of\_Readers is a shared variable among reader processes. So, if more than one process is updating this variable then it's very likely that we will end up with wrong value. Thus, the first wait(mutex) and signal(mutex) is used to create a block, which only allows one reader to update (increment) the value of Number\_of\_Readers. When wait(mutex) is called the mutex is decremented to 0 (from 1). This makes sure that no other reader process will try to update the value of Number\_of\_Readers. After updating the value of Number\_of\_Readers siganl(mutex) is called. This increments the value of mutex releasing the section to be used by other readers.

> if(Number\_of\_Readers == 1)

implies that the current reader process is the first reader process to access the main critical section. Thus it is his duty to make sure that the coming writer processes are blocked. Thus wait(wrt) is enforced. Subsequent readers coming don't need to do that, as the first reader has already signalled writers to be blocked.
In the second block of the code, Read operation is being performed by the process(es). After a process has performed it's reading task it will exit the code section. The third block of the code is exit portion. Here also wait(mutex) is implemented as we only want one reader process to update the value of Number\_of\_Readers. A reader process implementing this will decrement the value of mutex to 0 (from 1), signalling other reader processes not to update the value of the variable. After value is decremented, process checks for

> if(Number\_of\_Readers == 0)

If this condition is satisfied, then it implies that the current reader process is the last one to exit. Thus, it is the responsibility of this process to signal(wrt). This will increment the value of 'wrt' to 1 allowing writer program to enter is required. Value not satisfying implies that there are still reader process(es) in the critical section and thus signal(wrt) is not executed. After Number\_of\_Readers is updated singal(mutex), increments the value of mutex (to 1), is called allowing other reader processes to access this value for updating.
Thus wait(wrt) and signal(wrt) are used to synchronize between 'Reader and Writer' processes. While wait(mutex) and singal(mutex) are used for synchronization among different 'Reader' processes. This makes sure that the value of Number\_of\_Readers value is not updated by many reader processes at the same time.

# Answer
> 4 votes
"No\_of\_Readers" is a shared variable hence, mutex is used to provide mutual exclusion to maintain data consistency.

Consider the statement : No\_of\_Readers ++; In high level language it is only one statement but in machine level it is a combination of more than one statements like shown below: ( Machine languages are architecture dependent so please do not go into the syntax)

```
    Statement 1: MOV No_of_Readers, R0
    Statement 2: INC R0
    Statement 3: MOV R0, No_of_Readers

```

Consider the scenario where binary semaphore ( mutex) is not used.
Now suppose the first process P1 ( a reader ) executed Statement 1 and Statement 2.
Initially value of No\_of\_Readers was 0.
After execution of Statement 1 '0' value was moved to the register R0.
After Statement 2 R0 value became 1.

Note that this incremented value is not yet reflected into No\_of\_Readers.
After this P1 got preempted and another process P2 got into execution. P2 will find the value of No\_of\_Readers as '0' and will make it value '1'.

At this point P1 again gets a chance to execute and it resumes its execution from Statement 3. But as the registers value was incremented to 1 by P1, it will write '1' into No\_of\_Reader.

Here is where the problem is: Even though there are 2 readers but the variable No\_Of\_Readers has value = 1. This is data inconsistency.

To avoid this, the mutex is used.

---
Tags: concurrency, synchronization, mutual-exclusion
---


title: Comparing DFA's produced languages

text:
# Question
Title: Comparing DFA's produced languages
I'm working on some questions to bone up on my knowledge of DFA's for a computing class and I've run across the following problem that is giving me some issues. If we have some DFA M = (Q, Σ, δ, q0, F) and some other DFA M' = (Q, Σ, δ, q0, F') where F is a proper subset of F', are the following relations possible or not between the two produced languages?

1) L(M) ⊂ L(M')

2) L(M) ⊃ L(M')

My current theory is that the first one is not possible, due to the fact that the first machine has fewer finish states than the other, thus the language must be larger and cannot be subset to M'. This would of course mean that the second relationship is possible, since M must contain M'. Am I on the right track here and if so, how could I prove this?

# Answer
L(M) ⊂ L(M') can be proved as below:

Suppose a string 'w' ∈ L(M') .
Since it is given that F is a proper subset of F' , there exists a state q1 such that
q1 ∈ F' but not to F.
Since the transition function is same for both the DFAs, hence there is a transition possible as below:
δ(q0, w) = q1
which means the state change takes place from the initial state to the state q1 on reading the input symbols from the string 'w'.

Since q1 ∈ F' but not to F, we can say that 'w' does not belong to L(M).
On the same lines it can also be proved that any string in L(M) is also present in L(M'), thereby proving the relation.
> 4 votes

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


title: Quantifiers in lambda calculus

text:
# Question
Title: Quantifiers in lambda calculus
I'm learning lambda calculus, however I'm quite confused about the quantifiers in lambda calculus. As far as I know, quantifiers such as "∃" are concepts of first order logic (FOL), which are not needed by lambda calculus. Moreover, I didn't find anything about quantifiers in any tutorials I have read.

However, I find this paper (Lambda Dependency-Based Compositional Semantics), in the first page of which the author used quantifier in lambda calculus.

So, are quantifiers used in lambda calculus? If so, what do they mean? Is it the same as in FOL?

Precisely, what does "∃" mean in the following lambda calculus?

```
λx.∃e.PlacesLived(x, e) ∧ Location(e, Seattle)

```

# Answer
> 4 votes
It appears that the author is using lambda notation for sets and relations. That is, sets are represented as boolean-valued unary functions, and relations are represented as boolean-valued binary (or k-ary) functions. In other words, we work with the sets/relations' characteristic functions instead, with no loss of generality.

For instance $\\{n | n\geq 5\\}$ is written as $\lambda n.\ n\geq 5$ where "$n\geq 5$" must be understood as the boolean $\sf true$ or $\sf false$, depending on the value of $n$.

The existential expression $\exists x.\ p(x)$ must be understood similarly: it "evaluates" to true iff there is some value of $x$ which satisfies $p$.

Also, note that, in the theory of typed lambda calculi, we do have some powerful type systems which allow $\forall/\exists$ to appear. For instance the second-order lambda calculus $\lambda 2$ (AKA System F) allows universals in types. In the very powerful Calculus of Constructions we can indeed write things such as $\lambda x:\tau.\ \exists y:\sigma.\ p x y$ which is a function of type $\tau \rightarrow \*$. It takes a value of type $\tau$, and returns an existential type.

You do not need this theory for the paper you mention, though.

# Answer
> 5 votes
There is no notion of quantification in the standard $\lambda$-calculus as introduced by Church. As far as I can tell from Liang's paper, it deals with a specialized version of $\lambda$-calculus in which $\lambda$-expressions can be logical expressions containing quantifiers and logical connectives. This approach is meant as a way of formally representing natural language statements. Thus, we are really dealing with an applied $\lambda$-calculus with function symbols that correspond to logical connectives and function symbols and are to be interpreted in this way.

---
Tags: lambda-calculus, semantics
---


title: Maximal Elements in a Lower Set

text:
# Question
Title: Maximal Elements in a Lower Set
I have a collection of objects, and a feasibility property for sets of objects which is slow to compute. If a set is feasible then so is any subset. For example, it could be whether the set of things will fit into a certain-sized packing crate.

I want to compute all feasible sets (equivalently - all maximal feasible sets), minimizing the number of evaluations of the feasibility property (worst-case or average). Does anyone know of any theoretical work on this?

Bonus question - what if the cost to compute the property is linear (or superlinear) in the size of the set being evaluated?

# Answer
> 2 votes
Your problem is equivalent to exact learning of monotone DNFs. This task is equivalent to learning all *minterms* of a monotone function, whereas you are interested in learning all *maxterms* of a monotone function, but the two problems are equivalent. (Look these terms up if you are not familiar with them.)

If the only queries you allow are *membership queries* (test whether a given set is feasible or not) then your problem is rather difficult. Theorem 2 in Angluin's Queries and Concept Learning shows that $2^n-1$ queries are required even if there are only $2n$ objects and $n+1$ minterms. See the paper for other models in which your problem can be solved efficiently.

---
Tags: algorithms, search-algorithms, order-theory
---


# Question
Title: Removing edges from a fully connected weighted graph
Given a fully connected graph $G(V,E)$ with associated edge weights and a set of constraints specifying distance $D(V\_i, V\_j) \< M\_{ij}$, where $\left\\{V\_{i..j}\right\\} ⊂ V$, how can I go about finding the smallest subset graph $G'(V', E')$ such that none of the constraints are violated?

In other words, find the smallest subset of the graph such that the distance between a given set of vertices does not exceed some constant.

# Answer
This is NP-hard by reduction from Set Cover. The problem remains NP-hard even if edge weights are restricted to $\\{1, 3\\}$.

In the Set Cover problem, we are given a ground set $U$ containing $m$ elements $x\_1, \dots, x\_m$, a collection $\mathbf S$ of $n$ subsets $S\_1, \dots, S\_n$ of $U$, and an integer $k$, and our task is to determine whether there exists some set of at most $k$ of the $n$ sets in $\mathbf S$ whose union contains all $m$ elements in $U$.

First let's frame your problem as a decision problem: Given an edge-weighted undirected graph $G = (V, E)$, a set of $r$ constraints $d(v\_{s(i)}, v\_{f(i)}) \le M\_i$ for $1 \le i \le r$ and an integer $q$, does there exist a subgraph $G'$ of $G$ such that each constraint is satisfied by some path in $G'$ and $G'$ contains at most $q$ edges?

To convert a given Set Cover instance into an instance of this problem:

1. Create a vertex $t$.
2. For each element $x\_i$, create a vertex $u\_i$ and the constraint $d(u\_i, t) \le 2$.
3. For each set $S\_j$, create a vertex $v\_j$ and the unit-weight edge $v\_jt$.
4. For each $x\_i$ that belongs to a set $S\_j$, create the unit-weight edge $u\_iv\_j$.
5. Add in all possible remaining edges, giving each weight 3.
6. Set $q$ to $m+k$.

First, suppose the solution to the Set Cover problem is YES. It is easy to construct a solution to the constructed instance of your problem: For each set $S\_j$ not selected by the Set Cover solution, delete the corresponding edge $v\_jt$. For each element $x\_i$, choose some set $S\_j$ such that $x\_i \in S\_j$ and $S\_j$ was selected by the Set Cover solution (since the solution was YES, such an $S\_j$ must exist) and keep the corresponding edge $u\_iv\_j$; delete all other edges incident on $u\_i$. Finally, delete all weight-3 edges. Clearly this leaves exactly $m$ edges incident on $u$-vertices, plus at most $k$ edges connecting $v$-vertices to $t$, for a total of at most $q = m+k$ edges. Each $u\_i$ is connected to $t$ by a length-2 path via the vertex $v\_j$ corresponding to its chosen containing set $v\_j$, so all distance constraints are satisfied. Thus the solution to the constructed instance of your problem is also YES.

Second, suppose that the solution to the constructed instance of your problem is YES. Let $G'$ be any such satisfying subgraph.

Since $G'$ satisfies all distance constraints, and no weight-3 edge can participate in any such path, removing any remaining weight-3 edges in $G'$ must produce another valid solution $G''$.

Every $u$-vertex in $G''$ is adjacent to some $v$-vertex that is adjacent to $t$, since the answer to the problem was YES and there are no other paths from $u$-vertices to $t$ of distance $\le 2$. Suppose some $u\_i$ in $G''$ is incident on 2 or more outgoing edges. All but one of these edges can be removed without violating the $d(u\_i, t) \le 2$ constraint. Let $G'''$ be the graph that results from performing these edge deletions on $G''$: $G'''$ is a valid solution.

Each of the $m$ $u$-vertices in $G'''$ is incident on exactly 1 edge, and since the answer to the problem was YES, the total number of edges in $G'''$ is $\le q = m+k$, so there are at most $k$ other edges in $G'''$. These can only be edges between $v$-vertices and $t$. Construct a solution to the original Set Cover problem by selecting the at most $k$ sets corresponding to the $v$-vertices that are adjacent to $t$ in $G'''$: clearly the union of these sets contains all $m$ vertices, so the answer to the original Set Cover problem is also YES.

We have established that a YES answer to each problem implies a YES answer to the other problem, so a NO answer to either problem implies a NO answer to the other one, so the problems are equivalent. The constructed instance of your problem is easily constructed in polynomial time, so it follows that your problem is NP-hard.
> 4 votes

# Answer
This problem is NP-hard problem, you should go with heuristics or meta-heuristics, to find acceptable solution in acceptable time. try first Genetic algorithms, they are very powerful and they will give you great ideas.
> 0 votes

---
Tags: graphs, network-analysis
---


# Question
Title: Under what conditions is K-means clustering transformation-invariant?
Given a set of data points $X = \\{x\_1, x\_2, \ldots, x\_m\\}$ where $x\_i \in \mathbb{R}^d$ we run K-means on $X$ and obtain the clusters $c\_1, c\_2, \ldots, c\_k$.

Now, if we create a new dataset $Y = \\{y\_1, y\_2, \ldots, y\_m\\}$ where $y\_i = Ax\_i + b$ and $y\_i \in \mathbb{R}^d$ and run K-means on $Y$ to get clusters $g\_1, g\_2, \ldots g\_k$.

Under what conditions of $A$ and $b$ are we guaranteed to get the same clusters?

Let's assume that K-means is using the euclidean distance and has same initial conditions on both algorithms, that is, if the initial centers for X are $c^0\_1, \ldots, c^0\_k$ then the initial centers for Y are $g^0\_1, \ldots, g^0\_k$ where $g^0\_i = Ac^0\_i + b$.

So far I've thought that $A$ has to be full rank and $b$ can be any vector. However, I haven't been able to prove it.

# Answer
The answer depends on your K-means algorithm, but what follows should work for standard algorithms.

You will get the same result if your transformation $T$ satisfies two conditions:

1. It preserves distances: $d(z,w) = d(T(z),T(w))$, where $d$ is your metric, say $d(z,w) = \\|z-w\\|$.
2. It preserves averages: if $\sum\_i p\_i z\_i$ is a convex combination that $T(\sum\_i p\_i z\_i) = \sum\_i p\_i T(z\_i)$.

You can check this by going over the algorithm, showing that it always makes the same choices.
> 6 votes

---
Tags: algorithms, clustering
---


# Question
Title: What is the origin of λ for empty string?
I usually use the symbol $\varepsilon$ for empty string (empty word or null string). But I know some people use $\lambda$ instead of $\varepsilon$.

I think $\varepsilon$ is derived from the word "Empty". However I don't know what's the origin of $\lambda$.

In automata theory, there is the epsilon transition of automata, and it's also said to be the lambda transition. For example, JFLAP software uses $\lambda$ for the label of epsilon transitions by default.

I googled on the origin and searched cs.stackexchange, but I couldn't find. Does anyone know a reference that describes this?

# Answer
> 12 votes
The German Wikipedia claims that $\lambda$ comes from "leer", which means "empty" in German. That seems plausible, as German used to be one of the major languages in mathematics.

Chomsky used $I$ as the empty string (or actually as the identity element for string concatenation) in his early papers. Some people in combinatorics still use $1$ as the empty string, with the same justification.

# Answer
> 9 votes
Probably the notation originates from the "Finnish school".

My copy of 'Formal Languages' by Arto Salomaa (Academic Press, ACM monograph series, 1973) uses $\lambda$ for the empty string. And so does his 1969 book 'Theory of Automata' (Pergamon Press).

We move back. The classic 'Finite Automata and Their Decision Problems' by M.O. Rabin and D.Scott (April 1959) have the notation (capital) $\Lambda$ for "the empty tape with no symbols" (where a tape is a finite sequence of symbols).

One of the early people to write on finite automata was Trakhtenbrot and he used a symbol much like $\Lambda$ but typeset as $\land$ (as in his book with Barzdin, 1970, my russian is lousy but I recognize $\land p= p\land=p$).

---
Tags: formal-languages, automata, reference-request, notation, history
---


# Question
Title: The transition function of the union of regular languages
I follow Michael Sipser's book, "Introduction to the Theory of Computation". To be specific, I am trying to understand the proof about the union of regular languages. However, I have a problem grasping how exactly the transition function is defined. The book says that for each $(r\_1, r\_2) \in Q$ and each $a \in\sum$, let $\delta((r\_1, r\_2),a) = (\delta\_1(r\_1, a), \delta\_2(r\_2,a))$. The problem is that I cannot understand what happens if, for example, $\delta\_2(r\_2,a) = \emptyset$ and $\delta\_1(r\_1, a) = q\_1$ and I get $\delta((r\_1, r\_2),a) = (q\_1, \emptyset)$, which does not belong to the set of all pairs of states.

# Answer
In the definition of a deterministic finite automaton, we require that the transition function $\delta$ is well defined on all of $Q\times\Sigma$, i.e. $\delta: Q\times \Sigma\rightarrow Q$. Sometimes we allow omitting transitions, and say that the automaton is "stuck" if it stumbles upon this transition, however in Sipser's book he defines the transition function as above (defined on all of $Q\times\Sigma$).

If you insist on allowing the the automaton to get stuck, then this results in a slight modification of the proof. Instead of looking at $Q\_1\times Q\_2$ (where $Q\_i$ is the state set of the $i'th$ automaton), consider the state space $\left(Q\_1\cup\left\\{\widehat{q\_1}\right\\}\right)\times\left(Q\_1\cup\left\\{\widehat{q\_2}\right\\}\right)$, where $\widehat{q\_1},\widehat{q\_2}$ are special states designed to deal with lack of transition. You can now complete the details yourself.
> 4 votes

# Answer
The transition function of a DFA gets a state and a symbol and outputs a state. It cannot output the empty set. That would be a type mismatch. In other words, in a DFA, every state has an outgoing transition for every symbol – exactly one, in fact.

You can define an "extended" DFA in which some transitions are allowed to be missing, but you would then need to modify the definition of the product DFA. It is a good exercise to see what the appropriate modification would be.
> 3 votes

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


# Question
Title: Runtime of algorithm to transpose a graph
I am working with an algorithm to compute the transpose of a directed graph. Here is a rough overview of the algorithm: For each vertex in the graph, traverse each edge and add an edge from the neighbor to the parent node. The adding of an edge takes constant time, $O(1)$. And I figured, if I am traversing each edge, then the asymptotic run time should be $O(|E|)$. However, the run time of this algorithm is $O(|V| + |E|)$. The only way I can make sense of this is: once it reaches the final level of the tree (the roots), even though the nodes don't have any edges, the for loop will still iterate through those nodes. However, if I am taking this into account, then shouldn't it be $O(|V|)$. Why are we taking both $|V|$ and $|E|$ into account? Can someone can offer some insight to this?

# Answer
It all depends on how exactly you store the graph. For example:

* If you store the graph as an adjacency matrix, the complexity is $\Theta(|V|^2)$.
* If you store the graph as a linked list of edges *per vertex* (i.e., adjacency lists), then the complexity is $\Theta(|V|+|E|)$.
* If you store the graph as a linked list of *all* edges (and don't store the vertices explicitly), then the complexity is $\Theta(|E|)$.

The representations usually used are the first two. I have never heard of the third being used. In most cases, the number of edges exceeds the number of vertices, and so there would be the third method would have no advantage over the second one, but it would have many disadvantages.
> 7 votes

---
Tags: asymptotics, runtime-analysis
---


# Question
Title: How can you determine what set of boxes will maximize nesting?
I'm trying to find a dynamic solution to the nesting boxes problem.

You're basically given a set of "boxes" which all have different dimensions. The goal is to find the maximum set of boxes that can be nested inside of each other.

So more formally,

Given set B = {b\_1, b\_2, . . . b\_n} where each b\_i contains a box with a width, height and depth.

Find the set of boxes that will allow you to nest as many as possible together.

# Answer
Let $\le\_B$ denote the inclusion relation between boxes, i.e. $b\_i\le\_B b\_j$ if we can put the box $b\_i$ inside $b\_j$. Obviously $\le\_B$ is a partial ordering of $B=\left\\{b\_1,...,b\_n\right\\}$.

Your question translates to finding the maximal linearly ordered subset of $B$ relative to $\le\_B$. A linearly ordered subset is a path in the acyclic directed graph $G$ representing $\le\_B$, i.e. $V\_G=B$ and $(b\_i,b\_j)\in E\_G\iff b\_i\le\_B b\_j$. We can now reduce your problem into finding the longest path in the DAG $G$. This can be done in linear time with topological sorting. Overall, the time consuming part is constructing $G$, which requires $O(n^2)$ time.
> 3 votes

---
Tags: algorithms, algorithm-analysis, dynamic-programming, sets
---


# Question
Title: Is Semantic Preservation Soundness (or Correctness) or Completeness
When transforming terms from one language to another, the intuitively desired property is the preservation of semantics (as used e.g. here for a CPS transformatation):

$$ s \Downarrow v \implies c(s) \Downarrow c(v) $$

I am a little troubled, however, by reconciling this with the classical terms *correctness* (or soundness) and *completeness* of logic systems. Usually, I would consider the above statement the completeness property of $c$ (and the converse the definition of correctness).

Intuitively, however, a compiler should be correct rather than complete (as e.g. type-checking often rules out correct programs). The converse of the statement above is only true if $c$ is injective: If the source language contains for instance booleans and operations on them and the compilation replaces them via Church-encoding, the target language can evaluate boolean operations on terms compiled from boolean literals and lambda-abstractions, which the source language cannot evaluate.

1. Am I right to assume, that the above statement is the completeness property of $c$ (so the intuitive requirement actually has a counter-intuitive name)?
2. Am I also right in my conclusion that a non-injective compiler then is usually not correct?

# Answer
This is really a question about the notion of *operational correspondence*.

The paper *Towards a Unified Approach to Encodability and Separation Results for Process Calculi* by Daniele Gorla (http://wwwusers.di.uniroma1.it/~gorla/papers/G-CONCUR08.pdf) is concerned with correctness criteria for translations between process calculi.

In his work, Gorla introduces a notion of behavioural equivalence; I will leave it out here in order not to complicate the explanation overly.

Let $\[ \\! \[ \\; \] \\! \]$ be an encoding, let $\rightarrow\_1$ be the transition relation defined for the source language and let $\rightarrow\_2$ be the transition relation defined for the target language. If we have that

* If $S \rightarrow\_1 S'$ then $\[ \\! \[ S \] \\! \] \rightarrow^\*\_2 \[ \\! \[ S' \] \\! \]$, we say that the encoding is *complete*
* If $\[ \\! \[ S \] \\! \] \rightarrow^\*\_2 T$, then there exists a $S'$ such that $S \rightarrow^\*\_1 S'$ and $T \rightarrow^\*\_2 \[ \\! \[ S' \] \\! \]$, we say that the encoding is *sound*.

So yes, the notion mentioned in the questions is indeed that of completeness. The notion of soundness is shaped by the fact that the target language will often be richer than the target language or contain syntactic constructs whose behaviour does not correspond to anything in the source language. This explains why we speak of the intermediate configuration $T$ in the definition instead of requiring injectivity.
> 3 votes

# Answer
Intuitively speaking, the correctness property for a transformation over a language on which a notion of evaluation is defined states that if a term has a certain semantics then the image of the term by that transformation evaluates to the image of said semantics. In other words, a correct compiler is one that transforms a program into another program with the same behavior (expressed in the target language).

Here, I infer from your notations that the source language is a language of terms $s$ with a notion of evaluation $\Downarrow$: $s \Downarrow v$ means that $s$ reduces (in any number of steps) to the value $v$. A correct compiler $c$ is one that transforms any program $s$ into a compiled program $c(s)$ which evaluates to the corresponding compiler value $c(v)$.

This corresponds to the definition on Wikipedia if values compile to themselves: if $s$ has the property $\Downarrow v$ then so does $c(s)$.

A sound compiler does not need to be injective: it's possible, and extremely common, for different source programs with the same semantics to be compiled to the same compiled program.

Compilers are generally not complete: as you note, it is common to have terms in the compiled language that cannot be the output of the compiler, i.e. the compiler isn't surjective.
> 2 votes

---
Tags: terminology, logic, compilers, semantics
---


# Question
Title: Is structural induction on terms applicable when a function is involved?
Assume an evaluation-relation on terms $t \Downarrow v$. If I want to prove correctness of a function $\phi$ w.r.t. evaluation, I have to show that the following implication always holds:

$$\frac{\phi(t) \Downarrow \phi(v)}{t \Downarrow v}$$

Naturally, this is a candidate for structural induction. But on what structure? Is it sufficient to run the induction over terms, or do I have to run it over the derivation tree? Structural induction is usually only allowed for direct sub-terms, but the function could, in principle, yield completely different results.

Is it sensible to consider $\phi$ part of the promise or do I have to consider it a part of the recursive structure?

# Answer
You probably shouldn't write $\cfrac{\phi(t)\Downarrow \phi(u)}{t\Downarrow u}$ for "For any terms $t,u$, $\phi(t)\Downarrow \phi(u)$ implies $t\Downarrow u$".

---

I'll take a concrete example: Terms are made using $0,S,+$. And there are six rules:

$$\cfrac{}{0 \Downarrow 0}(0)\hspace{2em}\cfrac{x\Downarrow y}{Sx \Downarrow Sy}(S)\hspace{2em}\cfrac{x\Downarrow y}{x+0 \Downarrow y}(+0)\hspace{2em}\cfrac{x\Downarrow y}{0+x \Downarrow y}(0+)\hspace{2em}\cfrac{x+y\Downarrow z}{x+Sy \Downarrow Sz}(+S)\hspace{2em}\cfrac{x+y\Downarrow z}{Sx+y \Downarrow Sz}(S+)$$

Note that $(0+)$ and $(S+)$ are superfluous (but do not break the uniqueness of the normal form).

I'll provide three examples where different proof techniques apply.

---

Let's take $\phi(x)=Sx$.

Suppose that for some $a$, $Sa=\phi(a)\Downarrow \phi(b)=Sb$. The only rule that allows you to prove this is the rule $(S)$ with $x=a$ and $y=b$ (because it's the only rule that can have successor on both sides of $\Downarrow$ in the conclusion), so you must have $a\Downarrow b$, which is what you want. So you can prove that "For any terms $t,u$, $\phi(t)\Downarrow \phi(u)$ implies $t\Downarrow u$".

You were able to prove it without even using induction because the definition of $\phi$ wasn't inductive.

**Remark**

But you can not compose rules to get $\cfrac{St\Downarrow Su}{t\Downarrow u}$ (because there are more $S$ in the conclusion than in the premise and all rules have at most as many $S$ in the conclusion as in the premise).

Your result is a meta-theorem but not a theorem (because it's not just a combination of the rules).

A theorem would, for example, be $\cfrac{}{S0\Downarrow S0}$ (that you get by composing $(0)$ and $(S)$ or $\cfrac{x\Downarrow y}{x+S0\Downarrow Sy}$ (that you get by composing $(+0)$ and $(+S)$).

---

Let's take another example: $\varphi(0)=0$, $\varphi(Sx)=SSx$ and $\varphi(x+y)=\varphi(x)+\varphi(y)$.

Now suppose that $\varphi(a)\Downarrow \varphi(b)$.

We'll prove $a\Downarrow b$ by induction on the size of the proof of $\varphi(a)\Downarrow \varphi(b)$.

If it's of size $1$, then it has to be just an application of $(0)$ so $\varphi(a)=0=\varphi(b)$ and so $a=0=b$ and $(0)$ gives us the proof we want.

If it's of size $\>1$, the last rule is not $(0)$ so you do case analysis and apply the induction hypothesis on the premise of the rule. You'll have to do case analysis, but you should be able to prove that it works.

---

There should be some case where you can do induction on terms to prove the thing but I couldn't find one. It feels more natural when you have a small step transition system $\to$ and define a big step one $x\Downarrow y$ by $x\to^\* y$ and for any $z$, $y\not\to z$. Then, it you manage to prove that $\phi(x)\to \phi(y)$ implies $x\to^+ y$ and that $x\to y$ implies $\phi(x)\to^+\phi(y)$, you will get that $\phi(x)\Downarrow \phi(y)$ implies $x\Downarrow y$.

The main thing you should remember is that "case analysis" \< "induction on terms" \< "induction on proofs" in terms of what you can proove but often, the number of cases you have to handle often grows. So you should try the proofs techniques in that order until you get one that works.
> 3 votes

# Answer
If your logic has a rule like $\dfrac{\phi(t) \Downarrow \phi(v)}{t \Downarrow v}$ then you can't use induction over terms to prove something. A rule like this is not *syntax-directed*: you can't choose which rule to apply to deduce a conclusion based on the syntax of that conclusion.

To perform induction over proofs, you need to do induction over the syntax of the proof. This is equivalent to induction over terms only when the deduction rules are syntax-directed. Syntax-directed rules are nice, but they aren't always possible.

To give a concrete example, a logic that has a transitivity rule like $\dfrac{A \preceq B \quad A \preceq C}{A \preceq C}$ isn't syntax-directed and it's often impossible to prove properties of such relations with the syntax of terms alone, because you never know when an inequality might have been obtained via transitivity rather than for structural reasons. Sometimes transitivity is a derived rule (i.e. you can prove that for any $A$, $B$ and $C$ such that $A \preceq B$ and $B \preceq C$ are derivable then there exists a derivation of $A \preceq C$. That makes the system easier to work with because (barring other, similar rules) you no longer have to consider arbitrary intermediate $B$'s when you induct over the structure of derivations.

If $\phi$ is a meta function rather than part of the syntax of the language, then it's even more obvious that you can't do induction on the structure. Consider the case when $\phi$ is the identity function...
> 2 votes

---
Tags: proof-techniques, correctness-proof, semantics, induction
---


# Question
Title: Algorithm: Finding median in a sorted array with duplicates
If array is sorted we can generally find median in O(1) by returning the element at the middle. But what if there are duplicates?

E.g \[2, 2, 3, 3, 3, 3\]

# Answer
Yes. Even with duplicates, the process of finding median is same. See this link - https://math.stackexchange.com/questions/1191119/how-to-find-the-median-of-three-numbers-if-one-of-them-appears-twice
> 2 votes

---
Tags: algorithms, arrays, searching
---


# Question
Title: Does the running-time of this push-relabel algorithm become zero if there are many edges?
According to the Wikipedia page on the Push-relabel maximum flow algorithm:

> Subcubic $O(|V||E| \log\frac{|V|^2}{|E|})$ time complexity can be achieved using dynamic trees, although in practice it is less efficient.

What if $|E| = |V|^2$? Don't we then have this?

$$O(|V||E| \log\frac{|V|^2}{|V|^2})$$ $$O(|V||E| \log 1)$$ $$O(|V||E| 0)$$ $$O(0)$$

There's no way this can be right, so what am I misunderstanding?

# Answer
First of all, we usually assume that there are no self-loops. As a consequence, $|E| \leq |V|(|V| - 1) \< |V|^2$.

---

That aside, there is (probably) a misuse of Landau notation here.

The given bound is (probably) not correct for all (families of) graphs. For instance, if $|E| = 0$ the same arithmetic issue occurs but the algorithm will certainly have non-zero running time.

The authors probably simplified away terms of the order of, say, $\Theta(|V|)$ or $\Theta(|E|)$. They do this because they are asymptotically *dominated* by the given term -- if all quantities are non-zero. This is a fundamental problem with using Landau notation with more than one variable without being rigorous about it.

So, even if the leading term would become zero (which can certainly happen and be correct!) lower-order terms would be non-zero and lead to useful bounds.

### Example

Consider this very simple algorithm:

```
1 def algo(n, m)
2   x = 0
3   for i = 1 .. n
4     for j = 1 .. m
5       x += 1
6   return x

```

A standard analysis tells you immediately that the running-time is in $\Theta(nm)$ as that is how often the line `x += 1` will be executed. Now, if `n` or `m` is zero, does the algorithm have zero running time? No!

A more precise analysis leads to the running-time being

$\qquad c\_1 + c\_2 n + c\_3 m + c\_4 nm$

with suitable constants $c\_1$ (cost of lines 2 and 6, setup of line 3), $c\_2$ (management of line 3, setup of line 4), $c\_3$ (management of line 4) and $c\_4$ (line 5).

### Background

Landau notation only makes sense if the parameters go to infinity in suitable ways. We can not just insert finite values for some parameters and expect it to behave well.

Refer to A general definition of the O-notation for algorithm analysis by Kalle Rutanen et al. for details.
> 2 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, landau-notation
---


title: Must a complete subgraph be induced?

text:
# Question
Title: Must a complete subgraph be induced?
If we had some $K\_n$ subgraph where $K\_n \subseteq G$, must the complete subgraph $K\_n$ be an induced subgraph from $G$? In other words, can we create a situation where we remove vertices from a simple graph $G$ to obtain some complete subgraph where the subgraph was not complete when it was a part of $G$?

# Answer
Every complete subgraph $K\_n$ contained in a graph $G$ can be considered as an induced subgraph of $G$. Note that, by definition, an induced subgraph is formed from a subset of the vertices of the original graph along with *all* of the edges connecting pairs of vertices in that subset.
> 2 votes

# Answer
The subgraph $G(V')$ induced by $V' \subseteq V$ consists of $V'$ and all edges incident to nodes of $V'$.

If a subgraph $G' = (V', E')$ is complete, then $G(V')$ can not possibly contain any edges $G'$ does not; we have $G' = G(V')$.
> 2 votes

---
Tags: graphs, terminology
---


# Question
Title: How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3?
How many comparisons in the worst case, does it take to merge 3 sorted lists of size n/3? (where n is a power of 3)

I was told it takes:

$$2(n-2) + 1 = 2n-3$$

However, I can't seem to figure out why.

The way to merge them I was thinking just to merge two of the lists, and then merge that big 2/3 list with the remaining list. How come the worst case of that 2n-3?

The complete explanation I was given was:

> The worst case occurs if the first list empties when there is exactly 1 item in each of the other two. Prior to this, each of the other n−2 numbers requires 2 comparisons before going into the big list. After this, we only need 1 more comparison between the 2 leftover items.

Which doesn't make complete sense to me. Not sure if its just the grammar of the sentences, but not sure where the $2(n-2)$ came from... What does:

> The worst case occurs if the first list empties when there is exactly 1 item in each of the other two.

even mean?

When it says "prior to this", its not clear to me what exactly happened before hand...

What does the "big list" referring to? How did we even get a "big list"?

Btw, I am **not** looking for an asymptotic answer.

---

I was also interested in the generalization of my question though:

Extending my question, if we extend merge sort algorithm but instead of 2, to divide by some constant c, why would the recurrence be of the form:

$$T(n) = cT \left( \frac{n}{c} \right) + \left\[ (c-1)(n-(c-1)) + \sum^{c-2}\_{i=1} i\right\]$$

The extra term for merging is not entirely clear to me.

# Answer
First of all, we have to distinguish between two different questions. The first is about analyzing the specific (generalized) merging algorithm used in merge sort. The second is about analyzing the problem.

**Merge sort merging**

The paragraph you quote attempts to analyze the merge sort merging algorithm. It only gives a lower bound on the number of comparisons, though presumably it is easy to show that it is also an upper bound. In order to give a lower bound of $C$ on the number of comparisons, it is enough to describe a situation in which the algorithm uses $C$ comparisons. Such a situation is the "worst case \[instance\]" that the paragraph is talking about.

The merging algorithm starts with three lists of length $n/3$, and constructs a "big list" of length $3$. The algorithm works by comparing the smallest elements in all remaining lists, and moving the smallest one to the top of the big list. As the algorithm progresses, eventually lists will empty — all their elements have been moved to the big list.

The paragraph suggests to consider the situation in which the first list empties when the other two have exactly one element remaining, which it claims is a "bad case", indeed the "worst case"; for the sake of the lower bound, we don't care whether this is actually true. You have to argue that the situation can actually happen, and carefully count all comparisons done by the merging algorithm. The merging algorithm the paragraph considers always compares the bottom elements of all remaining lists, requiring $\ell-1$ comparisons if $\ell$ non-empty lists remain. In this case, as long as all lists are non-empty, we need two comparisons per element.

At the situation considered there are only two elements left, so $n-2$ elements have been processed with two comparisons per element, leading to $2(n-2)$ comparisons. The final two elements require one more comparison. It is not too hard to check that this is indeed the worst case: this situation maximized the number of times that an element requires two comparisons to process.

The more general case with $c$ lists is very similar. Again the worst case is when the first list empties when all other lists have exactly one element. Up to now there have been $(c-1)(n-c+1)$ comparisons. The next element will require $c-2$ comparisons only (since there are only $c-1$ non-empty lists), the element after that $c-3$, and so on. This gives the formula you state.

**General question**

A different question one can ask is: given $c$ sorted lists of length $n/c$, how many comparisons are needed to determine the sorted order of all of them merged. There are two variants of this question:

1. What is the minimal $C$ such that there is an algorithm which outputs the correct order and never uses more than $C$ comparisons; the algorithm is only allowed to access the lists by comparing two elements. This is the so-called decision-tree model.
2. What is the minimal running time of an algorithm merging the lists.

These questions are rather different. The first question is much easier to answer, and I will only comment on it. However, the minimal $C$ doesn't necessarily correspond to an efficient algorithm, since determining which comparison to do next could be difficult.

The classical lower bound on sorting extends to this situation. Given $c$ sorted lists of length $n/c$, the number of possible ways they fit together to one big list is $\frac{n!}{(n/c)!^c} = \Theta\big(\frac{c^n}{n^{(c-1)/2}}\big)$, and we obtain a lower bound of $(\log\_2 c)n - O\_c(\log n)$. Fredman's classical result shows that there is a corresponding algorithm in the decision-tree model using at most $(2+\log\_2 c)n$ comparisons (for large enough $n$, depending on $c$), which is better than the merge sort merging procedure for $c \geq 5$. The correct answer is probably $(\log\_2 c)n \pm o\_c(n)$. Indeed, using heaps you can merge $c$ lists with $O((\log c)n)$ comparisons efficiently, as described for example in answers to the following question.
> 5 votes

# Answer
I think the worst case is actually better; about (5/3)n instead of 2n.

We start with three lists of length n/3, a total of n elements. We repeatedly determine the smallest element, and move it from its list to the output list.

As long as we have three non-empty lists, this is done easily with two comparisons: We compare the smallest elements of list 1 and list 2, then compare the smaller one with the smallest element of list 3. At some point we are down to two lists, so we need one comparison for the next element (save one comparison) until we are down to one list, where we need no comparisons (save two comparisons per element). Worst case we go from three lists with one element each to two lists then to one list, and save 3 comparisons, which gives us 2n-3 comparisons.

However, there are two situations now: If the element of list 3 is the smallest, then we still know whether the element of list 1 or list 2 was smaller after the move, so we save a comparison. If the element of list 3 is not the smallest the list 3 doesn't empty, so there will be elements left in list 3 when one of the other lists empties.

Assume the element of list 3 was the smallest (k) times until one list was empty. We saved k comparisons. If k \< n/3 then there are n/3 - k items left in list 3, and at least one more element in another list. Worst case we save one comparison (n/3 - k) times, then we have one item left and save another two comparisons. So n/3 + 2 comparisons are saved in total, which means we need 5/3 n - 2 comparisons.

PS. Yuval Filmus states a lower bound of about $n log\_2(3)$ which is about 1.585n, so 5/3 n - 2 ≈ 1.667 n isn't bad.
> 2 votes

---
Tags: algorithms, time-complexity, runtime-analysis, sorting
---


# Question
Title: How to prove an identity of regular expressions
I am in trouble how to prove that these two regular expressions are equivalent. I know what are closures and all the basics of automata. But the problem is I don't know the method or way of solving this kind of problem.

Question:

> Prove that R.H.S regular expression is same as L.H.S
>
> $$ (a+b)^\* a (a+b)^\* b (a+b)^\* = (a+b)^\* ab (a+b)^\* $$

# Answer
> 2 votes
Regular expressions stand for languages. To show that two languages are equal, we show that every string in the first also belongs to the second, and vice versa.

As an example, let us prove the identity $$ a(ba)^\*b = ab(ab)^\*. $$ Denote the language of a regular expression $r$ by $L\[r\]$. A word $w$ belongs to $L\[a(ba)^\*b\]$ if there exists $n \geq 0$ such that $w = a(ba)^nb$. Now $w = a(ba)^nb = (ab)^{n+1} = ab(ab)^n \in L\[ab(ab)^\*\]$. Similarly, a word $w$ belongs to $L\[ab(ab)^\*\]$ if there exists $n \geq 0$ such that $w = ab(ab)^n$. Now $w = ab(ab)^n = (ab)^{n+1} = a(ba)^nb \in L\[a(ba)^\*b\]$.

(You can prove the various identities I used, such as $(ab)^{n+1} = a(ba)^nb$, by induction on $n$.)

Your particular identity states that if a word over $\\{a,b\\}$ contains an $a$ followed by $b$ (with possibly letters separating them) then it contains the substring $ab$, and vice versa. You should start by understanding why this holds.

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


# Question
Title: Somewhat-hardware-conscious algorithm for top k-of-n with $k=\Omega(\sqrt{n})$
The "top k of n" problem: You have n (not necessarily distinct) elements in an array, and you need to return another array containing the k elements with the highest value.

So, I'm going to need a top-k-of-n implementation for something I'm working on. Never mind exactly which programming language and hardware I'm going to use - but do mind that it's going to actually run on actual hardware. Thus there is multi-level caching so dereferencing pointers to arbitrary places should be minimized; there's the balance between computation and memory bandwidth to consider; there's multithreads/SIMDizing/whatever so I would like something parallelizable without too much communication... that's what I meant by somewhat-hardware-conscious.

Anyway, for a really small k I would probably just use a priority queue which fits in cache (or even linear search through several registers). But - what if your k is large? Large that the top k elements won't just be hiding at the top end of an estimated distribution? In this case I was thinking of estimating k using sampling, then (sort of) partitioning on that guess k; seeing how badly I missed; and iterating that, either partitioning my more-than-k or my more-than-n-minus-k. On one hand the length decreases quickly, and on the other hand I get closer to the really-small-k case, until I can settle for a priority queue (say for each core even) for the last bit.

So, my questions are:

* Can someone describe known algorithms for this variant of the problem, meeting my "vague hardware consciousness" constraint?
* Does the algorithm sketch I described sound like something you know?
* If not, does it sound like a good idea or can you describe shortcomings of this kind of an approach?

**Notes:**

* You may assume the data are non-negative integers if it helps in any way (I don't think it should), or make any any other reasonable assumptions.
* This problem is different that the partial sorting problem in that the output does not need to be sorted. Of course, for small k = $o(\sqrt{n})$ there isn't that much of a difference.
* The data is in memory, i.e. this is not a streaming algorithm and you can read data multiple times. You can't alter the input; you can make a full copy but hopefully that should be overkill.

# Answer
> 1 votes
If you're allowed to make multiple passes through the data, one efficient approach is to use QuickSelect to find the value of the $k$-th largest element, then follow with a linear scan that outputs all elements that are larger than it.

This is more or less a more carefully-worked out version of the kind of approach you seemed to be considering.

See also https://en.wikipedia.org/wiki/Selection\_algorithm.

---

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another possible approach would be to take a sorting network, which is a hardware circuit that sorts all of the values. Then, throw away all but the last $k$ outputs, and keep only the gates they depend on. You might be able to throw away a non-trivial fraction of the sorting network -- I haven't tried to work out how much. This would solve the partial sorting network, and could potentially be hardware-friendly.

---

The following approach was written for an earlier version of the question, which specified $k = O(\sqrt{n})$, but might not be useful for large $k$:

Another approach is to do something like merge sort, but where you only keep the top $k$ elements in each list at each stage. In other words, split your data so that each processor receives an equal number of items. Have each processor find the top $k$ of its elements (say, using a priority queue or any other method). Then merge lists recursively, where each merge operation merges two or more lists of size $k$ and outputs only the first (largest) $k$ elements of the result. This might work very well for out-of-cache (too-large-to-fit-in-main-memory) situations, or for parallel computing. If you can fit $B$ items in cache/memory, then each merge step merges $B/k$ lists, so the number of rounds is $\lg\_{B/k} (n/B)$.

---
Tags: algorithms, searching, filtering-problem
---


title: pattern search with k-mismatch

text:
# Question
Title: pattern search with k-mismatch
I have used Rabin Karp Rolling Hash for searching a pattern $P$ in a text $T$. Now I am allowing $k$-mismatches, but not able to do a faster implementation.

I tried modifying RK algorithm by splitting the pattern into few blocks, but that does not improve the speed.

I'm trying to use locality sensitive hashing, but not sure how could I calculate hash with sliding window manner. Any help would be appreciated. For my case, the length of $P$ is 50~75 and $T$ is 100~150.

# Answer
> 4 votes
## Split into segments

One simple approach is to split $P$ into $k+1$ pieces, say $P = P\_0 P\_1 \cdots P\_k$, as @j\_random\_hacker suggests. You can make each of the $P\_i$ be of approximately equal length, though this is not required. Then, for each $i$, search for all instances of $P\_i$ in $T$ (with no mismatches), and see if it can extend to an instance of $P$ with at most $k$ mismatches. If there is a solution for your original problem, then this procedure will find it.

For non-degenerate cases, if every $|P\_i|$ is large compared to $\log\_{|\Sigma|} |T|$ and $P,T$ are more or less random, we can expect that there will be few "false matches" of a piece, and consequently we can expect that the running time will be approximately $O(k \cdot |T|)$. Thus this should be pretty fast in your specific situation.

This approach allows you to use any fast string-matching algorithm to search for instances of $P\_i$ in $T$; e.g., you can use Rabin-Karp or any other existing algorithm -- this is nice because you can re-use existing well-tuned string matching libraries. This approach might be not-too-difficult to implement and fairly efficient in practice.

## Levenshtein automaton

You can build a NFA (nondeterministic finite-state automaton) to recognize instances of $P$ with at most $k$ mismatches. In particular, the NFA recognizes all strings $S$ that end with something that matches $P$ with at most $k$ mismatches. The NFA has $(k+1) \times |P|$ states: each state is of the form $(m,i)$, where $m$ counts the number of mismatches so far and $i$ counts the length of the prefix of $P$ that has been matched so far.

You can convert this NFA to a DFA. Heuristically, I expect the size of the DFA to be pretty small, say $O(k \cdot |P|)$, though I don't know of any proof of this. Next, you can run the DFA along the text $T$, to find the first place where there is a match, which takes $O(|T|)$ time.

This might be fast if $k$ is not too large. If $k$ gets too large, it's possible the DFA will be enormous and the approach might fail. This is probably most useful if you plan to re-use the same pattern $P$ with many different texts $T$, or if $T$ is far longer than $P$. I wouldn't recommend it for your specific situation.

I have no proof that the resulting DFA will be small. See also Levenshtein automata, which consider the far harder problem of building a DFA to recognize all strings $S$ that end with something that has edit distance $\le k$ to $P$ (i.e., they allow for at most $k$ mismatches, insertions, and/or deletions, in total). The resulting DFA is much more complex, yet there are amazing algorithms to build the edit-distance DFA in running time that is linear in $|P|$ (but possibly exponential in $k$). Your problem is considerably easier and will probably lead to DFA that are significantly smaller.

---
Tags: algorithms, strings, searching, rolling-hash
---


# Question
Title: Making mathematical expressions as balanced trees as possible
I am having some trouble with turning the following mathematical expressions into as balanced binary trees as possible.

This is what I have done so far, but is there a way to make them even more balanced?

$( − 3)(^2 + − 1)$

$4( − 1)( − 2)( − 3)$

# Answer
> 0 votes
Since these are *mathematical* expressions, you can bracket the second one as (4 (x-1)) ((y-2) (z-3)) to make it more balanced. In many programming languages this wouldn't be allowed, because with floating point arithmetic, the order of operations will often change the result.

Can't see any way to improve the first one.

---
Tags: optimization, trees, arithmetic
---


# Question
Title: Set of vertex-disjoint cycles maximizing different colored vertices
Let $G=(V,E)$ be a directed graph whose vertices $v \in V$ have colors and its edges $e\in E$ have costs $cost(e)$.

I am looking to find a set of vertex-disjoint cycles that:

1. First maximizes the number of differently colored covered vertices.
2. In case of ties, break ties by secondly maximizing the number of chosen edges.
3. In case of any further ties, third minimizes the total cost of the chosen edges.

This is very similar to this problem, with additional constraint (#1). Without the first constraint (maximize the colors) this problem is easily solved by:

* Splitting each vertex $v$ to $v^+$ and $v^-$.
* Each vertex $v^+$ and $v^-$ provides a supply of $+1$ and $-1$, respectively.
* Replacing an original edge $e': v \to w$ with $e: v^+ \to w^-$. Such each edge has cost $cost(e') = cost(e)$ and unit capacity.
* Adding a "bind" edge $e'' : v^+ \to v^-$. Its cost is $c(e'') \gg 1$

Here is a representation:

And the problem has been reduced to a minimum-flow problem (MCF). A MCF algorithm will choose $A\_1 \to B\_1 \to A\_2 \to B2 \to A\_3 \to B\_3 \to A\_1$.

My question: is it possible to apply a similar modeling to satisfy the color constraint in polynomial time? If so, is it possible to reduce the problem to a MCF problem?

Here is how far I have managed to take it:

Here, bind-edges $e''$ go through a collective set of nodes, one per color, e.g., "A no+" and "A no-". These represent the corresponding vertices not chosen. Between "A no+" and "A no-" three edges are added with unit capacities and costs $ c(e\_{red}) \>\> c(e\_{orange}) \>\> 1$

I basically model that the cost of not choosing one or even two yellow items is insignificant to the cost of not choosing all three yellow items. Therefore, the goal is to choose $A\_1 \to C \to B\_3 \to A\_1$.

Nevertheless, this did not quite work. Basically, if a flow goes through $A\_1^+ \to A\_{no}^+ \to A\_{no}^-$, it's not guaranteed that it will return to $A\_1^-$.

I have tried other approaches, including toying around with non-unit capacities, but I didn't find a solution. Can it be solved in polynomial time?

# Answer
> 6 votes
It cannot be solved in polynomial time, assuming P$\\,\neq\\,$NP.

Without worrying about colors (i.e. if every vertex had the same color), it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature and can be solved in polynomial time with a reduction to the Assignment Problem.

With the introduction of colors to the problem, it is NP-hard (and the corresponding decision problem is NP-complete). The problem that you described can be called TROPICAL MAX SIZE EXCHANGE (TROPMAX EXCHANGE). CNFSAT reduces to TROPMAX EXCHANGE.

Create a graph with one vertex for each variable in the CNFSAT expression, with all of these "variable vertices" colored the same way. Assign each clause in the expression its own color. From each "variable vertex" create two cycles - label one cycle 'true' and one 'false'. For each literal in the expression, create a vertex that is the color of its clause and put it on the appropriate 'true' or 'false' cycle of the corresponding variable vertex. Finally, add additional vertices of some new color so that every 'true' and 'false' cycle has the same number of vertices.

Because we are choosing vertex-disjoint cycles, each 'variable vertex' can only be in its 'true' cycle or 'false' cycle, not both. There are no cycles in the graph other than those true/false cycles. Every cycle has the same number of vertices, so an algorithm that first maximizes the number of vertices in the cycles can choose any combination of cycles: either true or false for each variable vertex. If the secondary criterion is to maximize the number of colors in the cycles, then if all colors can be included the CNFSAT expression can be satisfied.

Highley, Timothy and Le, Hoang. "Tropical Vertex-Disjoint Cycles of a Vertex-Colored Digraph: Barter Exchange with Multiple Items Per Agent" dmtcs:3186 - Discrete Mathematics & Theoretical Computer Science, July 31, 2018, vol. 20 no. 2 https://dmtcs.episciences.org/4690 https://arxiv.org/abs/1610.05115

---
Tags: network-flow, matching
---


# Question
Title: Find number X by asking Hamming distance between X and Y in binary representation
We need to find unknown 16-bit integer X. We can ask "how many '1'-bits in number X xor Y" (Y is 16-bit too). What best strategy to find X? Or what minimum number of questions?

For example, if answer for Y=0 is 1, we can do binarysearch-like strategy restoring X in 4 additional operations.

I have found set of 10 numbers {26330, 15436, 4730, 5006, 10083, 227, 2775, 2367, 17754, 25121} such if we ask about all of these, we can uniquely restore X.

# Answer
> 1 votes
One reasonable heuristic would be to use a greedy algorithm, which at each step picks a query that is likely to reduce the space of possibilities as much as possible.

Suppose you care about the maximum number of questions (worst-case). Then I suggest the following strategy. At any point, you have a set $S$ of possible values of $X$ that remain. For each possible query $Y$ and each possible response $R$ to that query, let $n(Y,R)$ denote how many possibilities of $S$ would remain consistent with the response $R$ to query $Y$. Define $n(Y) = \max\_R n(Y,R)$. Now, choose the query $Y$ that makes $n(Y)$ as small as possible. \[This is basically Knuth's minimax algorithm.\]

Alternatively, suppose you care about the expected number of questions asked (average-case). Then do the same, except now define $h(Y)$ to be the entropy of a random variable that takes on the value $R$ with probability $n(Y,R) / |S|$. In other words, define

$$h(Y) = - \sum\_R {n(Y,R) \over |S|} \lg {n(Y,R) \over |S|}.$$

Then choose the query $Y$ that minimizes $h(Y)$.

There is no guarantee that these procedures are optimal, but I bet they're pretty good.

Related but not the same: you might also be interested in Ulam's game, a generalization of the game of 20 questions. Also, take a look at this post, which describes an algorithm for 20 questions based on entropy calculations.

---
Tags: xor
---


# Question
Title: How to determine $10^{\log n}$ and $3n^2$ which grows faster asymptotically?
My think is pretty easy that $10^{\log n} = n$, which is growing slower than $3n^2$.

However, many tutorial shows that $3n^2$ ranks before $10^{\log n}$.

I'm really confused.

# Answer
> 8 votes
You have to be careful here, since the answer depends on the particular log function you use. As Lieuwe noted if $\log$ in this context means $\log\_{10}$ then $10^{\log n}=n$ and certainly $n$ "ranks before" $3n^2$, under any reasonable interpretation of "ranks before". However, if we have a different base for the logarithm, that might not be the case.

It's not hard to show that $10^{\log\_b n}=n^{log\_b{10}}$ (take the log of both sides) and so $10^{\log\_b{n}}$ will be asymptotically larger than $n^2$ as long as $\log\_b10\>2$, i.e., when $b^2\<10$, so when you use logs to base $b$ with, say, $b=3$ you'll have $10^{\log\_b n}$ "ranks after" $3n^2$.

# Answer
> 4 votes
If you are using base 10 log, then yes, $10^{\log n}=n$. It has lower asymptotic growth than $3n^2$, as you note, because for every $c$, there is an $n\_0$ such that $3n^2\>cn$ for all $n$ which are greater than $n\_0$. Proving this is an exercise for the reader.

If you read that $3n^2$ ranks before $10^{\log n}$, then those sources are wrong. There are other functions that look superficially similar that do grow faster, such as $n^{\log n} = 10^{(\log n)^2}$ and $\log n^{\log n}=10^{\log n \cdot \log\log n}$.

# Answer
> 0 votes
As others have noted, it depends on the base of the $log$. When a base is not given, in computer science it is generally assumed to be 2. In mathematics, it is generally assumed to be $e$. In engineering, it is generally assumed to be 10.

---
Tags: asymptotics
---


# Question
Title: Does it matter if I reverse the arguments order of a lambda calculus function?
what is the difference between the below functions? $$\lambda x.\lambda y.f(x, y)$$ $$\lambda y.\lambda x.f(x, y)$$

And it appears that there is a $\texttt{reverse operation}$ in lambda calculus which can reverse the order of the arguments. So does the order actually matter?

I am asking this question because I am reading this paper, in which the author reverse the argument order in the 5th page: $$ \[\\!\[ R\[b\]\]\\!\] = \lambda y.\lambda x.\[\\!\[b\]\\!\](x, y) $$ Here $R$ is the ${reverse}$ $operator$. I am not sure why the author did this. And why it matters to change the order in which the arguments are taken.

# Answer
> 2 votes
You can compute either of them from the other, by using the aforementioned "reverse arguments" function.

However, they are very different as functions. For instance, the usual encoding of true is $\lambda xy.\\, x$ while false is encoded as $\lambda yx.\\, x$ ($\alpha$-equivalent to $\lambda xy.\\, y$), which is the flipped version of true. True and false are meant to be different.

Indeed, if we had true and false equal then, for any $M,N$ $$ M =\_\beta^2 (\lambda xy.\\, x) M N =\_{Hp} (\lambda yx.\\, x) M N =\_\beta^2 N $$ So, we would get that all $\lambda$-terms are equal, making the whole theory of lambda calculus trivial.

---
Tags: lambda-calculus
---


# Question
Title: Is there a language with non-isomorphic minimum-state UFAs?
For all regular languages L, by the Myhill-Nerode classes, all state-minimal DFAs for L are isomorphic.  On the other hand, "a regular language may have many non-isomorphic state-minimal nfas".  What about Unambiguous Finite Automata?  Every DFA is also a UFA, so every regular language has at least one UFA.  The natural numbers are well-ordered, so in turn every regular language has at least one state-minimal UFA.

Is there a regular language whose state-minimal Unambiguous Finite Automata are not all isomorphic to each other?

# Answer
> 3 votes
In their paper "A note about minimal non-deterministic automata" Arnold, Dicky and Nivat observe that the problem of finding non-isomorphic minimal automata was solved in a report by Christian Carrez (Lille, 1970).

They give the following example, which happen to be both unambiguous, so are applicable in your case too.

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


# Question
Title: Partitioning a bipartite graph to get disjoint components of same size
I have a bipartite graph $G = (V, E)$ where $V = S \cup T$ is the division into the two halves. I want to select $n$ elements from $S$ and $nk$ elements from $T$ such that the graph they generate has $n$ connected components, each of size $k+1$ and containing one element of $S$. To be clear, $n$ and $k$ are inputs to the problem: it's not a maximisation problem.

The naïve brute force algorithm would consider $\binom{S}{n}$ candidate subsets of $S$, and would do $O(E)$ work for each to identify vertices in $T$ which have an edge to exactly one element of the candidate subset of $S$. For fixed $n$ that's $O(S^n E)$.

I'm not optimistic, because it's an independence problem, but is there an algorithm for fixed $n$ and $k$ whose running time is polynomial in $E$ with exponent independent of $n$ and $k$?

# Answer
Your problem is NP-hard, even for any fixed $k \geq 3$ by a straight-forward reduction from 3-SET-COVER. Quick explanation: nodes of $S$ are triplets, nodes of $T$ are set elements and each triplet connected to all elements it contains.

I am still thinking about the case when $n$ is fixed.
> 3 votes

---
Tags: graphs, polynomial-time
---


# Question
Title: Prove consistency of maximum of two consistent heuristic functions?
Suppose we have two heuristic functions $h\_1$ and $h\_2$ which are both consistent, that is,

$$h\_i(n) \leq c(n,a,n') + h\_i(n')\qquad \ i\in\\{1,2\\}\\,,$$

where $c(n,a,n')$ denotes cost of reaching the successor node $n'$ with action $a$. Can we conclude that the $h\_3:=\max(h\_1,h\_2)$ is also consistent?

# Answer
Proof (Show consistency property of $h\_3$):

$$ h\_3(n) = \max(h\_1(n), h\_2(n)) \\ \leq max(h\_1(n')+c(n,a,n'), \ h\_2(n')+c(n,a,n')) \\ \leq \max(h\_1(n'), \ h\_2(n')) + c(n,a,n') = h\_3(n') + c(n,a,n') $$
> 5 votes

---
Tags: artificial-intelligence, search-algorithms, heuristics
---


# Question
Title: Vertex-disjoint cycles passing through a collection of vertices
I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist a collection of vertex-disjoint cycles $C\_1, C\_2, \ldots$ such that each $u \in U$ belongs to some cycle $C\_i$?

When $U=V$, I can see how to reduce this to the problem of finding a maximum matching in a bipartite graph. I'm not sure how to handle the case when $U$ is a strict subset of $V$.

# Answer
> 2 votes
If $U$=$V$ it reduces to a matching problem by splitting all of the vertices into a left-vertex and a right-vertex to create a corresponding bipartite graph. All existing edges in the original graph translate to the bipartite graph as low-cost edges directed left-to-right (from the origin's left-vertex to the destination's right-vertex). For each left/right pair, you add a high cost edge connecting the left to the right. (Unless it already had an edge due to a loop, in which case the edge remains low cost.) The minimum cost matching will use as few of those high cost edges as possible. The resulting matching corresponds to a set of vertex-disjoint cycles with the maximum number of total vertices because for each vertex not in a cycle, the high-cost edge is used.

Now assume $U$ is instead a strict subset of $V$. For each vertex not in $U$, consider the high cost edge connecting its left-vertex and right-vertex. Lower the cost of those edges so that the only remaining high-cost edges are the ones connecting left/right vertices in $U$. (Again, if a vertex in $U$ has a loop, the edge is instead low cost.) The minimum cost matching will use as few of those high cost edges as possible, thus maximizing the number of vertices in $U$ that are in cycles.

---
Tags: algorithms, graphs, matching
---


# Question
Title: How to solve an ILP problem with conditions in an objective function?
I have came accross this link.

I have an integer linear programming (ILP) problem
$$\max\_{(x\_1, x\_2,\ldots, x\_n)}\sum\_{i=1}^n x\_i\cdot f(x\_i),$$

$$\text{subject to } \begin{cases} ..., &(1)\\ L≤x\_i≤U,&(2)\\ x\_i \in \mathbb{Z}, i \in I,&(3)\\ \end{cases} $$ here $X=\\{x\_i \in \mathbb{Z}: L \le x\_i \le U, L\<0, U\>0, i\in I\\}$ is the variable, $I=\\{1,2, \ldots, n\\}$ is the set of indicies, the function $f(x\_i)$ is defined as $$f(x\_i) = \begin{cases} a\_i \in A, &\text{if } x\_i\>0, \\ b\_i, \in B, &\text{if } x\_i\<0.\\ \end{cases} $$ $A=\\{a\_i \in \mathbb{R}^+: a\_i\<a\_{i+1}, \forall i= 1, 2, \ldots, n-1\\}$, $B=\\{b\_i \in \mathbb{R}^+: b\_i\<b\_{i+1}, \forall i=1,2,\ldots, n-1\\}$ are the input (ordered) constants, such that $b\_i \< a\_i, i \in I$. In the system of constraints mentioned above the Eq.(1) means some extra constraints.

As the result I'd like to have the optimal solution $X^\*$ and corresponded values of the $n$ input constants $a\_i$ and $b\_i$, $i \in I$.

**Question.** How to solve an ILP problem with the function $f(\cdot)$ in the objective function?

**Update 4.**

I think, I can obtain the result with next steps:

1) make a precomputing of the input constants: $C=\\{c\_{ji}, i \in I, j \in J\\}$ is the set of permutations of $a\_i$ and $b\_i$, $J=\\{1,2,\dots, 2^n\\}$.

Let's $A=(2.2, 4.4, 6.6)$ and $B=(1.1, 3.3, 5.5)$ then $$C=\left(% \begin{array}{ccc} 1.1 & 3.3 & 5.5 \\ 1.1 & 3.3 & 6.6 \\ 1.1 & 4.4 & 5.5 \\ 1.1 & 4.4 & 6.6\\ 2.2 & 3.3 & 5.5\\ 2.2 & 3.3 & 6.6\\ 2.2 & 4.4 & 5.5\\ 2.2 & 4.4 & 6.6\end{array}% \right).$$

2) find the optimal solution $X^\*\_j$ of the $j$-th IPL problem from the set $$\max\_{(x\_1, x\_2,\ldots, x\_n)}\\{\sum\_{i=1}^n x\_i\cdot c\_{ji}, j \in J\\},$$ and apply $f(\cdot)$ to each element of $X^\*$. For instance,

$X^\*=\left(% \begin{array}{ccc} -1 & 3 & 2 \\ 1 & -3 & 3 \\ 1 & -4 & 2 \\ -1 & 4 & 1\\ -2 & 3 & 2\\ -2 & 3 & 5\\ 2 & -4 & 1\\ 2 & 4 & 1\end{array}% \right),$ $f(X^\*)=\left(% \begin{array}{ccc} 1.1 & 4.4 & 6.6 \\ 2.2 & 3.3 & 6.6 \\ 2.2 & 3.3 & 6.6 \\ 1.1 & 4.4 & 6.6\\ 1.1 & 4.4 & 6.6\\ 1.1 & 4.4 & 6.6\\ 2.2 & 3.3 & 5.5\\ 2.2 & 4.4 & 6.6\end{array}% \right).$

3) match the elements of $C$ and $f(X^\*)$ by rows: $Res=if(C==f(X^\*),1,0)$. In the example the $4$-th and $6$-th rows were matched only (denoted by 1's):

$$Res=\left(% \begin{array}{ccc} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\\ 1 & 1 & 1\end{array}% \right),$$

4) select the maximum from the values of objective functions for the matched rows only:

$\max\_{(x\_1, x\_2,\ldots, x\_n)}\\{\sum\_{i=1}^n x\_i\cdot c\_{ji}, j =\\{4,6\\} \\}=\max(-1\cdot 1.1 + 4 \cdot 4.4 + 1 \cdot 6.6, 2\cdot 2.2 + 4 \cdot 4.4 + 1 \cdot 6.6 )=\max(23.1, 28.6)=28.6$. Thus, the optimal solution of the intial ILP is: $X^\*=(2,4,6)$ which corresponds to the input constants $(a\_1, a\_2, a\_3)=(2.2,4.4,6.6)$.

**The weak points are:**

1. How to prove that you will have at least one matched pair on the step 3?
2. How to match elements $C$ and $f(X^\*)$ if $f(X^\*\_{ij})=0$ on the step 2?

# Answer
Introduce integer variables $x^+\_i,x^-\_i,y\_i$, where each $y\_i$ is 0 or 1. The intended meaning of $y\_i$ is that $y\_i=1$ means $x\_i$ is positive, $y\_i=0$ means $x\_i$ is zero or negative; and that $x^+\_i$ captures the positive part of $x\_i$ and $x^-\_i$ captures the negative part. We'll enforce that intention by adding the following constraints:

$$\begin{gather\*} x\_i = x^+\_i + x^-\_i\\ 0 \le x^+\_i \le U \cdot y\_i\\ L \cdot (1-y\_i) \le x^-\_i \le 0\\ 0 \le y\_i \le 1 \end{gather\*}$$

This ensures that the $x\_i,y\_i,x^+\_i,x^-\_i$ are consistent. Finally, note that

$$x\_i \cdot f(x\_i) = a\_i x^+\_i + b\_i x^-\_i,$$

so the objective function can be expressed as

$$\sum\_i a\_i x^+\_i + b\_i x^-\_i,$$

which is a linear function of the variables. Now maximize this objective function subject to the constraints above and any other constraints you might have, by feeding it to any ILP solver.

See Express boolean logic operations in zero-one integer linear programming (ILP) for other tricks of the trade.
> 1 votes

---
Tags: linear-programming, permutations, integer-programming
---


title: Finding trading cycles

text:
# Question
Title: Finding trading cycles
Say we have N persons and M items (when a person has a certain item, she usually only has one piece). For example,

* person 1 has item A, C, D, and wants item F
* person 2 has item B, C, and wants E
* person 3 has item E, and wants G

...

You get the idea. So it's basically a supply/demand matching problem, and if we represent this as a person-item matrix, it's gonna be a very sparse one.

So my question would be:

1. How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?
2. How do I find the shortest series (or path) that involves more than 2 people (so one-to-one exchange I think I've figured how by using some matrix operations)?
3. What would be the complexity for finding longest/shortest paths?

Any advice would be appreciated.

# Answer
> 5 votes
I'm assuming that items are always traded 1-for-1.

> How do I find the longest possible series (or path) of supply & demand matching among some people and therefore can foster an exchange?"

If you are only looking for one long path, then you are looking for a Hamiltonian circuit if one exists, so the decision version of the problem is NP-complete. If you are open to having multiple disjoint cycles of exchange and just looking for as many items as possible involved in the exchange, then it is the MAX SIZE EXCHANGE problem from the Kidney Exchange literature, and it is solvable in polynomial time.

---

P. Biro, D. F. Manlove, and R. Rizzi. Maximum weight cycle packing in directed graphs, with application to kidney exchange programs. Discrete Mathematics, Algorithms and Applications, 1(04):499–517, 2009.

---
Tags: algorithms, graphs, data-structures, shortest-path, matrices
---


# Question
Title: Correctness proof: 2-approximation of greedy matching-algorithm
**Input:** number of edges and vertices, and array of all edges in graph.

**Output:** array of edges that construct a matching, so that: $$\frac{\text{the number of edges in this matching}}{\text{the number of edges in maximum matching}} \geq \frac{1}{2}$$

---

**Algorithm I implemented**

Loop:

* take a random edge (actually in order it was given);
* if we can add it to our matching then add;

Finally we get a matching.

*The proof of condition* from **given** section by contradiction: let's compare our matching with the maximum one. Let's consider one edge from our matching. There're two cases: the same edge is in the maximum matching or not. If it belongs to the maximum then it's OK. If not, then there's could be not more than two adjacent edges in maximum matching. Let's assume that it happened with each edge in our matching. Nevertheless, our matching satisfies the given conditions: it has not less than 0.5 of number of edges in maximum matching.

However the proof seems not really good to me. I guess there also should be a proof by induction by edges of matching. But I can't come up with a good idea.

# Answer
> 4 votes
Let $M$ be a maximal matching in the graph $G$. Let $M'$ be the matching returned by our approximation algorithm (obviously this algorithm returns a valid matching).

For all $e\in M'$ let $M\_e\subseteq M$ be the set of edges in $M$ who have common vertices with $e$, meaning all $e\_M\in M$ such that $e\_M\cap e\neq\emptyset$. Obviously $\forall e\in M': |M\_e|\le 2$, since at the worst, $e=(u,v)$ and both $u,v$ are matched to some other vertex in $M$.

Note that $M=\bigcup\limits\_{e\in M'}M\_e$. To see why, suppose for the purpose of contradiction that there exists $e\in M$ with no common vertices with any $e'\in M'$. This means that our algorithm could have added $e$ to $M'$, contradiction. So we have:

$|M|\le\sum\limits\_{e\in M'}|M\_e|\le 2|M'|$.

---
Tags: algorithm-analysis, approximation, correctness-proof, matching
---


# Question
Title: In a DAG, longest path where every vertex has degree at most 2
I have a directed acyclic graph (DAG). How I can find the longest path using only vertices with degree at most 2?

Currently, I try this

```
def all_simple_paths(g):
  for path in all_paths(g):
      if len(path) > 2:
          center_path = path[1:-1]
          nodes_degree = g.degree(center_path).values()
          if max(nodes_degree) <= 2:
              return path

```

but that might output any path, rather than the longest path.

# Answer
> 3 votes
First, remove all vertices whose degree is greater than 2 (i.e., their degree was greater than 2 in the original graph). The result is a smaller DAG. This can be done in linear time.

Now, find the longest path in the resulting DAG. This can be done in linear time, too; see https://en.wikipedia.org/wiki/Longest\_path\_problem.

---
Tags: graphs, dag
---


# Question
Title: Amortized analysis for dynamic array - how to come up with a potential function?
I learned about amortized analysis and the potential method, I also leaned an example of a binary counter which I think I understand well.

In the case of the binary counter I understand the choice of the potential function - we are paying in advance for a transition from one to zero that must be made in the future when a bit changes from zero to one so the potential function is how much I payed that I haven't used already.

I got an exercise to find a potential function for a dynamic array with only inserts. I understand why a dynamic array have an amortized time of $O(1)$ on inserts - either the array have sufficient size and there is a simple insert costs $O(1)$ or the array is of size $k$ and it is full and in that case we spread the cost of the $O(k)$ is costs to insert the element with the last $k/2$ elements of the array (the new elements), the amortized cost is somewhat of $O(k)/(k/2)=O(1)$.

However I can't come up with a potential function, I don't see a methodical way of taking this understanding and making it formal with the potential method.

I have found online a potential function $\Phi=2n-m$ where $n$ is the number of current elements in the array and $m$ is the size of the array, I do see a factor of $2$ maybe relating to the $2$ in the $k/2$ above, but I can't manage to get to the above $\Phi$ myself.

I would appreciate help in understanding how to take my argument and derive $\Phi$ from it

# Answer
> 1 votes
One method is guess-and-check. We might guess that the potential function has the form $\Phi = \alpha n + \beta m$ for some constants $\alpha,\beta$, then try to work out a proof, and see what properties $\alpha,\beta$ need to have, and look for (solve for) a value of $\alpha,\beta$ that makes the proof work out.

Another way is to use intuition. Intuitively, the idea is that some operations are slow; and other operations might be fast to complete but are going to make our life harder down the road (i.e., are going to make other operations take longer). We can then look for a potential function that charges extra for operations that are fast right now but will make life harder down the road, and then use the accumulated charges to pay for the slow operations. Intuition might help us identify which operations should increase the potential and which should decrease the potential, and then we can go from there to try to work out the specifics.

---
Tags: algorithms, algorithm-analysis, amortized-analysis
---


title: what is edge-disjoint cycles in graph?

text:
# Question
Title: what is edge-disjoint cycles in graph?
I was reading something about Eulerian Tour and there is one property claiming that:

> An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree.

Can someone explain what is edge-disjoint cycles?

Wikipedia: Eulerian path

# Answer
> 4 votes
A set of cycles $C$ of a graph $G=(V,E)$ is edge-disjoint if the cycles $c\_i$, $c\_j \in C$ have no edges in common.

---
Tags: graphs, eulerian-paths
---


title: Unique min-cut means unique max flow?

text:
# Question
Title: Unique min-cut means unique max flow?
This is not a home work question.

Is that correct to say in a flow network, if min cut is unique then max flow must also be unique?

Assume we have two max flow in a network. Then for each max flow, we can get a min cut and they are surely different.

# Answer
I do not agree with the downvoters of your question. This questions seems like a legit misunderstanding of the statement of the min-cost-max-flow theorem.

The theorem states that the **value** of the sum of edge weights in a minimum $s$-$t$ cut of a graph is equal to the **value** of the maximum $s$-$t$ flow in the graph interpreted as a flow network. It does not establish a one-to-one correspondence between flows and cuts.

In fact, this correspondence cannot be established in general. Here is a counter example of an unweighted undirected graph (all weights/capacities are unit):

$1$-$5$ max-flow/min-cut is equal to one. While there is a single minimum cut ({1 - 2}). There are a lot of possible maximum flows (take the unit of flow entering 2 and distribute it between 3 and 4 as you like).
> 2 votes

---
Tags: graphs, network-flow
---


# Question
Title: Relationship between an integer N and the number of bits n required to represent the integer
I'm trying to understand the time complexity of the following code in terms of n.

Pseudocode for trial division:

I understand that the time complexity of the algorithm is O(sqrt(N)). However, can someone explain how the person in the link below came up with O(e^(n/2)). In other words, what's the mathematical relationship between N and n? Thanks.

Time complexity explanation:

# Answer
> 2 votes
The integer $N$ takes $\log\_2 N$ bits to write down. Set $n = \log\_2 N$. Then $N = 2^n$, so $\sqrt{N} = 2^{n/2}$.

I'd guess they are using the natural logarithm (to base $e$), which is where they get $e$ instead of $2$. That's a bit odd but I suppose it is valid.

See also Complexity of multiplication and Precise runtime of the algorithm to find number of digits in an integer.

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


# Question
Title: Confusion regarding terminology surrounding perceptron learning
I am having trouble understanding the terminology with perceptron learning. Is my current understanding correct? Let's say I have some data that classifies what type of flower a particular flower is. And let's say the factors taken into consideration are petal size, petal coloring, and leaf size. So my current understanding is that we take every pair of inputs and make them the axis of a graph(e.g. leaf size vs petal coloring). So in this case, we would have 3 graphs. Now, we plot the data points and see if it is linearly separable. That is, we can draw a line called a "decision boundary" that separates the data into two regions to be able to differentiate which inputs correlate with which outputs. This line is defined by $w^T \cdot x = y$. However, my first confusion is the following. How are 3 different graphs each with pairs of inputs (the 2 axis) represented using a equation of a single line that is used as the input layer of the neural network?

My second confusion is, is the objective function what defines how the $w^T \cdot x$ is to be interpreted? For instance, something like $y = 1 $ if $w^T \cdot x \geqslant 0$ and else $y = 0$. Also, as I have understood, the learning rule is supposed to be how to update consecutive weights.

Can someone please explain the situation I have laid out. I am reading Bishop's book on Neural Networks. But I am confused by the text.

# Answer
> In machine learning, the perceptron is an algorithm for supervised learning of binary classifiers.

Its much complex than just drawing some graph and fitting a line to divide these data. I should tell you that you gone entirely wrong about the core concept.

Our brain are capable of solving complex problem, few of which are impossible for a computer to figure out. Thus scientist studies our brain and tried to **mimic its biological structure** to achieve its capability in computers. One of the initial steps towards it was perceptron.

Two types of perceptron are:

1. Single Layer perceptron - works only in linearly separable data.
2. Multi Layer perceptron - work with non linear data too.

Perceptron have the **capability of learning** from a given (training) data and implement that knowledge into another (new) data as we desire.

Your problem: (desired output)

> classify what type of flower a particular flower is?

There are thousands and thousands of types of flowers so, for simplicity I'm modifying you question as "classify if this flower is jasmine or not"

Input you fed to the perceptron are: (features)

> petal size, petal coloring, and leaf size

If you construct a perceptron (network) it will be:

$x\_1, x\_2, x\_3$ are input neuron, $w\_1, w\_2, w\_3$ are weights (mimicking the strength between biological neurons) and $Y$ is the output neuron.

You may have a question "*Why 3 nodes (or neurons) in input and 1 node in output layer?*" so I'm explaining that below:

3 neuron in the input layer as we have 3 features(or inputs).

1 neuron in the output layer as we have 1 class (jasmine or not).

Input layer have 3 nodes which will carry you features to output neuron which will classify if its jasmine or not.

Unlike other classification methods, here we should teach the system (like a human brain learns when we first see a jasmine flower).

*How will a computer come to know if its a jasmine flower?* Answer is, by showing sample features (petal size, petal coloring, and leaf size) of many jasmine to it.

**Note**: In biology neural network, the neuron get activated when electric impulses exceeds a threshold. Mimicking it, we use a threshold function to active(output one) or not(output zero) a artificial neuron\[ threshold value = $\theta$ \].

If the input is a jasmine flower, output neuron will output '1' else '0'.

$ Y = \begin{cases} \text{1,} &\quad\text{if $\sum\_{}^{} w\_ix\_i\>\theta $}\\ \text{0,} &\quad\text{else}\\ \end{cases} $

**Note**: When we consider $w\_i$ and $x\_i$ as vector ($W$ and $X$ respectively) its can be written as $Y=W^tX$ (you mentioned it as objective function).

We give sample features (petal size, petal coloring, and leaf size) of jasmine to input neurons $x\_1,x\_2,x\_3$ respectively and tell its a jasmine(set output as one). Meanwhile, the weights $w\_1, w\_2, w\_3$ take some random (initial) values and output $Y$ is found. As we have given a jasmine data to input neuron we expect the output to be one but as weights are taken in random, the output wont be one and an error $E$ is formed.

$E =|ExpectedOutput - ActualOutput|$

This error is propagated back, so that according to the error the weights $w\_1, w\_2, w\_3$ can be updated such that next time error will be much lesser or zero.

This process is called **Training**, the data used to train the perceptron is called Training data and the network after training is called trained network. The training is called *back-propagation algorithm*.

It learns from the training data we provide and this trained network can easily classify a new flower(can tell if its jasmine or not).

Read these : Biological neural networks, NPTEL Artificial intelligence, MIT Introduction: The Perceptron
> 2 votes

---
Tags: artificial-intelligence, neural-networks, perceptron
---