# Question
Title: Can CYK Parsing algorithm generate the parsing tree in O(n^3)?
I found this question What is the usage of CYK algorithm in the real world considering we have algorithms with a much better Time complexity? saying CYK Parsing algorithm can compute any Context Free Grammar in $O(n^3)$.

But this does not make sense because I cannot see how NonDeterministic Context Free grammar can be parsed in $O(n^3)$. Then, while reading Hopcroft and Ullman (2006) pages 304 I found:

> In $O(n^3)$ time the algorithm constructs a table that tells whether w is in L $\in$ Note that when computing this running time the grammar itself is considered fixed and its size contributes only a constant factor to the running time which is measured in terms of the length of the string w whose membership in L is being tested.

So, the correct affirmation is: There is no way a NonDeterministic Context Free Grammar parsing tree can be built in $O(n^3)$ time, only its word membership can be determined in $O(n^3)$ time by the CYK algorithm. NonDeterministic Context-Free Grammars Parsing Trees can only be built in Exponential Time (worst case)?

Related:

1. Chomsky Hierarchy and P vs NP
2. What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?

# Answer
It depends what you mean by build a parse tree.

You can build a parse forest in $O(n^3)$ time and space. The forest represents all parse trees, even an infinite number of parse trees, because it is a graph, not a tree. From a parse forest, it is possible to produce a single parse tree in time linear to the size of the forest, and it is possible to iterate through all possible parses.

So if you either consider that "build a parse tree" means "find one of the possible parses" or if you consider that it means "build a datastructure which represents all possible parses", then you can certainly do that with a CYK grammar in $O(n^3)$.

If, on the other hand, you intend "build a parse tree" to mean "build all parse trees for a sentence", then it is not limited to exponential time; it is easy to write a grammar with an infinite number of possible parses for certain sentences.
> 3 votes

---
Tags: algorithms, formal-languages, automata, context-free, compilers
---


# Question
Title: How can I prove the languages of incompressible words is undecidable?
I have hard time understanding the proof by contradiction for the claim "$L=\\{x : K(x) \ge |x| \\}$" is undecidable ".

The proof is as follows :

> M' = " On input $n$
>
> 1. Enumerate over all $n$-bit strings $x$ in lexicographical order
> 2. Simulate M on each $x$, where $M$ is the Turing machine that decides $L$.
> 3. Output first $x$ which $M$ accepts. "
>
> Since TM $M'$ produced incompressible using only $O(\log n)$ to specify $n$, we can compress incompressible strings which is a contradiction.

I understood the $M'$ construction. **However, I do not understand where exactly is the contradiction happening?** According to me, $M'$ outputs $x$ which is in-compressible(ensured by TM $M$) but how does it is also compressible at same time?

# Answer
Consider the word $w\_n$ that is the output of $M'$ given input $n$.

Note that description of $w\_n$ is the description of $M'$, whose length is some constant $c$, plus the description of $n$, whose length is $O(\log n)$ since we can express $n$ in the binary representation. So $K(w\_n)\le c + O(\log n)$. If $n$ is large enough, we get $$K(w\_n)\lt n = |w\_n|.$$

That is a contradiction since, as you have noted, $w\_n$ should be incompressible.
> 2 votes

---
Tags: turing-machines, undecidability, kolmogorov-complexity
---


# Question
Title: Encoding a "not-k-out-of-n" constraint for SAT solvers
I'm finding myself needing to encode a "not-k-out-of-n" constraint in a SAT solver.

The "at-most-k-out-of-n" constraint for SAT solvers is something I can find research about -- this paper by Frisch and Giannaros, for example.

Given an "at-most-k-out-of-n" tool, I can get an "at-least-k-out-of-n" tool by inverting all the terms. With both tools, I can get a "k-out-of-n" tool by having both the "at-most-k" and "at-least-k" constraints.

But I don't see how I can encode a "not-k-out-of-n" constraint. If I use "at-most-(k-1)" and "at-least-(k+1)", then obviously I'm going to get no solutions.

Is there a simple transformation here that I'm missing?

# Answer
Assuming you work in CNF, construct "at least $k+1$-out-of-$n$" and add "or $p$" to each disjunction. Do the same for "at most $k-1$-out-of-$n$" and add "or $q$" to each disjunction.

Then add one extra term to your main conjunction, $\neg p \vee \neg q$.
> 3 votes

---
Tags: satisfiability, sat-solvers, applied-theory
---


# Question
Title: Nodes in a binary search tree that span a range
I have a binary search tree of height $h$ with an integer in each leaf. I also have a range $\[\ell,u\]$. I want to find a set of nodes that span the range $\[\ell,u\]$, i.e., a set $S$ of nodes such that the leaves under $S$ form all (and only) those leaves containing integers in the range $\[\ell,u\]$. How large does $S$ need to be, in the worst case, as a function of the height $h$? How do I find such a set explicitly?

# Answer
I'm assuming you have parent pointers, you can probably avoid them by maintaining a couple stacks though.

Find the extremal two nodes $\ell \leq p \leq q \leq u$ and their common ancestor $a$ in $O(h)$ time. If nodes $p$ and $q$ are the same, return $S = \\{p\\}$.

While $p$ is the left child of its parent and its parent is not the common ancestor, let $p := \text{parent}(p)$. Similarly for $q$ but with being the right child as criterion.

Now if $p$ and $q$ are both the direct children of $a$ let $S = \\{a\\}$ and you are done. Otherwise initialize $S = \\{p, q\\}$ and repeat:

1. $p := \text{parent}(p)$
2. If $p = a$ break.
3. Add the right child of $p$ to $S$.

And to finish up, do the same for $q$ but adding the left children instead. Note that the first iteration of the above loop can add $p$ or $q$ to the set while it is already in it. If you use an array instead of a proper set you want to make a special case for the first iteration.

In the worst case this adds $2h + O(1)$ elements to $S$. This can be necessary too, consider a full binary tree where the range includes all but the smallest and biggest node.
> 2 votes

---
Tags: binary-trees, search-trees
---


# Question
Title: Checking whether there is k circles with common area
I have N circles with different radius and position in the plane. The problem is finding k circles which have a common area.Obviously this can be solved using Brute-Force in $O(N^k)$. Is there a more efficient way to do such query?

# Answer
> 1 votes
This problem and related problems have been studied in the paper "Bajaj, C., & Li, M. (1983). *On the duality of intersections and closest points*. Cornell University."

They call a common area for $k$ circles a '$k$-intersection'. The paper gives an $O(n^2\log n)$ algorithm for the problem of finding a $k$-intersection when the circles have different radius. (Theorem 13) It is not clear to me from the paper how that bound is achieved, but I do see how to achieve $O(n^3)$ time with their approach.

## Algorithm

The main idea is to construct the following (directed) planar intersection graph $G=(V,E,F)$: The vertices $V$ of this graph are all intersection points of the circles and the edges $E$ are the circle arcs connecting those intersection points. The direction of the edges is counterclockwise on the circle, such that the interior of the circle it is part of lies to the left of the edge. We also keep track of the *faces* $F$ of this planar graph, which are the regions enclosed by the edges $E$.

Note that each region of circle intersections corresponds to a face of this planar graph and that the number of circles that contain the region is equal to the number of *clockwise* boundary edges of the corresponding face. If we have computed $G$, then we can maintain a counter for each face in $F$ and traverse the graph to visit all edges and increase the counter of face left of each edge. Then, after we have traversed the edges, each face has the number of circles that contain it stored in the counter.

## Complexity

Since there can be at most $O(n^2)$ intersections of $n$ circles, $|V|=O(n^2)$. Since $G$ is a planar graph, $|E|\leq 3|V|-6 =O(n^2)$. So, traversing the graph takes $O(|V|+|E|)=O(n^2)$ time.

As for constructing the graph, the authors claim that this graph can be constructed in $O(n^2\log n)$ time by sorting the edges. I did not see any further explanation of this in the paper and do immediately see how to achieve this. (in particular, it would be helpful to know on *what* they sort.)

I do see how to do this in $O(n^3)$: The vertices and edges of the graph can be constructed in $O(n^2)$ time by iteratively adding new circles. When a new circle is added, we add the new intersection points and subdivide some of the existing edges.

Adding the faces is more complicated and I currently only see the naive method of for each edge $e$, traversing all edges that are on the boundary of the two faces adjacent to edge $e$. This takes $O(n)$ per edge, so $O(n^3)$ in total. It does seem like we can do better here, but I currently don't see how.

---

$O(n^2\log n)$ is good, but can we do better? For the case where the circles all have the same radius, this is possible: Chazelle and Lee have found an $O(n^2)$ time algorithm based on an implicit traversal through the intersection graph ("Chazelle, B. M., & Lee, D. T. (1986). On a circle placement problem. Computing, 36(1-2), 1-16."). Whether $O(n^2)$ is possible for the case with circles of different radius they leave as an open problem, which has remained open for now, as far as I'm aware.

# Answer
> 0 votes
I don't believe this problem is NP-hard, due to a simple observation: the maximum number of regions formed by $N$ circles is A014206 which is $O(N^2)$. You can just keep track of and iterate over each region with smart computational geometry formed by circle arcs, choose an arbitrary point in each region and check if $k$ circles contain that point.

This is not easy to program (computational geometry is complex), but should be on the order of $O(N^3)$ or $O(N^4)$. But perhaps someone comes up with a better algorithm.

---
Tags: computational-geometry
---


# Question
Title: Iteration vs Recursion question in Lisp method
I am curious if the following method would be called iterative or recursive:

`(define (deep-reverse items)
 (define (iter things answer)
 (cond ((null? things) answer)
 ((pair? (car things))
 (iter (cdr things) (cons (deep-reverse (car things)) answer)))
 (else (iter (cdr things) (cons (car things) answer)))))
 (iter items ()))`

I am confused because `iter` only calls itself with the state variables `things` and `answer` as arguments, and modifies those each run, so that I think it is iterative. It is defined in a method `deep-reverse` that does recursively call itself... This is confusing to me because there are elements both of iteration and recursion in this method, so that I don't know in the end how I would classify it... Is `deep-reverse` recursive? Is `iter` iterative?

Thank you.

# Answer
> Is `deep-reverse` recursive?

* It is mutually recursive with `iter`. Its call to `iter` is not in itself (properly) recursive.

> Is `iter` iterative?

* Its calls to itself are iterative.
* Its call to `deep-reverse` is (properly) recursive.

It is not the functions as a whole,but each call within them that you can classify as iterative or recursive.

As you noticed, the `iter` function makes no use of its `deep-reverse` context. Better separate the functions into distinct `define`s:

```
(define (deep-reverse items)
  (iter items ()))

(define (iter things answer)
  (cond ((null? things) answer)
        ((pair? (car things))
          (iter (cdr things) (cons (deep-reverse (car things)) answer)))
        (else (iter (cdr things) (cons (car things) answer))))

```

These are mutually recursive:

* `deep-reverse` calls `iter` and
* `iter` calls `deep-reverse`.

And `iter` calls itself twice.

The `deep-reverse` call to `iter` and both the `iter` calls of itself are tail calls: they are the last thing done in the enclosing computation. They are in your terms iterative, though the first does not involve repetition. They could each be implemented as an appropriately set up control-jump/goto. Any Scheme compiler will short-circuit the calls in this way.

The call of `deep-reverse` from `iter` is different. The call is inside a `cons`. It can't be dug out. It is properly recursive, so needs some kind of stack to carry its nest of invocations.

---

I tested the above by translating the functions into Clojure, a Lisp dialect with explicit tail recursion using the reserved word `recur` instead of the function name. Here is the code:

```
(defn pair? [x]
  (and (coll? x) (next x)))

(defn deep-reverse [items]
  (iter items ()))

(defn iter [things answer]
  (cond
    (empty? things) answer
    (pair? (first things))
      (recur (rest things) (cons (deep-reverse (first things)) answer))
    :else (recur (rest things) (cons (first things) answer))))

```
> 0 votes

# Answer
Since `deep-reverse` and `iter` call each other, they are *(mutually) recursive*. Their combination is *not **tail** recursive* however, so `deep-reverse` is **not** iterative in the scheme parlance (IOW, does **not** admit tail call optimization).

PS. A proverbial *sufficiently smart compiler* (and, in fact, many real ones) *can* compile this function into an iteration (i.e., not using the function call stack).
> 0 votes

---
Tags: recursion, iteration, lisp
---


# Question
Title: How does this example violate Liskov substitution principle, which then causes violation of the open-closed principle?
From Agile Principles, Patterns, and Practices in C# by Robert Martin,

> Listing 10-1. A violation of LSP causing a violation of OCP
>
> ```
> struct    Point   {double x,  y;}
> public    enum    ShapeType   {square,    circle};
> public    class   Shape
> {
>       private ShapeType   type;
>       public  Shape(ShapeType t){type =   t;}
>       public  static  void    DrawShape(Shape s)
>       {
>               if(s.type   ==  ShapeType.square)
>                       (s  as  Square).Draw();
>               else    if(s.type   ==  ShapeType.circle)
>                       (s  as  Circle).Draw();
>       }
> }
> public    class   Circle  :   Shape
> {
>       private Point   center;
>       private double  radius;
>       public  Circle()    :   base(ShapeType.circle)  {}
>       public  void    Draw()  {/* draws   the circle  */}
> }
> public    class   Square  :   Shape
> {
>       private Point   topLeft;
>       private double  side;
>       public  Square()    :   base(ShapeType.square)  {}
>       public  void    Draw()  {/* draws   the square  */}
> }
>
> ```
>
> `DrawShape()` violates OCP. It must know about every possible derivative of the Shape class, and it must be changed whenever new derivatives of Shape are created.
>
> The fact that `Square` and `Circle` cannot be substituted for `Shape` is a violation of LSP. This violation forced the violation of OCP by DrawShape . Thus, a violation of LSP is a latent violation of OCP.

How does it violate Liskov substitution principle (LSP)? (In particular, why can `Square` and `Circle` not be substituted for `Shape`?)

How does violation of LSP cause violation of the open-closed principle (OCP)? (I can see it directly violates OCP, but I can't understand how violation of LSP causes violation of OCP.)

Thanks.

# Answer
> 1 votes
The listing does not appear to be a good illustration of LSP violation, since no clear reason is given why the draw method couldn't be a virtual method of Shape. If it was, then there would be no need to do any type query in drawShape: calling draw would work for all subclasses of Shape.

The Liskov Substitution Principle is typically described in terms of *contracts*. For example: the contract of the square root function **requires** that the input is non-negative and **ensures** that the square of the output is equal to the input.

Hence, an overridden method in a subclass is substitutable for the corresponding method in the superclass if it:

* **requires** no more of its input than the superclass contract
* **ensures** no less of its output

A subclass is LSP-conforming if all its methods are LSP conforming.

Hence, a better illustration of LSP violation might be a rotate method, in which all shapes except Square can be rotated by any angle, but Square is only rotatable by some multiple of 90% (such a requirement would actually demonstrate that the Square should not be a subclass of Shape).

In general, LSP violation causes OCP violation because there is no meaningful action that a 'closed' function can take without needing knowledge of specific subclasses in the type hierarchy.

The standard example of this is to have a Circle class be a subclass of an Ellipse class that has a `resize(xaxis,yaxis)` method. Unless the semantics of resize are so diluted as to be largely useless ('maybe resize yourself or throw an exception') then subclasses can end up in a state that is inconsistent with anything meaningful/useful to the 'closed' function that is calling its methods.

A good discussion of the LSP (including the 'Circle-Ellipse' issue) can be found here

---
Tags: programming-languages, type-theory, software-engineering, design-patterns
---


# Question
Title: Can data be compressed through this hash function technique?
I'd like to know if this data compression scheme would work or not, and why:

Suppose we have a file. If we treat the bits that make up the file as the binary representation of a number n, we have n (of course, if the first bit is zero we flip every bit so that n is unique). Now we have the number n, and a boolean that informs us whether to flip all the bits of the binary representation of n or not.

My idea was approximating n from below (e.g. finding a relative big number raised to a relative big power, such as 17^6038) and then start to compute arbitrary hashes for all numbers from this approximated n to the real n, counting the number of collisions. When we finally get to n, we have the "collision state" of the hashes and then we output the compressed file, which basically contains information about how to get to the approximation of n (e.g. 17^6038) and the "collision state" for n (note that this "collision state" must also occupy very few bits, so I'm not sure this would be possible).

The decompression procedure would do a very similar process; it will approximate n (e.g. compute ~n as 17^6038) and then start to hash (i.e. apply a function and check the result) every single number (we could also check every 5 numbers or another divisor of n - ~n) until the "collision state" is the same as the specified in the compressed file. Once we match everything, we have n. Then, it would just be a matter of flipping every bit or not (as specified in the compressed file) and outputting to a file.

Could this work? The only problem I can think of is (besides the time required for processing) the number of collisions being extremely huge.

# Answer
> 2 votes
No. Any compression method that does not model its data in some way to prefer some inputs over others is doomed to fail by the pigeonhole principle. Since your algorithm does not prefer one type of data over another it by definition can not meaningfully compress.

# Answer
> 1 votes
There are trivially $2^k$ possible binary strings of length $k$, and hence any encoding that is reversible necessarily uses $2^k$ different bit-strings to encode all of these strings (representing files). So clearly any reversible encoding must map at least one binary string of length $k$ to a binary string of length at least $k$, since there are only $2^k-1$ possible binary strings of length less than $k$. Thus no reversible encoding can compress all strings of length $k$. So we don't even need to look at any details of your proposed 'hash function technique' to know that it will fail.

---
Tags: algorithms, hash, data-compression, heuristics
---


# Question
Title: Asymptotic notation and random variables
I have two random variables $X$ and $Y$ and I want to bound the value of one in terms of the other (for now, I don't care about the actual distribution of their values).

Suppose that the two variables can have different distributions with values chosen from $\[1, n\]$. But $X$ is always upper bounded by $Y \cdot c\log{n}$ for some constant $c$. Can I write this as $X = O(Y\log{n})$ (if I care about the behavior for large $n$). I'm not sure what is the convention wrt to random variables and asymptotic notation.

# Answer
On first look, the notation $X = O(Y\\,\log{n})$ seems intuitively reasonable since $X$ is always upper bounded by $c (Y\\,\log n)$ for some constant $c$. ($c$ must be positive since $X,Y\ge1$).

Can we formalize the exact meaning of that notation?

Here is one natural definition.

> Let $(\Omega,S,T)$ represents a set of 2-dimensional random vectors on $\Omega$ parameterized by $n$, i.e., for all $n$, $(S\_n, T\_n)$ is a random vector from $\Omega\_n$ (which is a set of possible outcomes) to ${\Bbb R}^2$. We write
>
> $$S=O(T){\text{ as }}n\to \infty $$ if and only if there is a positive constant $c$ such that for all sufficiently large values of $n$, for all $\omega\in\Omega\_n$, the absolute value of $S\_n(w)$ is at most $c\\,T\_n(w)$.

We can apply the above definition to $(I, X, Y\\,\log n)$ where $I\_n=\[1,n\]$.
> 0 votes

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


title: If Then Constraint Linear Programming

text:
# Question
Title: If Then Constraint Linear Programming
I want to write the following constraint: If A=1 and B \<= m then C=1 ( where A and C are binary, m is a constant and B is continuous).

# Answer
> 1 votes
My solution requires some kind of hack in the model, a *Big*-$M$ value, which is pretty common, but also a tolerance $\varepsilon$, which is not very desirable. I hope that I do not miss something easy here but reckon there is no way around it.

To model a condition of the form $(X \wedge Y) \to Z$ for binary $X, Y, Z$, you can use $$\tfrac12(X + Y) \leq Z + \tfrac12.$$ We can verify this by inserting: $X=Y=1$ yields to $1$ on the left hand side, thus, $Z$ has to be at least $\frac12$, and since it is binary, it must be $1$. If either $X$ or $Y$ is $0$ (or both), we have at most $\frac12$ on the left hand side and in this case $Z$ might be either $0$ or $1$.

We also need to transform the constraint $B \leq m$ as a binary variable in order to use the template above. This can be done by introducing a new binary variable $B'$ which must assume the vaue $1$ iff $B \leq m$. We also need a *Big-$M$* value which must be greater than any value that $B$ can assume (note that for numerical reasons in practice, $M$ should be not too large). Moreover, we have $\varepsilon$, a small tolerance value to get a strict $\>$-inequality (in practice you would choose the difference to the next greater number from $m$ that can be represented exactly on your machine). We now add the constraints $$B \leq m + (1-B')M\tag{1}$$ $$B \geq m + \varepsilon - B'M\tag{2}$$ $(1)$ guarantees that $B' = 0$ if $B \> m$, $(2)$ guarantees that $B' = 1$ if $B \leq m$. We verify this again: If $B \leq M$, $(1)$ and $(2)$ can be satisfied with $B' = 1$, but not with $0$. If $B \> m$, we need $B' = 0$ to satisfy $(1)$ and then $(2)$ is satisfied since $B$ is at least $\varepsilon$ larger than $m$.

Putting it all together, we obtain your constraint $$ \tfrac12(A + B') \leq C + \tfrac12,\\ B \leq m + (1-B')M,\\ B \geq m + \varepsilon - B'M. $$

---
Tags: integer-programming
---


# Question
Title: Is this a good way of generating diverse solutions to a problem using a genetic algorithm?
Imagine a complicated blackbox-esque system that has 20 inputs and 5 outputs. I have a set of criteria I am able to use to construct a fitness function. I run a genetic algorithm to deduce values which maximize my fitness function, and I keep iterating until a solution emerges which passes a threshold. Once this threshold is met, the genetic algorithm starts afresh except the fitness function now includes a positive term proportional to the euclidan distance between the candidate solutions and the previously determined solution (the one that exceeded the threshold earliar.)

Once a second set of inputs is found which matches exceeds the threshold, the fitness function is updated to also include a term proportional to the euclidian disance from the second solution. Both terms are divided by two to prevent this euclidan distance derived terms in my fitness function from overpowering the others.

Would a process like this, iterated sufficiently, be an efficient way of generating a diverse set of inputs, each of which represents a set of inputs which achieve a high fitness score?

(Please assume that a diverse of solutions exists for the problem at hand; the goal of the algorithm is to find them)

# Answer
> 1 votes
The success (or otherwise) of your proposed scheme may well be highly problem dependant, so I would urge you to consider diversity-promoting methods such as 'niching' or 'island models' that have proved useful across a wide-range of problems.

Island models, for example involve partitioned populations that are evolved separately, with only occasional gene transfer.

More details on diversification methods can be found in the (freely downloadable) 'Essentials of Metaheuristics'

---
Tags: optimization, genetic-algorithms
---


# Question
Title: Is "lazy evaluation" part of the compilation process or a run-time feature?
I'm studing the `Clean` functional programming language, and like other functional PL it uses Lazy Evaluation.

The thing that I can't get is when a PL that using that kind of evaluation evaluates the needed parameters. Does the compiler recognize which parameters are used and generate the code for evaluating them? or maybe some run-time mechanism takes responsibility to evaluate the parameters?

My question is about the concept of Lazy Evaluation in general, not just about this particular language.

Thanks in advance!

# Answer
I am not familiar with Clean; this answer addresses Lazy Evaluation in general.

Lazy evaluation happens at runtime.

The most fundamental form of lazy evaluation is leftmost reduction in lambda calculus. I will not burden this answer with a full introduction to lambda calculus. The intuition is that terms in lambda calculus consist of function definitions and function applications (and little to nothing else). Runtime of a program (which is a term) means evaluating the term. For an application term (which you can think of as $f(a)$), both $f$ and $a$ are also terms. Evaluating $f(a)$ may entail evaluating $f$ and/or $a$. The principle of leftmost reduction (lazy evaluation) means that $f$ is evaluated before $a$. Let us say $f$ is the function defined by $f(x)=x+x$ and $a$ is the term $1+2$. Then, lazy evaluation proceeds with the following steps:

1. $f(a)$
2. $a+a$
3. $(1+2)+a$
4. $(1+2)+(1+2)$

(At least if $+$ does not have a definition of its own. If it has, then after 2. the definition of $+$ will be expanded.)

If, on the other hand, $f$ is defined by $f(x)=0$, the evaluation is

1. $f(a)$
2. $0$

You notice that $a$ is not evaluated (because it is not needed), hence the connection to lazy evaluation. One final comment on this part: Lambda terms are in prefix notation, so "leftmost" actually means "outermost" when you think in terms of nested function applications.

In the second example above, lazy evaluation led to a speedup, because the term $a$ was not evaluated. In the first example, it led to a slowdown, because $a$ was evaluated twice. Actual lazily evaluated functional programming languages usually (again, I am not familiar with Clean) make the following optimization: Terms are not stored as syntax trees but as syntax dags. That is, in the first example, the two $a$ in term 2 would be the same node, also shared among all other positions of all other terms into which $a$ might have been copied. As soon as lazy evaluation dictates that $a$ is evaluated, the result is stored in place of the node $a$, becoming immediately available at all other occurences of $a$. The effect is a bit like memoization.
> 0 votes

---
Tags: functional-programming, evaluation-strategies
---


# Question
Title: Does every Partially Ordered relation and its dual have the same number of topological orderings?
Given the Hasse Diagram of a Partially Ordered Relation, is it the case that both the POSET itself and its dual POSET have the same number of topological orderings? I have tried a few examples, and although it does seem to be the case, I need a formal way of proving the same. So please help me with this.

# Answer
> 0 votes
> Is it the case that both the poset and its dual poset have the same number of topological orderings?

Yes, you have observed/discovered a fact about partially ordered set (poset). In fact, there is a stronger and more pleasing fact, which is a special case of the duality of order theory.

---

**The dual order of a topological ordering of a poset is a topological order of the dual order of that poset.**

Given a poset $p$, let $p^{d}$ be the **d**ual order of $p$. Let $p\rightarrowtail$q mean $q$ is a topological ordering of $p$. Then the above claim can be expressed as

$$ p\rightarrowtail q\ \Leftrightarrow p^d \rightarrowtail q^d$$

**Proof**: All we need to do is to follow the definitions. Let the underlying set of $p$ be $S$, which is also the underlying set of $q$, $p^d$ and $q^d$. For a poset $p$, we use "$\preceq\_p$" to denote the binary relation on of $p$ $S\times S$.

"$\Rightarrow$":

* Let $s\_1,s\_2\in S$ such that $s\_1\preceq\_{p^d} s\_2$. Then by the definition of the dual order, $s\_2\preceq\_{p} s\_1$. By the definition of a topological sort, $s\_2\preceq\_{q} s\_1$. By the definition of the dual order, $s\_1\preceq\_{q^d}s\_2$.
* Since $q$ is a total order, so is $q^d$.

"$\Leftarrow$":

* Let $s\_1,s\_2\in S$ such that $s\_1\preceq\_{p} s\_2$. Then by the definition of the dual order, $s\_2\preceq\_{p^d} s\_1$. By the definition of a topological sort, $s\_2\preceq\_{q^d} s\_1$. By the definition of the dual order, $s\_1\preceq\_{q}s\_2$.
* Since $q^d$ is a total order, so is ${(q^d)}^d=q$.

In fact, the implication "$\Leftarrow$" is the dual of the implication "$\Rightarrow$". Replacing $p$ by $p^d$ and $q$ by $q^d$ in the implication "$\Rightarrow$", we get "$\Leftarrow$".

Q.E.D.

---

The claim above shows that given a poset $p$, whenever we can construct a topological order $q$ for $p$, we also have $q^d$, a topological order for $q^d$. Hence $q\to q^d$ maps the topological orders of $p$ to the topological orders of $p^d$.

Similarly, whenever we can construct a topological order $r$ for $p^d$, we also have $r^d$, a topological order for ${(p^d)}^d=p$.

The map $q\to q^d$ and $r\to r^d$ are inverse functions to each other. So, each map is, in fact, a one-one correspondence. So the number of topological orderings of $p$ equals the number of the topological orderings of $p^d$.

---

Be careful that the topological orders of the original poset $p$ and its dual $p^d$ might not be same, although they are dual to each other.

For example, we can check the poset $p=\\{a,b,c\\}$ with $a\preceq\_p b$ and $a\preceq\_p c$. All topological orders of $p$ shares the unique least element $a$ but don't share greatest elements. All topological orders of $p^d$ shares the unique greatest element $a$ but don't share least elements.

---

**Exercise.** A poset is connected if the directed graph representing the poset is connected. Show that the maximum number of topological orderings of a connected poset of $n$ vertices is $(n-1)!$.

---
Tags: partial-order
---


# Question
Title: Is there a data structure that can find the kth smallest in constant time with logarithmic add and delete operations?
I'm looking for a single or a conjunction of data structures that can find the kth smallest element in constant time, delete the kth smallest element in logarithmic time, and add a new element in logarithmic time. The closest I've found to this is the order statistic tree which achieves logarithmic add and delete operations but has logarithmic time complexity for accessing the kth smallest element.

Any ideas along these lines would be much appreciated.

Clarification: kth smallest means that for any variable k value (non-constant), the data structure should be able to retrieve that value

# Answer
An array is the only thing that will get you consistent lookup in constant time.

Removal & Insertion time $\in O(n)$

If you can fit your data to a model (I.e. a polynomial) and the size of your elements remains somewhat constant you can have almost constant lookup with log addition/removal
> 1 votes

# Answer
Kth smallest number in a dynamic stream of numbers. Idea from the above source.

Have two heaps, one a max heap with $k$ elements (all the elements less than the $k$th largest element and the $k$th largest element itself are here) and the rest of the elements are in the other min heap.

1. Inserting a new element: If the new element is less than the top of the max heap (which is the current $k$th largest element), then insert it into the max heap, after that (I mean to say after the heapification following the insertion) pop the top element and insert it into the min heap. If the new element is greater than or equal to the current $k$th largest insert it into the min heap.
2. Deletion: If the element is in the min heap (ie., greater than equal to the $k$th largest) then simply delete from the min heap\*. Else delete the element from the max heap and pop the top of the min heap and insert it into the max heap.
3. Look up: simply output the top of the min heap. You'll have to suitably handle the corner case where there aren't enough elements ie. the total number of elements are less than $k$.

Please look into deletion of element in $O(\log n)$ time. It's a little complicated – you've gotta keep track of the positions of the elements in the heap so that you have $O(\log n)$ if you use a set (in C++) or $O(1)$ amortized if you use hash tables/unordered set. After finding the element in heap you've gotta replace it with the last element in the heap and let it sift down or up, which is $O(\log n)$.
> -1 votes

---
Tags: algorithms, data-structures, time-complexity, asymptotics
---


# Question
Title: negative weight cycle detection using dijkstra's algorithm
Can we store a struct in place of vertex. struct { int v, update\_count; }

run dijkstra's algorithm and whenever a node is updated we will increase update\_count value. If update\_count value is greater than V(no of nodes) we will know that there is negative weight cycle. Is this a viable solution.

# Answer
> 2 votes
No. In a graph with $n$ nodes, Dijkstra's algorithm never updates a node more than $n-1$ times, so your test will never change anything. More fundamentally, negative-weight edges or cycles don't cause Dijkstra to get into infinite loops; they just make it give wrong answers in some cases.

This answer on Stack Overflow gives more detail.

---
Tags: graphs
---


# Question
Title: Turing machine where the next step is determined by the state and the symbols up to the read/write head
Given a modified type of turning machine where

$\delta = Q\times \Gamma^\* \implies Q\times \Gamma \times \\{L,R\\}$

where the next step of the machine is determined by the current state and whatever written on the tape up to the current point.

For example: if the tape content is $a\\\_ab\\\_\\$\\$a$, and the head is on the left \\$, then the next step is determined by the state and the word $a\\\_ab\\\_\\$$.

1. How can I prove that unrecognized languages can be recognized with these types of machines?
2. Do those machines contradict the Church–Turing thesis?

# Answer
Suppose we are given a language $L$ of words of finite length. We will construct machine $M\_L$ that runs as the following.

---

$M\_L$ starts at state $q\_0$. On input $x$ of finite length that is put to the right of its head, $M\_L$ will move right all the way to the end of input, keeping the input and state intact. (This might mean nothing if the input is empty.) When $M\_L$ read the first blank symbol, what is written on the tape up to the current point exclusive is exactly the input $x$. (If current point should be included, let $M\_L$ go back a cell.) It halts, changing state to

* $q\_1$, an accepting state if $x\in L$,
* or $q\_2$, a rejecting state otherwise.

It is clear that $M\_L$ decides $L$.

---

Well, it is reasonable to say that that $M\_L$ does not compute $L$ at all. $M\_L$ just knows effectively each and every word in $L$ without any computation. When $L$ is infinite or even undecidable, we are not able to build or truly simulate such a machine within any bounded time by any known physical means and intelligence. Hence, we would not believe those imaginary machines contradict the Church–Turing thesis.

---

**Exercise.** Given a modified type of turning machine where

$$\delta: Q\times \Gamma^\* \to Q\times \Gamma \times \\{L,R\\}$$

where the next step of the machine is determined by the current state and the content of last $\lceil\log\_2n\rceil$ cells that has been read by it, where $n$ is the number of steps the machine has run. Can some unrecognized languages be recognized with these types of machine?
> 1 votes

# Answer
Here is an informal argument. I will leave you to fill in the gaps.

If such an enhanced Turing machine (let's call it a megaTuring machine) were possible, then you could program it to accept any language (any subset of $\Gamma^\*$) simply by listing the words in the language. Even a language for which a formal grammar does not exist (i.e. an unrecognizeable language) could be "recognized" by a megaTuring machine programmed with a list of the words in that language.

The problem is that the set $\Gamma^\*$ is infinite, so in general the program for a megaTuring machine is infinitely large. We could reduce the program to a finite size if there were some rule that allows us to compress $Q \times \Gamma^\*$ to a finite size (for example "do $X$ if tape content is $a$; do $Y$ if tape content is anything else"). But these are precisely the cases where the language recognized by the megaTuring machine can be described by a formal grammar, and so the behavior of the megaTuring machine can be reproduced by an ordinary Turing machine.

Since part of our informal definition of an algorithm is that it can be described in a finite amount of space and time, the programs that a megaTuring machine could run are not, in the general case, algorithms. So the concept of a megaTuring machine does not contradict the Church-Turing thesis.
> 1 votes

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


# Question
Title: Covering radius of a code in the Hamming space
A deterministic $(2−2/(k+1))^n$ algorithm for $k$-SAT based on local search

I have read this paper and I couldn't understand how to culculate the $covering$ $radius$ of a code in the Hamming space. It is defined as follows in the paper.

---

We identify assignments with binary words. The set of these words of length $n$ is the $Hamming$ $space$ denoted by $H\_n=\\{0,1\\}^n$. The $Hamming$ $distance$ between two assignments is the number of positions in which these two assignments differ. The $ball$ of radius $r$ around an assignment $a$ is the set of all assignments whose Hamming distance to $a$ is at most $r$.
A $code$ of length $n$ is simply a subset of $H\_n$. The $covering$ $radius$ $r$ of a code $C$ is defined by $$r=\max\_{u∈\\{0,1\\}^n}\min\_{v∈C }d(u,v),$$ where $d(u,v)$ denotes the Hamming distance between $u$ and $v$.

---

The $\max$ of $\min$ is exactly the point I couldn't calculate. So I considered the instance of $C$ and tried to calculate its covering radius.
e.g.)$$C=\\{000,010,011,100,101,110\\}⊆H\_3$$
In this case, how can I calculate the covering radius $r$?

# Answer
It's easier to remove from your table all lines with codes already in C. In your case only two lines will remain, minimum distance in both lines are 1, so the maximum distance of these two is `max(1,1)=1`

Overall, the algorithm is the following:

* for each possible code `x`, find the closest element `c` in C (i.e. the one with minimum distance `d(x,c)`) and record this distance
* find the maximum of all distances recorded at the previous step

I find that it's well visualized with set of spheres covering part of 3D space. You check all points outside of spheres and find one that has the largest distance to its closest sphere.
> 1 votes

---
Tags: hamming-distance
---


# Question
Title: Which memory holds the copy of the program that is to be executed?
I don't know whether it is RAM or cache; I can say that isn't the registers since their memory capacity is very small.

# Answer
> 2 votes
It's the RAM.

But further, in order to enhance speed, the CACHE stores a shadow of the RAM content, so it may hold a copy of the program as well (similarly, the RAM has a copy of the program that previously was stored on the hard-drive).

Eventually, parts of the code goes into the CPU and gets stored in one of its registers (not the general purpose ones, but rather some designated registers you have no access to; just think about them as flip-flops). From that point, the program is being executed, one instruction at a time, by the CPU hardware.

# Answer
> 2 votes
This is a very ambiguous question. The *whole* program will be stored on a local hard drive or a remote server or some other secondary storage device such as a flash drive. At run time some part of the program will be copied into RAM, but not necessarily the whole program. It is the job of the operating system to make sure that RAM contains a copy of the next set of instructions or data that the program needs - this task is called "memory management" or "paging".

From RAM or "main memory", individual instructions will then be copied into instruction cache memory, into a series of pipelining buffer registers and finally into the instruction register which holds the instruction that is currenttly being executed.

# Answer
> 1 votes
A program will remain in secondary memory (HDD) is not running or in Primary memory (RAM, CACHE) if ran recently or expected to run. A program that is being executed is called a process. For every process, a Process Control Block is created and kept in primary memory (RAM). The PCB contains pointers to the start and the current line in the program to be executed .

# Answer
> 1 votes
Your question doesn’t make sense. There is no “memory” dedicated to holding “the copy of the program to be executed”.

On a modern computer there isn’t *one* program to be executed. Normally I have a dozen or two programs running at the same time.

Each program is stored on the hard drive, SSD drive or flash drive. The OS assigns address space to the program, then the whole program is mapped to that address space. At that point, none of the program is in RAM. As instructions are to be executed, the OS automatically loads those instructions into RAM. Cache memory holds copies of the least recently used data in RAM. Instructions are removed from cache or RAM if they have not been used for a while.

Summary: It’s all over the place.

# Answer
> -2 votes
The whole point of the Von Neumann architecture is that programs and data are treated in the same way. So the answer to your question is that the registers, cache, main memory and backing store are used in exactly the same way as they would be for any other data.

---
Tags: computer-architecture
---


title: Dubins TSP crossing trajectory theorem

text:
# Question
Title: Dubins TSP crossing trajectory theorem
In the Dubins TSP (DTSP for short), one needs to visit a set of given points in the plane, and return to the starting point, minimizing the distance of such a trajectory. The difference with the Euclidean TSP (ETSP for short) however is that the visiting entity is curvature constrained by some $r$, meaning the vehicle can, at any moment in time, either go straight, or move on the edge of some circle of radius $r'\geq r$.

Consider the following theorem, by Le Ny *et al.* (Theorem 2 in http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.982&rep=rep1&type=pdf) which we will call **Theorem 1** in this post :

> A trajectory based on an ETSP optimal visit order, is not necessarily an optimal trajectory for the DTSP.

(I changed the wording of their theorem to suit this post)

Suppose the next theorem, **Theorem 2** :

> There exists instances for which the optimal DTSP visit order creates a **crossing** ETSP trajectory.

My question is : Does Theorem 2 imply Theorem 1 ?
The idea is as follows. Since some instances have the optimal DTSP visit order creating a crossing ETSP trajectory $T$, this ETSP trajectory $T$ is not optimal (due to the triangle inequality). This in turn implies that some optimal ETSP trajectory $T\*$ on these instances (or their corresponding optimal ETSP visit order) cannot be adapted and optimized to obtain the optimal DTSP trajectory. If it could, then $T = T\*$, which is a contradiction, since $T$ admits a crossing trajectory.

# Answer
No, theorem 2 does not imply theorem 1 unless you also prove for that instance that *every* optimal DTSP visit order creates a crossing ETSP trajectory. There might be another optimal DTSP $|T'| = |T|$ visit order that does not result in a crossing ETSP so that we have $T\* = T'$.
> 1 votes

---
Tags: traveling-salesman
---


# Question
Title: What untyped term inhabits induction on natural numbers in CoC?
Induction on Church-encoded natural numbers (which I will call `indNat`) can not be defined within the Calculus of Constructions.

If we assumed `indNat` as an axiom, is there an untyped term that would have the semantics of the induction function? What if we had Scott-encoded natural numbers and `fix`?

Can induction be inhabited in CoC + `fix` (such that the function would have the proper semantics, not an infinite loop)?

# Answer
Yes, there is such an untyped function, and it turns out that it is equivalent to the untyped erasure of iteration for church numerals.

The Cedille project has been doing lots to give types to these functions, and the core concept there is the *dependent intersection*, which provides a limited form of self reference that is enough to derive induction principles. This paper will probably interest you.

If you have $fix$ you can definitely implement induction principles, using structural recursion on the natural number. This is how they do it in CiC and Coq, with an extra restriction that the recursive calls must be on a structurally smaller value. Without this condition, you can write induction, but you also can write nonterminating terms with the same type as an induction principle.
> 5 votes

---
Tags: lambda-calculus, type-theory, dependent-types, calculus-of-constructions
---


# Question
Title: Are Context Sensitive Grammar with Polynomial Complexity Time?
Accordingly, to the question Chomsky Hierarchy and P vs NP, Context-Sensitive Grammars are on Linear Space.

Assuming a Deterministic Parser is the one which can parse unambiguous grammars in something like linear time complexity, while a NonDeterministic Parser can parse any grammar in some worst time complexity like $O(n^5)$ or exponential.

1. When something is on Linear Space, it takes Exponential time to be parsed by a Deterministic Parser? (probably space complexity has no relation to its time complexity, maybe something in $NSPACE(n)$ or $PSPACE(n^2)$ can affect time complexity?)
2. Can any Context Sensitive Grammar be parsed in a Polynomial Complexity Time?

# Answer
> 3 votes
To your first question, the answer is affirmative:

On one hand, a task that only takes polynomial time can only take polynomial space, and many among them only take linear space, so there definitely exist tasks which take linear space and polynomial time.

On the other hand, that doesn't mean *every* task that takes linear space takes only polynomial time. However, until now, nobody has been able to prove either way. Even for the hardest problems that take polynomial space, the PSPACE-complete problems, it is not known whether they can be done in polynomial time: we don't know whether PSPACE = P. If you can prove for a single PSPACE-complete problem that it can be done in polynomial time, or that it cannot, you will be famous in computing science forever. In practice, for such problems, we have no better than exponential algorithms.

To answer your second question: parsing context-sensitive grammars is PSPACE-complete, so it takes exponential time in practice; it takes only polynomial time for *growing* context-sensitive grammars.

---
Tags: complexity-theory, formal-languages, turing-machines, context-free, chomsky-hierarchy
---


# Question
Title: Polynomial size Boolean circuit for counting number of bits
Given a natural number $n \geq 1$, I am looking for a Boolean circuit over $2n$ variables, $\varphi(x\_1, y\_1, \dots, x\_n, y\_n)$, such that the output is true if and only if the assignment that makes it true verifies

$$\sum\_{i = 1}^{i = n} (x\_i + y\_i) \not\equiv n \bmod 3$$

I should specify that this I am looking for a Boolean *circuit*, not necessarily a Boolean formula as it is usually written in Conjunctive Normal Form (CNF). This is because when written in CNF, a formula like the one before has a trivial representation where the number of clauses is approximately $\frac{4^n}{3}$, as it contains a clause for every assignment $(x\_1, y\_1, \dots, x\_n, y\_n)$ whose bits sum to a value which is congruent with $n \bmod 3$. Constructing such a formula would therefore take exponential time.

I have been told that a Boolean circuit can be found for this formula that accepts a representation of size polynomial in $n$. However, so far I have been unable to find it. I would use some help; thanks.

# Answer
> 2 votes
You can write a straight-line program (an equivalent way to define a circuit) that computes the Boolean variables $z\_{i,j}=\[x\_1+y\_1+\cdots+x\_i+y\_i \equiv j \pmod{3}\]$ (where $i=1,\ldots,n$ and $j=0,1,2$) as follows:

* $z\_{1,0} = \lnot x\_1 \land \lnot y\_1$.
* $z\_{1,1} = (x\_1 \land \lnot y\_1) \lor (\lnot x\_1 \land y\_1)$.
* $z\_{1,2} = x\_1 \land y\_1$.
* $z\_{i+1,j} = (z\_{i,j} \land \lnot x\_{i+1} \land \lnot y\_{i+1}) \lor (z\_{i,j-1} \land ((x\_{i+1} \land \lnot y\_{i+1}) \lor (\lnot x\_{i+1} \land y\_{i+1})) \lor (z\_{i,j-2} \land x\_{i+1} \land y\_{i+1})$

The output of the circuit is $o = \lnot z\_{n,n \bmod 3}$.

The circuit has size $O(n)$.

---
Tags: complexity-theory, logic, boolean-algebra, polynomials
---


# Question
Title: Sensitivity and block sensitivity of specific problem, is there an errata? Arora-Barak exercise 12.4
There's an exercise in Arora-Barak on sensitivity and block sensitivity. The statement of the problem is:

> Let $f$ be a function on $n = k^2$ variables that is an OR of $k$ applications of $g: \\{0, 1\\}^n \rightarrow \\{0,1\\}$, all $k$ blocks of variables are disjoint. $g(x\_1, \ldots, x\_k) = 1$ if there exists $i \in \[k-1\]$ s.t. $x\_i = x\_{i=1} = 1$ and $x\_j = 0$ for all $j \neq i$. Prove that $s(f) = \sqrt{n}, bs(f) = n/2$.

I am confused about $x\_{i=1} = 1$. Is there a typo and should it be $x\_{i-1} = 1?$ If it is the case, what about $i=1$? Or is it simply $x\_1 = 1?$

Another question is whether $g = 1$ iff the condition holds, or if it is only a sufficient condition.

# Answer
The definition of $g$ should be: $g(x\_1,\ldots,x\_k) = 1$ if there exists $i \in \[k-1\]$ such that $x\_i=x\_{i+1}=1$ and $x\_j = 0$ for $j \neq i,i+1$.

As for your question, whether $g=1$ iff the condition holds, or whether it is just a sufficient condition: in mathematics, when we define something, we use the word "if" to mean "iff". Check your favorite textbook, monograph or paper for many examples.
> 1 votes

---
Tags: complexity-theory
---


title: Join with Bloom-filters

text:
# Question
Title: Join with Bloom-filters
can you tell me how i can use a bloom-filter by a joining operation with two tables?

let's assume that:

**Table A ={A\_id,B\_id,age}**, **Table B = {B\_id, color}**.

now i want to use a bloom-filter so i can do the join operation faster, but i do not know how i can use this in this case. I would first take from A the PK A\_id and bloom-filter that with some hash functions and just mark the indexes with 1 and then i would do the same operation with Table B and finally just AND both results. but it's not correct...

# Answer
> 2 votes
A Bloom Filter will typically be used to eliminate mismatches quickly, since it produces true negatives, but some false positives. A join (specifically, an equi-join) which is expected to have some non-matching keys can be sped up by pre-processing the valid keys from one table into a Bloom filter. The join operator tests each key from the other table against the Bloom filter first and only does a full lookup for each positive ("maybe in the set") result.

For instance if you are joining on B\_id above, you might first preprocess all of the B\_id's in table B into a Bloom filter, and use it to test each B\_id in table A for a possible match. If a B\_id from A tests negative in the filter, you can discard it, so you only consult table B for B\_id's which are either in B or are false positives.

The benefit of using a pre-filter is basically in the number of negatives it can eliminate at a lower per-key cost than a full lookup. The filter may also be a smaller size than the set of keys it represents, so it can be broadcast to all threads or nodes that are processing the join in a distributed environment.

Ives and Taylor summarize a number of techniques like this in Sideways Information Passing for Push-Style Query Processing.

---
Tags: database-theory, databases, bloom-filters
---


# Question
Title: CSP Forward checking with n-ary (and binary) constraints
I have implemented my own CSP solver using a Backtracking algorithm. Within the Backtracking algorithm I apply a Forward Checking algorithm (reducing domains of connected, unnasigned variables) that only works with Binary constraints.

The problem I have is that the CSP I try to solve has lots of n-ary constraints, making the FC algorithm mostly redundant.

Is there a way to enhance or replace my FC algorithm, so it works with n-ary constraints. Or is there a "simple" procedure to convert n-ary constraints to binary constraints?

**EDIT:** Added pseudo code (attempt) of the Forward Checking algorithm:

```
function ForwardChecking(variable, csp) list of variables with new domains, or failure
    for each constraint in connectedConstraints(variable) do
        if connectedVariable is assigned then
            if constraint is not satisfied then
                return failure
        else
            for each value in connectedVariable.domain do
                connectedVariable.assign(value)
                if constraint is not satisfied do
                    remove value from connectedVariable.domain
                if connectedVariable.domain.count == 0 then
                    return failure
                add connectedVariable to solution
    return solution

```

# Answer
> 1 votes
Instead of forward checking, try arc consistency. You run arc consistency after every assignment to reduce backtracking.

Another further improvement would be assigning a least constraining value (LCV) to a variable with minimum value in the domain (MRV).

# Answer
> 1 votes
Arc-Consistency algorithm only works on binary constraints.You have to use binary encoding and hidden variable encoding method.

---
Tags: algorithms, satisfiability, sat-solvers, constraint-satisfaction, constraint-programming
---


title: Learning a perceptron from stream data

text:
# Question
Title: Learning a perceptron from stream data
I want to train a Perceptron using stochastic gradient rulefrom the stream data. I have very limited amount of memory and i can store only $N$ examples.

Suppose my population consist of point as show in the following picture:

Now suppose my first $N$ examples come in following fashion and i can classify them correctly as show in the next picture:

Now the problem is if the next $N$ examples come in this way:

and i have classified them as shown. The problem is that since i can't train perceptron for previous $N$ examples(because i can store only $N$ examples and previous $N$ examples need to be thrown away) and training on next $N$ examples contradicts the hyper-plane for previous $N$ examples.

How to train a perceptron from stream data? Do i need to store all examples or there is an alternative way?

# Answer
I think you're confusing yourself by worrying about a worst case that likely won't happen. Assuming each element of the stream comes randomly and independently from some distribution, then it is exponentially unlikely that the case you mention happens.

How do you train from a stream? Easy: each time you see an example, you update the weights of the neural network following the rules of gradient descent, then throw away that example. In this way, the weights of the neural network change over time, and you don't need to store any past examples. Over time, as you've seen enough examples, this should converge to a neural network that performs about as well as possible on the data, assuming that all of the data in the stream comes from the same distribution.
> 1 votes

# Answer
After the first $N$ examples, the separator you got is after its rigorous adjustments through shift and angular orientation operations from its initial position. These adjustments are done by the weights of the data of each dimension. So every time a new data arrives and fed to the perceptron, the weights changes accordingly (rate of change in error is calculated) and the separator gets a new position. Thus there is no question of storing old data and state. If your system is too low in memory to hold the neural network and the feature vector, then it will be handled by the OS through the virtual memory system.
> 0 votes

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


# Question
Title: UCT (Upper Confidence bounds applied to Trees)
For UCT (Upper Confidence bounds applied to Trees), why If given infinite time and memory, UCT theoretically converges to Minimax. ?

Besides, I do not quite understand how *UCT deals with the flaw of Monte-Carlo Tree Search, when a program may favor a losing move with only one or a few forced refutations, but due to the vast majority of other moves provides a better random playout score than other, better moves.*

# Answer
This result is stated in:

* Kocsis, L., & Szepesvári, C. (2006, September). Bandit based monte-carlo planning. In European conference on machine learning (pp. 282-293). Springer, Berlin, Heidelberg.

It is the content of Theorems 5 & 6. Sadly there is no detailed proof for theorem 5.

The main reference for this is:

* Auer, P., Cesa-Bianchi, N., & Fischer, P. (2002). Finite-time analysis of the multiarmed bandit problem. Machine learning, 47(2-3), 235-256.

To give you some intuition about the convergence given infinite time, you need to understand the UCB1 formula: it makes a tradeoff between exploring the best move and exploring the least explored moves. As the term for exploring the least explored move can grow arbitrariy large and the payoff is smaller than 1, if you have infinite time, you will end up exploring it infinitely many times, even if its payoff is $0$.

Therefore, at a fixed node, given infinite time, you will explore infinitely many times each possible move. Repeat this by induction : you will explore the whole tree in infinite time. So in the end, what actually matters is the score of each node, as the exploration bias will go to $0$.

In short : what removes the MCTS flaw is the fact that you have infinitely many moves, it removes the randomness.
> 2 votes

---
Tags: algorithms, algorithm-analysis, search-trees, monte-carlo
---


# Question
Title: Is it reasonable to model row buffers in DRAM corresponding to the same bank ID as one big row buffer?
I'm creating a simple row buffer simulator to go along with a simple cache simulator in order to count hits and misses in the row buffer. Whenever a cache block isn't in the cache I want to go look for it in the row buffers of the main memory and record whether it is present of not.

How accurate would it be to have just one long "row buffer" struct containing all the data found in all the individual row buffers of each corresponding bank in each DRAM chip? Say that each chip has 8 banks, I would then have to create 8 of these extra long row buffers to simulate these chips. This idea is based on the understanding that all these chips work in unison, so that if I want to load the cache block at address 0, the row buffers of bank 0 in each chip would fill with data from addresses starting at address 0 in chip 0, and ending at address 0 + (length of row buffer * number of DRAM chips) in the last chip. It would assume a row interleaved address mapping (with consecutive rows in consecutive banks) for simplicity's sake.

Are there any major misunderstandings about how DRAM works that causes this to be a very bad way to model row buffer behavior or is this a reasonable simplification? I'd also like to underscore that simplicity is the main goal here.

EDIT *added clarification on question posted in comments below*: I assume that all the row buffers for banks with ID, say, 0 work together in unison on the same read or write, with all of them containing data for that particular operation. Couldn't I model these 8 row buffers (if I have 8 DRAM chips) as just one very big row buffer? The total size of this combined row buffer would be the length of the normal row buffer\*number of DRAM chips. So if I were to a model chips with 8 banks for example, I'd have 8 of these "combined" row buffers, one for each bank.

# Answer
You can look at how one of the existing DRAM simulators work. Consider, for example, Ramulator, which is a popular academic DRAM simulator. Ramulator Models main memory as a tree of nodes, where the root node represents a memory channel and lower nodes represent ranks, bank groups (supported in DDR4), banks, rows, and columns. For the DRR4 and DRR3 protocols, these levels are defined in the source code here and here, respectively. Therefore, the physical row buffer of each chip of the same bank are actually treated as a single row buffer whose state is maintained using a single value.
> 3 votes

---
Tags: computer-architecture, memory-management, simulation, memory-hardware
---


# Question
Title: How can we find a palindrome within a string?
The problem requires us to find the substring within a string which happens to be a palindrome. Multiple palindromes are also allowed.
For example, in "LODHIHDAK" "DHIHD" is a palindrome.

Comparing the reversed string with the original string to identify the common substring is one way but it isn't fool-proof.

For example,
In the case of "KLXABAXYC", it would work.
But in the case of "ABACDGFDCABA", it would not.

I was wondering if brute force could be used but I don't understand how.
I'm looking to find the longest palindrome.

# Answer
Of course, every letter is a one letter palindrome - so let's assume you are looking for a palindrome that is at least two letters long.

If your goal is just to find any palindrome in a string $\\{a\_i\\}$(rather than finding all palindromes or finding the longest palindrome, for example) then you only need to consider two cases:

1) If $a\_n=a\_{n+1}$ for any $n$ then you have found a two letter palindrome.

2) If $a\_n=a\_{n+2}$ for any $n$ then you have found a three letter palindrome.

Any longer palindrome must contain a two or a three letter palindrome as a substring.
> 2 votes

# Answer
Your solution only works in the cases where the midpoint of the palindrome is the middle point of the string. You can use the more general following approach:

*Consider each letter of the string to be the midpoint of a palindrome. Then look to the left and to the right of the current letter and check if the characters match. If they do check if the next pair of characters match. If they do not, consider the next character as the midpoint.*

For example, consider the sting **AEBCDCBGGGGG**

You first consider the first $A$ to be the midpoint. Since it has no character to the left it cannot be a midpoint. You move on to the second letter, $E$ and consider it to be the midpoint. Next, you compare $A$ and $B$. Since they are not the same $E$ is not the midpoint of a palidrome. You consider $B$ as a midpoint. Again since $E$ and $C$ are not the same, $B$ cannot be the midpoint of a palindrome. After some steps, you will consider $D$ as a midpoint. This time its neighbouring letters are $C$ and $C$, therefore, $D$ is the midpoint of a palindrome. You move on to the next letters which are $B$ and $B$, so they are part of the palindrome. The next letters are $E$ and $G$, therefore they are not part of a palindrome. So you know that the string contains at least one palindrome, **BCDCB**. You continue traversing the string in the same way looking for more palindromes.
> 0 votes

---
Tags: algorithms, time-complexity, dynamic-programming
---


# Question
Title: prove that there is a complete language in $L \cup \{A_{TM}\}$
$A\_{TM} = \\{\langle M,w\rangle\mid w\in L(M)\\}$

$L$ = complexity class containing decision problems that can be solved by a deterministic Turing machine using logarithmic space

Given the language $L \cup \\{A\_{TM}\\}$,

we will say that $A$ is complete in $L \cup \\{A\_{TM}\\}$ if:

* $A \in L\cup\\{A\_{TM}\\}$
* For every $B\in L \cup \\{A\_{TM}\\} \implies B\le\_LA$

Is there a complete language in $L \cup \\{A\_{TM}\\}$?

# Answer
> 1 votes
We will show that $A\_{TM}$ is complete for your class.

In order to show that, we need to show that for every language $A\in L\cup \\{A\_{TM}\\}$, it holds that $A\le\_L A\_{TM}$.

First, if $A=A\_{TM}$, then the trivial reduction suffices. That is, a reduction that given input $x$, return $x$. Clearly $x\in A\_{TM}\iff x\in A\_{TM}$.

Now, if $A\in L$, we need to work slightly harder. We need to show that $A\le\_L A\_{TM}$. In order to do that, we construct a reduction from $A$ to $A\_{TM}$, as follows: let $M$ be a deterministic TM that decides $A$ in logspace (why does there exist such a machine?).

Now, the reduction works as follows: given input $x$, the reduction uses $M$ to check whether $x\in A$. If $x\in A$, the reduction outputs $\langle\epsilon, T\_1\rangle$, where $T\_1$ is a TM that accepts every input immediately. If $x\notin A$ the reduction outputs $\langle\epsilon, T\_2\rangle$, where $T\_2$ is a TM that rejects every input immediately. Note that $T\_1,T\_2$ are fixed, i.e. they are hard-coded in the reduction.

Try to prove that this reduction is correct, and that it is indeed in logspace.

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


title: Analysis of Basic Recursive Functions

text:
# Question
Title: Analysis of Basic Recursive Functions
I'm trying to understand the contrast between run-time for this function

```
public static String f(int N) {
    if (N == 0) return "";
    String s = f(N / 2);
    if (N % 2 == 0) return s + s;
    else            return s + s + "x";
}

```

and this function

```
public static String f(int N) {
    if (N == 0) return "";
    if (N == 1) return "x";
    return f(N/2) + f(N - N/2);
}

```

where string concatenation takes time proportional to the size of the strings.

So far, I believe that the first function is called log(N) times for input N and the second 2log(N) times. Is that right? Beyond that, I'm not sure how to think about how many operations happen in each of those calls. I know that for the first function, in the base case there are 0 operations (no concatenation), then 1 operation (concatenation of two null strings with a string of length 1?), then 2 operations. In general I believe the string produced by a call with N is of length N? But I just don't know where to start thinking about how it all adds up.

For the second one likewise I'm a little lost. I just need a way to approach the analysis. Keep in mind I'm not great with symbols, so if you're going to show off with symbols, I'd appreciate an explanation that will help me follow the symbols as well.

# Answer
Set them up as recurrences. First, note that both just return $N$ characters $x$. Call the time taken by the first function for $N$ $A(N)$ and similarly $B(N)$ for the second. For the first version, the function calls itself with $\lfloor N / 2 \rfloor$ (I'm taking your language to be Java or similar, dividing integers truncates), and then concatenates some strings. As noted, $f(N)$ is just $N$ times 'x'. Consider teh different cases, and what work is done in each of them:

$$A(N) = \begin{cases} 0 & N = 0 \\ A(\lfloor N / 2 \rfloor) + 2 \cdot N / 2 & N \> 0 \wedge 2 \mid N \\ A(\lfloor N / 2 \rfloor) + 2 \cdot (N - 1) / 2 + 1 & \text{otherwise} \end{cases}$$

You see that both last cases simplify to just $A(\lfloor N / 2 \rfloor) + N$. Your recurrence is $A(N) = A(\lfloor N / 2 \rfloor) + N, A(0) = 0$

For the second one, you get $B(N) = B(\lfloor N / 2 \rfloor) + B(\lceil N / 2\rceil) + N, B(0) = B(1) = 0$
> 2 votes

---
Tags: algorithms
---


# Question
Title: How to characterize equivalence classes induced by Myhill-Nerode theorem?
Given $L=\lbrace w\in \lbrace 0,1 \rbrace^\ast : N\_0(w)=N\_1(w) \rbrace$, where $N\_0(\cdot)$ and $N\_1(\cdot)$ mean the number of zeroes and ones respectively, I need to characterize the classes induced by the relation on $\\{0,1\\}^\ast$ $$x \thicksim\_{L} y \iff \forall z\in \\{0,1\\}^\ast \left(xz \in L \iff yz \in L\right)$$ The reference I have already shows that the (obviously, infinitely many) classes are of the form $C\_k=\lbrace w\in \lbrace 0,1 \rbrace ^{\ast} : N\_0(w)-N\_1(w)=k \rbrace $ and clearly $\bigcup\_{k\in\Bbb Z } C\_k = \\{0,1\\}^\ast $, but I have no idea how could I have deduced this correct characterization myself.

When given a regular language, I find it easier to construct a suitable minimal DFA and then "back engineer" each state to a useful characterization of its class. But for a non-regular language, I'm having a really hard time working with the relation definition. In this particular example, I don't understand how it applies to the classes $C\_k$ above.

So for me there are two underlying questions here:

1. If given the equivalence classes, how can one prove that they are indeed induced from the relation?
2. However, if they are not given, is there a systematic\algorithmic approach to characterize all of these classes for a given language? mainly, a non-regular one.

# Answer
> 2 votes
To prove that the classes $C\_k$ are equivalence classes for the Myhill-Nerode relation we need to show

1. For any strings $x,y \in C\_k$ there does not exist a distinguishing extension of $x$ and $y$. This proves $C\_k \subseteq \[w\]$.
2. For any $x \in C\_j$ and $y \in C\_k$ there does exist a distinguishing extension. Since every string $\omega$ belongs to some $C\_k$ this shows that the $C\_k$ form a partition of $\Sigma^\*$.

These together show that the $C\_k$ are exactly the equivalence classes under $\sim\_L$.

Let $N(w)$ denote $N\_0(x) - N\_1(x)$.

---

For the first part, note that $x, y \in C\_k \implies N(x) = N(y)$. Then for any extension $r$, we have that

$N(xr) = N(x) + N(r) = N(y) + N(r) = N(yr)$

and so $xr \in L \iff yr\in L$. Thus $r$ cannot distinguish $x$ and $y$.

---

For the second part, we have that $N(x) \neq N(y)$. Assume WLOG $N(x) \> 0$.

Then the extension $1^{N(x)}$ distinguishes $x$ and $y$ since $$N(x1^{N(x)}) = N(x) - N(x) = 0 \implies x1^{N(x)} \in L$$ while $$N(y1^{N(x)}) = N(y) - N(x) \neq 0 \implies y1^{N(x)} \notin L$$

---

Intuitively, we interpret the equivalence classes as "states" of some machine for deciding the language. This is literally true in the case of regular $L$, but even in this infinite case we can interpret "state" to mean $k$. Once two strings are in the same state, there is no going back: there is no further information that we can feed to the machine and cause it to diverge.

In this particular case, we look at the definition of the language and note that the only information that we care about is $N(w)$. Since this information in some sense captures all we need to know about a string, it makes sense that strings that are identical under this classification can never be distinguished by the language.

There is certainly no algorithmic way of classifying $\sim\_L$ in full generality since even deciding whether two strings belong to the same class is undecidable clearly for undecidable languages $L$.

In the restricted case of context free languages I don't know of any generic canonical characterization. There are some relevant discussions here and here

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


# Question
Title: Returning sorted lowest k elements in a binary heap
Given a binary heap of size $n$ and a number $k\le n$. How can I return an array with size $k$, which contains the $k$ lowest elements in the binary heap, so that it will be sorted in the end?

The problem is that the time-complexity needs to be $\Theta(k \log(k))$.

# Answer
> 3 votes
Construct a new min-heap $H$ using the root of the original heap $O$ as its only element. Then $k$ times you want to pop the smallest value from $H$, append it to our output array and add the children that node has in $O$ to $H$.

The maximum size $H$ gets here is $k + 1$, so all the above has a complexity of $O(k \log k)$.

If you meant to keep the original heap intact, you are now done. If you also want to remove these $k$ elements from $O$, then all you need to do is use $H$ as your new heap, making any leaf of $H$ use the child pointers that respective node had in $O$.

---

All of the above is assuming you have a pointer-based tree structure. If you use an array as your heap data structure using indices as implicit children, I doubt it's possible at all.

On top of that, this optimization is likely not worth it unless $n$ is very large and $k$ is very small.

---
Tags: algorithms, data-structures, heaps
---


# Question
Title: is it always true that the depth of BFS is $\leq$ DFS?
I have a simple theoretical question in very basic algorithms, as the title mentions, is it always true that the depth of BFS is $\leq$ DFS?

From what I understand, the tricky part here is the possible cycles in the graph. Even though that I believe that the depth of BFS will always be less or equal to the depth of DFS.

In each iteration of BFS, from what I understand, the depth might grow by one, but DFS's grows in each vertex it can not reach, sometimes above the maximal value of BFS.

So, is it always true that the depth of BFS is $\leq$ DFS?

# Answer
A result about BFS is that what you call the depth of the BFS of a node $v$ is the length of a shortest path from the source to $v$.

Assume the exists an instance where the depth of the DFS $\<$ BFS. Then we have a path from the source to $v$ that has length strictly smaller (the path taken by the DFS to reach $v$) than the length of a shortest path from the source to $v$ (the path taken by the BFS), which is impossible.

This argument by contradiction shows that depth BFS $\leq$ DFS, for any graph.
> 4 votes

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


# Question
Title: Figuring out when one algorithm will be slower than another algorithm
I'm studying for a computing exam and came past the following question on a past paper and need help with it.

When would algorithm *A* be slower than algorithm *B*? Demonstrate your answer with the help of an example. Also what will the value of *SUM* be at the end of each algorithm if the size is set to $10'000$?

Algorithm *A*:

```
SET sum TO 0
FOR i=1 to size
  FOR j=1 to 10000
    sum=sum+1

```

Algorithm *B*:

```
SET sum TO 0
FOR i=1 to size
  FOR j=1 to size
    sum=sum + 1

```

I came up with this answer but not sure if it is correct:

The algorithm *A* will be slower than algorithm *B* when the performance of the algorithm is directly proportional to the cubed or more of the size of the input data set, for example if the Big O notation becomes $O(N^3)$ or $O(N^4)$ or $O(N^5)$ etc. The Big $O$ notation $O(N^3)$ nesting the for loops in two more for loops:

```
Set Sum TO 0
For i=1 to size
  For k=1 to size
    For l=1 to size
      For j=1 to 10000
sum=sum+1

```

# Answer
> 1 votes
Algorithm *A* contains an instruction that is executed $size * 10000$ times.
Algorithm *B* contains an instruction that is executed $size * size$ times.

It is obvious that the comparison between *A* and *B* depends on the variable *size*.
You can see that if $size \< 10000$ then *B* performs better, and if $size \> 10000$ then *A* performs better.
If $size = 10000$ then *A* and *B* can be considered equally fast.

It is easy to calculate the result for $sum$ when $size = 10000$.

I am not sure if it makes sense to answer with big O notation here because the algorithms are different. *A* computes $size * 10000$ and *B* computes $size^2$, which are two different algorithms; it does not make sense to compare them with big O notation in my opinion. Usually big O analysis helps in comparing algorithms that solve the same problem, which is not the case here.

# Answer
> 0 votes
The question is posed badly.

The asymptotic execution time of one algorithm is $\Theta(n^2)$, the other is $\Theta(n)$. That means A is asymptotically faster on any implementation.

But that’s not the question. The question is “when is A faster”. And that depends on the exact implementation. We can make an educated guess: Both algorithms add up the same number of integers when size=10,000. But what the exact execution time is, we can only guess.

PS. Many compilers will replace the inner loop with “sum=sum+10,000” or “sum=sum+size” and the question changes totally. Many compilers will calculate the sum in constant time.

---
Tags: algorithms, algorithm-analysis, efficiency
---


title: vertex cover reduction to subset sum

text:
# Question
Title: vertex cover reduction to subset sum
> **Subset sum**
>
> * **Input:** A multi set $S$ of numbers and a natural number $t$
> * **Question:** Does $S$ contain a subset $A$ such that $\sum\_{x \in A} x = t$? (e.g., $\\{1,1,2,3,4,5\\}$, by multiset it means duplicates are allowed)

> **Vertex cover**
>
> * **Input:** An undirected graph $G$ and a number $k$.
> * **Question:** Does $G$ have a vertex cover of size $k$?

**Show: vertex cover $\leq\_P$ subset sum**

---

**My work so far:** I need to somehow transform $(G, k) \to (S, t)$

Above is a example graph $G$ that I constructed. It's vertex covers are $\\{v\_1, v\_3\\}$ so the size of the vertex cover is $2$, thus $k = 2$.

This is basically $S$

\begin{array}{|c|c|c|c|c|} \hline & e\_1 & e\_2 & e\_3 & e\_4 \\ \hline v\_1 & 1& 0& 0& 1\\ \hline v\_2 & 1& 1& 0& 0\\ \hline v\_3 & 0& 1& 1& 0\\ \hline v\_4 & 0& 0& 1&1\\ \hline \end{array}

if $e\_i$ and $v\_j$ is incident I put $1$; otherwise $0$

Now what I need is a target $t$ to satisfy this.

The matrix above can be written in a set to be $S = \\{1001, 1100, 0110, 0011\\}$ if I were to add up all these values probably in base 2 since its binary, it would give me a value but I think I need a consistent value $t$, so this wont work. I'm also unsure how to integrate the $k = 2$ into this either.

Could someone help me construct this?

# Answer
For simplicity write all the numbers in base $4$. Fix an arbitrary ordering of the edges of the graph $G$ and let $e\_i$ be the $i$-th edge ($i= 1, \dots, |E(G)|$).

For each vertex $v \in V(G)$ define an integer $n\_v$ of $|E(G)| + 1$ digits as follows:

* the $i$-th least significant digit of $n\_v$ is $1$ if $e\_i$ is incident to $v$ and $0$ otherwise;
* the most significant digit of $n\_v$ is $1$.

For each edge $e\_i \in E(G)$ let $m\_{e\_i} = 4^{i-1}$ (i.e., the $i$-th least significant digit of $m\_e$ is $1$ and all the other digits are $0$).

The instance of subset sum is obtained by choosing $S = \\{ n\_v : v \in V(G) \\} \cup \\{m\_e : e \in E(G) \\}$ and $t = k 4^{|E(G)|} + 2\sum\_{i=0}^{|E(G)|-1} 4^i$. In other words, the most significant digits of $t$ encode the number $k$ in base $4$, while the $|E(G)|$ least significant digits of $t$ are all equal to $2$.

---

If there is a vertex cover $V' \subseteq V(G)$ of $G$ of size $k$, let $E'$ be the set of edges $(u,v) \in E(G)$ such that *exactly* one of $u$ and $v$ is in $V'$. Then, $A = \\{ n\_v : v \in V' \\} \cup \\{ m\_e : e \in E' \\}$ is a subset of $S$ that sums to $t$. Indeed: $$ \sum\_{x \in A} x = \sum\_{v \in V'} n\_v + \sum\_{e \in E'} m\_v = k 4^{|E(G)|} + 2 \sum\_{e\_i \in E \setminus E'} 4^{i-1} + 2 \sum\_{e\_i \in E'} 4^{i-1} = k 4^{|E(G)|} + 2 \sum\_{e\_i \in E} 4^{i-1} = t. $$

If there is a subset $A$ of $S$ that sums to $t$, then $A$ contains exactly $k$ numbers from $\\{ n\_v : v \in V(G) \\}$ (as otherwise the most significant digits of $\sum\_{x \in A} x$ would not match those of $t$). Moreover, $V' = \\{v\_i : n\_i \in A \\}$ is a vertex cover for $G$.

To see this, pick any $e\_i = (u,v) \in E(G)$ and notice the $i$-th least significant digit of $t$ is $2$. Since, for $j=1,\dots, |E(G)|$, there are exactly $3$ numbers in $S$ whose $j$-th least significant digit is non-zero (namely $n\_{u'}$, $n\_{v'}$, and $m\_{e\_j}$, where $e\_j = (u', v')$), we have that in the summation $\sum\_{x \in A} x$ no carry occurs among the $|E(G)|$ least significant digits. We conclude that $A$ contains exactly two numbers from $\\{n\_u, n\_v, m\_e\\}$, implying that $u \in V'$ or $v \in V'$ (possibly both).

---

In your example graph, for $k=3$ you get the following (bold rows denote the elements of $A$ when $V'=\\{v\_1, v\_3, v\_4\\}$): $$ \begin{array}{|c|c|c|c|c|} \hline & & e\_1 & e\_2 & e\_3 & e\_4 \\ \hline \pmb{n\_{v\_1}} & \pmb{1} & \pmb{1}& \pmb{0}& \pmb{0}& \pmb{1}\\ \hline n\_{v\_2} & 1 & 1& 1& 0& 0\\ \hline \pmb{n\_{v\_3}} & \pmb{1} & \pmb{0} & \pmb{1} & \pmb{1} & \pmb{0}\\ \hline \pmb{n\_{v\_4}} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{1} & \pmb{1}\\ \hline \end{array} $$ $$ \begin{array}{|c|c|c|c|c|} \hline & & e\_1 & e\_2 & e\_3 & e\_4 \\ \hline \pmb{m\_{e\_1}} & \pmb{0} & \pmb{1} & \pmb{0} & \pmb{0} & \pmb{0} \\ \hline \pmb{m\_{e\_2}} & \pmb{0} & \pmb{0}& \pmb{1}& \pmb{0}& \pmb{0}\\ \hline m\_{e\_3} & 0 & 0& 0& 1& 0\\ \hline m\_{e\_4} & 0 & 0& 0& 0& 1\\ \hline \end{array} $$

$$ \begin{array}{|c|c|c|c|c|} \hline \phantom{m\_{e\_4}}& & e\_1 & e\_2 & e\_3 & e\_4 \\ \hline t & 3 & 2& 2& 2& 2\\ \hline \end{array} $$
> 3 votes

---
Tags: polynomial-time-reductions
---


# Question
Title: Prove that there is no computability reduction HP $\le$ $\Sigma$*
I tried to prove in negative way that there is computability reduction HP $\le$ $\Sigma$* and accept contradiction because of HP $\in$ RE and $\Sigma$* $\in$ R but it feels that is not strong argument.

There is a more solid way to prove it?

# Answer
Let us actually prove more: If $L$ is a language and $L \not\in \mathsf{R}$, then $L \not\le\_\mathrm{T} L'$ for any $L' \in \mathsf{R}$. (Here, $\le\_\mathrm{T}$ indicates a Turing reduction; this is synonymous with your notion of a "computability" reduction.) In other words, $\mathsf{R}$ is closed under Turing reductions.

Suppose towards a contradiction that such a reduction exists and is computed by a Turing machine $M$. Furthermore, let $M'$ be a decider for $L'$. Then there is a Turing machine which solves $L$, namely by directly simulating $M$, answering all of its oracle queries by simulating $M'$ on them, and, at the end, answering what $M$ does. This contradicts $L \not\in \textsf{R}$.

The case of the halting problem follows from it not being in $\mathsf{R}$ (since it is not even in $\mathsf{RE}$) and, naturally, $\Sigma^\ast \in \mathsf{R}$.

An aside: If you find the idea of classes closed under Turing reductions interesting, I suggest you look up the computation-theoretical notion of Turing degree. $\mathsf{R}$ would be the "base case" (i.e., degree zero) in that context.
> 3 votes

---
Tags: computability, reductions
---


# Question
Title: A* without heuristic more efficient than Dijkstra
I am using the module `networkx` to operate on graphs made from `OpenStreetMap`. I wanted to compare the shortest path algorithm to find which one is faster, and I compared Dijkstra and A\*. The problem is : A\* is most of the time faster than Dijkstra even though I didn't defined any heuristic function. I understood that A\* with $h=0$ was equivalent to Dijkstra, then why is it not the same time?

# Answer
It depends how you implement Dijkstra. The usual description of Dijkstra adds every vertex of the graph to the queue at the start, which is rather inefficient. A\* without a heuristic is often called "uniform cost search" (UCS) and the way it's described, you only add vertices to the queue when you discover them.

This means that, especially in sparse graphs (such as road maps, which are almost planar), UCS has a much lower memory footprint, which can make it considerably faster. Also, the various operations on the queue are much faster, since the queue is typically much shorter.

There's more information in Ariel Felner's paper *Dijkstra's algorithm versus uniform cost search or a case against Dijkstra's algorithm* (Proceedings of 4th International Symposium on Combinatorial Search, SoCS-2011, AAAI, 2011).

By the way, straight-line distance is probably a very good heuristic for A\* in your situation.
> 2 votes

# Answer
The best way to answer this is to use a profiler, but since I don't have your test cases I've looked around in the code and I'm fairly confident that it's due to differences in the way they produce the paths.

The networkx A\* implementation uses the standard technique of building a predecessor map and chaining backwards down it when the destination is reached. The Dijkstra implementation, on the other hand, produces full lists as it searches. It's wasting a lot of time copying lists to append an element to the end. This is partly a problem of using an inefficient return type, and partly a problem of failing to take advantage of special cases (specifically, using a multi-source multi-destination search to implement single-source single-destination), trading simplicity and non-duplication of code against performance.
> 1 votes

---
Tags: algorithms, algorithm-analysis, shortest-path, heuristics, a-star-search
---


# Question
Title: Generate triangular surface mesh of convex hull spanned by 8 points in 3D-Space
I am looking for a numerically efficient algorithm to get a triangular surface mesh of the convex hull given by 8 points in three-dimensional space.

For context, the use case is the following:

I have a numerical Simulation calculating the time evolution of a field with three components on a lattice. Say we have lattice coordinates $(i,j,k)$, then every lattice point $(i,j,k)$ has a field vector $(\phi\_1, \phi\_2 , \phi\_3)$ attached.

For relevant physics, I need to now take unit cells on my lattice, so the 8 corners of a little cube of my lattice. I take the field vectors $(\phi\_1, \phi\_2 , \phi\_3)$ of every corner of my unit cell and then interpret their convex hull as a closed volume in $\phi$-space, with $\phi$-space being the 3D space given by the $(\phi\_1,\phi\_2,\phi\_3)$ coordinates.

I am now interested if the volume spanned by these 8 points in $\phi$-space does the following things:

1. If it contains the origin, $(0 ,0 ,0 )$
2. If a Ray traveling from the origin in $(-1,0,0)$-direction pierces my given volume

The idea to evaluate both 1.) and 2.) at the same time is to decompose the surface of the convex hull into triangles. For a triangle in 3-Dimensional space, it is easy to evaluate whether it is pierced by my given Ray in $(-1,0,0)$ direction. I can then count how many triangles are pierced. If exactly two triangles are pierced (because of convexity), I know the cell satisfies condition 2.). If exactly one triangle is pierced, I know the origin has to lie inside my volume, that is condition 1.) is satisfied. Lastly, when no triangles are pierced, none of the above apply.

I think this approach is probably relatively fast. Speed is critical, because I have approximately $10^6 ... 10^9$ cells to evaluate per sweep across my lattice.

I'd be interested in any other approaches as well, though.

**Update:** So, I think possibly a 3D-Gift-Wrapping algorithm would atleast produce the required result, because it creates the convex hull by consecutively finding triangles on the surface? I will have to try that out tomorrow.

Can I do better than that in terms of efficiency?

# Answer
You don't actually need the convex hull. This is a simple linear programming instance: find $a\_i$ such that $$0 \le a\_i \\ \sum a\_i = 1 \\ \sum a\_i \phi\_{i, 1} \le 0 \\ \sum a\_i \phi\_{i, 2} = 0 \\ \sum a\_i \phi\_{i, 3} = 0$$ maximising $\sum a\_i \phi\_{i, 1}$. There are optimised LP solvers out there which you can use.
> 1 votes

---
Tags: algorithms
---


title: Reduce subset sum to 3SAT

text:
# Question
Title: Reduce subset sum to 3SAT
How to do it? I'm not asking the solution for the proof of why subset sum is NPC, but rather the opposite reduction

# Answer
The trick to reducing any NP problem to SAT is 1) writing a subroutine that checks the polynomially-sized certificate, 2) converting that routine to a circuit, and 3) flattening the circuit to CNF using the usual methods.

For example, to convert integer factorization to SAT, you would write a routine that multiplies two $n$-bit multipliers producing a 2$n$-bit result. Convert the routine to a circuit, then convert the circuit to CNF. Then add simple declarative CNF clauses that force the $2n$ output variables of the circuit to match the bits of the integer that you want to factor. The resulting CNF instance will be satisfiable only if a bit pattern for the two $n$-bit numbers exists that when multiplied together produces the 2$n$-bit number you want factored. (If you want trivial solutions excluded then you also need to add two extra CNF clauses that demand the most significant $n$-1 bits of each multiplier are not all zero.)

Subset sum is a bit more intricate. You need to write $n$ routines, each of which returns a particular one of the $n$ integers of the problem set or zero depending on the setting of a parameter bit. These routines feed input into another routine you wrote that sums all $n$ of its inputs and outputs the result. Convert all this into a circuit whose inputs are the parameter bits and whose outputs are the result of the addition routine. Convert the circuit to CNF. Add declarative CNF clauses that force the output variables of the adder routine to match the bits of $k$, the number a solution must sum to. The resulting CNF instance will be satisfiable only if there exists a bit pattern of the parameter bits selecting a subset of the problem set that sums up to $k$.
> 3 votes

# Answer
Usually, there are no intuitive or enlightening reductions between problems in different problem domains.

The proof that 3SAT is **NP**-complete is essentially by writing a formula that says "This **NP** Turing machine accepts this input." For other problems about logical formulas, you can often translate the formula into a 3SAT instance. Sometimes, you can express problems in other domains as 3CNF formulas: for example, you can do 3-colourability by having variables for each combination of "vertex $v$ has colour $q$" and write a formula that says that each vertex has exactly one colour and adjacent vertices have different colours.

However, usually, when you're faced with a problem from a completely different domain, you can't do much better than say that subset sum is in **NP** so it's decided by a Turing machine that I can express as a 3SAT instance. Perhaps you can come up with a less generic reduction, but it probably wouldn't teach you anything.
> 1 votes

---
Tags: np-complete, reductions
---


title: Analysis of an approximation claim

text:
# Question
Title: Analysis of an approximation claim
Consider the load balancing problem on two machines. Thus we want to distribute a set of $n$ jobs with processing times $t\_1,...,t\_n$ over two machines such that the makespan (maximum of the processing times of the two machines) is minimized. Professor Smart has designed an approximation algorithm *Alg* for this problem, and he claims that his algorithm is a $1.05$ approximation algorithm. We run *Alg* on a problem instance where the total size of all jobs is $200$, and *Alg* returns a solution whose makespan is $120$.

(i) Suppose that we know that all job sizes are at most $100$. Can we then conclude that professor Smart's claim is false?

(ii) Same question when all job sizes are at most $10$.

Let's talk about the case (i):

We know that $\sum{t\_i} = 200$ and that $t\_i \leq 100$. The makespan of the Algorithm $Alg = 120$, so $Alg \leq 1.05 * OPT$. We have no other information about the algorithm used. A lower bound would be $LB = max( \frac{\sum{t\_i}}{2}, max(t\_i)) = max (100,100) = 100$ so I would say for that particular instance we'd have $120 \leq 1.05 * 100 = 105$ which means the claim would be false.

Likewise for the case (ii).

My answer is marked as incorrect, and I am struggling to do the right analysis.

Can anyone help please ?

# Answer
You case (i) analysis is wrong, consider the input $60 + 60 + 60 + 20 = 200$. The most even split you can do is $60 + 60$ and $60 + 20$ which has a makespan of $120$, thus there is at least one feasible input for which professor Smart's algorithm returns the optimal result.

For case (ii) we know each job size is at most 10. Professor Smart's algorithm returns a makespan of $120$, which means one machine has a sum of jobs of $120$ and thus the other $200 - 120 = 80$.

But since we know each job has at most a size of $10$ we could move jobs over from the bigger instance to the smaller instance at least until the bigger instance hits $110$ and the smaller $90$ while being guaranteed that each job moved reduces the makespan. But $110 \cdot 1.05 \< 120$ thus the algorithm is not a $1.05$ approximation algorithm.
> 1 votes

---
Tags: approximation
---


title: Approximating a discrete distribution

text:
# Question
Title: Approximating a discrete distribution
I have a discrete distribution of reference. For the example let's say:

* P(X=1)=0.2
* P(X=2)=0.7
* P(X=3)=0.1

Now I am given `n` numbers, and I want to group (sum) those numbers into 3 bins and approximate as close as possible the above distribution in the sense of minimizing the sum of squared error. So let's say I have those numbers: 10, 25, 25 50 (total sum =100). So I want to group them into 3 bins, and ideally the sum of each bin would be 20, 70, 10 and that would perfectly match the distribution. Unfortunately that's not possible and the best here would be 25, 75 (50+25), 10. The error here is (25-20)²+(75-70)²+(10-10)²=50

What is the algorithm solving the general problem?

# Answer
The case where $\Pr(X=1)=\Pr(X=2)=\tfrac12$ is the subset sum problem, which is **NP**-complete so you won't find an efficient algorithm in general. Dynamic programming is probably the way to go.
> 1 votes

---
Tags: algorithms
---


title: find derivation trees for CFG

text:
# Question
Title: find derivation trees for CFG
I need to draw the derivation tree for $1-2-(3-4)\*5\*6$ from the grammar below. I want to know how many possible derivation trees are there from this grammar.

$$\begin{align}V\_n&=\\{expr,term,factor,number\\}\\ V\_t&= \\{(,),-,\*,0...9\\}\\ P&=\left \\{ \begin{aligned} expr&\to expr-expr\\;\mid\\;term\\ term&\to term\*factor\\;\mid\\;factor\\ factor&\to number \\;\mid\\; (expr) \\ number&\to 0\mid1\mid2\mid3\mid4\mid5\mid6\mid7\mid8\mid9 \end{aligned} \right \\}\\ S&=expr \end{align} $$

The possibilities that I can find are:

$$(1-2)-(((3-4)\*5)\*6)\\ 1-(2-( ((3-4)\*5) \*6))$$

Are there other possibilities?

# Answer
No, there are no other possibilities as far as I can see.

The ambiguity comes from the production rule $expr \rightarrow expr - expr$. This rule allows you to derive the expression in two different ways:

1. Derive $1$ from the left $expr$ and the rest from the right $expr$
2. Derive $1-2$ from the left $expr$ and the rest from the right $expr$

Some ideas that might help.

The precedences look ok to me; the lower the precedence the closer the operator should be to the root (in this case $expr$).
`-` has the lowest (derived from $expr$), `*` has a higher precedence (derived from a production after $expr$).
And the parentheses `(...)` have the highest (derived from a production after $term$).

The $term$ production rule is left associative, which helps avoid the ambiguity of associativity.

The $expr$ production rule is the problem as mentioned above. A solution to that would be similar to what you see for the $term$ production rule. Make it left associative.
> 0 votes

---
Tags: automata, context-free, regular-expressions, discrete-mathematics
---