# Question
Title: Early termination of A* with weak heuristic if solution is known
I have a large graph G and a pair of nodes s,t. I want to use the A\* algorithm to find the shortest path from s to t, and I have a heuristic that is consistent.

Suppose I already know of a path whose length is guaranteed to be at most 1.1 times as long as the shortest path. Does this help A\* find the shortest path faster? If so, how and why? Can knowledge of this path be used to improve the running time of A\*, reduce the number of nodes, or make the heuristic more accurate?

One improvement I can see is to remove the all the nodes in the open list which exceed the current solution. But if the heuristic is weak, this wouldn't help in reducing the number of nodes to be explored in the open list. So, in what other ways one can use the knowledge of known path in hand to help A\* terminate itself earlier than without the knowledge of known complete path.

# Answer
> 1 votes
In order to prove that the solution is optimal, with a consistent heuristic A\* needs to expand all states with f \< f\* (the perfect solution cost) and it also may expand some states with f = f\* so it seems hard that knowing an upper bound on the number of expansions can help to reduce the number of node expansions without modifying the heuristic.

A potential way of helping A\* in this context may be that of heuristic selection. That is, in cases where more than one heuristic is available, meta-reason about what subset of heuristics should be used \[1,2\].

In this scenario it could be possible to use the sub-optimal path to select which ones to use (e.g., it may be worth it to compute more expensive heuristics because they have greater chances of pruning the node). However, this is an open problem and I'm not aware of any work on that direction.

\[1\] David Tolpin, Tal Beja, Solomon Eyal Shimony, Ariel Felner, Erez Karpas: Toward Rational Deployment of Multiple Heuristics in A. IJCAI 2013: 674-680

\[2\] Levi H. S. Lelis, Santiago Franco, Marvin Abisrror, Mike Barley, Sandra Zilles, Robert C. Holte: Heuristic Subset Selection in Classical Planning. IJCAI 2016: 3185-3191

---
Tags: algorithms, graphs, optimization, shortest-path, heuristics
---


title: What is an unrestricted production?

text:
# Question
Title: What is an unrestricted production?
I was reading an article at

What does "context" in "context-free grammar" refer to?

The production

```
zA -> xy

```

is described as being an "unrestricted" production. In what way is it "unrestricted"?

I even visited https://en.wikipedia.org/wiki/Unrestricted\_grammar

which talks about unrestricted grammar as the one that is comprised of productions which have no restriction on LHS or RHS. On this note, I assume that an unrestricted production is the one with no restriction on LHS or RHS.

What restrictions are being talked about and how is the production free from such restrictions?

# Answer
> 2 votes
A single rule can not be "unrestricted".

The *whole* set of rules is $(T \cup N)^+ \to (T \cup N)^\*$. So the *class* of unrestricted grammars may use any rule from this set.

*Restricted* classes of grammars are only allowed to use a strict subset of all rles, e.g.

* right-regular grammars are restricted to $N \to T^\*N^{\\{0,1\\}}$, and
* context-free grammars to $N \to (T \cup N)^\*$.

By going through the Chomsky hierarchy, you will note that the rule

$\qquad zA \to xy$

is not admitted in any but the type-0 grammars; try to see why it's not a "context-sensitive rule". That does not mean it is *only ever* allowed in the unrestricted class -- just that it's not in any *on this list*. There are many more classes.

---
Tags: formal-grammars
---


# Question
Title: What is the relation between EXPTIME and NP HARD complexity classes?
Need to know the relation between **EXPTIME** and **NP HARD** complexity classes.

# Answer
There are NP-hard problems that are not in EXPTIME and vice versa. This is to be expected as NP-hard is defined by a lower bound and EXPTIME mainly by an upper bound. NP is contained in EXPTIME, however, and NP-complete is of course contained in NP.
> 9 votes

# Answer
The two classes are incomparable: neither is a subset of the other.

* There are problems in **EXPTIME** that are not **NP**-hard. The languages $\emptyset$ and $\Sigma^\*$ are both in **EXPTIME** but are definitely not **NP**-hard since no other language can be many-one reduced to either of them. If we assume that **P$\\,\neq\\,$NP**, then we get plenty more problems (all of **P**) that are in **EXPTIME** but not **NP**-hard.
* There are **NP**-hard problems that are not in **EXPTIME**. For example, consider the class **2EXPTIME**$\\,=\bigcup\_{c\geq 0}\mathrm{TIME}\left\[2^{2^{n^c}}\right\]$. Because **NP$\\,\subset\\,$2EXPTIME** any **2EXPTIME**-complete problem is **NP**-hard. However, by the time hierarchy theorem, we know that **EXPTIME$\\,\neq\\,$2EXPTIME**, which means that no problem in **EXPTIME** is **2EXPTIME**-complete. (In fact, for a more extreme example, the halting problem is **NP**-hard and that's definitely not in **EXPTIME**!)
> 8 votes

# Answer
**NP hard** is a subset of **EXPTIME**, but we have no idea if that subset is strict. Answered by: @jmite
> -4 votes

---
Tags: complexity-theory, time-complexity, complexity-classes
---


# Question
Title: Counting the number of minimal covers of a binary matrix
Given a binary $n$-times-$n$ matrix $A$, we'd like to cover the regions comprised of $1$'s with non-intersecting rectangles. A collection of disjoint rectangles that covers all $1$'s (and only $1$'s, i.e., it mustn't cover any $0$'s) is called a *cover*. (Notice that a problem instance may have *many* different covers.)

A cover is called a *minimum cover* if it uses the smallest number of rectnagles possible.

The counting problem I'm interested in is: given an $n$-times-$n$ binary matrix $A$, count the number of minimum covers of $A$.

What can you say about this problem? (This post was inspired by this SO question.)

# Answer
> 2 votes
It's easy to show that some inputs can produce an exponential number of minimum covers. Consider the following 3x3 matrix:

```
110
100
000

```

This can be minimally covered in exactly 2 ways: either using a single vertical 2x1 rectangle and a single 1x1 rectangle, or a single horizontal 1x2 rectangle and a single 1x1 rectangle.

Thus placing $k$ non-overlapping copies of this gadget in a grid will produce an instance with $2^k$ distinct minimal covers. You could, for example, tile an $n$ by $n$ grid with $n^2/9$ of them to produce an instance with $2^{n^2/9}$ minimal covers.

(It's possible that a better gadget exists -- that is, smaller gadgets that would increase the coefficient in the exponent. More interestingly it's possible that instances with *asymptotically more* minimal covers exist.)

# Answer
> 2 votes
This problem comes up as a technique for proving lower bounds in communication complexity. See for example these lecture notes.

There are some bounds on the number of rectangles. For example the number of rectangles is at least the rank of the matrix. Google yields more with the search terms "monochromatic rectangle tiling".

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


# Question
Title: Reduce the following decision problem to CNF-SAT
**Input**:

* $X$ = {$x\_1$,$x\_2$,$x\_3$,...,$x\_n$}
* $Y$ = {$y\_1$,$y\_2$,$y\_3$,...,$y\_m$}
* $k$, where, $k$ $\leq$ $m$

**Output** (Yes/No): Satisfying the following condition, can all the elements in set $X$ be assigned to elements in set $Y$, such that, no elements in $X$ is left unassigned?

**Condition**: At least $k$ elements in $Y$ is needed to access all the elements in $X$. All the elements assigned to $y\_i \in Y$ are said to be accessible using $y\_i$.

Reduce this decision problem to CNF-SAT.

**Thoughts**:

I have considered $n \times m$ no. of variables. Each variables for a pair of element of set $X$ and set $Y$. i.e., $a\_{ij}$ : for all $x\_i$ and $y\_j$.

For ensuring that no elements in $X$ is left unassigned the CNF expression will be. $(a\_{11} \vee a\_{12} \vee ... \vee a\_{1m}) \wedge (a\_{21} \vee a\_{22} \vee ... \vee a\_{2m})... (a\_{n1} \vee a\_{n2} \vee ... \vee a\_{nm})$

I am not able to form the CNF expression for ensuring that at least $k$ elements from $Y$ are required to access all the elements in $X$. It seems that there will be an exponential number of clauses in the expression.

Thanks for helping.

# Answer
> 4 votes
Yes, you certainly can reduce it to SAT: the problem you state is obviously in NP, and thanks to Cook's theorem, everything in NP can be reduced to SAT.

I suspect that wasn't what you actually meant to ask. Actually, your problem is in P: Hall's theorem says that such an assignment exists if and only if the corresponding bipartite graph has a perfect matching. You can test whether a bipartite graph has a perfect matching in polynomial time using standard algorithms.

---
Tags: complexity-theory, reductions, satisfiability, decision-problem
---


# Question
Title: How static Bayesian networks are stored? Like Hugin etc
I wanted to know the standard format to store the Bayesian network structure? I came across Hugin format and others. But couldn't find out the documentation as how its been written, if I wanted to write a piece of package that writes the BN in a file which can be read by other popular Bayesian inferencing tools for Bayesian networks.

# Answer
> 1 votes
For anyone who shares this same query. I have found a link that answers it. Further, found a implementation as well.

---
Tags: machine-learning, graphical-models
---


# Question
Title: How to formulate a computational problem rigorously?
I often interact with people who want to ask for an algorithm for a computational problem (or its complexity), but they don't express it in a rigorous way for us (computer scientists) to understand.

Referring them to books like CLRS is not helpful because the examples there usually have a quite straightforward way of stating rigorously, e.g. given the adjacency list of a graph and two vertices in it compute the shortest path between those vertices.

> Is there any good book (or some other resource) where a person with minimal knowledge of CS can learn how one should formulate and state computational problems in a rigorous way that is understandable to computer scientists?

Preferably the book should have many examples of how to formulate computational problems rigorously from various domain and real world examples.

---

### Clarification

To make the question more specific, let's assume that they know basic math/CS terminology like sets, functions, graphs, lists, etc. at the level of 1st/2nd year undergraduate CS student (which is the case with people who I have in mind). For example, they have read some introductory textbook like Aho and Ullman (although they might not have understood it completely).

# Answer
> 3 votes
a good resource on/for this, fairly well known by academics but not so widely known outside of specialists, is *Mathematical Writing* by Donald E. Knuth, Tracy L. Larrabee, and Paul M. Roberts. there is a published book, lecture videos, and a set of notes. it is more written from the perspective of people attempting to master mathematical writing eg for creating papers, but all the advice is highly applicable to the case of laymen attempting to formulate problems precisely. mathematical writing while formidable to learn is the scientific approach to rigorously define/formulate—and as the book details, *solve*, eg via algorithms or proofs—computational/algorithmic problems.

also, the classic Garey & Johnson text, Computers & Intractability does not exactly describe how to formulate problems precisely, but it does give many examples, and diverse theoretical/conceptual/technical "patterns", organized into sections of similar problems, which can be used as "building blocks" to describe computational/algorithmic problems.

# Answer
> 3 votes
just ran across this nice/neat, unusual, relatively new/unknown ref on his home page by Emmanuele Viola, prof (T)CS at Northeastern University) apparently unpublished elsewhere. 41pp. it starts out with very basic mathematical concepts eg implication and then ranges all the way into advanced topics like the Erdős–Szekeres theorem and Ramsey theory.

# Answer
> 0 votes
Buy the book Algorithms and Data Structures from Robert Lafore.

On this book, every algorithm is explained as a story, very much like a poetry. Then, give the person the Lafore version of an algorithm, and later the CLRS version.

Maybe like this, the person will get a feeling on how to translate from intuitive description to rigorous ones.

---
Tags: algorithms, reference-request, books
---


# Question
Title: Binary Equivalent vs. Computer code(Ascii or UTF)
Does computer convert every stuff using Ascii or UTF?
Meaning if there is a mathematical calculation including 65 (as a number) will it convert it into binary (00100001)?
And then how it differentiate it with 'A', whose code point is also 65 with code 00100001?

# Answer
> 1 votes
I am not an expert in the field, but I can try to give an approximately correct answer.

Reading from memory itself, you can not diferentiate between lets say ints and characters. The compiled program is compiled with locations of where to find the operator that is needed, in this case print for ints and for chars. You must specify how to represent that data in your print command.

Example in c:

```
printf("ASCII value = %d, Character = %c\n", ch , ch );

```

This code will first represent data at location ch as a number and than as a char.

Let me give another example: Let us say that your language can "add" strings, in form of concatenating one onto another. How can computer know which "add" to use, if you cannot learn of data type from memory? The compiler compiled the program with address to the appropriate "add" command, according to data type you specified your operands to be.

Moral of the story: you cannot learn of data type from memory. Hopefully this clears it out.

---
Tags: arithmetic
---


# Question
Title: Optimizing hash table for common subset of keys?
Are there variants of hash tables that take advantage of the likely distribution of key values? For example, if I'm using utf-8 encoded unicode strings as identifiers in a compiler but expect the majority of them to fit into ASCII, can I optimize for that use case?

# Answer
> 2 votes
Yes, it's sometimes possible to optimize hash tables based on expected key values (i.e. make certain classes of keys at the expense of other classes). But I don't see how there could be one in your case.

There are two ways to potentially make hash tables faster: use a hash function with fewer collisions, and use a hash functions that's faster to calculate. But they pull in opposite directions: you can either make the hash function faster or better, not both.

Hash functions are designed to spread out likely key values in the first place. So if you have “typical” input, there's nothing to be gained here.

For example, if you're making exact string comparisons, then the fact that the strings are encoded in UTF-8 doesn't affect the way the hashes are calculated. The hash function looks at all the bytes of the string anyway, and has a low probability of collisions except for specially-crafted data. A hash function specialized to pure-ASCII strings won't be faster to calculate (operations are on bytes anyway, even on words, not on individual bits) nor have more collisions (repeated bit patterns like “all upper bits are 0” is something typical hash functions are designed to cope with).

An example where you can gain performance for typical cases is when the key for the hash table is a large data structure, such that there's a gain to be made by hashing only part of the data structure. Say the key consists of both a name and some large extra data, and most keys have different names, but occasionally there are distinct keys with the same name. Then you might use a two-level table: first hash on the key, and then, only in buckets where there is more than one entry, calculate the hash of the extra data.

In the case of a string, the closest thing would be to hash only a prefix. But that typically gives bad results in practice; for example, in a compiler, it's very common to have large sets of identifiers with a common prefix.

Another case where a simpler, partial hash function can be useful is when equality between keys is hard to test. This may be the case with Unicode strings if you need to treat different representations of the same text as equal, e.g. treat combining characters as equivalent to non-canonical forms. In this case, you may want to avoid doing the work of normalizing each string. However that wouldn't help for the pure-ASCII case, since normalizing a pure-ASCII string is easy. It might help with typical “tame” uses of Unicode (sticking to characters that are common in one language).

A hash table is not necessarily the best structure to represent a mapping from keys to values. Search trees or tries have many advantages. Balanced search trees have guaranteed $O(\lg(n))$ behavior, whereas hash tables are harder to protect against deliberately-crafted key sets (not so much an issue in compilers, but it can be an issue when interpreting code from an untrusted source, e.g. a web browser running Javascript code from some random website). Hash tables are pretty much impossible to share intelligently — you have to copy the whole table. With trees, on the other hand, sharing comes naturally. Sharing is very often useful in compilers, between scopes that differ only on a few identifiers.

# Answer
> -1 votes
*Shortly, yes, - you can use this information for improvements. But you should define a current implementation and an optimization goal for a precise answer.*

For example, you could optimize average search by key time. Let's assume that the "ASCII" set means that the last bit inside the utf-8 (8 bit) set is zero. Let's assume that you'd been used a naive hash Map and hash function as implementation. Always 8 buckets (static), the unsophisticated hash function is the last 3 bits. All ASCII symbols appear uniformly, and the utf-8's remainder chars are "very sparse."

**Optimization:** change the last 3 bits to the first three bits. You just get rid from "almost"(depending on the "very sparse") 1/3 adding hash collisions. Look at any article about hash Map's performance to figure out what performance boost you got via elimination of 1/3 hash collisions on average. Operations complexity for Java's HashMaps.

**Avg. situation changed like.** (hash function time + 1 or 2 operations with list for accessing)

000 - "NUL"(00000000)" -\> "7" (11100000)

*(a bucket with "000" hash label and two collided elements)*

010 - "ESC(00111010)"

**becomes** (hash calculation + 1 operation)

000 - "NUL"

111 - "7"

001 - "ESC"

If there was no "very sparse" utf-8 remainder (and non-uniform access patterns) both hash functions act in the mentioned aspect equally. This is how, in principle, we can use size, keys, values, access patterns distribution and other use-cases info for optimizations.

---
Tags: data-structures, strings, hash-tables
---


title: Collection of APX-hard problems

text:
# Question
Title: Collection of APX-hard problems
Everyone knows "Garey & Johnson", which is my go-to reference whenever I need a problem to transform from for an NP-hardness proof. However I recently find myself in need of an APX-hardness proof, and I wonder if there is a similar (and more up to date..?) collection of problems that have been shown to be APX-hard.

Does anybody know of anything like this? I find it hard to believe that there is no website systematically collecting such problems, but my Google skills seem to be insufficient.

# Answer
> 5 votes
I've used this compendium a few times... Is this what you were aiming for?

---
Tags: complexity-theory, reference-request, time-complexity, complexity-classes
---


title: DFA's with more than one initial state

text:
# Question
Title: DFA's with more than one initial state
( This may be related to NFAs with more than one initial state )

Consider a dfa $M$ with alphabet $\Sigma$ and states $Q$, typically also characterized by a specific initial state $q\_0\in Q$. As the above-cited question points out, nfa's that nondeterministically select among several possible initial states can be converted to equivalent (wrt to their accepted language) nfa's with a unique initial state. And I'm asking if the same is true of dfa's, as follows.

Instead of $M$'s input being only a tape/string $s\in\Sigma^\ast$, let its input be $(q\_0,s)\in Q\times\Sigma^\ast$, i.e., you give it the initial state $q\_0\in Q$ that you want it to start in, as well as a string.

I'd think each possible $q\_0\in Q$ defines a different language, call it $L\_{q\_0}\subseteq\Sigma^\ast$, accepted by $M$. But $Q$ can possibly be partitioned into equivalence classes, where all the states in a class accept the same $L$. But if there's more than one such class, then no single dfa with a unique $q\_0$ starting state could represent this $M$.

So, assuming that's more-or-less correct, my additional question is how to characterize the equivalence classes. That is, given $M$'s transition function, $\delta:\Sigma\times Q\to Q$, how would you determine whether $q\equiv q^\prime$ belong to the same class (besides, that is, individually working out the language each accepts)? Is there a more elegant way to do that?

# Answer
> 3 votes
As Lukas points out, having multiple initial states is something of a red herring. You've defined your automaton to accept a subset of the strings that match the regular expression $Q\Sigma^\*$ and that regular expression matches the language accepted by some ordinary DFA using the usual techniques. (Lukas gives an explicit construction in terms of the original automaton.)

For equivalence, there is a standard polynomial-time technique used for state minimization for DFAs. Luca Trevisan has a good set of notes (PDF) on this, which I'll briefly summarize. Let the automaton have state set $Q$, alphabet $\Sigma$ and transition function $\delta$.

For a state $q$ and string $w$, write $\delta^\*(q,w)$ for the state that you reach by starting at $q$ and reading $w$. For states $p$ and $q$, write $p\equiv q$ to mean that $\delta^\*(p,w)$ and $\delta^\*(q,w)$ are either both accepting or both rejecting. This gives the same relation $\equiv$ that you give in the question. We'll show how to compute $\equiv$.

To do this, for any $n\geq 0$, define $p\equiv\_n q$ in the same way as $p\equiv q$, except restricting $w$ to be of length at most $n$. We'll compute the relations $\equiv\_n$ inductively, and show that knowing a finite number of them is the same as knowing $\equiv$.

First, note that $p\equiv\_0 q$ if, and only if, $p$ and $q$ are both accepting or both rejecting so we can compute $\equiv\_0$ easily. Now, suppose we've already computed $\equiv\_n$. We claim that $p\equiv\_{n+1}q$ if, and only if, $p\equiv\_n q$ and $\delta(p,u)\equiv\_n\delta(q,u)$ for all $u\in\Sigma$. Obviously, if $p$ and $q$ "agree" on all strings of length at most $n+1$, they must also agree on all strings of length at most $n$. For the second part, consider a string $uw$ where $|u|=1$ and $|w|=n$. We're saying that, for $p$ and $q$ to agree on $uw$, it must be that, after reading $u$, they move to states that agree on $w$.

This allows us to construct the relations $\equiv\_n$ for all $n$. Finally, we claim that $\equiv\_{|Q|}$ is actually the same relation as $\equiv$. To see this, observe that every $\equiv\_n$ is an equivalence relation and, furthermore, the procedure from moving from $\equiv\_n$ to $\equiv\_{n+1}$ can only split equivalence classes into smaller ones: it can never merge them. Also, if $\equiv\_n$ and $\equiv\_{n+1}$ are the same relation, then $\equiv\_{n+i}$ is the same relation for all $i\geq 0$. $\equiv\_0$ has at most two equivalence classes. Every step of the process either splits at least one equivalence class or is the end of the game: it doesn't split any class and nor does any future step. We can't split classes more than $|Q|$ times because, if we did, we'd have more equivalence classes than states, which is impossible. So it must be that $\equiv\_{|Q|}$ is the same thing as $\equiv$ and we're done.

# Answer
> 2 votes
If you input the desired initial state (plus the actual input word), then you are not really using multiple initial states, right? Your proposed solution can easily be transformed into a DFA with a singular initial state: Add a state $\tilde{q\_0}$, add transitions $\delta(\tilde{q\_0}, q) = q$ (ok, I'm abusing notation here - your alphabet needs an element to represent each of your states in this case, but you could also encode them as words of whatever elements your alphabet has) to $\delta$ and make $\tilde{q\_0}$ your initial state. Now the first input element selects the "actual initial state".

As for equivalence classes on the states: I'm not sure how they they help you there. Only trivial DFAs will have only one equivalence class on all of their states. Or are you talking about the "multiple initial states" belonging to different equivalence classes? In that case: It is easy to construct a DFA that accepts e.g. "a\*" if it starts in $q\_1$ and "b\*" if it starts in $q\_2$ - thus, $q\_1$ and $q\_2$ clearly belong to different equivalence classes. However, it is equally easy to construct a DFA that accepts "(a\*|b\*)" with a single initial state.

---
Tags: finite-automata
---


# Question
Title: How does the token method of amortized analysis work in this example?
Below is the description of the answer to a question which says the following:

**Design a data structure to support two operations for a dynamic multiset S of integers which allows duplicate values.**

1. Insert operation for one element
2. Delete-larger-half(S) deletes the largest ceil(|S|/2) elements from S.
3. m insert and delete-larger-half operations run in O(m) time.
4. Also output the elements in O(|S|) time.

In answer unsorted array has been taken. I think delete-larger-half corresponds to deleting the |S|/2 elements with highest magnitude. Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median). I suppose the amortized analysis is what is bringing out the complexity. I'm looking for an answer that can explain the token based amortized analysis by using the example in this question.

**What I know already:** Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more. On average it evens out giving a better amortized complexity. Example: implementing dynamic array which is probably what has been done in the solution linked below.

Link to solution: https://courses.csail.mit.edu/6.046/fall01/handouts/ps7sol.pdf

> You use an unsorted array, so insert takes O(1) worst-case time. For DELETE-LARGER-HALF, you use the linear-time median algorithm to find the median, then you use PARTITION to partition the array around the median, then you delete the larger side of the partition in O(1) time. For the amortized analysis, insert each item with 2 tokens on it. When you perform a DELETE-LARGER-HALF operation, each item in the list pays 1 token for the operation. When you delete the larger half, the tokens on these items are redistributed on the remaining items. If each item on the list starts with 2 tokens, they each have one after the median finding, and then each item in the deleted half gives its token to one of the remaining items. Thus, there are always two tokens per item and we get constant amortized time.

I've not been able to understand the logic behind random assigning of token and taking it off.

In the answer, the `insert` has been assigned 2 tokens, the find median and partition take away 1 token total. And then deletion gives the 1 token. I understand that each time, delete-larger-half is called, the next delete-larger-half's cost reduces drastically but why exactly the values 2, 1, 1 have been chosen?

# Answer
> 1 votes
> Then how does deleting with median work unless there is n comparisons (i.e compare each element with the median).

After partitioning (they assume Quicksort-style partitioning), you can just delete the last $\lceil |S| / 2 \rceil$ elements in the array.

> Amortized analysis means doing some expensive work in previous steps which leads to worst case of a following step not happening as often. Every time the expensive step occurs, the probability of it happening again reduces more and more.

That is a useful intuition, but I feel a little bit besides the point.

Mainly, amortized analysis is about investigating the *compound cost* of *sequences of operations*. By dividing the sum by the number of operations we get what we call *amortized cost* for each operation.

I don't see a specification of such sequences in your problem statement so it may be ill-posed, unless the analysis goes through for *all* sequences.

So let us check. What is the *worst* that could happen? Well, probably a sequence of *only* DELETE-LARGER-HALF operations; consider $n$ elements and a sequence of $m = \lfloor \log\_2 n \rfloor$ DELETE-LARGER-HALF operations (after this many, the set is almost empty). Since each operation has linear cost in the number of elements, the total cost then is $\Theta\bigl( \sum\_{i=1}^{\log\_2 m} 2^i \bigr) = \Theta(m)$ -- fits!

If we wanted to make this sequence more expensive by making individual summands larger, we would need to add INSERT operations. Say we wanted to increase one summand $2^i$ to $2^{i+1}$. We would have to add $2^i$ elements at cost $O(1)$ each, so the compound cost would increase by $2^{i+1}$ -- but $m$ would increase by $2^{i}$! Therefore, the *amortized* cost would only increase by a constant.

The core observation is this: if an element is to partake in making a DELETE-LARGER-HALF operation expensive (by being there), it has to be INSERTed first. Since DELETE-LARGER-HALF has linear cost, we can not add more than constant cost per element. In combination, this means we will get constant amortized time.

The tokens are a way to formalize this into a proof (which the part you quote does not quite manage to do). The way the tokens are set up and passed around, we see that the cost of any sequence of operations is in $\Theta$ of the total number of tokens we see. We can not possibly see more than $2m$ different tokens so we get an $O(m)$ bound on the compound cost or an $O(1)$ bound on the amortized cost.

---
Tags: algorithm-analysis, runtime-analysis, arrays, amortized-analysis
---


# Question
Title: Length of the solution calculation in Breadth-first
I'm trying to figure out how to calculate the route cost on this graph (it's the missionaries and cannibals game)

I have my definition as:

```
Mi = Missionary on the initial side, C = Cannibal on the initial side, B = Boat [I = Boat in the Initial Side, F = Boat on the Final Side],
Mf = Missionary on the other side of the river, Cf = Cannibal on the other side of the river
State: (Mi, Ci, B, Mf ,Cf)
Initial Status: (3, 3, I, 0,0)
Final Status: (0, 0, F, 3,3)
Status Space (All the valid statuses):
{(3,3,I,0,0),(3,2,F,0,1),(2,2,F,1,1),(3,1,F,0,2),(3,2,I,0,1),(3,0,F,0,3),(3,1,I,0,2),(1,1,F,2,2),(2,2,I,1,1),(0,2,F,3,1),(0,3,I,3,0),(0,1,F,3,2),(0,2,I,3,1),(2,2,I,1,1),(3,2,I,0,1),(0,0,F,3,3)}

```

Rules:

```
1.  Bote can only carry two people
2.  One person has to drive the boat
3.  Cannibals can't outnumber the missionaries or they the missionaries will be eaten.
Cost: 1 per crossing.

```

Exhaustive Search (or Brute Search):

```
(3, 3, I, 0, 0) -> (2, 2, F, 1, 1) -> (3,2,I,0,1), -> (3,2,I,0,1) -> (3,2,1,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,F,1,1) -> (0,2,F,3,1) -> (0,3,I,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (0,0,F,3,3)

```

According to me and the graph the route cost for Exhaustive Search would be 11.

How can I calculate the route cost for that graph for Breadth-first?

I do know that Breadth-first I have to separate the graphs on levels and it will test each node on that level against the final result (depending on the direction, clockwise, or counterclockwise) but **I'm not sure if I should take each node as a crossing** (I'm getting 14 as length of the solution). For instance in the image I take the crossing from (3,3,I,0,0) to (3,2,F,0,1) as 1 and then there isn't more child-nodes on that branch so I should get back to (3,3,I,0,0) in order to reach the branch of (2,2,F,1,1) **this I don't know If I should count it too or not**

To get 14 I'm doing. `(3, 3, I, 0, 0) -> (3,2,F,0,1) -> (2,2,F,1,1) -> (3,1,F,0,2) -> (3,2,I,0,1) -> (3,0,F,0,3) -> (3,1,I,0,2) -> (1,1,F,2,2) -> (2,2,I,1,1) -> (0,2,F,3,1) -> (0,3,1,3,0) -> (0,1,F,3,2) -> (0,2,I,3,1) -> (2,2,I,1,1) -> (0,0,F,3,3)`

Because of this doubts I have troubles calculating the Length of the solution

# Answer
I do not know how your sources define "route cost" (I've never heard that term).

There are two points of view I can imagine.

1. **Length of the solution**

Once you reach a fitting leaf you have found your solution and can abort. The length of the solution, i.e. the number of steps you have to perform to get everybody across, is *the length of the path from the root to that leaf*.
2. **Cost of the algorithm**

The number of steps the algorithm has to perform is different, of course; it may visit many nodes that are not part of the final solution. The details depend on the specific implementation at hand.

Specifically, you seem to be concerned about *backtracking* out of dead ends. The usual way to implement BFS is using a *queue* which makes backtracking *free* since you don't actually do it; the next node to visit is already at the front of the queue.

If you don't use a queue and backtrack explicitly, well, you get quadratic worst-case performance. Don't do it.
> 3 votes

# Answer
If you want to calculate the distance between two nodes using BFS, you could use the algorithm as described in the Wikipedia.

Maybe it's easier to understand how this works if you think of BFS as working in waves:

```
wave <- starting node
set all distances to infinity
d = 0
while wave is not empty:
     set the distance of all nodes in wave to d
     next_wave = all neighbors of nodes in wave with infinite distance
     d = d + 1
     wave = next_wave

```

The wave-front travels over the graph very much like the wave in a pond after you throw a stone in it. In this formulation you don't explicitly traverse edges forwards or backwards, so it's harder to get confused when to increase distances.
> 1 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis, search-algorithms, graph-traversal
---


# Question
Title: Greedy algorithm for a variation of the $k$-center problem
This is a variation of the well-known $k$-center problem with priorities given on the vertices.

> **Problem:**
>
> Let $G = (V,E)$ be a complete graph with a distances on the edges satisfying the triangle inequality. Then, additionally, there is a priority function $p: V\to (0,\infty)$. Given some $k\in\mathbb{N}$ then we wish to solve the following optimization problem $$\min\_{\substack{C \subseteq V \\ |C|\leq k}} \text{cost}(C)$$ where the cost is given by $$\text{cost}(C) = \max\_{v\in V}p(v)\cdot d(v,C) $$ and $d(v,C)$ is the distance from $v$ to its closest center $c\in C$.

Assume that we know the optimal radius $r^\*$. Then we propose the following greedy algoritm:

1. Initialize $S = V$ and $C = \emptyset$.
2. Now repeat steps $3$-$5$ as long as $S \neq \emptyset$:
3. Select the vertex $c\in S$ with the highest priority $p(c)$.
4. Add $c$ to $C$, i.e. $C := C \cup \\{c\\}$.
5. Remove all vertices $v$ from $S$ that satisfies $p(v)\cdot d(v,c) \leq 2r^\*$
6. Return $C$.

I wish to prove that this is a $2$-approximation algorithm. I'm having trouble specifically to get the $2$-factor. I've looked at some proofs of the usual $k$-center problem algorithms for inspiration, but the priority part is throwing me off.

Can anyone give a proof of the $2$-factor, or perhaps some hints?

# Answer
As a hint, let me work out the case $k = 1$ for you. We are given that some set $C$ of size 1 satisfies $p(v) d(v,C) \leq r^\*$ for all $v \in V$. Let $C = \\{x\\}$. Then $p(v) d(v,x) \leq r^\*$ for all $v \in V$.

The given algorithm picks the point $c$ which maximizes $p(c)$, and then removes from $S$ all points in $A = \\{ v \in V : p(v) d(v,c) \leq 2r^\* \\}$. We will show that $A = V$, and so the algorithm terminates after one step, outputting the set $C = \\{c\\}$. By construction, $p(v)d(v,c) \leq 2r^\*$ for all $v \in V$, so this is a 2-approximation.

It remains to show that $A = V$, that is, that all vertices $v \in V$ satisfy $p(v) d(v,c) \leq 2r^\*$. Indeed, since $p(v) d(v,x), p(c) d(c,x) \leq r^\*$, the triangle inequality implies that $$ p(v) d(v,c) \leq p(v) d(v,x) + p(v) d(c,x) \leq p(v) d(v,x) + p(c) d(c,x) \leq 2r^\*, $$ using the obvious $p(v) \leq p(c)$.

All that remains is to generalize this proof for larger $k$.
> 2 votes

---
Tags: approximation, greedy-algorithms
---


# Question
Title: How to construct XOR gate using only 4 NAND gate?
`xor` gate, now I need to construct this gate using only 4 `nand` gate

```
a b out
0 0 0
0 1 1
1 0 1
1 1 0

```

the `xor = (a and not b) or (not a and b)`, which is \begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

I know the answer but how to get the gate diagram from the formula?

**EDIT**

I mean intuitively, to me, I should get this one if I do it step by step followed by the definition `xor = (a and not b) or (not a and b)`.

\begin{split}\overline{\overline{\overline{A}{B}}\cdot\overline{{A}\overline{B}}}\end{split}

and `xor` will be constructed with 5 `nand` gates (first #1 image below)

my question is more like: imagine the first person in history figure out this formula, how can he or she (the thinking process) get the 4 `nand` soltuion from this formula, step by step.

\begin{split}\overline{A}{B}+{A}\overline{B}\end{split}

# Answer
From that formula? It can be done. But it's easier to start with this one: (using a different notation here)

```
a ^ b = ~(a & b) & (a | b)

```

Ok, now what? Eventually we should derive `~(~(~(a & b) & a) & ~(~(a & b) & b))` (which looks like it has 5 NANDs, but just like the circuit diagram it has a sub-expression which is used twice).

So make something that looks like `~(a & b) & a` (and the same thing but with a `b` at the end) and hope that it'll stick around: (`and` distributes over `or`)

```
(~(a & b) & a) | (~(a & b) & b)

```

Pretty close now, just apply DeMorgan to turn that middle `or` into an `and`:

```
~(~(~(a & b) & a) & ~(~(a & b) & b))

```

And that's it.
> 19 votes

# Answer
I think you are asking for this proof:

```
A^B = (!A)B + A(!B)
    = !!((!A)B) + !!(A(!B))
    = !(!!A + !B) + !(!A + !!B)
    = !(A + !B) + !(!A + B)
    = !((A + !B)(!A + B))
    = !(A(!A) + AB + (!A)(!B) + B(!B))
    = !(AB + (!A)(!B))
    = !(AB)(!(!A)(!B))
    = !(AB)(!!A + !!B)
    = !(AB)(A+B)
    = !(AB)A + !(AB)B
    = !!(!(AB)A + !(AB)B)
    = !((!(!(AB)A))(!(!(AB)B)))

```

Although apparently there are 5 `NAND`s used in the resultant equation, but the duplicate `!(AB)` will be used only once when you are designing its circuit.
> 10 votes

# Answer
Since you already have the diagram answer, easily awailable from wikipedia by typing you question title in Google, as a .png diagram identical to yours, it should be easy for you to find the formula by extracting it from that diagram. Given the definition NAND as $\text{NAND}(A,B)=\overline{AB}\\;$:

* The leftmost gate gives $C=\overline{AB}$;
* The top gate gives $D\_1=\overline{AC}$;
* The top gate gives $D\_2=\overline{BC}$, as the NAND is commutatve like the AND;
* The rightmost gate gives $E=\overline{D\_1D\_2}$.

Putting it all together we first note that

$C=\overline{AB}=\overline A+\overline B$

$\begin{align} \overline{D\_1}&=AC\\ &=A(\overline A+\overline B)\\ &=A\overline A+A\overline B\\ &=0+A\overline B\\ &=A\overline B\\ \end{align}$

Similarly: $\overline{D\_2}=B\overline A$

Thus
$\begin{align} E&=\overline{D\_1D\_2}\\ &=\overline{D\_1}+\overline{D\_2}\\ &=A\overline B + B\overline A \end{align}$

Which is precisely the definition of XOR. You may just reverse all this if you want to start from your initial data, rather than just check the answer.

## Finding the answer with no prior knowledge

This is intended to answer the explicit request, added as an edit to the question, for a way of finding the solution from scratch. Given that the question is about a thought process, I am giving all details.

I would try to rely on the constraints of the problem (only 4 NAND gates) and on its symmetry between $A$ and $B$ which may be preserved in the solution.

One thing I know (assuming information flows from left to right as in the question diagrams) is that there must be a rightmost NAND gate that produces the desired answer $\text{XOR}(A,B)=A\overline B + B\overline A\\;$.

So we can try to guess what kind of input to this gate would produce the desired output.

We know that $\text{NAND}(X,Y)=\overline{XY}= \overline X+\overline Y\\;$

Unifying this last formula with the result we have to get, we obtain:

* $\overline X=A\overline B\\;$, thus $X=\overline{A\overline B}=\overline A+B\\;$.
* and symetrically $Y=\overline{\overline A B}=A+\overline B\\;$.

Note that this is only the simplest possibility. There are other pairs of inputs that would give the desired result, because we are not unifying in a free algebra, since NAND has equational properties. But we try that for a start.

The problem is now whether we can obtain both $X$ and $Y$ from $A$ and $B$ with 3 NAND gates.

We could try to repeat the unification procedure (I did), but this will naturally lead us to using four more gates, hence to a 5 gates solution.

Assuming we are on the right track, we need two NAND gates to produce $X$ and $Y$. So that leaves us with only one gate to produce a formula $Z$ that combined with $A$ or $B$ will provide the input for these two intermediate gates.

Given that we have to provide symetrically for $X$ and $Y$, we can expect that $Z$ should be symmetric in $A$ and $B$. Hence this leftmost NAND gate should take both $A$ and $B$ as input.

This first NAND gate, with $A$ and $B$ as input, produces as output:

$Z=\text{NAND}(A,B)=\overline{AB}= \overline A+\overline B\\;$

Now, we have to check whether combining $Z$ with itself, $A$, $B$, 0, or 1 through a NAND gate can produce $X$, and also $Y$.

We know that combining a value with itself, 0 or 1 through a NAND gate is either the identity function or the negation. So the only remaining candidates are $A$ and $B$.

It is easy to check that

$\begin{align} \text{NAND}(Z,A)&=\overline{ZA}\\ &=\overline{\overline{AB}\\;A}\\ &=\overline{(\overline A+\overline B)\\;A}\\ &=\overline{\overline AA+\overline BA}\\ &=\overline{0+\overline BA}\\ &=\overline{\overline BA}\\ &=\overline{A\overline B}\\ &=X \end{align}$

Similarly $\text{NAND}(Z,B)=Y$

Hence we can compose these four gates to get the desired result, i.e., the XOR function.
> 6 votes

# Answer
I take the input $(0,0)$ as an example.

For $\text{XOR}$, the desired output is 0. However, $\text{NAND}(0,0) = 1$.

* Because the only way to get a 0 using $\text{NAND}$ is (at the last layer) $\text{NAND}(1,1) = 0$, you should first produce two 1's.

+ According to $\text{NAND}(0,1) = 1$ or $\text{NAND}(1,0) = 1$, you produce a 1 using one $\text{NAND}(0,0)$ at the first layer and feed it, along with one input 0, into a second layer $\text{NAND}$.

Only four $\text{NAND}$s are involved. But it is only correct for the input $(0,0)$ so far. So you need to check other inputs $(0,1), (1,0),$ and $(1,1)$ against the solution and find that it just works. Lucky.
> 0 votes

# Answer
I tried my best to give the answer using formula as asked.Hope you appreciate it.
Z=AB'+A'B
Z=AA'+AB'+BB'+A'B ---\>BB'=AA'=0
Z=A(A'+B')+B(B'+A')
Z=A(AB)'+B(AB)' --\> Hint
so now (AB)' can get through 1st NAND gate,then in 2nd and third NAND gate the output of 1st NAND gate pass through with one of the input as A and B.After this we need one more complement so use fourth NAND gate.
NAND(1st)=(AB)'=A'+B'
NAND(2nd)=(A(AB)')'=(A(A'+B'))'=(AB')'=A'+B
NAND(3rd)=(B(AB)')'=(B(A'+B'))'=(A'B)'=A+B'
NAND(4th)=\[(A'+B)(A+B')\]' =\[A'B'+AB\]'=(A+B)(A'+B')=AB'+A'B

Happy!
> 0 votes

# Answer
The formula: XOR = (a and not b) or (not a and b).

Thats' not what you want, you want a formula that is a NAND. Remember that not (a or b) = not a and not b, and therefore (a or b) = not (not a and not b). Therefore

(a and not b) or (not a and b) =

not (not (a and not b) and not (not a and b)) =

not ((not a or b) and (a or not b)) =

NAND (not a or b, a or not b).

So we used one NAND gate, and have to calculate (not a or b) and (a or not b) using three NANDs. We turn each expression into a NAND:

not a or b = not (a and not b) = NAND (a, not b)

a or not b = not (not a and b) = NAND (not a, b)

Now we observe that (x and y) = x and (not x or y): If x is false then both sides are false. If x is true then (not x or y) = (false or y) = y. This is true for NAND just as it's true for AND. Therefore

NAND (a, not b) = NAND (a, not a or not b) = NAND (a, NAND (a, b))

NAND (b, not a) = NAND (b, not b or not a) = NAND (b, NAND (a, b)).

So we first find mid = NAND (a, b), left = NAND (a, mid) and right = NAND (b, mid), finally XOR = NAND (left, right).
> 0 votes

# Answer
\*From left to right--D1,D2,D3,D4 \** D1=(A.B)' OR(A'+B')

suppose

(A.B)'=C

D2=(A.C)'=A'+C'

D3=(B.C)'=B'+C' then

D4=(D2.D3)'

D4=((A.C)'.(B.C)')'

D4=(A.C)''+(B.C)''

D4=(A.C)+(B.C)

D4=A.(A'+B')+B.(A'+B')

D4=AB'+BA' {A.A'=B.B'=0}\**
> -2 votes

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


title: Stabilization of lower approximation

text:
# Question
Title: Stabilization of lower approximation
Let $f:\mathbb{N} \to \mathbb{R}$ be a lower semicomputable function, i.e. there exists a recursive function $g:\mathbb{N}\times \mathbb{N} \to \mathbb{Q}$ s.t.

$$\forall x \in \mathbb{N} \quad \lim\_{k \to \infty} g(k,x) = f(x) \qquad\qquad (1)$$ $$\forall x \in \mathbb{N} \quad g(k,x) \le g(k+1,x)\qquad\qquad (2)$$

Question: can we assume that if $f(x)$ is rational then eventually $g(k,x)$ stabilizes on the true value? Formally, can we prove that there exists a recursive function $g':\mathbb{N}\times\mathbb{N}\to\mathbb{Q}$, possibly different from $g$, s.t. $(1)$ and $(2)$ holds for $g'$ and additionally

$$ \forall x \in \mathbb{N} \quad \left( f(x) \in \mathbb{Q} \Rightarrow \exists k\_0 \in \mathbb{N}\\, \forall k\>k\_0 ~~g'(k,x) = f(x) \right)$$

I tried many different strategies but they all seem to a dead end.

Notice that $g'$ need not to be build from $g$ (there may be no relations among the two) and we need not to be able to *know* when $g'$ stabilizes. Think for example to the function $f$ that prints 1 if the $n$-th TM halts otherwise 0 (i.e. the characteristic function of the halting set). If you pick $g'$ as $g'(k,n)=$"$1$ if the TM $n$ halts in $k$ steps and $0$ otherwise" you clearly get that $g'$ eventually stabilizes on all $n \in \mathbb{N}$ even though we will never be able to say when.

Currently I don't even know whether this should be true or false. Maybe I'd bet on true, but it's just a feeling and that can be totally wrong of course.

# Answer
Define $h(k,x)$ as the maximal $\ell \leq k$ such that program $x$ halts on inputs $1,\ldots,\ell$ after at most $k$ steps. Clearly $h(k,x)$ is computable. Define $g(k,x) = -1/h(k,x)$. Clearly $g(k,x)$ is computable and monotone.

If $x$ computes a total function then $\lim\_{k\to\infty} g(k,x) = 0$. Otherwise, if $s$ is the first input on which $x$ doesn't halt then $\lim\_{k\to\infty} g(x,k) = -1/(s-1) \< 0$.

Suppose now that some computable function $g'(k,x)$ satisfies $\lim\_{k\to\infty} g(k,x) = \lim\_{k\to\infty} g'(k,x)$ for all $x$, and $g'(k,x)$ eventually stabilizes for all $x$. Thus $x$ is total iff $\exists k.g'(k,x) = 0$, putting TOT in $\Sigma\_1$. However, TOT is known to be $\Pi\_2$-complete, and in particular doesn't belong to $\Sigma\_1$.
> 1 votes

---
Tags: computability, approximation
---


# Question
Title: Why should we study all the three forms of representation of finite automata?
DFA, NFA and epsilon NFA all the three allow us to represent a particular regular language. With any of those representations we can arrive to the same regular expression, then why do we need to study all the three form of representation of finite automata? There can some explanation on what NFA can do which DFA cannot , that is NFA might help us in designing uncertainties. For example in designing a game (chess), we have many options to move a particular piece from a particular location which can be easily represented using NFA. But what is the use of epsilon NFA when the same can done using NFA or DFA?

# Answer
> 13 votes
Add regular grammars for a fourth. There are others...

Part of the interest in DFA + NFA is that they are simple computation models, with NFA (and $\epsilon$-NFA) examples of nondeterminism (a crucial idea for more elaborate models). To prove DFA and NFA accept the same set of languages is also exploring a very important phenomenon in a simple, understandable setting.

Regular expressions (and also regular grammars) are completely different formalisms, that happen to describe the same set of languages. Again, the proof of this fact explores important cross-relations, and are an example that formalisms might *look* very diffent, be based on radically dissimilar concepts, but describe the same languages. Again, in a rather simple setting.

For "real world" use, you can start with a regular expression and get a minimal DFA for high-performance searching. Digital circuits are essentially DFAs, understanding them is central in computer engineering. Last but not least, often systems can be modelled as "being in a state" and "moving to another one" on external stimuli, even if the system is very far from a real DFA viewing it this way might help understanding it.

**Added later:** As noted by Raphael, it may be more efficient to interpret an NFA directly for searching, because creating a DFA can be expensive, and an NFA may be much smaller.

# Answer
> 5 votes
there are a wide variety of reasons to study the different forms/ correspondences of DFAs vs NFAs. here are a few selected highlights some from advanced complexity theory.

* NFAs are a interesting model for "parallel computation". one can regard the advancement of states through the NFA as a parallel version of DFA computation. so DFA vs NFA computations reflect some of the distinction of sequential vs parallel computation. by comparing both contexts it also helps to study the inherent algorithmic complexity of problems.
* NFAs are often used in regular expression matching systems (quite ubiquitous across languages esp modern ones spawned in the unix era), which typically allow descriptions of regular expressions that are converted to NFAs, and then possibly converted to DFAs to aid with more efficient searching.
* there are quite a few open problems that remain in the areas and they are often studied based on the DFA/ NFA correspondence. see eg are there any open problems left on DFAs (cstheory stackexchange). somewhat amazingly, some of them are tied up with very deep areas of CS including the P vs NP problem ie intersection nonemptiness of DFAs. also another open area is eg computing the minimal NFA for a DFA.
* also for some related insight see this semifamous/ highvoted question on cstheory.se: What is the enlightenment I'm supposed to attain after studying finite automata?
* there are very diverse applications of DFAs vs NFAs and the correspondence between the two is often exploited in them. string pattern matching is mentioned above, but DFA/NFA constructions are used often in (automated) speech recognition. see eg this highly cited paper: Weighted Finite-State Transducers in Speech Recognition / Mohri, Pereira, Riley

# Answer
> 2 votes
DFAs has a easier implementation than NFA since their next state is determined by a function and NFAs help a user to easily express what they want as an output, because the NFA can choose between multiple paths. and epsilon-NFA is an extension of NFA where transitions can be done without taking any input symbols.

# Answer
> 1 votes
There is a nasty thing about the number of states of DFAs. It explodes, *sometimes*.

In short, if the number of states is simply too high (still finite but we live in a physical world.), then you have to increase the level of abstraction to cope with the complexity in expense of some slowdown. The other models, like NFAs and AFAs, are to provide more succinct ways to represent regular languages.

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


# Question
Title: Given a list of points on a sphere find the place for another point such that most space is covered?
Suppose I knew my current location as a geographical point (Lat/Lng) and had a standard radius to search (meters). Now given a list of previously searched geographical points as the centers of circles with the same standard radius that are nearby my point but do not encompass my point what would be a good algorithm for determining where to place the center of the new geographical point such that the circle around it covers the most area not covered by other circles while also containing my current geographical point?

I've already done some thinking and I thought perhaps something to do with the average of all the points would perhaps work, but it becomes tricky because the points are on a sphere instead of on a plane.

Of course because this is the real world we must take all distances as "sphere" distances instead of straight-line distances. An algorithm which uses straight line distance but can be substituted for sphere distance is also acceptable.

I'm sure there is a name for this problem, I just could not find a name so I figured I would ask here.

# Answer
> 2 votes
The general problem is called Circle packing, which gets easier with equiradius circles, to get hexagonal grid and put circles on hexagon vertices and one in the center. This works on Euclidian space, so the hexagon coordinates should be converted by some kind of mapping, for example Vincenty formulae.

This method will give really neglible overlapping, but to be exact further corrections might be needed (like error calculation at intersection points to shift the centers). For small radius (like 50m) error will be very small (using the mapping to sphere). Performing grow on already available circles will give the problem of initial rotation to fit more space, so with many initial circles not fitting the grid only general method (iterative one) will give the optimum.

The deterministic optimization shows the method to treat circle packing as quadratic optimization.

---
Tags: algorithms, space-partitioning
---


# Question
Title: Running time of naive recursive implementation of unbounded knapsack problem
How does one go about analyzing the running time of a naive recursive solution to the unbounded knapsack problem? Lots of sources say the naive implementation is "exponential" without giving more detail.

For reference, here's a bit of Python code that implements the brute-force solution. Note that this can run for a long time even on smallish inputs. One of the interesting things about Knapsack is some inputs are lot harder than others.

```
import random, time
import sys

class Item:
    def __init__(self, weight, value):
        self.weight = weight
        self.value = value

    def __repr__(self):
        return "Item(weight={}, value={})".format(self.weight, self.value)

def knapsack(capacity):
    if capacity==0: return ([], 0)
    max_value = 0
    max_contents = []
    for item in items:
        if item.weight <= capacity:
            (contents, value) = knapsack(capacity-item.weight)
            if value + item.value > max_value:
                max_value = value + item.value
                max_contents = [item]
                max_contents.extend(contents)
    return (max_contents, max_value)

def generate_items(n, max_weight, vwratio=1):
    items = []
    weights = random.sample(range(1,max_weight+1),n)
    for weight in weights:
        variation = weight/10
        value = max(1, int(vwratio*weight + random.gauss(-variation, variation)))
        item = Item(weight, value)
        items.append(item)
    return items

n=30
max_item_weight=100
capacity=100

items = generate_items(n=n, max_weight=max_item_weight, vwratio=1.1)

st = time.time()
solution, value = knapsack(capacity)
print("completed in %f"%(time.time() - st))

```

Note that this algorithm can be improved upon nicely by memoizing yielding a *O(nW)* pseudo-polynomial time solution, but I was interested in understanding how to analyze the brute-force algorithm more precisely.

# Answer
> 1 votes
You will be trying every sequence of items that fit, adding the same item multiple times if that is possible. So first you need to check if you actually wanted the same item to be used multiple times. Whether you did or not, you can make the algorithm a lot more efficient if you only add items in ascending order, that is if you added item k, then you only add further items k, k+1, k+2, ... or only items k+1, k+2, ... depending on whether you wanted to allow the same item multiple times.

You could also save substantial time again by sorting the items for example in descending order. If you do that, you can try adding items with the smallest first, and when an item doesn't fit, you know further items won't fit either - so you can stop the search there.

Anyway, the time depends entirely on the data. If all the items are in size between capacity/2 and capacity then it's $O (n^2)$ (could be $O (n)$ with improvements described earlier). If any item has weight 0, then your algorithm never ends; you should check that first. In the worst case where all n items have size 1 and the capacity is W, your algorithm takes $n^W$ steps - that's especially bad because that particular problem is trivial.

# Answer
> 0 votes
Here's my attempt to answer my own question, which may very well be wrong. Comments and alternatives welcome.

In each step, we consider *n* options for the next item to add to the pack, where *n* is the number of different types of items. The number of such steps we end up doing depends on W, the capacity of our knapsack (maximum weight it can hold). The exact relation between W and the depth of the recursion is a little mysterious, depending on the particular values. But, if we increase the capacity by some factor, we'll on average recurse one level deeper, leading me to guess that it's bounded by *O(n^cW)* for some constant *c*.

Alternatively, I could imagine trying to extend the 2^n bound of the 0-1 knapsack problem to the unbounded case. Something like *2^(nW)* where the number of binary in/out decisions we have to make is proportional to both *n* and *W*.

---
Tags: algorithm-analysis, runtime-analysis, knapsack-problems
---


# Question
Title: How to reduce constrained proofs to 0-1 IP
Consider the following problem:

Can $X$ be proven in fewer than $Y$ steps, from axioms $Z$, with finitely many transition rules $\tau$?

This lies in $NP$, since if I supply a proof $M$, and individual steps can checked against the list of possible transitions $\tau$ in polynomial time, then $M$ can be checked for length $\<=Y$ in linaer time, and verified for correctness in $Y\*O(n^{O(1)})$

What isn't clear is how to reduce this generic "finite resource" automated theorem proving problem, to 3-SAT.

Obviously it should be reducible since $3-SAT$ is NP Complete but it's not clear how to do that.

# Answer
*If* your problem is truly in NP, the reduction follows immediately from the Cook-Levin theorem. You described how to build a verifier for your problem. The proof of the Cook-Levin theorem shows how to turn that into a 3SAT instance. Basically, the variables of the 3SAT formulas are the intermediate states of the verifier, and the formula itself says that each pair of consecutive states are consistent and that the verifier ends up accepting.

I am not persuaded by your proof that it is in NP. Your proof would be fine if $Y$ is provided on the input in unary, but not if it is provided in binary -- in the latter case, the length of the proof is exponential in the size of the input, so your proposed verifier doesn't run in polynomial time. If the problem is not in NP, there is no (polynomial-time) reduction to 3SAT.
> 1 votes

---
Tags: complexity-theory, np-complete, reductions, polynomial-time, automated-theorem-proving
---


# Question
Title: Safe way to explicitly define new types instead of using Algebraic data types for my functional language
**Question:**

As I'm working on a Hindley-Milner typed lambda calculus, in order to make it usable I need to add some types such as list and pairs. The way I currently do it is, I have an `unsafe` keyword that lets me explicitly set the type of a global function that tells the type checker to just trust the explicitly given type and ignore the term's type. Then I use Church encoding to encode my types, so for instance, I can create my `Pair` type by encoding it in a `(a -> b -> x) -> x` function like this:

```
unsafe pair : a -> b -> (Pair a b) = \a.\b.\f.(f a b)
unsafe pairRead : (a -> b -> x) -> (Pair a b) -> x = \f.\p.(p f)

```

Then I can define `fst` and `snd` like:

```
fst = (pairRead \a.\b.a)
snd = (pairRead \a.\b.b)

```

It seems that, since lambda calculus is Turing complete and I'm just wrapping lambda types with explicitly given types, I should be able to emulate any Algebraic data types, and more, in case ADTs have any limitations (seems like they do since there are also GATDs, which I guess I should also be able to emulate).

The obvious problem is that this is not type safe, which defeats the whole purpose of type checking, so I wonder if there is already a way to do this in a safe manner instead of attempting to recreate the wheel. I could also just implement ADTs but, if there's a way to make it safe, I'd like to use this better since it's closer to what I have already implemented, it's simpler (I won't need to also implement pattern matching) and it seems to be a superset of ADTs.

**What I've done so far:**

I'm pretty sure if I provide a way to encode an existing type into a custom type while keeping all the type variables, and a way to go back to the original type, then I will be safe.

For instance, I could add a keyword `using` that uses this syntax:

```
using [CustomTypeName] [FullListOfTypeVariablesInOriginalType] = [OriginalType] {
    [FunctionsDefinitions]
}

```

Inside `[FunctionsDefinitions]` I'd define my functions and I'd have access to two other new keywords `$to` and `$from`, which would have the types of functions that go from the original type to the custom type, and the other way around, respectively, but would behave as an identity function during evaluation. So for instance, I would define my pair functions like this: (note that I'm including the `x` in the `Pair` definition):

```
using Pair a b x = (a -> b -> x) -> x {
    pair = \a.\b.($to \f.(f a b))
    pairRead = \f.\p.(($from p) f)
}

```

In this case, `$to` and `$from` would be equivalent to these functions (defined using the `unsafe` keyword I mentioned above):

```
unsafe $to : ((a -> b -> x) -> x) -> Pair a b x = \x.x
unsafe $from : Pair a b x -> ((a -> b -> x) -> x) = \x.x

```

So this should be safe since `$from` will always map back to the original type because the `Pair` type includes every type variable in the original type, but is still not good.

Since I'm including `x` in the definition of `Pair`, my `Pair` type will include the return type of whatever function I pass to `pairRead`. So if at any point I read a pair `p` using `pairRead` with a function that returns a number, from that point on I could only read pair `p` using functions that return numbers, since the `x` in `Pair` would have become a number type. For instance, a function `swap = \p.(pair (snd p) (fst p))` would require both types in the pair to be the same.

So I'd like to be able to ditch the `x` in the original type to get `Pair a b`. So the question would be, when can a variable be safely ditched? I think this would be variables that are not bound to an outer type. In my definition of `pair` above, the type of `\f.(f a b)` is really $\forall x (a \rightarrow b \rightarrow x) \rightarrow x$ with $a$ and $b$ bound to the outer type, so if I want to encode this type, I only need to store the types of $a$ and $b$ to be able to recreate the original type.

I think what my type checker needs to do is basically (in the case of `Pair`), when it sees a `$to` keyword, first type check its term, then unify its type with `(a -> b -> x) -> x` (using a fresh copy of `x`) and finally make sure that no occurrence of `x` has been unified with any type that exists in the current type context. If that's all good, then return the type `Pair a b` with `a` and `b` taken from the resulting type.

But then again, I'm no mathematician and I don't have a proof of correctness, and somebody may have already came up with a better way to do this.

# Answer
You're on the right track: people have come up with the same way to do this. The general concept is known as abstract types.

With the Church encoding, the type of a pair of elements of types $a$ and $b$ is polymorphic: it has the type $\forall x, \mathtt{Pair} \\, a \\, b \\, x$ where $x$ is the type of the destructor's continuation. The type family you're making abstract is $\mathtt{Pair} \\, a \\, b$. You aren't “ditching” the $x$ — you're including it in the type.

Once you've defined a type alias called `Pair` and some functions whose type refers to this alias, you can “forget” or “hide” the fact that this is an alias. With the alias hidden, values of type `Pair` can only be constructed and destructed via the functions defined in the “module” or “package” where the alias is not hidden.

To show that this can be included in a type system without breaking anything, make the aliasing explicit: define

```
unsafe_pair : ∀a, ∀b, Pair a b → ∀x, ((a → b → x) → x) = identity
unsafe_pairRead : ∀a, ∀b, (∀x, ((a → b → x) → x)) → Pair a b = identity

```

In the place where the `Pair` alias is transparent, use those constants. You aren't using any kind of abstraction, so you're still using existing type system. In the place where the `Pair` alias is hidden, forbid the use of those constants. You've effectively created an abstract type without touching the type system.

Zero type theory lets you get started with abstract types, but type theory comes up if you want to model the concept of hiding. A module that declares an abstract type is saying “there's this type, and it has those properties (functions), but I'm not saying exactly what it is” — mathematically, this matches the concept of existential quantification, and indeed abstract types can be modeled with an existential quantifier.

```
pair_module = ∃ Pair, ((Pair a b → ∀x, ((a → b → x) → x)),
                       (∀a, ∀b, (∀x, ((a → b → x) → x)) → Pair a b))

```

It may be difficult to get an intuition of what's going on here, because the pair abstract data type essentially allows any values to be constructed. I encourage you to work out types with constraints, for example an abstract type of pairs where the first element is less than the second, so the conversion function `unsafe_increasing_pair` is identical to `unsafe_pair` but the constructor for the `IncreasingPair` type compares its arguments and swaps them if necessary.

If you want to extend the basic concept to allow other types to depend on abstract types, then the type theory becomes more complex. You enter the realm of modules and functors, about which there is a rich literature, especially based on ML-like languages.

Here are some historical papers that I think are worth reading for you because you're thinking among the same lines. They're fairly readable even without much of a mathematical background since they didn't have much mathematical theory to build on.

* James H. Morris, Jr. *Protection in programming languages*. Commun. ACM, 16(1):15– 21, 1973. doi:10.1145/361932.361937 — PDF
First read his POPL '73 paper *Types are not set*, if you can get a copy.
* Barbara Liskov and Stephen Zilles. *An Approach to Abstraction*. Computation Structures Group Memo 88, MIT (project MAC), Sept. 1973. PDF
And for a broader retrospective *A History of CLU*.
* David MacQueen. *Modules for Standard ML*. In LFP ’84: Proceedings of the 1984 ACM Symposium on LISP and functional programming, p. 198–207. doi:10.1145/800055.802036PDF
* John C. Mitchell and Gordon D. Plotkin. *Abstract Types Have Existential Type*. ACM Transactions on Programming Languages and Systems, Vol. 10, No. 3, July 1988, pp. 470–502. doi:10.1145/44501.45065PDF

As usual, Benjamin Pierce's *Types and Programming Languages* (TAPL) and the second book ATTAPL have relevant material: chapter 24 of TAPL about existential types and their use to model abstract types, and primarily Robert Harper's chapter on modules in ATTAPL.
> 8 votes

---
Tags: type-theory, functional-programming, type-checking, language-design
---


# Question
Title: Genetic Algorithms: Converge to best solution for one, few or many environments?
Let's say we take someone's garden (A) as the environment. We want a robot to pick up a series of eggs that chickens have laid in the garden, while covering as little ground as possible (those heavy rover tracks damage the turf, you know). So we evolve a solution whereby the genes representing the robot's *behaviour* (i.e. we are not just evolving some chain of path states/positions) work great in *that* garden.

All freshly laid eggs in (A) are collected in record time. Our algorithm has learned *some* tricks about navigating gardens; like driving a car for the first time. But there is more.

If I now put the same robot in a different garden (B), it may or may not do OK. It depends, I suppose, on how similar (B) is to (A) in certain key factors, i.e., will any of the tricks learned in (A) apply here? The likelihood is it will need new tricks, so I'm going to have evolve it further in (B) if I want anything like an optimal solution. Yet if I don't, at every iteration, continue to test it in (A) too, *then I may be losing fitness for (A) in every new generation, yes?*

So if I want a algorithm that performs well under a wide variety of circumstances, I am going to have to test it in all of those N circumstances, for all of the M candidates; will I thus need to run MxN tests on each generation? What about circumstances I didn't cover?

# Answer
> 3 votes
Unless you define "wide variety" very precisely and prove that your algorithm is able to abstract over all varieties in the way you want, then yes, you'll have to test it every time. I think for most interesting problems you won't be able to produce such a proof.

For a related entertaining read, check Neural Network Follies. The author describes a project where a neural network was trained to spot tanks in images. Instead the network learned how to tell whether it's sunny or not.

# Answer
> 2 votes
To answer this question, we can just look at the real world. Because you are talking about genetic algorithms let's look at the evolution.

A giraffe is trained in Garden A(African Savannah) for thousand of years and now almost optimal(but still slowly evolving). You are now taking it to Garden B(North Pole) and expecting it to survive just because it knows to survive in a low food supply area. If you have to much time, the giraffe population will adapt to North Pole but it will leave it's abilities that is suited for Africa. For Example, it will become white to hide itself inside ice , have more hair etc. When you put it back to Garden A, it's fitness will absolutely fall.

The only species I know that can live through different environments without to long adaptation is `human`. You can put an African baby in north pole and it will learn how to survive when he is 20 years old. For Giraffe that adaptation will take probably thousand of years.

**Back to your question**, you can train your robot in different environment until it's fitness is optimal for one environment but as soon as you move to the next environment, the previous adaptation will fall and it will leave you in a vicious cycle where you only train your robot but can not maximize it's effectiveness.

---
Tags: algorithms, artificial-intelligence, genetic-algorithms
---


title: Knapsack with same value

text:
# Question
Title: Knapsack with same value
I'm wondering if there's a name/reference for the variant of knapsack problem where all items have the same value (so we only care about maximizing the number of items), but there are multiple weight constraints.

Maximize $\sum\_{j=1}^nx\_j$

subject to $\sum\_{j=1}^nw\_{ij}x\_j\leq W\_i$ for $1\leq i\leq m$

and $x\_i=0,1$.

This is a special case of multidimensional knapsack. I've looked at the list of knapsack problems, but the only one with uniform value is not multidimensional but instead wants the sum of weights to be exactly $W$. Is there some reference for the version I described?

# Answer
> 1 votes
Your problem appears to be a special case of integer programming where the variables are boolean. I could not find it on wikipedia, but a lot of course materials online introduce this problem as Capital Budgeting problem under different models of integer programming. Hope it helps.

---
Tags: terminology, optimization, reference-request, knapsack-problems
---


# Question
Title: Finding Shortest Paths of weighted graph using stacks
I will be given some kind of this graph as in the picture below. I've searched some algorithms but it seams as if it is something impossible for me to figure them out. In fact using Floyd–Warshall algorithm it is kinda of possible, but unfortunately I'm only allowed to use stacks (instead of matrices). I also looked for Dijkstra's algorithm but I could not get the relationship with my problem.

Clearly my aim is to get all **shortest paths** from one point to another one. As I mentioned I will just output the solution from my **stack** in a vector string. I guess I have to visit each node and what I am most afraid is of getting stacked in a loop or even loosing the track during the search. Also note that this is **not a directed graph**. If Dijkstra's algorithm is applicable here I would be very grateful if anyone of you would guide me and I would really appreciate any help, suggestion, idea or even a vision for not getting stacked in a loop or loosing the track while searching.

Thanks in advance.

# Answer
As with most graph searching algorithms, you have to keep the state of each node during the searching. The state would have following values: **white, gray, black** with following interpretation:

* **white** = node has not yet been discovered during the current search, or it is unreachable.
* **gray** = node that was discovered, but not yet processed by the search algorithm.
* **black** = reachable nodes in your graph, that the search algorithm has discovered and also processed.

This **labeling** ensures that you do not search in endless loops.

To get **all** shortest paths from a node **s** to another node **e**:

* mark all nodes nodes as **white**.
* then as you visit nodes you label them **gray** and put them on the stack.
* If you processed all neighbours of a node, you label it **black**.
* To recover all the shortest paths from s to e, you need to maintain an array, call it **parents**, i.e. parents(v) = u, meaning **v** was visited from **u**.

After you searched the whole graph, you proceed **backwards** from the end node **e** via the parents array, to get all the shortest paths from the starting node **s**.
> 1 votes

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


title: How Types avoids Russel's Paradox?

text:
# Question
Title: How Types avoids Russel's Paradox?
I gone through the Russel's paradox.

From Wikipedia :

> According to naive set theory, any definable collection is a set. Let R be the set of all sets that are not members of themselves. If R is not a member of itself, then its definition dictates that it must contain itself, and if it contains itself, then it contradicts its own definition as the set of all sets that are not members of themselves.

Next Russell's and Alonzo Church developed type theory to avoid this paradox. Can someone explain clearly how these types (type theory) avoids this paradox. Thanks

# Answer
There is a second solution to the conundrum, which is Quine's NF (New Foundations) set theory.

NF is a set theory that avoid the paradox, but a set of all sets does exist. NF avoids Russell's paradox by putting constraints on the what formulae are allowed in comprehension. In other words the predicate $\phi$ in

$$ \\{x\ |\ \phi(x)\\} $$

does not range over all predicates, but only over predicates that are "well-stratified". In particular, $true$ is well-stratified, so the universe

$$ U = \\{x\ |\ true\\} $$

is a set in NF. A first-order logic formula $\phi$ in the language of set-theory (i.e. $\in$ is the sole non-equality predicate) is **well-stratified**, provided there is a function

$$level : Vars \rightarrow \mathbb{N}$$

(Here $Vars$ is the set of all variables) such that the following holds.

* For all sub-formulae $x \in y$ in $\phi$: $level(x) + 1 = level(y)$.
* For all sub-formulae $x = y$ in $\phi$: $level(x) = level(y)$.

In summary, while ZF(C) set-theory avoids Russell's paradox by prohibiting sets that are **too big**, NF avoids Russell's paradox by prohibiting sets that are **too ugly**.
> 7 votes

# Answer
Here's a rough loose-goosey explanation.

---

For any type `t` we have a type denoted `set(t)`, along with an operation `_∈_ : t → set(t) →` , where  are the booleans.

Now the type of  is already sufficient to dismiss Russell's paradox ─more or less.

This is because we cannot form the expression `X ∈ X` as it is ill-defined and so Russell's set `{x : set | x ∉ x }` is ill-typed since  is not between sets at the same level, moreover, `set` needs to be over some type.
> 6 votes

# Answer
In MLT or CIC type thery (and HoTT), they use a hierarchy of universes, it is quite similar to the Grothendieck universe construction in the Tarski–Grothendieck set theory, which asserts for each set, there is some universe set containing it, a universe set is a model of ZFC, so every basic construction operation can be carry out within that universe, but not these operations applied on the universe. This is how TG set theory avoids Russell paradox. In TT, a similar construction is presented, namely $U\_1:U\_2:U\_3:\cdots$, so it avoids Russell paradox by throwing propositions about one level to a next level. Actually, any directed set suffices to serve as indices. The existence of universe is basically asserting the existence of inaccessible cardinals, which essentially saying you cannot construct that level using basic set theoretical operations (or in TT, basic type constructions) like union, powerset, replacement, etc.

I think TT and ST are quite the same in expressive power, but ST uses FOL as its logic, and TT's logic is itself, and it is intuitionistic in nature.
> 2 votes

---
Tags: type-theory, mathematical-foundations
---


# Question
Title: How to show that two vertices in a connected component are in the same set? (bi conditional)
Show that after all edges are processed by CONNECTED-COMPONENTS, two vertices are in the same connected component if and only if they are in the same set.

The CONNECTED-COMPONENTS algorithm is the following:

It seems pretty obvious that when we keep adding the vertices of the direct edges of a connected component to a set, eventually the set formed has all the vertices in the connected component - directly connected as well as indirectly connected. But how do I formally prove that? Also it seems like a biconditional to me. I've thought of things like loop-invariant or a proof by contradiction. But unable to exactly figure out what to do. Any help is appreciated.

# Answer
Below are two approaches to your problem.

# detailed semi-formal proof

Since you've provided a minimal context, I will state my assumptions then provide a solution. Moreover, I will use very basic loops rather than the fancy for-each loop since they are easier to prove correctness with ─more accurately, easier for me with my current knowledge.

1. We are assuming simple undirected graphs: ie., pairs `(V, E)` of a set `V` of vertices and a symmetric relation `E ⊆ V × V`.
2. Two vertices are “connected” precisely when there is a path along `E` between the two: `x ~ y ∶≡ (∃ n : ℕ • x Eⁿ y)` ─where the bullet serves to separate the bound variable of the quantifier and the body of the quantifier, and exponentiation is iterated relational product.
3. A “connected component” is a subgraph in which any two vertices are connected, and which is connected to no additional vertices in the supergraph. For our needs, we only consider connected components arising from subsets of vertices.

```
 connected-component
⇔ (∀ x,y :  • x ~ y) ∧ (∀  : ℙ V •  ⊆  ∧ (∀ x,y :  • x ~ y) ⇒  = )
⇔ (∀  : ℙ V • (∀ x,y :  • x ~ y) ∧  ⊆  ⇔  ⊆ )
⇔  is an ~-equivalence class

```

Note that ∧ means “and”.
4. `Make-set` assigns the emptyset ∅ to each vertex, in some look-up table. We assume this to be the case at the very beginning and so need not worry about it.

`Find-set` looks up the set that is associated to a vertex, in the aforementioned look-up table.

`Union(x,y)` alters the set associated to `x` by unioning it what the set associated to `y`, and does so as well for `y`. In particular, after this command we have `Find-set x = old-Find-set x ∪ old-Find-set y`.

---

5. The post-condition of the program is

```
∀ x : V •
   Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

```

i.e.,

```
∀ x : V • connected-component (Find-set x)

```

That is, the algorithm assigns the connected components to the associated sets of the vertices. Alternatively, it is: `Find-set x = the ~-equivalence class of x`.
6. From the post-condition,

```
  ∀ x : V •
   Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

```

The simplest thing to do is to replace a constant, say `E`, with a new variable, and relate it to the constant to obtain an invariant.

```
P ∷  ⊆ E  ∧
    (∀ x : V •
       Find-set x
       = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁))})

```

So it is obvious that the post-condition is obtained once we've arrived at the conclusion `E ⊆` . So a good idea is to increase until this condition is true. Moreover, the invaraint needs to hold before the loop and we can do this by setting  `≔ ∅`: indeed `∅ ⊆ E` and intially every vertex is assigned the emptyset which is what is needed since,

```
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁)))}
=⟨ initial value of  ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ ∅ xᵢ₊₁)))}
=⟨ definition of empty set ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • false))}
=⟨ “for all i, we have false  ≡ false” ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ false)}
=⟨ “false ∧ stuff ≡ false” ⟩
  {y : V ❙ (∃ x₀,…,xₙ : V • false)}
=⟨ “there is some stuff yielding false ≡ false” ⟩
  {y : V ❙ false }
=⟨ there are no y that make false true ⟩
  ∅
=⟨ initial value of Find-set ⟩
  Find-set x

```

So, to be very explicit, we assume that before the algorithm is run, we have

```
∀ x : V • find-set x = ∅.

```
7. Anyhow, the previous paragraph informs us that the algorithm we are looking for has the shape

```
{Pre: (∀ x : V • find-set x = ∅) }
 ≔ ∅
; {Invariant:  ⊆ E  ∧
(∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y           ∧ (∀ i • xᵢ  xᵢ₊₁))}) }
while ¬ E ⊆  : do-stuff
{Post: (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

```

Note that it is common to place “assert” statements within curly braces. `C♯` for example documents them in the form `Contract.Assert.IsTrue(...)`.
8. It seems the only thing left to do is find an implementation of `do-stuff`. Well, the loop terminates if we make the loop guard `¬ E ⊆`  false.

By the invariant, we know `♯ ≤ ♯E` and so increasing  will do the job. We can choose an edge of `E`, it doesn't matter which one as long as it's one we haven't considered it, and add that to . What, are there even such edges!? Well, by the invariant, we have  `⊆ E ∧ E ⊈`  within the loop, which implies `E - ≠ ∅`, whence there are such edges.

Hence, one possible candidate for `do-stuff` is

```
 (u,v) ≔ choose an edge from E -
 ;  ≔  ∪ {(u,v)}

```

The candidate is enough and we are done deriving our algorithm, “provided” that this choice of `do-stuff` does not ruin the invariant. It clearly does ruin the invariant since we have not altered the find-set for these two vertices.

The final result is

```
 {Pre: (∀ x : V • find-set x = ∅) }
  ≔ ∅
 ; {Invariant:  ⊆ E  ∧
 (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ  xᵢ₊₁))}) }
 while ¬ E ⊆  :
   (u,v) ≔ choose an edge from E -
   ; if find-set u ≠ find set u then union(u,v)
   ;  ≔  ∪ {(u,v)}
 {Post: (∀ x : V • Find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}

```
9. To relate this to your initial code, consider the following.

```
 for each i in S : do-stuff
≈
 visited ≔ ∅
 ; while visited ≠ S:
       i ≔ pick an element of S - visited
     ; do-stuff
     ; visited ≔ visited ∪ {i}

```

Our loop had `¬ E ⊆`  and this is tantamount to `E ≠` :

```
  E ≠
=⟨ bi-containment ⟩
  ¬(E ⊆  ∧  ⊆ E)
=⟨ invariant ⟩
  ¬(E ⊆  ∧ true)
=⟨ “stuff ∧ true ≡ true” ⟩
  ¬ E ⊆

```

We use basic while loops since they are easier to work with is all. I've never really learned to write correctness proofs for for-each loops.

Hope this helps!

# Bi-implication informal argument

The algorithm's post-condition is `find-set x = {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}`.

We show the equality using a bi-implication.

(⊆) ∷

By the construction of `find-set`, i.e., the way we add elements to the set associated to `x`, we know that any added element is connected to `x` and so `find-set x ⊆ {y : V ❙ (∃ x₀,…,xₙ : V • x = x₀ ∧ xₙ = y ∧ (∀ i • xᵢ E xᵢ₊₁))}`.

(⊇) ∷

We will show by induction that any vertex `y` at-least `n : ℕ` edges away from `x` must be within `find-set x`.

Base case: n = 0. Then `x = x₀ = xₙ = y` and clearly `y ∈ find-set x`.

Inductive step: if `x E x₁ E x₂ E ⋯ E xₙ E xₙ₊₁ = y` then by the inductive hypothesis `xₙ ∈ find-set x`; moreover, the algorithm ensures `find-set x = find-set xₙ`. Now since `(xₙ, xₙ+1)` is an edge ─a given─, the algorithm ensures `find-set xₙ₊₁ = find-set xₙ` but by the previous equalities we then have `y ∈ find-set y = find-set xₙ₊₁ = find-set xₙ = find-set x`.

:-)
> 1 votes

---
Tags: algorithms, graphs, proof-techniques, discrete-mathematics, union-find
---


# Question
Title: Why on board graphics is unfit for gaming/rendering?
What is the difference between a dedicated GPU and an integrated one?

# Answer
> 1 votes
The difference between dedicated and integrated device is in resources and power. Dedicated have own resources integrated share them with various tasks. Integrated is less parallel but has (commonly) higher frequency. Integrated card uses CPU and RAM while dedicated has own RAM and own cores (far more than dedicated one).

This makes integrated cards unfit for *real* graphics, besides rendering part there are also tasks like controlling the game, running AI, keeping buffers of done tasks etc.

---
Tags: graphics
---


# Question
Title: When is ε-removal from a CFG idempotent?
For which context-free grammars is it idempotent to remove $\varepsilon$-productions? Given that there are multiple rewriting algorithms which preserve language and leave the grammar without $\varepsilon$-productions (apart from $S \to \varepsilon$ iff $\varepsilon \in L(G)$), is this sensitive to the choice of algorithm?

As far as I can tell:

* If $L(G) \not \ni \varepsilon$ then rewriting is always idempotent: the second pass finds no $\varepsilon$-productions to operate on.
* If the start symbol doesn't occur on any right-hand-side it is always idempotent: after the first rewrite this property is maintained and there are no $\varepsilon$-productions except maybe $S \to \varepsilon$. The second pass may find an $\varepsilon$-production but since $S$ doesn't occur on any right-hand side there are no rules to transform.

Is there some variant of $\varepsilon$-removal which is always idempotent? Will treating the start symbol as never nullable (even if it is) produce an idempotent $\varepsilon$-removal algorithm? My tests suggest so, but I can't think of a proof at the moment.

# Answer
> 1 votes
Pretending the start symbol to not be nullable will lead to an $\varepsilon$-removal algorithm which is idempotent on all CFGs. I'll now formalize and prove this.

I define a non-terminal $A$ to be *S-nullable* iff

* It is not $S$ (the start symbol); and
* It either has a rule $A \to \varepsilon$ or it has a rule $A \to X\_1 \ldots X\_n$ where each $X\_i$ is an S-nullable non-terminal.

The $\varepsilon$-removal algorithm then becomes:

**Input:** A context-free grammar $G = (N, \Sigma, S, P)$.

**Output**: A context-free grammar $G\_\varepsilon$ with no S-nullable non-terminals and $L(G\_\varepsilon) = L(G)$.

**Procedure**: let $G' = (N, \Sigma, S, P \setminus \\{(A \to \varepsilon) \in P \mid A \not= S\\})$. For each non-terminal $A$ in $N$ which is S-nullable in $G$, for each rule $B \to \alpha A \beta$ in $G'$, add the rule $B \to \alpha \beta$ to $G'$ if $\alpha \beta \not= \varepsilon$ or $B = S$ ($\alpha$ and $\beta$ are strings in $(N \cup \Sigma)^\*$). Let $G\_\varepsilon$ be $G'$ after all such rules have been added.

**Note** that one-by-one addition of rules means that if we have $S \to ABCd$ and $ABC$ is nullable and we nullify $A$, $B$, $C$ in that order, we will first add $S \to BCd$, then add $S \to ACd$ and $S \to Cd$, then add $S \to ABd \mid Bd \mid Ad \mid d$. In other words, it should be equivalent to doing the combinatorial expansion of rules one rule at a time.

Clearly $G\_\varepsilon$ has **no S-nullable rules**: all $\varepsilon$ rules were removed (except $S \to \varepsilon$ if it was there), and no $\varepsilon$ rules were added (except maybe $S \to \varepsilon$). Hence no non-terminal is S-nullable directly (since $S$ is never S-nullable), and the inductive case has no basis to apply to.

Hence the algorithm is **idempotent**: it only adds or removes rules if there is an S-nullable non-terminal in $G$.

Also the algorithm **preserves language**, i.e. $L(G\_\varepsilon) = L(G)$, by translation of derivations.

When we derive $A \Rightarrow \varepsilon$, we can instead avoid introducing $A$ in the first place, unless $A = S$ in which case $S \to \varepsilon$ is a rule. In the other direction, when we derive $\alpha \beta$ we can sprinkle it with (S-)nullable non-terminals and derive $\varepsilon$ from those.

Once more, with formality:

**In one direction**, when $\alpha \beta$ is derived from $A$ in $G\_\varepsilon$ and $A \to \alpha \beta$ doesn't occur in $G$, this is because we added this rule based on finding $A \to \alpha B \beta$ with $B$ S-nullable. Either this rule occurs in $G$, in which case derive $\varepsilon$ from $B$, or this rule was itself added; let $\alpha' \beta' = \alpha B \beta$ such that we added $A \to \alpha' \beta'$ based on finding $A \to \alpha' C \beta'$ where $C$ is S-nullable.

Every inductive step searches for a right-hand side that's longer by 1 and bounded by the length of the longest rule in $G$, hence this process terminates. Derive $\varepsilon$ from all the back-filled non-terminals (they're all S-nullable). This will derive $\alpha \beta$ from $A$ in multiple steps, hence $\Rightarrow^\*$ is preserved (in one direction).

**In the other direction**, if $\varepsilon$ is derived from $A$ (in a single step) where $A \to \varepsilon$ doesn't occur in $G\_\varepsilon$, we know that $A \not= S$ (because we never remove $S \to \varepsilon$) and $A$ is S-nullable; hence we must have previously derived some sentential form containing $A$ in at least one derivation step.

Let $B \to \alpha A \beta$ be the rule which introduced the $A$ in question. If $\alpha \beta \not= \varepsilon$, we added the rule $B \to \alpha \beta$. Use this rule instead. (Any derivations performed between introducing and eliminating $A$ can still be performed, and have identical results.)

If $\alpha \beta = \varepsilon$, then either $B = S$ or $B$ is S-nullable. If $B = S$ we added the rule $S \to \varepsilon$; use this to replace the derivation $\gamma \underline{S} \delta \Rightarrow \gamma A \delta$ with $\gamma \underline{S} \delta \Rightarrow \gamma \delta$.

If $B \not= S$ it is S-nullable (as $B \Rightarrow A \Rightarrow \varepsilon$) and some other rule introduced $B$ to our sentential form. Apply the same replacement; the number of recursive steps is bounded above by the number of derivation steps done so far.

**Unrelated observation**: if in $G$ we have rules $S \to \varepsilon$ and $A \to \alpha S \beta$ then $G\_\varepsilon$ will still have those rules, i.e. it will not be essentially non-contracting. However, if $S$ never occurs on the right-hand side of any rule in $G$, then $G\_\varepsilon$ will be essentially non-contracting (and $S$ will also not occur on any right-hand side in $G\_\varepsilon$).

---
Tags: algorithms, context-free, formal-grammars, normal-forms
---


# Question
Title: Regular Expression to Context-Free Grammar
Anyone knows if there is an algorithm for directly write the context-free grammar that generates a given regular expression?

# Answer
I assume you want to get a grammar that generates the same language as the given regular expression.

You can achieve that by the following steps:

1. Translate the regular expression into an NFA.
2. Translate the NFA into a (right-)regular grammar.

Both translations are standard and covered in basic textbooks on formal languages and automata. Note that any regular grammar is also context-free.
> 9 votes

# Answer
Yes. I give the high-level answer, without many details.

First you have to parse the expressions. That can be done using a simple recursive decent parser. Several examples on the web.

Then you should add "semantic" rules to the parser, when returning from the recursion. Those are standard in any formal language theory course. If $S\_1$ and $S\_2$ are non-terminals that generate expressions $E\_1$ and $E\_2$ then we can generate $E\_1+E\_2$ by $S$ and the rules $S\to S\_1$, $S\to S\_2$. We can generate concatenation $E\_1 E\_2$ by $S$ and the rule $S\to S\_1 S\_2$. $E\_1\*$ by $S$ and the rules $S\to S\_1 S$, $S\to \lambda$. Assuming we choose fresh nonterminals each time.
> 4 votes

# Answer
Like a previous answer, I assume you want to get a grammar that generates the same language as the given regular expression $r$.

A recursive algorithm for constructing a context-free grammar $G$ with $L(G) = L(r)$ goes as follows:

* if $r = \emptyset$, output a grammar with no production rules (or $S \to S$ if it must have a rule).
* if $r = \Lambda$, output $S \to \Lambda$.
* if $r = a$ (the expression is just a single letter), output $S \to a$.
* if $r = a \cup b$ (union, also notated as + or |): construct disjoint grammars for $a$ and $b$ with start symbols $S\_a$ and $S\_b$, combine them and add $S \to S\_a \mid S\_b$.
* if $r = lr$ (concatenation, also notated as $\cdot$): construct disjoint grammars for $l$ and $r$ with start symbols $S\_l$ and $S\_r$, combine them and add $S \to S\_l S\_r$.
* if $r = x^\*$ (Kleene star): construct a grammar for $x$ with start symbol $S\_x$ and add $S \to S\_x S \mid \Lambda$.

This is essentially equivalent to Hendrik's answer, but with more detail which may be useful.
> 2 votes

---
Tags: formal-grammars, regular-expressions, context-free
---


# Question
Title: Complexity of finding a perfect matching in directed graphs
To the best of my knowledge, finding a perfect matching in an undirected graph is NP-hard. But is this also the case for directed and possibly cyclic graphs?

I guess there are two possibilities to define whether two edges are incident to each other, which would also result in two possibilities to define what is allowed in a perfect matching:

1. Allowed in the perfect matching are only edges that do not share a common start or end point, i.e. antiparallel edges are not allowed in the perfect matching.
2. Antiparallel edge are allowed in the perfect matching, i.e. selecting edge $v\_i\rightarrow v\_j$ does not exclude selecting $v\_ j\rightarrow v\_i$.

What I've read sofar, option 1 is the typical generalization for directed graphs, but is finding a perfect matching NP-hard for both cases?

# Answer
> 2 votes
You can find the maximum matching in all three cases in polynomial time. It follows that it's possible to check whether there exists a perfect matching and, if so, to find one.

Finding a maximum matching in an undirected graph can be done in polynomial time. It is not known (or likely) to be NP-hard. See https://en.wikipedia.org/wiki/Matching\_(graph\_theory)#Algorithms\_and\_computational\_complexity.

If you define the problem according to option 1, then finding a maximum matching in an undirected graph $G$ is equivalent to finding a perfect matching in the corresponding undirected graph (where you just ignore the edge directions) -- and thus can also be done in polynomial time.

If you use option 2, then the following algorithm can be used to find a maximum matching in polynomial time:

* Given a directed graph $G=(V,E)$, construct a *weighted* undirected graph $G'=(V,E')$ with edge set defined as follows:

+ If $G$ has an edge $v \to w$ but not its reverse $w \to v$, add $(v,w)$ to $E'$ with weight 1.
    + If $G$ has an edge $v \to w$ and also its reverse $w \to v$, add $(v,w)$ to $E'$ with weight 2.
* Find the maximum-weight matching in $G'$, i.e., the matching whose weight is maximized.
* Now turn this into a set of edges in the original directed graph. If this process selected an edge $(v,w)$ and $G$ contains both $v\to w$ and $w\to v$, add both to the matching in $G$. If it selected an edge $(v,w)$ and $G$ contains only one of $v \to w$, $w\to v$ but not the other, add the one you can.

This runs in polynomial time and finds the maximum matching in $G$.

A simpler way to check whether $G$ has a perfect matching (i.e., one that covers all the vertices) is to construct the undirected graph $G'$ (you can ignore the weights) and check whether $G'$ has a perfect matching.

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