# Question
Title: Derivation of the energy function of a hopfield network
Can someone please point me towards a rigorous derivation of the energy function of a discrete Hopfield network. What I want, is the derivation must start out with the structure of the network and prove that the critical points of the dynamical system can be obtained by minimization of some function (possibly by constructing the Lyapunov function of the dynamical system). I cannot seem to find such a rigorous proof. Thankyou!

# Answer
> 6 votes
I believe what you want to show is that the energy function is monotonically decreasing from time $t$ to time $t+1$ given the state update rules. Since there is only a finite number of states, this means the state must converge to a equilibrium under the given dynamics.

To this end let $\mathbf{s}(t) \in \\{0,1\\}^n$ be the state of the network at time $t$. We update the network state by picking a unit $s\_i(t)$ and updating the state according to $$ s\_i(t+1) = \left\\{\begin{array}{r l} 1:& \sum\_{j} w\_{ij} s\_j(t) \> 0\\ 0:& \text{otherwise}\end{array}\right. $$ and define the energy function as $$ E(\mathbf{s}(t)) = -\frac{1}{2}\sum\_i\sum\_jw\_{ij}s\_i(t)s\_j(t), $$ where $w\_{ij}$ is the weight between unit $i$ and $j$, $w\_{ij} = w\_{ji}$ and $w\_{ii} = 0$ for al $i$.

WLOG assume we will update the $i^{th}$ unit. First, because of the restrictions on the weights, we may rewrite $E(\mathbf{s}(t))$ as the difference of 2 terms $$ E(\mathbf{s}(t)) = -\frac{1}{2}\sum\_{j\neq i}\sum\_{k\neq i}w\_{jk}s\_j(t)s\_k(t) - s\_i(t)\sum\_jw\_{ij}s\_j. $$ Let $c\_t = -\frac{1}{2}\sum\_{j\neq i}\sum\_{k\neq i}w\_{jk}s\_j(t)s\_k(t)$ be the part of the energy function that does not depend on $s\_i(t)$. Now if $s\_i(t+1) = s\_i(t)$ then clearly we have $E(\mathbf{s}(t+1)) = E(\mathbf{s}(t))$, so we only need to consider the 2 other cases.

Case 1: If $s\_i(t+1) = 1$ and $s\_i(t) = 0$ then it must be that $\sum\_{j} w\_{ij} s\_j(t) = \Delta\_t \> 0$. So $$ E(\mathbf{s}(t+1)) = c\_{t+1} - \Delta\_t = c\_t - \Delta\_t \< c\_t = E(\mathbf{s}(t)). $$ Case 2: If $s\_i(t+1) = 0$ and $s\_i(t) = 1$ then it must be that $\sum\_{j} w\_{ij} s\_j(t) = \Delta\_t \le 0$. So $$ E(\mathbf{s}(t+1)) = c\_{t+1} = c\_t \le c\_t - \Delta\_t = E(\mathbf{s}(t)). $$ Having considered each case we can conclude that $E(\mathbf{s}(t+1)) \le E(\mathbf{s}(t))$ and is therefore monotonically decreasing.

# Answer
> 0 votes
One way to go about it is to consider the energy function for a (fully visible) Boltzmann machine which approaches a hop field net as T-\>0. You can derive the sigmoidal activation function from the energy via the boltzmann distribution and Bayes rule P(output=1| net input) for each unit.

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


# Question
Title: Consistency and completeness imply soundness?
I understand that soundness implies consistency. Also, I understand that consistency alone does not imply soundness. But shouldn't consistency + completeness imply soundness? Scott Aaronson in his blog-post hints otherwise. What am I exactly missing?

Update: By completeness I assume that all sentences true under all interpretations are deducible. By soundness I assume that all deduced sentences are true under all interpretations. Finally, by consistency I assume that no sentence $P$ and its negation $\neg P$ can be deduced.

# Answer
In the Scott Aaronson blog post you linked, (syntactic) *consistency* means that there is no sentence $P$ such that both $P$ and its negation can be deduced from the axioms of the theory. (Syntactic) *completeness* means that either $P$ or $\neg P$ are deducible from the axioms. And *soundness* means that if $P$ is deducible from the axioms then it is valid under all possible models/interpretations of the axioms.

Consistency + completeness does not imply soundness because you could have a set of axioms and a theorem $P$ where $P$ is deducible from the axioms, $\neg P$ is not deducible from the axioms but there is some model of the axioms under which $P$ is false and $\neg P$ is true.

Aaronson gives an example in his post:

> If I believe that there’s a giant purple boogeyman on the moon, then presumably my belief is unsound, but it might be perfectly consistent with my various other beliefs about boogeymen.

"There's a giant purple boogeyman on the moon" is (perhaps) syntactically *consistent* with your axioms because you do *not* believe that "there isn't a giant purple boogeyman on the moon." Your axioms may be syntactically complete because they allow you to deduce at least one of the sentences "there's a giant purple boogeyman on the moon" or "there isn't a giant purple boogeyman on the moon." But in fact it is not true that "there's a giant purple boogeyman on the moon," so your deduction is unsound even though your axioms and deductive system are both consistent and complete.

The hardest concept in the above is probably *soundness*. Soundness relates the syntactic structure of your sentences and deduction rules to the *interpretations* (or *models* or *semantics*) of those sentences. A *model* of a language is a set, along with some relations and functions on the members of that set. For example, Gödel's *language* was the Peano axioms and the underlying *model* of the Peano axioms is the set of integers with (at least) an equality relation and a successor function. The Peano axioms are (I think) *sound*: if you can prove something with the Peano axioms then it is true of the natural numbers. But Gödel proved that the Peano axioms are not *complete*: there are sentences in the language of the Peano axioms that are in fact true of the natural numbers, but which are not derivable from the Peano axioms.
> 12 votes

---
Tags: terminology, logic
---


# Question
Title: Training and testing image sizes for classification in computer vision
When training a classifier for object detection using features extracted from images (eg HoG features), how important is it that the images used for training fed into the classifier in their natural aspect ratio?

For example, regardless of their aspect ratio, would a classifier work if all images were edited re-sized into squares of equal dimensions? (I know that OpenCV does this in its cascaded classifiers).

And if this is possible, then in the end, when we want to test the classifier, do we provide test images in their natural aspect ratio, or would the test images, too, have to be resized into squares?

# Answer
> 4 votes
It's important that all of the training and test images have the same aspect ratio but it doesn't necessarily have to be the natural one. If you think about it for a while you can see why that is. For example, if you're making a face detector and you have altered the aspect ratio to make all the faces look abnormally tall and skinny then you have a tall and skinny face detector. It won't work unless you do the same transform on the input images.

I'm not sure if I believe you about opencv making all the inputs to the cascade classifiers square. There is no reason it has to be square as long as all of the training images are the same size.

---
Tags: image-processing, classification, computer-vision
---


# Question
Title: Is there a name for defining recursive functions as an infinite list of input/output pairs?
Recursive functions are usually defined by directly calling a function inside its own body.

```
Nat = Z | S Nat
double Z = Z
double (S x) = S (S (double x)))

```

What if, instead of defining them this way, we just enumerated two recursive datatypes and zipped them?

To be more descriptive, mind the following functions/types:

```
enum Nat = [Z, S Z, S S Z, S S S Z ...]
elem (S S S Z) (enum Nat) = 3
[4,5,6] !! 1 = 5
zip [1,2,3] [4,5,6] = [(1,4), (2,5), (3,6)]
# a b = \x -> (zip (enum a) (enum b)) !! (elem x (enum a))

```

That is, `enum` enumerates elements of a recursive datatype, `elem`, `!!` and `zip` are just as defined by Haskel. Now, using #, there is an interesting way to define some recursive functions.

```
Even = Z | S (S Even)
double = Nat # Even

```

This makes `double` equivalent to:

```
double x = [(0,0),(1,2),(2,4),(3,6)...] !! x

```

In other words, instead of defining the function recursively, we just created an infinite list with the input/output pairs of that function, by zipping two recursive datatypes together. I never heard of this approach being used, so my question is: this there a name for this? Any relevant papers? What kinds of functions can be defined this way?

# Answer
Well it's the "set-theoritic" perspective of a function where a function from `A` onto `B` is really just the a subset of `A x B` where each `a` in `A` appears only once.

The problem is that some types are uncountable so enumerating them in this manner isn't possible; for some types a finite member may not be at a finite index.

Consider for example, how you would do this for `Double`.
> 1 votes

# Answer
For a function $f\colon D \to R$, the set $\\{(x,f(x)) : x \in D\\} \subseteq D \times R$ is known as the *graph* of the function. We can think of the graph as a sequence (ordered arbitrarily), and then we can say that the graph is *r.e.* if it can be recursively enumerated in some order. Assuming the function is total (and domain and range are both the natural numbers), the graph of a function is r.e. iff the function is computable.
> 0 votes

---
Tags: algorithms, computability, programming-languages, recurrence-relation
---


# Question
Title: Binary heap removal peculiar potential function analysis
Given the potential function $\phi$, it seems that remove max may take $O(1)$ amoratized, meaning that $n$ removals would take $O(n)$, which can't be, as it means we get a linear time comparison based sort if we build the heap in $O(n)$.

Where is the falling point in this potential function, and does it not give a $O(1)$ time guarantee and why?

\begin{align\*} \overline C\_i =& C\_i + \phi\_i-\phi\_{i-1} \\ \phi\_i =& \sum\_{a\in Heap}{depth(a)} \\ \end{align\*}

* meaning the potential function is the sum of depths of all nodes in the tree. \begin{align\*} C\_i &= \log n \\ \phi\_{i} &= \phi\_{i-1} - \log n \\ \overline C\_i &= \log n + \phi\_{i-1} - \log n - \phi\_{i-1} = 0 \end{align\*}

# Answer
Amortized analysis relies on $\sum\_{i=1}^n \overline{C\_i} = \sum\_{i=1}^n C\_i+\phi\_n-\phi\_0$ being an upper bound for $\sum\_{i=1}^n C\_i$. This requires $\phi\_n$ to be at least as large as $\phi\_0$. Your potential function does not satisfy this requirement, aince $\phi$ will get smaller with each step.
> 3 votes

---
Tags: heaps, amortized-analysis
---


# Question
Title: Why can't we solve the dinner party problem by finding a maximum matching?
Consider the following *dinner party problem*:

> Given a list of acquaintances, and a list containing all pairs of individuals who are not on speaking terms with each other, find the largest set of acquaintances you can invite to a dinner party such that you do not invite any two who are not on speaking terms.

I have read in Arora-Barak that is not possible to find an efficient solution for the dinner party problem. I'm confused because I thought that it was easy to solve with Edmond's Blossom algorithm (it finds a maximum matching).

This is what I thought (of course it must be wrong):

1. We create a graph where vertices are acquaintances, and edges are "not on speaking terms with each other".
2. We exchange vertices with edges.
3. We find a maximum matching, and these edges are the guests I can invite.

EDIT: I explain it better:

1. We create a graph where edges are acquaintances and vertex are "not on speaking terms with each other" If the resulting graph has edges at the ends (it could be possible) we add extra vertex at these ends.
2. We find a maximum matching, and these edges are the guests I can invite.

But I'm not sure why I'm wrong.

# Answer
The problem is that you can not model all instances of the problem in the way you suggest: A person can be 'not on speaking terms' with arbitrarily many other persons, but an edge in a graph can only be connected to two vertices. So instances where someone doesn't want to speak to 3 or more other people cannot be modeled.
> 7 votes

---
Tags: algorithm-analysis, matching
---


# Question
Title: Finding a graph-theoretic representation of expressions in Boole's algebra
I just read "Boole's Algebra Isn't Boolean Algebra" by Theodore Halperin (behind a paywall here). I don't have a strong background in abstract algebra, so, frankly, the paper is a bit over my head but the gist of it is as follows: the algebra developed by Boole in the 19th century has some strange properties. Boole interprets every term in an expression as representing a set and restricts the domain of valid expressions on the basis of relationships between the underlying sets. In particular, he asserts that the expression $x + y$ is valid iff $x$ and $y$ represent disjoint sets, and $x - y$ is valid iff the intersection of $x$ and $y$ is nonempty. He also defines an operation $w = \frac x y$ such that $w$ has many solutions. Halperin goes to great lengths to construct a commutative ring that satisfies Boole's constraints.

I think that there might be a nice, intuitive, graph-theoretic interpretation of Boole's algebra where we can say something like "Given a complex expression in Boole's algebra, $\Phi = \\{\phi\_1, \phi\_2\\, \dots, \phi\_n\\}$, we can construct a (di)graph $G$ such that $\Phi$ is valid if and only if $G$ has some property $P$."

For example, to test if $X + Y$ is valid, we could do something like the following:

Let $G$ be a graph. Let $V(G) = X \cup Y \cup \\{v\_X, v\_Y\\}$, i.e. make a vertex for every element of the underlying set, plus a vertex for each term in the expression. Then define

$$E(G) = \\{uv\_X \mid u \in X \\} \cup \\{uv\_Y \mid u \in Y \\}$$

and let $\partial(G)$ be the set of all valid bonds formed by subsets of $V(G)$. It follows that $X + Y$ is valid if and only if $|\partial(G)| = 2$.

From there, I'm not sure how to go about forming graphs for complex expressions like $\frac {y(x + z)} {z^2 + 1}$ by composing simpler graphs. I imagine that there is literature about representing Boolean algebra on graphs, but I haven't been able to find it.

Does anyone have an elegant interpretation? Or a pointer to relevant literature that might get me started?

EDIT: I can't find the article for free anywhere, but wikipedia touches on the issues:

> In places, Boole talks of terms being interpreted by sets, but he also recognises terms that cannot always be so interpreted, such as the term 2AB...Such terms he classes uninterpretable terms...uninterpretable terms cannot be the ultimate result of equational manipulations from meaningful starting formulae.

Halperin's paper shows that his algebra is isomorphic to "a commutative ring with unit having no additive or multiplicative nilpotents." I think, for that reason, that it will require heavier machinery to represent than normal Boolean logic operations.

# Answer
> 2 votes
A bit of shameless self-promotion, but you might find http://www.sciencedirect.com/science/article/pii/0895717794001669 relevant, as well as the earlier paper I cite there by Frank Harary.

Those papers present the idea that a boolean function can be represented as a hypercube in which the vertices represent combinations of truth values. That is, rather than construct a graph with a vertex for each boolean variable X, Y etc, construct a graph where one vertex represents the tuple `<X=0,Y=0>`, one represents `<X=0,Y=1>` etc.

---
Tags: graphs, logic, boolean-algebra
---


# Question
Title: Reason for differences between ways of specifying trees
Might be an odd question but how is it that when you specify a tree using an adjacency list emphasizing leafs first you state only need state 0 or 1 parent for each node but when you define a tree in another matter, emphasizing the root first (moving inward), you must specify any number of child nodes for each node? Seems like the second method requires more data to specify the same tree than the first. Or perhaps that’s not the case for all trees?

# Answer
> 1 votes
You're right. You need less space to save a tree with an adjacency list. But (like Dave Clarke's comment already says) there are more interesting fields, not only the space-complexity. Sometimes it is useful to spend more space to reduce for example the time-complexity of a problem. An easy example makes that point clear: If you represent your tree by saving the children of each node, you can compute the children of a given point in constant time (just looking which children are saved for the particular node). If you otherwise save the parent of each node, then you have to check every node in your tree (except the given point) to compute the children of a given node. In the first case you need more space and less time. In the second case you need less space, but more time.

# Answer
> 1 votes
Not all is space/computing complexity. Trees are useful for *modelling* problems (and their solutions). Say you have several alternative courses of action, and after deciding on one of them, you get offered another selection, and do on. This is naturally modelled by a tree with a root (your starting point) and branch points where the number of decendents aren't necessarily the same. The decendents aren't even in any particular order (you can set up a list of the alternatives, but that is an artificial, externally imposed, order). This is your conceptual model, which you probably would represent concretely as a rooted, ordered tree (children are in a particular, arbitrary, order), and you might decide to store that as a linked data structure of nodes with first child, next sibbling pointers.

---
Tags: trees
---


# Question
Title: Recognizing a language given an automaton
I'm trying to figure out which language can be recognized in this automaton

Automata http://cdn.imghack.se/images/64b81d259a1d403b810dd9744dc222f7.jpg

According to Wikipedia here "The language L ⊆ Σ\* recognized by an automaton is the set of all the words that are accepted by the automaton."

So using what Wikipedia states and knowing that this automaton is a finite state automaton, I would dare to say that this automaton accepts regular languages.

If I would use *M* to define this automaton then I could say:

The language recognized by *M* is the regular language given by a certain regular expression.

But I'm having a a hard time figuring out the regular expression.

I'm not sure of about this but here is what I think the regular expression looks like

$$ L = (a|b)(a|b)^\*a^\* $$

I would appreciate any help in this matter

# Answer
In general, there is a dynamic programming algorithm for converting finite automata into regular expressions. But this one is simple enough that we can eyball it.

From the start state, we have two choices. So we can see our expression has the form *|* where _ represents the parts of the expression yet to be filled in.

Let's look at the top branch. There we must read two a's, then as many a's or b's as we want. So this part will have the form aa(a|b)\*

For the second half, we see we must read at least one a or b. Then we can loop on a or b as many times a we want, and then we must read two a's. So we get (a|b)(a|b)\*aa

Notice the patterns here. When we have more than one transition coming out of a state, that represents the "|" operation. A transiton on "a,b" is equivalent to having one transition on a and another on b.

So, our final expression is (aa(a|b)\*) | ((a|b)(a|b)\*aa).

Any time we have a cycle, either on a particular state, or on a path of states, we get something corresponding to \*. And every time we have to read something in sequence, we have concatenation.
> 3 votes

# Answer
~~Minimise the Automaton, as it is a Finite Automaton, so we can apply the method of minimising states. The RegEx will be formed that describes the language recognised by this automaton.~~

Edit: this answer seems to be wrong, please refer to David's comment below.
> -2 votes

---
Tags: automata, finite-automata, regular-expressions
---


title: comparisons vs arithmetic complexity

text:
# Question
Title: comparisons vs arithmetic complexity
I'm trying to find out which operation is fast, evaluating a comparison vs doing an arithmetic option on a single word (e.g subtract, add). Can anyone point me in the right direction with some blogs, books and other material?

# Answer
> 2 votes
It principle it could depend on the processor. However, I imagine that comparison are done using the same circuitry as subtraction, so the complexity should be comparable. I'm assuming that by *comparison* you mean an instruction comparing two registers and setting some flags (or another register). A conditional jump might interfere with pipelining and so would be costlier.

---
Tags: algorithms, complexity-theory, reference-request
---


# Question
Title: Can we represent all computer programs as graphs?
I was thinking the other day, and it occurred to me that computer programs all seem to be representable as a graph (an abstract syntax tree for example), or, once common expressions are combined, an abstract syntax graph.

It occured to me that perhaps any computer program can be represented as one of these graphs + evaluation semantics attached to it. I'm curious if anyone knows if this is universally true for a turing machine (I assume you can get a potentially infinite graph, but this is math so that's OK). I've been pondering on it and a lot of things like strong type systems and such fit well in this abstraction (they impose structural constraints on the graph). You might even be able to consider the type system its own program and represent *that* as a different graph + evaluation semantics operating on the program graph...

Just curious if this is a known equivalence or not.

# Answer
I don't know if it's a particularly well known equivalence, but it's fairly simple when you think about it.

Turing Machines are known to be equivalent to the (untyped) Lambda Calculus. The Church-Turing thesis proposes that this is they are the most powerful form of computation.

The Lambda Calculus is a syntactically defined term re-writing system. Essentially, it's a very simple programming language. So, it can be parsed into an abstract syntax tree (graph).

So, we have:

1. Every computer program is representable in the untyped lambda calculus.
2. Every lambda calculus program can be parsed into an abstract syntax tree

This means that every computer program can be represented as a Lambda Calculus abstract syntax tree.

These trees might not have much in the way of interesting properties. For example, they're definitely not unique i.e. two different trees can perform identical computations.
> 11 votes

# Answer
yes there is a close connection between graphs and programming in quite a few areas. the simplest way to picture this is as loops, branch, or subroutine entry points in code as destinations in a directed graph. see also

see also Visual Programming languages cs.se
> 2 votes

---
Tags: graphs, turing-machines, machine-models
---


title: Eliminating Left Recursion

text:
# Question
Title: Eliminating Left Recursion
Hello I have the above Context Free Grammar and I try to eliminate the left recursion so I can pass it to a tool. Any techniques I've read so far doesn't help me so a little help would be appreciated.

```
exp  ->   num | exp op exp | (exp)
op    ->   + | - | * | /

```

I don't have the slightest idea on how to proceed. The only technique I've seen on the internet is to transform a CFG where the symbol appears once with another one and not twice or anything like below.

```
foo->foo a
     | b

```

which can be transformed:

```
foo-> a bar
bar-> b bar
    | epsilon

```

# Answer
Given a grammar $ G=(V,\Sigma,P,S)$ You can eliminate left recursion with the following algorithm:

Let $ A \rightarrow A\alpha\_1 | A\alpha\_2|...|A\alpha\_n$

be the left recursions of a variable $A$, and $ A \rightarrow \beta\_1 |\beta\_2|...|\beta\_m$ such that each $ \beta\_i$ doesn't starts with $A$ (meaning $\beta\_i \notin A\left \\{ V \cup \Sigma \right \\}^{\*}$

We will construct a new grammaer $G'=(V\cup \left \\{ B \right \\} , \Sigma, P\_1, S )$ by replacing all the left recursion derivations of $A$ with the following rules:

$A \rightarrow \beta\_i \\: |\\: \beta\_i B$ for $1\leq i \leq m$, and

$B \rightarrow \alpha\_j \\: |\\: \alpha\_jB $ for $1\leq j \leq n$

You can show that $L(G) = L(G')$

Applying this algorithm on your grammar yeilds the following rules:

$ exp \rightarrow num \\: |\\: num\\: B \\: |\\: (exp) \\: | \\: (exp)\\: B $

$ B \rightarrow op \\: exp \\: | \\: op\\: exp \\: B $

$op \rightarrow + \\: |\\: - \\: |\\: * \\: |\\: \\: / $ (as before)

(Note that your example is wrong, it should be that $foo \rightarrow b \\: \\: bar$)
> 2 votes

---
Tags: context-free
---


# Question
Title: Choose $n/2$ vertices and guarantee $3/4$ of edges are accounted for proof
Give a polynomial-time algorithm that finds ceil(V/2) vertices that collectively account for at least three-fourths (3/4) of the edges in an arbitrary undirected graph.

The algorithm I have come up with is a greedy algorithm that iterates through the graph choosing the node with the largest number of incident edges and then updating the adjacent vertices with their new incident edge count.

I am fairly confident this algorithm will work, however I am struggling with the proof that I will always account 3/4 of the edges.

What I have so far is that because the sum of the degrees of all the edges in the graph is equal to 2E then on average every node will contribute at least a degree of 2E/*n* to that summation. 2E/*n* x *n*/2 vertices provides me with just E. Is this correct or am I missing something?

# Answer
I'm not sure your algorithm works. Here is an algorithm that does work: choose $\lceil V/2 \rceil$ random vertices. You can calculate that each edge is chosen with probability at least $3/4$, and so the expected number of chosen edges is at least $3/4$ of all edges.

This algorithm can be derandomized (made deterministic) using the method of conditional expectations. I suggest you read about the method and work the details out. You will get something very similar to the greedy algorithm you're suggesting, but I suspect there will be some subtle differences.
> 2 votes

---
Tags: graphs, proof-techniques
---


# Question
Title: Reducing 3-colouring to planar 3-colouring
I was reading these lecture notes and I'm trying to understand how one would formally describe reducing 3-colouring to planar 3-colouring. The link pretty much describes the process but understanding the mathematical formalism is a bit over my head. In short, it seems that every edge crossing is replaced with some new graph. How does this work?

# Answer
> 5 votes
The idea is simple. Given an arbitrary graph embedded in the plane, what might make it non-planar is that edges could cross. By slightly perturbing the planar embedding (where we put the vertices), we can ensure that no more than two edges meet at a point.

The idea is to replace each crossing with a certain planar gadget $W$, which functions as a cloverleaf. The four vertices on the outside of the gadget consist of a horizontal pair $x\_1,x\_2$ and a vertical pair $v\_1,v\_2$. The gadget has the property that in any valid 3-coloring $c$, $c(x\_1) = c(x\_2)$ and $c(v\_1) = c(v\_2)$, and vice versa, for each choice of $c(x\_1) = c(x\_2)$ and $c(v\_1) = c(v\_2)$ there is such a coloring.

How do we use this gadget? Suppose that the graph has exactly one crossing, the edge $(a,b)$ crossing the edge $(r,s)$, we put a copy of the gadget with $x\_1 = a$ and $v\_1 = r$. The gadget ensures that $c(x\_2) = c(a)$ and $c(v\_2) = c(r)$, so if we connect $x\_2$ to $b$ and $v\_2$ to $s$, the new graph is 3-colorable iff the original one is (I encourage you to draw this, consulting the lecture notes). Plus, the crossing has been replaced by the gadget, which is itself planar.

The general case is more complicated but of the same spirit, and you can read about it in the proof. The idea is to replace each crossing with a copy of the gadget; two adjacent crossings on the same edge share vertices, as illustrated on page 124 of the lecture notes.

The difficult part in coming up with this reduction is constructing the gadget. The idea itself is pretty natural, and it is somewhat surprising that it can be made to work.

---
Tags: algorithms, graphs, np-complete
---


# Question
Title: Build a regular expression to define a regular language
The language is an infinite set of chains that are defined by the next conditions.

Conditions:

```
1) The language chains may consist of symbols from the set {1,a,b}.
2) The language chains always start from subchain '1a'.
3) Every languange chain has to include at least one subchain 'aa'.

```

For example:

```
1aa, 1abaa, 1aaab, 1aab1a, ... etc.

```

My current solution is this:

```
1a ((1+b)* a)* (a (1+b)*)* a (1+b+a)*

```

My solution seems to pass tests like these:

```
Allowed chains    : 1aa, 1aaa, 1abaa, 1aaba, 1aabaa, 1aab, 1aaab, 1aaabaaa
Not allowed chains: 1aba, 1abab, 1ababab

```

But I'm not quite sure if it's still correct. Is it correct?

If not, please offer your solution using only the type of formal language used in my solution.

# Answer
One way to do it by hand, in such a simple case, would be to build a FA for condition 2, i.e. strings that start with $1a$, and another FA for condition 3, i.e. strings that contain $aa$. Both FAs have only 3 states.

Then you use the intersection construction to have an automaton that obeys both conditions. That remains simple enough if you organize your state pairs as a 3 by 3 matrix.

From that you can easily deduce a regular expression: $1(a+a(a+b+1)^\*a)a(a+b+1)^\*$

Your solution can be proved consistent (compliant with the stated conditions) with a case analysis over the two main star operators (cases depending on whether there is zero occurrence or at least one). One also has to prove it is complete, i.e. that it does cover all compliant strings.

If you have a constraint regarding the use of parentheses, you should state it in your question. Is there a reason for the constraint ?

Find more details in the answer to your other question about this language, and a comment on how to better write the question.
> 1 votes

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


title: Convert regular expression to Automaton

text:
# Question
Title: Convert regular expression to Automaton
I'm trying to construct a finite-state automaton from the following regular expression:

$$ (a|ba)(a|ba)^\*(b|ab)^\* $$

I know that from $$ (a|ba) $$

the automaton should look something like this:

automaton http://cdn.imghack.se/images/5ab1437745d2a53d4630619819074d6c.jpg

from $$ (a|ba)^\* $$

it should look like this I guess:

automaton2 http://cdn.imghack.se/images/e1dc6ac63c6d967086d1f40aebf62c51.jpg

and from $$ (b|ab)^\* $$

is pretty much the same as the last one, the thing is I don't know how to unite them in one automaton.

I would appreciate any help in this matter

PS: I'm sorry for the images I'm still learning how to work with the automata editor jflap...

# Answer
Regular expressions can be turned into (nondeterministic) finite automata very easily. What your automata are missing are start- and final states.

Once you have marked those, its very simple: If you have the automaton $A\_1$ for $(a|ba)$ and $A\_2$ for $(a|ba)^\*$, to get an automaton for $(a|ba)(a|ba)^\*$, just add $\varepsilon$-transitions from all finite states of $A\_1$ to the start state of $A\_2$. (This is btw part of the Thompson-construction, in case you want to look it up :) ) If needed, you can then remove all $\varepsilon$-transitions.

If you directly want to construct a $\varepsilon$-free NFA, you can use Glushkovs construction.
> 1 votes

---
Tags: automata, finite-automata, regular-expressions
---


# Question
Title: Reducing A(TM) to some decidable problem
We know that A(TM) is undecidable, what if we reduce A(TM) to A(DFA) which is decidable? How will we prove that A(DFA) is decidable?

I couldn't find an example or theory.

Thanks

# Answer
$A(TM)$ is undecidable because a Turing machine can fail to halt on its input. $A(DFA)$ is decidable since a DFA must always halt on any input. We can always decide whether a DFA accepts some string just by running the DFA on the string and seeing whether the DFA ends up in an accepting state. Not so with a Turing machine.

It is extraordinarily unlikely that there is a valid reduction of $A(TM)$ to $A(DFA)$; that would be a bit like effectively demonstrating that triangles have actually always had 3.5 sides, not 3. If you've got such a proof you should buy as many futures in mops as you can, since there will be a lot of brain matter to clean up after all the computer scientists' and mathematicians' heads explode.

I suspect the real question may really be more about whether proofs of the form "A reduces to B. B is decidable. Therefore, A is decidable." are valid. The answer is that, as you probably expect, of course they're valid: if you ever find yourself needing to prove a problem is decidable, this is the gold standard way to do it. If you've never seen a proof like this, per se, the reasons could be either that the default assumption is that problems are decidable until proven otherwise, *or* because this proof method is tantamount to just designing an algorithm to solve the problem (in which case, it might not appear to be a proof of anything so much as a description of an algorithm).

To give an example: consider Bubble Sort. This can be viewed as a proof that the Sorting problem is decidable, since it reduces $Sort$ to $\\{GreaterThanOrEqualTo, Swap, Loop\\}$, which we know are decidable. All right, there's some hand-waving there, but you get the idea.
> 3 votes

# Answer
If you could reduce A$\_\text{TM}$ to A$\_\text{DFA}$, you would have shown that A$\_\text{TM}$ is decidable, which it certainly is not, so that approach won't work. To show that A$\_\text{DFA}$ is decidable, you need a decider, namely an algorithm that would take a DFA $M$ and a word $w$ and always correctly answer the question "does $M$ accept $w$ or not?" Put yourself in the place of the decider: if someone gave you a DFA and a word, how would *you* answer the question? That should give you the algorithm.
> 2 votes

---
Tags: computability, reductions, undecidability
---


title: Cost of partitioning in quicksort

text:
# Question
Title: Cost of partitioning in quicksort
I'm reading "Algorithms Fourth Edition" by Sedgewick & Wayne and am wondering if I have spotted an error in the book or if I just can't wrap my head around something so simple.

When talking about the complexity of quicksort, the book says that the cost of partitioning, measured in the number of compares, is equal to `N + 1`, where `N` is equal to the number of elements in the collection to sort. We are assuming here that we just choose the first element in the collection to serve as the partition.

My question is would the cost of partitioning not really be equal to `N - 1`? That is, that you choose an element to serve as the partition and you compare it with every *other* element in the array.

--

As requested, the partitioning process is defined as follows:

* The entry which will serve as partition is in its final place in the array.
* No entries in positions before the partition are greater than the partition value.
* No entries in positions after the partition are less than the partition value.

At this point I'm guessing it is in fact a typo...

--

The partitioning algorithm is outlined as follows

* Take the leftmost array element as the "partitioning item"
* Scan the array from the left until an element greater than or equal to the partitioning item is found
* Scan from the right until an entry less than or equal to the partitioning item is found
* When both a right and left item are found, exchange them
* Repeat until the scan indexes cross
* Once the scan indexes cross, exchange the partitioning item with the rightmost entry in the lower side of the array.

Note that the "cost" of the partitioning is being calculated in compares and not array accesses.

# Answer
> 3 votes
This is a pretty common version of partition and in this case you need N+1 comparisons.

For example consider an array containing ${1,2,\ldots,N}$.

Now, 1 is your pivot (partitioning item). pivot 1 is compared with first element 1 and it is greater than or equal it, so you got the left item. Here you need 1 comparison.

Then, pivot 1 is compared with $N,N-1,\ldots$. Note that the right item will be 1 as we want a number less than or equal to the pivot. Hence you need to compare 1 with all the elements $N,N-1,\ldots,1$. Thus here you need $N$ comparisons.

In total you need $N+1$ comparison.

In general we have two pointers one from left and one from right. pivot is compared with elements pointed by these two pointers. Left pointers moves towards right, right pointer moves towards left. Thus all the elements are compared with pivot at least once. But, one element is compared twice where the two pointers meet and cross. Thus we need $N+1$ comparisons.

---
Tags: quicksort, partitions, comparison
---


# Question
Title: Local and Global storage with multithreading pools + locking threads
I am having difficulty answering the following questions relating to the use of threading.

Question 1 is of relating to the possibility of a local storage per thread and a global storage accessible to all threads. Consider the following scenario; A program creates a series of threads each with their own local storage, kind of like a mutex system except for that no thread can access another's memory, and a square matrix stored in global storage which is accessible to all threads. When the space complexity of the following program is calculated, is the space complexity (# of elements in the square matrix)2 \+ (local storage of finishing thread) or (# of elements in the square matrix)2 \+ (local storage of all threads at the time that the finishing thread completed)?

Question 2 relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed?

Any help on the answering of these questions would be appreciated. Please comment if additional info is required.

# Answer
I will answer Question 1. As @DavidRicherby said, you should post the other question separately.

The *space complexity* is the *maximum* amount of space required while the algorithm is running. So it certainly would be more than the (number of elements in matrix) + (local storage of just finishing thread). It *might* be the total storage of all the threads at the time the program finished but only if (a) you haven't already exited any of the threads, and (b) none of the threads freed up a bunch of memory just before the program finished.

You also need to be careful to not overcount. As described here there are a lot of optimizations that allow you to reuse space, so you can't just sum up all the memory allocated by every thread that ever existed. You really need to figure out the point in time during your program execution when the most memory is in use.
> 0 votes

---
Tags: space-complexity, threads
---


title: Maximum Value Contiguous Subsequence

text:
# Question
Title: Maximum Value Contiguous Subsequence
I have stumbled upon this problem online:

> Given a sequence of n real numbers A(1) ... A(n), determine a contiguous subsequence A(i)... \> A(j) for which the sum of elements in the subsequence is maximized.

Now my solution is so: I assume that the sequence is stored in an array. We need 2 arrays under the original array, one is a flag array A and the other is a real number array B.

Take the first element as the subsequence we are searching for, put a 1 under it in A, and put the value of the element in it's index in B (which is right under it's index in A). Go to the next element. If it isn't negative, put a 1 under it in A, and put the sum of that element and the element before him in B. If it's negative, put a 0 under it in A, and go to the next element, starting a new subsequence.

The complexity is O(n) time because I run on the whole sequence once.

Example:

Sequence: 4 33 -24 3 4 2 -5 6 19 -11 32 40 -30 5 6
Array A: 1 1 0 1 1 1 0 1 1 0 1 1 0 1 1
Array B: 4 37 13 3 7 9 4 6 19 8 32 70 40 5 11

My question is: is that the wanted solution? and does it really run in O(n) time?

# Answer
Your algorithm does not yield the solution. An extension of your algorithm that follows will provide a solution. You need to mark the extremes of consecutive 1's in the flag array (an obvious observation ). For example, the flag array is 1111101111 then you need to mark 0,5,9 indices (zero based) and for every pair of extremes you need to find the difference computed in prefix sum array. The number of marker indices are of the order of n. So number of pairs are of the order n^2.
> 3 votes

# Answer
Here is another suggestion. Given the original array $A\_1,\ldots,A\_n$, define a new array $B\_0, B\_1,\ldots,B\_n$ by $$B\_i = \sum\_{j=1}^i A\_j. $$ This is useful since $$\sum\_{j=i\_1}^{i\_2} A\_j = B\_{i\_2} - B\_{i\_1-1}. $$ So now we want to find the maximum value of $B\_{i\_2} - B\_{i\_1-1}$. The idea is to scan the array from left to right, keeping track of the optimal choice of $i\_1$ at any given moment. I will let you fill in the details.
> 0 votes

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


# Question
Title: How can OS schedule disk requests efficiently without knowing the LBN to PBN mapping ?
I learn from the OS schoolbook that the OS has the function that schedule the disk requests with the knowing algorithms such as SSTF, SCAN .. However, the date layout inner disk drives now is very complex that we may can't know. Disk zoning, disk skew, disk slipping and many other features of disk drives changes the distribution of data layout. So how can the OS do this work ? Thanks!

# Answer
Modern disks interfaces provide an approximation of position called the *logical base address*. This is just a linear integer indexing scheme where each block gets a unique integer assigned to it.

While you can't calculate an exact "distance" (in terms of arm movement latency and rotational latency) between two blocks it is approximately the case that if the difference between address $a$ and address $b$ is smaller than the distance between address $a$ and address $c$ then block $a$ will be closer to block $b$ than it is to block $c$.

Disk scheduling algorithms try to improve average latency or average throughput without being significantly unfair or causing starvation. They also don't know about requests that are going to arrive in the future, so whatever they do needs to be an approximation based only on the requests they've already seen.

Since the algorithms are approximate anyway, the fact that we don't know the exact distance between two requests is not particularly a problem.
> 1 votes

---
Tags: operating-systems, scheduling
---


# Question
Title: Shortest path in weighted(positive or negative) undirected graph
I have to find an algorithm that finds the SSSP (single-source shortest path - shortest paths from one source vertex to all other vertices) on a weighted undirected graph. If there are 2 different shortest paths, the algorithm should prefer the one with less edges on it. The time complexity of the algorithm is $O((|V|+|E|) \log |V|)$.

So, I tried:

* My first thought was DFS/BFS (the $O(|V|+|E|)$ looks tempting), but (I believe) no modification of these two algorithms works on weighed graphs.
* Then I thought about Dijkstra's algorithm - but that one doesn't work on graphs, which can have negative edges.
* My last hope was Bellman-Ford algorithm, which could work I guess, but I have no idea, how to rewrite it for undirected graphs.

Any hint is appreciated.

# Answer
A generic scheme to make an undirected graph directed is to replace each of its edges by two directed edges with same weight as the original weight of the edge. For an undirected edge $(u,v)$. Replace it by two directed edges $(u,v)$(direction u to v) and $(v,u)$(direction v to u). The weight of both of these edges are same as weight of undirected edge $(u,v)$.

Thus the algorithm which you have in mind for solving directed SSSP can also be applied on undirected graph with the above mentioned changes.

And, a good way to get a shortest path with smallest number of edges is to add a small constant weight ($\epsilon$) to all edges. Note that if we have two shortest path having $x$ and $y$ edges ($x \> y$) before, then adding small value to all edges changes the weight of the shortest path with $x$ and $y$ edges by amount $x\epsilon$ and $y\epsilon$. As $x\epsilon \> y\epsilon$, now the shortest path with $y$ edges is having lesser cost. Thus after changing the edge weight by a very small amount you can apply your favorite SSSP algo to get the path with minimum number of edges. Note that as $\epsilon$ is very small a path which was not shortest before can't be shortest after changing the weights.
> 3 votes

# Answer
After making the graph undirected, you can use Johnson's Algorithm, which works by using the Bellman–Ford algorithm to modify the input graph removing all negative weights, allowing Dijkstra's algorithm to be used on the resultant graph. It has a time complexity of $O(V^2 \log V + VE)$, which is better than Floyd-Warshall alone!
> 1 votes

---
Tags: graphs, shortest-path
---


title: Timing threads in an algorithm

text:
# Question
Title: Timing threads in an algorithm
This question relates to timing threads to go at a very precise rate. Consider the following scenario; A program creates a series of threads that continually add a random set of elements to their local storage. The program finishes and returns the thread that received the shortest number of elements in its random set. If one thread was to go faster than another, the program would be incorrect. Is there a way to "lock" the threads to go at the same speed? If so would it be possible for someone post a quick python or other language script that performs this task?

If more info is needed, please post

# Answer
> 1 votes
You are probably looking for a barrier synchronization primitive. Each thread calls into the barrier when it is done creating its set. Only when *all* the threads have called into the barrier are any threads permitted to proceed.

If your programming language doesn't include a barrier primitive, then you can fake it, in your example, simply by having the main thread sit in a loop and join with all the children thread as the children finish and return from their computation. The loop should only exit when it sees every child thread finish.

---
Tags: algorithms, threads
---


# Question
Title: Efficient set data structure supporting insert and set equal
What's the best way to represent sets that support the following two operations:

1. Insert(s, i) - adds nonnegative integer i to set s
2. Equal(s1, s2) - Tests if s1 and s2 are the same set.

In addition, I have an upper bound on the integers added to each set. That is, I know $N$ such that $0 \le i \< N$.

I'm also willing to accept that Equal is only approximate. ie Equal(s1,s2) could be true even if s1 != s2. I guess in that case I'm looking for a hash function. Does anyone know a good hash function?

We can assume that an integer is only inserted once into a set. $N$ can be about 3-5 million, and the number of sets I want to test for equality can be in the thousands.

# Answer
> 2 votes
Let $F$ be a finite field with efficient procedures for addition and
multiplication and almost-uniform sampling. $\\:$ Let $z$ be a field element.
(I use that letter because things will be slightly more convenient if $z$ is
the zero element, although efficient sampling means that even if one
can't find the zero of $F\hspace{-0.03 in}$, one should still be able to find *a* field element.)

To initialize the data structure, sample a field element $x$.
Empty sets are represented by $z$, `Insert(s,i)` adds $x^i$ to the representation of s,
and `Equal(s1,s2)` just tests if the two representing field elements are equal.
Since addition is associative and commutative, there are no false negatives. $\\:$ If each integer is only inserted once into a set, then the probability of there being at least one false positive is at most
the distance from $x$'s distribution to uniform $\\;+\\;$ $((N\cdot \text{number of equality tests})\hspace{.02 in}/($$\hspace{-0.03 in}\operatorname{card}$$(F\hspace{.03 in})) \\;\\;$.

To efficiently compute $x^i\hspace{-0.04 in}$, see this paper, and either avoid the methods that involve negative
powers or make slightly stronger assumptions on $F$. $\\:$ I would recommend 5.1 on page 14.

# Answer
> 1 votes
If you are not allowed to add the same value more than once, then the insert operation can add the hash value of $i$ to some accumulator associated with $s$, and the equality testing can compare the accumulators.

If you are allowed to add the same value twice, you can use Bloom filters.

# Answer
> 1 votes
Assuming $N$ is not too large, consider using a bitvector. For example, you can use a single integer type as a data structure, or an array of bits. Insertion can be done in constant time, and equality checking is very fast as well.

# Answer
> 1 votes
I'll add an additional suggestion based on @Mihai's answer to this similar cstheory.se question.

If each object in the set has a unique hash, then any commutative operation on the hashes of the members of the set will produce a decent insertion-order independent hash of the entire set. @Yuval's Bloom filters can be viewed as using the bitwise "or" operator. @Juho's approach is also using the bitwise "or" operator and the element hash is just the "one-hot" encoding of each member of the set. @Mihai is suggesting that the encoding of a member $i$ of the set be $a^i \mod p$, for some preselected $a$ that is relatively prime to $p$, and that the commutative operator be addition $\mod p$. If $p$ is larger than $N$ then the probability of a false equality between two different sets is $O(N/p)$ (according to @Mihai's answer). I'm sure that there are situations in which bitwise "xor" works as the commutative operator too.

# Answer
> 0 votes
for bitvectors the number of items is not really important, 5 million bits can be stored in 1 megabyte. you should look at the total length of the biggest number or find a mapping into smaller numbers.

For comparison you can calculate the hash over this bitvector.

---
Tags: data-structures, hash, equality
---


# Question
Title: How to explain rehosting and retargeting with T-diagrams?
I'm currently learning for an exam about compilers and found the following question:

> (3 p.) **Bootstrapping**: Explain the concepts of *rehosting* and *retargeting*. Use T-diagrams.

As far as I understand, rehosting means to compile a compiler for another platform (host), so it should look like this:

```
-------------
| a       b |     --------------
-----   -----     | a        b |
    | c |-------------    ------
    -----| c       x || x |
         -----   ----------
             | ? |
             -----

```

Is this correct? And what does retargeting mean?

# Answer
`Retargeting` refers to having the compiler generate code for a different CPU or instruction set.
A different CPU would be X86 vs PowerPC.
A different instruction set would be ARM vs THUMB or x86 vs x86-64 (same CPU, but different mode).

`Rehosting` means running the code on a different machine than the code was compiled on.
The new machine usually has the same architecture.
Rehosting need not be trivial, because e.g. the filesystem may look different on the compiler system.

See: http://www.cs.southern.edu/halterman/Courses/Spring2009/425/Slides/ch11.pdf

> Retargetability
> Easily modified to generate code for a different target language
>
> Rehostability
> Easily modified to run on a different machine

Collectively the two terms are often combined in the term `portability`.
Code that is portable is not tied to an architecture *(target)* and not tied to the setup of a specific machine *(host)*.

**refering to your question**
Rehosting does **not** mean compiling for another platform!
Retargeting is compiling for another platform.
Rehosting is moving your program to another computer (same platform) *(and keeping your fingers crossed to see if it works)*
> 1 votes

# Answer
`?` should be replaced by `x`, see these lecture notes.

Rehosting: your target machine is fixed and you simply run the compiler to achieve the machine code. Example, a C compiler for intel x86 processor.

Retarget: you want flexibility for your compiler and need to cross-compile it using another compiler and therefore, "Target" it for different machine than which was originally intended for.

(I am feeling a bit strange as this is how I have justified the lecuture to myself :P). For all intents and purposes, I am more than happy to get a slap on the wrist for a wrong answer :
> 0 votes

---
Tags: terminology, compilers
---


# Question
Title: Situations where Kleene star of A is context-free, but A is not
This question appeared on my Theory of Computer Science final:

True | False: $A^\*$ is context-free $\implies$ $A$ is context-free.

My professor says the answer is false, and I believe him, but am having trouble constructing a counterexample or even just convincing myself why. It seems to me that if a grammar can describe repeated concatenation, there must be some nonterminal that is concatenated.

Does anyone have a counterexample?

# Answer
> 8 votes
Let $L$ be any non-context-free language, then we can construct the language $A = \Sigma\cup L$ - i.e. $A$ is either an element of $\Sigma$ or a string from $L$ (these can happily overlap too). This is clearly not context free either (if it were, then we would have a PDA for it, and we can easily modify this PDA to recognise $L$).

If we now take $A^{\ast}$ however, we get $\Sigma^{\ast}$, which is most certainly context free.

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


# Question
Title: Hilbert's 10th Problem and Chaitin's Diophantine Equation "Computer"?
In Chaitin's *Meta Math! The Quest For Omega*, he briefly talks about Hilbert's 10th Problem. He then says that any Diophantine Equation $p=0$ can be changed into two equal polynomials with positive integer coefficients: $p=0 \iff p\_1 = p\_2$.

Then he says that we can think of these equations like a "computer":

> **Diophantine Equation Computer**: $$L(k,n,x,y,z,...)=R(k,n,x,y,z,...)$$ **Program:** $k$, **Output:** $n$, **Time:** $x,y,z,...$

With left side $L$, right side $R$. He says $k$ is the program of this computer, which outputs $n$. He also says that the unknowns are a *multi-dimensional time variable*.

What confuses me is that he then says that Hilbert's 10th Problem is clearly not solvable when viewed in this way. He basically says "because of Turing's Halting Problem". But I don't see the connection (I'm just beginning to learn the theory). I was hoping someone could more clearly explain what Chaitin's point is here.

I know that Turing's Halting Problem basically states that you cannot predict when a program will halt before it actually halts (given a finite amount of time). What is the application to Hilbert's 10th Problem, using the notation laid out by Chaitin?

# Answer
> 9 votes
Good question. It sounds like you might need some additional background on Hilbert's 10th Problem. I hope this isn't overkill.

The problem asks:

> Is there an algorithm that, given a Diophantine polynomial, decides whether or not there is a setting of its variables that makes it equal to $0$?

This was resolved in the 70's as a consequence of the MRDP (also called Matiyasevich's theorem, if you feel like searching it) which states:

> Define: A set $D \subset \mathbb{N}$ is *Diophantine* if there is a Diophantine polynomial $p$ on $k+1$ inputs such that $D = \\{ x \\, | \\, \exists y \in \mathbb{R}\_+^k \\, p(x, y) = 0\\}$.
>
> The Diophantine sets are precisely those that are recognizable by Turing machines.

This theorem is obvious in one direction (every Diophantine set is recognizable by a Turing Machine -- on input $x$, simply have your machine start guessing vectors $y \in \mathbb{R}\_+^k$, evaluate $p(x, y)$, and halt if/when you find that $p(x, y) = 0$). It is very non-obvious in the other direction -- why is it true that every Turing recognizable set is Diophantine? The encoding schemes are disgusting, but trust me, it can be done.

Anyways, how does the MRDP theorem resolve Hilbert's 10th problem? Well...

For the sake of contradiction, let's pretend we have an algorithm that, given a Diophantine polynomial $p(y)$, decides whether or not there is an input vector $y$ that causes $p(y) = 0$.

Now I'm going to use this magical algorithm to solve the halting problem. Given a machine, I will use the disgusting encoding of Diophantine equations to convert the problem "Does $M$ halt on input $x$?" into the problem "Does the Diophantine polynomial $p(y | x)$ have a set of inputs that make it equal to $0$?" Then I will use my magical algorithm to solve this problem, and now I have solved the halting problem.

Of course, this is impossible, so in reality there can't be a magical algorithm that searches for an input vector that causes $p(y) = 0$. Similarly, there can't be an algorithm that looks at two Diophantine polynomials and decides if they're ever equal. That's what Chaitin is saying.

---
Tags: logic, halting-problem
---


# Question
Title: Deciding the set of all Turing machines that halt in at most $k|x|$ steps $\forall x \in \Sigma^*$
Let $L = \\{ \<M\> | M$ halts on every input $x$ in at most $200 * |x|$ steps $\\}$.

Is $L$ decidable? Recognizable?

Given that membership in $L$ asserts something about $M$'s behavior on an infinite set of strings, it seems extremely unlikely to me that $L$ could be either. I have shown that co-$L$ is Turing-recognizable (I think): you can make an enumerator that tests each $M\_1, M\_2, \dots, $ for each $s\_1, s\_2, \dots$ and emits $M$ if it does not accept some $s$ in at most $200|x|$ steps.

Since co-$L$ is recognizable, either $L$ is not recognizable, or it is decidable. I can't imagine that $L$ is decidable. However, it definitely cannot be reduced to the halting problem, nor can Rice's theorem be applied to it (since the quality in question is the quality of halting in a particular number of steps, being able to decide it doesn't let us decide other arbitrary properties).

It seems to me that the best way to go will be to show that $L$ lets me recognize something that is unrecognizable, since the only problems it solves are ones which require me to run over infinite sets of strings. But I can't think of what this could be. I thought that maybe co-HALT would work, but I can't ever prove that a TM will never halt on some input.

I'm stuck. What direction should I go in?

# Answer
The language is actually decidable, but the proof is quite involved, and uses crossing-sequence arguments. See this paper for details.

If you change $200|x|$ to a faster growing function, such as $|x|\log |x|$ (plus some constant), then the language becomes undecidable by standard reduction arguments.
> 6 votes

# Answer
This answer is wrong. I'm leaving it here since this sort of argument is the natural way to go, and does work for faster growing functions, as mentioned in Shaull's answer.

Hint: Let $M$ be a machine having no input. Define a new machine $M'$ as follows: on input $x$, $M'$ simulates $M$ for $f(|x|)$ steps, where $f(t)$ is a function tending to infinity such that the simulation takes less than $200 t$ steps. If $M$ ever halts, then $M'$ switches to an infinite loop. When is $\langle M' \rangle \in L$?
> 2 votes

---
Tags: computability, turing-machines, undecidability, decision-problem
---


title: Understanding Monte Carlo Probabilities

text:
# Question
Title: Understanding Monte Carlo Probabilities
I am trying to get a good grasp on Monte Carlo (MC) algorithms, but I feel I am missing something fundamental.

What I don't understand is how MC improves its confidence of giving the correct solution by running more executions.

So please correct me if I am wrong and assume that $Pr\[false\] \leq 0.5$. Assume we need to find the number of executions so that $Pr\[false\] \leq 0.125$, thus improving confidence.

Is it true that the number of needed executions is $3$, since $0.5^3=0.125$?

Thanks in advance...

# Answer
This is the idea of *probability amplification*, in which one improves the probability of correctness of the algorithm by running it multiple times. You are talking about Monte-Carlo algorithms which have **one-sided** error. Lets take an example (from Wikipedia) having such a similar feature :

> The Solovay–Strassen primality test is used to determine whether a given number is a prime number. It always answers true for prime number inputs; for composite inputs, it answers false with probability at least 1/2 and true with probability at most 1/2. Thus, false answers from the algorithm are certain to be correct, whereas the true answers remain uncertain; this is said to be a (1/2)-correct false-biased algorithm.

The probability that the above algorithm returns an incorrect answer is thus at most 1/2. Now, the key idea is to understand that successive runs of the algorithm produce answers that are *independent* of each other - hence, on running it twice, the probability that the algorithm returns an incorrect answer *both* times is at most $(\frac{1}{2})^2$. Thus, after $k$ iterations, the probability of an incorrect answer reduces to at most $(\frac{1}{2})^k$. Thus, if we adopt the scheme that the algorithm returns **false** if the any of the first $k$ runs give an output of *false*, else return **true**, then the probability that our scheme returns an incorrect answer is at most $1 - (\frac{1}{2})^k$, which can be driven down to $0$ for large values of $k$.
> 4 votes

---
Tags: algorithms, probability-theory, randomized-algorithms, monte-carlo
---


# Question
Title: What's the meaning of "Front" in "Pareto-Optimal Front"?
I'm reading a paper about **Multi-Objective Optimization Problem**. I understand **Optimal in Pareto sense**, and I even know what is **Pareto-Optimal Front** somehow. But I can't find a relationship between the word **Front** and the concept. So, what's the meaning of this word in this context?

# Answer
> 2 votes
I think it is sort of short for "frontier" (as in boundary between one thing and another.) The two canonical examples would be a weather front (the boundary between a cold airmass and a warm airmass) and a military front (the boundary between the areas controlled by a pair of belligerent armies).

---
Tags: optimization
---


# Question
Title: Concatenation property of regular languages
If L is the empty set and therefore a regular language, I know that L concatenated with sigma star is equal L; Are there any other languages that, when concatenated with sigma star will result in the same language?

# Answer
> 4 votes
$L \Sigma^\* = \emptyset \Sigma^\* = \emptyset = L$

$\Sigma^\*L = \Sigma^\* \emptyset = \emptyset = L$

$L \Sigma^\* = (S \Sigma^\*)\Sigma^\* = S \Sigma^\* = L$ for all languages $S$

$\Sigma^\* L = \Sigma^\* (\Sigma^\* S) = \Sigma^\* S = L$ for all languages S

$L \Sigma^\* = (\Sigma^\* S \Sigma^\*) \Sigma^\* = \Sigma^\* S \Sigma^\* = L$ for all languages $S$

$\Sigma^\* L = \Sigma^\* (\Sigma^\* S \Sigma^\*) = \Sigma^\* S \Sigma^\* = L$ for all languages S.

In short: there are infinitely many distinct languages where appending the language to $\Sigma^\*$ (front or back) will yield the same language. An infinite family of such languages is given by $\Sigma^\* S \Sigma^\*$ where $S$ can be any language whatsoever.

---
Tags: regular-languages
---


# Question
Title: Can we compute the sum of a range of entries in $O(1)$ time?
I have encountered a few tests in algorithms which ask for a data structure which allows to get the sum of all the elements of an array in the range \[i..j\], in O(1) time.

Is it even possible to do so?

# Answer
Yes, calculation of range sum is possible in O(1) time. Suppose the data is given in an array. You need to preprocess the array to find the prefix sums. For this you need another array. To find range sum S(i,j\] you need to compute P\[j\]-P\[i\]. Where P\[j\] and P\[i\] are entries of prefix sum array. For example, the given array is: 4 5 -2 5 -77 45. Corresponding prefix sum array is: 4 9 7 12 -65 -20. So, S(2, 4\] = -65 - 7 = -72 (Sum from 2 to 4, 2 excluded and zero based indexing)

Note: We preprocess the given data to build the prefix sum array which takes O(n) time where n is the number of entries. After that, each query of the form S(i,j\] takes O(1) time.
> 5 votes

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


# Question
Title: Understanding Expected Running Time of Randomized Algorithms
I want to understand the expected running time and the worse-case expected running time.

I got confused when I saw this figure (source),

where $I$ is the input and $S$ is the sequence of random numbers.

What I don't understand from the above equation is why the expected running time is given for one particular input $I$?

I always thought that for a problem $\pi$, $E(\pi) = \sum\_{input \in Inputs}(Pr(input)\*T(input))$ , isn't this correct?

So, let's assume Pr(x) is the uniform distribution, and we are to find the expected running time of the problem of searching an element in a $n$ element array using linear search.

Isn't the expected running time for linear search,

$$E(LinearSearch) = \frac{1}{n}\sum\_1^ni $$

And what about the worst case expected running time, isn't it the time complexity of having the worst behavior? Like the figure below,

I would highly appreciate if someone can help me understand the two figures above.

Thank you in advance.

# Answer
> 8 votes
There are two notions of expected running time here. Given a randomized algorithm, its running time depends on the random coin tosses. The *expected running time* is the expectation of the running time with respect to the coin tosses. This quantity depends on the input. For example, quicksort with a random pivot has expected running time $\Theta(n\log n)$. This quantity depends on the length of the input $n$.

Given either a randomized or a deterministic algorithm, one can also talk about its expected running time *on a random input* from some fixed distribution. For example, deterministic quicksort (with a fixed pivot) has expected running time $\Theta(n\log n)$ on a randomly distributed input of length $n$. This is known as average-case analysis. Your example of linear search fits this category.

A related concept is *smoothed analysis*, in which we are interested in the expected running time of an algorithm in the *neighborhood* of a particular input. For example, while the simplex algorithm has exponential running time on some inputs, in the "vicinity" of *each* input it runs in polynomial time *in expectation*.

---
Tags: algorithms, time-complexity, probability-theory, randomized-algorithms, average-case
---


# Question
Title: Build a regular grammar for a regular language
The language considered is the infinite set of all chains that meet the following conditions.

Conditions:

```
1) They consist of symbols from the set {1,a,b}.
2) They always start with the subchain '1a'.
3) They always include at least one subchain 'aa'.

```

For example:

```
1aa, 1abaa, 1aaab, 1aab1a, ... etc.

```

One regular expression for this language seems to be like this: $1a ((1+b)^\* a)^\* (a (1+b)^\* )^\* a (1+b+a)^\*$

**How to find a regular grammar for this language?**

I've thought of many ways but it seems to be too complex for me. I tried the following as solution, but it is not correct, I guess.

```
G ({1,a,b}, {A,S}, P, S)
P:
S -> 1S|bS|aA
A -> 1A|bA|1a

```

# Answer
This language was already considered by the same OP in another question Build a regular expression to define a regular language. But then, posters are told not to ask two questions in the same post.

I already answered that a simple method is to consider the regular languages defined by conditions 1 and 2, $1a(1+a+b)^\*$, and by conditions 1 and 3, $(1+a+b)^\*aa(1+a+b)^\*$.

You take the FA for them, both having 3 states (4 if you count a dead state), and construct the FA for the intersection. Which is quite easy, and gives a five-states automaton (6 states if you count a dead state).

From that FA you can get a regular expression for the language, which is $1(a+a(1+a+b)^\*a)a(1+a+b)^\*$.

But you can also get a regular grammar:

$S \rightarrow 1T$
$T \rightarrow aX \mid aY$
$X \rightarrow 1X \mid aX \mid bX \mid aY$
$Y \rightarrow a \mid aZ$
$Z \rightarrow 1 \mid a \mid b \mid 1Z \mid aZ \mid bZ$

which derives directly from the automaton.

**In more details: Why do it as I did above?**

Proving that a regular expression defines the language specified by a set of such conditions can be long and tedious. The same is true for a grammar or an automaton. This is why the proper way of answering such a question is to find a systematic way of building the desired result from elementary components for which things are obvious to prove.

Here, as I had already answered, elementary components are the regular languages defined respectively

* by conditions 1 and 2: $1a(1+a+b)^∗$ ;
* by conditions 1 and 3: $(1+a+b)^∗aa(1+a+b)^∗$ .

For each of these 2 languages, it is easy to find the regular expression (above) or to give a regular grammar or a finite-state automaton (FA). Each has a 3 states FA that recognizes it (4 states including a dead state).

To get a FA for the language meeting all three conditions, you only have to get the intersection of these two languages. There is a standard cross-product construction for building a FA recognizing the intersection of two regular languages. This construction is easy to apply by hand in our example. It produce a 5 states FA for the language defined by all three conditions (or a 6 states FA, including a dead state).

From this last FA, it is easy to build either the regular expression or the regular grammar given above.

Since the answer was built in a systematic way using well known techniques (that have been proved correct long ago), there is no need to prove that the resulting regular expression, grammar or FA are correct. Barring of course mistakes in the use of the constructions ... but then, you can also make mistakes in proofs.

I added the precision about dead states so that no one gets confused. But, except for some constructions, it is often simpler just to omit dead states and transitions leading to them.
> 2 votes

# Answer
The expression always starts with `1a`. There are two options, the third character in the string is `a` or not. If it is `a`, then you don't have the obligation of following 'it contains at least one `a`'. Otherwise, you need to. Thus the regular expression is:

```
    1aa(1+a+b)*+1a(1+a+b)*aa(1+a+b)* .

```

The conversion from regular expression to automata to regular grammar is standard. One possible algorithm is given here: https://math.stackexchange.com/questions/574571/build-regular-grammar-from-regular-expression

Here is an intuitive way to convert a regular expression to a right linear grammar:

1. Convert the regular expression to an NFA. This is standard (see page 102 of Automata Theory, language and computation, 3rd ed).
2. To convert the NFA to a right linear grammar, take the states to be non-terminal and the alphabets to be terminal. For a transition of the form `S -> S'` via `a`, add the production rule `S -> aS'`. Please note that you need to take care of the final states and epsilon transitions separately.

You can also convert the NFA to a DFA (again, standard subset construction method, see the aforementioned book) and then the method will be simpler.
> 4 votes

# Answer
I suggest you approach this problem completely differently. The easiest way to get a regular grammar is to start from a DFA, not a regular expression. Can we make a DFA? Easily:

```
q    s    q'
---  ---  ---
q0   1    q1
q0   a    q2 // dead
q0   b    q2 // dead
q1   1    q2 // dead
q1   a    q3
q1   b    q2 // dead
q2   1    q2 // dead
q2   a    q2 // dead
q2   b    q2 // dead
q3   1    q4
q3   a    q5 // accepting
q3   b    q4
q4   1    q4
q4   a    q6
q4   b    q4
q5   1    q5 // accepting
q5   a    q5 // accepting
q5   b    q5 // accepting
q6   1    q4
q6   a    q5 // accepting
q6   b    q4

```

Basically, in pseudocode:

```
read the next symbol
if a '1', then
    read the next symbol
    if an 'a', then
        read the next symbol
        if an 'a', then
            read all remaining symbols
            accept
        otherwise, then
            while there are still symbols, do
               read the next symbol
               if an 'a', then
                   read the next symbol
                   if an 'a', then
                       read all remaining symbols
                       accept
                   endif
               endif
            loop
        endif
    endif
endif
reject

```

Once you have a DFA, getting the regular grammar is easy:

1. One non-terminal symbol for each state in the DFA.
2. One production of the form `q := sq'` (where `q`, `s` and `q'` are as in the table above)
3. One production of the form `qA := <empty>` for every accepting state `qA`.

If your definition of regular grammars doesn't allow productions leading to the empty string, replace rule 3 with:

* One production of the form `q := s` whenever you have, from the second rule, a production of the form `q := sq'` where `q'` is an accepting state.

The one-to-one nature of regular grammars and DFAs has another implication:

> Finding a regular grammar from a NFA (resp. regular expression) must be at least as hard as finding a DFA from a NFA (resp. regular expression).

So you lose nothing by going for the DFA first.
> 2 votes

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


title: Name for this algorithm?

text:
# Question
Title: Name for this algorithm?
I'm trying to figure out if there is a proper or commonly accepted name for this particular function (`f`).

```
float clamp(float min, float max, float v)
{
    if (v < min) return min;
    else if (v > max) return max;
    else return v;
}

float f(float min, float max, float v)
{
    float t = (v - min) / (max - min);

    return clamp(0.0, 1.0, t);
}

```

# Answer
This is sometimes called "0-1 normalization" or "feature scaling".

http://en.wikipedia.org/wiki/Feature\_scaling

http://en.wikipedia.org/wiki/Normalization\_(statistics)

The entire function f() is a Piecewise function, which consists of 3 domains, defined separately for

1. v \<= min
2. v is between min and max, and
3. v \>= max.

The primary function is the normalization function when v is between min and max. The other two functions just limit the range or codomain of the function.

Piecewise functions are used often in mathematics to make the whole function continuous over a larger domain or to handle special cases like divide by zero, which the original poster might want to handle when min == max.

And what does the function do?
Creates a function f(x) where f(min) returns 0.0, f(max) returns 1.0, and f(v) rescales the input v from 0.0 to 1.0 linearly. Anything less than min maps to 0.0; anything more than max maps to 1.0.

One application of this is to calculate the percentile of a data samples (but from 0.0 to 1.0 vice 0 to 100).
> 8 votes

---
Tags: algorithms, terminology, statistics
---


# Question
Title: red black tree and 2-3-4 tree isomorphism
Are all cases of addition and removal in 2-3-4 trees isomorphic to cases of addition and removal in red black trees?

# Answer
It depends what you mean by isomorphic. Indeed a black node with its (zero, one or two) children corresponds to a 2-3-4 node (with 1,2,3 keys and 2,3,4 children). The basic operations on the two types of trees are really different but translate quite well.

There is a single difference in symmetry: there is only one type of 3-node (2 keys, 3 children), whereas in a red-black tree the red child to the black node may be at the left or right side.
> 1 votes

---
Tags: algorithms, search-trees
---


title: Python Prime Numbers Code Problem

text:
# Question
Title: Python Prime Numbers Code Problem
I was trying to write my own code for primes in Python. I know that code already exists, but I am doing this to challenge my knowledge and make my own solution. I was wondering if any of you guys would tell me what's wrong with it.

```
factor_list = [ ]

def integer_test(x):

    if type(x) == int:
        return True
    else:
        return False

def factor_checker(x):

    count = 0
    y = x
    while count <= y:
        print(count)
        count += 1
        if integer_test(x / count) == True:
            factor_list.append(count)

factor_checker(45)

print(factor_list)

```

When I try to input a number for factor checker and then look at the factor list, I just get an empty list. What is wrong?

Thanks.

# Answer
You don't get an empty list. See this. However you won't get the desired results because in python `int` divided by `int` is always `int`. You may want to try this:

```
import math

factor_list = [ ]

def integer_test(x):

    if math.floor(x) == math.ceil(x):
        return True
    else:
        return False

def factor_checker(x):

    count = 0
    y = x
    while count <= y:
        print(count)
        count += 1
        if integer_test(1.0 * x / count) == True:
            factor_list.append(count)

factor_checker(45)

print(factor_list)

```

In this code `x/count` is a double. So the `integer_test` will only return true if it's ceiling and floor return the same number i.e the integer itself.
> 1 votes

---
Tags: primes
---


# Question
Title: Bounds for Akra-Bazzi versus Master theorem
I had my final exam today in an advanced algorithms course. In it there were two recurrence relations and I used the Akra-Bazzi theorem to solve them. After the examination I was discussing the problem with one of my colleagues and they apparently got a different bound using Master theorem. My question is which of this two bounds are tighter?

The recurrences were:

$1)\quad T(n) = 8T\left(\frac{(2n-1)}{4}\right)+n^3+n\log n$

$2)\quad T(n) = 3T(n/2)+n\log^2 n $

Now, correct me if I'm wrong but Akra-Bazzi gives 1) as $\Theta(n^3\log n )$ and 2) as $\Theta(n\log^2 n )$ Can somebody please verify 2) by Akra-Bazzi? I checked and regularilty condition doesn't hold for 2) .

# Answer
Both methods give $\Theta$ type estimates. That is, the master theorem gives some estimate $T = \Theta(f)$, and the Akra–Bazzi theorem gives some estimate $T = \Theta(g)$. From the definition of $\Theta$ it immediately follows that $f = \Theta(g)$ and $g = \Theta(f)$, that is, the estimates are equivalent. I suspect either one of you was mistaken, or both bounds that you got, while seemingly different, are in fact equivalent.
> 1 votes

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Algorithm for cost function maximization
I have a system that takes in 'm' inputs and provides a cost value as an output. The system is a "black box" to me. The inputs can be varied and the corresponding output can be observed, however, I have no prior knowledge of the function that this box implements. Given that I can fiddle with the input values(all real valued), is there an algorithm or a learning based solution that can maximize the cost function in minimum number of iterations? I think this might be a well known problem, however, this genre is way beyond my ken and I am finding it difficult to frame the terms I should be googling for. A link or mention of the name of the algorithm or a short description of the solution would be appreciated.

# Answer
> 3 votes
If don't know anything about the function, then your problam is practically unsolvable: The function in the box could be 0 evereywhere, except for a single set of inputs, where it is 1. No strategy can guarantee that you find this set of inputs in finite time.

The situation might look better, if you can assume some sort of smoothness and/or monotony conditions.

---
Tags: algorithms, machine-learning, optimization
---


# Question
Title: Build a context-free grammar for a context-free language
A context-free language is defined by its description:

$L=(a^{2k} \space b^n \space c^{2n} \mid k \geq 0, \space n \> 0)$

For example:

$bcc, aabcc, aabbcccc, bbcccc$

**How to build a context-free grammar for this context-free language?**

I suppose that the order for generating any chain in this problem matters: 'b' will always stand after 'a' and 'c' - after 'b'. Is it so?

My attempts leaded to this solution:

$ S \rightarrow aaAbcc \mid bAcc \mid aabAcc $

$ A \rightarrow aa \mid bcc \mid λ $

Please correct me if I'm wrong or better offer your solution to this problem.

# Answer
$ S \rightarrow EG $ , $ E \rightarrow aO \mid λ $ , $ O \rightarrow aE $ , $ F \rightarrow bFcc \mid λ $, $ G \rightarrow bFcc $ . I am assuming $λ$ stands for empty string.

Better one:

$ S \rightarrow EF $ , $ E \rightarrow aO \mid λ $ , $ O \rightarrow aE $ , $ F \rightarrow bFcc \mid bcc $.
> 2 votes

---
Tags: context-free
---


title: Finding dynamic programming algorithm

text:
# Question
Title: Finding dynamic programming algorithm
I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and $(i+1)$st rows cannot come from the same column.

The problem asks to make an algorithm such that the summation of all the numbers I've chosen is the minimum possible, has time complexity $O(n)$ and space complexity of $O(1)$.

I know how to do this with dynamic programming, in a more classical way: I calculate the sub-problems, store the results in a matrix of size $3\times n$ until the matrix is complete, then the result is the minimum value of the last row.

The problem is that will have space complexity of size $O(n)$, what I'm not seeing?

# Answer
Run along the columns of the matrix keeping three numbers. For each row determine the minimum score assuming the last number chosen came from that row.
> 4 votes

---
Tags: dynamic-programming, space-complexity
---


title: Sum of all nodes from A to B in a Tree

text:
# Question
Title: Sum of all nodes from A to B in a Tree
Given a Tree and pointers to two of it's nodes A and B (a key value of each node is positive).

Find an algorithm that sums up all the values on the path between A and B, when preproccessing is allowed.

# Answer
> 11 votes
## Preproccessing: $O(n)$

For each node in the tree, we will keep the sum of all the values on the path from the root to the node.

Additionally, we will prepare for LCA (lowest common ancestor) queries in $O(n)$ time.

## Query: $O(1)$

When asking for the sum on the path $A \rightarrow B$, Return $$\text{sumFromRoot}(A) + \text{sumFromRoot}(B) - 2 \cdot \text{sumFromRoot}(\text{LCA(A,B)})$$

We subtract twice the path from the LCA to the root, as we counted it twice in the sums from the root.

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


title: big O of a complex function

text:
# Question
Title: big O of a complex function
I have a complex function, which looks something like this:

$$f(x) = \sum\_{k=0}^x{\frac{g(k)}{h(k)}} + l(x)$$

Now, $g(k) = O(\log k)$ and $h(k) = O(k)$, the sum iterates $k$ from $0$ to the parameter $x$ and $l(x)$ is meant to provide a decimal correction, but its form is $\dfrac{a^{b-x}}{h(k)} (a,b - const)$.

How can I assess the big O of $f(x)$?

I did some calculations and came up with $O(x^2 \log x)$, but I'm not confident it is right.

# Answer
I'm assuming you meant $l(x) = a^{b-x}/h(x)$, where $a \geq 1$. This term is $o(1)$ so can be ignored. For the main term, we cannot conclude anything since we only have an upper bound on $h$; we would like a lower bound on $h$. It could be, for example, that $g(k) = \log k$ and $h(k) = e^{-k}$, a function certainly satisfying $h(k) = O(k)$, and in that case $f(x) = \Omega(e^x)$.

Assuming you meant $h(k) = \Theta(k)$, or at least $h(k) = \Omega(k)$, we can estimate the sum using an integral: $$ \sum\_{k=0}^x \frac{g(k)}{h(k)} = O\left(\sum\_{k=0}^x \frac{\log k}{k}\right) = O\left(\int\_0^x \frac{\log k}{k} dk\right) = O(\log^2 x),$$ using $\int \frac{\log k}{k} = \frac{1}{2} \log^2 k$. If $g(k) = \Theta(\log k)$ and $h(k) = \Theta(k)$ then $f(x) = \Theta(\log^2 x)$.
> 3 votes

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


# Question
Title: Is it possible to repeat a wildcard in regex?
`.{5}` would match any string of 5 symbols (excluding newline). Suppose I wanted to define "a 5-character repetition of a single character."

The immediate way that comes to mind is `(.)\1{4}`, but this relies on a back reference.

Using a subset of regex which is dependent only on `|,(),*,concat` any regex expression of pattern size `M` and search string size `N` can be solved with a means an `M`-size NFA in `O(NM)` time.

Backreferences, unlike `+, {n}, etc.` are not derivable from the restricted regex tools above, and result in exponential times.

Is it possible to replicate the desired pattern in the non-exponential-time subset of regex (without using exponential\* size)? **If not, then why (how can we prove so)?**

\*one could go factorial in size by brute-forcing in this case.

# Answer
Using backreferences you can accept non-regular languages such as the language of squares $ww$, which is accepted by `(.*)\1`. This language cannot be represented as a non-extended regular expression at all.
> 1 votes

---
Tags: regular-expressions
---


title: Turing Decidable

text:
# Question
Title: Turing Decidable
```
M = (Q, Σ, Γ, δ, q1, qaccept, qreject), where
Q ={q1, q2, qaccept, qreject},
Σ = {0, 1},
Γ = {0, 1, U},

```

and transition function δ is as follows:

```
δ (q1, U) = (q1, U, R)
δ (q1, 0) = (q2, U, R)
δ (q1, 1) = (q2, U, R)
δ (q2, U) = (qaccept, U, R) δ (q2, 0) = (q1, U, R)
δ (q2, 1) = (q1, U, R)

```

is L Turing - decidable? From what I know, a language L is turing decidable if there is a turing machine M such that M decides L (M is a decider and L=L(M)).

What would be the language that M recognises? I am very new to Turing languages so not quite sure how to read the transition function. I know that a language is decidable if it halts (rejects or accepts) for every input string, but thats about it.

# Answer
> 1 votes
You're in luck here: since every transition of your TM moves the head right, the state of this machine will never depend on the previous contents of the tape. This means that your TM will act as if it were a finite automaton, basing its transitions only on the current input symbol. In other words, your TM is essentially equivalent to this FA:

It's easy enough to define the language accepted by this FA. It consists of all strings of the form:

* (an arbitrary number of U's) followed by (any even-length string of 0's and 1's),
* repeated an arbitrary number of times,
* ending with 0u or 1u.

As a regular expression, this language is denoted by $$ (U + 00 + 01 + 10 + 11)^\*(0 + 1)U $$ Where $r + s$ represents the union of the sets denoted by the regular expressions $r$ and $s$. This, then, is the language, $L(M)$, of your original machine. Since the language is regular, it is certainly decidable, since a finite automaton will always eventually halt.

The question of whether your TM is a decider will depend on your local definition of what that means. Customarily, a TM is defined to be a decider if it eventually halts on every possible input. This machine will certainly do that, even though it will never enter $q\_{\text{reject}}$, so under this definition your TM is indeed a decider. Be aware, though, that some authors require that a decider must eventually enter $q\_{\text{accept}}$ or $q\_{\text{reject}}$ and halt for *any* possible input, so under that definition, your TM wouldn't be a decider. Look at your notes to see which definition applies (from what you wrote, it seems to be the latter).

---

Another reasonable interpretation of this problem is that 'U' is intended to represent the blank character. Under this interpretation, the TM is definitely not a decider, since when given the empty string as input, namely when faced with a tape initially containing nothing but blanks, the TM will loop in state $q\_1$ forever, thereby never halting. No matter which definition of a decider you choose, it's universally agreed that a decider must halt on all inputs, hence under this interpretation, the TM isn't a decider.

---
Tags: turing-machines, automata, finite-automata, undecidability
---


# Question
Title: How to pack polygons inside another polygon?
I have ordered a few leather sheets from which I would like to build juggling balls by sewing edges together. I'm using the Platonic solids for the shape of the balls.

I can scan the leather sheets and generate a polygon that approximates the shape of the leather sheet (as you know, it's animal skin, and it doesn't come in rectangles).

So now, I would like to maximize the size of my juggling ball.

In my example, the polygons are regular ones, but I'm looking for a solution with simple polygons.

What is the largest scale factor that I can apply to my polygons so that they all fit inside the sheet ?

I am trying to minimize the waste by using as much as material as possible.

Obviously, cutting the polyhedron net into individual polygon will increase the space of possible combination, but also decrease the quality of the final geometry, because there is more sewing involved and accumulated errors. But this question is not about enumerating the different ways of unfolding a polyhedron. They can be considered independently. So the polygons are simple polygons.

*Formally:*

Input:

* $P$ : a simple polygon (the target)
* $S$ : the set of polygons I want to place
* $G$ : a graph of $n$ simple polygons - each node represents a simple polygon in $S$, and there is one edge edge between each pair of polygons that share a common edge
* $\alpha \>= 0, \beta \>= 0$ (usage of material and connectivity)

Output:

* a scale factor $f$
* $H$, a subgraph of $G$
* $Loc$: a location and an angle for each polygon in $V(G)$
* a measure of the quality $m$ of the solution: $ m = \alpha.f + \beta. {|E(H)|\over|E(G)|} $

Maximize $m$ subject to these conditions:

* $ | V(H) | = |V(G)| $ (1)
* $ | E(H) | \<= |E(G)| $ (2)
* for every polygon $S\_i$ in $S$, $S\_i$ scaled by a factor $f$ at location $Loc(S\_i)$ is inside $P$ (3)
* polygons in $V(H)$ don't overlap (4)

( V(G) are the vertices in the graph, and S is the set of polygons, but they describe the same set of objects. Maybe there is a more compact way to do this.)

Explanation of the conditions:

* (1) I want all the polygons to be in the final layout
* (2) Some connections may be broken if necessary
* (3) (4) the ball is made of leather

Here is the target polygon

Here is the set of polygons I want to pack:

# Answer
> 3 votes
This belongs to an optimization class of problems called Packing problems. In your case, instead of a regular polygon as container, you've got an irregular one, but the idea remains the same.
These optimization problems are usually NP-hard, so I don't think there is an easy way to get the exact solution and trying all the combinations would be too too expensive.
There are some people interested in this kind of problems; I've found this link of some solved specific packing problems: https://erich-friedman.github.io/packing/

The easiest way I see, is to define an approximate center of the leather sheet, to move the set of polygons to there and, by scaling up and down and checking if the set of polygons is or not inside the target polygon, to get a closer and closer scale factor 'f' for your desired set of polygons.

But, unless you are going to use this factor for a large scale juggling balls production, probably doing it by hand would be fairly enough.

---
Tags: optimization, computational-geometry, packing
---


# Question
Title: Research in Graph Theory versus Graph Algorithms
I have a very generic question to ask. It is related to research. I'm interested in Graph theory. I have done a course in it. I have done some topics related to both graph theory as a point of view of doing it as a mathematics student and also studied some graph algorithms. I'm going for research internship in graph theory. But there is some glitch in my mind that I'm unable to fix about my real interest in graphs because of lack of proper distinctive ideas about *the real difference in doing research in graph algorithm or doing graph theory as a mathematics student*. I would like to know the following things:

1. What is the real difference in doing graph theory as a mathematics student or doing graph algorithms? Do both of them have some real difference?
2. Can someone tell me some good source for getting research papers on graph theory and graph algorithms.
3. Is it good to start doing graphs as a mathematics student?

I don't know if it is a right place to put forward such kind of problems. Please let me know if it doesn't fit here.

# Answer
**Question 1**

I would say that the two areas are definitely not identical, however there is a huge overlap. Partly it depends on where you draw some very fuzzy lines. Let's start with:

* *Graph Theory* is about the properties of graphs as mathematical objects
* *Graph Algorithms* as an area of research is about solving ***computational*** problems that are represented using graphs.

Of course graph theory is unsurprisingly very useful in developing graph algorithms, and graph algorithms can answer questions in graph theory. Indeed, as you have obviously noticed, many problems in Graph Theory can be cast as computational problems, and answered by giving an algorithm (in a sense this is an aspect of the Curry-Howard Correspondence), so especially at the introductory level, there is little more than the style of presentation that separates them.

Just to make things even more confusing, most researchers in one field have at least some interest and experience in the other, but there are a couple of points where we can draw certain lines of distinction:

* Graph theory (as a field) will happily deal with infinite graphs, which are not so interesting from an algorithmic perspective.
* Graph theorists will tend to be more interested in existential statements ("the chromatic number of a class of graphs is at most blah"), whereas graph algorithms people will be looking for the best algorithm to solve a problem ("how do we compute the actual value of the chromatic number as quickly as possible?").
* Graph algorithms includes/overlaps with the application and tailoring of graph algorithms to solve problems that aren't really about graphs (e.g. developing a good algorithm to cluster protein interaction networks), which a graph theorist would be uninterested in (at least *as* a graph theorist).

**Question 2**

If you have access to university subscriptions or similar (this is no way exhaustive):

To muddy things further, many of these include examples of both pure graph theory and graph algorithms.

A couple of lists for further exploration:

There is the arXiv preprint server, which has preprint versions of research papers, but again, you'll have to spend a small amount of time to explore and find something you want (it's more set up for finding a paper you already know is there).

**Question 3**

This question cannot really be answered objectively. It depends entirely on things that you have no way of knowing (i.e. the future), and I have no way of knowing (how good the people are at your university, what opportunities you will gain or lose by taking that internship).

If you want my subjective *general* opinion, I would say yes. Graph theory is an important part of mathematics and computer science (I personally contend they're not different things anyway), and versatility and breadth of knowledge are important characteristics of a good researcher, even if you later decide you have no intention of being a graph theorist - it's not going to stop you from being able to do complex analysis or topology.

Again, this is about whether an arbitrary student would benefit from doing work in graphs (algorithms or theory) - you personally may be in a particular situation where it would not be beneficial, and we can't answer that here. For example, if taking the internship means that you don't get to do the internship in Category Theory that is actually the thing you want to do, then this could set you back. Early in a research career it is difficult to escape a particular path, without going back to step one. Later on, it's easier to transition, but for better or worse there's period effectively like apprenticeship where you can't easily jump to any job you're interested in, but that's a question for Academia.SE.
> 10 votes

---
Tags: graphs
---


# Question
Title: Sequence of N operations Amortized Analysis
A sequence of $N$ operations is performed on a certain data structure.

The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1.

How can I calculate the amortized cost for every operation using the potential function method?

# Answer
> 3 votes
How about this. Assume we maintain a binary counter $C$ that counts the operations executed so far. Let $D\_i$ be the data structure after the $i$-th operation. We then define as potential $\Phi(D\_i)$ number of $\tt 1$-digits in $C$. As usual $c\_i$ denotes the actual costs, and $\hat c\_i$ the amortized costs.

If $i$ is not a power of two, then we have $$ \hat c\_i = c\_i + \Phi(D\_i) - \Phi(D\_{i-1}) \le 2 .$$ This is true since the addition of a $\tt 1$ on $C$ will turn one digit from $\tt 0$ to $\tt 1$ while possibly turning some digits from $\tt 1$ to $0$.

If $i$ is a power of two then clearly $$ \hat c\_i = c\_i + \Phi(D\_i) - \Phi(D\_{i-1})= i + 1 - (i-1) =2 .$$

As a final comment, the amortized costs do always depend on the potential function. So another potential function yields different amortized costs.

# Answer
> 1 votes
I don't know about the potential function method, but to calculate the amortized cost, you compute the total cost of $n$ operations and divide by $n$. In this case, if we denote by $x\_i$ the cost of the $i$th operation then $$ \sum\_{i=1}^n x\_i = n + \sum\_{2^j \leq n} (2^j-1) \leq 3n, $$ and we can conclude that the amortized time $O(1)$. I'll let you carry out the calculation and detail, and figure out how to apply the potential function method.

---
Tags: algorithms, data-structures, amortized-analysis
---