# Question
Title: What data-structure is best suited for escape analysis?
I'm making a compiler using LLVM and LLVM's shadow-stack. I thought I might easy the load of the GC by using escape analysis and allocate some variables on the stack. Can I use my typed AST for this algorithm, or must I use a graph data-structure?

# Answer
> 5 votes
Escape analysis is a static analysis that determines whether the lifetime of data exceeds its static scope. As such, it is not really about stack vs heap allocation, just about lifetimes.

I don't think you can use your typed AST for escape analysis, because what you are analyzing is the *data flow* of the program. The appropriate structure for that is a graph, not a tree, because the data flow is cyclic. So what you want is to build a *control flow graph* (cfg), and perform data flow analysis on it.

Data flow analysis is a method or family of methods used for implementing a whole range of compiler optimizations. Among them, escape analysis. In it, you keep track of all objects, variables and references of your program in a *points-to graph*. Each object and variable is a node in the graph and, depending on how you implement it, references between them can either be nodes or edges.

For example, consider this Java method:

```
public Pair myMethod(Pair[] pairs) {
    Foo f = new Foo();
    Pair p1 = new Pair(1, 2);
    Pair p2 = new Pair(3, 4);
    p1.value = f;
    pairs[0] = p1;
    return new Pair(5, 6);
}

```

Escape analysis would work roughly like this:

* **Line 1**: An array of type `Pair` is passed into the method and a `Pair` is returned from it. Add two nodes to the graph, one labelled `pairs` and another labelled `RETURN` both with flagged `foreigner`.
* **Line 2**: An object called `f` is created in the `myMethod` method- Add a node labelled `f` with flag `native` to the graph.
* **Line 3-4**: Add two more `native` nodes labelled `p1` and `p2`.
* **Line 5**: The field `value` of `p1` is set to refer to `f`. Add an edge from node `p1` to `f`.
* **Line 6**: First element of the `pairs` array is set to refer to `p1`. Add an edge from `pairs` to `p1`.
* **Line 7**: A new pair object is returned. Add an anonymous `native` node representing the pair object to the graph. Then add an edge from the `RETURN` node to this anonymous node.

After this step, traverse the graph beginning at the `foreigner` nodes and flag all nodes visited as `foreigner`. It is exactly the same task as the mark step in a mark and sweep garbage collector.

Then all objects that weren't reached by the traversal retain their `native` flag and are eligible for stack allocation provided that the compiler can statically determine their sizes. The rest must be allocated on the heap.

I highly recommend watching the Youtube lectures of this professor:

The paper Escape analysis for Java also provides a fairly good description on how the algorithm works.

---
Tags: compilers
---


# Question
Title: Is 0-1 integer linear programming with only equality constraints NP-Hard?
We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it

$$\min c^T x \text{ s.t. } Ax = b \quad x\_i \in \\{0,1\\}\quad (i=1,2,...,n)$$

# Answer
> 3 votes
Consider the Maximum Independent Set problem ($\mathcal{NP}$-hard): given a graph $G=(V,E)$, find the maximum independent set in $G$, i.e., the subset of vertices $I \subseteq V$ such that every two vertices in $I$ are not adjacent $\forall v\_1,v\_2 \in I, (v\_1,v\_2) \notin E$.

This problem has a well known Integer programming formulation: let $x\_i$ be a binary variable for every $i \in V$ and equal one if $i \in I$. \begin{align} \max & \sum\limits\_{i=1}^n x\_i \\ \text{subject to} & \\ & x\_i + x\_j \leq 1 \text{ for all } (i,j) \in E \\ & x\_i \in \\{0,1\\} \text{ for all } i \in V \end{align}

If $|V| = n$, this problem has $n$ variables and $O(n^2)$ constraints.

To transform it to equality form (a.k.a. standard form) one might introduce slack variables for every constraint. Generally, if you have $Ax \<= b$ you can write $Ax + x\_s = b$ where $x\_s \geq 0$ and $x\_s$ are called slack variables.

It appears that for Independent Set slack variables are actually binary! Thus, you have the formulation \begin{align} \max & \sum\limits\_{i=1}^n x\_i \\ \text{subject to} & \\ & x\_i + x\_j +y\_{ij} = 1 \text{ for all } (i,j) \in E \\ & x\_i \in \\{0,1\\} \text{ for all } i \in V \\ & y\_{ij} \in \\{0,1\\} \text{ for all } i,j \in V \end{align}

This formulation exactly satisfies yours

> 0-1 integer linear programming with only equality constraints (ILPEQ)

Now, you have a basic reduction argument. Suppose, you can solve ILPEQ fast, that means you can solve independent set fast, but it is known to be $\mathcal{NP}$-hard, so ILPEQ is also $\mathcal{NP}$-hard. The formal argument as well as checking that this is in fact a polynomial reduction I leave to the reader.

---
Tags: complexity-theory, np-hard, linear-programming, integer-programming
---


# Question
Title: NP-hardness of finding a subset of vertices in a vertex-weighted graph
This is task from the German IT contest ("Bundeswettbewerb Informatik"), but since the deadline is past, asking this question is no cheating.

Given a vertex-weighted, directed graph $G=(V, E)$ and values $c\_v$, find a subset of nodes $V\_{res}\subseteq V$ that maximizes $$\sum\_{v \in V\_{res}} c\_v$$ subject to $$\forall (u,v) \in E: u \in V\_{res} \implies v \in V\_{res}$$ Is this problem NP-hard?

I could prove that the problem is in P if every node has either no parents or no children by showing that in this case, it can be solved by Vertex Cover on bipartite graphs, but I failed in finding a reduction that proofes the NP-hardness of the original problem.

Can somebody give me a hint how to do this?

PS: In the contest, the task was only to find an algorithm that solves this problem, the original (German) definition is task 1 of this document: http://www.bundeswettbewerb-informatik.de/fileadmin/templates/bwinf/aufgaben/bwinf35/aufgaben352.pdf

# Answer
> 1 votes
The problem is polynomial-time solvable, suggested in Lemma 1 of the paper Computational Complexity of Some Maximum Average Weight Problems with Precedence Constraints.

Basically the idea is to write a linear program on variables $x\_i\in\[0,1\]$, where $x\_u-x\_v\leq 0$ if $(u,v)\in E$. The signed adjacency matrix is totally unimodular, so we can compute the integral optimum.

---
Tags: complexity-theory, reductions, np-hard
---


# Question
Title: Solving this recurrence: T(n) = 9 T(n/2) + n^3 lg n
Would it be possible to use the master theorem to solve the following recurrence?

T(n) = 9 T(n/2) + n^3 lg n

This recurrence hasn't been mentioned before in any of the questions on StackOverflow.

Best,

# Answer
You should use the Master Theorem to solve that kind of recurrence relation:

The general form of the Master Theorem is: $T(n) = a T(n/b) + O(n^d)$ or $T(n) = a T(n/b) + f(n)$, where $f(n)$ can take multiple forms (I'll let you dive into that).

That being said, let us begin solving the recurrence relation, step by step:

$$T(n) = 9 T(n/2) + n^3 \lg n$$

Step 1: Identify **a**, **b** and **d**. In your relation $a = 9$, $b = 2$. We need to work a little harder to find $d$, as you can see. The function $f(n)$ is of the form $n^\mathbf{d} \log^k n$. So $f(n) = O(n^3 \lg n)$, thus $\mathbf{d} = 3$.

Step 2: Analyze the **a, b, d** output of your recurrence relation and decide which of the following cases is valid:

I) $a = b^d$, then $T(n) = O(n^d \log^{k+1} n)$;

II) $a \< b^d$, then $T(n) = O(n^d)$;

III) $a \> b^d$, then $T(n) = O(n^{\log\_b a})$.

In your situation, we have $9 \> 2^3$, thus $T(n) = O(n^{\log\_29}) = O(n^{3.17})$.

As you can see, this is a simple exercise on asymptotic notation. Next time try to give more insight on your thoughts regarding your problems, don't just post your homework blankly.
> 2 votes

---
Tags: recurrence-relation
---


# Question
Title: Formal model of execution for Java (or general imperative language)
I'm trying to prove some statements about execution in Java programs under some heavy restrictions (basically I have a conjecture that if two methods satisfy a set of constraints for a given input then the are they equivalent - i.e., that return value and state after execution are identical). To prove this I'm looking for some sort of formalism that will let me talk about this.

I'm familiar with the operational semantics of functional languages and I could possibly translate for loops/while loops to recursive functions... I'd rather not do this and it would be nice to have some machinery so I could stay in imperative land.

More specifically, I want to reason about the *state* of a method at the *k*th step of execution. This includes global state:

* Calls like `this.field = 2` update our class state
* Calls modifying parameters update state outside of our method:
    + `myParam.setFoo(...)`
    + `myParam.x = y`
* Calls to static methods
    + `Blah.static_side_effects()`

I am assuming that all of this is *deterministic*. That is, I want to formalize the assumption that if any of these global updates to state occur in two methods, both of whose global and local execution states are identical, then the new state will also be identical - that each step of computation is determined precisely by global state and local state. This obviously precludes RNGs and parallelism (but I may deal with this later...).

Any ideas or sources on how I could approach this? My only thought is to treat methods as a list of statements and try to describe a statements semantics formally.

If possible I'd love to do this at the Java language level rather than the JVM level. This may not be feasible but my goal for now is to make some reasonable assumptions about my operational semantics and then take it from there.

Oh, one final note - any suggestions on how I can improve this question would be greatly appreciated. I'm kind of flailing around trying to find the right language to ask the question and if I'm abusing terminology (like local/global execution state...) I'd love to correct this.

# Answer
Featherweight Java is quite highly regarded in the PL community. But if that doesn't suit your needs, here's a general approach to modelling:

* Formalize your language's AST into expressions and statements
* Write a semantics for expressions and statements. Your semantics will need:
    + an evaluation relation, relating expression-state pairs $(e,\sigma)$ to an evaluated expressions with updated state $(e', \sigma')$,
    + an execution relation, relating statement-state pairs $(s, \sigma)$ to output states $\sigma$.
* These will be mutually recursive on each other, and can be a big or small-step semantics, depending on your particular need. Big step is simpler, but worse at modeling non-terminating executions.

This basic structure will get you pretty far. To model Java, you probably want to structure your state set hierarchically, around specific objects, but the basic principles are the same. You'll also want to model dynamic dispatch, so it probably makes sense to transform class methods into functions taking an explicit "this" argument.

An axiomatic semantics i.e. Hoare triples, which define a logic of pre- and post-conditions for statements to model imperative programs. I don't know how these relate to OOP, but I'm sure someone has tried in the 50 years they've been around.

You might also be interested in Software Foundations. It's oriented at reasoning about imperative languages in the Coq theorem prover, but it gives an excellent overview of formal semantics.
> 7 votes

# Answer
There is an (operational) semantics for Java 1.4 formulated in the $\mathbb{K}$ framework. Associated to this framework is a proof system called Matching Logic. While that page describes a prototype implementation, it seems that the functionality is being incorporated into the $\mathbb{K}$ framework tools themselves as `kprover`. Unfortunately, it seems the framework is in the middle of being updated, and getting the framework to build and work appropriately is a bit of a chore, and I'm not really sure how practical and/or functional `kprover` currently is. You could, however, manually prove things referencing the operational semantics (and also using the Matching Logic proof system if you like). The paper describing the Java semantics, K-Java: A Complete Semantics of Java, references some other systems that are less complete, but may be complete enough for your purposes. That said, they may well not be geared toward proving properties about Java programs. Indeed, in the paper, the semantics is being used for model checking rather than correctness proofs.

This is an answer if you want a high degree of confidence that the actual Java code behaves as you intend. If the goal is more verifying the algorithm than the specific realization into Java, then this is likely overkill. That said, you could easily formalize a simple imperative language in $\mathbb{K}$ if you only need basic imperative/OO features. Indeed, this is done as an exercise in the $\mathbb{K}$ framework tutorial. In fact, if you can reformulate your problem into the fragment of C the Matching Logic prototype supports, you could possibly use that as-is.
> 8 votes

---
Tags: programming-languages, semantics, java, operational-semantics
---


title: Implementing a Compiler with Macros

text:
# Question
Title: Implementing a Compiler with Macros
I've been thinking about embedded languages (domain-specific or otherwise), and in particular the approach where we define a datatype to represent terms of the embedded language, e.g. (in Haskell):

```
data Expr = Numeral Int
          | Apply Expr Expr
          | Lambda String Expr
          | Var String
          | ...

```

We then provide a library of functions which allow us to write programs, like `plus 10 5`, but when "run" they don't actually produce the 'answer' (`15`), they instead produce a representation of that program in the embedded language, like `Apply (Apply (Var "plus") (Numeral 10)) (Numeral 5)`.

My question is: can we implement a general-purpose, high-level programming language, like Haskell, such that the "compiler" is actually a set of library functions, "compiling" is just interpreting our program, and the resulting value is machine code (or Javascript, or whatever our compilation target is).

Another way to think about this: in Lisp-like languages, we can create new language constructs using macros, which get "expanded" into other macro calls and eventually down to "special forms" implemented with an interpreter/compiler. From this perspective, my question would be: is it possible to make a Lisp where the only special forms are (representations of) machine code, and the whole "user-facing" language (function definition, calling, branching, etc.) is just a set of macros? In such a system, macro-expanding a program would result in a compiled binary. I'm willing to ignore the "dynamic"/reflection/etc. features found in "real" Lisps.

Another way to think about this: assembly languages get macro-expanded into machine code; are there any any assemblers which do/could provide "high-level" features, like higher-order functions, pattern-matching, garbage collection or linear types, etc.?

Is there some insurmountable difficulty with this (e.g. linking?)? Is it something that's been done? Things which seem related, but slightly different:

* Forth seems to 'bootstrap' itself in a similar way when executed, but doesn't (in my limited experience) seem to "compile down" to a 'self-contained binary'; rather, it either runs "dynamically" (i.e. the code we write gets executed 'as is'), or it gets compiled into a form with an embedded interpreter.
* The IO approach of Haskell, Idris, etc. is similar, in that Haskell can be seen as a macro language for constructing "IO programs", but it's not quite the same: our Haskell code isn't "fully expanded" by the compiler: we can write pure functions which only get executed at runtime, and even when things do get inlined/fused/etc. it's because of 'compiler magic' rather than the language's semantics.
* The Nix language is purely functional and turing complete, and its programs evaluate to give "derivations", containing an environment and build script for some 'package'. Derivations can, optionally, be sent to the `nix-build` tool for execution. Could we make a similar language which evaluates to give a "machine code" (or "unlinked assembly") value, which we can subsequently pass to an assembler/linker/etc.?

In such a system, our program would be instructions for the "compiler" (the interpreter we run to get the resulting binary), hence we could implement things like instrumentation, optimisation, cross-compiling, etc. as library functions, rather than having to update some separate, monolithic program like GHC.

# Answer
> 4 votes
Yes and no.

Yes, you *could* structure a compiler this way, but most of the benefits you are hoping for would not materialize. There may be some benefits, such as a powerful compile-time meta-language. There are also costs like a complete loss of the ability to make meaningful guarantees about code that isn't completely self-contained (e.g. takes in objects or higher-order functions as parameters).

Felleisen defines a notion of "macro expressiveness" in his 1991 paper On the expressive power of programming languages. Basically, a programming language feature that is macro-expressible is one that can be expressed by a localized and delimited syntactic transformation. With this notion you can partially compare the "expressive power" of different language features: a language feature is at least as expressive as another feature if the second feature is macro-expressible in a language with the first feature (relative to a common base language).

If a feature is not macro expressible relative some language, that means to implement it requires non-local (often global) transformations. This may be done in a brute-force way as a transformation of the whole program, but it also could be done by having a bunch of smaller macros that coordinate to maintain invariants. Either way, the point is if I want to extend your language with a macro of my own creation that operates at the "base" level (machine code in your idea), then my macros need to maintain all the invariants your macros rely upon or else I'll break the "high-level language". It's possible that these invariants are too constraining for what I want to do. If I proceed anyway, rewriting parts of the language so its compatible with my new macros, the end result is that I haven't extended your language at all, I've made a *new, incompatible* language. It's quite likely that I will either not be able to use your language's existing standard library or that I will need to reimplement it so that it takes advantage of the new features. Even if I can make something that's compatible with the old language, if what I'm doing is not macro-expressible in terms of the "high-level language" (which presumably it isn't or else I wouldn't be accessing the base language) then *my* macros are going to have their own invariants that need to be maintained across usages and/or will be making assumptions about the low-level details. Now imagine I'm not making an application but a library. Now imagine you want to use my library and another library that has its own set of macros and invariants but don't know about each other.

I've discussed this quite extensively at LtU. See this comment thread and the comment threads it references. I even briefly touch on the thought experiment of assembly + macros in this comment (from 2006). This comment (a bit into one of the threads referenced by the first comment) may be a relatively coherent explanation with examples.

In a nutshell, separately adding two features which are not macro-expressible to a common language will typically produce two incompatible languages. The less expressive the common language is, the more often this will occur.

---
Tags: compilers, interpreters, code-generation, meta-programming
---


# Question
Title: In programming languages, generally we do not distinguish relations and functions. Is there a better way to deal with these two concepts?
When we write a mathematical formula, the rule $a=42$ (when we say let $a=42$) and testing them (when we write something like $\ldots \mathrm{if} x=42$) is written in a same equal sign. I think that both of them are representing some relation. However, while programming, we write `=` for the first circumstance and `==` for the second, and `==` is actually the infix representation of the equivalent testing function. Should they be treated as the same thing?

---

Previous question:

*Are programming languages confounding relations and functions?*

p.s. I have been asking this a few hours ago on StackOverflow, but they told me that it was on a wrong venue.

For example, the equivalent sign `=` has a lot of meanings, including returning a boolean value that tests whether to expressions are equal to some extent, setting up a rule that both side are equal, and assign the right side to the left side. And notations such as `<` and `||` are generally parsed as boolean operators. What's more, they do not distinguish predicates and boolean functions.

In my opinion, this is not a very elegant way to treat the 'rules'. I think notations like  should be thought to be a relation, which means `a≤b` implies $(a,b)\in R\_\leq$, where $R\_\leq \subset S^2$ and $S$ is the domain of $a$ and $b$. Mathematically,  is not a function at all (If it is, it should be something maps from a subset of $S^2$ to $\\{True, False\\}$). It is just representing some rules.

However, while programming, we generally do not realize the difference between them. We may consider `k = a < b` as a simpler way to write something like `k = True for a<b, False otherwise`. However, I believe that this makes things confusing in some circumstances, for example, the use of `=`.

I have seen a lot of imperative and functional language that do not seem to respect these differences. Am I correct in this point of view? Is there a better way to solve this?

# Answer
> 2 votes
Let $A$ be any set. Then, its powerset $\mathcal{P}(A)$ is isomorphic to the function space $A\to \mathbb{B}$ where $\mathbb{B}=\\{\sf true, false\\}$.

Indeed, the isomorphism is given by mapping each subset to its own characteristic function.

$$ \begin{array}{lcl} \mathcal P A & \leftrightarrow & (A \to \mathbb B) \\ X & \mapsto & \lambda a. {\sf if}\ a\in X\ {\sf then\ true\ else\ false} \\ \\{a|g(a)={\sf true}\\} & \leftarrow\\!\shortmid & g \end{array} $$

Since relations are sets of pairs, relations too can be seen as binary functions whose codomain is $\mathbb B$.

In most programming languages, as you realized, we don't really find propositions, sets, or relations, but we instead find their isomorphic counterparts: booleans, unary boolean functions, binary (or more) boolean functions.

This choice is mostly suggested by the fact that everything we compute ultimately is represented by a few bits. It is therefore very efficient for a computer to represent the truth values associated to propositions. Further, it is convenient to be able to write e.g. `b = b or (y < 5)` without using a conditional. (Actually, using a conditional for that usually reveals that the programmer does not understand that boolean expressions are indeed expressions, and not special syntax that is relegated to conditional or loop guards. This phenomenon also shows up in the infamous `if b==true ...` where the programmer often thought that we have to use at least one boolean operator in the guard, since we usually need that.)

In programming languages, there are some theoretical contexts where we do separate propositions from booleans, though. For instance, in the calculus of inductive constructions, as implemented in `Coq`, we find a `Prop` type for propositions, and a `bool` type for booleans. Very roughly, this allows the programmer to deal with propositions that can not be automatically checked by the computer, e.g. $\forall a,b,c\in\mathbb N.\ (a+b)\cdot c = a\cdot c + b\cdot c$ is a `Prop`. Even if the computer can not check them, we can still mathematically prove them. Note that we can not turn a `Prop` into its `bool` truth value since we have no way to check $\forall n$ or $\exists n$. (Actually, there's no such a thing as its "truth value" since the logic is constructive, but I'll be silent about this.) By comparison, we get two forms of `n < 4` comparisons: one which is a `Prop` and can be used in logic, and another one which is a `bool` and can be used in programs.

---
Tags: programming-languages
---


# Question
Title: How to get the best factor for abstract algorithm that has expected cost?!
> 1.10 Let A be an algorithm for minimization NP-optimization problem such that the expected cost of the solution produced by A is at most $\alpha OPT$, for a constant $\alpha\>1$. What is the best approximation guarantee you can establish for this problem using algorithm A?

Hint: A guarantee of $2\alpha-1$ follows easily. to be honest, I don't really understand the question good. So usually when we want an approximation factor we take the ratio between solution of algorithm A and OPT of problem. could you explain the problem in other way! and how we get factor of $2\alpha-1$. Suppose I want to use Markov's bound, since the information we know is expected value. Thus, I would get $\alpha OPT/a$ for $a\>0$. I don't see any logic here! I would like any help in terms of explanation!

Thank you!

# Answer
> 2 votes
I don't know what the author of the question means with "*approximation guarantee*" (is it defined earlier in the book?), so I am just going to tell you what you can derive from the information that's given.

If the expected value of the algorithm is $\mathbb{E}=v$, then the probability that the algorithm outputs a value larger than $kv$ is at most $\frac{1}{k}$, from Markov's bound, if the cost function never goes negative. So if you run the algorithm $t$ times, then the probability that the minimum value among all trials is greater than $kv$, is at most $k^{-t}$ (why? because the trials are independent).

There are no hard guarantees until there is more information.

---
Tags: algorithms, approximation
---


# Question
Title: Shortest path between all pairs of vertices in cyclic undirected weighted sparse graph
Is there any efficient algorithm to find shortest distance between **all pairs of vertices**?

The graph is:

* Cyclic
* Sparse (each vertex has either 2 or 3 edge)
* undirected(bidirectional)
* weighted
* non-negative

Since Floyd-Warshall algorithm and Johnson's algorithm are best for finding shortest path for every pairs but:

* Johnson's algorithm works on directed
* Floyd-Warshall algorithm is best for dense graphs

I couldn't find any algo that is efficient for above graph conditions.

# Answer
Mikkel Thorup's paper Undirected Single-Source Shortest Paths with Positive Integer Weights in Linear Time shows an $O(m)$ time algorithm for single-source shortest paths on undirected weighted graphs. That immediately implies an $O(mn)$ time algorithm for all pair shortest paths, which is the optimal $O(n^2)$ in your scenario.
> 3 votes

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


# Question
Title: Find all pairs (i, j), such that i + (i+1) + (i+2) + ... + j = n
We have give positive integer $n$, and we want to find all the pairs $(i, j), i\leq j$ such that: $$i + (i+1) +(i+2)+(i+3)+ \dots + j = n$$

Clearly we can try all possible pairs in $O(N^2)$, but that is pretty slow. Here is my observation.

We already know that the sum of numbers from $1$ to $n$ equals $\frac{n\cdot(n+1)}{2}$. Using simple math we can show that the sum of the numbers in the range from $i$ to $j$ equals $\frac{(j-i+1)\cdot(i+j)}{2}$. If we fix number $i$ using this formula we can find $j$, and check if it is positive integer, but this is $O(N)$, can we go faster?

# Answer
Another algorithm:

Find all factorizations of $2n$ into a product of two integers, say $2n=r \times s$ with $r \le s$. Then find $i,j$ such that $j-i+1=r$ and $i+j=s$, i.e., $i=(s-r+1)/2$ and $j=(s+r-1)/2$. Check whether $i,j$ are positive. If they are, output this pair $i,j$. Do this for each way of expressing $2n$ as the product $2n=r \times s$.

How do you find all factorizations of $2n$ into two integers? First factor $2n$ into a product of prime powers, say

$$2n = \prod p\_i^{e\_i}.$$

Next, for each $c\_i$ with $0 \le c\_i \le e\_i$, you can let $r = \prod p\_i^{c\_i}$ and $s = \prod p\_i^{e\_i-c\_i}$. So in this way you can enumerate all such factorizations. There will be $\prod (1+e\_i)$ of them.

The running time for this is significantly faster than $O(n)$. In the worst case the number of such factorizations can be no larger than $O(n^{1/2})$, so the worst-case running time of this method is $O(n^{1/2})$ -- already a significant speedup over Hendrik Jan's elegant answer. Even better, in the average case, the number of such factorizations is far smaller than $n$, exponentially smaller, making this much faster. Often, the dominant cost will be the cost to factor $2n$, which can be done in subexponential time using standard algorithms.
> 3 votes

# Answer
Set $i$ and $j$ to $1$. Set $\mathrm{sum}$ to $0$.

Repeat:

If $\mathrm{sum} = n$ we have a pair, if $\mathrm{sum} \< n$ increment $j$ and adjust $\mathrm{sum}$, if $\mathrm{sum} \> n$ increment $i$ and adjust $\mathrm{sum}$.
> 1 votes

---
Tags: algorithms, integers, searching
---


title: Prove or disprove the given equivalence

text:
# Question
Title: Prove or disprove the given equivalence
f(n) = n/100 = Ω(n) . I am new at proving asymptotic notations , especially at big-Ω. That's why I even didnt start the beginning myself. I tried to prove myself as looking at other proofs and searched on the internet to find same question but I couldnt find. I dont think so this question is a duplicate of another which was asked here. Thanks for helps.

# Answer
I assume $n$ takes only positive values. By the definition of Big-Omega you could prove it by showing the following

$$\lim\_{n \rightarrow \infty}\frac{\frac{n}{100}}{n} \>0$$

The rest is a simple exercise.
> 0 votes

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


# Question
Title: Depth of a leaf in a prefix tree (Huffman Coding)
So, regarding Huffman Coding we know that the optimal way of "storing" it is using a full binary tree (where all nodes have either 0 or 2 children). All leaves are the symbols $i$ of the alphabet we want to encode (all $i$ have a frequency of appearance$f\_i$) and if we consider the freq. $f\_i$ of each leaf (freq. of that character) then the freq. of a node is the sum of the frequencies of its children, therefore the root has $f\_i = 100$ or $f\_i = 1$.

Visual example (taken from *Introduction to Algorithms*) because I'm not really good at explaining this stuff:

Now I want to prove that the depth of a leaf (a character) in this prefix tree is $O(\log\_{2}{(1/f\_I))}$, where $f\_i$ is the freq. of the character $i$.

I've tried by induction, where the base case would be for $\log\_{2}{(1/1) = 0 }$ and indeed the depth of the root is 0. But I don't know how to proceed.

I've been thinking about how in a complete binary tree the depth of a leaf is $\log\_{2}{n}$ with n being the number of nodes in that level (I'm not 100% sure about this) and how de depth of a character i in the prefix tree = length of the binary code (for example depth of d is 3 and its coding is 111) but I can't see how I could use those two things (if they are even useful).

What do you think about it? I don't know how to approach it :(

Btw thanks for your time and have a nice day!

# Answer
> 3 votes
Consider a symbol $\sigma$ whose frequency is $f$. During the course of Huffman's algorithm, $\sigma$ is matched with other nodes, and the depth of $\sigma$ is the number of times this happens.

At the first time that $\sigma$ is matched, it is either the symbol with smallest frequency or with second smallest frequency. In the former case, it is merged into a new symbol whose frequency is at least $2f$. In the latter case, after $\sigma$ is merged with the symbol of smallest frequency, all symbols have frequency at least $f$, and so the next time that it is merged, the merged symbol will have frequency at least $2f$.

Summarizing, it takes at most two mergings to double the frequency of a symbol. If its original frequency is $f$, then this shows that the depth of $f$ is at most $2\lceil \log\_2(1/f) \rceil = O(\log(1/f))$.

---
Tags: algorithms, trees
---


title: Optimal Partition of Book Chapters

text:
# Question
Title: Optimal Partition of Book Chapters
Suppose you want to read a book with $n$ chapters, and chapter $i$ has $a\_i$ pages. Now you want to read the entire book in $d$ days. But there are two restrictions:

* by the end of each day, you cannot be in the middle of a chapter.
* You must read the chapters in order.

You also want to minimize the maximum number of pages read in a single day.

Now let's consider the brute force algorithm: look at every possible way of dividing the chapters into $d$ days, and compute the maximum number of pages read in a single day. There are $\binom{n+d-1}{n}$ ways to divide the chapters up (using stars and bars) and you must check the number of pages read in each day, ultimately by doing $n$ operations. So this algorithm takes $O\left(n\binom{n+d-1}n\right)$ time, which is pretty bad, but I can't think of how to improve it.

Imagine an analogous decision problem:

> Given a book with $n$ chapters, is it possible to read it in $d$ days such that you never read more than $k$ pages in a single day without violating the restrictions?

The decision problem seems to have a really easy greedy solution: Each day, read as many chapters as you can without exceeding $k$ pages. If you're done with the book after $d$ days, the answer is yes. Otherwise, the answer is no. This takes $O(n)$ time.

It seems weird that the decision problem would have such a simple solution but the original one doesn't. Can anyone think of how to do better than the brute force algorithm for the original problem?

# Answer
Your brute force solution is far from optimal. One improvement is to use dynamic programming. For every $i,j$, determine the minimal maximum number of pages per day when reading the first $i$ chapters in $j$ days. Implemented naively, this leads to an $O(n^2d)$ solution, though you might be able to improve this to $O(nd)$ using a smart implementation.

A perhaps better solution is to use binary search. You state that it is easy to determine whether a certain maximum number of pages can be achieved. To find the minimum number that can be achieved, use binary search with the decision algorithm as an oracle. The running time in principle depends on the total number of pages, but in fact there are only $n^2$ different possible answers, and this leads to an $O(n^2)$ algorithm, which can probably be improved to $O(n\log n)$ with some additional ideas.
> 2 votes

# Answer
If you have a limit of k pages per day, then you can easily check whether you can read the book in d days using the greedy reading strategy.

Let T be the total number of pages. When d = 1, k = T is obviously the best solution, so assume d ≥ 2. Let C be the number of pages in the longest chapter.

A lower bound for k is max (C, ceil (T / d)). Let d' = floor (d / 2), then an upper bound is max (C, ceil (T / d')): That is because in any two consecutive days, we will be reading more than k pages, or we could have read those pages in one day. There are d' pairs of consecutive days, so we can read more than k * d' pages in 2d' days, therefore T pages in d days.

If C ≥ ceil (T / d') then k = C is the smallest possible value for k. Otherwise, since checking whether k is large enough or not takes O (n), binary search will find the smallest possible k in O (n log (T / d')) = O (n log (T / d)) operations.

A small improvement: During the binary search, if the greedy algorithm determines that reading up to k pages per day works, you can check what the largest number k' of pages read in one day actually was, and obviously choosing k' instead of k will also work. If reading up to k pages per day didn't work, you can determine the smallest k' where you could have read more pages on one day, and use k' as a lower bound. This should help if T is excessively large.

PS. You can probably a better execution time on average. Checking whether k pages per day is enough can be done in O (n) where n is the number of chapters. But if k' is close to k, and n is significantly larger than d, then we should be able to check k' by modifying the result of the greedy algorithm for k in time that is closer to d than to n.
> 0 votes

---
Tags: algorithms, optimization, greedy-algorithms
---


# Question
Title: Are finite state transducers and Mealy machines the same machines?
There are several versions of the definitions of the FST and the Mealy machine. Some of the definitions are almost same. Some have a little differences. But it seems that they both are a kind of DFA with an output function $G \colon \Sigma \times Q \rightarrow \Gamma \times Q$, where $\Sigma$ is the input alphabet and $\Gamma$ is the output alphabet.

I'm not sure about the differences between them.

Are they the same machines? Why is there two different names?

BTW, I found that there is not the set of final states in the definition of Mealy machines or Moore machines. On the other hand, final states do exist in the definition of FST, although Mealy machine is one type of FST. Does it mean that final state is not important when we are talking about the Mealy machines?

# Answer
> 1 votes
Mealy machine (*by G. Mealy*) is a deterministic finite state transducer with output associated with transition (edge) instead of state. It could handle multiple inputs and multiple outputs but by definition cannot be non-deterministic. According to definition it must be defined for all possible combinations of states and inputs.

Finite State Transducer is a generalization of Finite State Machine (*M. Rabin, D. Scott*) which can be both deterministic and non-deterministic. The output is associated with states, not all combinations of states and input must be present. Not all NFST can be determinized.

The computational power of both is equal in the Chomsky hierarchy, but there exist machines that cannot be expressed by other type. In special transduction hierarchy FST is higher than Mealy.
There are extensions to create nondeterministic Mealy machines, but nondeterminism for transducers is not really exploited, it would generate the family of outputs when one is really needed, unless it was the goal then NFST wins here.

From physical point of view it makes difference, Mealy equivalent machines are shifted in time, but considering only the result it does not matter.

---
Tags: automata, finite-automata, computation-models, transducers
---


# Question
Title: Summed-area table for circular range queries
A summed-area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a *rectangular* subset of a grid \[Wikipedia\]. Is there any algorithm for quickly and efficiently generating the sum of values in a *circular* subset of a grid?

# Answer
The best way is to approximate circle with hexagon or octagon as desciribed in expired patent US 6507676 B1. Further improvement is to add rectangles to octagon to get more circular shape or like harold proposed cover the whole circle with rectangles. Unfortunately this defies the core efficiency of summed area table.
The naive way would be to use e.g. Bresenham circle algorithm and sum consecutive rectangles, which by the way is still big speed up, proportional to circle size. The best way is to inscribe square and add rectangles to get finer results. This is illustrated here.

*Picture taken from http://yehar.com/*

There is no possibility of creating SAT especially for circle even leaving jagged border, simple proof is from impossibility of tesselating space by circles.
> 4 votes

---
Tags: computational-geometry, image-processing
---


# Question
Title: Defining a predicate on the structure of a string
I have the following homework question. (For a bit of context - the study unit is Formal Languages and Automata).

> Define the predicate $\mathrm{pre}(s,t)$ over $s, t\in\Sigma^\*$ by induction *on the structure of $s$* such that it satisfies the following conditions: $$\mathrm{pre}(s,t) = \begin{cases} \mathsf{true} & \text{if there exists $s'\in\Sigma^\*$ such that $s \mathbin{+\\!\\!+} s' = t$} \\ \mathsf{false} & \text{otherwise}. \end{cases}$$

Now I have considered two definitions so far. However they both assume things about the structure of $t$, and the way the question is worded implies that we can only assume things on the structure of $s$ (in a recursive way).

The definition is: $$ \mathrm{pre}(\epsilon,t) := \mathsf{true}\\ \mathrm{pre}(\alpha.s,\beta.t) := (\alpha = \beta) \wedge \mathrm{pre}(s,t), $$ and the second, which avoids having $\beta.t$ in the argument: $$ \mathrm{pre}(\epsilon,t) := \mathsf{true}\\ \mathrm{pre}(\alpha.s,t) := (\alpha =\mathrm{head}(t)) \wedge \mathrm{pre}(s,\mathrm{tail}(t)), $$ where I would then define $\mathrm{head}$ and $\mathrm{tail}$ in a recursive way on $\alpha.s\in\Sigma^\*$ (so essentially, this does the same thing).

Is there a way this can be done without assuming anything about the structure of $t$?

# Answer
No, in the recursive case you need to take the first symbol out of $t$, so you need at that point to unfold the structure of $t$.

Note that, as in functional programming, the functions $head$ and $tail$ should be used with great care since they are not total: $head(\epsilon)$ and $tail(\epsilon)$ are undefined. Hence, remember to require $t\neq\epsilon$ every time you use $head(t)$ or $tail(t)$, and to handle the $\epsilon$ case elsewhere.

I would tend to use your first solution, which needs a similar fix.

$$ \begin{array}{l} {\sf pre}(\epsilon,t):= \sf true \\ {\sf pre}(\alpha.s,\epsilon):=\sf false \\ {\sf pre}(\alpha.s,\beta.t):=(\alpha=\beta)\land {\sf pre}(s,t) \end{array} $$

In this way you are not assuming that the second argument is non empty. You are still assuming that it is a word, but that's needed.
> 0 votes

---
Tags: formal-languages, automata, logic, strings
---


# Question
Title: Creating regular expression with sub sequences of strings
I am creating a program which searches for particular types of strings. The alphabet of these strings are in $\\{a, b, c\\}$, for which every sub string of length 3 contains exactly $c$. Some strings that follow these constraints are:

$cabcbbca$, $cbb$ and $acaacb$

And strings that don't follow the constraints are:

$aaac$, $ccc$ and $cbcaac$

From this, I can see that a regular expression might need to be made to search for strings that follow the constraints.

I have tried hard coding some regular expressions such as:

$((a \cup b)(a \cup b)c)^\*$, which would cover strings like $abcabcabc$, but will obviously not work for all strings, as their are many combinations the strings could be in.

I'm not sure how I could create a general regular expression that could strictly follow any sub string of length 3 to contain exactly one $c$. Any help would be appreciated.

# Answer
> 2 votes
The following regular language should match your specification. I've used a slightly different notation than yours, denoting $(a \cup b)$ as $\\{a,b\\}$.

$\mathcal{L} = c \cup c \\{a,b\\} \cup c \\{a,b\\} \\{a,b\\} \cup \\{a,b\\} \cup \\{a,b\\}\\{a,b\\} \cup \left( ((\\{a,b\\}c) \cup c)? (\\{a,b\\}\\{a,b\\}c)\*\right)$

$?$ denotes repetition zero or one time, and $\*$ repetition zero or more times.

It can be written in a more compact representation as: $\mathcal{L} = c\\{a,b\\}\\{a,b\\} \cup \\{a,b\\}?c?\\{a,b\\}? \cup (\\{a,b\\}?\\{a,b\\}?c)?(\\{a,b\\}\\{a,b\\}c)\* $

---
Tags: regular-expressions, strings
---


# Question
Title: Was multiple inheritance ever implemented by adding redundant data members?
In discussions about why most languages which implement inheritance only implement single-inheritance, the question of the precise semantics of overlaps often comes up, and having redundant data members is sometimes given as an example semantic that would be undesirable. Note that this semantic effectively implements inheritance with composition.

Given that "prefer composition over inheritance" seems to be the current prevailing wisdom, having overlaps be redundant doesn't sound as bad as it once did.

So my question is:

Are there any programming languages which implemented multiple inheritance by adding redundant data members? How did that turn out, if so?

# Answer
It does not matter how you implement multiple inheritance, the inherent issues coming from that still apply.

If $C$ is a class, and $D$ a derived class (subclass), and $d:D$ we can write `d.foo()` to call a method that can be defined in $D$ (possibly ovverriding $C$'s own method) or the method which is inherited from $C$ (and not overridden). In any case, there a clear choice on which one should be called.

If instead $D$ derives from $C\_1,C\_2$ then that method might be inherited from both and we need to disambiguate somehow. For instance, `d.foo()` could be an error now, and we could require something like `d.C1::foo()` instead. Or we could give priority to the "first" superclass. Or we could require that the definition of $D$ must resolve the ambiguity (e.g. an overridden method is now mandatory). None of this is an ideal solution. Liskov substitution principle for $C\_2$ is likely broken by any of these options.

Using composition instead of inheritance, things hardly change. We still need to disambiguate. We can use `d.field_c1.foo()` instead. We can make $D$ to define a `foo()` method that chooses according to the wanted priority. We also have the additional option of making $D$ not expose the `foo()` method at all, but this means that $D$ can no longer be considered a subtype of $C\_1,C\_2$, not even in some lax sense.

More pragmatically, after decades of being almost dogmatic about OOP, the software engineering community is now coming to a more honest evaluation of it, trying to highlight the advantages without hiding the issues. Inheritance is now still found interesting and useful, but much less so.
> 4 votes

---
Tags: programming-languages, object-oriented, language-design
---


title: Infinite Union of Recursive language

text:
# Question
Title: Infinite Union of Recursive language
## Question

> Is **Infinite Union** of Recursive language is **Recursive**?

I know it is already posted here, but the i am not getting answer also i want to know if my approach is correct.

### My Approach/Doubt

$\text{let}\\,\\,L\_1=abcd \\,\\,\\,L\_2=a^2b^2c^2d^2=aabbccdd,L\_3=a^3b^3c^3d^3=aaabbbcccddd$

here $L\_{1},L\_{2},L\_{3}\\,....\text{are finite hence regular hence recursive}$

let $L\_{Iu}=L\_1 \\,\cup\\,L\_2\\,\cup\\,L\_3\\,\cup........$

but $L\_{Iu}=a^{n}b^{n}c^{n} \text{which is recursive }$ .

so can i say that **Infinite Union** of Recursive language is **Recursive**

Please help me out

# Answer
Every finite language is recursive.

Every language can be written as an infinite union of finite languages.

Some language isn't recursive.
> 1 votes

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


# Question
Title: Best way for two players to visit a set of graph vertices in a given order
I am struggling with the following dynamic programming problem:

> Given a complete $N$ vertex digraph and a list of vertices $List$, find a way for two players who start at vertices 1 and 2 respectively to visit each vertex from $List$ (order matters, i.e. $List\_{i + 1}$ should be the vertex visited after $List\_i$). Some vertices may appear in $List$ more than once (multiset). It is sufficient for a vertex to be visited by only one of players (i.e. one of them can visit all vertices while the other would remain at his starting position) If one player makes a move, the other stands still (can't make moves in parallel). If the current vertex to be visited is $List\_i$, players must move to it directly, i.e. take either $(List\_{i - 1}, List\_i)$ edge (since the previous move guarantees one of player is in $List\_{i - 1}$) or $(List\_j, List\_i)$, for some $j \< i$ ($List\_j$ is the position other player stopped at during some previous move). This means the path with $L$ vertices in it consists of exactly $L$ edges. The weight/cost of the path should be minimal. Weight of edge $(i, i)$ is always $0$, all weights are non-negative integers, no multi-edges or loops are allowed. Output the cost of such a path.

This is actually a problem from a Russian online judge. The original problem has three players (starting at $1, 2, 3$) in it and also asks to output what player did visit $List\_i$, but I reduced the problem for the case of two players which should just make things easier for perception. I think according to the rules I should provide the link for the source problem even if this is a Russian language only website, so here it is http://informatics.mccme.ru/moodle/mod/statements/view.php?chapterid=3379 . If someone really needs it, the stated constraints (that shouldn't matter since we are talking about a simplified version of a problem) for the original problem are $(3 \leq N \leq 200)$ and the number of vertices to be visited is at most $1000$ (I swapped denoting letters), no memory/time limits are given.

The problem has a `2D dynamic programming` tag.

My thoughts would be to denote $dp\_{i, j}$ as a shortest path that visits vertices from $List\_i$ to $List\_j$, i.e. $(List\_i, List\_{i + 1}, ...,List\_{j - 1}, List\_j)$. The answer is would be stored in $dp\_{1, L}$, provided that indexing goes from $1$ and $L$ stands for the length of the $List$. The problem is that I don't have a clear idea how to compute this dp-table. I thought of doing someting like $dp\_{i, j} = \min\_{k \in i..j}\\{ dp\_{i,k - 1} + cost(k - 1, List\_k) + cost(List\_k, k + 1) + dp\_{k+1,j}\\}$. Naturally, I'd at first compute all paths of length 2, then 3 and so on. The thing is, I don't understand how to deal with the main 'problem' of this problem, determining when the move is made by player 1 or 2. I thought there would probably have to be different costs of paths for different players, but they actually use the same graph, so all that matters is the position player $x$ ended up at. Filling the DP-table would actually have to consider two cases, the one described above which is guaranteed to exist as in path $dp\_{i,k - 1}$ we know that one of players ended up in vertex $k - 1$. The case where the other player goes from 'some previous' vertex should be taken into consideration as well, $\min\\{ dp\_{i,k - 1} + cost(j, List\_k) + cost(List\_k, k + 1) + dp\_{k+1,j}\\}$ , where $j$ stands for 'some previous' vertex. While writing this, I also realized that I'd probably need a little hint how to remember the player that visited vertex $List\_i$ which is needed for the original problem.

Could you provide me some help please?

# Answer
Here is the naive dynamic programming algorithm, which can probably be improved upon: For every $1 \leq i, j \leq |List|$, compute the minimal weight of a path in which Player 1 is at $List\_i$, Player 2 is at $List\_j$, and the players have covered all vertices up to $List\_{\max(i,j)}$. This should run in $O(|List|^3)$.
> 1 votes

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


# Question
Title: How to estimate floating-point precision of function?
Let's say I have a function that consists solely of floating-point operations where the last operation rounds the computed value to a predefined number of digits. And I feed this function with a range of floats.

*How do I conclude - just by looking at the decimals of the operand(s), and the structure of the code / sequence of floating-point calculations - that the round-up errors may or may not yield an unexpected result?*

Do you know of any rule of thumb or mathematical methodology? Anything I can put to general use? I don't want to actually test the code.

**Just one example for reference; range of input, required precision, and implementation of calc() are arbitrary:**

*Input:* 0, 0.01, 0.02 ... 999.98, 999.99, 1000 (delta = 0.01)

*Required precision:* Rounded accurately to 2nd decimal

*Pseudo code:*

```
function main(a) {
  res = calc(a);
  return round(res); // Rounds res to desired decimals
}

function calc(a) {
  float b = 1.1;
  return a * b;
}

```

**Update #1:**

I found an interesting blogpost on the topic: Introduction to Scientific Computing: Error Propagation

It seems to contain the mathematical tools one needs to evaluate how "error prone" a computation is.

**Update #2:**

I worked out the following method to estimate the error propagation and will describe how I applied it on my use case.

It would be great if you comment on my thoughts. I'm not sure if I did it right. And thanks for your help so far! :)

*Pseudo code:*

```
// Floats conform to IEEE 547

function main() {
  float a,b; // Real value between 199 and 684
  a = some_value;
  b = another_value;
  res_a = calc(a);
  res_b = calc(b);
  res = res_a + res_b;
  return round(res); // Rounds to 2nd decimal
}

function calc(x) {
  float c = yet_another_value; // Real value between 1 and 1.4
  return c * x;
}

```

*Estimation:*

1. As I'm using IEEE 547 floats, the machine epsilon ε is 1.1e-16.
2. The relative error δ is 2ε - according to the article linked under update #1.
3. So the absolute error of my maximal input emax won't exceed 3.8304e-13. *
4. That means the result will be precise up to the 12th decimal.
5. Since I just desire a precision of 2, the calculation does work precisely enough.

\*) emax = 2ε * resmax = 2 * 1.1e-16 * 2 * 684 * 1.4 = 3.8304e-13.

*Bonus consideration:*

Q: Would one add up the results of calc() infinitely, how many results would be "needed" approximately to contaminate the rounded total?

A: One would have to call calc() at least 4 trillion times. \o/

* e has to be at least 0.001 to force a round-up error
* The maximum result of calc() is xmax = 684 * 1.4 = 957.6
* e = δ * x =\> x = e / δ = e / 2ε = 1e-3 / (2 * 1.1e-16) = 1e+13 / 2.2
* n = x / xmax = 1e+13 / (2.2 * 957.6) ≈ 4e+9

# Answer
Assuming that you're rounding from the thousandths place, the code in your example will always be accurate. Floating point numbers remain useful because they keep their imprecisions quite small *relative to the most significant digit*.

For instance, using the 8-byte IEEE754 standard (`double`s in Java), `10.0/3.0` becomes`3.3333333333333335`.

You also asked for a rule of thumb to quickly determine whether your math will be accurate. Assuming that you are using the 8-byte standard, you can reasonably guess whether the calculation you are doing will be inaccurate by remembering that inaccuracies begin roughly 15-16 digits beyond the largest digit. If you're using the 4-byte standard (like you did in your example), you only get about 7-8 digits beyond the largest digit.

With that understanding, you can easily spot places you might run into trouble. If you're going to use a loop to multiply your number repeatedly, and then check whether the 1s digit is even or odd, you will likely run into inaccuracies.

One slightly surprising way to find trouble is to check simple equality. Consider the following Java code:

```
double x = 10.0;
double y = 3.0;
System.out.println( (1*x/(y*1)) == (10*x/(y*10)) );

```

It ultimately prints `false`, because it is really testing `3.3333333333333335 == 3.333333333333333`. So, for equality testing, you will need to make some decisions about levels of precision, and run some rounding algorithm to obtain that.
> 1 votes

# Answer
There's no rule of thumb. There is analysis, and that analysis can be more or less elaborate, depending on what you want.

Assume IEEE 754 double precision arithmetic in default rounding mode (round to nearest even). If the highest bit of the mantissa has a value of $2^k$, that is if $2^k ≤ |x| \< 2^{k+1}$ then the lowest bit of the mantissa has a value of $2^{k-52}$, the rounding error in each single operation will be at most $2^{k-53}$, and the relative error is less than $2^{-53}$.

For multiplication and division, the relative error of the result is limited by the relative errors of both inputs, plus an additional $2^{-53}$. For addition and subtraction, the absolute error of the result is limited by the relative errors of both inputs, plus an additional $2^{k-53}$, depending on the size of the result.

For a more precise analysis, consider that x-y is calculated with no rounding error at all if x/2 ≤ y ≤ 2x (the actual range is a bit larger). Relative errors are lower when a result is a little below a power of two. Multiplication / division by powers of two is exact, and so on.
> 1 votes

---
Tags: floating-point, numerical-analysis, error-estimation
---


title: How to maximize the profit

text:
# Question
Title: How to maximize the profit
In CLRS , under the section "Maximum sub array problem", there is a problem to maximize the profit in the stock exchange. The problem is.. given an array ***A\[1..n\]*** and we have to find ***i*** and ***j*** such that ***i \< j*** and ***A\[j\] - A\[i\]*** should be maximum. the solution given is **O(n^2)** . But I have a solution which does it in **O(n)** . I know it should be wrong , But I cant find a single counter example to my solution.

My solution :

(i) Find the maximun and minimum in **A\[1..n\]** . Let ***A\[x\]*** be the maximum and ***A\[y\]*** be the minimum.

(ii) And find minimum in ***A\[1..x\]*** . Let that be ***A\[u\]***.

(iii)Find maximum in ***A\[y..n\]*** . Let that be ***A\[v\]***.

(iV) Answer = **Max{(A\[x\]-A\[u\]),(A\[v\]-A\[y\])}**

What am I doing wrong?

# Answer
> 0 votes
### Counter example

Consider the array $A=\[5,2,3,4,1\]$, where $n=5$.

(i) Then $A\[1\]=5$ is the maximum and $x=1$, $A\[5\]=1$ is the minimum and $y=5$.

(ii) And find minimum in $A\[1 .. x\] = A\[1 .. 1\]=A\[1\]$ which is $5$. So, $u=1$.

(iii) Find maximum in $A\[y..n\] = A\[5..5\]= A\[5\]$ which is $1$. So, $v=5$.

(iv) Answer is $$\max(A\[x\]-A\[u\]),(A\[v\]-A\[y\]) = \max(A\[1\]-A\[1\], A\[5\]- A\[5\])= \max(0,0)=0$$

But the maximum profit is $A\[4\] - A\[2\] = 2$.

### $O(n)$ solution

The idea is to start with two pointers $i=1$ and $j=2$ and at each step increase $j$ by one. At each step check if the difference $A\[j\] - A\[j\]$ is greater than the maximum profit. If it is then update the maximum profit. But if $A\[i\] \> A\[j\]$ (in which case $A\[j\] - A\[j\]$ is negative and max profit is not updated) then we make $i$ point to the same location $j$ points to, since if for some $k \> j$, $A\[k\] - A\[i\]$ is greater than the current maximum profit then $A\[k\] - A\[j\] \> A\[k\] - A\[i\] \> maxprofit$.

1. Set $i=1$, $j=2$, $maxprofit=0$
2. If $A\[j\] - A\[i\] \> maxprofit$ then set $maxprofit = A\[j\] - A\[i\]$
3. If $A\[i\] \> A\[j\]$ then set $i = j$
4. $j = j + 1$
5. If $j\>n$ return $maxprofit$
6. Goto 2

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


# Question
Title: Prefix complexity of x conditioned on prefix complexity of x
I wonder what is $K(x|K(x))$, $K$ denoting (Kolmogorov-Chaitin) prefix complexity. Naively, it looks like it should just be $K(x)+O(1)$. Is that right? The same question for plain Kolmogorov complexity is interesting as well.

# Answer
For plain complexity the assertion is true. One direction is clear: $K(x|K(x))\leq K(x)$ (easier to describe x from something than from nothing). In the other direction one can argue by contraposition. Suppose one could find $x$s with programs $q$s of length $l(q)$ arbitrarily shorter than $K(x)$. Set $K(x)-l(q) \equiv C$. In other words one can find $x$s with arbitrarily large corresponding $C$s. To reconstruct $x$ one needs to only know $q$ and $C$, which can be encoded in $l(q)+2\log(C)$ bits. Now $K(x)-l(q)-2\log(C) = C-2\log(C)$ which can be made arbitrarily large for sufficiently large $C$. Hence, we have obtained a description of $x$ much shorter than $K(x)$, a contradiction. This may be found as problem 43 in the following book (in Russian): https://www.mccme.ru/free-books/shen/kolmbook.pdf (Vereschagin, Uspensky, Shen, "Kolmogorov complexity and algorithmic randomness").
> 3 votes

---
Tags: kolmogorov-complexity
---


# Question
Title: $\Omega(\sqrt[3]{n})$ lower bound on random-access memory?
Here is a perhaps naive question that has been tingling me: Is there an $\Omega(\sqrt\[3\]{n})$ asymptotic lower bound for addressing arbitrarily large memory randomly? My cause of belief is that the shortest path to any memory stored physically must be through three-dimensional space, and the diagonal here must have some minimal length.

For example, when sorting arbitrarily many elements, then addressing these elements must eventually cost something proportional to the distance, and even if you have high-speed cable between every single point in some space, it seems as if there is a geometric limit bounded at higher than $\Omega(n \lg n)$.

What is wrong with my argument?

# Answer
If you are talking about latency, yes, that sounds right to me. A lower bound on distance implies a lower bound on latency, due to speed-of-light considerations. However in practice these speed-of-light considerations probably do not dominate until the amount of memory is extremely large.

By the way, the situation is different if we are talking about bandwidth (i.e., the number of random-access memory operations performed per second), rather than latency. One can process many random-access memory operations concurrently, by using sorting networks.

One important caveat is that you seem to be assuming an architecture where we have one big CPU on the left and one big memory on the right, and they are separated somehow. However that's not necessarily the only way to structure a computation. One can also structure a computation, for instance, as a parallel computation, where you have a 2-D or 3-D mesh of small processors each with their own local working memory. Now accessing your local memory can be very fast, whereas accessing far-away memory is slow. In some sense there is still a $\sqrt{n}$ or $\sqrt\[3\]{n}$ bound operating, but the $n$ is much smaller for local memory than for far-away memory, so if your algorithm is designed in a way that ensures that most memory operations are to local memory, then you may be able to "beat" the lower bound you described (in some sense).

In computer architecture, one often measures the performance of a circuit by the $AT$ measure: in other words, the area of the circuit ($A$) multiplied by the time it takes for the circuit to complete a computation ($T$). If you like, you can think of this as a price-to-performance ratio: it is the price (which is assumed to be proportional to the area of the circuit) divided by the performance (the number of computations that can be performed per second, i.e., the inverse of $T$). A standard architecture with a single beefy CPU and one big memory is not always the optimal architecture. Sometimes you can get large speedups (more than a constant factor) by using parallel computation or other architectures. This is at least partly due to exactly the issue that you mentioned: it is much faster to access memory that is near you than to access memory that is far away. Caching (e.g., L1 cache, L2 cache, etc.) is also based upon the same principle.

Below is an example of a paper in the world of cryptography that considers design of special-purpose circuits for cryptanalytic tasks, and takes these issues into account. For instance, it has a bunch of processors, a big memory, and a sorting network in between the two to route memory accesses from the processors to memory. This enables a high number of memory operations to be "in flight" at once, even though it does not eliminate the latency.

---

If you want to dive further into this line of thinking, there is an interesting (but mostly theoretical) debate one can have over whether the right metric is area or volume, i.e., whether the right lower bound is $\sqrt{n}$ or $\sqrt\[3\]{n}$. Yes, the world is three-dimensional, but heat dissipation is two-dimensional; a massive cube of computers would be limited by its ability to dissipate heat, which scales with its surface area, not its volume. One can continue onward in this vein. If this sounds like a fascinating topic, see Q.9 (pp.45-46) of the following paper:
> 6 votes

# Answer
See related lower bounds for computation (and memory, which can be viewed as a form of computation) sensitive to limited communication speed, lower bounds on unit size, and fixed spatial dimension.

David C. Fisher: Your Favorite Parallel Algorithms Might Not Be as Fast as You Think. IEEE Trans. Computers 37(2): 211-213 (1988)

In particular, in dimension $d$, you get a lower bound of $\sqrt\[d+1\]{N}$, so cubic root shows up for dimension two - appropriate for most semiconductor chips today. Watch out for Micron's DRAM cube!
> 2 votes

# Answer
The theoretical asymptotic bound is also $O(\sqrt{n})$ if we want to avoid the computer collapsing into a black hole.

Obviously this restriction is lifted if we figure out wormholes, in which case we can run our computer in a pocket universe as well.
> 2 votes

---
Tags: algorithms
---


# Question
Title: What is a "closed set" in context of AI? How is it different from an open set or a frontier?
I am reading some properties on the A\* search algorithm on Wikipedia, specifically:

"If the heuristic function h is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A\* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then h must also be monotonic (or consistent) for A\* to be optimal."

But I am not sure I understand what a "closed set" refers to. Is it different than an open set / frontier? If so, why? And why do we use a "closed set" as opposed to an "open set" for A\*? Is a priority queue a closed set?

# Answer
There are two variants of the A\* algorithm:

* The standard algorithm maintains two sets of vertices. One called the "open set", and the other is called the "closed set".
* An alternative version maintains just an open set, and doesn't use a closed set. This requires that the heuristic function satisfy some some additional conditions.

See any standard treatment of A\* for explanation of how it works and what the closed set is; e.g., A\* search.
> 1 votes

---
Tags: algorithms, graphs, data-structures, artificial-intelligence
---


# Question
Title: AVL Tree or HashTable for storing relatively big data?
I have been looking to implement a data structure for my project. I came across AVL tree and Hash Table. As I am a beginner so I'm in dilemma what data structure I use for large data. The main operation will be mostly searching through the database efficiently.

AVL Tree seems to be very good option to store around 120000 entries(object) of data and keep the search time to O(logn), however I stumble upon a perfect hashing concept. It states it expected the search time is constant O(1), if collision occur then it would use secondary hash function that will still have access time of O(1) if I'm not mistaken.

perfect hashing function according to Introduction to Algorithm by Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, Clifford Stien is :- h(k) = ((3k + 42) mod 101) mod size(number of enteries)

Data that I'm storing is from text file, converting each line into an object. All those objects will be inserted all at once in data structure. After that main operation I have to use is search through the data structure.

Bus -\> street1 -street2- street3- destination, this line would be converted into an object. So search would be like return the route bus1 took to reach destination5.

Any suggestions which one would be more reliable and efficient for time and space complexity?

# Answer
For search dominant operation, supported *insert*, *delete*, *find* only there are huge benefits in using the Hash Table.

* the memory footprint is low, only colliding entries require pointer, one per entry while AVL requires two pointers per entry.
* access time is expected $\mathcal O(1)$, say in the worst case 5, which gives one hash calculation and 5 equality tests while AVL has 25 full comparissons for 120000 entries in the worst case.
* rehashing could be avoided with maximal capacity known in advance, otherwise it would be rare operation.

What would opt for AVL?

* traversal queries, looking for ranges etc.
* access to sorted data.
* inexact queries, looking for nearest neighbour (at the cost of additional pointers).

By the way the *perfect hash table* is commonly refered to as having no collisions, which requires static setting, rehashing. What you refer to is probably *dynamic perfect hashing*, a two-tier scheme with guaranteed deterministic constant lookup.

If you have all data (or substantial amount) it is beneficial to sort data and create balanced tree to avoid inserting nodes one by one. (Something like DSW algorithm would help).
In that case the hash table may be constructed without collisions at all for initial data, leaving space for future elements and work really fast.

For the search part, none of the structures would help. If I understood correctly, your data is a graph, so both presented structures will help with indexing only and the Hash Table is the winner.

Sidenote:
To store compactly textual data something like Trie or Directed Acyclic Word Graph would be better. The edited part about search would require a graph, path finding algorithm and auxiliary indexing data structure, in your case probably Hash Table or DAWG used as map.
> 2 votes

---
Tags: algorithms, algorithm-analysis, hash-tables
---


# Question
Title: Karatsuba Multiplication with n/3 division of large number
I was studying Karatsuba multiplication where the complexity is reduced as compared to classical algorithm by splitting each number into two parts.

Now I'm trying to understand how the multiplication will take place when a number is divided into three parts instead of two.

I tried to solve the math but only came up with more number of multiplications than in Karatsuba.

Can someone help me out with this problem?

# Answer
The algorithm you are looking for seems to be the Toom-3 algorithm.
> 2 votes

---
Tags: algorithms, algorithm-analysis, divide-and-conquer, multiplication
---


title: Asymptotics and logarithmic exponents

text:
# Question
Title: Asymptotics and logarithmic exponents
I was tasked to order some functions in respect to the $\mathcal{O}$ notation, and have some problems with the following ones:

$n^{\ln(7)} = \mathcal{O}(n^{3})$: I can't find a more elegant proof for this other than using L'Hôpital's rule and a numerical approximation of $\ln(7)$:

$\lim\_{n\to\infty} \frac{n^{\ln(7)}}{n^3} = \lim\_{n\to\infty} \frac{n^{ \approx1.94591014906}}{n^3} = \lim\_{n\to\infty} \frac{n^{\approx1.94591014906-3}}{3\*2\*1} = 0 $

(The last equal sign is valid, since the exponent is negative.) Is there a better way to do this ?

Furthermore I have no idea how to prove $8^{\log\_2 n} = \mathcal{O}(5^n)$. I tried to apply the limit rule but to no avail. I think it is intuitively clear, since $\log\_2 n$ grows slower than $n$, but I don't know how to argue that rigorously.

Thanks for any answers.

# Answer
> 4 votes
First, notice that $3 \> \ln 7$. You can prove this formally using the Taylor expansion of $e^x$: $$ e^3 = \sum\_{n=0}^\infty \frac{3^n}{n!} \geq 1 + 3 + \frac{9}{2} = 8.5 \> 7. $$ Monotonicity of $\ln$ implies that indeed $3 \> \ln 7$.

Armed with this knowledge, we deduce that for $n \geq 1$, $$ n^3 = n^{3 - \ln 7} n^{\ln 7} \geq n^{\ln 7}. $$ This shows that $n^{\ln 7} = O(n^3)$, using the definition of big O.

For your other question, try using $8^{\log\_2 n} = n^3$ and induction. The idea is that as you increase $n$ by 1, the value of $n^3$ hardly increases, whereas $5^n$ increases by a factor of 5.

Finally, let me say that there is absolutely no reason to be so formal. It's enough to go through the formalities once, just to get convinced that they work, and afterwards you can just use well-known facts such as $n^k = o(c^n)$ for all $c \> 1$.

---
Tags: asymptotics
---


# Question
Title: Classes of languages for which the language $\{a_1^n \cdots a_k^n \mid n \geq 0\}$ is in the language for $k$ but not $k+1$
In any introductory course on the theory of computing, one encounters the language $$L\_k = \\{a\_1^n \cdots a\_k^n \mid n \geq 0\\}$$ as a canonical (or at least pedagogical) counterexample for a language which is not regular ($k=2$) or context-free ($k=3$). The next jump is usually to the turing machine, where $L\_k$ is in the class for all $k$.

Is there a (sensible, e.g. defined in some terms of generating grammar or recognizing automaton) hierarchy of classes of languages $\mathsf{COMP}\_k$ so that $L\_j \in \mathsf{COMP}\_k$ for $j \< k$ and $L\_j \not\in \mathsf{COMP}\_k$ for $j \geq k$? Ideally it would also hold generally that $\mathsf{COMP}\_k \subset \mathsf{COMP}\_{k+1}$. Or, perhaps, is this distinction of being able to recognize $L\_k$ not important/fundamental once $k \geq 3$ (in whatever sense you want to interpret that question)?

# Answer
One example would be the hierarchy defined by blind counter automata. A blind $k$-counter automaton has access to $k$ counters for which

* there is an increment and a decrement instruction (and no zero-test),
* a run is accepting if in the end, all counters are zero, and
* during a run, the counters are allowed to be negative.

Let $\mathcal{B}\_k$ denote the class of languages accepted by blind $k$-counter automata. Then $L\_{k}\in \mathcal{B}\_{k-1}$: while you read $a\_1$'s, you increment all $k-1$ counters simultaneously; then each of the remaining $k-1$ letter blocks decreases one of the counters.

On the other hand, one has $L\_{k}\notin\mathcal{B}\_{k-2}$. This can be shown, for example, using Theorem 6.4 in Fernau and Stiebe's paper on valence automata/grammars. This pumping lemma allows, in a blind $\ell$-counter automaton, the simultaneous repetition of $\le\ell+1$ non-empty factors. Hence, if we had $L\_k\in\mathcal{B}\_{k-2}$, we could repeat $\le k-1$ factors, which can span at most $k-1$ distinct letters in a word $a\_1^\*\cdots a\_k^\*$. Hence, we could pump up powers of some $a\_i$'s without touching at least one letter $a\_j$, which clearly leads out of the language. In Fernau and Stiebe's paper, the class $\mathcal{B}\_k$ is denoted $\mathscr{L}(\mathrm{Val},\mathrm{Reg},\mathbb{Z}^k)$.
> 4 votes

---
Tags: formal-languages
---


# Question
Title: Can we apply De Morgan's to any operator? (boolean , arithmetic , relational)
I have seen various statements with negation( or complement) operators and when i try to negate them using De Morgan's law , i become confused about how to negate.

**The main doubts are what variables to negate and what operators to negate.**

Example:- ~(p^q)= ~p∨~q (according to De Morgan's)

**Doubt1** but for ~(p=q) should i blindly negate everything like ~p!=~q or should i do p!=q ?

**Doubt2** Can DeMorgan's law be applied to this below statement(it contains addition operator )?

x and y are 4 bit signed numbers (2s complement..)

x - y can be obtained by:

!(!x + y) because

If z is an n-bit number then !z=2^n−1−z.

So...

!(!x+y)=2^n−1−(2^n−1−x+y)=x−y.

but if I try to simplify the expression using DeMorgan's law

I get !(!x+y)=x+!y

and x+!y is not equal to x-y (in 2's complement).

So I am not able to find out my mistake. Can someone please help.

# Answer
> 2 votes
Relating to "can we apply De Morgan's laws to any operator", De Morgan's Laws are applicable in De Morgan algebras (by definition), which is a bit broader than just Boolean algebras. Fuzzy logic is a non-Boolean example where De Morgan's Laws hold (and can properly be called that, despite relating operations that we normally call minimum and maximum). The laws definitely cannot be applied to all operators all the time.

This actually also answers your first question, De Morgan's Laws do not even apply to $\sim(p=q)$ in the first place.

Generalizing further, laws that *look like* De Morgan's Laws show up when a pair of operation is each others "mirror image": operation A becomes B when you work in a mirror image of the applicable number line, and vice versa. If you go that far, laws like these show up as, if being really generous with the naming, "variants of De Morgan's Laws":

* $-\min(a, b) = \max(-a, -b)$
* $-\text{avg-round-down}(a, b) = \text{avg-round-up}(-a, -b)$
* $-\lfloor x \rfloor = \lceil -x \rceil$ (not even a 2-operand operation, but I think it's relevant here)

Note that all of these are "directional", they care about the built-in "direction" of the number line so mirroring it makes a difference.

Relating more to your second question (the addition thing), subtraction and addition are not related through a variant of De Morgan's Law. In fact if you mirror addition (with negation), you get back addition: $-(-x + -y) = x + y$. A fundamental problem here is that addition does not care about the inherent "direction" of the number line, so of course it *had* to be its own mirror image - from the point of view of addition, nothing has really changed.

An other way to say that is that addition does not have a "bias" in any particular direction, while what the mirroring would do is switch the direction of the bias. Mirroring with complement in bitvector arithmetic doesn't help, although a stray 1 shows up and makes it look like there might have been a bias, bitvector addition actually isn't biased.

An other problem here is that addition is commutative while subtraction is anticommutative, but the mirror image of a commutative operation is still commutative - all the mirroring does is change the direction of the space you're in, the operation still acts the same way, just maybe in a different direction.

That said, $x - y = \sim(\sim x + y)$ (also part of your second question) does make sense now that we're thinking about mirroring and changing the direction of space. Imagine $x$ and $y$ as being arrows, then $\sim x$ turns that arrow around, we add $y$ to it, and then we flip the result around too. Geometrically, it makes sense that the effect is that $y$ was reversed and added to $x$.. but there is of course a catch, because $x - y \neq x + \sim y$. The funny thing here is that addition is sort of "centered" on zero, while the mirroring operation we're using mirrors $0 \leftrightarrow -1$, so we either need two mirroring operations to cancel out that problem or an explicitly offset: obviously also $x - y = x + \sim y + 1$.

That's not an example of De Morgan's Laws in action. By those laws, both operands would be mirrored so the entire operation happens in the context of a mirrored number line. But $\sim(\sim x + \sim y) = x + y + 1$, where that extra +1 shows up again because the offsets from both inner mirroring operations are added, but only compensated for *once* by the outer mirroring operation. This is of course nowhere near a subtraction, it's more like a version of $-(-x + -y) = x + y$ except it works out less well.

# Answer
> 5 votes
De Morgan laws are **precisely** the following formulas: $$\lnot(p \land q) \iff \lnot p \lor \lnot q$$ and $$\lnot(p \lor q) \iff \lnot p \land \lnot q$$ You may only apply them in the above two situations. Anything else, whether it involves numbers, addition, equality, etc., has nothing to do with de Morgan laws.

There may be some *generalizations* of de Morgan laws which might be applicable in some other situations, and there might be some other rules that are similar to de Morgan laws, but given what you are asking, it's best not to worry about them.

In some situations, you can *indirectly* apply de Morgan laws if you first bring your formula into a suitable form. For example $\lnot (p = q)$ where $p$ and $q$ are Boolean values, we need to notice that $p = q$ is just $p \Leftrightarrow q$, which is $(p \Rightarrow q) \land (q \Rightarrow p)$, which is then $(\lnot p \lor q) \land (\lnot q \lor p)$, and so \begin{align\*} \lnot (p = q) &\iff \lnot (p \Leftrightarrow q) \\ &\iff \lnot ((p \Rightarrow q) \land (q \Rightarrow p)) \\ &\iff \lnot ((\lnot p \lor q) \land (\lnot q \lor p)) \\ &\iff \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor p) \tag{by de Morgan}\\ &\iff (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot p) \tag{by de Morgan} \\ &\iff (p \land \lnot q) \lor (q \land \lnot p) \end{align\*}

**Supplemental:** Since the OP is asking about applicability of de Morgan laws, let me expand on this a bit. The basic de Morgan lawss hold in any Boolean algebra, examples of which are the propositional calculus and the powerset of a set. These are mentioned by the OP. There are other cases two, for instance $$-\max(x, y) = \min(-x, -y)$$ and $$-\min(x,y) = \max(-x, -y)$$ holds in real numbers. This idea leads to further investigations of de Morgan laws in algebra, of which I know next to nothing.

Another kind of generalization of de Morgan laws is $$(\lnot \forall x . \phi(x)) \iff \exists x . \lnot \phi(x)$$ and $$(\lnot \exists x . \phi(x)) \iff \forall x . \lnot \phi(x).$$ But I still stand by my original advice that one should learn to walk before one tries running.

---
Tags: logic
---


# Question
Title: How to prove the equivalence between Hoare and Floyd assignment axioms?
How to show that these two axioms are equivalent:

1: $\\{G\[v/e\]\\} v:=e \\{G\\}$

2: $\\{F\\} v:=e \\{\exists v' (F\[v/v'\] \land v=e\[v/v'\])\\}$

I've tried with $G = \exists v' (F\[v/v'\] \land v=e\[v/v'\]) $and then I get $G\[v/e\] = F$, but when I try $F = G\[v/e\]$ then from $\exists v' (F\[v/v'\] \land v=e\[v/v'\])$ I can't obtain $G$.

Is that even correct way to approach this proof?

Thanks!

p.s. There was a question already, but isn't answered: How to show equivalence of the Hoare assignment axiom vs Floyd assignment axiom?

# Answer
> 3 votes
> but when I try $F = G\[v/e\]$ then from $\exists v' (F\[v/v'\] \land v=e\[v/v'\])$ I can't obtain $G$.

We can assume $v'$ not free in $G$. Then, we have

$$ \begin{array}{ll} & \exists v' (F\[v/v'\] \land v=e\[v/v'\]) \\ \iff & \mbox{\\{def. $F$\\}}\\ & \exists v' (G\[v/e\]\[v/v'\] \land v=e\[v/v'\]) \\ \iff & \mbox{\\{property of $H\[v/-\]\[v/-\]$\\}}\\ & \exists v' (G\[v/(e\[v/v'\])\] \land v=e\[v/v'\]) \\ \iff & \mbox{\\{replacing equals with equals\\}}\\ & \exists v' (G\[v/v\] \land v=e\[v/v'\]) \\ \iff & \mbox{\\{$\[v/v\]$ has no effect\\}}\\ & \exists v' (G \land v=e\[v/v'\]) \\ \iff & \mbox{\\{$v'$ not free in $G$\\}}\\ & G \land \exists v' (v=e\[v/v'\]) \\ \implies & \mbox{\\{logic\\}}\\ & G \end{array} $$

The crucial step is to realize that any $v$ which occurs free in $G\[v/e\]$ is a $v$ that originated from $e$. Hence, $G\[v/e\]\[v/t\] = G\[v/(e\[v/t\])\]$.

Also note that we don't get exactly $G$ but a slightly stronger postcondition. Since postconditions can be weakened, this is not an issue.

---
Tags: hoare-logic, software-verification
---


# Question
Title: Regular language such that L(r) = L(r₁) L(r) ∪ L(r₂)
Prove or disprove the following statement: for arbitrary regular expressions $r\_1$ and $r\_2$ over an alphabet $\Sigma$ such that $\epsilon$ belongs to $L(r\_1)$, there exists a regular expression $r$ over $\Sigma$ such that $r = r\_1r + r\_2$.

My Solution: Let us consider $\Sigma =\\{a\\}$. $L\_1$ is even number of symbols so $r\_1 =(aa)^\*$ and $L\_2$ is odd number of symbols so $r\_2 = a(aa)^\*$. $r$ is either $r\_2$ which is possible or $rr\_1$. Now if we keep replacing $r$ with $rr\_1$ in the expression we will end up getting an infinitely large string because $r$ cannot be $\epsilon$ (thats what I think). So in my opinion this language is not regular. But I am not sure if I am thinking correctly.

# Answer
Take $r = (r\_1 + r\_2)^\*$. We have to prove $$(r\_1 + r\_2)^\* = r\_1(r\_1 + r\_2)^\* + r\_2$$

First note that both $(r\_1 + r\_2)^\*$ and $r\_1(r\_1 + r\_2)^\* + r\_2$ contain $\epsilon$ since we are given that $\epsilon \in L(r\_1)$, so we will consider a nonempty string in our proof.

Let's first show that $(r\_1 + r\_2)^\*\subseteq r\_1(r\_1 + r\_2)^\* + r\_2$. But it is trivial since we know that $\epsilon \in L(r\_1)$ and so $$r\_1(r\_1 + r\_2)^\* + r\_2 = (r\_1 + r\_2)^\* + r\_1'(r\_1 + r\_2)^\* + r\_2, \text { where } r\_1 = r\_1' + \epsilon$$

Now we have to show that $r\_1(r\_1 + r\_2)^\* + r\_2 \subseteq (r\_1 + r\_2)^\*$. Assume a nonempty string $s \in r\_1(r\_1 + r\_2)^\* + r\_2$. Then either $s \in r\_2$ or $s \in r\_1(r\_1+r\_2)^m$ for some nonnegative integer $m$. In the first case since $r\_2 \subseteq (r\_1+r\_2)^\*$, we are done, so assume $s \in r\_1(r\_1+r\_2)^m$. But we know that $(r\_1+r\_2)^{m+1} \subseteq (r\_1+r\_2)^\*$. Thus $$(r\_1+r\_2)^{m+1} = (r\_1+r\_2)(r\_1+r\_2)^m = r\_1(r\_1+r\_2)^m + r\_2(r\_1+r\_2)^m$$ meaning $r\_1(r\_1+r\_2)^m \subseteq (r\_1+r\_2)^\*$.
> 2 votes

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


# Question
Title: Minimum Number of People Such That No Two People Know the Same Two People
In a population of $n$ people, each person knows $k$ other people and each person is known by the same $k$ people. However, no two people, p1 and p2, know the same two people p3 and p4. What is the minimum $n$ such that this is possible for a given $k$? Or, in other words, what's the minimum number of nodes that must exist such that it is possible to connect each node to $k$ other nodes while not allowing a cycle of length 4?

Also, if it is possible, is there a program that can generate these graphs?

I don't have much on this problem yet besides a weak lower bound of $n\geq k^2-k+2$.

In the graphs below, an edge means that the two people it connects know each other. In 1), this is a demonstration of what we don't want, both A and C know D and B. In 2) these are configurations that work for k=2. For k=2, n=3 and all n\>4 work. In 3) n=10, this is the smallest possible configuration for k=3.

# Answer
The comment of Carlos actually gives an upper bound. There is a much better (and almost tight) upper bound for $k+1$ being a prime number: $n=k(k+1)$. The construction is a classical result in extremal graph theory, namely $C\_4$-free $k$-regular graphs, which can be found here.

The vertices are labeled with $(a,b)$ where $1\leq a\leq k, 0\leq b\leq k$. Two vertices $(a,b)$ and $(c,d)$ are linked if and only if $ac\equiv b+d\mod (k+1)$. Notice that for any given pair $(a,b)$ the number of solutions $(c,d)$ is exactly $k$, so the graph is $k$-regular. To see the graph is $C\_4$-free, consider the following congruence equations $$\left\\{ \begin{array}{ll}ax\equiv b+y\mod (k+1)\\ cx\equiv d+y\mod (k+1)\end{array} \right.$$ Since these imply $(a-c)x\equiv b-d \mod (k+1)$, and $k+1$ is prime, there is at most one solution whenever $(a,b)\neq (c,d)$, so the graph contains no $4$-cycle.

There are many other constructions among this context, for instance, when $k-1$ is a prime power there is a construction of size $n=2(k^2-k+1)$ with bipartite incidence graph (See, e.g., here).
> 2 votes

---
Tags: graphs, trees
---


# Question
Title: Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?
Consider two heuristics $h\_1$ and $h\_2$ defined for the 15 puzzle problem as:

1. $h\_1(n)$ = number of misplaced tiles
2. $h\_2(n)$ = total Manhatten distance

Could anyone tell why $h\_2$ is a better heuristic than $h\_1$? I would like to know why the number of nodes generated for $h\_1$ is greater than that for $h2$. Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

Source: Informed Search

# Answer
> 5 votes
There probably will be no formal proof; probably the only way to tell which is better is through experiments.

But some intuition seems possible. $h\_1$ only takes into account whether a tile is misplaced or not, but it doesn't take into account how far away that tile is from being correct: a tile that is 1 square away from its ultimate destination is treated the same as a tile that is far away from where it belongs.

In contrast, $h\_2$ does take this information into account. Instead of treating each tile as either "correct" or "incorrect" (a binary decision), $h\_2$ introduces shades of grey that take into account how far the tile is from where it belongs. It seems plausible that this might possibly yield some improvement.

Of course, the only way to find out which one *actually* works better is to try the experiment. But this might give some intuition about why one might reasonably hope that $h2$ could be potentially be better than $h\_1$.

# Answer
> 4 votes
The current answers are good, but I think I have a simpler way to understand it. The Manhattan Distance heuristic approximates the actual distance better than the misplaced tiles heuristic. So, you can think of the actual number of moves it would take as the perfect heuristic (at that point it stops being a heuristic). Like Daniil Agashiyev said, the lowest the Manhattan distance huristic can possibly be is equal to the misplaced tile heuristic. Since both are admissible, that means they both underestimate the true distance. So, the estimations are closer to the actual for Manhattan distance heuristic since it is grater then $H\_1$ and less than the actual (let’s call it $H^\*$). This is the better heuristic definitively, and it can be formally proven.

$$H\_1 \leq H\_2 \leq H^\*.$$

The reason it will generate less nodes in the search tree is because it will be able to approximate which nodes to explore next better than the misplaced tile heuristic. This is related to $H\_1\leq H\_2\leq H^\*$. Of all the nodes unexplored, the one to select next is decided by the cost estimated by the heuristic. Therefore, the $H\_2$ heuristic will provide you a better selection criterion on what to move next. At $H\_2$’s worst case, it’ll be equal to $H\_1$. For example, beginning at the start state, all the next moves possible will have equal cost with $H\_1$. This is because no tile can be placed in the right location in one move. For $H\_2$ there will be an order to the next moves, so you can still look one by one, but in an order that can only help.

> Also why going deeper into the state space the number of nodes increase drastically for both heuristics.

I think you mean going deeper down the search tree? This is because A\* is based off Breadth first search, the number of nodes expand exponentially as you explore more nodes.

# Answer
> 1 votes
$h\_1(n) \leq h\_2(n)$ because if a tile is misplaced, it will add value of 1 to the total heuristic evaluation, while its Manhattan distance will be at least 1. If it's not misplaced, both are 0.

$h\_2(n) \leq h^\*(n)$ because each transition will change the Manhattan distance of only one tile and each tile will have to move at least its Manhattan distance to the goal state.

Now the answer to the question why $h1$ expands more nodes than $h2$ when $h\_1(n) \leq h\_2(n) \leq h^\*(n)$, has been given before:
Why is it the lower the h(n) cost the more nodes need to be expanded in A\*?

---
Tags: algorithms, heuristics
---


# Question
Title: Are all vertices within a strongly connected component with 2 or more vertices part of a cycle?
Within a directed simple graph, are all vertices within a strongly connected component with 2 or more vertices part of a cycle?

# Answer
> 1 votes
Suppose it's not the case, it means that there is a node $v$ that is either isolated (contradicts $n \geq 2$) or has an arrow that is incident to it. Let this arrow be from $v$ to $v'$, with no loss of generality. Since we have supposed that $v$ is not part of a cycle, it's impossible to go from $v'$ to $v$, which contradicts strong connectivity.

---
Tags: graphs
---


# Question
Title: Minimum number of nucleotides to force duplicate substring
There are 4 DNA nucleotides, each represented by one of the letters A, C, G, or T.

Assume that they can be arranged in a string e.g. "GATTACA...". I want to figure out the minimum number of nucleotides I would have to encounter before I'm pigeonholed into seeing a duplicate substring of length 3.

Observe that a string of 4 nucleotides could produce a duplicate substring of length 3 (although I'm not forced into a pigeonhole since there are other strings of length 4 that don't produce a duplicate).

```
AAAA

```

Substrings \[0-3) and \[1-4) are both "AAA", so a duplicate occurrence of a length 3 substring has appeared.

I originally tried concatenating together every combination of 3 nucleotides.

```
[AAA][CAA][GAA][TAA][ACA][CCA]
AAACAAGAATAAACACCA...

```

But this algorithm produces a duplicate rather quickly: substrings \[0-3) and \[10-13).

I know there are 4^3 = 64 different substrings of length 3, so an upper bound to force pigeonholing is a string of length (64 * 3) + 1 = 195 -\> one of the 64 substrings must appear twice. I've convinced myself that this can be bounded tighter to length 67 since this could contain 64 different substrings that start at indexes 0-63 and one duplicate that starts at 64. The interleaving of the substrings with each other is what makes them hard to analyze. How much tighter can this bound go, and what is an algorithm for producing a sequence that forces a pigeonhole?

# Answer
> 4 votes
The answer is 66: any sequence of length greater than 66 must contain some repeated substring (as you argue in the question), and there exists a sequence of length 66 where no substring is repeated.

The latter can be obtained from a de Bruijn sequence with $n=3$ and $k=4$. The length of this sequence is $k^n=64$ symbols. A de Bruijn sequence is a cyclic string such that every possible length-$n$ string occurs exactly once as a substring of it. It is known that a de Bruijn sequence of length $k^n$ exists. If we take the de Bruijn sequence $x\_1 x\_2 \cdots x\_{64}$, then $x\_1 x\_2 \cdots x\_{64} x\_1 x\_2$ is an ordinary string where every possible length-3 string occurs exactly once as a substring. In particular, no length-3 substring of $x\_1 x\_2 \cdots x\_{64} x\_1 x\_2$ is repeated. There are also standard algorithms to find such a string.

---
Tags: combinatorics, substrings, bioinformatics
---


# Question
Title: Detecting face like patterns using CNN based face detector
I have a CNN based object detector trained on WIDER Face dataset. It can successfully detect human faces in a given image.

Now, I am trying to detect abstract face and minimalistic face patterns in clouds or houses etc but having no success.

Initially, I thought I could lower the detection threshold to detect such patterns, but such scheme didn't work.

My question is there any way other than collecting and labelling such training examples (face like patterns) to solve this problem.

# Answer
You probably need a training set that contains examples of abstract faces and minimalistic face patterns. There's no reason to expect a neural network trained on real faces to detect abstract face patterns; neural networks don't necessarily generalize that way.
> 1 votes

---
Tags: machine-learning, neural-networks
---


# Question
Title: Is there a way to make chess an absolutely fair game?
Chess is usually considered a mostly "fair game" between White and Black because the opening position of pieces has mirror symmetry (between players). In practice it also *appears* to be a fair game because it is combinatorially complex, so if White has a first-move-advantage, it is hard to detect in actual play.

What are some examples of changes in the rules of chess where the game can be made exactly mathematically fair, including eliminating any possibility of White's possible first-move-advantage, and without adding any chance events (such as a coin toss as to who moves first)?

# Answer
> 1 votes
We can run a pair of games, sequentially, where player one first plays white, then black.

Let's write W for win, L for lose and D for draw, from the point of view of player one. In the cases WW,WD,DW, player one wins the match. In the cases LL,LD,DL, player one loses the match. In the cases WL,LW,DD, the match is a draw. (If a draw match is undesired, play another match.)

# Answer
> 1 votes
Chess has not been solved: that is, there is no runnable algorithm which can look at a board and see if there is a move that will guarantee a win for one player. Minimax does this in principle, but when starting from a fresh chess board, would take far too much time to complete. So, we don't know who would win if we had two perfect, omniscient players.

This is in contrast to Checkers, which has been solved. It turns out that if both players play perfectly, it will always be a draw.

So the answer to your question could be that chess is already mathematically balanced between both sides. Or it could be that one side can always win if playing optimally. But we don't know, and may never know.

# Answer
> -1 votes
Simple. Throw a coin to decide who moves first.

In a single game, white has a distinctive advantage. Usually you play tournaments where each side plays white and black equally often.

---
Tags: combinatorics, board-games
---


# Question
Title: Given a computable function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$?
1) (cited from "Introduction to the Theory of Computation" by Michael Sipser)

> Let $M$ be a Turing machine, we say that $M$ decides a language $L$ if $M$ is a decider which recognizes $L$.

2) (cited from "Computational complexity: a modern approach" by Boaz Barak and Sanjeev Arora)

> Let $f \colon \Sigma^{∗} \rightarrow \Sigma^{∗}$ and let $T \colon \mathbb{N} \rightarrow \mathbb{N}$ be some functions, and let $M$ be a Turing machine. We say that $M$ computes $f$ if for every $x \in \Sigma^{∗}$, whenever $M$ is initialized to the start configuration on input $x$, then it halts with $f (x)$ written on its output tape.

I think these two definitions shows two different functions of TMs, and it seems that there is not conflict between them.

So, given a computable total function $f$ and a decidable language $L$, is there a Turing machine $M$ such that $M$ both decides $L$ and computes $f$ ?

# Answer
> 3 votes
Yes it clearly exists; informally you can build such $M$ in this way:

* $M$ makes a copy of its input $x$
* then without touching such a copy, $M$ decides if $x$ is in $L$ (possibly "destroying" the working copy of $x$),
* if $x \in L$ it enters a "subprogram" (set of states) in which all states are accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in an accepting state)
* if $x \notin L$ it enters a "subprogram" (set of states) in which all states are NON accepting and such subprogram uses the copy of $x$ to compute $f(x)$ (leaving the result in the output tape and ending in a NON accepting state)

---
Tags: computability, turing-machines, computation-models
---