# Question
Title: What is the complete version of the paper: "How to Generate and Exchange Secrets (extended abstract)" by Andrew Yao?
I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. However, I can only seem to locate the extended abstract which lacks proofs and does not seem to mention garbled circuits. It only appears to define useful properties for solving the problem and state several theorems without proof. A complete version of the paper is mentioned at the end of this extended abstract, but I cannot locate it. Is the complete version under a different name?

I have already found expositions that explain garbled circuits. At this point I am interested in finding the complete paper, if possible.

# Answer
Garbled circuits were only implied by the extended abstract. They were only explicitly introduced in the talk given by Andrew Yao at the conference.

This is clear from a footnote on the Turing Award Page:

> The first of these two papers introduces secure function evaluation, and gives a \> protocol for the famous Millionaires’ Problem. In talks related to these papers \> Yao introduced a technique for secure computation known as garbled circuits.

which may be found here: http://amturing.acm.org/bib/yao\_1611524.cfm#bib\_6

Credit is due to Wandering Logic for giving this very helpful answer in the comments above.
> 1 votes

# Answer
Wikipedia now has a brief survey of the history of garbled circuits with reference to published materials:

https://en.wikipedia.org/wiki/Garbled\_circuit
> 0 votes

---
Tags: reference-request, cryptography, security
---


# Question
Title: Generating a random minimum spanning tree
I am tring to find the simplest method of generating a random minimum spanning tree.

My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a grid which all connect together in a random way.

One method I have come across is to generate random points on a grid and run a Randomized incremental Delaunay triangulation algorithm (Explained quite nicely here) on it with the weights of the nodes being determined by their distances from eachother. Couple this with Kruskal's algorithm and then I will have my minimum spanning tree.

I'm relatively new to this field of Maths and was having trouble creating the Delaunay algorithm (and even more trouble understanding some libraries out there) and thought perhaps there is a simpler method to get the same result.

One method that came to mind was to create a fully connected graph of random points (much simpler for me to do) and then run Kruskal's algorithm on that, However my intuition tells me that this would not be so efficient even though I am only talking about a maximum of 10 or 15 nodes for my intended use.

Are there any other methods I should consider to generate such a graph? I've come across the Prüfer sequence which seems incredibley simple, however with my current understanding of it I do not see how I can take into account the positions of the Rooms/Nodes on the grid or perhaps even chose where to place the nodes on the grid.

# Answer
> 1 votes
Since there are just about 10 random points, the following simplest algorithm is should be fast and easy enough for your need.

1. Generate random points $p\_i$, $0\le i\le9 $ in the grid, in whichever way you prefer.
2. Compute all Euclidean distances between each pair of points. (In fact, I believe for your purpose, the Manhattan distance should be fine as well. What is nice about Manhattan distance is that it is much easier to code and compute. The MST generated will be roughly the same.)
3. Compute the MST of the points with the distances between them.

There are many existing libraries that computing MST. You can just select any popular one that is convenient for you. I guarantee you that they will be fast enough for your need.

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


# Question
Title: Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$
I recently thought of the following problem:

Given a set $A$ of sets find a minimal set $B$ of pair-wise disjoint sets such that each set in $A$ can be expressed as a union of sets in $B$.

For example, if $A = \\{ \\{ 1, 2 \\}, \\{ 1, 2, 3 \\}, \\{3, 4\\}, \\{4\\} \\}$ then $B = \\{ \\{ 1, 2 \\}, \\{ 3 \\}, \\{ 4 \\} \\}$.

I designed the following algorithm:

1. Let $B = \emptyset$ initially.
2. Let $S$ be the set of set(s) of lowest of cardinality in $A$.
3. Let $I$ be the intersection of the sets in $S$.
4. If $I = \emptyset$: add the sets in $S$ to $B$, remove the elements in the sets in $S$ from the sets in $A$, and remove $\emptyset$ from $A$.

If $I \neq \emptyset$: add $I$ to $B$, remove the elements in $I$ from the sets in $A$, and remove $\emptyset$ from $A$.
5. Repeat from step 2 until $A = \emptyset$.

My questions are:

* Does this problem have a name?
* Is this algorithm correct?
* What is the complexity of this algorithm?
* Is this algorithm optimal, and if not, what would be a better algorithm?

# Answer
Essentially you are finding all non-empty components of the Venn diagram of the sets in $A$. So here is an algorithm:

```
B = empty set
for each set S in A:
    for each set T in B:
        remove T from B
        compute (S \cap T), (T \ S) and (S \ T)
        if (S \cap T) is not empty, add (S \cap T) into B
        if (T \ S) is not empty, add (T \ S) into B
        S = S \ T
    if S is not empty, add S into B
return B

```

This algorithm runs in $O(nm)$ time where $n$ is the number of all elements involved, and $m$ is the number of sets in $A$.

---

For your example, initially $B$ is empty.

After dealing with $\\{1,2\\}$, $B=\\{\\{1,2\\}\\}$.

After dealing with $\\{1,2,3\\}$, $B=\\{\\{1,2\\},\\{3\\}\\}$.

After dealing with $\\{3,4\\}$, $B=\\{\\{1,2\\},\\{3\\},\\{4\\}\\}$.

After dealing with $\\{4\\}$, $B=\\{\\{1,2\\},\\{3\\},\\{4\\}\\}$.
> 2 votes

# Answer
This problem sounds very interesting. I am not aware of any name for this problem, however.

Your algorithm is not correct.

Here is a counterexample. $A = \\{ \\{ 1, 2 \\}, \\{ 1, 3 \\}, \\{1, 4\\}, \\{2,3\\}, \\{2,4\\}\\}$. The minimal set of pairwise disjoint sets such that each set in A can be expressed as a union of sets in it is $B = \\{ \\{1\\}, \\{2 \\}, \\{ 3 \\}, \\{ 4 \\} \\}$, which has 4 elements. However, in the step 4 of your algorithm, all 5 sets in $A$ will be added.

In fact, as you pointed out, the step 4 may add non-disjoint sets, thus invalidating the algorithm. The smallest counterexample is $A = \\{\\{1, 2 \\}, \\{2, 3 \\}, \\{1,3\\}\\}$. The step 4 of the algorithm will add all 3 sets in $A$, which contains no disjoint pairs.
> 1 votes

---
Tags: algorithms, complexity-theory, sets
---


# Question
Title: Proving correctness of inefficient algorithm - Path between two vertices
Consider the following inefficient algorithm that decides if there is a path between two vertices s and t of a directed graph G. Show that the algorithm is correct. In addition, analyze its complexity and compare it with the other path between two vertices algorithms (Dijsktra, Bellman-Ford Algorithm, etc.) and explain why this algorithm is inefficient.

```
ALGORITHM Reachable(G, s, t)
     RETURN A(G,s,t,|V(G)|)
END Reachable

FUNCTION A(G,s,t,d)
     IF d=1 THEN
        IF s == t OR there is a directed edge (s,t) in G THEN
              RETURN TRUE
        ELSE
              RETURN FALSE
     ELSE
          FOR each vertex v in G DO
              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF
          ENDFOR
          return FALSE
END A

```

I tried to prove correctness using invariants, but I'm not sure if that's the best way to prove it. Could you help me, please?

And I tried to obtain time complexity considering the for-loop, but also I have doubts.

Thanks a lot for your help!

# Answer
> 1 votes
If we interpret d/2 as real number division, then A(G,s,t,3) will run forever. If we interpret d/2 as integer division such as 3/2=1, then the algorithm will fail for a graph which is just a path of 6 vertices and 5 edges. If we interpret d/2 rather unnaturally as integer division of d+1 by 2, the algorithm becomes correct but the semantic of A(G,s,t,d) is not very natural either.

Hence, we will change the following part of the algorithm

```
              IF A(G,s,v,d/2) AND A(G,v,t,d/2) THEN
                   RETURN TRUE
              ENDIF

```

to

```
              IF A(G,s,v,d/2) AND A(G,v,t,(d+1)/2) THEN
                   RETURN TRUE
              ENDIF

```

together with the conventional interpretation of d/2 and (d+1)/2, the integer division. We will see this change makes the most sense as shown by the simple proposition below that characterizes the semantic of function A(G,s, t,d).

---

We have the following proposition.

**Reachable(d)**: A(G,s,t,d) returns TRUE if and only the distance from s to t is less than or equal to d.

Let us prove the above proposition by induction on d.

The base case when d = 1 is trivial.

Suppose reachable(d) is true for all d \<= n, where n\>=1. Let check the case when d=n+1. There are two cases.

* n+1 is even. Suppose n+1 = 2k. Checking the definition of function A, we can see that A(G,s,t, n+1) returns TRUE if and only if there is a vertex v such that both A(G,s,v, k) and A(G,v,t,k) return true, i.e., both the distance from s to v and the distance from v to t are less than or equal to k, thanks to the induction hypothesis since k \<=n. That means the distance from s to t is less than or equal to 2k = n+1.
* n+1 is odd. I will leave this case for you to check.

Proof is done.

The correctness of the algorithm is the correctness of reachable(|V(G)|), since there is path from s and t if and only if the distance from s to t is less than or equal to |V(G)|-1 (or |V(G)|, which is equivalent).

---

To verify that this algorithm can be very inefficient, we should find an example where it runs very slowly. We would like to choose a graph for which A(G,s,t,d) computes as much as possible and return as late as possible. How about graphs with no edges? Let D be a graph of 2^n vertices without an edge.

Claim: A(D,s,t,2^k) will call A(D,\*,\*,2^(k-1)) 2^(n+1) times.

Claim: A(D,s,t,2^n) will call A(D,\*,\*,1) (2^(n+1))^n=(2^n)^(n+1)=|V(D)|^(log |V(D)| +1) times.

---

I will let you contemplate why this algorithm is so inefficient.

---
Tags: algorithms, graphs, algorithm-analysis, time-complexity, correctness-proof
---


title: Point rank in 2D plane time complexity?

text:
# Question
Title: Point rank in 2D plane time complexity?
I'm reading about the algorithm of finding the ranks of all points in a 2D plane, I don't understand the time complexity formula for it. It has four steps:

1. Compute the median of x-coordinates of all point, and divide the plane into two half Left, and Right.
2. Recursively do 1. then when there is only 1 point, rank(that point)=0.
3. Sort points by y-coordinate in Left, and Right separately.
4. Update Right.

I understand the idea of these steps, and 3. has complexity $O(n\log n)$, but the time complexity formula in my book is

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

why the last term is not $\Theta(n\lg n)$? That is my current idea is that the $T(n)=\Theta(n\lg^2n)$, by applying master's theorem.

# Answer
I think I may solve it but I'm not sure: In short the sorting can be done in $\Theta(n)$, so the book statement, hence my assumption, is not correct. The "Sort points by y-coordinate in Left, and Right" actually only need to merge it, and this step is $\Theta(n)$.
> 0 votes

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


# Question
Title: Whether same output is obtained for the two queries
Consider the following SQL Queries executed on the relation Employee:

> Employee (Eid, Ename, sal)

Eid is the primary key

Queries:

> S1:SELECT count (\*) FROM Employee;
>
> S2: SELECT count (Eid) FROM Employee;

Will these queries return the same result or different results?

According to me, these queries should return same values.

But my solution manual claims that the values returned should be different. It says that S1 will also include results where Eid field is empty.

But according to me, the primary key field can never be empty. So, there will never be a case where Eid field will be empty. As this field will never be empty, the output of S1 and S2 should be equal.

Can anyone please tell me whether I am correct? If not, please tell me what I am doing wrong.

Thanks in advance!

# Answer
> 1 votes
> where Eid field is empty.

What do you mean by "empty"? Perhaps you mean 'null'?

What words *exactly* does your "solution manual" use? "empty" or "null"?

If the `Eid` field is `CHAR` there could easily be a row with `Eid` "empty" -- that is: zero length, or containing only space characters. `count(*)` and `count(Eid)` return the same value in that case.

If the `Eid` field is `NULLABLE` there could easily be a row with `Eid` null. `count(*)` will include that row, whereas `count(Eid)` will not.

Usually fields in keys are expected to be `NOT NULL`. Some vendors' implementations of the SQL standard insist on `NOT NULL`. But some don't. It is good practice to make key fields `NOT NULL`. Presumably your manual is getting you to think about why.

---
Tags: database-theory, relational-algebra, relational-calculus, tuple-relational-calculus
---


# Question
Title: Algorithm to find sets of vertices connected to at most one incoming and one outgoing vertex outside the set
I have a directed graph with vertices $V$, and I need to find a strict subset $U$ of its vertices such that:

1. $U$ contains at least two vertices, and $U \neq V$
2. There is at most one vertex in $V \setminus U$ connected to a vertex in $U$
3. There is at most one vertex in $U$ connected to a vertex in $V \setminus U$

(assuming there is such a subset).

The current algorithm I have works by recursively calling itself with one added vertex until the set has the appropriate conditions, but it's much too slow.

Is there any algorithm I could use to do this more efficiently?

# Answer
> 0 votes
Let's name the vertices $v \in V \setminus U$ and $u \in U$ the vertices that are allowed to have out-neighbors anywhere.

Suppose that we know the vertex $u$ and delete all its out-edges.

Now we are looking for a vertex $v$ that "separates" the graph in two components, $V \ni v$ and $U \ni u$.

We can find $u$ in $O(n)$ time by trying all possibilities. We can also find the strongly connected components in $O(n + m)$ time. In this graph, we must find $v$ with the above property. That can be done in linear time $O(n + m)$. Hence it all runs in $O(n(n+m))$ time, which is at most $O(n^3)$.

---
Tags: algorithms, graphs
---


title: Cache and Main Memory

text:
# Question
Title: Cache and Main Memory
As we know that average access time is given by

t=p\*(tc)+(1-p)\*(tc+tm)

where t represent the average time, p is the hit ratio , tc is the time to access the data from the cache and tm is time to retrieve data from main memory. I was wondering wouldn't it be possible to decrease this time to

t=p\*(tc)+(1-p)\*(tm)

if we search for the data in both the cache and the main memory in parallel?

# Answer
> 2 votes
It would be possible for that access, but nevertheless, it is not a good idea.

Even with relatively small caches, the cache miss rate of most programs is well under 10%. If a designer did what you proposed, what would likely happen is

* access 1 is looked up in the cache while a memory access is started;
* the cache reports the lookup is a success;
* the next instruction that wants to access memory now *cannot* proceed. It could look up the cache, but (with your scheme) it would need to look up memory at the same time, and the memory subsystem is still working on access 1. (In fact, in has just started working on it.)

The point is that the memory subsystem cannot possibly support as anywhere near as many lookups per second as the CPU can issue. One of the points of the cache is reduce the load on it to level it can support.

---
Tags: computer-architecture, operating-systems
---


# Question
Title: So if a problem is more difficult the language it represents is smaller?
I'm reading the definition of polynomial time reducible:

> Let $L\_1, L\_2$ be two language. If $L\_1$ is polynomial time reducible to $L\_2$ then exists $f:\\{0,1\\}^\*$ s.t. $\forall x\in\\{0,1\\}^\*$ $$x\in L\_1\iff f(x)\in L\_2$$

For me this means the $L\_1$ may be bigger (in cardinality) than $L\_2$, but $L\_2$ is more difficult since $L\_1$ can be solved after reduced to $L\_2$?

# Answer
$L\_1$ and $L\_2$ are always countably infinite, and thus "equally big".

If any language is finite, then it is "constant time" recognizable.
> 7 votes

---
Tags: np-complete, reductions, decision-problem
---


# Question
Title: "Process functions" in iterative and recursive depth-first search
I was reading *The Algorithm Design Manual* by Steven Skiena, and I noticed his use of "process functions" in depth-first search and breadth-first search. Consider the following pseudocode for depth-first search:

```
DFS(G,u)
    state[u] = "discovered"
    process_vertex_early(u)
    entry[u] = time
    time = time + 1
    for every vertex v adjacent to u
        if state[v] = "undiscovered"
            parent[v] = u
            process_edge(u,v)
            DFS(G,v)
        else if state[v] != "processed" or G is directed
            process_edge(u,v)
    state[u] = "processed"
    exit[u] = time
    process_vertex_late(u)
    time = time + 1

```

Notice the use of the `process_vertex_early`, `process_edge`, and `process_vertex_late` functions.

I am attempting to implement an iterative version of depth-first search to avoid a stack overflow with larger graphs. Here is the pseudocode for my attempt:

```
DFS(G)
    mark every vertex in G as "undiscovered"
    mark the start and finish time for every vertex in G as (0, 0)
    time = 0
    for every vertex vrtx in G
        create empty stack S
        if vrtx is "undiscovered"
            S.push(vrtx)
        while S is not empty
            time = time + 1
            u = S.top
            if u is "undiscovered"
                u.start_time = time
                mark u as "discovered"
                process_vertex_early(u)
            done = true
            for every vertex v adjacent to u
                if v is "undiscovered"
                    done = false
                    v.parent = u
                    process_edge(u,v)
                    S.push(v)
                else if v is not "processed" or G is directed
                    process_edge(u,v)
            if done
                S.pop
                mark u as "processed"
                u.finish_time = time
                process_vertex_late(orig)

```

I ran both versions of the code for a sample graph of 10 vertices and generated the following data:

```
Iterative data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       18      -1
1       1       1       1       14      14      5
2       1       1       1       13      13      5
3       1       3       1       5       11      7
4       1       3       1       2       17      0
5       1       6       1       3       16      4
6       1       3       1       6       10      3
7       1       3       1       4       12      5
8       1       3       2       8       8       9
9       1       3       1       7       9       6

Recursive data:
vertex  early   edge    late    s_time  f_time  parent
0       1       1       1       1       20      -1
1       1       1       1       14      15      5
2       1       1       1       16      17      5
3       1       2       1       7       10      6
4       1       2       1       2       19      0
5       1       4       1       3       18      4
6       1       2       1       6       11      9
7       1       2       1       8       9       3
8       1       2       1       4       13      5
9       1       2       1       5       12      8

```

Here is the adjacency list for the graph I used:

```
0 : 4
1 : 5
2 : 5
3 : 6,7
4 : 0,5
5 : 1,2,4,7,8
6 : 3,9
7 : 3,5
8 : 5,9
9 : 6,8

```

I know that the vertices will be visited in different orders for the recursive and iterative implementations and that neither order is right or wrong, which is why the values for s\_time, f\_time and parent are different. The `early` and `late` columns represent the number of times each function was called for each vertex, while the `edge` column represents the number of times the `process_edge` function was called for each vertex as the `u` vertex. I feel like these values should be the same for both implementations or at least more similar than they are.

My question is: have I preserved the semantics of the original algorithm with my iterative translation? What changes, if any, should I make?

# Answer
Here is an iterative algorithm which preserves the behavior of the original recursive algorithm. The idea is to let each vertex to keep track of its next child to visit.

```
Iterative DFS on G starting at vertex v
    mark every vertex in G as "undiscovered"
    create stack S, each of whose elements will be a pair that consists of a vertex and the index of its next child to visit
    S.push([v,0])
    state[v] = "discovered"
    process_vertex_early(v)

    while S is not empty
        let [v, i] be the top element of S
        if i is less than the number of neighbours of v
            update that element to [v, i+1]
            let w be the i-th neighbour of v
            if w is marked "undiscovered"
                state[w] = "discovered"
                process_vertex_early(w)
                parent[w] = v
                S.push([w, 0])
                process_edge(v, w)
            else if state[w] is not "processed" or G is directed
                process_edge(v,w)
        else
            pop S
            process_vertex_late(v)
            state[v] = "processed"

```

There are general strategies that convert recursive algorithm/functions to iterative algorithm/functions. You can search "recursion and iteration" for more information if you have not done it yet.
> 2 votes

# Answer
I accepted the answer by @Apass.Jack because it did allow me to exactly replicate the behavior of the original algorithm, albeit with some modifications. I wanted to get the start and finish times for each vertex, so I modified it to get those. I also modified it so that it does not allow the user to provide a start vertex and instead iterates through all the vertices, as in CLRS. I had forgotten to mention this when I asked the question.

**Updated pseudocode**:

```
DFS(G)
    mark every vertex in G as "undiscovered"
    set the start and finish time for every vertex in G to (0,0)
    set the parent for every vertex in G to -1
    time = 0
    for every vertex u in G
        create stack S, each of whose elements will be a pair that consists of a vertex and the index of its next child to visit
        if u is "undiscovered"
            S.push([u,0])
        while S is not empty
            let [v,i] be the top element of S
            if v is "undiscovered"
                time = time + 1
                v.start_time = time
                mark v as "discovered"
                process_vertex_early(v)
            if i is less than the number of neighbors of v
                update that element to [v,i+1]
                let w be the i-th neighbour of v
                if w is marked "undiscovered"
                    parent[w] = v
                    process_edge(v,w)
                    S.push([w,0])
                else if state[w] is not "processed" or G is directed
                    process_edge(v,w)
            else
                time = time + 1
                pop S
                state[v] = "processed"
                process_vertex_late(v)
                v.finish_time = time

```

This new algorithm generates the same exact data as the recursive pseudocode presented in the original question, both for directed and undirected graphs.
> 1 votes

---
Tags: graphs, graph-traversal
---


# Question
Title: How do you detect if an algorithm is running at O(nlogn)?
Given only input and output(e.g. runtime), how do you know if an algorithm is running at O(nlogn) time complexity?

For example, how does LeetCode detect my code is running at O(nlogn)？ https://leetcode.com/problems/sort-list/description/

> Sort a linked list in O(n log n) time using constant space complexity.

---

Here's what I think:

I assume the complexity formula looks like $ f(x) = a\cdot x \cdot\log\_{b} x\ $

Then for input $x\_2 = 2x\_1$, $ \frac{f(x\_2)}{f(x\_1)} = 2\cdot\log\_{x\_1}x\_2 $

So I take inputs like $2,4,8,16...$, get each runtime let's say $i\_1,i\_2,i\_3,i\_4... $. Then check if runtime ratio $\frac{i\_2}{i\_1}, \frac{i\_3}{i\_2} ,\frac{i\_4}{i\_3} \approx \log\_{2}4, \log\_{4}8,\log\_{8}16...$.

If it is, then I would "guess" it's running at O(nlogn).

**Can I make a good "guess" based on the "characteristic" I described above?**

# Answer
> 1 votes
Look at the definition of f(n) = O (g (n)): There is a constant c \> 0, and N \> 0, such that for every n \> N we have f (n) ≤ c * g (n).

If you run your problem with sizes up to size X, then we can pick N = X + 1, and all your measurements up to size X are completely irrelevant. So you can *only* determine the time complexity of an algorithm by mathematical analysis, not by measurements.

You can of course measure the execution time of a specific implementation for various problem sizes, and then say for example "for various problem sizes n from 1 to $10^{15}$ where I measured the execution time, 3.74 n $log\_2$ n microseconds was a good approximation to the execution time of this algorithm".

# Answer
> 1 votes
I would like to apologize for sloppy notation in advance.

Recall that $\log\_2 10^{10} \< 34$, so that for any practical purposes, $O(n \log n)$ will be bounded by $34 \cdot O(n)$, which of course is $O(n)$ (again for all practical purposes).

That means that if language A is 34 times faster than language B, then an $O(n)$ algorithm in B is indistinguishable from an $O(n \log n)$ algorithm in language A.

In practice, it's not possible without a theoretical analysis of the algorithm.

However, it's often simpler to distinguish an $O(n \log n)$ algorithm from an $O(n^2)$ algorithm (in the same language, at least), although we do have problems distinguishing an $O(n \log n)$ algorithm in Python from an efficient $O(n^2)$ in C/C++ in programming contests.

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


title: Check if one condition includes another

text:
# Question
Title: Check if one condition includes another
I have two conditions A and B in a form of "ast tree". How can I check that B is more strict than A? I.e. if B is true then A is always true.

Example

A: x = 1 and (b = 2 or c = d)

B: y = 5 and x = 1 and (b = 2 or c = d)

Does B include A -\> true

---

A: x = 1 and (b = 2 or c = d)

B: y = 5 and x = 1 and (b = 2 or c = d)

Does B include A -\> false

---

This seems to be a common task for a specialist in logical math. But I have only very basic knowledge about logical arithmetics. Any articles/studies about subject appreciated.

# Answer
If your ASTs have a small number of conditions, then you can use the following naive approach.

1) Convert your ASTs to a CSOP (Canonical Sum Of Products) expression. From your example, lets convert each condition to a boolean variable and express $A$ and $B$ as boolean expressions in the following variables

$p: (x ==1)$
$q: (y==5)$
$r: (b == 2)$
$s: (c == d)$

Now
$ A: \space p \cdot (r + s)$
$B: p \cdot q \cdot (r + s)$
Normalising $A$ and $B$ yields
$A: p \cdot \lnot q \cdot r \cdot \lnot s + p \cdot \lnot q \cdot r \cdot s + p \cdot q \cdot r \cdot \lnot s + p \cdot q \cdot r \cdot s + p \cdot \lnot q \cdot \lnot r \cdot s + p \cdot q \cdot \lnot r \cdot s $
$B: p \cdot q \cdot r \cdot \lnot s + p \cdot q \cdot \lnot r \cdot s + p \cdot q \cdot r \cdot s $

2) Check if $ B \subseteq A$. In the above example it is true. This implies $B$ is stricter than $A$. If thought logically, all conditions in $B$ are fulfilled by $A$, but $A$ also satisfies other conditions not in $B$. Hence, $B$ is stricter compared to $A$.

Note: Expanding boolean expressions to normal forms requires exponential space. The algorithm might need some optimisation tweaks for larger expressions.
> 0 votes

---
Tags: logic
---


# Question
Title: Why are not all recursive languages undecidable?
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.

If a language is an REL (recursive enumerable language), I know that there exists a TM (Turing machine) that accepts it (regardless of the TM halting or not). Say, however, that for a language $L$ you have found a TM which accepts it, thus indicating $L$ is REL. We know that, given a TM, it is undecidable whether the TM halts or not. Thus, it is not possible to deduce whether $L$ is recursive or not: we have a TM that accepts $L$, but whether the TM halts or not is undecidable and, thus, we cannot comment on whether $L$ is recursive or not; this makes telling whether $L$ is recursive or not *undecidable*. Hence, recursive languages should be undecidable―which they are not!

What is wrong with the above reasoning?

# Answer
> 3 votes
You are correct. The *problem* of deciding "$L$ is a recursively enumerable language" is undecidable. However, that does not make $L$ itself undecidable.

Do not mistake a language for its class! Telling whether $L$ is in a class is definitely **not** the same as deciding membership in $L$.

# Answer
> 1 votes
You're talking about the following two problems:

1. I give you a string and ask "Is it in this recursive language?"
2. I give you a language and ask "Is this language recursive?"

You're assuming that they're the same problem, but they're not.

---
Tags: formal-languages, turing-machines, undecidability, decision-problem, semi-decidability
---


# Question
Title: Optimal Loading of a Hopping Airplane Minimum Cost Flow Problem
I have a Problem with an Optimal Loading a Hopping Airplane example . This is the Part of Minimum Cost Flow Problem.. .. I dont understand a Picture at all. I should to make one example with numbers and i need to show, how could i send flow along the Airline with bigger Revenue und possible smallest cost... Thank you for your Attending..

# Answer
> 1 votes
One approach to understand some complicated situation is to figure out some simplest but still meaningful situations.

In the current situation, let us check a situation when there are only two hops, hop 0 and hop 1. The simpler situation when there is only one hop is too trivial to be instructive, sine there will be no passenger to pick up.

Picking up your pen (or pencil or stylus or your finger), draw the following reduced version of Figure 9.4 in the reference provided.

The above direct network means

* there are up to $b\_{12}$ passengers at node 1-2 who can be picked up at node 1 (hop 1) and who should be dropped at node 2 (hop 2)
* The cost of the arc from node 1-2 to node 1 is $-f\_{12}$, where $f\_{12}$ is the fare per passenger from node 1 to node 2. That means every passenger picked up will pay $f\_{12}$.
* The capacity of arc from node 1 to node 2 is $p$. There is no associated cost.
* The arc from node 1-2 to node 2 is the imaginary flight with no cost associated nor any capacity limit.
* There should be $b\_{12}$ passengers reaching node 2. They either take the flight from node 1 to node 2 physically or **take the arc from node 1-2 to node 2 virtually without paying any fare**.

The minimum cost flow problem for this simple directed network is the following, where $x\_{a,b}$ means the number of passengers (the flow) on the arc from $a$ to $b$.

> $$\text{Minimize }\ \ z(x)= (-f\_{1-2, 1})x\_{1-2,1} + 0x\_{1,2} + 0x\_{1-2, 2}$$ subject to $$x\_{1-2,1} + x\_{1-2,2} = b\_{12}$$ $$x\_{1,2} - x\_{1-2,1} = 0$$ $$-x\_{1-2,2} - x\_{1,2} = -b\_{12}$$ $$ 0\le x\_{1-2, 1}$$ $$ 0\le x\_{1, 2}\le p$$ $$ 0\le x\_{1-2,2}$$

Why do we want to minimize $z(x)$? Because the total fare collected is $-z(x)$.

All the conditions in the end just means, $x\_{1-2,1}\le b\_{12}$ and $x\_{1-2,1}\le p$. We can solve this problem minimum cost flow easily by letting $x\_{1-2,1}=\min(b\_{12},p)$, the most passengers available not exceeding the airplane capacity.

Hopefully the above explanation is detailed enough to enable you to further understand the full minimum cost flow formulation for the problem of optimally loading a hopping airplane. You can establish a one-to-one correspondence between feasible passenger routings and feasible flows in the minimum cost flow formulation of the problem.

---
Tags: minimum-spanning-tree
---


# Question
Title: How this proof of fractional knapsack works?
I don't understand a step in my book proving the fractional knapsack problem:

> Let value of items $v\_1\ge v\_2\ge \dots\ge v\_n$, and assume $X=\langle x\_1, \dots,x\_n\rangle$ are the solution by greedy, where $0\le x\_i\le 1$ is the fraction packed into the knapsack.
>
> Assume $j$ is the first index s.t. $x\_j\<1$. Let $Y=\langle y\_1,\dots, y\_n\rangle$ be any solution not $X$.
>
> Consider $$\dfrac{v\_i}{w\_i}(x\_i-y\_i)\ge\dfrac{v\_j}{w\_j}(x\_i-y\_i),\tag{????}$$
>
> So $\displaystyle\sum\_{i=1}^n v\_i(x\_i-y\_i)=\sum\color{blue}v\_i\dfrac{w\_i}{\color{blue}w\_i}(x\_i-y\_i)\ge\color{blue}{\dfrac{v\_j}{w\_j}}\sum w\_i(x\_i-y\_i)\ge0.$

I can understand the blue part I highlighted, but can anyone help me understand the (????) part? Why it must hold?

# Answer
> 2 votes
The following condition is implicitly included in the question.

$$\dfrac{v\_1}{w\_1}, \dfrac{v\_2}{w\_2}, \cdots, \dfrac{v\_n}{w\_n} \text{ is in the descending order.}$$

Let $W$ be the total weight to be filled. The greedy algorithm for fractional knapsack problem is the following procedure.

Let $k$ loop through $1, 2, ..., n$ in that order.

1. Set $$x\_k = \dfrac{W- \sum\_{1\le i\lt k} x\_i}{w\_i}$$
2. If $x\_k\<1$, set $x\_l=0$ for all $l\>k$. Break the loop.

---

$$\dfrac{v\_i}{w\_i}(x\_i-y\_i)\ge\dfrac{v\_j}{w\_j}(x\_i-y\_i),\tag{????}$$

There are three cases for $i$.

* The case when i \< j, i.e., $\dfrac{v\_i}{w\_i}\ge\dfrac{v\_j}{w\_j}$. Since $j$ is the first index s.t. $x\_j\<1$, $x\_i=1$, i.e., $x\_i-y\_i\ge0$.
* The case when i = j. Both sides are 0.
* The case when i \> j, i.e., $\dfrac{v\_i}{w\_i}\le\dfrac{v\_j}{w\_j}$. Since $j$ is the first index s.t. $x\_j\<1$, according to the definition of the greedy algorithm, $x\_i=0$. That means $x\_i-y\_i\le0$.

---
Tags: algorithms, correctness-proof, greedy-algorithms
---


# Question
Title: How to solve the following left recursion?
A common left recursion:

```
A -> Aa | B

```

can be solve by transforming it into:

```
A  -> BA'
A' -> aA' | E

```

However, I face another similar yet different left recursion when I'm writing my compiler:

```
A -> (A|B) a

```

So, my question is, how to solve such left recursion?

# Answer
> 1 votes
Rewriting `(A|B) a` as `Aa | Ba` allows you to apply the solution you already have (with `Ba` instead of `B`).

---
Tags: formal-grammars, compilers, parsers
---


# Question
Title: Is there a way to convert a program into a Boolean formula?
Let's say I have a program `P`, in form of a binary code for x86 architecture.

I want to find a Boolean formula F (in form of CNF, or something like that), such that `F(input,output) = true iff P(input) = output` So to answer a question "what output does the program produce on given input" I will only need to run a SAT/SMT solver for `X` on formula `F(input,X) == true.` I understand that this problem is undecidable in general case, but I only care for some practical cases.

What keywords should I google to find more about this topic?

# Answer
> I understand that this problem is undecidable in general case, but I only care for some practical cases.

This is impossible if the program contains complicated loops

* infinite loops
* loops that depend on the value of the input, e.g. `for(int i = 0; i < input; ++i)`
* ...

For program where loops can be unfolded, you can construct such a formula using either Bounded Model Checking or Symbolic Execution.

You are asking about x86 machine code, which is very difficult for program analysis, as disassembly alone can be very imprecise.

For C programs, you can use CBMC to translate a program into either a SAT or SMT formula. All the details of the translation can be found on this technical report. http://shelf2.library.cmu.edu/Tech/52490804.pdf
> 2 votes

# Answer
Disclaimer: I'm not sure how useful any of this is for getting this done practically since you have a program, not a Turing Machine.

The Cook-Levin Theorem essentially states that you can translate the execution of a Turing Machine into a boolean formula that is polynomial in the length of the TM's execution such that the formula is satisfiable iff the TM accepts the input.

In your case 'accepts' means 'returns true'. One could model this in a TM by transitioning to an accepting state instead of returning true.

The linked Wiki article gives a good exposition of the proof but the gist if it is that you have variables that describe the input to the machine, the sequence of states the machine takes during an execution, the position of the head during an execution, and a bunch of conjunctions that force satisfying assignment of the variables to describe a successful execution of the TM on the input.
> 7 votes

---
Tags: logic, satisfiability, formal-methods, software-verification
---


title: Roadmap to formal verification

text:
# Question
Title: Roadmap to formal verification
I would like to learn about different approaches to formal verification of software programs that goes beyond what Wikipedia has to offer. Ideally one would not only get an overview but also recommendations which books and articles to read next.

My goal is to be able to judge what parts of formal verification I could apply to my job as a software/network engineer. So if the overview had a practical slant it would be a plus. But I also don't mind theory at all since I have a rather solid background in pure maths.

# Answer
> 5 votes
> My goal is to be able to judge what parts of formal verification I could apply to my job as a software/network engineer.

If you plan to use formal verification as black boxes, then I would suggest using some tools to have an idea how they work. Here are some open source tools:

If you want to understand their basics, you can start with the book "Principal of Program Analysis". It covers many basic topics from Type Theory to Abstract Interpretation etc.

The book doesn't discuss anything deeply. For example, it doesn't discuss any abstract domains, the key part in abstract interpretation. Recent topics such as separation logic, which Facebook Infer is based on, are not covered either.

If you want to learn advanced topics, the only way is to read the proceedings of top conferences, e.g. POPL, PLDI, CAV, VMCAI, SAS, ICSE, FSE, ASE, ISSTA, etc etc.

---

A comment by @DmitriChubarov

> As I understand this is a question of why there is so little use of formal methods in the practice software development, ... or is there?

There are companies that are earning hundreds of millions a quarter by selling static analysis tools (I work for one of them), so I believe the number of companies that use formal verification is not little at all.

---
Tags: logic, type-theory, formal-methods, automated-theorem-proving
---


# Question
Title: Why is Adleman's molecular algorithm for Hamiltonian Path linear?
In Adleman's 1994 paper (archived), he describes a method of manipulating DNA molecules in a lab that results in a solution to the Hamiltonian Path problem with high probability.

He claims that "The number of different oligonucleotides required should grow linearly with the number of edges", and this makes sense given the molecular encoding of the edges described in the paper, but he also claims that "the number of procedures required should grow linearly with the number of *vertices* in the graph". Why is this last claim true? In other words, why isn't the assembly of edge molecules counted towards this calculation? If it were, the complexity of lab procedures would be $O(|V|^2)$, as the number of edges in a graph is bound by this function.

Thank you.

# Answer
> 2 votes
You are right that in the coding of the graph one needs a possibly quadratic number of strands to represent the edges.

My guess is that Adleman likes to distinguish the two kinds of operations. First there is the coding of the input graph, which may be very complicated to avoid accidental combinations. Then there is the number of laboratory steps to actually check the presence of Hamiltonian paths.

I think this might be explained by the way he envisions how molecular computing can be used. Given a big "database" of available strands one performs a number of laboratory steps to find the solution to a problem. This is then the same operation performed in parallel to zillions of molecules. This I read from the way how he explains the number of operations performed per second.

---
Tags: complexity-theory, graphs, hamiltonian-path
---


# Question
Title: Why any problem can be reduced to SAT is NP-Complete?
I have a book statement says the title, I don't understand it. From my current understanding if a problem A can be reduced to a problem B then it only means B is at least as difficult as A.

# Answer
> 3 votes
Indeed that is **incorrect**. All problems in $\mathbf{P}$ are reducible to SAT. In fact, even trivial problems (e.g., finite languages) are reducible to SAT.

What *is* probably meant is that, if a problem in $\mathbf{NP}$ is such that SAT is reducible to it, then it is $\mathbf{NP}$-complete.

---
Tags: complexity-theory, np-complete, p-vs-np
---


# Question
Title: Which flow algorithm on a graph is used when the capacity is a rational number?
Does ford fulkerson only use whole numbers? I tried to understand this but without success

Thank you

# Answer
Since all steps of the algorithm merely involve addition, you can compute the least common multiple $m$ of the denominators of all weights involved, and creating $G'$ from $G$ by multiplying all weights by $m$.

Then all weights are integers and you can run Ford-Fulkerson. You can divide the results from it by $m$ again to get back your rationals.
> 1 votes

---
Tags: ford-fulkerson
---


# Question
Title: Divide and Conquer Algorithm to calculate $a^n$
I am attempting to create an algorithm which given the value of $a \in \mathbb{R}$ and $b \in \mathbb{N}$, calculate $a^n$.

So for example, using the Java language pattern, the algorithm will be defined as follows:

```
public double exp(float a, int n) {
    ...
}

```

But I am unable to determine what would be possible sub-problems of this problem as there is not set from which I can create subsets.

How can I achieve this using a divide and conquer method?

# Answer
I think you are looking for something along these lines.

```
public double exp(float a, int n) {
    if(n<=0) return 1; // just for safety saying <= instead of == to allow
    if(n==1) return a;
    float floor_exp = exp(a,floor(n/2))
    if(floor(n/2) < ceil(n/2)){
        return floor_exp * floor_exp * a;
    }
    else{
        return floor_exp * floor_exp;
    }
}

```

Note that floor and ceil are not functions in Java but in Python. Use these for Java. Also this will only work for n \>= 0. The result is incorrect for the other case.
> 1 votes

---
Tags: algorithms, divide-and-conquer, pseudocode
---


# Question
Title: How to generate an instance for an NP_hard proof, where each element has two inputs?
I want to prove the NP-hardness of an scheduling problem. The problem seems to be NP-hard in the ordinary sense, so I am trying with the Partition Problem, precisely the Equal Cardinality Partition (ECP). So we have:

**(ECP):** Let $X = \\{x\_1, x\_2, \dots, x\_{2n}\\}$ be a set of positive integers, does there exist a partition of $X$ into two subsets $X\_1$ and $X\_2$, such that $\sum\_{x\_i \in X\_1}x\_i = \sum\_{x\_i \in X\_2}x\_i = B$, where $B$ is a positive integer, and such that $|X\_1|=|X\_2|$?

The inputs for my scheduling problem are a set of $n$ jobs, where each job has a processing time $p\_i$ and a due date $d\_i$. So, my instance has jobs where processing times are linked to the integers from the Partition problem, i.e. $p\_i=x\_i$.

The issue that I have is this: If I assign a common due date for all jobs, i.e. $d\_i=d$, then the problem is not NP-hard. So, how I can generate the instance with non-equal due dates? For example, can I use the same integers $x\_i$ for the due dates (e.g. $d\_i=B-x\_i$)? Is it Ok if I use the job *id* ($i$) in the due dates (e.g. $d\_i=B-2i^2$)?

p.s. I realized that I cannot use the $x\_i$ of one job in the due date of another job, as then those jobs will be related to each other thai is not correct. Actually, that makes even very simple problems to be NP-hard.

# Answer
> 1 votes
As you noted yourself, the problem in general is NP-hard. You can reduce from Partition by letting due date $d = B = (\sum X)/2$, where $X$ is the input to Partition, and let there be two processes.

The proof is quite straight forward and left as an exercise.

# Answer
> 0 votes
So, let resolve the issue with this problem first.

The single machine scheduling problem is considered. There is a set of jobs $J=\\{J\_1,J\_2,...,J\_n\\}$, each job has a processing time $p\_i$ and a due date $d\_i$. Lateness of a job is $L\_i=C\_i-d\_i$, where $C\_i$ is the completion time of the job. The problem is to minimize the maximum lateness $L\_{max}$.

We know that this problem can be polynomially solved with sequencing jobs in EDD (Earliest Due Date). However, I have a reduction from the ECP to this problem. That means my reduction is not correct, because if it is true, then the problem should be NP\_hard, while it is not.

The ECP problem is defined above, and here is the instance of the scheduling problem.

There is a set $J$ of $2n$ jobs that can be partitioned into two subsets: $J\_1=\\{J\_i|p\_i=x\_i, d\_i=B\\}$ and $J\_2=\\{J\_i|p\_i=2x\_i, d\_i=3B\\}$. Does there exists a schedule with $L\_{max}\<=0$?

If the ECP has a solution, then we can use elements of $X\_1$ in $J\_1$ and elements of $X\_2$ in $J\_2$ and the problem has a solution. And if ECP does not have a solution, (e.g. $\sum X\_1=B-1$, or $\sum X\_1 = B+1$), then the scheduling problem does not have a solution as well.

So this reduction seems correct to me. However, something must be wrong as the considered scheduling problem is **not** NP-hard. What is my mistake?

---
Tags: complexity-theory, proof-techniques, np-hard, scheduling, partitions
---


# Question
Title: Flow value over edges in Max flow/Min Cut Ford Fulkerson
Is it true that if a given edge e is in the min cut of a graph that there exists a max flow of the graph that has e with its full capacity?

# Answer
> 0 votes
Yes. More precisely, for every min cut $(W,\bar{W})$, there is some max flow $f$ such that $f(x,y)=0$ if edge $(x,y)$ goes from $\bar{W}$ to $W$, and $f(x,y)$ equals the capacity of $(x,y)$ if edge $(x,y)$ goes from $W$ to $\bar{W}$. This is usually proven using the linear programming formulations of min cut and max flow, and follows by the complementary slackness property.

---
Tags: ford-fulkerson
---


# Question
Title: If a non-deterministic Turing machine runs in f(n) space, then why does it run in 2^O(f(n)) time?
Assuming that f(n) \>= n.

If possible, I'd like a proof in terms of Turing machines. I understand the reason why with machines that run on binary, because each "tape cell" is a bit with either 0 or 1, but in Turing machines a tape cell could hold any number of symbols. I'm having trouble why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape.

# Answer
> why the base is '2' and not something like 'b' where 'b' is the number of types of symbols of the Turing machine tape?

Because it does not matter in the sense that $2^{O(f(n))} = b^{O(f(n))}$ for any positive $b \> 1$.

Using the popular set-theoretic understanding of the big $O$-notation, we have $$\begin{align} 2^{O(f(n))}&=\\{2^{g(n)}\mid g(n)\in O(f(n))\\} \\ &=\\{\left(b^{\log\_b2}\right)^{g(n)}\mid g(n)\in O(f(n))\\} \\ &=\\{b^{h(n)}\mid \exists g(n),\ h(n)= (\log\_b2)g(n),\ g(n)\in O(f(n))\\} \\ &=\\{b^{h(n)}\mid h(n)\in O(f(n))\\} \\ &=b^{O(f(n))}\end{align}$$

By the way, there is no need to assume $f(n)\ge n$. For example, all above hold when $f(n) = \lceil\sqrt n\rceil$ or $f(n) = \lceil\log\_2n\rceil$.
> 3 votes

# Answer
Because an exponential function to any base can be expressed in terms of any exponential function of another base, in a way which also happens to make this possible. Namely, for any real number $a \> 0$, $a^x = 2^{\lg(a)\ x}$. Thus if you have $a^{O(f(n))}$ it is the same as $2^{\lg(a)\ O(f(n))}$. But a constant multiplying a big-O simply gets absorbed into it, since the whole point of the notation is that it's the shape, not the scale, of the function wrapped by it that counts.
> 0 votes

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


# Question
Title: Is there a fundamental CS problem in ORMs that leads to N+1?
Many of us are familiar with N+1 problem when working with database queries. The problem was known before ORMs (Object-relational mapping frameworks) came around, but it seems that ORMs exacerbated it.

The problem goes like this. If your database has a table of cars and each car has a list of wheels (stored in another table), if you first query for all cars (1) and then *for each car* you query for its wheels (N) you get orders of magnitude less efficient query because you in fact have N+1 queries, whereas you could just have one.

I'll show you one scenario in which it is difficult for a less experienced developer to spot that they have an N+1 problem while using ORM.

Let's assume we have the following tables definition in Microsoft Sql Server:

```
CREATE TABLE [dbo].[Article](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [Title] [nvarchar](max) NULL,
CONSTRAINT [PK_dbo.Article] PRIMARY KEY CLUSTERED ([Id] ASC)
)
GO

CREATE TABLE [dbo].[ArticleScore](
  [Id] [int] IDENTITY(1,1) NOT NULL,
  [ArticleId] [int] NOT NULL,
  [ActualCity] [nvarchar](10) NULL,
  [Score] [int] NOT NULL,
 CONSTRAINT [PK_dbo.ArticleScore] PRIMARY KEY CLUSTERED ([Id] ASC)
)

GO

ALTER TABLE [dbo].[ArticleScore]  WITH CHECK ADD  CONSTRAINT [FK_dbo.ArticleScore_dbo.Article_ArticleId] FOREIGN KEY([ArticleId])
REFERENCES [dbo].[Article] ([Id])
GO

```

There is nothing fancy here, the main thing is that we have two tables that have a foreign key relationship.

Now let's assume that we use EntityFramework, and somewhere in the code we have a line like this:

```
var scores = context.ArticleScores.Where(x => x.Score < 100).ToList();

```

Now the scores list gets passed around a few methods, and somewhere else it's used like this:

```
var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

```

This last line will cause a separate query to be executed *for each Article object*. When the number of objects are large, the overhead as we all know serious.

Full example that can be run and examined in SQL Profiler can be found here, which is adapted from here but I hope that the idea is clear.

The problem with this particular case can be solved with eager loading, and Entity Framework offers Include method that would load Article objects along with ArticleScore objects in the first query, thus eliminating the need to query the database at all for the second query.

Now to my question.

I would (apparently incorrectly) imagine, that there should be enough information for ORM to execute the second query in a single sql query, thus reducing N+1 problem to 1+1 problem which, in most cases won't be a problem.

ORM knows about relationship between Article table and ArticleScore table. It knows that conceptually a list of ArticleScore objects represent a slice of ArticleScore table. Thus it should be able to figure out how to get the corresponding slice of the Article table in one query, it does not look like a rocket science.

**So could you please tell me, is there some fundamental problem, when writing ORMs, that would prevent elimination of most of the N+1 problems?**

I understand that you cannot prevent someone from shooting oneself in the foot by writing specifically incorrect code, but in the examples like the one given above *many people* can easily miss the problem altogether, which is apparent to me after a few code reviews I conducted. To many people this code *looks* like it should have worked without exhibiting N+1.

# Answer
> 3 votes
## Challenge #1: Imperative code

You've shown code that is in a nicely functional form. But in many languages, in many cases, the code won't be in that nice form. Imagine if instead of

```
var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

```

the code is instead

```
var filtered = new List();
for (x in scores)
    if (x.Article.Title != "trash")
        filtered.append(x);

```

Now you're hosed: you're stuck with n+1 queries, and there's no hope for the ORM to avoid that. In many (imperative) programming languages, you'd be lucky for the code to show up in the former form; it'll more typically be in the latter form.

## Challenge #2: Static analysis of code

Let's go back to your original example:

```
var filtered = scores.Where(x => x.Article.Title != "trash").ToList();

```

How can the ORM transform this into a single SQL query? To do that, it would have to do non-trivial static analysis of the source code. This can't be handled just through a simple library.

From the ORM's perspective, it is passed a function that determines which articles should be kept; it knows nothing about what the function does -- it can just call the function. That's not enough to do the transformation you want. To do the transformation you want, one would have to inspect the code of that function and figure out what it is doing and then somehow turn that into a SQL query. That is decidedly non-trivial (and might require both compiler support and non-trivial static analysis algorithm).

Put another way, from the ORM's perspective, the above code is equivalent to

```
var filtered = scores.Where(f).ToList();

```

where the ORM knows nothing about what `f` does; all the ORM can do is invoke `f` on values of its choice. When you don't know what `f` does, there's no way to transform that into a single SQL query.

Fixing this would require a way to take code written in the underlying language and compile it to SQL. That basically means building a second compiler for the underlying programming language, and it's not easy.

In some languages, the ORM library actually obtains more than just a black-box function `f`: by using support for domain-specific languages or reflection, the ORM library might be able to obtain a parse tree for `f`. In this case, the ORM library has more to work with, and in principle the ORM library could use static analysis of the parse tree of `f` to try to compile it to a single SQL query. It will be language-dependent whether an ORM library can do this, purely as a library, without compiler support. So in some languages achieving what you want will be easier than in others.

# Answer
> 1 votes
As there are drop-in replacements for LINQ to SQL (PDF) that *guarantee* a number of queries proportional to the number of occurrences of `IQueryable` *in the type*, no, this is not a fundamental problem. Or at least, LINQ to SQL doesn't present it.

---
Tags: compilers, databases, program-optimization
---


title: Verify this cfg is finite or not

text:
# Question
Title: Verify this cfg is finite or not
S-\> aAb | aBd
A-\> ab | Bd | e
B-\> ab | d | f

I am getting a loop during CNF conversion but in question it stated that it's a finite language.

# Answer
> 1 votes
If we read the productions of $B$ we immediately see that the language generated by $B$ contains exactly three words ($\\{ab,d,f\\}$).

Hence, the production $A\to Bd$ also generates three words. Considering all the productions of $A$, we can say that $A$ contains at most 1+3+1 words.

Can you now give an upper bound to the number of words of $S$, considering its productions?

Alternatively, note that if we (well-)order the nonterminals as $S \> A \> B$ we can see that expanding a non terminal with any production causes the appearance of only "smaller" nonterminals. Hence, there is an upper bound to the number of expansions we can perform starting from $S$.

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


# Question
Title: The Law of Excluded Miracle in the language of guarded commands
The definition of weakest precondition is familiar (let me use Isabelle's syntax here):

```
definition "wp c Q s ≡ ∃t. (c,s) ⇒ t ∧ Q t"

```

the weakest precondition ensuring Q when executing a command in an initial state s is given by the formula in the RHS.

Now, Dijkstra, for instance in, "Nondeterminacy and Formal Derivation of Programs" talks about the law of the excluded middle:

```
definition "F ≡ λ t. False"

lemma "wp c F = F" unfolding wp_def F_def by simp

```

according to this article the meaning of this proposition would be:

> started in a given state, a program execution must either terminate or loop forever

However, I don't see how this proposition states this fact. Unrolling the definitions I get:

```
∃t. (c,s) ⇒ t ∧ (λ t. False) t = ∃t. (c,s) ⇒ t ∧ False = False

```

seen as a function in s, obviously this LHS matches the RHS. However, I don't see how this tells that the program terminates or loops. Could you explain what is happening here?

# Answer
> 3 votes
The answer I can provide is I was reusing the definition of weakest precondition from the IMP language, but in fact I need a stronger definition. This definition looks as follows:

```
definition "wp c Q s ≡ (∃t. (c,s) ⇒ t) ∧ (∀ t'. (c,s) ⇒ t' ⟶ Q t')"

```

It is taking care of non-determinism. When one evaluates:

```
lemma excluded_miracle: "wp c (λ t. False) = (λ s. False)"

```

One realizes that the statement is simply saying that the program either terminates, or does not terminate. Therefore, the import point now is to see whether my proposed definition is correct or can be improved in any way.

---
Tags: nondeterminism, semantics, formal-methods, hoare-logic
---


# Question
Title: Confusing notation in concatenation of error correcting codes
Define an $(m,q,d,k)$-(block) code $C$ to be a code with block size $m$, alphabet $0\ldots ,q-1$, and (non-relative) rate $k$. Meaning: $k=log\_q (|C|)$ (if we think of $C$ as a set of legal codewords) ($d$ is the distance which isn't important for this particular question). Such a code could also be thought of as a function: $$C:\[q\]^k\rightarrow\[q\]^m$$ As it takes a word of length $k$ over $\[q\]$ and encodes it into a word of length $m$.

To my understanding, given an $(m,q,d,k)$ code $C\_{out}$ and an $(m',q',d',k')$ code $C\_{in}$ such that $q'^{k'}=q$, we can define the concatenation of $C\_{out}$ with $C\_{in}$ to be a code which takes an input for $C\_{out}$, encodes it using $C\_{out}$, and then encodes each letter of the resulting word using $C\_{in}$. If this is how a concatenated code truly works, then if we denote the concatenated code $C'$ it should be thought of as a function: $$C':\[q\]^k\rightarrow \[q'\]^{m\*m'}$$ However, the common notation for such a codes (as can be seen here, for example) is: $$C\_{out}\circ C\_{in}$$ Which is exactly in the opposite order to what we would expect if we think about the concatenated code as a composition of functions.

Is there a problem with my understanding of concatenated codes, or is the notation simply confusing? And if my understanding is good, is there a reason the aforementioned notation is common?

# Answer
You get it right.

The notation $$(C\_{out}\circ C\_{in})(m)$$ means: "take m, encode it with $C\_{out}$ and then encode each symbol with $C\_{in}$." From the point of view of the channel, $C\_{in}$ is "closer", hence the inner one; see the figure in the wiki page you refer to.

This is indeed what the wiki page says.

The confusion is probably because you think of composition of functions, where the common notation $(g\circ f)(x)$ means $g(f(x))$. But here we don't have function composition but instead code **concatenation**, so the $\circ$ operation has a different meaning - it means $$ C\_{in}(c\_1), \ldots, C\_{in}(c\_n)$$ with $(c\_1, \ldots, c\_n) = C\_{out}(m)$.

Just to complete the picture, concatenation codes where developed by David Forney in 1965, where he named the inner/outer codes that way (again, having the channel as the center of this point-of-view). See his PHD work and in particular Figure 2 that illustrates this concept (same as in wikipedia).
> 1 votes

---
Tags: error-correcting-codes
---


# Question
Title: Why are there two not operators in lambda calculus?
From Wikipedia:

> $\mathrm{true} = \lambda a. \lambda b. a$
> $\mathrm{false} = \lambda a. \lambda b. b$
>
> Because true and false choose the first or second parameter they may be combined to provide logic operators. Note that there are two version of not, depending on the evaluation strategy that is chosen.
>
> $\mathrm{and} = \lambda p . \lambda q . p \\, q \\, p$
> $\mathrm{or} = \lambda p . \lambda q . p \\, p \\, q$
>
> $\mathrm{not}\_A = \lambda p . \lambda a . \lambda b . p \\, b \\, a$ (This is only a correct implementation if the evaluation strategy is applicative order.)
>
> $\mathrm{not}\_N = \lambda p . p \\, (\lambda a . \lambda b . b) \\, (\lambda a . \lambda b . a) = \lambda p . p \\, \mathrm{false} \\, \mathrm{true}$ (This is only a correct implementation if the evaluation strategy is normal order.)

I know what applicative order and normal order are (eager evaluation vs lazy evaluation of arguments to functions). But I don’t understand why the two nots don’t work in both of these evaluation strategies.

# Answer
The lambda-calculus is confluent. All the terms involved are strongly normalizing (these boolean encodings only work on booleans; they could do anything if applied to a lambda-term that doesn't reduce to $\mathrm{true}$ or $\mathrm{false}$). So the choice of reduction strategy is not relevant.

---

When something looks weird or incomprehensible on Wikipedia, check the history. Sometimes things get deformed over successive edits, and sometimes an edit is just wrong. WikiBlame can be very useful for that.

The edit that introduced the distinction between two evaluation strategy is from September 2012. It has no edit description, its content doesn't make sense (it implies that call-by-value is not an applicative-order strategy), and even the author was clearly not sure what they wrote (they left a comment with an interrogation).

The bit about normal order was added in December 2013 which was part of a series of edits mainly to improve the formatting and the wording. It doesn't look to me like the editor meant to change the meaning of the article, but they were mislead by the previous edit.

Hopefully someone will soon edit this article to rectify it, ideally with references for both of the not functions.

---

Incidentally, the choice of reduction strategy does matter if you want to extend these functions outside the booleans. For example, if you want to have $\mathrm{if}\\,b\\,M\\,N$ where $b$ is a boolean (a term that reduces to $\mathrm{true}$ or $\mathrm{false}$) and $M$ and $N$ are arbitrary terms, then this behaves differently depending on the evaluation strategy. With call-by-value, this only terminates if $M$ and $N$ terminates. With call-by-name, this terminates if whichever of $M$ or $N$ is selected terminates, and the one that isn't selected doesn't matter. This is the reason why `if` can be defined as a function in languages that use call-by-name or lazy evaluation such as Haskell, but it needs to be a special form in languages that use eager evaluation such as Lisp and ML.

Another case where the evaluation strategy matters is if you want to work on *partial* booleans, that is, terms that either reduce to one of $\mathrm{true}$ or $\mathrm{false}$ or don't terminate ($\bot$). For $\mathrm{not}$, the choice of evalation strategy doesn't matter: $\mathrm{not}\\,\bot = \bot$ anyway. For an operator like $\mathrm{or}$, the evaluation order does matter: $\mathrm{or} \\, \mathrm{true} \\, \bot$ could be either $\mathrm{true}$ or $\bot$, and likewise for $\mathrm{or} \\, \bot \\, \mathrm{true}$. With eager evaluation, they're both $\bot$, but with left-to-right normal order $\mathrm{or} \\, \mathrm{true} \\, \bot \to \mathrm{true}$ while $\mathrm{or} \\, \bot \\, \mathrm{true}$ does not terminate. It's natural to wonder if there could be a more clever implementation of $\mathrm{or}$ that always picks its terminating argument regardless of the evaluation strategy. This problem is known as Plotkin's parallel or, and it's an important result in the theory of the lambda calculus that there is no such term. There is no way for a lambda calculus function to take two arguments and evaluate them “in parallel”, reducing them and stopping as soon as one of them terminates. The function can be weakly normalizing (it terminates in some evaluation strategies) but not strongly normalizing (there are evaluation strategies where it doesn't terminate). Thus the lambda calculus is said to be *inherently sequential*. It's a very nice model of sequential computation, but if you want to model parallelism or concurrency, you need other tools.
> 7 votes

---
Tags: lambda-calculus, functional-programming, boolean-algebra
---


# Question
Title: Possible ways to have cross and full edges in a mincut maxflow
I am trying to solve the following problem about maxflow mincut it seems like my conclusion is incorrect and I am wonder where.

There is no graph just following question.

An edge e can be (x) always full, (y) sometimes full, (z) never full; it can be (x') always crossing, (y') sometimes crossing, (z') never crossing. So there are nine possible combinations: (xx') always full and always crossing, (xy') always full and sometimes crossing, and so on. Or are there? Maybe some possibilities are impossible. Let's draw a table:

Possible answers ---based on my conclusions

* **always full and always crossing.** (true based on the image above)
* **always full and sometimes crossing.** (true based on the image above and the fact that we may have several crossing edges one of them may be full, all them if all edges in the min cut is 1 and one of the crossing edges is 2)
* **always full and never crossing.** (false seems like there always must be a possibility of one of the ways to use edge with less capacity)
* **sometimes full and always crossing.** (true if we have all edges in the mincut that are 1 and crossing edge is two)
* **sometimes full and sometimes crossing.**( false since if we have many crossing edges that are 1 and one of them is 2 means that we might want to use the edge 2to flow more)
* **sometimes full and never crossing.** (true easy to see and edge that sometime full but never crossing in a graph)
* **never full and always crossing.** (true if all edges in a mincut is 1 and crossing edge is two)
* **never full and sometimes crossing.** (true if we have many 2 crossing edges)
* **never full and never crossin**g. (true if we have a graph where one edge is 2 in min cut that never crossing)

Have asked this question on /math.stackexchange.com with no luck.

wording used.

The edge is full means in in any way we pump the flow the edge is always going to be full, basically if we have and C---(1)---A------(1)----B and there is no other way to get to B other then going thru a then A is always full. Somewhat full if we can have C---(1)---A------(1)----B and if there is another way to get to b by doing C---(1)---E---(1)----B then edge is only sometime full. never full if we have C---(1)---E---(2)----B then most we can flow is 1 but b takes 2 then it never full. The crossing part if we it can be the crossing edge in the min-cut from the cut to the sink. basically it and edge that connects the cut with the rest of flow.

Thanks.

# Answer
This is the previous question which defines the terms. I hope this helps you solve the question.

Thus question provides these as true:

* always full and always crossing.
* always full and sometimes crossing.

We know from the definitions I've provided that the following are also true:

* sometimes full and never crossing
* never full and never crossing

This is all. The answer is included in the definitions.
> 0 votes

---
Tags: algorithms, discrete-mathematics, network-flow
---


# Question
Title: Can 2-philosophers problem be analogous to dining philosophers problem?
Two philosophers A and B, two forks numbered "1", "2"; A needs both "1" and "2" for eating, so does B.

Is this theoretical a dining philosopher problem? I'm questioning about the forks philosopher A needs all come from B. However, the DP problem usually gives an example of 5 philosophers, in which case, for example, philosophers A requests 2 forks from two different neighbors.

# Answer
Short answer: yes, though it could be considered a "degenerate case" (that is, a case that ends up being somewhat different from most others).

Long answer: the Dining Philosophers problem is really about having $n$ philosophers, and coming up with an algorithm that works for any $n$. A good algorithm should work for even "degenerate cases" like zero philosophers or one philosopher—by hard-coding them if necessary ("if there's only one philosopher, eat whenever you feel like"). So $n=2$ is a perfectly valid Dining Philosophers problem.
> 1 votes

---
Tags: algorithms, concurrency, synchronization, deadlocks
---


# Question
Title: Algorithm to explore every node in a graph
I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes.

The following algorithm (in psuedocode) appears to gather every node but results in duplicate nodes (I think because the recursive 'paths' crossover at some points):

```
rFindAll(Node ID, Array currentpath) //current path passed by value
{
  Array connectedNodes = getConnectedNodes(ID);

  for_each_node (Node n : connectedNodes)
  {
     if(find(currentpath, n) == NOT_FOUND) // check to ensure id not in current recursive path
     {
        // every n is a node which is within the same graph as the original node
        currentpath.add(n);
        rFindAll(n, currentpath);
     }
  }

}

```

I was just wondering whether anyone has a better suggestion to do this. I've looked on google/wikipedia and there was nothing which would obviously help.

Thanks

# Answer
The standard way to solve this is called **whatever-first search**. (Because depth-first and breadth-first and best-first and others are all special cases of it.)

The algorithm goes like this:

```
Pick a starting node
Add the starting node to a "bag" (arbitrary data structure)
While the bag isn't empty:
    Take a node out of the bag
    Mark this node as "explored"
    [Do whatever you like with this node]
    Add all this node's unexplored neighbors to the bag

```

The choice of "bag" is up to you. A stack makes depth-first search, a queue makes breadth-first search, a priqueue makes best-first search, and so on, but you can use anything you like, as long as you can put things into it and take things out of it.
> 2 votes

# Answer
Not sure whether "rFindAll" is first called in your program. If you just pass the initial node with empty "currentpath", obviously, the initial node is not added into the path and will be visited again and introduce duplication. You can update your function by moving the line currentpath.add(n); to the first position of the function: rFindAll(...) { currentpath.add(n); ... }

Another potential issue might be related to your programming language. If you are using c/c++, your code does have problem on function argument: rFindAll(Node ID, Array currentpath) Here "Array currentpath" is defined by val, so the update on this variable will not be propagated to the upper level. This may also lead to duplication.

In addition, please you'd set to store visited node instead of array, for better performance.
> -1 votes

---
Tags: algorithms, graphs
---


# Question
Title: If all edges are of equal weight, can one use BFS to obtain a minimal spanning tree?
If given that all edges in a graph $G$ are of equal weight $c$, can one use breadth-first search (BFS) in order to produce a minimal spanning tree in **linear time**?

Intuitively this sounds correct, as BFS does not visit a node twice, and it only traverses from vertex $v$ to vertex $u$ iff it hasn't visited $u$ before, such that there aren't going to be any cycles, and if $G$ is connected it will eventually visit all nodes. Since the weight of all edges is equal, it doesn't matter which edges the BFS chose.

Does my reasoning make any sense?

# Answer
If your graph is unweighted, or equivalently, all edges have the same weight, then any spanning tree is a minimum spanning tree. As you observed, you can use a BFS (or even DFS) to find such a tree in time linear in the number of edges.
> 15 votes

# Answer
If all edge costs are equal, then any spanning tree is also a minimum spanning tree. In this case, any algorithm that solves REACHABILITY solves MST as well.

```
Let S = {v0} be a set of nodes initially containing v0
Mark v0
Parent[v0] = -1
While S is not empty
  Remove a vertex v from S
  For all edges (v,u)
    If u is unmarked
      Mark it and add it to S
      Parent[u] = v

```

You can recover the tree from the `Parent` relation. If `S.Remove` and `S.Add` take constant time, then the algorithm takes $\cal O(v+e)=\cal O(v^2)$ where $v,e$ are the number of vertices and edges.
> 3 votes

# Answer
If all the edges are of equal weight we can use:

**-BFS -DFS -Dijkstra's algorithm -Prim's algorithm**

But you cannot use

**-kruskal's algorithm**
> -3 votes

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


# Question
Title: What is the time complexity of this algorithm?
In my class my teacher calculated the time complexity for this algorithm, relative to the number of sum operations executed:

She represented the cost of the algorithm by the following sum:

$\sum\limits\_{i=1}^n \sum\limits\_{j=1}^i\sum\limits\_{k=1}^j 3 = \frac{n^3}{2} + \frac{3n^2}{2} + n $

The step by step used to solve the sum bellow:

```
n = 10
count=0
for i in range (0, n):
    for j in range (0, i):
        for k in range (0, j):
            count+=3

print count

```

Then, I wrote a algorithm in python to verify the solution, but it not produce the expected output, for example, for n = 10 we expected 660 operations, but it print 360.

Change the index to start with 1 like in the bellow didn't worked either, in fact it got more distance from the expected (252).

```
n = 10
count=0
for i in range (1, n):
    for j in range (1, i):
        for k in range (1, j):
            count+=3

print count

```

# Answer
Now, you need to make index reach n, rather than go just up to it,
so instead of range(1,n), it should be range(1,m) for some m such that  n \< m .
To avoid n+1, one also needs  m ≤ n+1 .    Combining those gives  n \< m ≤ n+1 .
The simplest such m is obviously  m = n+1 ,  so your initial range should be `range(1,n+1)`.
> 1 votes

# Answer
In Python, `range(0,n)` iterates through the values `0`, `1`, `2`, .., `n-1` (but not `n`). Therefore, your summation should have been

$$\sum\_{i=0}^{n-1} \cdots$$

rather than

$$\sum\_{i=1}^{n} \cdots$$

and similarly for the other sums as well.
> 4 votes

# Answer
Your teacher was incorrect in thinking that a triple summation of i + j + k (in Python, temp += i + j + k) equals a triple of summation of 1 + 1 + 1 (in Python, temp += 1 + 1 + 1 or temp += 3). See my step-by-step work attached at bottom.

The triple summation of 1 + 1 + 1, i.e. incrementing by 3, over k from 1 to j, j from 1 to i, and i from 1 to n, equals (n**3 + 3\*n**2 + 2\*n) / 2. For n = 10, for instance, 1320/2 = 660. Simple Python 3 code confirms this math.

In Python 3, n = 10 count=0 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+=3 print(count) 660

The more intricate summation of (i + j + k) over k from 1 to j, j from 1 to i, and i from 1 to n, equals (n**4 + 4\*n**3 + 5\*n\**2 + 2\*n) / 4, which is exactly (n+1)/2 times the previous sum. Can you deduce why? Because, on average, the quantities i, j, and k will be halfway between 1 and n. For n = 10, for instance, 14520/4 = 3630. Again, Python 3 code that increments count += i + j + k confirms this result at n = 10.

n = 10 count=0 for i in range (1, n+1): for j in range (1, i+1): for k in range (1, j+1): count+= i + j + k print(count) 3630
> 0 votes

# Answer
Your implementation does not match the algorithm written in the pseudo-code. In the pseudo-code: `for i ← 1 to n do` means i could take n values from 1 to n. for simple, let's consider the last iteration, namely i=n. Then consider the second loop: `for j ← 1 to j do` could be reduced to: `for j ← 1 to n do` That's to say, j could also take n values from 1 to n. But for your implementation in python, `for i in range (0, n)` i could take n values from 0 to n-1. Let's also consider the last iteration, namely i=n-1. Unfortunately, for the second loop: `for j in range (0, n-1)` here j can only take n-1 values from 0 to n-2. Obviously mismatched to the original algorithm. Two ways to solve your problem:

Index start from 1 and use LCRC rule:
`for i in range (1, n+1):
 for j in range (1, i+1):
 for k in range (1, j+1):
 count+=3` or start from index 0, but use LCRC rule for all inner loops:
`for i in range (0, n):
 for j in range (0, i+1):
 for k in range (0, j+1):
 count+=3` The first one is preferred as it exactly match the algorithm. But the second one could let you clearly understand the difference between the outer loop and inner loops.
> 0 votes

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


# Question
Title: Is it possible to solve this problem in less than n^2 time without using additional space?
Here's the problem:

Given an array `array` containing integers, maximize `array[i] + array [j] + |i - j|` where i and j both range from 0 to length -1. i and j potentially could be the same.

Upon reasoning, I concluded that it is not possible. Am I wrong?

# Answer
Let’s use $a\_i$ for the array. You are interested in $$ \begin{align\*} \max\_{i,j} a\_i + a\_j + |i-j| &= \max\_{i,j} a\_i + a\_j + \max(i-j,j-i) \\ &= \max\_{i,j} \max((a\_i+i)+(a\_j-j), (a\_j+j)+(a\_i-i)) \\ &= \max \left\[ \max\_{i,j} (a\_i+i) + (a\_j-j), \max\_{i,j} (a\_j+j) + (a\_i-i) \right\] \\ &\stackrel{(\*)}= \max\_{i,j} (a\_i+i) + (a\_j-j) \\ &= \max\_i (a\_i + i) + \max\_j (a\_j - j). \end{align\*} $$ The tricky step is $(\*)$. The final expression can be computed in linear time and constant space.
> 7 votes

# Answer
Something was bothering me about Yuval Filmus's answer so I wrote it down in detail to convince myself that it was right. Perhaps someone else might also find it useful so I'm posting it as an answer.

$$ \begin{eqnarray} \max\_{i,j} a\_i + a\_j + |i-j| &=& \max\_{i,j} (a\_i + a\_j + \max(i-j,j-i)) \nonumber \\ &=& \max\_i( \max\_{j \leq i}(a\_i + a\_j + i - j), \max\_{j \gt i}(a\_i + a\_j + j - i)) \nonumber \\ &=& \max\_i( \max\_{j \leq i}(a\_i + a\_j + i - j), \max\_{j \lt i}(a\_j + a\_i + i - j)) \nonumber \\ &=& \max\_i( \max\_{j \leq i}(a\_i + a\_j + i - j), \max\_{j \lt i}(a\_i + a\_j + i - j)) \nonumber \\ &=& \max\_i \max\_{j \leq i}(a\_i + a\_j + i - j) \nonumber \\ &=& \max\_i( a\_i + i + \max\_{j \leq i}(a\_j - j)) \nonumber \end{eqnarray} $$

Here you need an extra argument to separate the variables : If $i\_{max}$ is the index where $\max\_i(a\_i + i)$ is reached, and $j\_{max}$ is where the $\max\_j(a\_j - j)$ is reached, then it follows that $i\_{max} \geq j\_{max}$.

You can then write :

$$ \begin{eqnarray} \max\_i( a\_i + i + \max\_{j \leq i}(a\_j - j)) &=& \max\_i( a\_i + i + \max\_{j}(a\_j - j)) \nonumber \\ &=&\max\_i( a\_i + i) + \max\_{j}(a\_j - j) \end{eqnarray} $$
> 2 votes

---
Tags: algorithms, optimization, arrays
---


# Question
Title: Find four sets where each element from those four appears in at least two of those four sets
I have a list of sorted arrays ("sets") of integers $A\_1..A\_n$ where each element is unique w.r.t. the other elements in the same array:

* $A\_i = \\{x\_{i,1}..x\_{i,c\_i}\\}$
* $x\_{i,p} \< x\_{i,p+1}$

$A\_i$ has length $c\_i$ and the average of $c\_i \ll n$. For example in one of the runs, the average $c\_i$ ranged from $10$ to $15$ and $n$ from $2000$ to $15000$.

I want to find all combinations of four different arrays $M=\\{A\_r,A\_s,A\_t,A\_u\\}$, where each element that appears in any of the $A$'s, appears in at least one of the other $A$'s:

$\forall A\_i \in M: \forall x \in A\_i: \exists A\_{j \ne i} \in M: x \in A\_j$

> Assuming that only a small number of the combinations $\epsilon \ll n (\ll O(n^4))$ satisifies these requirements, is there a way to do this more efficiently than the obvious $O(n^4f(c))$? Here $f(c)$ is some reasonably small function in the average $c\_i$.

It's probably viable for me if it can be done in $O(n^2c)$ but not if it's $O(n^3c)$.

If we consider the problem described so far to be the case with $|M|=4$, is there also an efficient algorithm for the case with $|M|=3$?

For the case with $|M|=2$, I can simply add each $A\_i$ to a hash set after checking if another $A\_j$ with the same values is already in the hash set, with expected time about $O(nc)$.

I'm also very interested in the cases where there's up to $y$ cases of $x\_i$ that appear in only one of the sets of $M$, where $y = y'-|M|$ and $y'$ is $4$ or $5$

---

So where would I use such an algorithm? I'm writing a SAT solver. The idea of the solver is that it looks for an integer solution to an ILP problem (without inequality constraints). I have a rectangular matrix with very small integers (0,1,2 mod 3, without the n=2m constraint and the promise) and bring it into Smith normal form. To reduce the search search space, I look for a small set of rows with a small number of nonzero entries, but such rows could be hidden as linear combinations of the rows in the matrix. However since the matrix is in Smith normal form, a row with 4 nonzero entries can only be a linear combination of up to 4 rows, as any 5 rows have 5 pivots. Each row of the normal-form matrix becomes an $A\_i$ in the described problem, with the pivot column removed.

The current implementation on github (first link above) only finds rows with 2 nonzero entries and it takes $O(n^2)$ in the worst case.

# Answer
Assume set A has an element x. Then you need to add another set B which also has the same element x. Then if there is an item y element of A or B but not both, you need to add a set C contains y. And finally add a set D containing all elements that are elements of exactly one of A, B or C, plus possibly elements common to two of them.

I’d first count for each of the elements how many sets contain it; if x is contained only by one set A, then remove A from the problem. Sort the elements of each set by how many sets contain them. Sort the sets in lexicographic order according to the number of sets containing each element, except sets with fewer elements come later. (So if A contains x and y, both elements of two sets only, and B contains u and v both elements of two sets, and w element of 200 sets, then B comes before A, and both close to the start of the list).

You said that your sets tend to have 10 to 15 elements, then each element will tend to belong to not more than 10 or 15 sets. If you have much more than n different items in total, that number is actually smaller.

Now take the first set A in the list. Take its element x belonging to the smallest number of different sets, and pick each of these sets as the second set B in turn. Take the element y belonging to exactly one of A and B belonging to the smallest number of sets, and pick each of those sets as the third set C. Take the element z belonging to exactly one of A, B and C belonging to the smallest number of sets, and check all those sets in turn.

In cases where no element is required to be added (all elements belong to two of A, B and C for example), try all possible sets as the next set.

When all possibilities for B, C and D have been examined, remove A, adjusting all the counts. Assuming items don’t belong to more than k sets on average, this should take no more than n k^3 steps.

PS I assumed the number of different items is about the same as n. As long as the number of different items is at least n^(2/3) this will run in O(n^2). Well, roughly.
> 1 votes

---
Tags: algorithms, data-structures, arrays, sets
---


# Question
Title: Technique for converting recursive DP to iterative DP
I'm new to Dynamic Programming and before this, I used to solve most of the problems using recursion(if needed).

But, I'm unable to convert my `recursive code` to `DP code`.

For eg, below is the **pseudo-code** for `Finding longest common-subsequence in 2 strings` :

```
int LCS(i,j):
    if A[i]=='\0' or B[j]=='\0':
        return 0;
    else if(A[i]==B[j]):
        return 1 + LCS(i+1,j+1)
    else:
        return max(LCS(i+1,j),LCS(i,j+1))

```

Now, I understand the above code and below is its **DP equivalent**:

```
//Some initializations are needed which have been skipped
if(A[i]=B[j]):
    LCS[i,j] = 1 + LCS[i-1,j-1]
else:
    LCS[i,j] = max(LCS[i+1,j],LCS[i,j+1])

```

I'm not able to figure out how did they construct its **DP** equivalent with the help of the recursion technique?

In the recursion technique, `1 + LCS(i+1,j+1)` is written whereas, in DP `1 + LCS[i-1,j-1]` has been used.

I am wondering how did they use `minus` in place of `plus` and how will I figure out myself(for other programs involving DP) that such adjustments need to be made in the code?

# Answer
This DP code is the bottom up solution of the problem. The key is that you start with smaller subproblems and then use these solutions to solve a bigger subproblem.

The data structure we use to store these results is actually holding results to different subproblems of the problem. For eg. let say we want to find a LCS for strings `abcbdab` and `bacdba` and let the data structure be a 2D array called `cache[][]`.

The smallest problem is when first string has only `a` and second string has only `b`. Here nothing is common. So the LCS has a length of 0 and hence $cache\[1\]\[1\] = 0$ (1-based indexing). A slightly bigger problem than this would be when first string is `a` and second string is `ba`. Here the characters match and hence $cache\[1\]\[2\] = 1$.

So in this way you can see we can keep growing the problem incrementally and use the previous solutions to have a solution of a bigger size problem.

The reason why we are using minus is because we are just using solutions of subproblems of smaller size represented by smaller indexes in our solution array.

You should not relate recursive and bottom up solutions. There is no direct relation. They are totally different way to solve the same problem. Hence you should keep in mind that you have to solve smaller subproblems and store their results.

I hope this clears the doubt.
> 2 votes

# Answer
You can easily make it *fast* using memoization! The problem is that you do many repetitive recursive calls. Try to first make a global dictionary/map/hashmap that maps `dp[i][j] = lcs(i,j)` and before every recursive call, you check if you already computed it or not.

Once that's done, you can make it DP if you want to, you're not far away.

Then you just "*manually* run the recursive calls" bottom-up, something like:

```
for i, j in enumeration(n):
    dp[i][j] = 1 + dp[i-1,j-1] if i == j else max(dp[i+1,j], dp[i,j+1])
return dp[n][n]

```

That's at least the gist of it!
> 1 votes

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


# Question
Title: Replace 1's with -1's and vice versa in a matix
Assume that we have an anti-symmetric matrix that consists of 1's and -1's and 0's. All the elements of the main diagonal are 0 and each row and each column has exactly one 1, and one -1. Design an algorithm that replaces all 1's with -1's and vice versa only by swapping some rows and some columns.

# Answer
Your matrix encodes a directed graph in which the in-degree and out-degree of each vertex is 1. In other words, your graph is a collection of directed cycles.

If you swap rows $i$ and $j$ and columns $i$ and $j$, then you have swapped vertices $i$ and $j$ in the graph. This has the effect of switching the direction of the edge between $i$ and $j$, but also affects other edges touching $i$ and $j$.

In order to finish the solution, it suffices to consider a single directed cycle involving all vertices, say $1 \to 2 \to \cdots \to n \to 1$. We would like to swap vertices so that the the cycle becomes $1 \gets 2 \gets \cdots \gets n \gets 1$.

We now consider two cases:

1. $n = 2k+1$ is odd. In this case, we swap $(1,n), (2,n-1), \ldots, (k,k+2)$ to get $$ n \to n-1 \to \cdots \to k+2 \to k+1 \to k \to \cdots \to 1 \to n. $$
2. $n = 2k$ is even. In this case, we swap $(1,n), (2,n-1), \ldots,(k,k+1)$ to get $$ n \to n-1 \to \cdots \to k+1 \to k \to \cdots \to 1 \to n. $$
> 0 votes

---
Tags: algorithms, matrix
---


# Question
Title: Given n drinks, find optimum way to spend money if for each drink the price and the expiration date is given
Let's say we are given $n$ types of drinks, integer $m$ representing the budget we have and integer $d$ representing the cost of delivery when we order some drinks. For each of the $n$ drinks we are given $P\_i \text{ the price of i-th drink and } E\_i - \text{expire date}$. For example $(3, 2)$ is representing drink with price $3$ for one bottle and the second number means that this drink can be used at most $2$ days after we buy it. One cannot drink drinks that have expired date of usage and one must drink exactly once per day.

We can order as many drinks as we want from each type, but each time we order we are paying $d$ dollars for delivery. Notice that the delivery doesn't matter in the day, so we can buy drink with exprite date $2$ and used it either today, tomorrow, or the day after tomorrow.

We want to maximize the number of drinks we will buy and drink.

I think that this problem can be solved with greedy strategy, but I'm not able to find anything that can lead to correct result and good time complexity.

Here are some things that I got so far:

We don't want to buy things that will be expired, so from each drink with price $P\_i$ we will spend at most $P\_i \cdot(E\_i + 1)$

Because we may have big budget, it is good to find one way of buying drinks and use it couple times, until we don't run out of money from the budget.

We will first buy the cheaper drinks and for the more expensive ones we should decide should we make a new order, or buy some drinks from the next type.

I didn't got anything that lead to correct strategy, so please share some of your ideas.

# Answer
It’s not very difficult really, assuming we only care about the cost and don’t have any preferences for drinks.

If we want to make a single order that lasts for n days as cheap as possible, we order the cheapest drink with expiry k, for each 0 \<= k \< n. That supply costs the cost of the drinks plus d. We can calculate this cost for 1 \<= n \<= E+1, where E is the longest expiry of any drink.

If we want drinks for N days, we make 1 or more orders to minimise the total cost. We may assume the orders are ordered by size in descending order (and if we find the best sequence of orders with this restriction, we can rearrange it any way we like). Finding the best orders is now a simple dynamic programming problem.

If you are looking for something complicated, it’s not needed.
> 1 votes

---
Tags: greedy-algorithms
---


# Question
Title: Algorithm for generate all solutions to a linear Diophantine equation
Consider the linear Diophantine equation of the form: $$\sum\_{i=1}^{k}a\_ix\_i=n.$$ My goal is to list all the non-negative solutions to this equation. I wrote the following recursive algorithm, but I am not sure if it is the most efficient way to build the solutions. Here is the current version:

```
def recsolve(n, L, cursol, result = []):
if len(L) == 1:
    ak = L[0]
    if n%ak == 0:
        result.append(cursol + [n//ak])
    return

else:
    a1 = L[0]
    end = math.floor(n/a1)
    for k in range(0, end + 1):
        recsolve(n-k*a1,L[1:], cursol + [k],result)

result = []
n = 5
L = [1,2,3]
recsolve(n, L, [], result)
print(result, "; Number of solutions:", len(result))

```

I would be grateful if someone could suggest more efficient approaches to finding all solutions to a linear Diophantine equation.

# Answer
Your current recursive solution is pretty solid. It is, I believe, about the most efficient recursive approaches we can have for the general situation.

Somehow I prefer the code in you first solution since it is easier to read. All we need to make it correct is to change `return [None]` to `return []` and `if None not in res:` to `if res:`

Implementation-wise, we could change it to use an iterative method which should run faster. Also, we could sort $a\_i$ in descending order which may improve the listing speed. For example, solutions for $100x\_1+100x\_2+x\_3=1000$ will be found much faster than $x\_1+100x\_2+100x\_3=1000$.

In some special cases, we might be able to speed up the performance. For example, for $15x\_1+10x\_2+6x\_3=100000$, $x\_1$ must be a multiple of 2, $x\_2$ must be a multiple of 3, $x\_3$ must be a multiple of 5. These restriction could help us to improve the speed if they are given or they can be found by factorization easily.
> 1 votes

# Answer
You can use dynamic programming. For each $j \leq k$ and $m \leq n$, find the number of solutions to $$ \sum\_{i=1}^j a\_i x\_i = m. $$ Details left to you.
> 0 votes

---
Tags: recursion, number-theory
---


title: Real RAM computational mode

text:
# Question
Title: Real RAM computational mode
Given a real value $M\>0$, I want to compute the greatest value of $\epsilon$ strictly smaller than $M$. Given the assumption that the computational model is Real-RAM, how to find a real number sufficiently close to $M$?

# Answer
In Real RAM precision is infinite, this comes straight from definition: it uses exact real numbers. As you have noticed this is purely theoretical model. It is also worth notting that real-RAM model gives enormous computational boost from standard RAM model where each cell uses only fixed length, called machine word.

For hardware (practical one), using something like IEEE754, these are not real numbers, but fixed-precision representation, with sign, significand and exponent. Common float has about seven digits of precision. There are types using 24, 32, 64, 80, 128... bits.

If you want to model something with practical indication in mind, do not use real-RAM as it is too powerful.
> 1 votes

---
Tags: algorithms, computational-geometry, mathematical-analysis, numerical-analysis, real-numbers
---